Как работают сегментированные стеки

Я дам вам краткий набросок одной возможной реализации.

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

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

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

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

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

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

Go на самом деле не использует страницу защиты, если я правильно понимаю. Скорее пролог функции явно проверяет ограничение стека и, если новый кадр стека не помещается, вызывает функцию для расширения стека.

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

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

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

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