Using sparse to catch invalid RCU dereferences?

Using sparse to catch invalid RCU dereferences?

[Johannes Berg]

[-- Attachment #1: Type: text/plain, Size: 674 bytes --]

Hi,

Just a thought, I haven't tried this yet because I'm not entirely sure
it's actually correct. I was just thinking it should be possible to
introduce something like

	#define __rcu	__attribute__((address_space(3)))

(for sparse only, of course) and then be able to say

	struct myfoo *foo __rcu;

and sparse would warn on

	struct myfoo *bar = foo;

but not on

	struct myfoo *bar = rcu_dereference(foo);

by way of using __force inside rcu_dereference(), rcu_assign_pointer()
etc.

Would this be feasible? Or should one actually use __bitwise/__force to
also get the warning when assigning between two variables both marked
__rcu?

johannes

[-- Attachment #2: This is a digitally signed message part --]
[-- Type: application/pgp-signature, Size: 828 bytes --]

Re: Using sparse to catch invalid RCU dereferences?

[Paul E. McKenney]

On Tue, Apr 08, 2008 at 12:04:16AM +0200, Johannes Berg wrote:
> Hi,
> 
> Just a thought, I haven't tried this yet because I'm not entirely sure
> it's actually correct. I was just thinking it should be possible to
> introduce something like
> 
> 	#define __rcu	__attribute__((address_space(3)))
> 
> (for sparse only, of course) and then be able to say
> 
> 	struct myfoo *foo __rcu;
> 
> and sparse would warn on
> 
> 	struct myfoo *bar = foo;
> 
> but not on
> 
> 	struct myfoo *bar = rcu_dereference(foo);

Ah, "address_space" is a sparse-ism, no wonder I couldn't find it in
the gcc docs...

So the address_space attribute says what the pointer points to rather
than where the pointer resides, correct?

> by way of using __force inside rcu_dereference(), rcu_assign_pointer()
> etc.
> 
> Would this be feasible? Or should one actually use __bitwise/__force to
> also get the warning when assigning between two variables both marked
> __rcu?

It might be.  There are a number of places where it is legal to access
RCU-protected pointers directly, and all of these would need to be
changed.  For example, in the example above, one could do:

	foo = NULL;

I recently tried to modify rcu_assign_pointer() to issue the memory
memory barrier only when the pointer was non-NULL, but this ended badly.
Probably because I am not the greatest gcc expert around...  We ended
up having to define an rcu_assign_index() to handle the possibility of
assigning a zero-value array index, but my attempts to do type-checking
backfired, and I eventually gave it up.  Again, someone a bit more clued
in to gcc than I am could probably pull it off.

In addition, it is legal to omit rcu_dereference() and rcu_assign_pointer()
when holding the update-side lock.

So I very much like this approach in general, but it will require some
care to implement.  I would be very happy to review and comment!!!

							Thanx, Paul

Re: Using sparse to catch invalid RCU dereferences?

[Johannes Berg]

[-- Attachment #1: Type: text/plain, Size: 1636 bytes --]


> So the address_space attribute says what the pointer points to rather
> than where the pointer resides, correct?

Yeah. It's currently used for __user and __iomem. Using it for rcu
wouldn't be quite the way it was intended, I think, but hey :)

> It might be.  There are a number of places where it is legal to access
> RCU-protected pointers directly, and all of these would need to be
> changed.  For example, in the example above, one could do:
> 
> 	foo = NULL;

Yeah, all of those would lead to sparse warnings. Are we willing to
change all that code?

> I recently tried to modify rcu_assign_pointer() to issue the memory
> memory barrier only when the pointer was non-NULL, but this ended badly.
> Probably because I am not the greatest gcc expert around...  We ended
> up having to define an rcu_assign_index() to handle the possibility of
> assigning a zero-value array index, but my attempts to do type-checking
> backfired, and I eventually gave it up.  Again, someone a bit more clued
> in to gcc than I am could probably pull it off.

I don't think I would be that person :)

> In addition, it is legal to omit rcu_dereference() and rcu_assign_pointer()
> when holding the update-side lock.

Right. Those too would lead to problems, unless we change that code to
use those (or other) macros.

> So I very much like this approach in general, but it will require some
> care to implement.  I would be very happy to review and comment!!!

I'll play with it a bit if I get around, was just reviewing some RCU
usage and had the feeling that it should be possible to automate.

johannes

[-- Attachment #2: This is a digitally signed message part --]
[-- Type: application/pgp-signature, Size: 828 bytes --]

Re: Using sparse to catch invalid RCU dereferences?

[Paul E. McKenney]

On Tue, Apr 08, 2008 at 06:09:15PM +0200, Johannes Berg wrote:
> 
> > So the address_space attribute says what the pointer points to rather
> > than where the pointer resides, correct?
> 
> Yeah. It's currently used for __user and __iomem. Using it for rcu
> wouldn't be quite the way it was intended, I think, but hey :)

;-)

> > It might be.  There are a number of places where it is legal to access
> > RCU-protected pointers directly, and all of these would need to be
> > changed.  For example, in the example above, one could do:
> > 
> > 	foo = NULL;
> 
> Yeah, all of those would lead to sparse warnings. Are we willing to
> change all that code?

If it found some bugs, I would certainly be in favor!

> > I recently tried to modify rcu_assign_pointer() to issue the memory
> > memory barrier only when the pointer was non-NULL, but this ended badly.
> > Probably because I am not the greatest gcc expert around...  We ended
> > up having to define an rcu_assign_index() to handle the possibility of
> > assigning a zero-value array index, but my attempts to do type-checking
> > backfired, and I eventually gave it up.  Again, someone a bit more clued
> > in to gcc than I am could probably pull it off.
> 
> I don't think I would be that person :)

When it comes to gcc extensions and type-casting trickery, I am not all
that clued in, to be honest...

> > In addition, it is legal to omit rcu_dereference() and rcu_assign_pointer()
> > when holding the update-side lock.
> 
> Right. Those too would lead to problems, unless we change that code to
> use those (or other) macros.

Yep.

> > So I very much like this approach in general, but it will require some
> > care to implement.  I would be very happy to review and comment!!!
> 
> I'll play with it a bit if I get around, was just reviewing some RCU
> usage and had the feeling that it should be possible to automate.

If it finds a few bugs, it would be worth it!

							Thanx, Paul

Re: Using sparse to catch invalid RCU dereferences?

[Johannes Berg]

[-- Attachment #1: Type: text/plain, Size: 4128 bytes --]


> It might be.  There are a number of places where it is legal to access
> RCU-protected pointers directly, and all of these would need to be
> changed.  For example, in the example above, one could do:
> 
> 	foo = NULL;

Ok, that I understand, but sparse always treats NULL specially anyway.

> I recently tried to modify rcu_assign_pointer() to issue the memory
> memory barrier only when the pointer was non-NULL, but this ended badly.

Hm? I thought that's in the current tree.

> Probably because I am not the greatest gcc expert around...  We ended
> up having to define an rcu_assign_index() to handle the possibility of
> assigning a zero-value array index, but my attempts to do type-checking
> backfired, and I eventually gave it up.  Again, someone a bit more clued
> in to gcc than I am could probably pull it off.

Ah, ok.

> In addition, it is legal to omit rcu_dereference() and rcu_assign_pointer()
> when holding the update-side lock.

That I don't understand. Well, I do understand that omitting
rcu_dereference() is ok, but it seems to me that the memory and compiler
barrier in rcu_assign_pointer() is actually needed.

I've been playing a bit, see below for my play rcupdate.h and test.c
test program.

Unfortunately, sparse doesn't have the ability to declare
"__attribute__((force_bitwise)) typeof(p)" or even
"__attribute__((force)) typeof(p)" which makes this force more than
necessary and causes it to not catch when incompatible pointers are
used. gcc notices that because I only do a cast at all for sparse, but
that doesn't help, since e.g. list_for_each_entry_rcu() requires that
the correct type is returned. So without sparse supporting the latter
notation, we don't stand a chance.

Also, I wouldn't know how to declare that an array or so needs
rcu-access to the members.

johannes


rcupdate.h:

#define USE_BITWISE

#ifdef __CHECKER__
#ifdef USE_BITWISE
#define __rcu __attribute__((bitwise))
#define __force_rcu_cast(p) (*((__attribute__((force)) void **)&(p)))
// would like instead:
//#define __force_rcu_cast(p) ((__attribute__((force_bitwise)) typeof(p)) (p))
#else /* not bitwise */
#define __rcu __attribute__((address_space(3)))
#define __force_rcu_cast(p) (*((__attribute__((force)) void **)&(p)))
// would like instead:
//#define __force_rcu_cast(p) ((__attribute__((force_address_space)) typeof(p)) (p))
#endif

#else /* not checker */
#define __rcu
#define __force_rcu_cast(p) (p)
#endif

#define ACCESS_ONCE(x) (*(volatile typeof(x) *)&(x))

#define rcu_dereference(p)     ({ \
				typeof(p) _________p1 = ACCESS_ONCE(p); \
				smp_read_barrier_depends(); \
				__force_rcu_cast(_________p1); \
				})

/**
 * rcu_fetch - fetch an RCU-protected pointer in the update-locked
 * critical section.
 *
 * This macro exists for documentation and code checking purposes.
 */
#define rcu_fetch(p)     __force_rcu_cast(p);

#define rcu_assign_pointer(p, v) \
	({ \
		if (!__builtin_constant_p(v) || \
		    ((v) != NULL)) \
			smp_wmb(); \
		__force_rcu_cast(p) = (v); \
	})


test.c:

#include <stdlib.h>
#include "rcupdate.h"

/* my rcu protected variables */
static unsigned int __rcu *prot;
static unsigned int __rcu *prot_same;
static unsigned char __rcu *prot2;

// dummies
static smp_read_barrier_depends(void) {}
static smp_wmb(void) {}

int main(void)
{
	unsigned int *tmp;

	// no warnings from sparse due to forced cast
	rcu_assign_pointer(prot, tmp);
	// but gcc warns
	rcu_assign_pointer(prot2, tmp);

	// no warnings
	rcu_assign_pointer(prot, NULL);
	rcu_assign_pointer(prot2, NULL);

	// no warnings
	prot = NULL;
	prot2 = NULL;

	// no warnings from sparse due to forced cast
	tmp = rcu_dereference(prot);
	// but gcc warns
	tmp = rcu_dereference(prot2);

	/* now within locked section rcu_dereference isn't required */

	// no warnings from sparse due to forced cast
	tmp = rcu_fetch(prot);
	// but gcc warns
	tmp = rcu_fetch(prot2);

	/* not caught with address_space, but is caught with bitwise */
	prot = prot_same;
}


[-- Attachment #2: This is a digitally signed message part --]
[-- Type: application/pgp-signature, Size: 828 bytes --]

Re: Using sparse to catch invalid RCU dereferences?

[Paul E. McKenney]

On Wed, Apr 09, 2008 at 10:09:46PM +0200, Johannes Berg wrote:
> 
> > It might be.  There are a number of places where it is legal to access
> > RCU-protected pointers directly, and all of these would need to be
> > changed.  For example, in the example above, one could do:
> > 
> > 	foo = NULL;
> 
> Ok, that I understand, but sparse always treats NULL specially anyway.

But "int foo = 0;" would need the memory barrier -- index 0 of some
RCU-protected array.

> > I recently tried to modify rcu_assign_pointer() to issue the memory
> > memory barrier only when the pointer was non-NULL, but this ended badly.
> 
> Hm? I thought that's in the current tree.

It was for a bit.  Build failures in odd (but very real) circumstances.

> > Probably because I am not the greatest gcc expert around...  We ended
> > up having to define an rcu_assign_index() to handle the possibility of
> > assigning a zero-value array index, but my attempts to do type-checking
> > backfired, and I eventually gave it up.  Again, someone a bit more clued
> > in to gcc than I am could probably pull it off.
> 
> Ah, ok.
> 
> > In addition, it is legal to omit rcu_dereference() and rcu_assign_pointer()
> > when holding the update-side lock.
> 
> That I don't understand. Well, I do understand that omitting
> rcu_dereference() is ok, but it seems to me that the memory and compiler
> barrier in rcu_assign_pointer() is actually needed.

You are right -- I was confused.  The case where you can omit the
rcu_assign_pointer() would be when building a multiple-element data
structure that is then published as a unit.  For example:

	p = kmalloc(sizeof(*p), GFP_KERNEL);
	q = kmalloc(sizeof(*p), GFP_KERNEL);
	p->next = q; /* don't need rcu_assign_pointer() here. */
	q->next = NULL;  /* or here. */
	/* initialize other fields of p and q. */
	rcu_assign_pointer(global_pointer, p);

The assignment to p->next doesn't have to be rcu_assign_pointer() because
other CPUs are unable to access the data structure -- only the final
assignment that publishes the whole group need be rcu_assign_pointer().
On the other hand, the cost of the extra memory barrier would be
insignificant in most cases.

> I've been playing a bit, see below for my play rcupdate.h and test.c
> test program.
> 
> Unfortunately, sparse doesn't have the ability to declare
> "__attribute__((force_bitwise)) typeof(p)" or even
> "__attribute__((force)) typeof(p)" which makes this force more than
> necessary and causes it to not catch when incompatible pointers are
> used. gcc notices that because I only do a cast at all for sparse, but
> that doesn't help, since e.g. list_for_each_entry_rcu() requires that
> the correct type is returned. So without sparse supporting the latter
> notation, we don't stand a chance.

"<feff>"???

> Also, I wouldn't know how to declare that an array or so needs
> rcu-access to the members.

Hmmm...  Can you apply the address-space attribute to the array itself?
I suppose one could convert the array to a pointer, but yecch!

						Thanx, Paul

> johannes
> 
> 
> rcupdate.h:
> 
> #define USE_BITWISE
> 
> #ifdef __CHECKER__
> #ifdef USE_BITWISE
> #define __rcu __attribute__((bitwise))
> #define __force_rcu_cast(p) (*((__attribute__((force)) void **)&(p)))
> // would like instead:
> //#define __force_rcu_cast(p) ((__attribute__((force_bitwise)) typeof(p)) (p))
> #else /* not bitwise */
> #define __rcu __attribute__((address_space(3)))
> #define __force_rcu_cast(p) (*((__attribute__((force)) void **)&(p)))
> // would like instead:
> //#define __force_rcu_cast(p) ((__attribute__((force_address_space)) typeof(p)) (p))
> #endif
> 
> #else /* not checker */
> #define __rcu
> #define __force_rcu_cast(p) (p)
> #endif
> 
> #define ACCESS_ONCE(x) (*(volatile typeof(x) *)&(x))
> 
> #define rcu_dereference(p)     ({ \
> 				typeof(p) _________p1 = ACCESS_ONCE(p); \
> 				smp_read_barrier_depends(); \
> 				__force_rcu_cast(_________p1); \
> 				})
> 
> /**
>  * rcu_fetch - fetch an RCU-protected pointer in the update-locked
>  * critical section.
>  *
>  * This macro exists for documentation and code checking purposes.
>  */
> #define rcu_fetch(p)     __force_rcu_cast(p);
> 
> #define rcu_assign_pointer(p, v) \
> 	({ \
> 		if (!__builtin_constant_p(v) || \
> 		    ((v) != NULL)) \
> 			smp_wmb(); \
> 		__force_rcu_cast(p) = (v); \
> 	})
> 
> 
> test.c:
> 
> #include <stdlib.h>
> #include "rcupdate.h"
> 
> /* my rcu protected variables */
> static unsigned int __rcu *prot;
> static unsigned int __rcu *prot_same;
> static unsigned char __rcu *prot2;
> 
> // dummies
> static smp_read_barrier_depends(void) {}
> static smp_wmb(void) {}
> 
> int main(void)
> {
> 	unsigned int *tmp;
> 
> 	// no warnings from sparse due to forced cast
> 	rcu_assign_pointer(prot, tmp);
> 	// but gcc warns
> 	rcu_assign_pointer(prot2, tmp);
> 
> 	// no warnings
> 	rcu_assign_pointer(prot, NULL);
> 	rcu_assign_pointer(prot2, NULL);
> 
> 	// no warnings
> 	prot = NULL;
> 	prot2 = NULL;
> 
> 	// no warnings from sparse due to forced cast
> 	tmp = rcu_dereference(prot);
> 	// but gcc warns
> 	tmp = rcu_dereference(prot2);
> 
> 	/* now within locked section rcu_dereference isn't required */
> 
> 	// no warnings from sparse due to forced cast
> 	tmp = rcu_fetch(prot);
> 	// but gcc warns
> 	tmp = rcu_fetch(prot2);
> 
> 	/* not caught with address_space, but is caught with bitwise */
> 	prot = prot_same;
> }
> 


--
To unsubscribe from this list: send the line "unsubscribe linux-sparse" in
the body of a message to majordomo@vger.kernel.org
More majordomo info at  http://vger.kernel.org/majordomo-info.html

Re: Using sparse to catch invalid RCU dereferences?

[Peter Zijlstra]

On Tue, 2008-04-08 at 08:52 -0700, Paul E. McKenney wrote:
> On Tue, Apr 08, 2008 at 12:04:16AM +0200, Johannes Berg wrote:
> > Hi,
> > 
> > Just a thought, I haven't tried this yet because I'm not entirely sure
> > it's actually correct. I was just thinking it should be possible to
> > introduce something like
> > 
> > 	#define __rcu	__attribute__((address_space(3)))
> > 
> > (for sparse only, of course) and then be able to say
> > 
> > 	struct myfoo *foo __rcu;
> > 
> > and sparse would warn on
> > 
> > 	struct myfoo *bar = foo;
> > 
> > but not on
> > 
> > 	struct myfoo *bar = rcu_dereference(foo);
> 
> Ah, "address_space" is a sparse-ism, no wonder I couldn't find it in
> the gcc docs...
> 
> So the address_space attribute says what the pointer points to rather
> than where the pointer resides, correct?
> 
> > by way of using __force inside rcu_dereference(), rcu_assign_pointer()
> > etc.
> > 
> > Would this be feasible? Or should one actually use __bitwise/__force to
> > also get the warning when assigning between two variables both marked
> > __rcu?
> 
> It might be.  There are a number of places where it is legal to access
> RCU-protected pointers directly, and all of these would need to be
> changed.  For example, in the example above, one could do:
> 
> 	foo = NULL;
> 
> I recently tried to modify rcu_assign_pointer() to issue the memory
> memory barrier only when the pointer was non-NULL, but this ended badly.
> Probably because I am not the greatest gcc expert around...  We ended
> up having to define an rcu_assign_index() to handle the possibility of
> assigning a zero-value array index, but my attempts to do type-checking
> backfired, and I eventually gave it up.  Again, someone a bit more clued
> in to gcc than I am could probably pull it off.
> 
> In addition, it is legal to omit rcu_dereference() and rcu_assign_pointer()
> when holding the update-side lock.

We could start by annotating those as well, for example:

 __rcu spinlock_t tree_lock;

Then we would know that when tree lock is held the data structure is
stable and we can ommit the rcu_*() functions.

Re: Using sparse to catch invalid RCU dereferences?

[Paul E. McKenney]

On Fri, Apr 11, 2008 at 08:18:42PM +0200, Peter Zijlstra wrote:
> On Tue, 2008-04-08 at 08:52 -0700, Paul E. McKenney wrote:
> > On Tue, Apr 08, 2008 at 12:04:16AM +0200, Johannes Berg wrote:
> > > Hi,
> > > 
> > > Just a thought, I haven't tried this yet because I'm not entirely sure
> > > it's actually correct. I was just thinking it should be possible to
> > > introduce something like
> > > 
> > > 	#define __rcu	__attribute__((address_space(3)))
> > > 
> > > (for sparse only, of course) and then be able to say
> > > 
> > > 	struct myfoo *foo __rcu;
> > > 
> > > and sparse would warn on
> > > 
> > > 	struct myfoo *bar = foo;
> > > 
> > > but not on
> > > 
> > > 	struct myfoo *bar = rcu_dereference(foo);
> > 
> > Ah, "address_space" is a sparse-ism, no wonder I couldn't find it in
> > the gcc docs...
> > 
> > So the address_space attribute says what the pointer points to rather
> > than where the pointer resides, correct?
> > 
> > > by way of using __force inside rcu_dereference(), rcu_assign_pointer()
> > > etc.
> > > 
> > > Would this be feasible? Or should one actually use __bitwise/__force to
> > > also get the warning when assigning between two variables both marked
> > > __rcu?
> > 
> > It might be.  There are a number of places where it is legal to access
> > RCU-protected pointers directly, and all of these would need to be
> > changed.  For example, in the example above, one could do:
> > 
> > 	foo = NULL;
> > 
> > I recently tried to modify rcu_assign_pointer() to issue the memory
> > memory barrier only when the pointer was non-NULL, but this ended badly.
> > Probably because I am not the greatest gcc expert around...  We ended
> > up having to define an rcu_assign_index() to handle the possibility of
> > assigning a zero-value array index, but my attempts to do type-checking
> > backfired, and I eventually gave it up.  Again, someone a bit more clued
> > in to gcc than I am could probably pull it off.
> > 
> > In addition, it is legal to omit rcu_dereference() and rcu_assign_pointer()
> > when holding the update-side lock.
> 
> We could start by annotating those as well, for example:
> 
>  __rcu spinlock_t tree_lock;
> 
> Then we would know that when tree lock is held the data structure is
> stable and we can ommit the rcu_*() functions.

Good point!  Though IIRC there are are cases where we are updating
one RCU-protected data structure while in an RCU read-side critical
section with respect to another RCU-protected data structure.

But it would probably best to start as you say rather than trying
to classify different RCU uses.  :-)

						Thanx, Paul

