Уже указывалось, что среда выполнения C не обязательно использует стек (кадры активации функции могут быть размещены в куче). Итак, давайте предположим, что у нас есть система, которая использует стек для автоматических переменных. Тогда мы сможем определить направление стека, сравнивая адреса переменных из двух разных фреймов активации. Однако у этого подхода есть две проблемы:
- Сравнение незаконно. Если компилятор может сказать, что сравнение недопустимо или что сравнение, если оно допустимо, должно иметь конкретный результат, то он может не сгенерировать код для выполнения сравнения. Например, если вы сравниваете два указателя с типом T и программа не содержит массивов типа T [] длиной больше 1, то компилятор может сделать вывод, что указатели должны сравниваться равными.
- Как мы можем быть уверены, что переменные действительно находятся в разных кадрах активации? Компилятор может преобразовать некоторые автоматические переменные в статические переменные, и даже встроенные рекурсивные функции могут быть встроены (GCC содержит простую рекурсивную факториальную функцию).
Первая проблема неразрешима, если у нас есть символическая среда выполнения, которая может обнаружить недопустимое сравнение указателей во время выполнения. Итак, давайте предположим, что у нас есть обычный оптимизирующий компилятор, который представляет указатели с пустыми машинными адресами (когда их нельзя оптимизировать).
Размышляя обо всем этом, я изначально отвлекся на идею преобразования указателей в целые числа (uintptr_t в C99). Но это красная сельдь, я думаю. Во-первых, сравнение целых чисел может не дать того же результата, что и сравнение исходных указателей, поэтому вам все равно придется преобразовывать их обратно. Во-вторых, мы не пытаемся скрыть от компилятора, что мы сравниваем указатели; мы только пытаемся скрыть от компилятора , какие указатели мы сравниваем.
Я обнаружил, что это помогло сначала рассмотреть вторую проблему: как мы можем обеспечить наличие указателей на переменные в разных фреймах активации?
Давайте отвергнем идею поместить одну функцию в отдельную библиотеку или динамически загружаемый модуль: это было бы непереносимо, и если мы собираемся быть непереносимыми, то мы могли бы также распечатать указатели с помощью printf ( "% p \ n", p) и сравните их с утилитами оболочки. Помимо непереносимости, это тоже было бы совсем не весело.
Чтобы заставить компилятор генерировать код с локальными переменными в кадрах активации, у нас может быть функция, которая является рекурсивной по глубине, которая не может быть определена во время компиляции с локальной переменной, которая потенциально может существовать во время рекурсивного вызова, и так далее , Короче говоря, мы хотим, чтобы компилятору было очень трудно, желательно невозможно, определить, что произойдет во время выполнения.
Существуют различные способы сделать выполнение предсказуемым для нас, но неясным для компилятора. Мы могли бы использовать сложную математику или генератор псевдослучайных чисел. Тем не менее, это, вероятно, достаточно просто для того, чтобы сделать его потенциально зависимым от аргументов командной строки, при этом поведение, которое мы хотим, является поведением по умолчанию без аргументов (надеясь, что ни один реальный компилятор не оптимизирует программу, выполняя символическую интерпретацию с допущением что это будет выполнено без аргументов). Таким образом, мы можем иметь последовательность операций, которые должны быть явно указаны в argv [1], и программа будет своего рода мини-интерпретатором.
При таком подходе я думаю, что смогу ответить на исходный вопрос с помощью следующей программы, которая пытается быть переносимой без использования заголовочных файлов или библиотечных функций:
// 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;
}
Вот более длинная версия с комментариями и выводом трассировки, чтобы объяснить, как она работает:
// 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;
}
Обратите внимание, что я с трудом тестировал эту программу!
Первоначально меня привлекла эта проблема из-за неудачного теста autoconf в пакете Debian "librep". Тем не менее, я бы не рекомендовал пока что непроверенную программу, подобную этой, для использования в тесте autoconf. На практике я бы предположил, что безопаснее предполагать, что все стеки убывают, если у нас нет распознанного исключения, такого как архитектура hppa Debian.