Felix021

想了十天十夜不知道写些什么，那就写写面试题吧。

1

在面试应聘者的时候，我常常会问：

在 Linux 下，如何删除一个目录下的所有 log 文件？

不知道是不是我人畜无害的围笑给了应聘者我很好应付的错觉 



以至于应聘者全都回答：`rm *.log`

追问：该目录下可能有很多子目录，如何把子目录里的 log 文件也删掉呢？

接着 上一篇-内存暴涨坑 再挖个坟，讲讲去年踩的另一个坑。 

---

前方低能

那是去年7月的一天，被透过落地玻璃的宇宙中心五道口的夕阳照着的正在工位搬砖的我，突然听到一阵骚乱，转头一看，收到夺命连环call的D同学反馈，流量严重异常。

点开报警群，一串异常赫然在目： 

之前从网上找的一段代码，按行读取文件:



看起来没问题，用起来也没问题，直到踩了个坑：针对某个特定的文件，读取到某一行以后就不再继续了。

既然总能复现，那就好解决，我的一个常用方法是：制造一个总能复现的case，并不断缩小case的规模。

例如这个case，把那一行单独拿出来，通过二分找到出问题的位置。

原以为是该行有特殊字符导致触发了什么奇怪的逻辑，但经过不断尝试，发现临界点是该行长度 = 65536 的时候，正好会触发错误。

这么整的数字（2^16, 64KB）必然是代码里的特殊逻辑了，翻了一下 bufio 的源码，果然有一个



搜索这个常量在代码里的引用：


在 for 循环后加上一句：


实锤：



那怎么解决呢？

MaxScanTokenSize 上面的注释是这么写的：



于是最终版的解决方案是这样：



真是丑陋的api啊。

系列更新：
* [译] Ｃ程序员该知道的内存知识 (1)
* [译] Ｃ程序员该知道的内存知识 (2)
* [译] Ｃ程序员该知道的内存知识 (3)

这是本系列的第4篇，也是最后一篇，含泪填完这个坑不容易，感谢阅读~

这个系列太干了，阅读量一篇比一篇少，但我仍然认为这个系列非常有价值，在翻译的过程中我也借机进行系统性的梳理、并学习了很多新知识，收获满满。希望你也能有收获（但肯定没我多）。

那，开始吧。 

---

# 理解内存消耗

工具箱：
* vmtouch [2] - portable virtual memory toucher

（译注：vmtouch这个工具用来诊断和控制系统对文件系统的缓存，例如查看某个文件被缓存了多少页，清空某个文件的缓存页，或将某个文件的页面锁定在内存中；基于这些功能可以实现很多有意思的应用；详情参考该工具的文档。） 

然而共享内存的概念导致传统方案 —— 测量对内存的占用 —— 变得无效了，因为没有一个公正的方法可以测量你进程的独占空间。这会引起困惑甚至恐惧，可能是两方面的：



页面有两种状态：清洁(clean)页和脏(dirty)页。区别是，脏页在被回收之前需要被写回到持久存储中（译注：写回文件实际存放的地方）。MADV_FREE 这个建议通过将脏标志位清零这种方式来实现更轻量的内存释放，而不是修改整个页表项（译注：page table entry，常缩写为PTE，记录页面的物理页号及若干标志位，如能否读写、是否脏页、是否在内存中等）。此外，每一页都可能是私有的或共享的，这正是导致困惑的源头。

前面引用的两个都是（部分）真实的，取决于视角。在系统缓冲区的页面需要计入进程的内存消耗里吗？如果进程修改了缓冲区里那些映射文件的那些页面呢？在这混乱中可以整出点有用的东西么？ 

假设有一个进程，索伦之眼（the_eye）会写入对 魔都（mordor） 的共享映射（译注：指环王的梗）。写入共享内存不计入 RSS（resident set size，常驻内存集）的，对吧？



（译注：$$ 是 bash 变量，保存了在执行当前script的shell的PID；这里应该是用来指代the_eye的PID）

呃，让我们回到小黑板。 

## PSS（Proportional Set Size） 

PSS（译注：Proportional 意思是 “比例的”） 计入了私有映射，以及按比例计入共享映射。这是我们能得到的最合理的内存计算方式了。关于“比例”，是指将共享内存除以共享它的进程数量。举个例子，有个应用需要读写某个共享内存映射：



（译注：cat /proc/$PID/maps 是从内核中读取进程的所有内存映射）

这是个被简化并截断了的映射，第一列是地址范围，第二列是权限信息，其中 r 表示可读， w 表示可写，x 表示可执行 —— 这都是老知识点了 —— 然后 s 表示共享，p 表示私有。然后是映射文件的偏移量，设备号（OS分配的），inode号（文件系统上的），以及最后是文件的路径名。具体参见这个文档[3]（译注：kernel.org 对 /proc 文件系统的说明文档），超级详细。 

我得承认我删掉了一些输出中一些不太有意思的信息。如果你对被私有映射的库感兴趣的话可以读一下 FAQ-为什么“strict overcommit”是个蠢主意[4]（译注：根据这个FAQ，strict overcommit应该是指允许overcommmit、但要为申请的每一个虚拟页分配一个真实页，不管是用物理页还是swap，确实听起来很蠢……）。不过这里我们感兴趣的是魔都（mordor）这个映射：



译注：这个文件大小 32GB，已加载了 1521MB 到内存中，因为只有这一个进程映射了它，所以在这个进程的PSS中占比是100%，也是 1521MB。

在共享映射里的私有页面 —— 搞得我像巫师一样？在Linux上，即使共享内存也会被认为是私有的，除非它真的被共享了（译注：不止一个进程创建共享映射）。让我们看看它是否在系统缓冲区里：



