内存分配器之 arena

今天，就开始逐步更新剖析 RocksDB 源码的博客。思前想后，准备自下而上，因此还是从内存分配器开始叭。

在 RocksDB 中主要有两类内存分配器MemoryAllocator、Allocator。

MemoryAllocator

MemoryAllocator 是个基类，RocksDB 提供了两个子类：MemkindKmemAllocator、JemallocNodumpAllocator，而这两个子类，实际上分别是 memkind、jemalloc两个开源库的 wrapper，即利用两个开源库的函数来实现Allocate、Deallocate操作。jemalloc后者有时间再开专题专门细解，这里就不展开说了。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
class MemoryAllocator {
 public:
  virtual ~MemoryAllocator() = default;

  virtual const char* Name() const = 0;

	///@note 需要保证线程安全
  ///@param 至少分配的内存大小
  virtual void* Allocate(size_t size) = 0;
	
  ///@note 需要保证线程安全
  ///@brief 释放之前由 Allocate 分配的内存
  virtual void Deallocate(void* p) = 0;

  ///@brief 返回 ptr 指向的block的内存大小
  virtual size_t UsableSize(void* ptr, size_t allocation_size) const {
    // default implementation just returns the allocation size
    return allocation_size;
  }
};

Allocator

本节主要详细讲解Allocator及其子类Arena的实现。

类 Allocator 是个基类，主要有两个接口：

  • Allocate：分配无须对齐的内存；
  • AllocateAligned：分配需要经过对齐的内存；

关于内存对齐，可以参考之前写过的一期博客 [内存对齐之 alignof、alignas 、aligned_storage、align 深度剖析]，在这一期，通过讲解Allocator，会更加深刻的理解内存对齐。

1
2
3
4
5
6
7
8
9
10
11
class Allocator {
 public:
  virtual ~Allocator() {}

  virtual char* Allocate(size_t bytes) = 0;
  virtual char* AllocateAligned(size_t bytes, 
                                size_t huge_page_size = 0,
                                Logger* logger = nullptr) = 0;

  virtual size_t BlockSize() const = 0;
};

