[RFC][PATCH] introduce ptr_diff()

[RFC][PATCH] introduce ptr_diff()

[Namhyung Kim]

When I compiled allyesconfig'ed kernel with C=1, I got 1519 lines of
following message:

 include/linux/mm.h:599:16: warning: potentially expensive pointer subtraction

which is around 10% of total warnings. this was caused by page_to_pfn() macro
so I think it's worth to remove it by calculating pointer subtraction
manually.

ptr_diff() does subtraction of two pointers as if they were integer values
and divides it by the size of their base type. Currently it does not deal
with a difference alignment requirement than the size of base type, it
would be a trivial job.

Impact: remove a _lot_ of sparse warnings
Signed-off-by: Namhyung Kim <namhyung@gmail.com>
---

I have no idea where the right place is.
Please kindly point me to the place if here is not the one.
And any comments are greatly welcomed also.

Thanks.

 include/asm-generic/memory_model.h |   23 +++++++++++++++++++----
 1 files changed, 19 insertions(+), 4 deletions(-)

diff --git a/include/asm-generic/memory_model.h b/include/asm-generic/memory_model.h
index fb2d63f..ffec625 100644
--- a/include/asm-generic/memory_model.h
+++ b/include/asm-generic/memory_model.h
@@ -22,13 +22,28 @@
 
 #endif /* CONFIG_DISCONTIGMEM */
 
+#include <linux/log2.h>
+
+#define ptr_diff(p1, p2)					\
+({	long __diff;						\
+	unsigned long  __addr1 = (unsigned long) (p1);		\
+	unsigned long  __addr2 = (unsigned long) (p2);		\
+	unsigned __size = sizeof(typeof(*p1));			\
+								\
+	if (is_power_of_2(__size))				\
+		__diff = (__addr1 - __addr2) >> ilog2(__size);	\
+	else							\
+		__diff = (__addr1 - __addr2) / __size;		\
+	__diff;							\
+})
+
 /*
  * supports 3 memory models.
  */
 #if defined(CONFIG_FLATMEM)
 
 #define __pfn_to_page(pfn)	(mem_map + ((pfn) - ARCH_PFN_OFFSET))
-#define __page_to_pfn(page)	((unsigned long)((page) - mem_map) + \
+#define __page_to_pfn(page)	((unsigned long)(ptr_diff((page), mem_map)) + \
 				 ARCH_PFN_OFFSET)
 #elif defined(CONFIG_DISCONTIGMEM)
 
@@ -41,7 +56,7 @@
 #define __page_to_pfn(pg)						\
 ({	struct page *__pg = (pg);					\
 	struct pglist_data *__pgdat = NODE_DATA(page_to_nid(__pg));	\
-	(unsigned long)(__pg - __pgdat->node_mem_map) +			\
+	(unsigned long)(ptr_diff(__pg, __pgdat->node_mem_map)) +	\
 	 __pgdat->node_start_pfn;					\
 })
 
@@ -49,7 +64,7 @@
 
 /* memmap is virtually contiguous.  */
 #define __pfn_to_page(pfn)	(vmemmap + (pfn))
