Discussion :

[Emmanuel Delahaye]

Oui, j'étais en train de bloquer là-dessus.
Je bloque au niveau de la structure, je sais la déclarer, mais faire un tableau de structures, et l'utiliser, je bloque complètement (c'est le genre de trucs que j'ai jamais vraiment sû faire !).

C'est le coeur du C, alors c'est le moment de t'y mettre...

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
3
4
5
6
7
8
9
 
static void *tab_mem_malloc;
...
struct addr_t {
	void *address;
	unsigned char flag;
};
...
tab_mem_malloc=(struct addr_t *)malloc(block_nb);

Visiblement, tu n'as pas compris qu'il y avait 2 variables.

- le bloc de donnée préalloué qui va servir à l'allocation des petits blocs
- le tableau de structure sui sert à memoriser l'état des petits blocs. (adresse, libre/ocupé)

La globale pour le bloc est, par exemple :

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

static void *G_p_mem;

et dans init(), on fait

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

   G_p_mem = malloc(nb_bloc * taille_bloc);

et la globale pour le tableau d'état des blocs :

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
3
4
5
6
7
 
static struct bloc 
{
   void *address;
   int libre;
}
*G_a_blocs;

avec ceci dans init() :

EDIT

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

G_a_blocs = malloc (sizeof *G_a_blocs * nb_bloc);

Ensuite, il faut remplir le tableau de blocs avec les adresses précalculées et c'est là que ça devient interessant. (Penser aussi à affirmer le flag 'libre')

Tu verras qu'il faut aussi mémoriser le nombre et la taille des blocs. Je suggère une structure globale unique.

J'ai fait comme ça :

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
 
struct block
{
   void *p;
   int libre;
};
 
/* globale interne */
static struct data
{
   void *p_mem;
   size_t block_nb;
   size_t block_size;
 
   struct block *a_blocks;
}
G;

[Jack_serious]

Alors, je commence à mieux saisir !
Et on ne peut pas définitivement se passer du malloc ?

Si. Et non.

malloc() est la fonction generique la plus basse.
Si tu prend plus bas que malloc() pour allouer de la memoire, tu perds la portabilite,

En dessous de malloc() tu as la fonction brk() ou sbrk() par exemple. Mais ce ne sont plus des fonctions de la libc mais des appels systemes. Dont pas portable.
Mais c'est plus rapide.

Si le fait de faire un malloc() ou deux au debut de ton programme t'ennuie, tu peux faire un sbrk(). Plus rapide. Mais la derniere fois que j'ai voulu tester la resistance de sbrk() au changement d'architecture, ca c'est fini par "bus error" si ma memoire est bonne.

Cela dit, avec un seul malloc, je pense que c'est tres valable.

Bon courage.

[Emmanuel Delahaye]

Alors, je commence à mieux saisir !
Et on ne peut pas définitivement se passer du malloc ?

Si. Et non.

On peut très bien gérer un allocateur à partir d'un bloc statique. On a pas besoin de malloc().

[progfou]

Dans ce code :

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
 
G_a_blocs = malloc (sizeof *a_blocs * nb_bloc);

C'est quoi *a_blocs ?

Le reste, j'avais presque bon, mais je m'étais compliqué la tâche.
Je commence à mieux saisir le truc !

[Emmanuel Delahaye]

Dans ce code :

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
 
G_a_blocs = malloc (sizeof *a_blocs * nb_bloc);

C'est quoi *a_blocs ?

Le reste, j'avais presque bon, mais je m'étais compliqué la tâche.
Je commence à mieux saisir le truc !

Une erreur de frappe, désolé. (Je corrige)

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
 
G_a_blocs = malloc (sizeof *G_a_blocs * nb_bloc);

[progfou]

Pas de problème, mais j'étais dubitatif .

[PRomu@ld]

En fait si tu as accès à des fonction plus bas niveau que malloc, c'est peut être possible, en fait, si je me souvient bien, sous linux, il y a des fonction qui te permettent de modifier l'emplacement du point de rupture entre la pile et le tas.

Je ne sais pas si c'est plus performant que malloc (d'ailleur malloc utilise cet appel bas niveau sous linux). Mais c'est surement un peu plus galère à gérer.

De plus, je ne sais pas si tu as ce genre de fonction pour ton système.

sinon, c'est ce genre de fonction qu'il faut utiliser :
http://manpagesfr.free.fr/man/man2/brk.2.html

