Стек вызовов - Call stack

В Информатика, а стек вызовов это куча структура данных в котором хранится информация об активном подпрограммы из компьютерная программа. Такой стек также известен как стек выполнения, стек программ, стек управления, стек времени выполнения, или же машинный стек, и часто сокращается до "стек". Хотя обслуживание стека вызовов важно для правильного функционирования большинства программного обеспечения, детали обычно скрыты и автоматически в языки программирования высокого уровня. Многие компьютерные наборы инструкций предоставить специальные инструкции по работе со стопками.

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

Описание

Поскольку стек вызовов организован как куча, вызывающая сторона помещает адрес возврата в стек, а вызываемая подпрограмма, когда она завершается, тянет или хлопает адрес возврата из стека вызовов и передает управление этому адресу. Если вызываемая подпрограмма вызывает еще одну подпрограмму, она помещает другой адрес возврата в стек вызовов и так далее, при этом информация накапливается и распаковывается в соответствии с требованиями программы. Если нажатие занимает все пространство, выделенное для стека вызовов, возникает ошибка, называемая переполнение стека происходит, обычно заставляя программу крушение. Добавление записи подпрограммы в стек вызовов иногда называют «намоткой»; и наоборот, удаление записей "раскручивает".

Обычно существует ровно один стек вызовов, связанный с запущенной программой (или, точнее, с каждой задача или же нить из процесс ), хотя могут быть созданы дополнительные стеки для сигнал обработка или совместная многозадачность (как с setcontext ). Поскольку в этом важном контексте есть только один, его можно назвать то стек (неявно «задачи»); однако в Язык программирования Forth то стек данных или же стек параметров доступ к нему осуществляется более явно, чем к стеку вызовов, и его обычно называют то стек (см. ниже).

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

Функции стека вызовов

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

В зависимости от языка, операционной системы и машинной среды стек вызовов может служить дополнительным целям, включая, например:

Локальное хранилище данных
Смотрите также: Распределение памяти на основе стека
Подпрограмме часто требуется место в памяти для хранения значений локальные переменные, переменные, которые известны только в рамках активной подпрограммы и не сохраняют значения после ее возврата. Часто бывает удобно выделить пространство для этого использования, просто переместив верх стека на столько, чтобы освободить место. Это очень быстро по сравнению с распределение динамической памяти, который использует пространство кучи. Обратите внимание, что каждая отдельная активация подпрограммы получает свое собственное отдельное пространство в стеке для локальных пользователей.
Передача параметров
Подпрограммы часто требуют, чтобы значения для параметры могут быть предоставлены им кодом, который их вызывает, и нередко пространство для этих параметров может быть размещено в стеке вызовов. Обычно, если есть всего несколько небольших параметров, регистры процессора будет использоваться для передачи значений, но если параметров больше, чем можно обработать таким образом, потребуется место в памяти. Стек вызовов хорошо работает как место для этих параметров, тем более что каждый вызов подпрограммы, которая будет иметь разные значения параметров, будет иметь отдельное место в стеке вызовов для этих значений.
Оценочный стек
Операнды для арифметических или логических операций чаще всего помещаются в регистры и обрабатываются там. Однако в некоторых ситуациях операнды могут быть сложены до произвольной глубины, что означает необходимость использования чего-то большего, чем регистры (это случай зарегистрировать разлив ). Стек таких операндов, примерно как в Калькулятор РПН, называется стеком оценки и может занимать место в стеке вызовов.
Указатель к текущему экземпляру
Немного объектно-ориентированные языки (например., C ++ ), сохраните это указатель вместе с аргументами функции в стеке вызовов при вызове методов. В это указатель указывает на объект пример связанный с вызываемым методом.
Включение контекста подпрограммы
Некоторые языки программирования (например, Паскаль и Ада ) поддержка объявления вложенные подпрограммы, которым разрешен доступ к контексту включающих их подпрограмм, то есть к параметрам и локальным переменным в рамках внешних подпрограмм. Такое статическое вложение может повторяться - функция, объявленная внутри функции, объявленной внутри функции ... Реализация должна предоставлять средства, с помощью которых вызываемая функция на любом заданном статическом уровне вложенности может ссылаться на охватывающий фрейм на каждом охватывающем уровне вложенности. Обычно эта ссылка реализуется указателем на кадр самого последнего активированного экземпляра включающей функции, называемого «нисходящей ссылкой» или «статической ссылкой», чтобы отличать ее от «динамической ссылки», которая относится к непосредственному вызывающему ( которая не обязательно должна быть статической родительской функцией).

