Стек вызовов

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

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

Описание [ править ]

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

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

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

Функции стека вызовов [ править ]

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

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

Локальное хранилище данных: Подпрограмме часто требуется пространство памяти для хранения значений локальных переменных , переменных, которые известны только внутри активной подпрограммы и не сохраняют значения после ее возврата. Часто бывает удобно выделить место для этого использования, просто переместив верхнюю часть стека на достаточное расстояние, чтобы освободить место. Это очень быстро по сравнению с динамическим распределением памяти , которое использует пространство кучи . Обратите внимание, что каждая отдельная активация подпрограммы получает свое отдельное место в стеке для локальных переменных.
Передача параметров: Подпрограммы часто требуют, чтобы значения параметров передавались им кодом, который их вызывает, и нередко место для этих параметров может быть выделено в стеке вызовов. Обычно, если имеется всего несколько небольших параметров, для передачи значений будут использоваться регистры процессора , но если параметров больше, чем можно обработать таким образом, потребуется пространство памяти. Стек вызовов хорошо подходит в качестве места для этих параметров, особенно потому, что каждому вызову подпрограммы, которая будет иметь разные значения параметров, будет выделено отдельное место в стеке вызовов для этих значений. В объектно-ориентированных языках , таких как C++ , список параметров может также включать this указатель .
Стек оценок: Операнды для арифметических или логических операций чаще всего помещаются в регистры и выполняются там. Однако в некоторых ситуациях операнды могут быть уложены на произвольную глубину, что означает, что необходимо использовать нечто большее, чем просто регистры (это случай разгрузки регистров ). Стек таких операндов, примерно как в RPN-калькуляторе , называется стеком вычислений и может занимать место в стеке вызовов.
Включающий контекст подпрограммы: Некоторые языки программирования (например, Pascal и Ada ) поддерживают объявление вложенных подпрограмм , которым разрешен доступ к контексту охватывающих их подпрограмм, т. е. к параметрам и локальным переменным в пределах области действия внешних подпрограмм. Такая статическая вложенность может повторяться (функция, объявленная внутри функции, объявленной внутри функции…). Реализация должна предоставлять средства, с помощью которых вызываемая функция на любом заданном статическом уровне вложенности может ссылаться на включающий фрейм на каждом включающем уровне вложенности. Эта ссылка обычно реализуется указателем на кадр последнего активированного экземпляра включающей функции, называемого «ссылка на нисходящий стек» или «статическая ссылка», чтобы отличить ее от «динамической ссылки», которая ссылается на непосредственного вызывающего объекта ( которая не обязательно должна быть статической родительской функцией).; Вместо статической ссылки ссылки на включающие статические кадры могут быть собраны в массив указателей, известный как дисплей , который индексируется для поиска нужного кадра. Глубина лексической вложенности подпрограммы является известной константой, поэтому размер отображения подпрограммы фиксирован. Кроме того, известно количество содержащихся областей, которые необходимо пройти, индекс на дисплее также фиксирован. Обычно отображение подпрограммы располагается в отдельном фрейме стека, но в Burroughs B6500 такое отображение реализовано аппаратно, поддерживая до 32 уровней статической вложенности.; Записи отображения, обозначающие содержащие области, получаются из соответствующего префикса отображения вызывающего объекта. Внутренняя рекурсивная процедура создает отдельные кадры вызова для каждого вызова. В этом случае все статические ссылки внутренней подпрограммы указывают на один и тот же контекст внешней подпрограммы.
Контекст закрытого блока: В некоторых языках, например, ALGOL 60 , PL/I , блок внутри процедуры может иметь свои собственные локальные переменные, выделяемые при входе в блок и освобождаемые при выходе из блока. Аналогично, блок может иметь свои собственные обработчики исключений, деактивируемые при выходе из блока.
Другое состояние возврата: Помимо обратного адреса, в некоторых средах могут существовать другие состояния машины или программного обеспечения, которые необходимо восстановить при возвращении из подпрограммы. Сюда могут входить такие вещи, как уровень привилегий, информация об обработке исключений, арифметические режимы и т. д. При необходимости его можно сохранить в стеке вызовов так же, как адрес возврата.

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

