Comment gérer correctement la gestion de la mémoire via mmap?

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.

Il existe plusieurs implémentations possibles pour un malloc basé sur mmap:

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; } 
  1. Allouer
    1. Itérer votre liste pour un morceau libre approprié (optimisable)
    2. Si rien n’a été trouvé, redimensionnez le dernier morceau à la taille requirejse et créez un morceau libre à la taille restante.
    3. Si vous atteignez la fin de la page, (la 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 …)
  2. Pour libérer, encore plus simplement: définissez simplement 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:

  • Vous avez une page de 4096 octets. c’est-à-dire (-16 pour les métadonnées) 4080 octets utilisables
  • Pour allouer un petit bloc, divisez simplement la page en deux morceaux de 2 048 octets et divisez à nouveau la première moitié en morceaux de 1 028 octets … jusqu’à obtenir un espace utilisable convenable (minimum de 32 octets (16 utilisable)). .
  • Chaque bloc, s’il ne s’agit pas d’une page complète, a un copain.
  • Vous vous retrouvez avec une structure arborescente comme celle-ci: comme ça
  • pour accéder à votre ami, utilisez un XOR binary entre votre pointeur et la taille de votre bloc.

La mise en oeuvre:

  1. Allouer un bloc de taille Size
    1. Obtenir le Block_size = 2^k > size + sizeof(chunk) requirejs Block_size = 2^k > size + sizeof(chunk)
    2. trouve le plus petit espace libre dans l’arborescence qui convient à block_size
    3. Si cela peut devenir plus petit, divisez-le, de manière récursive.
  2. Libérer un bloc
    1. Définir is_free à 1
    2. vérifier si votre ami est libre (taille XOR, n’oubliez pas de vérifier qu’il a la même taille que vous)
    3. s’il l’est, doublez sa taille. Recurse

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; } 
  • Depuis le début, vous avez quelques petites pages, chacune divisée en blocs de taille constante (une page de 8 octets, une de 16 octets, une de 32 octets, etc.).
  • Les “informations de liberté” de ces compartiments de données sont stockées dans des ensembles de bits (structures représentant un grand ensemble d’entrées), au début de chaque page ou dans une zone mémoire distincte.

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.