Bonjour,

Voila, je ne sais pas trop pourquoi, mais hier j'en suis arrivé à me poser quelques questions au niveau de la gestion de la mémoire par le système.
Et plus précisément, à ce qui se passe lors d'un malloc() (ou calloc()) au niveau du système.

Bon, bien entendu, je sais qu'il s'agit d'une réservation d'espace mémoire à l'execution, d'un "bloc" de mémoire, sans type bien entendu au niveau système. Tout ce qui caractérise ce bloc c'est sa taille.

Dans un programme C, lorsque l'on fait :
int* p_ent = (int*) malloc( 4 * sizeof(int) );
On réserve un espace mémoire qui va accueillir des données. Cet espace mémoire fait 4 fois la taille d'un int.
(Je vais dire par la suite 4 CASES)
Bon, on se sert de cet espace mémoire comme d'un tableau, grace à "l'equivalence pointeur-tableau" par exemple :
p_ent[0] = ...
p_ent[1] = ...

Tout cela est très bien.
Maintenant ce qui m'intéresse un peu plus, c'est pourquoi lorsque je veux libérer cet espace mémoire, je peux me contenter de faire
free(p_ent).

__________________________________________________
___
| I) Comment mes free() sont gérés par le système ? |

--------------------------------------------------
---

Je veux dire, p_ent, au niveau de mon programme C, c'est un pointeur sur UN int (=sur une CASE), mais rien de dit si l'espace mémoire qu'il pointe a bien été alloué avec la taille d'UN int.
Et dans notre cas, il y a même 4 ints à la que-leu-leu dans notre mémoire.
Comment le système fait-il pour s'y retrouver ?

HYPOTHESE 1
-----------
La solution que j'ai imaginé, c'est qu'à chaque appel de malloc(), le système réserve la taille demandée, suivi d'un "en-queue", pour dire : "fin de cet espace mémoire".
Parce que sinon, il n'aurait aucun moyen lors d'un free() de savoir jusqu'où allait ce "bloc mémoire" dont "parle" p_ent.

HYPOTHESE 2 (celle qui ferait mal)
-----------------------------------
La deuxième possibilité, c'est que depuis que je code en C (un bail pourtant..), je fais mal mes free() et je laisse du bordel en mémoire.
Je me suis dis "et si lorsque tu fais free() ca détruisait uniquement ce qui est pointé par le pointeur, mais UNE case. Et si j'avais fais un malloc de 4 CASES (ints par ex), il faut peut être faire ;
-------------------------
int i; // Servira à parcourir les "CASES" de notre "BLOC" mémoire
int* p_ent = malloc(4 * sizeof(int));
//utilisation...
//Liberation
int* current_point = p_ent; // Pointe aussi au début du "bloc" (sur la première "case").
for(i=0; i<4; i++)
{
free(current_point + i); // i sert de décallage du pointeur
}
-----------------------------------
Et bien entendu, j'ai essayé ce code qui plante lamentablement.
D'un autre coté, cela me rassure : il suffit de faire free(p_ent) pour libérer tout le "BLOC" (ie toutes les cases qui composent le bloc).
Cela signifie que je faisais correctement mes free() jusqu'alors.
C'est déjà ça...
Mais cela ne m'en dit pas plus sur ce qu'il se passe derrière.
J'en reviens donc à mon hypothèse numéro une : le système doit gérer les fins de blocs par des "en-queues" à la fin de ceux-là.

__________________________________________________
__________
| II) Retour à malloc() : Où est-elle ma mémoire allouée ? |

--------------------------------------------------
----------
J'en reviens aux allocations mémoire.
J'ai l'impression qu'il s'agit en fait d'une réservation de mémoire "virtuelle", au niveau du tas associé à ce processus.
Mais immédiatement apres un malloc(), je pense que la mémoire n'est pas réellement allouée en mémoire physique.
Est-ce que je me trompe ?

Et pour que cet espace mémoire existe réellement en mémoire physique, il faut probablement faire une lecture/écriture sur ces données, qui seront rapatriées dans la RAM par blocs.

