实现分配固定大小内存池-C++

内存池简述

内存池（Memory Pool），又被称为固定大小区块规划（fixed-size-blocks allocation），允许程序员以类似 C语言 的 malloc 或是 C++ 的 new 操作数进行动态的存储器规划。对于其它动态存储器规划的实践来说，因为会变动存储器区块大小导致的碎片问题，导致在实时系统上受限于性能因此，根本无法使用。内存池提供了一个更有效率的解决方案：预先规划一定数量的存储器区块，使得整个程序可以在执行期规划 (allocate)、使用 (access)、归还 (free) 存储器区块。 ——维基百科

实现设计

编写一个MyMemoryPool类作为内存池，MyMemoryPool类参照 C++ 标准库中的 std::allocator 设计。核心是维护两条链表：内存块表 (open_list)、分配后被释放而产生的重分配链表 (free_memory)。

内存块表设计如图

内存块表

一次性申请一大块内存，然后在头部开辟表头，用以储存之前的内存头地址。剩余部分划分为多个固定大小的区块，将成为真正的内存分配区域。

重分配链表 (free_memory) 构成如图

重分配链表

重分配链表不含表头区域，完全是由待分配的内存构成。

内存分配步骤为： 1. 检查重分配链表 (free_memory) 是否有内存 2. 若有直接分配重分配链表的内存，若无准备分配内存块表的内存 3. 检查内存块表的空闲空间是否足够分配所需内存 4. 若空闲空间不足，申请新的内存块表；否则直接分配内存块表的内存

具体实现

基础建设

根据 allocator 的要求，我的目标是完成 C++11 的部分标准且我的类名为 MyMemoryPool。因此首先实现几个别名。

1
2
3
4
5
6
using value_type = T;
using potinter = T *;
using const_pointer = const T *;
using reference = T &;
using const_reference = const T &;
using size_type = size_t;

由于标准没有对构造函数进行具体要求，我直接使用默认构造函数。

1
2
3
4
MyMemoryPool() {}
MyMemoryPool(const MyMemoryPool &other) {}
template <typename U>
MyMemoryPool(const MyMemoryPool<U> &other) {}

rebind 是为了应对类似 std::list 的容器，这类容器在往往要求分配的是一个结构而不是储存的类型，比如 std::list<int,std::allocator<int>> 会在内部将 std::allocator<int> 改为 std::allocator<node<int>> 而 node 对调用 list 的人是不可见的，因此 allocator 需要提供 rebind 使 list 能自行更改指定的分配器。

1
template <typename U> struct rebind { typedef MyMemoryPool<U> other; };

下面将是 private 部分，即我自己的实现细节。首先为方便理解变量的具体含义，定义几个类型别名、结构、指针。

1
2
3
4
5
6
7
8
9
10
11
12
13
static constexpr size_t block_size = 1024lu;
struct Node {
  T *data;
  Node *next;
};
typedef Node *block_pointer;
typedef Node *memory_pointer;
typedef T *data_pointer;
typedef char *byte_pointer;
block_pointer open_list;
memory_pointer current;
memory_pointer free_memory;
memory_pointer end;

block_size是每次申请的内存块大小，Node用于充当内存块头和空闲内存分配区，block_pointer指向当前正在分配的内存块头，current指向即将分配的空闲内存块，free_memory是释放后产生的空闲内存，end为当前内存块表的最后一个内存地址

分配器

根据 成员函数 allocate 的要求，我原本应该实现一个可以一次分配多个内存块且根据 hint 指针进行调整的分配器，但为简化实现，我的分配器每次只分配一个内存区块且忽略 hint 指针。

1
2
3
4
5
6
7
8
9
10
data_pointer allocate(size_t n, const data_pointer hint = nullptr) {
  if (free_memory != nullptr) {
    memory_pointer target = free_memory;
    free_memory = free_memory->next;
    return reinterpret_cast<data_pointer>(target);
  }
  if (current >= end)
    new_block();
  return reinterpret_cast<data_pointer>(current++);
}

首先判断是否有释放后产生的空闲内存，有优先使用它，否则分配内存块表中的空闲内存。检查内存块表是否有剩余空间，若无申请新的内存块表，最后将指向空闲内存的current强制转换为数据指针后返回（后自增）。

申请新的内存块表

调用operator new从系统中获得一块固定大小的内存。由于char占用 1 字节，因此char*即指向 char 类型的指针是一字节一字节的操作，将其当作直接操作内存字节的指针而不是真的需要操作字符。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
size_t padPointer(byte_pointer p, size_t align) const {
 uintptr_t result = reinterpret_cast<uintptr_t>(p);
 return ((align - result) % align);
}

