[PATCH] mac80211: optimise ieee80211_get_hdrlen

[PATCH] mac80211: optimise ieee80211_get_hdrlen

[Johannes Berg]

This patch optimises the ieee80211_get_hdrlen function by exploiting the
bit masks directly.

On powerpc, this decreases the function by 4 instructions, but more
importantly it kills 4 of the 5 branches it contained.

Signed-off-by: Johannes Berg <johannes@sipsolutions.net>

---
And don't ask me how the compiler actually gets by with a single branch
now!

It was fun to do but in my userspace test program on powerpc doesn't
seem to change much, CPU time goes down by like 2%...

 net/mac80211/ieee80211.c |   23 ++++++++++++++---------
 1 file changed, 14 insertions(+), 9 deletions(-)

--- wireless-dev.orig/net/mac80211/ieee80211.c	2007-03-27 16:33:47.163155480 +0200
+++ wireless-dev/net/mac80211/ieee80211.c	2007-03-27 16:33:48.473155480 +0200
@@ -258,19 +258,24 @@ int ieee80211_get_hdrlen(u16 fc)
 	case IEEE80211_FTYPE_DATA:
 		if ((fc & IEEE80211_FCTL_FROMDS) && (fc & IEEE80211_FCTL_TODS))
 			hdrlen = 30; /* Addr4 */
-		if (fc & IEEE80211_STYPE_QOS_DATA)
-			hdrlen += 2; /* QoS Control Field */
+		/* QoS Control Field */
+		hdrlen += (fc & IEEE80211_STYPE_QOS_DATA)
+				>> (ilog2(IEEE80211_STYPE_QOS_DATA)-1);
 		break;
 	case IEEE80211_FTYPE_CTL:
-		switch (fc & IEEE80211_FCTL_STYPE) {
-		case IEEE80211_STYPE_CTS:
-		case IEEE80211_STYPE_ACK:
+		/*
+		 * ACK and CTS are 10 bytes, all others 16. To see how
+		 * to get this condition consider
+		 *   subtype mask:   0b0000000011110000 (0x00F0)
+		 *   ACK subtype:    0b0000000011010000 (0x00D0)
+		 *   CTS subtype:    0b0000000011000000 (0x00C0)
+		 *   bits that matter:         ^^^      (0x00E0)
+		 *   value of those: 0b0000000011000000 (0x00C0)
+		 */
+		if ((fc & 0xE0) == 0xC0)
 			hdrlen = 10;
-			break;
-		default:
+		else
 			hdrlen = 16;
-			break;
-		}
 		break;
 	}
 

Re: [PATCH] mac80211: optimise ieee80211_get_hdrlen

[Jouni Malinen]

On Tue, Mar 27, 2007 at 06:01:45PM +0200, Johannes Berg wrote:

> This patch optimises the ieee80211_get_hdrlen function by exploiting the
> bit masks directly.

> --- wireless-dev.orig/net/mac80211/ieee80211.c	2007-03-27 16:33:47.163155480 +0200
> +++ wireless-dev/net/mac80211/ieee80211.c	2007-03-27 16:33:48.473155480 +0200
> @@ -258,19 +258,24 @@ int ieee80211_get_hdrlen(u16 fc)
>  	case IEEE80211_FTYPE_DATA:
>  		if ((fc & IEEE80211_FCTL_FROMDS) && (fc & IEEE80211_FCTL_TODS))
>  			hdrlen = 30; /* Addr4 */
> -		if (fc & IEEE80211_STYPE_QOS_DATA)
> -			hdrlen += 2; /* QoS Control Field */
> +		/* QoS Control Field */
> +		hdrlen += (fc & IEEE80211_STYPE_QOS_DATA)
> +				>> (ilog2(IEEE80211_STYPE_QOS_DATA)-1);
>  		break;

Could you please add a comment explaining what exactly happens here and
more importantly, include an easy way of understanding that this adds 2
bytes.

