广告搜索技术-内存分配

内存分配器Allocator

内存分配器Allocator

db中内存的布局和存放结构已经大致清楚了，这时候需要抽象出来一个专门的分配器，来管理内存的分配，初始化和释放。所以为了管理内存抽象了一个内存分配器Allocator。

1. ::new操作

C++中需要动态分配堆上的内存需要使用new操作，但是这块内存具体分配到那个地址，是由编译器最后来决定的，这显然不符合新的db内存分配要求，因为我们将所有内存固定在了实际地址大小100GB的空间内。所以需要对实际的内存地址按实际地址来进行分配。很幸运C++中的new操作可以直接指定new在那块地址上，比如：

#include <iostream>

int main(void)
{
    int buf[10];
    void* p = ::new(buf) int(555);
    std::cout<< *((int*)p)<<std::endl;
    return 0;
}

新new出来的555这个变量就是直接在栈内存buf[10]的首地址开始分配内存的。

2. Allocator设计

zsearch的allocator内存分配器实现了对db中内存管理的封装。当前结构如下：

allocator

2.1 allocator基类

首先看一下allocator基类的实现。

class Allocator : public SupportErrorMsg {
 public:
  Allocator(): SupportErrorMsg(false) {
  }
  virtual ~Allocator() {
  }
  template<class _Tp>
  _Tp *New();               //无参数

  template<class _Tp>
  _Tp *New(size_t size);    //申请一个新对象，带大小参数

  template<class _Tp>
  _Tp *New(size_t size1, size_t size2);     //申请一个新对象，带大小参数

  template<class _Tp>
  void Delete(_Tp *ptr, bool delay = true); //销毁对象，带延迟释放

  virtual void *Malloc(size_t size, const char *file_name,const char *function, int32 line) = 0;   //动态申请内存，但未初始化
   // 带初始化的内存分配
  void *Calloc(size_t size, const char *file_name,const char *function, int32 line) {
    void *ptr = Malloc(size, file_name, function, line);
    if (ptr) memset(ptr, 0, size);
    return ptr;
  }
  // 内存释放
  virtual void Free(void *ptr, bool delay, const char *file_name,const char *function, int32 line) = 0;
  // 获取内存状态
  virtual void GetStatus(rapidjson::Value &value, rapidjson::Value::AllocatorType &allocator) = 0;
  virtual size_t GetUsedSize() = 0; //获取当前使用量
  virtual size_t GetCachedSize() = 0; //获取缓存大小
  virtual size_t GetAllSize() = 0; //获取DB总大小
  virtual size_t GetFreeSize() = 0; //获取空闲内存总大小
};

可以看出allocator基类中有一个New和Free的接口，同时预留了几个获取db状态的接口，给子类来实现。

2.2 FtAllocator

FtAllocator分配器是用来分配zsearch内存的分配器，我简略了部分函数，留下了主要的几个函数。

class FtAllocator : public Allocator {
 public:
  FtAllocator(DbMetadata *db_metadata);
 protected:
  void *DoAllocByPage(size_t size);                             //实现分配大于一个4KB的内存页
  void DoFreeByPage(void *ptr, size_t size, bool delay);        //释放一个页空间的内存
  void *DoAllocBySmallBox(size_t size);                         //实现分配一个小的块
  void DoFreeBySmallBox(void *ptr, size_t size, bool delay);    //释放一个小块的内存
  void *DoAllocByMiddleBox(size_t size);                        //实现分配一个中块内存
  void DoFreeByMiddleBox(void *ptr, size_t size, bool delay);   //释放一个中等块大小
  void *DoAllocByBox(FtBufList *list, size_t size);             //分配内存块
  bool FillBox(FtBufList *list, size_t size);                   //分配内存块
  void *AllocPage(int32 page_num);                              //分配一个新页
  void FreePage(void *ptr, int32 page_num);                     //释放一个新页
  void CheckDelayPageFree();                                    //check内存页是否可以释放
  void GetBoxStatus(rapidjson::Value &value, rapidjson::Value::AllocatorType &allocator,
                    FtBufList *box_list, int32 box_size,
                    int32 box_interval_size, int32 box_start_size);
  void *DoMalloc(size_t size, bool is_cal_used);                //分配内存接口函数
  void DoFree(void *ptr, bool delay, bool is_cal_used);         //释放内存接口函数
  void GetSmallStatus(rapidjson::Value &value, rapidjson::Value::AllocatorType &allocator);
  void GetMiddleStatus(rapidjson::Value &value, rapidjson::Value::AllocatorType &allocator);
  void GetPageStatus(rapidjson::Value &value, rapidjson::Value::AllocatorType &allocator);
 protected:
  DbMetadata *db_metadata_;
};

对于每个内存都存在一个头部，用来记录此次内存分配的大小：

/**
 * ft内存分配器保留结构
 */
struct FtReserveHead {
  int32 size;                                         // 内存地址实际大小
  int32 reserve;                                      // 保留
};

下面对整个内存的分配和回收流程做如下梳理：

new内存

首先判断需要分配的内存大小，此时的内存大小是加上头部后的总大小，然后调用不同的分配大小的函数来分配。
计算矫正需要分配的页数，比如要分配的是small的小内存，如果只分配90B的内存，那么该内存需要分配在round_div(90/8)*8 = 96的小块内存空间上，small小块的内存间隔为8字节。
从metadata中获取记录small块的数组，然后获取数组中记录96块的链表头指针。
```
FtBufList *list = &(db_metadata_->mem_info.ft_head.small_box_list[box_idx]);
```

此时开始检查链表中内存的状态，由于搜索框架中使用了rcu技术所以在内存的释放中就要延迟释放，所以此时就要对比一下此时内存的timeoffset是不是允许释放。