Вместо статической ссылки ссылки на включающие статические фреймы могут быть собраны в массив указателей, известный как отображать который индексируется для поиска нужного кадра. Глубина лексической вложенности подпрограммы является известной константой, поэтому размер отображения подпрограммы является фиксированным. Кроме того, известно количество охватывающих областей, которые необходимо пересечь, индекс в отображении также фиксирован. Обычно отображение процедуры располагается в собственном стековом фрейме, но Берроуз B6500 реализовал такой дисплей аппаратно, который поддерживал до 32 уровней статической вложенности.
Записи отображения, обозначающие содержащие области, берутся из соответствующего префикса отображения вызывающего абонента. Внутренняя процедура, которая рекурсивно создает отдельные кадры вызова для каждого вызова. В этом случае все статические ссылки внутренней подпрограммы указывают на один и тот же контекст внешней подпрограммы.
Другое состояние возврата
Помимо адреса возврата, в некоторых средах могут быть другие состояния машины или программного обеспечения, которые необходимо восстановить при возврате подпрограммы. Сюда могут входить такие вещи, как уровень привилегий, информация об обработке исключений, арифметические режимы и так далее. При необходимости это может быть сохранено в стеке вызовов так же, как адрес возврата.

Типичный стек вызовов используется для адреса возврата, локальных переменных и параметров (известных как кадр вызова). В некоторых средах стеку вызовов может быть назначено больше или меньше функций. в Язык программирования Forth, например, обычно только адрес возврата, подсчитываемые параметры цикла и индексы и, возможно, локальные переменные хранятся в стеке вызовов (который в этой среде называется возвратный стек), хотя любые данные могут быть временно помещены туда с помощью специального кода обработки стека возврата, если соблюдаются потребности вызовов и возвратов; параметры обычно хранятся на отдельном стек данных или же стек параметров, обычно называемый то stack в терминологии Forth, даже если существует стек вызовов, поскольку к нему обычно обращаются более явно. У некоторых фортов также есть третий стек для плавающая точка параметры.

Структура

Схема стека вызовов для растущих вверх стеков

А стек вызовов состоит из кадры стека (также называемый записи активации или же кадры активации). Это зависит от машины и ABI -зависимые структуры данных, содержащие информацию о состоянии подпрограммы. Каждый кадр стека соответствует вызову подпрограммы, которая еще не завершилась возвратом. Например, если подпрограмма с именем DrawLine в настоящее время запущен, был вызван подпрограммой DrawSquare, верхняя часть стека вызовов может быть расположена, как на соседнем рисунке.

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

Фрейм стека в верхней части стека предназначен для выполняющейся в данный момент процедуры. Кадр стека обычно включает в себя как минимум следующие элементы (в порядке отправки):

  • аргументы (значения параметров), переданные в подпрограмму (если есть);
  • адрес возврата обратно к вызывающему подпрограмме (например, в DrawLine кадр стека, адрес в DrawSquareкод); и
  • место для локальных переменных процедуры (если есть).

Указатели стека и фрейма

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

Расположение всех других полей в кадре может быть определено либо относительно верха кадра, как отрицательные смещения указателя стека, либо относительно верха нижнего кадра, как положительные смещения указателя кадра. Местоположение самого указателя фрейма должно быть определено как отрицательное смещение указателя стека.

Сохранение адреса во фрейме звонящего

