[T09] Esercitazione del 15 maggio 2020

Istruzioni per l’esercitazione:

• Aprite il form di consegna in un browser e loggatevi con le vostre credenziali uniroma1.
• Scaricate e decomprimete sulla scrivania il codice dell’esercitazione. Vi sarà una sotto-directory separata per ciascun esercizio di progammazione. Non modificate in alcun modo i programmi di test *_main.c.
• Rinominare la directory chiamandola cognome.nome. Sulle postazioni del laboratorio sarà /home/biar/Desktop/cognome.nome/.
• È possibile consultare appunti/libri e il materiale didattico online.
• Rispondete alle domande online sul modulo di consegna.
• Finiti gli esercizi, e non più tardi della fine della giornata:
  • zippate la directory di lavoro in cognome.nome.zip (zip -r cognome.nome.zip cognome.nome/).
• Per consegnare:
  • inserite nel form di consegna come autovalutazione il punteggio di ciascuno dei test forniti (inserite zero se l’esercizio non è stato svolto, non compila, o dà errore di esecuzione).
  • fate upload del file cognome.nome.zip.

Per maggiori informazioni fate riferimento al regolamento delle esercitazioni.

Esercizio 1 (prefisso di stringa)

Tradurre in IA32 la seguente funzione is_prefix definita in E1-is-prefix/e1.c che, date due stringhe s1 e s2, verifica se la s1 è un prefisso di s2. Ad esempio ham è prefisso di hamburger, mentre hum non lo è.

e1.c

int is_prefix(const char* s1, const char* s2){
    while (*s1 && *s1++ == *s2++);
    return *s1 == 0;
}

Scrivere la soluzione nel file E1-is-prefix/e1.s. Usare il file E1-is-prefix/e1_eq.c per sviluppare la versione C equivalente e E1-is-prefix/e1_main.c come programma di prova.

Esercizio 2 (un semplice allocatore di memoria)

L’obiettivo dell’esercizio è implementare l’operazione di deallocazione di un semplice allocatore di memoria. L’operazione mymalloc è fornita e si richiede di scrivere l’operazione myfree nel file E2-free/e2.c. L’operazione deve prendere il blocco deallocato e inserirlo in testa alla lista di blocchi liberi puntata dalla variabile globale free_list come descritto nella dispensa del corso. I blocchi liberi dell’allocatore hanno una header di 4 byte che contiene la dimensione del blocco, seguita da un campo next come definito nel file e2.h:

e2.h (estratto)

#pragma pack(1)
typedef struct header_t {
    unsigned size;
    struct header_t* next;
} header_t;

Si ricorda che la direttiva del compilatore #pragma pack(1) evita l’inserimento di padding tra il campo size e il campo next, che quindi sono contigui in memoria. L’implementazione della mymalloc (che non deve essere modificata) è riportata di seguito:

e2.c

header_t* free_list = NULL;

void* mymalloc(size_t m) {                           // prende size del payload da allocare
    header_t *p, *q = NULL;
    m = ((m+3)/4)*4;                                 // arrotonda al più piccolo multiplo di 4 maggiore o uguale a m
    if (m < 8) m = 8;                                // garantisce spazio per il puntatore next
    for (p=free_list; p != NULL; q = p, p = p->next) // cerca blocco libero first-fit
        if (p->size >= m) break;
    if (p == NULL) p = sbrk(4 + m);                  // nessun blocco libero, si espande l'heap
    else                                             // toglie nodo dalla lista dei blocchi liberi
        if (q == NULL) free_list = free_list->next;
        else q->next = q->next->next;
    ((header_t*)p)->size = m;                        // size misura il blocco a meno del campo size stesso  
    return (char*)p+4;                               // restituisce puntatore al payload
}

void myfree(void* p) {                               // prende puntatore al payload
    // completare la funzione...
}

Si compili il programma con make. Se myfree è realizzata correttamente, l’output del programma di prova E2-free/e2_main.c deve essere il seguente (ovviamente gli indirizzi saranno diversi):

--- heap size: 76 byte
1   [0x10289f000][size=16  ][free]
2   [0x10289f014][size=24  ][used]
3   [0x10289f030][size=8   ][free]
4   [0x10289f03c][size=12  ][used]
=== free_list: 0x10289f000
*   [0x10289f000][size=16  ][next=0x10289f030]
*   [0x10289f030][size=8   ][next=0x0]

Se l’output è questo (a parte i valori degli indirizzi) inserire 1 nel form di consegna, e 0 altrimenti.

