{{indexmenu_n>7}} ====== 7 - Dynamická alokace a textové soubory ====== * [[courses:b0b36prp:internal:tutorialinstruction:06|pro vyučující]] ===== Cíle cvičení ===== - Dynamická alokace: ''malloc'' a ''realloc''. - Načítání vstupu ze souboru. - Zpracování argumentů programu. - Implementace funkčního a správného programu s ošetřením možných chybových stavů. Cvičení na dynamickou alokaci pokračuje [[courses:b0b36prp:labs:lab08|8 - Dynamická alokace a struktury]]. Věnujte dostatek času pochopení základů a případně pokračujete na dalším cvičení. ==== Materiály ==== * [[courses:b0b36prp:tutorials:coding:c_dyn_mem|Dynamická alokace paměti v C]] ===== Úkoly ===== * Implementujte program, který načte vstupní textový soubor, který následně vypíše v opačném pořadí řádků (//varianta příkazu [[https://man7.org/linux/man-pages/man1/tac.1.html|tac]]//). * 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. * 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é a ukážeme si v lab07.//). * Při implementaci můžete využít ladění programem ''valgrind''. * Před ukončením programu uvolněte alokovanou paměť. Funkčnost programu si můžete ověřit vytvořením kontrolního výstupu programem ''tac'' a porovnáním s výstupem implementovaného programu. Např. ./main in.txt > my_out.txt; tac in.txt > out.txt; diff my_out.txt out.txt Program dekomponujeme na následující funkce. * Načtení řádku, ++ např. | char* read(FILE *fd);++. * Načtení řádků, ++ např.| char** read_lines(FILE *fd, size_t *n); ++. * //Tisk řádku a řádků, // pokud nechceme například použít ''printf("%s")'', ++ např. | int print_lines(size_t n, char **lines); nebo jen int print_lines(char **lines); pokud použijeme ''NULL-terminated'' pole řetězců++. * Uvolnění paměti ++ např. | free_lines(char ***lines);++. Implementační postup můžeme zvolit například následující. - Implementace načtení řádku znak-po-znaku s dynamickou alokací, pro zjednodušení budeme uvažovat ''FILE *fd = stdin;''. - Implementace načtení řádků. - Vytištění výstupu. - Přidání zpracování argumentu programu se jménem vstupního souboru. - Rozlišení chyby vstupu a chyby alokace. ==== Načtení řádku s dynamickou alokací ==== * Vytvoříme si funkce pro načtení textové řetězce ze souboru typu ''FILE*'' a jeho vytištění na ''stdout'', funkce ''print''. * Pro začátek použijme vstupní ''stdin'', např. jako ''FILE *fd = stdin;''. * Výpis řádku předpokládá, že na vstupu načteme konec řádku '''\n''', který je součástí textového řetězce. * Výpis je tisk jednotlivých znaků dokud 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í, načtením vstupu a předáváním proměnných.// ++++ Příklad funkce print()| int print(char *line) { int r = 0; while (line && *line != '\0' && (r = putchar(*line++)) != EOF); return r == EOF ? ERROR_OUT : ERROR_OK; } ++++ * Pro zjednodušení zatím neuvažujeme rozlišení chyby vstupu a chyby 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 vrací funkce ''read'' hodnotu neplatného ukazatele ''NULL''. ++++ Příklad volání načtení vstupu a tisk | #include #include void print(char *str); char* read(FILE *fd); int main(void) { int ret = EXIT_SUCCESS; FILE *fd = stdin; char *str = NULL; unsigned int count = 1; while ((str = read(fd))) { 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í, přesto je 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//. ++++ Příklad volání read_lines(), print_lines() a free_lines() | int print_lines(size_t n, char **str); char** read_lines(FILE *fd, size_t *n); void free_lines(size_t n, char ***str); int main(void) { int ret = EXIT_SUCCESS; FILE *fd = stdin; size_t n = 0; char **lines = read_lines(fd, &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; } ++++ ==== Zpracování argumentu programu se jménem vstupního programu ==== * Program zobecníme pro načítání vstupu ze souboru, jehož jméno je prvním argumentem programu. Pokud není argument zadán, budeme uvažovat ''stdin'' nebo ohlásíme chybu. * Použijeme funkci ''fclose()'' pro explicitní uzavření souboru, jakmile načteme řádky ze souboru. //Podobně jako volání ''free()'' v krátkých programech, učíme se programovat správně, přestože v malém, jednorázovém programu to nemusí být pragmaticky nutné, neboť soubory jsou uzavřeny po skončení programu.// ++++ Příklad zpracování argumentu programu| int main(int argc, char const *argv[] { FILE *fd = stdin; if (argc > 1) { fd = fopen(argv[1], "r"); } if (!fd) { fprintf(stderr, "ERROR: Cannot open input file\n"); fprintf(stderr, "Usage is %s [filename]\n", argv[0]); fprintf(stderr, "If filename is not given, stdin is used\n"); return ERROR_IN; } size_t m = 0; char **lines = read_lines(fd, &m); ... if (argc > 1) { fclose(fd); //close input if it is not the stdin } ... ++++ ==== Přidání ošetření chybových stavů a reportování chyby návratovou hodnotou ==== * Upravíme 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. ++++ Příklad chybových kódu programu| 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. ++++ Defince prototypů funkcí | char* read(FILE *fd, int *error); char** read_lines(FILE *fd, size_t *n, int *error); ++++ * Výstup realizujeme vlastní funkcí ''print()'' a přidáme návratovou hodnotu. ++++ Příklad hlavičky funkcí print a read| int print(char *str); //return error value char* read(FILE *fd, int *error); ++++ * Opakování cyklu výpisu řádku podmíníme úspěšným výpisem, např. ++++ Příklad funkce print_lines | int print(char *line) { int r = 0; while (line && *line != '\0' && (r = putchar(*line++)) != EOF); return r == EOF ? ERROR_OUT : ERROR_OK; } int print_lines(size_t n, char **lines) { int ret = ERROR_OK; // Since i is of the size_t type, we might have to avoid "underflow" to negative values. Note that over/underflow of unsigned integers is defined in C/C++; however, for educative purposes, think about it! for (size_t i = n; ret == ERROR_OK && lines && i > 0; --i) { ret = print(lines[i-1]); } return ret; } ++++ * Podobně výpis jednoho řádku ++++ Jiný příklad tisku 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. ++++ Kratší verze ternárním operátorem ? :| 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 můžeme 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 (++ příklad vygenerování 20MB souboru | $ tr -dc A-Za-z'\n' < /dev/urandom | head -c 20000000 > in-long.txt ++). 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 ./main * 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 ./main 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(int argc, char const *argv[]) { ... print_error(ret); return ret; } ++++ Například | void print_error(int error) { switch(error) { case ERROR_READ: fprintf(stderr, "ERROR: Reading input file\n"); break; case ERROR_MEM: fprintf(stderr, "ERROR: Memory allocation\n"); break; case ERROR_OUT: fprintf(stderr, "ERROR: Print the read input\n"); break; case ERROR_OK: default: //nothing to do break; } } ++++ 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ě rychlé 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 ./main * Proto nastavíme více, např. 12 MB. limits -v 12582912 ./main * 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 ./main < 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) ./main < 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, ++např.| ulimit -v 32768 ./main < 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) ./main < 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 zdroji. 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 k procvičení ===== * 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 položkou s hodnotou NULL, podobně jako je u textového řetězce //null character//, viz [[https://en.wikipedia.org/wiki/Null-terminated_string]].