J’essaie d’écrire mon propre malloc
et free
implémentation free
pour apprendre, avec juste mmap
et munmap
(puisque brk
et sbrk
sont obsolètes). J’ai lu pas mal de documentation sur le sujet, mais chaque exemple que je vois utilise soit sbrk
soit ne explique pas très bien comment gérer de grandes zones de mémoire mappée.
L’idée de ce que j’essaie d’écrire est la suivante: je mappe d’abord une grande zone (c’est-à-dire 512 pages); cette zone contient toutes les atsortingbutions comsockets entre 1 et 992 octets, par incréments de 16 octets. Je ferai la même chose plus tard avec une zone de 4096 pages pour les allocations plus importantes (ou mmap directement si la taille demandée est supérieure à une page). J’ai donc besoin d’un moyen de stocker des informations sur chaque morceau que j’alloue ou que je libère.
Ma question est la suivante: comment gérer correctement ces informations?
Ma problématique est la suivante: si je crée une liste chaînée, comment puis-je allouer plus d’espace à chaque nœud? Ou dois-je le copier dans la zone cartographiée? Si oui, comment puis-je jongler entre espace de données et espace réservé? Ou est-il préférable d’utiliser un tableau de taille statique? Le problème, c’est que la taille de ma zone dépend de la taille de la page.
Séquentiel (premier ajustement, meilleur ajustement).
Idée: utilisez une liste chaînée dont le dernier morceau correspond à la taille restante de votre page.
struct chunk { size_t size; struct chunk *next; int is_free; }
size
est trop petite et la next
est NULL), mmappez simplement une nouvelle page (optimisable: générez une page personnalisée si la taille est anormale …) is_free
sur 1. Si vous le souhaitez, vous pouvez vérifier si le bloc suivant est également libre et les fusionner en un bloc plus grand (attention aux bordures de page). Avantages: facile à mettre en œuvre, sortingvial à comprendre, simple à modifier.
Inconvénients: pas très efficace (parcourir toute la liste pour trouver un bloc?), Besoin de beaucoup d’optimisation, organisation de la mémoire agitée
Copains binarys (j’aime l’arithmétique binary et la récursion)
Idée: utilisez les puissances de 2 comme unités de taille:
struct chunk { size_t size; int is_free; }
la structure ici n’a pas besoin d’une next
comme vous le verrez.
Le principe est le suivant:
La mise en oeuvre:
Size
Block_size = 2^k > size + sizeof(chunk)
requirejs Block_size = 2^k > size + sizeof(chunk)
block_size
is_free
à 1 Avantages: Extrêmement rapide et économe en mémoire, propre.
Inconvénients: compliqué, quelques cas délicats (bordures de page et taille des contacts) Nécessité de conserver une liste de vos pages
Seaux (j’ai beaucoup de temps à perdre)
C’est la seule méthode des trois que je n’ai pas essayé de mettre en œuvre moi-même, je ne peux donc parler que de la théorie:
struct bucket { size_t buck_num; //number of data segment size_t buck_size; //size of a data segment void *page; void *freeinfo; }
Par exemple, pour un compartiment de 512 octets dans des pages de 4096 octets, le jeu de bits le représentant serait un jeu de bits de 8 bits, en supposant que *freeinfo = 01001000
soit signifié que les deuxième et cinquième seaux sont libres.
Avantages: De loin le plus rapide et le plus propre sur le long terme, le plus efficace sur de nombreuses petites allocations
Inconvénients: très lourde à mettre en œuvre, assez lourde pour un petit programme, nécessite un espace mémoire séparé pour les bits.
Il existe probablement d’autres algorithmes et implémentations, mais ces trois-là sont les plus utilisés. J’espère donc que vous pourrez comprendre ce que vous voulez en faire.