Seminář 4

Životnost objektů za běhu programu

Pro nás význam: kdy je objekt v paměti během běhu programu? (anglicky storage duration). Když je pamět objektu přidělena, říkáme, že je pro něj alokována. Uvolnění paměti objektu někdy říkáme dealokace.

Existují tři typy životnosti, statická, automatická a manuální.

Pro objekty se statickou životností je paměť alokována při startu programu, uvolněna na konci běhu programu. O její alokaci je rozhodnuto při překladu programu. Statickou zprávu paměti mají zejména

Objekty lze inicializovat na hodnotu známou v době překladu. Bez explicitní inicializace v kódu jsou automaticky inicializovány na 0.

Storage class static se u proměnné specifikuje při definici, píše se na první místo. Proměnná si uchovává hodnotu mezi jednotlivými zavoláními funkce.

int fce() {
    static int count;  // inicializace na 0 pri startu programu
    count += 1;
    return count;      // vraci kolikrat byla zavolana
}

Řetězcové literály jsou pouze ke čtení, pokus o jejich změnu vede k nedefinovanému chování. Mohou být uloženy tak, že se překrývají, například sdílejí svůj konec.

char *r = "retezcovy literal";
r[0] = 'x';  // nedefinovane chovani

Složené literály lze měnit.

typedef struct {
    float x;
    float y;
} vec2f;

// globalni promena
vec2f *ptr = &(vec2f){.x=3.2f, .y=2.1f};

// nekde uvnitr funkce
prt->x = 2.4;   // OK

Alokace a dealokace objektů s automatickou životností se děje automaticky za běhu programu. Mezi objekty s automatickou životností patří

Objekty typicky vznikají v momentě vstupu do bloku, ve kterém jsou definovány a zanikají při výstupu z tohoto bloku. Nejsou automaticky inicializovány, je nutné je inicializovat explicitně. Je chyba vracet z funkce adresu objektu s automatickou životností, objekt je totiž po skončení funkce dealokován. Dereference adresy pak vede k nedefinovanému chování.

int* fce() {
  int array[] = {1,2,3};
  return array;            // chyba !!!!!
}

// nekde v kodu
int *a = fce();
a[0] = 5;    // nedefinovane chovani

K manuální správě paměti aplikační programátor většinou využije nejakou knihovnu, kde je implementován alokátor paměti (ten se stará o přidělování paměti, sám ji získává od operačního systému, případně spravuje paměť se statickou životností). Rozhraní alokátoru ze standardní knihovny je dáno funkcemi z hlavičkového souboru stdlib.h.

Princip použití alokačních funkcí je následující: funkci předáme počet bajtů, které chceme alokovat. Funkce vrátí adresu prvního bajtu souvislého kusu paměti požadované velikosti. V případě, že se alokace nepovede, vrací funkce 0.

Funkci free předáme jako argument adresu, kterou někdy předtím vrátila některá alokační nebo realokační funkce, a která ukazuje na doposud neuvolněnou paměť.free tuto paměť uvolní. Pokud jí předáme 0, nedělá free nic. Pokud jí ovšem předáme jakoukoliv jinou adresu, vede to nedefinovanému chování.

Funkce realloc umožňuje změnit velikost již alokované paměti.

Podrobnosti k jednotlivým funkcím si čtenář najde v referenční příručce, řekneme si pouze příklady typického použití a častých chyb.

int m = 20;
int* array = malloc(m * sizeof(int)); // alokace pro pole int velikosti m
assert(array);  // pro ucely kurzu staci tato kontrola, 
                // obecne muze byt potreba komplikovanejsi test uspechu alokace

// pracuj s polem array

free(array);   // uvolnime pamet
array = 0;     // nastavime pointer na neplatny

Funkce realloc muze při změně velikosti alokovane paměti přesunout její obsah na jinou adresu a původní paměť uvolnit.

int realloc_size[] = {10, 12, 512, 32768, 65536, 32768};
int m = sizeof(realloc_size)/sizeof(realloc_size[0]);
int *next = 0;

for (int i = 0; i < m; i += 1) {
    int *ret = realloc(next, sizeof(int) * realloc_size[i]);
    assert(ret);
    printf("%p -> %p\n", next, ret);   // pokud dojde k presunu, vypisi se ruzne adresy
    next = ret;
}
free(next);

Mezi hlavní chyby při manuální správě paměti patří tzv. memory leak a double free. První chyba nastane tak, že v programu zapomeneme adresu alokované paměti bez toho, abychom ji uvolnili. Tím pádem už ji nikdy uvolnit nemůžeme. Program má pak tuto paměť alokovánu zbytečně. Ke druhé chybě dojde tak, že se alokovanou paměť pokusíme uvolnit dvakrát (nebo vícekrát), mimo první pokus to vede k nedefinovanému chování.

Na závěr dodejme, že po skončení programu všechnu jeho paměť uvolní operační systém.

Existují také jiné přístupy ke správě paměti, které nahrazují nebo vylepšují manuální správu, například tzv. počítání referencí nebo garbage kolektory. Ty jsou v určité formě pro jazyk C přístupné jako knihovny (např.Boehm garbage collector).

Úkoly

  1. Implementujte funkci, která vrátí nově alokovaný řetězec, jehož obsah vznikne spojením dvou řetězců předaných funkci jako argumenty.

  2. Implementuje zásobník pomocí dynamického pole.

    typedef struct {
    int *data;    // pole pro vlozena data
    int top;      // pocet vlozenych prvku
    int cap;    // velikost pole data
} Stack;

Stack create_stack() {
    return (Stack){0};
}

    Doprogramujte operaci push tak, aby v momentě, kdy je zásobník zaplněn, tato operace realokovala položku data na dvojnásobnou velikost.

    Doprogramujte operaci ‘pop’ tak, aby v momentě, kdy je zásobník zaplněn z jedné čtvrtiny, zmenšila položku data na polovinu.

    První nenulovou velikost zásobníku vyberte jako malou mocninu 2, např. 16.

  3. Vytvořte strukturu struct matrix pro matici desetinných čísel (double), s položkami pro rozměry matice (počet řádků a sloupců) a data (obsah matice). O vnitřním uložení a adresování jednotlivých prvků matice rozhodněte sami.

    Naprogramujte funkce:

    void allocate_matrix(struct matrix *m, int rows, int cols);

    Funkce nastaví v m položky pro rozměry matice a alokuje pamět pro data.

    void initialize_matrix_from_array(struct matrix *m, double *array);

    Funkce inicializuje obsah podle pole array v row-major pořadí: řádky matice jsou naskládány za sebe, jako reprezentaci dvourozměrného pole jednorozměrným z minulého semestru. Můžete předpokládat, že array je dostatečně velké.

    void destroy_matrix(struct matrix *m);

    Funkce dealokuje paměť a nastaví odpovídající pointery na 0.

    struct matrix multiply_matrix(struct matrix a, struct matrix b);

    Funkce vynásobí matice (předpokládejme, že vynásobit jdou). Pro data výsledné matice alokuje novou paměť.

    void print_matrix(struct matrix a);

    Funkce vytiskne matici jako tabulku.