Spinlock

參考文章

• Synchronization primitives in the Linux kernel. Part 1.
• Linux内核的自旋锁

Spinlock 顧名思義，就是一直使用 CPU 不釋出，但在 Linux 中 Spinlock 是可以被中斷的，他在 Linux 中各版本的實作也不盡相同，讓我們從以下三個階段的修改，藉此了解 Spinlock 在近代的 Linux 中比較接近什麼概念

1. Spinlock
   最初的 Spinlock，每個 Thread 發起 Spinlock 時，並不給予對應的編號，沒有任何排序，無法預期是否是先要求 Spinlock 就能夠先得到
2. Ticket Spinlock
   按照要求 Spinlock 的順序排隊，先進先出(FIFO)，越早申請可以越早獲得 Lock
3. Queued Spinlock
   為了搭配 SMP(Symmetric Multi-Processing) 架構重新設計而成的機制，原先的實作是共同維護一個資料結構，但在 SMP 架構底下，若要共同維護一個資料結構，每顆 CPU 都要輪流查詢過一次該資料結構，是非常浪費資源的設計
   那什麼是 Queued Spinlock？核心設計概念是在每顆 CPU 都自行複製一個同樣的資料結構，這樣可以透過查詢自己所持有的資料結構，來降低訪查造成的消耗

MCS Spinlock

參考 MCS locks and qspinlocks

Spinlock 與 Ticket Spinlock 並不多作介紹，可以自行從字面上的意義推估一二，主要要介紹的點在於 Queued Spinlock，而 Queued Spinlock 的核心概念是從 MCS Lock 發展而成

• mcs_spinlock 的結構，其實就是一般 Linked List 的結構

struct mcs_spinlock {
    struct mcs_spinlock *next;
    int locked; /* 1 if lock acquired */
};

• 先有一個 mcs_spinlock ，稱他叫做 Main Lock
  

• CPU 1 嘗試獲得 Lock
  

CPU 1 自行建立了一個 mcs_spinlock 結構，然後與 Main Lock 執行原子交換(Atomic Exchange)，這個動作會把 next 指向的物件所持有的 locked 數值，儲存到自己結構中的 locked

原子交換(Atomic Exchange) 指的是不可中斷的交換，稍後再作介紹

在執行原子交換時，CPU 1 發現 Main Lock 中 next 指向的地址是 NULL ，這表示沒有人在使用 Lock ，如此就成功獲得鎖了

最後 locked 被寫入成 1，因為已經把 Lock 已經由 CPU 1 獲得，Main Lock 也將 next 指向 CPU 1

• CPU 2 嘗試獲得 Lock
  

跟之前一樣，對 Main Lock 執行原子交換，但他發現 Main Lock 已經指向 CPU 1 了，所以現在 CPU 2 中的 locked 數值變為 1，且他現在被鎖住了，無法動彈

MCS lock 的好處在這邊就體現出來了，每個 CPU 會針對各自結構中的 locked 數值進行 Spin

然後我們會再將 CPU 1 的 next 指向 CPU 2，這個是因為 Main Lock 永遠都會指向整個 Queue 的最末端，透過 CPU 1 指向 CPU 2 這個動作，我們就可以知道下一個 Lock 要給誰才對

• CPU 1 釋出 Lock
  

結束工作的時候，會跟 Main Lock 作原子交換，並把自己指向 NULL

Atomic Exchange 的一種方法就是指 CAS(Compare-and-Swap)

• CAS 的虛擬碼(參考 Wikipedia: 比較並交換)

int cas(long *addr, long old, long new)
{
    /* Executes atomically. */
    if(*addr != old)
        return 0;
    *addr = new;
    return 1;
}

確認 locked 數值是不是舊的數值，是的話就跟你交換，替換成 CPU 1 現在持有的數值

但在這個案例中，他不會動 Main Lock 所持有的 locked ，會直接跟自己的 next 作交換，這樣又省了一個步驟@@，如果要先跟 Main Lock 作交換，Main Lock 不就還要再去通知一次 CPU 2

總之，完成任務後，與自己的 next 作 CAS 操作，如果 next 指向 NULL ，則跟 Main Lock 作 CAS

Kernel 程式碼中的技巧

在開始閱讀 Queued Spinlock 原始碼之前，要先了解 Kernel 中常使用到的技巧，不然會看得很痛苦 ...... 熟悉程式碼的朋友，可以直接跳過這部份

