Dynamic Memory Allocation

dynamická alokácia pamäte pomocou malloc() a calloc(), uvoľnenie alokovanej pamäte pomocou free(), problémy pri alokovaní, pravouhlé pole, zubaté pole, pole smerníkov

Záznam z prednášky

Previously In Programovanie

  • (slide) Naposledy sme sa pozreli na to, ako a hlavne kde sú údaje uložené v pamäti. Zoznámili sme sa s operátormi referencie a dereferencie.

  • Celý čas sme sa ale hrali s jednoduchými údajovými typmi. Na konci sme sa pozreli, ako je to s jednorozmernými poliami, kde sme porovnávali dva reťazce. Dnes na túto tému nadviažeme.

Problem of Copying Strings

  • Ak pracujeme s jednoduchými typmi, tak skopírovať hodnotu premennej a do premennej b je veľmi jednoduché - stačí použiť operátor priradenia (=). Prvý pokus o vytvorenie kópie reťazca by teda mohol vyzerať takto (reťazec, ktorý predstavuje kópiu zdroja, bude mať prvé písmeno veľké (použitím knižnice ctype.h), aby bolo jasné, že sa jedná o kópiu):

    #include <stdio.h>
    #include <ctype.h>
    
    int main(){
        char src[10];
    
        printf("Write a simple string: ");
        scanf("%s", src);
    
        char *dest = src;
        dest[0] = toupper(dest[0]);
    
        printf("%5s: %s\n%5s: %s\n", 
              "src", src, "dest", dest);
    }
  • Problém je, že po sputení programu majú veľké začiatočné písmeno oba reťazce. To je spôsobené tým, že miesto skopírovania obsahu pôvodného reťazca sme skopírovali len jeho adresu. O tom sa môžeme presvedčiť spustením programu cgdb a nechať si vypísať:

    • adresu pôvodného reťazca src:

      print &src
    • adresu, na ktorú ukazuje *dest:

      print dest
  • Ak chceme skopírovať reťazec, musíme:

    • vytvoriť dostatočne veľké miesto v pamäti, a
    • prekopírovať znak po znaku pôvodný reťazec na toto nové miesto.
  • Vytvoriť kópiu teda môžeme pomocou vlastnej funkcie takto:

    char* str_copy(const char* string){
        char buffer[10];
    
        for(int i = 0; string[i] != '\0'; i++){
            buffer[i] = string[i];
        }
    
        buffer[0] = toupper(buffer[0]);
        return buffer;
    }
  • (slide) Aj keď je zámer dobrý, prekladač odmietne program preložiť s odôvodnením, že sa snažíme vrátiť adresu lokálnej premennej. Problém je v tom, že buffer, ktorý sme v tejto funkcii vytvorili pre potreby vytvorenia kópie, je lokálny a zanikne po ukončení behu tejto funkcie. Preto potrebujeme vytvoriť dostatočne veľké miesto tak, aby sme ho mali k dispozícii aj po ukončení funkcie str_copy().

Memory Allocation with malloc()

  • (slide) Na to použijeme funkciu malloc() zo štandardnej knižnice stdlib.h. Táto funkcia nám umožňuje požiadať systém o pridelenie takého množstva voľnej pamäte, koľko potrebujeme. Parametrom tejto funkcie je teda množstvo pamäte, ktoré potrebujeme. Ak systém má prostriedky k vyhradeniu uvedeného množstva pamäte, vráti nám referenciu naň. Ak nemá, vráti NULL.

  • (slide) Pri špecifikovaní veľkosti požadovanej pamäte je potrebné požiadať o presný počet bytov, ktorý sa má vyhradiť. Preto je potrebné toto množstvo špecifikovať zápisom:

    POCET POLOZIEK * VELKOST JEDNEJ POLOZKY
  • V našom prípadíme alokujeme priestor pre buffer nasledovne:

    char* buffer = malloc(10 * sizeof *string);
  • Samozrejme môžeme buffer alokovať dynamicky na základe skutočnej dĺžky reťazca string:

    char* buffer = malloc(strlen(string) * sizeof *string);
  • Pri preklade už nebude prekladač nič namietať.