-#define __page_to_pfn(page)	(unsigned long)((page) - vmemmap)
+#define __page_to_pfn(page)	(unsigned long)(ptr_diff((page), vmemmap))
 
 #elif defined(CONFIG_SPARSEMEM)
 /*
@@ -59,7 +74,7 @@
 #define __page_to_pfn(pg)					\
 ({	struct page *__pg = (pg);				\
 	int __sec = page_to_section(__pg);			\
-	(unsigned long)(__pg - __section_mem_map_addr(__nr_to_section(__sec)));	\
+	(unsigned long)(ptr_diff(__pg,  __section_mem_map_addr(__nr_to_section(__sec)))); \
 })
 
 #define __pfn_to_page(pfn)				\
-- 
1.7.0.4

Re: [RFC][PATCH] introduce ptr_diff()

[Bernd Petrovitsch]

On Don, 2010-08-19 at 20:37 +0900, Namhyung Kim wrote:
> When I compiled allyesconfig'ed kernel with C=1, I got 1519 lines of
> following message:
> 
>  include/linux/mm.h:599:16: warning: potentially expensive pointer subtraction
> 
> which is around 10% of total warnings. this was caused by page_to_pfn() macro
> so I think it's worth to remove it by calculating pointer subtraction
> manually.
> 
> ptr_diff() does subtraction of two pointers as if they were integer values
> and divides it by the size of their base type. Currently it does not deal
> with a difference alignment requirement than the size of base type, it
> would be a trivial job.
> 
> Impact: remove a _lot_ of sparse warnings
> Signed-off-by: Namhyung Kim <namhyung@gmail.com>
> ---
> 
> I have no idea where the right place is.
> Please kindly point me to the place if here is not the one.
> And any comments are greatly welcomed also.
> 
> Thanks.
> 
>  include/asm-generic/memory_model.h |   23 +++++++++++++++++++----
>  1 files changed, 19 insertions(+), 4 deletions(-)
> 
> diff --git a/include/asm-generic/memory_model.h b/include/asm-generic/memory_model.h
> index fb2d63f..ffec625 100644
> --- a/include/asm-generic/memory_model.h
> +++ b/include/asm-generic/memory_model.h
> @@ -22,13 +22,28 @@
>  
>  #endif /* CONFIG_DISCONTIGMEM */
>  
> +#include <linux/log2.h>
> +
> +#define ptr_diff(p1, p2)					\
> +({	long __diff;						\
> +	unsigned long  __addr1 = (unsigned long) (p1);		\
> +	unsigned long  __addr2 = (unsigned long) (p2);		\
> +	unsigned __size = sizeof(typeof(*p1));			\
The typeof() is actually redundant here.
> +								\
> +	if (is_power_of_2(__size))				\
> +		__diff = (__addr1 - __addr2) >> ilog2(__size);	\
> +	else							\
> +		__diff = (__addr1 - __addr2) / __size;		\
> +	__diff;							\
> +})
> +

IMHO this kills gcc's type compatibility checks on p1 and p2 (even if
they are suboptimal).
There is the "__same_type" macro in compiler.h for this or the "else"
branch uses plain C
	__diff = p1 - p2;
