一、首先，什么是fastlock？
在 openser（一个开源的SIP协议路由程序）中，提供了四种互斥机制，分别是fastlock、pthread_mutex_lock、POSIX信号量、SYSV信号量。可以通过编译选项决定在openser中使用哪一种互斥机制。并且Makefile中介绍，这四种互斥机制的效率按前面列举的顺序从高到低排列。下面对这四种互斥机制做一些简单介绍：
1、信号量
为什么说它们最没效率呢？因为它们完全是借助系统调用来实现的……
2、pthread_mutex_lock
pthread_mutex_lock是linux线程库提供的互斥机制，不仅限于线程，进程也可以使用这种互斥机制（需要设置PTHREAD_PROCESS_SHARED选项）。
关于pthread_mutex_lock的实现，不同的linux线程库可能有不同的做法。linuxthreads库好像也是用内核的信号机制来实现的；而NTPL则使用了相对很先进的futex机制。
pthread_mutex_lock有一些额外考虑，比如递归加锁、进程间共享、等等。
3、fastlock
相比之下，fastlock就要更加单纯。
所谓fastlock，简单的讲，就是用一个整型值来表示锁（0值表示未上锁、1值表示上锁）。相应的lock和unlock操作就是对这个整型值的置1和 置0，而当锁的值为1时，lock操作需要等到锁的值变为0（被别的进程释放）后，才能完成。就这么简单，因此叫快锁。
当然，单纯的一个整型值是不能做到互斥这一点的。假设进程A发现锁a的值为0，于是准备对其上锁。而这时发生了调度，进程B开始执行并对锁a上锁。等调度回到进程A，它仍然认为锁a值是0（它并不知道发生了调度，不可能再回去检查一下锁），于是它也给a上锁了。
实际上，fastlock的互斥由两个原子操作来保证：tsl（相当于trylock，如果未上锁则上锁，并返回成功；否则返回失败）和release_lock（释放锁）。
这样，fastlock的lock操作就是不断地tsl，直到tsl成功（不成功则让别的进程先执行，然后再tsl）；而unlock操作就release_lock即可。
附、关于锁
以上这些锁的命名出于openser。而实际上，对于锁的实现一直以来主要分为两种方式。
1、由内核实现。进程的调度是由内核实现的，内核自然有办法解决进程间的互斥问题。由内核实现的锁其优点是在等待状态下获得锁的进程可以被内核唤醒；缺点是系统调用开销较大。比较适用于上锁不频繁、等待时间较长的情况；
2、由原子指令实现。就像上面说到的fastlock，它完全是用户态的程序，但是通过原子指令实现了互斥。这种做法的优点是上锁快；缺点是没有唤醒机制，等待锁的进程处于“忙等待”状，需要不断轮询；
自linux 2.6之后，出现了futex机制。这一机制实现的锁实际上是原子指令与内核配合实现的，结合了两种方式的优点。进程通过原子指令去检查锁和上锁，如果需要等待则通过futex系统调用进入睡眠。
NPTL库的pthread_mutex就是使用这种机制来实现的。
二、实现fastlock
正如我们前面看到的，实现fastlock的关键就是实现原子性的tsl和release_lock。如果用C语言实现，可能只有用另一种互斥操作把这个fastlock保护起来。但像这样使用一种锁来实现另一种锁，显然是不可取的。
所以，自然想到要用更底层的汇编来实现。linux内核代码中有atomic.h这个文件（每种CPU对应一个实现），里面就使用汇编语言，实现了多种原子操作。前面说到的信号量，就是建立在这一组原子操作之上的。
现在，让我们先来看看tsl的实现。tsl输入的参数是lock的地址，函数判断该地址上的值是否为0，是则将其置1，并返回成功；否则返回失败。
在X86下，这个功能可以这样实现：
关于gcc内嵌汇编语言的语法，可以参阅下面的文档：
http://www.ibiblio.org/gferg/ldp/GCC-Inline-Assembly-HOWTO.html
而上面这段代码的意思就是：将内存单元中的*lock与立即数1进行交换，交换以后，*lock的值为1（不管怎样，这个锁都是上定了），而lock的原值被交换到val变量中（如果lock原本已经被上锁，val值为1，此次上锁失败）。
在单处理器的情况下，一条CPU指令是不能被中断的，无论它进行了多么复杂的操作、经历了多少个时钟周期。而多处理器条件下情况就不一样了，哪怕内存的读- 改-写都在一条指令中，别的处理器也可能会与之发生冲突。唯一的办法就是锁住总线。庆幸的是xchg指令已经包含了锁总线的功能，所以即使在多处理器条件 下，上面的代码也不会有问题。（另外，非特权模式下的CPU也不应该能够直接执行锁总线操作，否则一个用户进程的恶意锁总线将导致整个系统的瘫痪。所以锁 总线的操作被封装在某个指令中供非特权模式下的CPU执行，这是个很自然的做法。）
再来看看powerpc下的tsl的实现：
powerpc是简单指令集，不会像X86那样提供对内存即读又写同时又锁总线的指令，所以实现tsl的代码看上去要多一些。
其中，lwarx与 stwcx.是ppc专用于互斥机制的指令。执行lwarx时，CPU会置一个标志位，有了该标志位，stwcx.才能执行成功，并且执行完stwcx. 后，标志位会自动清除。这样一来，当其间发生调度，多个lwarx与stwcx.指令序列交差执行时，多个lwarx都会成功，但是只有第一个 stwcx.会成功。所以写不成功是很正常的事，于是，stwcx.后都会跟一句bne-，不成功就返回重试。
而release_lock的代码就简单多了，直接将*lock置0。
X86的实现：
powerpc的实现：
三、使用fastlock遇到的问题
在使用openser v1.3.1进行二次开发时，openser使用fastlock作为互斥机制。使用过程中发现，由fastlock保护的临界区出现了访存冲突的现象。于是就fastlock的代码展开了研究。
首先发现了release_lock中的一处错误。release_lock函数除了上面列出的那段汇编代码外，其后还有一句"*lock = 0;"。
这样一来，*lock等于是两次被清0，如果在两次清0之间发生调度，别的进程对该lock上锁了，则再次调度回这个进程的时候，它又自动给lock解锁了。于是在lock真正被解锁之前，别的进程还可能对其上锁成功，并进入临界区，导致访存冲突。
除release_lock的问题外，之后又发现一个更隐蔽的错误。tsl的代码在gcc编译选项未添加-O优化选项（或指定了-O0）时，生成的目标代码有问题。通过objdump后得出下面的汇编代码：
用于立即数1和返回值val的寄存器使用冲突了（都使用了r0）。于是tsl永远都成功（总是把*lock的原值0写回去）。
参照linux内核代码atomic.h中的写法，对tsl做了修改：
这样的代码编译得出的目标代码就是正确的，无论编译时是否添加-O优化选项。
看到这样的结果，首先想到问题是出现"b"这个约束上，可能 是fastlock的代码编写不当。于是对ppc下，"b"约束的意义做了一些研究。ppc是简单指令系统，一条指令最多只支持一次内存访问。也就是说， 如果要以某个基址，访问某个偏移量，则必须先把基地址读入寄存器。如：
像这样的指令，就是以r31寄存器的值为基地址，24为偏移量的读操作。
ppc除支持寄存器值+偏移量的读操作外，也支持寄存器值+寄存器值的变地址读操作，如：
这就是以r30为基地址，r31为变地址的读操作。
其中r0~r31是ppc操作的32个通用寄存器。然而，有个例外，就是r0。如果以r0作为基地址，则表示基地址为0（不管r0里面的值是多少）。所以，关于r0的使用是有讲究的。
在gcc的汇编中，"r"约束表示装入任意寄存器，gcc可能会将其装入r0。如果这个值不是用来当基地址使用的，就没问题。否则，就需要使用"b"约束让gcc选择r0以外的寄存器。
在tsl函数中，被装入寄存器的是lock（类型为int*），而真正操作的是*lock，所以需要通过装入寄存器的lock的值来取出*lock。于是，fastlock的作者为保险起见，使用了"b"约束（尽管在读*lock时，lock的地址值是作为变地址）。
这样看来，造成tsl目标代码不正确的原因，似乎并不是"b"约束的误用，而是powerpc-linux-gcc的问题。无论如何，不应该生成同一寄存器被两个变量复用的代码。而上面的修改，就规避了gcc的错误。
这个观点似乎很正确了，但是在仔细阅读了前面链接给出的那篇关于gcc内嵌汇编语言的语法的文档，以及网络上的其他一些资料后，又发现了另外一个问题。原先 的tsl编译生成错误的目标代码，也并不是gcc的问题。问题的关键在于前面提到的另一处修改，把"=r"改成"=&r"。文档中对于'&'的解释是：
"&" : Means that this operand is an earlyclobber operand, which is modified before the instruction is finished using the input operands. Therefore, this operand may not lie in a register that is used as an input operand or as part of any memory address.
可以理解为：'&'表示该输出操作（'&'只用于修饰输出）完成于其他输入操作完成之前。因此需要确保对应寄存器中的值不能被其他的输入操作篡改。（怎样确保呢？输入输出使用不同的寄存器就行了。实际上'&'约束就是这个意思。）
一般而言，输出的内容都是由输入的内容来决定的。输入的变量先写入到寄存器，经过处理之后，原先输入的寄存器的值没必要再保留了，可以再利用这个寄存器写回输出的变量。此时输入和输出所使用的寄存器是可以重复的。
然而，像tsl的情况就不大一样。第一句lwarx指令就已经把输出寄存器准备好了，而此时输入值"立即数1"还没使用到。基于上面输入输出可以复用寄存器的原理，gcc可以让立即数1使用与输出的val变量相同的寄存器，于是出现了tsl生成的目标代码的错误。
而这里增加了'&'约束，就等于告诉了gcc，输出的值（val）可能在输入值（立即数1）被用到之前就已经准备好了，因此不能让它们使用同一个寄存器。
未使用'&'约束申明这一情况，导致目标代码寄存器使用冲突，这应该是tsl的BUG。
至此，由fastlock引发了上述这些关于互斥机制的研究、关于gcc内嵌汇编代码的研究、关于powerpc指令的研究。
