内存管理

苹果的内存管理分为NanoZone和ScalableZone两种管理方式，只有当NanoZone无法处理时，ScalableZone才会介入，从英文拼写（Nano：纳米）可以看出NanoZone是用于管理颗粒度更小的内存块，（Scalable：扩展）ScalableZone用于管理单位不固定的内存

NanoZone的开启规则是64位设备。

ScableZone无限制开启规则

内存分类

苹果对内存申请的大小进行了分类，分为TINY、SMALL、Medium、Large类型，每个类型代表不同的内存大小范围。

苹果为了方便管理，对所有分类都声明了新的大小单位

Nano内存简介

Nano内存存在的目的是为了解决小内存频繁申请和释放带来的效率以及管理问题。

其他类型的内存存在内存不连续、管理复杂等问题，因此苹果引入小于256字节的小内存的轻量级管理Nano。

Nano操作更简单，节省时间（无锁分配），对小内存的频繁申请和释放有更好的处理效果。

Nano内存是一块连续的内存，起始内存位置固定。

Nano数据结构

在Nano分配内存时的内存结构是共用体，地址addr和fields可以相互切换，也就是对64位内存地址进行分割

// Union that allows easy extraction of the fields in a Nano V2 address.
typedef union  {
    void *addr;
    struct nanov2_addr_s fields;
} nanov2_addr_t;


struct nanov2_addr_s {
    uintptr_t nano_signature : NANOZONE_SIGNATURE_BITS;
#if NANOV2_MULTIPLE_REGIONS
    uintptr_t nano_region: NANOV2_REGION_BITS;
#endif // NANOV2_MULTIPLE_REGIONS
	uintptr_t nano_arena : NANOV2_ARENA_BITS;
	uintptr_t nano_block : NANOV2_BLOCK_BITS;
	uintptr_t nano_offset : NANOV2_OFFSET_BITS;
};

Nano通过对64位内存位置进行分级得到Nano的内存单位，从小到大分为Block、Arena、Region

下方是各个数据类型的数据结构：

block

block结构体内的content是unsigned char类型，size是2^14 = 16kb，也就是1个block是16kb

#define NANOV2_OFFSET_BITS		14

// Size of a block (currently 16KB)
#define NANOV2_BLOCK_SIZE		(1 << NANOV2_OFFSET_BITS)

// A block is a chunk of NANOV2_BLOCK_SIZE bytes of memory.
typedef struct {
	unsigned char content[NANOV2_BLOCK_SIZE];
} nanov2_block_t;

Arena

arena包含NANOV2_BLOCKS_PER_ARENA（4096）个block，一个arena的可代表内存是NANOV2_BLOCKS_PER_ARENA * 16kb（每个block的内存） = 64mb

// block可代表的内存 (当前是16KB)
#define NANOV2_BLOCK_SIZE		(1 << NANOV2_OFFSET_BITS)

// 一个arena可代表的内存 (当前是 64MB)
#define NANOV2_ARENA_SIZE		(64 * 1024 * 1024)

// 每个arena包含多少个block (当前是 4096个) 
#define NANOV2_BLOCKS_PER_ARENA	(NANOV2_ARENA_SIZE/NANOV2_BLOCK_SIZE)

// An arena is an array of NANOV2_BLOCKS_PER_ARENA blocks.
typedef struct {
	nanov2_block_t blocks[NANOV2_BLOCKS_PER_ARENA];
} nanov2_arena_t;

Region

region包含NANOV2_ARENAS_PER_REGION（8）个arena，一个region的可代表内存是NANOV2_ARENAS_PER_REGION* 64mb（每个arena的内存） =512mb

// Size of an arena (currently 64MB)
#define NANOV2_ARENA_SIZE		(64 * 1024 * 1024)

// Size of a region (currently 512MB)
#define NANOV2_REGION_SIZE		(512 * 1024 * 1024)

// Number of arenas per region (currently 8)
#define NANOV2_ARENAS_PER_REGION	(NANOV2_REGION_SIZE/NANOV2_ARENA_SIZE)

// A region is an array of NANOV2_ARENAS_PER_REGION arenas.
typedef struct {
	nanov2_arena_t arenas[NANOV2_ARENAS_PER_REGION];
} nanov2_region_t;

通过查看Block、Arena、Region的结构体可以观测出：

一个Block包括了16kb的内存空间;

一个Arena包括了4kb个Block;

一个Region包括了8个Arena;

