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