来源

llvm项目 https://github.com/llvm/llvm-project , android aosp进行了定制

这是一个概念

概念

scudo 大概分为以下几个部分：

前端FrontEnd：使用Primary或Secondary后端来分配内存，还包括在初始化时根据配置（环境变量或者hook callback）来设置一些运行时参数：比如gc的时间、是否检查一些错误等。
Primary后端: 对应aosp上用的是SizeClassAllocator64，负责小内存分配，最大支持0x10010大小的分配（这个大小还要包括chunk header的大小，且是对齐后的），Primary后端在初始化的时候就会为每个size class mmap 256M的VM（没有commit的）供前端使用。
Secondary后端: 对于无法从Primary分配的大内存，这里会直接用mmap去分配。
TSDRegistrySharedT：从名称能看出来这种tsd是多线程共享的。从下面的AndroidConfig能看到aosp上最多两个TSD(min(2, cpus))，即多个线程共享一个TSD中缓存的内存block。
AndroidSizeClassMap：简单认为size class table的配置，即多少种slab，每种slab的元素的大小。slab是针对小内存提出的概念

配置

Android 添加了scudo的相关配置, 下面很多地方用到了这里面的配置

struct AndroidSizeClassConfig {
#if SCUDO_WORDSIZE == 64U
  ...
  static constexpr u32 Classes[] = {
      0x00020, 0x00030, 0x00040, 0x00050, 0x00060, 0x00070, 0x00090, 0x000b0,
      0x000c0, 0x000e0, 0x00120, 0x00160, 0x001c0, 0x00250, 0x00320, 0x00450,
      0x00670, 0x00830, 0x00a10, 0x00c30, 0x01010, 0x01210, 0x01bd0, 0x02210,
      0x02d90, 0x03790, 0x04010, 0x04810, 0x05a10, 0x07310, 0x08210, 0x10010,
  };
  struct AndroidConfig {
  using SizeClassMap = AndroidSizeClassMap;
#if SCUDO_CAN_USE_PRIMARY64
  // 256MB regions  2^28 = 256M 一次map 256M * NumClasses 空间 
  typedef SizeClassAllocator64<SizeClassMap, 28U, 1000, 1000,
                               /*MaySupportMemoryTagging=*/true>
      Primary;
#else
  // 256KB regions 2^18 = 256k 一次map 256k * NumClasses  32位上
  typedef SizeClassAllocator32<SizeClassMap, 18U, 1000, 1000> Primary;
#endif
  // Cache blocks up to 2MB
  typedef MapAllocator<MapAllocatorCache<256U, 32U, 2UL << 20, 0, 1000>>
      Secondary;
  template <class A>
  using TSDRegistryT = TSDRegistrySharedT<A, 8U, 2U>; // Shared, max 8 TSDs.
  setNumberOfTSDs((NumberOfCPUs == 0) ? DefaultTSDCount
                                        : Min(NumberOfCPUs, DefaultTSDCount))
};

ChunkHeader

每个堆内存块的前面都会有一个块标头。这有两个目的，第一个目的是存储有关块的各种信息，第二个目的是检测潜在的堆溢出。为了实现这一点，将对报头进行校验和，包括指向区块本身的指针和全局密码。当访问所述报头时，将检测到所述报头的任何损坏。

以下信息存储在报头中：

16位checksum；Checksum
该块的类ID，对于Primary后端的分配，它是块“缓存池”的id；对于Secondary分配器, 该值是0；ClassId
该区块的大小(Primary后端)或未使用的字节（Secondary后端)，这是计算区块大小所必需的； SizeOrUnUsedBytes
数据块的状态(可用、已分配或已隔离)； Available/Allocated/Quarantined State
分配类型(Malloc、New、NewArray或Memalign)，用于检测使用的分配API中可能不匹配的情况； Origin
在所有支持的平台上，此标头的大小均在8字节以内。

