欢迎您访问程序员文章站本站旨在为大家提供分享程序员计算机编程知识!
您现在的位置是: 首页  >  IT编程

STL源码分析之第二级配置器

程序员文章站 2022-06-04 22:54:22
前言 第一级是直接调用 分配空间, 调用 释放空间, 第二级三就是建立一个内存池, 小于128字节的申请都直接在内存池申请, 不直接调用 和`free`. 本节分析第二级空间配置器, STL将第二级配置器设置为默认的配置器, 所以只要一次申请的空间不超过128字节就默认在内存池中申请空间, 超过才会 ......

前言

第一级是直接调用malloc分配空间, 调用free释放空间, 第二级三就是建立一个内存池, 小于128字节的申请都直接在内存池申请, 不直接调用mallocfree. 本节分析第二级空间配置器, stl将第二级配置器设置为默认的配置器, 所以只要一次申请的空间不超过128字节就默认在内存池中申请空间, 超过才会调用第一级配置器.

第二级配置器

首先先来介绍3个常量.

  1. __align : 以8字节进行对齐
  2. __max_bytes : 二级分配器最大分配的内存大小
  3. __nfreelists : 128字节能分配的的链表个数, 并且从每个链表保存的内存大小都是8的倍数, 而且都比前一个大8字节, 也就是分别是8, 16, 32...128字节
// 二级配置器
enum {__align = 8}; // 设置对齐要求. 对齐为8字节, 没有8字节自动补齐
enum {__max_bytes = 128};   // 第二级配置器的最大一次性申请大小, 大于128就直接调用第一级配置器
enum {__nfreelists = __max_bytes/__align};  // 链表个数, 分别代表8, 16, 32....字节的链表

再介绍一个宏操作, 这是进行对齐操作, 将不满8的倍数的填充成8的倍数.

static size_t freelist_index(size_t bytes) \
{\
    return (((bytes) + align-1) / __align - 1);\
}

从allocate先切入分析

  1. 先判断申请的字节大小是不是大于128字节, 是, 则交给第一级配置器来处理. 否, 继续往下执行
  2. 找到分配的地址对齐后分配的是第几个大小的链表.
  3. 获得该链表指向的首地址, 如果链表没有多余的内存, 就先填充链表.
  4. 返回链表的首地址, 和一块能容纳一个对象的内存, 并更新链表的首地址
static void * allocate(size_t n)
{
      obj * __volatile * my_free_list;
      obj * __restrict result;
    
      if (n > (size_t) __max_bytes) 
      {
        return(malloc_alloc::allocate(n));
      }
      my_free_list = free_list + freelist_index(n);
      result = *my_free_list;
      if (result == 0)  // 没有多余的内存, 就先填充链表.
      {
        void *r = refill(round_up(n));
        return r;
      }
      *my_free_list = result -> free_list_link;
      return (result);
};

refill内存填充.

  1. 向内存池申请空间的起始地址
  2. 如果只申请到一个对象的大小, 就直接返回一个内存的大小, 如果有更多的内存, 就继续执行
  3. 从第二个块内存开始, 把从内存池里面分配的内存用链表给串起来, 并返回一个块内存的地址给用户
// 内存填充
template <bool threads, int inst>
void* __default_alloc_template<threads, inst>::refill(size_t n)
{
    int nobjs = 20;
    char * chunk = chunk_alloc(n, nobjs);             // 向内存池申请空间的起始地址
    obj * __volatile * my_free_list;
    obj * result;
    obj * current_obj, * next_obj;
    int i;

    // 如果只申请到一个对象的大小, 就直接返回一个内存的大小
    if (1 == nobjs) return(chunk);
    my_free_list = free_list + freelist_index(n);

    // 申请的大小不只一个对象的大小的时候
    result = (obj *)chunk;
    // my_free_list指向内存池返回的地址的下一个对齐后的地址
    *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 -> free_list_link = 0;
            break;
        } 
        else 
        {
            current_obj -> free_list_link = next_obj;
        }
        }
    return(result);
}

再从deallocate结束

  1. 释放的内存大于128字节直接调用一级配置器进行释放
  2. 将内存直接还给对应大小的链表就行了, 并不用直接释放内存, 以便后面分配内存的时候快速.
static void deallocate(void *p, size_t n)
{
      obj *q = (obj *)p;
      obj * __volatile * my_free_list;
    
      // 释放的内存大于128字节直接调用一级配置器进行释放
      if (n > (size_t) __max_bytes) 
      {
        malloc_alloc::deallocate(p, n);
        return;
      }
      my_free_list = free_list + freelist_index(n);
      q -> free_list_link = *my_free_list;
      *my_free_list = q;
}

统一的接口

定义符合stl规格的配置器接口, 不管是一级配置器还是二级配置器都是使用这个接口进行分配的

// 定义符合stl规格的配置器接口, 不管是一级配置器还是二级配置器都是使用这个接口进行分配的
template<class t, class alloc>
class simple_alloc {
  public:
    static t *allocate(size_t n)
    { return 0 == n? 0 : (t*) alloc::allocate(n * sizeof (t)); }
    static t *allocate(void)
    { return (t*) alloc::allocate(sizeof (t)); }
    static void deallocate(t *p, size_t n)
    { if (0 != n) alloc::deallocate(p, n * sizeof (t)); }
    static void deallocate(t *p)
    { alloc::deallocate(p, sizeof (t)); }
};

总结

用链表来保存不同字节大小的内存块, 就很容易的进行维护, 而且每次的内存分配都直接可以从链表或者内存池中获得, 提升了我们申请内存的效率, 毕竟每次调用malloc和free效率是很低的, 特别是很小内存的时候.

stl默认的就是第二级配置器, 它会自动判断我们使用哪一个配置器.