Abstract
动态内存分配器 (malloc/free) 在多线程环境下依靠互斥锁来保护共享数据的一致性. 使用锁在性能, 可用性, 健壮性, 程序灵活性方面有很多缺点. Lock-free 的内存分配器能消除线程延迟或被杀死以及 CPU 的调度策略对程序的性能影响. 这篇 paper 呈上了一个完整的无锁内存分配器. 它的实现只使用被广泛支持的操作系统 API 和硬件原子指令. 即使出现线程中断 (thead termination) 或死机故障(crash-failure), 它也是可用的. 由于是无锁的, 它避免了死锁的情况. 另外, 我们的分配器是高度可扩展的, 我们把空间溢出限制为常数因子, 同时能够避免 false sharing. 另外, 我们的分配器有优越的并发性能和极低的延迟.
1. Introduction
动态内存分配函数在多线程应用中广泛使用, 应用范围从商业数据库, web 服务器到数据挖掘, 科学性质应用. 目前的分配器使用互斥锁来保证线程安全.
Lock-free 同步 (synchronization) 是一个合适的实现线程安全的替换方案. 它有以下优点:
免疫死锁
异步信号安全(asynv-signal-safety): 如果使用了互斥锁, 他们将不会使用信号, 因为无法保证异步信号安全. 假设一个线程持有用户级的锁, 这时它接受到一个信号, 信号处理程序调用分配器, 该程序也会请求同样的互斥锁, 但是被中断的线程正持有这个锁. 信号处理程序等待被中断的线程释放互斥锁, 但是, 在信号处理程序完成前, 线程不会恢复. 这就造成了死锁. 因此, 在使用互斥锁后, 这些实现智能屏蔽中断或者在 malloc,free 时使用内核级别的锁. 但是这样会损失很多性能. 相反, 一个无锁分配器能够保证异步信号安全, 而不损失任何性能.
容忍优先倒置(tolerance to priority inversion): 用户级别的锁很容易因为优先倒置导致死锁. 高优先的线程 A 等待一个低优先的线程 B 释放锁, 但是直到高优先的 A 完成前, 低优先的线程 B 不会被调度. 无锁同步能够无视线程的调度策略.
Kill-tolerant availability: 一个无锁对象能够免疫死锁, 即使在任意多的线程在操作它时被 kill. 这对于高可用的服务器很有用, 这能使程序容忍不频繁的进程损失, 来缓解临时的资源短缺.
抢占容忍(preemption-tolerance): 当一个线程持有互斥锁时, 其他线程抢占了处理器, 但是由于抢占线程也在等待同样的锁, 因此抢占线程不能执行下去. 从持有锁的线程被抢占, 到处理器重新调度持有锁的线程完成任务并施放锁, 这之间的时间相当于是被浪费的时间. 而无锁同步不在意线程的调度情况.
每个线程从自己的堆上请求内存, 并释放块 (blocks) 到自己的堆上. 然而, 这是难以接受的解决方案, 因为这导致了无限的内存消耗. 即使这个程序的内存需求实际上很小. 其他不可接受的特点, 包括需要初始化很大一片地址空间, 人为设置总体大小. 限制特定线程或特定内存块大小的地址的预请求区域. 可接受的方案应该是广泛适用且节省空间的, 不应该强加对地址空间的使用限制.
为了建设我们的无锁分配器只使用简单的当前主流处理器支持的原子指令, 我们把 malloc 和 free 分解为几个原子操作, 组织分配器的数据结构
2. 原子指令
我们只需处理器支持 Compare-and-swap(CAS)或者 load-linked 和 store-conditionnal(LL/SC)的组合两者之一即可. 像 fetch-and-add 或者 swap 都可以由 CAS 或 LL/SC 实现.
3. 实现
这个实现是在 64 位地址空间的. 32 位的版本会更加简单. 同时 64 位的 CAS 操作兼容 32 位架构.
首先, 我们来介绍这个分配器的结构. 大型 blocks 将直接从 OS 请求, 并释放到 OS. 对于小型 blocks. 较大的 superblocks(比如 16KB)组成 heap. 每一个 superblock 分割为多个大小相等的 block.superblock 根据 block 的 size 分布在 size classes 中. 每个 size class 包含多个 processor heap(即 procheap 结构),heap 的数量与处理器的数量成正比. 每个 processor heap 最多有一个 active 状态的 superblock.active 状态的 superblock 包含一个及以上数量的可用 block. 当用户请求一个可用 block,superblock 将会把一个可用 block 设为保留状态, 以此保证线程能通过 processor heap 的地址访问到 block. 每一个 superblock 对应一个 descriptor 结构. 每一个被请求的 block 包含 8 字节的指向 superblock 的前缀. 在第一次调用 malloc 时, size classes 结构和 procheap 结构 (about 16 KB for a processor machine) 将被请求并初始化.
调用 mallock 时, procheap 一般已经有一个活跃状态的 superblock 了. 线程原子地读取指向 active superblock(descriptor 结构)的指针, 并保留一个 block. 然后, 线程原子地从 superblock 中 pop 一个 block, 并更新 descriptor 结构. 调用 free 时, push 一个被释放的 block 到原先 superblock 的可用 block 的列表中, 并更新 descriptor 结构.
之前我们讲述了三个主要结构: size class 结构(保存),procheap 结构, 和 descriptor 结构. 这里, 还有两个辅助结构, anchor 结构和 active 结构. anchor 是 decriptor 的辅助结构. Active 是 procheap 的辅助结构. 如果 proheap 结构中的 active 域不为 NULL, 那就说明当前有 active 状态的 superblock 可用. 当调用 malloc, 线程读取 active 结构, 原子地对 credits 减 1, 然后验证 active superblock 是否仍然为 active.
- // Superblock descriptor structure
- typedef anchor : // fits in one atomic block
- unsigned avail:10, //index of the first available block in the superblock
- count:10, //count holds the number of unreserved blocks in the superblock
- state:2, //state holds the state of the superblock
- tag:42; //is used to prevent the ABA problem
- // state codes ACTIVE=0 FULL=1 PARTIAL=2 EMPTY=3
- typedef descriptor :
- anchor Anchor;
- descriptor* Next;
- void* sb; // pointer to superblock
- procheap* heap; // pointer to owner procheap
- unsigned sz; // block size
- unsigned maxcount; // superblock size/sz
- // Processor heap structure
- typedef active :
- unsigned ptr:58, //a pointer to the descriptor of the active superblock owned by the processor heap
- credits:6; // number of blocks available for reservation in the active superblock less one
- typedef procheap :
- active Active; // initially NULL
- descriptor* Partial; // initially NULL
- sizeclass* sc; // pointer to parent sizeclass
- // Size class structure
- typedef sizeclass :
- descList Partial; // initially empty
- unsigned sz; // block size
- unsigned sbsize; // superblock size
在 descriptor 结构中的 Anchor 域包含有原子更新的子域. 子域 avail 持有这个 super block 中第一个可用内存块的 index. 子域 count 持有 superblock 中已使用的内存块的个数. 子域 state 持有 superblock 的状态. 子域 tag 用来避免 ABA 问题.
处理器堆结构中的 active 域是指向该处理器拥有的当前活跃的 superblock 的 descriptor 的指针. 如果 active 的值不为 NULL, 就保证了活跃 superblock 有至少一个内存块可用. 子域 credits 持有活跃 superblock 可用内存块数减 1, 如果 credits 的值为 n, 那么 superblock 包含 n+1 个可用内存块. 在一个典型的 malloc 操作中(比如当 active!=NULL and credits>0), 线程在验证活跃 superblock 仍然有效后, 读取 active 然后原子地对 credits 减 1.
superblock 有以下四种状态: active,full,partial,empty.ACTIVE 表示这个 superblock 在这个堆中是活跃 superblock, 或者一个线程正试图将它安装为 active.FULL 表示这个 superblock 中所有 block 都已经被分配或被保留. PARTIAL 表示这个 superblock 是非 ACTIVE 的, 并且包含未保留的可用的 block.EMPTY 表示如果 free 这个 superblock 是安全操作.
malloc 算法.
如果 block 的 size 很大, block 将直接从 OS 请求内存, 它的前缀被设置为与 size 相关. 不然, 相应的堆用被请求的 block 大小和线程 id 标记. 然后, 线程试图以下述顺序请求 block.
从堆的活跃 superblock 请求一个 block.
如果没有活跃的 superblock, 试图从 PARTIAL 的 superblock 请求一个 block.
如果都没有, 那么请求一个新的 superblock 并尝试设置了 ACTIVE
- void* malloc(sz) {
- // Use sz and thread id to find heap.
- heap = find heap(sz);
- if (!heap) // Large block
- Allocate block from OS and return its address.
- while(1) {
- addr = MallocFromActive(heap);
- if (addr) return addr;
- addr = MallocFromPartial(heap);
- if (addr) return addr;
- addr = MallocFromNewSB(heap);
- if (addr) return addr;
- } }
Malloc form active superblock 算法
绝大多数 malloc 请求经由此算法返回. 此算法主要分为两步. 第一步 (代码 1-6) 请求读取指向 active superblock 的指针然后原子地对 active 结构中的 credits 域减 1. 对 credits 减 1 这个动作保留出 1 个 block, 然后检查 active superblock 是否仍然有效. 在 CAS 成功之后, 线程保证了 1 个 block 被保留且可用. 第二步 (代码 7-18) 对 LIFO(即栈)进行 lock-free 的 pop 操作. 线程从 anchor.avail 域中读取第一个可用 block 的 index, 然后读取下一个可用 block 的 index. 最后验证之前读取的第二个 index 确实为现在栈中的第二个 index, 然后把指针指向第二个可用 block.
仅当 anchor.avail 等于 oldanchor.avail 时才验证为有效. 线程 X 从 anchor.avail 从读取了值 A, 从 * addr 中读取了值 B. 读取 B 后, 其他线程抢占了 CPU 并 pop 了 block A, 又 pop 了 block B, 最后 push 了 block A 回来. 之后, 线程 A 恢复了, 并执行 CAS. 如果没有 anchor.tag 域, CAS 将会发现 anchor 等于 oldanchor 并错误地执行 swap 操作, 实际上, 第二个可用 block 已经不是 block B 了. 为了防止这个 ABA 问题, 我们使用了 IBM 经典的 tag 机制. 每当 pop 时, 我们都对 anchor.tag 加 1. 这样, 在上述情况发生时, 由于 anchor.tag 不等于 oldanchor.tag,CAS 操作将会正确地返回 false, 程序返回循环顶部. tag 的位数 (bits) 必须足够大, 因为它只能递增. 使用 LL/SC 原子操作能在原理层面避免 ABA 问题.
13-17 行, 线程检查这次操作是否提取了最后一个 credit. 如果确实是最后一个(credit==0), 那么检查 superblock 是否有更多可用的 block(由于 descriptor.maxcount 大于 MAXCREDITS 或者有 block 刚被 free). 如果有更多 block 可用(count>0), 线程将尽可能多地保留 block. 否则(count=0), 将这个 superblock 声明为 FULL
当这个线程提取了 credit, 它会试着执行 UpdateActive 函数来更新 Active 结构. 多线程同时提取向一个 superblock 提取 credit 并没有 ABA 问题. 最后, 线程存储 descriptor 结构的地址到新请求的 block 的最前部, 以便于当 block 之后被 free 时能确定这个 block 来自于哪个 superblock. 每个 block 包含 8 字节的前部.
在行 6 的 CAS 成功后, 行 18 的 CAS 成功前, superblock 的状态可能由 ACTIVE 变为 FULL 或 PARTIAL, 或者变为另一个 procheap 的 active superblock(但是必须是同一个 size class). 但是这些都对原线程没有影响.
- void* MallocFromActive(heap) {
- do { // First step: reserve block
- newactive = oldactive = heap->Active;
- if (!oldactive) return NULL;
- if (oldactive.credits == 0)
- newactive = NULL;
- else
- newactive.credits--;
- } until CAS(&heap->Active,oldactive,newactive);
- // Second step: pop block
- desc = mask credits(oldactive);
- do {
- // state may be ACTIVE, PARTIAL or FULL
- newanchor = oldanchor = desc->Anchor;
- addr = desc->sb+oldanchor.avail*desc->sz;
- next = *(unsigned*)addr;
- newanchor.avail = next;
- newanchor.tag++;
- if (oldactive.credits == 0) {
- // state must be ACTIVE
- if (oldanchor.count == 0)
- newanchor.state = FULL;
- else {
- morecredits = min(oldanchor.count,MAXCREDITS);
- newanchor.count -= morecredits;
- }
- }
- } until CAS(&desc->Anchor,oldanchor,newanchor);
- if (oldactive.credits==0 && oldanchor.count>0)
- UpdateActive(heap,desc,morecredits);
- *addr = desc; return addr+EIGHTBYTES;
- }
- UpdateActive
当 heap 上没有 active superblock 时, 调用 UpdateActive 会将 desc->sb 重新注册为当前 active 的 superblock. 然而, 在重新注册之前, 其他线程有可能注册了一个新的 superblock. 如果发生后述的情况, 当前线程必须返回 credit, 并把 superblock 设为 PARTIAL, 再放入 procheap.partial 中, 以供将来使用.
- UpdateActive(heap,desc,morecredits) {
- newactive = desc;
- newactive.credits = morecredits-1;
- if CAS(&heap->Active,NULL,newactive) return;
- // Someone installed another active sb
- // Return credits to sb and make it partial
- do {
- newanchor = oldanchor = desc->Anchor;
- newanchor.count += morecredits;
- newanchor.state = PARTIAL;
- } until CAS(&desc->Anchor,oldanchor,newanchor);
- HeapPutPartial(desc);
- }
- MallocFromPartial
当线程发现 procheap.active==NULL 时, 它会调用 mallocFromPartial. 线程试图调用 HeapGetPartial 来获取 PARTIAL 状态的 superblock. 如果成功获取了一个 superblock, 它会尽可能多地保留 block, 在行 10 的 CAS 成功之后, 线程成功保留了多个 block. 然后从它保留的 block 中 pop 一个出来供该线程使用, 如果还有多余的 block, 就将这个 superblock 设为 active, 否则设为 FULL.
在 HeapGetPartial 中, 线程首先试图从 procheap.partial 从提取 superblock, 如果提取不到, 那么从对应的 size class 的 partial list 中提取.
- void* MallocFromPartial(heap) {
- retry:
- desc = HeapGetPartial(heap);
- if (!desc) return NULL;
- desc->heap = heap;
- do { // reserve blocks
- newanchor = oldanchor = desc->Anchor;
- if (oldanchor.state == EMPTY) {
- DescRetire(desc); goto retry;
- }
- // oldanchor state must be PARTIAL
- // oldanchor count must be> 0
- morecredits = min(oldanchor.count-1,MAXCREDITS);
- newanchor.count -= morecredits+1;
- newanchor.state = (morecredits> 0) ? ACTIVE : FULL;
- } until CAS(&desc->Anchor,oldanchor,newanchor);
- { // pop reserved block
- newanchor = oldanchor = desc->Anchor;
- addr = desc->sb+oldanchor.avail*desc->sz;
- newanchor.avail = *(unsigned*)addr;
- newanchor.tag++;
- } until CAS(&desc->Anchor,oldanchor,newanchor);
- if (morecredits> 0)
- UpdateActive(heap,desc,morecredits);
- *addr = desc; return addr+EIGHTBYTES;
- }
- descriptor* HeapGetPartial(heap) {
- do {
- desc = heap->Partial;
- if (desc == NULL)
- return ListGetPartial(heap->sc);
- } until CAS(&heap->Partial,desc,NULL);
- return desc;
- }
- Malloc from new superblock
如果线程找不到 PARTIAL 状态的 superblock, 它将调用 mallocFromNewSB. 线程调用 DescAlloc 请求一个新的 descriptor, 然后初始化这个 descriptor(行 2-11). 最后, 用 CAS 尝试在 procHeap.active 注册这个 superblock. 当注册失败, 说明有新的 active superblock 已经注册, 那么就删除该线程生成的这个 desciptor 和对应的 superblock, 去使用那个已注册的 active superblock. 当然你也可以使用自己注册的这个 superblock, 并设置为 PARTIAL. 我们为了避免太多的 PARTIAL superblock 和因此产生的不必要的碎片, 我们更倾向于直接 free 这个 superblock.
在内存一致性 (memory consistency) 弱于顺序一致性 (sequential consistency) 的系统中, 处理器可能无序地执行和观察内存访问, 内存屏障可以用来确保内存访问的顺序. 行 12 的内存屏障确保在该 superblock 注册成功前, 相应的 descriptor 结构同步到其他处理器. 如果没有这个内存屏障, 在 CAS 之后, 其他处理器上的线程可能读到过时的值.
- void* MallocFromNewSB(heap) {
- desc = DescAlloc();
- desc->sb = AllocNewSB(heap->sc->sbsize);
- Organize blocks in a linked list starting with index 0.
- desc->heap = heap;
- desc->Anchor.avail = 1;
- desc->sz = heap->sc->sz;
- desc->maxcount = heap->sc->sbsize/desc->sz;
- newactive = desc;
- newactive.credits =
- min(desc->maxcount-1,MAXCREDITS)-1;
- desc->Anchor.count =
- (desc->maxcount-1)-(newactive.credits+1);
- desc->Anchor.state = ACTIVE;
- memory fence.
- if CAS((&heap->Active,NULL,newactive) {
- addr = desc->sb;
- *addr = desc; return addr+EIGHTBYTES;
- } else {
- Free the superblock desc->sb.
- DescRetire(desc); return NULL;
- }
- }
后面还有些 free 算法和性能检测, 就不翻译了
[Paper 翻译]Scalable Lock-Free Dynamic Memory Allocation
来源: http://www.bubuko.com/infodetail-2709037.html