L’output elenca dapprima i blocchi presenti in heap e poi mostra il contenuto della lista di blocchi liberi dopo aver eseguito la seguente sequenza di operazioni:

    void* p1 = mymalloc(16);
    void* p2 = mymalloc(22);
    void* p3 = mymalloc(8);
    void* p4 = mymalloc(12);
    myfree(p1);
    myfree(p3);
    void* p5 = mymalloc(4);
    void* p6 = mymalloc(14);
    myfree(p5);
    myfree(p6);

Esercizio 3 (Domande)

Domanda 1 Quale delle seguenti affermazioni è VERA?

• A. malloc è una system call
• B. malloc alloca tutti blocchi della stessa dimensione
• C. malloc restituisce indirizzi fisici
• D. L’indirizzo passato alla free punta al payload del blocco allocato da malloc
• E. Nessuna delle precedenti

Domanda 2 Dato il seguente codice, quale tra le seguenti affermazione è VERA?

• A. Il processo figlio non entra mai nello stato zombie poiché il padre esegue la wait
• B. Il processo figlio diventa orfano non appena il processo padre termina, e viene quindi adottato (cioè diventa figlio di un altro processo) da un processo antenato (nell’albero dei processi) del processo padre
• C. Il processo figlio entra nello stato zombie dopo aver terminato la propria esecuzione e fino al momento in cui il processo padre raccoglie il suo exit status
• D. Il processo padre termina sicuramente prima del figlio in virtù della chiamata a wait
• E. Nessuna delle precedenti

Domanda 3 Dato il seguente output di valgrind, quale delle seguenti affermazioni è VERA?

• A. Il programma profilato da valgrind soffre di memory leak
• B. Il programma accede in scrittura oltre la fine di un blocco allocato con malloc
• C. Non si è verificato nessun errore durante l’esecuzione del programma
• D. Nel programma non viene mai invocata la funzione malloc
• E. Al termine dell’esecuzione del programma 20 byte sono stati allocati, ma non sono stati liberati tramite free()
• F. Nessuna delle precedenti

Domanda 4 Dato il seguente output di valgrind, quale delle seguenti affermazioni è FALSA?

• A. Valgrind segnala un errore che riguarda lo heap
• B. Valgrind segnala un errore nella funzione evaluate alla riga 11 del file sorgente main.c
• C. In tutto il programma non viene effettuata nessuna malloc/free
• D. L’errore segnalato da valgrind è causato da un’area di memoria non inizializzata
• E. la funzione evaluate è invocata direttamente dalla funzione main

Domanda 5 Dato il seguente output di valgrind, quale delle seguenti affermazioni è FALSA?

• A. Valgrind segnala un errore di tipo memory leak
• B. Il programma profilato da valgrind esegue una sola malloc
• C. Valgrind segnala che nella funzione clone (alla riga 9 del sorgente main.c) viene allocato un blocco di 13 byte tramite malloc, ma non viene mai liberato tramite free
• D. Il programma profilato da valgrind ha “Hello, world” come suo unico output sul terminale
• E. Il nome del programma profilato da valgrind è a.out

Domanda 6 Quale delle seguenti affermazioni è VERA?

• A. La frammentazione esterna si verifica a causa del padding
• B. L’allocatore della mamoria dinamica (malloc/free) non soffre di frammentazione esterna
• C. Il meccanismo di paginazione della memoria virtuale non soffre di frammentazione interna, poiché tutte le pagine hanno la stessa dimensione
• D. L’area di swap è necessaria per contrastare la frammentazione interna
• E. Nessuna delle precedenti

Soluzioni

Esercizio 1 (prefisso di stringa)

e1_eq.c

#include "e1.h"

int is_prefix(const char* s1, const char* s2){
    const char* c = s1;
    const char* d = s2;
L:; char a = *c;
    if (a == 0)
        goto E;
    char b = *d;
    c++;
    d++;
    if (a != b)
        goto E;
    goto L;
E:  a = *c;
    a = a == 0;
    return a;
}

e1.s

.globl is_prefix

is_prefix: # int is_prefix(const char* s1, const char* s2)
    pushl %ebx
    movl 8(%esp), %ecx              # const char* c = s1;
    movl 12(%esp), %edx             # const char* d = s2;
L:  movb (%ecx), %al                # char a = *c;
    testb %al, %al                  # if (a == 0)
    je E                            #     goto E;
    movb (%edx), %bl                # char b = *d;
    incl %ecx                       # c++;
    incl %edx                       # d++;
    cmpb %bl, %al                   # if (a != b)
    jne E                           #     goto E;
    jmp L                           # goto L;
