x86 处理器可以调用多少个子程序？

Question

我正在编写一个小程序来使用 printf("\219") 打印一个多边形，看看我正在做的事情是否适合我的内核。但它需要调用很多函数，我不知道 x86 处理器是否可以接受那么多子例程，我在 google 中找不到结果。所以我的问题是它会接受这么多函数调用吗？最大值是多少。（我的意思是这样的:-)

function a() {b();}
function b() {c();}
function c() {d();}
...

我已经使用了 5 个这样的级别（你知道我的意思，对吧？）

Answer 1

您的函数深度不受处理器的限制，而是受堆栈大小的限制。在幕后，对 C++ 函数的调用通常转换为 x86 中的 call 指令，它将四个（或八个，对于 x64 程序）字节压入程序的堆栈以获取 return 指针。有时调用被优化并且根本不接触堆栈。函数也可能将额外的字节（例如本地函数状态）压入堆栈。

要获得您可以调用的函数的确切数量，您需要反汇编代码以计算每个函数压入堆栈的字节数（最小 four/eight 因为 return 地址，但可能更多），然后 find the maximum stack size 并将其除以函数帧大小。

Answer 2

call and ret instructions aren't special; the CPU doesn't know how deeply nested it is. (And doesn't know the difference between calling another function or being recursive.) As described ，函数是一个高级概念，asm 为您提供了实现的工具。

CPU 所知道的是，如果运行出栈 space，压入 return 地址是否会导致页面错误。（“堆栈溢出”）。通常是递归太深的结果，或者自动存储中的巨大数组（C++ 本地变量）或 alloca.

（如评论中所述，并非每个 C 函数调用都会导致 call 指令；内联可以完全优化它是一个单独函数的事实。您想要内联的小函数，C++ 标准库中模板类的设计依赖于此以提高效率。此外，tailcall 可以只是一个 jmp，让下一个函数接管这个堆栈space 而不是获取新的 space。）

Linux 通常为 user-space 进程使用 8 MiB 堆栈。 (ulimit -s)。 Windows 通常为 1 MiB。在内核内部，您经常使用较小的堆栈。例如Linux x86-64 的内核线程堆栈目前为 16 kiB。以前 32 位 x86 小到 4 kiB（一页），但一些代码有更多的局部变量占用堆栈 space.

相关：How does the stack work in assembly language?。当 ret 执行时，它只是弹出程序计数器。当堆栈指针指向你想跳转的地方时，由程序员（或编译器）创建运行s ret 的 asm。（通常是 return 地址。）

在现代 Linux 系统中，最小的堆栈帧是 16 字节，因为 ABI 指定在 call 之前保持 16 字节堆栈对齐。所以最好的情况是在溢出堆栈之前你可以有一个 512k 的调用深度。（除非您处于一个以超大线程堆栈启动的线程中）。

如果您在 32 位模式下使用旧版本的 i386 System V ABI，它只需要 4 字节堆栈对齐（例如 gcc -mpreferred-stack-boundary=2 而不是默认的 4），并且函数只需要在不使用任何其他堆栈的情况下调用 space，8 MiB 的堆栈将为您提供 8 MiB / 4B = 2 Mi 调用深度。

在现实生活中，主线程堆栈上的一些 8MiB space 被 env vars 用完并且 argv[] 已经在进程入口点的堆栈上（由内核复制到那里） ), 然后 _start 调用一个调用 main.

的函数

为了使它能够在最后真正 return，而不是最终出错，你需要一个巨大的链，或者一些带有终止条件的递归，比如

void recurse(int n) {
   if (n == 1)
       return;
   recurse(n - 1);
}

并通过一些优化进行编译，但不足以让编译器将其转换为 do{}while(--n); 循环或进行优化。

如果你想要所有不同的功能，没关系，代码大小限制至少为 2GiB，并且 call rel32 / ret 总共需要 6 个字节。（未优化的代码也将默认为 push ebp 或 push rbp，因此如果您想满足 4 字节堆栈框架目标，则必须避免使用 32 位代码你所有的堆栈 space 满只是 return 个地址）。

例如 GCC（请参阅了解 __attribute__((noipa)) 选项）

__attribute__((noipa))  // don't let other functions even notice that this is empty, let alone inline it
void foo(void){}

__attribute__((noipa))
void bar(){
    foo();
}

void baz(){
    bar();
}

用 GCC (Godbolt compiler explorer) 编译到这个 32 位 asm，只是调用而不使用任何堆栈 space 用于其他任何事情：

## GCC11.2  -O1 -m32 -mpreferred-stack-boundary=2
foo():
        ret
bar():
        call    foo()
        ret
baz():
        call    bar()
        ret

g++ -O2 会将这些 call/ret 函数优化为类似 jmp foo 的尾调用，它不会推送 return 地址。这就是为什么我只使用 -O1 或 -Og。当然在现实生活中你确实想要内联和优化东西；打败它只是为了这个愚蠢的计算机技巧来实现最长的有限调用深度，如果你让它更长，实际上会崩溃。

你可以无限期地重复这个模式； GCC 允许长符号名，因此拥有许多不同的唯一函数名不是问题。您可以拆分多个文件，而另一个文件中的其中一个函数只有一个原型。

如果您减少 -falign-functions 调整设置，您可能可以将其从默认值降低到每个函数 6 个字节（无填充）或 8 个（按 8 对齐，因此填充 2 个字节）将每个函数标签对齐 16，每个函数浪费 10 个字节。

递归：

我让 GCC 制作了递归的 asm，return 地址之间没有间隙：

void recurse(int n){
    if (!--n)
        return;
    recurse(n);
}

## G++11.2  -O1 -mregparm=3 -m32 -mpreferred-stack-boundary=2
recurse(int):
        sub     eax, 1       # --n
        jne     .L6          # skip over the ret if the result is non-zero
.L4:
        ret
.L6:
        call    recurse(int)   # push a 4-byte ret addr and jump to top
        jmp     .L4          # silly compiler, should put another ret here.  But we told it not to optimize too much

注意 -mregparm=3 选项，因此前最多 3 个参数在寄存器中传递，而不是在低效的 i386 System V 调用约定中传递到堆栈中。（它是很久以前设计的；x86-64 SysV 调用约定要好得多。）

使用 -O2，此函数优化为仅 ret。（它将调用变成一个循环的尾调用，然后它可以看到它是一个没有副作用的非无限循环，所以它只是将其删除。）

当然在现实生活中您想要这样的优化。与循环相比，asm 中的递归很糟糕。如果您担心代码的健壮性和调用深度，请不要首先编写递归函数，除非您知道递归深度会很浅。如果调试版本没有将您的递归转换为迭代，您不希望您的内核崩溃。

只是为了好玩，我让 GCC 在 -O1 时通过说服它在 call 上执行条件分支来收紧 asm，只有一个 ret 指令在函数中，所以尾部重复无论如何都不相关。这意味着快速路径（递归）涉及一个 not-taken 宏融合条件分支加上一个调用。

void recurse(int n){
    if (__builtin_expect(!!--n, 1))
        recurse(n);
}

Godbolt

## GCC 11.2  -O1 -mregparm=3 -m32 -mpreferred-stack-boundary=2
recurse(int):
        sub     eax, 1
        je      .L1
        call    recurse(int)
.L1:
        ret

x86 处理器可以调用多少个子程序？

to how many subroutines can x86 processors call?

c++

stack-overflow

x86

gcc

callstack

递归：