Ce qui me fait me dire tout ça, c'est qu'en lisant le man du malloc(), je suis tombé sur :
--- MAN MALLOC---------
<< BUGS
By default, Linux follows an optimistic memory allocation strategy.
This means that when malloc() returns non-NULL there is no guarantee
that the memory really is available.
[...]

-----------------------
J'ai d'abord trouvé cela inquiétant : "[...] Cela signifie que quand malloc() renvoit un pointeur non NULL, il n'y a aucune garantie que cette mémoire soit réellement disponible".
Je me suis dis "mais ce n'est pas possible, moi je teste le retour de malloc() pour voir que l'allocation n'a pas échouée. Mais si même lorsque le pointeur n'est pas NULL la mémoire peut ne pas être réellement disponible, comment écrire des applis qui marchent (toujours)?

Et puis je me suis dis que ce qu'ils voulaient certainement dire c'est que notre mémoire est allouée "dans l'espace d'adressage du processus".
Mais qu'il n'y a absolument aucune garantie que cette mémoire existe à un moment physiquement (en RAM).
Cela doit dépendre de la quantité de RAM, de la quantité de mémoire consommée par d'autres programmes, de la possibilité de swapper des processus, etc...

C'est la seule explication que j'ai pu y voir.

__________________________________________________
__________
|III) Conclusion |

--------------------------------------------------
----------

Vous l'aurez compris, je suis soucieux de bien comprendre ce qui se passe au niveau système lors des allocations mémoires et libérations, afin d'écrire des applications de qualité.

J'ai parlé des mes interrogations à des collègues (certains meme chevronnés), et tous ont eu du mal à fournir une explication cohérente.
Je sais que la liaison entre les différentes facettes de l'informatique (système, programmation, archi...) est complexe.
Et il est difficile d'avoir une vision globale.
Mais moi justement, ce qui m'intéresse par dessus tout en informatique, c'est la vision globale.
Savoir à quel niveau se situent quelles élements, et comment la liaison entre les différents niveaux est assurée.

A toi Godrik, notre ordonnanceur-fou !

PS : Ne vous foutez pas trop de ma gueule, le sujet est surement trivial pour certains, mais je me rend compte que peu de personnes peuvent y répondre avec certitude

Pour la première question c'est la réponse une qui est vrai, sauf que c'est un en tête qui est stocké (avant le pointeur que tu obtient).

Pour la deux, c'est un problème bien connu que sous linux tu ne peut pas récupérer de pointeur nulL. Si tu demande de la mémoire, tu l'obtient et à un moment, lorsqu'il n'y en a plus, le système décide de tuer un processus (selon des critères de celui qui est "nice", qui tourne depuis peu de temps, qui consomme beaucoup de mémoire, etc. voir OOM). Ça peut-être un problème si tu veux un programme qui doit avoir une mémoire cache dont tu aimerais qu'elle soit la plus grande possible sans géner le reste du système. Il n'y a pas de méthode facile de faire ça.

Par contre, je pense (mais je n'en suis pas sûr) que l'allocation de la mémoire a lieu directement lorsque tu fait un malloc, car celui-ci est une surcouche à d'autre appel système (qui eux ne vont pas réserver la mémoire), mais justement l'en tête dont on parlait tout à l'heure est écrit directement dans la mémoire (et ce genre de chose est géré au niveau des pages de mémoire (32ko généralement) qui sont allouée d'un coup. Mais un test n'est pas très compliqué à faire.

annule ce que j'ai dit sur l'en tête. Il fallait que ce soit au début pour que free sache où chercher l'information (parce que tes free sont correcte), si c'est à la fin, il ne sait pas regardé.

Mais manifestement ce n'est pas là, donc ça doit être une table au début de la page mémoire ou je ne sais où (à voir dans l'implémentation de le code de malloc).

1. saleGauss Voir le profil de saleGauss
2. Posté le 11 février 2010 à 11:23:48 Avertir un administrateur
3. Mais qu'il n'y a absolument aucune garantie que cette mémoire existe à un moment physiquement (en RAM).

Cela doit dépendre de la quantité de RAM, de la quantité de mémoire consommée par d'autres programmes, de la possibilité de swapper des processus, etc...

