allocator的基本概念

在C++中所有STL容器的空间分配其实都是使用的std::allocator

std::allocator是可以感知类型的空间分配器，将空间的申请与对象的构建、以及空间的回收与对象的销毁严格分离。

以前我们知道使用new创建单个对象的时候，空间的申请与对象的构造实际也是分开的（可以回顾new表达式的工作步骤）。

那么为什么要将空间的申请与对象的构建分开呢？

1. 减少不必要的对象构造和析构：在容器的使用过程中，有时只是需要预留一些空间，而并不需要立即在这些空间上构造对象。例如，std::vector 的 reserve 函数，它的作用是为容器预留足够的内存空间，但不会构造任何对象。如果不将空间申请和对象构建分开，每次预留空间时都会构造对象，之后又可能因为不需要这些对象而进行析构，这会带来不必要的性能开销。

2. 方便实现复杂的容器操作：在实现容器的一些操作，如插入、删除元素时，将空间申请和对象构建分开可以更方便地处理各种情况。例如，在插入元素时，如果当前空间不足，容器可以先申请新的空间，然后将原有元素移动到新空间，最后在合适的位置构造新的对象，这样的操作更加灵活和高效。（比如vector的动态扩容机制背后就使用了空间配置器）

常用成员函数

xxxxxxxxxx
11
1
//申请空间
2
T* allocate( std::size_t n );
3

4
//释放空间
5
void deallocate( T* p, std::size_t n );
6

7
//构建对象
8
void construct( pointer p, const_reference val );
9

10
//执行析构
11
void destroy( pointer p );  //p->~T()

底层实现

原理

空间配置器会分为两级：

一级空间配置器使用类模板malloc_alloc_template ，其底层使用的是malloc/free进行空间的申请与释放；

二级空间配置器使用类模板default_alloc_template（默认空间配置器），其底层根据申请空间大小又分为两个分支，第一分支是当申请的空间大于128字节的时候，还是走malloc_alloc_template ，当申请的空间小于128字节的使用，使用内存池 + 自由链表的方法申请空间。

注意：这里提到的自由链表实际是一个容量为16的指针数组，在源码中使用了_S_free_list这个名字，直译为自由链表

有一个容量为16的指针数组，每个元素（指针）指向一个链表 ，用于管理不同大小的内存块。这 16 个指针所指向的链表，分别对应 8、16、24、32、40、48、52、64、72、80、88、96、104、112、120、128 字节的内存块。

每当程序申请小于 128 字节的内存时，二级空间配置器会先将申请的内存大小上调为 8 的倍数，再根据上调后的大小（8的整数倍）找到对应的链表。

比如：

数组中下标为3的指针，代表着会按照8 * (3 + 1) = 32字节为基本单位申请空间。

第一次申请32个字节空间的时候，一次性申请很大一片空间（比如32 * 20 = 640个字节），然后按照32字节为一个等分，分成多个等分，然后挂接在下标为3的指针下面，形成链表形式。

以后需要32字节的时候，直接在下标为3的下面取出一个节点即可，就是32个字节的内存空间。

---

如果申请64字节空间，第一次申请时也申请很大一片空间，同样按照64字节为一个等分，分成多个等分，挂载在数组中下标为7的指针之下。

以后如果需要申请64字节时，就在下标为7的下面取出一个节点即可。

其他下标的处理方式完全一致。

自由链表的工作示意图如下,第一次申请空间时比较麻烦，后续再此申请同等大小的空间可以以O(1)的时间复杂度完成申请。

这么干有什么意义呢，为什么不每次直接申请相应大小的空间？

如果频繁申请小片空间，可能会出现内存碎片的问题，这样导致空间的利用率低；

会在内核态与用户态之间进行频繁的切换，时间消耗也比较大。

源码

由头文件<memory>找到<stl_alloc.h>

xxxxxxxxxx
20
1
template <class _Tp>
2
class allocator {
3
    // 了解到_Alloc类型别名
4
    typedef alloc _Alloc;
5

6
public:
7
    _Tp *allocate(size_type __n, const void * = 0) {
8
        // 如果申请空间大小不为0，调用_Alloc的静态成员函数allocate
9
        // 如果申请空间大小为0，返回空指针
10
        return __n != 0 ? static_cast<_Tp *>(_Alloc::allocate(__n * sizeof(_Tp))) : nullptr;
11
    }
12

13
    void deallocate(pointer __p, size_type __n) {
14
        _Alloc::deallocate(__p, __n * sizeof(_Tp));
15
    }
16

17
    void construct(pointer __p, const _Tp &__val) { new (__p) _Tp(__val); }
18

19
    void destroy(pointer __p) { __p->~_Tp(); }
20
};

