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

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

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

Язык программирования Rust

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

Создание ссылочного зацикливания

Предотвращение ссылочной зацикленности: замена умного указателя Rc<T> на Weak<T>

Создание древовидной структуры данных: Node с дочерними узлами

Добавление ссылки от ребёнка к его родителю

Визуализация изменений в strong_count и weak_count

Итоги

Предотвращение ссылочной зацикленности: замена умного указателя `Rc<T>` на `Weak<T>`

Создание древовидной структуры данных: `Node` с дочерними узлами

Визуализация изменений в `strong_count` и `weak_count`