linux內(nèi)存管理策略
   linux低層采用三層結(jié)構(gòu)，實(shí)際使用中可以方便映射到兩層或者三層結(jié)構(gòu)，以適用不同的硬件結(jié)構(gòu)。最下層的申請(qǐng)內(nèi)存函數(shù)get_free_page。之上有三種類型的內(nèi)存分配函數(shù)
（1）kmalloc類型。內(nèi)核進(jìn)程使用，基于slab技術(shù)，用于管理小于內(nèi)存頁(yè)的內(nèi)存申請(qǐng)。思想出發(fā)點(diǎn)和應(yīng)用層面的內(nèi)存緩沖池同出一轍。但它針對(duì)內(nèi)核結(jié)構(gòu)，特別處理，應(yīng)用場(chǎng)景固定，不考慮釋放。不再深入探討。
（2）vmalloc類型。內(nèi)核進(jìn)程使用。用于申請(qǐng)不連續(xù)內(nèi)存。
（3）brk/mmap類型。用戶進(jìn)程使用。malloc/free實(shí)現(xiàn)的基礎(chǔ)。
有關(guān)詳細(xì)內(nèi)容，推薦http://www.kerneltravel.net/journal/v/mem.htm。http://www.kerneltravel.net上有不少內(nèi)核相關(guān)知識(shí)。
malloc系統(tǒng)的內(nèi)存管理策略
   malloc系統(tǒng)有自己的內(nèi)存池管理策略，malloc的時(shí)候，檢測(cè)池中是否有足夠內(nèi)存，有則直接分配，無(wú)則從內(nèi)存中調(diào)用brk/mmap函數(shù)分配，一般小于等于128k（可設(shè)置）的內(nèi)存，使用brk函數(shù)，此時(shí)堆向上（有人有的硬件或系統(tǒng)向下）增長(zhǎng)，大于128k的內(nèi)存使用mmap函數(shù)申請(qǐng)，此時(shí)堆的位置任意，無(wú)固定增長(zhǎng)方向。free的時(shí)候，檢測(cè)標(biāo)記是否是mmap申請(qǐng)，是則調(diào)用unmmap歸還給操作系統(tǒng)，非則檢測(cè)堆頂是否有大于128k的空間，有則通過(guò)brk歸還給操作系統(tǒng)，無(wú)則標(biāo)記未使用，仍在glibc的管理下。glibc為申請(qǐng)的內(nèi)存存儲(chǔ)多余的結(jié)構(gòu)用于管理，因此即使是malloc(0)，也會(huì)申請(qǐng)出內(nèi)存(一般16字節(jié)，依賴于malloc的實(shí)現(xiàn)方式），在應(yīng)用程序?qū)用妫琺alloc(0)申請(qǐng)出的內(nèi)存大小是0，因?yàn)閙alloc返回的時(shí)候在實(shí)際的內(nèi)存地址上加了16個(gè)字節(jié)偏移，而c99標(biāo)準(zhǔn)則規(guī)定malloc（0）的返回行為未定義。除了內(nèi)存塊頭域，malloc系統(tǒng)還有紅黑樹(shù)結(jié)構(gòu)保存內(nèi)存塊信息，不同的實(shí)現(xiàn)又有不同的分配策略。頻繁直接調(diào)用malloc，會(huì)增加內(nèi)存碎片，增加和內(nèi)核態(tài)交互的可能性，降低系統(tǒng)性能。linux下的glibc多為Doug Lea實(shí)現(xiàn)
