基于共享内存的对象池管理方案

Posted on | In

..1. 目录

通用的对象池方案

该方案本质上一个简单分离存储的内存分配方案:
分配器维护多个空闲链表, 每个空闲链表包含大小相等的空闲块 每个块的大小为这个大小类中最大元素的大小, 不分割不合并.

buddy_system

数据结构定义

1
2
3
4
5
对象池管理器
  [对象A条目IDX]: 对象是否包含虚函数(是否需要重建虚函数表):  对象类型(对应条目IDX): 对象大小: 对象个数: 该条目总长: 条目对应内存地址:  条目对应对象起始地址: 空闲对象下标ID : 已分配计数   
  [对象B条目IDX]: 对象是否包含虚函数(是否需要重建虚函数表):  对象类型(对应条目IDX): 对象大小: 对象个数: 该条目总长: 条目对应内存地址:  条目对应对象起始地址: 空闲对象下标ID : 已分配计数   
  [对象C条目IDX]: 对象是否包含虚函数(是否需要重建虚函数表):  对象类型(对应条目IDX): 对象大小: 对象个数: 该条目总长: 条目对应内存地址:  条目对应对象起始地址: 空闲对象下标ID : 已分配计数   
  [对象D条目IDX]: 对象是否包含虚函数(是否需要重建虚函数表):  对象类型(对应条目IDX): 对象大小: 对象个数: 该条目总长: 条目对应内存地址:  条目对应对象起始地址: 空闲对象下标ID : 已分配计数

单个条目指向的起始地址结构:

1
flag|flag|flag : ...  FENCE SIZE: NODE SIZE :   FENCE SIZE: NODE SIZE :   ...

条目指向的地址会首先保存flag标志标明该对象是否在使用中, 用于请求和释放时候的判定标志
NODE SIZE会进行8字节对齐, FENCE SIZE也选择8字节 这样整个对象池的地址都是保证8字节对齐的
FENCE写入特殊固定的魔法数值 用于溢出检测
分配出去的对象 NODE SIZE的起始地址即为对象的地址
空闲的对象, 其NODE SIZE的第一个U32保存的是下一个空闲内存 

1
2
: NODE SIZE: 对应下面结构
: FREE IDX, NODE SIZE- FENCE SIZE:

初始化

我们首先通过静态代码定义好对应每种对象的条目ID, 并记录(注册)该条目的条目信息, 这时可以得到对象池管理器占用的大小, 以及每个对象池的总长, 以保证共享内存在分配的时候分配足够的内存完成初始化.
在对象池管理器的内存之后 开始逐个条目初始化对象池
首先对FLAG标志段的内存清零, 即所有flag都是空闲
然后从FLAG后开始进行空闲对象池的初始化

  1. 设置FENCE数值 例如0XBEAFBEAFBEAFBEAF
  2. 设置FREE IDX 指向下一个对象的IDX . 即obj[0].free_idx =1; obj[1].free_idx =2; 依次初始化. 最后一个对象的空闲指针指向一个特殊值(-1)表示没有下一个
  3. 设置对象池管理器中该条目的空闲对象下标ID(空闲链表的HEAD)为第一个对象0

分配

检查空闲链表是否为空(指向-1), 如果不是则把第一个对象摘除(设置head为该空闲对象的的next free idx), 并重新设置该对象前后的FENCE, 以及该对象所在的FLAG标志位使用中
性能是O(1)

回收

通过该对象的条目信息找到对象池的起始地址, 计算对象所在的IDX
检查FLAG标记是否是使用中
检查FENCE是否被覆盖(溢出)

加入空闲链表: 空闲HEAD指向该对象, 该对象的空闲索引指向原HEAD.
设置FLAG标记

性能是O(1)

虚函数表的重建

对于内存池管理器中存在包含有虚函数的对象池, 遍历已分配的对象, 并设置该对象起始内存的第一个8字节为真正的虚函数表的地址.
TIPS:
只允许单继承, 多继承情况下虚函数表的指针位置和个数难以确定(没有相应的语言标准 跟随编译器实现)
空闲索引ID如果扩增为8字节并且在分配出去的内存保留, 则可以减少resume时的遍历个数, 即和已分配个数一致 而不是遍历条目中的所有对象. 会牺牲一点内存

协助使用的容器类

KV容器

  • 基于定长内存实现一个HASH MAP, 实现一个有公共溢出区的的HASH map
    • 桶的数量固定, 溢出区留够充分的空间, (一般hash的load_factor负载因子大约在0.75~0.85, 但因为这个实现没有扩展能力需要远超过这个因子大小)
      • 双倍容器大小的桶数量
      • 容器大小往后的桶按照空闲对象池的处理方式做成单向的空闲链表
      • 桶包含前后指针, 遇到冲突时从空闲池中获取一个新桶
      • 释放时候从桶的双向链表中摘除并交换给空闲链表

数组容器

  • 容器的最大大小是固定的, 但动态调整当前已使用大小.
    • 类似vector reserve足够的大小时的情景, 比std:array更易用

与动态内存分配器方案简单对比:

对比内容 定长内存(对象)池分配方案 动态内存分配器方案
内存利用率 低, 不同大小甚至不同类型的内存无法相互替换使用, 也不能通过合并来满足更大的内存分配请求 高, 一般都会进行切分与合并空闲块来减少内部碎片与外部碎片, 并且在合适的时候进行内存收缩
分配性能 高, 稳定且很小的常数 高, 一般能达到接近常数, 最坏情况LGN
适应场景 固定的使用场景, 类型大小固定, 上限确定并且有限, 通常能达到接近上限而不会超过上限的水平 几乎任意场景, 例如STL容器, LUA脚本虚拟机, protobuff
峰值使用预估 好评估, 从选用该方案前的业务侧就能确定上限, 在代码编译期或者系统运行前读到配置后就一次性计算好总大小 无法简单使用对象池的领域往往业务侧就只能给出宽松的上限, 通过这些宽松的上限直接计算出的总内存量一般在实际运行时只具备参考意义, 需要结合生产环境的实际测试进行综合评估
实现复杂度 低, 简单分离存储模型 高, 分离适配模型
调试难度 低, 内存地址和类型固定映射, 并且方便扩充管理信息 高, 内存地址和类型无关