iOS内存-堆(libmalloc)-scalable_zone

发表于 | 分类于

scalable_zone是zone其中一种类型, 分配堆内存管理者，malloc，free等函数真正的入口

SZone

在zone中，会根据申请的堆大小选择不同rack进行分配

zone和rack关系如下图

scalable_zone即s_zone, 拥有三个Rack_S对象，分别用来处理不同大小的堆内存操作

  • tiny _rack 处理小于1009字节的分配
  • small _rack 处理1009B~32KB的分配(iOS 1009B~15KB)
  • medium_rack 处理32(iOS 15)KB~8M的分配
  • (如果大于8M内存的申请，则通过系统调用申请)

相关函数 

1
2
3
create_scalable_szone   	 //  创建zone
szone_malloc   			     // zone malloc函数入口
szone_malloc_should_clear    // 在这判断大小选择rack

Rack

在rack中，会根据当前运行线程的所在的核选择不同Magazine进行分配

rack和magazine关系如下

rack的属性magazine*指向的是magazine数组。该数组内存区域通过系统调用mach_vm_map申请, 申请大小magazine数组数量+1

magazines数量即rack的num_magazines属性如何确定呢? 以及为什么+1，多出来的那个magazine用来干啥的？

num_magazines由当前主机CPU核数决定. 如果CPU核数没有设置，num_magazines=1，如果大于1小于64，则取CPU核数值，如果大于64，则取64; 这么设计的目的是为了真正并发的性能

  • 多核上多线程通过操作不同的magazine(对内存的malloc和free等), 可以减少lock的使用
  • 让多核CPU的缓存得到充分利用，每个核拥有自己的多级缓存

+1 是为了给magazines数组加上一个depot magazine, 放置在数组的首位置上，并且rack的magazines指向magazines数组第2个元素的位置

  • depot magazine是当前线程所在的核对应的magazine无法分配出heap空间时，会通过depot magazine分配。分配出的空间地址对应的heap region会添加到当前magazine中，在free block块合并的时候，也会给depot magazine添加heap region. 当然后面会详细讲

相关函数

1
2
3
rack_init    // 初始化rack和创建magazines
tiny_malloc_should_clear       // 选择tiny_rack magazine
small_malloc_should_clear      // 选择small_rack magazine

Magazine

magazine是真正操作堆内存的对象

magazine的结构如下, 其中每个属性注释在后面的malloc和free过程中都会说到 

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
struct magazine_s {
	_malloc_lock_s magazine_lock MALLOC_CACHE_ALIGN;
	
	// 当前是否在向内核申请heap region
	volatile boolean_t alloc_underway;
	
	// 最后一次free的地址和大小
	void *mag_last_free;
	msize_t mag_last_free_msize;	
	// 最后一次free的地址所在的heap region
	region_t mag_last_free_rgn; 

	// 空闲链表数组
	free_list_t mag_free_list[MAGAZINE_FREELIST_SLOTS];  // MAGAZINE_FREELIST_SLOTS => 256
	// 空闲链表数组bit信息
	uint32_t mag_bitmap[MAGAZINE_FREELIST_BITMAP_WORDS]; // MAGAZINE_FREELIST_BITMAP_WORDS => 8

	// 最后申请的heap region中未使用的大小
	size_t mag_bytes_free_at_end;
	// 最后申请的heap region的随机起始偏移未使用的大小(ASLR)
	size_t mag_bytes_free_at_start;
	// 最后一次向内核申请的heap region地址
	region_t mag_last_region;

	// magazine已经分配出去的大小
	size_t mag_num_bytes_in_objects;
	// magazine总共的heap大小(包括分配的和未分配的)
	size_t num_bytes_in_magazine;
	// heap region 数量
	unsigned mag_num_objects;

	// heap regions metadata双向链表首尾节点
	unsigned recirculation_entries;
	region_trailer_t *firstNode;
	region_trailer_t *lastNode;

	// 页填充无用数据
	uintptr_t pad[320 - 14 - MAGAZINE_FREELIST_SLOTS -
			(MAGAZINE_FREELIST_BITMAP_WORDS + 1) / 2];
} magazine_t;

Heap Region

