Inside AddressSanitizer Allocator

本文深入分析了 AddressSanitizer Allocator 的实现。

AddressSanitizer 通过 intercept malloc/free, new/delete 的调用，使得开启 ASan 后程序的内存分配和释放都由 ASan allocator 负责，本文深入分析了 AddressSanitizer Allocator 的实现。

ASan allocator 与其他 allocator 有一些明显不同的点，例如：

Memory Chunk

每当调用 malloc 或 new 申请一块内存时，ASan allocator 真正申请的内存大小是比用户请求的内存大小更大的。这是因为：一方面需要额外的内存来保存一些信息，如：用户申请内存的大小、申请内存时的 stacktrace 等；另一方面也需要在用户申请的内存左右两侧多申请内存作为 redzone，用于检测 heap-buffer-overflow bug。

我们将 ASan allocator 实际申请的内存块称为 memory chunk。由 ASan allocator 分配得到的 memory chunk 的布局如下所示：

 L L L L L L H H U U U U U U R R
   L -- left redzone words (0 or more bytes)
   H -- ChunkHeader (16 bytes), which is also a part of the left redzone.
   U -- user memory.
   R -- right redzone (0 or more bytes)

如上所示，memory chunk 中返回给用户使用的内存称为 user memory。ASan allocator 额外申请的紧邻 user memory 左右两侧的额外内存就是 redzone。

当 left redzone 的大小大于 ChunkHeader 的大小（即 16-bytes）时，ASan allocator 会将 magic value: kAllocBegMagic 存储到 memory chunk 的第一个 8-bytes 中，将 ChunkHeader 的地址保存在 memory chunk 的第二个 8-bytes 中：

 M B L L L L L L L L L  H H U U U U U U
   |                    ^
   ---------------------|
   M -- magic value kAllocBegMagic
   B -- address of ChunkHeader pointing to the first 'H'

ChunkHeader 的代码实现如下：

class ChunkHeader {
  atomic_uint8_t chunk_state;
  u8 alloc_type : 2;
  u8 lsan_tag : 2;

  // align < 8 -> 0
  // else      -> log2(min(align, 512)) - 2
  u8 user_requested_alignment_log : 3;

  u16 user_requested_size_hi;
  u32 user_requested_size_lo;
  atomic_uint64_t alloc_context_id;
};

static const uptr kChunkHeaderSize = sizeof(ChunkHeader);
COMPILER_CHECK(kChunkHeaderSize == 16);

当应用程序申请一块内存时，ASan allocator 需要计算为 user memory 添加 redzone 后所需要的内存大小 needed_size，伪代码如下：

uptr ComputeNeededSize(uptr size, uptr alignment) {
  const uptr min_alignment = ASAN_SHADOW_GRANULARITY;
  if (alignment < min_alignment)
      alignment = min_alignment;
  uptr rz_log = ComputeRZLog(size);
  uptr rz_size = RZLog2Size(rz_log);
  uptr rounded_size = RoundUpTo(Max(size, kChunkHeader2Size), alignment);
  uptr needed_size = rounded_size + rz_size;
  if (alignment > min_alignment)
      needed_size += alignment;
  if (!PrimaryAllocator::CanAllocate(needed_size, alignment))
      needed_size += rz_size;
  return needed_size;
}

  1. 首先根据用户申请的内存大小计算所需的 redzone 大小 rz_size。基本逻辑是用户申请的内存越大，则对应的 redzone 就越大。并且如前所述， rz_size 最小就是 ChunkHeader 的大小 16-bytes。

  2. 计算 rounded_size 是将 Max(size, kChunkHeader2Size) 对齐至 alignment，这是因为：对于已经释放的内存，ASan 需要像用 atomic_uint64_t alloc_context_id 保存申请内存的线程 id 和 stacktrace 一样，使用 atomic_uint64_t free_context_id 记录释放内存的线程 id 和 stacktrace。通过 Max(size, kChunkHeader2Size) 使得 chunk 中 user memory 的大小至少为 kChunkHeader2Size，这样 ASan 就可以通过复用 user memory 来保存 free_context_id 了。

    class ChunkBase : public ChunkHeader {
  atomic_uint64_t free_context_id;
};