to keep them (which probably also keeps sparse's warnings).

Actually one would assume that gcc internally just does the above as the
size of the type is statically known (and sparse could be improved to
not warn where sizeof(*p1) is a power of 2).

	Bernd
-- 
mobile: +43 664 4416156              http://www.sysprog.at/
    Linux Software Development, Consulting and Services

Re: [RFC][PATCH] introduce ptr_diff()

[David Howells]

Namhyung Kim <namhyung@gmail.com> wrote:

> +	if (is_power_of_2(__size))				\
> +		__diff = (__addr1 - __addr2) >> ilog2(__size);	\
> +	else							\
> +		__diff = (__addr1 - __addr2) / __size;		\

You shouldn't need to do this.  The compiler's optimiser should switch a
divide to a shift for a power-of-2 divisor.

David

Re: [RFC][PATCH] introduce ptr_diff()

[Andi Kleen]

Namhyung Kim <namhyung@gmail.com> writes:

> When I compiled allyesconfig'ed kernel with C=1, I got 1519 lines of
> following message:
>
>  include/linux/mm.h:599:16: warning: potentially expensive pointer subtraction
>
> which is around 10% of total warnings. this was caused by page_to_pfn() macro
> so I think it's worth to remove it by calculating pointer subtraction
> manually.

IMHO it would be better to simply disable the warning in sparse instead
of uglying the code just to work around sparse bogosity. It doesnt' seem
to make much sense. A subtraction followed by a shift is not expensive.

-Andi

-- 
ak@linux.intel.com -- Speaking for myself only.

Re: [RFC][PATCH] introduce ptr_diff()

[Matthew Wilcox]

On Thu, Aug 19, 2010 at 02:23:09PM +0200, Andi Kleen wrote:
> IMHO it would be better to simply disable the warning in sparse instead
> of uglying the code just to work around sparse bogosity. It doesnt' seem
> to make much sense. A subtraction followed by a shift is not expensive.

What makes you think it's a shift?  struct page isn't necessarily a
power of two in size.  The original poster said "allyesconfig" which is
going to add in KMEMCHECK and WANT_PAGE_DEBUG_FLAGS.  I think that makes
it 76 bytes on x86-32, so sparse is right to warn.

-- 
Matthew Wilcox				Intel Open Source Technology Centre
"Bill, look, we understand that you're interested in selling us this
operating system, but compare it to ours.  We can't possibly take such
a retrograde step."

Re: [RFC][PATCH] introduce ptr_diff()

[Bernd Petrovitsch]

On Don, 2010-08-19 at 14:23 +0200, Andi Kleen wrote:
> Namhyung Kim <namhyung@gmail.com> writes:
> 
> > When I compiled allyesconfig'ed kernel with C=1, I got 1519 lines of
> > following message:
> >
> >  include/linux/mm.h:599:16: warning: potentially expensive pointer subtraction
> >
> > which is around 10% of total warnings. this was caused by page_to_pfn() macro
> > so I think it's worth to remove it by calculating pointer subtraction
> > manually.
> 
> IMHO it would be better to simply disable the warning in sparse instead
> of uglying the code just to work around sparse bogosity. It doesnt' seem
> to make much sense. A subtraction followed by a shift is not expensive.

The code above is IMHO actually (the line with "return" in)
----  snip  ----
static __always_inline void *lowmem_page_address(struct page *page)
{
	return __va(PFN_PHYS(page_to_pfn(page)));
}
----  snip  ----
If so, the warning seems valid as sizeof(struct page) is probably not
(always) a power of 2. On a native build on x86_64 it is 56 bytes
hereover.
Hmm ....

	Bernd
-- 
mobile: +43 664 4416156              http://www.sysprog.at/
    Linux Software Development, Consulting and Services

Re: [RFC][PATCH] introduce ptr_diff()

[Bernd Petrovitsch]

On Don, 2010-08-19 at 14:23 +0200, Andi Kleen wrote:
> Namhyung Kim <namhyung@gmail.com> writes:
> 
> > When I compiled allyesconfig'ed kernel with C=1, I got 1519 lines of
> > following message:
> >
> >  include/linux/mm.h:599:16: warning: potentially expensive pointer subtraction
> >
> > which is around 10% of total warnings. this was caused by page_to_pfn() macro
> > so I think it's worth to remove it by calculating pointer subtraction
> > manually.
> 
> IMHO it would be better to simply disable the warning in sparse instead
> of uglying the code just to work around sparse bogosity. It doesnt' seem
> to make much sense. A subtraction followed by a shift is not expensive.

The code above is IMHO actually (the line with "return" in)
----  snip  ----
static __always_inline void *lowmem_page_address(struct page *page)
{
	return __va(PFN_PHYS(page_to_pfn(page)));
}
----  snip  ----
If so, the warning seems valid as sizeof(struct page) is probably not
(always) a power of 2. On a native build on x86_64 it is 56 bytes
hereover.
Hmm ....

	Bernd
-- 
mobile: +43 664 4416156              http://www.sysprog.at/
    Linux Software Development, Consulting and Services

Re: [RFC][PATCH] introduce ptr_diff()

[Andi Kleen]

On Thu, Aug 19, 2010 at 06:40:17AM -0600, Matthew Wilcox wrote:
> On Thu, Aug 19, 2010 at 02:23:09PM +0200, Andi Kleen wrote:
> > IMHO it would be better to simply disable the warning in sparse instead
> > of uglying the code just to work around sparse bogosity. It doesnt' seem
> > to make much sense. A subtraction followed by a shift is not expensive.
> 
> What makes you think it's a shift?  struct page isn't necessarily a
> power of two in size.  The original poster said "allyesconfig" which is
> going to add in KMEMCHECK and WANT_PAGE_DEBUG_FLAGS.  I think that makes
> it 76 bytes on x86-32, so sparse is right to warn.

These can be still implemented cheaply. Small constants generally are
The only thing that would be really expensive is division by unknown number.

-Andi

-- 
ak@linux.intel.com -- Speaking for myself only.

Re: [RFC][PATCH] introduce ptr_diff()

[Andi Kleen]

On Thu, Aug 19, 2010 at 06:40:17AM -0600, Matthew Wilcox wrote:
> On Thu, Aug 19, 2010 at 02:23:09PM +0200, Andi Kleen wrote:
> > IMHO it would be better to simply disable the warning in sparse instead
> > of uglying the code just to work around sparse bogosity. It doesnt' seem
> > to make much sense. A subtraction followed by a shift is not expensive.
> 
> What makes you think it's a shift?  struct page isn't necessarily a
> power of two in size.  The original poster said "allyesconfig" which is
> going to add in KMEMCHECK and WANT_PAGE_DEBUG_FLAGS.  I think that makes
> it 76 bytes on x86-32, so sparse is right to warn.

These can be still implemented cheaply. Small constants generally are
The only thing that would be really expensive is division by unknown number.

-Andi

-- 
ak@linux.intel.com -- Speaking for myself only.

Re: [RFC][PATCH] introduce ptr_diff()

[Andi Kleen]

> If so, the warning seems valid as sizeof(struct page) is probably not
> (always) a power of 2. On a native build on x86_64 it is 56 bytes
> hereover.
> Hmm ....


gcc just generats a mull with inverted value. mull is cheap on any
reasonable CPU.  Please fix sparse.

-andi

Re: [RFC][PATCH] introduce ptr_diff()

[Bernd Petrovitsch]

On Don, 2010-08-19 at 14:59 +0200, Andi Kleen wrote:
> > If so, the warning seems valid as sizeof(struct page) is probably not
> > (always) a power of 2. On a native build on x86_64 it is 56 bytes
> > hereover.
> > Hmm ....
> 
> gcc just generats a mull with inverted value. mull is cheap on any
> reasonable CPU.  Please fix sparse.

Not that I really know the code of sparse but what would be an
acceptable condition (except plain simply disabling/removing the warning
as such)?
No warning if it's a constant value (read: explicit or sizeof())?

	Bernd
-- 
Bernd Petrovitsch                  Email : bernd@petrovitsch.priv.at
                     LUGA : http://www.luga.at

Re: [RFC][PATCH] introduce ptr_diff()

[Andi Kleen]

On Thu, Aug 19, 2010 at 03:05:13PM +0200, Bernd Petrovitsch wrote:
> On Don, 2010-08-19 at 14:59 +0200, Andi Kleen wrote:
> > > If so, the warning seems valid as sizeof(struct page) is probably not
> > > (always) a power of 2. On a native build on x86_64 it is 56 bytes
> > > hereover.
> > > Hmm ....
> > 
> > gcc just generats a mull with inverted value. mull is cheap on any
> > reasonable CPU.  Please fix sparse.
> 
> Not that I really know the code of sparse but what would be an
> acceptable condition (except plain simply disabling/removing the warning
> as such)?

I think acceptable would be to warn if the type is variable sized
(although I think gcc likely would error out in this case anyways)

-Andi
-- 
ak@linux.intel.com -- Speaking for myself only.

Re: [RFC][PATCH] introduce ptr_diff()

[Namhyung Kim]

2010-08-19 (목), 14:23 +0200, Andi Kleen:
> IMHO it would be better to simply disable the warning in sparse instead
> of uglying the code just to work around sparse bogosity. It doesnt' seem
> to make much sense. A subtraction followed by a shift is not expensive.
> 
> -Andi
> 

I'm curious who turns on that switch. -Wptr-subtraction-blows is turned
off by default, I didn't use CF variable at build time and I could not
find any reference of it in the source tree. Hmm..

-- 
Regards,
Namhyung Kim

Re: [RFC][PATCH] introduce ptr_diff()

[Bernd Petrovitsch]

On Fre, 2010-08-20 at 00:53 +0900, Namhyung Kim wrote:
> 2010-08-19 (목), 14:23 +0200, Andi Kleen:
> > IMHO it would be better to simply disable the warning in sparse instead
> > of uglying the code just to work around sparse bogosity. It doesnt' seem
> > to make much sense. A subtraction followed by a shift is not expensive.
[...]
> I'm curious who turns on that switch. -Wptr-subtraction-blows is turned
> off by default, I didn't use CF variable at build time and I could not
> find any reference of it in the source tree. Hmm..

sparse also gets gcc's parameters which include (usually) "-Wall". And
this activates it.
Adding -Wno-ptr-subtraction-blows to CHECKFLAGS should do the trick.

	Bernd
-- 
mobile: +43 664 4416156              http://www.sysprog.at/
    Linux Software Development, Consulting and Services

Re: [RFC][PATCH] introduce ptr_diff()

[Namhyung Kim]

2010-08-19 (목), 18:04 +0200, Bernd Petrovitsch:
> sparse also gets gcc's parameters which include (usually) "-Wall". And
> this activates it.
> Adding -Wno-ptr-subtraction-blows to CHECKFLAGS should do the trick.
> 
> 	Bernd

I see. thanks for the info. :-)