译注：

1.  “-m 64G” 表示允许 vmtouch 将小于 64G 的文件加载到内存中，应当是用于需要加载一个目录下的文件、但排除其中过大的文件，似乎不适用于这里；至少忽略这个参数不影响阅读
   
2.  o 表示这一块部分被加载，O 表示全部被加载。因为物理内存有限，虽然全量读取了文件，但只有部分内容被缓存

嗬，只是简单地读取一个文件就会把它缓存起来？先不管这，我们的进程呢？



常见的误解是，映射文件会消耗内存，而通过文件API读取不会。实际上，无论哪一种方式，包含文件内容的页面都会被放进系统缓冲区。但还有个小的区别是，使用mmap的方式需要在进程的页表中创建对应的页表项（PTE），而这些包含文件内容的页面是可以被共享的。有趣的是，我们这个进程的RSS缩小了，因为系统 _需要_ 进程的页面了（译注：因为 mordor 太大，可用物理内存页不够，系统将 the_eye 的部分页面swap了；所以前述命令才会需要等一分钟，因为涉及到磁盘IO）。 

## 有时我们的所有想法都是错的

映射文件的内存总是可被回收的，区别只在于该页是否脏页 —— 脏页在回收前需要被清理（译注：写回底层存储）。所以当你在 top 命令发现有一个进程占用了大量内存时是否需要恐慌？当这个进程有很多匿名的脏页的时候才需要恐慌——因为这些页面无法被回收。如果你发现有个匿名映射段在增长，你可能就有麻烦了（而且是双倍的麻烦）。但是不要盲目相信 RSS 甚至 PSS 。

另一个常见错误是认为进程的虚拟内存和实际消耗内存之间总有某种关系，甚至认为所有内存映射都一样。任何可回收的内存，实际上都可以认为是空闲的。简而言之，它不会导致你下次内存分配失败，但_可能_会增加分配的延迟 —— 这点我会解释： 

内存管理器需要花很大功夫来决定哪些东西需要保存在物理内存里。它可能会决定将进程内存中的一部分调到swap，以便给系统缓存腾出空间，因此该进程下次访问这一块时需要再将这些页面调回到物理内存中。幸运的是这通常是可以配置的。例如，Linux 有一个叫做 swappiness[5] 的选项，用来指导内核何时开始将匿名映射的内存页调出到swap。当它取值为 0 是表示“直到绝对绝对有必要的时候”（译注：取值[0, 100]，值越低，系统越倾向于先清理系统缓冲区的页面）。 

# 终章，一劳永逸地

如果你看到这里，向你致敬！我在工作之余写的这篇文章，希望能用一种更方便的方式，不仅能解释这些说过上千遍的概念，还能帮我整理这些思维，以及帮助其他人。我花了比预期更长的时间。远超预期。 

我对文章的作者们只有无尽的敬意，因为写作真是个冗长乏味、令人头秃的过程，需要永无止境的修改和重写。Jeff Atwood（译注：stack overflow的创始人）曾说过，最好的学编程书籍是教你盖房子的那本。我不记得在哪儿了，所以无法引用它。我只能说，第二好的是教你写作的那本。说到底，编程本质上就是写故事，简明扼要。 

EDIT：我修正了关于 alloca() 和 将 sizeof(char) 误写为 sizeof(char*) 的错误，多亏了 immibis 和 BonzaiThePenguin。感谢 sWvich 指出在 slab + sizeof(struct slab) 里漏了的类型转换。显然我应该用静态分析跑一下这篇文章，但并没有 —— 涨经验了。

开放问题 —— 有没有比 Markdown 代码块更好的实现？我希望能展示带注释的摘录，并且能下载整个代码块。 

写于 2015 年 2 月 20 日。

---

---

读到这里都是真爱，喜欢的话请留言支持，让更多人看到，感谢~

照例再贴下之前推送的几篇文章：

* 《踩坑记：go服务内存暴涨》 
* 《TCP：学得越多越不懂》 
* 《UTF-8：一些好像没什么用的冷知识》
* 《关于RSA的一些趣事》
* 《程序员面试指北：面试官视角》

---

参考链接：
 
[1] What a C programmer should know about memory
https://marek.vavrusa.com/memory/

[2] vmtouch - the Virtual Memory Toucher
https://hoytech.com/vmtouch/

[3] kernel.org - THE /proc FILESYSTEM
https://www.kernel.org/doc/Documentation/filesystems/proc.txt

[4] FAQ (Why is “strict overcommit” a dumb idea?)
http://landley.net/writing/memory-faq.txt

[5] wikipedia - Paging - swapinness
https://en.wikipedia.org/wiki/Swappiness

续上篇：

* [译] Ｃ程序员该知道的内存知识 (1)
* [译] Ｃ程序员该知道的内存知识 (2)

这是本系列的第3篇，预计还会有1篇，感兴趣的同学记得关注，以便接收推送，等不及的推荐阅读原文。 

---

照例放图镇楼： 



来源：Linux地址空间布局 - by Gustavo Duarte

关于图片的解释参见第一篇。

开始吧。


## 有趣的内存映射

工具箱： 
* sysconf() - 在运行时获取配置信息
* mmap() - 映射虚拟内存
* mincore() - 判断页是否在内存中
* shmat() - 共享内存操作

有些事情是内存分配器没法完成的，需要内存映射来救场。比如说，你无法选择分配的地址范围。为了这个，我们得牺牲一些舒适性 —— 接下来将和整页内存打交道了。注意，虽然一页通常是 4KB，但你不应该依赖这个“通常”，而是应该用 sysconf() 来获取的实际大小： 



