linux内存管理策略
   linux低层采用三层结构，实际使用中可以方便映射到两层或者三层结构，以适用不同的硬件结构。最下层的申请内存函数get_free_page。之上有三种类型的内存分配函数
（1）kmalloc类型。内核进程使用，基于slab技术，用于管理小于内存页的内存申请。思想出发点和应用层面的内存缓冲池同出一辙。但它针对内核结构，特别处理，应用场景固定，不考虑释放。不再深入探讨。
（2）vmalloc类型。内核进程使用。用于申请不连续内存。
（3）brk/mmap类型。用户进程使用。malloc/free实现的基础。
有关详细内容，推荐http://www.kerneltravel.net/journal/v/mem.htm。http://www.kerneltravel.net上有不少内核相关知识。
malloc系统的内存管理策略
   malloc系统有自己的内存池管理策略，malloc的时候，检测池中是否有足够内存，有则直接分配，无则从内存中调用brk/mmap函数分配，一般小于等于128k（可设置）的内存，使用brk函数，此时堆向上（有人有的硬件或系统向下）增长，大于128k的内存使用mmap函数申请，此时堆的位置任意，无固定增长方向。free的时候，检测标记是否是mmap申请，是则调用unmmap归还给操作系统，非则检测堆顶是否有大于128k的空间，有则通过brk归还给操作系统，无则标记未使用，仍在glibc的管理下。glibc为申请的内存存储多余的结构用于管理，因此即使是malloc(0)，也会申请出内存(一般16字节，依赖于malloc的实现方式），在应用程序层面，malloc(0)申请出的内存大小是0，因为malloc返回的时候在实际的内存地址上加了16个字节偏移，而c99标准则规定malloc（0）的返回行为未定义。除了内存块头域，malloc系统还有红黑树结构保存内存块信息，不同的实现又有不同的分配策略。频繁直接调用malloc，会增加内存碎片，增加和内核态交互的可能性，降低系统性能。linux下的glibc多为Doug Lea实现
应用层面的内存池管理
   1：不定长内存池。
   典型的实现有apr_pool。优点是不需要为不同的数据类型创建不同的内存池，缺点是造成分配出的内存不能回收到池中。这是由于这种方案以session为粒度，以业务处理的层次性为设计基础。
   apr_pool中的内存池并不是仅仅一个内存池，相反而是存在多个内存池，这些内存池之间形成层次结构。根据处理阶段的周期长短引出了子内存池的概念，与之对应的是父内存池以及根内存池的概念，它们的唯一区别就是存在的周期的不同而已。比如对于HTTP连接而言，包括两种内存池：连接内存池和请求内存池。由于一个连接可能包含多个请求，因此连接的生存周期总是比一个请求的周期长，为此连接处理中所需要的内存则从连接内存池中分配，而请求则从请求内存池中分配。而一个请求处理完毕后请求内存池被释放，一个连接处理后连接内存池被释放。根内存池在整个Apache运行期间都存在,因此apr_pool比较适合用于内存使用的生命期有明显层次的情况.
2:定长内存池
    典型的实现有BOOST,LOKI。特点是为不同类型的数据结构分别创建内存池，需要内存的时候从相应的内存池中申请内存，优点是可以在使用完毕立即把内存归还池中，可以更为细粒度的控制内存块。
 伪代码分析LOKI内存池:

//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块总数
};
/**//*
每个chunk管理一定数量的block,每个chunk中lock的申请和释放时间都是O（1）。
chunk：首次申请一块连续内存，pdata_指向该内存基址，依据block大小，划分成多个连续的block，每个block开头的第一个字节保存该block的顺序号，firstAvailableBlock_存储上次分配出的block序号。
分配block：返回pdata_+firstAvailableBlock_*blocksize,同时firstAvailableBlock_赋值为该快的序列号
收回block：block指针假设为pblock,该块序列号赋值为firstAvailableBlock_,firstAvailableBlock_赋值为(pblock-pdata_)/blocksize即可
*/

