leveldb Arena 分析

版權聲明：本文為 cheng-zhi 原創(chuàng)文章儿倒，可以隨意轉載，但必須在明確位置注明出處斗锭！

Arena

Arena 是 leveldb 項目里面使用的輕量級的內(nèi)存池對象枣购，leveldb 用這個對象來管理內(nèi)存的分配，簡化了 new 和 delete 的調(diào)用颠放，我們也可以從這個輕量級的內(nèi)存池對象學習 google 大神工程師是如何管理內(nèi)存的。

Arena 內(nèi)存管理模型

這是羅道文網(wǎng)站上關于 leveldb 的一張 Arena 的內(nèi)存模型圖:

Arena 使用下面幾個成員變量來描述上面的模型圖

// 當前內(nèi)存塊未分配內(nèi)存的起始地址
char* alloc_ptr_;

// 當前內(nèi)存塊剩余的內(nèi)存
size_t alloc_bytes_remaining_;

// Arena 使用 vector 來存儲每個內(nèi)存塊的地址
std::vector<char*> blocks_;

// 當前 Arena 已經(jīng)分配的總內(nèi)存量 
port::AtomicPointer memory_usage_;

在開始分析之前你需要了解申請內(nèi)存和分配內(nèi)存的區(qū)別：

1. 申請內(nèi)存：使用 new 來向操作系統(tǒng)申請一塊連續(xù)的內(nèi)存區(qū)域吭敢。
2. 分配內(nèi)存：將已經(jīng)申請的內(nèi)存分配給項目組件使用碰凶，這體現(xiàn)在增加 alloc_ptr_ 和減少 alloc_bytes_remaining_ 這兩個指針上。

為什么要強調(diào)這兩個概念呢鹿驼？

因為 Arena 是一個內(nèi)存池欲低，他的功能就是內(nèi)存的管理，包括申請內(nèi)存蠢沿，分配內(nèi)存伸头，釋放內(nèi)存。

Arena 的構造和析構

Arena 的源碼位置：/leveldb/util/arena.h, /leveldb/util/arena.cc

// 良好的初始化風格
Arena::Arena() : memory_usage_(0) {
  alloc_ptr_ = NULL;  
  alloc_bytes_remaining_ = 0;
}

Arena::~Arena() {
  // 分別釋放 vector 中每個指針指向的內(nèi)存塊
  for (size_t i = 0; i < blocks_.size(); i++) {
    delete[] blocks_[i];
  }
}

Arena 提供的接口函數(shù)

Arena 給我們提供了 3 個 public 函數(shù)來簡化我們的內(nèi)存訪問

public:
  // 基本的內(nèi)存分配函數(shù)
  char* Allocate(size_t bytes);

  // 按照字節(jié)對齊來分配內(nèi)存
  char* AllocateAligned(size_t bytes);

  // 返回目前分配的總的內(nèi)存
  size_t MemoryUsage() const;

下面一一分析

Allocate

這是一個最重要的內(nèi)存分配函數(shù)舷蟀，這個函數(shù)會根據(jù)你要申請的內(nèi)存大小來調(diào)用另外兩個私有的內(nèi)存分配函數(shù)

inline char* Arena::Allocate(size_t bytes) {
  // 不需要分配 0 字節(jié)的內(nèi)存
  assert(bytes > 0);

  // 申請的內(nèi)存小于剩余的內(nèi)存，就直接在當前內(nèi)存塊上分配內(nèi)存
  if (bytes <= alloc_bytes_remaining_) {
    char* result = alloc_ptr_;
    alloc_ptr_ += bytes;
    alloc_bytes_remaining_ -= bytes;
    return result;
  }

  // 申請的內(nèi)存的大于當前內(nèi)存塊剩余的內(nèi)存，就用這個函數(shù)來重新申請內(nèi)存
  return AllocateFallback(bytes);
}

AllocateFallback

在申請的內(nèi)存大于當前塊剩余內(nèi)存時野宜，AllocateFallback會被調(diào)用扫步，它提供 2 種申請內(nèi)存的策略：

1. 當前塊剩余內(nèi)存 < 申請的內(nèi)存 < 默認內(nèi)存塊大小的 1 / 4 (1096 KB / 4 = 1024 KB)，重新申請一個默認大小的內(nèi)存塊 (4096 KB)匈子。
2. 申請的內(nèi)存大于當前塊剩余內(nèi)存河胎，并且大于默認內(nèi)存塊大小的 1 / 4，直接申請一個需要的的 bytes 大小的內(nèi)存塊虎敦。

第二種分配方法的理由是可以減少內(nèi)存分配的次數(shù)游岳，分析如下：

假如我當前塊剩余 900 KB 內(nèi)存，而我需要申請 1200 KB 內(nèi)存其徙，如果我直接申請一塊大小為 1200 KB 的內(nèi)存塊胚迫，就只需要申請一次；但是如果我在當前塊先分配 900 KB 內(nèi)存唾那，然后再申請一個新的 4096 KB 的內(nèi)存塊访锻，再在里面分配 1200 - 900 = 300 KB 的內(nèi)存，這樣就需要申請 1 次內(nèi)存闹获，分配兩次內(nèi)存期犬，效率低下了不少(在分配比較頻繁的時候)，因此這樣直接申請并分配一個 bytes 大小的內(nèi)存塊非常高效方便避诽。

