Skip to contentSkip to conversation

fix sparse warning from include/linux/mmzone.h

PATCH In review Harvey Harrison 4 participants 9 messages Feb 7, 2008 – Feb 13, 2008

Subsystems (2)
lore
Share & tools
lore
#0 lore raw

PATCH 1/1 fix sparse warning from include/linux/mmzone.h

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.

---
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(-)
include/linux/mmzone.h +6 -3
index 8d8d197..cb07758 100644
@@ -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
Signature · 1 line
1.5.4.1219.g65b9
maintainer
#1 lore raw
Quoted 30 lines · On Thu, 07 Feb 2008 12:52:23 -0800 Harvey Harrison <[email protected]>…

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.

---
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(-)
include/linux/mmzone.h +0 -2
index 8d8d197..cb07758 100644
@@ -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 ||

include/linux/mmzone.h static inline int is_normal_idx(enum zone_type idx) · line 648

Quoted 10 lines
include/linux/mmzone.h +6 -1
-		(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.

#2 lore raw
Quoted 6 lines · Andrew Morton
Quoted 6 lines

#ifdef CONFIG_HIGHMEM

include/linux/mmzone.h +2 -3
-	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);
Quoted 8 lines

include/linux/mmzone.h static inline int is_normal_idx(enum zone_type idx) · line 645

Quoted 4 lines
include/linux/mmzone.h +4 -0
+
+	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

#3 lore raw
Quoted 17 lines · Linus Torvalds
Quoted 6 lines · Andrew Morton
Quoted 6 lines

#ifdef CONFIG_HIGHMEM

include/linux/mmzone.h +2 -3
-	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);
Quoted 8 lines

include/linux/mmzone.h static inline int is_normal_idx(enum zone_type idx) · line 645

Quoted 4 lines
include/linux/mmzone.h +4 -0
+
+	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.

Quoted 1 line

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

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

Quoted 7 lines

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

#4 lore raw
In reply to Linus Torvalds
Quoted 10 lines · Linus Torvalds

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

#5 lore raw
In reply to Linus Torvalds
Quoted 7 lines · Linus Torvalds

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

#8 lore raw
In reply to Linus Torvalds

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

---
Linus, something like the following?

 include/linux/mmzone.h |    7 ++++---
 1 files changed, 4 insertions(+), 3 deletions(-)
include/linux/mmzone.h +4 -3
index 8d8d197..7ed2922 100644
@@ -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
Signature · 1 line
1.5.4.1219.g65b9
#6 lore raw
In reply to Linus Torvalds

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

#7 lore raw

PATCH 1/1 remove sparse warning for mmzone.h

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
---
 include/linux/mmzone.h |    7 ++++---
 1 files changed, 4 insertions(+), 3 deletions(-)
include/linux/mmzone.h +4 -3
index 8d8d197..3109a65 100644
@@ -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
Signature · 1 line
1.5.4.1.1278.gc75be