Les articles precedents utilisaient des mots comme “registre”, “pile”, “frame” sans les definir vraiment. On disait push rbp = “sauvegarde le frame du parent” et mov rdi, rax = “prepare l’argument”. Mais qu’est-ce qu’un registre ? Comment la pile fonctionne-t-elle physiquement ? Pourquoi le processeur a-t-il besoin de ces mecanismes ?

Cet article repond a ces questions en utilisant le binaire factorial comme support.

Les registres : 16 tiroirs ultra-rapides

Un processeur x86-64 a 16 registres a usage general. Un registre est un emplacement de stockage a l’interieur du processeur — pas en memoire RAM. Acceder a un registre prend environ 0.3 nanosecondes. Acceder a la RAM prend ~100 nanosecondes. C’est 300 fois plus lent.

Pensez aux registres comme des tiroirs sur votre bureau. La RAM, c’est l’armoire au fond de la piece. Vous pouvez garder 16 choses sur le bureau. Tout le reste est dans l’armoire — accessible, mais il faut se lever.

Les registres utilises par factorial

RegistreRole dans factorialQuand
rdiArgument d’entree — contient la valeur passee a factAvant chaque call
raxValeur de retour — contient le resultat apres retApres chaque ret
rbpPointeur de frame — pointe vers le debut de l’espace de travailPendant toute la fonction
rspPointeur de pile — pointe vers le sommet de la pileToujours
rcxScratch — utilise temporairement pour la multiplicationPendant imul rax, rcx
r10Scratch — utilise pour le bounds-checkPendant cmp rax, r10

Les 10 autres registres (rbx, rdx, rsi, r8, r9, r11-r15) existent mais factorial ne les utilise pas. Les programmes plus complexes les utilisent.

La convention : qui met quoi ou ?

Ce n’est pas le processeur qui decide quel registre fait quoi — c’est une convention entre l’appelant et l’appele. La convention System V AMD64 (utilisee par Linux) dit :

  • L’appelant met le premier argument dans rdi
  • L’appele met son resultat dans rax
  • L’appele doit sauvegarder rbp s’il le modifie

Verbose suit cette convention. C’est la meme que GCC, Rust, et tout compilateur Linux x86-64.

La pile : une colonne de 8 Mo qui grandit vers le bas

La pile est une zone de memoire que Linux alloue pour chaque programme. Par defaut : 8 Mo. Elle commence a une adresse haute et grandit vers le bas — chaque nouvel element est place a une adresse plus basse.

flowchart TD
    TOP[Adresse haute] --> F1[Frame _start]
    F1 --> F2[Frame fact 3 : n.v = 3]
    F2 --> F3[Frame fact 2 : n.v = 2]
    F3 --> F4[Frame fact 1 : n.v = 1]
    F4 --> F5[Frame fact 0 : n.v = 0]
    F5 --> RSP[rsp pointe ici]

Chaque rectangle est un frame — l’espace de travail d’une fonction. Quand fact 3 appelle fact 2, un nouveau frame est empile sous le precedent. Quand fact 2 retourne, son frame est depile.

Le registre rsp pointe toujours vers le sommet de la pile (l’adresse la plus basse utilisee). Le registre rbp pointe vers le debut du frame en cours.

Le prologue : ouvrir un frame

Quand le processeur entre dans fact, les 4 premieres instructions preparent le frame :

55                    push rbp            sauvegarde le frame du parent
48 89 E5              mov rbp, rsp        notre frame commence ici
48 83 EC 08           sub rsp, 8          reserve 8 octets pour n.v
48 89 7D F8           mov [rbp-8], rdi    copie l'argument dans le frame

push rbp — 1 octet

Deux choses en une instruction : rsp descend de 8, et rbp est ecrit a cette adresse. On sauvegarde le pointeur de frame du parent pour pouvoir le restaurer au retour.

mov rbp, rsp — 3 octets

A partir de maintenant, rbp pointe vers le debut de NOTRE frame. Tout ce qu’on stocke sera a des offsets negatifs : [rbp - 8], [rbp - 16], etc.

sub rsp, 8 — 4 octets

Reserve 8 octets sur la pile pour nos variables locales. Factorial a une seule variable locale (n.v). Des programmes plus complexes reservent plus.

mov [rbp-8], rdi — 4 octets

Copie le contenu de rdi (notre argument) dans la memoire a l’adresse rbp - 8. C’est la que n.v vit pendant l’execution de la fonction.

