Comment malloc() est-il mis en œuvre à l'interne? [dupliquer]
cette question a déjà une réponse ici:
- comment fonctionnent malloc() et free ()? 14 réponses
est-ce que quelqu'un peut expliquer comment malloc() fonctionne en interne?
j'ai parfois fait strace program et je vois beaucoup d'appels système sbrk , faisant man sbrk parle de son utilisation dans malloc() mais pas beaucoup plus.
3 réponses
le sbrk appel système déplace la "frontière" du segment de données. Cela signifie qu'il déplace une bordure d'une zone dans laquelle un programme peut lire/écrire des données (le laisser croître ou rétrécir, bien que AFAIK no malloc donne réellement des segments de mémoire au noyau avec cette méthode). En plus de cela, il y a aussi mmap qui est utilisé pour mapper des fichiers dans la mémoire mais qui est aussi utilisé pour allouer de la mémoire (si vous avez besoin d'allouer de la mémoire partagée, mmap est la façon dont vous le faites).
donc vous avez deux méthodes pour obtenir plus de mémoire à partir du noyau: sbrk et mmap . Il existe différentes stratégies pour organiser la mémoire que vous avez du noyau.
une manière naïve est de le diviser en zones, souvent appelées" seaux", qui sont dédiés à certaines tailles de structures. Par exemple, une implémentation malloc pourrait créer des seaux pour les structures de 16, 64, 256 et 1024 octets. Si vous demandez malloc pour vous donner 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 zone plus grande malloc peut utiliser mmap pour 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 y a divers malloc conceptions et il n'y a probablement pas une seule vraie façon de mettre en œuvre malloc que vous avez besoin de faire un compromis entre la vitesse, les frais généraux et le fait d'éviter la fragmentation/l'efficacité de l'espace. 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. Cela serait assez peu encombrant, mais cela ne serait pas possible avec tous les modèles. Si vous obtenez simplement 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" libre "doit rendre l'espace disponible pour malloc encore une fois d'une manière ou d'une autre. On ne distribue pas la mémoire sans la réutiliser.
si vous êtes intéressé, le proxy OpenSER/Kamailio SIP a deux implémentations malloc (ils ont besoin de leur propre implémentation parce qu'ils utilisent beaucoup la mémoire partagée et le système malloc ne supporte pas la mémoire partagée). Voir: https://github.com/OpenSIPS/opensips/tree/master/mem
alors vous pouvez aussi jeter un oeil à la GNU libc malloc implementation , mais celle-ci est très compliquée, IIRC.
Simpliste malloc et free fonctionne comme ceci:
malloc fournit l'accès à un tas de processus. Le tas est une construction dans la bibliothèque C core (généralement libc) qui permet aux objets d'obtenir un accès exclusif à un espace sur le tas du processus.
chaque allocation sur le tas est appelé une cellule de tas. 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.
quand on démarre un processus, le tas contient une seule cellule qui contient tout l'espace tas assigné au démarrage. Cette cellule existe sur la liste libre du tas.
quand on appelle malloc, la mémoire est prise à partir de la grande cellule de tas, qui est retournée par malloc. Le reste est formé en une nouvelle cellule de tas qui se compose de tout le reste de la mémoire.
quand on libère la mémoire, la cellule de tas est ajoutée à la fin de la liste libre du tas. Les mallocs suivants parcourent la liste libre à la recherche d'une cellule de taille appropriée.
comme on peut s'y attendre, le tas peut se fragmenter et le gestionnaire du tas peut de temps en temps, essayer de fusionner les cellules contiguës du tas.
lorsqu'il n'y a plus de mémoire disponible sur la liste libre pour une allocation désirée, malloc appelle brk ou sbrk qui sont les appels système demandant plus de pages mémoire du système d'exploitation.
Now il y a quelques modifications pour optimiser les opérations du tas.
- Pour les grandes allocations de mémoire (typiquement > 512 octets, le tas le directeur 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 aussi se diviser en bacs un pour les petites allocations et un pour les plus grandes allocations pour faire plus allocations plus rapides.
- il existe également des mécanismes astucieux pour optimiser l'allocation de tas multi-filetés.
il est également important de se rendre compte que simplement déplacer le pointeur de rupture de programme autour avec brk et sbrk ne fait pas réellement allouer la mémoire, il met juste en place l'espace d'adresse. Sur Linux, par exemple, la mémoire sera "sauvegardée" par des pages physiques réelles Lorsque cette plage d'adresses est accessible, ce qui aboutira à un défaut de page, et conduira finalement au noyau appelant dans l'allocateur de page pour obtenir une page de sauvegarde.