E:  movb (%ecx), %al                # a = *c;
    testb %al, %al                  # a = a == 0;
    sete %al
    movsbl %al, %eax
    popl %ebx
    ret

Esercizio 2 (un semplice allocatore di memoria)

e2.c

void myfree(void* p) {
    header_t* q = (header_t*)((char*)p-4);
    q->next = free_list;
    free_list = q;
}

Esercizio 3 (Domande)

1. D. L’indirizzo passato alla free punta al payload del blocco allocato da malloc

   Spiegazione: alla funzione free occorre passare l’indirizzo restituito dalla corrispondente malloc, che punta al payload del blocco (cioè la parte effettivamente utilizzabile per i dati) e non al header del blocco (che è gestito internamente da malloc/free in modo totalmente trasparente per il programmatore).

2. C. Il processo figlio entra nello stato zombie dopo aver terminato la propria esecuzione e fino al momento in cui il processo padre raccoglie il suo exit status

   Spiegazione: quando un processo termina, il kernel libera le risorse associate, ma deve conservarne alcune, come il PCB, per permettere al processo padre di raccogliere l’exit status tramite wait/waitpid. In questo intervallo di tempo il processo entra in uno stato denominato zombie. Quando il padre raccoglie l’exit status il kernel può rilasciare tutte le risorse associate al figlio, che esce dallo stato zombie e non compare più nella lista dei processi. Se il padre termina senza raccogliere l’exit status del figlio (con wait/waitpid) il processo figlio viene adottato da un processo antenato del processo padre (storicamente init, nei sistemi moderni un discendente di init) che raccoglie l’exit status del figlio permettendo così al kernel di liberare tutte le risorse associate (questi processi vengono detti anche reaper).

3. B. Il programma accede in scrittura oltre la fine di un blocco allocato con malloc

   Spiegazione: La riga di errore di valgrind specifica “Invalid write of size 4”, cioè accesso in scrittura (di 4 byte) non valido. Tra i dettagli dell’errore troviamo “Address 0x5204054 is 0 bytes after a block of size 20 alloc'd”, cioè l’indirizzo di accesso non valido è a 0 byte di spiazzamento oltre la fine di un blocco di dimensione 20 (allocato con malloc). Quindi l’errore riguarda un accesso ai primi 4 byte oltre la fine del blocco allocato con malloc. Questo è un errore tipico che si presenta, ad esempio, quando si alloca un array di n elementi (indici da 0 a n-1) e si accede in scrittura all’elemento di indice n.

4. A. Valgrind segnala un errore che riguarda lo heap

   Spiegazione: L’unico errore segnalato da valgrind è “Conditional jump or move depends on uninitialized value(s)”. Questo errore è relativo al fatto che una qualche istruzione condizionale (corrisponedente nel sorgente C a istruzioni if, while, for, ecc.) dipende da una variabile non inizializzata. Nello HEAP SUMMARY di valgrind si vede chiaramente che non è stato allocato alcun blocco nello heap. Dunque la variabile non inizializzata è nel segmento stack o data.

5. B. Il programma profilato da valgrind esegue una sola malloc

   Spiegazione: Nello HEAP SUMMARY di valgrind si vede che sono state eseguite 2 malloc e una free.

6. E. Nessuna delle precedenti

   Spiegazione: Tutte le altre risposte sono false. Infatti:

   • La frammentazione esterna si ha quando si avrebbe spazio libero sufficiente ad accogliere una richiesta di allocazione, ma poiché i blocchi liberi sono frammentati non è possibile accoglierla (ciascun blocco libero non è sufficientemente grande da soddisfare la richiesta di allocazione). Questa non ha niente a che vedere con il padding, perciò l’affermazione A è falsa.
   • L’allocatore malloc/free soffre di frammentazione esterna. Infatti, la malloc deve poter allocare blocchi di dimensioni diverse (dunque la free può lasciare buchi di dimensioni diverse) e, per ovvie ragioni, può restituire solo blocchi contigui di memoria. Dunque anche la risposta B è falsa.
   • Il meccanismo di paginazione della memoria, poiché alloca solo blocchi di dimensione fissa, non soffre del problema della frammentazione esterna, tuttavia soffre del problema della frammentazione interna (come tutti gli allocatori che possono allocare blocchi di memoria più grandi di quelli realmente richiesti). Dunque la risposta C è falsa.
   • Infine, l’area di swap permette di allocare più memoria virtuale di quanta ne sia disponibile in memoria fisica (in RAM). Non rappresenta un mezzo per contrastare la frammentazione interna, che invece rimane indipendentemente dall’area di swap. Dunque anche la risposta D è falsa.