Non effectivement car ce genre de chose est transparent pour le programme. Lui il travaille comme si il avait la totalité de la mémoire du système à disposition mais en réalité il manipule une mémoire virtuelle.

L'OS dispose de toute une table de translation entre les adresses virtuelles utilisées par ton application et les éventuelles adresses physiques (qui sont même pas forcément 100% contiguës à ma connaissance).

Donc non, un espace que tu as fraîchement alloué n'est pas garanti d'exister dans ta RAM, il peut très bien se trouver sur disque en fait en cas de swap, tout comme physiquement une donnée peut être swappée, puis rechargée complètement ailleurs, c'est l'OS qui s'occupe de faire que l'adresse utilisée par le pointeur du programme reste cohérente.

C'est même encore pire que ça. En fait il n'est même pas garanti qu'il y ait suffisamment d'espace en RAM ou en swap sur le disque pour satisfaire la requête d'allocation dynamique. Il existe une excellente analogie de ce principe d'allocation avec le mécanisme de réservation des billets des compagnies aériennes. En effet, ces dernières vendent davantage de billets qu'il n'y a de places disponibles en pariant sur le fait que tous les passagers ne se présenteront pas au moment du départ. Sous Linux, c'est la même chose avec la mémoire quand tu demandes une allocation via un malloc, le système enregistre ta requête et t'alloues des « petits bouts » au fur et à mesure que tu vas les utiliser en pariant sur le fait que tu ne vas pas réellement utiliser ce que tu as réclamé. C'est ce qu'ils appellent une stratégie optimiste d'allocation mémoire. Ça a été conçu comme ça pour minimiser le coût de copies de processus lors de forks mais ça fiche la pagaille dans des environnement où la mémoire est restreinte (intervention de l'OOM killer qui va tuer des processus (presque) à l'aveugle pour gratter de la mémoire). À ma connaissance c'est un design propre à Linux (que je n'aime pas du tout), les autres Unix que je connais ne fonctionnent pas comme ça.
J'ai retrouvé ce post sur le sujet qui est assez rigolo et décrit assez bien (toujours via une analogie avec l'avion) l'algorithme mis en œuvre : http://lwn.net/Articles/104185/

Si la gestion du tas t'intéresse, je te conseille les liens [1] et [2] ci-dessous.
[1] est issu d'un tutoriel de développement d'OS et décrit une implémentation simpliste du tas. C'est simpliste mais les concepts restent assez proches de ceux mis en œuvre dans le dlmalloc [2] longtemps mis en œuvre dans Linux.

[1] http://www.jamesmolloy.co.uk/tutorial_html/7.-The%20Heap.html
[2] http://g.oswego.edu/dl/html/malloc.html

Oula, la gestion de la memoire. C'est quelque chose d'assez complique, il y a plein d'algo different pour eviter la fragmentation memoire et je ne sais pas exactement qu'est ce qui est utilise aujourd'hui. Mais dans l'idee ca marche comme ca:

La primitive systeme qui alloue de la memoire est brk(2) et son copain sbrk(2) qui je pense sont des fonctions posix. Mais malloc n'est pas un wrapper a brk, parceque si tu fais des petit appel a brk tu vas fragmenter la memoire de ton systeme.

Donc malloc va s'allouer un enorme buffer a l'aide de brk et va gerer cette espace memoire lui meme. Une facon simple de faire est de gerer une liste chaine de la memoire dans ce buffer.
Quand je fais mon premier malloc (10), malloc alloue 1Mo avec brk et commence par ecrire un header au debut de la memoire (void* mem (non non contractuel) ) qui doit ressembler a
struct header
{
size_t size;
enum {USED, UNUSED} status;
}
Il fixe size a 10 et status a USED. puis un deuxieme header a mem+sizeof)header)+10 ou il met size a (1Mo-2*size(header)-10) et status a UNUSED.

Lorsque tu vas faire un deuxieme appel a malloc pour allouer 30 octets, il va reparcourir "la liste chaine", il voit que le premier bloc est utilise et va donc aller au deuxieme, le deuxieme est libre et fait plus de 30 octets, il va donc le couper de la meme facon en deux parties. une USED de 30 octets et creer a la suite un espace UNUSED de 10Mo-3sizeof(header)-10-30.