把全局密码(每次程序执行时生成一把随机key) 、区块指针本身和 checksum字段清零的8字节chunkheader 计算CRC32值作为checksum存储在chunkheader中 (在硬件支持下速度更快)。

分配流程

Primary

Secondary

分配流程图

RegionInfo 对应了RegionSize classId的一整块区域, RegionInfo 的FreeList维持了一个长的链列, 在FreeList取出TransferBatch, 填给PerClass, 如果取出为空, 则需要重新装填FreeList, mmap分配内存, 并按ClassId size 切片打包装入TransferBatch, 挂到FreeList 链队中. 是在populateBatches中处理的. PerClass 为容量较小的缓存, PerClass退Batch的过程可以理解成子弹出弹夹的过程, 当弹夹为空后, 需要从RegionInfoArray[classId]的FreeList 出来TransferBatch, 打包装填PerClass的Chunks, PerClass的Chunks数组容量是两倍的TransferBatch的大小, 一次装填只能填入一半.

PerClass Chunks 可以理解成枪的弹夹, 只能存少量的子弹, 而FreeList可以理解成补给兵的备用弹夹, TransferBatch则是用来一次装填枪弹夹的弹药包. mmap的过程理解成兵工厂制作备用弹夹的过程, 而classId的内存单元比成子弹. 子弹分不同的口径, classId 有不同的size. 生产出子弹后, 打乱子弹的编号, 放到弹药包中, 防止利用子弹的编号规律查到一些信息. 而这里则是为了更安全, 连续 malloc相同classid的内存单元, 内存地址不会是连续的, 规避漏洞.

释放隔离流程

启用隔离

默认没有启动隔离区, 需要在主程序中实现该方法, 配置scudo 参数.

// 示例代码
extern "C" __attribute__((visibility("default"))) const char *
__scudo_default_options() {
  return "quarantine_size_kb=256:thread_local_quarantine_size_kb=128:"
         "quarantine_max_chunk_size=512:";
}

释放流程

如有需要会先对指针untag，然后加载Chunk的Header（这里会做checksum检查，以及分配类型是否匹配：malloc/free，delete/new），再根据入参的ptr获得用户分配的size大小（做delete size mismatch检查）。
deallocate有两种去向，即是否需要进行Quarantine，如果不需要则进行步骤3释放回后端（Primary或Secondary）, 否则进行隔离(这个是为了检测UAF错误)。
通过chunck header得到真正的从后端拿到的block的地址，根据class id决定释放到Primary还是Secondary中。class id = 0 代表是从secondary后端分配。
对于Secondary后端，如果释放的block小于2M，则先尝试放到MapAllocatorCache的CacheBlock数组中，如果成功放入数组，会将当前时间作为这个block释放的时间，还会根据配置的gc时间间隔将数组中老化时间超过gc间隔的block释放掉（madvise而不是munmap）, 调用releaseOlderThan。 另外一种情况如果在放回CacheBlock数组的时候发现数组满了(累计4次)，则会unmap所有block，同时当前被释放的block也会被unmap(store过程中做的)。
对于Primary后端，首先还是拿到当前线程对应的TSD并获取TSD中的cache，如果cache不满则直接放到cache中，free到此结束。如果cache满了，则将cache中一半数量的缓存block返回给Primary对应Region的freelist中，然后再将当前被释放的block放到cache中。cache返回给primary对应region之后会判断是否需要做madvise释放free list 中的 block占用的pss(物理内存 MADV_DONTNEED)，依据包含：上次freelist释放pss的时间以及gc间隔判断老化时间是否足够，以及freelist中的block大小( 调用releaseToOSMaybe(Region, ClassId)函数 -> FreePagesRangeTracker.finish() -> closeOpenedRange -> releasePageRangeToOS)
1
2
Region->CanRelease = (I != SizeClassMap::BatchClassId) &&
(getSizeByClassId(I) >= (PageSize / 32))

