Linux核心實作筆記

1. 計算機編碼

符號與值(sign & magnitude)

計算機中以二進位作為資料的表示方式和儲存方式，符號則另存為另外一個bit來表示正負數，比如說:

10000001 -> -1
00000001 -> +1

最前面的1或0作為正負數的標示，後面則是數值的大小

此表示法的缺點就是0會有兩種表示方法，

10000000 -> -0
00000000 -> +0

並且在近行加法或減法時，加法時需要進行進位(carry)，減法時需要進行借位(borrow)，在現實生活中很難被實現，所以現今計算機不使用此編碼方式

一補數(Ones' complement)

一補數實際上只是將二進位中的1變成0，0變成1，讓負數可以用來作為減法的方法，比如說原本為:

1-2=-1

變成

1+(-2)=-1

從二進位的角度來看

    0001
+   1101      ->  1101為2的一補數 = -2
---------
    1110      ->  1110為1的一補數 = -1
此題答案即為-1

所以從以上運算可以看到上面是沒有進位的一補數運算，也看到一補數運算可以讓原本的減法變成加法，這樣可以讓正負號不需要多出一個bit來儲存它，下面則是需要進位的一補數算法

e.g
2+(-1)=1

    0010
+   1110      ->  1110為1的一補數 = -1
---------
 [1]0000
+      1      ->  多進了一位所以+1  
---------
       1
此題答案即為1

此表示法的的缺點在於遇到需要進位時要進行循環進位，但比起符號與值每個加法和減法都需要去比較是否要進位和借位簡單許多，但是0的表示法仍然有兩種，0000和1111

二補數(Two's complement)

二補數就是一補數再加上1，並且計算方式為最高位元為負數，其他皆為正數，這樣即可解決0有兩種表示方法的問題

0有兩種表示法
0000為+0
1111為0000的一補數-0

依照二補數的表示法
    1111
+   0001
---------
 [1]0000    ->  和0000相同
 
->0變成只有一種表示法

e.g
-6的二補數
= ~(0110) + 0001
= 1001 + 0001
= 1010
=> (-2)^3+2^1 = -6

參考資訊

解讀計算機編碼

2. C語言bit-wise operator

首先先了解三種bit-wise operator:|，&，^

以C語言實作二進位加法

| (OR) 運算子

input 1	input 2	output
0	0	0
0	1	1
1	0	1
1	1	1

& (AND) 運算子

input 1	input 2	output
0	0	0
0	1	0
1	0	0
1	1	1

^ (XOR) 運算子

input 1	input 2	output
0	0	0
0	1	1
1	0	1
1	1	0

英文大小寫轉換

深入理解二進位所編成的ascii碼後，發現我們可以使用bit-wise運算子來簡單的將大小轉換

• ascii 編碼表

以E轉換成e作為例子:
上表中E為69，e為101，轉為二進位

E = 0100 0101
e = 0110 0101

兩者差32，回去查表，32代表著空格(' ')，接著再加入bit-wise運算子看看會發生什麼

(E|' ') => e
(e|' ') => e

原因:
(E|' ')
=(0100 0101 | 0010 0000) = 0110 0101(e)


(E&' ') => E
(e&' ') => E

原因:
(E&' ')
=(0100 0101 & 0010 0000) = 0110 0101(E)


(E^' ') => e
(e^' ') => E

原因:
(E^' ')
=(0100 0101 ^ 0010 0000) = 0110 0101(e)

參考資訊

你所不知道的 C 語言: bitwise 操作

3. 並行程式設計

Question:
livelock?
promela?
ABA-problem?

Atomics Operations

主要概念為將每一個動作區分為沒辦法再分割的動作，常見的 Atomics Operations 有 Read-modify-write，Test-and-Set，Fetch-and-add 和 Compare-and-Swap

Compare-and-Swap

int CAS(int *a, int old_val, int new_val) {
    if (*a == old_val) {
        *a = new_val;
        return old_val;
    }
    return *a;
}

Test-and-Set

#define LOCKED 1

int test_and_set(int* lockPtr) {
    int oldValue;

    // -- Start of atomic segment --
    // This should be interpreted as pseudocode for illustrative purposes only.
    // Traditional compilation of this code will not guarantee atomicity, the
    // use of shared memory (i.e., non-cached values), protection from compiler
    // optimizations, or other required properties.
    oldValue = *lockPtr;
    *lockPtr = LOCKED;
    // -- End of atomic segment --

    return oldValue;
}

volatile 關鍵字和 Atomic operation 的關係

volatile 到底是什麼?

直接看 c 語言規格書 來看看 volatile 到底在幹嘛

Accessing a volatile object, modifying an object, modifying a file, or calling a function
that does any of those operations are all side effects, which are changes in the state of
the execution environment. Evaluation of an expression may produce side effects. At
certain specified points in the execution sequence called sequence points, all side effects
of previous evaluations shall be complete and no side effects of subsequent evaluations
shall have taken place.

在使用 volatile 時，需要注意的是會產生的 side effect，也就是說在執行的情況下遭到了未預期的改變，而 volatile 的作用在取原本的數值並且抑制編譯器的優化。在 Why the "volatile" type class should not be used 中也有提到:

The key point to understand with regard to volatile is that its purpose is
to suppress optimization, which is almost never what one really wants to
do. In the kernel, one must protect shared data structures against
unwanted concurrent access, which is very much a different task. The
process of protecting against unwanted concurrency will also avoid almost
all optimization-related problems in a more efficient way.

Like volatile, the kernel primitives which make concurrent access to data
safe (spinlocks, mutexes, memory barriers, etc.) are designed to prevent
unwanted optimization. If they are being used properly, there will be no
need to use volatile as well. If volatile is still necessary, there is
almost certainly a bug in the code somewhere. In properly-written kernel
code, volatile can only serve to slow things down.

抑制編譯器的優化從來不是我們想要的事情，所以從核心的 shared memory 中資料的讀取應該要有較為有效率的動作比如說 spinlock，mutex 之類的而不是使用 volatile。

POSIX Threads

Process vs. Threads

Process 由作業系統所提供，裡面的資訊包含以下幾點:

• 程式資訊和程式狀態 program resources & program state
• Process ID, process group ID, user ID, address space
• File descriptors, inter-process 中的通訊工具，例如共享記憶體 (shared memory)，pipes，semaphores

Threads 則是存在於 Process 中，並且視為一個獨立的控制流程，可以被作業系統排程，其原因為擁有以下幾點:

• Stack pointer
• Registers
• Scheduling properties (such as policy or priority)
• Set of pending and blocked signals
• Thread specific data.

在同一個 Process 中可以擁有多個 threads，而所有的 threads 可以共享同個 Process 的資源，並且執行在同一個 Process 中。

從一個 thread 中執行任務改變共享記憶體內的資料時，會被所有 threads 存取，與此同時有可能會發生兩個指標指向同一個位置並且擁有同樣的值，以上會造成一種情況就是兩個 thread 同時在更改同一塊記憶體。

所以到底什麼是 POSIX Threads?

在 POSIX Threads (Portable Operating System Interfaces,又稱 PThreads ) 還沒有被定義的年代，每家硬體供應商都有自己對 multi-threads 獨特的寫法，導致程式設計師很難整合多個硬體的 multi-threads 來研發產品，而為了解決此一問題，定義了標準的程式介面。

• For UNIX systems, this interface has been specified by the IEEE POSIX 1003.1c standard (1995).
• Implementations adhering to this standard are referred to as POSIX threads, or Pthreads.
• Most hardware vendors now offer Pthreads in addition to their proprietary API’s.

同步執行緒 Synchronizing Threads

為了避免兩個執行緒 thread 同時在更改同一會記憶體，所以同步執行緒的動作是必要的，而以下則為幾種同步的方式

• mutex
  • Linux kenrel 中的 mutex lock, <include/mutex.h>
• semaphore
  • Linux kernel 中的 semaphore, <include/semaphore.h>
  • semaphore 讓數個 producer 與數個 consumer 在計數器的基礎上進行合作

  mutex 和 semaphore 的差別?

  最大的差異在於 Mutex 只能由上鎖的 thread 解鎖，而 Semaphore 沒有這個限制，可以由原本的 thread 或是另外一個 thread 解開。另外，Mutex 只能讓一個 thread 進入 critical section，Semaphore 的話則可以設定要讓幾個 thread 進入。這讓實際上使用 Mutex 跟 Semaphore 場景有很大的差別。

  舉例而言，Mutex 的兩個特性：一個是只能有持鎖人解鎖、一個是在釋放鎖之前不能退出的特性，讓 Mutex 叫常使用在 critical section 只能有一個 thread 進入，而且要避免 priority inversion 的時候；Semaphore 也能透過 binary semaphore 做到類似的事情，卻沒有辦法避免 priority inversion 出現。

  而 Semaphore 更常是用在同步兩個 thread 或功能上面，因為 Semaphore 實際上使用的是 signal 的 up 與 down，讓 Semaphore 可以變成是一種 notification 的作用，例如 A thread 執行到某個地方時 B thread 才能繼續下去，就可以使用 Semaphore 來達成這樣的作用。

  需特別注意在 mutex 的型態等於 PTHREAD_MUTEX_INITIALIZER ，mutex 和 semaphore 的某些行為會看似一樣，但是此行為其實是被定義為 undefined behavior，參考自 pthread_mutex_lock

  If the mutex type is PTHREAD_MUTEX_DEFAULT, attempting to recursively lock the mutex results in undefined behavior. Attempting to unlock the mutex if it was not locked by the calling thread results in undefined behavior. Attempting to unlock the mutex if it is not locked results in undefined behavior.

  資料來源 : 你用的 Mutex 真的是你知道的 Mutex 嗎？

• condition variables
  • condition variables 允許其他 thread 阻擋 (block) 直到某一情況符合條件
  • 上述情況會一直持續到其他 thread 通知此 thread 任務可以繼續進行
  • 依照上述情況可以推知 condition variables 大概都會使用到 mutex_lock
  ​​  pthread_mutex_t *lock;
  ​​  pthread_cond_t *notFull, *notEmpty;
  
  ​​  void consumer(char* buf) {
  ​​  for(;;) {
  ​​  pthread_mutex_lock(lock);
  ​​  while(count == 0)
  ​​      pthread_cond_wait(notEmpty, lock);
  ​​  useChar(buf[count-1]);
  ​​  count--;
  ​​  pthread_cond_signal(notFull);
  ​​  pthread_mutex_unlock(lock);
  ​​  }
  ​​}
  

Mutex & Semaphores 的風險

Dijkstra 透過 Binary Semaphore 來嘗試解決在共享記憶體上的 race condition 的問題。方法為透過隔絕任務開始和任務結束之間的時間來阻止其他可能的變化。而上述情況可能會有以下問題產生:

• Deadlock
  Deadlock 出現在當某個任務被鎖住然後等待著一個永遠不會解鎖的情況
• Recursive Deadlock
  Recursive Deadlock 出現在當某個任務想要 lock 已經鎖住的 semaphores
  • 實際例子: MySQL database bug
• Priority Inversion

Lock-free Programming

簡單來說就是在撰寫多執行緒程式時，執行緒是否與其他執行緒分隔

參考資訊

並行程式設計
An Introduction to Lock-Free Programming
Department of Computing Imperial College of Science, Technology and Medicine
What are Pthreads?

4. RCU 同步機制

RCU 為 Read-Copy-Update 的縮寫，簡單來說就是在多執行緒的環境下，對某個資料結構進行資料的更新並且對每個執行緒共享數據結構。

RCU 考慮以下議題:

• 寬限期
  為什麼要寬限期?

  • 寬限期為一個時間區段兩個執行緒執行同一段程式碼，若一個時間區段開始時已經有一個執行緒開始讀取資料 (read) ，一個執行緒已經結束了他的任務正要釋放記憶體，那此時記憶體釋放會破壞正在讀取資料的執行緒的任務。
  • 寬限期的目的即為只要在此時間區段之前有讀取資料 (read) 那釋放記憶體的工作就會延長到最後一個執行緒執行完任務。
    
    

• 訂閱發布制 (Publish-Subscribe)

參考資訊

Linux 核心設計: 淺談同步機制
Mutex, Semaphore, the difference, and Linux kernel
Linux 核心設計: RCU 同步機制
Read-copy-update

5. 事件驅動的 I/O 模型

I/O 事件模型

參考資訊

Linux 核心設計: 針對事件驅動的 I/O 模型演化

6. 檔案系統 filesystem

littlefs