公告
页次： 1
#1 2022-10-09 12:22:07
linux源码解读（十）：内存管理——内存分配和释放关键函数分析&ZGC垃圾回收
上文介绍了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