はじめに
spinlockはbusy waitによって実現するlockの手法のことである。busy waitとは、lockを取得できるまでloopで待機するという点で原始的だが、lock/unlockに要するオーバーヘッドを最小限にできるので、Linux kernelでは頻繁に登場する。
内部実装的には、簡単に言うと、spinlockを実現する関数(spin_lock())はxchg命令でlockの取得を試み、もしも失敗した場合はpause(rep;nop;だが機械語は同じ)で、(他が)unlockされるのを待ち、xchg命令でlockの取得を試み...みたいなことを繰り返す。
この関数の定義元が意外と追いづらく、spin_lock()の中身も割と複雑だったりするので、ある程度詳しめにまとめてみようと思った。
なお、本記事ではread_spinlockやwrite_spinlockには触れない1。
reference
- [1]Understanding the Linux Kernel ch.5(Spin Locksの小節), ch.7(scheduler)あたり
前回の記事同様、今回もreference[1]にならって、versionは2.6.11とします。
定義
include/linux/spinlock.hから出発するが、ifdefなどで少し込み入っているので、コードの概略を示す。x86/defconfigを見ると、CONFIG_SMP=yおよびCONFIG_DEBUG_SPINLOCKは定義されてない：
#ifndef __LINUX_SPINLOCK_H #define __LINUX_SPINLOCK_H #ifdef CONFIG_SMP // If CONFIG_SMP is set, pull in the _raw_* definitions↲ #include <asm/spinlock.h> // skip #else // !CONFIG_SMP #ifdef CONFIG_DEBUG_SPINLOCK // in x86, not set #else // If CONFIG_SMP is unset, declare the _raw_* definitions as nops #endif /* CONFIG_DEBUG_SPINLOCK */ /* RW spinlocks: No debug version */ #endif // end #ifdef CONFIG_SMP // Define the various spin_lock and rw_lock methods. Note we define these regardless of whether CONFIG_SMP or CONFIG_PREEMPT are set. // // __cond_lock is useful when sparse(type checker tools) is used #define spin_trylock(lock) __cond_lock(_spin_trylock(lock)) // skip #define spin_lock(lock) _spin_lock(lock) // skip #ifdef CONFIG_SMP #define spin_lock_irqsave(lock, flags) flags = _spin_lock_irqsave(lock) // skip #else // CONFIG_SMP #define spin_lock_irqsave(lock, flags) _spin_lock_irqsave(lock, flags) // skip #endif #define spin_lock_irq(lock) _spin_lock_irq(lock) #define spin_unlock(lock) _spin_unlock(lock) #define spin_unlock_irqrestore(lock, flags) _spin_unlock_irqrestore(lock, flags) #define spin_unlock_irq(lock) _spin_unlock_irq(lock) #define spin_trylock_irq(lock) \ ({ \ local_irq_disable(); \ _spin_trylock(lock) ? \ 1 : ({local_irq_enable(); 0; }); \ }) #define spin_trylock_irqsave(lock, flags) \ ({ \ local_irq_save(flags); \ _spin_trylock(lock) ? \ 1 : ({local_irq_restore(flags); 0;}); \ }) #define spin_can_lock(lock) (!spin_is_locked(lock)) #endif /* __LINUX_SPINLOCK_H */
spin_lockの実体は_spin_lockだが、これは、kernel/spinlock.cにある：
// kernel/spinlock.c int __lockfunc _spin_trylock(spinlock_t *lock) { preempt_disable(); if (_raw_spin_trylock(lock)) return 1; preempt_enable(); return 0; } EXPORT_SYMBOL(_spin_trylock); // skip #ifndef CONFIG_PREEMPT // skip #else /* CONFIG_PREEMPT: */ BUILD_LOCK_OPS(spin, spinlock); BUILD_LOCK_OPS(read, rwlock); BUILD_LOCK_OPS(write, rwlock); // skip
BUILD_LOCK_OPSはマクロで以下の関数を定義する：
_[spin|read|write]_lock() _[spin|read|write]_lock_irq() _[spin|read|write]_lock_irqsave() _[spin|read|write]_lock_bh()
BUILD_LOCK_OPSは https://gist.github.com/knknkn1162/3cca43b2c03728648ed84c0469c30397 であり、このマクロをバラすと以下のようになる：
// op=spin, locktype=spinlock // #define spin_lock(lock) _spin_lock(lock) void __lockfunc _spin_lock(spinlock_t *lock) { preempt_disable(); for (;;) { if (likely(_raw_spin_trylock(lock))) break; preempt_enable(); if (!(lock)->break_lock) (lock)->break_lock = 1; while (!spin_can_lock(lock) && (lock)->break_lock) cpu_relax(); // #define cpu_relax() rep_nop() preempt_disable(); } } unsigned long __lockfunc _spin_lock_irqsave(spinlock_t *lock) { unsigned long flags; preempt_disable(); for (;;) { local_irq_save(flags); if (likely(_raw_spin_trylock(lock))) break; local_irq_restore(flags); preempt_enable(); if (!(lock)->break_lock) (lock)->break_lock = 1; while (!spin_can_lock(lock) && (lock)->break_lock) cpu_relax(); // #define cpu_relax() rep_nop() preempt_disable(); } return flags; } void __lockfunc _spin_lock_irq(spinlock_t *lock) { _spin_lock_irqsave(lock); }
__lockfuncは#define __lockfunc fastcall __attribute__((section(".spinlock.text"))で、.spinlock.textセクションの在り処は以下の通り：
/* arch/i386/kernel/vmlinux.lds.S */ #define LOCK_TEXT \ VMLINUX_SYMBOL(__lock_text_start) = .; \ *(.spinlock.text) \ VMLINUX_SYMBOL(__lock_text_end) = .; // skip /* read-only */ _text = .; /* Text and read-only data */ .text : { *(.text) // skip LOCK_TEXT // skip
今回は、_spin_lockを取り上げることにする。
なお、_spin_trylockはざっくり_spin_lockのfor(;;)loopがなくなったバージョンの関数なので、_spin_lockの実装が追えれば問題なく_spin_trylockもわかると思う。
spin_lock
spin_lock(spinlock_t lock)はlockが奪取できるまで処理をblockする関数である。この関数を用いることで複数のCPU-メモリ間で同期的な振る舞いを保てることになる。コアのlockingの部分の命令はatomicになっているため、例えばinterruptなどでlocking処理の途中に邪魔されることもない。
なお、blockさせたくない場合は、spin_trylockを用いること。
改めて再掲：
typedef struct { // the value 1/0 corresponds to the unlocked/locked state volatile unsigned int slock; #ifdef CONFIG_DEBUG_SPINLOCK // in x86/defconfig, no unsigned magic; #endif #ifdef CONFIG_PREEMPT // in x86/defconfig, CONFIG_PREEMPT=y unsigned int break_lock; #endif } spinlock_t; void __lockfunc _spin_lock(spinlock_t *lock) { preempt_disable(); for (;;) { if (likely(_raw_spin_trylock(lock))) break; preempt_enable(); if (!(lock)->break_lock) (lock)->break_lock = 1; while (!spin_can_lock(lock) && (lock)->break_lock) cpu_relax(); // #define cpu_relax() rep_nop() preempt_disable(); } }
spin_lockは以下のようなフローとなっている：
spin_lock(spinlock_t *lock) - _spin_lock(spinlock_t *lock): - inc_preempt_count(): add_preempt_count(1) - barrier(): memory barrier(when compilation) - __asm__ __volatile__("": : :"memory"); see `include/linux/compiler-gcc.h` - (loop:) - break loop when _raw_spin_trylock(lock) = true: see `include/asm-i386/spinlock.h` and below - preempt_enable(): otherwise; - preempt_enable_no_resched(): - barrier(): memory barrier(when compilation) - dec_preempt_count: sub_preempt_count(1) - preempt_check_resched(): exec context switch if TIF_NEED_RESCHED - preempt_schedule(): if unlikely(¤t_thread_info()->flags & TIF_NEED_RESCHED) - add_preempt_count(PREEMPT_ACTIVE): (set label need_sched:) - schedule(): exec context switch. goto the other process! - sub_preempt_count(PREEMPT_ACTIVE) - barrier(); - if test_thread_flag(TIF_NEED_RESCHED)), goto need_sched label again! - set (spin_lock*)lock->break_lock = 1; - cpu_relax(): until lock->break_lock=0 or lock->slock = 1(unlocked) - rep_nop: - __asm__ __volatile__("rep;nop": : :"memory"); // same as `pause` - preempt_disable(): - inc_preempt_count(): add_preempt_count(1) - barrier(); - (goto loop label)
一つ一つのプロセスを分解すると複雑に見えるが、とりあえず重要な関数を一つづつピックアップして行こう。
barrier
GCC compilerの場合、以下のように追っていけば良い：
// include/linux/compiler.h #if __GNUC__ > 3 # include <linux/compiler-gcc+.h> /* catch-all for GCC 4, 5, etc. */ #elif __GNUC__ == 3 # include <linux/compiler-gcc3.h> #elif __GNUC__ == 2 # include <linux/compiler-gcc2.h> #else # error Sorry, your compiler is too old/not recognized. #endif // include/linux/compiler-gcc+.h #include <linux/compiler-gcc.h> // include/linux/compiler-gcc.h #define barrier() __asm__ __volatile__("": : :"memory")
_raw_spin_trylockとxchg
次に、_raw_spin_trylockこれはinclude/linux/spinlock.h内の#include <asm/spinlock.h>で定義されている(include/asm-i386/spinlock.h3)
// include/asm-i386/spinlock.h typedef struct { volatile unsigned int slock; #ifdef CONFIG_PREEMPT // in x86/defconfig, yes unsigned int break_lock; #endif } 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; }
_raw_spin_trylock4はlockが成功すればtrueを失敗すれば0を返す。つまり、
[lockが成功する場合]古いlock->slockが1(unlocked)でxchgによって正常に、lock->slock=0(locked)の状態に切り替わる => oldval(古いlock->slock)が1(unlock)となる場合
[lockが失敗する場合]古いlock->slockが1(locked)されているまま => xchgによってlock->slock=0(locked)の状態のまま => oldvall(古いlock->slock)が0(locked)である場合
の2種類考えられる。lockが失敗する場合は他のCPUがspinlock_t *lockを握っている場合。
ここで、xchgとはexchangeの意味の命令であり、Intel SDM vol.3の8.1.2.1 Automatic Lockingによれば、When executing an XCHG instruction that references memory.に当てはまるので、atomicであることに注意5。
_spin_lockでは、_raw_spin_trylockがfalse(つまり、lockが失敗した場合)の場合、lockがunlockになるまで待ち、for(;;)の先頭に戻って、再度_raw_spin_trylockの判定がなされる(lock->slock=1(unlock)のままである場合がほとんどだから、今度はlockingが高確率で成功する)。
preempt_enable
_spin_lockでは、非常に低い確率にしろ、長時間この関数内にとどまる状況に陥る可能性があるため、for(;;)のループごとにスケジューリングの要求を確認し、(TIF_NEED_RESCHED6=ON)、必要ならば、schedule()で別のプロセスに移ってしまう7。この役割を担うのがpreempt_enableである。
ちなみに、_spin_trylockの方は_spin_lockと違って、即時に値を返すので、preempt_check_reschedが必要ない。
cpu_relax()
linux 2.6では、#define cpu_relax() rep_nop()と定義されている。rep_nop関数は文字通り、__asm__ __volatile__("rep;nop": : :"memory");となっている。rep; nop;は実際にはpause命令と同じであるが、8、pause命令の仕様が少し紛らわしい(言葉どおりに捉えると、一時停止だが、少し誤解を招くと思う)ので、まずはIntel SDM vol.2のpause命令を参照したい：
pause: Spin Loop Hint
Description
Improves the performance of spin-wait loops. When executing a “spin-wait loop,” processors will suffer a severe performance penalty when exiting the loop because it detects a possible memory order violation. The PAUSE instruction provides a hint to the processor that the code sequence is a spin-wait loop. The processor uses this hint to avoid the memory order violation in most situations, which greatly improves processor performance. For this reason, it is recommended that a PAUSE instruction be placed in all spin-wait loops.
An additional function of the PAUSE instruction is to reduce the power consumed by a processor while executing a spin loop. A processor can execute a spin-wait loop extremely quickly, causing the processor to consume a lot of power while it waits for the resource it is spinning on to become available. Inserting a pause instruction in a spin- wait loop greatly reduces the processor’s power consumption.
This instruction was introduced in the Pentium 4 processors, but is backward compatible with all IA-32 processors. In earlier IA-32 processors, the PAUSE instruction operates like a NOP instruction. The Pentium 4 and Intel Xeon processors implement the PAUSE instruction as a delay. The delay is finite and can be zero for some processors. This instruction does not change the architectural state of the processor (that is, it performs essentially a delaying no-op operation).
つまり、実際はspin loop(busy wait)しないが、俺はSpin Loopしてるぜ、ってヒントを出す命令ということになる。古いprocessor(Pentium 4 processors以前)では、nopと同様で、文字通り何もしない。(たぶん、"何もしない"という命令が走っている) 他方、pauseを使うことでなんの恩恵を受けているかというと、Intel Hyper-Threading Technology(論理コア)を有効活用するため9である。
-
reference[1]のch.5の"Read/Write Spin Locks"にも詳しめに書いてある。↩
-
https://stackoverflow.com/questions/19965076/gcc-memory-barrier-sync-synchronize-vs-asm-volatile-memory が良さげ。↩
-
Makefileでinclude/asmに
include/asm-$(ARCH)のシンボリックリンクを貼ってる。Makefileのinclude/asmラベルを参照のこと。↩ -
__asm__ __volatile__のような格好(inline assemblerという)に慣れていない方は、 http://caspar.hazymoon.jp/OpenBSD/annex/gcc_inline_asm.html に目を通すと良いとおもう。↩ -
この処理がatomicでない場合、例えば、interruptが発生して、exchangeの処理の最中にinterrupt handlerが走ったとしたら、
lockの値が壊れてしまうので、望ましくない動作を引き起こす。↩ -
TIF_NEED_RESCHEDがどういうときに付加されるかは、Reference[1]のch.7の"Lazy invocation"に書いてあるので、省略する。簡単に言うと、すぐにschedule()に突入できない状況下において、とりあえずTIF_NEED_RESCHEDを付けておき、scheduling可能なフェーズに入ったらTIF_NEED_RESCHEDを確認することで、scheduleすべきか否かを判断したいというモチベーションである。↩ -
なお、schedule()の実行の前に
PREEMPT_ACTIVEを付けているが、PREEMPT_ACTIVEがOFFの場合は、User Modeからのinterruptの突入(nested kernel control pathではないこと)が保証される。spin_lockはkernel modeから呼び出す?(多分)のでその印として、PREEMPT_ACTIVEをつける↩ -
https://stackoverflow.com/questions/7086220/what-does-rep-nop-mean-in-x86-assembly-is-it-the-same-as-the-pause-instru を見ると良い↩
-
Intel SDM vol.3の8.10.2 PAUSE Instruction とか8.10.6.1のUse the PAUSE Instruction in Spin-Wait Loopsを見れば良さそう↩
