LevelDB源碼分析之三：arena

一.原理

? ? ? ? arena是LevelDB內部實現(xiàn)的內存池。

? ? ? ? 我們知道，對于一個高性能的服務器端程序來說，內存的使用非常重要。C++提供了new/delete來管理內存的申請和釋放，但是對于小對象來說，直接使用new/delete代價比較大，要付出額外的空間和時間，性價比不高。另外，我們也要避免多次的申請和釋放引起的內存碎片。一旦碎片到達一定程度，即使剩余內存總量夠用，但由于缺乏足夠的連續(xù)空閑空間，導致內存不夠用的假象。
? ? ? ? C++ STL為了避免內存碎片，實現(xiàn)一個復雜的內存池，LevelDB中則沒有那么復雜，只是實現(xiàn)了一個"一次性"內存池arena。在leveldb里面，并不是所有的地方都使用了這個內存池，主要是memtable使用，主要是用于臨時存放用戶的更新數(shù)據，由于更新的數(shù)據可能很小，所以這里使用內存池就很合適。

? ? ? ? 為了避免小對象的頻繁分配，需要減少對new的調用，最簡單的做法就是申請大塊的內存，多次分給客戶。LevelDB用一個vector

二.頭文件

class?Arena?{
?public:
??Arena();
??~Arena();

??//?Return?a?pointer?to?a?newly?allocated?memory?block?of?"bytes"?bytes.
??//?分配bytes大小的內存塊，返回指向該內存塊的指針
??char*?Allocate(size_t?bytes);

??//?Allocate?memory?with?the?normal?alignment?guarantees?provided?by?malloc
??//?基于malloc的字節(jié)對齊內存分配
??char*?AllocateAligned(size_t?bytes);

??//?Returns?an?estimate?of?the?total?memory?usage?of?data?allocated
??//?by?the?arena?(including?space?allocated?but?not?yet?used?for?user
??//?allocations).
??//?返回整個內存池使用內存的總大?。ú痪_），這里只計算了已分配內存塊的總大小和
??//?存儲各個內存塊指針所用的空間。并未計算alloc_ptr_和alloc_bytes_remaining_
??//?等數(shù)據成員的大小。
??size_t?MemoryUsage()?const?{
????return?blocks_memory_?+?blocks_.capacity()?*?sizeof(char*);
??}

?private:
??char*?AllocateFallback(size_t?bytes);
??char*?AllocateNewBlock(size_t?block_bytes);

??//?Allocation?state
??//?當前內存塊(block)偏移量指針，也就是未使用內存的首地址
??char*?alloc_ptr_;
??//?表示當前內存塊(block)中未使用的空間大小
??size_t?alloc_bytes_remaining_;

??//?Array?of?new[]?allocated?memory?blocks
??//?用來存儲每一次向系統(tǒng)請求分配的內存塊的指針
??std::vectorblocks_;

??//?Bytes?of?memory?in?blocks?allocated?so?far
??//?迄今為止分配的內存塊的總大小
??size_t?blocks_memory_;

??//?No?copying?allowed
??Arena(const?Arena&);
??void?operator=(const?Arena&);
};

三.源文件

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).
??//?如果允許分配0字節(jié)的內存，那么返回值在語義上會比較難以理解，因此這里禁止bytes=0
??//?如果需求的內存小于當前內存塊中剩余的內存，那么直接從當前內存快中獲取
??assert(bytes?>?0);
??if?(bytes?<=?alloc_bytes_remaining_)?{
????char*?result?=?alloc_ptr_;
????alloc_ptr_?+=?bytes;
????alloc_bytes_remaining_?-=?bytes;
????return?result;
??}
??//?因為alloc_bytes_remaining_初始為0，因此第一次調用Allocate實際上直接調用的是AllocateFallback
??//?如果需求的內存大于內存塊中剩余的內存，也會調用AllocateFallback
??return?AllocateFallback(bytes);
}

char*?Arena::AllocateFallback(size_t?bytes)?{
??//?如果需求的內存大于內存塊中剩余的內存，而且大于1K，則給這內存單獨分配一塊bytes大小的內存。
??//?這樣可以避免浪費過多的空間（因為如果bytes大于1K也從4K的內存塊去取用，那么如果當前內存塊中剛好剩余
??//?1K，只能再新建一個4K的內存塊，并且取用bytes。此時新建的內存塊是當前內存塊，后續(xù)操作都是基于當前內
??//?存塊的，那么原內存塊中的1K空間就浪費了）
??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;
??}
??//?如果需求的內存大于內存塊中剩余的內存，而且小于1K，則重新分配一個內存塊，默認大小4K，
??//?原內存塊中剩余的內存浪費掉（這樣雖然也會浪費，但是浪費的空間小于1K）。并在新內存塊
??//?中取用bytes大小的內存。
??//?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;
}

//?提供了字節(jié)對齊內存分配，一般情況是4字節(jié)或8個字節(jié)對齊分配，
//?對齊內存的好處簡單的說就是加速內存訪問。
//?首先獲取一個指針的大小const?int?align?=?sizeof(void*)，
//?很明顯，在32位系統(tǒng)下是4?,64位系統(tǒng)下是8?，為了表述方便，我們假設是32位系統(tǒng)，即align?＝?4,
//?然后將我們使用的char?*?指針地址轉換為一個無符號整型(reinterpret_cast(result):
//?It?is?an?unsigned?int?that?is?guaranteed?to?be?the?same?size?as?a?pointer.)，通過與操作來
//?獲取size_t?current_mod?=?reinterpret_cast(alloc_ptr_)?&?(align-1);當前指針模4
//?的值，有了這個值以后，我們就容易知道，還差?slop?=?align?-?current_mod多個字節(jié)，內存才是對齊的，
//?所以有了result?=?alloc_ptr?+?slop。那么獲取bytes大小的內存，實際上需要的大小為needed?=?bytes?+?slop。
char*?Arena::AllocateAligned(size_t?bytes)?{
??const?int?align?=?sizeof(void*);????//?We'll?align?to?pointer?size
??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;
}

關于內存對齊可參考：內存對齊到底是怎么回事？

//?分配新的內存塊
char*?Arena::AllocateNewBlock(size_t?block_bytes)?{
??char*?result?=?new?char[block_bytes];
??blocks_memory_?+=?block_bytes;
??blocks_.push_back(result);
??return?result;
}

//?釋放整個內存池所占內存
Arena::~Arena()?{
??for?(size_t?i?=?0;?i?<?blocks_.size();?i++)?{
????delete[]?blocks_[i];
??}
}