Spinlock汇编代码分析

在这篇文章中，我将会介绍 Kernel 提供用来使用 spinlock 的 function。除此之外，我还会告诉各位，为何在 SMP 的环境里，使用 spinlock 会比将所有 CPU 的中断 disable 这个方法来的有效率，我也会告诉各位如何针对不同的使用需求，使 spinlock 的 cost 再降低，进而使系统的效能更好... 

前言 


在 Linux Kernel 里有着许多重要的资料结构，这些资料在作业系统的运作中扮演着举足轻重的角色。然而，Linux 是个多任务的作业系统，也就是在同一时间里可以同时有许多的行程在执行，所以，很有可能某个行程在依序读取 inode list，同时却又有另一个在 inode list 里加入新的 inode，这会造成什幺情形呢？这会造成 inode list 的不稳定。所以，在 Kernel 里，我们需要一个机制，可以使得当我们在修改某个重要的资料结构时，不能被中断，即使被中断了，这个资料结构由于还没修改完，别的行程也都不能去读取和修改它。Linux Kernel提供了 spinlock 这个机制可以使我们做到这样的功能。 

有的人会想到当我们在修改某个重要的资料结构时，将中断都 disable 掉就好了，等修改完了再将中断 enable 不就得了，何必还要再提供一个 spinlock 来做同样的事。在 uni-processor 的环境底下，的确是如此。所谓 uni-processor 就是指只有一个 CPU 的电脑，但是在SMP的环境下就不是这幺一回事了。 

我们知道现在 Linux 已经有支持 SMP，也就是可以使用多颗 CPU 来加快系统的速度，如果当我们在修改重要的资料结构时，将执行修改工作的 CPU 中断 disable 掉的话，只有目前的这个 CPU 的执行不会被中断，在 SMP 环境下，还有别的 CPU 正同时运作，如果别的 CPU 也去修改这个资料结构的话，就会造成同时有两个 CPU 在修改它，不稳定性就会产生。解决方法是将全部的 CPU 中断都 disable 掉，等修改完之后，再全部都 enable 起来。但是这样的做法其 cost 会很大，整个系统的效能会 down 下来。因此，Linux Kernel 才会提供 spinlock 这样的机制，它不会将全部 CPU 的中断 disable 掉，所以效率比上述的方法好，但同时却又能确保资料的稳定性，不会有某个行程在修改它，另外又有一个行程在读取或修改它的情形发生。 

在这篇文章中，我将会介绍 Kernel 提供用来使用 spinlock 的 function。除此之外，我还会告诉各位，为何在 SMP 的环境里，使用 spinlock 会比将所有 CPU 的中断 disable 这个方法来的有效率，我也会告诉各位如何针对不同的使用需求，使 spinlock 的 cost 再降低，进而使系统的效能更好。 


spinlock的资料结构 


spinlock 的资料结构在 Linux底下是以 spinlock_t 来表示的，在 SMP 和 UP 环境底下两者的栏位有一些差异，其实在 UP 底下 spinlock_t 可以说是一个空的结构，空就是空的，为何要说"可以说是空的"呢？这是因为 gcc 版本的问题，gcc 在 2.8 版以前结构的内容必须不能是空的，而在 2.8 版之后就可以，所以在 UP 环境底下，会根据 gcc 的版本而设定不同的 spinlock_t 结构栏位，但基本上，在 UP 环境底下，是根本不会用到 spinlock_t 结构里的栏位的，详情请见以下诸节即可了解。 

由于 spinlock 主要是用在SMP的环境底下，所以，以下我们就只针对在SMP环境底下的 spinlock_t 结构来讨论，它的结构内容是这样子的： 
typedef struct { 
volatile unsigned int lock; 
} spinlock t; 

说穿了，不过就是一个 unsigned int 型别的变数而已，但可不要小看这小小的变数，螺丝钉虽小，功能却是不可忽视的。 


使用 spinlock 



spinlock t xxx lock = SPIN_LOCK_UNLOCKED; 
unsigned long flags; 

spin lock irqsave (&xxx lock, flags) 
...critical section... 
spin unlock irqrestore (&xxx lock, flags) 

