6 - Dynamická alokace 1/2

6 - Dynamická alokace 1/2

* pro vyučující: 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 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

Ú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 <stdio.h>
#include <stdlib.h>
 
#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 <stdlib.h>
#include <stdio.h>
 
#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
1. Načte řádky.
2. 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).
3. 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 <in-long.txt; echo $?
ld-elf.so.1: /lib/libc.so.7: mmap of entire address space failed: Cannot allocate memory
1

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 <in-long.txt; echo $?
101

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 <in-long.txt; echo $?
101

Proto nastavíme více, např. 12 MB.

limits -v 12582912 ./rand <in-long.txt; echo $?
...
DEBUG: n: 5921 size: 8192
DEBUG: n: 5922 size: 8192
101

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.

Table of Contents