形象一点：Block、Arena、Region的关系如下图：

64位的设备代表了地址也是64位的，Nano分为单Region和多Region情况，多Region用于Mac和模拟器，其他都是单Region（比如iOS）的，因此模拟器运行的效果不能作为真机的运行效果，内存分布情况都不一样的。

单Region分布情况：

多Region分布情况，Region的内容通过拆分Signature来完成。

上述分布的依据：

// mac/模拟器
#if TARGET_OS_OSX || TARGET_OS_SIMULATOR || MALLOC_TARGET_DK_OSX

// 多Region
#define NANOV2_REGION_BITS		15
#define NANOV2_ARENA_BITS		3
#define NANOV2_BLOCK_BITS		12
#define NANOV2_OFFSET_BITS		14

// 其他
#else // TARGET_OS_OSX || TARGET_OS_SIMULATOR || MALLOC_TARGET_DK_OSX

// 单Region
#define NANOV2_REGION_BITS		0
#define NANOV2_ARENA_BITS		3
#define NANOV2_BLOCK_BITS		12
#define NANOV2_OFFSET_BITS		14

#endif // TARGET_OS_OSX || TARGET_OS_SIMULATOR || MALLOC_TARGET_DK_OSX

至此可以得出如下表格：

前面已经介绍了内存单元以及大小，实际的分配过程中不会一个字节一个字节的分配，而是以16个字节作为一个单位，也就是我们申请内存的最小单位是16B，如果低于16B也会返回16B的内存大小。

这是一个很有意思的点：

int *p = malloc(sizeof(int));

p指向了一个4B大小的内存，但是往后面写再访问3个也不会存在问题 p + 1; p + 2； p+3 都不会有问题，因为p申请内存时就返回了16B大小的内存，p+ 3也属于着16B的范围内，但是不建议这样操作。

#define SHIFT_NANO_QUANTUM		4
#define NANO_REGIME_QUANTA_SIZE	(1 << SHIFT_NANO_QUANTUM)	// 16字节

为了更好的管理，Nano对申请的内存就行了分级，同等级别的内存放在一起，Nano申请的最大单位位256B，最小单位位16B，因此分成256/16 = 16个级别

Nano针对分级创建了一个新的单位Unit，每个Unit是64个Nano的Block单位 = 64 * 16KB = 1MB大小，如下图，BLOCKS_PER_UNIT = 2 ^ 6 = 64个Block

// BLOCKS_PER_UNIT must be a power of two to make it possible to get the size
// class from a pointer reasonably cheaply. Do not change the value without
// fixing the code that depends on it.
#define BLOCKS_PER_UNIT_SHIFT 6
#define BLOCKS_PER_UNIT (1 << BLOCKS_PER_UNIT_SHIFT)

分级后，对不同的内存级别，不能都分为同样大小的内存空间，有些内存大小会常用一些，有些不常用，常用级别的内存大小分配的内存单元应该更多一些，不常用的更少一些。

// Number of units of each size class in an arena. The numbers here must add
// up to 64. One unit corresponds to BLOCKS_PER_UNIT blocks in the corresponding
// size class, so 64 units maps to a total of 64 * 64 = 4096 blocks and each
// block is 16K, making a total of 64MB, which is the size of an arena.
static int block_units_by_size_class[] = {
	2,	// 16-byte allocations (less 1 for the metadata block)
	10,	// 32-byte allocations
	11,	// 48-byte allocations
	10,	// 64-byte allocations
	5,	// 80-byte allocations
	3,	// 96-byte allocations
	3,	// 112-byte allocations
	4,	// 128-byte allocations
	3,	// 144-byte allocations
	2,	// 160-byte allocations
	2,	// 176-byte allocations
	2,	// 192-byte allocations
	2,	// 208-byte allocations
	2,	// 224-byte allocations
	1,	// 240-byte allocations
	2,	// 256-byte allocations
};

从上图的代码可以总结出如下的内存，共用64个Unit，每个Unit是1MB

Nano中的Slot概念

结合分级，对block的区域进行分配时，1个block对不同分级的内存可分配数量是不一样的，第0级的16B一个单位，一个block是16kb则可以分配为1024个单位

此单位命名为slot：槽，此单位用于描述一个block中可以存储多少个sizeClass的数量；

同理第1级是32B一个单位，1个Block可分配512个slot，也就是slot的单位是不固定的，和分级是关联的。

