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