Adrian's Blog

[C語言] 兩變數內容值互換技巧

2011-08-11T20:14:00.021+08:00

記得大學時, C語言課程一定會談到兩變數內容值互換技巧, 其方法利用暫存空間實現, 如底下程式碼所示:

void swap(int *a, int *b)

{

  int tmp;



  tmp = *a;

  *a = *b;

  *b = tmp;                                                                                             

}

然而, 有幾個方法不使用暫存空間便能達到此目的.

方法一使用三次互斥或 (Exclusive OR, XOR)

void swap(int *a, int *b)

{

  if(*a != *b) {

      *a = *a ^ *b;

      *b = *a ^ *b;

      *a = *a ^ *b;

  }

}

演算式如下所示:

簡化上段程式碼: 試想底下程式碼有沒有什麼問題?

#include <stdio.h>                                                      



void swap(int *a, int *b)

{

  if(*a != *b)

      *a ^= *b ^= *a ^= *b;

}



int main(void)

{

  int a = 11, b = 3;



  printf("===== before swapping =====\n");

  printf("a: %d, b: %d\n", a, b);



  swap(&a, &b);



  printf("===== after swapping =====\n");

  printf("a: %d, b: %d\n", a, b);



  return 0;

}

直接看執行結果:

為什麼會這樣呢? 筆者將此C程式碼用gcc編譯成組合語言, 用以了解其運作邏輯, 底下為swap函式片段程式碼, 完整組合語言程式碼請按此連結下載.

程式堆疊示意圖

程式說明:

由於使用一行程式碼做三次XOR, gcc編譯器會先把*a, *b, *a, *b的內容放在edx(11), ecx(3), ebx(11), eax(3)暫存器 (line 9-16), 然後再分別對這四個暫存器做三次的XOR:

line 18-20: 第一次XOR (eax=3 XOR ebx=11), 並將其結果 (ebx=8)回存到變數a的記憶體位址, 如下圖所示:
line 21-25: 第二次XOR (eax=8 XOR ecx=3), 並將其結果 (ecx=11)回存到變數b的記憶體位址, 如下圖所示:
line 26-30: 第三次XOR (eax=11 XOR edx=11), 並將其結果 (edx=0)回存到變數a的記憶體位址, 如下圖所示:

所以問題在於, 程式設計師不能在一行程式碼中, 對同一變數做兩次的運算, 否則會造成不可預知的結果, 切記!

方法二使用加減法

void swap(int *a, int *b)

{

  if(*a != *b) {

      *a = *a + *b;

      *b = *a - *b;

      *a = *a - *b;

  }

}

演算式如下所示:

【Reference】
[1] XOR - the magic swap
[2] XOR swap

簡介C語言volatile關鍵字及其陷阱

2011-08-05T19:14:00.005+08:00

volatile變數代表其所儲存的內容會不定時地被改變，宣告volatile變數用來告訴編譯器 (Compiler) 不要對該變數做任何最佳化操作，凡牽涉讀取該volatile變數的操作，保證會到該變數的實體位址讀取，而不會讀取CPU暫存器的內容 (提升效能) 。舉個例子，某一硬體狀態暫存器 (Status Register)就必須宣告volatile關鍵字，因為該狀態暫存器會隨時改變，宣告volatile便可確保每次讀取的內容都是最新的。

Volatile關鍵字的應用範疇

1. 硬體暫存器，如狀態暫存器。
2. 多執行緒所共用的全域變數。
3. 中斷服務函式 (Interrupt Service Rountie，ISR)所使用的全域變數。

Volatile陷阱
想想底下範例是否有問題?



#include <stdio.h>



int square(volatile int *var)

{

    return *var **var;

}



int main(void)

{

    int    var = 5;



    printf("result: %d\n", square(&var));

    return 0;

}

其問題在於square函式的平方算式，*var**var，此指令代表到var位址讀取其內容。然而，var位址可能儲存硬體暫存器，這些暫存器內容會隨時間而改變 (例如: 狀態暫存器)，有可能第一次讀取的時候為4, 下一次讀取為5, 導致計算出來的值不正確。

因此，避免此錯誤發生便是在square函式宣告一local變數，看底下程式範例較為清楚:



#include <stdio.h>



int square(volatile int *var)

{

    int    local_var = *var;



    return local_var * local_var;

}



int main(void)

{

    int    var = 5;



    printf("result: %d\n", square(&var));

    return 0;

}

【Reference】
[1] How to Use C's volatile Keyword

[Linux Kernel] Allocate memory buffer whose starting address is aligned with the specific memory size

2011-07-26T21:07:00.005+08:00

撰寫裝置驅動程式時, 常常會因為硬體需求, 需配置一塊記憶體空間用來映射至硬體的I/O或記憶體空間, 且此已配置記憶體空間的起始位址往往都必須對齊某一固定大小的記憶體。舉例來說，欲配置4906位元的記憶體空間，且起始位址需對齊16位元。底下為C語言範例程式。

void *memory_align(unsigned int size, unsigned int aligned_size)

{

    void *ptr;



    unsigned int mask = ~(aligned_size -1);



    if((ptr = malloc(sizeof(size + (aligned_size - 1)))) == NULL) {

        perror("memory allocation failed");

        return NULL;

    }



    ptr = (void *) ((unsigned int) (ptr + (aligned_size - 1)) & mask);



    return ptr;

}

unsigned int mask = ~(aligned_size -1);

此mask變數為位元遮罩, 假設aligned_size=16, 則mask=0xFFFFFFF0。

ptr = malloc(sizeof(size + (aligned_size - 1)))

由於我們欲讓所配置的記憶體起始位址對齊aligned_size, 所以需向系統配置size+(aligned_size - 1)大小的記憶體空間。

ptr = (void *) ((unsigned int) (ptr + (aligned_size - 1)) & mask);

把所配置的記憶體起始位址加上(aligned_size - 1)，然後跟mask變數做位元遮罩，如此便能取得正確的記憶體起始位址。

下圖為詳細範例計算

範例程式下載

解決"sudo: must be setuid root"的問題

2010-12-28T18:16:00.004+08:00

今天在自己的Linux桌機 (Ubuntu 10.10) 幹了一件傻事:

$ sudo chown -R adrian.adrian /usr/

結果導致使用sudo會有底下的問題:

$ sudo su
sudo: must be setuid root

這下可high了, Ubuntu在安裝的時候並沒有讓管理者設定root密碼, 所以無法使用root登入, 沒有root權限什麼事都不能做啊! 底下解決方式:

重新啟動Ubuntu，在grub選單中選擇有recovery mode的選項, Ex: "Ubuntu, with Linux 2.6.35-23-server (recovery mode)"
以recovery模式開機後, 會出現"Recovery Menu"選單, 選擇"root Drop to root shell prompt"選項就可進入root shell prompt。
利用ls -l觀看sudo資訊，所以是擁有此程式使用者的問題。
```
-rwxr-xr-x 2 adrian adrian 147872 2010-09-01 04:39 /usr/bin/sudo
```

執行底下指令便可大功告成:

# chwon root:root /usr/bin/sudo
# chmod 4755 /usr/bin/sudo
# reboot

最後還是乖乖地把/usr/重新設定回root。
```
$ sudo chown root.root /usr/
```

【Reference】
[1] Ubuntu forum

[打造簡易作業系統 - 以GNU Assembler組合語言撰寫] (七) 利用Call Gate與TSS (Task-State Segment)實現特權等級的轉換

2010-12-21T10:09:00.018+08:00

上篇文章僅介紹如何利用Call Gate，文中並未提及如何實現特權等級的轉換，也就是從低特權等級進入高特權等級，就如同Linux的user space (Privilege 3或稱Ring 3)進入kernel space (Privilege 0或稱Ring 0)。

簡介TSS (Task-State Segment)
本文僅簡單說明TSS在本文被使用的地方，如欲詳盡說明請參考[2]之第七章。

Task Structure
Figure 1為一個工作任務 (Task)的結構圖，一個工作任務分為兩大部份: 1. 工作任務的執行空間 (Task Execution Space)，其中包含CS、SS以及若干個DS，也就是Figure 1右上角的三個區段。2. TSS: 由工作任務執行空間與一個儲存空間 (用來儲存工作任務的狀態)所組成。Figure 1又說明另一件事: TSS的Segment Selector必須儲存在Task Register。因此在使用TSS之前，必須使用LTR指令將TSS之Segment Selector載入至Task Register。

Figure 1 Structure of a Task

TSS Memory Layout
Figure 2為32位元TSS記憶體空間配置圖，如下所述:

ESP0、SS0、ESP1、SS1、ESP2與SS2: 分別為特權等級0、1與2的堆疊區段與堆疊指標，也就是Figure 1右下角三個 "Stack Seg. Priv. Level x"。本文利用ESP0與SS0實現特權等級的轉換 (Ring 3轉換至Ring 0)，因此作者僅設定TSS的這兩個欄位，其它欄位則設為0。
其它欄位在此不進一步探討，有興趣的網友可以參考[2]。

Figure 2 TSS Memory Layout

原始碼下載

由於篇幅的關係，往後該系列文章將不張貼程式碼，將提供連結下載方式，原始碼下載點。

作業系統程式碼說明
Figure 3為作業系統程式碼解說圖，此圖說明GDT與LDT的記憶體配置圖與程式流程圖，其流程圖並非以傳統方式表示。取而代之，改以紅色圈圈的數字代表程式流程並搭配GDT與LDT記憶體配置圖，如此更能清楚地明白程式執行流程。底下將針對每一步驟 (紅色圈圈的數字)做詳盡的解釋:

Figure 3 High Level Perspective of OS code

使用ljmp指令由真實模式轉換至32位元保護模式 (Ring 0)。其片段程式碼如下所示:


  /* Jump to protected-mode OS code        *
   * ljmpl prototype:                      *
   *   ljmpl segment_selector_of_CS offset */
  ljmpl     $SegSelectorCode32, $0

此區段程式碼將Msg1輸出至螢幕，並將LDT的segment selector載入至LDTR，接著使用lcall指令跳至LDT的CS，如下所示:

    /* Load LDT selector */
   mov     $(SegSelectorLDT), %ax

   /* Load LDT selector in GDT to LDT register */
   lldt     %ax

   /* Jump to code segment in LDT */
   lcall     $(SegSelectorLDTCode32), $0

如第1點所述。
如第1點所述。
輸出Msg2，隨即使用lret指令返回LABEL_GDT_CODE。
通常，call與ret指令必須配合使用。執行call指令時，處理器會將SS、ESP、CS與EIP推入(Push) 該執行空間的堆疊 (Stack)。接著，執行ret指令時，處理器會將EIP、CS、ESP與SS從堆疊取出 (Pop)。為了實現從Ring 0返回Ring 3，底下程式碼模擬處理器的工作: 將Ring 3的SS、ESP、CS與EIP推入(Push) 該執行空間的堆疊 (Stack)並使用lret指令返回Ring 3。
```
   pushl    $(SegSelectorStackR3)
  pushl    $(TopOfStackR3)
  pushl    $(SegSelectorCodeR3)
  pushl    $0
  lret
```
從Ring 0 (LABEL_GDT_CODE)返回 Ring 3 (LABEL_GDT_CODE_R3)。

此Ring 3程式區段將Msg1_R3輸出至螢幕，利用call gate並搭配TSS成功地返回Ring 0程式區段。因此，必須設定TSS之ESP0與SS0欄位，如下所示:

LABEL_TSS:
 .4byte  0                         /* Previous Task Link   */
 .4byte  TopOfStackR0              /* ESP0                 */
 .4byte  SegSelectorStackR0        /* SS0                  */
 .4byte  0                         /* ESP1                 */
 .4byte  0                         /* SS1                  */
 .4byte  0                         /* ESP2                 */
 .4byte  0                         /* SS2                  */
 .4byte  0                         /* CR3 (PDBR)           */
 .4byte  0                         /* EIP                  */
 .4byte  0                         /* EFLAGS               */
 .4byte  0                         /* EAX                  */
 .4byte  0                         /* ECX                  */
 .4byte  0                         /* EDX                  */
 .4byte  0                         /* EBX                  */
 .4byte  0                         /* ESP                  */
 .4byte  0                         /* EBP                  */
 .4byte  0                         /* ESI                  */
 .4byte  0                         /* EDI                  */
 .4byte  0                         /* ES                   */
 .4byte  0                         /* CS                   */
 .4byte  0                         /* SS                   */
 .4byte  0                         /* DS                   */
 .4byte  0                         /* FS                   */
 .4byte  0                         /* GS                   */
 .4byte  0                         /* LDT Segment Selector */
 .2byte  0                         /* Reserved             */
 .2byte  (. - LABEL_TSS + 2)       /* I/O Map Base Address */
.set TSSLen, (. - LABEL_TSS)

在此，特別對特權等級轉換做進一步解釋，以便讓讀者了解為什麼只要設定ESP0與SS0欄位即可。當存取目的程式區段 (Destination Code Segment)是被允許的，處理器便會根據Call Gate Descriptor的Segment Selector欄位找出對應的程式區段，如果又涉及特權等級轉換，處理器會將原本使用中的堆疊切換至目標特權等級的堆疊。舉例來說，假設目前程式區段運行於Ring 3，處理器便使用Ring 3的堆疊，當使用Call Gate欲轉換至Ring 0的程式區段。如果此要求是被允許的，則處理器會跳至Ring 0的程式區段並使用Ring 0的堆疊，因此程式設計員必須先設定Ring 0堆疊 (ESP0與SS0)，這就是為什麼必須設定TSS的ESP與SS0欄位的原因。

跳至GDT之Call Gate的描述子 (Descriptor)。
根據Call Gate描述子的Segment Selector欄位找出對應的CS。
將Msg3輸出至螢幕並返回。
返回Ring 3程式區段，並執行一無窮迴圈。

QEMU測試結果

【Reference】
[1] Solrex - 使用開源軟體-自己動手寫作業系統
[2] Intel 64 and IA-32 Architectures. Software Developer's Manual. Volume 3A
[3] 30天打造OS！作業系統自作入門
[4] Jserv's Blog
[5] X86 開機流程小記
[6] Linux assemblers: A comparison of GAS and NASM
[7] linux-source-2.6.31

[8] 本篇範例下載點

[打造簡易作業系統 - 以GNU Assembler組合語言撰寫] (六) 簡介Call Gate

2010-12-08T16:22:00.010+08:00

Call Gate主要目的用來將一程式的特權等級 (Privilege Level) 轉換至另一個特權等級。舉例來說，Linux使用者利用ioctl()系統呼叫從user space (Privilege 3)進入kernel space (Privilege 0)。

Note
本篇範例程式僅示範如何使用call gate，並如何利用call gate呼叫所對應的程式碼片段，所有的程式碼都運行於privilege 0。對於特權等級的轉換 (Privilege 3 -> Privilege 0)，留待往後的文章再詳加探討。本篇文章僅簡單地介紹Call Gate，詳盡介紹請參考Intel 64 and IA-32 Architectures. Software Developer's Manual. Volume 3A之5.8節。