Mais tu dis que ton programme est lent à s'éxécuter, est tu sur qu'il n'y a pas d'amélioration algorithmique à utiliser (plutôt que t'utiliser les optimisations de gcc).

[progfou]

Disons, au départ, ça venait de malloc mais du coup, je met le prog de côté pendant quelques jours, et j'essaie de comprendre les mécanismes de la mémoire. En faisant ce gestionnaire de mémoire simple, et en l'améliorant ensuite, je pense que je pourrais arriver à quelque chose de performant et assez générique (en tout cas, j'espère !). En plus, ça touche des notions importantes du C qui sont encore obscures pour moi, comme les structures.
Edit :
Ce code :

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

G_a_blocs = malloc (sizeof *G_a_blocs * nb_bloc);

A pour effet de...
Je ne comprends pas en fait, j'ai l'impression qu'il n'y a qu'une seule structure de créée.

[Emmanuel Delahaye]

Ce code :

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

G_a_blocs = malloc (sizeof *G_a_blocs * nb_bloc);

A pour effet de...
Je ne comprends pas en fait, j'ai l'impression qu'il n'y a qu'une seule structure de créée.

Celui ci céee 1 structure

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

G_a_blocs = malloc (sizeof *G_a_blocs);

pareil que

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

G_a_blocs = malloc (sizeof *G_a_blocs * 1);

celui-là crée un tableau de nb_bloc structures

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

G_a_blocs = malloc (sizeof *G_a_blocs * nb_bloc);

Mais si tu n'es pas à l'aise avec les structures et l'allocation dynamique, c'est sûr que ce problème est un peu difficile à résoudre pour toi pour le moment.

Il faut d'abord consolider tes connaissances, et ensuite tu pourras attaquer ce gestionnaire de mémoire (ultra-simple, quand même, car les blocs ont une taille fixe).

[progfou]

OK, j'ai compris !
Donc, G_a_blocs est un tableau de nb_bloc.
Ca, j'ai vérifié, c'est OK.
La globale nommé G est là pour ... ?
C'est une sorte de "super bloc" ?
Je ne vois pas trop...

[Emmanuel Delahaye]

OK, j'ai compris !
Donc, G_a_blocs est un tableau de nb_bloc.

Mmmm. Pour être précis, disons que ça se comporte de la sorte. En fait, c'est un pointeur vers un bloc alloué d'une taille de sizeof *G_a_blocs *nb_bloc bytes.

Ca évite de croire que les pointeurs sont des variable de taille elastique, ce qui est évidemment faux.

Ca, j'ai vérifié, c'est OK.

Je ne vois pas trop ce que tu as pu vérifier ni comment...

La globale nommé G est là pour ... ?
C'est une sorte de "super bloc" ?
Je ne vois pas trop...

Ah, tu parles de mon implémentation, oui G est une structure globale privée de type 'struct data' qui englobe toutes les globales dont on a besoin pour faire tourner l'allocateur de blocks.

[progfou]

J'ai juste vérifé qu'un appelle à G_a_blocs[0].libre était valide, de même pour un appel G_a_blocs[nb_bloc-1] et pas au-delà .
Tu as déjà implémenté un allocateur mémoire ?
Je ne l'ai pas trouvé dans ta lib...
Edit: J'ai pris un papier et un crayon, histoire de voir si je saisissais tout, et je me suis posé la question de savoir si je pouvais faire mieux, c'est à dire allouer avec un système un peu plus évolué, qui serait capable de gérer les blocs, mais avec une taille de chaque bloc variable. Et là, j'ai un truc qui apparaît, c'est une "fragmentation" de la mémoire (ça se dit ?).
Alors, là, je bloque (encore !).

[Emmanuel Delahaye]

J'ai juste vérifé qu'un appelle à G_a_blocs[0].libre était valide, de même pour un appel G_a_blocs[nb_bloc-1] et pas au-delà .
Tu as déjà implémenté un allocateur mémoire ?

Suite à ton post initial, oui, j'en ai fait un chez moi en, disons ... 20 minutes. J'ai quand même cherché à vérifier que je ne racontais pas trop de salades...

Je ne l'ai pas trouvé dans ta lib...

Gros fénéant ! Je le publierais quand tu auras fait le tien. Mais il y a des idées à prendre dans le module SYSALLOC...

Edit: J'ai pris un papier et un crayon, histoire de voir si je saisissais tout, et je me suis posé la question de savoir si je pouvais faire mieux, c'est à dire allouer avec un système un peu plus évolué, qui serait capable de gérer les blocs, mais avec une taille de chaque bloc variable. Et là, j'ai un truc qui apparaît, c'est une "fragmentation" de la mémoire (ça se dit ?).
Alors, là, je bloque (encore !).

Pourquoi faire simple quand on peut faire compliqué...

Taille variable, ça devient complexe... Il faut chainer les blocs, et comme tu l'as deviné, on gruyèrise la mémoire rapidement...

Mais je te rappelle que tu voulais de la performance. Y'a pas trop le choix, c'est taille fixe. Dans l'industrie, on crée des pools de mémoire pre-allouées de taille fixe, mais differentes, par exemple :

128 x 16 bytes
128 x 32 bytes
32 x 64 bytes
16 x 128 bytes
8 x 1536 pour le pool de trames Ethernet...
etc.
tu vois le genre...

L'allocateur prend d'abord les plus petits possibles en ensuite prends les plus gros etc.

C'est une solution intermédiare assez rapide... On eut aussi créer des pools spécialisés qui ne servent qu'à un type d'application (approvisionner des buffers de réception de taille fixe pour une pile de protocole...) et dans ce cas, ça peut être très rapide...

[progfou]

Bon, je n'ai pas eu des masses de temps depuis deux jours, je m'y remets.
J'ai réfléchi à ta structure globale G, j'aime bien le concept.
Donc, si j'ai bien compris, je me retrouve avec ça :

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
 
struct block
{
   void *p;
   int libre;
};
 
static struct data
{
   void *p_mem;
   size_t block_nb;
   size_t block_size;
 
   struct block *G_a_blocs;
}G;
 
void mem_init(size_t block_nb, size_t block_size) {
	G.p_mem=malloc(block_nb*block_size);
	G.G_a_blocs = malloc (sizeof *G.G_a_blocs * block_nb);
	G.block_nb=block_nb;
	G.block_size=block_size;
}

En tout cas, ça compile :p .

[Emmanuel Delahaye]

Donc, si j'ai bien compris, je me retrouve avec ça :

Y'a de l'idée. Avant de mettre à jour la globale, il faut travailler en local et vérifier que les allocations se sont bien passées. Retourner un compte rendu.

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

int mem_init(size_t block_nb, size_t block_size) {

[progfou]

Ca, c'est fait, car c'est important effectivement.
J'en suis à un problème d'alloc/free.
Dans le cas où je libère les blocs "dans l'ordre", ça ne pose pas de problème, au niveau du concept quoi, mais j'avoue que cette partie me pose pas mal de soucis.
Tu adopterais quelle stratégie (tu, ou les autres ), une écriture dans chaque bloc de taille size bits de leur adresse et du fait qu'ils sont libres ou non, ou une écriture par "gros paquet", en clair, un bloc qui reçoit une adresse (qui est renvoyée) flag libre mis à jour et sa taille.
Ou autre chose ?

[Emmanuel Delahaye]

Dans le cas où je libère les blocs "dans l'ordre", ça ne pose pas de problème, au niveau du concept quoi, mais j'avoue que cette partie me pose pas mal de soucis.
Tu adopterais quelle stratégie (tu, ou les autres ), une écriture dans chaque bloc de taille size bits de leur adresse et du fait qu'ils sont libres ou non, ou une écriture par "gros paquet", en clair, un bloc qui reçoit une adresse (qui est renvoyée) flag libre mis à jour et sa taille.
Ou autre chose ?

Je crois que j'avais déjà exposé l'algo ultra simpliste du malloc() :

• vérifier que la taille est inérieure ou égale à la taille max d'un bloc
• si elle dépasse, ou si elle est nulle, retournetr NULL.
• dans le tableau des blocs, chercher un bloc libre
• si il n'y en a pas, retourner NULL
• si on en trouve un, le marquer occupé, retourner son adresse.

C'est tout.

Pour le free, c'est encore plus simple.

dans le tableau des blocs,

• chercher l'adresse du bloc à libérer
• si on l'a trouvé, le marquer 'libre'.

C'est tout.

Je ne vois vraiment pas ce qui est compliqué...

Ce mécanisme peut libérer les blocs dans n'importe quel ordre (du moment qu'on ne scie pas la branche sur laquelle on est assis...)

[progfou]

Oui, j'avais bien compris ça !
Ce qui me pose problème, c'est de savoir si tous les blocs (donc block_nb blocks) doivent être marqués libre ou occupé, ou s'il est préférable de modifier la structure d'un bloc pour qu'il contienne une taille. En clair :

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

int *p = mem_malloc(sizeof(*p) * 3);

Réserve 3 blocks de 4 octets.
Ma structure block

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
3
4
5
6
struct block
{
	void *p;
	size_t size;
	int libre;
};

voit donc un block supplémentaire qui a pour adresse la première adresse "libre" dans le bloc mémoire, et size=12.

[Emmanuel Delahaye]

Oui, j'avais bien compris ça !
Ce qui me pose problème, c'est de savoir si tous les blocs (donc block_nb blocks) doivent être marqués libre

Ils sont évidemment marqués libres par la fonction mem_init(). On a pas déjà expliqué tout ça ?

ou occupé, ou s'il est préférable de modifier la structure d'un bloc pour qu'il contienne une taille. En clair :

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

int *p = mem_malloc(sizeof(*p) * 3);

Réserve 3 blocks de 4 octets.
Ma structure block

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
3
4
5
6
struct block
{
	void *p;
	size_t size;
	int libre;
};

voit donc un block supplémentaire qui a pour adresse la première adresse "libre" dans le bloc mémoire, et size=12.

Pas besoin de noter la taille (sauf pour le debug, et encore...). La structure bloc c'est plutôt ça :

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
3
4
5
6
 
struct block
{
	void *p;
	int libre;
};

dans le tableau de struct block, tu cherches le 1er 'libre' et tu fais ce qui été expliqué 14.000 fois avant... Je fatigue... Tu as l'algo, code le, c'est tout, ça va pas de mordre !

[progfou]

Ca me parait juste lent de marquer les n blocks occupés.