19 февраля 2015 г.

Фреймы на стеке (стековые фреймы)

Эта статья обсуждает концепцию фреймов на стеке, что это такое, когда они создаются, когда они не создаются, на что они влияют, как они соотносятся со стеками вызовов.

Что такое стековые фреймы

Семейство процессоров x86 (как 32-битных, так и 64-битных) использует аппаратный стек процессора для хранения последовательности вызова подпрограмм (т.е. процедур, функций и методов) по мере их выполнения. Другие процессоры могут использовать для этого и другие способы. Стековые фреймы (также иногда называемые "фреймами вызовов", "записями активации" или "фреймами активации") представляют собой структуры в стеке процессора, которые содержат информацию о состоянии подпрограммы. Каждый стековый фрейм соответствует вызову какой-то подпрограммы, которая была вызвана, но ещё не завершилась. Например, если подпрограмма DrawLine была вызвана подпрограммой DrawSquare и пока ещё выполняется, то верхняя часть стека может выглядеть примерно так:


Примечание: не забывайте, что на x86 стек растёт от больших адресов к меньшим.

Стековый фрейм на вершине стека идентифицирует подпрограмму, которая выполняется прямо сейчас. Фрейм обычно содержит такую информацию (в порядке размещения на стеке):
  • Аргументы (значения параметров) подпрограммы (если они есть)
  • Адрес для возврата управления в вызывающую подпрограмму (т.е. в фрейме для DrawLine будет сохранён адрес какого-то кода внутри DrawSquare).
  • Место для локальных переменных подпрограммы (если они есть).
Кроме того, фрейм также имеет обязательное поле, в котором сохраняется предыдущее значение регистра фрейма (frame pointer register) - т.е. значение, которое там было, когда вызвали подпрограмму. Например, фрейм DrawLine будет иметь место для хранения значения регистра фрейма, которое использовала DrawSquare. Это значение сохраняется сразу при входе в подпрограмму, до выделения места под её локальные переменные (т.е. указатель на предыдущий фрейм хранится между адресом возврата и локальными переменными), и восстанавливается при выходе из подпрограммы. На рисунке выше это поле отдельно не показано, оно расположено в "Locals of DrawLine" сразу за "Return address" - т.е. в некотором роде это "первая локальная переменная".

Примечание: на x86-32 в качестве регистра фрейма используется регистр EBP - т.н. "база" стека (BP = Base Pointer).

Наличие такого поля в заранее известном месте позволяет коду перебрать цепочку фреймов, имея на руках указатель на текущий фрейм. И конечно же, это позволяет текущей подпрограмме легко восстановить состояние до её вызова. Другими словами, стековые фреймы образуют цепочку: каждый фрейм содержит указатель на предыдущий фрейм в цепочке.

Идея состоит в том, что каждая подпрограмма может работать вне зависимости от текущего положения на стеке, сохраняя предыдущий указатель стека и меняя "базу стека", она работает как если бы она была единственной подпрограммой на стеке. С этой точки зрения, всё, что было до неё - недоступно, а ей доступен "весь стек" - с базы и до конца. Подпрограмма всегда знает, где лежат её аргументы и локальные переменные - относительно якобы "вершины стека" (на самом деле - базы).

Здесь важно понять, что архитектура x86-32 не диктует обязательного использования стековых фреймов. Они могут создаваться, а могут и не создаваться - решение зависит от самой подпрограммы (читай: компилятора, который её создал). Некоторые подпрограммы могут сохранять только "голый" адрес возврата, вообще без какой-либо дополнительной информации и уж тем более без указателя на предыдущий фрейм. Архитектура x86-64, несмотря на её похожесть на x86-32, тем не менее, диктует обязательность использования фреймов.

Примечание: фреймы x86-32 отличаются от фреймов x86-64. x86-64 не использует указатель фрейма ("базу" стека). В этом смысле можно говорить, что x86-64 использует FPO (Frame Pointer Omission). Вместо этого x86-64 использует дополнительную информацию о функциях для работы с фреймами. Эта мета-информация для функций (размер функции, кол-во аргументов, блоки try-except, ...) тесно связана с data-driven обработкой исключений в x86-64. Она (мета-информация) генерируется компилятором и хранится внутри особой секции в исполняемом файле. А для динамически генерируемого кода необходимо добавлять такие мета-описания вручную. Аналога этой мета-информации на x86-32 просто нет.