这一组的函式在使用上是最保险的，用的频率也算是最多的。首先在使用前，必须先宣告一个 spinlock_t 型别的变数，并把初始值设为 SPIN_LOCK_UNLOCKED。除此之外，还必须有一个unsigned long型别的变数，这个变数是用来将 CPU 的 flag（旗标）储存起来的，等 critical section 执行完了，再把 flag 的值设回到系统里。使用上是很简单明白的。这两个 function 除了可以在 SMP 的环境下使用外，在UP的环境里也是同样可行的，接下来，我们来看看它们程序码是怎幺写的。 

在 这个档案里定义了 spin_lock_irqsave() 及 spin_lock_irqrestore() 这两个 function。 


#define spin_lock_irqsave(lock，flags) 
do { local_irq_save(flags); spin_lock(lock); } while (0) 

#define spin_unlock_irqrestore(lock，flags) 
do { spin_unlock(lock); local_irq_restore(flags); } while (0) 

local_irq_save(flags) 做的事就是将 CPU 的 flag 值先储存到 flags 变数里，然后将 CPU 的中断 diable 掉。这里将 CPU 的中断 disable 是指将执行这段 code 的 CPU，并不是指全部的 CPU。 也就是说它只会 disable local CPU 的中断。我们可以在里看到这样的程序码： 
#define local_irq_save(x) __asm__ __volatile__("pushfl ; popl %0 ; 
cli":"=g" (x): /* no input */ :"memory") 
#define local_irq_restore(x) __asm__ __volatile__("pushl %0 ; popfl" 
/* no output */ :"g" (x):"memory") 

至于 local_irq_restore(flags) 从字面上可以很清楚的看出来，只是将 flags 里的值再设回 CPU 的 flag 里而已。至于 spin_lock(lock) 和 spin_unlock(lock) 这两个函式，在 SMP 和在 UP 的环境底下则会扩展成不同的样子。首先先看到这个档案的下半部。 
#ifdef __SMP__ 
#include  

#else /* !SMP */ 
....... 
#endif 

在 SMP 的环境底下，SMP 这个constant被会 set。而在 UP 底下则不会，所以，如果要看 UP 底下 spin_lock(lock) 会变成怎幺样子，就必须来看看 #else /* !SMP */ 和 #endif 之间的程序码。 

UP 环境下的 Implementation 


我们先来看看在 UP 的环境下， spin_lock(lock) 会变成什幺样子。 
#define spin_lock(x) (void)lock 
#define spin_unlock(x) do {} while(0) 

简单吧，根本什幺事都没有做，所以，在 UP 的环境底下，我们如果将上面那段 spinlock 的使用扩展开来的话，会变成下面这个样子。 
spinlock_t xxx_lock = SPIN_LOCK_UNLOCKED; 
unsigned long flags; 

local_save_flags(flags); cli(); 
... critical section ... 
local_restore_flags(flags); 

而这也正是在 UP 环境下，用来保护重要资料结构的写法。这也就是为什幺在介绍spinlock_t 的结构内容时，我们说在UP环境底下这个结构就算是空的也不会影响到 spinlock 的功效，因为根本没用到里面的栏位，但是在 SMP 底下，这就很重要了。 

SMP 环境下的 Implementation 


在 SMP 的环境底下， spin_lock() 和 spin_unlock() 这两个函式的原始码是放在 中。 
extern inline void spin_lock(spinlock_t *plock) 
{ 
__asm__ __volatile__( 
spin_lock_string 
:"=m" (__dummy_lock(plock))); 
} 

其实，这段程序码是经过我削减后的，至于削减掉的程序码是用来做 debug 的，所以，就不列出来，有兴趣的朋友不彷自行去看看。在上图中，spin_lock_string 是一个 macro，加上 □asm□ 语法，我将它展开成下面这个样子： 
extern inline void spin_lock(spinlock_t *plock) 
{ 
1: 
lock ; btsl $0,plock; 
jc 2f; 
.section .text.lock,"ax" 
2: 
testb $1,plock;  注：lock, rep,分号等都是AT&T汇编语言语法
rep;nop; 
jne 2b; 
jmp 1b; 
.previous 
} 

