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

Цикли посилань можуть призвести до витоку пам'яті

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

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

Подивімося, як може виникнути цикл посилань і як цьому запобігти, почавши з визначення енуму List і методу tail у Блоці коду 15-25:

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

fn main() {}

Блок коду 15-25: визначення списку cons, що містить RefCell<T>, щоб ми могли змінювати, на що посилається варіант Cons

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

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

Файл: 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 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());
}

Блок коду 15-26: створення циклу посилань з двох значень List, що вказують одне на іншого

Ми створили екземпляр 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 [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, яка зменшує лічильник посилань екземпляра Rc<List> b з 2 до 1. Пам'ять, яку Rc<List> тримає в купі, не буде скинуто у в цей момент, тому що лічильник посилань дорівнює 1, а не 0. Потім Rust очищує a, так само зменшуючи кількість посилань екземпляра Rc<List> a з 2 до 1. Пам'ять цього екземпляра також не може бути очищена, тому що інший екземпляр Rc<List> досі посилається на неї. Пам'ять, виділена для списку, залишиться незвільненою назавжди. Щоб візуалізувати цей цикл посилань, ми створили діаграму на Рисунку 15-4.

Рисунок 15-4: цикл посилань у списках a і b, що вказують один на іншого

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

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

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

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

Запобігання циклам посилань: перетворення Rc<T> на Weak<T>

Поки що ми продемонстрували, що виклик Rc::clone збільшує strong_count у екземплярі Rc<T>, і екземпляр Rc<T> очищується лише якщо його strong_count дорівнює 0. Ви також можете створити weak reference на значення в екземплярі 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 і дочірні вузли

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

Файл: 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>. Ми також хочемо змінити, які вузли є дочірніми для іншого вузла, тож ми маємо в children RefCell<T> навколо Vec<Rc<Node>>.

Далі ми використаємо визначення нашої структури і створимо один екземпляр Node з назвою leaf, значенням 3 і без дочірніх вузлів, і інший екземпляр з назвою branch, значенням 5 і leaf як один з дочірніх вузлів, як показано у Блоці коду 15-27:

Файл: 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)]),
    });
}

Блок коду 15-27: створення вузла leaf без дочірніх вузлів і вузла branch з одним дочірнім вузлом 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 виглядає наступним чином:

Файл: 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());
}

Вузол тепер може посилатися на батьківський вузол, але не володіє ним. У Блоці коду 15-28 ми оновлюємо main, щоб використати нове визначення, так щоб вузол leaf матиме спосіб послатися на батьківський вузол branch:

Файл: 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());
}

Блок коду 15-28: вузол leaf зі слабким посиланням на свій батьківський вузол branch

Створення вузла leaf виглядає схожим на Блок коду 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, то також уникаємо циклу, який врешті-решт переповнив би стеку, як було у Блоці коду 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 створюється, а потім очищується, коли виходить за межі області видимості. Зміни показані у Блоці коду 15-29:

Файл: 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 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),
    );
}

Блок коду 15-29: створення branch у внутрішній області видимості і перевірка лічильників сильних та слабких посилань

Після створення leaf його Rc<Node> налічує 1 сильне посилання і 1 слабке. У внутрішній області видимості ми створюємо 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. Вказавши у визначенні Node, що стосунки дочірнього вузла до батьківського мають бути посиланням Weak<T>, ви змогли отримати взаємні посилання з батьківських вузлів до дочірніх і назад, не створивши циклу посилань і витоку пам'яті.

Підсумок

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

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

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

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