内存地址

Linux内存模型

虚拟内存地址与物理内存地址:用户编程使用的地址称为虚地址或逻辑地址，其对应的存储空间称为虚存空间或逻辑地址空间；而计算机物理内存的访问地址则称为实地址或物理地址，其对应的存储空间称为物理存储空间或主存空间。对于虚拟内存来说，每个进程有各自独立的2^N(N为机器位数)字节的虚拟地址空间。虚拟地址空间的作用主要是简化程序的编写及方便操作系统对进程间内存的隔离管理，虚拟内存到物理内存的映射由操作系统按页动态维护。虚拟内存一方面保护了操作系统的安全，另一方面允许应用程序使用比实际物理内存更大的地址空间。

Linux 64位系统的内存空间：理论上，64bit内存地址可用空间为0x0000000000000000 ~ 0xFFFFFFFFFFFFFFFF，而Linux64位操作系统仅使用低47位，高17位做扩展（只能是全0或全1）。所以，实际用到的地址为空间为0x0000000000000000 ~ 0x00007FFFFFFFFFFF和0xFFFF800000000000 ~ 0xFFFFFFFFFFFFFFFF，其中前面为用户空间（User Space），后者为内核空间（Kernel Space）。进程虚拟内存空间：虚拟内存地址由MMU（Memory Management Unit）动态转化为物理内存地址对真实数据进行操作。这个空间被划分以下几部分1）code：存放程序的二进制代码段 。2）.data：存放常量字符串，初始化的全局变量和静态变量，程序结束后由系统释放。3）.bss：未初始化的全局变量和静态变量，程序结束后由系统释放。4）heap：一般由程序员分配释放，若程序员不释放，程序结束时可能由 OS 回收。5）mapping area：这里是与mmap系统调用相关的区域。大多数实际的malloc实现会考虑通过mmap分配较大块的内存区域。6）.stack ：由编译器自动分配释放，存放函数的参数值，局部变量的值等。

堆：堆是由三段连续内存组成，分别为开始部分，最大限制，堆顶。堆顶指针指向映射区域的边界，从堆起始地址到break之间的地址空间为映射好的，可以供进程访问；而从break往上，是未映射的地址空间，如果访问这段空间则程序会报错。

brk与sbrk

int brk(void *addr);
void *sbrk(intptr_t increment);

	brk将break指针直接设置为某个地址，而sbrk将break从当前位置移动increment所指定的增量。brk在执行成功时返回0，否则返回-1并设置errno为ENOMEM；sbrk成功时返回break移动之前所指向的地址，否则返回(void *)-1。如果将increment设置为0，则可以获得当前break的地址。由于Linux是按页进行内存映射的，所以如果break被设置为没有按页大小对齐，则系统实际上会在最后映射一个完整的页，从而实际已映射的内存空间比break指向的地方要大一些。

malloc

分配前初始化

#include <unistd.h> /*sbrk 函数所在的头文件 */void malloc_init()
{last_valid_address = sbrk(0); /* 用 sbrk 函数在操作系统中取得最后一个有效地址（当前break的位置） */managed_memory_start = last_valid_address; /* 将 最 后 一 个有效地址作为管理内存的起始地址 */has_initialized = 1; /* 初始化成功标记 */
}

内存块的结构

内存块的数据结构：所要申请的内存是由多个内存块构成的链表。内存块的大致结构：每个块由meta区和数据区组成，meta区：记录数据块的元信息（数据区大小、空闲标志位、指针等等），数据区是真实分配的内存区域，并且数据区的第一个字节地址即为malloc返回的地址。

typedef struct s_block *t_block;
struct s_block {size_t size; /* 数据区大小 */t_block next; /* 指向下个块的指针 */int free; /* 是否是空闲块 */int padding; /* 填充4字节，保证meta块长度为8的倍数 */char data[1] /* meta区的末尾，这是一个虚拟字段，表示数据块的第一个字节，长度不应计入meta */
};

	关于数据区：1）为了完全地管理内存，需要能够追踪要分配和回收哪些内存。在对内存块进行了 free调用之后，需要做的是诸如将它们标记为未被使用的等事情，并且，在调用 malloc 时，要能够定位未被使用的内存块。因此， malloc 返回的每块内存的起始处首先要有这个结构：		

struct mem_control_block
{	int is_available;//是否空闲int size; //内存块大小
};

获取内存块

内存对齐

	考虑64位情况，指针必须是8的倍数（64位 = 8字节），因为元数据块已经对齐，唯一需要的是对齐数据块的大小。

对齐公式：
(X − 1)/8 × 8 + 8
即：
(((((X)-1)>>3)<<3)+8)

从空闲block获取

