Spin-lock技术与应用.doc

Spin-lock技术及应用在 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 结构来讨论，它的结构内容是这样子的： typedefstructvolatileunsignedintlock;spinlockt;说穿了，不过就是一个 unsigned int 型别的变数而已，但可不要小看这小小的变数，螺丝钉虽小，功能却是不可忽视的。 使用 spinlockspinlocktxxxlock=SPIN_LOCK_UNLOCKED;unsignedlongflags;spinlockirqsave(&xxxlock,flags).criticalsection.spinunlockirqrestore(&xxxlock,flags)这一组的函式在使用上是最保险的，用的频率也算是最多的。首先在使用前，必须先宣告一个 spinlock_t 型别的变数，并把初始值设为 SPIN_LOCK_UNLOCKED。除此之外，还必须有一个unsigned long型别的变数，这个变数是用来将 CPU 的 flag（旗标）储存起来的，等 critical section 执行完了，再把 flag 的值设回到系统里。使用上是很简单明白的。这两个 function 除了可以在 SMP 的环境下使用外，在UP的环境里也是同样可行的，接下来，我们来看看它们程序码是怎幺写的。 在 这个档案里定义了 spin_lock_irqsave() 及 spin_lock_irqrestore() 这两个 function。 #definespin_lock_irqsave(lock，flags)dowhile(0)#definespin_unlock_irqrestore(lock，flags)dowhile(0)local_irq_save(flags) 做的事就是将 CPU 的 flag 值先储存到 flags 变数里，然后将 CPU 的中断 diable 掉。这里将 CPU 的中断 disable 是指将执行这段 code 的 CPU，并不是指全部的 CPU。 也就是说它只会 disable local CPU 的中断。我们可以在里看到这样的程序码： #definelocal_irq_save(x)_asm_volatile_(pushfl;popl%0;cli:=g(x):/*noinput*/:memory)#definelocal_irq_restore(x)_asm_volatile_(pushl%0;popfl/*nooutput*/: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) 会变成什幺样子。 #definespin_lock(x)(void)lock#definespin_unlock(x)dowhile(0)简单吧，根本什幺事都没有做，所以，在 UP 的环境底下，我们如果将上面那段 spinlock 的使用扩展开来的话，会变成下面这个样子。 spinlock_txxx_lock=SPIN_LOCK_UNLOCKED;unsignedlongflags;local_save_flags(flags);cli();.criticalsection.local_restore_flags(flags);而这也正是在 UP 环境下，用来保护重要资料结构的写法。这也就是为什幺在介绍spinlock_t 的结构内容时，我们说在UP环境底下这个结构就算是空的也不会影响到 spinlock 的功效，因为根本没用到里面的栏位，但是在 SMP 底下，这就很重要了。 SMP 环境下的 Implementation在 SMP 的环境底下， spin_lock() 和 spin_unlock() 这两个函式的原始码是放在 中。 externinlinevoidspin_lock(spinlock_t*plock)_asm_volatile_(spin_lock_string:=m(_dummy_lock(plock);其实，这段程序码是经过我削减后的，至于削减掉的程序码是用来做 debug 的，所以，就不列出来，有兴趣的朋友不彷自行去看看。在上图中，spin_lock_string 是一个 macro，加上 asm 语法，我将它展开成下面这个样子： externinlinevoidspin_lock(spinlock_t*plock)1:lock;btsl,plock;jc2f;.section.text.lock,ax2:testb,plock;rep;nop;jne2b;jmp1b;.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 而已。 #defineSPIN_LOCK_UNLOCKED(spinlock_t)所以，检查其状态就变成了 spin_lock() 的首要工作，如果已被锁住，则 CPU 就不能去使用它所保护的资料结构，而如果没上锁，则可以从 spin_lock() 传回，接下去使用它所保护的资料。所以，检查其状态我们可以检查 spinlock_t.lock 的第 0 个 bit。btsl , plock 会将 plock 的第 0 个 bit 值传到 flag 旗标的 carry 并把 plock 的第 0 个 bit 设为 1，其中 是在 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() 就会发觉简单多了。 #definespin_unlock(lock)_asm_volatile_(spin_unlock_string:=m(_dummy_lock(lock)其中，spin_unlock_string 一样是个 macro，展开后变成下面这个样子: spin_unlock(plock)lock;btrl,plock;btrl , 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_txxx_lock=RW_LOCK_UNLOCKED;unsignedlongflags;read_lock_irqsave(&xxx_lock，flags);.criticalsectionthatonlyreadstheinfo.read_unlock_irqrestore(&xxx_lock，flags);write_lock_irqsave(&xxx_lock，flags);.readandwriteexclusiveaccesstotheinfo.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这组函式的原始码是怎幺样子的： #defineread_lock_irqsave(lock，flags)dolocal_irq_save(flags);read_lock(lock);while(0)#defineread_unlock_irqrestore(lock，flags)doread_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 环境底下是这个样子的： #defineread_lock(lock)(void)(lock)/*Notunusedvariable.*/#defineread_unlock(lock)dowhile(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);.lock) : : memory static inline void spin_lock(spinlock_t *lock) _asm_ _volatile_( spin_lock_string :=m (lock-lock) : : memory); static inline void spin_unlock(spinlock_t *lock) char oldval = 1; _asm_ _volatile_(spin_unlock_string ); 如果将上面的语句转化成纯汇编的话，则是这样： spin_lock(lock) 1: lock ; decb %0 js 2f .section .text.lock, ax 2: cmpb ,%0 rep;nop jle 2b jmp 1b .previous 其中%0就是函数参数传进来的lock-lock，下面详细地解释一下每一条 汇编指令： * lock ; decb %0 decb将lock-lock减1，它前边的lock指令表示在执行decb的时候，要锁住内存总线（memory bus），另外的CPU不能访问内存，以保证decb指令的原子性。注意，decb并不是原子操作（atomic operation），它需要将变量从内存读出来，放入寄存器（register），减1，再写入内存。如果在这时候另外的CPU也进行同样的操作的时候，那么decb的执行结果就会不确定，也就是说，操作的原子性遭到了破坏。 * js 2f 如果decb的结果小于0，表示无法取得spin lock，则跳到标签为2的指令（f表示向前跳）。如果decb的结果等于0，表示已经获得spin lock，执行下一条指令，则跳出整段代码，函数返回。注意, j2 2f的下一条指令并不是cmpb ,%0。 * .section .text.lock, ax .previous 从.section到.previous的这一段代码被用来检测spin lock何时被释放。linux定义了一个专门的区(.text.lo