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

//char型的firstAvailableBlock_所以沒辦法存儲大于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_; //第一個可用block塊和可用block塊總數(shù)
};
/**//*
每個chunk管理一定數(shù)量的block,每個chunk中l(wèi)ock的申請和釋放時間都是O（1）。
chunk：首次申請一塊連續(xù)內(nèi)存，pdata_指向該內(nèi)存基址，依據(jù)block大小，劃分成多個連續(xù)的block，每個block開頭的第一個字節(jié)保存該block的順序號，firstAvailableBlock_存儲上次分配出的block序號。
分配block：返回pdata_+firstAvailableBlock_*blocksize,同時firstAvailableBlock_賦值為該快的序列號
收回block：block指針假設(shè)為pblock,該塊序列號賦值為firstAvailableBlock_,firstAvailableBlock_賦值為(pblock-pdata_)/blocksize即可
*/

//得益于char的小所以可以分配很小的block出來,且在需要對齊的情況下不會出現(xiàn)問題
void Chunk::Init(std::size_t blockSize,unsigned char blocks)
{
    pData_ = new unsigned char(blockSize*blocks); 
    firstAvailableBlock_ = 0;    //上次分配的塊的序列號
    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); //得到該塊的序列號,第一個位置存儲的為序列號
    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); //強制轉(zhuǎn)換,靜態(tài)，不檢測運行態(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,它保存一個vector<chunk>。
FixedAllocator中的block申請：FixedAllocator中保存活動的chunk（上次有空閑空間的chunk），申請block的
    時候如果活動chunk有空閑快，直接申請，否則掃描vector，時間復(fù)雜度o(N),同時更新活動chunk。
FixedAllocator中的回收block：簡單想，給定block回收到FixedAllocator，自然要掃描vector，以確認(rèn) block屬于哪個chunk，以便chunk回收。
    實際實現(xiàn)的時候，Loki針對應(yīng)用場景進(jìn)行了優(yōu)化，一般使用都是批量使用，回收一般和申請順序相同或者相反，
    因此FixedAllocator保存上次回收block的chunk指針，每次回收優(yōu)先匹配這個chunk，匹配不上則以該chunk為中心，向兩側(cè)chunk順序檢測。
FixedAllocator帶來的優(yōu)點：上文提到的消除了block的上限限制。另一方面，可以以chunk為單位，把內(nèi)存歸還給操作系統(tǒng)。
    實際實現(xiàn)中防止剛釋放的內(nèi)存立即又被申請，是存在兩個空閑chunk的時候才回收一個。這個特點，這里暫時歸結(jié)為優(yōu)點吧。
    實際使用中，回收多余內(nèi)存?zhèn)€人認(rèn)為是個缺點，意義并不是很大。
FixedAllocator帶來的缺點：很明顯，就是申請回收block的時間復(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è)大小,超過maxObjectSize大小的用new申請
    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都是定長。因此封裝一層適用于任意長度的內(nèi)存申請。
SmallObjAllocator保存了一個FixedAllocator的數(shù)組pool_，存儲擁有不同block長度的FixedAllocator。
    當(dāng)前SmallObjAllocator的構(gòu)造函數(shù)有3個參數(shù)：chunksize，maxblocksize，alignsize。
    數(shù)組元素個數(shù)取 maxblocksize除以alignsize的向上取整。每個FixedAllocator中實際的blocksize是（下標(biāo)＋1） *alignsize。
SmallObjAllocator中block申請：依據(jù)block和alignsize的商直接取到數(shù)組pool_下標(biāo)，使用相應(yīng)的FixedAllocator申請。
SmallObjAllocator中回收block：根據(jù)block和alignsize的商直接找到相應(yīng)的FixedAllocator回收。
優(yōu)點：差異化各種長度的對象申請，增強了易用性。
缺點：增加掃描的時間復(fù)雜度，當(dāng)前版本的loki浪費內(nèi)存。這也是進(jìn)一步封裝，屏蔽定長申請的細(xì)節(jié)，帶來的負(fù)面效應(yīng)。
*/
class SmallObject
{
//重載new，delete,設(shè)計為模板函數(shù)等
};
/**//*
暴露給外部使用的一層。引入模版，當(dāng)前版本 SmallObject有6個模版參數(shù)，第一個是線程策略，緊接著的三個正好是SmallObjAllocator層面的
三個構(gòu)造參數(shù)，下面的一個生存期策略，最后的是鎖方式。
這里說下SmallObjAllocator層面的三個默認(rèn)參數(shù)值，分別是4096，256，4。意味著SmallObjAllocator層面有數(shù)組（256+4-1)/4=64個，
數(shù)組存儲的FixedAllocator中的chunksize一般都是4096（當(dāng)4096<= blocksize*255時候）字節(jié)（第一個chunk的申請推遲到首次使用的時候），
各FixedAllocator中的chunk的 blocksize依次是4、8256，大于256字節(jié)的內(nèi)存申請交給系統(tǒng)的malooc/new管理，
數(shù)組中FixedAllocator 中單個chunk中的blocknum依次是4096/4=824>255取255、2554096/256=16。如果這不能滿足需求，
請調(diào)用的時候顯式賦值。
當(dāng)前l(fā)oki提供了三種線程策略：
SingleThreaded  單線程 
ObjectLevelLockable  對象級別，一個對象一個鎖 
ClassLevelLockable  類級別，一個類一個鎖，該類的所有對象共用該鎖 
目前只提供了一種鎖機制：Mutex
它的基類SmallObjectBase復(fù)寫了new/delete操作子，因此直接繼承SmallObject就可以象普通的類一樣new/delete，并且從內(nèi)存池分配內(nèi)存。
SmalObject中block申請和釋放都從一個全局的SmallObjAllocator單例進(jìn)行。
*/

