Aller au contenu principal
own2pwn
os/mm.tsx

Comment l'OS te file de la mémoire

Adressage virtuel comme facade au-dessus de la RAM physique, segmentation Intel via la table de segments, et strategies d'allocation cote kernel.

Maxime Jérôme··5 min de lecture

Prerequis

  • Comprehension basique de Linux
    • Shell
  • Programmation en C
  • Introduction

Hello o/

Plus l'acces memoire est rapide, moins elle est grande, et inversement. La memoire en informatique c'est complique a definir. Par exemple pour N processus, chaque processus a son propre espace d'adresses virtuelles... mais aucun n'a acces directement a son espace physique.

Ce qui est bien avec l'adressage virtuel, c'est qu'au final c'est une interface, une sorte de facade pour la memoire physique. L'adressage virtuel peut vous faire croire que vous avez 2^64 octets de RAM... alors que vous en avez 8 Go.

Adressage virtuel vs physique

Chaque processus voit un espace d'adresses virtuel continu, gere par le MM (Memory Management) du kernel et le materiel via le MMU (Memory Management Unit). La MMU traduit les adresses virtuelles en adresses physiques a la volee, avec l'aide du TLB (Translation Lookaside Buffer) pour mettre en cache les traductions recentes et eviter d'aller relire les page tables a chaque acces.

virtual-physical-mapping.txt
  Processus A              Processus B
  Espace virtuel           Espace virtuel
  ┌──────────────┐         ┌──────────────┐
  │ 0x0000...    │         │ 0x0000...    │
  │  [stack]     │         │  [stack]     │
  │  ...         │         │  ...         │
  │  [heap]      │         │  [heap]      │
  │  [.bss]      │         │  [.bss]      │
  │  [.data]     │         │  [.data]     │
  │  [.text]     │         │  [.text]     │
  └──────┬───────┘         └──────┬───────┘
         │                        │
         │   MMU + Page Tables     │
         └───────────┬────────────┘
                     ▼
         RAM physique (ex: 8 Go)
         ┌──────────────────────────┐
         │ frame 0 │ frame 1 │ ...  │
         │   (A)   │   (B)   │      │
         └──────────────────────────┘
Chaque processus a son propre espace virtuel ; la MMU fait la translation vers la RAM physique.

Page tables et VMA

La traduction passe par une structure de donnees appelee page table. Sur Linux, chaque processus a sa propre page table. L'espace virtuel est decoup en regions logiques appelees VMA (Virtual Memory Area) : une VMA pour le stack, une pour le heap, une par segment ELF charge, etc. On peut les voir avec /proc/<pid>/maps.

page-table.txt
  Adresse virtuelle
  ┌────────────────────────────────────┐
  │  VPN (Virtual Page Number)         │
  │  +  offset dans la page (12 bits)  │
  └──────────────┬─────────────────────┘
                 │
                 ▼
         Page Table Entry
         ┌─────────────────────────────┐
         │ PFN (Physical Frame Number) │
         │ present ? dirty ? writable? │
         └──────────────┬──────────────┘
                        │
                        ▼
         Adresse physique = PFN * 4096 + offset
