It has already been noted that the C runtime does not necessarily use the stack (function activation frames can be heaped). So, let's say we have a system that uses a stack for automatic variables. Then we could determine the direction of the stack by comparing the addresses of variables from two different activation frames. However, there are two problems with this approach:
- Comparison is illegal. If the compiler can say that the comparison is illegal or that the comparison, if it is legal, should have a specific result, then it may not generate code to perform the comparison. For example, if you are comparing two pointers to type T, and the program does not contain arrays of type T [] longer than 1, then the compiler can deduce that pointers should compare equal.
- How can we be sure that the variables are indeed in different activation frames? The compiler can convert some automatic variables to static variables, and even recursive functions can be inlined (GCC builds a simple recursive factorial function).
The first problem is unsolvable if we have a symbolic runtime that can detect illegal pointer comparisons at runtime. So, let's say that we have a regular optimizing compiler that represents pointers with a bare machine (when they cannot be optimized).
Thinking about all this, I first got distracted by the idea of converting pointers to integers (C99 uintptr_t). I think this is red herring. First, comparing integers may not produce the same result as comparing the original pointers, so you still have to translate them back. Secondly, we are not trying to hide from the compiler that we are comparing pointers; we are only trying to hide from the compiler which pointers we are comparing.
I found that this helped to consider the second problem first: how can we guarantee that we have pointers to variables in different activation frames?
Let's give up the idea of putting one function in a separate library or dynamically loaded module: it will not be portable, and if we are going to be portable, then we could also print pointers with printf ("% p \ n", p) and compare them with shell utilities. Besides the fact that it is not tolerated, it will also not be funny.
To force the compiler to generate code with local variables in activation frames, we could have a function that is recursive for depth, which cannot be determined at compile time with a local variable that could potentially interact through a recursive call, and so on, in short, we want to make it very difficult, and possibly impossible, for the compiler to determine what happens at runtime.
There are various ways in which we could make predictable execution for us, but it is not clear to the compiler. We could use complex math or a pseudo random number generator. However, this is probably good enough to make it potentially depend on command line arguments, and the behavior we want is the default behavior without arguments (hoping that no real-world compiler optimizes the program, making a symbolic interpretation with the assumption that it will be executed without arguments). Thus, we could perform a sequence of operations specified explicitly in argv [1], and the program would be a kind of mini-interpreter. With this approach, I think I can answer the original question with the following program, which tries to be portable without using 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 conclusions to explain how this 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; }
Please note that I almost did not test this program!
I was initially brought to this problem by the failed autoconf test in the Debian librep package. However, I hesitate to recommend a yet untested program like this one for use in the autoconf test. In practice, I would suggest that it is safer to assume that all stacks go down unless we have a recognized exception, such as the Debian "hppa" architecture.