В большинстве систем стековый фрейм имеет поле, содержащее предыдущее значение регистра указателя фрейма, значение, которое он имел во время выполнения вызывающей стороны. Например, кадр стека DrawLine будет иметь ячейку памяти, содержащую значение указателя кадра, которое DrawSquare использует (не показано на диаграмме выше). Значение сохраняется при входе в подпрограмму и восстанавливается при возврате. Наличие такого поля в известном месте в фрейме стека позволяет коду обращаться к каждому фрейму последовательно под фреймом выполняющейся в данный момент подпрограммы, а также позволяет подпрограмме легко восстанавливать указатель фрейма на звонящий кадр, непосредственно перед его возвращением.

Лексически вложенные подпрограммы

Дальнейшая информация: Вложенная функция и Нелокальная переменная

Языки программирования, поддерживающие вложенные подпрограммы также есть поле в кадре вызова, которое указывает на кадр стека самый последний активация процедуры, которая наиболее точно инкапсулирует вызываемого, т.е. немедленное объем вызываемого. Это называется ссылка для доступа или же статическая ссылка (поскольку он отслеживает статическое вложение во время динамических и рекурсивных вызовов) и предоставляет подпрограмме (а также любым другим подпрограммам, которые она может вызывать) доступ к локальным данным своих инкапсулирующих подпрограмм на каждом уровне вложенности. Некоторые архитектуры, компиляторы или варианты оптимизации хранят по одной ссылке для каждого уровня включения (а не только непосредственно включающего), так что глубоко вложенные подпрограммы, которые обращаются к неглубоким данным, не должны проходить через несколько ссылок; эту стратегию часто называют «демонстрацией».[2]

Ссылки доступа могут быть оптимизированы, когда внутренняя функция не имеет доступа к каким-либо (непостоянным) локальным данным в инкапсуляции, как, например, в случае с чистыми функциями, общающимися только через аргументы и возвращаемые значения. Некоторые исторические компьютеры, такие как Большие системы Берроуза, имели специальные «регистры отображения» для поддержки вложенных функций, в то время как компиляторы для большинства современных машин (таких как вездесущий x86) просто резервируют несколько слов в стеке для указателей, если это необходимо.

Перекрывать

Для некоторых целей кадр стека подпрограммы и кадр ее вызывающей стороны можно рассматривать как перекрывающиеся, причем перекрытие состоит из области, в которой параметры передаются от вызывающей стороны к вызываемой. В некоторых средах вызывающий помещает каждый аргумент в стек, таким образом расширяя его кадр стека, а затем вызывает вызываемого. В других средах вызывающий имеет предварительно выделенную область в верхней части кадра стека для хранения аргументов, которые он передает другим вызываемым им подпрограммам. Эту область иногда называют область исходящих аргументов или же область выноски. При таком подходе размер области вычисляется компилятором как самый большой, необходимый для любой вызываемой подпрограммы.

Использовать

Обработка звонков на сайт

Обычно манипуляции со стеком вызовов, необходимые на месте вызова подпрограммы, минимальны (что хорошо, поскольку для каждой вызываемой подпрограммы может быть много участков вызова). Значения фактических аргументов оцениваются на сайте вызова, поскольку они специфичны для конкретного вызова, и либо помещаются в стек, либо помещаются в регистры, как определено используемым соглашение о вызовах. Фактическая инструкция вызова, такая как «переход и ссылка», затем обычно выполняется для передачи управления коду целевой подпрограммы.

Обработка записи подпрограммы

В вызываемой подпрограмме первый выполненный код обычно называется пролог подпрограммы, так как он выполняет необходимую уборку перед запуском кода для операторов подпрограммы.

Для архитектур с набором команд, в которых инструкция, используемая для вызова подпрограммы, помещает адрес возврата в регистр, а не помещает его в стек, пролог обычно сохраняет адрес возврата, помещая значение в стек вызовов, хотя, если вызываемый подпрограмма не вызывает никаких других подпрограмм, она может оставить значение в регистре. Точно так же могут быть переданы значения текущего указателя стека и / или указателя кадра.

Если используются указатели кадров, пролог обычно устанавливает новое значение регистра указателя кадра из указателя стека. Затем можно выделить пространство в стеке для локальных переменных, постепенно изменяя указатель стека.

В Язык программирования Forth разрешает явную намотку стека вызовов (называемого там «стеком возврата»).

Обработка возврата

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

Размотка

