levelDB 代码阅读笔记 05 arena

Mar 20, 2022 · 3 min read · leveldb

Overview

arena时levelDB中的内存池实现

接口

没有太多好说的，都非常直观。补了些注释

 1
 2class Arena {
 3 public:
 4  Arena();
 5
 6  Arena(const Arena&) = delete;
 7  Arena& operator=(const Arena&) = delete;
 8
 9  ~Arena();
10
11  // Return a pointer to a newly allocated memory block of "bytes" bytes.
12  char* Allocate(size_t bytes);
13
14  // Allocate memory with the normal alignment guarantees provided by malloc.
15  char* AllocateAligned(size_t bytes);
16
17  // Returns an estimate of the total memory usage of data allocated
18  // by the arena.
19  size_t MemoryUsage() const {
20    return memory_usage_.load(std::memory_order_relaxed);
21  }
22
23 private:
24  char* AllocateFallback(size_t bytes);
25  char* AllocateNewBlock(size_t block_bytes);
26
27  // Allocation state
28  // alloc_ptr_ 表示下一个可用的位置
29  char* alloc_ptr_;
30  size_t alloc_bytes_remaining_;
31
32  // Array of new[] allocated memory blocks
33  // 需要注意，vector中每一个元素都是一段内存块(memory, block)
34  std::vector<char*> blocks_;
35
36  // Total memory usage of the arena.
37  //
38  // TODO(costan): This member is accessed via atomics, but the others are
39  //               accessed without any locking. Is this OK?
40  std::atomic<size_t> memory_usage_;
41};
42

分配策略

代码可说的不多，主要想讲讲分配策略

之前玩nvJPEG的时候也实现过一个简单的显存池从而避免过多的cudamalloc

当时的策略是

Info

提前分配好很多种不同size的block. 每次分配就二分找到最合适大小的未被使用的block,然后将这个block标记为已使用.
某个block在使用完会被再次标记为unused,从而可以再次使用
如果某次分配需要的size找不到合适的block,会额外分配一个block. 分配的size会比实际需要的略大，避免下次出现比当前需要size大一点的时候还需要额外分配block
每个block在同一时间内最多只会被一个handle占用。不会存在将一个Block分配给多个handle使用的情况

而levelDB中的arena中的分配策略很不相同

Info

对于大size，单独分配恰好符合需要的block
不提供清理内存的接口，只有在析构的时候释放内存
同一个block可能会被多个handle使用
block只有一种固定大小

这种策略其实简单了很多，而且省去了分配内存的时候查找合适size block的开销

一些细节补充在代码注释中了

 1
 2
 3static const int kBlockSize = 4096;
 4// 整体分配逻辑是默认每个block KblockSize个、 当目前的block不足当前的需要时，就舍弃掉，分配新的。
 5// 但是如果需要的比较大时，就单独分配一个大block,避免过多的浪费。
 6// note: 实际上只有小内存才能受益于内存池，大内存每次都要allocate,和自己手动new没区别
 7
 8Arena::Arena()
 9    : alloc_ptr_(nullptr), alloc_bytes_remaining_(0), memory_usage_(0) {}
10
11Arena::~Arena() {
12  for (size_t i = 0; i < blocks_.size(); i++) {
13    delete[] blocks_[i];
14  }
15}
16
17char* Arena::AllocateFallback(size_t bytes) {
18  if (bytes > kBlockSize / 4) {
19    // 这里保证了浪费最多不超过 kBlockSize/4
20    // Object is more than a quarter of our block size.  Allocate it separately
21    // to avoid wasting too much space in leftover bytes.
22    // 因为下面的逻辑是新分配block size个，当前的block的全都扔掉，
23    char* result = AllocateNewBlock(bytes);
24    return result;
25  }
26
27  // We waste the remaining space in the current block.
28  // 这里当前Block不够的那些就全都扔掉了
29  alloc_ptr_ = AllocateNewBlock(kBlockSize);
30  alloc_bytes_remaining_ = kBlockSize;
31
32  char* result = alloc_ptr_;
33  alloc_ptr_ += bytes;
34  alloc_bytes_remaining_ -= bytes;
35  return result;
36}
37
38char* Arena::AllocateAligned(size_t bytes) {
39  const int align = (sizeof(void*) > 8) ? sizeof(void*) : 8;
40  static_assert((align & (align - 1)) == 0,
41                "Pointer size should be a power of 2");
42  // &(align-1)相当于 %align  因为这里align这里一定时2的倍数
43  size_t current_mod = reinterpret_cast<uintptr_t>(alloc_ptr_) & (align - 1);
44  // slophi计算还差几个字节能把当前开始的分配起点alloc_ptr_ 调整到最近的aligned 地址
45  size_t slop = (current_mod == 0 ? 0 : align - current_mod);
46  size_t needed = bytes + slop;
47  char* result;
48  if (needed <= alloc_bytes_remaining_) {
49    result = alloc_ptr_ + slop;
50    alloc_ptr_ += needed;
51    alloc_bytes_remaining_ -= needed;
52  } else {
53    // AllocateFallback always returned aligned memory
54    result = AllocateFallback(bytes);
55  }
56  assert((reinterpret_cast<uintptr_t>(result) & (align - 1)) == 0);
57  return result;
58}
59
60char* Arena::AllocateNewBlock(size_t block_bytes) {
61  char* result = new char[block_bytes];
62  blocks_.push_back(result);
63  memory_usage_.fetch_add(block_bytes + sizeof(char*),
64                          std::memory_order_relaxed);
65  return result;
66}
67

levelDB 代码阅读笔记 05 arena

Overview

接口

分配策略

Posts in this Series