Le programme suivant affiche l'adresse où est stockée une variable locale de type entier :

#include <stdio.h>
int main() {
  int i = 0;
  printf("@i = %18p\n", (void*)&i);
  return 0;
}

1. Vérifiez que les allocations sur la pile (variables locales) se font bien en allant vers les adresses basses.

   Attention, le compilateur peut changer l'ordre des variables dans un même bloc. Pour voir l'évolution des adresses de la pile, il est nécessaire de créer des blocs imbriqués :

   • soit à la main avec des accolades (for(...){...}),

   • soit avec des appels de fonctions.

2. Les adresses affichées par le programme sont elles des adresses virtuelles ou des adresses physiques ?

$ setarch $(uname -m) -R bash

1. Où sont stockées les variables globales : plutôt aux adresses hautes, ou plutôt aux adresses basses ?

2. Les variables globales sont séparées en deux parties : les variables initialisées (segment data), et les variables non-initialisées (segment BSS). Où se trouvent ces deux parties dans la mémoire ?

N'oubliez pas de donner un programme C pour justifier votre réponse.

Remarque : la commande

$ size FILE

affiche la taille des segments text, data et BSS d'un exécutable. (Elle affiche aussi la taille totale, en décimal et hexadécimal.)

Qu'affiche le programme suivant ?

#include <stdio.h>
#include <stdlib.h>

typedef void* address_t;

int main() {
  address_t *x;

  x = malloc(sizeof(address_t));
  *x = (void*)3735928559;

  printf(" x = %p\n", (address_t)x);
  printf("*x = %p\n", (address_t)*x);
  printf("&x = %p\n", (address_t)&x);
}

Expliquez précisément le résultat observé.

Faites un schéma récapitulatif (en ASCII art dans un fichier question4.txt) des zones mémoires et de leur utilisation. Les zones suivantes devront apparaitre :

• pile

• tas

• segment text

• segment data

• segment bss

et les information suivantes également

• code du programme,

• variables globales initialisées,

• variables globales non initialisées,

• variables locales statiques (static int i;),

• variables locales,

• tableaux statiques (int tab[SIZE];),

• tableaux dynamiques (int *t = malloc(size*sizeof(int));),

• arguments des fonctions.

Pendant le développement, il sera utile de pouvoir afficher la liste des zones allouées.

Complétez la fonction suivante dans le fichiers tinygc.c, qui fait cet affichage.

// display a visual representation of a list
void print_list(cell_t *list) {
    int index = 0;
    fprintf(stderr, "  +-------+--------------+----------+------+\n");
    fprintf(stderr, "  | index |   address    |   size   | used |\n");
    fprintf(stderr, "  +-------+--------------+----------+------+\n");
    cell_t *p;
    for (???; ???; ???) {
        fprintf(stderr, "  |  %03i  |  %10p  |  %6lu  |  %c   |\n",
                        index,
                        ???,
                        ???,
                        ???);
        n++;
    }
    fprintf(stderr, "  +-------+--------------+----------+------+\n");
}

Voici un exemple de ce que ma fonction print_list affiche

$ ./tinygc
+-------+----------------------+----------+------+
| index |       address        |   size   | used |
+-------+----------------------+----------+------+
|  000  |      0x5557353b5010  |       1  |  *   |
|  001  |      0x5557353b5060  |       1  |      |
|  002  |      0x5557353b50b0  |       1  |  *   |
|  003  |      0x5557353b5510  |      20  |  *   |
+-------+----------------------+----------+------+

N'oubliez pas de tester. Vous pouvez pour ceci utiliser la fonction

void insert_BLOCKS(address_t start, size_t size);

qui insère des valeurs dans la liste (globale) BLOCKS.

Complétez la fonction GC_malloc qui appelle la fonction malloc du système et insère les informations pertinentes dans la liste BLOCKS grâce à la fonction insert_BLOCKS.

La fonction mark_region est donnée par

// mark blocks from a memory region
void mark_region(address_t start, address_t end) {
    address_t p;  // pointer to memory
    address_t v;  // value at pointer p
    for (p=start; p<end; p+=WORD_SIZE) {
        v = *p;
        mark_BLOCK(v);
    }
}

Si vous compilez ce code, le compilateur affichera un warning pour la ligne

        v = *p;                                   

Ajoutez le cast pertinent pour corriger ce problème. (Attention, seul le typage de cette ligne est incorrect : il ne faut pas modifier son contenu "calculatoire" en changeant les variables ou en ajoutant / supprimant des * ou &.)

L'appel mark_BLOCK(v) parcourt la liste de zones allouées BLOCKS et marque la zone qui contient v comme utilisée (bit de poids faible du champs flags à 1).

Complétez cette fonction.

La fonction mark_from_stack parcourt la pile pour marquer les blocs correspondants. Pour ceci, il faut appeler la fonction mark_region avec les arguments start et end appropriés.

1. La variable globale STACK_TOP contient l'adresse du haut de la pile. Elle doit être initialisé dans la fonction main.

   En vous inspirant des tests faits dans la première partie du TP (affichages d'adresses de la pile), initialisez la variable STACK_TOP de manière appropriée. (Attention, cette variable doit être alignée sur un mot. Le plus simple est d'utiliser une variable de type int pour garantir ceci...)

2. L'adresse du bas de la pile change au cours de l'exécution, au fil des déclarations de variables et d'appels de fonctions.

   Comment peut-on trouver l'adresse du bas de la pile à l'intérieur de la fonction mark_from_stack ?

   Appelez la fonction mark_region avec les bonnes valeurs de start et end.

N'oubliez pas de commenter ce que vous faites !

La fonction GC_collect (fournie) appelle la fonction mark_from_stack et libère toutes les zones non utilisées.

Vérifiez que votre ramasse miettes fonctionne correctement en ajoutant un test dans la fonction principale qui :

• fait quelques allocations avec GC_malloc,

• écrase certains pointeurs avec, par exemple, des NULL,

• appelle la fonction print_list,

• appelle la fonction GC_collect,

• appelle la fonction print_list.

Si tout fonctionne, la seconde liste devrait contenir moins de zones allouées...

On peut initialiser un tableau dynamique à deux dimensions avec

int **T = malloc(size * sizeof(int*));
for (int i=0; i<size; i++) {
  T[i] = malloc(size * sizeof(int));
}

1. Remplacez les appels à malloc par des appels à GC_malloc et regarder ce que fait GC_collect.

   Qu'en pensez vous ?

2. Proposez une solution et programmez une fonction mark_from_heap qui sera appelé depuis GC_collect pour corriger le problème.

1. À ce stade, votre ramasse miette parcourt la pile et le tas pour libérer les zones inutilisées.

   Quelle(s) autre(s) zone(s) faudrait il parcourir pour éviter de libérer une zone encore référencée ?

2. Il n'est pas très pratique d'avoir à appeler la fonction GC_collect manuellement. Proposez une solution simple pour pouvoir l'appeler automatiquement.

3. Le GC de Boehm propose une fonction GC_malloc_atomic : les zones allouées par par cette fonction sont libérées automatiquement mais ne sont pas traversées pour y rechercher des adresses.

   • Donnez un exemple d'application pour cette fonction GC_malloc_atomic.

   • Ajoutez cette fonction dans votre ramasse miettes.

4. Actuellement, tinygc.c est un programme. Transformez le en bibliothèque afin de pouvoir l'utiliser avec n'importe quel autre programme C.

   Pour ceci, il faudra écrire une fonction GC_init (avec des arguments pertinents) pour initialiser le ramasse miettes.