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的基本分配单元是slot。slot大小从16Bytes到2048Bytes，分别是16,32,48,… n*16,512,1024,2048. 不同大小的slot对应不同种类的Run，换句话说，一种Run提供大小相同的slot. 一共有34种Run.
一, Run的基本结构
一个Run,可以分为两大部分，分别是Run header和Data Area。如下所示：
Run header里面包含了
∙ Magic number: Debug相关
∙ Size_bracket_idx_: 表示了该Run中的slot的size是多大。比如Size_bracket_idx_是10，那么该Run中的slot的size是（10+1）*16=176 Bytes.
∙ Is_thread_local:表示了该Run是否是Thread local area. ROS allocator规定每个线程都会持有一组Thread local Run，该组Run的slot size最大为176Bytes. 即，如果某个线程需要分配一个space，若该space不大于176Bytes，那么就从该线程的Run中获得虚拟内存，而不会从ART runtime中获取。
∙ to_be_bulk_freed_: 该字段是一个flag，用来辅助处理一次释放多个对象的情况。若该标志置位，说明该Run有多个slot正在被释放。若该Run是thread 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的时候，slot在Run的Data 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_[]，前者对应于该Run是thread_local的情况，后者对应于该Run是非thread_local的情况。至于为什么要有这个bulk_free_bit_map_[]字段，是为了性能的考虑，可以减少锁冲突。
∙ thread_local_free_bit_map_[]: 若该Run是thread local的，那么该字段会在slot free的时候置1，当在适当的时候会更新到alloc_bit_map_[]字段中（具体的时机见前面to_be_bulk_freed_的说明）。
∙ padding 是为了对齐的需要。由于每种Run占用的空间不同（占用的空间包含Run header和Data 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，是真正的数据区。若没有被分配出去，就是空闲的，若分配出去了，就是已经被使用了。
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大小为16的Run对应数组中的第0个，数组第n个对应于slot大小为(n+1)*16的Run. 找到Run后，
(1) 若该Run为空，表示，该Run还没有向系统申请空间。不过这种情况下并不会立即向系统申请空间，而是会查一下，是否有该种类的Run之前已经全部被分配出去后，又因为有些slot被释放，而又可以被复用的情况。如果有，就用可以复用的Run. 否则，就像系统申请若干虚拟页，每一类的Run在一次填充的时候，需要的页数都是不一样的，具体的页数存放在numOfPages[]数组中。所有slot用完的Run都存放在full_runs_的hash_set中。而由于有slot被释放而又有可用的slot的Run则存放在non_full_runs_的Set中。
(2) 若该Run非空，先查一下top_slot_idx_字段，若该字段并没有到达结尾，就返回一个slot，并把top_slot_idx_字段加1。若top_slot_idx_字段已经到达结尾，那么会搜索一下有没有在该Run中已经分配出去的slot由释放的情况，如果有，分配出去。若该Run的slot都用满了，那就看看该Run是不是thread local的，如果是的话，将thread_local_free_bit_map_[]中的信息同步过来，看是否有用的slot. 若至此仍然没有找到一个可用的slot，那把该Run加入到full_runs_的hash_set中。重新分配一个Run，向系统申请页. 然后在从该Run中分配slot. 每分配一个slot 就会将alloc_bit_map_中对应的bit置1，表示该slot被分配出去了。
2. 释放
若某个object被释放后，根据该object的地址，rundown成页地址，根据页地址去查询该页的用途。对于一个ROS系统所拥有的虚拟页都是连续的，事先通过mmap的方式分配得到。ROS系统维护了一个page_map_的数组。每一页对应一个Byte. 如果该页用于slot分配的Run,该Run占用的第一页在page_map_中对应的byte设置为枚举常量kPageMapRun, 剩余页被设置为枚举kPageMapRun。因此当释放某个object的时候，根据地址以及page_map_可以得到Run在内存中的地址。 如果该object属于Largeobject（page_map_中对应的byte的值为kPageMapLargeObject），那就直接释放该页。
若该页在page_map_中对应的byte的值为kPageMapRun，就在对应的Run中将alloc_bit_map 该slot的对应位清0.说明该slot空闲了。若该slot对应的Run并非系统正在使用的Run(该Run因为slot被用完后，系统又分配了新的slot)，那么就将该Run从full_runs_中移到non_full_runs中。如果该Run此时全部为free了，就会将该Run分解掉，其占用的pages退回到free_pages_的set中。而如果该Run为thread local的，那么该Run是不会被退回的，因为若该Run为thread local的情况下，该Run一定属于当前正在使用的Run。如果thread local的Run中的slot全部被消耗完了，会被扔到full_runs_中，其thread local的属性也会被去掉。
三，参考
评论
发表评论