Linux內(nèi)核同步機(jī)制之原子操作

一、源由

我們的程序邏輯經(jīng)常遇到這樣的操作序列：

1、讀一個(gè)位于memory中的變量的值到寄存器中

2、修改該變量的值（也就是修改寄存器中的值）

3、將寄存器中的數(shù)值寫回memory中的變量值

如果這個(gè)操作序列是串行化的操作（在一個(gè)thread中串行執(zhí)行），那么一切OK，然而，世界總是不能如你所愿。在多CPU體系結(jié)構(gòu)中，運(yùn)行在兩個(gè)CPU上的兩個(gè)內(nèi)核控制路徑同時(shí)并行執(zhí)行上面操作序列，有可能發(fā)生下面的場景：

多個(gè)CPUs和memory chip是通過總線互聯(lián)的，在任意時(shí)刻，只能有一個(gè)總線master設(shè)備（例如CPU、DMA controller）訪問該Slave設(shè)備（在這個(gè)場景中，slave設(shè)備是RAM chip）。因此，來自兩個(gè)CPU上的讀memory操作被串行化執(zhí)行，分別獲得了同樣的舊值。完成修改后，兩個(gè)CPU都想進(jìn)行寫操作，把修改的值寫回到memory。但是，硬件arbiter的限制使得CPU的寫回必須是串行化的，因此CPU1首先獲得了訪問權(quán)，進(jìn)行寫回動(dòng)作，隨后，CPU2完成寫回動(dòng)作。在這種情況下，CPU1的對(duì)memory的修改被CPU2的操作覆蓋了，因此執(zhí)行結(jié)果是錯(cuò)誤的。

不僅是多CPU，在單CPU上也會(huì)由于有多個(gè)內(nèi)核控制路徑的交錯(cuò)而導(dǎo)致上面描述的錯(cuò)誤。一個(gè)具體的例子如下：

系統(tǒng)調(diào)用的控制路徑上，完成讀操作后，硬件觸發(fā)中斷，開始執(zhí)行中斷handler。這種場景下，中斷handler控制路徑的寫回的操作被系統(tǒng)調(diào)用控制路徑上的寫回覆蓋了，結(jié)果也是錯(cuò)誤的。

二、對(duì)策

對(duì)于那些有多個(gè)內(nèi)核控制路徑進(jìn)行read-modify-write的變量，內(nèi)核提供了一個(gè)特殊的類型atomic_t，具體定義如下：

從上面的定義來看，atomic_t實(shí)際上就是一個(gè)int類型的counter，不過定義這樣特殊的類型atomic_t是有其思考的：內(nèi)核定義了若干atomic_xxx的接口API函數(shù)，這些函數(shù)只會(huì)接收atomic_t類型的參數(shù)。這樣可以確保atomic_xxx的接口函數(shù)只會(huì)操作atomic_t類型的數(shù)據(jù)。同樣的，如果你定義了atomic_t類型的變量（你期望用atomic_xxx的接口API函數(shù)操作它），這些變量也不會(huì)被那些普通的、非原子變量操作的API函數(shù)接受。

具體的接口API函數(shù)整理如下：

三、ARM中的實(shí)現(xiàn)

我們以atomic_add為例，描述linux kernel中原子操作的具體代碼實(shí)現(xiàn)細(xì)節(jié)：

（1）ARMv6之前的CPU并不支持SMP，之后的ARM架構(gòu)都是支持SMP的（例如我們熟悉的ARMv7-A）。因此，對(duì)于ARM處理，其原子操作分成了兩個(gè)陣營，一個(gè)是支持SMP的ARMv6之后的CPU，另外一個(gè)就是ARMv6之前的，只有單核架構(gòu)的CPU。對(duì)于UP，原子操作就是通過關(guān)閉CPU中斷來完成的。

（2）這里的代碼和preloading cache相關(guān)。在strex指令之前將要操作的memory內(nèi)容加載到cache中可以顯著提高性能。

（3）為了完整性，我還是重復(fù)一下匯編嵌入c代碼的語法：嵌入式匯編的語法格式是：asm(code : output operand list : input operand list : clobber list)。output operand list 和 input operand list是c代碼和嵌入式匯編代碼的接口，clobber list描述了匯編代碼對(duì)寄存器的修改情況。為何要有clober list？我們的c代碼是gcc來處理的，當(dāng)遇到嵌入?yún)R編代碼的時(shí)候，gcc會(huì)將這些嵌入式匯編的文本送給gas進(jìn)行后續(xù)處理。這樣，gcc需要了解嵌入?yún)R編代碼對(duì)寄存器的修改情況，否則有可能會(huì)造成大麻煩。例如：gcc對(duì)c代碼進(jìn)行處理，將某些變量值保存在寄存器中，如果嵌入?yún)R編修改了該寄存器的值，又沒有通知gcc的話，那么，gcc會(huì)以為寄存器中仍然保存了之前的變量值，因此不會(huì)重新加載該變量到寄存器，而是直接使用這個(gè)被嵌入式匯編修改的寄存器，這時(shí)候，我們唯一能做的就是靜靜的等待程序的崩潰。還好，在output operand list 和 input operand list中涉及的寄存器都不需要體現(xiàn)在clobber list中（gcc分配了這些寄存器，當(dāng)然知道嵌入?yún)R編代碼會(huì)修改其內(nèi)容），因此，大部分的嵌入式匯編的clobber list都是空的，或者只有一個(gè)cc，通知gcc，嵌入式匯編代碼更新了condition code register。

