本文最后更新于：2 年前

如何在系统调用之上构建程序能够普遍受惠的标准库？

熟悉又陌生的 libc

为什么需要 libc?

“裸奔” 编程：能用 (而且绝对够用)，但不好用。很多功能是重复的！！！

long syscall(int num, ...) {
  va_list ap;
  va_start(ap, num);
  register long a0 asm ("rax") = num;
  register long a1 asm ("rdi") = va_arg(ap, long);
  register long a2 asm ("rsi") = va_arg(ap, long);
  register long a3 asm ("rdx") = va_arg(ap, long);
  register long a4 asm ("r10") = va_arg(ap, long);
  va_end(ap);
  asm volatile("syscall"
    : "+r"(a0) : "r"(a1), "r"(a2), "r"(a3), "r"(a4)
    : "memory", "rcx", "r8", "r9", "r11");
  return a0;
}

任何程序都用得上的定义

例如，不同机器下的(long类型)很多类型，实现的底层是不一样的，例如大小。就可能导致可移植性造成一些问题。。。

即便是没有任何的代码，也可以给我们提供一些必要的支持，比如说整数大小，之类的。很多库能帮助我们解决一部分这样的问题。

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

stddef.h - size_t
stdint.h - int32_t, uint64_t
stdbool.h - bool, true, false
float.h
limits.h
stdarg.h
- syscall 就用到了 (但 syscall0, syscall1, … 更高效)
inttypes.h
- 回答了你多年来的疑问！
- 在你读过了小白阶段以后，就真的是 friendly manual 了

解决了Portable问题，考虑到了，虽然看起来很shit……

然后，系统调用也要用得方便！

系统调用是操作系统 “紧凑” 的最小接口。并不是所有系统调用都像 fork 一样可以直接使用。

低情商 API：

extern char **environ;
char *argv[] = { "echo", "hello", "world", NULL, };
// 这里会失败，因为execve要求的第一个参数，必须是一个合法的路径！！！！不合法就不行！！！
// 本质上我们想让操作系统做的是：“找到path里面的echo”，并且执行，我们还要自己找路径？？？不存在的！！！
if (execve(argv[0], argv, environ) < 0) {
  perror("exec");
}

高情商 API：

// 这个就会帮助我们自动去路径里面找到echo命令，然后执行echo hello world
// 包括下面的system()，就更加高级昂！！！
execlp("echo", "echo", "hello", "world", NULL);
system("echo hello world");

Libc: low level -> high level，把底层不好用的API，做成我们更好用的封装，低情商 -> 高情商。

封装 (1): 纯粹的计算

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

简单，不简单

void *memset(void *s, int c, size_t n) {
  for (size_t i = 0; i < n; i++) {
    ((char *)s)[i] = c;
  }
  return s;
}

让我们看看 clang 把它编译成了什么……

以及，线程安全性？memset-race.c
标准库只对 “标准库内部数据” 的线程安全性负责
- 例子：printf 的 buffer

#include "thread.h"

char buf[1 << 30];

void foo(int id) {
  memset(buf, '0' + id, sizeof(buf) - 1);
}

int main() {
  for (int i = 0; i < 4; i++)
    create(foo);
  join();
  puts(buf);
}

排序和查找

低情商 (低配置) API

void qsort(void *base, size_t nmemb, size_t size,
           int (*compar)(const void *, const void *));

void *bsearch(const void *key, const void *base,
              size_t nmemb, size_t size,
              int (*compar)(const void *, const void *));

高情商 API

1 2	`sort(xs.begin(), xs.end(), [] (auto& a, auto& b) {...}); xs.sort(lambda key=...)`

封装 (2): 文件描述符

stdio.h: 你熟悉的味道

访问操作系统对象最主要的就是访问文件描述符，文件描述符就是一个打开了的文件。Linux上，一切都是文件。原则上，文件描述符可以访问任何对象！！！

FILE * 背后其实是一个文件描述符

我们可以用 gdb 查看具体的FILE *(例如 stdout)
- 可以 “窥探” 到 glibc 的一些内部实现
- 可以加载 glibc 的 debug symbols
  - 在这门课上不推荐：你调试起来会很浪费时间
封装了文件描述符上的系统调用 (fseek, fgetpos, ftell, feof, …)

vprintf 系列

使用了 stdarg.h 的参数列表

1 2	`int vfprintf(FILE stream, const char format, va_list ap); int vasprintf(char *ret, const char format, va_list ap);`

popen 和 pclose

我们在 dosbox-hack.c 中使用了它

一个设计有缺陷的 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.

高情商 API (现代编程语言)

