[关闭]
@markheng 2018-08-02T13:38:51.000000Z 字数 4692 阅读 1028

STL源码剖析笔记 - STL的Allocator

C++


目标

配置器的作用是对模板对象进行空间分配和归还

结构

配置器一般分为两级,一级配置器和二级配置器,其中一级配置器直接与操作系统交互,向操作系统申请和归还内存。二级配置器,是在预申请内存小于128K时,从自身维护的内存池中直接分配和归还内存。

一级配置器

  1. class __malloc_alloc_template{
  2. private:
  3. // 三个函数指针处理内存不足的情况,oom = out of memory
  4. static void *oom_malloc(size_t);
  5. static void *oom_realloc(void*, size_t);
  6. static void (*__malloc_alloc_oom_handler)();
  7. public:
  8. static void * allocate(size_t n);
  9. static void deallocate(void *p, size_t);
  10. static void * reallocate(void *p, size_t , size_t new_sz);
  11. static void (* set_malloc_handler(void (*f)()))(); //仿真C++的set_new_handler()
  12. }

oom_mallocoom_realloc函数只有在allocatereallocate中调用malloc不成功的时候才调用,两个oom函数中不断地尝试申请和重新申请内存,直到申请成功或者调用malloc_handler或者抛出BAD_ALLOC异常

二级配置器

二级配置器维护一个内存池,并负责内存的分配和回收。并且会将任何小额区块的内存需求上调至8的倍数,并维护16个free-list,每个free-list分别管理bytes的区块,每个free-list是一个链表,该链表的节点结构如下

  1. union obj{
  2. union obj * free_list_link;
  3. char client_data[1]; // clients see this
  4. }

为了避免节点中存储额外的指针指向后继的节点,因此节点用的是union,达到一物二用的目的。从第一项看,是指针,第二项看,是数据空间

  1. enum {__ALIGN = 8};
  2. enum {__MAX_BYTES = 128};
  3. enum {__NFREELISTS = __MAX_BYTES / __ALIGN};
  4. class __default_alloc_template{
  5. private:
  6. static size_t ROUND_UP(size_t bytes){
  7. return (((bytes) + __ALIGN-1) & ~(__ALIGN - 1));
  8. }
  9. private:
  10. union obj{
  11. union obj * free_list_link;
  12. char client_data[1];
  13. };
  14. static obj * volatile free_list[__NFREELISTS];
  15. static size_t FREELIST_INDEX(size_t bytes){
  16. return (((bytes) + __ALIGN - 1) / __ALIGN - 1);
  17. }
  18. static void *refill(size_t n);
  19. //申请可以包含nobjs个free-list节点的空间,如果不行,那么会尝试降低nobjs的大小
  20. static char *chunk_alloc(size_t size, int &nobjs);
  21. static char *start_free;
  22. static char *end_free;
  23. static size_t heap_size;
  24. public:
  25. static void * allocate(size_t n){...}
  26. static void dallocate(void *p, size_t n){...}
  27. static void * reallocate(void *p, size_t old_sz, size_t new_sz);
  28. }

空间申请函数allocate()

  1. static void * allocate(size_t n)
  2. {
  3. obj * volatile * my_free_list;
  4. obj * result;
  5. // 大于128就调用一级配置器
  6. if(n > (size_t) __MAX_BYTES){
  7. return (malloc_alloc::allocate(n));
  8. }
  9. // 寻找16个free lists中合适的节点
  10. my_free_list = free_list + FREELIST_INDEX(n);
  11. result = *my_free_list;
  12. if(result == 0){ // 节点不足
  13. void *r = refill(ROUND_UP(n)); // 上调大小并重新申请节点
  14. return r;
  15. }
  16. *my_free_list = result -> free_list_link; // 调整free-list
  17. return (result);
  18. }

内存池

空间释放函数deallocate()

先判断区块大小,大于128bytes调用第一级配置器,小于128bytes就找出相应的free-list,将区块放回

  1. static void deallocate(void *p, size_t n)
  2. {
  3. obj *q = (obj*) p;
  4. obj * volatile * my_free_list;
  5. if (n > (size_t) __MAX_BYTES) { // 大于__MAX_BYTES是大区块
  6. malloc_alloc::deallocate(p, n);
  7. return;
  8. }
  9. // 寻找对应的free-list
  10. my_free_list = free_list + FREELIST_INDEX(n);
  11. q -> free_list_link = *my_free_list;
  12. *my_free_list = q;
  13. }

图示
回收内存图示

重新填充free lists (refill函数)

