{{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]].