09 - C Standard Library and Implementation

09 - C 标准库和实现

其实目前已经学习了许多系统调用...这节课介绍 C lib...or libc

操作系统为我们提供了对象和操作它们的 API：

我们学习了

进程管理的 fork, execve, exit, waitpid；
内存管理的 mmap；文件 (对象) 管理的 open, read, write, dup, close, pipe, ……大家观察到这些

API 的设计有一个有趣的原则：

“非必要不实现” (“机制与策略分离”、“最小完备性原则”)
但凡应用程序能自己搞定的功能，操作系统就不需要提供——在一定程度上，这样的设计能防止 “包揽一切” 导致代码膨胀，甚至在长期演化的过程中成为历史的包袱。
"在底层提供尽可能少的机制", 但少不意味着不出错...
所以 syscall() 其实算作最底层的, 内容也比较少, 而主要的常用的功能由编程语言自己实现...

本讲内容：在操作系统 API 之上，为了服务应用程序，毋庸置疑需要有一套 “好用” 的库函数。虽然 libc 在今天的确谈不上 “好用”，但成就了 C 语言今天 “高级的汇编语言” 的可移植地位，以 ISO 标准的形式支撑了操作系统生态上的万千应用。

1. libc 简介

void _start() {
    __asm__("mov $60, %eax\n"  // syscall: exit
            "xor %edi, %edi\n" // status: 0
            "syscall");
}

1.1. 从"最小"的 C 程序出发

可以构建整个应用世界

C 语言机制
- 指针\数组\结构体\函数...
syscall
- fork execve mmap open...

1.2. 系统调用是地基 C 语言是框架

C 语言: 世界上"最通用"的高级语言

C 是一种"高级汇编语言"
- 可以把 C 代码原样变成汇编语言
- C++则更好用但更难移植
- 其他的功能实现, 如果不重视底层大可以使用 Python or JavaScript
系统调用的一层"浅封装"

小到任何一个平台到大的机器, 基本都有一个 C 的编译器

因为有 C 所以可以在任何硬件移植

Prompt: 为什么称 C 语言是高级的汇编语言？

C语言被称为“高级的汇编语言”，主要因其兼具高级语言的抽象能力和接近硬件的底层控制特性：

硬件级操作 C语言支持指针、直接内存访问和位操作，能精准控制硬件资源（如寄存器、内存地址），这与汇编语言相似。
高效性 C代码经编译后生成的机器指令效率接近汇编，且可通过内联汇编进一步优化关键代码，适合系统级开发。
结构化抽象 相比汇编的指令式编程，C语言提供函数、循环、条件分支等结构化语法，显著提升了代码可读性和可维护性。
跨平台与可移植 C语言通过编译器实现硬件适配，避免了汇编语言对特定架构的强依赖，同时保留了对底层细节的控制权。

这一设计使C语言成为操作系统、嵌入式系统等对性能和底层控制要求较高场景的理想选择。

C23: 演进没有完全停止

constexpr int n = 5 + 4;  // ???
typeof(n) arr[n];  // ???

[[maybe_unused]] auto* ptr = foo();  // ???
ptr = nullptr;  // ???

constexpr 是 C++11 引入的关键字，用于声明常量表达式
typeof 是一个 GNU C 扩展，用于获取变量的类型
[[maybe_unused]] 是 C++17 引入的属性，用于标记变量或函数可能未被使用
nullptr 是 C++11 引入的关键字，用于表示空指针

1.3. 如果没有库函数, 寸步难行

就算有系统调用, 也没法编程?

道理上可行, 工程上不行

int read(int fd, void *buf, size_t count);
int write(int fd, const void *buf, size_t count);

int main() {
    int a = ???; // 读入 a
    int b = ???; // 读入 b
    int sum = a + b;
    // 输出 sum ???
}

libc 绝大部分都可以用底层代码, 汇编实现

1.4. The C Standord Library

语言机制运行库

