Linux 内核内存池原理与实现___alloc_size__

1. 内存池原理

实际开发中，为了避免频繁执行malloc/fre产生的内存碎片，通常会在程序中设计单独的内存管理模块，即内存池。原理：程序启动时为内存池申请一块比较大的内存区，程序在使用内存时全部是由内存池进行分配的，不再使用内存时，交给内存池回收，用于再次分配，优点在于内存分配效率的提升。

2. 内存池数据结构源码分析

2.1 数据结构

typedef struct mempool_s {
	spinlock_t lock;  // 防止多处理器并发引入的一种锁
	int min_nr;		// elements 数组中的成员数量
	int curr_nr;		// 当前elements数组中空闲的成员数量 
	void **elements;   // 用来存放内存成员的二维数组，长度：min_nr 宽度：各个内存对象的长度

	void *pool_data;  // 内存池与内核缓冲区结合使用（这个指针专门用来指向这种内存对象对应的缓存区的指针）
	mempool_alloc_t *alloc; // 用户在创建一个内存池对象时，提供的内存分配函数。
							//（此函数可以是用户自己定义的，也可以是系统提供的API）
	mempool_free_t *free;  // 内存释放函数
	wait_queue_head_t wait; // 任务等待队列 
} mempool_t;
1
2
3
4
5
6
7
8
9
10
11
12

2.2 内存池创建函数

2.3 内存池分配内存

2.4 内存对象重新放到内存池

3. 内存池设计实现（简单的内存池程序）

3.1 设计思路

• 获取内存映射表的位置
• 获取内存所在位置
• 获取内存分配表的位置
• 内存池初始化
• 内存分配
• 内存释放
• 内存池销毁
  

3.2 代码实现

#include <stdio.h>
#include <stdlib.h>
#include <string.h>

#define ALLOC_SIZE 8
#define LOOP 5
#define MAX_POOL_SIZE 1024 * 1024 
#define BLOCK_SIZE 64

typedef struct memory_map_table {
    char *p_block;
    int index;
    int used;
}Memory_Map_Table;

typedef struct memory_alloc_table {
    char *p_start;
    int used;
    int block_start_index;
    int block_cnt;
}Memory_Alloc_Table;

typedef struct memory_pool {
    char *memory_start;
    Memory_Alloc_Table *alloc_table;
    Memory_Map_Table *map_table;
    int total_size;
    int internal_total_size;
    int increment;
    int used_size;
    int block_size;
    int block_cnt;
    int alloc_cnt;
}Memory_Pool;

// 获取内存映射表所对应的位置
Memory_Map_Table *map_table_pos(Memory_Pool *pool) {
    Memory_Map_Table *pm = (Memory_Map_Table *)(pool->memory_start + sizeof(Memory_Pool));
    return pm;
}

// 获取内存分配表
Memory_Alloc_Table *alloc_table_pos(Memory_Pool *pool) {
    Memory_Alloc_Table *pm = (Memory_Alloc_Table *)(pool->memory_start + sizeof(Memory_Pool) \
        + sizeof(Memory_Map_Table) * (pool->block_cnt));
    return pm;
}

// 获取内存所在位置
char * memory_pos(Memory_Pool *pool) {
    char *pm = (char *)(pool->memory_start + sizeof(Memory_Pool) \
        + (sizeof(Memory_Map_Table) + sizeof(Memory_Alloc_Table)) * pool->block_cnt);
    
    return pm;
}

