Shulou(Shulou.com)06/01 Report--

This article introduces what is the principle of unlocked garbage collection based on epoch in crossbeam-epoch. The content is very detailed. Interested friends can use it for reference. I hope it will be helpful to you.

Crossbeam provides an epoch-based garbage collection (epoch based reclamation) library. First of all, let's briefly talk about the principle of garbage collection.

The algorithm of garbage collection based on epoch is mainly involved in Keir Fraser's doctoral thesis. We have seen from the previous simple implementation of the unlocked concurrent stack that the container of the data structure in the concurrent environment (such as the node that contains the out-stack element) completes its mission in a thread and then prepares to be released. But there may be other threads holding their snapshots at this time (mainly for CAS purposes). However, no new thread will continue to take its snapshot. Then you can release the container with peace of mind as long as all the threads that take a snapshot of the container have completed the operation. This algorithm requires: a global epoch counter each thread has a local epoch counter, a global list to record whether each epoch generated garbage marking thread is active, the marker algorithm is like this: when a thread needs to operate on a data structure, it first sets its own identifier to active, and then updates the local epoch counter to the global epoch counter. If a thread needs to delete a node from the data structure, it will add that node to the current epoch garbage list. When the thread completes the operation on the data structure, the thread marks itself as inactive. Then, when garbage collection is needed, a thread will traverse all threads and check whether the epoch of all active threads is the same as the current global epoch. If so, the global epoch count will be + 1, and the garbage before 2 epoch can be collected. In fact, when in epoch No.2, since all threads that operate on data (active) are after epoch Number1, you can safely clean up the junk list of epoch N. Crossbeam-epoch 's APIGuard uses pin to generate Guard, which identifies the current thread as an active use crossbeam_epoch as epoch

Let guard = & epoch::pin (); defer_destroy puts the data into the garbage list, waits for two epoch before it can be cleaned up pub unsafe fn defer_destroy (& self, ptr: Shared), and then we'll see three big pointer types: Shared We just saw Shared in the function signature of defer_destroy, which is a pointer type protected by Guard's lifecycle'g, which is equivalent to & g T. It ensures that the data is accessible during the existence of the Guard. Owned, which is equivalent to Box, is an amount that will not be touched by other threads. Atomic this is an atomic pointer that can be exchanged between threads. Shared pub fn load (& self, ord: Ordering, &'g Guard)-> Shared Result > where O: CompareAndSetOrdering, P: Pointer can be read out under the protection of Guard. With these API, we can implement a lock-free MPMC Treiber stack. Use std::mem::ManuallyDrop;use std::ptr;use std::sync::atomic::Ordering:: {Acquire, Relaxed, Release}

Use crossbeam_epoch:: {self as epoch, Atomic, Owned}

# [derive (Debug)] pub struct TreiberStack {head: Atomic,}

# [derive (Debug)] struct Node {data: ManuallyDrop, / / tells the compiler that the variable does not require automatic Drop next: Atomic,}

Impl TreiberStack {pub fn new ()-> TreiberStack {TreiberStack {head: Atomic::null (),}}

Pub fn push (& self, t: t) {let mut n = Owned::new (Node {data: ManuallyDrop::new (t), next: Atomic::null (),})

Let guard = epoch::pin (); / / Mark the current thread as active

Loop {let head = self.head.load (Relaxed, & guard); n.next.store (head, Relaxed)

Match self.head.compare_and_set (head, n, Release, & guard) {/ / CAS Ok (_) = > break, Err (e) = > n = e.new,}

Pub fn pop (& self)-> Option {let guard = epoch::pin (); / / Mark the current thread as active loop {let head = self.head.load (Acquire, & guard)

Match unsafe {head.as_ref ()} {Some (h) = > {let next = h.next.load (Relaxed, & guard)

If self .head .floor _ and_set (head, next, Relaxed, & guard) / / CAS .is _ ok () {unsafe {guard.defer_destroy (head) / / add garbage to the list return Some (ManuallyDrop::into_inner (ptr::read (& (* h) .data)); / / return the data in the node} None = > return None,}

Pub fn is_empty (& self)-> bool {let guard = epoch::pin (); self.head.load (Acquire, & guard). Is_null ()}

Impl Drop for TreiberStack {fn drop (& mut self) {while self.pop (). Is_some () {}} about what is the principle of epoch-based unlocked garbage collection in crossbeam-epoch. I hope the above content can be helpful to you and learn more knowledge. If you think the article is good, you can share it for more people to see.

Welcome to subscribe "Shulou Technology Information " to get latest news, interesting things and hot topics in the IT industry, and controls the hottest and latest Internet news, technology news and IT industry trends.