Распределение памяти на основе стека

Стеки в вычислительных архитектурах — это области памяти , в которых данные добавляются или удаляются по принципу «последним пришел — первым обслужен» (LIFO) .

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

Стек часто используется для хранения переменных фиксированной длины, локальных для активных в данный момент функций. Программисты также могут явно использовать стек для хранения локальных данных переменной длины. Если область памяти находится в стеке потока, говорят, что эта память выделена в стеке, т. е. распределение памяти на основе стека (SBMA). Это контрастирует с распределением памяти на основе кучи (HBMA). SBMA часто тесно связан со стеком вызовов функций .

Преимущества и недостатки

Поскольку данные добавляются и удаляются в порядке очереди, распределение памяти на основе стека очень просто и обычно намного быстрее, чем распределение памяти на основе кучи (также известное как динамическое распределение памяти ), например, C. в malloc.

Другая особенность заключается в том, что память в стеке автоматически и очень эффективно освобождается при выходе из функции, что может быть удобно для программиста, если данные больше не требуются. ^[1] (То же самое относится и к longjmp , если он переместился в точку перед вызовом alloca Однако если данные необходимо сохранить в каком-то виде, то их необходимо скопировать из стека в кучу до выхода из функции. Следовательно, распределение на основе стека подходит для временных данных или данных, которые больше не требуются после выхода из текущей функции.

Назначенный потоку размер стека может достигать нескольких байт на некоторых небольших процессорах. Выделение в стеке большего количества памяти, чем доступно, может привести к сбою из-за переполнения стека . Именно поэтому функции, использующие alloca обычно запрещается встраивать: ^[2] если такая функция будет встроена в цикл, вызывающая сторона пострадает от непредвиденного роста использования стека, что сделает переполнение гораздо более вероятным.

Распределение на основе стека также может вызвать незначительные проблемы с производительностью: это приводит к кадрам стека переменного размера, поэтому как указателями стека, так и указателями кадров необходимо управлять (в случае с кадрами стека фиксированного размера указатель стека является избыточным из-за умножения кадра стека). указатель по размеру каждого кадра). Обычно это намного дешевле, чем звонить malloc и free в любом случае. В частности, если текущая функция содержит как вызовы alloca, так и блоки, содержащие локальные данные переменной длины, тогда возникает конфликт между попытками alloca увеличить текущий кадр стека до тех пор, пока текущая функция не завершится, и необходимостью компилятора поместить локальные переменные переменной длины в то же место в кадре стека. Этот конфликт обычно разрешается путем создания отдельной цепочки хранилища кучи для каждого вызова alloca. ^[3] Цепочка записывает глубину стека, на которой происходит каждое выделение, последующие вызовы alloca в любой функции обрезают эту цепочку до текущей глубины стека, чтобы в конечном итоге (но не сразу) освободить любое хранилище в этой цепочке. Вызов alloca с нулевым аргументом также можно использовать для запуска освобождения памяти без ее выделения. В результате этого конфликта между alloca и хранилищем локальных переменных использование alloca может быть не более эффективным, чем использование malloc.

Системный интерфейс

Многие Unix-подобные системы, а также Microsoft Windows реализуют функцию, называемую alloca для динамического распределения памяти стека аналогично принципу на основе кучи malloc. Компилятор обычно преобразует его во встроенные инструкции, манипулирующие указателем стека, аналогично тому, как массивы переменной длины . обрабатываются ^[4] Хотя нет необходимости явно освобождать память, существует риск неопределенного поведения из-за переполнения стека. ^[5] Эта функция присутствовала в системах Unix еще в версии 32/V (1978 г.), но не является частью стандарта C или какого-либо стандарта POSIX .

Более безопасная версия alloca называется _malloca, который выполняет выделение в куче, если размер выделения слишком велик, и сообщает об ошибках переполнения стека, существует в Microsoft Windows. Это требует использования _freea. ^[6] gnulib предоставляет эквивалентный интерфейс, хотя вместо выдачи исключения SEH при переполнении он делегирует malloc при обнаружении слишком большого размера. ^[7] Подобную функцию можно имитировать с помощью ручного учета и проверки размера, например, при использовании alloca_account в glibc. ^[8]

Некоторые семейства процессоров, например x86 , имеют специальные инструкции для управления стеком текущего выполняющегося потока. Другие семейства процессоров, включая RISC-V , PowerPC и MIPS (ABI) операционной системы , не имеют явной поддержки стека, а вместо этого полагаются на соглашение и делегируют управление стеком двоичному интерфейсу приложений .

Авто VLA

Кроме того, начиная с версии C C99 (необязательно, начиная с C11), можно автоматически создавать массив в стеке внутри функции, известной как auto VLA ( массив переменной длины ). ^[9]

void f(int arrayLength)
{
    int b[arrayLength]; // auto VLA - this array's length is set at 
                      // the time of the function invocation / stack generation.
    for (int i = 0; i < arrayLength; i++)
        b[i] = 1;
    // at the end of this function, b[] is within the stack frame, and will 
    // disappear when the function exits, so no explicit call to free() is required.
}

См. также

Ссылки

^ «Преимущества Аллока» . Библиотека GNU C.
^ "В соответствии" . Использование коллекции компиляторов GNU (GCC) .
^ «Исходный код Alloca.c [libiberty/Alloca.c] — Codebrowser» .
^ alloca(3) – Linux программиста Руководство – Библиотечные функции
^ «Почему использование alloca() не считается хорошей практикой?» . stackoverflow.com . Проверено 5 января 2016 г.
^ "_маллока" . Документация Microsoft CRT .
^ "gnulib/malloca.h" . Гитхаб . Проверено 24 ноября 2019 г.
^ "glibc/include/alloca.h" . Зеркала Берена Минора. 23 ноября 2019 г.
^ «Определение ISO C 99» (PDF) . Проверено 10 апреля 2022 г.

[1] «Преимущества Аллока» . Библиотека GNU C.

[2] "В соответствии" . Использование коллекции компиляторов GNU (GCC) .

[3] «Исходный код Alloca.c [libiberty/Alloca.c] — Codebrowser» .

[4] alloca(3) – Linux программиста Руководство – Библиотечные функции

[5] «Почему использование alloca() не считается хорошей практикой?» . stackoverflow.com . Проверено 5 января 2016 г.

[6] "_маллока" . Документация Microsoft CRT .

[7] "gnulib/malloca.h" . Гитхаб . Проверено 24 ноября 2019 г.

[8] "glibc/include/alloca.h" . Зеркала Берена Минора. 23 ноября 2019 г.

[C99-9] «Определение ISO C 99» (PDF) . Проверено 10 апреля 2022 г.

[1]

[2]

[3]

[4]

[5]

[6]

[7]

[8]

[9]