Call-Gate Descriptor之介紹
參考Figure 1，其欄位如下所述:

Offset: 代表所指定的程式區段 (Code Segment)進入點 (Entry Point)，通常都設為0。
Segment Selector: 此區段選擇器指定所要存取的程式區段 (Code Segment)。如此說明或許有點模糊，請參考Figure 2，此圖紅色數字方塊展示出設定Call Gate的必要程序，因此設定Call Gate需要三道步驟：A. 設定Call Gate Descriptor相關欄位，其欄位設定值如Table 1所示。B. 設定對應之程式區段。C. 設定Call-Gate之區段選擇器。
Param. Count: 指定呼叫程序 (Calling Procedure)欲傳遞幾個參數給被呼叫的程序 (Called Procedure)。
DPL (Descriptor Privilege Level): 此區段描述子之特權等級，其DPL與RPL特權等級之檢查請參考Intel 64 and IA-32 Architectures. Software Developer's Manual. Volume 3A之Figure 5-11。
P: 此Call-Gate描述子是否有有效 (有效: P=1, 無效: P=0)。

Figure 1. Call-Gate Descriptor

Figure 2. Steps for Configuring Call Gate

Table 1. Field Value Configuration for Call-Gate Descriptor

Boot Loader程式碼
請參考此篇文章的"Boot Loader 程式碼"。

作業系統程式碼
Figure 3為作業系統程式碼，此作業系統程式碼運行於32位元保護模式，程式說明如下:

定義七個Segment Descriptor (LABEL_GDT_NULL、LABEL_GDT_CODE、LABEL_GDT_DATA、LABEL_GDT_VIDEO、LABEL_GDT_LDT、LABEL_GDT_CG_CODE與LABEL_GDT_CG)。其中VIDEO的基底位址為0xB8000，詳情請參考Printing to Screen。接著定義GDT的長度、定義Code、Data、VIDEO與LDT的segment selector、定義輸出的字串、定義GDTPtr與定義LDT表。
LABEL_GDT_CG為Call Gate Descriptor，其儲存在GDT。此設定步驟為Figure 2的1號紅色方塊。
LABEL_GDT_CG_CODE為Call Gate Descriptor欄位Segment Selector所指定的地方，也就是Call Gate所對應的區段程式碼。此設定步驟為Figure 2的2號紅色方塊。

/* os.S
*
*/

#include "pm.h"

.code16
.text
  jmp os_main

# Segment descritors for GDT
LABEL_GDT_NULL:     SEG_DESC     0, 0, 0
LABEL_GDT_CODE:     SEG_DESC     0, (PECode32Len - 1), (DESC_ATTR_TYPE_CD_ER | DESC_ATTR_D)
LABEL_GDT_DATA:     SEG_DESC     0, (DataLen - 1), (DESC_ATTR_TYPE_CD_RW)
LABEL_GDT_VIDEO:    SEG_DESC     0xB8000, 0xFFFF, (DESC_ATTR_TYPE_CD_RW)
LABEL_GDT_LDT:      SEG_DESC     0, (LDTLen - 1), (DESC_ATTR_TYPE_LDT)
LABEL_GDT_CG_CODE:  SEG_DESC     0, (CG_CODE32_LEN - 1), (DESC_ATTR_TYPE_CD_ER | DESC_ATTR_D)
LABEL_GDT_CG:       CALL_GATE    SegSelectorCGCODE, 0, 0, (GATE_CG_ATTR)

# The length of GDT
.set GdtLen, (. - LABEL_GDT_NULL)

# Segment selectors
.set SegSelectorCode32,   (LABEL_GDT_CODE - LABEL_GDT_NULL)
.set SegSelectorData,     (LABEL_GDT_DATA - LABEL_GDT_NULL)
.set SegSelectorVideo,    (LABEL_GDT_VIDEO - LABEL_GDT_NULL)
.set SegSelectorLDT,      (LABEL_GDT_LDT - LABEL_GDT_NULL)
.set SegSelectorCGCODE,   (LABEL_GDT_CG_CODE - LABEL_GDT_NULL)
.set SegSelectorCG,       (LABEL_GDT_CG - LABEL_GDT_NULL)

# data segment
LABEL_DATA:
Msg1:     .ascii "Welcome to Protect mode in GDT.\0"
Msg2:     .ascii "Welcome to Protect mode in LDT.\0"
Msg3:     .ascii "Welcome to Protect mode through Call Gate.\0"

.set     Msg1Offset, (Msg1 - LABEL_DATA)
.set     Msg2Offset, (Msg2 - LABEL_DATA)
.set     Msg3Offset, (Msg3 - LABEL_DATA)

.set DataLen, (. - LABEL_DATA)

# GDTR pointer
LABEL_GDTR:
  .2byte (GdtLen - 1)     # Limit field
  .4byte 0                 # base field

# LDT information
LABEL_LDT:
LABEL_LDT_ENTRY: SEG_DESC 0, (LDT_CODE32_LEN - 1), (DESC_ATTR_TYPE_CD_E | DESC_ATTR_D)

# length of LDT
.set LDTLen, (. - LABEL_LDT)

# LDT selector
.set SegSelectorLDTCode32,     (LABEL_LDT_ENTRY - LABEL_LDT + SA_TIL)


# real-mode OS code
os_main:
  mov %cs, %ax
  mov %ax, %ds
  mov %ax, %ss
  mov %ax, %es


  /* Set gdt for code segment */
  InitSegDescriptor LABEL_PE_CODE32, LABEL_GDT_CODE
  InitSegDescriptor LABEL_DATA, LABEL_GDT_DATA
  InitSegDescriptor LABEL_LDT, LABEL_GDT_LDT
  InitSegDescriptor LABEL_PE_LDT_CODE32, LABEL_LDT_ENTRY
  InitSegDescriptor LABEL_PE_CG_CODE32, LABEL_GDT_CG_CODE

  /* Set GDTR */
  xor     %ax, %ax
  mov     %cs, %ax
  shl     $4, %eax
  addl    $LABEL_GDT_NULL, %eax
  movl     %eax, (LABEL_GDTR + 2)             

  /* Enable A20 line */
  xor     %ax, %ax
  in      $0x92, %al
  or      $2, %al
  out     %al, $0x92

  cli

  /* Load the GDT base address and limit from memory into the GDTR register */
  lgdt     LABEL_GDTR

  /* Enable protect mode */
  movl     %cr0, %eax
  orl      $1, %eax
  movl     %eax, %cr0

  /* Jump to protected-mode OS code */
  ljmp     $SegSelectorCode32, $0

LABEL_PE_CG_CODE32:
.code32
  mov     $(SegSelectorData), %ax
  mov     %ax, %ds
  mov     $(SegSelectorVideo), %ax
  mov     %ax, %gs

  xorl    %esi, %esi
  xorl    %edi, %edi
  movl    $Msg3Offset, %esi
  movl    $((80 * 11 + 0) * 2), %edi
  movb    $0xC, %ah

cg_dump_str:
  lodsb
  andb    %al, %al
  jz      cg_fin
  mov     %ax, %gs:(%edi) 
  addl    $2, %edi
  jmp     cg_dump_str

cg_fin:
  lret 

.set CG_CODE32_LEN, (. - LABEL_PE_CG_CODE32)

LABEL_PE_LDT_CODE32:
.code32
  # invoke a procedure call throught a call-gate.
  lcall   $(SegSelectorCG), $0

  mov     $(SegSelectorData), %ax
  mov     %ax, %ds
  mov     $(SegSelectorVideo), %ax
  mov     %ax, %gs

  xorl    %esi, %esi
  xorl    %edi, %edi
  movl    $Msg2Offset, %esi
  movl    $((80 * 13 + 0) * 2), %edi
  movb    $0xC, %ah

ldt_dump_str:
  lodsb
  andb    %al, %al
  jz      ldt_fin
  mov     %ax, %gs:(%edi) 
  addl    $2, %edi
  jmp     ldt_dump_str

ldt_fin:
  jmp     .

.set LDT_CODE32_LEN, (. - LABEL_PE_LDT_CODE32)

# protected-mode OS code in GDT
LABEL_PE_CODE32:
.code32 
  /* Load data segment selector */
  mov     $(SegSelectorData), %ax
  mov     %ax, %ds

  /* Load Video segment selector */
  mov     $(SegSelectorVideo), %ax
  mov     %ax, %gs

  /* Output the data */
  xorl    %esi, %esi
  xorl    %edi, %edi
  movl    $Msg1Offset, %esi
  movl    $((80 * 10 + 0) * 2), %edi
  movb    $0xC, %ah

dump_str:
  lodsb
  andb    %al, %al
  jz      fin
  mov     %ax, %gs:(%edi) 
  addl    $2, %edi
  jmp     dump_str

fin:
  /* Load LDT selector */
  mov     $(SegSelectorLDT), %ax

  /* Load LDT selector in GDT to LDT register */
  lldt    %ax

  /* Jump to code segment in LDT */
  ljmp    $(SegSelectorLDTCode32), $0

.set PECode32Len, (. - LABEL_PE_CODE32)
   
  .ascii "Welcome to OS context!"
  .byte   0 

  .org    0x400, 0x41 # fill characters with 'A'. Sector 2

Figure 3. Operating System Code

pm.h標頭檔

/* pm.h
*
* Adrian Huang (adrianhuang0701@gmail.com)
*/
.macro SEG_DESC Base, Limit, Attr
   .2byte (\Limit & 0xFFFF)
   .2byte (\Base & 0xFFFF)
   .byte  ((\Base >> 16) & 0xFF)
   .2byte ((\Attr & 0xF0FF) | ((\Limit >> 8) & 0x0F00))
   .byte  ((\Base >> 24) & 0xFF)
.endm

.macro InitSegDescriptor OFFSET GDT_SEG_ADDR
  xor     %ax, %ax
  mov     %cs, %ax
  shl     $4, %eax
  addl    $(\OFFSET), %eax
  movw    %ax, (\GDT_SEG_ADDR + 2)
  shr     $16, %eax
  movb    %al, (\GDT_SEG_ADDR + 4) 
  movb    %ah, (\GDT_SEG_ADDR + 7) 

.endm

.macro CALL_GATE SegSelector, Offset, ParamCount, Attr
  .2byte (\Offset & 0xFFFF)
  .2byte (\SegSelector)
  .byte  (\ParamCount)
  .byte  (\Attr)
  .2byte ((\Offset >> 16) & 0xFFFF)
.endm

.set DESC_ATTR_TYPE_LDT,         0x82     /* LDT Segment         */
.set DESC_ATTR_TYPE_CG,          0x8C     /* Call-Gate Segment         */
.set DESC_ATTR_TYPE_CD_ER,       0x9A     /* Code segment with Execute/Read */
.set DESC_ATTR_TYPE_CD_E,        0x98     /* Code segment with Execute Only */
.set DESC_ATTR_TYPE_CD_RW,       0x92     /* Data segment with R/W         */
.set DESC_ATTR_D,                0x4000   /* 32-bit segment                 */

/* Selector Attribute */
.set SA_TIL,      0x4
.set SA_RPL0,     0x0
.set SA_RPL1,     0x1
.set SA_RPL2,     0x2
.set SA_RPL3,     0x3

/* The attribute of call gate */
.set GATE_CG_ATTR, 0x8C

編譯程式碼
下圖為編譯的Makefile。

LD=ld
CC=gcc

all: boot_loader.bin

boot_loader.bin: boot_loader.o os.o
  ${LD} -Ttext=0x7C00 -s $< -o $@ --oformat binary    ${LD} -Ttext=0x0 -s os.o -o os.bin --oformat binary    cat os.bin >> $@

boot_loader.o:
  ${CC} -c boot_loader.S

os.o:
  ${CC} -c os.S

clean:
  rm -f boot_loader.o os.o os.bin boot_loader.bin

其編譯訊息如下所示:

adrian@adrian-desktop:~/working/build_os/my_ex/blog/pe-call-gate-same-priv$ make clean all
rm -f boot_loader.o os.o os.bin boot_loader.bin  
gcc -c boot_loader.S
gcc -c os.S
ld -Ttext=0x7C00 -s boot_loader.o -o boot_loader.bin --oformat binary
ld -Ttext=0x0 -s os.o -o os.bin --oformat binary
ld: warning: cannot find entry symbol _start; defaulting to 0000000000000000
cat os.bin >> boot_loader.bin
adrian@adrian-desktop:~/working/build_os/my_ex/blog/pe-call-gate-same-priv$

QEMU測試結果

【Reference】
[1] Solrex - 使用開源軟體-自己動手寫作業系統
[2] Intel 64 and IA-32 Architectures. Software Developer's Manual. Volume 3A
[3] 30天打造OS！作業系統自作入門
[4] Jserv's Blog
[5] X86 開機流程小記
[6] Linux assemblers: A comparison of GAS and NASM
[7] linux-source-2.6.31

現今最受歡迎的Linux Distribution

2010-11-02T14:06:00.001+08:00

今天在網路上看到很有興趣的Linux Distribution搜尋排名比較，請參考原文網址，其中DistroWatch根據使用者點閱Linux Distribution網頁所得出的結果如下:

1. Ubuntu
2. Fedora
3. Mint
4. OpenSUSE
5. Debian
6. PCLinuxOS
7. Mandriva
8. Sabayon
9. Arch
10. Puppy

然而，此統計數據以Linux Desktop OS Distribution為基礎，所以Android沒在排名之中。

於是，作者利用Google Trend所得出的結果，則是Android排名第一。

[打造簡易作業系統 - 以GNU Assembler組合語言撰寫] (五) 使用Local Descriptor Table (LDT)

2010-10-11T14:39:00.005+08:00

上篇文章使用Global Descriptor Table (GDT)儲存Code Segment (CS)與Data Segment (DS)的資訊，以便能在保護模式下成功地執行程式碼與存取資料。本篇說明如何設定LDT，以便能執行位於LDT的程式碼。

LDT之介紹
LDT實現作業系統多個程序功能 (multiple processes)，其特色為各個程序有自己的位址空間彼此互不干擾，每個程序會有各自的LDT，當作業系統欲執行某一程序時，作業系統會找出其對應的LDT，以便能執行該程序。詳細資料請參考Local Descriptor Table。

LDT相關設定
LDT設定分成兩大步驟如下所述:

1. 在GDT表裡設定一個LDT entry (Configure a LDT Entry in GDT)
參考Figure 1，其每個欄位所應設定值如Table 1所示:

Figure 1. Segment Descriptor

Table 1. LDT entry configuration in GDT

2. 設定LDT表
LDT表設定code segment/data segment相關資訊，其設定值如Table 2所示。

Table 2. LDT entry configuration in LDT

