首页 » 技术文章 » 【源码解读】mono内存管理及gc源码阅读

【源码解读】mono内存管理及gc源码阅读

 

简介

Mono支持内存自动回收,因为MONO集成了内存回收算法。在1.X到2.X的版本中,MONO集成了贝母内存管理及回收算法;而在3.X或更高版本中,则开始启用SGEN内存管理及回收算法。本周研究了2.6.X版本的BOEHM(贝母)的内存管理及GC算法部分代码。BOEHM属于一个开源项目,其实现为支持C/C的内存管理及GC,在C/C项目中,将分配内存部分接口(malloc或者其他分配内存等接口)替换成BOEHM提供的内存分配接口(GC_malloc),则可以在C/C++项目中实现内存自动管理,无需手动调用free等释放内存接口。而MONO正是基于BOEHM,实现了内存管理及自动GC。

GC实现的方式

对于GC实现的方式有许多种: 引用计数算法;引用技术算法是唯一一种不用用到根集概念的GC算法。其基本思路是为每个对象加一个计数器,计数器记录的是所有指向该对象的引用数量。每次有一个新的引用指向这个对象时,计数器加一;反之,如果指向该对象的引用被置空或指向其它对象,则计数器减一。当计数器的值为0时,则自动删除这个对象。 Mark & Sweep 算法:也叫标记清除算法,标记阶段通过标记所有根节点可达的对象,未被标记的对象则表示无引用,可回收,BOEHM正是使用该算法实现内存自动回收; 节点复制算法:将活的节点复制到新内存区,老内存区一次性释放,对象会被转移,应该还需要设置元数据中间层,具体实现未做研究;

BOEHM算法内存管理

BOEHM算法采用标记清除法,在标记阶段通过访问根节点,并遍历到叶子节点,最终将所有存在引用的内存都标记出来,而未标记的内存(所有从堆中分配的内存BOEHM中均有记录,因此可将未标记的部分清除释放掉)。下面介绍BOEHM分配内存过程。在介绍分配流程之前,先介绍关键数据结构。

GC_size_map[2049],一个MAXOBJBYTES(2048+1)个元素的数组,每个数组为一个整数值,分配该内存为了在分配内存时快速定位出分配的粒度的倍数(其实完全可以用(bytes+16-1)/16来规避掉这个数组,这么做应该是为了减少计算量...),而16这个是BOEHM分配内存的最小粒度,也就是说分配1字节,BOEHM也会给你分配16字节的内存(我这里看代码时是根据64位机器定义的宏来分析的,不同平台字节略有差异,不影响分析)。同时若分配的内存大小大于2048时,此时要执行另一个大内存分配分支(由于流程大同小异,因此对大内存分配暂时做研究,下述介绍均为对2048个字节内的内存分配及回收介绍)。

GC_obj_kinds[3] 三个元素的数组,BOEHM定义这个数组是为了区分分配的内存类型,在BOEHM中,存在存储指针内存,普通内存和非回收内存之分,本周的分析为普通内存分配的流程(因为这是应用程序调用最为频繁,而非回收内存属于BOEHM自己为了最到内存管理而分配的内存,这些内存不需要标记和回收的),每个元素包含一个ok_freelist[MAXOBJGRANULES+1]的数组,MAXOBJGRANULES为128,为128的原因是,每个GRANULES是一个分配粒度,即16字节,那么12816=2048,刚好是能分配的小内存的上限。ok_freelist这个数组每个元素为一个空闲链表的指针,指向的内存块大小是index16,即第一个元素存储16个字节大小块的内存块链表指针,而第128个元素存储的链表中内存块大小为128*16=2048的内存块大小的指针。这个数组保存的内存块大小作用为:当分配内存时,会优先检查该链表是否存在FREE块,若存在,则直接可以在链表中取出一块返回给应用上层,若否,则会再调用分配函数,分配较大一块内存,然后将大内存分割为小内存链表存储在ok_freelist中(具体存储INDEX由上层分配的内存大小需要几个GRANULE决定)。