备注 —— 即使系统宣称使用统一的page size（译注：这里指sysconf的返回值），它在底层可能用了其他尺寸。例如Linux有个叫 transparent huge page（THP）[2]的概念，可以减少地址翻译的开销（译注：地址翻译指 虚拟地址->线性地址->物理地址，细节比较多，涉及到多级页表、MMU、TLB等，详情可参考知乎这篇文章《https://zhuanlan.zhihu.com/p/65298260" target="_blank">虚拟地址转换》[3]）和连续内存块访问导致的page fault（译注：本来4KB一次，现在4MB一次，少了3个量级）。但这里还要打个问号，尤其是当物理内存碎片化，导致连续的大块内存较少的情况。一次page fault的开销也会随着页面大小提高，因此对于少量随机IO负载的情况，huge page的效率并不高。很不幸这对你是透明的，但Linux有一个专有的 mmap 选项 MAP_HUGETLB 允许你明确指定使用这个特性，因此你应该了解它的开销。

## 固定内存映射

举个栗子，假如你现在得为一个小可怜的进程间通信（IPC）建立一个固定映射（译注：两个进程都映射到相同的地址），你该如何选择映射的地址呢？这有个在 x86-32 上可能有点风险的提案，但是在 64 bit上，大约在 TASK_SIZE 2/3 位置的地址（用户空间最高的可用地址；译注：见镇楼图右上方）大致是安全的。你可以不用固定映射，但是就别想用指向共享内存的指针了（译注：不固定起始地址的话，共享内存中同一个对象在两个不同进程的地址就不一样了，这样的指针无法在两个进程中通用）。



译注：如前文所述，开头用 mmap() 创建了一个稀疏数组 array；第四行应该是指代前述需要清理掉其中一部分数据；第7行用 mmap 重新映射从 array + offset 开始、长度为 length 字节的空间，注意这行的 length 应当是需要清理的数据长度，不同于第一行的length（整个稀疏数组的长度）。 


这等价于取消旧页面的映射，并将它们重新映射到那个**特殊页面**（译注：指上一篇说到的全 0 页面）。这会如何影响进程的内存消耗呢——进程仍然占用同样大小的虚拟内存，但是驻留在物理内存的尺寸减少了（译注：取消旧页面映射时，对应的真实页面被OS回收了）。这是我们能做到的最接近 *内存打洞* 的办法了。

## 基于文件的内存映射

工具箱： 
* msync() - 将映射到内存的文件内容同步到文件系统
* ftruncate() - 将文件截断到指定的长度
* vmsplice() - 将用户页面内容写入到管道

到这里我们已经知道关于匿名内存的所有知识了，但是在64bit地址空间中真正让人亮瞎眼的还是基于文件的内存映射，它可以提供智能的缓存、同步和写时复制（copy-on-write；译注：常缩写为COW）。是不是太多了点？ 



译注：LMDB（Lightning Memory-mapped DataBase）是一个轻量级的、基于内存映射的kv数据库，由于可以直接返回指针、避免值拷贝，所以性能非常高；更多细节详见wikipedia。 

基于文件的共享内存映射使用一个新的模式 MAP_SHARED ，表示你对页面的修改会被写回到文件，从而可以和其他进程共享。具体何时同步取决于内存管理器，不过还好有个 msync() 可以强制将改动同步到底层存储。这对于数据库来说很重要，可以保证被写入数据的持久性（durability）。但不是谁都需要它，尤其是不需要持久化的场景下，完全不需要同步，你也不用担心丢失 写入数据的可见性（译注：这里应该是指修改后立即可读取）。这多亏了页面缓存，得益于此你也可以用内存映射来实现高效的进程间通信。 



译注：MS_SYNC会等待写入底层存储后才返回；MS_ASYNC会立即返回，OS会异步写回存储，但期间如果系统异常崩溃就会导致数据丢失。 

注意，你不能映射比文件内容更长的内存，所以你无法通过这种方式增加或者减少文件的长度。不过你可以提前用 ftruncate() 来创建（或加长）一个稀疏文件（译注：稀疏文件是指，你可以创建一个很大的文件，但文件里只有少量数据；很多文件系统如ext\*、NTFS系列都支持只存储有数据的部分）。但稀疏文件的坏处是，会让紧凑的存储更困难，因为它同时要求文件系统和OS都支持才行。 

在Linux下，`fallocate(FALLOC_FL_PUNCH_HOLE)` 是最佳选项，但最适合移植（也最简单的）方法是创建一个空文件：



一个文件被内存映射，并不意味着不能再以文件来用它。这对于需要区分不同访问情况的场景很有用，比如说你可以一边把这个文件用只读模式映射到内存中，一边用标准的文件API来写入它。这对于有安全要求的情况很有用，因为暴露的内存映射是有写保护的，但还有些需要注意的地方。msync() 的实现没有严格定义，所以 MS_SYNC 往往就是一系列同步的写操作。呸，这样的话速度还不如用标准文件API，异步的 pwrite() 写入，以及 fsync() 或 fdatasync() 完成同步或使缓存失效。（译注：`pwrite(fd, buf, count, offset)` 往fd的offset位置写入从buf开始的count个字节，适合多线程环境，不受fd当前offset的影响；fsync(fd)、fdatasync(fd) 用于将文件的改动同步写回到磁盘） 