Под стековым фреймом можно понимать как структуру целиком (аргументы, адрес возврата, ссылку на предыдущий фрейм, локальные переменные), так и только комбинацию "ссылка на предыдущий фрейм + адрес возврата". С точки зрения инструментов трассировки под фреймом обычно понимают второе.

Трассировка стека

Трассировка стека - это построение стека вызовов подпрограмм по аппаратному стеку. Поскольку фреймы вызовов образуют цепочку, которую легко "размотать", и, кроме того, содержат в себе адреса возврата, то информация из фреймов вызовов может быть использована для трассировки стека.

Как уже было сказано выше, фреймы вызовов не всегда создаются для архитектуры x86-32 (в отличие от x86-64). Это означает, что на x86-64 всегда можно построить гарантированно верный стек вызовов (конечно же, при условии, что данные в самом стеке не повреждены). Это невозможно для x86-32. Для x86-32 методы трассировки делятся на два класса: т.н. RAW и т.н. frame-based.

Frame-based методы трассировки

Frame-based методы трассировки ("методы трассировки, основывающиеся на фреймах") строят стек вызовов, используя информацию из стековых фреймов, которые создаются большинством подпрограмм (об этом "большинстве" - ниже). Обычно этот тип методов даёт приемлемые результаты (если вы не используете много слишком коротких методов - см. ниже). Эффективность методов этого класса можно увеличить включением опции "Stack Frames". Этот метод всегда работает точно (в смысле отсутствия ложно-положительных результатов) и быстро: он не сканирует весь стек, а ищет только "зарегистрированные" вызовы, проходя по цепочке фреймов, где каждый фрейм указывает на предыдущий. Этот метод не сможет работать с подпрограммами, скомпилированными с FPO-оптимизацией (не используется в Delphi), если подпрограмма не создаёт фрейма, в случае не стандартного соглашения вызова, либо в случае повреждения стека.

Примечание: можно сказать, что метод трассировки стека для x86-64 относится к классу frame-based методов.

Методы трассировки RAW

RAW методы работают иначе: они просто перебирают все значения в стеке, проверяя каждое значение, не является ли оно адресом возврата. Действительно, фреймы вызовов не всегда могут присутствовать в стеке (на x86-32), но адрес возврата будет сохранён всегда - ведь иначе из подпрограммы нельзя будет вернуть управление вызывающему. Проблема здесь в том, что нет никакого 100% способа узнать, является ли некоторое значение адресом возврата. Поэтому любой RAW-метод пытается это угадать. Иными словами, любой RAW-метод трассировки стека может использоваться только вместе с какой-то эвристикой (которая и будет определять "валидность" значений адресов). Таким образом, создаваемые стеки вызовов в значительной степени будут зависеть от характеристик используемой эвристики. Отсутствующая или имеющаяся отладочная информация также может значительно влиять на результаты, поскольку алгоритм эвристики может обращаться к ней за помощью в проверке. Некоторые особо продвинутые алгоритмы эвристики также используют дизассемблеризирование кода.

Примечание: на платформе x86-64 нет нужды в RAW-методах, поскольку существует способ точного построения стека по фреймам и мета-информации.

Когда создаются стековые фреймы (только для x86-32)

В x86-32 в некоторых случаях стековый фрейм может не создаваться (omitted). Посмотрите на такой код:

Опция "Stack Frames" отключена, опция "Optimization" включена
Примечание: не забудьте, что при изменении настроек проекта вам необходимо сделать полную сборку проекта (Project / Build) вместо простой компиляции (Project / Compile) - иначе уже скомпилированные модули не будут пересобраны с новыми настройками.

Заметьте, что слева от строки "begin" нет синей точки. Что это значит? Это значит, что строка "begin" не генерирует машинного кода. Т.е. в этой подпрограмме отсутствует код по созданию фрейма на стеке. Это произошло потому, что эта подпрограмма очень простая, в нет ней необходимости для создания фрейма.

Примечание: напротив, строка с "end" генерирует код. В данном случае в этой строке будет стоять возврат управления в вызывающую подпрограмму (TControl.Click).

Эти факты можно подтвердить просмотром кода Button1Click в машинном отладчике:

Машинный код обработчика Button1Click из примера выше
Попробуем включить опцию "Stack Frames":

Опция "Stack Frames" включена
Примечание: вместо включения опции "Stack Frames" можно выключить опцию "Optimization" - это приведёт к ровно тому же эффекту.

