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

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

mctx 中的状态存储运行结果. 层级函数 L 的组合依靠高阶函数 LCompose, 它接受两个层级函数 L 1 和 L 2 , 得到一
个新的复合层级函数. 每个层级函数可以扩展出多个策略抽象, 这些策略函数 p 可以进一步提升层级的可定制性.
例如为了得到一个可组合的层级函数 L k , 必须通过柯里化 (Currying) 的方式不断为未完成的层级函数 l k 填充策略
函数, 直到所有的策略输入被定义, 该层级函数的类型才允许进行函数的组合. 即完整的层级函数. 本文使用
L 1 ::L 2 表示 LCompose(L 1 ,L 2 ) .

表 1 榫卯内存分配框架函数组合模型的定义

定义 说明
mctx 内存请求上下文
L : mctx → mctx 可组合的层级函数定义
LCompose(L 1 ,L 2 ) := fun x : mctx → L 1 (L 2 (x)) 用于组合层级函数L的高阶函数定义, 其中 L 1 ,L 2 : L
p := {p 0 , p 1 ,..., p n } 策略函数定义
l : p → p → ... → p → L 未填入策略函数的层级函数定义
i
m
k
L k := fun x : mctx → l k (p i , p j ,..., p m )(x) 填满策略函数的层级函数定义
Cm : A → mctx 用户内存分配封装函数
C f : mob j → mctx 用户内存释放封装函数
D : mctx → mobj 内存上下文解析函数
S : B → mobj 产生mobj的函数
V : mob j → mctx → mctx 消除mobj的函数

为了能够通过用户内存请求构造内存请求上下文, 我们需要定义用户内存申请封装函数 C m 以及它的解析函
数 D, 其中 A 是抽象数据类型, 可以由用户自定义. 最简单的 A 是用户请求的内存大小. mobj 是内存块指针及其大
小. 相似地, 对于内存释放请求同样需要定义 C f . 通常各层函数并不能凭空产生内存块. mobj 必须由已存在的内存
块通过分割函数产生. 不过, 最顶层至少有一个能产生 mobj 类型的函数 S 和消除 mobj 的函数 V. 其中, B 为抽象
数据类型, 描述可用于产生 mobj 的对象. 这里的 S 与 V 函数可以视为系统接口函数的抽象, 它可以通过向操作系
统请求或归还内存来产生或消除 mobj. 由此本文得到分配器的整体 3 层函数架构: (1) 用户接口层函数实现 C m ,
C f 和 D, 该层定义用户调用的内存请求接口, 使用抽象数据类型帮助用户根据应用需求定制更为灵活的内存请求
接口, 例如可以将抽象数据类型 A 定义为 size×cpu_id , 要求用户同时输入请求的大小以及 CPU 核心 ID, 以此可
构建根据 DRAM bank 或者 cache 分区策略的内存分配器. (2) 基础层函数实现未填入策略的层级函数 l 与策略函
数 p. 该层定义具体的内存分配机制, 同时可扩展出多种可替换的策略, 用户可将 p 填入 l 中得到可组合的层级函
数 L. 对于一个可组合的层级函数, 若本层无法处理用户内存请求则将请求转至上一层处理. (3) 系统接口层函数
实现 S 和 V, 该层定义最终的内存请求处理. 在有操作系统环境下, 该层通常定义如何与操作系统交互, 如处理新
的内存页的映射以及归还; 若在无操作系统的裸机环境下, 该层定义如何管理可用物理页.
至此, 本文提出了一种可组合的内存分配框架的设计. 该内存分配框架基于函数式编程思想将内存分配抽象
为互不耦合的层级函数, 通过层级函数的组合与定制实现分配器的搭建. 如图 2 所示, 在榫卯框架中, 每一个已定
义的层级函数都是一个可组合的构件, 而一个层级函数可以定义策略槽用于填充额外的策略函数以提供额外的扩
展性和定制性. 若策略槽已被填满, 层级函数完成定义, 能够连接到主构件中. 而内存分配从用户接口层对用户暴
露的接口函数 C m 调用开始, 接口会构造一个内存请求上下文 mctx, 用于封装内存请求信息, 各层的状态信息以及
分配的结果. 内存请求上下文会从底层函数向上逐级传递, 直到最顶层为止. 一旦满足要求的内存被分配, 内存块
mobj 会被记录到内存请求上下文中并逐级向下返回, 最后用户接口的解析函数 D 将 mctx 中记录的 mobj 提取出
来. 对于内存释放请求, 则通过 C f 函数包装为内存请求上下文, 与状态信息一并向上传递直到封装的 mobj 被某一
层级函数回收.
同时, 本文能够用一种简单的抽象模型语言来描述复杂的内存分配器架构, 如图 1 所示的分配器, 可描述为
A::B(sync = spinlock)::C(sync = ccsynch)::D(…)::E(…)::F. 其中每个层级函数括号中的为策略槽位, 即可自定义的

策略函数.