C program to find direction of stack growth

How do I find i开发者_运维问答n C whether a stack is progressing in forward or reverse direction ? WIll this work?

int j = 0;
int k = 0;

if (&k > &j) 
 printf ("Stack is growing in forward direction");

else if (&k < &j) 
  printf ("Stack is growing in reverse direction");

To be reliable, one would have to find the difference between two function calls.

void func(int *p) {
    int i;
    if (!p)
        func(&i);
    else if (p < &i)
        printf("Stack grows upward\n");
    else
        printf("Stack grows downward\n");
}

func(NULL);

Note that this won't give you an answer about C, but about your compiler.

You cannot. In your code, (&k > &j) invokes undefined behavior behavior. Pointer comparison with relational operators is not defined unless the pointers point to objects within the same array (or one object beyond the end of the array).

Whether a stack exists is dictated by your implementation. Undefined behavior cannot predict implementation details.

The ISO C standard does not mention the word "stack" even once. A stack might not even exist. The memory used by function invocations to keep local variables might not even be contiguous.

This is not a characteristic easy to determine in C alone because your compiler may perform various optimizations that can break such tests. You would probably be better off with an assembly function.

In other words, your function could work, but it's not sure. And if it doesn't work, it won't report an error: instead, you'll get an incorrect result, and no way to tell. The stack, and the handling of calling conventions, are about the only two low-level things that C manages to hide.

My x86 assembler is rusty, but off my head, this (Intel syntax) assembly function could give the correct results. Its C prototype would be int getGrowthDirection(); it returns a positive number if the stack grows forward and a negative number if the stack grows in reverse direction.

getGrowthDirection:
    mov ebx, esp
    push esp
    sub ebx, esp
    xor eax, eax
    sub eax, ebx
    pop esp
    ret

Note that this function is next to useless, as assembly requires you to know the platform you're targetting, and if you know the platform you're targetting, then you should know the stack growth direction.

It has already been pointed out that a C execution environment does not necessarily use a stack (function activation frames may be allocated on a heap). So let us assume that we have a system that does use a stack for automatic variables. Then we might be able to determine the stack direction by comparing the addresses of variables from two different activation frames. However, there are two problems with this approach:

1. The comparison is illegal. If the compiler can tell that a comparison is illegal, or that the comparison, if it is legal, must have a particular result, then it might not generate code to perform the comparison. For example, if you compare two pointers to type T and the program contains no arrays of type T[] of length greater than 1 then the compiler might deduce that the pointers must compare equal.
2. How can we be sure that the variables really are in different activation frames? A compiler could convert some automatic variables into static variables and even recursive functions may be inlined (GCC inlines a simple recursive factorial function).

The first problem is insoluble if we have a symbolic execution environment that can detect an illegal pointer comparison at run time. So let us assume that we have a conventional optimising compiler that represents pointers with bare machine addresses (when they cannot be optimised away).

