* [PATCH] rbtree: use READ_ONCE in RB_EMPTY_ROOT
@ 2016-01-11 18:22 Davidlohr Bueso
2016-01-12 9:06 ` Peter Zijlstra
0 siblings, 1 reply; 4+ messages in thread
From: Davidlohr Bueso @ 2016-01-11 18:22 UTC (permalink / raw)
To: Andrew Morton, Peter Zijlstra; +Cc: dave, linux-kernel, Davidlohr Bueso
With d72da4a4d97 (rbtree: Make lockless searches non-fatal) our rbtrees
provide weak guarantees that allows us to do lockless (and very speculative)
reads of the tree. Such readers cannot see partial stores on nodes, ie
left/right as well as root. As such, similar to the WRITE_ONCE semantics when
doing rotations, use READ_ONCE when checking the root node in RB_EMPTY_ROOT.
Signed-off-by: Davidlohr Bueso <dbueso@suse.de>
---
include/linux/rbtree.h | 2 +-
1 file changed, 1 insertion(+), 1 deletion(-)
diff --git a/include/linux/rbtree.h b/include/linux/rbtree.h
index a5aa7ae..b690009 100644
--- a/include/linux/rbtree.h
+++ b/include/linux/rbtree.h
@@ -50,7 +50,7 @@ struct rb_root {
#define RB_ROOT (struct rb_root) { NULL, }
#define rb_entry(ptr, type, member) container_of(ptr, type, member)
-#define RB_EMPTY_ROOT(root) ((root)->rb_node == NULL)
+#define RB_EMPTY_ROOT(root) (READ_ONCE((root)->rb_node) == NULL)
/* 'empty' nodes are nodes that are known not to be inserted in an rbtree */
#define RB_EMPTY_NODE(node) \
--
2.1.4
^ permalink raw reply related [flat|nested] 4+ messages in thread
* Re: [PATCH] rbtree: use READ_ONCE in RB_EMPTY_ROOT
2016-01-11 18:22 [PATCH] rbtree: use READ_ONCE in RB_EMPTY_ROOT Davidlohr Bueso
@ 2016-01-12 9:06 ` Peter Zijlstra
2016-01-12 15:09 ` Davidlohr Bueso
0 siblings, 1 reply; 4+ messages in thread
From: Peter Zijlstra @ 2016-01-12 9:06 UTC (permalink / raw)
To: Davidlohr Bueso; +Cc: Andrew Morton, linux-kernel, Davidlohr Bueso
On Mon, Jan 11, 2016 at 10:22:43AM -0800, Davidlohr Bueso wrote:
> With d72da4a4d97 (rbtree: Make lockless searches non-fatal) our rbtrees
> provide weak guarantees that allows us to do lockless (and very speculative)
> reads of the tree. Such readers cannot see partial stores on nodes, ie
> left/right as well as root. As such, similar to the WRITE_ONCE semantics when
> doing rotations, use READ_ONCE when checking the root node in RB_EMPTY_ROOT.
No objection, but is this actually used anywhere?
Or is this a just-in-case completeness thing?
^ permalink raw reply [flat|nested] 4+ messages in thread
* Re: [PATCH] rbtree: use READ_ONCE in RB_EMPTY_ROOT
2016-01-12 9:06 ` Peter Zijlstra
@ 2016-01-12 15:09 ` Davidlohr Bueso
2016-01-12 15:59 ` Peter Zijlstra
0 siblings, 1 reply; 4+ messages in thread
From: Davidlohr Bueso @ 2016-01-12 15:09 UTC (permalink / raw)
To: Peter Zijlstra; +Cc: Andrew Morton, linux-kernel, Davidlohr Bueso
On Tue, 12 Jan 2016, Peter Zijlstra wrote:
>On Mon, Jan 11, 2016 at 10:22:43AM -0800, Davidlohr Bueso wrote:
>> With d72da4a4d97 (rbtree: Make lockless searches non-fatal) our rbtrees
>> provide weak guarantees that allows us to do lockless (and very speculative)
>> reads of the tree. Such readers cannot see partial stores on nodes, ie
>> left/right as well as root. As such, similar to the WRITE_ONCE semantics when
>> doing rotations, use READ_ONCE when checking the root node in RB_EMPTY_ROOT.
>
>No objection, but is this actually used anywhere?
I found this because I wanted to use the waiter check in rtmutexes in a lockless
fashion (ie rt_mutex_has_waiters).
>
>Or is this a just-in-case completeness thing?
This too.
Thanks,
Davidlohr
^ permalink raw reply [flat|nested] 4+ messages in thread
* Re: [PATCH] rbtree: use READ_ONCE in RB_EMPTY_ROOT
2016-01-12 15:09 ` Davidlohr Bueso
@ 2016-01-12 15:59 ` Peter Zijlstra
0 siblings, 0 replies; 4+ messages in thread
From: Peter Zijlstra @ 2016-01-12 15:59 UTC (permalink / raw)
To: Davidlohr Bueso; +Cc: Andrew Morton, linux-kernel, Davidlohr Bueso
On Tue, Jan 12, 2016 at 07:09:46AM -0800, Davidlohr Bueso wrote:
> On Tue, 12 Jan 2016, Peter Zijlstra wrote:
>
> >On Mon, Jan 11, 2016 at 10:22:43AM -0800, Davidlohr Bueso wrote:
> >>With d72da4a4d97 (rbtree: Make lockless searches non-fatal) our rbtrees
> >>provide weak guarantees that allows us to do lockless (and very speculative)
> >>reads of the tree. Such readers cannot see partial stores on nodes, ie
> >>left/right as well as root. As such, similar to the WRITE_ONCE semantics when
> >>doing rotations, use READ_ONCE when checking the root node in RB_EMPTY_ROOT.
> >
> >No objection, but is this actually used anywhere?
>
> I found this because I wanted to use the waiter check in rtmutexes in a lockless
> fashion (ie rt_mutex_has_waiters).
OK, fair enough.
Acked-by: Peter Zijlstra (Intel) <peterz@infradead.org>
^ permalink raw reply [flat|nested] 4+ messages in thread
end of thread, other threads:[~2016-01-12 15:59 UTC | newest]
Thread overview: 4+ messages (download: mbox.gz / follow: Atom feed)
-- links below jump to the message on this page --
2016-01-11 18:22 [PATCH] rbtree: use READ_ONCE in RB_EMPTY_ROOT Davidlohr Bueso
2016-01-12 9:06 ` Peter Zijlstra
2016-01-12 15:09 ` Davidlohr Bueso
2016-01-12 15:59 ` Peter Zijlstra
This is an external index of several public inboxes,
see mirroring instructions on how to clone and mirror
all data and code used by this external index.