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

ch15-06-reference-cycles.md
commit bd27a8b72336610c9a200f0ca932ffc8b6fb5ee1

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

制造引用循環(huán)

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

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

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

在示例 15-26 中增加了一個(gè) main 函數(shù)，其使用了示例 15-25 中的定義。這些代碼在 a 中創(chuàng)建了一個(gè)列表，一個(gè)指向 a 中列表的 b 列表，接著修改 a 中的列表指向 b 中的列表，這會(huì)創(chuàng)建一個(gè)引用循環(huán)。在這個(gè)過(guò)程的多個(gè)位置有 println! 語(yǔ)句展示引用計(jì)數(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)建一個(gè)引用循環(huán)：兩個(gè) List 值互相指向彼此

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

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

如果保持最后的 println! 行注釋并運(yùn)行代碼，會(huì)得到如下輸出：

$ 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í)例的引用計(jì)數(shù)都是 2。在 main 的結(jié)尾，Rust 丟棄 b，這會(huì) b Rc<List> 實(shí)例的引用計(jì)數(shù)從 2 減為 1。然而，b Rc<List> 不能被回收，因?yàn)槠湟糜?jì)數(shù)是 1 而不是 0。接下來(lái) Rust 會(huì)丟棄 a 將 a Rc<List> 實(shí)例的引用計(jì)數(shù)從 2 減為 1。這個(gè)實(shí)例也不能被回收，因?yàn)?nbsp;b Rc<List> 實(shí)例依然引用它，所以其引用計(jì)數(shù)是 1。這些列表的內(nèi)存將永遠(yuǎn)保持未被回收的狀態(tài)。為了更形象的展示，我們創(chuàng)建了一個(gè)如圖 15-4 所示的引用循環(huán)：

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

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

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

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

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

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

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

強(qiáng)引用代表如何共享 Rc<T> 實(shí)例的所有權(quán)，但弱引用并不屬于所有權(quán)關(guān)系。他們不會(huì)造成引用循環(huán)，因?yàn)槿魏稳跻玫难h(huán)會(huì)在其相關(guān)的強(qiáng)引用計(jì)數(shù)為 0 時(shí)被打斷。

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

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

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

在最開(kāi)始，我們將會(huì)構(gòu)建一個(gè)帶有子節(jié)點(diǎn)的樹(shù)。讓我們創(chuàng)建一個(gè)用于存放其擁有所有權(quán)的 i32 值和其子節(jié)點(diǎn)引用的 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é)點(diǎn)，同時(shí)也希望通過(guò)變量來(lái)共享所有權(quán)，以便可以直接訪問(wèn)樹(shù)中的每一個(gè) Node，為此 Vec<T> 的項(xiàng)的類型被定義為 Rc<Node>。我們還希望能修改其他節(jié)點(diǎn)的子節(jié)點(diǎn)，所以 children 中 Vec<Rc<Node>> 被放進(jìn)了 RefCell<T>。

接下來(lái)，使用此結(jié)構(gòu)體定義來(lái)創(chuàng)建一個(gè)叫做 leaf 的帶有值 3 且沒(méi)有子節(jié)點(diǎn)的 Node 實(shí)例，和另一個(gè)帶有值 5 并以 leaf 作為子節(jié)點(diǎn)的實(shí)例 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)建沒(méi)有子節(jié)點(diǎn)的 leaf 節(jié)點(diǎn)和以 leaf 作為子節(jié)點(diǎn)的 branch 節(jié)點(diǎn)

這里克隆了 leaf 中的 Rc<Node> 并儲(chǔ)存在了 branch 中，這意味著 leaf 中的 Node 現(xiàn)在有兩個(gè)所有者：leaf和branch?？梢酝ㄟ^(guò) branch.children 從 branch 中獲得 leaf，不過(guò)無(wú)法從 leaf 到 branch。leaf 沒(méi)有到 branch 的引用且并不知道他們相互關(guān)聯(lián)。我們希望 leaf 知道 branch 是其父節(jié)點(diǎn)。稍后我們會(huì)這么做。

增加從子到父的引用

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

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

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

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

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

文件名: 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：一個(gè) leaf 節(jié)點(diǎn)，其擁有指向其父節(jié)點(diǎn) branch 的 Weak 引用

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

此時(shí)，當(dāng)嘗試使用 upgrade 方法獲取 leaf 的父節(jié)點(diǎn)引用時(shí)，會(huì)得到一個(gè) None 值。如第一個(gè) println! 輸出所示：

leaf parent = None

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

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

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

可視化 strong_count 和 weak_count 的改變

讓我們通過(guò)創(chuàng)建了一個(gè)新的內(nèi)部作用域并將 branch 的創(chuàng)建放入其中，來(lái)觀察 Rc<Node> 實(shí)例的 strong_count 和 weak_count 值的變化。這會(huì)展示當(dāng) branch 創(chuàng)建和離開(kāi)作用域被丟棄時(shí)會(huì)發(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 并檢查其強(qiáng)弱引用計(jì)數(shù)

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

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

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

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

總結(jié)

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

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

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

接下來(lái)，讓我們談?wù)?Rust 的并發(fā)。屆時(shí)甚至還會(huì)學(xué)習(xí)到一些新的對(duì)并發(fā)有幫助的智能指針。