大部分可以用 C 语言本身实现
少部分需要"底层支持"

库也被标准化

ISO IEC 标准的一部分
POSIX C Library 的子集
- 稳定, 可靠 - 不用担心升级版本会破坏实现
- 极佳的移植性: 包括你自己的操作系统!

唯一不用担心 - 编译器有问题 - 的语言

1.5. 学习 libc 最好的方法: 自己写一个 libc

今天我们有 AI 老师...可以让老师来帮忙逃课...

修了好多 bug

Inline assembly 忘记 %%
_start 的 rsp 已经被改过了
mmap 的参数顺序错了
munmap 忘记处理头上的 8 字节 size
- 也只是让 test.c 能正常运行了
- 不知道还有没有更多的问题

代码：谨慎使用 AIGC

Also you can learn by Open Source libc - minilibc

root@LAPTOP-GT06V0GS:/mnt/d/CSLab/osCourse/lec9/minilibc# ./test/test
String copied: Hello from mini libc!
Length of string: 21
Number of arguments: 1
Command line arguments:
  argv[0]: ./test/test
Allocated memory: Memory allocation works!
This is printed using puts()
root@LAPTOP-GT06V0GS:/mnt/d/CSLab/osCourse/lec9/minilibc# echo $?
42

2. 基础编程机制的抽象

2.1. 计算的封装

学习已有的 libc 实现

调试 glibc？

不，你不想
glibc 的代码有非常沉重的历史包袱
- 以及非常多的优化——都是对 “理解原理” 的阻碍
- 新手阅读体验极差

基本原则：总有办法的

让 AI Copilot 帮你解释代码 (这个可以有)
是否有比 glibc 更适合学习的 libc 实现？
- (我的知识储备跟不上 AI，更跟不上有 RAG 的 AI)
- 幸好我还做了正确的选择：musl

2.2. Con'd

下载源码不难，难的是怎么 “使用” 下载的 libc

我们知道可以使用 gcc 和 ld
但到底应该用什么编译选项？

如何使用我自己的 clang、musl 替代 glibc 编译程序？

当然，我们还是选择自己编译
- 比较重要的选项
- - -O1: 减少优化级别，便于查看状态
  - -g3: 增加调试信息
- 使用 musl-gcc 静态编译
试一试：从第一条指令开始调试一个 C 程序

看起来讲的很轻松, 实际上一个 CS System 是复杂的

2.3. 基础数据的体系结构无关抽象

Freestanding 环境下也可以使用的定义

stddef.h - size_t
- 还有一个有趣的 “offsetof” (Demo; 遍历手册的乐趣)
stdint.h - int32_t, uint64_t
stdbool.h - bool, true, false
float.h
limits.h
stdarg.h
inttypes.h
- 打印 intptr_t 变量 printf 的格式字符串是什么？

2.4. 字符串和数组

string.h: 字符串/数组操作

memcpy, memmove, strcpy, ...

stdlib.h: 常用功能

rand, abort, atexit, system, atoi, ...
看起来就不像是人用的

2.5. more

在 AI 的指导下阅读手册

更多的 stdlib.h 中的例子
- atoi, atol, atoll, strtoull, ...
- rand (注意线程安全), ...
math.h
- FP8: E4M3/E5M2; Quantization
- 一个原本就深奥的课题；AI 时代变得更复杂困难
setjmp.h
- 这个好玩！要用状态机去理解
实现库函数 = C 语言课程习题

2.6. AI

“Attention is all you need.”

你需要给他 “关键词” (prompt engineering)
推理模型降低了对 “关键词” 的依赖
- 但 “神来之笔” 的关键词仍然能起决定性的作用

3. 系统调用与环境的抽象

3.1. 输入输出

Standard I/O: stdio.h

FILE * 背后其实是一个文件描述符
我们可以用 gdb 查看具体的 FILE *
- 例如 stdout
封装了文件描述符上的系统调用 (fseek, fgetpos, ftell, feof, ...)

