Ссылочные зацикливания могут приводить к утечке памяти
Гарантии безопасности памяти в 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 list, который содержит 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` 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, что уменьшает количество ссылок на 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. Вы также можете создать слабую ссылку на значение внутри экземпляра 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<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>. Мы также хотим изменять те узлы, которые являются дочерними по отношению к другому узлу, поэтому у нас есть тип RefCell<T> в поле children оборачивающий тип 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> имеет значения strong count равное 1 и weak count равное 0. Во внутренней области мы создаём branch и связываем её с leaf, после чего при печати значений счётчиков Rc<Node> в branch они будет иметь strong count 1 и weak count 1 (для leaf.parent указывающего на branch с Weak<Node> ). Когда мы распечатаем счётчики из leaf, мы увидим, что они будут иметь strong count 2, потому что branch теперь имеет клон Rc<Node> переменной leaf хранящийся в branch.children, но все равно будет иметь weak count 0.
Когда заканчивается внутренняя область видимости, branch выходит из области видимости и strong count Rc<Node> уменьшается до 0, поэтому его Node удаляется. Weak count 1 из leaf.parent не имеет никакого отношения к тому, был ли Node удалён, поэтому не будет никаких утечек памяти!
Если мы попытаемся получить доступ к родителю переменной leaf после окончания области видимости, мы снова получим значение None. В конце программы Rc<Node> внутри leaf имеет strong count 1 и weak count 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. Вы даже узнаете о нескольких новых умных указателях.