Структура [ править ]

Стек вызовов состоит из кадров стека (также называемых записями активации или кадрами активации ). Это машинно-зависимые и 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, включая атаку return-to-libc или атаки, исходящие из возвратно-ориентированного программирования . Были предложены различные способы смягчения последствий, такие как хранение массивов в совершенно отдельном месте от стека возврата, как в случае с языком программирования Форт. ^[6]

См. также [ править ]

Ссылки [ править ]

^ Кшижановский, Павел (16 февраля 2018 г.). «Стек кадров» . Университет Рутгерса . Архивировано из оригинала 28 августа 2021 г. Проверено 19 декабря 2021 г.
^ «Понимание стека» . cs.umd.edu . 22 июня 2003 г. Архивировано из оригинала 25 февраля 2013 г. Проверено 21 мая 2014 г.
^ Альтернативная конструкция микропроцессора
^ Макмастер, С.; Мемон, А. (2006). Покрытие стека вызовов для сокращения набора тестов графического пользовательского интерфейса (PDF) . 17-й Международный симпозиум по проектированию надежности программного обеспечения ( ISSRE '06). стр. 33–44. CiteSeerX 10.1.1.88.873 . дои : 10.1109/ISSRE.2006.19 . ISBN 0-7695-2684-5 .
^ «Отладка с помощью GDB: исследование стека» . chemie.fu-berlin.de . 17 октября 1997 г. Архивировано из оригинала 14 апреля 2021 г. Проверено 16 декабря 2014 г.
^ Дуг Хойт. «Четвертый язык программирования – почему ВАМ следует его изучать» .

Дальнейшее чтение [ править ]

Дейкстра, EW (1960). «Рекурсивное программирование». Численная математика . 2 (1): 312–318. дои : 10.1007/BF01386232 .
Уилсон, PR; Джонстон, штат Массачусетс; Нили, М.; Болес, Д. (1995). «Динамическое распределение памяти: обзор и критический обзор». Управление памятью . Конспекты лекций по информатике. Том. 986. стр. 1–116. CiteSeerX 10.1.1.47.275 . дои : 10.1007/3-540-60368-9_19 . ISBN 978-3-540-60368-9 .
«2.4. Стек». Руководство по программированию на языке ассемблера MCS-4 — Руководство по программированию микрокомпьютерной системы INTELLEC 4 (PDF) (предварительное издание). Санта-Клара, Калифорния, США: Корпорация Intel . Декабрь 1973 г. стр. 2-7–2-8. MCS-030-1273-1. Архивировано (PDF) из оригинала 1 марта 2020 г. Проверено 02 марта 2020 г. (Примечание. 4004 4-битный процессор Intel реализует внутренний стек, а не стек в памяти.)

Внешние ссылки [ править ]

Вызов функций и операции с указателем кадра в 68000. Архивировано 24 июля 2010 г. на Wayback Machine.
Проект libunwind — независимый от платформы API раскрутки.

[1] Кшижановский, Павел (16 февраля 2018 г.). «Стек кадров» . Университет Рутгерса . Архивировано из оригинала 28 августа 2021 г. Проверено 19 декабря 2021 г.

[2] «Понимание стека» . cs.umd.edu . 22 июня 2003 г. Архивировано из оригинала 25 февраля 2013 г. Проверено 21 мая 2014 г.

[3] Альтернативная конструкция микропроцессора

[4] Макмастер, С.; Мемон, А. (2006). Покрытие стека вызовов для сокращения набора тестов графического пользовательского интерфейса (PDF) . 17-й Международный симпозиум по проектированию надежности программного обеспечения ( ISSRE '06). стр. 33–44. CiteSeerX 10.1.1.88.873 . дои : 10.1109/ISSRE.2006.19 . ISBN 0-7695-2684-5 .

[5] «Отладка с помощью GDB: исследование стека» . chemie.fu-berlin.de . 17 октября 1997 г. Архивировано из оригинала 14 апреля 2021 г. Проверено 16 декабря 2014 г.

[6] Дуг Хойт. «Четвертый язык программирования – почему ВАМ следует его изучать» .

[1]

[2]

[3]

[4]

[5]

[6]