應(yīng)用層面的內(nèi)存池管理
   1：不定長(zhǎng)內(nèi)存池。
   典型的實(shí)現(xiàn)有apr_pool。優(yōu)點(diǎn)是不需要為不同的數(shù)據(jù)類型創(chuàng)建不同的內(nèi)存池，缺點(diǎn)是造成分配出的內(nèi)存不能回收到池中。這是由于這種方案以session為粒度，以業(yè)務(wù)處理的層次性為設(shè)計(jì)基礎(chǔ)。
   apr_pool中的內(nèi)存池并不是僅僅一個(gè)內(nèi)存池，相反而是存在多個(gè)內(nèi)存池，這些內(nèi)存池之間形成層次結(jié)構(gòu)。根據(jù)處理階段的周期長(zhǎng)短引出了子內(nèi)存池的概念，與之對(duì)應(yīng)的是父內(nèi)存池以及根內(nèi)存池的概念，它們的唯一區(qū)別就是存在的周期的不同而已。比如對(duì)于HTTP連接而言，包括兩種內(nèi)存池：連接內(nèi)存池和請(qǐng)求內(nèi)存池。由于一個(gè)連接可能包含多個(gè)請(qǐng)求，因此連接的生存周期總是比一個(gè)請(qǐng)求的周期長(zhǎng)，為此連接處理中所需要的內(nèi)存則從連接內(nèi)存池中分配，而請(qǐng)求則從請(qǐng)求內(nèi)存池中分配。而一個(gè)請(qǐng)求處理完畢后請(qǐng)求內(nèi)存池被釋放，一個(gè)連接處理后連接內(nèi)存池被釋放。根內(nèi)存池在整個(gè)Apache運(yùn)行期間都存在,因此apr_pool比較適合用于內(nèi)存使用的生命期有明顯層次的情況.
2:定長(zhǎng)內(nèi)存池
    典型的實(shí)現(xiàn)有BOOST,LOKI。特點(diǎn)是為不同類型的數(shù)據(jù)結(jié)構(gòu)分別創(chuàng)建內(nèi)存池，需要內(nèi)存的時(shí)候從相應(yīng)的內(nèi)存池中申請(qǐng)內(nèi)存，優(yōu)點(diǎn)是可以在使用完畢立即把內(nèi)存歸還池中，可以更為細(xì)粒度的控制內(nèi)存塊。
 偽代碼分析LOKI內(nèi)存池:

//char型的firstAvailableBlock_所以沒(méi)辦法存儲(chǔ)大于255的位置
struct Chunk 
{
    void Init(std::size_t blockSize,unsigned char blocks);
    void Release();
    void* Allocate(std::size_t blockSize);
    void Deallocate(void* p,std::size_t blockSize);
    unsigned char* pData_;
    unsigned char firstAvailableBlock_, blocksAvailable_; //第一個(gè)可用block塊和可用block塊總數(shù)
};
/**//*
每個(gè)chunk管理一定數(shù)量的block,每個(gè)chunk中l(wèi)ock的申請(qǐng)和釋放時(shí)間都是O（1）。
chunk：首次申請(qǐng)一塊連續(xù)內(nèi)存，pdata_指向該內(nèi)存基址，依據(jù)block大小，劃分成多個(gè)連續(xù)的block，每個(gè)block開(kāi)頭的第一個(gè)字節(jié)保存該block的順序號(hào)，firstAvailableBlock_存儲(chǔ)上次分配出的block序號(hào)。
分配block：返回pdata_+firstAvailableBlock_*blocksize,同時(shí)firstAvailableBlock_賦值為該快的序列號(hào)
收回block：block指針假設(shè)為pblock,該塊序列號(hào)賦值為firstAvailableBlock_,firstAvailableBlock_賦值為(pblock-pdata_)/blocksize即可
*/

//得益于char的小所以可以分配很小的block出來(lái),且在需要對(duì)齊的情況下不會(huì)出現(xiàn)問(wèn)題
void Chunk::Init(std::size_t blockSize,unsigned char blocks)
{
    pData_ = new unsigned char(blockSize*blocks); 
    firstAvailableBlock_ = 0;    //上次分配的塊的序列號(hào)
    blocksAvailable_ = blocks;
    unsigned char i = 0;
    unsigned char *p = pData_;
    for (;i != blocks; p += blockSize)
    {
        *p = ++i;
    }
}

//分配blockSize單位固定大小的內(nèi)存
void* Chunk::Allocate(std::size_t blockSize)
{
    if (!blocksAvailable_)
    {
        return 0;
    }
    unsigned char* pResult = pData_ +(firstAvailableBlock_ * blockSize); //得到該塊的序列號(hào),第一個(gè)位置存儲(chǔ)的為序列號(hào)
    firstAvailableBlock_ = *pResult;
    --blocksAvailable_;
    return pResult;
}