照例这有个警告——系统应当有一个统一的缓冲和缓存（unified buffer cache）。历史上，页面缓存（page cache，按页缓存文件的内容）和块设备缓存（block device cache，缓存磁盘的原始block数据）是两个不同的概念。这意味着同时使用标准API写入文件和使用内存映射读文件，二者会产生不一致，除非你在每次写入之后都使缓存失效。摊手。不过，你通常不用担心，只要你不是在跑OpenBSD或低于2.4版本的Linux。 

### 写时复制（Copy-On-Write）

前面讲的都还是关于共享的内存映射，但其实还有另一种用法——映射文件的一份拷贝，且对它的修改不会影响原文件。注意这些页面不会立即被复制，因为这没啥意义，而是在你修改时才被复制（译注：一方面，通常来说大部分页面不会被修改，另一方面，延迟到写时才复制，可以降低STW导致的延时）。这不仅有助于创建新进程（译注：fork新进程的时候只需要拷贝页表）或者加载共享库的场景，也有助于处理来自多个进程的大数据集的场景。



译注：MAP_PRIVATE 这个 flag 用于创建 copy-on-write 映射，对该映射的改动不影响其他进程，也不会写回到被映射的文件。当写入该映射时，会触发 page fault，内核的中断程序会拷贝一份该页，修改页表，然后再恢复进程的运行。

### 零拷贝串流（Zero-copy streaming）

由于（被映射的）文件本质上就是一块内存，你可以将它“串流”（stream）到管道（也包括socket），用零拷贝模式（译注：“零拷贝”不是指完全不拷贝，而是避免在内核空间和用户空间之间来回拷贝，其典型实现是先 read(src, buf, len) 再 write(dest, buf, len) ）。和 splice() 不同的是，vmsplice 适用于 copy-on-write 版本的数据（译注：splice的源数据用fd指定，vmsplice的源数据用指针指定）。*免责声明：这只适用于使用Linux的老哥！*



译注：vmsplice第二个参数 iov 是一个指针，上例只指向一个 struct iovec，实际上它可以是一个数组，数组的长度由第三个参数标明。 

译注：举几个具体的场景，例如 nginx 使用 sendfile（底层就是splice）来提高静态文件的性能；php也提供了一个 readfile() 方法来实现零拷贝发送文件；kafka将partition数据发送给consumer时也使用了零拷贝技术，consumer数量越多，节约的开销越显著。

### mmap不顶用的场景

还有些奇葩的场景，映射文件性能会比常规实现差得多。按理来说，处理page fault会比简单读取文件块要慢，因为除了读取文件还需要做其他事情（译注：修改页表等）。但实际上，基于映射的文件IO也可能更快，因为可以避免对数据的双重甚至三重缓存（译注：可能是指文件库的缓存，例如os本身会有缓存，c的fopen/fread还内建了缓存），并且可以在后台预读数据。但有时这也有害。一个例子是“小块随机读取大于可用内存的文件”（译注：如2G内存，4G的文件，每次从随机位置读取几个字节），在这个场景下，系统预读的块大概率不会被用上，而每一次访问都会触发page fault。当然你也可以用 madvise() 做一定程度的优化（译注：用上 MADV_RANDOM 这个建议，告诉OS预读没用）。 

还有 TLB 抖动（thrashing）的问题。将虚拟页的地址翻译到物理地址是有硬件辅助的，CPU会缓存最近的翻译 —— 这就是 TLB（Translation Lookaside Buffer；译注：可译作“后备缓冲器”，CPU中的MMU专用的缓存，用来加速地址翻译）。随机访问的页面数量超过缓存能力必然会导致**抖动（thrashing）**_，_因为（在缓存不顶用时）系统必须遍历页表才能完成地址翻译。对于其他场景可以考虑使用 huge page ，但这里行不通，因为仅仅为了访问几个字节而读取几MB的数据会让性能变得更糟。 

---

下一篇会继续翻译最后一节《Understanding memory consumption》，敬请关注~

以及照例再贴下之前推送的几篇文章：

* 《踩坑记：go服务内存暴涨》 
* 《TCP：学得越多越不懂》 
* 《UTF-8：一些好像没什么用的冷知识》
* 《关于RSA的一些趣事》
* 《程序员面试指北：面试官视角》

---

**参考链接：**

[1] What a C programmer should know about memory
https://marek.vavrusa.com/memory/

[2] Linux - Transparent huge pages
https://lwn.net/Articles/423584/

[3] 虚拟地址转换
https://zhuanlan.zhihu.com/p/65298260

[4] Reddit - What every programmer should know about solid-state drives
https://www.reddit.com/r/programming/comments/2vyzer/what_every_programmer_should_know_about/comhq3s

续上篇：

*  [译] Ｃ程序员该知道的内存知识 (1)

这是本系列的第二篇，预计还会有2篇，感兴趣的同学记得关注，以便接收推送，等不及的推荐阅读原文。 

---

先放图镇楼： 



来源：Linux地址空间布局 - by Gustavo Duarte

关于图片的解释可参见上篇。

开始吧。 

---

# 理解堆上的内存分配

工具箱： 

* brk(), sbrk() - 修改数据段的大小
* malloc() 家族 - 可移植的 libc 内存分配器

堆上的内存分配，最简单的实现可以是修改 program break[2]（译注：参见上图中部右侧）的上界，申请对原位置和新位置之间内存的访问权限。如果就这么搞的话，堆上内存分配和栈上分配一样快（除了换页的开销，一般我们认为栈是被锁定在内存中；译注：指栈不会被换出到磁盘，可以用mlock限制OS对一段地址空间使用swap）。但这里还是有只猫（cat），我是说，有点毛病（catch），见鬼。（译tu注cao：这个真难翻）


