2015年3月4日 星期三

[Linux Kernel] ACCESS_ONCE Macro

最近看Kernel code,看到這個ACCESS_ONCE巨集,仔細看了它的定義發現挺有趣的,順便記錄一下。 

ACCESS_ONCE顧名思義,就是確實地讀取所指定記憶體位址的內容值,且僅限這一次。所以在這個巨集肯定有volatile關鍵字,其原始定義如下:

 #define ACCESS_ONCE(x) (*(volatile typeof(x) *)&(x))  

使用情境
底下程式碼擷取於kernel/locking/mutex.c (linux-v4.0-rc1)
 while (true) {  
     struct task_struct *owner;  
     ...  
     /*  
      * If there's an owner, wait for it to either  
      * release the lock or go to sleep.  
      */  
     owner = ACCESS_ONCE(lock->owner);  
     if (owner && !mutex_spin_on_owner(lock, owner))  
         break;  
     ...  

然而,如果沒有加入ACCESS_ONCE macro,程式碼如下:
 while (true) {  
     struct task_struct *owner;  
     ...  
     /*  
      * If there's an owner, wait for it to either  
      * release the lock or go to sleep.  
      */  
     owner = lock->owner;  
     if (owner && !mutex_spin_on_owner(lock, owner))  
         break;  
     ...  

由於,編譯器優化關係[1]發現"owner = lock->owner"在這個while loop沒有被更改,所以編譯器把這行程式碼放到while loop外面,如此不用每次都實際地讀取lock->owner,其程式碼變成:
 struct task_struct *owner;  
   
 owner = lock->owner;  
 while (true) {  
     ...  
     if (owner && !mutex_spin_on_owner(lock, owner))  
         break;  
     ...  
   

問題來了,"lock->owner"有可能被其它task修改,如此造成資料不一致。
因此使用ACCESS_ONCE可以防止編譯器做相關優化工作,並確保每次都能到實體記憶體位址讀取。其做法便是將某參數暫時性地轉換成具volatile型態。如此,存取該參數在非引入ACESS_ONCE macro的地方 (不具volatile特性),仍可享用編譯器優化的好處。

延伸閱讀
2014 11月 Christian Borntraeger在lkml提出ACCESS_ONCE用gcc 4.6/4.7編繹所造成的問題,詳見compiler bug gcc4.6/4.7 with ACCESS_ONCE and workarounds。其問題在於: 如果所傳入的參數是non-scalar型態,gcc 4.6/4.7會把volatile關鍵字自動拿掉,如下程式碼:
 typedef struct {  
     unsigned long pte;  
 } pte_t;  
   
 pte_t pte;  
   
 pte_t p = ACCESS_ONCE(pte);  
   

上述程式碼 (存取struct) 可能被編譯器優化 (因為gcc 4.6/4.7針對non-scalar型態會自動地去掉volatile)。

最直覺的解法就是存取scalar-type的參數,如下所示:
 unsigned long p = ACCESS_ONCE(pte->pte);  

但此方法需要更改所有使用ACCESS_ONCE的程式碼,這將是一件很無聊的工作。經過一番lkml討論,Christian決定更改ACCESS_ONCE (參照lkml patch set),其程式碼如下:

 #define __ACCESS_ONCE(x) ({ \  
      __maybe_unused typeof(x) __var = (__force typeof(x)) 0; \  
     (volatile typeof(x) *)&(x); })  
 #define ACCESS_ONCE(x) (*__ACCESS_ONCE(x))  

其解法就是限制ACCESS_ONCE只能傳入scalar type參數 (union也可以,不過,有些限制,詳見include/linux/compiler.h檔裡面的註解)。

如果傳入non-scalar type參數,會發生編繹錯誤。示範程式碼與編繹結果如下:
1:  #include <stdio.h>  
2:    
3:  #define __maybe_unused __attribute__((unused))  
4:    
5:  #define __ACCESS_ONCE(x) ({ \  
6:      __maybe_unused typeof(x) __var = 0; \  
7:      (volatile typeof(x) *)&(x); })  
8:    
9:  #define ACCESS_ONCE(x) (*__ACCESS_ONCE(x))  
10:    
11:  typedef struct {  
12:      unsigned long pte;  
13:  } pte_t;  
14:    
15:  int main(void)  
16:  {  
17:      pte_t pte;  
18:    
19:      ACCESS_ONCE(pte);  
20:    
21:      return 0;  
22:  }  
23:    

 $ gcc -o access_once access_once.c  
 access_once.c: In function ‘main’:  
 access_once.c:19:2: error: invalid initializer  
  ACCESS_ONCE(pte);  
  ^  
   

