LevelDB源码解析(1) Arena内存分配器

背景

LevelDB中需要频繁申请和释放内存，如果直接使用系统的new/delete或者malloc/free接口申请和释放内存，会产生大量内存碎片，进而拖累系统的性能表现。所以LevelDB实现了一个Area内存分配器来对内存进行管理，以保证性能。

Arena的核心思想

LevelDB本身不再直接申请和释放内存，需要内存时，向Arena申请。内存释放由Arena负责，LevelDB不再关心内存释放问题。

Arena从系统申请内存时是以固定大小（block_size) 整块申请的，LevelDB向Arena申请内存时，Arena按照LevelDB申请的内存大小(request_size)从已申请的内存块中分配，如果内存块中剩下的内存少于request_size，就不能直接分配了。此时分两种情况：如果requet_size 大于block_size的四分之一，Arena会申请一个request_size的内存返回给LevelDB。反之就申请一个block_size的内存块，然后从新的内存块中分配内存给LevelDB。

四分之一策略，让小内存可以都从内存块中分配内存，而较大的内存申请从系统申请。避免了大量的小内存申请和释放，同时也保证了每个内存块被浪费的空间不会超过block_size/4。这里要理解内存浪费是不可避免的，比如如果把四分之一的阈值降低到百分之一，确实每个内存块浪费的空间会减少很多，但是也意味着很多小于block_size/4但是大于block_size/100的的小内存请求都从系统申请了，这就会造成本文开头所提到的内存碎片问题。所以四分之一的阈值其实是在空间浪费和内存碎片之间找的一个平衡点。

如果request_size比block_size还大怎么办？此时，Arena会申请一个request_size大小的内存块，返回给LevelDB。

Arena申请的内存什么时候释放呢？Arena申请的所有内存都是在Arena析构时一起释放的。LevelDB中每个MemTable对象都有一个Arena成员变量，MemTable是LevelDB在内存中的数据缓存结构，每个MemTable写满后就会落盘（写入磁盘），然后被销毁。Arena也会跟着一起析构。所以不用担心内存一直释放不了。

Arena源码解析

注：本文使用的代码版本是是LevelDB 1.22

我们先看头文件arena.h

#include <atomic>
#include <cassert>
#include <cstddef>
#include <cstdint>
#include <vector>

namespace leveldb
{
  class Arena
  {
  public:
    Arena();

    Arena(const Arena&) = delete;

    Arena& operator=(const Arena&) = delete;

    ~Arena();

    char* Allocate(size_t bytes);

    char* AllocateAligned(size_t bytes);

    size_t MemoryUsage() const
    {
      return memory_usage_.load(std::memory_order_relaxed);
    }

  private:
    char* AllocateFallback(size_t bytes);

    char* AllocateNewBlock(size_t block_bytes);

    char* alloc_ptr_;
    size_t alloc_bytes_remaining_;

    std::vector<char*> blocks_;

    std::atomic<size_t> memory_usage_;
  };

  inline char* Arena::Allocate(size_t bytes)
  {
    assert(bytes > 0);
    if( bytes <= alloc_bytes_remaining_ )
    {
      char* result = alloc_ptr_;
      alloc_ptr_ += bytes;
      alloc_bytes_remaining_ -= bytes;
      return result;
    }
    return AllocateFallback(bytes);
  }
}

Arena的接口很简单，除了构造/析构函数，对外接口实际上只有三个：Allocate，AllocateAligned，MemoryUsage，内部私有接口有两个AllocateFallback和AllocateFallback，有4个私有成员变量

成员变量

allocptr 指向当前可分配的内存块空闲空间的头部。 alloc_bytesremaining 存储当前内存空空闲空间的大小 blocks_ 是一个数组，保存了所有已分配内存块的指针 memoryusage 保存Arena占用的总内存大小

Allocate函数

Allcate是Arena提供给外部用于申请内存的接口，参数只有一个bytes，代表想要申请的内存大小。

Allocate函数是内联函数，不了解内联函数的同学可以看一下内联函数(inline Function)浅析，函数的实现体如下：

inline char* Arena::Allocate(size_t bytes)
{
  assert(bytes > 0);
  if( bytes <= alloc_bytes_remaining_ )
  {
    char* result = alloc_ptr_;
    alloc_ptr_ += bytes;
    alloc_bytes_remaining_ -= bytes;
    return result;
  }
  return AllocateFallback(bytes);
}

Allocate先检查当前内存块的空闲内存是否足够，如果足够就直接从当前内存块分配，如果不足，就调用AllocateFallback来分配内存。AllocateFallback顾名思义，就是在空闲内存不足时的应变分配计划。

如果是直接从当前内存块分配，Arena会从当前空闲内存的头部划出bytes的空间返回给调用方，并把alloc_ptr_指向新的空闲内存头部。并把alloc_bytes_remaining_减去bytes。

下面我们看一下AllocateFallback

AllocateFallback函数

