В информатике стек вызовов представляет собой структуру данных стека , в которой хранится информация об активных подпрограммах компьютерной программы . Этот тип стека также известен как стек выполнения , стек программы , стек управления , стек времени выполнения или машинный стек , и его часто сокращают до простого « стека ». Хотя обслуживание стека вызовов важно для правильного функционирования большинства программ , в языках программирования высокого уровня детали обычно скрыты и выполняются автоматически . Многие наборы компьютерных команд содержат специальные инструкции для управления стеками.
Стек вызовов используется для нескольких взаимосвязанных целей, но основная причина его использования — отслеживание точки, в которую каждая активная подпрограмма должна вернуть управление после завершения выполнения. Активная подпрограмма — это та, которая была вызвана, но еще не завершила выполнение, после чего управление должно быть передано обратно в точку вызова. Такие активации подпрограмм могут быть вложены на любой уровень (в частном случае рекурсивно), отсюда и структура стека. Например, если подпрограмма DrawSquareвызывает подпрограмму DrawLineиз четырех разных мест, DrawLineнеобходимо знать, куда вернуться после завершения ее выполнения. Для этого адрес , следующий за инструкцией перехода к DrawLine, адрес возврата , помещается на вершину стека вызовов при каждом вызове.
Поскольку стек вызовов организован в виде стека , вызывающая программа помещает адрес возврата в стек, а вызываемая подпрограмма, когда она завершает работу, извлекает или извлекает адрес возврата из стека вызовов и передает управление этому адресу. Если вызываемая подпрограмма вызывает еще одну подпрограмму, она помещает другой адрес возврата в стек вызовов и так далее, при этом информация накапливается и разбирается в соответствии с указаниями программы. Если передача занимает все пространство, выделенное для стека вызовов, возникает ошибка, называемая переполнением стека , которая обычно приводит к сбою программы . Добавление записи блока или подпрограммы в стек вызовов иногда называют «обмоткой», а удаление записей — «очисткой».
Обычно с работающей программой (или, точнее, с каждой задачей или потоком процесса ) связан ровно один стек вызовов , хотя могут быть созданы дополнительные стеки для обработки сигналов или совместной многозадачности (как в случае с setcontext ). Поскольку в этом важном контексте он только один, его можно назвать стеком (неявно «задачи»); однако в языке программирования Форт доступ к стеку данных или стеку параметров осуществляется более явно, чем к стеку вызовов, и его обычно называют стеком (см. ниже).
В языках программирования высокого уровня специфика стека вызовов обычно скрыта от программиста. Им предоставляется доступ только к набору функций, а не к памяти самого стека. Это пример абстракции . С другой стороны, большинство языков ассемблера требуют участия программистов в управлении стеком. Фактические детали стека в языке программирования зависят от компилятора , операционной системы и доступного набора команд .
Как отмечалось выше, основная цель стека вызовов — хранить адреса возврата . При вызове подпрограммы местоположение (адрес) инструкции, с которой вызывающая подпрограмма может позже возобновиться, должно быть где-то сохранено. Использование стека для сохранения адреса возврата имеет важные преимущества по сравнению с некоторыми альтернативными соглашениями о вызовах , такими как сохранение адреса возврата перед началом вызываемой подпрограммы или в каком-либо другом фиксированном месте. Во-первых, каждая задача может иметь свой собственный стек, и, таким образом, подпрограмма может быть потокобезопасной , то есть быть активной одновременно для разных задач, выполняющих разные действия. Еще одним преимуществом является то, что благодаря обеспечению повторного входа рекурсия автоматически поддерживается. Когда функция вызывает себя рекурсивно, адрес возврата необходимо сохранять для каждой активации функции, чтобы его позже можно было использовать для возврата из активации функции. Структуры стека обеспечивают эту возможность автоматически.
В зависимости от языка, операционной системы и машинной среды стек вызовов может служить дополнительным целям, включая, например:
thisуказатель .Типичный стек вызовов используется для адреса возврата, локальных переменных и параметров (известный как кадр вызова ). В некоторых средах стеку вызовов может быть назначено больше или меньше функций. В языке программирования Форт , например, обычно в стеке вызовов (который в этой среде называется стеком возврата ) хранятся только адрес возврата, подсчитанные параметры и индексы цикла и, возможно, локальные переменные, хотя любые данные могут быть временно помещены там используется специальный код обработки стека возвратов, если соблюдаются потребности вызовов и возвратов; параметры обычно хранятся в отдельном стеке данных или стеке параметров , обычно называемом стеком в терминологии Форта, даже несмотря на то, что существует стек вызовов, поскольку к нему обычно обращаются более явно. Некоторые Форты также имеют третий стек для параметров с плавающей запятой .
DrawSquareподпрограммы (показана синим цветом ) DrawLine(показана зеленым ), которая является выполняемой в данный момент подпрограммой.Стек вызовов состоит из кадров стека (также называемых записями активации или кадрами активации ). Это машинно-зависимые и ABI -зависимые структуры данных, содержащие информацию о состоянии подпрограммы. Каждый кадр стека соответствует вызову подпрограммы, которая еще не завершилась возвратом. Например, если подпрограмма с указанным именем DrawLineв настоящий момент выполняется и была вызвана подпрограммой DrawSquare, верхняя часть стека вызовов может располагаться, как на соседнем рисунке.
Подобную диаграмму можно нарисовать в любом направлении, если понятно расположение вершины и, следовательно, направление роста стека. Архитектуры различаются в зависимости от того, растут ли стеки вызовов в сторону более высоких или меньших адресов, поэтому логика любой диаграммы по соглашению не зависит от этого выбора адресации.
Кадр стека в верхней части стека предназначен для выполняющейся в данный момент процедуры, которая может получать доступ к информации внутри своего кадра (например, к параметрам или локальным переменным) в любом порядке. [1] Кадр стека обычно включает в себя как минимум следующие элементы (в порядке отправки):
DrawLineкадре стека, адрес в DrawSquareкоде); иКогда размеры кадров стека могут различаться, например, между разными функциями или между вызовами определенной функции, удаление кадра из стека не представляет собой фиксированное уменьшение указателя стека . При возврате функции указатель стека вместо этого восстанавливается до указателя кадра , значения указателя стека непосредственно перед вызовом функции. Каждый кадр стека содержит указатель стека на верхнюю часть кадра, расположенного непосредственно под ним. Указатель стека — это изменяемый регистр, общий для всех вызовов. Указатель кадра данного вызова функции является копией указателя стека, каким он был до вызова функции. [2]
Местоположение всех остальных полей в кадре может быть определено либо относительно верхней части кадра (как отрицательное смещение указателя стека), либо относительно верхней части нижнего кадра (как положительное смещение указателя кадра). Местоположение самого указателя кадра должно по своей сути определяться как отрицательное смещение указателя стека.
В большинстве систем кадр стека имеет поле, содержащее предыдущее значение регистра указателя кадра, значение, которое оно имело во время выполнения вызывающей стороны. Например, кадр стека DrawLineбудет иметь ячейку памяти, содержащую значение указателя кадра, которое DrawSquareиспользует (не показано на диаграмме выше). Значение сохраняется при входе в подпрограмму. Наличие такого поля в известном месте в кадре стека позволяет коду получать доступ к каждому кадру последовательно под кадром выполняемой в данный момент подпрограммы, а также позволяет подпрограмме легко восстанавливать указатель кадра на кадр вызывающего объекта непосредственно перед его возвратом.
Языки программирования, поддерживающие вложенные подпрограммы, также имеют поле в кадре вызова, которое указывает на кадр стека последней активации процедуры, которая наиболее точно инкапсулирует вызываемого объекта, т. е. непосредственную область действия вызываемого объекта. Это называется ссылкой доступа или статической ссылкой (поскольку она отслеживает статическую вложенность во время динамических и рекурсивных вызовов) и обеспечивает подпрограмме (а также любым другим подпрограммам, которые она может вызывать) доступ к локальным данным ее инкапсулирующих подпрограмм при каждом вложении. уровень. В некоторых архитектурах, компиляторах или случаях оптимизации сохраняется одна ссылка для каждого включающего уровня (а не только непосредственно включающего), так что глубоко вложенным процедурам, обращающимся к поверхностным данным, не нужно проходить несколько ссылок; эту стратегию часто называют «показом». [3]
Ссылки доступа можно оптимизировать, когда внутренняя функция не обращается к каким-либо (непостоянным) локальным данным в инкапсуляции, как, например, в случае с чистыми функциями, взаимодействующими только через аргументы и возвращаемые значения. Некоторые исторические компьютеры, такие как Electrologica X8 и несколько позже большие системы Burroughs , имели специальные «регистры дисплея» для поддержки вложенных функций, в то время как компиляторы для большинства современных машин (таких как вездесущая x86) просто резервируют несколько слов в стеке для указатели по мере необходимости.
В некоторых целях кадры стека подпрограммы и кадра ее вызывающей программы можно рассматривать как перекрывающиеся, причем перекрытие состоит из области, в которой параметры передаются от вызывающей программы к вызываемой. В некоторых средах вызывающая сторона помещает каждый аргумент в стек, расширяя таким образом кадр стека, а затем вызывает вызываемую сторону. В других средах вызывающая программа имеет предварительно выделенную область в верхней части кадра стека для хранения аргументов, которые она передает другим подпрограммам, которые она вызывает. Эту область иногда называют областью исходящих аргументов или областью выноски . При таком подходе размер области рассчитывается компилятором как самый большой, необходимый для любой вызываемой подпрограммы.
Обычно манипуляции со стеком вызовов, необходимые в месте вызова подпрограммы, минимальны (и это хорошо, поскольку для каждой вызываемой подпрограммы может быть много мест вызова). Значения фактических аргументов оцениваются на месте вызова, поскольку они специфичны для конкретного вызова, и либо помещаются в стек, либо помещаются в регистры, как это определено используемым соглашением о вызовах . Фактическая инструкция вызова, такая как «ветвь и ссылка», затем обычно выполняется для передачи управления коду целевой подпрограммы.
В вызываемой подпрограмме первый выполняемый код обычно называется прологом подпрограммы , поскольку он выполняет необходимую служебную работу перед тем, как начинается код операторов подпрограммы.
Для архитектур набора команд, в которых инструкция, используемая для вызова подпрограммы, помещает адрес возврата в регистр, а не помещает его в стек, пролог обычно сохраняет адрес возврата, помещая значение в стек вызовов, хотя если вызываемый подпрограмма не вызывает никаких других процедур, она может оставить значение в регистре. Аналогично, текущие значения указателя стека и/или указателя кадра могут быть перенесены.
Если используются указатели кадров, пролог обычно устанавливает новое значение регистра указателя кадра из указателя стека. Затем пространство в стеке для локальных переменных можно выделить путем постепенного изменения указателя стека.
Язык программирования Форт допускает явную обмотку стека вызовов (называемого там «стеком возврата»).
Когда подпрограмма готова вернуться, она выполняет эпилог, который отменяет шаги пролога. Обычно это восстанавливает сохраненные значения регистров (например, значение указателя кадра) из кадра стека, извлекает весь кадр стека из стека путем изменения значения указателя стека и, наконец, переходит к инструкции по адресу возврата. Согласно многим соглашениям о вызовах, элементы, извлекаемые из стека эпилогом, включают в себя исходные значения аргументов, и в этом случае обычно вызывающей стороне не требуется никаких дополнительных манипуляций со стеком. Однако в соответствии с некоторыми соглашениями о вызовах ответственность за удаление аргументов из стека после возврата лежит на вызывающей стороне.
Возврат из вызванной функции приведет к удалению верхнего кадра из стека, возможно, оставив возвращаемое значение. Более общее действие по извлечению одного или нескольких кадров из стека для возобновления выполнения в другом месте программы называется раскручиванием стека и должно выполняться, когда используются нелокальные структуры управления, например те, которые используются для обработки исключений . В этом случае кадр стека функции содержит одну или несколько записей, определяющих обработчики исключений. При возникновении исключения стек разворачивается до тех пор, пока не будет найден обработчик, готовый обработать (перехватить) тип выброшенного исключения.
В некоторых языках есть другие структуры управления, которые требуют общей раскрутки. Паскаль позволяет глобальному оператору перехода передавать управление из вложенной функции в ранее вызванную внешнюю функцию. Эта операция требует, чтобы стек был развернут, удалив столько кадров стека, сколько необходимо, чтобы восстановить правильный контекст для передачи управления целевому оператору внутри включающей внешней функции. Точно так же в C есть функции setjmpиlongjmp , которые действуют как нелокальные переходы. Common Lisp позволяет управлять тем, что происходит при раскручивании стека, с помощью unwind-protectспециального оператора.
При применении продолжения стек (логически) разматывается, а затем перематывается со стеком продолжения. Это не единственный способ реализации продолжений; например, используя несколько явных стеков, применение продолжения может просто активировать его стек и завершить передаваемое значение. Язык программирования Scheme позволяет выполнять произвольные переходы в определенных точках при «размотке» или «перемотке» стека управления при вызове продолжения.
Стек вызовов иногда можно проверить во время работы программы. В зависимости от того, как написана и скомпилирована программа, информация в стеке может использоваться для определения промежуточных значений и трассировок вызовов функций. Это использовалось для создания детальных автоматических тестов [4] и в таких случаях, как Ruby и Smalltalk, для реализации первоклассных продолжений. Например, отладчик GNU (GDB) реализует интерактивную проверку стека вызовов работающей, но приостановленной программы C. [5]
Регулярное получение выборок стека вызовов может быть полезно при профилировании производительности программ, поскольку, если указатель подпрограммы появляется в данных выборки стека вызовов много раз, он, вероятно, будет действовать как узкое место в коде и должен быть проверен на предмет проблем с производительностью. .
В языке со свободными указателями или записью в непроверяемый массив (например, в C) смешивание данных потока управления, которые влияют на выполнение кода (адреса возврата или указатели сохраненных кадров), и простых данных программы (параметров или возвращаемых значений). ) в стеке вызовов представляет собой угрозу безопасности и, возможно, может быть использована через переполнение буфера стека , которое является наиболее распространенным типом переполнения буфера .
Одна из таких атак включает в себя заполнение одного буфера произвольным исполняемым кодом, а затем переполнение этого или какого-либо другого буфера для перезаписи некоторого адреса возврата значением, которое указывает непосредственно на исполняемый код. В результате, когда функция возвращает значение, компьютер выполняет этот код. Этот вид атаки можно заблокировать с помощью W^X , [ необходима цитация ] , но подобные атаки могут быть успешными даже при включенной защите W^X, включая атаку возврата в libc или атаки, исходящие из возвратно-ориентированного программирования . Были предложены различные способы смягчения последствий, такие как хранение массивов в совершенно отдельном месте от стека возврата, как в случае с языком программирования Форт. [6]
