C allocation de mémoire dynamique - C dynamic memory allocation

L'allocation de mémoire dynamique C fait référence à la gestion manuelle de la mémoire pour l'allocation de mémoire dynamique dans le langage de programmation C via un groupe de fonctions de la bibliothèque standard C , à savoir malloc , realloc , calloc et free .

Le langage de programmation C++ inclut ces fonctions ; cependant, les opérateurs new et delete offrent des fonctionnalités similaires et sont recommandés par les auteurs de cette langue. Néanmoins, il existe plusieurs situations dans lesquelles l'utilisation new/deleten'est pas applicable, telles que le code de récupération de place ou le code sensible aux performances, et une combinaison de mallocet placement newpeut être requise à la place de l' newopérateur de niveau supérieur .

De nombreuses implémentations différentes du mécanisme d'allocation de mémoire réel, utilisé par malloc , sont disponibles. Leurs performances varient à la fois en termes de temps d'exécution et de mémoire requise.

Raisonnement

Le langage de programmation C gère la mémoire de manière statique , automatique ou dynamique . Les variables de durée statique sont allouées dans la mémoire principale, généralement avec le code exécutable du programme, et persistent pendant toute la durée de vie du programme ; les variables de durée automatique sont allouées sur la pile et vont et viennent au fur et à mesure que les fonctions sont appelées et renvoyées. Pour les variables de durée statique et de durée automatique, la taille de l'allocation doit être constante au moment de la compilation (sauf dans le cas des tableaux automatiques de longueur variable). Si la taille requise n'est pas connue avant l' exécution (par exemple, si des données de taille arbitraire sont lues à partir de l'utilisateur ou d'un fichier disque), alors l'utilisation d'objets de données de taille fixe est inadéquate.

La durée de vie de la mémoire allouée peut également être préoccupante. Ni la mémoire statique ni la mémoire de durée automatique ne sont adéquates pour toutes les situations. Les données allouées automatiquement ne peuvent pas persister sur plusieurs appels de fonction, tandis que les données statiques persistent pendant toute la durée de vie du programme, qu'elles soient nécessaires ou non. Dans de nombreuses situations, le programmeur a besoin d'une plus grande flexibilité dans la gestion de la durée de vie de la mémoire allouée.

Ces limitations sont évitées en utilisant l'allocation de mémoire dynamique , dans laquelle la mémoire est gérée de manière plus explicite (mais plus flexible), généralement en l'allouant à partir du magasin libre (appelé officieusement le « tas »), une zone de mémoire structurée à cet effet. En C, la fonction de bibliothèque mallocest utilisée pour allouer un bloc de mémoire sur le tas. Le programme accède à ce bloc de mémoire via un pointeur qui mallocretourne. Lorsque la mémoire n'est plus nécessaire, le pointeur est passé freeauquel désalloue la mémoire afin qu'elle puisse être utilisée à d'autres fins.

La description originale de C indiquait que callocet cfreeétaient dans la bibliothèque standard, mais pas malloc. Le code pour une implémentation de modèle simple d'un gestionnaire de stockage pour Unix a été fourni avec allocet en freetant que fonctions d'interface utilisateur, et en utilisant l' sbrkappel système pour demander de la mémoire au système d'exploitation. La documentation Unix 6e édition donne allocet freecomme fonctions d'allocation de mémoire de bas niveau. Les routines mallocet freedans leur forme moderne sont complètement décrites dans le manuel Unix de la 7e édition.

Certaines plates-formes fournissent des appels de bibliothèque ou de fonction intrinsèque qui permettent une allocation dynamique au moment de l'exécution à partir de la pile C plutôt que du tas (par exemple alloca()). Cette mémoire est libérée automatiquement à la fin de la fonction appelante.

Aperçu des fonctions

Les fonctions d'allocation dynamique de mémoire en C sont définies dans l'en- stdlib.htête ( en- cstdlibtête en C++).

Fonction La description
malloc alloue le nombre d'octets spécifié
realloc augmente ou diminue la taille du bloc de mémoire spécifié, en le déplaçant si nécessaire
calloc alloue le nombre d'octets spécifié et les initialise à zéro
free libère le bloc de mémoire spécifié vers le système