La page table mappe chaque page virtuelle (VP) vers un frame physique (FP) ou signale une absence (fault).
TLB : le cache des traductions
A chaque acces memoire, consulter la page table serait trop lent. Le TLB (Translation Lookaside Buffer) est un petit cache materiel (quelques dizaines a quelques centaines d'entrees) qui stocke les traductions recentes VP -> FP. Un context switch vide souvent le TLB (TLB flush), d'ou un cout visible sur les programmes tres multi-threades.

Segmentation Intel

La segmentation de la memoire est un mecanisme historique des processeurs a architecture Intel (x86). L'idee : un segment c'est un couple (s, o) = (segment number, offset). A chaque initialisation de processus, une table de segments lui est assignee.

L'adresse physique se calcule simplement :

text
Adresse Physique = TableSegment[s] + o
segmentation.txt
  Registres de segment
  CS (code)   DS (data)   SS (stack)
  ┌───┐       ┌───┐       ┌───┐
  │ s │       │ s │       │ s │
  └─┬─┘       └─┬─┘       └─┬─┘
    │            │            │
    ▼            ▼            ▼
  GDT / LDT (Global / Local Descriptor Table)
  ┌──────────────────────────────────────────┐
  │ Entree s : base | limite | flags         │
  └─────────────────┬────────────────────────┘
                    │
                    │  + offset (o)
                    ▼
           Adresse lineaire (puis MMU -> physique)
  ┌──────────────────────────────────────────┐
  │     .text     │    .data     │   stack   │
  └──────────────────────────────────────────┘
La segmentation Intel mappe chaque segment logique (code, data, stack) vers une zone de la memoire physique via la GDT/LDT.

En pratique, Linux et les OS modernes utilisent un modele de segmentation "flat" : tous les segments ont une base a 0 et couvrent tout l'espace d'adresses. La vraie isolation est faite par la pagination (page tables), pas par la segmentation.

Segmentation vs pagination
La segmentation decoupeen regions de taille variable (un segment peut faire 1 octet comme 4 Go). La pagination decoupe en pages de taille fixe (4 Ko sur x86-64). Les OS modernes s'appuient quasi exclusivement sur la pagination pour la protection memoire.

Allocation memoire cote kernel

Le kernel gere sa propre arena pour allouer de la memoire aux processus. Le probleme classique : la fragmentation. Quand on libere et realloue beaucoup, l'espace libre devient morcel en petits blocs non contigus, et on ne peut plus satisfaire les grosses allocations meme si la somme des blocs libres est suffisante.

Strategies d'allocation

Plusieurs strategies existent pour choisir quel bloc libre attribuer :

StrategiePrincipeAvantage / Inconvenient
First FitPrend le premier bloc libre suffisamment grandRapide, mais fragmente le debut de l'espace libre
Best FitPrend le bloc le plus petit parmi ceux assez grandsMinimise le gaspillage par allocation, mais cree beaucoup de micro-fragments
Worst FitPrend le plus grand bloc disponibleLaisse de gros blocs residuels, moins de micro-fragments, mais contre-intuitif
Fragmentation externe vs interne
Fragmentation externe : l'espace libre est divise en petits blocs non contigus, on ne peut pas satisfaire une grosse demande. Fragmentation interne : le bloc alloue est plus grand que necessaire (ex : on demande 3 octets, on obtient un bloc de 8 par alignement).

Allocateurs du kernel Linux

Linux utilise principalement deux allocateurs internes :

  • Buddy allocator : gere les pages (blocs de 4 Ko et multiples de 2). Permet de fusionner les blocs libres adjacents ("buddy") pour limiter la fragmentation externe.
  • Slab allocator (SLUB/SLOB selon la config) : au dessus du buddy, gere les petits objets frequemment alloues/liberes (inodes, task_struct, etc.) en les recyclant dans des "slabs" preconstruits.
buddy-allocator.txt
  Memoire totale : 64 pages
  ┌────────────────────────────────────────────────────────────┐
  │                         64 pages                          │
  └──────────────────────┬─────────────────────────────────────┘
                         │ split
              ┌──────────┴──────────┐
              │ 32 pages            │ 32 pages
              └──────┬──────────────┴──────────┐
                     │ split                    │ libre
              ┌──────┴──────┐
              │ 16 pages    │ 16 pages libres
              └──────┬──────┘
                     │ alloue 16 pages a proc A
              [OCCUPE 16p]

  Liberation : si les deux buddies de 16p sont libres -> fusion en 32p
Le buddy allocator divise la memoire en blocs de taille puissance de 2, et fusionne les 'buddies' libres adjacents.

Resume

En une image, voila comment s'articulent les couches de la gestion memoire d'un OS moderne :

mm-layers.txt
  Processus
  ┌────────────────────────────────────┐
  │  Espace virtuel (VMA par VMA)      │
  │  stack / heap / .text / .data ...  │
  └──────────────────┬─────────────────┘
                     │  appel syscall (mmap, brk...)
                     ▼
  Kernel
  ┌────────────────────────────────────┐
  │  Gestion des VMA (mm_struct)       │
  │  Page tables (traduction VP->FP)   │
  │  Slab allocator (petits objets)    │
  │  Buddy allocator (pages)           │
  └──────────────────┬─────────────────┘
                     │  acces physique
                     ▼
  Materiel
  ┌────────────────────────────────────┐
  │  MMU + TLB (traduction a la volee) │
  │  RAM physique (frames 4 Ko)        │
  └────────────────────────────────────┘
Les couches de la gestion memoire : du processus jusqu'a la RAM physique.

La gestion memoire c'est le fondement de tout ce qu'on fait en exploitation binaire : comprendre ou vit chaque region (stack, heap, .text...), comment elles sont protegees (permissions VMA), et comment le kernel alloue/libere sont indispensables pour la suite de la serie.

Suite de la serie OS ici.