{{indexmenu_n>6}} ====== 6 - Dynamická alokace 1/2 ====== * pro vyučující: [[courses:b0b36prp:internal:tutorialinstruction:06|]] ===== Cíle cvičení ===== - Dekompozice programu na funkce. - Implementace funkčního a správného programu s ošetřením možných chybových stavů. - Dynamická alokace a načítání vstupu (souboru). Cvičení na dynamickou alokaci pokračuje [[courses:b0b36prp:labs:lab07|7 - Dynamická alokace 2/2]]. Hlavním cílém 6. cvičení je seznámit se se základním použitím ''malloc'' a ''realloc'' ve funkci ''read()''. Rozšíření na načítání více řádků je možné dokončit na 7. cvičení. ==== Teoretická příprava ==== * [[courses:b0b36prp:tutorials:coding:c_dyn_mem|Dynamická alokace paměti v C]] * [[https://en.wikipedia.org/wiki/Standard_deviation|Smerodatna odchylka]] ===== Úkoly ===== * Implementujte program, který načte vstupní textový soubor, který následně vypíše v náhodném pořadí řádků. * Nejdříve si vyzkoušejte implementaci vytvoření permutace posloupnosti čísel 0 až n, viz ''man 3 rand''. * Následně implementujte načtení řádků s dynamickou alokací. Předpokládejte, že vstup má řádky zakončeny znakem '''\n'''. * Program vhodně dekomponujte a uvažujte tři chybové stavy (//jejich hlavní význam bude při následné úpravě programu pro přímou práci se soubory//). * 100 - Chyba načtení. * 101 - Chyba alokace dynamické paměti. * 102 - Chyba výstupu. //Uvažujte, že tisk na standardní výstup může selhat//. * Jako datovou strukturu uvažujte dynamicky alokované pole ukazatelů na textové řetězce reprezentující postupně načtené řádky. (//Není nutné používat složený typ ''struct'', byť to může být výhodné//). * Při implementaci můžete využít ladění programem ''valgrind''. * Před ukončením programu, uvolněte alokovanou paměť. ==== Vytvoření permutace ==== - Implementujte tři funkce ''init'', ''print'', ''permute'', např. void init(unsigned int n, unsigned int a[n]); void print(unsigned int n, unsigned int a[n]); void permute(unsigned int n, unsigned int a[n]); - Funkce použijte v např. v jednoúčelovém programu pro inicializaci pole celých čísel, jeho vytištění, permutování a znovu vytištění na ''stdout''. #include #include #ifndef MAX_NUM #define MAX_NUM 10 #endif void init(unsigned int n, unsigned int a[n]); void print(unsigned int n, unsigned int a[n]); void permute(unsigned int n, unsigned int a[n]); int main(void) { int ret = EXIT_SUCCESS; const unsigned int n = MAX_NUM; unsigned int a[MAX_NUM]; init(n, a); print(n, a); permute(n, a); printf("Randomized array\n"); print(n, a); return 0; } S výstupem např. clang -DMAX_NUM=5 perm.c -o perm && ./perm 0 1 2 3 4 Randomized array 3 0 4 2 1 ==== Načtení řádku s dynamickou alokací ==== * Vytvoříme si funkce pro načtení textové řetězce ze ''stdin'' a jeho vytištění na ''stdoout'' funkce ''print''. * Výpis řádku předpokládá, že na vstupu načteme konec řádků, který je součástí textového řetězce. * Výpis je tisk jednotlivých znaků do nenarazíme na znak konce řetězce '''\0'''. * Naše funkce ''print'' předpokládá, že arugment je platný ukazatel na paměť zakončenou znakem '''\0'''. //To musíme zajistit programově, korektní incializací a předáváním proměnných.// void print(char *str) { size_t i = 0; while (str && str[i] != '\0') { putchar(str[i++]); } // if (str && str[i] == '\0') putchar('\n'); //not needed if new line character '\n' is a part of the string str. } * Pro zjednodušení zatím neuvažujeme rozlišení chybu vstupu a chybu alokace paměti. * Nicméně program ve funkci ''read'' korektně ošetřuje možné chybové stavy načtení a alokace paměti. * V případě chyby nebo ukončení vstupu vrací funkce ''read'' hodnotu neplatného ukazatele ''NULL''. #include #include #ifndef INIT_SIZE #define INIT_SIZE 128 #endif void print(char *str); char* read(void); int main(void) { int ret = EXIT_SUCCESS; char *str = NULL; unsigned int count = 1; while ((str = read())) { printf("%3d ", count++); print(str); free(str); } return ret; } * Ve funkci ''read()'' použijeme dynamickou alokaci (volání ''malloc'') a realokaci (volání ''realloc'') s kontrolou úspěšného přidělení paměti. * Můžeme použít různé strategie postupného zvětšování, je však postačující zvěšovat počáteční velikost dvakrát. * Možná úspora je po načtení řádku realokovat paměť řetězce na velikost (+1 pro '''\0''') voláním ''realloc''. ==== Načtení řádků do pole ukazatelů na textové řetězce ==== * Program zobecníme pro postupné načítání všech řádků s využitím implementované funkce ''read''. * Využijeme k tomu funkce ''read_lines'' a ''print_lines''. * Můžeme explicitně uvažovat počet načtených řádků, nebo využijeme podobného mechanismu jako //null terminating string//. int print_lines(size_t n, char **str); char** read_lines(size_t *n); void free_lines(size_t n, char ***str); int main(void) { int ret = EXIT_SUCCESS; size_t n = 0; char **lines = read_lines(&n); print_lines(n, lines); free_lines(n, &lines); return ret; } void print_lines(size_t n, char **str) { if (str) { for (size_t i = 0; i < n; ++i) { print(str[i]); } } } void free_lines(size_t n, char ***str) { if (str && *str) { for (int i = 0; i < n; ++i) { free((*str)[i]); } free(*str); } *str = NULL; } ==== Výpis řádků v náhodné permutaci ==== * Dosud implementované funkce spojíme do výsledného programu - Načte řádky. - Vytvoří náhodnou permutaci //Předpokládáme počet řádků je relativně malý a permutace čísel řádků se vejde na zásobník, proto použijeme VLA (pole variabilní délky).// - Vypíše řádky dle permutace. int main(void) { int ret = EXIT_SUCCESS; size_t n = 0; char **lines = read_lines(&n); unsigned int a[n]; // Počet řádku se musí vejít do paměti (zásobníku) init(n, a); permute(n, a); for (int i = 0; i < n; ++i) { print(lines[a[i]]); } free_lines(n, &lines); return ret; } ==== Přidání ošestření chybových stavů a reportování chyby návratovou hodnotou ==== * Upravte program pro ošetření chybových stavů. (//Řešení je několik, můžete realizovat různě.//) * Jednou z možností je přidat do funkcí načítání a výpisu ukazatel na proměnnou ''error''. (//podobně funguje ''errno'' ve std. knihovně C//). * Přidáme výčtový typ, kde zavedeme též vlastní ''ERROR_OK'' jako ''EXIT_SUCCESS'', abychom unifikovali identifikátory. enum { ERROR_OK = EXIT_SUCCESS, ERROR_IN = 100, ERROR_MEM = 101, ERROR_OUT = 102, }; * Hlavičky funkcí načítání upravíme přidáním ukazatele na ''error''. Při chybě vrací ''NULL'', kterým nerozlišíme důvod chyby. char* read(int *error); char** read_lines(size_t *n, int *error); * Původní funkce výpise nemají navratovou hodnotu, proto postačí přidat. int print(char *str); //return error value char* read(int *error); * Opakování cyklus výpisu řádku podmíníme úspěšným výpisem, např. int print_lines(size_t n, char **str) { int ret = ERROR_OK; if (str) { for (size_t i = 0; i < n && ret == ERROR_OK; ++i) { ret = print(str[i]); } } return ret; } * Podobně výpis jednoho řádku int print(char *str) { int ret = ERROR_OK; size_t i = 0; while (str && str[i] != '\0') { if (putchar(str[i++]) == EOF) { ret = ERROR_OUT; break; } } return ret; } * Nebo kratší verzí bez ''break'' s využitím ternárního operátor. int print(char *str) { int ret = ERROR_OK; size_t i = 0; while (str && ret == ERROR_OK && str[i] != '\0') { ret = putchar(str[i++]) == EOF) ? ERROR_OUT : ret; } return ret; } * Podobně upravíme funkce načítání řádku ''read'' a ''read_lines''. ==== Testování vstupu a chybových stavů ==== * Otestování chyby dynamické alokace z důvodu nedostatečné paměti lze realizovat nastavením limitu process, např. ''limit'', ''ulimit'' nebo ''limits'', dle OS a použitého interpretu příkazů. * Lze omezit heap paměť, ale také přímo velikost virtuální paměti přidělené processu. * Pro otestování budeme potřebovat nějaký rozumě veliký vstupný soubor (ideálně několik jednotek nebo desítek MB). Nicméně i tak je heap paměť využívána standardní knihovnou a i 2MB mohou být málo pro incializaci knihovny ''libc'' limits -v 2621440 ./rand * V případě nastavení 5 MB již program pro vstup řádově desítky MB selže a korektně vrátí návratovou hodnotu ''101''. limits -v 5242880 ./rand V Linuxu spíše použijete příkaz ulimit, který nastavuje aktuální sezení příkazového interpretu, což samo o sobě vyžaduje paměti více. Mimoto je nastavení paměti v kB a simulace malé paměti tak může být náročnější. Nicméně princip ošetření zůstává stále validní, ikdyž zrovna teď máme paměti dost, zásadní je princip, že uvažujeme takovou možnost a jsme na ni připraveni. Alternativně můžeme přijmout fakt, že chyba se může stát, ale když se stane, tak s tím nic neuděláme, což je typicky příklad vypisování zpráv na stderr, případně stdout, kde běžně nekontrolujeme, že se vypsalo vše co mělo. V takovém případě indikaci špatného chování máme, v případě přístupu do nepřidělené paměti může program stále běžet, ale nebude mít definované chování a uživatel o tom nebude informován. * Program dále můžeme rozšířit o vypsání chybové hlášky na ''stderr''. int main(void) { ... print_error(ret); return ret; } V případě jediného místa ukončení programu, return v hlavní funkci main, je to relativně snadné. Samotné rozšíření programu o testování chybových stavů je spíše pracné, než náročné. Zdrojový kód se stane relativně méně přehledný. Nicméně při krátkých funkcí je rozšíření relativně rychle a pokud jste implementovali vlastní řešení vhodně, mělo by se pohybovat mezi 5 až 10 minutami. * V programu můžeme vypsat ladící informaci o počtu načtených řádků, např. ve funkci read_lines fprintf(stderr, "DEBUG: n: %lu size: %lu\n", *n, size); * Při spuštění však zjistíme, že ani 5 MB není dost. limits -v 5242880 ./rand * Proto nastavíme více, např. 12 MB. limits -v 12582912 ./rand * Z čehož vidíme, že se nám podařilo načíst pouze 5922 řádků, což v našem případě odpovídá 742533 bytům, např. si necháme vypsat pouze prvních 5922 řádků programem ''head'' a spočítáme řádky, slova a znaky programem ''wc''. head -n 5922 in-long.txt |wc 5922 95927 742533 === Omezení paměti v Linuxu === Protože v Linuxu můžeme ještě narazit na chování OS a volání ''malloc'', které spíše vrátí přidělenou paměť (z virtuálního adreseního prostoru, který je v případě 64-bit dostatečně veliký) nicméně k fyzickému přidělení paměti dojde až při zápisu do paměti, které v případě nedostatku paměti skončí ukončením programu. Toto tzv. //overcommit// chování je možné nastavit globálně ''sysctl vm.overcommit_memory = 2'' a následně ''vm.overcommit_ratio'' a ''vm.overcommit_kbytes'', což však může mít katastrofální důsledky pro běžící OS. * Alternativou, tak může být přidat do funkce ''read_lines'' ladící výpis o pokusu rozšíření paměti, např. následovně. char** read_lines(size_t *n, int *error) { size_t size = INIT_SIZE; char **lines = malloc(size * sizeof(char*)); //Assume INIT_SIZE would always be > 0 *n = 0; *error = ERROR_OK; //assume everything would be fine if (lines) { char *str; while ((str = read(error))) { //read would return NULL and set the error if (*n == size) { fprintf(stderr, "DEBUG: realloc from %lu -> %lu\n", size, size * 2); char **t = realloc(lines, sizeof(char*) * size * 2); ... * Následně program spustíme s 26 MB ulimit -v 26624 ./rand < in-long.txt DEBUG: realloc from 128 -> 256 DEBUG: realloc from 256 -> 512 DEBUG: realloc from 512 -> 1024 DEBUG: realloc from 1024 -> 2048 DEBUG: realloc from 2048 -> 4096 DEBUG: realloc from 4096 -> 8192 DEBUG: realloc from 8192 -> 16384 DEBUG: realloc from 16384 -> 32768 DEBUG: realloc from 32768 -> 65536 DEBUG: realloc from 65536 -> 131072 zsh: segmentation fault (core dumped) ./rand < in-long.txt * kdy se nám podaří načíst 65536 řádků, následně malloc (nebo realloc) selže ve funkci ''read()'', podařilo se nám tak načíst pouze část vstupu. * Program tak havaruje z důvodu alokace ''unsigned int a[n];'' a omezené velikosti zásobníku. * Pokud paměť zvětšíme na 32 MB, program havaruje později. ulimit -v 32768 ./rand < in-long.txt DEBUG: realloc from 128 -> 256 DEBUG: realloc from 256 -> 512 DEBUG: realloc from 512 -> 1024 DEBUG: realloc from 1024 -> 2048 DEBUG: realloc from 2048 -> 4096 DEBUG: realloc from 4096 -> 8192 DEBUG: realloc from 8192 -> 16384 DEBUG: realloc from 16384 -> 32768 DEBUG: realloc from 32768 -> 65536 DEBUG: realloc from 65536 -> 131072 DEBUG: realloc from 131072 -> 262144 zsh: segmentation fault (core dumped) ./rand < in-long.txt Přidání uvedeného ladícího výstupu je příkladem ladění, které není tak přímočaré realizovat krokováním, neboť nás zajímá poslední hodnota, kdy program selže a krokování je v takovém případě neefektivní. === Ověření chování při chybě vstupu nebo výstupu === * Ověření správného chování při chybě vstupu nebo výstupu je náročnější, o to více, že používáme ''stdin'' a ''stdout'' společně s dostatečnými zdroj. Spíše můžeme realizovat např. omezený diskový prostor při ukládání na disk nebo vzdálené síťové uložiště, což vyžaduje hlubší znalost používání OS. * V našem případě se tak prozatím spokojíme s inspekcí kódu. ===== Další úkoly ===== * Program rozšiřte o zpracování dvou argumentů program indikující vstupní a výstupní soubor. * Práci se soubory můžete realizovat funkcemi ''fopen'', ''fclose'' a náhradou ''getchar'' a ''putchar'' funkcemi pro práci s proudem ''getc'' a ''putc''. * Místo explicitního udržování početu řádků můžeme použít dynamicky alokované pole se "zarážkou" reprezentovanou poloužkou s hodnotou NULL, podobně jako je u textového řetězce //null character//, viz [[https://en.wikipedia.org/wiki/Null-terminated_string]].