The printf() family

这些代码理应没有 “code clones”

3.2. popen 和 pclose

我们在游戏修改器中使用了它

一个设计有历史包袱和缺陷的 API
- Since a pipe is by definition unidirectional, the type argument may specify only reading or writing, not both; the resulting stream is correspondingly read-only or write-only.

为什么我们要用现代编程语言？

let checksum = {
  Exec::shell("find . -type f")
    | Exec::cmd("sort") | Exec::cmd("sha1sum")
}.capture()?.stdout_str();  // ()? returns "std::nullopt"

3.3. err, error, perror

所有 API 都可能失败

$ gcc nonexist.c
gcc: error: nonexist.c: No such file or directory

反复出现的 “No such file or directory”

这不是巧合！
- 我们也可以 “山寨” 出同样的效果
Quiz: errno 是进程共享还是线程独享？
- 线程有一些我们 “看不到” 的开销：ucontext, errno, ...

3.4. environ(7)

这个绝对不是操作系统写的

libc 没有任何神秘的地方...也不用知道这么多内容...

int main(argc, char *argv[], char *envp[]);

envp: execve() 传递给进程的 “环境”

全局变量 environ 是谁赋值的？
- 是时候请出我们的老朋友 watch point 了
- 没有对他进行赋值
RTFM: System V ABI
- p33
- Figure 3.9 Initial Process Stack
- - 操作系统有一个 “初始状态”
  - libc 调用 main 前还会继续初始化这个 “初始状态”

4. 动态内存管理

4.1. malloc() 和 free()

I call it my billion-dollar mistake. It was the invention of the null reference in 1965. (Tony Hoare)

发明了空指针...这其实是一个 billion-dollar mistake

我们总是假设输入是正确的...
总是假设指针不是空的...

编程语言抽象不足

malloc/free 也有类似的问题
- Use after free
- Double free
- Memory leak
“最小完备性原则” 和 “机制策略分离” 的反面教材
- “每一个 malloc 在任何可能路径上都必有一次配对的 free，且之后不再使用”
- 在复杂系统里太难保证了

使用的系统调用：mmap (历史：sbrk)

大段内存，要多少有多少
- 用 MAP_ANONYMOUS 申请
- 超过物理内存上限都行 (Demo)

root@LAPTOP-GT06V0GS:/mnt/d/CSLab/osCourse/lec9/mmap# make
gcc -Wall -g alloc.c -o alloc
root@LAPTOP-GT06V0GS:/mnt/d/CSLab/osCourse/lec9/mmap# ./alloc
mmap: 7f7cf861d000
Read get: 2
Read get: 0
Read get: 3

延迟分配（Lazy Allocation）
1. Linux 的 mmap 实现了延迟分配（也称为懒惰分配）。这意味着在 mmap 调用返回时，实际的物理内存可能还没有被分配。
2. 只有在首次访问这些内存时（触发缺页异常），操作系统才会分配实际的物理内存。
匿名映射（Anonymous Mapping）
1. MAP_ANONYMOUS 标志表示分配的内存不与任何文件关联，而是匿名的。
2. 这种映射通常用于分配临时内存。
私有映射（Private Mapping）
1. MAP_PRIVATE标志表示映射是私有的，对映射的修改不会影响其他进程。

root@LAPTOP-GT06V0GS:/mnt/d/CSLab/osCourse/lec9/mmap# strace ./alloc

# 程序启动 第一个 system call
execve("./alloc", ["./alloc"], 0x7ffc7013c5b0 /* 36 vars */) = 0

# 内存分配 - 堆
brk(NULL)                               = 0x557eed6fb000

# 匿名内存映射
mmap(NULL, 8192, PROT_READ|PROT_WRITE, MAP_PRIVATE|MAP_ANONYMOUS, -1, 0) = 0x7f1aecd5a000

