將內存分配給遞歸函數

我編寫了一個簡單的程序，並將其放大。將內存分配給遞歸函數

#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的輸出，你可以看到，沒有系統調用被稱爲開放的系統調用之間結束。那麼，如何在沒有系統調用的情況下爲被調用的函數分配內存到內存中？

來源

2013-10-28 PaulDaviesC

缺少foo定義的「}」？此外，編譯優化器將刪除對k的引用，因爲它不在任何地方使用。 – rickhg12hs

堆棧操作（新堆棧幀，函數返回，調整新變量空間，刪除變量等）通常不是通過系統調用完成的，而是由生成的代碼完成。因此，'strace'不會很有用...... – twalberg

在這裏沒有回答你的問題，但值得注意的是你的程序並不像你認爲的那樣工作：即使內存分配給每個堆棧遞歸調用時，內存將在您進入第一次open（）調用時分配，因爲您的遞歸在調用之前發生，而不是在調用之後發生。 – Jules

堆棧的使用和分配（至少在Linux上）以這種方式工作：

分配了一點堆棧。
保護範圍設置在程序的「其他」部分之後，大約佔地址空間的1/4。
如果堆棧使用到最高和最高，堆棧會自動增加。
如果達到了ulimit的限制（和SIGSEGV s），或者如果沒有這種限制，直到碰到防範範圍（然後得到SIGBUS），則會發生這種情況。

來源

2013-10-29 05:38:08 glglgl

如何自動增加堆棧？ – PaulDaviesC

@PaulDaviesC：它在頁面錯誤時完成。例如在x86上，首先檢查所有其他可能性，如果沒有它們，則頁面錯誤是由於當前映射堆棧之外的訪問（前面的檢查爲地址+ 65536 + 32 * sizeof（無符號長整型）< regs-> sp'）。參見'arch/x86/mm/fault.c：do_page_fault（）'。 – ninjalj

主線程的堆棧內存在系統調用execve()期間由內核分配。在此調用期間，還會設置可執行文件中定義的其他映射（也可能用於可執行文件中指定的動態鏈接器）。對於ELF文件，這在fs/binfmt_elf.c中完成。

其他線程的堆棧內存由線程支持庫編輯，mmap()通常是C運行時庫的一部分。

您還應該注意，在虛擬內存系統中，主線程堆棧由內核響應頁面錯誤而增長，達到可配置限制（由ulimit -s顯示）。

來源

2013-10-28 16:48:53 ninjalj

您的（單線程）程序堆棧大小是固定的，因此不需要進一步分配。

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

請注意，即使你這個限制設置爲「無限」，時時會出現一個實際的限制：

隨着32位進程，除非你是低的RAM /交換，虛擬內存空間限制將導致地址衝突
使用64位進程時，內存（RAM +交換）耗盡會導致系統崩潰並最終導致程序崩潰。

無論如何，從來沒有明確的系統調用來期望會增加堆棧大小，它只在程序啓動時設置。

還要注意，堆棧內存的處理與堆內存完全相同，即只有被訪問的部分被映射到實際內存（RAM或交換）。這意味着堆棧種類按需增長，但除標準虛擬內存管理外，沒有任何其他機制可以處理這種情況。

來源

2013-10-28 16:51:01 jlliagre

我看不出它是如何以任何方式修復的。你在哪裏看到？ – glglgl

這是設計。程序啓動時，主（或單個）線程的堆棧大小具有固定的大小。你可以通過使用「ulimit -s」命令來查看它是什麼。這是虛擬內存，與使用malloc獲取的內存一樣，只是保留並且只有在訪問時才由真實內存（RAM或交換）支持。沒有機制允許進程在運行時增加堆棧大小。 – jlliagre

你可以設置'ulimit -s unlimited'。之後，你沒有真正的限制。你可以測試[這個代碼]（http://codepad.org/QHQjibVO），看看它是如何前進和發展的，並且棧越來越多，並且越來越多地朝着更小的地址發展。你會看到，在長時間運行後，它最終會與程序的其他部分發生衝突。但是當堆棧從'bf82f000'開始（確切的值可能會發生變化）並且其他部分在'401bb000'以下時，我們在堆棧上有很多空間可用（在碰撞之前我已經到達步驟1027625）。 'ulimit -s'只是一個額外的「噱頭」... – glglgl

你的程序不會開始做任何open調用，直到遞歸「低谷」。在這一點上，堆棧被分配，它只是從嵌套中彈出。

你爲什麼不用調試器來完成它。

來源

2013-10-28 18:13:12 Kaz

你想知道哪些變量被分配給爲函數創建的「棧幀」嗎？我已經修改了你的程序向你展示你的堆棧變量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

來源

2013-10-28 22:30:54 ChuckCottrill

將內存分配給遞歸函數

回答

相關問題