继续查看类型别名原本的定义

xxxxxxxxxx
2
1
typedef malloc_alloc alloc;
2
typedef __malloc_alloc_template<0> malloc_alloc;

xxxxxxxxxx
11
1
template <int __inst>
2
class __malloc_alloc_template {
3
public:
4
    static void *allocate(size_t __n) {
5
        // 其实底层就是使用了malloc
6
        void *__result = malloc(__n);
7
        if (nullptr == __result)
8
            __result = _S_oom_malloc(__n); // 申请失败的情况
9
        return __result;
10
    }
11
};

这就是一级空间配置器

回到typedef alloc _Alloc; 查找alloc时还有第二个分支

xxxxxxxxxx
11
1
// 另一个分支的alloc类
2
typedef __default_alloc_template<__NODE_ALLOCATOR_THREADS, 0> alloc;
3

4
// 相当于
5
#ifdef __USE_MALLOC
6

7
typedef malloc_alloc alloc;
8

9
#else
10
typedef __default_alloc_template<__NODE_ALLOCATOR_THREADS, 0> alloc;
11
#endif

查看__default_alloc_template的定义(下面对源码进行了一定的简化)

也就是二级空间配置器

xxxxxxxxxx
34
1
// 主要查看静态成员函数allocate的定义
2
template <bool threads, int inst>
3
class __default_alloc_template {
4
    enum { _ALIGN = 8 };
5
    enum { _MAX_BYTES = 128 };
6
    enum { _NFREELISTS = 16 };
7

8
    /* __n must be > 0      */
9
    static void *allocate(size_t __n) {
10
        void *__ret = nullptr;
11

12
        if (__n > 128) { // if (__n > (size_t) _MAX_BYTES){
13
            //__ret = malloc_alloc::allocate(__n);
14
            // 又回到刚才的情况了，等价于就是调用了malloc
15
            __ret = malloc(__n);
16
        } else {
17
            // 这一步很关键，跳转查看_S_free_list和_S_freelist_index
18
            // 从数组开始位置偏移相应长度，接下来可以在这个位置之下挂载内存块节点
19
            //
20
            // 假设arr是一个存着int*元素的数组 int * arr[16] = {0}
21
            // arr int** + 3 就得到了数组中第四个元素的地址
22
            _Obj **__my_free_list = _S_free_list + _S_freelist_index(__n);
23

24
            _Obj *__RESTRICT __result = *__my_free_list;
25
            if (__result == 0)
26
                __ret = _S_refill(_S_round_up(__n));
27
            else {
28
                *__my_free_list = __result->_M_free_list_link;
29
                __ret = __result;
30
            }
31
        }
32
        return __ret;
33
    };
34
};

对于_S_free_list，最终其类型为_obj*[16]

xxxxxxxxxx
15
1
#if defined(__SUNPRO_CC) || defined(__GNUC__) || defined(__HP_aCC)
2
static _Obj *_S_free_list[];
3
// Specifying a size results in duplicate def for 4.1
4
#else
5
    static _Obj*  _S_free_list[16]; 
6

7
template <bool __threads, int __inst>
8
typename __default_alloc_template<__threads, __inst>::_Obj* __STL_VOLATILE
9
__default_alloc_template<__threads, __inst> ::_S_free_list[
10
#if defined(__SUNPRO_CC) || defined(__GNUC__) || defined(__HP_aCC)
11
    _NFREELISTS
12
#else
13
    __default_alloc_template<__threads, __inst>::_NFREELISTS
14
#endif
15
] = {0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, };

对于_S_freelist_index(__n)

xxxxxxxxxx
5
1
// 假设申请32字节，这里传入的参数就是32
2
static size_t _S_freelist_index(size_t __bytes) {
3
    //(32 + 8 - 1)/8 - 1 = 4 - 1 = 3       32字节对应数组中下标为3的位置
4
    return (((__bytes) + (size_t)_ALIGN - 1) / (size_t)_ALIGN - 1);
5
}

作用：根据申请内存的大小取其对应于指针数组（自由链表）中的下标

