Discussion :

[IsraGab]

Bonjour,
Je viens de finir mes etudes en informatique, et j'ai postule pour un job concernant le C et la programmation embarquee.

A l'entretient il m'a ete posee une question (que je pense avoir mal repondu).
Je souhaiterai avoir quelques expliquations.
Voici la question qui m'a ete posee:

Un systeme d'exploitation a ete devellope, dans lequel il est permis, grace a 2 fonctions d'allouer de la memoire a un programme.
La 1er fonction se nomme: void* big_Malloc(int size).
La 2eme fonction se nomme: void* small_Malloc(int size).
Les 2 fonctions renvoient un pointeur de type void* que si size est un multiple de 16.
Lorsque la place a allouer est superieur a 512 octets, big_Malloc() est appelee, dans le cas contraire (place a allouer <= 512 octets), small_Malloc()
serra appelee.
A ces 2 fonctions, sont associees 2 fonctions: void big_Free(void *ptr) et void small_Free(void *ptr), pour liberer la memoire.
Ecrivez l'implementation d'une fonction malloc() et free() en utilisant les fonctions decrites precedement, de telle sorte qu'il soit possible d'allouer toute taille (et non juste un multiple de 16)
l'implementation se doit d'etre claire et propre.

En plus de l'ennonce, etait joint un exemple d'une implementation possible des fonctions Malloc() et Free()
voici a peu pret a quoi cela ressemblait:

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
23
24
25
26
27
28
29
30
31
32
#include "OS.h"

int G_sz;
void* Malloc(int size)
{
        void *p;
        G_sz = size;
        if(size>512)
               {
                     p=big_Malloc(size);
                }
        else
                {
                     p=small_Maloc(size);
                 }
       
         return p;
     } 


void Free(void *ptr)
{
      if(size>512)
               {
                    big_free(ptr);
                }
        else
                {
                     small_free(ptr);
                 }
}

Il est stipule dans l'ennonce que le code est faux, et on demande de ne pas le corriger, il vient juste en guise d'indication pour nous orienter sur la bonne reponse.

Qu'en pensez vous?
Merci

[Aquanum]

1) Je pense que déjà tout dépendra de la gestion de la mémoire dans ton OS. Typiquement pour que le free sache la taille à libérer, et comment, etc. Parce que le coup du size en variable globale c'est plutôt marrant comme concept

Code :

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

1
2
3
#include "OS.h"

int G_sz;

Mais ça se fait pas comme ça en temps normal. Donc là le cas est simpliste, mais il te manque des infos sur la gestion de la mémoire de ton système. Enfin, s'ils disent de ne pas corriger l'erreur c'est qu'ils ne doivent pas vouloir que tu réfléchisses sur ce point.

2) Il va falloir découper ton allocation en blocs de 16 octets.

3) Il faut aussi rajouter de la gestion d'erreurs.

Par contre, il manque quelque chose là :

Les 2 fonctions renvoient un pointeur de type void* que si size est un multiple de 16.

Et sinon ? Ça renvoie quoi ? NULL ?

l'implementation se doit d'etre claire et propre.

Bah non biensûr, obsfusquons le code, tant qu'à faire ahah

Enfin voilà, c'est comme ça que j'aurais envisagé une réponse.

[IsraGab]

Bonjour,

Par contre, il manque quelque chose là :

Les 2 fonctions renvoient un pointeur de type void* que si size est un multiple de 16.

Et sinon ? Ça renvoie quoi ? NULL ?

Tout simplement l'allocation n'aurra pas lieu

[prgasp77]

Bonjour,

Tout simplement l'allocation n'aurra pas lieu

Et comment le sait-on ?

Le problème n'est pas l'écriture de la fonction malloc (test sur la taille + allocation du plus petit multiple de 16 supérieure à cette taille), mais celle de free, qui doit décider si elle doit faire appelle à big_free ou à small_free avec pour seule donnée l'adresse de la zone à libérer.

Il faut donc stocker cette information quelque part ... à moins qu'un appel à small_free avec en argument l'adresse d'une zone réservée avec big_malloc ne retourne NULL. Auquel cas, problème trivial.

Cdlt,

Edit: grilled

[Aquanum]

Je suis d'accord sur l'aspect entretien de code.
C'est comme les examens de dev sur papier à l'école, une hérésie.
Bon ça permet aussi de filtrer à la louche, ce qui n'est pas plus mal parfois.
Quand j'ai eu des tests comme ça en entretien je répondais juste un truc aux questions tordues -> "man / google". Désolé mon cerveau ne contient pas tous les mans.

Bon je pense que là avant toute chose c'est le raisonnement qui est attendu.

Pour répondre au

Tout simplement l'allocation n'aurra pas lieu

Un malloc qui rate, renvoie NULL C'est comme ça, et uniquement comme ça que l'on sait si l'allocation a raté, donc il faut l'erreur, qui n'est pas précisée dans l'énoncé.