Différences entre malloc()etcalloc()

  • malloc()prend un seul argument (la quantité de mémoire à allouer en octets), alors qu'il a calloc()besoin de deux arguments (le nombre de variables à allouer en mémoire et la taille en octets d'une seule variable).
  • malloc()n'initialise pas la mémoire allouée, tout en calloc()garantissant que tous les octets du bloc mémoire alloué ont été initialisés à 0.
  • Sur certains systèmes d'exploitation, calloc()peut être implémenté en pointant initialement toutes les pages des adresses virtuelles de la mémoire allouée vers une page en lecture seule de tous les 0, et en allouant uniquement des pages physiques en lecture-écriture lorsque les adresses virtuelles sont écrites, une méthode appelée copy- en écriture .

Exemple d'utilisation

La création d'un tableau de dix entiers avec une portée automatique est simple en C :

int array[10];

Cependant, la taille du tableau est fixée au moment de la compilation. Si l'on souhaite allouer dynamiquement un tableau similaire, le code suivant peut être utilisé :

int *array = (int*)malloc(10 * sizeof(int));

Cela calcule le nombre d'octets que dix entiers occupent en mémoire, puis demande ce nombre d'octets mallocet attribue le résultat à un pointeur nommé array(en raison de la syntaxe C, les pointeurs et les tableaux peuvent être utilisés de manière interchangeable dans certaines situations).

Étant donné mallocqu'il ne sera peut-être pas en mesure de traiter la demande, il peut renvoyer un pointeur nul et il est recommandé de vérifier ceci :

int *array = malloc(10 * sizeof(int));
if (array == NULL) {
  fprintf(stderr, "malloc failed\n");
  return -1;
}

Lorsque le programme n'a plus besoin du tableau dynamique , il doit éventuellement appeler freepour renvoyer la mémoire qu'il occupe dans le magasin libre :

free(array);

La mémoire mise de côté par mallocn'est pas initialisée et peut contenir du cruft : les restes de données précédemment utilisées et rejetées. Après allocation avec malloc, les éléments du tableau sont des variables non initialisées . La commande callocrenverra une allocation qui a déjà été effacée :

int *array = calloc(10, sizeof(int));

Avec realloc, nous pouvons redimensionner la quantité de mémoire vers laquelle pointe un pointeur. Par exemple, si nous avons un pointeur agissant comme un tableau de size et que nous voulons le changer en un tableau de size , nous pouvons utiliser realloc.

int *arr = malloc(2 * sizeof(int));
arr[0] = 1;
arr[1] = 2;
arr = realloc(arr, 3 * sizeof(int));
arr[2] = 3;

Notez que realloc doit être supposé avoir changé l'adresse de base du bloc (c'est-à-dire s'il n'a pas réussi à étendre la taille du bloc d'origine, et a donc alloué un nouveau bloc plus grand ailleurs et y a copié l'ancien contenu). Par conséquent, tous les pointeurs vers des adresses dans le bloc d'origine ne sont également plus valides.

Type de sécurité

mallocrenvoie un pointeur vide ( void *), qui indique qu'il s'agit d'un pointeur vers une région de type de données inconnu. L'utilisation du casting est requise en C++ en raison du système de types fort, alors que ce n'est pas le cas en C. On peut "caster" (voir conversion de type ) ce pointeur vers un type spécifique :

int *ptr, *ptr2;
ptr = malloc(10 * sizeof(*ptr)); /* without a cast */
ptr2 = (int *)malloc(10 * sizeof(*ptr)); /* with a cast */

Il y a des avantages et des inconvénients à effectuer un tel casting.

Avantages du casting

  • L'inclusion du cast peut permettre à un programme ou à une fonction C de se compiler en C++.
  • La distribution permet des versions antérieures à 1989 de malloccelle qui renvoyait à l'origine un fichier char *.
  • Le transtypage peut aider le développeur à identifier les incohérences dans le dimensionnement du type si le type de pointeur de destination change, en particulier si le pointeur est déclaré loin de l' malloc()appel (bien que les compilateurs et les analyseurs statiques modernes puissent avertir d'un tel comportement sans nécessiter le transtypage).

