Język programowania Rust

Cykle referencji mogą prowadzić do wycieków pamięci

Gwarancje bezpieczeństwa pamięci w Rust sprawiają, że trudno, ale nie jest niemożliwe, przypadkowe tworzenie pamięci, która nigdy nie jest zwalniana (znane jako wyciek pamięci). Całkowite zapobieganie wyciekom pamięci nie jest jedną z gwarancji Rust, co oznacza, że wycieki pamięci są bezpieczne w Rust. Możemy zobaczyć, że Rust dopuszcza wycieki pamięci, używając Rc<T> i RefCell<T>: Możliwe jest tworzenie referencji, w których elementy odwołują się do siebie w cyklu. Tworzy to wycieki pamięci, ponieważ licznik referencji każdego elementu w cyklu nigdy nie osiągnie 0, a wartości nigdy nie zostaną usunięte.

Tworzenie cyklu referencji

Przyjrzyjmy się, jak może powstać cykl referencji i jak mu zapobiec, zaczynając od definicji enum List i metody tail w Listingu 15-25.

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 tail(&self) -> Option<&RefCell<Rc<List>>> {
        match self {
            Cons(_, item) => Some(item),
            Nil => None,
        }
    }
}

fn main() {}

Używamy kolejnej wariacji definicji List z Listingu 15-5. Drugi element wariantu Cons to teraz RefCell<Rc<List>>, co oznacza, że zamiast możliwości modyfikacji wartości i32, jak to robiliśmy w Listingu 15-24, chcemy modyfikować wartość List, na którą wskazuje wariant Cons. Dodajemy również metodę tail, aby ułatwić nam dostęp do drugiego elementu, jeśli mamy wariant Cons.

W Listingu 15-26 dodajemy funkcję main, która używa definicji z Listingu 15-25. Ten kod tworzy listę w a i listę w b, która wskazuje na listę w a. Następnie modyfikuje listę w a, aby wskazywała na b, tworząc cykl referencji. Po drodze znajdują się instrukcje println!, aby pokazać, jakie są liczniki referencji w różnych punktach tego procesu.

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 tail(&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!("a initial rc count = {}", Rc::strong_count(&a));
    println!("a next item = {:?}", a.tail());

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

    println!("a rc count after b creation = {}", Rc::strong_count(&a));
    println!("b initial rc count = {}", Rc::strong_count(&b));
    println!("b next item = {:?}", b.tail());

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

    println!("b rc count after changing a = {}", Rc::strong_count(&b));
    println!("a rc count after changing a = {}", Rc::strong_count(&a));

    // Uncomment the next line to see that we have a cycle;
    // it will overflow the stack.
    // println!("a next item = {:?}", a.tail());
}

Tworzymy instancję Rc<List> przechowującą wartość List w zmiennej a z początkową listą 5, Nil. Następnie tworzymy instancję Rc<List> przechowującą inna wartość List w zmiennej b, która zawiera wartość 10 i wskazuje na listę w a.

Modyfikujemy a tak, aby wskazywała na b zamiast Nil, tworząc cykl. Robimy to, używając metody tail do uzyskania referencji do RefCell<Rc<List>> w a, którą umieszczamy w zmiennej link. Następnie używamy metody borrow_mut w RefCell<Rc<List>>, aby zmienić wewnętrzną wartość z Rc<List>, która przechowuje wartość Nil, na Rc<List> w b.

Po uruchomieniu tego kodu, z pominięciem ostatniego println! na razie, otrzymamy następujący wynik:

$ cargo run
   Compiling cons-list v0.1.0 (file:///projects/cons-list)
    Finished `dev` profile [unoptimized + debuginfo] target(s) in 0.53s
     Running `target/debug/cons-list`
a initial rc count = 1
a next item = Some(RefCell { value: Nil })
a rc count after b creation = 2
b initial rc count = 1
b next item = Some(RefCell { value: Cons(5, RefCell { value: Nil }) })
b rc count after changing a = 2
a rc count after changing a = 2

Licznik referencji instancji Rc<List> zarówno w a, jak i b wynosi 2 po zmianie listy w a na wskazującą na b. Na końcu main Rust usuwa zmienną b, co zmniejsza licznik referencji instancji Rc<List> z b z 2 do 1. Pamięć, którą Rc<List> ma na stercie, nie zostanie w tym momencie usunięta, ponieważ jej licznik referencji wynosi 1, a nie 0. Następnie Rust usuwa a, co zmniejsza licznik referencji instancji Rc<List> z a również z 2 do 1. Pamięć tej instancji również nie może zostać usunięta, ponieważ inna instancja Rc<List> nadal się do niej odwołuje. Pamięć alokowana na listę pozostanie niezebrana na zawsze. Aby zwizualizować ten cykl referencji, stworzyliśmy diagram na Rysunku 15-4.

Rysunek 15-4: Cykl referencji list a i b wskazujących na siebie nawzajem

Jeśli odkomentujesz ostatnią instrukcję println! i uruchomisz program, Rust spróbuje wypisać ten cykl, w którym a wskazuje na b, b na a i tak dalej, aż do przepełnienia stosu.

W porównaniu do rzeczywistego programu, konsekwencje tworzenia cyklu referencji w tym przykładzie nie są bardzo poważne: zaraz po utworzeniu cyklu referencji program się kończy. Jednakże, jeśli bardziej złożony program alokowałby dużo pamięci w cyklu i utrzymywał ją przez długi czas, program zużywałby więcej pamięci niż potrzebował i mógłby przeciążyć system, powodując wyczerpanie dostępnej pamięci.

Tworzenie cykli referencji nie jest łatwe, ale też nie niemożliwe. Jeśli masz wartości RefCell<T>, które zawierają wartości Rc<T> lub podobne zagnieżdżone połączenia typów z mutowalnością wewnętrzną i zliczaniem referencji, musisz zapewnić, że nie tworzysz cykli; nie możesz polegać na Rust w ich wykrywaniu. Tworzenie cyklu referencji byłoby błędem logicznym w twoim programie, który powinieneś minimalizować za pomocą automatycznych testów, przeglądów kodu i innych praktyk rozwoju oprogramowania.

Innym rozwiązaniem pozwalającym uniknąć cykli referencji jest reorganizacja struktur danych tak, aby niektóre referencje wyrażały własność, a inne nie. W rezultacie możesz mieć cykle składające się z relacji własności i relacji braku własności, a tylko relacje własności wpływają na to, czy wartość może zostać usunięta. W Listingu 15-25 zawsze chcemy, aby warianty Cons posiadały swoją listę, więc reorganizacja struktury danych nie jest możliwa. Przyjrzyjmy się przykładowi używającemu grafów składających się z węzłów rodzicielskich i węzłów potomnych, aby zobaczyć, kiedy relacje braku własności są odpowiednim sposobem na zapobieganie cyklom referencji.

Zapobieganie cyklom referencji za pomocą Weak<T>

Do tej pory wykazaliśmy, że wywołanie Rc::clone zwiększa strong_count instancji Rc<T>, a instancja Rc<T> jest usuwana tylko, jeśli jej strong_count wynosi 0. Możesz również utworzyć słabą referencję do wartości w instancji Rc<T>, wywołując Rc::downgrade i przekazując referencję do Rc<T>. Silne referencje to sposób na współdzielenie własności instancji Rc<T>. Słabe referencje nie wyrażają relacji własności, a ich licznik nie wpływa na to, kiedy instancja Rc<T> jest usuwana. Nie spowodują one cyklu referencji, ponieważ każdy cykl zawierający słabe referencje zostanie przerwany, gdy silny licznik referencji wartości w nim zaangażowanych osiągnie 0.

Kiedy wywołujesz Rc::downgrade, otrzymujesz wskaźnik sprytny typu Weak<T>. Zamiast zwiększać strong_count w instancji Rc<T> o 1, wywołanie Rc::downgrade zwiększa weak_count o 1. Typ Rc<T> używa weak_count do śledzenia liczby istniejących referencji Weak<T>, podobnie jak strong_count. Różnica polega na tym, że weak_count nie musi wynosić 0, aby instancja Rc<T> została usunięta.

Ponieważ wartość, do której odwołuje się Weak<T>, mogła zostać usunięta, aby coś zrobić z wartością, na którą wskazuje Weak<T>, musisz upewnić się, że wartość nadal istnieje. Zrób to, wywołując metodę upgrade na instancji Weak<T>, która zwróci Option<Rc<T>>. Otrzymasz wynik Some, jeśli wartość Rc<T> nie została jeszcze usunięta, i wynik None, jeśli wartość Rc<T> została usunięta. Ponieważ upgrade zwraca Option<Rc<T>>, Rust zapewni, że przypadki Some i None zostaną obsłużone, i nie będzie nieprawidłowego wskaźnika.

Jako przykład, zamiast używać listy, której elementy wiedzą tylko o następnym elemencie, stworzymy drzewo, którego elementy wiedzą o swoich elementach potocznych i swoich elementach nadrzędnych.

Tworzenie struktury danych drzewa

Na początek zbudujemy drzewo z węzłami, które wiedzą o swoich węzłach potocznych. Stworzymy strukturę o nazwie Node, która będzie zawierała własną wartość i32, a także referencje do swoich potomnych węzłów Node:

Nazwa pliku: src/main.rs

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

#[derive(Debug)]
struct Node {
    value: i32,
    children: RefCell<Vec<Rc<Node>>>,
}

fn main() {
    let leaf = Rc::new(Node {
        value: 3,
        children: RefCell::new(vec![]),
    });

    let branch = Rc::new(Node {
        value: 5,
        children: RefCell::new(vec![Rc::clone(&leaf)]),
    });
}

Chcemy, aby Node był właścicielem swoich dzieci, i chcemy współdzielić tę własność ze zmiennymi, abyśmy mogli bezpośrednio uzyskiwać dostęp do każdego Node w drzewie. Aby to zrobić, definiujemy elementy Vec<T> jako wartości typu Rc<Node>. Chcemy również modyfikować, które węzły są dziećmi innego węzła, więc mamy RefCell<T> w children wokół Vec<Rc<Node>>.

Następnie użyjemy naszej definicji struktury i stworzymy jedną instancję Node o nazwie leaf z wartością 3 i bez dzieci, oraz inną instancję o nazwie branch z wartością 5 i leaf jako jedno z jej dzieci, jak pokazano w Listingu 15-27.

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

#[derive(Debug)]
struct Node {
    value: i32,
    children: RefCell<Vec<Rc<Node>>>,
}

fn main() {
    let leaf = Rc::new(Node {
        value: 3,
        children: RefCell::new(vec![]),
    });

    let branch = Rc::new(Node {
        value: 5,
        children: RefCell::new(vec![Rc::clone(&leaf)]),
    });
}

Klonujemy Rc<Node> z leaf i przechowujemy go w branch, co oznacza, że Node z leaf ma teraz dwóch właścicieli: leaf i branch. Możemy przejść od branch do leaf poprzez branch.children, ale nie ma sposobu, aby przejść od leaf do branch. Powodem jest to, że leaf nie ma referencji do branch i nie wie, że są ze sobą powiązane. Chcemy, aby leaf wiedziało, że branch jest jego rodzicem. Zrobimy to w następnym kroku.

Dodawanie referencji od dziecka do jego rodzica

Aby węzeł potomny był świadomy swojego rodzica, musimy dodać pole parent do definicji naszej struktury Node. Problem polega na podjęciu decyzji, jaki typ powinno mieć parent. Wiemy, że nie może zawierać Rc<T>, ponieważ stworzyłoby to cykl referencji, w którym leaf.parent wskazywałoby na branch, a branch.children na leaf, co spowodowałoby, że ich wartości strong_count nigdy nie byłyby równe 0.

Rozważając relacje w inny sposób, węzeł rodzicielski powinien być właścicielem swoich dzieci: Jeśli węzeł rodzicielski zostanie usunięty, jego węzły potomne również powinny zostać usunięte. Jednak dziecko nie powinno być właścicielem swojego rodzica: Jeśli usuniemy węzeł potomny, rodzic powinien nadal istnieć. To przypadek dla słabych referencji!

Tak więc, zamiast Rc<T>, typ parent będzie używał Weak<T>, a konkretnie RefCell<Weak<Node>>. Teraz definicja naszej struktury Node wygląda tak:

Nazwa pliku: src/main.rs

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

#[derive(Debug)]
struct Node {
    value: i32,
    parent: RefCell<Weak<Node>>,
    children: RefCell<Vec<Rc<Node>>>,
}

fn main() {
    let leaf = Rc::new(Node {
        value: 3,
        parent: RefCell::new(Weak::new()),
        children: RefCell::new(vec![]),
    });

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

    let branch = Rc::new(Node {
        value: 5,
        parent: RefCell::new(Weak::new()),
        children: RefCell::new(vec![Rc::clone(&leaf)]),
    });

    *leaf.parent.borrow_mut() = Rc::downgrade(&branch);

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

Węzeł będzie mógł odwoływać się do swojego węzła rodzicielskiego, ale nie posiada swojego rodzica. W Listingu 15-28 aktualizujemy main, aby używał tej nowej definicji, tak aby węzeł leaf miał sposób odwoływania się do swojego rodzica, branch.

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

#[derive(Debug)]
struct Node {
    value: i32,
    parent: RefCell<Weak<Node>>,
    children: RefCell<Vec<Rc<Node>>>,
}

fn main() {
    let leaf = Rc::new(Node {
        value: 3,
        parent: RefCell::new(Weak::new()),
        children: RefCell::new(vec![]),
    });

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

    let branch = Rc::new(Node {
        value: 5,
        parent: RefCell::new(Weak::new()),
        children: RefCell::new(vec![Rc::clone(&leaf)]),
    });

    *leaf.parent.borrow_mut() = Rc::downgrade(&branch);

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

Tworzenie węzła leaf wygląda podobnie do Listingu 15-27, z wyjątkiem pola parent: leaf zaczyna bez rodzica, więc tworzymy nową, pustą instancję referencji Weak<Node>.

W tym momencie, gdy próbujemy uzyskać referencję do rodzica leaf za pomocą metody upgrade, otrzymujemy wartość None. Widzimy to w wynikach pierwszej instrukcji println!:

leaf parent = None

Kiedy tworzymy węzeł branch, będzie on również miał nową referencję Weak<Node> w polu parent, ponieważ branch nie ma węzła rodzicielskiego. Nadal mamy leaf jako jedno z dzieci branch. Gdy już mamy instancję Node w branch, możemy zmodyfikować leaf, aby nadać mu referencję Weak<Node> do jego rodzica. Używamy metody borrow_mut w RefCell<Weak<Node>> w polu parent węzła leaf, a następnie używamy funkcji Rc::downgrade do stworzenia referencji Weak<Node> do branch z Rc<Node> w branch.

Kiedy ponownie wypiszemy rodzica leaf, tym razem otrzymamy wariant Some przechowujący branch: Teraz leaf może uzyskać dostęp do swojego rodzica! Gdy wypiszemy leaf, unikamy również cyklu, który ostatecznie zakończył się przepełnieniem stosu, jak to miało miejsce w Listingu 15-26; referencje Weak<Node> są wypisywane jako (Weak):

leaf parent = Some(Node { value: 5, parent: RefCell { value: (Weak) },
children: RefCell { value: [Node { value: 3, parent: RefCell { value: (Weak) },
children: RefCell { value: [] } }] } })

Brak nieskończonego wyniku wskazuje, że ten kod nie stworzył cyklu referencji. Możemy to również stwierdzić, patrząc na wartości, które otrzymujemy po wywołaniu Rc::strong_count i Rc::weak_count.

Wizualizacja zmian w strong_count i weak_count

Spójrzmy, jak zmieniają się wartości strong_count i weak_count instancji Rc<Node>, tworząc nowy wewnętrzny zakres i przenosząc tworzenie branch do tego zakresu. W ten sposób możemy zobaczyć, co dzieje się, gdy branch jest tworzone, a następnie usuwane, gdy wyjdzie poza zakres. Modyfikacje pokazano w Listingu 15-29.

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

#[derive(Debug)]
struct Node {
    value: i32,
    parent: RefCell<Weak<Node>>,
    children: RefCell<Vec<Rc<Node>>>,
}

fn main() {
    let leaf = Rc::new(Node {
        value: 3,
        parent: RefCell::new(Weak::new()),
        children: RefCell::new(vec![]),
    });

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

    {
        let branch = Rc::new(Node {
            value: 5,
            parent: RefCell::new(Weak::new()),
            children: RefCell::new(vec![Rc::clone(&leaf)]),
        });

        *leaf.parent.borrow_mut() = Rc::downgrade(&branch);

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

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

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

Po utworzeniu leaf, jego Rc<Node> ma silny licznik równy 1 i słaby licznik równy 0. W wewnętrznym zakresie tworzymy branch i kojarzymy go z leaf, po czym, gdy wypiszemy liczniki, Rc<Node> w branch będzie miało silny licznik równy 1 i słaby licznik równy 1 (dla leaf.parent wskazującego na branch za pomocą Weak<Node>). Kiedy wypiszemy liczniki w leaf, zobaczymy, że będzie miało silny licznik równy 2, ponieważ branch ma teraz klon Rc<Node> z leaf przechowywany w branch.children, ale nadal będzie miało słaby licznik równy 0.

Kiedy wewnętrzny zakres się kończy, branch wychodzi poza zakres, a silny licznik Rc<Node> zmniejsza się do 0, więc jego Node zostaje usunięty. Słaby licznik równy 1 z leaf.parent nie ma wpływu na to, czy Node jest usuwany, więc nie mamy wycieków pamięci!

Jeśli spróbujemy uzyskać dostęp do rodzica leaf po zakończeniu zakresu, ponownie otrzymamy None. Na końcu programu Rc<Node> w leaf ma silny licznik równy 1 i słaby licznik równy 0, ponieważ zmienna leaf jest teraz ponownie jedyną referencją do Rc<Node>.

Wszystkie logiki zarządzające licznikami i usuwaniem wartości są wbudowane w Rc<T> i Weak<T> oraz ich implementacje cechy Drop. Określając, że relacja od dziecka do rodzica powinna być referencją Weak<T> w definicji Node, jesteś w stanie sprawić, że węzły rodzicielskie wskazują na węzły potoczne i vice versa bez tworzenia cyklu referencji i wycieków pamięci.

Podsumowanie

Ten rozdział omówił, jak używać wskaźników sprytnych, aby uzyskać różne gwarancje i kompromisy w porównaniu do tych, które Rust domyślnie zapewnia ze zwykłymi referencjami. Typ Box<T> ma znany rozmiar i wskazuje na dane alokowane na stercie. Typ Rc<T> śledzi liczbę referencji do danych na stercie, tak aby dane mogły mieć wielu właścicieli. Typ RefCell<T> ze swoją mutowalnością wewnętrzną daje nam typ, którego możemy używać, gdy potrzebujemy nimutowalnego typu, ale musimy zmienić wewnętrzną wartość tego typu; egzekwuje on również zasady pożyczania w czasie wykonania zamiast w czasie kompilacji.

Omówiono również cechy Deref i Drop, które umożliwiają wiele funkcjonalności wskaźników sprytnych. Zbadaliśmy cykle referencji, które mogą powodować wycieki pamięci, i jak im zapobiegać za pomocą Weak<T>.

Jeśli ten rozdział wzbudził Twoje zainteresowanie i chcesz zaimplementować własne wskaźniki sprytne, zajrzyj do „The Rustonomicon” po więcej przydatnych informacji.

Następnie będziemy rozmawiać o współbieżności w Rust. Nauczysz się nawet kilku nowych wskaźników sprytnych.