explorer

万丈高楼平地起,勿在浮沙筑高台

0%

[What]Free-Space Management

理解内存管理的一些细节,如何尽量避免内存碎片又要保持内存申请和释放的高效率?

  • 外部碎片(external fragmentaion):指的是当被申请的内存空间遍布内存各个位置,导致剩下很多小的空闲内存,从而形成碎片
    • 这就会出现总空闲内存虽然远大于申请内存,但申请内存依然会失败的情况
  • 内部碎片(internal fragmentation):当内存管理器返回的内存大小大于申请的大小时,多于的部分程序不会使用,也就浪费了
    • 这是因为内存管理器以块为单位管理内存空间,申请得到的内存总是块大小的整数倍

底层机制

空闲空间的分散与聚合

现在先站在内存管理库(比如 glibc)的角度来看堆的内存管理。

使用一个空闲链表来保存空闲部分的地址和大小,比如一个堆的使用情况如下:

mempic/free_space_management/heap1.jpg

那么对应的链表结构如下:

mempic/free_space_management/list1.jpg

如上图所示,当用户要申请的内存大于 10 字节时,由于外部内存碎片,便会失败。

分散

假设用户仅申请 1 字节,并且内存管理器也是以 1 字节为最小切割单位,那么申请后的空闲链表就可能是这样:

mempic/free_space_management/list2.jpg

这样就相当于链表选择了第二个空闲部分,malloc() 返回的地址是 20,并且此时第二个空闲部分相当于被切割了 1 字节下来。

聚合

假设用户释放中间的 10 字节堆空间,那么释放后的内存空间链表就是这样:

mempic/free_space_management/list3.jpg

但如果是这样的话,用户要一次性申请大于 10 字节空间时,依然也会失败,因为每个块的大小只有 10 字节。

所以我们需要聚合空闲块:当发生一次内存释放后,查找其紧连邻居节点是否有空闲,如果有空闲则整个为一个节点。 整合后的空闲链表如下:

mempic/free_space_management/list4.jpg

已申请空间的保存

当我们使用 free() 时,接口仅提供了内存的首地址,那就说明内存管理器保存了其申请空间的大小。

以一个简单的示例说明,实际上用户申请 N 字节内存, 内存管理器真正申请是大于 N 字节内存的,因为还需要一个头来保存这块内存的信息

mempic/free_space_management/heap2.jpg

如上图所示,用户通过 malloc() 得到的是 ptr,实际上管理器还用了 hptr 保存了申请空间的大小还有对应的魔数以验证地址的正确性。

当用户通过 free() 释放内存时,内存管理器的大致流程如下:

  1. 通过 ptr 减去固定值得到 hptr
  2. 首先验证 hptr->magic 是否正确,以确认用户释放的地址无误
  3. 然后开始释放 hptr->size + sizeof(header) 这么多字节的内存

整体流程

实际上无论是空闲链表的每个节点还是已申请空间的每个块都需要一个头来保存当前内存块的信息,这就类似于文件系统的 metadata 和 block 一样。

最开始的空闲链表

下面假设有 4 KB 的内存空间,最开始全部空闲,那么使用空闲链表后的堆内存如下(假设头大小为 8 字节):

mempic/free_space_management/process1.jpg

可以看到,除开头的 8 字节后,真正用户能够申请的空间只有 4088 字节。

申请内存

当用户申请一个 100 字节的空间后,除了真正的 100 字节空间还需要头来保存这块内存信息:

mempic/free_space_management/process2.jpg

接下来再连续申请:

mempic/free_space_management/process3.jpg

释放内存

释放中间地址后将其插入空闲列表头:

mempic/free_space_management/process4.jpg

接下来释放其他所有空间:

mempic/free_space_management/process5.jpg

可以看到当没有使用聚合的情况下,这空闲内存就分为了好几个小块。

申请更大的内存

一般内存管理库最开始为向操作系统申请一块内存用于用户申请。

当申请的内存过大时,内存管理库又会再次向操作系统申请一大块内存,然后此时申请内存的 API 才返回成功。

示例程序

下面这段示例代码便是很好的展示了内存碎片是如何产生的:

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
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
#include <stdio.h>
#include <assert.h>
#include <sys/mman.h>
#include <stdint.h>
#include <string.h>

#define MEM_SIZE (4096)
#define MAGIC (0x12345678)

#if __SIZEOF_POINTER == 4
#define INT_TYPE int32_t
#else
#define INT_TYPE int64_t
#endif
typedef struct __node_t
{
INT_TYPE size;
struct __node_t *next;
}node_t;
typedef struct{
INT_TYPE size;
INT_TYPE magic;
}header_t;

static node_t *free_head;

static void print_mem(void)
{

printf("-----------------\n");
printf("The free spaces of memory are:\n");

node_t *node = free_head;

uint8_t free_cnt = 1;

do
{
printf("free node <%d> at %p with %ld bytes\n",
free_cnt++, node, node->size);
node = node->next;
}while(node);
printf("-----------------\n");
}

