[原创]Linux内核里的同步机制（1）—— 原子操作

platero

[原创]Linux内核里的同步机制（1）—— 原子操作

原子操作 –单一的不可中断的操作。

首先看一个counter++的例子(Sch[94])。

在汇编层次，这一条语句会变成3个指令，
1.将counter值从内存中拷贝到CPU寄存器R0。
2.寄存器R0中的值加1。
3.将寄存器的值拷回到内存。

如果此时有两个CPU同时执行counter++，那么假设counter初始值为0，两次加1所得出来的结果就不是2，而是1，Bug由此而生。
这是一个SMP的例子。类似的，对于UP来说，如果两个任务“同时”执行counter++，那么同样会出现此问题。“同时”上面加了引号，那是因为UP永远不会真的同时，不过如果在1->2或者2->3之间切换到了另一个任务或者被中断，而此任务或中断例程也执行counter++，就有可能产生这个BUG。

如何避免上面这个问题？首先我们必须保证了1->2->3是一个单一步骤，不被“打断”（这里的打断只是逻辑意义上的，而不是特指我们通常说的中断，后文可以看到在ARMV6以上的平台，原子操作中间也是可以发生中断的）。而对于SMP，还需要保证对临界内存的访问是互斥的。

Linux内核为原子操作提供了类型atomic_t和一组内核API，使用起来非常简单。原子版的counter++如下：

atomic_t counter =ATOMIC_INIT(0);
atomic_inc（&counter);

atomic_t相关的原子操作由平台代码负责实现，不同的处理器会采用不同的方式，目的都是为了上面说的两个保证。

那Linux内核如何保证这组API的原子性呢？
1.保证不能被打断。

从字面上理解，就是要禁止上下文切换，禁止中断发生。这个很容易实现，只要保证在这个原子操作的时候不发生中断就可以了。所以通过关本地中断就可以实现。简单粗暴而又有效。
2.保证对共享内存的访问是互斥的。
这一点和具体平台紧密相连。一般来说，可以通过Bus锁或者其他的对内存访问的互斥机制实现。Linux理应交给平台代码去实现。

以ARM为例，分析一下代码。以下代码均来自2.6.35.11。
在代码中，发现共有两种实现，分别为ARMV6之前，ARMV6之后。

在ARMV6之前的实现如下，

#ifdef CONFIG_SMP
#error SMP not supported onpre-ARMv6 CPUs
#endif
static inline intatomic_add_return(int i, atomic_t *v)
{
        unsignedlong flags;
        intval;

        raw_local_irq_save(flags);
        val= v->counter;
        v->counter= val += i;
        raw_local_irq_restore(flags);

        returnval;

}
#define atomic_add(i, v)       (void) atomic_add_return(i, v)

ARMV6之前不支持SMP，所以只要在具体实现里关中断就可以了。轻松实现两个保证。

再看ARMV6以后，

/*
* ARMv6UP and SMP safe atomic ops.  We use load exclusive and
* storeexclusive to ensure that these are atomic.  We may loop
* toensure that the update happens.
*/

static inline void atomic_add(inti, atomic_t *v)
{
        unsignedlong tmp;
        intresult;

        __asm____volatile__("@ atomic_add\n"

"1:     ldrex   %0, [%3]\n"
"       add     %0, %0,%4\n"
"       strex   %1, %0,[%3]\n"
"       teq     %1, #0\n"
"       bne     1b"
        :"=&r" (result), "=&r" (tmp), "+Qo"(v->counter)
        :"r" (&v->counter), "Ir" (i)
        :"cc");

}

这里出现了几个问题，首先，在实现上没有区分UP和SMP。其次，也没有关中断及加总线锁的动作。那么这个函数如何保证原子性呢？上面有段注释很有价值。说是采用了loadexclusive和storeexclusive确保其原子性。读一下汇编发现最后一行的意思是当strex的返回值不为0时(%1,即tmp)，会跳转到1重新执行一遍。所以最后一行注释说“Wemay loop to ensure that the update happens.”。那么strex又是什么？

查了一下ARM用户手册[AARM]，终于在A2.9找到了上面所有问题的答案。
ldrex和和strex是AMRV6引入的新的同步机制，取代了过去的SWP和SWPB指令。ldrex就是Load-Exclusive的缩写，而strex就是Store-Exclusive的缩写。这两个指令与addressmonitor协同工作，为内存的访问提供了一个状态机。对于SMP和UP来说，这种机制稍有不同。简单地讲，对于非共享内存的情况(UP)，只需要维护一个monitor就可以了。而对于共享内存的情况(SMP)，需要为每一个CPU维护一个monitor，状态机就复杂一些。但是这些区别在指令的层次上是体现不出来的。所以，使用了ldrex和strex，就不需要为UP和SMP单独实现一套原子操作。

ARM到底是如何实现这种新的同步机制的？道理上很简单。简单地说，指令ldrex会为执行处理器做一个标记(tag)，说当前对该物理地址已经有一个CPU访问了，但是还没有访问完毕。当strex指令执行时，就会检查是否存在这个标记。如果存在，那么将完成这次store的过程，并且返回0，然后清除该标记。如果没有这个标记，不会完成store，返回1。这样就能够在不关闭中断，没有执行任何buslock的情况下，保证操作的原子性。详细过程请参阅ARM用户手册[AARM]。

根据Linux内核里面atomic_add的实现，分析一个UP上的并发情景。(SMP上会复杂一点，但是大体意思相同）



• 首先会执行指令ldrex，添加一个标记(Tag)，说明执行CPU标记了一个物理地址，但访问尚未完毕。
• 假设此时发生了中断，在中断处理或者切换了上下文后需要对该值进行原子加一。
• 在新上下文中执行指令ldrex，strex。由于此时有标记，strex会成功执行，而后更新内存，清除标记。
• 假设此时中断返回，被中断的任务继续进行。当执行strex时，会发现标记已被清除，此时strex就不会更新内存，并且返回1。
• 跳转到1(bne        1b)，重新执行。
  

上面只是一个理论过程，但是查资料的时候发现一个patch[LKM]，说有一些互斥机制使用了LDREX/STREXEQ的组合，当使用这些机制的代码并发时，就可能出现LDREX和STREXEQ执行不成对的情况(STREXEQ是条件执行，未必每次都能得到执行），这样就无法保证原子性了。为了解决这个问题，就在exceptionhandler推出时，显式的调用一下clrex或者strex，这样就相当于在每次中断结束后，手动清理一下标记。也就是说，在原子操作时，只要发生了中断，标记都会被清除。

总之，使用这种Load-exclusive和Store-exclusive机制，避免了关中断和总线锁，能够显著提高效率。


参考资料：
[Sch94] Curt Schimmel: UNIX Systems for Modern Architectures: Symmetric
Multiprocessingand Caching for Kernel Programmers. Addison Wesley, 1994
[LKM]http://lists.infradead.org/pipermail/linux-arm-kernel/2009-September/000665.html
[AARM]ARM Architecture Reference Manual


转载请注明原帖出处：http://bbs.t268.com/forum.php?mod=viewthread&tid=828&extra=

platero

自己给自己加精了~~~