Objective-C Runtime中的并发内存释放

Mac和iOS代码中的核心是Objective runtime机制，而runtime的核心是objc_msgSend方法，objc_msgSend的核心是方法缓存机制。今天我们将探索Apple如何在线程安全的情况下改变方法缓存内存的大小和释放，而同时又不影响性能。

1. 消息发送概念

objc_msgSend的工作原理就是为发送的方法找寻到适合的方法实现，并跳转到这个方法实现上。伪码大致如下：

IMP loopUp(id obj, SEL selector) {
    Class cls = object_getClass(obj);

    while(cls) {
        for(int i=0; i<cls->numMethods; i++) {
            Method m = c->methods [i];
            if (m.selector == selector) {
                return m.imp;
            }
        }
        cls = cls->superClass;
    }
    return _objc_msgForward;
}

2. 方法缓存

如果寻找一个方法的实现是全局搜索，那么必将是非常慢的。方法缓存就是解决方法，它把用过的方法存到哈希表中。每个类存一个哈希表，这张表中存有方法和和对应的实现。objc_msgSend使用汇编语言快速搜索这个哈希表，这个搜索的事件数量级是纳秒级的。当然第一次由于没有缓存，所以会比较慢。但是第二次有了缓存之后将会非常快。

一提到缓存，一般就指的是快速获得最近使用的资源的有限内存。比如说，图片缓存，从网络上获取到图片后，一般会缓存下来。等到下次使用的时候，就不用从网络上获取，而直接从缓存中获取。而且这个缓存会有大小限制，因此到达限制后，新图片会替换最老的图片。

这对很多问题是一种解决方法，但是它会有一些性能问题。比如，缓存是40张图片，但是刚好你的应用经常用到第41张新图片，这样缓存就会变得不怎么有效。

如果是我们自己的应用，我们可以调节缓存的大小来应对这种问题。但是Objective-C runtime却无法这样做。因为方法缓存对性能是非常重要的，所以runtime没有对缓存大小做限制并会扩展缓存大小来缓存所有被发送的方法。

3. 大小改变、释放和线程

改变缓存的大小从概念上来讲非常简单。伪码如下：

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, ^{
    free(oldCache);
});

这样也同样会产生上面那个问题，只是刚好发生在5s后。

如果定死一个时间延迟释放不好的，那就一直等待知道不出现这种场景。让我们增加一个计数器，伪码如下：

gInMsgSend++;
lookUpCache(class->cache);
gInMsgSend--;

如果考虑到线程安全的话，这个计数器得是atomic。

使用计数器的话，缓存重新申请的伪码应该是这样：

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(gOldCacheList, oldCache);
if(!gInMsgSend) {
    for (cache in gOldCacheList) {
        free(cache);
    }
    gOldCacheList.clear();
}

以上的版本跟Objective runtime的实现非常接近。

5. 零花费标识

在这中间有两部分极度不对称。objc_msgSend侧每秒跑数亿次并且需要尽可能快。另一方面，改变缓存大小是一个少见的操作，且通常随着程序的运行变得越来越少见。一旦程序达到平稳状态，不再加载新代码或者编辑消息列表，并且缓存变得足够大时，改变缓存大小的操作将不再发生。在那之前，它可能发生数百或者数千次直到缓存增大到符合需求的大小，但是和objc_msgSend操作相比，它是非常少的，而且对性能的影响也是很小的。

因为这种不对称，最好在消息发送侧尽可能小，即使它会使缓存释放部分变慢。在每个缓存空闲操作中以100万个CPU周期为代价削减objc_msgSend中的一个CPU周期，这是一个极大的胜利。

即使一个全局的计数器是花费巨大的。这是objc_msgSend种的两个额外的内存访问，会增加大量的开销。他们需要具备atomic和使用memory barrier。幸好，Objective-C runtime有一种技术可以使objc_msgSend得花销降到0，其代价是使缓存释放变的更慢。

全局计数器的目的是追踪任何线程是否在特定的代码区域内。线程已经有了跟踪他们当前正在运行的代码的东西：程序计数器。这是跟踪当前指令内存地址的CPU寄存器。我们可以检查每个线程的程序计数器，看它是否在objc_msgSend中，而不是用全局计数器。如果所有线程都在外面，那么释放旧缓存是安全的。伪码如下：

BOOL ThreadsInMsgSend(void) {
    for(thread in GetAllThreads()) {
        uniptr_t pc = thread.GetPC();
        if (pc >= objc_msgsend_startAddresss && pc <= objc_msgSend_endAddress) {
            return YES;
        }
    }
    return NO;
}

bucket_t *oldCache = class->cache;
class->cache = malloc(newSize);
append(gOldCacheList, oldCache);
if(!ThreadsInMsgSend) {
    for (cache in gOldCacheList) {
        free(cache);
    }
    gOldCacheList.clear();
}

objc_msgSend根本没做任何特殊的事情。它可以直接访问缓存，而不用担心标记访问。伪码如下：

lookUpCache(class->cache);

6. 真实的代码

Apple的实现能在runtime函数_collecting_in_critical中看到，它在objc-cache.mm中。
至关重要的程序计数器存储在全局变量中：

OBJC_EXPORT uinptr_t objc_entryPoints[];
OBJC_EXPORT uinptr_t objc_exit Points[];

实际上有多个objc_msgSend实现（像struct返回），内部的cache_getImp函数也直接访问缓存。他们都需要被检查从而安全释放缓存。

函数本身不带任何参数，并返回int，它只是作为一个布尔标志来表示是否有任何线程处于关键函数中：

static int _collecting_in_critical(void) {

我将跳过这个函数中不那么有趣的代码，以便集中精力于最好的部分。如果你想看到整个实现，请参阅opensource.apple.com。

获取线程信息的API位于内核级。 task_threads获得一个给定任务中的所有线程的列表（内核进程的术语），这个代码使用它来获取在自己的进程中的线程：

    ret = task_threads(mach_task_self(), &threads, &number);

这将返回线程中的thread_t值的数组，以及数量中的线程数。然后循环它们：

    for (count = 0; count < number; count++) {

为一个线程提取程序计数器是在一个单独的函数中完成的，我们简短的看以下：

        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是x86-64上PC的寄存器名称; R代表“注册”，IP代表“指令指针”。

入口点和出口点本身在汇编语言文件中定义。他们看起来像这样：

.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

第一种模式，把垃圾留到下一次，用于正常缓存大小调整。循环模式总是释放在运行时的方法产生的缓存垃圾，并且刷新所有类的所有缓存，因为这通常会产生大量的垃圾。从代码中可以看出，只有在启用将所有消息发送到文件的调试日志记录工具时才会发生这种情况。它会刷新缓存，因为消息缓存会干扰日志记录。

7. 结论

性能和线程安全往往彼此相互矛盾。访问和共享数据往往存在不对称性，这使得线程安全性更高。全局标志或计数器能够指出哪些操作访问数据是不安全的。在Objective-C runtime中，Apple更进一步的使用每个线程的程序计数器来指出线程何时执行不安全操作。这是一个专门的案例，很难看到这个技术在哪里会用到，但是分析它很有趣。

8. 参考

Concurrent Memory Deallocation in the Objective-C Runtime