>  	case IEEE80211_FTYPE_CTL:
> -		switch (fc & IEEE80211_FCTL_STYPE) {
> -		case IEEE80211_STYPE_CTS:
> -		case IEEE80211_STYPE_ACK:
> +		/*
> +		 * ACK and CTS are 10 bytes, all others 16. To see how
> +		 * to get this condition consider
> +		 *   subtype mask:   0b0000000011110000 (0x00F0)
> +		 *   ACK subtype:    0b0000000011010000 (0x00D0)
> +		 *   CTS subtype:    0b0000000011000000 (0x00C0)
> +		 *   bits that matter:         ^^^      (0x00E0)
> +		 *   value of those: 0b0000000011000000 (0x00C0)
> +		 */
> +		if ((fc & 0xE0) == 0xC0)
>  			hdrlen = 10;
> -			break;
> -		default:
> +		else
>  			hdrlen = 16;
> -			break;
> -		}

Is this case even used anywhere? Looks like unnecessary optimization at
the cost of making the source code more difficult to understand and
modify.

-- 
Jouni Malinen                                            PGP id EFC895FA

Re: [PATCH] mac80211: optimise ieee80211_get_hdrlen

[Johannes Berg]

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

On Wed, 2007-03-28 at 12:11 -0700, Jouni Malinen wrote:

> > +		/* QoS Control Field */
> > +		hdrlen += (fc & IEEE80211_STYPE_QOS_DATA)
> > +				>> (ilog2(IEEE80211_STYPE_QOS_DATA)-1);
> >  		break;
> 
> Could you please add a comment explaining what exactly happens here and
> more importantly, include an easy way of understanding that this adds 2
> bytes.

Yeah, I should do that.

> Is this case even used anywhere? Looks like unnecessary optimization at
> the cost of making the source code more difficult to understand and
> modify.

Not sure. I tested in userspace with a program that simply tried all
possible values.

johannes

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

Re: [PATCH] mac80211: optimise ieee80211_get_hdrlen

[Jouni Malinen]

On Thu, Mar 29, 2007 at 01:07:27PM +0200, Johannes Berg wrote:
> On Wed, 2007-03-28 at 12:11 -0700, Jouni Malinen wrote:

> > Is this case even used anywhere? Looks like unnecessary optimization at
> > the cost of making the source code more difficult to understand and
> > modify.
> 
> Not sure. I tested in userspace with a program that simply tried all
> possible values.

At least originally, there were no need for processing any control
frames which is why asked this.. I haven't looked whether any of the new
hardware drivers have needs for processing them.

-- 
Jouni Malinen                                            PGP id EFC895FA

[PATCH] mac80211: optimise ieee80211_get_hdrlen

[Johannes Berg]

This patch optimises the ieee80211_get_hdrlen function by exploiting the
bit masks directly.

On powerpc, this decreases the function by 4 instructions, but more
importantly it kills 3 of the 5 branches it contained.

Signed-off-by: Johannes Berg <johannes@sipsolutions.net>

---
Looks like I forgot to resend this with the new comment. I think
optimising the control frames too is fine even if we don't use them,
it's not /that/ hard to understand.

 net/mac80211/ieee80211.c |   31 +++++++++++++++++++++----------
 1 file changed, 21 insertions(+), 10 deletions(-)