void Chunk::Deallocate(void* p,std::size_t blockSize)
{
    ASSERT(p >= pData_);    //歸還的內(nèi)存必須大于分配起始內(nèi)存
    unsigned char* toRelese = static_cast<unsigned char*>(p); //強(qiáng)制轉(zhuǎn)換,靜態(tài)，不檢測(cè)運(yùn)行態(tài)
    *toRelese = firstAvailableBlock_;
    firstAvailableBlock_ = static_cast<unsigned char>((toRelese - pData_)/blockSize);
    ASSERT(firstAvailableBlock_ == (toRelese - pData_)/blockSize);
    ++blockSize;
}

#include "pool.h"

class FixedAllocator
{
public:
    void* Allocate(std::size_t blockSize_);
private:
    std::size_t blocksize_;
    unsigned char numBlocks_;
    typedef std::vector<Chunk> Chunks;
    Chunks Chunks_;
    Chunk* allocChunk_;    //上一次分配的Chunks
    Chunk* deallocChunk_;
};

/**//*
chunk中的block上限是255，不具有通用性，因此封裝了一層，成為FixedAllocator,它保存一個(gè)vector<chunk>。
FixedAllocator中的block申請(qǐng)：FixedAllocator中保存活動(dòng)的chunk（上次有空閑空間的chunk），申請(qǐng)block的
    時(shí)候如果活動(dòng)chunk有空閑快，直接申請(qǐng)，否則掃描vector，時(shí)間復(fù)雜度o(N),同時(shí)更新活動(dòng)chunk。
FixedAllocator中的回收block：簡(jiǎn)單想，給定block回收到FixedAllocator，自然要掃描vector，以確認(rèn) block屬于哪個(gè)chunk，以便chunk回收。
    實(shí)際實(shí)現(xiàn)的時(shí)候，Loki針對(duì)應(yīng)用場(chǎng)景進(jìn)行了優(yōu)化，一般使用都是批量使用，回收一般和申請(qǐng)順序相同或者相反，
    因此FixedAllocator保存上次回收block的chunk指針，每次回收優(yōu)先匹配這個(gè)chunk，匹配不上則以該chunk為中心，向兩側(cè)chunk順序檢測(cè)。
FixedAllocator帶來(lái)的優(yōu)點(diǎn)：上文提到的消除了block的上限限制。另一方面，可以以chunk為單位，把內(nèi)存歸還給操作系統(tǒng)。
    實(shí)際實(shí)現(xiàn)中防止剛釋放的內(nèi)存立即又被申請(qǐng)，是存在兩個(gè)空閑chunk的時(shí)候才回收一個(gè)。這個(gè)特點(diǎn)，這里暫時(shí)歸結(jié)為優(yōu)點(diǎn)吧。
    實(shí)際使用中，回收多余內(nèi)存?zhèn)€人認(rèn)為是個(gè)缺點(diǎn)，意義并不是很大。
FixedAllocator帶來(lái)的缺點(diǎn)：很明顯，就是申請(qǐng)回收block的時(shí)間復(fù)雜度。
*/

/**///////////////////////////////////////////////////////////////////////////
void* FixedAllocator::Allocate(std::size_t blockSize_)
{
    if (allocChunk_ ==0 || allocChunk_.blocksAvailable_ == 0)
    {
        Chunks::iterator i = Chunks.begin();
        for (;;++i)
        {
            if (i ==  Chunks_.end())
            {
                Chunks_.push_back(Chunk());
                Chunk& newChunk = Chunks_.back();
                newChunk.Init(blockSize_,Blocks);
                allocChunk_ = newChunk;
                deallocChunk_ = &Chunks_.front();
            }
            if (i->blocksAvailable_)
            {
                allocChunk_ = &*i;
                break;
            }
        }
    }
    ASSERT(allocChunk_ != 0);
    ASSERT(allocChunk_->blocksAvailable_ > 0);
    return allocChunk_->Allocate(blockSize_);        
}

