Gustavo Duarte 发布的文章

在上篇文章中我们提到了闭包、对象、以及栈外的其它东西。我们学习的大部分内容都是与特定编程语言无关的元素,但是,我主要还是专注于 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 行):

乐队名字被读入到相同的内存位置,并且覆盖了前面存储的歌曲名字。bandsong 最终都准确指向到相同点。最后,我们甚至都不能得到 “of Montreal”(LCTT 译注:一个欧美乐队的名字) 的正确输出。你能猜到是为什么吗?

因此,即使栈很有用,但也有很重要的限制。它不能被一个函数用于去存储比该函数的运行周期还要长的数据。你必须将它交给 ,然后与热点缓存、明确的瞬时操作、以及频繁计算的偏移等内容道别。有利的一面是,它是工作 的:

这个代价是你必须记得去 free() 内存,或者由一个垃圾回收机制花费一些性能来随机回收,垃圾回收将去找到未使用的堆对象,然后去回收它们。那就是栈和堆之间在本质上的权衡:性能 vs. 灵活性。

大多数编程语言的虚拟机都有一个中间层用来做一个 C 程序员该做的一些事情。栈被用于值类型,比如,整数、浮点数、以及布尔型。这些都按特定值(像上面的 argc )的字节顺序被直接保存在本地变量和对象字段中。相比之下,堆被用于引用类型,比如,字符串和 对象。 变量和字段包含一个引用到这个对象的内存地址,像上面的 songband

参考这个 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 ,它是一个快乐的小王国,在这里它的名字 abc 是有明确意义的。它有两个参数和由函数声明的一个本地变量。程序也可以在别的地方使用相同的名字,但是在 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中国 荣誉推出

上一周我们讲解了 栈是如何工作的 以及在函数的 序言 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 ,主要部分如下:

mainadd 中拷贝返回值到本地变量 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)。注意,关于从 esplocal_buffer 的箭头不是随意连接的。这个箭头代表着事务:它专门指向到由 local_buffer 所拥有的第一个字节,因为,那是一个保存在 esp 中的精确地址。

第二个寄存器跟踪的栈是 ebp(LCTT 译注:扩展基址指针寄存器),它包含一个 基指针 base pointer 或者称为 帧指针 frame pointer 。它指向到一个当前运行的函数的栈帧内的固定位置,并且它为参数和局部变量的访问提供一个稳定的参考点(基址)。仅当开始或者结束调用一个函数时,ebp 的内容才会发生变化。因此,我们可以很容易地处理在栈中的从 ebp 开始偏移后的每个东西。如图所示。

不像 espebp 大多数情况下是在程序代码中通过花费很少的 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()

mainesp 减去 12 之后得到它所需的栈空间,它为 ab 设置值。在内存中的值展示为十六进制,并且是小端格式,与你从调试器中看到的一样。一旦设置了参数值,main 将调用 add,并且开始运行:

现在,有一点小激动!我们进入了另一个函数序言,但这次你可以明确看到栈帧是如何从 ebp 到栈建立一个链表。这就是调试器和高级语言中的 Exception 对象如何对它们的栈进行跟踪的。当一个新帧产生时,你也可以看到更多这种典型的从 ebpesp 的捕获。我们再次从 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 页面所在的节(即圆括号里的 23)也提供了线索。节 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 对此有一些帮助。因此要做 文件的内存映射,它允许一个程序仅访问内存就可以读或写磁盘文件。类似的映射也存在于像视频卡这样的地方。最终,云计算的经济性可能导致内核消除或最小化用户模式/内核模式的切换。

最终,系统调用还有益于系统安全。一是,无论如何来历不明的一个二进制程序,你都可以通过观察它的系统调用来检查它的行为。这种方式可能用于去检测恶意程序。例如,我们可以记录一个未知程序的系统调用的策略,并对它的异常行为进行报警,或者对程序调用指定一个白名单,这样就可以让漏洞利用变得更加困难。在这个领域,我们有大量的研究,和许多工具,但是没有“杀手级”的解决方案。

这就是系统调用。很抱歉这篇文章有点长,我希望它对你有用。接下来的时间,我将写更多(短的)文章,也可以在 RSSTwitter 关注我。这篇文章献给 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中国 荣誉推出