奇变偶不变

buddy 分配器是 linux 内核中的经典分配器，学习 linux 内存管理的肯定绕不开它，甚至学习其他 linux 子系统的也会学学它，因为实在是太经典了。作者想从根本理解 buddy 分配器的原理，所以找来了 buddy 分配器最初提出的文章：A fast storage allocator 和 knuth 在The Art of Computer Programming, Fundamental Algorithms, Volume 1. 中深入分析 buddy 分配器一节（2.5 节）阅读，下面内容算是这两处内容的笔记了。

本文是《系统虚拟化：原理与实现》第一章的学习笔记。

因为要用 qemu monitor 的 info tlb 功能，奈何 ubuntu 官方版本太低，不支持，所以只能源码安装了。

设备：树莓派 3b+、sdcard、读卡器、usb 转串口线

基本信息：无显示器、串口连接

本文持续更新

连接 wifi

sudo raspi-config

接着输入 wifi 名字和密码

设备：树莓派 3b+、sdcard、读卡器、usb 转串口线

环境：Ubuntu 20.04.6 LTS

树莓派镜像

我选择最新的 arm64 镜像，可以从 https://downloads.raspberrypi.org/raspios_arm64/images/ 查找下载，写这篇文章时最新的是 https://downloads.raspberrypi.org/raspios_arm64/images/raspios_arm64-2023-05-03/2023-05-03-raspios-bullseye-arm64.img.xz，下载之后得到 2023-05-03-raspios-bullseye-arm64.img.xz 文件：

环境：ubuntu 20.04

准备工作

1
2

$ sudo apt-get install qemu qemu-system-arm gcc-aarch64-linux-gnu gdb-multiarch
$ sudo apt install flex bison libssl-dev

编译内核

下载 Linux 源码：kernel 各版本下载

下载完内核之后，如放在 ~/linux-5.10 目录下：

1
2
3
4

$ cd linux-5.10
$ mkdir out
$ make O=out ARCH=arm64 CROSS_COMPILE=aarch64-linux-gnu- defconfig
$ make O=out ARCH=arm64 CROSS_COMPILE=aarch64-linux-gnu- Image -j8

本文是一个实操笔记，记录本地如何编译一个内核版本并安装到系统中使用。我使用的环境如下：

1
2
3
4
5
6
7
8
9
10
11

$ cat /etc/issue
Ubuntu 20.04.5 LTS

$ cat /proc/cpuinfo | grep name | cut -f2 -d: | uniq -c
      8  Intel(R) Core(TM) i7-6700HQ CPU @ 2.60GHz

$ grep 'processor' /proc/cpuinfo | sort -u | wc -l
8

$ cat /proc/cpuinfo | grep "cpu cores" | uniq
cpu cores	: 4

以上表明我使用的是 Ubuntu 20.04.5，机器是 Intel 4 核 8 线程 CPU，每个频率都是 2.60GHz。我编译的版本是 Linux kernel 主线的版本，相当于从 github 上直接拉下来的代码，我下的代码最新的提交是 c1649ec55708ae42091a2f1bca1ab49ecd722d55。以下方法不保证比较老的内核也可以编译通过。

plist 是内核中一种带优先级的双向链表数据结构，链表中每个元素的优先级按数值大小升序排序。plist 作为 pi-futex 的一部分补丁引入内核，初始提交链接为：https://github.com/torvalds/linux/commit/77ba89c5cf28d5d98a3cae17f67a3e42b102cc25。本文基于 6.2-rc2 版本内核解析 plist 实现，阅读本文需要了解 kernel 中 list 数据结构的实现，因为 plist 是基于 list 实现的。