Мова програмування Rust

Цикли посилань можуть спричинити витік пам’яті

Гарантії безпеки пам’яті Rust ускладнюють, але не унеможливлюють випадкове створення пам’яті, яка ніколи не очищається (це відоме як витік пам’яті). Повне запобігання витокам пам’яті не є однією з гарантій Rust, тобто витоки пам’яті є безпечними з точки зору пам’яті в Rust. Ми можемо побачити, що Rust допускає витоки пам’яті, використовуючи Rc<T> і RefCell<T>: можливо створити посилання, у яких елементи посилаються один на одного в циклі. Це створює витоки пам’яті, тому що лічильник посилань кожного елемента в циклі ніколи не досягне 0, і значення ніколи не будуть звільнені.

Створення циклу посилань

Давайте подивимося, як може виникнути цикл посилань і як цьому запобігти, починаючи з визначення перелікa List і методу tail у Listing 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() {}

Ми використовуємо ще один варіант визначення List з Listing 15-5. Другий елемент у варіанті Cons тепер є RefCell<Rc<List>>, тобто замість можливості змінювати значення i32, як ми робили в Listing 15-24, ми хочемо змінювати значення List, на яке вказує варіант Cons. Ми також додаємо метод tail, щоб нам було зручно отримувати доступ до другого елемента, якщо в нас є варіант Cons.

У Listing 15-26 ми додаємо функцію main, яка використовує визначення з Listing 15-25. Цей код створює список у a і список у b, який вказує на список у a. Потім він змінює список у a, щоб він вказував на b, створюючи цикл посилань. Тут є оператори println!, які показують, якими є лічильники посилань у різні моменти цього процесу.

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());
}

Ми створюємо екземпляр Rc<List>, що містить значення List, у змінній a з початковим списком 5, Nil. Потім ми створюємо екземпляр Rc<List>, що містить інше значення List, у змінній b, яке містить значення 10 і вказує на список у a.

Ми змінюємо a, щоб воно вказувало на b замість Nil, створюючи цикл. Ми робимо це, використовуючи метод tail, щоб отримати посилання на RefCell<Rc<List>> у a, яке ми поміщаємо у змінну link. Потім ми використовуємо метод borrow_mut на RefCell<Rc<List>>, щоб змінити значення всередині з Rc<List>, який містить значення Nil, на Rc<List> у b.

Коли ми запускаємо цей код, залишивши останній println! закоментованим на даний момент, ми отримаємо такий вивід:

$ 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

Лічильник посилань екземплярів Rc<List> як у a, так і в b дорівнює 2 після того, як ми змінюємо список у a, щоб він вказував на b. Наприкінці main Rust звільняє змінну b, що зменшує лічильник посилань екземпляра b Rc<List> з 2 до 1. Пам’ять, яку Rc<List> має в купі, не буде звільнена на цьому етапі, тому що її лічильник посилань дорівнює 1, а не 0. Потім Rust звільняє a, що також зменшує лічильник посилань екземпляра a Rc<List> з 2 до 1. Цю пам’ять також не можна звільнити, тому що інший екземпляр Rc<List> усе ще посилається на неї. Пам’ять, виділена для списку, залишиться незбираною назавжди. Щоб візуалізувати цей цикл посилань, ми створили діаграму на Figure 15-4.

Figure 15-4: Цикл посилань списків a і b, які вказують одне на одне

Якщо ви розкоментуєте останній println! і запустите програму, Rust спробує надрукувати цей цикл із a, що вказує на b, що вказує на a, і так далі, доки не переповнить стек.

Порівняно зі справжньою програмою наслідки створення циклу посилань у цьому прикладі не дуже серйозні: одразу після того, як ми створюємо цикл посилань, програма завершується. Однак якщо складніша програма виділяла б багато пам’яті в циклі й утримувала б її тривалий час, програма використовувала б більше пам’яті, ніж їй потрібно, і могла б перевантажити систему, спричинивши вичерпання доступної пам’яті.

Створити цикл посилань непросто, але це не неможливо. Якщо у вас є значення RefCell<T>, які містять значення Rc<T>, або подібні вкладені комбінації типів із внутрішньою змінністю та підрахунком посилань, ви мусите переконатися, що не створюєте цикли; ви не можете покладатися на Rust, щоб він їх виявив. Створення циклу посилань було б логічною помилкою у вашій програмі, яку ви маєте намагатися мінімізувати за допомогою автоматизованих тестів, code review та інших практик розробки програмного забезпечення.

Інше рішення для уникнення циклів посилань — це реорганізувати ваші структури даних так, щоб деякі посилання виражали власність, а деякі — ні. У результаті ви можете мати цикли, складені з деяких відносин власності та деяких відносин без власності, і лише відносини власності впливають на те, чи може значення бути звільнене. У Listing 15-25 ми завжди хочемо, щоб варіанти Cons володіли своїм списком, тому реорганізація структури даних неможлива. Давайте розглянемо приклад із використанням графів, складених із батьківських і дочірніх вузлів, щоб побачити, коли відносини без власності є доречним способом запобігти циклам посилань.