//得益于char的小所以可以分配很小的block出来,且在需要对齐的情况下不会出现问题
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单位固定大小的内存
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_);    //归还的内存必须大于分配起始内存
    unsigned char* toRelese = static_cast<unsigned char*>(p); //强制转换,静态，不检测运行态
    *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，时间复杂度o(N),同时更新活动chunk。
FixedAllocator中的回收block：简单想，给定block回收到FixedAllocator，自然要扫描vector，以确认 block属于哪个chunk，以便chunk回收。
    实际实现的时候，Loki针对应用场景进行了优化，一般使用都是批量使用，回收一般和申请顺序相同或者相反，
    因此FixedAllocator保存上次回收block的chunk指针，每次回收优先匹配这个chunk，匹配不上则以该chunk为中心，向两侧chunk顺序检测。
FixedAllocator带来的优点：上文提到的消除了block的上限限制。另一方面，可以以chunk为单位，把内存归还给操作系统。
    实际实现中防止刚释放的内存立即又被申请，是存在两个空闲chunk的时候才回收一个。这个特点，这里暂时归结为优点吧。
    实际使用中，回收多余内存个人认为是个缺点，意义并不是很大。
FixedAllocator带来的缺点：很明显，就是申请回收block的时间复杂度。
*/

/**///////////////////////////////////////////////////////////////////////////
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的预设大小,超过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都是定长。因此封装一层适用于任意长度的内存申请。
SmallObjAllocator保存了一个FixedAllocator的数组pool_，存储拥有不同block长度的FixedAllocator。
    当前SmallObjAllocator的构造函数有3个参数：chunksize，maxblocksize，alignsize。
    数组元素个数取 maxblocksize除以alignsize的向上取整。每个FixedAllocator中实际的blocksize是（下标＋1） *alignsize。
SmallObjAllocator中block申请：依据block和alignsize的商直接取到数组pool_下标，使用相应的FixedAllocator申请。
SmallObjAllocator中回收block：根据block和alignsize的商直接找到相应的FixedAllocator回收。
优点：差异化各种长度的对象申请，增强了易用性。
缺点：增加扫描的时间复杂度，当前版本的loki浪费内存。这也是进一步封装，屏蔽定长申请的细节，带来的负面效应。
*/
class SmallObject
{
//重载new，delete,设计为模板函数等
};
/**//*
暴露给外部使用的一层。引入模版，当前版本 SmallObject有6个模版参数，第一个是线程策略，紧接着的三个正好是SmallObjAllocator层面的
三个构造参数，下面的一个生存期策略，最后的是锁方式。
这里说下SmallObjAllocator层面的三个默认参数值，分别是4096，256，4。意味着SmallObjAllocator层面有数组（256+4-1)/4=64个，
数组存储的FixedAllocator中的chunksize一般都是4096（当4096<= blocksize*255时候）字节（第一个chunk的申请推迟到首次使用的时候），
各FixedAllocator中的chunk的 blocksize依次是4、8256，大于256字节的内存申请交给系统的malooc/new管理，
数组中FixedAllocator 中单个chunk中的blocknum依次是4096/4=824>255取255、2554096/256=16。如果这不能满足需求，
请调用的时候显式赋值。
当前loki提供了三种线程策略：
SingleThreaded  单线程 
ObjectLevelLockable  对象级别，一个对象一个锁 
ClassLevelLockable  类级别，一个类一个锁，该类的所有对象共用该锁 
目前只提供了一种锁机制：Mutex
它的基类SmallObjectBase复写了new/delete操作子，因此直接继承SmallObject就可以象普通的类一样new/delete，并且从内存池分配内存。
SmalObject中block申请和释放都从一个全局的SmallObjAllocator单例进行。
*/

