Objective-C Runtime中的并發內存分配
本文由翻譯自mikeash的博客，原文：Concurrent Memory Deallocation in the Objective-C Runtime
譯者：lynulzy（社區ID,博客） 校對：唧唧歪歪（博客）
Objective-C的Runtime機制是Mac和iOS程序中的核心，而objc_msgSend函數是Runtime的核心，進言之，這個函數的核心正是方法緩存。今天將代領大家探索蘋果是如何以一種線程安全且不影響程序性能的方式來調整和分配方法緩存所用內存的，其所用的技術也許是在其他關于線程安全的資料中從未使用的。
消息轉發的概念
Objc_msgSend方法的工作方式是為發送過來的方法查找恰當的方法實現，并且跳轉到該實現中的方式工作。用官方的說法來講，查找方法的過程是這樣的：
IMP lookUp(id obj, SEL selector) {
Class c = object_getClass(obj);
while(c) {
for(int i = 0; i < c->numMethods; i++) {
Method m = c->methods[i];
if(m.selector == selector) {
return m.imp;
}
}
c = c->superclass;
}
return _objc_msgForward;
} 【注】代碼中的一些變量名已經替換，如果你對原始代碼有興趣可以去下載一份Objective-C runtime的[源碼](http://www.opensource.apple.com/source/objc4/)
方法緩存
在Objective-C的程序中，消息發送隨處可見，如果對每一條消息都執行完整的消息搜索，那將會使程序變得異常遲鈍。
解決方法就是緩存，每一個類都擁有一個哈希表與之關聯,這個哈希表將選擇器映射到方法實現。使用哈希表的初衷正是為了最大限度的提高讀取速度，同時 objc_msgSend 使用了極其細致且高效的匯編源碼來快速執行哈希表的檢索，這使得在緩存模式下的消息發送僅維持在一個個位數的納秒量級上。當然，任何消息在第一次使用的時候很慢，以后將會非常快。
我們提到的緩存，是用來提高多次讀取最近使用資源的速度的，它通常也是有大小限制的。例如，你可能會緩存從網絡上加載的圖片，這樣連續2次讀取圖片就不會請求網絡2次了。但是，你又不想使用太多內存，所以你可能會給緩存圖片的數量設置一個最大值，當達到最大值，且又有新的圖片進來時，就可以把最舊的圖片刪掉。
在大多數情況下這是一種很好的解決方案，但是在一些隱蔽的情況下可能會有較差的表現。舉個例子，如果你把圖片緩存個數設置為40個，但是應用卻以41張一組這樣的規模循環圖片的話，你會忽然發現你的緩存策略失效了。
對于我們自己的應用，我們可以測試和調整緩存的大小以避免這種情況發生，但是Objective-C的Runtime機制并沒有這種條件。因為方法緩存對于性能極其嚴苛，并且每個條目都相對較小。runtime并不會強制的限制緩存區的大小，相反，它會在需要的時候擴充緩存區以保存所有已經被發送的消息。
請注意，緩存有時候會刷新；有一些操作會造成緩存數據過期，如在處理過程中加載入更多的代碼，或者改變一個類的方法列表，恰當的緩存區會被銷毀并且允許再次填充的。
改變緩存大小、分配內存以及線程問題
在概念上，改變緩存的大小簡單，就像這樣
bucket_t *newCache = malloc(newSize); copyEntries(newCache, class->cache); free(class->cache); class->cache = newCache;
Objective-C runtime 實際上在這里采用了一些捷徑，但是不會將舊的條目拷貝到新的緩存區！畢竟它僅僅是緩存而已，沒有必要保存數據，這些條目將在消息發送的時候再次被填充，所以，真實情況是這樣的：
free(class->cache); class->cache = malloc(newSize);
在單線程環境下，你需要做的僅有這些，那么這篇文章也本該很短。當然Objective - C runtime也必須要支持多線程，也就是說所有這些代碼都必須是線程安全的。任何給出的類的緩存，都可以從多個線程中被同時訪問，所以這些代碼必須考慮周全，確保可以應付這種場景。
寫到這里的代碼是無法處理多線程的情況的。在`釋放舊的緩存到分配新的緩存之前`這段時間內，其他線程也許會訪問這些已經失效的緩存指針，這會造成它使用的數據是垃圾數據，或者由于指定的內存并未映像物理地址出而立刻崩潰。
我們該如何解決這種問題？典型的保存共享數據的一種方法是加鎖，代碼如下：
lock(class->lock); free(class->cache); class->cache = malloc(newSize); unlock(class->lock);
為此，包括讀取在內的所有訪問都會被這個鎖控制。也就是說 *Objc_msgSend* 方法需要獲得這個鎖，查找緩存，然后放鎖。每次進行加鎖，解鎖操作都會增加許多開銷，考慮到緩存每次對自己的檢索只需要幾納秒時間，這對性能的影響太大了。
我們也許會嘗試通過一些其他方式關閉這個時間窗口（*釋放舊緩存到分配新緩存這個時間窗*）。例如，對緩存先分配地址并賦值，然后再去釋放舊的緩存如何？
bucket_t *oldCache = class->cache; class->cache = malloc(newSize); free(oldCache);
這會有一些幫助，但是并不能解決這個問題。另外一個線程也許會檢索舊的緩存指針，然后在他可以訪問內容之前通過系統先行占取這塊緩存。這塊舊的緩存在其他的線程再次運行之前被銷毀，之前的問題再次出現。
如果加一個像這樣的延遲呢？
bucket_t *oldCache = class->cache;
class->cache = malloc(newSize);
after(5 /* seconds */, ^{
free(oldCache);
}); 這幾乎是可行的。但還是有下面的情況，一個線程剛好被系統搶占了緩存，并且被搶占的時間足夠長，這樣延遲5秒的釋放就會先觸發。這使得崩潰的可能微乎其微,但也不能完全保證不會發生。
不采用一個隨機的延遲時間，一直等待到時間窗完全騰出來會怎么樣呢？我們對Objc_msgSend加一個計數器：
gInMsgSend++; lookUpCache(class->cache); gInMsgSend--;
一個恰當的線程安全版本需要用到計數器的原子性，合適的內存`阻隔`來確保依賴加載/存儲顯示正常。本文的目的不是討論這些，想象它們已經存在就好了。
在計數器的幫助下，緩存的再分配像是這樣：
bucket_t *oldCache = class->cache; class->cache = malloc(newSize); while(gInMsgSend) ; // spin free(oldCache);
注意到這里沒有必要阻塞執行objc_msgSend方法就可以正常工作。一旦釋放緩存的代碼確定在它替換了緩存指針之后，objc_msgSend中沒有東西了，這段代碼就會繼續向下執行，釋放舊的緩存區。其他線程可能會在舊的緩存區指針釋放的時候調用 Objc_msgSend 方法，但是這個相對較新的調用將不能再使用舊的指針，因此這種條件下是線程安全的。
不斷的循環是低效率且不夠優美的。釋放緩存并沒有那么緊急。釋放內存是好的，如果要花些時間也沒什么問題。與其低效的循環，不如讓我們保存一份未釋放緩存列表，每次當緩存釋放的時候會將所有等待中的操作全部執行完畢，上代碼:
bucket_t *oldCache = class->cache;
class->cache = malloc(newSize);
append(gOldCachesList, oldCache);
if(!gInMsgSend) {
for(cache in gOldCachesList) {
free(cache);
}
gOldCachesList.clear();
} 當一個新的發送消息在處理的過程中，這個操作不會立刻釋放舊的緩存，但這并不是問題。當再次訪問它、訪問之后的時候、或者將來的某個時間點會被釋放。
這個版本已經相當接近Objective-C Runtime機制的實際運行原理了。`
零耗費標志
這兩個交互的部分存在這極大的不對稱。Objc_msgSend這邊, 可能每秒會運行百萬次，并且的確是需要盡可能地快。最好的情況是單次調用的運行時間只需要幾納秒。另一方面，改變緩存區的大小是一個較少的操作，并且隨著app的持續運行將會變得越來越少。一旦應用達到了一種穩態，不在加載新的代碼，或者編輯消息列表，并且緩存變得足夠大而且能滿足所需的時候，緩存塊大小的重新計算操作將不會再發生。但在此之前，這個操作在緩存區增大到它所需的大小時或許會發生個幾百或者幾千次，但是與Objc_msgSend相比而言是極其小的，并且性能敏感性也更低。
由于這種不對稱性，在消息發送方應該放盡可能少的任務，即使這會使緩存釋放部分會變慢一些。在objc_msgSend的百萬級別CPU循環中每削減一個CPU運行循環累積下帶來的優勢與釋放操作是一個以巨大優勢的凈贏。
即使全局計數器花費太大。在objc_msgSend方法中的這兩個附加的內存訪問操作將仍然帶來很大的開銷。它們需要保持原子性并且使用內存隔離會使情況更糟。
幸運的是，Objective-C runtime機制有一個技術是以犧牲緩存釋放的速度來將objc_msgSend的開銷降為0。
假設全局計數器的目的在于追蹤任何在一個特定代碼區塊內的線程。這些線程已經有已有一些來監測當前它們是在哪段代碼中執行，它就是程序計數器（program counter）。這是一個CPU內部的寄存器，其功能在于記錄當前指令的內存地址。與全局計數器相比，我們可以檢查每個線程的程序計數器來確認他是否在執行objc_msgSend
。如果所有線程都沒有執行objc_msgSend方法，那么對它而言，釋放緩存就是安全的，代碼實現如下:
BOOL ThreadsInMsgSend(void) {
for(thread in GetAllThreads()) {
uintptr_t pc = thread.GetPC();
if(pc >= objc_msgSend_startAddress && pc cache;
class->cache = malloc(newSize);
append(gOldCachesList, oldCache);
if(!ThreadsInMsgSend()) {
for(cache in gOldCachesList) {
free(cache);
}
gOldCachesList.clear();
} 然后，objc_msgSend不必做任何其他的事情。它可以直接訪問緩存區，而不用給讀取加個標志，就像下面這樣：
lookUpCache(class->cache);
由于緩存釋放需要檢查進程中的每個線程的狀態，因此它是相對低效的。但是如果objc_msgSend只用考慮單線程的環境下，它的執行效率將會非常高。這值得做出權衡。這基本上就是蘋果的Runtime機制如何工作的。
實際的代碼
到底蘋果如何實現上述的技術可以在runtime的實現文件[objc-cache.mm]文件中的函數 _collection_in_critical 中找到。
關鍵的PC位置存儲在全局變量中：
OBJC_EXPORT uintptr_t objc_entryPoints[]; OBJC_EXPORT uintptr_t objc_exitPoints[];
實際上objc_msgSend有多種實現（比如返回結構體版本的），并且內部的cache_getImp 函數也會直接訪問緩存。這些都需要被檢查，以確保釋放緩存的安全性。
函數本身不需要參數，返回值是 **int**類型的，使用起來就像一個標志位一樣，用來標識在一個關鍵函數中是否有多個線程：
static int _collectiong_in_critical(void)
{ 為了專注于更好的代碼，我將會略過這個函數中一些無聊的代碼。如果你想看全部的代碼，在[這里](http://www.opensource.apple.com/source/objc4/objc4-646/runtime/objc-cache.mm)可以找到。
獲得線程信息的API位于mach層面。task_threads 獲得了給定任務中所有線程的線程列表，并且這些代碼使用它來獲得其所在進程中的其他線程。
ret = task_threads(mach_task_self(), &threads, &number);
它返回了一組包含了多個thread_t值的threads數組，并且可以獲得數組元素的個數，然后它會遍歷這些元素
for (count = 0; count < number; count++) { 取得一個線程的PC的操作在另外一個獨立的函數中，我們可以簡單看下：
pc = _get_pc_for_thread (threads[count]);
然后遍歷這些入口和出口，然后比較各個元素
for (region = 0; objc_entryPoints[region] != 0; region++)
{
if ((pc >= objc_entryPoints[region]) &&
(pc <= objc_exitPoints[region])) { result = TRUE; goto done; } } } 在循環結束后向調用者返回結果
return result; }
_get_pc_for_thread這個函數如工作？這是相對簡單代碼，它通過調用thread_get_state方法來獲得目標線程的寄存器狀態。它位于一個獨立的函數中的主要原因是寄存器狀態的結構是特定于系統架構的，因為每個架構下有著不同的寄存器。這就意味著這個函數對于每種支持的架構需要一個獨立的實現，盡管每種實現都幾乎是一樣的。這里有一個關于x86-64架構下的實現
static uintptr_t _get_pc_for_thread(thread_t thread)
{
x86_thread_state64_t state;
unsigned int count = x86_THREAD_STATE64_COUNT;
kern_return_t okay = thread_get_state (thread, x86_THREAD_STATE64, (thread_state_t)&state, &count);
return (okay == KERN_SUCCESS) ? state.__rip : PC_SENTINEL;
} 注意到`rip`是PC在x86-64架構下的名字，其中R代表"register",IP代表"instruction pointer";
入口點和出口點他們本身是在一個匯編語言文件中定義的，這個文件中同時還包含了問題中的一些其他函數，
.private_extern _objc_entryPoints _objc_entryPoints: .quad _cache_getImp .quad _objc_msgSend .quad _objc_msgSend_fpret .quad _objc_msgSend_fp2ret .quad _objc_msgSend_stret .quad _objc_msgSendSuper .quad _objc_msgSendSuper_stret .quad _objc_msgSendSuper2 .quad _objc_msgSendSuper2_stret .quad 0 .private_extern _objc_exitPoints _objc_exitPoints: .quad LExit_cache_getImp .quad LExit_objc_msgSend .quad LExit_objc_msgSend_fpret .quad LExit_objc_msgSend_fp2ret .quad LExit_objc_msgSend_stret .quad LExit_objc_msgSendSuper .quad LExit_objc_msgSendSuper_stret .quad LExit_objc_msgSendSuper2 .quad LExit_objc_msgSendSuper2_stret .quad 0
_collecting_in_critical 與我們上面假設的例子中的用法相似。它在釋放殘留的內存垃圾之前調用。runtime實際上有兩種獨立的模式：一種是留下垃圾知道下次再有其他線程進入臨界函數。另一個是不斷的循環直到清除干凈，而且通常會同時釋放這些垃圾內存。
// Synchronize collection with objc_msgSend and other cache readers
if (!collectALot) {
if (_collecting_in_critical ()) {
// objc_msgSend (or other cache reader) is currently looking in
// the cache and might still be using some garbage.
if (PrintCaches) {
_objc_inform ("CACHES: not collecting; "
"objc_msgSend in progress");
}
return;
}
}
else {
// No excuses.
while (_collecting_in_critical())
;
}
// free garbage here 第一種留下垃圾的模式是用于普通的緩存區重新計算的。通常會釋放垃圾的循環的模式用于runtime的清除所有類的所有緩存,這很顯然會產生喝多垃圾。通過對代碼的分析，這僅會在打印所有調試信息的調試設備這種情況下才會發生。它會清除緩存，正是于消息緩存會干涉日志輸出。
結論
性能和線程安全是一個矛盾體。不同的代碼快訪問共享數據要求更高的線程安全性這也是不平衡的。一個全局的標志或者計數器是一種利用這種特點的一種方法。在Objective-C的runtime機制中，蘋果采用了比這種策略更深層次的方法，它通過使用每個線程的程序計數器（PC）隱式的表明了什么時候一個線程正在執行一種不安全的操作。這是一個特例，并且其他地方很難看到這種方法的用武之地，但它本身很奇妙。
來源：mikeash