// 初始化内存池
Memory_Pool *Memory_pool_init(int size, int increment) {
    char *p = NULL;
    char *p_memory = NULL;
    Memory_Pool *pool = NULL;
    Memory_Alloc_Table *alloc_table = NULL;
    Memory_Alloc_Table *p_alloc_table = NULL;
    Memory_Map_Table *map_table = NULL;
    Memory_Map_Table *p_map_table = NULL;

    int block_cnt = 0;
    int all_size = 0;
    int i = 0;

    if (size < 0 || size > MAX_POOL_SIZE) {
        printf("Memory_pool_init(): Invalid size(%d). \n", size);
        return pool;
    }

    block_cnt = (size + BLOCK_SIZE - 1) / BLOCK_SIZE;
    all_size = sizeof(Memory_Pool) + (sizeof(Memory_Map_Table) + sizeof(Memory_Alloc_Table)) * block_cnt + size;

    p = (char *)malloc(all_size);

    if (p == NULL) {
        printf("Malloc Failed.\n");
        return pool;
    }

    memset(p, 0, all_size);
    pool = (Memory_Pool *)p;
    pool->block_cnt = block_cnt;
    pool->block_size = BLOCK_SIZE;
    pool->increment = increment;
    pool->internal_total_size = BLOCK_SIZE * block_cnt;
    pool->total_size = size;
    pool->used_size = 0;
    pool->alloc_cnt = 0;
    pool->memory_start = p;

    p_memory = memory_pos(pool);
    map_table = map_table_pos(pool);
    for (i = 0; i < block_cnt; i ++) {
        p_map_table = (Memory_Map_Table *)((char *)map_table + i * sizeof(Memory_Map_Table));
        p_map_table->index = 0;
        p_map_table->p_block = p_memory + i * BLOCK_SIZE;
        p_map_table->used = 0;
    }

    alloc_table = alloc_table_pos(pool);
    for (i = 0; i < block_cnt; i ++) {
        p_alloc_table = (Memory_Alloc_Table *)((char *)alloc_table + i * sizeof(Memory_Alloc_Table));
        p_alloc_table->block_cnt = 0;
        p_alloc_table->block_start_index = 1;
        p_alloc_table->p_start = NULL;
        p_alloc_table->used = 0;
    }
    
    printf("Memory_pool_init: total size: %d, block cnt: %d, block size: %d\n", \
        pool->total_size, pool->block_cnt, BLOCK_SIZE);

    return pool;
}

// 分配内存
void *Memory_alloc(Memory_Pool *pool, int size) {
    char *p_start = NULL;
    int need_block_cnt = 0;
    Memory_Alloc_Table *alloc_table = NULL;
    Memory_Alloc_Table *p_alloc_table = NULL;
    Memory_Map_Table *map_table = NULL;
    Memory_Map_Table *p_map_table = NULL;

    int block_cnt = 0;
    int start_index = -1;
    int i = 0;

    if (size <= 0) {
        printf("Memory_alloc(): Invalid size(%d) \n", size);
        return p_start;
    }
    
    if (size > pool->total_size) {
        printf("Memory_alloc(): %d is more than total size.\n", size);
        return p_start;
    }

    if (size > pool->total_size - pool->used_size) {
        printf("Memory_alloc(): free memory(%d) is less than allocated(%d).\n ", pool->total_size - pool->used_size, size);
        return NULL;
    }

    need_block_cnt = (size + BLOCK_SIZE - 1) / BLOCK_SIZE;
    map_table = map_table_pos(pool);
    
    start_index = -1;
    for (i = 0; i < pool->block_cnt; i ++) {
        p_map_table = (Memory_Map_Table *)((char *)map_table + i * sizeof(Memory_Map_Table));
        if (p_map_table->used) {
            block_cnt = 0;
            start_index = -1;
            continue;
        }

        if (start_index == -1) 
        start_index = i;
        block_cnt ++;

        if (block_cnt == need_block_cnt) 
            break;
    }

    if (start_index == -1) {
        printf("No available memory to used.\n");
        return NULL;
    }

    alloc_table = alloc_table_pos(pool);

    for (i = 0; i < pool->block_cnt; i ++) {
        p_alloc_table = (Memory_Alloc_Table *)((char *)alloc_table + i * sizeof(Memory_Alloc_Table));
        if (p_alloc_table->used == 0) 
            break;
        p_alloc_table = NULL;
    }

    if (p_alloc_table == NULL) {
        return NULL;
    }
    
    p_map_table = (Memory_Map_Table *)((char *)map_table + sizeof(Memory_Map_Table) * start_index);
    p_alloc_table->p_start = p_map_table->p_block;
    p_alloc_table->block_start_index = p_map_table->index;
    p_alloc_table->block_cnt = block_cnt;
    p_alloc_table->used = 1;

    for (i = start_index; i < start_index + block_cnt; i ++) {
        p_map_table = (Memory_Map_Table *)((char *)map_table + i * sizeof(Memory_Map_Table));
        p_map_table->used = 1;
    }

    printf("Alloc size: %d, Block: (start: %d, end: %d, cnt: %d) \n", \
        size, start_index, start_index + block_cnt - 1, block_cnt);
    pool->block_cnt ++;
    pool->used_size += size;

    return p_alloc_table->p_start;    
}