Lorsque tu fais un free(foo) qui correspond au premier espace memoire, il obtient l'addresse de la structure header en faisant h = foo - sizeof(header)et passe le status du bloc memoire a UNUSED, si le bloc d'apres est UNUSED egalement, il va les fusionner.

Bon ca c'est l'idee, mais apres il y a plein d'optimisation faisable. Par exemple, tu peux stocker separement l'adresse du premier bloc UNUSED pour ne pas avoir a le chercher explicitement dans la memoire parceque ca prendrait un temps incroyable. deplus, on peut utiliser la memoire qui n'est pas utiliser pour stocker un pointeur vers le prochain bloc unused.

Il y a certainement d'autre optimisation pour eviter la fragmentation de la memoire qui va chercher a t'allouer un bloc qui est le plus proche de la taille que tu demande (best fit est meilleur que first fit. CF le probleme online bin packing ).

Finalement, au debut j'ai dit que brk alloue la memoire physique. Je ne suis pas sur que ca soit vrai dans linux. Linux utilise la politique d'allocation physique "first touch" qui fait que la memoire physique n'est associe a une addresse virtuel qu'au moment ou cette memoire est acceder. Cela est TRES utile dans les architecture NUMA (Non Uniform Memory Access) pour associe la memoire physique sur un banc memoire qui est proche du processeur qui l'accede, cela ameliore en moyenne les temps d'access memoire.

En relisant le post de sankukai, je vois que j'ai oulie quelquechose a propos de fork().

Lorsque tu fais fork(), la facon "naive" de faire serait de dupliquer toute la memoire physique du processus de facon a ce qu'il y ait deux processus qui ont chacun leur memoire propre. En pratique ce n'est pas fait comme ca, un flag est positionner sur la page memoire pour qu'elle reste partage entre les deux processus tant qu'elle n'est pas change.

Quand la page memoire va etre acceder en ecriture, linux copie cette page ailleurs en memoire et va changer les flag des pages memoire pour que tout se passe bien. Cela permet d'avoir des appels a fork qui sont quasiment gratuit et de ne pas dupliquer toutes la memoire "comme un con" lorsque le prochain appel systeme apres fork est exec (qui va flusher toute la memoire). Cela permet aussi de partager le code et configuration pour les demons systemes. Enfin, c'est assez pratique.

Je n'ai aucune idee de comment ca marche ailleurs

Au sujet de l'allocation memoire first touch, je pense que les BSD ne font pas ca, il repartisse la memoire physique au moment des appels a brk. Les algos d'allocation memoire sont different des algo de malloc parceque les appels a brk ont toujours des tailles bien connu (probablement des multiples de 4Ko). Du coup ca permet d'utiliser des algos plus adapter (je pense que d'anciennes revisions de BSD utilisaient un buddy allocator)

Un peu plus sur le OOM
http://linux-mm.org/OOM_Killer

Je savais pas que ça existait pour être honnête. Bon en même temps je suis pas un gourou linux.
Ca pourrait amener à un débat intéressant sur la stratégie de gestion d'erreur à adopter. Il est clair à mon avis que très peu de programmeurs testent systématiquement les valeurs de retour de malloc, à part peut être ceux qui font de l'embarqué.

OOM_killer est quand meme un peu moche Pendant un temps, il y avait meme un hack dedans pour qu'il ne kill pas X

moche, mais en même temps assez précis. Ça œuvre pour la stabilité du système plutôt que pour le confort de chaque programme. Ensuite c'est vrai qu'il manque peut-être une autre interface à l'allocation de mémoire pour qu'un programme puisse savoir la mémoire physique qui existe réellement (et encore, seulement la RAM généralement).

Il y a eu une discussion la dessus il y a quelques jours sur la lise caml :

L'archive est accessible là, mais même si l'inscription n'est pas modéré, les archives demande d'être inscrit d'abord :
http://yquem.inria.fr/cgi-bin/mailman/listinfo/caml-list
La discussion s'appel "Being aware of memory overuse"

