Page 500 - 《软件学报》2024年第4期

2078 软件学报 2024 年第 35 卷第 4 期

内存分配器视为多个 Heap 类的组合, 并提供灵活, 解耦合的 Heap 类自定义. Heap 类主要实现 3 种接口, 分别为
malloc (sz)/free (ptr)/get_size (ptr). 在构造内存分配器时, 用户只需要通过 C++ mix-in 机制混合多个 Heap 类即可
得到所需的内存分配器. 虽然 HeapLayer 能够定制出满足大部分应用场景的专用分配器, 但是它依然存在一些限
制. 例如, Heap 类内存请求传递的只有内存请求的大小或者释放的内存指针. 尽管 HeapLayer 能够快速构建出
malloc(3) 定义的内存分配器实现, 却无法实现更灵活的用户接口. 例如操作系统内存分配常用的接口并非 malloc(3),
而是页对齐分配接口 page_alloc 与对象分配接口 kmalloc; 而在一些内存分区隔离的分配器中, 分配接口还需要传
入额外的核心 ID 作为可选参数以区分特定的 DRAM bank 和 CPU cache 组 [6−8] . 同时, HeapLayer 也没有提供同步
机制的抽象, 这意味着 HeapLayer 无法依据应用场景的需求与并发竞争程度定制最佳的线程同步方式. 例如, 在存
在大量竞争分散的锁时, CAS 自旋锁具有性能优势; 而在要求确定的最差情况执行时间的实时系统领域, 同步过
程需要使用公平锁, 它能保证等待锁的线程不会陷入饥饿; 在存在高度并发的 NUMA 系统中, 基于委任的分层锁
通常更具性能优势 [9−15] . HeapLayer 依赖 C++标准库以及 C++模板提供的 mix-in [16] , 因而难以在无操作系统的裸机
环境或嵌入式实时操作系统环境下定制内存分配器. 此外, HeapLayer 在某些存在约束的编码场景下也无法应用,
如只有 C 编译器支持的嵌入式硬件平台以及禁止 C++编码的 Linux 内核编程.
针对当前内存分配框架存在的限制, 本文提出了一种新型可组合的定制化内存分配框架榫卯, 如图 1 所示. 榫
卯框架基于可组合的函数式编程思想, 将内存分配器抽象为多个互不耦合的层级函数. 层级函数分为系统接口层,
基础层与用户接口层 3 大类. 开发人员能够通过组合已定义好的层级函数, 快速构建出所需要的专用动态内存分
配器, 从而避免手动编写内存分配器时可能出现的错误. 此外, 开发人员可以使用该框架内提供的库函数, 策略函
数与数据结构等基本构件编写并定制新的层级函数. 在编写过程中开发人员只需关注特定层函数的实现.

内存请求示意 层级连接
系统接口层 A
策略填充
...
错误处理策略
基础层 B 大小阶划分策略
同步策略
自旋锁 CAS-spin

基础层 C 排队自旋锁 ticket

[LARGE_SIZE, 委任锁 ccsynch
MAX_ULONG)
基础层 D

[MEDIUM_SIZE, 基础层 E
LARGE_SIZE)
[0,
MEDIUM_SIZE)

用户接口层 F

图 1 榫卯内存框架示意图

与现有的内存分配框架相比, 榫卯框架的特点在于:
(1) 组合性更好. 榫卯框架以函数式编程思想审视内存分配流程, 通过构造可扩展的内存请求上下文来在层级
函数之间传递内存请求, 同时封装函数产生的副作用. 这使得榫卯框架能够自定义用户请求接口.
(2) 定制性更好. 榫卯框架为每一个层级函数扩展出策略槽, 用于插入一些可复用的策略函数, 例如大小阶
(size class) 的映射函数与保证线程安全的同步算法函数. 这些策略函数为榫卯框架提供了更高的自由度, 可以产
生更多的定制组合.