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实现。好，就到这里^.^