# 加载动态连接器和库
access("/etc/ld.so.preload", R_OK)      = -1 ENOENT (No such file or directory)
openat(AT_FDCWD, "/etc/ld.so.cache", O_RDONLY|O_CLOEXEC) = 3
fstat(3, {st_mode=S_IFREG|0644, st_size=82479, ...}) = 0
mmap(NULL, 82479, PROT_READ, MAP_PRIVATE, 3, 0) = 0x7f1aecd45000
close(3)                                = 0
openat(AT_FDCWD, "/lib/x86_64-linux-gnu/libc.so.6", O_RDONLY|O_CLOEXEC) = 3

# 加载 libc 库
read(3, "\177ELF\2\1\1\3\0\0\0\0\0\0\0\0\3\0>\0\1\0\0\0\220\243\2\0\0\0\0\0"..., 832) = 832
pread64(3, "\6\0\0\0\4\0\0\0@\0\0\0\0\0\0\0@\0\0\0\0\0\0\0@\0\0\0\0\0\0\0"..., 784, 64) = 784
fstat(3, {st_mode=S_IFREG|0755, st_size=2125328, ...}) = 0
pread64(3, "\6\0\0\0\4\0\0\0@\0\0\0\0\0\0\0@\0\0\0\0\0\0\0@\0\0\0\0\0\0\0"..., 784, 64) = 784
mmap(NULL, 2170256, PROT_READ, MAP_PRIVATE|MAP_DENYWRITE, 3, 0) = 0x7f1aecb33000
mmap(0x7f1aecb5b000, 1605632, PROT_READ|PROT_EXEC, MAP_PRIVATE|MAP_FIXED|MAP_DENYWRITE, 3, 0x28000) = 0x7f1aecb5b000
mmap(0x7f1aecce3000, 323584, PROT_READ, MAP_PRIVATE|MAP_FIXED|MAP_DENYWRITE, 3, 0x1b0000) = 0x7f1aecce3000
mmap(0x7f1aecd32000, 24576, PROT_READ|PROT_WRITE, MAP_PRIVATE|MAP_FIXED|MAP_DENYWRITE, 3, 0x1fe000) = 0x7f1aecd32000
mmap(0x7f1aecd38000, 52624, PROT_READ|PROT_WRITE, MAP_PRIVATE|MAP_FIXED|MAP_ANONYMOUS, -1, 0) = 0x7f1aecd38000
close(3)                                = 0

# 其他初始化
mmap(NULL, 12288, PROT_READ|PROT_WRITE, MAP_PRIVATE|MAP_ANONYMOUS, -1, 0) = 0x7f1aecb30000
arch_prctl(ARCH_SET_FS, 0x7f1aecb30740) = 0
set_tid_address(0x7f1aecb30a10)         = 3595
set_robust_list(0x7f1aecb30a20, 24)     = 0
rseq(0x7f1aecb31060, 0x20, 0, 0x53053053) = 0
mprotect(0x7f1aecd32000, 16384, PROT_READ) = 0
mprotect(0x557edf558000, 4096, PROT_READ) = 0
mprotect(0x7f1aecd92000, 8192, PROT_READ) = 0
prlimit64(0, RLIMIT_STACK, NULL, {rlim_cur=8192*1024, rlim_max=RLIM64_INFINITY}) = 0
munmap(0x7f1aecd45000, 82479)           = 0

# 程序逻辑 分配 8 GiB 匿名内存
mmap(NULL, 8589934592, PROT_READ|PROT_WRITE, MAP_PRIVATE|MAP_ANONYMOUS, -1, 0) = 0x7f18ecb30000

# 文件描述符操作
fstat(1, {st_mode=S_IFCHR|0600, st_rdev=makedev(0x88, 0), ...}) = 0

# 随机数生成
getrandom("\xab\x4b\x81\xcd\x9f\xfe\x97\xb6", 8, GRND_NONBLOCK) = 8

# 堆扩展
brk(NULL)                               = 0x557eed6fb000
brk(0x557eed71c000)                     = 0x557eed71c000