堆内存 heap region是用户态malloc内存真正的区域

设计

数据结构如下

1
2
3
4
5
6
7
8
9
10
11
typedef struct tiny_region {
	// Data; malloc申请的空间在这里面
	tiny_block_t blocks[NUM_TINY_BLOCKS];   // sizeof(tiny_block_t) => 16;  NUM_TINY_BLOCKS => 64520

	// Meta_Data;
	region_trailer_t trailer;
	tiny_header_inuse_pair_t pairs[CEIL_NUM_TINY_BLOCKS_WORDS];  // blocks对应的bitmap
	
	// 对齐用的无用空间
	uint8_t pad[TINY_REGION_SIZE - (NUM_TINY_BLOCKS * sizeof(tiny_block_t)) - TINY_METADATA_SIZE];
} * tiny_region_t

tiny_region布局结构如下

tiny_region通过系统调用mach_vm_map分配, 分配出来的空间划分为两部分

  • Data

    data区按照16个字节作为一个block, block也是malloc申请的最小单位
    block也刚好能存储两个指针数据，可以作为空闲链表的一个节点

  • MetaData

    metaData存储着data区的使用情况(bitmap)以及heap_region prev和next的metaData指针(双向链表)

和magazine的关系

  • magazine的firstNode和lastNode指向heap region metaData双向链表的第一个和最后一个节点
  • magazine的 mag_last_region指向最后一次magazine向内核申请的heap region

描述如下图

Last_Free

magazine的last_free等属性储存着该magazine最后一次free的block块地址，块大小，以及块地址的heap region地址

Free_Lists

free过的内存会作为节点储存在空闲链表中，而free_lists是magazine的空闲链表数组，数组元素空闲链表按照内存块大小递增

对于tiny_rack最多分配1008个字节，因此该rack下的每个magazine的空闲链表数组个数最大为1008/16 + 1 = 64，即第1个空闲链表的每个节点内存大小为1block(=16B), 第2个空闲链表的每个节点内存大小为2blocks(=32B)…第63个空闲链表的每个节点内存为63blocks(=1008B), 但最后一个第64个空闲链表的每个节点内存大于等于64blocks(>=1024B，该链表节点是free时合并产生)

magazine中的空闲链表数组结构如下

  • 对于16B空闲链表的节点，只存储前驱和后继节点指针

  • 对于大于16字节小于等于1008B空闲链表的节点，前面16字节存储前驱和后继指针，指针后两个字节存储块大小(如图，在free过程中向下一个block合并时用到), 最后两个字节也储存着块大小数据(在free过程中向上一个block合并时用到). 对应函数TINY_FREE_SIZE

  • 对于最后一个空闲链表，每个节点都是大于等于1024B. 其他指针，块大小数据布局同上.

SZone架构总结

整个宏观的架构设计就解释到这了，如下图

当然上面的解释还是太宏观了，很多巧妙的设计操作以及分配策略都没有提及，接下来就看看具体的malloc和free操作

Malloc and Free

tiny_malloc

tiny_malloc_should_clear 是整个分配流程, 在函数szone_malloc_should_clear中通过判断申请的内存大小调用的，当申请大小小于1009个字节时调用

msize

msize表示block申请大小单位，1表示申请1个block，16字节。当申请大小不满16B，分配1个block，申请大于16B小于等于32B，分配2个block, 以此类推…

具体实现: msize = (size+15) >> 4 即 msize = (size+15)/16