(2)boost::pool系列。boost 的内存池最低层是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的内存池申请释放block的时间复杂度都是O(1)（object_pool和pool_allocator除外），另避免的小内存的浪费，同时boost不能象loki那样在将 block归还给内存池的时候根据chunk的空闲数量释放内存归还给系统，只能显式调用释放内存函数或者等内存池销毁的时候，基本上和内存池生命周期内永不释放没什么区别。
    boost的最低层是simple_segregated_storage,主要算法和loki中的chunk一样，不多说了。这里说下影响上层接口的两类实现：add_block/malloc/free、add_ordered_block/malloc/ordered_free，两种低层实现造成 boost上层设计的成功与失败,前者效率高，和loki一样直接增加释放,时间复杂度O(1)，后者扫描排序，时间复杂度O(n)。
    boost提供了四种内存池模型供使用：pool、object_pool、singleton_pool、pool_allocator/fast_pool_allocator。
1）pool
基本的定长内存池

#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的模版参数只有一个分配子类型，boost提供了两种 default_user_allocator_new_delete/default_user_allocator_malloc_free，指明申请释放内存的时候使用new/delete，还是malloc/free，默认是default_user_allocator_new_delete。构造函数有2个参数：nrequested_size,nnext_size。nrequested_size是block的大小（因为void*保存序号，因此boost内置了block的最小值，nrequested_size过小则取内置值），nnext_size是 simple_segregated_storage中内存不足的时候，申请的block数量，默认是32。最全面的实例化pool类似这样： boost::pool<boost::default_user_allocator_malloc_free> student_pool(sizeof(CStudent),255);
    pool提供的函数主要有：

malloc/free	基于add_block/malloc/free实现，高效
ordered_malloc/ordered_free	基于add_ordered_block/malloc/ordered_free实现，在pool中无任何意义，切勿使用。
release_memory/purge_memory	前者释放池中未使用内存，后者释放池中所有内存。另池析构也会释放内存

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，有两个模版参数，第一个就是对象类型，第二个是分配子类型，默认同pool是 default_user_allocator_new_delete。构造函数参数只有nnext_size，意义以及默认值同pool。最全面的实例化object_pool类似这样：boost::pool<A,boost:: default_user_allocator_malloc_free> obj_pool(255);
object_pool提供的函数主要有（继承至父类的略）：

malloc/free	复写pool的malloc/free，add_ordered_block/malloc/ordered_free实现
construct/destroy	基于本类的malloc/free实现，额外调用默认构造函数和默认析构函数。
~object_pool	若析构的时候有对象未被destroy，可以检测到，释放内存前对其执行destroy

   object_pool　主要着眼于“自动析构”，在没有gc的情况下，达到提高效率和自动管理内存的目的。而且它也特别适合于“多次申请，一次释放”的情况.所以它甚至是鼓励你忽略使用destroy（从它的例子就可以看出来）。

destroy函数并没有提高复杂度，因为内部链表始终处于有序状态（由于使用order_malloc,order_free)，所以不论是逐个释放，还是成批释放，它的复杂度都是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的加锁封装，适用于多线程环境，其中所有函数都是静态类型。它的模版参数有5个，tag：标记而已，无意义；RequestedSize：block的长度；UserAllocator：分配子，默认还是 default_user_allocator_new_delete；Mutex：锁机制，默认值最终依赖于系统环境，linux下是 pthread_mutex，它是对pthread_mutex_t的封装；NextSize：内存不足的时候，申请的block数量，默认是32。最全面的使用singleton_pool类似这样：typedef boost::singleton_pool<singleton_pool_tag,sizeof(CStudent),default_user_allocator_new_delete,details::pool::default_mutex,200>  global;
    它暴露的函数和pool相同。
4）pool_allocator/fast_pool_allocator
    stl::allocator的替换方案。两者都是基于singleton_pool实现，实现了stl::allocator要求的接口规范。两者的使用相同，区别在于pool_allocator的实现调用ordered_malloc/ordered_free， fast_pool_allocator的实现调用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的模版参数有四个：类型，分配子，锁类型，内存不足时的申请的block数量，后三者都有默认值，不再说了。它使用的singleton_pool的tag是boost::fast_pool_allocator_tag。