Linux Synchronization - 3

Spin lock 的變化型：

‧ spin_lock(spinlock_t *lock) & spin_unlock(spinlock_t *lock)
最基本的 Spin lock 函式，用來取得或釋放 lock。適用於多處理器系統，且共用資源會被不同的 CPU 執行的行程同時存取的情況。


‧ spin_lock_bh(spinlock_t *lock) & spin_unlock_bh(spinlock_t *lock)
加上 Local softirq disabling 的 Spin lock 函式，關閉 Bottom half 的程序並取得 lock，或是釋放 lock 並開啟 Bottom half 的程序。
適用於多處理器系統，且共用資源會被 Bottom half 的程序所存取的情況。

spin_lock_bh(l) = local_bh_disable() + spin_lock(l)
spin_unlock_bh(l) = spin_unlock(l) + local_bh_enable()


‧ spin_lock_irq(spinlock_t *lock) & spin_unlock_irq(spinlock_t *lock)
加上 Local interrupt disabling 的 Spin lock 函式，關閉 CPU 的中斷並取得 lock，或是釋放 lock 並開啟 CPU 的中斷。
適用於多處理器系統，且共用資源會被中斷處理函式所存取的情況。

spin_lock_irq(l) = local_irq_disable() + spin_lock(l)
spin_unlock_irq(l) = spin_unlock(l) + local_irq_enable()


‧ spin_lock_irqsave(spinlock_t *lock, unsigned long flags) & spin_unlock_irqrestore(spinlock_t *lock, unsigned long flags)
加上 Local interrupt disabling 的 Spin lock 函式，關閉 CPU 的中斷並取得 lock，或是釋放 lock 並開啟 CPU 的中斷。
此外，在關閉中斷前會儲存中斷的狀態，以及使用該儲存的狀態來開啟中斷。
適用於多處理器系統，且共用資源會被中斷處理函式所存取，同時中斷會在呼叫 Spin lock 之前就己經關閉的場合。
這一組 spin lock 會有當釋放 lock 時，不會再啟動中斷的效果(例如巢狀的中斷)。

spin_lock_irqsave(l, f) = local_irq_save(f) + spin_lock(l)
spin_unlock_irqrestore(l, f) = spin_unlock(l) + local_irq_restore(f)


使用 Spin lock 的注意事項：

握有 lock 的行程不能進入休眠狀態或是被另一行程搶走 CPU 執行權，否則可能會讓其他想要取得同一個 lock 的行程
進入無窮的 "忙碌迴圈" 之中 ，CPU資源就會完全地被該行程給吃掉(因為握有 lock 的行程不知何時才會釋放 lock)。

Linux Synchronization - 2

以下為 Spin lock 不同的實作方式：

1. Uni-processor 且為 Non-preemptive 的系統 (CONFIG_SMP 及 CONFIG_PREEMPT 均未定義)
Spin lock 完全無作用——因為在這種系統中，共用資源在同一時間不可能會被兩個以上的行程所存取，故不需要實作出 lock 的保護功能。

typedef struct { } spinlock_t;　/* 內容為空的結構 */

#define spin_lock(lock)　　　_spin_lock(lock)
#define spin_unlock(lock)　　_spin_unlock(lock)
#define _spin_lock(lock) \
　　do { \
　　　　preempt_disable(); \
　　　　_raw_spin_lock(lock); \
　　　　__acquire(lock); \
　　} while(0)

#define _spin_unlock(lock) \
　　do { \
　　　　_raw_spin_unlock(lock); \
　　　　preempt_enable(); \
　　　　__release(lock); \
　　} while (0)

#define _raw_spin_lock(lock)　　　do { (void)(lock); } while(0)
#define _raw_spin_unlock(lock)　　do { (void)(lock); } while(0)

定義於 include/linux/spinlock.h

#define preempt_disable()　　do { } while (0)
#define preempt_enable()　　do { } while (0)

定義於 include/linux/preempt.h

#define __acquire(x)　　(void)0
#define __release(x)　　(void)0

定義於 include/linux/compiler.h


