Jun
21
之前从网上找的一段代码，按行读取文件:
看起来没问题，用起来也没问题，直到踩了个坑：针对某个特定的文件，读取到某一行以后就不再继续了。
既然总能复现，那就好解决，我的一个常用方法是：制造一个总能复现的case，并不断缩小case的规模。
例如这个case，把那一行单独拿出来，通过二分找到出问题的位置。
原以为是该行有特殊字符导致触发了什么奇怪的逻辑，但经过不断尝试，发现临界点是该行长度 = 65536 的时候，正好会触发错误。
这么整的数字（2^16, 64KB）必然是代码里的特殊逻辑了，翻了一下 bufio 的源码，果然有一个
搜索这个常量在代码里的引用：
在 for 循环后加上一句：
实锤：
那怎么解决呢？
MaxScanTokenSize 上面的注释是这么写的：
于是最终版的解决方案是这样：
真是丑陋的api啊。
inFile, err := os.Open("xxx.log")
if err != nil {
fmt.Fprintf(os.Stderr, "open failed: %v\n", err)
return
}
defer inFile.Close()
scanner := bufio.NewScanner(inFile)
for scanner.Scan() {
line := scanner.Bytes()
//do sth. with line
}
if err != nil {
fmt.Fprintf(os.Stderr, "open failed: %v\n", err)
return
}
defer inFile.Close()
scanner := bufio.NewScanner(inFile)
for scanner.Scan() {
line := scanner.Bytes()
//do sth. with line
}
看起来没问题，用起来也没问题，直到踩了个坑：针对某个特定的文件，读取到某一行以后就不再继续了。
既然总能复现，那就好解决，我的一个常用方法是：制造一个总能复现的case，并不断缩小case的规模。
例如这个case，把那一行单独拿出来，通过二分找到出问题的位置。
原以为是该行有特殊字符导致触发了什么奇怪的逻辑，但经过不断尝试，发现临界点是该行长度 = 65536 的时候，正好会触发错误。
这么整的数字（2^16, 64KB）必然是代码里的特殊逻辑了，翻了一下 bufio 的源码，果然有一个
const (
//...(一堆注释)...
MaxScanTokenSize = 64 * 1024
)
//...(一堆注释)...
MaxScanTokenSize = 64 * 1024
)
搜索这个常量在代码里的引用：
func NewScanner(r io.Reader) *Scanner {
return &Scanner{
r: r,
split: ScanLines,
maxTokenSize: MaxScanTokenSize,
}
}
...
func (s *Scanner) Scan() bool {
....
if len(s.buf) >= s.maxTokenSize || len(s.buf) > maxInt/2 {
s.setErr(ErrTooLong)
return false
}
...
}
return &Scanner{
r: r,
split: ScanLines,
maxTokenSize: MaxScanTokenSize,
}
}
...
func (s *Scanner) Scan() bool {
....
if len(s.buf) >= s.maxTokenSize || len(s.buf) > maxInt/2 {
s.setErr(ErrTooLong)
return false
}
...
}
在 for 循环后加上一句：
if scanner.Err() != nil {
fmt.Fprintf(os.Stderr, "scan err: %v\n", scanner.Err())
}
fmt.Fprintf(os.Stderr, "scan err: %v\n", scanner.Err())
}
实锤：
引用
scan err: bufio.Scanner: token too long
那怎么解决呢？
MaxScanTokenSize 上面的注释是这么写的：
引用
// MaxScanTokenSize is the maximum size used to buffer a token
// unless the user provides an explicit buffer with Scanner.Buffer.
// The actual maximum token size may be smaller as the buffer
// may need to include, for instance, a newline.
// unless the user provides an explicit buffer with Scanner.Buffer.
// The actual maximum token size may be smaller as the buffer
// may need to include, for instance, a newline.
于是最终版的解决方案是这样：
...
scanner := bufio.NewScanner(inFile)
buf := make([]byte, 0, bufio.MaxScanTokenSize * 10) //根据自己的需要调整这个倍数
scanner.Buffer(buf, cap(buf))
for scanner.Scan() {
line := scanner.Bytes()
//do sth. with line
}
if scanner.Err() != nil {
fmt.Fprintf(os.Stderr, "scan err: %v\n", scanner.Err())
}
scanner := bufio.NewScanner(inFile)
buf := make([]byte, 0, bufio.MaxScanTokenSize * 10) //根据自己的需要调整这个倍数
scanner.Buffer(buf, cap(buf))
for scanner.Scan() {
line := scanner.Bytes()
//do sth. with line
}
if scanner.Err() != nil {
fmt.Fprintf(os.Stderr, "scan err: %v\n", scanner.Err())
}
真是丑陋的api啊。
May
24
系列更新：
* [译] Ｃ程序员该知道的内存知识 (1)
* [译] Ｃ程序员该知道的内存知识 (2)
* [译] Ｃ程序员该知道的内存知识 (3)
这是本系列的第4篇，也是最后一篇，含泪填完这个坑不容易，感谢阅读~
这个系列太干了，阅读量一篇比一篇少，但我仍然认为这个系列非常有价值，在翻译的过程中我也借机进行系统性的梳理、并学习了很多新知识，收获满满。希望你也能有收获（但肯定没我多）。
那，开始吧。
# 理解内存消耗
工具箱：
* vmtouch [2] - portable virtual memory toucher
（译注：vmtouch这个工具用来诊断和控制系统对文件系统的缓存，例如查看某个文件被缓存了多少页，清空某个文件的缓存页，或将某个文件的页面锁定在内存中；基于这些功能可以实现很多有意思的应用；详情参考该工具的文档。）
然而共享内存的概念导致传统方案 —— 测量对内存的占用 —— 变得无效了，因为没有一个公正的方法可以测量你进程的独占空间。这会引起困惑甚至恐惧，可能是两方面的：
用上了基于 mmap 的I/O操作后，我们的应用现在几乎不占用内存.
— CorporateGuy
求救！我这写入共享内存的进程有严重的内存泄漏！！！
— HeavyLifter666
页面有两种状态：清洁(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)
这是本系列的第4篇，也是最后一篇，含泪填完这个坑不容易，感谢阅读~
这个系列太干了，阅读量一篇比一篇少，但我仍然认为这个系列非常有价值，在翻译的过程中我也借机进行系统性的梳理、并学习了很多新知识，收获满满。希望你也能有收获（但肯定没我多）。
那，开始吧。
# 理解内存消耗
工具箱：
* vmtouch [2] - portable virtual memory toucher
（译注：vmtouch这个工具用来诊断和控制系统对文件系统的缓存，例如查看某个文件被缓存了多少页，清空某个文件的缓存页，或将某个文件的页面锁定在内存中；基于这些功能可以实现很多有意思的应用；详情参考该工具的文档。）
然而共享内存的概念导致传统方案 —— 测量对内存的占用 —— 变得无效了，因为没有一个公正的方法可以测量你进程的独占空间。这会引起困惑甚至恐惧，可能是两方面的：
引用
用上了基于 mmap 的I/O操作后，我们的应用现在几乎不占用内存.
— CorporateGuy
求救！我这写入共享内存的进程有严重的内存泄漏！！！
— HeavyLifter666
页面有两种状态：清洁(clean)页和脏(dirty)页。区别是，脏页在被回收之前需要被写回到持久存储中（译注：写回文件实际存放的地方）。MADV_FREE 这个建议通过将脏标志位清零这种方式来实现更轻量的内存释放，而不是修改整个页表项（译注：page table entry，常缩写为PTE，记录页面的物理页号及若干标志位，如能否读写、是否脏页、是否在内存中等）。此外，每一页都可能是私有的或共享的，这正是导致困惑的源头。
前面引用的两个都是（部分）真实的，取决于视角。在系统缓冲区的页面需要计入进程的内存消耗里吗？如果进程修改了缓冲区里那些映射文件的那些页面呢？在这混乱中可以整出点有用的东西么？
假设有一个进程，索伦之眼（the_eye）会写入对 魔都（mordor） 的共享映射（译注：指环王的梗）。写入共享内存不计入 RSS（resident set size，常驻内存集）的，对吧？
$ ps -p $$ -o pid,rss
PID RSS
17906 1574944 # <-- 什么鬼? 占用1.5GB？
PID RSS
17906 1574944 # <-- 什么鬼? 占用1.5GB？
（译注：$$ 是 bash 变量，保存了在执行当前script的shell的PID；这里应该是用来指代the_eye的PID）
呃，让我们回到小黑板。
## PSS（Proportional Set Size）
PSS（译注：Proportional 意思是 “比例的”） 计入了私有映射，以及按比例计入共享映射。这是我们能得到的最合理的内存计算方式了。关于“比例”，是指将共享内存除以共享它的进程数量。举个例子，有个应用需要读写某个共享内存映射：
$ cat /proc/$$/maps
00400000-00410000 r-xp 0000 08:03 1442958 /tmp/the_eye
00bda000-01a3a000 rw-p 0000 00:00 0 [heap]
7efd09d68000-7f0509d68000 rw-s 0000 08:03 4065561 /tmp/mordor.map
7f0509f69000-7f050a108000 r-xp 0000 08:03 2490410 libc-2.19.so
7fffdc9df000-7fffdca00000 rw-p 0000 00:00 0 [stack]
... 以下截断 ...
00400000-00410000 r-xp 0000 08:03 1442958 /tmp/the_eye
00bda000-01a3a000 rw-p 0000 00:00 0 [heap]
7efd09d68000-7f0509d68000 rw-s 0000 08:03 4065561 /tmp/mordor.map
7f0509f69000-7f050a108000 r-xp 0000 08:03 2490410 libc-2.19.so
7fffdc9df000-7fffdca00000 rw-p 0000 00:00 0 [stack]
... 以下截断 ...
（译注：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）这个映射：
$ grep -A12 mordor.map /proc/$$/smaps
Size: 33554432 kB
Rss: 1557632 kB
Pss: 1557632 kB
Shared_Clean: 0 kB
Shared_Dirty: 0 kB
Private_Clean: 1557632 kB
Private_Dirty: 0 kB
Referenced: 1557632 kB
Anonymous: 0 kB
AnonHugePages: 0 kB
Swap: 0 kB
KernelPageSize: 4 kB
MMUPageSize: 4 kB
Locked: 0 kB
VmFlags: rd wr sh mr mw me ms sd
Size: 33554432 kB
Rss: 1557632 kB
Pss: 1557632 kB
Shared_Clean: 0 kB
Shared_Dirty: 0 kB
Private_Clean: 1557632 kB
Private_Dirty: 0 kB
Referenced: 1557632 kB
Anonymous: 0 kB
AnonHugePages: 0 kB
Swap: 0 kB
KernelPageSize: 4 kB
MMUPageSize: 4 kB
Locked: 0 kB
VmFlags: rd wr sh mr mw me ms sd
译注：这个文件大小 32GB，已加载了 1521MB 到内存中，因为只有这一个进程映射了它，所以在这个进程的PSS中占比是100%，也是 1521MB。
在共享映射里的私有页面 —— 搞得我像巫师一样？在Linux上，即使共享内存也会被认为是私有的，除非它真的被共享了（译注：不止一个进程创建共享映射）。让我们看看它是否在系统缓冲区里：
# 好像开头的那一块在内存中...
$ vmtouch -m 64G -v mordor.map
[OOo ] 389440/8388608
Files: 1
Directories: 0
Resident Pages: 389440/8388608 1G/32G 4.64%
Elapsed: 0.27624 seconds
# 将它全都载入到Cache!
$ cat mordor.map > /dev/null
$ vmtouch -m 64G -v mordor.map
[ooooooooo oooOOOOO] 2919606/8388608
Files: 1
Directories: 0
Resident Pages: 2919606/8388608 11G/32G 34.8%
Elapsed: 0.59845 seconds
$ vmtouch -m 64G -v mordor.map
[OOo ] 389440/8388608
Files: 1
Directories: 0
Resident Pages: 389440/8388608 1G/32G 4.64%
Elapsed: 0.27624 seconds
# 将它全都载入到Cache!
$ cat mordor.map > /dev/null
$ vmtouch -m 64G -v mordor.map
[ooooooooo oooOOOOO] 2919606/8388608
Files: 1
Directories: 0
Resident Pages: 2919606/8388608 11G/32G 34.8%
Elapsed: 0.59845 seconds
译注：
1. “-m 64G” 表示允许 vmtouch 将小于 64G 的文件加载到内存中，应当是用于需要加载一个目录下的文件、但排除其中过大的文件，似乎不适用于这里；至少忽略这个参数不影响阅读
2. o 表示这一块部分被加载，O 表示全部被加载。因为物理内存有限，虽然全量读取了文件，但只有部分内容被缓存
嗬，只是简单地读取一个文件就会把它缓存起来？先不管这，我们的进程呢？
$ ps -p $$ -o pid,rss
PID RSS
17906 286584 # <-- 等了足足一分钟
PID RSS
17906 286584 # <-- 等了足足一分钟
常见的误解是，映射文件会消耗内存，而通过文件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
May
16
续上篇：
* [译] Ｃ程序员该知道的内存知识 (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)
这是本系列的第3篇，预计还会有1篇，感兴趣的同学记得关注，以便接收推送，等不及的推荐阅读原文。
---
照例放图镇楼：
来源：Linux地址空间布局 - by Gustavo Duarte
关于图片的解释参见第一篇。
开始吧。
## 有趣的内存映射
工具箱：
* sysconf() - 在运行时获取配置信息
* mmap() - 映射虚拟内存
* mincore() - 判断页是否在内存中
* shmat() - 共享内存操作
有些事情是内存分配器没法完成的，需要内存映射来救场。比如说，你无法选择分配的地址范围。为了这个，我们得牺牲一些舒适性 —— 接下来将和整页内存打交道了。注意，虽然一页通常是 4KB，但你不应该依赖这个“通常”，而是应该用 sysconf() 来获取的实际大小：
long page_size = sysconf(_SC_PAGESIZE); /* Slice and dice. */
备注 —— 即使系统宣称使用统一的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 位置的地址（用户空间最高的可用地址；译注：见镇楼图右上方）大致是安全的。你可以不用固定映射，但是就别想用指向共享内存的指针了（译注：不固定起始地址的话，共享内存中同一个对象在两个不同进程的地址就不一样了，这样的指针无法在两个进程中通用）。
#define TASK_SIZE 0x800000000000
#define SHARED_BLOCK (void *)(2 * TASK_SIZE / 3)
void *shared_cats = shmat(shm_key, SHARED_BLOCK, 0);
if(shared_cats == (void *)-1) {
perror("shmat"); /* Sad :( */
}
[code]
译注：shmat是“shared memory attach”的缩写，表示将 shm_key 指定的共享内存映射到 SHARED_BLOCK 开始的虚拟地址上。shm_key 是由 `shmget(key, size, flag)` 创建的一块共享内存的标识。详细用法请google。
OKay，我知道，这是个几乎无法移植的例子，但是大意你应该能理解了。固定地址映射通常被认为至少是不安全的，因为它不检查那里是否已经映射了其他东西。有一个 mincore() 函数可以告诉你一个页面是否被映射了，但是在多线程环境里你可能不那么走运（译注：可能你刚检查的时候没被映射，但在你映射之前被另一个线程映射了；作者这里使用 mincore 可能不太恰当，因为它只检查页面是否在物理内存中，而一个页面可能被映射了、但是被换出到swap）。
然而，固定地址映射不仅在未使用的地址范围上有用，而且对**已用的**地址范围也有用。还记得内存分配器如何使用 mmap() 来分配大块内存吗？由于按需调页机制，我们可以实现高效的稀疏数组。假设你创建了一个稀疏数组，然后现在你打算释放掉其中一些数据占用的空间，该怎么做呢？你不能 free() 它（译注：因为不是malloc分配的），而 mmap () 会让这段地址空间不可用（译注：因为这段地址空间属于稀疏数组，仍可能被访问到，不能被unmap）。你可以调用 `madvise()` ，用 MADV_FREE / MADV_DONTNEED 将这些页面标记为空闲（译注：页面可被回收，但地址空间仍然可用），从性能上来讲这是最佳解决方案，因为这些页面可能不再会因触发 page fault 被载入，不过这些“建议”的语义可能根据具体的实现而变化（译注：换句话说就是虽然性能好，但可移植性不好，例如在Linux不同版本以及其他Unix-like系统这些建议的语义会有差别；关于这些建议的说明详见上一篇）。
一种可移植的做法是在这货上面覆盖映射：
[code]
void *array = mmap(NULL, length, PROT_READ|PROT_WRITE,
MAP_ANONYMOUS, -1, 0);
/* ... 某些魔法玩脱了 ... */
/* Let's clear some pages. */
mmap(array + offset, length, MAP_FIXED|MAP_ANONYMOUS, -1, 0);
#define SHARED_BLOCK (void *)(2 * TASK_SIZE / 3)
void *shared_cats = shmat(shm_key, SHARED_BLOCK, 0);
if(shared_cats == (void *)-1) {
perror("shmat"); /* Sad :( */
}
[code]
译注：shmat是“shared memory attach”的缩写，表示将 shm_key 指定的共享内存映射到 SHARED_BLOCK 开始的虚拟地址上。shm_key 是由 `shmget(key, size, flag)` 创建的一块共享内存的标识。详细用法请google。
OKay，我知道，这是个几乎无法移植的例子，但是大意你应该能理解了。固定地址映射通常被认为至少是不安全的，因为它不检查那里是否已经映射了其他东西。有一个 mincore() 函数可以告诉你一个页面是否被映射了，但是在多线程环境里你可能不那么走运（译注：可能你刚检查的时候没被映射，但在你映射之前被另一个线程映射了；作者这里使用 mincore 可能不太恰当，因为它只检查页面是否在物理内存中，而一个页面可能被映射了、但是被换出到swap）。
然而，固定地址映射不仅在未使用的地址范围上有用，而且对**已用的**地址范围也有用。还记得内存分配器如何使用 mmap() 来分配大块内存吗？由于按需调页机制，我们可以实现高效的稀疏数组。假设你创建了一个稀疏数组，然后现在你打算释放掉其中一些数据占用的空间，该怎么做呢？你不能 free() 它（译注：因为不是malloc分配的），而 mmap () 会让这段地址空间不可用（译注：因为这段地址空间属于稀疏数组，仍可能被访问到，不能被unmap）。你可以调用 `madvise()` ，用 MADV_FREE / MADV_DONTNEED 将这些页面标记为空闲（译注：页面可被回收，但地址空间仍然可用），从性能上来讲这是最佳解决方案，因为这些页面可能不再会因触发 page fault 被载入，不过这些“建议”的语义可能根据具体的实现而变化（译注：换句话说就是虽然性能好，但可移植性不好，例如在Linux不同版本以及其他Unix-like系统这些建议的语义会有差别；关于这些建议的说明详见上一篇）。
一种可移植的做法是在这货上面覆盖映射：
[code]
void *array = mmap(NULL, length, PROT_READ|PROT_WRITE,
MAP_ANONYMOUS, -1, 0);
/* ... 某些魔法玩脱了 ... */
/* Let's clear some pages. */
mmap(array + offset, length, MAP_FIXED|MAP_ANONYMOUS, -1, 0);
译注：如前文所述，开头用 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）。但不是谁都需要它，尤其是不需要持久化的场景下，完全不需要同步，你也不用担心丢失 写入数据的可见性（译注：这里应该是指修改后立即可读取）。这多亏了页面缓存，得益于此你也可以用内存映射来实现高效的进程间通信。
/* Map the contents of a file into memory (shared). */
int fd = open(...);
void *db = mmap(NULL, file_size, PROT_READ|PROT_WRITE,
MAP_SHARED, fd, 0);
if (db == (void *)-1) {
/* Mapping failed */
}
/* Write to a page */
char *page = (char *)db;
strcpy(page, "bob");
/* This is going to be a durable page. */
msync(page, 4, MS_SYNC);
/* This is going to be a less durable page. */
page = page + PAGE_SIZE;
strcpy(page, "fred");
msync(page, 5, MS_ASYNC);
int fd = open(...);
void *db = mmap(NULL, file_size, PROT_READ|PROT_WRITE,
MAP_SHARED, fd, 0);
if (db == (void *)-1) {
/* Mapping failed */
}
/* Write to a page */
char *page = (char *)db;
strcpy(page, "bob");
/* This is going to be a durable page. */
msync(page, 4, MS_SYNC);
/* This is going to be a less durable page. */
page = page + PAGE_SIZE;
strcpy(page, "fred");
msync(page, 5, MS_ASYNC);
译注：MS_SYNC会等待写入底层存储后才返回；MS_ASYNC会立即返回，OS会异步写回存储，但期间如果系统异常崩溃就会导致数据丢失。
注意，你不能映射比文件内容更长的内存，所以你无法通过这种方式增加或者减少文件的长度。不过你可以提前用 ftruncate() 来创建（或加长）一个稀疏文件（译注：稀疏文件是指，你可以创建一个很大的文件，但文件里只有少量数据；很多文件系统如ext\*、NTFS系列都支持只存储有数据的部分）。但稀疏文件的坏处是，会让紧凑的存储更困难，因为它同时要求文件系统和OS都支持才行。
在Linux下，`fallocate(FALLOC_FL_PUNCH_HOLE)` 是最佳选项，但最适合移植（也最简单的）方法是创建一个空文件：
/* Resize the file. */
int fd = open(...);
ftruncate(fd, expected_length);
int fd = open(...);
ftruncate(fd, expected_length);
一个文件被内存映射，并不意味着不能再以文件来用它。这对于需要区分不同访问情况的场景很有用，比如说你可以一边把这个文件用只读模式映射到内存中，一边用标准的文件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新进程的时候只需要拷贝页表）或者加载共享库的场景，也有助于处理来自多个进程的大数据集的场景。
int fd = open(...);
/* Copy-on-write mapping */
void *db = mmap(NULL, file_size, PROT_READ|PROT_WRITE,
MAP_PRIVATE, fd, 0);
if (db == (void *)-1) {
/* Mapping failed */
}
/* This page will be copied as soon as we write to it */
char *page = (char *)db;
strcpy(page, "bob");
/* Copy-on-write mapping */
void *db = mmap(NULL, file_size, PROT_READ|PROT_WRITE,
MAP_PRIVATE, fd, 0);
if (db == (void *)-1) {
/* Mapping failed */
}
/* This page will be copied as soon as we write to it */
char *page = (char *)db;
strcpy(page, "bob");
译注：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的老哥！*
int sock = get_client();
struct iovec iov = { .iov_base = cat_db, .iov_len = PAGE_SIZE };
int ret = vmsplice(sock, &iov, 1, 0);
if (ret != 0) {
/* No streaming :( */
}
struct iovec iov = { .iov_base = cat_db, .iov_len = PAGE_SIZE };
int ret = vmsplice(sock, &iov, 1, 0);
if (ret != 0) {
/* No streaming :( */
}
译注：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
May
15
续上篇：
* [译] Ｃ程序员该知道的内存知识 (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/
* [译] Ｃ程序员该知道的内存知识 (1)
这是本系列的第二篇，预计还会有2篇，感兴趣的同学记得关注，以便接收推送，等不及的推荐阅读原文。
先放图镇楼：
来源：Linux地址空间布局 - by Gustavo Duarte
关于图片的解释可参见上篇。
开始吧。
# 理解堆上的内存分配
工具箱：
* brk(), sbrk() - 修改数据段的大小
* malloc() 家族 - 可移植的 libc 内存分配器
堆上的内存分配，最简单的实现可以是修改 program break[2]（译注：参见上图中部右侧）的上界，申请对原位置和新位置之间内存的访问权限。如果就这么搞的话，堆上内存分配和栈上分配一样快（除了换页的开销，一般我们认为栈是被锁定在内存中；译注：指栈不会被换出到磁盘，可以用mlock限制OS对一段地址空间使用swap）。但这里还是有只猫（
char *block = sbrk(1024 * sizeof(char));
* 我们无法回收不再使用的内存块
* 它也不是线程安全的，因为堆是在线程间共享的
* 这个接口（译注：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 的下界和上界，建议对照图中右侧的标注）之间总是连续的（译注：这里指的是虚拟地址空间连续，但其中每一页都可能映射到任一物理页），因此你无法在中间打个洞来减少数据段的尺寸。比如这个场景：
char *truck = malloc(1024 * 1024 * sizeof(char));
char *bike = malloc(sizeof(char));
free(truck);
char *bike = malloc(sizeof(char));
free(truck);
堆分配器将会调大 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 不感兴趣 —— 就是你找分配器要一块内存，例如说一整页，然后切成很多固定大小的小块。如果每个小块都能保存至少一个指针或一个整数，你就可以把他们串成一个链表 ，表头指向第一个空闲元素。
/* Super-simple slab. */
struct slab {
void **head;
};
/* Create page-aligned slab */
struct slab *slab = NULL;
posix_memalign(&slab, page_size, page_size);
slab->head = (void **)((char*)slab + sizeof(struct slab));
/* Create a NULL-terminated slab freelist */
char* item = (char*)slab->head;
for(unsigned i = 0; i < item_count; ++i) {
*((void**)item) = item + item_size;
item += item_size;
}
*((void**)item) = NULL;
struct slab {
void **head;
};
/* Create page-aligned slab */
struct slab *slab = NULL;
posix_memalign(&slab, page_size, page_size);
slab->head = (void **)((char*)slab + sizeof(struct slab));
/* Create a NULL-terminated slab freelist */
char* item = (char*)slab->head;
for(unsigned i = 0; i < item_count; ++i) {
*((void**)item) = item + item_size;
item += item_size;
}
*((void**)item) = NULL;
译注：
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 的指针。
/* Free an element */
struct slab *slab = (void *)((size_t)ptr & PAGESIZE_BITS);
*((void**)ptr) = (void*)slab->head;
slab->head = (void**)ptr;
/* Allocate an element */
if((item = slab->head)) {
slab->head = (void**)*item;
} else {
/* No elements left. */
}
struct slab *slab = (void *)((size_t)ptr & PAGESIZE_BITS);
*((void**)ptr) = (void*)slab->head;
slab->head = (void**)ptr;
/* Allocate an element */
if((item = slab->head)) {
slab->head = (void**)*item;
} else {
/* No elements left. */
}
译注：对于 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] 写得不咋地，不过抛开这些小缺陷，它允许你完成基于内存池的分配和回收（包括部分回收和全量回收）。
/* Define block allocator. */
#define obstack_chunk_alloc malloc
#define obstack_chunk_free free
/* Initialize obstack and allocate a bunch of animals. */
struct obstack animal_stack;
obstack_init (&animal_stack);
char *bob = obstack_alloc(&animal_stack, sizeof(animal));
char *fred = obstack_alloc(&animal_stack, sizeof(animal));
char *roger = obstack_alloc(&animal_stack, sizeof(animal));
/* Free everything after fred (i.e. fred and roger). */
obstack_free(&animal_stack, fred);
/* Free everything. */
obstack_free(&animal_stack, NULL);
#define obstack_chunk_alloc malloc
#define obstack_chunk_free free
/* Initialize obstack and allocate a bunch of animals. */
struct obstack animal_stack;
obstack_init (&animal_stack);
char *bob = obstack_alloc(&animal_stack, sizeof(animal));
char *fred = obstack_alloc(&animal_stack, sizeof(animal));
char *roger = obstack_alloc(&animal_stack, sizeof(animal));
/* Free everything after fred (i.e. fred and roger). */
obstack_free(&animal_stack, fred);
/* Free everything. */
obstack_free(&animal_stack, NULL);
译注：obstack这些api实际都是宏；需要通过宏来指定找OS分配和回收整块内存用的方法，如上第2、3行所示。由于对象使用栈的方式管理（先分配的最后释放），所以释放 fred 的时候，会把 fred 和在 fred 之后分配的对象（roger）一起释放掉。
还有个小技巧：你可以扩展栈顶的那个对象。例如带缓冲的输入，变长数组，或者用来替代 realloc()-strcpy() 模式（译注：重新分配内存，然后把原数据拷贝过去）：
/* This is wrong, I better cancel it. */
obstack_grow(&animal_stack, "long", 4);
obstack_grow(&animal_stack, "fred", 5);
obstack_free (&animal_stack, obstack_finish(&animal_stack));
/* This time for real. */
obstack_grow(&animal_stack, "long", 4);
obstack_grow(&animal_stack, "bob", 4);
char *result = obstack_finish(&animal_stack);
printf("%s\n", result); /* "longbob" */
obstack_grow(&animal_stack, "long", 4);
obstack_grow(&animal_stack, "fred", 5);
obstack_free (&animal_stack, obstack_finish(&animal_stack));
/* This time for real. */
obstack_grow(&animal_stack, "long", 4);
obstack_grow(&animal_stack, "bob", 4);
char *result = obstack_finish(&animal_stack);
printf("%s\n", result); /* "longbob" */
译注：前三行是作者逗逼了，看后四行就行；用 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：
char *block = malloc(1024 * sizeof(char));
mlock(block, 1024 * sizeof(char));
mlock(block, 1024 * sizeof(char));
（译注：访问被换出到swap的页面会触发page fault，然后内存管理器会从磁盘中载入页面，这会导致较严重的性能问题；用 mlock 将这段区域锁定后，OS就不会被操作系统换出到swap；例如，在允许的情况下，MySQL会用mlock将索引保持在物理内存中）
注意：你还可以根据自己的内存使用模式，给内核提出建议
char *block = malloc(1024 * sizeof(block));
madvise(block, 1024 * sizeof(block), MADV_SEQUENTIAL);
madvise(block, 1024 * sizeof(block), MADV_SEQUENTIAL);
对建议的解释是平台相关的，系统甚至可能选择忽略它，但大部分平台都处理得很好。但不是所有建议都有良好的支持，有些平台可能会改变建议的语义（如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/
May
2
上篇 《踩坑记：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
尽管如此，我仍然觉得讲得不够透，思来想去觉得还是文中提到的《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\]（译注：指允许申请超过可用空间的内存），有一些正当的应用有这种需求（例如稀疏数组），这也意味着内存分配不会简单被拒绝。
char *block = malloc(1024 * sizeof(char));
if (block == NULL) {
return -ENOMEM; /* sad :( */
}
if (block == NULL) {
return -ENOMEM; /* sad :( */
}
检查 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() - 设置或获取信号栈上下文
栈相对比较容易理解，毕竟每个人都知道如何在栈上放一个变量，对吧 ？比如：
int stairway = 2;
int heaven[] = { 6, 5, 4 };
int heaven[] = { 6, 5, 4 };
变量的有效性受到作用域的限制。在 C 里，作用域指的就是一对大括号 `{}`。因此每次遇到一个右大括号，对应的变量作用域就结束了。
然后是 alloca()，在当前 *栈帧*上动态分配内存。栈帧和内存帧（也叫做物理页）不太一样，它只是一组被压到栈上的数据（函数，参数，变量等）。由于我们在栈顶（译注：SP寄存器总是指向栈顶），我们可以使用剩下的栈空间，只要不超过栈大小限制。
这就是变长数组（variable-length，VLA）和 alloca 的原理，区别在于 ，VLA受限于作用域，alloca分配的内存的有效性可以持续到当前函数返回。这里没有语言律师业务（译注：没人管你，爱咋咋地），但如果你在循环里用alloca可能会踩坑，因为你没办法释放它分配的空间：
void laugh(void) {
for (unsigned i = 0; i < megatron; ++i) {
char *res = alloca(2);
memcpy(res, "ha", 2);
char vla[2] = {'h','a'}
} /* vla dies, res lives */
} /* all allocas die */
for (unsigned i = 0; i < megatron; ++i) {
char *res = alloca(2);
memcpy(res, "ha", 2);
char vla[2] = {'h','a'}
} /* vla dies, res lives */
} /* all allocas die */
如果要申请大量内存，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
Apr
27
这周换换口味，记录一下去年踩的一个大坑。
起
大概是去年8月份，那会儿我们还在用着64GB的“小内存”机器。
由于升级一次版本需要较长的时间（1~2小时），因此我们每天只发一次车，由值班的同学负责，发布所有已merge的commit。
当天负责值班的我正开着车，突然收到 Bytedance-System 的夺命连环call，打开Lark一看：
[规则]：机器资源报警
[报警上下文]：
host: 10.x.x.x
内存使用率: 0.944
[报警方式]：电话&Lark
打开ganglia一看，更令人害怕：
起
大概是去年8月份，那会儿我们还在用着64GB的“小内存”机器。
由于升级一次版本需要较长的时间（1~2小时），因此我们每天只发一次车，由值班的同学负责，发布所有已merge的commit。
当天负责值班的我正开着车，突然收到 Bytedance-System 的夺命连环call，打开Lark一看：
引用
[规则]：机器资源报警
[报警上下文]：
host: 10.x.x.x
内存使用率: 0.944
[报警方式]：电话&Lark
打开ganglia一看，更令人害怕：
Apr
20
TCP#2: 西厢记和西厢计划
上篇《TCP：学得越多越不懂》发出来以后，有朋友很委婉地说：“如果能结合现实生产场景会有意义一点。”
经过深刻的反思，我决定虚心接受建议，写一点理论结合实践的内容。
# == 回忆杀 ==
曾经在猫扑和天涯冲浪的网虫应该都还记得，谷歌当时还是Goooooogle，是可以直接访问的。
但是如果想搜索一些奇怪的词汇（比如███），一点击"手气不错"，浏览器马上就会显示无法访问，并且这个现象会持续几分钟。
于是很多小伙伴就换到一个号称自己更懂中文的搜索引擎了。
（该爬虫当年有个广告拍得不错：https://v.qq.com/x/page/r0137s2op5j.html ）
作为一个曾被新自由主义（Neoliberalism）洗脑的年轻人，我在寻找“自由”的路上发现了墙的存在，也知道了这是方校长的杰作。
但是墙到底是个什么样的存在呢？
# == 防火墙 ==
我们的防火墙，其名源自《The Great Firewall of China: How to Build and Control an Alternative Version of the Internet》这本书。
虽然名字叫防火墙（Firewall，简称FW），但严格来说，（在早期）它其实是一个入侵检测系统（Instrusion Detection System，简称IDS）。
和FW不同的是，IDS是监听设备，不需要部署在链路中间，只要能把流量旁路引出供它分析即可。
通过旁路分析，IDS可以在不影响现有流量的情况下部署（只要路由器/交换机上有镜像端口即可），在IDS出现异常时（例如在流量高峰IDS设备性能不足时 ）也不会导致网络中断。
曾经有人发现，在流量特别大的时候，墙的检测功能有时会失效，因此推测其是旁路引流进行分析的（符合IDS的特征）。
既然是旁路的，就无法直接Drop数据包，为了达到阻断通信的目的，需要利用协议的特性来实现。
# == RST大法 ==
看了上篇《TCP：学得越多越不懂》的同学，对报文的控制位里的 RST 可能还有点印象，在遇到异常情况时，可用于通知对方重置连接（细节详见RFC 793）：
有些同学可能像我一样懒得读英文原文，所以翻译一下：
* 如果连接状态处于“非连接完成”状态（例如SYN-SEND, SYN-RECEIVED），当收到reset时会将状态返回LISTEN；
* 如果TCP状态是 ESTABLISHED, FIN-WAIT-1, ..., LAST-ACK, TIME-WAIT 其中之一时，放弃连接并通知用户。
忘了上述状态含义的话，可以再回顾下这张状态流转图：
(tcp连接状态图，截取自rfc 793)
这就是上篇里提到的“我们敬爱的防火墙很爱用它”的原因了：
当检测到“入侵行为”时（例如HTTP报文中出现了███）发送RST，按照RFC 793规范的TCP协议栈实现，收到RST后就应当放弃本次连接。
于是你就在浏览器上看到连接被重置(reset)了。
# == 反RST大法 ==
那么，如果我忽略RST包，不就可以不被墙欺骗吗？
实际上，用 iptables 来实现这一点很简单：
很不幸，方校长的团队对此的解决方法也非常简单，只要向双方都发送RST包就可以了。
当然如果在服务器一端也忽略RST，就可以成功绕过墙的忽悠——据说剑桥大学有人实验验证过，确实可行。
可惜的是，用户通常没法控制服务器端忽略RST，因此这个方法的实用价值不高。
但是这个思路为西厢计划做好了铺垫。
# == 西厢计划 ==
我看到这个项目的名字的时候 ，真佩服作者的脑洞。
了解这个计划的原理之后，就更佩服作者的脑洞了。
前面说到，墙是在检测到某个关键词的时候才会发送RST包。
为了检测关键词，它需要工作在应用层（HTTP协议）。
而为了工作在应用层，它需要维护TCP连接的状态。
由于那时的设备性能比较弱（所以会出现高峰期检测失效的情况），为了提高吞吐量，方校长团队的方案是：实现一个简化的TCP栈。
RFC 793规范中定义了很多有效性检测，例如检测序列号是否有效来过滤old duplicates等，以保证通信的可靠性。
但这不是墙的需求，因此可以去掉很多规则，从而提高分析性能。
那么，如果我可以欺骗墙，这个连接已经被关闭，那么后续该连接的包就会被墙认为是网络中滞留的无效包，绕过关键词检测。
具体该怎么办呢？
# == 第一阶段 ==
上篇提到了一个细节：
我们知道，在三次握手的最后一步，A本应发送一个ACK(seq=y+1)。
但如果这时候 A 发送了一个 FIN 呢？
B收到以后，由于此时连接尚未建立，会直接忽略这个包。
而墙实现的TCP栈比较简陋，它认为A已经关闭了链接，因此A后续发送的包就不会再触发关键词检测。
但是注意，TCP是双向的，虽然A主动关闭连接，但是B仍然可能有数据要发送（划重点：面试题“为什么TCP断开连接需要4次”的答案），因此还需要欺骗墙说在B这侧也终止链接了。
这又该怎么办呢？
# == 第二阶段 ==
显然我们不能让服务器直接发一个FIN，否则这个连接就真完了。
幸运的是，RFC 793给了一个“梯子”：
翻译：如果连接处于“非连接完成”状态，收到一个无效的ACK，应当发出一个reset。
如果A在三次握手的最后一步，没有按规范要求发送ACK(seq=y+1)，而是发送ACK(seq=y)，那么B在收到以后就会按照协议的要求回复一个RST：
这时我们可以在 A 上用“反RST大法”，忽略服务端返回的RST，这个连接就不受影响。
但是墙的TCP栈认为客户端会按照协议终止连接，于是就不再有必要检测服务端后续的报文了。
# == 大结局 ==
从此张生和崔莺莺过上了幸福的生活。
方校长的团队当然不会放任这种事情的发生，西厢计划没过多久就失效了。
随着技术的进步、性能的提升，现在墙似乎已经集成到了链路中、可以直接DROP数据包，不再需要RST大法了。
不过为了业务需要，企业可以向电信主管部门申请VPN用于正常的生产经营。
例如字节跳动，为了建设21世纪数字丝绸之路，通过技术出海，在40多个国家和地区排在应用商店总榜前列，包括韩国、印尼、马来西亚、俄罗斯、土耳其等“一带一路”沿线的主要国家。
如果你也想过上幸福的生活，不妨投个简历，一起为一带一路做贡献吧。
关于字节跳动面试的详情，可参考我之前写的《程序员面试指北：面试官视角》
https://mp.weixin.qq.com/s/Byvu-w7kyby-L7FBCE24Uw
# ~ 投递链接 ~
网盟广告（穿山甲）-后端开发(上海)
https://job.toutiao.com/s/sBAvKe
网盟广告（穿山甲）-后端开发(北京)
https://job.toutiao.com/s/sBMyxk
网盟广告（穿山甲）-广告策略研发(上海)
https://job.toutiao.com/s/sBDMAK
其他地区、其他职能线
https://job.toutiao.com/s/sB9Jqk
# 参考文章
[1] “西厢计划”原理小解
https://blog.youxu.info/2010/03/14/west-chamber/
[2] 从Linux协议栈代码和RFC看西厢计划原理
https://blog.csdn.net/dog250/article/details/7246895
[3] RFC 793 - TRANSMISSION CONTROL PROTOCOL
https://tools.ietf.org/html/rfc793
引用
自那日听琴之后，多日不见莺莺，张生害了相思病，趁红娘探病之机会，托她捎信给莺莺，莺莺回信约张生月下相会。夜晚，小姐莺莺在后花园弹琴，张生听到琴声，攀上墙头一看，是莺莺在弹琴。急欲与小姐相见，便翻墙而入，莺莺见他翻墙而入，反怪他行为下流，发誓不再见他，致使张生病情愈发严重。
《西厢记》
《西厢记》
上篇《TCP：学得越多越不懂》发出来以后，有朋友很委婉地说：“如果能结合现实生产场景会有意义一点。”
经过深刻的反思，我决定虚心接受建议，写一点理论结合实践的内容。
# == 回忆杀 ==
曾经在猫扑和天涯冲浪的网虫应该都还记得，谷歌当时还是Goooooogle，是可以直接访问的。
但是如果想搜索一些奇怪的词汇（比如███），一点击"手气不错"，浏览器马上就会显示无法访问，并且这个现象会持续几分钟。
于是很多小伙伴就换到一个号称自己更懂中文的搜索引擎了。
（该爬虫当年有个广告拍得不错：https://v.qq.com/x/page/r0137s2op5j.html ）
作为一个曾被新自由主义（Neoliberalism）洗脑的年轻人，我在寻找“自由”的路上发现了墙的存在，也知道了这是方校长的杰作。
但是墙到底是个什么样的存在呢？
# == 防火墙 ==
我们的防火墙，其名源自《The Great Firewall of China: How to Build and Control an Alternative Version of the Internet》这本书。
虽然名字叫防火墙（Firewall，简称FW），但严格来说，（在早期）它其实是一个入侵检测系统（Instrusion Detection System，简称IDS）。
和FW不同的是，IDS是监听设备，不需要部署在链路中间，只要能把流量旁路引出供它分析即可。
通过旁路分析，IDS可以在不影响现有流量的情况下部署（只要路由器/交换机上有镜像端口即可），在IDS出现异常时（例如在流量高峰IDS设备性能不足时 ）也不会导致网络中断。
曾经有人发现，在流量特别大的时候，墙的检测功能有时会失效，因此推测其是旁路引流进行分析的（符合IDS的特征）。
既然是旁路的，就无法直接Drop数据包，为了达到阻断通信的目的，需要利用协议的特性来实现。
# == RST大法 ==
看了上篇《TCP：学得越多越不懂》的同学，对报文的控制位里的 RST 可能还有点印象，在遇到异常情况时，可用于通知对方重置连接（细节详见RFC 793）：
引用
If the receiving TCP is in a non-synchronized state (i.e. SYN-SENT, SYN-RECEIVED), it returns to LISTEN on receiving an acceptable reset. If the TCP is in one of the synchronized states (ESTABLISHED, FIN-WAIT1, FIN-WAIT2, CLOSE-WAIT, CLOSING, LAST-ACK, TIME-WAIT), it aborts the connection and informs its user
https://tools.ietf.org/html/rfc793
https://tools.ietf.org/html/rfc793
有些同学可能像我一样懒得读英文原文，所以翻译一下：
* 如果连接状态处于“非连接完成”状态（例如SYN-SEND, SYN-RECEIVED），当收到reset时会将状态返回LISTEN；
* 如果TCP状态是 ESTABLISHED, FIN-WAIT-1, ..., LAST-ACK, TIME-WAIT 其中之一时，放弃连接并通知用户。
忘了上述状态含义的话，可以再回顾下这张状态流转图：
(tcp连接状态图，截取自rfc 793)
这就是上篇里提到的“我们敬爱的防火墙很爱用它”的原因了：
当检测到“入侵行为”时（例如HTTP报文中出现了███）发送RST，按照RFC 793规范的TCP协议栈实现，收到RST后就应当放弃本次连接。
于是你就在浏览器上看到连接被重置(reset)了。
# == 反RST大法 ==
那么，如果我忽略RST包，不就可以不被墙欺骗吗？
实际上，用 iptables 来实现这一点很简单：
$ iptables -A INPUT -p tcp --tcp-flags RST RST -j DROP
很不幸，方校长的团队对此的解决方法也非常简单，只要向双方都发送RST包就可以了。
当然如果在服务器一端也忽略RST，就可以成功绕过墙的忽悠——据说剑桥大学有人实验验证过，确实可行。
可惜的是，用户通常没法控制服务器端忽略RST，因此这个方法的实用价值不高。
但是这个思路为西厢计划做好了铺垫。
# == 西厢计划 ==
我看到这个项目的名字的时候 ，真佩服作者的脑洞。
了解这个计划的原理之后，就更佩服作者的脑洞了。
前面说到，墙是在检测到某个关键词的时候才会发送RST包。
为了检测关键词，它需要工作在应用层（HTTP协议）。
而为了工作在应用层，它需要维护TCP连接的状态。
由于那时的设备性能比较弱（所以会出现高峰期检测失效的情况），为了提高吞吐量，方校长团队的方案是：实现一个简化的TCP栈。
RFC 793规范中定义了很多有效性检测，例如检测序列号是否有效来过滤old duplicates等，以保证通信的可靠性。
但这不是墙的需求，因此可以去掉很多规则，从而提高分析性能。
那么，如果我可以欺骗墙，这个连接已经被关闭，那么后续该连接的包就会被墙认为是网络中滞留的无效包，绕过关键词检测。
具体该怎么办呢？
# == 第一阶段 ==
上篇提到了一个细节：
引用
虽然ISN=4000，但是发送方发送的第一个包，SEQ是4001开始的，TCP协议规定 SYN 需要占一个序号（虽然SYN并不是实际传输的数据），所以前面示意图中ACK的seq是 x+1 。同样，FIN也会占用一个序号，这样可以保证FIN报文的重传和确认不会有歧义。
TCP：学得越多越不懂
https://mp.weixin.qq.com/s/xyPUEFUr_v9sSKKqlBkI7w
TCP：学得越多越不懂
https://mp.weixin.qq.com/s/xyPUEFUr_v9sSKKqlBkI7w
我们知道，在三次握手的最后一步，A本应发送一个ACK(seq=y+1)。
但如果这时候 A 发送了一个 FIN 呢？
B收到以后，由于此时连接尚未建立，会直接忽略这个包。
而墙实现的TCP栈比较简陋，它认为A已经关闭了链接，因此A后续发送的包就不会再触发关键词检测。
但是注意，TCP是双向的，虽然A主动关闭连接，但是B仍然可能有数据要发送（划重点：面试题“为什么TCP断开连接需要4次”的答案），因此还需要欺骗墙说在B这侧也终止链接了。
这又该怎么办呢？
# == 第二阶段 ==
显然我们不能让服务器直接发一个FIN，否则这个连接就真完了。
幸运的是，RFC 793给了一个“梯子”：
引用
If the connection is in any non-synchronized state (LISTEN, SYN-SENT, SYN-RECEIVED), and the incoming segment acknowledges something not yet sent (the segment carries an unacceptable ACK), or ...(省略)..., a reset is sent.
Reset Generation, RFC 793 [Page 35]
Reset Generation, RFC 793 [Page 35]
翻译：如果连接处于“非连接完成”状态，收到一个无效的ACK，应当发出一个reset。
如果A在三次握手的最后一步，没有按规范要求发送ACK(seq=y+1)，而是发送ACK(seq=y)，那么B在收到以后就会按照协议的要求回复一个RST：
这时我们可以在 A 上用“反RST大法”，忽略服务端返回的RST，这个连接就不受影响。
但是墙的TCP栈认为客户端会按照协议终止连接，于是就不再有必要检测服务端后续的报文了。
# == 大结局 ==
方校长的团队当然不会放任这种事情的发生，西厢计划没过多久就失效了。
随着技术的进步、性能的提升，现在墙似乎已经集成到了链路中、可以直接DROP数据包，不再需要RST大法了。
不过为了业务需要，企业可以向电信主管部门申请VPN用于正常的生产经营。
例如字节跳动，为了建设21世纪数字丝绸之路，通过技术出海，在40多个国家和地区排在应用商店总榜前列，包括韩国、印尼、马来西亚、俄罗斯、土耳其等“一带一路”沿线的主要国家。
如果你也想过上幸福的生活，不妨投个简历，一起为一带一路做贡献吧。
关于字节跳动面试的详情，可参考我之前写的《程序员面试指北：面试官视角》
https://mp.weixin.qq.com/s/Byvu-w7kyby-L7FBCE24Uw
# ~ 投递链接 ~
网盟广告（穿山甲）-后端开发(上海)
https://job.toutiao.com/s/sBAvKe
网盟广告（穿山甲）-后端开发(北京)
https://job.toutiao.com/s/sBMyxk
网盟广告（穿山甲）-广告策略研发(上海)
https://job.toutiao.com/s/sBDMAK
其他地区、其他职能线
https://job.toutiao.com/s/sB9Jqk
# 参考文章
[1] “西厢计划”原理小解
https://blog.youxu.info/2010/03/14/west-chamber/
[2] 从Linux协议栈代码和RFC看西厢计划原理
https://blog.csdn.net/dog250/article/details/7246895
[3] RFC 793 - TRANSMISSION CONTROL PROTOCOL
https://tools.ietf.org/html/rfc793
Apr
6
周末小课堂又开张了，这次我们来聊一聊TCP协议。
== 握手 ==
多少有点令人意外的是，大多数程序员对TCP协议的印象仅限于在创建连接时的三次握手。
严格地说，“三次握手”其实是一个不太准确的翻译，英文原文是 "3-way handshake"，意思是握手有三个步骤。
不过既然教科书都这么翻译，我就只能先忍了。
“三次握手”的步骤相信各位都非常熟悉了：
（咦，这不是远程面试的开场白吗）
那么问题来了：为什么不是2次握手或者4次握手呢？
== 3次 ==
针对“为什么不是4次”，知乎的段子手是这么回答的：
由此可见知乎质量的下降。
实际上，上面省略了真正重要的信息，在握手过程中传输的，不是“你能不能听得到”，而是：
协商一个序号的过程需要一个来回（告知 + 确认），理论上需要2个来回（4次），互相确认了双方的初始序号（ISN，Initial Sequence Number），才能真正开始通信。
由于第二个来回的“告知”可以和前一次的“确认”合并在同一个报文里（具体怎么结合后面讲），因此最终只需要3次握手，就可以建立起一个tcp链接。
这也解释了为什么不能只有2次握手：因为只能协商一个序号。
不过话说回来，知乎段子手的回复也不是全在抖机灵：毕竟，发起方怎么才能确认接收方已经知道发起方知道接收方知道了呢？即使发起方再问一遍，接收方又怎么知道发起方知道了接收方知道了呢？
很遗憾，结论是：无论多少个来回都不能保证双方达成一致。
由于实践中丢包率通常不高，因此最合理的做法就是3次握手（2个来回），少了不够，多了白搭；同时配上相应的容错机制。
例如 SYN+ACK 包丢失，那么发起方在等待超时后重传SYN包即可。
然后问题又来了：为什么需要协商初始序号，才能开始通信呢？
== 可靠 ==
我们都知道，tcp是一个“可靠”（Reliable）的协议。
这里“可靠”指的不是保证送达，毕竟网络链路中存在太多不可靠因素。
在 IETF 的 RFC 793（TCP协议）中，Reliability的具体定义是：TCP协议必须能够应对网络通信系统中损坏、丢失、重复或者乱序发送的数据。
为了保证这一点，tcp需要给每一个 [字节] 编号：双方通过三次握手，互相确定了对方的初始序号，后续 [每个包的序号 - 初始序号] 就能标识该包在字节流中所处的位置，这样就可以通过重传来保证数据的连续性。
举个例子：
* 发送方（ISN=4000）
* 发出 4001、4002、4003、4004
* （假设每个包只有1字节的数据）
* 接收方
* 收到 4001、4002、4004
* 4003因为某种原因没有抵达
* 这时上层应用只能读到4001、4002中的信息
由于接收方没有收到4003，因此给发送方的ACK中，序号最大值是4003（表示收到了4003之前的数据）。
过了一段时间（Linux下默认是1s），发送方发现4003一直没被ACK，就会重传这个包。
当接收方最终收到 4003 以后，上层应用才可以读到4003和4004，从而保证其收到的消息都是可靠的。（以及，接收方需要给发送方ACK，序号是4005）
注意：虽然ISN=4000，但是发送方发送的第一个包，SEQ是4001开始的，TCP协议规定 SYN 需要占一个序号（虽然SYN并不是实际传输的数据），所以前面示意图中ACK的seq是 x+1 。同样，FIN也会占用一个序号，这样可以保证FIN报文的重传和确认不会有歧义。
但是，为什么序号不能从 0 开始呢？
== 可靠² ==
真实世界的复杂性总是让人头秃。
我们知道，操作系统使用五元组（协议=tcp，源IP，源端口，目的IP，目的端口）来标识一个连接，当一个包抵达时，会根据这个包的信息，将它分发到对应的连接去处理。
一般情况下，服务器的端口号通常是固定的（如http 80），而操作系统会为客户端随机分配一个最近没有被使用的端口号，因此包总能被分发到正确的连接里。
但在某些特殊的场景下（例如快速、连续地开启和关闭连接），客户端使用的端口号也可能和上一次一样（或者用了其他刚断开的连接的端口号）。
而TCP协议并不对此作出限制：
那么：
* 如果前一个连接的包，因为某种原因滞留在网络中，这会儿才送达，客户端可能无法区分（其sequence number在本连接中可能是有效的）。
* 恶意第三方伪造报文的难度很小。注意，在这个场景里，第三方并 [不需要] 处于通信双方的链路之间，只要他发出的报文可以抵达通信的一方即可。
因此我们需要精心挑选一个ISN，使得上述case发生的可能性尽可能低。
注意：不是在tcp协议的层面上100%避免，因为这会导致协议变得更复杂，实现上增加额外的开销，而在绝大多数情况下是不必要的。如果需要“100%可靠”，需要在应用层协议上增加额外的校验机制；或者使用类似IPSec这样的网络层协议来保证对包的有效识别。
那么，ISN应该如何挑选呢？
== ISN生成器 ==
说起来其实很简单：
TCP协议的要求是，实现一个大约每 4 微秒加 1 的 32bit 计数器（时钟），在每次创建一个新连接时，使用这个计数器的值作为ISN。
假设传输速度是 2 Mb/s，连接使用的sequence number大约需要 4.55 小时才会溢出并绕回（wrap-around）到ISN。即使提高到 100 Mb/s，也需要大约 5.4 分钟。
而一个包在网络中滞留的时间通常是有限的，这个时间我们称之为MSL（Maximum Segment Lifetime），工程实践中一般认为不会超过2分钟。
所以我们一般不用担心本次连接的早期segment（tcp协议称之为 old duplicates）导致的混淆。
注：在家用千兆以太网已经逐渐普及、服务器间开始使用万兆以太网卡的今天，wrap-around的时间已经降低到32.8s（千兆）、3.28s（万兆），这个假定已经不太站得住脚了，因此 rfc1185 针对这种高带宽环境提出了一种扩展方案，通过在报文中加上时间戳，从而可以识别出这些 old duplicates。
主要风险在于前面提到的场景：前一个连接可能传输了较多数据，因此其序列号可能大于当前连接的ISN；如果该连接的报文因为某种原因滞留、现在又突然冒出来，当前连接将无法分辨。
因此，TCP协议要求在断开连接时，TIME-WAIT 状态需要保留 2 MSL 的时间才能转成 CLOSED（如下图底部所示）。
（tcp连接状态图，截取自rfc 793）
那么问题又来了：为什么只有 TIME-WAIT 需要等待 2MSL，而LAST-ACK不需要呢？
== 报文 ==
针对TCP协议可以提的问题太多了，写得有点累，所以这里不打算继续自问自答了。
但写了这么多，还没有看一下TCP报文是什么结构的，实在不应该，这里还是祭出 rfc 793 里的 ascii art（并顺便佩服rfc大佬的画图功力）
简单介绍下：
* 一行是4个字节（32 bits），header一般共5行（options和padding是可选的）
* 第一行包含了源端口和目的端口
* 每个端口16bits，所以端口最大是65535
* 源IP和目的IP在IP报文头里
* 第二行是本次报文的Sequence Number
* 第三行是ACK序列号
* 第四行包含了较多信息：
* 数据偏移量：4字节的倍数，最小是0101（5），表示数据从第20个字节开始（大部分情况）
* 控制位（CTL）：一共6个，其中的ACK、SYN、FIN就不介绍了
* RST是Reset，遇到异常情况时通知对方重置连接（我们敬爱的防火墙很爱用它）
* URG表示这个报文很重要，应该优先传送、接收方应该及时给上层应用。URG的数据不影响seq，实际很少被用到，感兴趣的话可以参考下RFC 854（Telnet协议）
* PSH表示这个报文不应该被缓存、应当立即被发送出去。在交互式应用中比较常用，如ssh，用户每按下一个键都应该及时发出去。注意和Nagle算法可能会有一些冲突。
* 窗口大小：表示这个包的发送方当前可以接受的数据量（字节数），从这个包里的ack序号开始算起。**用于控制滑动窗口大小的关键字段就是它了。**
举个例子，三次握手的第二步，SYN和ACK合并的报文就是这么生成的：
* Sequence Number填入从ISN生成器中获取的值
* Acknowledgement Number填入 [发送方的序号 + 1]
* 将控制位中的ACK位、SYN位都置1
写不动了，真是没完没了（相信看到这里的同学已经不多了），但是TCP协议中还有很多有意思的设计本文完全没有涉及，文末我给出一些推荐阅读的链接，供感兴趣的同学参考。
== 总结 ==
* TCP“三次握手”翻译不准确
* 握手的目的是双方协商初始序列号ISN
* 序列号是用于保证通信的可靠性
* 不使用 0 作为ISN可以避免一些坑
* TCP报文里包含了端口号、2个序列号、一些控制位、滑动窗口大小
* 我在字节跳动网盟广告业务线（穿山甲），由于业务持续高速发展，长期缺人。关于字节跳动面试的详情，可参考我之前写的
* 《程序员面试指北：面试官视角》
* https://mp.weixin.qq.com/s/Byvu-w7kyby-L7FBCE24Uw
~ 投递链接 ~
后端开发(上海) https://job.toutiao.com/s/sBAvKe
后端开发(北京) https://job.toutiao.com/s/sBMyxk
广告策略研发(上海) https://job.toutiao.com/s/sBDMAK
其他地区、职能线 https://job.toutiao.com/s/sB9Jqk
== 推荐阅读 ==
[1] RFC 793：TRANSMISSION CONTROL PROTOCOL
https://tools.ietf.org/html/rfc793
[2] Coolshell - TCP 的那些事儿 （上 & 下）
https://coolshell.cn/articles/11564.html
https://coolshell.cn/articles/11609.html
[3] 知乎 - TCP 为什么是三次握手，而不是两次或四？
https://www.zhihu.com/question/24853633
== 握手 ==
多少有点令人意外的是，大多数程序员对TCP协议的印象仅限于在创建连接时的三次握手。
严格地说，“三次握手”其实是一个不太准确的翻译，英文原文是 "3-way handshake"，意思是握手有三个步骤。
不过既然教科书都这么翻译，我就只能先忍了。
“三次握手”的步骤相信各位都非常熟悉了：
引用
A: 喂，听得到吗 (SYN)
B: 阔以，你呢 (SYN-ACK)
A: 我也阔以，开始唠吧 (ACK)
B: 阔以，你呢 (SYN-ACK)
A: 我也阔以，开始唠吧 (ACK)
（咦，这不是远程面试的开场白吗）
那么问题来了：为什么不是2次握手或者4次握手呢？
== 3次 ==
针对“为什么不是4次”，知乎的段子手是这么回答的：
引用
A: 喂，听得到吗 (SYN)
B: 阔以，你呢 (SYN-ACK)
A: 我也阔以，你呢 (SYN-ACK)
B: ...我不想和傻*说话 (FIN)
B: 阔以，你呢 (SYN-ACK)
A: 我也阔以，你呢 (SYN-ACK)
B: ...我不想和傻*说话 (FIN)
实际上，上面省略了真正重要的信息，在握手过程中传输的，不是“你能不能听得到”，而是：
引用
A: 喂，我的数据从x开始编号 (SYN)
B: 知道了，我的从y开始编号 (SYN-ACK)
A: 行，咱俩开始唠吧 (ACK)
B: 知道了，我的从y开始编号 (SYN-ACK)
A: 行，咱俩开始唠吧 (ACK)
协商一个序号的过程需要一个来回（告知 + 确认），理论上需要2个来回（4次），互相确认了双方的初始序号（ISN，Initial Sequence Number），才能真正开始通信。
由于第二个来回的“告知”可以和前一次的“确认”合并在同一个报文里（具体怎么结合后面讲），因此最终只需要3次握手，就可以建立起一个tcp链接。
这也解释了为什么不能只有2次握手：因为只能协商一个序号。
不过话说回来，知乎段子手的回复也不是全在抖机灵：毕竟，发起方怎么才能确认接收方已经知道发起方知道接收方知道了呢？即使发起方再问一遍，接收方又怎么知道发起方知道了接收方知道了呢？
很遗憾，结论是：无论多少个来回都不能保证双方达成一致。
由于实践中丢包率通常不高，因此最合理的做法就是3次握手（2个来回），少了不够，多了白搭；同时配上相应的容错机制。
例如 SYN+ACK 包丢失，那么发起方在等待超时后重传SYN包即可。
引用
想想看，如果最后一个ACK丢了会怎样？
然后问题又来了：为什么需要协商初始序号，才能开始通信呢？
== 可靠 ==
我们都知道，tcp是一个“可靠”（Reliable）的协议。
这里“可靠”指的不是保证送达，毕竟网络链路中存在太多不可靠因素。
在 IETF 的 RFC 793（TCP协议）中，Reliability的具体定义是：TCP协议必须能够应对网络通信系统中损坏、丢失、重复或者乱序发送的数据。
引用
Reliability:
The TCP must recover from data that is damaged, lost, duplicated, or delivered out of order by the internet communication system.
https://tools.ietf.org/html/rfc793
The TCP must recover from data that is damaged, lost, duplicated, or delivered out of order by the internet communication system.
https://tools.ietf.org/html/rfc793
为了保证这一点，tcp需要给每一个 [字节] 编号：双方通过三次握手，互相确定了对方的初始序号，后续 [每个包的序号 - 初始序号] 就能标识该包在字节流中所处的位置，这样就可以通过重传来保证数据的连续性。
举个例子：
* 发送方（ISN=4000）
* 发出 4001、4002、4003、4004
* （假设每个包只有1字节的数据）
* 接收方
* 收到 4001、4002、4004
* 4003因为某种原因没有抵达
* 这时上层应用只能读到4001、4002中的信息
由于接收方没有收到4003，因此给发送方的ACK中，序号最大值是4003（表示收到了4003之前的数据）。
过了一段时间（Linux下默认是1s），发送方发现4003一直没被ACK，就会重传这个包。
当接收方最终收到 4003 以后，上层应用才可以读到4003和4004，从而保证其收到的消息都是可靠的。（以及，接收方需要给发送方ACK，序号是4005）
注意：虽然ISN=4000，但是发送方发送的第一个包，SEQ是4001开始的，TCP协议规定 SYN 需要占一个序号（虽然SYN并不是实际传输的数据），所以前面示意图中ACK的seq是 x+1 。同样，FIN也会占用一个序号，这样可以保证FIN报文的重传和确认不会有歧义。
但是，为什么序号不能从 0 开始呢？
== 可靠² ==
真实世界的复杂性总是让人头秃。
我们知道，操作系统使用五元组（协议=tcp，源IP，源端口，目的IP，目的端口）来标识一个连接，当一个包抵达时，会根据这个包的信息，将它分发到对应的连接去处理。
一般情况下，服务器的端口号通常是固定的（如http 80），而操作系统会为客户端随机分配一个最近没有被使用的端口号，因此包总能被分发到正确的连接里。
但在某些特殊的场景下（例如快速、连续地开启和关闭连接），客户端使用的端口号也可能和上一次一样（或者用了其他刚断开的连接的端口号）。
而TCP协议并不对此作出限制：
引用
The protocol places no restriction on a particular connection being used over and over again. ... New instances of a connection will be referred to as incarnations of the connection.
那么：
* 如果前一个连接的包，因为某种原因滞留在网络中，这会儿才送达，客户端可能无法区分（其sequence number在本连接中可能是有效的）。
* 恶意第三方伪造报文的难度很小。注意，在这个场景里，第三方并 [不需要] 处于通信双方的链路之间，只要他发出的报文可以抵达通信的一方即可。
因此我们需要精心挑选一个ISN，使得上述case发生的可能性尽可能低。
注意：不是在tcp协议的层面上100%避免，因为这会导致协议变得更复杂，实现上增加额外的开销，而在绝大多数情况下是不必要的。如果需要“100%可靠”，需要在应用层协议上增加额外的校验机制；或者使用类似IPSec这样的网络层协议来保证对包的有效识别。
那么，ISN应该如何挑选呢？
== ISN生成器 ==
说起来其实很简单：
TCP协议的要求是，实现一个大约每 4 微秒加 1 的 32bit 计数器（时钟），在每次创建一个新连接时，使用这个计数器的值作为ISN。
假设传输速度是 2 Mb/s，连接使用的sequence number大约需要 4.55 小时才会溢出并绕回（wrap-around）到ISN。即使提高到 100 Mb/s，也需要大约 5.4 分钟。
而一个包在网络中滞留的时间通常是有限的，这个时间我们称之为MSL（Maximum Segment Lifetime），工程实践中一般认为不会超过2分钟。
所以我们一般不用担心本次连接的早期segment（tcp协议称之为 old duplicates）导致的混淆。
注：在家用千兆以太网已经逐渐普及、服务器间开始使用万兆以太网卡的今天，wrap-around的时间已经降低到32.8s（千兆）、3.28s（万兆），这个假定已经不太站得住脚了，因此 rfc1185 针对这种高带宽环境提出了一种扩展方案，通过在报文中加上时间戳，从而可以识别出这些 old duplicates。
主要风险在于前面提到的场景：前一个连接可能传输了较多数据，因此其序列号可能大于当前连接的ISN；如果该连接的报文因为某种原因滞留、现在又突然冒出来，当前连接将无法分辨。
因此，TCP协议要求在断开连接时，TIME-WAIT 状态需要保留 2 MSL 的时间才能转成 CLOSED（如下图底部所示）。
（tcp连接状态图，截取自rfc 793）
那么问题又来了：为什么只有 TIME-WAIT 需要等待 2MSL，而LAST-ACK不需要呢？
== 报文 ==
针对TCP协议可以提的问题太多了，写得有点累，所以这里不打算继续自问自答了。
但写了这么多，还没有看一下TCP报文是什么结构的，实在不应该，这里还是祭出 rfc 793 里的 ascii art（并顺便佩服rfc大佬的画图功力）
简单介绍下：
* 一行是4个字节（32 bits），header一般共5行（options和padding是可选的）
* 第一行包含了源端口和目的端口
* 每个端口16bits，所以端口最大是65535
* 源IP和目的IP在IP报文头里
* 第二行是本次报文的Sequence Number
* 第三行是ACK序列号
* 第四行包含了较多信息：
* 数据偏移量：4字节的倍数，最小是0101（5），表示数据从第20个字节开始（大部分情况）
* 控制位（CTL）：一共6个，其中的ACK、SYN、FIN就不介绍了
* RST是Reset，遇到异常情况时通知对方重置连接（我们敬爱的防火墙很爱用它）
* URG表示这个报文很重要，应该优先传送、接收方应该及时给上层应用。URG的数据不影响seq，实际很少被用到，感兴趣的话可以参考下RFC 854（Telnet协议）
* PSH表示这个报文不应该被缓存、应当立即被发送出去。在交互式应用中比较常用，如ssh，用户每按下一个键都应该及时发出去。注意和Nagle算法可能会有一些冲突。
* 窗口大小：表示这个包的发送方当前可以接受的数据量（字节数），从这个包里的ack序号开始算起。**用于控制滑动窗口大小的关键字段就是它了。**
举个例子，三次握手的第二步，SYN和ACK合并的报文就是这么生成的：
* Sequence Number填入从ISN生成器中获取的值
* Acknowledgement Number填入 [发送方的序号 + 1]
* 将控制位中的ACK位、SYN位都置1
写不动了，真是没完没了（相信看到这里的同学已经不多了），但是TCP协议中还有很多有意思的设计本文完全没有涉及，文末我给出一些推荐阅读的链接，供感兴趣的同学参考。
== 总结 ==
* TCP“三次握手”翻译不准确
* 握手的目的是双方协商初始序列号ISN
* 序列号是用于保证通信的可靠性
* 不使用 0 作为ISN可以避免一些坑
* TCP报文里包含了端口号、2个序列号、一些控制位、滑动窗口大小
* 我在字节跳动网盟广告业务线（穿山甲），由于业务持续高速发展，长期缺人。关于字节跳动面试的详情，可参考我之前写的
* 《程序员面试指北：面试官视角》
* https://mp.weixin.qq.com/s/Byvu-w7kyby-L7FBCE24Uw
~ 投递链接 ~
后端开发(上海) https://job.toutiao.com/s/sBAvKe
后端开发(北京) https://job.toutiao.com/s/sBMyxk
广告策略研发(上海) https://job.toutiao.com/s/sBDMAK
其他地区、职能线 https://job.toutiao.com/s/sB9Jqk
== 推荐阅读 ==
[1] RFC 793：TRANSMISSION CONTROL PROTOCOL
https://tools.ietf.org/html/rfc793
[2] Coolshell - TCP 的那些事儿 （上 & 下）
https://coolshell.cn/articles/11564.html
https://coolshell.cn/articles/11609.html
[3] 知乎 - TCP 为什么是三次握手，而不是两次或四？
https://www.zhihu.com/question/24853633