static const uptr kChunkHeader2Size = sizeof(ChunkBase) - kChunkHeaderSize;
COMPILER_CHECK(kChunkHeader2Size <= 16);

  3. if (!PrimaryAllocator::CanAllocate()) needed_size += rz_size; ASan allocator 由 PrimaryAllocator 和 SecondaryAllocator 组成，优先从 PrimaryAllocator 中分配内存。由 PrimaryAllocator 分配的 chunk 只有 left redzone 没有 right redzone，这是因为 PrimaryAllocator 保证相同大小的 chunk 是相邻分布的，所以对于当前 chunk，可以使用相邻的右侧 chunk 的 left redzone 作为当前 chunk 的 right redzone。而 SecondaryAllocator 则没有这个保证，所以需要额外申请 rz_size 大小内存作为 right redzone。

Size Class

应用程序在申请内存时，ASan allocator 首先会计算添加 redzone 后所需要的内存大小 needed_size，如果小于等于 128KB，那么会由 PrimaryAllocator 进行分配。PrimaryAllocator 将分配的内存大小划分为了 53 个类别，称为 size class，每个 size class 都对应一个大小，比如 16-bytes, 32-bytes, 48-bytes。PrimaryAllocator 在真正申请内存时会 needed_size 向上取整到 size class 的大小，例如应用程序申请 8-bytes 的内存，添加 redzone 后所需要的内存大小 needed_size 为 24-bytes，然后会将 24-bytes RoundUp 到最近的 size class 2 对应的大小 32-bytes，最终 PrimaryAllocator 在真正申请内存时申请的大小是 32-bytes。

SizeClassMap 用于将 allocation sizes 映射到对应的 size class，以及根据 size class 得到其对应的 allocation size。SizeClassMap 在代码实现时被实现为一个模版类，包含以下模版参数：

ASan 使用的 SizeClassMap 模版参数为：kNumBits=3, kMinSizeLog=4, kMidSizeLog=8, kMaxSizeLog=17，具体的 size class 和 allocation size 的对应关系如下表：

size classallocation size (bytes)
00Class 0 always corresponds to size 0
116KMinSize (2^kMinSizeLog = 2^4 = 16)
232diff: +16
348
464
580
696
7112
8128
9144
10160
11176
12192
13208
14224
15240
16256KMidSize = 2^KMidSizeLog = 2^8 = 256 = 0b100000000
17320diff: +64, 320 = 0b101000000
18384diff: +64, 384 = 0b110000000
19448diff: +64, 448 = 0b111000000
20512diff: +64, 512 = 0b1000000000
21640diff: +128, 640 = 0b1010000000
22768diff: +128, 768 = 0b1100000000
23896diff: +128, 896 = 0b1110000000
241024diff: +128, 1024 = 0b10000000000
251280diff: +256, 1280 = 0b10100000000
261536diff: +256, 1536 = 0b11000000000
271792diff: +256, 1792 = 0b11100000000
…
52131072kMaxSize = 2^kMaxSizeLog = 2^17 = 131072

AllocationSize To ClassId

  static const uptr kMinSize = 1 << kMinSizeLog;
  static const uptr kMidSize = 1 << kMidSizeLog;
  static const uptr kMidClass = kMidSize / kMinSize;
  static const uptr S = kNumBits - 1;
  static const uptr M = (1 << S) - 1;

  static uptr ClassID(uptr size) {
    if (UNLIKELY(size > kMaxSize))
      return 0;
    if (size <= kMidSize)
      return (size + kMinSize - 1) >> kMinSizeLog;
    const uptr l = MostSignificantSetBitIndex(size);
    const uptr hbits = (size >> (l - S)) & M;
    const uptr lbits = size & ((1U << (l - S)) - 1);
    const uptr l1 = l - kMidSizeLog;
    return kMidClass + (l1 << S) + hbits + (lbits > 0);
  }

ClassId To AllocationSize

  static const uptr kMinSize = 1 << kMinSizeLog;
  static const uptr kMidSize = 1 << kMidSizeLog;
  static const uptr kMidClass = kMidSize / kMinSize;
  static const uptr S = kNumBits - 1;
  static const uptr M = (1 << S) - 1;

  static uptr Size(uptr class_id) {
    // Estimate the result for kBatchClassID because this class does not know
    // the exact size of TransferBatch. It's OK since we are using the actual
    // sizeof(TransferBatch) where it matters.
    if (UNLIKELY(class_id == kBatchClassID))
      return kMaxNumCachedHint * sizeof(uptr);
    if (class_id <= kMidClass)
      return kMinSize * class_id;
    class_id -= kMidClass;
    uptr t = kMidSize << (class_id >> S);
    return t + (t >> S) * (class_id & M);
  }