Boot Loader程式碼
請參考上篇文章的"Boot Loader 程式碼"。

作業系統程式碼
Figure 2為作業系統程式碼，此作業系統程式碼運行於32位元保護模式，一開始定義三個Segment Descriptor (NULL、CODE32、VIDEO與LDT)，其中VIDEO的基底位址為0xB8000，詳情請參考Printing to Screen。接著定義GDT的長度、定義Code32、Data、VIDEO與LDT的segment selector、定義輸出的字串、定義GDTPtr與定義LDT表。

/* os.S
*
*/

#include "pm.h"

.code16
.text
  jmp os_main

# Segment descritors for GDT
LABEL_GDT_NULL: SEG_DESC 0, 0, 0
LABEL_GDT_CODE: SEG_DESC 0, (PECode32Len - 1), (DESC_ATTR_TYPE_CD_ER | DESC_ATTR_D)
LABEL_GDT_DATA: SEG_DESC 0, (DataLen - 1), (DESC_ATTR_TYPE_CD_RW)
LABEL_GDT_VIDEO: SEG_DESC 0xB8000, 0xFFFF, (DESC_ATTR_TYPE_CD_RW)
LABEL_GDT_LDT: SEG_DESC     0, (LDTLen -1), (DESC_ATTR_TYPE_LDT)

# The length of GDT
.set GdtLen, (. - LABEL_GDT_NULL)

# Segment selectors
.set SegSelectorCode32, (LABEL_GDT_CODE - LABEL_GDT_NULL)
.set SegSelectorData,     (LABEL_GDT_DATA - LABEL_GDT_NULL)
.set SegSelectorVideo,     (LABEL_GDT_VIDEO - LABEL_GDT_NULL)
.set SegSelectorLDT,     (LABEL_GDT_LDT - LABEL_GDT_NULL)

# data segment
LABEL_DATA:
Msg1:     .ascii "Welcome to Protect mode in GDT.\0"
Msg2:     .ascii "Welcome to Protect mode in LDT.\0"
Msg3:     .ascii "This is signed by Adrian.\0"

.set     Msg1Offset, (Msg1 - LABEL_DATA)
.set     Msg2Offset, (Msg2 - LABEL_DATA)
.set     Msg3Offset, (Msg3 - LABEL_DATA)

.set DataLen, (. - LABEL_DATA)

# GDTR pointer
LABEL_GDTR:
  .2byte (GdtLen - 1)     # Limit field
  .4byte 0                 # base field

# LDT information
LABEL_LDT:
LABEL_LDT_ENTRY: SEG_DESC 0, (LDT_CODE32_LEN - 1), (DESC_ATTR_TYPE_CD_E | DESC_ATTR_D)

# length of LDT
.set LDTLen, (. - LABEL_LDT)

# LDT selector
.set SegSelectorLDTCode32,     (LABEL_LDT_ENTRY - LABEL_LDT + SA_TIL)


# real-mode OS code
os_main:
  mov %cs, %ax
  mov %ax, %ds
  mov %ax, %ss
  mov %ax, %es


  /* Set gdt for code segment */
  InitSegDescriptor LABEL_PE_CODE32, LABEL_GDT_CODE
  InitSegDescriptor LABEL_DATA, LABEL_GDT_DATA
  InitSegDescriptor LABEL_LDT, LABEL_GDT_LDT
  InitSegDescriptor LABEL_PE_LDT_CODE32, LABEL_LDT_ENTRY

  /* Set GDTR */
  xor     %ax, %ax
  mov     %cs, %ax
  shl     $4, %eax
  addl    $LABEL_GDT_NULL, %eax
  movl     %eax, (LABEL_GDTR + 2)             

  /* Enable A20 line */
  xor     %ax, %ax
  in         $0x92, %al
  or         $2, %al
  out     %al, $0x92

  cli

  /* Load the GDT base address and limit from memory into the GDTR register */
  lgdt     LABEL_GDTR

   /* Enable protect mode */
  movl     %cr0, %eax
  orl     $1, %eax
  movl     %eax, %cr0

  /* Jump to protected-mode OS code */
  ljmp     $SegSelectorCode32, $0


LABEL_PE_LDT_CODE32:
.code32
  mov     $(SegSelectorData), %ax
  mov     %ax, %ds
  mov     $(SegSelectorVideo), %ax
  mov     %ax, %gs

  xorl     %esi, %esi
  xorl    %edi, %edi
  movl     $Msg2Offset, %esi
  movl     $((80 * 11 + 0) * 2), %edi
  movb     $0xC, %ah

ldt_dump_str:
  lodsb
  andb     %al, %al
  jz      ldt_fin
  mov     %ax, %gs:(%edi) 
  addl     $2, %edi
  jmp     ldt_dump_str

ldt_fin:
  jmp .

.set LDT_CODE32_LEN, (. - LABEL_PE_LDT_CODE32)

# protected-mode OS code in GDT
LABEL_PE_CODE32:
.code32 
  /* Load data segment selector */
  mov     $(SegSelectorData), %ax
  mov     %ax, %ds

  /* Load Video segment selector */
  mov     $(SegSelectorVideo), %ax
  mov     %ax, %gs

  /* Output the data */
  xorl     %esi, %esi
  xorl    %edi, %edi
  movl     $Msg1Offset, %esi
  movl     $((80 * 10 + 0) * 2), %edi
  movb     $0xC, %ah

dump_str:
  lodsb
  andb     %al, %al
  jz      fin
  mov     %ax, %gs:(%edi) 
  addl     $2, %edi
  jmp     dump_str

fin:
  /* Load LDT selector */
  mov     $(SegSelectorLDT), %ax

  /* Load LDT selector in GDT to LDT register */
  lldt     %ax

  /* Jump to code segment in LDT */
  ljmp     $(SegSelectorLDTCode32), $0

.set PECode32Len, (. - LABEL_PE_CODE32)
   
os_msg:
  .ascii "Welcome to OS context!"
  .byte     0 

  .org    0x200, 0x41 # fill characters with 'A'. Sector 2

Figure 2. Code for Operating System

16位元real mode程式碼 (os_main)中，執行若干任務如下所述:

設定LABEL_GDT_CODE的基底位址為PE_CODE32的起始位址
設定LABEL_GDT_DATA的基底位址為LABEL_DATA的起始位址
設定LABEL_GDT_LDT的基底位址為LABEL_LDT的起始位址
設定LABEL_LDT_ENTRY的基底位址為LABEL_PE_LDT_CODE32的起始位址
設定GDTPtr的基底位址為GDT的起始位址(也就是GDT_DESC_NULL)
開啟A20線路 (A20 Line)
將GDT的起始位址載入至GDTR暫存器
設定cr0暫存器的bit 0以便進入保護模式
使用ljmp指令跳至PE_CODE32程式碼
使用lldt指令將LDT的segment selector載入至LDTR (Local Descriptor Table Register)，並跳至SegSelectorLDTCode32 segment selector執行LDT的程式碼。

32位元保護模式程式碼 (LABEL_PE_CODE32)利用Video segment selector將"Welcome to Protect mode in GDT."顯示在螢幕上，而LABEL_PE_LDT_CODE32則將"Welcome to Protect mode in LDT."顯示在螢幕上，用以驗證程式運作之正確性。

pm.h標頭檔

/* pm.h
*
* Adrian Huang (adrianhuang0701@gmail.com)
*/
.macro SEG_DESC Base, Limit, Attr
   .2byte (\Limit & 0xFFFF)
  .2byte (\Base & 0xFFFF)
  .byte  ((\Base >> 16) & 0xFF)
  .2byte ((\Attr & 0xF0FF) | ((\Limit >> 8) & 0x0F00))
  .byte  ((\Base >> 24) & 0xFF)
.endm

.macro InitSegDescriptor OFFSET GDT_SEG_ADDR
  xor     %ax, %ax
  mov     %cs, %ax
  shl     $4, %eax
  addl    $(\OFFSET), %eax
  movw     %ax, (\GDT_SEG_ADDR + 2)
  shr     $16, %eax
  movb     %al, (\GDT_SEG_ADDR + 4) 
  movb     %ah, (\GDT_SEG_ADDR + 7) 

.endm

.set DESC_ATTR_TYPE_LDT,         0x82       /* LDT Segment         */
.set DESC_ATTR_TYPE_CD_ER,         0x9A     /* Code segment with Execute/Read */
.set DESC_ATTR_TYPE_CD_E,         0x98     /* Code segment with Execute Only */
.set DESC_ATTR_TYPE_CD_RW,         0x92    /* Data segment with R/W         */
.set DESC_ATTR_D,                 0x4000     /* 32-bit segment                 */

/* Selector Attribute */
.set SA_TIL,     0x4
.set SA_RPL0,     0x0
.set SA_RPL1,     0x1
.set SA_RPL2,     0x2
.set SA_RPL3,     0x3

編譯程式碼
請參照此篇的Makefile程式碼

其編譯訊息如下所示:

adrian@adrian-desktop:~/working/build_os/my_ex/04day/blog/pe-multi-seg-ldt$ make clean all
rm -f boot_loader.o os.o boot_loader.bin  
gcc -c boot_loader.S
gcc -c os.S
ld -Ttext=0x7C00 -s boot_loader.o -o boot_loader.bin --oformat binary
ld -Ttext=0x0 -s os.o -o os.bin --oformat binary
ld: warning: cannot find entry symbol _start; defaulting to 0000000000000000
cat os.bin >> boot_loader.bin
adrian@adrian-desktop:~/working/build_os/my_ex/04day/blog/pe-multi-seg-ldt$

[打造簡易作業系統 - 以GNU Assembler組合語言撰寫] (四) 由16位元真實模式 (Real Mode) 進入32位元保護模式 (Protect Mode)

2010-09-29T19:02:00.011+08:00

前三篇文章所展示的程式碼都是CPU執行於真實模式 (Real Mode)。然而，一般作業系統運行於保護模式 (Protect Mode)，其記憶體定址最高可至4GB (32位元)。故本文先介紹real mode與protect mode記憶體定址的方式。

Real mode與Protect mode記憶體定址介紹
Figure 1展示real mode記憶體定址方式，其觀念在於將邏輯位址(Logical Address)的區段(Segment)位址向左位移4個位元，再將其所得的位址加上位移值，如此便能轉換成線性位址 (Linear Address)。至於，邏輯位址該如何表示呢? 其表示法為"Address of Segment:Offset"
，例如: CS:IP、SS:SP、DS:SI和ES:DI，詳情請參考x86 Assembly Language。Figure 1描述一個簡單邏輯位址轉換線性位址的例子，因此不再贅述。

Figure 1. Memory Segmentation in Real Mode

Figure 2展示保護模式記憶體定址方式，其觀念在於將區段 (Segment)看成區段選擇器 (Segment Selector)，用此選擇器索引出對應的Segment Descriptor，如此便能索引32位元的基底位址 (32-bit base address)，然後再加上位移植，便能轉換成線性位址。

Figure 2. Memory Segment in Protect Mode

保護模式相關課題之介紹
此段落將著重介紹保護模式相關課題之介紹，包含介紹GDT/LDT (GDTR/LDTR)、Segment Descriptor、Segment Selector、和Memory Management Register

Global and Local Descriptor Table (GDT and LDT)
當CPU運行於保護模式時，所有的記憶體存取都必須經由GDT或LDT，此表格 (GDT or LDT)存放最小單元便是Segment Descriptor。每一個Segment Descriptor都有對應的segment selector，用以索引出對應的Segment Descriptor。

GDTR and LDTR (GDT Register and LDT Register)
GDTR與LDTR用以儲存GDT與LDT的起始位置，此設定必須在進入保護模式完成設定。Figure 3展示GDTR與LDTR格式，其中GDTR包含32位元的基底位址與16位元的長度限制。而LDTR多增加了16位元的segment selector。

Figure 3. Memory Management Register

Segment Descriptor
Segment Descriptor為Descriptor Table組成的基本元素，其長度為8位元組。如Figure 4所示，可分為三大類: 1. 32位元的基底位址 (Base Address), 2. 20位元的區段限制 (Segment Limit), 3. 區段屬性。細節請參考Intel 64 and IA-32 Architectures. Software Developer's Manual. Volume 3A

Figure 4. Segment Descriptor [2]

Segment Selector
Figure 5展示Segment Selector示意圖，其目的用來索引對應的Segment Descriptor。因Descriptor Index有13個位元，故Descriptor個數最大可至8192。

Figure 5. Segment Selector

Boot Loader程式碼

/* boot_loader.S
*
* Copyright (C) 2010 Adrian Huang (adrianhuang0701@gmail.com)
*
* This code is intended to simulate a simplified boot loader. This boot
* loader loads 3 sectors into the physical memory and jumps the entry
* point of OS.
*
*/

.code16
.text

.set     BOOT_SEG,     0x07C0    /* starting code segment (CS) of boot loader */
.set     OS_SEG,       0x0900    /* code segment address of OS entry point */
.set     OS_OFFSET,    0x0000    /* the offset address of OS entry point */

.global _start
_start:
  # FAT12 file system format
 jmp       start_prog         # jmp instruction

.byte     0x90
.ascii    "ADRIAN  "         # OEM name (8 bytes)
.word     512                # Bytes per sector
.byte     1                  # Sector per cluster
.word     1                  # Reserved sector count: should be 1 for FAT12
.byte     2                  # Number of file allocation tables.
.word     224                # Maximum number of root directory entries.
.word     2880               # Total sectors
.byte     0xf0               # Media descriptor:
.word     9                  # Sectors per File Allocation Table
.word     18                 # Sectors per track
.word     2                  # Number of heads
.long     0                  # Count of hidden sectors
.long     0                  # Total sectors
.byte     0                  # Physical driver number
.byte     0                  # Reserved
.byte     0x29               # Extended boot signature
.long     0x12345678         # Serial Number
.ascii    "HELLO-OS   "      # Volume Label
.ascii    "FAT12   "         # FAT file system type
.fill     18, 1, 0           # fill 18 characters with zero

start_prog:
# initialize the register with cs register
movw    %cs, %ax
movw    %ax, %ds
movw    %ax, %es
movw    %ax, %ss
xorw    %sp, %sp

cld                     # clear direction flag
sti                     # set interrupt flag

# The following code is loaded three sectors (2-4th sectors from boot.bin)
# into the physical memory 0x8000-0x85FF.
movw    $OS_SEG,     %ax
mov     %ax,         %es  # ES:BX-> destination buffer address pointer
movw    $OS_OFFSET,  %bx
movb    $2,          %cl  # sector


cont:
movb     $0x02, %ah  # Read sectors from drive
movb     $0x1,  %al  # Sectors to read count
movb     $0x0,  %ch  # track
movb     $0x0,  %dh  # head
movb     $0,    %dl  # drive

int      $0x13       # trigger a interrupt 0x13 service
jc       fail        # the clear flag is set if the operation is failed

