Processus Linux : La face de la pile utilisateur

Introduction

En regardant attentivement la pile des processus manipulés dans les derniers articles sur les petits processus et sur la visualisation d'un Copy On Write, force est de se poser quelques questions :

• Pourquoi le processus "fatiny" a-t-il deux pages de pile allouées ?
• Pourquoi la région de pile est-elle plus grande que ces 2 pages ?
• Quel rapport entre la taille de cette région de pile et la limite définie par ulimit ?
• etc.

Comme on s'intéresse exclusivement à la pile, pas besoin de programme minimaliste du point de vue du code...  On va donc dans cet article essayer d'observer le fonctionnement de la pile utilisateur d'un processus Linux, du point de vue taille, espace d'adressage, etc...  Les mécanismes d'utilisation par les compilateurs pour les appels de procédures ne seront pas abordés.

Conditions d'expérimentation

• Linux 3.5.0.17 de la distribution Ubuntu 12.10 (32 bits) dans une machine virtuelle VirtualBox
• Pour pouvoir comparer les résultats entre deux exécutions du programme de test, il est plus simple d'inhiber le mécanisme d'ASLR (echo 0 >/proc/sys/kernel/randomize_va_space)
• Outils d'observation: le shell script getpg.sh présenté et utilisé dans l'article sur le COW

Combien de pages au début de main?

On va utiliser un programme relativement simple qui va imprimer l'adresse de argc et d'une variable locale i, et déterminer l'adresse virtuelle de la page qui contient respectivement ces deux variables. Le programme réel est légèrement différent parce qu'il enchaine les différentes étapes que l'on va utiliser dans notre exploration.

