五十行代码教你写一个简单的内存池（二级指针的应用）

固定大小内存的内存池实现

该内存池是一个很简单的内存池，只能申请固定大小的内存，仅供学习

要点：

• 构造隐式链表
• 二级指针

存储结构

typedef struct mempool_s{
    int block_size;  // 每一块的大虚哎
    int free_count;  // 剩余有多少块是可以用的
    char *free_ptr;  // 可以分配的开始位置
    char *mem;       // 指向4k的起始位置
}mempool_t;
1
2
3
4
5
6

开放的API

• int memp_init(mempool_t * m, int block_size)

  对内存池每一项都赋值，用malloc申请大块内存，让mem指向malloc，

  这里面有特殊操作：构建隐式链表

• void* memp_alloc(mempool_t* m)

  以free_ptr链开始分配

• void* memp_free(mempool_t* m, void *ptr)
  释放给定的内存块，并将它头插在隐式链表中

构建隐式链表

我们会用malloc分配一个4k大小的内存，mem指向这块起始地址，free_ptr指向可以分配的内存的起始地址

每次从内存池中分配一个32字节大小的内存块，于是4k内存就分分割为下图所示

现在就有一些问题

• 如何管理些块块内存？

• 分配时分配哪一个块？

• 释放了的块怎么回收？

上述这些问题全部都可以用隐式链表来解决

构造隐式链表的思路：

每次我们申请的是32个字节，我们可以将前面8个字节拿来存储next指针，也就是下一个块的地址，这样我们的内存就变成了这样

这样的话我们就构建了一个隐式链表，每次分配就从头部取，每次挥手就将32B的块头插进这个链表

如何实现

利用二级指针可以很方便的实现隐式链表的构造。

二级指针是一个指向指针的指针

操作

假设有下述4K内存

char * free_ptr = malloc(1024);
1

每个块的大小为32用变量block_size表示

int block_size = 32;
1

一共有1024/32个块用free_count表示

int free_count = 1024 / block_size;
1

使用二级指针

int i = 0;
char *ptr = m->free_ptr;
for(i = 0; i < m->free_count; i++){
    *(char**)ptr = ptr + block_size; 
    ptr += block_size;
}
*(char**)ptr = NULL;
1
2
3
4
5
6
7

ptr一级指针被强转为了二级指针，ptr本来是指向一个字节（char）的指针，现在变为了指向8个字节的指针，

对于这一*(char**)ptr解引用操作，就能够操作以ptr原本指向的一字节开始的八个字节，就将这8个字节赋予为下一个块的地址ptr + block_size，这里不懂的话最后还会有一个二级指针操作队列尾部的例子。

这里我有必要解释一下一级指针与二级指针以char为例

• char*一级指针，指向char类型的指针，char类型为一字节，也可以说是指向一个字节的指针
• char**二级指针，指向char*类型的指针，由于64位下指针类型大小为8个字节所以，也可以说是指向8个字节的指针

经过上述操作，就隐式的构建了链表这样一来内存池内存块的管理就实现了。

• 分配时从free_ptr中取出
• 回收时从将内存块插入链表的头部

完整代码实现

#include 
#include 
// 实现一个分配固定大小块的内存池
// 将4k的内存分割为大小相等的块  比如 32bytes/block  就有128个块
#define MEM_PAGE_SIZE 0X1000
typedef struct mempool_s{
    int block_size;  // 每一块
    int free_count;  // 剩余有多少块 可以用
    char *free_ptr;  // 可以分配的开始位置
    char *mem;       // 指向4k的起始位置
}mempool_t;
1
2
3
4
5
6
7
8
9
10
11

初始化内存池块

int memp_init(mempool_t * m, int block_size){  // 初始化4k内存
    if(!m) return -2;
    // 对内存池的每一项赋值
    m->block_size = block_size;
    m->free_count = MEM_PAGE_SIZE / block_size;  // 4k/32
    m->free_ptr = (char*)malloc(MEM_PAGE_SIZE);
    if(!m->free_ptr) return -1;
    m->mem = m->free_ptr;

    // 构建了隐式链表
    int i = 0;
    char *ptr = m->free_ptr;
    for(i = 0; i < m->free_count; i++){
        *(char**)ptr = ptr + block_size; 
        ptr += block_size;
    }
    *(char**)ptr = NULL;
    return 0;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19

分配内存块

// 以free_ptr链开始分配
void* memp_alloc(mempool_t* m){  // 已经确定了固定大小  不需要传入大小
    if(!m || m->free_count == 0) return NULL;
    void *ptr = m->free_ptr;
    m->free_ptr = *(char**)ptr;  // 后移指向下一个空闲处
    m->free_count--;

    return ptr;
}
1
2
3
4
5
6
7
8
9

回收内存块

void* memp_free(mempool_t* m, void *ptr){  // 
    // 将空闲块头插 进空闲列表
    *(char**)ptr = m->free_ptr;
    void * old_free = (void*)m->free_ptr;
    m->free_ptr = (char*)ptr;

    m->free_count++;

    return old_free;
}
1
2
3
4
5
6
7
8
9
10

测试

int main(){
    mempool_t m;
    int i = memp_init(&m, 32);
    printf("%d\n", i);
    void* p1 = memp_alloc(&m);
    printf("memp_alloc : %p\n", p1);
    void* p2 = memp_alloc(&m);
    printf("memp_alloc : %p\n", p2);
    void* p3 = memp_alloc(&m);
    printf("memp_alloc : %p\n", p3);
    void* p4 = memp_alloc(&m);
    printf("memp_alloc : %p\n", p4);
    memp_free(&m, p1);
    memp_free(&m, p3);
    void* p5 = memp_alloc(&m);
    printf("memp_alloc : %p\n", p5);
    void* p6 = memp_alloc(&m);
    printf("memp_alloc : %p\n", p6);
    
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20

打印

memp_alloc : 0x5624aa9cc260 # p1
memp_alloc : 0x5624aa9cc280 # p2
memp_alloc : 0x5624aa9cc2a0 # p3
memp_alloc : 0x5624aa9cc2c0 # p4
memp_alloc : 0x5624aa9cc2a0 # p5
memp_alloc : 0x5624aa9cc260 # p6
1
2
3
4
5
6

这个内存池存在的问题

可以明显的看见，我们分配的32个字节的内存其中将前面8个字节用来构造了隐式链表，所以实际能用的内存只有32-8，并且如果你分配的块的大小小于8，则上述程序会出现段错误

二级指针操作自定义类型

自定义类型二级指针的应用

假设有下列结构

typedef struct task_s {
    task_t *next;  // 必须是第一个字段
    handler_pt func;
    void *arg;
} task_t;

1
2
3
4
5
6

初始化

task_t *a = malloc(sizeof(task_t));
1

二级指针操作

*(task_t**)a = NULL;  // 等价于 a->next = NULL;
1

解释：a本来是一个task_t类型的指针，由于task_t有24个字节，也可以说a是指向24个字节的指针，由于a被转为了二级指针，意思就是现在a是一个指向8个字节的指针，该8个字节就对应task_t中前8个字节也就是next指针，与是解引用就是相当于解了next指针的引用