Ссылочные зацикливания могут приводить к утечке памяти
Гарантии безопасности памяти в 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
, так что можно изменять то, на что ссылается вариант 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>
с 2 на 1. Память, на которую Rc<List>
указывает в куче, на этом этапе не будет удалена, потому что её счётчик ссылок равен 1, а не 0. Затем Rust удаляет a
, что также уменьшает счётчик ссылок экземпляра a
Rc
с 2 до 1. Память этого экземпляра также не может быть удалена, потому что другой экземпляр Rc
по-прежнему ссылается на неё. Память, выделенная для списка, навсегда останется не освобождённой. Чтобы наглядно представить этот эталонный цикл, мы создали диаграмму на Рисунке 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::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>
.
Сильные ссылки - это способ, которым вы можете делиться владением экземпляра Rc<T>
. Слабые ссылки не выражают отношения владения. Они не будут вызывать ссылочную зацикленность, потому что любой цикл, включающий некоторые слабые ссылки, будет прерван, как только счётчик сильных ссылок вовлечённых значений будет равен 0.
Поскольку значение, на которое ссылается 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
выглядит так же, как при создании узла 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. Вы даже узнаете о нескольких новых умных указателях.