spinlock在X86的设计和实现

在Linux的内核中，spin lock用在多处理器环境中。当一个CPU访问一个临界资源 
(critical section)的时候，需要预先取得spin lock，如果取不到的话，它就在空循环 
等待，直到另外的CPU释放spin lock。由于涉及到多个处理器，spin lock的效率非常重要。 
因为在等待spin lock的过程，处理器只是不停的循环检查，并不执行其他指令。但即使这样， 
一般来说，spn lock的开销还是比进程调度(context switch）少得多。这就是spin lock 
被广泛应用在多处理器环境的原因。 

1. spin lock的数据结构 

/* include/asm-i386/spinlock.h */ 

typedef struct { 
volatile unsigned int lock; 
} spinlock_t; 

spin lock的数据结构很简单，只是一个整数变量lock， 如果lock等于1的话，表示 
这个spin lock是自由的；如果lock小于等于0的话，则表示spin lock已经被其他CPU所 
获取。 

2. spin lock的实现 

#define spin_lock_string 
"n1:t" 
"lock ; decb %0nt" 
"js 2fn" 
".section .text.lock,"ax"n" 
"2:t" 
"cmpb $0,%0nt" 
"rep;nopnt" 
"jle 2bnt" 
"jmp 1bn" 
".previous" 


#define spin_unlock_string 
"movb $1,%0" 
:"=m" (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,%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,%0"。 

* .section .text.lock, "ax" 
.previous 
从.section到.previous的这一段代码被用来检测spin lock何时被释放。linux定义了一个 
专门的区(.text.lock)来存放这段代码。它们和前边的"js 2f"并不在一个区（section）里， 
　　　　所以说"js 2f"的下一条指令并不是"cmpb $0,%0"。 
　　　　之所以定义成一个单独的区，原因是在大多数情况下，spin lock是能获取成功的，从.section 
　　　　到.previous的这一段代码并不经常被调用，如果把它跟别的常用指令混在一起，会浪费指令 
　　　　缓存的空间。从这里也可以看出，linux内核的实现，要时时注意效率。 

* 2: cmpb $0,%0 
　　rep;nop 
jle 2b 
jmp 1b 
检查lock->lock，和0比较，如果小于等于0（jle 2b），则跳回到标签2的指令，重新比较 
(b表示往回跳)。如果大于0，表示spin lock已经被释放，则往回跳回到标签1，重新试图 
　　　　　取得spin lock。 

　　* rep;nop 
这是一条很有趣的指令:)，咋一看，这只是一条空指令，但实际上这条指令可以降低CPU的运行 
　　　　频率，减低电的消耗量，但最重要的是，提高了整体的效率。因为这段指令执行太快的话，会生成 
　　　　很多读取内存变量的指令，另外的一个CPU可能也要写这个内存变量，现在的CPU经常需要重新 
　　　　排序指令来提高效率，如果读指令太多的话，为了保证指令之间的依赖性，CPU会以牺牲流水线 
　　　　执行（pipeline）所带来的好处。从pentium 4以后，intel引进了一条pause指令，专门 
　　　　用于spin lock这种情况，据intel的文档说，加上pause可以提高25倍的效率！ 

spin_unlock(lock) 
　　* movb $1,%0 
spin_unlock的实现很简单，只是重新将lock->lock置1就行了。 

　　还有一个问题我想谈的是，在linux 2.3以前，spin lock是用"lock; btrl $0,%0"来实现 
加锁的，但是后来的版本只使用了简单的mov指令，执行时间从22个时钟周期降低到1个时钟周期。 
但是最开始linus本人不同意这种做法，以为他以为由于intel芯片的指令重排序，会使斯spin lock 
的实现不稳定，但后来intel里的一个工程师出来澄清了linus的错误。这也许是open source的好处吧。 

　　spin lock的实现看起来简单，但是细微之处却很复杂，如果大家需要进一步理解，请细细读一下 
kernel的mail list和intel关于pentium的文档。