STL源码剖析(空间配置器)

前言

在STL中，容器的定义中都带一个模板参数，如vector

template <class T, class Alloc = alloc>

class vector {...}

其中第二个参数就是该容器使用的空间配置器，其中缺省使用STL已经实现的空间配置器(alloc)，

该配置器使用malloc/free等为vector分配内存。

缺省的空间配置器

alloc定义了两级的空间配置器，第一级是对malloc/free简单的封装。

而为了解决内存碎片的问题，跟进行内存管理，alloc实现的第二级的空间配置器。

第二级空间配置器在分配大块内存(大于128bytes)时，会直接调用第一级空间配置器，

而分配小于128bytes的内存时，则使用内存池跟free_list进行内存分配/管理。

第一级空间配置器

基本实现如下(跟SGI STL可能有点出入，主要是提取核心的内容)

 class base_alloc {

 public:

     // 只是对malloc/free的简单封装

     static void* allocate(size_t n)

     {

         void* res = malloc(n);

         if ( == res) res = oom_malloc(n);

         return res;

     }

     static void* reallocate(void* p, size_t new_sz)

     {

         void* res = realloc(p, new_sz);

         if ( == res) res = oom_realloc(p, new_sz);

         return res;

     }

     static void deallocate(void* p)

     {

         free(p);

     }

     // 用来设置内存不足时的处理函数 该函数参数跟返回值都是一个函数指针

     // 一般会抛出异常/尝试回收内存

     static void(*set_handler(void(*f)()))()

     {

         void(*old)() = _oom_handler;

         _oom_handler = f;

         return old;

     }

 private:

     // 用来处理内存不足的情况

     static void* oom_malloc(size_t n)

     {

         void(*my_handler)();

         void* res;

         for (;;)

         {

             my_handler = _oom_handler;

             if ( == my_handler) { return NULL; }

             (*my_handler)();

             if (res = malloc(n)) return res;

         }

     }

     // 用来处理内存不足的情况

     static void* oom_realloc(void* p, size_t n)

     {

         void(*my_handler)();

         void* res;

         for (;;)

         {

             my_handler = _oom_handler;

             if ( == my_handler) { return NULL; }

             (*my_handler)();

             if (res = reallocate(p, n)) return res;

         }

     }

     // 由用户设置，在内存不足的时候进行处理，由上面两个函数调用

     static void(*_oom_handler)();

 };

 // 处理函数默认为0

 void(*base_alloc::_oom_handler)() = ;

它可以设定一个处理内存不足的时候的处理函数(跟set_new_handler类似)。

第二级空间配置器

该配置器维护一个free_list，这是一个指针数组。

在分配内存的时候，补足8bytes的倍数，free_list数组中每个指针分别管理分配大小为8、16、24、32...bytes的内存。

下图表示从二级空间配置器中分配内存时是如何维护free_list的(建议参考下面源码阅读)。

开始所有指针都为0，没有可分配的区块时(就是free_list[i]==0)会从内存池中分配内存(默认分配20个区块)插入到free_list[i]中。

然后改变free_list[i]的指向，指向下一个区块(free_list_link指向下一个区块，如果没有则为0)。

下图表示二级空间配置器回收内存时是如何维护free_list结构的。

回收的时候只是将区块插入到free_list[i]的开头，这块内存用于下次分配的时候使用。

该配置器实现如下(同样提取核心的部分)：

 enum { _ALIGN =  };    // 对齐

 enum { _MAX_BYTES =  }; // 区块大小上限

 enum { _NFREELISTS = _MAX_BYTES / _ALIGN }; // free-list个数

 class default_alloc {

 private:

     // 将bytes上调到8的倍数

     static size_t ROUND_UP(size_t bytes)

     {

         return (bytes + _ALIGN - ) & ~(_ALIGN - );

     }

 private:

     union obj {

         union obj* free_list_link;

         char client_data[];

     };

 private:

     // 16个free-lists 各自管理分别为8,16,24...的小额区块

     static obj* free_list[_NFREELISTS];

     // 根据区块大小，决定使用第n号free-list

     static size_t FREELIST_INDEX(size_t bytes)

     {

         return (bytes + _ALIGN - ) / _ALIGN - ;

     }

     // 分配内存，返回一个大小为n的区块，可能将大小为n的其他区块加入到free_list

     static void* refill(size_t n)

     {

         // 默认分配20个区块

         int nobjs = ;

         char* chunk = chunk_alloc(n, nobjs);

         obj** my_free_list;

         obj* result, *current_obj, *next_obj;

         // 如果只分配了一个区块，直接返回

         if ( == nobjs) return chunk;

         // 否则将其他区块插入到free list

         my_free_list = free_list + FREELIST_INDEX(n);

         result = (obj*)chunk;

         // 第一个区块返回 后面的区块插入到free list

         *my_free_list = next_obj = (obj*)(chunk + n);

         for (int i = ;; ++i)

         {

             current_obj = next_obj;

             next_obj = (obj*)((char*)next_obj + n);

             // 最后一个next的free_list_link为0

             if (nobjs -  == i)

             {

                 current_obj->free_list_link = ;

                 break;

             }

             current_obj->free_list_link = next_obj;

         }

         return result;

     }

     // 分配内存

     // 在内存池容量足够时，只调整start_free跟end_free指针

     // 在内存池容量不足时，调用malloc分配内存(2 * size * nobjs +  ROUND_UP(heap_size >> 4)，每次调整heap_size += 本次分配内存的大小)

     static char* chunk_alloc(size_t size, int& nobjs);

     static char* start_free; //内存池的起始位置

     static char* end_free;     //内存池的结束位置

     static size_t heap_size;         //分配内存时的附加量

 public:

     static void* allocate(size_t n)

     {

         obj** my_free_list;

         obj* result;

         // 大于128就调用第一级空间配置器

         if (n > (size_t)_MAX_BYTES)

             return base_alloc::allocate(n);

         // 寻找适当的free-list

         my_free_list = free_list + FREELIST_INDEX(n);

         result = *my_free_list;

         // 没有可用的free list

         if (result == )

             return refill(ROUND_UP(n));

         // 调整free list 移除free list

         *my_free_list = result->free_list_link;

         return result;

     }

     static void deallocate(void* p, size_t n)

     {

         obj* q = (obj*)p;

         obj** my_free_list;

         // 大于128就调用第一级空间配置器

         if (n > (size_t)_MAX_BYTES)

         {

             base_alloc::deallocate(p);

             return;

         }

         // 寻找对应的free list

         my_free_list = free_list + FREELIST_INDEX(n);

         // 调整free list 回收区块(将区块插入到my_free_list)

         q->free_list_link = *my_free_list;

         *my_free_list = q;

     }

     static void reallocate(void* p, size_t old_sz, size_t new_sz);

 };

 char* default_alloc::start_free = ;

 char* default_alloc::end_free = ;

 size_t default_alloc::heap_size = ;

 default_alloc::obj* default_alloc::free_list[_NFREELISTS] = { , , , , , , , , , , , , , , ,  };

巴特西

STL源码剖析(空间配置器)

最新文章

热门文章