* 我们无法回收不再使用的内存块   
* 它也不是线程安全的，因为堆是在线程间共享的
* 这个接口（译注：sbrk）也很难移植，因此库函数被禁止碰这个break。

[qoute]man 3 sbrk — 各种系统的 sbrk 使用多种不同的参数类型，常见的包括 int, ssize_t, ptrdiff_t, intptr_t[/quote]

由于这些问题，libc要求实现统一的内存分配接口，具体实现有很多[3]（译注：例如glibc，jemalloc，tcmalloc等），但都给你提供了线程安全、支持任意尺寸的内存分配器……只是要付出点代价——延迟，因为得引入锁机制，以及用来维护已用/可用内存的数据结构，和额外的内存开销。还有，堆也不是唯一的选项，在大块内存分配的情况下常常也会用内存映射段（Memory Mapping Segment，MMS）。

[qoute]man 3 malloc —— 一般来说，malloc() 从堆上分配内存,  ... 当分配的内存块大于 MMAP_THRESHOLD 时，glibc的 malloc() 实现使用私有匿名映射来分配内存。[/qoute]

（译注：Linux 下 mmap 的 flags 参数是个 bitmap，其中有两个 bit 分别为 MAP_PRIVATE、MAP_ANONYMOUS，对应引用中提到的“私有”、“匿名”） 

由于堆空间在 start_brk 和 brk （译注：即 heap 的下界和上界，建议对照图中右侧的标注）之间总是连续的（译注：这里指的是虚拟地址空间连续，但其中每一页都可能映射到任一物理页），因此你无法在中间打个洞来减少数据段的尺寸。比如这个场景： 



堆分配器将会调大 brk，以便给 truck 腾出空间。对于 bike 也一样。但是当 truck 被释放后，brk 不能被调小，因为 bike 正占着高位的地址。结果是，你的进程 **可以** 重用 truck 的内存，但 **不能** 退还给OS，除非 bike 也被释放。当然你也可以用 mmap 来分配 truck 所需的空间，不放在堆内存段里，就可以不影响 program break ，但这仍然无法解决分配小块内存导致的空洞（换句话说就是“引起碎片化”）。

注意 free() 并不总是会缩小数据段，因为这是一个有很大潜在开销的操作（参见后文“对按需调页的解释”）。对于需要长时间运行的程序（例如守护进程）来说这会是个问题。有个叫  malloc_trim() 的 GNU 扩展可以用来从堆顶释放内存，但可能会慢得令人蛋疼，尤其对于大量小对象的情况，所以应该尽量少用。

## 什么时候应该使用自定义分配器

有一些实际场景中通用分配器有短板，例如大量分配固定尺寸的小内存。这看起来不像是典型的场景，但实际上出现得很频繁 。例如，用于查找的数据结构（典型如树、字典树）需要分配大量节点用于构造其层次结构。在这个场景下，不仅碎片化会是个问题，数据的局部性也是。cache效率高的数据结构会将key放在一起（最好在同一个内存页），而不是和数据混在一起。默认的分配器不能保证下次分配时还在同一个block，更糟的是分配小单元的额外空间开销。解决办法在此：

X

来源: Slab by wadem, on Flickr (CC-BY-SA)

（译注：原图无法打开了，另贴一张）



来源：IBM - Linux slab 分配器剖析


## Slab分配器

工具箱：
* posix_memalign() - 分配对齐的内存

Bonwick 为内核对象缓存写的这篇文章[4]介绍了 slab 分配器的原理，也可用于用户空间。Okay，我们对绑定在CPU上的 slab 不感兴趣 —— 就是你找分配器要一块内存，例如说一整页，然后切成很多固定大小的小块。如果每个小块都能保存至少一个指针或一个整数，你就可以把他们串成一个链表 ，表头指向第一个空闲元素。



译注：
1. 代码里用的二级指针可能让人有点晕，这是Linus推崇的链表实现，推荐阅读"linus torvalds answers your questions"[5]，在favorite hack这一节，是个很有趣的思维训练
2. 第8行 `posix_memalign` 分配了一页内存，并且对齐到页边界，这意味着正好拿到了一个物理页
3. 因为申请到的 slab 大小是一个page，所以 `item_count` = `page_size` / `item_size`；其中 `item_size` 可以根据应用需要指定。

然后内存分配就简单到只要弹出链表的头结点就行了，内存释放则是插入头结点。这里还有个优雅的小技巧：既然 slab 对齐到了页边界，你只要将指针向下取整到 page_size 就能得到这个 slab 的指针。



译注：对于 page_size = 4KB 的页面，PAGESIZE_BITS = 0xFFFFF000，ptr & PAGESIZE_BITS 清零了低12位，正好是这一页的开始，也就是这个slab的起始地址。

太棒了，但是还有binning（译注：应该是指按不同的长度分桶），变长存储，cache aliasing（译注：同一个物理地址中的数据出现在多个不同的缓存行中），咖啡因（译注：这应该是作者在逗逼了），...怎么办？可以看看我之前为 Knot DNS 写的代码[6]，或者其他实现了这些点的库。例如，（喘口气），glib 里有个很整齐的文档[7]，把它称为“memory slices”。 

译注：slab 分配器适合大量小对象的分配，可以避免常见的碎片问题；在内核中的实现还可以支持硬件缓存对齐，从而提高缓存的利用率。

## 内存池

工具箱：
* obstack_alloc() - 从object stack中分配内存
（译注：指 GNU 的 obstack ，用stack来保存object的内存池实现）

