[malloc] questions sur l'allocation dynamique

Bonjour a tous,

Desole d'avance, mais j'ecris depuis un clavier anglais, donc pour les accents c'est rape...
Je m'interesse a l'allocation dynamique. Je cherchai donc a me prouver certaines proprietes:

Que malloc() aligne l'allocation sur la taille des pages
Que free() ne fait decroitre le tas que si les pages liberees sont contigues en fin de tas
Que malloc() alloue la memoire par bloc et pas a chaque appel atomique (en gros que brk n'est pas appele a chaque fois)

J'ai des problemes avec le point 3. En fait, si j'alloue plusieurs fois 1 octet, je pensais que la premiere fois sbrk() serait appele pour allouer un bloc, et que les appels suivants ne ferait pas bouger le tas, mais placerait l'octet dans la region reservee.
Ce que je constate, c'est que sbrk() est appele a chaque fois. Je pense que je me trompe quelque part, mais je vois pas trop.
Voici le petit programme:

Code:

1
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
64
65
66
67
68
69
70
71
 
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <unistd.h>
 
#ifndef MAX_ALLOCS
  #define MAX_ALLOCS 1000000
#endif
//For 32 bit OS, page size is 4kbytes
#define PAGE_SIZE 4096
 
void usage(char *progName)
{
  if (progName != NULL || progName[0] != '\0')
    fprintf(stderr, "Usage: %s num-allocs block-size [step [min [max]]]\n", progName);
  exit(EXIT_FAILURE);
}
 
int main(int argc, char *argv[])
{
  char *ptr[MAX_ALLOCS];
  int freeStep, freeMin, freeMax, blockSize, numAllocs, j;
 
  if (argc < 3 || strcmp(argv[1], "-h") == 0)
    usage(argv[0]);
 
  numAllocs = (int)strtol(argv[1], NULL, 0);
  if (numAllocs > MAX_ALLOCS)
  {
    fprintf(stderr, "Can't allocate more than MAX_ALLOCS. num-allocs < %u\n", MAX_ALLOCS);
    usage(argv[0]);
  }
 
  blockSize = (int)strtol(argv[2], NULL, 0);
  freeStep = (argc > 3) ? (int)strtol(argv[3], NULL, 0) : 1;
  freeMin = (argc > 4) ? (int)strtol(argv[4], NULL, 0) : 1;
  freeMax = (argc > 5) ? (int)strtol(argv[5], NULL, 0) : numAllocs;
 
  if (freeMax > numAllocs)
  {
    fprintf(stderr, "Can't free more than we have allocated. max < num-allocs\n");
    usage(argv[0]);
  }
  void *initialHeap = (void*)sbrk(0);
  printf("Intial program break: %10p\n", initialHeap);
  printf("Allocate %d*%d bytes\n", numAllocs, blockSize);
  int numBytes = numAllocs * blockSize;
  printf("We need %.3f pages for %d bytes\n", numBytes/(float)PAGE_SIZE, numBytes);
 
  for ( j = 0; j < numAllocs; j++)
  {
    ptr[j] = malloc(blockSize);
    printf("Current value of the heap for block %u (total alloc=%u): %10p\n", j, j*blockSize + blockSize, ptr[j]);
    if (ptr[j] == NULL)
      exit(EXIT_FAILURE);
  }
 
  void *newHeap = (void*)sbrk(0);
  printf("Program break is now: %10p\n", newHeap);
  printf("We allocated %.3f pages\n", (newHeap - initialHeap)/(float)PAGE_SIZE);
 
  printf("Freeing from %d to %d (step: %d)\n", freeMin, freeMax, freeStep);
  for ( j = freeMin; j < freeMax; j += freeStep)
    free(ptr[j]);
 
  void *endHeap = (void*)sbrk(0);
  printf("After free program break: %10p\n", endHeap);
 
  exit(EXIT_SUCCESS);
}

Et la sortie qui me gene est la derniere, les 2 avant montrent 2.:

Code:

1
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
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
 
./free_and_sbrk 20 10240 1 10 20
Intial program break:  0x96c3000
Allocate 20*10240 bytes
We need 50.000 pages for 204800 bytes
Current value of the heap for block 0 (total alloc=10240):  0x96c3008
Current value of the heap for block 1 (total alloc=20480):  0x96c5810
Current value of the heap for block 2 (total alloc=30720):  0x96c8018
Current value of the heap for block 3 (total alloc=40960):  0x96ca820
Current value of the heap for block 4 (total alloc=51200):  0x96cd028
Current value of the heap for block 5 (total alloc=61440):  0x96cf830
Current value of the heap for block 6 (total alloc=71680):  0x96d2038
Current value of the heap for block 7 (total alloc=81920):  0x96d4840
Current value of the heap for block 8 (total alloc=92160):  0x96d7048
Current value of the heap for block 9 (total alloc=102400):  0x96d9850
Current value of the heap for block 10 (total alloc=112640):  0x96dc058
Current value of the heap for block 11 (total alloc=122880):  0x96de860
Current value of the heap for block 12 (total alloc=133120):  0x96e1068
Current value of the heap for block 13 (total alloc=143360):  0x96e3870
Current value of the heap for block 14 (total alloc=153600):  0x96e6078
Current value of the heap for block 15 (total alloc=163840):  0x96e8880
Current value of the heap for block 16 (total alloc=174080):  0x96eb088
Current value of the heap for block 17 (total alloc=184320):  0x96ed890
Current value of the heap for block 18 (total alloc=194560):  0x96f0098
Current value of the heap for block 19 (total alloc=204800):  0x96f28a0
Program break is now:  0x9707000
We allocated 68.000 pages
Freeing from 10 to 20 (step: 1)
After free program break:  0x96fd000
 
./free_and_sbrk 20 10240 2 10 20
Intial program break:  0x9abf000
Allocate 20*10240 bytes
We need 50.000 pages for 204800 bytes
Current value of the heap for block 0 (total alloc=10240):  0x9abf008
Current value of the heap for block 1 (total alloc=20480):  0x9ac1810
Current value of the heap for block 2 (total alloc=30720):  0x9ac4018
Current value of the heap for block 3 (total alloc=40960):  0x9ac6820
Current value of the heap for block 4 (total alloc=51200):  0x9ac9028
Current value of the heap for block 5 (total alloc=61440):  0x9acb830
Current value of the heap for block 6 (total alloc=71680):  0x9ace038
Current value of the heap for block 7 (total alloc=81920):  0x9ad0840
Current value of the heap for block 8 (total alloc=92160):  0x9ad3048
Current value of the heap for block 9 (total alloc=102400):  0x9ad5850
Current value of the heap for block 10 (total alloc=112640):  0x9ad8058
Current value of the heap for block 11 (total alloc=122880):  0x9ada860
Current value of the heap for block 12 (total alloc=133120):  0x9add068
Current value of the heap for block 13 (total alloc=143360):  0x9adf870
Current value of the heap for block 14 (total alloc=153600):  0x9ae2078
Current value of the heap for block 15 (total alloc=163840):  0x9ae4880
Current value of the heap for block 16 (total alloc=174080):  0x9ae7088
Current value of the heap for block 17 (total alloc=184320):  0x9ae9890
Current value of the heap for block 18 (total alloc=194560):  0x9aec098
Current value of the heap for block 19 (total alloc=204800):  0x9aee8a0
Program break is now:  0x9b03000
We allocated 68.000 pages
Freeing from 10 to 20 (step: 2)
After free program break:  0x9b03000
 
./free_and_sbrk 20 512
Intial program break:  0x99b4000
Allocate 20*512 bytes
We need 2.500 pages for 10240 bytes
Current value of the heap for block 0 (total alloc=512):  0x99b4008
Current value of the heap for block 1 (total alloc=1024):  0x99b4210
Current value of the heap for block 2 (total alloc=1536):  0x99b4418
Current value of the heap for block 3 (total alloc=2048):  0x99b4620
Current value of the heap for block 4 (total alloc=2560):  0x99b4828
Current value of the heap for block 5 (total alloc=3072):  0x99b4a30
Current value of the heap for block 6 (total alloc=3584):  0x99b4c38
Current value of the heap for block 7 (total alloc=4096):  0x99b4e40
Current value of the heap for block 8 (total alloc=4608):  0x99b5048
Current value of the heap for block 9 (total alloc=5120):  0x99b5250
Current value of the heap for block 10 (total alloc=5632):  0x99b5458
Current value of the heap for block 11 (total alloc=6144):  0x99b5660
Current value of the heap for block 12 (total alloc=6656):  0x99b5868
Current value of the heap for block 13 (total alloc=7168):  0x99b5a70
Current value of the heap for block 14 (total alloc=7680):  0x99b5c78
Current value of the heap for block 15 (total alloc=8192):  0x99b5e80
Current value of the heap for block 16 (total alloc=8704):  0x99b6088
Current value of the heap for block 17 (total alloc=9216):  0x99b6290
Current value of the heap for block 18 (total alloc=9728):  0x99b6498
Current value of the heap for block 19 (total alloc=10240):  0x99b66a0
Program break is now:  0x99d5000
We allocated 33.000 pages
Freeing from 1 to 20 (step: 1)
After free program break:  0x99d5000

En fait je m'attendrai a ce que la valeur de sbrk ne change pas a chaque appel de malloc. Est ce que quelqu'un a 1 idee de ce qui pourrait expliquer ca?

Merci d'avance.

En fait, il faut faire le sbrk() après le premier malloc. D'autre part, je ne vois pas de tests avec juste un octet.
Enfin, tu peux voir les brk() appelé avec un strace sur ton programme, et en faisant le test on a (sans les write):

Citation:

Envoyé par strace ./dahtah 50 1

[...]
unmap(0x7f4cab8cd000, 82330) = 0
brk(0) = 0x23d2000
fstat(1, {st_mode=S_IFCHR|0600, st_rdev=makedev(136, 2), ...}) = 0
mmap(NULL, 4096, PROT_READ|PROT_WRITE, MAP_PRIVATE|MAP_ANONYMOUS, -1, 0) = 0x7f4cab8e1000
write(1, "Intial program break: 0x23d2000\n", 33) = 33
write(1, "Allocate 50*1 bytes\n", 20) = 20
write(1, "We need 0.012 pages for 50 bytes\n", 33) = 33
brk(0x23f3000) = 0x23f3000
write(1, "Current value of the heap for block 0 (total alloc=1): 0x23d2010\n", 66) = 66
write(1, "Current value of the heap for block 1 (total alloc=2): 0x23d2030\n", 66) = 66
[...]
write(1, "Current value of the heap for block 49 (total alloc=50): 0x23d2630\n", 68) = 68
write(1, "Program break is now: 0x23f3000\n", 33) = 33
write(1, "We allocated 33.000 pages\n", 26) = 26
write(1, "Freeing from 1 to 50 (step: 1)\n", 31) = 31
write(1, "After free program break: 0x23f3000\n", 37) = 37
exit_group(0) = ?

Où on voit juste un break après le permier malloc et c'est tout.

PS: au passage si step n'est pas un nombre, on a 0 et du coup, ça fait les free() en boucle :D (je suis tombé dessus en mettant -o /tmp/foo pour le strace mais à la fin, donc pour ton programme)

Citation:

Envoyé par D[r]eadLock

En fait, il faut faire le sbrk() après le premier malloc. D'autre part, je ne vois pas de tests avec juste un octet.

Non, j'ai mis 512, mais chez moi j'ai teste avec 1, le resultat est le meme. Pour moi, tout ce qui est en dessous d'1 page devrait etre bon.

Citation:

Envoyé par D[r]eadLock

Enfin, tu peux voir les brk() appelé avec un strace sur ton programme

Oui, la effectivement, ca confirme le comportement que je voulais observer. Et la je viens de voir que j'ai fait une erreur de couillon dans le printf dans la boucle. Je print la valeur du pointeur, alors que je voulais printer la borne superieure du tas (soit la valeur de sbrk(0)) pout voir qu'elle ne bougeait pas:

Code:

printf("Current value of the heap for block %u (total alloc=%u): %10p\n", j, j*blockSize + blockSize, sbrk(0));

La je vois bien que sbrk alloue 33 pages au premier malloc, et que les suivants ne changent pas la valeur du tas (comme sur le strace).

Citation:

Envoyé par D[r]eadLock

PS: au passage si step n'est pas un nombre, on a 0 et du coup, ça fait les free() en boucle :D (je suis tombé dessus en mettant -o /tmp/foo pour le strace mais à la fin, donc pour ton programme)

Merci, mais je corrigerai pas pour autant :), c'etait juste un petit programme de test. C'est cool, GNU/Linux alloue la memoire comme prevu :)