Il y en a une partie sur google là :
http://groups.google.com/group/fa.caml/browse_thread/thread/14b3bacbad629126/4636124a7e198be2?lnk=raot

(Tout est sur usenet sinon, sans inscription donc)

Désolé de ne pas avoir pu répondre avant.
Merci beaucoup à vous tous pour toutes ces explications.

Donc si je devais résumer,

De manière générale, sur un "système posix":
--------------------------------------------
.brk() est la primitive système qui s'occupe d'allouer de la mémoire. (l'alloue t-il physiquement en RAM, ou en mémoire virtuelle uniquement ?)
.Une couche supérieure, fournie par malloc() permet d'éviter la fragmentation mémoire. Il alloue lui d'un seul coup plus de mémoire que ce qui est demandé (si il n'a rien de dispo sous la main dans son "buffer"), pour éviter la fragmentation.
Ce "buffer" de mémoire qu'il se constitue, il le gère par une liste chainée, où figure dedans ce que Godrik appelle des Headers (que moi j'appellais en-queue).
Cet Header m'ont l'air d'être en fait des en-tête où figure la taille du "bloc contigu" qui suit et son sttatut (utilisé/inutilisé).

. En définitive, lors d'un appel à malloc(), il parcourt sa liste chainée à la recherche d'un bloc libre. Lorsqu'il en trouve qui correspond le plus à la taille demandée, il le découpe eventuellement en deux (à l'aide de Headers) et spécifie l'un comme utilisé, l'autre comme inutilisé.
Si il ne trouve rien de dispo dans son propre buffer, il doit faire un gros appel à brk() encore.
Et ainsi de suite.

Spécifique à Linux
-----------------

. Si j'ai bien compris, Linux est un optimiste qui croit que l'on (=un processus) réserve de la mémoire et que l'on ne va pas tout utiliser réellement.
Il se peut donc que la mémoire qu'il nous a "alloué" (via un malloc()) ne soit disponible nulle part (ni en RAM, ni en swap).
Dans ce cas, il fait appel à
out_of_memory() -> select_bad_process() -> badness()
du OOM_Killer, pour tuer un processus dans le but de récupérer de la mémoire.

Et j'ai un peu de mal à faire le lien entre ce qui est général (plus haut) et ce qui est spécifique à linux.
Dans un linux, quand j'appelle malloc(), il me renvoit l'adresse d'un peu de mémoire de son buffer. Mais cette mémoire peut ne pas exister réellement (spécifique à Linux). Cela voudrait dire que linux gère un buffer plus gros que ce qu'il a réellement à disposition dans son buffer qu'il s'est constitué grâce à ses propres appels à brk().

Par exemple :
Dans un systeme linux :
Le buffer de mémoire "du malloc()" :
->de l'adresse 1 à X :
Header{ X octets, USED } suivi d'emplacement dans la liste chainée qui sont utilisés.

-> de l'adresse X+1 à Y :
Header{ Y-X octets, UNUSED } suivi d'emplacement dans la liste chainée qui sont inutilisés.

Mais alors que le deuxième Header annonce Y-X octets disponibles, peut être n'y a t'il que Y-X-80 (80 arbitraire) emplacements réellement, à la suite de ce header.
Et si le processus se sert réellement de toute la mémoire qu'il a demandé, le buffer va devoir grandir (la liste chainée va s'allonger). Pour cela, il y aura des appels à brk(), et si brk() refuse d'allouer plus, il y aura un appel au schéma out_of_memory() -> select_bad_process() -> badness() suivi d'un nouvel appel à brk().

Ais-je bien compris ?

Même si j'ai un peu de mal à comprendre l'intéret de cette politique linux, je pense avoir compris comment cela est géré dans le cas général.
Je vous remercie beaucoup à tous, et particulièrement à Godrik pour ton exemple très clair.

