Re: [patch 01/15] Kernel Tracepoints

[Paul E. McKenney]

On Tue, Jul 15, 2008 at 12:51:23PM -0400, Mathieu Desnoyers wrote:
> * Peter Zijlstra (peterz@xxxxxxxxxxxxx) wrote:
> > On Tue, 2008-07-15 at 12:08 -0400, Mathieu Desnoyers wrote:
> > > * Peter Zijlstra (peterz@xxxxxxxxxxxxx) wrote:
> > > > On Tue, 2008-07-15 at 11:22 -0400, Mathieu Desnoyers wrote:
> > > > > * Peter Zijlstra (peterz@xxxxxxxxxxxxx) wrote:
> > > > > > 
> > > > > > I'm confused by the barrier games here.
> > > > > > 
> > > > > > Why not:
> > > > > > 
> > > > > >   void **it_func;
> > > > > > 
> > > > > >   preempt_disable();
> > > > > >   it_func = rcu_dereference((tp)->funcs);
> > > > > >   if (it_func) {
> > > > > >     for (; *it_func; it_func++)
> > > > > >       ((void(*)(proto))(*it_func))(args);
> > > > > >   }
> > > > > >   preempt_enable();
> > > > > > 
> > > > > > That is, why can we skip the barrier when !it_func? is that because at
> > > > > > that time we don't actually dereference it_func and therefore cannot
> > > > > > observe stale data?
> > > > > > 
> > > > > 
> > > > > Exactly. I used the implementation of rcu_assign_pointer as a hint that
> > > > > we did not need barriers when setting the pointer to NULL, and thus we
> > > > > should not need the read barrier when reading the NULL pointer, because
> > > > > it references no data.
> > > > > 
> > > > > #define rcu_assign_pointer(p, v) \
> > > > >         ({ \
> > > > >                 if (!__builtin_constant_p(v) || \
> > > > >                     ((v) != NULL)) \
> > > > >                         smp_wmb(); \
> > > > >                 (p) = (v); \
> > > > >         })
> > > > 
> > > > Yeah, I saw that,.. made me wonder. It basically assumes that when we
> > > > write:
> > > > 
> > > >   rcu_assign_pointer(foo, NULL);
> > > > 
> > > > foo will not be used as an index or offset.
> > > > 
> > > > I guess Paul has thought it through and verified all in-kernel use
> > > > cases, but it still makes me feel unconfortable.
> > > > 
> > > > > #define rcu_dereference(p)     ({ \
> > > > >                                 typeof(p) _________p1 = ACCESS_ONCE(p); \
> > > > >                                 smp_read_barrier_depends(); \
> > > > >                                 (_________p1); \
> > > > >                                 })
> > > > > 
> > > > > But I think you are right, since we are already in unlikely code, using
> > > > > rcu_dereference as you do is better than my use of read barrier depends.
> > > > > It should not change anything in the assembly result except on alpha,
> > > > > where the read_barrier_depends() is not a nop.
> > > > > 
> > > > > I wonder if there would be a way to add this kind of NULL pointer case
> > > > > check without overhead in rcu_dereference() on alpha. I guess not, since
> > > > > the pointer is almost never known at compile-time. And I guess Paul must
> > > > > already have thought about it. The only case where we could add this
> > > > > test is when we know that we have a if (ptr != NULL) test following the
> > > > > rcu_dereference(); we could then assume the compiler will merge the two
> > > > > branches since they depend on the same condition.
> > > > 
> > > > I remember seeing a thread about all this special casing NULL, but have
> > > > never been able to find it again - my google skillz always fail me.
> > > > 
> > > > Basically it doesn't work if you use the variable as an index/offset,
> > > > because in that case 0 is a valid offset and you still generate a data
> > > > dependency.
> > > > 
> > > > IIRC the conclusion was that the gains were too small to spend more time
> > > > on it, although I would like to hear about the special case in
> > > > rcu_assign_pointer.
> > > > 
> > > > /me goes use git blame....
> > > > 
> > > 
> > > Actually, we could probably do the following, which also adds an extra
> > > coherency check about non-NULL pointer assumptions :
> > > 
> > > #ifdef CONFIG_RCU_DEBUG /* this would be new */
> > > #define DEBUG_RCU_BUG_ON(x) BUG_ON(x)
> > > #else
> > > #define DEBUG_RCU_BUG_ON(x)
> > > #endif
> > > 
> > > #define rcu_dereference(p)     ({ \
> > >                                 typeof(p) _________p1 = ACCESS_ONCE(p); \
> > >                                 if (p != NULL) \
> > >                                   smp_read_barrier_depends(); \
> > >                                 (_________p1); \
> > >                                 })
> > > 
> > > #define rcu_dereference_non_null(p)     ({ \
> > >                                 typeof(p) _________p1 = ACCESS_ONCE(p); \
> > >                                 DEBUG_RCU_BUG_ON(p == NULL); \
> > >                                 smp_read_barrier_depends(); \
> > >                                 (_________p1); \
> > >                                 })
> > > 
> > > The use-case where rcu_dereference() would be used is when it is
> > > followed by a null pointer check (grepping through the sources shows me
> > > this is a very very common case). In rare cases, it is assumed that the
> > > pointer is never NULL and it is used just after the rcu_dereference. It
> > > those cases, the extra test could be saved on alpha by using
> > > rcu_dereference_non_null(p), which would check the the pointer is indeed
> > > never NULL under some debug kernel configuration.
> > > 
> > > Does it make sense ?
> > 
> > This would break the case where the dereferenced variable is used as an
> > index/offset where 0 is a valid value and still generates data
> > dependencies.
> > 
> > So if with your new version we do:
> > 
> >   i = rcu_dereference(foo);
> >   j = table[i];
> > 
> > which translates into:
> > 
> >   i = ACCESS_ONCE(foo);
> >   if (i)
> >     smp_read_barrier_depends();
> >   j = table[i];
> > 
> > which when i == 0, would fail to do the barrier and can thus cause j to
> > be a wrong value.
> > 
> > Sadly I'll have to defer to Paul to explain exactly how that can happen
> > - I always get my head in a horrible twist with this case.
> > 
> 
> I completely agree with you. However, given the current
> rcu_assign_pointer() implementation, we already have this problem. My
> proposal assumes the current rcu_assign_pointer() behavior is correct
> and that those are never ever used for index/offsets.
> 
> We could enforce this as a compile-time check with something along the
> lines of :
> 
> #define BUILD_BUG_ON_NOT_OFFSETABLE(x) (void)(x)[0]
> 
> And use it both in rcu_assign_pointer() and rcu_dereference().  It would
> check for any type passed to rcu_assign_pointer and rcu_dereference
> which is not either a pointer or an array.
> 
> Then if someone really want to shoot himself in the foot by casting a
> pointer to a long after the rcu_deref, that's his problem.
> 
> Hrm, looking at rcu_assign_pointer tells me that the ((v) != NULL) test
> should probably already complain if v is not a pointer. So my build test
> is probably unneeded.

Yeah, I was thinking in terms of rcu_dereference() working with both
rcu_assign_pointer() and an as-yet-mythical rcu_assign_index().  Perhaps
this would be a good time to get better names:

Current:	rcu_assign_pointer()	rcu_dereference()
New Pointers:	rcu_publish_pointer()	rcu_subscribe_pointer()
New Indexes:	rcu_publish_index()	rcu_subscribe_index()

And, while I am at it, work in a way of checking for either being in
the appropriate RCU read-side critical section and/or having the
needed lock/mutex/whatever held -- something I believe PeterZ was
prototyping some months back.

Though I still am having a hard time with the conditional in
rcu_dereference() vs. the smp_read_barrier_depends()...

						Thanx, Paul
--
To unsubscribe from this list: send the line "unsubscribe linux-kernel" in
the body of a message to majordomo@xxxxxxxxxxxxxxx
More majordomo info at  http://vger.kernel.org/majordomo-info.html
Please read the FAQ at  http://www.tux.org/lkml/