malloc

Cookie占用8个字节，所需大小比较小的话，Cookie占用的比率就比较大，造成了浪费。

各版本 allocator 实现方式;

G2.9 容器使用的分配器，不是std::allocator 而是 std::alloc。而在G4.9里 std::alloc 变为 __pool_alloc。

而pool allocator的思想是，对于相同大小的元素/同一类型的元素放到一整块内存中，每次只malloc这一整块内存，容器在为每个元素申请内存时只需要在申请的一整块大的内存中分割一小块即可。这一小块中不需要包含上述的cookie信息，因此就节省了很多不需要的额外内存。

std::alloc原理

一般常见的内存池是为一个类维护一个内存池，说是一个类，其实它的限制并没有那么的严谨，应该说是为了一种大小的子空间维护一个内存池，也就是说，只要每次分配的内存空间的大小相同(如容器)，那么就可以使用同一个内存池为其分配内存。

std::alloc就是使用了这种思想，他并不是分散的维护一个一个的小的内存池，而是维护一个内存池的链表(长度为16)，间隔8byte的维护16种不同大小的内存池。如下图所示:(图片来自侯捷C++内存分配课程讲义)

#0所对应的节点连接的链表负责分配大小为8byte的子空间
#3所对应的节点连接的链表负责分配大小为32byte的子空间
以此以8byte的间隔向后类推
#15所对应的节点连接的链表负责分配大小为128byte的子空间

当需要一次性分配的内存超过了128byte，std::alloc()本身就不会为其服务，而会将这个需求转给malloc去处理。

可是用户申请分配的空间可能并不会正好是8的倍数(通常都不是)，这时，就会把他提升至最近的长度，并为其分配对应大小的内存块。

同时，在每一次需要调用malloc去分配内存时，std::alloc通常会分配比指定的大小更大的内存(至少为要求的20 * 2 倍)，其中一半的作为当前的内存块进行分割并交付，剩下的将会被储存至pool。

而当我们归还内存时，也是将他连接到对应大小的内存队列头部，如果超过了128byte，也会被转交给其他函数。

最初的时候，std::alloc()会创建一个链表(代码中的free_list)，并将初始值都设置为0，以后将用他们去维护16个子块大小不同的内存池(间隔为8byte)。

当我们第一次申请分配内存时，由于pool为空，所以会调用malloc去分配内存。这里假设需求的内存是32byte，那么就会调用malloc申请为pool分配32 * 20 * 2 + RoundUp = 1280的内存，然后将其中的32 * 20 的内存分割成20块，连接在#3上，并将其中的第一块交付。

RoundUp = 已经分配过的内存大小的总和 / 16；（经验值，不知理论依据）

此时pool中还剩余有640的内存

此时，我们再次申请分配64byte的内存，这时由于pool中有内存，且大于所需分配的内存，那么就在pool中切割出尽量多的子块(大小为需要的64byte)，然后将第一块交付，将剩下的挂载在#7的队列上。

此时pool的剩余内存为0，下次在需要分配内存时，又会需要调用malloc去进行分配.

下边几张图片的行为和上面的行为相同：

七：这一步再次申请分配8byte大小的内存，同样切割pool，交付，连接。结束之后，pool中剩余内存为80byte。

这里再次申请了104byte的内存，但是pool中剩余的大小为80byte，不足以为其划分，于是者80byte的内存就被当成了内存碎片，由于其大小对应于#9链表，所以将他挂载到了#9链表下，然后再次调用malloc重新分配pool。

这里，我们申请72byte大小的空间，但是#8上边并未挂在内存块，pool中的大小为24也不足以分配一个空间，malloc在我们的假设中也调用失败。
于是编辑器就将pool中原有的24byte视为内存碎片，挂载到#2中。之后从#8链表开始向后寻找最近的挂在有内存块的链表，在这里是#9，取出其中的第一块，将其视为pool进行分割、交付、挂载。

问题分析

上边的流程结束之后，存在有很明显的问题：

首先，当他判定没有内存可分配从而结束程序时，至少两块的内存是可以分配的：

1、在alloc所掌握的内存中，还有很多的内存块没有被使用，只不过这些内存块的大小都小于所需要分配的内存，如果将他们拼接起来说不定足够为这次请求分配空间。

那为什么不这么做呢？答案很简单，代价太高。由于在这个架构里，多次分配、归还之后，每个链表上连接的空内存块可能并不是在物理上相邻的，但是我们要写数据需要的是物理上相连的内存，但是我们在这些内存块中去搜索物理相连的内存的难度又太大，所以并没有这么做。

2、由于每次调用malloc都会分配很多的内存，但是我们所真正需要的仅仅是其中的一小部分，那可以减少malloc所要求的内存，这样很多情况下都可以获得一块足够大的内存。