隔离区 QuarantineBatch 退回的过程

QuarantineBatch 托管了要释放的指针, 而不用管具体的指针指向的内存属于哪个RegionSize类

从QuarantineCache 开始看, 这个是一个用于保存延迟释放隔离内存区的类, TSD相关的QuarantineCache类中保存了一个List, 链接该线程所有的QuarantineBatch. Size成员保存了已经放到隔离区的总的内存大小. QuarantineBatch中保存了一个Batch[MaxCount]的数组. 该数组中保存了要释放的指针(指针的ChunkHeader的状态已经变成 Chunk::State::Quarantined). 一个QuarantineBatch最大放MaxCount(1019)个指针.

在放入隔离区时, 先往TSD的QuarantineCache中放, 当TSD的QuarantineCache的内存Size > getCacheSize 时(即配置了thread_local_quarantine_size_kb的值), 会将TSD的QuarantineCache整个移入Global QuarantineCache, TSD的QuarantineCache会重置. 然后再判断Global的 QuarantineCache 下的总内存是否大于MinSize(0.9*quarantine_size_kb), 则出队移入tmp, 这里采用QuarantineBatch 一个一个从全局Cache出队, 直到满足<MinSize为止. 出队的QuarantineBatch会进行回收, 同时释放QuarantineBatch 结构.

参数配置

// 示例代码
int main() {
    mallopt(M_CACHE_COUNT_MAX, 100);
    mallopt(M_CACHE_SIZE_MAX, 1024 * 1024 * 2);
    mallopt(M_TSDS_COUNT_MAX, 8);
    ...
}

M_TSDS_COUNT_MAX

设置线程局部存储(TSL)相关的TSD的数目, M_TSDS_COUNT_MAX设置为8后, 如小于等于8个线程, 每个线程会绑定一个TSD.

在每个线程中使用malloc free时, 会根据线程状态寄存器查找到其绑定的TSD缓存池.

scudo没有外部配置的情况下, 只有两个TSD缓存池, 在配置M_TSDS_COUNT_MAX后, 会产生最多M_TSDS_COUNT_MAX个缓存池, 该值会影响 small(primary) 分配器. 在TSD缓存池少的情况下, 会出现多个线程共用一个TSD缓存池的情况, 分配释放内存时需要等锁.

Secondary 分配器没有绑定TSD(不是线程私有), 是所有线程共用同一块缓存池, 分配释放需要加锁等锁.

jemalloc5 中在sz index(36-45范围内的), 对应几十k字节的large类使用的缓存是绑定tcache的(线程私有).
M_CACHE_COUNT_MAX

option->MaxCacheEntriesCount

large(Secondary) 分配器在分配释放内存时, 所有线程共用的缓存池的容量, 每次free 时, 会先将该内存单元放到缓存池中, 下次malloc时, 会优先根据分配的size 在缓存池中查找是否有匹配的缓存内存单元, 如果有则直接把该内存单元的地址返回给调用方.

large(Secondary)的缓存池在满了以后, 下一次free时, 会重置清空缓存池

该值对应上图的 EntriesArraySize, 默认值为32, 最大只能设置到256, 如果超过256, 会设置失败, 用默认值.
M_CACHE_SIZE_MAX

option->MaxCacheEntrySize

在free时, large(Secondary) 分配器并不是将所有大于small分配器的内存单元全部放到缓存池中, 而是在 0x40010-M_CACHE_SIZE_MAX范围内的会在free时放到缓存池中(small的范围0-0x40010), malloc时会优先从缓存池中查找. 而大于M_CACHE_SIZE_MAX的malloc则直接走mmap, free走unmap.

该值对应上图的 MaxEntrySize, 默认值是2M

脚本使用