整个分配简介流程如下，后面对每个步骤过程会详细介绍 

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
void *
tiny_malloc_should_clear(rack_t *rack, msize_t msize, boolean_t cleared_requested) {
	
	// 1
	void *ptr;
	mag_index_t mag_index = tiny_mag_get_thread_index() % rack->num_magazines;
	magazine_t *tiny_mag_ptr = &(rack->magazines[mag_index]);
	
	// 2. 
	ptr = tiny_mag_ptr->mag_last_free;
	
	if (tiny_mag_ptr->mag_last_free_msize == msize) {
		tiny_mag_ptr->mag_last_free = NULL;
		tiny_mag_ptr->mag_last_free_msize = 0;
		tiny_mag_ptr->mag_last_free_rgn = NULL;
		
		if (cleared_requested) {
			memset(ptr, 0, TINY_BYTES_FOR_MSIZE(msize));
		}
		return ptr;
	}
	
	// 3.
	ptr = tiny_malloc_from_free_list(rack, tiny_mag_ptr, mag_index, msize);
	if (ptr) {
		if (cleared_requested) {
			memset(ptr, 0, TINY_BYTES_FOR_MSIZE(msize));
		}
		return ptr;
	}
	
	// 4.
	if (tiny_get_region_from_depot(rack, tiny_mag_ptr, mag_index, msize)) {
		ptr = tiny_malloc_from_free_list(rack, tiny_mag_ptr, mag_index, msize);
		if (ptr) {
			if (cleared_requested) {
				memset(ptr, 0, TINY_BYTES_FOR_MSIZE(msize));
			}
			return ptr;
		}
	}
	
	// 5.
	void *fresh_region;
	fresh_region = mvm_allocate_pages_securely(TINY_REGION_SIZE, TINY_BLOCKS_ALIGN, VM_MEMORY_MALLOC_TINY, rack->debug_flags);
	
	if (!fresh_region) {
		return NULL;
	}
	
	ptr = tiny_malloc_from_region_no_lock(rack, tiny_mag_ptr, mag_index, msize, fresh_region);
	return ptr
}
  1. current magazine 根据当前线程找到tiny_rack对应tiny _magazine, 之后的分配流程操作会基于该magazine
  2. last_free 判断该magazine的last_free cache大小和申请大小是否匹配，如果匹配，则分配该地址
  3. free_list of curretn magazine 2步骤失败，通过magazine的空闲链表分配
  4. free_list of depot magazine 3步骤失败，通过tiny _rack的depot _magazine的空闲链表分配
  5. mmap 4步骤失败，通过系统调用向内核申请一块heap region, 并从中分配
  6. return nil 5步骤失败，return nil

大致过程就介绍到这了，如果对细节不敢兴趣，可以直接跳到tiny_free了解free的过程

下面开始介绍详细过程

1. current magazine

函数tiny_mag_get_thread_index 根据当前线程所在的CPU核，获取tiny_rack的magazines的偏移，从而得到当前核的magazine

2. last_free

magazine属性mag_last_free, 表示该magazine最后一次free的地址(没有添加到空闲链表中)

通过上一步得到的magazine，判断magazine的mag_last_free_msize和当前申请大小(转换成msize)是否匹配, 如果匹配，则返回该地址mag_last_free

验证demo

1
2
3
4
5
void* ptr1 = malloc(16);    // msize = 1
printf("%p\n", ptr1);
free(ptr1);
void* ptr2 = malloc(1);     // msize = 1
printf("%p\n", ptr2);

打印可以发现ptr1和ptr2是同一地址

漏洞利用
如果cleared_requested为false, 那么mag _last _free分配出来的内存的内容不会被清除，还是上一个对象的内容

3. free_list of curretn magazine(重点)

函数tiny_malloc_from_free_list从当前magazine的空闲链表和last heap region中分配空间

从空闲链表分配也有好几个步骤

  1. free_list of msize 找到msize对应大小的空闲链表(之前说过magazine拥有空闲链表数组)，有节点，直接分配头节点
  1. first free_list which is more than msize and has node 1步骤失败，找到第一个比msize大, 节点不为空的空闲链表(bit操作)；有节点，分配节点，并将多余的块大小添加到对应的空闲链表中
  1. last free_list 查看空闲链表数组的最后一个空闲链表(节点内存大于1008B)是否有节点，如果有，则分配，并将多余的块大小添加到对应的空闲链表中
  1. last heap region 2，3步骤失败，表示当前magazine的空闲链表数组中比申请msize大的空闲链表都没有节点.
    从mag_last_region中申请内存，该heap region 是该magazine最后一次向内核申请的堆内存区域，有些内存block还没有用过(free过的存在空闲链表中)
  1. 4步骤失败，表示最后一块heap内存区域也没有多余的空间了，整个大的步骤结束
  1. return_tiny_alloc如果申请成功，做一些收尾工作，即将节点从空闲链表中移除，将多余的块作为节点添加到对应的空闲链表中，设置block对应的bitmap信息

