C++内存管理机制——loki::allocator

上中下3个class

loki::allocator中包含3个类，从上层至下层分别为SmallObjAllocator、FixedAllocator和Chunk。

Chunk

Init是由上层的类来调用的，不会提供给用户。其会申请blockSize * blocks大小的内存，并调用Reset来重置第一块可以使用的的内存索引firstAvailableBlock_为0，可使用的块数量blocksAvailable_为blocks。随后，将内存块中每个块的最前面的一个字节当做索引，与嵌入式指针类似。Release是用来释放Chunk申请的内存的。

接下来，探索索引的变化规则。假设当前的编号为5012367...64，通过Chunk::Allocate()申请内存，首先查Chunk的firstAvaliableBlock_，发现第一个可用内存块的索引为4，于是找到图中索引为3的位置，并将其置为使用状态，firstAvaliableBlock_变更为3，blocksAvailable_减1变更为63。

在执行Deallocate(p, blockSize)前，会先通过遍历找到p属于哪个Chunk，p减去Chunk的首地址，再被除以blockSize即可确定p的位置。然后将p对应的索引设置为firstAvaliableBlock_，blocksAvailable_加1。

FixedAllocator

FixedAllocator的成员如下代码所示，其中allocChunk_指向上一次满足分配的Chunk，deallocChunk_指向上一次释放的Chunk，这也很符合内聚性。

chunks_: vector<Chunk>
allocChunk_: Chunk*
deallocChunk_: Chunk*

FixedAllocator分配时首先判断allocChunk_是否为空或没有可以块，如果是上述情形，则暴力遍历chunks_。如果找到有可用块的Chunk，则让allocChunk指向该Chunk，调用Chunk::Allocate()进行分配。如果没找到，new一个新Chunk挂载在chunks_的末端，并初始化。allocChunk_指向这块新创建的Chunk，deallocChunk_指向chunks_的前端（因为新创建Chunk后，chunks_不一定还在原来的位置，可能被复制到其他位置，如果deallocChunk_指向的位置还是原来的位置可能会出现异常，因此把该指针指向最新的chunks_的前端）。

FixedAllocator释放时首先通过VicinityFind()找到块所在的位置。首先定义lo和hi两个指针，在循环中从deallocChunk_和deallocChunk_ + 1向chunks_的两端进行搜索，直到找到所在的Chunk。

这里存在一个bug，如果p并非由此系统取得，会跳不出循环

DoDeallocate()会调用deallocChunk_的Deallocate()方法进行回收，并判断其可用内存块数量blockAvailable_是否等于分配的内存块数量numBlocks。如果等于，则进行如下三个判断：

1. 如果deallocChunk_是chunks_的最后一个区块，且chunks_的大小大于1及deallocChunk_的前一个Chunk所有的区块也为空，则释放chunks_的最后一个区块。
2. 如果最后一个Chunk的所有块为空，释放最后一个区块，并令allocChunk_=deallocChunk_。
3. 否则，将deallocChunk_一道chunks_的末端。

参考

侯捷-C++内存管理机制