Paradigmes et interprétation

Micro Rust 2 : gestion mémoire

Les pointeurs "stupides" (pas smart)

Ce sont ceux des premiers langages de programmation, notamment Fortran, C, Pascal,...

Ce sont le plus souvent des entiers désignant une adresse dans un espace d'adressage qui couvre à la fois "le tas" et "la pile".

C'est une gestion mémoire "statique" (déterminée à la compilation) et c'est le programmeur qui choisit quand désallouer de la mémoire (cf instruction free en C).

• avantage: on peut contrôler finement l'utilisation de la mémoire

• inconvénient: source de nombreux bugs et failles de sécurité

• autre inconvénient (surtout pour C): ces vieux langages reposent sur une vision de la mémoire qui n'est pas adaptée à celle des machines modernes et sont non-triviaux à optimiser

Les principaux griefs contre les pointeurs à la C

• le pointeur null ("the billion dollar mistake", Tony Hoare)

• l'arithmétique de pointeur, qui permet:

  • les dépassements de tableaux (souvent un bug silencieux)
  • les erreurs d'alignement

• les pointeurs vers la pile (les &x, qui ne sont pas des emprunts comme en Rust mais des pointeurs pas du tout "smart"): très peu de langages autorisent cela!

• les pointeurs pendants ("dangling pointers", "use after free", ...)

• les fuites mémoires

• les "double free"

• l'absence de valeur initiale

• ...

Les "ramasses-miettes" (garbage collector, GC)

Apparus avec Lisp dès les années 70, ils se sont imposés dans la grande majorité des langages dès les années 80.

Avec un GC, la gestion mémoire est "dynamique", la décision de désallouer la mémoire est prise à l'exécution et aucune instruction de déallocation n'est générée à la compilation.

Avec un GC, tous (ou presque) les griefs précédents n'ont plus cours. Bon, il reste bien le pointeur null en Java...

• avantage: beaucoup moins de bugs

• inconvénient: on doit écrire son code de sorte à permettre au GC à désallouer la mémoire, mais on ne peut pas le forcer à désallouer

• autre inconvénient, le GC doit par moment "arrêter tous les threads" $^1$, avec parfois un coût prohibitif au niveau des performances

$^1$ voir par exemple ce billet sur le GC de Python

Ce que vise Rust

mais aussi Cyclone, le projet Verona, et dans une certaine mesure C++,

c'est

1. pas de GC
2. pas (ou peu) de free/drop explicites avec l'emploi de RAII et des smart pointers
3. pas de faute mémoire grâce à
   • la discipline d'ownership
   • des détections d'erreurs mémoires à runtime qui restent souvent silencieuses en C (ex: débordement de tableau).

Et dans µRust?

Le langage µRust de la semaine dernière repose sur une mémoire composée uniquement d'une pile d'espaces de noms.

Nous allons maintenant ajouter à notre modèle mémoire un tas et à notre langage des smart pointers.

Nous allons aussi mettre en place des mécanismes de détection d'erreurs mémoires.

Les pointeurs bruts

Voici un exemple de ce qu'on veut pouvoir obtenir avec notre interpréteur

µRust # let x = Ptr::new() x : Ptr = @42 µRust # *x = 2 - : unit = () µRust # *x - : isize = 2 µRust # let y = x y : Ptr = @42 µRust # *y = 3 - : unit = () µRust # *x - : isize = 3

@42: l'adresse 42 dans le tas

On lève une erreur pour les valeurs non initialisées.

µRust # let x = Ptr::new() x : Ptr = @42 µRust # *x Evaluation Error: Value in `*x` is not initialized.

On lève aussi une erreur en cas de tentative d'arithmétique de pointeur.

µRust # let z = 4 z : isize = 4 µRust # *z = 5 Evaluation error: Type mismatch in expression `z`. Expected: Ptr. µRust # let ptr = Ptr::new() ptr : Ptr = @43 µRust # *(ptr + 1) Evaluation error: Type mismatch in expression `ptr`. Expected: isize. Found: Ptr.

Notre modèle de tas

On va prendre un modèle très simple, sans arithmétique de pointeurs:

• on a une notion d'adresse (un entier pour faire simple, mais peu importe)

  • une adresse peut être allouée ou pas
  • une adresse allouée contient une cellule mémoire

• on peut allouer une nouvelle cellule mémoire dans le tas

  • mais l'allocation peut échouer (si la mémoire est pleine)
  • on pourra aussi désallouer une adresse

