Comment malloc () est-il implémenté en interne?

Question

Quelqu'un peut-il expliquer comment malloc() travaille en interne?

J'ai parfois fait strace program et je vois beaucoup d'appels système sbrk , faisant man sbrk parler de son utilisation dans malloc() mais pas beaucoup plus.

Answer 1

L' sbrkappel système se déplace de la "frontière" du segment de données. Cela signifie qu'il se déplace d'une frontière d'une zone dans laquelle un programme de lecture/écriture de données (laisser d'augmenter ou de réduire, autant que je sache, bien que n' malloc donne vraiment des segments de mémoire vers le noyau avec cette méthode). A côté de cela, il y a aussi mmap qui est utilisé pour les fichiers de mappage en mémoire mais est également utilisé pour allouer de la mémoire (si vous avez besoin d'allouer de la mémoire partagée, mmap est comment vous le faites).

Donc, vous avez deux moyens d'obtenir plus de mémoire du noyau: sbrk et mmap. Il existe différentes stratégies sur la façon d'organiser la mémoire que vous avez obtenu à partir du noyau.

Un naïf moyen est de partition en zones, souvent appelé "seaux", qui sont dédiés à une certaine structure de tailles. Par exemple, un malloc mise en œuvre pourrait créer des seaux de 16, 64, 256 et 1024 octets de structures. Si vous demandez malloc pour vous donner de la mémoire d'une taille donnée, il arrondit un nombre à la taille de paquet et vous donne ensuite un élément de ce seau. Si vous avez besoin d'une plus grande région malloc pourrait utiliser mmap d'allouer directement avec le noyau. Si le seau d'une certaine taille est vide malloc pourrait utiliser sbrk pour obtenir plus d'espace pour un nouveau seau.

Il existe différents malloc conçoit et il n'y a probablement pas un seul vrai moyen de mettre en œuvre malloc que vous avez besoin de faire un compromis entre la vitesse, les frais généraux et d'éviter la fragmentation de l'espace/efficacité. Par exemple, si un seau à court d'éléments d'une mise en œuvre pourrait obtenir un élément d'un plus grand seau, les diviser et ajouter le seau qui a manqué d'éléments. Ce serait tout à fait efficace de l'espace, mais ne serait pas possible avec chaque conception. Si vous venez de recevoir un autre seau via sbrk/mmap qui pourrait être plus rapide et encore plus facile, mais pas aussi efficace de l'espace. Aussi, la conception doit bien sûr prendre en compte que le "gratuit" doit faire de la place disponible à l' malloc de nouveau en quelque sorte. Vous ne vous contentez pas de la main à la mémoire sans de le réutiliser.

Si vous êtes intéressé, la OpenSER/Kamailio proxy SIP a deux malloc des implémentations (ils ont besoin de leur propre parce qu'ils font un usage intensif de la mémoire partagée et le système malloc ne prend pas en charge la mémoire partagée). Voir: https://github.com/OpenSIPS/opensips/tree/master/mem

Ensuite, vous pouvez également jeter un oeil à la GNU libc malloc mise en œuvre, mais que l'on est très compliqué, d'autant que je me souvienne.

Answer 2

De manière simpliste à malloc et free fonctionne comme ceci:

malloc permet d'accéder à un processus de tas. Le tas est une construction dans le C bibliothèque de base (généralement de la libc) qui permet des objets pour obtenir l'accès exclusif à l'espace sur le tas.

Chaque allocation sur le tas est appelé un tas de cellules. Généralement, cela se compose d'un en-tête qui contiennent des informations sur la taille de la cellule ainsi qu'un pointeur vers le prochain tas de cellules. Ce qui fait un tas efficacement une liste liée.

Lorsque l'on démarre un processus, le tas contient une seule cellule qui contient tous les tas de l'espace attribué au démarrage. Cette cellule existe sur le segment de la liste libre.

Quand on appelle la fonction malloc, la mémoire est prise du grand tas de cellules, qui est retourné par malloc. Le reste est formé dans un nouveau tas de cellules qui se compose de tout le reste de la mémoire.

Quand on libère la mémoire, le tas de cellule est ajoutée à la fin du segment de mémoire de la liste libre. Ultérieure mallocs de marche de la liste libre à la recherche d'une cellule de taille appropriée.

Comme on peut s'y attendre le tas peut être fragmenté et le gestionnaire de tas peut de temps en temps, essayez de fusionner adjacentes tas de cellules.

Quand il n'y a pas de mémoire à gauche sur la liste d'espace libre pour un souhaité, appels malloc brk ou sbrk qui sont les appels système demande plus de pages de mémoire du système d'exploitation.

Maintenant il y a un peu de modification pour optimiser les opérations segment.

• Pour les grandes allocations de mémoire (typiquement > 512 octets, le tas le gestionnaire peut aller directement à l'OS et consacrer une pleine page de mémoire.
• Le tas peut spécifier une taille minimale de l'allocation pour éviter de grandes quantités de la fragmentation.
• Le tas peut également se diviser dans des bacs à l'un pour les petits les allocations et l'autre pour les grands allocations de faire de grands allocations plus rapide.
• Il y a aussi astucieux mécanismes pour l'optimisation multi-thread allocation de tas.

Answer 3

J'ai trouvé quelques notes de cours utiles qui expliquent comment mettre en œuvre un malloc du monde réel par le biais d'expérimentation

http://web.eecs.utk.edu/~huangj/cs360/360/notes/Malloc1/lecture.html

http://web.eecs.utk.edu/~huangj/cs360/360/notes/Malloc2/lecture.html

Answer 4

Il est également important de réaliser que déplacer simplement le pointeur de rupture de programme avec brk et sbrk n'alloue pas réellement la mémoire, il configure simplement l'espace d'adressage. Sous Linux, par exemple, la mémoire sera "sauvegardée" par les pages physiques réelles lors de l'accès à cette plage d'adresses, ce qui entraînera une erreur de page et conduira éventuellement au noyau à appeler la page d'allocation pour obtenir une page de sauvegarde.