Identity mapping, Demand paging et Copy on Write

Aller encore un petit tour avec des techniques qui utilise la mémoire virtuelle, aujourd'hui je vais vous présenter trois concepts vraiment très simple mais aussi très efficace.
Les deux derniers servent notamment à réduire la mémoire physique utilisé à un moment donnée ce qui n'est pas si mal puisque celle ci est beaucoup plus limité que la mémoire virtuelle.
Je ne vous l'avais peut être pas encore dit mais chaque processus à sa propre mémoire virtuelle d'ailleurs c'est pour ça qu'il ne peut pas accéder à la mémoire des autres processus or tout les processus partagent la même mémoire physique et la on voit bien que la mémoire physique est beaucoup plus utilisé que la mémoire virtuelle.


Bon alors commençons par l'identity mapping, concepts le plus simple qu'il existe, il s'agit d'un mapping à l'identique de la mémoire physique vers la mémoire virtuelle. Dans linux, l'identity mapping est utilisé pour l'espace noyau qui est le dernier giga de la mémoire virtuelle c'est à dire que 3G + x en mémoire virtuelle correspond à x en mémoire physique ceci facilite d'autant plus les manipulations de mémoire virtuelle. Cependant ont se heurte à un petit problème, comme l'espace noyau ne fait que 1G alors on ne pourra accèder qu'au premier giga de la ram. En fait ce qui ce passe dans linux c'est que les 128 derniers Mo sont réservés pour mapper le reste de la mémoire physique donc si le noyau à besoin d'un emplacement mémoire au dessus des 1G de la ram il va utilisait ces 128 derniers Mo pour mapper mais bon c'est top comme solution, il y a une autre solution c'est de donner 2G à l'espace noyau et 2G à l'espace user comme pour windows si je ne me trompe pas, bon le problème c'est qu'on diminue l'espace utilisateur et comme toute les librairies dynamiques sont mapper dans les 2G de l'espace utilisateur il vaut mieux ne pas en charger trop sinon il ne nous restera plus de mémoire mais bon il faut faire un choix soit on veut accéder à toute la mémoire physique soit on veut plus de mémoire virtuelle.


