Циклы ссылок могут приводить к утечкам памяти
Гарантии безопасности памяти Rust делают трудным, но не невозможным, случайное создание памяти, которая никогда не очищается (известной как утечка памяти). Полное предотвращение утечек памяти не является одной из гарантий Rust, что означает, что утечки памяти являются безопасными для памяти в Rust. Мы можем видеть, что Rust допускает утечки памяти, используя Rc<T> и RefCell<T>: возможно создание ссылок, где элементы ссылаются друг на друга в цикле. Это создаёт утечки памяти, потому что счётчик ссылок каждого элемента в цикле никогда не достигнет 0, и значения никогда не будут удалены.
Создание цикла ссылок
Давайте посмотрим, как может произойти цикл ссылок и как его предотвратить, начиная с определения перечисления List и метода tail в Листинге 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() {}
Мы используем another вариацию определения List из Листинга 15-5. Второй элемент в варианте Cons теперь RefCell<Rc<List>>, что означает, что instead возможности изменять значение i32, как мы делали в Листинге 15-24, мы хотим изменять значение List, на которое указывает вариант Cons. Мы также добавляем метод tail, чтобы нам было удобно получать доступ ко второму элементу, если у нас есть вариант Cons.
В Листинге 15-26 мы добавляем функцию main, которая использует определения из Листинга 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>, содержащий another значение 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! закомментированным на moment, мы получим этот вывод:
$ 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> в both a и b равен 2 after того, как мы изменяем список в a чтобы указывать на b. В конце main Rust удаляет переменную b, что уменьшает счётчик ссылок экземпляра Rc<List> b с 2 до 1. Память, которую Rc<List> имеет в куче, не будет удалена в этот point, потому что её счётчик ссылок равен 1, а не 0. Затем Rust удаляет a, что уменьшает счётчик ссылок экземпляра Rc<List> a с 2 до 1 также. Память этого экземпляра не может быть удалена either, потому что other экземпляр Rc<List> всё ещё ссылается на неё. Память, выделенная для списка, останется неосвобождённой навсегда. Чтобы визуализировать этот цикл ссылок, мы создали диаграмму на Рисунке 15-4.
Рисунок 15-4: Цикл ссылок списков a и b, указывающих друг на друга
Если вы раскомментируете последний println! и запустите программу, Rust попытается напечатать этот цикл с a, указывающим на b, указывающим на a и так далее, until он переполнит стек.
По сравнению с реальной программой, последствия создания цикла ссылок в этом примере не очень серьёзны: сразу after того, как мы создаём цикл ссылок, программа завершается. However, если бы более сложная программа выделяла много памяти в цикле и удерживала её в течение long времени, программа использовала бы больше памяти, чем нужно, и могла бы перегрузить систему, вызывая исчерпание доступной памяти.
Создание циклов ссылок не делается легко, но и не невозможно. Если у вас есть значения RefCell<T>, которые содержат значения Rc<T>, или similar вложенные комбинации типов с внутренней изменяемостью и подсчётом ссылок, вы должны гарантировать, что не создаёте циклы; вы не можете полагаться на Rust в их обнаружении. Создание цикла ссылок было бы логической ошибкой в вашей программе, которую вы должны использовать автоматизированные тесты, обзоры кода и other практики разработки программного обеспечения для минимизации.
Another решение для избежания циклов ссылок — реорганизация ваших структур данных так, чтобы some ссылки выражали владение, а some ссылки — нет. В результате вы можете иметь циклы, состоящие из some отношений владения и some отношений без владения, и only отношения владения влияют на то, будет ли значение удалено или нет. В Листинге 15-25 мы always хотим, чтобы варианты Cons владели своим списком, поэтому реорганизация структуры данных невозможна. Давайте рассмотрим пример использования графов, состоящих из родительских узлов и дочерних узлов, чтобы увидеть, когда отношения без владения являются подходящим способом предотвращения циклов ссылок.
Предотвращение циклов ссылок с помощью Weak<T>
До сих пор мы демонстрировали, что вызов Rc::clone увеличивает strong_count экземпляра Rc<T>, и экземпляр Rc<T> очищается only если его strong_count равен 0. Вы также можете создать слабую ссылку на значение внутри экземпляра Rc<T>, вызвав Rc::downgrade и передав ссылку на Rc<T>. Сильные ссылки (Strong references) — это то, как вы можете разделять владение экземпляром Rc<T>. Слабые ссылки (Weak references) не выражают отношение владения, и их счётчик не влияет на то, когда экземпляр Rc<T> очищается. Они не вызовут цикла ссылок, потому что any цикл, включающий some слабые ссылки, будет разорван, once счётчик сильных ссылок задействованных значений станет 0.
Когда вы вызываете Rc::downgrade, вы получаете умный указатель типа Weak<T>. Instead увеличения strong_count в экземпляре Rc<T> на 1, вызов Rc::downgrade увеличивает weak_count на 1. Тип Rc<T> использует weak_count для отслеживания того, сколько ссылок Weak<T> существует, similar strong_count. Разница в том, что weak_count не обязательно должен быть 0 для очистки экземпляра Rc<T>.
Поскольку значение, на которое ссылается Weak<T>, могло быть удалено, чтобы сделать anything со значением, на которое указывает Weak<T>, вы должны убедиться, что значение всё ещё существует. Сделайте это, вызвав метод upgrade на экземпляре Weak<T>, который вернёт Option<Rc<T>>. Вы получите результат Some, если значение Rc<T> ещё не было удалено, и результат None, если значение Rc<T> было удалено. Поскольку upgrade возвращает Option<Rc<T>>, Rust гарантирует, что случаи Some и None обрабатываются, и не будет недействительного указателя.
В качестве примера, instead использования списка, элементы которого знают only о следующем элементе, мы создадим дерево, элементы которого знают о своих дочерних элементах и своих родительских элементах.
Создание древовидной структуры данных
Для начала мы построим дерево с узлами, которые знают о своих дочерних узлах. Мы создадим структуру с именем 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 в дереве directly. Для этого мы определяем элементы Vec<T> как значения типа Rc<Node>. Мы также хотим изменять, какие узлы являются детьми другого узла, поэтому у нас есть RefCell<T> в children вокруг Vec<Rc<Node>>.
Далее мы используем наше определение структуры и создаём один экземпляр Node с именем leaf со значением 3 и без детей, и another экземпляр с именем branch со значением 5 и leaf как одним из его детей, как показано в Листинге 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.
Думая об отношениях another way, родительский узел должен владеть своими детьми: если родительский узел удалён, его дочерние узлы должны быть также удалены. However, ребёнок не должен владеть своим родителем: если мы удалим дочерний узел, родитель должен всё ещё существовать. Это случай для слабых ссылок!
Итак, instead Rc<T>, мы сделаем тип parent использующим Weak<T>, specifically 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.
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 выглядит similar Листингу 15-27 за исключением поля parent: leaf начинается без родителя, поэтому мы создаём новый, пустой экземпляр ссылки Weak<Node>.
В этот point, когда мы пытаемся получить ссылку на родителя leaf, используя метод upgrade, мы получаем значение None. Мы видим это в выводе из первого оператора println!:
leaf parent = None
Когда мы создаём узел branch, он также будет иметь новую ссылку Weak<Node> в поле parent, потому что branch не имеет родительского узла. У нас всё ещё есть leaf как один из детей branch. Once мы имеем экземпляр 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.
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), ); }
After создания leaf его Rc<Node> имеет сильный счётчик 1 и слабый счётчик 0. Во внутренней области видимости мы создаём branch и связываем его с leaf, в which point, когда мы печатаем счётчики, Rc<Node> в branch будет иметь сильный счётчик 1 и слабый счётчик 1 (для leaf.parent, указывающего на branch с Weak<Node>). Когда мы печатаем счётчики в leaf, мы увидим, что он будет иметь сильный счётчик 2, потому что branch теперь имеет клон Rc<Node> из leaf, сохранённый в branch.children, но будет still иметь слабый счётчик 0.
Когда внутренняя область видимости заканчивается, branch выходит из области видимости, и сильный счётчик Rc<Node> уменьшается до 0, поэтому его Node удаляется. Слабый счётчик 1 от leaf.parent не имеет влияния на то, будет ли Node удалён или нет, поэтому мы не получаем any утечек памяти!
Если мы попытаемся получить доступ к родителю leaf after конца области видимости, мы снова получим None. В конце программы Rc<Node> в leaf имеет сильный счётчик 1 и слабый счётчик 0, потому что переменная leaf теперь again является единственной ссылкой на Rc<Node>.
Вся логика, которая управляет счётчиками и удалением значений, встроена в Rc<T> и Weak<T> и их реализации трейта Drop. Указав, что отношение от ребёнка к его родителю должно быть ссылкой Weak<T> в определении Node, вы able иметь родительские узлы, указывающие на дочерние узлы, и наоборот без создания цикла ссылок и утечек памяти.
Итоги
Эта глава охватила, как использовать умные указатели для создания различных гарантий и компромиссов от тех, которые Rust делает по умолчанию с обычными ссылками. Тип Box<T> имеет известный размер и указывает на данные, выделенные в куче. Тип Rc<T> отслеживает количество ссылок на данные в куче, чтобы данные могли иметь нескольких владельцев. Тип RefCell<T> с его внутренней изменяемостью даёт нам тип, который мы можем использовать, когда нам нужен неизменяемый тип, но необходимо изменить внутреннее значение этого типа; он также обеспечивает соблюдение правил заимствования во время выполнения instead во время компиляции.
Также обсуждались трейты Deref и Drop, которые обеспечивают много функциональности умных указателей. Мы исследовали циклы ссылок, которые могут вызывать утечки памяти, и как предотвратить их с помощью Weak<T>.
Если эта глава возбудила ваш интерес и вы хотите реализовать свои собственные умные указатели, проверьте «The Rustonomicon» для получения more полезной информации.
Далее мы поговорим о конкурентности в Rust. Вы даже узнаете о нескольких новых умных указателях.