刚才的allocate函数中申请空间大小小于128的分支就可以这样来进行理解

xxxxxxxxxx
15
1
// 假设申请32字节，__n = 32
2
//_S_freelist_index(32) = 3
3
// 类似于int* arr[16] = {0};
4
// int **p = arr + 3;
5
_Obj **__my_free_list = _S_free_list + _S_freelist_index(__n);
6

7
// 一开始_S_free_list里存的全都是空指针
8
//__result = nullptr;
9
_Obj *__RESTRICT __result = *__my_free_list;
10
if (__result == nullptr)
11
    __ret = _S_refill(_S_round_up(__n)); // 跳转查看_S_round_up，再跳转查看_S_refill
12
else {
13
    *__my_free_list = __result->_M_free_list_link;
14
    __ret = __result;
15
}

_S_round_up函数

xxxxxxxxxx
25
1
static size_t _S_round_up(size_t __bytes) //__bytes = 32
2
{
3
    //(32 + 8 - 1) & ~(8 - 1) = 39 & ~7  按位与
4
    // 39 = 32 + 4 + 2 + 1 ====> 0010 0111
5
    // 7 = 4 + 2 + 1 ====> 0000 0111  再取反 ~7 = 1111 1000
6
    // 39 & ~7 = 0010 0000  =====> 就是32
7
    return (((__bytes) + (size_t)_ALIGN - 1) & ~((size_t)_ALIGN - 1));
8
}
9

10
// 传入的参数是32，返回值也是32，好像有点没必要，那么试试如果传进来的是31
11
//(31 + 8 - 1) & ~(8 - 1) = 38 & ~7  按位与
12
// 38 = 32 + 4 + 2 ====> 0010 0110
13
// 7 = 4 + 2 + 1 ====> 0000 0111  再取反 ~7 = 1111 1000
14
// 38 & ~7 = 0010 0000  =====> 也是32
15

16
// 如果传入的是33
17
//(33 + 8 - 1) & ~(8 - 1) = 40 & ~7  按位与
18
// 40 = 32 + 8 ====> 0010 1000
19
// 7 = 4 + 2 + 1 ====> 0000 0111  再取反 ~7 = 1111 1000
20
// 40 & ~7 = 0010 1000  =====> 40
21

22
// 不妨多试一下参数
23
// 25 ---> 32
24
// 24 ---> 24
25
//...

作用：这个函数实现的就是向上取整得到8的整数倍

_S_refill函数

xxxxxxxxxx
34
1
// 仍然根据刚才的假设走，此时传入参数__n = 32
2
void *__default_alloc_template<__threads, __inst>::_S_refill(size_t __n) {
3
    int __nobjs = 20;
4
    //_S_chunk_alloc实际申请了2 * 20 * 32 = 1280字节空间
5
    //__chunk会指向前640字节的空间的首地址
6
    char *__chunk = _S_chunk_alloc(__n, __nobjs); //_S_chunk_alloc这个函数才是真正去申请了空间的函数
7

8
    _Obj *__STL_VOLATILE *__my_free_list;
9
    _Obj *__result;
10
    _Obj *__current_obj;
11
    _Obj *__next_obj;
12
    int __i;
13

14
    if (1 == __nobjs)
15
        return (__chunk);
16

17
    // 在数组中偏移到下标3位置，接下来32字节的内存块都挂载到这个位置之下
18
    __my_free_list = _S_free_list + _S_freelist_index(__n);
19

20
    /* Build free list in chunk */
21
    __result = (_Obj *)__chunk;                             // 指向640个字节的最开始，强转成_Obj*类型指针，并且__result作为了最后的返回值，实际上就是把32字节的空间交出来了
22
    *__my_free_list = __next_obj = (_Obj *)(__chunk + __n); // 从640字节内存首地址偏移32字节，强转成_Obj*类型指针，并用数组中的第四个指针（下标3）进行指向
23
    for (__i = 1;; __i++) {
24
        __current_obj = __next_obj;
25
        __next_obj = (_Obj *)((char *)__next_obj + __n); //__next_obj再偏移32字节
26
        if (__nobjs - 1 == __i) {                        // 20 - 1 != 1，走else分支 —— 要循环19次，最终把剩下的19 * 32字节切割成32字节等分，一步一步挂载起来
27
            __current_obj->_M_free_list_link = 0;
28
            break;
29
        } else {
30
            __current_obj->_M_free_list_link = __next_obj; // 用链表连接的方式，从（640-32）剩下的内存块中又切割出32字节
31
        }
32
    }
33
    return (__result);
34
}