• une cellule mémoire contient une valeur (entier, booléen, unit, pointeur,...)

  • ou n'est pas encore initialisée

Déallocation et double free

Voici un exemple de ce qu'on veut pouvoir faire avec notre interpréteur

µRust # let mut x = Ptr::new() x : Ptr = @39 µRust # *x = 2 - : unit = () µRust # x - : Ptr = @39 µRust # free(x) - : unit = () µRust # *x Evaluation Error: Cell at `x` is not allocated. µRust # x x : Ptr = @39 µRust # free(x) Evaluation Error: Cell at `x` is not allocated.

Les pointeurs vers la pile

Voici un exemple de ce qu'on voudrait faire

µRust # let mut x = 7 x : isize = 7 µRust # let y = &x y : Ptr = @[0,x] µRust # *y = 42 - : unit = () µRust # x x : isize = 42

L'adresse @[0,x] veut dire: la variable x dans l'espace de noms tout en bas de la pile (indice 0)

On peut avoir des erreurs

µRust # let x = 7 x : isize = 0 µRust # let mut ptr = &x ptr : Ptr = @[0,x] µRust # {let z = 8; ptr = &z ; *ptr } - : isize = 8 µRust # ptr - : Ptr = @[1,z] µRust # *ptr Evaluation error: Cell at `ptr` is not allocated.

Faisons le point

Le tas et la pile sont des espaces d'adressages: à certaines adresses on peut trouver des cellules mémoires.

Certaines adresses sont pendantes (dangling): elles ont accueilli une cellule mémoire par le passé mais n'en possèdent plus. Si on va y lire, on commet une erreur.

Ces adresses pourront être réutilisées, mais c'est un autre problème (à suivre).

Une cellule mémoire peut être non initialisée, ou contenir une valeur. Lire une cellule mémoire non initialisée est une erreur.

Les adresses du tas sont des entiers positifs ou nuls (pour faire simple et concret), et les adresses de la pile sont des couples indice/identifiant.

Modèle mémoire de µRust (abrégé)

pub enum MemoryCell {
    NotAllocated,
    Allocated(AllocatedCell),
}

struct AllocatedCell {
    mutable: bool,
    val: Option<Value>,
    // ...
}

struct NameSpace(Hashmap<Identifier, MemoryCell>) 
//                                   ^^^^^^^^^^ 

struct NameSpaceStack(Vec<NameSpace>)

struct Heap(Vec<MemoryCell>) 

struct Memory {
    stack: NameSpaceStack,
    heap: Heap
}

enum Address {
    StackAddress(usize, Identifier),
    HeapAddress(usize)
}

Quelques fonctions associées

impl NameSpaceStack {

    fn get_address(&self, id: &Identifier) -> Result<Address, EvalError> {
        // renvoie l'adresse de pile d'un identifiant (cf opérateur `&x`)

        for index in  (0..self.0.len()).rev() {
            if self.0[index].0.contains_key(id) { 
                return Ok(Address::StackAddress(index, id.clone()))
            }
        }
        Err(EvalError::Undefined(id.clone()))

    }
}

impl Heap {

    fn malloc(&mut self) -> Address {
        // un allocateur qui essaie d'utiliser un emplacement pris par une cellule
        // non allouée, sinon augmente la taille du tas (pour simplifier, le tas est "infini")

        for addr in 0..self.0.len() {
            if !self.0[addr].is_allocated() { 
                self.0[addr] = MemoryCell::new_uninitialized();
                return Address::HeapAddress(addr)
            }
        }
        self.0.push(MemoryCell::new_uninitialized());
        return Address::HeapAddress(self.0.len() - 1);
    }
}

impl Memory {

    fn value_at(&self, addr: &Address) -> Result<Value, EvaluationError> {
       // renvoie la valeur de la cellule à l'adresse indiquée
       // si la cellule n'est pas valide, lève une erreur
       //...
    }

    fn write_at(&mut self, addr: &Address, v: Value) -> Result<Value, EvaluationError> {
       // écrit la valeur de la cellule à l'adresse indiquée
       // si la cellule n'est pas valide, ou pas mutable, lève une erreur
       //...
    }


   fn free(&mut self, addr: &Address) -> Result<(), EvaluationError> {
      // ...
   }

}

AST avec les pointeurs

enum Expression {
    Const(ParsedValue),
    Identifier(Identifier),
    BinOp(Box<Expression>, Binop, Box<Expression>),
    Conditional{ /* ... */ },

    // NOUVEAU
    NewPtr,                                       
    Deref(Box<Expression>),                        
    AmpersAnd(Box<Expression>),
}

