Malloc mise en œuvre?

J’essaie d’implémenter malloc et free pour C, et je ne sais pas comment réutiliser la mémoire. J’ai actuellement une struct qui ressemble à ceci:

 typedef struct _mem_dictionary { void *addr; size_t size; int freed; } mem_dictionary; 

Mon malloc ressemble à ceci:

 void *malloc(size_t size) { void *return_ptr = sbrk(size); if (dictionary == NULL) dictionary = sbrk(1024 * sizeof(mem_dictionary)); dictionary[dictionary_ct].addr = return_ptr; dictionary[dictionary_ct].size = size; dictionary[dictionary_ct].freed = 1; dictionary_ct++; return return_ptr; } 

Lorsque je libère de la mémoire, je marque simplement l’adresse comme étant 0 (cela indiquerait qu’elle est libre). Dans mon malloc , j’utilisais ensuite une boucle for pour rechercher une valeur dans le tableau égale à 0 , puis allouer de la mémoire à cette adresse. Je suis un peu confus quant à la façon de mettre en œuvre cela.

Le moyen le plus simple de le faire est de conserver une liste chaînée de blocs libres. Dans malloc , si la liste n’est pas vide, vous recherchez un bloc suffisamment volumineux pour satisfaire la demande et le retournez. Si la liste est vide ou si aucun bloc de ce type ne peut être trouvé, vous appelez sbrk pour allouer de la mémoire à partir du système d’exploitation. en mode free , vous ajoutez simplement le bloc de mémoire à la liste des blocs libres. En prime, vous pouvez essayer de fusionner un bloc libéré contigu, et vous pouvez modifier la stratégie de choix du bloc à restituer (premier ajustement, meilleur ajustement, …). Vous pouvez également choisir de diviser le bloc s’il est plus grand que la demande.

Quelques exemples d’implémentation (utilisation non testée, et évidemment non thread-safe, utilisation à vos risques et périls):

 typedef struct free_block { size_t size; struct free_block* next; } free_block; static free_block free_block_list_head = { 0, 0 }; static const size_t overhead = sizeof(size_t); static const size_t align_to = 16; void* malloc(size_t size) { size = (size + sizeof(size_t) + (align_to - 1)) & ~ (align_to - 1); free_block* block = free_block_list_head.next; free_block** head = &(free_block_list_head.next); while (block != 0) { if (block->size >= size) { *head = block->next; return ((char*)block) + sizeof(size_t); } head = &(block->next); block = block->next; } block = (free_block*)sbrk(size); block->size = size; return ((char*)block) + sizeof(size_t); } void free(void* ptr) { free_block* block = (free_block*)(((char*)ptr) - sizeof(size_t)); block->next = free_block_list_head.next; free_block_list_head.next = block; } 

Remarque: (n + align_to - 1) & ~ (align_to - 1) est une astuce pour arrondir n au multiple le plus proche de align_to supérieur à n . Cela ne fonctionne que lorsque align_to est une puissance de deux et dépend de la représentation binary des nombres.

Quand align_to est une puissance de deux, il n’a qu’un jeu de bits, et donc align_to - 1 a tous les jeux de bits les plus bas (c’est-à-dire align_to est de la forme 000 … 010 … 0 et align_to - 1 est de le formulaire 000...001...1 ). Cela signifie que ~ (align_to - 1) a tout le bit haut défini et le bit bas non défini (c’est-à-dire qu’il est de la forme 111...110...0 ). Donc x & ~ (align_to - 1) mettra à zéro tous les bits bas de x et arrondira au multiple le plus proche de align_to .

Enfin, en ajoutant align_to - 1 à size , nous arrondissons au multiple d’ align_to le plus proche (à moins que la size ne soit déjà un multiple de align_to auquel cas nous voulons obtenir la size ).

Vous ne voulez pas définir le champ de size de l’entrée de dictionnaire à zéro – vous aurez besoin de ces informations pour pouvoir les réutiliser. Au lieu de cela, définissez freed=1 uniquement lorsque le bloc est libéré.

Vous ne pouvez pas fusionner des blocs adjacents car il peut y avoir eu des appels sbrk() à sbrk() , ce qui facilite les choses. Vous avez juste besoin d’une boucle for qui recherche un bloc libéré suffisamment grand:

 typedef struct _mem_dictionary { void *addr; size_t size; int freed; } mem_dictionary; void *malloc(size_t size) { void *return_ptr = NULL; int i; if (dictionary == NULL) { dictionary = sbrk(1024 * sizeof(mem_dictionary)); memset(dictionary, 0, 1024 * sizeof(mem_dictionary)); } for (i = 0; i < dictionary_ct; i++) if (dictionary[i].size >= size && dictionary[i].freed) { dictionary[i].freed = 0; return dictionary[i].addr; } return_ptr = sbrk(size); dictionary[dictionary_ct].addr = return_ptr; dictionary[dictionary_ct].size = size; dictionary[dictionary_ct].freed = 0; dictionary_ct++; return return_ptr; } void free(void *ptr) { int i; if (!dictionary) return; for (i = 0; i < dictionary_ct; i++ ) { if (dictionary[i].addr == ptr) { dictionary[i].freed = 1; return; } } } 

Ce n'est pas une bonne implémentation de malloc() . En fait, la plupart free implémentations malloc / free allouent un petit en-tête pour chaque bloc renvoyé par malloc. L'en-tête peut commencer à l'adresse huit (8) octets de moins que le pointeur renvoyé, par exemple. Dans ces octets, vous pouvez stocker un pointeur sur l'entrée mem_dictionary possédant le bloc. Ceci évite l'opération O (N) en mode free . Vous pouvez éviter le O (N) dans malloc() en implémentant une queue prioritaire de blocs libérés. Pensez à utiliser un segment binomial, avec la taille de bloc comme index.

J’emprunte du code à la réponse de Sylvain. Il semble avoir manqué de calculer la taille du free_block * ini calculer les frais généraux.

Globalement, le code fonctionne en ajoutant ce free_block en tant qu’en-tête de la mémoire allouée. 1. Lorsque l’utilisateur appelle malloc, malloc renvoie l’adresse de la charge, juste après cet en-tête. 2. Lors de l’appel de free, l’adresse du début de l’en-tête du bloc est calculée (en soustrayant la taille de l’en-tête de l’adresse du bloc) et est ajoutée au pool de blocs libres.

 typedef struct free_block { size_t size; struct free_block* next; } free_block; static free_block free_block_list_head = { 0, 0 }; // static const size_t overhead = sizeof(size_t); static const size_t align_to = 16; void* malloc(size_t size) { size = (size + sizeof(free_block) + (align_to - 1)) & ~ (align_to - 1); free_block* block = free_block_list_head.next; free_block** head = &(free_block_list_head.next); while (block != 0) { if (block->size >= size) { *head = block->next; return ((char*)block) + sizeof(free_block); } head = &(block->next); block = block->next; } block = (free_block*)sbrk(size); block->size = size; return ((char*)block) + sizeof(free_block); } void free(void* ptr) { free_block* block = (free_block*)(((char*)ptr) - sizeof(free_block )); block->next = free_block_list_head.next; free_block_list_head.next = block; }