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
|
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; /* current word of binmap */
mchunkptr fwd; /* 链表操作 */
mchunkptr bck; /* 链表操作 */
const char *errstr = NULL;
checked_request2size (bytes, nb); // 检查并将申请内存转换为适合内存分配的块大小
if (__glibc_unlikely (av == NULL)) // 没有可用arena即arena未初始化
{
void *p = sysmalloc (nb, av); // 通过sysmalloc系统调用从mmap获取堆块
if (p != NULL)
alloc_perturb (p, bytes); // 用memset清理空间数据
return p;
}
// 在fastbin大小内
if ((unsigned long)(nb) <= (unsigned long)(get_max_fast())) // global_max_fast:0x80
{
idx = fastbin_index(nb); // 获取fastbin中的索引，无任何检查，改global_max_fast可使idx极大
mfastbinptr *fb = &fastbin(av, idx);
// #define fastbin(ar_ptr, idx) ((ar_ptr)->fastbinsY[idx]) 即fb指向fastbin中对应的bin的地址
mchunkptr pp = *fb; // pp指向该对应fastbin中第一个chunk
do
{
victim = pp; // 取出第一个空闲chunk来分配 【victim】
if (victim == NULL) // fastbin中无chunk，跳出，去申请相应大小的smallbin
break;
// 等价于*fb = victim->fd, 链表头指向该空闲chunk的下一个chunk
} while ((pp = catomic_compare_and_exchange_val_acq(fb, victim->fd, victim)) != victim);
// # define catomic_compare_and_exchange_val_acq(mem, newval, oldval)
// CAS(Compareand-Swap)原子操作, 避免多线程的ABA问题
// 存在可使用的chunk
if (victim != 0)
{
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); // 对chunk标志位检查、是否是malloc_state所表示的分配区中的
// 检查是否已分配，是否重复分配和大小检查
void *p = chunk2mem(victim); // p 指向 chunk 的 fd 字段地址即data区域
alloc_perturb(p, bytes);
return p;
}
}
// 在 small bin 大小范围内
if (in_smallbin_range(nb))
{
idx = smallbin_index(nb); // 获取smallbin的下标索引
bin = bin_at(av, idx); // 取出对应的bin
if ((victim = last(bin)) != bin)
// #define last(b) ((b)->bk) 即 bin->bk != bin说明small bin非空
// 【victim为取出的表尾第一个chunk】
{
if (victim == 0) /* main_arena未初始化时victim为0，表示smallbin还未初始化为双向循环链表 */
malloc_consolidate(av); // 初始化
else
{
bck = victim->bk; // 取出victim之后的一个chunk检查
if (__glibc_unlikely(bck->fd != victim)) // 安全检查: 该chunk的fd应指回victim
{
errstr = "malloc(): smallbin double linked list corrupted";
goto errout;
}
set_inuse_bit_at_offset(victim, nb); // 设置物理相邻的下一个chunk inuse位, 表示victim被使用
// 使链表头 bin 与 bck 的bk与fd相互连接, 将 victim 脱离双向循环链表
bin->bk = bck;
bck->fd = bin;
if (av != &main_arena) // 若是非住分配区将标志位清零
victim->size |= NON_MAIN_ARENA; // 只有申请出的chunk才会置该位, bin中chunk不置位 0x4
check_malloced_chunk(av, victim, nb);
void *p = chunk2mem(victim); // p 指向 chunk 的 fd 字段地址
alloc_perturb(p, bytes);
return p;
}
}
}
// 否则在 large bin 范围中，先不查找而是对fastbin进行处理
else
{
idx = largebin_index(nb); // 获取largebin中索引
if (have_fastchunks(av)) // ((M)->flags & FASTCHUNKS_BIT) == 0 即是否已初始化main_arena
malloc_consolidate(av); // 对fastbin中所有chunk进行遍历、合并，将空闲chunk放入unsorted bin
}
// 在 unsorted bin中找，并将相应的bin按照大小放入small bin和large bin中
for (;;)
{
int iters = 0;
// 取unsorted bin中最后一个chunk victim, 反向遍历unsorted bin直到unsorted bin为空
while ((victim = unsorted_chunks(av)->bk) != unsorted_chunks(av))
{
bck = victim->bk; // victim的前一个chunk
if (__builtin_expect(victim->size <= 2 * SIZE_SZ, 0) ||
__builtin_expect(victim->size > av->system_mem, 0))
// 若小于0x10或大于arena管理的最大内存，报错
malloc_printerr(check_action, "malloc(): memory corruption",
chunk2mem(victim), av);
size = chunksize(victim); // 获取chunk大小
// 需要切割情况
if (in_smallbin_range(nb) && // 申请大小在small bin范围
bck == unsorted_chunks(av) && // unsorted bin中只有一个chunk victim
victim == av->last_remainder && // victim刚好是last_remainder
(unsigned long)(size) > (unsigned long)(nb + MINSIZE)) // victim大小 > 申请大小 + 0x20
{
remainder_size = size - nb;
remainder = chunk_at_offset(victim, nb); // 切出一个remainder_size的chunk
unsorted_chunks(av)->bk = unsorted_chunks(av)->fd = remainder; // 切出的chunk放入unsorted bin
av->last_remainder = remainder; // 设置新的remainder
remainder->bk = remainder->fd = unsorted_chunks(av); // 维护双向链表
if (!in_smallbin_range(remainder_size))
{ // 若是large bin则设置两个nextsize
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;
}
/* 不满足切割的条件，将 victim 从 unsorted bin 中取出 */
unsorted_chunks(av)->bk = bck;
bck->fd = unsorted_chunks(av);
if (size == nb) // 若victim大小刚好为用户申请的大小, 直接取出
{
set_inuse_bit_at_offset(victim, size);
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链表中，分别获得bck和fwd用于插入
// 若 victim 大小属于 small bin
if (in_smallbin_range(size))
{
victim_index = smallbin_index(size);
bck = bin_at(av, victim_index); // bck赋值为smallbin的链表表头
fwd = bck->fd; // fwd指向small bin第一个chunk，victim将插入到bck和fwd中作为第一个chunk
}
// 若 victim 大小属于 large bin
else
{
victim_index = largebin_index(size);
bck = bin_at(av, victim_index); // bck赋值为largebin的链表表头
fwd = bck->fd; // fwd指向large bin第一个chunk
if (fwd != bck) // large bin中非空，即其中有空闲chunk存在
{
size |= PREV_INUSE; // 当前chunk的size的inuse置位，便于加快chunk大小比较
assert((bck->bk->size & NON_MAIN_ARENA) == 0); // 多次判断确保NON_MAIN_ARENA为0，主线程
if ((unsigned long)(size) < (unsigned long)(bck->bk->size))
// fd一般指向比自己小的，bck的bk指向的是最小的size，此时victim为最小size
{
// 交换
fwd = bck; // fwd 指向 largebin 链表表头
bck = bck->bk; // bck 指向largebin中最小size的chunk
// 更新victim的2个nextsize，使得victim插入largebin的末尾
// fd_nextsize指向最大的chunk
victim->fd_nextsize = fwd->fd;
// bk_nextsize指向最大chunk的bk_nextsize, 即最小size的第一个chunk(因为最小chunk可能多个)
victim->bk_nextsize = fwd->fd->bk_nextsize;
fwd->fd->bk_nextsize = victim->bk_nextsize->fd_nextsize = victim; // 对应反向指
}
else // victim不为最小size
{
assert((fwd->size & NON_MAIN_ARENA) == 0);
// 遍历找到第一个小于等于victim size的chunk
while ((unsigned long)size < fwd->size)
{
fwd = fwd->fd_nextsize; // 不断遍历使得fwd->size非严格递减
assert((fwd->size & NON_MAIN_ARENA) == 0);
}
if ((unsigned long)size == (unsigned long)fwd->size)
fwd = fwd->fd; // 插入第二个位置，则不需要更新fd_nextsize和bk_nextsize
else
{ // 此时victim > fwd(同样大小第一个)，更新将victim插入fwd前
victim->fd_nextsize = fwd;
victim->bk_nextsize = fwd->bk_nextsize;
fwd->bk_nextsize = victim;
victim->bk_nextsize->fd_nextsize = victim;
}
bck = fwd->bk; // bck 更新为找到的fwd的上一个chunk
}
}
else // largebin 为空直接插入更新nextsize
victim->fd_nextsize = victim->bk_nextsize = victim;
}
// 统一维护fd和bk指针将victim插入bck和fwd中间
mark_bin(av, victim_index);
/*
#define mark_bin(m, i) ((m)->binmap[idx2block(i)] |= idx2bit(i))
将对应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) // 循环10000次处理unsorted bin中的chunk
break;
}
// 此时unsorted bin 链表已经处理完成，在 large bin 中查找
if (!in_smallbin_range(nb))
{
bin = bin_at(av, idx); // 对应large bin
if ((victim = first(bin)) != bin && // large bin不为空，victim设为largebin最大cunk
(unsigned long)(victim->size) >= (unsigned long)(nb)) // 申请大小小于最大chunk
{
victim = victim->bk_nextsize; // 最大chunk的bk_nextsize指向最小chunk, 此时victim最小
// 遍历找到比申请的nb大小小的最近的
while (((unsigned long)(size = chunksize(victim)) < (unsigned long)(nb)))
victim = victim->bk_nextsize; // 最小chunk的bk_nextsize的chunk size 不断变大
// victim有效 且 有至少两个size相同的chunk
if (victim != last(bin) && victim->size == victim->fd->size)
victim = victim->fd; // 再往下跳一步避免维护两个nextsize指针
// 分割
remainder_size = size - nb; // 不一定完全合适，计算remainder_size
unlink(av, victim, bck, fwd); // 将找到的victim 脱链
// 比MINSIZE还小则不能切割，将整个victim返回，实际分配的chunk比所需chunk大一些
if (remainder_size < MINSIZE)
{
set_inuse_bit_at_offset(victim, size); // 设置下一个chunk的prev_inuse
if (av != &main_arena)
victim->size |= NON_MAIN_ARENA; // 非主线程设置non_main_arena位
}
// 否则需要切割
else
{ // 从victim中切分出所需的chunk，剩余部分作为新chunk加入unsorted bin中
remainder = chunk_at_offset(victim, nb); // 剩余chunk
bck = unsorted_chunks(av); // 获取unsorted bin
fwd = bck->fd; // 指向 unsorted bin 第一个 chunk
if (__glibc_unlikely(fwd->bk != bck)) // 检测是否指针相互指向
{
errstr = "malloc(): corrupted unsorted chunks";
goto errout;
}
// 将remainder其放入unsorted bin中
remainder->bk = bck;
remainder->fd = fwd;
bck->fd = remainder;
fwd->bk = remainder;
if (!in_smallbin_range(remainder_size))
{
remainder->fd_nextsize = NULL;
remainder->bk_nextsize = NULL;
}
// 设置victim标志
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; // 从largebin中取出victim返回
}
}
++idx; // 正确的idx找不到chunk，加一看下一个索引:比当前binindex大的small/large bin 是否能找到chunk
bin = bin_at(av, idx);
block = idx2block(idx); // 将idx/32转移到binmap中的block, 32位一组block
// #define idx2block(i) ((i) >> BINMAPSHIFT)
// #define BINMAPSHIFT 5
map = av->binmap[block]; // binmap用于加速查找bin是否包含空闲chunk
bit = idx2bit(idx); // 将idx指定的位置1，其他位清零
// #define idx2bit(i) ((1U << ((i) & ((1U << BINMAPSHIFT) - 1))))
for (;;)
{
// 大于等于该bit位的位都未置1，表示该block没有可用的空闲chunk，需要搜索下一个block
if (bit > map || bit == 0)
{
do
{ // 加一换到下一组block
if (++block >= BINMAPSIZE) // 检查是否超过范围
goto use_top;
} while ((map = av->binmap[block]) == 0); // 直到找到一个不为0的block
bin = bin_at(av, (block << BINMAPSHIFT)); // block*32转换为bin的位置
bit = 1;
} // 可以确定有可用的chunk
while ((bit & map) == 0) // 与后为0则表明没有可用chunk
{ // 在一个block中遍历对应的bin直到找到一个bit不为0，退出遍历
bin = next_bin(bin); // 找下一个bin
bit <<= 1;
assert(bit != 0);
}
// 获取bin中的最后一个chunk victim
victim = last(bin);
if (victim == bin) // victim与bin链表头相同则说明bin中无空闲chunk，binmap设置有误
{
av->binmap[block] = map &= ~bit; // 将binmap的相应bit位清零
bin = next_bin(bin); // 获取下一个bin
bit <<= 1; // 将bit移到下一个bit位，即乘以2
}
else // bin中有空闲chunk，不为空，基本操作同之前
{
size = chunksize(victim); // 获取大小
/* We know the first chunk in this bin is big enough to use. */
assert((unsigned long)(size) >= (unsigned long)(nb));
remainder_size = size - nb; // 计算切分出所需chunk后剩余部分大小
unlink(av, victim, bck, fwd); // 从链表取出victim
// 无法切割
if (remainder_size < MINSIZE)
{
set_inuse_bit_at_offset(victim, size);
if (av != &main_arena)
victim->size |= NON_MAIN_ARENA;
}
else // 可以切割，将切割出的remainder放入unsored bin
{
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;
// 若剩余部分chunk属于smallbin，将分配区的last_remainder chunk设置为remainder
if (in_smallbin_range(nb))
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;
}
}
// 均找不到可用chunk, 则切top chunk
use_top:
victim = av->top;
size = chunksize(victim);
if ((unsigned long)(size) >= (unsigned long)(nb + MINSIZE))
{
remainder_size = size - nb; // 切割出remainder
remainder = chunk_at_offset(victim, nb);
av->top = remainder; // remainder成为新的top chunk
// 设置标志位
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; // 返回top chunk切割出的victim
}
else if (have_fastchunks(av)) // 看是否有fastchunk
{
malloc_consolidate(av); // 进一步处理fastchunk放入unsorted bin
if (in_smallbin_range(nb)) // 再重新赋值idx找
idx = smallbin_index(nb);
else
idx = largebin_index(nb);
}
else
{
void *p = sysmalloc(nb, av); // 系统调用sysmalloc向操作系统申请内存返回堆块
if (p != NULL)
alloc_perturb(p, bytes);
return p;
}
} // 分配不到则死循环，在其他线程中找，要么报错要么找到并返回
}
|