enum Instruction {
    Expr(Expression),
    Let{id:Identifier, mutable:bool, expr:Expression},
    Block(Vec<Instruction>),
    IfElse{ /* ... */ },
    While(Expression, Box<Instruction>),

    // NOUVEAU
    WriteAt(Expression, Expression),    // x = 1, *x = 1+1, ...
    Free(Expression),
}

Évaluation

On peut évaluer une expression soit en tant qu'adresse (membre gauche d'un = ou membre droit d'un &), soit en tant que valeur. Attention, désormais l'évaluation peut modifier la mémoire (allocation mémoire induite par l'expression Ptr::new() )

impl Expression {

    fn eval_to_address(&self, mem: &mut Memory)
//                                  ^^^ 
                       -> Result<Address, EvaluationError>
    { /* ... */ }

    fn eval(&self, mem: &mut Memory) 
//                       ^^^ 
            -> Result<Value, EvalError> 
    { /* ... */ }

}

impl Instruction {

    fn exec(&self, &mut mem:  Memory) 
            -> Result<(Option<Identifier>, Value), EvalError> 
    { /* ... */ }

}

Typage dynamique

µRust adopte le typage dynamique (comme Python ou Racket, mais aussi Java), au sens où:

• quand on connait une valeur, on peut déterminer son type (grace au constructeur). On pourrait ajouter à notre langage une instruction type_of ou instance_of

• on détecte les erreurs de typage au moment de l'évaluation (ex: fonction eval, cas des opérateurs binaires); en typage statique, il y a une étape d'analyse sémantique entre l'analyse syntaxique (construction de l'AST) et l'évaluation; nous n'avons pas cette étape dans nos interpréteurs.

Note: au TP Microrust 1 il était proposé un typage dynamique "rigide": le type d'une variable mutable était considéré comme non mutable (on ne pouvait pas mettre à jour avec une valeur d'un type différent de la précédente). On va dorénavant laisser muter le type d'une variable mutable.

Les valeurs

enum Value {
    Integer(isize),
    Boolean(bool)
    Unit,
    Pointer(Pointer)
} 

struct Pointer {
    address: Address,
    // ...
}

Détection d'erreur de pointeur

Pour le moment, on ne détecte pas les erreurs de pointeurs suivantes:

• les fuites mémoires (memory leaks)
• les pointeurs pendants (use after free)

Ces erreurs sont "silencieuses", on aimerait que µRust les détecte et génère une erreur.

Application: les techniques que nous allons étudier pour détecter ces erreurs se retrouvent dans les GC, mais surtout dans les "dévermineurs mémoires" (Valgrind, clang sanitizer, etc) qui permettent d'exécuter un programme en surveillant son utilisation mémoire (ce qui le ralentit, certes, mais est bien pratique pour découvrir des bugs).

Use after free

Exemple de session avec un use after free non détecté

µRust # let ptr = Ptr::new() ptr : Ptr = @0 µRust # free(ptr) - : unit = () µRust # let x = Ptr::new() x : Ptr = @0 µRust # *x = 42 - : unit = () µRust # *ptr <- use after free - : isize = 42

On voudrait afficher

Evaluation Error: `*ptr` is a use after free

Autre exemple de use after free

µRust # let mut ptr = 0 ptr : isze = 0 µRust # {let x = 1; ptr = &x} - : unit = () µRust # ptr - : Ptr = @[1,x] µRust # {let x = 2; *ptr} <- use after free - : isize = 2

Détection par Horodatage

Le problème vient du fait qu'on a deux cellules mémoires "différentes" à la même adresse, mais à des moments différents. Le pointeur ptr ne devrait plus être valide après le free, il pointe vers l'"ancienne" cellule.

Pour détecter les use after free on peut horodater les cellules et les pointeurs:

• on marque chaque cellule par l'"heure" (timestamp) de sa création
• on marque chaque pointeur par l'heure de la cellule vers laquelle il pointe au moment où il est créé
• lorsqu'on déréférence un pointeur, on verifie que le timestamp du pointeur coïncide avec celui

Mise en oeuvre de l'horodatage dans µRust

struct AllocatedCell {
    mutable: bool,
    val: Option<Value>,
    timestamp: Timestamp
    // ...
}

struct Pointer {
    address: Address,
    timestamp: Timestamp,
    // ...
}

enum Value {
    // ...
    Pointer(Pointer)
}

struct Timestamp(SystemTime)
impl Timestamp {
    fn generate() -> Self { 
        Timestamp { SystemTime::now()}
    } 
}

