skaiuijing

引言

在前面连续讲了几章的Linux内核网络协议栈与内存。我们知道数据包在进入内核时会写入到ringbuf指定的地址中，而这些内存空间是提前建立的内存缓冲区。

在FreeBSD中，也有cluster这种内存空间的存在，当分配一定大小的数据包时，内核会直接从cluster 中拿一块内存。

我们要实现的网络协议栈肯定没有这些复杂度策略，不过为了学习这种预先分配的设计以及为了更好的管理内存，让我们设计一个内存池。

内存池

设计

使用两条链表维护，内存池的布局如图：

1
2
3
graph LR
Aa(头部)--空闲链表-->Ab(空闲内存块)--空闲链表-->Ba(空闲内存块)-->C(下一个空闲内存块)
Aa--连接链表-->Ab--连接链表-->Ba

分配

当发生内存块分配时，该空闲内存块会被踢出空闲链表，但仍然会保持连接链表的连接：

1
2
3
4
5
6
graph LR
Aa(头部)--空闲链表-->Ba(空闲内存块)--连接链表-->C
Ab(已分配的内存块)

Aa--连接链表-->Ab--连接链表-->Ba--空闲链表-->C(下一个空闲内存块)

这样可以保证每次只使用一次迭代，就可以获取到空闲内存块。

回收

重新讲已分配内存池插入空闲链表即可：

1
2
3
4
graph LR
Aa(头部)--空闲链表-->Ab(空闲内存块)--空闲链表-->Ba-->C(下一个空闲内存块)
Ba(已分配的内存块)
Aa--连接链表-->Ab--连接链表-->Ba

代码实现

基本结构定义

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
Class(PoolNode)
{
    uint8_t used;
    struct list_node free_node;
    PoolNode *next;
};

Class(PoolHead)
{
    PoolNode *head;
    struct list_node free_list;
    size_t BlockSize;
    size_t AllCount;
    uint8_t RemainNode;
};

这段定义了两类结构：

  • PoolNode

    used：标记此块是否已被分配（0=空闲，1=已用）

    free_node：用于将节点串入空闲链表的链表节点

    next：指向下一个物理相邻的 PoolNode

  • PoolHead

    head：第一块 PoolNode 的地址

    free_list：头部的空闲链表，所有空闲节点都挂到这一条链上

    BlockSize：每个用户数据块的大小

    AllCount：总共能分配的节点数

    RemainNode：当前剩余的空闲节点数

初始化节点链表

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
void pool_apart(PoolHead *ThePool, uint8_t amount, size_t apart_size)
{
    PoolNode *prev_node = ThePool->head;
    PoolNode *new_node;

    while(amount != 0) {
        new_node = (PoolNode *)(((size_t)prev_node) + apart_size);
        new_node->used = 0;
        list_add_next(&prev_node->free_node, &new_node->free_node);
        prev_node->next = new_node;
        prev_node = new_node;
        amount--;
    }
    new_node->next = NULL;
}
  • 从 head 开始，按 apart_size（含对齐和节点头）逐块“切分”
  • 每新切出一个 new_node：
    1. 标记 used = 0
    2. 插入空闲链表
    3. 用 next 串入物理相邻顺序
  • 循环 amount 次后，将最后一个节点 next = NULL

创建内存池

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
PoolHeadHandle memPool_creat(uint16_t size, uint8_t amount)
{
    size_t apart_size = size + NodeStructSize;
    if(apart_size & alignment_byte) {
        apart_size += alignment_byte + 1 - (apart_size & alignment_byte);
    }

    uint32_t all_size = amount * apart_size + HeadStructSize;
    void *start_address = malloc(all_size);
    if (!start_address) return false;

    PoolHead *ThePool = (PoolHead *)start_address;
    *ThePool = (PoolHead){
        .head = (PoolNode *)((size_t)start_address + HeadStructSize),
        .BlockSize = size,
        .AllCount = amount,
        .RemainNode = amount
    };
    ThePool->head->used = 0;
    list_node_init(&ThePool->free_list);

    PoolNode *first_node = ThePool->head;
    list_add_next(&ThePool->free_list, &first_node->free_node);

    pool_apart(ThePool, amount - 1, apart_size);
    return ThePool;
}
  • 计算每块 apart_size（用户块 + 节点头 + 对齐补齐）
  • 计算总申请字节数 all_size，并从 heap 中拿一大块
  • 在最前面布置一个 PoolHead 结构，指向后续第一个 PoolNode
  • 将第一个节点插入空闲链表，再调用 pool_apart 切分其余节点

分配块

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
void *memPool_apl(PoolHeadHandle ThePool)
{
    if (!ThePool) return NULL;
    if (ThePool->free_list.next == &ThePool->free_list) return NULL;

    PoolNode *use_node = container_of(ThePool->free_list.next, PoolNode, free_node);
    list_remove(ThePool->free_list.next);

    if (use_node->used == 0) {
        use_node->used = 1;
        ThePool->RemainNode--;
        return (void *)((uint8_t *)use_node + NodeStructSize);
    }
    return NULL;
}
  • 检查池是否存在，或空闲链表是否为空
  • 取出空闲链表头部节点 use_node
  • 标记 used=1，剩余节点计数减一
  • 返回节点的“用户数据区”地址（跳过头部结构）

释放块

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
void memPool_free(PoolHeadHandle ThePool, void *xRet)
{
    if (!xRet) return;
    PoolNode *FreeBlock = (PoolNode *)((uint8_t *)xRet - NodeStructSize);
    FreeBlock->used = 0;

    PoolNode *find_node = FreeBlock->next;
    while (find_node && find_node->used != 0) {
        find_node = find_node->next;
    }

    if (find_node) {
        list_add_prev(&find_node->free_node, &FreeBlock->free_node);
    } else {
        list_add_prev(&ThePool->free_list, &FreeBlock->free_node);
    }
}
  • 由用户数据指针恢复到 PoolNode 头
  • 标记为 used=0
  • 向后查找第一个空闲或末尾节点
  • 将刚释放节点插入其前面，保持空闲链表顺序

删除内存池

1
2
3
4
5
6
void memPool_delete(PoolHeadHandle ThePool)
{
    if (ThePool) {
        free(ThePool);
    }
}

直接调用 free 释放底层整块内存