蚊章汇 - Gustavo Duarte
type: channel
link: https://linuxcn.bwsl.wang/author/843/
description: Gustavo Duarte
items: 闭包、对象，以及堆“族”
items: 尾调用、优化和 ES6
items: 探秘“栈”之旅（II）：结语、金丝雀和缓冲区溢出
items: 探秘“栈”之旅
items: 系统调用，让世界转起来！
items: 递归：梦中梦
items: 页面缓存：内存和文件之间的那些事
items: 内核如何管理内存
items: 当 CPU 空闲时它都在做什么？
items: 剖析内存中的程序之秘

闭包、对象，以及堆“族”
type: item
date: 2018-06-18T19:05:00+08:00
description: 在上篇文章中我们提到了闭包、对象、以及栈外的其它东西。我们学习的大部分内容都是与特定编程语言无关的元素，但是，我主要还是专注于 JavaScript，以及一些 C。让我们以一个简单的 C 程序开始，它的功能是读取一首歌曲和乐队名字，然后将它们输出给用户：#include <stdio.h> #include <string.h> char *read() { char data[64]; fgets(data, 64, stdin); return data; } int main(int argc, char *argv[]) { char *song, *band; puts("Enter song, then band:"); song = read(); band = read(); printf("\n%sby %s", song, band); return 0; } stackFolly.c 下载如果你运行这个程序，你会得到什么？（=> 表示程序输出）：./stackFolly => Enter song, then band: The Past is a Grotesque Animal of Montreal => ?ǿontreal => by ?ǿontreal （曾经的 C 新手说）发生了错误？事实证明，函数的栈变量的内容仅在栈帧活动期间才是可用的，也就是说，仅在函数返回之前。在上面的返回中，被栈帧使用过的内存 被认为是可用的，并且在下一个函数调用中可以被覆写。下面的图展示了这种情况下究竟发生了什么。这个图现在有一个图片映射（LCTT 译注：译文中无法包含此映射，上下两个矩形区域分别链接至输出的 #47 行和 #70 行），因此，你可以点击一个数据片断去看一下相关的 GDB 输出（GDB 命令在 这里）。只要 read() 读取了歌曲的名字，栈将是这个样子：在这个时候，这个 song 变量立即指向到歌曲的名字。不幸的是，存储字符串的内存位置准备被下次调用的任意函数的栈帧重用。在这种情况下，read() 再次被调用，而且使用的是同一个位置的栈帧，因此，结果变成下图的样子（LCTT 译注：上下两个矩形映射分别链接至 #76 行和 #79 行）：乐队名字被读入到相同的内存位置，并且覆盖了前面存储的歌曲名字。band 和 song 最终都准确指向到相同点。最后，我们甚至都不能得到 “of Montreal”（LCTT 译注：一个欧美乐队的名字） 的正确输出。你能猜到是为什么吗？因此，即使栈很有用，但也有很重要的限制。它不能被一个函数用于去存储比该函数的运行周期还要长的数据。你必须将它交给 堆，然后与热点缓存、明确的瞬时操作、以及频繁计算的偏移等内容道别。有利的一面是，它是工作 的：这个代价是你必须记得去 free() 内存，或者由一个垃圾回收机制花费一些性能来随机回收，垃圾回收将去找到未使用的堆对象，然后去回收它们。那就是栈和堆之间在本质上的权衡：性能 vs. 灵活性。大多数编程语言的虚拟机都有一个中间层用来做一个 C 程序员该做的一些事情。栈被用于值类型，比如，整数、浮点数、以及布尔型。这些都按特定值（像上面的 argc ）的字节顺序被直接保存在本地变量和对象字段中。相比之下，堆被用于引用类型，比如，字符串和 对象。 变量和字段包含一个引用到这个对象的内存地址，像上面的 song 和 band。参考这个 JavaScript 函数：function fn() { var a = 10; var b = { name: 'foo', n: 10 }; } 它可能的结果如下（LCTT 译注：图片内“object”、“string”和“a”的映射分别链接至 #1671 行、 #8656 行和 #1264 行）：我之所以说“可能”的原因是，特定的行为高度依赖于实现。这篇文章使用的许多流程图形是以一个 V8 为中心的方法，这些图形都链接到相关的源代码。在 V8 中，仅 小整数 是 以值的方式保存。因此，从现在开始，我将在对象中直接以字符串去展示，以避免引起混乱，但是，请记住，正如上图所示的那样，它们在堆中是分开保存的。现在，我们来看一下闭包，它其实很简单，但是由于我们将它宣传的过于夸张，以致于有点神化了。先看一个简单的 JS 函数：function add(a, b) { var c = a + b; return c; } 这个函数定义了一个 词法域 lexical scope ，它是一个快乐的小王国，在这里它的名字 a、b、c 是有明确意义的。它有两个参数和由函数声明的一个本地变量。程序也可以在别的地方使用相同的名字，但是在 add 内部它们所引用的内容是明确的。尽管词法域是一个很好的术语，它符合我们直观上的理解：…

