1

Esercitazione E5MemoriaSistemi Operativi (9 CFU), CdL Informatica, A. A. 2013/2014Dipartimento di Scienze Fisiche, Informatiche e MatematicheUniversità di Modena e Reggio Emiliahttp://weblab.ing.unimo.it/people/andreolini/didattica/sistemi-operativi

2

Quote of the day(Meditate, gente, meditate...)

“Bad programmers worry about the code. Good programmers worry about data structures and their relationships. ”Linus Torvalds (1969-)ProgrammatoreAutore di Subsurface

3

ALLOCAZIONE DINAMICA - HEAP

4

Spazio di indirizzamento processo(Repetita iuvant)

A grandissime linee, lo spazio di indirizzamento lineare di ciascun processo è organizzato come in figura.Program break: puntatore alla cimadell'heap.Stack pointer: puntatore alla cima dello stack.

CodiceCodice

Dati

Heap

Stack

Programbreak

Stackpointer

Memory map

5

Allocazione mediante heap(Primitiva)

Il modo più semplice di allocare memoria in maniera dinamica consiste nell'innalzare il program break.In Linux (come in tutti i sistemi UNIX), il program break è gestibile con due chiamate di sistema:

sbrk(). brk().

6

sbrk()(Incrementa il program break e ritorna il suo valore precedente)

La chiamata di sistema sbrk() consente di incrementare e decrementare il valore attuale del program break di un offset specifico.

