allocate需要如下需求：
- 如何設計內(nèi)存池始鱼；
- 如何設計字節(jié)對齊臀防；
- 如何設計統(tǒng)計內(nèi)存使用情況为流；（待完成）
- 如何設計單元測試驗證內(nèi)存池的正確性酸茴。（待完成）
一些技術(shù)問題：
- malloc是已經(jīng)實現(xiàn)內(nèi)存對齊了烫映，問如何實現(xiàn)的沼本，怎么證明？（未解決）
- free和delete是如何實現(xiàn)的锭沟，如何知道釋放多少內(nèi)存抽兆。（未解決）
一 如何設計內(nèi)存池
內(nèi)存池一般而言，即是大塊內(nèi)存直接分配族淮，小塊內(nèi)存則先申請一個大塊內(nèi)存辫红，然后不斷地使用這個大塊內(nèi)存直至用完∽＠保基本算法如下：
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_) { //是否能從可用內(nèi)存中獲取
char* result = alloc_ptr_;
alloc_ptr_ += bytes;
alloc_bytes_remaining_ -= bytes;
return result;
}
return AllocateFallback(bytes); //不能贴妻，去申請內(nèi)存
}
大塊內(nèi)存一定無法從可用內(nèi)存中獲取，小塊內(nèi)存則需要看剩余內(nèi)存大小较幌，如果剩余量小于需求揍瑟，則也需要申請，否則乍炉，不需要申請绢片。
所以小塊內(nèi)存共用的大塊內(nèi)存的使用情況，需要使用如下兩個變量來標識：
// Allocation state
char* alloc_ptr_; //大塊內(nèi)存的可用位置岛琼；
size_t alloc_bytes_remaining_; //當前大塊內(nèi)存還剩余多少
簡化了小塊內(nèi)存的分配底循，大塊內(nèi)存的分配邏輯如下：
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) { //所有申請內(nèi)存的操作都在這；
char* result = new char[block_bytes];
blocks_.push_back(result);
memory_usage_.NoBarrier_Store(
reinterpret_cast<void*>(MemoryUsage() + block_bytes + sizeof(char*)));
return result;
}
申請大塊內(nèi)存有兩種情況：
（1）用戶本身申請的就是大內(nèi)存槐瑞；
（2）用戶申請的是小內(nèi)存熙涤，但是小內(nèi)存所使用的大內(nèi)存塊用完了。
對于第一種情況，直接調(diào)用AllocateNewBlock方法祠挫，申請出那么大的內(nèi)存來并交給用戶就可以了那槽。
對于第二種情況，調(diào)用完AllocateNewBlock方法申請固定大小內(nèi)存（kBlockSize）等舔，還需要設置 alloc_ptr_和alloc_bytes_remaining_變量骚灸；最后在這塊新申請的大內(nèi)存中分配內(nèi)存給用戶。
內(nèi)存的釋放是統(tǒng)一在一起進行的慌植，位于分配器的析構(gòu)函數(shù)中：
Arena::~Arena() {
for (size_t i = 0; i < blocks_.size(); i++) {
delete[] blocks_[i];
}
}
blocks_定義如下：
// Array of new[] allocated memory blocks
std::vector<char*> blocks_;
blocks_包含了所有AllocateNewBlock方法申請的內(nèi)存甚牲，最后統(tǒng)一釋放。
一些問題：
- 小內(nèi)存共用的大塊內(nèi)存是多大蝶柿，即一次申請多大合適丈钙？（相關(guān)的論文查詢）
leveldb中是這個大小：
static const int kBlockSize = 4096;
申請多大的內(nèi)存適合直接返回給用戶交汤，而不是共用大內(nèi)存塊雏赦？
這種分為兩種情況：
（1）存在可用大塊內(nèi)存時，只要大塊內(nèi)存夠用蜻展，就都是直接返回給用戶喉誊；
（2）不存在可用的大塊內(nèi)存時，超過kBlockSize的1/4纵顾，就直接申請相應大小的內(nèi)存返回給用戶伍茄，而不是當作小內(nèi)存來申請kBlockSize大小的內(nèi)存。以上策略存在內(nèi)存的浪費施逾，具體表現(xiàn)為：
當用戶新申請的內(nèi)存不在可用內(nèi)存大小范圍內(nèi)敷矫，且小于kBlockSize時，那一段可用內(nèi)存就被浪費了汉额，去新申請新的內(nèi)存了曹仗， alloc_ptr_從新內(nèi)存開始。內(nèi)存是最后統(tǒng)一釋放的蠕搜，所以是不是需要一些策略來提前釋放以節(jié)約內(nèi)存怎茫？具體的釋放時機是什么？
二 如何設計字節(jié)對齊
malloc分配的內(nèi)存一定是對齊的妓灌，含義是其返回的地址一定是2的冪次（內(nèi)存對齊的大小一般是指針的大小轨蛤，指針的大小一定是2的冪次）。
所以對齊的大小align求法：
const int align = (sizeof(void*) > 8) ? sizeof(void*) : 8;
對齊之后的地址一定滿足（align - 1的值中1的個數(shù)代表了返回值指針最后的0的個數(shù)）：
assert((reinterpret_cast<uintptr_t>(result) & (align-1)) == 0);
具體算法如下：
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<uintptr_t>(alloc_ptr_) & (align-1); //alloc_ptr_的后n位虫埂，n為對齊的位數(shù)
size_t slop = (current_mod == 0 ? 0 : align - current_mod); //對齊需要空余的字節(jié)數(shù)
size_t needed = bytes + slop;
char* result;
if (needed <= alloc_bytes_remaining_) { //類似于上一小節(jié)的Allocate
result = alloc_ptr_ + slop;
alloc_ptr_ += needed;
alloc_bytes_remaining_ -= needed;
} else {
// AllocateFallback always returned aligned memory
result = AllocateFallback(bytes); //調(diào)用malloc的一定是內(nèi)存對齊的祥山；
}
assert((reinterpret_cast<uintptr_t>(result) & (align-1)) == 0);
return result;
}
函數(shù)同樣分為兩部分來處理：
（1）申請內(nèi)存大小 + 對齊字節(jié)數(shù) > 可用內(nèi)存大小，此時直接調(diào)用malloc去申請（此時可能會造成內(nèi)存的浪費）掉伏，此時一定是內(nèi)存對齊的缝呕；
（2）申請內(nèi)存大小 + 對齊字節(jié)數(shù) < 可用內(nèi)存大小澳窑，手動對齊：將alloc_ptr_調(diào)整到對齊位置，作為返回結(jié)果供常，再調(diào)整alloc_ptr_到下一可用位置摊聋。其中對齊的結(jié)果是返回值對齊的，最后的alloc_ptr_不是對齊的栈暇。
三 如何設計統(tǒng)計內(nèi)存使用情況栗精；
內(nèi)存的使用需要進行統(tǒng)計，以方便進行監(jiān)控以及內(nèi)存泄露的查詢瞻鹏。
內(nèi)存的統(tǒng)計要求所有的內(nèi)存申請工作都需要在同一個函數(shù)中進行：AllocateNewBlock。