char* Arena::AllocateFallback(size_t bytes)
{
  if( bytes > kBlockSize / 4 )
  {
    char* result = AllocateNewBlock(bytes);
    return result;
  }

  alloc_ptr_ = AllocateNewBlock(kBlockSize);
  alloc_bytes_remaining_ = kBlockSize;

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

AllocateFallback会先检查申请的bytes是否超过了内存块固定大小kBlockSize的四分之一，如果超过了就调用AllocateNewBlock直接分配一个bytes大小的内存块。如果没有超过，就调用AllocateNewBlock分配一个kBlockSize的新内存块。alloc_ptr_指向最新的内存块头部，并把alloc_bytes_remaining_置为kBlockSize。然后再从当前内存块分配内存并返回，分配逻辑和在Allocate中直接分配相同。

可以看到，两种情况下AllocateFallback都会调用AllocateNewBlock来分配新的内存块，只是申请的大小和用途不太一样。

AllocateNewBlock函数

AllocateNewBlock函数的实现体如下所示

char* Arena::AllocateNewBlock(size_t block_bytes)
{
  char* result = new char[block_bytes];
  blocks_.push_back(result);
  memory_usage_.fetch_add(block_bytes + sizeof(char*), std::memory_order_relaxed);
  return result;
}

AllocateNewBlock的逻辑其实非常简单，首先申请一个size为block_bytes的内存块（这里使用了char数组来实现），然后把内存块的指针存入blocks_数组，然后把block_bytes + sizeof(char*)累加到memory_usage_，可以看到memory_usage_并不是分配的内存块大小，还包含了每个内存块的指针大小。最后AllocateNewBlock返回申请到的内存块指针。

到这里就理清楚了Arena的Allocate分配内存的完整逻辑了，是不是还忘了点什么？

对的，除了Allocate，Arena还提供了另外一个外部接口AllocateAligned。顾名思义，这个接口分配的内存是对齐的。内存对齐是为了减少CPU取数据的次数，提高性能，内存对齐又可以展开为一篇新的文章了，篇幅原因，这里就不赘述了。我们重点介绍AllocateAligned的实现。

AllocateAligned函数

char* Arena::AllocateAligned(size_t bytes)
{
  const int align = (sizeof(void*) > 8) ? sizeof(void*) : 8;
  static_assert((align & (align - 1)) == 0, "Pointer size should be a power of 2");
  size_t current_mod = reinterpret_cast<uintptr_t>(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
  {
    result = AllocateFallback(bytes);
  }
  assert((reinterpret_cast<uintptr_t>(result) & (align - 1)) == 0);
  return result;
}

Step1：判断当前的系统需要对齐多少字节，指针的size就代表了系统的对齐字节。如果对齐字节小于8，就把align设置为8，反之设置为系统的对齐字节。
Step2：断言判断对齐字节数align是否为2的N次方，不是就出大问题了。。想想有一个31bit位的操作系统。这里用了一个比较tricky的方式，通过与操作来判断是否为2的N次方，避免了反复求余。
Step3：计算当前空闲内存的首地址未对齐的字节数current_mod。因为align一定是2的n次方，所以其二进制形式肯定是1[0]*这种形式，即一个1，N个0。那么align-1二进制结果就是N个1了。alloc_ptr进行与运算后只保留了低N位的值，自然也就是为对齐的字节数了
Step4：求需要补齐的字节数slop，如果current_mod为0，说明已经对齐了，不需要补字节，如果current_mod不为0，就需要补align-current_mode的字节数，这个很好理解。
Step5：bytes+slop得到实际需要申请的内存数，即实际申请的内存数应当为原先申请的内存数+对齐补上的字节数。
Step6：这里的分配逻辑就和Allocate里面一样了，如果需要内存needed小于等于当前空闲内存，就直接从当前内存块分配，只是首地址加上了对齐字节数的偏移量。这样分配的内存的首地址就是对齐了。
Step7：如果剩余空闲内存不足，就调用AllocateFallback进行分配，AllocateFallback是直接从系统申请内存的，所以内存一定是对齐的（不然这个系统要着还有何用），这里可能会让有些同学比较困惑。既然系统分配的内存时对齐的，为什么前面的还需要进行对齐呢？假设现在有一个新的对齐的内存块，首地址为0x00，系统的对齐字节数为8，我们先从内存块分配了5个字节内存，显然这个内存的首地址是对齐的，此时alloc_ptr_的值变为了0x05。如果此时我们再从剩下的空闲内存中分配5个字节的内存，新分配的5字节的首地址就是0x05了，没有对齐，所以需要补上3个字节进行对齐，这样新分配的内存的首地址就变成了0x08，就对齐了。
Step8：断言检查分配的内存首地址是否为2的整数倍
Step9：返回分配的内存首地址。

可以看到，在AllocateAligned中，使用了static_assert和assert，这个两个都是断言，有什么区别呢，感兴趣的同学可以移步C/C++中的断言(assert与static_assert)

源码版本

https://github.com/google/leveldb/releases/tag/1.22