Memory Allocation with calloc()

  • (slide) Alternatívou funkcie malloc() je funkcia calloc(). Hlavným rozdielom medzi nimi je to, že funkcia calloc() vracia pamäť, kde každý jej byte je inicializovaný na hodnotu \0 (pamäť vyprázdni, resp. vynuluje). Funkcia malloc() toto nerobí.

  • Okrem toho má funkcia calloc() dva parametre miesto jedného:

    • počet prvkov, pre ktoré má byť pamäť vyhradená, a
    • veľkosť jedného prvku v pamäti
  • Finálna verzia programu s funkciou calloc() bude vyzerať takto:

    char* str_copy(const char* string){
        char *buffer = calloc(strlen(string), sizeof *string);
    
        for(int i = 0; string[i] != '\0'; i++){
            buffer[i] = string[i];
        }
    
        buffer[0] = toupper(buffer[0]);
        return buffer;
    }

Memory leak

  • (slide) Existuje niekoľko problémov, s ktorými sa dá stretnúť pri dynamickej práci s pamäťou, ako napr.:

    • čítanie z miesta, ktoré mi nepatrí
    • zápis na miesto, ktoré mi nepatrí
    • stratenie referencie na oblasť pamäti, ktorú som si vyhradil
    • neupratanie si pamäte po skončení funkcie alebo programu
  • Tieto problémy sa odhaľujú ťažko a častokrát si dokonca ani nevšimnete, že k tomuto problému došlo. Proste - ste mali šťastie. Rovnako je tomu aj v predchádzajúcom príklade - všimli ste si, že je v ňom chyba? Veď predsa vrátil presne to, čo mal.

