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

[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 ?

[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);
}

[Bktero]

Bien joué !

[Bktero]

J'ai jeté un oeil dans le K&R. La section 8.7 est consacré à l'écriture d'un système d'allocation mémoire. La gestion se fait avec une liste des espaces mémoires libres. Lors du free, on rajoute juste l'espace à libérer à cette liste. Pas grand chose pour aider dans notre problème si ce n'est la confirmation de la liste chainée, mais ce n'est pas franchement une surprise.

Je me disais aussi qu'il n'était pas nécessaire d'avoir 2 listes chainées. Une seule pourrait suffire.

[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 !

[prgasp77]

Bonjour,

Tu prends 2 octets de plus, mais tu ne décales que de 1 cran avec le ++

Il me semble que ++ appliqué à un pointeur non void incrémente l'adresse de la taille de l'élément pointé.

Guyt54 : effectivement, c'est une solution.

[Guyt54]

Pour l'histoire du ptr++, quand je demande à mes étudiants la question suivante:

Soit le code suivant (on suppose toujours des int de 16 bits):

Code :

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

1
2
3
4
int* ptr ;
 ptr = (int*)1000 ;
 ptr++ ;  // p = p  + 1

Prof: Quelle est la valeur de "ptr"?
Elèves (en coeur): 1001!
Prof: 1002 que je vous dis
Éleves: Hein???????????
Prof:

- Bon, les petits vous vous souvenez de l'étroite relation entre les pointeurs et tableaux:

Code :

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

1
2
   *(ptr+index) === ptr[index]

- Oui msieur!

- Alors l'élement dans ptr[1], il est à quelle adresse toujours en supposant que le tableau commence à l'adresse 1000 et que chaque élément occupe 2 octets?

- (En coeur): 1002 msieur.

- Alors p++, ça pointe à quelle adresse?

- (En coeur): 1002 msieur!!!

(et là, j'envie le prof qui enseigne le Java et qui n'a pas à montrer les pointeurs)

[Aquanum]

Huhu, j'aimerais beaucoup enseigner un jour, mais essayer de faire rentrer le principe des pointeurs dans la têtes d'étudiants doit être une horreur

[Bktero]

Je suis parti du principe qu'on allouait des tableaux d'entiers, ce qui est totalement bête. D'ailleurs, c'est écrit 2 bytes, ça aurait dû me faire tilter qu'on allouait des char.

Mettons un sizeof(int) à la place du 2

[Guyt54]

Huhu, j'aimerais beaucoup enseigner un jour, mais essayer de faire rentrer le principe des pointeurs dans la têtes d'étudiants doit être une horreur

ça t'apprendra, là tu me lances le mode nostalgie.

Bin, tu sais il fut un temps où c'était facile à expliquer, la glorieuse époque où on prenait le temps d'étudier l’architecture interne d'un micro, les instructions machines, les modes d'adressage, l'assembleur.

Quand venait le temps d’expliquer les pointeurs en C, on avait qu'à dire, "c'est de l'adressage indirect" et tout le monde avait compris.

Avec le temps, la technologie c'est complexifiée, il y avait de plus en plus de matière à voir, on a donc pris la décision de laisser tomber le très bas niveau comme l'assembleur.

Avec du recul, je pense que ce fut une grosse gaffe de notre part. Essaye d'expliquer des notions très avancées telle la récursivité quand l'étudiant n'a pas la moindre idée du mécanisme d'appel de routines et de la localisation des variables locales via une pile.

Il me semble que tout est bâti sur du mou. L'étudiant ne se formalise pas de ne pas comprendre l’architecture interne d'un ordi. Après tout, a-t-on besoin de savoir comment fonctionne un moteur pour conduire une voiture?

L'an passé, j'ai essayé de ré-introduire l'assembleur (Avec AVR Studio) dans mes cours. J'ai vite abandonné devant le peu d'intérêt manifesté par les étudiants. "Beaucoup de code pour pas grand chose, finalement".

Mais bon, toute cette nostalgie être peut-être celle d'un has-been qui ne saisit pas les modes d'apprentissage de cette nouvelle génération.

[Bktero]

Je te connais pas mais je t'aime bien toi ! J'aurais aimé t'avoir en prof je crois !

[Aquanum]

Guyt54> Non tu n'es pas has-been. J'ai la même vision des choses que toi et je pense que tous les gens qui font de l'embarqué et du bas niveau la partagent. Et je pense que la raison pour laquelle le secteur de l'embarqué est si porteur, c'est que de moins en moins de monde s'intéresse au bas niveau... C'est malheureux. Mais tant pis pour eux, ça nous fait plein de travail passionnant

[Guyt54]

Merci Bktero et Aquanum pour vos commentaires positifs, ça me remonte le moral, c'est pas drôle en ce moment au Québec (et plus particulièrement à Montréal) avec ce conflit étudiant qui dégénère de jour en jour.