让我们来看看 spin_lock() 这段组合语言是什幺意思。在 Linux 底下，组合语言是用 AT&T 的语法，跟平常我们在 PC 底下使用的 Microsoft 语法不相同，主要的差别是 source 与 destination 的位置相反。基本上，spinlock 有两种状态，第一种被锁住的状态（lock），第二种则是没被锁住的状态（unlock）；当 spinlock 被锁住时，spinlock_t.lock 会被设为 1，当没被锁时，则会设回 0，各位可以去看我们之前所列出来的使用方法，它会将 spinlock_t 结构的初始值设为 SPIN_LOCK_UNLOCK，现在再来看看这个 constant 的值，可以发现它其实就是将 spinlock_t.lock 设为 0 而已。 
#define SPIN_LOCK_UNLOCKED (spinlock_t) { 0 } 

所以，检查其状态就变成了 spin_lock() 的首要工作，如果已被锁住，则 CPU 就不能去使用它所保护的资料结构，而如果没上锁，则可以从 spin_lock() 传回，接下去使用它所保护的资料。所以，检查其状态我们可以检查 spinlock_t.lock 的第 0 个 bit。btsl $0, plock 会将 plock 的第 0 个 bit 值传到 flag 旗标的 carry 并把 plock 的第 0 个 bit 设为 1，其中 $0 是在 AT&T 语法中是指数字，也就是 immediate value。所以，再来只要检查 carry 的值就可以了。当 carry 的值是 1 时，表示 spinlock 是上锁状态的，就跳到 label 2 的地方去执行，在程序码里，我们可以看到 jump 指令后面接着 2b，2f 及 1b 这些字眼，这些都是指 1: 或 2: 这些 label，如果某个 label 定在 jump 的前面，则指定label 时，要加上 b（backward），如果在后面，则加上 f（forward）。在 label 2 这段程序码里，它不停的做回圈，执行 nop 指令，每次的回圈都会去检查一次 spinlock_t.lock 的值，当 spinlock 不是锁住的状态时，就会跳离回圈，离开 spin_lock() 函式。 

看完了 spin_lock()，再来看 spin_unlock() 就会发觉简单多了。 
#define spin_unlock(lock) 
__asm__ __volatile__( spin_unlock_string 
:"=m" (__dummy_lock(lock))) 

其中，spin_unlock_string 一样是个 macro，展开后变成下面这个样子: 
spin_unlock(plock) 
｛ 
lock; btrl $0, plock; 
} 

btrl $0, plock 这一行会将 plock 的第 0 个 bit 设为 0，可以很清楚的看出来，spin_unlock() 只是将 plock 的第 0 个 bit 再设回 0 而已。在 spin_lock() 和 spin_unlock() 里我们都可以看到 lock 这个指令在 btrl 或 btsl 的前头，这个指令的用途是当 btrl 或 btsl 在修改 plock 的值时，其它别的行程都不能来修改 plock 的值，如果有别的行程企图修改 plock 的值就会造成 exception 的发生。 

看到这里，各位应该可以了解 spinlock 的运作方式及其基本的使用方法了，接下来，我要跟各位介绍 spinlock 的另一种小小的变型，叫 read-write spinlock。 

第二种的使用方式 


有些资料结构是这样子的，我们希望有人在修改它的内容时，别人都不能读取或修改它，但是当没有人在修改它时，可以同时有很多人去读取它的内容。我们称这样的 spinlock 为 read-write spinlock。 Kernel 为它定义了 rwlock_t，放在 里。使用方式是这样子的。 
rwlock_t xxx_lock = RW_LOCK_UNLOCKED; 

unsigned long flags; 

read_lock_irqsave(&xxx_lock， flags); 
... critical section that only reads the info ... 
read_unlock_irqrestore(&xxx_lock， flags); 

write_lock_irqsave(&xxx_lock， flags); 
... read and write exclusive access to the info ... 
write_unlock_irqrestore(&xxx_lock， flags); 

其实我们可以看到，它们的使用方式都是差不多的。在使用之前，先要宣告一个 rwlock_t 的变数，并将初始值设为 RW_LOCK_UNLOCKED， flags 还是一样是用来存放 CPU flag 的值。如果你要去读取资料结构的值，可以呼叫 read_lock_irqsave()，用完时则呼叫read_unlock_irqrestore()。至于当你要修改资料结构时，则呼叫 write_lock_irqsave()，修改完呼叫 write_unlock_irqrestore() 即可。 