class SmallObjAllocator
{
public:
    SmallObjAllocator(std::size_t chunkSize,std::size_t maxObjectSize); //chunk的預(yù)設(shè)大小,超過(guò)maxObjectSize大小的用new申請(qǐng)
    void* Allocate(std::size_t numBytes);
    void Deallocate(void* p, std::size_t size);
private:
    std::vector<FixedAllocator> pool_;
    FixedAllocator* pLastAlloc_;    //最后一次分配用的FixedAllocator
    FixedAllocator* pLastDealloc_;
};
/**//*
截至到FixedAllocator層面blocksize都是定長(zhǎng)。因此封裝一層適用于任意長(zhǎng)度的內(nèi)存申請(qǐng)。
SmallObjAllocator保存了一個(gè)FixedAllocator的數(shù)組pool_，存儲(chǔ)擁有不同block長(zhǎng)度的FixedAllocator。
    當(dāng)前SmallObjAllocator的構(gòu)造函數(shù)有3個(gè)參數(shù)：chunksize，maxblocksize，alignsize。
    數(shù)組元素個(gè)數(shù)取 maxblocksize除以alignsize的向上取整。每個(gè)FixedAllocator中實(shí)際的blocksize是（下標(biāo)＋1） *alignsize。
SmallObjAllocator中block申請(qǐng)：依據(jù)block和alignsize的商直接取到數(shù)組pool_下標(biāo)，使用相應(yīng)的FixedAllocator申請(qǐng)。
SmallObjAllocator中回收block：根據(jù)block和alignsize的商直接找到相應(yīng)的FixedAllocator回收。
優(yōu)點(diǎn)：差異化各種長(zhǎng)度的對(duì)象申請(qǐng)，增強(qiáng)了易用性。
缺點(diǎn)：增加掃描的時(shí)間復(fù)雜度，當(dāng)前版本的loki浪費(fèi)內(nèi)存。這也是進(jìn)一步封裝，屏蔽定長(zhǎng)申請(qǐng)的細(xì)節(jié)，帶來(lái)的負(fù)面效應(yīng)。
*/
class SmallObject
{
//重載new，delete,設(shè)計(jì)為模板函數(shù)等
};
/**//*
暴露給外部使用的一層。引入模版，當(dāng)前版本 SmallObject有6個(gè)模版參數(shù)，第一個(gè)是線程策略，緊接著的三個(gè)正好是SmallObjAllocator層面的
三個(gè)構(gòu)造參數(shù)，下面的一個(gè)生存期策略，最后的是鎖方式。
這里說(shuō)下SmallObjAllocator層面的三個(gè)默認(rèn)參數(shù)值，分別是4096，256，4。意味著SmallObjAllocator層面有數(shù)組（256+4-1)/4=64個(gè)，
數(shù)組存儲(chǔ)的FixedAllocator中的chunksize一般都是4096（當(dāng)4096<= blocksize*255時(shí)候）字節(jié)（第一個(gè)chunk的申請(qǐng)推遲到首次使用的時(shí)候），
各FixedAllocator中的chunk的 blocksize依次是4、8256，大于256字節(jié)的內(nèi)存申請(qǐng)交給系統(tǒng)的malooc/new管理，
數(shù)組中FixedAllocator 中單個(gè)chunk中的blocknum依次是4096/4=824>255取255、2554096/256=16。如果這不能滿足需求，
請(qǐng)調(diào)用的時(shí)候顯式賦值。
當(dāng)前l(fā)oki提供了三種線程策略：
SingleThreaded  單線程 
ObjectLevelLockable  對(duì)象級(jí)別，一個(gè)對(duì)象一個(gè)鎖 
ClassLevelLockable  類級(jí)別，一個(gè)類一個(gè)鎖，該類的所有對(duì)象共用該鎖 
目前只提供了一種鎖機(jī)制：Mutex
它的基類SmallObjectBase復(fù)寫(xiě)了new/delete操作子，因此直接繼承SmallObject就可以象普通的類一樣new/delete，并且從內(nèi)存池分配內(nèi)存。
SmalObject中block申請(qǐng)和釋放都從一個(gè)全局的SmallObjAllocator單例進(jìn)行。
*/

