image frame

Ytyan的博客

编程语言如何实现闭包

闭包是什么

这里偷懒抄一下维基百科的定义：

在计算机科学中，闭包（英语：Closure），又称词法闭包（Lexical Closure）或函数闭包（function closures），是在支持头等函数的编程语言中实现词法绑定的一种技术。闭包在实现上是一个结构体，它存储了一个函数（通常是其入口地址）和一个关联的环境（相当于一个符号查找表）。

简单地说，闭包是一个在函数内定义的函数，并且闭包能够捕获定义处函数中所拥有的变量（包括全局变量和局部变量）。

如果一个语法只能在函数内定义函数，却无法使用上层函数的局部变量，那么它就不是闭包语法。这种方式只不过是缩减了函数名的命名空间，仅仅能减少命名冲突罢了。例如下面的rust语句就不是闭包（rust通过其他语法实现闭包）。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
fn func1() {
    let n = 100;
    fn add(a: i32, b: i32) -> i32 {
        // println!("n = {}", n) // 这行语句无法被编译，因为add只是一个普通函数，不能捕获环境中的局部变量n
        a + b
    }
    add(4, 6);
}
fn func2() {
    let n = 100;
    let add = |a: i32, b: i32| -> i32 {
        println!("n = {}", n); // 这里可以被编译，这是个闭包语法，能捕获环境中的局部变量n
        a + b
    };
    add(4, 6);
}

那么，闭包应该如何实现呢，我们可以通过C++、Rust、Golang、Python这几个语言中的行为或实现来观察其究竟使用什么方式实现闭包。

解释型语言中的编译模块

通常所说的解释型语言逐行解释执行，不进行编译是不正确的。目前主流解释型语言的官方实现，除了bash部分等shell脚本语言外，都是会先编译为字节码，再由解释器执行的。所以当本文提及编译器时，请注意也包含了Python和Lua，只不过它们的编译器内置在解释器内。

闭包的组成

计算机并不区分程序和数据，但人类设计的系统和程序会区分，并且将程序和数据分开存储，闭包也是这样。

闭包有两个核心组成部分：闭包函数的代码和其捕获的数据。其中代码段由编译器在编译期生成，而数据则在运行时捕获。

闭包如何捕获变量

熟悉C++的读者会知道，闭包捕获变量有两种捕获方式：值捕获和引用捕获。不过在一些语言中，并没有值捕获这种方式，例如Python、Lua。

值得注意的是Go，作为一个保留了指针的语言，Go也不提供值捕获能力，如果需要值捕获需要将变量作为闭包的参数传入。

值捕获

我们来看下面的C++代码。该代码使用C++11编译。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
#include <iostream>
#include <functional>

std::function<int()> make_closure(int x) {
    auto inner = [x]()mutable {
        return ++x;
    };
    x++;
    return inner;
}

int main() {
    auto closure1 = make_closure(100);
    auto closure2 = make_closure(200);

    int c1r1 = closure1();
    int c2r1 = closure2();

    int c1r2 = closure1();
    int c2r2 = closure2();

    std::cout << "closure1() = " << c1r1 << std::endl;
    std::cout << "closure2() = " << c2r1 << std::endl;

    std::cout << "closure1() = " << c1r2 << std::endl;
    std::cout << "closure2() = " << c2r2 << std::endl;
    return 0;
}

上面这段代码为值捕获，其输出如下。

1
2
3
4
closure1() = 101
closure2() = 201
closure1() = 102
closure2() = 202

可以看到闭包closure1调用后返回了x自增后的值，第二次调用后x继续自增，而closure2的调用则是与closure1的调用结果相互独立，并不会互相影响。这里我们可以看出，实现上，闭包会将捕获的局部变量复制到自身内部成为其组成部分，从而能让闭包保存自身所捕获变量的状态。

另外我们还发现，make_closure最后的x++并没有对闭包捕获的x造成影响，从这里我们可以看到，对于值捕获的闭包而言，其捕获变量的时机就是在其所定义的位置。

我们可以用C语言模拟这种闭包行为。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
#include <stdio.h>
#include <malloc.h>
struct ClosureEnv
{
    int env1;
};

struct Closure
{
    int (*function)(struct ClosureEnv *env);
    struct ClosureEnv env;
};

int closure_function(struct ClosureEnv *env)
{
    return ++env->env1;
}

struct Closure *make_closure(int x)
{
    struct Closure *inner = malloc(sizeof(struct Closure));

    inner->function = closure_function,
    inner->env.env1 = x;

    x++;
    return inner;
}

int main()
{
    struct Closure *closure1 = make_closure(100);
    struct Closure *closure2 = make_closure(200);

    printf("closure1() = %d\n", closure1->function(&closure1->env));
    printf("closure1() = %d\n", closure1->function(&closure1->env));

    printf("closure2() = %d\n", closure2->function(&closure2->env));
    printf("closure2() = %d\n", closure2->function(&closure2->env));
    return 0;
}

为了实现这个闭包，我们需要手动构造闭包的环境，并且在外部写一个闭包的函数体。而支持闭包的语言可以通过模板或者泛型的方式帮助我们自动完成这些枯燥的过程，并且省去传入的参数。

多个闭包共享同个变量

从上面的代码可以看到，对于值捕获的闭包情况，每个闭包都会有各自捕获的值的的拷贝，但是实际编程中很有可能遇到同一个函数内使用两个或更多闭包，如果使用值捕获的方式，那么捕获的变量就无法共享。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
#include <iostream>
#include <functional>

std::pair<std::function<int()>, std::function<int()>> make_closure(int x) {
    auto inner = [x]()mutable {
        return ++x;
    };
    auto inner2 = [x]()mutable {
        return ++x;
    };
    x++;
    return std::make_pair(inner, inner2);
}

int main() {
    auto closures = make_closure(0);
    auto closure1a = closures.first;
    auto closure1b = closures.second;

    std::cout << "closure1a() = " << closure1a() << std::endl;
    std::cout << "closure1b() = " << closure1b() << std::endl;
    return 0;
}

大家可以自己参考上面的C代码，想想这里的C代码模拟实现是什么样子的。而这里的C++代码，输出结果为

1
2
closure1a() = 1
closure1b() = 1

但是大多数时候我们会需要不同闭包间共享同一个局部变量，并且还能把闭包内对局部变量的修改反映到闭包外。事实上，这是大多数语言，如Go、Python、JS的默认行为。这些被共享的变量，通常被称为freevars，即自由变量。下面举一个Python的例子。

1
2
3
4
5
6
7
8
9
10
def outer(n):
    def getter():
        return n
    def setter(m):
        nonlocal n
        n = m
    return getter, setter
g, s = outer(100)
s(200)
print('g() = {}'.format(g())) # g() = 200

引用捕获

C++中的引用捕获

为了让多个闭包能够共享同一变量，C++还提供了引用捕获。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
#include <iostream>


void test_closure(int x) {
    auto inner = [&x]()mutable {
        return ++x;
    };
    auto inner2 = [&x]()mutable {
        return ++x;
    };
    std::cout << inner() << std::endl;
    std::cout << inner2() << std::endl;
}

int main() {
    test_closure(100);
    return 0;
}

当使用引用捕获时，闭包可以捕获局部变量的引用，这样就可以在多个闭包间共享同一个局部变量了，但这种方式也有缺陷，当对变量的引用超出变量的作用范围时会发生UB。

显然，为了解决这个问题，我们可以将这个局部变量拷贝到由程序员手动管理的内存中，并在闭包不再使用后删除。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
#include <iostream>
#include <functional>
#include <memory>

std::pair<std::function<int()>, std::function<int()>> make_closure(int x) {
    std::shared_ptr<int> heap_x = std::make_shared<int>(x);

    auto inner = [heap_x]()mutable {
        return ++(*heap_x);
    };
    auto inner2 = [heap_x]()mutable {
        return ++(*heap_x);
    };
    return std::make_pair(inner, inner2);
}

int main() {
    auto closures = make_closure(100);
    auto closure1a = closures.first;
    auto closure1b = closures.second;

    std::cout << "closure1a() = " << closure1a() << std::endl;
    std::cout << "closure1b() = " << closure1b() << std::endl;
    return 0;
}

Rust中的引用捕获

Rust与C++不一样，生命周期和所有权机制并不允许出现像上面C++那样的写法。生命周期禁止将捕获了引用的闭包传到局部变量的生命周期外，而所有权机制则禁止出现多个可变引用，所以为了实现上面的写法，必须要借助RefCell才可以。

Go中的引用捕获

同为编译型语言，Go语言默认提供了引用捕获的方式，让我们看示例代码。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
package main

import "fmt"

type FnG func() int
type FnS func(int)

func testClosure(n int) (FnG, FnS) {
	getter := func() int {
		return n
	}
	setter := func(m int) {
		n = m
	}
	return getter, setter
}
func main() {
	get, set := testClosure(100)
	fmt.Printf("get() = %d\n", get())
	set(5400)
	fmt.Printf("get() = %d\n", get())
}

打印出来结果为

1
2
get() = 100
get() = 5400

我们并没有在Go代码中看到任何形式指针，这是因为对自由变量的分析被内置在编译器中，编译器的逃逸分析模块会自动查找自由变量，并且根据实际情况选择捕获其引用还是使用值捕获，让原变量保存在栈中。

Go当前的编译器的判断标准是：如果一个变量从未被修改，并且小于128字节，那么就使用值捕获。显然变量从未被修改是一个必须条件，而小于128字节是Go团队认为的合适的大小，如果超过这个大小，可能值捕获提高的效率就不多了。

1
2
3
4
5
6
7
8
9
//file:src/cmd/compile/internal/escape/escape.go@batch.flowClosure
// Capture by value for variables <= 128 bytes that are never reassigned.
n.SetByval(!loc.addrtaken && !loc.reassigned && n.Type().Size() <= 128)
if !n.Byval() {
    n.SetAddrtaken(true)
    if n.Sym().Name == typecheck.LocalDictName {
        base.FatalfAt(n.Pos(), "dictionary variable not captured by value")
    }
}

Python中的引用捕获

有些熟悉Python的朋友可能会问，Python万物皆对象，那么所有的变量都是引用，为什么还要单独提引用捕获呢？

通常，Python中的局部变量以PyObject *指针的方式存在于Python函数的栈帧中。而Python是一种使用解释器的语言，其函数调用的方式不会像编译目标为机器码的语言一样受很大程度的平台指令集限制。这意味着想要捕获上层函数的环境，除了像Go一样使用逃逸分析的为其额外分配以外，还可以将整个函数的栈保留下来。不过Python也使用了额外分配的方式。

与Go编译器类似的，Python也使用了类似逃逸分析的方式去分析函数中的变量是否使用了上层函数的变量，不过由于Python的特性，其实现思路与Go差距很大。

首先，Python会检查对变量的赋值操作。当在处理函数时，如果一个变量在函数的任意位置被赋值，则认为该变量在函数中做了声明，会进入函数时会预先为其引用分配栈空间，以加速对象存取。如果这个变量完全没有被赋值，只是被使用了（obj.attr = 1也是被使用而非被赋值），那么Python就认为这是一个外部变量，会递归向上查找定义该变量的位置，如果直到找到全局名称空间仍未找到，则直接将其认定为一个全局变量。而如果在上层函数中找到，则认为其是一个闭包变量。

如果使用global或nonlocal声明了变量，那么Python不会通过是否存在赋值判断其是否应该在栈上创建对象引用，而是直接在全局或上层函数作用域中查找。值得注意的是，global变量不存在的时候，Python会直接创建该变量，且不会报错；但nonlocal变量不存在的时候，Python则会在编译时直接报错，不会执行任何一条代码，因为python需要在编译时处理上层的变量。

当识别出闭包使用的变量后，Python的行为就与其他语言类似了：无论是外部的函数还是闭包，都不在栈中直接访问对象，而是通过对象的引用访问对象。而进入闭包的第一个参数也是通过COPY_FREE_VARS将外部变量的引用传入到内部栈中，然后在栈中使用{LOAD,STORE}_DEREF操作这些变量。

Python的在处理自由变量时是在analyze_block中处理的。这里展开可能比较长，不再细述。

EMOCK工作原理

EMOCK 简介

首先来简单介绍一下EMOCK，EMOCK是C和C++语言常见的MOCK库，它可以在运行时将可执行程序或动态链接库的代码替换为mock函数，以实现对函数进行打桩。其原理为修改函数入口处的代码，将其替换为跳转到mock函数的代码。

例如实际业务代码中有获取1-100随机值的函数，但在测试中我们只希望验证随机值为1的情况，那么就可以使用EMOCK。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
// get_random.c at libcredit.so
__attribute__((noinline))int get_random()
{
    return rand() % 100;
}

