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

Циклические ссылки могут приводить к утечке памяти

Гарантии безопасности памяти в 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() {}

Мы используем ещё один вариант определения 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));

    // 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>, содержащий другое значение 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 владели своим списком, поэтому реорганизация структуры данных невозможна. Давайте посмотрим на пример с графами, состоящими из родительских и дочерних узлов, чтобы увидеть, когда отношения без владения являются подходящим способом предотвращения циклических ссылок.

Предотвращение циклических ссылок с использованием 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 с дочерними узлами

Сначала мы построим дерево с узлами, которые знают о своих дочерних узлах. Мы создадим структуру с именем 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)]),
    });
}

Мы клонируем 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 выглядит похоже на Листинг 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),
    );
}

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