Have fun with glibc内存管理

  • 使用的源码版本 glibc-2.24
  • 持续更新,治疗拖延症。

1.malloc 分析

​ malloc其实是调用了void *__libc_malloc (size_t bytes),但是这个函数实质是对static void *_int_malloc (mstate av, size_t bytes)的封装。

​ 分析开始,先来看void *__libc_malloc (size_t bytes)函数

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
void *__libc_malloc (size_t bytes)
{
mstate ar_ptr;
void *victim;
//首先检查是否存在内存分配的hook函数,如果有,就直接调用;hook函数主要
//是进程创建新线程的时候内存分配,或者支持用户提供的内存分配函数。
void *(*hook) (size_t, const void *)
= atomic_forced_read (__malloc_hook);
if (__builtin_expect (hook != NULL, 0))
return (*hook)(bytes, RETURN_ADDRESS (0));
arena_get (ar_ptr, bytes);
victim = _int_malloc (ar_ptr, bytes);
/* Retry with another arena only if we were able to find a usable arena
before. */
if (!victim && ar_ptr != NULL)
{
LIBC_PROBE (memory_malloc_retry, 1, bytes);
ar_ptr = arena_get_retry (ar_ptr, bytes);
victim = _int_malloc (ar_ptr, bytes);
}
//若分配成功,释放锁
if (ar_ptr != NULL)
(void) mutex_unlock (&ar_ptr->mutex);
assert (!victim || chunk_is_mmapped (mem2chunk (victim)) ||
ar_ptr == arena_for_chunk (mem2chunk (victim)));
return victim;
}

arena_get (ar_ptr, bytes)展开宏就是

1
2
3
4
#define arena_get(ptr, size) do { \
ptr = thread_arena; \
arena_lock (ptr, size); \
} while (0)

​ 获得分配区并加锁,之后就进入了主要负责内存分配的_int_malloc (ar_ptr, bytes)函数

​ 该函数代码特别长,只能一部分一部分看了,首先给出原型,函数有两个参数,即分配区和要分配的内存的大小(用户传进来的,并不是真正的要分配的大小)。