其出錯原因在於這段程式碼 "__maybe_unused typeof(x) __var = 0;",它限制所傳入參數必須為scalar type參數 (因為 "__var = 0")。如果傳入一結構型態,則必須"__var = {0}",才能避免編繹錯誤。只能說Linux Kernel好多程式藝術在裡面啊!!!!!

因此,如果要存取non-scalar type參數,請改用READ_ONCE與ASSIGN_ONCE,如此便能避免編繹錯誤。

在linux-4.0-rc1原始碼,__ACCESS_ONCE導入一新patch,用以這個編繹警告 "Using plain integer as NULL pointer",詳見lkml - kernel: Fix sparse warning for ACCESS_ONCE
 #define __ACCESS_ONCE(x) ({ \  
      __maybe_unused typeof(x) __var = (__force typeof(x)) 0; \  
     (volatile typeof(x) *)&(x); })  
 #define ACCESS_ONCE(x) (*__ACCESS_ONCE(x))  
   

[Reference]
ACCESS_ONCE()
ACCESS_ONCE() and compiler bugs


2012年3月8日 星期四

Redirecting standard output and standard error

formal form:
$ ifconfig eth100 > msg.log 2>&1


can be shortened like that:
$ ifconfig eth100 &> msg.log

or
$ ifconfig eth100 >& msg.log


【Reference】
Bash Reference Manual

2011年8月11日 星期四

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

記得大學時, 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

2011年8月5日 星期五

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

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

2011年7月26日 星期二

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

撰寫裝置驅動程式時, 常常會因為硬體需求, 需配置一塊記憶體空間用來映射至硬體的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變數做位元遮罩,如此便能取得正確的記憶體起始位址

下圖為詳細範例計算


2010年12月28日 星期二

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

今天在自己的Linux桌機 (Ubuntu 10.10) 幹了一件傻事:
$ sudo chown -R adrian.adrian /usr/
結果導致使用sudo會有底下的問題:
$ sudo su
sudo: must be setuid root
這下可high了, Ubuntu在安裝的時候並沒有讓管理者設定root密碼, 所以無法使用root登入, 沒有root權限什麼事都不能做啊! 底下解決方式:

  1. 重新啟動Ubuntu,在grub選單中選擇有recovery mode的選項, Ex: "Ubuntu, with Linux 2.6.35-23-server (recovery mode)"
  2. 以recovery模式開機後, 會出現"Recovery Menu"選單, 選擇"root Drop to root shell prompt"選項就可進入root shell prompt。
  3. 利用ls -l觀看sudo資訊,所以是擁有此程式使用者的問題。
    -rwxr-xr-x 2 adrian adrian 147872 2010-09-01 04:39 /usr/bin/sudo
  4. 執行底下指令便可大功告成:
    # chwon root:root /usr/bin/sudo
    # chmod 4755 /usr/bin/sudo
    # reboot
  5. 最後還是乖乖地把/usr/重新設定回root。
    $ sudo chown root.root /usr/

【Reference】
[1] Ubuntu forum

2010年12月21日 星期二

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

上篇文章僅介紹如何利用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

  1. 使用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
    
  2. 如第1點所述。
  3. 如第1點所述。
  4. 輸出Msg2,隨即使用lret指令返回LABEL_GDT_CODE。
  5. 通常,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
    
  6. 從Ring 0 (LABEL_GDT_CODE)返回 Ring 3 (LABEL_GDT_CODE_R3)。
  7. 此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欄位的原因。
  8. 跳至GDT之Call Gate的描述子 (Descriptor)。
  9. 根據Call Gate描述子的Segment Selector欄位找出對應的CS。
  10. 將Msg3輸出至螢幕並返回。
  11. 返回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