int get_credit()
{
    if (get_random() == 1) {
        return 100;
    }
    return 10;
}
// end

// test.cpp
#include "gtest/gtest.h"
#include "emock/emock.h"
extern "C"{
int get_random();
int get_credit();
}
TEST(CreditTest, should_get_100_credit_when_random_is_1)
{
    // 这里我们只希望获取 `get_random` 返回1的情况
    // 但是so中的函数已经被编译，无法修改，此时需要使用EMOCK
    // 通过下面的代码，可以让 `get_random` 函数永远返回1
    EMOCK(get_random).stubs().with(any()).will(returnValue(1));
    ASSERT_EQ(get_credit(), 100);
}

EMOCK 工作原理

前言：从零开始设计MOCK

如果不限制任何条件，重新从零开始设计一个C/C++ MOCK工具，应该怎么设计呢？

首先想到的最简单的方式就是直接修改被测函数的源代码，为其增加一个全局的hook函数指针，当hook不为空时就返回hook函数。在测试代码中使用 extern 关键字获取该变量并赋值

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
int (*_hook_get_random)()  = NULL;
int get_random()
{
    if (_hook_get_random) {
        return _hook_get_random();
    }
	return rand() % 100;    
}
// test.cpp

extern "C" {
extern int (*_hook_get_random)()
}
int get_random_as_1()
{
    return 1;
}
TEST(BaseTest, should_xxx)
{
    _hook_get_random = get_random_as_1;
}

通过使用宏，还可以避免在生产环境运行时测试代码的不必要占用。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
#ifdef _BUILDING_TEST
int (*_hook_get_random)()  = NULL;
#endif
int get_random()
{
#ifdef _BUILDING_TEST
    // 只有测试代码才会包含这个检查，上线运行时不会有额外的开销。
    if (_hook_get_random) {
        return _hook_get_random();
    }
#endif
	return rand() % 100;    
}

这种方式虽然可行，但缺陷也非常明显，每当需要hook一个被测函数时都需要为其准备一个钩子变量，并且要在函数中插入对该钩子变量的检测，虽然生产环境没有额外的性能开销，但是显然增加了不少编码的负担。同时，生产环境的代码几乎必须要使用第三方库，为第三方库增加大量的这种测试代码不仅不符合常理，也容易因为编码失误导致第三方库不稳定。更何况大多数第三方库是预编译的动态链接库，不可能为已经编译好的库插入这种代码。

那么究竟该如何做一个通用的mock呢？

CPU的运行方式：以X86-64为例

虽然在逻辑上，存在仅需一条指令就可以图灵完备的CPU，但实际上一个可用的CPU至少应该有三种指令：算术指令，包括整数、浮点、位运算、寄存器传递；访存指令，即读取/写入内存的指令；跳转指令，包括相对跳转、绝对跳转，这其中还可以分为有条件或无条件跳转。

现在有如下简单的的C语言代码，为了演示方便，这段代码的编译不使用任何优化（-O0）。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
#include <stdio.h>

int add(int a, int b) {
    return a + b;
}

int sub(int a, int b) {
    return a - b;
}

int main() {
    int a = 4;
    int b = 5;
    int res;
    if (a == 4) {
        res = add(a, b);
        goto end;
    } else {
        res = sub(a, b);
    }
    printf("Oops, I can't be executed!\n");
end:
    printf("sum = %d\n", res);
    return 0;
}

这段代码在我的设备上编译后，使用objdump -d获得编译后文件的人类可读格式，这里我们忽略不是我们编写的函数。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
Disassembly of section .plt.sec:

0000000000001050 <printf@plt>:
    1050:       f3 0f 1e fa             endbr64
    1054:       f2 ff 25 75 2f 00 00    bnd jmp *0x2f75(%rip)        # 3fd0 <printf@GLIBC_2.2.5>
    105b:       0f 1f 44 00 00          nopl   0x0(%rax,%rax,1)

Disassembly of section .text:

......
0000000000001169 <add>:
    1169:       f3 0f 1e fa             endbr64
    116d:       55                      push   %rbp
    116e:       48 89 e5                mov    %rsp,%rbp
    1171:       89 7d fc                mov    %edi,-0x4(%rbp)
    1174:       89 75 f8                mov    %esi,-0x8(%rbp)
    1177:       8b 55 fc                mov    -0x4(%rbp),%edx
    117a:       8b 45 f8                mov    -0x8(%rbp),%eax
    117d:       01 d0                   add    %edx,%eax
    117f:       5d                      pop    %rbp
    1180:       c3                      ret

0000000000001181 <sub>:
    1181:       f3 0f 1e fa             endbr64
    1185:       55                      push   %rbp
    1186:       48 89 e5                mov    %rsp,%rbp
    1189:       89 7d fc                mov    %edi,-0x4(%rbp)
    118c:       89 75 f8                mov    %esi,-0x8(%rbp)
    118f:       8b 45 fc                mov    -0x4(%rbp),%eax
    1192:       2b 45 f8                sub    -0x8(%rbp),%eax
    1195:       5d                      pop    %rbp
    1196:       c3                      ret

0000000000001197 <main>:
    1197:       f3 0f 1e fa             endbr64
    119b:       55                      push   %rbp
    119c:       48 89 e5                mov    %rsp,%rbp
    119f:       48 83 ec 10             sub    $0x10,%rsp
    11a3:       c7 45 f8 04 00 00 00    movl   $0x4,-0x8(%rbp)
    11aa:       c7 45 fc 05 00 00 00    movl   $0x5,-0x4(%rbp)
    11b1:       83 7d f8 04             cmpl   $0x4,-0x8(%rbp)
    11b5:       75 14                   jne    11cb <main+0x34>
    11b7:       8b 55 fc                mov    -0x4(%rbp),%edx
    11ba:       8b 45 f8                mov    -0x8(%rbp),%eax
    11bd:       89 d6                   mov    %edx,%esi
    11bf:       89 c7                   mov    %eax,%edi
    11c1:       e8 a3 ff ff ff          call   1169 <add>
    11c6:       89 45 f4                mov    %eax,-0xc(%rbp)
    11c9:       eb 21                   jmp    11ec <main+0x55>
    11cb:       8b 55 fc                mov    -0x4(%rbp),%edx
    11ce:       8b 45 f8                mov    -0x8(%rbp),%eax
    11d1:       89 d6                   mov    %edx,%esi
    11d3:       89 c7                   mov    %eax,%edi
    11d5:       e8 a7 ff ff ff          call   1181 <sub>
    11da:       89 45 f4                mov    %eax,-0xc(%rbp)
    11dd:       48 8d 05 20 0e 00 00    lea    0xe20(%rip),%rax        # 2004 <_IO_stdin_used+0x4>
    11e4:       48 89 c7                mov    %rax,%rdi
    11e7:       e8 74 fe ff ff          call   1060 <puts@plt>
    11ec:       8b 45 f4                mov    -0xc(%rbp),%eax
    11ef:       89 c6                   mov    %eax,%esi
    11f1:       48 8d 05 27 0e 00 00    lea    0xe27(%rip),%rax        # 201f <_IO_stdin_used+0x1f>
    11f8:       48 89 c7                mov    %rax,%rdi
    11fb:       b8 00 00 00 00          mov    $0x0,%eax
    1200:       e8 6b fe ff ff          call   1070 <printf@plt>
    1205:       b8 00 00 00 00          mov    $0x0,%eax
    120a:       c9                      leave
    120b:       c3                      ret

在objdump的输出中，第一列为以十六进制表示的文件中的偏移量，第二列为机器代码的16进制表现形式，第三列为反汇编出来的汇编代码，与机器代码一一对应。CPU就是通过一条条执行第二列的二进制机器代码来运行程序的，如果改变这些机器代码，就可以改变程序的执行流程，而这里就是可以mock的地方。

运行时修改机器代码

想要修改，首先需要确定被修改的位置。如果要将某个函数替换为mock函数，直觉上可以修改每个调用该函数的位置，将它们call的函数从原函数修改为mock函数。但是这样有一个很大的缺陷：有些调用并非直接通过call进行静态调用，而是使用函数指针或在PLT表中进行动态调用，无法从代码段中分析出这类函数究竟调用的是哪个函数。并且call可跳转的范围是有限的，跨动态链接库的情况下很可能无法直接跳转，需要使用长跳方式。

使用短跳指令hook函数

针对以上缺陷，可以换一种思路：虽然不是所有的call都使用同一种调用方式，但是所有的call最终都会前往函数的入口，那么就可以修改函数入口的代码，让其刚刚进入就跳转到mock函数。以add函数举例，我们尝试覆写其函数入口，将其跳转到sub函数。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
0000000000001169 <add>:
    1169:       f3 0f 1e fa             endbr64 ; 这个是安全机制，得留着
    ; 下面这些不要了，我们尝试直接覆写它
    116d:       55                      push   %rbp
    116e:       48 89 e5                mov    %rsp,%rbp
    ; 这段成为新的了，直接动手修改
    116d:       eb 12                   jmp    1181 ; 实际为 jmp $ + (0x1181 - 0x116d)
    116f:       89 e5                   ; 被损坏的指令,是原 116e 的 (48 [89 e5]) 部分
    1171:       89 7d fc                mov    %edi,-0x4(%rbp)
    1174:       89 75 f8                mov    %esi,-0x8(%rbp)
    1177:       8b 55 fc                mov    -0x4(%rbp),%edx
    117a:       8b 45 f8                mov    -0x8(%rbp),%eax
    117d:       01 d0                   add    %edx,%eax
    117f:       5d                      pop    %rbp
    1180:       c3                      ret

0000000000001181 <sub>:
    1181:       f3 0f 1e fa             endbr64
    1185:       55                      push   %rbp
    1186:       48 89 e5                mov    %rsp,%rbp
    1189:       89 7d fc                mov    %edi,-0x4(%rbp)
    118c:       89 75 f8                mov    %esi,-0x8(%rbp)
    118f:       8b 45 fc                mov    -0x4(%rbp),%eax
    1192:       2b 45 f8                sub    -0x8(%rbp),%eax
    1195:       5d                      pop    %rbp
    1196:       c3                      ret

这样我们就成功覆写了指令，让我们在C语言中实际尝试一下。如果读者想要使用这段代码，请保证您的代码是在Linux系统，X86-64（也即64bit）环境下编译执行。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
#include <stdio.h>
#include <sys/mman.h>
#include <stdlib.h>
#include <stdint.h>
#include <stdbool.h>

int add(int, int);
int sub(int, int);

int sub(int a, int b)
{
    return a - b;
}

int add(int a, int b)
{
    return a + b;
}

bool check_endbr64(void*ptr){
    uint8_t *p = (uint8_t*)ptr;
    // f3 0f 1e fa
    return p[0] == 0xf3 && p[1] == 0x0f && p[2] == 0x1e && p[3] == 0xfa;
}
void change_add()
{
    void *page_start = (void *)(uintptr_t)((uintptr_t)add & (~(uintptr_t)0xfff));
    if (mprotect(page_start, 4096, PROT_READ | PROT_WRITE | PROT_EXEC) == -1) {
        perror("mprotect");
        exit(1);
    }
    uint8_t *func_start = (uint8_t*)add;
    // 跳过 0，1，2，3 字节，这里是保护指令，如果被修改
    // 在使用函数指针跳转时会发生错误
    intptr_t skip_endbr64 = 0;
    if (check_endbr64(func_start)) {
        skip_endbr64 = 4;
    }
    intptr_t offset = (intptr_t)sub - (intptr_t)(add + skip_endbr64 /*跳过endbr64*/);
    offset -= 5; // 减去 jmp 指令的长度
    if (offset > INT32_MAX || offset < INT32_MIN) {
        fprintf(stderr, "offset is too large\n");
        exit(1);
    }
    func_start[4] = 0xe9; // jmp 较长跳指令，占用5个字节
    *(int32_t*)(func_start + 5) = offset;
}

int main()
{
    int a = 4;
    int b = 5;
    int res;
    change_add();
    if (a == 4) {
        res = add(a, b);
        goto end;
    } else {
        res = sub(a, b);
    }
    printf("Oops, I can't be executed!\n");
end:
    printf("sum = %d\n", res);
    return 0;
}

在这次修改后，a仍然是4，b仍然是5，但是打印结果却并非是sum = 9，也并没有打印Oops, I can't be executed!，这说明分支仍然是 a == 4的分支，但是调用的函数变了。

1
2
qxy@qxy:~/testc$ ./a.out
sum = -1