// 内存释放
void Memory_free(Memory_Pool *pool, void *memory) {
    Memory_Alloc_Table *alloc_table = NULL;
    Memory_Alloc_Table *p_alloc_table = NULL;
    Memory_Map_Table *map_table = NULL;
    Memory_Map_Table *p_map_table = NULL;

    int i = 0;
    int block_start_index = 0;
    int block_cnt = 0;

    if (memory == NULL) {
        printf("Memory_free(): memory is NULL.\n");
        return;
    }

    if (pool == NULL) {
        printf("Pool is NULL.\n");
        return;
    }

    alloc_table = alloc_table_pos(pool);
    for (i = 0; i < pool->alloc_cnt; i ++) {
        p_alloc_table = (Memory_Alloc_Table *)((char *)alloc_table + i * sizeof(Memory_Alloc_Table));
        if (p_alloc_table->p_start == memory) {
            block_start_index = p_alloc_table->block_start_index;
            block_cnt = p_alloc_table->block_cnt;
        }
    }

    if (block_cnt == 0) {
        return;
    }

    map_table = map_table_pos(pool);
    printf("Block_Free: start: %d, end: %d, cnt: %d\n", block_start_index,\
        block_start_index + block_cnt - 1, block_cnt);
    
    for (i = block_start_index; i < block_start_index + block_cnt; i ++) {
        p_map_table = (Memory_Map_Table *)((char *)map_table + i * sizeof(Memory_Map_Table));
        p_map_table->used = 0;
    }

    p_alloc_table->used = 0;
    pool->used_size = block_cnt *BLOCK_SIZE;

    return;
}

// 销毁内存池
void Memory_pool_destroy(Memory_Pool *pool) {
    if (pool == NULL) {
        printf("Memory_pool_destroy: pool is NULL.\n");
        return;
    }

    free(pool);
    pool = NULL;

    return;
}

int main() {
    Memory_Pool *pool = NULL;
    char *p1 = NULL;
    int i = 0;

    pool = Memory_pool_init(1024, 512);
    if (pool == NULL) {
        printf("Memory_pool_init error.\n");
    }

    for (i = 0; i < 2; i ++) {
        p1 = (char *)Memory_alloc(pool, ALLOC_SIZE);
        if (p1 == NULL) {
            printf("Malloc failed.\n");
        } else {
            printf("Malloc success.\n");
        }
        Memory_free(pool, p1);
    }
    Memory_pool_destroy(pool);
    return 0;
}
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
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
230
231
232
233
234
235
236
237
238
239
240
241
242
243
244
245
246
247
248
249
250
251
252
253
254
255
256
257
258
259
260
261
262
263
264
265
266
267
268
269
270
271
272
273
274
275
276
277
278
279
280
281
282
283
284
285
286
287
288
289

参考

推荐一个零声学院免费公开课程，个人觉得老师讲得不错，分享给大家：[Linux，Nginx，ZeroMQ，MySQL，Redis，fastdfs，MongoDB，ZK，流媒体，CDN，P2P，K8S，Docker，TCP/IP，协程，DPDK等技术内容，点击立即学习:https://course.0voice.com/v1/course/intro?courseId=5&agentId=0