Re: Using sparse to catch invalid RCU dereferences?

[Johannes Berg]

[-- Attachment #1: Type: text/plain, Size: 2974 bytes --]

On Thu, 2008-04-10 at 15:32 -0700, Paul E. McKenney wrote:
> On Wed, Apr 09, 2008 at 10:09:46PM +0200, Johannes Berg wrote:
> > 
> > > It might be.  There are a number of places where it is legal to access
> > > RCU-protected pointers directly, and all of these would need to be
> > > changed.  For example, in the example above, one could do:
> > > 
> > > 	foo = NULL;
> > 
> > Ok, that I understand, but sparse always treats NULL specially anyway.
> 
> But "int foo = 0;" would need the memory barrier -- index 0 of some
> RCU-protected array.

Oh. Hmm, I guess that wouldn't really be possible to find at least not
with sparse right now. Though maybe we can add some sort of annotation
that that special type can't even take zero directly.

> You are right -- I was confused.  The case where you can omit the
> rcu_assign_pointer() would be when building a multiple-element data
> structure that is then published as a unit.  For example:
> 
> 	p = kmalloc(sizeof(*p), GFP_KERNEL);
> 	q = kmalloc(sizeof(*p), GFP_KERNEL);
> 	p->next = q; /* don't need rcu_assign_pointer() here. */
> 	q->next = NULL;  /* or here. */
> 	/* initialize other fields of p and q. */
> 	rcu_assign_pointer(global_pointer, p);
> 
> The assignment to p->next doesn't have to be rcu_assign_pointer() because
> other CPUs are unable to access the data structure -- only the final
> assignment that publishes the whole group need be rcu_assign_pointer().
> On the other hand, the cost of the extra memory barrier would be
> insignificant in most cases.

Ah. Yeah, but we probably need a "raw" accessor anyway if we're going to
go this route, e.g. for any deref within the update-locked section.

> > I've been playing a bit, see below for my play rcupdate.h and test.c
> > test program.
> > 
> > Unfortunately, sparse doesn't have the ability to declare
> > "__attribute__((force_bitwise)) typeof(p)" or even
> > "__attribute__((force)) typeof(p)" which makes this force more than
> > necessary and causes it to not catch when incompatible pointers are
> > used. gcc notices that because I only do a cast at all for sparse, but
> > that doesn't help, since e.g. list_for_each_entry_rcu() requires that
> > the correct type is returned. So without sparse supporting the latter
> > notation, we don't stand a chance.
> 
> "<feff>"???

Hmm?

> > Also, I wouldn't know how to declare that an array or so needs
> > rcu-access to the members.
> 
> Hmmm...  Can you apply the address-space attribute to the array itself?
> I suppose one could convert the array to a pointer, but yecch!

Not sure if applying that to an array would work, and I wouldn't want to
convert it to pointers either. But I suppose you could declare the array
like this:

static struct foo * __attribute__((bitwise or address_space)) array[7];

which should, as far as I understand, apply the attribute to the array
members instead of the array.

johannes

[-- Attachment #2: This is a digitally signed message part --]
[-- Type: application/pgp-signature, Size: 828 bytes --]