2. Uni-processor 且為 Preemptive 的系統 (定義 CONFIG_PREEMPT 且 CONFIG_SMP 未定義)
Spin lock 實作成開、關 Kernel preemption 的功能，目的也是讓共用資源在同一時間不會被兩個以上的行程所存取。

typedef struct { } spinlock_t;　/* 內容為空的結構 */

#define spin_lock(lock)　　　_spin_lock(lock)
#define spin_unlock(lock)　　_spin_unlock(lock)
#define _spin_lock(lock) \
　　do { \
　　　　preempt_disable(); \
　　　　_raw_spin_lock(lock); \
　　　　__acquire(lock); \
　　} while(0)

#define _spin_unlock(lock) \
　　do { \
　　　　_raw_spin_unlock(lock); \
　　　　preempt_enable(); \
　　　　__release(lock); \
　　} while (0)

#define _raw_spin_lock(lock)　　　do { (void)(lock); } while(0)
#define _raw_spin_unlock(lock)　　do { (void)(lock); } while(0)

定義於 include/linux/spinlock.h

#define preempt_disable() \
　　do { \
　　　　inc_preempt_count(); \
　　　　barrier(); \
　　} while (0)

#define preempt_enable() \
　　do { \
　　　　preempt_enable_no_resched(); \
　　　　preempt_check_resched(); \
　　} while (0)

定義於 include/linux/preempt.h

#define __acquire(x)　　(void)0
#define __release(x)　　(void)0

定義於 include/linux/compiler.h


3. Multi-processor 且為 Non-preemptive 的系統 (定義 CONFIG_SMP 且 CONFIG_PREEMPT 未定義)
Spin lock 有實作出 "忙碌迴圈" 的功能，用來鎖住想要使用共用資源卻又無法取得 lock 的行程。

typedef struct {
　　volatile unsigned int slock;
} spinlock_t;

static inline void _raw_spin_lock(spinlock_t *lock)
{
　　__asm__ __volatile__(
　　　　spin_lock_string
　　　　:"=m" (lock->slock) : : "memory"
　　);
}

static inline void _raw_spin_unlock(spinlock_t *lock)
{
　　char oldval = 1;
　　__asm__ __volatile__(
　　　　spin_unlock_string
　　);
}

#define spin_lock_string \
　　"\n1:\t" \
　　"lock ; decb %0\n\t" \
　　"jns 3f\n" \
　　"2:\t" \
　　"rep;nop\n\t" \
　　"cmpb $0,%0\n\t" \
　　"jle 2b\n\t" \
　　"jmp 1b\n" \
　　"3:\n\t"

#define spin_unlock_string \
　　"xchgb %b0, %1" \
　　　　:"=q" (oldval), "=m" (lock->slock) \
　　　　:"0" (oldval) : "memory"

定義於 include/asm-i386/spinlock.h

#define spin_lock(lock)　　　_spin_lock(lock)
#define spin_unlock(lock)　　_spin_unlock(lock)

定義於 include/linux/spinlock.h

void __lockfunc _spin_lock(spinlock_t *lock)
{
　　preempt_disable();
　　_raw_spin_lock(lock);
}

EXPORT_SYMBOL(_spin_lock);

void __lockfunc _spin_unlock(spinlock_t *lock)
{
　　_raw_spin_unlock(lock);
　　preempt_enable();
}

EXPORT_SYMBOL(_spin_unlock);

定義於 kernel/spinlock.c

#define preempt_disable()　　do { } while (0)
#define preempt_enable()　　do { } while (0)

定義於 include/linux/preempt.h

4. Multi-processor 且為 Preemptive 的系統 (定義 CONFIG_SMP 及 CONFIG_PREEMPT)
Spin lock 有實作出 "忙碌迴圈" 的功能，而且被鎖住的行程，可以讓其他行程搶走 CPU 的執行權。

typedef struct {
　　volatile unsigned int slock;
　　unsigned int break_lock;　/* #ifdef CONFIG_PREEMPT */
} spinlock_t;

static inline int _raw_spin_trylock(spinlock_t *lock)
{
　　char oldval;
　　__asm__ __volatile__(
　　　　"xchgb %b0,%1"
　　　　:"=q" (oldval), "=m" (lock->slock)
　　　　:"0" (0) : "memory"
　　);
　　return oldval > 0;
}

