Rust 引用循環(huán)會導致內(nèi)存泄漏

ch15-06-reference-cycles.md
commit bd27a8b72336610c9a200f0ca932ffc8b6fb5ee1

Rust 的內(nèi)存安全性保證使其難以意外地制造永遠也不會被清理的內(nèi)存（被稱為 內(nèi)存泄漏（memory leak）），但并不是不可能。與在編譯時拒絕數(shù)據(jù)競爭不同， Rust 并不保證完全地避免內(nèi)存泄漏，這意味著內(nèi)存泄漏在 Rust 被認為是內(nèi)存安全的。這一點可以通過 Rc<T> 和 RefCell<T> 看出：創(chuàng)建引用循環(huán)的可能性是存在的。這會造成內(nèi)存泄漏，因為每一項的引用計數(shù)永遠也到不了 0，其值也永遠不會被丟棄。

制造引用循環(huán)

讓我們看看引用循環(huán)是如何發(fā)生的以及如何避免它。以示例 15-25 中的 List 枚舉和 tail 方法的定義開始：

文件名: 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: 一個存放 RefCell 的 cons list 定義，這樣可以修改 Cons 成員所引用的數(shù)據(jù)

這里采用了示例 15-25 中 List 定義的另一種變體?，F(xiàn)在 Cons 成員的第二個元素是 RefCell<Rc<List>>，這意味著不同于像示例 15-24 那樣能夠修改 i32 的值，我們希望能夠修改 Cons 成員所指向的 List。這里還增加了一個 tail 方法來方便我們在有 Cons 成員的時候訪問其第二項。

在示例 15-26 中增加了一個 main 函數(shù)，其使用了示例 15-25 中的定義。這些代碼在 a 中創(chuàng)建了一個列表，一個指向 a 中列表的 b 列表，接著修改 a 中的列表指向 b 中的列表，這會創(chuàng)建一個引用循環(huán)。在這個過程的多個位置有 println! 語句展示引用計數(shù)。

文件: src/main.rs

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：創(chuàng)建一個引用循環(huán)：兩個 List 值互相指向彼此

這里在變量 a 中創(chuàng)建了一個 Rc<List> 實例來存放初值為 5, Nil 的 List 值。接著在變量 b 中創(chuàng)建了存放包含值 10 和指向列表 a 的 List 的另一個 Rc<List> 實例。

最后，修改 a 使其指向 b 而不是 Nil，這就創(chuàng)建了一個循環(huán)。為此需要使用 tail 方法獲取 a 中 RefCell<Rc<List>> 的引用，并放入變量 link 中。接著使用 RefCell<Rc<List>> 的 borrow_mut 方法將其值從存放 Nil 的 Rc<List> 修改為 b 中的 Rc<List>。

如果保持最后的 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

可以看到將列表 a 修改為指向 b 之后， a 和 b 中的 Rc<List> 實例的引用計數(shù)都是 2。在 main 的結(jié)尾，Rust 丟棄 b，這會 b Rc<List> 實例的引用計數(shù)從 2 減為 1。然而，b Rc<List> 不能被回收，因為其引用計數(shù)是 1 而不是 0。接下來 Rust 會丟棄 a 將 a Rc<List> 實例的引用計數(shù)從 2 減為 1。這個實例也不能被回收，因為 b Rc<List> 實例依然引用它，所以其引用計數(shù)是 1。這些列表的內(nèi)存將永遠保持未被回收的狀態(tài)。為了更形象的展示，我們創(chuàng)建了一個如圖 15-4 所示的引用循環(huán)：

圖 15-4: 列表 a 和 b 彼此互相指向形成引用循環(huán)

如果取消最后 println! 的注釋并運行程序，Rust 會嘗試打印出 a 指向 b 指向 a 這樣的循環(huán)直到棧溢出。

這個特定的例子中，創(chuàng)建了引用循環(huán)之后程序立刻就結(jié)束了。這個循環(huán)的結(jié)果并不可怕。如果在更為復雜的程序中并在循環(huán)里分配了很多內(nèi)存并占有很長時間，這個程序會使用多于它所需要的內(nèi)存，并有可能壓垮系統(tǒng)并造成沒有內(nèi)存可供使用。

創(chuàng)建引用循環(huán)并不容易，但也不是不可能。如果你有包含 Rc<T> 的 RefCell<T> 值或類似的嵌套結(jié)合了內(nèi)部可變性和引用計數(shù)的類型，請務必小心確保你沒有形成一個引用循環(huán)；你無法指望 Rust 幫你捕獲它們。創(chuàng)建引用循環(huán)是一個程序上的邏輯 bug，你應該使用自動化測試、代碼評審和其他軟件開發(fā)最佳實踐來使其最小化。

另一個解決方案是重新組織數(shù)據(jù)結(jié)構，使得一部分引用擁有所有權而另一部分沒有。換句話說，循環(huán)將由一些擁有所有權的關系和一些無所有權的關系組成，只有所有權關系才能影響值是否可以被丟棄。在示例 15-25 中，我們總是希望 Cons 成員擁有其列表，所以重新組織數(shù)據(jù)結(jié)構是不可能的。讓我們看看一個由父節(jié)點和子節(jié)點構成的圖的例子，觀察何時是使用無所有權的關系來避免引用循環(huán)的合適時機。