正如slab分配器一样，内存池比通用分配器好的地方在于，你每次申请一大块内存，然后像切蛋糕一样一小块一小块切出去，直到不够用了，然后你再申请一大块。还有，当你都处理完了以后，你就可以收工，一次性释放所有空间。

是不是特别傻瓜化？因为确实如此，但只是针对特定场景如此。你不需要考虑同步，也不需要考虑释放。再没有忘记回收的坑了，数据的局部性也更加符合预期，而且对于小对象的开销也几乎为0。

这个模式特别适合很多类型的任务，包括短生命周期的重复分配（例如网络请求处理），和长生命周期的不可变数据（例如frozen set；译注：创建后不再改变的集合）。你不再需要逐个释放对象（译注：可以最后批量释放）。如果你能合理推测出平均需要多少内存，你还可以将多余的内存释放，以便用于其他目的。这可以将内存分配问题简化成简单的指针运算。 

而且你很走运 —— GNU libc 提供了，嗬，一整套API来干这事儿。这就是 obstacks ，用栈来管理对象。它的 HTML 文档[8] 写得不咋地，不过抛开这些小缺陷，它允许你完成基于内存池的分配和回收（包括部分回收和全量回收）。



译注：obstack这些api实际都是宏；需要通过宏来指定找OS分配和回收整块内存用的方法，如上第2、3行所示。由于对象使用栈的方式管理（先分配的最后释放），所以释放 fred 的时候，会把 fred 和在 fred 之后分配的对象（roger）一起释放掉。 

还有个小技巧：你可以扩展栈顶的那个对象。例如带缓冲的输入，变长数组，或者用来替代 realloc()-strcpy() 模式（译注：重新分配内存，然后把原数据拷贝过去）： 



译注：前三行是作者逗逼了，看后四行就行；用 obstack_grow 扩展栈顶元素占用的内存，扩展结束后调用 obstack_finish 结束扩展，并返回栈顶元素的地址。

## 对按需调页（demand paging）的解释

工具箱：
* mlock() - 锁定/解锁内存（避免被换出到swap）
* madvise() - 给（内核）建议指定内存范围的处置方式

通用内存分配器不立即将内存返回给系统的原因之一是，这个操作开销很大。系统需要做两件事：(1) 建立 **虚拟** 页到 **真实（real）** 页的映射，和 (2) 给你一个清零的**真实**页。这个真实页被称为**帧（frame）**，现在你知道它们的差别了。每一帧都必须被清空，毕竟你不希望 OS 泄漏其他进程的秘密，对吧。这里还有个小技巧，还记得 **overcommit** 吗？虚拟内存分配器只把这个交易刚开始的那部分当回事，然后就开始变魔术了 —— 页表里的大部分页面并不指向一个真实页，而是指向一个特殊的全 0 页面。 

每次你想要访问这个页面时，就会触发一个 page fault，这意味着内核会暂停 进程的执行，分配一个真实页、更新页表，然后恢复进程，并假装什么也没发生。这是汇总在一句话里、我能做出的最好解释了，这里[9]还有更个详细的版本。这也被称作**“按需调页”（demand paging）** 或 **“延迟加载”（lazy loading）**。



（译注：星际迷航，斯波克说“One man cannot summon the future.”，柯克说“But one man can change the present.”）

内存管理器不是先知，他只是保守地预测你访问内存的方式，而你自己也未必更清楚（你将会怎样访问内存）。（如果你知道）你可以将一段连续的内存块锁定在**物理**内存中，以避免后续的page fault： 



（译注：访问被换出到swap的页面会触发page fault，然后内存管理器会从磁盘中载入页面，这会导致较严重的性能问题；用 mlock 将这段区域锁定后，OS就不会被操作系统换出到swap；例如，在允许的情况下，MySQL会用mlock将索引保持在物理内存中）

注意：你还可以根据自己的内存使用模式，给内核提出建议 



对建议的解释是平台相关的，系统甚至可能选择忽略它，但大部分平台都处理得很好。但不是所有建议都有良好的支持，有些平台可能会改变建议的语义（如MADV_FREE移除私有脏页；译注：“脏页”，dirty page，是指分配以后有过写入，其中可能有未保存的数据），但是最常用的还是MADV_SEQUENTIAL, MADV_WILLNEED, 和 MADV_DONTNEED 这神圣三人组（译注：holy trinity，圣经里的三位一体，作者用词太跳脱……）。

译注：还记得《踩坑记：go服务内存暴涨》里对 MADV_DONTNEED 和 MADV_FREE 的解释吗？这里再回顾下
* MADV_DONTNEED：不再需要的页面，Linux会立即回收
* MADV_FREE：不再需要的页面，Linux会在需要时回收
* MADV_SEQUENTIAL：将会按顺序访问的页面，内核可以通过预读随后的页面来优化，已经访问过的页面也可以提前回收
* MADV_WILLNEED：很快将访问，建议内核提前加载

---

又到休息点，这篇暂时到这里。 

下一篇会继续翻译下一节《Fun with memory mapping》，还有很多有意思的内容，敬请关注~

顺便再贴下之前推送的几篇文章，祝过个充实的五一假期~

* 《踩坑记：go服务内存暴涨》 
* 《TCP：学得越多越不懂》 
* 《UTF-8：一些好像没什么用的冷知识》
* 《关于RSA的一些趣事》
* 《程序员面试指北：面试官视角》

---

参考链接：
[1] What a C programmer should know about memory
https://marek.vavrusa.com/memory/

[2] sbrk(2) - Linux man page
https://linux.die.net/man/2/sbrk

[3] C Programming/stdlib.h/malloc
https://en.wikibooks.org/wiki/C_Programming/C_Reference/stdlib.h/malloc#Implementations