mov      %es,   %ax
addw     $0x20, %ax  # move to the next sector
movw     %ax,   %es  # move to the next sector
incb     %cl

cmpb     $3, %cl     # has finished reading 3 sectors?
jbe      cont        # continue to read the sector

jmp      os_entry    # jump to OS entry point

fail:
movw     $err_msg, %si
fail_loop:
lodsb
andb     %al, %al
jz       end
movb     $0x0e, %ah
int      $0x10
jmp      fail_loop


os_entry:
ljmp $OS_SEG, $OS_OFFSET  # jump to os context

end:
 hlt
 jmp end

err_msg:
.ascii "Reading sectors operation is failed!"
.byte     0

.org 0x1FE, 0x41 # fill the rest of characters with zero until the 254th character

 # Boot sector signature
.byte     0x55
.byte     0xaa

作業系統程式碼
此作業系統程式碼運行於32位元保護模式，一開始定義三個Segment Descriptor (NULL, CODE32與VIDEO)，其中VIDEO的基底位址為0xB8000，詳情請參考Printing to Screen。接著定義GDT的長度、定義Code32與VIDEO的segment selector、定義GDTPtr。

16位元real mode程式碼 (os_main)中，執行若干任務如下所述:

設定Code32的基底位址為PE_CODE32的起始位址
設定GDTPtr的基底位址為GDT的起始位址(也就是GDT_DESC_NULL)
開啟A20線路 (A20 Line)
將GDT的起始位址載入至GDTR暫存器
設定cr0暫存器的bit 0以便進入保護模式
使用ljmp指令跳至PE_CODE32程式碼

32位元保護模式程式碼 (PE_CODE32)利用Video segment selector將'H'字元顯示在螢幕，用以驗證程式運作之正確性。

/* os.S
*
* Adrian Huang (adrianhuang0701@gmail.com)
*
* This code is OS context for protected-mode.
*
*/
#include "pm.h"

.code16
.text
jmp os_main

# Segment descritors for GDT
GDT_DESC_NULL: SEG_DESC      0, 0, 0
GDT_DESC_CODE32: SEG_DESC    0, (PECode32Len - 1), (DESC_ATTR_TYPE_CD_ER | DESC_ATTR_D)
GDT_DESC_VIDEO: SEG_DESC     0xB8000, 0xFFFF, (DESC_ATTR_TYPE_CD_RW)

# The length of GDT
.set GdtLen, (. - GDT_DESC_NULL)

# Segment selectors for code segment and video output
.set SegSelectorCode32, (GDT_DESC_CODE32 - GDT_DESC_NULL)
.set SegSelectorVideo,  (GDT_DESC_VIDEO - GDT_DESC_NULL)

# GDTR pointer
GDTPtr:
.2byte (GdtLen - 1)     # Limit field
.4byte 0                 # base field

# real-mode OS code
os_main:
mov %cs, %ax
mov %ax, %ds
mov %ax, %ss
mov %ax, %es


/* Set gdt for code segment */
InitSegDescriptor PE_CODE32, GDT_DESC_CODE32

/* Set GDTR */
xor     %ax, %ax
mov     %cs, %ax
shl     $4, %eax
addl    $GDT_DESC_NULL, %eax
movl     %eax, (GDTPtr + 2)        

/* Enable A20 line */
xor     %ax,   %ax
in      $0x92, %al
or      $2,    %al
out     %al,   $0x92

cli

/* Load the GDT base address and limit from memory into the GDTR register */
lgdt     GDTPtr

/* Enable protect mode */
movl     %cr0, %eax
orl      $1,   %eax
movl     %eax, %cr0

/* Jump to protected-mode OS code */
ljmp     $SegSelectorCode32, $0


# protected-mode OS code
PE_CODE32:
.code32
/* Load Video segment selector */
mov     $(SegSelectorVideo), %ax
mov     %ax, %gs

/* Output the data */
movl    $((80 * 10 + 0) * 2), %edi
movb    $0xC, %ah
movb    $'H', %al
mov     %ax, %gs:(%edi)

jmp .

.set PECode32Len, (. - PE_CODE32)

os_msg:
.ascii "Welcome to OS context!"
.byte     0

.org    0x200, 0x41 # fill characters with 'A'. Sector 2

pm.h標頭檔

/* pm.h
*
* Adrian Huang (adrianhuang0701@gmail.com)
*/


.macro SEG_DESC Base, Limit, Attr
.2byte (\Limit & 0xFFFF)
.2byte (\Base & 0xFFFF)
.byte  ((\Base >> 16) & 0xFF)
.2byte ((\Attr & 0xF0FF) | ((\Limit >> 8) & 0x0F00))
.byte  ((\Base >> 24) & 0xFF)
.endm

.macro InitSegDescriptor OFFSET GDT_SEG_ADDR
xor     %ax, %ax
mov     %cs, %ax
shl     $4, %eax
addl    $(\OFFSET), %eax
movw    %ax, (\GDT_SEG_ADDR + 2)
shr     $16, %eax
movb    %al, (\GDT_SEG_ADDR + 4)
movb    %ah, (\GDT_SEG_ADDR + 7)

.endm

.set DESC_ATTR_TYPE_LDT,         0x82     /* LDT Segment                    */
.set DESC_ATTR_TYPE_CD_ER,       0x9A     /* Code segment with Execute/Read */
.set DESC_ATTR_TYPE_CD_E,        0x98     /* Code segment with Execute Only */
.set DESC_ATTR_TYPE_CD_RW,       0x92     /* Data segment with R/W          */
.set DESC_ATTR_D,                0x4000   /* 32-bit segment                 */

/* Selector Attribute */
.set SA_TIL,      0x4
.set SA_RPL0,     0x0
.set SA_RPL1,     0x1
.set SA_RPL2,     0x2
.set SA_RPL3,     0x3

編譯程式碼
下圖為編譯的Makefile。

LD=ld
CC=gcc

all: boot_loader.bin

boot_loader.bin: boot_loader.o os.o
${LD} -Ttext=0x7C00 -s $< -o $@ --oformat binary
${LD} -Ttext=0x0 -s os.o -o os.bin --oformat binary
cat os.bin >> $@

boot_loader.o:
${CC} -c boot_loader.S

os.o:
${CC} -c os.S

clean:
rm -f boot_loader.o os.o os.bin boot_loader.bin

其編譯訊息如下所示:

adrian@adrian-desktop:~/working/build_os/my_ex/04day/pe-orig-makefile$ make all
gcc -c boot_loader.S
gcc -c os.S
ld -Ttext=0x7C00 -s boot_loader.o -o boot_loader.bin --oformat binary
ld -Ttext=0x0 -s os.o -o os.bin --oformat binary
ld: warning: cannot find entry symbol _start; defaulting to 0000000000000000
cat os.bin >> boot_loader.bin

[打造簡易作業系統 - 以GNU Assembler組合語言撰寫] (三) Boot Loader + 作業系統載入實例 (CF Card)

2010-08-31T18:58:00.005+08:00

上篇說明如何撰寫小型Boot Loader將作業系統載入至記憶體並執行該作業系統程式碼，並利用qemu實現。為了更真實性，本篇將boot loader及作業系統安裝在CF card並利用CF card開機，用以證明該boot loader及作業系統可以正確地在實體機器上運行。

將DL暫存器更改為0x80
由於上篇是使用軟碟機開機，因此在使用BIOS中斷服務0x13時 (AH=02 Read Sectors from Driver)，需將DL暫存器設定為0(0代表軟碟機0，1代表軟碟機1)，但因為現在要從硬碟讀取，所以需將DL設定為0x80，即底下範例程式紅色部份。

Boot Loader範例程式 (以FAT32為範例)

/* boot_loader.S
*
* Copyright (C) 2010 Adrian Huang (adrianhuang0701@gmail.com)
*
* This code is intended to simulate a simplified boot loader. This boot
* loader loads 3 sectors into the physical memory and jumps the entry
* point of OS.
*
*/

BOOT_SEG     = 0x07C0    /* starting code segment (CS) of boot loader */
OS_SEG       = 0x0800    /* code segment address of OS entry point */
OS_OFFSET    = 0x0000    /* the offset address of OS entry point */

 .code16

 .section .text

 .global _start
_start:
 # FAT12 file system format
 ljmp     $BOOT_SEG, $start_prog         # jmp instruction

 .byte     0x90
 .ascii    "ADRIAN  "        # OEM name (8 bytes)
 .word     512               # Bytes per sector
 .byte     1                 # Sector per cluster
 .word     32                # Reserved sector count: should be 32 for FAT32
 .byte     2                 # Number of file allocation tables. 
 .word     0                 # Maximum number of root directory entries. 0 for FAT32
 .word     0                 # Total sectors
 .byte     0xf8              # Media descriptor: fix disk
 .word     9                 # Sectors per File Allocation Table
 .word     18                # Sectors per track
 .word     2                 # Number of heads
 .long     0                 # Count of hidden sectors
 .long     2030112           # Total sectors
 .byte     0                 # Physical driver number
 .byte     0                 # Reserved
 .byte     0x29              # Extended boot signature
 .long     0x12345678        # Serial Number
 .ascii    "HELLO-OS   "     # Volume Label
 .ascii    "FAT12   "        # FAT file system type
 .fill     18, 1, 0          # fill 18 characters with zero

start_prog:
 # initialize the register with cs register
 movw    %cs, %ax
 movw    %ax, %ds
 movw    %ax, %es
 movw    %ax, %ss
 xorw    %sp, %sp

 cld                     # clear direction flag
 sti                     # set interrupt flag

 # The following code is loaded three sectors (2-4th sectors from boot.bin)
 # into the physical memory 0x8000-0x85FF.
 movw    $OS_SEG,     %ax
 mov     %ax,         %es  # ES:BX-> destination buffer address pointer
 movb    $2,          %cl  # sector


cont:
 movw     $0,    %bx
 movb     $0x02, %ah  # Read sectors from drive
 movb     $0x1,  %al  # Sectors to read count
 movb     $0x0,  %ch  # track
 movb     $0x0,  %dh  # head
 movb     $0x80, %dl  # drive

 int      $0x13        # trigger a interrupt 0x13 service
 jc       fail         # the clear flag is set if the operation is failed

 mov      %es, %ax  
 addw     $0x20, %ax     # move to the next sector
 movw     %ax, %es       # move to the next sector
 incb     %cl
 cmpb     $3, %cl        # has finished reading 3 sectors?
 jbe      cont           # continue to read the sector

 jmp  os_entry           # jump to OS entry point

fail:
 movw     $err_msg, %si
fail_loop:
 lodsb 
 andb     %al, %al
 jz       end
 movb     $0x0e, %ah
 int      $0x10    
 jmp      fail_loop


os_entry:
 ljmp $OS_SEG, $OS_OFFSET  # jump to os context

end:
 hlt

err_msg:
 .ascii "Reading sectors operation is failed!"
 .byte     0

 .org 0x1FE, 0x41 # fill the rest of characters with zero until the 254th character

 # Boot sector signature
 .byte     0x55
 .byte     0xaa

作業系統程式碼與編譯
請參照這篇的"作業系統程式碼"與"編譯程式碼"。

安裝boot_loader.bin安裝至CF card

adrian@adrian-mem1:~/img$ sudo dd if=./boot_loader.bin of=/dev/sda

測試結果
將該系統重開並選擇CF Card開機，其畫面如下:

【Reference】
1.30天打造OS！作業系統自作入門
2. Jserv's Blog
3. X86 開機流程小記
4. Linux assemblers: A comparison of GAS and NASM
5. linux-source-2.6.31

Google將推出Chrome作業系統的平板電腦

2010-08-20T10:43:00.001+08:00

Google將與HTC合作，以Google Chrome作業系統開發平板電腦，預計今年11月26發表。

詳見: First Chrome OS Tablet Set for Black Friday Debut

文中還提及為什麼不使用Android的原因。

Google大神開始對Linux Kernel Source貢獻了

2010-08-13T10:57:00.003+08:00

Linux 2.6.35有Google大神的程式碼了!! (跪拜0rz......)
其主要提升網路封包處理速度
詳見: Linux 2.6.35 Includes Speedy Google Code, Less Bloat

[打造簡易作業系統 - 以GNU Assembler組合語言撰寫] (二) Boot Loader + 作業系統載入實例 (QEMU)

2010-08-11T10:00:00.017+08:00

繼上篇說明如何撰寫開機Hello World，本篇文章說明如何撰寫簡單的Boot Loader跟一個只會印出訊息的作業系統。

小型Boot Loader設計概念
筆者所撰寫的小型Boot Loader於BIOS開機成功後，會被載入至實體記憶體位址0x7C00並跳至此位址執行boot loader的程式碼，此boot loader程式碼會將作業系統程式碼 (僅三個磁區)，載入實體記憶體位址0x8000並跳至此位址執行作業系統的程式碼，然而此作業系統別無功能，僅會印出簡單的訊息。如此便能模擬一般boot loader載入作業系統的程序。

圖一為筆者所編譯出來的plain binary file，此程式碼僅有四個磁區 (共2048 bytes)，0x0-0x1ff為boot loader磁區，0x200-0x7ff為作業系統的三個磁區，雖然，真正的作業系統程式碼在0x200-0x3ff，其它兩個磁區僅填入字元'B'與'C'，但筆者還是把這三個磁區稱為作業系統程式碼，因為boot loader會將這三個磁區載入實體記憶體位址0x8000。

圖一、Boot + OS Binary Image Layout

圖二為boot loader將作業系統載入實體記憶體位址示意圖，至於為什麼會選擇0x8000開始存放作業系統程式碼，其原因是x86系統規範位址0x7E00-0x7FFFF為conventional memory，因此筆者就挑0x8000來存放程式碼。

圖二、Boot Loader + OS Physical Memory Layout

Boot Loader程式碼

下圖為Boot Loader程式碼，其運作原理在此稍作描述。首先，boot_loader透過.byte、.word、.long跟.ascii等指令將此磁區描述為一個FAT12檔案系統。接著，利用中斷服務編號0x13將作業系統的三個磁區讀入0x8000實體記憶體位址。如果讀取失敗的話，則利用中斷服務編號0x010印出錯誤訊息。特別要提出的是，程式碼使用兩次遠程跳躍 (Far Dump)，其原型ljmp code_segment_address, relative_address，例如: ljmp $BOOT_SEG, $start_prog代表code segment設定為0x07C0加上start_prog標籤的位址，即0x7C00+start_prog位址，此為Intel x86 CPU memory segmentation機制。透過此設定，boot loader程式碼便能正確地在0x7C00位址執行。另一個ljmp，ljmp $OS_SEG, $OS_OFFSET，因為boot loader將作業系統程式碼放在0x8000實體記憶體位址，因此code segment必須設為0x0800，以便讓作業系統程式碼可以正確地執行。