并不是每个分级都可以被Block整除，比如第2级别，SizeClass = 48B，16KB（一个block大小）/ 38 = 341.333333....，也就是有341个Slot，16 * 1024 - 341 * 48  = 16B，也就是有16B大小的内存是无法使用的

// Number of slots in a block, indexed by size class. Note that there is a small
// amount of wastage in some size classes because the block size is not always
// exactly divisible by the allocation size. The number of wasted bytes is shown
// in parentheses in the comments below.
MALLOC_NOEXPORT 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)
};

画图说明：

SizeClass和Slot的关系

16K（16 * 1024） / SizeClass = Slot

Nano的元数据Meta

Meta是用于标识Slot是否已经被使用，标识Slot的使用状态，是否已经分配以及分配情况

Meta直接描述是Block的使用情况。

数据结构：

// Per-block header structure, embedded in the arena metadata block.
typedef struct {
    uint32_t next_slot : 11;	// Next slot on free list, 1-based.
    uint32_t free_count : 10;	// Free slots in this block - 1
    uint32_t gen_count : 10;	// A-B-A count
    uint32_t in_use : 1;		// Being used for allocations.
} nanov2_block_meta_t;

next_slot：已回收（freelist）的指针链表的下一个槽地址

free_count：未分配槽数量-1

gen_count：已”分配“的槽数量

in_use：是否已在使用中

对上述的结构体进行计算大小，sizeof(nanov2_block_meta_t) = 32bit = 4B（字节），

nanov2_block_meta_t是存储在arena中，一个arena是有一个nanov2_block_meta_t的结构体数组，数组的数量是NANOV2_BLOCKS_PER_ARENA，也就是和arena中block的数量相等，共占用NANOV2_BLOCKS_PER_ARENA * 4B = 4096 * 4 = 16 * 1024 = 16kb，相当于一个Block的大小

// Size of an arena (currently 64MB)
#define NANOV2_ARENA_SIZE		(64 * 1024 * 1024)

// Size of a region (currently 512MB)
#define NANOV2_REGION_SIZE		(512 * 1024 * 1024)

// Number of blocks per arena (currently 4096)
#define NANOV2_BLOCKS_PER_ARENA	(NANOV2_ARENA_SIZE/NANOV2_BLOCK_SIZE)

// Structure overlaid onto an arena's metadata block. This must be exactly
// the same size as a block.
typedef struct {
	nanov2_block_meta_t arena_block_meta[NANOV2_BLOCKS_PER_ARENA];
} nanov2_arena_metablock_t;

结合Region、Arena、Block的关系图，可以得出如下结论图

总结

至此，已经熟悉了所有的数据结构，这里对上述内容进行汇总下

1、Nano中的内存根据大小分为Region、Arena、Block，一个Block是16k，一个Arena是4k个Block，共4k *16k = 64MB，一个Region是8个Arena，共8 * 64MB = 512MB

2、Nano根据分配内存时分配的大小进行了分级，共分为16级别（SizeClass）,最低级是16B，最大256B，中间的级别和大小的关系是（（SizeClass + 1) * 16B = Size）

3、因不同级别的内存使用的频率高低不一，Nano为不同级别（SizeClass）分配的可使用内存是不一样的，并创建了一个新的单位Unit，一个Unit代表1MB，并维护了一个不同级别占用unit数量的数组，标识不同级别占用的unit数量

4、Nano分级后，引入了槽（slot）的概念，槽是个数量概念，代表一个block内，某个分级（SizeClass）内存块的数量

5、内存的元数据放到了Arena中的第一个Block中，meta的数量和arena中的block数量保持一致，用于描述block内存槽（slot）的使用情况

对上述过程进行画图总结

Nano内存申请和释放过程

下面我们进入我们的核心内容，申请和释放。

根据数据结构篇的介绍，我们清楚了meta对应的是每一个block，也意味着我们的申请和释放时围绕着block进行的，申请的最小单位为一个slot。

Nano的申请过程

对于Block存在以下几种状态，用于描述nanov2_block_meta_t结构体的next_slot字段

// Distinguished values of 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.

SLOT_NULL：Block未用过

SLOT_GUARD：标记Block为Guard Block，不在参与内存分配。

SLOT_BUMP：当前无释放的内容（或者被释放的内容已被重新申请走）

SLOT_FULL：block已全部被申请完，  可能有释放的

SLOT_CAN_MADVISE：用于标记内存是否可释放，这种释放是内核级别的释放，就是物理内存的释放，需手动标记