GC_hblkfreelist[N_HBLK_FLS+1]数组N_HBLK_FLS=28(为何是这个值是因为设计就是这样),GC_hblkfreelist每个元素存储的也是一个空闲内存链表,与ok_freelist不同的是,它的内存基本块大小是PAGE_SIZE,即4096,与ok_freelist类似,每个元素存储的链表块大小与index相关,可以这么理解,第一个元素的链表内存块大小为PAGE_SIZE,第二个为PAGE_SIZE*2,以此类推。由于本文只介绍小内存分配,因此不需要考虑特别大内存分配的处理方式。当需要分配内存时,例如当请求分配16个字节的内存时(上层调用下来的已经进行粒度GRANULE对齐了),此时会将其进行(bytes+PAGE_SIZE-1)/PAGE_SIZE得到index,然后检测GC_hblkfreelist[index]是否存在空闲快,若无则会继续向后遍历,找到后,将大块拆分成小块,再重新将两个小块的后一块推入GC_hblkfreelist合适的位置,将前一块用来分配,由于上层只分配16字节内存,当给了上层PAGE_SIZE大小的内存,此时会将该内存按照16字节划分,并生成链表(链表指针无需额外增加内存,只用16字节的中的前8个字节作为指针即可),将链表存储到ok_freelist[1]中,此时上层就能完成内存分配。GC_hblkfreelist中的内存则是通过下述调用来分配:

#1  0x00002aaaaaabeb66 in GC_add_to_heap (p=0x64e000, bytes=65536) at alloc.c:770
#2  0x00002aaaaaabef7a in GC_expand_hp_inner (n=16) at alloc.c:903
#3  0x00002aaaaaaca781 in GC_init_inner () at misc.c:713
#4  0x00002aaaaaaca2f9 in GC_init () at misc.c:428
#5  0x0000000000402f95 in main () at test.c:1351

从上可以看出,一个内存分配过程,首先会检测ok_freelist链表,若存在FREE块,则直接取出返回(当然会设置使用标记,GC会使用),若ok_freelist中无对应大小的内存,则从GC_hblkfreelist调用获取PAGE_SIZE内存并存储,下次再分配就可以直接从ok_freelist中取得了,相当于做了一个简型内存池。

Hblkhdr数据结构,此数据结构为关键数据结构,GC能否正常运行全靠这个块信息描述。当从GC_hblkfreelist分配PAGE_SIZE的一块内存时,会生成一个hblkhdr的对象,此对象描述该PAGE_SIZE内存块,该hblkhdr会存储(hb_sz, hb_mark5,descr等信息),hb_sz存储上层分配的传递的内存块大小,当分配16字节时,hb_sz就会被设置为16,设置这个元素的作用就是为了知晓存储在该PAGE中的元素的大小(若分配16字节,说明上层分配内存存储的对象最大为16字节),而hb_mark用来存储该PAGE哪些块被使用(每个BIT可以描述一个小块,每个小块最小为16字节,因此5个8字节有足够的BIT位来描述一个PAGE,因为可以描述588*16个字节,超过了4096个字节)。

分配好HBLKHDR结构后,它会被存储到二级数组中,存储方式为(这里假定PAGE的起始位置为P指针) top_index[p>>22]->bottom_index[p>>12 & 1024]的位置,12是因为每个PAGE为4096字节,即2的12次方。即会把每个PAGE的地址的高10位作为索引,中10位作为索引,在二级数组中存储该HBLKHDR(当然,这个二级数组并非一启动就生成这么大的二级数组,而是运行过程中生成(否则过于浪费内存,如果一开始就生成,则至少需要102410248,即8M内存,而很多巢位在运行期间根本不会被用到)),生成了这个数据后,任何一个指针都可以找到它属于的HBLKHDR的描述符,而根据该描述符,可以知晓该指针指向的对象最大的内存块大小以及它的标记情况(hb_sz和hb_mark)。

介绍完上述之后,大概可以有一个思路,分配内存的大体流程为:先检查ok_freelist---->GC_hblkfreelist--->分配一个PAGE--->并分配描述HBLKHDR。其进行的函数调用堆栈为:

#1  0x00002aaaaaabd52d in GC_allochblk_nth (sz=16, kind=1, flags=0, n=16) at allchblk.c:769  这里从GC_hblkfreelist分配内存
#2  0x00002aaaaaabce3a in GC_allochblk (sz=16, kind=1, flags=0) at allchblk.c:577
#3  0x00002aaaaaacb75a in GC_new_hblk (gran=1, kind=1) at new_hblk.c:190
#4  0x00002aaaaaabf2ef in GC_allocobj (gran=1, kind=1) at alloc.c:1002
#5  0x00002aaaaaac4a28 in GC_generic_malloc_inner (lb=7, k=1) at malloc.c:119 这里尝试从ok_freelist中分配内存
#6  0x00002aaaaaac4bbc in GC_generic_malloc (lb=7, k=1) at malloc.c:159
#7  0x00002aaaaaac5041 in GC_core_malloc (lb=7) at malloc.c:272
#8  0x00002aaaaaad0283 in GC_malloc (bytes=7) at thread_local_alloc.c:176
#9  0x00000000004026eb in run_one_test () at test.c:1037
#10 0x0000000000402fcc in main () at test.c:1367