/* boot_loader.S
*
* Copyright (C) 2010 Adrian Huang (adrianhuang0701@gmail.com)
*
* This code is intended to simulate a simplified boot loader. This boot
* loader loads 3 sectors into the physical memory and jumps the entry
* point of OS.
*
*/

BOOT_SEG     = 0x07C0       /* starting code segment (CS) of boot loader */
OS_SEG       = 0x0800       /* code segment address of OS entry point */
OS_OFFSET    = 0x0000       /* the offset address of OS entry point */

.code16

.section .text

.global _start
_start:
# FAT12 file system format
ljmp     $BOOT_SEG, $start_prog   # jmp instruction

.byte   0x90
.ascii  "ADRIAN  "                # OEM name (8 bytes)
.word   512                       # Bytes per sector
.byte   1                         # Sector per cluster
.word   1                         # Reserved sector count: should be 1 for FAT12
.byte   2                         # Number of file allocation tables.
.word   224                       # Maximum number of root directory entries.
.word   2880                      # Total sectors
.byte   0xf0                      # Media descriptor
.word   9                         # Sectors per File Allocation Table
.word   18                        # Sectors per track
.word   2                         # Number of heads
.long   0                         # Count of hidden sectors
.long   2880                      # Total sectors: 18 (sectors per track) * 2 (heads) * 80 (sectors) = 2880
.byte   0                         # Physical driver number
.byte   0                         # Reserved
.byte   0x29                      # Extended boot signature
.long   0x12345678                # Serial Number
.ascii  "HELLO-OS   "             # Volume Label
.ascii  "FAT12   "                # FAT file system type
.fill   18, 1, 0                  # fill 18 characters with zero

start_prog:
# initialize the register with cs register
movw    %cs, %ax
movw    %ax, %ds
movw    %ax, %es
movw    %ax, %ss
xorw    %sp, %sp

cld                     # clear direction flag
sti                     # set interrupt flag

# The following code is loaded three sectors (2-4th sectors from boot.bin)
# into the physical memory 0x8000-0x85FF.
movw    $OS_SEG,     %ax
mov     %ax,         %es  # ES:BX-> destination buffer address pointer
movb    $2,          %cl  # sector


cont:
movw     $0,    %bx
movb     $0x02, %ah     # Read sectors from drive
movb     $0x1,  %al     # Sectors to read count
movb     $0x0,  %ch     # track
movb     $0x0,  %dh     # head
movb     $0,    %dl     # drive

int      $0x13          # trigger a interrupt 0x13 service
jc       fail           # the clear flag is set if the operation is failed

mov     %es, %ax
addw    $0x20, %ax      # move to the next sector
movw    %ax, %es        # move to the next sector
incb    %cl
cmpb    $3, %cl         # has finished reading 3 sectors?
jbe     cont            # continue to read the sector

jmp  os_entry           # jump to OS entry point

fail:
movw    $err_msg, %si
fail_loop:
lodsb
andb    %al, %al
jz      end
movb    $0x0e, %ah
int     $0x10
jmp     fail_loop


os_entry:
ljmp $OS_SEG, $OS_OFFSET  # jump to os context

end:
hlt

err_msg:
.ascii "Reading sectors operation is failed!"
.byte     0

.org 0x1FE, 0x41 # fill the rest of characters with zero until the 254th character

# Boot sector signature
.byte     0x55
.byte     0xaa

作業系統程式碼

此段程式碼僅將訊息輸出至螢幕上，所以不再贅述。

/* os.S *  
 * Copyright (C) 2010 Adrian Huang (adrianhuang0701@gmail.com)
 *
 * This code is OS context. 
 *
 */
    .code16
    .section .text
    .global main

main:
    movw    %cs, %ax
    movw    %ax, %ds
    movw    %ax, %es
    movw    %ax, %ss
    xorw    %sp, %sp
    
    cld                     # clear direction flag 
    sti                     # set interrupt flag

    movw  $os_msg, %si
 
load_msg:
    lodsb
    andb %al, %al
    jz      os_fin
    movb $0x0e, %ah
    int  $0x10
    jmp  load_msg

os_fin:
    hlt
    jmp  os_fin

os_msg:
    .ascii "Welcome to OS context!"
    .byte     0    

    .org    0x200, 0x41 # fill characters with 'A'. Sector 1
    .org    0x400, 0x42 # fill characters with 'B'. Sector 2
    .org    0x600, 0x43 # fill characters with 'C'. Sector 3

編譯程式碼
下圖為編譯的Makefile。

LD=ldCC=gcc

all: boot_loader.bin

boot_loader.bin: boot_loader.o os.o
    ${LD} -Ttext=0x0 -s $< -o $@ --oformat binary
    ${LD} -Ttext=0x0 -s os.o -o os.bin --oformat binary
    cat os.bin >> $@

boot_loader.o:
    ${CC} -c boot_loader.S

os.o:
    ${CC} -c os.S
    

clean:
    rm -f boot_loader.o boot_loader.bin os.o

其編譯訊息如下所示:

adrian@adrian-desktop:~/working/build_os/my_ex/boot_loader$ make clean allrm -f boot_loader.o boot_loader.bin os.o
gcc -c boot_loader.S
gcc -c os.S
ld -Ttext=0x0 -s boot_loader.o -o boot_loader.bin --oformat binary
ld -Ttext=0x0 -s os.o -o os.bin --oformat binary
ld: warning: cannot find entry symbol _start; defaulting to 0000000000000000
cat os.bin >> boot_loader.bin
adrian@adrian-desktop:~/working/build_os/my_ex/boot_loader$

測試結果

為了驗證作業系統的程式碼正確地載入實體記憶體位址0x8000，筆者利用xxd工具將boot_loader.bin dump出來，下圖為其結果。紅色框框為作業系統程式碼的十六進制碼。

下圖中，筆者利用qemu提供的xp工具將0x8000-0x8010的內容dump出來，用以跟上圖0x200-0x210比對，比較上、下這兩張圖，可以證明作業系統程式碼正確地被載入至0x8000。

【Reference】

1.30天打造OS！作業系統自作入門

2. Jserv's Blog

3. X86 開機流程小記

4. Linux assemblers: A comparison of GAS and NASM

5. linux-source-2.6.31

[打造簡易作業系統 - 以GNU Assembler組合語言撰寫] (一) 開機Hello World實例

2010-08-03T16:39:00.030+08:00

小弟最近想嘗試利用GAS(GNU Assembler)組合語言撰寫非常小型的作業系統，本篇文章說明如何利用GAS組合語言在終端機上印出Hello World.

簡介x86 CPU開機流程
x86 CPU開機後，首要之事會先跳至0xFFFF0執行BIOS ROM的程式，當BIOS測試程序通過後，BIOS便會把執行權交給下一個程式 (boot loader或一支小程式)，BIOS會將該程式
(通常為一個磁區[Sector]大小，即512 bytes)載入記憶體0x7C00位置，並跳至0x7C00執行該段程式碼。該磁區被稱為MBR，BIOS會檢查該磁區最後兩個位完組必須為0x55AA，否則該磁區該被視為無效的MBR。

所以，首要之事就是利用GAS撰寫一支大小為512位元組的二進位檔 (Binary File)，此檔需具備底下功能:

檔案系統，如: FAT12, FAT16, FAT32, NTFS等等。
利用BIOS中斷號碼0x10將資料寫至螢幕。
在最後兩個位元組寫入0x55AA以便通過BIOS識別。

底下為原始碼:

    .code16



    .section .text

    .global main

main:

    # FAT12 file system format

    jmp       start_prog       # jmp instruction

    .byte     0x90

    .ascii    "ADRIAN  "       # OEM name (8 bytes)

    .word     512              # Bytes per sector

    .byte     1                # Sector per cluster

    .word     1                # Reserved sector count: should be 1 for FAT12

    .byte     2                # Number of file allocation tables.

    .word     224              # Maximum number of root directory entries.

    .word     2880             # Total sectors

    .byte     0xf0             # Media descriptor:

    .word     9                # Sectors per File Allocation Table

    .word     18               # Sectors per track

    .word     2                # Number of heads

    .long     0                # Count of hidden sectors

    .long     2880             # Total sectors: 18 (sectors per track) * 2 (heads) * 80 (sectors) = 2880

    .byte     0                # Physical driver number

    .byte     0                # Reserved

    .byte     0x29             # Extended boot signature

    .long     0x12345678       # Serial Number

    .ascii    "HELLO-OS   "    # Volume Label

    .ascii    "FAT12   "       # FAT file system type

    .fill     18, 1, 0         # fill 18 characters with zero



start_prog:

    movw    $0, %ax            # Initialize register

    movw    %ax, %ss

    movw    %ax, %ds

    movw    %ax, %es



    movw    $msg, %si          # move the address of msg to SI





loop:

    movb    $0xe, %ah

    movb    (%si), %al        # move the first character of msg to AL register

    cmpb    $0, %al

    je      fin

    int     $0x10             # write the specific character to console

    addw    $1, %si

    jmp     loop



fin:

# do nothing



msg:

    .ascii "Hello, World! This is Adrian Huang."

    .byte   0



    .org    0x1FE, 0x00       # fill the rest of characters with zero until the 254th character



# Boot sector signature

    .byte     0x55

    .byte     0xaa

Compile and Link
以"gcc -c"將.S組合語言轉為成object file

adrian@adrian-desktop:~/working/build_os/my_ex/02day/helloos4$ ls

hello.S

adrian@adrian-desktop:~/working/build_os/my_ex/02day/helloos4$ gcc -c hello.S

adrian@adrian-desktop:~/working/build_os/my_ex/02day/helloos4$ file hello.o

hello.o: ELF 64-bit LSB relocatable, x86-64, version 1 (SYSV), not stripped

adrian@adrian-desktop:~/working/build_os/my_ex/02day/helloos4$

再經由ld連結器將此object轉換成plain binary file

$ ld -Ttext=0x7C00 hello.o -o hello.bin --oformat binary

$ file hello.bin

hello.bin: DOS floppy 1440k, x86 hard disk boot sector

利用xxd工具觀察helo.bin格式 (以十六進制)

adrian@adrian-desktop:~/working/build_os/my_ex/02day/helloos4$ xxd hello.bin

0000000: eb4e 9041 4452 4941 4e20 2000 0201 0100  .N.ADRIAN  .....

0000010: 02e0 0040 0bf0 0900 1200 0200 0000 0000  ...@............

0000020: 400b 0000 0000 2978 5634 1248 454c 4c4f  @.....)xV4.HELLO

0000030: 2d4f 5320 2020 4641 5431 3220 2020 0000  -OS   FAT12   ..

0000040: 0000 0000 0000 0000 0000 0000 0000 0000  ................

0000050: b800 008e d08e d88e c0be 6b7c b40e 8a04  ..........k|....

0000060: 3c00 7407 cd10 83c6 01eb f148 656c 6c6f  <.t........Hello

0000070: 2c20 576f 726c 6421 2054 6869 7320 6973  , World! This is

0000080: 2041 6472 6961 6e20 4875 616e 672e 0000   Adrian Huang...

0000090: 0000 0000 0000 0000 0000 0000 0000 0000  ................

00000a0: 0000 0000 0000 0000 0000 0000 0000 0000  ................

00000b0: 0000 0000 0000 0000 0000 0000 0000 0000  ................

00000c0: 0000 0000 0000 0000 0000 0000 0000 0000  ................

00000d0: 0000 0000 0000 0000 0000 0000 0000 0000  ................

00000e0: 0000 0000 0000 0000 0000 0000 0000 0000  ................

00000f0: 0000 0000 0000 0000 0000 0000 0000 0000  ................

0000100: 0000 0000 0000 0000 0000 0000 0000 0000  ................

0000110: 0000 0000 0000 0000 0000 0000 0000 0000  ................

0000120: 0000 0000 0000 0000 0000 0000 0000 0000  ................

0000130: 0000 0000 0000 0000 0000 0000 0000 0000  ................

0000140: 0000 0000 0000 0000 0000 0000 0000 0000  ................

0000150: 0000 0000 0000 0000 0000 0000 0000 0000  ................

0000160: 0000 0000 0000 0000 0000 0000 0000 0000  ................

0000170: 0000 0000 0000 0000 0000 0000 0000 0000  ................

0000180: 0000 0000 0000 0000 0000 0000 0000 0000  ................

0000190: 0000 0000 0000 0000 0000 0000 0000 0000  ................

00001a0: 0000 0000 0000 0000 0000 0000 0000 0000  ................

00001b0: 0000 0000 0000 0000 0000 0000 0000 0000  ................

00001c0: 0000 0000 0000 0000 0000 0000 0000 0000  ................

00001d0: 0000 0000 0000 0000 0000 0000 0000 0000  ................

00001e0: 0000 0000 0000 0000 0000 0000 0000 0000  ................

00001f0: 0000 0000 0000 0000 0000 0000 0000 55aa  ..............U.

接著，使用qemu驗證hello.bin

為了讓此範例更真實，筆者有一台機器備有CF Card，將hello.bin透過dd工具寫進此CF Card最前面的512 bytes, 命令如下:

adrian@adrian-mem1:~/img$ sudo dd if=./hello.bin of=/dev/sda

[sudo] password for adrian:

1+0 records in

1+0 records out

512 bytes (512 B) copied, 0.00124243 s, 412 kB/s

adrian@adrian-mem1:~/img$

將該系統重開並選擇CF Card開機，其畫面如下:

【Reference】
1.30天打造OS！作業系統自作入門
2. Jserv's Blog
3. X86 開機流程小記
4. Linux assemblers: A comparison of GAS and NASM

簡介Linux Block I/O Layer (三) - I/O Path

2010-03-19T11:25:00.002+08:00

此系列文章最後講解Block I/O Layer I/O Path運作原理。圖一為I/O Path簡易圖，檔案系統核心經由submit_bio函式將該bio交給Block I/O Layer的generic_make_request和__generic_make_request函式，緊接著呼叫__make_request_fn callback函式 (對應至__make_request())，此函式主要目的用來檢查此bio是否可以跟尚未處理的request結構的bio成員結合在一起 (merge)，如果不行的話，則另外配置一個新的request結構並將其bio安插至該reqeust結構，再將該request交給I/O Scheduler，最後Block I/O Layer經由request_fn() callback function將待處理的request交給SCSI子系統。

圖一、Block I/O Layer之I/O Path簡易圖

下圖二為Linux Block I/O Layer核心I/O Path示意圖，此圖以ReiserFS為例，此圖對每個函式有詳細的解釋，所以在此不再解釋，請參照圖二。

圖二、Block I/O Layer之I/O Path

【Reference】
1. Linux Device Driver, third edition
2. Linux Kernel Source 2.6.31
3. Request-based Device-mapper multipath and Dynamic load balancing
4. Understanding the Linux Kernel, Third Edition - Chapter 14. Block Device Drivers