AsanThreadLocalMallocStorage

对于每个线程，ASan 都为其开辟了一块特殊的空间，称为 AsanThreadLocalMallocStorage。AsanThreadLocalMallocStorage 的结构如下图所示：

AsanThreadLocalMallocStorage 包含两个成员变量：quarantine_cache 和 allocator_cache。

PrimaryAllocator(SizeClassAllocator64)

ASan allocator 的 PrimaryAllocator 就是代码中的 SizeClassAllocator64。PrimaryAllocator 用于处理 128KB 以内的内存分配。PrimaryAllocator 维护了一个 address space，结构如下图所示：

Address space 由两部分组成：一块大小为 kSpaceSize 的连续内存地址空间，本文中称之为 RegionSpace；一块大小为 AdditionalSize 的连续内存地址空间，本文中称之为 RegionInfoSpace。

SecondaryAllocator(LargeMmapAllocator)

ASan allocator 的 SecondaryAllocator 就是代码中的 LargeMmapAllocator。LargeMmapAllocator 用于处理大于 128KB 的内存分配，顾名思义 LargeMmapAllocator 是通过 mmap 来分配内存的。

由 SecondaryAllocator 负责分配的内存会额外申请 page_size_ 大小的内存用作额外的 Header：

SecondaryAllocator 会维护一个数组 ptr_array_，该数组中保存的是指向 SecondaryAllocator 已分配内存的 Header 的指针：

给定一个指针 ptr，SecondaryAllocator 在判断该指针 ptr 是否指向一块内存由自己分配的chunk 时，就是通过遍历 ptr_array_ 查看 ptr_array_[i]->map_beg <= ptr < ptr_array_[i]->map_beg + ptr_array_[i]->map_size 是否满足。

The flow of asan_allocate()

我们将 ASan allocator 分配内存的流程抽象为 asan_allocate()，流程图如下所示：

  1. 用户申请的内存大小是 user_requested_size，首先计算添加 redzone 后所需要的内存大小 needed_size。

  2. 如果 needed_size 超过了 ASan 能够申请的最大内存大小 kMaxAllowedMallocSize = 0x10000000000，那么根据在环境变量 ASAN_OPTIONS 中是否设置了 may_return_null=1 而选择报错 “allocation-size-too-big” 并终止程序还是返回 nullptr。

  3. 如果 needed_size <= 128KB，那么由 thread local allocator cache 负责分配，执行步骤 4。否则由 SecondaryAllocator 负责分配，执行步骤 5。

  4. 对于 <= 128KB 的内存分配由 thread local allocator cache 负责。如果当前线程的 allocator cache 有 SizeClassMap::ClassId(needed_size) 的空闲 chunk，那么直接将空闲 chunk 返回给用户。如果没有的话，则先向 PrimaryAllocator 申请一些 SizeClassMap::ClassId(needed_size) 的 chunks，补充至当前线程的 allocator cache 中，然后再将空闲可用的 chunk 返回给用户。

  5. 对于 > 128KB 的内存分配由 SecondaryAllocator 负责，SecondaryAllocator 通过 mmap 申请内存返回给用户。

  6. 如果在步骤 4 或步骤 5 中没有足够的内存可供分配，则报错 “out-of-memory” 并终止程序。

  7. 成功申请到了内存后，设置 ChunkHeader：alloc_type, user_requested_alignment_log, user_requested_size, alloc_context_id。

  8. 将 chunk 中 user memory 对应的 shadow memory 的每个字节的值都设置为表示 addressable 的 magic value，将 chunk 中 redzone 对应的 shadow memory 的每个字节的值设置为表示 redzone 的 magic value: kAsanHeapLeftRedzoneMagic。

  9. 然后 malloc_fill 就是填充 user memory 的内容，通过 memset 将 user memory 的值设置为 0xbe，默认情况下最多只填充 user memory 的前 4KB。可以通过在环境变量 ASAN_OPTIONS 设置 max_malloc_fill_size 来控制最多填充 user memory 的多少个字节，默认 max_malloc_fill_size=0x1000；可以通过在环境变量 ASAN_OPTIONS 设置 malloc_fill_byte 即用于填充 user memory 每个字节的值，默认malloc_fill_byte=0xbe。

  10. 最后将 ChunkHeader 中的 chunk_state 更新为 CHUNK_ALLOCATED，返回给用户一个指向 chunk 中 user memory 的指针。至此，ASan allocator 分配内存的流程结束。

