why is the call stack set up like this?

Question

I was just playing with the call stack, trying to change the return address of a function etc, and wound up writing this program in C:

#include<stdio.h>

void trace(int);
void func3(int);
void func2(int);
void func1(int);

int main(){

    int a = 0xAAAA1111;

    func1(0xFCFCFC01);

    return 0;

}

void func1(int a){

    int loc = 0xBBBB1111;

    func2(0xFCFCFC02);

}

void func2(int a){

    int loc1 = 0xCCCC1111;
    int loc2 = 0xCCCC2222;

    func3(0xFCFCFC03);

}

void func3(int a){

    int loc1 = 0xDDDD1111;
    int loc2 = 0xDDDD2222;
    int loc3 = 0xDDDD3333;

    trace(0xFCFCFC04);

}

void trace(int a){

    int loc = 0xEEEE1111;

    int *ptr = &loc;

    do {
    printf("0x%08X : %08X\n", ptr, *ptr, *ptr);
    } while(*(ptr++) != 0xAAAA1111);

}

(sorry for the length)

This produced the following output (with comments that I added):

0xBF8144D4 : EEEE1111 //local int in trace
0xBF8144D8 : BF8144F8 //beginning of trace stack frame
0xBF8144DC : 0804845A //return address for trace to func3
0xBF8144E0 : FCFCFC04 //int passed to trace
0xBF8144E4 : 08048230 //(possibly) uninitialized padding
0xBF8144E8 : 00000000 //padding
0xBF8144EC : DDDD3333 //local int in func3
0xBF8144F0 : DDDD2222 //local int in func3
0xBF8144F4 : DDDD1111 //local int in func3
0xBF8144F8 : BF814518 //beginning of func3 stack frame
0xBF8144FC : 08048431 //return address for func3 to func2
0xBF814500 : FCFCFC03 //parameter passed to func3
0xBF814504 : 00000000 //padding
0xBF814508 : 00000000 //padding
0xBF81450C : 00000000 //padding
0xBF814510 : CCCC2222 //local int in func2
0xBF814514 : CCCC1111 //local int in func2
0xBF814518 : BF814538 //beginning of func2 stack frame
0xBF81451C : 0804840F //return address for func2 to func1
0xBF814520 : FCFCFC02 //parameter passed to func2
0xBF814524 : 00000000 //padding
0xBF814528 : BF816728 //uninitialized padding
0xBF81452C : B7DF3F4E //uninitialized padding
0xBF814530 : B7EA61D9 //uninitialized padding
0xBF814534 : BBBB1111 //local int in func1
0xBF814538 : BF814558 //beginning of func1 stack frame
0xBF81453C : 080483E8 //return address for func1 to main
0xBF814540 : FCFCFC01 //parameter passed to func1
0xBF814544 : 08049FF4 //(maybe) padding
0xBF814548 : BF814568 //(maybe) padding
0xBF81454C : 080484D9 //(maybe) padding
0xBF814550 : AAAA1111 //local int in main

I was wondering if anybody could fill me in on the blank spots here... I'm running Ubuntu linux compiling with gcc 4.3.3 (on an x86 -- AMD Turion 64)

What are the 0804... numbers? What's the third address up from the bottom? Is that the return address for main? If so, why is it out of order compared to the rest of the stack? The 0x0804 numbers are return addresses, or pointers to code/data or something, while the 0xBF814 numbers are stack pointers

What's this:

0xBF814524 : 00000000 //padding?
0xBF814528 : BF816728 //I have no idea
0xBF81452C : B7DF3F4E //????
0xBF814530 : B7EA61D9 //????

seen just after the local int in func1?

Okay I have my stack dump almost completely filled in.

It looks like the the compiler wants to have the parameters pushed onto the stack starting at a 0x.......0 address, and everything between the local variables from the function before and the first parameter of the function being called seems to be padding (whether 0x00000000 or some uninitialized value). Some of them I'm unsure about because they look like code/data segment pointers, but I can't see them being used in the code: they're just there when the stack pointer gets reduced.

and I know it's a HUGE nono to touch the call stack in any kind of project, but that's okay. It's fun, right?

also

Greg wants to see the assembly, here it is

    .file   "stack.c"
    .text
.globl main
    .type   main, @function
main:
    leal    4(%esp), %ecx
    andl    $-16, %esp
    pushl   -4(%ecx)
    pushl   %ebp
    movl    %esp, %ebp
    pushl   %ecx
    subl    $20, %esp
    movl    $-1431695087, -8(%ebp)
    movl    $-50529279, (%esp)
    call    func1
    movl    $0, %eax
    addl    $20, %esp
    popl    %ecx
    popl    %ebp
    leal    -4(%ecx), %esp
    ret
    .size   main, .-main
.globl func1
    .type   func1, @function
func1:
    pushl   %ebp
    movl    %esp, %ebp
    subl    $24, %esp
    movl    $-1145368303, -4(%ebp)
    movl    $-50529278, (%esp)
    call    func2
    leave
    ret
    .size   func1, .-func1
.globl func2
    .type   func2, @function
func2:
    pushl   %ebp
    movl    %esp, %ebp
    subl    $24, %esp
    movl    $-859041519, -4(%ebp)
    movl    $-859037150, -8(%ebp)
    movl    $-50529277, (%esp)
    call    func3
    leave
    ret
    .size   func2, .-func2
.globl func3
    .type   func3, @function
func3:
    pushl   %ebp
    movl    %esp, %ebp
    subl    $24, %esp
    movl    $-572714735, -4(%ebp)
    movl    $-572710366, -8(%ebp)
    movl    $-572705997, -12(%ebp)
    movl    $-50529276, (%esp)
    call    trace
    leave
    ret
    .size   func3, .-func3
    .section    .rodata
.LC0:
    .string "0x%08X : %08X\n"
    .text
.globl trace
    .type   trace, @function
trace:
    pushl   %ebp
    movl    %esp, %ebp
    subl    $40, %esp
    movl    $-286387951, -4(%ebp)
    leal    -4(%ebp), %eax
    movl    %eax, -8(%ebp)
.L10:
    movl    -8(%ebp), %eax
    movl    (%eax), %edx
    movl    -8(%ebp), %eax
    movl    (%eax), %eax
    movl    %edx, 12(%esp)
    movl    %eax, 8(%esp)
    movl    -8(%ebp), %eax
    movl    %eax, 4(%esp)
    movl    $.LC0, (%esp)
    call    printf
    movl    -8(%ebp), %eax
    movl    (%eax), %eax
    cmpl    $-1431695087, %eax
    setne   %al
    addl    $4, -8(%ebp)
    testb   %al, %al
    jne .L10
    leave
    ret
    .size   trace, .-trace
    .ident  "GCC: (Ubuntu 4.3.3-5ubuntu4) 4.3.3"
    .section    .note.GNU-stack,"",@progbits

Answer 1

Inspecting the stack like this seems like one step too far away. I might suggest loading your program in a debugger, switching to the assembly language view, and single stepping through every machine instruction. Understanding of the CPU stack necessarily requires an understanding of the machine instructions operating on it, and this will be a more direct way to see what's going on.

As others mentioned, the structure of the stack is also highly dependent on the processor architecture you're working with.