簡介Linux Block I/O Layer (二) - 探討BIO (Block I/O) and Request 結構

2010-03-18T13:52:00.005+08:00

上一篇文章簡單介紹page, bio和request結構的定位，本篇文章著重於探討bio與request結構是如何串起來的。底下將分別介紹reqeust queue、request、bio與bio_vec等資料結構。首先，下圖展示這四個資料結構的關係。

Request Queue
Request Queue用來將待處理的request串成一個雙向的鏈結串列，此結構 (struct request_queue)定義在include/linux/blkdev.h檔頭檔。

Request
一個request資料結構，即表示一次block I/O傳輸請求。結構裡的queuelist便是將整個request串起來的成員，bio成員代表該request所欲傳輸block I/O個數，buffer成員代表當前資料傳輸的buffer區塊。request資料結構裡還有許多其它成員，詳見include/linux/blkdev.h標頭檔。

BIO (Block I/O)
當block I/O layer上層 (可參考此篇文章的圖，Ex: 檔案系統或虛擬記憶體子系統)欲傳輸某一區塊時，該層便會產生一個bio結構並交由Block I/O Layer，Block I/O Layer將新請求的bio併入現有的request結構裡 (前提是該request結構裡的bio所欲傳輸的區塊磁區剛好跟新請求的bio所欲傳輸的區塊磁區相近，如此變能發揮更大的傳輸效益)，或者產生一個新的request結構並將此bio併入此request結構，此結構 (struct request_queue)定義在include/linux/bio.h標頭檔。

bio_vec (BIO Vector)
bio結構裡有一個稱為bi_io_vec一維陣列的成員，該陣列成員紀錄欲傳輸的資料緩衝區在記憶體何處。

【Reference】
1. Linux Device Driver, third edition
2. Linux Kernel Source 2.6.31
3. Request-based Device-mapper multipath and Dynamic load balancing
4. Understanding the Linux Kernel, Third Edition - Chapter 14. Block Device Drivers

簡介Linux Block I/O Layer (一) - Page, BIO (Block I/O) and Request 結構意義

2010-03-18T09:26:00.001+08:00

Linux Block I/O Layer主要處理上層檔案系統的請求，進而將該請求往丟至低層的low-level device driver (例如: Linux SCSI Subsystem)，下圖展示出這三層的關係，由圖中可知檔案系統驅動程式主要以page結構來描述所欲存取的資料在哪裡, 接著檔案系統驅動程式將page結構轉換bio (Block I/O)，並經由submit_bio函式將該請求送至Block I/O Layer，該層主要任務便將bio結構轉換成request結構 (往後會有幾篇探討該層運作細節)，並將該request結構丟至low-level device driver，以上是簡單的介紹.

【Reference】
1. Linux Device Driver, third edition
2. Linux Kernel Source 2.6.31
3. Request-based Device-mapper multipath and Dynamic load balancing

C語言malloc之sizeof使用技巧

2010-03-15T11:30:00.003+08:00

C語言程式設計師使用結構指標時，在配置一塊記憶體時通常都會使用下列宣告描述 (粗體字):

struct abc {
     char *ptr;
     int var[20];
     struct abc *next;
};

struct abc *ptr = (struct abc *) malloc(sizeof(struct abc));

另一種寫法可以將程式碼簡化，將sizeof(struct abc)改成sizeof(*ptr)，如下所示:

struct abc *ptr = malloc(sizeof(*ptr));

提供給各位參考.

Linux Kernel: container_of 巨集

2010-01-25T16:39:00.004+08:00

Linux驅動程式裡很常看container_of巨集，其目的為何呢? 假設Linux驅動程式只知道某一結構成員的位址，該驅動程式便可使用container_of巨集，將已知某一結構成員的位址計算出該結構的起始位址，其原型如下:

#define offsetof(TYPE, MEMBER) ((size_t) &((TYPE *)0)->MEMBER)

#define container_of(ptr, type, member) ({ \
const typeof( ((type *)0)->member ) *__mptr = (ptr); \
(type *)( (char *)__mptr - offsetof(type,member) );})

假設有一結構定義如下，且我們只知道phone_num成員的位址，如此便能使用該巨集計算出該結構變數的起始位址:

/* The student structure definition */
typedef struct student {
     char name[16];
     int id;
     char addr[64];
     char phone_num[16];
}STUDENT, *STUDENT_PTR;

該結構記憶體配置圖如下所示:

Figure 1. 結構記憶體配置圖

範例程式碼:

Figure 2. 範例程式碼

以此結構為範例來看containter_of巨集的兩行程式碼:

◎ const typeof( ((type *)0)->member ) *__mptr = (ptr); ==> 得到phone_num的位址 (x+84) ，請參考Figure 1跟Figure 2。
◎ (type *)( (char *)__mptr - offsetof(type,member) ); → (type *)( (char *)__mptr - ((size_t) &((type *)0)->member) ); ==> 其中((size_t) &((type *)0)->member)這段敘述代表以零為起始位址算出member這個成員的相對位址，即為phone_num成員的相對位址，也就是84 (請參考Figure 1)。所以整個敘述變成 (x+84) - 84 = x ，如此便能取得該結構變數的起始位址。

範例程式

Linux Kernel: Lookaside Cache (前瞻快取)

2010-01-22T11:32:00.002+08:00

驅動程式往往根據使用者請求一次又一次地配置相同記憶體大小的物件。為此，Linux核心提供此需求的機制 - Lookaside cache。而此機制稱為Slab Allocator。

以SCSI驅動程式為例，當使用者要讀寫硬碟資料時，會由區塊裝置驅動程式 (Block Device Driver)向SCSI層發出請求，SCSI層將此請求轉換成SCSI command的結構 (struct scsi_cmnd)，為了能快速配置與存取SCSI command，SCSI層驅動程式為每一個SCSI command結構配置lookaside cache。其用法如下:

1. 首先，必須先配置一個快取物件導向，其函式: struct kmem_cache *
kmem_cache_create (const char *name, size_t size, size_t align,
unsigned long flags, void (*ctor)(void *))

    ◎ name: 此快取物件名稱，此名稱會出現在/proc/slabinfo。
    ◎ size: 物件大小。
    ◎ align: 對齊字元數大小，通常為零。
    ◎ flag: 配置物件的方式，詳見include/linux/slab.h。
    ◎ ctor: 建構子函式位址。當核心成功地配置物件後，便會呼叫此函式。

2. 接著，呼叫kmem_cache_alloc，配置每一個物件，其原型: void *kmem_cache_alloc(struct kmem_cache *cachep, gfp_t flags);

    ◎ cachep: kmem_cache_create回傳的位址。
    ◎ flags：詳見kmalloc的flags參數。

3. 釋放記憶體:
void kmem_cache_free(struct kmem_cache *cachep, void *objp)
→ 釋放物件，但並未釋放快取。
void kmem_cache_destroy(struct kmem_cache *cachep) → 釋放快取。

範例 (取自Linux SCSI驅動程式):

【Reference】
1. Linux Device Driver, third edition
2. Linux Kernel Source 2.6.31

Linux Kernel: init, initdata屬性

2010-01-15T16:57:00.003+08:00

在trace Linux核心原始碼很常看到__init和__initdata兩個屬性。其原型如下:

#define __init __section(.init.text) __cold notrace
#define __initdata __section(.init.data)

只要函數被定義__init屬性，代表此函數的所有內容被編譯器放置在.init.text節區。此節區代表該函數只會執行一次，此後就不會再執行，因此執行完該函數，核心會將該函數所佔記憶體空間釋放出來。__init屬性非常適合裝置驅動程式的init_module函數，其範例宣告如下:

static int __init dm_init(void); (from linux-source-2.6.31/drivers/md/dm.c)

利用objdump觀察dm_init函數被放置在哪個節區:

adrian@adrian-laptop:/usr/src/linux-source-2.6.31$ objdump -x drivers/md/built-in.o | grep md_init
00000000 l F .init.text 000000de md_init
00000000 l O .initcall4.init 00000004 __initcall_md_init4

__initdata屬性跟__init屬性的作用大同小異，唯一不同在於前者放置在.init.data節區。

範例:

static int (*_inits[])(void) __initdata = {
     local_init,
     dm_target_init,
     dm_linear_init,
     dm_stripe_init,
     dm_kcopyd_init,
     dm_interface_init,
};

利用objdump觀察_inits變數被放置在哪個節區:

adrian@adrian-laptop:/usr/src/linux-source-2.6.31$ objdump -x drivers/md/built-in.o | grep _inits
00000000 l O .init.data 00000018 _inits

問題來了，釋放記憶體的工作由核心的哪一函數負責呢? 答案是: free_initmem (arch/x86/mm/init.c)

【Reference】
FAQ/InitExitMacros
Linux Kernel Source 2.6.31

An Introduction to Linux Kernel Booting Sequence Part 3

2010-01-15T11:11:00.002+08:00

上篇文章提到go_to_protected_mode函式最後會執行由組合語言所撰寫的函式protected_mode_jump，此函式工作如下:

函式呼叫原型:
protected_mode_jump(boot_params.hdr.code32_start, (u32)&boot_params + (ds() << 4));

其程式碼:

/*
* void protected_mode_jump(u32 entrypoint, u32 bootparams);
*/
GLOBAL(protected_mode_jump)
movl %edx, %esi # Pointer to boot_params table

xorl %ebx, %ebx
movw %cs, %bx
shll $4, %ebx
addl %ebx, 2f
jmp 1f # Short jump to serialize on 386/486
1:

movw $__BOOT_DS, %cx
movw $__BOOT_TSS, %di

### 設定x86之cr0暫存器的PE位元，如此便能進入proctected-mode
movl %cr0, %edx
orb $X86_CR0_PE, %dl # Protected mode
movl %edx, %cr0

# Transition to 32-bit mode
.byte 0x66, 0xea # ljmpl opcode
2: .long in_pm32 # offset
.word __BOOT_CS # segment
ENDPROC(protected_mode_jump)

.code32
.section ".text32","ax"
GLOBAL(in_pm32)
# Set up data segments for flat 32-bit mode
movl %ecx, %ds
movl %ecx, %es
movl %ecx, %fs
movl %ecx, %gs
movl %ecx, %ss
# The 32-bit code sets up its own stack, but this way we do have
# a valid stack if some debugging hack wants to use it.
addl %ebx, %esp

# Set up TR to make Intel VT happy
ltr %di

# Clear registers to allow for future extensions to the
# 32-bit boot protocol
xorl %ecx, %ecx
xorl %edx, %edx
xorl %ebx, %ebx
xorl %ebp, %ebp
xorl %edi, %edi

# Set up LDTR to make Intel VT happy
lldt %cx

## 跳至code32_start的標籤
jmpl *%eax # Jump to the 32-bit entrypoint
ENDPROC(in_pm32)

至於code32_start在哪裡呢? 此標籤定義在arch/x86/boot/header.S，如下所示:

code32_start: # here loaders can put a different
# start address for 32-bit code.
.long 0x100000 # 0x100000 = default for big kernel

也就是說，核心已做完real-mode Linux程式碼該做的事情，並跳至protected-mode Linux程式碼的起始位址 (1MB)，請看下圖:

[Reference]
【The Kernel Boot Process】
【Linux Kernel Source 2.6.31】

An Introduction to Linux Kernel Booting Sequence Part 2

2010-01-12T14:11:00.006+08:00

上篇文章Linux核心被載入記憶體並執行start_of_setup標籤(arch/x86/boot/header.S)，在start_of_setup標籤末段會執行由C語言撰寫的main函式 (arch/x86/boot/main.c)，此函式工作如下所示:

1. 複製開機標頭 (boot header) 至 zero page
2. 設定heap_end變數
3. 偵測記憶體layout
4. 設定鍵盤重複率 (Keyboard Repeat Rate)
5. 查詢MCA (Micro Channel Architecture) 資訊
6. 查詢Intel SpeedStep
7. 設定video模式
8. 進入protected-mode (go_to_protected_mode，arch/x86/boot/pm.c)

其中3-6項，經由BIOS呼叫 (intcall，arch/x86/boot/bioscall.S)，以便向BIOS取到相關的資訊。
main函式最後呼叫go_to_protected_mode函式，以便從real-mode轉換至protected-mode。

在真正進入protected-mode之前，有幾項工作必須先被執行，也就是go_to_protected_mode函式裡所做的事情，如下所示:

1. 設定A20位址線，如此便能存取超過1MB以後的資料 (因為在real-mode，只能存取1MB以下的資料)。

2. 設定idt (interrupt descriptor table)。在real-mode，interrupt vector table的起始位址是從記憶體零的位址開始算起。然而，在protected-mode，interrupt vector table是儲存於CPU的暫存器 (IDTR，Interrupt Descriptor Table Register)，因此轉換至protected-mode之前，必須先設定idt。

3. 設定gdt (global descriptor table)。由於，real-mode與proctected-mode位址轉換 (由邏輯位址 [logical address] 轉換成線性位址 [linear address])，詳見x86_memory_segmentation。因此轉換至protected-mode之前，必須先設定gdt，以便能正確地根據logical address轉換成linear address。

在go_to_protected_mode函式最後會執行由組合語言所撰寫的函式protected_mode_jump，此函式便是設定CPU為protected-mode，細節留到下回做進一步解釋。

【Reference】 The Kernel Boot Process

An Introduction to Linux Kernel Booting Sequence Part 1

2009-12-25T17:31:00.004+08:00

此系列文章將著重於探討Linux x86核心開機過程,
其中, 假設BIOS跟Boot Loader (GRUB, for example) 運行正常, 且Boot Loader已將核心 (/boot/vmlinuz-2.6.31-16-generic) 載入記憶體並跳至載入記憶體之起始位置執行.

Linux核心主要可以分為兩大部份: 1. 執行於CPU之real mode的核心程式碼 2. 執行於CPU之protected mode的核心程式碼. 然而這兩大部份被載入至不同的記憶體區段: 1. real mode核心程式碼載入至0-640KB的某一區間, 2. protected mode核心程式碼載入至1MB記憶體位址. 如下所示:

Figure 1. Linux kernel RAM content after loading the Linux kernel image into RAM

首先第一個被執行的Linux核心檔案為arch/x86/boot/header.S，此檔案由組合語言所撰寫，此檔案前512位元組 (其中有15個位元組為核心標頭) 為早期的核心開機磁區，但現今的boot loader直接跳過此512位元組。緊接著在512位元組之後，即為Linux核心執行的起始點，底下展示此起始點的兩行程式碼 (以Linux核心原始碼版本2.6.31為例)：

.byte 0xeb # short (2-byte) jump
.byte start_of_setup-1f

此兩行代表跳至start_of_setup標籤。".byte 0xeb" (arch/x86/boot/header.S:112)代表two-bytes jmp組合語言指令。".byte start_of_setup-1f" (arch/x86/boot/header.S:113)的"f"代表forward short jump，"start_of_setup-1"代表用"start_of_setup" (arch/x86/boot/header.S:241)標籤起始位址減去"1" (arch/x86/boot/header.S:114)標籤起始位址。

