Говоря псевдокодом, вы можете назвать стек «массивом упакованных кадров стека», где каждый кадр стека представляет собой структуру данных переменного размера, которую вы можете выразить следующим образом:
template struct stackframe<N> {
uintptr_t contents[N];
#ifndef OMIT_FRAME_POINTER
struct stackframe<> *nextfp;
#endif
void *retaddr;
};
Проблема в том, что каждая функцияимеет различный <N> - размеры фреймов различаются.
Компилятор знает размеры фреймов, и если при создании отладочной информации они обычно выдаются как часть этого.Все, что нужно сделать отладчику, - это найти последний счетчик программы, найти функцию в таблице символов, а затем использовать это имя для поиска размера фрейма в информации отладки.Добавьте это к указателю стека, и вы попадете в начало следующего кадра.
Если вы используете этот метод, вам не требуется связывание кадров, и обратная трассировка будет работать нормально, даже если вы используете -fomit-frame-pointer.С другой стороны, если у вас есть связывание кадров, то итерация стека просто следует за связанным списком - потому что каждый указатель кадра в новом стековом кадре инициализируется кодом пролога функции, чтобы указывать на предыдущий.
Еслиу вас нет ни информации о размере фрейма, ни указателей фреймов, но все еще таблица символов, тогда вы также можете выполнить обратное отслеживание с помощью небольшого обратного инжиниринга, чтобы вычислить размеры фреймов из фактического двоичного файла.Начните со счетчика программы, найдите функцию, которой он принадлежит, в таблице символов, а затем разберите функцию с самого начала.Изолируйте все операции между началом функции и счетчиком программы, которые фактически изменяют указатель стека (записывают что-либо в стек и / или выделяют пространство стека).Это вычисляет размер кадра для текущей функции, поэтому вычтите его из стека указателя, и вы должны (на большинстве архитектур) найти последнее слово, записанное в стек перед вводом функции - обычно это адрес возврата в вызывающей стороне.Повторите при необходимости.
Наконец, вы можете выполнить эвристический анализ содержимого стека - изолировать все слова в стеке, которые находятся внутри исполняемых отображаемых сегментов адресного пространства процесса (и, следовательно, могут бытьфункция смещает обратные адреса) и играет в игру «что если», просматривая память, разбирая там инструкцию и проверяя, является ли она на самом деле инструкцией вызова, если да, то действительно ли это называется «следующий» и можно ли создатьнепрерывная последовательность вызовов из этого.Это работает до некоторой степени, даже если двоичный файл полностью удален (хотя в этом случае вы можете получить только список адресов возврата).Я не думаю, что GDB использует эту технику, но некоторые встроенные отладчики низкого уровня используют.В x86 из-за разной длины команд это ужасно сложно сделать, потому что вы не можете легко «шагнуть назад» через поток команд, но в RISC, где длины команд фиксированы, например, в ARM, это намного проще.
Есть некоторые дыры, из-за которых простые или даже сложные / исчерпывающие реализации этих алгоритмов иногда падают, например, хвосто-рекурсивные функции, встроенный код и так далее.Исходный код GDB может дать вам еще несколько идей:
http://sourceware.org/cgi-bin/cvsweb.cgi/src/gdb/frame.c?rev=1.287&content-type=text/x-cvsweb-markup&cvsroot=src
GDB использует множество таких методов.