显然，在修改过后，对add的调用就转为了对sub的调用，这是因为原本add的执行流程被我们修改为跳转到sub函数了。

有些读者可能会问：假如修改了动态链接库的函数，那么是不是会对其他使用这个动态链接库的函数造成破坏呢？

这个问题很有意思，考虑到了动态链接库在物理内存中是由多个进程共享的。 不过答案是不会的，我们可以查看每个进程对动态链接库的map来找到原因。

1
2
3
4
5
6
7
8
... 省略了其他map
7ff4590b2000-7ff4590da000 r--p 00000000 fd:00 393289                     /usr/lib/x86_64-linux-gnu/libc.so.6
7ff4590da000-7ff45926f000 r-xp 00028000 fd:00 393289                     /usr/lib/x86_64-linux-gnu/libc.so.6
7ff45926f000-7ff4592c7000 r--p 001bd000 fd:00 393289                     /usr/lib/x86_64-linux-gnu/libc.so.6
7ff4592c7000-7ff4592c8000 ---p 00215000 fd:00 393289                     /usr/lib/x86_64-linux-gnu/libc.so.6
7ff4592c8000-7ff4592cc000 r--p 00215000 fd:00 393289                     /usr/lib/x86_64-linux-gnu/libc.so.6
7ff4592cc000-7ff4592ce000 rw-p 00219000 fd:00 393289                     /usr/lib/x86_64-linux-gnu/libc.so.6
... 省略了其他map

以上面的libc.so.6为例，可以看到，无论是只读段、读写段还是代码段，其共享位都是p，这说明libc是个勇士其会被以私有内存的形式map，而操作系统对这种map会采取COW（写时复制）的机制，当进程对共享段进行修改时，操作系统会复制出一份单独的页面给该程序使用，避免进程对自身的共享库的修改影响到其他进程。

当然，这样做仍然有缺陷。

  1. jmp指令的立即数寻址范围有限，只能寻址附近2GB的内存，想要更远就需要其他指令或跳板。
  2. 对代码进行了修改，但是没有保存源代码，如果想解除mock就只能再从磁盘上读取文件。

如何跳得更远

jmp指令可以跳转前后2GB的空间，看上去很大了，很少有程序能有2GB的大小， 那么为什么还需要跳得更远呢？因为X64系统下，虚拟内存空间有非常大的128TB，并且通常so和主程序之间的空洞很大，远超2GB大小，这种情况下就需要长跳了。

长跳通常需要借助寄存器，那这样就需要增加指令的数量了。大致的流程如下。

  1. 将地址加载到寄存器。
  2. 跳转到寄存器所指向的位置。

在X86-64机器上，我们可以使用movabs指令后跟8字节立即数的方式指定指针的位置。

下面的例子介绍了应该如何修改 libc.so.6中的rand()函数。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
#include <stdio.h>
#include <stdlib.h>
#include <sys/mman.h>
#include <stdint.h>
#include <stdbool.h>

int rand_only_1()
{
	return 1;
}
bool check_endbr64(void *ptr)
{
	uint8_t *p = (uint8_t *)ptr;
	// f3 0f 1e fa
	return p[0] == 0xf3 && p[1] == 0x0f && p[2] == 0x1e && p[3] == 0xfa;
}
void change_rand()
{
	void *page_start = (void *)(uintptr_t)((uintptr_t)rand & (~(uintptr_t)0xfff));
	if (mprotect(page_start, 4096, PROT_READ | PROT_WRITE | PROT_EXEC) == -1) {
		perror("mprotect");
		exit(1);
	}
	uint8_t *func_start = (uint8_t *)rand;
	intptr_t skip_endbr64 = 0;
	if (check_endbr64(func_start)) {
		skip_endbr64 = 4;
	}
	intptr_t offset = (intptr_t)rand_only_1 - (intptr_t)(rand + skip_endbr64 /*跳过endbr64*/);
	offset -= 5; // 减去 jmp 指令的长度
	if (offset > INT32_MAX || offset < INT32_MIN) {
		// 这里直接的jmp指令就无法处理了，但我们可以将位置加载到寄存器中，然后跳转
		func_start[0] = 0x48; // movabsq $0x0, %rdi
		func_start[1] = 0xbf;
		*(int64_t *)(func_start + 2) = (int64_t)rand_only_1;
		func_start[10] = 0xff; // jmp *%rdi
		func_start[11] = 0xe7;
		return;
	}
	func_start[4] = 0xe9; // jmp 较长跳指令，占用5个字节
	*(int32_t *)(func_start + 5) = offset;
	return;
}

int main()
{
	change_rand();
	for (int i = 0; i < 10; i++) {
		for (int j = 0; j < 10; j++) {
			printf("%d ", rand());
		}
		printf("\n");
	}
}
/*
qxy@qxy:~/testc$ gcc test.c -g && ./a.out
1 1 1 1 1 1 1 1 1 1
1 1 1 1 1 1 1 1 1 1
1 1 1 1 1 1 1 1 1 1
1 1 1 1 1 1 1 1 1 1
1 1 1 1 1 1 1 1 1 1
1 1 1 1 1 1 1 1 1 1
1 1 1 1 1 1 1 1 1 1
1 1 1 1 1 1 1 1 1 1
1 1 1 1 1 1 1 1 1 1
1 1 1 1 1 1 1 1 1 1
*/

这里我们还观察到，这次的修改就需要函数至少有11字节的大小才能工作，如果函数过小，就有可能导致覆盖下一个函数的函数头，引起未知问题。然而，我们无法直接从代码段中获知函数的长度，这需要解析二进制文件才能得知。并且，即使是解析了二进制文件，仍然有可能有内部链接的静态函数因为符号表被剥离，程序无法解读，进而遭到破坏。

技术上，x86架构中的一个函数最少只会有1字节（也即只有1个ret指令），不过实际使用中，编译器往往会将一个函数填充到至少16字节，这给了我们充分的操作空间。如果函数长度大于5字节，也可以使用短跳后+寄存器跳的方式规避。但如果函数的大小真的只有1字节，那确实就无能为力了，不过只有一字节就说明这个函数单纯返回了，什么也没干，没有hook的必要，否则即使函数有2字节，都可以使用超短跳（仅2字节的jmp指令）跳过后再用跳板跳到寄存器处。

修改并非作用于PLT表上

有些熟悉链接器的读者可能会认为上面的代码并不正确：其没有考虑到PLT表在动态链接时的影响。的确，PLT表是实现动态链接的重要工具，通常访问函数都是首先通过PLT表进行跳转，以实现延迟绑定 (lazy banding)，而如果上面的代码只修改了PLT表，则会导致其他使用rand()函数的so实际上不会被修改，如果rand()在其他so调用其表现就会和没有修改一样。

但是事实上是不会的，编译器检测到一个函数被使用了函数指针，这个函数就会从延迟绑定变为提前绑定(early banding)，其在内存中的实际位置会在主函数运行之前写入GOT表中。

1
2
mov    0x2d5b(%rip),%rax        # 3ff8 <rand@GLIBC_2.2.5>
mov    %rax,-0x10(%rbp)

可以看到它会尝试直接从GOT表中获取函数指针，而并非获取的PLT指针。

实际上，我们也可以通过编写一个so来测试这个方法。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
// my_rand.c
#include <stdlib.h>
int my_rand()
{
    return rand();
}
// gcc my_rand.c -fPIC -shared -o libmyrand.so
// 修改 test.c 中的main函数

int my_rand();
int main()
{
	change_rand();
	for (int i = 0; i < 10; i++) {
		for (int j = 0; j < 10; j++) {
			printf("%d ", my_rand());
		}
		printf("\n");
	}
}
// gcc test.c -lmyrand -L.
// LD_LIBRARY_PATH=`pwd` ./a.out

其输出仍然是10*10的1，并不会有任何变化。

如何处理寄存器

有些读者可能会发现，上面的汇编代码破坏了寄存器%rdi，有可能导致未预期的行为，但这通常是可以接受的，因为%rdi在大部分ABI下，都是由调用方进行保存的，如果函数已经跳转，说明调用方已经妥善保存或不需要该寄存器的值，我们可以随意使用。

但是如果真的就有那么一种ABI，%rdi变成了参数寄存器，所有的寄存器和栈都需要完整保留给被调用函数呢？我们仍然有办法。

在寄存器跳转前增加一个push %rdi指令，将%rdi存入栈中，并且不直接跳转到mock函数，而是跳转到mock函数附近的一个中转函数（并非程序中的函数，更像是一段纯机器代码），在中转函数中使用pop %rdi指令将%rsp和%rdi恢复，并紧接着使用jmp指令直接跳转到对应位置。此时可以保证所有的寄存器以及栈都能完整传递给mock函数，就好像从来没有发生过跳转一样。

虚指针、函数重载等

只要了解了C++虚表的实现原理，这些东西都是很容易做到的，这个文章写了好几个小时了，上面C的看懂了，C++虚函数怎么mock的问题就只剩下怎么获取虚表了，这里我就不再赘述了，这不是本篇文章的重点。

总结

各种MOCK需要对内存和CPU都有较深的了解才能正确工作，并且这种方式需要指定CPU架构，我这里只写了x86-64架构的，arm64的又是不同的一种方式，如果长跳需要ldr br两个指令8字节和8字节的立即数16字节才能完成，不过由于arm64指令集是等长的，短跳情况下arm只会占用一个指令，这减少了不少短跳的负担。

其实还是C/C++积重难返，其他语言大多都是全量源码编译，mock这种事情编译期就能搞定。而Python、Java这样的字节码语言就更简单了。

记一次EMOCK引起的段错误异常

EMOCK简介

可以去看我的另一篇文章，介绍了EMOCK的功能和其工作原理。

发生了什么问题

在一些X86机器上，突然发现定义变量时发生了Segmentation Fault。

1
2
3
4
5
6
int test_function_body()
{
    // ... 几十行代码
    void *ctx = nullptr; // 通过GDB发现这行发生了段错误，并且必现
    // ... 几十行代码
}

定位思路

思路1：堆栈溢出

通常在栈中发生了段错误，第一反应就是栈溢出，而栈溢出通常罪魁祸首只有两个，一个是无限递归，另一个是栈中出现过大的变量。

通过检视代码，发现最大的栈变量也只有几KB的大小，并且在gdb中使用backtrace命令也未发现递归调用的情况，这两种情况都排除了后，我开始思考更进一步的可能性。

思路2：越界写

排除了溢出的可能性，我考虑的第一种可能性是越界写栈数组导致存储上一级（或多级）函数的栈顶指针被破坏，在函数退出恢复寄存器时导致%rsp内容有误，进而导致写入位置错误。这种问题也同样容易排除，只需要在gdb中使用info reg就可以获得寄存器数值。程序由gdb启动时，gdb会关闭其ASLR，所以每次运行到同一位置时每个变量的内存地址都是固定的。查看%rsp寄存器数值，发现其处于通常的栈范围内0x7fff...。

当时我认为这种可能性很低，因为%rsp被破坏通常也伴随着pc也被破坏，然而执行流程没有错误，这就让这种可能性降到很低了。不过由于这个排查非常容易，还是先排查了这个。

思路3：从根本原因出发

在容易排查的问题排查过后，我决定从根本原因出发。在非嵌入式设备上，CPU和操作系统共同通过MMU来对进程的内存进行页式管理。程序的虚拟内存虽然有128TB（x86_64用户空间典型值），但是需要被操作系统映射之后才能被使用，并且其有读取、写入、执行三个权限。当程序尝试访问未被映射的内存或操作与内存的权限不匹配时（例如尝试写入r-xp的内存），操作系统则会给进程发送SIGINT信号，这通常会导致进程因Segmetation Fault终止。

在有以上的基础知识后，我们可以通过 cat /proc/$pid/maps在*nix系统上获取对应进程的内存映射布局。例如，可以使用 cat /proc/self/maps获取我们正在使用的这个cat进程的内存布局，示例如下。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
59bf1d469000-59bf1d46b000 r--p 00000000 103:01 580                       /usr/bin/cat
59bf1d46b000-59bf1d46f000 r-xp 00002000 103:01 580                       /usr/bin/cat
59bf1d46f000-59bf1d471000 r--p 00006000 103:01 580                       /usr/bin/cat
59bf1d471000-59bf1d472000 r--p 00007000 103:01 580                       /usr/bin/cat
59bf1d472000-59bf1d473000 rw-p 00008000 103:01 580                       /usr/bin/cat
59bf1e4ea000-59bf1e50b000 rw-p 00000000 00:00 0                          [heap]
........ 省略了一些不必要的细节
7e6c76600000-7e6c76628000 r--p 00000000 103:01 68112                     /usr/lib/x86_64-linux-gnu/libc.so.6
........ 省略了一些不必要的细节
7e6c76979000-7e6c7697b000 rw-p 00039000 103:01 34594                     /usr/lib/x86_64-linux-gnu/ld-linux-x86-64.so.2
7fff01941000-7fff01962000 rw-p 00000000 00:00 0                          [stack]
7fff019de000-7fff019e2000 r--p 00000000 00:00 0                          [vvar]
7fff019e2000-7fff019e4000 r-xp 00000000 00:00 0                          [vdso]
ffffffffff600000-ffffffffff601000 --xp 00000000 00:00 0                  [vsyscall]