避免引用循環(huán)：將 Rc<T> 變?yōu)?nbsp;Weak<T>

到目前為止，我們已經(jīng)展示了調(diào)用 Rc::clone 會增加 Rc<T> 實例的 strong_count，和只在其 strong_count 為 0 時才會被清理的 Rc<T> 實例。你也可以通過調(diào)用 Rc::downgrade 并傳遞 Rc<T> 實例的引用來創(chuàng)建其值的 弱引用（weak reference）。調(diào)用 Rc::downgrade 時會得到 Weak<T> 類型的智能指針。不同于將 Rc<T> 實例的 strong_count 加 1，調(diào)用 Rc::downgrade 會將 weak_count 加 1。Rc<T> 類型使用 weak_count 來記錄其存在多少個 Weak<T> 引用，類似于 strong_count。其區(qū)別在于 weak_count 無需計數(shù)為 0 就能使 Rc<T> 實例被清理。

強引用代表如何共享 Rc<T> 實例的所有權，但弱引用并不屬于所有權關系。他們不會造成引用循環(huán)，因為任何弱引用的循環(huán)會在其相關的強引用計數(shù)為 0 時被打斷。

因為 Weak<T> 引用的值可能已經(jīng)被丟棄了，為了使用 Weak<T> 所指向的值，我們必須確保其值仍然有效。為此可以調(diào)用 Weak<T> 實例的 upgrade 方法，這會返回 Option<Rc<T>>。如果 Rc<T> 值還未被丟棄，則結(jié)果是 Some；如果 Rc<T> 已被丟棄，則結(jié)果是 None。因為 upgrade 返回一個 Option<Rc<T>>，Rust 會確保處理 Some 和 None 的情況，所以它不會返回非法指針。

我們會創(chuàng)建一個某項知道其子項和父項的樹形結(jié)構的例子，而不是只知道其下一項的列表。

創(chuàng)建樹形數(shù)據(jù)結(jié)構：帶有子節(jié)點的 Node

在最開始，我們將會構建一個帶有子節(jié)點的樹。讓我們創(chuàng)建一個用于存放其擁有所有權的 i32 值和其子節(jié)點引用的 Node：

文件名: src/main.rs

use std::cell::RefCell;
use std::rc::Rc;

#[derive(Debug)]
struct Node {
    value: i32,
    children: RefCell<Vec<Rc<Node>>>,
}

我們希望能夠 Node 擁有其子節(jié)點，同時也希望通過變量來共享所有權，以便可以直接訪問樹中的每一個 Node，為此 Vec<T> 的項的類型被定義為 Rc<Node>。我們還希望能修改其他節(jié)點的子節(jié)點，所以 children 中 Vec<Rc<Node>> 被放進了 RefCell<T>。

接下來，使用此結(jié)構體定義來創(chuàng)建一個叫做 leaf 的帶有值 3 且沒有子節(jié)點的 Node 實例，和另一個帶有值 5 并以 leaf 作為子節(jié)點的實例 branch，如示例 15-27 所示：

文件名: src/main.rs

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：創(chuàng)建沒有子節(jié)點的 leaf 節(jié)點和以 leaf 作為子節(jié)點的 branch 節(jié)點

這里克隆了 leaf 中的 Rc<Node> 并儲存在了 branch 中，這意味著 leaf 中的 Node 現(xiàn)在有兩個所有者：leaf和branch。可以通過 branch.children 從 branch 中獲得 leaf，不過無法從 leaf 到 branch。leaf 沒有到 branch 的引用且并不知道他們相互關聯(lián)。我們希望 leaf 知道 branch 是其父節(jié)點。稍后我們會這么做。

增加從子到父的引用

為了使子節(jié)點知道其父節(jié)點，需要在 Node 結(jié)構體定義中增加一個 parent 字段。問題是 parent 的類型應該是什么。我們知道其不能包含 Rc<T>，因為這樣 leaf.parent 將會指向 branch 而 branch.children 會包含 leaf 的指針，這會形成引用循環(huán)，會造成其 strong_count 永遠也不會為 0。

現(xiàn)在換一種方式思考這個關系，父節(jié)點應該擁有其子節(jié)點：如果父節(jié)點被丟棄了，其子節(jié)點也應該被丟棄。然而子節(jié)點不應該擁有其父節(jié)點：如果丟棄子節(jié)點，其父節(jié)點應該依然存在。這正是弱引用的例子！

所以 parent 使用 Weak<T> 類型而不是 Rc<T>，具體來說是 RefCell<Weak<Node>>?，F(xiàn)在 Node 結(jié)構體定義看起來像這樣：

文件名: 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>>>,
}

這樣，一個節(jié)點就能夠引用其父節(jié)點，但不擁有其父節(jié)點。在示例 15-28 中，我們更新 main 來使用新定義以便 leaf 節(jié)點可以通過 branch 引用其父節(jié)點：

