在上篇文章中我们提到了闭包、对象、以及栈外的其它东西。我们学习的大部分内容都是与特定编程语言无关的元素，但是，我主要还是专注于 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 内部它们所引用的内容是明确的。尽管词法域是一个很好的术语，它符合我们直观上的理解：毕竟，我们从字面意义上看，我们可以像词法分析器一样，把它看作在源代码中的一个文本块。在看到栈帧的操作之后，很容易想像出这个名称的具体实现。在 add 内部，这些名字引用到函数的每个运行实例中私有的栈的位置。这种情况在一个虚拟机中经常发生。现在，我们来嵌套两个词法域：function makeGreeter() { return function hi(name){ console.log('hi, ' + name); } } var hi = makeGreeter(); hi('dear reader'); // prints "hi, dear reader" 那样更有趣。函数 hi 在函数 makeGreeter 运行的时候被构建在它内部。它有它自己的词法域，name 在这个地方是一个栈上的参数，但是，它似乎也可以访问父级的词法域，它可以那样做。我们来看一下那样做的好处：function makeGreeter(greeting) { return function greet(name){ console.log(greeting + ', ' + name); } } var heya = makeGreeter('HEYA'); heya('dear reader'); // prints "HEYA, dear reader" 虽然有点不习惯，但是很酷。即便这样违背了我们的直觉：greeting 确实看起来像一个栈变量，这种类型应该在 makeGreeter() 返回后消失。可是因为 greet() 一直保持工作，出现了一些奇怪的事情。进入闭包（LCTT 译注：“Context” 和 “JSFunction” 映射分别链接至 #188 行和 #7245 行）：虚拟机分配一个对象去保存被里面的 greet() 使用的父级变量。它就好像是 makeGreeter 的词法作用域在那个时刻被 关闭 closed over 了，一旦需要时被具体化到一个堆对象（在这个案例中，是指返回的函数的生命周期）。因此叫做 闭包 closure ，当你这样去想它的时候，它的名字就有意义了。如果使用（或者捕获）了更多的父级变量，对象内容将有更多的属性，每个捕获的变量有一个。当然，发送到 greet() 的代码知道从对象内容中去读取问候语，而不是从栈上。这是完整的示例：function makeGreeter(greetings) { var count = 0; var greeter = {}; for (var i = 0; i < greetings.length; i++) { var greeting = greetings[i]; greeter[greeting] = function(name){ count++; console.log(greeting + ', ' + name); } } greeter.count = function(){return count;} return greeter; } var greeter = makeGreeter(["hi", "hello","howdy"]) greeter.hi('poppet');//prints "howdy, poppet" greeter.hello('darling');// prints "howdy, darling" greeter.count(); // returns 2 是的，count() 在工作，但是我们的 greeter 是在 howdy 中的栈上。你能告诉我为什么吗？我们使用 count 是一条线索：尽管词法域进入一个堆对象中被关闭，但是变量（或者对象属性）带的值仍然可能被改变。下图是我们拥有的内容（LCTT 译注：映射从左到右“Object”、“JSFunction”和“Context”分别链接至 #1671 行、#7245 行和 #188 行）：这是一个被所有函数共享的公共内容。那就是为什么 count 工作的原因。但是，greeting 也是被共享的，并且它被设置为迭代结束后的最后一个值，在这个案例中是 “howdy”。这是一个很常见的一般错误，避免它的简单方法是，引用一个函数调用，以闭包变量作为一个参数。在 CoffeeScript 中， do 命令提供了一个实现这种目的的简单方式。下面是对我们的 greeter 的一个简单的解决方案：function makeGreeter(greetings) { var count = 0; var greeter = {}; greetings.forEach(function(greeting){ greeter[greeting] = function(name){ count++; console.log(greeting + ', ' + name); } }); greeter.count = function(){return count;} return greeter; } var greeter = makeGreeter(["hi", "hello", "howdy"]) greeter.hi('poppet'); // prints "hi, poppet" greeter.hello('darling'); // prints "hello, darling" greeter.count(); // returns 2 它现在是工作的，并且结果将变成下图所示（LCTT 译注：映射从左到右“Object”、“JSFunction”和“Context”分别链接至 #1671 行、#7245 行和 #188 行）：这里有许多箭头！在这里我们感兴趣的特性是：在我们的代码中，我们闭包了两个嵌套的词法内容，并且完全可以确保我们得到了两个链接到堆上的对象内容。你可以嵌套并且闭包任何词法内容，像“俄罗斯套娃”似的，并且最终从本质上说你使用的是所有那些 Context 对象的一个链表。当然，就像受信鸽携带信息启发实现了 TCP 一样，去实现这些编程语言的特性也有很多种方法。例如，ES6 规范定义了 词法环境 作为 环境记录( 大致相当于在一个块内的本地标识）的组成部分，加上一个链接到外部环境的记录，这样就允许我们看到的嵌套。逻辑规则是由规范（一个希望）所确定的，但是其实现取决于将它们变成比特和字节的转换。你也可以检查具体案例中由 V8 产生的汇编代码。Vyacheslav Egorov 有一篇很好的文章，它使用 V8 的 闭包内部构件 详细解释了这一过程。我刚开始学习 V8，因此，欢迎指教。如果你熟悉 C#，检查闭包产生的中间代码将会很受启发 —— 你将看到显式定义的 V8 内容和实例化的模拟。闭包是个强大的“家伙”。它在被一组函数共享期间，提供了一个简单的方式去隐藏来自调用者的信息。我喜欢它们真正地隐藏你的数据：不像对象字段，调用者并不能访问或者甚至是看到闭包变量。保持接口清晰而安全。但是，它们并不是“银弹”（LCTT 译注：意指极为有效的解决方案，或者寄予厚望的新技术）。有时候一个对象的拥护者和一个闭包的狂热者会无休止地争论它们的优点。就像大多数的技术讨论一样，他们通常更关注的是自尊而不是真正的权衡。不管怎样，Anton van Straaten 的这篇 史诗级的公案 解决了这个问题：德高望重的老师 Qc Na 和它的学生 Anton 一起散步。Anton 希望将老师引入到一个讨论中，Anton 说：“老师，我听说对象是一个非常好的东西，是这样的吗？Qc Na 同情地看了一眼，责备它的学生说：“可怜的孩子 —— 对象不过是穷人的闭包而已。” Anton 待它的老师走了之后，回到他的房间，专心学习闭包。他认真地阅读了完整的 “Lambda：The Ultimate…" 系列文章和它的相关资料，并使用一个基于闭包的对象系统实现了一个小的架构解释器。他学到了很多的东西，并期待告诉老师他的进步。在又一次和 Qc Na 散步时，Anton 尝试给老师留下一个好的印象，说“老师，我仔细研究了这个问题，并且，现在理解了对象真的是穷人的闭包。”Qc Na 用它的手杖打了一下 Anton 说：“你什么时候才能明白？闭包是穷人的对象。”在那个时候，Anton 顿悟了。Anton van Straaten 说：“原来架构这么酷啊？”探秘“栈”系列文章到此结束了。后面我将计划去写一些其它的编程语言实现的主题，像对象绑定和虚表。但是，内核调用是很强大的，因此，明天将发布一篇操作系统的文章。我邀请你 订阅 并 关注我。via:https://manybutfinite.com/post/closures-objects-heap/作者：Gustavo Duarte 译者：qhwdw 校对：wxy本文由 LCTT 原创编译，Linux中国 荣誉推出
在探秘“栈”的倒数第二篇文章中，我们提到了 尾调用 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) { return getpid(); // tail } return n * pidFactorial(n-1) * getpid(); // not tail } int main(int argc) { int answer = pidFactorial(5); printf("%d\n", answer); } 递归 PID 阶乘 下载优化它，unix 精灵！现在，我们有了一个常规的 递归调用 并且这个函数分配 O(n) 栈帧来完成工作。GCC 在递归的基础上仍然 为 getpid 使用了 TCO。如果我们现在希望让这个函数尾调用递归，我需要稍微变一下：#include <stdio.h> #include <sys/types.h> #include <unistd.h> int tailPidFactorial(int n, int acc) { if (1 == n) { return acc * getpid(); // not tail } acc = (acc * getpid() * n); return tailPidFactorial(n-1, acc); // tail } int main(int argc) { int answer = tailPidFactorial(5, 1); printf("%d\n", answer); } tailPidFactorial.c 下载现在，结果的累加是 一个循环，并且我们获得了真实的 TCO。但是，在你庆祝之前，我们能说一下关于在 C 中的一般情形吗？不幸的是，虽然优秀的 C 编译器在大多数情况下都可以实现 TCO，但是，在一些情况下它们仍然做不到。例如，正如我们在 函数序言 中所看到的那样，函数调用者在使用一个标准的 C 调用规则调用一个函数之后，它要负责去清理栈。因此，如果函数 F 带了两个参数，它只能使 TCO 调用的函数使用两个或者更少的参数。这是 TCO 的众多限制之一。Mark Probst 写了一篇非常好的论文，他们讨论了 在 C 中的合理尾递归，在这篇论文中他们讨论了这些属于 C 栈行为的问题。他也演示一些 疯狂的、很酷的欺骗方法。“有时候” 对于任何一种关系来说都是不坚定的，因此，在 C 中你不能依赖 TCO。它是一个在某些地方可以或者某些地方不可以的离散型优化，而不是像合理尾调用一样的编程语言的特性，虽然在实践中可以使用编译器来优化绝大部分的情形。但是，如果你想必须要实现 TCO，比如将 Scheme 转译 transpilation 成 C，你将会 很痛苦。因为 JavaScript 现在是非常流行的转译对象，合理尾调用比以往更重要。因此，对 ES6 及其提供的许多其它的重大改进的赞誉并不为过。它就像 JS 程序员的圣诞节一样。这就是尾调用和编译优化的简短结论。感谢你的阅读，下次再见！via:https://manybutfinite.com/post/tail-calls-optimization-es6/作者：Gustavo Duarte 译者：qhwdw 校对：wxy本文由 LCTT 原创编译，Linux中国 荣誉推出
探秘“栈”之旅（II）：结语、金丝雀和缓冲区溢出
上一周我们讲解了 栈是如何工作的 以及在函数的 序言 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 的话解释如下：计算机科学拥有比其它任何领域都丰富多彩的语言，在其它的领域中你进入一个无菌室，小心地将温度控制在 68°F，然后，能找到病毒、特洛伊木马、蠕虫、臭虫（bug）、炸弹（逻辑炸弹）、崩溃、爆发（口水战）、扭曲的变性者（双绞线转换头），以及致命错误吗？—— Steve McConnell 《代码大全 2》不管怎么说，这里所谓的“栈金丝雀”应该看起来是这个样子的：金丝雀是通过汇编来实现的。例如，由于 GCC 的 栈保护器 选项的原因使金丝雀能被用于任何可能有漏洞的函数上。函数序言加载一个魔法值到金丝雀的位置，并且在函数结语时确保这个值完好无损。如果这个值发生了变化，那就表示发生了一个缓冲区溢出（或者 bug），这时，程序通过 __stack_chk_fail 被终止运行。由于金丝雀处于栈的关键位置上，它使得栈缓冲区溢出的漏洞挖掘变得非常困难。深入栈的探秘之旅结束了。我并不想过于深入。下一周我将深入递归、尾调用以及其它相关内容。或许要用到谷歌的 V8 引擎。作为函数的序言和结语的讨论的结束，我引述了美国国家档案馆纪念雕像上的一句名言：（ 凡是过去 皆为序章 what is past is prologue ）。via:https://manybutfinite.com/post/epilogues-canaries-buffer-overflows/作者：Gustavo Duarte 译者：qhwdw 校对：wxy本文由 LCTT 原创编译，Linux中国 荣誉推出
早些时候，我们探索了 “内存中的程序之秘”，我们欣赏了在一台电脑中是如何运行我们的程序的。今天，我们去探索栈的调用，它在大多数编程语言和虚拟机中都默默地存在。在此过程中，我们将接触到一些平时很难见到的东西，像 闭包 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 在第二个字节的位置有一个值 2，因此，它的数学上的值是 2 * 256 = 512（我们与 256 相乘是因为，每个位置值的范围都是从 0 到 255）。同时，param2 承载的数量是 1 * 256 * 256 = 65536。这个栈帧的内部数据是由两个重要的部分组成：前一个栈帧的地址（保存的 ebp 值）和函数退出才会运行的指令的地址（返回地址）。它们一起确保了函数能够正常返回，从而使程序可以继续正常运行。现在，我们来看一下栈帧是如何产生的，以及去建立一个它们如何共同工作的内部蓝图。首先，栈的增长是非常令人困惑的，因为它与你你预期的方式相反。例如，在栈上分配一个 8 字节，就要从 esp 减去 8，去，而减法是与增长不同的奇怪方式。我们来看一个简单的 C 程序：Simple Add Program - 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假设我们在 Linux 中不使用命令行参数去运行它。当你运行一个 C 程序时，实际运行的第一行代码是在 C 运行时库里，由它来调用我们的 main 函数。下图展示了程序运行时每一步都发生了什么。每个图链接的 GDB 输出展示了内存和寄存器的状态。你也可以看到所使用的 GDB 命令，以及整个 GDB 输出。如下：第 2 步和第 3 步，以及下面的第 4 步，都只是函数的 序言 prologue ，几乎所有的函数都是这样的：ebp 的当前值被保存到了栈的顶部，然后，将 esp 的内容拷贝到 ebp，以建立一个新的栈帧。main 的序言和其它函数一样，但是，不同之处在于，当程序启动时 ebp 被清零。如果你去检查栈下方（右边）的整形变量（argc），你将找到更多的数据，包括指向到程序名和命令行参数（传统的 C 的 argv）、以及指向 Unix 环境变量以及它们真实的内容的指针。但是，在这里这些并不是重点，因此，继续向前调用 add()：在 main 从 esp 减去 12 之后得到它所需的栈空间，它为 a 和 b 设置值。在内存中的值展示为十六进制，并且是小端格式，与你从调试器中看到的一样。一旦设置了参数值，main 将调用 add，并且开始运行：现在，有一点小激动！我们进入了另一个函数序言，但这次你可以明确看到栈帧是如何从 ebp 到栈建立一个链表。这就是调试器和高级语言中的 Exception 对象如何对它们的栈进行跟踪的。当一个新帧产生时，你也可以看到更多这种典型的从 ebp 到 esp 的捕获。我们再次从 esp 中做减法得到更多的栈空间。当 ebp 寄存器的值拷贝到内存时，这里也有一个稍微有些怪异的字节逆转。在这里发生的奇怪事情是，寄存器其实并没有字节顺序：因为对于内存，没有像寄存器那样的“增长的地址”。因此，惯例上调试器以对人类来说最自然的格式展示了寄存器的值：数位从最重要的到最不重要。因此，这个在小端机器中的副本的结果，与内存中常用的从左到右的标记法正好相反。我想用图去展示你将会看到的东西，因此有了下面的图。在比较难懂的部分，我们增加了注释：这是一个临时寄存器，用于帮你做加法，因此没有什么警报或者惊喜。对于加法这样的作业，栈的动作正好相反，我们留到下次再讲。对于任何读到这里的人都应该有一个小礼物，因此，我做了一个大的图表展示了 组合到一起的所有步骤。一旦把它们全部布置好了，看上起似乎很乏味。这些小方框给我们提供了很多帮助。事实上，在计算机科学中，这些小方框是主要的展示工具。我希望这些图片和寄存器的移动能够提供一种更直观的构想图，将栈的增长和内存的内容整合到一起。从软件的底层运作来看，我们的软件与一个简单的图灵机器差不多。这就是我们栈探秘的第一部分，再讲一些内容之后，我们将看到构建在这个基础上的高级编程的概念。下周见！via:https://manybutfinite.com/post/journey-to-the-stack/作者：Gustavo Duarte 译者：qhwdw 校对：wxy本文由 LCTT 原创编译，Linux中国 荣誉推出
我其实不想将它分解开给你看，用户应用程序其实就是一个可怜的 瓮中大脑 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 */]) = 0 brk(0) = 0x9aa0000 access("/etc/ld.so.nohwcap", F_OK) = -1 ENOENT (No such file or directory) mmap2(NULL, 8192, PROT_READ|PROT_WRITE, MAP_PRIVATE|MAP_ANONYMOUS, -1, 0) = 0xb7767000 access("/etc/ld.so.preload", R_OK) = -1 ENOENT (No such file or directory) open("/etc/ld.so.cache", O_RDONLY|O_CLOEXEC) = 3 fstat64(3, {st_mode=S_IFREG|0644, st_size=18056, ...}) = 0 mmap2(NULL, 18056, PROT_READ, MAP_PRIVATE, 3, 0) = 0xb7762000 close(3) = 0 [...snip...] getpid() = 14678 fstat64(1, {st_mode=S_IFCHR|0600, st_rdev=makedev(136, 1), ...}) = 0 mmap2(NULL, 4096, PROT_READ|PROT_WRITE, MAP_PRIVATE|MAP_ANONYMOUS, -1, 0) = 0xb7766000 write(1, "14678\n", 614678 ) = 6 exit_group(6) = ? 输出的每一行都显示了一个系统调用、它的参数，以及返回值。如果你在一个循环中将 getpid(2) 运行 1000 次，你就会发现始终只有一个 getpid() 系统调用，因为，它的 PID 已经被缓存了。我们也可以看到在格式化输出字符串之后，printf(3) 调用了 write(2)。strace 可以开始一个新进程，也可以附加到一个已经运行的进程上。你可以通过不同程序的系统调用学到很多的东西。例如，sshd 守护进程一天都在干什么？~/code/x86-os$ ps ax | grep sshd 12218 ? Ss 0:00 /usr/sbin/sshd -D ~/code/x86-os$ sudo strace -p 12218 Process 12218 attached - interrupt to quit select(7, [3 4], NULL, NULL, NULL [ ... nothing happens ... No fun, it's just waiting for a connection using select(2) If we wait long enough, we might see new keys being generated and so on, but let's attach again, tell strace to follow forks (-f), and connect via SSH ] ~/code/x86-os$ sudo strace -p 12218 -f [lots of calls happen during an SSH login, only a few shown] [pid 14692] read(3, "-----BEGIN RSA PRIVATE KEY-----\n"..., 1024) = 1024 [pid 14692] open("/usr/share/ssh/blacklist.RSA-2048", O_RDONLY|O_LARGEFILE) = -1 ENOENT (No such file or directory) [pid 14692] open("/etc/ssh/blacklist.RSA-2048", O_RDONLY|O_LARGEFILE) = -1 ENOENT (No such file or directory) [pid 14692] open("/etc/ssh/ssh_host_dsa_key", O_RDONLY|O_LARGEFILE) = 3 [pid 14692] open("/etc/protocols", O_RDONLY|O_CLOEXEC) = 4 [pid 14692] read(4, "# Internet (IP) protocols\n#\n# Up"..., 4096) = 2933 [pid 14692] open("/etc/hosts.allow", O_RDONLY) = 4 [pid 14692] open("/lib/i386-linux-gnu/libnss_dns.so.2", O_RDONLY|O_CLOEXEC) = 4 [pid 14692] stat64("/etc/pam.d", {st_mode=S_IFDIR|0755, st_size=4096, ...}) = 0 [pid 14692] open("/etc/pam.d/common-password", O_RDONLY|O_LARGEFILE) = 8 [pid 14692] open("/etc/pam.d/other", O_RDONLY|O_LARGEFILE) = 4 看懂 SSH 的调用是块难啃的骨头，但是，如果搞懂它你就学会了跟踪。能够看到应用程序打开的是哪个文件是有用的（“这个配置是从哪里来的？”）。如果你有一个出现错误的进程，你可以 strace 它，然后去看它通过系统调用做了什么？当一些应用程序意外退出而没有提供适当的错误信息时，你可以去检查它是否有系统调用失败。你也可以使用过滤器，查看每个调用的次数，等等：~/code/x86-os$ strace -T -e trace=recv curl -silent www.google.com. > /dev/null recv(3, "HTTP/1.1 200 OK Date: Wed, 05 N"..., 16384, 0) = 4164 <0.000007> recv(3, "fl a{color:#36c}a:visited{color:"..., 16384, 0) = 2776 <0.000005> recv(3, "adient(top,#4d90fe,#4787ed);filt"..., 16384, 0) = 4164 <0.000007> recv(3, "gbar.up.spd(b,d,1,!0);break;case"..., 16384, 0) = 2776 <0.000006> recv(3, "$),a.i.G(!0)),window.gbar.up.sl("..., 16384, 0) = 1388 <0.000004> recv(3, "margin:0;padding:5px 8px 0 6px;v"..., 16384, 0) = 1388 <0.000007> recv(3, "){window.setTimeout(function(){v"..., 16384, 0) = 1484 <0.000006> 我鼓励你在你的操作系统中的试验这些工具。把它们用好会让你觉得自己有超能力。但是，足够有用的东西，往往要让我们深入到它的设计中。我们可以看到那些用户空间中的应用程序是被严格限制在它自己的虚拟地址空间里，运行在 Ring 3（非特权模式）中。一般来说，只涉及到计算和内存访问的任务是不需要请求系统调用的。例如，像 strlen(3) 和 memcpy(3) 这样的 C 库函数并不需要内核去做什么。这些都是在应用程序内部发生的事。C 库函数的 man 页面所在的节（即圆括号里的 2 和 3）也提供了线索。节 2 是用于系统调用封装，而节 3 包含了其它 C 库函数。但是，正如我们在 printf(3) 中所看到的，库函数最终可以产生一个或者多个系统调用。如果你对此感到好奇，这里是 Linux （也有 Filippo 的列表）和 Windows 的全部系统调用列表。它们各自有大约 310 和 460 个系统调用。看这些系统调用是非常有趣的，因为，它们代表了软件在现代的计算机上能够做什么。另外，你还可能在这里找到与进程间通讯和性能相关的“宝藏”。这是一个“不懂 Unix 的人注定最终还要重新发明一个蹩脚的 Unix ” 的地方。（LCTT 译注：原文 “Those who do not understand Unix are condemned to reinvent it，poorly。” 这句话是 Henry Spencer 的名言，反映了 Unix 的设计哲学，它的一些理念和文化是一种技术发展的必须结果，看似糟糕却无法超越。）与 CPU 周期相比，许多系统调用花很长的时间去执行任务，例如，从一个硬盘驱动器中读取内容。在这种情况下，调用进程在底层的工作完成之前一直处于休眠状态。因为，CPU 运行的非常快，一般的程序都因为 I/O 的限制在它的生命周期的大部分时间处于休眠状态，等待系统调用返回。相反，如果你跟踪一个计算密集型任务，你经常会看到没有任何的系统调用参与其中。在这种情况下，top(1) 将显示大量的 CPU 使用。在一个系统调用中的开销可能会是一个问题。例如，固态硬盘比普通硬盘要快很多，但是，操作系统的开销可能比 I/O 操作本身的开销 更加昂贵。执行大量读写操作的程序可能就是操作系统开销的瓶颈所在。向量化 I/O 对此有一些帮助。因此要做 文件的内存映射，它允许一个程序仅访问内存就可以读或写磁盘文件。类似的映射也存在于像视频卡这样的地方。最终，云计算的经济性可能导致内核消除或最小化用户模式/内核模式的切换。最终，系统调用还有益于系统安全。一是，无论如何来历不明的一个二进制程序，你都可以通过观察它的系统调用来检查它的行为。这种方式可能用于去检测恶意程序。例如，我们可以记录一个未知程序的系统调用的策略，并对它的异常行为进行报警，或者对程序调用指定一个白名单，这样就可以让漏洞利用变得更加困难。在这个领域，我们有大量的研究，和许多工具，但是没有“杀手级”的解决方案。这就是系统调用。很抱歉这篇文章有点长，我希望它对你有用。接下来的时间，我将写更多（短的）文章，也可以在 RSS 和 Twitter 关注我。这篇文章献给 glorious Clube Atlético Mineiro。via:https://manybutfinite.com/post/system-calls/作者：Gustavo Duarte 译者：qhwdw 校对：wxy本文由 LCTT 原创编译，Linux中国 荣誉推出
“方其梦也，不知其梦也。梦之中又占其梦焉，觉而后知其梦也。”—— 《庄子·齐物论》递归是很神奇的，但是在大多数的编程类书藉中对递归讲解的并不好。它们只是给你展示一个递归阶乘的实现，然后警告你递归运行的很慢，并且还有可能因为栈缓冲区溢出而崩溃。“你可以将头伸进微波炉中去烘干你的头发，但是需要警惕颅内高压并让你的头发生爆炸，或者你可以使用毛巾来擦干头发。”难怪人们不愿意使用递归。但这种建议是很糟糕的，因为在算法中，递归是一个非常强大的思想。我们来看一下这个经典的递归阶乘：#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 输出 中看到更详细的数据，它是使用 命令 采集的数据。它展示了递归的良好表现，因为这是一个适合使用递归的问题。而且这并不奇怪：当涉及到算法时，递归是规则，而不是例外。它出现在如下情景中——进行搜索时、进行遍历树和其它数据结构时、进行解析时、需要排序时——它无处不在。正如众所周知的 pi 或者 e，它们在数学中像“神”一样的存在，因为它们是宇宙万物的基础，而递归也和它们一样：只是它存在于计算结构中。Steven Skienna 的优秀著作 算法设计指南 的精彩之处在于，他通过 “战争故事” 作为手段来诠释工作，以此来展示解决现实世界中的问题背后的算法。这是我所知道的拓展你的算法知识的最佳资源。另一个读物是 McCarthy 的 关于 LISP 实现的的原创论文。递归在语言中既是它的名字也是它的基本原理。这篇论文既可读又有趣，在工作中能看到大师的作品是件让人兴奋的事情。回到迷宫问题上。虽然它在这里很难离开递归，但是并不意味着必须通过调用栈的方式来实现。你可以使用像 RRLL 这样的字符串去跟踪转向，然后，依据这个字符串去决定老鼠下一步的动作。或者你可以分配一些其它的东西来记录追寻奶酪的整个状态。你仍然是实现了一个递归的过程，只是需要你实现一个自己的数据结构。那样似乎更复杂一些，因为栈调用更合适。每个栈帧记录的不仅是当前节点，也记录那个节点上的计算状态（在这个案例中，我们是否只让它走左边，或者已经尝试向右）。因此，代码已经变得不重要了。然而，有时候我们因为害怕溢出和期望中的性能而放弃这种优秀的算法。那是很愚蠢的！正如我们所见，栈空间是非常大的，在耗尽栈空间之前往往会遇到其它的限制。一方面可以通过检查问题大小来确保它能够被安全地处理。而对 CPU 的担心是由两个广为流传的有问题的示例所导致的： 哑阶乘 dumb factorial 和可怕的无记忆的 O( 2 n ) Fibonacci 递归。它们并不是栈递归算法的正确代表。事实上栈操作是非常快的。通常，栈对数据的偏移是非常准确的，它在 缓存 中是热数据，并且是由专门的指令来操作它的。同时，使用你自己定义的在堆上分配的数据结构的相关开销是很大的。经常能看到人们写的一些比栈调用递归更复杂、性能更差的实现方法。最后，现代的 CPU 的性能都是 非常好的 ，并且一般 CPU 不会是性能瓶颈所在。在考虑牺牲程序的简单性时要特别注意，就像经常考虑程序的性能及性能的测量那样。下一篇文章将是探秘栈系列的最后一篇了，我们将了解尾调用、闭包、以及其它相关概念。然后，我们就该深入我们的老朋友—— Linux 内核了。感谢你的阅读！via:https://manybutfinite.com/post/recursion/作者：Gustavo Duarte 译者：qhwdw 校对：FSSlc本文由 LCTT 原创编译，Linux中国 荣誉推出
页面缓存：内存和文件之间的那些事
上一篇文章中我们学习了内核怎么为一个用户进程 管理虚拟内存，而没有提及文件和 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 内容的页面要立刻释放掉吗？人们通常会如此考虑，但是，那样做并不是个好主意。你应该想到，我们经常在一个程序中创建一个文件，退出程序，然后，在第二个程序去使用这个文件。页面缓存正好可以处理这种情况。如果考虑更多的情况，内核为什么要清除页面缓存的内容？请记住，磁盘读取的速度要慢于内存 5 个数量级，因此，命中一个页面缓存是一件有非常大收益的事情。因此，只要有足够大的物理内存，缓存就应该保持全满。并且，这一原则适用于所有的进程。如果你现在运行 render 一周后， scene.dat 的内容还在缓存中，那么应该恭喜你！这就是什么内核缓存越来越大，直至达到最大限制的原因。它并不是因为操作系统设计的太“垃圾”而浪费你的内存，其实这是一个非常好的行为，因为，释放物理内存才是一种“浪费”。（LCTT 译注：释放物理内存会导致页面缓存被清除，下次运行程序需要的相关数据，需要再次从磁盘上进行读取，会“浪费” CPU 和 I/O 资源）最好的做法是尽可能多的使用缓存。由于页面缓存架构的原因，当程序调用 write() 时，字节只是被简单地拷贝到页面缓存中，并将这个页面标记为“脏”页面。磁盘 I/O 通常并不会立即发生，因此，你的程序并不会被阻塞在等待磁盘写入上。副作用是，如果这时候发生了电脑死机，你的写入将不会完成，因此，对于至关重要的文件，像数据库事务日志，要求必须进行 fsync()（仍然还需要去担心磁盘控制器的缓存失败问题），另一方面，读取将被你的程序阻塞，直到数据可用为止。内核采取预加载的方式来缓解这个矛盾，它一般提前预读取几个页面并将它加载到页面缓存中，以备你后来的读取。在你计划进行一个顺序或者随机读取时（请查看 madvise()、readahead()、Windows 缓存提示.aspx#caching_behavior) ），你可以通过 提示 hint 帮助内核去调整这个预加载行为。Linux 会对内存映射的文件进行 预读取，但是我不确定 Windows 的行为。当然，在 Linux 中它可能会使用 O\_DIRECT 跳过预读取，或者，在 Windows 中使用 NO\_BUFFERING.aspx) 去跳过预读，一些数据库软件就经常这么做。一个文件映射可以是私有的，也可以是共享的。当然，这只是针对内存中内容的更新而言：在一个私有的内存映射上，更新并不会提交到磁盘或者被其它进程可见，然而，共享的内存映射，则正好相反，它的任何更新都会提交到磁盘上，并且对其它的进程可见。内核使用 写时复制 copy on write （CoW）机制，这是通过 页面表条目 page table entry （PTE）来实现这种私有的映射。在下面的例子中，render 和另一个被称为 render3d 的程序都私有映射到 scene.dat 上。然后 render 去写入映射的文件的虚拟内存区域：两个程序私有地映射 scene.dat，内核误导它们并将它们映射到页面缓存，但是使该页面表条目只读。render 试图写入到映射 scene.dat 的虚拟页面，处理器发生页面故障。内核分配页面帧，复制 scene.dat 的第二块内容到其中，并映射故障的页面到新的页面帧。继续执行。程序就当做什么都没发生。上面展示的只读页面表条目并不意味着映射是只读的，它只是内核的一个用于共享物理内存的技巧，直到尽可能的最后一刻之前。你可以认为“私有”一词用的有点不太恰当，你只需要记住，这个“私有”仅用于更新的情况。这种设计的重要性在于，要想看到被映射的文件的变化，其它程序只能读取它的虚拟页面。一旦“写时复制”发生，从其它地方是看不到这种变化的。但是，内核并不能保证这种行为，因为它是在 x86 中实现的，从 API 的角度来看，这是有意义的。相比之下，一个共享的映射只是将它简单地映射到页面缓存上。更新会被所有的进程看到并被写入到磁盘上。最终，如果上面的映射是只读的，页面故障将触发一个内存段失败而不是写到一个副本。动态加载库是通过文件映射融入到你的程序的地址空间中的。这没有什么可奇怪的，它通过普通的 API 为你提供与私有文件映射相同的效果。下面的示例展示了映射文件的 render 程序的两个实例运行的地址空间的一部分，以及物理内存，尝试将我们看到的许多概念综合到一起。这是内存架构系列的第三部分的结论。我希望这个系列文章对你有帮助，对理解操作系统的这些主题提供一个很好的思维模型。via:https://manybutfinite.com/post/page-cache-the-affair-between-memory-and-files/作者：Gustavo Duarte 译者：qhwdw 校对：wxy本文由 LCTT 原创编译，Linux中国 荣誉推出
在学习了进程的 虚拟地址布局 之后，让我们回到内核，来学习它管理用户内存的机制。这里再次使用 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 中的权限标志位有可能或可能不完全转换为硬件保护。内核只能做它能做到的，但是，最终的架构限制了它能做的事情。虚拟内存不保存任何东西，它只是简单地 映射 一个程序的地址空间到底层的物理内存上。物理内存被当作一个称之为物理地址空间的巨大块而由处理器访问。虽然内存的操作涉及到某些总线，我们在这里先忽略它，并假设物理地址范围从 0 到可用的最大值按字节递增。物理地址空间被内核进一步分解为页面帧。处理器并不会关心帧的具体情况，这一点对内核也是至关重要的，因为，页面帧是物理内存管理的最小单元。Linux 和 Windows 在 32 位模式下都使用 4KB 大小的页面帧；下图是一个有 2 GB 内存的机器的例子：在 Linux 上每个页面帧是被一个 描述符 和 几个标志 来跟踪的。通过这些描述符和标志，实现了对机器上整个物理内存的跟踪；每个页面帧的具体状态是公开的。物理内存是通过使用 Buddy 内存分配 （LCTT 译注：一种内存分配算法）技术来管理的，因此，如果一个页面帧可以通过 Buddy 系统分配，那么它是未分配的（free）。一个被分配的页面帧可以是匿名的、持有程序数据的、或者它可能处于页面缓存中、持有数据保存在一个文件或者块设备中。还有其它的异形页面帧，但是这些异形页面帧现在已经不怎么使用了。Windows 有一个类似的页面帧号（Page Frame Number (PFN)）数据库去跟踪物理内存。我们把虚拟内存区域（VMA）、页面表条目（PTE），以及页面帧放在一起来理解它们是如何工作的。下面是一个用户堆的示例：蓝色的矩形框表示在 VMA 范围内的页面，而箭头表示页面表条目映射页面到页面帧。一些缺少箭头的虚拟页面，表示它们对应的 PTE 的当前标志位被清除（置为 0）。这可能是因为这个页面从来没有被使用过，或者是它的内容已经被交换出去了。在这两种情况下，即便这些页面在 VMA 中，访问它们也将导致产生一个页面故障。对于这种 VMA 和页面表的不一致的情况，看上去似乎很奇怪，但是这种情况却经常发生。一个 VMA 像一个在你的程序和内核之间的合约。你请求它做一些事情（分配内存、文件映射、等等），内核会回应“收到”，然后去创建或者更新相应的 VMA。 但是，它 并不立刻 去“兑现”对你的承诺，而是它会等待到发生一个页面故障时才去 真正 做这个工作。内核是个“懒惰的家伙”、“不诚实的人渣”；这就是虚拟内存的基本原理。它适用于大多数的情况，有一些类似情况和有一些意外的情况，但是，它是规则是，VMA 记录 约定的 内容，而 PTE 才反映这个“懒惰的内核” 真正做了什么。通过这两种数据结构共同来管理程序的内存；它们共同来完成解决页面故障、释放内存、从内存中交换出数据、等等。下图是内存分配的一个简单案例：当程序通过 brk() 系统调用来请求一些内存时，内核只是简单地 更新 堆的 VMA 并给程序回复“已搞定”。而在这个时候并没有真正地分配页面帧，并且新的页面也没有映射到物理内存上。一旦程序尝试去访问这个页面时，处理器将发生页面故障，然后调用 do\_page\_fault()。这个函数将使用 find\_vma() 去 搜索 发生页面故障的 VMA。如果找到了，然后在 VMA 上进行权限检查以防范恶意访问（读取或者写入）。如果没有合适的 VMA，也没有所尝试访问的内存的“合约”，将会给进程返回段故障。当找到了一个合适的 VMA，内核必须通过查找 PTE 的内容和 VMA 的类型去处理故障。在我们的案例中，PTE 显示这个页面是 不存在的。事实上，我们的 PTE 是全部空白的（全部都是 0），在 Linux 中这表示虚拟内存还没有被映射。由于这是匿名 VMA，我们有一个完全的 RAM 事务，它必须被 do\_anonymous\_page() 来处理，它分配页面帧，并且用一个 PTE 去映射故障虚拟页面到一个新分配的帧。有时候，事情可能会有所不同。例如，对于被交换出内存的页面的 PTE，在当前（Present）标志位上是 0，但它并不是空白的。而是在交换位置仍有页面内容，它必须从磁盘上读取并且通过 do\_swap\_page() 来加载到一个被称为 major fault 的页面帧上。这是我们通过探查内核的用户内存管理得出的前半部分的结论。在下一篇文章中，我们通过将文件加载到内存中，来构建一个完整的内存框架图，以及对性能的影响。via: http://duartes.org/gustavo/blog/post/how-the-kernel-manages-your-memory/作者：Gustavo Duarte 译者：qhwdw 校对：wxy本文由 LCTT 原创编译，Linux中国 荣誉推出
在 上篇文章中 我说了操作系统行为的基本原理是，在任何一个给定的时刻，在一个 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 Hz。这是由你构建内核时在 CONFIG_HZ 选项中定义的。对于一个空闲 CPU 来说，它看起来似乎是个无意义的工作。如果外部世界没有新的输入，在你的笔记本电脑的电池耗尽之前，CPU 将始终处于这种每秒钟被唤醒 250 次的地狱般折磨的小憩中。如果它运行在一个虚拟机中，那我们正在消耗着宿主机 CPU 的性能和宝贵的时钟周期。在这里的解决方案是 动态滴答，当 CPU 处于空闲状态时，定时器中断被 暂停或重计划，直到内核知道将有事情要做时（例如，一个进程的定时器可能要在 5 秒内过期，因此，我们不能再继续睡眠了），定时器中断才会重新发出。这也被称为无滴答模式。最后，假设在一个系统中你有一个活动进程，例如，一个长时间运行的 CPU 密集型任务。那样几乎就和一个空闲系统是相同的：这些示意图仍然是相同的，只是将空闲任务替换为这个进程，并且相应的描述也是准确的。在那种情况下，每 4 毫秒去中断一次任务仍然是无意义的：它只是操作系统的性能抖动，甚至会使你的工作变得更慢而已。Linux 也可以在这种单一进程的场景中停止这种固定速率的滴答，这被称为 自适应滴答 模式。最终，这种固定速率的滴答可能会 完全消失。对于阅读一篇文章来说，CPU 基本是无事可做的。内核的这种空闲行为是操作系统难题的一个重要部分，并且它与我们看到的其它情况非常相似，因此，这将帮助我们理解一个运行中的内核。via: https://manybutfinite.com/post/what-does-an-idle-cpu-do/作者：Gustavo Duarte 译者：qhwdw 校对：wxy本文由 LCTT 原创编译，Linux中国 荣誉推出
内存管理是操作系统的核心任务；它对程序员和系统管理员来说也是至关重要的。在接下来的几篇文章中，我将从实践出发着眼于内存管理，并深入到它的内部结构。虽然这些概念很通用，但示例大都来自于 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() 去请求一个大的内存块，C 库将会创建这样一个匿名映射而不是使用堆内存。这里所谓的“大”表示是超过了MMAP_THRESHOLD 设置的字节数，它的缺省值是 128 kB，可以通过 mallopt() 去调整这个设置值。接下来讲的是“堆”，就在我们接下来的地址空间中，堆提供运行时内存分配，像栈一样，但又不同于栈的是，它分配的数据生存期要长于分配它的函数。大多数编程语言都为程序提供了堆管理支持。因此，满足内存需要是编程语言运行时和内核共同来做的事情。在 C 中，堆分配的接口是 malloc() 一族，然而在支持垃圾回收的编程语言中，像 C#，这个接口使用 new 关键字。如果在堆中有足够的空间可以满足内存请求，它可以由编程语言运行时来处理内存分配请求，而无需内核参与。否则将通过 brk() 系统调用（代码实现）来扩大堆以满足内存请求所需的大小。堆管理是比较 复杂的，在面对我们程序的混乱分配模式时，它通过复杂的算法，努力在速度和内存使用效率之间取得一种平衡。服务一个堆请求所需要的时间可能是非常可观的。实时系统有一个 特定用途的分配器 去处理这个问题。堆也会出现 碎片化 ，如下图所示：最后，我们抵达了内存的低位段：BSS、数据、以及程序文本。在 C 中，静态（全局）变量的内容都保存在 BSS 和数据中。它们之间的不同之处在于，BSS 保存 未初始化的 静态变量的内容，它的值在源代码中并没有被程序员设置。BSS 内存区域是 匿名 的：它没有映射到任何文件上。如果你在程序中写这样的语句 static int cntActiveUsers，cntActiveUsers 的内容就保存在 BSS 中。反过来，数据段，用于保存在源代码中静态变量 初始化后 的内容。这个内存区域是 非匿名 的。它映射了程序的二进值镜像上的一部分，包含了在源代码中给定初始化值的静态变量内容。因此，如果你在程序中写这样的语句 static int cntWorkerBees = 10，那么，cntWorkerBees 的内容就保存在数据段中，并且初始值为 10。尽管可以通过数据段映射到一个文件，但是这是一个私有内存映射，意味着，如果改变内存，它并不会将这种变化反映到底层的文件上。必须是这样的，否则，分配的全局变量将会改变你磁盘上的二进制文件镜像，这种做法就太不可思议了！用图去展示一个数据段是很困难的，因为它使用一个指针。在那种情况下，指针 gonzo 的内容（一个 4 字节的内存地址）保存在数据段上。然而，它并没有指向一个真实的字符串。而这个字符串存在于文本段中，文本段是只读的，它用于保存你的代码中的类似于字符串常量这样的内容。文本段也会在内存中映射你的二进制文件，但是，如果你的程序写入到这个区域，将会触发一个段故障错误。尽管在 C 中，它比不上从一开始就避免这种指针错误那么有效，但是，这种机制也有助于避免指针错误。这里有一个展示这些段和示例变量的图：你可以通过读取 /proc/pid_of_process/maps 文件来检查 Linux 进程中的内存区域。请记住，一个段可以包含很多的区域。例如，每个内存映射的文件一般都在 mmap 段中的它自己的区域中，而动态库有类似于 BSS 和数据一样的额外的区域。下一篇文章中我们将详细说明“ 区域 area ”的真正含义是什么。此外，有时候人们所说的“ 数据段 data segment ”是指“ 数据 data + BSS + 堆”。你可以使用 nm 和 objdump 命令去检查二进制镜像，去显示它们的符号、地址、段等等。最终，在 Linux 中上面描述的虚拟地址布局是一个“弹性的”布局，这就是这几年来的缺省情况。它假设 RLIMIT_STACK 有一个值。如果没有值的话，Linux 将恢复到如下所示的“经典” 布局：这就是虚拟地址空间布局。接下来的文章将讨论内核如何对这些内存区域保持跟踪、内存映射、文件如何读取和写入、以及内存使用数据的意义。via: http://duartes.org/gustavo/blog/post/anatomy-of-a-program-in-memory/作者：Gustavo Duarte 译者：qhwdw 校对：wxy本文由 LCTT 原创编译，Linux中国 荣誉推出