Это тот же самый код, но теперь он скомпилирован с включенной опцией "Stack Frames". Обратите внимание, что теперь слева от строки "begin" стоит синяя точка. Это означает, что теперь эта строка генерирует машинный код - и это код по созданию фрейма. Иными словами, опция "Stack Frames" насильно заставляет компилятор всегда создавать фреймы на стеке, даже если в них нет прямой необходимости.

Примечание: хотя это не указано в документации, но опция "Stack Frames" ничего не делает на платформе x86-64.

Вот как выглядит новая версия кода под машинным отладчиком:

Новый машинный код обработчика Button1Click
Как вы можете видеть, здесь компилятор создаёт простейший стековый фрейм - сохраняя предыдущее значение указателя "базы" стека и меняя базу стека на начало текущей подпрограммы. При выходе производятся обратные действия.

Но посмотрим теперь на такой код:

Опция "Stack Frames" выключена
Как вы можете видеть, этот код тоже создаёт фрейм - даже хотя опция "Stack Frames" выключена. Это происходит потому, что в коде используется локальная переменная типа string. String - это сложный авто-управляемый тип, компилятору требуется использовать для него код инициализации и финализации, вот почему он создаёт стековый фрейм.

Если бы мы не использовали строки в подпрограмме (а, скажем, использовали бы только Integer), то код подпрограммы остался простым, так что компилятор смог бы обойтись без создания стекового фрейма.

Использование авто-управляемых типов - не единственное условие, при котором компилятору нужны фреймы. Большое количество локальных переменных и аргументов, сложные выражения, использование исключений - всё это также приведёт к созданию фрейма. В итоге, более-менее сложная подпрограмма будет иметь стековый фрейм вне зависимости от состояния опции "Stack Frames" - потому что компилятору нужен стековый фрейм для управления данными подпрограммы.

Как стековые фреймы влияют на стеки вызовов (только для x86-32)

Я приведу два примера как стековые фреймы влияют на стеки вызовов.

Фреймы и смещения

Трейсеры исключений (и другие отладочные инструменты) позволяют вам просматривать т.н. "строковые смещения". Строковое смещение вычисляется как разница между текущим положением и началом подпрограммы. Например:

Номера строк для подпрограммы со стековым фреймом
Вызов метода Hide расположен в строке 28[1], что читается как "строка №28, она отстоит от начала подпрограммы на одну строчку".

Примечание: некоторые инструменты могут сообщать этот же факт как 28[2], что читается как: "вторая строка в подпрограмме" - другими словами, одни инструменты используют 1-нумерацию, а другие - 0-нумерацию.

В любом случае, смысл в том, что "первой строкой" подпрограммы здесь считается строка с "begin" - а вовсе не заголовок ("procedure") и не первый оператор в подпрограмме. Ведь начало подпрограммы определяется её кодом. И первой строчкой в этой программе, которая генерирует код, является "begin" - что и указывается наличием синей точки слева от этой строки. Напротив заголовков, объявлений (локальных переменных) и т.д. таких точек нет, поскольку эти строки не генерируют машинного кода. Таким образом, строка "begin" является первой строкой в подпрограмме и имеет номер 27, строка с "Hide" является второй строчкой и имеет номер 28 - соответственно, разница между ними будет равна 1 - именно эта 1 и закодирована в записи 28[1].

Как вы могли уже догадаться, строковые смещения зависят от стековых фреймов, а точнее - от их наличия или отсутствия. Посмотрите на этот же код, но без стекового фрейма:

Номера строк для подпрограммы без фрейма
Вызов метода Hide теперь расположен в строке 28[0], что читается как "строка №28, она имеет нулевое смещение от первой строки в подпрограмме, т.е. она является первой строкой в подпрограмме" (и снова, некоторые инструменты могут сообщать этот же факт как 28[1] - используя 1-нумерацию).

В этом случае первой строкой подпрограммы стала строка с "Hide", а строка с "begin" и вовсе не генерирует кода.

В результате, если вы получили отчёт со стеком вызовов от старой версии программы, то вам нужно использовать не точные значения номеров строк, а имена подпрограмм и строковые смещения. Вы должны учитывать опции, с которыми создан ваш код, чтобы правильно отсчитать строки. И если вы меняли опции между сборками, то вам, возможно, потребуется делать правки на +/-1.

Фреймы и методы трассировки

Модули RTL и VCL скомпилированы с выключенной опцией "Stack Frames". Это означает, что любой frame-based метод трассировки стека не сможет находить "простые" подпрограммы в модулях RTL/VCL.

Однако, этот факт также имеет менее очевидное следствие. Посмотрите на такой код:

