Extra Cookie

Yet Another Programmer's Blog

STL 源码分析-A.万物起源-3

上一篇提到过,第二级 alloc 在分配大于 128 bytes 的时候,直接使用第一级 alloc,如果小于 128 bytes 才采用内存池的方式进行内存分配。

分配过程是这样的,每次分配一大块内存,存到一个 free list 中,下次 client 若再有相同大小的内存要求,就直接从这个 free list 中划出,内存释放时,则直接回收到对应的 list 中。为了管理的方便,实际分配的大小都被调整为 8 的倍数,所以有 16 个 free lists,分别为 8, 16, 24, 32, 40, 48, 56, 64, 72, 80, 88, 96, 104, 112, 120, 128 bytes。例如需要 20 bytes,将会被自动调整为 24 bytes。free lists 的结构如下

1
2
3
4
5
6
7
8
9
10
11
enum {_ALIGN = 8};
enum {_MAX_BYTES = 128};
enum {_NFREELISTS = 16}; // _MAX_BYTES/_ALIGN

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

private:
    static _Obj* __STL_VOLATILE _S_free_list[_NFREELISTS];

为了节省内存使用,使用 union 结构,这个设计很巧妙,每一个元素(内存区域对象)即可以当作下一个元素的指针,例如后面代码中的 result -> _M_free_list_link,也可以当作该元素的值,例如 *__my_free_list。整个 free lists 的结构便是一串使用后者的元素构成的节点,每个节点的值是使用前者构成的单向链表的首地址。

首先来看 allocate 的过程

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
  static void* allocate(size_t __n)
  {
    void* __ret = 0;
    // 还记得上篇中的 “typedef __malloc_alloc_template<0> malloc_alloc;” 吗?
    // 如果需分配的 size 大于 _MAX_BYTES(128) 时,采用第一级 alloc
    if (__n > (size_t) _MAX_BYTES) {
      __ret = malloc_alloc::allocate(__n);
    }
    else {
      // 获得 free lists 对应节点地址(首地址 + index)
      // _S_freelist_index(__n) 根据需要分配内存的 size 算出节点的 index,见下
      _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)
        // 如果该节点对应的可用区域分配的单向链表为空,则需要重新填充空间
        // _S_round_up(__n) 对内存分配 size 进行 8 倍圆整,见下
        __ret = _S_refill(_S_round_up(__n));
      else {
        // 如果该节点对应可用区域存在,则调整单向链表,取链首元素
        *__my_free_list = __result -> _M_free_list_link;
        __ret = __result;
      }
    }

    return __ret;
  };

  static  size_t _S_freelist_index(size_t __bytes) {
        return (((__bytes) + (size_t)_ALIGN-1)/(size_t)_ALIGN - 1);
  }

  static size_t
  _S_round_up(size_t __bytes)
    { return (((__bytes) + (size_t) _ALIGN-1) & ~((size_t) _ALIGN - 1)); }

上面解决了 free list 节点已经存在可用区域(即链表不为空)的情况下内存的分配问题,那么当不存在可用区域的时候该如何处理呢?也就是说到底 _S_refill() 做了什么?

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
/* Returns an object of size __n, and optionally adds to size __n free list.*/
// 传入参数必需是 8 倍数圆整之后的
/* We assume that __n is properly aligned.                                */
/* We hold the allocation lock.                                         */
template
void*
__default_alloc_template <__threads , __inst>::_S_refill(size_t __n)
{
    // 设定一次性分配内存区域个数
    int __nobjs = 20;
    // 分配 __nohjs 个 size 是 __n 的内存区域给 free lists 节点,见下
    // _S_chunk_alloc() 维护内存池,内存分配先从内存池中分配,如不够,再通过 malloc 分配
    char* __chunk = _S_chunk_alloc(__n, __nobjs);
    _Obj* __STL_VOLATILE* __my_free_list;
    _Obj* __result;
    _Obj* __current_obj;
    _Obj* __next_obj;
    int __i;
    // 如果只是分配出一个区域,直接返回给 client 使用
    if (1 == __nobjs) return(__chunk);
    // 获得节点地址
    __my_free_list = _S_free_list + _S_freelist_index(__n);

    /* Build free list in chunk */
      // 作为分配出来的第一个元素传回给 client 使用
      __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) {
            // 直到最后一个元素,_M_free_list_link 置为 NULL
            __current_obj -> _M_free_list_link = 0;
            break;
        } else {
            __current_obj -> _M_free_list_link = __next_obj;
        }
      }
    return(__result);
}

/* We allocate memory in large chunks in order to avoid fragmenting     */
/* the malloc heap too much.                                            */
/* We assume that size is properly aligned.                             */
/* We hold the allocation lock.                                         */
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;

    // 如果剩余空间满足需求,直接从 chunk 中分配
    // _S_start_free 指向 chunk 空闲位置
    if (__bytes_left >= __total_bytes) {
        __result = _S_start_free;
        _S_start_free += __total_bytes;
        return(__result);
    // 剩余空间不满足需求,但至少可用分配一个(含一个)区域以上
    // 直接从 chunk 中分配,并更改分配区域个数
    } else if (__bytes_left >= __size) {
        __nobjs = (int)(__bytes_left/__size);
        __total_bytes = __size * __nobjs;
        __result = _S_start_free;
        _S_start_free += __total_bytes;
        return(__result);
    } else {
        // 如果连一个区域也无法分配
        // 设置需要 malloc() 分配内存空间大小,为需求的两倍,再加上附加值
        // _S_heap_size 是每一次 __bytes_to_get 的累加值
        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) {
            // 将 chunk 中剩余的空间分配给对应的节点
            // 因为剩余空间小于需求,所以直接分配给跟剩余空间大小相符的节点
            _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;
        }
        // 通过 malloc 分配
        _S_start_free = (char*)malloc(__bytes_to_get);
        // 如果 heap 空间不够导致 malloc 失败
        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.
            // 从需要分配的节点开始,依次遍历所有的节点,找到有未用区域的
            // 将其作为 chunk 的空闲区域,然后再次调用本函数进行分配
            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;
                    // 置为 chunk 的空闲区域
                    _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.
                }
            }
            // 如果执行到这里,也就意味着最后的努力也以失败告终
	        _S_end_free = 0;	// In case of exception.
            // 使用第一级 alloc 进行分配,因为其实第一级 alloc 也是调用 malloc()
            // 所以只是试试看内存分配失败处理函数或者抛出异常说不定有用或者内存使用得到缓解
            _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;
        // 重新进行分配,因为已经通过 malloc() 分配到了内存
        return(_S_chunk_alloc(__size, __nobjs));
    }
}

reallocate 只是先调用 allocate 分配新实体,然后拷贝老实体的值到新实体,然后释放老实体,就不再赘述。最后是 deallocate

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
  /* __p may not be 0 */
  static void deallocate(void* __p, size_t __n)
  {
    // 同 allocate,大于 128 时使用第一级 alloc
    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 */
      // 调整链表,将 __p 插入链首,同时更改节点值(指向链表)
      __q -> _M_free_list_link = *__my_free_list;
      *__my_free_list = __q;
      // lock is released here
    }
  }

Comments