1.概述
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
static void *
_int_malloc (mstate av, size_t bytes) //分配区,大小
{
INTERNAL_SIZE_T nb; /* normalized request size */
unsigned int idx; /* associated bin index */
mbinptr bin; /* associated bin */
mchunkptr victim; /* inspected/selected chunk */
INTERNAL_SIZE_T size; /* its size */
int victim_index; /* its bin index */
mchunkptr remainder; /* remainder from a split */
unsigned long remainder_size; /* its size */
unsigned int block; /* bit map traverser */
unsigned int bit; /* bit map traverser */
unsigned int map; /* current word of binmap */
mchunkptr fwd; /* misc temp for linking */
mchunkptr bck; /* misc temp for linking */
const char *errstr = NULL;
/*
Convert request size to internal form by adding SIZE_SZ bytes
overhead plus possibly more to obtain necessary alignment and/or
to obtain a size of at least MINSIZE, the smallest allocatable
size. Also, checked_request2size traps (returning 0) request sizes
that are so large that they wrap around zero when padded and
aligned.
*/
checked_request2size (bytes, nb);
/* There are no usable arenas. Fall back to sysmalloc to get a chunk from
mmap. */
if (__glibc_unlikely (av == NULL))
{
void *p = sysmalloc (nb, av);
if (p != NULL)
4alloc_perturb (p, bytes);
return p;
}

这个转换是把需要的内存大小bytes,转换成需要分配的chunk的大小nb。

1
2
3
4
5
6
7
8
9
10
11
#define checked_request2size(req, sz) \
if (REQUEST_OUT_OF_RANGE (req)) { \
__set_errno (ENOMEM); \
return 0; \
} \
(sz) = request2size (req);
#define request2size(req) \
(((req) + SIZE_SZ + MALLOC_ALIGN_MASK < MINSIZE) ? \
MINSIZE : \
((req) + SIZE_SZ + MALLOC_ALIGN_MASK) & ~MALLOC_ALIGN_MASK)

2.fastbin

如果分配大小正好是fastbin,那就直接从fastbin分配。

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
/*
If the size qualifies as a fastbin, first check corresponding bin.
This code is safe to execute even if av is not yet initialized, so we
can try it without checking, which saves some time on this fast path.
*/
4
//要分配的值小于等于最大的fastbin大小
if ((unsigned long) (nb) <= (unsigned long) (get_max_fast ()))
{
idx = fastbin_index (nb);
mfastbinptr *fb = &fastbin (av, idx);
mchunkptr pp = *fb;
do
{
victim = pp;
if (victim == NULL)
break;
}
while ((pp = catomic_compare_and_exchange_val_acq (fb, victim->fd, victim))
!= victim);
if (victim != 0)
{
if (__builtin_expect (fastbin_index (chunksize (victim)) != idx, 0))
{
errstr = "malloc(): memory corruption (fast)";
errout:
malloc_printerr (check_action, errstr, chunk2mem (victim), av);
return NULL;
}
check_remalloced_chunk (av, victim, nb);
void *p = chunk2mem (victim);
alloc_perturb (p, bytes);
return p;
}
}
//一些其他的宏
/* Atomically store NEWVAL in *MEM if *MEM is equal to OLDVAL.
Return the old *MEM value. */
#if !defined atomic_compare_and_exchange_val_acq \
&& defined __arch_compare_and_exchange_val_32_acq
# define atomic_compare_and_exchange_val_acq(mem, newval, oldval) \
__atomic_val_bysize (__arch_compare_and_exchange_val,acq, \
44 mem, newval, oldval)
#endif
#ifndef catomic_compare_and_exchange_val_acq
# ifdef __arch_c_compare_and_exchange_val_32_acq
# define catomic_compare_and_exchange_val_acq(mem, newval, oldval) \
__atomic_val_bysize (__arch_c_compare_and_exchange_val,acq, \
44 mem, newval, oldval)
# else
# define catomic_compare_and_exchange_val_acq(mem, newval, oldval) \
atomic_compare_and_exchange_val_acq (mem, newval, oldval)
# endif
#endif
//展开之后
#define __atomic_val_bysize(pre, post, mem, ...) \
({ \
__typeof (*mem) __atg1_result; \
if (sizeof (*mem) == 1) \
__atg1_result = pre##_8_##post (mem, __VA_ARGS__); \
else if (sizeof (*mem) == 2) \
__atg1_result = pre##_16_##post (mem, __VA_ARGS__); \
else if (sizeof (*mem) == 4) \
__atg1_result = pre##_32_##post (mem, __VA_ARGS__); \
else if (sizeof (*mem) == 8) \
__atg1_result = pre##_64_##post (mem, __VA_ARGS__); \
else \
abort (); \
__atg1_result; \
})

​ 首先根据分配大小,获取该chunk所属的fastbin的index,然后根据index获取所需要的fastbin的空闲链表的头指针;然后将头指针的下一个chunk 作为空闲chunk 链表的头部。后面check之后,直接使用chunk2mem()把用户所需的内存块转换并且返回。


3.small bin
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
/*
If a small request, check regular bin. Since these "smallbins"
hold one size each, no searching within bins is necessary.
(For a large request, we need to wait until unsorted chunks are
processed to find best fit. But for small ones, fits are exact
anyway, so we can check now, which is faster.)
*/
if (in_smallbin_range (nb))
{
idx = smallbin_index (nb);
bin = bin_at (av, idx);
if ((victim = last (bin)) != bin)//与表头相同,说明链表是空的;不相同的话进入下面的逻辑
{
if (victim == 0) /* initialization check */
malloc_consolidate (av); //合并fastbin
else
{
//将victim从双向循环链表中取出来
bck = victim->bk;
if (__glibc_unlikely (bck->fd != victim))
{
errstr = "malloc(): smallbin double linked list corrupted";
goto errout;
}
44//设置inuse标志。
set_inuse_bit_at_offset (victim, nb);
bin->bk = bck;
bck->fd = bin;
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;
}
}
}

​ 首先还是根据分配的大小,找到所对应的small bin的index,然后根据这个index去找到所需的small bin的空闲链表头指针;然后将最后一个chunk赋值给victim,然后做判断,如果和表头相同,那么说明这个链表当前是空的,就不能从这个small bin中分配内存,这就要走后面的流程了;如果不同,这里有两种情况:

  1. victim为0,即还没有初始化双向循环链表,这时候就要去合并fast bin;
  2. victim不为0,直接把victim从small bin中取出来,设置标志位,然后判断是否属于主分配区,之后调用chunk2meme()转换成用户所需内存空间并返回。

4.large bin
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
/*
If this is a large request, consolidate fastbins before continuing.
While it might look excessive to kill all fastbins before
even seeing if there is space available, this avoids
fragmentation problems normally associated with fastbins.
Also, in practice, programs tend to have runs of either small or
large requests, but less often mixtures, so consolidation is not
invoked all that often in most programs. And the programs that
it is called frequently in otherwise tend to fragment.
*/
else
{
idx = largebin_index (nb);
if (have_fastchunks (av))
//合并fastbin中的chunk,加入unsorted bin
malloc_consolidate (av);
}

​ 在分配之前会先合并fast bin中的chunk,加入unsorted bin。

​ 下面代码是遍历unsorted bin中的空闲块,加入到相应的small bin 或者large bin之中,代码比较长,所以一部分一部分的看。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
/*
Process recently freed or remaindered chunks, taking one only if
it is exact fit, or, if this a small request, the chunk is remainder from
the most recent non-exact fit. Place other traversed chunks in
bins. Note that this step is the only place in any routine where
chunks are placed in bins.
The outer loop here is needed because we might not realize until
near the end of malloc that we should have consolidated, so must
do so and retry. This happens at most once, and only when we would
otherwise need to expand memory to service a "small" request.
*/
for (;; )
{
int iters = 0;
while ((victim = unsorted_chunks (av)->bk) != unsorted_chunks (av))
{
bck = victim->bk;
if (__builtin_expect (victim->size <= 2 * SIZE_SZ, 0)
|| __builtin_expect (victim->size > av->system_mem, 0))
malloc_printerr (check_action, "malloc(): memory corruption",
chunk2mem (victim), av);
size = chunksize (victim);

这里先是反向遍历链表,检查size,要小于等于 2*SIZE_SZ,并且不能大于系统分配的总量。然后获取chunk的size。

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
/*
If a small request, try to use last remainder if it is the
only chunk in unsorted bin. This helps promote locality for
runs of consecutive small requests. This is the only
exception to best-fit, and applies only when there is
no exact fit for a small chunk.
*/
if (in_smallbin_range (nb) &&
bck == unsorted_chunks (av) &&
victim == av->last_remainder &&
(unsigned long) (size) > (unsigned long) (nb + MINSIZE))
{
/* split and reattach remainder */
remainder_size = size - nb;
remainder = chunk_at_offset (victim, nb);
unsorted_chunks (av)->bk = unsorted_chunks (av)->fd = remainder;
av->last_remainder = remainder;
remainder->bk = remainder->fd = unsorted_chunks (av);
//large chunk
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;
}

​ 之前的small bin 没有成功分配,并且只有一个chunk的时候,那个chunk就是last remainder chunk,且last remainder chunk 的size大于所需要的大小+MINSIZE,这个时候就可已从这个块中去分配所需要的内存。

​ 后面就是从这个chunk 中切分出所需大小的chunk,计算切分后剩下chunk 的大小,将剩下的chunk加入unsorted bin 的链表中,并将剩下的chunk 作为分配区的last remainder chunk,若剩下的chunk 属于large bin chunk,将该chunk 的fd_nextsizebk_nextsize设置为NULL。

​ 然后设置一些标志位,对于last remainder chunk需要调用set_foot(),因为处于空闲状态的chunk的pre_size才是有效的;之后就是利用chunk2mem()转换,然后返回给用户了。

1
2
3
/* remove from unsorted list */
unsorted_chunks (av)->bk = bck;
bck->fd = unsorted_chunks (av);

​ 将双向循环链表中的最后一个chunk 移除

1
2
3
4
5
6
7
8
9
10
11
12
13
/* Take now instead of binning if exact fit */
if (size == nb)
{
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;
}

​ 如果当前遍历的chunk的size正好和需要的分配的大小nb相等,那直接就返回当前块:设置inuse标志位,然后判断是否属于主分配区,并设置相应的标志位,之后调用chunk2mem()转换后就返回给用户了。

1
2
3
4
5
6
7
8
/* place chunk in bin */
if (in_smallbin_range (size))
{
victim_index = smallbin_index (size);
bck = bin_at (av, victim_index);
fwd = bck->fd;
}

判断当前遍历的chunk是否在small bin的范围,在的话插入到small bin的表头,成为第一个块。

不在small bin的范围的话,就是large bin了,就走下面的逻辑:

1
2
3
4
5
6
else
{
victim_index = largebin_index (size);
bck = bin_at (av, victim_index);
fwd = bck->fd;

类似上面的,把当前遍历的这个chunk插入到large bin的表头成为large bin的第一个块。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
/* maintain large bins in sorted order */
if (fwd != bck)
{
/* Or with inuse bit to speed comparisons */
size |= PREV_INUSE;
/* if smaller than smallest, bypass loop below */
assert ((bck->bk->size & NON_MAIN_ARENA) == 0);
if ((unsigned long) (size) < (unsigned long) (bck->bk->size))
{
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;
}

if (fwd != bck)意味着当前链表不为空,需要把当前的块插入large bin的链表中,设置inuse标志,并且插入到适合的位置。

1
2
3
4
5
6
7
8
else
{
assert ((fwd->size & NON_MAIN_ARENA) == 0);
while ((unsigned long) size < fwd->size)
{
fwd = fwd->fd_nextsize;
assert ((fwd->size & NON_MAIN_ARENA) == 0);
}

如果size比最后一个chunk的siz还要小,那就直接插入到最后。

1
2
3
4
5
6
7
8
9
10
11
if ((unsigned long) size == (unsigned long) fwd->size)
/* Always insert in the second position. */
fwd = fwd->fd;
else
{
victim->fd_nextsize = fwd;
victim->bk_nextsize = fwd->bk_nextsize;
fwd->bk_nextsize = victim;
victim->bk_nextsize->fd_nextsize = victim;
}
bck = fwd->bk;

正向遍历chunk size链表,找到一个和当前chunk大小相同的chunk就退出,那么chunk size 链表中一定包含fwd 所指向的chunk,为了不修改chunk size 链表,当前chunk 只能插入fwd 之后。

1
2
3
4
5
}
}
else
victim->fd_nextsize = victim->bk_nextsize = victim;
}

如果large bin链表里没有chunk,那么就直接插入chunk size链表。

1
2
3
4
5
mark_bin (av, victim_index);
victim->bk = bck;
victim->fd = fwd;
fwd->bk = victim;
bck->fd = victim;

完成chunk的插入空闲链表之后,设置bitmap。

1
2
3
4
#define MAX_ITERS 10000
if (++iters >= MAX_ITERS)
break;
}

这里设置了最大的迭代次数,超出就直接退出了。

​ 当将unsorted bin 中的空闲chunk 加入到相应的small bins 和large bins 后,将使用最佳匹配法分配large bin chunk。源代码如下:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
/*
If a large request, scan through the chunks of current bin in
sorted order to find smallest that fits. Use the skip list for this.
*/
if (!in_smallbin_range (nb))
{
bin = bin_at (av, idx);
/* skip scan if empty or largest chunk is too small */
if ((victim = first (bin)) != bin &&
(unsigned long) (victim->size) >= (unsigned long) (nb))
{
victim = victim->bk_nextsize;
while (((unsigned long) (size = chunksize (victim)) <
(unsigned long) (nb)))
victim = victim->bk_nextsize;

​ 如果所分配的块是large bin chunk,那么进入这段逻辑,当large bin list不为空且最大的chunk可以满足需要,就反向遍历链表,找到大小最合适的chunk,然后退出循环。

1
2
3
4
5
6
7
/* Avoid removing the first entry for a size so that the skip
list does not have to be rerouted. */
if (victim != last (bin) && victim->size == victim->fd->size)
victim = victim->fd;
remainder_size = size - nb;
unlink (av, victim, bck, fwd);

​ 如果所选的chunk(即victim)不是最后一个chunk,且下一个块chunk大小和所选的chunk大小一致,那么把后面的那个chunk作为备选。

​ 计算victim分割后剩余的size,然后使用unlink()宏去把victim从链表中取出来。

1
2
3
4
5
6
7
/* Exhaust */
if (remainder_size < MINSIZE)
{
set_inuse_bit_at_offset (victim, size);
if (av != &main_arena)
victim->size |= NON_MAIN_ARENA;
}

​ 之后判断分割后剩余大小,如果小于MINSIZE(分配的chunk要略大于需要的chunk),那么就给victim设置inuse标志,然后根据是否是主分配区的判断,设置相应的标志位。

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
/* Split */
else
{
remainder = chunk_at_offset (victim, nb);
/* We cannot assume the unsorted list is empty and therefore
have to perform a complete insert here. */
bck = unsorted_chunks (av);
fwd = bck->fd;
if (__glibc_unlikely (fwd->bk != bck))
{
errstr = "malloc(): corrupted unsorted chunks";
goto errout;
}
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;
}
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中分割出去的剩余部分作为新chunk加入到unsorted bin中,接着是判断大小,如果是large bin的范围,还要把fd_nextsizebk_nextsize置为NULL,之后设置标志位,因为remainder空闲,所以还要设置foot(上面的分析里也有类似这段设置标志位的逻辑)。最后就很简单了,调用chunk2mem()的到可用的内存指针并返回给用户。

​ 上面从最合适的small bin和large bin都没有合适的chunk去分配,那么就会查看比当前index大的下一个small bin 或者large bin中有没有合适的块去分配给用户,源码如下

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
/*
Search for a chunk by scanning bins, starting with next largest
bin. This search is strictly by best-fit; i.e., the smallest
(with ties going to approximately the least recently used) chunk
that fits is selected.
The bitmap avoids needing to check that most blocks are nonempty.
The particular case of skipping all bins during warm-up phases
when no chunks have been returned yet is faster than it might look.
*/
++idx;
bin = bin_at (av, idx);
block = idx2block (idx);
map = av->binmap[block];
bit = idx2bit (idx);

​ 首先获取下一个bin,下面是malloc_state的结构体,bitmap是标识对应的bin中有没有空闲chunk。bitmap是按照block管理的,所以先获取了block,然后根据获取到的block去获取bitmap。

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
struct malloc_state
{
/* Serialize access. */
mutex_t mutex;
/* Flags (formerly in max_fast). */
int flags;
/* Fastbins */
mfastbinptr fastbinsY[NFASTBINS];
/* Base of the topmost chunk -- not otherwise kept in a bin */
mchunkptr top; //point to the TOP CHUNK of malloc state -- by muhe
/* The remainder from the most recent split of a small request */
mchunkptr last_remainder;
/* Normal bins packed as described above */
mchunkptr bins[NBINS * 2 - 2];
/* Bitmap of bins */
unsigned int binmap[BINMAPSIZE];
/* Linked list */
struct malloc_state *next;
/* Linked list for free arenas. Access to this field is serialized
by free_list_lock in arena.c. */
struct malloc_state *next_free;
/* Number of threads attached to this arena. 0 if the arena is on
the free list. Access to this field is serialized by
free_list_lock in arena.c. */
INTERNAL_SIZE_T attached_threads;
/* Memory allocated from the system in this arena. */
INTERNAL_SIZE_T system_mem;
INTERNAL_SIZE_T max_system_mem;
};

​ bit通过下面的宏被设置,idx指定的位置为1,其他位为0 。

1
#define idx2bit(i) ((1U << ((i) & ((1U << BINMAPSHIFT) - 1))))

​ 如果bit大于map,则map为0,map为0,说明当前bin中没有空闲chunk,所以去遍历bitmap的下一个block,直到找到一个不为0,或者遍历完才结束。

​ 在退出循环遍历后,设置bin 指向block 的第一个bit 对应的bin,并将bit 为1, 表示该block中bit 1 对应的bin,这个bin 中如果有空闲chunk,该chunk 的大小一定满足要求。

1
#define BINMAPSHIFT 5
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
for (;; )
{
/* Skip rest of block if there are no more set bits in this block. */
if (bit > map || bit == 0)
{
do
{
if (++block >= BINMAPSIZE) /* out of bins */
goto use_top; //走top chunk的逻辑
}
while ((map = av->binmap[block]) == 0); //取到下一个block的map
bin = bin_at (av, (block << BINMAPSHIFT));
bit = 1;
}

​ 这段逻辑,是遍历一个block里所有的bin,因为map是非0的,所以找到bit不为0就退出循环,那么这个bit对应bin中一定有空闲chunk。

1
2
3
4
5
6
7
/* Advance to bin with set bit. There must be one. */
while ((bit & map) == 0)
{
bin = next_bin (bin);
bit <<= 1;
assert (bit != 0);
}

​ 获取这个bin的最后一个chunk即victim,如果最后一个chunk和链表头指针相同,那么说明这个链表中没有空chunk,这个时候就先把之前bit清零,然后到下一个bin中,

1
2
3
4
5
6
7
8
9
10
/* Inspect the bin. It is likely to be non-empty */
victim = last (bin);
/* If a false alarm (empty bin), clear the bit. */
if (victim == bin)
{
av->binmap[block] = map &= ~bit; /* Write through */
bin = next_bin (bin);
bit <<= 1;
}

​ 如果不相同,那么先的到victim的size,然后和之前的逻辑类似,计算分割后的大小remainder_size,然后使用unlink宏去把victim从链表中解链出来。

1
2
3
4
5
6
7
8
9
10
11
else
{
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;
/* unlink */
unlink (av, victim, bck, fwd);

​ 这里判断切割后的大小并针对不同的大小做不同的处理。

  1. 如果切割剩余大小比MINSIZE小,那么就应该把整个chunk分给用户,之后就设置对应的标志位,之后就是返回的工作了;
  2. 如果比MINSIZE大,就要分割了。分割剩下的这块,要作为新的chunk加入unsorted bin。
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
/* Exhaust */
if (remainder_size < MINSIZE)
{
set_inuse_bit_at_offset (victim, size);
if (av != &main_arena)
victim->size |= NON_MAIN_ARENA;
}
/* Split */
else
{
remainder = chunk_at_offset (victim, nb);
/* We cannot assume the unsorted list is empty and therefore
have to perform a complete insert here. */
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是small bin,那么就要把分配区的last remainder 设置为这个chunk;如果是large bin,要把fd_nextsizebk_nextsize置NULL,然后和之前对large bin处理的逻辑一样,设置head、foot的标志位。

1
2
3
4
5
6
7
8
9
10
11
12
13
/* advertise as last 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);
}

​ 最后逻辑很简单,调用chunk2mem的到可用的内存指针,并返回给用户。

1
2
3
4
5
6
check_malloced_chunk (av, victim, nb);
void *p = chunk2mem (victim);
alloc_perturb (p, bytes);
return p;
}
}
5.top chunk

​ 这部分是在前面所有分配都失败的情况下才会到的逻辑,即fastbin 、small bin、large bin 都没有分配到所需要的chunk,就会从当前分配实例的top chunk直接分配内存,代码如下

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
use_top:
/*
If large enough, split off the chunk bordering the end of memory
(held in av->top). Note that this is in accord with the best-fit
search rule. In effect, av->top is treated as larger (and thus
less well fitting) than any other available chunk since it can
be extended to be as large as necessary (up to system
limitations).
We require that av->top always exists (i.e., has size >=
MINSIZE) after initialization, so if it would otherwise be
exhausted by current request, it is replenished. (The main
reason for ensuring it exists is that we may need MINSIZE space
to put in fenceposts in sysmalloc.)
*/
victim = av->top;
size = chunksize (victim);
if ((unsigned long) (size) >= (unsigned long) (nb + MINSIZE))
{
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;
}

​ 首先,获取到top chunk,然后获取top chunk的size,接着判断size和要分配的大小nb,如果size大于我们要分配的大小nb,那就直接从top chunk中分割,的到victim,分割剩余部分作为新的top chunk,设置victim的一些标志位之后,调用chunk2mem()的到可用内存指针并且返回给用户。

​ 一点小细节,因为top chunk需要MINSIZE 的空间来作为fencepost,所以大小比较的时候要加个MINSIZE;所以在分割完成之后并不用去设置foot。

1
2
3
4
5
6
7
8
9
10
11
/* When we are using atomic ops to free fast chunks we can get
here for all block sizes. */
else if (have_fastchunks (av))
{
malloc_consolidate (av);
/* restore original bin index */
if (in_smallbin_range (nb))
idx = smallbin_index (nb);
else
idx = largebin_index (nb);
}

​ 如果还是没从top chunk中分配到,判断当前分配区中是否有fast bins中是否有chunk,有的话就合并到unsorted bin中,接着判断,在small bin范围内,就再次设置idx,进到最外层循环,再来一次,相对应的,large bin范围内也是一样,设置idx,再到最外层循环。

6.sysmalloc

​ 在之前的分配策略都没办法分配到我们想要的内存的时候,就会走到这里。这里直接调用了sycmalloc()去分配,其实就是使用了mmap()直接映射,当然这个函数不可能这么简单,他对不同情况做了不同的处理。

1
2
3
4
5
6
7
8
9
10
11
12
/*
Otherwise, relay to handle system-dependent cases
*/
else
{
void *p = sysmalloc (nb, av);
if (p != NULL)
alloc_perturb (p, bytes);
return p;
}
}
}

2. sysmalloc 分析

1
2
static void *
sysmalloc (INTERNAL_SIZE_T nb, mstate av)
为了治疗拖延症,所以把过程记录在博客上,慢慢更新...
文章目录
  1. 1. 1.malloc 分析
    1. 1.0.1. 1.概述
    2. 1.0.2. 2.fastbin
    3. 1.0.3. 3.small bin
    4. 1.0.4. 4.large bin
    5. 1.0.5. 5.top chunk
    6. 1.0.6. 6.sysmalloc
  • 2. 2. sysmalloc 分析
  • ,