也会调用setup_header用来初始化对应的HBLKHDR,调用GC_install_header来分配第二级数组及分配HBLKHDR(这个结构是从非回收内存中分配的)。

上述描述可以看出,BOEHM分配的内存指针通过32BIT来描述,如果同时存在64BIT的内存和32BIT的内存低地址位相同,那么就会冲突,BOEHM通过其他方式规避该问题(通过指定分配内存的起始位置(这里没详细看,linux它是通过sbrk来分配内存,GDB也发现了这一点,由于不影响分析流程,所以对于该细节未做过多研究))。

BOEHM GC原理

上述介绍了BOEHM分配内存的原理,这里介绍其GC原理。从上述分配原理中知道,给出一个指针,可以根据二级数组找到HBLKHDR的描述信息,根据HBLKHDR又能知道其对应的OBJ大小。再根据指针对齐原理,知道指针会存储在OBJ内的地方(遍历整个OBJ,将可能为指针的都拿出来检查)。经过这几层可以得到引用树。

具体实现为首先将所有线程暂停(pthread_kill SUSPEND,当然不能把自己这个线程也挂起,相关宏为#define STOP_WORLD GC_stop_world),然后访问各个线程的堆栈顶及底部(GC创建每个线程时会获取底部指针,而线程在处理SUSPEND信号时,会将当前栈顶指针保存到GC_THREAD结构中,每个线程都对应一个GC_THREAD结构),然后遍历所有线程的栈内存,按照指针存储对齐原理,获取可能的指针(判定该指针是否是有效指针的方式是:BOEHM会保存自己从HEAP分配内存的最低地址和最高地址,若判定的指针位于该区间,则认为其可能为一个指针),再通过二级数组获取该指针对应的HBLKHDR,若未找到(这种属于异常情况了,未找到,却可能被引用,有可能是非BOEHM分配的内存,则将该内存对应PAGE地址放入BLACKLIST中,不能用来分配了,否则有几率存在碰撞可能,一般情况下很少会发生,这个应该是BOEHM后来打的补丁,暂不关注),找到HBLKHDR后,会检查该PAGE是否为空闲状态(已被分配到ok_freelist中后,PAGE会被设置为非空闲),若为空闲,则忽略该指针(因为未指向有效对象),若是,则标记该指针指向的OBJ为使用状态,并将对应的标记位设置为可用(每给出一个指针,都能根据HBLKHDR知道该OBJ的大小,因为其中存储了hb_sz字段),然后再遍历该OBJ,找出可能的指针,并一一标记。

在整个标记过程开始前,GC会清除所有HBLKHDR的标记字段(此时其他线程已暂停),所有的HBLKHDR有一个队列头,遍历队列能获取到所有的HBLKHDR。然后标记完成后,被标记的说明存在引用,未被标记的则会被释放到ok_freelist,若整个HBLKHDR所有标记都未被设置,则会将HBLKHDR还回到GC_hblkfreelist中,并且会根据其地址,将相邻的PAGE合并成大PAGE再调整其在GC_hblkfreelist中的存储位置。

这里介绍时忽略了其执行的细节(因为研究时重点看了其管理内存的方式,对于回收分为几个过程,并通过管理回收状态来标记和清扫,并最终回收,整个过程的代码较为晦涩,所以只管理其重点部分)。

相关堆栈

#1  0x00002aaaaaac8658 in GC_push_all_eager (bottom=0x7fffffffe538 "8\345\377\377\377\177", top=0x7fffffffe9d0 "\001") at mark.c:1516
#2  0x00002aaaaaac868d in GC_push_all_stack (bottom=0x7fffffffe538 "8\345\377\377\377\177", top=0x7fffffffe9d0 "\001") at mark.c:1565 处理单个堆栈
#3  0x00002aaaaaad1bc4 in GC_push_all_stacks () at pthread_stop_world.c:290  这里是将所有堆栈进行处理
#4  0x00002aaaaaacc95b in GC_default_push_other_roots () at os_dep.c:2255
#5  0x00002aaaaaac9df0 in GC_push_roots (all=0, cold_gc_frame=0x7fffffffe628 "") at mark_rts.c:611
#6  0x00002aaaaaac68e8 in GC_mark_some (cold_gc_frame=0x7fffffffe628 "") at mark.c:350
#7  0x00002aaaaaabe2a8 in GC_stopped_mark (stop_func=0x2aaaaaabd8d7 <GC_timeout_stop_func>) at alloc.c:484
#8  0x00002aaaaaabdd71 in GC_maybe_gc () at alloc.c:285
#9  0x00002aaaaaabe0ee in GC_collect_a_little_inner (n=1) at alloc.c:419
#10 0x00002aaaaaabf33e in GC_allocobj (gran=84, kind=1) at alloc.c:997
#11 0x00002aaaaaac4aa8 in GC_generic_malloc_inner (lb=1024, k=1) at malloc.c:119
#12 0x00002aaaaaac4c3c in GC_generic_malloc (lb=1024, k=1) at malloc.c:159
#13 0x00002aaaaaac50c1 in GC_core_malloc (lb=1024) at malloc.c:272
#14 0x00002aaaaaad02e6 in GC_malloc (bytes=1024) at thread_local_alloc.c:176
#15 0x00000000004023e9 in xxxdddd () at test.c:1019
#16 0x0000000000402429 in run_one_test () at test.c:1042
#17 0x00000000004027a1 in main () at test.c:1385

这里未研究其他全局数据GC方式,原理跟堆栈中引用类似。

总结

MONO按照16字节内存的对齐方式分配内存,每分配一个对象时,会根据其内存大小并尝试分配ok_freelist,若程序存在一堆小内存对象,且其对象大小为16,32,48等内存大小,则会生成三个ok_freelist链表,每个链表占用了一个PAGE,若这些对象数量不大,则会导致内存的浪费。将16和32字节大小的对象定义更大,让其接近48字节,这样所有的小对象都未48字节,反而能节省MONO内存(因为只用分配一个PAGE即可以满足这些小内存对象的分配)。 定义的对象占用内存尽量压缩,因为GC时会遍历整个OBJ,因此如果OBJ越大,那么GC访问的内存就会越多,当然也就越慢,因此对象在能实现机制的前提下,越小越好。

上述两条看起来有些冲突,其表达的意思是:对于一些小对象,尽量让其按照某一个GRANULE对齐(当然,若某种GRANULE的对象有很多,则不需要特地处理),尽量节省内存(因为如果某个GRANULE的对象很少,则浪费了1整个PAGE);而GC会遍历内存,因此定义对象时,内存能用更小的字节表达,则尽量小,一些字段顺序进行调整能使得编译时进行内存对齐的开销更小,有可能也能节省部分内存。

相关资源及从系统分配内存对齐方式

Mono官网http://www.mono-project.com/docs/

BOEHM项目官网http://www.hboehm.info/

其使用到的与从堆中分配内存相关的函数为sbrk,同时也调用了一个不常用的函数mprotect,用来改变内存段属性(会用来作为辅助调试的方式),在预分配时先改为PROT_NONE,只有真正分配给应用使用时,才设置为可访问,这样如果存在内存越界等行为,可以在测试阶段发现。 GC_unix_sbrk_get_mem接口会调用sbrk,分配内存前会保证分配给上层的地址是按照页面对齐的,其具体实现为:

ptr_t cur_brk = (ptr_t)sbrk(0);
    SBRK_ARG_T lsbs = (word)cur_brk & (GC_page_size-1);
    if ((SBRK_ARG_T)bytes < 0) {
  result = 0; /* too big */
  goto out;
    }
    if (lsbs != 0) {  如果没有对齐
        if((ptr_t)sbrk(GC_page_size - lsbs) == (ptr_t)(-1)) { 则分配一块废内存,占用这片空间
      result = 0;
      goto out;
  }

因为其上面所描述的分配HBLKHDR描述PAGE块时,基本前提是内存块按照PAGE_SIZE对齐。

CUBE调用的部分接口回顾

  • 通过阅读MONO GC算法,回头再看CUBE调用的接口mono_object_is_alive,就比较容易理解了,是通过读取二级数组获取到对应指针的HBLKHDR后,查找其中对应的hb_mark BIT位,来判定某个OBJ是否存活;
  • Cube通过调用mono_object_is_alive来判定对象存活,然后该接口在sgen GC算法中已废弃,若UNITY后续更新MONO版本,CUBE该功能将可能失效(需要用新的方式);
  • Mono_object_is_alive一定要在gc_collect()调用完成后才能调用,否则无法获取到正确信息(因为只有GC完成后才能判定是否存活,在GC_malloc调用后,并不会设置HBLKHDR相应的mark标记(这么做应该为了简便,因为只有GC回收内存时才需要标记,分配内存不标记,待GC阶段再标记));

本文作者:马良

原文链接:【源码解读】mono内存管理及gc源码阅读,转载请注明来源!

0