Запобігання циклам посилань за допомогою Weak<T>

Досі ми демонстрували, що виклик Rc::clone збільшує strong_count екземпляра Rc<T>, і екземпляр Rc<T> очищається лише якщо його strong_count дорівнює 0. Ви також можете створити слабке посилання на значення всередині екземпляра Rc<T>, викликавши Rc::downgrade і передавши посилання на Rc<T>. Сильні посилання — це те, як ви можете спільно володіти екземпляром Rc<T>. Слабкі посилання не виражають відносини власності, і їхній лічильник не впливає на те, коли екземпляр Rc<T> очищається. Вони не спричинять цикл посилань, тому що будь-який цикл, що містить деякі слабкі посилання, буде розірваний, щойно сильний лічильник посилань залучених значень стане 0.

Коли ви викликаєте Rc::downgrade, ви отримуєте розумний вказівник типу Weak<T>. Замість того, щоб збільшувати strong_count в екземплярі Rc<T> на 1, виклик Rc::downgrade збільшує weak_count на 1. Тип Rc<T> використовує weak_count, щоб відстежувати, скільки існує посилань Weak<T>, подібно до strong_count. Різниця в тому, що weak_count не повинен дорівнювати 0, щоб екземпляр Rc<T> був очищений.

Оскільки значення, на яке посилається Weak<T>, могло бути звільнене, щоб робити щось зі значенням, на яке вказує Weak<T>, ви мусите переконатися, що значення все ще існує. Зробіть це, викликавши метод upgrade на екземплярі Weak<T>, який поверне Option<Rc<T>>. Ви отримаєте результат Some, якщо значення Rc<T> ще не було звільнене, і результат None, якщо значення Rc<T> було звільнене. Оскільки upgrade повертає Option<Rc<T>>, Rust забезпечить обробку випадків Some і None, і не буде недійсного вказівника.

Як приклад, замість використання списку, елементи якого знають лише про наступний елемент, ми створимо дерево, елементи якого знають про свої дочірні елементи і про свої батьківські елементи.

Створення структури даних дерева

Для початку ми побудуємо дерево з вузлами, які знають про свої дочірні вузли. Ми створимо структуру з назвою Node, яка містить власне значення i32, а також посилання на значення своїх дочірніх Node:

Filename: 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)]),
    });
}

Ми хочемо, щоб Node володів своїми дочірніми елементами, і ми хочемо розділяти цю власність із змінними, щоб ми могли безпосередньо отримувати доступ до кожного Node у дереві. Щоб зробити це, ми визначаємо елементи Vec<T> як значення типу Rc<Node>. Ми також хочемо змінювати, які вузли є дочірніми для іншого вузла, тому ми маємо RefCell<T> у children навколо Vec<Rc<Node>>.

Далі ми використаємо наше визначення структури й створимо один екземпляр Node з ім’ям leaf зі значенням 3 і без дочірніх елементів, а також інший екземпляр branch зі значенням 5 і leaf як одним зі своїх дочірніх елементів, як показано в Listing 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)]),
    });
}

Ми клонують Rc<Node> у leaf і зберігаємо це в branch, тобто Node у leaf тепер має двох власників: leaf і branch. Ми можемо дістатися від branch до leaf через branch.children, але немає способу дістатися від leaf до branch. Причина в тому, що leaf не має посилання на branch і не знає, що вони пов’язані. Ми хочемо, щоб leaf знав, що branch є його батьком. Далі ми зробимо саме це.

Додавання посилання від дочірнього елемента до його батька

Щоб зробити дочірній вузол обізнаним про свого батька, нам потрібно додати поле parent до визначення нашої структури Node. Трудність полягає у визначенні того, яким має бути тип parent. Ми знаємо, що він не може містити Rc<T>, тому що це створило б цикл посилань із leaf.parent, що вказує на branch, і branch.children, що вказує на leaf, що спричинило б те, що їхні значення strong_count ніколи не були б 0.

Якщо подумати про відносини по-іншому, батьківський вузол повинен володіти своїми дочірніми елементами: якщо батьківський вузол звільняється, його дочірні вузли також мають бути звільнені. Однак дочірній елемент не повинен володіти своїм батьком: якщо ми звільняємо дочірній вузол, батьківський усе одно має існувати. Це випадок для слабких посилань!

Отже, замість Rc<T> ми зробимо тип parent таким, що використовує Weak<T>, а саме RefCell<Weak<Node>>. Тепер наше визначення структури Node виглядає так:

Filename: 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());
}