primary分配器perclass中最近缓存的可用地址已用地址的分析, map region区域中的地址单元的状态分析, 包括header state / class_size / 分配的大小等
secondary分配器中的地址单元的分析, 所有使用状态和free后的地址单元的状态解析
给定chunk header的地址, 打印其header的状态
给定一个内存地址, 搜索其命中的内存区域(perclass/RegionInfo/secondary used/secondary cached), 如果命中, 给出其分析状态
统计功能, 分析所有使用状态的内存地址单元(如果有映射虚表), 按照命中次数/分配的总大小来进行统计, 给出降序的统计结果
离线功能结合tombstones 分析内存地址chunk header的状态
Primary分配器中分析每个线程绑定了哪个perclass.

怎样查看tsd绑定到哪些线程?

scudo 把tsd (Allocator)的首地址写到了 tpidr_el0 向后偏移6个指针的位置, tpidr_el0 寄存器的地址在tls区域. 线程在创建时, 会将tls的相关数据结构存储在pthread_internal_t类型的结构中, 并挂到链表中, g_thread_list为该链表的表头. 通过解析g_thread_list, 找到bionic_tls区域, 在该区域前面为bionic_tcb区域, tpidr_el0的地址即为bionic_tcb区域的首地址. 解析该区域即可将Allocator 的地址找到. 在加载linker后, g_thread_list会变成linker bss段的符号, 解析会出错, 这个时候再想解析, 可以通过dump libc bss段, 检索g_thread_list 符号的方法.

有些地址已经被换出perclass了, 就会丢失tsd的信息, 如果想确定这部分数据与线程的关系, 是获取不了的

class_id   tsd_ind    count    max_count    class_size
-------------------------------------------------------
0           0      12       28           128       
1           0      14       28           32        
2           0      11       28           48        
3           0      9        28           64        
4           0      11       28           80        
5           0      10       28           96        
6           0      15       28           112       
7           0      4        28           144       
8           0      7        28           176       
9           0      13       28           192       
...   
0           1      7        28           128       
1           1      14       28           32        
2           1      23       28           48        
3           1      15       28           64        
4           1      14       28           80        
5           1      15       28           96        
6           1      14       28           112       
7           1      14       28           144       
8           1      11       28           176       
9           1      14       28           192       
...
tid     tsd_ind    tsd_addr    
-----------------------------------
8380    0          0x73eea5a780
711     0          0x73eea5a780
709     1          0x73eea5cc80
694     0          0x73eea5a780
652     1          0x73eea5cc80
651     0          0x73eea5a780
650     1          0x73eea5cc80
628     0          0x73eea5a780

脚本使用与维护

1 2	git clone ssh://<user>@gerrit.pt.mioffice.cn:29418/miui/bootable/recovery-tools git push ssh://<user>@gerrit.pt.mioffice.cn:29418/miui/bootable/recovery-tools HEAD:refs/for/master

可以参考 scudo_shadow/gdb_scripts下的脚本定制自己的gdb 脚本(包括gdb elf/gdb remote attach elf/gdb coredump).

目前发现有些lib库里面定义的Allocator与scudo的重了, 导致scudo脚本无法使用, 如果发现类似的库, 需要将其从lib目录下移出.

定位方法: gdb中使用ptype Allocator 查看其数据类型, 如果不是scudo::Allocator, 需要看其下面的类型定义或类的相关信息, 据此查找其属于哪个lib库.

与jemalloc 比较

scudo 中与内存单元相关的数据结构包括

small size class

Batch(或者chunk)(最基础的单位) -> Perclass::Chunks [TSD]->TransferBatch->RegionInfo->RegionInfoArray
large size class

cacheBlock -> largeBlock -> inUsedBlocks

jemalloc5 中与内存单元的数据结构包括

small size class

region(最基础单位) -> slab(extent) -> base -> cache_bin [TSD] ->tcache[TSD] -> extents(dirty|muzzy|retained) -> rtree -> bin -> arena
large size class

region(最基础单位) -> extent -> base -> extents -> rtree -> bin -> arena

blog

scudo 内存分配器调研

来源

概念

配置