下面是从空闲链表分配的详细过程

1. 从空闲链表数组中找到大小匹配的空闲链表

  1. 获取申请大小msize对应的空闲链表偏移(slot)，得到对应msize的空闲链表

    1
    2
    3
    4
    5
    6
    static inline grain_t
    tiny_slot_from_msize(msize_t msize)
    {
    	// msize > 63(tiny limit) ? 63 : msize-1
    	return (!msize || (msize > NUM_TINY_SLOTS) ? NUM_TINY_SLOTS : msize - 1);
    }

  1. 如果空闲链表有节点，该节点为这次申请内存地址，并将该节点从该空闲链表移除. 移除该节点，空闲链表如果没有节点，设置空闲链表metadata的bitmap对应的bit位为0 

    1
    2
    3
    4
    5
    6
    if (next) {
    	next->previous = ptr->previous;
    } else {
    	BITMAPV_CLR(tiny_mag_ptr->mag_bitmap, slot);  // 设置bit位
    }
    the_slot->p = next;   // (将空闲链表指向下一节点)

这里的tiny_malloc的bitmap用了8个字节64bit位表示该magazine的64个空闲链表，0表示链表无节点，1表示有链表节点

  1. 如果该空闲链表没有节点，接着走下面流程👇

2. 从第一个大于申请msize的空闲链表申请

比如申请的msize为2，但是msize为2对应的空闲链表没有节点，这时候查看msize为3，4，5…63的空闲链表

  1. 取出表示大于msize的bitmap 

    1
    bitmap = ((uint64_t *)(tiny_mag_ptr->mag_bitmap))[0] & ~((1ULL << slot) - 1);
小于msize对应的bit位设置为1

  1. 找到第一个bit不为0的bitmap的位置(slot偏移)

    1
    slot = BITMAPV_CTZ(bitmap);    // __builtin_ctzl(返回从第0位开始bit为0的bit个数)

  1. 通过1和2操作得到第一个大于申请msize的空闲链表偏移. 然后和上面一样判断节点有值与否，移除节点等操作

  2. 如果有节点，取得节点大小(上面说的大于16B的block节点中会存储该节点大小数据)，将该节点多余的block作为节点添加到对应大小的空闲链表中

    1
    2
    3
    4
    msize(申请大小)
    this_msize = TINY_FREE_SIZE(ptr);     // 取得该节点的block大小
    leftover_msize = this_msize - msize;  // 多余块大小
    tiny_free_list_add_ptr;			// 将多余块按照大小添加到对应的空闲链表
  1. 如果该空闲链表没有节点，接着走下面流程👇

3. 从最大的空闲链表(第64个)中申请

找到空闲链表数组的最后一个元素，即最大的空闲链表(节点大于等于1024B, >=64 Blocks)中查看是否有节点

  • 如果有, 和上面一样，从链表中移除该节点，设置bitmap, 将该节点多余的空间作为新节点添加到对应的空闲链表中

  • 如果没有, 接着走下面流程👇

4. 从最后一个heap region中分配

如果上述从空闲链表申请堆内存操作失败，表示之前所有的heap region中没有一块连续的大于等于申请大小的空间，因为之前的heap region的blocks要么在空闲链表中(free过的)，要么在使用中.

只有最后一个heap region中的blocks是在空闲链表中或者在使用中，或者从未使用过

因此从最后一个heap region中申请堆内存 

1
2
3
4
5
6
7
8
9
10
11
if (tiny_mag_ptr->mag_bytes_free_at_end >= TINY_BYTES_FOR_MSIZE(msize)) {
	ptr = (tiny_free_list_t *)((uintptr_t)TINY_REGION_END(tiny_mag_ptr->mag_last_region) - tiny_mag_ptr->mag_bytes_free_at_end);
	tiny_mag_ptr->mag_bytes_free_at_end -= TINY_BYTES_FOR_MSIZE(msize);
	if (tiny_mag_ptr->mag_bytes_free_at_end) {
		// let's add an in use block after ptr to serve as boundary
		set_tiny_meta_header_in_use_1((unsigned char *)ptr + TINY_BYTES_FOR_MSIZE(msize));
	}
	this_msize = msize;

	goto return_tiny_alloc;
}
  • mag_bytes_free_at_end表示该heap region还剩余的未使用过的大小
  • TINY_REGION_END(tiny_mag_ptr->mag_last_region)表示该heap region的blocks的尾位置