我们来看看read这组函式的原始码是怎幺样子的： 
#define read_lock_irqsave(lock， flags) do { local_irq_save(flags);　 
read_lock(lock); } while (0) 

#define read_unlock_irqrestore(lock， flags) do { read_unlock(lock);　　 
local_irq_restore(flags); } while (0) 

这二个函式和 spin_lock_irqsave() 与 read_unlock_irqrestore() 的 差别只在于一个是呼叫 spin_lock() 与 spin_unlock()，另一个则是呼叫 read_lock() 与 read_unlock()。 

我们再来看看 read_lock() 与 read_unlock() 这两个函式，在 UP 环境底下是这个样子的： 
#define read_lock(lock) (void)(lock) /* Not "unused variable". */ 
#define read_unlock(lock) do { } while(0) 

啊哈，跟 UP 底下的 spin_lock() 与 spin_unlock() 完全是一模一样的，所以，事实上在 UP 的环境下，使用 rwlock 和 spinlock 是没有差别的。其实，各位可以自己去看 write_lock_irqsave() 与 write_unlock_irqsave() 的程序，扩展开来跟上面两组函式都是一样的。原因其实很简单，在 UP 的环境下，虽然 Linux 号称多任务的系统，但由于只有一颗 CPU，在同一时间只有一个行程在执行，其它的行程都会被 suspend，唯一会中断 Kernel 执行的只有 interrupt 了。所以，事实上，要做好 critical section 的保护只要暂时将中断 disable 掉就行了。 Kernel 之所以要提 供上面这些函式其实是要给 SMP 的系统使用的，除此之外，它另一个用途就是增加 portability。 程序只要用 spinlock 来写的话，那不管是在 SMP 或 UP 环境下都可以直接 compile 并执行，不用再重新修改程序码。 

至于 SMP 底下 rwlock 的实作方式我就不再赘述，基本上它们的实作方式都是差不多的，只有一点要特别说的是，由于 rwlock 可以容许多个 reader，但却只能有一个 writer，所以，它不会只用到 rwlock_t.lock 的第 0 个 bit 而已。事实上，rwlock_t.lock 是个 32bit 的 unsigned int 型别的变数，因此，它用第 0 到 30 个 bit 当作 reader 的 counter，而第 31 个 bit 则是用来给 writer 使用的。当第 31 个 bit 为 1 时，表示目前 rwlock 被 writer 锁住，此时前 30 个 bit 都应该是 0，表示此时没有任何的 reader。因此，可以推断 rwlock 同一时间最多可以有 2 的 30 次方个 reader。 


第三种使用 spinlock 的方式 


我们可以看到以上两种的使用机制都是以 disable 中断的方式来做的，虽然 disable 中断很简单，只要一个指令就行了，但事实上，这个指令的 cost 对 CPU 来讲是蛮大的。所以， Kernel 还提供另一组的函式，它不 disable 中断，所以，它的执行速度会比上面两种来得有效率一些。 但是，上帝是公平的，它让你速度快，相对的它也提供的某些限制。这个限制就是就如果你确定 interrupt handler 不会用到这个受保护的资料结构时，那你就可以考虑用这一组的函式， 以加快程序的执行。其实，这一组函式我们已经在上面见过了。 
spin_lock(&lock); 
... 
spin_unlock(&lock); 

就是 spin_lock() 和 spin_unlock() 这两个函式。在上面我们已经见过这两个函式展开的情形了， 在 UP 的环境里，这两个函式跟空的没什幺两样。但为何在UP底下，它们可以做到保护 critical section的作用呢？原因其实也讲过了，因为在UP底下只有一个 CPU，所以，在同一时间只有一个行程在执行，除非行程自己放弃执行，不然只有 interrupt 会中断其执行。刚才我们说过，使用这组函式的前提是在 interrupt handler 中不能使用到放在 critical section 中的资料结构。既然在 interrupt handler 中不会使用到，就算在 critical section 使用这个资料结构使用到一半，中断突然发生，处理完中断，CPU 还是会直接回来执行 critical section 的程序码。所以，不会造成受保护的资料结构的不稳定。我们现在来看看，如果我们使用这组函式， 而且在 interrupt handler 中使用受保护的资料结构时会发生什幺事。 
spin_lock(&lock); 
.... 
<------ interrupt 
spin_lock(&lock); 
... 
spin_unlock(&lock) 

