Understanding ROS Memory Allocator in ART Virtual Machine

原创文章,转载请注明出处.转载自: Li Haifeng's Blog
本文链接地址: Understanding ROS Memory Allocator in ART Virtual Machine

Agenda

1. Run基本结构
2. 主要算法
a)    Allocate
b)    Free
正文

ROS memory allocator Android ART virtual machine GC的一个内存分配器。 ROS Run-of-Slots的缩写。 ROS allocator中,分配的都是虚拟地址区间(具体的物理内存什么时候分配是由kernel中的page fault来负责的)。ROS allocator的基本分配单元是slotslot大小16Bytes2048Bytes,分别是16,32,48,… n*16,512,1024,2048. 不同大小的slot对应不同种类的Run,换句话说,一种Run提供大小相同的slot. 一共有34Run.

, Run的基本结构
一个Run,可以分为两大部分,分别是Run headerData Area。如下所示:
Run header里面包含了
            Magic number: Debug相关
            Size_bracket_idx_: 表示了该Run中的slotsize是多大。比如Size_bracket_idx_10,那么该Run中的slotsize是(10+1*16=176 Bytes.
            Is_thread_local:表示了该Run是否是Thread local area. ROS allocator规定每个线程都会持有一组Thread local Run,该组Runslot size最大为176Bytes. 即,如果某个线程需要分配一个space,若该space不大于176Bytes,那么就从该线程的Run中获得虚拟内存,而不会从ART runtime中获取。
           to_be_bulk_freed_: 该字段是一个flag,用来辅助处理一次释放多个对象的情况。若该标志置位,说明该Run有多个slot正在被释放。若该Runthread local的,那么bulk_free_bitmap的置位信息将会更新到thread_local_free_bitmap中。thread_local_free_bitmap_的信息会在分配thread local slot的时候存在失败的情况下,会更新thread_local_free_bitmap_中的信息到alloc_bitmap_中。若该Run不是thread local的,那么在bulk free的时候,会同步到alloc_bit_map_字段中。alloc_bit_map_是用来在分配slot的时候指示哪些slot已经被分配出去了。
            top_slot_idx_: 一个Run在分配slot的时候,slotRunData Area中的分配顺序是从小到大的。因此该字段表示当前slot分配到哪里了。若需要分配新的slot,只需要在该字段的基础上+1就可以了。可是,在Run分配slot的时候,也会有某些被分配过的slot又被释放的情形。因此若top_slot_idx_到头的情况下,会根据alloc_bit_map_看一下该Run中是否还有空闲的slot可供分配。若有,那么就分配出去。
            alloc_bit_map_[]: Run中的每一个slot在该字段代表一位。若为1,说明slot被分配出去了。若为0,说明该slot还是空闲的。
            bulk_free_bit_map_[]: 每一个slot在该字段中代表1位。若free,置1,该字段会在适当的时候,更新到thread_local_free_bit_map_[]然后在适当的时候更新到alloc_bit_map[]或者直接更新到alloc_bit_map_[],前者对应于该Runthread_local的情况,后者对应于该Run是非thread_local的情况。至于为什么要有这个bulk_free_bit_map_[]字段,是为了性能的考虑,可以减少锁冲突。
            thread_local_free_bit_map_[]: 若该Runthread local的,那么该字段会在slot free的时候置1,当在适当的时候会更新到alloc_bit_map_[]字段中(具体的时机见前面to_be_bulk_freed_的说明)。
            padding 是为了对齐的需要。由于每种Run占用的空间不同(占用的空间包含Run headerData Area),slot的大小,slot的数量都不同,因此三个bitmap(alloc_bit_map_[],bulk_free_bit_map_[],thread_local_free_bit_map_[])所占用的空间大小也不同。而last slot是需要页对其的,因此Data area部分是需要n*slot_size页对其,所以这个padding的空间大小也是每种Run都是不一样的。

slot0,slot 1,…,last slot,是真正的数据区。若没有被分配出去,就是空闲的,若分配出去了,就是已经被使用了。
二,主要算法
1.      分配
当系统向garbage collection请求为一个object分配空间的时候,首先计算该object所占用的空间大小request_size, request_size大于2048Bytes,则直接申请页。否则,根据request_size,查找对应的Run. 系统正在被分配的Run都组织为数组,这些Run数组分为两类,一类是用于分配大于176Bytes的数据块的,另一类是用于分配小于176Bytes的数据块,这类是thread local的。如开头所述,每一slot大小的Run对应于一个索引,slot大小为16Run对应数组中的第0个,数组第n个对应于slot大小为(n+1)*16Run. 找到Run后,
(1)     若该Run为空,表示,该Run还没有向系统申请空间。不过这种情况下并不会立即向系统申请空间,而是会查一下,是否有该种类的Run之前已经全部被分配出去后,又因为有些slot被释放,而又可以被复用的情况。如果有,就用可以复用的Run. 否则,就像系统申请若干虚拟页,每一类的Run在一次填充的时候,需要的页数都是不一样的,具体的页数存放在numOfPages[]数组中。所有slot用完的Run都存放在full_runs_hash_set中。而由于有slot被释放而又有可用的slotRun则存放在non_full_runs_Set中。
(2)     若该Run非空,先查一下top_slot_idx_字段,若该字段并没有到达结尾,就返回一个slot,并把top_slot_idx_字段加1。若top_slot_idx_字段已经到达结尾,那么会搜索一下有没有在该Run中已经分配出去的slot由释放的情况,如果有,分配出去。若该Runslot都用满了,那就看看该Run是不是thread local的,如果是的话,将thread_local_free_bit_map_[]中的信息同步过来,看是否有用的slot. 若至此仍然没有找到一个可用的slot,那把该Run加入到full_runs_hash_set中。重新分配一个Run,向系统申请页. 然后在从该Run中分配slot. 每分配一个slot 就会将alloc_bit_map_中对应的bit1,表示该slot被分配出去了。
2.     释放
若某个object被释放后,根据该object的地址,rundown成页地址,根据页地址去查询该页的用途。对于一个ROS系统所拥有的虚拟页都是连续的,事先通过mmap的方式分配得到。ROS系统维护了一个page_map_的数组。每一页对应一个Byte. 如果该页用于slot分配的Run,Run占用的第一页在page_map_中对应的byte设置为枚举常量kPageMapRun, 剩余页被设置为枚举kPageMapRun。因此当释放某个object的时候,根据地址以及page_map_可以得到Run在内存中的地址。 如果该object属于Largeobjectpage_map_中对应的byte的值为kPageMapLargeObject),那就直接释放该页。
若该页在page_map_中对应的byte的值为kPageMapRun,就在对应的Run中将alloc_bit_map slot的对应位清0.说明该slot空闲了。若该slot对应的Run并非系统正在使用的Run(Run因为slot被用完后,系统又分配了新的slot),那么就将该Runfull_runs_中移到non_full_runs中。如果该Run此时全部为free了,就会将该Run分解掉,其占用的pages退回到free_pages_set中。而如果该Runthread local的,那么该Run是不会被退回的,因为若该Runthread local的情况下,该Run一定属于当前正在使用的Run。如果thread localRun中的slot全部被消耗完了,会被扔到full_runs_中,其thread local的属性也会被去掉。
三,参考

From Li Haifeng's Blog, post Understanding ROS Memory Allocator in ART Virtual Machine

Post Footer automatically generated by wp-posturl plugin for wordpress.

分享到: