Dokumentacja C z przykładami: Stos a sterta

Każda zmienna w programie C gdzieś mieszka, a to gdzie decyduje o dwóch rzeczach, których potem nie zmienisz: jak długo przetrwa i ile jej możesz mieć. C daje trzy obszary pamięci, a zły wybór kończy się albo awarią, albo wyciekiem. Ta strona je opisuje i pokazuje klasyczny błąd, który bierze się z pomylenia czasu życia.

Trzy obszary

  wysokie adresy
  +---------------------------+
  |  stos                     |  zmienne lokalne, parametry, adresy powrotu
  |    rosnie w dol    |      |  zwalniane same przy powrocie
  |                    v      |
  +---------------------------+
  |      (nieuzywana luka)    |
  +---------------------------+
  |                    ^      |
  |    rosnie w gore   |      |
  |  sterta                   |  bloki z malloc / calloc / realloc
  +---------------------------+  zwalniane tylko przez free()
  |  dane statyczne/globalne  |  zmienne globalne i static, caly przebieg
  +---------------------------+
  |  kod (text)               |  kod maszynowy, tylko do odczytu
  +---------------------------+
  niskie adresy

Pamięć automatyczna (stos) przechowuje parametry funkcji i niestatyczne zmienne lokalne. Fragment stosu jest zajmowany przy wejściu do funkcji i zwalniany przy powrocie. Rozmiar jest ustalony w czasie kompilacji.
Pamięć dynamiczna (sterta) przechowuje wszystko z malloc, calloc i realloc. Rozmiar ustala się w czasie działania, a czas życia kończy się dopiero przy free.
Pamięć statyczna przechowuje zmienne globalne i wszystko, co zadeklarowano jako static. Istnieje przez cały czas działania programu i jest inicjalizowana zerami przed startem main.

Adresy na schemacie to typowy układ, a nie gwarancja: standard opisuje czasy życia, a nie rozmieszczenie w pamięci.

Pamięć automatyczna w praktyce

#include <stdio.h>

void demo(void) {
    int local = 42;             /* tworzona tutaj */
    int table[4] = {1, 2, 3, 4};

    printf("local = %d, table[0] = %d\n", local, table[0]);
}                               /* obie zwalniane tutaj */

int main(void) {
    demo();
    demo();
    return 0;
}

Każde wywołanie demo dostaje świeże local i świeże table. Nic nie jest zwalniane ręcznie, nic nie może wyciec, a alokacja kosztuje jedną instrukcję przesuwającą wskaźnik stosu. Dlatego zwykłe zmienne lokalne powinny być twoim domyślnym wyborem: to najszybsza i najbezpieczniejsza pamięć, jaką ma C.

Haczykiem jest nawias zamykający. Gdy zostanie wykonany, ta pamięć znika.

Wiszący wskaźnik

Oto błąd, który każdy programista C popełnia raz:

/* ZEPSUTE: zwraca adres pamieci, ktora juz nie istnieje */
int *make_counter(void) {
    int count = 0;
    return &count;          /* count umiera na tym nawiasie */
}

int main(void) {
    int *p = make_counter();
    *p = 5;                 /* zapis do martwej ramki stosu */
    return 0;
}

&count było całkowicie poprawnym adresem, dopóki działało make_counter. Po powrocie ta przestrzeń stosu trafia do kolejnej wywołanej funkcji, więc p wskazuje teraz na cudze zmienne lokalne. Odczyt daje śmieci, a zapis je psuje. GCC i Clang ostrzegają dokładnie przed tym kształtem kodu (-Wreturn-local-addr), więc kompiluj z włączonymi ostrzeżeniami.

Ten sam błąd przebiera się przy tablicach, a wtedy ostrzeżenie często się nie pojawia:

#include <stdio.h>
#include <string.h>

/* Poprawnie: pamiec dostarcza wywolujacy, wiec przetrwa wywolanie. */
void make_greeting(char *out, size_t size, const char *name) {
    snprintf(out, size, "Czesc, %s!", name);
}

int main(void) {
    char message[64];
    make_greeting(message, sizeof message, "Ada");
    printf("%s\n", message);
    return 0;
}

Zepsuta wersja tej funkcji budowałaby tekst w lokalnym char buf[64] i robiła return buf;, zwracając adres bufora, który w tej samej chwili przestaje istnieć.