- Soit on fait du C, et nous poussons le vice à détailler tout
- Soit on fait du pseudo code et on ne demande pas de coder

Bktero> Je suis d'accord également avec toi pour la variable size. En fait soit la gestion de la mémoire est cachée, soit elle ne l'est pas. Enfin je vois pas l'intérêt non plus de G_sz si c'est transparent dans l'exercice.

Enfin bref, c'est assez bizarre comme exercice... C'est pas clair...

Genre prenez exemple de ce code faux ...

[Bktero]

Le problème n'est pas l'écriture de la fonction malloc (...), mais celle de free, qui doit décider si elle doit faire appelle à big_free ou à small_free avec pour seule donnée l'adresse de la zone à libérer.

C'est vrai que je ne mettais pencher que sur le cas de malloc... Si c'est le cas que tu donnes, c'est trivial en effet. Mais je ne pense pas que le retour soit ainsi, vu qu'un vrai free ne renvoie rien XD

En fait, l'exercice revient à coder le moyen de se souvenir de "qui a alloué à quel endroit ?".

Idée : faire deux listes chainées, une pour chaque malloc. A chaque fois qu'on fait une allocation avec xxx_Malloc, on ajoute un nouveau maillon (contenant l'adresse fraichement) à la liste correspondante ; quand vient le free(), on regarde si l'adresse passée en paramètre est dans une de ces 2 listes et on sait quel xxx_Free() appeler ou pas.

C'est encore plus bête car il est certain que chaque xxx_Malloc() possède une telle représentation.

Faut que je pense à regarder ce soir dans le K&R : il me semble qu'il y a un exemple de malloc() et de free().

[prgasp77]

C'est vrai que je ne mettais pencher que sur le cas de malloc... Si c'est le cas que tu donnes, c'est trivial en effet. Mais je ne pense pas que le retour soit ainsi, vu qu'un vrai free ne renvoie rien XD

Oui oui, je dis de la merde. Disons que le problème est trivial si un small_free sur un pointeur d'une zone allouée avec big_malloc ne fait rien. Dans ce cas :

Code :

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

1
2
3
4
5
void free(void* ptr)
{
   small_free(ptr);
   big_free(ptr);
}

[Guyt54]

Il faut donc stocker cette information quelque part
Edit: grilled

Un bon endroit pour stocker la grosseur de la mémoire dynamique serait peut-être dans la mémoire dynamique elle-même, en trichant un peu!

Me semble que ça pourrait ressembler à quelque chose du genre (en supposant un "int" de 16 bits):

pour allouer:

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
void* Malloc(int size)
{
        void *p;
      
        if(size>510)
          {
             p=big_Malloc(size+2); // on prend 2 bytes de plus
          }
        else
          {
             p=small_Maloc(size+2);
          }
        *((int*) p) = size ; // on met le size dans les 2 premiers bytes
        ((int*)p)++ ; // on cache les 2 premiers bytes
         return p ; 
     }

pour libérer:

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
void Free(void *ptr)
{
      int  size ;

      ptr = (int*) ptr - 1 ;
      size = *((int*)ptr)  ;
      if(size>510)
         {
            big_free(ptr);
         }
      else
         {
             small_free(ptr);
         }
}

Et si je passe pas l'entrevue, je les emmerde. De toute façon, la pleine retraite m'attend le 12/12/12, après avoir purgé la peine maximale, soit 35 ans de boulot

[Bktero]

Quelques petites remarques :

1. Tu prends 2 octets de plus, mais tu ne décales que de 1 cran avec le ++
2. Pas con du tout la technique !
3. 35 ans de cotisation ??? Quand je pense que notre ancien président nous a fait culpabiliser parce qu'on ne travaillait que 40 ans !

[Bktero]

Je n'ai jamais eu de tests à un entretien et je pense que c'est une belle connerie.

1) Je ne comprends pas l'intérêt de cette variable.... Elle est écrasée à chaque malloc() et on ne sait pas si elle est utilisée dans big_Malloc() et small_Malloc().
Aquanum, la façon de gérer de l'OS t'es cachée et on doit supposer qu'elle est respectée dans big_Malloc() et small_Malloc()

2) Il faut plutôt trouver le multiple de 16 immédiatement supérieur à la taille passée en paramètre de malloc() et la transmettre à big_Malloc() ou small_Malloc() selon les cas.

3) Tu peux passer outre ce que renvoient ces deux fonctions en écrivant un truc dans le genre :

Code :

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

1
2
3
4
5
void* malloc(int taille)
{
    // blabla
    return big_Malloc(...);
}

Cet exercice est vraiment nul pour juger du niveau d'un candidat....


EDIT :

Tout simplement l'allocation n'aurra pas lieu

Parfaitement d'accord, mais comment cela est signalée dans le code retour ?