Inconvénients du casting

  • Sous la norme C, la distribution est redondante.
  • L'ajout du cast peut masquer l'échec de l'inclusion de l'en-tête stdlib.h, dans lequel se trouve le prototype de la fonction for malloc. En l'absence de prototype pour malloc, la norme C90 exige que le compilateur C assume qu'il mallocrenvoie un fichier int. S'il n'y a pas de transtypage, C90 requiert un diagnostic lorsque cet entier est affecté au pointeur ; cependant, avec le casting, ce diagnostic ne serait pas produit, cachant un bug. Sur certaines architectures et modèles de données (comme LP64 sur les systèmes 64 bits, où longet les pointeurs sont 64 bits et int32 bits), cette erreur peut en fait entraîner un comportement indéfini, car la déclaration implicite mallocrenvoie une valeur 32 bits alors que la fonction réellement définie renvoie une valeur de 64 bits. Selon les conventions d'appel et la disposition de la mémoire, cela peut entraîner un écrasement de la pile . Ce problème est moins susceptible de passer inaperçu dans les compilateurs modernes, car C99 n'autorise pas les déclarations implicites, le compilateur doit donc produire un diagnostic même s'il suppose un intretour.
  • Si le type du pointeur est modifié lors de sa déclaration, il peut également être nécessaire de modifier toutes les lignes où mallocest appelé et transtypé.

Erreurs courantes

L'utilisation inappropriée de l'allocation dynamique de mémoire peut fréquemment être une source de bogues. Ceux-ci peuvent inclure des bogues de sécurité ou des plantages de programmes, le plus souvent dus à des erreurs de segmentation .

Les erreurs les plus courantes sont les suivantes :

Ne pas vérifier les échecs d'allocation
L'allocation de mémoire n'est pas garantie de réussir et peut à la place retourner un pointeur null. L'utilisation de la valeur renvoyée, sans vérifier si l'allocation est réussie, invoque un comportement indéfini . Cela conduit généralement à un plantage (en raison de l'erreur de segmentation résultante sur le déréférencement du pointeur null), mais il n'y a aucune garantie qu'un plantage se produira, donc s'appuyer sur cela peut également entraîner des problèmes.
Fuites de mémoire
L'échec de désallouer la mémoire à l'aide de freeconduit à l'accumulation de mémoire non réutilisable, qui n'est plus utilisée par le programme. Cela gaspille des ressources mémoire et peut entraîner des échecs d'allocation lorsque ces ressources sont épuisées.
Erreurs logiques
Toutes les allocations doivent suivre le même modèle : allocation à l'aide de malloc, utilisation pour stocker des données, désallocation à l'aide de free. Le non-respect de ce modèle, comme l'utilisation de la mémoire après un appel à free( pointeur dangling ) ou avant un appel à malloc( wild pointer ), appeler freedeux fois ("double free"), etc., provoque généralement une erreur de segmentation et entraîne un plantage du programme. Ces erreurs peuvent être transitoires et difficiles à déboguer - par exemple, la mémoire libérée n'est généralement pas immédiatement récupérée par le système d'exploitation, et ainsi les pointeurs pendants peuvent persister pendant un certain temps et sembler fonctionner.

De plus, en tant qu'interface qui précède la normalisation ANSI C, mallocet ses fonctions associées ont des comportements qui ont été intentionnellement laissés à la mise en œuvre de définir eux-mêmes. L'un d'eux est l'allocation de longueur zéro, qui pose davantage de problèmes realloccar il est plus courant de redimensionner à zéro. Bien que POSIX et la spécification Single Unix nécessitent une gestion appropriée des allocations de taille 0 en retournant NULLou en quelque chose d'autre qui peut être libéré en toute sécurité, toutes les plates-formes ne sont pas tenues de respecter ces règles. Parmi les nombreuses erreurs doubles qu'il a entraînées, le RCE WhatsApp 2019 était particulièrement important. Un moyen d'encapsuler ces fonctions pour les rendre plus sûres consiste simplement à vérifier les allocations de taille 0 et à les transformer en celles de taille 1. (Le retour NULLa ses propres problèmes : cela indique autrement un échec de mémoire insuffisante. realloccela aurait signalé que la mémoire d'origine n'a pas été déplacée et libérée, ce qui encore une fois n'est pas le cas pour la taille 0, conduisant au double-libre.)

Implémentations

La mise en œuvre de la gestion de la mémoire dépend fortement du système d'exploitation et de l'architecture. Certains systèmes d'exploitation fournissent un répartiteur pour malloc, tandis que d'autres fournissent des fonctions pour contrôler certaines régions de données. Le même allocateur de mémoire dynamique est souvent utilisé pour implémenter à la fois mallocet l'opérateur newen C++ .

Basé sur le tas

La mise en œuvre de l'allocateur se fait généralement à l'aide du tas ou du segment de données . L'allocateur agrandira et contractera généralement le tas pour répondre aux demandes d'allocation.

La méthode du tas souffre de quelques défauts inhérents, provenant entièrement de la fragmentation . Comme toute méthode d'allocation de mémoire, le tas deviendra fragmenté ; c'est-à-dire qu'il y aura des sections de mémoire utilisée et inutilisée dans l'espace alloué sur le tas. Un bon allocator tentera de trouver une zone inutilisée de mémoire déjà allouée à utiliser avant de recourir à l'expansion du tas. Le problème majeur avec cette méthode est que le tas n'a que deux attributs significatifs : la base, ou le début du tas dans l'espace mémoire virtuel ; et la longueur, ou sa taille. Le tas nécessite suffisamment de mémoire système pour remplir toute sa longueur et sa base ne peut jamais changer. Ainsi, toutes les grandes zones de mémoire inutilisées sont gaspillées. Le tas peut rester "bloqué" dans cette position s'il existe un petit segment utilisé à la fin du tas, ce qui pourrait gaspiller n'importe quelle quantité d'espace d'adressage. Sur les schémas d'allocation de mémoire paresseux, tels que ceux que l'on trouve souvent dans le système d'exploitation Linux, un grand tas ne réserve pas nécessairement la mémoire système équivalente ; il ne le fera qu'à la première écriture (les lectures de pages mémoire non mappées renvoient zéro). La granularité de ceci dépend de la taille de la page.

dlmalloc et ptmalloc

Doug Lea a développé le domaine public dlmalloc ("Doug Lea's Malloc") en tant qu'allocateur à usage général, à partir de 1987. La bibliothèque GNU C (glibc) est dérivée du ptmalloc de Wolfram Gloger ("pthreads malloc"), un fork de dlmalloc avec des améliorations liées au threading. En novembre 2019, la dernière version de dlmalloc est la version 2.8.6 d'août 2012.

dlmalloc est un répartiteur de balises de limite. La mémoire sur le tas est allouée en tant que "morceaux", une structure de données alignée sur 8 octets qui contient un en-tête et une mémoire utilisable. La mémoire allouée contient une surcharge de 8 ou 16 octets pour la taille du morceau et des indicateurs d'utilisation (similaire à un vecteur de dope ). Les morceaux non alloués stockent également des pointeurs vers d'autres morceaux libres dans la zone d'espace utilisable, ce qui fait que la taille de morceau minimale est de 16 octets sur les systèmes 32 bits et de 24/32 (selon l'alignement) octets sur les systèmes 64 bits.

