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.