Введение
Форма выделения компьютерной памяти
Стеки в вычислительных архитектурах – это области памяти, в которых данные добавляются или удаляются по принципу "последний пришел – первый ушел" (LIFO). В большинстве современных компьютерных систем каждая нить имеет зарезервированную область памяти, называемую стеком. При выполнении функции она может добавить часть своих локальных данных в вершину стека; при завершении функции она отвечает за удаление этих данных из стека. Как минимум, стек нити используется для хранения адреса возврата, предоставленного вызывающей функцией, чтобы обеспечить возврат в правильное местоположение при выполнении операторов возврата. Стек часто используется для хранения локальных переменных фиксированной длины, относящихся к текущим активным функциям. Программисты также могут явно использовать стек для хранения локальных данных переменной длины. Если область памяти находится в стеке нити, то говорят, что эта память выделена в стеке, то есть используется выделение памяти на основе стека (SBMA). Это противопоставляется выделению памяти на основе кучи (HBMA). SBMA часто тесно связано со стеком вызовов функций.
Преимущества и недостатки
Поскольку данные добавляются и удаляются по принципу "последним пришел – первым ушел", выделение памяти на основе стека очень простое и, как правило, значительно быстрее, чем выделение памяти на основе кучи (также известное как динамическое выделение памяти), например, в языке C. Другая особенность заключается в том, что память на стеке автоматически и очень эффективно освобождается при выходе из функции, что может быть удобно для программиста, если данные больше не требуются. (То же самое справедливо и для `longjmp`, если он перешел к точке, предшествующей вызову). Однако, если данные необходимо сохранить, их следует скопировать из стека в кучу до выхода из функции. Следовательно, выделение памяти на основе стека подходит для временных данных или данных, которые больше не нужны после завершения текущей функции. Размер стека, выделенного потоку, может быть очень мал – всего несколько байт на некоторых небольших процессорах. Выделение большего объема памяти на стеке, чем доступно, может привести к аварийному завершению программы из-за переполнения стека. Именно поэтому функциям, использующим `alloca`, обычно запрещают инлайнинг: если такая функция будет встроена в цикл, вызывающая функция столкнется с непредвиденным увеличением использования стека, что значительно повысит вероятность переполнения. Выделение памяти на основе стека также может вызывать незначительные проблемы с производительностью: оно приводит к стековым фреймам переменного размера, что требует управления как указателем стека, так и указателем фрейма (при использовании стековых фреймов фиксированного размера указатель стека становится избыточным, поскольку размер каждого фрейма умножается на указатель стекового фрейма). Как правило, это обходится дешевле, чем вызовы `malloc` и `free`. В частности, если текущая функция содержит как вызовы `alloca`, так и блоки с локальными данными переменной длины, возникает конфликт между попытками `alloca` увеличить текущий стековый фрейм до выхода из функции и необходимостью компилятора размещать локальные переменные переменной длины в одном и том же месте стекового фрейма. Обычно этот конфликт разрешается путем создания отдельной цепочки хранения в куче для каждого вызова `alloca`. Эта цепочка фиксирует глубину стека, на которой происходит каждое выделение памяти, а последующие вызовы `alloca` в любой функции обрезают эту цепочку до текущей глубины стека, чтобы в конечном итоге (но не немедленно) освободить память в этой цепочке. Вызов `alloca` с аргументом, равным нулю, также можно использовать для освобождения памяти без выделения дополнительной памяти. В результате этого конфликта между `alloca` и хранением локальных переменных использование `alloca` может быть не более эффективным, чем использование `malloc`.
Another feature is that memory on the stack is automatically, and very efficiently, reclaimed when the function exits, which can be convenient for the programmer if the data is no longer required. (The same applies to longjmp if it moved to a point before the call to happened.) If, however, the data needs to be kept in some form, then it must be copied from the stack to the heap before the function exits. Therefore, stack based allocation is suitable for temporary data or data which is no longer required after the current function exits. A thread's assigned stack size can be as small as only a few bytes on some small CPUs. Allocating more memory on the stack than is available can result in a crash due to stack overflow. This is also why functions that use are usually prevented from being inlined: should such a function be inlined into a loop, the caller would suffer from an unanticipated growth in stack usage, making an overflow much more likely. Stack based allocation can also cause minor performance problems: it leads to variable size stack frames, so that both stack and frame pointers need to be managed (with fixed size stack frames, the stack pointer is redundant due to multiplying the stack frame pointer by the size of each frame). This is usually much less costly than calling and anyway. In particular, if the current function contains both calls to alloca and blocks containing variable length local data then a conflict occurs between alloca's attempts to increase the current stack frame until the current function exits versus the compiler's need to place local variables of variable length in the same location in the stack frame. This conflict is typically resolved by creating a separate chain of heap storage for each call to alloca. The chain records the stack depth at which each allocation occurs, subsequent calls to alloca in any function trim this chain down to the current stack depth to eventually (but not immediately) free any storage on this chain. A call to alloca with an argument of zero can also be used to trigger the freeing of memory without allocating any more such memory. As a consequence of this conflict between alloca and local variable storage, using alloca might be no more efficient than using malloc.
Система интерфейса
Многие Unix-подобные системы, а также Microsoft Windows реализуют функцию для динамического выделения стековой памяти аналогично malloc в куче. Компилятор обычно преобразует её во встроенные инструкции, манипулирующие указателем стека, подобно тому, как обрабатываются массивы переменной длины. Хотя освобождать память явно не требуется, существует риск неопределённого поведения из-за переполнения стека. Эта функция появилась в Unix-системах ещё в 32/V (1978), но не входит в стандарт C или любой стандарт POSIX. В Microsoft Windows существует более безопасная версия, которая выделяет память в куче, если размер запроса слишком велик, и сообщает об ошибках переполнения стека. Для её использования требуется gnulib, которая предоставляет эквивалентный интерфейс, но вместо генерации исключения SEH при переполнении делегирует управление функции, когда обнаруживается слишком большой размер. Аналогичную функциональность можно эмулировать с помощью ручного учёта и проверки размера, например, при использовании в glibc. Некоторые семейства процессоров, такие как x86, имеют специальные инструкции для работы со стеком текущего выполняемого потока. Другие семейства процессоров, включая RISC V, PowerPC и MIPS, не имеют прямой поддержки стека и вместо этого полагаются на соглашения и делегируют управление стеком приложению через интерфейс прикладных программ (ABI) операционной системы.