boost内存池的实现

很多网络库都会用到内存池来管理一些经常创建和释放的内存,比如TCP连接,网络包等。现在的项目用boost的内存池来管理对象,这篇文章主要分析了一下boost::pool是如何进行内存管理的。

simple_segregated_storage内存管理

boost内存池底层采用一种叫做simple_segregated_storage的类来管理内存,是boost::pool、boost::object_pool等内存池的基础。

基本思想

simple_segregate_storage的设计思想与stl中内存allocator的思想基本一致,采用采用单链表来管理空闲内存,单链表的实现比较巧妙,是高效分配和释放内存的基础。

simple_segregated_storage中连续的内存叫做block,每个固定大小的内存块叫做chunk。上图中simple_segreate_storage管理5个内存块(chunk),每个内存块16个字节。simple_segregate_storage有一个first成员指向free_chunk_list的首部,每个free_chunk的首部存储下一个free_chunk的地址。

  • 分配chunk:返回first,并将first指向first->next
  • 回收chunk: 将chunk->next指向first, first=chunk

另外,simple_segrate_storage支持按顺序释放,比如先释放0x100后释放0x110,直接free时first会指向0x110,而ordered_free时first仍会指向0x100。按序释放可以实现按照链表顺序查找时,能够找到内存连续的free_chunk。

非按序的分配和释放内存时间复杂度都是O(1),但按序释放内存需要遍历free_list因此时间复杂度为O(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
// 将block指向的大小为sz的内存,切分成partition_sz大小的内存,
// 链入free_list,最后一个chunk指向end,返回第一个chunk的指针
void * simple_segregated_storage<SizeType>::segregate(
void * const block,
const size_type sz,
const size_type partition_sz,
void * const end);
// 申请一块free chunk
void * malloc BOOST_PREVENT_MACRO_SUBSTITUTION();
// 释放chunk到free_list
void free BOOST_PREVENT_MACRO_SUBSTITUTION(void * const chunk);
// 分配n个partition_size大小的chunk
// n个chunk内存连续
void * malloc_n(size_type n, size_type partition_size);
// 释放n个chunk,非按序释放
void free_n(void * const chunks, const size_type n,
const size_type partition_size);
// 按序释放n个chunk
void ordered_free_n(void * const chunks, const size_type n,
const size_type partition_size)

boost::pool内存池

内存管理的实现

boost::pool是boost提供的基本定长内存池,继承自simple_segregated_storage,在simple_segregated_storage的基础上,将连续的内存块block封装成PODptr, 通过链表对内存块PODptr进行管理,基本结构见下图。


boost::pool对象中包含一个PODPtr的list, 每个PODptr由三部分组成,最前面的Element是simple_segregated_storage中的block,即应用需要的内存。后面两个字段第一个字段指向的是下一个PODPtr,第二个字段下一个是PODptr的大小。

  • 内存申请
    • 如果simple_segregated_storage中仍有可用内存,直接返回first指向的chunk.
    • 如果simple_segregated_storage没有可用内存了,申请一块指定长度的大内存,调用segregate函数,返回可用内存。
  • 内存释放
    • 直接调用simple_segregated_storage的free方法。

内存对齐

在申请新的block后,需要访问NextPODPtr和NextPODSize,因此NextPODPtr和NextPODsize需要对齐在对应的内存上。NextPODPtr为void*类型,NextPODsize为size_type,最小的对齐的字节为两个类型对齐大小的最小公倍数。

1
min_align = lcm(align_of(void*), align_of(size_type));

每个chunk最小分配的内存大于partition_size和lcm(sizeof(void*), sizeof(size_type)),然后取模对齐在min_algin上。
关于内存对齐更加深入的解释可以参考boost文档

接口

Boost::pool的接口与simple_segregated的接口比较接近,提供了malloc、ordered_malloc、free、ordered_free等接口这里不再赘述。

boost::object_pool内存池

boost的object_pool在boost::pool的基础上又做了一层封装,提供对对象自动自动构造和析构的功能,类似智能指针,避免了内存泄漏的问题。object_pool为了能够在析构时达到O(N)的复杂度,所有调用都使用ordered_malloc和ordered_free.因此object_pool分配和释放内存的复杂度均为O(N)。

boost内存池的几点思考

  • 为什么要有ordered_malloc和ordered_free?

    An ordered pool maintains it’s free list in order of the address of each free block - this is the most efficient way if you’re likely to allocate arrays of objects. However, freeing an object can be O(N) in the number of currently free blocks which can be prohibitively expensive in some situations.

    An unordered pool does not maintain it’s free list in any particular order, as a result allocation and freeing single objects is very fast, but allocating arrays may be slow (and in particular the pool may not be aware that it contains enough free memory for the allocation request, and unnecessarily allocate more memory).

也就是说,按序分配和释放主要保证了在分配连续内存时有较高的成功率,同时在析构object_pool时能够实现O(N)的复杂度。

  • 何时使用object_pool?

我个人的观点是尽量不要使用object_pool,除非你对自己的行为带来的后果由明确的了解。因为自动释放内存可以通过shared_ptr等智能指针来完成,而仅仅因为这一点好处将内存分配和释放的复杂度由O(1)提高的O(N)有些得不偿失。

  • 可以不依赖boost么?

boost项目的相互依赖比较严重,其实从boost::pool的源码来看,内存池的实现还算比较独立,我想精简一个版本只保留boost::pool并且去掉按序分配和释放的功能。基本做好了,还要测试一下。全部完成以后会更新上来。