[4] The Slab Allocator: An Object-Caching Kernel Memory Allocator
https://www.usenix.org/legacy/publications/library/proceedings/bos94/full_papers/bonwick.a

[5] linus torvalds answers your questions
https://meta.slashdot.org/story/12/10/11/0030249/linus-torvalds-answers-your-questions

[6] Knot DNS - slab.h
https://github.com/CZNIC-Labs/knot/blob/1.5/src/common-knot/slab/slab.h

[7] glib  - memory slices
https://developer.gnome.org/glib/stable/glib-Memory-Slices.html

[8] GNU libc - Obstacks
https://www.gnu.org/software/libc/manual/html_node/Obstacks.html

[9] How the kernel manages your memory
http://duartes.org/gustavo/blog/post/how-the-kernel-manages-your-memory/

上篇 《踩坑记：go服务内存暴涨》还挺受欢迎的。虽然文中的核心内容很少，但是为了让大多数人能读懂，中间花了很大的篇幅来解释。

尽管如此，我仍然觉得讲得不够透，思来想去觉得还是文中提到的《What a C programmer should know about memory》[1]讲得好，想借着假期翻译一下，也借机再学习一遍（顺便练习英文）。

内容有点长，我会分成几篇。

以下是正文。

# C程序员应该知道的内存知识

2007年，Ulrich Drepper 大佬写了一篇“每个程序员都应该知道的内存知识”[2]，特别长，但干货满满。

但过去了这么多年（译注：原文写于2015年2月），“虚拟内存”这个概念对很多人依然很迷，就像*某种魔法*。呃，实在是忍不住引用一下（译注：应该是指皇后乐队的 A Kind of Magic）。

即使是该文的正确性，这么多年以后仍然被质疑[3]（译注：有人在stackoverflow上提问文中内容有多少还有效）。出了什么事？



（译注：北桥是早年电脑主板上的重要芯片，用来处理来自CPU、内存等设备的高速信号）

我会试着展现学习这些知识的实用性（即你可以做什么），包括“学习锁的基本原理”，和更多有趣的东西。你可以把这当成那篇文章和你日常使用的东西之间的胶水。

文中例子会使用 Linux 下的 C99 来写（译注：1999年版的c语言标准），但很多主题都是通用的。注：我对 Windows 不太熟悉，但我会很高兴附上能解释它的文章链接（如果有的话）。我会尽量标注哪些方法是特定平台相关的。但我只是个凡人，如果你发现有出入，请告诉我。

# 理解虚拟内存 - 错综复杂

除非你在处理某些嵌入式系统或内核空间代码，否则你会在保护模式下工作。（译注：指的是x86 CPU提出的保护模式，通过硬件提供的一系列机制，操作系统可以用低权限运行用户代码）。这*太棒了*，你的程序可以有独立的 [虚拟] 地址空间。“虚拟”这个词在这里很重要。这表示，包括其他一些情况，你不会被可用内存限制住，但也没有资格使用任何可用内存。想用这个空间，你得找OS要一些真东西来做“里子”，这叫 映射（mapping）。这个里子（backing）可以是物理内存（并不一定需要是RAM），或者持久存储（译注：一般指硬盘 ）。前者被称为*“匿名映射”*。别急，马上讲重点。

虚拟内存分配器（VMA，virtual memory allocator）可能会给你一段并不由他持有的内存，并且徒劳地希望你不去用它。就像如今的银行一样（译注：应该是指银行存款）。这被称为 overcommiting\[4\]（译注：指允许申请超过可用空间的内存），有一些正当的应用有这种需求（例如稀疏数组），这也意味着内存分配不会简单被拒绝。



检查 NULL 返回值是个好习惯，但已经没有过去那么强大了。由于 overcommit 机制的存在，OS可能会给你的内存分配器一个有效的指针，但是当你要访问它的时候 —— 铛*。这里的“*铛”是平台相关的，但是通常表现为你的进程被 OOM Killer [5]干掉。（译注：OOM 即 Out Of Memory，当内存不足时，Linux会根据一定规则挑出一个进程杀掉，并在 dmesg 里留下记录）

—— 这里有点过度简化了；在后面的章节里有进一步的解释，但我倾向于在钻研细节之前先过一遍这些更基础的东西。

# 进程的内存布局

进程的内存布局在 Gustavo Duarte 的《Anatomy of a Program in Memory》[6] 里解释得很好了，所以我只引用原文，希望这算是*合理使用*。我只有一些小意见，因为该文只介绍了 x86-32 的内存布局，不过还好 x86-64 变化不大，除了进程可以用大得多的空间 —— 在 Linux 下高达 48 位。



(来源：Linux地址空间布局 - by Gustavo Duarte)

译注：针对上图加一些解释备查

1. 图中显示的地址空间是由高到低，0x00000000在底部，最高0xFFFFFFFF，一共4GB（2^32）。
2. 高位的1GB是内核空间，用户代码 **不能** 读写，否则会触发段错误。图右侧标注的 0xC0000000 即 3GB；TASK\_SIZE 是Linux内核编译配置的名称，表示内核空间的起始地址。
3. Random stack offset：加上随机偏移量以后可以大幅降低被栈溢出攻击的风险。
4. Stack（grows down）: 进程的栈空间，向下增长，栈底在高位地址，PUSH指令会减小CPU的SP寄存器（stack pointer）。图右侧的 RLIMIT\_STACK 是内核对栈空间大小的限制，一般是8MB，可以用 setrlimit 系统调用修改。
5. Memory Mapping Segment：内存映射区，通过mmap系统调用，将文件映射到进程的地址空间（包括 libc.so 这样的动态库），或者匿名映射（不需要映射文件，让OS分配更多有里子的地址空间）。
6. Heap：我们常说的堆空间，从下往上增长，通过brk/sbrk系统调用扩展其上限
7. BSS段：包含未初始化的静态变量   
8. Data段：代码里静态初始化的变量
9. Text段（ELF）：进程的可执行文件（机器码）
10. 这里说的段（segment）的概念，源于x86 cpu的段页式内存管理

