Architecture des systèmes informatiques

Organisation de la mémoire virtuelle des processus

Enjeux de compréhension

Nous avons décrit le phénomène de segmentation assuré par la

P.M.M.U. et le système pour virtualiser la mémoire et permettre
ainsi de sécuriser les adresses physiques tout en organisant le
partage des mémoires.

On a vu avec le Little thinker qu’un programme en exécution

manipulait un compteur ordinal indexant des lignes de code machine
exécutables.

On a vu aussi que le C (comme de nombreux autres langages)

utilisait une pile d’exécution pour gérer les appels de fonctions.

Il y a bien plus que ça dans la mémoire virtuelle d’un

processeur !
Plage de valeur

Dans un processus et par commodité, toute adresse sur 64 bits (si

votre système est aussi 64 bits) est potentiellement utilisable.
I Charles Antony Richard Hoare a tout de même inventé le
pointeur NULL qui est, par convention, invalide (son erreur à
un milliard de dollars).
I Il peut y avoir des décalages et des masques binaires car 264 ,
c’est environ 16 milliards de milliards (et quelques brouettes
pleines). Le système n’est pas contraint de partir de 0 pour
arriver à 264 − 1
I Il va falloir y caser la pile, le tas, le code source mais pas que. . .
Carte de la mémoire virtuelle

Une carte de la mémoire (Wikipédia)

Autre carte de la mémoire virtuelle

Schéma de la mémoire virtuelle (2004)

Troisième carte de la mémoire virtuelle

Mémoire virtuelle (site web Hackndo)

Quatrième carte de la mémoire virtuelle

Mémoire virtuelle (site web Yann Langlois)

Et bien alors, qui a raison ?

Calmez-vous. . . Ils ont tous plus ou moins raison. . .

I Certains sont plus précis que d’autres.
I Certains donnent des adresses, d’autres pas.
I Le système est mis à jour régulièrement, ça change !
I La transition du 32 bits vers 64 bits est jeune (10-15 ans).
I Comprendre ce qu’il se passe en interne pour mieux organiser,
programmer et déboguer est finalement le seul objectif louable.
Monsieur, je ne crois que ce que je vois. . .

Pas de problème, ça va piquer un peu mais avec un petit code qui

déconne, on doit pouvoir extraire les informations.

#define MAX_MSG 256

#define SIZE_MAP_MAX 50

typedef struct virtual_addr{

void* addr; /* address of a variable */
char msg[MAX_MSG]; /* description for this variable */
}V_addr;

typedef struct virtual_map{

V_addr tab[SIZE_MAP_MAX]; /* array of all virtual addr */
int size; /* current size */
}V_map;

Voici un ensemble de couple (adresse virtuelle, description). Faisons

notre propre carte de la mémoire !
Monsieur, je ne crois que ce que je vois. . .

Voici un peu une fonction clé du programme qui va faire notre carte
mémoire ! La fonction ajoute un couple (adresse virtuelle, message
décrivant l’élément) dans notre carte de la mémoire.

void add_in_map(V_map* map, const void* addr, const char* msg){

map->tab[map->size].addr = addr;
strcpy(map->tab[map->size].msg, msg);
map->size++;
}

Pour une adresse (unsigned long int en 64 bits), une simple

affectation suffit. Pour le message, une véritable copie de chaîne est
nécessaire.
Monsieur, je ne crois que ce que je vois. . .
int cmp_v_addr(const void* a1, const void* a2){
const V_addr* va1 = (const V_addr*)a1;
const V_addr* va2 = (const V_addr*)a2;

if ((char*)va1->addr > (char*)va2->addr)

return 1;
if ((char*)va1->addr < (char*)va2->addr)
return -1;
return 0;
}

void sort_v_map(V_map* map){

int i = 11;

add_in_map(map, &i, "Locale dans un sous appel");

qsort(map->tab, map->size, sizeof(V_addr), cmp_v_addr);
}

Au passage, comme on va trier une seule fois à la fin, on enregistre

l’adresse virtuelle de la variable locale i avant l’appel à qsort.
Monsieur, je ne crois que ce que je vois. . .
void display_v_map(V_map* map){
int i;
void* min = map->tab[0].addr;
void* max = map->tab[map->size-1].addr;
size_t dist_up;
size_t dist_down;

for(i=0 ; i<map->size ; i++){

dist_up = (char*)max - (char*)map->tab[i].addr;
dist_down = (char*)map->tab[i].addr - (char*)min;

if (dist_up < dist_down)

printf("%p : +%13lu : %s\n", map->tab[i].addr,
dist_up, map->tab[i].msg);
else
printf("%p : -%13lu : %s\n", map->tab[i].addr,
dist_down, map->tab[i].msg);
}}

Une astuce ici : suivant l’écart au min ou au max, on oriente les

offsets côté pile ou côté tas. . .
Il faut maintenant nourrir la carte !

I On a du code pour manipuler des couples (adresses,

description).
I On peut fabriquer un gros ensemble, le trier puis finalement
l’afficher.
I On va maintenant utiliser add_in_map à toutes les sauces
I variables globales (static)(const)(initialisées)
I argc, argv, argv[0], &argc, . . .
I allocation dynamique
I variable locale modifiable ou pas
I fonction des bibliothèques
I Un vrai bordel !
Monsieur, je ne crois que ce que je vois. . .

/* Initialized (static)(const) globals */

int glob_int = 1;
const int const_glob_int = 2;
static int static_glob_int = 3;
static const int static_const_glob_int = 4;

/* Non-initialized (static)(const) globals */

int glob_int_ni;
const int const_glob_int_ni;
static int static_glob_int_ni;
static const int static_const_glob_int_ni;

Ça ne serait pas des variables globales dégueulasses ? Y’en a

aussi. . . .
Monsieur, je ne crois que ce que je vois. . .

add_in_map(&map, &glob_int, "Globale");

add_in_map(&map, &const_glob_int, "Globale constante");
add_in_map(&map, &static_glob_int, "Globale statique");
add_in_map(&map, &static_const_glob_int,
"Globale statique constante");

add_in_map(&map, &glob_int_ni, "Globale non init.");

add_in_map(&map, &const_glob_int_ni,
"Globale constante non init.");
add_in_map(&map, &static_glob_int_ni,
"Globale statique non init.");
add_in_map(&map, &static_const_glob_int_ni,
"Globale statique constante non init.");

Poussez-pas dans le fond, il y aura de la place pour tout le monde !

Monsieur, je ne crois que ce que je vois. . .

Bon, c’est le moment de compiler et exécuter. . .