这里忽略了一些so和其他文件的映射，以专注于栈内存和其他内存的区别。

后面标注了[stack]的就是栈内存，其他的内存有堆、二进制本身、系统调用、动态链接库，这些map的作用这里不做详细介绍，这里我们只看栈的内存。

可以通过计算器轻松算出这个进程栈的大小 0x7fff01962000 - 0x7fff01941000 = 135_168，为132KB，共计33个4K页面。可以看到这个进程占用的栈空间是很小的。当时发生错误的程序也是大约100K左右的内存。那么是因为进程的栈空间太小才发生了这个问题吗？显然不是的。

在Linux上，可以使用ulimit -s获得栈的最大大小，单位为KB，通常栈的大小在Linux上为8192KB，也即8MB，Windows上为1024KB，而实际上当时机器的最大栈大小都是8MB。

Linux栈内存的特殊性

我的另一篇文章对Linux内核的内存管理做了简单的分析，那里提到了向下增长栈Linux在使用没有被映射的栈内存时，会有一个expand_downwards的过程，这个过程通常需要有足够的，简单来说，就是一个进程的主线程的栈的大小会随着使用自动向下扩展，而非一开始就map出足够的空间。这也就导致了大部分程序的主线程栈都只会map几十到几百KB，因为这些程序实际只使用了这么大的空间，所以操作系统也只会为栈分配这么多空间，但只有主线程才会这样做。

由EMOCK导致的问题

通过获取该进程的map，果然发现了一个问题。我发现就在栈顶（也就是栈的最低地址处）有另一个映射紧贴着栈顶分配了4KB空间，这导致栈无法自动向下扩展，当栈变量用完了原有的栈空间，并且也用完了这紧贴着的4KB空间后，栈无法继续增长，也就导致了栈变量赋值到未映射的内存中，进而导致了进程段错误。

1
2
3
7e6c76979000-7e6c7697b000 rw-p 00039000 103:01 34594                     ld.so.2
7fff01940000-7fff01941000 rwxp 00000000 00:00 0   <==== 这里多出来一个没名字的映射顶到栈了
7fff01941000-7fff01962000 rw-p 00000000 00:00 0                          [stack]

由于这段内存具有少见的可执行属性（rwxp中的x），而我们的程序并没有JIT系统，所以优先怀疑emock等可能申请可执行内存的库。不过此时代码检视就显得过于麻烦，于是我采取了另一种方案：使用gdb跟踪mmap函数。因为这种类型的内存一定是mmap分配出来的。

于是，我通过gdb为mmap函数做断点，成功在发现一次EMOCK调用后，该未知内存被分配出来。但是我没有进一步定位问题根因（懒狗），推测有两种可能性，一种是EMOCK的bug，另一种是不当使用EMOCK，导致EMOCK分配位置错误。

定位到该原因后，虽然无法立即解决，但可以为该问题做规避方案了。于是我新增一个函数，并在初始化过程中调用。

1
2
3
4
5
6
7
8
__attribute__((noinline, optimize("O0"))) void fill_stack()
{
#define SIZE (4 * 1024 *1024)
    char data[SIZE];
    for (int i = SIZE - 1; i >= 0; i++) {
        data[i] = 1;
    }
}

这段代码会在整个测试的初始化时期调用，通过调用该代码，函数会先保存至少4MB的栈空间，这样就可以让程序有足够的栈空间运行而不会发生段错误，而EMOCK在这之后即使想要紧贴栈顶map内存，也要距离当前栈指针差不多4MB空间才可以map，这样就最大程度避免了栈空间还不大时就无法向下扩展的问题。

另外简单介绍几个其中的trick：

  1. 这里没有初始化数组，并且是反向遍历，而非正向遍历，这是尽可能沿着栈生长的方向填充。
  2. 填充1而不是0，其实在指定不优化时，0和1都没什么区别，但是优化时填充1可以保证让系统实际map物理内存，虽然在这个场景下实际map物理内存并没有什么意义。
  3. 通过 __attribute__指定函数不被内联，让函数return后栈空间一定可以被其他函数使用。
  4. 同样通过__attribute__指定不优化，否则这种代码很可能被聪明的编译器优化没。

最终定位

几天后这个问题被注意到，于是尝试确定问题根因，最终定位到居然是编译器的问题。其中一行代码如下。

1
2
3
if (std::labs((long)dst - (long)last_end) < kMaxAllocationDelta /*这个数字是2G*/)) {
    // 这里应该触发
}

gdb断点追踪，多次逐行运行，查看变量并计算发现其确实小于2G，但却没有触发mmap，实在无法理解的我开始逐个查看寄存器与汇编。发现其对应的汇编如下。

1
2
3
4
5
6
; ...
mov      -0x10e0(%rbp), %rdx
sub      %rbx, %rdx
cmp      $0x7fffffff, %rdx
ja       0x4ff810             ; emock::TrampolineAllocate 这里是无符号比较 (jmp above)
; ...

可以看到，其加载到寄存器后，仅仅做了一个减法，并将结果与2G-1进行比较，如果无符号整数的情况下大于2G-1则跳转出去不去运行if块的内容，而这个剑法的结果为负数，补码表示远远大于2G-1，这也就导致了被跳过。也就是说，这里的std::labs根本没有生效。

而一个真正做了std::labs的函数，其反汇编是这样的。

1
2
3
4
5
6
7
sub      %rax, %rbx          ; 先做正常的减法
mov      %rbx, %rax          ; 将结果复制一份
sar      $0x3f, %rax         ; 实现负数取绝对值的关键操作，如果是负数这里64位全1，正数则全0
xor      %rax, %rbx          ; 负数异或全1了以后符号位和数字位全部取反，相当于 rbx = -rbx - 1，正数则异或全0不变
sub      %rax, %rbx          ; 这里是 rbx = rbx - rax ，如果是负数就减-1，把上条指令的rbx少的1又加了回来，正数则减0不变
cmp      $0x7fffffff, %rbx   ; 与2G-1比较
jg       if_block            ; 有符号跳转 (jmp greater)

总结

真是屎山上又拉了一坨看上去毫无意义的屎，没想到有一天我也能写出“不要删除这个函数，虽然它看上去没有用，但删除它程序会崩溃”的代码。

如何配置git连接github

Git如何连接GitHub

第一步 配置git

1
2
3
4
5
6
git config --global user.name "Your Name" # 可以是任何名字
# 这里的Email可以是任何邮箱，但是只有在GitHub上配置过的邮箱（默认是登陆邮箱）
# 才能看到你的小绿块（活动记录）
# 同时GitHub提供匿名邮箱 12345678+xxx@users.noreply.github.com
# 可以避免邮箱
git config --global user.email "12345678+xxx@users.noreply.github.com"

可以看到git只配置了邮箱和名字，并没有密码之类的身份验证的东西。事实上，git并不做身份验证，只有git使用的SSH或HTTPS才可能需要身份验证。因为git完全可以在单机或局域网内运行，所以身份验证对于git来说并无必要。

不过GitHub需要知道你的身份，因为GitHub需要管理权限、付费等等必要因素，而git又是匿名的，所以需要使用一种身份验证方式来确认身份，如果你使用HTTPS进行clone操作的话，那么每次提交都会让你输入GitHub的用户名密码，所以可以使用SSH进行clone，这样我们可以用SSH来登录GitHub，通过下面的操作，GitHub会将某个SSH密钥对关联到你的账号，无需像HTTPS那样频繁输入用户名密码。

第二步 生成密钥对

注意：使用下面的命令时千万要注意输出中的Overwrite（覆盖）这个关键字，出现该关键字说明你已经有一个私钥了，就算无脑按回车（默认会跳过）也不要无脑按y继续。

1
2
3
# 这里的email并不一定要与上面的相同，同样也可以是任何邮箱
# 而且邮箱不会影响使用，随便编一个也是可以的，但是太多不好管理
ssh-keygen -C "your_github_email@gmail.com"

命令会询问你输入 passphrase，我们不管，直接回车就好。

默认情况下，ssh-keygen命令会在~/.ssh/目录下生成id_rsa和id_rsa.pub两个文件。

Windows下可以通过复制%UserProfile%\.ssh\到资源管理器访问文件夹，Linux下可以使用cd ~/.ssh访问。

也可以使用-f选项指定路径，如果指定那么则是path/to/name和path/to/name.pub两个文件。

第三步 将公钥添加到GitHub

前往上一步生成的目录，使用文本编辑器打开带有.pub后缀的文件，会看到一行文字，这就是要复制到GitHub上的SSH公钥。其类似下面这样

1
ssh-rsa AAAAC3...... your_github_email@gmail.com

复制该行内容到Github SSH and GPG keys 页面，点击 New SSH Key，Title随便输入一点什么，Key则为刚刚复制的那行文字。

第四步 配置SSH

如果在第二步生成密钥对时没有使用-f指定文件名，那么该步骤可以忽略，请直接到下一步。

有两种方法可以配置，使用其一即可。

  • 第一种方法

    使用文本编辑器打开~/.ssh/config文件，在最后面添加如下行。

    1
    2
    3
    4
    5
    Host github.com
        HostName github.com
        User git
        IdentityFile path/to/your/private_key # 请将这里替换为你的私钥
        IdentitiesOnly yes

    ~/.ssh/config文件为ssh使用的配置文件，在这里使用即可让连接到GitHub的命令均使用IdentityFile指定的私钥。

    这种方法是全局生效的，并且对第二种方法有隐性影响。

  • 第二种方法

    在命令行中输入以下命令，注意路径不要有空格等特殊字符，不然引号转义很麻烦。

    1
    git config --global core.sshCommand 'ssh -i path/to/your/private_key'

    这种方式也是全局生效的，不过如果使用了第一种方法配置后，这里的文件使用错误，则会默认使用第一种方法下的IdentityFile，而不会报错。

    如果去掉命令中的--global则可只对某个仓生效，这对使用多个GitHub账号的人而言会方便一些。

第五步 测试

输入以下命令

1
ssh -T git@github.com

如果出现下面的输出，那么就做对了。

1
Hi XXX! You've successfully authenticated, but GitHub does not provide shell access.

如果出现下面的输出，那么就是你的公钥没有配置对，需要重新从第二步开始检查。

1
git@github.com: Permission denied (publickey).

使用GPG签名提交

这里并非必选项，如果只需要连接到GitHub，这里可以不用看了。

在第一步我们发现我们可以随意填写名字和邮箱时，git的身份是很容易伪造的，在互联网下进行合作时，可以使用GPG对自己的提交进行签名，以避免其他人伪造自己的提交。对于初学GitHub的普通人而言，自然没人会伪造你，不过如果公司有要求，或者你意外出名了，就可以使用GPG的方式来签名你的提交。

GPG全程为GNU Privacy Guard，虽然直译为隐私保护，但目前它的主要用法是防止伪造身份。与实名制不同，这种方式下使用者身份只与一个私钥文件挂钩，而不与任何现实身份挂钩，只要私钥不泄露，身份就不会被伪造，同时也可以保证隐私。可以认为谁有这个私钥，谁就有这个身份。

这里的教程只教GPG的最基本用法，GPG的套路可以很复杂，但这里进行了尽可能的简化。

第一步 安装GPG

没什么好说的，apt、yum、brew 之类的命令install就行，Windows用户可以安装Gpg4win。不会可以去Google，这不是本文章的重点。

对于Windows用户，需要额外多执行一条命令以使得Git适配GPG，这是因为安装Git时，其自带的MinGW环境自带了一个MinGW版GPG，这会导致git优先使用自带的GPG，而非你安装的GPG，当然，你也可以通过调整PATH环境变量的方式直接使用git自带的GPG，应该也是一种可行的方案。Linux / Mac 用户不需要。

1
2
3
where.exe gpg
# 在获得了目录以后，需要将下面的字符串换成where输出的位置。
git config --global gpg.program "C:\Program Files (x86)\GnuPG\bin\gpg.exe"

第二步 生成密钥对