static void create_mem(void)
{

free_head = mmap(NULL, MEM_SIZE, PROT_READ | PROT_WRITE,
MAP_ANON | MAP_PRIVATE, -1, 0);
assert(free_head);

free_head->size = MEM_SIZE - sizeof(node_t);
free_head->next = NULL;

print_mem();
}
static void my_free(void *ptr)
{

header_t *use_head = ptr - sizeof(header_t);
assert(use_head->magic == MAGIC);

node_t *node = free_head;
while(node->next)
{
node = node->next;
}
node_t *new_node = (node_t *)use_head;
new_node->next = NULL;
node->next = new_node;

print_mem();
}
static void *my_malloc(int size)
{

void *ptr = NULL;

node_t *node = free_head;
node_t *prev = NULL;

printf("finding free space...\n");
while(node)
{
printf("find node %p, with space %ld, next-> %p\n",
node, node->size, node->next);
if(node->size >= size)
{
//move or insert a new node
uint16_t offset = sizeof(node_t) + size;
uint16_t free_size = node->size - size - sizeof(node_t);
printf("offset = %d\n", offset);
if(node == free_head)
{
free_head = (node_t *)((uint8_t *)free_head + offset);
free_head->size = free_size;
}
else
{
node_t *new_node = (node_t *)((uint8_t *)node + offset);
new_node->size = free_size;
new_node->next = NULL;

prev->next = new_node;
}

header_t *use_head = (header_t *)node;
use_head->magic = MAGIC;
use_head->size = size;

ptr = (void *)((uint8_t *)use_head + sizeof(header_t));

printf("used header : addr %p, size %ld\n",
use_head, use_head->size);

break;
}

prev = node;
node = node->next;
}
print_mem();

if(!ptr)
{
printf("error: Sorry, I didn't find free space!\n");
}
else
{
printf("The address of malloc space is %p\n", ptr);
}


return ptr;
}

int main(void)
{

create_mem();

uint8_t *m1 = (uint8_t *)my_malloc(1000);
assert(m1);
memset(m1, 1, 1000);
uint8_t *m2 = (uint8_t *)my_malloc(1000);
assert(m2);
memset(m2, 2, 1000);
uint8_t *m3 = (uint8_t *)my_malloc(1000);
assert(m3);
memset(m3, 3, 1000);
uint8_t *m4 = (uint8_t *)my_malloc(1000);
assert(m4);
memset(m4, 4, 1000);

printf("\nfree memory:\n");
my_free(m2);
my_free(m4);

uint8_t *m5 = (uint8_t *)my_malloc(2000);
assert(m5);
memset(m5, 5, 1000);

return 0;
}

基础策略

为了更好的管理空闲空间,有下面这些基础策略。

best fit

将内存空间预选分隔为大小不同的多种块,当用户申请内存时,从遍历空闲列表,从空闲块中找出最小能满足申请需求的一块。

  • 优点:尽量的避免内存浪费
  • 缺点:每次查找最小块所耗费的时间较长

worst fit

best fit 不同,当用户申请内存时,从空闲块中找出最大的一块内存,然后将剩余的内存放入空闲列表。

  • 优点:相比 best fit 更能避免内存浪费,因为 best fit 找到最小块后剩余的空闲部分有很大概率不会满足今后的申请大小需求了
  • 缺点:每次查找最大块所耗费的时间较长

first fit

当用户申请内存时,找到第一个可以满足要求的内存块,剩余的部分放回空闲列表。

  • 优点:查询速度相比前两者要快得多
  • 缺点:这种方式将会产生很多小的内存块
    • 如果内存列表是按照地址依次排列的话,可以将地址连续的小内存块和后面的一个块进行合并,以减少碎片

next fit

使用一个指针保存上一次搜寻到的位置,下一次用户申请时,便从此处继续往后搜寻。

  • 优点:相比 first fit ,这种方式避免在空闲列表开头的部分存在很多碎片,而是使其均匀分布
  • 缺点:依然会有合并内存碎片的需求

示例

假设空闲内存列表如下,用户需要申请 15 字节的内存:

mempic/free_space_management/fit_normal.jpg

那么按照 best fit 的策略,先遍历列表,找出最小满足块,那么就会选择第三块空闲块,最终的空闲列表如下:

mempic/free_space_management/fit_best.jpg

这样如果用户还想继续再申请两个 15 字节内存的话,这张列表只能成功申请一次了。

按照 worst fit 的策略,先遍历列表,找出最大满足块,那么就会选择第二块空闲块,最终的空闲列表如下:

mempic/free_space_management/fit_worst.jpg

可以看到,如果这时用户还想继续再申请两个 15 字节内存的话,这张列表是可以满足了,因为 worst fit 策略可以尽量保证空闲块尽量的大,而不是很多无效的小块。

按照 first fit 策略的搜寻结果和 worst fit 一致,但是 first fit 只要找到了便停止搜寻了,效率会高很多。 而 next fit 下一次寻找就会紧接着 first fit 进行。

其他策略

分离列表

当应用经常频繁的申请相同的大小块内存时,可以特地分配一大块内存,内存中的每一个小块的大小即为常用申请块大小。

这样做有以下两点好处:

  1. 由于申请的内存大小和块一样的,所以不会出现内存碎片
  2. 由于空闲列表上块的大小一致,所以也不需要查找了

kernel 会在最开始为常用的数据结构申请对应的大小的块列表,当对于列表被用完时,又会申请一大块内存。

buddy 分配器

mempic/free_space_management/buddy.jpg

buddy 分配器的每一块空闲空间的大小是 2^N 字节。 当有申请内存的请求发出时,buddy 递归的将空闲空间一分为二,直到找到一块能最小满足该请求的内存块。

  • 比如上述有 64KB 空闲空间,当用户要申请 7KB 空间时,64KB 先分为两个 32 KB,然后是 16KB,最后找到 8KB 可以满足最小块。

当用户释放被申请的空间后,这块空间便会看它旁边的块是否空闲,如果也是空闲的便合并二者,这样一直递归合并,直到合并完毕或遇到伙伴块不空闲。

  • 比如刚刚申请的块释放,那么会和 8KB 合并为 16KB,16KB 又会和其 buddy 合并为 32KB,最终又会合并为 64 KB 的空闲空间。

这种方式避免了内部的内存碎片。

Last Updated 2020-06-28 Sun 11:59.
Render by hexo-renderer-org with Emacs 26.3 (Org mode 9.3.7)