La mémoire non allouée est regroupée en " bacs " de tailles similaires, implémentés en utilisant une liste de morceaux à double liaison (avec des pointeurs stockés dans l'espace non alloué à l'intérieur du morceau). Les bacs sont triés par taille en trois classes :

  • Pour les requêtes inférieures à 256 octets (une requête « smallbin »), un simple répartiteur à deux puissances est utilisé. S'il n'y a pas de blocs libres dans ce bac, un bloc du prochain bac le plus élevé est divisé en deux.
  • Pour les requêtes de 256 octets ou plus mais en dessous du seuil mmap , dlmalloc depuis la version 2.8.0 utilise un algorithme de trie au niveau du bit ("treebin"). S'il n'y a plus d'espace libre pour satisfaire la requête, dlmalloc essaie d'augmenter la taille du tas, généralement via l' appel système brk . Cette fonctionnalité a été introduite bien après la création de ptmalloc (à partir de la v2.7.x), et par conséquent ne fait pas partie de la glibc, qui hérite de l'ancien allocator le mieux adapté.
  • Pour les requêtes supérieures au seuil mmap (une requête "largebin"), la mémoire est toujours allouée à l'aide de l' appel système mmap . Le seuil est généralement de 256 Ko. La méthode mmap évite les problèmes avec d'énormes tampons piégeant une petite allocation à la fin après leur expiration, mais alloue toujours une page entière de mémoire, qui sur de nombreuses architectures a une taille de 4096 octets.

Le développeur de jeux Adrian Stone soutient que dlmalloc, en tant qu'allocateur de balises limites, n'est pas convivial pour les systèmes de console dotés de mémoire virtuelle mais n'ayant pas de pagination à la demande . Cela est dû au fait que ses rappels de réduction et de croissance du pool (syssmalloc/systrim) ne peuvent pas être utilisés pour allouer et valider des pages individuelles de mémoire virtuelle. En l'absence de pagination à la demande, la fragmentation devient une préoccupation plus importante.

Jemalloc de FreeBSD et NetBSD

Depuis FreeBSD 7.0 et NetBSD 5.0, l'ancienne mallocimplémentation (phkmalloc) a été remplacée par jemalloc , écrit par Jason Evans. La principale raison en était le manque d'évolutivité de phkmalloc en termes de multithreading. Afin d'éviter les conflits de verrouillage, jemalloc utilise des "arènes" distinctes pour chaque CPU . Des expériences mesurant le nombre d'allocations par seconde dans une application multithread ont montré que cela le rend évolutif de manière linéaire avec le nombre de threads, tandis que pour phkmalloc et dlmalloc, les performances étaient inversement proportionnelles au nombre de threads.

malloc d'OpenBSD

L'implémentation de la mallocfonction par OpenBSD utilise mmap . Pour les requêtes de taille supérieure à une page, l'intégralité de l'allocation est récupérée à l'aide de mmap; des tailles plus petites sont attribuées à partir de pools de mémoire gérés par mallocdans un certain nombre de "pages de compartiment", également allouées avec mmap. Lors d'un appel à free, la mémoire est libérée et démappée de l' espace d'adressage du processus à l' aide de munmap. Ce système est conçu pour améliorer la sécurité en tirant parti des fonctionnalités de randomisation de la disposition de l'espace d'adressage et des pages vides implémentées dans le cadre de l' mmap appel système d'OpenBSD , et pour détecter les bogues d'utilisation après la libération, car une grande allocation de mémoire est complètement démappée une fois libérée. , une utilisation ultérieure provoque une erreur de segmentation et l'arrêt du programme.

Amasser malloc

Hoard est un allocator dont l'objectif est des performances d'allocation de mémoire évolutives. Comme l'allocateur d'OpenBSD, Hoard utilise mmapexclusivement, mais gère la mémoire en morceaux de 64 kilo-octets appelés superblocs. Le tas de Hoard est logiquement divisé en un seul tas global et un certain nombre de tas par processeur. De plus, il existe un cache local de thread qui peut contenir un nombre limité de superblocs. En allouant uniquement des superblocs sur le tas local par thread ou par processeur, et en déplaçant les superblocs pour la plupart vides vers le tas global afin qu'ils puissent être réutilisés par d'autres processeurs, Hoard maintient la fragmentation faible tout en atteignant une évolutivité presque linéaire avec le nombre de threads .

mimalloc

Un répartiteur de mémoire compact open source à usage général de Microsoft Research axé sur les performances. La bibliothèque est d'environ 11 000 lignes de code .

Malloc de mise en cache des threads (tcmalloc)