在 UP 的的环境下，由于 spin_lock() 是空的，则当中断发生时，很有可能行程使用资料结构到一半，中断跑进来，也在使用它，造成这个资料结构的不稳定。如果是在SMP的环境下，由于 spin_lock() 是真的有在做事，所以当中断发生时，如果这个中断是发生在别的 CPU 上， 那就没事，因为 spin_lock() 只会让中断发生的 CPU suspend 住而已。等原先的 CPU 执行完 spin_unlock() 它就可以恢复了，但是如果这时的中断还是发生在原先的 CPU 上时，那在 interrupt handler 中，CPU 会一直被 suspend 住，直到 lock 被释放为止。这就造成了一个 dead lock。因为这颗 CPU 现在已经被 lock 住，如何离开 interrupt handler 去呼叫 spin_unlock() 呢。 

混合使用 


针对 rwlock_t 这组函式除了上面提到的用法外，事实上，还是可以混合 spin_lock() 及 spin_unlock() 来使用的。由于 rwlock_t 可以允许多个 reader，所以如果在 interrupt handler 中只会读取受保护的资料结构，而不会去修改它的话，那我们可以使用 spin_lock() 这组函式，但是当行程要修改资料结构时，还是得呼叫 write_spin_lock() 及 write_spin_unlock() 这组的函式。这样既可以增加执行的效率，又可以确保重要资料结构的稳定性了。 

结论 


虽然在 UP 的环境中，保护重要的资料结构只要呼叫 cli() 和 sti() 就好，但是随着 SMP 技术的成熟，相信 SMP 系统会逐渐的增加，为了让自己写的程序具有可移植性，善用 spinlock 这项机制相信会为未来省下相当修改程序码的功夫。 

=====

从上看到，spin_lock的主要内容是spin_lock_string宏，定义如下：

#define spin_lock_string \ "\n1:\t" \ "lock ; decb %0\n\t" \ "js 2f\n" \ LOCK_SECTION_START("") \ "2:\t" \ "cmpb $0,%0\n\t" \ "rep;nop\n\t" \ "jle 2b\n\t" \ "jmp 1b\n" \ LOCK_SECTION_END

在上面的汇编代码中，首先将lock递减，如果为负（表明锁已被持有），则进入自旋。每次自旋在执行一条空指令后，根据lock和0的比较结果进行跳转。如果lock小于或等于0，则继续自旋；否则（说明锁已被释放），则将lock递减后返回。在这里，采取了一种优化手段，因为在大多数情况下，自旋锁是能成功获取的，而自旋部分代码，只是在锁被持有时才执行，因此利用LOCK_SECTION_START和LOCK_SECTION_END将这些代码放到一个专门的区（.text.lock）中。如果把它跟别的常用指令混在一起，会浪费指令缓存的空间。理解这一点，我们也就能明白spin_lock是如何退出的了。事实上，由于不再同一个区（section），所以"js 2f"的下一条指令并不是"cmpb $0,%0"。

#define LOCK_SECTION_NAME \ ".text.lock." __stringify(KBUILD_BASENAME)

#define LOCK_SECTION_START(extra) \ ".subsection 1\n\t" \ extra \ ".ifndef " LOCK_SECTION_NAME "\n\t" \ LOCK_SECTION_NAME ":\n\t" \ ".endif\n\t"

#define LOCK_SECTION_END \ ".previous\n\t"

如果用类C语言来描述上述过程，将是：void spin_lock(int &lock){ int flag;

label1: flag = lock--; if (flag >= 0) { return; } else { do { nop; } while(lock <= 0); goto label1; }}

当然，我们需要保证lock--为原子操作，就像在汇编中在decb指令前加上lock前缀一样。释放锁时使用spin_unlock_string宏，定义如下：

static inline void spin_unlock(spinlock_t *lock){ __asm__ __volatile__( spin_unlock_string );}

#define spin_unlock_string \ "movb $1,%0" \ :"=m" (lock->lock) : :

"memory"需要强调的是，为了和spin_lock相配合，我们在释放锁是必须将lock设置为1，而不能使用lock++的方式。

#define SPIN_LOCK_UNLOCKED (spinlock_t) { 1 SPINLOCK_MAGIC_INIT }

