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
280
281
282
283
284
285
286
287
288
289
290
291
292
293
294
295
296
297
298
299
300
301
302
303
304
305
306
307
308
309
310
311
312
313
314
315
316
317
318
319
320
321
322
323
324
325
326
327
328
329
330
331
332
333
334
335
336
337
338
339
340
341
342
343
344
345
346
347
348
349
350
351
352
353
354
355
356
357
358
359
360
361
362
363
364
365
366
367
368
369
370
371
372
373
374
375
376
377
378
379
380
381
382
383
384
385
386
387
388
389
390
391
392
393
394
395
396
397
398
399
400
401
402
403
404
405
406
407
408
409
410
411
412
413
414
415
416
417
418
419
420
421
422
423
424
425
426
427
428
429
430
431
432
433
434
435
436
437
438
439
440
441
442
443
444
445
446
447
448
449
450
451
452
453
454
455
456
457
458
459
460
461
462
463
464
|
static void *
_int_malloc (mstate av, size_t bytes)
{
INTERNAL_SIZE_T nb; /* 请求的chunk_size */
unsigned int idx; /* 对应bin数组中的index */
mbinptr bin; /* 指向对应bin的指针 */
mchunkptr victim; /* 指向分配的chunk */
INTERNAL_SIZE_T size; /* 分配的chunk的size */
int victim_index; /* 分配的chunk的bin的index */
mchunkptr remainder; /* 指向分割后剩下的那块chunk */
unsigned long remainder_size; /* 分割后剩下的那块chunk的size */
unsigned int block; /* bit map traverser */
unsigned int bit; /* bit map traverser */
unsigned int map; /* 一个block值 */
mchunkptr fwd; /* 用于链表操作 */
mchunkptr bck; /* 用于链表操作 */
const char *errstr = NULL; /* 报错字符串指针 */
checked_request2size (bytes, nb); /* 计算chunk_size */
if (__glibc_unlikely (av == NULL))
{
//无可用的分配区,使用sysmalloc获取内存
void *p = sysmalloc (nb, av);
if (p != NULL)
alloc_perturb (p, bytes); //对数据用memset进行处理
return p;
}
if ((unsigned long) (nb) <= (unsigned long) (get_max_fast ()))
{
//要分配的chunk大小小于global_max_fast则先从fastbin中寻找
idx = fastbin_index (nb); //通过size获取在fastbin中对应的index
mfastbinptr *fb = &fastbin (av, idx); //通过index获取分配区的fastbin中对应的bin
mchunkptr pp = *fb; //获取bin的首个chunk
do
{
victim = pp;
if (victim == NULL)
break;
} while ((pp = catomic_compare_and_exchange_val_acq (fb, victim->fd, victim)) != victim);
//将头指针的下一个chunk作为空闲chunk链表的头部,这里使用lock‑free的技术实现.Lock‑free算法的基础是CAS(Compare‑and‑Swap)原子操作.避免了ABA问题
//此时victim是该fb原来的首个chunk,或者为0
if (victim != 0)
{
//存在可使用的fastbin chunk
if (__builtin_expect (fastbin_index (chunksize (victim)) != idx, 0))
{
//检测该chunk的size是否符合该bin的index
errstr = "malloc(): memory corruption (fast)";
errout:
malloc_printerr (check_action, errstr, chunk2mem (victim), av);
return NULL;
}
check_remalloced_chunk (av, victim, nb);
/*
#if !MALLOC_DEBUG
# define check_chunk(A, P)
# define check_free_chunk(A, P)
# define check_inuse_chunk(A, P)
# define check_remalloced_chunk(A, P, N)
# define check_malloced_chunk(A, P, N)
# define check_malloc_state(A)
非debug模式下这些宏定义为空
*/
void *p = chunk2mem (victim); //将chunk指针转化为mem指针,即指向data区域
alloc_perturb (p, bytes);
/*
# define __glibc_unlikely(cond) (cond)
static int perturb_byte;
static void alloc_perturb (char *p, size_t n) {
if (__glibc_unlikely (perturb_byte))
memset (p, perturb_byte ^ 0xff, n);
}
该函数配合calloc使用
*/
return p; //将分配出来的mem指针返回
}
}
//victim为0说明对应fastbin无空闲chunk,继续进行分配
if (in_smallbin_range (nb))
{
//所需的chunk大小属于smallbin
idx = smallbin_index (nb);
bin = bin_at (av, idx); //根据index获得对应smallbin的表头
if ((victim = last (bin)) != bin)
{
//victim赋值为表尾,如果该表不为空
if (victim == 0)
//victim为0,表示smallbin还没有初始化为双向循环链表,调用malloc_consolidate函数,此时由于global_max_fast也未初始化,所以会调用malloc_init_state初始化
malloc_consolidate (av);
else
{
bck = victim->bk;
if (__glibc_unlikely (bck->fd != victim))
{
//双向链表检测,last(bin)->bk->fd == last(bin)
errstr = "malloc(): smallbin double linked list corrupted";
goto errout;
}
set_inuse_bit_at_offset (victim, nb); //设置inuse标志
bin->bk = bck;
bck->fd = bin; //将victim从smallbin的双向循环链表中取出
if (av != &main_arena)
//如果是非主分配区,将标志bit清零
victim->size |= NON_MAIN_ARENA;
check_malloced_chunk (av, victim, nb);
void *p = chunk2mem (victim);
alloc_perturb (p, bytes);
return p; //同上,正常的分配流程
}
}
//该表为空则继续分配
}
else
{
//所需的chunk大小属于largebin
idx = largebin_index (nb);
if (have_fastchunks (av))
//调用malloc_consolidate()函数合并fastbin chunk,并将这些空闲chunk加入unsorted_bin中
malloc_consolidate (av);
}
for (;;)
{
int iters = 0;
while ((victim = unsorted_chunks (av)->bk) != unsorted_chunks (av))
{
//反向遍历unsorted_bin,遍历结束的条件是unsorted_bin为空
//victim是unsorted_bin中最后一个chunk
bck = victim->bk; //bck是unsorted_bin中倒数第二个chunk
if (__builtin_expect (victim->size <= 2 * SIZE_SZ, 0)
|| __builtin_expect (victim->size > av->system_mem, 0))
//chunk的大小不能小于等于2 * SIZE_SZ,也不能超过该分配区总的内存分配量
malloc_printerr (check_action, "malloc(): memory corruption", chunk2mem (victim), av);
size = chunksize (victim); //获取最后一个chunk的size
if (in_smallbin_range (nb)
&& bck == unsorted_chunks (av)
&& victim == av->last_remainder
&& (unsigned long) (size) > (unsigned long) (nb + MINSIZE))
{
//如果请求的chunk大小为smallbin范围,且unsorted_bin中只有一个last_remainder chunk,且其大小大于所需chunk的大小加上MINSIZE
remainder_size = size - nb; //计算切分后剩余chunk的size
remainder = chunk_at_offset (victim, nb); //计算切分后剩余chunk的地址
unsorted_chunks (av)->bk = unsorted_chunks (av)->fd = remainder; //将切分后剩余的chunk放入unsorted_bin
av->last_remainder = remainder; //设置为last_remainder chunk
remainder->bk = remainder->fd = unsorted_chunks (av); //设置last_remainder chunk的bk和fd
if (!in_smallbin_range (remainder_size))
{
//若剩下的chunk属于largebin chunk,将其fd_nextsize和bk_nextsize设置为NULL
remainder->fd_nextsize = NULL;
remainder->bk_nextsize = NULL;
}
set_head (victim, nb | PREV_INUSE | (av != &main_arena ? NON_MAIN_ARENA : 0));
//设置头部(addr + 0x8),包括大小和标志位,由于临近的前一个chunk一定位于使用中,所以PREV_INUSE为1
set_head (remainder, remainder_size | PREV_INUSE);
//同理,由于victim会被分配给用户,所以PREV_INUSE为1
set_foot (remainder, remainder_size);
//该chunk不在使用中,使用set_foot对该chunk的inuse标志位置零
check_malloced_chunk (av, victim, nb);
void *p = chunk2mem (victim);
alloc_perturb (p, bytes);
return p; //同上,正常的分配流程
}
unsorted_chunks (av)->bk = bck;
bck->fd = unsorted_chunks (av); //不满足上述情况则将该chunk从unsorted_bin链表中取出
if (size == nb)
{
//victim大小与所需的chunk大小一致
set_inuse_bit_at_offset (victim, size); //对victim的inuse标志位置零
if (av != &main_arena)
//不属于主分配区则对对应的标志位置零
victim->size |= NON_MAIN_ARENA;
check_malloced_chunk (av, victim, nb);
void *p = chunk2mem (victim);
alloc_perturb (p, bytes);
return p; //同上,正常的分配流程
}
//到这说明该victim会放入对应的bin链表
if (in_smallbin_range (size))
{
//victim属于smallbin
victim_index = smallbin_index (size); //获得所属smallbin的index
bck = bin_at (av, victim_index); //将该smallbin的链表表头赋值给bck
fwd = bck->fd; //该smallbin第一个chunk赋值给fwd
//victim会插入到bck和fwd之间,作为该smallbin链表的第一个chunk.
}
else
{
//victim属于largebin
victim_index = largebin_index (size); //获得所属largebin的index
bck = bin_at (av, victim_index); //将该largebin的链表表头赋值给bck
fwd = bck->fd; //该largebin第一个chunk赋值给fwd
if (fwd != bck)
{
//该largebin中有空闲chunk存在
size |= PREV_INUSE; //将当前chunk的size的inuse标志bit置位,便于加快chunk大小的比较
assert ((bck->bk->size & NON_MAIN_ARENA) == 0);
//断言该largebin最后一个chunk的size字段中的非主分配区的标志bit没有置位
if ((unsigned long) (size) < (unsigned long) (bck->bk->size))
{
//当前chunk比最后一个chunk小,就插入到该largebin的链表的最后
fwd = bck;
bck = bck->bk;
victim->fd_nextsize = fwd->fd;
victim->bk_nextsize = fwd->fd->bk_nextsize;
fwd->fd->bk_nextsize = victim->bk_nextsize->fd_nextsize = victim;
//将victim插入chunk size链表的尾部,该链表是从大到小排列的
}
else
{
assert ((fwd->size & NON_MAIN_ARENA) == 0);
//断言该largebin第一个chunk的size字段中的非主分配区的标志bit没有置位
while ((unsigned long) size < fwd->size)
{
//正向遍历chunk size链表,直到找到第一个小于等于当前chunk大小的chunk
fwd = fwd->fd_nextsize;
assert ((fwd->size & NON_MAIN_ARENA) == 0);
}
if ((unsigned long) size == (unsigned long) fwd->size)
//同一大小的chunk已经存在,则不需要修改chunk size链表,当前chunk插入fwd之后
fwd = fwd->fd;
else
{
//当前chunk大于fwd,则将当前chunk作为该chunk size的代表加入chunk size链表,位置为fwd的前面
victim->fd_nextsize = fwd;
victim->bk_nextsize = fwd->bk_nextsize;
fwd->bk_nextsize = victim;
victim->bk_nextsize->fd_nextsize = victim;
}
bck = fwd->bk;
}
}
else
//如果largebin中没有chunk,直接将当前chunk加入chunk size链表,chunk size链表表头位于第一个chunk的fd_nextsize和bk_nextsize,所以第一个chunk是最大的
victim->fd_nextsize = victim->bk_nextsize = victim;
}
mark_bin (av, victim_index); //将对应map里该index对应的标志位置1
victim->bk = bck;
victim->fd = fwd;
fwd->bk = victim;
bck->fd = victim; //将当前chunk插入到对应bin中
#define MAX_ITERS 10000
if (++iters >= MAX_ITERS)
//如果unsorted_bin中的chunk超过了10000个,最多遍历10000个就退出
break;
}
//此时unsorted_bin链表已经处理完成
if (!in_smallbin_range (nb))
{
//所需分配的chunk大小为largebin
bin = bin_at (av, idx); //获取对应的bin
if ((victim = first (bin)) != bin
&& (unsigned long) (victim->size) >= (unsigned long) (nb))
{
//如果largebin链表不为空且链表中最大的chunk大于所需chunk的大小,则遍历该largebin链表,找到合适的chunk
victim = victim->bk_nextsize; //从最后一个也就是最小一个开始遍历
while (((unsigned long) (size = chunksize (victim)) < (unsigned long) (nb)))
//反向遍历chunk size链表,直到找到第一个大于等于所需chunk大小的chunk退出循环
victim = victim->bk_nextsize;
if (victim != last (bin) && victim->size == victim->fd->size)
//如果victim不是链表中的最后一个chunk且与victim大小相同的chunk不止一个,意味着victim为chunk size链表中的节点,取victim->fd节点对应的chunk作为候选chunk
victim = victim->fd;
remainder_size = size - nb; //由于size可能大于所需的chunk,所以要计算看是否要划分
unlink (av, victim, bck, fwd); //调用unlink宏函数将victim从largebin链表中取出
if (remainder_size < MINSIZE)
{
//如果将victim切分后剩余大小小于MINSIZE,则将整个victim返回,实际分配的chunk比所需的chunk要大一些
set_inuse_bit_at_offset (victim, size);
if (av != &main_arena)
victim->size |= NON_MAIN_ARENA;
}
else
{
//从victim中切分出所需的chunk,剩余部分作为一个新的chunk加入到unsorted_bin,其他处理与前面类似
remainder = chunk_at_offset (victim, nb);
bck = unsorted_chunks (av);
fwd = bck->fd;
if (__glibc_unlikely (fwd->bk != bck))
{
//验证第一个chunk的bk
errstr = "malloc(): corrupted unsorted chunks";
goto errout;
}
remainder->bk = bck;
remainder->fd = fwd;
bck->fd = remainder;
fwd->bk = remainder; //将remainder插入为unsorted_bin的第一个chunk
if (!in_smallbin_range (remainder_size))
{
//若剩下的chunk属于largebin chunk,将该chunk的fd_nextsize和bk_nextsize设置为NULL
remainder->fd_nextsize = NULL;
remainder->bk_nextsize = NULL;
}
set_head (victim, nb | PREV_INUSE | (av != &main_arena ? NON_MAIN_ARENA : 0));
set_head (remainder, remainder_size | PREV_INUSE);
set_foot (remainder, remainder_size); //划分后设置,同上
}
check_malloced_chunk (av, victim, nb);
void *p = chunk2mem (victim);
alloc_perturb (p, bytes);
return p; //返回chunk过程,同上
}
}
//从最合适的smallbin或largebin中都没有分配到需要的chunk,则查看比当前bin的index大的smallbin或largebin是否有空闲chunk可利用来分配所需的chunk
++idx;
bin = bin_at (av, idx); //获取下一个相邻bin的空闲chunk链表
block = idx2block (idx);
map = av->binmap[block];
bit = idx2bit (idx);
//获取该bin对于binmap中的bit位的值,使用binmap可以加快查找bin是否包含空闲chunk,idx2bit宏将idx指定的位设置为1,其它位清零
for (;;)
{
if (bit > map || bit == 0)
{
//map为0即该block所对应的所有bins中都没有空闲chunk.于是遍历binmap的下一个block,直到找到一个不为0的block或者遍历完所有的block
do
{
if (++block >= BINMAPSIZE) //遍历完所有的block都没有则使用top chunk分配
goto use_top;
} while ((map = av->binmap[block]) == 0);
bin = bin_at (av, (block << BINMAPSHIFT));
bit = 1;
}
while ((bit & map) == 0)
{
//在一个block遍历对应的bin直到找到一个bit不为0退出遍历
bin = next_bin (bin);
bit <<= 1;
assert (bit != 0);
}
victim = last (bin); //将bin链表中的最后一个chunk赋值给victim
if (victim == bin)
{
//victim与bin链表头指针相同,表示该bin中没有空闲chunk,binmap中的相应位设置不准确,将binmap的相应bit位清零,获取当前bin下一个bin,将bit移到下一个bit位,即乘以2
av->binmap[block] = map &= ~bit;
bin = next_bin (bin);
bit <<= 1;
}
else
{
//当前bin中的最后一个chunk满足要求,获取该chunk的大小,计算切分出所需chunk后剩余部分的大小,然后将victim从bin的链表中取出
size = chunksize (victim);
assert ((unsigned long) (size) >= (unsigned long) (nb));
remainder_size = size - nb;
unlink (av, victim, bck, fwd);
if (remainder_size < MINSIZE)
{
set_inuse_bit_at_offset (victim, size);
if (av != &main_arena)
victim->size |= NON_MAIN_ARENA;
}
else
{
remainder = chunk_at_offset (victim, nb);
bck = unsorted_chunks (av);
fwd = bck->fd;
if (__glibc_unlikely (fwd->bk != bck))
{
errstr = "malloc(): corrupted unsorted chunks 2";
goto errout;
}
remainder->bk = bck;
remainder->fd = fwd;
bck->fd = remainder;
fwd->bk = remainder;
if (in_smallbin_range (nb))
//剩余部分chunk属于smallbin,将分配区的last_remainder chunk设置为剩余部分构成的chunk
av->last_remainder = remainder;
if (!in_smallbin_range (remainder_size))
{
remainder->fd_nextsize = NULL;
remainder->bk_nextsize = NULL;
}
set_head (victim, nb | PREV_INUSE | (av != &main_arena ? NON_MAIN_ARENA : 0));
set_head (remainder, remainder_size | PREV_INUSE);
set_foot (remainder, remainder_size);
}
check_malloced_chunk (av, victim, nb);
void *p = chunk2mem (victim);
alloc_perturb (p, bytes);
return p;
}
}
use_top:
//从top chunk中分配所需chunk
victim = av->top;
size = chunksize (victim);
//将当前分配区的top chunk赋值给victim,并获得victim的大小
if ((unsigned long) (size) >= (unsigned long) (nb + MINSIZE))
{
//top chunk切分出所需chunk后还需要MINSIZE的空间来作为fencepost
//切分后的剩余部分将作为新的top chunk,原top chunk的fencepost仍然作为新的top chunk的fencepost,所以切分之后剩余的chunk不用set_foot
remainder_size = size - nb;
remainder = chunk_at_offset (victim, nb);
av->top = remainder;
set_head (victim, nb | PREV_INUSE | (av != &main_arena ? NON_MAIN_ARENA : 0));
set_head (remainder, remainder_size | PREV_INUSE);
check_malloced_chunk (av, victim, nb);
void *p = chunk2mem (victim);
alloc_perturb (p, bytes);
return p;
}
else if (have_fastchunks (av))
{
//如果top chunk也不能满足要求,查看fastbin中是否有空闲chunk存在,因为free属于fastbin的chunk时不需要获得分配区的锁,调用malloc_consolidate函数并重新设置当前bin的index,再次循环
malloc_consolidate (av);
if (in_smallbin_range (nb))
idx = smallbin_index (nb);
else
idx = largebin_index (nb);
}
else
{
//如果fastbin中没有空闲chunk存在,向系统申请内存
void *p = sysmalloc (nb, av);
if (p != NULL)
alloc_perturb (p, bytes);
return p;
}
}
}
|
