LevelDB源碼解析27. Arena內存分配器
Arena內存分配器
在LevelDB裡面為了防止出現內存分配的碎片，採用了自己寫的一套內存分配管理器。名稱為Arena。
但是需要注意的是，這個內存分配器並不是為整個LevelDB項目考慮的。主要是為skiplist也就是memtable服務。
skiplist裡面記錄的是用戶傳進來的key/value，這些字元串有長有短，放到內存中的時候，很容易導致內存碎片。所以這裡寫了一個統一的內存管理器。
skiplist/memtable要申請內存的時候，就利用Arena分配器來分配內存。當skiplist/memtable要釋放的時候，就直接通過Arena類的block_把所有申請的內存釋放掉。
首先看一下這個類的內部成員。
class Arena {
// Allocation state
// 當前申請的內存塊的指針
char* alloc_ptr_;
// 已經申請的內存塊，剩餘的bytes數
size_t alloc_bytes_remaining_;
// Array of new[] allocated memory blocks
// 記錄所有已經分配的內存塊
std::vector<char*> blocks_;
// Total memory usage of the arena.
// size_t memory_usage_
// 也就是總共申請出去的內存數目
port::AtomicPointer memory_usage_;
};
內存需要放回去？
看一下Arena的公有介面，
class Arena {
// 跟malloc一樣的效果
char* Allocate(size_t bytes);
// 分配對齊的內存
char* AllocateAligned(size_t bytes);
// 統計所有由Arena生成的內存總數
// 這裡面可能包含一些內存碎片
// 所以返回的是近似值
// 其實沒有必要把memory_usage_設置成AtomicPointer的
// 直接設置成一般變數就可以了
// 比如size_t memory_usage_;
size_t MemoryUsage() const;
公有介面，本質上只有一個功能，那麼就是分配內存。分配內存的時候，由於有不同的需求，比如有的要求對齊，有的不需要對齊。所以這裡分出兩個小介面。 AllocateAligned和Allocate。
這裡就會發現，怎麼沒有還內存的介面呢？那豈不是一直要分配內存，從來不還回去？
這裡會涉及到兩方面：
- skiplist/memtable是沒有刪除介面的。所以裡面的元素總是不斷地添加進來。
- skiplist/memtable會在生成L0的文件之後，統一銷毀掉。所以內存塊可以直接由
Arena來統一銷毀。
基於這兩點原因，所以Arena是沒有還內存的介面的。
申請新塊
首先看一下一個比較簡單的函數。申請一個新塊。
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;
}
這個函數就是三個功能。
1. new一個新塊
2. 把這個塊指針放到vector裡面記錄著，析構的時候一起全部釋放掉。
3. 增加已分配的內存
AllocateFallback
AllocateFallback是對AllocateNewBlock一次封裝。這裡並不是把AllocateNewBlock直接給client使用的一個原因是，如果把AllocateNewBlock直接給client使用，那麼設計上講，就與直接使用new/delete沒有了區別。所以在AllocateFallback中會做一點點優化。
char* Arena::AllocateFallback(size_t bytes) {
// 只有當要申請的內存數大於1K的時候，才直接用NewBlock
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;
}
// 直接申請一個新的內存塊
alloc_ptr_ = AllocateNewBlock(kBlockSize);
alloc_bytes_remaining_ = kBlockSize;
// 從這個新塊裡面扣一個內存出來。
char* result = alloc_ptr_;
alloc_ptr_ += bytes;
alloc_bytes_remaining_ -= bytes;
return result;
}
總結一下，這個優化就是：
1. 申請一個新塊。
2. 如果要的內存空間大於1K，那麼直接返回相應的大小
3. 否則從4K的block裡面扣內存
兩個公有介面
這時再返回來看兩個公有介面。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 dont need
// them for our internal use).
// 說這麼多，實際上就是不允許只申請bytes > 0的情況
assert(bytes > 0);
// 如果當前塊餘下的空間還夠用
if (bytes <= alloc_bytes_remaining_) {
// 得到當前塊的指針頭
char* result = alloc_ptr_;
// 移動指針
alloc_ptr_ += bytes;
// 更新餘下的bytes數
alloc_bytes_remaining_ -= bytes;
return result;
}
// 當餘下的空間不夠用的時候，這裡就去申請一個新塊
// 如果要的bytes數目是大於1k，那麼就申請bytes那麼多。
// 如果要的bytes數目小於1k，那麼新申請的時候，就
// 按照4k來申請，並且從裡面扣.
return AllocateFallback(bytes);
}
AllocateAligned這裡就是分配對齊的內存塊。
char* Arena::AllocateAligned(size_t bytes) {
// 如果sizeof(void*)比8還要大，也就是遇到更高位的機器了？
// 如果更大，就用sizeof(void*)來對齊
// 否則就是用8來進行對齊
const int align = (sizeof(void*) > 8) ? sizeof(void*) : 8;
// 確保是2的指數次方
assert((align & (align-1)) == 0); // Pointer size should be a power of 2
// 取得當前地址未對齊的尾數
// 比如，要對齊的要求是8bytes
// 但是當前指針指向的是0x017這裡。
// 那麼餘下的current_mod就是1
size_t current_mod = reinterpret_cast<uintptr_t>(alloc_ptr_) & (align-1);
// 如果當前地址是0x17, 要求對齊是8 bytes
// 那麼current_mod = 1, slop 就是7
size_t slop = (current_mod == 0 ? 0 : align - current_mod);
// bytes + slop，
// 就是把餘下的這個slop = 7算在新的申請者頭上
// 返回的時候，直接向前移動slop個bytes
// 就完成了對齊。
size_t needed = bytes + slop;
// 總結一下：AllocateAligned就是需要計算一下
// 對齊地址
char* result;
// 這裡的邏輯就與Allocate完全一樣的了。
// 除了會移動一下slop以外。
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);
}
// 這裡斷言一下，返回地址result肯定是對齊的。
assert((reinterpret_cast<uintptr_t>(result) & (align-1)) == 0);
return result;
}
推薦閱讀：
