Keyboard shortcuts

Press ← or → to navigate between chapters

Press S or / to search in the book

Press ? to show this help

Press Esc to hide this help

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

Гарантии безопасности памяти Rust затрудняют, но не делают невозможным случайное создание памяти, которая никогда не будет очищена (это известно как утечка памяти). Полное предотвращение утечек памяти не входит в гарантии Rust, а значит, утечки памяти в Rust безопасны с точки зрения памяти. Мы можем увидеть, что Rust допускает утечки памяти, используя Rc<T> и RefCell<T>: можно создать ссылки, в которых элементы ссылаются друг на друга по циклу. Это создает утечки памяти, потому что счетчик ссылок каждого элемента в цикле никогда не достигнет 0, и значения никогда не будут удалены.

Создание цикла ссылок

Посмотрим, как может возникнуть цикл ссылок и как его предотвратить, начав с определения enum 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() {}
Listing 15-25: Определение cons-списка, который хранит 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());
}
Listing 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.

Прямоугольник с меткой 'a' указывает на прямоугольник, содержащий целое число 5. Прямоугольник с меткой 'b' указывает на прямоугольник, содержащий целое число 10. Прямоугольник, содержащий 5, указывает на прямоугольник, содержащий 10, а прямоугольник, содержащий 10, указывает обратно на прямоугольник, содержащий 5, создавая цикл.

Рисунок 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>. Мы также хотим изменять, какие узлы являются дочерними для другого узла, поэтому в children у нас есть RefCell<T>, оборачивающий 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)]),
    });
}
Listing 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());
}
Listing 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),
    );
}
Listing 15-29: Создание 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. Указав в определении Node, что отношение от дочернего узла к родителю должно быть ссылкой Weak<T>, вы можете позволить родительским узлам указывать на дочерние узлы и наоборот, не создавая цикла ссылок и утечек памяти.

Итоги

В этой главе мы рассмотрели, как использовать умные указатели, чтобы получать другие гарантии и компромиссы по сравнению с теми, которые Rust по умолчанию дает с обычными ссылками. Тип Box<T> имеет известный размер и указывает на данные, выделенные в куче. Тип Rc<T> отслеживает количество ссылок на данные в куче, чтобы у данных могло быть несколько владельцев. Тип RefCell<T> с его внутренней изменяемостью дает нам тип, который можно использовать, когда нам нужен неизменяемый тип, но нужно изменить внутреннее значение этого типа; он также проверяет правила заимствования во время выполнения, а не во время компиляции.

Мы также обсудили трейты Deref и Drop, которые обеспечивают значительную часть функциональности умных указателей. Мы изучили циклы ссылок, которые могут вызывать утечки памяти, и способы предотвращать их с помощью Weak<T>.

Если эта глава пробудила ваш интерес и вы хотите реализовать собственные умные указатели, загляните в «The Rustonomicon», где есть больше полезной информации.

Далее мы поговорим о конкурентности в Rust. Вы даже узнаете о нескольких новых умных указателях.