Les boucles de références qui peuvent provoquer des fuites de mémoire

Les garanties de sécurité de la mémoire de Rust rendent difficile, mais pas impossible, la création accidentelle de mémoire qui n'est jamais nettoyée (aussi appelée fuite de mémoire). Eviter totalement les fuites de mémoire n'est pas une des garanties de Rust, en tout cas pas comme pour l'accès concurrent au moment de la compilation, ce qui signifie que les fuites de mémoire sont sans risque pour la mémoire avec Rust. Nous pouvons constater que Rust permet les fuites de mémoire en utilisant Rc<T> et RefCell<T> : il est possible de créer des références où les éléments se réfèrent entre eux de manière cyclique. Cela crée des fuites de mémoire car le compteur de références de chaque élément dans la boucle de références ne vaudra jamais 0, et les valeurs ne seront jamais libérées.

Créer une boucle de références

Voyons comment une boucle de références peut exister et comment l'éviter, en commençant par la définition de l'énumération List et la méthode parcourir de l'encart 15-25 :

Fichier : src/main.rs

use crate::List::{Cons, Nil};
use std::cell::RefCell;
use std::rc::Rc;

#[derive(Debug)]
enum List {
    Cons(i32, RefCell<Rc<List>>),
    Nil,
}

impl List {
    fn parcourir(&self) -> Option<&RefCell<Rc<List>>> {
        match self {
            Cons(_, item) => Some(item),
            Nil => None,
        }
    }
}

fn main() {}

Encart 15-25 : une liste de construction qui stocke une RefCell<T> pour que nous puissions modifier ce sur quoi une variante Cons pointe

Nous utilisons une autre variation de la définition de List de l'encart 15-5. Le second élément dans la variante Cons est maintenant un RefCell<Rc<List>>, ce qui signifie qu'au lieu de pouvoir modifier la valeur i32 comme nous l'avions fait dans l'encart 15-24, nous modifions ce sur quoi une variante Cons pointe (qui reste une valeur List). Nous ajoutons également une méthode parcourir pour nous faciliter l'accès au second élément si nous avons une variante Cons.

Dans l'encart 15-26, nous ajoutons une fonction main qui utilise les définitions de l'encart 15-25. Ce code crée une liste dans a et une liste dans b qui pointe sur la liste de a. Ensuite, on modifie la liste de a pour pointer sur b, ce qui crée une boucle de références. Il y a aussi des instructions println! tout du long pour montrer la valeur des compteurs de références à différents endroits du processus.

Fichier : src/main.rs

use crate::List::{Cons, Nil};
use std::cell::RefCell;
use std::rc::Rc;

#[derive(Debug)]
enum List {
    Cons(i32, RefCell<Rc<List>>),
    Nil,
}

impl List {
    fn parcourir(&self) -> Option<&RefCell<Rc<List>>> {
        match self {
            Cons(_, item) => Some(item),
            Nil => None,
        }
    }
}

fn main() {
    let a = Rc::new(Cons(5, RefCell::new(Rc::new(Nil))));

    println!("compteur initial de a = {}", Rc::strong_count(&a));
    println!("prochain élément de a = {:?}", a.parcourir());

    let b = Rc::new(Cons(10, RefCell::new(Rc::clone(&a))));

    println!("compteur de a après création de b = {}", Rc::strong_count(&a));
    println!("compteur initial de b = {}", Rc::strong_count(&b));
    println!("prochain élément de b = {:?}", b.parcourir());

    if let Some(lien) = a.parcourir() {
        *lien.borrow_mut() = Rc::clone(&b);
    }

    println!("compteur de b après avoir changé a = {}", Rc::strong_count(&b));
    println!("compteur de a après avoir changé a = {}", Rc::strong_count(&a));

    // Décommentez la ligne suivante pour constater que nous sommes dans
    // une boucle de références, cela fera déborder la pile
    // println!("prochain élément de a = {:?}", a.parcourir());
}