这个架构同样没有这么做，其原因在于，处于多进程的运行环境下，OS可能不仅仅跑了当前这一个程序，如果采用2的办法，我们虽然可以获取内存，但是我们也很可能完全占用OS的全部内存，那么其他的运行程序就会崩溃。ps：我个人理解中，RoundUp之所以调整的这么大，有可能与这一点也有关

其次，回收的内存并没有还给OS
正如之前的文章中描述的那样，将如此琐碎的内存还给OS是一件非常困难的事情，所以alloc中也并没有这样做。

源码

// author : Hou Jie (侯捷)
// date : 2015/11/11 
// compiler : DevC++ 5.61 (MinGW with GNU 4.9.2)
//
// 說明：這是侯捷 E-learning video "C++內存管理" 的實例程式.
//
// filename : allocc.h
// 取材自 SGI STL 2.91 <stl_alloc.h>, 移植至 C language.


#include <stdlib.h>  //for malloc(),realloc()
#include <stddef.h>  //for size_t
#include <memory.h>  //for memcpy()

//#define __THROW_BAD_ALLOC   cerr << "out of memory" << endl; exit(1)
#define __THROW_BAD_ALLOC   exit(1)

//----------------------------------------------
// 第1級配置器。
//----------------------------------------------

void (*oom_handler)() = 0;

void* oom_malloc(size_t n)
{
  void (*my_malloc_handler)();
  void* result;

  for (;;) {    //不斷嘗試釋放、配置、再釋放、再配置…
    my_malloc_handler = oom_handler;
    if (0 == my_malloc_handler) { __THROW_BAD_ALLOC; }
    (*my_malloc_handler)();    //呼叫處理常式，企圖釋放記憶體
    result = malloc(n);        //再次嘗試配置記憶體
    if (result) return(result);
  }
}

void* oom_realloc(void *p, size_t n)
{
  void (*my_malloc_handler)();
  void* result;

  for (;;) {    //不斷嘗試釋放、配置、再釋放、再配置…
    my_malloc_handler = oom_handler;
    if (0 == my_malloc_handler) { __THROW_BAD_ALLOC; }
    (*my_malloc_handler)();    //呼叫處理常式，企圖釋放記憶體。
    result = realloc(p, n);    //再次嘗試配置記憶體。
    if (result) return(result);
  }
}

void* malloc_allocate(size_t n)
{
  void *result = malloc(n);   //直接使用 malloc()
  if (0 == result) result = oom_malloc(n);
  return result;
}

void malloc_deallocate(void* p, size_t n)
{
  free(p);  //直接使用 free()
}

void* malloc_reallocate(void *p, size_t old_sz, size_t new_sz)
{
  void* result = realloc(p, new_sz); //直接使用 realloc()
  if (0 == result) result = oom_realloc(p, new_sz);
  return result;
}

void (*set_malloc_handler(void (*f)()))()
{ //類似 C++ 的 set_new_handler().
  void (*old)() = oom_handler;
  oom_handler = f;
  return(old);
}

//----------------------------------------------
//第二級配置器
//----------------------------------------------

enum {__ALIGN = 8};                        //小區塊的上調邊界
enum {__MAX_BYTES = 128};                  //小區塊的上限
enum {__NFREELISTS = __MAX_BYTES/__ALIGN}; //free-lists 個數

// union obj {                   //G291[o],CB5[x],VC6[x]
//   union obj* free_list_link;  //這麼寫在 VC6 和 CB5 中也可以，
// };                            //但以後就得使用 "union obj" 而不能只寫 "obj"
typedef struct __obj {
  struct __obj* free_list_link;
} obj;

char*   start_free = 0;
char*   end_free = 0;
size_t  heap_size = 0;
obj* free_list[__NFREELISTS]
     = {0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0 };


// 若bytes为13，则（13+7）&~（7）即 16
size_t ROUND_UP(size_t bytes) {
    return (((bytes) + __ALIGN-1) & ~(__ALIGN - 1));
}


// 计算多大的字节应该由几号链表来挂载
size_t FREELIST_INDEX(size_t bytes) {
    return (((bytes) + __ALIGN-1)/__ALIGN - 1);
}