// bytes 代表實際要申請的內(nèi)存大小
char* Arena::AllocateFallback(size_t bytes) {
  // kBlockSize = 4096 KB
  // bytes > 1 / 4 (1024 KB)龟虎，調(diào)用 AllocateNewBlock 申請一塊新的大小為 bytes 的內(nèi)存
  if (bytes > kBlockSize / 4) {
    char* result = AllocateNewBlock(bytes);
    return result;
  }

  // bytes < 1 / 4 (1024 KB)，申請一個默認大小為 4096 KB 的內(nèi)存塊
  alloc_ptr_ = AllocateNewBlock(kBlockSize);
  alloc_bytes_remaining_ = kBlockSize;

  // 在申請的默認大小的內(nèi)存塊里分配 bytes 字節(jié)內(nèi)存
  char* result = alloc_ptr_;
  alloc_ptr_ += bytes;
  alloc_bytes_remaining_ -= bytes;
  return result;
}

AllocateNewBlock

這是 AllocateNewBlock 的實現(xiàn)沙庐，它就是簡單的申請了一個 block_bytes 大小的內(nèi)存塊

char* Arena::AllocateNewBlock(size_t block_bytes) {
  // 申請一個 block_bytes 大小的內(nèi)存塊
  char* result = new char[block_bytes];
  
  // 向 vector 中添加這個內(nèi)存塊的地址
  blocks_.push_back(result);

  // 增加當前內(nèi)存分配的總量
  memory_usage_.NoBarrier_Store(
      reinterpret_cast<void*>(MemoryUsage() + block_bytes + sizeof(char*)));
  return result;
}

AllocateAligned

這個函數(shù)可以分配字節(jié)對齊的內(nèi)存遣总，實現(xiàn)稍微有些復雜，不過仔細分析還是有很多營養(yǎng)的轨功，注釋很詳細

char* Arena::AllocateAligned(size_t bytes) {
  // 設置要對齊的字節(jié)數(shù)旭斥，最多 8 字節(jié)對齊，否則就按照當前機器的 void* 的大小來對齊
  const int align = (sizeof(void*) > 8) ? sizeof(void*) : 8;

  // 字節(jié)對齊必須是 2 的次冪, 例如 align = 8
  // 8 & (8 - 1) = 1000 & 0111 = 0, 表示 8 是字節(jié)對齊的
  assert((align & (align-1)) == 0);   
  
  // 了解一個公式：A & (B - 1) = A % B
  // 所以古涧，這句話的意思是將 alloc_ptr_ % align 的值強制轉換成 uintptr_t 類型
  // 這個 uintptr_t 類型代表了當前機器的指針大小
  size_t current_mod = reinterpret_cast<uintptr_t>(alloc_ptr_) & (align-1);
  
  // 如果上面的代碼返回 0 代表當前 alloc_ptr_ 已經(jīng)是字節(jié)對齊了
  // 否則就計算出對齊的偏差
  // 例如 current_mod = 2, 則還需要 8 - 2 = 6 個字節(jié)才能使得 alloc_ptr 按照 8 字節(jié)對齊
  size_t slop = (current_mod == 0 ? 0 : align - current_mod);

  // 分配的字節(jié)數(shù)加上對齊偏差就是最后需要分配的內(nèi)存字節(jié)總量
  size_t needed = bytes + slop;
  char* result;

  // 當總量小于當前內(nèi)存塊的剩余大小垂券，就直接在當前內(nèi)存塊分配 needed 大小的內(nèi)存
  if (needed <= alloc_bytes_remaining_) {
    result = alloc_ptr_ + slop;
    alloc_ptr_ += needed;
    alloc_bytes_remaining_ -= needed;
  } else {
    // 否則就按照這個函數(shù)的內(nèi)存分配策略來申請內(nèi)存，見上面的分析
    result = AllocateFallback(bytes);
  }
  assert((reinterpret_cast<uintptr_t>(result) & (align-1)) == 0);
  return result;
}

總結

總的來說羡滑，Arena 有 3 種內(nèi)存分配策略菇爪，下面申請的內(nèi)存用 bytes 表示：

1. bytes < 當前塊剩余內(nèi)存 => 直接在當前塊分配。
2. 當前塊剩余內(nèi)存 < bytes < 1024 KB (默認內(nèi)存塊大小的 1 / 4) => 直接申請一個默認大小為 4096 KB 的內(nèi)存塊柒昏，然后分配內(nèi)存凳宙。
3. bytes > 當前塊剩余內(nèi)存 && bytes > 1024 KB => 直接申請一個新的大小為 bytes 的內(nèi)存塊，并分配內(nèi)存职祷。

Arena 是一個內(nèi)存池對象氏涩，用來管理 leveldb 的內(nèi)存分配届囚，可以說是整個項目非常重要的模塊了，不可不知 ~

試著了解開源項目的內(nèi)存分配策略

原文地址