Et pour répondre à _skip : effectivement, on peut alors se poser la question de la stratégie à adopter lorsque le systeme nous renvoit NULL après un malloc.
Déjà, cela peut-il arrivé ? (vous avez dit que sous linux un processus sera tué, et sous d'autres systeme une autre politique doit etre appliquée).
Est-il possible que le systeme réponde juste "non, tu n'aura pas ta mémoire".

Et si cela pouvait arriver, comment gérer cela au mieux ?
Car de toute facon, si tel est le cas, tout sera très dur, car le systeme doit etre dans des conditions lamentables pour ne plus pouvoir rien allouer.
Meme écrire l'erreur dans un fichier log pourrait consommer plus de mémoire que demandée...

Mais cela doit etre un vaste débat.
Dans la majorité des applis non critiques, nous feront surrement un :
perror(Plus de mémoire !");
exit(PLUS_DE_MEMOIRE);

alors que dans un systeme critique ???
Huum...

dans un système critique tu n'alloue jamais de mémoire, c'est une règle assez standard (au moins pour les logiciels embarqués). Comme ça tu n'as pas de problèmes.

Pour ta première partie, il faut bien différencier linux, qui donne des pages en mémoire à l'aide de la fonction brk. C'est là qu'il est optimiste (au sens où les pages ne sont effectivement mappé sur la mémoire que lorsque l'on écrit dedans) et qu'il peut s'ensuivre qu'il tue un processus s'il a besoin de mappé une page alors que plus aucune mémoire n'est disponible.

Au niveau du C, malloc alloue de la mémoire dans son tas. Et seulement si ce tas est plein (ou pas assez grand) il demande une nouvelle page au système. Mais comme il écrit directement dedans (les en tête de ce qu'il te renvoie donc, mais qui ne sont pas des en tête non plus (ou en tout cas pas de chaque petit bloc)) il force les page à être directement mappé en mémoire.

Cependant, tant que le système lui donne des pages (et sauf à demander plus de 2Go de mémoire sur un système 32bits (qui est capable d'en gérer plus mais pas pour un seul process) ou plus de beaucoup beaucoup sur un système 64 bits) malloc, sous linux, tu répondras toujours OK (i.e. un pointeur non-null).

Sous d'autre système effectivement, malloc à le droit de te renvoyer un pointeur NULL si le système ne lui alloue pas de page (parce que ça c'est assez courant comme manière de faire) lorsqu'il en a besoin.

Mais comme effectivement à ce moment là la situation est probablement très merdique, tu ne peut pas faire grand chose. Et pour que tout les processus ne soit pas pénalisé par un seul qui as une fuite mémoire, la technique de linux est assez bonne, d'essayer de déterminer qui est le processus qui mérite le plus de mourrir (et en pratique il y en a toujours un qui fuit, même si ce n'est pas forcément celui-la que OOM décide d'abattre).

POSIX dit que l'appel a brk agrandit la taille du segment data de la memoire. Il ne dit rien sur la memorie virtuelle/physique parceque ce n'est pas le probleme de posix.

La plupart des systemes allouent la memoire physique et la mappe a la memoire virtuel au moment de l'appel a brk, mais linux l'allouera au moment ou la memoire sera effectivement utilise.

Si on en crois ce manuel :
http://linux.die.net/man/3/malloc

C'est possible que malloc renvoie NULL, mais ce n'est pas systématique. Par contre on devrait pouvoir tester errno.

Sinon, en cas d'outofmemory, toutes les opérations faites sur la pile sont encore possible, ca laisse assez de marge de manoeuvre pour éventuellement libérer quelque chose.

Autrement j'ai profité de demander à un gars du labo de robotique comme ils faisaient. En fait ils emploient une librairie fournie par le fabricant du système embarqué qui permet à l'application d'allouer tout son heap au démarrage.
Les fonctions d'allocation sont toutes implémentées pour travailler sur ce pseudo-heap virtuel qui est alloué une fois pour toute, tel un gros array statique.
Les avantages sont assez évidents : plus aucune demande est faite à l'OS, l'application a reçu X MO, à elle de s'en servir comme elle sent, en plus il existe tout un tas de fonctions d'audit de ce pseudo-tas par exemple pour savoir combien d'octets sont occupés, idéal pour la détection de fuite ou pour anticiper un overflow.