# SunMao

**Repository Path**: matrixsukhoi/sun-mao

## Basic Information

- **Project Name**: SunMao
- **Description**: "榫卯"操作系统内核编程框架。

- **Primary Language**: C
- **License**: Not specified
- **Default Branch**: master
- **Homepage**: None
- **GVP Project**: No

## Statistics

- **Stars**: 1
- **Forks**: 1
- **Created**: 2023-05-22
- **Last Updated**: 2024-06-19

## Categories & Tags

**Categories**: Uncategorized

**Tags**: None

## README

博士毕业论文工作的全部代码，用于开源评估，确保论文结果可复现。

# 榫卯：可组合的内核编程框架

机载软件领域的DO-178C标准对操作系统内核验证要求是形式化验证或100%代码覆盖率的测试。由于与硬件关系密切，内核代码的验证开销极为昂贵——在假设硬件和编译器都是正确基础上，代码规模9000行的seL4内核代码进行完全形式化验证的平均验证工时高达10.7小时/行，因此开发者应尽可能提高内核代码的可复用性，减少重复验证的开销。

围绕改善内核编程的代码可复用性目标，“榫卯”内核编程框架采用基于组件的函数式编程模型，其核心思想是将内核功能分解为去耦合的组件，通过分离其外部依赖和函数副作用，从而尽可能将组件功能实现为可复用、可组合的纯函数。榫卯内核编程框架采用GNU C11标准的C语言实现，充分利用编译器扩展、泛型和函数式元编程简化内核实现，并通过基于编译器静态分析与自动化静态验证技术提升内核编程安全性。

为了能让组件实现尽可能的纯函数化，组件函数本身并不维护状态。在用户填充依赖函数后将组件实例化之后，由组件实例的使用者(通常在一个.c文件中实现)负责维护全局状态(由组件函数创建或初始化的对象)，并在调用组件函数时显式的将全局状态输入。组件不维护全局状态的好处主要由两方面体现，一方面，所有组件函数都能以static inline内联或编译器强制内联(\_\_attribute\_\_((always\_inline)))函数以及宏函数的形式在.h文件中实现。这些组件函数可以被用户在头文件中引入，而不用担心除占据宏命名和函数命名以外的任何副作用。组件在组合时，所有代码对编译器都是可见的，可由编译器优化不必要的函数调用过程，提升性能。另一方面，组件函数本身与全局状态无关、只与输入有关的特点也便于集成测试。开发者能在不影响系统正常运行的情况下，构造所需状态来测试代码分支，从而确保代码全部覆盖。同时，组件可以在操作系统用户环境下填入合适的依赖函数将组件实例化后使用。

榫卯内核编程框架的代码组织结果如下
```
/ftest - 功能测试
/include - 框架核心实现
/include_api - 框架对外api
/include_arch - 框架体系结构依赖
/include_plat - 框架平台依赖
/include/base - 类型定义与宏元编程的实现
/include/base/macro - 宏元编程的相关实现
/include/compl - 编译器提供的内置函数及语法糖定义
/include/dbg - 调试相关的实现
/include/dcont - 控制流抽象
/include/ddblk - 阻塞式同步实现(APFSDS同步框架)
/include/dinfra - 内核基础数据结构与算法
/include/metalc - METAlc内存分配器框架
/libcoco - COCO库实现
/libapfsds - APFSDS库实现
/libmetalc - METAlc库实现
```

# μmp: 基于multi-prompt delimited control的控制流组合

基于组件的函数式编程可实现编译时的代码静态组合和复用，而在实际的操作系统内核编程中，还要求代码具备一定的运行时的动态控制流可组合性，例如I/O场景。

基于多prompt分界控制(Multi-prompt Delimited Control)语义，榫卯内核编程框架实现了一种高性能、可组合、易移植的动态控制流组合方式μmp。μmp结合内核环境的应用特点，运用编译器内联汇编优化、硬件预取等方式改善性能和局部性。通过将μmp实现为协程库的形式，与目前主流的协程实现进行对比。在四种不同硬件平台运行微基准测试的实验结果显示，基于μmp实现的协程库在协程上下文切换时间、协程创建、多协程上下文切换时间等关键性能指标上全面优于其他实现，在Intel Core i7 13700k平台上，μmp单协程上下文切换时间为5.7ns，切换速度是目前最快的libaco的2.4倍(13.7ns)。


<!-- $$
		stack_ptr - {prompt栈指针}\\
		stack_size - {prompt栈大小}\\
		prompt_fun - {prompt函数指针}\\
		prompt_val - {prompt参数或返回值}\\
		yield_fun - {yield回调函数}\\
		({prompt初始化})\ \textbf{prompt_init}:(stack_ptr,stack_size) \rightarrowprompt \
		({prompt初次执行})\textbf{prompt_exec}:(prompt,prompt_fun,prompt_val) \rightarrowprompt_val \\
		({prompt出让})\textbf{prompt_yield}:(prompt,yield_fun,prompt_val) \rightarrow prompt_val\\
		({prompt恢复})\textbf{prompt_resume}:(prompt,prompt_val) \rightarrowprompt_val \\
		({prompt返回})\textbf{prompt_return} :prompt_val 
$$ -->

μmp主要实现包括`include/dcont/dprompt.h`和体系结构支持`include_arch/dcont/*.h`，`include/dcont/pcorou.h`是μmp的协程封装。