Chaque thread a un stockage local de thread pour les petites allocations. Pour les grandes allocations, mmap ou sbrk peuvent être utilisés. TCMalloc , un malloc développé par Google, a un ramasse-miettes pour le stockage local des threads morts. Le TCMalloc est considéré comme plus de deux fois plus rapide que le ptmalloc de la glibc pour les programmes multithreads.

Dans le noyau

Les noyaux du système d'exploitation doivent allouer de la mémoire tout comme les programmes d'application. mallocCependant, l' implémentation de dans un noyau diffère souvent de manière significative des implémentations utilisées par les bibliothèques C. Par exemple, les tampons mémoire peuvent avoir besoin de se conformer à des restrictions spéciales imposées par DMA , ou la fonction d'allocation de mémoire peut être appelée à partir du contexte d'interruption. Cela nécessite une mallocimplémentation étroitement intégrée au sous-système de mémoire virtuelle du noyau du système d'exploitation.

Remplacement de malloc

Parce que mallocet ses proches peuvent avoir un impact important sur les performances d'un programme, il n'est pas rare de remplacer les fonctions d'une application spécifique par des implémentations personnalisées optimisées pour les modèles d'allocation de l'application. La norme C ne fournit aucun moyen de le faire, mais les systèmes d'exploitation ont trouvé diverses façons de le faire en exploitant la liaison dynamique. Une façon consiste simplement à créer un lien dans une bibliothèque différente pour remplacer les symboles. Un autre, utilisé par Unix System V.3 , consiste à créer mallocet à utiliser freedes pointeurs qu'une application peut réinitialiser en fonctions personnalisées.

Limites de taille d'allocation

Le plus grand bloc de mémoire possible mallocpouvant être alloué dépend du système hôte, en particulier de la taille de la mémoire physique et de l'implémentation du système d'exploitation.

Théoriquement, le plus grand nombre devrait être la valeur maximale pouvant être contenue dans un size_ttype, qui est un entier non signé dépendant de l'implémentation représentant la taille d'une zone de mémoire. Dans la norme C99 et les versions ultérieures, elle est disponible en tant que SIZE_MAXconstante de <stdint.h>. Bien qu'il ne soit pas garanti par ISO C , il l'est généralement . 2^(CHAR_BIT * sizeof(size_t)) - 1

Sur les systèmes glibc, le plus grand bloc de mémoire possible mallocpouvant être alloué n'est que la moitié de cette taille, à savoir . 2^(CHAR_BIT * sizeof(ptrdiff_t) - 1) - 1

Extensions et alternatives

Les implémentations de la bibliothèque C livrées avec divers systèmes d'exploitation et compilateurs peuvent être accompagnées d'alternatives et d'extensions à l' mallocinterface standard . Parmi ceux-ci, notons :

  • alloca, qui alloue un nombre demandé d'octets sur la pile d'appels . Aucune fonction de désallocation correspondante n'existe, car généralement la mémoire est désallouée dès le retour de la fonction appelante. allocaétait présent sur les systèmes Unix dès 32/V (1978), mais son utilisation peut être problématique dans certains contextes (par exemple, embarqués). Bien qu'il soit pris en charge par de nombreux compilateurs, il ne fait pas partie de la norme ANSI-C et peut donc ne pas toujours être portable. Cela peut également entraîner des problèmes de performances mineurs : cela conduit à des cadres de pile de taille variable, de sorte que les pointeurs de pile et de cadre doivent être gérés (avec des cadres de pile de taille fixe, l'un d'entre eux est redondant). Des allocations plus importantes peuvent également augmenter le risque de comportement indéfini en raison d'un débordement de pile . C99 proposait des tableaux de longueur variable comme mécanisme d'allocation de pile alternatif - cependant, cette fonctionnalité a été reléguée au rang d'option dans la dernière norme C11 .
  • POSIX définit une fonction posix_memalignqui alloue de la mémoire avec un alignement spécifié par l'appelant. Ses allocations sont désallouées avec free, donc l'implémentation doit généralement faire partie de la bibliothèque malloc.

Voir également

Les références

Liens externes