Вузол зможе посилатися на свій батьківський вузол, але не володіє своїм батьком. У Listing 15-28 ми оновлюємо main, щоб використовувати це нове визначення, так що вузол leaf матиме спосіб посилатися на свого батька, 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());
}

Створення вузла leaf виглядає подібно до Listing 15-27 за винятком поля parent: leaf починається без батька, тому ми створюємо новий порожній екземпляр посилання Weak<Node>.

На цьому етапі, коли ми намагаємося отримати посилання на батька leaf, використовуючи метод upgrade, ми отримуємо значення None. Ми бачимо це у виводі першого оператора println!:

leaf parent = None

Коли ми створюємо вузол branch, він також матиме нове посилання Weak<Node> у полі parent, тому що branch не має батьківського вузла. У нас усе ще є leaf як один із дочірніх елементів branch. Щойно ми маємо екземпляр Node у branch, ми можемо змінити leaf, щоб дати йому посилання Weak<Node> на його батька. Ми використовуємо метод borrow_mut на RefCell<Weak<Node>> у полі parent у leaf, а потім використовуємо функцію Rc::downgrade, щоб створити посилання Weak<Node> на branch з Rc<Node> у branch.

Коли ми знову друкуємо батька leaf, цього разу ми отримаємо варіант Some, що містить branch: тепер leaf може отримати доступ до свого батька! Коли ми друкуємо leaf, ми також уникаємо циклу, який зрештою завершився переповненням стека, як у Listing 15-26; посилання Weak<Node> друкуються як (Weak):

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

Відсутність нескінченного виводу вказує на те, що цей код не створив цикл посилань. Ми також можемо визначити це, подивившись на значення, які отримуємо з виклику Rc::strong_count і Rc::weak_count.

Візуалізація змін strong_count і weak_count

Давайте подивимося, як змінюються значення strong_count і weak_count екземплярів Rc<Node>, створивши нову внутрішню область видимості та перемістивши створення branch у цю область. Зробивши це, ми можемо побачити, що відбувається, коли branch створюється, а потім звільняється, коли виходить з області видимості. Зміни показано в Listing 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),
    );
}

Після створення leaf його Rc<Node> має сильний лічильник 1 і слабкий лічильник 0. У внутрішній області видимості ми створюємо branch і пов’язуємо його з leaf, після чого, коли ми друкуємо лічильники, Rc<Node> у branch матиме сильний лічильник 1 і слабкий лічильник 1 (за leaf.parent, що вказує на branch з Weak<Node>). Коли ми друкуємо лічильники в leaf, ми побачимо, що він матиме сильний лічильник 2, тому що branch тепер має клон Rc<Node> leaf, збережений у branch.children, але все ще матиме слабкий лічильник 0.

Коли внутрішня область видимості закінчується, branch виходить з області видимості, і сильний лічильник Rc<Node> зменшується до 0, тож його Node звільняється. Слабкий лічильник 1 з leaf.parent не має жодного впливу на те, чи буде Node звільнено, або ні, тож ми не отримуємо жодних витоків пам’яті!

Якщо ми спробуємо отримати доступ до батька leaf після завершення області видимості, ми знову отримаємо None. Наприкінці програми Rc<Node> у leaf має сильний лічильник 1 і слабкий лічильник 0, тому що змінна leaf тепер знову є єдиним посиланням на Rc<Node>.

Уся логіка, що керує лічильниками та звільненням значень, вбудована в Rc<T> і Weak<T> та їхні реалізації трейту Drop. Вказавши, що відношення від дочірнього елемента до його батька має бути посиланням Weak<T> у визначенні Node, ви можете мати батьківські вузли, що вказують на дочірні вузли, і навпаки, без створення циклу посилань і витоків пам’яті.

Підсумок

Цей розділ охоплював, як використовувати розумні вказівники, щоб робити різні гарантії та компроміси порівняно з тими, які Rust робить за замовчуванням зі звичайними посиланнями. Тип Box<T> має відомий розмір і вказує на дані, виділені в купі. Тип Rc<T> відстежує кількість посилань на дані в купі, щоб дані могли мати кількох власників. Тип RefCell<T> з його внутрішньою змінністю дає нам тип, який ми можемо використовувати, коли нам потрібен незмінний тип, але треба змінити внутрішнє значення цього типу; він також забезпечує правила запозичення під час виконання замість часу компіляції.

Також було розглянуто трейти Deref і Drop, які забезпечують багато функціональності розумних вказівників. Ми дослідили цикли посилань, які можуть спричиняти витоки пам’яті, і те, як запобігти їм за допомогою Weak<T>.

Якщо цей розділ викликав у вас інтерес і ви хочете реалізувати власні розумні вказівники, перегляньте “The Rustonomicon” для отримання більш корисної інформації.

Далі ми говоритимемо про конкурентність у Rust. Ви навіть дізнаєтеся про кілька нових розумних вказівників.