rcu,doc: lock-free update site
Subsystems (2)
PATCH 1/1 rcu,doc: lock-free update site
Add a document which describes a pattern of using RCU to implement lock-free(lockless) update site.
--- Documentation/RCU/00-INDEX | 2 + Documentation/RCU/lock-free-update-site.txt | 143 +++++++++++++++++++++++++++ 2 files changed, 145 insertions(+), 0 deletions(-)
Documentation/RCU/00-INDEX +2 -0
@@ -8,6 +8,8 @@ listRCU.txt - Using RCU to Protect Read-Mostly Linked Lists lockdep.txt - RCU and lockdep checking +lock-free-update-site.txt + - RCU pattern of lock-free update site NMI-RCU.txt - Using RCU to Protect Dynamic NMI Handlers rcubarrier.txt
Documentation/RCU/lock-free-update-site.txt new file +143 -0
143 lines not on this page · raw message
Quoted 3 lines · * Lai Jiangshan ([email protected]) wrote:
Add a document which describes a pattern of using RCU to implement lock-free(lockless) update site.
[...]
Documentation/RCU/lock-free-update-site.txt line 6
Quoted 7 lines
Documentation/RCU/lock-free-update-site.txt new file +6
-0@@ -0,0 +1,143 @@ +Lock-free(lockless) update site + +This article describes a pattern of using RCU to implement lock-free(lockless) +update site. RCU update site is considered call-rare and it is protected +by a update-site lock generally. But blocking algorithms are undesirable +in some cases for some reasons, thus, this pattern may help.
Hi Lai,
Yes, using this kind of rcu read-side lock to protect against the cmpxchg ABA problem is well-known (to me at least) ;) I used this technique in the userspace RCU library "lock-free queue" and "lock-free stack" in 2010*. Please feel free to dig through my RCU data containers code to bring in more data structure examples:
Thanks!
Mathieu
* AFAIK I introduced this technique using RCU read-side C.S. to deal with cmpxchg ABA at that point, but someone might have thought about it before me without my knowledge. My litterature survey so far indicates that using a double-word CAS on a pointer/counter was one of the usual technique used to protect against cmpxchg ABA so far. Other techniques imply allocating elements in a limited-size array (so a simple cmpxchg can update the array index and counter atomically), Hasard Pointers, or having a full-blown GC which provides similar guarantees to the RCU grace period with a read-side lock held. Ref.:
[1998] Maged Michael, Michael Scott "Simple, fast, and practical non-blocking and blocking concurrent queue algorithms" [2002] Maged M.Michael "Safe memory reclamation for dynamic lock-free objects using atomic reads and writes" [2003] Maged M.Michael "Hazard Pointers: Safe memory reclamation for lock-free objects"
Quoted 140 lines
Documentation/RCU/lock-free-update-site.txt new file +137
-0+ +This pattern can only protect a single pointer which is the only reference +of the object. + +object pointer: + +struct my_struct *gptr; + +wait-free read site: +{ + rcu_read_lock(); + ptr = rcu_dereference(gptr); + my_struct_read(ptr); + rcu_read_unlock(); +} + +lock-free update site(update as new): +{ + new_ptr = my_struct_alloc(); + for (;;) { + rcu_read_lock(); + + old_ptr = rcu_dereference(gptr); + + /* copy data from old_ptr to new_ptr and update it */ + my_struct_update(new_ptr, old_ptr); + + /* atomically publish the new_ptr and de-publish the old_ptr */ + if (cmpxchg(&gptr, old_ptr, new_ptr) == old_ptr) { + rcu_read_unlock(); + + /* + * free it after a grace-period, read sites and other + * update sites may be reading it in parallel. + */ + kfree_rcu(old_ptr); + + /* success, exit the loop */ + break; + } else { + rcu_read_unlock(); + + /* + * Other update site successfully update it, we need + * to read the latest data and try the update again. + * + * If the other update site did the same thing we need, + * we can free the new_ptr and exit this loop too, + * and it may becomes a wait-free algorithm. + */ + } + } +} + +1) In update site, rcu_read_lock() is needed for my_struct_update(). + + In this kind of lock-free update site, many update sides + may run parallel, other update side may had successfully + de-published old_ptr and tried to free it. rcu_read_lock() + prevents old_ptr from freeing and ensures it valid for + my_struct_update(). + +2) In update site, rcu_read_lock() is needed until cmpxchg() finished. + + Although the content of old_ptr is not accessed when cmpxchg(), + but old_ptr should not be freed until cmpxchg() finished. + Otherwise we may miss other successful update and publish a + new_ptr without information from the latest object. + + Example:(wrong update site code, rcu_read_unlock() is moved up before cmpxchg()) + (cause ABA-problem: http://en.wikipedia.org/wiki/ABA_problem) + + CPU0 CPU1 + rcu_read_lock() + old_ptr = rcu_dereference(gptr); + my_struct_update(new_ptr, old_ptr); + rcu_read_unlock(); + . successfully update, now gptr=other_ptr + . old_ptr is freed + . + . other update, my_struct_alloc() returns old_ptr + . successfully publish and de-publish + . now gptr=old_ptr again + . + cmpxchg(&gptr, old_ptr, new_ptr) + cmpxchg() success, but the 2 updates + of CPU1 are completely missed. + + This exmaple shows rcu_read_lock() is needed to prevent old_ptr from reusing + before cmpxchg() finished and to prevent ABA-problem. + +3) Beware NULL pointer. + + Some use cases may set gptr to NULL when needed. (the previous gptr != NULL) + +lock-free update site(dispose, wait-free): +{ + old_ptr = xchg(&gptr, NULL); + if (old_ptr != NULL) + kfree_rcu(old_ptr); +} + + This code cause NULL reusing and may cause ABA-problem like above example: + + CPU0 CPU1 + rcu_read_lock() + old_ptr = rcu_dereference(gptr); + /* old_ptr = NULL */ + my_struct_update(new_ptr, NULL); + . successfully update, now gptr=other_ptr + . + . successfully dispose + . now gptr=NULL again + . + cmpxchg(&gptr, NULL, new_ptr) + cmpxchg() success, but the update + and the dispose of CPU1 are missed + consideration by CPU0. + rcu_read_unlock(); + + In many use cases, these behaviors are OK. In these use cases, + my_struct_update(new_ptr, NULL) give us the same result even we retry. + + But in some raw use cases(I can't find any use-case now, I believe it exist), + the missed considerations of the updates are not acceptable, in this case, + we should use different null-value for NULL pointer for every disposing. + +lock-free update site(dispose, wait-free, paranoid version): +{ + null_ptr = alloc_null_ptr(); + old_ptr = xchg(&gptr, null_ptr); + if (is_null_ptr(old_ptr)) + free_null_ptr_by_rcu_for_preventing_it_from_reusing(old_ptr); + else + kfree_rcu(old_ptr); +} +
Signature · 4 lines
Mathieu Desnoyers Operating System Efficiency R&D Consultant EfficiOS Inc. http://www.efficios.com
A message that is not in the archive (sent off-list or not yet received): [email protected]
Quoted 21 lines · Mathieu Desnoyers
Quoted 3 lines · * Lai Jiangshan ([email protected]) wrote:
Add a document which describes a pattern of using RCU to implement lock-free(lockless) update site.
[...]
Documentation/RCU/lock-free-update-site.txt line 6
Quoted 7 lines
Documentation/RCU/lock-free-update-site.txt new file +6
-0@@ -0,0 +1,143 @@ +Lock-free(lockless) update site + +This article describes a pattern of using RCU to implement lock-free(lockless) +update site. RCU update site is considered call-rare and it is protected +by a update-site lock generally. But blocking algorithms are undesirable +in some cases for some reasons, thus, this pattern may help.Hi Lai,
Yes, using this kind of rcu read-side lock to protect against the cmpxchg ABA problem is well-known (to me at least) ;) I used this technique in the userspace RCU library "lock-free queue" and "lock-free stack" in 2010*. Please feel free to dig through my RCU data containers code to bring in more data structure examples:
Quoted 7 lines
Thanks!
Mathieu
Hi, Mathieu
I will try to make simple update site wait-free, so I wrote a simple guide/document at first. I didn't notice your work. Your work is excellent,
I will add some references. I hope you rewrite/pretty this document also.
The lock-free stack is a good example, but the lock-free queue is not good here I think.
Thanks,
Lai
Quoted 16 lines
* AFAIK I introduced this technique using RCU read-side
C.S. to deal with cmpxchg ABA at that point, but someone might have thought about it before me without my knowledge. My litterature survey so far indicates that using a double-word CAS on a pointer/counter was one of the usual technique used to protect against cmpxchg ABA so far. Other techniques imply allocating elements in a limited-size array (so a simple cmpxchg can update the array index and counter atomically), Hasard Pointers, or having a full-blown GC which provides similar guarantees to the RCU grace period with a read-side lock held. Ref.:[1998] Maged Michael, Michael Scott "Simple, fast, and practical non-blocking and blocking concurrent queue algorithms" [2002] Maged M.Michael "Safe memory reclamation for dynamic lock-free objects using atomic reads and writes" [2003] Maged M.Michael "Hazard Pointers: Safe memory reclamation for lock-free objects"
Quoted 31 lines · Lai Jiangshan
Quoted 21 lines · Mathieu Desnoyers
Quoted 3 lines · * Lai Jiangshan ([email protected]) wrote:
Add a document which describes a pattern of using RCU to implement lock-free(lockless) update site.
[...]
Documentation/RCU/lock-free-update-site.txt line 6
Quoted 7 lines
Documentation/RCU/lock-free-update-site.txt new file +6
-0@@ -0,0 +1,143 @@ +Lock-free(lockless) update site + +This article describes a pattern of using RCU to implement lock-free(lockless) +update site. RCU update site is considered call-rare and it is protected +by a update-site lock generally. But blocking algorithms are undesirable +in some cases for some reasons, thus, this pattern may help.Hi Lai,
Yes, using this kind of rcu read-side lock to protect against the cmpxchg ABA problem is well-known (to me at least) ;) I used this technique in the userspace RCU library "lock-free queue" and "lock-free stack" in 2010*. Please feel free to dig through my RCU data containers code to bring in more data structure examples:
Quoted 7 lines
Hi, Mathieu
I will try to make simple update site wait-free, so I wrote a simple guide/document at first. I didn't notice your work. Your work is excellent,
I will add some references. I hope you rewrite/pretty this document also.The lock-free stack is a good example, but the lock-free queue is not good here I think.
I look forward to seeing the update!
Thanx, Paul
Quoted 26 lines
Thanks,
LaiQuoted 12 lines
* AFAIK I introduced this technique using RCU read-side
C.S. to deal with cmpxchg ABA at that point, but someone might have thought about it before me without my knowledge. My litterature survey so far indicates that using a double-word CAS on a pointer/counter was one of the usual technique used to protect against cmpxchg ABA so far. Other techniques imply allocating elements in a limited-size array (so a simple cmpxchg can update the array index and counter atomically), Hasard Pointers, or having a full-blown GC which provides similar guarantees to the RCU grace period with a read-side lock held. Ref.:Quoted 4 lines
[1998] Maged Michael, Michael Scott "Simple, fast, and practical non-blocking and blocking concurrent queue algorithms" [2002] Maged M.Michael "Safe memory reclamation for dynamic lock-free objects using atomic reads and writes" [2003] Maged M.Michael "Hazard Pointers: Safe memory reclamation for lock-free objects"
--
To unsubscribe from this list: send the line "unsubscribe linux-kernel" in the body of a message to [email protected]
More majordomo info at http://vger.kernel.org/majordomo-info.html
Please read the FAQ at http://www.tux.org/lkml/