block链中的查找算法：1）First fit：从头开始，使用第一个数据区大小大于要求size的块所谓此次分配的块2）Best fit：从头开始，遍历所有块，使用数据区大小大于size且差值最小的块作为此次分配的块。两种方法各有千秋，best fit具有较高的内存使用率（payload较高），而first fit具有更好的运行效率。find_block从frist_block开始，查找第一个符合要求的block并返回block起始地址，如果找不到这返回NULL。这里在遍历时会更新一个叫last的指针，这个指针始终指向当前遍历的block。这是为了如果找不到合适的block而开辟新block使用的。

frist_block查找合适的空闲块：t_block find_block(t_block *last, size_t size) {t_block b = first_block;while(b && !(b->free && b->size >= size)) {*last = b;b = b->next;}return b;
}

	First fit有一个比较致命的缺点，就是可能会让很小的size占据很大的一块block。为了提高payload，会在列表中插入一个新的块,将其分裂为一个新的block：

分裂block代码：void split_block(t_block b, size_t s) {t_block new;new = b->data + s; //由于字段数据是类型char[]，所以总和是按字节精度完成的。new->size = b->size - s - BLOCK_SIZE ;new->next = b->next;new->free = 1;b->size = s;b->next = new;}

	如果现有block都不能满足size的要求，则需要在链表最后开辟一个新的block。

拓展新block

	当开辟的空间小于128K时，调用brk()函数，malloc的底层实现是系统调用函数 brk()，其主要移动break位置。当开辟的空间大于128K时，malloc使用mmap()系统调用函数在虚拟地址空间中（堆和栈中间，称为“文件映射区域”的地方）找一块空间来开辟。。这两种方式分配的都是虚拟内存，没有分配物理内存。在第一次访问已分配的虚拟地址空间的时候，发生缺页中断，操作系统负责分配物理内存，然后建立虚拟内存和物理内存之间的映射

使用brk拓展block代码：#define BLOCK_SIZE 24 //sizeof(struct s_block)t_block extend_heap(t_block last, size_t s) {t_block b;b = sbrk(0);if(sbrk(BLOCK_SIZE + s) == (void *)-1)return NULL;b->size = s;b->next = NULL;if(last)last->next = b;b->free = 0;return b;
}

free

碎片处理

碎片：malloc一块空间时，为了更好的利用了内存，如果找到了较大的一块空间后会将这块空间分割以供给后续空间使用。于是堆空间有可能存在大量的内存碎片。free函数处理碎片：在free内存时候，通过扫描这块内存的左右内存块将与其相邻的内存碎片和当前free掉的内存块整合在一起，放入空闲列表中。

整合碎片：typedef struct s_block *t_block;struct s_block {size_t size; //数据区域大小t_block next; //指向下一区域的指针t_block prev; // 指向下一区的指针int free; //是否为空闲区域（因为内存对齐所以用int）int padding;  // 填充4字节，保证meta块长度为8的倍数 */char data[1]  // 这是一个虚拟字段，表示数据块的第一个字节，不计入meta的长度
};t_block fusion(t_block b){if (b->next && b->next ->free ){b->size += BLOCK_SIZE + b->next ->size; //更新大小b->next = b->next ->next;    //更改指向if(b->next)b->next->prev = b; }return (b);
}

合法性检查

free前需要对指针的合法性进行检验，以保证这个地址是malloc的地址，有两种方法：
1）在结构体中添加几个magic number。在free之前通过相对偏移量比较是否与设定的magic number相同。
2）在结构体中添加一个指向数据区第一个字节的指针ptr。在free之前通过比较参数指针是否等于其指向结构体的ptr成员。

指针方式合法性检查：#define BLOCK_SIZE 40 //sizeof(struct s_block)typedef struct s_block *t_block;struct s_block {...t_block prev; // 指向下一区的指针void* ptr; //指向data。...
};t_block get_block(void *p) {char *tmp; tmp = p;return (p = tmp -= BLOCK_SIZE);
}int valid_addr(void *p) {if(first_block) {if(p > first_block && p < sbrk(0)) {return p == (get_block(p))->ptr;}}return 0;
}

释放内存空间

void free(void *p) {t_block b;//合法检查if(valid_addr(p)) {b = get_block(p);b->free = 1;//整合前一个if(b->prev && b->prev->free)b = fusion(b->prev);//整合后一个if(b->next)fusion(b);else {//释放堆顶if(b->prev)b->prev->prev = NULL;else //无内存块first_block = NULL;brk(b);}}
}

STL内存管理

gnu中的八种内存分配器

gnu中为管理内存提供了八种内存分配器：

__gnu_cxx::new_allocator

	简单地封装了new和delete操作符，通常就是std::allocator对象的构造分为四步：1）申请内存空间，对应函数是allocator::allocate()2）执行构造函数，对应函数是allocator::construct()3）执行析构函数，对应函数是allocator::destroy()4）释放内存空间，对应函数是allocator::deallocate()使用::operator new和::operator delete来申请和释放内存空间（::operator new和::operator delete实际分配或释放内存调用的malloc和free，加上了异常处理等操作），使用placement new来执行构造，显示调用析构函数来执行析构并提供了多个版本的析构函数以优化

