allocate需要如下需求：
- 如何设计内存池；
- 如何设计字节对齐；
- 如何设计统计内存使用情况；（待完成）
- 如何设计单元测试验证内存池的正确性。（待完成）
一些技术问题：
- malloc是已经实现内存对齐了，问如何实现的，怎么证明？（未解决）
- free和delete是如何实现的，如何知道释放多少内存。（未解决）
一 如何设计内存池
内存池一般而言，即是大块内存直接分配，小块内存则先申请一个大块内存，然后不断地使用这个大块内存直至用完。基本算法如下：
inline char* Arena::Allocate(size_t bytes) {
// The semantics of what to return are a bit messy if we allow
// 0-byte allocations, so we disallow them here (we don't need
// them for our internal use).
assert(bytes > 0);
if (bytes <= alloc_bytes_remaining_) { //是否能从可用内存中获取
char* result = alloc_ptr_;
alloc_ptr_ += bytes;
alloc_bytes_remaining_ -= bytes;
return result;
}
return AllocateFallback(bytes); //不能，去申请内存
}
大块内存一定无法从可用内存中获取，小块内存则需要看剩余内存大小，如果剩余量小于需求，则也需要申请，否则，不需要申请。
所以小块内存共用的大块内存的使用情况，需要使用如下两个变量来标识：
// Allocation state
char* alloc_ptr_; //大块内存的可用位置；
size_t alloc_bytes_remaining_; //当前大块内存还剩余多少
简化了小块内存的分配，大块内存的分配逻辑如下：
char* Arena::AllocateFallback(size_t bytes) {
if (bytes > kBlockSize / 4) {
// Object is more than a quarter of our block size. Allocate it separately
// to avoid wasting too much space in leftover bytes.
char* result = AllocateNewBlock(bytes);
return result;
}
// We waste the remaining space in the current block.
alloc_ptr_ = AllocateNewBlock(kBlockSize);
alloc_bytes_remaining_ = kBlockSize;
char* result = alloc_ptr_;
alloc_ptr_ += bytes;
alloc_bytes_remaining_ -= bytes;
return result;
}
char* Arena::AllocateNewBlock(size_t block_bytes) { //所有申请内存的操作都在这；
char* result = new char[block_bytes];
blocks_.push_back(result);
memory_usage_.NoBarrier_Store(
reinterpret_cast<void*>(MemoryUsage() + block_bytes + sizeof(char*)));
return result;
}
申请大块内存有两种情况：
（1）用户本身申请的就是大内存；
（2）用户申请的是小内存，但是小内存所使用的大内存块用完了。
对于第一种情况，直接调用AllocateNewBlock方法，申请出那么大的内存来并交给用户就可以了。
对于第二种情况，调用完AllocateNewBlock方法申请固定大小内存（kBlockSize），还需要设置 alloc_ptr_和alloc_bytes_remaining_变量；最后在这块新申请的大内存中分配内存给用户。
内存的释放是统一在一起进行的，位于分配器的析构函数中：
Arena::~Arena() {
for (size_t i = 0; i < blocks_.size(); i++) {
delete[] blocks_[i];
}
}
blocks_定义如下：
// Array of new[] allocated memory blocks
std::vector<char*> blocks_;
blocks_包含了所有AllocateNewBlock方法申请的内存，最后统一释放。
一些问题：
- 小内存共用的大块内存是多大，即一次申请多大合适？（相关的论文查询）
leveldb中是这个大小：
static const int kBlockSize = 4096;
申请多大的内存适合直接返回给用户，而不是共用大内存块？
这种分为两种情况：
（1）存在可用大块内存时，只要大块内存够用，就都是直接返回给用户；
（2）不存在可用的大块内存时，超过kBlockSize的1/4，就直接申请相应大小的内存返回给用户，而不是当作小内存来申请kBlockSize大小的内存。以上策略存在内存的浪费，具体表现为：
当用户新申请的内存不在可用内存大小范围内，且小于kBlockSize时，那一段可用内存就被浪费了，去新申请新的内存了， alloc_ptr_从新内存开始。内存是最后统一释放的，所以是不是需要一些策略来提前释放以节约内存？具体的释放时机是什么？
二 如何设计字节对齐
malloc分配的内存一定是对齐的，含义是其返回的地址一定是2的幂次（内存对齐的大小一般是指针的大小，指针的大小一定是2的幂次）。
所以对齐的大小align求法：
const int align = (sizeof(void*) > 8) ? sizeof(void*) : 8;
对齐之后的地址一定满足（align - 1的值中1的个数代表了返回值指针最后的0的个数）：
assert((reinterpret_cast<uintptr_t>(result) & (align-1)) == 0);
具体算法如下：
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); //alloc_ptr_的后n位，n为对齐的位数
size_t slop = (current_mod == 0 ? 0 : align - current_mod); //对齐需要空余的字节数
size_t needed = bytes + slop;
char* result;
if (needed <= alloc_bytes_remaining_) { //类似于上一小节的Allocate
result = alloc_ptr_ + slop;
alloc_ptr_ += needed;
alloc_bytes_remaining_ -= needed;
} else {
// AllocateFallback always returned aligned memory
result = AllocateFallback(bytes); //调用malloc的一定是内存对齐的；
}
assert((reinterpret_cast<uintptr_t>(result) & (align-1)) == 0);
return result;
}
函数同样分为两部分来处理：
（1）申请内存大小 + 对齐字节数 > 可用内存大小，此时直接调用malloc去申请（此时可能会造成内存的浪费），此时一定是内存对齐的；
（2）申请内存大小 + 对齐字节数 < 可用内存大小，手动对齐：将alloc_ptr_调整到对齐位置，作为返回结果，再调整alloc_ptr_到下一可用位置。其中对齐的结果是返回值对齐的，最后的alloc_ptr_不是对齐的。
三 如何设计统计内存使用情况；
内存的使用需要进行统计，以方便进行监控以及内存泄露的查询。
内存的统计要求所有的内存申请工作都需要在同一个函数中进行：AllocateNewBlock。