如下图

绿色块表示从未使用过，是连续的. mag_bytes_free_at_end即表示绿色块的大小
蓝色表示正在使用中
黄色的块是使用过且free了的，在free_list中

  1. 将最前面的绿色块位置作为此次申请的heap地址
  2. mag_bytes_free_at_end减掉此次申请的msize大小
  3. 如果该heap region还有block,设置刚刚申请块对应在metadata的bitmap的边界bit位为1, 作为下次申请的起始位置

Blocks Bitmap设置如下

其中每8个字节(64bit)表示32个blocks

  • 前面的32bit(蓝色)表示32个block的block_header(可以理解为连续blocks起始block)
    bit ···10010001 (block_header) | ···10010001 (in use) 表示第1个block到第4个block一段正在使用的连续空间，同理第5个block到第7个block也是如此

  • 后面32bit(绿色)中的bit表示blocks是否正在使用(1表示使用中，0表示未使用)
    bit ···10010001 (block_header) | ···10000001 (in use) 表示第1个block到第4个block一段正在使用的连续空间，但第5个block到第7个block表示的是free的连续空间

对应函数 

1
2
3
set_tiny_meta_header_in_use
set_tiny_meta_header_in_use_1(用来设置边界 or msize == 1)
set_tiny_meta_header_free

通过heap region的bitmap信息，在free的时候，可以知道free地址申请的内存大小

5. 收尾工作

  1. 在上面的过程中，如果成功分配了空间，则记录信息
  • 设置该magazine的mag_num_objects加一，该magazine字节使用mag_num_bytes_in_objects加上msize*16

  • 设置当前分配的堆地址所在的heap region的metadata. 包括该heap region的字节使用trailer->bytes_used和bitmap设置(上面解释了)

    通过堆地址，获取该地址所在的heap region的地址 (free时只需要地址的原因) 

1
2
// TINY_BLOCKS_ALIGN = 20
#define TINY_REGION_FOR_PTR(_p) ((void *)((uintptr_t)(_p) & ~((1 << TINY_BLOCKS_ALIGN) - 1)))

去掉 NUM _TINY _BLOCKS * TINY _QUANTUM(64520*16) 最多能占用的20个bit位. 得到region基地址

这是因为在向内核申请heap region时，指定了堆地址内存对齐为(1<<20)-1，顾所有的heap region起始地址后20个bit为0. 系统调用函数mach_vm_map的第4个参数为内存对齐

  1. 分配空间失败，走下面的流程👇

4. free_list of depot magazine

tiny_get_region_from_depot函数从depot magazine中寻找一个能分配msize空闲链表(大于等于msize)的第一个节点所在的heap region, 将该heap region从depot magazine移到current magazine

然后在从current magazine中分配(即上一步流程)

函数流程如下 

1
2
3
4
5
6
7
bool tiny_get_region_from_depot(...) {
	tiny_find_msize_region;
	recirc_list_extract;
	tiny_free_detach_region;
	tiny_free_reattach_region;
	recirc_list_splice_first;
}
  1. tiny_find_msize_region函数从depot magazine的空闲链表数组中寻找一个大于等于申请大小msize的节点(过程同上面free_lists一样)，通过节点地址得到该节点的heap region(TINY_REGION_FOR_PTR函数, 上面也说过)
  2. recirc_list_extract函数将上一步得到的heap region从depot magazine双向链表region_trailer中移除
  3. tiny_free_detach_region通过遍历heap regionblocks的bitmap，将free的blocks从depot magazine的空闲链表中移除
  4. tiny_free_reattach_region通过遍历heap regionblocks的bitmap，将free的blocks添加到current magazine的空闲链表中
  5. recirc_list_splice_first将heap region作为节点添加到current magazine的双向链表region_trailer中