nborie@bayer:$ gcc -o test mem_map.c -Wall -ansi
mem_map.c: In function ‘add_in_map’:
mem_map.c:34:28: warning: assignment discards ‘const’
qualifier from pointer target type [-Wdiscarded-qualifiers]
map->tab[map->size].addr = addr;
^
nborie@bayer:$
Oui euhhh. . . Ce warning. . . Tout ça. . . Euhh. . .
Tais-toi gcc, c’est pour la bonne cause. Tagguer comme const la
structure n’est pas une bonne idée à cause des swaps opérés dans
qsort. . .
Carte de la mémoire personnelle
nborie@bayer:$ ./test
0x5590f37887ea : + 0 : Adresse d'une fonction du programme
0x5590f3788946 : + 348 : Adresse d'une autre fonction
0x5590f3788ac0 : + 726 : Adresse du main
0x5590f3788fe8 : + 2046 : Globale constante
0x5590f3788fec : + 2050 : Globale statique constante
0x5590f378902e : + 2116 : Chaine litérale (char *)
0x5590f37892cc : + 2786 : Locale statique constante
0x5590f398a010 : + 2103334 : Globale
0x5590f398a014 : + 2103338 : Globale statique
0x5590f398a018 : + 2103342 : Locale statique
0x5590f398a020 : + 2103350 : Globale statique non init.
0x5590f398a024 : + 2103354 : Globale statique constante non init.
0x5590f398a028 : + 2103358 : Locale statique non init.
0x5590f398a02c : + 2103362 : Locale statique constante non init.
0x5590f398a030 : + 2103366 : Globale constante non init.
0x5590f398a034 : + 2103370 : Globale non init.
0x5590f5488260 : + 30407286 : Alloué dynamiquement 1
0x5590f5488280 : + 30407318 : Alloué dynamiquement 2
0x7f801610fe80 : - 540820387147 : Adresse de printf
0x7f8016142070 : - 540820181851 : Adresse de malloc
0x7f8016161540 : - 540820053643 : Adresse de strcpy
0x7f8016239590 : - 540819168827 : Adresse de strlen
0x7ffe0178e4d4 : - 20215 : Locale dans un sous appel
0x7ffe0178e4fc : - 20175 : Adresse de argc
0x7ffe0178e500 : - 20171 : Locale
0x7ffe0178e504 : - 20167 : Locale constante
0x7ffe017918c0 : - 6923 : Chaine locale (char[20])
0x7ffe017918e0 : - 6891 : Chaine locale constante (char[20])
0x7ffe017919e8 : - 6627 : Adresse argv
0x7ffe017933cb : - 0 : Adresse argv[0]

On va lire ça en deux morceaux. . .

Carte de la mémoire personnelle : côté Pile
--- BIBLIOTHÈQUES CHARGÉES ---
0x7f801610fe80 : - 540820387147 : Adresse de printf
0x7f8016142070 : - 540820181851 : Adresse de malloc
0x7f8016161540 : - 540820053643 : Adresse de strcpy
0x7f8016239590 : - 540819168827 : Adresse de strlen
--- HAUT DE LA PILE D'APPEL : 20,3k / 8M ---
0x7ffe0178e4d4 : - 20215 : Locale dans un sous appel
0x7ffe0178e4fc : - 20175 : Adresse de argc
0x7ffe0178e500 : - 20171 : Locale
0x7ffe0178e504 : - 20167 : Locale constante
0x7ffe017918c0 : - 6923 : Chaine locale (char[20])
0x7ffe017918e0 : - 6891 : Chaine locale constante (char[20])
0x7ffe017919e8 : - 6627 : Adresse argv
0x7ffe017933cb : - 0 : Adresse argv[0]
--- BAS DE LA PILE : premier appel à main ---

Quand on ne déclare pas de grosses variables locales et quand on

passe les structures par adresse, on encombre pas la pile. C’est
beaucoup 8 Méga d’appels de fonctions !
Carte de la mémoire personnelle : côté Pile

I On remarque que la pile semble commencer à l’adresse