[rbp - 8] est une adresse memoire relative : “prends l’adresse dans rbp, soustrais 8, va a cette adresse”. C’est comme dire “la case qui est 8 octets sous le debut de mon frame”.

L’appel recursif : empiler un nouveau frame

Quand factorial calcule fact(n.v - 1) :

48 8B 45 F8           mov rax, [rbp-8]     charge n.v
48 83 E8 01           sub rax, 1           rax = n.v - 1
48 89 C7              mov rdi, rax         prepare argument
E8 A9 FF FF FF        call fact            appel recursif

L’instruction call — 5 octets

call fait deux choses automatiquement :

  1. Push l’adresse de retour sur la pile (l’adresse de l’instruction APRES le call)
  2. Saute a l’adresse cible

L’adresse de retour permet au processeur de savoir ou revenir quand fact terminera. Sans elle, ret ne saurait pas ou aller.

ret — 1 octet

L’inverse de call :

  1. Pop l’adresse de retour depuis la pile
  2. Saute a cette adresse

Le processeur reprend exactement la ou il s’etait arrete avant le call.

La pile complete pour fact 3

Quand on est dans fact 0 (le cas de base), 4 frames sont empiles :

Adresse haute
   Frame _start
   ─────────────────
   Adresse retour vers _start     pushee par call fact 3
   ─────────────────
   Frame fact 3
     ancien rbp = rbp de _start
     n.v = 3
   ─────────────────
   Adresse retour vers fact 3     pushee par call fact 2
   ─────────────────
   Frame fact 2
     ancien rbp = rbp de fact 3
     n.v = 2
   ─────────────────
   Adresse retour vers fact 2
   ─────────────────
   Frame fact 1
     ancien rbp = rbp de fact 2
     n.v = 1
   ─────────────────
   Adresse retour vers fact 1
   ─────────────────
   Frame fact 0     NOUS SOMMES ICI
     ancien rbp = rbp de fact 1
     n.v = 0
     rsp pointe ici
Adresse basse

Chaque frame fait 24 octets : 8 (adresse de retour par call) + 8 (ancien rbp par push) + 8 (variable locale n.v).

4 frames = 96 octets utilises. Linux en fournit 8 000 000.

L’epilogue : fermer le frame

48 89 EC              mov rsp, rbp     restaure rsp
5D                    pop rbp          restaure le rbp du parent
C3                    ret              depile l'adresse de retour et saute

mov rsp, rbp : remet rsp a sa valeur d’avant le sub rsp, 8. Ca “libere” toutes les variables locales d’un coup. La memoire n’est pas effacee — elle est juste marquee comme libre.

pop rbp : lit l’ancien rbp sauvegarde sur la pile, le remet dans rbp. Maintenant rbp pointe vers le frame du parent.

ret : pop l’adresse de retour et saute. On est de retour dans la fonction appelante, qui peut lire le resultat dans rax.

Le stack overflow : quand la pile deborde

Si on appelle fact 1000000 sans bounds-check, chaque appel ajoute 24 octets. 1 000 000 appels = 24 Mo. Linux donne 8 Mo. Au bout d’environ 333 000 frames, rsp descend sous la guard page — une zone memoire interdite de 4 Ko que Linux place sous la pile.

Le processeur essaie d’ecrire dans la guard page. Linux detecte l’acces interdit et envoie SIGSEGV (signal 11). Le programme meurt.

C’est pour ca que les articles #1 et #2 insistaient sur le bounds-check. Les 38 octets de verification empechent le processeur d’atteindre cette situation.

Ce qu’on a appris

  1. Les registres sont des tiroirs rapides (0.3 ns) a l’interieur du processeur. La RAM est 300 fois plus lente. x86-64 en a 16.

  2. La pile grandit vers le bas. Chaque appel empile un frame (prologue), chaque retour le depile (epilogue). rsp pointe vers le sommet.

  3. Le prologue a 4 instructions fixes : push rbp, mov rbp rsp, sub rsp N, mov [rbp-N] rdi.

  4. call et ret travaillent en paire. call push l’adresse de retour et saute. ret pop l’adresse et revient. C’est le mecanisme de la recursion.

  5. Stack overflow = trop de frames. 8 Mo / 24 octets = 333 000 appels max. Le bounds-check de verbose limite a 11 frames (264 octets — 0.003% de la pile).

Verbose est open source : github.com/verbose-org/verbose Version utilisee dans cet article : v0.7.0 Serie : “Verbose — comprendre ce qui se passe vraiment” Article precedent : #3 — Comment verbose prouve la terminaison