变化过程如下(msize=2)

变化之前

变化之后

如果上面的tiny_find_msize_region失败，表示depot magazine空闲链表数组中也没有大于等于msize的节点. 接着走下面的流程👇

5. mmap

mvm_allocate_pages_securely向内核申请一块heap region

  • 失败，return nil
  • 成功，tiny_malloc_from_region_no_lock函数从刚刚申请的heap region中分配msize
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
void* tiny_malloc_from_region_no_lock(...) {
	
	// aligned_address = heap region地址
	
	// 1. 设置magazine最后一次向内核申请的heap地址
	tiny_mag_ptr->mag_last_region = aligned_address;
	
	// 2. ASLR 随机偏移（offset_msize的blocks丢弃不使用）
	#if CONFIG_ASLR_INTERNAL
		int offset_msize = malloc_entropy[0] & TINY_ENTROPY_MASK
	#else
		int offset_msize = 0; 
	#endif
	
	// 3. 得到申请地址
	ptr = aligned_address + offset_msize;
	
	// 4. 设置metadata信息
	/// 设置heap region的bit信息
	set_tiny_meta_header_in_use(ptr, msize);  // 设置使用bit
	set_tiny_meta_header_in_use_1;  // 设置边界bit
	
	/// 设置magazine信息
	mag_num_objects  
	mag_num_bytes_in_objects
	num_bytes_in_magazine
	mag_bytes_free_at_end
	
	// 5. 将heap region添加到magazine的node双向链表中
	recirc_list_splice_last;
	
	return ptr;
}

至此，整个tiny_malloc的过程就分析完了，下面看看对应的free过程tiny _free吧

tiny_free

函数free()通过函数find_registered_zone找到释放地址所在的zone, 再调用zone的basic_zone在zone创建时注册的free函数

s_zone注册的free函数为szone_free，szone_free会通过释放地址ptr尝试获取ptr所在的heap region, 包括tiny, small, medium. 如果tiny(<1009B)返回的heap region不为空, 则走free_tiny函数

对于tiny_free函数主要有3个步骤，如下

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
void free_tiny() {
	ptr  			// 当前释放地址
	msize 			// 当前释放堆大小
	tiny_region 	// 当前释放地址所在的heap region地址
	
	·
	·
	·
	
	// 1. 验证Double Free
	msize = get_tiny_meta_header(ptr, &is_free);   
	if (is_free) {
		free_tiny_botch(rack, ptr);    // 抛出异常
		return;
	}
	
	// 2. 设置last_free
	if (msize < 16) {
		void *ptr2 = tiny_mag_ptr->mag_last_free;  // Might be NULL
		msize_t msize2 = tiny_mag_ptr->mag_last_free_msize;
		region_t rgn2 = tiny_mag_ptr->mag_last_free_rgn;
		
		tiny_mag_ptr->mag_last_free = ptr;
		tiny_mag_ptr->mag_last_free_msize = msize;
		tiny_mag_ptr->mag_last_free_rgn = tiny_region;
		
		msize = msize2;
		ptr = ptr2;
		tiny_region = rgn2;
	}
	
	// 3. 释放last_free
	tiny_free_no_lock(..., tiny_region, ptr, msize);
}
  1. 根据heap region的metadata的bitmap，验证ptr是否是free过的(In Use对应的bit位为0)
  2. 设置free_cache, 如果释放内存小于16个msize,则此次释放地址设置成last_free, 然后对上一次的last_free操作
  3. 释放last_free

真正free堆内存在tiny_free_no_lock函数中

tiny_ free_ no_lock

正常只需要将释放地址作为节点添加到对应大小的空闲链表中，然后设置地址块对应的bitmap信息就行了.

但是在libmalloc的free中有个合并过程，合并为了整理内存碎片，为了之后分配更大的内存提供可能

tiny_ free_ no_lock函数如下

1
2
3
4
5
6
7
bool tiny_free_no_lock() {
	// 1. 向前合并
	
	// 2. 向后合并
	
	// 3. 更新bitmap信息，将合并结果添加到对应大小的空闲链表中；更新magazine的信息数据
}

向前合并(上一个block)