所以上述兩個位元組即代表：以目前的位址向下跳至n個位元組 (即start_of_setup-1)，因此便能正確地跳至start_of_setup標籤。

範例 (以Ubuntu 9.10之2.6.31-16-generic核心為例)

此範例利用hexdump將Linux核心dump出來，並觀看其16進制碼用以對照上述之論述。

adrian@adrian-desktop:/boot$ hexdump vmlinuz-2.6.31-16-generic > ~/vmlinuz-2.6.31-16-generic-hexdump
adrian@adrian-desktop:/boot$ gvim ~/vmlinuz-2.6.31-16-generic-hexdump

其結果如下所示:

Figure 2. Hexdump from Linux Kernel

其中，0xAA55為Linux早期的核心開機磁區最後一個位元組(第512個位元組，arch/x86/boot/header.S:103)。0x62eb代表往下跳至62個位元組，即0x00000262位址。

本篇文章只介紹Linux之real-mode核心程式碼的entry point，往後會有陸陸續續的文章繼續探討。

【Reference】
The Kernel Boot Process

[Ubunut] 解決Firefox Flash網頁亂碼

2009-12-18T14:12:00.001+08:00

Follow up:
1. sudo rm -f /etc/fonts/conf.d/49-sansserif.conf
2. restart firefox

大功告成.

[Reference] http://blog.xuite.net/maxkerr/blog/17037089

likely() and unlikely() macro in Linux kernel

2009-05-21T18:20:00.004+08:00

Linux核心原始碼，經常出現兩個巨集：likely() and unlikely()，如下所示:

#define likely(x) __builtin_expect(!!(x), 1)
#define unlikely(x) __builtin_expect(!!(x), 0)

重點就是__builtin_expect這個函式的意義。此函式用來告訴編譯器，哪些程式區段可做預測。
底下為__builtin_expect的原型:

long __builtin_expect(long EXP, long C)
此函式__builtin_expect有兩大重點:
__builtin_expect的回傳值即EXP這個判斷式。
__builtin_expect語意上，是期待(EXP == C)。
例子一:
if (__builtin_expect(x, 1))
    do_something();

此敘述告知編譯器，x變數期待是1 (上述重點2), 且由於x=1, 所以__builtin_expect回傳值便是1(上述重點1)，因此編譯器可以大膽預測do_something()一定會被執行到。因此便能將處理器的管線(Pipe Line)功能發揮的淋漓盡致。

例子二:
if (__builtin_expect(x, 0))
    do_something1();
else
    do_something2();

此敘述告知編譯器，x變數期待是0 (上述重點2), 且由於x=0, 所以__builtin_expect回傳值便是0(上述重點1)，因此編譯器可以大膽預測do_something2()一定會被執行到，而不是預測執行do_something1()。

總結likely()與unlikely()巨集:

if(likely(x)) {
預測想要執行的原始碼
} else {
}

if(unlikely(x)) {
} else {
預測想要執行的原始碼
}

[Reference]
1. FAQ/LikelyUnlikely
2. richliu's blog

