5.7.2.3 分配large bin chunk(二)
如果通过上面的方式从最合适的
small bin
或
large bin
中都没有分配到需要的
chunk
,则查看比当前
bin
的
index
大的
small bin
或
large bin
是否有空闲
chunk
可利用来分配所需的
chunk
。源代码实现如下
/*
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
的空闲
chunk
链表,并获取该
bin
对于
binmap
中的
bit
位的值。
Binmap
中的标识了相应的
bin
中是否有空闲
chunk
存在。
Binmap
按
block
管理,每个
block
为一个
int
,共
32
个
bit
,可以表示
32
个
bin
中是否有空闲
chunk
存在。使用
binmap
可以加快查找
bin
是否包含空闲
chunk
。这里只查询比所需
chunk
大的
bin
中是否有空闲
chunk
可用。
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;
} while ( (map = av->binmap[block]) == 0);
bin = bin_at(av, (block << BINMAPSHIFT));
bit = 1;
}
Idx2bit()
宏将
idx
指定的位设置为
1
,其它位清零,
map
表示一个
block
(
unsigned int
)值,如果
bit
大于
map
,意味着
map
为
0
,该
block
所对应的所有
bins
中都没有空闲
chunk
,于是遍历
binmap
的下一个
block
,直到找到一个不为
0
的
block
或者遍历完所有的
block
。退出循环遍历后,设置
bin
指向
block
的第一个
bit
对应的
bin
,并将
bit
置为
1
,表示该
block
中
bit 1
对应的
bin
,这个
bin
中如果有空闲
chunk
,该
chunk
的大小一定满足要求。
/* Advance to bin with set bit. There must be one. */
while ((bit & map) == 0) {
bin = next_bin(bin);
bit <<= 1;
assert(bit != 0);
}
在一个block遍历对应的bin,直到找到一个bit不为0退出遍历,则该bit对于的bin中有空闲chunk存在。
/* Inspect the bin. It is likely to be non-empty */
victim = last(bin);
将bin链表中的最后一个chunk赋值为victim。
/* 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与bin链表头指针相同,表示该bin中没有空闲chunk,binmap中的相应位设置不准确,将binmap的相应bit位清零,获取当前bin下一个bin,将bit移到下一个bit位,即乘以2。
}
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(victim, bck, fwd);
当前bin中的最后一个chunk满足要求,获取该chunk的大小,计算切分出所需chunk后剩余部分的大小,然后将victim从bin的链表中取出。
/* Exhaust */
if (remainder_size < MINSIZE) {
set_inuse_bit_at_offset(victim, size);
if (av != &main_arena)
victim->size |= NON_MAIN_ARENA;
如果剩余部分的大小小于
MINSIZE
,将整个
chunk
分配给应用层,设置
victim
的状态为
inuse
,如果当前分配区为非主分配区,设置
victim
的非主分配区标志位。
}
/* 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 (__builtin_expect (fwd->bk != bck, 0))
{
errstr = "malloc(): corrupted unsorted chunks 2";
goto errout;
}
remainder->bk = bck;
remainder->fd = fwd;
bck->fd = remainder;
fwd->bk = remainder;
/* 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;
}
从victim
中切分出所需的
chunk
,剩余部分作为一个新的
chunk
加入到
unsorted
bin
中。如果剩余部分
chunk
属于
small bins
,将分配区的
last remainder chunk
设置为剩余部分构成的
chunk
;如果剩余部分
chunk
属于
large bins
,将剩余部分
chunk
的
chunk size
链表指针设置为
NULL
,因为
unsorted bin
中的
chunk
是不排序的,这两个指针无用,必须清零。
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);
设置victim和remainder的状态,由于remainder为空闲chunk,所以需要设置该chunk的foot。
}
check_malloced_chunk(av, victim, nb);
void *p = chunk2mem(victim);
if (__builtin_expect (perturb_byte, 0))
alloc_perturb (p, bytes);
return p;
调用chunk2mem()获得chunk中可用的内存指针,返回给应用层,退出。
}
}
如果从所有的
bins
中都没有获得所需的
chunk
,可能的情况为
bins
中没有空闲
chunk
,或者所需的
chunk
大小很大,下一步将尝试从
top
chunk
中分配所需
chunk
。源代码实现如下:
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);
将当前分配区的top chunk赋值给victim,并获得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);
if (__builtin_expect (perturb_byte, 0))
alloc_perturb (p, bytes);
return p;
}
由于top chunk
切分出所需
chunk
后,还需要
MINSIZE
的空间来作为
fencepost
,所需必须满足
top
chunk
的大小大于所需
chunk
的大小加上
MINSIZE
这个条件,才能从
top chunk
中分配所需
chunk
。从
top chunk
切分出所需
chunk
的处理过程跟前面的
chunk
切分类似,不同的是,原
top chunk
切分后的剩余部分将作为新的
top chunk
,原
top chunk
的
fencepost
仍然作为新的
top chunk
的
fencepost
,所以切分之后剩余的
chunk
不用
set_foot
。
#ifdef ATOMIC_FASTBINS
/* 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
存在,由于开启了
ATOMIC_FASTBINS
优化情况下,
free
属于
fast bins
的
chunk
时不需要获得分配区的锁,所以在调用
_int_malloc()
函数时,有可能有其它线程已经向
fast bins
中加入了新的空闲
chunk
,也有可能是所需的
chunk
属于
small bins
,但通过前面的步骤都没有分配到所需的
chunk
,由于分配
small bin chunk
时在前面的步骤都不会调用
malloc_consolidate()
函数将
fast bins
中的
chunk
合并加入到
unsorted bin
中。所在这里如果
fast bin
中有
chunk
存在,调用
malloc_consolidate()
函数,并重新设置当前
bin
的
index
。并转到最外层的循环,尝试重新分配
small bin chunk
或是
large bin chunk
。如果开启了
ATOMIC_FASTBINS
优化,有可能在由其它线程加入到
fast bins
中的
chunk
被合并后加入
unsorted bin
中,从
unsorted bin
中就可以分配出所需的
large bin chunk
了,所以对没有成功分配的
large bin chunk
也需要重试。
#else
/*
If there is space available in fastbins, consolidate and retry,
to possibly avoid expanding memory. This can occur only if nb is
in smallbin range so we didn't consolidate upon entry.
*/
else if (have_fastchunks(av)) {
assert(in_smallbin_range(nb));
malloc_consolidate(av);
idx = smallbin_index(nb); /* restore original bin index */
}
如果top chunk
也不能满足要求,查看
fast bins
中是否有空闲
chunk
存在,如果
fast bins
中有空闲
chunk
存在,在没有开启
ATOMIC_FASTBINS
优化的情况下,只有一种可能,那就是所需的
chunk
属于
small bins
,但通过前面的步骤都没有分配到所需的
small bin chunk
,由于分配
small bin chunk
时在前面的步骤都不会调用
malloc_consolidate()
函数将
fast bins
中的空闲
chunk
合并加入到
unsorted bin
中。所在这里如果
fast bins
中有空闲
chunk
存在,调用
malloc_consolidate()
函数,并重新设置当前
bin
的
index
。并转到最外层的循环,尝试重新分配
small bin chunk
。
#endif
/*
Otherwise, relay to handle system-dependent cases
*/
else {
void *p = sYSMALLOc(nb, av);
if (p != NULL && __builtin_expect (perturb_byte, 0))
alloc_perturb (p, bytes);
return p;
山穷水尽了,只能想系统申请内存了。sYSMALLOc()函数可能分配的chunk包括small bin chunk,large bin chunk和large chunk。将在下一节中介绍该函数的实现。
}
}
至此,
_int_malloc()
函数的代码就罗列完了,当还有两个关键函数没有分析,一个为
malloc_consolidate()
,另一个为
sYSMALLOc()
,将在下面的章节介绍其实现。
分享到:
相关推荐
NULL 博文链接:https://mqzhuang.iteye.com/blog/1064966
Glibc内存管理 Ptmalloc2 源代码分析
glibc内存管理ptmalloc源代码分析-电子资料-高清PDF版-pdf打印版
简介133.2.2内存管理的设计假设 143.2.3内存管理数据结构概述 143.2.4内存分配概述 193.2.5内存回收概述 213.2.6配置选项概述 2
淘宝网的研发人员写的文档,对了解GNU C的内存分配机制有很大的帮助!
该文档详细分析了c库中的内存管理细节,可广大程序员做参考。
简介133.2.2内存管理的设计假设 143.2.3内存管理数据结构概述 143.2.4内存分配概述 193.2.5内存回收概述 213.2.6配置选项概述 2
清晰版,对内存分析,程序设计非常有帮助。适合进阶的。
本文通过Glibc的内存暴增问题,主要介绍了系统的内存管理问题,具体如下: 目录 1. 问题 2. 基础知识 2.1 X86平台Linux进程内存布局 2.1.1 32位模式下进程内存经典布局 2.1.2 32位模式下进程默认内存布局 ...
glibc内存管理ptmalloc源代码分析.pdf
源代码分析 glibc的ptmalloc 分析
glibc内存管理ptmalloc源代码分析4.pdf
学习自《glibc内存管理ptmalloc源代码分析》庄明强 著 部分资料参考自互联网 chunk 描述: 当用户通过malloc等函数申请空间时,实际上是从堆中分配内存 目前 Linux 标准发行版中使用的是 glibc 中的堆分配器:...