基类Allocator 有两个子类，Arena 和concurrent_arena，分别用于单线程和多线程内存分配，其中 concurrent_arena 也是个Arena的wrapper，外加了一些措施，保证Arnea在多线程下的安全。因此，本文先详细讲解下Arena，下一节再把注意力集中在concurrent_arena`的多线程设计上。

Arena

类Arena 在分配内存时，是以 block 为单位，即每次先分配一个block大小的内存，后续所需bytes大小的内存时，会先尝试从block 中获取，如果这个block中剩余的可用内存能满足bytes，则从block中划出一部分给上层使用，否则才从操作系统中获取。

一个block容纳的内存大小，由kBlockSize参数来指定。

现在Arena怎么实现基类中Allocate、AllocateAligned两个接口？

Arena 中有两个指针：aligned_alloc_ptr_、unaligned_alloc_ptr_，当一个block的内存创建完毕时：

  • aligned_alloc_ptr_：指向该block的首地址（低地址），后续用于分配需要对齐的内存；
  • unaligned_alloc_ptr_：指向该block的末地址（高地址），后续用于分配不需要对齐的内存。

示意图如下：

1
2
3
4
block : [-------------------------]
        ^                         ^
        |                         | 
   aligned_alloc_ptr_    unaligned_alloc_ptr_

为啥要这么做？

由于每次内存对齐操作可能存在一定的浪费，而同一个类中所需的内存对齐大小一般是固定的，因此从blokc的一端只分配需要对齐的内存，若内存对齐大小是固定的，那么每次分配的内存也都是连续的，如此就可以减少因为内存对齐带来的浪费。

从block的另一端分配无需对齐的内存，还能提高内存利用率。

比如，block的大小为7个字节，分配一块需要4字节对齐的内存，还剩下3字节的内存，可以继续用于无须对齐的内存。

下面先整体看看类Arean。

在下面的源码分析中，做了一些简化，去除了一些统计内存大小部分的代码，读者可自行追溯RocksDB中该部分的源码。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
class Arena : public Allocator {
 public:
  // No copying allowed
  Arena(const Arena&) = delete;
  void operator=(const Arena&) = delete;

  static const size_t kInlineSize = 2048;
  static const size_t kMinBlockSize;
  static const size_t kMaxBlockSize;

  explicit Arena(size_t block_size = kMinBlockSize,
                 AllocTracker* tracker = nullptr, 
                 size_t huge_page_size = 0);
  ~Arena();
	
  /// 分配无需对齐的内存
  char* Allocate(size_t bytes) override;
  
  /// 分配需要对齐的内存
  char* AllocateAligned(size_t bytes, 
                        size_t huge_page_size = 0,
                        Logger* logger = nullptr) override;
 
  /// 当前已使用内存大小
  size_t ApproximateMemoryUsage() const {
    return blocks_memory_ + blocks_.capacity() * sizeof(char*) - alloc_bytes_remaining_;
  }

  /// 总的已分配内存
  size_t MemoryAllocatedBytes() const { return blocks_memory_; }

  /// 剩余可用内存
  size_t AllocatedAndUnused() const { return alloc_bytes_remaining_; }

  /// 分配的不对齐block数
  size_t IrregularBlockNum() const { return irregular_block_num; }
	
  /// 一个 block 的内存大小
  size_t BlockSize() const override { return kBlockSize; }
	
  /// blocks_ 是否用的栈上内存
  bool IsInInlineBlock() const {
    return blocks_.empty();
  }

 private:
  alignas(max_align_t) char inline_block_[kInlineSize];
  // 一个block分配的内存大小
  const size_t kBlockSize;           
  typedef std::vector<char*> Blocks; 
  // 使用new分配的block集合
  Blocks blocks_;										

  struct MmapInfo {
    void* addr_;
    size_t length_;

    MmapInfo(void* addr, size_t length) : addr_(addr), length_(length) {}
  };
  // 使用 mmap 分配内存的block集合
  std::vector<MmapInfo> huge_blocks_; 
  
  size_t irregular_block_num = 0;
  char* unaligned_alloc_ptr_ = nullptr;
  char* aligned_alloc_ptr_ = nullptr;
  // 当前block剩余可用内存
  size_t alloc_bytes_remaining_ = 0; 
   // 目前一共分配的内存
  size_t blocks_memory_ = 0;        
  
#ifdef MAP_HUGETLB
  size_t hugetlb_size_ = 0;
#endif  // MAP_HUGETLB
  
  char* AllocateFromHugePage(size_t bytes);
  char* AllocateFallback(size_t bytes, bool aligned);
  char* AllocateNewBlock(size_t block_bytes);
};

Arena::Arena

先来看看构造函数 Arena::Arena。这里，主要初始化一些类成员变量：

  • kBlockSize

    字段kBlockSize ，表达的是以后每次分配一个block时的内存大小。在初始化之前，使用OptimizeBlockSize函数对传入的参数block_size进行限制，使其满足后续的assert判断。

    通过 OptimizeBlockSize 函数限制block_size的值，减少后续分配需要对齐的内存浪费。

    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    16
    const size_t Arena::kMinBlockSize = 4096;           // 最小为 4k
    const size_t Arena::kMaxBlockSize = 2u << 30;       // 最大为 8k
    static const int kAlignUnit = alignof(max_align_t); // 按照 8 byte 对齐

    size_t OptimizeBlockSize(size_t block_size) {
      // 确保满足： Arena::kMinBlockSize <= block_size <= Arena::kMaxBlockSize
      block_size = std::max(Arena::kMinBlockSize, block_size);
      block_size = std::min(Arena::kMaxBlockSize, block_size);
    	
      // 确保 block_size 是 8 的倍数
      if (block_size % kAlignUnit != 0) {
        block_size = (1 + block_size / kAlignUnit) * kAlignUnit;
      }

      return block_size;
    }

  • inline_block_

    字段inline_block_ ，其中的inline语义是指这块内存分配在栈上，在地址上和Arena是连续的。这对于那些只需要分配小内存的操作具有优势，可以避免从堆上分配内存。当这块内存使用完毕，会再从堆上获取。

  • hugetlb_size_

    字段hugetlb_size_，是默认情况下使用mmap给block分配的内存大小。如果 hugetlb_size_ == 0，则表示不使用mmap分配内存。

    当然，hugetlb_size_ 在构造函数中也是经过向上取整操作，变为 8 的倍数。

现在，可以很好的阅读构造函数 Arena::Arena 了。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
Arena::Arena(size_t block_size, 
             AllocTracker* tracker, 
             size_t huge_page_size)
    : kBlockSize(OptimizeBlockSize(block_size)) {
  assert(kBlockSize >= kMinBlockSize && kBlockSize <= kMaxBlockSize &&
         kBlockSize % kAlignUnit == 0);
  alloc_bytes_remaining_ = sizeof(inline_block_);
  blocks_memory_ += alloc_bytes_remaining_;
  // 对齐侧指向了低地址
  aligned_alloc_ptr_ = inline_block_;
  // 不对齐侧指向了高地址
  unaligned_alloc_ptr_ = inline_block_ + alloc_bytes_remaining_;

#ifdef MAP_HUGETLB
  hugetlb_size_ = huge_page_size;
  if (hugetlb_size_ && kBlockSize > hugetlb_size_) {
    // hugetlb_size_ 向上取整
    hugetlb_size_ = ((kBlockSize - 1U) / hugetlb_size_ + 1U) * hugetlb_size_;
  }
#else
  (void)huge_page_size;
#endif
}

Arena::AllocateNewBlock

AllocateNewBlock 函数比较普通，本质上就是使用 new 操作从操作系统获取内存。

这里面稍微有个trick的操作，是blocks_.emplace_back(nullptr); 这行，作用是在blocks_中预留一个指针大小的空间，即 sizeof(Block*)，出于内存泄露的考虑，使用了emplace_back，而不是reserve函数。

RocksDB 解释如下：

  • 如果emplace_back 函数抛出异常，不会发生内存泄露，因为此时还没使用new分配内存；
  • 如果new 抛出异常（即std::bad_alloc异常），也不会发生内存泄露，因为在blocks_中预留的空间将会基于RAII语义被清除。

AllocateNewBlock 函数，直接使用new操作分配内存，不负责进行内存对齐操作。如果需要按照某个alignment大小进行对齐，得调用 AllocateAligned 函数，这个后面再说。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
///@return 返回指针，指向当前分配的 block
char* Arena::AllocateNewBlock(size_t block_bytes) {
  // Reserve space in `blocks_` before allocating memory via new.
  // Use `emplace_back()` instead of `reserve()` to let std::vector manage its
  // own memory and do fewer reallocations.
  //
  // - If `emplace_back` throws, no memory leaks because we haven't called `new`
  //   yet.
  // - If `new` throws, no memory leaks because the vector will be cleaned up
  //   via RAII.
  blocks_.emplace_back(nullptr);
  // 分配内存
  char* block = new char[block_bytes];
  size_t allocated_size;
#ifdef ROCKSDB_MALLOC_USABLE_SIZE
  allocated_size = malloc_usable_size(block);
#else
  allocated_size = block_bytes;
#endif
  // 增加已分配内存
  blocks_memory_ += allocated_size;
  // 赋值
  blocks_.back() = block;
  return block;
}

下面来解释下为何使用reserve可能会导致内存泄露，写法如下。

1
2
3
4
5
6
7
8
9
10
11
12
13
char* Arena::AllocateNewBlock(size_t block_bytes) {
  blocks_.reserve(1);        // 预留空间
  char* block = new char[block_bytes];
  size_t allocated_size;
#ifdef ROCKSDB_MALLOC_USABLE_SIZE
  allocated_size = malloc_usable_size(block);
#else
  allocated_size = block_bytes;
#endif
  blocks_memory_ += allocated_size;
  blocks_.emplace_back(block); // 抛出异常???
  return block;
}

理由很简单：上面这个写法，如果在emplace_back的过程中抛出异常，那么 block 指向的内存将会泄露。

尽管emplace_back抛异常这种bad case极少出现，但也应该为RocksDB的细致点赞。

Arena::AllocateFromHugePage

Arena 中有两种方式从操作系统获取内存：

  • new：即如Arena::AllocateNewBlock 函中数的实现；
  • mmap：即如 Arena::AllocateFromHugePage 函数中的实现。

mmap、munmap函数的原型如下。

1
2
3
4
5
#include <sys/mman.h>
// 分配内存
void* mmap(void* addr, size_t len, int prot, int flags, int fd, off_t offset); 
// 释放 mmap 分配的内存
int munmap(void *addr, size_t len);

使用mmap分配内存，需要linux内核支持 HUGE_PAGE，即当前linux内核具有 MAP_HUGETLB 标志位， 即可以如下操作。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
///@return 返回指针，指向当前分配的 block
char* Arena::AllocateFromHugePage(size_t bytes) {
#ifdef MAP_HUGETLB
  if (hugetlb_size_ == 0) {
    return nullptr;
  }
  // 先使用 emplace_back 理由同上
  huge_blocks_.emplace_back(nullptr /* addr */, 0 /* length */);

  // 使用 mmap 从 hugepage 中分配 bytes 个字节
  void* addr = mmap(nullptr, 
                    bytes, 
                    (PROT_READ | PROT_WRITE),
                    (MAP_PRIVATE | MAP_ANONYMOUS | MAP_HUGETLB), // 需要 MAP_HUGETLB 支持
                    -1, 
                    0);

  if (addr == MAP_FAILED) {
    return nullptr;
  }
  huge_blocks_.back() = MmapInfo(addr, bytes);
  blocks_memory_ += bytes;
  return reinterpret_cast<char*>(addr);
#else
  (void)bytes;
  return nullptr;
#endif
}

Arena::AllocateFallback

好嘞，介绍完上面两种分配内存的措施，现在来看看统一上述两个操作的AllocateFallback函数。

当调用AllocateFallback函数时，是上层发现当前block中剩余的内存无法满足bytes个字节的需求，需要重新从操作系统获取内存。运行到AllocateFallback函数时，逻辑如下：

  • 如果所需的内存大小 bytes 超过了kBlockSize / 4，就直接从操作系统中获取bytes大小的内存，返回给AllocateFallback函数的调用方。那么就能避免浪费当前 block 中剩余的内存，这部分可以继续保留，供给下一次内存分配时使用。

  • 否则，当前block中剩余的内存就将会被抛弃，重新从操作系统获中分配一个block的内存，供给上层使用。

    此时，由 bytes <= kBlockSize / 4，因此也降低了浪费，

现在，顺着代码注释往下看。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
char* Arena::AllocateFallback(size_t bytes, bool aligned) {
  if (bytes > kBlockSize / 4) {
    ++irregular_block_num;
    // 如果所需的内存大小 bytes 超过了 block 的1/4，那么就直接分配内存
    return AllocateNewBlock(bytes);
  }
  
  size_t size = 0;
  char* block_head = nullptr;
#ifdef MAP_HUGETLB
  if (hugetlb_size_) {
    // mmap 分配的的一个block内存大小为 hugetlb_size_
    size = hugetlb_size_;
    block_head = AllocateFromHugePage(size);
  }
#endif
  if (!block_head) {
    // block_head == nullptr, 即当前linux内核不支 hugetlb
    // 那么使用 new 来分配内存
    size = kBlockSize;
    block_head = AllocateNewBlock(size);
  }
  
  //! 之前block未使用的内存就忽略了，
  //! 但不会内存泄露，因为会在析构函数 ~Arena 中释放
  
  // 当前block划掉 bytes 个字节后，剩余的可用内存大小
  alloc_bytes_remaining_ = size - bytes;

  if (aligned) {
    aligned_alloc_ptr_ = block_head + bytes; // 从低地址端增加 bytes 字节
    unaligned_alloc_ptr_ = block_head + size;
    // 表示 [block_head, block_head + bytes) 可用
    return block_head;
  } else {
    aligned_alloc_ptr_ = block_head; 
    unaligned_alloc_ptr_ = block_head + size - bytes; // 尾部向前推动 bytes
    // 表示 [unaligned_alloc_ptr_, unaligned_alloc_ptr_ + bytes) 可用
    return unaligned_alloc_ptr_;
  }
}

Arena::AllocateAligned

最后，就是对外提供分配对齐内存的函数 AllocateAligned。

其输入参数huge_page_size，语义是在使用mmap分配内存时的自定义 alignment，如果 huge_page_size 为 0，只是表示此时不需要自定义的alignment，使用默认的kAlignUnit即可。

换句话说，当需要自定义alignment时，RcoskDb 是准备使用mmap来分配内存。

当使用默认的kAlignUnit，如果当前block中剩余的可用内存能满足need个字节（need个字节，是bytes字节按照kAlignUnit对齐的后的大小），则继续从当前block中划分出去need个字节，否则就使用上述的AllocateFallback函数，重新从操作系统分配内存。

现在，顺着代码注释向下看。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
char* Arena::AllocateAligned(size_t bytes, 
                             size_t huge_page_size,
                             Logger* logger) {
  // Pointer size should be a power of 2
  assert((kAlignUnit & (kAlignUnit - 1)) == 0);  
	
  // 自定义的内存对齐值 huge_page_size，只使用mmap来分配
#ifdef MAP_HUGETLB
  if (huge_page_size > 0 && bytes > 0) {
    assert(logger != nullptr);
    // 将 bytes 向上调整到 huge_page_size 的整倍数
    size_t reserved_size = ((bytes - 1U) / huge_page_size + 1U) * huge_page_size;
    assert(reserved_size >= bytes);
    char* addr = AllocateFromHugePage(reserved_size);
    if (addr == nullptr) {
      ROCKS_LOG_WARN(logger,
                     "AllocateAligned fail to allocate huge TLB pages: %s",
                     errnoStr(errno).c_str());
    } else {
      return addr;
    }
  }
#else
  (void)huge_page_size;
  (void)logger;
#endif
  
  // 下面则使用默认的 kAlignUnit 对齐大小

  size_t current_mod =
      reinterpret_cast<uintptr_t>(aligned_alloc_ptr_) & (kAlignUnit - 1);
  // 计算距离对齐还差几个字节
  size_t slop = (current_mod == 0 ? 0 : kAlignUnit - current_mod);
  // 对齐后需分配的字节数
  size_t needed = bytes + slop;  
  char* result;
  // 当前block中的剩余内存是否能满足此次 needed 个字节需求
  if (needed <= alloc_bytes_remaining_) {
    // result 调整到对齐后的位置
    result = aligned_alloc_ptr_ + slop; 
    // 调整到对齐后的位置
    aligned_alloc_ptr_ += needed;  
    // block中剩余的字节数
    alloc_bytes_remaining_ -= needed;   
  } else {
    // 如果当前 block 剩余的内存不足，则从操作系统获取
    result = AllocateFallback(bytes, true /* aligned */);
  }
  assert((reinterpret_cast<uintptr_t>(result) & (kAlignUnit - 1)) == 0);
  return result;
}

by the way

这里稍微总结下，如何向上调整、计算对齐后的地址。

实际上计算的方法有很多种，但是都符合上一期 [内存对齐之 alignof、alignas 、aligned_storage、align 深度剖析] 最后提到了一点：本质上就是以「alignment进制」向上（下）取为alignment的整倍数。

比如，在十进制下，12向上取整为10的倍数，即20。

理解了这一层之后，再来看看下面几个计算方式：

  • case 1：size_t aligned = ((bytes - 1U) / alignment + 1U) * alignment

    单纯地将bytes向上调整为alignment的整倍数，可以实现为 (bytes / alignment + 1U) * alignment，那为啥要 - 1 呢？

    如果bytes本身就已是alignment的整数，按照这 native 实现，会无端将bytes增加了alignment。为了应对这种情况，需要先减少1。

    此外，在 Arena::Arena 中调整hugetlb_size_ 时，也是如此计算。而在OptimizeBlockSize函数中，调整block_size时，可以确定block_size 不是 kAlignUnit的整数时，就可将-1去掉，简化如下：

    1
    2
    3
    if (block_size % kAlignUnit != 0) {
      block_size = (1 + block_size / kAlignUnit) * kAlignUnit;
    }

  • case 2：size_t aligned = (bytes - 1u + alignment) & -alignment

    这种实现，利用位位运算将余数清除，效率较高，这也是std::align 函数的实现方式，这在 [内存对齐之 alignof、alignas 、aligned_storage、align 深度剖析] 分析过，这里顺带再解释下。

    其中 alignment 是无符号数，-alignment 的值实际上是 ::pow(2, n) - alignment。那么bytes - 1u + alignment 对 -alignment 取 &操作，就能保证 bytes - 1u + alignment 的高位不变，而小于alignment 的余数全部清除。

万变不离其宗，理解了这个逻辑，无论是向上调整、亦或是向下调整，都能很好理解了。

Arena::Allocate

讲完了上面AllocateAligned函数之后，再看Allocate函数，就非常好理解了。

1
2
3
4
5
6
7
8
9
10
11
inline char* Arena::Allocate(size_t bytes) {
  assert(bytes > 0);
  // 如果当前block剩余足够的内存，则直接分配
  if (bytes <= alloc_bytes_remaining_) {
    unaligned_alloc_ptr_ -= bytes;
    alloc_bytes_remaining_ -= bytes;
    return unaligned_alloc_ptr_;
  }
  // 不用对齐
  return AllocateFallback(bytes, false /* unaligned */);
}

Arena::~Arena

释放所有已分配的内存。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
Arena::~Arena() {
  // 释放所有使用 new 分配的内存
  for (const auto& block : blocks_) {
    delete[] block;
  }

#ifdef MAP_HUGETLB
  for (const auto& mmap_info : huge_blocks_) {
    if (mmap_info.addr_ == nullptr) {
      continue;
    }
    // 释放所有使用 mmap 分配的内存
    auto ret = munmap(mmap_info.addr_, mmap_info.length_);
    if (ret != 0) {
      // TODO(sdong): Better handling
    }
  }
#endif
}

Say Something

一个优秀的开源项目，其单元测试（unitest）也是很好的学习资料。尤其对于RocksDB这类比较大的项目，无法下手的话，可以先从单元测试着手。

下一期，讲解下多线程内存分配器的设计，会更加硬核，敬请期待。