-- 
Regards,
Namhyung Kim

Re: [RFC][PATCH] introduce ptr_diff()

[Al Viro]

On Thu, Aug 19, 2010 at 02:23:09PM +0200, Andi Kleen wrote:
> Namhyung Kim <namhyung@gmail.com> writes:
> 
> > When I compiled allyesconfig'ed kernel with C=1, I got 1519 lines of
> > following message:
> >
> >  include/linux/mm.h:599:16: warning: potentially expensive pointer subtraction
> >
> > which is around 10% of total warnings. this was caused by page_to_pfn() macro
> > so I think it's worth to remove it by calculating pointer subtraction
> > manually.
> 
> IMHO it would be better to simply disable the warning in sparse instead
> of uglying the code just to work around sparse bogosity. It doesnt' seem
> to make much sense. A subtraction followed by a shift is not expensive.

"Bogosity" in question is quite real and proposed "fix" actually makes the
things even worse.  At least gcc bothers to optimize the division in there...

Basically, sparse warns about pointer subtractions that divide by constants
that are not powers of two.  Which _does_ have non-trivial price, even with
optimizations done by gcc.

Posted patch is complete crap, since all it does is
	a) confuse sparse into not noticing the operation
	b) confuse gcc into not trying to optimize the thing, which actually
makes the situation *worse*.