std::allocator代码示意：#include <new>// for new
#include <cstddef> //  size_t
#include <climits> // for unit_max
#include <iostream> // for cerr
using namespace std;namespace SLD {
template <class T>
class allocator
{
public:typedef T		value_type;typedef T*		pointer;typedef const T*	const_pointer;typedef T&		reference;typedef const T&	const_reference;typedef size_t		size_type;typedef ptrdiff_t	difference_type;template <class U>struct rebind{typedef allocator<U> other;};//申请内存pointer allocate(size_type n, const void* hint = 0){T* tmp = (T*)(::operator new((size_t)(n * sizeof(T))));if (!tmp)cerr << "out of memory"<<endl;return tmp;}//释放内存void deallocate(pointer p){::operator delete(p);}//构造void construct(pointer p, const T& value){new(p) T1(value);}//析构函数version1void destroy(pointer p){p->~T();}//析构函数version2，接受两个迭代器。此函式设法找出元素的数值型别，//进而利用 __type_traits<> 求取最适当措施。template <class ForwardIterator>inline void destroy(ForwardIterator first, ForwardIterator last) {__destroy(first, last, value_type(first));}// 判断元素的数值型别（value type）是否有trivial destructortemplate <class ForwardIterator, class T>inline void __destroy(ForwardIterator first, ForwardIterator last, T*){typedef typename __type_traits<T>::has_trivial_destructor trivial_destructor;__destroy_aux(first, last, trivial_destructor());}// 如果元素的数值型别（value type）有non-trivial destructor…template <class ForwardIterator>inline void__destroy_aux(ForwardIterator first, ForwardIterator last, __false_type) {for ( ; first < last; ++first)destroy(&*first);}// 如果元素的数值型别（value type）有 trivial destructor…template <class ForwardIterator>inline void __destroy_aux(ForwardIterator, ForwardIterator, __true_type) {}//析构函数version3，针对迭代器为char*和wchar_t*的特化版inline void destroy(char*, char*) {}inline void destroy(wchar_t*, wchar_t*) {}//取地址pointer address(reference x){return (pointer)&x;}const_pointer const_address(const_reference x){return (const_pointer)&x;}size_type max_size() const {return size_type(UINT_MAX/sizeof(T));}
};
}

__gnu_cxx::__pool_alloc

	基于内存池，通常就是std::alloc，但std::alloc在更高版本的gnu cxx中已移除。SGI STL中pool alloc分配器以128个字节来区分小块和大块内存，将空间配置器分为两级结构，一级空间配置器处理大块内存，二级空间配置器处理小块内存。一级空间配置器：__malloc_alloc_template一级空间配置器的原理就是直接将malloc和free进行了封装，当调用malloc和realloc申请不到内存空间的时候，会改调用oom_malloc()和oom_realloc()，这两个函数会反复调用用户传递过来的out of memory handler处理函数，直到能用malloc或者realloc申请到内存为止。如果用户没有传递__malloc_alloc_oom_handler，__malloc_alloc_template会抛出__THROW_BAD_ALLOC异常。

一级空间配置器代码示意：static void* allocate(size_t __n)
{void* __result = malloc(__n);if (0 == __result)__result = _S_oom_malloc(__n);return __result;
}static void deallocate(void* __p, size_t /* __n */)
{free(__p);
}static void* reallocate(void* __p, size_t /* old_sz */, size_t __new_sz)
{void* __result = realloc(__p, __new_sz);if (0 == __result) __result = _S_oom_realloc(__p, __new_sz);return __result;
}

二级空间配置器：__default_alloc_template二级空间配置器专门负责处理小于128字节的小块内存。SGI STL采用了内存池的技术来提高申请空间的速度以及减少额外空间的浪费，采用哈希桶的方式来提高用户获取空间的速度。为何是128Kb：malloc函数以128Kb为区分，对于大于128Kb的空间，由映射取分配，可直接释放；对于小于128Kb的空间，靠着移动堆顶指针来分配，并用链表管理，不能随时释放，会出现内存碎片。一级分配器是在申请的空间大于128Kb的情况下对malloc的封装，所获取的内存属于映射区，能随时申请和释放，不会产生碎片；二级分配器申请的空间小于128Kb，属于堆区，使用malloc容易产生碎片，因而设计内存池自己管理。

	二级分配器中，存在16条空闲链表，每条链表中的空闲块的大小都是固定的：第一条链表的空闲块大小是8bytes, 往后依次是16, 24, 32, 40, 48, 56, 64, 72, 80, 88, 96, 104, 112, 120, 128bytes。16条空闲链表的起始地址组成大小为16的数组。另外存在一个内存池，内存池的维护需要三根指针：s_start_free，s_end_free，s_heap_size。它们分别指向整个内存池的起始地址，结束地址和可用空间大小。