#define spin_lock_init(x) do { *(x) = SPIN_LOCK_UNLOCKED; } while(0)

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

#define spin_unlock_wait(x) do { barrier(); } while(spin_is_locked(x))

由于spin_trylock不需要自旋，实现中采用xchgb指令（该指令将自动锁总线，而不需要再使用lock前缀）。若lock原来的值为1，说明未上锁，因此返回为真，表明成功获得锁；否则返回为假。static inline int spin_trylock(spinlock_t *lock){ char oldval; __asm__ __volatile__( "xchgb %b0,%1" :"=q" (oldval), "=m" (lock->lock) :"0" (0) : "memory"); return oldval > 0;}

自旋锁的应用在讨论自旋锁的应用时，我们一般区分两种平台：单处理器非抢占式内核和对称多处理器或抢占式内核。在前面我们看到，在单处理器非抢占式内核下，自旋锁根本不存在。这体现了一种出色的设计策略，既然没有别人能够同时刻执行，就没有理由加锁。对于抢占式内核，我们将它等同于对称多处理器来考虑。

1． 用户上下文之间如果数据结构只可能被用户上下文访问，最高效的办法就是使用信号量。（我们在后面将讨论信号量机制）。

2． 用户上下文与softirq之间这种情况下，使用spin_lock_bh()/spin_unlock_bh()可以满足要求。如果是单处理器非抢占式内核，自旋锁消失了，spin_lock_bh等同于local_bh_disable，会进制在用户上下文时进制softirq，从而避免用户上下文和softirq同时进入临界区。如果是对称多处理器或者抢占式内核，即使是在不同CPU上的用户上下文和softirq同时运行，自旋锁机制保证了只有一个持有者，只有在它释放锁之后，另一个才能进入临界区。

3． 用户上下文和Tasklet/Timer之间同上。同加锁观点来看，Tasklet和Timer的地位是同样的。

4． Tasklet或Timer之间这里有两点需要说明：

（1）同一时刻，一个Tasklet或Timer不会同时在两个CPU上执行；

（2）如果CPU已经处在Tasklet或Timer中，它不会同时再执行其它的Tasklet或Timer。因此我们只需要考虑在不同CPU上运行两个不同Tasklet或Timer的情况，而这种情况只需要使用自旋锁机制，即spin_lock和spin_unlock函数。

5． Softirq之间或和Tasklet/Timer之间同一个softirq可能在不同的CPU上执行，同上道理，使用spin_lock和spin_unlock可以在不同CPU的同一个或不同softirq，或者Softirq与Tasklet或Timer之间保护共享数据。

6． 硬件中断之间如果被保护的共享资源在软中断（包括tasklet和timer）或进程上下文和硬中断上下文访问，那么在软中断或进程上下文访问期间，可能被硬中断打断，从而进入硬中断上下文对共享资源进行访问，因此，在进程或软中断上下文需要使用spin_lock_irq和spin_unlock_irq来保护对共享资源的访问。 而在中断处理句柄中使用什么版本，需依情况而定，如果只有一个中断处理句柄访问该共享资源，那么在中断处理句柄中仅需要spin_lock和spin_unlock来保护对共享资源的访问就可以了。 因为在执行中断处理句柄期间，不可能被同一CPU上的软中断或进程打断。但是如果有不同的中断处理句柄访问该共享资源，那么需要在中断处理句柄中使用spin_lock_irq和spin_unlock_irq来保护对共享资源的访问。在使用spin_lock_irq和spin_unlock_irq的情况下，完全可以用spin_lock_irqsave和spin_unlock_irqrestore取代，具体应该使用哪一个也需要依情况而定，如果可以确信在对共享资源访问前中断是打开的，那么使用spin_lock_irq更好一些，因为它比spin_lock_irqsave要快一些。但是如果不能确定是否中断使能，那么使用spin_lock_irqsave和spin_unlock_irqrestore更好，因为它将恢复访问共享资源前的中断标志而不是直接打开中断。 当然，有些情况下需要在访问共享资源时必须禁止中断，而访问完后必须打开中断，这样的情形使用spin_lock_irq和spin_unlock_irq最好

====

http://hi.baidu.com/greatren518/blog/item/f438df348c226eb3d1a2d346.html