Sheesh...

Re: [RFC][PATCH] introduce ptr_diff()

[Al Viro]

On Thu, Aug 19, 2010 at 02:59:57PM +0200, Andi Kleen wrote:
> > If so, the warning seems valid as sizeof(struct page) is probably not
> > (always) a power of 2. On a native build on x86_64 it is 56 bytes
> > hereover.
> > Hmm ....
> 
> 
> gcc just generats a mull with inverted value. mull is cheap on any
> reasonable CPU.

Depends on gcc version.

> Please fix sparse.

Frankly, I'd rather stop crapping -Wall into its arguments; there's
a reason why that check is optional and it's *not* defaulting to
on in sparse.

Re: [RFC][PATCH] introduce ptr_diff()

[Matthew Wilcox]

On Fri, Aug 20, 2010 at 01:07:37PM +0100, Al Viro wrote:
> On Thu, Aug 19, 2010 at 02:23:09PM +0200, Andi Kleen wrote:
> > IMHO it would be better to simply disable the warning in sparse instead
> > of uglying the code just to work around sparse bogosity. It doesnt' seem
> > to make much sense. A subtraction followed by a shift is not expensive.
> 
> "Bogosity" in question is quite real and proposed "fix" actually makes the
> things even worse.  At least gcc bothers to optimize the division in there...
> 
> Basically, sparse warns about pointer subtractions that divide by constants
> that are not powers of two.  Which _does_ have non-trivial price, even with
> optimizations done by gcc.

I'm not sure the price is so high.  I googled around and came across
http://mdfs.net/Docs/Comp/ARM/Cookbook/cook3 (section 3.3).  Dividing by
2^n, (2^n + 2^m) or (2^n - 2^m) can be done using a small series of adds
and subtractions (important on ARM as it had no divide instruction at
the time).  Most structures are going to be of one of these sizes ...
and in particular, struct page is 56 bytes in my config, which is 64 - 8.
Maybe sparse needs to be taught that dividing by 2^n [+-] 2^m is cheap
enough to not warn about.

-- 
Matthew Wilcox				Intel Open Source Technology Centre
"Bill, look, we understand that you're interested in selling us this
operating system, but compare it to ours.  We can't possibly take such
a retrograde step."

Re: [RFC][PATCH] introduce ptr_diff()

[Andi Kleen]

> I'm not sure the price is so high.  I googled around and came across
> http://mdfs.net/Docs/Comp/ARM/Cookbook/cook3 (section 3.3).  Dividing by
> 2^n, (2^n + 2^m) or (2^n - 2^m) can be done using a small series of adds
> and subtractions (important on ARM as it had no divide instruction at
> the time).  Most structures are going to be of one of these sizes ...
> and in particular, struct page is 56 bytes in my config, which is 64 - 8.
> Maybe sparse needs to be taught that dividing by 2^n [+-] 2^m is cheap
> enough to not warn about.

Usually you can just use x/n = x*(1/n) and generate *(1/n) with 1/n 
being computed at compile time. Multiplications are fast in hardware.

gcc only does that when -Os is not set though (friends don't let friends
compile with -Os...)

-Andi

-- 
ak@linux.intel.com -- Speaking for myself only.