subprocess.check_output(['cat'],
  input=b'Hello World', stderr=subprocess.STDOUT)
let dir_checksum = {
  Exec::shell("find . -type f")
    | Exec::cmd("sort") | Exec::cmd("sha1sum")
}.capture()?.stdout_str();

封装 (3): 更多的进程/操作系统功能

err, error, perror

所有 API 都可能失败

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

这个 “No such file or directory” 似乎见得有点多？

上面这些函数，表现出来的行为都是一致的，背后是不是有什么东西在支撑这个呢？非常能够猜到，这个报错or提示，应该来自同一个库 or 包来实现。

cat nonexist.c, wc nonexist.c 都是同样的 error message
这不是巧合！
- 我们也可以 “山寨” 出同样的效果
- warn(“%s”, fname); (观察 strace)
  - err 可以额外退出程序

strace看看底层更加有意思，甚至打印的都是分开的，有点组件的感觉。（其实底层call的是同一个library）-> 已经被广泛接受啦！！！

errno 是进程共享还是线程独享？
- 这下知道协程的轻量了吧

environ (7)

我们也可以实现自己的 env.c

alex ~ $ man environ -> 可以看看这个手册昂

#include <stdio.h>

int main() {
  extern char **environ;
  for (char **env = environ; *env; env++) {
    printf("%s\n", *env);
  }
}

问题来了：environ 是谁赋值的？
- 这个函数又是在哪里定义的？

怎么去查，用gdb来debug一下，看看！！！

gcc env.c -g -static && gdb a.out:

哦～在_libc_start_main()中，完成了对于上面这个environ变量的赋值。
动态链接是一样的，是可以看到的昂！！！

_init里，就是在那个ld.so那个loader里面昂！！！

debugger + libc，就可以看到很多执行流程，可以边学习边康康昂！！！
RTFM 后
- 对环境变量的理解又上升了

封装 (4): 地址空间

malloc 和 free & 自定义malloc和free

很重要！！！申请内存！！！

本质上malloc/free就是进行内存的“区间管理”嘛！！

红黑树之类的数据结构会有偏差！！！算法里面强调worst case的best，不符合OS实际应用昂！！！多处理器上，不合理！！！

实现高效的 malloc/free

Premature optimization is the root of all evil.

——D. E. Knuth

重要的事情说三遍：

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

然后，去哪里找 workload? -> 找到业界

当然是paper了 (顺便白得一个方案)
- Mimalloc: free list sharding in action (APLAS’19)

Workload 分析

指导思想：O(n)大小的对象分配后至少有Ω(n) 的读写操作，否则就是 performance bug (不应该分配那么多)。

越小的对象创建/分配越频繁
- 字符串、临时对象等 (几十到几百字节)；生存周期可长可短
较为频繁地分配中等大小的对象
- 较大的数组、复杂的对象；更长的生存周期
低频率的大对象
- 巨大的容器、分配器；很长的生存周期
Chanllenge: 并行、并行、再并行
- 所有分配都会在所有处理器上发生
- 使用链表/区间树 (first fit) 可不是个好想法

Malloc, Fast and Slow

设置两套系统：

fast path
- 性能极好、并行度极高、覆盖大部分情况
- 但有小概率会失败 (fall back to slow path)
slow path
- 不在乎那么快
- 但把困难的事情做好
  - 计算机系统里有很多这样的例子 (比如 cache)

人类也是这样的系统

Daniel Kahneman. Thinking, Fast and Slow. Farrar, Straus and Giroux, 2011.

Malloc: Fast Slow Path 设计

使所有 CPU 都能并行地申请内存

Fast
- 线程都事先瓜分一些 “领地” (thread-local allocation buffer)
- 默认从自己的领地里分配
  - 除了在另一个 CPU 释放，acquire lock 几乎总是成功
Slow
- 如果自己的领地不足，就从全局的池子里借一点

不要在乎一点小的浪费
- 这就是为什么要对齐到 2k 字节

绝大多数fast path，很少的slow path -> 如果slow path还是用链表实现，大锁的contension很小的昂！！！加上可能马上就释放掉了！！！

为每一个分配大小，串成链表！！！（视频一个半小时的位置，这里讲的很好！！！可以去听听！！！）

一个page_size是64KB，内存按需大小分块。比如16B，那么一页，就相当于4096块。32B -> 2048，64B -> 1024。分配的时候，按照大小范围分配，很快！！！

Malloc(28B) -> malloc(32B)，从链表头部取一块儿，就完成了分配，O(1)，很快昂！！！你看，32B总共有2048，分配两千次，才可能触发一次Slow Path，就很酷昂！！！很快！！！！！

