Discussion :

[xion.luhnis]

Bonjour à tous,

actuellement, je dois m'occuper de la partie "allocation dynamique" d'un projet de compilateur, mais je n'ai aucune idée réelle de comment ça se passe, et comment on implémente cela.

A la base, je partais sur l'idée de rester sur la stack, et allouer simplement de la place quand nécessaire (genre pour traduire un alloc/alloc_array).
Mais je me suis vite rendu compte que ça deviendrait infaisable pour la simple raison que lorsque j'alloue une zone sur la stack, dans une fonction, et que la fonction finit son exécution, dans la plupart des cas, le pointeur de la stack va remonter et donc l'espace alloué sera en-dessous du pointeur de la stack, et si j'appelle de nouveau des fonctions, je dois m'assurer que je ne réécrit pas sur cet espace... et donc la stack me paraît un très mauvais choix pour l'allocation dynamique.

Ensuite, j'ai entendu parlé de "heap" un peu partout, comme si c'était la solution à l'allocation dynamique, à part que je n'ai trouvé AUCUN tutorial à propos de cette pile en x86-64/x86 sous linux.

Bien sûr, il y a aussi l'argument : utilise malloc qui fait ça, mais j'ai l'impression que ce n'est pas du tout ce que je dois faire vu que je devrais être sensé plutôt "implémenter moi-même malloc".

Et finalement, j'ai aussi vu ça et là que un certain syscall à brk :
http://www.dreamincode.net/forums/to...e-memory-heap/

Sauf que ça ne fait pas vraiment appel à la "heap" et que j'ai plutôt été aiguillé pour utiliser cette dernière par mon prof.
Avez-vous des informations sur l'allocation dynamique en x86-64 sous linux ?
Je dois avouer ne pas avoir d'intérêt à appeler des functions malloc ou autre, je suis sensé les implémenter en asm !
Sauf que ça a l'air évident pour tout le monde vu que personne n'en parle (ou c'est un grand mystère ? - j'en doute).

Merci pour votre aide

[Obsidian]

Ce n'est pas « la heap » mais plutôt « le heap » puisqu'il s'agit d'un tas ! :-) Et un tas n'est pas une pile. En fait, la pile elle-même ne sert pas à proprement parler à allouer de la mémoire. On s'en sert à ça, entre autres choses.

brk() (et sbrk()) sont des appels système UNIX qui permettent de demander au système de modifier la taille du segment de données alloué au processus courant par le système d'exploitation. Celui-ci t'octroie donc UN long segment de mémoire contiguë et c'est à toi de l'organiser correctement. L'idée générale étant de minimiser autant que possible les appels au système et surtout, de faire face à la fragmentation (j'alloue un bloc A, puis un bloc B, puis je libère le bloc A). L'inconvénient étant que, comme tu renvoies l'adresse mémoire de l'emplacement mémoire disponible à ton processus, tu ne peux pas faire le ménage en réorganisant les blocs en mémoire, surtout que cette opération a un coût en temps machine.

En fait, le problème de l'allocation de la mémoire ressemble à celui de l'allocation de l'espace disque par le système de fichiers. La mémoire en elle-même est un long segment, mais c'est à toi de tenir la comptabilité de ce qui est utilisé et de ce qui ne l'est pas.

Tout l'exercice consiste alors à choisir la bonne stratégie d'allocation, et il semblerait que l'utilisation d'un tas donne de bons résultats. Je n'ai pas été creuser plus loin.

Bon courage.

[xion.luhnis]

Ce n'est pas « la heap » mais plutôt « le heap » puisqu'il s'agit d'un tas ! :-) Et un tas n'est pas une pile. En fait, la pile elle-même ne sert pas à proprement parler à allouer de la mémoire. On s'en sert à ça, entre autres choses.

Quand tu parles de tas / pile, tu parles de la même chose ou sont-ce deux entités totalement différentes ?

Et comment accède-t-on à ce tas / la pile ?

L'appel à brk permet d'allouer de l'espace utilisable, mais est-ce le tas dont on parle ? ou bien la pile ? ou bien y a-t-il un moyen plus simple sans appel système pour y accéder ?

[Obsidian]

Tu as lu beaucoup trop vite. Toutes ces réponses sont dans mon précédent post. Relis-le en entier.

Le « tas » (heap en anglais) est une structure de données, c'est-à-dire une manière abstraite de les organiser, et qui est décrite derrière le lien que je t'ai donné. C'est en fait un arbre binaire.

Une « pile » est, elle-aussi, une structure de données. C'est plus précisément une structure LIFO (Last In First Out), dans laquelle on pose chaque donnée au dessus de la précédente, comme dans une pile d'assiettes. Et dans cette pile d'assiettes, la dernière posée est la première que tu reprends. Tu peux gérer une pile comme tu le sens, mais tous les micro-processeurs proposent depuis longtemps des instructions pour exploiter une pile, parce qu'il en ont besoin, ne serait-ce que pour empiler les adresses de retour lors d'appels à des fonctions, ou pendant les interruptions.

Le fait est que, dans tous les cas, il s'agit simplement de lire et d'écrire des données en mémoire. Tu as un seul segment pour tout caser, et c'est à toi de l'organiser. Tu peux ranger ces données dans une pile, ou dans un tas, mais dans tous les cas, tu as un seul segment de mémoire pour tout caser. À toi de définir ton « plan d'occupation des sols » et ta politique d'aménagement.

[xion.luhnis]

Ah, ok.

Donc en fait, on est plus ou moins obligé de passer par brk, le première fois avec un paramètre nul pour savoir où démarre notre segment, puis ensuite avec la taille que l'on demande pour réellement allouer de la mémoire.

Et le reste, c'est à nous de l'implémenter de la manière qu'on veut... heap/pile ou quoi que ce soit.

... il me reste donc beaucoup à faire. Mais merci beaucoup pour ton aide.

[Obsidian]

Ah, ok.

Donc en fait, on est plus ou moins obligé de passer par brk, le première fois avec un paramètre nul pour savoir où démarre notre segment, puis ensuite avec la taille que l'on demande pour réellement allouer de la mémoire.

En fait, c'est sa petite sœur sbrk() que tu vas utiliser pour cela, mais l'esprit est là?

Et le reste, c'est à nous de l'implémenter de la manière qu'on veut... heap/pile ou quoi que ce soit.

C'est ça, quoiqu'il faudra impérativement que tu réserves au moins un segment de pile, car le micro-processeur l'utilise directement.

... il me reste donc beaucoup à faire. Mais merci beaucoup pour ton aide.

À ton service.