leveldb - slice status arena


接下来是util目录,这个目录里面都是一些工具,包括内存管理,cache,hash,随机数,过滤器什么的。先看了几个简单的。

slice

虽然slice.h没在util目录下,但是在看status的时候遇到了,发现这个头文件的功能很简单,所以就在这里说一说。

leveldb/include/leveldb/slice.h这个头文件提供了一个指针指向外部的数据,以及一个size成员用来记录数据的大小。要注意的是必须保证在使用这个指针时,指针指向的外部数据没有被销毁类似于避免__use after free__,另外这个指针指向的数据可以包含\0

同时,在这个头文件中还提供了Slice之间的比较操作。

status

leveldb 尝鲜里面就用到了leveldb::Status

leveldb/include/leveldb/status.h这个头文件里声明了Status类,这个类里面通过5个静态公有成员函数来构造对应的status(私有变量state_),同时提供了5个bool型返回值的函数用于判断当前是什么状态。

用于构造status结构的是一个私有成员函数Status(Code code, const Slice& msg, const Slice& msg2),其中Code是一个枚举

enum Code {
    kOk = 0,
    kNotFound = 1,
    kCorruption = 2,
    kNotSupported = 3,
    kInvalidArgument = 4,
    kIOError = 5
  };

Status成员函数要构造的状态(state_)具有如下结构

const char* state_;
state_[0..3] ==> 状态信息的长度
state_[4]    ==> code (枚举值)
state_[5..]  ==> 状态信息

leveldb/util/status.cc里面只有两个私有成员函数的实现以及一个将状态信息转换为std::string返回的公有成员的实现,这个实现非常简单所以忽略掉,下面来看看两个私有成员函数的实现。

  • 一个是复制状态
const char* Status::CopyState(const char* state) {
  uint32_t size;
  memcpy(&size, state, sizeof(size));
  char* result = new char[size + 5];
  memcpy(result, state, size + 5);
  return result;
}

不好的地方,size没有初始化(默认初始化为0)!
为了帮助理解这段代码,看下面的例子

#include <iostream>
#include <cstring>

int main()
{
  uint32_t size = 0;
  char state[15] = {0};
  uint32_t len = 10;
  char code = 1;
  memcpy(state, &len, sizeof(len));
  state[4] = code;
  memcpy(state+5, "this is ok", 10);
  std::cout << "state = " << state+5 << std::endl;
  memcpy(&size, state, sizeof(size));
  std::cout << "size = " << size << std::endl;
  char *result = new char[size + 5];
  memcpy(result, state, size + 5);
  std::cout << "result = " << result+5 << std::endl;
}

这段代码会输出

state = this is ok
size = 10
result = this is ok

由于Status::CopyState只接受一个参数,没有包含state的长度,所以作者通过这种方式来实现状态的拷贝!第一次看到这种方式,感觉很神奇的样子!

  • 一个是构造状态
Status::Status(Code code, const Slice& msg, const Slice& msg2) {
  assert(code != kOk);
  const uint32_t len1 = msg.size();
  const uint32_t len2 = msg2.size();
  const uint32_t size = len1 + (len2 ? (2 + len2) : 0); // 总长度
  char* result = new char[size + 5]; // 总长度 + 长度记录4 + code1
  memcpy(result, &size, sizeof(size)); // 复制信息长度记录4
  result[4] = static_cast<char>(code); // 赋值code1
  memcpy(result + 5, msg.data(), len1); // 复制msg1内容
  if (len2) {
  // 如果msg2不为空,那么最后看起来向这样
  // [[长][度][记][录][code][msg.data()][:][ ][msg2.data()]]
    result[5 + len1] = ':';
    result[6 + len1] = ' ';
    memcpy(result + 7 + len1, msg2.data(), len2);
  }
  state_ = result;
}

arena .h .cc

arena是leveldb自己的一个简单的内存管理。类声明如下

static const int kBlockSize = 4096;
class Arena {
 public:
  Arena();
  ~Arena();

  // Return a pointer to a newly allocated memory block of "bytes" bytes.
  char* Allocate(size_t bytes);

  // Allocate memory with the normal alignment guarantees provided by malloc
  char* AllocateAligned(size_t bytes);

  // Returns an estimate of the total memory usage of data allocated
  // by the arena.
  size_t MemoryUsage() const {
    return reinterpret_cast<uintptr_t>(memory_usage_.NoBarrier_Load());
  }

 private:
  char* AllocateFallback(size_t bytes);
  char* AllocateNewBlock(size_t block_bytes);

  // Allocation state
  char* alloc_ptr_;
  size_t alloc_bytes_remaining_;

  // Array of new[] allocated memory blocks
  std::vector<char*> blocks_;

  // Total memory usage of the arena.
  port::AtomicPointer memory_usage_;

  // No copying allowed
  Arena(const Arena&);
  void operator=(const Arena&);
};

其中私有变量

  • char *alloc_ptr_指向new返回的内存块
  • size_t alloc_bytes_remaining_指示这个返回的内存块还有多少可用
  • std::vector<char*> blocks_用来存放这些new返回的内存块,在析构函数中统一释放
  • port::AtomicPointer memory_usage_用于表示class Arena已使用的内存量。(这个变量完全可以用size_t memory_usage_代替,可能考虑到多线程的情况,作者使用了自己实现的AtomicPointer)

Class Arena的策略是

  • 如果传入的bytes小于默认的kBlockSize就直接分配kBlockSize的内存
  • 下一次传入的bytes小于等于第一次使用后的alloc_bytes_remaining_就继续使用上一次的分配的那块内存,并且alloc_bytes_remaining_ -= bytes以及alloc_ptr += bytes
  • 下一次传入的bytes如果大于alloc_bytes_remaining_并且大于kBlockSize的四分之一,那么就直接向系统申请bytes大小的内存
  • 下一次传入的bytes如果大于alloc_bytes_remaining_但是小于kBlockSize的四分之一,那么再一次new一个kBlockSize的内存,而上一次分配的内存块中剩余的空间就浪费掉alloc_ptr_重新指向这次新分配的内存

在储存和获取内存使用的memory_usage_以及内存对齐时使用的reinterpret_cast参考这里这里

最后来看看class Arena的内存对齐,由于Arena::Allocate()并不能保证返回的内存地址是对齐的,所以就有了如下的代码

char* Arena::AllocateAligned(size_t bytes) {
    const int align = (sizeof(void*) > 8) ? sizeof(void*) : 8;
    assert((align & (align-1)) == 0);   // Pointer size should be a power of 2
    size_t current_mod = reinterpret_cast<uintptr_t>(alloc_ptr_) & (align-1);
    size_t slop = (current_mod == 0 ? 0 : align - current_mod);
    size_t needed = bytes + slop;
    char* result;
    if (needed <= alloc_bytes_remaining_) {
      result = alloc_ptr_ + slop;
      alloc_ptr_ += needed;
      alloc_bytes_remaining_ -= needed;
    } else {
      // AllocateFallback always returned aligned memory
      result = AllocateFallback(bytes);
    }
    assert((reinterpret_cast<uintptr_t>(result) & (align-1)) == 0);
    return result;
  }

它的思路是,输入要对齐到的bytes,然后计算还差多少才能对齐,然后alloc_ptr_加上这个差值,如果这个差值大于当前内存块的剩余可用值的话就直接返回一块从系统申请的新的已对齐的块。

关于内存对齐看这个讨论,数据结构对其看这里

PS
Arean::AllocateAligned()只在skiplist中用到过。



转载请注明:Serenity » leveldb - slice status arena

上一篇

下一篇