Valgrind

  • (slide) Odhaliť úniky v pamäti je možné pomocou vhodných nástrojov. Jedným z nich je aj nástroj s názvom Valgrind. Jeho použitie vyzerá nasledovne:

    $ valgrind ./spustitelny_subor
  • V našom prípade ho teda spustím s preloženou binárkou programu copy.c:

    $ valgrind ./copy
  • Na obrazovke sa objaví výpis podobný tomuto:

    ==1234== Invalid read of size 1
    ==1234==    at 0x4C30BC4: strlen (vg_replace_strmem.c:454)
    ==1234==    by 0x5192AD0: vfprintf (in /usr/lib64/libc-2.24.so)
    ==1234==    by 0x5199718: printf (in /usr/lib64/libc-2.24.so)
    ==1234==    by 0x4007FD: main (copy.c:27)
    ==1234==  Address 0x55098c4 is 0 bytes after a block of size 4
    alloc'd
    ==1234==    at 0x4C2DB9D: malloc (vg_replace_malloc.c:299)
    ==1234==    by 0x400745: copy (copy.c:7)
    ==1234==    by 0x4007DF: main (copy.c:25)
  • Vo výstupe je možné vidieť, že došlo k neoprávnenému čítaniu o veľkosti 1B (Invalid read of size 1) priamo za alokovaným miestom v pamäti (Address 0x55098c4 is 0 bytes after a block of size 4 alloc'd) pri použití funkcie printf().

  • Tento problém pramení vo vytvorenej funkcii str_copy(), kde sme pri alokácii pamäte zabudli na jeden byte navyše pre ukončenie reťazca (terminátor). Po ošetrení kódu táto chyba zmizne:

    char *buffer = calloc(strlen(string) + 1, sizeof *string);

Unreleased Memory

  • Okrem tejto chyby však valgrind hlási ešte jeden problém:

    ==35463== HEAP SUMMARY:
    ==35463==     in use at exit: 4 bytes in 1 blocks
    ==35463==   total heap usage: 3 allocs, 2 frees, 2,052 bytes 
    allocated
    ==35463==
    ==35463== LEAK SUMMARY:
    ==35463==    definitely lost: 4 bytes in 1 blocks
    ==35463==    indirectly lost: 0 bytes in 0 blocks
    ==35463==      possibly lost: 0 bytes in 0 blocks
    ==35463==    still reachable: 0 bytes in 0 blocks
    ==35463==         suppressed: 0 bytes in 0 blocks
  • V závislosti od dĺžky reťazca valgrind hlási, že po skončení programu zostalo v pamäti neuvoľnené 4 byty.

  • Tento problém súvisí s tým, že sme si po sebe neupratali - neuvoľnili sme pamäť, ktorú sme si vyhradili. V tomto prípade nie je problém veľký, pretože všetky prostriedky, ktoré sme si počas behu programu vyhradili, budú uvoľnené automaticky systémom po skončení programu. Dokonca sú tieto byty označené ako definitívne stratené.

  • Tento problém môže byť však veľmi nebezpečný. Ak budeme nepravidelne alokovať pamäť, ktorú nebudeme uvoľňovať, toto správanie môže viesť až ku úplnému vyplytvaniu voľnej pamäte, kedy funkcie na alokáciu pamäte budú vracať NULL.

  • (slide) Tomu samozrejme vieme predísť tým, že keď už danú pamäť nepotrebujeme, požiadame o jej uvoľnenie pomocou funkcie free(). Parametrom tejto funkcie je adresa, ktorá nám bola pridelená funkciou na alokáciu pamäte.

  • Po zapracovaní úprav bude výsledná podoba programu vyzerať nasledovne:

    #include <stdio.h>
    #include <ctype.h>
    #include <string.h>
    #include <stdlib.h>
    
    char* str_copy(char* string){
        char *buffer = calloc(strlen(string) + 1, sizeof *string);
    
        for(int i = 0; string[i] != '\0'; i++){
            buffer[i] = string[i];
        }
    
        buffer[0] = toupper(buffer[0]);
        return buffer;
    }
    
    int main(){
        char src[30];
    
        printf("Write a string: ");
        scanf("%s", src);
    
        char *dest = str_copy(src);
    
        printf("%5s: %s\n%5s: %s\n", "src", src, "dest", dest);
    
        free(dest);
    }
  • Po preložení a spustení programu už valgrind nebude hlásiť žiadny problém.

The Problem: Loading the Words DB into Memory

  • Vytvorenú funkciu na kopírovanie reťazcov použijeme pri implementovaní nasledovného problému.

  • Pri Hangmanovi ste používali predpripravenú funkciu getWord(), ktorá umožňovala načítať náhodné slovo zo súboru, ktorý obsahoval spolu 55900 slov. Čo ak by ale k tomuto súboru pristupovalo naraz niekoľko spustených programov (multipoužívateľský Linux)? Alebo čo ak by sa jednalo o sieťovú aplikáciu a zakaždým, keď by niekto chcel získať tajné slovo by tento súbor musel otvoriť? Výber náhodného slova zo súboru by sa veľmi rýchlo mohol stať úzkym hrdlom celej aplikácie.

  • Vyriešiť tento problém by sme mohli tak, že celý súbor načítame naraz do pamäte a pre získanie náhodného slova už nebudeme potrebovať pristupovať k súboru, ale priamo ho z tej pamäte dostaneme.

  • Pokúsme sa teda vytvoriť funkciu, ktorá tento súbor načíta a vráti nám ho v podobe dvojrozmerného poľa, kde počet riadkov bude zodpovedať počtu slov v súbore a na každom riadku sa bude nachádzať jedno slovo.

Bootstrap

  • Začneme jednoduchým programom, pomocou ktorého otvoríme súbor words.txt a vypíšeme jeho obsah slovo po slove na obrazovku:

    #include <stdio.h>
    #include <stdlib.h>
    
    int main(){
        FILE *fp = fopen("words.txt", "r");
        if(fp == NULL){
            printf("No such file or directory: words.txt\n");
            exit(EXIT_FAILURE);
        }
    
        char buffer[30];
    
        while(fscanf(fp, "%s", buffer) != EOF){
            printf("%s\n", buffer);
        }
    
        fclose(fp);
    }

Square Array

  • Teraz sa pokúsime načítať obsah súboru words.txt do dvojrozmerného poľa, pričom každé slovo sa bude nachádzať na jednom riadku tohto poľa.

  • Aké rozmery bude mať toto pole? Počet riadkov (počet slov = 55900) x počet stĺpcov (max. dĺžka slova = 15)

  • Zadeklarujeme toto statické pole:

    char words[55900][15];
  • (slide) Typ poľa, ktoré sme takto vytvorili, sa nazýva pravouhlé pole (z angl. square array). Je to typ poľa NxM, kde má každý riadok rovnakú dĺžku (šírku). V našom prípade to znamená, že aj keď reťazce samotné majú svoju dĺžku rozličnú, je pre každý z nich (riadok) vyhradené rovnako dlhé miesto v pamäti. Takýto typ poľa je veľmi jednoduché zakresliť aj pomocou štvorčekovaného papiera, kde jeho obrys predstavuje obdĺžnik.

  • Začneme teda miesto vypisovania reťazcov na obrazovku tieto vkladať do vytvoreného poľa:

    #include <stdio.h>
    #include <stdlib.h>
    
    int main(){
        FILE *fp = fopen("words.txt", "r");
        if(fp == NULL){
            printf("No such file or directory: words.txt\n");
            exit(EXIT_FAILURE);
        }
    
        char buffer[30];
        char words[55900][15];
        int line = 0;
    
        while(fscanf(fp, "%s", buffer) != EOF){
            sprintf(words[line], "%s", buffer);
            line++;
        }
    
        fclose(fp);
    }
  • A pre kontrolu správnosti po načítaní postupne tieto slová vypíšeme na obrazovku od posledného po prvé:

    #include <stdio.h>
    #include <stdlib.h>
    
    int main(){
        FILE *fp = fopen("words.txt", "r");
        if(fp == NULL){
            printf("No such file or directory: words.txt\n");
            exit(EXIT_FAILURE);
        }
    
        char buffer[30];
        char words[55900][15];
        int line = 0;
    
        while(fscanf(fp, "%s", buffer) != EOF){
            sprintf(words[line], "%s", buffer);
            line++;
        }
    
        fclose(fp);
    
        line--;
        while(line >= 0){
            printf("%s\n", words[line]);
            line--;
        }
    }
  • (slide) Výhodou je síce jednoduchosť deklarácie aj prístupu, ale nevýhodou je plytvanie pamäťou. Ak najdlhší reťazec má dĺžku N a iný (kratší) reťazec má dĺžku M, tak tento reťazec plytvá v pamäti práve N-M bytmi.

Jagged Array

  • (slide) Pokúsime sa teda upraviť náš program tak, aby sme pre každý reťazec použili práve toľko miesta, koľko potrebuje. Pre každý jeden reťazec si vyžiadame toľko pamäte, koľko daný reťazec potrebuje (plus terminátor). Okrem toho potrebujeme zoznam referencií na jednotlivé reťazce.

    Jagged Array
  • (slide) Tento typ poľa sa volá zubaté pole (z angl. jagged array).

Pole pointerov

  • Najprv vytvoríme pole pointerov na reťazce, ktorý bude vyzerať nasledovne:

    char* words[55900];
  • Keďže sa však jedná o pole pointerov, pre každý reťazec budeme potrebovať v pamäti vyhradiť (alokovať) miesto zvlášť.

  • Výsledný kód, ktorý realizuje tento prístup, je nasledovný:

    #include <stdio.h>
    #include <stdlib.h>
    #include <string.h>
    
    int main(){
        FILE *fp = fopen("words.txt", "r");
        if(fp == NULL){
            printf("No such file or directory: words.txt\n");
            exit(EXIT_FAILURE);
        }
    
        char buffer[30];
        char *words[55900];
        int line = 0;
    
        while(fscanf(fp, "%s", buffer) != EOF){
            // created earlier
            words[line] = str_copy(buffer);  
            line++;
        }
    
        fclose(fp);
    
        line--;
        while(line >= 0){
            printf("%s\n", words[line]);
            line--;
        }
    }

Pointer na pointer

  • Ak chceme vytvoriť funkciu, ktorá má vrátiť pole pointerov, nemôžeme použiť zápis char* words[55900] pretože týmto spôsobom vytvoríme statické pole pointerov na znak, resp. reťazce. Ak chceme vytvoriť takéto pole dynamicky, budeme postupovať takto:

    char** words = calloc(55900, sizeof(char*));
  • Následne potom postupujeme ako pri poli pointerov - pre každý riadok vyhradíme v pamäti miesto zvlášť.

  • Výsledný kód, ktorý realizuje tento prístup, je nasledovný:

    #include <stdio.h>
    #include <stdlib.h>
    #include <string.h>
    
    int main(){
        FILE *fp = fopen("words.txt", "r");
        if(fp == NULL){
            printf("No such file or directory: words.txt\n");
            exit(EXIT_FAILURE);
        }
    
        char buffer[30];
        char **words = calloc(55900, sizeof(char*));
        int line = 0;
    
        while(fscanf(fp, "%s", buffer) != EOF){
            words[line] = str_copy(buffer);  // created earlier
            line++;
        }
    
        fclose(fp);
    
        line--;
        while(line >= 0){
            printf("%s\n", *(words + line));
            line--;
        }
    }

Parametre príkazového riadku

  • (slide) S týmto spôsobom zápisu ste sa stihli stretnúť už v zimnom semestri v rámci predmetu Základy algoritmizácie a programovania, keď ste hovorili o parametroch príkazového riadku. Deklarácia funkcie main vyzerá takto:

    int main(int argc, char** argv)

    (slide) alebo takto:

    int main(int argc, char* argv[])
  • A tu si môžete všimnúť, akým spôsobom je reprezentovaný parameter argv - je to vlastne pole pointerov, o ktorom sme dnes rozprávali.

Zistenie počtu slov v súbore

  • Aj keď sme síce vyriešili problém, že vieme načítať ľubovoľný súbor, nemôžeme zaistiť, že každý z nich bude mať vždy práve 55900 slov. Pred načítavaním by sme teda potrebovali zistiť, koľko slov sa v skutočnosti v danom súbore nachádza.

  • Keďže už vieme súbor prechádzať po slovách, budeme potrebovať vykonať jeden prechod bez toho, aby sme slová do poľa ukladali. Tento prechod využijeme len na to, aby sme zistili počet slov, ktoré sa v súbore nachádzajú. Využiť môžeme tento fragment kódu:

    // count words
    int counter = 0;
    while(fscanf(fp, "%s", buffer) != EOF){
        counter++;
    }
  • Tento kód sa zastaví vtedy, keď funkcia fscanf() už nebude môcť ďalej zo súboru načítavať. To nastane v prípade, keď sa kurzor (pozícia v súbore, z ktorej čítame) dostane na koniec súboru.

  • My však budeme potrebovať načítať obsah súboru znova a tentokrát jednotlivé slová aj ukladať. Budeme potrebovať presunúť kurzor na začiatok súboru. To môžeme docieliť

    • zatvorením a znovuotvorením súboru, čo je nepraktické,

    • použitím funkcie fseek(), ktorá slúži práve na presunutie pozície kurzora v súbore. Volaním v tvare

      fseek(fp, 0, SEEK_SET);

      docielime presunutie kurzora na začiatok súboru.

    • použitím funkcie rewind(), ktorá presunie pozíciu kurzora na začiatok súboru. Používa sa v tvare:

      rewind(fp);
  • Nahradením hodnoty 55900 obsahom premennej counter následne docielime požadovaný výsledok:

    #include <stdio.h>
    #include <stdlib.h>
    #include <string.h>
    
    int main(int argc, char* argv[]){
        if(argc != 2){
            printf("Error: missing parameter\n");
            exit(EXIT_FAILURE);
        }
    
        FILE *fp = fopen(argv[1], "r");
        if(fp == NULL){
            fprintf(stderr, 
                    "No such file or directory: words.txt\n"
            );
            exit(EXIT_FAILURE);
        }
    
        char buffer[30];
    
        // count words
        int counter = 0;
        while(fscanf(fp, "%s", buffer) != EOF){
            counter++;
        }
        rewind(fp);
    
        char **words = calloc(counter, sizeof(char*));
        int line = 0;
    
        while(fscanf(fp, "%s", buffer) != EOF){
            words[line] = str_copy(buffer);  // created earlier
            line++;
        }
    
        fclose(fp);
    
        line--;
        while(line >= 0){
            printf("%s\n", *(words + line));
            line--;
        }
    }

Funkcia vracajúca zoznam načítaných slov zo súboru

  • Nakoniec už len spojíme veci dokopy a vytvoríme funkciu get_words(), ktorá vráti pole smerníkov na samotné slová:

    #include <stdio.h>
    #include <stdlib.h>
    #include <string.h>
    
    char** get_words(const char* file, int *counter){
        FILE *fp = fopen(file, "r");
        if(fp == NULL){
            fprintf(stderr, 
                    "No such file or directory: %s\n", 
                    file
            );
            exit(EXIT_FAILURE);
        }
    
        char buffer[30];
    
        // count words
        *counter = 0;
        while(fscanf(fp, "%s", buffer) != EOF){
            *counter += 1;
        }
        rewind(fp);
    
        char **words = calloc(*counter, sizeof(char*));
        int line = 0;
    
        while(fscanf(fp, "%s", buffer) != EOF){
            words[line] = str_copy(buffer);  // created earlier
            line++;
        }
    
        fclose(fp);
        return words;
    }
    
    int main(int argc, char* argv[]){
        if(argc != 2){
            printf("Error: missing parameter\n");
            exit(EXIT_FAILURE);
        }
    
        int counter = 0;
        char** words = get_words(argv[1], &counter);
    
        for(int line = 0; line < counter; line++){
            printf("%s\n", words[line]);
        }
    }

Cleanup

  • Ak teraz spustíme valgrind, tak vypíše stav využívania pamäti po skončení aplikácie, z ktorého vyplýva, že sme po sebe neuvoľnili spolu 55901 alokácií, čím v pamäti zostalo 923 068 bytov:

    ==22750== HEAP SUMMARY:
    ==22750==     in use at exit: 923,068 bytes in 55,901 blocks
    ==22750==   total heap usage: 55,904 allocs, 3 frees, 928,740 
    bytes allocated
  • Pred ukončením programu je dobré si po sebe upratať. Preto je potrebné pre každú jednu alokáciu vytvoriť aj dealokáciu v poradí od jednotlivých reťazcov až po uvoľnenie pamäti so zoznamom referencií na jednotlivé alokované reťazce.

  • Výsledná implementácia teda môže vyzerať nasledovne:

    // cleanup
    for(int line = 0; line < counter; line++){
        free(words[line]);
    }
    
    free(words);

Double Free

  • (slide) Nastavením premennej, ktorá sa odkazovala na pridelenú pamäť, na hodnotu NULL slúži aj ako ochrana pred problémom s dvojitým uvoľnením (z angl. double free). Ako už názov hovorí, k tomuto problému dôjde pri opätovnom pokuse uvoľniť už uvoľnenú pamäť. V prípade, že však parametrom funkcie free() bude hodnota NULL, nič sa nevykoná.

  • Ak teda skopírujeme riadok uvoľňujúci pole referencií words, program preložíme a spustíme, skončí s chybou segmentácie.

Use After Free

  • (slide) Častým problémom býva, že sa k obsahu pamäte snažíme pristúpiť aj po jej uvoľnení. Uvoľnená pamäť totiž nemusí byť hneď prepísaná novými údajmi, takže sa môže stať, že sa k uloženým údajom ešte dokážeme dostať.

  • Tento problém sa volá Use After Free a má 8. priečku v zozname TOP 25 najnebezpečnejších softvérových chýb (2020 CWE Top 25 Most Dangerous Software Weaknesses). Použitím pamäte po jej uvoľnení totiž môže dôjsť k neočakávanému správanie až k pádu programu.

  • Je preto dobré priamo po uvoľnení pamäte ešte premennú, ktorá držala referenciu na uvoľňovanú pamäť priamo nastaviť na hodnotu NULL, čím problému predídeme.

Conclusion

  • (slide) Teraz už určite musíte rozumieť tomu, ako to v tej pamäti funguje. A ak nie, dajte ešte raz šancu videu, ktoré ste už videli aj minulý týždeň. Veď - opakovanie je matkou múdrosti ;)