大家對(duì)著上面的code就可以分開各段內(nèi)容了。@符號(hào)標(biāo)識(shí)該行是注釋。

這里的__volatile__主要是用來防止編譯器優(yōu)化的。也就是說，在編譯該c代碼的時(shí)候，如果使用優(yōu)化選項(xiàng)（-O）進(jìn)行編譯，對(duì)于那些沒有聲明__volatile__的嵌入式匯編，編譯器有可能會(huì)對(duì)嵌入c代碼的匯編進(jìn)行優(yōu)化，編譯的結(jié)果可能不是原來你撰寫的匯編代碼，但是如果你的嵌入式匯編使用__asm__ __volatile__(嵌入式匯編)的語法格式，那么也就是告訴編譯器，不要隨便動(dòng)我的嵌入?yún)R編代碼哦。

（4）我們先看ldrex和strex這兩條匯編指令的使用方法。ldr和str這兩條指令大家都是非常的熟悉了，后綴的ex表示Exclusive，是ARMv7提供的為了實(shí)現(xiàn)同步的匯編指令。

LDREX , []

是base register，保存memory的address，LDREX指令從base register中獲取memory address，并且將memory的內(nèi)容加載到(destination register)中。這些操作和ldr的操作是一樣的，那么如何體現(xiàn)exclusive呢？其實(shí)，在執(zhí)行這條指令的時(shí)候，還放出兩條“狗”來負(fù)責(zé)觀察特定地址的訪問（就是保存在[]中的地址了），這兩條狗一條叫做local monitor，一條叫做global monitor。

STREX , , []

和LDREX指令類似，是base register，保存memory的address，STREX指令從base register中獲取memory address，并且將 (source register)中的內(nèi)容加載到該memory中。這里的保存了memeory 更新成功或者失敗的結(jié)果，0表示memory更新成功，1表示失敗。STREX指令是否能成功執(zhí)行是和local monitor和global monitor的狀態(tài)相關(guān)的。對(duì)于Non-shareable memory（該memory不是多個(gè)CPU之間共享的，只會(huì)被一個(gè)CPU訪問），只需要放出該CPU的local monitor這條狗就OK了，下面的表格可以描述這種情況

開始的時(shí)候，local monitor處于Open Access state的狀態(tài)，thread 1執(zhí)行LDREX 命令后，local monitor的狀態(tài)遷移到Exclusive Access state（標(biāo)記本地CPU對(duì)xxx地址進(jìn)行了LDREX的操作），這時(shí)候，中斷發(fā)生了，在中斷handler中，又一次執(zhí)行了LDREX ，這時(shí)候，local monitor的狀態(tài)保持不變，直到STREX指令成功執(zhí)行，local monitor的狀態(tài)遷移到Open Access state的狀態(tài)（清除xxx地址上的LDREX的標(biāo)記）。返回thread 1的時(shí)候，在Open Access state的狀態(tài)下，執(zhí)行STREX指令會(huì)導(dǎo)致該指令執(zhí)行失?。]有LDREX的標(biāo)記，何來STREX），說明有其他的內(nèi)核控制路徑插入了。

對(duì)于shareable memory，需要系統(tǒng)中所有的local monitor和global monitor共同工作，完成exclusive access，概念類似，這里就不再贅述了。

大概的原理已經(jīng)描述完畢，下面回到具體實(shí)現(xiàn)面。

其中％3就是input operand list中的"r" (&v->counter)，r是限制符（constraint），用來告訴編譯器gcc，你看著辦吧，你幫我選擇一個(gè)通用寄存器保存該操作數(shù)吧。％0對(duì)應(yīng)output openrand list中的"=&r" (result)，=表示該操作數(shù)是write only的，&表示該操作數(shù)是一個(gè)earlyclobber operand，具體是什么意思呢？編譯器在處理嵌入式匯編的時(shí)候，傾向使用盡可能少的寄存器，如果output operand沒有&修飾的話，匯編指令中的input和output操作數(shù)會(huì)使用同樣一個(gè)寄存器。因此，&確保了％3和％0使用不同的寄存器。

（5）完成步驟（4）后，％0這個(gè)output操作數(shù)已經(jīng)被賦值為atomic_t變量的old value，毫無疑問，這里的操作是要給old value加上i。這里％4對(duì)應(yīng)"Ir" (i)，這里“I”這個(gè)限制符對(duì)應(yīng)ARM平臺(tái)，表示這是一個(gè)有特定限制的立即數(shù)，該數(shù)必須是0～255之間的一個(gè)整數(shù)通過rotation的操作得到的一個(gè)32bit的立即數(shù)。這是和ARM的data-processing instructions如何解析立即數(shù)有關(guān)的。每個(gè)指令32個(gè)bit，其中12個(gè)bit被用來表示立即數(shù)，其中8個(gè)bit是真正的數(shù)據(jù)，4個(gè)bit用來表示如何rotation。更詳細(xì)的內(nèi)容請(qǐng)參考ARM ARM文檔。

（6）這一步將修改后的new value保存在atomic_t變量中。是否能夠正確的操作的狀態(tài)標(biāo)記保存在％1操作數(shù)中，也就是"=&r" (tmp)。

（7）檢查memory update的操作是否正確完成，如果OK，皆大歡喜，如果發(fā)生了問題（有其他的內(nèi)核路徑插入），那么需要跳轉(zhuǎn)到lable 1那里，從新進(jìn)行一次read-modify-write的操作。