在运行时给出其大小的向量的堆栈空间?(C 代码)

stack space for a vector that its size is given at runtime? (C code)

提问人:isma 提问时间:6/30/2020 最后编辑:Peter Cordesisma 更新时间:10/13/2020 访问量:208

问:

置入以下 C 代码:

int main(){
    int n;
    scanf("%d\n", &n);

    int a[n];
    int i;
    
    for (i = 0; i<n; i++){
        a[i] = 1;
    }

}

我们有一个在堆栈空间中的向量,但直到执行时间(直到用户给变量 n 一个值)我们才知道向量的大小。所以我的问题是:何时以及如何为堆栈部分的该向量保留空间?

到目前为止,我已经了解到堆栈空间是在编译时保留的,堆空间是在运行时保留的(使用像 malloc 这样的函数)。但是在运行时之前,我们无法知道这个向量的大小。

我认为可以做的是在知道 n 的那一刻从堆栈指针中减去它的值,从而放大该函数的堆栈,以便向量适合(我提到的这种减法只会在组装代码中看到)。

但是我一直在观察 /proc/[pid]/maps 内容进行一些测试。并且进程的堆栈空间没有改变,所以我的想法(在汇编代码中,将 n*sizeof(int) 减去堆栈顶部的指令)没有完成。我已经在 main 函数的开头和结尾观看了 /proc/[pid]/maps 的内容。

如果我为 x86 (gcc -m32 -o test.c) 组装此代码,请获取以下汇编代码(以备不时之需):

.file   "test.c"
    .text
    .section    .rodata
.LC0:
    .string "%d\n"
    .text
    .globl  main
    .type   main, @function
main:
.LFB0:
    .cfi_startproc
    leal    4(%esp), %ecx
    .cfi_def_cfa 1, 0
    andl    $-16, %esp
    pushl   -4(%ecx)
    pushl   %ebp
    .cfi_escape 0x10,0x5,0x2,0x75,0
    movl    %esp, %ebp
    pushl   %esi
    pushl   %ebx
    pushl   %ecx
    .cfi_escape 0xf,0x3,0x75,0x74,0x6
    .cfi_escape 0x10,0x6,0x2,0x75,0x7c
    .cfi_escape 0x10,0x3,0x2,0x75,0x78
    subl    $44, %esp
    call    __x86.get_pc_thunk.ax
    addl    $_GLOBAL_OFFSET_TABLE_, %eax
    movl    %gs:20, %ecx
    movl    %ecx, -28(%ebp)
    xorl    %ecx, %ecx
    movl    %esp, %edx
    movl    %edx, %esi
    subl    $8, %esp
    leal    -44(%ebp), %edx
    pushl   %edx
    leal    .LC0@GOTOFF(%eax), %edx
    pushl   %edx
    movl    %eax, %ebx
    call    __isoc99_scanf@PLT
    addl    $16, %esp
    movl    -44(%ebp), %eax
    leal    -1(%eax), %edx
    movl    %edx, -36(%ebp)
    sall    $2, %eax
    leal    3(%eax), %edx
    movl    $16, %eax
    subl    $1, %eax
    addl    %edx, %eax
    movl    $16, %ebx
    movl    $0, %edx
    divl    %ebx
    imull   $16, %eax, %eax
    subl    %eax, %esp
    movl    %esp, %eax
    addl    $3, %eax
    shrl    $2, %eax
    sall    $2, %eax
    movl    %eax, -32(%ebp)
    movl    $0, -40(%ebp)
    jmp .L2
.L3:
    movl    -32(%ebp), %eax
    movl    -40(%ebp), %edx
    movl    $1, (%eax,%edx,4)
    addl    $1, -40(%ebp)
.L2:
    movl    -44(%ebp), %eax
    cmpl    %eax, -40(%ebp)
    jl  .L3
    movl    %esi, %esp
    movl    $0, %eax
    movl    -28(%ebp), %ecx
    xorl    %gs:20, %ecx
    je  .L5
    call    __stack_chk_fail_local
.L5:
    leal    -12(%ebp), %esp
    popl    %ecx
    .cfi_restore 1
    .cfi_def_cfa 1, 0
    popl    %ebx
    .cfi_restore 3
    popl    %esi
    .cfi_restore 6
    popl    %ebp
    .cfi_restore 5
    leal    -4(%ecx), %esp
    .cfi_def_cfa 4, 4
    ret
    .cfi_endproc
.LFE0:
    .size   main, .-main
    .section    .text.__x86.get_pc_thunk.ax,"axG",@progbits,__x86.get_pc_thunk.ax,comdat
    .globl  __x86.get_pc_thunk.ax
    .hidden __x86.get_pc_thunk.ax
    .type   __x86.get_pc_thunk.ax, @function
__x86.get_pc_thunk.ax:
.LFB1:
    .cfi_startproc
    movl    (%esp), %eax
    ret
    .cfi_endproc
.LFE1:
    .hidden __stack_chk_fail_local
    .ident  "GCC: (Ubuntu 7.5.0-3ubuntu1~18.04) 7.5.0"
    .section    .note.GNU-stack,"",@progbits
C 程序集 x86 可变长度阵列 自动存储

评论

0赞 Samuel Liew 7/2/2020
评论不用于扩展讨论;此对话已移至 Chat

答:

0赞 user253751 6/30/2020 #1

这是特定于平台的,但通常,在程序启动时会保留空间,并且您具有最大堆栈大小。在 Windows 上,根据 Microsoft 的说法,默认最大值为 1MB,你可以使用链接器设置(在 Visual Studio 的项目属性中)进行更改。

如果您的程序是多线程的,则其他线程的堆栈空间在启动时会保留。