Alternatives

On pourrait horodater avec un simple compteur (il faudrait mettre ce compteur dans un "horodateur" qu'on utiliserait pour générer un nouveau timestamp à chaque appel à generate.

On pourrait aussi calculer le hash du contenu de la cellule et le stocker dans le pointeur (un hash pointer). Cela ne permet pas de détecter toutes les erreurs de use after free, cependant. Les hash pointers sont utilisés dans les blockchains pour garantir l'immutabilité des valeurs pointées par les pointeurs (on ne veut pas laisser un attaquant "réécrire l'histoire").

Fuites mémoires

Pour le moment les fuites mémoires sont silencieuses. On aimerait afficher des messages d'erreur et effectuer un GC, comme suit.

µRust # let mut p = Ptr::new() p : Ptr = @0 µRust # p = Ptr::new() Evaluation error: leaking @0 µRust # p p : Ptr = @1 µRust # let ptr = Ptr::new() ptr : Ptr = @0 <- on a pu réallouer la cellule fuitée µRust # { let ptr2 = Ptr::new() } Evaluation error: leaking @2

Détection de fuites mémoires

Pour détecter les fuites mémoires, il faut savoir déterminer si une cellule mémoire reste accessible ou non. On peut le faire en comptant le nombre de pointeurs sur cette cellule mémoire (c'est le reference counting vu au cours 3), mais certaines fuites peuvent rester non détectées s'il y a des cycles de pointeurs.

La technique ultime, utilisée par les GC, c'est recalculer entièrement l'ensemble des cellules accessibles:

• on part des cellules de la pile
• on suit les pointeurs (parcours du graphe en largeur ou en profondeur, peu importe)
• on marque les cellules visitées (pour se souvenir qu'elles sont accessibles, et pour ne pas les explorer une seconde fois)
• on parcours l'ensemble des cellules, et on vérifie qu'elles sont bien toutes marquées. Si une cellule n'est pas marquée, on a détecté une fuite mémoire

Ce que fait en plus un GC dans une phase "mark and sweep", c'est de désallouer les cellules non marquées.

Variante "copy and compact: on recopie à la volée toutes les cellules marquées dans un nouveau tas, en maintenant une table de traduction d'adresses. Plus compliqué, mais plus efficace (pas besoin de parcourir l'ensemble des cellules, et on défragmente la mémoire).

Vous n'aurez pas à écrire de GC "copy and compact" 😅 mais au final pour détecter les fuites mémoires, vous aurez à écrire un GC "mark and sweep"

Mise en place du marquage de cellule dans µRust

enum MemoryCell {
    NotAllocated,
    AllocatedCell(AllocatedCell)
}


struct AllocatedCell {
    mutable: bool,
    va: Value,
    timestamp: Timestamp,
    marked: bool,  // <- NOUVEAU
    // ...
}

impl Memory {

    fn mark_reachable_cells(&mut self) {
        // met le champs `marked` des cellules accessibles depuis la pile à `true`
        // ...
    }

    fn unmark_and_sweep(&mut self) -> Result<(), EvalError> {
        // parcours toute la pile et tout le tas
        // met le champs `marked` de toutes les cellules allouées (pile et tas) à `false`
        // renvoie `MemoryLeak` si une cellule allouée du tas n'était pas marquée
        // désalloue toute cellule non marquée
        // ...
    } 
}

Marquage par un parcours en profondeur

Vous avez vu (ou allez voir?) ça en cours d'algo, mais voici une façon de faire pour le marquage de cellules accessibles.

1. Soit P une pile d'adresses, initialement vide
2. Pour toute adresse a contenue dans une variable (dans la pile d'espaces de noms), empiler a sur P
3. Dépiler une adresse a de P
4. Si la cellule à l'adresse a n'est pas marquée et contient une adresse a', empiler a'
5. Marquer la cellule à l'adresse a (si elle est déjà marquée, on ne fait rien)
6. Si P n'est pas vide, revenir à 3.

Possession et sémantique MOVE

On veut maintenant ajouter une gestion des pointeurs proche de celle des Box de Rust:

• les valeurs de type Ptr sont en sémantique MOVE
• les entiers, booléens, et unit sont en sémantique COPY
• une cellule peut (ne plus) contenir une valeur déplacée
• une cellule qui contient une valeur peut être possédée par une autre cellule, au plus.

Version finale des cellules mémoires

On a besoin d'ajouter deux informations sur les cellules:

• est-ce que la valeur a été déplacée
• est-ce que la valeur est possédée, et par qui

pub enum MemoryCell {
    NotAllocated,
    Allocated(AllocatedCell),
}

pub struct AllocatedCell {
    mutable: bool,
    cellvalue: CellValue,
    timestamp: TimeStamp,
    marked: bool,
}

pub enum CellValue {
    Moved,
    Val(Option<Value>),
    OwnedVal{val: Option<Value>, owner: Address},
}

Détection de déplacement illégal

On ne peut pas désallouer une cellule possédée.

µRust # let ptr = Ptr::new() ptr : Ptr = @0 µRust # *ptr = Ptr::new() - : unit = () µRust # free(*ptr) Evaluation error: cannot free `*ptr`, owned value

Si une valeur (en sémantique move) est possédée, on ne peut pas la déplacer.

µRust # let ptr = Ptr::new() ptr : Ptr = @0 µRust # *ptr = Ptr::new() - : unit = () µRust # let ptr2 = *ptr Evaluation error: cannot move `*ptr`, owned value with move semantics µRust # *ptr = 42 - : unit = () µRust # let x = *ptr <- en sémantique copy, pas de soucis x : isize = 42

Détection des lectures de valeurs déplacées

Si on essaie de lire une valeur déplacée, on génère une erreur

µRust # let ptr = Ptr::new() ptr : Ptr = @0 µRust # let ptr2 = ptr ptr2 : Ptr = @0 µRust # ptr Evaluation error: `ptr` has been moved

Autre exemple

µRust # let x = 42 x : isize = 42 µRust # let ptr = &x ptr : Ptr = @[0,x] µRust # let ptr2 = ptr ptr : Ptr = @[0,x] µRust # ptr Evaluation error: `ptr` has been moved

& n'est pas un emprunt

C'est une prise de possession de la valeur contenue à l'adresse pointée:

• sans la voler si elle n'avait pas de propriétaire (on crée un nouveau pointeur)

• en déplaçant le pointeur de son ancien propriétaire vers le nouveau si la valeur était possédée

• la prise de possession peut échouer si le pointeur (chez l'ancien propriétaire) est lui-même possédé

µRust # let x = 42 x : isize = 42 µRust # let ptr = &x ptr : Ptr = @[0,x] µRust # let ptr2 = &x ptr2 : Ptr = @[0,x] µRust # ptr Evaluation error: `ptr` has been moved µRust # let ptr3 = &ptr2 ptr3 : Ptr = @[0,ptr2] µRust # let ptr4 = &x Evaluation error: cannot move `&x`, owned value with move semantics

RAII et GC

On rajoute enfin une forme de RAII à notre langage

• lorsqu'une cellule de la pile est "dépilée", si elle contient un pointeur, on désalloue aussi la cellule pointée
• lorsqu'une cellule (de la pile ou du tas) contenant un pointeur est mise à jour (ou désallouée), on désalloue la cellule qu'elle pointait

Exemple

µRust # {let ptr = Ptr::new(); ptr } - : Ptr = @0

Pas de fuite mémoire! le free(ptr) est implicite en fin de bloc...

Autre exemple

µRust # let mut ptr = Ptr::new() ptr : Ptr = @0 µRust # ptr = Ptr::new() - : unit = ()

Pas de fuite mémoire! le free(ptr) est implicite avant l'affectation.

Conclusion

On termine sur une notion bien compliquée de cellule mémoire!, mais on pourrait simplifier.

Avec la discipline de possession les champs marked et timestamp deviennent inutile:

On n'a (presque) plus de fuites mémoires: certaines sont maintenant des erreurs de possession, d'autres sont "rattrapées" par le RAII. Il en reste une: les possessions cycliques... mais on pourrait l'interdire (par exemple avec un typage statique).

On peut se débrouiller pour ne plus avoir de use after free ni de double free (pas détaillé ici, laissé en exercice).

On peut résumer la possession à l'existence de ce champs owner et à l'invariant:

$$ \begin{array}{ccc} \begin{array}{c} \mbox{la cellule à l'adresse }a\\ \mbox{pointe vers une cellule}\\ \mbox{qui contient } v \end{array} & \Leftrightarrow & v \mbox{ est possédé par } a \end{array} $$

Cela implique pas d'aliasing, et chaque cellule a un compteur de références égal à 0 ou 1.

Enfin, insistons sur le fait que µRust reste un objet à but pédagogique: Rust utilise des mécanismes très différents (ne serait-ce que parce que le typage est statique en Rust).

En TP la gestion mémoire de µRust.