Bon maintenant passons à un premier concept qui va permettre d'économiser dans un premier temps la mémoire physique et donc on aura moins besoin de faire de manipulation de swap et les performances en seront améliorées.
Ce concept tout comme l'identity mapping est vraiment tout simple, en fait on va allouer l'espace mémoire que le programme à besoin en mémoire virtuelle mais pas en mémoire physique en fait il n'y aura pas d'association entre la mémoire virtuelle et la mémoire physique.
Voyons ça un peu plus en détail, la première chose que le programme va faire c'est qu'il va executer la première instruction de code ( logique non ? ) donc à ce moment là la première page virtuelle de code a été allouée ( ça a été fait par le loader quel qu'il soit -- elf, PE ... ) mais comme je l'ai dit aucune association avec la mémoire physique n'a été fait donc pagefault, a ce moment là l'OS va s'apercevoir qu'il n'y a pas d'association entre mémoire virtuelle et mémoire physique pour cette page donc normalement il devrait renvoyait un segfault ou accès violation sauf qu'il se rend compte que la mémoire physique a été alloué ( grâce à des structures internes ) et on arrive dans une situation de demand paging, il va alors copier les 4 premiers Ko de code grâce à fichier exécutable, les copier dans une page physique et faire une association entre mémoire physique et mémoire virtuelle pour cette page. Ensuite il réexecute la première instruction et là pas de problème puisqu'il y a association entre mémoire virtuelle et mémoire physique et ce jusqu'à ce qu'il sorte de cette page et rebellote copie du code dans une page physique et association entre mémoire virtuelle et mémoire physique sur la page en question, le même principe est appliqué pour les données.
Donc en fait on copie l'exécutable au fur et à mesure de son exécution et on retarde au plus possible les manipulations du swap.


Enfin voyons le Copy on Write souvent abrégé COW, qui est aussi une façon d'économiser l'utilisation de la mémoire physique.
Seulement ce concept ne s'applique seulement dans un cas précis celui du fork().
Bon déjà un fork c'est quoi ?
Un fork c'est tout simplement une duplication d'un processus, on dit que le créateur du second processus est le père et que le processus ainsi crée est le fils.
En fait ce qui se passe lors d'un fork c'est que le processus n'est pas dupliqué à partir de l'exécutable de base, sinon il y aurait deux fois le même code et bien entendu c'est absurde. Seul l'espace d'adressage ( la mémoire virtuelle avec ces associations avec la mémoire physique ) est dupliqué.
Seulement voila pour le code cela ne posera pas de problème puisque le code est en lecture seule seulement pour les données ça sera problématique puisque les deux processus n'auront pas forcément exactement les mêmes données au même moment, en général lors d'un fork on exécute un code différent pour le père et pour le fils mais même si le code exécuté était le même vu qu'on est dans un système multi-tâche, les deux processus s'exécute en même temps mais pas au même moment donc il y aura un conflit de données.
Il y a deux possibilités, soit la section ( une section est ensemble de pages ayant les même flags ) est en shared et dans ce cas là on laisse les deux processus partager cette section et après il se débrouille, soit la page est en private est la on utilisera le Copy on Write.
Le truc c'est que les sections private seront mis en lecture seule pour le fils donc lorsqu'il essayera d'écrire dans cette section ... pagefault, donc l'OS prend la main et se rend compte grâce à des structures internes que la page correspondante n'est pas réellement en lecture seule et qu'il s'agit d'un COW donc il va copier la page ( et non pas la section entière ) sur une nouvelle page physique changer l'association avec la mémoire virtuelle et relancer l'écriture.
Donc tant que le processus n'écrira pas sur une section private il n'y aura pas de nouvelle page physique d'allouer.


Voila pour ces trois concepts très intéressant que Linux implémente complètement ( je ne sais rien à propos de Windows si quelqu'un sait quelque chose merci de me le signaler ) et donc qui en améliore les performances et qui facilite la manipulation de l'espace kernel pour ce qui est de l'identity mapping.
Je pense qu'avec cet article j'ai fait le tour de ce que je pouvais dire sur la mémoire virtuelle en tout cas avec mes connaissances actuelles.
Dans tout les cas à bientôt dans un prochain épisode.

EmptyWorkingSet

Bon alors il y a pas longtemps j'ai découvert un soft qui s'appelle Firefox Ultimate Optimizer qui permet de libérer la mémoire non utilisé par Firefox car comme beaucoup le savent dans le version 2.0 il y a pas mal de fuite de mémoire. D'après les dev de Mozilla plus de 350 sources de fuites de mémoire ont été corrigées dans la version 3.0. Donc c'est un soft très intéressant car il n'est pas rare que mon Firefox atteigne les 200Mo d'utilisation de mémoire et dès que je lance le soft il redescend entre 5 et 10Mo ( impressionnant n'est ce pas ). D'après Korben, tout l'intérêt du soft réside dans la fonction EmptyWorkingSet() qui fait tout le boulot mais comme il l'a dit il fallait y penser. Donc sans plus attendre je m'empresse d'aller trouver le secret de cette fonction ( moi qui suit un fana de ce genre de fonction avec surement un peu de mémoire virtuelle ) dans les sources de reactos.

BOOL STDCALL EmptyWorkingSet(HANDLE hProcess)
{
NTSTATUS nErrCode;
QUOTA_LIMITS qlProcessQuota;

/* query the working set */
nErrCode = NtQueryInformationProcess
(
hProcess,
ProcessQuotaLimits,
&qlProcessQuota,
sizeof(qlProcessQuota),
NULL
);

/* failure */
if(!NT_SUCCESS(nErrCode))
goto fail;

/* empty the working set */
qlProcessQuota.MinimumWorkingSetSize = -1;
qlProcessQuota.MaximumWorkingSetSize = -1;

/* set the working set */
nErrCode = NtSetInformationProcess
(
hProcess,
ProcessQuotaLimits,
&qlProcessQuota,
sizeof(qlProcessQuota)
);

/* success */
if(NT_SUCCESS(nErrCode))
return (TRUE);

fail:
/* failure */
SetLastError(RtlNtStatusToDosError(nErrCode));
return (FALSE);
}

Hum apparemment tout ce passe dans NtSetInformatioProcess avec un ProcessInformationClass à ProcessQuotaLimits, donc allons voir ça de plus près :

NTSTATUS
NTAPI
NtSetInformationProcess(IN HANDLE ProcessHandle,
                      IN PROCESSINFOCLASS ProcessInformationClass,
                      IN PVOID ProcessInformation,
                      IN ULONG ProcessInformationLength)
{
  PEPROCESS Process;
  KPROCESSOR_MODE PreviousMode = ExGetPreviousMode();
  ACCESS_MASK Access;
  NTSTATUS Status;
  HANDLE PortHandle = NULL;
  HANDLE TokenHandle = NULL;
  PROCESS_SESSION_INFORMATION SessionInfo = {0};
  PVOID ExceptionPort;
  PAGED_CODE();

  /* Verify Information Class validity */
#if 0
  Status = DefaultSetInfoBufferCheck(ProcessInformationClass,
                                     PsProcessInfoClass,
                                     RTL_NUMBER_OF(PsProcessInfoClass),
                                     ProcessInformation,
                                     ProcessInformationLength,
                                     PreviousMode);
  if (!NT_SUCCESS(Status)) return Status;
#endif

  /* Check what class this is */
  Access = PROCESS_SET_INFORMATION;
  if (ProcessInformationClass == ProcessSessionInformation)
  {
      /* Setting the Session ID needs a special mask */
      Access |= PROCESS_SET_SESSIONID;
  }
  else if (ProcessInformationClass == ProcessExceptionPort)
  {
      /* Setting the exception port needs a special mask */
      Access |= PROCESS_SUSPEND_RESUME;
  }

  /* Reference the process */
  Status = ObReferenceObjectByHandle(ProcessHandle,
                                     Access,
                                     PsProcessType,
                                     PreviousMode,
                                     (PVOID*)&Process,
                                     NULL);
  if (!NT_SUCCESS(Status)) return Status;

  /* Check what kind of information class this is */
  switch (ProcessInformationClass)
  {
      /* Quotas and priorities: not implemented */
      case ProcessQuotaLimits:
      case ProcessBasePriority:
      case ProcessRaisePriority:
          Status = STATUS_NOT_IMPLEMENTED;
          break;
  ...
  }
  ...
}

Rho zut alors reatos n'implémente pas encore cette fonctionnalité, en attendant si un reverser kernel windows dans l'âme avec quelques connaissances en mémoire virtuelle sous windows veut bien nous éclairer avec ce syscall ( perso j'y connais rien à ces syscall windows ni comment les tracer ), je sais que neitsabes avez commencé avec quelques ProcessInformationClass mais pas celui la donc voila.

Bon sinon ce que je pense de cette fonction, elle réside surement tout simplement dans un système de swap à la con qui vire les pages physiques les moins utilisées sans touchés aux pages virtuelles juste au cas où on en ait encore besoin sinon Access violation dans ta face et après tout 2Go en espace user de mémoire virtuelle ya de quoi faire alors que généralement la ram ne dépasse pas souvent les 1Go et il y a pas mal d'autre chose dans la mémoire physique alors que la mémoire virtuelle est spécifique au processus.

Dans tout les cas c'est une fonction sympa, on pourrait faire un petit tools qui fassent ça sur tout les process et pas seulement firefox car je suis sur qu'il doit bien y avoir dans d'autre process des fuites de mémoire.

http://msdn.microsoft.com/en-us/library/ms682606.aspx

Have fun with this function !!!

Une autre façon de voir les listes chainées

Après une introduction aux listes chainées pour ceux qui ne savent pas ce que c'est, je vous présenterez une façon plus générique ( en tout cas selon moi ) et bien plus originale d'implementé cette structure de donnée qui est tirée du code de linux.

Avant tout, qu'est ce qu'une liste chainée et pourquoi on l'utilise ?

Et bien une liste chainée c'est une structure de donnée ( le mot clé struct en C ) qui permet de lier entre eux plusieurs données, un peu comme un tableau mais de façon beaucoup plus dynamique.
Un tableau de structure statique pourrait faire la même chose mais avec l'inconvénient que la longueur du tableau est fixé à la compilation et ne pourra pas être adapter en fonction des besoins.Prenons par exemple le cas d'une liste de processus, on pourrait fixer le tableau à 500 entrée ce qui a peut de chance d'arriver mais peut tout de même y arriver et puis on utiliserait de la mémoire pour rien ( environ 450 structures inutilisées la plupart du temps ).
Pour remédier à la taille du tableau, on pourrait utiliser un tableau dynamique avec le jeu de fonctions malloc()/realloc()/free() pour changer dynamiquement la taille du tableau. Mais la encore il se pose un autre problème c'est lorsqu'on a besoin de supprimer une structure, concrêtement on ne peut pas vraiment la supprimer, on peut la réinitialiser à 0 en jusqu'à ce que quelqu'un d'autre en ait besoin mais la encore on utilise de la mémoire pour rien puisqu'elle ne sera pas utilisée pendant un certain moment et puis imaginer que je ne sais pour qu'elle raison on ait besoin de 1000 structures et que soudain on ne s'en sert plus que d'une dizaine et bien là c'est vraiment ce qu'on apelle du gaspillage de mémoire. On aurait éventuellement la possibilité de faire un memmove() puis un realloc() mais le memmove est très coûteux si jamais on a beaucoup de données.
Donc une autre possibilité s'offre à nous c'est de faire une structure de données dans là qelle on ferait un ou deux champ(s) ( suivant que c'est une liste doublement ou simplement chainée ) qui sont de même type que la structure elle même.
Ces champs seront des pointeurs sur la structure précédente et la structure suivante pour le cas d'une liste doublement chainée et pour le cas d'une liste simplement chainée il n'y a que le champ vers la strucuture suivante ce qui nous permet bien de faire une liste de cette même structure.

La façon classique de déclarer une liste chainée c'est donc quelque chose qui ressemble à ça :

struct linked_list
{
// nawak
struct linked_list *prev, *next;
};

Voila donc une liste doublement chainée, pour une liste simplement chainée il n'y a que le champ next et bien évidement les données sont à la place de "nawak".

Voila en image à quoi ça ressemble des listes simplement et doublement chainées :



L'avantage des listes chainées c'est qu'on peut facilement ajouter ou supprimer un élément de la liste en agisant simplement sur les champs next et prev.
Par exemple, on a trois structures et on veut supprimer la seconde alors il suffit de faire pointer le champ next de la première vers la troisième et le champ prev de la troisième vers la première et on peut alors libérer la mémoire allouer pour la seconde structure.


Nous allons donc maintenant voir comment les listes chainées sont implémentées dans linux car c'est vraiment très intéressant à voir et ça ressemble beaucoup à stdarg.h qui utilise des macros avec des adresses qui n'ont l'air de correspondre à rien.
Enfin plein de truc marrant qui sont au final très pratique et comme je le disais en introduction l'implémentation de linux est bien plus générique que l'implémentation "classique".

Bon alors avant de partir plus loin voyons ensemble la définition d'une liste chainée dans include/linux/list.h :

struct list_head {
struct list_head *next, prev;
};

Wtf ? Euh elles sont où les données ?

C'est justement ça la particularité, au lieu que la structure de donnée ait des liens sur elle même, elle a un champ vers cette structure list_head. Et selon moi ceci fait que cette définition des listes chainées en font des listes chainées plus génériques que les autres.

Bon alors voyons maintenant la mise en place de ces listes chainées un peu particulière :

struct mastructure
{
// nawak

struct list_head list;
}

Bon c'est un peu particulier parce qu'on a pas l'habitude de l'apprendre comme ça et il y a certaines choses qui peuvent être un peu compliquer à comprendre.

Une petite image pour voir à quoi ça ressemble :



On dispose de plusieurs macros pour créer ou initialiser une liste chainée :

#define LIST_HEAD_INIT(name) { &(name), &(name) }

#define LIST_HEAD(name) \
struct list_head name = LIST_HEAD_INIT(name)

Bon rien de compliquer, on crée une variable avec le nom passé en paramètre de la macro et on initialise la liste pour que les champs prev et next pointent sur la liste elle même, on voit déjà que ce sont des listes circulaires.
Bon en général on n'aura pas besoin de créer de liste, on va juste l'initialiser.

Voila, je ne vais pas passer en revu toutes les macros et fonctions, si vous voulez savoir comment ça marche aller voir les sources directement ( c'est l'avantage du libre ^^ ).
Je vais vous expliquez maintenant le point le plus difficile qui est bien entendu : "Comment fait t'on pour accèder à notre structure avec ces listes chainées ?".

En fait c'est une petite astuce qui est vraiment toute simple mais encore faut t'il y penser. Récapitulons ce que nous avons, on a notre structure et dans celle ci ont à notre list_head, il faut donc qu'on se débrouille avec seulement ça. L'astuce est de soustraire à l'adresse de la list_head ( c'est bon on l'a ) son offset au sein la structure ( on l'a aussi mais de façon un peu plus détourné ) et comme ça on retombe sur nos pattes tels un félin avec l'adresse du début de la structure avec un petit transtypage et c'est réglé.
Bon maintenant le tout c'est de savoir comment on récupère l'offset d'un membre à l'intérieur d'une structure ( on ne va quand même pas hardcoder l'offset pour chaque structure et puis imaginer si on rajoute un membre ).
Heureusement pour nous il existe encore une autre macro très pratique qui fait ça très bien dans include/linux/stddef.h :

#define offsetof(TYPE, MEMBER) ((size_t) &((TYPE *)0)->MEMBER)

Et c'est la qu'on voit qu'on manipule des adresses qui ne correspondent à rien =p.
Bon en clair on chope l'adresse du membre et comme l'adresse de base de la structure est 0 on se retrouve bien avec notre offset.

Maintenant qu'on à l'offset, on peut faire notre soustraction pour trouver l'adresse de base de la structure, voyons voir comment ils ont fait ça dans include/linux/kernel.h :

/**
* container_of - cast a member of a structure out to the containing structure
* @ptr:       the pointer to the member.
* @type:   the type of the container struct this is embedded in.
* @member:    the name of the member within the struct.
*
*/
#define container_of(ptr, type, member) ({            \
const typeof( ((type *)0)->member ) *__mptr = (ptr);    \
(type *)( (char *)__mptr - offsetof(type,member) );})

Avec les explications pour chaque membre en anglais.

Bon ensuite dans /include/linux/list.h, on a un alias de cette fonction pour une utilisation spécifique aux listes :

#define list_entry(ptr, type, member) \
contaier_of(ptr, type, member)

No comment.


Et bien voila c'est la fin de cet article, je voulais vous présentez cette structure car je la trouve très intéressante et surtout originale ( j'aime bien l'originalité ).
Bien entendu il existe d'autres implémentation de listes chainées génériques, je pense notamment à la glib avec sa GList qui utilise un pointeur sur void comme donnée et donc on peut faire ce qu'on veut avec. Cependant l'implémentation de linux en plus d'être générique est très originale puisque avant de la connaître je pensais qu'il n'existait qu'une seule façon de faire des listes chainées ( comme tout le monde je pense ) mais je me tromper bien entendu.
De plus on voit qu'il y a plein de macro amusante et qu'on peut faire vraiment beaucoup de chose avec.

Et bien apparemment il existe la même chose avec windows ( merci Ivanlef0u ), voici un lien vers la msdn pour en savoir plus :
* http://msdn.microsoft.com/en-us/library/aa489548.aspx

Sur ce je vous dis à bientôt pour un prochain article.