Hazard pointers

[ghost]

Epoch-based memory reclamation is great, but it is not the right solution for all situations that require deferred memory reclamation in concurrent settings. We will probably need to implement hazard pointers to accommodate the rest.

Here are some of my thoughts on this matter. I don't have any concrete proposals yet - just want to lay everything out so we can share our notes and think this through. If you have any ideas, concerns, interesting use-cases for hazard pointers, or any other comments, please say so. :)

I'm particularly interested in hearing more about @jeehoonkang's wait-free queue. He has already prototyped garbage collection based on a combination of epochs and hazard pointers, so check that out.

Epoch-based reclamation vs hazard pointers

The fundamental difference between epoch-based reclamation (EBR) and hazard pointers (HP) is in how coarse or fine-grained object protection is. With EBR, we declare critical sections by pinning and saying "in this critical section, we might potentially access any object". With HP, however, each hazard pointer protects only a single object at a time. So even if we're accessing just one object for a long time, that will not prevent reclamation of other objects.

EBR has a (mostly theoretical?) danger of accumulating unbounded number of dead unreclaimed objects. E.g. this might happen if a pinned thread gets preempted by the OS for a very long time. On the other hand, with HP we usually have a bounded number of hazard pointers so only a bounded number of dead objects can be be kept unreclaimed.

Pinning a thread and protecting an object with a hazard pointer should be operations with comparable performance costs. They both perform a few atomic loads, atomic stores into thread-locals, and a full fence.

Traversing a linked data structure is almost certainly faster using EBR. For example, if we want to search for a particular node in a skiplist or binary search tree, we'll have to start from the root and make several steps through the data structures to find the node. EBR would incur a fixed cost at the beginning and at the end of the procedure, but HP would come with a performance penalty at each step of traversal.

The main advantage of HP is that hazard pointers can be kept alive for a very long time without worry of blocking memory reclamation globally. With EBR, we must make sure that threads are pinned only for very short periods of time. There is another advantage of HP - it supports eager memory reclamation, as will be demonstrated in the following section.

Eager garbage collection using HP

In crossbeam-deque, we have two structs: Deque (owned by a single thread) and Stealer (shared among multiple threads). A Chase-Lev deque contains a buffer that gets atomically replaced with a larger one when it gets full or a smaller one when its capacity is underused. But note that only operations on Deque (a single thread) can modify the pointer to the buffer.

The buffer is only occasionally replaced, and when it is, we want to destroy the old one as soon as possible (because it might be pretty large). Currently, we call guard.flush() just after replacing the buffer so that it gets moved into the global garbage queue immediately. We also periodically call collect() on every Nth call to epoch::pin() so that garbage collection is triggerred often enough. This is a hacky solution. We can do better.

Suppose that we used HP instead. The cost of pinning and protecting the buffer by a hazard pointer should be comparable because we don't traverse the data structure. In each operation, we only do a single load to acquire the buffer, that's it.

In order to defer destruction of an old buffer, instead of calling guard.defer(...) let's call
retire(old_buffer), which is implemented as:

fn retire(old: *mut Buffer<T>) {
    for haz in hazard::iter_all_hazard_pointers() {
        loop {
            // Is there sombeody still using the old buffer?
            if haz.load(Relaxed) == old {
                // Yes. Let's try setting this hazard pointer to null.
                if haz.compare_and_swap(old, ptr::null(), Relaxed) {
                    // Success! When the owner of `haz` stops using it, they will notice that `haz`
                    // is set to null and will take over the responsibility of retiring the old
                    // buffer. Then that thread will call `retire(old)` to try destroying the
                    // buffer again.
                    return;
                }
            } else {
                // No. Move on.
                break;
            }
        }
    }

    // Nobody is using the old buffer. We may destroy it immediately.
    unsafe { drop(Box::from_raw(old)); }
}

Note that this strategy makes destruction fully eager: the old buffer gets destroyed as soon as all threads stop using it, without any further delay. In fact, eager destruction with hazard pointers is not much different from eager destruction with Rc or Arc.

