Warning
This page is located in archive.

6 - Dynamická alokace 1/2

* pro vyučující: 06

Cíle cvičení

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

  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

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.
courses/b0b36prp/labs/lab06.txt · Last modified: 2022/10/25 13:11 by faiglj