很遗憾，GPG并不能直接使用SSH的私钥，所以除了上面的SSH密钥，还需要额外管理一套GPG密钥。相比SSH密钥，GPG密钥的自定义项会比较多。

使用gpg --full-generate-key生成一个新密钥对，这会交互式地引导用户创建一个密钥对。

过程中会要求输入名字和邮箱，这里的邮箱必须是一个你能够收到邮件的邮箱，因为GitHub要使用该邮箱做认证。

中间可能需要你输入passphrase，和SSH私钥类似，我们也可以不输入直接点击OK（Windows，Linux下回车），这样可以创建一个无密码保护的密钥。虽然理论上无密码保护会导致黑客攻破设备时私钥被直接窃取，但以我的经验看，比起电脑被黑客攻击的概率，密码把未来的我自己防住的概率要高得多得多，所以除非有足够的准备，否则不建议大家输入密码，不然将来会后悔的。

剩下的去看GitHub去吧，没什么大坑了。

Telling Git about your signing key - GitHub Docs

Python排序详解

Python中的排序方法

原生Python中有两种常见的排序方法，分别是 list.sort()与sorted()内置函数。

其中，list.sort()是列表的排序方法，是一个原地排序方法，使用尽可能少的额外空间，它只能在列表上使用。

而sorted()则会返回一个已经排好序的列表，其参数可以是任何可迭代对象，无论是列表、元组、字符串、range、字典、甚至使用函数生成的迭代器，只要其是一个可迭代对象，并且返回的对象可以比较，那就可以进行排序。其行为可以用以下代码模拟。

1
2
3
4
def sorted(iterable):
    tmp = list(iterable)
    tmp.sort()
    return tmp

所以当传入字典参数时，其返回的结果不会包括字典的value，而仅会包括字典的key。

排序的基本规则

排序算法

Python中的排序算法为TimSort，这种排序算法是一种稳定的排序算法，同时其保证最坏时间复杂度为$O(n log(n))$。而在数组已经有序时，其时间复杂度能低至$O(n)$​，即每个元素仅比较一次。

稳定意味着对于在比较中相等的值，在排序后依然保持原来的顺序不变。

排序会优先使用小于进行

Python在排序时，两个对象的比较会优先使用<进行比较，而如果<没有定义，则会尝试使用>进行比较，如果这两者都没有定义，那么就会抛出一个TypeError，表示不能对此进行排序。

排序的两个关键字参数

无论是list.sort()还是sorted()，其都接受两个关键字参数key和reverse。

key参数

key参数可以决定Python如何获取可比较的对象。当传入此参数时，Python比较时不会简单的进行 a<b这种方式，而是会进行key(a) < key(b)的比较，这可以让我们操作比较的细节。

例如，传入abs可以让Python按绝对值进行排序。

1
2
sorted([-1,-5,3,4])          # [-5, -1, 3, 4]
sorted([-1,-5,3,4], key=abs) # [-1, 3, 4, -5]

也可以通过匿名函数，让排序只对元组的某一个位置比较进行排序，而不是从头开始比较。

1
2
3
lst = [("Alice", 27), ("Bob", 26), ("Altman", 26)]
sorted(lst)                     # [('Alice', 27), ('Altman', 26), ('Bob', 26)]
sorted(lst, key=lambda x: x[1]) # [('Bob', 26), ('Altman', 26), ('Alice', 27)]

也可以巧妙的通过加符号而让一个升序，一个降序。

1
2
lst = [(1, 3), (5, 6), (1, 4)]
sorted(lst, key=lambda x: (x[0], -x[1]))  # [(1, 4), (1, 3), (5, 6)]

来自一个B站用户的想法：想让元组中第一个数字升序，第二个字符串降序。由于字符串不能使用负号反转比较结果，我们可以反转整数的比较结果，让第一个数字降序，第二个字符串升序，并且指示反转排序结果，可以看到这种取巧的方式也依然可行且为稳定排序。

1
2
3
lst = [(1, 'a', 'first'), (1, 'b'), (1, 'a', 'second'), (2, 'a')]
sorted(lst, key=lambda x: (-x[0], x[1]), reverse=True)
# [(1, 'b'), (1, 'a', 'first'), (1, 'a', 'second'), (2, 'a')]

其他使用方式

类似的，可以使用匿名函数对字典的某个键或者对象的某个属性进行排序，以让不可比较对象能够通过某种方式进行比较。

对于列表中被排序的每个元素，即使多次被比较，key函数也只会被调用一次。而显然，为了排序，key函数也至少会被调用一次。

Python标准库functools中有一个cmp_to_key函数，可以让大部分情况下自定义比较方法更简单，我们后文会提到。

注意事项

对于list.sort()而言，CPython中有一个实现细节：在排序过程中，会将列表的长度设为0，并将内容指针设为空。同时，在排序结束时，会检查列表是否被修改过。

如果排序时通过key函数访问原始的列表，打印该列表可以发现该列表的内容为空。如果此时在key函数中修改了列表，则可能会出现ValueError: list modified during sort，即使修改进行了list.clear()操作仍然会导致该问题。除非并未实际修改（如my_list.extend([])）,该行为可能会因为版本不同而不同，我们需要知道的只是如果排序中需要访问列表，我们需要访问列表的复制。

当然，不进行原地排序的sorted()不会受到该特性的影响。

reverse参数

reverse参数比较简单，就是反向排序，默认的排序方案是小的排在前面，通过指定reverse=True，可以让大的排在前面。和先进行排序，再进行反转不同的是，这种排序方式仍然是稳定的。

富比较

__cmp__与富比较方法

使用C语言的朋友们一定知道，在C中的各类比较并非通过任何运算符重载，而通常是通过一个cmp函数进行比较。我们以strcmp(char* str1, char* str2) 为例，其可能返回0、-1或1，分别代表str1 == str2，str1<str2, str1>str2。这种比较方式的优点是仅需要实现一个比较函数，就可以完成排序、寻找最大值等多种需要比较的场合，C++也于C++20引入了<=>（三向比较运算符）支持这种方式。

事实上，在Python2时代，Python也使用这种方式来重载所有比较运算符，然而这有一个很难注意到的问题：这里的比较结果只能为0、大于0或小于0，也就是说一个值和另一个值比较，不是大于或小于，就是等于，但是也有一些时候我们的数据不是全序的，会需要既不大于，也不小于，也不等于的比较，此时__cmp__方法就无能为力了。

上述情况中最常见的属于浮点数NaN，我们来看代码。

1
2
3
4
5
6
7
nan = float('nan')
print("nan == nan", nan == nan)  # False
print("nan > nan", nan > nan)  # False
print("nan < nan", nan < nan)  # False
print("nan >= nan", nan >= nan)  # False
print("nan <= nan", nan <= nan)  # False
print("nan != nan", nan != nan)  # True

类似的，还有SQL中的NULL比较等，也都不是cmp函数可以覆盖的范围。

所以在Python3中，Python不再使用__cmp__运算符，而是将其分为了6个富比较运算符。

  • __eq__ 重载==运算符，a == b相当于a.__eq__(b)
  • __ne__ 重载!=运算符，a != b相当于a.__ne__(b)
  • __lt__ 重载<运算符，a < b相当于a.__lt__(b)
  • __gt__ 重载>运算符，a > b相当于a.__gt__(b)
  • __le__ 重载<=运算符，a <= b相当于a.__le__(b)
  • __ge__ 重载>=运算符，a >= b相当于a.__ge__(b)

所以在Python中，我们也不是不可能可能见到a == b and a != b为真的情况，不过应该没人会写这种代码。我们也可能见到 a==b的返回值并非bool值的情况，而这种情况常常发生在numpy中。

标准库中的cmp_to_key

默认情况下，这个函数由C语言实现以提高速度，不过标准库中仍然提供了纯Python实现的fallback，该实现和C语言实现具有同样的行为，并且这个实现很简单，我们直接看实现源码。

（是的，C语言实现中也使用了对象和0的Rich Compare，而并非仅接受数字的比较，所以你可以在cmp函数中返回任何可以和0相比较的对象。）

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
def cmp_to_key(mycmp):
    """Convert a cmp= function into a key= function"""
    class K(object):
        __slots__ = ['obj']
        def __init__(self, obj):
            self.obj = obj
        def __lt__(self, other):
            return mycmp(self.obj, other.obj) < 0
        def __gt__(self, other):
            return mycmp(self.obj, other.obj) > 0
        def __eq__(self, other):
            return mycmp(self.obj, other.obj) == 0
        def __le__(self, other):
            return mycmp(self.obj, other.obj) <= 0
        def __ge__(self, other):
            return mycmp(self.obj, other.obj) >= 0
        __hash__ = None
    return K

不知道该说啥，着实是简单了点，让我们看一个实际案例：让字符串升序排在前面，让数字降序排在后面。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
from functools import cmp_to_key


def cmp(a, b):  # 字符串升序排前面，数字降序排后面
    # True 和 False几乎在任何情况下均可以当作 1 和 0 看待
    if isinstance(a, str) and isinstance(b, str):
        return (a > b) - (a < b) # True - False = 1, False - True = -1
    elif isinstance(a, int) and isinstance(b, int):
        return (a < b) - (a > b)
    else:  # 类型不同时，字符串要排前面就需要比其他类型小，所以返回-1
        if isinstance(a, str):
            return -1
        else:
            return 1


def main():
    lst = [3, 2, 1, 'a', 'b', 'c']
    lst.sort(key=cmp_to_key(cmp))
    print(lst)


if __name__ == '__main__':
    main()

记一次C++错误静态链接导致进程被Abort

静态链接符号重名导致的Abort

本质上来说，这就是编译时连接器ld没有发现符号名冲突，进而导致运行时链接器ld-linux-$(arch).so将同一个对象初始化了两遍，并且在该对象上调用了两遍析构函数，进而导致析构时引发double free。

需要注意的是，只有 *nux 系统中才有这种问题，Windows 系统中并不存在该问题，因为 Windows 切实处理好了所有被静态链接的库，会在内存中加载相同的副本。

由于涉及到链接器的细节，所以我将仔细区分编译式链接器和运行式链接器。

在编译 glog、gtest 时，你是否遇到过无端出现 Aborted的情况？根据退出消息，你的进程出现了 double free。然而，即使你把代码审查了个遍，仍然没有发现究竟在哪里发生了 double free。这时就需要考虑一下代码之外的问题，比如这可能是链接器导致的。

在编译时，你的主程序编译时链接了一个动态库。而你的主程序和动态库都编译时链接了一个静态库，而这个静态库又是由C++编写的，且拥有非static的、析构函数中需要调用free(void *)的变量，此时就有不小的发生 double free 以及内存泄漏的风险。而对于static变量，则只有内存泄露的问题，不过通常这种程度的泄露不会有任何问题。

为什么没有在编译时发现

在编译时链接器进行链接时，如果是 .o 文件，那么当符号发生冲突时，编译时链接器将会报告链接错误。然而，如果是.a 或 .so 文件，编译时链接器会忽略第一个符号以后的其他符号。

原因

C/C++均使用符号作为启动时期定位全局变量内存地址的方式，在程序执行运行时动态链接时，运行时链接器会将变量名与地址空间相关联，同时会执行对应动态链接库的初始化函数，并且在程序结束时会执行库的卸载回调函数。

对于 c 语言库而言，如果不对函数使用特殊标记__attribute__((constructor)) / __attribute__((destructor))，那么就没有额外的初始化函数及拆卸回调要执行。但是对于 c++ 而言，在加载动态库以及程序退出时，均会执行全局变量的构造及析构函数，并且每一个动态库都会执行一次。然而，由于编译时链接器仅链接了第一个符号，两次构造也均会在同一个内存地址上进行构造和析构，发生两次构造，只会导致内存泄露。然而，发生两次析构则会导致 double free。

以std::string为例，如果在cpp文件中写了全局变量std::string g_abort_str = "0123456789abcdef"，运行时动态链接器会为每个so中的该符号执行一次构造函数，然而，对于导出符号而言，即使同名符号处于两个不同的动态链接库中，最终仍然会映射到内存当中的同一地址，该地址会被初始化两次，显然，第一次初始化的使用的内存发生了内存泄露。而当程序退出，运行时链接器执行清理时，同样会对该地址执行两次析构函数，第一次析构函数当然可以正常释放内存，而第二次析构函数执行时，由于该内存已经在第一次析构函数当中释放，再次尝试释放该内存则会导致 double free。注意字符串长度如果小于16个字节，则会因为SSO优化而不会有该问题。

如何避免

