页次: 1
上文介绍了buddy和slab内存管理的思路,本文看看这些算法的关键代码都是怎么写的,这里用的是4.9版本的源码;重新把这个图贴出来,方便后续理解代码!
1、如上图所示,slab算法的入口就是kmem_cache结构体了,和其他重要结构体管理的方式类似,这里也统一采用数组的形式管理所有的kmem_cache结构体,所以也会根据用户输入的参数从数组里面找到合适的kmem_cache结构体,如下:
/*
* Conversion table for small slabs sizes / 8 to the index in the
* kmalloc array. This is necessary for slabs < 192 since we have non power
* of two cache sizes there. The size of larger slabs can be determined using
* fls.
* 通过size_index_elem求出8的倍数后,继续查找kmem_cache的index;
* 从这里可以直观看到用户申请不同size内存对应的kmem_cache的index
*/
static s8 size_index[24] = {
3, /* 8 */
4, /* 16 */
5, /* 24 */
5, /* 32 */
6, /* 40 */
6, /* 48 */
6, /* 56 */
6, /* 64 */
1, /* 72 */
1, /* 80 */
1, /* 88 */
1, /* 96 */
7, /* 104 */
7, /* 112 */
7, /* 120 */
7, /* 128 */
2, /* 136 */
2, /* 144 */
2, /* 152 */
2, /* 160 */
2, /* 168 */
2, /* 176 */
2, /* 184 */
2 /* 192 */
};
/*
8字节对齐,也就是8的多少倍?
*/
static inline int size_index_elem(size_t bytes)
{
return (bytes - 1) / 8;
}
/*
* Find the kmem_cache structure that serves a given size of
* allocation
*/
struct kmem_cache *kmalloc_slab(size_t size, gfp_t flags)
{
int index;
if (unlikely(size > KMALLOC_MAX_SIZE)) {
WARN_ON_ONCE(!(flags & __GFP_NOWARN));
return NULL;
}
/*如果用户申请的size小于192byte*/
if (size <= 192) {
if (!size)
return ZERO_SIZE_PTR;
index = size_index[size_index_elem(size)];
} else
/*如果用户申请的size大于192byte*/
index = fls(size - 1);
#ifdef CONFIG_ZONE_DMA
if (unlikely((flags & GFP_DMA)))
return kmalloc_dma_caches[index];
#endif
return kmalloc_caches[index];
}
上面的size_index数组看起来可能还有些抽象,这里有个更直接的映射表:object的size和kmem_cache的index、名字之间的映射关系,比如用户申请96byte的内存,那么这个kmem_cache的index就是1,和size_index数组刚好吻合;
/*
* kmalloc_info[] is to make slub_debug=,kmalloc-xx option work at boot time.
* kmalloc_index() supports up to 2^26=64MB, so the final entry of the table is
* kmalloc-67108864.
*/
static struct {
const char *name;
unsigned long size;
} const kmalloc_info[] __initconst = {
{NULL, 0}, {"kmalloc-96", 96},
{"kmalloc-192", 192}, {"kmalloc-8", 8},
{"kmalloc-16", 16}, {"kmalloc-32", 32},
{"kmalloc-64", 64}, {"kmalloc-128", 128},
{"kmalloc-256", 256}, {"kmalloc-512", 512},
{"kmalloc-1024", 1024}, {"kmalloc-2048", 2048},
{"kmalloc-4096", 4096}, {"kmalloc-8192", 8192},
{"kmalloc-16384", 16384}, {"kmalloc-32768", 32768},
{"kmalloc-65536", 65536}, {"kmalloc-131072", 131072},
{"kmalloc-262144", 262144}, {"kmalloc-524288", 524288},
{"kmalloc-1048576", 1048576}, {"kmalloc-2097152", 2097152},
{"kmalloc-4194304", 4194304}, {"kmalloc-8388608", 8388608},
{"kmalloc-16777216", 16777216}, {"kmalloc-33554432", 33554432},
{"kmalloc-67108864", 67108864}
};
最关键的就是index的计算方法了;小于192byte直接查表,大于192byte调用fls,find last bit set函数查找index,代码如下:
/*
* fls = Find Last Set in word
* @result: [1-32]
* fls(1) = 1, fls(0x80000000) = 32, fls(0) = 0
*/
static inline __attribute__ ((const)) int fls(unsigned long x)
{
if (__builtin_constant_p(x))
return constant_fls(x);
return 32 - clz(x);
}
/*
* Count the number of zeros, starting from MSB
* Helper for fls( ) friends
* This is a pure count, so (1-32) or (0-31) doesn't apply
* It could be 0 to 32, based on num of 0's in there
* clz(0x8000_0000) = 0, clz(0xFFFF_FFFF)=0, clz(0) = 32, clz(1) = 31
*/
static inline __attribute__ ((const)) int clz(unsigned int x)
{
unsigned int res;
__asm__ __volatile__(
" norm.f %0, %1 \n"
" mov.n %0, 0 \n"
" add.p %0, %0, 1 \n"
: "=r"(res)
: "r"(x)
: "cc");
return res;
}
核心作用是返回输入参数的最高有效bit位(从低位往左数最后的有效bit位)的序号,该序号与常规0起始序号不同,它是1起始的(当没有有效位时返回0);
要点:
kmem_cachess数组最多13个元素,也就是说最多有13种不同size的object;
如果用户申请的size小于192byte,直接查size_index数组就可以找到kmem_cache的index
如果用户申请的size大于192byte,返回输入参数的最高有效bit位(从低位往左数最后的有效bit位)的序号
2、kmem_cache得到后,下一步就是找到slab了,linux是这样干的:
static __always_inline void *
slab_alloc(struct kmem_cache *cachep, gfp_t flags, unsigned long caller)
{
unsigned long save_flags;
void *objp;
flags &= gfp_allowed_mask;
cachep = slab_pre_alloc_hook(cachep, flags);
if (unlikely(!cachep))
return NULL;
cache_alloc_debugcheck_before(cachep, flags);
/*保存flag寄存器的状态,然后关中断,避免被中断切换进程*/
local_irq_save(save_flags);
/*得到了返回值*/
objp = __do_cache_alloc(cachep, flags);
/*重新打开中断*/
local_irq_restore(save_flags);
objp = cache_alloc_debugcheck_after(cachep, flags, objp, caller);
prefetchw(objp);
if (unlikely(flags & __GFP_ZERO) && objp)
memset(objp, 0, cachep->object_size);
slab_post_alloc_hook(cachep, flags, 1, &objp);
return objp;
}
函数的返回值objp是调用_do_cache_alloc返回的,重点继续分析这个函数(其他函数都是陪衬┭┮﹏┭┮);经过一系列的调用链,最终来到了这里:返回值是objp,来自两个地方:先检查cpu的缓存(也就是array_cache数组),如果还有就从缓存数组分配;如果没有就继续调用cache_alloc_refill从 3 个 slabs_(free/partial/full)中寻找可用的object,并将其填充到 array_cache 中;
static inline void *____cache_alloc(struct kmem_cache *cachep, gfp_t flags)
{
void *objp;
struct array_cache *ac;
check_irq_off();
/*先看array_cache缓存是不是还有*/
ac = cpu_cache_get(cachep);
if (likely(ac->avail)) {
ac->touched = 1;
objp = ac->entry[--ac->avail];
STATS_INC_ALLOCHIT(cachep);
goto out;
}
STATS_INC_ALLOCMISS(cachep);
/*array_cache缓存没了再重新寻找可用的object*/
objp = cache_alloc_refill(cachep, flags);
/*
* the 'ac' may be updated by cache_alloc_refill(),
* and kmemleak_erase() requires its correct value.
*/
ac = cpu_cache_get(cachep);
out:
/*
* To avoid a false negative, if an object that is in one of the
* per-CPU caches is leaked, we need to make sure kmemleak doesn't
* treat the array pointers as a reference to the object.
*/
if (objp)
kmemleak_erase(&ac->entry[ac->avail]);
return objp;
}
和objp相关的两个函数都操作了arry_cache,这究竟是个啥结构体了?如下:
/*
* struct array_cache
*
* Purpose:
* - LIFO ordering, to hand out cache-warm objects from _alloc
* - reduce the number of linked list operations
* - reduce spinlock operations
*
* The limit is stored in the per-cpu structure to reduce the data cache
* footprint.
* 给每个cpu设置的对象缓存池
*/
struct array_cache {
unsigned int avail;/*缓存池中可用的object数量*/
unsigned int limit;/*最大object数量*/
unsigned int batchcount;/*要从 slab_list 转移进本地高速缓存对象的数量,或从本地高速缓存中转移出去的 obj 数量*/
unsigned int touched;/*从缓存池移除对象时设置为1,否则设置为0*/
void *entry[]; /* 保存释放的object实例指针
* Must have this definition in here for the proper
* alignment of array_cache. Also simplifies accessing
* the entries.
*/
};
这个结构体带来的好处:
提高cpu L1/L2/L3 cache的命中率:当此CPU上释放object后,如果再次申请一个相同大小的object时,原object很可能还在这个CPU的 L1/L2/L3 cache中,所以为每个CPU维护一个这样的链表,当需要新的object时,会优先尝试从当前CPU的本地CPU空闲object链表获取相应大小的object,此时很有可能命中cpu的L1/L2/L3 cache,提升分配效率;
减少锁的竞争:假设多个CPU同时申请同样大小的object,为了互相同步,需要暂时多个cpu之间暂时互斥,导致分配效率降低;有个array_cache后,申请object时会先从cpu自己的array_cache查找,减少了cpu之间互斥的概率,提升分配效率;
结构体的字段确定后,就要填充了,在cache_alloc_refill函数种完成,代码如下:
static void *cache_alloc_refill(struct kmem_cache *cachep, gfp_t flags)
{
int batchcount;
struct kmem_cache_node *n;
struct array_cache *ac, *shared;
int node;
void *list = NULL;
struct page *page;
/*确保中断已经关闭*/
check_irq_off();
node = numa_mem_id();
ac = cpu_cache_get(cachep);
batchcount = ac->batchcount;
if (!ac->touched && batchcount > BATCHREFILL_LIMIT) {
/*
* If there was little recent activity on this cache, then
* perform only a partial refill. Otherwise we could generate
* refill bouncing.
*/
batchcount = BATCHREFILL_LIMIT;
}
n = get_node(cachep, node);
BUG_ON(ac->avail > 0 || !n);
shared = READ_ONCE(n->shared);
if (!n->free_objects && (!shared || !shared->avail))
goto direct_grow;
spin_lock(&n->list_lock);
shared = READ_ONCE(n->shared);
/* See if we can refill from the shared array */
//从全局共享空闲对象中转移空闲对象到本地 CPU 空闲对象链表上
if (shared && transfer_objects(ac, shared, batchcount)) {
shared->touched = 1;
goto alloc_done;
}
while (batchcount > 0) {
/* Get slab alloc is to come from. */
page = get_first_slab(n, false);//从 slab 中获取空闲 slab
if (!page)
goto must_grow;
check_spinlock_acquired(cachep);
/*从free slab中获取空闲object,转移到本地CPU空闲object链表上*/
batchcount = alloc_block(cachep, ac, page, batchcount);
fixup_slab_list(cachep, n, page, &list);
}
must_grow:
n->free_objects -= ac->avail;
alloc_done:
spin_unlock(&n->list_lock);
fixup_objfreelist_debug(cachep, &list);
direct_grow:
if (unlikely(!ac->avail)) {
/* Check if we can use obj in pfmemalloc slab */
if (sk_memalloc_socks()) {
void *obj = cache_alloc_pfmemalloc(cachep, n, flags);
if (obj)
return obj;
}
/*当slab中都没有空闲object时,就从buddy系统中获取内存*/
page = cache_grow_begin(cachep, gfp_exact_node(flags), node);
/*
* cache_grow_begin() can reenable interrupts,
* then ac could change.
*/
ac = cpu_cache_get(cachep);
if (!ac->avail && page)
alloc_block(cachep, ac, page, batchcount);
cache_grow_end(cachep, page);
if (!ac->avail)
return NULL;
}
ac->touched = 1;
return ac->entry[--ac->avail];
}
整个array_cache填充过程总结如下:
首先会从本地 CPU 空闲object链表中尝试获取一个object用于分配:如果失败,则检查所有CPU共享的空闲object链表链表中是否存在,并且空闲链表中是否存在空闲object,若有就转移 batchcount 个空闲object到本地 CPU空闲object链表中;
如果上述失败,就尝试从 SLAB中分配;这时如果还失败,kmem_cache会尝试从页框分配器中获取一组连续的页框建立一个新的SLAB,然后从新的SLAB中获取一个对象。
相应的object释放流程(没在cache_alloc_refill):
首先会先将object释放到本地CPU空闲object链表中,如果本地CPU空闲object链表中对象过多,kmem_cache 会将本地CPU空闲object链表中的batchcount个对象移动到所有CPU共享的空闲object链表链表中
如果所有CPU共享的空闲object链表链表的object也太多了,kmem_cache也会把所有CPU共享的空闲object链表链表中 batchcount 个数的object移回它们自己所属的SLAB中,
这时如果SLAB中空闲对象太多,kmem_cache会整理出一些空闲的SLAB,将这些SLAB所占用的页框释放回页框分配器中。
cache_alloc_refill中比较关键的函数:从slab_partial和slab_free队列找空闲的object:
static struct page *get_first_slab(struct kmem_cache_node *n, bool pfmemalloc)
{
struct page *page;
page = list_first_entry_or_null(&n->slabs_partial,
struct page, lru);
if (!page) {
n->free_touched = 1;
page = list_first_entry_or_null(&n->slabs_free,
struct page, lru);
}
if (sk_memalloc_socks())
return get_valid_first_slab(n, page, pfmemalloc);
return page;
}
最后就是_kmalloc函数了:
static __always_inline void *kmalloc(size_t size, gfp_t flags)
{
if (__builtin_constant_p(size)) {
if (size > KMALLOC_MAX_CACHE_SIZE)
return kmalloc_large(size, flags);
#ifndef CONFIG_SLOB
if (!(flags & GFP_DMA)) {
int index = kmalloc_index(size);
if (!index)
return ZERO_SIZE_PTR;
return kmem_cache_alloc_trace(kmalloc_caches[index],
flags, size);
}
#endif
}
return __kmalloc(size, flags);
}
_kmalloc继续调用_do_kmalloc函数,核心调用的正式上面分析的kmalloc_slab函数和slab_alloc函数!
/**
* __do_kmalloc - allocate memory
* @size: how many bytes of memory are required.
* @flags: the type of memory to allocate (see kmalloc).
* @caller: function caller for debug tracking of the caller
*/
static __always_inline void *__do_kmalloc(size_t size, gfp_t flags,
unsigned long caller)
{
struct kmem_cache *cachep;
void *ret;
/*根据用户参数找到高速缓存块*/
cachep = kmalloc_slab(size, flags);
if (unlikely(ZERO_OR_NULL_PTR(cachep)))
return cachep;
/*根据kmem_cache结构体和用户参数找到object,并返回地址*/
ret = slab_alloc(cachep, flags, caller);
kasan_kmalloc(cachep, ret, size, flags);
trace_kmalloc(caller, ret,
size, cachep->size, flags);
return ret;
}
总结:
对于用户来说,需要用内存时直接调用malloc就行了,但是操作系统找空闲内存区域的时候可谓是大费周折(甚至还要关闭中断,避免分配的过程被打断;同时加锁,和其他cpu核之间互斥保持同步),这是malloc函数效率低的根本原因;如果客观条件允许,调用malloc函数后申请的内存建议反复使用(但是可能带来部分安全问题,这里需要平衡两者的权衡利弊),不要频繁地malloc和free!
slab机制比buddy复杂,各种概念伴随着层出不穷的结构体,但是万变不离其宗:(1)将内存进一步分割成更小的块,从8byte起步,尽可能避免碎片 (2)不同size的内存块分开管理,提高分配和回收合并的效率; 以上所有的结构体都是围绕着这两点目的展开的,比如缓存array_cache、多级链式查找等!
多级链式建立和维护的时候比较复杂,比如下图的从kmem_cache_node→partital中分配object,最多需要经历4次链式跳转查询object,为啥不直接用bitmap管理,而是要搞得这么复杂了?注意观察:每次链式跳转查询都有不同的结构体承载,每个结构体都有自己特定的字段属性,由此达到分层解耦的目的!
https://img2020.cnblogs.com/blog/2052730/202112/2052730-20211221095658911-877821572.png
内存操作函数概览:
https://img2020.cnblogs.com/blog/2052730/202112/2052730-20211221162242031-658490447.png
栈和堆的区别
写过代码的人都知道,代码运行的时候数据主要存储在两块人为划分的区域:栈和堆;栈一般用来存参数、返回地址、局部变量;堆用来存new出来的对象实例、全局变量、静态变量等;碎片化问题主要集中在堆区域,重来没听过栈内存有碎片化问题的,这是为啥了?
栈是通过sp指针管理的,sp减少或增加,意味着栈增加或减少,一般是函数调用前和函数调用完毕移动sp;栈内部存放的函数frame的大小就是函数参数、返回地址、局部变量的大小总和;编译器在编译阶段就能够精准计算函数frame的大小,所以函数调用前和调用后移动sp的距离也是能提前精准计算的,所以sp移动时给函数frame分配的空间也是精准的,这就是栈上没有碎片的根本原因!相比之下堆就不一样了: 堆要承担给用户app存放对象实例、全局变量、静态变量的重任,全局变量和静态变量还好,编译时就能确定大小,但是对象实例就不行了,这个完全依赖于运行时的情况确定,尤其时代码各种分支比较多的情况,所以堆内存的使用是没法提前预判的;为了增加内存分配的灵活性,就诞生了各种内存分配、GC的算法!
3、尽管linux操作系统采取了buddy和slab等算法,但还是无法完全避免内存碎片;并且由于c/c++自生的限制,没有jvm这种自动垃圾回收的机制,导致了malloc或new出来的内存需要程序员人工手动释放;一旦忘记释放,就会一直占用着内存,直到程序运行结束,操作系统全部回收整个程序的内存才会释放。如果某些应用程序因为业务需要无法停止(比如服务器上跑的应用),必须一直运行,那么这块“被遗忘”的内存会一直被占用,可用内存会越来越少,最终可能导致内存严重不够,整个应用崩盘重来(这也是服务端开发java越来越流行的原因之一)!目前业界公认垃圾回收算法最牛的就属ZGC和shenandoah了,这里简单介绍一下ZGC算法的过程和牛逼之处!
(1)jvm也会把内存按照不同大小分块(官方给的称呼是分页,但是个cpu硬件对内存的分页不同),jvm分页的大小如下:
小页面2MB,用于存储小于256KB的对象
中页面32MB,用于存储256KN~4MB的对象
大页面大小不固定,用于存储大于4MB的对象
(2)要回收垃圾,就要正确地识别垃圾,避免误伤正常的对象,ZGC是这样做的:找到GC root(线程栈变量、static变量、常量池、jni指针等),挨个查找这些对象内部的fileds,看看有没有引用其他的变量,由此找到直接的对象引用;
这个阶段称之为“初始标记”。为了确保标记的准确性,需要暂停所有线程的工作,官方称之为stop the world,简称STW;由于不需要像传统的GC算法那样扫描堆区域,所以再大的内存都不怕。从实测的数据看,此阶段耗时小于1ms;找到直接引用的对象后(比如下面的A对象),会把GC root指针的M0位置1,标明A对象正在经历GC流程!
(3)经过初始标记,找到了GC root直连的对象,很明显此刻并不能回收,因为还有很多对象可能并不是CG root节点直接引用的,比如B、C节点(有可能是A节点用了链表、数组、new Object等方式生成了B、C节点);为了提高效率,需要多个GC线程同时来标记所有的间接引用对象,此阶段称为“并发标记”;此阶段并不需要STW,所以并不影响业务线程的正常运行,时间长也不影响!B、C找到后,A->B和B->C引用指针的M0位同样标绿;此阶段有点像是多叉树或图的遍历!
这一步并发标记方法称为“三色标记”法;整个阶段由于没有STW,并且是多个GC线程和业务线程一起协作,可能出现漏标的情况:GC1线程没有标记C节点,以为C是垃圾,要回收C节点的内存;但是GC2线程还未完成,此时业务线程执行了B.c=null,把B->C的引用去掉,CG2线程执行后也会人为C节点没有引用;实际上由于业务线程执行了A.c=C,导致C节点被A引用,本身并不是垃圾,明显被误伤了!
为了避免C被误伤,jvm执行到A.c的时候需要把C先记录在remember set;为下一步的再标记做准备!使用的算法或技术叫snapshot at the begining,简称SATB,也就是在开始的时候拍快照,把代码中的引用关系保存下来,用作后续备查!
(4)上一步的并发标记由于没有STW,存在对象漏标的情况,可能导致正常引用的节点被当成垃圾回收;为了避免误伤,采用了remembor set的方式,一旦遇到A.c这种情况马上记录到set,然后通过set找到还在正常被使用的对象标记;为了精准标记、避免误伤,此阶段需要STW,让业务线程先暂停;由于只处理漏标的对象,实际测试看耗时小于1ms;此阶段称为再标记
(5)并发转移准备:经过前面3个阶段找到了垃圾,现在要着手准备删除垃圾、回收内存了;ZGC采用了copying算法:找到相同大小、还未使用过的页面,然后把正常引用的对象复制到新页面,旧页面存放的数据全部擦除,思路就是这么简单粗暴;此阶段没有STW,不影响正常的业务线程;
(6)初始转移:
由于需要移动对象,并且这些对象还有GC root的直接引用(没有引用的对象就是垃圾了,还需要转移么?),此阶段肯定要STW,耗时小于1ms(大部分是垃圾,需要转移的很少;并且此阶段只移动和GC root直连的对象,间接连接的对象此阶段部考虑)
把A复制到新页面,更改GC root的指针指向,同时更改颜色指针为蓝色,表示remapped移动阶段结束!
(7)并发转移
B和C转移到新页面,但是B和C的引用怎么转移了?在旧页面维护了转发表Forward table(和GC root不直连的对象都会在转发表),类似hashtable,把实例的新旧地址做了对应
此阶段没有STW的,如果有线程正在需要读B和C怎么办了?此时就需要读屏障了:等B和C搬迁到新地址后再读(通过转发表找到),这个有点类似自旋,汇编层面通过jmp slow_path实现;额外开销约4%;那么问题又来了:业务线程怎么知道B和C线程有没有搬迁到新地址了?还是通过对象引用指针的着色确定的;如果4个bit都是0,说明改引用是good color,对象可以直接读写;如果4bit中有任何bit是1,就是bad color,说明正处于GC流程,这种对象是不能马上使用的!
(8)还剩最后一步了:B和C复制到新页面后,原有的引用关系还没恢复了,这个问题什么时候解决了?这就要等到下一次GC启动后的第二阶段:对象重定位阶段进行!这个阶段A->B和B->C的指针都是绿色的,表示上次GC遗留下来没有更新的指针!最终的结果如下:A、B和C在新页面建立引用关系,指针改成红色!
B和C这种间接引用,为啥要放到第二次GC才做了?为啥不第一次就完结了?因为这种可达性分析没必要做两次,可以直接复用第一次的forward table!所以也不需要STW业务线程!
最后通过实测,每个阶段耗时如下:需要STW的是初始标记、再标记和初始转移阶段,3个阶段加起来耗时约0.7ms,这效率杠杠滴!
参考:
1、https://cloud.tencent.com/developer/article/1622989 slab分配一个object的流程分析
2、https://www.dingmos.com/index.php/archives/23/ slab分配器
3、https://www.bilibili.com/video/BV1cb4y117Vg?p=6&spm_id_from=pageDriver ZGC垃圾回收过程
离线
页次: 1