Zone篇介绍了zone在初始化时指定了nanozone管理256字节以内内存，其余内存由scalablezone管理，本文主要分析一下nanozone的实现。libmalloc库中关于nano内存管理的实现，有2个版本，nano和nanov2，虽然思路上类似，但是具体实现方式差异较大，本篇主要分析的nanov2版本实现。
内存单位
首先，需要了解nanozone的整体思路，即分配时，预先映射一块虚拟内存空间，后续的内存分配回收发生在该范围内，如下图：
为了高效复用该区域，算法将内存空间层层划分成若干区域，从大到小，这些区域分别称为region、arena、block。下图是这些区域在nano空间的组成情况。
该区域的首地址是一个固定，例如0x2000000，区域包含一块或者若干个region（宏定义），每个region包含若干arena，每个arena包含若干block，具体的内存从block中分配。相关的数据结构如下：
block
内存区域划分的最小单位，1个block的大小是16KB，nano内存从block中分配。数据结构是：
typedef struct {
unsigned char content[NANOV2_BLOCK_SIZE]; //16KB
} nanov2_block_t;
字段：
- content，unsigned char数组
arena
较大一级内存单位，大小是64MB，包含4096个block，数据结构：
typedef struct {
nanov2_block_t blocks[NANOV2_BLOCKS_PER_ARENA];
} nanov2_arena_t;
字段：
- blocks，nanov2_block_t[4096]数组，大小是4096 * 16KB = 64MB
region
更大一级内存单位，大小是512MB，包含8个area，数据结构：
typedef struct {
nanov2_arena_t arenas[NANOV2_ARENAS_PER_REGION];
} nanov2_region_t;
字段：
- arenas，nanov2_arena_t[8]数组，大小是8 * 64MB = 512MB
因此，nano的内存区域包含若干region，每个region由8个arena组成，每个arena由4096个block组成，具体内存从block中分配。
内存地址
因为nano内存从某个region->arena->block区域中分配，因此，分配出的nano内存地址addr可以反映其位于哪个region、area、block内。分配出的nano内存地址的定义如下：
typedef union {
void *addr;
struct nanov2_addr_s fields;
} nanov2_addr_t;
是union类型，其中，addr字段是void*，表示一个具体内存地址，例如0x18000000，fields字段通过addr转换，可以映射出对应的region、arena、block，结构体如下：
#if NANOV2_MULTIPLE_REGIONS
#define SHIFT_NANO_SIGNATURE 44
#define NANOZONE_SIGNATURE_BITS 20
#define NANOZONE_SIGNATURE 0x6ULL
#define NANOZONE_BASE_REGION_ADDRESS (NANOZONE_SIGNATURE << SHIFT_NANO_SIGNATURE)
#else
#define SHARED_REGION_BASE 0x100000000ULL
#define SHARED_REGION_SIZE 0x100000000ULL
#define SHIFT_NANO_SIGNATURE 29
#define NANOZONE_SIGNATURE_BITS 35
#define NANOZONE_BASE_REGION_ADDRESS (SHARED_REGION_BASE + SHARED_REGION_SIZE)
#define NANOZONE_SIGNATURE (NANOZONE_BASE_REGION_ADDRESS >> SHIFT_NANO_SIGNATURE)
#endif
#if NANOV2_MULTIPLE_REGIONS
#define NANOV2_REGION_BITS 15
#else
#define NANOV2_REGION_BITS 0
#endif
#define NANOV2_ARENA_BITS 3
#define NANOV2_BLOCK_BITS 12
#define NANOV2_OFFSET_BITS 14
struct nanov2_addr_s {
uintptr_t nano_signature : NANOZONE_SIGNATURE_BITS; //35
#if NANOV2_MULTIPLE_REGIONS
uintptr_t nano_region: NANOV2_REGION_BITS; //
#endif // NANOV2_MULTIPLE_REGIONS
uintptr_t nano_arena : NANOV2_ARENA_BITS; //3
uintptr_t nano_block : NANOV2_BLOCK_BITS; //12
uintptr_t nano_offset : NANOV2_OFFSET_BITS; //14
};
nanov2_addr_s描述一个nano内存地址情况，支持多region和单region模式2种。
- 单region模式
-
基地址：nano内存区的首地址，例如0x200000000，后续的内存分配地址基于该地址偏移。
-
bit段含义：64位内存地址addr各bit段的含义如下：
-
nano_signature：前35位，作为nano内存区域的标识信息，例如内存地址：
//nano_signature=16 bits： 00000000 00000000 00000000 00000010 00000000 00000000 00000000 00000000 16进制： 0x200000000地址addr是0x200000000，对应的nano_signature值是16。
-
nano_region：addr位于哪块region，单region模式下没有该字段，因为内存分配在同一块region，后29位规定了内存范围，大小是2^29=512MB，即一块region的大小范围。例如基地址是0x200000000，内存范围是0x200000000 ~ 0x21fffffff。
bits： 00000000 00000000 00000000 00000010 00000000 00000000 00000000 00000000 ~ 00000000 00000000 00000000 00000010 00011111 11111111 11111111 11111111 16进制： 0x200000000 ~ 0x21fffffff -
nano_arena：region内部划分为8个arena区域，如下图，nano_arena表示addr位于哪个arena，通过3个bit位（2^3）表示，每个arena范围大小是64MB。
例如地址是0x200000000~0x21fffffff的region区域内，各个arena的范围如下，绿色为nano_arena的bit位：
nano_arena：000=0 bits： 00000000 00000000 00000000 00000010 000 000 00 00000000 00000000 00000000 ~ 00000000 00000000 00000000 00000010 000 000 11 11111111 11111111 11111111 16进制： 0x200000000 ~ 0x203ffffff nano_arena：001=1 bits： 00000000 00000000 00000000 00000010 000 001 00 00000000 00000000 00000000 ~ 00000000 00000000 00000000 00000010 000 001 11 11111111 11111111 11111111 16进制： 0x204000000 ~ 0x207ffffff nano_arena：010=2 bits： 00000000 00000000 00000000 00000010 000 010 00 00000000 00000000 00000000 ~ 00000000 00000000 00000000 00000010 000 010 11 11111111 11111111 11111111 16进制： 0x208000000 ~ 0x20bffffff nano_arena：011=3 bits： 00000000 00000000 00000000 00000010 000 011 00 00000000 00000000 00000000 ~ 00000000 00000000 00000000 00000010 000 011 11 11111111 11111111 11111111 16进制： 0x20c000000 ~ 0x20fffffff nano_arena：100=4 bits： 00000000 00000000 00000000 00000010 000 100 00 00000000 00000000 00000000 ~ 00000000 00000000 00000000 00000010 000 100 11 11111111 11111111 11111111 16进制： 0x210000000 ~ 0x213ffffff nano_arena：101=5 bits： 00000000 00000000 00000000 00000010 000 101 00 00000000 00000000 00000000 ~ 00000000 00000000 00000000 00000010 000 101 11 11111111 11111111 11111111 16进制： 0x214000000 ~ 0x217ffffff nano_arena：110=6 bits： 00000000 00000000 00000000 00000010 000 110 00 00000000 00000000 00000000 ~ 00000000 00000000 00000000 00000010 000 110 11 11111111 11111111 11111111 16进制： 0x218000000 ~ 0x21bffffff nano_arena：111=7 bits： 00000000 00000000 00000000 00000010 000 111 00 00000000 00000000 00000000 ~ 00000000 00000000 00000000 00000010 000 111 11 11111111 11111111 11111111 16进制： 0x21c000000 ~ 0x21fffffff -
nano_block：arena内部划分为4096个block区域（每个block大小是16KB），nano_block表示addr位于哪个block，通过12个bit位（2^12）表示，例如：
nano_arena：6，0x218000000 block0的地址范围 bits： 00000000 00000000 00000000 00000010 000 110 00 00000000 00000000 00000000 ~ 00000000 00000000 00000000 00000010 000 110 00 00000000 00111111 11111111 16进制： 0x218000000 ～ 0x218003fff block4095的地址范围 bits： 00000000 00000000 00000000 00000010 000 110 11 11111111 11000000 00000000 ~ 00000000 00000000 00000000 00000010 000 110 11 11111111 11111111 11111111 16进制： 0x21bffc000 ～ 0x21bffffff -
nano_offset：addr在block内的位置，一个block范围是16K，用最后14bit位（2^14）描述。
-
-
多region模式
nano内存区域包含多个region区域，相较于单region模式，用于分配nano内存的范围扩大，相应的，各bits段的有所调整。
- 基地址：固定是0x6 << 44=0x600000000000。
bits： 00000000 00000000 0110 0000 00000000 00000000 00000000 00000000 00000000 16进制： 0x600000000000- nano_signature：如上，值固定是6，前20位，后44位描述nano所在的region、arena、block
- nano_region：中间15个bit位表示，因为内部划分为2^15=32K个region区域。nano_region表示addr内存位于哪个region内。
bits： 00000000 00000000 0110 0000 00000000 00000000 00000000 00000000 00000000 16进制： 0x600000000000
- addr -> block内存地址
#define NANOV2_BLOCK_ADDRESS_MASK ~((1ULL << (NANOV2_OFFSET_BITS)) - 1) static nanov2_block_t *nanov2_block_address_for_ptr(void *ptr) { return (void *)(((uintptr_t)ptr) & NANOV2_BLOCK_ADDRESS_MASK); } 00000000 00000000 00000000 00000010 00011000 00000000 00 010000 00000000 (0x218001000) & 11111111 11111111 11111111 11111111 11111111 11111111 11 000000 00000000 = 00000000 00000000 00000000 00000010 00011000 00000000 00 000000 00000000 (0x218000000) - addr -> arena内存地址
#define NANOV2_ARENA_ADDRESS_MASK ~((1ULL << (NANOV2_BLOCK_BITS + NANOV2_OFFSET_BITS)) - 1) static nanov2_arena_t *nanov2_arena_address_for_ptr(void *ptr) { return (void *)(((uintptr_t)ptr) & NANOV2_ARENA_ADDRESS_MASK); } - addr -> region内存地址
#define NANOV2_REGION_ADDRESS_MASK ~((1ULL << (NANOV2_ARENA_BITS + NANOV2_BLOCK_BITS + NANOV2_OFFSET_BITS)) - 1) static nanov2_region_t *nanov2_region_address_for_ptr(void *ptr) { return (nanov2_region_t *)(((uintptr_t)ptr) & NANOV2_REGION_ADDRESS_MASK); } - addr -> block的index
static nanov2_block_index_t nanov2_block_index_for_ptr(void *ptr) { return (nanov2_block_index_t)(((uintptr_t)ptr) >> NANOV2_OFFSET_BITS) & ((1 << NANOV2_BLOCK_BITS) - 1); }
辅助逻辑
在理解分配与回收逻辑之前，需要理解一些辅助信息与常用概念。
size分级
在具体分配时，并不是根据上层需要多少size而直接分配相应大小，而是首先根据要分配的size，按照16B的倍数计算对应的分级（size-class），实际分配按照16B的倍数分配。下列方法是传入一个size，返回对应的size-class，公式如下：
#define SHIFT_NANO_QUANTUM 4
#define NANO_REGIME_QUANTA_SIZE (1 << SHIFT_NANO_QUANTUM) // 16
#define NANO_SIZE_CLASSES (NANO_MAX_SIZE/NANO_REGIME_QUANTA_SIZE) //256/16=16
static nanov2_size_class_t nanov2_size_class_from_size(size_t size)
{
return (nanov2_size_class_t)howmany(size, NANO_REGIME_QUANTA_SIZE) - 1;
}
例如分配17B，则对应的size-class = nanov2_size_class_from_size(17) = 1。反之，根据size-class，计算出对应的size：
static int nanov2_size_from_size_class(nanov2_size_class_t size_class)
{
return (size_class + 1) * NANO_REGIME_QUANTA_SIZE;
}
例如，分配17B对应的size-class是1，返回32B，实际按照32B的大小来分配内存。
由于nano内存的大小不超过256B，总共可以划分为16个级别，即size-class 0～15。对于每个size-class的内存，并不是随意选择一块空间区域进行分配，而是为每个size-class预先划分好范围，在指定的范围内分配。下图反映了arena中为各个size-class划分的范围。
划分的基本单位是unit，1个unit大小是16KB * 64 = 1024KB = 1MB，包含64个block，因此，arena中共64个unit，BLOCKS_PER_UNIT宏表示一个unit中包含64各blcok。
#define BLOCKS_PER_UNIT (1 << BLOCKS_PER_UNIT_SHIFT) //64
可以看到，各区域大小不一致，例如为size-class 2划分的区域最大，包含11个unit，即11M大小，说明这个分级下的内存被分配和使用次数较多。
block_units_by_size_class和first_block_offset_by_size_class两个变量，规定了各size-class对应区域的范围。
- block_units_by_size_class，为每个size-class划分的内存区域大小，单位是unit
static int block_units_by_size_class[] = { 2, // 16-byte allocations，128 10, // 32-byte allocations，640 11, // 48-byte allocations，704 10, // 64-byte allocations，640 5, // 80-byte allocations，320 3, // 96-byte allocations，192 3, // 112-byte allocations，192 4, // 128-byte allocations，256 3, // 144-byte allocations，192 2, // 160-byte allocations，128 2, // 176-byte allocations，128 2, // 192-byte allocations，128 2, // 208-byte allocations，128 2, // 224-byte allocations，128 1, // 240-byte allocations，64 2, // 256-byte allocations，128 }; - first_block_offset_by_size_class，每个size-class对应的起始block位置
first_block_offset_by_size_class[0] = 1 first_block_offset_by_size_class[1] = 2*64 = 128 ... first_block_offset_by_size_class[15] - last_block_offset_by_size_class，每个size-class对应的最后一个block。
last_block_offset_by_size_class[0] = 127 last_block_offset_by_size_class[1] = 767 ... last_block_offset_by_size_class[15] - ptr_offset_to_size_class，各unit内存块属于哪个size-class，例如unit0~unit1属于size-class 0.
//unit0~unit1对应size-class 0 ptr_offset_to_size_class[0] ~ ptr_offset_to_size_class[1] = 0 //unit2~unit11对应size-class 1 ptr_offset_to_size_class[2] ~ ptr_offset_to_size_class[11] = 1
slot
分配内存时，首先会选取其中一个空闲的block，并在block内部分配。block内部会预先为size-class划分成若干等份内存区域，分配时直接返回某块空闲的区域，划分的区域称为slot。例如下图，对于size-class0，即分配16B，划分成1024个slot，每次分配返回一个可用的slot区域，对于size-class1，即分配32B，则只能划分成512份。
const int slots_by_size_class[] = {
NANOV2_BLOCK_SIZE/(1 * NANO_REGIME_QUANTA_SIZE), // 16 bytes: 1024 (0)
NANOV2_BLOCK_SIZE/(2 * NANO_REGIME_QUANTA_SIZE), // 32 bytes: 512 (0)
NANOV2_BLOCK_SIZE/(3 * NANO_REGIME_QUANTA_SIZE), // 48 bytes: 341 (16)
NANOV2_BLOCK_SIZE/(4 * NANO_REGIME_QUANTA_SIZE), // 64 bytes: 256 (0)
NANOV2_BLOCK_SIZE/(5 * NANO_REGIME_QUANTA_SIZE), // 80 bytes: 204 (64)
NANOV2_BLOCK_SIZE/(6 * NANO_REGIME_QUANTA_SIZE), // 96 bytes: 170 (64)
NANOV2_BLOCK_SIZE/(7 * NANO_REGIME_QUANTA_SIZE), // 112 bytes: 146 (32)
NANOV2_BLOCK_SIZE/(8 * NANO_REGIME_QUANTA_SIZE), // 128 bytes: 128 (0)
NANOV2_BLOCK_SIZE/(9 * NANO_REGIME_QUANTA_SIZE), // 144 bytes: 113 (112)
NANOV2_BLOCK_SIZE/(10 * NANO_REGIME_QUANTA_SIZE), // 160 bytes: 102 (64)
NANOV2_BLOCK_SIZE/(11 * NANO_REGIME_QUANTA_SIZE), // 176 bytes: 93 (16)
NANOV2_BLOCK_SIZE/(12 * NANO_REGIME_QUANTA_SIZE), // 192 bytes: 85 (64)
NANOV2_BLOCK_SIZE/(13 * NANO_REGIME_QUANTA_SIZE), // 208 bytes: 78 (160)
NANOV2_BLOCK_SIZE/(14 * NANO_REGIME_QUANTA_SIZE), // 224 bytes: 73 (32)
NANOV2_BLOCK_SIZE/(15 * NANO_REGIME_QUANTA_SIZE), // 240 bytes: 68 (64)
NANOV2_BLOCK_SIZE/(16 * NANO_REGIME_QUANTA_SIZE), // 256 bytes: 64 (0)
};
注意的是，部分的size-class内存大小，一个block的大小不能完全整除，例如size-class=5（96B），只能划分成96份，空余64B的内存，存在部分内存浪费的情况。
因此，具体分配内存时，通过slot的下标就可以定位到block中指定的内存区域。
static void *nanov2_slot_in_block_ptr(nanov2_block_t *block, nanov2_size_class_t size_class,
int slot_index)
{
return (void *)((uintptr_t)block + nanov2_size_from_size_class(size_class) * slot_index);
}
反之，根据内存地址，可以计算出对应的slot下标：
static int
nanov2_slot_index_in_block(nanov2_block_t *block, nanov2_size_class_t size_class, void *ptr)
{
return (int)((uintptr_t)ptr - (uintptr_t)block)/(nanov2_size_from_size_class(size_class));
}
block meta
由于内存从block内部分配，因此需要管理并维护所有block，算法为block提供了block_meta信息，用于描述该block的使用情况，例如当前block是否参与分配，内部的分配情况等，对应的数据结构nanov2_block_meta_t如下：
typedef struct {
uint32_t next_slot : 11;
uint32_t free_count : 10;
uint32_t gen_count : 10;
uint32_t in_use : 1;
} nanov2_block_meta_t;
一个block_meta数据的大小是32bit = 4B，包含以下4个字段：
- next_slot：状态/空闲链表的next指针
- free_count：block中剩余多少slot可以分配
- gen_count：block中已经分配了多少slot
- in_use：block是否正在参与分配回收，对于各size class，当前参与只有一个block正在使用。
因此通过一个block_meta可以反应出block的使用情况。 block_meta信息是如何存储的，下图反映了block和block-meta的内存布局：
typedef struct {
nanov2_block_meta_t arena_block_meta[NANOV2_BLOCKS_PER_ARENA]; //4096
} nanov2_arena_metablock_t;
获取meta block的方法如下：
static nanov2_arena_metablock_t *nanov2_metablock_address_for_ptr(nanozonev2_t *nanozone, void *ptr)
{
return (nanov2_arena_metablock_t *)nanov2_logical_address_to_ptr(nanozone, nanov2_arena_address_for_ptr(ptr));
}
meta block因为是block0，实质获取的是arena的地址，然后转成nanov2_arena_metablock_t类型。
另外如图，meta-block和block的地址可以相互转化。具体的查找逻辑如下：
-
根据meta找到block
static nanov2_block_t * nanov2_block_address_from_meta_ptr(nanozonev2_t *nanozone, nanov2_block_meta_t *block_metap) { //获取meta所在的block，即block0 nanov2_block_t *meta_block = nanov2_block_address_for_ptr(block_metap); //获取meta所在的arena nanov2_arena_t *arena = nanov2_arena_address_for_ptr(block_metap); //计算meta的index nanov2_meta_index_t meta_index = (nanov2_meta_index_t)(block_metap - (nanov2_block_meta_t *)meta_block); //根据meta的index获取对应的block index nanov2_block_index_t block_index = nanov2_meta_index_to_block_index(meta_index); //根据block index获取block内存地址 return &arena->blocks[block_index]; } -
查找内存地址所在的block对应的meta
static nanov2_block_meta_t *nanov2_meta_ptr_for_ptr(nanozonev2_t *nanozone, void *ptr) { //arena中存放meta数据的区域 nanov2_arena_metablock_t *meta_block = nanov2_metablock_address_for_ptr(nanozone, ptr); //根据ptr找到对应block的index nanov2_block_index_t block_index = nanov2_block_index_for_ptr(ptr); //根据block的index获取对应的meta index nanov2_meta_index_t meta_index = nanov2_block_index_to_meta_index(block_index); //找到对应的meta内存地址 return &meta_block->arena_block_meta[meta_index]; }相互转换的核心逻辑是block index和meta index的相互转换。
static nanov2_meta_index_t nanov2_block_index_to_meta_index(nanov2_block_index_t block_index) { return ((block_index >> 6) | (block_index << 6)) & 0xFFF; } static nanov2_block_index_t nanov2_meta_index_to_block_index(nanov2_meta_index_t block_meta_index) { return ((block_meta_index >> 6) | (block_meta_index << 6)) & 0xFFF; }
可以看到，block的按序排列，meta的排序不和block保持一致，例如block index是2，对应的meta index是128。
arena内部布局
综上，arena中的内存布局规则可以用以下这张图来说明：
- 根据一个内存地址addr，推算出对应的size-class下标
static nanov2_size_class_t nanov2_size_class_for_ptr(nanozonev2_t *nanozone, void *ptr) { //1.ptr位于哪个block内 nanov2_block_index_t block = (int)(nanov2_block_index_for_ptr(ptr) ^ nanozone->aslr_cookie); //2.block对应的unit区域和size-class return ptr_offset_to_size_class[block >> BLOCKS_PER_UNIT_SHIFT]; } - 根据一个meta index，计算出对应的size-class
static nanov2_size_class_t nanov2_size_class_for_meta_index(nanozonev2_t *nanozone, nanov2_meta_index_t meta_index) { //1.meta index -> block_index nanov2_block_index_t block_index = nanov2_meta_index_to_block_index(meta_index); int logical_block_index = (int)(block_index ^ nanozone->aslr_cookie); //2.block对应的unit区域和size-class return ptr_offset_to_size_class[logical_block_index >> BLOCKS_PER_UNIT_SHIFT]; } - 返回size-class i在arena中的第一个block对应的meta
static nanov2_block_meta_t *nanov2_first_block_for_size_class_in_arena(nanozonev2_t *nanozone, nanov2_size_class_t size_class, nanov2_arena_t *arena) { //size-class i 对应的第一个block在arena中的偏移 int block_offset = first_block_offset_by_size_class[size_class]; //block for meta nanov2_arena_metablock_t *meta_blockp = nanov2_metablock_address_for_ptr(nanozone, arena); //block index nanov2_block_index_t block_index = (nanov2_block_index_t)(block_offset ^ nanozone->aslr_cookie); //block index -> meta index nanov2_meta_index_t meta_index = nanov2_block_index_to_meta_index(block_index); //meta return &meta_blockp->arena_block_meta[meta_index]; } - 同一个size-class下，查找当前block内存地址连续的后一个block，返回meta
static nanov2_block_meta_t * nanov2_next_block_for_size_class(nanozonev2_t *nanozone, nanov2_size_class_t size_class, nanov2_block_meta_t *meta_blockp, boolean_t *wrapped) { //... } - 同一个size-class下，查找当前block内存地址前一个block，返回meta
static nanov2_block_meta_t *nanov2_previous_block_for_size_class(nanozonev2_t *nanozone,nanov2_size_class_t size_class, nanov2_block_meta_t *meta_blockp,boolean_t *wrapped) { //... }
arena管理
相对于arena内部的内存分布规则，region内arena的布局比较简单，一个arena中等分为8个arena，如图：
static nanov2_arena_t *nanov2_first_arena_for_region(nanov2_region_t *region)
{
return (nanov2_arena_t *)region;
}
分配内存时，首先需要在一块指定的arena内查找block，查找范围是当前arena地址～limit arena地址，limit arena通常为内存地址连续的后一个arena，为了快速获取该地址，算法用维护了current_region_next_arena变量保存。current_region_next_arena记录当前region的下一个arena，初始化时设置为arena1：
static nanov2_arena_t *nanov2_limit_arena_for_region(nanozonev2_t __unused *nanozone, nanov2_region_t *region, nanov2_arena_t *current_region_next_arena)
{
nanov2_arena_t *limit_arena;
if (region == nanov2_current_region_base(current_region_next_arena)) {
limit_arena = current_region_next_arena;
} else {
limit_arena = nanov2_first_arena_for_region(region + 1);
}
return limit_arena;
}
如果current_region_next_arena和arena位于当前region，则直接使用current_region_next_arena，否则返回偏移一个region大小的内存地址。
region管理
算法分为单region和多region模式，对于单region模式，全局只有一个region，不存在region管理的情况。针对多region模式，首先规定了一个能够分配region的最大范围。
static nanov2_addr_t nanov2_max_region_base = {
.fields.nano_signature = NANOZONE_SIGNATURE,
.fields.nano_region = NANOV2_MAX_REGION_NUMBER
};
初始时，只分配一块region区域，当前region区域不够分配时，会新分配一块region区域，分配逻辑如下：
nanov2_arena_t *nanov2_allocate_new_region(nanozonev2_t *nanozone)
{
//1.当前region首地址
nanov2_region_t *current_region = nanov2_current_region_base(os_atomic_load(&nanozone->current_region_next_arena, relaxed));
//2.分配新region，直到成功
nanov2_region_t *next_region = current_region + 1;
while ((void *)next_region <= nanov2_max_region_base.addr) {
if (nanov2_allocate_region(next_region)) {
allocated = true;
break;
}
next_region++;
}
if (!allocated) {
return NULL;
}
//3.新region的偏移维护到链表中
nanov2_region_linkage_t *current_region_linkage = nanov2_region_linkage_for_region(nanozone, current_region);
uint16_t offset = next_region - current_region;
os_atomic_store(¤t_region_linkage->next_region_offset, offset, release);
//3.获取新region的首个arena
nanov2_arena_t *first_arena = nanov2_first_arena_for_region(next_region);
//4.更新region的current_region_next_arena信息
os_atomic_store(&nanozone->current_region_next_arena, first_arena + 1, release);
//4.返回新region的首个arena地址
return first_arena;
}
分配流程如下：
-
获取当前region首地址，当分配达到arena的边界时，current_region_next_arena指向region的最大边界，通过-1操作回到当前region范围内，通过nanov2_region_address_for_ptr方法获取region首地址。
static nanov2_region_t *nanov2_current_region_base(nanov2_arena_t *current_region_next_arena) { return nanov2_region_address_for_ptr((void *)(((uintptr_t)current_region_next_arena) - 1)); } -
开始分配新的region区域，默认取偏移region长度后的地址，然后调用nanov2_allocate_region方法尝试分配，如果失败，说明该区间已经有内存分配了，继续偏移，直到找到一块未使用的区域，分配成功，否则失败。分配流程如图：
-
由于分配的新region地址不一定连续，因此算法通过一个链表数据结构nanov2_region_linkage_t来管理
typedef struct { os_atomic(uint16_t) next_region_offset; uint16_t unused; } nanov2_region_linkage_t;其中，next_region_offset存储下一个region的地址偏移，unused存储region是否未使用。region_linkage共4B，存储在meta_block对应的meta位置，因为meta_block是专门存储meta的block，实际没有被业务使用，因此对应的meta可以用来存储region_linkage数据。
-
更新新的region的current_region_next_arena信息，为第2个arena。
-
返回新region的首个arena作为待上层分配使用的arena。
由于新创建的region加入链表中管理，因此根据current region可以得到next region。
static nanov2_region_t *nanov2_next_region_for_region(nanozonev2_t *nanozone, nanov2_region_t *region,
nanov2_arena_t *current_region_next_arena)
{
nanov2_region_linkage_t *linkage = nanov2_region_linkage_for_region(nanozone, region);
int offset = os_atomic_load(&linkage->next_region_offset, relaxed);
if (!offset) {
return NULL;
}
nanov2_region_t *next_region = region + offset;
return (nanov2_arena_t *)next_region < current_region_next_arena ? next_region : NULL;
}
分配回收
主要包含2块逻辑：
- block的管理，为内存分配提供可用的block，并管理这些block
- 找到block后，查找内部空闲的slot，将slot内存区域返回给上层使用。
为了更加清晰的分析，首先分析block内分配回收内存的逻辑。
block内部逻辑
block状态
block状态反应了当前block参与分配内存时的状态，该状态决定后续分配的策略。首先，block中的内存分配以slot为单位，即每个分配一个slot给上层，因此，slot的使用有3种状态：
- 未被使用
- 正在使用
- 使用后被回收
这样，对于一个包含若干slot的block来说，各个slot状态组成了block的整体状态，状态值对应block meta的next_slot字段值。
#define SLOT_NULL 0 // Slot has never been used.
#define SLOT_GUARD 0x7fa // Marks a guard block.
#define SLOT_BUMP 0x7fb // Marks the end of the free list
#define SLOT_FULL 0x7fc // Slot is full (no free slots)
#define SLOT_CAN_MADVISE 0x7fd // Block can be madvised (and in_use == 0)
#define SLOT_MADVISING 0x7fe // Block is being madvised. Do not touch
#define SLOT_MADVISED 0x7ff // Block has been madvised.
结合下图，总结为以下4个状态：
- SLOT_NULL：block中所有slot未被使用过。
- SLOT_BUMP：block内有slot正在使用，但是slot没有被回收。
- SLOT_FULL：block内所有slot都在使用中，没有剩余可用的slot。
- SLOT_CAN_MADVISE、SLOT_MADVISING、SLOT_MADVISED：MADVISE策略相关标识，后续具体介绍。
此外，当有slot被回收时，slot会被加入freelist中，并且next_slot值指向回收的slot，下文进行具体介绍。
空闲链表
为了实现block内部的空间复用，采用了freelist管理block内被回收的内存块，后续分配先从freelist中查找空闲内存，freelist中维护的是使用后被回收的slot。链表上的各节点，通过如下数据结构存储：
typedef struct {
uint64_t double_free_guard;
uint64_t next_slot;
} nanov2_free_slot_t;
nanov2_free_slot_t数据存储在一块slot空间内，因为对于已经回收的slot内存，slot无需存储业务数据，可以用来存储链表节点信息，通过next_slot将节点串联起来。freelist的首节点通过上文提到的block meta的next_slot字段存储。
freelist的结构如下图，其中未使用slot标记为白色，正使用的slot标记为黄色，使用后被回收的slot橙色。
分配流程
由于block当前的状态决定后续的分配逻辑，用下图来说明block的几种状态，并说明该状态下对应的分配逻辑。图中未使用slot标记为白色，正使用的slot标记为黄色，使用后被回收的slot为橙色。
- SLOT_NULL：所有slot均未分配，可被使用。
- SLOT_BUMP：部分slot被分配使用，没有slot被回收，freelist为空，后续分配向后取slot。
- SLOT_FULL：所有slot均在使用，没有slot被回收，freelist为空，此时block不能使用。
- slot index：next_slot是被回收的slot，说明freelist中存在被回收的slot，下次分配时，首先从freelist中取slot，例如下图的next_slot是2。
下面具体分析一下相关代码：
通过nanov2_allocate_from_block_inline具体实现，block_metap是用于分配size_class内存块的block的meta信息，madvise_block_metap_out用于存储需要madvise的block的meta。
void * nanov2_allocate_from_block_inline(nanozonev2_t *nanozone,
nanov2_block_meta_t *block_metap, nanov2_size_class_t size_class,
nanov2_block_meta_t **madvise_block_metap_out, bool *corruption)
{
//1.当前block meta
nanov2_block_meta_view_t old_meta_view;
old_meta_view.meta = os_atomic_load(block_metap, dependency);
nanov2_block_t *blockp = NULL;
again:
//是否能参与分配
if (!nanov2_can_allocate_from_block(old_meta_view.meta)) {
return NULL;
}
//新block meta
nanov2_block_meta_t new_meta = {
.in_use = 1,
.free_count = old_meta_view.meta.free_count - 1, //free_count-1
.gen_count = old_meta_view.meta.gen_count + 1 //gen_count+1
};
//block是否用满
boolean_t slot_full = old_meta_view.meta.free_count == 0;
//freelist空，向后查找slot
if (old_meta_view.meta.next_slot == SLOT_BUMP || old_meta_view.meta.next_slot == SLOT_CAN_MADVISE) {
new_meta.next_slot = slot_full ? SLOT_FULL : SLOT_BUMP;
slot = slots_by_size_class[size_class] - old_meta_view.meta.free_count - 1;
} else {
//从freelist中查找
from_free_list = TRUE;
if (!blockp) {
//meta对应的block
blockp = nanov2_block_address_from_meta_ptr(nanozone, block_metap);
}
slot = old_meta_view.meta.next_slot - 1; // meta.next_slot is 1-based.
//slot对应的内存
ptr = nanov2_slot_in_block_ptr(blockp, size_class, slot);
nanov2_free_slot_t *slotp = (nanov2_free_slot_t *)ptr;
new_meta.next_slot = slot_full ? SLOT_FULL : slotp->next_slot;
}
//更新block meta
if (!os_atomic_cmpxchgv(block_metap, old_meta_view.meta, new_meta,
&old_meta_view.meta, dependency))
{
//...
}
if (!ptr) {
if (!blockp) {
//meta对应的block
blockp = nanov2_block_address_from_meta_ptr(nanozone, block_metap);
}
//slot对应的内存
ptr = nanov2_slot_in_block_ptr(blockp, size_class, slot);
}
//...
return ptr;
}
对应的机制如下：
- 首先，通过block meta获取block的状态，根据状态判断，该block是否可以参与分配，如果状态为SLOT_FULL，直接返回NULL，分配失败。
- 如果可以分配开始分配逻辑，根据block meta的next_slot值判断当前block的状态，分为2种：
- next_slot是SLOT_BUMP或者SLOT_CAN_MADVISE，说明不存在freelist，向后取未使用的slot进行分配，如果slot全部在使用变为SLOT_FULL，否则仍然是SLOT_BUMP。
- next_slot是slot index，说明存在freelist，通过next_slot分配freelist的首节点slot。
- 返回slot块的内存地址。
- 更新block meta信息。
内存回收通过nanov2_free_to_block_inline函数实现：
nanov2_block_meta_t *nanov2_free_to_block_inline(nanozonev2_t *nanozone, void *ptr,
nanov2_size_class_t size_class, nanov2_block_meta_t *block_metap)
{
nanov2_block_t *blockp = nanov2_block_address_for_ptr(ptr);
if (!block_metap) {
block_metap = nanov2_meta_ptr_for_ptr(nanozone, ptr);
}
nanov2_block_meta_t old_meta = os_atomic_load(block_metap, relaxed);
int slot_count = slots_by_size_class[size_class];
nanov2_block_meta_t new_meta;
boolean_t was_full;
nanov2_free_slot_t *slotp = (nanov2_free_slot_t *)ptr;
again:
//生成新的block meta信息
was_full = old_meta.next_slot == SLOT_FULL;
new_meta.free_count = old_meta.free_count + 1;
new_meta.in_use = old_meta.in_use;
new_meta.gen_count = old_meta.gen_count + 1;
//是否回收最后一个正在使用的slot
boolean_t freeing_last_active_slot = !was_full &&
new_meta.free_count == slots_by_size_class[size_class] - 1;
//回收了最后一个正在使用的slot
if (freeing_last_active_slot) {
os_atomic_store(&slotp->next_slot, SLOT_NULL, relaxed);
//更新next_slot
new_meta.next_slot = new_meta.in_use ? SLOT_BUMP : SLOT_CAN_MADVISE;
//更新block meta
if (!os_atomic_cmpxchgv(block_metap, old_meta, new_meta, &old_meta, release)) {
goto again;
}
if (new_meta.next_slot == SLOT_CAN_MADVISE && nanov2_madvise_policy == NANO_MADVISE_IMMEDIATE) {
return block_metap;
}
} else {
//freelist加入被回收的slot
int slot_index = nanov2_slot_index_in_block(blockp, size_class, ptr);
new_meta.next_slot = slot_index + 1; // meta.next_slot is 1-based
os_atomic_store(&slotp->next_slot,was_full ? SLOT_BUMP : old_meta.next_slot, relaxed);
//更新block meta
if (!os_atomic_cmpxchgv(block_metap, old_meta, new_meta, &old_meta, release)) {
goto again;
}
}
}
对应的机制如下：
- 获取当前block meta信息，计算新生成的block meta信息
- 判断当前是否正在回收最后一个正在使用的slot，如果是，则当前block内所有slot未在使用，只存在未被使用过或者使用后被回收的slot，此时更新next_slot为SLOT_BUMP或者SLOT_CAN_MADVISE。之前维护的freelist不再生效。
- 如果不是，则将slot加入freelist中，供后续内存分配使用。
针对上述实现，结合图例说明分配回收的流程，以size-class 0（每次分配16B内存）为例。
- 初识block为未使用状态，所有slot（16B）未参与分配，block meta的next_slot是SLOT_NULL。
- 首次分配内存时，选取slot0，block meta的next_slot是SLOT_BUMP。
- 继续分配时，block meta的next_slot是SLOT_BUMP，说明freelist为空，因此从未使用的slot中分配，例如一次性分配5个slot1～5，block meta的next_slot依然是SLOT_BUMP。
- 此时，如果分配过程中未发生内存回收，则分配完最后一个未使用的slot时，block meta的next_slot是SLOT_FULL。
- 如果发生slot被回收，block meta的next_slot变成回收的slot，作为freelist首节点。例如slot2，block meta的next_slot更新成2。
- 如果有新的slot被回收，例如slot0、slot5依次被回收，依次插入freelist的最前部。block meta的next_slot更新成最新的slot5，后续节点通过nanov2_free_slot_t的next_slot串联。freelist的slot依次是，slot5、slot0、slot2
- 再次分配内存时，首先取slot5，然后更新next_slot。
- 如果正在使用的slot全部被回收，freelist被弃用，block meta的next_slot更新成SLOT_BUMP。等效于SLOT_NULL的情况，下次分配从首个slot分配。
block查找逻辑
介绍了block内部是如何分配内存的，接下来介绍如何在arena中查找一块合适的block参与分配。
查找范围
根据上文介绍，arena中为每个size-class预先划分了内存空间范围，每块区域包含若干block，如下图，size-class0的范围是block1～127，size-class对应的block在该范围内查找。
基本思路
查找block的基本思路是从范围内某一个block开始查找，根据block的状态判断是否符合条件，如果满足条件，直接返回，否则查找下一个block，直到arena内所有block都遍历，如果没有block满足条件，则返回失败。查找下一个block的策略是，首先向前取，即每次取连续内存地址前一个block，直到block是范围内第一个block，改成向后取，即每次取连续内存地址后一个block，直到block是范围内最后一个block后，回到第一个block后中止，如下图，例如从block2开始：
策略与条件
首先，定义了一个scan_policy枚举来决定选取的策略：
typedef enum {
NANO_SCAN_FIRST_FIT = 0,
NANO_SCAN_CAPACITY_BASED,
} nanov2_block_scan_policy_t;
有2种策略：
- NANO_SCAN_FIRST_FIT：只要block的状态满足基本条件，直接选取第一个满足条件的block。
- NANO_SCAN_CAPACITY_BASED：除了满足基本条件，需要判断block内部slot使用情况，返回最符合条件的block。
然后，具体结合源代码分析。
nanov2_block_meta_t *nanov2_find_block_in_arena(nanozonev2_t *nanozone,
nanov2_arena_t *arena, nanov2_size_class_t size_class,
nanov2_block_meta_t *start_block)
{
//是否匹配第一个满足条件
boolean_t use_first_fit = !start_block || nanov2_policy_config.block_scan_policy == NANO_SCAN_FIRST_FIT;
//范围内第一个block
nanov2_block_meta_t *first_block = nanov2_first_block_for_size_class_in_arena(
nanozone, size_class, arena);
boolean_t scanning_backwards;
//如果未指定start_block，取first_block
if (!start_block) {
start_block = first_block;
}
int slots_in_block = slots_by_size_class[size_class];
nanov2_block_meta_t old_meta;
nanov2_block_meta_t *this_block;
nanov2_block_meta_t *found_block;
nanov2_block_meta_t *madvisable_block;
nanov2_block_meta_t *free_block;
nanov2_block_meta_t *fallback_block;
boolean_t fallback_below_max;
int scan_limit;
retry:
this_block = start_block;
found_block = NULL;
madvisable_block = NULL;
free_block = NULL;
fallback_block = NULL;
fallback_below_max = FALSE;
//匹配次数
scan_limit = nanov2_policy_config.block_scan_limit;
scanning_backwards = TRUE;
do {
//current block meta
old_meta = os_atomic_load(this_block, relaxed);
//block状态not full，not madvising
if (!old_meta.in_use && old_meta.next_slot != SLOT_FULL
&& old_meta.next_slot != SLOT_MADVISING)
{
if (old_meta.next_slot == SLOT_CAN_MADVISE) {
if (!madvisable_block) {
madvisable_block = this_block;
}
} else if (old_meta.next_slot == SLOT_NULL || old_meta.next_slot == SLOT_MADVISED) {
//满足条件，存储到free_block
if (!free_block) {
free_block = this_block;
}
} else if (use_first_fit) {
//只匹配第一个，直接查找成功
found_block = this_block;
} else {//按照block使用情况匹配
MALLOC_ASSERT(nanov2_policy_config.block_scan_policy == NANO_SCAN_CAPACITY_BASED);
int percent_used = (100 * old_meta.free_count)/slots_in_block;
if (percent_used >= nanov2_policy_config.block_scan_min_capacity
&& percent_used <= nanov2_policy_config.block_scan_max_capacity) {
//满足，查找成功
found_block = this_block;
} else if (percent_used >= nanov2_policy_config.block_scan_min_capacity) {
//满足条件，存储到fallback_block
if (!fallback_block || fallback_below_max) {
fallback_block = this_block;
}
} else if (!fallback_block && percent_used < nanov2_policy_config.block_scan_min_capacity) {
//满足条件，存储到fallback_block
fallback_block = this_block;
fallback_below_max = TRUE;
} else if (!free_block) {
free_block = this_block;
}
}
if (use_first_fit && (found_block || fallback_block || free_block)) {
break;
}
}
if (scan_limit > 0) {
if ((fallback_block || free_block) && --scan_limit == 0) {
break;
}
}
if (scanning_backwards) {
boolean_t wrapped;
nanov2_block_meta_t *prev_block = nanov2_previous_block_for_size_class(
nanozone, size_class, this_block, &wrapped);
if (wrapped) {
scan_limit = nanov2_policy_config.block_scan_limit;
scanning_backwards = FALSE;
this_block = start_block;
} else {
this_block = prev_block;
}
} else {
this_block = nanov2_next_block_for_size_class(nanozone, size_class, this_block, NULL);
if (this_block == start_block) {
break;
}
}
} while (!found_block);
if (!found_block) {
if (fallback_block) {
found_block = fallback_block;
} else if (free_block) {
found_block = free_block;
} else if (madvisable_block) {
found_block = madvisable_block;
}
}
if (found_block) {
old_meta = os_atomic_load(found_block, relaxed);
if (old_meta.next_slot == SLOT_MADVISING) {
goto retry;
}
boolean_t reset_slot = old_meta.next_slot == SLOT_NULL
|| old_meta.next_slot == SLOT_CAN_MADVISE
|| old_meta.next_slot == SLOT_MADVISED;
nanov2_block_meta_t new_meta = {
.in_use = 1,
.free_count = reset_slot ? slots_in_block - 1 : old_meta.free_count,
.next_slot = reset_slot ? SLOT_BUMP : old_meta.next_slot,
.gen_count = reset_slot ? 0 : old_meta.gen_count + 1,
};
if (!os_atomic_cmpxchgv(found_block, old_meta, new_meta, &old_meta,
relaxed)) {
goto retry;
}
}
return found_block;
}
整体流程如下：
- 设置一些控制变量，use_first_fit表示是否直接选取满足表示的第一个block，如果未指定start_block或者policy=NANO_SCAN_FIRST_FIT，则use_first_fit=true，start_block是开始查找的第一个block，如果没有指定，则从first_block开始查找。
- 开始遍历block，根据block meta的next_slot状态判断是否满足基本条件，!SLOT_FULL且!SLOT_MADVISING。
- 如果不满足条件，则按照上文的方向查找下一个block，通过scanning_backwards控制查找方向。nanov2_previous_block_for_size_class是获取前一个block，nanov2_next_block_for_size_class获取后一个block。
- 如果满足条件，则根据策略来选取block。找到的block用found_block变量记录。
- 策略1: 如果use_first_fit=true，found_block是当前block。
- 策略2: 如果use_first_fit=false，遍历block直到找到最符合条件的block，选取条件是看block内部的slot空闲情况，用percent_used=freeCount / slots_in_block * 100来表示空闲比例，分为4种情况。
- 完全空闲，对应SLOT_NULL
- 在指定的最小最大值范围内，block_scan_min_capacity ～ block_scan_max_capacity
- 大于block_scan_max_capacity
- 小于block_scan_min_capacity
- 如果满足情况1，用free_block变量记录block
- 如果满足情况2，直接找到found_block，结束遍历查找流程
- 如果满足情况3或者4，用fallback_block变量记录
- 找到found_block后，更新block meta信息，并返回上层。如果遍历完所有block均不满足条件，则查找失败，返回上层逻辑。
整体逻辑
本节将前2节的内存串联起来，介绍一下nano内存分配的整体逻辑。首先，以nanov2_malloc函数为入口开始分配。
void *nanov2_malloc(nanozonev2_t *nanozone, size_t size)
{
size_t rounded_size = _nano_common_good_size(size);
if (rounded_size <= NANO_MAX_SIZE) {
//size-class
nanov2_size_class_t size_class = nanov2_size_class_from_size(rounded_size);
//cache block
int allocation_index = nanov2_get_allocation_block_index();
nanov2_block_meta_t **block_metapp = &nanozone->current_block[size_class][allocation_index];
nanov2_block_meta_t *block_metap = os_atomic_load(block_metapp, relaxed);
bool corruption = false;
void *ptr = NULL;
if (block_metap) {
//block内分配内存
ptr = nanov2_allocate_from_block_inline(nanozone, block_metap, size_class, &madvise_block_metap, &corruption);
if (ptr && !corruption) {
nanov2_free_slot_t *slotp = (nanov2_free_slot_t *)ptr;
os_atomic_store(&slotp->double_free_guard, 0, relaxed);
os_atomic_store(&slotp->next_slot, 0, relaxed);
return ptr;
}
}
//查找block
return nanov2_allocate_outlined(nanozone, block_metapp, rounded_size,
size_class, allocation_index, madvise_block_metap, ptr, false);
}
//其他方式分配内存
return nanozone->helper_zone->malloc(nanozone->helper_zone, size);
}
主要流程如下：
-
计算对齐后的size，size小于等于256B走nano内存分配，否则走其他分配方式。
-
走缓存逻辑，为了加速block的查找和内存分配，算法会缓存之前查找到的可用block，通过current_block字段维护缓存block的meta信息，current_block[][]是包含size-class和allocation_index2个维度的二维数组，即current_block[size-class][allocation_index]。
- size-class，nano共有16级size-class，因此一维数组长度是16.
- allocation_index获取当前执行的CPU核心，例如设备有6个CPU核心，则allocation_index位于0～5。
- 查找缓存block时，获取size-class和allocation_index，查找current_block[size-class][allocation_index]对应的block。block_metap是找到的cache block的meta信息。
-
如果存在block_metap，则直接从对应block内分配内存，调用nanov2_allocate_from_block_inline方法。
-
如果分配失败，或者没有cache block，则进入查找block与内存分配的流程。调用nanov2_allocate_outlined方法。nanov2_allocate_outlined内部调用nanov2_find_block_and_allocate方法，大致流程如下：
void *nanov2_find_block_and_allocate(nanozonev2_t *nanozone, nanov2_size_class_t size_class, nanov2_block_meta_t **block_metapp) { //... nanov2_block_meta_t *orig_block = start_block; if (start_block) { arena = nanov2_arena_address_for_ptr(start_block); } else { arena = nanov2_arena_address_for_ptr(nanozone->first_region_base); } //... retry: start_region = nanov2_region_address_for_ptr(arena); nanov2_arena_t *start_arena = arena; nanov2_region_t *region = start_region; nanov2_arena_t *limit_arena = nanov2_limit_arena_for_region(nanozone, start_region, initial_region_next_arena); do { nanov2_block_meta_t *block_metap = nanov2_find_block_in_arena(nanozone, arena, size_class, start_block); if (block_metap) { void *ptr = nanov2_allocate_from_block(nanozone, block_metap, size_class); if (ptr) { os_atomic_store(block_metapp, block_metap, relaxed); if (orig_block) { nanov2_turn_off_in_use(orig_block); } return ptr; } nanov2_turn_off_in_use(block_metap); start_block = block_metap; goto retry; } start_block = NULL; arena++; if (arena >= limit_arena) { region = nanov2_next_region_for_region(nanozone, region, initial_region_next_arena); if (!region) { region = nanozone->first_region_base; } arena = nanov2_first_arena_for_region(region); limit_arena = nanov2_limit_arena_for_region(nanozone, region, initial_region_next_arena); } } while (arena != start_arena); nanov2_arena_t *current_region_next_arena = os_atomic_load( &nanozone->current_region_next_arena, relaxed); if (current_region_next_arena == initial_region_next_arena) { if (nanov2_current_region_next_arena_is_limit( current_region_next_arena)) { arena = nanov2_allocate_new_region(nanozone); } else { arena = current_region_next_arena; os_atomic_store(&nanozone->current_region_next_arena, current_region_next_arena + 1, relaxed); } } else { arena = current_region_next_arena - 1; } if (!failed) { start_block = NULL; goto retry; } //... return NULL; }整体的逻辑如下：
- 从start block所在的arena中查找，如果start block为空，则从nanozone的第一块region的首个arena查找，上层传start block，说明有cache block，但是由于SLOT_FULL等原因，分配内存失败，需要新查找block，如果start block为空，说明之前没有找到cache block。
- 开始第一轮查找，标记开始查找arena为start_arena，limit_arena为本轮查找的边界arena。
- do-while循环中，调用nanov2_find_block_in_arena方法查找当前arena中可用的block，如果成功，则block内开始内存分配，如果分配成功，则block存入缓存中，并且通过nanov2_turn_off_in_use把之前的block标记为!inuse。为了提升性能，当前只有一个block是活跃状态，内存只从该block分配，减少了查找block的操作次数。
- 如果失败，说明当前arena中没有可用的block，通过arena++，判断下一个arena中的block情况，直到达到arena_limit时，结束本轮查找。
- 根据nanov2_current_region_next_arena_is_limit方法判断arena是否达到当前region的边界，通过nanov2_allocate_new_region方法则new一块新的region，并且将arena设置为new region的首个arena，否则current_region_next_arena设置arena，在通过retry开始下一轮查找。
底层调用
nanov2_allocate_new_region方法分配内存时，内部调用系统接口mach_vm_map映射一块虚拟内存。
boolean_t nano_common_allocate_vm_space(mach_vm_address_t base, mach_vm_size_t size)
{
vm_address_t vm_addr = base;
kern_return_t kr = mach_vm_map(mach_task_self(), &vm_addr, size, 0,
VM_MAKE_TAG(VM_MEMORY_MALLOC_NANO), MEMORY_OBJECT_NULL, 0, FALSE,
VM_PROT_DEFAULT, VM_PROT_ALL, VM_INHERIT_DEFAULT);
if (kr != KERN_SUCCESS || vm_addr != base) {
if (!kr) {
vm_deallocate(mach_task_self(), vm_addr, size);
}
return FALSE;
}
return TRUE;
}
madvise机制
为了优化内存占用，算法会在某个时机调用系统接口madvise，实现部分空闲内存的回收，定义如下：
int madvise(caddr_t addr, size_t len, int advice);
madvise接口用于向内核提供有关地址范围的建议或指导，这些地址范围始于地址addr且具有大小len字节。advice是具体的策略，部分策略如下：
#define MADV_NORMAL POSIX_MADV_NORMAL
#define MADV_RANDOM POSIX_MADV_RANDOM
#define MADV_SEQUENTIAL POSIX_MADV_SEQUENTIAL
#define MADV_WILLNEED POSIX_MADV_WILLNEED
#define MADV_DONTNEED POSIX_MADV_DONTNEED
#define MADV_FREE 5 /* pages unneeded, discard contents */
#define MADV_ZERO_WIRED_PAGES 6 /* zero the wired pages that have not been unwired before the entry is deleted */
#define MADV_FREE_REUSABLE 7 /* pages can be reused (by anyone) */
#define MADV_FREE_REUSE 8 /* caller wants to reuse those pages */
#define MADV_CAN_REUSE 9
#define MADV_PAGEOUT 10 /* page out now (internal only) */
malloc是如何madvise接口来实现内存优化的：
首先，mvm_madvise_free封装了madvise，内部调用madvise接口，传入的策略是MADV_FREE_REUSABLE，给内核提供一个建议：标记这块内存已经不再使用，可以被回收重用，但是是否回收和回收的时间点由内核来决定。
#define CONFIG_MADVISE_STYLE MADV_FREE_REUSABLE
int mvm_madvise_free(void *rack, void *r, uintptr_t pgLo, uintptr_t pgHi, uintptr_t *last, boolean_t scribble)
{
//...
if (-1 == madvise((void *)pgLo, len, CONFIG_MADVISE_STYLE)) {return 1;}
//...
}
上层调用mvm_madvise_free接口，对应的逻辑是：
- 回收针对的内存区域是某个block，在回收逻辑nanov2_free_to_block_inline中，当前block如果满足以下2个条件，可以被回收：
- !inUse，该block不是活跃的，上文提到，每次查找一块新的block后，把旧的block的inUse状体设置为flase，表示当前block不是活跃的，内存分配只从当前活跃的block中分配。
- block中的内存全部回收，没有在使用的内存。 判断inUse状态是为了保证性能，因为inUse的block即使内存全部不再使用，下次分配时，通过cache复用机制，仍然从该block中分配内存，而不用重新查找一块新内存。
- 如果满足条件，该block meta的next_slot标记为SLOT_CAN_MADVISE，表示该内存块可以被madvise。标记过程如图：
针对状态是SLOT_CAN_MADVISE的block，存在几种时机执行madvise操作：
- 在回收流程时，如果block设置SLOT_CAN_MADVISE，进一步判断policy是否是NANO_MADVISE_IMMEDIATE，表示立即进行madvise操作，则在回收流程中执行mvm_madvise_free方法标记内存回收。
- 如果不是NANO_MADVISE_IMMEDIATE，则下次内存分配时，如果发现当前block的状态是SLOT_CAN_MADVISE，也调用nanov2_madvise_block方法标记内存回收。
本文分析nanozoneV2的开源代码实现，欢迎大家交流评论～
