给递归函数分配内存

Question

给递归函数分配内存

3

我编写了一个简单的程序，如下所示，并进行了strace跟踪。

#include<stdio.h>
int foo(int i)
{
    int k=9;
    if(i==10)
            return 1;
    else
            foo(++i);
    open("1",1);
}
int main()
{
    foo(1);
}

我这么做的目的是检查函数中变量（此例中为 int k）在栈上分配内存的情况。我使用了一个开放系统调用作为标记。strace 的输出如下：

execve("./a.out", ["./a.out"], [/* 25 vars */]) = 0
brk(0)                                  = 0x8653000
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) =     0xb777e000
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=95172, ...}) = 0
mmap2(NULL, 95172, PROT_READ, MAP_PRIVATE, 3, 0) = 0xb7766000
close(3)                                = 0
access("/etc/ld.so.nohwcap", F_OK)      = -1 ENOENT (No such file or     directory)
open("/lib/i386-linux-gnu/libc.so.6", O_RDONLY|O_CLOEXEC) = 3
read(3, "\177ELF\1\1\1\0\0\0\0\0\0\0\0\0\3\0\3\0\1\0\0\0000\226\1\0004\0\0\0"..., 512) = 512
fstat64(3, {st_mode=S_IFREG|0755, st_size=1734120, ...}) = 0
mmap2(NULL, 1743580, PROT_READ|PROT_EXEC, MAP_PRIVATE|MAP_DENYWRITE, 3, 0) =     0xb75bc000
mmap2(0xb7760000, 12288, PROT_READ|PROT_WRITE,     MAP_PRIVATE|MAP_FIXED|MAP_DENYWRITE, 3, 0x1a4) = 0xb7760000
mmap2(0xb7763000, 10972, PROT_READ|PROT_WRITE, MAP_PRIVATE|MAP_FIXED|MAP_ANONYMOUS, -1, 0) = 0xb7763000
close(3)                                = 0
mmap2(NULL, 4096, PROT_READ|PROT_WRITE, MAP_PRIVATE|MAP_ANONYMOUS, -1, 0) =     0xb75bb000
set_thread_area({entry_number:-1 -> 6, base_addr:0xb75bb900, limit:1048575, seg_32bit:1, contents:0, read_exec_only:0, limit_in_pages:1, seg_not_present:0, useable:1}) = 0
mprotect(0xb7760000, 8192, PROT_READ)   = 0
mprotect(0x8049000, 4096, PROT_READ)    = 0
mprotect(0xb77a1000, 4096, PROT_READ)   = 0
munmap(0xb7766000, 95172)               = 0
open("1", O_WRONLY)                     = -1 ENOENT (No such file or     directory)
open("1", O_WRONLY)                     = -1 ENOENT (No such file or     directory)
open("1", O_WRONLY)                     = -1 ENOENT (No such file or directory)
open("1", O_WRONLY)                     = -1 ENOENT (No such file or     directory)
open("1", O_WRONLY)                     = -1 ENOENT (No such file or     directory)
open("1", O_WRONLY)                     = -1 ENOENT (No such file or     directory)
open("1", O_WRONLY)                     = -1 ENOENT (No such file or     directory)
open("1", O_WRONLY)                     = -1 ENOENT (No such file or directory)
open("1", O_WRONLY)                     = -1 ENOENT (No such file or directory)
exit_group(-1)                          = ?

在strace输出的末尾，您可以看到在open系统调用之间没有调用任何系统调用。那么，在没有系统调用的情况下，如何为被调用的函数分配堆栈上的内存？

- PaulDaviesC

foo定义缺少“}”？此外，编译优化器将删除对k的引用，因为它在任何地方都没有被使用。 - rickhg12hs

栈操作（新的堆栈帧，从函数返回，为新变量调整空间，删除变量等）通常不是通过系统调用完成的，而是由生成的代码简单处理。因此，“strace”并不是非常有用... - twalberg

这里不回答你的问题，但值得注意的是你的程序并不像你想象的那样运行：即使为每个递归调用分配了堆栈内存，由于你的递归发生在调用之前而不是之后，所以在第一个open()调用之前所有内存都已经被分配完毕。 - Jules

关于 strace 的一条严重注意事项：strace 无法显示使用 dl_open() 打开的库。 - PersianGulf

5个回答

2

您的（单线程）程序堆栈大小是固定的，因此不会有进一步的分配。

您可以使用ulimit -s命令查询和增加此大小。

请注意，即使将此限制设置为“无限制”，也总会存在实际限制：

对于32位进程，除非您的RAM /交换空间不足，否则虚拟内存空间限制会导致地址冲突
对于64位进程，内存（RAM +交换空间）耗尽将使系统崩溃并最终崩溃您的程序。