Si fornisce come argomento un intero (l'incremento).Viene ritornato il valore del program breakalla modifica (tutto OK) oppure -1 (errore).man sbrk per tutti i dettagli.

Esempio d'uso: sorgente sbrk.c contenuto nell'archivio E5-esempi.tar.gz.

7

Una osservazione(L'indirizzo del program break cambia sempre)

Si provi ad invocare più volte l'eseguibile sbrk. L'indirizzo del program break dovrebbe cambiare sempre. Perché?Come misura di protezione contro gli attacchi di tipo buffer overflow, il kernel implementa la tecnica di Linear Address Space Randomization (LASR).

Ad ogni esecuzione, l'indirizzo di partenza delprogram break è generato dinamicamente.

→ Un attaccante non è in grado di sapere consemplicità dove andare ad attaccare l'heap.

8

Gestione LASR(Nessuna protezione, protezione media, protezione completa)

Il supporto LASR è attivabile mediante il file:/proc/sys/kernel/randomize_va_space.

Valori possibili:0 → supporto LASR spento.1 → randomizza inizio stack, vdso, indirizzo iniziale

per le mappature (mmap).2 → 1+ randomizza indirizzo partenza heap.

9

Disattivazione LASR(Occorre essere root)

Si provi a disattivare LASR (richiede root):echo 0 | sudo tee /proc/sys/kernel/randomize_va_space

Si esegua nuovamente sbrk.Si scoprirà che l'indirizzo di partenza del program break è costante.Alla fine dell'esperimento, si riattivi LASR:echo 2 | sudo tee /proc/sys/kernel/randomize_va_space

10

brk()(Imposta il program break ad un indirizzo)

La chiamata di sistema brk() imposta il program break ad un indirizzo lineare specifico.

Si fornisce come argomento un void * all'indirizzolineare.Viene ritornato 0 (tutto OK) o -1 (errore).

Esempio d'uso: sorgente brk.c contenuto nell'archivio E5-esempi.tar.gz.

11

sbrk() vs. brk()(Un confronto fra le due chiamate di sistema)

La chiamata sbrk() è indubbiamente più versatile di brk().

→ brk() viene usata raramente nelle applicazioni.Tuttavia, brk() è usata nelle librerie di sistema come la funzione di gestione basso livello.

→ sbrk() è implementata tramite brk(). → malloc() è implementata tramite brk().

12

Esercizi (5 min.)

1.Modificare il sorgente del programma sbrk.c in modo tale da scrivere la lettera 'A' otto byte dopo il vecchio indirizzo iniziale dell'heap.

13

Soluzioni

1.Si studi il sorgente del programma sbrk_write.c, contenuto nell'archivioE5-soluzioni.tar.gz.

14

Esercizi (5 min.)

2.Modificare il sorgente del programma sbrk.c in modo tale da scrivere la lettera 'A' trentadue byte dopo il vecchio indirizzo iniziale dell'heap.

Qual è il risultato atteso?Che cosa succede in realtà?

15

Soluzioni

2.Si studi il sorgente del programma sbrk_write_offarea.c, contenuto nell'archivioE5-soluzioni.tar.gz.

Ci si aspetterebbe un “segmentation fault”, poiché si sta scrivendo fuori area.Invece, il programma esce correttamente.

16

Esercizi (5 min.)

3.Individuare l'offset minimo a partire dal quale la scrittura di un carattere provoca il segmentation fault.

Che cosa si deduce?

18

Esercizi (5 min.)4.Modificare il sorgente del programma sbrk.c

in modo tale da:allocare 16 byte mediante modifica al program break.deallocare i 16 byte appena allocati mediantemodifica al program break.scrivere la lettera 'A' 8 byte dopo il vecchio indirizzoiniziale dell'heap.

Qual è il risultato atteso?Che cosa succede in realtà?

19

Soluzioni4.Si studi il sorgente del programma sbrk_use_after_free.c, contenuto nell'archivioE5-soluzioni.tar.gz.

Ci si aspetterebbe un “segmentation fault”, poiché si sta scrivendo fuori area.Si ottiene proprio un segmentation fault.Perché?Perché la memoria non è stata sporcata prima della deallocazione non esiste un frame fisico associato.→

20

Esercizi (5 min.)5.Modificare il sorgente del programma sbrk.c

in modo tale da:allocare 16 byte mediante modifica al program break.scrivere la lettera 'A' 8 byte dopo il vecchio indirizzoiniziale dell'heap.deallocare i 16 byte appena allocati mediantemodifica al program break.scrivere la lettera 'A' 8 byte dopo il vecchio indirizzoiniziale dell'heap.

Qual è il risultato atteso?Che cosa succede in realtà?

21

Soluzioni5.Si studi il sorgente del programma sbrk_write_use_after_free.c, contenuto nell'archivio E5-soluzioni.tar.gz.

Ci si aspetterebbe un “segmentation fault”, poiché si sta scrivendo fuori area.Si ottiene proprio un segmentation fault.Perché?Perché una volta abbassato il program break, l'associazione fra indirizzi lineari più grandi ed i rispettivi frame fisici è distrutta dal kernel.

22

Scoperte(Che cosa si è imparato da questi esperimenti?)

Le chiamate brk() e sbrk() provocano allocazioni per pagine.Scrivere fuori area non implica la ricezione di un segmentation fault.Una volta liberata l'area di memoria virtuale (tramite diminuzione del program break) i frame fisici sono restituiti al kernel.

→ Se si prova a scrivere su tale area, si ottiene unsegmentation fault.

23

ALLOCAZIONE DINAMICA - MMAP

24

Allocazione mediante mappatura(Più elegante rispetto al program break)

L'allocazione dinamica di memoria può avvenire anche tramite la creazione di una mappa di memoria con le chiamate di sistema seguenti.

mmap(): crea la mappatura. munmap(): distrugge la mappatura.

La mappa può essere di due tipi.Anonima: l'area di memoria virtuale non è associata ad alcunfile. Se riferita, viene associata a frame fisici.Con nome: l'area di memoria virtuale è associata ad un file. Seriferita, comporta la lettura di una porzione di file o il suoaggiornamento su disco.

25

mmap()(Una chiamata di sistema incredibilmente versatile)

La chiamata di sistema mmap() crea una nuova mappa di memoria.Argomenti:

l'indirizzo iniziale della mappa.la lunghezza della mappa.i permessi di accesso.il tipo di mappa.la porzione di un eventuale file da mappare.

Valore di ritorno:l'indirizzo iniziale della mappa (tutto OK).il valore speciale MAP_FAILED (errore).

26

Un esempio di mappatura anonima(Non è immediato)

Il sorgente mmap_anon.c contenuto nell'archivio E5-esempi.tar.gz mostra un esempio di mappatura anonima.NOTA: si deve impostare il tipo di mappa (privata o condivisa), altrimenti mmap() ritorna EINVAL.

27

Esercizi (2 min.)

6.Modificare il sorgente del programma mmap_anon.c in modo tale da scrivere fuori dalla mappa condivisa.

Qual è il risultato atteso?Che cosa succede in realtà?

28

Soluzioni6.Si studi il sorgente del programma mmap_anon_offarea.c, contenuto nell'archivioE5-soluzioni.tar.gz.

Ci si aspetterebbe un “segmentation fault”, poiché si sta scrivendo fuori area.Invece, il programma esce correttamente.

→ La mappatura anonima provoca allocazioni per pagine, esattamente come nel caso del program break.

29

Esercizi (2 min.)7.Modificare il sorgente del programma mmap_anon.c in modo tale da:

allocare 16 byte mediante mappatura anonima.deallocare i 16 byte appena allocati mediantedistruzione della mappatura.scrivere la lettera 'A' otto byte dopo il vecchio indirizzoiniziale dell'heap.

Qual è il risultato atteso?Che cosa succede in realtà?

30

Soluzioni7.Si studi il sorgente del programma mmap_anon_use_after_free.c, contenuto nell'archivio E5-soluzioni.tar.gz.

Ci si aspetterebbe un “segmentation fault”, poiché si sta scrivendo fuori area.Si ottiene proprio un segmentation fault.Perché?Perché la memoria non è stata sporcata prima della deallocazione non esiste un frame fisico associato.→

31

Esercizi (2 min.)8.Modificare il sorgente del programma mmap_anon.c in modo tale da:

allocare 16 byte mediante mappatura anonima.scrivere la lettera 'A' 8 byte dopo il vecchio indirizzoiniziale dell'heap.deallocare i 16 byte appena allocati mediantedistruzione della mappatura.scrivere la lettera 'A' 8 byte dopo il vecchio indirizzoiniziale dell'heap.

Qual è il risultato atteso?Che cosa succede in realtà?

32

Soluzioni8.Si studi il sorgente del programma mmap_anon_write_use_after_free.c, contenuto nell'archivio E5-soluzioni.tar.gz.

Ci si aspetterebbe un “segmentation fault”, poiché si sta scrivendo fuori area.Si ottiene proprio un segmentation fault.Perché?Perché una volta distrutta la mappatura anonima, l'associazione fra indirizzi lineari più grandi ed i rispettivi frame fisici è distrutta dal kernel.

33

Una avvertenza importante(Riguardante le scritture fuori mappatura)

Attenzione a saltare troppo in avanti. Si potrebbe beccare un'altra mappatura read/write (ad esempio, di una libreria condivisa).

→ Non è detto che vediate sempre un segmentation fault!

CodiceCodice

Dati

Heap

Stack

Programbreak

Stackpointer

Memory mapUltima mappa

creata

addr+8192

Memory map

34

Scoperte(Che cosa si è imparato da questi esperimenti?)

La chiamata mmap() provoca allocazioni per pagine.Scrivere fuori area non implica la ricezione di un segmentation fault.Una volta liberata l'area di memoria virtuale (tramite distruzione della mappatura) i frame fisici sono restituiti al kernel.

→ Se si prova a scrivere su tale area, si ottiene unsegmentation fault.

35

ALLOCAZIONE DINAMICA - MALLOC

36

L'allocatore della libreria del C(Usa il program break e le mappature di memoria)

L'allocatore standard della libreria del C usa due funzioni di libreria.

malloc(): prenotazione di aree lineari di memoria.free(): restituzione di aree lineari di memoria.

Allocazioni piccole: si gestisce una lista di blocchi liberi all'interno dell'heap.Allocazioni grandi: si crea una nuova mappatura anonima.La soglia fra le due allocazioni è posta a 128KB.

37

Esempio di allocazione piccola(Gestione lista blocchi liberi nell'heap)

L'esempio malloc-small.c contenuto nell'archivio E5-esempi.tar.gz mostra l'uso di malloc() per una quantità piccola di memoria (16B). Osservazioni:

dopo la malloc() il program break cresce di 132KB.l'indirizzo iniziale dell'area è 16B dopo il vecchioprogram break.dopo la free() il program break non vienemodificato.

38

Esempio di allocazione media(Gestione lista blocchi liberi nell'heap)

L'esempio malloc-average.c contenuto nell'archivio E5-esempi.tar.gz mostra l'uso di malloc() per una quantità piccola di memoria (4KB). Osservazioni:

dopo la malloc() il program break cresce di 136KB(i 128KB di espansione iniziale, più 4KB richiesti, più4KB per uso interno).l'indirizzo iniziale dell'area è 16B dopo il vecchioprogram break.dopo la free() il program break viene abbassatodi 4KB.

39

Esempio di allocazione grande(Mappatura anonima di memoria)

L'esempio malloc-big.c contenuto nell'archivio E5-esempi.tar.gz mostra l'uso di malloc() per una quantità piccola di memoria (256KB). Osservazioni:

il program break rimane inalterato.L'l'indirizzo iniziale dell'area sembra essere dentro lazona delle mappature di memoria.

40

Lista dei blocchi liberi nell'heap(Per allocazioni <128KB)

Per allocazioni <128KB, malloc() usa l'heap e mantiene una lista doppiamente collegata di aree libere.L'invocazione di malloc() provoca, come prima cosa, la ricerca di un blocco libero sufficientemente grande nella lista.Nel caso in cui sia trovato un blocco disponibile, viene ritornato quello.

41

Il blocco di controllo(Per allocazioni <128KB)

Se nella lista non è trovato alcun blocco di memoria di dimensioni sufficienti, viene allocato un nuovo blocco di memoria.Viene allocato anche un blocco di controllo contenente informazioni di stato sulla memoria appena allocata (ad esempio, la quantità).

Informazionidi controllo

Memoria ad uso dellafunzione invocante

Indirizzo ritornatoda malloc()

Blocco dicontrollo

Memoriaallocata

16 byte

42

Restituzione del blocco alla lista(Per allocazioni <128KB)

Quando la memoria è liberata tramite free() il blocco allocato è reinserito nella lista.I primi byte del blocco (ora libero) sono usati per memorizzare i collegamenti all'elemento libero successivo e precedente.

Informazionidi controllo

Bloccolibero

Blocco dicontrollo

Memorialibera

Puntatoreal blocco

liberoprecedente

Puntatoreal blocco

liberosuccessivo

Al blocco liberoprecedente

Al blocco liberosuccessivo

43

Esercizi (5 min.)

9.Modificare il sorgente del programma malloc-small.c in modo tale da:

allocare 16 byte mediante malloc().scrivere la lettera 'A' 8 byte dopo l'indirizzo dell'area.deallocare i 16 byte appena allocati mediantefree().scrivere la lettera 'A' 8 byte dopo l'indirizzo dell'area.

Che cosa succede?

44

Soluzioni9.Si studi il sorgente del programma mmap_anon_write_use_after_free.c, contenuto nell'archivio E5-soluzioni.tar.gz.

Ci si aspetterebbe un “segmentation fault”, poiché si sta scrivendo fuori area.Si ottiene proprio un segmentation fault.Perché?Perché una volta distrutta la mappatura anonima, l'associazione fra indirizzi lineari più grandi ed i rispettivi frame fisici è distrutta dal kernel.

45

MISURAZIONE

46

Misurazione della memoria libera(Quanta memoria è usata?)

Il comando free mostra informazioni sulla memoria a disposizione e sulla sua occupazione.

man free per tutti i dettagli.Opzioni utili.

-h: stampa le dimensioni in formato “humanreadable”.-s 1: aggiorna le statistiche ogni secondo.

Esempio d'uso: free -h -s 1

47

I campi “buffers” e “cached”(Dove è spesa la memoria usata?)

Campo buffers.Misura il consumo dovuto al buffering dei blocchinella page cache.

Campo cached.Misura il consumo dovuto all'uso degli oggetti SLAB.

48

Distruzione delle cache del kernel(Pessima per le prestazioni, ottima dal punto di vista didattico)

Linux mette a disposizione un file per l'attivazione del meccanismo di distruzione delle cache del kernel:

/proc/sys/vm/drop_caches.Valori possibili:

0 → non tocca le cache.1 → distrugge la page cache.2 → distrugge la dentry cache e la inode cache.3 1+2.→

49

Un piccolo esperimento(L'avrete probabilmente intuito)

Si provi ad annientare tutte le cache (richiede i diritti di root):

echo 3 | sudo tee /proc/sys/vm/drop_cachesLe prestazioni della macchina dovrebbero calare nettamente.

50

Esercizi (2 min.)

10.Distruggere tutte le cache, se possibile.Eseguire il seguente comando:

ls -lR /In un altro terminale, monitorare il consumo della memoria “cached” e “buffers”.Chi aumenta? Perché?Interrompete ls ed eseguitelo di nuovo.Chi aumenta? Perché?

51

Soluzioni10.Alla prima esecuzione di ls si dovrebbe

vedere un aumento repentino di “buffers” ed unaumento più lento di “cached”.→ Il kernel legge nuovamente da disco tutti i blocchi contenenti gli inode.

→ Le letture avvengono con dei readahead; sileggono una marea di blocchi.

→ Per ogni file toccato, si creano alcunestrutture dati di gestione (cache di oggetti).

Alla seconda esecuzione, i blocchi sono in page cache e sono create solo le strutture.

52

Esercizi (2 min.)

11.Distruggere tutte le cache, se possibile.Eseguire il seguente comando:

sudo dd if=/dev/sda of=/dev/nullIn un altro terminale, monitorare il consumo della memoria “cached” e “buffers”.Chi aumenta? Perché?Interrompete dd ed eseguitelo di nuovo.Chi aumenta? Perché?

53

Soluzioni11. Alla prima esecuzione di dd si dovrebbe

vedere un aumento repentino di “buffers” ed unaumento più lento di “cached”.→ Il kernel legge nuovamente da disco tutti i blocchi del file.→ Per ogni buffer logico letto il kernel crea

alcune strutture dati di gestione (cache dioggetti).

Alla seconda esecuzione, i blocchi sono in page cache e non sono create strutture di gestione.

54

Esercizi (5 min.)

12.Riuscite a creare un programma che modifichi il solo campo “cached”?

55

Soluzioni

12. Si possono leggere di continuo i metadati di un file.while true; do stat file; done

56

Misurazione del demand paging(Quante risorse sta consumando?)

Il comando vmstat fornisce informazioni specifiche sulle prestazioni del gestore della memoria virtuale.

swpd, free, buff, cache: già visti con free.bi, bo: blocchi trasferiti da e verso il disco(attività di disco legata alla paginazione).si, so: swap-in, swap-out (paginazione dovuta alloswapping).r, b: processi in stato di esecuzione o di attesa di I/O(ingorgo dovuto a sovraccarico di CPU e/o disco).us, sy, ni, wa: consumo risorse CPU.

57

Misurazione dei page fault(Quanto è intensa l'attività di paginazione?)

Il comando sar fornisce informazioni specifiche sull'attività di page fault.

sar -B 1: misura l'attività di page fault ognisecondo.

Campi interessanti.majflt/s: numero di major fault al secondo.fault/s: numero di major+minor fault al secondo.

58

Esercizi (5 min.)

13.Distruggere tutte le cache, se possibile.Eseguire il seguente comando:

lowriterIn un altro terminale, monitorare l'attività di paginazione.Quali fault si riscontrano all'inizio?

59

Soluzioni

13. Si riscontrano major fault per la lettura del programma e delle librerie condivise da disco.