【C++内存管理】15_Loki allocator 源码分析 c++c

Loki是由 Andrei 编写的一个与《Modern C++ Design》（C++设计新思维）一书配套发行的C++代码库。其中有两个文件 SmallObj.h 、SmallObj.cpp 进行内存管理，可以单独进行使用
Loki 源码下载
类层次结构 SmallObj 文件中有三个类：chunk, FixedAllocator 和 SmallObjAllocator。其中SmallObjAllocator 位于最顶层供应用程序调用

文章图片

Chunk Chunk 是类层次结构中最底层管理内存块的类，它负责向操作系统进行内存申请
Init, Reset, Release
文章图片

1. Init(), 使用 operator new 申请一段内存 chunk, 并使用 pData_ 指向 chunk 2. Reset(), 对 pData_ 指向的内存进行分割。[数组代替链表，索引代替指针] [与嵌入式指针类似]每一块 block 的第一个字节存放的是下一个可用的 block 距离起始位置 pData_ 的偏移量(以 block 大小为单位) 3. Relese(), 向操作系统归还内存 -- 1. blockSize、blocksblock, block 大小及数量 2. firstAvailableBlock_,当前可用内存块的偏移量 3. blocksAvailable,当前 chunk 中剩余的 block 数量

unsigned char i = 0; unsigned char *p = pData; for(; i!=blocks; p+=blockSize)// 以 blockSize 为间隔切分 chunk 为 block *p = ++i; // 以 block 的第一个字节存储下一个可用 block 索引

参数初始化后的 chunk

文章图片

Allocate

用索引对区块进行管理[第一字节流水号]

文章图片

Deallocate

文章图片

FixedAllocator FixedAllocate 负责管理一个具有相同大小 block 的 chunk 集合。它负责根据应用程序需求，创建特定大小的 chunk，并放置在 vcector 中进行管理
Allocate

