We know that rust ownership has three principles:
- For each value, there is an owner.
- A value can only have one owner at a time.
- When the owner leaves the scope, the corresponding value is automatically dropped.
But sometimes a value is shared by multiple variables. Also it cannot be solved by reference, because there is no way to determine which variable ended up last and there is no way to determine the lifecycle. So this is where the Rc reference count smart pointer comes in handy, Rc shares ownership and adds one for each reference, and subtracts one when it leaves scope, and executes a destructor when the reference count is 0.
Rc is not thread-safe, cross-threaded, you need to use Arc, where A is the atomic atom.
View reference count
1
2
3
4
5
6
7
8
9
10
11
12
13
14
|
use std::rc::Rc;
fn main() {
let a = Rc::new(String::from("https://mytechshares.com/"));
println!("ref count is {}", Rc::strong_count(&a));
let b = Rc::clone(&a);
println!("ref count is {}", Rc::strong_count(&a));
{
let c = Rc::clone(&a);
println!("ref count is {}", Rc::strong_count(&a));
println!("ref count is {}", Rc::strong_count(&c));
}
println!("ref count is {}", Rc::strong_count(&a));
}
|
strong_count checks the reference count, the variable c is in inner lexical scope and prints the reference count before leaving the scope.
1
2
3
4
5
6
7
|
Finished dev [unoptimized + debuginfo] target(s) in 0.03s
Running `target/debug/hello_cargo`
ref count is 1
ref count is 2
ref count is 3
ref count is 3
ref count is 2
|
Each time a reference is added, the count is added by one. In the inner statement block, the count is 3, but when left, the count is reduced to 2.
Circular references
Anyone familiar with Garbage Collection knows that there are GC algorithms that rely on reference counting, such as the python implementation. For example, the Redis object is also implemented with rc. Since redis rc is not exposed to the user, as long as you pay attention to the direction of the reference when writing code, you won’t write circular references, but rust Rc is unavoidable.
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
|
use std::rc::Rc;
use std::cell::RefCell;
struct Node {
next: Option<Rc<RefCell<Node>>>,
}
impl Drop for Node {
fn drop(&mut self) {
println!("Dropping https://mytechshares.com 董泽润的技术笔记");
}
}
fn main() {
let first = Rc::new(RefCell::new(Node {next: None}));
let second = Rc::new(RefCell::new(Node {next: None}));
let third = Rc::new(RefCell::new(Node {next: None}));
(*first).borrow_mut().next = Some(Rc::clone(&second));
(*second).borrow_mut().next = Some(Rc::clone(&third));
(*third).borrow_mut().next = Some(Rc::clone(&first));
}
|
This is a representative of a circular chain table, a little bit around, the principle is first -> second -> third, while third -> first, the code runs, and does not print Dropping https://mytechshares.com 董泽润的技术笔记
The RefCell , borrow_mut are a bit hard to understand, I just learned rust when it has been difficult to understand. The next article will explain in detail. Simply put, RefCell , Cell provides a mechanism called internal mutability, because Rc shares the ownership of variables, so it requires that only reads and no modifications are allowed. Then the value inside Rc wraps around a layer of RefCell , Cell to avoid compiler checks and turn it into a runtime check, which is equivalent to opening a back door . This design pattern is used a lot in Rust.
So how do you fix this circular reference? The answer is the Weak pointer, which only increases the reference logic and does not share ownership, i.e. it does not increase the strong reference count.
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
|
use std::rc::Rc;
use std::rc::Weak;
use std::cell::RefCell;
struct Node {
next: Option<Rc<RefCell<Node>>>,
head: Option<Weak<RefCell<Node>>>,
}
impl Drop for Node {
fn drop(&mut self) {
println!("Dropping https://mytechshares.com 董泽润的技术笔记");
}
}
fn main() {
let first = Rc::new(RefCell::new(Node {next: None, head: None}));
let second = Rc::new(RefCell::new(Node {next: None, head: None}));
let third = Rc::new(RefCell::new(Node {next: None, head: None}));
(*first).borrow_mut().next = Some(Rc::clone(&second));
(*second).borrow_mut().next = Some(Rc::clone(&third));
(*third).borrow_mut().head = Some(Rc::downgrade(&first));
}
|
This is the fixed code, adding a head field, a pointer of type Weak, and generating a weak reference to first via Rc::downgrade.
1
2
3
4
5
6
7
|
# cargo run
Compiling hello_cargo v0.1.0 (/root/zerun.dong/code/rusttest/hello_cargo)
Finished dev [unoptimized + debuginfo] target(s) in 2.63s
Running `target/debug/hello_cargo`
Dropping https://mytechshares.com 董泽润的技术笔记
Dropping https://mytechshares.com 董泽润的技术笔记
Dropping https://mytechshares.com 董泽润的技术笔记
|
After running, we see that the Dropping message is printed three times, as expected. Also, since the object pointed to by the Weak pointer may be destructured, you can’t dereference it directly, you have to pattern match and then upgrade.
Thread-safe Arc
Let’s look at an example of concurrent variable modification, from the rust book official website.
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
|
use std::sync::{Arc, Mutex};
use std::thread;
fn main() {
let counter = Arc::new(Mutex::new(0));
let mut handles = vec![];
for _ in 0..10 {
let counter = Arc::clone(&counter);
let handle = thread::spawn(move || {
let mut num = counter.lock().unwrap();
*num += 1;
});
handles.push(handle);
}
for handle in handles {
handle.join().unwrap();
}
println!("董泽润的技术笔记 Got Result: {}", *counter.lock().unwrap());
}
|
spawn opens 10 threads, concurrently adds one to counter, and prints it after the final run.
1
2
3
4
5
|
# cargo run
Compiling hello_cargo v0.1.0 (/root/zerun.dong/code/rusttest/hello_cargo)
Finished dev [unoptimized + debuginfo] target(s) in 3.72s
Running `target/debug/hello_cargo`
董泽润的技术笔记 Got Result: 10
|
When I first learned it was really hard to understand, even concurrently modify variables are so troublesome, all kinds of Arc set Mutex , in fact, this is to achieve zero-cost runtime security, someone always have to do the GC side of the work.
And all kinds of wrapper does not prevent reading the source code, just ignore it and focus on the code logic, only when writing need to think carefully.
Underlying implementation
1
2
3
4
5
6
7
8
9
10
11
12
|
#[stable(feature = "rust1", since = "1.0.0")]
pub struct Rc<T: ?Sized> {
ptr: NonNull<RcBox<T>>,
phantom: PhantomData<RcBox<T>>,
}
#[repr(C)]
struct RcBox<T: ?Sized> {
strong: Cell<usize>,
weak: Cell<usize>,
value: T,
}
|
Rc is a structure, two fields ptr , phantom members are RcBox type, note that there are strong , weak count fields and real data value fields, see again the Cell to achieve the internal variable
PhantomData is a ghost data type, refer to nomicon documentation, the general scenario is.
When writing non-safe code, we often encounter situations where a type or lifecycle is logically associated with a structure, but is not a member of any of its members. This is particularly common for lifecycles.
PhantomData does not consume storage space, it just simulates some type of data for static analysis. Doing so is less error-prone than explicitly telling the type system what variability you need, and also provides the information needed for drop checking.
1
2
3
4
5
|
Zero-sized type used to mark things that "act like" they own a `T`.
Adding a `PhantomData<T>` field to your type tells the compiler that your
type acts as though it stores a value of type `T`, even though it doesn't
really. This information is used when computing certain safety properties.
|
Simply put, PhantomData is a zero-length placeholder that tells the compiler that it looks like I own the T, but it doesn’t belong to me, and also calls drop to release the T if it is destructured. Because of the phantom field, Rc does not own RcBox, NonNull tells the compiler that the pointer ptr must not be null and you can optimize it, and Option<Rc<T>> occupies the same size as Rc<T>, removing the flag field for whether it is null or not.
1
2
3
4
5
6
7
8
9
|
pub fn new(value: T) -> Rc<T> {
// There is an implicit weak pointer owned by all the strong
// pointers, which ensures that the weak destructor never frees
// the allocation while the strong destructor is running, even
// if the weak pointer is stored inside the strong one.
Self::from_inner(
Box::leak(box RcBox { strong: Cell::new(1), weak: Cell::new(1), value }).into(),
)
}
|
From the initialization Rc::new code, we see that the initial strong, weak count is 1.
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
|
#[stable(feature = "rust1", since = "1.0.0")]
impl<T: ?Sized> Clone for Rc<T> {
#[inline]
fn clone(&self) -> Rc<T> {
self.inner().inc_strong();
Self::from_inner(self.ptr)
}
}
impl<T: ?Sized> Rc<T> {
#[inline(always)]
fn inner(&self) -> &RcBox<T> {
// This unsafety is ok because while this Rc is alive we're guaranteed
// that the inner pointer is valid.
unsafe { self.ptr.as_ref() }
}
}
fn inc_strong(&self) {
let strong = self.strong();
// We want to abort on overflow instead of dropping the value.
// The reference count will never be zero when this is called;
// nevertheless, we insert an abort here to hint LLVM at
// an otherwise missed optimization.
if strong == 0 || strong == usize::MAX {
abort();
}
self.strong_ref().set(strong + 1);
}
|
Rc::clone does not copy the data, it only increases the strong ref count.
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
|
#[stable(feature = "rust1", since = "1.0.0")]
unsafe impl<#[may_dangle] T: ?Sized> Drop for Rc<T> {
fn drop(&mut self) {
unsafe {
self.inner().dec_strong();
if self.inner().strong() == 0 {
// destroy the contained object
ptr::drop_in_place(Self::get_mut_unchecked(self));
// remove the implicit "strong weak" pointer now that we've
// destroyed the contents.
self.inner().dec_weak();
if self.inner().weak() == 0 {
Global.deallocate(self.ptr.cast(), Layout::for_value(self.ptr.as_ref()));
}
}
}
}
}
|
You can see that drop first does a count minus one operation, and if the strong ref count reaches 0, it starts to destruct and release the object. At the same time, if the weak ref count reaches 0, RcBox is released, which means that RcBox and Value T are released separately.
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
|
pub struct Arc<T: ?Sized> {
ptr: NonNull<ArcInner<T>>,
phantom: PhantomData<ArcInner<T>>,
}
struct ArcInner<T: ?Sized> {
strong: atomic::AtomicUsize,
// the value usize::MAX acts as a sentinel for temporarily "locking" the
// ability to upgrade weak pointers or downgrade strong ones; this is used
// to avoid races in `make_mut` and `get_mut`.
weak: atomic::AtomicUsize,
data: T,
}
|
And the count inside Arc is guaranteed atomic with atomic, so it is concurrent word full.
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
|
#[stable(feature = "rc_weak", since = "1.4.0")]
pub struct Weak<T: ?Sized> {
// This is a `NonNull` to allow optimizing the size of this type in enums,
// but it is not necessarily a valid pointer.
// `Weak::new` sets this to `usize::MAX` so that it doesn’t need
// to allocate space on the heap. That's not a value a real pointer
// will ever have because RcBox has alignment at least 2.
// This is only possible when `T: Sized`; unsized `T` never dangle.
ptr: NonNull<RcBox<T>>,
}
#[stable(feature = "rc_weak", since = "1.4.0")]
pub fn downgrade(this: &Self) -> Weak<T> {
this.inner().inc_weak();
// Make sure we do not create a dangling Weak
debug_assert!(!is_dangling(this.ptr.as_ptr()));
Weak { ptr: this.ptr }
}s
|
Rc::downgrade generate Weak logic is also relatively simple, inc_weak add weak ref count weak reference count, and then return Weak.
There are many source implementations, it is a little difficult to understand, more google check, and then read the comments, interested in their own view.