如果你试图使用比现有空间更多的堆栈空间,那么通常情况下,你的程序会崩溃,它可能是也可能不是安全漏洞(即让人们入侵你的程序)——参见“堆栈冲突”。

0赞 isma 7/2/2020 #2

您可以阅读有关该问题的评论,由于 PeterCordes 的帮助,这些评论解决了我的问题。基本上,堆栈中需要数组的空间将在运行时在数组声明的精确时刻保留(因为 n 是此时的已知值)。我们在组装代码中会有一个指令,即 stackPointer = stackPointer - n * sizeof(int)。

0赞 Peter Cordes 10/13/2020 #3

首先,您的代码被严重损坏:直到使用它来设置 的大小之后才设置。在此之后进行更改不会更改数组维度。可变长度数组是 C99 的一项功能,并且 C99 消除了声明在块中的任何其他语句之前出现的需要,从而使您可以在语句在堆栈上为该大小的数组保留空间之前进入。nint vector[n];nscanfnint vector[n];

到目前为止,我已经了解到堆栈空间是在编译时保留的,堆空间是在运行时保留的

总堆栈区域在程序启动时保留。根据操作系统的不同,为堆栈增长保留的空间量由操作系统设置选择,而不是可执行文件中的元数据。(例如,在 Linux 中,通过初始线程堆栈的设置,pthreads 选择为每个线程堆栈分配多少空间。ulimit -s

堆栈帧的布局在编译时是固定的(局部变量相对于彼此的位置),但每次函数运行时都会发生实际分配。这就是函数如何递归和重入的!这也是使堆栈成为堆栈的原因:在末尾为当前函数腾出空间,在返回之前释放它。(可变长度数组,并且具有运行时变量大小,因此编译器通常会将它们放在其他局部变量之下。alloca

只有静态存储才能在编译时真正保留/分配。(全局变量和变量。static

(ISO C 不需要实际的堆栈,只需要自动存储变量生存期的后进先出语义。某些 ISA 上的一些实现基本上是动态地为堆栈帧分配空间,例如使用 malloc,而不是使用堆栈。

这排除了在编译时为局部变量静态分配空间的可能性。在大多数 C 实现中,它们都位于 x86-64 或其他版本的堆栈上。当然,局部变量相对于彼此的布局编译时是固定的,在大分配内部,因此编译器不需要编写存储指向对象的指针的代码,它们只需发出使用寻址模式的指令,例如 .sub rsp, 24[rsp + 4]

所以我的问题是:何时以及如何为堆栈部分的该向量保留空间?

逻辑上在 C 抽象机中:当达到 int vector[n] 语句时,在此执行函数。相比之下,固定大小的对象存在于封闭范围的顶部。

因此,你的榜样被严重破坏了。在分配 VLA 之前,您将保持未初始化状态!在启用警告的情况下编译代码,以捕获此类问题。 应该在 之前。(另外,不要称普通数组为“向量”,这对了解 C++ 的人来说是错误的。nscanfint vector[n]

但在这种情况下,提到局部变量应按其声明顺序放置的 C 和 x86 规则将不被遵守。

没有这样的规则。在 ISO C 中,写入和比较单独对象的地址是未定义行为。(C++ 允许使用 ;C 没有等效项 C 是否有来自 C++ 的 std::less 等效项?vector < &nstd::less

允许 C 编译器以它选择的方式布局其堆栈框架,例如将小对象组合在一起,以避免在填充上浪费空间来对齐较大的对齐对象。

x86 ASM 根本没有变量声明。作为程序员(或 C 编译器),您可以编写移动堆栈指针的指令,并使用内存寻址模式访问要访问的内存。通常,您将以实现“变量”的高级概念的方式执行此操作。

例如,让我们创建一个作为函数参数的函数版本,而不是用 scanf 来打扰。n

#include <stdio.h>

void use_mem(void*);   // compiler can't optimize away calls to this unknown function

void foo(int size) {
    int n = size;  // uninitialized was UB
    int array[n];
    int i;
    i = 5;     // optimizes away, i is kept in a register

    //scanf("%d\n", &n);  // read some different size later???  makes no sense
    for (i = 0; i<n; i++){
        array[i] = 1;
    }
    use_mem(array);  // make the stores not be dead
}

在带有 GCC10.1 -O2 -Wall 的 Godbolt 上,对于 x86-64 System V:

foo(int):
        push    rbp
        movsx   rax, edi             # sign-extend n
        lea     rax, [15+rax*4]      # round size up
        and     rax, -16             # to a multiple of 16, to main stack alignment
        mov     rbp, rsp            # finish setting up a frame pointer
        sub     rsp, rax             # allocate space for array[]
        mov     r8, rsp              # keep a pointer to it
        test    edi, edi             # if ( n==0 ) skip the loop
        jle     .L2
        mov     edi, edi             # zero-extend n
        mov     rax, r8              # int *p = array
        lea     rdx, [r8+rdi*4]      # endp = &array[(unsigned)n]
.L3:                                 # do{
        mov     DWORD PTR [rax], 1     # *p = 1
        add     rax, 4                 # pointer increment
        cmp     rax, rdx
        jne     .L3                  # }while(p != endp)
.L2:
        mov     rdi, r8             # pass a pointer to the VLA
        call    use_mem(void*)
        leave                       # tear down frame pointer / stack frame
        ret

请注意,运行时,空间位于堆栈指针上方,即“已分配”。call use_memarray[n]

如果回调到此函数,则会在堆栈上分配具有其自身大小的另一个 VLA 实例。use_mem

该指令只是 / ,因此它将堆栈指针设置为指向已分配空间的上方,从而取消分配它。leavemov rsp, rbppop rbp

评论

0赞 Peter Cordes 10/13/2020
(如果这个答案 3/4 写在浏览器选项卡中,最终完成了 FWIW。