--- wireless-dev.orig/net/mac80211/ieee80211.c	2007-04-27 12:03:38.334987898 +0200
+++ wireless-dev/net/mac80211/ieee80211.c	2007-04-27 12:03:43.034987898 +0200
@@ -255,21 +255,32 @@ int ieee80211_get_hdrlen(u16 fc)
 
 	switch (fc & IEEE80211_FCTL_FTYPE) {
 	case IEEE80211_FTYPE_DATA:
-		if ((fc & IEEE80211_FCTL_FROMDS) && (fc & IEEE80211_FCTL_TODS))
+		if (unlikely((fc & IEEE80211_FCTL_FROMDS) && (fc & IEEE80211_FCTL_TODS)))
 			hdrlen = 30; /* Addr4 */
-		if (fc & IEEE80211_STYPE_QOS_DATA)
-			hdrlen += 2; /* QoS Control Field */
+		/*
+		 * The QoS Control field is two bytes and its presence is
+		 * indicated by the IEEE80211_STYPE_QOS_DATA bit. Add 2 to
+		 * hdrlen if that bit is set.
+		 * This works by masking out the bit and shifting it to
+		 * bit position 1 so the result has the value 0 or 2.
+		 */
+		hdrlen += (fc & IEEE80211_STYPE_QOS_DATA)
+				>> (ilog2(IEEE80211_STYPE_QOS_DATA)-1);
 		break;
 	case IEEE80211_FTYPE_CTL:
-		switch (fc & IEEE80211_FCTL_STYPE) {
-		case IEEE80211_STYPE_CTS:
-		case IEEE80211_STYPE_ACK:
+		/*
+		 * ACK and CTS are 10 bytes, all others 16. To see how
+		 * to get this condition consider
+		 *   subtype mask:   0b0000000011110000 (0x00F0)
+		 *   ACK subtype:    0b0000000011010000 (0x00D0)
+		 *   CTS subtype:    0b0000000011000000 (0x00C0)
+		 *   bits that matter:         ^^^      (0x00E0)
+		 *   value of those: 0b0000000011000000 (0x00C0)
+		 */
+		if ((fc & 0xE0) == 0xC0)
 			hdrlen = 10;
-			break;
-		default:
+		else
 			hdrlen = 16;
-			break;
-		}
 		break;
 	}
 

Re: [PATCH] mac80211: optimise ieee80211_get_hdrlen

[Jiri Benc]

On Fri, 27 Apr 2007 17:10:17 +0200, Johannes Berg wrote:
> --- wireless-dev.orig/net/mac80211/ieee80211.c	2007-04-27 12:03:38.334987898 +0200
> +++ wireless-dev/net/mac80211/ieee80211.c	2007-04-27 12:03:43.034987898 +0200
> @@ -255,21 +255,32 @@ int ieee80211_get_hdrlen(u16 fc)
>  
>  	switch (fc & IEEE80211_FCTL_FTYPE) {
>  	case IEEE80211_FTYPE_DATA:
> -		if ((fc & IEEE80211_FCTL_FROMDS) && (fc & IEEE80211_FCTL_TODS))
> +		if (unlikely((fc & IEEE80211_FCTL_FROMDS) && (fc & IEEE80211_FCTL_TODS)))

This is not unlikely if you have a WDS link set up. I wouldn't change the
condition.

 Jiri

-- 
Jiri Benc
SUSE Labs

Re: [PATCH] mac80211: optimise ieee80211_get_hdrlen

[Johannes Berg]

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

On Sat, 2007-04-28 at 15:40 +0200, Jiri Benc wrote:
> On Fri, 27 Apr 2007 17:10:17 +0200, Johannes Berg wrote:
> > --- wireless-dev.orig/net/mac80211/ieee80211.c	2007-04-27 12:03:38.334987898 +0200
> > +++ wireless-dev/net/mac80211/ieee80211.c	2007-04-27 12:03:43.034987898 +0200
> > @@ -255,21 +255,32 @@ int ieee80211_get_hdrlen(u16 fc)
> >  
> >  	switch (fc & IEEE80211_FCTL_FTYPE) {
> >  	case IEEE80211_FTYPE_DATA:
> > -		if ((fc & IEEE80211_FCTL_FROMDS) && (fc & IEEE80211_FCTL_TODS))
> > +		if (unlikely((fc & IEEE80211_FCTL_FROMDS) && (fc & IEEE80211_FCTL_TODS)))
> 
> This is not unlikely if you have a WDS link set up. I wouldn't change the
> condition.

Good point. Want me to resend of do you want to just remove the
unlikely?

johannes

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

Re: [PATCH] mac80211: optimise ieee80211_get_hdrlen

[Jiri Benc]

On Sat, 28 Apr 2007 15:58:37 +0200, Johannes Berg wrote:
> On Sat, 2007-04-28 at 15:40 +0200, Jiri Benc wrote:
> > This is not unlikely if you have a WDS link set up. I wouldn't change the
> > condition.
> 
> Good point. Want me to resend of do you want to just remove the
> unlikely?

Applied without the unlikely part.

Thanks,

 Jiri

-- 
Jiri Benc
SUSE Labs