作用：将调用_S_chunk_alloc所返回的640字节以32字节为一个等分，分成20等分，第一等分交给__result直接作为返回值，剩下的19个32字节会以链表的形式挂接在数组中下标为3的元素之下。

_S_chunk_alloc函数

xxxxxxxxxx
66
1
template <bool __threads, int __inst>
2
char *
3
__default_alloc_template<__threads, __inst>::_S_chunk_alloc(size_t __size, // 32
4
                                                            int &__nobjs)  // 20
5
{
6
    char *__result;
7
    size_t __total_bytes = __size * __nobjs;           // 640
8
    size_t __bytes_left = _S_end_free - _S_start_free; // 0 第二次变成1280
9

10
    if (__bytes_left >= __total_bytes) {
11
        __result = _S_start_free;       // 将1280字节的空间交出了640个字节
12
        _S_start_free += __total_bytes; //_S_start_free和_S_end_free之间只剩640字节空间
13
        return (__result);
14
    } else if (__bytes_left >= __size) {
15
        __nobjs = (int)(__bytes_left / __size);
16
        __total_bytes = __size * __nobjs;
17
        __result = _S_start_free;
18
        _S_start_free += __total_bytes;
19
        return (__result);
20
    } else {
21
        // 第一次得到了__bytes_to_get = 1280
22
        size_t __bytes_to_get =
23
            2 * __total_bytes + _S_round_up(_S_heap_size >> 4);
24
        // Try to make use of the left-over piece.
25
        if (__bytes_left > 0) {
26
            _Obj *__STL_VOLATILE *__my_free_list =
27
                _S_free_list + _S_freelist_index(__bytes_left);
28

29
            ((_Obj *)_S_start_free)->_M_free_list_link = *__my_free_list;
30
            *__my_free_list = (_Obj *)_S_start_free;
31
        }
32

33
        _S_start_free = (char *)malloc(__bytes_to_get); //_S_start_free指向1280字节的首地址
34

35
        if (0 == _S_start_free) {
36
            size_t __i;
37
            _Obj *__STL_VOLATILE *__my_free_list;
38
            _Obj *__p;
39
            // Try to make do with what we have.  That can't
40
            // hurt.  We do not try smaller requests, since that tends
41
            // to result in disaster on multi-process machines.
42
            for (__i = __size;
43
                 __i <= (size_t)_MAX_BYTES;
44
                 __i += (size_t)_ALIGN) {
45
                __my_free_list = _S_free_list + _S_freelist_index(__i);
46
                __p = *__my_free_list;
47
                if (0 != __p) {
48
                    *__my_free_list = __p->_M_free_list_link;
49
                    _S_start_free = (char *)__p;
50
                    _S_end_free = _S_start_free + __i;
51
                    return (_S_chunk_alloc(__size, __nobjs));
52
                    // Any leftover piece will eventually make it to the
53
                    // right free list.
54
                }
55
            }
56
            _S_end_free = 0; // In case of exception.
57
            _S_start_free = (char *)malloc_alloc::allocate(__bytes_to_get);
58
            // This should either throw an
59
            // exception or remedy the situation.  Thus we assume it
60
            // succeeded.
61
        }
62
        _S_heap_size += __bytes_to_get;               //_S_heap_size = 1280
63
        _S_end_free = _S_start_free + __bytes_to_get; //_S_end_free指向1280字节的尾后位置
64
        return (_S_chunk_alloc(__size, __nobjs));     // 递归调用
65
    }
66
}

xxxxxxxxxx
8
1
template <bool __threads, int __inst>
2
char *__default_alloc_template<__threads, __inst>::_S_start_free = 0;
3

4
template <bool __threads, int __inst>
5
char *__default_alloc_template<__threads, __inst>::_S_end_free = 0;
6

7
template <bool __threads, int __inst>
8
size_t __default_alloc_template<__threads, __inst>::_S_heap_size = 0;

xxxxxxxxxx
4
1
union _Obj {
2
    union _Obj *_M_free_list_link;
3
    char _M_client_data[1]; // The client sees this.
4
};

再回过头来看allocate函数，如果是第二次申请32字节空间，逻辑是怎样的。

