Ссылочные зацикливания могут приводить к утечке памяти

Гарантии безопасности памяти в 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. Вы даже узнаете о нескольких новых умных указателях.

The Rust Programming Language