• macro

參考 談Linux Kernel巨集 do{…}while(0) 的撰寫方式，這篇文章是參考 Linux kernel coding style，不過我是懶得看英文 ...

macro 這個東西，他會直接把程式碼複製到對應的位置，可以使用 gcc -E 進行編譯，執行成功後會得到展開所有 macro 的程式碼，複製貼上！？總之這會導致一些問題，以下有五點需要注意

1. 避免使用影響流程的語法，比如： return break
   比如：在迴圈中呼叫一個 macro ，但迴圈還沒完全執行，就離開迴圈了，如果不看到 macro 的程式碼，開發者並不知道他有這個能力，而 macro 也不該有這個能力

#define FOO(x)                                  \
        do {                                    \
                if (blah(x) < 0)                \
                        return -EBUGGERED;      \
        } while (0)

2. 避免使用 macro 中無法直接看到的變數，全域變數跟區域變數都不要，除了 macro 自帶的參數
   跟第一點是同樣的道理，只是現在把問題搬到了 macro 中，不看到呼叫 macro 的地方，根本不知道該變數長什麼樣子

#define FOO(val) bar(index, val)

3. macro 不要當作 l-value 作使用
   這個跟 inline 寫法有關，macro 只是前處理的部份，會直接把當成純文字複製貼上，但是 inline 是在 compile 階段的事情，你不能對一個 function 修改一個 function 的數值阿@@

#define FOO(val) val
inline int FOO(int val)
{
    return val;
}

int func()
{
    int x = 10;
    FOO(x) += 30;
    return x;
}

4. 務必要使用括號包裝運算式或者變數
   如果沒有正確的把 macro 中的變數括號起來，展開後可是會悲劇的，可以思考以下範例執行結果為何

#include <stdio.h>
#define SquareOf(x) x*x

int main()
{
    int vBase=7;
    
    printf("vBase = %d and define SquareOf(x) = x*x\n", vBase);
    printf("SquareOf(vBase) = %d\n", SquareOf(vBase));
    printf("SquareOf(vBase+1) = %d\n", SquareOf(vBase+1));
    printf("SquareOf(vBase+vBase) = %d\n", SquareOf(vBase + vBase));
    
    return 0;
}

正確的寫法

#define SquareOf(x) ((x)*(x))

5. namespace collision
   以下這段程式碼有蠻多重點的
   • typeof 是一個 GCC 的語法，可以讓你寫起來像是在寫 C++ 的 Templeate ......
   • 大掛號的部份，就是為了處理 ret 這個變數名字，因為這實在太常見了，透過這種方式，他可以被包裝成 __foo_ret

#include <stdio.h>
#define FOO(x)                          \
({                                      \
        typeof(x) ret;                  \
        ret = square(x);              \
        (ret);                          \
})

int square(int x) {
    return x*x;
}

int main()
{
    int x = 2;
    printf("%d\n", FOO(x));
    // 展開後長這樣
    // printf("%d\n", ({ typeof(x) ret; ret = square(x); (ret); }));
    
    return 0;
}

最後講一下 macro 中常常使用 do{…}while(0) 的方法宣告，為什麼不直接寫就好呢？這是為了確保 macro 在 if/else 判斷式中的正確性，不會因為展開後邏輯就爆炸了，一切都是因為 macro 只是單純的文字複製貼上啦

• volatile
  參考 C 語言 setjmp 與 longjmp 函數用法教學

volatile 是指避免 Compiler 把這個變數作最佳化，將變數放置到暫存器中

• likely(), unlikely()

參考 likely() and unlikely()，這個是一個很詭異的設計，真的是為了極盡可能的優化效能而設計，這其實是 GCC 的 built-in function，用來提示編譯器，讓他知道這個數值比較可能是 1/0，這樣他比較能精準的進行 branch prediction，不過這個我懶得看到底是怎麼優化

likely() 表示這個數值比較可能接近 1
unlikely() 表示這個數值比較可能接近 0

• union

很多 struct 被宣告成 union 的形式，大多是為了 DEBUG 做準備

Others

除了以上一些小地方之外，還有兩個很難懂的部份要介紹 Memory Order 以及 Inline Assembly，而之後兩天我們先了解這兩個部份，才能比較輕易的閱讀 Kernel 中的程式碼

本系列文的重點並不在於解析每一行程式碼的意思，只是想要對 Linux 中的機制有所了解，並參照其實作從中學習