[RFC 0/3] Examples for the new sparse context tracking functionality

[RFC 0/3] Examples for the new sparse context tracking functionality

[Johannes Berg]

Here are some patches that show how the new sparse functionality  
could be used in the kernel if merged.

As mentioned before, I have actually found three bugs in mac80211
using these patches. If you apply them and the sparse patches I have
also just posted, you can find them too :)

johannes

[RFC 1/3] add macros for new sparse features

[Johannes Berg]

[-- Attachment #1: 011-kernel-add-new-sparse-stuff.patch --]
[-- Type: text/plain, Size: 1577 bytes --]

This patch adds kernel macros for a few new sparse features, namely
 * checking try_lock functions and
 * making a function or macro require a certain lock.

Still waiting to see what the sparse folks say to my patches.

Not-yet-signed-off-by: Johannes Berg <johannes@sipsolutions.net>
---
 include/linux/compiler.h |    6 ++++++
 1 file changed, 6 insertions(+)

--- everything.orig/include/linux/compiler.h	2008-04-10 15:36:18.000000000 +0200
+++ everything/include/linux/compiler.h	2008-04-10 15:36:40.000000000 +0200
@@ -11,9 +11,12 @@
 # define __nocast	__attribute__((nocast))
 # define __iomem	__attribute__((noderef, address_space(2)))
 # define __acquires(x)	__attribute__((context(x,0,1)))
+# define __try_acquires(x,t,f)	__attribute__((conditional_context(x,0,t,f)))
 # define __releases(x)	__attribute__((context(x,1,0)))
 # define __acquire(x)	__context__(x,1)
 # define __release(x)	__context__(x,-1)
+# define __requires(x)	__attribute__((context(x,1,1)))
+# define __macro_requires(x)	__context__(x,0,1)
 # define __cond_lock(x,c)	((c) ? ({ __acquire(x); 1; }) : 0)
 extern void __chk_user_ptr(const volatile void __user *);
 extern void __chk_io_ptr(const volatile void __iomem *);
@@ -28,9 +31,12 @@ extern void __chk_io_ptr(const volatile 
 # define __chk_io_ptr(x) (void)0
 # define __builtin_warning(x, y...) (1)
 # define __acquires(x)
+# define __try_acquires(x,t,f)
 # define __releases(x)
 # define __acquire(x) (void)0
 # define __release(x) (void)0
+# define __requires(x)
+# define __macro_requires(x)
 # define __cond_lock(x,c) (c)
 #endif
 

-- 

[RFC 2/3] rcu: allow functions to declare they need RCU locking

[Johannes Berg]

[-- Attachment #1: 012-rcu-requires.patch --]
[-- Type: text/plain, Size: 897 bytes --]

Often enough, subsystems have a lookup function that goes from some
sort of key to an RCU-protected structure. They can then declare the
function as such:

struct mystruct *get_mystruct(...) __requires_rcu;

and sparse will automatically be able to check that the function is
invoked under rcu_read_lock().

Not-yet-signed-off-by: Johannes Berg <johannes@sipsolutions.net>
---
 include/linux/rcupdate.h |    4 ++++
 1 file changed, 4 insertions(+)

--- everything.orig/include/linux/rcupdate.h	2008-04-10 15:36:18.000000000 +0200
+++ everything/include/linux/rcupdate.h	2008-04-10 15:36:43.000000000 +0200
@@ -65,6 +65,10 @@ struct rcu_head {
        (ptr)->next = NULL; (ptr)->func = NULL; \
 } while (0)
 
+
+#define __requires_rcu		__requires(RCU)
+#define __macro_requires_rcu	__macro_requires(RCU)
+
 /**
  * rcu_read_lock - mark the beginning of an RCU read-side critical section.
  *

-- 

[RFC 3/3] mac80211: annotate with __requires_rcu

[Johannes Berg]

[-- Attachment #1: 013-mac80211-rcu-sparse.patch --]
[-- Type: text/plain, Size: 4688 bytes --]

As an example, this annotates mac80211 with the new __requires_rcu.

Not-yet-signed-off-by: Johannes Berg <johannes@sipsolutions.net>
---
 net/mac80211/key.c      |    2 +-
 net/mac80211/key.h      |    2 +-
 net/mac80211/rx.c       |   12 ++++++------
 net/mac80211/sta_info.h |    3 ++-
 net/mac80211/tx.c       |    3 ++-
 5 files changed, 12 insertions(+), 10 deletions(-)

--- everything.orig/net/mac80211/sta_info.h	2008-04-10 15:36:20.000000000 +0200
+++ everything/net/mac80211/sta_info.h	2008-04-10 15:36:45.000000000 +0200
@@ -321,7 +321,8 @@ static inline enum plink_state sta_plink
 /*
  * Get a STA info, must have be under RCU read lock.
  */
-struct sta_info *sta_info_get(struct ieee80211_local *local, u8 *addr);
+struct sta_info *sta_info_get(struct ieee80211_local *local, u8 *addr) __requires_rcu;
+
 /*
  * Get STA info by index, BROKEN!
  */
--- everything.orig/net/mac80211/key.c	2008-04-10 15:36:20.000000000 +0200
+++ everything/net/mac80211/key.c	2008-04-10 15:36:45.000000000 +0200
@@ -299,7 +299,7 @@ struct ieee80211_key *ieee80211_key_allo
 
 void ieee80211_key_link(struct ieee80211_key *key,
 			struct ieee80211_sub_if_data *sdata,
-			struct sta_info *sta)
+			struct sta_info *sta) __requires_rcu
 {
 	struct ieee80211_key *old_key;
 	unsigned long flags;
--- everything.orig/net/mac80211/key.h	2008-04-10 15:36:20.000000000 +0200
+++ everything/net/mac80211/key.h	2008-04-10 15:36:45.000000000 +0200
@@ -146,7 +146,7 @@ struct ieee80211_key *ieee80211_key_allo
  */
 void ieee80211_key_link(struct ieee80211_key *key,
 			struct ieee80211_sub_if_data *sdata,
-			struct sta_info *sta);
+			struct sta_info *sta) __requires(RCU);
 void ieee80211_key_free(struct ieee80211_key *key);
 void ieee80211_set_default_key(struct ieee80211_sub_if_data *sdata, int idx);
 void ieee80211_free_keys(struct ieee80211_sub_if_data *sdata);
--- everything.orig/net/mac80211/rx.c	2008-04-10 15:36:20.000000000 +0200
+++ everything/net/mac80211/rx.c	2008-04-10 15:36:45.000000000 +0200
@@ -1261,7 +1261,7 @@ static bool ieee80211_frame_allowed(stru
  * requires that rx->skb is a frame with ethernet header
  */
 static void
-ieee80211_deliver_skb(struct ieee80211_rx_data *rx)
+ieee80211_deliver_skb(struct ieee80211_rx_data *rx) __requires_rcu
 {
 	struct net_device *dev = rx->dev;
 	struct ieee80211_local *local = rx->local;
@@ -1349,7 +1349,7 @@ ieee80211_deliver_skb(struct ieee80211_r
 }
 
 static ieee80211_rx_result
-ieee80211_rx_h_amsdu(struct ieee80211_rx_data *rx)
+ieee80211_rx_h_amsdu(struct ieee80211_rx_data *rx) __requires_rcu
 {
 	struct net_device *dev = rx->dev;
 	struct ieee80211_local *local = rx->local;
@@ -1466,7 +1466,7 @@ ieee80211_rx_h_amsdu(struct ieee80211_rx
 }
 
 static ieee80211_rx_result
-ieee80211_rx_h_data(struct ieee80211_rx_data *rx)
+ieee80211_rx_h_data(struct ieee80211_rx_data *rx) __requires_rcu
 {
 	struct net_device *dev = rx->dev;
 	u16 fc;
@@ -1876,7 +1876,7 @@ static void __ieee80211_rx_handle_packet
 					 struct sk_buff *skb,
 					 struct ieee80211_rx_status *status,
 					 u32 load,
-					 struct ieee80211_rate *rate)
+					 struct ieee80211_rate *rate) __requires_rcu
 {
 	struct ieee80211_local *local = hw_to_local(hw);
 	struct ieee80211_sub_if_data *sdata;
@@ -1997,7 +1997,7 @@ static inline u16 seq_sub(u16 sq1, u16 s
 u8 ieee80211_sta_manage_reorder_buf(struct ieee80211_hw *hw,
 				struct tid_ampdu_rx *tid_agg_rx,
 				struct sk_buff *skb, u16 mpdu_seq_num,
-				int bar_req)
+				int bar_req) __requires_rcu
 {
 	struct ieee80211_local *local = hw_to_local(hw);
 	struct ieee80211_rx_status status;
@@ -2100,7 +2100,7 @@ u8 ieee80211_sta_manage_reorder_buf(stru
 }
 
 static u8 ieee80211_rx_reorder_ampdu(struct ieee80211_local *local,
-				     struct sk_buff *skb)
+				     struct sk_buff *skb) __requires_rcu
 {
 	struct ieee80211_hw *hw = &local->hw;
 	struct ieee80211_hdr *hdr = (struct ieee80211_hdr *) skb->data;
--- everything.orig/net/mac80211/tx.c	2008-04-10 15:36:20.000000000 +0200
+++ everything/net/mac80211/tx.c	2008-04-10 15:36:45.000000000 +0200
@@ -968,7 +968,7 @@ static ieee80211_tx_result
 __ieee80211_tx_prepare(struct ieee80211_tx_data *tx,
 		       struct sk_buff *skb,
 		       struct net_device *dev,
-		       struct ieee80211_tx_control *control)
+		       struct ieee80211_tx_control *control) __requires_rcu
 {
 	struct ieee80211_local *local = wdev_priv(dev->ieee80211_ptr);
 	struct ieee80211_hdr *hdr;
@@ -1047,6 +1047,7 @@ static int ieee80211_tx_prepare(struct i
 				struct sk_buff *skb,
 				struct net_device *mdev,
 				struct ieee80211_tx_control *control)
+	__requires_rcu
 {
 	struct ieee80211_tx_packet_data *pkt_data;
 	struct net_device *dev;

-- 

Re: [RFC 0/3] Examples for the new sparse context tracking functionality

[Johannes Berg]

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

On Thu, 2008-04-10 at 15:48 +0200, Johannes Berg wrote:
> Here are some patches that show how the new sparse functionality  
> could be used in the kernel if merged.

For those who haven't seen those patches:

http://thread.gmane.org/gmane.comp.parsers.sparse/1249

johannes

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

Re: [RFC 1/3] add macros for new sparse features

[Stefan Richter]

Johannes Berg wrote:
> This patch adds kernel macros for a few new sparse features, namely
>  * checking try_lock functions and
>  * making a function or macro require a certain lock.
> 
> Still waiting to see what the sparse folks say to my patches.
> 
> Not-yet-signed-off-by: Johannes Berg <johannes@sipsolutions.net>
> ---
>  include/linux/compiler.h |    6 ++++++
>  1 file changed, 6 insertions(+)
> 
> --- everything.orig/include/linux/compiler.h	2008-04-10 15:36:18.000000000 +0200
> +++ everything/include/linux/compiler.h	2008-04-10 15:36:40.000000000 +0200
> @@ -11,9 +11,12 @@
>  # define __nocast	__attribute__((nocast))
>  # define __iomem	__attribute__((noderef, address_space(2)))
>  # define __acquires(x)	__attribute__((context(x,0,1)))
> +# define __try_acquires(x,t,f)	__attribute__((conditional_context(x,0,t,f)))
>  # define __releases(x)	__attribute__((context(x,1,0)))
>  # define __acquire(x)	__context__(x,1)
>  # define __release(x)	__context__(x,-1)
> +# define __requires(x)	__attribute__((context(x,1,1)))
> +# define __macro_requires(x)	__context__(x,0,1)


So, instead of

  /* always call with host_lock held */
  int foo(struct bar *b)
  {

we could write

  int foo(struct bar *b) __requires(host_lock)
  {

and let sparse check the call chains... or how is it used?

And what about dynamically allocated locks?
E.g. b->lock
Or struct host h* = container_of(b, struct host, m); with the necessity
to hold h->lock...
-- 
Stefan Richter
-=====-==--- -=-- -=-=-
http://arcgraph.de/sr/

Re: [RFC 1/3] add macros for new sparse features

[Johannes Berg]

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


> So, instead of
> 
>   /* always call with host_lock held */
>   int foo(struct bar *b)
>   {
> 
> we could write
> 
>   int foo(struct bar *b) __requires(host_lock)
>   {
> 
> and let sparse check the call chains... or how is it used?

Yes.

> And what about dynamically allocated locks?
> E.g. b->lock
> Or struct host h* = container_of(b, struct host, m); with the necessity
> to hold h->lock...

I was looking at making sparse check that certain variable references
are under rcu, but it's not as easy. Also, the lock context is just an
arbitrary name, there's no way to actually link it to a certain variable
or so to differentiate between them. I think that's not really solvable
in sparse, look at the things lockdep has to do.

johannes

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

Re: [RFC 3/3] mac80211: annotate with __requires_rcu

[Geert Uytterhoeven]

[-- Attachment #1: Type: TEXT/PLAIN, Size: 1158 bytes --]

On Thu, 10 Apr 2008, Johannes Berg wrote:
> --- everything.orig/net/mac80211/key.h	2008-04-10 15:36:20.000000000 +0200
> +++ everything/net/mac80211/key.h	2008-04-10 15:36:45.000000000 +0200
> @@ -146,7 +146,7 @@ struct ieee80211_key *ieee80211_key_allo
>   */
>  void ieee80211_key_link(struct ieee80211_key *key,
>  			struct ieee80211_sub_if_data *sdata,
> -			struct sta_info *sta);
> +			struct sta_info *sta) __requires(RCU);
                                              ^^^^^^^^^^^^^^^
					      __requires_rcu? (for consistency)

With kind regards,

Geert Uytterhoeven
Software Architect

Sony Network and Software Technology Center Europe
The Corporate Village · Da Vincilaan 7-D1 · B-1935 Zaventem · Belgium

Phone:    +32 (0)2 700 8453
Fax:      +32 (0)2 700 8622
E-mail:   Geert.Uytterhoeven-osDt5Q4Chk1BDgjK7y7TUQ@public.gmane.org
Internet: http://www.sony-europe.com/

Sony Network and Software Technology Center Europe
A division of Sony Service Centre (Europe) N.V.
Registered office: Technologielaan 7 · B-1840 Londerzeel · Belgium
VAT BE 0413.825.160 · RPR Brussels
Fortis Bank Zaventem · Swift GEBABEBB08A · IBAN BE39001382358619

Re: [RFC 3/3] mac80211: annotate with __requires_rcu

[Johannes Berg]

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

On Sat, 2008-04-12 at 10:50 +0200, Geert Uytterhoeven wrote:
> On Thu, 10 Apr 2008, Johannes Berg wrote:
> > --- everything.orig/net/mac80211/key.h	2008-04-10 15:36:20.000000000 +0200
> > +++ everything/net/mac80211/key.h	2008-04-10 15:36:45.000000000 +0200
> > @@ -146,7 +146,7 @@ struct ieee80211_key *ieee80211_key_allo
> >   */
> >  void ieee80211_key_link(struct ieee80211_key *key,
> >  			struct ieee80211_sub_if_data *sdata,
> > -			struct sta_info *sta);
> > +			struct sta_info *sta) __requires(RCU);
>                                               ^^^^^^^^^^^^^^^
> 					      __requires_rcu? (for consistency)

Yeah, forgot to fix up this one, I had been playing with it locally
without __requires_rcu first.

Thanks,
johannes

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

Re: [RFC 0/3] Examples for the new sparse context tracking functionality

[Paul E. McKenney]

On Thu, Apr 10, 2008 at 03:48:10PM +0200, Johannes Berg wrote:
> Here are some patches that show how the new sparse functionality  
> could be used in the kernel if merged.
> 
> As mentioned before, I have actually found three bugs in mac80211
> using these patches. If you apply them and the sparse patches I have
> also just posted, you can find them too :)

I like this approach in general, deferring to Josh on specifics.

At some point in the future, we might want to distinguish between
the different flavors of RCU -- except that there is already common
code that doesn't care which flavor of RCU is in use, as long as
some sort of RCU is present.  So make that "some point in the distant
future"...

						Thanx, Paul
--
To unsubscribe from this list: send the line "unsubscribe linux-wireless" in
the body of a message to majordomo-u79uwXL29TY76Z2rM5mHXA@public.gmane.org
More majordomo info at  http://vger.kernel.org/majordomo-info.html

Re: [RFC 0/3] Examples for the new sparse context tracking functionality

[Johannes Berg]

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


> At some point in the future, we might want to distinguish between
> the different flavors of RCU -- except that there is already common
> code that doesn't care which flavor of RCU is in use, as long as
> some sort of RCU is present.  So make that "some point in the distant
> future"...

No big deal, just declare

my_specific_rcu_get() __acquires(RCU) __acquires(specificRCU);

and then annotate whatever needs the specific RCU type with
__requires(specificRCU)

johannes

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

Re: [RFC 0/3] Examples for the new sparse context tracking functionality

[Paul E. McKenney]

On Mon, Apr 21, 2008 at 10:25:55AM +0200, Johannes Berg wrote:
> 
> > At some point in the future, we might want to distinguish between
> > the different flavors of RCU -- except that there is already common
> > code that doesn't care which flavor of RCU is in use, as long as
> > some sort of RCU is present.  So make that "some point in the distant
> > future"...
> 
> No big deal, just declare
> 
> my_specific_rcu_get() __acquires(RCU) __acquires(specificRCU);
> 
> and then annotate whatever needs the specific RCU type with
> __requires(specificRCU)

Cute!!!  I didn't realize you could mark a single interface with
multiple __acquires() markings.

So if there is at least one match, sparse is happy?

							Thanx, Paul
--
To unsubscribe from this list: send the line "unsubscribe linux-wireless" in
the body of a message to majordomo-u79uwXL29TY76Z2rM5mHXA@public.gmane.org
More majordomo info at  http://vger.kernel.org/majordomo-info.html

Re: [RFC 0/3] Examples for the new sparse context tracking functionality

[Johannes Berg]

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


> > my_specific_rcu_get() __acquires(RCU) __acquires(specificRCU);
> > 
> > and then annotate whatever needs the specific RCU type with
> > __requires(specificRCU)
> 
> Cute!!!  I didn't realize you could mark a single interface with
> multiple __acquires() markings.
> 
> So if there is at least one match, sparse is happy?

No, sparse requires all the given contexts to match. For example, say
you have

#define __requires_rcu __requires(RCU)

#define __requires_special_rcu \
	__requires(specificRCU)

#define __acquires_special_rcu \
	__acquires(RCU) __acquires(specificRCU)

#define __acquires_regular_rcu __acquires(RCU)

Then a function marked "__acquires_special_rcu" with acquire *both*
contexts, and a function marked __requires_special_rcu will require just
the special one. And a function marked __requires_rcu just requires the
regular one. So say you have

rcu_special_lock __acquires_special_rcu
rcu_special_unlock __releases_special_rcu

rcu_regular_lock __acquires_rcu
rcu_regular_unlock __releases_rcu

rcu_do_special __requires_special_rcu
rcu_do_something __requires_rcu


Then both this will be fine:


rcu_special_lock()
rcu_do_special()
rcu_do_something()
rcu_special_unlock()


but this will result in a warning:


rcu_regular_lock()
rcu_do_special()
rcu_regular_unlock()

because the "specialRCU" context is missing.

You could mark do_special with *both* __requires(RCU) and
__requires(specialRCU) but as long as the acquires/releases parts have a
strict dependency (specialRCU implies RCU) that isn't necessary.

johannes

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