下面我列举几种可能的规避方式。正确使用以下的任何一种方法都可以规避该问题。

  1. 在编译选项中加入-Wl,--exclude-libs,<your_static_lib>

    -Wl为gcc 传给静态链接器ld的选项。gcc -Wl,aa,bbb,cde在gcc传给ld时，会变为ld aaa bbb cde这种形式。

    需要注意的是这里的lib名是需要lib前缀的。

    通常情况下，一个动态库链接静态库后，这个动态库也会继承静态库当中的导出符号（即非static符号），而使用该链接选项，则可以让动态库在链接静态库后将静态库中的导出符号改为非导出符号，相当链接时为静态库中的所有函数、变量均加上了 static。这样所有静态库符号都保存在本地，同样也不会被主程序或其他动态链接库劫持符号。

  2. 在编译选项中加入-Wl,-Bsymbolic。（不推荐）

    这会使共享库中的全局符号优先绑定到本地(locally)，不会被主程序或其他共享库劫持。然而，这也会导致共享库出现一些其他的行为差异。

  3. 使用dlopen

    使用dlopen打开动态库，例如dlopen("libconflict.so", RTLD_LOCAL | RTLD_LAZY);，RTLD_LAZY同样也会保证该 so 中的符号不被劫持。

常见Hash算法分类

哈希算法是什么？

哈希算法是一类将数据映射到固定长度输出的算法。它满足两个最基本的性质。

  1. 输出长度是有限的
  2. 同样的数据输入产生同样的输出。

这里的输出长度有限就像是的成语一样，无论故事长短，最终都会简化为四个字的成语。类似的，哈希函数也会生成固定长度的输出，比如 md5总是会产生128比特，也就是32个16进制字符的输出。而SHA-1算法则总是会生成160比特的数据。

常见哈希算法的分类

哈希算法根据用途不同，在多种不同的特征都有差异。其中我们经常看到的 md5、SHA-1 算法都属于加密哈希函数。

加密哈希

加密哈希(Cryptographic hash)在满足上述哈希算法的要求的情况下，又额外满足三个条件。

抗原像攻击、抗次原像攻击、抗碰撞性。

  1. 抗原像攻击

    给定一个哈希值 $y$，很难找到一个消息$x$，使得 $h(x)=y$。

    例如，我给定一个文件的SHA-1值0880c6327abd62fdc94aa09d7ba1cd994ed90d12，除了暴力穷举以外，没有其他更有效的方法找到一个与其SHA-1相同的文件。

  2. 抗次原像攻击

    给定一个消息$x_1$，很难找到另一个消息$x_2$使得 $h(x_1) = h(x_2)$

    例如，123456的SHA-1为7c4a8d09ca3762af61e59520943dc26494f8941b，同样除了暴力穷举外，很难再找到另一个文件使得输出也为这个值。

  3. 抗碰撞性

    很难找到两个不同的输入 $x_1$和 $x_2$，使得 $h(x_1) = h(x_2)$

    例如，对于你电脑里的任意两个不同的文件，它们的 SHA-256 值都互不相同。

需要注意的是，对于任何哈希函数而言，碰撞都是必然的。根据我们小学就学过的鸽笼原理，十只鸽子放入九个鸽笼，那么必然有一个鸽笼有着一只以上的鸽子。像上面例子中提到的 SHA-1 算法，其输出长度只有160比特，而对于所有大小为 1KB 的文件而言，平均其每个哈希值就对应了$2^{8032}$个文件。这么多的文件，不可能找不到原像、第二原相，所以这里说的仅仅是没有比暴力穷举更快的方式找到两个消息，使它们的哈希值相同。

常见的加密哈希有 md5、SHA 家族，同时也有bcrypt 、blake、国密sm3等不太常见的哈希算法。不过MD5、SHA1目前都已经被证明为不安全的哈希函数，它们都不满足特定场景下上述的抗第二原像攻击的性质，目前已经逐渐被更新、输出更长的加密哈希取代。不过在假设没有被攻击的情况下（大多数情况下都可以做这种假设），这些哈希函数仍然可以用来校验文件的完整性。

非加密哈希

很多哈希函数并没有显著的特点，他们的目的仅仅是为了更均匀地输出哈希值。这些没有显著特点的，且不符合加密哈希要求的，统称为非加密哈希。

大部分编程语言中的哈希函数都是非加密哈希，这些哈希函数主要用于为 map 数据结构提供基础能力，所以快速是他们的主要目的。不过为了防止hash DoS 攻击，一些编程语言（比如 Rust），也采用了加密哈希，以降低一点速度为代价，避免哈希表因恶意攻击而进入最坏情况，导致拒绝服务攻击。

滚动哈希

哈希函数理论上可以接受无限长的输入，虽然常用的一些哈希函数可以接受的输入有限，但这些限制也远远超过了目前文件的最大大小。但是滚动哈希的输入是有限长度的。它有一个窗口，每当新数据进入这个窗口时，滚动哈希就会“遗忘”掉老数据，并产生一个新哈希值。例如为12345678计算窗口大小为4的滚动哈希，则会先计算1234的哈希值，然后计算2345、3456直到5678。

显然，普通的哈希函数也可以做到这一点，例如下面的代码。

1
2
3
4
import hashlib
data = b"1234567890abcdefghijklmnopqrstuvwxyz"
for i in range(len(data) - 8):
    print(data[i:i+8], hashlib.sha1(data[i:i+8]).hexdigest())

然而，普通的哈希函数，窗口每滑动一次，就需要将窗口内的全部数据重新计算。设窗口的大小为 $w$ 数据的大小为 $m$，显然无论如何，其时间复杂度都为$O(mk)$，而滚动哈希的设计，会让窗口向前滑动时，仅需要计算新输入的那部分数据，将时间复杂度缩小为了 $O(w+m)$。滚动哈希通常被用于进行字符串搜索，使用它可以在 $O(n)$ 时间内完成大量字符串的预过滤，提升后续的查找效率。

媒体哈希

大部分哈希函数的设计原则是相似的输入产生完全不同的输出，以尽可能达到让输出均匀分布、减少冲突的目的。但还有一些哈希函数是为搜索优化的哈希函数，相似的输入会产生相似或者相同的输出。而通过对比哈希值的相似性，我们可以间接得知输入的相似性。

例如，图片领域有直方图哈希、aHash、pHash、dHash，而音频领域也有音频指纹等。我们平常使用的以图搜图、听歌识曲等功能，就用到了这些技术。

GeoHash

GeoHash是对地理位置进行哈希。不过这种哈希函数与其说是哈希，更像是对地理位置按块进行编码。在划分好块后，每一个块都唯一对应一个哈希，而每一个哈希也唯一对应一个块。这些哈希值通常共享前缀越长，则地理上的位置就越接近，不过反之则不然，即使地理上的位置非常接近，也有可能拥有完全不同的前缀。使用这种哈希，可以让搜索特定的地理位置变得更加快速和准确。

预处理、编译、链接都在做什么

最近先写一个简单的，之后再写复杂的。

在初学C语言时，我们往往被告知C语言的编译过程是预处理、编译和链接，那么这些过程都是什么呢？

下面以Linux下常用的gcc编译器举例说明我们平时见到的这些过程都是什么。

gcc原名GNU C Compiler，后改名 GNU Compiler Collection，下面的介绍也能让你明白为什么gcc换了名字。

预处理

我们先写一个入门C语言程序hello.c。这里puts的功能与printf类似，但是其只能输出纯字符串，不能像printf那样输出其他变量，使用puts代替printf是因为printf相关的优化较多且无法关闭，实际操作和理论一致性较差。

1
2
3
4
5
6
7
8
#include <stdio.h>

#define OK 0

int main() {
    puts("Hello, World!\n");
    return OK;
}

在C语言中，一些以#开头的行，被称为预处理指令，它们通常没有任何缩进，可以出现在文件中的任意一行，一些指令会被预处理器处理，最后生成新的.i的文本文件，这些.i文件会实际上参与下一步 - 编译。

预处理指令主要有以下功能

  • 处理包含指令。上面代码中相当于将 stdio.h内的所有内容粘贴到到#include所在的行并删除该行，当然如果stdio.h中也有#include指令那么它也会被处理，直到没有该指令。
  • 处理宏。例如将上面代码中的OK替换为0
  • 处理条件编译指令#if、#ifdef等
  • 更改编译器的行为（如字节对齐）

需要注意的是，预处理器并不会处理所有的预处理指令。有一些虽然定义上是预处理指令，但实际上会在编译阶段起作用，比如#pragma指令通常在编译期生效，在.i文件中你仍然可以看到这些指令。

汇编

通常C编译器并不直接从C代码生成机器指令，而是会有一个生成汇编代码的步骤，再通过汇编器将汇编代码编译为机器代码。这种方式方便了程序员使用内联汇编。由于C编译器生成的汇编代码有缩进格式，所以往往能见到使用多行内联汇编时会在\n后加\t（不加也一样）。该阶段生成的代码人类仍然可读。查看改代码可以发现头文件的大部分内容都已经消失，只剩下实际使用的puts这一个函数的名称了。

编译

汇编器会将刚才生成的汇编代码转换为机器可执行的代码。它会生成.o文件，此时该文件人类已经不可读，但其仍然和汇编文件基本对应，可以使用objdump工具查看其内容。

链接

链接是生成可执行程序的最后一步，它被用于处理符号引用。我们平时使用的printf、puts均会在此处被处理。链接分为动态链接和静态链接，通常我们使用的都是动态链接方式。

动态链接需要分别在两个阶段进行：编译时与运行时（这里说的编译是指源代码到生成可执行文件的整个流程，通常编译指的都是这个流程）。编译时的链接用于指定某个符号在哪个动态库中，而运行时链接则为真正在内存中装载函数和变量。

原子计数、缓存行、争用与总线锁

原子计数、缓存争用与性能问题

操作系统会在什么时候进行线程切换

想必熟背八股的朋友们都知道，操作系统进行线程切换时无非是两种情况：线程时间片用尽和线程主动让出执行权。

线程主动让出执行权时包括等待锁、等待IO操作或者是单纯的sleep，这里我们主要讨论的不是这个问题。

而操作系统是如何知道线程的时间片用尽的呢？实际上，操作系统是根据时钟中断来确认时间片是否用尽的。时钟中断的触发频率通常为100-1000Hz，这在Linux系统中由编译时决定，可以使用zcat /proc/config.gz | grep CONFIG_HZ来查看时钟中断的频率。

比如我的WSL，获取到的结果为

1
2
3
4
5
6
7
qy@localhost ~/test_c$ zcat /proc/config.gz |grep CONFIG_HZ
# CONFIG_HZ_PERIODIC is not set
CONFIG_HZ_100=y
# CONFIG_HZ_250 is not set
# CONFIG_HZ_300 is not set
# CONFIG_HZ_1000 is not set
CONFIG_HZ=100

这代表我的电脑的时钟中断频率为100Hz，也即每秒钟会有100次时钟中断。操作系统会每秒会进行100次的时钟处理，这其中包括更新系统时间、检查线程时间片是否用尽，如果用尽则调度线程、更新一些系统计数（如load average）等等操作。

CPU会在什么时候处理中断

中断分为硬中断(Hardware interrupt)和软中断(Software interrupt)，顾名思义，硬中断是由计算机的外围硬件引发的中断，而软中断则是由软件自身引发的中断。而时钟中断则属于一种硬中断。

硬中断

由于硬中断并非由CPU内部产生，其到达的时机不固定，CPU不能同时处理指令和中断，所以CPU会将硬中断暂存，每当执行一条指令前，CPU会检查中断寄存器，如果发现有中断则会执行中断处理程序。

这里我们可以看到CPU的指令执行本身是原子的，一条指令过程中并不会被硬中断打断，也就意味着不会被操作系统调度。

软中断

软中断即为程序通过指令触发的中断，除了通过int指令手动调用中断外，其他指令也可能会引起软中断，比如内存访问引起的缺页中断，除法指令引起的除0中断等，这些中断都在指令执行中发生，而具体如何处理取决于操作系统和程序设计。

多核下的竞争冒险

我们来看一段在x86上的C代码，如无特殊说明，这些代码都采用gcc -O2编译。

多核读写同一个变量

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
#include<stdio.h>
#include<stdint.h>
#include<pthread.h>
// TOTAL 这个数字在我的i7-7700HQ上大部分时间能跑完示例，如果你的CPU性能太好可以酌情加一些
#define TOTAL (100000000)
__attribute__((aligned(4))) static uint32_t counter = 0;

void *add_addl(void *ctx) {
    for (int i = 0; i < TOTAL; i++) {
        // 一条汇编指令，没有锁，也没有原子计数
        asm("addl $0x1, %0":"+m"(counter));
        asm(""); // 空指令
    }
    return NULL;
}

