Changes between Version 48 and Version 49 of AS6-TME-B6

Timestamp:

Mar 29, 2022, 8:32:34 PM (3 years ago)

Author:

franck

Comment:

--

AS6-TME-B6

@@ -54 +54 @@
   - Cette demande de place a pour effet de créer un bloc vide.
   - L'API de cet allocateur est `void * malloc(size_t)` et `void free(void *)`
-  - `void * malloc(size)` (politique de remplissage first fit)
+  - `void * malloc(size)` (politique de remplissage first-fit)
     - La fonction parcourt l'ensemble des blocs en commençant par le tout premier à la recherche d'un bloc vide assez grand pour contenir `size`. 
     - Si la place restante est plus petite qu'une ligne de cache, alors l'ensemble du bloc est marqué comme `plein`.
@@ -169 +169 @@
 '''
 }}}
-1. L'allocateur d'objets (nommés blocs dans le rappel de cours au-dessus) pour l'application utilise une politique ''first fit''. Qu'est-ce que cela signifie ? Quels sont les autres ? Existe-t-il une politique meilleure que les autres et pour quel critère ?
-{{{#!protected ------------------------------------------------------------------
-'''
- * L'allocation ''first fit'' signifie que l'allocateur utilise le premier bloc libre assez grand pour l'objet alloué. Ce bloc libre est coupé en deux s'il est trop grand pour produire un nouveau bloc libre, mais plus petit parce qu’amputé de la partie allouée à l'objet. 
- * On a aussi l'allocation ''next fit'' qui consiste à ne pas partir du début dans la recherche d'un bloc libre, mais de l'endroit de la dernière affectation, et la l'allocation ''best fit'' qui consiste à trouver un bloc libre de la bonne taille en premier.
+1. L'allocateur d'objets (nommés blocs dans le rappel de cours au-dessus) pour l'application utilise une politique ''first-fit''. Qu'est-ce que cela signifie ? Quels sont les autres ? Existe-t-il une politique meilleure que les autres et pour quel critère ?
+{{{#!protected ------------------------------------------------------------------
+'''
+ * L'allocation ''first-fit'' signifie que l'allocateur utilise le premier bloc libre assez grand pour l'objet alloué. Ce bloc libre est coupé en deux s'il est trop grand pour produire un nouveau bloc libre, mais plus petit parce qu’amputé de la partie allouée à l'objet. 
+ * On a aussi l'allocation ''next-fit'' qui consiste à ne pas partir du début dans la recherche d'un bloc libre, mais de l'endroit de la dernière affectation, et la l'allocation ''best-fit'' qui consiste à trouver un bloc libre de la bonne taille en premier.
  * Il en existe d'autres, leur but est d'augmenter les performances et de réduire la fragmentation.
  * Il n'y a pas de meilleures solutions, mais si on connaît la nature des besoins en termes d'allocation, on peut imaginer des mécanismes plus efficaces.
@@ -299 +299 @@
     ├── libc.c
     ├── libc.h
-    ├── memory.c             // code de l'allocateur first fit 
+    ├── memory.c             // code de l'allocateur first-fit 
     ├── memory.h             // prototype de l'allocateur
     ├── thread.c
@@ -307 +307 @@
 
 
-== B.1. Transformer l'allocateur first fit et allocateur next fit
-
-L'allocateur first fit parcourt la liste des blocs depuis le tout premier jusqu'à la fin à la recherche du premier bloc non plein assez grand pour l'objet à allouer.
-
-
-== B.2. Transformer l'allocateur first/next fit et allocateur best fit
+== B.1. Transformer l'allocateur first-fit et allocateur next-fit
+
+L'allocateur first-fit parcourt la liste des blocs depuis le tout premier jusqu'à la fin à la recherche du premier bloc non plein assez grand pour l'objet à allouer. Pour transformer ce comportement en next-fit, il suffit de se souvenir du dernier bloc alloué.
+
+Dans le code ci-après, on peut voir la fonction `try_malloc()` appelée par la fonction `malloc()`.
+On voit que les blocs sont parcouru depuis `Heap.beg` le premier bloc jusqu'au dernier `Heap.end` (qui n'est pas vraiment un bloc mais une frontière). Lisez le code et trouvez comment recommencer le prochain `try_malloc()` à partir de dernier bloc alloué. Ce n'est pas difficile, mais il faut comprendre...
+
+{{{#!c
+static size_t CacheLineSize;    // cache line size set by malloc_init()
+
+typedef struct block_info_s {   // small structure always put at the beginning of each blocks
+    unsigned full:1;            // 1 full, 0 free (means empty)
+    unsigned magic:7;           // MAGIC_HEAP : magic number to check the corruption
+    unsigned size:24;           // Number of block_info to the next block_info
+} block_info_t;
+
+static struct heap_s {          // user Heap
+    block_info_t *beg;          // Heap beginning
+    block_info_t *end;          // Heap end
+} Heap;
+
+#define LINE_FLOOR(p)   (block_info_t *)FLOOR((size_t)(p),CacheLineSize)
+#define LINE_CEIL(p)    (block_info_t *)CEIL((size_t)(p),CacheLineSize)
+#define BINFO_SZ        sizeof(block_info_t)
+
+static void* try_malloc (size_t size)
+{
+    size = CEIL (size+BINFO_SZ, CacheLineSize);             // true required size in bytes
+    size = size / sizeof (block_info_t);                    // in the heap size is in block_info_t
+    block_info_t *oldnext, *newnext, *new;
+
+    for (new = Heap.beg;                                    // from the beginning of the Heap
+        (new < Heap.end) && (new->full||(new->size<size));  // while end not reached and no space
+        new += new->size);                                  // go to next block
+
+    if (new > Heap.end) return NULL;                        // end reached without finding space
+
+    new->full = 1;                                          // space found, we put the block
+    oldnext = new + new->size;                              // next block address before the cut
+    newnext = LINE_CEIL(new+size);                          // find the new next block
+
+    if (newnext != oldnext) {                               // if we need to cut the find block
+        new->size = newnext - new;                          // new size of current block
+        new->magic = MAGIC_HEAP;                            // to try detect Heap corruption
+        newnext->size = oldnext - newnext;                  // new size of remainning space
+        newnext->full = 0;                                  // that is free space
+        newnext->magic = MAGIC_HEAP;                        // to try detect Heap corruption
+    }
+    return (void *)(new + 1);                               // the allocated block after block_info
+}
+
+void * malloc (size_t size)
+{
+    block_info_t *ptr = try_malloc (size);                  // Search for a block
+    if (ptr == NULL) {                                      // if no free space
+        merge (Heap.beg);                                   // merge all free blocks from beginning
+        ptr = try_malloc (size);                            // try again to find a block
+    }
+    return ptr;                                             // return what you have found
+}
+}}}
+
+
+== B.2. Transformer l'allocateur first-fit en allocateur best-fit
+
+Plus difficile, passer l'allocateur en best-fit. Je ne vous demande pas d'écrire le code, sauf si vous avez du temps et de la motivation. En revanche, vous pouvez réfléchir à la manière de procéder. Pour vous aidez, l'idée, c'est de ne pas toucher aux chaînages des blocs utilisés par first-fit. Il faut créer un chaînage ordonné par taille des blocs libres en utilisant l'API `list`.
 
 == B.3. Tester que les piles n'ont pas débordées
+
+
 
 == B.4. Faire en sorte que les listes d'objets libres du noyau ne retombent à 0