# 写入内存
write(1, "mmap: 7f18ecb30000\n", 19mmap: 7f18ecb30000
)    = 19
write(1, "Read get: 2\n", 12Read get: 2
)           = 12
write(1, "Read get: 0\n", 12Read get: 0
)           = 12
write(1, "Read get: 3\n", 12Read get: 3
)           = 12

# 程序退出 退出整个进程组
exit_group(0)                           = ?
+++ exited with 0 +++

反而，操作系统不支持分配一小段内存

这是应用程序自己的事
- 应用程序可以每次向操作系统 “多要一点” 内存
- 自己在内存上实现一个数据结构

4.2. 实现 malloc()

使用的系统调用：mmap (历史：sbrk)

大段内存，要多少有多少
- 用 MAP_ANONYMOUS 申请
- 超过物理内存上限都行 (Demo)

反而，操作系统不支持分配一小段内存

这是应用程序自己的事
- 应用程序可以每次向操作系统 “多要一点” 内存
- 自己在内存上实现一个数据结构
malloc 的每一个内存只能有一个所有者?

4.3. 对现实的恐怖一无所知...

早在 1995 年：这才叫 research

Understanding real program behavior still remains the most important first step in formulating a theory of memory management. Without doing that, we cannot hope to develop the science of memory management; we can only fumble around doing ad hoc engineering, in the too-often-used pejorative sense of the word. At this point, the needs of good science and of good engineering in this area are the same—a deeper qualitative understanding. We must try to discern what is relevant and characterize it; this is necessary before formal techniques can be applied usefully.

停止无意义的 “科研实践”，去做真正有价值的事情

4.4. 实现高效的 malloc()/free()

Premature optimization is the root of all evil.

——D. E. Knuth

重要的事情说三遍：

脱离 workload 做优化就是耍流氓
- 在开始考虑性能之前，理解你需要考虑什么样的性能

然后，去哪里找 workload?

当然是 paper 了 (顺便白得一个方案)
- Mimalloc: free list sharding in action (APLAS'19)
- 卷到今天大家做的事情也没变：看 workload 调性能

4.5. 理论 v.s. 实践

在实际系统中，我们通常不考虑 adversarial worst case

现实中的应用是 “正常” 的，不是 “恶意” 的
- 但这给了很多 Denial of Service 的机会：Cross container attack

malloc() 的观察

大对象分配后应，读写数量应当远大于它的大小
- 否则就是 performance bug
- 申请 16MB 内存，扫了一遍就释放了
- - 这不是 bug，难道还是 feature 吗？
推论：越小的对象创建/分配越频繁

4.6. malloc() 的观察

考虑具体的功能

我们需要管理的对象

小对象：字符串、临时对象等；生存周期可长可短
中对象：容器、复杂的对象；更长的生存周期
大对象：巨大的容器、分配器；很长的生存周期

结论

我们几乎只要管好小对象就好了 (当然，仅针对 oslabs)
- 在 Lab 里至少是如此的
由于所有分配都会在所有处理器上发生
- 小对象分配/回收的 scalability 是主要瓶颈
- 使用链表/区间树 (first fit) 可不是个好想法

4.7. malloc, Fast and Slow

人类也是这样的系统

Thinking, Fast and Slow by Daniel Kahneman

设置两套系统

Fast path (System I) ← AI 已经开始超越 System I 人类
- 性能极好、覆盖大部分情况
- 但有小概率会失败 (fall back to slow path)
Slow path (System II) ← 人类也已经失守了
- 不在乎那么快
- 但把困难的事情做好
计算机系统里有很多这样的例子 (比如 cache)

4.8. 人类的智慧: 空间换整洁

分配: Segregated List (Slab)

每个 slab 里的每个对象都一样大
- 每个线程拥有每个对象大小的 slab
- fast path → 立即在线程本地分配完成
- slow path → mmap()

Previous08 - Terminal and UNIX Shell Next10 - Executable files

Last updated 2 months ago