Encart 15-26 : création d'une boucle de références de deux valeurs List qui se pointent mutuellement dessus

Nous créons une instance Rc<List> qui stocke une valeur List dans la variable a avec une valeur initiale de 5, Nil. Nous créons ensuite une instance Rc<List> qui stocke une autre valeur List dans la variable b qui contient la valeur 10 et pointe vers la liste dans a.

Nous modifions a afin qu'elle pointe sur b au lieu de Nil, ce qui crée une boucle. Nous faisons ceci en utilisant la méthode parcourir pour obtenir une référence au RefCell<Rc<List>> présent dans a, que nous plaçons dans la variable lien. Ensuite nous utilisons la méthode borrow_mut sur le RefCell<Rc<List>> pour remplacer la valeur actuellement présente en son sein, la Rc<List> contenant Nil, par la Rc<List> présente dans b.

Lorsque nous exécutons ce code, en gardant le dernier println! commenté pour le moment, nous obtenons ceci :

$ cargo run
   Compiling cons-list v0.1.0 (file:///projects/cons-list)
    Finished dev [unoptimized + debuginfo] target(s) in 0.53s
     Running `target/debug/cons-list`
compteur initial de a = 1
prochain élément de a = Some(RefCell { value: Nil })
compteur de a après création de b = 2
compteur initial de b = 1
prochain élément de b = Some(RefCell { value: Cons(5, RefCell { value: Nil }) })
compteur de b après avoir changé a = 2
compteur de a après avoir changé a = 2

Les compteurs de références des instances de Rc<List> valent tous les deux 2 pour a et b après avoir modifié a pour qu'elle pointe sur b. A la fin du main, Rust nettoie d'abord la variable b, ce qui décrémente le compteur de références dans l'instance Rc<List> de 2 à 1. La mémoire utilisée sur le tas par Rc<List> ne sera pas libérée à ce moment, car son compteur de références est à 1, et non pas 0. Puis, Rust libère a, ce qui décrémente le compteur a de références Rc<List> de 2 à 1, également. La mémoire de cette instance ne peut pas non plus être libérée car l'autre instance Rc<List> y fait toujours référence. La mémoire alouée à la liste ne sera jamais libérée. Pour représenter cette boucle de références, nous avons créé un diagramme dans l'illustration 15-4.

Une boucle de références de listes

Illustration 15-4 : une boucle de références entre les listes a et b qui se pointent mutuellement dessus

Si vous décommentez le dernier println! et que vous exécutez le programme, Rust va essayer d'afficher cette boucle avec a qui pointe sur b qui pointe sur a ... et ainsi de suite jusqu'à ce que cela fasse déborder la pile.

Dans ce cas, juste après que nous avons créé la boucle de références, le programme se termine. Les conséquences de cette boucle ne sont pas désastreuses. Cependant, si un programme plus complexe alloue beaucoup de mémoire dans une boucle de références et la garde pendant longtemps, le programme va utiliser bien plus de mémoire qu'il n'en a besoin et pourrait surcharger le système en consommant ainsi toute la mémoire disponible.

La création de boucles de références n'est pas facile à réaliser, mais n'est pas non plus impossible. Si vous avez des valeurs RefCell<T> qui contiennent des valeurs Rc<T> ou des combinaisons similaires de types emboîtés avec de la mutabilité interne et du comptage de références, vous devez vous assurer que vous ne créez pas de boucles ; vous ne pouvez pas compter sur Rust pour les détecter. La création de boucle de références devrait être un bogue de logique de votre programme dont vous devriez réduire le risque en pratiquant des tests automatisés, des revues de code, ainsi que d'autres pratiques de développement.

Une autre solution pour éviter les boucles de références est de réorganiser vos structures de données afin que certaines références prennent possession et d'autres non. Par conséquent, vous pouvez obtenir des boucles de certaines références qui prennent possession ou d'autres références qui ne prennent pas possession, et seules celles qui prennent possession décident si oui ou non une valeur peut être libérée. Dans l'encart 15-25, nous voulons toujours que les variantes Cons possèdent leur propre liste, donc il est impossible de réorganiser la structure des données. Voyons maintenant un exemple qui utilise des graphes constitués de nœuds parents et de nœuds enfants pour voir quand des relations sans possessions constituent un moyen approprié d'éviter les boucles de références.

Eviter les boucles de références : transformer un Rc<T> en Weak<T>

Précédemment, nous avons démontré que l'appel à Rc::clone augmente le strong_count d'une instance de Rc<T>, et une instance Rc<T> est nettoyée seulement si son strong_count est à 0. Vous pouvez aussi créer une référence faible (NdT : d'où le weak) vers la valeur présente dans une instance Rc<T> en appelant Rc::downgrade et en lui passant une référence vers le Rc<T>. Lorsque vous faites appel à Rc::downgrade, vous obtenez un pointeur intelligent du type Weak<T>. Plutôt que d'augmenter le strong_count de l'instance de 1, l'appel à Rc::downgrade augmente le weak_count de 1. Le type Rc<T> utilise le weak_count pour compter combien de références Weak<T> existent, de la même manière que strong_count. La différence réside dans le fait que weak_count n'a pas besoin d'être à 0 pour que l'instance Rc<T> soit nettoyée.

Les références fortes désignent la manière de partager la propriété d'une instance Rc<T>. Les références faibles n'expriment pas de relation de possession. Ils ne provoqueront pas de boucle de références car n'importe quelle boucle impliquant des références faibles sera détruite une fois que le compteur de références fortes des valeurs impliquées vaudra 0.

Comme la valeur contenue dans une référence Weak<T> peut être libérée, pour pouvoir faire quelque chose avec cette valeur, vous devez vous assurer qu'elle existe toujours. Vous pouvez faire ceci en appelant la méthode upgrade sur une instance Weak<T>, qui va retourner une Option<Rc<T>>. Ce résultat retournera Some si la valeur Rc<T> n'a pas encore été libérée, et un None si la valeur Rc<T> a été libérée. Comme upgrade retourne une Option<Rc<T>>, Rust va s'assurer que les cas de Some et de None sont bien gérés, et qu'il n'existe pas de pointeur invalide.

Par exemple, plutôt que d'utiliser une liste dont les éléments ne connaissent que les éléments suivants, nous allons créer un arbre dont les éléments connaissent les éléments enfants et leurs éléments parents.

Créer une structure d'arbre de données : un Noeud avec des nœuds enfants

Pour commencer, nous allons créer un arbre avec des nœuds qui connaissent leurs nœuds enfants. Nous allons créer une structure Noeud qui contient sa propre valeur ainsi que les références vers ses Noeud enfants :

Fichier : src/main.rs

use std::cell::RefCell;
use std::rc::Rc;

#[derive(Debug)]
struct Noeud {
    valeur: i32,
    enfants: RefCell<Vec<Rc<Noeud>>>,
}

fn main() {
    let feuille = Rc::new(Noeud {
        valeur: 3,
        enfants: RefCell::new(vec![]),
    });

    let branche = Rc::new(Noeud {
        valeur: 5,
        enfants: RefCell::new(vec![Rc::clone(&feuille)]),
    });
}

Nous souhaitons qu'un Noeud prenne possession de ses enfants, et nous souhaitons partager la possession avec des variables afin d'accéder directement à chaque Noeud de l'arbre. Pour pouvoir faire ceci, nous définissons les éléments du Vec<T> comme étant des valeurs du type Rc<Noeud>. Nous souhaitons également pouvoir modifier le fait que tel nœud soit enfant de tel autre, donc, dans enfants, nous englobons le Vec<Rc<Noeud>> dans un RefCell<T>.

Ensuite, nous allons utiliser notre définition de structure et créer une instance de Noeud qui s'appellera feuille avec la valeur 3 et sans enfant, comme dans l'encart 15-27 :

Filename : src/main.rs

use std::cell::RefCell;
use std::rc::Rc;

#[derive(Debug)]
struct Noeud {
    valeur: i32,
    enfants: RefCell<Vec<Rc<Noeud>>>,
}

fn main() {
    let feuille = Rc::new(Noeud {
        valeur: 3,
        enfants: RefCell::new(vec![]),
    });

    let branche = Rc::new(Noeud {
        valeur: 5,
        enfants: RefCell::new(vec![Rc::clone(&feuille)]),
    });
}

Encart 15-27 : création d'un nœud feuille sans aucun enfant et un nœud branche avec feuille comme enfant

Nous créons un clone du Rc<Noeud> dans feuille et nous le stockons dans branche, ce qui signifie que le Noeud dans feuille a maintenant deux propriétaires : feuille et branche. Nous pouvons obtenir feuille à partir de branche en utilisant branche.feuille, mais il n'y a pas de moyen d'obtenir branche à partir de feuille. La raison est que feuille n'a pas de référence vers branche et ne sait pas s'ils sont liés. Nous voulons que feuille sache quelle branche est son parent. C'est ce que nous allons faire dès maintenant.

Ajouter une référence à un enfant vers son parent

Pour que le nœud enfant connaisse son parent, nous devons ajouter un champ parent vers notre définition de structure Noeud. La difficulté ici est de choisir quel sera le type de parent. Nous savons qu'il ne peut pas contenir de Rc<T>, car cela créera une boucle de référence avec feuille.parent qui pointe sur branche et branche.enfant qui pointe sur feuille, ce qui va faire que leurs valeurs strong_count ne seront jamais à 0.

En concevant le lien d'une autre manière, un nœud parent devrait prendre possession de ses enfants : si un nœud parent est libéré, ses nœuds enfants devraient aussi être libérés. Cependant, un enfant ne devrait pas prendre possession de son parent : si nous libérons un nœud enfant, le parent doit toujours exister. C'est donc un cas d'emploi pour les références faibles !

Donc, plutôt qu'un Rc<T>, nous allons faire en sorte que le type de parent soit un Weak<T>, plus précisément un RefCell<Weak<Noeud>>. Maintenant, la définition de notre structure Noeud devrait ressembler à ceci :

Fichier : src/main.rs

use std::cell::RefCell;
use std::rc::{Rc, Weak};

#[derive(Debug)]
struct Noeud {
    valeur: i32,
    parent: RefCell<Weak<Noeud>>,
    enfants: RefCell<Vec<Rc<Noeud>>>,
}

fn main() {
    let feuille = Rc::new(Noeud {
        valeur: 3,
        parent: RefCell::new(Weak::new()),
        enfants: RefCell::new(vec![]),
    });

    println!("parent de la feuille = {:?}", feuille.parent.borrow().upgrade());

    let branche = Rc::new(Noeud {
        valeur: 5,
        parent: RefCell::new(Weak::new()),
        enfants: RefCell::new(vec![Rc::clone(&feuille)]),
    });

    *feuille.parent.borrow_mut() = Rc::downgrade(&branche);

    println!("parent de la feuille = {:?}", feuille.parent.borrow().upgrade());
}

Un nœud devrait pouvoir avoir une référence vers son nœud parent, mais il ne devrait pas prendre possession de son parent. Dans l'encart 15-28, nous mettons à jour cette nouvelle définition pour que le nœud feuille puisse avoir un moyen de pointer vers son parent, branche :

Fichier : src/main.rs

use std::cell::RefCell;
use std::rc::{Rc, Weak};

#[derive(Debug)]
struct Noeud {
    valeur: i32,
    parent: RefCell<Weak<Noeud>>,
    enfants: RefCell<Vec<Rc<Noeud>>>,
}

fn main() {
    let feuille = Rc::new(Noeud {
        valeur: 3,
        parent: RefCell::new(Weak::new()),
        enfants: RefCell::new(vec![]),
    });

    println!("parent de la feuille = {:?}", feuille.parent.borrow().upgrade());

    let branche = Rc::new(Noeud {
        valeur: 5,
        parent: RefCell::new(Weak::new()),
        enfants: RefCell::new(vec![Rc::clone(&feuille)]),
    });

    *feuille.parent.borrow_mut() = Rc::downgrade(&branche);

    println!("parent de la feuille = {:?}", feuille.parent.borrow().upgrade());
}

Encart 15-28 : un nœud feuille avec une référence faible vers son nœud parent, branche

La création du nœud feuille semble être identique à la création du nœud feuille de l'encart 15-27, sauf pour le champ parent : feuille commence sans parent, donc nous créons une nouvelle instance de référence de type Weak<Noeud>, qui est vide.

A ce moment-là, lorsque nous essayons d'obtenir une référence vers le parent de feuille en utilisant la méthode upgrade, nous obtenons une valeur None. Nous constatons cela dans la première instruction println! sur la sortie :

parent de la feuille = None

Lorsque nous créons le nœud branche, il va aussi avoir une nouvelle référence Weak<Noeud> dans le champ parent, car branche n'a pas de nœud parent. Nous avons néanmoins feuille dans enfants de branche. Une fois que nous avons l'instance de Noeud dans branche, nous pouvons modifier feuille pour lui donner une référence Weak<Noeud> vers son parent. Nous utilisons la méthode borrow_mut sur la RefCell<Weak<Noeud>> du champ parent de feuille, et ensuite nous utilisons la fonction Rc::downgrade pour créer une référence de type Weak<Node> vers branche à partir du Rc<Noeud> présent dans branche.

Lorsque nous affichons à nouveau le parent de feuille, cette fois nous obtenons la variante Some qui contient branche : désormais, feuille peut accéder à son parent ! Lorsque nous affichons feuille, nous avons aussi évité la boucle qui aurait probablement fini en débordement de pile comme nous l'avions expérimenté dans l'encart 15-26 ; les références Weak<Noeud> s'écrivent (Weak) :

parent de la feuille = Some(Noeud { valeur: 5, parent: RefCell { value: (Weak) },
enfants: RefCell { value: [Noeud { valeur: 3, parent: RefCell { value: (Weak) },
enfants: RefCell { value: [] } }] } })

L'absence d'une sortie infinie nous confirme que ce code ne crée pas de boucle de références. Nous pouvons aussi le constater en affichant les valeurs que nous pouvons obtenir en faisant appel à Rc::strong_count et Rc::weak_count.

Visualiser les modifications de strong_count et weak_count

Regardons comment changent les valeurs strong_count et weak_count des instances de Rc<Noeud> en créant une portée interne et en déplaçant la création de branche dans cette portée. En faisant ceci, nous pourrons constater ce qui se passe lorsque branche est créée et lorsqu'elle sera libérée lorsqu'elle sortira de la portée. Ces modifications sont présentées dans l'encart 15-29 :

Fichier : src/main.rs

use std::cell::RefCell;
use std::rc::{Rc, Weak};

#[derive(Debug)]
struct Noeud {
    valeur: i32,
    parent: RefCell<Weak<Noeud>>,
    enfants: RefCell<Vec<Rc<Noeud>>>,
}

fn main() {
    let feuille = Rc::new(Noeud {
        valeur: 3,
        parent: RefCell::new(Weak::new()),
        enfants: RefCell::new(vec![]),
    });

    println!(
        "feuille strong = {}, weak = {}",
        Rc::strong_count(&feuille),
        Rc::weak_count(&feuille),
    );

    {
        let branche = Rc::new(Noeud {
            valeur: 5,
            parent: RefCell::new(Weak::new()),
            enfants: RefCell::new(vec![Rc::clone(&feuille)]),
        });

        *feuille.parent.borrow_mut() = Rc::downgrade(&branche);

        println!(
            "branche strong = {}, weak = {}",
            Rc::strong_count(&branche),
            Rc::weak_count(&branche),
        );

        println!(
            "feuille strong = {}, weak = {}",
            Rc::strong_count(&feuille),
            Rc::weak_count(&feuille),
        );
    }

    println!("parent de la feuille = {:?}", feuille.parent.borrow().upgrade());
    println!(
        "feuille strong = {}, weak = {}",
        Rc::strong_count(&feuille),
        Rc::weak_count(&feuille),
    );
}

Encart 15-29 : création de branche dans une portée interne et vérification des compteurs de références strong et weak

Après la création de feuille, son Rc<Noeud> a le compteur strong à 1 et le compteur weak à 0. Dans la portée interne, nous créons branche et l'associons à feuille, et à partir de là, lorsque nous affichons les compteurs, le Rc<Noeud> dans branche aura le compteur strong à 1 et le compteur weak à 1 (pour que feuille.parent pointe sur branche avec un Weak<Noeud>). Lorsque nous affichons les compteurs dans feuille nous constatons qu'il a le compteur strong à 2, car branche a maintenant un clone du Rc<Noeud> de feuille stocké dans branche.enfants, mais a toujours le compteur weak à 0.

Lorsque la portée interne se termine, branche sort de la portée et le compteur strong de Rc<Noeud> décroît à 0, donc son Noeud est libéré. Le compteur weak à 1 de feuille.parent n'a aucune répercussion suite à la libération ou non du Noeud, donc nous ne sommes pas dans une situation de fuite de mémoire !

Si nous essayons d'accéder au parent de feuille après la fin de la portée, nous allons à nouveau obtenir None. A la fin du programme, le Rc<Noeud> dans feuille a son compteur strong à 1 et son compteur weak à 0, car la variable feuille est à nouveau la seule référence au Rc<Noeud>.

Toute cette logique qui gère les compteurs et les libérations des valeurs est intégrée dans Rc<T> et Weak<T> et leurs implémentations du trait Drop. En précisant dans la définition de Noeud que le lien entre un enfant et son parent doit être une référence Weak<T>, vous pouvez avoir des nœuds parents qui pointent sur des nœuds enfants et vice versa sans risquer de créer des boucles de références et des fuites de mémoire.

Résumé

Ce chapitre a expliqué l'utilisation des pointeurs intelligents pour appliquer des garanties et des compromis différents de ceux qu'applique Rust par défaut avec les références classiques. Le type Box<T> a une taille connue et pointe sur une donnée allouée sur le tas. Le type Rc<T> compte le nombre de références vers une donnée présente sur le tas afin que cette donnée puisse avoir plusieurs propriétaires. Le type RefCell<T> nous permet de l'utiliser lorsque nous avons besoin d'un type immuable mais que nous avons besoin de changer une valeur interne à ce type, grâce à sa fonctionnalité de mutabilité interne ; elle nous permet aussi d'appliquer les règles d'emprunt à l'exécution plutôt qu'à la compilation.

Nous avons aussi vu les traits Deref et Drop, qui offrent des fonctionnalités très importantes aux pointeurs intelligents. Nous avons expérimenté les boucles de références qui peuvent causer des fuites de mémoire et nous avons vu comment les éviter en utilisant Weak<T>.

Si ce chapitre a éveillé votre curiosité et que vous souhaitez mettre en œuvre vos propres pointeurs intelligents, visitez “The Rustonomicon” pour en savoir plus.

Au chapitre suivant, nous allons parler de concurrence en Rust. Vous découvrirez peut-être même quelques nouveaux pointeurs intelligents ...