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.

Answer 2

Almost all the processors architectures nowadays supports stack manipulation instruction (e.g LDM,STM instructions in ARM). Compilers with the help of those implements stack. In most of the cases when data is pushed into stack, stack pointer decrements (Growing Downwards) and Increments when data popped from stack.

So it depends on processor architecture and compiler how stack is implemented.

Answer 3

Depends on the compiler and platform. The same thing can be done in more than one way as long it is done consistently by a program (this case the compiler translation to assembly, i.e. machine code) and the platform supports it (good compilers try to optimize assembly to get the “most” of each platform).

A very good source to deeply understand what goes behind the scenes of c, what happens when compiling a program and why they happen, is the free book Reverse Engineering for Beginners (Understanding Assembly Language) by Dennis Yurichev, the latest version can be found at his site.