Утечка простого объекта, опция "Stack Frames" включена
Этот код создаёт утечку памяти, создавая неучтённый экземпляр TStringList. Отладочный менеджер памяти обнаружит эту утечку и создаст для неё стек вызовов.

Примечание: для этого примера вы также можете использовать возбуждение исключения и трейсер исключений, но вам нужно быть уверенным, что вы возбуждаете исключение внутри кода RTL/VCL.

Как вы можете видеть, обработчик Button1Click имеет фрейм - из-за включенной опции "Stack Frames". Вы можете ожидать, что стек вызовов для этой утечки памяти будет содержать упоминание Button1Click.

Но этого не произойдёт.

Стековый фрейм от Button1Click позволяет идентифицировать вызывающего (в данном случае: TControl.Click). Действительно, стековый фрейм содержит информацию о вызывающем: это - адрес возврата. Адрес возврата для Button1Click будет указывать на TControl.Click.

Но что насчёт обработчика Button1Click? Адрес возврата в него будет сохранён в вызванном конструкторе TStringList. TStringList - класс из RTL, и, следовательно, он скомпилирован с выключенной опцией "Stack Frames". Поэтому конструктор TStringList не будет иметь стекового фрейма (поскольку он очень простой). Следовательно, frame-based метод трассировки не обнаружит стекового фрейма от конструктора TStringList, а, значит, не увидит и адрес возврата к Button1Click. В итоге, frame-based метод трассировки не увидит метод Button1Click.

Примечание: при желании вы можете перекомпилировать RTL/VCL с включенной опцией "Stack Frames".

Заключение

Краткие выводы:
  1. Для x86-32 существует несколько разных способов строить стеки вызовов, все они используют различные допущения и эвристики;
  2. Напротив, для x86-64 существует способ построить 100% верный стек вызовов;
  3. RAW методы трассировки дадут больше записей в стеке, frame-based методы дадут меньше (как правило);
  4. RAW методы могут показывать ложно-положительные вызовы, frame-based методы всегда пропустят вызовы без стекового фрейма;
  5. RAW методы - это медленно, frame-based методы - это быстро;
  6. Отсутствие стекового фрейма можно обнаружить по отсутствию синей точки слева от строки с "begin";
  7. Стековые фреймы создаются почти всегда:
    1. Стековые фреймы создаются:
      1. На платформе x86-64 или...
      2. Если включена опция "Stack frames" или...
      3. Если выключена опция "Optimization" или...
      4. В подпрограмме много кода (аргументов, параметров, выражений) или...
      5. В подпрограмме есть блок обработки исключений или...
      6. Подпрограмма использует авто-управляемый тип (строки, динамические массивы, варианты, интерфейсы);
    2. Стековые фреймы не создаются:
      1. Платформа - x86-32 и...
      2. Опция "Stack frames" выключена и...
      3. Опция "Optimization" включена и...
      4. Подпрограмма слишком проста и короткая (аргументы, локальные параметры, выражения, нет блоков обработки исключений и авто-управляемых типов);
  8. Присутствующий стековый фрейм добавит 1 к строковому смещению в записи стека вызова, соответствующей данной подпрограмме;
  9. RTL и VCL скомпилированы без опции "Stack frames";
  10. Фреймовый стек предоставляет информацию о вызывающем (адрес возврата);
  11. Фреймовый стек не влияет на то, окажется ли в стеке вызовов текущая подпрограмма.

Примечание: возможно, мне не стоило смешивать две разные вещи. Если слева от "begin" стоит синяя точка - это ещё не означает присутствие стекового фрейма. Возможно, компилятор просто сохранил регистры в стек перед вычислением сложного выражения. Такая процедура не внесёт вклад в стек вызовов (её вызывающий не будет обнаружен), но даст прирост строкового смещения.

