Version imprimable
Bonjour,
Je m'intéresse à la mémoire et je souhaite en apprendre davantage.
Je souhaiterais donc refaire un mini-malloc.
j'ai vu que, pour demander de la mémoire dans la zone heap, il fallait utiliser la fonction sbrk.
Ce que je comprends, c'est comment je peux demander d'allouer une zone qui fais x fois la taille d'un int par exemple ?
Les exemples ne sont pas clairs. Pouvez-vous m'aider ?
Merci d'avance.
en lisant la doc de la fonction, par exemple man sbrk.
Cela dit, pourquoi vouloir refaire malloc?
Que comptes-tu apprendre ainsi?
Tu apprendras mieux en lisant le code de malloc, plutot qu'en tentant à l'aveugle de la reconstruire.
Il existe ce qu'on appelle "le modèle de mémoire du C", qui est décrit précisément dans la norme.
Les détails techniques de comment ce modèle mémoire est réalisé par un système d'exploitation précise sur une architecture précise n'est qu'un cas particulier de mise en œuvre.
Tout d'abord, C'est un exercice que j'ai a réaliser pour mes études.
Je dois recodé un mini malloc et les seuls fonctions que j'ai d'autorisé au niveau de la mémoire sont sbrk et sbk c'est donc pour sa que je m’intéresse qu'a ces deux la.
Bien, le cadre étant maintenant posé, on peut passer à la suite:
D'après man brk, cette fonction est volontairement exclue de la norme POSIX. C'est intéressant.
Elle permet de modifier la limite supérieure du segment de données, à condition de respecter la pile et le segment de texte.
J'imagine que tu sais ce que sont les segments de mémoire. Et de là, ce que signifie une segmentation fault.
De plus, sbrk est une fonction C non système augmentant la taille du segment de données d'une valeur fixe. J'imagine qu'elle appele brk en interne.
C'est un point de départ, mais ca n'est pas encore une fonction de malloc.
malloc retourne un pointeur. Il te faut donc un moyen de choisir une adresse.
De quelle manière la choisirais-tu?
PS: J'imagine que, puisque tu l'as acceptée en t'inscrivant, tu as lu notre charte, notamment son article IV-N.
Salut,
ayant moi meme recodé malloc il y a quelques années dans le cadre de mes etudes je te conseille
de te renseigner sur les algo suivants :
- first fit (le plus simple mais le moins performant)
- Best fit
- Buddy
Contrairement a Ternel j'avais trouvé l'exercice tres interessant a l'epoque, j'avais appris beaucoup de chose.
Bon courage
Pour avoir fais l'exercice aussi, si je l'avais trouvé intéressant à l'époque, j'en retire surtout deux enseignements avec l'expérience:
- Attention aux fausses connaissances qu'on en tire
- Comprendre, c'est apprendre, mais refaire, c'est risquer.
Dans la réalité du développement, il ne faut surtout pas refaire ce qui fonctionne très bien.
malloc n'entre pas du tout dans les "fonctions bancales qui font ce qu'il faut, mais c'est un coup de chance".
Je suis parfaitement d'accord avec toi, et j'encourage vivement la compréhension du mécanisme.
Mais lire et comprendre la norme du langage sur la mémoire est encore plus important.
On est bien là à la frontière entre ce que le langage garantit (l'existence d'une pile et d'un tas, et d'un espace d'adressage des fonctions, ou des chaines de caractères), et ce dont le système dispose vraiment: de la RAM.
Bonjour;
Merci pour vos réponses.
J'ai bien lu l'article IV-N. (et la charte entière au passage)
Je ne viens pas pour qu'on me fasse mon exercice.
J'ai bien avancé et compris le fonctionnement de sbrk.
Par contre je ne vois pas comment stocké les adresses utilisées pour ensuite les libérer . je ne peux pas faire de liste chainée etc. vu que je ne peux pas mall oc à l'intérieur de mall oc.
J'ai donc pensé à faire un tableau de structure qui contiendrait les adresses (adresse de départ, adresse de fin allouée) pour chaque appel à mon mall oc lite.
Cette solution ne paraît pas optimiser et je suis obligé de définir un nombre maximum d'adresse demandable.
Tu peux quand meme te debrouiller pour faire des listes chainée sans malloc, c'est d'ailleur la base des algo first fit et best fitCitation:
Envoyé par vodkline
je pensais partir sur ce type d'algo
http://sandbox.mc.edu/~bennet/cs404/outl/buddy.html
Tres bien, buddy systeme est plus performant que best fit
Merci
Je met ce sujet en résolu.
Merci de vos conseil.
Bonsoir,
Citation:
Envoyé par vodkline
Il se fait tard et je vais essayer d’apporter quelques explications avant de répondre à la question posée. Dans les faits, il vous est possible d’allouer plus de mémoire que votre mémoire RAM en dispose; cela peut paraître farfelu, mais en réalité c’est exactement ce que font les systèmes d’exploitation GNU/Linux ou Unix tous deux utilisent une mascarade pour vous donner une illusion de mémoire infinie pour chaque processus. Cette mascarade en question s’appelle « mémoire virtuelle » (on dit processus l’environnement dans lequel le programme s’exécute et cet environnement est composé de 3 segments qui sont : un segment de données utilisateurs, un segment de données système et un segment d’instruction. Un programme quant à lui n’est rien d’autre qu'une collection d’instruction et de données conservées dans un fichier ordinaire sur votre disque dur dont, dans son noeud d’index, il est marqué comme étant un fichier exécutable et le contenu de ce fichier ordinaire marqué exécutable est organisé selon des règles de votre système d’exploitation).
Il faut donc comprendre que les processus des systèmes d’exploitation GNU/Linux et Unix disposent d’un espace d’adressage qui est un ensemble d’adresses linéaires d’une région mémoire qu’un processus peut utiliser. Cette adresse est définie par une adresse initiale et une taille dite longueur et quand vous faites un "fork", accéder à un fichier en mémoire, un appel à la fonction d’allocation mémoire "malloc", etc. le processus obtient une nouvelle région mémoire. Sur des architectures 32 bits, l’espace d’adressage est de 4 giga (soit 2^32), mais le système d’exploitation se réserve un gigaoctet. Au final, un processus aura un adressage maximum de 3 giga octets à sa disposition. Tout cet espace est découpé en segments qui ont des fonctions bien particulières à savoir;
- Un segment appelé « text » qui contient le code exécutable mais aussi les fonctions des bibliothèques partagées et ce segment s’entend jusqu’à l’adresse dans la variable "_etext"*
- Un segment appelé "data" qui est le segment des données initialisé au chargement d’un processus. Ce segment s’étend de l’adresse contenue dans la variable "_etext" jusqu’à celle contenue dans "_edata".
- Un segment de données non initialisé et des données allouées dynamiquement qui s’étendent de l’adresse contenue dans "_edata" à celle contenue dans "_end". Ce segment est appelé bss
"_etext, _edata et _end" sont des variables qui contiennent des adresses correspondantes (dans l’ordre): à la première adresse valide qui se situe au-dessus de "text". des données non initialisées, et enfin des sections non initialisées. À l’autre bout de l’espace d’adressage se trouvent d’autres données comme : les variables d’environnements appellées "env" ; la pile du processus dite communément pile des variables automatiques et appelées "stack". Le tas communément variable dynamique appelé "heap".
Quand vous allouez de la mémoire, le système ne vous réserve pas de la mémoire dans la RAM, mais vous attribuez des adresses mémoire virtuelle. Plus exactement, quand vous faites appel à la fonction d’allocation mémoire malloc (et bien entendu qui) fait appel à la fonction "brk" qui a son tour positionne la fin du segment de données. En clair, il procède au positionnement de la variable "_end" (première adresse de la section non initialisée .bss) provoquant ainsi la modification de la taille du segment "bss" . Et l’utilisation de "sbrk" ne fait qu’incrémenter l’espace de données en octet. Donc si vous invoquez "sbrk" en l’incrémentant d’une valeur entière ou le contraire vous ne faites qu’augmenter ou diminuer la taille du segment "bss" bien entendu il ne faut pas non plus comprendre que malloc fait appel systématiquement à "sbrk" c’est totalement faux. malloc ,fait appel à "sbrk" occasionnellement, car elle gère à elle seule des blocs mémoire déjà à disposition. De plus, le fait d’augmenter la taille du segment ne signifie en rien que le système exploitation va allouer de la mémoire bien au contraire, c’est quand vous allez écrire des données sur cette zone mémoire ou bloc de mémoire que le système d’exploitation va réellement vous donner de la mémoire dite réelle plus exactement, il déclenche une sorte de erreur d’accès qui donne par la suite une page mémoire réelle. Cette petite mascarade vous permet alors de réserver beaucoup plus de mémoire que le système peut en fournir sans que l’allocation mémoire avec malloc échoue on appelle cela une sur-allocation mémoire « overcommit-mémory » qui suppose qu’une application sollicite toujours plus de mémoire qu’il en a besoin et de ce fait le système accepte toutes allocations mémoire à la condition que la mémoire virtuelle du processus en question ne soit pas saturée ou qui n’excède pas la taille de la mémoire physique disponible.
Et si votre malloc échoue, c’est juste parce que vous avez essayé de dépasser la limite RLIMIT_DATA, ou que la zone mémoire sollicitée déborde sur une autre mémoire ou peut être parce que vous avez demander en une seule fois une taille de mémoire qui dépasse la capacité de la mémoire virtuelle totale. Les échecs allocation peuvent très bien déclencher un "out of memory killer" (OOM-Killer) qui est une routine de sécurité déclenchée lorsque toute la mémoire du système GNU/Linux ou Unix est saturé. Il a pour seule et unique mission de faire des investigations dans le but de trouver le processus qui est à l’origine de la saturation mémoire et de le tuer (cela à un côté bénéfique c’est une sorte de sécurité qui permet d’éviter ce qui peut être ou est une attaque par déni de service. Cependant, dans des systèmes critiques ça peut devenir très très vite un problème majeur donc désactiver OOM-Killer c’est savoir ce que l’on fait).
Comme je l'ai mentionné plus haut, quand vous allouez de la mémoire, le système ne vous réserve pas de la mémoire dans la RAM, mais vous attribuez des adresses mémoire virtuelle. Pour avoir un aperçu de façon concrète nous allons allouer 50000 blocs de 1Go chacune et ensuite nous allons tenter d’accéder à cette mémoire pour voir si on peut y écrire quelque chose et voir OOM-Killer faire son travail et dans un second cas nous allons désactiver l'OOM-Killer pour voir le comportement du système quand un processus sature la mémoire.
Avant toute chose : je ne suis pas responsable de tout dommage direct ou indirect tel qu'il soit. Tester le code de préférence sous une VM ou machine isolée configurée pour les test de ce genre.
Pour desactiver OMM-Killer il faut écrire dans le fichier overcommit-memory la valeur 2. Ce fichier se trouve généralement dans /proc/sys/vm/overcommit-acounting
Code:
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
Resultat du test:
- malloc n’a jamais renvoyé NULL
- malloc renvoie des pointeurs sur l’espace virtuel
et lors de la tentative d’initialisation OOM-killeur tue memset avec un signal SIGKILL
Pour répondre à la question posée, il vous est théoriquement possible d’allouer X en taille mémoire à condition que cette mémoire n’excède pas la taille de la mémoire virtuelle totale ou réelle. Toutefois, vous serez limité à un moment donné à la tentative d’écriture sur cette X mémoire ou bloc de Y mémoire de X.
Deuxième point : Réécrire malloc permet de comprendre certaines choses et les mécanismes de la mémoire, mais il faut savoir que malloc est beaucoup plus complexe que ça : exemple, malloc sur les systèmes BSD voire autres utilise la projection mémoire mmap pour obtenir de gros bloc mémoire indépendant et le mécanisme de mmap n’a absolument rien à voir avec sbrk. Tout de même, rien ne vous empêche de réécrire malloc ou concevoir un système de gestion mémoire minimaliste totalement indépendant de la mémoire libre. A vous de faire ce dont vous avez envie.
à bientôt.
La chose que je ne comprends pas avec brk/sbrk qui agrandissent le tas et les "implémentations perso de malloc()", c'est comment on évite ensuite les conflits avec le vrai malloc() (comment on empêche malloc() de retourner une adresse dans le tas que notre "code perso" a déjà "alloué" à ses appelants)...
En ne s'en servant pas.
Ce genre de situation intervient quand on écrit une libc (ou juste un avatar), pour un pseudo OS de découverte.
Un peu comme un Minix.
Bonjour,
Personnellement je pense qu’il n’y a pas de conflits parce que "malloc" dispose déjà d’une zone mémoire à sa disposition qu'elle gère. Deuxièmes points "malloc" fait appel occasionnellement à "sbrk" de plus, toutes les adresses que "malloc" vous fournit ne sont pas des adresses de mémoire réel, mais virtuel, car le système ne réserve pas de la mémoire dans la RAM, mais attribue des adresses mémoire virtuelle. Sans oublié que "malloc" échouera systématiquement quand vous essayez de dépasser "RLIMIT_DATA", où que la zone mémoire sollicitée déborde sur une autre mémoire où parce que vous avez demandé en une seule fois une taille de mémoire qui dépasse la capacité de la mémoire virtuelle totale et d'ailleurs « out of memory killer" OOM-Killer est là pour vous faire un rappel a l’ordre. De mêmes "sbrk" échouera si taille de mémoire sollicitée déborde.Citation:
Envoyé par Médinoc
Non, pas comme Minix . Chez Minix ce genre de chose ne peut avoir lieu; je m’explique. Minix possède également un mécanisme de mémoire virtuelle. La mémoire virtuelle d’un processus Minix est découpée en trois parties de segments (segment contenant le code exécutable appeler text, un segment contenant les données de taille fixe appeler stack et le segment contenant les données de taille dynamique appelée data). "malloc" sur Minix va dans un premier temps utiliser une zone mémoire suffisamment grande déjà disponible quelle dispose, mais quand cette mémoire n’est pas disponible malloc fait appel « brk/sbrk » qui va alors sollicité de la mémoire dans le tas. Tout compte fait, s’il n’y a pas assez de mémoire alors "sbrk" échouera tout comme la fonction "malloc". Finalement, mêmes sur Minix il peut y avoir une telle chose Tanenbaum a tout de même pensé à la chose. Ceci dit, sur des systèmes d'exploitation exotique ou conçue dans les garages il peut y avoir une telle chose, tout de même, un concepteur de système d’exploitation du dimanche pense à une bonne gestion de la mémoire donc c’est très très rare.Citation:
Envoyé par ternel
à bientôt
Bonjour,
Sujet très intéressant :)
Ce que je ne comprends pas c'est que si malloc retourne un nombre qui représente une adresse virtuelle qui est totalement décorrélée de la mémoire physique, coment cette ligne peut fonctionner ?
=> Si pmem est un pointeur sur une adresse virtuelle qui ne correspond à rien, comment le langage C fait pour la retrouver l'adresse physique ?Code:pmem[1] = 0x10;
Citation:
Ce que je ne comprends pas c'est que si malloc retourne un nombre qui représente une adresse virtuelle qui est totalement décorrélée de la mémoire physique, coment cette ligne peut fonctionner ?Code:pmem[1] = 0x10;
Parce que tu ne fais que stocker une valeur dans une variable dont l'espace mémoire est déjà réservé. Et cela ne fonctionnera que si le tableau/pointeur pmem a une case 1 correctement allouée (soit par un malloc, soit par une déclaration genre char pmem[50].
C'est le rôle de la MMU, celle-ci convertit et contrôle l'accès à l'adresse virtuelle en adresse physique. Et sur x86, tu as une étape supplémentaire adresse virtuelle convertie en adresse linéaire, qui est analysée et convertie en adresse physique par la gestion de la segmentation.Citation:
i pmem est un pointeur sur une adresse virtuelle qui ne correspond à rien, comment le langage C fait pour la retrouver l'adresse physique ?
Si l'adresse ne correspond à rien, tu auras un segfault.
Et pour compléter ce qui a déjà été dit :
Extrait page Copy On write WikipediaCitation:
Le copy-on-write ou copie sur écriture (souvent désigné par son sigle anglais COW) est une stratégie d'optimisation utilisée en programmation informatique. L'idée fondamentale : si de multiples appelants demandent des ressources initialement impossibles à distinguer, vous pouvez leur donner des pointeurs vers la même ressource. Cette fiction peut être maintenue jusqu'à ce qu'un appelant modifie sa « copie » de la ressource. À ce moment-là, une copie privée est créée. Cela évite que le changement soit visible ailleurs. Ceci se produit de manière transparente pour les appelants. L'avantage principal est que si un appelant ne fait jamais de modifications, la copie privée n'est jamais créée.
L'utilisation principale du Copy-on-write est la mémoire virtuelle de systèmes d'exploitation. Lorsqu'un processus crée une copie de lui-même, les pages de la mémoire qui doivent être modifiées soit par le processus soit par sa copie sont marquées copy-on-write. Lorsque le processus modifie une page mémoire, le noyau du système d'exploitation intercepte l'opération et copie la page mémoire pour que les changements de la mémoire d'un processus n'affectent pas celle d'un autre.
Une autre utilisation est la fonction calloc. Elle peut être implémentée en ayant une page de mémoire vive remplie par des zéros. Quand la mémoire est allouée, les pages retournées font toutes référence à la page de zéros et sont marquées copy-on-write. De cette façon, la quantité de mémoire vive allouée pour le processus n'augmente pas tant que les données ne sont pas écrites dans le tampon retourné par calloc. Typiquement, cela n'est fait que pour les allocations mémoire importantes.
Le Copy-on-write peut être implémenté en disant à la MMU que certaines pages dans l'espace d'adresses du processus sont en lecture seule. Quand des données sont écrites dans ces pages, la MMU lève une exception qui est gérée par le noyau. Celui-ci alloue de la mémoire vive et fait que la page écrite corresponde à ce nouvel endroit de la mémoire vive.
ok merci, je comprends mieux (travaillant sur µControlleur, je n'ai jamais eu à utiliser de MMU).