编译步骤：

```bash
cd libcoco
./get3rd.sh # git clone获取第三方协程实现用于对比，如果不需要可以不执行，但make lib过程中依赖第三方协程实现的封装会编译失败
make lib # 编译libcoco库，生成的静态库在./build_lib，生成的动态库在./build_libso目录下
make #编译微基准测试，编译结果在./build目录下
```

完成库编译后可通过脚本执行全部微基准测试。执行结果保存在`./libcoco/log/result.tsv`中：

```bash
./runbech.sh 5 # 参数为执行次数
```

`./libcoco/script`中是计算结果平均数和标准差的python脚本

# APFSDS: 异步Promise/Future风格的委任同步

锁同步、合并同步(combining)与委任同步(delegation)是三种典型的阻塞式同步方式。基于并行编程的Promise/Future模型，本文对合并同步以及委任同步的执行过程做了进一步的分解，提出了一种可组合的委任同步框架APFSDS(Asynchronous Promise/Future-Style Delegation Synchronization, 异步Promise/Future风格的委任同步)。APFSDS同步框架在榫卯内核编程框架中实现，在提供传统的同步接口的同时，还额外提供更细粒度的future fetch/try/wait接口，从而允许合并同步及委任同步过程的异步执行。

在APFSDS框架实现了一种核心感知的合并同步方法(CAC)。该方法的主要思想是通过优先将临界区转移给高性能核心，加速临界区执行，从而解决异构多核系统同步过程中的小核瓶颈问题。

<!-- $$
	ptr-{内存指针}\\
	size-{内存大小}\\
	apfsds-{apfsds promise对象}\\
	apfsds\_fun-{apfsds请求函数}\\
	apfsds\_args-{apfsds请求执行参数}\\
	apfsds\_future-{apfsds future对象}\\
	({apfsds对象构造})\textbf{apfsds\_init}:(ptr,size) \rightarrowapfsds \
	({apfsds对象析构})\textbf{apfsds\_destruct}:(apfsds, size) \rightarrowptr \
	({apfsds future对象获取})\textbf{apfsds\_fetch}:(apfsds,apfsds\_fun,apfsds\_args) \rightarrowapfsds\_future \\
	({apfsds future对象测试})\textbf{apfsds\_try}:(apfsds, apfsds\_future) \rightarrow bool \\
	({apfsds future阻塞式等待})\textbf{apfsds\_wait}:(apfsds, apfsds\_future) \rightarrowapfsds\_val \\
	({apfsds 同步})\textbf{apfsds\_sync} :(apfsds,\ apfsds\_fun,\ apfsds\_args) \rightarrow\ apfsds\_val \\
$$ -->

编译步骤：

```bash
cd libapfsds
make lib # 编译libapfsds库，生成的库在./build_lib目录下
make #编译微基准测试，编译结果在./build目录下
cd bench	# 编译splash3
./build_bench.sh # 编译splash3
```

基准测试：

```bash
./bench_all.sh 8 # 传入线程数N=8运行所有微基准测试(共10次)
```

`./libcoco/script`中是对微基准测试结果绘图的python脚本。

# METAlc: 可组合的内存管理框架 

针对现有的内存管理框架组合性与定制性不足的问题，METAlc(META-ALloCator)框架将系统内存分配抽象为多个互不耦合的内存分配层级函数的组合，这些层级函数能够扩展出策略槽，以提供更高的定制性和组合性。METAlc基于榫卯内核编程框架实现，通过基于组件的函数式编程实现层级函数组合的零性能开销。

METAlc框架下还实现了一种无等待的实时内存分配算法wfspan。针对现有无锁内存分配算法的线程饥饿问题，wfspan采用两种高性能无等待数据构造，其一是不可线性化的MPSC空闲内存链表，其二是基于帮助机制的SPMC span链表。wfspan以提升有上界的最差情况内存占用换取内存请求过程有界的执行步骤。

编译步骤：

```bash
cd libmetalc
./get3rd.sh # 获取第三方git库
./build3rd.sh # 编译第三方库
make lib # 编译libapfsds库，生成的库在./build_lib目录下
make #编译微基准测试，编译结果在./build目录下
```

基准测试的编译与运行步骤：

```bash
./bench_libsize.sh # 对可执行文件大小进行统计
./bench_wcet.sh 5 # 运行最坏情况执行时间测试5次
./bench_wcmf.sh 5 # 运行最坏情况内存占用测试5次
cd ./git3rd/mimalloc-bench/out/bench # 进入mimalloc-bench目录
../../bench_my.sh -r=5 allan allt # 执行mimalloc-bench基准测试
```

`./libmetalc/script`中是对微基准测试结果绘图的python脚本。

# 相关文献

[1] Core-aware combining: Accelerating critical section execution on heterogeneous multi-core systems via combining synchronization[J]. Journal of Parallel and Distributed Computing, 2022, 162: 27-43. 

[2] wfspan: wait-free dynamic memory management[J]. ACM Transactions on Embedded Computing Systems, 2022, 43: 1-26. 

[3] 榫卯: 一种可组合的定制化内存管理框架[J]. 软件学报. 

<!-- [4] 面向多核实时操作系统的关键技术研究[D]. 西安：西北工业大学, 2023. -->