Циклы ссылок могут приводить к утечке памяти
Гарантии безопасности памяти 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() {}
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!, чтобы показать, какими
являются счётчики ссылок в различных точках этого процесса.
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));
// Раскомментируйте следующую строку, чтобы увидеть, что у нас цикл;
// он приведёт к переполнению стека.
// println!("a next item = {:?}", a.tail());
}
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, b указывает на a, и так далее, пока не
переполнится стек.
По сравнению с реальной программой последствия создания цикла ссылок в этом примере не очень серьёзны: сразу после создания цикла ссылок программа завершается. Однако если более сложная программа выделила много памяти в цикле и удерживала её в течение длительного времени, программа использовала бы больше памяти, чем нужно, и могла бы перегрузить систему, вызвав нехватку доступной памяти.
Создание циклов ссылок не делается легко, но и не невозможно.
Если у вас есть значения RefCell<T>, содержащие значения Rc<T> или подобные вложенные
комбинации типов с внутренней изменяемостью и подсчётом ссылок, вы должны
убедиться, что не создаёте циклы; вы не можете полагаться на то, что Rust их поймает.
Создание цикла ссылок было бы логической ошибкой в вашей программе, которую следует
минимизировать с помощью автоматических тестов, обзоров кода и других практик разработки программного обеспечения.
Другое решение для избежания циклов ссылок — реорганизовать ваши структуры
данных так, чтобы некоторые ссылки выражали владение, а некоторые — нет.
В результате вы можете иметь циклы, состоящие из некоторых отношений владения и
некоторых отношений без владения, и только отношения владения влияют на
то, может ли значение быть освобождено. В листинге 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:
Имя файла: 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.
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)]),
});
}
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.
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 со слабой ссылкой на его родительский узел 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.
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),
);
}
branch во внутренней области видимости и изучение счётчиков сильных и слабых ссылокПосле создания 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. Вы даже узнаете о нескольких новых умных указателях.