对于大于16字节空闲链表的节点，前面16字节存储前驱和后继指针，指针后两个字节存储块大小msize, 最后两个字节也储存着块大小msize. 对应函数TINY_FREE_SIZE

合并前如下图

图中红色表示当前释放的内存, 绿色表示在空闲链表的内存

合并后如下图

此时还没加入到空闲链表中，待下面向后合并步骤完成，才加入到空闲链表中

合并过程如下

  1. block_header:
    判断当前free ptr地址的前一个block是否是block_header

    根据bitmap判断，即图中100前一个bit是否为1

    如果是1则free ptr前1个block为单独的连续的空间，即为block_header
    如果不是1, 则表示free ptr前n个block为单独的连续的空间previous(如图所示)

  2. pre_size:
    如果前一个block是block_ header，那么连续空间previous大小pre_size等于1 

    如果不是block_header，表示连续空间`previous`大小大于1

    对于大于1的blocks, 如果该连续空间在空闲链表中，该空间的最后两个字节储存着该区域所占用的block大小(如图pre_size=2)

    如果该空间不在空闲链表中(不需要合并)，也暂时先读最后两个字节作为pre_size，之后再通过bitmap的block_header==1进行验证

  1. 验证:
    根据上一步获取到的pre_size，将free_ptr对应的bit位向前移动pre_size, 得到previous的起始位置对应的bit. 当该bit位的block_header=1, In Use=0 表示该连续区间在空闲链表中需要合并(如上图所示)

    但如果···1010100···(block_header) ···0010100···(in use)这种情况. 100还是要释放的内存, 前面的10内存块为使用中，这时候如果该内存块最后两个字节为4. 那么在合并中就会取100的前面4个块作为一个连续的区间，对应bit为1010(block_header) 0010(in use) ，此时验证也是正确的. 那么使用中的10两个内存block就会被合并

    解决: 验证该连续区域大小

    从1010(block_header) 0010(in use)内存起始位置计算得到的大小为2，与4不符合. 验证失败 （空闲链表节点的前驱后继指针之后(16字节之后)存储着块大小msize）

  2. 合并:

    如果free ptr前面的连续空间previous在空闲链表中，将free ptr和previous进行合并

    1. 先将previous从当前空闲链表中移除
    2. 清除free ptr内存区域对应的bitmap信息
    3. free ptr和previous大小和作为新free大小
    4. free ptr = previous

向后合并(下一个block)

对于大于16字节空闲链表的节点，前面16字节存储前驱和后继指针，指针后两个字节存储块大小msize

合并前如下图

合并后如下图

合并过程和上面类似

合并结束

合并结束后更新合并内存块对应的bitmap信息，将合并的内存块添加到对应的空闲链表中
更新magazine数据，更新当前heap region的metadata信息

至此，整个tiny_free过程结束

总结思考

libmalloc确实是一个优秀的用户堆管理库. 里面有许多优秀的分配策略设计, 并发的支持设计，内存碎片管理，性能考虑等等. 之前看有些书说过的堆设计的问题，它都有对应的解决策略

  1. 多核并发性设计

    采用一核对应一个堆管理magazine，让该核下的虚拟并发性能更好

  2. 堆管理最小单位

    将堆内存划分为多个相同大小的block, 即堆中的最小单位, 16B, 更利于空闲链表管理

  3. 采用空闲链表数组

    将不同大小的free了的堆空间组成不同空闲链表形成一个空闲链表数组，加快分配效率，更易于管理

  4. 多级分配策略

    • last free属性缓存;
    • 空闲链表匹配;
    • 寻找更大的空闲链表(分割处理多余的空间); // 对应bit优化算法找到空闲链表
    • 最后一个可利用的堆
    • 仓库depot magazine
    • 内核

  5. bitmap记录block信息

    使用64bit表示32个blocks信息; Block Header and In Use

  6. 系统调用返回对齐的heap region

    对齐20bit, 一个heap region中blocks能占用的空间，通过堆内存中的地址去掉后20bit可以获得该heap region的基地址

  7. 合并。碎片内存整理

    free过程中，整理前后内存碎片. 将碎片内存合并在一起，利用分配更大的堆内存

  8. 等等