无论如何，永远没有明确的系统调用来增加堆栈大小，它只在程序启动时设置。

还要注意，堆栈内存的处理方式与堆内存完全相同，即仅将已访问部分映射到实际内存（RAM或交换空间）。这意味着堆栈在需求增长，但除标准虚拟内存管理外，没有其他机制来处理。

- jlliagre

我不明白它被修复了哪些方面。你在哪里看到的？ - glglgl

这是有意为之的。程序启动时，主线程（或者在这里是单个线程）的堆栈大小是固定的。你可以使用"ulimit -s"命令查看它的大小。这是虚拟内存，所以就像使用malloc获取的内存一样，它只是被保留，并且只有在访问时才被真正的内存（RAM或交换空间）支持。没有机制允许进程在运行时增加其堆栈大小。 - jlliagre

您可以设置 ulimit -s unlimited。之后，您就没有真正的限制了。您可以测试这段代码，看看它如何不断增长，堆栈向更小的地址增长。您会发现，在运行很长时间后，它最终会与程序的其他部分发生冲突。但是由于堆栈始于 bf82f000（确切值可能会变化），而这些其他部分位于 401bb000 及以下，因此我们在堆栈上有非常多的空间可用（我已经到达步骤 1027625，然后才发生冲突）。ulimit -s只是额外的“花招”... - glglgl

顺便说一句，有趣的是，如果程序达到了（设置的）ulimit，我会收到一个SIGSEGV信号，而如果我达到了“程序区域”，我会收到一个SIGBUS信号... - glglgl

即使指定“无限制”，也总会有实际限制，就像您所经历的那样。如果您的程序编译为64位，则不会发生地址冲突，但会出现内存耗尽的情况。无论如何，从来没有明确的系统调用执行分配，这正是OP所寻找的。 - jlliagre

1

你想了解变量是如何分配到为函数创建的“堆栈帧”中的吗？我修改了你的程序，向你展示了堆栈变量k和参数变量kk的内存地址。

//Show stack location for a variable, k
#include <stdio.h>
int foo(int i)
{
    int k=9;
    if(i>=10) //relax the condition, safer
        return 1;
    else
        foo(++i);
    open("1",1);
    //return i;
}
int bar(int kk, int i)
{
    int k=9;
    printf("&k: %x, &kk: %x\n",&k,&kk); //address variable on stack, parameter
    if(i<10) //relax the condition, safer
        bar(k,++i);
    else
        return 1;
    return k;
}
int main()
{
    //foo(1);
    bar(0,1);
}

而在我的系统上输出为：

$ ./foo
&k: bfa8064c, &kk: bfa80660
&k: bfa8061c, &kk: bfa80630
&k: bfa805ec, &kk: bfa80600
&k: bfa805bc, &kk: bfa805d0
&k: bfa8058c, &kk: bfa805a0
&k: bfa8055c, &kk: bfa80570
&k: bfa8052c, &kk: bfa80540
&k: bfa804fc, &kk: bfa80510
&k: bfa804cc, &kk: bfa804e0
&k: bfa8049c, &kk: bfa804b0

- ChuckCottrill

1

你的程序只有在递归“底部”时才开始进行任何open调用。此时，堆栈已分配，并且仅弹出嵌套。

为什么不使用调试器逐步执行程序。

- Kaz

1

栈的使用和分配（至少在Linux上）是这样的：

分配一点栈空间。
在程序的“其他”部分之后设置一个守卫范围，大约占用地址空间的1/4。
如果栈被用到了顶部并且以上，栈会自动增加。
这会发生在达到ulimit限制（并出现SIGSEGV）或者如果没有这样的限制，直到达到守卫范围（然后获得SIGBUS）。

- glglgl

2

@PaulDaviesC：这是在页面错误时完成的。例如，在x86上，首先检查所有其他可能性，如果不是它们中的任何一个，则页面错误是由于访问当前映射堆栈之外的地址（先前的检查是address + 65536 + 32 * sizeof(unsigned long) < regs->sp）。请参见arch/x86/mm/fault.c:do_page_fault()。 - ninjalj

网页内容由stack overflow 提供, 点击上面的

可以查看英文原文，
原文链接

- ninjalj · Accepted Answer

主线程的堆栈内存是在execve()系统调用期间由内核分配的。在此调用期间，还设置了可执行文件中定义的其他映射（可能还包括可执行文件中指定的动态链接器）。对于ELF文件，这是在fs/binfmt_elf.c中完成的。

其他线程的堆栈内存是由线程支持库使用mmap()分配的，该库通常是C运行时库的一部分。

您还应注意，在虚拟内存系统上，主线程堆栈会在响应页面错误时由内核增长，最高可达可配置极限（ulimit -s显示）。