Long-lived pointers

Iterators over concurrent data structures don't work well with EBR because they can be long-lived,
while pinning must be very quick. In other words, EBR forces us to keep loaded pointers for very
short periods of time.

This is a problem for data structures like wait-free queues and skiplists. Hazard pointers are a very natural solution for long-lived pointers.

Here is an example of how we might iterate over a linked list using HP:

struct Node<T> {
    data: ManuallyDrop<T>,
    next: Atomic<Node<T>>,
}

struct List<T> {
    head: Atomic<Node<T>>,
}

impl<T> List<T> {
    fn count(&self) -> usize {
        // Register two new shields (in a way, they are similar to `epoch::Shared<T>`).
        let mut a = hazard::shield();
        let mut b = hazard::shield();

        let mut count = 0;

        self.head.load(SeqCst, &mut a);

        while !a.is_null() {
            // Load the next pointer into `b` and set `a` to null.
            a.unwrap().next.load(SeqCst, &mut b);
            a.release();

            // Swap `a` and `b` and continue iterating.
            mem::swap(&mut a, &mut b);
            count += 1;
        }

        count

        // `a` and `b` are dropped and get unregistered.
    }
}

Writing the same code using EBR would require us to pin the current thread for the entire duration of count, which might take an unacceptably long time for one pinning. Repinning during iteration (guard.repin()) is not possible because we can't let go of the pointer to the current node.

Hybrid GC: using both EBR and HP at the same time

Suppose we want to add a new operation called pop_head() to List<T>, but use EBR instead of HP. We might implement it as:

impl<T> List<T> {
    fn pop_head(&self) -> Option<T> {
        let guard = &epoch::pin();

        loop {
            let head = self.head.load(SeqCst, guard);
            if head.is_null() {
                return None;
            }

            let next = unsafe { head.deref().next.load(SeqCst, guard) };

            if self.head.compare_and_set(head, next, SeqCst, guard) {
                unsafe {
                    let data = ptr::read(&head.deref().data);

                    guard.defer(move || {
                        // Once EBR decides that `head` is unreachable, we must also make sure that
                        // there are no outstanding hazard pointers to it. We pass the garbage
                        // along to the HP-based GC.
                        //
                        // The first argument to `defer` is the actual pointer, and the second
                        // argument is the destructor.
                        hazard::defer(data.as_raw(), move || {
                            data.into_owned();
                        });
                    });

                    return Some(data);
                }
            }
        }
    }
}

Note that this way a dead object first goes through the epoch-based GC and then through the HP-based GC, where it is finally destroyed.

An interesting challenge with mixing EBR and HP is how to make APIs from crossbeam-epoch and crossbeam-hazard work well together. For example, how are we going to load a crossbeam_epoch::Atomic<T> into a crossbeam_hazard::Shield<T>? Is it going to be atomic.load(SeqCst, &shield)? Or maybe shield.protect(a.load(SeqCst, epoch::unprotected()))? I don't know...

Shield registration

A Shield<T> is a slot that holds a hazard pointer, shielding an object from destruction. (I'm actually using terms shield and hazard pointer interchangeably.) Each shield typically belongs to a specific thread (although it is always readable by all threads). In order to create a shield, we have to register it in some kind of global list so that other threads are aware of all currently existing shields.

We should allow registration of arbitrary number of shields. However, it must be noted that having a lot of registered shields will slow down garbage collection.

Sometimes it makes sense to cache registered shields in TLS to avoid the cost of shield registration on every operation. For example:

thread_local! {
    static A: Shield<u8> = hazard::shield();
    static B: Shield<u8> = hazard::shield();
}

impl<T> List<T> {
    fn count(&self) -> usize {
        A.with(|a| {
            B.with(|b| {
                // Ugly hack, but oh well.
                let a: &Shield<T> = unsafe { mem::transmute(a) };
                let b: &Shield<T> = unsafe { mem::transmute(b) };

                // ...
            })
        })
    }
}

That is some really ugly code, but you get the idea. :)

