Are C stack variables stored in reverse?

Question

I'm trying to understand how C allocates memory on stack. I always thought variables on stack could be depicted like structs member variables, they occupy successive, contiguous bytes block within the Stack. To help illustrate this issue I found somewhere, I created this small program which reproduced the phenomenon.

#include <stdio.h>
#include <stdlib.h>
#include <string.h>

void function(int  *i) {
    int *_prev_int =  (int *) ((long unsigned int) i -  sizeof(int))  ;
    printf("%d\n", *_prev_int );    
}

void main(void) 
{
    int x = 152;
    int y = 234;
    function(&y);
}

See what I'm doing? Suppose sizeof(int) is 4: I'm looking 4 bytes behind the passed pointer, as that would read the 4 bytes before where int y in the caller's stack.

It did not print the 152. Strangely when I look at the next 4 bytes:

int *_prev_int =  (int *) ((long unsigned int) i +  sizeof(int))  ;

and now it works, prints whatever in x inside the caller's stack. Why x has a lower address than y? Are stack variables stored upside down?

Answer 1

Stack organization is completely unspecified and is implementation specific. In practice, it depends a lot of the compiler (even of its version) and of optimization flags.

Some variables don't even sit on the stack (e.g. because they are just kept inside some registers, or because the compiler optimized them -e.g. by inlining, constant folding, etc..).

BTW, you could have some hypothetical C implementation which does not use any stack (even if I cannot name such implementation).

To understand more about stacks:

• Read the wikipage on call stacks, tail calls, threads, and on continuations

• Become familiar with your computer's architecture & instruction set (e.g. x86) & ABI, then ...

• ask your compiler to show the assembler code and/or some intermediate compiler representations. If using GCC, compile some simple code with gcc -S -fverbose-asm (to get assembler code foo.s when compiling foo.c) and try several optimization levels (at least -O0, -O1, -O2 ....). Try also the -fdump-tree-all option (it dumps hundred of files showing some internal representations of the compiler for your source code). Notice that GCC also provides return address builtins

• Read Appel's old paper on garbage collection can be faster than stack allocation, and understand garbage collection techniques (since they often need to inspect and possibly change some pointers inside call stack frames). To know more about GC, read the GC handbook.

Sadly, I know no low-level language (like C, D, Rust, C++, Go, ...) where the call stack is accessible at the language level. This is why coding a garbage collector for C is difficult (since GC-s need to scan the call stack pointers)... But see Boehm's conservative GC for a very practical and pragmatic solution.