注意，每个Page的链表头，也就是slab，需要一把锁。这样从这个页面里面，取出内容进行分配的时候，并发才不会出问题昂。不过这个是每个CPU拥有的内存啦，也快很多昂，不是全局的！！！

小内存：Segregated List

分配: Segregated List (Slab)

每个 slab 里的每个对象都一样大
- 每个线程拥有每个对象大小的 slab
- fast path → 立即在线程本地分配完成
- slow path → pgalloc()
两种实现
- 全局大链表 v.s. List sharding (per-page 小链表)

回收

直接归还到 slab 中
- 注意这可能是另一个线程持有的 slab，需要 per-slab 锁 (小心数据竞争)

大内存：一把大锁保平安

Buddy system (1963)

如果你想分配 1, 2, 3, 4, …, n个连续的页面？
- 例如：64 KB/页面
那就 first fit 或者 best fit 吧……

你只需要一个数据结构解决问题

区间树；线段树……

用链表当然也可以啦，很方便！！！当然啦，线段树也可以，对应的就是buddy system。

现实世界中的 malloc/free

以上就是所有现代 malloc/free 实现的基础

当然，实际情况会复杂一些，性能也是锱铢必较
- glibc: arena → heap → tcache (thread-local)
- tcmalloc: thread-caching malloc, mimalloc
- OpenJDK: ZGC: region based + tlab (thread-local)
  - managed memory 允许 object move，因此复杂得多……

无止境地封装

想知道有没有更多的功能？

RTFM: The GNU C Library, RTFSC: Newlib

都不太长 (glibc 的手册和 newlib 的源码) 也好读
Computer System 系列课程的重要目标：摆正看手册的心态

你会发现很多宝藏

Globbing
Regex
Shell-style word expansion
……

我们还可以……

走出 C 的领域，基于 libc 实现

C++ 编译器
- 继续实现 C++ Standard Library
- 继续实现 OpenJDK (HotSpot)
- 继续实现 V8 (JavaScript)
CPython
Go
- 再之后 Go 就可以自己编译自己了 (Goodbye, C!)

Eventually, (千疮百孔) 的整个计算机世界！

C is not a low-level language (CACM’18)
C isn’t a programming language any more (Gankra’s Blog)

shell + libc，就已经足以构建所有的上层应用啦，这俩本质上都是最底层操作系统层面kernel的API的封装昂！！！

后面就开始介绍kernel内部的实现啦！！！(本质就是一个C程序昂！！！)

总结

无止境地封装

想知道有没有更多的功能？

RTFM: The GNU C Library, RTFSC: Newlib

都不太长 (glibc 的手册和 newlib 的源码) 也好读
Computer System 系列课程的重要目标：摆正看手册的心态

你会发现很多宝藏

Globbing
Regex
Shell-style word expansion
……

References

Vedio link: https://www.bilibili.com/video/BV17F411s7e9/?spm_id_from=333.999.0.0&vd_source=ff957cd8fbaeb55d52afc75fbcc87dfd，还是建议看看，尤其我这种C语言基础不扎实的orz
perror -> print a system error message，可以$ man 3 perror，查看调用。
environ手册。
RTFM: Read The Fucking Manual
debugger + libc，就可以看到很多执行流程，可以边学习边康康昂！！！
脱离 workload 做优化就是耍流氓

南京大学操作系统

#研0自学

NJUOS-14-C标准库的实现

https://alexanderliu-creator.github.io/2022/12/29/njuos-14-c-biao-zhun-ku-de-shi-xian/

作者

Alexander Liu

发布于

2022年12月29日

许可协议

NJUOS-15-Fork的应用上一篇

NJUOS-13-系统调用和Shell 下一篇

NJUOS-14-C标准库的实现

熟悉又陌生的 libc

为什么需要 libc?

任何程序都用得上的定义

然后，系统调用也要用得方便！

封装 (1): 纯粹的计算

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

排序和查找

更多的例子

封装 (2): 文件描述符

stdio.h: 你熟悉的味道

popen 和 pclose

封装 (3): 更多的进程/操作系统功能

err, error, perror

environ (7)

封装 (4): 地址空间

malloc 和 free & 自定义malloc和free

实现高效的 malloc/free

Workload 分析

Malloc, Fast and Slow

Malloc: Fast Slow Path 设计

小内存：Segregated List

大内存：一把大锁保平安

现实世界中的 malloc/free

无止境地封装

想知道有没有更多的功能？

我们还可以……

总结

无止境地封装

想知道有没有更多的功能？

References