static inline void _raw_spin_unlock(spinlock_t *lock)
{
　　char oldval = 1;
　　__asm__ __volatile__(
　　　　spin_unlock_string
　　);
}

#define spin_unlock_string \
　　"xchgb %b0, %1" \
　　　　:"=q" (oldval), "=m" (lock->slock) \
　　　　:"0" (oldval) : "memory"

#define spin_is_locked(x)　　(*(volatile signed char *)(&(x)->slock) <= 0)

定義於 include/asm-i386/spinlock.h

#define spin_lock(lock)　　　　_spin_lock(lock)
#define spin_unlock(lock)　　　_spin_unlock(lock)
#define spin_can_lock(lock)　　(!spin_is_locked(lock))

定義於 include/linux/spinlock.h

#define BUILD_LOCK_OPS(op, locktype) \
void __lockfunc _##op##_lock(locktype##_t *lock) \
{ \
　　preempt_disable(); \
　　for (;;) { \
　　　　if (likely(_raw_##op##_trylock(lock))) \
　　　　　　break; \
　　　　preempt_enable(); \
　　　　if (!(lock)->break_lock) \
　　　　　　(lock)->break_lock = 1; \
　　　　while (!op##_can_lock(lock) && (lock)->break_lock) \
　　　　　　cpu_relax(); \
　　　　preempt_disable(); \
　　} \
} \
\
EXPORT_SYMBOL(_##op##_lock);

BUILD_LOCK_OPS(spin, spinlock);　/* #ifdef CONFIG_PREEMPT */

void __lockfunc _spin_unlock(spinlock_t *lock)
{
　　_raw_spin_unlock(lock);
　　preempt_enable();
}

EXPORT_SYMBOL(_spin_unlock);

定義於 kernel/spinlock.c

#define preempt_disable() \
　　do { \
　　　　inc_preempt_count(); \
　　　　barrier(); \
　　} while (0)

#define preempt_enable() \
　　do { \
　　　　preempt_enable_no_resched(); \
　　　　preempt_check_resched(); \
　　} while (0)

定義於 include/linux/preempt.h

Linux Synchronization - 1

以下列出 Kernel 的同步機制：

1. Per-CPU variables
將 Kernel 中的變數宣告成 per-CPU 的陣列型式，每一個 CPU 都有屬於自己的變數空間，不會和其他的CPU共用。

2. Atomic operations
讓存取記憶體的指令能夠完整的執行完成，不會被中斷或其他的 CPU 指令所打斷。

3. Memory barriers
利用一些 Macro 安插於某段程式中，確保程式能如預期的順序來執行。

4. Spin lock
以 lock 的方法來保護特定資源只能被一個程序使用，其他欲使用該資源的程序會進入 "忙碌迴圈" 等待資源被釋放為止。

5. Semaphore
類似 Spin lock 的保護方法，但待等特定資源的行程會進入休眠狀態，也就是要讓出 CPU 使用權，因此不可用於中斷處理函式。

6. Seqlock
類似 Spin lock 的原理，將 lock 分為 reader 及 writer 兩種，分別用來保護資源被謮與寫的動作。而 writer 有高於 reader 的優先權，亦即同時發生讀、寫同一資源時，寫的動作會優先執行。

7. Local interrupt disabling
利用關閉目前 CPU 的中斷處理函式來保護程序不會被其他中斷所打斷，但是在多 CPU 的機器上不能使其他 CPU 關閉中斷。

8. Local softirq disabling
利用停止延遲執行的中斷處理函式(例如 Bottom Half)，來保護特定資源不會被其他的延遲執行的中斷處理函式所存取，而且此種方式不會關閉中斷。

9. Read-Copy Update (RCU)
利用指標的資料結構，當某指標發生被寫的動作時，將該指標複製一份(例如拷貝指標所指向的記憶體)，然後對複本進行存取。完成寫的動作後，再更新該指標成為修改過的複本(例如將原來的指標改成複製後的記憶體位址)。

下表列出如何使用同步機制來保護 Kernel data structure：