Previous work

Finally, it's worth looking into existing implementations of HP-based garbage collection. Here are a few examples I'm aware of:

• conc: http://ticki.github.io/blog/fearless-concurrency-with-hazard-pointers/
• libcds: https://kukuruku.co/post/lock-free-data-structures-the-inside-memory-management-schemes/
• comere: https://github.com/martinhath/comere/tree/master/src/hp
• C++ HP proposal: http://www.open-std.org/jtc1/sc22/wg21/docs/papers/2017/p0233r4.pdf

[martinhath]

Interesting! Especially the parts about mixing HP and EBR. I'm not too sure about the shield API as presented here, but this is certainly something we can play around with. I'd imagined a Ptr like struct, which registers and deregisters itself, or something. For what its worth, I've implemented a working version of HP in my semester project over here, although the code base is dubious at best (so don't judge! 😇).

Is something missing or misplaced in the code under "Eager garbage collection using HP"? That loop seems very ... loopy 😄

Also, I'm curious about where the "shield" name comes from (maybe this is a question for @jeehoonkang)?

[ghost]

I'm not too sure about the shield API as presented here, but this is certainly something we can play around with.

All the code I've written above is just heavy handwaving - definitely not an API we should settle with. :)

For what its worth, I've implemented a working version of HP in my semester project over here, although the code base is dubious at best (so don't judge! 😇).

Oh, nice! I'll take a look at the code and add it to the Previous work section.

Is something missing or misplaced in the code under "Eager garbage collection using HP"? That loop seems very ... loopy 😄

Oops, you're right! I've fixed the code now.

Also, I'm curious about where the "shield" name comes from

It's from the Project Snowflake paper. Shield should be equivalent to HazardPtr in comere, AFAICT.

[LionsAd]

Why not use QBSR instead in combination to say that you are finished with the objects for now?

The main critique of the paper that compared the performance of EBR, QBSR and HP (http://csng.cs.toronto.edu/publication_files/0000/0159/jpdc07.pdf) was that EBR is too fine grained, hence I think what you ended up implementing is what they call NEBR there.

However nothing is stopping you from saying, once all the shared objects are out of scope, set current epoch = global epoch. (e.g. the case when there are no more HP right now)

This is only a problem if you retrieve long-lived objects, which you do not copy from structures, but keep all the time.

Of course copying has some overhead (and best solution would be a copy-on-write like scheme), but the big problem with hazard pointers is that the memory used is potentially unbounded. (at least for data structures more complicated than lists)

---

Basically I described the same approach as used by DEBRA: https://arxiv.org/pdf/1712.01044.pdf

[ghost]

Why not use QBSR instead in combination to say that you are finished with the objects for now?

You can simulate QSBR with Guard::repin. See #18 for a discussion on this topic.

but the big problem with hazard pointers is that the memory used is potentially unbounded.

Sorry, I'm confused - did you perhaps mean QSBR or EBR instead of hazard pointers?

With hazard pointers, the amount of garbage can be made bounded. That's one of the main advantages of hazard pointers.

[mpoeter]

You might want to take a look at my Master's Thesis Effective Memory Reclamation for Lock-Free Data Structures in C++. It describes a large number of different reclamation schemes, and discusses C++ implementations of some of them (LFRC, EBR, NEBR, QSBR, Hazard Pointers and Stamp-it).

The implementation of the reclamation schemes is based on an adapted version of the interface proposed by Robison (the main architect of Intel TBB) for the C++ standard: Policy-based design for safe destruction in concurrent containers .

Based on the implementation for the thesis I have started development of a C++ library with additional reclamation schemes (DEBRA, Hazard Eras) and data structures: https://github.com/mpoeter/xenium

I am not very experienced with Rust, but I do think that the abstract interface I implemented for the reclamation scheme would be a good fit for Rust too.

[zaharidichev]

Just to get an idea of the state of things (as its been awhile). Is this something that is still actively considered as an addition to crossbeam ?