申请空间：1）向上对齐字节数后，所需字节数大于128由一级空间配置器来处理，不大于由二级空间配置器处理。2）对于二级配置器，先找到对应的桶，检查桶下是否存在内存块，存在直接将第一个内存块返回给用户3）不存在则要先向桶中添加内存块，然后将第一个内存块返回给用户

填充内存块：1）一次性向内存池索取20个内存块（chunk），真实返回的内存块不小于12）只有一块就直接返回给用户，否则将第一块返回给用户，剩余的挂在对应的桶中

向内存池索要空间：1）计算20个内存块总大小和内存池剩余空间大小，能提供20块切割空间则返回2）不能提供20块，能否提供至少一块，能提供切割空间则返回3）一块也不能提供，说明内存池空间不足，此时将内存池剩余空间挂到对应桶下并补充内存池4）通过系统堆补充内存池，补充成功则重新回到第一步5）补充失败，从哈希桶中找更大的内存块补充，补充成功重新回到第一步6）哈希桶也补充失败，向一级空间配置器申请补充

二级空间配置器代码示意：template <bool threads, int inst>
class __default_alloc_template {private:// Really we should use static const int x = N// instead of enum { x = N }, but few compilers accept the former.enum {_ALIGN = 8};//小块区域的上界enum {_MAX_BYTES = 128};//小块区域的下降enum {_NFREELISTS = 16}; // _MAX_BYTES/_ALIGN，有多少个区域/*SGI 为了方便内存管理， 把128B 分成16*8 的块*///将Byte调到8的倍数static size_t_S_round_up(size_t __bytes) { return (((__bytes) + (size_t) _ALIGN-1) & ~((size_t) _ALIGN - 1)); }//管理内存的链表union _Obj {union _Obj* _M_free_list_link;char _M_client_data[1];    /* The client sees this.        */};//声明了16个 free_list, 注意 _S_free_list是成员变量static _Obj* __STL_VOLATILE _S_free_list[_NFREELISTS];//同了第几个free_list, 即_S_free_list[n],当然这里是更具区域大小来计算的static  size_t _S_freelist_index(size_t __bytes) {return (((__bytes) + (size_t)_ALIGN-1)/(size_t)_ALIGN - 1);}// Returns an object of size __n, and optionally adds to size __n free list.static void* _S_refill(size_t __n);// Allocates a chunk for nobjs of size size.  nobjs may be reduced// if it is inconvenient to allocate the requested number.static char* _S_chunk_alloc(size_t __size, int& __nobjs);// Chunk allocation state.static char* _S_start_free;//内存池的起始位置static char* _S_end_free;//内存池的结束位置static size_t _S_heap_size;//堆的大小public://分配内存/* __n must be > 0      */static void* allocate(size_t __n);//释放内存/* __p may not be 0 */static void deallocate(void* __p, size_t __n);//重新分配内存static void* reallocate(void* __p, size_t __old_sz, size_t __new_sz);}//下面是一些 成员函数的初始值的设定
template <bool __threads, int __inst>
char* __default_alloc_template<__threads, __inst>::_S_start_free = 0;template <bool __threads, int __inst>
char* __default_alloc_template<__threads, __inst>::_S_end_free = 0;template <bool __threads, int __inst>
size_t __default_alloc_template<__threads, __inst>::_S_heap_size = 0;template <bool __threads, int __inst>
typename __default_alloc_template<__threads, __inst>::_Obj* __STL_VOLATILE
__default_alloc_template<__threads, __inst> ::_S_free_list[] = 
{0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, };

static void* allocate(size_t __n)
{void* __ret = 0;if (__n > (size_t) _MAX_BYTES) {//如果大于128B， 直接调用一级配置器__ret = malloc_alloc::allocate(__n);}else {//找出 16个free-list 中的一个_Obj* __STL_VOLATILE* __my_free_list= _S_free_list + _S_freelist_index(__n);_Obj* __RESTRICT __result = *__my_free_list;if (__result == 0)//如果满了,则我refill整一个链表__ret = _S_refill(_S_round_up(__n));else {*__my_free_list = __result -> _M_free_list_link;__ret = __result;}}return __ret;
};static void deallocate(void* __p, size_t __n)
{if (__n > (size_t) _MAX_BYTES)//如果大于128,直接释放malloc_alloc::deallocate(__p, __n);else {//找到对应的链表_Obj* __STL_VOLATILE*  __my_free_list= _S_free_list + _S_freelist_index(__n);_Obj* __q = (_Obj*)__p;//回收，该链表__q -> _M_free_list_link = *__my_free_list;*__my_free_list = __q;// lock is released here}
}template <bool __threads, int __inst>
char*
__default_alloc_template<__threads, __inst>::_S_chunk_alloc(size_t __size, int& __nobjs)
{char* __result;size_t __total_bytes = __size * __nobjs;//申请的总内存空间size_t __bytes_left = _S_end_free - _S_start_free;//内存池剩余的内存空间if (__bytes_left >= __total_bytes) {//如果你能满足我__result = _S_start_free;_S_start_free += __total_bytes;return(__result);} else if (__bytes_left >= __size) {//如果能满足我一块或一块以上，参考__Obj这个联合体（free_list）__nobjs = (int)(__bytes_left/__size);__total_bytes = __size * __nobjs;__result = _S_start_free;_S_start_free += __total_bytes;return(__result);} else {//如果连一块都给不出size_t __bytes_to_get = 2 * __total_bytes + _S_round_up(_S_heap_size >> 4);// Try to make use of the left-over piece.if (__bytes_left > 0) {_Obj* __STL_VOLATILE* __my_free_list =_S_free_list + _S_freelist_index(__bytes_left);((_Obj*)_S_start_free) -> _M_free_list_link = *__my_free_list;*__my_free_list = (_Obj*)_S_start_free;}.//从堆空间重新分配内存_S_start_free = (char*)malloc(__bytes_to_get);if (0 == _S_start_free) {//连堆都没有内存了size_t __i;_Obj* __STL_VOLATILE* __my_free_list;_Obj* __p;for (__i = __size;__i <= (size_t) _MAX_BYTES;__i += (size_t) _ALIGN) {__my_free_list = _S_free_list + _S_freelist_index(__i);__p = *__my_free_list;if (0 != __p) {*__my_free_list = __p -> _M_free_list_link;_S_start_free = (char*)__p;_S_end_free = _S_start_free + __i;return(_S_chunk_alloc(__size, __nobjs));}}_S_end_free = 0;	// In case of exception.//调用一级配置器，主要是为了调用_S_oom_malloc压榨出内存来_S_start_free = (char*)malloc_alloc::allocate(__bytes_to_get);// This should either throw an// exception or remedy the situation.  Thus we assume it// succeeded.}//更改一下内存池_S_heap_size += __bytes_to_get;_S_end_free = _S_start_free + __bytes_to_get;return(_S_chunk_alloc(__size, __nobjs));}
}

__gnu_cxx::__mt_alloc

	对多线程环境进行了优化

支持多线程的内存分配器__gnu_cxx::__mt_alloc

__gnu_cxx::malloc_allocator

	简单地封装了malloc和free函数

__gnu_cxx::debug_allocator

__gnu_cxx::throw_allocator

__gnu_cxx::array_allocator

__gnu_cxx::bitmap_allocator

gcc-4.6.3/ibstdc++

SGI内存管理组件

分配器的使用

	对于STL容器，包含相应头文件后，只需将分配器作为模板参数传入即可，如vector<int, __gnu_cxx::__pool_alloc<int>> vec。

uninitialized组件

template <class _InputIter, class _ForwardIter>
inline _ForwardIter
uninitialized_copy(_InputIter __first, _InputIter __last,_ForwardIter __result)
{return __uninitialized_copy(__first, __last, __result,__VALUE_TYPE(__result));
}

	uninitialized_copy()会将迭代器_first和_last之间的对象拷贝到迭代器_result开始的地方。它调用的__uninitialized_copy(__first, __last, __result,__VALUE_TYPE(__result))，会判断迭代器_result所指的对象是否是POD类型，如果是POD类型，则调用算法库的copy实现；否则遍历迭代器_first~_last之间的元素，在_result起始地址处一一构造新的元素。uninitialized_fill()和uninitialized_fill_n()同样如此。

template <class _ForwardIter, class _Tp>
inline void uninitialized_fill(_ForwardIter __first,_ForwardIter __last, const _Tp& __x)
{__uninitialized_fill(__first, __last, __x, __VALUE_TYPE(__first));
}template <class _ForwardIter, class _Size, class _Tp>
inline _ForwardIter 
uninitialized_fill_n(_ForwardIter __first, _Size __n, const _Tp& __x)
{return __uninitialized_fill_n(__first, __n, __x, __VALUE_TYPE(__first));
}

loki库的小对象内存管理

	Loki Allocator中有三个类，对比pool allocator，它的优点就在于它会把内存还给系统：1）Chunk2）FixedAllocator3）SmallObjAllocator

Chunk

Chunk是一段由许多个固定大小内存块组成的连续的空间，内部调用malloc函数分配空间。在Chunk初始化时，每个内存块的大小和Chunk中的内存块个数都由传入参数确定。，内存块个数不超过256个。Chunk中内存块的管理方式为数组模拟的链表。

	Chunk管理内存块需要用到三个变量		

// 指向内存块
unsigned char * pData_;
// 目前可用区块的第一块的索引
unsigned char firstAvailableBlock_;
// 有多少块可用
unsigned char blocksAvailable_;

 		Chunk初始化：分配内存块并用数组的方式模拟链表，将内存块串接（将每个小区块的第一个字节设置为索引排好号）

bool Chunk::Init( ::std::size_t blockSize, unsigned char blocks ) {const ::std::size_t allocSize = blockSize * blocks;pData_ = static_cast< unsigned char * >( ::operator new ( allocSize ) );Reset( blockSize, blocks );return true;
}void Chunk::Reset(::std::size_t blockSize, unsigned char blocks) {firstAvailableBlock_ = 0;blocksAvailable_ = blocks;// 这把每个区块的前一个字节 来记录索引unsigned char i = 0;for ( unsigned char * p = pData_; i != blocks; p += blockSize ) {*p = ++i;}
}

	Chunk分配：1）从 当前可用区块的第一块索引（firstAvailableBlock_所指）中取得当前可用区块并返回2）被返回的可用区块中的索引被设置到当前可用区块索引去（这样下一次就会使用到它）3）可用区块数目（blocksAvailable_所指）减1

void* Chunk::Allocate(::std::size_t blockSize) {if ( 0 == blocksAvailable_ ) {return nullptr;}// 1. 取得目前可用的第一块unsigned char * pResult = pData_ + (firstAvailableBlock_ * blockSize);firstAvailableBlock_ = *pResult;// 2. 当前可用区块 - 1--blocksAvailable_;// 3. 将目前可用第一块返回回去return pResult;
}

	Chunk回收：原则：回收回来的区块，下次分配优先分配1）计算回收回来的区块的索引idx2）当前可用区块的索引号（firstAvailableBlock_ 所指）设置为idx3）之前可用区块的索引号（firstAvailableBlock_ 的旧值）设置到回收回来的区块包含的索引中去4）当前可用区块（blocksAvailable_）加1

void Chunk::Deallocate(void* p, ::std::size_t blockSize) {unsigned char* toRelease = static_cast<unsigned char*>(p);// 找这个指针在区块中的索引unsigned char index = static_cast< unsigned char >(( toRelease - pData_ ) / blockSize);// 回收回来以后下次优先用它// 1. 回收的区块里的索引设置为当前可用区块的索引*toRelease = firstAvailableBlock_;// 2. 当前的第一块可用索引修改为回收回来的区块应该放置的位置firstAvailableBlock_ = index;// 3. 可用数 + 1++blocksAvailable_;
}

	Chunk的释放：Chunk等到所有区块被回收时，内存将被释放，这件事由Chunk的管理者FixedAllocator负责

void Chunk::Release() {::operator delete ( pData_ );
}

FixedAllocator

	FixedAllocator的成员：FixedAllocator拥有一个Chunk的数组，并使用了三个指针来管理它

// vector<Chunk>
typedef ::std::vector< Chunk > Chunks;
Chunks chunks_;// 指向 vector<Chunk> 其中某两个 Chunk
// allocChunk_ 指向上次分配区块的 Chunk
Chunk * allocChunk_;
// deallocChunk_ 指向上次回收区块的 Chunk
Chunk * deallocChunk_;// 指向唯一一个空Chunk 如果没有则为 nullptr
Chunk * emptyChunk_;

	FixedAllocator分配：1）看allocChunk_(指向上次分配过区块的Chunk) 是否有效，有效则直接分配2）否则看emptyChunk_(指向一个空Chunk) 是否有效，有效则直接分配3）否则依次遍历vector找到其中一个能分配区块的Chunk4）找不到则创建一个新的Chunk并将其push_back到vector中

void * FixedAllocator::Allocate( void ) {// 上次分配出去过区块的chunk 如果为空或者是该chunk可用区块为0// 则将空chunk赋值给它// 如果没有空chunk  if ( ( nullptr == allocChunk_ ) || 0 == allocChunk_->blocksAvailable_ ) {if ( nullptr != emptyChunk_ ) {allocChunk_ = emptyChunk_;emptyChunk_ = nullptr;} else {// 都没有则从头找：遍历一遍 vectorChunks::iterator i = chunks_.begin();for ( ; ; ++i ) {// 到达尾部还是没找着就创建一个临时对象并init这个chunk// 然后将其push到容器中if ( chunks_.end() == i ) {chunks_.push_back(Chunk());Chunk &newChunk = chunks_.back();newChunk.Init(blockSize_, numBlocks_);// 记录好，下次就从这里面去取区块allocChunk_ = &newChunk;// vector push_back的时候有可能发生成长// vector 成长是两倍申请内存然后将其拷贝过去// 如果不重新取迭代器地址的话有可能该迭代器失效deallocChunk_ = &chunks_.front();break;}// 如果找到一个chunk 的可用区块大于 0 则用它来分配if ( i->blocksAvailable_ > 0) {allocChunk_ = &*i;break;}}}// 如果上次分配区块的chunk是emptyChunk 则将 emptyChunk 置为空// 因为 emptyChunk 已经被用了} else if ( allocChunk_ == emptyChunk_) {emptyChunk_ = nullptr;}// 上次分配过区块的chunk 如果还能分配则直接分配返回回去void * place = allocChunk_->Allocate( blockSize_ );return place;
}

	FixedAllocator回收：1）寻找要回收的区块在哪个Chunk中：a. 先从上一次回收过区块的Chunk中查看b. 再从上一次分配过区块的Chunk中查看c. 如果都没有则用一种特殊的搜索方法：从上一次回收过区块的Chunk作为临界点，每次循环一次向上找、一次向下找，直到找到2）调用释放函数：如果发生了全回收，则看是否已经有一块全回收了，两块全回收时才释放其中一块，避免突然又要用到那块Chunk

bool FixedAllocator::Deallocate( void * p ) {Chunk * foundChunk = nullptr;const ::std::size_t chunkLength = numBlocks_ * blockSize_;// 先看看是否在之前回收过区块的 Chunk里面// 再看看是否在之前分配过区块的 Chunk里面if ( p >= deallocChunk_->pData_ && p < deallocChunk_->pData_ + chunkLength ) {foundChunk = deallocChunk_;} else if ( p >= allocChunk_->pData_ && p < allocChunk_->pData_ + chunkLength ) {foundChunk = allocChunk_;} else {// 实在找不到再去搜索foundChunk = VicinityFind( p );}if ( nullptr == foundChunk ) {return false;}deallocChunk_ = foundChunk;// 此时再真正的去deallocateDoDeallocate(p);return true;
}Chunk * FixedAllocator::VicinityFind( void * p ) const {if ( chunks_.empty() ) {return nullptr;}const ::std::size_t chunkLength = numBlocks_ * blockSize_;// lo指向上一次回收过区块的 Chunk// hi指向上一次回收过区块的 Chunk的下一个Chunk * lo = deallocChunk_;Chunk * hi = deallocChunk_ + 1;const Chunk * loBound = &chunks_.front();const Chunk * hiBound = &chunks_.back() + 1;if ( hi == hiBound ) {hi = nullptr;}for (;;) {// lo 往上走，hi 往下走，直到找到，或者，触碰到边界if (lo) {if ( p >= lo->pData_ && p < lo->pData_ + chunkLength ) {return lo;}if ( lo == loBound ) {lo = nullptr;if ( nullptr == hi ) {break;}} else { --lo;}}if (hi) {if ( p >= hi->pData_ && p < hi->pData_ + chunkLength ) {return hi;}if ( ++hi == hiBound ) {hi = nullptr;if ( nullptr == lo ) {break;}}}}return nullptr;
}// 总得来说就是 当有2个全回收的Chunk才释放掉一个
void FixedAllocator::DoDeallocate(void* p) {// 让 Chunk 回收掉这个区块deallocChunk_->Deallocate(p, blockSize_);// 如果这个Chunk 已经全回收了if ( deallocChunk_->blocksAvailable_ == numBlocks_ ) {if ( nullptr != emptyChunk_ ) {Chunk * lastChunk = &chunks_.back();if ( lastChunk == deallocChunk_ ) {deallocChunk_ = emptyChunk_;} else if ( lastChunk != emptyChunk_ ) {::std::swap( *emptyChunk_, *lastChunk );}// 最后释放掉内存lastChunk->Release();chunks_.pop_back();// 修正 allocChunk 指针 防止 被释放掉的是 allocChunkif ( ( allocChunk_ == lastChunk ) || allocChunk_->blocksAvailable_ == 0 ) {allocChunk_ = deallocChunk_;}}emptyChunk_ = deallocChunk_;}
}

SmallObjAllocator

	SmallObjAllocator维护一个固定长度的FixedAllocator数组，初始化的时候确定。维护着三个成员变量：

// vector<FixedAllocator> 其实是个数组 你可以理解成 vector
::Loki::Private::FixedAllocator * pool_;
// 支持分配的最大内存大小
const ::std::size_t maxSmallObjectSize_;
// 用于对齐操作
const std::size_t objectAlignSize_;//底层由多个([maxobjectSize/objectAlignSize]个)FixedAllocator 组成，每个FixedAllocator内存大小最大为pagesize，
//FixedAllocator 的一块Chunk由numBlock个blockSize组成，其中blocksize=(i+1)*alignSize, numBlock=pagesize/blockSize
//numBlock <= UCHAR_MAX,不同下标的FixedAllocator分配的block不一样，下标i的FixedAllocator 分配的block大小为(i+1)*alignSize
SmallObjAllocator::SmallObjAllocator( std::size_t pageSize,std::size_t maxObjectSize, std::size_t objectAlignSize ) :pool_( NULL ),maxSmallObjectSize_( maxObjectSize ),objectAlignSize_( objectAlignSize )
{assert( 0 != objectAlignSize );const std::size_t allocCount = GetOffset( maxObjectSize, objectAlignSize );//GetOffset向上取整pool_ = new FixedAllocator[ allocCount ];for ( std::size_t i = 0; i < allocCount; ++i )pool_[ i ].Initialize( ( i+1 ) * objectAlignSize, pageSize );
}

	SmallObjAllocator分配从vector找合适的FixedAllocator然后再用底层的FixedAllocator去找Chunk分配内存

void * SmallObjAllocator::Allocate( std::size_t numBytes, bool doThrow )
{//超过MaxObjSize，调用C语言的malloc或者C++的newif ( numBytes > GetMaxObjectSize() )return DefaultAllocator( numBytes, doThrow );if ( 0 == numBytes ) numBytes = 1;const std::size_t index = GetOffset( numBytes, GetAlignment() ) - 1; // 得到对应pool中的小标，对应的FiexAllocator固定分配的内存大小刚好满足numBytesconst std::size_t allocCount = GetOffset( GetMaxObjectSize(), GetAlignment() );(void) allocCount;assert( index < allocCount );FixedAllocator & allocator = pool_[ index ];assert( allocator.BlockSize() >= numBytes );assert( allocator.BlockSize() < numBytes + GetAlignment() );void * place = allocator.Allocate();//内存不足的情况出现，因为底层的chunk可能有空的chunk，所以调用TrimExcessMemory，尝试释放pool中每个FixedAllocator下chunks可能存在的emptyChunk,尽可能的把用户态内存先归还给操作系统，然后在分配给用户态if ( ( NULL == place ) && TrimExcessMemory() ) place = allocator.Allocate();if ( ( NULL == place ) && doThrow ) //如果还不行的话，没救了，看看要不要抛出异常，否则返回NULL{
#ifdef _MSC_VERthrow std::bad_alloc( "could not allocate small object" );
#else// GCC did not like a literal string passed to std::bad_alloc.// so just throw the default-constructed exception.throw std::bad_alloc();
#endif}return place;
}

	SmallObjAllocator回收找回收的内存对应的FixedAllocator然后调用下一层的FixedAllocator去进行真实回收操作

void SmallObjAllocator::Deallocate( void * p )
{if ( NULL == p ) return;assert( NULL != pool_ );FixedAllocator * pAllocator = NULL;const std::size_t allocCount = GetOffset( GetMaxObjectSize(), GetAlignment() );Chunk * chunk = NULL;for ( std::size_t ii = 0; ii < allocCount; ++ii ){chunk = pool_[ ii ].HasBlock( p ); //遍历pool,查看该块内存是否属于对应的FixedAllocatorif ( NULL != chunk ){pAllocator = &pool_[ ii ];break;}}if ( NULL == pAllocator ){DefaultDeallocator( p );return;}assert( NULL != chunk );const bool found = pAllocator->Deallocate( p, chunk );(void) found;assert( found );
}

基于策略的SmallObjAllocator

	loki库是基于策略的，也就是说通过实现一个模板框架，通过传入算法策略（模板参数）能够改变框架内部的过程，通过不同策略的组合能够实现不同功能

AllocatorSingleton

	继承自SmallObjAllocator，AllocatorSingleton，有多个模板参数，主要的策略算法有：用于管理自己单件模式的生命期策略，线程同步策略

template<template <class, class> class ThreadingModel = LOKI_DEFAULT_THREADING_NO_OBJ_LEVEL,std::size_t chunkSize = LOKI_DEFAULT_CHUNK_SIZE,std::size_t maxSmallObjectSize = LOKI_MAX_SMALL_OBJECT_SIZE,std::size_t objectAlignSize = LOKI_DEFAULT_OBJECT_ALIGNMENT,template <class> class LifetimePolicy = LOKI_DEFAULT_SMALLOBJ_LIFETIME,class MutexPolicy = LOKI_DEFAULT_MUTEX>class AllocatorSingleton : public SmallObjAllocator{...// 单例模式inline static AllocatorSingleton & Instance( void ){return MyAllocatorSingleton::Instance();}}

SmallObjectBase

	该类提供线程锁操作，重载了new与delete，属于应用层提供给用户使用，内存的申请与释放都是通过单例AllocatorSingleton.allocate来操作。实际使用的SmallObject仅仅是继承自SmallObjectBase

template
<template <class, class> class ThreadingModel,std::size_t chunkSize,std::size_t maxSmallObjectSize,std::size_t objectAlignSize,template <class> class LifetimePolicy,class MutexPolicy
>
class SmallObjectBase{//....typedef AllocatorSingleton< ThreadingModel, chunkSize,maxSmallObjectSize, objectAlignSize, LifetimePolicy > ObjAllocatorSingleton;typedef typename ObjAllocatorSingleton::MyAllocatorSingleton MyAllocatorSingleton;// 重载new操作符static void * operator new ( std::size_t size ) throw ( std::bad_alloc ){typename MyThreadingModel::Lock lock;(void)lock; // get rid of warningreturn MyAllocatorSingleton::Instance().Allocate( size, true );}//....
}