I don't mean they're hard to implement, they're not easy either, but ok, I can confidently say it's not hard to implement your own Hazard Pointer class.
What I mean is that it is really hard to deploy hazard pointers in your own data structure or algorithm, and even harder if you have to do it in someone else's data structure.
Anybody who says that hazard pointers are easy is just saying bullsh1t or has no idea what they're talking about... unless it's Maged Michael saying it, then ok, I can believe it's easy for him because he invented the bloody thing :)
Let me (try to) justify why I say this:
When you deploy the Hazard Pointers (HP) technique in a data structure, there are several steps and questions that you need to answer. For example:
- What are the pointers that are shared between threads?
The more shared pointers (and objects) there are, the more hazard pointers you will need.
- Do we dereference all of these pointers?
Maybe some pointers are shared but we don't dereference them. Maybe we don't need an hazard pointer for those.
- Do we need to worry about ABA issues for the pointers that are not dereferenced?
If yes, then we need an hazard pointer to protect them anyhow.
- When does the lifetime of the local pointer ends?
When it's no longer needed we have to clear the corresponding entry of the array of hazard pointers to allow the object to be deleted.
- Which pointers go with which indexes?
Some pointers are never used at the same time so they can "share" the same index in the array of hazard pointers. Otherwise, a given pointer should have a unique bound to an entry of the hp array.
- How many hazard pointers are needed?
The more pointers are held at the same time, the less entries in the hp array can be shared. If we're traversing a list, typically we won't need more than three, but if we're traversing a tree, we may need one for each level of the tree.
- For the validation step, is it ok to use the same shared variable or not?
Most of the times, validating an hazard pointer is just a matter of reading an atomic variable, storing it in the hp array, and then checking that the same atomic variable has not changed. Sometimes, this is not enough to ensure safety and we need to read some other variable.
Figuring out what that other variable is, depends on the invariants of the data structure where you're trying to deploy HPs.
- When is it safe to retire an object/node?
We can retire a node only when that node is no longer accessible by other threads, and it's not always trivial to figure out in the code where to do it.
... and there's more, but I'll spare you.
<sarcasm>
Ohhhh wait, you thought this "Hazard Pointer thing" was just a matter of publishing some pointers so that those objects don't get deleted?
ooops, looks like it's not that simple, now does it? :)
</sarcasm>
Memory reclamation techniques like Hazard Pointers or RCU have two sides to it. There's the "readers" which just read objects/nodes but don't delete anything, and there's the "reclaimers" which retire and delete object/nodes (and also read).
In terms of progress conditions, HP is lock-free for the readers and wait-free bounded for the reclaimers.
There are some wait-free data structures where the "helping" mechanism can be used to make the HP readers become wait-free, but this is a specially tricky thing to do and deserves its own blog post.
On the other hand, RCU (and by RCU I mean Userspace-RCU) can be wait-free population oblivious for the readers, and is (at best) blocking with starvation-freedom for the reclaimers.
Perhaps more important than their progress conditions, is the fact that in HP, each (reader) thread has to do one sequentially-consistent atomic store for every node/object that is used (an MFENCE on x86), while on RCU it has to do it two or three times, regardless of the number of number of nodes/objects that are used.
Just in case you missed it, it's two or three times for RCU versus HP doing it a million times if there are a million nodes in a list!
How about RCU, how easy is to deploy it?
It's just a matter of calling rcu_read_lock() at the beginning of each method, and rcu_read_unlock() in every exit path, and in remove() it would need a synchronize_rcu() after the rcu_read_unlock() of a successful remove, followed by a free()/delete of the node.
Obviously, such an approach makes the remove() blocking because it has to wait for all "readers".
Huhhh so what are the questions you need to ask when you want to deploy RCU?
- Where do the functions start?
Huhhh immediately after the curly braces. We can place the call to rcu_read_lock() at the beginning, or anywhere before a shared variable is read.
- Where do the functions return?
Huhhh immediately before a "return" statement or at the last curly brace if the function returns void. We can place the call to rcu_read_unlock() before any exit path or as soon as no shared pointers are used anymore.
- When is it safe to retire an object/node?
We can retire a node only when that node is no longer accessible by other threads.
For the methods that need to delete an object/node, call synchronize_rcu() after the rcu_read_unlock() and then delete node.
That's it!
Did you notice any difference between the list of questions for RCU and the ones for Hazard Pointers?
This is where RCU's true magic comes from: its simplicity of deployment.
Sure, it's blocking for reclaimers (but it can scale by sharing grace periods).
RCU is wait-free for readers (low latency), has little synchronization overhead (high throughput), and it is easy to deploy... what more do you want?
FYI, there aren't that many concurrency constructs that give you high throughput and low latency.
Sure, it's just for the readers, and the reclaimers get blocked, but there are no silver bullets, only engineering solutions that fit better depending on the scenario, and RCU is the best fit in more scenarios than you may think ;)
No comments:
Post a Comment