[PATCH] fix sparse warning from include/linux/mmzone.h

[PATCH] fix sparse warning from include/linux/mmzone.h

[Harvey Harrison]

include/linux/mmzone.h:640:22: warning: potentially expensive pointer subtraction

The code in question was doing a pointer subtraction to find the index of
the zone argument in the node_zones array.  This essentially boils down to:

((unsigned long)zone - (unsigned long)zone->zone_pgdat->node_zones)/sizeof(struct zone)

Which can be expensive if struct zone is not a power of two.  Instead, just
calculate the offsets rather than the index in the array.

Signed-off-by: Harvey Harrison <harvey.harrison@gmail.com>
---
This shows up > 30 times in an x86 allyesconfig, would be nice to get
rid of it and makes the code a little more efficient.  I believe this
is correct, unless there is a subtlety I have missed.

 include/linux/mmzone.h |    9 ++++++---
 1 files changed, 6 insertions(+), 3 deletions(-)

diff --git a/include/linux/mmzone.h b/include/linux/mmzone.h
index 8d8d197..cb07758 100644
--- a/include/linux/mmzone.h
+++ b/include/linux/mmzone.h
@@ -637,9 +637,12 @@ static inline int is_normal_idx(enum zone_type idx)
 static inline int is_highmem(struct zone *zone)
 {
 #ifdef CONFIG_HIGHMEM
-	int zone_idx = zone - zone->zone_pgdat->node_zones;
-	return zone_idx == ZONE_HIGHMEM ||
-		(zone_idx == ZONE_MOVABLE && zone_movable_is_highmem());
+	const int highmem_off = ZONE_HIGHMEM * sizeof(*zone);
+	const int movable_off = ZONE_MOVABLE * sizeof(*zone);
+
+	int zone_off = (unsigned long)zone - (unsigned long)zone->zone_pgdat->node_zones;
+	return zone_off == highmem_off ||
+		(zone_off == movable_off && zone_movable_is_highmem());
 #else
 	return 0;
 #endif
-- 
1.5.4.1219.g65b9

Re: [PATCH] fix sparse warning from include/linux/mmzone.h

[Andrew Morton]

On Thu, 07 Feb 2008 12:52:23 -0800
Harvey Harrison <harvey.harrison@gmail.com> wrote:

> include/linux/mmzone.h:640:22: warning: potentially expensive pointer subtraction
> 
> The code in question was doing a pointer subtraction to find the index of
> the zone argument in the node_zones array.  This essentially boils down to:
> 
> ((unsigned long)zone - (unsigned long)zone->zone_pgdat->node_zones)/sizeof(struct zone)
> 
> Which can be expensive if struct zone is not a power of two.  Instead, just
> calculate the offsets rather than the index in the array.
> 
> Signed-off-by: Harvey Harrison <harvey.harrison@gmail.com>
> ---
> This shows up > 30 times in an x86 allyesconfig, would be nice to get
> rid of it and makes the code a little more efficient.  I believe this
> is correct, unless there is a subtlety I have missed.
> 
>  include/linux/mmzone.h |    9 ++++++---
>  1 files changed, 6 insertions(+), 3 deletions(-)
> 
> diff --git a/include/linux/mmzone.h b/include/linux/mmzone.h
> index 8d8d197..cb07758 100644
> --- a/include/linux/mmzone.h
> +++ b/include/linux/mmzone.h
> @@ -637,9 +637,12 @@ static inline int is_normal_idx(enum zone_type idx)
>  static inline int is_highmem(struct zone *zone)
>  {
>  #ifdef CONFIG_HIGHMEM
> -	int zone_idx = zone - zone->zone_pgdat->node_zones;
> -	return zone_idx == ZONE_HIGHMEM ||
> -		(zone_idx == ZONE_MOVABLE && zone_movable_is_highmem());
> +	const int highmem_off = ZONE_HIGHMEM * sizeof(*zone);
> +	const int movable_off = ZONE_MOVABLE * sizeof(*zone);
> +
> +	int zone_off = (unsigned long)zone - (unsigned long)zone->zone_pgdat->node_zones;
> +	return zone_off == highmem_off ||
> +		(zone_off == movable_off && zone_movable_is_highmem());
>  #else
>  	return 0;
>  #endif
> -- 

hrm.  For my i386 build (and that's where CONFIG_HIGHMEM really matters)
this patch makes mm/page_alloc.o six bytes larger, and I don't think the
change did much for readability.

Re: [PATCH] fix sparse warning from include/linux/mmzone.h

[Linus Torvalds]

On Fri, 8 Feb 2008, Andrew Morton wrote:
> >  #ifdef CONFIG_HIGHMEM
> > -	int zone_idx = zone - zone->zone_pgdat->node_zones;
> > -	return zone_idx == ZONE_HIGHMEM ||
> > -		(zone_idx == ZONE_MOVABLE && zone_movable_is_highmem());
> > +	const int highmem_off = ZONE_HIGHMEM * sizeof(*zone);
> > +	const int movable_off = ZONE_MOVABLE * sizeof(*zone);
> > +
> > +	int zone_off = (unsigned long)zone - (unsigned long)zone->zone_pgdat->node_zones;
> > +	return zone_off == highmem_off ||
> > +		(zone_off == movable_off && zone_movable_is_highmem());
> 
> hrm.  For my i386 build (and that's where CONFIG_HIGHMEM really matters)
> this patch makes mm/page_alloc.o six bytes larger, and I don't think the
> change did much for readability.

Heh, yeah. That's a very odd way to write it.

It would probably make more sense to just write it as something like

	struct zone *base = zone->zone_pgdat->node_zones;

	if (zone == base + ZONE_HIGHMEM ||
		(zone == base + ZONE_MOVABLE && zone_movable_is_highmem());

instead.

The above is totally untested, of course.

		Linus

Re: [PATCH] fix sparse warning from include/linux/mmzone.h

[Harvey Harrison]

On Fri, 2008-02-08 at 14:04 -0800, Linus Torvalds wrote:
> 
> On Fri, 8 Feb 2008, Andrew Morton wrote:
> > >  #ifdef CONFIG_HIGHMEM
> > > -	int zone_idx = zone - zone->zone_pgdat->node_zones;
> > > -	return zone_idx == ZONE_HIGHMEM ||
> > > -		(zone_idx == ZONE_MOVABLE && zone_movable_is_highmem());
> > > +	const int highmem_off = ZONE_HIGHMEM * sizeof(*zone);
> > > +	const int movable_off = ZONE_MOVABLE * sizeof(*zone);
> > > +
> > > +	int zone_off = (unsigned long)zone - (unsigned long)zone->zone_pgdat->node_zones;
> > > +	return zone_off == highmem_off ||
> > > +		(zone_off == movable_off && zone_movable_is_highmem());
> > 
> > hrm.  For my i386 build (and that's where CONFIG_HIGHMEM really matters)
> > this patch makes mm/page_alloc.o six bytes larger, and I don't think the
> > change did much for readability.
> 
> Heh, yeah. That's a very odd way to write it.

As long as you read 'odd' as 'rather dumb'

> 
> It would probably make more sense to just write it as something like
> 
> 	struct zone *base = zone->zone_pgdat->node_zones;
> 
> 	if (zone == base + ZONE_HIGHMEM ||
> 		(zone == base + ZONE_MOVABLE && zone_movable_is_highmem());

s/if/return/ I think.  And missing a closing brace.  Unless I'm (again)
missing something.

Harvey

Re: [PATCH] fix sparse warning from include/linux/mmzone.h

[Ingo Molnar]

* Linus Torvalds <torvalds@linux-foundation.org> wrote:

> Heh, yeah. That's a very odd way to write it.
> 
> It would probably make more sense to just write it as something like
> 
> 	struct zone *base = zone->zone_pgdat->node_zones;
> 
> 	if (zone == base + ZONE_HIGHMEM ||
> 		(zone == base + ZONE_MOVABLE && zone_movable_is_highmem());
> 
> instead.

missing closing parenthesis ;-)

btw., doesnt this look even nicer?:

     if (zone == base + ZONE_HIGHMEM ||
        (zone == base + ZONE_MOVABLE && zone_movable_is_highmem()));

[ i guess it must be Friday... ;-) ]

	Ingo

Re: [PATCH] fix sparse warning from include/linux/mmzone.h

[Linus Torvalds]

On Fri, 8 Feb 2008, Linus Torvalds wrote:
> 
> It would probably make more sense to just write it as something like
> 
> 	struct zone *base = zone->zone_pgdat->node_zones;
> 
> 	if (zone == base + ZONE_HIGHMEM ||
> 		(zone == base + ZONE_MOVABLE && zone_movable_is_highmem());

Side note: while the above is more readable, gcc still isn't smart enough 
to notice that the two compares could be done more efficiently as a 
subtraction. But using an actual pointer subtraction does involve that 
nasty divide (well, it's nasty only for certain sizes of "struct zone"), 
so writing it as such is not very nice either, even if it's the most 
obvious way from a source code standpoint.

Here's an example:

	/* 12-byte (non-power-of-two) example struct */
	struct example {
	        int a, b, c;
	};
	
	#define ptrcmp1(ptr, base, index) \
	        ((ptr) == (base) + (index))
	#define ptrcmp2(ptr, base, index) \
	        ((ptr) - (base) == (index))
	#define ptrcmp3(ptr, base, index) \
	        ((char *)(ptr) - (char *)(base) == (index)*sizeof(*ptr))

	#define test(cmp) \
	        if (cmp(ptr, base, 1) || cmp(ptr, base, 3)) \
	                printf("success\n")

	int test1(struct example *ptr, struct example *base) { test(ptrcmp1); }
	int test2(struct example *ptr, struct example *base) { test(ptrcmp2); }
	int test3(struct example *ptr, struct example *base) { test(ptrcmp3); }

and the results for me are:

	test1:
	        leaq    12(%rsi), %rax
	        cmpq    %rdi, %rax
	        je      .L15
	        leaq    36(%rsi), %rax
	        cmpq    %rdi, %rax
	        je      .L15

	test2:
	        subq    %rsi, %rdi
	        leaq    -12(%rdi), %rax
	        cmpq    $11, %rax
	        jbe     .L11
	        leaq    -36(%rdi), %rax
	        cmpq    $11, %rax
	        jbe     .L11

	test3:
	        subq    %rsi, %rdi
	        cmpq    $12, %rdi
	        je      .L4
	        cmpq    $36, %rdi
	        je      .L4

ie the only way to get the *nice* code generation is that ugly third 
alternative.

YMMV depending on compiler, of course.

			Linus

Re: [PATCH] fix sparse warning from include/linux/mmzone.h

[Harvey Harrison]

Maybe I'm beating a dead horse, but here's what I came up with:

include/linux/mmzone.h:640:22: warning: potentially expensive pointer subtraction

Using arch/x86/mm/highmem_32.o as an example, line 82, PageHighMem
expands to is_highmem.

	if (!PageHighMem(page))
		return page_address(page);

I've run through the current code, one of Linus' suggestions and Linus'
alternate version of my original patch without the stupid unsigned
long casts, using char *.  The best version appears to be the char *
version.  Code size will increase by one byte for each use of
is_highmem, but there is one fewer instruction (saves a sar over the
base code).  The reason for the code size increase is the two cmps
use 32-bit compares rather than 16 bit compares in the original due
to the sar beforehand. (-3 bytes for no sar +4 bytes for longer cmp)

It's a small thing, if you agree that the new code is better, I'll
send a patch.

Original:
static inline int is_highmem(struct zone *zone)
{
#ifdef CONFIG_HIGHMEM
	int zone_idx = zone - zone->zone_pgdat->node_zones;
	return zone_idx == ZONE_HIGHMEM ||
		(zone_idx == ZONE_MOVABLE && zone_movable_is_highmem());
#else
	return 0;
#endif
}

 207:	2b 80 8c 07 00 00    	sub    0x78c(%eax),%eax
 20d:	c1 f8 0b             	sar    $0xb,%eax
 210:	83 f8 02             	cmp    $0x2,%eax
 213:	74 16                	je     22b <kmap_atomic_prot+0x144>
 215:	83 f8 03             	cmp    $0x3,%eax
 218:	0f 85 8f 00 00 00    	jne    2ad <kmap_atomic_prot+0x1c6>
 21e:	83 3d 00 00 00 00 02 	cmpl   $0x2,0x0
 225:	0f 85 82 00 00 00    	jne    2ad <kmap_atomic_prot+0x1c6>
 22b:	64 a1 00 00 00 00    	mov    %fs:0x0,%eax

Linus' suggestion:
static inline int is_highmem(struct zone *zone)
{
#ifdef CONFIG_HIGHMEM
	struct zone *base = zone->zone_pgdat->node_zones;
	return zone == base + ZONE_HIGHMEM ||
		(zone == base + ZONE_MOVABLE && zone_movable_is_highmem());
#else
	return 0;
#endif
}

 202:	8d 90 00 00 00 00    	lea    0x0(%eax),%edx
 208:	8b 8a 8c 07 00 00    	mov    0x78c(%edx),%ecx
 20e:	8d 81 00 10 00 00    	lea    0x1000(%ecx),%eax
 214:	39 c2                	cmp    %eax,%edx
 216:	74 1b                	je     233 <kmap_atomic_prot+0x14c>
 218:	8d 81 00 18 00 00    	lea    0x1800(%ecx),%eax
 21e:	39 c2                	cmp    %eax,%edx
 220:	0f 85 8f 00 00 00    	jne    2b5 <kmap_atomic_prot+0x1ce>
 226:	83 3d 00 00 00 00 02 	cmpl   $0x2,0x0
 22d:	0f 85 82 00 00 00    	jne    2b5 <kmap_atomic_prot+0x1ce>
 233:	64 a1 00 00 00 00    	mov    %fs:0x0,%eax
 
An alternate suggestion (excuse the long line):

static inline int is_highmem(struct zone *zone)
{
#ifdef CONFIG_HIGHMEM
	int zone_off = (char *)zone - (char *)zone->zone_pgdat->node_zones;
	return zone_off == ZONE_HIGHMEM * sizeof(*zone) ||
		(zone_off == ZONE_MOVABLE * sizeof(*zone) && zone_movable_is_highmem());
#else
	return 0;
#endif
}

 207:	2b 80 8c 07 00 00    	sub    0x78c(%eax),%eax
 20d:	3d 00 10 00 00       	cmp    $0x1000,%eax
 212:	74 18                	je     22c <kmap_atomic_prot+0x145>
 214:	3d 00 18 00 00       	cmp    $0x1800,%eax
 219:	0f 85 8f 00 00 00    	jne    2ae <kmap_atomic_prot+0x1c7>
 21f:	83 3d 00 00 00 00 02 	cmpl   $0x2,0x0
 226:	0f 85 82 00 00 00    	jne    2ae <kmap_atomic_prot+0x1c7>
 22c:	64 a1 00 00 00 00    	mov    %fs:0x0,%eax

Cheers,

Harvey

[PATCH] remove sparse warning for mmzone.h

[Harvey Harrison]

include/linux/mmzone.h:640:22: warning: potentially expensive pointer subtraction

Calculate the offset into the node_zones array rather than the index
using casts to (char *) and comparing against the index * sizeof(struct zone).

On X86_32 this saves a sar, but code size increases by one byte per
is_highmem() use due to 32-bit cmps rather than 16 bit cmps.

Before:
 207:   2b 80 8c 07 00 00       sub    0x78c(%eax),%eax
 20d:   c1 f8 0b                sar    $0xb,%eax
 210:   83 f8 02                cmp    $0x2,%eax
 213:   74 16                   je     22b <kmap_atomic_prot+0x144>
 215:   83 f8 03                cmp    $0x3,%eax
 218:   0f 85 8f 00 00 00       jne    2ad <kmap_atomic_prot+0x1c6>
 21e:   83 3d 00 00 00 00 02    cmpl   $0x2,0x0
 225:   0f 85 82 00 00 00       jne    2ad <kmap_atomic_prot+0x1c6>
 22b:   64 a1 00 00 00 00       mov    %fs:0x0,%eax

After:
 207:   2b 80 8c 07 00 00       sub    0x78c(%eax),%eax
 20d:   3d 00 10 00 00          cmp    $0x1000,%eax
 212:   74 18                   je     22c <kmap_atomic_prot+0x145>
 214:   3d 00 18 00 00          cmp    $0x1800,%eax
 219:   0f 85 8f 00 00 00       jne    2ae <kmap_atomic_prot+0x1c7>
 21f:   83 3d 00 00 00 00 02    cmpl   $0x2,0x0
 226:   0f 85 82 00 00 00       jne    2ae <kmap_atomic_prot+0x1c7>
 22c:   64 a1 00 00 00 00       mov    %fs:0x0,%eax

Signed-off-by: Harvey Harrison <harvey.harrison@gmail.com>
---
 include/linux/mmzone.h |    7 ++++---
 1 files changed, 4 insertions(+), 3 deletions(-)

diff --git a/include/linux/mmzone.h b/include/linux/mmzone.h
index 8d8d197..3109a65 100644
--- a/include/linux/mmzone.h
+++ b/include/linux/mmzone.h
@@ -637,9 +637,10 @@ static inline int is_normal_idx(enum zone_type idx)
 static inline int is_highmem(struct zone *zone)
 {
 #ifdef CONFIG_HIGHMEM
-	int zone_idx = zone - zone->zone_pgdat->node_zones;
-	return zone_idx == ZONE_HIGHMEM ||
-		(zone_idx == ZONE_MOVABLE && zone_movable_is_highmem());
+	int zone_off = (char *)zone - (char *)zone->zone_pgdat->node_zones;
+	return zone_off == ZONE_HIGHMEM * sizeof(*zone) ||
+	       (zone_off == ZONE_MOVABLE * sizeof(*zone) &&
+	        zone_movable_is_highmem());
 #else
 	return 0;
 #endif
-- 
1.5.4.1.1278.gc75be

Re: [PATCH] fix sparse warning from include/linux/mmzone.h

[Harvey Harrison]

include/linux/mmzone.h:640:22: warning: potentially expensive pointer subtraction

Signed-off-by: Harvey Harrison <harvey.harrison@gmail.com>
---
Linus, something like the following?

 include/linux/mmzone.h |    7 ++++---
 1 files changed, 4 insertions(+), 3 deletions(-)

diff --git a/include/linux/mmzone.h b/include/linux/mmzone.h
index 8d8d197..7ed2922 100644
--- a/include/linux/mmzone.h
+++ b/include/linux/mmzone.h
@@ -637,9 +637,10 @@ static inline int is_normal_idx(enum zone_type idx)
 static inline int is_highmem(struct zone *zone)
 {
 #ifdef CONFIG_HIGHMEM
-	int zone_idx = zone - zone->zone_pgdat->node_zones;
-	return zone_idx == ZONE_HIGHMEM ||
-		(zone_idx == ZONE_MOVABLE && zone_movable_is_highmem());
+	struct zone *base = zone->zone_pgdat->node_zones;
+
+	return zone == base + ZONE_HIGHMEM ||
+		(zone == base + ZONE_MOVABLE && zone_movable_is_highmem());
 #else
 	return 0;
 #endif
-- 
1.5.4.1219.g65b9