Lab 06 - Dynamická alokace 1/2

• Pro vyučující: 06.

1. Dekompozice programu na funkce.
2. Implementace funkčního a správného programu s ošetřením možných chybových stavů.
3. Dynamická alokace a načítání vstupu (souboru).

• Dynamická alokace paměti v C
• Smerodatna odchylka

• 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ěť.

1. 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]);

1. 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

• 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.

• 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;
}

• 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; 
}

• 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.

• 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

• Program dále můžeme rozšířit o vypsání chybové hlášky na stderr.

int main(void)
{
  ...
  print_error(ret);
  return ret;
}

• 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

• 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

• 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.

• 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.