Trzy sposoby naprawy

1. Bufor dostarcza wywołujący (pokazane wyżej). Bez alokacji, bez pytania o własność, i to najczęstszy styl w bibliotekach C. Funkcja przyjmuje rozmiar, żeby się w nim zmieścić.

2. Zwróć pamięć ze sterty i powiedz, kto ją zwalnia.

#include <stdio.h>
#include <stdlib.h>
#include <string.h>

/* Zwraca nowo zaalokowany napis; wywolujacy musi go zwolnic. */
char *make_greeting(const char *name) {
    size_t size = strlen(name) + 16;
    char *out = malloc(size);
    if (out == NULL) {
        return NULL;
    }
    snprintf(out, size, "Czesc, %s!", name);
    return out;
}

int main(void) {
    char *message = make_greeting("Ada");
    if (message == NULL) {
        return 1;
    }
    printf("%s\n", message);
    free(message);
    return 0;
}

Blok na stercie z założenia przeżywa funkcję i właśnie o to chodzi w pamięci dynamicznej. Ceną jest komentarz o własności i free po stronie wywołującego.

3. Użyj pamięci statycznej, gdy jeden wspólny bufor jest do przyjęcia:

#include <stdio.h>

int *next_id(void) {
    static int id = 0;      /* jedna instancja, zyje przez caly program */
    id++;
    return &id;             /* bezpieczne: pamiec statyczna nigdy nie znika */
}

int main(void) {
    printf("%d\n", *next_id());
    printf("%d\n", *next_id());
    printf("%d\n", *next_id());
    return 0;
}

static wewnątrz funkcji zostawia zasięg zmiennej lokalny, ale daje jej czas życia całego programu, więc zwracanie jej adresu jest dozwolone. Ceną jest to, że istnieje zawsze tylko jedna: wszyscy wywołujący ją współdzielą, co wyklucza ten wzorzec w kodzie wielowątkowym i bywa zaskakujące nawet w jednowątkowym, gdy dwa miejsca trzymają wskaźnik jednocześnie.

Rozmiar: gdzie kończy się stos

Miejsce na stosie jest małe i stałe. Główny wątek dostaje zwykle 1 MB na Windows i 8 MB na Linuksie, a uruchomiony wątek często dużo mniej. Sterta jest ograniczona dostępną pamięcią systemu.

void bad(void) {
    int huge[1000000];      /* ~4 MB stosu: prawdopodobnie wysypie sie przy wejsciu */
    huge[0] = 1;
}

Nie ma żadnej diagnostyki ani NULL do sprawdzenia: program po prostu umiera, zwykle z segmentation fault, zanim wykona się pierwsza linia ciała funkcji. Wersja ze stertą poprawnie zgłasza porażkę:

#include <stdio.h>
#include <stdlib.h>

int main(void) {
    size_t n = 1000000;

    int *huge = malloc(n * sizeof *huge);
    if (huge == NULL) {
        fprintf(stderr, "nie udalo sie zaalokowac %zu liczb int\n", n);
        return 1;
    }

    huge[0] = 1;
    huge[n - 1] = 2;
    printf("%d ... %d (%zu bytes)\n", huge[0], huge[n - 1], n * sizeof *huge);

    free(huge);
    return 0;
}

Głęboka rekurencja wyczerpuje stos w ten sam sposób, ramka po ramce. W praktyce niekontrolowana funkcja rekurencyjna to najczęstsza przyczyna przepełnienia stosu.

Koszt i lokalność

Alokacja na stosie to jedna operacja arytmetyczna na rejestrze. Alokacja na stercie to wywołanie biblioteki, które szuka odpowiedniego bloku, może założyć blokadę i czasem prosi system operacyjny o więcej pamięci. W gorącej pętli ta różnica jest mierzalna.

Dane na stosie są też zwarte i niedawno używane, więc zwykle są w pamięci podręcznej. Bloki na stercie mogą być porozrzucane. Żaden z tych faktów nie powinien sam decydować o projekcie, bo najpierw liczy się poprawny czas życia, ale z dwóch projektów, które oba są poprawne, ten oparty na stosie jest zwykle szybszy.

Podgląd obszarów