Thinking about all this I initially got distracted by the idea of converting the pointers into integers (C99's uintptr_t). But this is a red herring, I think. Firstly, comparing the integers might not give the same result as comparing the original pointers so you would have to convert them back anyway. Secondly, we are not trying to conceal from the compiler that we are comparing pointers; we are only trying to conceal from the compiler which pointers we are comparing.

I found it helped to consider the second problem first: how can we ensure that we have pointers to variables in different activation frames?

Let us reject the idea of putting one function in a separate library or dynamically loaded module: that would be non-portable, and if we are going to be non-portable then we might as well print out the pointers with printf("%p\n", p) and compare them with shell utilities. Apart from being non-portable that would also be no fun at all.

To force the compiler to generate code with local variables in activation frames we could have a function that is recursive to a depth that cannot be determined at compile time with a local variable that is potentially live across a recursive call, and so on. In short, we want to make it very hard, preferably impossible, for the compiler to determine what is going to happen at run time.

There are various ways we could make the execution predictable for us but unclear to the compiler. We could use complex mathematics or a pseudorandom number generator. However, it is probably good enough just to make it potentially depend on the command-line arguments, with the behaviour we want being the default behaviour with no arguments (hoping that no real-world compiler optimises a program by doing symbolic interpretation with the assumption that it will be executed with no arguments). So we could have the sequence of operations to be performed specified explicitly in argv[1] and the program would be a kind of mini-interpreter. With that approach I think I can answer the original question with the following program that tries to be portable by using no header files or library functions:

// Program to determine stack direction by Edmund Grimley Evans

void *mem[99];
void **p = mem;
char *pc;

void run(void)
{
    void *a[2];
    for (;;) {
        switch (*pc++) {
        case '+': ++p; break;
        case '-': --p; break;
        case 't': { void *t = p[0]; p[0] = p[1]; p[1] = t; } break;
        case 'a': p[0] = &a[0]; p[1] = &a[1]; break;
        case 'p': *p = p; break;
        case 'l': *p = *(void **)*p; break;
        case 's': *(void **)p[0] = p[1]; break;
        case '<': *p = (p[0] < p[1]) ? p : 0; break;
        case 'c': run(); break;
        case 'r': return;
        }
    }
}

int main(int argc, char *argv[])
{
    pc = argc == 2 ? argv[1] : "ac+ac+ac-<rrrr";
    run();
    return !!*p;
}

Here is a longer version with comments and trace output to explain how it works:

// Program to determine stack direction by Edmund Grimley Evans

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

void *mem[99]; // memory
void **p = mem; // pointer to memory
char *pc; // program counter

int depth = 0; // number of nested calls, only for debug

// An interpreter for a strange programming language.
// There are 10 instructions in the instruction set: "+-tapls<cr".
// Not all are used in the default program that determines the
// stack direction, but the others are required to prevent a clever
// compiler from deducing that pointers will never be dereferenced,
// or that a local variable will never be written to, for example.
void run(void)
{
    // The local variable is an array so that pointer comparison
    // might make sense:
    void *a[2];

    for (;;) {
        {
            // Print contents of memory:
            void **t, **e = mem + sizeof(mem) / sizeof(*mem) - 1;
            while (e > p && !*e)
                --e;
            printf("  %d:", depth);
            for (t = mem; t <= e; t++)
                printf(t == p ? " [%p]" : " %p", *t);
            printf("\n%c\n", *pc);
        }

        switch (*pc++) {

            // increment memory pointer:
        case '+': ++p; break;

            // decrement memory pointer:
        case '-': --p; break;

            // swap contents of adjacent memory cells:
        case 't': { void *t = p[0]; p[0] = p[1]; p[1] = t; } break;

            // save addresses of local array in memory:
        case 'a': p[0] = &a[0]; p[1] = &a[1]; break;

            // save address of memory itself in memory:
        case 'p': *p = p; break;

            // load:
        case 'l': *p = *(void **)*p; break;

            // store:
        case 's': *(void **)p[0] = p[1]; break;

            // compare two pointers:
        case '<': *p = (p[0] < p[1]) ? p : 0; break;

            // recursive call to interpreter:
        case 'c': ++depth; run(); --depth; break;

            // return:
        case 'r': return;

        default:
            printf("  Error!\n");
            exit(1);
        }
    }
}

int main(int argc, char *argv[])
{
    // The default program does three recursive calls and compares
    // addresses from the last two frames:
    pc = argc == 2 ? argv[1] : "ac+ac+ac-<rrrr";
    run();
    printf("  Exit with %p (%d)\n", *p, !!*p);
    return !!*p;
}

Note that I have hardly tested this program!

I was originally drawn to this problem by a failing autoconf test in the Debian "librep" package. However, I would hesitate to recommend an as yet untested program like this for use in an autoconf test. In practice I would guess it is safer to assume that all stacks are descending unless we have a recognised exception, such as Debian's "hppa" architecture.

In a Linux (or other Operating System) process when a subroutine is called, the memory for local variables comes from stack area of the process. Any dynamically allocated memory (using malloc, new, etc.) comes from the heap area of the process. During recursion local memory is allocated from stack area during function call and get cleared when the function execution is done.

The memory is being represented with lowest address being at the bottom and highest being at the top. Here are the steps to find the direction of stack growth in recursion using a quick C code.

#include <stdio.h>

void test_stack_growth_direction(recursion_depth) {
  int local_int1;
  printf("%p\n", &local_int1);
  if (recursion_depth < 10) {
    test_stack_growth_direction(recursion_depth + 1);
  }
}

main () {
  test_stack_growth_direction(0);
}

out put on MAC

0x7fff6e9e19ac
0x7fff6f9e89a8
0x7fff6f9e8988
0x7fff6f9e8968
0x7fff6f9e8948
0x7fff6f9e8928
0x7fff6f9e8908
0x7fff6f9e88e8
0x7fff6f9e88c8
0x7fff6f9e88a8
0x7fff6f9e8888

output on ubuntu

0x7ffffeec790c
0x7ffffeec78dc
0x7ffffeec78ac
0x7ffffeec787c
0x7ffffeec784c
0x7ffffeec781c
0x7ffffeec77ec
0x7ffffeec77bc
0x7ffffeec778c
0x7ffffeec775c
0x7ffffeec772c

The stack is growing downwards on these specific setups as memory addresses are reducing. This depends on the architecture of the system and may have different behavior for other architectures. 0x7fff6f9e8868