The Stringify Operator (#) in C

2009-05-19T19:28:00.004+08:00

繼上次提到Token-pasting operator (##) in C文章後, 這次講一下在C語言define巨集參數使用的另一種方法, 在參數名稱前加一個#運算子, 此運算子代表所帶入的參數會被編譯器視為"字串", 所以#運算子又被稱為字串化運算子, 底下為一簡單的例子:

#define GET_RESULT(exp) printf(#exp "=%d\n", exp)

int main(void)
{
GET_RESULT(3+2);
return ;
}

Token-pasting operator(##) in C

2009-05-18T18:18:00.005+08:00

我們都知道C語言define前端處理假指令用來定義變數、字串或幾行的原始碼(統稱為巨集, Macro)。
當某一巨集被定義為參數帶入之巨集, 我們最常用的就是把該參數當作變數或指標來使用，如下所示:

#define INC_IDX(val, size) (++val % size) -> 以參數為變數之值帶入此巨集
#define GET_DATA(ptr) (ptr->data) -> 以參數為指標帶入此巨集

然而，我們可以把巨集所帶入的參數當作為識別子(Token)的一部分，如下所示:

#include

int class_num = 9;
int class_stds = 10;

#define GET_MEMBER(postfix) class_ ## postfix

int main(void)
{
     printf("class_num: %d\n", GET_MEMBER(num));
     printf("class_stds: %d\n", GET_MEMBER(stds));
     return 0;
}

如上列所示，class_num可以經由GET_MEMBER巨集(帶入部份識別子, 也就是num)取得，此參數傳遞方法稱為Token-pasting operator，這是一個非常好用的方法, 提供給大家參考。

Linus大神的十句經典名言~

2008-12-19T13:52:00.003+08:00

Linus的十句經典名言果然是太妙了, 噹了M$這句"Microsoft isn't evil, they just make really crappy operating systems.", 真是一針見血. 還有這句“My name is Linus, and I am your God.”, 你真的是一位大神!!

【詳情】
Linus大神十句經典名言

Hong Kong

2008-10-16T13:38:00.003+08:00

Ha, I'm in Hong Kong airport to transit to ShangHai airport for the purpose of the business travel. By the way,I'm so lucky that I met the signer, Li-Hong Wang, at the same airplane for transiting to ShangHai airport. Haha

類似網路芳鄰的好物 (sshfs)

2008-08-03T00:13:00.003+08:00

提到Linux網路芳鄰，大家第一個想到必是samba，但有一套小程式也有此功能：sshfs。只要兩台主機都有安裝ssh server，便可互相掛載資料夾，指令如下：

$ sshfs user@remote_host_ip:dir local_host_mountpoint

Skype 2.0 Beta for Linux支援Webcam!

2007-11-11T16:49:00.000+08:00

Skype 2.0 Beta for Linux支援webcam功能囉!! 看起來似乎還不賴~~有興趣的可以看看此Link

Nov 4, 2007 ICOS/COSCUP Day 3

2007-11-07T18:48:00.000+08:00

[開放組織新人秀]
這場會議主要由社群或ㄧ些組織介紹如何法人化的議題。其中，最帥應該算是乃特大吧!!! ㄧ整個砲轟ICOS主辦單位與SLAT理事長，只能說乃特大真的是太猛了!!!

[BSD]
由幾位玩BSD前被介紹FreeBSD相關議題，其中也提到ㄧ套新穎檔案系統─ZFS，感覺ZFS似乎還蠻強大的，有興趣的倒是也可以研究研究。

[Embedded system part1]
首先，由戒色v (jserv大)主講『快快樂樂設計嵌入式即時作業系統』，又再一次看到jserv新的鉅作─設計一套RT OS，只能說jserv果然強啊!!!

接著，由Joseph介紹DirectFB的議題，還蠻有趣的。

最後由Jollen大介紹OpenMoko議題，這場應該算是我最想聽的ㄧ場之ㄧ，Jollen是個強者啊!!! 強力介紹Jollen大的blog。

[Embedded system part2]
這場介紹openWRT的議題，其中比較有趣的是介紹如何Hackㄧ台router，讚!!!

Nov 2, 2007 ICOS/COSCUP Day 1

2007-11-02T23:47:00.000+08:00

今天特地請假，衝去國科會參加ICOS/COSCUP 2007，抵達會場大約10:00，報到完後，便走進會議室準備聽第一個session的演講。在會議室哩，遇到來自kalug的shawn與 kevin，他們居然坐半夜兩點的夜車趕上來，天啊!!!你們真是熱血啊!!!

『Session 1 自由軟體與商業軟體的對話』
此演講可說是自由軟體大戰M$啊!! 看著洪朝貴老師ㄧ直噹M$台灣協理，感覺M$台灣協理也快招架不住，也感覺這位協理也有點無辜，或許M$政策並非由她所主導。Anyway，此場會議便充滿著火藥味結束。

『Session 2 OpenSolaris Distro: The Road to Solaris Next』
講者ㄧ直推銷他們所開發的Solaris作業系統，說這是世界上最優秀的OS喲。緊接著，介紹Sun最近的ㄧ個專案─OpenSolaris，此為一套開放的Solaris作業系統，有興趣可以在Google打OpenSolaris關鍵字便能找到。

『Session 3 Linux LAN驅動程式開發』
此會議有Thinker主講有關網卡驅動程式開發，由於自己已有此方面相關經驗，所以覺得主講著講的還蠻清楚。

『Session 4 Embedded system Security』
此會議由徐千洋前輩主講，這應該是今天最精采的ㄧ場吧! Buffer Overflow講的簡單明瞭，一整個讚啊!!真不愧是Linux C函式庫的作者啊!!

Vim Tip: 識別子補齊 (Word Completion)

2007-10-29T19:33:00.000+08:00

用IDE寫過程式的人，應該都體會過識別子補齊的功能。譬如說，忘記某一結構的某一成員的全名，通常只要記得幾個字母，IDE便會秀出一個符合這幾個字母的小方塊，以供您選擇。

Vim當然有此功能，在Insert mode，把游標移到識別子上，再按Ctrl+n 或 Ctrl+p就可以了。

範例

下圖在某一結構詢問有哪些成員。

按Ctrl+n變出現下圖之結果:

當然忘記某一函式也行。例如，打mem然後再按Ctrl+n，如下兩圖所示:

[Reference]
Vim官網

Adrian's Blog被LinuxByExample收錄?

2007-10-24T22:26:00.000+08:00

剛剛去LinuxByExample逛了一下，發現小弟的Blog被該網站收錄至"Chinese Linux Blog"，大驚!!!

升級Ubuntu 7.10 (Gusty)後，Gvim亂碼!

2007-10-24T18:35:00.001+08:00

最近把Ubuntu升級至7.10 (Gusty)，發現執行Gvim居然會亂碼，囧rz..且還有Assertion。

** (gvim:9348): CRITICAL **: ascii_glyph_table_init: assertion `gui.ascii_glyphs->num_glyphs == sizeof(ascii_chars)' failed

結果是Gvim默認的一些字型(Ex: Sans, Monspace) 搞的鬼。因此換別的字型就可以用了，編輯~/.vimrc加入下列幾行：

if has("gui")
set guifont=Bitstream\ Vera\ Sans\ Mono\ 12
endif

輕輕鬆鬆升級Ubuntu (7.04 -> 7.10)

2007-10-22T19:51:00.000+08:00

今天在網路上看到四元兄有關升級Ubuntu的圖文說明，簡單明瞭，推啊。重點是完全不用修改/etc/apt/sources.list，推薦給大家!!!

ICOS/COSCUP 2007

2007-10-19T22:26:00.000+08:00

一年一度的台灣開放源碼研討會將於2007 11月1日至11月4日 (ICOS 2007)在國科會科技大樓舉行，其中較有興趣的是嵌入式系統與驅動程式相關議題，打算衝三天的session，想聽的session如下:

11/2 10:30~11:20 Keynote:自由軟體與商業軟體的對話
11/2 11:30~12:10 Keynote:SUN Microsystems
11/2 13:00~18:00 Linux平台周邊驅動程式開發研討會

11/3 10:00~12:00 COSCUP: 文字資訊處理
11/3 13:00~16:10 COSCUP: Web Based Platform & COSCUP: Distributed Computing
11/3 16:30~18:00 COSCUP: linux based laptop 與社群 & COSCUP: lightning talk

11/4 09:10~10:40 COSCUP: 開放組織新人秀
11/4 10:50~12:00 COSCUP: BSD
11/4 13:00-15:00 COSCUP: 嵌入式系統 #1
11/4 15:20-17:20 COSCUP: 嵌入式系統 #2

Linux Kernel: 強大又好用的list_head結構

2007-10-18T18:58:00.002+08:00

程式設計者在設計一個doubly linked list時，通常會在所宣告的結構裡宣告兩個結構指標，如下所示：

struct student {
    char name[16];
    int id;
    struct student *next, *prev;
};

只要經由prev與next兩個結構指標，便能取得該doubly linked list所有資訊。

然而，Linux kernel並非引用此種作法。因此，Linux kernel定義一通用結構 (struct list_head， include/linux/list.h)，用以實作doubly linked list，此結構相當簡單，如下所示：

struct list_head {
    struct list_head *next, *prev;
};

所以物件student宣告為如下：

struct student
{
    char name[16];
    int id;
    struct list_head list;
};

藉由list變數便能取得doubly linked list所有資訊。

list_head相關Marco與Function

這裡僅介紹較常用的macro與function，如欲進一步得知其它marco請參考include/linux/list.h

LIST_HEAD(name)
struct list_head name = { &(name), &(name) };
將next與prev指到自己，意味著此list為空的。

list_empty(const struct list_head *head)
retrun head->next == head;
檢查此list是否為空的。

list_add(struct list_head *new, struct list_head *head)
head->next->prev = new;
new->next = head->next;
new->prev = head;
head->next = new;
將資料加入至doubly linked list最前端。建議自己動手畫個圖，便可了解這幾個指標指到何處。

list_del(struct list_head *entry)
entry->next->prev = entry->prev;
entry->prev->next = entry->next;
將某一資料從中刪除。

list_entry(ptr,type,member)
((type *)((char *)(ptr)-(unsigned long)(&((type *)0)->member)))
透過此函式便能算出結構的起始位址，並做結構轉型便能取得結構的資料，此計算方式相當好用啊!!!
以struct student為例，如下所示：

(unsigned long)(&((struct student *)0)->member))) ==> 計算出list成員相對位址。通常看到這一個敘述，直覺地覺得應該會記憶體區段錯誤吧 (Segmentation Fault)!? 因為該敘述用NULL的pointer存取list成員，但在(struct student *)0)->member))前面加了&符號，就不會發生記憶體區段錯誤。因為&符號，只意味著存取list的位址，而不是資料，經由此敘述便能取得list的位移植。如下圖所示，該敘述所得之位移植值為20。
((type *)((char *)(ptr)-(unsigned long)(&((type *)0)->member))) ==> 取得位移植之後，再將list的位址減去位移植，便能取得該結構的起始位址，如下圖所示 (假設結構起始位址為x)，最後再做結構轉型變大功告成。

list_for_each(pos, head)
for (pos = (head)->next; pos != (head); pos = pos->next)
取得該doubly linked list所有資料。

範例程式
光看這些Macro跟函式可能比較無法有sense，因此小弟寫了一簡單的程式，有興趣的可以下載此範例程式玩玩看。XDD

[Reference]
Understanding the Linux Kernel, Third Edition
Linux Kernel Source Code Version 2.6.20-15

Vim Plugin: 好用的C函式庫參考手冊 (CRefVim)

2007-10-12T19:35:00.000+08:00

是否曾在coding的時候，知道函式名稱卻忘了如何傳遞參數? CRefVim Plugin會是您的好幫手, 至Vim官網下載並按照齊步驟安裝，便能有此功能。

功能說明

在Vim常態模式 (Normal Mode)按"\cw"，便會出現"What to lookup:"，輸入欲查詢的函式名稱。
編輯一個C語言原始檔，此原始檔有memset函式，假設欲查詢memset函數說明，將游標移至memset再按\cr，就可以嚕!!

Linux Kernel: 簡介HZ, tick and jiffies

2007-10-05T16:55:00.000+08:00

Linux核心幾個重要跟時間有關的名詞或變數，底下將介紹HZ、tick與jiffies。

HZ
Linux核心每隔固定週期會發出timer interrupt (IRQ 0)，HZ是用來定義每一秒有幾次timer interrupts。舉例來說，HZ為1000，代表每秒有1000次timer interrupts。HZ可在編譯核心時設定，如下所示 (以核心版本2.6.20-15為例)：

adrian@adrian-desktop:~$ cd /usr/src/linux adrian@adrian-desktop:/usr/src/linux$ make menuconfig Processor type and features ---> Timer frequency (250 HZ) --->

其中HZ可設定100、250、300或1000。以小弟的核心版本預設值為250。

小實驗
觀察/proc/interrupt的timer中斷次數，並於一秒後再次觀察其值。理論上，兩者應該相差250左右。

adrian@adrian-desktop:~$ cat /proc/interrupts | grep timer && sleep 1 && cat /proc/interrupts | grep timer 0: 9309306 IO-APIC-edge timer 0: 9309562 IO-APIC-edge timer


上面四個欄位分別為中斷號碼、CPU中斷次數、PIC與裝置名稱。

問題來了，timer interrupt會做哪些事情? 答案如下所列：

更新時間、日期與系統從開機至目前經過多少時間。
更新系統資源使用率統計
檢查正在執行的程序是否已經超過其所分配的執行時間額度。如果是的話，則侵佔(preempt)該程序以利執行其它等待執行的程序。
檢查軟體時間器(Software timer，如alarm系統呼叫)跟時間延遲函式(Delay function)的延遲時間是否已經超過。

Tick
Tick是HZ的倒數，意即timer interrupt每發生一次中斷的時間。如HZ為250時，tick為4毫秒 (millisecond)。

Jiffies
Jiffies為Linux核心變數(32位元變數，unsigned long)，它被用來紀錄系統自開幾以來，已經過多少的tick。每發生一次timer interrupt，Jiffies變數會被加一。值得注意的是，Jiffies於系統開機時，並非初始化成零，而是被設為-300*HZ (arch/i386/kernel/time.c)，即代表系統於開機五分鐘後，jiffies便會溢位。那溢位怎麼辦? 事實上，Linux核心定義幾個macro(timer_after、time_after_eq、time_before與time_before_eq)，即便是溢位，也能藉由這幾個macro正確地取得jiffies的內容。

另外，80x86架構定義一個與jiffies相關的變數jiffies_64 ，此變數64位元，要等到此變數溢位可能要好幾百萬年。因此要等到溢位這刻發生應該很難吧。那如何經由jiffies_64取得jiffies資訊呢? 事實上，jiffies被對應至jiffies_64最低的32位元。因此，經由jiffies_64可以完全不理會溢位的問題便能取得jiffies。

StarDict也可發音

2007-10-02T18:32:00.000+08:00

如同Dr.eye一樣，StarDict也可單字發音，其設定如下:

至Sourceforge下載WyabdcRealPeopleTTS檔案
將WyabdcRealPeopleTTS.tar.bz2解壓縮，解壓縮會產生WyabdcRealPeopleTTS資料夾，將其資料夾移至/usr/share/即可。
重新啟動stardict，查詢單字看看吧!!

[Reference]
海芋小站 - 介紹一系列StarDict設定

Vim Tip:在原始檔與標頭檔之間切換 (Switch between source file and header file)

2007-10-01T20:25:00.000+08:00

之前使用Anjuta有一個很方便快速鍵可以切換原始檔與標頭檔，但最近一直搜尋Vim是否也有此功能? 答案是有的，廢話不多說，設定如下：

編輯~/.vim/ftplugin/c_extra.vim，加入底下兩行
nmap ,c :find %:t:r.c ---> 將,c對應至搜尋原始檔(也就是.c檔)
nmap ,h :find %:t:r.h ---> 將,h對應至搜尋標頭檔(也就是.h檔)

如此便大功告成

[Reference]
Vim tip website

Trace Code的好幫手: GVim+Ctags+Cscope

2007-09-07T19:31:00.000+08:00

Trace Code的軟體舉凡Source Navigator與Anjuta都佔有一定比例使用人數，但GVim+Ctags+Cscope更是一項不錯的選擇，底下將簡單介紹如何使用Ctags與Cscope

Ctags
Ctags用來產生原始碼每一tag(函數名或識別子)所在位置，執行Ctags會產生名為tags的檔案，Vim參考此檔便可知道每一tag的資訊。因此，只要將游標移至函數名或識別子上，按Ctrl+
]就可以跳至函數或識別子定義的地方。如欲返回，則按Ctrl+t即可。

Cscope
使用Cscope可搜尋tag、搜尋哪些地方呼叫某一函數、搜尋某一檔案與利用正規表達式搜尋相關字串等等功能 (在Vim底下按":cs"會秀出Usage Tip)。

範例示範 (Step by Step，假設欲Trace Linux核心原始碼)

1. 至Cscope官網下載cscope_maps.vim，並將之複製到~/.vim/plugin/。如此便能於啟動Vim時，自動載入cscope產生出來的檔案 (cscope.out)。

2. 至/usr/src/linux-source-版本編號，執行ctags與cscope兩個檔案。

adrian@adrian-desktop:~# cd /usr/src/linux-source-2.6.20

adrian@adrian-desktop:/usr/src/linux-source-2.6.20# ctags -R && cscope -R (ctags產生tags檔，cscope產生cscope.out) --> 如欲離開cscope，按Ctrl+D即可。

3. 隨便編輯一個.c檔，如init/main.c

adrian@adrian-desktop:/usr/src/linux-source-2.6.20# vim init/main.c

假設在init/main.c想要觀看get_option這個識別子定義的地方，將游標移到該識別子上，再按Ctrl+]。如欲知道哪些地方呼叫該識別子，將游標移到該識別子上，按Ctrl+\，再按c即可。Ctrl+\，再按s則搜尋該識別子出現的地方。

New Google Applications for Linux coming soon!

2007-09-05T19:29:00.000+08:00

在slashdot看到Google Linux用戶端服務開發團隊 (Google Linux Client Team)正在開發Linux Desktop Application，應該蠻值得期待的吧!! 更有人期待Google Talk可以運作於Linux (沒有audio/Microphone等問題)。

有興趣可以看看!

Related links:
New Google Linux Apps

Ubuntu 7.04 (Feisty) + Adobe Reader 7.0

2007-05-25T09:43:00.000+08:00

Adobe reader 7.0在Ubuntu套件庫有deb包了, 詳情參考Ubuntu台灣官網有安裝教學.

3D Linux Desktop --> Ubuntu 7.04 + Beryl

2007-05-16T18:48:00.000+08:00

想玩Ubuntu想了一段時間, 最近有空終於把Linux distribution從Debian換成Ubuntu, 安裝完成重開後, Ubuntu給我第一個印象當然就是介面相當友善, 且感覺Ubuntu蠻棒的, 不愧是風評相當棒的Distribution.

言歸正傳, 今年四月在OSDC.TW 2007遇到Yuren, 聽Yuren說Ubuntu在安裝與設定Beryl相當容易, 前陣子索性安裝Beryl,. 如Yuren所說, apt-get一下, 使用ATI open source drvier, 外加簡單設定, Linux 3D就大功告成!

底下為我的xorg.conf片段 (顯卡為 ATI Technologies Inc RV370 [Sapphire X550 Silent]

Section "Module"
Load "i2c"
Load "bitmap"
Load "ddc"
Load "dri"
Load "extmod"
Load "freetype"
Load "glx"
Load "int10"
Load "vbe"
EndSection

Section "ServerLayout"
Option "AIGLX" "true"
Identifier "Default Layout"
Screen "Default Screen"
InputDevice "Generic Keyboard"
InputDevice "Configured Mouse"
InputDevice "stylus" "SendCoreEvents"
InputDevice "cursor" "SendCoreEvents"
InputDevice "eraser" "SendCoreEvents"
EndSection

Section "Device"
Identifier "ATI Technologies Inc RV370 [Sapphire X550 Silent]"
Driver "radeon"
BusID "PCI:1:0:0"
EndSection

Section "DRI"
Mode 0666
EndSection

Section "Extensions"
Option "Composite" "Enable"
EndSection

天殺的"texlive-base-bin"

2007-04-27T11:22:00.000+08:00

最近將Debain從lenny升級到sid遇到一個天殺的問題. 系統在設定texlive-base-bin這支程式的時候, 居然把我1G的RAM吃完, 連同我2G的Swap也全部被它給用它, 導致整個OS一直忙碌地做swap, 其設定訊息如下所示:

Setting up texlive-base-bin (2007-5)
Running mktexlsr. This may take some time...done
Building format(s) --all This may take some time.

結果光build format就花了4、5個小時還是沒做完. 因此, 索性將RAM升級到2G, 結果還是一樣, 2G RM吃完, 接著再把2G swap也用完, 且讓它跑了一整個晚上 (將近12小時), 結果還是沒build完. So, you don't just take some time. You certainly take a long long time! Goddamned!

哀....現在我的debian已經被我搞爛. 看來現在是轉戰Ubuntu的時候了, 之前看到[Yuren]在玩Ubuntu, 想說有時間一定要玩玩看, 反正都要重灌了, 乾脆完Ubuntu看看好了!

debian NO_PUBKEY error

2007-04-26T10:42:00.002+08:00

Debian或Unbuntu使用者在更新套件往往都會出現類似NO_PUBKEY xxxxxxxxxxxx的錯誤訊息, 此代表使用的public key已逾期或有新加入 apt 的 source 但未下載該對應之公開金鑰, 目前的解法是利用gpg程式到key server下載該key, 例如:

$ sudo gpg --keyserver hkp://wwwkeys.eu.pgp.net --recv-keys xxxxxxxxxxxxxxxx
$ sudo gpg --armor --export xxxxxxxxxxxxxxxx | apt-key add -

如此便解決該問題, 但就小弟所上班公司的網路只能從port 80出去, 上面之方法似乎沒辦法解決 (被firewall擋掉, 底下提供一簡單的方法:
1. 首先, 先到key server網站[SURFnet Public Key Infrastructure]下載公開金鑰, 例如:欲搜尋公開金鑰為A70DAF536070D3A1, 因此就在"Search String"文字方塊鍵入"0xA70DAF536070D3A1", 並下載存為key.txt

2. 使用apt-key程式手動加入A70DAF536070D3A1之公開金鑰
$ sudo apt-key add key.txt

3. 大功告成
$ sudo apt-get update --> 應該就可以了!!

[參考文獻]
APT 系統的金鑰管理機制簡介

基於Linux平台的智慧型手機

2007-04-09T14:25:00.000+08:00

最近看到一支以Linux(採用OpenMoko)為平台的smartphone手機, 其手機由大眾電腦所開發, 型號為Neo 1973, 感覺介面還蠻friendly, 且又號稱hackable. 讚!!!

參考:
LinuxDevices
Jollen大Blog

Adrian's Blog

[C語言] 兩變數內容值互換技巧

簡介C語言volatile關鍵字及其陷阱

[Linux Kernel] Allocate memory buffer whose starting address is aligned with the specific memory size

解決"sudo: must be setuid root"的問題

[打造簡易作業系統 - 以GNU Assembler組合語言撰寫] (七) 利用Call Gate與TSS (Task-State Segment)實現特權等級的轉換

[打造簡易作業系統 - 以GNU Assembler組合語言撰寫] (六) 簡介Call Gate

現今最受歡迎的Linux Distribution

[打造簡易作業系統 - 以GNU Assembler組合語言撰寫] (五) 使用Local Descriptor Table (LDT)

[打造簡易作業系統 - 以GNU Assembler組合語言撰寫] (四) 由16位元真實模式 (Real Mode) 進入32位元保護模式 (Protect Mode)

[打造簡易作業系統 - 以GNU Assembler組合語言撰寫] (三) Boot Loader + 作業系統載入實例 (CF Card)

Google將推出Chrome作業系統的平板電腦

Google大神開始對Linux Kernel Source貢獻了

[打造簡易作業系統 - 以GNU Assembler組合語言撰寫] (二) Boot Loader + 作業系統載入實例 (QEMU)

[打造簡易作業系統 - 以GNU Assembler組合語言撰寫] (一) 開機Hello World實例

簡介Linux Block I/O Layer (三) - I/O Path

簡介Linux Block I/O Layer (二) - 探討BIO (Block I/O) and Request 結構

簡介Linux Block I/O Layer (一) - Page, BIO (Block I/O) and Request 結構意義

C語言malloc之sizeof使用技巧

Linux Kernel: container_of 巨集

Linux Kernel: Lookaside Cache (前瞻快取)

Linux Kernel: __init, __initdata屬性

An Introduction to Linux Kernel Booting Sequence Part 3

An Introduction to Linux Kernel Booting Sequence Part 2

An Introduction to Linux Kernel Booting Sequence Part 1

[Ubunut] 解決Firefox Flash網頁亂碼

likely() and unlikely() macro in Linux kernel

The Stringify Operator (#) in C

Token-pasting operator(##) in C

Linus大神的十句經典名言~

Hong Kong

類似網路芳鄰的好物 (sshfs)

Skype 2.0 Beta for Linux支援Webcam!

Nov 4, 2007 ICOS/COSCUP Day 3

Nov 2, 2007 ICOS/COSCUP Day 1

Vim Tip: 識別子補齊 (Word Completion)

Adrian's Blog被LinuxByExample收錄?

升級Ubuntu 7.10 (Gusty)後，Gvim亂碼!

輕輕鬆鬆升級Ubuntu (7.04 -> 7.10)

ICOS/COSCUP 2007

Linux Kernel: 強大又好用的list_head結構

Vim Plugin: 好用的C函式庫參考手冊 (CRefVim)

Linux Kernel: 簡介HZ, tick and jiffies

StarDict也可發音

Vim Tip:在原始檔與標頭檔之間切換 (Switch between source file and header file)

Trace Code的好幫手: GVim+Ctags+Cscope

New Google Applications for Linux coming soon!

Ubuntu 7.04 (Feisty) + Adobe Reader 7.0

3D Linux Desktop --> Ubuntu 7.04 + Beryl

天殺的"texlive-base-bin"

debian NO_PUBKEY error

基於Linux平台的智慧型手機

Linux Kernel: init, initdata屬性