Arena内存管理-leveldb源码剖析(1)

leveldb实现了定制的Arena内存分配器,并没有直接使用glibc的malloc或者c++标准库的new,Arena主要与MemTable关联使用,实际主要用于SkipList中的Node内存分配,统一MemTable的内存分配需求,减少内存分配的实际系统调用次数(尤其针对小块内存),减少内存分配中的空洞(碎片),但也会造成一定的内存浪费;统一内存释放,不必频繁new/delete;鉴于Arena在leveldb中的使用场景不需考虑线程安全。Arena的实现简单轻量,代码总计百余行,服务于leveldb的定制需求,提高应用性能,并且提供了内存对齐的版本。

Arena提供的声明及主要接口如下:

class Arena {
 public:
  Arena();
  ~Arena();

  // Return a pointer to a newly allocated memory block of "bytes" bytes.
  char* Allocate(size_t bytes);

  // Allocate memory with the normal alignment guarantees provided by malloc
  char* AllocateAligned(size_t bytes);

  // Returns an estimate of the total memory usage of data allocated
  // by the arena.
  size_t MemoryUsage() const {
    return reinterpret_cast(memory_usage_.NoBarrier_Load());
  }

 private:
  char* AllocateFallback(size_t bytes);
  char* AllocateNewBlock(size_t block_bytes);

  // Allocation state
  char* alloc_ptr_;
  size_t alloc_bytes_remaining_;

  // Array of new[] allocated memory blocks
  std::vector<char*> blocks_;

  // Total memory usage of the arena.
  port::AtomicPointer memory_usage_;

  // No copying allowed
  Arena(const Arena&);
  void operator=(const Arena&);
};

主要三个public的对外接口,分配指定大小的内存以及对齐的版本,当前Arena内存的使用量。
内存对齐版本有神马好处呢?
glibc malloc和C++标准库的new返回的地址均是内存对齐的,这里由于是定制内存分配,指针预分配的大块内存(page页面大小),当连续分配小块内存时就需要做额外对齐。内存对齐有利于提高访存速度,因为内存按字节编址,根据CPU字长即sizeof(void *)大小做对齐,有利于减少访存指令次数,防止跨对齐边界访存,也能充分利用硬件体系,提高CPU性能。

下面先看Allocate非对齐版本的具体实现:

inline char* Arena::Allocate(size_t bytes) {
  // The semantics of what to return are a bit messy if we allow
  // 0-byte allocations, so we disallow them here (we don't need
  // them for our internal use).
  assert(bytes > 0);
  if (bytes <= alloc_bytes_remaining_) {
    char* result = alloc_ptr_;
    alloc_ptr_ += bytes;
    alloc_bytes_remaining_ -= bytes;
    return result;
  }
  return AllocateFallback(bytes);
}

char* Arena::AllocateFallback(size_t bytes) {
  if (bytes > kBlockSize / 4) {
    // Object is more than a quarter of our block size.  Allocate it separately
    // to avoid wasting too much space in leftover bytes.
    char* result = AllocateNewBlock(bytes);
    return result;
  }

  // We waste the remaining space in the current block.
  alloc_ptr_ = AllocateNewBlock(kBlockSize);
  alloc_bytes_remaining_ = kBlockSize;

  char* result = alloc_ptr_;
  alloc_ptr_ += bytes;
  alloc_bytes_remaining_ -= bytes;
  return result;
}

char* Arena::AllocateNewBlock(size_t block_bytes) {
  char* result = new char[block_bytes];
  blocks_.push_back(result);
  memory_usage_.NoBarrier_Store(
      reinterpret_cast<void*>(MemoryUsage() + block_bytes + sizeof(char*)));
  return result;
}

Arena内存的分配对于小块内存分配的预分配以4KB(page大小)为基准,Allocate不允许0字节大小内存分配,首先判断当前剩余空闲块是否满足该次内存申请大小,满足直接返回;不满足的情况,如果需求大于1/4默认块大小的较大内存,则使用AllocateNewBlock直接分配该块,并更新内存使用计数。不超过1/4默认块大小的较小内存需求,会直接分配默认块大小,并同时更新当前块的分配指针为新块指针,这样会造成一定的内存浪费,上一块内存块尚有较小剩余。

再看AllocateAligned对齐版本:

char* Arena::AllocateAligned(size_t bytes) {
  const int align = (sizeof(void*) > 8) ? sizeof(void*) : 8;
  assert((align & (align-1)) == 0);   // Pointer size should be a power of 2
  size_t current_mod = reinterpret_cast(alloc_ptr_) & (align-1);
  size_t slop = (current_mod == 0 ? 0 : align - current_mod);
  size_t needed = bytes + slop;
  char* result;
  if (needed <= alloc_bytes_remaining_) {
    result = alloc_ptr_ + slop;
    alloc_ptr_ += needed;
    alloc_bytes_remaining_ -= needed;
  } else {
    // AllocateFallback always returned aligned memory
    result = AllocateFallback(bytes);
  }
  assert((reinterpret_cast(result) & (align-1)) == 0);
  return result;
}

上面已提到过为何有内存对齐版本,这里实现上也是以提到的指针长度(sizeof(void*) )作为对齐字节数但默认最小8B(x64平台),这里使用了小trick判断最小对齐数是否为2的幂次方,是否有似曾相识的感觉?应届童鞋常做的题二进制数中1的个数。对齐版本在分配策略上与Allocate版没有区别。

再者是内存的释放,每次分配较大块时会把返回的起始地址放入vector,最后由析构函数进行统一销毁,代码如下,很简单:

Arena::~Arena() {
  for (size_t i = 0; i < blocks_.size(); i++) {
    delete[] blocks_[i];
  }
}

有个问题,Arena默认的预分配内存块大小为4K(kBlockSize),4K正好为内存页大小,为神马设定为这个值?按现行linux操作系统的段页式内存管理方式,内存分页机制的对应物理页面大小就是4K,设定4K大小这个值亦考虑到尽可能避免内存碎片,也可以增加局部性,而且Arena的实现初衷主要针对小内存分配的优化,因此定为4K是很合理的。

看最后一个接口的实现,主要用于获取AllocateNewBlock时更新的内存使用计数:

  // Returns an estimate of the total memory usage of data allocated
  // by the arena.
  size_t MemoryUsage() const {
    return reinterpret_cast(memory_usage_.NoBarrier_Load());
  }

memory_usage_是一个port::AtomicPointer类型的变量,该类型实现与平台相关。由于内存使用一直是增长,且依附于MemTable使用,为MemTable独享,不涉及多线程及数据共享,所以读写均使用了不需要内存屏障的版本,下一篇文章会对AtomicPointer进行专门的解读。而关于CPU、Cache、内存模型及Memory Barrier是个比较大的话题,以后会单独写一篇文章进行探讨。

Arena内存分配还是很简单的,代码清晰易读。同时也给我们启发怎样实现一个定制的内存分配器,后续会再以一篇博文分析经典的tcmalloc实现。好,就到这里^.^

发表评论

电子邮件地址不会被公开。 必填项已用*标注