文件名: src/main.rs

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 節(jié)點，其擁有指向其父節(jié)點 branch 的 Weak 引用

創(chuàng)建 leaf 節(jié)點類似于示例 15-27 中如何創(chuàng)建 leaf 節(jié)點的，除了 parent 字段有所不同：leaf 開始時沒有父節(jié)點，所以我們新建了一個空的 Weak 引用實例。

此時，當嘗試使用 upgrade 方法獲取 leaf 的父節(jié)點引用時，會得到一個 None 值。如第一個 println! 輸出所示：

leaf parent = None

當創(chuàng)建 branch 節(jié)點時，其也會新建一個 Weak<Node> 引用，因為 branch 并沒有父節(jié)點。leaf 仍然作為 branch 的一個子節(jié)點。一旦在 branch 中有了 Node 實例，就可以修改 leaf 使其擁有指向父節(jié)點的 Weak<Node> 引用。這里使用了 leaf 中 parent 字段里的 RefCell<Weak<Node>> 的 borrow_mut 方法，接著使用了 Rc::downgrade 函數(shù)來從 branch 中的 Rc<Node> 值創(chuàng)建了一個指向 branch 的 Weak<Node> 引用。

當再次打印出 leaf 的父節(jié)點時，這一次將會得到存放了 branch 的 Some 值：現(xiàn)在 leaf 可以訪問其父節(jié)點了！當打印出 leaf 時，我們也避免了如示例 15-26 中最終會導致棧溢出的循環(huán)：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: [] } }] } })

沒有無限的輸出表明這段代碼并沒有造成引用循環(huán)。這一點也可以從觀察 Rc::strong_count 和 Rc::weak_count 調(diào)用的結(jié)果看出。

可視化 strong_count 和 weak_count 的改變

讓我們通過創(chuàng)建了一個新的內(nèi)部作用域并將 branch 的創(chuàng)建放入其中，來觀察 Rc<Node> 實例的 strong_count 和 weak_count 值的變化。這會展示當 branch 創(chuàng)建和離開作用域被丟棄時會發(fā)生什么。這些修改如示例 15-29 所示：

文件名: src/main.rs

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：在內(nèi)部作用域創(chuàng)建 branch 并檢查其強弱引用計數(shù)

一旦創(chuàng)建了 leaf，其 Rc<Node> 的強引用計數(shù)為 1，弱引用計數(shù)為 0。在內(nèi)部作用域中創(chuàng)建了 branch 并與 leaf 相關聯(lián)，此時 branch 中 Rc<Node> 的強引用計數(shù)為 1，弱引用計數(shù)為 1（因為 leaf.parent 通過 Weak<Node> 指向 branch）。這里 leaf 的強引用計數(shù)為 2，因為現(xiàn)在 branch 的 branch.children 中儲存了 leaf 的 Rc<Node> 的拷貝，不過弱引用計數(shù)仍然為 0。

當內(nèi)部作用域結(jié)束時，branch 離開作用域，Rc<Node> 的強引用計數(shù)減少為 0，所以其 Node 被丟棄。來自 leaf.parent 的弱引用計數(shù) 1 與 Node 是否被丟棄無關，所以并沒有產(chǎn)生任何內(nèi)存泄漏！

如果在內(nèi)部作用域結(jié)束后嘗試訪問 leaf 的父節(jié)點，會再次得到 None。在程序的結(jié)尾，leaf 中 Rc<Node> 的強引用計數(shù)為 1，弱引用計數(shù)為 0，因為現(xiàn)在 leaf 又是 Rc<Node> 唯一的引用了。

所有這些管理計數(shù)和值的邏輯都內(nèi)建于 Rc<T> 和 Weak<T> 以及它們的 Drop trait 實現(xiàn)中。通過在 Node 定義中指定從子節(jié)點到父節(jié)點的關系為一個Weak<T>引用，就能夠擁有父節(jié)點和子節(jié)點之間的雙向引用而不會造成引用循環(huán)和內(nèi)存泄漏。

總結(jié)

這一章涵蓋了如何使用智能指針來做出不同于 Rust 常規(guī)引用默認所提供的保證與取舍。Box<T> 有一個已知的大小并指向分配在堆上的數(shù)據(jù)。Rc<T> 記錄了堆上數(shù)據(jù)的引用數(shù)量以便可以擁有多個所有者。RefCell<T> 和其內(nèi)部可變性提供了一個可以用于當需要不可變類型但是需要改變其內(nèi)部值能力的類型，并在運行時而不是編譯時檢查借用規(guī)則。

我們還介紹了提供了很多智能指針功能的 trait Deref 和 Drop。同時探索了會造成內(nèi)存泄漏的引用循環(huán)，以及如何使用 Weak<T> 來避免它們。

如果本章內(nèi)容引起了你的興趣并希望現(xiàn)在就實現(xiàn)你自己的智能指針的話，請閱讀 “The Rustonomicon” 來獲取更多有用的信息。

接下來，讓我們談談 Rust 的并發(fā)。屆時甚至還會學習到一些新的對并發(fā)有幫助的智能指針。