(2)boost::pool系列。boost 的內(nèi)存池最低層是simple_segregated_storage，類似于Loki中的chunk，在其中申請(qǐng)釋放block（boost中把 block稱為chunk，暈死，這里還是稱其為block）采用了和loki的chunk中同樣的算法，不同的是 simple_segregated_storage使用void*保存block的塊序號(hào)，loki中使用char，因此boost中的 simple_segregated_storage沒(méi)有255的上限限制，自然也就不需要再其上再封裝一層類似與FixedAllocator的層面。另boost沒(méi)有屏蔽塊的大小，直接提供定長(zhǎng)的接口給用戶，省掉了SmallObjAllocator層面。因此boost的內(nèi)存池申請(qǐng)釋放block的時(shí)間復(fù)雜度都是O(1)（object_pool和pool_allocator除外），另避免的小內(nèi)存的浪費(fèi)，同時(shí)boost不能象loki那樣在將 block歸還給內(nèi)存池的時(shí)候根據(jù)chunk的空閑數(shù)量釋放內(nèi)存歸還給系統(tǒng)，只能顯式調(diào)用釋放內(nèi)存函數(shù)或者等內(nèi)存池銷毀的時(shí)候，基本上和內(nèi)存池生命周期內(nèi)永不釋放沒(méi)什么區(qū)別。
    boost的最低層是simple_segregated_storage,主要算法和loki中的chunk一樣，不多說(shuō)了。這里說(shuō)下影響上層接口的兩類實(shí)現(xiàn)：add_block/malloc/free、add_ordered_block/malloc/ordered_free，兩種低層實(shí)現(xiàn)造成 boost上層設(shè)計(jì)的成功與失敗,前者效率高，和loki一樣直接增加釋放,時(shí)間復(fù)雜度O(1)，后者掃描排序，時(shí)間復(fù)雜度O(n)。
    boost提供了四種內(nèi)存池模型供使用：pool、object_pool、singleton_pool、pool_allocator/fast_pool_allocator。
1）pool
基本的定長(zhǎng)內(nèi)存池

#include <boost/pool/pool.hpp>
typedef struct student_st
{
   char name[10];
   int age;
}CStudent;
int main()
{
   boost::pool<> student_pool(sizeof(CStudent));
   CStudent * const obj=(CStudent *)student_pool.malloc();
   student_pool.free(obj);
   return 0;
}

    pool的模版參數(shù)只有一個(gè)分配子類型，boost提供了兩種 default_user_allocator_new_delete/default_user_allocator_malloc_free，指明申請(qǐng)釋放內(nèi)存的時(shí)候使用new/delete，還是malloc/free，默認(rèn)是default_user_allocator_new_delete。構(gòu)造函數(shù)有2個(gè)參數(shù)：nrequested_size,nnext_size。nrequested_size是block的大小（因?yàn)関oid*保存序號(hào)，因此boost內(nèi)置了block的最小值，nrequested_size過(guò)小則取內(nèi)置值），nnext_size是 simple_segregated_storage中內(nèi)存不足的時(shí)候，申請(qǐng)的block數(shù)量，默認(rèn)是32。最全面的實(shí)例化pool類似這樣： boost::pool<boost::default_user_allocator_malloc_free> student_pool(sizeof(CStudent),255);
    pool提供的函數(shù)主要有：

malloc/free	基于add_block/malloc/free實(shí)現(xiàn)，高效
ordered_malloc/ordered_free	基于add_ordered_block/malloc/ordered_free實(shí)現(xiàn)，在pool中無(wú)任何意義，切勿使用。
release_memory/purge_memory	前者釋放池中未使用內(nèi)存，后者釋放池中所有內(nèi)存。另池析構(gòu)也會(huì)釋放內(nèi)存

2）object_pool

#include <boost/pool/object_pool.hpp>

class A{
public:
   A():data_(0){}
private:
   int data_;
};
int main()
{
   boost::object_pool<A> obj_pool;
   A *const pA=obj_pool.construct();
   obj_pool.destroy(pA);
   return 0;
}

    object_pool繼承至pool，有兩個(gè)模版參數(shù)，第一個(gè)就是對(duì)象類型，第二個(gè)是分配子類型，默認(rèn)同pool是 default_user_allocator_new_delete。構(gòu)造函數(shù)參數(shù)只有nnext_size，意義以及默認(rèn)值同pool。最全面的實(shí)例化object_pool類似這樣：boost::pool<A,boost:: default_user_allocator_malloc_free> obj_pool(255);