9 комментариев :

  1. Наверное это подходящая статья, чтобы спросить. Иногда при трассировке стека хочется странного, а именно - получить значения параметров. В интернете встречал мнение что в случае с делфи это невозможно, т.к. по умолчанию параметры передаются через регистры и перетираются. Но ведь процедура, использующая параметры, их из регистров всё равно достает (и, насколько я могу увидеть, складывает рядом с ebp). Почему их нельзя оттуда получить?
    Окей, предположим получить такие параметры всё таки нельзя, но ведь их может быть всего 3, а в случае с методами классов и вовсе 2. Значит должно быть можно получить остальные, т.к. они все равно лежат в стеке?

    ОтветитьУдалить
  2. Я как-то использовал легковесную библиотеку для получения трассы стека (uLkStackTrace.pas). Все работало.
    Но т.к. exe-файл подписывался на этапе сборки инсталлятора, происходило смещение адресов, и в реальной работе имена функций в стеке были неверными.
    Случайно не посоветуете как эту проблему решить?

    ОтветитьУдалить
  3. >>> получить значения параметров

    В общем случае это невозможно.

    Дело тут не в Delphi и даже не в соглашении вызова. Если компилятор оптимизирующий, то параметры не живут дольше их последнего использования. Т.е. если, к примеру, подпрограмма при входе сохранила параметр в, скажем, поле объекта, то ниже по тексту этот параметр (где бы он ни был сохранён - в регистре или стеке) будет перезаписан под что-то более нужное.

    Нет никакой возможности узнать, что делает код с этим параметром. Может быть, код использует его. Может быть, продолжает хранить, где он был передан. Может быть, копирует в другое, более удобное место. Человек это может понять, посмотрев машинный код. Компилятор это знает, т.к. он же этот код и собирал, у него есть учёт какие данные куда идут.

    Внешний же код этого знать не может.

    Дело не изменяется даже в x86-64. Хотя соглашение вызова x86-64 резервирует место на стеке специально для хранения параметров ("param spilling"), но нет никакого требования именно хранить там параметры. Поэтому оптимизирующий компилятор использует это место как "песочницу" - просто дополнительную свободную память, доступную подпрограмме.

    Само собой, в частных случаях это сделать можно. Так что весь вопрос упирается в то, насколько частный ваш случай. Если вам нужно делать это для конкретной подпрограммы - можно попробовать использовать соглашение вызова, которое передаёт параметры в стеке, и стек чистит вызывающий. Под такое определение подходит cdecl.

    >>> exe-файл подписывался на этапе сборки инсталлятора, происходило смещение адресов

    Что? Каким образом подпись влияет на адреса? Есть мнение, что происходит что-то другое.

    ОтветитьУдалить
  4. >>> Каким образом подпись влияет на адреса?
    Опытным путем установлено, что до подписи адреса процедур из map-файла корректные, а после подписи уже нет.
    м.б. адрес загрузки модуля меняется.

    ОтветитьУдалить
  5. >>> адрес загрузки модуля меняется

    Это можно проверить в любом просмотрщике PE (многие HEX-редакторы также имеют такую возможность).

    >>> Опытным путем установлено, что до подписи адреса процедур из map-файла корректные, а после подписи уже нет

    Речь точно идёт о цифровой подписи, а не протекторе? Классическая цифровая подпись НЕ меняет данные.

    Для подписываемого файла вычисляется его хэш, на базе хэша создаётся сертификат для подписи, сертификат записывается в конец исполняемого файла. Из хэша исключается поле Checksum, запись Certificate Table в опциональном заголовке PE и сами данные сертификата в конце файла. Для валидации ОС считает хэш (с тремя исключениями выше) и сравниваем его с сертификатом.

    Как видите, в этом алгоритме нет "изменить базовый адрес" или чего-то такого. Так что вы видите что-то другое.

    ОтветитьУдалить
  6. Анонимный15 мая 2015 г., 14:32

    Добавлю ссыль на Кадр стека x86-64 (eng).
    По ссылке раскрыта информация, которая отсутствует в данной статье: красная зона или область параметров.
    И еще один ссыль x86-64 ABI (eng, pdf).



    ОтветитьУдалить
    Ответы
    1. Спасибо за ссылку.

      Ну, это блог про Delphi. 64-битные приложения Delphi умеет создавать только под Windows. В Windows красной зоны нет. Вместо этого есть зона параметров, которую я кратко упомянул, без деталей.

      Удалить

Можно использовать некоторые HTML-теги, например:

<b>Жирный</b>
<i>Курсив</i>
<a href="http://www.example.com/">Ссылка</a>

Вам необязательно регистрироваться для комментирования - для этого просто выберите из списка "Анонимный" (для анонимного комментария) или "Имя/URL" (для указания вашего имени и (опционально) ссылки на сайт). Все прочие варианты потребуют от вас входа в вашу учётку (поддерживается OpenID).

Пожалуйста, по возможности используйте "Имя/URL" вместо "Анонимный". URL можно просто не указывать.

Ваше сообщение может быть помечено как спам спам-фильтром - не волнуйтесь, оно появится после проверки администратором.