ACool & Blog

前言

最近在看Boost库相关的内容，之前的关注点一直在STL上面，后面听大佬讲了架构以后，我意识到了内存管理的重要性。在C++大型项目中，人们一般采用内存池技术对对象进行管理，可以很好地避免内存泄露问题，并且程序具有较高的健壮性。故此我对Boost源码里面内存池（singleton_pool）的实现进行了深入的探索。

接口定义

Singleton_pool类允许其他类型大小相同的池接口共享同一个池。

The singleton_pool class allows other pool interfaces for types of the same size to share the same pool.

首先我们先来看看源码主要部分：

//Distributed under the Boost Software License, Version 1.0.
//boost/pool/singleton_pool.hpp
template <typename Tag,
    unsigned RequestedSize,
    typename UserAllocator,
    typename Mutex,
    unsigned NextSize,
    unsigned MaxSize >
class singleton_pool{
public:
    static void * malloc();
    static void * ordered_malloc();
    static void * ordered_malloc(const size_type);
    static bool is_from(void *const);
    static void free(void *const);
    static void ordered_free(void *const);
    static void free(void *const, const size_type);
    static void ordered_free(void *const, const size_type);
    static bool release_memory();
    static bool purge_memory();
 }

模板参数如下：

Tag：指定对象类型，用于区分不同的对象池

RequestedSize：每次分配时请求的内存池中每个chunk的大小

UserAllocator：用户可自定义的内存分配器，默认为 default_user_allocator_new_delete

Mutex：此类是用于保护对基础池的同时访问的互斥锁类型。可以是任何Boost。比如Thread Mutex类型或 boost::details::pool::null_mutex，默认值为后者

NextSize：指定内存池在第一次申请内存时分配的块数，默认为32

MaxSize：指定单次分配的块数的最大值，默认为0，表示无上限

数据结构

内存池中有两个重要对象，分别是Block和Chunk。

Block为一大块内存，由多块Chunk组成。Block和Chunk的结构如下：

Block结构

其中 next_ptr 指向下一个 Block，next_size 为下个 Block 的大小。第一次申请内存时，由于没有可用 Block，内存池会向操作系统申请第一个 Block，如果采取默认的便包含32个 Chunk，当第一次申请的 Block 用完以后，第二次申请的 Block 会包含64个 Chunk（为前一次的两倍），以此类推，如果指定了MaxSize，则最多能申请 Maxsize 数量的 Chunk。

Block由 simple_segregated_storage 分割成 Chunk，每个 Chunk 指向相邻的下一个 Chunk，最后一个指向 NULL 或者下一个 Block 的第一个Chunk。最前面有一个 First 指针指向 Chunk1 。

分配内存接口

分配内存的几种接口如下：

static void * malloc();
static void * ordered_malloc();
static void * ordered_malloc(const size_type);

这几种接口的区别在于：

malloc()：返回第一个可用的Chunk，时间复杂度为O(1)

ordered_malloc：分配内存时候会保持 Block 和 Chunk 的顺序，时间复杂度为O(n)，对于分配连续 n 个 Chunk 的时候很有用

我们可以跟踪源码检验其内存分配策略是否如我们所说。以malloc()举例。

1.首先找到malloc接口的声明：

//boost/pool/singleton_pool.hpp
static void * malloc BOOST_PREVENT_MACRO_SUBSTITUTION()
{
  pool_type & p = singleton::instance();
  details::pool::guard<Mutex> g(p);
  return (p.p.malloc)();
}

2.进入(p.p.malloc)()查看下一层的声明：

//boost/pool/pool.hpp
void * malloc BOOST_PREVENT_MACRO_SUBSTITUTION()
    {
      // Look for a non-empty storage
      if (!store().empty())
        return (store().malloc)();
      return malloc_need_resize();//可以看出采取了"不够再分配"的策略
    }

3.再进入store().malloc()的声明：

//boost/pool/simple_segregated_storage.hpp
static void * & nextof(void * const ptr)
 { return *(static_cast<void **>(ptr)); }//强转成指向指针的指针来定位下一个chunk块
void * malloc BOOST_PREVENT_MACRO_SUBSTITUTION()
    {
      void * const ret = first;

      // 我们可以看到这里将first指针指向了下一个chunk块
      first = nextof(first);
      return ret;
    }

4.最后看看不够再分配策略的malloc_need_resize()代码：

template <typename UserAllocator>
void * pool<UserAllocator>::malloc_need_resize()
{
  // No memory in any of our storages; make a new storage,
  const size_type partition_size = alloc_size();
  const size_type POD_size = next_size * partition_size +
      details::pool::ct_lcm<sizeof(size_type), sizeof(void *)>::value + sizeof(size_type);
  char * const ptr = (UserAllocator::malloc)(POD_size);
  if (ptr == 0)
    return 0;
  const details::PODptr<size_type> node(ptr, POD_size);

  BOOST_USING_STD_MIN();
  if(!max_size)
    next_size <<= 1;//下一次分配为本次的两倍
  else if( next_size*partition_size/requested_size < max_size)
    next_size = min BOOST_PREVENT_MACRO_SUBSTITUTION(next_size << 1, max_size*requested_size/ partition_size);

  //  initialize it,
  store().add_block(node.begin(), node.element_size(), partition_size);

  //  insert it into the list,
  node.next(list);
  list = node;

  //  and return a chunk from it.
  return (store().malloc)();
}

通过对以上源码的研究，我们可以更好地理解内存分配的详细操作。

归还内存接口

归还内存的几种接口如下：

static void free(void *const);
static void ordered_free(void *const);
static void free(void *const, const size_type);
static void ordered_free(void *const, const size_type);

同分配内存时候的差别相似，这几种接口的区别在于：

free：将First直接指向归还的Chunk，时间复杂度为O(1)

ordered_free：在归还内存的时候会保持Chunk在链表中的顺序，时间复杂度为O(n)，可以返回连续的Chunk

清理内存

清理内存的接口如下：

static bool release_memory();
static bool purge_memory();

purge_memory：对所有Block无条件释放，即使有些Chunk正在使用

release_memory：只对ordered内存池有用

使用示例

Singleton_pool的使用方法如下：

class TestPool{};
typedef boost::singleton_pool<TestPool,2048> NewPool;
int main()
{
  char* p=(char*)NewPool::malloc();//每个Chunk大小为2K
  NewPool::free(p);
  return 0;
}

结语

在实际项目中，我们常用malloc和free，缺点在于管理的内存为非连续的，所以无法手动回收。ordered 内存池虽然可以手动回收，但是操作效率不高，不常使用。

其实这一块还有很多内容值得提，但是由于时间仓促，只能点到为止，研究的方法其实就是类似于 分配内存接口 这一段对源码的跟踪，如果在Windows下面，推荐使用 Source Insight 进行代码查看。