图中也展示了 内存映射段（memory mapping segment, MMS）是向下增长的，但并不总是这样。MMS通常（详见Linux 内核代码 x86/mm/mmap.c:113 和 arch/mm/mmap.c:1953）开始于栈的最低地址（译注：即栈底）以下的某个随机地址。注意是“通常”，因为它也可能在栈的上方 ，如果栈空间限制很大（或无限；译注：可用setrlimit修改），或者启用了兼容布局。这一点有多重要？——不重要，但可以让你了解到*自由地址范围*（free address ranges）。

在上图中，你可以看到3个不同的变量存放区：进程的数据段（静态存储，或堆内存分配），内存映射段，和栈。我们从这里开始。


# 理解栈上的内存分配

装备箱：
* alloca() - 在调用方的栈帧上分配内存
* getrlimit() - 获取/设置 resource limits
* sigaltstack() - 设置或获取信号栈上下文

栈相对比较容易理解，毕竟每个人都知道如何在栈上放一个变量，对吧 ？比如：



变量的有效性受到作用域的限制。在 C 里，作用域指的就是一对大括号 `{}`。因此每次遇到一个右大括号，对应的变量作用域就结束了。

然后是 alloca()，在当前 *栈帧*上动态分配内存。栈帧和内存帧（也叫做物理页）不太一样，它只是一组被压到栈上的数据（函数，参数，变量等）。由于我们在栈顶（译注：SP寄存器总是指向栈顶），我们可以使用剩下的栈空间，只要不超过栈大小限制。

这就是变长数组（variable-length，VLA）和 alloca 的原理，区别在于 ，VLA受限于作用域，alloca分配的内存的有效性可以持续到当前函数返回。这里没有语言律师业务（译注：没人管你，爱咋咋地），但如果你在循环里用alloca可能会踩坑，因为你没办法释放它分配的空间：



如果要申请大量内存，VLA和alloca都不太好使，因为你几乎无法控制可用的栈空间，如果分配内存超过栈限制，就会遇到令人喜闻乐见的stack overflow。有两种办法可以绕过它，但都不太实用：

第一种是用  `sigaltstack()` 来捕获并处理 SIGSEGV 信号，但这只能让你捕获栈溢出（译注：程序仍然无法获得所需的内存）。

另一种是编译时指定“split-stacks”，这会将一个大的stack分割成用链表组织的“栈碎片”（stacklet）。就我所知，GCC 和 clang 编译器可以用 `-fsplit-stasck` 选项来启用这个特性。理论上这会改善内存消耗，并降低创建线程的开销，因为刚开始的时候栈可以很小，并按需扩展。但实际上可能会遇到兼容问题，因为这需要一个支持 split-stack 的链接器（例如 gold；译注：这是GNU的ELF链接器，不同于我们常用的链接器 ld，针对ELF链接性能更好）、而这是对库透明的，还可能有性能问题，例如 Go 的 hot-split 问题，在 Agis Anastasopoulos 的这篇文章[7] 中有详细解释。（译注：Go 1.3 之前用 split stack，即前述用链表串起来的栈，在某些情况可能因反复的栈扩展和收缩带来性能问题；1.3 开始改成使用连续的栈空间，空间不够时重新分配、拷贝内容、修改指向栈空间的指针，因此也要求编译器能准确分析指针逃逸的情况）


* * *
 

休息一下，第一篇就到这里。

下一篇接着翻译下一节 Understanding  heap allocation，感兴趣的记得关注，等不及的推荐阅读原文。

顺便再贴下之前推送的几篇文章，祝过个充实的五一假期~

* 《踩坑记：go服务内存暴涨》 
* 《TCP：学得越多越不懂》 
* 《UTF-8：一些好像没什么用的冷知识》
* 《关于RSA的一些趣事》
* 《程序员面试指北：面试官视角》


* * *


# 参考链接：


[1] What a C programmer should know about memory
https://marek.vavrusa.com/memory/

[2] What every programmer should know about memory
http://www.akkadia.org/drepper/cpumemory.pdf

[3] stackoverflow.com - What Every Programmer Should Know About Memory?
https://stackoverflow.com/questions/8126311/what-every-programmer-should-know-about-memory

[4] Kernel - overcommit accounting
https://www.kernel.org/doc/Documentation/vm/overcommit-accounting

[5] Linux - Overcommit and OOM
https://www.win.tue.nl/~aeb/linux/lk/lk-9.html#ss9.6

[6] anatomy of a program in memory
http://duartes.org/gustavo/blog/post/anatomy-of-a-program-in-memory/

[7] Contiguous stacks in Go
http://agis.io/2014/03/25/contiguous-stacks-in-go.html

这周换换口味，记录一下去年踩的一个大坑。 

起

大概是去年8月份，那会儿我们还在用着64GB的“小内存”机器。

由于升级一次版本需要较长的时间（1~2小时），因此我们每天只发一次车，由值班的同学负责，发布所有已merge的commit。 

当天负责值班的我正开着车，突然收到 Bytedance-System 的夺命连环call，打开Lark一看：



打开ganglia一看，更令人害怕：