SLOT_MADVISING：正在被释放，不需要手动标记

SLOT_MADVISED：已经释放，不需要手动标记，系统会做标记

这些状态时用于描述meta的next_slot内容，当无释放时，next_slot就是这些状态，当有释放时就是freelist的头部。

注意：后面介绍的都是基于sizeclass为0的block进行的。

下面介绍下freelist的机制

freelist的机制

freelist是一种链表机制，，结构体如下：

// Structure overlaid on slots that are on the block freelist.
typedef struct {
    uint64_t double_free_guard;
    uint64_t next_slot; // Legal values are <= NEXT_SLOT_VALID_MASK
} nanov2_free_slot_t;

double_free_guard：这是一个校验slot的位置是否准确，如果slot位置不准确，则直接发生异常，此数据默认为0，进入freelist时会赋值为slot指针和某个公共变量的异或，校验时从freelist获取到slot的指针，取出此值和公共变量再异或，判断结果是否和slot指针一致，不一致则发生了异常。

next_slot：指向的时链表的下一个。

此链表的数据直接存于槽（slot）内，因为slot已经被释放，所以写nanov2_free_slot_t数据于槽（slot）内是没问题的（为什么use after free系统感知到？）

蓝色部分为已申请的内存，深蓝色为已释放的内存，从下图可以看出meta的next_slot指向slot4，slot4指向slot0，slot0指向slot2，slot2的next_slot为SLOT_BUMP

申请流程

第一步、初始状态:

typedef struct {
    uint32_t next_slot = SLOT_NULL
    uint32_t free_count = 0
    uint32_t gen_count  = 0
    uint32_t in_use  = 0
} nanov2_block_meta_t;

第二步、申请1次，gen_count + 1 = 1，free_count - 1 = 1023，in_use = 1;

typedef struct {
    uint32_t next_slot = SLOT_BUMP
    uint32_t free_count = 1023
    uint32_t gen_count  = 1
    uint32_t in_use  = 1
} nanov2_block_meta_t;

第三步、申请第2次，gen_count + 1 = 2，free_count - 1 = 1022，in_use = 1;

typedef struct {
    uint32_t next_slot = SLOT_BUMP
    uint32_t free_count = 1022
    uint32_t gen_count  = 2
    uint32_t in_use  = 1
} nanov2_block_meta_t;

第四步、申请第1024次，gen_count + 1024 = 1024，free_count - 1024 = 0，in_use = 1;

typedef struct {
    uint32_t next_slot = SLOT_FULL
    uint32_t free_count = 0
    uint32_t gen_count  = 0
    uint32_t in_use  = 1
} nanov2_block_meta_t;

至此，流程是很简单的，如果再申请需要新开一个block，继续上述过程。

但是当有freelist的链表时，过程会有少许差别，有freelist代表有已释放的slot，下面看下有freelist的分配过程

Nano的释放过程

释放过程涉及fresslist，下面从一个中间态来开始释放

初始状态，已申请5 = free_count = 1024 - 1019，next_slot = SLOT_BUMP，in_use = 1

下面依次申请4、0、3

第一步、释放slot4，free_count + 1 = 1020，gen_count + 1 = 6，in_use = 1

第二步、释放slot0，free_count + 1 = 1021，next_slot = slot0, slot0 转换为nanov2_free_slot_t结构体来指向slot4，gen_count + = 7，in use = 1

第三步、释放slot3，free_count + 1 = 1022，next_slot = slot3, slot3 转换为nanov2_free_slot_t结构体来指向slot0，gen_count + = 8，in use = 1

其他特殊情况

有2种特殊情况需要处理下，free_count 最大位10位无符号，最小值为0，最大为1023

第一种情况为，next_slot为SLOT_FULL，free_count = 0，这时候代表所有的均已分配完毕

第二种情况为，next_slot不为SLOT_FULL，free_count = 0，这里的0代表1024，代表free_list已满，整个block已全部被回收

针对第二种情况：

1、内存足够时，将next_slot标记为SLOT_CAN_MADVISE，由内核回收，回收后才活动管理器才认为已释放。

2、申请内存时，标记为SLOT_CAN_MADVISE的可以直接将next_slot置为SLOT_BUMP，继续使用。

思考

int *p = malloc(sizeof(int));

free(p);

int *p1 = malloc(sizeof(int) * 10);

free(p1);

同样都是free，为什么p1比p释放的多，这种机制是如何完成的

其他