free-list中没有可用区块时,就调用refill()给free list重新补充“弹药”,缺省获得20个新节点,万一内存池中空间不足,获得的节点数可能小于20

  1. // 返回一个大小为n的对象,并且为free-list适当增加节点
  2. // 假设n已经上调至8的倍数,n是一个节点的大小
  3. void * __default_alloc_template<>::refill(size_t n)
  4. {
  5. int nobjs = 20;
  6. // 调用 chunk_alloc(),尝试取得nobjs个区块作为free list的新节点
  7. // nobjs是pass by reference,当内存不够时,被调整
  8. char * chunk = chunk_alloc(n, nobjs);
  9. obj * volatile * my_free_list;
  10. obj * result;
  11. obj * current_obj, * next_obj;
  12. int i;
  13. // 如果只获得一个区块,就直接分配给调用者,free list没有新节点
  14. if (1 == nobjs) return (chunk);
  15. // 否则调整free list,加入新的节点
  16. my_free_list = free_list + FREELIST_INDEX(n);
  17. // 在chunk空间内建立free list
  18. result = (obj*) chunk; //这一块准备返回给客户端
  19. // 以下引导free list指向新配置的空间
  20. *my_free_list = next_obj = (obj*)(chunk + n);
  21. // 将free list各个节点串起来
  22. for( i = 1; ; ++i) { // 从1开始,第0个返回给客户端
  23. current_obj = next_obj;
  24. next_obj = (obj *) ((char*) next_obj + n);
  25. if(nobjs - 1 == i) {
  26. current_obj -> free_list_link = 0;
  27. break;
  28. }else {
  29. current_obj -> free_list_link = next_obj;
  30. }
  31. }
  32. return (result);
  33. }

内存池

从内存池中取空间free list使用,上文的chunk_alloc()的工作

  1. char* chunk_alloc(size_t size, int &objs)
  2. {
  3. char * result;
  4. size_t total_bytes = size * nobjs;
  5. size_t bytes_left = end_free - start_free;
  6. if(bytes_left > total_bytes){ //剩余内存完全满足需求量
  7. result = start_free;
  8. start_free += total_bytes;
  9. return(result);
  10. }else if(bytes_left >= size){ //
  11. nobjs = bytes_left / size;
  12. total_bytes = size * nobjs;
  13. result = start_free;
  14. start_free += total_bytes;
  15. return (result);
  16. }else{
  17. //
  18. size_t bytes_to_get = 2 * total_bytes + ROUND_UP(heap_size >> 4);
  19. //
  20. if(bytes_left > 0) {
  21. obj * volatile * my_free_list = free_list + FREELIST_INDEX(bytes_left);
  22. ((obj *) start_free) -> free_list_link = *my_free_list;
  23. *my_free_list = (obj *)start_free;
  24. }
  25. start_free = (char*) malloc(bytes_to_get);
  26. if(0 == start_free){
  27. int i;
  28. obj * volatile * my_free_list, *p;
  29. for(i = size; i <= __MAX_BYTES; i += __ALIGN) {
  30. my_free_list = free_list + FREELIST_INDEX(i);
  31. p = *my_free_list;
  32. if (0 != p)
  33. {
  34. *my_free_list = p -> free_list_link;
  35. start_free = (char*) p;
  36. end_free = start_free + i;
  37. return(chunk_alloc(size, alloc));
  38. }
  39. }
  40. end_free = 0; //
  41. start_free = (char*)malloc_alloc::allocate(bytes_to_get);
  42. }
  43. heap_size += bytes_to_get;
  44. end_free = start_free + bytes_to_get;
  45. return (chunk_alloc(size, nobjs));
  46. }
  47. }

chunk_alloc()中以end_free - start_free判断内存池中的水量。如果
1. 水量充足,直接调出20个区块返回给free list。
2. 如果不足以20个区块,但足够一个以上的区块,就拨出这不足20个区块的空间出去,并修改pass by reference的nobjs为实际能够供应的区块数。
3. 一个区块都没法供应,那么就需要用malloc()从heap中配置内存,为内存池中注入活水源头,新水量的大小为需求量的两倍,再加上一个随着配置次数增加而越来越大的附加量。
4. 万一山穷水尽,整个系统的heap空间都不够了,malloc()失败,chunk_alloc()就试着寻找没有被用到,并且更大的区块,找到一块就挖出,找不到就调用第一级配置器。第一级配置器使用malloc()配置内存,依赖它的out-of-memory处理机制,有机会释放其他的内存拿来使用,如果可以,就成功,否则,最后发出BAD_ALLOC异常。
内存池

两级配置的优点

可以避免内存碎片和抖动

添加新批注
在作者公开此批注前,只有你和作者可见。
回复批注