0x7fffffff ce qui donne un point au graphique de wikipédia !
I Il semblerait qu’entre 0xffffffff et 0x7fffffff, il reste de la place
pour mapping du noyau : 1 point pour hackndo.
I Quand on exécute plusieurs fois le programme, certaines choses
changent et d’autres pas. . . Effectivement, les bibliothèques
sont toujours chargées quelque part au milieu entre tas et pile.
(hackndo et L’ami Yann le mentionnaient mais l’ami yann est
le plus précis sur ce point. . . )
I Après, on pourrait faire un traçage plus violent de la pile mais
cela a été plus ou moins fait au cours précédant. . .
--- Zone text : code machine à la little Thinker ---
0x5590f37887ea : + 0 : Adresse d'une fonction du programme
0x5590f3788946 : + 348 : Adresse d'une autre fonction
0x5590f3788ac0 : + 726 : Adresse du main
--- Zone data : partie en read-only ---
0x5590f3788fe8 : + 2046 : Globale constante
0x5590f3788fec : + 2050 : Globale statique constante
0x5590f378902e : + 2116 : Chaine litérale (char *)
0x5590f37892cc : + 2786 : Locale statique constante
--- Zone data : partie modifiable ---
0x5590f398a010 : + 2103334 : Globale
0x5590f398a014 : + 2103338 : Globale statique
0x5590f398a018 : + 2103342 : Locale statique
--- Zone BSS : données non intialisées ---
0x5590f398a020 : + 2103350 : Globale statique non init.
0x5590f398a024 : + 2103354 : Globale statique constante non init.
0x5590f398a028 : + 2103358 : Locale statique non init.
0x5590f398a02c : + 2103362 : Locale statique constante non init.
0x5590f398a030 : + 2103366 : Globale constante non init.
0x5590f398a034 : + 2103370 : Globale non init.
--- Début du tas dynamique ---
0x5590f5488260 : + 30407286 : Alloué dynamiquement 1
0x5590f5488280 : + 30407318 : Alloué dynamiquement 2
--- Fin du tas ---
Carte de la mémoire personnelle : côté Tas

De ce côté, des points sont validés par les 4 graphiques tirés du web.
Quelque part, ils étaient, à peu de chose près, tous justes avec des
petites colorations suivant les auteurs.
I Au final, l’important n’est pas d’élire un gagnant et
d’apprendre par coeur sa carte. . .
I Faire des recherches et confronter l’information sont
importants.
I La durée de validité des informations en informatique est
toujours réduite car c’est une science JEUNE et ULTRA
ACTIVE.
I Se maintenir à la page et être capable de faire des expériences
pour maintenir son niveau de compréhension est un idéal à
viser.
Carte de la mémoire personnelle : côté Tas

I Mise à part la mémoire dynamique, de ce côté, tous les offsets

ne sont pas exécution dépendant. On appelle 50 fois le
programme et les écartements entre text, data et bss sont
TOUJOURS les mêmes.
I La zone text contient vraiment du code issu de la compilation
(partie de gcc qui génère le code machine).
I La zone data est scindée en deux : une partie en read-only
(segfault si tentative de modification) et une zone pour des
éléments statiques initialisés.
I La zone bss (by symbol) contient les éléments statiques non
initialisés à leur déclaration. Et les bits de cette zone sont
systématiquement initialisés à 0 (NULL pour les pointeurs, 0
pour les nombres, etc. . . ).
Travail du linker
I gcc -c compile sans linker. Cela signifie que ça prend en
argument du code source C (quatre boucles for imbriquées par
exemple) et cela génère un fichier objet qui contient du code
utilisant des primitives processeurs (quatre boucles for –> un
mélange affreux de sauts conditionnels).
I Quand un bout de code appelle une fonction extérieure, gcc -c
laisse un trou pour le linker. Exemple : il faudra appeler printf
ici, mais printf n’existe pas encore dans ce contexte.
I La compilation séparée (plusieurs appels à gcc -c) et
l’utilisation de tierces bibliothèques laissent des trous à remplir
par le linker un peu partout dans un code source.
I Dans la mémoire virtuelle du processus, tout est bien relié
correctement.
I Merci ld (man ld) pour ce travail de branchement (résolution
de symboles. . . ).
Allocation dynamique

Pour le système, c’est une zone contiguë croissante ou décroissante

mais enracinée en un endroit précis.
I Les primitives systèmes brk et sbrk permettent de positionner
une adresse virtuelle de fin de segment du tas. C’est moche !
I malloc (and friends !) est une stratégie d’exploitation du
segment contiguë mémoire. malloc et free minimisent
intelligemment les appels à brk/sbrk.
I L’idée d’un segment mémoire contiguë est ancienne et robuste
au bas niveau. Pas de raison que ça change.
I malloc a changé de nombreuses fois son implémentation ces 50
dernières années. Exploiter logiquement de manière optimale
un segment physique est champ ouvert actuel de la recherche
en informatique.
Allocation dynamique