Je vais essayer d'implementer malloc et free maintenant. J'ai regarde comment c'est fait et c'est vraiment ingenieux de stocker la taille de l'alloc avant la zone allouee, et sur chaque free de mettre la portion liberee dans une liste doublement chainee.

En tout cas merci D[r]eadLock, le strace m'a ouvert les yeux (et j'aurai du y penser)...
Merci a toi

Les propositions 1 et 3 ne sont-elles pas incompatibles?

Salut Medinoc,

Je ne pense pas, mais je me suis peut etre mal exprime.
Ce que je voulais dire avec 1., c'est que l'allocation sera de la taille d'une page (4ko ou 2Mo dans le case generique) ou d'un multiple de taille de page. Je voulais mettre en valeur que si tu alloues un tableau dynamiquement de 5000 octets, l'allocateur allouera alors un multiple de page, soit 8192.
Avec le point 3. (qui est similaire a 1.), je voulais dire que si tu alloues plusieurs fois des petites quantites de memoires atomiques, l'allocateur ne va pas reserver de la memoire a chaque fois. Il va directement allouer une taille de memoire consequente. Par exemple si tu alloues 5 fois 1 octets, l'allocateur va faire une seul appel a sbrk(), et non pas 5 fois un appel a sbrk() de 1 octet.

Je voulais juste voir ca de mes yeux...

A+