int main() {
    pthread_t t1;
    pthread_t t2;
    pthread_create(&t1, NULL, add_addl, NULL);
    pthread_create(&t2, NULL, add_addl, NULL);
    pthread_join(t1, NULL);
    pthread_join(t2, NULL);
    printf("end thread t1 and t2\n");
    printf("counter = %u\n", counter);
    return 0;
}

在执行的最后，其会有什么结果呢？刚刚我们知道，CPU在执行单条指令时不会被操作系统中断，那么结果会是counter = 200000000吗？不幸的是，在大多数CPU下，其结果不会是这个数字，和所有常见的竞争冒险类似，它的结果也是比200000000小的。但如果addl指令是不会被操作系统中断的，那么还有什么会是导致竞争冒险的原因呢？

显然，是多核CPU的导致了这个问题。我们知道，多核CPU是不共享L1、L2缓存的，这样就会导致虽然每个核心上计数器都是原子的，但是由于缓存的不一致，导致最终加起来的总数不一致。不过在单核CPU下，或者是使用某些方式将线程限制在仅在一个核心中运行时，则不会有这种问题。

那么，是因为使用了过期的缓存行吗？将上面的的代码略作修改，修改为下面的代码。

多核读写同一缓存行的不同变量

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
#include<stdio.h>
#include<stdint.h>
#include<pthread.h>
// TOTAL 这个数字在我的i7-7700HQ上大部分时间能跑完示例，如果你的CPU性能太好可以酌情加一些
#define TOTAL (100000000)
// aligned(64)保证其必然在同一个缓存行内，虽然不写大概率也会在同一个缓存行内
__attribute__((aligned(64))) static uint32_t counter[2] = {0};

void *add_addl_1(void *ctx) {
    for (int i = 0; i < TOTAL; i++) {
        // 和上面一样，但是这是在同一个缓存行内的两个counter
        asm("addl $0x1, %0":"+m"(counter[0]));
        asm("");
    }
    return NULL;
}

void *add_addl_2(void *ctx) {
    for (int i = 0; i < TOTAL; i++) {
        // 同一个缓存行内的另一个计数器
        asm("addl $0x1, %0":"+m"(counter[1]));
        asm("");
    }
    return NULL;
}

int main() {
    pthread_t t1;
    pthread_t t2;
    pthread_create(&t1, NULL, add_addl_1, NULL);
    pthread_create(&t2, NULL, add_addl_2, NULL);
    pthread_join(t1, NULL);
    pthread_join(t2, NULL);
    printf("end thread t1 and t2\n");
    printf("counter[0] = %u\n", counter[0]);
    printf("counter[1] = %u\n", counter[1]);
    return 0;
}

运行这段代码，我们会惊讶的发现，其运行结果为两者都是100000000，这可以证明CPU并非是使用了过期的缓存行数据。这里我们就要清楚缓存刷新原理与CPU指令执行的局限性。

即使CPU的单个指令看似是原子的，但是CPU实际上仍然不能直接操作主存，addl指令在实现内部仍然是读内存-增加-写回内存三步走，这也就可以解释为什么单指令多核多线程的不一致了。

缓存争用与总线锁

MESI 协议

如今CPU的缓存刷新方式是使用MESI协议，MESI 协议是 4 个状态单词的开头字母缩写，用于标记缓存行的四种不同状态，其含义分别为：

  • Modified，已修改：数据已被该核心修改，但还未写回主存（共享区域）。
  • Exclusive，独占：其他核心的缓存中没有该数据，CPU可以随意对该缓存行进行读写。
  • Shared，共享：其他核心的缓存行中也有该数据，但所有核心均未对该缓存行的数据进行修改。
  • Invalid，已失效：其他核心写入了该数据，这个缓存行的内容已经被修改过了。

现在让我们来看看MESI协议下，上面两种情况是CPU是如何工作的呢？

假设我们的counter的起始地址总是 0x1000，这样可以简化我们的部分讨论，并且和实际情况相差不大。

  • 多核读写同一个变量

    由于CPU0和CPU1都需要使用0x1000的数据，我们几乎可以断定在0x1000所在的缓存行中几乎不可能有Exclusive状态的时间。

    1. CPU1等待0x1000缓存行为Shared，读取，寄存器中为0

    2. CPU2等待0x1000缓存行为Shared，读取，寄存器中为0

      注意到此时CPU1和CPU2同时读取了同一个变量，目前其内部的寄存器值也相同

    3. CPU1为该寄存器+1，CPU2也为该寄存器+1

    4. CPU1将增加后的数值1写回0x1000，此时CPU1的缓存行为Modified，CPU2的缓存行为Invalid，内存中值为1

    5. CPU2等待缓存行刷新为Shared，并将增加后的数值1写回0x1000，此时CPU2的缓存行为Modified，CPU1的缓存行为Invalid，内存值仍然为1

    由此可见即使CPU只会写Shared的缓存行，仍然会出现竞争冒险问题，因为多核CPU的读写通常是不会被串行化的，这也就导致了在指令执行过程中数据变为旧数据的情况。

  • 多核读写同一缓存行内的不同变量

    1. CPU1等待0x1000缓存行为Shared，读取，寄存器中为0

    2. CPU2等待0x1004缓存行为Shared，读取，寄存器中为0

      注意到此时CPU1和CPU2同时读取了不同的变量，但它们都在同一个缓存行

    3. CPU1为该寄存器+1，CPU2也为该寄存器+1

    4. CPU1将增加后的数值1写回0x1000，此时CPU1的缓存行为Modified，CPU2的缓存行为Invalid，内存中值为1

    5. CPU2等待缓存行刷新为Shared，并将增加后的数值1写回0x1004，此时CPU2的缓存行为Modified，CPU1的缓存行为Invalid，内存值为1，其不会使用老值。

MOESI/MESIF 协议

可以看到，MESI协议下，每当数据脏时，都需要重新写回主存才能够让其他核心获得新数据，然而可以想到的是，CPU内部核心之间传递缓存行的速率会高于CPU与主存之间的通信效率。这也就诞生了MOESI和MESIF两个协议。

与MESI协议类似，但它们各增加了一个状态，增加的状态是对MESI协议的补充。协议的字母顺序仅仅是为了方便发音，其顺序并无含义。

  • Owned，拥有：MESI协议下，当数据写入缓存时，其他核心的该缓存都会变为Invalid，这样就导致所有使用该数据的核心一个需要写回主存，而剩下的则需要从主存拿回数据。Owned可以保持其他核心的Shared状态，但Owned的核心可以写入该缓存，并在写入后在CPU内部广播该写入，其他核心无需从主存中再次获取，加快了缓存更新的速度。 AMD、ARM主要使用该技术。
  • Forward，转发：与Owned类似，也是可以让缓存之间通信，而不通过主存的方式。但是F状态的是干净的缓存，该缓存由CPU内的L3缓存提供。这样当多个核心读取同一个内存地址时可以不用频繁访问主存。Intel主要使用该技术。

这里的优化对接下来的原理几乎没什么影响。

缓存争用带来的性能问题

上面的例子可以看到，CPU会频繁的争用同一个内存地址，这样在读取和写入时都会引起CPU等待缓存刷新，而这种等待会导致CPU无法执行其他任务，因为指令还未完成，操作系统也无法有效利用这些等待时间，是实打实的多占用了CPU时间。然而这种问题也是可以轻易规避的。显然，只要我们的变量不在同一缓存行，那么问题就迎刃而解。现代CPU的缓存大小通常为64字节，所以只要让变量间隔64字节，那么两个变量就不会映射在同一个缓存行，通常也不会被组相联映射在同一个缓存行里。

让我们先来实际测试一下CPU缓存征用带来的性能下降。我们对 多核读写同一缓存行的不同变量 这里的代码再稍作修改，改为下面的代码。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
#include<stdio.h>
#include<stdint.h>
#include<pthread.h>
// TOTAL 这个数字在我的i7-7700HQ上大部分时间能跑完示例，如果你的CPU性能太好可以酌情加一些
#define TOTAL (100000000)
// aligned(64)保证其必然在同一个缓存行内，虽然不写大概率也会在同一个缓存行内，64/4=16，所以我们申请17个int32，分别增加第一个和最后一个
__attribute__((aligned(64))) static uint32_t counter[17] = {0};

void *add_addl_1(void *ctx) {
    for (int i = 0; i < TOTAL; i++) {
        // 和上面一样，但是这是在同一个缓存行内的两个counter
        asm("addl $0x1, %0":"+m"(counter[0]));
        asm("");
    }
    return NULL;
}

void *add_addl_2(void *ctx) {
    for (int i = 0; i < TOTAL; i++) {
        // 同一个缓存行内的另一个计数器
        asm("addl $0x1, %0":"+m"(counter[16]));
        asm("");
    }
    return NULL;
}

int main() {
    pthread_t t1;
    pthread_t t2;
    pthread_create(&t1, NULL, add_addl_1, NULL);
    pthread_create(&t2, NULL, add_addl_2, NULL);
    pthread_join(t1, NULL);
    pthread_join(t2, NULL);
    printf("end thread t1 and t2\n");
    printf("counter[0]  = %u\n", counter[0]);
    printf("counter[16] = %u\n", counter[16]);
    return 0;
}

我们让两个线程分别使用两个缓存行，这样就可以尽量保证在每个CPU核心中，它们对缓存行都是独占状态，让我们来看看两个程序运行时间的差异。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
# 无缓存行争用版本
end thread t1 and t2
counter[0]  = 100000000
counter[16] = 100000000

real    0m0.181s
user    0m0.336s
sys     0m0.000s

# ============================================
#有缓存行争用版本
end thread t1 and t2
counter[0] = 100000000
counter[1] = 100000000

real    0m0.290s
user    0m0.551s
sys     0m0.010s

我们可以看到缓存行争用在极端情况下带来了60%的额外性能消耗。

总线锁

一些熟悉X86汇编的朋友们可能注意到，我在所有的操作里都没有使用lock这一个X86指令前缀，前面我说的是X86无锁的情况下，如果带上了lock前缀，那么就可以保证是原子操作。然而同样的操作，由于需要提供额外的顺序保障，会有更多的性能消耗。

锁与原子操作

互斥器 (mutex)

CAS原子操作

FAA原子操作

LL/SC原子操作

强弱内存模型架构

更高效的多线程

由此可见，多线程中想要效率更高，除了减少锁的使用，还应该尽量避免将写入较多的多线程的数据放入同一个缓存行中。对于高负载线程，应尽量每个线程绑定一个CPU核心执行，这样可以避免线程颠簸，对于多核CPU而言可能还好，但对于服务器上的多个CPU而言，线程颠簸的代价相对就大得多，因为这意味着要完全从内存中转移线程常用的数据，CPU中的缓存将彻底失效。

基于Linux对栈的分析

本文以Linux系统为例，简析栈究竟是什么东西。其中的部分思想也可以用于其他操作系统。

栈是什么

函数运行的栈是计算机内存中的一种数据结构，用于管理函数调用和执行过程中的局部变量、参数、返回地址以及执行上下文。

但无论在什么情况下，栈都是一块内存。或许是一块物理内存，或许是通过mmap映射出来的虚拟内存，又或者是操作系统通过某种方式保留的内存。具体是什么需要依据操作系统和架构而定。

栈的内存分配原理

向上增长还是向下增长

有些教程和书中提到栈是向下增长的，堆是向上增长的，很多人不求甚解，就此记了下来，并且会根据猜测（说难听点就是臆想）去理解编译器怎么编译与程序怎么执行。实际上，栈的增长方向取决于CPU架构，而且仅仅是CPU架构中的一个小设定：加速栈存取的指令push会将SP增加还是减少。如果push减少SP，那么就是向下增长。

我们常用的x86架构的CPU，其push会减少rsp寄存器的值，所以其向下增长。而ARM架构的CPU，其并不自动维护栈，所以程序员完全可以选择编译向上增长的操作系统，而做到栈向上增长。类似的，IA64、MIPS架构则是默认向上增长。

为什么通常是向下增长

通过上面的解释，我们知道，栈增长方向并非什么金科玉律，其只是依赖于CPU架构而进行选择罢了。

而为什么我们最广泛使用的X86 CPU会使用向下增长的栈，这个我并没有查到具体的资料。 大体的说，这和早期的CPU与内存的设计有关，有人说是因为CPU要让程序知道有多少空间可以使用，也有人说是为了让程序总能以正数的偏移量访问其栈内部的数据。它并不是一个多么好或者多么坏的设计，向上增长或者向下增长不会对程序的易用性和安全性产生巨大的影响。而这么多年过去了，如此设计原因恐怕也只有其设计者才能知道了。