Возврат из вызванной функции вытолкнет верхний фрейм из стека, возможно, оставив возвращаемое значение. Более общий акт выталкивания одного или нескольких кадров из стека для возобновления выполнения в другом месте программы называется разматывание стека и должны выполняться, когда используются нелокальные управляющие структуры, например, используемые для Обработка исключений. В этом случае кадр стека функции содержит одну или несколько записей, определяющих обработчики исключений. Когда генерируется исключение, стек разворачивается до тех пор, пока не будет найден обработчик, готовый обработать (перехватить) тип выброшенного исключения.

В некоторых языках есть другие управляющие структуры, требующие общей раскрутки. Паскаль позволяет глобальный идти к оператор для передачи управления из вложенной функции в ранее вызванную внешнюю функцию. Эта операция требует, чтобы стек был размотан, удалив столько кадров стека, сколько необходимо для восстановления правильного контекста, чтобы передать управление целевому оператору внутри внешней функции. Аналогично, C имеет setjmp и longjmp функции, которые действуют как нелокальные переходы. Common Lisp позволяет контролировать, что происходит, когда стек раскручивается, используя расслабиться-защитить специальный оператор.

При применении продолжение, стек (логически) разматывается, а затем перематывается со стеком продолжения. Это не единственный способ реализовать продолжения; например, используя несколько явных стеков, приложение продолжения может просто активировать свой стек и намотать значение для передачи. В Язык программирования схем позволяет произвольно thunks для выполнения в указанных точках при «раскручивании» или «перемотке» стека управления при вызове продолжения.

Осмотр

Смотрите также: Профилирование (компьютерное программирование)

Стек вызовов иногда можно проверить во время работы программы. В зависимости от того, как программа написана и скомпилирована, информация в стеке может использоваться для определения промежуточных значений и трассировки вызовов функций. Это было использовано для генерации детализированных автоматических тестов,[3] и в таких случаях, как Ruby и Smalltalk, для реализации первоклассных продолжений. Например, Отладчик GNU (GDB) реализует интерактивную проверку стека вызовов запущенной, но приостановленной программы C.[4]

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

Безопасность

Основная статья: Переполнение буфера стека

На языке со свободными указателями или записью непроверенных массивов (например, в C) смешивание данных потока управления, влияющих на выполнение кода (адреса возврата или сохраненные указатели кадров) и простых данных программы (параметры или возвращаемые значения) ) в стеке вызовов представляет угрозу безопасности, возможно пригодный для использования через переполнение буфера стека как наиболее распространенный вид переполнение буфера.

Одна из таких атак включает заполнение одного буфера произвольным исполняемым кодом, а затем переполнение того же или какого-либо другого буфера для перезаписи некоторого адреса возврата значением, которое указывает непосредственно на исполняемый код. В результате, когда функция возвращается, компьютер выполняет этот код. Этот вид атаки легко блокируется с помощью W ^ X.[нужна цитата ] Подобные атаки могут быть успешными даже при включенной защите W ^ X, включая возврат к libc атака или нападения, исходящие от возвратно-ориентированное программирование. Были предложены различные меры по снижению рисков, такие как хранение массивов в полностью отдельном месте от стека возврата, как в случае с языком программирования Forth.[5]

Смотрите также

Рекомендации

  1. ^ «Понимание стека». cs.umd.edu. 2003-06-22. Архивировано из оригинал на 2013-02-25. Получено 2014-05-21.
  2. ^ Альтернативный дизайн микропроцессора
  3. ^ McMaster, S .; Мемон, А. (2006). «Покрытие стека вызовов для сокращения GUI Test-Suite». 17-й Международный симпозиум по проектированию надежности программного обеспечения (PDF). С. 33–44. CiteSeerX  10.1.1.88.873. Дои:10.1109 / ISSRE.2006.19. ISBN  0-7695-2684-5.
  4. ^ «Отладка с помощью GDB: изучение стека». chemie.fu-berlin.de. 1997-10-17. Получено 2014-12-16.
  5. ^ Дуг Хойт. «Четвертый язык программирования - почему ВАМ следует его изучить».

дальнейшее чтение

внешняя ссылка