xxxxxxxxxx
14
1
// 假设申请32字节，__n = 32
2
//_S_freelist_index(32) = 3
3
// 同样找到数组下标3位置
4
_Obj **__my_free_list = _S_free_list + _S_freelist_index(__n);
5

6
// 这次_S_free_list的下标3位置存的不是空指针
7
// 而是还挂载着19个32字节
8
_Obj *__RESTRICT __result = *__my_free_list;
9
if (__result == nullptr)
10
    __ret = _S_refill(_S_round_up(__n)); // 跳转查看_S_round_up，再跳转查看_S_refill
11
else {
12
    *__my_free_list = __result->_M_free_list_link; // 让数组中下标3的元素（指针）指向再下一个内存块节点
13
    __ret = __result;                              // 又交出32字节
14
}

函数的调用关系图

现在对自由链表已经有了初步的了解，那么内存池又是什么？

从名字上进行推理，线程池就是先创建一堆的线程备用，内存池应该也是先申请好一片空间备用。回到刚才的_S_chunk_alloc函数，这个函数是真正去分配空间的函数。刚才申请32字节空间时，根据源码逻辑是申请了1280个字节堆空间的，但只拿出了640个字节挂接在数组中下标为4的链表中。还有640个字节的空间干什么用？当然是备用的。

根据源码分析，如果接下来又要申请64字节空间会怎样。

xxxxxxxxxx
21
1
class __default_alloc_template {
2
  static void* allocate(size_t __n) //__n = 64
3
  {
4
      void* __ret = 0;    
5
      //...
6
      
7
      //找到数组中下标为7的位置
8
      _Obj** __my_free_list = _S_free_list + _S_freelist_index(__n);  
9
        
10
      _Obj* __RESTRICT __result = *__my_free_list; //数组下标7位置的元素仍然是空指针   _S_free_list[7] = nullptr;
11
      if (__result == 0)
12
          //跳转_S_refill
13
        __ret = _S_refill(_S_round_up(__n));  //__ret = _S_refill(64);   
14
      else {
15
        *__my_free_list = __result -> _M_free_list_link;
16
        __ret = __result;
17
      }
18
    }
19
    return __ret;
20
  };
21
};

xxxxxxxxxx
32
1
void *__default_alloc_template<__threads, __inst>::_S_refill(size_t __n) {
2
    int __nobjs = 20;
3
    // 跳转先只执行完_S_chunk_alloc再看
4
    char *__chunk = _S_chunk_alloc(__n, __nobjs); // char* __chunk = _S_chunk_alloc(64, 20)
5
    _Obj *__STL_VOLATILE *__my_free_list;
6
    _Obj *__result;
7
    _Obj *__current_obj;
8
    _Obj *__next_obj;
9
    int __i;
10

11
    if (1 == __nobjs)
12
        return (__chunk);
13

14
    __my_free_list = _S_free_list + _S_freelist_index(__n); // 定位数组下标为7的位置
15

16
    /* Build free list in chunk */
17
    __result = (_Obj *)__chunk;                             // 拿出64字节给__result
18
    *__my_free_list = __next_obj = (_Obj *)(__chunk + __n); // 640字节首地址偏移64字节后强转，让数组下标7位置的元素指向第二个64字节
19

20
    // 接下来的逻辑仍然是切割，将剩下的内存切割成了9个64字节
21
    for (__i = 1;; __i++) {
22
        __current_obj = __next_obj;
23
        __next_obj = (_Obj *)((char *)__next_obj + __n);
24
        if (__nobjs - 1 == __i) {
25
            __current_obj->_M_free_list_link = 0;
26
            break;
27
        } else {
28
            __current_obj->_M_free_list_link = __next_obj;
29
        }
30
    }
31
    return (__result);
32
}

xxxxxxxxxx
35
1
template <bool __threads, int __inst>
2
char *__default_alloc_template<__threads, __inst>::_S_start_free = 0;
3

4
template <bool __threads, int __inst>
5
char *__default_alloc_template<__threads, __inst>::_S_end_free = 0;
6

7
template <bool __threads, int __inst>
8
size_t __default_alloc_template<__threads, __inst>::_S_heap_size = 0;
9

10
template <bool __threads, int __inst>
11
char *__default_alloc_template<__threads, __inst>::_S_chunk_alloc(size_t __size, //__size = 64
12
                                                                  int &__nobjs)  //__nobjs = 20   注意这里形参是引用，在函数中会通过形参改变实参
