文章目录

• 内存分配
• 第二级配置器
• • 空闲链表的设计
  • 内存申请
  • 代码
  • 内存释放
  • 代码
• 注意

内存分配

当我们new一个对象时，实际做了两件事情：

1. 使用malloc申请了一块内存。
2. 执行构造函数。

在SGI中，这两步独立出了两个函数：allocate申请内存，construct调用构造函数。这两个函数分别在和中。
SGI STL的二级空间配置器，把<=128 字节的内存分配，由内存池进行管理，把>128 字节的内存，通过一级空间配置器malloc和free进行管理。

第一级就不用讲了。

第二级配置器

在STL的第二级配置器中多了一些机制，避免太多小区块造成的内存碎片，小额区块带来的不仅是内存碎片，配置时还有额外的负担。区块越小，额外负担所占比例就越大。
如果要分配的区块小于128bytes，则以 内存池管理（memory pool），每次配置一大块内存，并维护对应的16个空闲链表（free-list）。下次若有相同大小的内存需求，则直接从 free-list 中取。如果有小额区块被释放，则由配置器回收到 free-list 中。

空闲链表的设计

这里的16个空闲链表存放在数组里，分别为管理大小为8、16、24…120、128字节大小的数据块的链表。这里空闲链表节点的设计十分巧妙，这里用了一个联合体既可以表示下一个空闲数据块（存在于空闲链表中）的地址，也可以表示已经被用户使用的数据块（不存在空闲链表中）的地址。

union obj
{union obj * free_list_link;     //下一个节点的指针char client_data[1];                    //内存首地址
}

内存申请

1. 使用allocate向内存池请求 size 大小的内存空间, 如果需要请求的内存大小大于128bytes, 直接使用 malloc.
2. 如果需要的内存大小小于128bytes, allocate根据size找到最适合的自由链表.
   1. 如果链表不为空, 返回第一个node, 链表头改为第二个 node.
   2. 如果链表为空, 使用 blockAlloc 向内存池请求分配 20 * size 大小的内存.
      1. 内存池中有大于一个 size 的空间, 分配尽可能多的内存(但是最多20 * size字节), 将一个node返回, 其他的node添加到链表中.
      2. 内存池中有于一个 size 的空间，则返回该内存。
      3. 若果如果连一个size大小都不满足, 先将剩余的那一点小内存塞入合适的自由链表，接着调用 malloc 申请请求分配内存，大小为 20size2.
      4. 分配成功, 再次进行分配过程
      5. 分配不成功就从管理大小更大的 chunk（自由链表） 里分配一个块当作备用内存池。
      6. 若大块的 chunk 里都没有的话，挣扎一下——再malloc一次，还不行就执行用户设置的回调函数，如没有就抛出bad alloc。

代码

allocate 代码：

  static void* allocate(size_t __n){void* __ret = 0;if (__n > (size_t) _MAX_BYTES) {__ret = malloc_alloc::allocate(__n);}else {_Obj* __STL_VOLATILE* __my_free_list= _S_free_list + _S_freelist_index(__n);// Acquire the lock here with a constructor call.// This ensures that it is released in exit or during stack// unwinding.
#     ifndef _NOTHREADS/*REFERENCED*/_Lock __lock_instance;
#     endif_Obj* __RESTRICT __result = *__my_free_list;if (__result == 0)// 重新填充链表__ret = _S_refill(_S_round_up(__n));else {*__my_free_list = __result -> _M_free_list_link;__ret = __result;}}return __ret;};

_S_refill 代码：

template 
void*
__default_alloc_template<__threads, __inst>::_S_refill(size_t __n)
{int __nobjs = 20;// 去内存池要内存char* __chunk = _S_chunk_alloc(__n, __nobjs);_Obj* __STL_VOLATILE* __my_free_list;_Obj* __result;_Obj* __current_obj;_Obj* __next_obj;int __i;// 有一个,只能满足要求，直接返回if (1 == __nobjs) return(__chunk);__my_free_list = _S_free_list + _S_freelist_index(__n);// 不止一个，插入到链表中/* Build free list in chunk */__result = (_Obj*)__chunk;*__my_free_list = __next_obj = (_Obj*)(__chunk + __n);for (__i = 1; ; __i++) {__current_obj = __next_obj;__next_obj = (_Obj*)((char*)__next_obj + __n);if (__nobjs - 1 == __i) {__current_obj -> _M_free_list_link = 0;break;} else {__current_obj -> _M_free_list_link = __next_obj;}}return(__result);
}

_S_chunk_alloc 代码：

template 
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;// 若够 20 个，返回 20 个if (__bytes_left >= __total_bytes) {__result = _S_start_free;_S_start_free += __total_bytes;return(__result);} else if (__bytes_left >= __size) {// 不够 20 个则返回尽可能多的__nobjs = (int)(__bytes_left/__size);__total_bytes = __size * __nobjs;__result = _S_start_free;_S_start_free += __total_bytes;return(__result);} else {// 若一个都凑不出来，去获取要求的 2 倍大小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);//分配不成功就从大一点chunk力分配一个块当作备用内存池。然后如果该块没有被用完，剩余的byte再次进入这个else也会被上面那个if语句插入到能用的地方if (0 == _S_start_free) {size_t __i;_Obj* __STL_VOLATILE* __my_free_list;_Obj* __p;// Try to make do with what we have.  That can't// hurt.  We do not try smaller requests, since that tends// to result in disaster on multi-process machines.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));// Any leftover piece will eventually make it to the// right free list.}}//若大块的chunk里都没有的话，挣扎一下跳到下面那个函数，再malloc一次，不行就执行用户设置的回调函数，如没有就抛出bad allco_S_end_free = 0;	// In case of exception._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));}
}

内存释放

代码

  static void deallocate(void* __p, size_t __n){if (__n > (size_t) _MAX_BYTES)malloc_alloc::deallocate(__p, __n);else {_Obj* __STL_VOLATILE*  __my_free_list= _S_free_list + _S_freelist_index(__n);_Obj* __q = (_Obj*)__p;// acquire lock
#       ifndef _NOTHREADS/*REFERENCED*/_Lock __lock_instance;
#       endif /* _NOTHREADS */__q -> _M_free_list_link = *__my_free_list;*__my_free_list = __q;// lock is released here}}

注意

1. 刚开始初始化内存池的时候, 其实内存池中并没有内存, 同时所有的自由链表都为空链表.
2. 只有用户第一次向内存池请求内存时, 内存池会依次执行上述过程来完成内存池以及链表的首次填充, 而此时, 其他未使用链表仍然是空的.
3. 所有已经分配的内存在内存池中没有任何记录, 释放与否完全靠程序员自觉.
4. 释放内存时, 如果大于128bytes, 则直接 free, 否则加入相应的自由链表中而不是直接返还给操作系统.