void _db_print(const char *format,...){
va_list args;
time_t tnow;
struct tm *tmp;
va_start(args, format);
{
tnow = time((time_t*)NULL);
tmp=localtime(&tnow);
fprintf(stderr,"%d-%02d-%02d %02d:%02d:%02d.",\
1900+tmp->tm_year,tmp->tm_mon+1,tmp->\
tm_mday,tmp->tm_hour,tmp->tm_min,tmp->tm_sec);
}
vfprintf(stderr,format, args);
va_end(args);
}
int debug_level=0;
#ifndef debug
#define debug(LEVEL) (LEVEL ? debug_level) ? (void) 0 : _db_print
#endif
#define dbgprint(format,args...) \
fprintf(stderr, format, ##args)
#define PRINTK(format, args...) {printk (KERN_ERR "%s" format, __FUNCTION__ , ## args);
#define debug(LEVEL) (LEVEL > debug_level) ? (void) 0 : _db_print
2006年4月15日 星期六
簡單地說，va函數的實現就是對參數指針的使用和控制。
typedef char * va_list; // x86平台下va_list的定義
函數的固定參數部分，可以直接從函數定義時的參數名獲得；對於可選參數部分，先將指針指向第一個可選參數，然後依次後移指針，根據與結束標誌的比較來判斷是否已經獲得全部參數。因此，va函數中結束標誌必須事先約定好，否則，指針會指向無效的記憶體地址，導致出錯。
這裡，移動指針使其指向下一個參數，那麼移動指針時的偏移量是多少呢，沒有具體答案，因為這裡涉及到記憶體對齊（alignment）問題，記憶體對齊跟具體使用的硬體平臺有密切關係，比如大家熟知的32位x86平臺規定所有的變數地址必須是4的倍數(sizeof(int) = 4)。va機制中用宏_INTSIZEOF(n)來解決這個問題，沒有這些宏，va的可攜性無從談起。
首先介紹宏_INTSIZEOF(n)，它求出變數佔用記憶體空間的大小，是va的實現的基礎。
#define _INTSIZEOF(n) ((sizeof(n)+sizeof(int)-1)&~(sizeof(int) - 1) )
#define va_start(ap,v) ( ap = (va_list)&v + _INTSIZEOF(v) )
//第一個可選參數地址
#define va_arg(ap,t) ( *(t *)((ap += _INTSIZEOF(t)) - _INTSIZEOF(t)) ) //下一個參數地址
#define va_end(ap) ( ap = (va_list)0 )
//將指針置為無效
下表是針對函數int TestFunc(int n1, int n2, int n3, …)
參數傳遞時的記憶體堆棧情況。（C編譯器默認的參數傳遞方式是__cdecl。）
對該函數的調用為int result = TestFunc(a, b, c, d. e); 其中e為結束標誌。
高位址
最後一個可選參數 => 用va_start後，arg_ptr指向下一個可選參數的位址
第一個可選參數 => 用va_start後，arg_ptr指向的位址
N3位址
N2位址
N1位址
函式返回位址
低位址
從上圖中可以很清楚地看出va_xxx宏如此編寫的原因。
1． va_start。為了得到第一個可選參數的地址，我們有三種辦法可以做到：
A) = &n3 + _INTSIZEOF(n3)
// 最後一個固定參數的地址 + 該參數佔用記憶體的大小
B) = &n2 + _INTSIZEOF(n3) + _INTSIZEOF(n2)
// 中間某個固定參數的地址 + 該參數之後所有固定參數佔用的記憶體大小之和
C) = &n1 + _INTSIZEOF(n3) + _INTSIZEOF(n2) + _INTSIZEOF(n1)
// 第一個固定參數的地址 + 所有固定參數佔用的記憶體大小之和
從編譯器實現角度來看，方法B)，方法C)為了求出地址，編譯器還需知道有多少個固定參數，以及它們的大小，沒有把問題分解到最簡單，所以不是很聰明的途徑，不予採納；相對來說，方法A)中運算的兩個值則完全可以確定。va_start()正是採用A)方法，接受最後一個固定參數。調用va_start()的結果總是使指針指向下一個參數的地址，並把它作為第一個可選參數。在含多個固定參數的函數中，調用va_start()時，如果不是用最後一個固定參數，對於編譯器來說，可選參數的個數已經增加，將給程式帶來一些意想不到的錯誤。(當然如果你認為自己對指針已經知根知底，遊刃有餘，那麼，怎麼用就隨你，你甚至可以用它完成一些很優秀（高效）的代碼，但是，這樣會大大降低代碼的可讀性。)
注意：宏va_start是對參數的地址進行操作的，要求參數地址必須是有效的。一些地址無效的類型不能當作固定參數類型。比如：寄存器類型，它的地址不是有效的記憶體地址值；數組和函數也不允許，他們的長度是個問題。因此，這些類型時不能作為va函數的參數的。
2． va_arg身兼二職：返回當前參數，並使參數指針指向下一個參數。
初看va_arg宏定義很彆扭，如果把它拆成兩個語句，可以很清楚地看出它完成的兩個職責。
#define va_arg(ap,t) ( *(t *)((ap += _INTSIZEOF(t)) - _INTSIZEOF(t)) ) //下一個參數地址
// 將( *(t *)((ap += _INTSIZEOF(t)) - _INTSIZEOF(t)) )拆成：
/* 指針ap指向下一個參數的地址 */
1． ap += _INTSIZEOF(t)； // 當前，ap已經指向下一個參數了
/* ap減去當前參數的大小得到當前參數的地址，再強制類型轉換後返回它的值 */
2． return *(t *)( ap - _INTSIZEOF(t))
回想到printf/scanf系列函數的%d %s之類的格式化指令，我們不難理解這些它們的用途了- 明示參數強制轉換的類型。
(注：printf/scanf沒有使用va_xxx來實現，但原理是一致的。)
3．va_end很簡單，僅僅是把指針作廢而已。
#define va_end(ap) (ap = (va_list)0) // x86平臺
四、 簡潔、靈活，也有危險
從va的實現可以看出，指針的合理運用，把C語言簡潔、靈活的特性表現得淋漓盡致，叫人不得不佩服C的強大和高效。不可否認的是，給編程人員太多自由空間必然使程式的安全性降低。va中，為了得到所有傳遞給函數的參數，需要用va_arg依次遍歷。其中存在兩個隱患：
1）如何確定參數的類型。
2）va_arg在類型檢查方面與其說非常靈活，不如說是很不負責，因為是強制類型轉換，va_arg都把當前指針所指向的內容強制轉換到指定類型；
3）2）結束標誌。如果沒有結束標誌的判斷，va將按默認類型依次返回記憶體中的內容，直到訪問到非法記憶體而出錯退出。例2中SqSum()求的是自然數的平方和，所以我把負數和0作為它的結束標誌。例如scanf把接收到的回車符作為結束標誌，大家熟知的printf()對字符串的處理用'\0'作為結束標誌，無法想像C中的字符串如果沒有'\0'， 代碼將會是怎樣一番情景，估計那時最流行的可能是字符數組，或者是malloc/free。
4）允許對記憶體的隨意訪問，會留給不懷好意者留下攻擊的可能。當處理cracker精心設計好的一串字符串後，程式將跳轉到一些惡意代碼區域執行，以使cracker達到其攻擊目的。(常見的exploit攻擊)所以，必需禁止對記憶體的隨意訪問和嚴格控制記憶體訪問邊界。
typedef char * va_list; // x86平台下va_list的定義
函數的固定參數部分，可以直接從函數定義時的參數名獲得；對於可選參數部分，先將指針指向第一個可選參數，然後依次後移指針，根據與結束標誌的比較來判斷是否已經獲得全部參數。因此，va函數中結束標誌必須事先約定好，否則，指針會指向無效的記憶體地址，導致出錯。
這裡，移動指針使其指向下一個參數，那麼移動指針時的偏移量是多少呢，沒有具體答案，因為這裡涉及到記憶體對齊（alignment）問題，記憶體對齊跟具體使用的硬體平臺有密切關係，比如大家熟知的32位x86平臺規定所有的變數地址必須是4的倍數(sizeof(int) = 4)。va機制中用宏_INTSIZEOF(n)來解決這個問題，沒有這些宏，va的可攜性無從談起。
首先介紹宏_INTSIZEOF(n)，它求出變數佔用記憶體空間的大小，是va的實現的基礎。
#define _INTSIZEOF(n) ((sizeof(n)+sizeof(int)-1)&~(sizeof(int) - 1) )
#define va_start(ap,v) ( ap = (va_list)&v + _INTSIZEOF(v) )
//第一個可選參數地址
#define va_arg(ap,t) ( *(t *)((ap += _INTSIZEOF(t)) - _INTSIZEOF(t)) ) //下一個參數地址
#define va_end(ap) ( ap = (va_list)0 )
//將指針置為無效
下表是針對函數int TestFunc(int n1, int n2, int n3, …)
參數傳遞時的記憶體堆棧情況。（C編譯器默認的參數傳遞方式是__cdecl。）
對該函數的調用為int result = TestFunc(a, b, c, d. e); 其中e為結束標誌。
高位址
最後一個可選參數 => 用va_start後，arg_ptr指向下一個可選參數的位址
第一個可選參數 => 用va_start後，arg_ptr指向的位址
N3位址
N2位址
N1位址
函式返回位址
低位址
從上圖中可以很清楚地看出va_xxx宏如此編寫的原因。
1． va_start。為了得到第一個可選參數的地址，我們有三種辦法可以做到：
A) = &n3 + _INTSIZEOF(n3)
// 最後一個固定參數的地址 + 該參數佔用記憶體的大小
B) = &n2 + _INTSIZEOF(n3) + _INTSIZEOF(n2)
// 中間某個固定參數的地址 + 該參數之後所有固定參數佔用的記憶體大小之和
C) = &n1 + _INTSIZEOF(n3) + _INTSIZEOF(n2) + _INTSIZEOF(n1)
// 第一個固定參數的地址 + 所有固定參數佔用的記憶體大小之和
從編譯器實現角度來看，方法B)，方法C)為了求出地址，編譯器還需知道有多少個固定參數，以及它們的大小，沒有把問題分解到最簡單，所以不是很聰明的途徑，不予採納；相對來說，方法A)中運算的兩個值則完全可以確定。va_start()正是採用A)方法，接受最後一個固定參數。調用va_start()的結果總是使指針指向下一個參數的地址，並把它作為第一個可選參數。在含多個固定參數的函數中，調用va_start()時，如果不是用最後一個固定參數，對於編譯器來說，可選參數的個數已經增加，將給程式帶來一些意想不到的錯誤。(當然如果你認為自己對指針已經知根知底，遊刃有餘，那麼，怎麼用就隨你，你甚至可以用它完成一些很優秀（高效）的代碼，但是，這樣會大大降低代碼的可讀性。)
注意：宏va_start是對參數的地址進行操作的，要求參數地址必須是有效的。一些地址無效的類型不能當作固定參數類型。比如：寄存器類型，它的地址不是有效的記憶體地址值；數組和函數也不允許，他們的長度是個問題。因此，這些類型時不能作為va函數的參數的。
2． va_arg身兼二職：返回當前參數，並使參數指針指向下一個參數。
初看va_arg宏定義很彆扭，如果把它拆成兩個語句，可以很清楚地看出它完成的兩個職責。
#define va_arg(ap,t) ( *(t *)((ap += _INTSIZEOF(t)) - _INTSIZEOF(t)) ) //下一個參數地址
// 將( *(t *)((ap += _INTSIZEOF(t)) - _INTSIZEOF(t)) )拆成：
/* 指針ap指向下一個參數的地址 */
1． ap += _INTSIZEOF(t)； // 當前，ap已經指向下一個參數了
/* ap減去當前參數的大小得到當前參數的地址，再強制類型轉換後返回它的值 */
2． return *(t *)( ap - _INTSIZEOF(t))
回想到printf/scanf系列函數的%d %s之類的格式化指令，我們不難理解這些它們的用途了- 明示參數強制轉換的類型。
(注：printf/scanf沒有使用va_xxx來實現，但原理是一致的。)
3．va_end很簡單，僅僅是把指針作廢而已。
#define va_end(ap) (ap = (va_list)0) // x86平臺
四、 簡潔、靈活，也有危險
從va的實現可以看出，指針的合理運用，把C語言簡潔、靈活的特性表現得淋漓盡致，叫人不得不佩服C的強大和高效。不可否認的是，給編程人員太多自由空間必然使程式的安全性降低。va中，為了得到所有傳遞給函數的參數，需要用va_arg依次遍歷。其中存在兩個隱患：
1）如何確定參數的類型。
2）va_arg在類型檢查方面與其說非常靈活，不如說是很不負責，因為是強制類型轉換，va_arg都把當前指針所指向的內容強制轉換到指定類型；
3）2）結束標誌。如果沒有結束標誌的判斷，va將按默認類型依次返回記憶體中的內容，直到訪問到非法記憶體而出錯退出。例2中SqSum()求的是自然數的平方和，所以我把負數和0作為它的結束標誌。例如scanf把接收到的回車符作為結束標誌，大家熟知的printf()對字符串的處理用'\0'作為結束標誌，無法想像C中的字符串如果沒有'\0'， 代碼將會是怎樣一番情景，估計那時最流行的可能是字符數組，或者是malloc/free。
4）允許對記憶體的隨意訪問，會留給不懷好意者留下攻擊的可能。當處理cracker精心設計好的一串字符串後，程式將跳轉到一些惡意代碼區域執行，以使cracker達到其攻擊目的。(常見的exploit攻擊)所以，必需禁止對記憶體的隨意訪問和嚴格控制記憶體訪問邊界。
2006年3月27日 星期一
C的組語
GAS與x86(IA32)的AT&T syntax組語寫法
基本介紹
Unix下寫組合語言， 這個需要組合語言的基礎也要有系統的觀念。 使用的工具有nasm或GNU as， nasm用Intel的語法就可以， GNU as跟其它unix上的工具as一樣要按照AT&T的語法規定， 所以如果你是先學Intel的有些語法上需要注意。
AT&T assembly與Intel/Microsoft syntax的不同
order(來源與目的暫存器順序不同)
source在前面destination在後面
Intex Syntax AT&T Syntax
instr dest,source instr source,dest
mov eax,[ecx] movl (%ecx),%eax
register naming(暫存器命名)
AT&T前面要加個% Intel Syntax AT&T Syntax
mov eax,1 movl $1,%eax
mov ebx,0ffh movl $0xff,%ebx
int 80h int $0x80
imme operand(立即定址命名)
AT&T前面要加個$
Intel Syntax AT&T Syntax
mov eax,1 movl $1,%eax
mov ebx,0ffh movl $0xff,%ebx
int 80h int $0x80
memory reference(間接定址)
AT&T用大括號()
Intel Syntax AT&T Syntax
instr foo,segreg:[base+index*scale+disp] instr %segreg:disp(base,index,scale),foo
mov eax,[ebx+20h] movl 0x20(%ebx),%eax
add eax,[ebx+ecx*2h] addl (%ebx,%ecx,0x2),%eax
lea eax,[ebx+ecx] leal (%ebx,%ecx),%eax
sub eax,[ebx+ecx*4h-20h] subl -0x20(%ebx,%ecx,0x4),%eax
opcode naming(指令命名)
必需指定長度 根據系統而不一樣 word有的是32 bits有的是16 bits b : byte
w : word
l : long
Intel Syntax AT&T Syntax
mov al,bl movb %bl,%al
mov ax,bx movw %bx,%ax
mov eax,ebx movl %ebx,%eax
mov eax, dword ptr [ebx] movl (%ebx),%eax
type casting(型別轉換) s (signed)
z (zero)
bl (from byte to long)
bw (from byte to word)
wl (from word to long)
movsbl %al, %edx
long jump, call與ret
Intel Syntax AT&T Syntax
jmp far seg:offsetljmp seg, offset
jmp far INITSEG:GO ljmp $INITSEG, $GO
call far INITSEG:GO lcall $INITSEG, $GO
ret far STACK_ADJUS lret $STACK_ADJUST
C下的inline組語
在C語言中勘進組語的程式碼加個
__asm__("asm code");
__asm__("movl $1,%eax\n\t" // SYS_exit
"xor %ebx,%ebx\n\t"
"int $0x80"
);
注意quote 與\n\t的位置 \n\t是因為gcc其實根據這些與其它c code產生一個.s檔 \n\t只是在.s檔產生newline與tab這在每一行都要除了最後一行不用 另外inline assembly的 通式是 __asm__(asm statements : outputs : inputs : clobber);
通式有兩個重要的概念， 一個是可以和C程式傳變數來溝通，另外 如果我們指定了eax ebx...等register，則這下可完了，如果其他的C code 也正在用eax ebx，則compiler必須先把這些值推進stack才能跑你的asm code， 所以我們可以不特別指定register，讓gcc自動作register運用的最佳化。 其實這是其他mips和其他CPU的作法，別種CPU的register命名沒 eax, ebx.....這麼死與囉唆， $1 $2 $3...就搞定，還可以換來換去很有彈性。 這個通式就是在做這樣的事，請看一個例子 int main (void) {
int operand1, operand2, sum, accumulator;
operand1 = rand (); operand2 = rand ();
__asm__ ("movl %1, %0\n\t"
"addl %2, %0"
: "=r" (sum) /* output operands */
: "r" (operand1), "r" (operand2) /* input operands */
: "0"); /* clobbered operands */
accumulator = sum;
__asm__ ("addl %1, %0\n\t"
"addl %2, %0"
: "=r" (accumulator)
: "0" (accumulator), "g" (operand1), "r" (operand2)
: "0");
return accumulator;
}
第一個__asm__是說input的東西把operand1(C的變數)放到r，也就是%1， operand2(C的變數)放到r，也就是%2，然後執行assembly code的 movl與addl， 然後結果放到sum(C的變數)=r 也就是%0， 在這邊我們沒有指定eax ebx，只是很單純的%0 %1 %2 r。 %0 %1 %2 分別對應了output r， input r， input r， %0 %1 %2.....會先對應output裡的register，再對應input裡的register， 就是它們出現的順序。 gcc會幫我們最佳化register的使用。 clobbered operands是一堆registers， 我們告訴gcc說這些registers的值已經被暴力的摧毀(被改變了)， 你要重新考慮它們的合法性才行， 在這邊0就是%0，gcc會特別照顧一下它所選的%0的值。 有一些規則要說明
r, g, 0這些東西叫constraints(限制的意思)，每一個符號有特殊意義 代表這個暫存器必需是什麼型式的(暫存器有通用暫存器，符點運算暫存器， cpu指令有的允許直接對memory做運算，有的不準等等條件的暫存器， r代表通用型暫存器)。
output operand前一定要有個"="表示這個constraint是read-ony， "="叫constraint modifier。
input output operands後一定要跟著相對應的C 變數的參數， 這是給asm的參數。
如果statement裡真要指定register要多加個%變成%%eax
通用constraints I, J, K .... P 是根據不同cpu可以做不同的解釋來表示一個範圍的立即定址整數
Q, R, S .... U
0, 1, 2 .... 相對於assembly statement裡的%0 %1 %2 ....
a, b, c .... f 可以根據不同cpu可以做不同定義的registers
m 表示這是一個memory的operand 例如mov eax, data中的data
p 合法的記憶體位址
r 一般通用型register
g 任何的通用型register, memory operand, 立即定址的整數
constraints在386上有
a eax
b ebx
c ecx
d edx
S esi
D edi
I 表示只有constant value (0 to 31)才行
r 可以是eax ebx ecx edx esi edi
q 可以是eax ebx ecx edx
g eax, ebx, ecx, edx or variable in memory
A eax and edx combined into a 64-bit integer (use long longs)
基本介紹
Unix下寫組合語言， 這個需要組合語言的基礎也要有系統的觀念。 使用的工具有nasm或GNU as， nasm用Intel的語法就可以， GNU as跟其它unix上的工具as一樣要按照AT&T的語法規定， 所以如果你是先學Intel的有些語法上需要注意。
AT&T assembly與Intel/Microsoft syntax的不同
order(來源與目的暫存器順序不同)
source在前面destination在後面
Intex Syntax AT&T Syntax
instr dest,source instr source,dest
mov eax,[ecx] movl (%ecx),%eax
register naming(暫存器命名)
AT&T前面要加個% Intel Syntax AT&T Syntax
mov eax,1 movl $1,%eax
mov ebx,0ffh movl $0xff,%ebx
int 80h int $0x80
imme operand(立即定址命名)
AT&T前面要加個$
Intel Syntax AT&T Syntax
mov eax,1 movl $1,%eax
mov ebx,0ffh movl $0xff,%ebx
int 80h int $0x80
memory reference(間接定址)
AT&T用大括號()
Intel Syntax AT&T Syntax
instr foo,segreg:[base+index*scale+disp] instr %segreg:disp(base,index,scale),foo
mov eax,[ebx+20h] movl 0x20(%ebx),%eax
add eax,[ebx+ecx*2h] addl (%ebx,%ecx,0x2),%eax
lea eax,[ebx+ecx] leal (%ebx,%ecx),%eax
sub eax,[ebx+ecx*4h-20h] subl -0x20(%ebx,%ecx,0x4),%eax
opcode naming(指令命名)
必需指定長度 根據系統而不一樣 word有的是32 bits有的是16 bits b : byte
w : word
l : long
Intel Syntax AT&T Syntax
mov al,bl movb %bl,%al
mov ax,bx movw %bx,%ax
mov eax,ebx movl %ebx,%eax
mov eax, dword ptr [ebx] movl (%ebx),%eax
type casting(型別轉換) s (signed)
z (zero)
bl (from byte to long)
bw (from byte to word)
wl (from word to long)
movsbl %al, %edx
long jump, call與ret
Intel Syntax AT&T Syntax
jmp far seg:offsetljmp seg, offset
jmp far INITSEG:GO ljmp $INITSEG, $GO
call far INITSEG:GO lcall $INITSEG, $GO
ret far STACK_ADJUS lret $STACK_ADJUST
C下的inline組語
在C語言中勘進組語的程式碼加個
__asm__("asm code");
__asm__("movl $1,%eax\n\t" // SYS_exit
"xor %ebx,%ebx\n\t"
"int $0x80"
);
注意quote 與\n\t的位置 \n\t是因為gcc其實根據這些與其它c code產生一個.s檔 \n\t只是在.s檔產生newline與tab這在每一行都要除了最後一行不用 另外inline assembly的 通式是 __asm__(asm statements : outputs : inputs : clobber);
通式有兩個重要的概念， 一個是可以和C程式傳變數來溝通，另外 如果我們指定了eax ebx...等register，則這下可完了，如果其他的C code 也正在用eax ebx，則compiler必須先把這些值推進stack才能跑你的asm code， 所以我們可以不特別指定register，讓gcc自動作register運用的最佳化。 其實這是其他mips和其他CPU的作法，別種CPU的register命名沒 eax, ebx.....這麼死與囉唆， $1 $2 $3...就搞定，還可以換來換去很有彈性。 這個通式就是在做這樣的事，請看一個例子 int main (void) {
int operand1, operand2, sum, accumulator;
operand1 = rand (); operand2 = rand ();
__asm__ ("movl %1, %0\n\t"
"addl %2, %0"
: "=r" (sum) /* output operands */
: "r" (operand1), "r" (operand2) /* input operands */
: "0"); /* clobbered operands */
accumulator = sum;
__asm__ ("addl %1, %0\n\t"
"addl %2, %0"
: "=r" (accumulator)
: "0" (accumulator), "g" (operand1), "r" (operand2)
: "0");
return accumulator;
}
第一個__asm__是說input的東西把operand1(C的變數)放到r，也就是%1， operand2(C的變數)放到r，也就是%2，然後執行assembly code的 movl與addl， 然後結果放到sum(C的變數)=r 也就是%0， 在這邊我們沒有指定eax ebx，只是很單純的%0 %1 %2 r。 %0 %1 %2 分別對應了output r， input r， input r， %0 %1 %2.....會先對應output裡的register，再對應input裡的register， 就是它們出現的順序。 gcc會幫我們最佳化register的使用。 clobbered operands是一堆registers， 我們告訴gcc說這些registers的值已經被暴力的摧毀(被改變了)， 你要重新考慮它們的合法性才行， 在這邊0就是%0，gcc會特別照顧一下它所選的%0的值。 有一些規則要說明
r, g, 0這些東西叫constraints(限制的意思)，每一個符號有特殊意義 代表這個暫存器必需是什麼型式的(暫存器有通用暫存器，符點運算暫存器， cpu指令有的允許直接對memory做運算，有的不準等等條件的暫存器， r代表通用型暫存器)。
output operand前一定要有個"="表示這個constraint是read-ony， "="叫constraint modifier。
input output operands後一定要跟著相對應的C 變數的參數， 這是給asm的參數。
如果statement裡真要指定register要多加個%變成%%eax
通用constraints I, J, K .... P 是根據不同cpu可以做不同的解釋來表示一個範圍的立即定址整數
Q, R, S .... U
0, 1, 2 .... 相對於assembly statement裡的%0 %1 %2 ....
a, b, c .... f 可以根據不同cpu可以做不同定義的registers
m 表示這是一個memory的operand 例如mov eax, data中的data
p 合法的記憶體位址
r 一般通用型register
g 任何的通用型register, memory operand, 立即定址的整數
constraints在386上有
a eax
b ebx
c ecx
d edx
S esi
D edi
I 表示只有constant value (0 to 31)才行
r 可以是eax ebx ecx edx esi edi
q 可以是eax ebx ecx edx
g eax, ebx, ecx, edx or variable in memory
A eax and edx combined into a 64-bit integer (use long longs)
2006年3月22日 星期三
Spinlock
在這篇文章中，我將會介紹 Kernel 提供用來使用 spinlock 的 function。除此之外，我還會告訴各位，為何在 SMP 的環境裡，使用 spinlock 會比將所有 CPU 的中斷 disable 這個方法來的有效率，我也會告訴各位如何針對不同的使用需求，使 spinlock 的 cost 再降低，進而使系統的效能更好...
前言
在 Linux Kernel 裡有著許多重要的資料結構，這些資料在作業系統的運作中扮演著舉足輕重的角色。然而，Linux 是個多任務的作業系統，也就是在同一時間裡可以同時有許多的行程在執行，所以，很有可能某個行程在依序讀取 inode list，同時卻又有另一個在 inode list 裡加入新的 inode，這會造成什?情形呢？這會造成 inode list 的不穩定。所以，在 Kernel 裡，我們需要一個機制，可以使得當我們在修改某個重要的資料結構時，不能被中斷，即使被中斷了，這個資料結構由於還沒修改完，別的行程也都不能去讀取和修改它。Linux Kernel提供了 spinlock 這個機制可以使我們做到這樣的功能。
有的人會想到當我們在修改某個重要的資料結構時，將中斷都 disable 掉就好了，等修改完了再將中斷 enable 不就得了，何必還要再提供一個 spinlock 來做同樣的事。在 uni-processor 的環境底下，的確是如此。所謂 uni-processor 就是指只有一個 CPU 的電腦，但是在SMP的環境下就不是這麼一回事了。
我們知道現在 Linux 已經有支持 SMP，也就是可以使用多顆 CPU 來加快系統的速度，如果當我們在修改重要的資料結構時，將執行修改工作的 CPU 中斷 disable 掉的話，只有目前的這個 CPU 的執行不會被中斷，在 SMP 環境下，還有別的 CPU 正同時運作，如果別的 CPU 也去修改這個資料結構的話，就會造成同時有兩個 CPU 在修改它，不穩定性就會產生。解決方法是將全部的 CPU 中斷都 disable 掉，等修改完之後，再全部都 enable 起來。但是這樣的做法其 cost 會很大，整個系統的效能會 down 下來。因此，Linux Kernel 才會提供 spinlock 這樣的機制，它不會將全部 CPU 的中斷 disable 掉，所以效率比上述的方法好，但同時卻又能確保資料的穩定性，不會有某個行程在修改它，另外又有一個行程在讀取或修改它的情形發生。
在這篇文章中，我將會介紹 Kernel 提供用來使用 spinlock 的 function。除此之外，我還會告訴各位，為何在 SMP 的環境裡，使用 spinlock 會比將所有 CPU 的中斷 disable 這個方法來的有效率，我也會告訴各位如何針對不同的使用需求，使 spinlock 的 cost 再降低，進而使系統的效能更好。
spinlock的資料結構
spinlock 的資料結構在 Linux底下是以 spinlock_t 來表示的，在 SMP 和 UP(uni-processor)環境底下兩者的欄位有一些差異，其實在 UP 底下 spinlock_t 可以說是一個空的結構，空就是空的，為何要說"可以說是空的"呢？這是因為 gcc 版本的問題，gcc 在 2.8 版以前結構的內容必須不能是空的，而在 2.8 版之後就可以，所以在 UP 環境底下，會根據 gcc 的版本而設定不同的 spinlock_t 結構欄位，但基本上，在 UP 環境底下，是根本不會用到 spinlock_t 結構裡的欄位的，詳情請見以下諸節即可瞭解。
由於 spinlock 主要是用在SMP的環境底下，所以，以下我們就只針對在SMP環境底下的 spinlock_t 結構來討論，它的結構內容是這樣子的：
typedef struct {
volatile unsigned int lock;
} spinlock t;
說穿了，不過就是一個 unsigned int 型別的變數而已，但可不要小看這小小的變數，螺絲釘雖小，功能卻是不可忽視的。
使用 spinlock
spinlock t xxx lock = SPIN_LOCK_UNLOCKED;
unsigned long flags;
spin lock irqsave (&xxx lock, flags)
...critical section...
spin unlock irqrestore (&xxx lock, flags)
這一組的函式在使用上是最保險的，用的頻率也算是最多的。首先在使用前，必須先宣告一個 spinlock_t 型別的變數，並把初始值設為 SPIN_LOCK_UNLOCKED。除此之外，還必須有一個unsigned long型別的變數，這個變數是用來將 CPU 的 flag（旗標）儲存起來的，等 critical section 執行完了，再把 flag 的值設回到系統裡。使用上是很簡單明白的。這兩個 function 除了可以在 SMP 的環境下使用外，在UP的環境裡也是同樣可行的，接下來，我們來看看它們程序碼是怎?寫的。
在 這個檔案裡定義了 spin_lock_irqsave() 及 spin_lock_irqrestore() 這兩個 function。
#define spin_lock_irqsave(lock，flags)
do { local_irq_save(flags); spin_lock(lock); } while (0)
#define spin_unlock_irqrestore(lock，flags)
do { spin_unlock(lock); local_irq_restore(flags); } while (0)
local_irq_save(flags) 做的事就是將 CPU 的 flag 值先儲存到 flags 變數里，然後將 CPU 的中斷 diable 掉。這裡將 CPU 的中斷 disable 是指將執行這段 code 的 CPU，並不是指全部的 CPU。 也就是說它只會 disable local CPU 的中斷。我們可以在裡看到這樣的程序碼：
#define local_irq_save(x) __asm__ __volatile__("pushfl ; popl %0 ;
cli":"=g" (x): /* no input */ :"memory")
#define local_irq_restore(x) __asm__ __volatile__("pushl %0 ; popfl"
/* no output */ :"g" (x):"memory")
至於 local_irq_restore(flags) 從字面上可以很清楚的看出來，只是將 flags 裡的值再設回 CPU 的 flag 裡而已。至於 spin_lock(lock) 和 spin_unlock(lock) 這兩個函式，在 SMP 和在 UP 的環境底下則會擴展成不同的樣子。首先先看到這個檔案的下半部。
#ifdef __SMP__
#include <asm/spinlock.h>
#else /* !SMP */
.......
#endif
在 SMP 的環境底下，SMP 這個constant被會 set。而在 UP 底下則不會，所以，如果要看 UP 底下 spin_lock(lock) 會變成怎?樣子，就必須來看看 #else /* !SMP */ 和 #endif 之間的程序碼。
UP 環境下的 Implementation
我們先來看看在 UP 的環境下， spin_lock(lock) 會變成什?樣子。
#define spin_lock(x) (void)lock
#define spin_unlock(x) do {} while(0)
簡單吧，根本什麼事都沒有做，所以，在 UP 的環境底下，我們如果將上面那段 spinlock 的使用擴展開來的話，會變成下面這個樣子。
spinlock_t xxx_lock = SPIN_LOCK_UNLOCKED;
unsigned long flags;
local_save_flags(flags); cli();
... critical section ...
local_restore_flags(flags);
而這也正是在 UP 環境下，用來保護重要資料結構的寫法。這也就是為什?在介紹spinlock_t 的結構內容時，我們說在UP環境底下這個結構就算是空的也不會影響到 spinlock 的功效，因為根本沒用到裡面的欄位，但是在 SMP 底下，這就很重要了。
SMP 環境下的 Implementation
在 SMP 的環境底下， spin_lock() 和 spin_unlock() 這兩個函式的原始碼是放在。
extern inline void spin_lock(spinlock_t *plock)
{
__asm__ __volatile__(
spin_lock_string
:"=m" (__dummy_lock(plock)));
}
其實，這段程序碼是經過我削減後的，至於削減掉的程序碼是用來做 debug 的，所以，就不列出來，有興趣的朋友不彷自行去看看。在上圖中，spin_lock_string 是一個 macro，加上 __asm 語法，我將它展開成下面這個樣子：
extern inline void spin_lock(spinlock_t *plock)
{
1:
lock ; btsl $0,plock;
jc 2f;
.section .text.lock,"ax"
2:
testb $1,plock;
rep;nop;
jne 2b;
jmp 1b;
.previous
}
讓我們來看看 spin_lock() 這段組合語言是什?意思。在 Linux 底下，組合語言是用 AT&T 的語法，跟平常我們在 PC 底下使用的 Microsoft 語法不相同，主要的差別是 source 與 destination 的位置相反。基本上，spinlock 有兩種狀態，第一種被鎖住的狀態（lock），第二種則是沒被鎖住的狀態（unlock）；當 spinlock 被鎖住時，spinlock_t.lock 會被設為 1，當沒被鎖時，則會設回 0，各位可以去看我們之前所列出來的使用方法，它會將 spinlock_t 結構的初始值設為 SPIN_LOCK_UNLOCK，現在再來看看這個 constant 的值，可以發現它其實就是將 spinlock_t.lock 設為 0 而已。
#define SPIN_LOCK_UNLOCKED (spinlock_t) { 0 }
所以，檢查其狀態就變成了 spin_lock() 的首要工作，如果已被鎖住，則 CPU 就不能去使用它所保護的資料結構，而如果沒上鎖，則可以從 spin_lock() 傳回，接下去使用它所保護的資料。所以，檢查其狀態我們可以檢查 spinlock_t.lock 的第 0 個 bit。btsl $0, plock 會將 plock 的第 0 個 bit 值傳到 flag 旗標的 carry 並把 plock 的第 0 個 bit 設為 1，其中 $0 是在 AT&T 語法中是指數字，也就是 immediate value。所以，再來只要檢查 carry 的值就可以了。當 carry 的值是 1 時，表示 spinlock 是上鎖狀態的，就跳到 label 2 的地方去執行，在程序碼裡，我們可以看到 jump 指令後面接著 2b，2f 及 1b 這些字眼，這些都是指 1: 或 2: 這些 label，如果某個 label 定在 jump 的前面，則指定label 時，要加上 b（backward），如果在後面，則加上 f（forward）。在 label 2 這段程序碼裡，它不停的做迴圈，執行 nop 指令，每次的迴圈都會去檢查一次 spinlock_t.lock 的值，當 spinlock 不是鎖住的狀態時，就會跳離迴圈，離開 spin_lock() 函式。
看完了 spin_lock()，再來看 spin_unlock() 就會發覺簡單多了。
#define spin_unlock(lock)
__asm__ __volatile__( spin_unlock_string
:"=m" (__dummy_lock(lock)))
其中，spin_unlock_string 一樣是個 macro，展開後變成下面這個樣子:
spin_unlock(plock)
｛
lock; btrl $0, plock;
}
btrl $0, plock 這一行會將 plock 的第 0 個 bit 設為 0，可以很清楚的看出來，spin_unlock() 只是將 plock 的第 0 個 bit 再設回 0 而已。在 spin_lock() 和 spin_unlock() 裡我們都可以看到 lock 這個指令在 btrl 或 btsl 的前頭，這個指令的用途是當 btrl 或 btsl 在修改 plock 的值時，其它別的行程都不能來修改 plock 的值，如果有別的行程企圖修改 plock 的值就會造成 exception 的發生。
看到這裡，各位應該可以瞭解 spinlock 的運作方式及其基本的使用方法了，接下來，我要跟各位介紹 spinlock 的另一種小小的變型，叫 read-write spinlock。
第二種的使用方式
有些資料結構是這樣子的，我們希望有人在修改它的內容時，別人都不能讀取或修改它，但是當沒有人在修改它時，可以同時有很多人去讀取它的內容。我們稱這樣的 spinlock 為 read-write spinlock。 Kernel 為它定義了 rwlock_t，放在 裡。使用方式是這樣子的。
rwlock_t xxx_lock = RW_LOCK_UNLOCKED;
unsigned long flags;
read_lock_irqsave(&xxx_lock， flags);
... critical section that only reads the info ...
read_unlock_irqrestore(&xxx_lock， flags);
write_lock_irqsave(&xxx_lock， flags);
... read and write exclusive access to the info ...
write_unlock_irqrestore(&xxx_lock， flags);
其實我們可以看到，它們的使用方式都是差不多的。在使用之前，先要宣告一個 rwlock_t 的變數，並將初始值設為 RW_LOCK_UNLOCKED， flags 還是一樣是用來存放 CPU flag 的值。如果你要去讀取資料結構的值，可以呼叫 read_lock_irqsave()，用完時則呼叫read_unlock_irqrestore()。至於當你要修改資料結構時，則呼叫 write_lock_irqsave()，修改完呼叫 write_unlock_irqrestore() 即可。
我們來看看read這組函式的原始碼是怎?樣子的：
#define read_lock_irqsave(lock， flags) do { local_irq_save(flags);
read_lock(lock); } while (0)
#define read_unlock_irqrestore(lock， flags) do { read_unlock(lock);
local_irq_restore(flags); } while (0)
這二個函式和 spin_lock_irqsave() 與 read_unlock_irqrestore() 的 差別只在於一個是呼叫 spin_lock() 與 spin_unlock()，另一個則是呼叫 read_lock() 與 read_unlock()。
我們再來看看 read_lock() 與 read_unlock() 這兩個函式，在 UP 環境底下是這個樣子的：
#define read_lock(lock) (void)(lock) /* Not "unused variable". */
#define read_unlock(lock) do { } while(0)
啊哈，跟 UP 底下的 spin_lock() 與 spin_unlock() 完全是一模一樣的，所以，事實上在 UP 的環境下，使用 rwlock 和 spinlock 是沒有差別的。其實，各位可以自己去看 write_lock_irqsave() 與 write_unlock_irqsave() 的程序，擴展開來跟上面兩組函式都是一樣的。原因其實很簡單，在 UP 的環境下，雖然 Linux 號稱多任務的系統，但由於只有一顆 CPU，在同一時間只有一個行程在執行，其它的行程都會被 suspend，唯一會中斷 Kernel 執行的只有 interrupt 了。所以，事實上，要做好 critical section 的保護只要暫時將中斷 disable 掉就行了。 Kernel 之所以要提 供上面這些函式其實是要給 SMP 的系統使用的，除此之外，它另一個用途就是增加 portability。 程序只要用 spinlock 來寫的話，那不管是在 SMP 或 UP 環境下都可以直接 compile 並執行，不用再重新修改程序碼。
至於 SMP 底下 rwlock 的實作方式我就不再贅述，基本上它們的實作方式都是差不多的，只有一點要特別說的是，由於 rwlock 可以容許多個 reader，但卻只能有一個 writer，所以，它不會只用到 rwlock_t.lock 的第 0 個 bit 而已。事實上，rwlock_t.lock 是個 32bit 的 unsigned int 型別的變數，因此，它用第 0 到 30 個 bit 當作 reader 的 counter，而第 31 個 bit 則是用來給 writer 使用的。當第 31 個 bit 為 1 時，表示目前 rwlock 被 writer 鎖住，此時前 30 個 bit 都應該是 0，表示此時沒有任何的 reader。因此，可以推斷 rwlock 同一時間最多可以有 2 的 30 次方個 reader。
第三種使用 spinlock 的方式
我們可以看到以上兩種的使用機制都是以 disable 中斷的方式來做的，雖然 disable 中斷很簡單，只要一個指令就行了，但事實上，這個指令的 cost 對 CPU 來講是蠻大的。所以， Kernel 還提供另一組的函式，它不 disable 中斷，所以，它的執行速度會比上面兩種來得有效率一些。 但是，上帝是公平的，它讓你速度快，相對的它也提供的某些限制。這個限制就是就如果你確定 interrupt handler 不會用到這個受保護的資料結構時，那你就可以考慮用這一組的函式， 以加快程序的執行。其實，這一組函式我們已經在上面見過了。
spin_lock(&lock);
...
spin_unlock(&lock);
就是 spin_lock() 和 spin_unlock() 這兩個函式。在上面我們已經見過這兩個函式展開的情形了， 在 UP 的環境裡，這兩個函式跟空的沒什?兩樣。但為何在UP底下，它們可以做到保護 critical section的作用呢？原因其實也講過了，因為在UP底下只有一個 CPU，所以，在同一時間只有一個行程在執行，除非行程自己放棄執行，不然只有 interrupt 會中斷其執行。剛才我們說過，使用這組函式的前提是在 interrupt handler 中不能使用到放在 critical section 中的資料結構。既然在 interrupt handler 中不會使用到，就算在 critical section 使用這個資料結構使用到一半，中斷突然發生，處理完中斷，CPU 還是會直接回來執行 critical section 的程序碼。所以，不會造成受保護的資料結構的不穩定。我們現在來看看，如果我們使用這組函式， 而且在 interrupt handler 中使用受保護的資料結構時會發生什?事。
spin_lock(&lock);
....
<------ interrupt
spin_lock(&lock);
...
spin_unlock(&lock)
在 UP 的的環境下，由於 spin_lock() 是空的，則當中斷發生時，很有可能行程使用資料結構到一半，中斷跑進來，也在使用它，造成這個資料結構的不穩定。如果是在SMP的環境下，由於 spin_lock() 是真的有在做事，所以當中斷發生時，如果這個中斷是發生在別的 CPU 上， 那就沒事，因為 spin_lock() 只會讓中斷發生的 CPU suspend 住而已。等原先的 CPU 執行完 spin_unlock() 它就可以恢復了，但是如果這時的中斷還是發生在原先的 CPU 上時，那在 interrupt handler 中，CPU 會一直被 suspend 住，直到 lock 被釋放為止。這就造成了一個 dead lock。因為這顆 CPU 現在已經被 lock 住，如何離開 interrupt handler 去呼叫 spin_unlock() 呢。
混合使用
針對 rwlock_t 這組函式除了上面提到的用法外，事實上，還是可以混合 spin_lock() 及 spin_unlock() 來使用的。由於 rwlock_t 可以允許多個 reader，所以如果在 interrupt handler 中只會讀取受保護的資料結構，而不會去修改它的話，那我們可以使用 spin_lock() 這組函式，但是當行程要修改資料結構時，還是得呼叫 write_spin_lock() 及 write_spin_unlock() 這組的函式。這樣既可以增加執行的效率，又可以確保重要資料結構的穩定性了。
結論
雖然在 UP 的環境中，保護重要的資料結構只要呼叫 cli() 和 sti() 就好，但是隨著 SMP 技術的成熟，相信 SMP 系統會逐漸的增加，為了讓自己寫的程序具有可移植性，善用 spinlock 這項機制相信會為未來省下相當修改程序碼的功夫。
前言
在 Linux Kernel 裡有著許多重要的資料結構，這些資料在作業系統的運作中扮演著舉足輕重的角色。然而，Linux 是個多任務的作業系統，也就是在同一時間裡可以同時有許多的行程在執行，所以，很有可能某個行程在依序讀取 inode list，同時卻又有另一個在 inode list 裡加入新的 inode，這會造成什?情形呢？這會造成 inode list 的不穩定。所以，在 Kernel 裡，我們需要一個機制，可以使得當我們在修改某個重要的資料結構時，不能被中斷，即使被中斷了，這個資料結構由於還沒修改完，別的行程也都不能去讀取和修改它。Linux Kernel提供了 spinlock 這個機制可以使我們做到這樣的功能。
有的人會想到當我們在修改某個重要的資料結構時，將中斷都 disable 掉就好了，等修改完了再將中斷 enable 不就得了，何必還要再提供一個 spinlock 來做同樣的事。在 uni-processor 的環境底下，的確是如此。所謂 uni-processor 就是指只有一個 CPU 的電腦，但是在SMP的環境下就不是這麼一回事了。
我們知道現在 Linux 已經有支持 SMP，也就是可以使用多顆 CPU 來加快系統的速度，如果當我們在修改重要的資料結構時，將執行修改工作的 CPU 中斷 disable 掉的話，只有目前的這個 CPU 的執行不會被中斷，在 SMP 環境下，還有別的 CPU 正同時運作，如果別的 CPU 也去修改這個資料結構的話，就會造成同時有兩個 CPU 在修改它，不穩定性就會產生。解決方法是將全部的 CPU 中斷都 disable 掉，等修改完之後，再全部都 enable 起來。但是這樣的做法其 cost 會很大，整個系統的效能會 down 下來。因此，Linux Kernel 才會提供 spinlock 這樣的機制，它不會將全部 CPU 的中斷 disable 掉，所以效率比上述的方法好，但同時卻又能確保資料的穩定性，不會有某個行程在修改它，另外又有一個行程在讀取或修改它的情形發生。
在這篇文章中，我將會介紹 Kernel 提供用來使用 spinlock 的 function。除此之外，我還會告訴各位，為何在 SMP 的環境裡，使用 spinlock 會比將所有 CPU 的中斷 disable 這個方法來的有效率，我也會告訴各位如何針對不同的使用需求，使 spinlock 的 cost 再降低，進而使系統的效能更好。
spinlock的資料結構
spinlock 的資料結構在 Linux底下是以 spinlock_t 來表示的，在 SMP 和 UP(uni-processor)環境底下兩者的欄位有一些差異，其實在 UP 底下 spinlock_t 可以說是一個空的結構，空就是空的，為何要說"可以說是空的"呢？這是因為 gcc 版本的問題，gcc 在 2.8 版以前結構的內容必須不能是空的，而在 2.8 版之後就可以，所以在 UP 環境底下，會根據 gcc 的版本而設定不同的 spinlock_t 結構欄位，但基本上，在 UP 環境底下，是根本不會用到 spinlock_t 結構裡的欄位的，詳情請見以下諸節即可瞭解。
由於 spinlock 主要是用在SMP的環境底下，所以，以下我們就只針對在SMP環境底下的 spinlock_t 結構來討論，它的結構內容是這樣子的：
typedef struct {
volatile unsigned int lock;
} spinlock t;
說穿了，不過就是一個 unsigned int 型別的變數而已，但可不要小看這小小的變數，螺絲釘雖小，功能卻是不可忽視的。
使用 spinlock
spinlock t xxx lock = SPIN_LOCK_UNLOCKED;
unsigned long flags;
spin lock irqsave (&xxx lock, flags)
...critical section...
spin unlock irqrestore (&xxx lock, flags)
這一組的函式在使用上是最保險的，用的頻率也算是最多的。首先在使用前，必須先宣告一個 spinlock_t 型別的變數，並把初始值設為 SPIN_LOCK_UNLOCKED。除此之外，還必須有一個unsigned long型別的變數，這個變數是用來將 CPU 的 flag（旗標）儲存起來的，等 critical section 執行完了，再把 flag 的值設回到系統裡。使用上是很簡單明白的。這兩個 function 除了可以在 SMP 的環境下使用外，在UP的環境裡也是同樣可行的，接下來，我們來看看它們程序碼是怎?寫的。
在 這個檔案裡定義了 spin_lock_irqsave() 及 spin_lock_irqrestore() 這兩個 function。
#define spin_lock_irqsave(lock，flags)
do { local_irq_save(flags); spin_lock(lock); } while (0)
#define spin_unlock_irqrestore(lock，flags)
do { spin_unlock(lock); local_irq_restore(flags); } while (0)
local_irq_save(flags) 做的事就是將 CPU 的 flag 值先儲存到 flags 變數里，然後將 CPU 的中斷 diable 掉。這裡將 CPU 的中斷 disable 是指將執行這段 code 的 CPU，並不是指全部的 CPU。 也就是說它只會 disable local CPU 的中斷。我們可以在裡看到這樣的程序碼：
#define local_irq_save(x) __asm__ __volatile__("pushfl ; popl %0 ;
cli":"=g" (x): /* no input */ :"memory")
#define local_irq_restore(x) __asm__ __volatile__("pushl %0 ; popfl"
/* no output */ :"g" (x):"memory")
至於 local_irq_restore(flags) 從字面上可以很清楚的看出來，只是將 flags 裡的值再設回 CPU 的 flag 裡而已。至於 spin_lock(lock) 和 spin_unlock(lock) 這兩個函式，在 SMP 和在 UP 的環境底下則會擴展成不同的樣子。首先先看到這個檔案的下半部。
#ifdef __SMP__
#include <asm/spinlock.h>
#else /* !SMP */
.......
#endif
在 SMP 的環境底下，SMP 這個constant被會 set。而在 UP 底下則不會，所以，如果要看 UP 底下 spin_lock(lock) 會變成怎?樣子，就必須來看看 #else /* !SMP */ 和 #endif 之間的程序碼。
UP 環境下的 Implementation
我們先來看看在 UP 的環境下， spin_lock(lock) 會變成什?樣子。
#define spin_lock(x) (void)lock
#define spin_unlock(x) do {} while(0)
簡單吧，根本什麼事都沒有做，所以，在 UP 的環境底下，我們如果將上面那段 spinlock 的使用擴展開來的話，會變成下面這個樣子。
spinlock_t xxx_lock = SPIN_LOCK_UNLOCKED;
unsigned long flags;
local_save_flags(flags); cli();
... critical section ...
local_restore_flags(flags);
而這也正是在 UP 環境下，用來保護重要資料結構的寫法。這也就是為什?在介紹spinlock_t 的結構內容時，我們說在UP環境底下這個結構就算是空的也不會影響到 spinlock 的功效，因為根本沒用到裡面的欄位，但是在 SMP 底下，這就很重要了。
SMP 環境下的 Implementation
在 SMP 的環境底下， spin_lock() 和 spin_unlock() 這兩個函式的原始碼是放在。
extern inline void spin_lock(spinlock_t *plock)
{
__asm__ __volatile__(
spin_lock_string
:"=m" (__dummy_lock(plock)));
}
其實，這段程序碼是經過我削減後的，至於削減掉的程序碼是用來做 debug 的，所以，就不列出來，有興趣的朋友不彷自行去看看。在上圖中，spin_lock_string 是一個 macro，加上 __asm 語法，我將它展開成下面這個樣子：
extern inline void spin_lock(spinlock_t *plock)
{
1:
lock ; btsl $0,plock;
jc 2f;
.section .text.lock,"ax"
2:
testb $1,plock;
rep;nop;
jne 2b;
jmp 1b;
.previous
}
讓我們來看看 spin_lock() 這段組合語言是什?意思。在 Linux 底下，組合語言是用 AT&T 的語法，跟平常我們在 PC 底下使用的 Microsoft 語法不相同，主要的差別是 source 與 destination 的位置相反。基本上，spinlock 有兩種狀態，第一種被鎖住的狀態（lock），第二種則是沒被鎖住的狀態（unlock）；當 spinlock 被鎖住時，spinlock_t.lock 會被設為 1，當沒被鎖時，則會設回 0，各位可以去看我們之前所列出來的使用方法，它會將 spinlock_t 結構的初始值設為 SPIN_LOCK_UNLOCK，現在再來看看這個 constant 的值，可以發現它其實就是將 spinlock_t.lock 設為 0 而已。
#define SPIN_LOCK_UNLOCKED (spinlock_t) { 0 }
所以，檢查其狀態就變成了 spin_lock() 的首要工作，如果已被鎖住，則 CPU 就不能去使用它所保護的資料結構，而如果沒上鎖，則可以從 spin_lock() 傳回，接下去使用它所保護的資料。所以，檢查其狀態我們可以檢查 spinlock_t.lock 的第 0 個 bit。btsl $0, plock 會將 plock 的第 0 個 bit 值傳到 flag 旗標的 carry 並把 plock 的第 0 個 bit 設為 1，其中 $0 是在 AT&T 語法中是指數字，也就是 immediate value。所以，再來只要檢查 carry 的值就可以了。當 carry 的值是 1 時，表示 spinlock 是上鎖狀態的，就跳到 label 2 的地方去執行，在程序碼裡，我們可以看到 jump 指令後面接著 2b，2f 及 1b 這些字眼，這些都是指 1: 或 2: 這些 label，如果某個 label 定在 jump 的前面，則指定label 時，要加上 b（backward），如果在後面，則加上 f（forward）。在 label 2 這段程序碼裡，它不停的做迴圈，執行 nop 指令，每次的迴圈都會去檢查一次 spinlock_t.lock 的值，當 spinlock 不是鎖住的狀態時，就會跳離迴圈，離開 spin_lock() 函式。
看完了 spin_lock()，再來看 spin_unlock() 就會發覺簡單多了。
#define spin_unlock(lock)
__asm__ __volatile__( spin_unlock_string
:"=m" (__dummy_lock(lock)))
其中，spin_unlock_string 一樣是個 macro，展開後變成下面這個樣子:
spin_unlock(plock)
｛
lock; btrl $0, plock;
}
btrl $0, plock 這一行會將 plock 的第 0 個 bit 設為 0，可以很清楚的看出來，spin_unlock() 只是將 plock 的第 0 個 bit 再設回 0 而已。在 spin_lock() 和 spin_unlock() 裡我們都可以看到 lock 這個指令在 btrl 或 btsl 的前頭，這個指令的用途是當 btrl 或 btsl 在修改 plock 的值時，其它別的行程都不能來修改 plock 的值，如果有別的行程企圖修改 plock 的值就會造成 exception 的發生。
看到這裡，各位應該可以瞭解 spinlock 的運作方式及其基本的使用方法了，接下來，我要跟各位介紹 spinlock 的另一種小小的變型，叫 read-write spinlock。
第二種的使用方式
有些資料結構是這樣子的，我們希望有人在修改它的內容時，別人都不能讀取或修改它，但是當沒有人在修改它時，可以同時有很多人去讀取它的內容。我們稱這樣的 spinlock 為 read-write spinlock。 Kernel 為它定義了 rwlock_t，放在 裡。使用方式是這樣子的。
rwlock_t xxx_lock = RW_LOCK_UNLOCKED;
unsigned long flags;
read_lock_irqsave(&xxx_lock， flags);
... critical section that only reads the info ...
read_unlock_irqrestore(&xxx_lock， flags);
write_lock_irqsave(&xxx_lock， flags);
... read and write exclusive access to the info ...
write_unlock_irqrestore(&xxx_lock， flags);
其實我們可以看到，它們的使用方式都是差不多的。在使用之前，先要宣告一個 rwlock_t 的變數，並將初始值設為 RW_LOCK_UNLOCKED， flags 還是一樣是用來存放 CPU flag 的值。如果你要去讀取資料結構的值，可以呼叫 read_lock_irqsave()，用完時則呼叫read_unlock_irqrestore()。至於當你要修改資料結構時，則呼叫 write_lock_irqsave()，修改完呼叫 write_unlock_irqrestore() 即可。
我們來看看read這組函式的原始碼是怎?樣子的：
#define read_lock_irqsave(lock， flags) do { local_irq_save(flags);
read_lock(lock); } while (0)
#define read_unlock_irqrestore(lock， flags) do { read_unlock(lock);
local_irq_restore(flags); } while (0)
這二個函式和 spin_lock_irqsave() 與 read_unlock_irqrestore() 的 差別只在於一個是呼叫 spin_lock() 與 spin_unlock()，另一個則是呼叫 read_lock() 與 read_unlock()。
我們再來看看 read_lock() 與 read_unlock() 這兩個函式，在 UP 環境底下是這個樣子的：
#define read_lock(lock) (void)(lock) /* Not "unused variable". */
#define read_unlock(lock) do { } while(0)
啊哈，跟 UP 底下的 spin_lock() 與 spin_unlock() 完全是一模一樣的，所以，事實上在 UP 的環境下，使用 rwlock 和 spinlock 是沒有差別的。其實，各位可以自己去看 write_lock_irqsave() 與 write_unlock_irqsave() 的程序，擴展開來跟上面兩組函式都是一樣的。原因其實很簡單，在 UP 的環境下，雖然 Linux 號稱多任務的系統，但由於只有一顆 CPU，在同一時間只有一個行程在執行，其它的行程都會被 suspend，唯一會中斷 Kernel 執行的只有 interrupt 了。所以，事實上，要做好 critical section 的保護只要暫時將中斷 disable 掉就行了。 Kernel 之所以要提 供上面這些函式其實是要給 SMP 的系統使用的，除此之外，它另一個用途就是增加 portability。 程序只要用 spinlock 來寫的話，那不管是在 SMP 或 UP 環境下都可以直接 compile 並執行，不用再重新修改程序碼。
至於 SMP 底下 rwlock 的實作方式我就不再贅述，基本上它們的實作方式都是差不多的，只有一點要特別說的是，由於 rwlock 可以容許多個 reader，但卻只能有一個 writer，所以，它不會只用到 rwlock_t.lock 的第 0 個 bit 而已。事實上，rwlock_t.lock 是個 32bit 的 unsigned int 型別的變數，因此，它用第 0 到 30 個 bit 當作 reader 的 counter，而第 31 個 bit 則是用來給 writer 使用的。當第 31 個 bit 為 1 時，表示目前 rwlock 被 writer 鎖住，此時前 30 個 bit 都應該是 0，表示此時沒有任何的 reader。因此，可以推斷 rwlock 同一時間最多可以有 2 的 30 次方個 reader。
第三種使用 spinlock 的方式
我們可以看到以上兩種的使用機制都是以 disable 中斷的方式來做的，雖然 disable 中斷很簡單，只要一個指令就行了，但事實上，這個指令的 cost 對 CPU 來講是蠻大的。所以， Kernel 還提供另一組的函式，它不 disable 中斷，所以，它的執行速度會比上面兩種來得有效率一些。 但是，上帝是公平的，它讓你速度快，相對的它也提供的某些限制。這個限制就是就如果你確定 interrupt handler 不會用到這個受保護的資料結構時，那你就可以考慮用這一組的函式， 以加快程序的執行。其實，這一組函式我們已經在上面見過了。
spin_lock(&lock);
...
spin_unlock(&lock);
就是 spin_lock() 和 spin_unlock() 這兩個函式。在上面我們已經見過這兩個函式展開的情形了， 在 UP 的環境裡，這兩個函式跟空的沒什?兩樣。但為何在UP底下，它們可以做到保護 critical section的作用呢？原因其實也講過了，因為在UP底下只有一個 CPU，所以，在同一時間只有一個行程在執行，除非行程自己放棄執行，不然只有 interrupt 會中斷其執行。剛才我們說過，使用這組函式的前提是在 interrupt handler 中不能使用到放在 critical section 中的資料結構。既然在 interrupt handler 中不會使用到，就算在 critical section 使用這個資料結構使用到一半，中斷突然發生，處理完中斷，CPU 還是會直接回來執行 critical section 的程序碼。所以，不會造成受保護的資料結構的不穩定。我們現在來看看，如果我們使用這組函式， 而且在 interrupt handler 中使用受保護的資料結構時會發生什?事。
spin_lock(&lock);
....
<------ interrupt
spin_lock(&lock);
...
spin_unlock(&lock)
在 UP 的的環境下，由於 spin_lock() 是空的，則當中斷發生時，很有可能行程使用資料結構到一半，中斷跑進來，也在使用它，造成這個資料結構的不穩定。如果是在SMP的環境下，由於 spin_lock() 是真的有在做事，所以當中斷發生時，如果這個中斷是發生在別的 CPU 上， 那就沒事，因為 spin_lock() 只會讓中斷發生的 CPU suspend 住而已。等原先的 CPU 執行完 spin_unlock() 它就可以恢復了，但是如果這時的中斷還是發生在原先的 CPU 上時，那在 interrupt handler 中，CPU 會一直被 suspend 住，直到 lock 被釋放為止。這就造成了一個 dead lock。因為這顆 CPU 現在已經被 lock 住，如何離開 interrupt handler 去呼叫 spin_unlock() 呢。
混合使用
針對 rwlock_t 這組函式除了上面提到的用法外，事實上，還是可以混合 spin_lock() 及 spin_unlock() 來使用的。由於 rwlock_t 可以允許多個 reader，所以如果在 interrupt handler 中只會讀取受保護的資料結構，而不會去修改它的話，那我們可以使用 spin_lock() 這組函式，但是當行程要修改資料結構時，還是得呼叫 write_spin_lock() 及 write_spin_unlock() 這組的函式。這樣既可以增加執行的效率，又可以確保重要資料結構的穩定性了。
結論
雖然在 UP 的環境中，保護重要的資料結構只要呼叫 cli() 和 sti() 就好，但是隨著 SMP 技術的成熟，相信 SMP 系統會逐漸的增加，為了讓自己寫的程序具有可移植性，善用 spinlock 這項機制相信會為未來省下相當修改程序碼的功夫。
2006年3月9日 星期四
#pragma pack()之用法
#pragma是用來設定complier的選項，跟你在complier後加 -Zp -Xk 等等設定
是一樣的。
#pragma pack(n)是用來讓struct的成員對齊記憶體用的，在32bit系統
下基於處理器效率的考量，預設的對齊位置是4 bytes，所以所有的struct成員視為
#pragma pack(4)，但有時候我們希望struct裡成員是連績的，尤其是控制硬體相關
的io位置，所以會設為#paragma pack(1)，讓struct的成員不要對齊。
看以下例子：
struct pci_conf {
WORD VendorID;
WORD DeviceID;
...
} pci;
如果沒有用#pragma pack(1)，VendorID後會空2 bytes不用，以便對到4 bytes
(假設一開始是對齊的)，然後才配置DeviceID。
可是若沒留意這樣的問題，
(BYTE*) p = &pci;
預期*(p+0x2)是DeviceID就會出問題。
如果你只有某一塊要特殊的alignement
#pragma pack(push, n)...#pragma pack(pop)
是一樣的。
#pragma pack(n)是用來讓struct的成員對齊記憶體用的，在32bit系統
下基於處理器效率的考量，預設的對齊位置是4 bytes，所以所有的struct成員視為
#pragma pack(4)，但有時候我們希望struct裡成員是連績的，尤其是控制硬體相關
的io位置，所以會設為#paragma pack(1)，讓struct的成員不要對齊。
看以下例子：
struct pci_conf {
WORD VendorID;
WORD DeviceID;
...
} pci;
如果沒有用#pragma pack(1)，VendorID後會空2 bytes不用，以便對到4 bytes
(假設一開始是對齊的)，然後才配置DeviceID。
可是若沒留意這樣的問題，
(BYTE*) p = &pci;
預期*(p+0x2)是DeviceID就會出問題。
如果你只有某一塊要特殊的alignement
#pragma pack(push, n)...#pragma pack(pop)
2006年2月20日 星期一
《陣列》多維動態陣列
《陣列》多維動態陣列
多維動態陣列在 C 中 大概只能用 malloc，但這在一維時尚
不構成問題，但需要多維陣列時怎麼辦呢？這算是程式論壇
最常被問到的問題之一了。
我把它整理了相關的回覆，都只用二維做說明，更多維的陣列
類推即可。
就從 C 談起吧！
動態產生一個[m][n]陣列 Array 的方法
code:------------------------------------------------------------------
int i;
int **Array;
Array= (int **)malloc(m*sizeof(void *));
for (i=0; i<m; i++)
Array=(int *)malloc(n*sizeof(int *));
--------------------------------------------------------------------------
這樣你就有一個 int Array[m][n]; 可以用了
是C 喔！不是 C++
但這不夠好，若你要的是一個較大的mXn陣列，那麼太多的malloc
會使記憶體碎片化(memory fragment)！沒關係，窮則變，變則通！
問題既出在for loop不斷的 memory allocation，就從那兒下手：
code:---------------------------------------------------------------------
int i;
int **Array, *pData;
Array= (int **)malloc(m*sizeof(int *));
pData= (int *)malloc(m*n*sizeof(int));
for (i=0; i<m; i++, pData+=n)
Array[i]=pData;
---------------------------------------------------------------------------
注意到嗎？這次只用了二次的malloc。
當要release memory也只要free Array[0] 和 Array 就成了！
(注意先free Array[0] 再 free Array)
如果嫌兩個alloc/free還是太多，也可簡單併成一個：
code:-----------------------------------------------------------------------
int i;
int **Array, *pData;
Array= (int **)malloc(m*sizeof(int *)+m*n*sizeof(int));
for (i=0,pData= (int *)(Array+m); i<m; i++, pData+=n)
Array[i]=pData;
----------------------------------------------------------------------------
要 free 時只要 free Array 就行了，帥吧？
如果用的是C++，那可用的方法就更多了！
《幼幼班》嘗試錯誤的階段
?> int Array[][] = new int [10][20];//這樣行ㄇ？
當然不行！ int Array[][]不是一個指標，而且只能有
一維為不定大小。
《小班》終於會從1數到100了
?> 那...
?> int *Array[] = new int [10][20];//這樣行ㄇ？
有點想法了！但可惜的是 '*' 在 C++的語法是修飾前面的
識別字，所以 int *Array[]的意思是 "Array是一個 int 指標
的一維陣列！"
如果能使那個 '*' 以獨立指標型態去宣告Array，就會變成
"Array是一個指標，指向一維 int 的陣列"，而我們知道指標
本身就可以當做一維的陣列，那麼是不是就成了"Array是一個二維
的int陣列"？
對了！這正是我們要的！問題是怎麼讓'*'成為獨立指標型態，
不會去修飾前面的int識別字？答案是使用括號：
int (*Array)[20] = new int [10][20];//這是正解！
但問題又來了， new 運算子可以使用 new int [m][n]，但
int (*Array)[20] 的 [20]卻沒辦法以 [n] 來取代，所以就
沒辦法做到不定大小的宣告了。所以這只能算是小班的答案，
要做到不定大小的動態多維宣告，加上 STL 的運用，是不錯
的想法。
《中班》vector 模板的運用
vector<int> *array=new vector<int>[m];
for (int i=0; i<n; i++) array[i].reserve(n);
嘿嘿...不錯吧！？不定大小的二維陣列，而且每個維度還
可以隨時調整大小喔！
不過還是有缺點ㄟ！！那行 for loop 看起來有點礙眼，不能
拿掉嗎？拿掉的話，基本上Array 還是二維陣列，但第二維
並沒有預留空間放東西你可以用push.back等成員函式來增加
空間和存放data，但不能在還沒有空間時使用像
array[5][3]=3; 這種陣列的存取方式。沒更好的方法了嗎？
vector 不是有預留空間大小的建構子嗎？像一維的宣告：
vector<int> *Array= new vector <int>(n);
//這不是預留了 n 個元素的陣列了嗎？
只可惜，這是一維的宣告，若你嘗試做這樣的宣告：
vector<int> *Array= new vector <int>[m](n);
編譯器會給你無情的嘲諷：陣列不能呼叫帶參數的建構子！
這是很令人失望的！為十麼不行？不是邏輯的問題，或許下
一版本的C++會可以這樣宣告吧！但為今之計只能自力救濟
了。
《大班》使用模板在模版中
仔細觀察下面的宣告：
vector<vector<int> > Array(m, vector<int>(n));
多維動態陣列在 C 中 大概只能用 malloc，但這在一維時尚
不構成問題，但需要多維陣列時怎麼辦呢？這算是程式論壇
最常被問到的問題之一了。
我把它整理了相關的回覆，都只用二維做說明，更多維的陣列
類推即可。
就從 C 談起吧！
動態產生一個[m][n]陣列 Array 的方法
code:------------------------------------------------------------------
int i;
int **Array;
Array= (int **)malloc(m*sizeof(void *));
for (i=0; i<m; i++)
Array=(int *)malloc(n*sizeof(int *));
--------------------------------------------------------------------------
這樣你就有一個 int Array[m][n]; 可以用了
是C 喔！不是 C++
但這不夠好，若你要的是一個較大的mXn陣列，那麼太多的malloc
會使記憶體碎片化(memory fragment)！沒關係，窮則變，變則通！
問題既出在for loop不斷的 memory allocation，就從那兒下手：
code:---------------------------------------------------------------------
int i;
int **Array, *pData;
Array= (int **)malloc(m*sizeof(int *));
pData= (int *)malloc(m*n*sizeof(int));
for (i=0; i<m; i++, pData+=n)
Array[i]=pData;
---------------------------------------------------------------------------
注意到嗎？這次只用了二次的malloc。
當要release memory也只要free Array[0] 和 Array 就成了！
(注意先free Array[0] 再 free Array)
如果嫌兩個alloc/free還是太多，也可簡單併成一個：
code:-----------------------------------------------------------------------
int i;
int **Array, *pData;
Array= (int **)malloc(m*sizeof(int *)+m*n*sizeof(int));
for (i=0,pData= (int *)(Array+m); i<m; i++, pData+=n)
Array[i]=pData;
----------------------------------------------------------------------------
要 free 時只要 free Array 就行了，帥吧？
如果用的是C++，那可用的方法就更多了！
《幼幼班》嘗試錯誤的階段
?> int Array[][] = new int [10][20];//這樣行ㄇ？
當然不行！ int Array[][]不是一個指標，而且只能有
一維為不定大小。
《小班》終於會從1數到100了
?> 那...
?> int *Array[] = new int [10][20];//這樣行ㄇ？
有點想法了！但可惜的是 '*' 在 C++的語法是修飾前面的
識別字，所以 int *Array[]的意思是 "Array是一個 int 指標
的一維陣列！"
如果能使那個 '*' 以獨立指標型態去宣告Array，就會變成
"Array是一個指標，指向一維 int 的陣列"，而我們知道指標
本身就可以當做一維的陣列，那麼是不是就成了"Array是一個二維
的int陣列"？
對了！這正是我們要的！問題是怎麼讓'*'成為獨立指標型態，
不會去修飾前面的int識別字？答案是使用括號：
int (*Array)[20] = new int [10][20];//這是正解！
但問題又來了， new 運算子可以使用 new int [m][n]，但
int (*Array)[20] 的 [20]卻沒辦法以 [n] 來取代，所以就
沒辦法做到不定大小的宣告了。所以這只能算是小班的答案，
要做到不定大小的動態多維宣告，加上 STL 的運用，是不錯
的想法。
《中班》vector 模板的運用
vector<int> *array=new vector<int>[m];
for (int i=0; i<n; i++) array[i].reserve(n);
嘿嘿...不錯吧！？不定大小的二維陣列，而且每個維度還
可以隨時調整大小喔！
不過還是有缺點ㄟ！！那行 for loop 看起來有點礙眼，不能
拿掉嗎？拿掉的話，基本上Array 還是二維陣列，但第二維
並沒有預留空間放東西你可以用push.back等成員函式來增加
空間和存放data，但不能在還沒有空間時使用像
array[5][3]=3; 這種陣列的存取方式。沒更好的方法了嗎？
vector 不是有預留空間大小的建構子嗎？像一維的宣告：
vector<int> *Array= new vector <int>(n);
//這不是預留了 n 個元素的陣列了嗎？
只可惜，這是一維的宣告，若你嘗試做這樣的宣告：
vector<int> *Array= new vector <int>[m](n);
編譯器會給你無情的嘲諷：陣列不能呼叫帶參數的建構子！
這是很令人失望的！為十麼不行？不是邏輯的問題，或許下
一版本的C++會可以這樣宣告吧！但為今之計只能自力救濟
了。
《大班》使用模板在模版中
仔細觀察下面的宣告：
vector<vector<int> > Array(m, vector<int>(n));
memory aligment
對一個 16位元的系統來說，意味著，系統有16條data bus，各能存取一個
bit資料。
16位元當然就是2bytes,正如我們2個一數，數數會是2,4,6,8一樣，address
也不會(也不需要)出現奇數位置1,3,5,7...
現在來看看硬體存取一個byte在奇偶數地址的情況：
1.
要取偶數位置E時，會抓到 (E,E+1)一個WORD(因為data bus是16bits)，
因為E是在Lo Byte 所以硬體只要把 Hi Bytes 拋棄掉就成了。
2.
要取奇數位置O時，會抓到 (O-1,O)一個WORD(因為data bus
是16bits)， 因為O是在Hi Byte 所以硬體得要把 Hi Bytes 搬到 Lo Bytes
才能算完成存取。
看到奇數地址存取會比偶數地址麻煩了嗎？差一點點而已有什麼關係？
好吧！我們再來看看硬體存取一個WORD在奇偶數地址的情況：
3.
要取偶數位置(E,E+1)時，會抓到 (E,E+1)一個WORD，這樣就完成
存取了。
4.
要取奇數位置(O,O+1)時，要先抓到 (O-1,O)取得Lo Byte O，然後
再抓(O,O+1)得到 Hi Byte(O+1)，最後合併(O,O+1)才算完成一個奇數
位址WORD的存取。
比較一下3,4，你就不會說只差一點點了吧！？
在32位元和64位元的系統，可以類推。這也是為什麼很多編譯器會預設
把變數位置調整在 2/4/8 倍數上來得到較佳的存取效率。
但這樣做會使像結構的資料大小意外的變化，若是某個結構的大小是很重要
的，你就必需找出編譯器相關的設定或directive(如VC的pack)來控制
aligment。
bit資料。
16位元當然就是2bytes,正如我們2個一數，數數會是2,4,6,8一樣，address
也不會(也不需要)出現奇數位置1,3,5,7...
現在來看看硬體存取一個byte在奇偶數地址的情況：
1.
要取偶數位置E時，會抓到 (E,E+1)一個WORD(因為data bus是16bits)，
因為E是在Lo Byte 所以硬體只要把 Hi Bytes 拋棄掉就成了。
2.
要取奇數位置O時，會抓到 (O-1,O)一個WORD(因為data bus
是16bits)， 因為O是在Hi Byte 所以硬體得要把 Hi Bytes 搬到 Lo Bytes
才能算完成存取。
看到奇數地址存取會比偶數地址麻煩了嗎？差一點點而已有什麼關係？
好吧！我們再來看看硬體存取一個WORD在奇偶數地址的情況：
3.
要取偶數位置(E,E+1)時，會抓到 (E,E+1)一個WORD，這樣就完成
存取了。
4.
要取奇數位置(O,O+1)時，要先抓到 (O-1,O)取得Lo Byte O，然後
再抓(O,O+1)得到 Hi Byte(O+1)，最後合併(O,O+1)才算完成一個奇數
位址WORD的存取。
比較一下3,4，你就不會說只差一點點了吧！？
在32位元和64位元的系統，可以類推。這也是為什麼很多編譯器會預設
把變數位置調整在 2/4/8 倍數上來得到較佳的存取效率。
但這樣做會使像結構的資料大小意外的變化，若是某個結構的大小是很重要
的，你就必需找出編譯器相關的設定或directive(如VC的pack)來控制
aligment。
新不定參數的 C 函式
只要寫過 C 程式的人，都用過 printf 這個函式，也都知道它可是一個
不定參數的函式，了解它的運作方式，你也可以實作自己的不定參數的
函式。
先看一下 printf 的原型：
int printf( const char *format [, argument]... );
在format後面的參數不但不定個數且型態也是不定的。
這些參數是one bye one 的堆在stack裡面。
printf這個函式如何正確的取出這些參數？
秘訣就在 format，函式根據format裡的格式("%d %f...")
依序把堆在stack裡的參數取出。而這取出的動作就是用到
va_arg, va_end, va_start這三個macro再加上va_list。
va_list 事實上是一個 char * 的型態：
typedef char * va_list;
其它的三個macro的例子(不同的平台會有不太一樣的macro)
/* A guess at the proper definitions for other platforms */
#define _INTSIZEOF(n) ( (sizeof(n) + sizeof(int) - 1) & ~(sizeof(int) - 1) )
#define va_start(ap,v) ( ap = (va_list)&v + _INTSIZEOF(v) )
#define va_arg(ap,t) ( *(t *)((ap += _INTSIZEOF(t)) - _INTSIZEOF(t)) )
#define va_end(ap) ( ap = (va_list)0 )
這三個macro若看得懂，對了解它們的運作會很有幫助；看不太懂也沒關係
，看一下下面的說明也差不可以了。
首先 va_start 把取出的指標(va_list)指到第一個不定參數。
然後就可以用 va_arg 以指定的型態從va_list取出資料並把va_list
指標移到下一個位置(例如取走了一個int 4 bytes 的資料， va_list便會加 4)
當取完資料後便可使用 va_end 把 va_list 歸零(這個macro應看得懂吧)。
其實對大部份的應用來說 va_end 做不做是沒太大的關係的。
下面是一個不定參數函式的範例(轉載自MSDN)：
int average( int first, ... )
{
int count = 0, sum = 0, i = first;
va_list marker;
va_start( marker, first ); /* Initialize variable arguments. */
while( i != -1 )
{
sum += i;
count++;
i = va_arg( marker, int);
}
va_end( marker ); /* Reset variable arguments. */
return( sum ? (sum / count) : 0 );
}
註：_INTSIZEOF 是 int size memory alignment，如果你不知那是什麼
就把 _INTSIZEOF 看成這樣的定義會比較容易理解：
#define _INTSIZEOF(n) sizeof(n)
為什麼不直接用sizeof(n)就好了，使用 macro 是為了跨平台時能保持運
作正確。若傳了一個2 bytrs的不定參數(如 short)，但在一個 32 bits的
平台推入堆疊就會是4個bytes(32 bits)不是2 bytes，所以參數的取出
就要非常的小心。使用_INTSIZEOF 在於保證引數指標移動的正確。
#define _INTSIZEOF(n) ( (sizeof(n) + sizeof(int) - 1) & ~(sizeof(int) - 1) )
令N=sizeof(n)+sizeof (int)-1
X=sizeof()int
若X為2之倍數
_INTSIZEOF(n)可簡化為N&~(X-1)
而原式為N-N%X，以下證明
N&~(X-1)=N-N%X
IF X=1
N&~(1-1)=N&~(0xFFFF..F)=N-N%1
IF X=2
N&~(2-1)=N&~(0xFFFF...FE)=N-N%2
IF X=4
N&~(4-1)=N&~(0xFFFF...FC)=N-N%4
目的為了讓_INTSIZEOF(n)成為X之倍數，也就是sizeof(int)之倍數
不定參數的函式，了解它的運作方式，你也可以實作自己的不定參數的
函式。
先看一下 printf 的原型：
int printf( const char *format [, argument]... );
在format後面的參數不但不定個數且型態也是不定的。
這些參數是one bye one 的堆在stack裡面。
printf這個函式如何正確的取出這些參數？
秘訣就在 format，函式根據format裡的格式("%d %f...")
依序把堆在stack裡的參數取出。而這取出的動作就是用到
va_arg, va_end, va_start這三個macro再加上va_list。
va_list 事實上是一個 char * 的型態：
typedef char * va_list;
其它的三個macro的例子(不同的平台會有不太一樣的macro)
/* A guess at the proper definitions for other platforms */
#define _INTSIZEOF(n) ( (sizeof(n) + sizeof(int) - 1) & ~(sizeof(int) - 1) )
#define va_start(ap,v) ( ap = (va_list)&v + _INTSIZEOF(v) )
#define va_arg(ap,t) ( *(t *)((ap += _INTSIZEOF(t)) - _INTSIZEOF(t)) )
#define va_end(ap) ( ap = (va_list)0 )
這三個macro若看得懂，對了解它們的運作會很有幫助；看不太懂也沒關係
，看一下下面的說明也差不可以了。
首先 va_start 把取出的指標(va_list)指到第一個不定參數。
然後就可以用 va_arg 以指定的型態從va_list取出資料並把va_list
指標移到下一個位置(例如取走了一個int 4 bytes 的資料， va_list便會加 4)
當取完資料後便可使用 va_end 把 va_list 歸零(這個macro應看得懂吧)。
其實對大部份的應用來說 va_end 做不做是沒太大的關係的。
下面是一個不定參數函式的範例(轉載自MSDN)：
int average( int first, ... )
{
int count = 0, sum = 0, i = first;
va_list marker;
va_start( marker, first ); /* Initialize variable arguments. */
while( i != -1 )
{
sum += i;
count++;
i = va_arg( marker, int);
}
va_end( marker ); /* Reset variable arguments. */
return( sum ? (sum / count) : 0 );
}
註：_INTSIZEOF 是 int size memory alignment，如果你不知那是什麼
就把 _INTSIZEOF 看成這樣的定義會比較容易理解：
#define _INTSIZEOF(n) sizeof(n)
為什麼不直接用sizeof(n)就好了，使用 macro 是為了跨平台時能保持運
作正確。若傳了一個2 bytrs的不定參數(如 short)，但在一個 32 bits的
平台推入堆疊就會是4個bytes(32 bits)不是2 bytes，所以參數的取出
就要非常的小心。使用_INTSIZEOF 在於保證引數指標移動的正確。
#define _INTSIZEOF(n) ( (sizeof(n) + sizeof(int) - 1) & ~(sizeof(int) - 1) )
令N=sizeof(n)+sizeof (int)-1
X=sizeof()int
若X為2之倍數
_INTSIZEOF(n)可簡化為N&~(X-1)
而原式為N-N%X，以下證明
N&~(X-1)=N-N%X
IF X=1
N&~(1-1)=N&~(0xFFFF..F)=N-N%1
IF X=2
N&~(2-1)=N&~(0xFFFF...FE)=N-N%2
IF X=4
N&~(4-1)=N&~(0xFFFF...FC)=N-N%4
目的為了讓_INTSIZEOF(n)成為X之倍數，也就是sizeof(int)之倍數
memcpy 跟strcpy 用法上的差別
strcpy()只能透過零結尾來判定結束，所以有以下的缺點：
1. 速度慢，因為只能以BYTE為單位執行拷貝。
2. 容易出現overlay/memory-corruption，這有兩個情況，一個是目標緩衝區太小了，另一個是來源忘了零結尾。
3. 重疊的情況時，拷貝會出錯。
char *strcpy( char *strDestination, const char *strSource )
把 strSource copy 到strDestination
因為C 的字串結束是用 0 所以. strcpy 作法是把strSource 中的資料一個一個設定strDestination 一直到0
程式大概是這樣子
while( (*strSource) != 0 )
{
*strDestination =*strSource;
++strDestination;
++strSource;
};
*strDestination=0;
void *memcpy( void *dest, const void *src, size_t count );
把src copy 到dest . 一共copy count 個byte
注意 count 個byte 是一定要給的.
程式大概是這樣寫的
const unsigned char *pSrc=src;
unsigned char *pDest=dest;
for( size_t i=0 ; i < count ; ++i,++pSrc,++pDest)
*pDest=*pSrc;
1. 速度慢，因為只能以BYTE為單位執行拷貝。
2. 容易出現overlay/memory-corruption，這有兩個情況，一個是目標緩衝區太小了，另一個是來源忘了零結尾。
3. 重疊的情況時，拷貝會出錯。
char *strcpy( char *strDestination, const char *strSource )
把 strSource copy 到strDestination
因為C 的字串結束是用 0 所以. strcpy 作法是把strSource 中的資料一個一個設定strDestination 一直到0
程式大概是這樣子
while( (*strSource) != 0 )
{
*strDestination =*strSource;
++strDestination;
++strSource;
};
*strDestination=0;
void *memcpy( void *dest, const void *src, size_t count );
把src copy 到dest . 一共copy count 個byte
注意 count 個byte 是一定要給的.
程式大概是這樣寫的
const unsigned char *pSrc=src;
unsigned char *pDest=dest;
for( size_t i=0 ; i < count ; ++i,++pSrc,++pDest)
*pDest=*pSrc;
2006年2月8日 星期三
volatile宣告
volatile unsigned int SlotStart : 4;
volatile不要對這個變數做最佳化
對於一個 address 的值, 如果有可能在其它地方被修改, 例如 被其它 thread 修改, 或是 硬體I/O 修改, 為了要確定讀到的是最新值, 就必需要用 volatile.
volatile不要對這個變數做最佳化
對於一個 address 的值, 如果有可能在其它地方被修改, 例如 被其它 thread 修改, 或是 硬體I/O 修改, 為了要確定讀到的是最新值, 就必需要用 volatile.
訂閱：
文章 (Atom)