13
{
14
    char *__result;
15
    size_t __total_bytes = __size * __nobjs; // 64 * 20 = 1280
16
                                             // 第一次申请32时这个结果为0，所以走的是下面的第三个分支；
17
    // 接着第一次申请64时这个结果已经是640了,所以应该走下面的第二个分支
18
    size_t __bytes_left = _S_end_free - _S_start_free;
19

20
    if (__bytes_left >= __total_bytes) {
21
        __result = _S_start_free;
22
        _S_start_free += __total_bytes;
23
        return (__result);
24
    } else if (__bytes_left >= __size) {
25
        __nobjs = (int)(__bytes_left / __size); // 640/64 = 10  注意这里__nobjs向外影响实参，改变为10
26
        __total_bytes = __size * __nobjs;       // 64 * 10 = 640
27
        __result = _S_start_free;
28
        _S_start_free += __total_bytes; //_S_start_free经过了这样的偏移，实际上就跟_S_end_free指到一起了（代表着内存池里的内存贡献出来了）
29
        return (__result);              // 这里的逻辑就是把刚才剩余的640字节空间的首地址作为了返回值
30
    } else {
31
        size_t __bytes_to_get =
32
            2 * __total_bytes + _S_round_up(_S_heap_size >> 4);
33
        //...
34
    }
35
}

如果接着还要申请64字节（或者57-64范围内的大小），就再从数组中下标7位置对应的链表中再拿一个内存块出来，非常方便。

如果再要申请96个字节，操作方式跟第一次申请32字节一样，在数组下标11的位置下面挂载一些96字节的内存块。

假如接下来某一次要申请72字节，但是内存池和堆空间都没有连续的72字节了。想要使用相同的逻辑再申请空间不会成功，那么会往上借，也就是往数组下标9的位置去找，再没有就往下标10、下标11去找。下标11下面挂载着内存块，从中去除96字节的块，进行切割，获取72字节，剩24字节作为内存池中的内存。

目前为止，只是解决了allocate的问题，再来看看deallocate函数

如果是一级空间配置器，其背后就是调用free释放空间

如果是二级空间配置器，对应找到这个函数

xxxxxxxxxx
14
1
static void deallocate(void *__p, size_t __n) //__p就是某个内存节点的首地址，__n就是要回收的内存块大小
2
{
3
    if (__n > 128)
4
        malloc_alloc::deallocate(__p, __n); // 底层还是free
5
    else {
6
        // 假设回收32字节，这一步就是定位到数组中下标3位置
7
        _Obj **__my_free_list = _S_free_list + _S_freelist_index(__n);
8
        _Obj *__q = (_Obj *)__p;
9

10
        // 其实是把刚刚用完的32个字节又挂接到链表的头上去了，就是一个还原的操作逻辑
11
        __q->_M_free_list_link = *__my_free_list;
12
        *__my_free_list = __q;
13
    }
14
}

通过deallocate的逻辑我们也能理解一件事情 —— 为什么刚才需要72字节空间时要往上借到96字节，而不是往下借（比如更近的2 * 64，借两块）

因为这些链表中的内存块节点并不一定是连续的。虽然刚开始申请时是连续空间，但是用了一些内存块，又还了一些内存块后，链表连接的两块内存块就不一定连续了。

再看看构建对象的函数和销毁对象的函数

xxxxxxxxxx
12
1
template <class _Tp>
2
class allocator {
3
    void construct(pointer __p, const _Tp &__val) {
4
        // 定位new表达式，在指定的空间上构建对象
5
        new (__p) _Tp(__val);
6
    }
7

8
    void destroy(pointer __p) {
9
        // 调用析构
10
        __p->~_Tp();
11
    }
12
};

总结函数的功能：

1. _S_freelist_index函数的作用在自由链表中取下标

2. _S_round_up函数的作用向上取整，得到8的整数倍

3. allocate对外是申请空间的函数，但是底层会调用_S_refill，但是_S_refill也不会申请空间，该函数会调用_S_chunk_alloc函数。

4. _S_chunk_alloc函数才是真正的申请空间的函数，并且该函数有可能会造成调用，会将其中的一部分返回给_S_refill，另外一部分会交给内存中的两个指针_S_start_free与_S_end_free，以备下一次申请的时候使用

5. _S_refill函数会将_S_chunk_alloc函数返回的空间进行切割，会切割成多个等分，并接在对应的自由链表的下面。