void *FixedAllocator::allocate() { if (allocChunk_ == 0 || allocChunk_->blocksAvailable == 0) { // 目前没有标定 chunk 或该 chunk 已无可用区块Chunks::iterator i = chunks_.begin(); // 打算从头找起 for (; ; ++i)// 找遍每个 chunk 直至找到拥有可用区块者 { if (i == chunks_.end())// 到达尾端，都没找到 { // Initialize chunks_.push_back(Chunk()); // 产生 a new chunk 挂于末端； Chunk()，创建临时对象拷贝至容器然后结束生命 Chunk& newChunk = chunks_.back(); // 指向末端 newChunk.Init(blockSize_, numBlocks_); // 设置好索引 allocChunk_ = &newChunk; // 标定，稍后将对此 chunk 取区块 deallocChunk_ = &chunks_.front(); // 另一标定 break; }if (i->blocksAvailable_ > 0) { // current chunk 有可用区块 allocChunk_ = &*i; // 取地址 break; } } }// allocChunk_，在此 chunk 找到可用区块，下次就优先从此找起 return allocChunk_->Allocate(blockSize_); // 向这个 chunk 取区块 }

allocChunk_

标记最近一次满足分配动作的 chunk, 当下次再有分配需求时，优先检查此 chunk

deallochunk_

依靠数据的内聚性和区域性原则当某一 chunk 发生内存回收时，下次回收也可能发生在此 chunk 上。以此尽量避免 `void Deallocate(void *p)`中 p 落在哪一个 chunks 的遍历查找动作（类比于上述代码 for ）

deallocChunk_ = &chunks_.front()

vector 在进行 insert 时，可能会导致内存增长，内存增长时元素将从旧空间拷贝到新的空间，此时过去 deallocChunk_ 指向的地址将失效，因此需要对 deallocChunk_ 重新标定

Deallocate 我们需要根据归还内存的地址，把这块内存回收到对应的 chunk 中

void FixedAllocator::Deallocate(void *p) { deallocChunk = VicinityFind(p); DoDeallocate(); }

VicinityFind
根据内存使用的区域性,采用临近查找法确定 p 所对应的 chunk

文章图片

1. 已知每一块 chunk 指向内存空间的地址 p_Data_ 2. 已知每一块内存空间的大小 numblocks_ * blocksize 3. 由此可计算出每一块 chunk 指向内存的地址范围 [p_Data_, p_Data_ + numblocks_ * blocksize] 4. 由此可计算出归还的内存 p 属于哪一个 chunk---查找思想：VicinityFind 采用临近分头查找的算法，从上一次 dealloChunk_ 的位置出发进行上下两头查找 (内存分配通常是个容器服务的,而容器元素连续创建时，通常就从同一个 chunk 获得连续的地址空间，归还的时候当然也是归还到同一块 chunk。通过对上一次归还 chunk 的记录，尽量避免遍历搜索，提高了查找定位速度)在上述实现中，如果 p 并非当初由此系统获得，肯定找不到对应的 chunk，于是陷入死循环。在新版本中已修复此问题

DoDeallocate
完成实际的内存回收

文章图片

1. deallocChunk->Deallocate(p, blockSize_); 由 FixedAllocator::chunk::Deallocate(void *p, std::size_t blockSize) 完成底层的内存回收 2. 当 deallockChunk_->blocksAvailable_ = numBlocks_ 时表示当前内存可以归还给操作系统 3. 延迟归还机制，把空的 chunk 交换到 vector 尾部，只有出现两个空的 chunk 时，才会发生真正的内存归还动作（表中标注①②③）

SmallObjAllocator 【【C++内存管理】15_Loki allocator 源码分析】SmallObjAllocator 负责管理具有不同 block size 的 FixedAllocate 的vector 集合
Allocate

void* SmallObjAllocator::Allocate(std::size_t numBytes) { if (numBytes > maxObjectSize_) return operator new(numBytes); if (pLastAlloc_ && pLastAlloc_->BlockSize() == numBytes) { return pLastAlloc_->Allocate(); }//找到第一个 >= numBytes 的位置 Pool::iterator i = std::lower_bound(pool_.begin(), pool_.end(), numBytes); //没找到相同的，就重新创建一个 FixedAllocator if (i == pool_.end() || i->BlockSize() != numBytes) { i = pool_.insert(i, FixedAllocator(numBytes)); pLastDealloc_ = &*pool_.begin(); } pLastAlloc_ = &*i; return pLastAlloc_->Allocate(); }

1. 当应用程序请求的 numBytes 大于 maxObjectSize_ 时交由 operator new 处理 2. pLastAlloc_ 记录上次分配 block 的 FixedAllocator object。如果本次申请的 block size 等于上次分配的 block size，就直接使用同一个 FixedAllocator object，以此尽力避免查找动作（最佳客户是容器，容器的元素大小是相同的） 3. 如果本次需求的 block size 不等于上次分配的 block size，就遍历查找大小相等的 FixedAllocator object。如果没有找到，就插入新的 FixedAllocator object。同时为了避免 vector 扩容引起的内存重新分配，对 pLastDealloc_重定位

Deallocate

void SmallObjAllocator::Deallocate(void* p, std::size_t numBytes) { if (numBytes > maxObjectSize_) return operator delete(p); if (pLastDealloc_ && pLastDealloc_->BlockSize() == numBytes) { pLastDealloc_->Deallocate(p); return; } Pool::iterator i = std::lower_bound(pool_.begin(), pool_.end(), numBytes); assert(i != pool_.end()); assert(i->BlockSize() == numBytes); pLastDealloc_ = &*i; pLastDealloc_->Deallocate(p); }

Loki allocator 检讨

曾经有两个 bugs, 新版已修正
精简强悍；手段暴力（关于 for-loop）
使用「以 array 取代 list, 以 index 取代 pointer」的特殊实现手法
能够以简单的方式判断「chunk 全回收」进而将 memory 归还给操作系统
有 Deferring (延迟归还)能力
这是个 allocator, 用来分配大量小块不带 cookie 的memory blocks, 它的最佳客户是容器（因为使用时要记录块大小）
内部使用的 vector 采用 std::allocator 实现

与 std::alloc 的比较

std::allocator	loki::allocator
不会向操作系统归还内存	延迟机制内存归还
服务于 8-128（每次增加 8byte）内存块，申请不满足时RoundUp调整	为不大于最大 block size 的所有 block size 服务