void new_block() {
 byte_pointer target = static_cast<byte_pointer>(::operator new(block_size));
 reinterpret_cast<block_pointer>(target)->next = open_list;
 open_list = reinterpret_cast<block_pointer>(target);
 byte_pointer body = target + sizeof(block_pointer);
 size_t bodyPadding = padPointer(body, alignof(Node));
 current = reinterpret_cast<memory_pointer>(body + bodyPadding);
 end = reinterpret_cast<memory_pointer>(target + block_size -sizeof(Node) + 1);
}

target指向新申请的连续空闲内存，同时在头部生成一个Node结构充当内存块头，并将 next 指向旧内存块。body指向内存块头 (Node) 的末尾，padPointer 函数的存在是因为“内存对齐”的要求。

内存对齐是一个基础却复杂的概念，简单来说“数据项仅仅能存储在地址是数据项大小的整数倍的内存位置上”。alignof 能够返回查询类型的对齐要求，padPointer 则返回 p 与对齐地址的距离。也许你更常看见

1
(reinterpret_cast<uintptr_t>(x) + static_cast<size_t>(7u)) & ~static_cast<size_t>(7u);

即返回将 x 转化为 unsigned long int 后的 8 的倍数。这也是进行内存对齐。

释放元素

1
2
3
4
5
void deallocate(data_pointer p, size_t n = 1) {
 if (p != nullptr) {
   reinterpret_cast<memory_pointer>(p)->next = free_memory;
   free_memory = reinterpret_cast<memory_pointer>(p);
 }

将 p 加入 free_memory 并忽略参数 n。

完整实现

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
#ifndef MY_MEMORYPOOL
#define MY_MEMORYPOOL

#include <cstddef>
#include <cstdint>
#include <memory>
#include <new>

template <typename T> class MyMemoryPool {
private:
  static constexpr size_t block_size = 1024lu;
  struct Node {
    T *data;
    Node *next;
  };
  typedef Node *block_pointer;
  typedef Node *memory_pointer;
  typedef T *data_pointer;
  typedef char *byte_pointer;
  block_pointer open_list;
  memory_pointer current;
  memory_pointer free_memory;
  memory_pointer end;

  size_t padPointer(byte_pointer p, size_t align) const {
    uintptr_t result = reinterpret_cast<uintptr_t>(p);
    return ((align - result) % align);
  }

  void new_block() {
    byte_pointer target = static_cast<byte_pointer>(::operator new(block_size));
    reinterpret_cast<block_pointer>(target)->next = open_list;
    open_list = reinterpret_cast<block_pointer>(target);
    byte_pointer body = target + sizeof(block_pointer);
    size_t bodyPadding = padPointer(body, alignof(Node));
    current = reinterpret_cast<memory_pointer>(body + bodyPadding);
    end = reinterpret_cast<memory_pointer>(target + block_size -
                                           sizeof(Node) + 1);
  }

public:
  MyMemoryPool()
      : open_list(nullptr), current(nullptr), free_memory(nullptr), end(nullptr) {}
  data_pointer allocate(size_t n, const data_pointer hint = nullptr) {
    if (free_memory != nullptr) {
      memory_pointer target = free_memory;
      free_memory = free_memory->next;
      return reinterpret_cast<data_pointer>(target);
    }
    if (current >= end)
      new_block();
    return reinterpret_cast<data_pointer>(current++);
  }
  void deallocate(data_pointer p, size_t n = 1) {
    if (p != nullptr) {
      reinterpret_cast<memory_pointer>(p)->next = free_memory;
      free_memory = reinterpret_cast<memory_pointer>(p);
    }
  }
  template <typename U> struct rebind { typedef MyMemoryPool<U> other; };
};

#endif

参考

  1. https://github.com/cacay/MemoryPool
  2. https://zhuanlan.zhihu.com/p/280706845
  3. https://www.cnblogs.com/wgwyanfs/p/6733609.html
  4. https://zh.cppreference.com/w/cpp/language/alignof
  5. https://en.cppreference.com/w/cpp/memory/allocator
  6. https://stackoverflow.com/questions/1845482/what-is-uintptr-t-data-type
  7. https://www.zhihu.com/question/25527491/answer/56571062
#工程
实现分配固定大小内存池-C++
https://blog.hydrogenroom.icu/post/e678ff2a.html
作者
Hydrogen
发布于
2022年9月25日
许可协议