unsigned int stkpg_argc; unsigned int stkpg_i; unsigned int stkpg; int main(int argc, char ** argv) {     int i;     stkpg_argc = ((unsigned int)&argc) & 0xFFFFF000;     stkpg_i    = ((unsigned int)&i) & 0xFFFFF000;     stkpg   = stkpg_i;         printf("argc address: %p stack page: %p\n", &argc, (void*)stkpg_argc);     printf("i    address: %p stack page: %p\n", &i, (void*)stkpg_i);     WAIT_NEXT();

Compilons, exécutons

fa$ gcc stack_layout.c -o stack_layout -static  fa$ ./stack_layout 1 argc address: 0xbffff1b0 stack page: 0xbffff000 i    address: 0xbffff180 stack page: 0xbffff000

Comme nous avons inhibé le mécanisme d'ASLR et que nous sommes sur une machine 32 bits, la pile se trouve juste en haut des 3GB et donc juste avant l'adresse 0xC000 0000. La page qui se trouve juste avant est donc 4096 octets avant (soit 0X1000): à l'adresse 0xBFFF F000.

So far, so good. Vérifions quelles sont les pages physiques allouées à la pile. Une page?

fa$ ./getpg.sh 3755 stack 3  3755 : Page 1 (stack) present (PFN: 0000b474) has count 1 3755 : Page 2 (stack) present (PFN: 0002a891) has count 1 3755 : Page 3 (stack) not present  fa$

Notre pile a déjà deux pages physique allouées!  A priori ce n'est probablement pas la faute de "WAIT_NEXT" qui fait un appel système read sur le fichier de descripteur 0. L'impact sur la pile sans être nul est de quelques octets...
Ah, oui! En fond de pile, le système inclut toutes les chaines des environnements, arguments et données auxiliaires (on reviendra sur ces données dans un autre article). Peut-on s'en débarrasser? On va utiliser un programme qui exécute son premier argument mais en évitant de transmettre l'ensemble des environnements.

/* code source de execit */ #include <unistd.h> int main(int argc, char ** argv, char ** envp) {     int res;     res = execvpe(argv[1], &argv[1], NULL);     perror("Cannot exec!");     return 1; }

Mettons  ce programme en œuvre:

fa$ ./execit ./stack_layout 1 argc address: 0xbffffe80 stack page: 0xbffff000 i    address: 0xbffffe50 stack page: 0xbffff000

Nos variables sont toujours dans la même page, mais elles sont beaucoup plus près du fond de pile que précédemment (0xe80 versus 0x1b0 pour argc). A-t-on toujours deux pages associées à notre pile?

fa$ ./getpg.sh 3799 stack 3 3799 : Page 1 (stack) present (PFN: 00028d5a) has count 1 3799 : Page 2 (stack)is not present 3799 : Page 3 (stack)is not present

Ah! On a gagné une page. En fait la deuxième page n'est pas directement liée aux variables d'environnement. La bibliothèque C exécute du code entre le point d'entrée du programme et l'appel à main. Ce sont les fonctions de la bibliothèque C qui, lorsque les environnements sont présents, ont besoin d'une deuxième page de pile. En clair, la pile a été plus grande qu'elle ne l'est au moment où l'on rentre dans le main.

Quelle est la taille de la région de la pile?

Si on regarde l'espace d'adressage du processus on obtient ceci:

fa$ cat /proc/3799/maps 08048000-080ef000 r-xp 00000000 08:01 268062     /home/fa/facepile/stack_layout 080ef000-080f1000 rw-p 000a6000 08:01 268062     /home/fa/facepile/stack_layout 080f1000-08115000 rw-p 00000000 00:00 0          [heap] b7ffe000-b7fff000 rw-p 00000000 00:00 0 b7fff000-b8000000 r-xp 00000000 00:00 0          [vdso] bffdf000-c0000000 rw-p 00000000 00:00 0          [stack] fa$ ulimit -s 8192 fa$

La  région mémoire utilisée pour la pile ne fait ni 1 page ni deux pages! Mais 0xC000 0000 - 0xBFFD F000, soit 0x21 000, et donc 33 pages, dont une seule est présente pour le moment. Pourtant la commande ulimit nous indique que la taille maximale de notre pile est de 8192 Kilo-octets. Ce qui nous fait théoriquement 2048 pages, et non pas 33!

Pourquoi 33? 

Dîtes 33? Pas sûr que ce soit pour s'assurer de la bonne santé de la pile ! D'autant plus qu'il n'est pas certain que les médecins finlandais demandent à leurs patients de dire 33. Linux  permet d'avoir  des chaines d'arguments et d'environnements à hauteur de 32 x 4 KB (voir ARG_MAX). Et il faut aussi fournir une page pour que le main puisse initialement travailler  d'où la région de 33 pages...

Que se passe-t-il

•  quand on accède à une page parmi les 33
•  quand on accède à des pages au delà des 33 premières

On peut le faire de différentes manières : un accès direct comme s'il s'agissait de mémoire "classique",  ou en forçant le sommet de pile à reculer (on peut appeler une procédure avec une très grosse variable locale, par exemple).

Normalement, on accède à la pile en décrémentant d'abord le pointeur de sommet de pile (%esp sur x86) .  Voir le commentaire dans le noyau Linux: "Accessing the stack below %sp is always a bug."
Mais, ici l'idée est de prendre des risques !

Accès à la première page de la zone de pile prédéfinie

On modifie notre programme pour qu'il accède à l'adresse la plus basse de la région mémoire de la pile. stkpg contenait l'adresse basse de la seule page de pile allouée. Pour accéder au début de la zone mémoire, il faut reculer de 32 pages soit 128 Kilo-octets.

printf("accessing to pre-mapped top of stack (low address)"            "132KB away from bottom (high address)\n");     stkpg -= (128 * 1024);     pt = (int *) stkpg;     *pt = 0xFAFAFAFA;     printf("Wrote one int at location: %p\n", pt);     WAIT_NEXT();

Apparemment, pas de souci pour accéder à cette zone mémoire sans avoir modifié le sommet de pile, voilà le résultat de l'exécution.

accessing to pre-mapped top of stack (low address)132KB away from bottom (high address) Wrote one int at location: 0xbffdf000

Observons les pages allouées pour la pile :

fa$ ./getpg.sh 3799 stack 3 3799 : Page 1 (stack) present (PFN: 00028d5a) has count 1 3799 : Page 2 (stack) is not present .... 3799 : Page 32 (stack) is not present 3799 : Page 33 (stack) present (PFN: 00038768) has count 1 fa$

Effectivement, l'accès s'est effectué sans problème et le système a alloué une page phsyique pour la première page de la région de pile. Les autres pages physiques n'ont pas été allouées.

Accès deux pages avant la région de la pile?

Que se passe-t-il si emporté par la confiance, on essaye d'accéder deux pages plus bas que le début défini de la région de la pile? Normalement, cet accès est compris dans la zone de 8192 Kilo-octets prévu pour la pile. Donc, le système devrait détecter qu'il s'agit d'une extension de la pile et résoudre cet accès en fournissant une nouvelle page physique.

printf("Attempting to access 2 pages lower than the pre-mapped top of stack\n");     stkpg -= (128 * 1024);     stkpg -= 8192;     pt = (int *) stkpg;     if (sigsetjmp(jmpbuf, 0) == 0) {         *pt = 0xFAFAFAFA;     } else {         printf("Access to %p has failed caught a SIGSEGV\n", pt);     }

On n'est jamais trop prudent...Définissons un handler de signal sur SIGSEGV. Le handler de signal effectue un siglongjmp... qui permet de rependre l'exécution dans la branche else du test ci-dessus.

Attempting to access 2 pages lower than the pre-mapped top of stack Access to 0xbffdd000 has failed caught a SIGSEGV

 Ouch! Donc un accès direct n'est pas reconnu comme une extension de pile, dès qu'on sort de la zone des 33 pages initiales. Un coup d’œil au fichier /proc/[pid]/maps confirme que rien n'a changé dans l'espace d'adressage de notre processus.

Une approche moins gourmande!

Si un accès direct deux pages avant la base de la pile génère une exception, que se passe-t-il si on est moins gourmand et que l'on génère un accès sur la page précédent le début courant de la pile?

printf("Attempting to extend stack one page at a time"            " (lowering address 1 page by 1)\n");     stkpg -= (128 * 1024);     if (sigsetjmp(jmpbuf, 0) == 0) {         for (cnt=0;;cnt++) {             stkpg -= 4096;             pt = (int*) stkpg;             *pt = 0xFAFAFAFA;         }     } else {          printf("Access to %p has failed caught a SIGSEGV after"                 " extending stack region by %d pages\n", pt, cnt);     }     WAIT_NEXT();

Idem,  on part de l'adresse valide la plus basse de la pile et on recule d'une seule page à la fois. En cas de problème, on récupère l'erreur grâce à notre handler de signaux. On devrait rencontrer une erreur, soit tout de suite (notre essai est considéré comme invalide par le noyau) soit quand on aura atteint la limite des 8192 Kilo-octets de la pile...

Attempting to extend stack one page at a time (lowering address 1 page by 1) Access to 0xbf7ff000 has failed caught a SIGSEGV after extending stack region by 2015 pages

Hey! Apparemment, ça marche, on peut étendre la pile  au delà des 132Kilo-octets initiaux (sans modifier le sommet de pile) à condition de créer les défauts de page sur la page précédant le début de la pile. Et on a alloué 2015 pages, au delà des 33 premières. Ce qui nous fait un total de 2048 pages soit 8192 Kilo-octets, ce qui correspond à la valeur renvoyée par ulimit!

Une fonction avec une très grande variable locale

Donc, on ne pourrait étendre la pile que petit à petit? En fait, nos tentatives précédentes ne sont pas orthodoxes dans le mesure où nous avons procédé à des accès directs sans avoir modifié la valeur courante du sommet de pile.

Effectivement, si on définit une fonction qui alloue un très grand tableau de caractères dans la pile et qu'on accède à l'adresse la plus basse de ce tableau, le système veut bien procéder alors à l'extension de la pile!

#define BIGSZ (8*1024*1024) - 8192 void big_local_variable_subroutine() {     char big_buf[BIGSZ];     big_buf[0]='f';     printf(" big_local_variable_subroutine, big_buf[0] at %p\n",            (int *)(((unsigned int)big_buf) & 0xFFFFF000)); }

Si on exécute cette séquence sur un processus qui n'a pas étendu sa pile page par page comme montré précédemment, on obtient:

Attempting to extend by calling a subroutine with large local variable (7MB) big_local_variable_subroutine, big_buf[0] at 0xbf801000

Regardons la carte du processus:

fa$ cat /proc/3799/maps 08048000-080ef000 r-xp 00000000 08:01 268062     /home/fa/facepile/stack_layout 080ef000-080f1000 rw-p 000a6000 08:01 268062     /home/fa/facepile/stack_layout 080f1000-08115000 rw-p 00000000 00:00 0          [heap] b7ffe000-b7fff000 rw-p 00000000 00:00 0 b7fff000-b8000000 r-xp 00000000 00:00 0          [vdso] bf801000-c0000000 rw-p 00000000 00:00 0          [stack] fa$

Donc notre pile a bien été agrandie. Si on regarde les pages allouées:

fa$ ./getpg.sh 3799 stack 3 3799 : Page 1 (stack) present (PFN: 00028d5a) has count 1 3799 : Page 2 (stack) is not present .... 3799 : Page 2046 (stack) is not present 3799 : Page 2047 (stack) present (PFN: 0002f497) and has count 1 fa$

Donc le système sait allouer des pages très loin après les 132Ko initiaux quand il s'agit d'un accès sur une variable locale mais pas quand on déréférence un pointeur quelconque! La différence étant que les variables locales sont accédées par déplacement  par rapport à la "frame" courante de la pile (%ebp). Et ces adresses sont normalement plus hautes que le sommet de pile (%esp).

Patouillons allègrement et sans vergogne le sommet de pile!

Donc, si on reprenait notre tentative d'accéder deux pages plus bas que les 132 Ko initiaux, mais en ayant pris soin de modifier la valeur du registre de sommet de pile au préalable, nos accès précédemment illégitimes, deviendraient-ils acceptables par le système?

Bon, c'est pas propre du tout. Ames sensibles s'abstenir!

printf("Attempting to move stack pointer prior accessing page in stack\n");     stkpg -= (128 * 1024);     for(cnt = 1; ; cnt++) {         stkpg -= (4*4096);         __asm__             (                 "  movl     %0,%%esp   \n"                 "  movl     %0,%1   \n"                 : "=r" (pt)                 : "r" (stkpg)             );         if ((cnt % 128) == 0) printf("moved by 512 pages (cnt = %d)\n", cnt);         if (sigsetjmp(jmpbuf, 0) == 0) {             *pt = 0xFAFAFAFA;         } else {             printf("Access to %p has failed caught a SIGSEGV after moving by %d pages\n", pt, 4*cnt);             break;         }    }

On essaye de reculer de 4  pages à chaque itération de la boucle. mais au passage on change la valeur de %esp comme nécessaire. Et on produit une trace toutes les 128 boucles (128 x 4 => 512 pages) .Tous les accès calculés par le compilateur vont  être fortement perturbés. En définissant les variables comme étant globales et non plus locales, l'extrait de code ci-dessus fonctionne... Ça reste à fuir!

Attempting to move stack pointer prior accessing page in stack moved by 512 pages (cnt = 128) moved by 512 pages (cnt = 256) moved by 512 pages (cnt = 384) Access to 0xbf7ff000 has failed caught a SIGSEGV after moving by 2016 pages

Épargnons nous la visite de la cartographie de l'espace d'adressage.  Elle est conforme à ce que l'on attend. Un coup d’œil aux pages allouées, réserve une surprise! Il y a deux pages allouées toutes les 4 pages. Hmmm, probablement, l'appel à sigsetjmp! Il aurait fallu le faire une fois pour toute plutôt que le faire à chaque itération!

Mais nous avons confirmé expérimentalement que dans le traitement d'un défaut de page relatif à la pile utilisateur, une fois dépassé les 132Ko initiaux, le sommet de pile était effectivement pris en compte. Il faudrait aller vérifier dans le code source du noyau Linux que c"est effectivement le cas.

Limite accessible au delà du sommet de pile : 64K + 32 registres

Si on considère le code du noyau (sur architecture x86) à cet endroit, on voit que le noyau accepte en fait les accès qui se situent dans une zone entre le sommet de pile et le le sommet de pile - 64KB  - 128 octets (32 registres). Le commentaire associé dit : "The large cushion allows instructions like enter and pusha to work. ("enter $65535, $31" pushes 32 pointers and then decrements %sp by 65535.)"
Une petite extension à notre programme permet effectivement de vérifier ce comportement:

void alloc_128K_and_access_stack() {     char medium_buf[MEDIUMSZ];     medium_buf[0]='a';     __asm__         (             "  movl     %%esp,%0   \n"             : "=r" (stkpg)             );     printf("alloc_128K_and_access_stack, sp at %p\n", (int *)stkpg);     stkpg -= (64 * 1024); stkpg -= (33 * 4);     pt = (int *) stkpg;     if (sigsetjmp(jmpbuf, 0) == 0) {         *pt = 0xFAFAFAFA;         printf("Succeeded at %p\n", (int *)stkpg);     } else {         printf("Access to %p has failed caught a SIGSEGV\n", pt);     }     WAIT();        stkpg += 4;     pt = (int *) stkpg;     if (sigsetjmp(jmpbuf, 0) == 0) {         *pt = 0xFAFAFAFA;         printf("Succeeded at %p\n", (int *)stkpg);     } else {         printf("Access to %p has failed caught a SIGSEGV\n", pt);     }     WAIT();   }

On alloue un tableau de 128KB pour se retrouver au bas des 33 pages réservées, et se débarrasser du comportement spécifique lié à ces pages initiales. L’instruction en assembleur permet de récupérer la valeur courante du sommet de pile. Un premier accès 64KB + 33 x 4 octets plus loin va échouer, mais un accès 4 octets moins loin va réussir... A noter que si l'on inverse les accès, la page de pile ayant été allouée par le premier accès en 64KB - 32 x 4 octets, le deuxième en 64KB - 33 x 4 octets deviendra valide si l'on accède la même page virtuelle.

fa$ ./stack_layout 9 alloc_128K_and_access_stack, medium_buf[0] at 0xbffdf000 alloc_128K_and_access_stack, sp at 0xbffdf620 Access to 0xbffcf59c has failed caught a SIGSEGV Succeeded at 0xbffcf5a0

Et si je volais l'espace réservé au 8192Ko de la pile?

Donc, la pile a une taille maximum sur mon système de 8Mo. Mais la région mémoire initiale réservée n'est que de 132Ko...

Que se passerait-il si j'allouais une zone mémoire (via mmap) dans la zone potentielle de la pile?

Ma tentative de créer une région en conflit potentiel avec une extension éventuelle de la pile va-t-elle être rejetée? Et sinon, quand la pile va rentrer en conflit avec ma région parasite que va-t-il se passer?

printf("Attempting to map anonymous within stack limit!\n");     stkpg += 4096;     stkpg -= 1024 * 1024;     printf("stkpg = 0x%x\n", stkpg);     pt = mmap((void *)stkpg, 4096, PROT_READ | PROT_WRITE, MAP_PRIVATE |MAP_ANONYMOUS, -1, 0);     if (pt == MAP_FAILED) {         perror ("mmap has failed!");     } else if (pt != (int*) stkpg) {         printf("mmap at a different location! Expected 0x%x got %p\n", stkpg, pt);     }         printf("Attempting to extend by calling a subroutine with large local variable (7MB)\n");     if (sigsetjmp(jmpbuf, 0) == 0) {         big_local_variable_subroutine();     } else {         printf("Well, apparently the system detected that stack extension was not a good idea!\n");     }

Dans le code ci-dessus, on créé donc une région en imposant l'adresse ou cette région doit commencer (1Mo sous l'adresse la plus haute de la pile). Puis on tente d'invoquer une fonction   ayant une variable locale de pas loin de 8MO.

Moteurs!

Attempting to map anonymous within stack limit! stkpg = 0xbff00000 Attempting to extend by calling a subroutine with large local variable (7MB) Well, apparently the system detected that stack extension was not a good idea!

Donc:

• la création de la région est parfaitement légitime
• le conflit est détecté au plus tard, quand la pile tente de grandir pour recouvrir  la région "illicite".

Dans l'extrait ci-dessous, l'avant  dernière région est celle créée explicitement. Et la pile n'a pas pu croître et a donc gardé sa taille initiale de 132Ko.

fa$ cat /proc/22492/maps 08048000-080ef000 r-xp 00000000 08:01 268062     /home/francois/lefauxplat/facepile/stack_layout 080ef000-080f1000 rw-p 000a6000 08:01 268062     /home/francois/lefauxplat/facepile/stack_layout 080f1000-08115000 rw-p 00000000 00:00 0          [heap] b7ffe000-b7fff000 rw-p 00000000 00:00 0 b7fff000-b8000000 r-xp 00000000 00:00 0          [vdso] bff00000-bff01000 rw-p 00000000 00:00 0 bffdf000-c0000000 rw-p 00000000 00:00 0          [stack] fa$