IPADS OS Course Lab Manual

本仓库包含上海交通大学IPADS实验室设计的操作系统课程系列实验。每个实验位于独立的目录，附有详细的实验说明和源码解析。

课程教材:

完成系列实验后，你可以在树莓派上用自己DIY的ChCore内核，运行宝可梦游戏、调用DeepSeek、本地运行Qwen-1.5b等等。

GBA

Lab0: 拆炸弹 (ARM 汇编)

该实验受到CSAPP课程启发，CSAPP课程设计了一个针对x86/x86-64汇编的拆炸弹实验。 不同之处在于，本实验目标是熟悉ARM汇编语言，并为后续的ARM/树莓派内核实验做好准备。

Tutorial: https://www.bilibili.com/video/BV1q94y1a7BF/?vd_source=63231f40c83c4d292b2a881fda478960

Lab1: 内核启动

该实验的主要内容是关于如何在内核启动过程中设置CPU异常级别、配置内核页表并启用MMU。 在内核实验系列中，我们将使用 ChCore 微内核 的基础版本，并使用 Raspi3b+作为实验平台（无论是使用QEMU树莓派模拟器还是树莓派开发板都可以）。

Tutorial: https://www.bilibili.com/video/BV1gj411i7dh/?spm_id_from=333.337.search-card.all.click

Lab2: 内存管理

该实验主要内容是关于内核中的伙伴系统和slab分配器的实现，并为应用程序设置页表。

Tutorial: https://www.bilibili.com/video/BV1284y1Q7Jc/?vd_source=316867e8ad2c56f50fa94e8122dd7d38

Lab3: 进程与线程

该实验主要内容包括创建第一个用户态进程和线程，完善异常处理流程和系统调用，编写一个Hello-World在实验内核上运行。

Tutorial: https://www.bilibili.com/video/BV11N411j7bR/

Lab4：多核调度与IPC

该实验中可以看到多核是如何启动的、多线程如何调度、基于capability权限管控的进程间通信机制。

Tutorial: https://www.bilibili.com/video/BV1AS421N7rU/

Lab5：虚拟文件系统

该实验关注虚拟文件系统（Virtual File System，VFS）, VFS抽象层使得不同类型的文件系统可以在应用程序层面以统一的方式进行访问。

Lab6：GUI (Optional)

该实验将详细介绍ChCore上基于Wayland的GUI系统的运行原理，包括Wayland通信协议和Wayland Compositor，并且要求读者在了解基于Wayland的GUI系统运行原理的基础上，基于ChCore的GUI框架编写自己的具有GUI界面的APP。

如何开始实验

• 环境准备
  • 使用Dev-Container (推荐)
  • 本地手动安装
• 文档说明
• CI评分

环境准备

对于所有的操作系统，本实验必须依赖Docker环境且仅能在Linux系统上进行运行(我们不支持Mac OS系统)， 请按照Docker官方指示为你运行的操作系统安装对应的Docker发行版。

gzip -cd docker.ipads.oslab.yy.mm.tar.gz | docker load

使用Dev-Container (推荐)

如果你使用的是带有支持Microsoft规范下Dev-Container插件的代码编辑器或者集成开发环境，亦或者你使用的是非Linux平台的开发环境，我们强烈建议你使用Dev-container直接进行开发，我们已经在其中已经预先安装好了你可能需要使用的所有工具链。并且针对vscode我们在每个Lab的分支目录下都已经配置好了合适的插件配置，简单安装即可以一键启用。安装完之后进入本实验的根目录，此时dev-container会识别到容器开发环境，重新进入后就可以直接使用了。

本地手动安装

如果你并不想要使用Dev-container，且你使用的是原生Linux平台或者自行创建的Linux虚拟机，我们在下方准备了所有流行发行版的工具链安装命令。同时我们也推荐安装clangd，其可以根据CMake生成的compile_commands.json即编译信息数据库提供增强的LSP的提示功能，用于支撑区分相同函数签名但是不同编译单元参与编译的重名跳转以及根据宏定义用于高显源文件。

以下是本Lab最主要的依赖

• Qemu-system-aarch64
• Qemu-user
• Python >= 3.7
• Make

以下是针对每个主流发行版的除去Docker以外的安装命令。

• Ubuntu/Debian

apt install qemu-system-aarch64 qemu-user python3 python3-pip python3-pexpect make gdb-multiarch

• Fedora

dnf install qemu-system qemu-user python3 python3-pip python3-pexpect make gdb

• Arch Linux

pacman -Sy qemu-user qemu-system-aarch64 python python-pip python-pexpect base-devel gdb

• Gentoo

USE="qemu_mmu_targets_aarch64 qemu_user_targets_aarch64" emerge -1v qemu python dev-python/pexpect python-pip make gdb qemu

• OpenSuse Tumbleweed

zypper install qemu qemu-linux-user python3 python3-pexpect make gdb

文档说明

各实验文档除开lab0为单独的实验内容，其他都包含了以下的几种习题，请根据下方的指示完成对应实验报告以及对应的编程题。

CI评分

在新实验中，我们特意准备了支持github actions以及gitlab ci的CI配置，你可以在你所使用的代码托管平台上自动运行脚本，为了确保你不会篡改预编译的.obj文件，我们会根据本仓库的主线的各个Lab中的filelist.mk(详细见贡献指南)的定义自动提取提交中所需要的文件与当前仓库主线的文件树进行合并，最终进行评分。

贡献指南

• 代码规范
• 工具链使用
• 如何提交新实验

代码规范

工具链使用

由于工具链版本问题，可能会导致在不同版本工具链编译的情况下导致在不同Release版本所链接的系统镜像无法正常工作的情况，请确保开发过程中使用与.devcontainer/Dockerfile即ubuntu 20.04.6的相同版本的交叉编译链进行预编译源文件，本仓库对所有Lab的正确答案的构建同样也开启了CI检查，如果发现在不同Release版本下无法通过，请检查你所使用的工具链是否符合预期。

如何提交新实验

对于新实验，我们使用两个文件进行定义实验规范，即filelist.mk以及scores.json，其中scores.json用于定义给分点以及对应的分数， filelist.mk则是提交文件列表，用于定义该Lab的提交文件，运行make submit后make会读取filelist.mk的文件定义，并按照一致的相对路径进行打包。 文件定义样例在Lab1中可以查看。

v25.03.1 更新内容

• 使用pexpect替换capturer.py
• 文档更新以及typo fix
• 删除gendeps.sh
• 容器与虚拟机镜像更新
• 更新代码讲解

Lab0：拆炸弹

• 简介
• Makefile 讲解
• 评分与提交规则

简介

在实验 0 中，你需要通过阅读汇编代码以及使用调试工具来拆除一个 二进制炸弹程序。本实验分为两个部分：第一部分介绍拆弹实验的基本知 识，包括 ARM 汇编语言、QEMU 模拟器、GDB 调试器的使用；第二部分 需要分析炸弹程序，推测正确的输入来使得炸弹程序能正常退出。

Makefile 讲解

• make bomb: 使用student-number.txt提供的学号，生成炸弹，如果您不是上海交通大学的学生可以自行随意填写。
• make qemu: 使用qemu-aarch64二进制模拟运行炸弹
• make qemu-gdb: 使用qemu-aarch64提供的gdb server进行调试
• make gdb: 使用gdb连接到qemu-aarch64的gdb-server进行调试

评分与提交规则

本实验你只需要提交ans.txt以及student-number.txt即可

基本知识

• 熟悉Aarch64汇编
• 使用 QEMU 运行炸弹程序
• QEMU 与 GDB

熟悉Aarch64汇编

AArch64 是 ARMv8 ISA 的 64 位执行状态。《ARM 指令集参考指 南》是一个帮助入门 ARM 语法的手册。在 ChCore 实验中，只 需要在提示下可以理解一些关键汇编和编写简单的汇编代码即可。 你可以在 Arm 的网站 上搜索具体的指令， 常备快速参考手册也有帮助，比如 这里。

使用 QEMU 运行炸弹程序

我们在实验中提供了bomb二进制文件，但该文件只能运行在基于 AArch64 的 Linux 中。通过 QEMU，我们可以在其他架构上模拟运行。同时，QEMU 可以结合 GDB 进行调试（如打印输出、单步调试等）

在lab0目录下，输入以下命令可以在 QEMU 中运行炸弹程序

[user@localhost Lab0]$ make qemu

炸弹程序的标准输出将会显示在 QEMU 中：

Type in your defuse password:

QEMU 与 GDB

在实验中，由于需要在 x86-64 平台上使用 GDB 来调试 AArch64 代 码，因此使用gdb-multiarch代替了普通的gdb。使用 GDB 调试的原理是， QEMU 可以启动一个 GDB 远程目标（remote target） （使用-s或-S参数 启动），QEMU 会在真正执行镜像中的指令前等待 GDB 客户端的连接。开 启远程目标之后，可以开启 GDB 进行调试，它会在某个端口上进行监听。

打开两个终端，在bomb-lab目录下，输入make qemu-gdb和make gdb命 令可以分别打开带有 GDB 调试的 QEMU 以及 GDB，在 GDB 中将会看 到如下的输出：

...
0x0000000000400540 in ?? ()
...
(gdb)

二进制炸弹拆除

我们在实验中提供了一个二进制炸弹程序bomb以及它的部分源码bomb.c。在 bomb.c 中，你可以看到一共有 6 个 phase。对每个 phase，bomb程序将从标准中输入中读取一行用户输入作为这一阶段的拆弹密码。若这一密码错误，炸弹程序将异常退出。你的任务是通过 GDB 以及阅读汇编代码，判断怎样的输入可以使得炸弹程序正常通过每个 phase。以下是一次失败尝试的例子：

[user@localhost lab0] $ make qemu
qemu -aarch64 bomb
Type in your defuse password:
1234
BOOM !!!