I Malloc alloue des blocs sur le tas mais rajoute

systématiquement des headers à ces blocs.
I malloc(t) alloue très souvent un bloc de taille 8 + 8 + 8 × dt/8e
I 8 pour l’offset vers l’header du bloc précédant
I 8 pour l’offset vers l’header du bloc suivant
I 8 × dt/8e pour avoir un multiple de 8

I Si les adresses des blocs sont des multiples de 8, alors les trois
derniers bits valent toujours 000 alors !
I Les trois derniers bits des adresses sont des masques binaires
pour stocker des informations contextuelles (libéré/alloué, . . . )
Zone u

La zone u (pour zone user) se trouve dans le trou identifié avant la

zone text (entre 0xfff. . . et 0x7ff. . . ). Enfin. . . Elle s’y trouve
virtuellement, et, seul le noyau peut la voir.
I Le noyau alloue pour chaque processus une structure appelée
zone u, qui contient des données privées du processus,
uniquement manipulables par le noyau.
I La zone u contient des informations sensibles sur les processus
(droits, emplacement du PCB, emplacement vers la table des
régions accessibles au processus, cputime, . . . )
I Tout accès non système en lecture ou écriture donne une
segfault. Seul le noyau peut lire/écrire sur la zone u. Quelques
appels système peuvent permettre de visualiser certaines
informations.
Les segments de mémoires sont doublement indexés. . .

Double indexation des régions

Les segments de mémoires sont doublement indexés. . .

Alors là, c’est le boulot du système ! En tant qu’utilisateur, on ne

souhaite absolument pas manipuler ces mécanismes à la main. . .
Mais pourquoi le système procède-t-il de la sorte ?
I Ça lui permet de consigner qui peut manipuler quoi ?
I Ça permet de référencer un même segment pour deux
processus distincts (multi-threading).
I Ça permet de mettre en place la ré-entrance de manière
efficace. On place la glibc dans un segment en read-only et on
autorise plusieurs processus à référencer le segment. 1 printf en
mémoire physique mais plusieurs programmes qui le voit en
virtuel dans leur contexte.
Les segments de mémoires sont doublement indexés. . .
Une dernière ruse ultime du noyau Unix : les vaches (cows), enfin les Copy
On Write. . .

I Ça permet de diminuer énormément les besoins mémoires.

I La copy on write (cow) est un mécanisme de duplication
feignante.
I On clone un segment pour un autre processus (disons un père
et son fils. . . ), tant que le fils ne fait d’écriture, on lui fait lire le
segment de son père.
I À la première écriture (du père ou du fils), on déclenche le
mécanisme lourd de copie et on distingue enfin les deux
segments.
I Miracle : seulement un très petit nombre de segments partagés
a besoin d’une duplication effective (le père ou le fils peut
retourner avant. . . )

Cette stratégie de Copy On Write a besoin de cette double indexation pour

être safe. Les flèches bougent durant une dissociation. . . C’est une
technique qui simule de l’overcommitting (il y a plus de mémoires
distribuées aux processus que de réellement disponibles, et pourtant, ça
marche!)
La fin. . .
C’était le dernier cours vous présentant des concepts et mécanismes
venant du système. On fera d’autres choses les deux prochaines
semaines. . .
I Il s’en passe des choses dans un ordinateur. . .
I Erreur commune des informaticiens : croire que les O.S. sont
composés que de codes techniques élaborés conjointement avec
les fabriquants de semi-conducteur.
I Après ce cours : non, il y a en fait plein d’algorithmique dans
un système d’exploitation. La puissance et l’ergonomie de nos
ordinateurs actuels proviennent très largement des astuces
élaborées toutes ces années par des experts.
.: Le système n’est pas de la sous-informatique. Ce sont les
programmeurs ne connaissant pas le système qui produisent
des sous-programmes :.
(Po po po. . . po po. . . )