LevelDB Arena源码分析

什么是Arena

Arena是LevelDB中实现的一个简易的内存池。因为LevelDB是一个key-value数据库，所以当为较小的key或value分配内存时可能会引起内存碎片以及性能问题（频繁调用new和delete）。Arena就是为了解决这些问题的。Arena的实现非常简洁，不过100多行C++代码，十分适合学习。下面我们就一起了解一下Google大佬们管理内存的方法吧。

Arena的实现思路

既然分配较小的内存会导致产生内存碎片，那么我们可以先分配一块较大的内存块，然后在将这个内存块分割成若干个较小的内存块分配给使用者来存储较小的key或value，这就是Arena的基本思路。

首先我们来看一下Arena的几个成员变量，它们指示了Arena当前的状态：

char* alloc_ptr_; // 内存块未分配内存的起始地址
size_t alloc_bytes_remaining_; // 内存块中未分配的字节数
std::vector<char*> blocks_; // Arena已申请的内存块
std::atomic<size_t> memory_usage_; // Arena的内存使用量

来看下面一张图：

Arena的blocks_成员存储着Arena已经申请的内存块。alloc_ptr_指向当前内存块中尚未分配空间的起始地址。当需要Arena分配n个字节的内存时，如果n大于1024（也就是1KB），则Arena会申请一个大小为n的内存块并返回内存块的地址，alloc_ptr_和alloc_bytes_remaining_的值都不会改变（之所以这样做是为了避免浪费大量内存）。如果n小于1024并且当前块中的内存块中剩余的字节数大于或等于n，那么Arena会以alloc_ptr_为起始地址分配n个字节的内存返回给申请者，并将alloc_ptr_向后移动n个字节指向新的未分配空间的起始地址。如果内存块剩余的空间小于n，则Arena会申请新的一块大小为4KB的内存块给调用者分配内存，之前的内存块中尚未分配的内存就浪费了。所以Arena最多会浪费1/4的内存。

Arena的实现

Arena为使用者提供了三个成员函数接口：

char* Allocate(size_t bytes);

char* AllocateAligned(size_t bytes);

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

Allocate用于为调用者分配bytes个字节的内存，AllocateAligned则为调用者分配bytes个字节的对齐的内存，MemoryUsage用于查看该Arena对象使用的内存总量。我们重点看一下Allocate和AllocateAligned的实现：

Allocate的实现

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首先会判断一下当前块中剩余的空间是否足够分配bytes个字节的内存。如果空间足够，Allocate会将alloc_ptr_向后移动bytes个字节让其指向新的未分配的内存的起始地址，并将alloc_bytes_remaining_减小bytes，然后返回分配的内存。如果当前块的剩余空间不足以分配bytes字节的内存，则Allocate会调用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用于为Arena申请新的内存块。首先，AllocateFallback会判断bytes是否大于1024。如果大于1024，AllocateFallback会调用AllocateNewBlock申请一个大小为bytes的内存块并返回，Arena会继续使用当前内存块进行下一次的内存分配。弱国小于或等于1024，则AllocateFallback会调用AllocateNewBlock申请一个大小为4KB的内存块并在新的内存块上分配内存。原来的内存块中未分配的空间则被浪费。

我们再来看一下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的代码很简单，它首先使用new[]申请block_bytes个字节的内存，然后将这个内存块加入block_中（Arena在析构时会释放掉block_中所有的内存），再记录一下内存的使用量就可以了。

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;
}

AllocateAligned以sizeof(void*)对齐内存（如果sizeof(void*)大于8的话），所以在64位机上它使用8字节对齐。变量slop的值是对齐到8个字节所需要的字节数。slop加上bytes就是分配这段内存所需要的字节数。接下来的流程就跟Allocate一样了。

总结

Arena的主要内容基本上就分析完了。虽然Arena的设计简单，却又十分巧妙，成功解决了内存碎片以及频繁调用new和delete的问题。博主接下来的一个小项目需要内存池来分配空间存储一些小的字符串，正好可以实现一个类似于Arena的内存池试试效果。

参考

1. LevelDB Github仓库
2. leveldb 笔记三：Arena 内存管理