add symbol table from file "bomb"
(y or n) y
Reading symbols from bomb ...
(gdb) break main
Breakpoint 1 at 0x4006a4
(gdb) continue
Continuing.
Breakpoint 1, 0x00000000004006a4 in main ()
(gdb) disassemble
Dump of assembler code for function main:
0x0000000000400694 <+0>:stp0x0000000000400698 <+4>:mov
x29 , x30 , [sp , # -16]!
x29 , sp
0x000000000040069c <+8>:adrpx0 , 0x464000 <free_mem +64>
0x00000000004006a0 <+12>:addx0 , x0 , #0x778
=> 0x00000000004006a4 <+16>:bl0x413b20 <puts >
0x00000000004006a8 <+20>:bl0x400b10 <read_line >
0x00000000004006ac <+24>:bl0x400734 <phase_0 >
0x00000000004006b0 <+28>:bl0x400708 <phase_defused >
0x00000000004006b4 <+32>:bl0x400b10 <read_line >
0x00000000004006b8 <+36>:bl0x400760 <phase_1 >
0x00000000004006bc <+40>:bl0x400708 <phase_defused >
0x00000000004006c0 <+44>:bl0x400b10 <read_line >
0x00000000004006c4 <+48>:bl0x400788 <phase_2 >
0x00000000004006c8 <+52>:bl0x400708 <phase_defused >
0x00000000004006cc <+56>:bl0x400b10 <read_line >
0x00000000004006d0 <+60>:bl0x400800 <phase_3 >
0x00000000004006d4 <+64>:bl0x400708 <phase_defused >
0x00000000004006d8 <+68>:bl0x400b10 <read_line >
0x00000000004006dc <+72>:bl0x4009e4 <phase_4 >
0x00000000004006e0 <+76>:bl0x400708 <phase_defused >
0x00000000004006e4 <+80>:bl0x400b10 <read_line >
0x00000000004006e8 <+84>:bl0x400ac0 <phase_5 >
0x00000000004006ec <+88>:bl0x400708 <phase_defused >
0x00000000004006f0 <+92>:adrpx0 , 0x464000 <free_mem +64>
0x00000000004006f4 <+96>:addx0 , x0 , #0x798
0x00000000004006f8 <+100>:bl0x413b20 <puts >
0x00000000004006fc <+104>:movw0 , #0x0
0x0000000000400700 <+108>:ldpx29 , x30 , [sp], #16
0x0000000000400704 <+112>:ret
// #0
End of assembler dump.
(gdb) info registers x0
x0
0x464778
4605816
(gdb) x /s 0x464778
0x464778:
"Type in your defuse password!"

在破解后续阶段时，为了避免每次都需要输入先前阶段的拆弹密码，你可以通过重定向的方式来让炸弹程序读取文件中的密码：

[user@localhost lab0] $ make qemu < ans.txt
qemu -aarch64 bomb
Type in your defuse password:
5 phases to go
4 phases to go
3 phases to go
2 phases to go
1 phases to go
0 phases to go
Congrats! You have defused all phases!

Lab1: 机器启动

简介

本实验作为 ChCore 操作系统课程实验的第一个实验，分为三个部分。

1. RTFSC: 代码导读，由于是Lab1，我们主要注重于Chcore的构建系统，这部分没有习题。
2. 机器启动：介绍aarch64结构启动时的关键寄存器以及关键的启动函数。
3. 页表配置：介绍aarch64页表结构，以及针对树莓派3平台的内存布局编写页表配置。

本实验你可以在QEMU模拟器上完成实验，也可以在树莓派开发板上完成。 本实验代码包含了基础的ChCore 微内核操作系统，除了练习题相关的源码以外，其余部分通过预先编译的二进制格式提供。

完成本实验的练习题之后，你可以进入 ChCore shell，运行命令或执行程序。 例如，可以在 shell 中输入 hello_world.bin 运行一个简单的用户态程序; 输入ls 查看目录内容。

 ______     __  __     ______     __  __     ______     __         __        
/\  ___\   /\ \_\ \   /\  ___\   /\ \_\ \   /\  ___\   /\ \       /\ \       
\ \ \____  \ \  __ \  \ \___  \  \ \  __ \  \ \  __\   \ \ \____  \ \ \____  
 \ \_____\  \ \_\ \_\  \/\_____\  \ \_\ \_\  \ \_____\  \ \_____\  \ \_____\ 
  \/_____/   \/_/\/_/   \/_____/   \/_/\/_/   \/_____/   \/_____/   \/_____/ 


Welcome to ChCore shell!
$ 

RTFSC(1)

Lab1的代码很多，在第一部分的代码架构解析的部分我们主要来讲解内核镜像是如何构建产生，以及评分基础设施是如何工作的。

• 构建系统
  • Makefile
  • CMake
    • 镜像定义生成
    • 定义多态设计
    • 镜像编译
• QEMU
• 评分系统

构建系统

Makefile

原有的Chcore的构建系统仅围绕着Scripts/chbuild这个脚本进行构建，但是由于OS Course Lab需要增加评分的设施， 我们为此在chbuild之外添加了Makefile的基础结构，以下为Lab1/Makefile的内容

LAB := 1
include $(CURDIR)/../Scripts/lab.mk

注意到我们我们仅仅我们定义了Lab的标识符，然后使用include将上层Scripts/lab.mk导入到当前的Makefile中。

# Note that this file should be included directly in every Makefile inside each lab's folder.
# This sets up the environment variable for lab's Makefile.

ifndef LABROOT
LABROOT := $(CURDIR)/..
endif

SCRIPTS := $(LABROOT)/Scripts

ifeq (,$(LAB))
$(error LAB is not set!)
endif


LABDIR  := $(LABROOT)/Lab$(LAB)
SCRIPTS := $(LABROOT)/Scripts
GRADER  ?= $(SCRIPTS)/grader.sh

# Toolchain Configuration
ifeq ($(shell command -v gdb-multiarch 2> /dev/null),)
# Default to gdb if gdb-multiarch is not available
# This is only the case on debian-based distros
    GDB := gdb
else
    GDB := gdb-multiarch
endif

DOCKER ?= docker
DOCKER_IMAGE ?= ipads/oslab:25.03
ifeq (,$(wildcard /docker.env))
DOCKER_RUN ?= 
else
DOCKER_RUN ?= $(DOCKER) run -it --rm \
        -e SCRIPTS=$(SCRIPTS) \
        -e LABROOT=$(LABROOT) \
        -e LABDIR=$(LABDIR) \
        -e TIMEOUT=$(TIMEOUT) \
        -e LAB=$(LAB) \
        -u $(shell id -u $(USER)):$(shell id -g $(USER)) \
        -v $(LABROOT):$(LABROOT) -w $(CURDIR) \
        --security-opt=seccomp:unconfined \
        --platform=linux/amd64 \
        $(DOCKER_IMAGE)
endif
QEMU-SYS ?= qemu-system-aarch64
QEMU-USER ?= qemu-aarch64

# Timeout for grading
TIMEOUT ?= 10

ifeq ($(shell test $(LAB) -eq 0; echo $$?),1)
    QEMU := $(QEMU-SYS)
    ifeq ($(shell test $(LAB) -gt 4; echo $$?),0)
        include $(LABROOT)/Scripts/extras/lab$(LAB).mk
    else
        include $(LABROOT)/Scripts/kernel.mk
    endif
    include $(LABROOT)/Scripts/submit.mk
else
    QEMU := $(QEMU-USER)
endif

而lab.mk主要针对Lab环境进行检查，同时定义一些关键的变量，最终根据当前的$(LAB)的序号，再去导入不同的定义，在此处由于 我们的$(LAB)变量为1，所以我们真正使用的Makefile定义为kernel.mk

V ?= 0
Q := @
GRADER_V :=
ifeq ($(V), 1)
    Q :=
endif

ifeq ($(V), 2)
    Q :=
    GRADER_V := -v
endif

BUILDDIR := $(LABDIR)/build
KERNEL_IMG := $(BUILDDIR)/kernel.img
_QEMU := $(SCRIPTS)/qemu_wrapper.sh $(QEMU)
QEMU_GDB_PORT := 1234
QEMU_OPTS := -machine raspi3b -nographic -serial mon:stdio -m size=1G -kernel $(KERNEL_IMG)
CHBUILD := $(SCRIPTS)/chbuild
SERIAL := $(shell LC_ALL=C tr -dc A-Za-z0-9 </dev/urandom | head -c 13; echo)

export LABROOT LABDIR SCRIPTS LAB TIMEOUT

all: build

defconfig:
    $(Q)$(CHBUILD) defconfig

build:
    $(Q)test -f $(LABDIR)/.config || $(CHBUILD) defconfig
    $(Q)$(CHBUILD) build
    $(Q)find -L $(LABDIR) -path */compile_commands.json \
       ! -path $(LABDIR)/compile_commands.json -print \
       | $(SCRIPTS)/merge_compile_commands.py

clean:
    $(Q)$(CHBUILD) clean
    $(Q)find -L $(LABDIR) -path */compile_commands.json -exec rm {} \;

distclean:
    $(Q)$(CHBUILD) distclean

qemu: build
    $(Q)$(_QEMU) $(QEMU_OPTS)

qemu-grade:
    $(SCRIPTS)/change_serial $(KERNEL_IMG) $(SERIAL)
    $(Q)$(_QEMU) $(QEMU_OPTS)

qemu-gdb: build
    $(Q)echo "[QEMU] Waiting for GDB Connection"
    $(Q)$(_QEMU) -S -gdb tcp::$(QEMU_GDB_PORT) $(QEMU_OPTS)

gdb:
    $(Q)$(GDB) --nx -x $(SCRIPTS)/gdb/gdbinit

grade:  
    $(Q)$(MAKE) distclean &> /dev/null
    $(Q)(test -f ${LABDIR}/.config && cp ${LABDIR}/.config ${LABDIR}/.config.bak) || :
    $(Q)$(MAKE) build
    $(Q)$(DOCKER_RUN) $(GRADER) -t $(TIMEOUT) -f $(LABDIR)/scores.json $(GRADER_V) -s $(SERIAL) make SERIAL=$(SERIAL) qemu-grade
    $(Q)(test -f ${LABDIR}/.config.bak && cp ${LABDIR}/.config.bak ${LABDIR}/.config && rm .config.bak) || :

.PHONY: qemu qemu-gdb gdb defconfig build clean distclean grade all

这里简述一下用法，其中我们定义了一个变量V，当我们运行例如make V=1时会将Q的定义重新设置，Q的目的主要是为了做 字符串的拼接。

当我们在Lab1运行make build，其就会转到kernel.mk的build这个规则下，此时Make会调用cmake完成进一步的构建

CMake

镜像定义生成

当我们运行make build之后，我们便进到了chbuild脚本中了，当开始时我们会使用chbuild defconfig这个bash函数调用cmake的其他脚本来生成镜像配置文件.config，由于我们默认使用raspi3配置，我们会将Scripts/defconfigs/raspi3.config复制到当前Lab的根目录下，这个是chcore的平台定义文件，之后则会调用Scripts/build/cmake添加到Lab当中，之后则会运行_config_default这个函数主要负责递归读入Lab目录下的config.cmake文件并按照默认设置将平台无关的镜像配置文件，之后运行_sync_config_with_cache将镜像定义设置.config同步到CMakeCache中进行缓存，并返回到Make当中，之后Make继续运行chbuild build，按照.config定义进行构建镜像脚本。

defconfig() {
    if [ -d $cmake_build_dir ]; then
        _echo_err "There exists a build directory, please run \`$clean_command\` first"
        exit 1
    fi

    if [ -z "$1" ]; then
        plat="raspi3"
    else
        plat="$1"
    fi

    _echo_info "Generating default config file for \`$plat\` platform..."
    cp $defconfig_dir/${plat}.config $config_file
    _config_default
    _sync_config_with_cache
    _echo_succ "Default config written to \`$config_file\` file."
}

_config_default() {
    _echo_info "Configuring CMake..."
    cmake -B $cmake_build_dir -C $cmake_init_cache_default
}

_sync_config_with_cache() {
    cmake -N -B $cmake_build_dir -C $cmake_init_cache_dump >/dev/null
}

定义多态设计

Chcore通过config.cmake这个文件来定义规则的，但是我们单独去看的时候它使用了chcore_config这个宏，但是这个指令是不存在，实际上 所有的config.cmake也是通过include指令来导入的，所以chbuild的每个指令都是去定义了cmake的chcore_config来执行不同的行为。 大致的过程图如下, DumpConfig.cmake主要是将chcore_config中的内容进行提取，并全部添加到defconfig生成的.conifg文件中，而CMakeList.txt构建时的chcore_config则是根据.config中的内容定向的配置子项目的编译选项。如果感兴趣你可以阅读Scripts/build/cmake/下的cmake脚本文件。

镜像编译

Chcore的编译是从CMakelists.txt的上层开始的，总的来说经过了如下的编译过程

首先上层的CMakeLists.txt会根据.config的内容构造_cache_args以及_common_args分别对应的是下层CMake的子项目的CMake构建参数以及变量参数，然后 创建kernel-incclean用于删除kernel.img构建时的副产物，对应到最上层chbuild clean以及make clean时的清理选项，然后会递归进入kernel这个子项目。 进入子项目后，CMake 首先会去导入KernelTools.cmake这个脚本去定义一些关键函数以及关键宏，同时会定义关键的工具链选项以及包含路径，最后再逐步地将每个子目录的CMakeLists.txt进行导入，对于源文件进行编译，对于预编译文件则是按照调试选项对应添加.dbg.obj或者是.obj文件进入文件列表，之后则是将user/procmgr这个文件利用incbin.tpl.S去生成对应的二进制汇编进行编译，最后使用linker.tpl.ld所生成的linker.ld的linker script进行链接最后得到kernel.img的镜像。

QEMU

当kernel构建完成后，我们将使用qemu-system-aarch64进行模拟，当我们运行make qemu或者是make qemu-gdb时我们会进入如下的规则，

    Q :=
    GRADER_V := -v
endif

       ! -path $(LABDIR)/compile_commands.json -print \
       | $(SCRIPTS)/merge_compile_commands.py

clean:
    $(Q)$(CHBUILD) clean
    $(Q)find -L $(LABDIR) -path */compile_commands.json -exec rm {} \;

此时Make 会将QEMU_OPTS以及可能QEMU_GDB_PORT进行字符串的拼接，然后将参数传入qemu_wrapper.sh转到qemu程序中。

评分系统

我们使用make grade时会将TIMEOUT参数以及评分定义scores.json以及被评分的指令传入grader.sh，

#!/usr/bin/env bash

if [[ -z $LABROOT ]]; then
    echo "Please set the LABROOT environment variable to the root directory of your project. (Makefile)"
    exit 1
fi


SCRIPTS=${LABROOT}/Scripts

. ${SCRIPTS}/shellenv.sh

info "Grading lab ${LAB} ...(may take ${TIMEOUT} seconds)"

bold "==========================================="
${SCRIPTS}/expect.py $@
score=$?

if [[ $score -eq 255 ]]; then
    error "Something went wrong. Please check the output of your program"
    exit 0
fi

info "Score: ${score}/100"
bold "==========================================="

if [[ $score -lt 100 ]]; then
    exit $?
else
    exit 0
fi

在备份.config之后，其会调用capturer.py的内容，去动态捕捉命令的输出，并按照顺序与scores.json的内容进行比对， 从而计算评分，如果提前退出或者接收到SIGINT信号，则整个程序会直接退出并返回0分。

内核启动

• 树莓派启动过程
• 启动 CPU 0 号核
• 切换异常级别
• 跳转到第一行 C 代码
• 初始化串口输出
• 启用 MMU

树莓派启动过程

在树莓派 3B+ 真机上，通过 SD 卡启动时，上电后会运行 ROM 中的特定固件，接着加载并运行 SD 卡上的 bootcode.bin 和 start.elf，后者进而根据 config.txt 中的配置，加载指定的 kernel 映像文件（纯 binary 格式，通常名为 kernel8.img）到内存的 0x80000 位置并跳转到该地址开始执行。

而在 QEMU 模拟的 raspi3b（旧版 QEMU 为 raspi3）机器上，则可以通过 -kernel 参数直接指定 ELF 格式的 kernel 映像文件，进而直接启动到 ELF 头部中指定的入口地址，即 _start 函数（实际上也在 0x80000，因为 ChCore 通过 linker script 强制指定了该函数在 ELF 中的位置，如有兴趣请参考附录）。

启动 CPU 0 号核

_start 函数（位于 kernel/arch/aarch64/boot/raspi3/init/start.S）是 ChCore 内核启动时执行的第一块代码。由于 QEMU 在模拟机器启动时会同时开启 4 个 CPU 核心，于是 4 个核会同时开始执行 _start 函数。而在内核的初始化过程中，我们通常需要首先让其中一个核进入初始化流程，待进行了一些基本的初始化后，再让其他核继续执行。

切换异常级别

AArch64 架构中，特权级被称为异常级别（Exception Level，EL），四个异常级别分别为 EL0、EL1、EL2、EL3，其中 EL3 为最高异常级别，常用于安全监控器（Secure Monitor），EL2 其次，常用于虚拟机监控器（Hypervisor），EL1 是内核常用的异常级别，也就是通常所说的内核态，EL0 是最低异常级别，也就是通常所说的用户态。

QEMU raspi3b 机器启动时，CPU 异常级别为 EL3，我们需要在启动代码中将异常级别降为 EL1，也就是进入内核态。具体地，这件事是在 arm64_elX_to_el1 函数（位于 kernel/arch/aarch64/boot/raspi3/init/tools.S）中完成的。

为了使 arm64_elX_to_el1 函数具有通用性，我们没有直接写死从 EL3 降至 EL1 的逻辑，而是首先判断当前所在的异常级别，并根据当前异常级别的不同，跳转到相应的代码执行。

BEGIN_FUNC(arm64_elX_to_el1)
	/* LAB 1 TODO 1 BEGIN */
	/* BLANK BEGIN */
	/* BLANK END */
	/* LAB 1 TODO 1 END */

	// Check the current exception level.
	cmp x9, CURRENTEL_EL1
	beq .Ltarget
	cmp x9, CURRENTEL_EL2
	beq .Lin_el2
	// Otherwise, we are in EL3.

	// Set EL2 to 64bit and enable the HVC instruction.
	mrs x9, scr_el3
	mov x10, SCR_EL3_NS | SCR_EL3_HCE | SCR_EL3_RW
	orr x9, x9, x10
	msr scr_el3, x9

	// Set the return address and exception level.
	/* LAB 1 TODO 2 BEGIN */
	/* BLANK BEGIN */
	/* BLANK END */
	/* LAB 1 TODO 2 END */

.Lin_el2:
	// Disable EL1 timer traps and the timer offset.
	mrs x9, cnthctl_el2
	orr x9, x9, CNTHCTL_EL2_EL1PCEN | CNTHCTL_EL2_EL1PCTEN
	msr cnthctl_el2, x9
	msr cntvoff_el2, xzr

	// Disable stage 2 translations.
	msr vttbr_el2, xzr

	// Disable EL2 coprocessor traps.
	mov x9, CPTR_EL2_RES1
	msr cptr_el2, x9

	// Disable EL1 FPU traps.
	mov x9, CPACR_EL1_FPEN
	msr cpacr_el1, x9

	// Check whether the GIC system registers are supported.
	mrs x9, id_aa64pfr0_el1
	and x9, x9, ID_AA64PFR0_EL1_GIC
	cbz x9, .Lno_gic_sr

	// Enable the GIC system registers in EL2, and allow their use in EL1.
	mrs x9, ICC_SRE_EL2
	mov x10, ICC_SRE_EL2_ENABLE | ICC_SRE_EL2_SRE
	orr x9, x9, x10
	msr ICC_SRE_EL2, x9

	// Disable the GIC virtual CPU interface.
	msr ICH_HCR_EL2, xzr

.Lno_gic_sr:
	// Set EL1 to 64bit.
	mov x9, HCR_EL2_RW
	msr hcr_el2, x9

	// Set the return address and exception level.
	adr x9, .Ltarget
	msr elr_el2, x9
	mov x9, SPSR_ELX_DAIF | SPSR_ELX_EL1H
	msr spsr_el2, x9

	isb
	eret

.Ltarget:
	ret
END_FUNC(arm64_elX_to_el1)

eret指令可用于从高异常级别跳到更低的异常级别，在执行它之前我们需要设置 设置 elr_elx（异常链接寄存器）和 spsr_elx（保存的程序状态寄存器），分别控制eret执行后的指令地址（PC）和程序状态（包括异常返回后的异常级别）。

练习完成后，可使用 GDB 跟踪内核代码的执行过程，由于此时不会有任何输出，可通过是否正确从 arm64_elX_to_el1 函数返回到 _start 来判断代码的正确性。

跳转到第一行 C 代码

降低异常级别到 EL1 后，我们准备从汇编跳转到 C 代码，在此之前我们先设置栈（SP）。因此，_start 函数在执行 arm64_elX_to_el1 后，即设置内核启动阶段的栈，并跳转到第一个 C 函数 init_c。

BEGIN_FUNC(_start)
    mrs	x8, mpidr_el1
    and	x8, x8,	#0xFF
    cbz	x8, primary

    /* Wait for bss clear */
wait_for_bss_clear:
    adr	x0, clear_bss_flag
    ldr	x1, [x0]
    cmp     x1, #0
    bne	wait_for_bss_clear

    /* Set cntkctl_el1 to enable cntvct_el0.
         * Enable it when you need to get current tick
         * at EL0, e.g. Running aarch64 ROS2 demos
    mov	x10, 0b11
    msr	cntkctl_el1, x10 */

    /* Turn to el1 from other exception levels. */
    bl 	arm64_elX_to_el1

    /* Prepare stack pointer and jump to C. */
    mov	x1, #INIT_STACK_SIZE
    mul	x1, x8, x1
    adr 	x0, boot_cpu_stack
    add	x0, x0, x1
    add	x0, x0, #INIT_STACK_SIZE
    mov	sp, x0

wait_until_smp_enabled:
    /* CPU ID should be stored in x8 from the first line */
    mov	x1, #8
    mul	x2, x8, x1
    ldr	x1, =secondary_boot_flag
    add	x1, x1, x2
    ldr	x3, [x1]
    cbz	x3, wait_until_smp_enabled

    /* Set CPU id */
    mov	x0, x8
    b 	secondary_init_c

    /* Should never be here */
    b	.

primary:

    /* Turn to el1 from other exception levels. */
    bl 	arm64_elX_to_el1

    /* Prepare stack pointer and jump to C. */
    adr 	x0, boot_cpu_stack
    add 	x0, x0, #INIT_STACK_SIZE
    mov 	sp, x0

    b 	init_c

    /* Should never be here */
    b	.
END_FUNC(_start)

进入 init_c 函数后，第一件事首先通过 clear_bss 函数清零了 .bss 段，该段用于存储未初始化的全局变量和静态变量（具体请参考附录）。

初始化串口输出

到目前为止我们仍然只能通过 GDB 追踪内核的执行过程，而无法看到任何输出，这无疑是对我们写操作系统的积极性的一种打击。因此在 init_c 中，我们启用树莓派的 UART 串口，从而能够输出字符。

在 kernel/arch/aarch64/boot/raspi3/peripherals/uart.c 已经给出了 early_uart_init 和 early_uart_send 函数，分别用于初始化 UART 和发送单个字符（也就是输出字符）。

void uart_send_string(char *str)
{
        /* LAB 1 TODO 3 BEGIN */
        /* BLANK BEGIN */
        /* BLANK END */
        /* LAB 1 TODO 3 END */
}

启用 MMU

在内核的启动阶段，还需要配置启动页表（init_kernel_pt 函数），并启用 MMU（el1_mmu_activate 函数），使可以通过虚拟地址访问内存，从而为之后跳转到高地址作准备（内核通常运行在虚拟地址空间 0xffffff0000000000 之后的高地址）。

关于配置启动页表的内容由于包含关于页表的细节，将在本实验下一部分实现，目前直接启用 MMU。

在 EL1 异常级别启用 MMU 是通过配置系统寄存器 sctlr_el1 实现的（Arm Architecture Reference Manual D13.2.118）。具体需要配置的字段主要包括：

• 是否启用 MMU（M 字段）
• 是否启用对齐检查（A SA0 SA nAA 字段）
• 是否启用指令和数据缓存（C I 字段）

由于没有配置启动页表，在启用 MMU 后，内核会立即发生地址翻译错误（Translation Fault），进而尝试跳转到异常处理函数（Exception Handler）， 该异常处理函数的地址为异常向量表基地址（vbar_el1 寄存器）加上 0x200。 此时我们没有设置异常向量表（vbar_el1 寄存器的值是0），因此执行流会来到 0x200 地址，此处的代码为非法指令，会再次触发异常并跳转到 0x200 地址。 使用 GDB 调试，在 GDB 中输入 continue 后，待内核输出停止后，按 Ctrl-C，可以观察到内核在 0x200 处无限循环。

页表映射

• AArch64 地址翻译
• 配置内核启动页表

AArch64 地址翻译

在配置内核启动页表前，我们首先回顾实验涉及到的体系结构知识。这部分内容课堂上已经学习过，如果你已熟练掌握则可以直接跳过这里的介绍（但不要跳过思考题）。

在 AArch64 架构的 EL1 异常级别存在两个页表基址寄存器：ttbr0_el1¹ 和 ttbr1_el1²，分别用作虚拟地址空间低地址和高地址的翻译。那么什么地址范围称为“低地址”，什么地址范围称为“高地址”呢？这由 tcr_el1 翻译控制寄存器³控制，该寄存器提供了丰富的可配置性，可决定 64 位虚拟地址的高多少位为 0 时，使用 ttbr0_el1 指向的页表进行翻译，高多少位为 1 时，使用 ttbr1_el1 指向的页表进行翻译⁴。一般情况下，我们会将 tcr_el1 配置为高低地址各有 48 位的地址范围，即，0x0000_0000_0000_0000～0x0000_ffff_ffff_ffff 为低地址，0xffff_0000_0000_0000～0xffff_ffff_ffff_ffff 为高地址。

了解了如何决定使用 ttbr0_el1 还是 ttbr1_el1 指向的页表，再来看地址翻译过程如何进行。通常我们会将系统配置为使用 4KB 翻译粒度、4 级页表（L0 到 L3），同时在 L1 和 L2 页表中分别允许映射 2MB 和 1GB 大页（或称为块）⁵，因此地址翻译的过程如下图所示：

其中，当映射为 1GB 块或 2MB 块时，图中 L2、L3 索引或 L3 索引的位置和低 12 位共同组成块内偏移。

每一级的每一个页表占用一个 4KB 物理页，称为页表页（Page Table Page），其中有 512 个条目，每个条目占 64 位。AArch64 中，页表条目称为描述符（descriptor）⁶，最低位（bit[0]）为 1 时，描述符有效，否则无效。有效描述符有两种类型，一种指向下一级页表（称为表描述符），另一种指向物理块（大页）或物理页（称为块描述符或页描述符）。在上面所说的地址翻译配置下，描述符结构如下（“Output address”在这里即物理地址，一些地方称为物理页帧号（Page Frame Number，PFN））：

• L0、L1、L2 页表描述符

• L3 页表描述符

页表描述符中除了包含下一级页表或物理页/块的地址，还包含对内存访问进行控制的属性（attribute）。这里涉及到太多细节，本文档限于篇幅只介绍最常用的几个页/块描述符中的属性字段：

配置内核启动页表

有了关于页表配置的前置知识，我们终于可以开始配置内核的启动页表了。

操作系统内核通常运行在虚拟内存的高地址（如前所述，0xffff_0000_0000_0000 之后的虚拟地址）。通过对内核页表的配置，将虚拟内存高地址映射到内核实际所在的物理内存，在执行内核代码时，PC 寄存器的值是高地址，对全局变量、栈等的访问都使用高地址。在内核运行时，除了需要访问内核代码和数据等，往往还需要能够对任意物理内存和外设内存（MMIO）进行读写，这种读写同样通过高地址进行。

因此，在内核启动时，首先需要对内核自身、其余可用物理内存和外设内存进行虚拟地址映射，最简单的映射方式是一对一的映射，即将虚拟地址 0xffff_0000_0000_0000 + addr 映射到 addr。需要注意的是，在 ChCore 实验中我们使用了 0xffff_ff00_0000_0000 作为内核虚拟地址的开始（注意开头 f 数量的区别），不过这不影响我们对知识点的理解。

在树莓派 3B+ 机器上，物理地址空间分布如下¹⁰：

现在将目光转移到 kernel/arch/aarch64/boot/raspi3/init/mmu.c 文件，我们需要在 init_kernel_pt 为内核配置从 0x00000000 到 0x80000000（0x40000000 后的 1G，ChCore 只需使用这部分地址中的本地外设）的映射，其中 0x00000000 到 0x3f000000 映射为 normal memory，0x3f000000 到 0x80000000映射为 device memory，其中 0x00000000 到 0x40000000 以 2MB 块粒度映射，0x40000000 到 0x80000000 以 1GB 块粒度映射。

完成 init_kernel_pt 函数后，ChCore 内核便可以在 el1_mmu_activate 中将 boot_ttbr1_l0 等物理地址写入实际寄存器(如 ttbr1_el1 )，随后启用 MMU 后继续执行，并通过 start_kernel 跳转到高地址，进而跳转到内核的 main 函数（位于 kernel/arch/aarch64/main.c, 尚未发布，以 binary 提供）。

Lab 2：内存管理

本实验主要目的在于让同学们熟悉内核启动过程中对内存的初始化和内核启动后对物理内存和页表的管理，包括三个部分。

1. 物理内存管理: 理解并完成伙伴系统以及SLAB系统
2. 虚拟页表管理: 深入理解页表分配机制以及页表项权限机制，并完成页表分配函数。
3. 缺页异常处理: 理解aarch64架构下的异常处理机制，并按照页表项的配置完成按需分配以及写时拷贝的缺页管理设置。

跟先前的Lab相同，本实验代码包含了基础的 ChCore 操作系统镜像，除了练习题相关部分的源码以外（指明需要阅读的代码），其余部分通过二进制格式提供。 在正确完成本实验的练习题之后，你可以在树莓派3B+QEMU或开发板上进入 ChCore shell。

物理内存管理

• 伙伴系统
• SLAB分配器
• Kmalloc

伙伴系统

内核初始化过程中，需要对内存管理模块进行初始化（mm_init 函数），首先需要把物理内存管起来，从而使内核代码可以动态地分配内存。

ChCore 使用伙伴系统（buddy system）¹对物理页进行管理，在 mm_init 中对伙伴系统进行了初始化。为了使物理内存的管理可扩展，ChCore 在 mm_init 的开头首先调用平台特定的 parse_mem_map 函数，该函数解析并返回了可用物理内存区域，然后再对各可用物理内存区域初始化伙伴系统。

伙伴系统中的每个内存块都有一个阶（order）表示大小，阶是从 0 到指定上限 BUDDY_MAX_ORDER 的整数。一个 $n$ 阶的块的大小为 $2^n\times PAGE\mathrm{\_}SIZE$，因此这些内存块的大小正好是比它小一个阶的内存块的大小的两倍。内存块的大小是 2 次幂对齐，使地址计算变得简单。当一个较大的内存块被分割时，它被分成两个较小的内存块，这两个小内存块相互成为唯一的伙伴。一个分割的内存块也只能与它唯一的伙伴块进行合并（合并成他们分割前的块）。

ChCore 中每个由伙伴系统管理的内存区域称为一个 struct phys_mem_pool，该结构体中包含物理页元信息的起始地址（page_metadata）、伙伴系统各阶内存块的空闲链表（free_lists）等。

SLAB分配器

我们希望通过基于伙伴系统的物理内存管理，在内核中进行动态内存分配，也就是可以使用 kmalloc 函数（对应用户态的 malloc）。ChCore 的 kmalloc 对于较小的内存分配需求采用 SLAB 分配器²，对于较大的分配需求则直接从伙伴系统中分配物理页。动态分配出的物理页被转换为内核虚拟地址（Kernel Virtual Address，KVA），也就是在 LAB 1 中我们映射的 0xffff_ff00_0000_0000 之后的地址。我们在练习题 1 中已经实现了伙伴系统，接下来让我们实现 SLAB 分配器吧。

Kmalloc

有了伙伴系统和 SLAB 分配器，就可以实现 kmalloc 了。

页表管理

在LAB 1 中我们已经详细介绍了 AArch64 的地址翻译过程，并介绍了各级页表和不同类型的页表描述符，最后在内核启动阶段配置了一个粗粒度的启动页表。现在，我们需要为用户态应用程序准备一个更细粒度的页表实现，提供映射、取消映射、查询等功能。

缺页异常处理

缺页异常（page fault）是操作系统实现延迟内存分配的重要技术手段。当处理器发生缺页异常时，它会将发生错误的虚拟地址存储于 FAR_ELx 寄存器中，并触发相应的异常处理流程。ChCore 对该异常的处理最终实现在 kernel/arch/aarch64/irq/pgfault.c 中的 do_page_fault 函数。本次实验暂时不涉及前面的异常初步处理及转发相关内容，我们仅需要关注操作系统是如何处缺页异常的。

在 ChCore 中，一个进程的虚拟地址空间由多段“虚拟地址区域”（VMR，又称 VMA）组成，一段 VMR 记录了这段虚拟地址对应的“物理内存对象”（PMO），而 PMO 中则记录了物理地址相关信息。因此，想要处理缺页异常，首先需要找到当前进程发生页错误的虚拟地址所处的 VMR，进而才能得知其对应的物理地址，从而在页表中完成映射。

缺页处理主要针对 PMO_SHM 和 PMO_ANONYM 类型的 PMO，这两种 PMO 的物理页是在访问时按需分配的。缺页处理逻辑为首先尝试检查 PMO 中当前 fault 地址对应的物理页是否存在（通过 get_page_from_pmo 函数尝试获取 PMO 中 offset 对应的物理页）。若对应物理页未分配，则需要分配一个新的物理页，再将页记录到 PMO 中，并增加页表映射。若对应物理页已分配，则只需要修改页表映射即可。

Lab 3：进程与线程

用户进程是操作系统对在用户模式运行中的程序的抽象。在Lab 1 和Lab 2 中，已经完成了内核的启动和物理内存的管理，以及一个可供用户进程使用的页表实现。现在，我们将一步一步支持用户态程序的运行。 本实验包括五个部分：

1. RTFSC(2): 代码导读，了解Chcore微内核的核心机制以及用户态和内核态是如何进行交互的。
2. 线程管理: 支持创建第一个用户态进程和线程，分析代码如何从内核态切换到用户态。
3. 异常处理: 完善异常处理流程，为系统添加必要的异常处理的支持。
4. 系统调用：正确处理部分系统调用，保证用户程序的正常输出。
5. 用户态程序编写：编写一个简单用户程序，使用提供的 ChCore libc 进行编译，并加载至内核镜像中。

工具链准备

从Lab3开始我们开放了用户态的一些代码，你需要使用如下的命令下载libc.

git submodule update --init --recursive

RTFSC (3)

本次代码导读主要聚焦从main函数开始自上而下讲解Lab2 Lab3内核态的资源管理机制以及用户态和内核态的互相调用

内核初始化

/*
 * @boot_flag is boot flag addresses for smp;
 * @info is now only used as board_revision for rpi4.
 */
void main(paddr_t boot_flag, void *info)
{
    u32 ret = 0;

    /* Init big kernel lock */
    ret = lock_init(&big_kernel_lock);
    kinfo("[ChCore] lock init finished\n");
    BUG_ON(ret != 0);

    /* Init uart: no need to init the uart again */
    uart_init();
    kinfo("[ChCore] uart init finished\n");

    /* Init per_cpu info */
    init_per_cpu_info(0);
    kinfo("[ChCore] per-CPU info init finished\n");

    /* Init mm */
    mm_init(info);

    kinfo("[ChCore] mm init finished\n");

    void lab2_test_buddy(void);
    lab2_test_buddy();
    void lab2_test_kmalloc(void);
    lab2_test_kmalloc();
    void lab2_test_page_table(void);
    lab2_test_page_table();
#if defined(CHCORE_KERNEL_PM_USAGE_TEST)
    void lab2_test_pm_usage(void);
    lab2_test_pm_usage();
#endif
    /* Mapping KSTACK into kernel page table. */
    map_range_in_pgtbl_kernel((void*)((unsigned long)boot_ttbr1_l0 + KBASE), 
            KSTACKx_ADDR(0),
            (unsigned long)(cpu_stacks[0]) - KBASE, 
            CPU_STACK_SIZE, VMR_READ | VMR_WRITE);

    /* Init exception vector */
    arch_interrupt_init();
    timer_init();
    kinfo("[ChCore] interrupt init finished\n");

    /* Enable PMU by setting PMCR_EL0 register */
    pmu_init();
    kinfo("[ChCore] pmu init finished\n");

    /* Init scheduler with specified policy */
#if defined(CHCORE_KERNEL_SCHED_PBFIFO)
    sched_init(&pbfifo);
#elif defined(CHCORE_KERNEL_RT)
    sched_init(&pbrr);
#else
    sched_init(&rr);
#endif
    kinfo("[ChCore] sched init finished\n");

    init_fpu_owner_locks();

    /* Other cores are busy looping on the boot_flag, wake up those cores */
    enable_smp_cores(boot_flag);
    kinfo("[ChCore] boot multicore finished\n");

#ifdef CHCORE_KERNEL_TEST
    kinfo("[ChCore] kernel tests start\n");
    run_test();
    kinfo("[ChCore] kernel tests done\n");
#endif /* CHCORE_KERNEL_TEST */

#if FPU_SAVING_MODE == LAZY_FPU_MODE
    disable_fpu_usage();
#endif

    /* Create initial thread here, which use the `init.bin` */
    create_root_thread();
    kinfo("[ChCore] create initial thread done\n");
    kinfo("End of Kernel Checkpoints: %s\n", serial_number);

    /* Leave the scheduler to do its job */
    sched();

    /* Context switch to the picked thread */

以下为Chcore内核初始化到运行第一个用户线程的主要流程图

我们在Lab2中主要完成mm_init以及内存管理器与vmspace和pmo的互联，现在我们再从第一个线程创建的数据流来梳理并分析 Chcore微内核的资源管理模式。

内核对象管理

在Chcore中所有的系统资源都叫做object（对象），用面向对象的方法进行理解的话，object即为不同内核对象例如vmspace, pmo, thread(等等)的父类， Chcore通过能力组机制管理所有的系统资源，能力组本身只是一个包含指向object的指针的数组

1. 所有进程/线程都有一个独立的能力组，拥有一个全局唯一ID (Badge)
2. 所有对象（包括进程或能力组本身）都属于一个或多个能力组当中，也就是说子进程与线程将属于父进程的能力组当中，在某个能力组的对象拥有一个能力组内的能力ID(cap)。
3. 对象可以共享，即单个对象可以在多个能力组中共存，同时在不同cap_group中可以有不同的cap
4. 对所有对象的取用和返还都使用引用计数进行追踪。当引用计数为0后，当内核垃圾回收器唤醒后，会自动回收.
5. 能力组内的能力具有权限，表明该能力是否能被共享(CAP_RIGHT_COPY)以及是否能被删除(CAP_RIGHT_REVOKE)

struct object {
        u64 type;
        u64 size;
        /* Link all slots point to this object */
        struct list_head copies_head;
        /* Currently only protect copies list */
        struct lock copies_lock;
        /*
         * refcount is added when a slot points to it and when get_object is
         * called. Object is freed when it reaches 0.
         */
        volatile unsigned long refcount;

        /*
         * opaque marks the end of this struct and the real object will be
         * stored here. Now its address will be 8-byte aligned.
         */
        u64 opaque[];
};
const obj_deinit_func obj_deinit_tbl[TYPE_NR] = {
        [0 ... TYPE_NR - 1] = NULL,
        [TYPE_CAP_GROUP] = cap_group_deinit,
        [TYPE_THREAD] = thread_deinit,
        [TYPE_CONNECTION] = connection_deinit,
        [TYPE_NOTIFICATION] = notification_deinit,
        [TYPE_IRQ] = irq_deinit,
        [TYPE_PMO] = pmo_deinit,
        [TYPE_VMSPACE] = vmspace_deinit,
#ifdef CHCORE_OPENTRUSTEE
        [TYPE_CHANNEL] = channel_deinit,
        [TYPE_MSG_HDL] = msg_hdl_deinit,
#endif /* CHCORE_OPENTRUSTEE */
        [TYPE_PTRACE] = ptrace_deinit
};
void *obj_alloc(u64 type, u64 size)
{
        u64 total_size;
        struct object *object;

        total_size = sizeof(*object) + size;
        object = kzalloc(total_size);
        if (!object)
                return NULL;

        object->type = type;
        object->size = size;
        object->refcount = 0;

        /*
         * If the cap of the object is copied, then the copied cap (slot) is
         * stored in such a list.
         */
        init_list_head(&object->copies_head);
        lock_init(&object->copies_lock);

        return object->opaque;
}
void __free_object(struct object *object)
{
#ifndef TEST_OBJECT
        obj_deinit_func func;

        if (object->type == TYPE_THREAD)
                clear_fpu_owner(object);

        /* Invoke the object-specific free routine */
        func = obj_deinit_tbl[object->type];
        if (func)
                func(object->opaque);
#endif

        BUG_ON(!list_empty(&object->copies_head));
        kfree(object);
}

所有的对象都有一个公共基类，并定义了虚构函数列表，当引用计数归零即完全被能力组移除后内核会执行deinit代码完成销毁工作。

用户态构建

我们在Lab1的代码导读阶段说明了kernel目录下的代码是如何被链接成内核镜像的，我们在内核镜像链接中引入了procmgr这个预先构建的二进制文件。在Lab3中，我们引入了用户态的代码构建，所以我们将procmgr的依赖改为使用用户态的代码生成。下图为具体的构建规则图。

procmgr是一个自包含的ELF程序，其代码在procmgr中列出，其主要包含一个ELF执行器以及作为Chcore微内核的init程序启动，其构建主要依赖于fsm.srv以及tmpfs.srv，其中fsm.srv为文件系统管理器其扮演的是虚拟文件系统的角色用于桥接不同挂载点上的文件系统的实现，而tmpfs.srv则是Chcore的根文件系统其由ramdisk下面的所有文件以及构建好libc.so所打包好的ramdisk.cpio构成。当构建完tmpfs.srv后其会跟libc.so进行动态链接，最终tmpfs.srv以及fsm.srv会以incbin脚本的形式以二进制的方式被连接至procmgr的最后。在构建procmgr的最后一步，cmake会调用read_procmgr_elf_tool将procmgr这个ELF文件的缩略信息粘贴至procmgr之前。此后procmgr也会以二进制的方式进一步嵌套进入内核镜像之后，最终会在create_root_thread的阶段通过其elf符号得以加载。 最终，Chcore的Kernel镜像的拓扑结构如下

线程生命周期管理

本实验的 OS 运行在 AArch64 体系结构，该体系结构采用“异常级别”这一概念定义程序执行时所拥有的特权级别。从低到高分别是 EL0、EL1、EL2 和 EL3。每个异常级别的具体含义和常见用法已在课程中讲述。

ChCore 中仅使用了其中的两个异常级别：EL0 和 EL1。其中，EL1 是内核模式，kernel 目录下的内核代码运行于此异常级别。EL0 是用户模式，user 目录下的用户库与用户程序代码运行在用户模式下。我们在之前的RTFSC中提到了，在Chcore中内核对用户态提供的所有的资源，如Lab2的内存对象，都围绕着cap_group以及capability展开。同目前所有的主流操作系统一样，ChCore 中的每个进程至少包含一个主线程，也可能有多个子线程，而每个线程则从属且仅从属于一个进程。在 ChCore 中，第一个被创建的进程是 procmgr，是 ChCore 核心的系统服务。本实验将以创建 procmgr 为例探索在 ChCore 中如何创建进程，以及成功创建第一个进程后如何实现内核态向用户态的切换。

在 ChCore 中，第一个被创建的进程是 procmgr，是 ChCore 核心的系统服务。本实验将以创建 procmgr 为例探索在 ChCore 中如何创建进程，以及成功创建第一个进程后如何实现内核态向用户态的切换。

权利组创建

创建用户程序至少需要包括创建对应的 cap_group、加载用户程序镜像并且切换到程序。在内核完成必要的初始化之后，内核将会跳转到创建第一个用户程序的操作中，该操作通过调用 create_root_thread 函数完成，本函数完成第一个用户进程的创建，其中的操作包括从procmgr镜像中读取程序信息，调用create_root_cap_group创建第一个 cap_group 进程，并在 root_cap_group 中创建第一个线程，线程加载着信息中记录的 elf 程序（实际上就是procmgr系统服务）。此外，用户程序也可以通过 sys_create_cap_group 系统调用创建一个全新的 cap_group。

ELF加载

然而，完成 cap_group 的分配之后，用户程序并没有办法直接运行，因为cap_group只是一个资源集合的概念。线程才是内核中的调度执行单位，因此还需要进行线程的创建，将用户程序 ELF 的各程序段加载到内存中。(此为内核中 ELF 程序加载过程，用户态进行 ELF 程序解析可参考user/system-services/system-servers/procmgr/libs/libchcoreelf/libchcoreelf.c，如何加载程序可以对user/system-services/system-servers/procmgr/srvmgr.c中的procmgr_launch_process函数进行详细分析)

进程调度

完成用户程序的内存分配后，用户程序代码实际上已经被映射在root_cap_group的虚拟地址空间中。接下来需要对创建的线程进行初始化，以做好从内核态切换到用户态线程的准备。

至此，我们完成了第一个用户进程与第一个用户线程的创建。接下来就可以从内核态向用户态进行跳转了。 回到kernel/arch/aarch64/main.c，在create_root_thread()完成后，分别调用了sched()与eret_to_thread(switch_context())。 sched()的作用是进行一次调度，在此场景下我们创建的第一个线程将被选择。

switch_context()函数的作用则是进行线程上下文的切换，包括vmspace、fpu、tls等。并且将cpu_info中记录的当前CPU线程上下文记录为被选择线程的上下文（完成后续实验后对此可以有更深的理解）。switch_context() 最终返回被选择线程的thread_ctx地址，即target_thread->thread_ctx。

eret_to_thread最终调用了kernel/arch/aarch64/irq/irq_entry.S中的 __eret_to_thread 函数。其接收参数为target_thread->thread_ctx，将 target_thread->thread_ctx 写入sp寄存器后调用了 exception_exit 函数，exception_exit 最终调用 eret 返回用户态，从而完成了从内核态向用户态的第一次切换。

注意此处因为尚未完成exception_exit函数，因此无法正确切换到用户态程序，在后续完成exception_exit后，可以通过 gdb 追踪 pc 寄存器的方式查看是否正确完成内核态向用户态的切换。

异常管理

由于 ChCore 尚未对用户模式与内核模式的切换进行配置，一旦 ChCore 进入用户模式执行就再也无法正常返回内核模式使用操作系统提供其他功能了。在这一部分中，我们将通过正确配置异常向量表的方式，为 ChCore 添加异常处理的能力。

在 AArch64 架构中，异常是指低特权级软件（如用户程序）请求高特权软件（例如内核中的异常处理程序）采取某些措施以确保程序平稳运行的系统事件，包含同步异常和异步异常：

• 同步异常：通过直接执行指令产生的异常。同步异常的来源包括同步中止（synchronous abort）和一些特殊指令。当直接执行一条指令时，若取指令或数据访问过程失败，则会产生同步中止。此外，部分指令（包括 svc 等）通常被用户程序用于主动制造异常以请求高特权级别软件提供服务（如系统调用）。
• 异步异常：与正在执行的指令无关的异常。异步异常的来源包括普通中 IRQ、快速中断 FIQ 和系统错误 SError。IRQ 和 FIQ 是由其他与处理器连接的硬件产生的中断，系统错误则包含多种可能的原因。本实验不涉及此部分。

发生异常后，处理器需要找到与发生的异常相对应的异常处理程序代码并执行。在 AArch64 中，存储于内存之中的异常处理程序代码被叫做异常向量（exception vector），而所有的异常向量被存储在一张异常向量表（exception vector table）中。可参考kernel/arch/aarch64/irq/irq_entry.S中的图表。

AArch64 中的每个异常级别都有其自己独立的异常向量表，其虚拟地址由该异常级别下的异常向量基地址寄存器（VBAR_EL3，VBAR_EL2 和 VBAR_EL1）决定。每个异常向量表中包含 16 个条目，每个条目里存储着发生对应异常时所需执行的异常处理程序代码。以上表格给出了每个异常向量条目的偏移量。

在 ChCore 中，仅使用了 EL0 和 EL1 两个异常级别，因此仅需要对 EL1 异常向量表进行初始化即可。在本实验中，ChCore 内除系统调用外所有的同步异常均交由 handle_entry_c 函数进行处理。遇到异常时，硬件将根据 ChCore 的配置执行对应的汇编代码，将异常类型和当前异常处理程序条目类型作为参数传递，对于 sync_el1h 类型的异常，跳转 handle_entry_c 使用 C 代码处理异常。对于 irq_el1t、fiq_el1t、fiq_el1h、error_el1t、error_el1h、sync_el1t 则跳转 unexpected_handler 处理异常。

系统调用

内核支持

系统调用是系统为用户程序提供的高特权操作接口。在本实验中，用户程序通过 svc 指令进入内核模式。在内核模式下，首先操作系统代码和硬件将保存用户程序的状态。操作系统根据系统调用号码执行相应的系统调用处理代码，完成系统调用的实际功能，并保存返回值。最后，操作系统和硬件将恢复用户程序的状态，将系统调用的返回值返回给用户程序，继续用户程序的执行。

通过异常进入到内核后，需要保存当前线程的各个寄存器值，以便从内核态返回用户态时进行恢复。保存工作在exception_enter 中进行，恢复工作则由exception_exit完成。可以参考kernel/include/arch/aarch64/arch/machine/register.h中的寄存器结构，保存时在栈中应准备ARCH_EXEC_CONT_SIZE大小的空间。

完成保存后，需要进行内核栈切换，首先从TPIDR_EL1寄存器中读取到当前核的per_cpu_info（参考kernel/include/arch/aarch64/arch/machine/smp.h）,从而拿到其中的cpu_stack地址。

Hello userland!

用户态libc支持

在本实验中新加入了 libc 文件，用户态程序可以链接其编译生成的libc.so,并通过 libc 进行系统调用从而进行向内核态的异常切换。在实验提供的 libc 中，尚未实现 printf 的系统调用，因此用户态程序无法进行正常输出。实验接下来将对 printf 函数的调用链进行分析与探索。

printf 函数调用了 vfprintf，其中文件描述符参数为 stdout。这说明在 vfprintf 中将使用 stdout 的某些操作函数。

在 user/chcore-libc/musl-libc/src/stdio/stdout.c中可以看到 stdout 的 write 操作被定义为 __stdout_write，之后调用到 __stdio_write 函数。

最终 printf 函数将调用到 chcore_stdout_write。

chcore_stdout_write 中的核心函数为 put，此函数的作用是向终端输出一个字符串。

至此，我们完成了对 printf 函数的分析及完善。从 printf 的例子我们也可以看到从通用 api 向系统相关 abi 的调用过程，并最终通过系统调用完成从用户态向内核态的异常切换。

用户程序编写

我们完成了内核态向用户态的切换，以及用户态向内核态的异常切换。同时，我们拥有了一个完整的 libc，可以帮助我们进行系统调用。接下来，我们将尝试使用 ChCore 的 libc 及编译器进行简单的程序编译，并将其加载到内核镜像中运行。

Hello ChCore!

到这里，你的程序应该可以通过所有的测试点并且获得满分。你可以编写一些更复杂的程序并尝试放入 ChCore 中运行。

Lab 4：多核调度与IPC

在本实验中，我们将逐步实现ChCore的多核支持以及微内核系统的核心：进程间通信，本Lab包含四个部分：]

1. 多核启动支持: 使ChCore通过树莓派厂商所提供的固件唤醒多核执行
2. 多核调度: 使ChCore实现在多核上进行round-robin调度。
3. IPC: 使ChCore支持进程间通信
4. IPC调优: 为ChCore的IPC针对测试的特点进行调优。

跟先前的Lab相同，本实验代码包含了基础的 ChCore 操作系统镜像，除了练习题相关部分的源码以外（指明需要阅读的代码），其余部分通过二进制格式提供。 在正确完成本实验的练习题之后，你可以在树莓派3B+QEMU或开发板上进入 ChCore shell。 注释/* LAB 4 TODO BEGIN (exercise #) */和/* LAB 4 TODO END (exercise #) */之间代表需要填空的代码部分。

多核支持

• 启动多核

为了让ChCore支持多核，我们需要考虑如下问题：

• 如何启动多核，让每个核心执行初始化代码并开始执行用户代码？
• 如何区分不同核心在内核中保存的数据结构（比如状态，配置，内核对象等）？
• 如何保证内核中对象并发正确性，确保不会由于多个核心同时访问内核对象导致竞争条件？

在启动多核之前，我们先介绍ChCore如何解决第二个问题。ChCore对于内核中需要每个CPU核心单独存一份的内核对象，都根据核心数量创建了多份（即利用一个数组来保存）。ChCore支持的核心数量为PLAT_CPU_NUM（该宏定义在 kernel/common/machine.h 中，其代表可用CPU核心的数量，根据具体平台而异）。 比如，实验使用的树莓派3平台拥有4个核心，因此该宏定义的值为4。ChCore会CPU核心的核心ID作为数组的索引，在数组中取出对应的CPU核心本地的数据。为了方便确定当前执行该代码的CPU核心ID，我们在 kernel/arch/aarch64/machine/smp.c中提供了smp_get_cpu_id函数。该函数通过访问系统寄存器tpidr_el1来获取调用它的CPU核心的ID，该ID可用作访问上述数组的索引。

#include <common/vars.h>

/* raspi3 config */
#define PLAT_CPU_NUM    4
#define PLAT_RASPI3

启动多核

在实验1中我们已经介绍，在QEMU模拟的树莓派中，所有CPU核心在开机时会被同时启动。在引导时这些核心会被分为两种类型。一个指定的CPU核心会引导整个操作系统和初始化自身，被称为CPU主核（primary CPU）。其他的CPU核心只初始化自身即可，被称为CPU从核（backup CPU）。CPU核心仅在系统引导时有所区分，在其他阶段，每个CPU核心都是被相同对待的。

然而在树莓派真机中，从还需要主C核手动指定每一个CPU核心的的启动地址。这些CPU核心会读取固定地址的上填写的启动地址，并跳转到该地址启动。在kernel/arch/aarch64/boot/raspi3/init/init_c.c中，我们提供了wakeup_other_cores函数用于实现该功能，并让所有的CPU核心同在QEMU一样开始执行_start函数。

与之前的实验一样，主CPU在第一次返回用户态之前会在kernel/arch/aarch64/main.c中执行main函数，进行操作系统的初始化任务。在本小节中，ChCore将执行enable_smp_cores函数激活各个其他CPU。

多核调度

• 调度队列初始化
• 调度队列入队
• 调度队列出队
• 协作式调度
• 抢占式调度
  • 物理时钟初始化
  • 物理时钟中断与抢占

ChCore已经可以启动多核，但仍然无法对多个线程进行调度。本部分将首先实现协作式调度，从而允许当前在CPU核心上运行的线程主动退出或主动放弃CPU时，CPU核心能够切换到另一个线程继续执行。其后，我们将驱动树莓派上的物理定时器，使其以一定的频率发起中断，使得内核可以在一定时间片后重新获得对CPU核心的控制，并基于此进一步实现抢占式调度。

ChCore中与调度相关的函数与数据结构定义在kernel/include/sched/sched.h中。

struct sched_ops {
        int (*sched_init)(void);
        int (*sched)(void);
        int (*sched_periodic)(void);
        int (*sched_enqueue)(struct thread *thread);
        int (*sched_dequeue)(struct thread *thread);
        /* Debug tools */
        void (*sched_top)(void);
};

sched_ops是用于抽象ChCore中调度器的一系列操作。它存储指向不同调度操作的函数指针，以支持不同的调度策略。 cur_sched_ops则是一个sched_ops的实例，其在内核初始化过程中（main函数）调用sched_init进行初始化。 ChCore用在 kernel/include/sched/sched.h 中定义的静态函数封装对cur_sched_ops的调用。sched_ops中定义的调度器操作如下所示：

• sched_init：初始化调度器。
• sched：进行一次调度。即将正在运行的线程放回就绪队列，然后在就绪队列中选择下一个需要执行的线程返回。
• sched_enqueue：将新线程添加到调度器的就绪队列中。
• sched_dequeue：从调度器的就绪队列中取出一个线程。
• sched_top：用于debug,打印当前所有核心上的运行线程以及等待线程的函数。

在本部分将实现一个基本的Round Robin（时间片轮转）调度器，该程序调度在同一CPU核心上运行的线程，因此内核初始化过程调用sched_init时传入了&rr作为参数。该调度器的调度操作（即对于sched_ops定义的各个函数接口的实现）实现在kernel/sched/policy_rr.c中，这里简要介绍其涉及的数据结构：

current_threads是一个数组，分别指向每个CPU核心上运行的线程。而current_thread则利用smp_get_cpu_id获取当前运行核心的id，从而找到当前核心上运行的线程。

struct queue_meta定义了round robin调度器使用的就绪队列，其中queue_head字段是连接该就绪队列上所有等待线程的队列，queue_len字段是目前该就绪队列的长度，queue_lock字段是用于保证该队列并发安全的锁。 kernel/sched/policy_rr.c定义了一个全局变量rr_ready_queue_meta,该变量是一个struct queue_meta类型的数组，数组大小由PLAT_CPU_NUM定义，即代表每个CPU核心都具有一个就绪队列。运行的CPU核心可以通过smp_get_cpu_id获取当前运行核心的id，从而在该数组中找到当前核心对应的就绪队列。

调度队列初始化

内核初始化过程中会调用sched_init初始化调度相关的元数据，sched_init定义在kernel/sched/sched.c中，该函数首先初始化idle_thread(每个CPU核心拥有一个idle_thread，当调度器的就绪队列中没有等待线程时会切换到idle_thread运行)，然后会初始化current_threads数组，最后调用struct sched_ops rr中定义的sched_init函数，即rr_sched_init。

调度队列入队

内核初始化过程结束之后会调用create_root_thread来创建第一个用户态进程及线程，在create_root_thread最后会调用sched_enqueue函数将创建的线程加入调度队列之中。sched_enqueue 最终会调用kernel/sched/policy_rr.c中定义的rr_sched_enqueue函数。该函数首先挑选合适的CPU核心的就绪队列（考虑线程是否绑核以及各个CPU核心之间的负载均衡），然后调用__rr_sched_enqueue将线程插入到选中的就绪队列中。

调度队列出队

内核初始化过程结束并调用create_root_thread创建好第一个用户态进程及线程之后，在第一次进入用户态之前，会调用sched函数来挑选要返回到用户态运行的线程（虽然此时就绪队列中只有root thread一个线程）。sched最终会调用kernel/sched/policy_rr.c中定义的rr_sched函数。 该调度函数的操作非常直观，就是将现在正在运行的线程重新加入调度器的就绪队列当中，并从就绪队列中挑选出一个新的线程运行。 由于内核刚刚完成初始化，我们还没有设置过current_thread，所以rr_sched函数中old为NULL，后面的练习中我们会考虑old不为NULL的情况。紧接着rr_sched会调用rr_sched_choose_thread函数挑选出下一个运行的线程，并切换到该线程。

rr_sched_choose_thread内部会调用find_runnable_thread从当前CPU核心的就绪队列中选取一个可以运行的线程并调用__rr_sched_dequeue将其从就绪队列中移除。

协作式调度

顾名思义，协作式调度需要线程主动放弃CPU。为了实现该功能，我们提供了sys_yield这一个系统调用(syscall)。该syscall可以主动放弃当前CPU核心，并调用上述的sched接口完成调度器的调度工作。kernel/sched/policy_rr.c中定义的rr_sched函数中，如果当前运行线程的状态为TS_RUNNING，即还处于可以运行的状态，我们应该将其重新加入到就绪队列当中，这样该线程在之后才可以被再次调度执行。

抢占式调度

使用刚刚实现的协作式调度器，ChCore能够在线程主动调用sys_yield系统调用让出CPU核心的情况下调度线程。然而，若用户线程不想放弃对CPU核心的占据，内核便只能让用户线程继续执行，而无法强制用户线程中止。 因此，在这一部分中，本实验将实现抢占式调度，以帮助内核定期重新获得对CPU核心的控制权。

ChCore启动的第一个用户态线程（执行user/system-services/system-servers/procmgr/procmgr.c的main函数）将创建一个“自旋线程”，该线程在获得CPU核心的控制权后便会执行无限循环，进而导致无论是该程序的主线程还是ChCore内核都无法重新获得CPU核心的控制权。就保护系统免受用户程序中的错误或恶意代码影响而言，这一情况显然并不理想，任何用户应用线程均可以如该“自旋线程”一样，通过进入无限循环来永久“霸占”整个CPU核心。

为了处理“自旋线程”的问题，ChCore内核必须具有强行中断一个正在运行的线程并夺回对CPU核心的控制权的能力，为此我们必须扩展ChCore以支持处理来自物理时钟的外部硬件中断。

物理时钟初始化

本部分我们将通过配置ARM提供的Generic Timer来使能物理时钟并使其以固定的频率发起中断。 我们需要处理的系统寄存器如下(Refer):

• CNTPCT_EL0: 它的值代表了当前的 system count。
• CNTFRQ_EL0: 它的值代表了物理时钟运行的频率，即每秒钟 system count 会增加多少。
• CNTP_CVAL_EL0: 是一个64位寄存器，操作系统可以向该寄存器写入一个值，当 system count 达到或超过该值时，物理时钟会触发中断。
• CNTP_TVAL_EL0: 是一个32位寄存器，操作系统可以写入 TVAL，处理器会在内部读取当前的系统计数，加上写入的值，然后填充 CVAL。
• CNTP_CTL_EL0: 物理时钟的控制寄存器，第0位ENABLE控制时钟是否开启，1代表enble，0代表disable；第1位IMASK代表是否屏蔽时钟中断，0代表不屏蔽，1代表屏蔽。

对物理时钟进行初始化的代码位于kernel/arch/aarch64/plat/raspi3/irq/timer.c的plat_timer_init函数。

物理时钟中断与抢占

我们在lab3中已经为ChCore配置过异常向量表（kernel/arch/aarch64/irq/irq_entry.S），当收到来自物理时钟的外部中断时，内核会进入handle_irq中断处理函数，该函数会调用平台相关的plat_handle_irq来进行中断处理。plat_handle_irq内部如果判断中断源为物理时钟，则调用handle_timer_irq。

ChCore记录每个线程所拥有的时间片（thread->thread_ctx->sc->budget），为了能够让线程之间轮转运行，我们应当在处理时钟中断时递减当前运行线程的时间片，并在当前运行线程的时间片耗尽时进行调度，选取新的线程运行。

进程间通信（IPC）

• 进程间通讯概览
• 具体流程

在本部分，我们将实现ChCore的进程间通信，从而允许跨地址空间的两个进程可以使用IPC进行信息交换。

进程间通讯概览

ChCore的IPC接口不是传统的send/recv接口。其更像客户端/服务器模型，其中IPC请求接收者是服务器，而IPC请求发送者是客户端。 服务器进程中包含三类线程:

• 主线程：该线程与普通的线程一样，类型为TYPE_USER。该线程会调用ipc_register_server将自己声明为一个IPC的服务器进程，调用的时候会提供两个参数:服务连接请求的函数client_register_handler和服务真正IPC请求的函数server_handler（即图中的ipc_dispatcher），调用该函数会创建一个注册回调线程;

• 注册回调线程：该线程的入口函数为上文提到的client_register_handler，类型为TYPE_REGISTER。正常情况下该线程不会被调度执行，仅当有Client发起建立IPC连接的请求时，该线程运行并执行client_register_handler，为请求建立连接的Client创建一个服务线程（即图中的IPC handler thread）并在服务器进程的虚拟地址空间中分配一个可以用来映射共享内存的虚拟地址。

• 服务线程：当Client发起建立IPC连接请求时由注册回调线程创建，入口函数为上文提到的server_handler，类型为TYPE_SHADOW。正常情况下该线程不会被调度执行，仅当有Client端线程使用ipc_call发起IPC请求时，该线程运行并执行server_handler（即图中的ipc_dispatcher），执行结束之后会调用ipc_return回到Client端发起IPC请求的线程。

具体流程

为了实现ChCore IPC的功能，首先需要在Client与Server端创建起一个一对一的IPC Connection。该Connection保存了IPC Server的服务线程（即上图中IPC handler Thread）、Client与Server的共享内存（用于存放IPC通信的内容）。同一时刻，一个Connection只能有一个Client接入，并使用该Connection切换到Server的处理流程。ChCore提供了一系列机制，用于创建Connection以及创建每个Connection对应的服务线程。下面将以具体的IPC注册到调用的流程，详细介绍ChCore的IPC机制：

1. IPC服务器的主线程调用: ipc_register_server (user/chcore-libc/musl-libc/src/chcore-port/ipc.c中)来声明自己为IPC的服务器端。

   • 参数包括server_handler和client_register_handler，其中server_handler为服务端用于提供服务的回调函数（比如上图中IPC handler Thread的入口函数ipc_dispatcher）；client_register_handler为服务端提供的用于注册的回调函数，该函数会创建一个注册回调线程。

   • 随后调用ChCore提供的的系统调用：sys_register_server。该系统调用实现在kernel/ipc/connection.c当中，该系统调用会分配并初始化一个struct ipc_server_config和一个struct ipc_server_register_cb_config。之后将调用者线程（即主线程）的general_ipc_config字段设置为创建的struct ipc_server_config，其中记录了注册回调线程和IPC服务线程的入口函数（即图中的ipc_dispatcher）。将注册回调线程的general_ipc_config字段设置为创建的struct ipc_server_register_cb_config，其中记录了注册回调线程的入口函数和用户态栈地址等信息。

2. IPC客户端线程调用ipc_register_client（定义在user/chcore-libc/musl-libc/src/chcore-port/ipc.c中）来申请建立IPC连接。

   • 该函数仅有一个参数，即IPC服务器的主线程在客户端进程cap_group中的capability。该函数会首先通过系统调用申请一块物理内存作为和服务器的共享内存（即图中的Shared Memory）。

   • 随后调用sys_register_client系统调用。该系统调用实现在kernel/ipc/connection.c当中，该系统调用会将刚才申请的物理内存映射到客户端的虚拟地址空间中，然后调用create_connection创建并初始化一个struct ipc_connection类型的内核对象，该内核对象中的shm字段会记录共享内存相关的信息（包括大小，分别在客户端进程和服务器进程当中的虚拟地址和capability）。

   • 之后会设置注册回调线程的栈地址、入口地址和第一个参数，并切换到注册回调线程运行。

3. 注册回调线程运行的入口函数为主线程调用ipc_register_server是提供的client_register_handler参数，一般会使用默认的DEFAULT_CLIENT_REGISTER_HANDLER宏定义的入口函数，即定义在user/chcore-libc/musl-libc/src/chcore-port/ipc.c中的register_cb。

   • 该函数首先分配一个用来映射共享内存的虚拟地址，随后创建一个服务线程。

   • 随后调用sys_ipc_register_cb_return系统调用进入内核，该系统调用将共享内存映射到刚才分配的虚拟地址上，补全struct ipc_connection内核对象中的一些元数据之后切换回客户端线程继续运行，客户端线程从ipc_register_client返回，完成IPC建立连接的过程。

4. IPC客户端线程调用ipc_create_msg和ipc_set_msg_data向IPC共享内存中填充数据，然后调用ipc_call（user/chcore-libc/musl-libc/src/chcore-port/ipc.c中）发起IPC请求。

   • ipc_call中会发起sys_ipc_call系统调用（定义在kernel/ipc/connection.c中），该系统调用将设置服务器端的服务线程的栈地址、入口地址、各个参数，然后迁移到该服务器端服务线程继续运行。由于当前的客户端线程需要等待服务器端的服务线程处理完毕，因此需要更新其状态为TS_WAITING，且不要加入等待队列。

5. IPC服务器端的服务线程在处理完IPC请求之后使用ipc_return返回。

   • ipc_return会发起sys_ipc_return系统调用，该系统调用会迁移回到IPC客户端线程继续运行，IPC客户端线程从ipc_call中返回。

实机运行与IPC性能优化

在本部分，你需要对IPC的性能进行优化。为此，你首先需要在树莓派3B实机上运行ChCore。

在ChCore启动并通过测试后，在命令行运行

./test_ipc_perf.bin

你会得到如下输出结果

[TEST] test ipc with 32 threads, time: xxx cycles
[TEST] test ipc with send cap, loop: 100, time: xxx cycles
[TEST] test ipc with send cap and return cap, loop: 100, time: xxx cycles
[TEST] Test IPC Perf finished!

IPC性能测试程序的测试用例包括：

1. 创建多个线程发起IPC请求（不传递cap），Server收到IPC后直接返回。记录从创建线程到所有线程运行结束的时间。
2. Client创建多个PMO对象，并发起IPC请求（传递PMO）；Server收到IPC后读取PMO，并依据读出的值算出结果，将结果写回随IPC传递的PMO中并返回；Client在IPC返回后读取PMO中的结果。将上述过程循环多次并记录运行时间。
3. Client创建多个PMO对象，并发起IPC请求（传递PMO）；Server收到IPC后读取PMO，并依据读出的值算出结果，然后创建新的PMO对象，将结果写入新创建的PMO中，并通过ipc_return_with_cap返回；Client在IPC返回后读取返回的PMO中的结果。将上述过程循环多次并记录运行时间。

在测试能够顺利通过的前提下，你可以修改任意代码。（测试程序所调用的函数位于 user/chcore-libc/libchcore/porting/overrides/src/chcore-port/ipc.c）

Lab 5：虚拟文件系统

虚拟文件系统（Virtual File System，VFS）提供了一个抽象层，使得不同类型的文件系统可以在应用程序层面以统一的方式进行访问。这个抽象层隐藏了不同文件系统之间的差异，使得应用程序和系统内核可以以一致的方式访问各种不同类型的文件系统，如 ext4、tmpfs、 FAT32 等。在 ChCore 中，我们通过 FSM 系统服务以及 FS_Base 文件系统 wrapper 将不同的文件系统整合起来，给运行在 ChCore 上的应用提供了统一的抽象。

本Lab一共分为三个部分：

1. Posix适配：分析ChCore是如何实现兼容posix的文件接口的。
2. FSM：FSM是ChCore的虚拟文件系统的实现层，其主要负责页缓存，挂载点管理，以及路径对接。我们在此部分实现这一文件系统转发层。
3. FS_Base: FS_Base是文件系统实现层，由于在微内核系统中文件系统实际由一个个进程实现，所以我们统一包装标准的文件操作到通用库即为FS_Base，我们需要在这一个部分实现它。

跟先前的Lab相同，本实验代码包含了基础的 ChCore 操作系统镜像，除了练习题相关部分的源码以外（指明需要阅读的代码），其余部分通过二进制格式提供。 在正确完成本实验的练习题之后，你可以在树莓派3B+QEMU或开发板上进入 ChCore shell。与之前的Lab不同的地方是，本Lab不涉及任何内核态的代码编写，你需要将所有的目光聚焦在user这个目录下面的文件。注释/* LAB 5 TODO BEGIN (exercise #) */和/* LAB 5 TODO END (exercise #) */之间代表需要填空的代码部分。

Posix 适配

无论我们采用的是什么样的操作系统，如果我们希望能够对上用户态的程序的话，我们都希望其采用同一套的调用规范。相同的在我们开发用户态程序的时候，我们也希望下层的libc提供的接口保持一致，以便于开发者进行移植。而在现代操作系统中Posix是一个非常重要的规范。我们都可以在Windows, MacOS, Linux以及其他的衍生系统上找到它的身影，Posix针对文件系统提出了一系列的API规范。下面是一个简要的描述

1. mount, umount API：用于文件系统的挂载以及
2. open, close：用于打开以及关闭文件描述符
3. write, read：用于文件的读写
4. mkdir, rmdir, creat, unlink, link, symlink：用于文件以及目录的创建与删除
5. fcntl (byte range locks, etc.)：用于修改文件描述符的具体属性
6. stat, utimes, chmod, chown, chgrp：用于修改文件的属性
7. 所有的文件路径都以及'/'开始

例如当我们在Linux系统中使用strace去追踪cat指令的系统调用时我们可以得到如下的系统调用序

openat(AT_FDCWD, "foo", O_RDONLY)       = 3
fstat(3, {st_mode=S_IFREG|0644, st_size=4, ...}) = 0
fadvise64(3, 0, 0, POSIX_FADV_SEQUENTIAL) = 0
mmap(NULL, 139264, PROT_READ|PROT_WRITE, MAP_PRIVATE|MAP_ANONYMOUS, -1, 0) = 0x7cb8b6fd3000
read(3, "foo\n", 131072)                = 4
write(1, "foo\n", 4foo
)                    = 4
read(3, "", 131072)                     = 0

撇去一些无关紧要的系统调用后，我们可以看到其首先调用了openat这个系统指令，其负责打开一个系统路径下的文件，并返回其一个文件描述符号。

Lab5 的所有代码都运行在用户态，不同应用间通过 IPC 进行通信，可调用的 IPC 相关函数定义在 user/chcore-libc/libchcore/porting/overrides/include/chcore/ipc.h。

如果你感兴趣的话，你也可以继续阅读read以及write这些文件系统调用的实现，来看看chcore-libc是怎么将Chcore文件系统的实现对齐在Posix的API之上的。

FSM

只要实现了 FSBase 和 FSWrapper 的接口的 IPC 服务，都可以成为一个文件系统示例。FSM 负责管理文件系统，为用户态建立文件系统连接并创建 IPC 的客户端，由于文件系统与其挂载点密切相关，所以 FSM 会处理以下类型的请求：

/* Client send fsm_req to FSM */
enum fsm_req_type {
        FSM_REQ_UNDEFINED = 0,

        FSM_REQ_PARSE_PATH,
        FSM_REQ_MOUNT,
        FSM_REQ_UMOUNT,

        FSM_REQ_SYNC,
};

当 FSM 收到 Client 的FSM_REQ_MOUNT 类型的请求时，其会执行挂载文件系统的操作，增加挂载的文件系统数量，创建对应的 mount_info_node 添加到挂载信息表中，直至最后与文件系统建立 IPC 连接，并将创建完的 IPC 客户端保存在挂载信息中，总而言之，FSM 仅负责挂载和文件系统同步有关的工作，剩下的其他功能由每个具体的FS服务进行处理。

struct mount_point_info_node {
        cap_t fs_cap;
        char path[MAX_MOUNT_POINT_LEN + 1];
        int path_len;
        ipc_struct_t *_fs_ipc_struct; // fs_client
        int refcnt;
        struct list_head node;
};

当 FSM 收到 Client 的 FSM_REQ_PARSE_PATH 类型的请求时，其首先会尝试解析 IPC 请求中访问文件的路径，通过遍历挂载信息链表，找到对应的最匹配的文件系统以及其挂载点路径。通过匹配的文件系统，获取到该文件系统的客户端 cap。如果 Client 已经获取到了文件系统的 cap，则直接返回解析后的挂载点路径；否则 FSM 会把挂载路径以及其对应的文件系统的 cap 也一并返回给 Client，并记录该 Client 已获取的文件系统 cap 的信息（FSM 会记录所有已经发送给某个 Client 的文件系统的 cap，见 user/system-services/system-servers/fsm/fsm_client_cap.h）。

FS_Base

• vnode
• server_entry
• fs_wrapper_ops

在 ChCore 中，FS_Base 是文件系统的一层 wrapper，IPC 请求首先被 FS_Base 接收，再由 FS_Base 调用实际的文件系统进行处理。

vnode

在 FS_Base wrapper 中，ChCore 实现了 vnode 抽象，为文件系统中的对象（如文件、目录、符号链接等）提供一个统一的表示方式。

ChCore 中 vnode 的定义为：

struct fs_vnode {
        ino_t vnode_id; /* identifier */
        struct rb_node node; /* rbtree node */

        enum fs_vnode_type type; /* regular or directory */
        int refcnt; /* reference count */
        off_t size; /* file size or directory entry number */
        struct page_cache_entity_of_inode *page_cache;
        cap_t pmo_cap; /* fmap fault is handled by this */
        void *private;

        pthread_rwlock_t rwlock; /* vnode rwlock */
};

其中，private 表示文件系统特定的私有数据，例如对 inode 的引用，refcnt 代表该 vnode 被引用的次数，在下文的 server_entry 中会提到。

server_entry

文件描述符（File Descriptor，简称 fd）是操作系统用于管理文件和其他输入/输出资源（如管道、网络连接等）的一种抽象标识符。我们来回顾一下计算机系统基础课中学习的unix文件系统抽象。在类 Unix 系统（如 Linux、macOS）中，文件描述符是一个非负整数，它指向一个内核中的文件表项，每个表项包含了文件的各种状态信息和操作方法。ChCore 将进程的 fd 保存在 chcore-libc 当中，同时在文件系统中通过 server_entry 维护了各个 Client 的 fd 的信息，把各个 Client 的 fd 和在文件系统侧的 fid 对应起来（(client_badge, fd) -> fid(server_entry)），也就是说 server_entry 对应着每个文件系统实例所对应的文件表项，其包含了对应文件表项的文件 offset 以及 vnode 引用。由于一个 vnode 可能会对应多个文件表项，所以 vnode 的引用数需要进行维护。

FS_Base 的 IPC handler 在处理 IPC 请求时，会先把 IPC 消息中包含的文件 fd 转换为 fid，所以我们需要把进程的 fd 和实际所对应的文件表项的映射建立起来，而在 ChCore 中对应的就是 server_mapping 链表。每当处理 IPC 请求时，文件系统都会通过进程发起的 badge 号找到与之对应的映射表，最终得到文件表项的 ID。

fs_wrapper_ops

当我们拥有了文件表项和VNode抽象后，我们便可以实现真正的文件系统操作了。

我们可以将 FS_Base 以及 FS_Wrapper 的所有逻辑看成一个 VFS 的通用接口，其暴露出的接口定义为 strcut fs_server_ops。对于每一个文件系统实例，其都需要定义一个全局的名为 server_ops 的全局句柄，并将实际的文件系统操作的实现注册到该句柄中。你可以通过查看 user/system-services/system-servers/tmpfs/tmpfs.c 中查看 ChCore 的默认 tmpfs 文件系统是怎么将其注册到 FS_Wrapper 中的。而到了实际处理文件请求时，上层的 FS_Wrapper 在响应 IPC 请求的时候，只需要调用 server_ops 中的函数指针即可，不需要实际真正调用每一个文件系统实现的操作函数， 这样便完成了一个统一的文件操作逻辑。例如在 tmpfs 中实际的读命令为 tmpfs_read 但在上层的 fs_wrapper 看来其调用只需要调用 server_ops->read 即可而不需要真正知晓 tmpfs 中的函数签名。

对于本 Lab 你只需要实现最基本的 Posix 文件操作即可，即 Open，Close，Read, Write 以及 LSeek 操作。而其下层每个文件系统除了 Open 操作，每当 FS_Base 尝试处理 Posix 文件请求时，其都会调用 translate_fd_to_fid 将对应的 fd 翻译成 fid 并重新写回 struct fs_request 中的 fd，所以请注意不需要在实际的fs_wrapper_函数中再次调用该函数。下面将简述一下每一个函数的语义。

对于 Open 以及 Close 来说，其主要的目的就是创建以及回收 Server Entry 即文件表项。由于在 VFS 中 VNode 的创建是动态的，所以当进程尝试发出 Open 中，我们需要调用与之对应的 server_ops 并同时分配对应的文件表项。对于每一个新增的文件表项，我们需要将其关联到对应的内存 VNode 中。由于文件表项所对应的 VNode 可能不在内存中，所以当文件系统返回 inode 号时我们需要尝试查找相应的 vnode，如果不存在则尝试分配并将其添加至对应的红黑树中。当完成 VNode 关联后，我们需要使用上一步实现的映射函数，将 server_entry 与用户 fd 映射，完成文件表项的创建。对于 Close，我们需要采取类似的逻辑，即回退所有的文件表项操作，减少引用计数，并尝试回收对应的系统资源。

针对 Read/Write/Lseek 操作，你需要参考 man 以及对应的 tests/fs_test 下的所有测试文件，按照 Posix 语义相应地维护 server_entry 以及 vnode 信息，并将数据返回给用户进程。

针对 mmap 操作，我们知道针对文件的 mmap 操作是采取 Demand Paging 的内存映射来实现的，当用户进程调用 mmap 时，FS 会首先为用户新增一个 pmo 即内存对象，并将其对应的类型设置为 PMO_FILE，并为其创建 Page_Fault 映射(user/system-services/system-servers/fs_base/fs_page_fault.c)，最后将该 pmo 对象发回用户进程并让其进行映射。当用户尝试访问该内存对象，并发生缺页异常时，内核会根据 pmo 的所有者(badge)将异常地址调用到对应FS处理函数进行处理，处理函数为每一个文件系统中的 user_fault_handler，此时 FS 服务器会根据缺页地址分配新的内存页，填充文件内容并完成缺页的处理，最终返回内核态，从而递交控制权到原来的用户进程。

源码解析

这部分内容是对机器启动部分的chcore源代码的详细解析，包括内核启动与页表映射两个部分。

内核启动

目录

• 内核启动
  • 目录
  • 多内核启动及设置
    • 总览
    • 启动 CPU 0 号核
    • 如何让内核依次启动？
      • 0号核
      • 非0号核
      • 后续操作
    • 内核启动时的设置
      • 关于栈的设置
      • bss段清零
      • 切换内核异常级别
      • 启用MMU
      • 初始化串口输出

让我们把目光放到 start.S 文件上，这里是内核启动的开始：

多内核启动及设置

总览

对于多内核的chcore系统，我们在启动内核的时候通常会让一个内核进入启动流程，让其他内核先进行等待，待该内核完成基本的初始化之后，再让其他核心进行这些流程

启动 CPU 0 号核

既然是排队，那么总要有一个先后顺序，我们在chcore中的策略是让0号核心先启动，看代码如下：

BEGIN_FUNC(_start)
 mrs x8, mpidr_el1
 and x8, x8, #0xFF
 cbz x8, primary

关于 mpidr_el1 这样的系统寄存器，可以在lab文档里给到的manual里查到相关信息（备注：更方便的手段是先询问llm，然后再在manual里面求证即可）：

由此我们得知，mpidr_el1寄存器存储的是CPU核心的唯一标识符，这里我们使用它来区分不同的核心，逻辑如下：

• 读取系统寄存器的值到 x8
• 与 0xFF 进行与操作，即保留低8位，是一个mask操作，这样可以去除掉高位的不必要的信息
• 将得到的值与0比较，若相等，则跳转到 primary 标签，进行后续操作

如何让内核依次启动？

继续浏览start.S，根据上文的逻辑，在判断出当前CPU是否为0号核心之后，0号核心与非0号核心需要执行的操作是不同的

但是如何让0号核和其他核区别开来，做好自己的启动工作呢？这里给出一个大概的逻辑

0号核

注意到此时代码跳转到了primary标签

primary:

 /* Turn to el1 from other exception levels. */
 bl  arm64_elX_to_el1

 /* Prepare stack pointer and jump to C. */
 adr  x0, boot_cpu_stack
 add  x0, x0, #INIT_STACK_SIZE
 mov  sp, x0

 b  init_c

 /* Should never be here */
 b .

关于降低异常级别的部分会在下面提到，我们现在只需要站在宏观的视角理解0号核干了什么：

• 从其他的异常级别降低到1
• 为跳转到C语言部分代码做设置栈的准备
• 跳转到init_c
• 代码的最后是一个死循环，如果前面发生了故障可以将内核卡死在这里，注意到注释也提到了“Should never be here”

非0号核

非0号核在cbz指令判断失败后，会按照顺序继续执行下面的代码，如下所示：

 /* Wait for bss clear */
wait_for_bss_clear:
 adr x0, clear_bss_flag
 ldr x1, [x0]
 cmp     x1, #0
 bne wait_for_bss_clear

...

 /* Turn to el1 from other exception levels. */
 bl  arm64_elX_to_el1

 /* Prepare stack pointer and jump to C. */
 mov x1, #INIT_STACK_SIZE
 mul x1, x8, x1
 adr  x0, boot_cpu_stack
 add x0, x0, x1
 add x0, x0, #INIT_STACK_SIZE
 mov sp, x0

wait_until_smp_enabled:
 /* CPU ID should be stored in x8 from the first line */
 mov x1, #8
 mul x2, x8, x1
 ldr x1, =secondary_boot_flag
 add x1, x1, x2
 ldr x3, [x1]
 cbz x3, wait_until_smp_enabled

 /* Set CPU id */
 mov x0, x8
 b  secondary_init_c

 /* Should never be here */
 b .

这里的代码采用了轮询的手段，通俗的讲，就是反复检查相关条件是否满足。CPU不断检查 clear_bss_flag 与 secondary_boot_flag 数组里的内容，若收到信号，则执行对应操作。

二者具体的操作逻辑不细讲，概括如下：

• bss段清零后，同样执行降低内存级别的操作，随后设置栈
• 这一段完成后继续等待信号，收到通知后即设置CPU id并跳转到这部分内核对应的c代码

后续操作

内核进行完毕初始设置后，即进入 init_c.c 部分的代码，在c代码的程序中继续完成相关设置：

• 叫醒其他核
• 清理bss段数据
• 初始化串口
• 设置mmu
• 注意这里不同内核执行的函数不一样，有高低贵贱之分

void init_c(void)
{
 /* Clear the bss area for the kernel image */
 clear_bss();

 /* Initialize UART before enabling MMU. */
 early_uart_init();
 uart_send_string("boot: init_c\r\n");

 wakeup_other_cores();

 /* Initialize Kernell Page Table. */
 uart_send_string("[BOOT] Install kernel page table\r\n");
 init_kernel_pt();

 /* Enable MMU. */
 el1_mmu_activate();
 uart_send_string("[BOOT] Enable el1 MMU\r\n");

 /* Call Kernel Main. */
 uart_send_string("[BOOT] Jump to kernel main\r\n");
 start_kernel(secondary_boot_flag);

 /* Never reach here */
}

void secondary_init_c(int cpuid)
{
 el1_mmu_activate();
 secondary_cpu_boot(cpuid);
}

内核启动时的设置

上一部分我们对多内核启动的全部过程有了一个大概的了解，而这一部分则主要讲解内核在启动过程中的具体设置，包括汇编与C代码中的重要函数

事实上，它们是相互交错运行的，共同为新生伊始的CPU内核配置好相关设置

关于栈的设置

/* Prepare stack pointer and jump to C. */
 adr  x0, boot_cpu_stack
 add  x0, x0, #INIT_STACK_SIZE
 mov  sp, x0

代码中的设置部分是将栈指针的内容准备（获取栈的基地址，计算栈顶地址）好后，直接移动到sp寄存器中，即完成了栈的设置

栈是系统用来存储局部变量、函数参数、返回地址、寄存器值的重要部分，若不设置这一部分，sp寄存器会指向随机地址，对系统的后续行为是毁灭性的打击

bss段清零

.bss段用于存储未初始化的全局变量和静态变量，将这部分值统一设置为0

若没有这一部分操作，则会让全局变量和静态变量的0初始值受到破坏

假如遇到程序或内核操作需要用到默认为0的全局变量，未初始化bss段数据的行为将会导致相应的操作出现bug

这一部分的代码在 init_c.c 中，可自行阅读

切换内核异常级别

上面分析 start.S 代码时，我们遇到了 arm_elX_to_el1 函数，其作用是将内核的异常级别从el3降低到el1。相关代码在同目录 tool.S 文件中，我们现在对其进行考察与分析：

BEGIN_FUNC(arm64_elX_to_el1)
 mrs x9, CurrentEL

 // Check the current exception level.
 cmp x9, CURRENTEL_EL1
 beq .Ltarget
 cmp x9, CURRENTEL_EL2
 beq .Lin_el2
 // Otherwise, we are in EL3.

 // Set EL2 to 64bit and enable the HVC instruction.

  ...

 // Set the return address and exception level.
 adr x9, .Ltarget
 msr elr_el3, x9
 mov x9, SPSR_ELX_DAIF | SPSR_ELX_EL1H
 msr spsr_el3, x9

.Lin_el2:
 // Disable EL1 timer traps and the timer offset.
 // Disable stage 2 translations.
 // Disable EL2 coprocessor traps.
 // Disable EL1 FPU traps.

  ...

 // Check whether the GIC system registers are supported.
 mrs x9, id_aa64pfr0_el1
 and x9, x9, ID_AA64PFR0_EL1_GIC
 cbz x9, .Lno_gic_sr

 // Enable the GIC system registers in EL2, and allow their use in EL1.
 // Disable the GIC virtual CPU interface.
 
  ...
  
.Lno_gic_sr: // No GIC System Registers

 // Set EL1 to 64bit.

  ...

 // Set the return address and exception level.
 adr x9, .Ltarget
 msr elr_el2, x9
 mov x9, SPSR_ELX_DAIF | SPSR_ELX_EL1H
 msr spsr_el2, x9

 isb
 eret

.Ltarget:
 ret
END_FUNC(arm64_elX_to_el1)

（部分细节处的琐碎设置代码已略去，看注释即可）

纵观全局，我们的源码符合lab文档里“没有直接写死从el3到el1”的逻辑，而是降低异常级别的行动分成了数个步骤来执行：

• 先获取当前异常级别
• 若级别是el3，则直接往下执行
• 若级别是el2/el1，则跳转到相应的部分，总体上是3→2→1的逻辑
• 在最后调用 eret 指令，正式调整内核级别

对于 eret 指令，这是一个用来从高级别跳转到低级别的指令，执行它需要我们设置两个寄存器：

• elr_elx：异常链接寄存器，保存跳转级别后执行的指令地址

• spsr_elx：保存的程序状态寄存器，包含异常返回后的异常级别

关于代码的其他部分，可以阅读注释作初步了解，深入学习可以结合llm与教材

启用MMU

如果你看过 init_c.c 文件，会发现我们在内核启动是还需要进行启动页表的相关配置。关于页表的具体配置较为复杂，会在另一篇解析单独讲解，这里主要讲解启用MMU的部分

启用MMU部分的代码同样在 tool.S 文件中，相关代码如下：

BEGIN_FUNC(el1_mmu_activate)
 stp     x29, x30, [sp, #-16]!
 mov     x29, sp

 bl invalidate_cache_all

 /* Invalidate TLB */
 /* Initialize Memory Attribute Indirection Register */
 /* Initialize TCR_EL1 */
 /* set cacheable attributes on translation walk */
 /* (SMP extensions) non-shareable, inner write-back write-allocate */
 /* Write ttbr with phys addr of the translation table */

  ...
 
 mrs     x8, sctlr_el1
 /* Enable MMU */
 orr     x8, x8, #SCTLR_EL1_M
 /* Disable alignment checking */
 bic     x8, x8, #SCTLR_EL1_A
 bic     x8, x8, #SCTLR_EL1_SA0
 bic     x8, x8, #SCTLR_EL1_SA
 orr     x8, x8, #SCTLR_EL1_nAA
 /* Data accesses Cacheable */
 orr     x8, x8, #SCTLR_EL1_C
 /* Instruction access Cacheable */
 orr     x8, x8, #SCTLR_EL1_I
 /* Writable eXecute Never */
 orr     x8, x8, #SCTLR_EL1_WXN
 msr     sctlr_el1, x8

 ldp     x29, x30, [sp], #16
 ret
END_FUNC(el1_mmu_activate)

这时候我们的内核异常级别已经降低到el1，而启用MMU的操作同样是通过为系统寄存器进行相应的赋值（即硬件与软件的相互配合），代码中则是通过不断配置相关的字段来实现的，对于这里的源码，我们执行的操作如下：

• 启用MMU，即M字段，这个是必须的
• 禁用内存对齐检查，即A，SA0，SA，nAA字段
• 启用指令与数据缓存，即C，I字段
• 启用写保护，即WXN字段，可写页但不可执行

初始化串口输出

同样是 init_c.c 中的操作，我们需要对树莓派的UART串口进行初始化启用，从而使kernel能输出字符

具体的实现在 uart.c 文件中，代码结构如下所示：

   #if USE_mini_uart == 1
   
   // Mini UART代码
   void early_uart_init(void) { ... }
   static unsigned int early_uart_lsr(void) { ... }
   static void early_uart_send(unsigned int c) { ... }
   
   #else
   
   // PL011代码
   void early_uart_init(void) { ... }
   static unsigned int early_uart_fr(void) { ... }
   static void early_uart_send(unsigned int c) { ... }
   
   #endif
   
   void uart_send_string(char *str) {
  int i;
  for (i = 0; str[i] != '\0'; i++) {
   if (str[i] == '\n')
   early_uart_send('\r');
  early_uart_send(str[i]);
  }
 }

其中上半部分的代码内容涉及到硬件的操作，如设置引脚、波特率等，我们无需了解。而这里的条件编译结构则为我们提供了两种uart——mini uart 与 主uart，同时二者对外的字符串发送接口是一样的，对外部保持了统一与抽象屏障

下半部分则是对字符串的具体发送工作，逻辑很简单——使用一个循环溜过去即可，遇到字符串结束符 \0 即停止

代码中在 \n 前方添加 \r 是为了兼容不同终端的换行处理。例如，在早期的Mac OS中，使用的是Carriage Return（CR），即 \r 作为换行符

页表映射

目录

• 页表映射
  • 复习：页表结构
    • 页表基址寄存器
    • 页表地址翻译
    • Chcore的物理地址空间分布
  • Chcore页表映射
    • 总览
    • 宏定义与数据结构声明
      • 内存区域划分
      • 页表项数组定义
      • 页表控制属性描述符
      • 提取索引辅助函数
    • 页表地址映射
      • 低地址映射
      • 高地址映射
      • 配置本地外设内存映射

参考源码文件：mmu.c ，与init_c.c同目录

复习：页表结构

页表基址寄存器

在 AArch64 架构的 EL1 异常级别存在两个页表基址寄存器：ttbr0_el1 和 ttbr1_el1，分别用作虚拟地址空间低地址和高地址的翻译。而关于高低地址的具体范围则由由 tcr_el1 翻译控制寄存器控制。

一般情况下，我们会将 tcr_el1 配置为高低地址各有 48 位的地址范围，即：

• 0x0000_0000_0000_0000～0x0000_ffff_ffff_ffff 为低地址
• 0xffff_0000_0000_0000～0xffff_ffff_ffff_ffff 为高地址

页表地址翻译

有了页表基址寄存器的知识，我们再来看chcore是如何翻译地址的。chcore中页表的地址翻译采取了多级页表的形式，如下图所示：

所谓多级页表，是一种内存管理技术，用于虚拟内存系统中将虚拟地址映射到物理地址。它通过多级层次结构来减少页表所占用的内存空间，并提高页表的查找效率。

在Chcore中，页表一共分为4级：从L0-L2都是对下一级别索引的指针，一直到最后一级L3，才指向具体到页（以4KB粒度）

Chcore的物理地址空间分布

如下图所示，这是我们后面页表映射时确定物理地址的重要信息

接下来，就让我们一起看看具体的页表映射源码吧！

Chcore页表映射

总览

先总览代码，获取一个对源码的大致印象与结构

    #include <common/macro.h>
    #include "image.h"
    #include "boot.h"
    #include "consts.h"
    
    typedef unsigned long u64;
    typedef unsigned int u32;
    
    /* Physical memory address space: 0-1G */
    #define PHYSMEM_START   (0x0UL)
    #define PERIPHERAL_BASE (0x3F000000UL)
    #define PHYSMEM_END     (0x40000000UL)
    
    /* The number of entries in one page table page */
    #define PTP_ENTRIES 512
    /* The size of one page table page */
    #define PTP_SIZE 4096
    #define ALIGN(n) __attribute__((__aligned__(n)))
    u64 boot_ttbr0_l0[PTP_ENTRIES] ALIGN(PTP_SIZE);
    u64 boot_ttbr0_l1[PTP_ENTRIES] ALIGN(PTP_SIZE);
    u64 boot_ttbr0_l2[PTP_ENTRIES] ALIGN(PTP_SIZE);
    u64 boot_ttbr0_l3[PTP_ENTRIES] ALIGN(PTP_SIZE);
    
    u64 boot_ttbr1_l0[PTP_ENTRIES] ALIGN(PTP_SIZE);
    u64 boot_ttbr1_l1[PTP_ENTRIES] ALIGN(PTP_SIZE);
    u64 boot_ttbr1_l2[PTP_ENTRIES] ALIGN(PTP_SIZE);
    u64 boot_ttbr1_l3[PTP_ENTRIES] ALIGN(PTP_SIZE);
    
    #define IS_VALID (1UL << 0)
    #define IS_TABLE (1UL << 1)
    #define IS_PTE   (1UL << 1)
    
    #define PXN            (0x1UL << 53)
    #define UXN            (0x1UL << 54)
    #define ACCESSED       (0x1UL << 10)
    #define NG             (0x1UL << 11)
    #define INNER_SHARABLE (0x3UL << 8)
    #define NORMAL_MEMORY  (0x4UL << 2)
    #define DEVICE_MEMORY  (0x0UL << 2)
    #define RDONLY_S       (0x2UL << 6)
    
    #define SIZE_2M (2UL * 1024 * 1024)
    #define SIZE_4K (4UL * 1024)
    
    #define GET_L0_INDEX(x) (((x) >> (12 + 9 + 9 + 9)) & 0x1ff)
    #define GET_L1_INDEX(x) (((x) >> (12 + 9 + 9)) & 0x1ff)
    #define GET_L2_INDEX(x) (((x) >> (12 + 9)) & 0x1ff)
    #define GET_L3_INDEX(x) (((x) >> (12)) & 0x1ff)
    
    extern int boot_cpu_stack[PLAT_CPU_NUMBER][INIT_STACK_SIZE];
    
    void init_kernel_pt(void)
    {
            u64 vaddr = PHYSMEM_START;
    
            /* TTBR0_EL1 0-1G */
            boot_ttbr0_l0[GET_L0_INDEX(vaddr)] = ((u64)boot_ttbr0_l1) | IS_TABLE
                                                 | IS_VALID | NG;
            boot_ttbr0_l1[GET_L1_INDEX(vaddr)] = ((u64)boot_ttbr0_l2) | IS_TABLE
                                                 | IS_VALID | NG;
    
            boot_ttbr0_l2[GET_L2_INDEX(vaddr)] = ((u64)boot_ttbr0_l3) | IS_TABLE
                                                 | IS_VALID | NG;
    
            /* first 2M, including .init section */
            for (; vaddr < SIZE_2M; vaddr += SIZE_4K) {
                    boot_ttbr0_l3[GET_L3_INDEX(vaddr)] =
                            (vaddr) | UXN /* Unprivileged execute never */
                            | PXN /* Privileged execute never */
                            | ACCESSED /* Set access flag */
                            | NG /* Mark as not global */
                            | INNER_SHARABLE /* Sharebility */
                            | NORMAL_MEMORY /* Normal memory */
                            | IS_PTE | IS_VALID;
    
                    /*
                     * Code in init section(img_start~init_end) should be mmaped as
                     * RDONLY_S due to WXN
                     * The boot_cpu_stack is also in the init section, but should
                     * have write permission
                     */
                    if (vaddr >= (u64)(&img_start) && vaddr < (u64)(&init_end)
                        && (vaddr < (u64)boot_cpu_stack
                            || vaddr >= ((u64)boot_cpu_stack)
                                                + PLAT_CPU_NUMBER
                                                          * INIT_STACK_SIZE)) {
                            boot_ttbr0_l3[GET_L3_INDEX(vaddr)] &= ~PXN;
                            boot_ttbr0_l3[GET_L3_INDEX(vaddr)] |=
                                    RDONLY_S; /* Read Only*/
                    }
            }
    
            /* Normal memory: PHYSMEM_START ~ PERIPHERAL_BASE */
            /* Map with 2M granularity */
            for (; vaddr < PERIPHERAL_BASE; vaddr += SIZE_2M) {
                    boot_ttbr0_l2[GET_L2_INDEX(vaddr)] =
                            (vaddr) /* low mem, va = pa */
                            | UXN /* Unprivileged execute never */
                            | ACCESSED /* Set access flag */
                            | NG /* Mark as not global */
                            | INNER_SHARABLE /* Sharebility */
                            | NORMAL_MEMORY /* Normal memory */
                            | IS_VALID;
            }
    
            /* Peripheral memory: PERIPHERAL_BASE ~ PHYSMEM_END */
            /* Map with 2M granularity */
            for (vaddr = PERIPHERAL_BASE; vaddr < PHYSMEM_END; vaddr += SIZE_2M) {
                    boot_ttbr0_l2[GET_L2_INDEX(vaddr)] =
                            (vaddr) /* low mem, va = pa */
                            | UXN /* Unprivileged execute never */
                            | ACCESSED /* Set access flag */
                            | NG /* Mark as not global */
                            | DEVICE_MEMORY /* Device memory */
                            | IS_VALID;
            }
    
            /* TTBR1_EL1 0-1G */
            /* BLANK BEGIN */
            vaddr = KERNEL_VADDR + PHYSMEM_START;
            boot_ttbr1_l0[GET_L0_INDEX(vaddr)] = ((u64)boot_ttbr1_l1) | IS_TABLE
                                                 | IS_VALID;
            boot_ttbr1_l1[GET_L1_INDEX(vaddr)] = ((u64)boot_ttbr1_l2) | IS_TABLE
                                                 | IS_VALID;
    
            /* Normal memory: PHYSMEM_START ~ PERIPHERAL_BASE
             * The text section code in kernel should be mapped with flag R/X.
             * The other section and normal memory is mapped with flag R/W.
             * memory layout :
             * | normal memory | kernel text section | kernel data section ... |
             * normal memory |
             */
    
            boot_ttbr1_l2[GET_L2_INDEX(vaddr)] = ((u64)boot_ttbr1_l3) | IS_TABLE
                                                 | IS_VALID;
    
            /* the kernel text section was mapped in the first
             * L2 page table in boot_ptd_l1 now.
             */
            BUG_ON((u64)(&_text_end) >= KERNEL_VADDR + SIZE_2M);
            /* _text_start & _text_end should be 4K aligned*/
            BUG_ON((u64)(&_text_start) % SIZE_4K != 0
                   || (u64)(&_text_end) % SIZE_4K != 0);
    
            for (; vaddr < KERNEL_VADDR + SIZE_2M; vaddr += SIZE_4K) {
                    boot_ttbr1_l3[GET_L3_INDEX(vaddr)] =
                            (vaddr - KERNEL_VADDR) | UXN /* Unprivileged execute
                                                            never */
                            | PXN /* Priviledged execute never*/
                            | ACCESSED /* Set access flag */
                            | INNER_SHARABLE /* Sharebility */
                            | NORMAL_MEMORY /* Normal memory */
                            | IS_PTE | IS_VALID;
                    /* (KERNEL_VADDR + TEXT_START ~ KERNEL_VADDR + TEXT_END) was
                     * mapped to physical address (PHY_START ~ PHY_START + TEXT_END)
                     * with R/X
                     */
                    if (vaddr >= (u64)(&_text_start) && vaddr < (u64)(&_text_end)) {
                            boot_ttbr1_l3[GET_L3_INDEX(vaddr)] &= ~PXN;
                            boot_ttbr1_l3[GET_L3_INDEX(vaddr)] |=
                                    RDONLY_S; /* Read Only*/
                    }
            }
    
            for (; vaddr < KERNEL_VADDR + PERIPHERAL_BASE; vaddr += SIZE_2M) {
                    /* No NG bit here since the kernel mappings are shared */
                    boot_ttbr1_l2[GET_L2_INDEX(vaddr)] =
                            (vaddr - KERNEL_VADDR) /* high mem, va = kbase + pa */
                            | UXN /* Unprivileged execute never */
                            | PXN /* Priviledged execute never*/
                            | ACCESSED /* Set access flag */
                            | INNER_SHARABLE /* Sharebility */
                            | NORMAL_MEMORY /* Normal memory */
                            | IS_VALID;
            }
    
            /* Peripheral memory: PERIPHERAL_BASE ~ PHYSMEM_END */
            /* Map with 2M granularity */
            for (vaddr = KERNEL_VADDR + PERIPHERAL_BASE;
                 vaddr < KERNEL_VADDR + PHYSMEM_END;
                 vaddr += SIZE_2M) {
                    boot_ttbr1_l2[GET_L2_INDEX(vaddr)] =
                            (vaddr - KERNEL_VADDR) /* high mem, va = kbase + pa */
                            | UXN /* Unprivileged execute never */
                            | PXN /* Priviledged execute never*/
                            | ACCESSED /* Set access flag */
                            | DEVICE_MEMORY /* Device memory */
                            | IS_VALID;
            }
    
            /*
             * Local peripherals, e.g., ARM timer, IRQs, and mailboxes
             *
             * 0x4000_0000 .. 0xFFFF_FFFF
             * 1G is enough (for Mini-UART). Map 1G page here.
             */
            vaddr = KERNEL_VADDR + PHYSMEM_END;
            boot_ttbr1_l1[GET_L1_INDEX(vaddr)] = PHYSMEM_END | UXN /* Unprivileged
                                                                      execute never
                                                                    */
                                                 | PXN /* Priviledged execute
                                                          never*/
                                                 | ACCESSED /* Set access flag */
                                                 | DEVICE_MEMORY /* Device memory */
                                                 | IS_VALID;
    }

结合注释信息可知，这部分代码主要分为两部分：

• 宏定义与数据结构声明：这部分定义了后面页表配置时相应属性对应的宏以及多级页表中会用到的数据结构；此外，宏定义中还包括内存区域划分与页表大小等信息
• 页表地址映射：即 init_kernel_pt() 函数，我们的页表映射工作即在此完成，也是我们源码解析的重点所在

宏定义与数据结构声明

这一部分主要介绍代码中的宏定义与页表配置相关的数据结构定义

内存区域划分

如下方代码所示：

/* Physical memory address space: 0-1G */
#define PHYSMEM_START   (0x0UL)
#define PERIPHERAL_BASE (0x3F000000UL)
#define PHYSMEM_END     (0x40000000UL)

这三行代码声明的宏将我们要映射的物理地址（一共1G）分为了两部分：普通的RAM内存区域与外设映射区域，其中 UL 表示 unsigned long

其中前者很好理解，就是内核自身的RAM内存，关于后者“外设映射”，可以理解为是在这部分地址开始映射各种硬件外设，例如：

• GPIO控制器
• UART串口
• 中断控制器
• 定时器
• USB控制器等

总体的内存结构即如下图所示：

0x00000000 +-----------------+ <- PHYSMEM_START
           |                 |
           |    普通内存区域   |
           |                 |
0x3F000000 +-----------------+ <- PERIPHERAL_BASE
           |                 |
           |    外设映射区域   |
           |                 |
0x40000000 +-----------------+ <- PHYSMEM_END

页表项数组定义

如下方代码所示：

/* The number of entries in one page table page */
#define PTP_ENTRIES 512
/* The size of one page table page */
#define PTP_SIZE 4096
#define ALIGN(n) __attribute__((__aligned__(n)))
u64 boot_ttbr0_l0[PTP_ENTRIES] ALIGN(PTP_SIZE);
u64 boot_ttbr0_l1[PTP_ENTRIES] ALIGN(PTP_SIZE);
u64 boot_ttbr0_l2[PTP_ENTRIES] ALIGN(PTP_SIZE);
u64 boot_ttbr0_l3[PTP_ENTRIES] ALIGN(PTP_SIZE);

u64 boot_ttbr1_l0[PTP_ENTRIES] ALIGN(PTP_SIZE);
u64 boot_ttbr1_l1[PTP_ENTRIES] ALIGN(PTP_SIZE);
u64 boot_ttbr1_l2[PTP_ENTRIES] ALIGN(PTP_SIZE);
u64 boot_ttbr1_l3[PTP_ENTRIES] ALIGN(PTP_SIZE);

其中数组部分比较好理解，看名称：ttbrx即表示页表基址寄存器，lx表示具体的页表级数（0-3），而数组大小即为定义好的512，是页表页的入口条数

这里再说说这一行代码：

#define ALIGN(n) __attribute__((__aligned__(n)))

这行代码定义了一个对齐属性的宏：__attribute__((__aligned__(n))) 是GCC编译器的一个特殊属性声明，它告诉编译器将变量或数据结构按照n字节边界对齐

例如下面这行声明代码：

u64 boot_ttbr0_l0[PTP_ENTRIES] ALIGN(PTP_SIZE);

这里 ALIGN(PTP_SIZE) 其中 PTP_SIZE = 4096，意味着这个数组将被对齐到4KB边界

而关于为什么需要对齐，这便涉及到硬件架构要求和性能优化的相关知识了，感兴趣的可以自己多查阅了解阅读

页表控制属性描述符

如下方代码所示：

#define IS_VALID (1UL << 0)
#define IS_TABLE (1UL << 1)
#define IS_PTE   (1UL << 1)

#define PXN            (0x1UL << 53)
#define UXN            (0x1UL << 54)
#define ACCESSED       (0x1UL << 10)
#define NG             (0x1UL << 11)
#define INNER_SHARABLE (0x3UL << 8)
#define NORMAL_MEMORY  (0x4UL << 2)
#define DEVICE_MEMORY  (0x0UL << 2)
#define RDONLY_S       (0x2UL << 6)

这部分定义了页表的属性描述符，在配置页表的时候，我们可以通过将待配置的地址与之进行或运算（即 | ） 即可

而页表属性的具体含义通常与内存访问权限等相关，具体见下，亦可以自行做更多了解：

• UXN : 用户模式（非特权态）下不可执行
• PXN : 特权模式（特权态）下不可执行
• RDONLY_S : 只读访问
• INNER_SHARABLE : 内部可共享
• NORMAL_MEMORY/DEVICE_MEMORY : 内存类型标识
• NG : 非全局页面标识

提取索引辅助函数

如下方代码所示：

#define GET_L0_INDEX(x) (((x) >> (12 + 9 + 9 + 9)) & 0x1ff)
#define GET_L1_INDEX(x) (((x) >> (12 + 9 + 9)) & 0x1ff)
#define GET_L2_INDEX(x) (((x) >> (12 + 9)) & 0x1ff)
#define GET_L3_INDEX(x) (((x) >> (12)) & 0x1ff)

这部分是用于将虚拟地址提取出对应位置的索引的辅助函数，从L0到L3都有。其中各个数字的含义如下：

• 12: 页内偏移位数（4KB页面 = 2^12）
• 9: 每级页表索引的位数（512个表项 = 2^9）
• 0x1ff: 9位掩码（二进制：111111111），是一个mask操作

绝知此事要躬行，我们假设有一个虚拟地址：

位数:   |   9位   |   9位   |   9位   |   9位   |   12位   |
内容:   | L0索引  | L1索引   | L2索引  | L3索引  | 页内偏移  |

那么各辅助函数的功能即如下所述：

• GET_L0_INDEX: 右移39位，获取最高的9位
• GET_L1_INDEX: 右移30位，获取第二个9位
• GET_L2_INDEX: 右移21位，获取第三个9位
• GET_L3_INDEX: 右移12位，获取第四个9位

页表地址映射

工欲善其事，必先利其器。上面的介绍为我们解析配置页表部分的源码扫清了障碍，现在，我们正式进入 init_kernel_pt() 函数，来对chcore的页表映射逻辑一窥究竟

浏览代码不难发现，本函数主要分为两大块：低地址映射与高地址映射，前者为用户态，后者为内核态，分别由相应的页表基址寄存器控制。其中各自具体配置手段相似，区别在于内核态配置时需要加上相应的偏移量，否则配置就是乱的

低地址映射

我们将详细讲解这一部分，对于后面的高地址映射，我们将只说明不同的地方，其余大体上是相似的

• 首先是设置多级页表之间的链接关系

        u64 vaddr = PHYSMEM_START;

        /* TTBR0_EL1 0-1G */
        boot_ttbr0_l0[GET_L0_INDEX(vaddr)] = ((u64)boot_ttbr0_l1) | IS_TABLE
                                             | IS_VALID | NG;
        boot_ttbr0_l1[GET_L1_INDEX(vaddr)] = ((u64)boot_ttbr0_l2) | IS_TABLE
                                             | IS_VALID | NG;

        boot_ttbr0_l2[GET_L2_INDEX(vaddr)] = ((u64)boot_ttbr0_l3) | IS_TABLE
                                             | IS_VALID | NG;

这里将vaddr设置为最开始的物理内存起始，然后进行了相应的链接关系配置

这里完成了初始化工作后，后面便开始了具体的配置

• 初始2M内存，以4KB粒度映射，注意这里包含.init部分，需要做特殊处理

        /* first 2M, including .init section */
        for (; vaddr < SIZE_2M; vaddr += SIZE_4K) {
                boot_ttbr0_l3[GET_L3_INDEX(vaddr)] =
                        (vaddr) | UXN /* Unprivileged execute never */
                        | PXN /* Privileged execute never */
                        | ACCESSED /* Set access flag */
                        | NG /* Mark as not global */
                        | INNER_SHARABLE /* Sharebility */
                        | NORMAL_MEMORY /* Normal memory */
                        | IS_PTE | IS_VALID;

                /*
                 * Code in init section(img_start~init_end) should be mmaped as
                 * RDONLY_S due to WXN
                 * The boot_cpu_stack is also in the init section, but should
                 * have write permission
                 */
                if (vaddr >= (u64)(&img_start) && vaddr < (u64)(&init_end)
                    && (vaddr < (u64)boot_cpu_stack
                        || vaddr >= ((u64)boot_cpu_stack)
                                            + PLAT_CPU_NUMBER
                                                      * INIT_STACK_SIZE)) {
                        boot_ttbr0_l3[GET_L3_INDEX(vaddr)] &= ~PXN;
                        boot_ttbr0_l3[GET_L3_INDEX(vaddr)] |=
                                RDONLY_S; /* Read Only*/
                }
        }

主体的配置过程其实就是这样的：

相应的页表级[辅助函数获取索引(vaddr)] = (vaddr) | 一大堆属性

这里还要注意一下for循环的末尾，有一个对.init部分内存的特殊设置—— RDONLY_S ，即只读

• 配置普通RAM内存与外设内存

        /* Normal memory: PHYSMEM_START ~ PERIPHERAL_BASE */
        /* Map with 2M granularity */
        for (; vaddr < PERIPHERAL_BASE; vaddr += SIZE_2M) {
                boot_ttbr0_l2[GET_L2_INDEX(vaddr)] =
                        (vaddr) /* low mem, va = pa */
                        | UXN /* Unprivileged execute never */
                        | ACCESSED /* Set access flag */
                        | NG /* Mark as not global */
                        | INNER_SHARABLE /* Sharebility */
                        | NORMAL_MEMORY /* Normal memory */
                        | IS_VALID;
        }

        /* Peripheral memory: PERIPHERAL_BASE ~ PHYSMEM_END */
        /* Map with 2M granularity */
        for (vaddr = PERIPHERAL_BASE; vaddr < PHYSMEM_END; vaddr += SIZE_2M) {
                boot_ttbr0_l2[GET_L2_INDEX(vaddr)] =
                        (vaddr) /* low mem, va = pa */
                        | UXN /* Unprivileged execute never */
                        | ACCESSED /* Set access flag */
                        | NG /* Mark as not global */
                        | DEVICE_MEMORY /* Device memory */
                        | IS_VALID;
        }

不难发现总体上的代码逻辑是相似的，那如何区分不同的内存呢？——通过页表属性即可

在这一部分我们以2M的粒度对普通内存+外设内存完成了映射，注意在2M粒度下，我们的页表级是L2

高地址映射

总体上和低地址映射是相似的，不同之处在于二者之间有一个偏移量，因此我们在配置高地址映射的时候需要加上这一部分，它由相应的页表基址寄存器控制。在代码中，即为 KERNEL_VADDR ，定义在 image.h 头文件中

这里我们只举一个例子来说明这一点，就不全部讲解了

/* TTBR1_EL1 0-1G */
        /* BLANK BEGIN */
        vaddr = KERNEL_VADDR + PHYSMEM_START;
        
     ...

        for (; vaddr < KERNEL_VADDR + PERIPHERAL_BASE; vaddr += SIZE_2M) {
                /* No NG bit here since the kernel mappings are shared */
                boot_ttbr1_l2[GET_L2_INDEX(vaddr)] =
                        (vaddr - KERNEL_VADDR) /* high mem, va = kbase + pa */
                        | UXN /* Unprivileged execute never */
                        | PXN /* Priviledged execute never*/
                        | ACCESSED /* Set access flag */
                        | INNER_SHARABLE /* Sharebility */
                        | NORMAL_MEMORY /* Normal memory */
                        | IS_VALID;
        }

    ...

以配置普通RAM内存这一段为例，这里初始化 vaddr 时即加上了对应的偏移量，在 for 循环中也有相应的体现，这便是高地址映射时不同的地方

配置本地外设内存映射

注意到1G-4G这部分内存还没有用到，这部分是留给配置本地外设用的。在chcore中，我们只配置了1G，但是这是足够的，如下方代码所示，这也是页表映射的最后一段：

        /*
         * Local peripherals, e.g., ARM timer, IRQs, and mailboxes
         *
         * 0x4000_0000 .. 0xFFFF_FFFF
         * 1G is enough (for Mini-UART). Map 1G page here.
         */
        vaddr = KERNEL_VADDR + PHYSMEM_END;
        boot_ttbr1_l1[GET_L1_INDEX(vaddr)] = PHYSMEM_END | UXN /* Unprivileged
                                                                  execute never
                                                                */
                                             | PXN /* Priviledged execute
                                                      never*/
                                             | ACCESSED /* Set access flag */
                                             | DEVICE_MEMORY /* Device memory */
                                             | IS_VALID;

1G的内存配置是便直接使用L1级别的页表了，这也体现了多级页表的特点

教材补充

一、ChCore启动与异常向量表初始化

1、特权级别与系统ISA

为了区分应用程序和操作系统的运行权限，CPU为两者提供了不同的特权级别：用户态和内核态。ISA（指令集架构）作为CPU向软件提供的接口，也对应地分为用户ISA和系统ISA，在用户态运行的软件只能使用用户ISA，在内核态运行的软件则可以同时使用系统ISA和用户ISA。

我们举例说明：

（1）通用寄存器、栈寄存器、条件码寄存器、运算指令等，都属于用户ISA

（2）系统ISA则包含系统状态、系统寄存器与系统指令。其中，系统状态包括当前CPU的特权级别、CPU发生错误时引发错误的指令地址、程序运行状态等。存储这些状态的寄存器称为系统寄存器，这些寄存器只能由运行在内核态的软件通过系统指令来访问。

案例分析：ARM的特权级别和系统ISA

接下来我们以AArch64为例介绍CPU特权级别和系统ISA的一种具体实现。

在AArch64中的特权级别被称为异常级别（Exception Level, EL），共分为4个级别，具体如下：

• EL0：用户态，应用程序通常运行在该特权级别。
• EL1：内核态，操作系统通常运行在该特权级别。
• EL2：用于虚拟化场景，虚拟机监控器通常运行在该特权级别。
• EL3：与安全特性TrustZone相关，负责普通世界和安全世界之间的切换。

这里需要注意的一点在于，对于许多ISA来说，当CPU运行在内核态运行用户ISA，一般会使用用户ISA的寄存器（如SP），这也是为什么从用户态切换到内核时，首先需要将用户态寄存器的值保存到内存。但是AArch64的做法是，为一些常用的用户态寄存器在不同特权级提供不同的硬件副本。例如对于栈寄存器SP，AArch64提供了SP_EL0（用户态）与SP_EL1（内核态）。其中，用户态在函数调用时使用SP_EL0，无法访问SP_EL1；内核态则使用SP_EL1。但也有权限读写SP_EL0。

AArch64的系统寄存器负责保存硬件系统状态，以及为操作系统提供管理硬件的接口。系统ISA提供了mrs和msr两条特权指令，其作用是从系统寄存器中读取值（获取系统信息）或向系统寄存器中写入值（控制系统状态）。系统ISA的指令只有在特权态才能运行，CPU在执行相关指令前会先根据PSTATE中的状态来判断是否合法。例如，当PSTATE记录当前运行级别为EL0时，CPU运行的指令无权访问ELREL1系统寄存器。由于AArch64有多个特权级，因此对于系统寄存器，也需要通过类似的后缀来表明这些寄存器在哪一个特权级下使用，例如TTBR0EL1（一阶段页表基地址寄存器）和TTBR0_EL2（用于虚拟化的二阶段页表基地址寄存器）。

2、异常机制与异常向量表

经过ICS的学习，相信我们的读者对于异常机制已经非常熟悉了，这里我们用一张图回顾一下异常控制流

当操作系统发生异常事件导致“下陷”到内核态时，CPU只允许从固定的入口开始执行。为此，操作系统需要提前将代码的入口地址“告诉”处理器。对不同类型的异常事件，CPU通常支持设置不同的入口。这些入口通常以一张表的形式记录在内存中，也就是异常向量表，由操作系统负责构造。在系统启动后，操作系统会将异常向量表的内存地址写入CPU上的一个特殊寄存器——异常向量表基地址寄存器（如AArch64中的VBAR_EL1寄存器），然后开启中断，这样便完成了异常机制的初始化。

3、将目光投向ChCore

经过我们前置知识的铺垫，我们了解到，异常向量表定义了操作系统的入口，因此异常向量表的初始化是启动后立即要做的重要步骤。

在计算机启动时，CPU 执行的第一段代码其实并非 ChCore 的代码。以在树莓派上运行 ChCore为例，在加电后，主板中的固件和 SD 卡中的 bootloader 将先后被加载到内存并运行，进行基本的初始化工作。之后，ChCore 的二进制文件将被 bootloader 加载到内存中约定好的位置，这时才从头开始执行 ChCore 的代码。

这里我们的读者可能会疑惑：bootloader是什么？有什么作用呢？

1 _start:
2 mrs x8, mpidr_el1
3 and x8, x8, #0xFF
4 cbz x8, primary
5
6 /* Code for secondary core */
7 ...
8 /* Init exception vector */
9 bl set_exception_vector
10 ...
11
12 primary:
13 /* Code for primary core */
14 /* init UART, Virtual Memory mapping in C */
15 ...
16 /* Init exception vector */
17 adr x0, el1_vector
18 msr vbar_el1,x0
19 ...
20
21 /* Exception Table */
22 el1_vector:
23 /* entry for other type of exception */
24...
25
26 /* entry for synchronous exception from ELO */
27 align 7   // 128 bytes for each entry
28 b sync_e10_64
29
30 /* entry for interrupt from ELO */
31 align 7  //128 bytes for each entry
32 b irq_el0_64
33
34 /* entry for other type of exception */
35 ...

如代码片段所示，ChCore起始位置的代码为_start，这便是进入ChCore时执行的第一段代码。在多核机器中，所有核心都会同时开始执行_start，ChCore 需要选择某个 CPU 核心作为主要核心（通常是第一个）来初始化操作系统，同时其他核心将被暂时阻塞。AArch64为我们提供了MPIDR这个系统寄存器来获取当前CPU 核心的编号。

通过系统指令 mrs x8，mpidr_el1 来读取 MPIDR 的值，然后判断当前核心是否为主核。主核进入初始化流程，其他核心等待主核完成初始化。

这里主要关注其中对异常向量表的初始化。在上述代码中，异常向量表存放在el1_vector代表的位置。在AArch64中，异常向量表中的每一项都可以存放128字节的指令，但ChCore只存放了一条跳转指令，用于跳转到不同异常事件对应的处理函数。例如，对于来源于用户态的同步异常，内核将跳转到sync_el0_64，并在其中保存通用寄存器，根据异常的详细信息进行不同的处理；对于异步异常（即中断），内核将跳转到irq_el0_64，并执行相应的处理。

在编译ChCore时，异常向量表的内容已按照AArch64的布局在二进制文件中构造好了。在启动阶段，异常向量表便作为二进制文件的一部分被bootloader直接加载到内存中。因此，进入内核后，ChCore只需要将异常向量表的起始地址放入指定的系统寄存器，便可完成异常向量表的初始化工作。

上述代码中，ChCore将el1_vector代表的异常向量表起始地址，通过msr指令存储到VBAR_ELl寄存器中。之后发生异常事件时，处理器便能跳转到VBAR_ELl寄存器指向的异常向量表中对应的表项，并跳转到操作系统内核进行处理。

4、系统调用的优化

• 在上文中，我们讲述了通过异常机制实现系统调用，但是这种方法实现的系统调用需要执行特权级别切换、上下文保存等操作，十分费时。如何绕过费时的异常机制来实现系统调用呢？
• 第一种方法是将一部分数据以只读的形式共享给应用，但如果系统调用需要修改内核中的变量或者在运行过程中需要读取更多内核数据，这种方法就不适用了。
• 第二种方法是应用以“向某一内存页写入请求”的方式发起系统调用，并通过轮询等待系统调用完成，内核同样通过轮询来等待用户的请求，然后执行系统调用，并将系统调用的返回值写入同一块内存页以表示完成。

面临的问题及解决方法

（1）如何处理顺序处理时延问题？——让多个CPU核心同时运行在内核态并轮询用户的请求

（2）只有一个CPU核心时该怎么办？——轮询改为批处理。即当CPU运行在用户态时，应用程序一次发起多个系统调用请求，同样将请求和参数写入共享内存页，然后CPU切换到内核态，内核一次性将所有系统调用处理完，把结果写入共享内存页，再切换回用户态运行。

二、ChCore虚拟内存管理

1、CPU的职责：内存地址翻译

1、地址翻译

CPU中的**内存管理单元(MMU)**负责地址翻译：应用进程在CPU核心上运行期间，使用的虚拟地址会由MMU进行翻译。当需要访问物理内存时，MMU翻译出来的物理地址将会通过总线传到物理内存，从而完成物理内存读写请求。

现代CPU中常包含转址旁路缓存(Translation Lookaside Buffer,TLB)作为加速地址翻译的部件(TLB是MMU 内部的硬件单元）。

2、分页机制

页表：操作系统为每个应用进程构造的一张记录从虚拟页到物理页的映射关系表；

页表基地址寄存器：存储页表的起始地址，在AArch64平台中称为TTBR。

在页表机制下，每个虚拟地址由两部分组成：第一部分标识虚拟地址的虚拟页号；第二部分标识虚拟地址的页内偏移。在地址翻译过程中，MMU首先解析得到虚拟地址中的虚拟页号，并通过虚拟页号去该应用进程的页表中找到对应条目，然后取出条目中存储的物理页号，最后用该物理页号对应的物理页起始地址加上虚拟地址的页内偏移，得到最终的物理地址。

3、多级页表

为压缩页表大小，MMU采用了多级页表。前面提到，在使用简单的单级页表时，一个虚拟地址将被划分为两部分——虚拟页号和页内偏移。当使用k级页表时，一个虚拟地址的虚拟页号将被进一步地划分成k个部分（虚拟页号0，……，虚拟页号i，0≤i<k),其中虚拟页号i对应该虚拟地址在第i级页表中的索引。当任意一级页表中的某一个条目为空时，该条目对应的下一级页表不需要存在，依次类推，接下来的页表同样不需要存在。因此，多级页表的设计极大减少了页表占用的空间大小。换句话说，多级页表允许整个页表结构中出现“空洞”，而单级页表则需要每一项都实际存在。通常，应用进程的虚拟地址空间中绝大部分的虚拟地址都不会被使用，所以多级页表通常具有很多“空洞”，从而能够极大地节约所占空间。

AArch64体系结构下一般为虚拟地址低48位参与地址翻译，页表级数为4级，虚拟页大小为4KB。

4、页表项与大页

中间级的页表项直接指向物理页时，其指向的是大页（比下一级页表项指向的物理页大小更大）。此外页表项也可以存储一些属性位，允许操作系统设置读写等权限。若实际访问所需权限和页表项中设置的权限不一致，则MMU会在地址翻译中出发访问异常。下图为页表项格式

5、TLB：页表的缓存

为了减少多级页表下地址翻译过程中的访存次数， MMU 引入转址旁路缓存（TranslationLookaside Buffer， TLB）部件来加速地址翻译的过程。具体来说， TLB缓存了虚拟页号到物理页号的映射关系。我们可以把 TLB 简化成存储着键值对的哈希表，其中键是虚拟页号，值是物理页号。MMU 会先把虚拟页号作为键去查询 TLB中的缓存项，若找到则可直接获得对应的物理页号而无须再查询页表。我们称通过TLB能够直接完成地址翻译的过程为TLB命中（TLB Hit），反之为TLB不命中（TLB Miss）。

2、操作系统的职责：管理页表映射

CPU在上电启动后会默认使用物理地址，这是因为MMU的地址翻译功能还未开启，而操作系统则负责在初始化过程中启用该功能。一旦启用MMU地址翻译，CPU会根据页表对指令执行中涉及的地址进行翻译，即认为这些地址都是虚拟地址，因而操作系统和应用进程在后续运行中都是使用虚拟地址。因此，操作系统除了需要为每个应用进程设置页表外，也需要为自己配置页表。

通常，操作系统为自己配置的页表具有两个特点：

第一，操作系统一般使用高虚拟地址，比如对于AArch64来说，操作系统使用高16位为1的虚拟地址；应用进程使用低虚拟地址，在AArch64中即为高16位为0的虚拟地址。

第二，操作系统一般会一次性将全部物理内存映射到虚拟地址空间中。映射方式为直接映射（Direct Mapping），即虚拟地址=物理地址+固定偏移。操作系统所使用的虚拟地址空间也称为内核地址空间。通过上述固定偏移的页表映射方式，操作系统能够在内核地址空间中很方便地在物理地址和虚拟地址之间进行转换。当操作系统需要访问一个物理地址时，仅需要访问该物理地址加上固定偏移的虚拟地址即可。

下图为AArch64体系结构下的操作系统页表和应用进程页表

3、ChCore虚拟内存管理

1、ChCore内核页表初始化

由于需要为应用程序提供虚拟内存抽象，操作系统启动期间会启用MMU。在启用后，MMU也会对操作系统执行期间使用的地址进行翻译，因此操作系统在启用MMU之前需要首先初始化自己的页表。

通常，操作系统对页表的配置分为两个阶段：第一阶段是启动初期，此时操作系统运行在低地址区域，页表将虚拟地址映射为完全相同的物理地址（VA=PA）；第二阶段是在跳转到高地址运行后，页表将虚拟地址映射为物理地址加上固定偏移（VA=PA+偏移量）。

1 BEGIN_FUNC(_start) 
2   //内核运行的第一条指令：获取CPUID
3 mrs x8, mpidr_el1 
4 and x8, x8, #0xFF 
5   //若当前是0号CPU，则跳转到主CPU初始化处执行
6 cbz x8, primary 
7 ...
8 
9 primary: 
10
11  //设置特权级别为EL1，即进入内核态执行
12 bl change_el_to_ell 
13
14  //设置内核启动期间的栈桢
15 adr x0, boot_cpu_stack 
16 add x0, x0, #INIT_STACK_SIZE 
17 mov sp, x0 
18
19  //调用C代码编写的初始化函数
20 bl init 
21
22  //init函数不返回，控制流不会到这里
23 b .
24 END_FUNC(_start) 
25
26
27 void init(void) 
28{
29 ...
30 
31  //初始化内核页表 
32 init_kernel_pt(); 
33
34  //启用MMU 
35 el1_mmu_activate(); 
36
37  //该函数位于高地址，且不返回
38 do_other_initialization(); 
39
40  //控制流不会到这里
41 }

延续上一节的代码，当判断为主核时，进入主核的初始化流程。

ChCore第一步会先把CPU特权级别设置为EL1（对应内核态），然后设置栈桢并调用C代码编写的初始化函数。

现在我们将目光放到下面的init函数上。在该函数中，ChCore首先配置自己的页表(init_kernel_pt函数)，其中会配置两份页表(boot_ttbr0_10负责 低地址范围的映射，而boot_ttbr1_10对应高地址范围的映射），然后启用MMU。

操作系统启动时的第一条指令一般在较低的地址，这是来自硬件/固件的要求。应用程序通常使用低地址，而操作系统使用高地址，所以操作系统启动期间需要跳转到高地址运行。因而ChCore在启用MMU后，会跳转到高地址继续执行剩余的初始化操作，此后将使用TTBR1_EL1中存储的页表进行翻译。

1 #define SCTLR_EL1M (1)
2
3 BEGIN_FUNC(el1_mmu_activate)
4 ...
5 
6 //设置页表基地址寄存器
7 adrp x8, boot_ttbr0_10 
8 msr ttbroel1, x8 
9 adrp x8, boot_ttbr110 
10 msr ttbr1el1, x8 
11 ...
12 
13 mrs x8, sctlr_el1 
14 ...
15 orr x8, x8, #SCTLR_EL1_M 
16 msr sctlr_el1, x8 
17 isb 
18 
19 ...
20 END_FUNC(e11_mmu_activate) 

上面这段代码展示了如何启用MMU，el1_mmu_activate函数首先在两个页表基地址寄存器中写入页表基地址，然后将系统寄存器sctlr_el1的第0位设置为1，即SCTLR_EL1_M位，从而开启MMU。

注意，从启动第一条指令到el1_mmu_activate 函数中的isb指令之间，MMU都未开启，ChCore使用的是物理地址；而从isb指令开始，由于MMU已经开启，指令地址也会经过地址翻译。假设isb指令的上一条msr指令所在的物理地址是0x81000（即存放在物理内存中的位置），那么isb指令的物理地址则是0x81004。

CPU在执行msr指令时，PC中存放的指令地址是0x81000，由于MMU尚未启用，CPU是通过物理地址0x81000取出该指令的。CPU执行完msr指令后，PC中存放的指令地址是0x81004（准备执行isb指令），由于MMU已经启用，CPU中的MMU会对PC中的地址进行地址翻译（把0x81004作为虚拟地址），而isb指令的物理地址是0x81004，所以页表中的地址映射需要虚拟地址与物理地址完全相同。

下图展示了ChCore的启动过程：先使用物理过程，在使用经由启动页表翻译的虚拟地址，之后使用经由内核页表翻译的虚拟地址。

2、ChCore内存管理

1 struct vmspace
2 //vmregion链表
3 struct list_head vmr_list;
4 //页表基地址（虚拟地址）
5 vaddr_t *pgtbl;
6 //用于修改地址空间的并发控制
7 struct lock vmspace_lock
8
9 ...
10 };

上述代码片段给出了虚拟地址空间vmspace结构体中的三个成员变量。

vmr_list是链表头，指向一个由虚拟地址区域组成的链表。应用进程的虚拟空间最大可达2^48，但是往往其中大部分都是未被使用的区域。ChCore将一个应用地址空间内有效使用的虚拟地址区域保存在该链表里。

gtbl存储着这个虚拟地址空间对应的页表基地址。需要注意的是，pgtbl存储的地址是虚拟地址，由操作系统使用；对应的物理地址填在页表基地址寄存器中，由MMU使用。ChCore在映射内核地址空间的时候，会保证内核虚拟地址和真正映射的物理地址之间相差一个固定的偏移量（直接映射）。因此，ChCore很容易根据pgtbl这个虚拟地址计算出真正应该写入页表基地址寄存器中的物理地址（在vmspace 中记录页表基地址的物理地址也是可行的，因为直接映射使虚拟地址和物理地址之间的转换变得很方便）。

1 struct vmregion {
2 //链表中的一个节点，存储着prev和next指针
3 struct list_head node; 
4 //区域起始地址 
5 vaddr_t start; 
6 //区域大小 
7 size_t size; 
8 //访问权限 
9 vmr_prop_t perm; 
10 //对应的物理内存对象
11 struct pmobject *pmo; 
12 }； 

上述代码给出了虚拟地址区域vmregion结构体中的成员变量。其中，成员变量 node将不同的vmregion对象连成链表，成员变量 start 和size分别标识该虚拟内存区域的起始地址和区域大小，成员变量perm标识该区域的读、写、执行权限，最后一个成员变量pmo标识映射到该区域的物理内存对象。实验内核采用简单的映射关系，只有一个物理内存对象映射到一个虚拟内存区域。

ChCore实验内核以对象的形式进行物理内存资源的管理。物理内存对象pmobject分为不同的类型，由type成员标识，包含以下类型。

拓展阅读与思考

前情提要

Lab 1 主要介绍Chcore 启动过程中的 工作 ，这些工作包括 启动cpu 0号核，切换异常级别 ，跳转到第一行C代码 ，初始化串口输出 ，启用MMU ，配置页表。

而在其他的系统之中，有不少的异同点，在下文之中我们将选取几个代表性的系统做对比分析

下文大纲

1. 我们将把 SJTU Chcore 系统 与 MIT xv6 系统进行比较，分析内核启动的相通点与不同点并探讨可能的问题。
2. 我们将基于 Linux 介绍执行系统内核代码前，bootloader相关的粗略工作。

正文

Part 1 : Chcore 和 XV6 的对比

Part 1.1：基本分析

我们先看一下 xv6 book 关于启动过程中的工作：

我们先不讨论内核代码在加载到内存之前系统做的工作，我们首先比较两个系统第一步执行内核代码的不同之处。对于Xv6而言，它的第一步是直接建立stack。而由Chcore文档我们知道进入内核第一步是通过一系列代码只让一个CPU Core工作，而其他CPU Core停止执行初始化工作 然后这��个CPU core切换异常级别接下来才是建立stack。那为什么xv6 会直接建立stack？我们接着看代码。两个系统在建立了stack都跳转到内核的第一行C代码进行初始化。

我们先看一下 xv6 book 关于这个过程中的工作：

第一句话解释了为什么xv6不是在建立stack之前切换异常级别：因为start级别中的代码只能在machine mode中执行，执行完之后再切换到supervisor mode。machine mode 相当于EL3，supervisor mode 相当于 EL2。我们接着看，我们使用一个指令切换到supervisor mode同时start 函数结束后将会返回到main.c 中（细节自行了解）。main.c 也是进行初始化工作，我们接着看代码：

#include "types.h"
#include "param.h"
#include "memlayout.h"
#include "riscv.h"
#include "defs.h"

volatile static int started = 0;

// start() jumps here in supervisor mode on all CPUs.
void
main()
{
  if(cpuid() == 0){
    consoleinit();
    printfinit();
    printf("\n");
    printf("xv6 kernel is booting\n");
    printf("\n");
    kinit();         // physical page allocator
    kvminit();       // create kernel page table
    kvminithart();   // turn on paging
    procinit();      // process table
    trapinit();      // trap vectors
    trapinithart();  // install kernel trap vector
    plicinit();      // set up interrupt controller
    plicinithart();  // ask PLIC for device interrupts
    binit();         // buffer cache
    iinit();         // inode table
    fileinit();      // file table
    virtio_disk_init(); // emulated hard disk
    userinit();      // first user process
    __sync_synchronize();
    started = 1;
  } else {
    while(started == 0)
      ;
    __sync_synchronize();
    printf("hart %d starting\n", cpuid());
    kvminithart();    // turn on paging
    trapinithart();   // install kernel trap vector
    plicinithart();   // ask PLIC for device interrupts
  }

  scheduler();        
}

main.c代码的结构好像似曾相识，仔细一看，这不就是和Chcore 中CPU Core启动一样吗！到此我们发现了内核代码的 consistent design。而在真实世界中linux也如此但也更复杂（链接：https://xinqiu.gitbooks.io/linux-inside-zh/content/Initialization/linux-initialization-4.html，我也未明白linux 内核的mode change故未放上链接）。

我们接着看 main.c 代码大体逻辑与Chcore相同 : 先初始化console (类比Chcore中的 uart_init),然后便开始启用MMU 并 初始化页表。这部分只拓展Lab1相关部分故不分析后面部分。

我们接下来看Xv6的页表初始化（地址映射），Xv6 内���映射相关代码代码与Chcore 中设置高地址页表思路相同，相关代码放在文章末尾。

Part 1.2：一个问题

看完之后我们可能会有问题，虽然虽然两个系统都会进行以上CPU core启动顺序相关工作，但代码位置却并不相同，我们下面分析一下这是为什么。那我们便要好好看下Chcore Lab1文档中的思考题12（在一开始我们暂停了三个其他核心的执行，根据现有代码简要说明它们什么时候会恢复执行。思考为什么一开始只让 0 号核心执行初始化流程？）

我们先看代码：

#include <common/asm.h>

.extern arm64_elX_to_el1
.extern boot_cpu_stack
.extern secondary_boot_flag
.extern secondary_init_c
.extern clear_bss_flag
.extern init_c

BEGIN_FUNC(_start)
 mrs x8, mpidr_el1
 and x8, x8, #0xFF
 cbz x8, primary

 /* Wait for bss clear */
wait_for_bss_clear:
 adr x0, clear_bss_flag
 ldr x1, [x0]
 cmp     x1, #0
 bne wait_for_bss_clear

 /* Set cntkctl_el1 to enable cntvct_el0.
         * Enable it when you need to get current tick
         * at EL0, e.g. Running aarch64 ROS2 demos
 mov x10, 0b11
 msr cntkctl_el1, x10 */

 /* Turn to el1 from other exception levels. */
 bl  arm64_elX_to_el1

 /* Prepare stack pointer and jump to C. */
 mov x1, #0x1000
 mul x1, x8, x1
 adr  x0, boot_cpu_stack
 add x0, x0, x1
 add x0, x0, #0x1000
        mov sp, x0

wait_until_smp_enabled:
 /* CPU ID should be stored in x8 from the first line */
 mov x1, #8
 mul x2, x8, x1
 ldr x1, =secondary_boot_flag
 add x1, x1, x2
 ldr x3, [x1]
 cbz x3, wait_until_smp_enabled

 /* Set CPU id */
 mov x0, x8
 bl  secondary_init_c

primary:
 /* Turn to el1 from other exception levels. */
 bl  arm64_elX_to_el1

 /* Prepare stack pointer and jump to C. */
 adr  x0, boot_cpu_stack
 add  x0, x0, #0x1000
 mov  sp, x0

 bl  init_c

 /* Should never be here */
 b .
END_FUNC(_start)

以上代码有两部分我们应该注意：wait_for_bss_clear 和 wait_until_smp_enabled。当第一个CPU core执行到 init.c 的时候会调用clear_bss 将clear_bss_flag 设置为0 然后其他CPU core 会切换异常级别并建立stack但会停在wait_until_smp_enabled这部分。第一个CPU core 继续执行 init.c 中的代码（初始化串口输出，配置页表，启用MMU,然后调用start_kernel 跳转到main.c ）第一个CPU Core 在main.c 中执行完时钟，调度器，锁的初始化后其他CPU Core 开始初始化。故答案应是在多核系统中，时钟、调度器和锁是多个核心共享的资源。在初始化时，如果多个核心同时访问这些资源，可能会引发竞争条件或未定义的行为。

接着看XV6代码：

review : the order is entry.S -> init.c -> main.c

entry.S:
        # qemu -kernel loads the kernel at 0x80000000
        # and causes each hart (i.e. CPU) to jump there.
        # kernel.ld causes the following code to
        # be placed at 0x80000000.
.section .text
.global _entry
_entry:
        # set up a stack for C.
        # stack0 is declared in start.c,
        # with a 4096-byte stack per CPU.
        # sp = stack0 + (hartid * 4096)
        la sp, stack0
        li a0, 1024*4
        csrr a1, mhartid
        addi a1, a1, 1
        mul a0, a0, a1
        add sp, sp, a0
        # jump to start() in start.c
        call start
spin:
        j spin
      
start.c:
// entry.S jumps here in machine mode on stack0.
void
start()
{
  // set M Previous Privilege mode to Supervisor, for mret.
  unsigned long x = r_mstatus();
  x &= ~MSTATUS_MPP_MASK;
  x |= MSTATUS_MPP_S;
  w_mstatus(x);

  // set M Exception Program Counter to main, for mret.
  // requires gcc -mcmodel=medany
  w_mepc((uint64)main);

  // disable paging for now.
  w_satp(0);

  // delegate all interrupts and exceptions to supervisor mode.
  w_medeleg(0xffff);
  w_mideleg(0xffff);
  w_sie(r_sie() | SIE_SEIE | SIE_STIE | SIE_SSIE);

  // configure Physical Memory Protection to give supervisor mode
  // access to all of physical memory.
  w_pmpaddr0(0x3fffffffffffffull);
  w_pmpcfg0(0xf);

  // ask for clock interrupts.
  timerinit();

  // keep each CPU's hartid in its tp register, for cpuid().
  int id = r_mhartid();
  w_tp(id);

  // switch to supervisor mode and jump to main().
  asm volatile("mret");
}

// ask each hart to generate timer interrupts.
void
timerinit()
{
  // enable supervisor-mode timer interrupts.
  w_mie(r_mie() | MIE_STIE);
  
  // enable the sstc extension (i.e. stimecmp).
  w_menvcfg(r_menvcfg() | (1L << 63)); 
  
  // allow supervisor to use stimecmp and time.
  w_mcounteren(r_mcounteren() | 2);
  
  // ask for the very first timer interrupt.
  w_stimecmp(r_time() + 1000000);
}

main.c:

#include "types.h"
#include "param.h"
#include "memlayout.h"
#include "riscv.h"
#include "defs.h"

volatile static int started = 0;

// start() jumps here in supervisor mode on all CPUs.
void
main()
{
  if(cpuid() == 0){
    consoleinit();
    printfinit();
    printf("\n");
    printf("xv6 kernel is booting\n");
    printf("\n");
    kinit();         // physical page allocator
    kvminit();       // create kernel page table
    kvminithart();   // turn on paging
    procinit();      // process table
    trapinit();      // trap vectors
    trapinithart();  // install kernel trap vector
    plicinit();      // set up interrupt controller
    plicinithart();  // ask PLIC for device interrupts
    binit();         // buffer cache
    iinit();         // inode table
    fileinit();      // file table
    virtio_disk_init(); // emulated hard disk
    userinit();      // first user process
    __sync_synchronize();
    started = 1;
  } else {
    while(started == 0)
      ;
    __sync_synchronize();
    printf("hart %d starting\n", cpuid());
    kvminithart();    // turn on paging
    trapinithart();   // install kernel trap vector
    plicinithart();   // ask PLIC for device interrupts
  }

  scheduler();        
}

经以上分析后可知，在Chcore内核代码的start.S中设置CPU Core 启动顺序是因为BSS 和 时钟，调度器，锁的初始化。然后我们看Xv6 中的main.c 中的代码正好包含时钟，调度器，锁的初始化工作（Xv6 并没有与清理BSS相关的代码，故不考虑），故Xv6代码会在这里设置CPU Core 启动顺序 即通过 cpuid() == 0 与 while(started == 0)两个控制语句使得只有0号CPU Core 可以执行相关初始化并在初始化结束之后将started设置为1来让其他CPU Core并行开始初始化。而之前的entry.S 以及 init.c 中的代码是可以让CPU Core并行���行的，故没必要在之前设置CPU Core 启动顺序。

Part 1.3：一个假设

按照Xv6的思路我们可以改写Chcore 代码：我们不必要在start.s 设置CPU Core 启动顺序，CPU Core可以并行进行切换异常级别，建立stack ，跳转到init.c 。init.c 中可以并行的代码依然放在init.c ,不能并行的放在main.c 中，然后main.c 采用Xv6 写法。反之我们可以改写Xv6。

以下是相关伪代码：

start.S:
BEGIN_FUNC(_start)

 /* Turn to el1 from other exception levels. */
 bl  arm64_elX_to_el1

 /* Prepare stack pointer and jump to C. */
 adr  x0, boot_cpu_stack
 add  x0, x0, #INIT_STACK_SIZE
 mov  sp, x0

 b  init_c

 /* Should never be here */
 b .
END_FUNC(_start)

init.c:

void init_c(void)
{
 //maybe some other initalize work
 early_uart_init();
 uart_send_string("boot: init_c\r\n");

 uart_send_string("[BOOT] Jump to kernel main\r\n");
 start_kernel(secondary_boot_flag);//jump to main

 /* Never reach here */
}

main.c:

volatile static int started = 0;

// start() jumps here in supervisor mode on all CPUs.
void
main()
{
  if(cpuid() == 0){
   clear_bss();
  init_kernel_pt();
  el1_mmu_activate();
  //other work is not listed here 
    started = 1;
  } else {
    while(started == 0)
      ;
   init_kernel_pt();
  el1_mmu_activate();
   //other work is not listed here 
  
  }

需注意上述这是设计的想法，具体还与架构等底层有关，故上述想法可能错误。只是希望读者可以从上述讲解中体会到操作系统设计的相通点并提出自己的思考。相关架构知识放在文章末尾。

Part 2 内核代码在被加载到内存之前到那些事

Part 2.1：BIOS之前的故事

由于Chcore文档并未过多讲述执行内核代码之前的事，我们将基于Linux讲述执行内核代码之前的工作，以下描述主要讲述大体流程，细节并未十分完善。

需要注意的一点是，内核代码很重要，但它并不是一开始就执行的，因为有一些非常基本的初始化工作要做，这主要与硬件有关。在Linux中，我们按下按钮，主板会从电池获取信号，然后启动CPU，CPU 则复位寄存器的所有数据，并设置每个寄存器的预定值，并且在 CPU 寄存器中定义了如下预定义数据：

IP          0xfff0
CS selector 0xf000
CS base     0xffff0000

而且CS base + IP = 0xfffffff0 ， 这个地方是 复位向量(Reset vector) 。 这是CPU在重置后期望执行的第一条指令的内存地址。它包含一个 jump 指令，这个指令通常指向BIOS入口点。

注：CPU将在实模式下执行，此模式下MMU并未启用，寻址方式为：PhysicalAddress = Segment * 16 + Offset 。

Part 2.2：BIOS的故事

然后CPU会跳转到 BIOS 的入口，BIOS 开始工作（初始化和检查硬件和寻找可引导设备）（BIOS 会检查配置并尝试根据设备在配置中的顺序找到设备中的引导扇区（通常是该设备的第一个扇区），而引导扇区始终包含主引导记录（MBR），MBR 通常有 446 个字节用于存储引导代码，64 个字节用于存储分区表，最后两个字节用于检查该设备是否为可引导设备），并且我们必须注意到，只要我们开始执行引导代码，BIOS 就已经将系统的控制权移交给引导代码了。

注：关于MBR的一些细节

如果我们只考虑下面三者的相对顺序同时忽视其他可能的细节，通常disk分区大致如下：

• 扇区 0：存放 MBR（主引导记录） 或 UEFI 引导程序。
• 扇区 1 到 N：存放 核心映像，也就是操作系统的引导程序或内核映像。这个区域通常存储引导所需的文件，它在启动时会被加载到内存的高地址。
• 扇区 N+1：开始存放 第一个可用分区，这个分区用于存储操作系统的文件系统，如 Windows 的 NTFS 或 Linux 的 EXT4 等。

文章末尾将补充关于核心映像加载到内存的高地址的由来。

Part 2.3：引导代码

在现实世界中，要启动 Linux 系统，有多种引导程序可以选择。比如 GRUB 2 和 syslinux。Linux内核通过 Boot protocol 来定义应该如何实现引导程序。在这里我们只介绍 GRUB 2。现在我们已经选择一个可引导设备并将控制权移到引导扇区中的引导代码（通常称为 Boot.img），这个引导代码只做了一些非常基本的初始化工作，然后跳转到 GRUB 2 的核心映像并执行代码（将内核代码和文件系统驱动程序放入内存然后初始化控制台等），执行完代码后会调用 grub_menu_execute_entry 函数列出可用的系统供选择，当选择一个系统时，grub_menu_execute_entry 会调用 boot 命令来引导所选系统即将所选系统的内核代码加载到内存中，在内核被引导入内存后，内存使用情况将入下表所示：

所以当 bootloader 完成任务，将执行权移交给 kernel，kernel 的代码从以下地址开始执行：

0x1000 + X + sizeof(KernelBootSector) + 1
个人以为应该是 X + sizeof(KernelBootSector) + 1 因为 X 已经是一个具体的物理地址了，不是一个偏移

上面的公式中， X 是 kernel bootsector 被引导入内存的位置。在我的机器上， X 的值是 0x10000，到这里，引导程序完成它的使命，并将控制权移交给了 Linux kernel。

文章末尾补充内容

Part 3 :页表配置代码

Part 3.1:XV6 页表配置代码

// Make a direct-map page table for the kernel.
pagetable_t
kvmmake(void)
{
  pagetable_t kpgtbl;

  kpgtbl = (pagetable_t) kalloc();
  memset(kpgtbl, 0, PGSIZE);

  // uart registers
  kvmmap(kpgtbl, UART0, UART0, PGSIZE, PTE_R | PTE_W);

  // virtio mmio disk interface
  kvmmap(kpgtbl, VIRTIO0, VIRTIO0, PGSIZE, PTE_R | PTE_W);

  // PLIC
  kvmmap(kpgtbl, PLIC, PLIC, 0x4000000, PTE_R | PTE_W);

  // map kernel text executable and read-only.
  kvmmap(kpgtbl, KERNBASE, KERNBASE, (uint64)etext-KERNBASE, PTE_R | PTE_X);

  // map kernel data and the physical RAM we'll make use of.
  kvmmap(kpgtbl, (uint64)etext, (uint64)etext, PHYSTOP-(uint64)etext, PTE_R | PTE_W);

  // map the trampoline for trap entry/exit to
  // the highest virtual address in the kernel.
  kvmmap(kpgtbl, TRAMPOLINE, (uint64)trampoline, PGSIZE, PTE_R | PTE_X);

  // allocate and map a kernel stack for each process.
  proc_mapstacks(kpgtbl);
  
  return kpgtbl;
}

// Initialize the one kernel_pagetable
void
kvminit(void)
{
  kernel_pagetable = kvmmake();
}

// add a mapping to the kernel page table.
// only used when booting.
// does not flush TLB or enable paging.
void
kvmmap(pagetable_t kpgtbl, uint64 va, uint64 pa, uint64 sz, int perm)
{
  if(mappages(kpgtbl, va, sz, pa, perm) != 0)
    panic("kvmmap");
}

Part 3.2:Chcore 页表配置代码

这部分内容可以参考源码解析部分的文章

Part 4:架构补充知识

Part 4.1:细粒度的汇编控制与编译器的自动优化

• ARM架构的汇编：ARM汇编指令在某些情况下比x86更加细粒度，特别是在多核并发编程中，对于缓存一致性和内存屏障的控制。ARM架构可能需要开发者在汇编层面显式地插入内存屏障指令，以确保不同线程之间的操作顺序（例如dmb、dsb等）。而在x86架构上，由于它的强一致性（即大多数情况下，内存操作的顺序已经得到硬件的保证），开发者通常无需关心指令的顺序，编译器和处理器会自动处理。
• 编译器支持：为了应对这些低级别的内存操作，编译器往往提供一些内置函数（如__sync_synchronize()）来强制执行内存屏障操作，确保在多线程环境下不同线程之间的可见性和顺序性。在ARM平台上，编译器需要支持这些内置的同步原语，或者开发者需要手动插入相应的内存屏障指令。

Part 4.2: 内存模型：强一致性 vs. 弱一致性

• x86的强一致性：x86架构（尤其是较新版本）通常采用强一致性的内存模型，也就是说，指令的执行顺序对于程序员来说是更直观的，硬件会确保内存操作的顺序与程序代码的顺序尽量一致。在这种架构下，许多并发相关的问题（例如数据竞争）能够通过简单的同步原语或内存屏障得到有效解决。
• ARM的弱一致性：与x86不同，ARM架构通常采用弱一致性模型，这意味着在没有显式同步指令的情况下，**处理器的内存访问可能会乱序执行，这对于多核处理器尤其重要。**在ARM上，如果你不显式地插入内存屏障，可能会遇到数据的"可见性"问题。例如，某些写操作可能不会立即对其他核心可见，从而导致程序出现潜在的并发错误。因此，ARM汇编通常需要开发者更加关注如何通过内存屏障指令来保证不同线程之间的操作顺序。

Part 4.3: __sync_synchronize()与兼容性

• __sync_synchronize()是一个编译器内置的内存屏障函数，主要用来确保在它之前的所有操作在它之后的操作之前完成。它可以帮助开发者避免一些由于内存重排引起的问题。在x86架构上，这个函数通常会被翻译成适当的内存屏障指令（如mfence或sfence）。然而，ARM架构可能会有不同的实现方式，依赖于不同的编译器（如GCC或Clang）以及ARM的具体实现（例如v7、v8或更高版本）来选择合适的指令（例如dmb、dsb）。
• 如果编译器没有自动插入正确的同步原语，开发者可能需要手动插入ARM汇编指令来保证多线程同步。这就涉及到开发者对平台底层细节的了解，特别是在不同架构上实现内存屏障的细节。

Part 5:核心映像加载到内存的高地址的由来

Part 5.1:内核映像加载位置的历史变化

• 早期的内核加载位置： 在早期的 Linux 系统中，内核映像通常被加载到 低地址，大约在 1MB 左右的地方。这是因为当时的硬件架构（比如 x86）内存较小，CPU 的物理地址空间和虚���地址空间通常都相对较小，且操作系统通常从较低的内存地址开始加载。内核从低内存加载的方式也较为简单，因为这时候没有复杂的内存管理机制。
• 现代 Linux 内核加载位置： 随着硬件技术的发展，尤其是 64 位系统的普及和内存容量的增大，现代的 Linux 系统通常将内核加载到 高地址。这种做法使得内核能够充分利用现代处理器的 虚拟内存机制，同时也能避免与用户空间的内存发生冲突。具体的高地址位置通常是由硬件架构、内核配置以及引导加载程序来决定。

Part 5.2: 内核加载位置的当前做法

在 现代 64 位 Linux 系统 中，内核映像通常被加载到一个 高位地址，例如：

• 在 x86_64 架构上，内核通常被加载到 0x1000000（16MB） 或更高的位置。这个位置是在内存的 高端，远离用户空间和其他内核空间，避免了地址冲突，并允许操作系统更灵活地管理内存。
• 在 ARM64 或其他架构上，内核的加载位置也类似，通常会在系统启动时由引导程序（如 U-Boot）和系统固件（如 UEFI）决定，并根据内存大小和硬件要求来分配。

Part 5.3:为什么从低地址到高地址变化？

• 支持更大的内存空间：现代的计算机通常具有大量的 RAM，使用高位地址加载内核可以让内核直接与硬件提供的高地址空间对接，避免内核与低位内存（如用户空间和系统堆栈等）发生冲突。
• 虚拟内存支持：现代系统的虚拟内存支持允许内核在虚拟地址空间中管理和映射更大的内存区域。高位地址加载使得内核可以在虚拟地址中灵活地划分内存，并减少碎片化问题。
• 更高效的内存管理：将内核映像加载到高位地址有助于现代内存管理技术（如 PAE、x86_64、NUMA 等）能够更好地工作，尤其是在需要管理大内存和多核处理器的环境下。
• 避免地址冲突：将内核映像加载到高位地址可以防止与用户空间的内存区域发生冲突。特别是对于需要动态分配内存的内核，这种方法有助于减少发生冲突的风险。

Part 5.4: Linux 内核加载位置的可配置性

虽然现代 Linux 系统的内核通常会被加载到高位地址，但这并不是固定不变的，也不是硬件强制的。实际上，Linux 内核的加载位置是可以通过引导程序来配置的。例如：

• 引导加载程序（如 GRUB） 会提供一个位置，用于将内核映像加载到内存中。这个位置可以根据需要进行配置，��别是在某些嵌入式系统中，可能会有特殊的要求。
• 内核配置：Linux 内核的配置中可以指定内核映像的加载地址。这通常是通过内核的启动选项或者配置文件来决定的。
• 物理和虚拟内存管理：内核的加载地址与物理和虚拟内存的管理密切相关，可能会根据硬件架构、内存管理策略等不同而有所不同。

Part 5.5: Linux 文档中的内核加载地址

根据 Linux 文档 和内核源代码（如 Documentation/x86/boot.rst 和 arch/arm/boot/dts 中的文档），现代系统中内核加载的地址是有标准的。例如，Linux 在启动时会读取引导加载程序指定的地址，并且根据系统的配置，使用一个默认的加载地址。

在 x86_64 架构中，常见的加载地址是 0x1000000（16MB），而对于 ARM64 系统，内核加载的地址可能是 0x40008000（64MB）。但这也取决于引导加载程序和系统配置，具体情况可以通过内核的启动配置和引导程序的选项进行调整。

Part 6:自己动手

源码解析

这部分内容是对内存管理部分的chcore源代码的详细解析，包括物理内存管理与虚拟内存管理两个部分。

Buddy System 伙伴系统

• 回顾：为什么需要伙伴系统
  • 外部碎片与内部碎片
  • 伙伴系统的设计理念
• Chcore伙伴系统的设计
  • 核心数据结构
    • page
    • phys_mem_pool
  • 核心函数接口
• Chcore源码对伙伴系统的具体实现
  • init_buddy
  • get_buddy_chunk
  • buddy_get_pages
  • buddy_free_pages
  • spilt_chunk
  • merge_chunk

SLab分配器

• 回顾：SLab分配器的设计理念
  • 基本结构
  • SLab的内部组织
• Chcore中SLab分配器的设计
  • 核心数据结构
    • slab_pointer
    • slab_header
    • slab_slot_list
  • 核心函数接口
• Chcore源码对SLab功能的具体实现
  • init_slab
  • alloc_in_slab
  • free_in_slab

Kmalloc & Kfree

• kmalloc
• kfree

Buddy System 伙伴系统

Buddy System，即伙伴系统，被广泛应用于分配连续的物理内存页。本节内容将：

• 回顾伙伴系统的基础知识与设计理念
• 分析Chcore源码对伙伴系统的代码实现与架构
• 解析Chcore源码对伙伴系统操作相关函数的具体实现

为什么需要伙伴系统

面对进程多种多样的内存分配请求，自然需要一个精良的分配器设计来承担这样宏伟的责任。许多分配器无不在内存碎片（无法被利用的内存）的困扰下捉襟见肘，而伙伴系统则在一定程度上解决了普通简易分配器会带来的内存碎片问题，尤其是在分配连续内存的情况下。

外部碎片与内部碎片

• 外部碎片：单个空闲内存部分小于分配请求的内存大小
• 内部碎片：分配内存大于实际内存导致的内存碎片

Buddy System将通过合并与级联的设计来避免这些困扰

伙伴系统的设计理念

伙伴系统设计理念即基于伙伴块进行分裂与合并，主要可概括为以下几点：

• 物理内存划为块为单位分配内存，每个块由连续物理页组成，大小为2^n个物理页（便于分裂与合并）
• 大块可根据分配需求分裂为小块，两个相同的小块可合并为大块，大块分裂出的两个小块即称作伙伴
• 分配时根据需求选择块，若这样的空闲块不存在，则找大块分裂；释放内存时查看其伙伴，若伙伴也空闲则直接合并

如下图所示，相同颜色的块即表示伙伴块

由此一来，基于Buddy System的分配模式便可确保每时每刻的空闲块都是最大的，这样可以避免外部碎片；同时基于分配请求来寻找空闲块分配的操作又尽可能减小了内部碎片的大小。尽量避免了较大内存碎片的产生

Chcore伙伴系统的设计

核心数据结构

核心数据结构，即 page 和 phys_mem_pool ，如下所示为源码：

#define N_PHYS_MEM_POOLS 3

/* The following two are defined in mm.c and filled by mmparse.c. */
extern paddr_t physmem_map[N_PHYS_MEM_POOLS][2];
extern int physmem_map_num;

/* All the following symbols are only used locally in the mm module. */

/* `struct page` is the metadata of one physical 4k page. */
struct page {
        /* Free list */
        struct list_head node;
        /* Whether the correspond physical page is free now. */
        int allocated;
        /* The order of the memory chunck that this page belongs to. */
        int order;
        /* Used for ChCore slab allocator. */
        void *slab;
        /* The physical memory pool this page belongs to */
        struct phys_mem_pool *pool;
};

struct free_list {
        struct list_head free_list;
        unsigned long nr_free;
};

/*
 * Supported Order: [0, BUDDY_MAX_ORDER).
 * The max allocated size (continous physical memory size) is
 * 2^(BUDDY_MAX_ORDER - 1) * 4K.
 * Given BUDDY_MAX_ORDER is 14, the max allocated chunk is 32M.
 */
#define BUDDY_PAGE_SIZE     (0x1000)
#define BUDDY_MAX_ORDER     (14)

/* One page size is 4K, so the order is 12. */
#define BUDDY_PAGE_SIZE_ORDER (12)

/* Each physical memory chunk can be represented by one physical memory pool. */
struct phys_mem_pool {
        /*
         * The start virtual address (for used in kernel) of
         * this physical memory pool.
         */
        vaddr_t pool_start_addr;
        unsigned long pool_mem_size;

        /*
         * The start virtual address (for used in kernel) of
         * the metadata area of this pool.
         */
        struct page *page_metadata;

        /* One lock for one pool. */
        struct lock buddy_lock;

        /* The free list of different free-memory-chunk orders. */
        struct free_list free_lists[BUDDY_MAX_ORDER];

        /*
         * This field is only used in ChCore unit test.
         * The number of (4k) physical pages in this physical memory pool.
         */
        unsigned long pool_phys_page_num;
};

/* Disjoint physical memory can be represented by several phys_mem_pools. */
extern struct phys_mem_pool global_mem[N_PHYS_MEM_POOLS];

page

在chcore中，一个 page 结构体即表示一个实际的4KB大小的物理内存页，我们来看它的具体成员组成：

• struct list_head node ：是用于维护空闲链表的节点，当我们需要把这个页移入/移出空闲链表时，就会使用到这个节点
• int allocated ：表示该页是否被分配
• int order ：表示该页所属的块的阶数（即2^n的n）
• struct phys_mem_pool *pool ：表示该页所隶属的内存池

另外还有slab，这个会在下文讲解slab分配器的时候具体解析

phys_mem_pool

chcore里的内存池即表示一整块连续的物理内存，也就是伙伴系统概念中所提到的整个空闲链表背后所属于的大的连续内存块。所以相应的，它就需要维护链表数组以及其所包含的所有页表元数据。我们还是来看看它的具体成员组成：

• vaddr_t pool_start_addr ：内存池表示内存的起始地址
• unsigned long pool_mem_size ：内存池表示的内存大小
• struct page *page_metadata ：一个页表数组，包含了这个内存块里的所有页表
• struct lock buddy_lock ：内存池的锁，用于并行化
• struct free_list free_lists[BUDDY_MAX_ORDER] ：空闲链表数组，这里的order最大为14，故有14个这样的链表，可以依次表示4KB到32MB的内存

核心函数接口

即伙伴系统用于实际操作这些数据结构的函数，这里先大概介绍一下接口，下文再深入研究其实现：

void init_buddy(struct phys_mem_pool *, struct page *start_page,
                vaddr_t start_addr, unsigned long page_num);

static struct page *get_buddy_chunk(struct phys_mem_pool *pool,
                                    struct page *chunk)
                                    
static struct page *split_chunk(struct phys_mem_pool *pool, int order,
                                struct page *chunk)
                                
static struct page *merge_chunk(struct phys_mem_pool *pool, struct page *chunk)

struct page *buddy_get_pages(struct phys_mem_pool *, int order);

void buddy_free_pages(struct phys_mem_pool *, struct page *page);

void *page_to_virt(struct page *page);

struct page *virt_to_page(void* ptr);

unsigned long get_free_mem_size_from_buddy(struct phys_mem_pool *);

unsigned long get_total_mem_size_from_buddy(struct phys_mem_pool *);

从上到下的函数接口依次的功能为：

• init_buddy ：初始化伙伴系统，包括其链表数组，页表元数据数组等
• get_buddy_chunk ：根据指定内存池和内存块（的起始页表项）找到其伙伴块
• split_chunk ：分裂内存块
• merge_chunk ：合并伙伴内存块
• buddy_get_pages ：查询并获取指定内存池和阶数的内存块
• buddy_free_pages ：释放指定内存池的内存块
• page_to_virt ：获取给定内存块（page_metadata）的虚拟地址，这是因为page类的指针指向的是 page_metadata 而非实际地址
• virt_to_page ：根据给定虚拟地址找到相应的内存块（page_metadata），和上面的函数互为逆操作
• get_free_mem_size_from_buddy ：获取给定内存池中当前可用的内存总量
• get_total_mem_size_from_buddy ：获取给定内存池的总大小

Chcore源码对伙伴系统的具体实现

上一部分我们从上层的视角讲解了伙伴系统的原理以及Chcore中伙伴系统的架构，这一部分我们则从下层的视角，来分析上文提到的函数接口以及Buddy System核心功能的具体实现

本节主要着重分析对伙伴系统的初始化以及对伙伴块的操作函数的讲解，而受限于篇幅，辅助函数本处不做解析，感兴趣者可自行阅读

init_buddy

源码

/*
 * The layout of a phys_mem_pool:
 * | page_metadata are (an array of struct page) | alignment pad | usable memory
 * |
 *
 * The usable memory: [pool_start_addr, pool_start_addr + pool_mem_size).
 */
void init_buddy(struct phys_mem_pool *pool, struct page *start_page,
                vaddr_t start_addr, unsigned long page_num)
{
        int order;
        int page_idx;
        struct page *page;

        BUG_ON(lock_init(&pool->buddy_lock) != 0);

        /* Init the physical memory pool. */
        pool->pool_start_addr = start_addr;
        pool->page_metadata = start_page;
        pool->pool_mem_size = page_num * BUDDY_PAGE_SIZE;
        /* This field is for unit test only. */
        pool->pool_phys_page_num = page_num;

        /* Init the free lists */
        for (order = 0; order < BUDDY_MAX_ORDER; ++order) {
                pool->free_lists[order].nr_free = 0;
                init_list_head(&(pool->free_lists[order].free_list));
        }

        /* Clear the page_metadata area. */
        memset((char *)start_page, 0, page_num * sizeof(struct page));

        /* Init the page_metadata area. */
        for (page_idx = 0; page_idx < page_num; ++page_idx) {
                page = start_page + page_idx;
                page->allocated = 1;
                page->order = 0;
                page->pool = pool;
        }

        /* Put each physical memory page into the free lists. */
        for (page_idx = 0; page_idx < page_num; ++page_idx) {
                page = start_page + page_idx;
                buddy_free_pages(pool, page);
        }
}

解析

这个函数主要负责初始化我们的伙伴系统，它将接受的参数用于初始化一个特定的内存池，并为之设置相应页表数组和空闲链表数组等。你可能会好奇，这些参数本身又是怎么来的？这便涉及到对整个物理内存系统的初始化，可以移步 mm.c 文件的 mm_init 函数及相关辅助函数作进一步的学习

根据抽象屏障原则，我们这里只需要关心它是如何初始化一个内存池即可

我们根据注释分析得到实际上的内存池内存布局：

内存池的布局：
+--------------------------------------------------------------------
|     页面元数据区域        |    对齐填充     |      实际可用内存区域      |
| (struct page 数组)      |    (未使用)     |    (用于分配的物理内存)    |
+------------------------+-------------------------------------------

源码的工作可以分成三个阶段：

• 初始化物理内存池：根据传入的参数设置物理内存池的相应数据成员，这里的 BUDDY_PAGE_SIZE 是0x1000，也即4KB
• 初始化空闲链表：用一个for循环将每个阶的空闲链表均初始化，这里首先将每个链表的空闲数设为0，同时用初始化函数 init_list_head 将这个链表节点的首尾都连到自己身上
• 初始化页表元数据：先用 memset 将这块内存全部清零；再用for循环溜一遍，利用指针运算初始化每个页表相应数据；最后再依次free每个物理页表，这里自然会涉及到后面的merge操作，并最终得到一个全部空闲的内存池

可以看见，chcore中实际的设计和书上提到的基本一致，不过书上的介绍做了一定的简化

get_buddy_chunk

找呀找呀找朋友，找到一个伙伴块

源码

static struct page *get_buddy_chunk(struct phys_mem_pool *pool,
                                    struct page *chunk)
{
        vaddr_t chunk_addr;
        vaddr_t buddy_chunk_addr;
        int order;

        /* Get the address of the chunk. */
        chunk_addr = (vaddr_t)page_to_virt(chunk);
        order = chunk->order;
        /*
         * Calculate the address of the buddy chunk according to the address
         * relationship between buddies.
         */
        buddy_chunk_addr = chunk_addr
                           ^ (1UL << (order + BUDDY_PAGE_SIZE_ORDER));

        /* Check whether the buddy_chunk_addr belongs to pool. */
        if ((buddy_chunk_addr < pool->pool_start_addr)
            || ((buddy_chunk_addr + (1 << order) * BUDDY_PAGE_SIZE)
                > (pool->pool_start_addr + pool->pool_mem_size))) {
                return NULL;
        }

        return virt_to_page((void *)buddy_chunk_addr);
}

解析

由伙伴块的定义可知，互为伙伴的两个块，它们的内存地址仅有一位不同，且该位由order决定

于是这块代码的核心便在于如何由位运算得到伙伴块的地址，首先，我们有：

块A的伙伴是块B = 块A的地址 ^ size
块B的伙伴是块A = 块B的地址 ^ size

于是我们可以由order和BUDDY_PAGE_SIZE_ORDER（这里是12，因为一个页的大小是4KB）得到size的大小：

(1UL << (order + BUDDY_PAGE_SIZE_ORDER))

再做一个异或，就得到了相应的伙伴块地址。接下来的事情，就交给辅助函数！

buddy_get_pages

现在让我们看看一次完整的向伙伴系统申请内存的流程是怎样的！

源码

struct page *buddy_get_pages(struct phys_mem_pool *pool, int order)
{
        int cur_order;
        struct list_head *free_list;
        struct page *page = NULL;

        if (unlikely(order >= BUDDY_MAX_ORDER)) {
                kwarn("ChCore does not support allocating such too large "
                      "contious physical memory\n");
                return NULL;
        }

        lock(&pool->buddy_lock);

        /* Search a chunk (with just enough size) in the free lists. */
        for (cur_order = order; cur_order < BUDDY_MAX_ORDER; ++cur_order) {
                free_list = &(pool->free_lists[cur_order].free_list);
                if (!list_empty(free_list)) {
                        /* Get a free memory chunck from the free list */
                        page = list_entry(free_list->next, struct page, node);
                        list_del(&page->node);
                        pool->free_lists[cur_order].nr_free -= 1;
                        page->allocated = 1;
                        break;
                }
        }

        if (unlikely(page == NULL)) {
                kdebug("[OOM] No enough memory in memory pool %p\n", pool);
                goto out;
        }

        /*
         * Split the chunk found and return the start part of the chunck
         * which can meet the required size.
         */
        page = split_chunk(pool, order, page);

out:
        unlock(&pool->buddy_lock);
        return page;
}

解析

纵览代码，我们可以绘制该函数执行的流程图：

重点可以看看伙伴系统是如何查找满足要求的空闲块的：

        /* Search a chunk (with just enough size) in the free lists. */
        for (cur_order = order; cur_order < BUDDY_MAX_ORDER; ++cur_order) {
                free_list = &(pool->free_lists[cur_order].free_list);
                if (!list_empty(free_list)) {
                        /* Get a free memory chunck from the free list */
                        page = list_entry(free_list->next, struct page, node);
                        list_del(&page->node);
                        pool->free_lists[cur_order].nr_free -= 1;
                        page->allocated = 1;
                        break;
                }
        }

从查询要求提供的order开始，一级一级向上查找，如果没有则向上加一级，如果有则操作链表，取出这块空闲块，并同时设置空闲链表的相应参数，退出循环

一个可能的例子如下：

假设要申请 order=2 (16KB) 的内存：

1. 先查找 order=2 的空闲链表
2. 如果没有，查找 order=3 的空闲链表
3. 如果没有，继续查找更大的空闲链表
4. 直到找到可用的内存块或达到最大阶数

至于裂开的操作，我们马上就会讲到

buddy_free_pages

和get操作类似，我们现在来看看free操作是如何进行的

源码

void buddy_free_pages(struct phys_mem_pool *pool, struct page *page)
{
        int order;
        struct list_head *free_list;

        lock(&pool->buddy_lock);

        BUG_ON(page->allocated == 0);
        /* Mark the chunk @page as free. */
        page->allocated = 0;
        /* Merge the freed chunk. */
        page = merge_chunk(pool, page);

        /* Put the merged chunk into the its corresponding free list. */
        order = page->order;
        free_list = &(pool->free_lists[order].free_list);
        list_add(&page->node, free_list);
        pool->free_lists[order].nr_free += 1;

        unlock(&pool->buddy_lock);
}

解析

get还需要查询是否有空闲块，而free则简单多了——直接设置参数后merge即可！最后不要使用链表操作将这个块放进内存池的空闲链表里

同样的，加锁和去锁在这里也少不了，它们是并发安全性的保证

下面我们就讲解裂开和合并的具体实现，也是伙伴系统最关键的地方

spilt_chunk

源码

static struct page *split_chunk(struct phys_mem_pool *pool, int order,
                                struct page *chunk)
{
        struct page *buddy_chunk;
        struct list_head *free_list;

        /*
         * If the @chunk's order equals to the required order,
         * return this chunk.
         */
        if (chunk->order == order)
                return chunk;

        /*
         * If the current order is larger than the required order,
         * split the memory chunck into two halves.
         */
        chunk->order -= 1;

        buddy_chunk = get_buddy_chunk(pool, chunk);
        /* The buddy_chunk must exist since we are spliting a large chunk. */
        if (buddy_chunk == NULL) {
                BUG("buddy_chunk must exist");
                return NULL;
        }

        /* Set the metadata of the remaining buddy_chunk. */
        buddy_chunk->order = chunk->order;
        buddy_chunk->allocated = 0;

        /* Put the remaining buddy_chunk into its correspondint free list. */
        free_list = &(pool->free_lists[buddy_chunk->order].free_list);
        list_add(&buddy_chunk->node, free_list);
        pool->free_lists[buddy_chunk->order].nr_free += 1;

        /* Continue to split current chunk (@chunk). */
        return split_chunk(pool, order, chunk);
}

解析

注意该函数接受的参数： order 指的是最后要得到的内存块的order，这一点也可以在上面申请内存的函数中对该函数的调用发现

函数整体上采用尾递归的设计，每次执行时先判断边界条件，随后再进行具体的单次分裂的操作

下面是对于其逻辑的具体分析：

以将16KB分裂为4KB为例，我们可以用一个示意图来描述这个过程。此处粉色块表示被加入空闲链表的伙伴块，白色块表示继续递归分裂的块，直到拿到我们想要的块

最后我们再来看合并块的实现

merge_chunk

源码

/* The most recursion level of merge_chunk is decided by the macro of
 * BUDDY_MAX_ORDER. */
static struct page *merge_chunk(struct phys_mem_pool *pool, struct page *chunk)
{
        struct page *buddy_chunk;

        /* The @chunk has already been the largest one. */
        if (chunk->order == (BUDDY_MAX_ORDER - 1)) {
                return chunk;
        }

        /* Locate the buddy_chunk of @chunk. */
        buddy_chunk = get_buddy_chunk(pool, chunk);

        /* If the buddy_chunk does not exist, no further merge is required. */
        if (buddy_chunk == NULL)
                return chunk;

        /* The buddy_chunk is not free, no further merge is required. */
        if (buddy_chunk->allocated == 1)
                return chunk;

        /* The buddy_chunk is not free as a whole, no further merge is required.
         */
        if (buddy_chunk->order != chunk->order)
                return chunk;

        /* Remove the buddy_chunk from its current free list. */
        list_del(&(buddy_chunk->node));
        pool->free_lists[buddy_chunk->order].nr_free -= 1;

        /* Merge the two buddies and get a larger chunk @chunk (order+1). */
        buddy_chunk->order += 1;
        chunk->order += 1;
        if (chunk > buddy_chunk)
                chunk = buddy_chunk;

        /* Keeping merging. */
        return merge_chunk(pool, chunk);
}

解析

有了对分裂块过程的了解，那么合并块理解起来就更简单了：同样是基于尾递归的实现，每次执行时先判断当前块是否已经达到最大的阶数or它的伙伴已经不在了，然后再执行相应操作，最后递归处理

我们以一张示例图结束伙伴块之间的羁绊

注意这里判断伙伴块阶数相同的操作，实际上是看伙伴块是否依然作为一个整体空闲着存在，而不是已经裂开了

同样以4KB——16KB为例，介绍一次典型的合并过程

这样便完成了对merge操作的实现的介绍与解析

SLab分配器

Buddy System负责分配连续的物理内存页，但是如果系统遇到了小内存分配的需求，比如仅仅数十个字节的结构体等，这时候若继续使用伙伴系统，由于其最少只能分配4KB的内存，便会造成严重的内部碎片问题。而SLab分配器（SLub）便是专用于小内存分配的，它和Buddy System一起构成了Chcore的物理内存管理系统

本节内容承接上文，为大家介绍Chcore中SLab分配器的设计与具体实现，主要还是包括三个部分：

• 回顾SLab分配器的基础知识与设计理念
• 分析Chcore源码对SLab的代码实现与架构
• 解析Chcore源码对SLab操作相关函数的具体实现

SLab分配器的设计理念

SLab专用于小内存的分配。和伙伴系统不同，SLab本身不涉及对内存块的合并与分裂，而是通过一个个不同的SLab池，来分配不同固定大小的内存块，并且在SLab池内部使用链表结构串起一个个SLab，SLab内部又使用空闲链表的结构，便可以对所有的空闲内存块进行管理和分配

基本结构

• SLab是一个内存分配器，主要用于分配小块内存（32字节到2048字节之间）
• 整个系统维护了多个不同大小的 slab_pool ，每个池对应特定大小的内存块
• 内存大小按2的幂次方划分：32, 64, 128, 256, 512, 1024, 2048字节（从2^5到2^11）

SLab的内部组织

每个 slab_pool 由多个slab组成，每个slab又具有以下特点：

• 固定大小为128KB（SIZE_OF_ONE_SLAB）
• 包含一个 slab_header（位于slab开始处）
• 剩余空间被划分为大小相等的对象槽（slots）
• 使用空闲链表（free_list）管理未分配的对象槽
• 每个 slab_pool 有current和partial指针，分别指向当前slab以及总的slab链表组

SLab的工作流程

• 当请求分配内存时，SLAB分配器会首先从部分使用Slab链表中查找是否有可用的对象
• 如果没有，它会从空闲Slab链表中取出一个slot，并将其移动到部分使用Slab链表
• 如果空闲链表也为空（即partial为空），则会从内存中（即伙伴系统）分配一个新的slab，然后进行上一步操作
• 当释放内存块时，如果一个slab中的所有slots都被释放，则该slab会被移动到空闲Slab链表

有如下示意图以供参考

这里的对象即为内存块，在Chcore实现中用slot表示，下面会提到。实际的SLab分配器的设计可能用到full_slab链表也可能不会，具体根据其实现确定

查看本机Slab示例：

sudo cat /proc/slabinfo

kmalloc-4k           569    584   4096    8    8 : tunables    0    0    0 : slabdata     73     73      0
kmalloc-2k           752    752   2048   16    8 : tunables    0    0    0 : slabdata     47     47      0
kmalloc-1k           704    704   1024   32    8 : tunables    0    0    0 : slabdata     22     22      0
kmalloc-512         2112   2112    512   32    4 : tunables    0    0    0 : slabdata     66     66      0
kmalloc-256          768    768    256   32    2 : tunables    0    0    0 : slabdata     24     24      0
kmalloc-192         1050   1050    192   42    2 : tunables    0    0    0 : slabdata     25     25      0
kmalloc-128         1376   1376    128   32    1 : tunables    0    0    0 : slabdata     43     43      0
kmalloc-96          1134   1134     96   42    1 : tunables    0    0    0 : slabdata     27     27      0
kmalloc-64          3072   3072     64   64    1 : tunables    0    0    0 : slabdata     48     48      0
kmalloc-32          3072   3072     32  128    1 : tunables    0    0    0 : slabdata     24     24      0
kmalloc-16          6144   6144     16  256    1 : tunables    0    0    0 : slabdata     24     24      0
kmalloc-8          12288  12288      8  512    1 : tunables    0    0    0 : slabdata     24     24      0

Chcore中SLab分配器的设计

同伙伴系统一样，这部分主要介绍Chcore中SLab分配器实现的核心数据结构和函数接口

核心数据结构

先上代码，看看有哪些数据结构

/*
 * order range: [SLAB_MIN_ORDER, SLAB_MAX_ORDER]
 * ChCore prepares the slab for each order in the range.
 */
#define SLAB_MIN_ORDER (5)
#define SLAB_MAX_ORDER (11)

/* The size of one slab is 128K. */
#define SIZE_OF_ONE_SLAB (128*1024)

/* slab_header resides in the beginning of each slab (i.e., occupies the first slot). */
struct slab_header {
        /* The list of free slots, which can be converted to struct slab_slot_list. */
        void *free_list_head;
        /* Partial slab list. */
        struct list_head node;

        int order;
        unsigned short total_free_cnt; /* MAX: 65536 */
        unsigned short current_free_cnt;
};

/* Each free slot in one slab is regarded as slab_slot_list. */
struct slab_slot_list {
        void *next_free;
};

struct slab_pointer {
        struct slab_header *current_slab;
        struct list_head partial_slab_list;
};

/* slab_pool is also static. We do not add the static modifier due to unit test.
 */
struct slab_pointer slab_pool[SLAB_MAX_ORDER + 1];
static struct lock slabs_locks[SLAB_MAX_ORDER + 1];

Chcore中的SLab分配器设定大体服从书上的安排，以内存池为单元，先看宏定义：

• SLAB_MIN_ORDER & SLAB_MIN_ORDER ：表示SLab分配器可以操作的内存块大小，从2^5到2^11字节
• SIZE_OF_ONE_SLAB ：表示每个slab的大小，在Chcore中是128KB

接下来我们再分析其核心数据结构的实现：

slab_pointer

即Chcore中表示slab池的数据结构，这个也可以在下面对 slab_pool 的定义中看见。其数据成员即我们之前介绍的current和partial指针，在这里以 slab_header 和 list_head 的形式出现

slab_header

是Chcore中代表一个个具体的slab的对象，其成员包含：

• void *free_list_head ：内部空闲slot的链表
• struct list_head node ：partial中表示自身的节点

如何由节点反过来得到其处于的slab？

在chcore之中采用的是内存对齐+元数据的方式，具体而言，元数据为：

• 在每一个slab块的开头，维护一个其中内存槽slot的free list head
• 在每一个内存槽slot之中，存一个next_free的指针
• slab由buddy sys分配，保证slab header地址按 page 对齐

这样，当我想要free addr时, 可以找到对应的page, 进而找到slab header, 进而得到free_list，最后在free_list之中插入这个slot, 然后由这个slab的空闲slot个数判断是否是 full → partial, partial→free, 从而进行插入partial list或者把slab空间归还给buddy sys的操作

• int order ：该slab的阶数
• total_free_cnt & current_free_cnt ：总的空闲块数 & 当前空闲块数

最后是slot自身

slab_slot_list

仅包含一个 void *next_free 指针，它们串起来得到每个slab内部的空闲块链表

核心函数接口

Chcore的SLab分配器的实现包含了较多的辅助函数，这里只介绍重要的几个接口：

void init_slab(void);
void *alloc_in_slab(unsigned long, size_t *);
void free_in_slab(void *addr);

从上到下函数接口的功能依次为：

• init_slab ：初始化SLab分配器
• alloc_in_slab ：在slab中申请分配内存
• free_in_slab ：释放相应的内存

Chcore源码对SLab功能的具体实现

同伙伴系统一样，这部分解析Chcore源码对SLab功能函数的具体实现，主要内容即为上面部分提到的三个函数，其中又会涉及到其他辅助函数，根据重要程度串起来讲解

init_slab

源码

void init_slab(void)
{
        int order;

        /* slab obj size: 32, 64, 128, 256, 512, 1024, 2048 */
        for (order = SLAB_MIN_ORDER; order <= SLAB_MAX_ORDER; order++) {
                lock_init(&slabs_locks[order]);
                slab_pool[order].current_slab = NULL;
                init_list_head(&(slab_pool[order].partial_slab_list));
        }
        kdebug("mm: finish initing slab allocators\n");
}

解析

初始化函数和伙伴系统比起来简单了许多，直接用一个for循环去过一遍所有slab池即可：

• 初始化 32~ 2048 字节为slot的各个slab, 每一个slab为 SIZE_OF_ONE_SLAB=128K 大小
• 初始化对应的锁
• 对全局变量的slab array的 current_slab partial_slab_list 初始化

alloc_in_slab

源码

void *alloc_in_slab(unsigned long size, size_t *real_size)
{
        int order;

        BUG_ON(size > order_to_size(SLAB_MAX_ORDER));

        order = (int)size_to_order(size);
        if (order < SLAB_MIN_ORDER)
                order = SLAB_MIN_ORDER;

#if ENABLE_MEMORY_USAGE_COLLECTING == ON
        if (real_size)
                *real_size = 1 << order;
#endif

        return alloc_in_slab_impl(order);
}

static void *alloc_in_slab_impl(int order)
{
        struct slab_header *current_slab;
        struct slab_slot_list *free_list;
        void *next_slot;

        lock(&slabs_locks[order]);

        current_slab = slab_pool[order].current_slab;
        /* When serving the first allocation request. */
        if (unlikely(current_slab == NULL)) {
                current_slab = init_slab_cache(order, SIZE_OF_ONE_SLAB);
                if (current_slab == NULL) {
                        unlock(&slabs_locks[order]);
                        return NULL;
                }
                slab_pool[order].current_slab = current_slab;
        }

        free_list = (struct slab_slot_list *)current_slab->free_list_head;
        BUG_ON(free_list == NULL);

        next_slot = free_list->next_free;
        current_slab->free_list_head = next_slot;

        current_slab->current_free_cnt -= 1;
        /* When current_slab is full, choose a new slab as the current one. */
        if (unlikely(current_slab->current_free_cnt == 0))
                choose_new_current_slab(&slab_pool[order], order);

        unlock(&slabs_locks[order]);

        return (void *)free_list;
}

static void choose_new_current_slab(struct slab_pointer *pool, int order)
{
        struct list_head *list;

        list = &(pool->partial_slab_list);
        if (list_empty(list)) {
                pool->current_slab = NULL;
        } else {
                struct slab_header *slab;

                slab = (struct slab_header *)list_entry(
                        list->next, struct slab_header, node);
                pool->current_slab = slab;
                list_del(list->next);
        }
}

解析

注意到源码将参数检查和核心实现分为了两部分，其中核心实现单独用了一个辅助函数，对外的接口则为 alloc_in_slab 本身

二者视作一起看，其核心逻辑如下：

• 参数检查，确保order符合范围，太大则报错，太小则向上补到最小值
• 加锁，确保并发安全性
• 若current为空，则为首次分配，需要先init一下（注意这里是直接使用的内部接口，保持了外界的无感知，也简化了这里的代码逻辑）
• 随后直接从current的slab的空闲链表中取出一块slot作为返回值，同时处理相应字段，如空闲块数量减一，修改list_head等
• 若当前slab已满，则换新的slab，通过 choose_new_current_slab 进行操作，方式依然是通过定义好的list操作宏直接操作相应的链表
• 解锁，完成分配

逻辑图可以作如下参考，便于理解阅读：

free_in_slab

最后是free的操作，为slab拼上最后一块拼图

源码

void free_in_slab(void *addr)
{
        struct page *page;
        struct slab_header *slab;
        struct slab_slot_list *slot;
        int order;

        slot = (struct slab_slot_list *)addr;
        page = virt_to_page(addr);
        if (!page) {
                kdebug("invalid page in %s", __func__);
                return;
        }

        slab = page->slab;
        order = slab->order;
        lock(&slabs_locks[order]);

        try_insert_full_slab_to_partial(slab);

#if ENABLE_DETECTING_DOUBLE_FREE_IN_SLAB == ON
        /*
         * SLAB double free detection: check whether the slot to free is
         * already in the free list.
         */
        if (check_slot_is_free(slab, slot) == 1) {
                kinfo("SLAB: double free detected. Address is %p\n",
                      (unsigned long)slot);
                BUG_ON(1);
        }
#endif

        slot->next_free = slab->free_list_head;
        slab->free_list_head = slot;
        slab->current_free_cnt += 1;

        try_return_slab_to_buddy(slab, order);

        unlock(&slabs_locks[order]);
}

解析

整体上还是走的“获取信息——转到相应object——根据情况分类讨论作对应操作”

梳理一下 free_in_slab 的实现逻辑：

• 处理参数，通过地址转换拿到slot、page、slab等对象
• 上锁
• 检查现在的slab是否是full的，如果是，那么在free前还得把它放回partial
• 进行free操作，即把链表头插回来、设置slab空闲链表、以及空闲数加一
• 检查现在的slab是否是空的，如果是，那么物归原主——还给buddy大人
• 解锁，完成free全部操作

至此，SLab分配器源码解析结束

Kmalloc与Kfree

有了Buddy System和SLab分配器，我们便能够去做真正的分配内存与释放内存的操作了——也即malloc和free。本部分源码解析即讲解Chcore的内核中kmalloc/kfree，这里的k表示kernel，即专用于内核空间分配/释放的函数

直接上源码！

源码

kmalloc

void *kmalloc(unsigned long size)
{
        size_t real_size;
        void *ret;
        ret = _kmalloc(size, true, &real_size);
        return ret;
}

/* Currently, BUG_ON no available memory. */
void *_kmalloc(size_t size, bool is_record, size_t *real_size)
{
        void *addr;
        int order;

        if (unlikely(size == 0))
                return ZERO_SIZE_PTR;

        if (size <= SLAB_MAX_SIZE) {
                addr = alloc_in_slab(size, real_size);
#if ENABLE_MEMORY_USAGE_COLLECTING == ON
                if(is_record && collecting_switch) {
                        record_mem_usage(*real_size, addr);
  }
#endif
        } else {
                if (size <= BUDDY_PAGE_SIZE)
                        order = 0;
                else
                        order = size_to_page_order(size);
                addr = get_pages(order);
        }

        return addr;
}

kfree

void kfree(void *ptr)
{
        _kfree(ptr, true);
}

void _kfree(void *ptr, bool is_revoke_record)
{
        struct page *page;

        if (unlikely(ptr == ZERO_SIZE_PTR))
                return;

        page = virt_to_page(ptr);
#if ENABLE_MEMORY_USAGE_COLLECTING == ON
        if (collecting_switch && is_revoke_record) {
                revoke_mem_usage(ptr);
 }
#endif
        if (page && page->slab)
                free_in_slab(ptr);
        else if (page && page->pool)
                buddy_free_pages(page->pool, page);
        else
                kwarn("unexpected state in %s\n", __func__);
}

解析

有了之前Buddy System和SLab提供的接口，实现这两个函数便简单多了，参数检查过后，直接用一个分支结构即可解决

kmalloc

• 参数检查
• 看需要分配的size大小，若小于 SLAB_MAX_SIZE 则使用SLab分配器的接口分配内存
• 若大于，则使用伙伴系统的接口分配内存（包装在 get_pages 函数里的，这里没有列出）
• 返回分配得到的地址指针

kfree

• 参数检查
• 根据地址拿到它所属的page
• 看page的属性，如果它有slab，则说明是slab里的page，交由slab接口处理
• 如果它有pool，则说明是伙伴系统的page，交由伙伴系统接口处理

总结

至此，物理内存管理部分的源码解析已经全部结束，希望能对你的学习有所裨益！

目录

• 页表管理
  • 核心数据结构
  • 函数功能实现
    • 接口定义
    • 源码解析
• 缺页管理
  • ARM异常机制
    • 异常类型
    • 处理逻辑
  • 缺页异常源码解析
  • VMR & PMO