Wypisanie adresów sprawia, że układ staje się namacalny. Dokładne wartości różnią się przy każdym uruchomieniu (nowoczesne systemy je losują), ale grupowanie jest widoczne:

#include <stdio.h>
#include <stdlib.h>

int global_value = 1;

int main(void) {
    static int static_value = 2;
    int local_value = 3;

    int *heap_value = malloc(sizeof *heap_value);
    if (heap_value == NULL) {
        return 1;
    }
    *heap_value = 4;

    printf("globalna:  %p\n", (void *)&global_value);
    printf("statyczna: %p\n", (void *)&static_value);
    printf("sterta:    %p\n", (void *)heap_value);
    printf("lokalna:   %p\n", (void *)&local_value);

    free(heap_value);
    return 0;
}

Zmienna globalna i statyczna leżą obok siebie, blok na stercie jest gdzie indziej, a zmienna lokalna jest zwykle daleko od obu. Dla %p rzutuj na void *, bo tego wymaga ten specyfikator formatu.

Wybór

Używaj stosu, gdy:

rozmiar jest znany w czasie kompilacji,
dane są potrzebne tylko w tej funkcji i w tych, które ona wywołuje,
i są małe: kilka kilobajtów, a nie megabajty.

Używaj sterty, gdy:

rozmiar zależy od wejścia, pliku lub obliczeń,
dane muszą przeżyć funkcję, która je utworzyła,
albo są na tyle duże, że zagrażają limitowi stosu.

Używaj pamięci statycznej, gdy:

przez cały program powinna istnieć dokładnie jedna instancja,
a współdzielenie jej przez wszystkich wywołujących jest naprawdę poprawne.

Domyślnie wybieraj stos. Po stertę sięgaj, gdy zachodzi jeden z jej trzech powodów, a wtedy stosuj zasady własności opisane na stronie o wyciekach pamięci, żeby blok, któremu dajesz dłuższe życie, nadal został zwolniony.

Dwa lustrzane błędy

Warto nazwać je razem, bo to to samo pytanie o czas życia, na które odpowiedziano na dwa sposoby:

Wiszący wskaźnik: pamięć umarła przed wskaźnikiem. Zwrócenie &local albo użycie wskaźnika po free. Program czyta lub zapisuje pamięć, która należy już do czegoś innego.
Wyciek pamięci: wskaźnik umarł przed pamięcią. Utrata ostatniej referencji do bloku z malloc. Nic nie psuje się od razu, proces po prostu rośnie.

Oba wynikają z niedopasowania tego, jak długo dane muszą żyć, do obszaru, w którym je umieszczono. Najpierw ustal czas życia, a obszar wyniknie z niego sam.

Najczęściej zadawane pytania

Czym różni się stos od sterty w C?

Stos przechowuje zmienne lokalne: ich rozmiar ustala kompilator, powstają przy wejściu do funkcji i są niszczone przy powrocie, a alokacja nic nie kosztuje. Sterta przechowuje bloki z malloc: rozmiar wybierasz w czasie działania, blok żyje, dopóki go nie zwolnisz przez free, a alokacja ma realny koszt.

Dlaczego nie można zwrócić wskaźnika na zmienną lokalną w C?

Bo pamięć zmiennej lokalnej jest zwalniana w chwili powrotu z funkcji. Wskaźnik nadal trzyma ten adres, ale pamięć należy już do następnego wywołania funkcji: odczyt daje śmieci, a zapis psuje niezwiązane dane. To jest wiszący wskaźnik. Zwróć blok z malloc albo niech wywołujący dostarczy bufor.

Jak duży jest stos w C?

Zwykle od 1 do 8 MB dla głównego wątku i dużo mniej dla dodatkowych wątków. To na tyle mało, że int big[1000000]; jako zmienna lokalna zwykle wysypuje program przy wejściu do funkcji. Sterta jest ograniczona dostępną pamięcią systemu, więc duże dane lub dane o nieznanym rozmiarze należą właśnie tam.

Kiedy w C używać sterty zamiast stosu?

W trzech przypadkach: rozmiar jest znany dopiero w czasie działania, dane muszą przeżyć funkcję, która je utworzyła, albo blok jest za duży na stos (mniej więcej wszystko powyżej kilkuset kilobajtów). Cała reszta powinna być zwykłą zmienną lokalną: to szybsze i nie może wyciec.

Powiązane zagadnienia