尾调用、优化和 ES6
type: item
date: 2018-06-14T20:50:16+08:00
description: 在探秘“栈”的倒数第二篇文章中，我们提到了 尾调用 tail call 、编译优化、以及新发布的 JavaScript 上 合理尾调用 proper tail call 。当一个函数 F 调用另一个函数作为它的结束动作时，就发生了一个尾调用。在那个时间点，函数 F 绝对不会有多余的工作：函数 F 将“球”传给被它调用的任意函数之后，它自己就“消失”了。这就是关键点，因为它打开了尾调用优化的“可能之门”：我们可以简单地重用函数 F 的栈帧，而不是为函数调用 创建一个新的栈帧，因此节省了栈空间并且避免了新建一个栈帧所需要的工作量。下面是一个用 C 写的简单示例，然后使用 mild 优化 来编译它的结果：int add5(int a) { return a + 5; } int add10(int a) { int b = add5(a); // not tail return add5(b); // tail } int add5AndTriple(int a){ int b = add5(a); // not tail return 3 * add5(a); // not tail, doing work after the call } int finicky(int a){ if (a > 10){ return add5AndTriple(a); // tail } if (a > 5){ int b = add5(a); // not tail return finicky(b); // tail } return add10(a); // tail } 简单的尾调用 下载在编译器的输出中，在预期会有一个 调用 的地方，你可以看到一个 跳转 指令，一般情况下你可以发现尾调用优化（以下简称 TCO）。在运行时中，TCO 将会引起调用栈的减少。一个通常认为的错误观念是，尾调用必须要 递归。实际上并不是这样的：一个尾调用可以被递归，比如在上面的 finicky() 中，但是，并不是必须要使用递归的。在调用点只要函数 F 完成它的调用，我们将得到一个单独的尾调用。是否能够进行优化这是一个另外的问题，它取决于你的编程环境。“是的，它总是可以！”，这是我们所希望的最佳答案，它是著名的 Scheme 中的方式，就像是在 SICP上所讨论的那样（顺便说一声，如果你的程序不像“一个魔法师使用你的咒语召唤你的电脑精灵”那般有效，建议你读一下这本书）。它也是 Lua 的方式。而更重要的是，它是下一个版本的 JavaScript —— ES6 的方式，这个规范清晰地定义了尾的位置，并且明确了优化所需要的几个条件，比如，严格模式。当一个编程语言保证可用 TCO 时，它将支持 合理尾调用 proper tail call 。现在，我们中的一些人不能抛开那些 C 的习惯，心脏出血，等等，而答案是一个更复杂的“有时候”，它将我们带进了编译优化的领域。我们看一下上面的那个 简单示例；把我们 上篇文章 的阶乘程序重新拿出来：#include <stdio.h> int factorial(int n) { int previous = 0xdeadbeef; if (n == 0 || n == 1) { return 1; } previous = factorial(n-1); return n * previous; } int main(int argc) { int answer = factorial(5); printf("%d\n", answer); } 递归阶乘 下载像第 11 行那样的，是尾调用吗？答案是：“不是”，因为它被后面的 n 相乘了。但是，如果你不去优化它，GCC 使用 O2 优化 的 结果 会让你震惊：它不仅将阶乘转换为一个 无递归循环，而且 factorial(5) 调用被整个消除了，而以一个 120 (5! == 120) 的 编译时常数来替换。这就是调试优化代码有时会很难的原因。好的方面是，如果你调用这个函数，它将使用一个单个的栈帧，而不会去考虑 n 的初始值。编译算法是非常有趣的，如果你对它感兴趣，我建议你去阅读 构建一个优化编译器 和 ACDI。但是，这里没有做尾调用优化时到底发生了什么？通过分析函数的功能和无需优化的递归发现，GCC 比我们更聪明，因为一开始就没有使用尾调用。由于过于简单以及很确定的操作，这个任务变得很简单。我们给它增加一些可以引起混乱的东西（比如，getpid()），我们给 GCC 增加难度：#include <stdio.h> #include <sys/types.h> #include <unistd.h> int pidFactorial(int n) { if (1 == n) { …

探秘“栈”之旅（II）：结语、金丝雀和缓冲区溢出
type: item
date: 2018-06-10T07:26:39+08:00
description: 上一周我们讲解了 栈是如何工作的 以及在函数的 序言 prologue 上栈帧是如何被构建的。今天，我们来看一下它的相反的过程，在函数 结语 epilogue 中栈帧是如何被销毁的。重新回到我们的 add.c 上：int add(int a, int b) { int result = a + b; return result; } int main(int argc) { int answer; answer = add(40, 2); } 简单的一个做加法的程序 - add.c在运行到第 4 行时，在把 a + b 值赋给 result 后，这时发生了什么：第一个指令是有些多余而且有点傻的，因为我们知道 eax 已经等于 result 了，但这就是关闭优化时得到的结果。leave 指令接着运行，这一小段做了两个任务：重置 esp 并将它指向到当前栈帧开始的地方，另一个是恢复在 ebp 中保存的值。这两个操作在逻辑上是独立的，因此，在图中将它们分开来说，但是，如果你使用一个调试器去跟踪，你就会发现它们都是自动发生的。在 leave 运行后，恢复了前一个栈帧。add 调用唯一留下的东西就是在栈顶部的返回地址。它包含了运行完 add 之后在 main 中必须运行的指令的地址。ret 指令用来处理它：它弹出返回地址到 eip 寄存器（LCTT 译注：32 位的指令寄存器），这个寄存器指向下一个要执行的指令。现在程序将返回到 main ，主要部分如下：main 从 add 中拷贝返回值到本地变量 answer，然后，运行它自己的 结语 epilogue ，这一点和其它的函数是一样的。在 main 中唯一的怪异之处是，保存在 ebp 中的是 null 值，因为它是我们的代码中的第一个栈帧。最后一步执行的是，返回到 C 运行时库（libc），它将退回到操作系统中。这里为需要的人提供了一个 完整的返回顺序 的图。现在，你已经理解了栈是如何运作的，所以我们现在可以来看一下，一直以来最臭名昭著的黑客行为：利用缓冲区溢出。这是一个有漏洞的程序：void doRead() { char buffer[28]; gets(buffer); } int main(int argc) { doRead(); } 有漏洞的程序 - buffer.c上面的代码中使用了 gets 从标准输入中去读取内容。gets 持续读取直到一个新行或者文件结束。下图是读取一个字符串之后栈的示意图：在这里存在的问题是，gets 并不知道缓冲区（buffer）大小：它毫无查觉地持续读取输入内容，并将读取的内容填入到缓冲区那边的栈，清除保存在 ebp 中的值、返回地址，下面的其它内容也是如此。对于利用这种行为，攻击者制作一个精密的载荷并将它“喂”给程序。在这个时候，栈应该是下图所示的样子，然后去调用 gets：基本的思路是提供一个恶意的汇编代码去运行，通过覆写栈上的返回地址指向到那个代码。这有点像病毒侵入一个细胞，颠覆它，然后引入一些 RNA 去达到它的目的。和病毒一样，挖掘者的载荷有许多特别的功能。它以几个 nop 指令开始，以提升成功利用的可能性。这是因为返回的地址是一个绝对的地址，需要猜测，而攻击者并不知道保存它的代码的栈的准确位置。但是，只要它们进入一个 nop，这个漏洞利用就成功了：处理器将运行 nop 指令，直到命中它希望去运行的指令。exec /bin/sh 表示运行一个 shell 的原始汇编指令（假设漏洞是在一个网络程序中，因此，这个漏洞可能提供一个访问系统的 shell）。将一个命令或用户输入以原始汇编指令的方式嵌入到一个程序中的思路是很可怕的，但是，那只是让安全研究如此有趣且“脑洞大开”的一部分而已。对于防范这个怪异的 get，给你提供一个思路，有时候，在有漏洞的程序上，让它的输入转换为小写或者大写，将迫使攻击者写的汇编指令的完整字节不属于小写或者大写的 ascii 字母的范围内。最后，攻击者重复猜测几次返回地址，这将再次提升他们的胜算。以 4 字节为界进行多次重复，它们就会更好地覆写栈上的原始返回地址。幸亏，现代操作系统有了 防止缓冲区溢出 的一系列保护措施，包括不可执行的栈和 栈内金丝雀 stack canary 。这个 “ 金丝雀 canary ” 名字来自 煤矿中的金丝雀 canary in a coal mine 中的表述（LCTT 译注：指在过去煤矿工人下井时会带一只金丝雀，因为金丝雀对煤矿中的瓦斯气体非常敏感，如果进入煤矿后，金丝雀死亡，说明瓦斯超标，矿工会立即撤出煤矿。金丝雀做为煤矿中瓦斯预警器来使用），这是对计算机科学词汇的补充，用 Steve McConnell 的话解释如下：计算机科学拥有比其它任何领域都丰富多彩的语言，在其它的领域中…

探秘“栈”之旅
type: item
date: 2018-05-16T02:31:28+08:00
description: 早些时候，我们探索了 “内存中的程序之秘”，我们欣赏了在一台电脑中是如何运行我们的程序的。今天，我们去探索栈的调用，它在大多数编程语言和虚拟机中都默默地存在。在此过程中，我们将接触到一些平时很难见到的东西，像 闭包 closure 、递归、以及缓冲溢出等等。但是，我们首先要作的事情是，描绘出栈是如何运作的。栈非常重要，因为它追踪着一个程序中运行的函数，而函数又是一个软件的重要组成部分。事实上，程序的内部操作都是非常简单的。它大部分是由函数向栈中推入数据或者从栈中弹出数据的相互调用组成的，而在堆上为数据分配内存才能在跨函数的调用中保持数据。不论是低级的 C 软件还是像 JavaScript 和 C# 这样的基于虚拟机的语言，它们都是这样的。而对这些行为的深刻理解，对排错、性能调优以及大概了解究竟发生了什么是非常重要的。当一个函数被调用时，将会创建一个 栈帧 stack frame 去支持函数的运行。这个栈帧包含函数的局部变量和调用者传递给它的参数。这个栈帧也包含了允许被调用的函数（callee）安全返回给其调用者的内部事务信息。栈帧的精确内容和结构因处理器架构和函数调用规则而不同。在本文中我们以 Intel x86 架构和使用 C 风格的函数调用（cdecl）的栈为例。下图是一个处于栈顶部的一个单个栈帧：在图上的场景中，有三个 CPU 寄存器进入栈。 栈指针 stack pointer esp（LCTT 译注：扩展栈指针寄存器） 指向到栈的顶部。栈的顶部总是被最后一个推入到栈且还没有弹出的东西所占据，就像现实世界中堆在一起的一叠盘子或者 100 美元大钞一样。保存在 esp 中的地址始终在变化着，因为栈中的东西不停被推入和弹出，而它总是指向栈中的最后一个推入的东西。许多 CPU 指令的一个副作用就是自动更新 esp，离开寄存器而使用栈是行不通的。在 Intel 的架构中，绝大多数情况下，栈的增长是向着低位内存地址的方向。因此，这个“顶部” 在包含数据的栈中是处于低位的内存地址（在这种情况下，包含的数据是 local_buffer）。注意，关于从 esp 到 local_buffer 的箭头不是随意连接的。这个箭头代表着事务：它专门指向到由 local_buffer 所拥有的第一个字节，因为，那是一个保存在 esp 中的精确地址。第二个寄存器跟踪的栈是 ebp（LCTT 译注：扩展基址指针寄存器），它包含一个 基指针 base pointer 或者称为 帧指针 frame pointer 。它指向到一个当前运行的函数的栈帧内的固定位置，并且它为参数和局部变量的访问提供一个稳定的参考点（基址）。仅当开始或者结束调用一个函数时，ebp 的内容才会发生变化。因此，我们可以很容易地处理在栈中的从 ebp 开始偏移后的每个东西。如图所示。不像 esp， ebp 大多数情况下是在程序代码中通过花费很少的 CPU 来进行维护的。有时候，完成抛弃 ebp 有一些性能优势，可以通过 编译标志 来做到这一点。Linux 内核就是一个这样做的示例。最后，eax（LCTT 译注：扩展的 32 位通用数据寄存器）寄存器惯例被用来转换大多数 C 数据类型返回值给调用者。现在，我们来看一下在我们的栈帧中的数据。下图清晰地按字节展示了字节的内容，就像你在一个调试器中所看到的内容一样，内存是从左到右、从顶部至底部增长的，如下图所示：局部变量 local_buffer 是一个字节数组，包含一个由 null 终止的 ASCII 字符串，这是 C 程序中的一个基本元素。这个字符串可以读取自任意地方，例如，从键盘输入或者来自一个文件，它只有 7 个字节的长度。因为，local_buffer 只能保存 8 字节，所以还剩下 1 个未使用的字节。这个字节的内容是未知的，因为栈不断地推入和弹出，除了你写入的之外，你根本不会知道内存中保存了什么。这是因为 C 编译器并不为栈帧初始化内存，所以它的内容是未知的并且是随机的 —— 除非是你自己写入。这使得一些人对此很困惑。再往上走，local1 是一个 4 字节的整数，并且你可以看到每个字节的内容。它似乎是一个很大的数字，在8 后面跟着的都是零，在这里可能会误导你。Intel 处理器是 小端 little endian 机器，这表示在内存中的数字也是首先从小的一端开始的。因此，在一个多字节数字中，较小的部分在内存中处于最低端的地址。因为一般情况下是从左边开始显示的，这背离了我们通常的数字表示方式。我们讨论的这种从小到大的机制，使我想起《格里佛游记》：就像小人国的人们吃鸡蛋是从小头开始的一样，Intel 处理器处理它们的数字也是从字节的小端开始的。因此，local1 事实上只保存了一个数字 8，和章鱼的腿数量一样。然而，param1 在…

系统调用，让世界转起来！
type: item
date: 2018-05-11T08:23:00+08:00
description: 我其实不想将它分解开给你看，用户应用程序其实就是一个可怜的 瓮中大脑 brain in a vat ：它与外部世界的每个交流都要在内核的帮助下通过系统调用才能完成。一个应用程序要想保存一个文件、写到终端、或者打开一个 TCP 连接，内核都要参与。应用程序是被内核高度怀疑的：认为它到处充斥着 bug，甚至是个充满邪恶想法的脑子。这些系统调用是从一个应用程序到内核的函数调用。出于安全考虑，它们使用了特定的机制，实际上你只是调用了内核的 API。“ 系统调用 system call ”这个术语指的是调用由内核提供的特定功能（比如，系统调用 open()）或者是调用途径。你也可以简称为：syscall。这篇文章讲解系统调用，系统调用与调用一个库有何区别，以及在操作系统/应用程序接口上的刺探工具。如果彻底了解了应用程序借助操作系统发生的哪些事情，那么就可以将一个不可能解决的问题转变成一个快速而有趣的难题。那么，下图是一个运行着的应用程序，一个用户进程：它有一个私有的 虚拟地址空间—— 它自己的内存沙箱。整个系统都在它的地址空间中（即上面比喻的那个“瓮”），程序的二进制文件加上它所使用的库全部都 被映射到内存中。内核自身也映射为地址空间的一部分。下面是我们程序 pid 的代码，它通过 getpid(2) 直接获取了其进程 id：#include <sys/types.h> #include <unistd.h> #include <stdio.h> int main() { pid_t p = getpid(); printf("%d\n", p); } pid.c download在 Linux 中，一个进程并不是一出生就知道它的 PID。要想知道它的 PID，它必须去询问内核，因此，这个询问请求也是一个系统调用：它的第一步是开始于调用 C 库的 getpid()，它是系统调用的一个封装。当你调用一些函数时，比如，open(2)、read(2) 之类，你是在调用这些封装。其实，对于大多数编程语言在这一块的原生方法，最终都是在 libc 中完成的。封装为这些基本的操作系统 API 提供了方便，这样可以保持内核的简洁。所有的内核代码运行在特权模式下，有 bug 的内核代码行将会产生致命的后果。能在用户模式下做的任何事情都应该在用户模式中完成。由库来提供友好的方法和想要的参数处理，像 printf(3) 这样。我们拿一个 web API 进行比较，内核的封装方式可以类比为构建一个尽可能简单的 HTTP 接口去提供服务，然后提供特定语言的库及辅助方法。或者也可能有一些缓存，这就是 libc 的 getpid() 所做的：首次调用时，它真实地去执行了一个系统调用，然后，它缓存了 PID，这样就可以避免后续调用时的系统调用开销。一旦封装完成，它做的第一件事就是进入了内核 超空间 hyperspace 。这种转换机制因处理器架构设计不同而不同。在 Intel 处理器中，参数和 系统调用号 是 加载到寄存器中的，然后，运行一个 指令 将 CPU 置于 特权模式 中，并立即将控制权转移到内核中的全局系统调用 入口。如果你对这些细节感兴趣，David Drysdale 在 LWN 上有两篇非常好的文章（其一，其二）。内核然后使用这个系统调用号作为进入 sys_call_table 的一个 索引，它是一个函数指针到每个系统调用实现的数组。在这里，调用了 sys_getpid：在 Linux 中，系统调用大多数都实现为架构无关的 C 函数，有时候这样做 很琐碎，但是通过内核优秀的设计，系统调用机制被严格隔离。它们是工作在一般数据结构中的普通代码。嗯，除了完全偏执的参数校验以外。一旦它们的工作完成，它们就会正常返回，然后，架构特定的代码会接手转回到用户模式，封装将在那里继续做一些后续处理工作。在我们的例子中，getpid(2) 现在缓存了由内核返回的 PID。如果内核返回了一个错误，另外的封装可以去设置全局 errno 变量。这些细节可以让你知道 GNU 是怎么处理的。如果你想要原生的调用，glibc 提供了 syscall(2) 函数，它可以不通过封装来产生一个系统调用。你也可以通过它来做一个你自己的封装。这对一个 C 库来说，既不神奇，也不特殊。这种系统调用的设计影响是很深远的。我们从一个非常有用的 strace(1) 开始，这个工具可以用来监视 Linux 进程的系统调用（在 Mac 上，参见 dtruss(1m) 和神奇的 dtrace；在 Windows 中，参见 sysinternals）。这是对 pid 程序的跟踪：~/code/x86-os$ strace ./pid execve("./pid", ["./pid"], [/* 20 vars …

递归：梦中梦
type: item
date: 2018-05-06T19:15:00+08:00
description: “方其梦也，不知其梦也。梦之中又占其梦焉，觉而后知其梦也。”—— 《庄子·齐物论》递归是很神奇的，但是在大多数的编程类书藉中对递归讲解的并不好。它们只是给你展示一个递归阶乘的实现，然后警告你递归运行的很慢，并且还有可能因为栈缓冲区溢出而崩溃。“你可以将头伸进微波炉中去烘干你的头发，但是需要警惕颅内高压并让你的头发生爆炸，或者你可以使用毛巾来擦干头发。”难怪人们不愿意使用递归。但这种建议是很糟糕的，因为在算法中，递归是一个非常强大的思想。我们来看一下这个经典的递归阶乘：#include <stdio.h> int factorial(int n) { int previous = 0xdeadbeef; if (n == 0 || n == 1) { return 1; } previous = factorial(n-1); return n * previous; } int main(int argc) { int answer = factorial(5); printf("%d\n", answer); } 递归阶乘 - factorial.c函数调用自身的这个观点在一开始是让人很难理解的。为了让这个过程更形象具体，下图展示的是当调用 factorial(5) 并且达到 n == 1这行代码 时，栈上 端点的情况：每次调用 factorial 都生成一个新的 栈帧。这些栈帧的创建和 销毁 是使得递归版本的阶乘慢于其相应的迭代版本的原因。在调用返回之前，累积的这些栈帧可能会耗尽栈空间，进而使你的程序崩溃。而这些担心经常是存在于理论上的。例如，对于每个 factorial 的栈帧占用 16 字节（这可能取决于栈排列以及其它因素）。如果在你的电脑上运行着现代的 x86 的 Linux 内核，一般情况下你拥有 8 GB 的栈空间，因此，factorial 程序中的 n 最多可以达到 512,000 左右。这是一个 巨大无比的结果，它将花费 8,971,833 比特来表示这个结果，因此，栈空间根本就不是什么问题：一个极小的整数 —— 甚至是一个 64 位的整数 —— 在我们的栈空间被耗尽之前就早已经溢出了成千上万次了。过一会儿我们再去看 CPU 的使用，现在，我们先从比特和字节回退一步，把递归看作一种通用技术。我们的阶乘算法可归结为：将整数 N、N-1、 … 1 推入到一个栈，然后将它们按相反的顺序相乘。实际上我们使用了程序调用栈来实现这一点，这是它的细节：我们在堆上分配一个栈并使用它。虽然调用栈具有特殊的特性，但是它也只是又一种数据结构而已，你可以随意使用。我希望这个示意图可以让你明白这一点。当你将栈调用视为一种数据结构，有些事情将变得更加清晰明了：将那些整数堆积起来，然后再将它们相乘，这并不是一个好的想法。那是一种有缺陷的实现：就像你拿螺丝刀去钉钉子一样。相对更合理的是使用一个迭代过程去计算阶乘。但是，螺丝钉太多了，我们只能挑一个。有一个经典的面试题，在迷宫里有一只老鼠，你必须帮助这只老鼠找到一个奶酪。假设老鼠能够在迷宫中向左或者向右转弯。你该怎么去建模来解决这个问题？就像现实生活中的很多问题一样，你可以将这个老鼠找奶酪的问题简化为一个图，一个二叉树的每个结点代表在迷宫中的一个位置。然后你可以让老鼠在任何可能的地方都左转，而当它进入一个死胡同时，再回溯回去，再右转。这是一个老鼠行走的 迷宫示例:每到边缘（线）都让老鼠左转或者右转来到达一个新的位置。如果向哪边转都被拦住，说明相关的边缘不存在。现在，我们来讨论一下！这个过程无论你是调用栈还是其它数据结构，它都离不开一个递归的过程。而使用调用栈是非常容易的：#include <stdio.h> #include "maze.h" int explore(maze_t *node) { int found = 0; if (node == NULL) { return 0; } if (node->hasCheese){ return 1;// found cheese } found = explore(node->left) || explore(node->right); return found; } int main(int argc) { int found = explore(&maze); } 递归迷宫求解 下载当我们在 maze.c:13 中找到奶酪时，栈的情况如下图所示。你也可以在 GDB 输出 中看到更详细的数据，它是使用 命令 采集的数据。它展示了递归的良好表现，因为这是一个适合使用递归的问题。而且这并不奇怪：当涉及到算法时，递归是规则，而不是例外。它出现在如下情景中——进行搜索时、进行遍历树和其它数据结构时、进行解析时、需要排序时——它无处不在。正如众所周…

页面缓存：内存和文件之间的那些事
type: item
date: 2018-04-09T03:17:00+08:00
description: 上一篇文章中我们学习了内核怎么为一个用户进程 管理虚拟内存，而没有提及文件和 I/O。这一篇文章我们将专门去讲这个重要的主题 —— 页面缓存。文件和内存之间的关系常常很不好去理解，而它们对系统性能的影响却是非常大的。在面对文件时，有两个很重要的问题需要操作系统去解决。第一个是相对内存而言，慢的让人发狂的硬盘驱动器，尤其是磁盘寻道。第二个是需要将文件内容一次性地加载到物理内存中，以便程序间共享文件内容。如果你在 Windows 中使用 进程浏览器 去查看它的进程，你将会看到每个进程中加载了大约 ~15MB 的公共 DLL。我的 Windows 机器上现在大约运行着 100 个进程，因此，如果不共享的话，仅这些公共的 DLL 就要使用高达 ~1.5 GB 的物理内存。如果是那样的话，那就太糟糕了。同样的，几乎所有的 Linux 进程都需要 ld.so 和 libc，加上其它的公共库，它们占用的内存数量也不是一个小数目。幸运的是，这两个问题都用一个办法解决了：页面缓存 —— 保存在内存中的页面大小的文件块。为了用图去说明页面缓存，我捏造出一个名为 render 的 Linux 程序，它打开了文件 scene.dat，并且一次读取 512 字节，并将文件内容存储到一个分配到堆中的块上。第一次读取的过程如下：render 请求 scene.dat 从位移 0 开始的 512 字节。内核搜寻页面缓存中 scene.dat 的 4kb 块，以满足该请求。假设该数据没有缓存。内核分配页面帧，初始化 I/O 请求，将 scend.dat 从位移 0 开始的 4kb 复制到分配的页面帧。内核从页面缓存复制请求的 512 字节到用户缓冲区，系统调用 read() 结束。读取完 12KB 的文件内容以后，render 程序的堆和相关的页面帧如下图所示：它看起来很简单，其实这一过程做了很多的事情。首先，虽然这个程序使用了普通的读取（read）调用，但是，已经有三个 4KB 的页面帧将文件 scene.dat 的一部分内容保存在了页面缓存中。虽然有时让人觉得很惊奇，但是，普通的文件 I/O 就是这样通过页面缓存来进行的。在 x86 架构的 Linux 中，内核将文件认为是一系列的 4KB 大小的块。如果你从文件中读取单个字节，包含这个字节的整个 4KB 块将被从磁盘中读入到页面缓存中。这是可以理解的，因为磁盘通常是持续吞吐的，并且程序一般也不会从磁盘区域仅仅读取几个字节。页面缓存知道文件中的每个 4KB 块的位置，在上图中用 #0、#1 等等来描述。Windows 使用 256KB 大小的 视图 view ，类似于 Linux 的页面缓存中的 页面 page 。不幸的是，在一个普通的文件读取中，内核必须拷贝页面缓存中的内容到用户缓冲区中，它不仅花费 CPU 时间和影响 CPU 缓存，在复制数据时也浪费物理内存。如前面的图示，scene.dat 的内存被存储了两次，并且，程序中的每个实例都用另外的时间去存储内容。我们虽然解决了从磁盘中读取文件缓慢的问题，但是在其它的方面带来了更痛苦的问题。内存映射文件是解决这种痛苦的一个方法：当你使用文件映射时，内核直接在页面缓存上映射你的程序的虚拟页面。这样可以显著提升性能：Windows 系统编程 报告指出，在相关的普通文件读取上运行时性能提升多达 30% ，在 Unix 环境中的高级编程 的报告中，文件映射在 Linux 和 Solaris 也有类似的效果。这取决于你的应用程序类型的不同，通过使用文件映射，可以节约大量的物理内存。对高性能的追求是永恒不变的目标，测量是很重要的事情，内存映射应该是程序员始终要使用的工具。这个 API 提供了非常好用的实现方式，它允许你在内存中按字节去访问一个文件，而不需要为了这种好处而牺牲代码可读性。在一个类 Unix 的系统中，可以使用 mmap 查看你的 地址空间，在 Windows 中，可以使用 CreateFileMapping.aspx)，或者在高级编程语言中还有更多的可用封装。当你映射一个文件内容时，它并不是一次性将全部内容都映射到内存中，而是通过 页面故障 来按需映射的。在 获取 需要的文件内容的页面帧后，页面故障句柄 映射你的虚拟页面 到页面缓存上。如果一开始文件内容没有缓存，这还将涉及到磁盘 I/O。现在出现一个突发的状况，假设我们的 render 程序的最后一个实例退出了。在页面缓存中保存着 scene.dat 内容的页面要立刻释放掉吗？人们通常会如此考虑，但是，那样做并不是个好主意。你应该想到，我们经常在一个程序中创建一个文件，退出程序，然后，在第二个程序去使用这个文件。页面缓存正好可以处理这种情况。如果考虑更多的情况，内核为什么要清除页面缓存的内容？请记住，磁盘…

内核如何管理内存
type: item
date: 2018-03-01T17:16:00+08:00
description: 在学习了进程的 虚拟地址布局 之后，让我们回到内核，来学习它管理用户内存的机制。这里再次使用 Gonzo：Linux 进程在内核中是作为进程描述符 task\_struct （LCTT 译注：它是在 Linux 中描述进程完整信息的一种数据结构）的实例来实现的。在 task\_struct 中的 mm 域指向到内存描述符，mm\_struct 是一个程序在内存中的执行摘要。如上图所示，它保存了起始和结束内存段，进程使用的物理内存页面的 数量（RSS 常驻内存大小 Resident Set Size ）、虚拟地址空间使用的 总数量、以及其它片断。 在内存描述符中，我们可以获悉它有两种管理内存的方式：虚拟内存区域集和页面表。Gonzo 的内存区域如下所示：每个虚拟内存区域（VMA）是一个连续的虚拟地址范围；这些区域绝对不会重叠。一个 vm\_area\_struct 的实例完整地描述了一个内存区域，包括它的起始和结束地址，flags 决定了访问权限和行为，并且 vm\_file 域指定了映射到这个区域的文件（如果有的话）。（除了内存映射段的例外情况之外，）一个 VMA 是不能匿名映射文件的。上面的每个内存段（比如，堆、栈）都对应一个单个的 VMA。虽然它通常都使用在 x86 的机器上，但它并不是必需的。VMA 也不关心它们在哪个段中。一个程序的 VMA 在内存描述符中是作为 mmap 域的一个链接列表保存的，以起始虚拟地址为序进行排列，并且在 mm\_rb 域中作为一个 红黑树 的根。红黑树允许内核通过给定的虚拟地址去快速搜索内存区域。在你读取文件 /proc/pid_of_process/maps 时，内核只是简单地读取每个进程的 VMA 的链接列表并显示它们。在 Windows 中，EPROCESS 块大致类似于一个 task\_struct 和 mm\_struct 的结合。在 Windows 中模拟一个 VMA 的是虚拟地址描述符，或称为 VAD；它保存在一个 AVL 树 中。你知道关于 Windows 和 Linux 之间最有趣的事情是什么吗？其实它们只有一点小差别。4GB 虚拟地址空间被分配到页面中。在 32 位模式中的 x86 处理器中支持 4KB、2MB、以及 4MB 大小的页面。Linux 和 Windows 都使用大小为 4KB 的页面去映射用户的一部分虚拟地址空间。字节 0-4095 在页面 0 中，字节 4096-8191 在页面 1 中，依次类推。VMA 的大小 必须是页面大小的倍数 。下图是使用 4KB 大小页面的总数量为 3GB 的用户空间：处理器通过查看页面表去转换一个虚拟内存地址到一个真实的物理内存地址。每个进程都有它自己的一组页面表；每当发生进程切换时，用户空间的页面表也同时切换。Linux 在内存描述符的 pgd 域中保存了一个指向进程的页面表的指针。对于每个虚拟页面，页面表中都有一个相应的页面表条目（PTE），在常规的 x86 页面表中，它是一个简单的如下所示的大小为 4 字节的记录：Linux 通过函数去 读取 和 设置 PTE 条目中的每个标志位。标志位 P 告诉处理器这个虚拟页面是否在物理内存中。如果该位被清除（设置为 0），访问这个页面将触发一个页面故障。请记住，当这个标志位为 0 时，内核可以在剩余的域上做任何想做的事。R/W 标志位是读/写标志；如果被清除，这个页面将变成只读的。U/S 标志位表示用户/超级用户；如果被清除，这个页面将仅被内核访问。这些标志都是用于实现我们在前面看到的只读内存和内核空间保护。标志位 D 和 A 用于标识页面是否是“脏的”或者是已被访问过。一个脏页面表示已经被写入，而一个被访问过的页面则表示有一个写入或者读取发生过。这两个标志位都是粘滞位：处理器只能设置它们，而清除则是由内核来完成的。最终，PTE 保存了这个页面相应的起始物理地址，它们按 4KB 进行整齐排列。这个看起来不起眼的域是一些痛苦的根源，因为它限制了物理内存最大为 4 GB。其它的 PTE 域留到下次再讲，因为它是涉及了物理地址扩展的知识。由于在一个虚拟页面上的所有字节都共享一个 U/S 和 R/W 标志位，所以内存保护的最小单元是一个虚拟页面。但是，同一个物理内存可能被映射到不同的虚拟页面，这样就有可能会出现相同的物理内存出现不同的保护标志位的情况。请注意，在 PTE 中是看不到运行权限的。这就是为什么经典的 x86 页面上允许代码在栈上被执行的原因，这样会很容易导致挖掘出栈缓冲溢出漏洞（可能会通过使用 return-to-libc 和其它技术来找出非可执行栈）。由于 PTE 缺少禁止运行标志位说明了一个更广泛的事实：在 VMA 中的权限标志位有可能或可能不完全转换为硬件保护。内核只能做…

当 CPU 空闲时它都在做什么？
type: item
date: 2018-02-02T04:52:00+08:00
description: 在 上篇文章中 我说了操作系统行为的基本原理是，在任何一个给定的时刻，在一个 CPU 上有且只有一个任务是活动的。但是，如果 CPU 无事可做的时候，又会是什么样的呢？事实证明，这种情况是非常普遍的，对于绝大多数的个人电脑来说，这确实是一种常态：大量的睡眠进程，它们都在等待某种情况下被唤醒，差不多在 100% 的 CPU 时间中，都处于虚构的“空闲任务”中。事实上，如果一个普通用户的 CPU 处于持续的繁忙中，它可能意味着有一个错误、bug、或者运行了恶意软件。因为我们不能违反我们的原理，一些任务需要在一个 CPU 上激活。首先是因为，这是一个良好的设计：持续很长时间去遍历内核，检查是否有一个活动任务，这种特殊情况是不明智的做法。最好的设计是没有任何例外的情况。无论何时，你写一个 if 语句，Nyan Cat 就会喵喵喵。其次，我们需要使用空闲的 CPU 去做一些事情，让它们充满活力，你懂得，就是创建天网计划呗。因此，保持这种设计的连续性，并领先于那些邪恶计划一步，操作系统开发者创建了一个空闲任务，当没有其它任务可做时就调度它去运行。我们可以在 Linux 的 引导过程 中看到，这个空闲任务就是进程 0，它是由计算机打开电源时运行的第一个指令直接派生出来的。它在 rest\_init 中初始化，在 init\_idle\_bootup\_task 中初始化空闲 调度类 scheduling class 。简而言之，Linux 支持像实时进程、普通用户进程等等的不同调度类。当选择一个进程变成活动任务时，这些类按优先级进行查询。通过这种方式，核反应堆的控制代码总是优先于 web 浏览器运行。尽管在通常情况下，这些类返回 NULL，意味着它们没有合适的任务需要去运行 —— 它们总是处于睡眠状态。但是空闲调度类，它是持续运行的，从不会失败：它总是返回空闲任务。好吧，我们来看一下这个空闲任务到底做了些什么。下面是 cpu\_idle\_loop，感谢开源能让我们看到它的代码：while (1) { while(!need_resched()) { cpuidle_idle_call(); } /* [Note: Switch to a different task. We will return to this loop when the idle task is again selected to run.] */ schedule_preempt_disabled(); } cpu\_idle\_loop我省略了很多的细节，稍后我们将去了解任务切换，但是，如果你阅读了这些源代码，你就会找到它的要点：由于这里不需要重新调度（即改变活动任务），它一直处于空闲状态。以所经历的时间来计算，这个循环和其它操作系统中它的“堂兄弟们”相比，在计算的历史上它是运行的最多的代码片段。对于 Intel 处理器来说，处于空闲状态意味着运行着一个 halt 指令：static inline void native_halt(void) { asm volatile("hlt": : :"memory"); } native\_halthlt 指令停止处理器中的代码执行，并将它置于 halt 的状态。奇怪的是，全世界各地数以百万计的 Intel 类的 CPU 们花费大量的时间让它们处于 halt 的状态，甚至它们在通电的时候也是如此。这并不是高效、节能的做法，这促使芯片制造商们去开发处理器的深度睡眠状态，以带来着更少的功耗和更长休眠时间。内核的 cpuidle 子系统 是这些节能模式能够产生好处的原因。现在，一旦我们告诉 CPU 去 halt（睡眠）之后，我们需要以某种方式让它醒来。如果你读过 上篇文章《你的操作系统什么时候运行？》 ，你可能会猜到中断会参与其中，而事实确实如此。中断促使 CPU 离开 halt 状态返回到激活状态。因此，将这些拼到一起，下图是当你阅读一个完全呈现的 web 网页时，你的系统主要做的事情：除定时器中断外的其它中断也会使处理器再次发生变化。如果你再次点击一个 web 页面就会产生这种变化，例如：你的鼠标发出一个中断，它的驱动会处理它，并且因为它产生了一个新的输入，突然进程就可运行了。在那个时刻， need_resched() 返回 true，然后空闲任务因你的浏览器而被踢出而终止运行。如果我们呆呆地看着这篇文章，而不做任何事情。那么随着时间的推移，这个空闲循环就像下图一样：在这个示例中，由内核计划的定时器中断会每 4 毫秒发生一次。这就是 滴答 tick 周期。也就是说每秒钟将有 250 个滴答，因此，这个滴答速率（频率）是 250 Hz。这是运行在 Intel 处理器上的 Linux 的典型值，而其它操作系统喜欢使用 100 …

剖析内存中的程序之秘
type: item
date: 2018-01-19T02:49:41+08:00
description: 内存管理是操作系统的核心任务；它对程序员和系统管理员来说也是至关重要的。在接下来的几篇文章中，我将从实践出发着眼于内存管理，并深入到它的内部结构。虽然这些概念很通用，但示例大都来自于 32 位 x86 架构的 Linux 和 Windows 上。这第一篇文章描述了在内存中程序如何分布。在一个多任务操作系统中的每个进程都运行在它自己的内存“沙箱”中。这个沙箱是一个 虚拟地址空间 virtual address space ，在 32 位的模式中它总共有 4GB 的内存地址块。这些虚拟地址是通过内核 页表 page table 映射到物理地址的，并且这些虚拟地址是由操作系统内核来维护，进而被进程所消费的。每个进程都有它自己的一组页表，但是这里有点玄机。一旦虚拟地址被启用，这些虚拟地址将被应用到这台电脑上的 所有软件，包括内核本身。因此，一部分虚拟地址空间必须保留给内核使用：但是，这并不是说内核就使用了很多的物理内存，恰恰相反，它只使用了很少一部分可用的地址空间映射到其所需要的物理内存。内核空间在内核页表中被标记为独占使用于 特权代码 （ring 2 或更低），因此，如果一个用户模式的程序尝试去访问它，将触发一个页面故障错误。在 Linux 中，内核空间是始终存在的，并且在所有进程中都映射相同的物理内存。内核代码和数据总是可寻址的，准备随时去处理中断或者系统调用。相比之下，用户模式中的地址空间，在每次进程切换时都会发生变化：蓝色的区域代表映射到物理地址的虚拟地址空间，白色的区域是尚未映射的部分。在上面的示例中，众所周知的内存“饕餮” Firefox 使用了大量的虚拟内存空间。在地址空间中不同的条带对应了不同的内存段，像 堆 heap 、 栈 stack 等等。请注意，这些段只是一系列内存地址的简化表示，它与 Intel 类型的段 并没有任何关系 。不过，这是一个在 Linux 进程的标准段布局：当计算机还是快乐、安全的时代时，在机器中的几乎每个进程上，那些段的起始虚拟地址都是完全相同的。这将使远程挖掘安全漏洞变得容易。漏洞利用经常需要去引用绝对内存位置：比如在栈中的一个地址，一个库函数的地址，等等。远程攻击可以闭着眼睛选择这个地址，因为地址空间都是相同的。当攻击者们这样做的时候，人们就会受到伤害。因此，地址空间随机化开始流行起来。Linux 会通过在其起始地址上增加偏移量来随机化栈、内存映射段、以及堆。不幸的是，32 位的地址空间是非常拥挤的，为地址空间随机化留下的空间不多，因此 妨碍了地址空间随机化的效果。在进程地址空间中最高的段是栈，在大多数编程语言中它存储本地变量和函数参数。调用一个方法或者函数将推送一个新的 栈帧 stack frame 到这个栈。当函数返回时这个栈帧被删除。这个简单的设计，可能是因为数据严格遵循 后进先出（LIFO） 的次序，这意味着跟踪栈内容时不需要复杂的数据结构 —— 一个指向栈顶的简单指针就可以做到。推入和弹出也因此而非常快且准确。也可能是，持续的栈区重用往往会在 CPU 缓存 中保持活跃的栈内存，这样可以加快访问速度。进程中的每个线程都有它自己的栈。向栈中推送更多的而不是刚合适的数据可能会耗尽栈的映射区域。这将触发一个页面故障，在 Linux 中它是通过 expand_stack() 来处理的，它会去调用 acct_stack_growth() 来检查栈的增长是否正常。如果栈的大小低于 RLIMIT_STACK 的值（一般是 8MB 大小），那么这是一个正常的栈增长和程序的合理使用，否则可能是发生了未知问题。这是一个栈大小按需调节的常见机制。但是，栈的大小达到了上述限制，将会发生一个栈溢出，并且，程序将会收到一个 段故障 Segmentation Fault 错误。当映射的栈区为满足需要而扩展后，在栈缩小时，映射区域并不会收缩。就像美国联邦政府的预算一样，它只会扩张。动态栈增长是 唯一例外的情况 ，当它去访问一个未映射的内存区域，如上图中白色部分，是允许的。除此之外的任何其它访问未映射的内存区域将触发一个页面故障，导致段故障。一些映射区域是只读的，因此，尝试去写入到这些区域也将触发一个段故障。在栈的下面，有内存映射段。在这里，内核将文件内容直接映射到内存。任何应用程序都可以通过 Linux 的 mmap() 系统调用（ 代码实现）或者 Windows 的 CreateFileMapping().aspx) / MapViewOfFile().aspx) 来请求一个映射。内存映射是实现文件 I/O 的方便高效的方式。因此，它经常被用于加载动态库。有时候，也被用于去创建一个并不匹配任何文件的匿名内存映射，这种映射经常被用做程序数据的替代。在 Linux 中，如果你通过 malloc() 去请求一个大的内…