object_pool提供的函數(shù)主要有（繼承至父類的略）：

malloc/free	復(fù)寫(xiě)pool的malloc/free，add_ordered_block/malloc/ordered_free實(shí)現(xiàn)
construct/destroy	基于本類的malloc/free實(shí)現(xiàn)，額外調(diào)用默認(rèn)構(gòu)造函數(shù)和默認(rèn)析構(gòu)函數(shù)。
~object_pool	若析構(gòu)的時(shí)候有對(duì)象未被destroy，可以檢測(cè)到，釋放內(nèi)存前對(duì)其執(zhí)行destroy

   object_pool　主要著眼于“自動(dòng)析構(gòu)”，在沒(méi)有g(shù)c的情況下，達(dá)到提高效率和自動(dòng)管理內(nèi)存的目的。而且它也特別適合于“多次申請(qǐng)，一次釋放”的情況.所以它甚至是鼓勵(lì)你忽略使用destroy（從它的例子就可以看出來(lái)）。

destroy函數(shù)并沒(méi)有提高復(fù)雜度，因?yàn)閮?nèi)部鏈表始終處于有序狀態(tài)（由于使用order_malloc,order_free)，所以不論是逐個(gè)釋放，還是成批釋放，它的復(fù)雜度都是O(N)
3）singleton_pool
pool的加鎖版本。

#include <boost/pool/singleton_pool.hpp>
typedef struct student_st
{
   char name[10];
   int age;
}CStudent;
typedef struct singleton_pool_tag{}singleton_pool_tag;
int main()
{
   typedef boost::singleton_pool<singleton_pool_tag,sizeof(CStudent)>  global;
   CStudent * const df=(CStudent *)global::malloc();
   global::free(df);
   return 0;
}

    singleton_pool為單例類，是對(duì)pool的加鎖封裝，適用于多線程環(huán)境，其中所有函數(shù)都是靜態(tài)類型。它的模版參數(shù)有5個(gè)，tag：標(biāo)記而已，無(wú)意義；RequestedSize：block的長(zhǎng)度；UserAllocator：分配子，默認(rèn)還是 default_user_allocator_new_delete；Mutex：鎖機(jī)制，默認(rèn)值最終依賴于系統(tǒng)環(huán)境，linux下是 pthread_mutex，它是對(duì)pthread_mutex_t的封裝；NextSize：內(nèi)存不足的時(shí)候，申請(qǐng)的block數(shù)量，默認(rèn)是32。最全面的使用singleton_pool類似這樣：typedef boost::singleton_pool<singleton_pool_tag,sizeof(CStudent),default_user_allocator_new_delete,details::pool::default_mutex,200>  global;
    它暴露的函數(shù)和pool相同。
4）pool_allocator/fast_pool_allocator
    stl::allocator的替換方案。兩者都是基于singleton_pool實(shí)現(xiàn)，實(shí)現(xiàn)了stl::allocator要求的接口規(guī)范。兩者的使用相同，區(qū)別在于pool_allocator的實(shí)現(xiàn)調(diào)用ordered_malloc/ordered_free， fast_pool_allocator的實(shí)現(xiàn)調(diào)用malloc/free，因此推薦使用后者。

#include <boost/pool/pool_alloc.hpp>
#include <vector>
typedef struct student_st
{
 char name[10];
 int age;
}CStudent;

int main()
{
  std::vector<CStudent *,boost::fast_pool_allocator<CStudent *> > v(8);
  CStudent *pObj=new CStudent();
  v[1]=pObj;
  boost::singleton_pool<boost::fast_pool_allocator_tag,sizeof(CStudent *)>::purge_memory(); 
  return 0;
}

    fast_pool_allocator的模版參數(shù)有四個(gè)：類型，分配子，鎖類型，內(nèi)存不足時(shí)的申請(qǐng)的block數(shù)量，后三者都有默認(rèn)值，不再說(shuō)了。它使用的singleton_pool的tag是boost::fast_pool_allocator_tag。