栈生长方向与栈帧布局

当然还是有人会把栈是向下生长的这种话作为金科玉律，这也是我写这篇文章的主要诱因。有些人不经过实测光凭想象就认为数组也是向下生长的，栈变量也是向下生长的。事实上，在函数内部，数组和栈变量如何布局与栈的生长方向完全没有关系，而是和编译器的实现有关系。是栈帧布局（stack frame layout）相关的内容了。但编译器的栈帧布局并不是我们主要讲的对象，所以这里我们只是做简单的说明。

对于数组而言，它并不是像CPU申请“我要一块栈空间”*n次，而是在函数编译时编译器就已经计算出来这个函数运行需要多少栈空间（这也是为什么C99前数组只能是定长的），并且在运行时提前为其分配对应的栈空间，也即将栈指针下移。

但无论栈是向下增长还是向上增长，数组的第N加一位的地址一定比数组的第N位地址要高。也就是说&arr[n+1] > &arr[n]恒为真，因为实际上arr[n]就是*(arr + n)的语法糖。而对于栈变量的布局，虽然大体上代码从前往后执行，编译器会从上往下排布栈变量，但是这也只是用于没有优化的阶段。如果开启了优化，栈变量连存在与否都不一定，更不要说内存的排布了。相信各位在使用gdb查看O2优化的程序的时候经常会看见<optimized out>，这就说明这个变量被优化没了。而对一些小的函数，其可能根本就没有使用到栈，而是仅仅在寄存器上就把所有的功能都完成并返回了，同样也没有栈变量与栈地址一说。

相关寄存器

X86-64

rsp寄存器

stack pointer. 栈指针寄存器。这个寄存器标识了函数的栈顶在哪里，栈地址中高于这个寄存器的地址空间都是受保护的区域，中断处理程序不会对该区域进行修改。而当你使用push/pop/call/ret/enter/leave等指令时，它们会自动调整该寄存器的值。

特别的，在Linux系统中，其下方的128字节区域内依然是受保护的区域，这被称为red zone。这种处理主要是为了方便优化，使得一些比较小的叶函数（不调用其他函数的函数）不需要使用额外的指令去调整rsp的大小，而可以直接使用那128字节的保留区域。不过Windows没有这种保证，rsp下的栈空间是不稳定的。

rbp寄存器

base pointer. 用于保存栈底指针，但是在任何非零的优化等级且无VLA（可变长数组）的函数内，该寄存器都将被视为通用寄存器使用，并不保存栈底指针。因为一个不含VLA的函数，其所需要的空间大小是固定的。仅需要根据栈顶指针的值和固定大小的偏移量，即可算出栈底指针的值。这样可以节省一次访存操作以及几个指令的开销，同时对正常运行的程序不会造成任何影响，所以即使是最低等级的优化也会将该寄存器用于通用寄存器。

如果在函数中使用了VLA，则依然会保存栈底指针，因为此时函数需要的空间大小不确定。此时需要将原rbp压栈，并将当前的rsp赋值给rbp，然后根据VLA的长度调整rsp的大小。函数返回时将rbp赋值给rsp，然后从栈中取出原rbp，这通常使用leave指令实现。

ARM64

Arm架构的CPU设计上相对来说就好多了，不再有那么多难记住的名字，取而代之的是所有的通用寄存器，都以Xn/Wn来命名。这让我们一眼就能看出哪些是通用寄存器，我们可以修改。

SP寄存器

类似于x86的rsp寄存器，同样有red zone保证。Apple产品会保证该区域不会被中断修改。

Linux 不知道。

我才不会去在ARM上玩Windows……

FP寄存器(X29)

Frame Pointer. 类似于x86的rbp寄存器，同样可用作通用寄存器。

LR寄存器(X30)

存储函数返回地址的寄存器，相较于X86 CPU，这是对叶子函数调用的进一步优化。它甚至不需要访问内存保存PC(rip)了，而是直接将PC转移到LR寄存器，能节省一些内存访问的开销。

为什么栈内存不设计为固定大小

猜测是因为需要支持在程序运行过程中动态调整栈的最大大小，所以没有将其在启动时就设定为固定大小。

但是除了主线程外，其他线程的栈为固定大小。

不同操作系统也有不同的做法，似乎Windows也会自动扩展，但总的来说，这不应该是一个可以假设的前提。

栈安全

与栈相关的漏洞

栈相关的漏洞较为基础，其有一些共同的特点：不正确的内存访问。这其中包括不正确的使用scanf, (f)gets,str(mem)cpy等函数，错误使用数组指针等。不过随着编译器的保护越来越多，静态代码检查越来越完善，很多可能产生漏洞的代码都会产生编译警告，而在生产环境下通常会使用-Wall选项将警告全部转换为错误强迫程序员修改该问题代码。

在计算机设计早期，内存页还不能设置执行权限的时候，栈内代码也可以执行。通过精心编排写入栈中的内容，可以做到任意代码执行，后来有了单独的执行权限，这种风险也就得以消除。

来自gcc的栈保护功能

然而，并非所有的风险都能被静态编译保护消除，仍然有许多风险不能在静态检查时被暴露。为此，gcc设计了栈保护器功能。该功能默认会在gcc认为可能产生漏洞的地方添加一层保护，无论优化级别如何，该选项始终会打开，可以通过-fno-stack-protector选项关闭检查。也可以通过-fstack-protector-all来对所有函数启用该检查，但需要注意的是该检查会堆运行时性能有一定影响，如果不是特别注重安全的情况下仅需默认栈保护即可。

使用Canary进行栈保护

gcc栈保护的原理是选取一个canary值，在函数运行时将其压入栈中，当函数即将返回时，对比栈中的canary的值与之前选取的canary值。如果不同则说明栈被破坏，将会调用__stack_chk_fail终止程序。

Canary的选取

在X86-64架构Linux系统下，gcc11.4版本会选取%fs:40作为canary的值。在Linux下，fs寄存器被glibc用于存储指向TLS(Thread Local Storage)的指针，而其再偏移40字节后则是一段随机值。每个程序每次启动时都不一样，而由于溢出攻击的原理，攻击者往往不能得知该值的内容，所以能够有效检测里用缓冲区漏洞的攻击。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
/* from glibc    sysdeps/x86_64/nptl/tls.h   2023/09/10*/
typedef struct
{
  void *tcb;     /* 0-8 bits */	/* Pointer to the TCB.  Not necessarily the
			   thread descriptor used by libpthread.  */
  dtv_t *dtv;     /* 8-16 bits */
  void *self;     /* 16-24 bits */		/* Pointer to the thread descriptor.  */
  int multiple_threads;/* 24-28 bits */
  int gscope_flag;     /* 28-32 bits */
  uintptr_t sysinfo;   /* 32-40 bits */
  uintptr_t stack_guard;/* 40-48 bits <==> %fs:40 <==> %fs:0x28 */
  uintptr_t pointer_guard;
  unsigned long int unused_vgetcpu_cache[2];
  /* Bit 0: X86_FEATURE_1_IBT.
     Bit 1: X86_FEATURE_1_SHSTK.
   */
  unsigned int feature_1;
  int __glibc_unused1;
  /* Reservation of some values for the TM ABI.  */
  void *__private_tm[4];
  /* GCC split stack support.  */
  void *__private_ss;
  /* The lowest address of shadow stack,  */
  unsigned long long int ssp_base;
  /* Must be kept even if it is no longer used by glibc since programs,
     like AddressSanitizer, depend on the size of tcbhead_t.  */
  __128bits __glibc_unused2[8][4] __attribute__ ((aligned (32)));

  void *__padding[8];
} tcbhead_t;

不过这个值也并非所有位都是随机的，这和最常发生的栈溢出的原因有关：通常是不正确/不安全的字符串函数使用与意外/精心配置的错误字符串导致的。

除了写越界的任意代码执行很危险外，读越界导致栈中的敏感信息泄露同样很危险。所以另一种canary的思路是使用固定的字节组合00 0D 0A FF (NUL CR LF EOF) (\0 \r \n \0xff)作为Canary，虽然如今并没有看到其实际使用，但仍然为现在的栈保护提供了思路。使用它们作为canary时，虽然不能防止精心构造的写越界攻击，但是可以防止大多数的字符串函数读越界，字符串操作函数将会在遇到其中之一时停止。而glibc也利用了这一点，其stack_guard并非完全随机，在glibc的实现中，其低位总是0。这样可以缓解攻击者利用不正确的字符串处理函数获取canary后，再构造能特定于栈溢出攻击的串。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
/* sysdeps/generic/dl-osinfo.h#L22-L48 */
static inline uintptr_t __attribute__ ((always_inline))
_dl_setup_stack_chk_guard (void *dl_random)
{
  union
  {
    uintptr_t num;
    unsigned char bytes[sizeof (uintptr_t)];
  } ret = { 0 };

  if (dl_random == NULL)
    {
      ret.bytes[sizeof (ret) - 1] = 255;
      ret.bytes[sizeof (ret) - 2] = '\n';
    }
  else
    {
      memcpy (ret.bytes, dl_random, sizeof (ret));
// 区分大小端的宏，其目的就是让低位为 00 防止被str类函数读出内容
#if BYTE_ORDER == LITTLE_ENDIAN
      ret.num &= ~(uintptr_t) 0xff;
#elif BYTE_ORDER == BIG_ENDIAN
      ret.num &= ~((uintptr_t) 0xff << (8 * (sizeof (ret) - 1)));
#else
# error "BYTE_ORDER unknown"
#endif
    }
  return ret.num;
}

不同系统、架构的区别

然而上面提到的canary仅面向X86-64 CPU。在arm架构上，这种保护有着不同的实现方式。其值被静态编译进二进制文件当中，而非从TLS中读取。 Windows上的msvc同样也支持类似原理的栈保护功能。

操作系统中针对栈的保护

操作系统中也有针对栈溢出相应的保护。与编译器相比，操作系统提供的保护是对整个栈空间的保护。虽然实现原理上各不相同，但本质都是不允许栈顶的一部分空间可读写，以此在栈溢出时让程序直接停止工作，而不是出现内存数据泄露或任意代码执行的风险。

栈保护页／栈保护空洞

以Linux内核的实现为例。在栈向下生长时内核总是额外要求1MB的空间，虽然额外的空间不会被映射，但是当检查时如果没有这1MB空间的空余，那么则会直接返回-ENOMEM，程序segmentation fault。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
// mm/mmap.c  @expand_downwards
/* Enforce stack_guard_gap */
int expand_downwards(struct vm_area_struct *vma, unsigned long address) {
    // ...
    prev = mas_prev(&mas, 0);
    /* Check that both stack segments have the same anon_vma? */
    if (prev) {
        if (!(prev->vm_flags & VM_GROWSDOWN) &&
            vma_is_accessible(prev) &&
            (address - prev->vm_end < stack_guard_gap))
            return -ENOMEM;
    }

    if (prev)
        mas_next_range(&mas, vma->vm_start);
    // ...
}
/* enforced gap between the expanding stack and other mappings. */
// 4KB page size，256*page_size = 1MB
unsigned long stack_guard_gap = 256UL<<PAGE_SHIFT; // #define PAGE_SHIFT 12

Windows则是以不可读、不可写、不可执行的页面放在栈顶来保护栈溢出的情况。

地址随机化

现在操作系统使用地址随机化来缓解和地址有关的攻击。在没有地址随机化之前，函数的栈、堆、系统调用等映射均是固定的。其他的库的映射也相对较为固定。有潜在的被利用风险。 Linux内核早在2.6版本就通过引入地址随机化的方式来缓解这一攻击风险。简单地说就是让这些固定位置的映射的地址都有一定随机程度的起始位置偏移，使得攻击者更难预测需要利用的数据的位置。这缓解了一系列任意代码执行漏洞及内存敏感信息泄露漏洞等风险。

为什么生产中不应该打印函数指针

让外界知道运行时的函数指针是一个非常危险的行为。如果打印了某个函数指针，则代表该动态链接库、或者该程序内的其他指针都有可能被计算出来。尤其是对于一些公共库的函数，更应该注意。因为攻击者不一定能获取到内部的二进制文件，但公共的二进制文件，比如glibc，是很容易获取到的。一旦该库中的函数指针被打印，那么就很容易计算出该库中的其他函数指针的位置，地址随机化就没有缓解攻击的功能了，此时配合缓冲区溢出漏洞，可以构造出return to glibc攻击，而由于glibc中含有非常多可以用于攻击的实用函数，故该行为非常危险。

  • Copyrights © 2019-2025 Ytyan

请我喝杯咖啡吧~