Как устроен stack?

Как устроен stack

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

Базовые принципы

Stack работает по принципу LIFO (Last In First Out) — последний добавленный элемент удаляется первым. Это как стопка тарелок: кладёшь сверху, берёшь сверху.

Структура памяти

В типичной системе память делится на несколько областей:

Высокие адреса     ┌──────────────────┐
                   │      STACK       │ ← растёт вниз
                   │   (растёт вниз)  │
                   ├──────────────────┤
                   │    Свободная     │
                   │      память      │
                   ├──────────────────┤
                   │      HEAP        │ ← растёт вверх
                   │   (растёт вверх) │
                   ├──────────────────┤
                   │   Данные (BSS)   │
                   ├──────────────────┤
                   │  Инициализ. дан. │
Низкие адреса      │      КОД         │
                   └──────────────────┘

Как работает stack

Указатель стека (Stack Pointer - SP/RSP) отслеживает вершину стека. При добавлении элемента (PUSH) SP уменьшается (на архитектурах x86/x64), при удалении (POP) увеличивается.

int foo(int x, int y) {
    int a = 10;    // Добавляется на стек
    int b = 20;    // Добавляется на стек
    return a + b;  // Оба удаляются
}

int main() {
    int result = foo(5, 15);  // Параметры передаются через стек
    return 0;
}

Вызов функции (Call Stack)

Когда функция вызывается, происходит следующее:

1. Сохранение адреса возврата — куда вернуться после завершения
2. Сохранение старого base pointer (EBP/RBP)
3. Выделение места под локальные переменные
4. Исполнение кода функции
5. Восстановление стека
6. Возврат на адрес возврата

// Ассемблер (x86-64 примерно)
void example(int x) {     // x передано в RDI
    push rbp              // Сохранили старый base pointer
    mov rbp, rsp          // Новый base pointer = текущий stack pointer
    sub rsp, 16           // Выделили место под локальные переменные
    
    int y = x + 1;        // Используем стек
    
    add rsp, 16           // Очистили локальные переменные
    pop rbp               // Восстановили старый base pointer
    ret                   // Вернулись
}

Call Stack в многоуровневых вызовах

void funcC() {}
void funcB() { funcC(); }
void funcA() { funcB(); }
void main() { funcA(); }

Вызовов: main → funcA → funcB → funcC

После вызова funcC():     После возврата:
┌──────────────────┐     ┌──────────────────┐
│  funcC frame     │     │  funcB frame     │
├──────────────────┤     ├──────────────────┤
│  funcB frame     │  →  │  funcA frame     │
├──────────────────┤     ├──────────────────┤
│  funcA frame     │     │  main frame      │
├──────────────────┤     └──────────────────┘
│  main frame      │
└──────────────────┘

Размер stack

Все операционные системы выделяют для стека ограниченный размер (по умолчанию):

• Linux/Unix: обычно 8 MB
• Windows: обычно 1 MB
• Может быть увеличен при запуске программы

// Проверка оставшегося места на стеке
char buffer[1000000];  // Stack overflow!
std::vector<int> v;     // В heap — безопаснее

Преимущества stack

• Очень быстро — просто два операции (PUSH/POP, инструкции процессора)
• Автоматическое управление — переменные удаляются при выходе из scope
• Cache-friendly — высокая локальность данных
• Не требует фрагментации — линейное выделение

Проблемы stack

Stack Overflow:

void recursive() {
    int array[10000];      // Много места
    recursive();            // Бесконечная рекурсия
}                           // Stack Overflow!

Слишком большие переменные:

std::vector<int> good;       // OK, в heap
int bad[1000000];            // Stack overflow!

Возврат указателя на локальную переменную:

int* dangerous() {
    int x = 42;
    return &x;              // Undefined Behavior!
}                           // x удалена, указатель на мусор

Стек в многопоточности

Каждый поток имеет свой собственный стек:

std::thread t([]() {
    int local = 42;         // На стеке этого потока
});
t.join();
// Локальные переменные потока удалены

Пример работы

int add(int a, int b) {
    // На стеке: a, b, адрес возврата
    return a + b;
}

int main() {
    int x = 5;
    int y = 3;
    int result = add(x, y);
    return 0;
}

// Последовательность стека:
// 1. main: выделена память под x, y, result
// 2. Вызов add: параметры a, b и адрес возврата на стеке
// 3. Возврат: frame функции удалён
// 4. main продолжает работу

Вывод

Stack — это быстрая и эффективная область памяти для хранения локальных данных. Понимание того, как он работает, критично для написания эффективного C/C++ кода, избежания stack overflow и предотвращения undefined behavior при работе с указателями.