int32 time_diff = (Z_TIMESTAMP2OFFSET(::time(NULL))
list->head->timestamp_offset);
if ((db_metadata_->delay_free_sec > 0)
  && ((time_diff)
  < (db_metadata_->delay_free_sec / Z_TIMESTAMP2OFFSET_TIME_UNIT))) {
// 延迟时间不到，不允许再使用
if (!FillBox(list, size)) {
  return NULL;
}
}

如果该内存不能够释放则直接申请一个4KB大小的新page页然后计算出来当前4KB可以保证多少个整数块在内存内。同时将这些新的内存块push到链表下面。

内存释放

首先会获取到该内存指针的时候得到内存头部信息指针FtReserveHead*，该内存头里面存放了实际内存的长度size

void FtAllocator::DoFree(void *ptr, bool delay, bool is_cal_used) {
  if (CKIT_UNLIKELY(ptr == NULL)) {
    return;
  }
  //判断是否设置了延时释放秒数
  if (db_metadata_->delay_free_sec <= 0) {
    delay = false;
  }
  // 获取出实际位置信息 Z_FT_RESERVE_SIZE宏是内存头部size
  char *real_ptr = reinterpret_cast<char *>(ptr) - Z_FT_RESERVE_SIZE;
  FtReserveHead *reserve_head = reinterpret_cast<FtReserveHead *>(real_ptr);
  // 获取出实际大小
  size_t real_size = reserve_head->size;
  FtBufHead *buf_head = reinterpret_cast<FtBufHead *>(real_ptr);
  // 设置释放时间
  memset(buf_head, 0, sizeof(FtBufHead));
  buf_head->timestamp_offset = delay ? Z_TIMESTAMP2OFFSET(::time(NULL)) : 0;//是延时释放还是直接释放

  if (real_size > Z_FT_MIDDLE_BOX_MAX_SIZE) {
    DoFreeByPage(real_ptr, real_size, delay);               //释放页内存
  } else if (real_size > Z_FT_SMALL_BOX_MAX_SIZE) {
    DoFreeByMiddleBox(real_ptr, real_size, delay);          //释放中块
  } else {
    DoFreeBySmallBox(real_ptr, real_size, delay);           //释放小块
  }
  if (is_cal_used) {
    db_metadata_->mem_info.used_bytes -= real_size;
  }
}

其中内存小块的释放过程如下：

void FtAllocator::DoFreeBySmallBox(void *ptr, size_t size, bool delay) {
  FtBufHead *buf_head = reinterpret_cast<FtBufHead *>(ptr);
  int32 box_idx = Z_FT_GET_SMALL_BOX(size);
  FtBufList *list = &(db_metadata_->mem_info.ft_head.small_box_list[box_idx]);
  // 延时释放入链表尾部，直接释放入链表头部
  if (delay) {
    FtBufListPushBack(list, buf_head);
  } else {
    FtBufListPushHead(list, buf_head);
  }
}

在free内存的时候分两种情况，如果该内存有延迟释放，则会将会该节点内存放到整个链表的末尾tail节点，而当没有延迟释放的内存需要回收的时候直接将内存放在链表的head头结点，这样下次就会再次命中使用。

freemem

Page页的申请和释放

Page页的申请第一步首先检查是否有空闲的page可以释放掉。
检查db中内存是不是已经完全占用完了，占用玩的话会新建一个chunk块给新内存。

然后开始在内存中找连续的page页。

// 获取连续的页
for (; chunk->page_cursor <= db_metadata_->chunk_page_size - page_num;) {
  int32 m = 0;
  for (; m < page_num; m++) {
    //寻找是否满足连续为m个的内存页
    if (BITSET_CHECK(chunk->page_status, chunk->page_cursor + m) != 0) {
      break;
    }
  }
  if (m == page_num) {
    // 获取到对应的连续页信息，并设置页属性
    for (int32 m = 0; m < page_num; m++) {
      BITSET_SET(chunk->page_status, chunk->page_cursor + m);
    }
    chunk->free_page_num -= page_num;//可用page数减去page_num个
    void *ptr = Z_GET_CHUNK_PAGE_ADDR(db_metadata_, i, chunk->page_cursor);
    chunk->page_cursor += page_num; //设置新的page游标
    return ptr;
  } else {
    chunk->page_cursor += (m + 1);
  }
}

相对来讲申请页内存相对比较简单一些，只需要寻找连续内存页即可。

内存页的释放流程

void FtAllocator::FreePage(void *ptr, int32 page_num) {
  // 通过地址获取到chunk位置
  char *chunk_addr = Z_GET_CHUNK_START_ADDR(ptr);
  // 通过地址算出chunk的位置
  int32 chunk_no = (chunk_addr - (char *) Z_GET_CHUNK_ADDR(db_metadata_, 0))
  / Z_CHUNK_MAX_SPACE_SIZE;
  Chunk *chunk = &(db_metadata_->chunk[chunk_no]);
  // 通过地址获取page_num;
  int32 page_start_no =
  (((char *) ptr - (char *) Z_GET_CHUNK_PAGE_ADDR(db_metadata_, chunk_no, 0))
      / Z_PAGE_SIZE);
  // 找到起始页，开始设置对页的应状态为未使用
  for (int32 m = 0; m < page_num; m++) {
BITSET_CLEAR(chunk->page_status, page_start_no + m);
  }
  chunk->free_page_num += page_num;
}

内存页的释放比较简单，只需要定位chunk的位置，然后对相应的bitset数组置0就行了。

总结

内存的申请和回收是相对比较复杂的，对整个内存的回收（当然这里面回收也只是部分回收小块和中块中用完的块无法回收）的细节需要仔细的分析，这篇文章主要对底层实现内存分配和释放做了一点分析。