The flow of asan_deallocate()

我们将 ASan allocator 释放内存的流程抽象为 asan_deallocate()，流程图如下所示：

  1. 首先查看当前正在释放的 chunk 的 ChunkHeader，如果 chunk_state 不是 CHUNK_ALLOCATED，报错 “double-free” 或 “bad-free” 并终止程序，否则继续执行步骤 2。

  2. 首先更新当前正在释放的 chunk 的 ChunkHeader，将 chunk_state 更新为 CHUNK_QUARANTINE。

  3. 检查 alloc_type 和 dealloc_type 是否匹配，例如申请内存时使用的 operator new[] 而是释放内存时却使用的 operator delete 这种情况。如果 alloc_type 和 dealloc_type 不匹配，报错 “alloc-dealloc-mismatch” 并终止程序。

  4. 更新 ChunkHeader，设置 dealloc_context_id 即释放内存的 stacktrace 和 thread id。

  5. free_fill 填充 user memory 的内容：通过 memset 将 user memory 的值设置为 0x55。默认情况下不填充 user memory，可以通过环境变量 ASAN_OPTIONS 设置 max_free_fill_size 来控制最多填充 user memory 的多少个字节，默认 max_free_fill_size=0，即不填充；可以通过环境变量 ASAN_OPTIONS 设置 free_fill_byte 即用于填充 user memory 每个字节的值，默认 free_fill_byte=0x55。

  6. 将正在释放的 chunk 中 user memory 对应的 shadow memory 每个字节的值设置为 kAsanHeapFreeMagic，表示这块内存在语义上已经被释放了，实际上并没有释放而是被放入了 quarantine 中。

  7. 将被释放的 chunk 添加至当前线程的 quarantine cache 中。如果当前线程的 quarantine cache 中保存的所有已释放的 chunks 的大小之和不超过 thread_local_quarantine_size_kb（默认为 1024KB，可以通过环境变量 ASAN_OPTIONS 进行设置），则 asan_deallocate() 的流程结束，否则继续执行步骤 8。

  8. 将当前线程的 quarantine cache 转移 transfer 到全局 central quarantine 中。如果当前线程的 quarantine cache 中保存的所有已释放的 chunks 的大小之和不超过 quarantine_size_mb（默认为 256MB，可以通过环境变量 ASAN_OPTIONS 进行设置），则 asan_deallocate() 的流程结束，否则继续执行步骤 9。

  9. 不停地从全局 central quarantine 队列中取出 chunk（记作 extracted chunks），直至全局 central quarantine 中剩余的 chunks 的大小之和不超过 quarantine_size_mb 的 90%。

  10. 更新 extracted chunks 的 ChunkHeader，将 chunk_state 更新为 CHUNK_INVALID。

  11. 将 extracted chunks 中 user memory 对应的 shadow memory 每个字节的值设置为 kAsanHeapLeftRedzoneMagic，表示这些 extraced chunks 已经真正被释放了，不再保存在 quarantine 中，交由 PrimaryAllocator 或 SecondaryAllocator 去释放。

  12. 判断每一个 extracted chunk 在申请时是由 PrimaryAllocator 或 SecondaryAllocator 分配的。如果是由 PrimaryAllocator 分配的，那么执行步骤 13 交给 PrimaryAllocator 释放；如果是由 SecondaryAllocator 分配的，那么执行步骤 14 交给 SecondaryAllocator 释放。

  13. 由 PrimaryAllocator 释放 extracted chunk，首先查看 extraced chunk 属于哪一个 size class，如果当前线程 allocator cache 中该 size class 的空闲 chunks 已经满了 (per_class_[size_class].count == per_class_[size_class].max_count)，那么将该 size class 的空闲 chunks 的一半归还给 PrimaryAllocator，保存在 PrimaryAllocator 对应的 Region 的 FreeArray 中，PrimaryAllocator 会定期将 FreeArray 中的 chunks 归还给操作系统。最后将 extracted chunk 添加至当前线程 allocator cache 中对应的 per_class_ 中。执行步骤 15。

  14. 由 SecondaryAllocator 释放 extracted chunk，因为申请时是通过 mmap 分配的，所以直接通过 unmap 释放。执行步骤 15。

  15. 至此，ASan allocator 释放内存的流程结束。

Summary

本文分析了 ASan allocator 的实现，还是有很多细节没有详细讨论的，如：

本文没有将这些细节事无巨细地写下来，可以阅读 ASan 代码来学习这些细节。