(2)boost::pool系列。boost 的內(nèi)存池最低層是simple_segregated_storage，類似于Loki中的chunk，在其中申請釋放block（boost中把 block稱為chunk，暈死，這里還是稱其為block）采用了和loki的chunk中同樣的算法，不同的是 simple_segregated_storage使用void*保存block的塊序號，loki中使用char，因此boost中的 simple_segregated_storage沒有255的上限限制，自然也就不需要再其上再封裝一層類似與FixedAllocator的層面。另boost沒有屏蔽塊的大小，直接提供定長的接口給用戶，省掉了SmallObjAllocator層面。因此boost的內(nèi)存池申請釋放block的時間復(fù)雜度都是O(1)（object_pool和pool_allocator除外），另避免的小內(nèi)存的浪費，同時boost不能象loki那樣在將 block歸還給內(nèi)存池的時候根據(jù)chunk的空閑數(shù)量釋放內(nèi)存歸還給系統(tǒng)，只能顯式調(diào)用釋放內(nèi)存函數(shù)或者等內(nèi)存池銷毀的時候，基本上和內(nèi)存池生命周期內(nèi)永不釋放沒什么區(qū)別。
    boost的最低層是simple_segregated_storage,主要算法和loki中的chunk一樣，不多說了。這里說下影響上層接口的兩類實現(xiàn)：add_block/malloc/free、add_ordered_block/malloc/ordered_free，兩種低層實現(xiàn)造成 boost上層設(shè)計的成功與失敗,前者效率高，和loki一樣直接增加釋放,時間復(fù)雜度O(1)，后者掃描排序，時間復(fù)雜度O(n)。
    boost提供了四種內(nèi)存池模型供使用：pool、object_pool、singleton_pool、pool_allocator/fast_pool_allocator。
1）pool
基本的定長內(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ù)只有一個分配子類型，boost提供了兩種 default_user_allocator_new_delete/default_user_allocator_malloc_free，指明申請釋放內(nèi)存的時候使用new/delete，還是malloc/free，默認(rèn)是default_user_allocator_new_delete。構(gòu)造函數(shù)有2個參數(shù)：nrequested_size,nnext_size。nrequested_size是block的大小（因為void*保存序號，因此boost內(nèi)置了block的最小值，nrequested_size過小則取內(nèi)置值），nnext_size是 simple_segregated_storage中內(nèi)存不足的時候，申請的block數(shù)量，默認(rèn)是32。最全面的實例化pool類似這樣： boost::pool<boost::default_user_allocator_malloc_free> student_pool(sizeof(CStudent),255);
    pool提供的函數(shù)主要有：

malloc/free	基于add_block/malloc/free實現(xiàn)，高效
ordered_malloc/ordered_free	基于add_ordered_block/malloc/ordered_free實現(xiàn)，在pool中無任何意義，切勿使用。
release_memory/purge_memory	前者釋放池中未使用內(nèi)存，后者釋放池中所有內(nèi)存。另池析構(gòu)也會釋放內(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，有兩個模版參數(shù)，第一個就是對象類型，第二個是分配子類型，默認(rèn)同pool是 default_user_allocator_new_delete。構(gòu)造函數(shù)參數(shù)只有nnext_size，意義以及默認(rèn)值同pool。最全面的實例化object_pool類似這樣：boost::pool<A,boost:: default_user_allocator_malloc_free> obj_pool(255);
object_pool提供的函數(shù)主要有（繼承至父類的略）：

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

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

destroy函數(shù)并沒有提高復(fù)雜度，因為內(nèi)部鏈表始終處于有序狀態(tài)（由于使用order_malloc,order_free)，所以不論是逐個釋放，還是成批釋放，它的復(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為單例類，是對pool的加鎖封裝，適用于多線程環(huán)境，其中所有函數(shù)都是靜態(tài)類型。它的模版參數(shù)有5個，tag：標(biāo)記而已，無意義；RequestedSize：block的長度；UserAllocator：分配子，默認(rèn)還是 default_user_allocator_new_delete；Mutex：鎖機制，默認(rèn)值最終依賴于系統(tǒng)環(huán)境，linux下是 pthread_mutex，它是對pthread_mutex_t的封裝；NextSize：內(nèi)存不足的時候，申請的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實現(xiàn)，實現(xiàn)了stl::allocator要求的接口規(guī)范。兩者的使用相同，區(qū)別在于pool_allocator的實現(xiàn)調(diào)用ordered_malloc/ordered_free， fast_pool_allocator的實現(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ù)有四個：類型，分配子，鎖類型，內(nèi)存不足時的申請的block數(shù)量，后三者都有默認(rèn)值，不再說了。它使用的singleton_pool的tag是boost::fast_pool_allocator_tag。