//----------------------------------------------
// We allocate memory in large chunks in order to
// avoid fragmentingthe malloc heap too much.
// We assume that size is properly aligned.
//
// Allocates a chunk for nobjs of size "size".
// nobjs may be reduced if it is inconvenient to
// allocate the requested number.
//----------------------------------------------
//char* chunk_alloc(size_t size, int& nobjs)  //G291[o],VC6[x],CB5[x]
char* chunk_alloc(size_t size, int* nobjs)
{
  char* result;
  size_t total_bytes = size * (*nobjs);   //原 nobjs 改為 (*nobjs)
  size_t bytes_left = end_free - start_free;

  //  如果池子能不能满足20个
  if (bytes_left >= total_bytes) {
      result = start_free;
      start_free += total_bytes;
      return(result);
  } else if (bytes_left >= size) {        //  如果池子能不能满足1个
      *nobjs = bytes_left / size;         //原 nobjs 改為 (*nobjs)
      total_bytes = size * (*nobjs);      //原 nobjs 改為 (*nobjs)
      result = start_free;
      start_free += total_bytes;
      return(result);
  } else {    // 如果不能满足20个也不能满足1个
      size_t bytes_to_get =
                 2 * total_bytes + ROUND_UP(heap_size >> 4);  // 计算大小，处理碎片
      // Try to make use of the left-over piece.
      if (bytes_left > 0) {
          obj* volatile *my_free_list =
                 free_list + FREELIST_INDEX(bytes_left);

          ((obj*)start_free)->free_list_link = *my_free_list;
          *my_free_list = (obj*)start_free;
      }
      // 调用malloc 分配内存大小
      start_free = (char*)malloc(bytes_to_get);
      
      if (0 == start_free) {
          int i;
          obj* volatile *my_free_list, *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.
          for (i = size; i <= __MAX_BYTES; i += __ALIGN) {
              my_free_list = free_list + FREELIST_INDEX(i);
              p = *my_free_list;
              if (0 != p) {    //如果可用，拿出一块
                  *my_free_list = p -> free_list_link;
                  start_free = (char*)p;
                  end_free = start_free + i;
                  return(chunk_alloc(size, nobjs));
                  //Any leftover piece will eventually make it to the
                  //right free list.
              }
          }
          end_free = 0;       //In case of exception.
          start_free = (char*)malloc_allocate(bytes_to_get);
          //This should either throw an exception or
          //remedy the situation. Thus we assume it
          //succeeded.
      }
      // 如果成功，跳转到这里
      heap_size += bytes_to_get;
      end_free = start_free + bytes_to_get;
      return(chunk_alloc(size, nobjs));
  }
}
//----------------------------------------------
// Returns an object of size n, and optionally adds
// to size n free list. We assume that n is properly aligned.
// We hold the allocation lock.
//----------------------------------------------
void* refill(size_t n)
{
    int nobjs = 20;
    char* chunk = chunk_alloc(n,&nobjs);
    obj* volatile *my_free_list;   //obj** my_free_list;
    obj* result;
    obj* current_obj;
    obj* next_obj;
    int i;

    if (1 == nobjs) return(chunk);
    my_free_list = free_list + FREELIST_INDEX(n);

    //Build free list in chunk
    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) {
          current_obj->free_list_link = 0;
          break;
      } else {
          current_obj->free_list_link = next_obj;
      }
    }
    return(result);
}
//----------------------------------------------
//
//----------------------------------------------
void* allocate(size_t n)  //n must be > 0
{
  obj* volatile *my_free_list;    //obj** my_free_list;
  obj* result;

  // 如果 大于 就转交给  第一级来做
  if (n > (size_t)__MAX_BYTES) {
      return(malloc_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);
}
//----------------------------------------------
//缺点：
//    	1.只申请，没有还给操作系统
//		2.没有检查*p是否为alloc取得
//----------------------------------------------
void deallocate(void *p, size_t n)  //p may not be 0
{
  obj* q = (obj*)p;
  obj* volatile *my_free_list;   //obj** my_free_list;

  if (n > (size_t) __MAX_BYTES) {
      malloc_deallocate(p, n);
      return;
  }
  my_free_list = free_list + FREELIST_INDEX(n);
  q->free_list_link = *my_free_list;
  *my_free_list = q;
}
//----------------------------------------------
//
//----------------------------------------------
void* reallocate(void *p, size_t old_sz, size_t new_sz)
{
  void * result;
  size_t copy_sz;

  if (old_sz > (size_t) __MAX_BYTES && new_sz > (size_t) __MAX_BYTES) {
      return(realloc(p, new_sz));
  }
  if (ROUND_UP(old_sz) == ROUND_UP(new_sz)) return(p);
  result = allocate(new_sz);
  copy_sz = new_sz > old_sz? old_sz : new_sz;
  memcpy(result, p, copy_sz);
  deallocate(p, old_sz);
  return(result);
}
//----------------------------------------------

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
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
230
231
232
233
234
235
236
237
238
239
240
241
242
243
244
245
246
247
248
249
250
251
252
253
254
255
256
257
258
259
260
261
262
263
264
265
266
267
268
269
270
271
272
273
274
275
276
277
278
279

整理