| <-Précédent | Retour à l'accueil | Contact : etienne"point"sauvage"at"gmail.com | Suivant-> |
Au chapitre précédent, nous avons obtenu la carte de la mémoire, qui nous était aussi utile qu'une carte de l'Ouganda à votre serviteur (qui n'y a jamais mis les pieds et qui ne compte absolument pas importuner les ougandais de son inopportune présence). Bref, la mémoire ça s'utilise, sinon c'est Alzeihmer.
On utilise déjà de la mémoire. Le code de KarlOS est en mémoire. Nous avons déjà donné des adresses de chargement, nous lisons et écrivons dans des cases mémoire et ce depuis le début. Alors, de quoi qu'est-ce que je vous chante avec mes histoires de carte mémoire ?
Et bien, figurez-vous qu'un développeur, ou qu'un concepteur de système d'exploitation, aussi génial soit-il, n'est pas omniscient. Autrement dit, il ne peut pas tout prévoir, ni n'en a le temps. La quantité d'information et de temps dans un homme fini est nécessairement finie. Conséquemment, il a peu d'idée sur quelle partie de la mémoire est utilisée à un instant donné pour quel usage : sinon, il serait capable de prévoir tous les comportements de tous les utilisateurs, et il ne serait pas développeur, il serait maître du monde.
Imaginons le cas suivant : nous écrivons cette page web. L'ensemble des caractères tapés doit être stocké en mémoire. Cela prend de la place, et il ne faudrait pas que ces caractères soient stockés sur l'emplacement mémoire occupé par le gestionnaire d'interruptions clavier, par exemple. De surcroît, je mets au défi qui que ce soit de donner, avant la fin de la composition, l'espace mémoire occupé par cette même composition, à l'octet près. Indépendamment du débat entre détermination et indétermination de l'univers, je n'ai pas les moyens de connaître la quantité de mémoire dont j'ai besoin avant de faire les choses. Il s'ensuit qu'un système d'exploitation, même indigne de ce nom, doit avoir un système permettant de stocker des choses en mémoire sans dézinguer les autres choses dont on a encore besoin.
Le paragraphe précédent, quoi qu'obscur, signifie que KarlOS se doit de gérer la mémoire. En simplifiant, cela consiste à marquer l'utilisation ou la disponibilité de la mémoire. Je veux stocker une chaîne de caractère. Je dis à KarlOS : "Hey, je veux de la mémoire !". Et je m'attends à ce que KarlOS me réponde : "Tiens, en v'là. Va donc voir au 31 rue de la forge 43189 TRIFOUILLY CEDEX.". Oui, je m'attends à recevoir l'adresse de la mémoire demandée. KarlOS doit donc savoir que le 31 rue de la forge à Trifouilly est vide d'occupant.
Poursuivons cette analogie. J'occupe, avec ma chaîne de caractères, le 31 rue de la forge à Trifouilly. Nous y vivons paisiblement, mais bon, vous savez ce que c'est, on vieillit, on souffre d'incontinence pianoteuse, on fait des cochonneries, et la chaîne grandit. Elle grandit tant et si bien qu'elle ne tiendra plus bien longtemps à cette adresse, parce que le 31 rue truc, il est prévu pour 256 octets et pas 3124. Et le 33, il est occupé par un terroriste qui n'a pas l'air d'apprécier nos débordements. On demandera donc à KarlOS de nous allouer une nouvelle adresse, plus grande.
Je continue avec ma grosse chaîne, mais maintenant, j'en ai marre, et je n'en ai plus besoin. Je rends les clefs. L'adresse que j'occupais doit maintenant être considérée comme vide. KarlOS, prévenu, reprend les clefs. Mécaniquement, ma chaîne disparaît.
Je suis maintenant victime du devoir et je disparais, purement et simplement, dézingué par le terroriste sus-cité, ou par KarlOS lui-même sous prétexte d'opération non-conforme, ne riez pas, je suis sûr que cela vous est déjà arrivé. KarlOS doit considérer mon adresse comme libre.
Cette analogie fonctionne bien, et montre que la gestion de la mémoire par le système d'exploitation, cela ressemble à la gestion foncière en République Populaire de Chine.
Pour résumer, la gestion de la mémoire doit se faire par, minimum syndical, trois fonctions : allocation, réallocation et libération. Aujourd'hui, ce sera bien assez de travail, on n'en fera qu'une, et encore, mal : l'allocation de mémoire.
Oui. Une méthode radicale et infaillible existe, dépourvue de tout problème de segmentation, perte, disproportion, complexité. Elle n'a qu'un seul et unique problème : elle ne permet pas d'accéder à la mémoire.
Les systèmes d'exploitations, les vrais de la vraie vie, ont des méthodes difficiles et poussées pour allouer de la mémoire. Pensez donc : il s'agit, en gros, de savoir à tout instant si un octet particulier est utilisé ou pas. Si on utilise un bit par octet, c'est-à-dire que pour chaque octet, on stocke si oui ou non il est utilisé, on a besoin du huitième de la mémoire. Autrement dit, sur votre ordinateur disposant de 2 gigaoctets, il y a 256 mégaoctets pris rien que pour savoir si chaque octet est libre ou pas. Et encore, à ce niveau-là, on ne sait pas par qui : donc impossible de mettre à jour ces bits si ceux qui l'utilisent ne le font pas eux-même. Donc, zou, on dégage, pas la bonne méthode. C'est un problème actuel et difficile, dont la solution n'est ni parfaite ni visiblement unique.
Nous, on n'est pas des vrais. Nous, on est des rigolos, des fumistes et notre but est juste d'appréhender une possibilité pour le faire. Alors, autant qu'elle soit instructive et simple à mettre en oeuvre. Aussi allons-nous parler fumisterie, et donc herbe. Ah non, pardon, arbres.
Voici le premier concept de programmation qui soit un peu indépendant du support. Toute notre progression est partie d'à peu près rien, tout de même. Maintenant, nous comprenons mieux comment fonctionne un ordinateur. Mais nous n'avons vu que des choses à peu près inutiles au commun des développeurs. Il serait temps de s'y essayer.
Si vous avez tenté de parler à un vrai développeur d'assembleur, de VESA, d'interruption et de mode protégé, je gage qu'on vous a regardé avec des yeux ronds. Ca c'est dans le meilleur des cas, si vous avez causé avec un dinosaure du Fortran. Si c'était un vieux programmeur C, vous avez récolté le dédain et la condescendance. Et si vous avez à faire à un programmeur objet, si vous croyez en un dieu, remerciez-le chaudement d'être toujours en vie : ces gens ont une sainte horreur de la programmation bas niveau, qu'ils accusent de tous les maux. D'ailleurs, à ce propos.
Parce que si on ne réinventait pas la roue en permanence, on en serait toujours à les utiliser à l'horizontale. C'est parce que Linus Torvald a réinventé un noyau qu'on a Linux. Et qu'on refasse les choses en permanence permet de montrer qu'elles sont humainement faisables. C'est parce que beaucoup de personnes font des avions qu'on sait toujours les faire.
Donc, les vrais développeurs de la vraie vie utilisent des trucs, qu'on retrouve quel que soit le langage de programmation. Et, in fine, ça se retrouve en assembleur. Celui que nous allons aborder s'appelle un arbre.
Un arbre, ça a, en première approximation, des racines, un tronc, des branches, des branches, encore des branches, et des cochonneries au bout des branches. Comme nous sommes des informaticiens, nous avons la réputation d'être peu au fait des choses de la nature. Et bien, soyons à la hauteur de notre réputation et supprimons ce qu'on ne voit pas; exit les racines. Tant qu'à faire, comparons un tronc à une branche : oui, ça ressemble beaucoup quand même. Allez, on le prend en automne, quand il n'a plus ni feuilles, ni fleurs, ni fruits, ni futile future chose commençant par un f, et finalement, on obtient ça : un arbre, c'est une branche qui porte des branches, qui portent des branches, qui elles-même portent des branches, ou pas. Chaque branche peut porter des branches, ou ne pas en porter. Voici un arbre numérique. Pas très sexy, mais un outil intéressant. Il y a un vocabulaire particulier pour ces arbres. La branche qui est au ras du sol s'appelle la racine. Oui, c'est un terme dévoyé par rapport à une vraie racine, mais on est comme ça, nous les informaticiens : la botanique, c'est à dévoyer. Chaque branche s'appelle aussi un noeud. La racine est donc un noeud, le noeud-racine. Oui, c'est lourd. Chaque branche qui part d'une autre branche est un fils de cette branche. C'est un noeud-fils. La branche qui a des fils est, du coup, un père : le noeud-père. Il n'y a malheureusement pas de noeud qui soit juste un noeud, donc pour les noeuds-noeud, vous repasserez, merci.
Si on a plusieurs noeuds-racine, on dispose d'une forêt. Tout à fait, on commence la forêt à deux arbres.
On peut décider arbitrairement qu'une branche ne peut avoir que deux fils au plus. On a alors défini un arbre binaire. Et tout arbre peut se réduire à un arbre binaire. Vous m'en ferez la démonstration.
Ah, malloc. Quelle étoile ! Quel phare éternel au firmament obscur du ciel pesant sur les épaules chastes du développeur ! Quel éclat, quel guide vers la nativité d'un programme fonctionnel ! J'espère que j'en fais trop, là.
malloc. Comme Memory ALLOCation. Allocation de mémoire. La base. La brique essentielle. On en était encore à bidouiller avec sa lampe à souder que malloc existait déjà. Les interfaces graphiques étaient encore inconcevables que malloc était là. Cette fonction a accompagné les vieux de la vieille aussi sûrement que ceux-ci accompagnaient l'empereur. Et, comme nos vénérables ancêtres, la jeune garde veut la cacher, la supprimer, la faire disparaître. Sauf que la vieille est essentielle, vitale, indispensable. Les jeunots ne font que la planquer, en fait. Elle existe toujours, même maquillée comme une voiture volée au travers des new, les afficionados du C++ apprécieront.
Bref, malloc est la fonction que nous allons tenter. Je n'en changerai pas le nom, tellement elle est essentielle.
Tout le monde s'en doute, malloc utilisera, quelque part, un arbre. Je me permets de préciser qu'a priori, pour un vrai système d'exploitation, ce n'est pas comme ça qu'il faut faire. Nous avons un malloc à faire dans un système d'exploitation en mousse et nous devons progresser en assembleur, nous allons donc en profiter pour toucher du doigt les arbres.
Première hypothèse : il sera demandé à malloc une quantité de mémoire suffisante pour que le nombre de blocs demandés soit négligeable devant la taille totale disponible. Seconde hypothèse : le gaspillage n'est pas répréhensible.
La mémoire va être représentée par une forêt. Chaque arbre de cette forêt représente un espace contigu, soit une ligne de la carte du chapitre 12. Un arbre est constitué d'un seul noeud comme point de départ. Ce noeud est un espace de x bits.
Soit x = 160. Notre malloc est en 32 bits, les adresses et tailles mémoire sont donc de 32 bits pour traiter toutes les possibilités. Toutes ces adresses, je vais les appeler des pointeurs, parce que j'en parle comme ça depuis des années, l'habitude est trop forte. L'adresse du noeud-fils gauche est donc le pointeur sur le fils gauche.
Disons que malloc va fonctionner comme cela : on l'appelle avec la taille demandée dans ECX. Au retour, dans l'accumulateur EAX, malloc va placer l'adresse qu'il a trouvée. Par ailleurs, l'initialisation de EAX aura l'amabilité d'être faite avant l'appel à malloc. Et l'adresse invalide sera -1. La forêt est stockée dans le deuxième segment, adresse 0. On lit ce qu'il y a à cette adresse, première racine de la forêt. Si c'est -1, merci, au revoir. Sinon, on va regarder ce qui se passe dans cet arbre. On l'affiche, d'abord. Ensuite, on lit le contenu du noeud. La dernière valeur est la taille de la mémoire réservée dans cet arbre. On l'ajoute à ECX. Si le résultat est supérieur à EDX (qui contient la taille du segment), alors il faut en trouver un autre : on n'a pas assez de place dans celui-ci. Sinon, nous allons trouver dans cet arbre le bon noeud. Pour ce faire, nous comparons la taille souhaitée à la moitié de la taille disponible. Si la taille souhaitée est plus grande que cette moitié, on va prendre tout le bloc. Sinon, on regarde fils par fils, en profondeur d'abord.
L'ensemble du code de ce chapitre se trouve ici :
Tuto13