ARM中的原子指令

MagicBoy2010

作者：Dolphin

不知道原子指令是否是正规叫法，这里主要想说的是ARM中用来实现多处理器/并发同步原语的指令，比如ARM-based Linux内核中的信号量，spin_lock的实现机制。想到写这么个帖子，是因为昨天在写spin_lock在ARM和x86处理器上的代码实现时，个人觉得那篇帖子更侧重在软件的实现上。当时阅读这段代码时查了下ARM相关指令，尤其是核心的LDREX和STREX，相对我以前掌握的ARM指令(V6以前的版本），有了不小的变化，当时为了理清spin lock的软件实现原理，只是大概看了下这两条指令，并没有深究下去，所以有可能有错误的地方。我今天抽空又看了V6上相关的知识点，有些心得，就发个帖子总结一下，防止以后忘了再捡起来又浪费时间。

在V6以前，实现信号量时用得是SWP指令。但是根据V6的文档，SWP已经out了 ，取而代之的是LDREX和STREX。我想随着时间的推移，今后ARM上实现原子操作的话，可以不用再考虑SWP了，既然人的脑容量有限，干脆忘了SWP吧。

废话说了不少，现在切入正题。信号量和spin lock这些东西最核心的事情基本上就是load-update-store序列，为了防止并发，必须保证这个序列是原子的，所谓原子，即处理器在执行这个指令序列时，得绝对占有处理器而不能够被切换出去。在ARM上，从V6开始，指令LDREX和STREX就是用来干这事的。下面详细分析一下这两条指令的过人之处：
1. LDREX--这条指令主要是从memory中取一个数，然后放到register中，但是相比普通的LDR指令，在于其内在的原子操作特性。先看一下这条指令的伪码：
MemoryAccess(B-bit, E-bit)
if ConditionPassed(cond) then
       processor_id = ExecutingProcessor()
       Rd = Memory[Rn,4]
       physical_address = TLB(Rn)
       if Shared(Rn) == 1 then
             MarkExclusiveGlobal(physical_address,processor_id,4)
       MarkExclusiveLocal(physical_address,processor_id,4)

ConditionPassed用来检查处理器的某些状态位，以确定该指令是否执行。如果要执行，并进入then后面的指令执行体。执行体的前三条指令比较好理解，我们重点看后面的语句：
     if Shared(Rn) == 1 then
                 MarkExclusiveGlobal(physical_address,processor_id,4)
       MarkExclusiveLocal(physical_address,processor_id,4)

Share(Rn)是说Rn所对应的memory是否在（多）处理器之间是共享的，如果是，标记一个全局的Exclusive标志，如果不是共享的，就不标记全局的。最后一句是标记一个Local的Exclusive标志，不管Rn所对应的memory是否有共享特性。

原帖链接：http://www.embexperts.com

MagicBoy2010

理解后面的MarkExclusiveGlobal(physical_address,processor_id,4)和MarkExclusiveLocal(physical_address,processor_id,4)需要消耗一定的脑细胞，如果从实用角度，作为一个底层驱动程序的开发者，理解了Linux内核中的信号量和自旋锁的软件实现原理已经足够，因为99.9%的读者并没有多少机会要亲自写一个信号量和自旋锁的实现（如果要自己写这么个东东，那么透彻理解ARM中的这种为实现并发共享而存在的指令原理是必需的），再则海豚自己也比较懒，一看ARM的手册上大篇幅的讲解这种并发共享原理就有点害怕，而且现在要学的东西太多，有些东西了解个大概其实是一种很明智的选择。三国时候诸葛亮就是个典型，《三国演义》第三十七回（司马徽再荐名士 刘玄德三顾草庐）有精彩的描写： ...徽曰：“孔明与博陵崔州平，颖川石光元，汝南孟公威与徐元直四人为密友。此四人务于精纯，惟孔明独观其大略。...”

所以海豚这里偷懒啦，把ARM V6手册上的两条重要的段落摘录于下，再加一点点自己的理解作为小点评，供同学们参考：

1.MarkExclusiveGlobal(<physical_address>,<processor_id>,<size>) records the fact that processor
<processor_id> has requested exclusive access covering at least <size> bytes from address
<physical_address>. The size of region marked as exclusive is IMPLEMENTATION DEFINED, up to a
limit of 128 bytes, and no smaller than <size>, and aligned in the address space to the size of the
region. It is UNPREDICTABLE whether this causes any previous request for exclusive access to any
other address by the same processor to be cleared.

2.MarkExclusiveLocal(<physical_address>,<processor_id>,<size>) records in a local record the fact
that processor <processor_id> has requested exclusive access to an address covering at least <size>
bytes from address <physical_address>. The size of the region marked as exclusive is
IMPLEMENTATION DEFINED, and can at its largest cover the whole of memory, but is no smaller than
<size>, and is aligned in the address space to the size of the region. It is IMPLEMENTATION DEFINED
whether this also performs a MarkExclusiveGlobal(<physical_address>,<processor_id>,<size>).

上面的这两段文字很好很强大，即使是出来打酱油的同学也应该好好读一读的。海豚已经把相关的内容精简到上面这两段了，如果再能耐着性子看完下面的STREX的伪代码，简历上也许就可以号称精通ARM processor   :

STREX operation:
if ConditionPassed(cond) then
       processor_id = ExecutingProcessor()
       physical_address = TLB(Rn)
       if IsExclusiveLocal(physical_address,processor_id,4) then
               if Shared(Rn) == 1 then
                         if IsExclusiveGlobal(physical_address,processor_id,4) then
                                   Memory[Rn,4] = Rm
                                   Rd = 0
                                  ClearExclusiveByAddress(physical_address,processor_id,4)
                         else
                                  Rd = 1
               else
                        Memory[Rn,4] =Rm
                        Rd = 0
       else
               Rd = 1
       ClearExclusiveLocal(processor_id)

MagicBoy2010

下来我根据自己的磋磨，竭尽全力用史上最直白的语言举个巨恶俗的例子，希望读者能理解海豚的良苦用心:
（为简单起见，假定处理器A和B，在共享内存单元C的情况下执行__raw_spin_lock代码，这时C=&lock->lock）
A处理器在执行__raw_spin_lock的时候，执行完ldrex        %0, [%1]语句出现context switch，B处理器开始执行__raw_spin_lock中的代码，故事就开始了...

常看动物世界的同学，知道某些动物为了tag一下新发现的领地属于自己，一般的行为是在那里撒泡尿。这里的C就是我们说的新发现的领地，在没有被发现之前，它是出于Open Access状态之中，意味着属于全体劳动人民。在某年某月某日的某个阳光明媚的午后，动物A发现了C，很兴奋的撒了泡尿tag了C，意思是从现在开始你就属于我胡汉三了，于是C处于Exclusive Access状态，向世人昭示：老娘我名花有主了。很不幸，A刚tag好了C，上帝一巴掌把A打到了一边，让动物B出场并发现了C，虽然此时C处于Exclusive Access状态，但是B依然可以在C上做LDREX操作，而C状态保持不变（依然为Exclusive Access）。接下来A和B __raw_spin_lock代码中的STREX的执行则比较令人费解，两种情况：1. A先执行 2.B先执行。V6的手册上讲得不是很详细，也或许我没能耐心仔细挖掘，总之这里的困惑是：当B在A之后去tag C时， C处于Exclusive Access总是对的，问题在于processor id。如果这种情况Global Monitor里记录的是(A and B) Exclusive Access upon C，那么不论A和B谁先执行接下来的STREX，update memory的操作总会成功，并且%0=0，并且同时会让C处于Open Access。这样，最后一次的STREX将作用在一个处于Open Access状态上的C，总会失败（%0=1, lock->lock不会被更新）。但是也有可能Global Monitor里记录的是(B only) Exclusive Access upon C，也就是说B的tag C的操作会覆盖A的操作以至于完全抹去了A的痕迹，这种情况下如果A先执行STREX。这里我没有搞清楚，做个简单推断：Global Monitor会记录最近一个processor id。这样对照V6上Shared Memory里面的状态转换图就好理解了，否则第一个STREX会update memory，但是C依然处于Exclusive Access状态，那么第二个STREX依然会成功update memory。因此，如果推断是对的，那么最近一次执行LDREX的处理器才可能最终获得锁。这里存疑...

总结：LDREX和STREX在单条指令里通过硬件逻辑实现的Monitor, State Machine和Memory Access的管理，为多处理器/并发实现了一个互斥的load-update-memory机制。

MagicBoy2010

3楼帖子对STREX和LDREX的理解有点问题，实际上因为global monitor存在的缘故，行为就类似于nested ldrex and strex pair

super皮波

正好看到这里，有一个问题请教一下，麻烦你帮着看看，各个指令的执行顺序按序号标注
cpu a                                                                                                                                                           cpu b，不用排他访问address
1.ldrex  a    address执行完这条指令的时候 被中断                                                                                                         2     ldr a address
2.xxxxx                                                                                                                                                                3     a+1
3.strex  a address中断返回之后，cpu b访问过address，这时strex这个会成功吗                                                                   4    str a address
回复 3# MagicBoy2010


   

super皮波

请忽略5楼的提问
正好看到这里，有一个问题请教一下，麻烦你帮着看看，各个指令的执行顺序按序号标注
cpu a                                                                                                                                                           cpu b，不用排他访问address
1.ldrex  a    address执行完这条指令的时候 被中断                                                                                                         2     ldr a address
5.xxxxx                                                                                                                                                                3     a+1
6.strex  a address中断返回之后，cpu b访问过address，这时strex这个会成功吗                                                                   4    str a address
回复 4# MagicBoy2010