Skip to contentSkip to conversation

Examples for the new sparse context tracking functionality

RFC In review Johannes Berg 6 participants 15 messages Apr 10, 2008 – Apr 21, 2008

Subsystems (3)
mac80211 RCU Sparse checker
lore
Share & tools
lore

Johannes Berg

author maintainer
#0 lore raw

cover Examples for the new sparse context tracking functionality

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

author maintainer
#1 lore raw

RFC 1/3 add macros for new sparse features

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 <[email protected]>
---
 include/linux/compiler.h |    6 ++++++
 1 file changed, 6 insertions(+)
include/linux/compiler.h +6 -0
@@ -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
#2 lore raw

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

Quoted 14 lines · Johannes Berg

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 <[email protected]>
---
 include/linux/compiler.h |    6 ++++++
 1 file changed, 6 insertions(+)

include/linux/compiler.h line 19

Quoted 9 lines
include/linux/compiler.h +3 -0
@@ -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...

Signature · 3 lines
Stefan Richter
-=====-==--- -=-- -=-=-
http://arcgraph.de/sr/
author maintainer
#3 lore raw

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

Quoted 7 lines

So, instead of

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

we could write

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

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

Yes.

Quoted 4 lines

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

author maintainer
#4 lore raw

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

In reply to Johannes Berg

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 <[email protected]>
---
 include/linux/rcupdate.h |    4 ++++
 1 file changed, 4 insertions(+)
include/linux/rcupdate.h +4 -0
@@ -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.
  *
author maintainer
#5 lore raw

RFC 3/3 mac80211: annotate with __requires_rcu

In reply to Johannes Berg

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

Not-yet-signed-off-by Johannes Berg <[email protected]>
---
 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(-)
net/mac80211/sta_info.h +2 -1
@@ -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!
  */
net/mac80211/key.c +1 -1
@@ -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;
net/mac80211/key.h +1 -1
@@ -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);
net/mac80211/rx.c +6 -6
@@ -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;
net/mac80211/tx.c +2 -1
@@ -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;
#6 lore raw

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

net/mac80211/key.h struct ieee80211_key *ieee80211_key_allo · line 149

Quoted 8 lines · Johannes Berg
net/mac80211/key.h +1 -1
@@ -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:   [email protected]
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

author maintainer
#7 lore raw

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

Quoted 11 lines · Geert Uytterhoeven

net/mac80211/key.h struct ieee80211_key *ieee80211_key_allo · line 149

Quoted 8 lines · Johannes Berg
net/mac80211/key.h +1 -1
@@ -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

#8 lore raw

RFC 1/2 mac80211: Patch to prevent mac80211 to clobber injected sequence numbers

In reply to Geert Uytterhoeven

# Patch to prevent mac80211 to clobber injected sequence numbers

net/mac80211/tx.c +3 -0
index f35eaea..ef3e33f 100644
@@ -292,6 +292,9 @@ ieee80211_tx_h_sequence(struct ieee80211_tx_data *tx)
 {
        struct ieee80211_hdr *hdr = (struct ieee80211_hdr *)tx->skb->data;
 
+       if (unlikely(tx->flags & IEEE80211_TXRXD_TX_INJECTED))
+               return TXRX_CONTINUE;
+
        if (ieee80211_get_hdrlen(le16_to_cpu(hdr->frame_control)) >= 24)
                ieee80211_include_sequence(tx->sdata, hdr);
#9 lore raw

Re: [RFC 1/2] mac80211: Patch to prevent mac80211 to clobber injected sequence numbers

Quoted 1 line · On Saturday 12 April 2008 15:38:00 Jory A. Pratt wrote:

See list archives for why these two patches are not acceptable as-is.

Signature · 1 line
Greetings Michael.
#11 lore raw
In reply to Johannes Berg
Quoted 6 lines · 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 :)

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 [email protected] More majordomo info at http://vger.kernel.org/majordomo-info.html

author maintainer
#12 lore raw
Quoted 6 lines

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

#13 lore raw
Quoted 7 lines · Johannes Berg
Quoted 6 lines

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"...

Quoted 6 lines

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 [email protected] More majordomo info at http://vger.kernel.org/majordomo-info.html

author maintainer
#14 lore raw
Quoted 10 lines
Quoted 5 lines

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