[RFC][PATCH 0/3] gcc work-around and math128

[RFC][PATCH 0/3] gcc work-around and math128

[Peter Zijlstra]

Hi all,

The SCHED_DEADLINE review resulted in the following three patches;

The first is a cleanup of various copies of the same GCC loop optimization
work-around. I don't think this patch is too controversial, at worst I've
picked a wrong name, but I wanted to get it out there in case people
know more sites.

The second two implement a few u128 operations so we can do 128bit math.. I
know a few people will die a little inside, but having nanosecond granularity
time accounting leads to very big numbers very quickly and when you need to
multiply them 64bit really isn't that much.

So far its just mult, add and cmp for u128, no divisions quite yet. I realize
that on 32bit archs mult_u128 will result in like 8 multiplication
instructions that's still nowhere near the most expensive thing ever.

Also, I suck at gcc inline asm, so patch 3/3 is very likely completely wrong,
in any case none of the patches has even been near a compiler and this really
is just an RFC to probe if we want to go here at all.

[RFC][PATCH 1/3] kernel,sched,time: Clean up gcc work-arounds

[Peter Zijlstra]

[-- Attachment #1: kernel-vs-gcc-while.patch --]
[-- Type: text/plain, Size: 3383 bytes --]

We've grown various copies of a particular gcc work-around,
consolidate them into one and add a larger comment.

Cc: Ingo Molnar <mingo@kernel.org>
Cc: Thomas Gleixner <tglx@linutronix.de>
Cc: Andrew Morton <akpm@linux-foundation.org>
Cc: Linus Torvalds <torvalds@linux-foundation.org>
Signed-off-by: Peter Zijlstra <a.p.zijlstra@chello.nl>
---
 include/linux/compiler.h |   12 ++++++++++++
 include/linux/math64.h   |    4 +---
 kernel/sched/core.c      |    8 ++------
 kernel/sched/fair.c      |    8 ++------
 kernel/time.c            |   11 ++++-------
 5 files changed, 21 insertions(+), 22 deletions(-)

--- a/include/linux/compiler.h
+++ b/include/linux/compiler.h
@@ -310,4 +310,16 @@ void ftrace_likely_update(struct ftrace_
  */
 #define ACCESS_ONCE(x) (*(volatile typeof(x) *)&(x))
 
+/*
+ * Avoid gcc loop optimization by clobbering a variable, forcing a reload
+ * and invalidating the optimization.
+ *
+ * The optimization in question transforms various loops into divisions/modulo
+ * operations, this is a problem when either the resulting operation generates
+ * unimplemented libgcc functions (u64 divisions for example) or the loop is
+ * known not to contain a lot of iterations and the division is in fact more
+ * expensive.
+ */
+#define __gcc_dont_optimize_loop(var) asm("" "+rm" (var))
+
 #endif /* __LINUX_COMPILER_H */
--- a/include/linux/math64.h
+++ b/include/linux/math64.h
@@ -105,9 +105,7 @@ __iter_div_u64_rem(u64 dividend, u32 div
 	u32 ret = 0;
 
 	while (dividend >= divisor) {
-		/* The following asm() prevents the compiler from
-		   optimising this loop into a modulo operation.  */
-		asm("" : "+rm"(dividend));
+		__gcc_dont_optimize_loop(dividend);
 
 		dividend -= divisor;
 		ret++;
--- a/kernel/sched/core.c
+++ b/kernel/sched/core.c
@@ -628,12 +628,8 @@ void sched_avg_update(struct rq *rq)
 	s64 period = sched_avg_period();
 
 	while ((s64)(rq->clock - rq->age_stamp) > period) {
-		/*
-		 * Inline assembly required to prevent the compiler
-		 * optimising this loop into a divmod call.
-		 * See __iter_div_u64_rem() for another example of this.
-		 */
-		asm("" : "+rm" (rq->age_stamp));
+		__gcc_dont_optimize_loop(rq->age_stamp);
+
 		rq->age_stamp += period;
 		rq->rt_avg /= 2;
 	}
--- a/kernel/sched/fair.c
+++ b/kernel/sched/fair.c
@@ -853,12 +853,8 @@ static void update_cfs_load(struct cfs_r
 		update_cfs_rq_load_contribution(cfs_rq, global_update);
 
 	while (cfs_rq->load_period > period) {
-		/*
-		 * Inline assembly required to prevent the compiler
-		 * optimising this loop into a divmod call.
-		 * See __iter_div_u64_rem() for another example of this.
-		 */
-		asm("" : "+rm" (cfs_rq->load_period));
+		__gcc_dont_optimize_loop(cfs_rq->load_period);
+
 		cfs_rq->load_period /= 2;
 		cfs_rq->load_avg /= 2;
 	}
--- a/kernel/time.c
+++ b/kernel/time.c
@@ -349,17 +349,14 @@ EXPORT_SYMBOL(mktime);
 void set_normalized_timespec(struct timespec *ts, time_t sec, s64 nsec)
 {
 	while (nsec >= NSEC_PER_SEC) {
-		/*
-		 * The following asm() prevents the compiler from
-		 * optimising this loop into a modulo operation. See
-		 * also __iter_div_u64_rem() in include/linux/time.h
-		 */
-		asm("" : "+rm"(nsec));
+		__gcc_dont_optimize_loop(nsec);
+
 		nsec -= NSEC_PER_SEC;
 		++sec;
 	}
 	while (nsec < 0) {
-		asm("" : "+rm"(nsec));
+		__gcc_dont_optimize_loop(nsec);
+
 		nsec += NSEC_PER_SEC;
 		--sec;
 	}

[RFC][PATCH 2/3] math128: Introduce {mult,add,cmp}_u128

[Peter Zijlstra]

[-- Attachment #1: math128.patch --]
[-- Type: text/plain, Size: 7794 bytes --]

Grow rudimentary u128 support without relying on gcc/libgcc.

Cc: Ingo Molnar <mingo@kernel.org>
Cc: Thomas Gleixner <tglx@linutronix.de>
Cc: Andrew Morton <akpm@linux-foundation.org>
Cc: Linus Torvalds <torvalds@linux-foundation.org>
Signed-off-by: Peter Zijlstra <a.p.zijlstra@chello.nl>
---
 arch/alpha/include/asm/math128.h      |    4 ++
 arch/arm/include/asm/math128.h        |    4 ++
 arch/avr32/include/asm/math128.h      |    4 ++
 arch/blackfin/include/asm/math128.h   |    4 ++
 arch/c6x/include/asm/math128.h        |    4 ++
 arch/cris/include/asm/math128.h       |    4 ++
 arch/frv/include/asm/math128.h        |    4 ++
 arch/h8300/include/asm/math128.h      |    4 ++
 arch/hexagon/include/asm/math128.h    |    4 ++
 arch/ia64/include/asm/math128.h       |    4 ++
 arch/m32r/include/asm/math128.h       |    4 ++
 arch/m68k/include/asm/math128.h       |    4 ++
 arch/microblaze/include/asm/math128.h |    4 ++
 arch/mips/include/asm/math128.h       |    4 ++
 arch/mn10300/include/asm/math128.h    |    4 ++
 arch/openrisc/include/asm/math128.h   |    4 ++
 arch/parisc/include/asm/math128.h     |    4 ++
 arch/powerpc/include/asm/math128.h    |    4 ++
 arch/s390/include/asm/math128.h       |    4 ++
 arch/score/include/asm/math128.h      |    4 ++
 arch/sh/include/asm/math128.h         |    4 ++
 arch/sparc/include/asm/math128.h      |    4 ++
 arch/tile/include/asm/math128.h       |    4 ++
 arch/um/include/asm/math128.h         |    4 ++
 arch/unicore32/include/asm/math128.h  |    4 ++
 arch/x86/include/asm/math128.h        |    4 ++
 arch/xtensa/include/asm/math128.h     |    4 ++
 include/linux/math128.h               |   47 ++++++++++++++++++++++++++++++++++
 lib/Makefile                          |    2 -
 lib/math128.c                         |   42 ++++++++++++++++++++++++++++++
 30 files changed, 198 insertions(+), 1 deletion(-)

--- /dev/null
+++ b/arch/alpha/include/asm/math128.h
@@ -0,0 +1,4 @@
+#ifndef _ASM_MATH128_H
+#define _ASM_MATH128_H
+
+#endif /* _ASM_MATH128_H */
--- /dev/null
+++ b/arch/arm/include/asm/math128.h
@@ -0,0 +1,4 @@
+#ifndef _ASM_MATH128_H
+#define _ASM_MATH128_H
+
+#endif /* _ASM_MATH128_H */
--- /dev/null
+++ b/arch/avr32/include/asm/math128.h
@@ -0,0 +1,4 @@
+#ifndef _ASM_MATH128_H
+#define _ASM_MATH128_H
+
+#endif /* _ASM_MATH128_H */
--- /dev/null
+++ b/arch/blackfin/include/asm/math128.h
@@ -0,0 +1,4 @@
+#ifndef _ASM_MATH128_H
+#define _ASM_MATH128_H
+
+#endif /* _ASM_MATH128_H */
--- /dev/null
+++ b/arch/c6x/include/asm/math128.h
@@ -0,0 +1,4 @@
+#ifndef _ASM_MATH128_H
+#define _ASM_MATH128_H
+
+#endif /* _ASM_MATH128_H */
--- /dev/null
+++ b/arch/cris/include/asm/math128.h
@@ -0,0 +1,4 @@
+#ifndef _ASM_MATH128_H
+#define _ASM_MATH128_H
+
+#endif /* _ASM_MATH128_H */
--- /dev/null
+++ b/arch/frv/include/asm/math128.h
@@ -0,0 +1,4 @@
+#ifndef _ASM_MATH128_H
+#define _ASM_MATH128_H
+
+#endif /* _ASM_MATH128_H */
--- /dev/null
+++ b/arch/h8300/include/asm/math128.h
@@ -0,0 +1,4 @@
+#ifndef _ASM_MATH128_H
+#define _ASM_MATH128_H
+
+#endif /* _ASM_MATH128_H */
--- /dev/null
+++ b/arch/hexagon/include/asm/math128.h
@@ -0,0 +1,4 @@
+#ifndef _ASM_MATH128_H
+#define _ASM_MATH128_H
+
+#endif /* _ASM_MATH128_H */
--- /dev/null
+++ b/arch/ia64/include/asm/math128.h
@@ -0,0 +1,4 @@
+#ifndef _ASM_MATH128_H
+#define _ASM_MATH128_H
+
+#endif /* _ASM_MATH128_H */
--- /dev/null
+++ b/arch/m32r/include/asm/math128.h
@@ -0,0 +1,4 @@
+#ifndef _ASM_MATH128_H
+#define _ASM_MATH128_H
+
+#endif /* _ASM_MATH128_H */
--- /dev/null
+++ b/arch/m68k/include/asm/math128.h
@@ -0,0 +1,4 @@
+#ifndef _ASM_MATH128_H
+#define _ASM_MATH128_H
+
+#endif /* _ASM_MATH128_H */
--- /dev/null
+++ b/arch/microblaze/include/asm/math128.h
@@ -0,0 +1,4 @@
+#ifndef _ASM_MATH128_H
+#define _ASM_MATH128_H
+
+#endif /* _ASM_MATH128_H */
--- /dev/null
+++ b/arch/mips/include/asm/math128.h
@@ -0,0 +1,4 @@
+#ifndef _ASM_MATH128_H
+#define _ASM_MATH128_H
+
+#endif /* _ASM_MATH128_H */
--- /dev/null
+++ b/arch/mn10300/include/asm/math128.h
@@ -0,0 +1,4 @@
+#ifndef _ASM_MATH128_H
+#define _ASM_MATH128_H
+
+#endif /* _ASM_MATH128_H */
--- /dev/null
+++ b/arch/openrisc/include/asm/math128.h
@@ -0,0 +1,4 @@
+#ifndef _ASM_MATH128_H
+#define _ASM_MATH128_H
+
+#endif /* _ASM_MATH128_H */
--- /dev/null
+++ b/arch/parisc/include/asm/math128.h
@@ -0,0 +1,4 @@
+#ifndef _ASM_MATH128_H
+#define _ASM_MATH128_H
+
+#endif /* _ASM_MATH128_H */
--- /dev/null
+++ b/arch/powerpc/include/asm/math128.h
@@ -0,0 +1,4 @@
+#ifndef _ASM_MATH128_H
+#define _ASM_MATH128_H
+
+#endif /* _ASM_MATH128_H */
--- /dev/null
+++ b/arch/s390/include/asm/math128.h
@@ -0,0 +1,4 @@
+#ifndef _ASM_MATH128_H
+#define _ASM_MATH128_H
+
+#endif /* _ASM_MATH128_H */
--- /dev/null
+++ b/arch/score/include/asm/math128.h
@@ -0,0 +1,4 @@
+#ifndef _ASM_MATH128_H
+#define _ASM_MATH128_H
+
+#endif /* _ASM_MATH128_H */
--- /dev/null
+++ b/arch/sh/include/asm/math128.h
@@ -0,0 +1,4 @@
+#ifndef _ASM_MATH128_H
+#define _ASM_MATH128_H
+
+#endif /* _ASM_MATH128_H */
--- /dev/null
+++ b/arch/sparc/include/asm/math128.h
@@ -0,0 +1,4 @@
+#ifndef _ASM_MATH128_H
+#define _ASM_MATH128_H
+
+#endif /* _ASM_MATH128_H */
--- /dev/null
+++ b/arch/tile/include/asm/math128.h
@@ -0,0 +1,4 @@
+#ifndef _ASM_MATH128_H
+#define _ASM_MATH128_H
+
+#endif /* _ASM_MATH128_H */
--- /dev/null
+++ b/arch/um/include/asm/math128.h
@@ -0,0 +1,4 @@
+#ifndef _ASM_MATH128_H
+#define _ASM_MATH128_H
+
+#endif /* _ASM_MATH128_H */
--- /dev/null
+++ b/arch/unicore32/include/asm/math128.h
@@ -0,0 +1,4 @@
+#ifndef _ASM_MATH128_H
+#define _ASM_MATH128_H
+
+#endif /* _ASM_MATH128_H */
--- /dev/null
+++ b/arch/x86/include/asm/math128.h
@@ -0,0 +1,4 @@
+#ifndef _ASM_MATH128_H
+#define _ASM_MATH128_H
+
+#endif /* _ASM_MATH128_H */
--- /dev/null
+++ b/arch/xtensa/include/asm/math128.h
@@ -0,0 +1,4 @@
+#ifndef _ASM_MATH128_H
+#define _ASM_MATH128_H
+
+#endif /* _ASM_MATH128_H */
--- /dev/null
+++ b/include/linux/math128.h
@@ -0,0 +1,47 @@
+#ifndef _LINUX_MATH128_H
+#define _LINUX_MATH128_H
+
+#include <linux/types.h>
+
+typedef struct {
+	u64 hi, lo;
+} u128;
+
+#include <asm/math128.h>
+
+#ifndef add_u128
+static inline u128 add_u128(u128 a, u128 b)
+{
+	u128 res;
+
+	res.hi = a.hi + b.hi;
+	res.lo = a.lo + b.lo;
+
+	if (res.lo < a.lo || res.lo < b.lo)
+		res.hi++;
+
+	return res;
+}
+#endif /* add_u128 */
+
+#ifndef mult_u128
+extern int u128 mult_u128(u64 a, u64 b);
+#endif
+
+#ifndef cmp_u128
+static inline int cmp_u128(u128 a, u128 b)
+{
+	if (a.hi > b.hi)
+		return 1;
+	if (a.hi < b.hi)
+		return -1;
+	if (a.lo > b.lo)
+		return 1;
+	if (a.lo < b.lo)
+		return -1;
+
+	return 0;
+}
+#endif /* cmp_u128 */
+
+#endif /* _LINUX_MATH128_H */
--- a/lib/Makefile
+++ b/lib/Makefile
@@ -12,7 +12,7 @@ lib-y := ctype.o string.o vsprintf.o cmd
 	 idr.o int_sqrt.o extable.o prio_tree.o \
 	 sha1.o md5.o irq_regs.o reciprocal_div.o argv_split.o \
 	 proportions.o prio_heap.o ratelimit.o show_mem.o \
-	 is_single_threaded.o plist.o decompress.o
+	 is_single_threaded.o plist.o decompress.o math128.o
 
 lib-$(CONFIG_MMU) += ioremap.o
 lib-$(CONFIG_SMP) += cpumask.o
--- /dev/null
+++ b/lib/math128.c
@@ -0,0 +1,42 @@
+#include <linux/math128.h>
+
+#ifndef mult_u128
+/*
+ * a * b = (ah * 2^32 + al) * (bh * 2^32 + bl) =
+ *   ah*bh * 2^64 + (ah*bl + bh*al) * 2^32 + al*bl
+ */
+u128 mult_u128(u64 a, u64 b)
+{
+	u128 res;
+	u64 ah, al;
+	u64 bh, bl;
+	u128 t1, t2, t3, t4;
+
+	ah = a >> 32;
+	al = a & ((1ULL << 32) - 1);
+
+	bh = b >> 32;
+	bl = b & ((1ULL << 32) - 1);
+
+	t1.lo = 0;
+	t1.hi = ah * bh;
+
+	t2.lo = ah * bl;
+	t2.hi = t2.lo >> 32;
+	t2.lo <<= 32;
+
+	t3.lo = al * bh;
+	t3.hi = t3.lo >> 32;
+	t3.lo <<= 32;
+
+	t4.lo = al * bl;
+	t4.hi = 0;
+
+	res = add_u128(t1, t2);
+	res = add_u128(res, t3);
+	res = add_u128(res, t4);
+
+	return res;
+}
+#endif /* mult_u128 */
+

[RFC][PATCH 3/3] math128, x86_64: Implement {mult,add}_u128 in 64bit asm

[Peter Zijlstra]

[-- Attachment #1: math128-x86_64.patch --]
[-- Type: text/plain, Size: 1020 bytes --]



Cc: Ingo Molnar <mingo@kernel.org>
Cc: Thomas Gleixner <tglx@linutronix.de>
Cc: H. Peter Anvin <hpa@zytor.com>
Cc: Andrew Morton <akpm@linux-foundation.org>
Cc: Linus Torvalds <torvalds@linux-foundation.org>
Signed-off-by: Peter Zijlstra <a.p.zijlstra@chello.nl>
---
 arch/x86/include/asm/math128.h |   29 +++++++++++++++++++++++++++++
 1 file changed, 29 insertions(+)

--- a/arch/x86/include/asm/math128.h
+++ b/arch/x86/include/asm/math128.h
@@ -1,4 +1,33 @@
 #ifndef _ASM_MATH128_H
 #define _ASM_MATH128_H
 
+#ifdef CONFIG_X86_64
+
+static inline mult_u128(u64 a, u64 b)
+{
+	u128 res;
+
+	asm("mulq %2"
+		: "=a" (res.lo), "=d" (res.hi)
+		:  "rm" (b), "0" (a));
+
+	return res;
+}
+#define mult_u128 mult_u128
+
+static inline add_u128(u128 a, u128 b)
+{
+	u128 res;
+
+	asm("addq %2,%0;\n"
+	    "adcq %3,%1;\n"
+		: "=rm" (res.lo), "=rm" (res.hi)
+		: "r" (b.lo), "r" (b.hi), "0" (a.lo), "1" (a.hi));
+
+	return res;
+}
+#define add_u128 add_u128
+
+#endif /* CONFIG_X86_64 */
+
 #endif /* _ASM_MATH128_H */

Re: [RFC][PATCH 3/3] math128, x86_64: Implement {mult,add}_u128 in 64bit asm

[H. Peter Anvin]

On 04/24/2012 09:10 AM, Peter Zijlstra wrote:

Are you sure that gcc won't simply generate this code already if given
"unsigned __int128"?

	-hpa

Re: [RFC][PATCH 3/3] math128, x86_64: Implement {mult,add}_u128 in 64bit asm

[Peter Zijlstra]

On Tue, 2012-04-24 at 09:34 -0700, H. Peter Anvin wrote:
> On 04/24/2012 09:10 AM, Peter Zijlstra wrote:
> 
> Are you sure that gcc won't simply generate this code already if given
> "unsigned __int128"?

It might, but I've been told some GCC versions had issues, also lots of
archs fall back to libgcc functions.

Re: [RFC][PATCH 3/3] math128, x86_64: Implement {mult,add}_u128 in 64bit asm

[H. Peter Anvin]

On 04/24/2012 09:36 AM, Peter Zijlstra wrote:
> On Tue, 2012-04-24 at 09:34 -0700, H. Peter Anvin wrote:
>> On 04/24/2012 09:10 AM, Peter Zijlstra wrote:
>>
>> Are you sure that gcc won't simply generate this code already if given
>> "unsigned __int128"?
> 
> It might, but I've been told some GCC versions had issues, also lots of
> archs fall back to libgcc functions.
> 

Yes, but this is specific to x86-64.  If gcc can generate the code it
can also schedule the code, which it can't for assembly...

	-hpa

Re: [RFC][PATCH 3/3] math128, x86_64: Implement {mult,add}_u128 in 64bit asm

[Peter Zijlstra]

On Tue, 2012-04-24 at 10:17 -0700, H. Peter Anvin wrote:
> On 04/24/2012 09:36 AM, Peter Zijlstra wrote:
> > On Tue, 2012-04-24 at 09:34 -0700, H. Peter Anvin wrote:
> >> On 04/24/2012 09:10 AM, Peter Zijlstra wrote:
> >>
> >> Are you sure that gcc won't simply generate this code already if given
> >> "unsigned __int128"?
> > 
> > It might, but I've been told some GCC versions had issues, also lots of
> > archs fall back to libgcc functions.
> > 
> 
> Yes, but this is specific to x86-64.  If gcc can generate the code it
> can also schedule the code, which it can't for assembly...

Ok, but are you sure unsigned __int128 works for all gcc versions we
support?

Re: [RFC][PATCH 3/3] math128, x86_64: Implement {mult,add}_u128 in 64bit asm

[H. Peter Anvin]

On 04/24/2012 10:19 AM, Peter Zijlstra wrote:
>>
>> Yes, but this is specific to x86-64.  If gcc can generate the code it
>> can also schedule the code, which it can't for assembly...
> 
> Ok, but are you sure unsigned __int128 works for all gcc versions we
> support?
> 

I have been told __int128 works for all versions of gcc which support
x86-64, but I haven't verified it myself, no.

	-hpa

Re: [RFC][PATCH 0/3] gcc work-around and math128

[H. Peter Anvin]

On 04/24/2012 09:10 AM, Peter Zijlstra wrote:
> 
> So far its just mult, add and cmp for u128, no divisions quite yet. I realize
> that on 32bit archs mult_u128 will result in like 8 multiplication
> instructions that's still nowhere near the most expensive thing ever.
> 

Please add shifts, at the very least.

	-hpa

Re: [RFC][PATCH 0/3] gcc work-around and math128

[H. Peter Anvin]

On 04/24/2012 10:22 AM, H. Peter Anvin wrote:
> On 04/24/2012 09:10 AM, Peter Zijlstra wrote:
>>
>> So far its just mult, add and cmp for u128, no divisions quite yet. I realize
>> that on 32bit archs mult_u128 will result in like 8 multiplication
>> instructions that's still nowhere near the most expensive thing ever.
>>
> 
> Please add shifts, at the very least.
> 

Oh, and a constant constructor.

	-hpa

Re: [RFC][PATCH 2/3] math128: Introduce {mult,add,cmp}_u128

[Linus Torvalds]

On Tue, Apr 24, 2012 at 9:10 AM, Peter Zijlstra <a.p.zijlstra@chello.nl> wrote:
> Grow rudimentary u128 support without relying on gcc/libgcc.
>
> +#ifndef add_u128
> +static inline u128 add_u128(u128 a, u128 b)
> +{
> +       u128 res;
> +
> +       res.hi = a.hi + b.hi;
> +       res.lo = a.lo + b.lo;
> +
> +       if (res.lo < a.lo || res.lo < b.lo)
> +               res.hi++;

This is wrong. Or at least stupid.

Just do one of the comparisons, not both. If overflow occurs, the
result will be smaller than *either* of the added numbers, so
comparing both is just silly and confused.

So just pick one.

Also, it might be worth looking at code generation, to see if it's
better to just do

   a.hi += b.hi;
   a.low += b.low;
   if (a.low < b.low)
      a.hi++;
   return a;

because that might make it clear that there are fewer actual values
live at any particular time. But gcc may not care. Try it.

Also, for the multiply, please make sure gcc knows to do a "32x32->64"
multiplication, rather than thinking it needs to do full 64x64
multiplies..

I'm not sure gcc understands that as you wrote it. You are probably
better off actually using 32-bit values, and then an explicit cast, ie

  u32 a32_0 = .. low 32 bits of a ..
  u32 b32_0 = .. low 32 bits of b ..
  u64 res64_0 = (u64) a32_0 * (u64) b32_0;

but if gcc understands it from the shifts and masks, I guess it doesn't matter.

        Linus

Re: [RFC][PATCH 1/3] kernel,sched,time: Clean up gcc work-arounds

[Linus Torvalds]

On Tue, Apr 24, 2012 at 9:10 AM, Peter Zijlstra <a.p.zijlstra@chello.nl> wrote:
> +#define __gcc_dont_optimize_loop(var) asm("" "+rm" (var))

This seems to be missing a colon.

               Linus

Re: [RFC][PATCH 2/3] math128: Introduce {mult,add,cmp}_u128

[Peter Zijlstra]

On Tue, 2012-04-24 at 12:37 -0700, Linus Torvalds wrote:
> Or at least stupid.
> 
I'll take stupid.. this bit-fiddling isn't something I've done lots of.

I'll go stare at gcc output now.. ;-)

Re: [RFC][PATCH 2/3] math128: Introduce {mult,add,cmp}_u128

[Måns Rullgård]

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

> On Tue, Apr 24, 2012 at 9:10 AM, Peter Zijlstra <a.p.zijlstra@chello.nl> wrote:
>> Grow rudimentary u128 support without relying on gcc/libgcc.
>>
>> +#ifndef add_u128
>> +static inline u128 add_u128(u128 a, u128 b)
>> +{
>> +       u128 res;
>> +
>> +       res.hi = a.hi + b.hi;
>> +       res.lo = a.lo + b.lo;
>> +
>> +       if (res.lo < a.lo || res.lo < b.lo)
>> +               res.hi++;
>
> This is wrong. Or at least stupid.
>
> Just do one of the comparisons, not both. If overflow occurs, the
> result will be smaller than *either* of the added numbers, so
> comparing both is just silly and confused.
>
> So just pick one.
>
> Also, it might be worth looking at code generation, to see if it's
> better to just do
>
>    a.hi += b.hi;
>    a.low += b.low;
>    if (a.low < b.low)
>       a.hi++;
>    return a;

I have no idea if it makes a difference, but that if statement can be
written as a.hi += a.low < b.low.  Just an observation.

> because that might make it clear that there are fewer actual values
> live at any particular time. But gcc may not care. Try it.
>
> Also, for the multiply, please make sure gcc knows to do a "32x32->64"
> multiplication, rather than thinking it needs to do full 64x64
> multiplies..

On ARM it does the right thing at least since 4.3, which is the oldest
ARM compiler I have at hand.

-- 
Måns Rullgård
mans@mansr.com

Re: [RFC][PATCH 0/3] gcc work-around and math128

[Andy Lutomirski]

On 04/24/2012 09:10 AM, Peter Zijlstra wrote:
> Hi all,
> 
> The SCHED_DEADLINE review resulted in the following three patches;
> 
> The first is a cleanup of various copies of the same GCC loop optimization
> work-around. I don't think this patch is too controversial, at worst I've
> picked a wrong name, but I wanted to get it out there in case people
> know more sites.
> 
> The second two implement a few u128 operations so we can do 128bit math.. I
> know a few people will die a little inside, but having nanosecond granularity
> time accounting leads to very big numbers very quickly and when you need to
> multiply them 64bit really isn't that much.

I played with some of this stuff awhile ago, and for timekeeping, it
seemed like a 64x32->96 bit multiply followed by a right shift was
enough, and that operation is a lot faster on 32-bit architectures than
a full 64x64->128 multiply.  Something like:

uint64_t mul_64_32_shift(uint64_t a, uint32_t mult, uint32_t shift)
{
  return (uint64_t)( ((__uint128_t)a * (__uint128_t)mult) >> shift );
}

or (untested, but compilable 32-bit gcc)

uint64_t mul_64_32_shift(uint64_t a, uint32_t mult, uint32_t shift)
{
  uint64_t part1 = ((a & 0xFFFFFFFFULL) * mult) >> shift;
  uint64_t part2 = ((a >> 32) * mult) << (32 - shift);
  return part1 + part2;
}

--Andy

Re: [RFC][PATCH 0/3] gcc work-around and math128

[Linus Torvalds]

On Tue, Apr 24, 2012 at 2:15 PM, Andy Lutomirski <luto@amacapital.net> wrote:
>
> I played with some of this stuff awhile ago, and for timekeeping, it
> seemed like a 64x32->96 bit multiply followed by a right shift was
> enough, and that operation is a lot faster on 32-bit architectures than
> a full 64x64->128 multiply.

Ack. That may sound like odd numbers, but 64x32->96 sounds sane. And I
think it avoids a multiply even on 64-bit, no?

              Linus

Re: [RFC][PATCH 0/3] gcc work-around and math128

[Peter Zijlstra]

On Tue, 2012-04-24 at 14:15 -0700, Andy Lutomirski wrote:
> > The second two implement a few u128 operations so we can do 128bit math.. I
> > know a few people will die a little inside, but having nanosecond granularity
> > time accounting leads to very big numbers very quickly and when you need to
> > multiply them 64bit really isn't that much.
> 
> I played with some of this stuff awhile ago, and for timekeeping, it
> seemed like a 64x32->96 bit multiply followed by a right shift was
> enough, and that operation is a lot faster on 32-bit architectures than
> a full 64x64->128 multiply. 

The SCHED_DEADLINE use case is not that, it multiplies two time
intervals. Basically it needs to evaluate if a task activation still
fits in the old period or if it needs to shift the deadline and start a
new period.

It needs to do: runtime / (deadline - t) < budget / period
which transforms into: (deadline - t) * period < budget * runtime

hence the 64x64->128 mult and 128 compare.

> Something like:
> 
> uint64_t mul_64_32_shift(uint64_t a, uint32_t mult, uint32_t shift)
> {
>   return (uint64_t)( ((__uint128_t)a * (__uint128_t)mult) >> shift );
> }

That looks a lot like what we grew mult_frac() for, it does:

/*              
 * Multiplies an integer by a fraction, while avoiding unnecessary
 * overflow or loss of precision.
 */
#define mult_frac(x, numer, denom)(                     \
{                                                       \
        typeof(x) quot = (x) / (denom);                 \
        typeof(x) rem  = (x) % (denom);                 \
        (quot * (numer)) + ((rem * (numer)) / (denom)); \
}                                                       \
)


and is used in __cycles_2_ns() and friends.

Re: [RFC][PATCH 0/3] gcc work-around and math128

[Andy Lutomirski]

On Tue, Apr 24, 2012 at 2:32 PM, Peter Zijlstra <a.p.zijlstra@chello.nl> wrote:
> On Tue, 2012-04-24 at 14:15 -0700, Andy Lutomirski wrote:
>> > The second two implement a few u128 operations so we can do 128bit math.. I
>> > know a few people will die a little inside, but having nanosecond granularity
>> > time accounting leads to very big numbers very quickly and when you need to
>> > multiply them 64bit really isn't that much.
>>
>> I played with some of this stuff awhile ago, and for timekeeping, it
>> seemed like a 64x32->96 bit multiply followed by a right shift was
>> enough, and that operation is a lot faster on 32-bit architectures than
>> a full 64x64->128 multiply.
>
> The SCHED_DEADLINE use case is not that, it multiplies two time
> intervals. Basically it needs to evaluate if a task activation still
> fits in the old period or if it needs to shift the deadline and start a
> new period.
>
> It needs to do: runtime / (deadline - t) < budget / period
> which transforms into: (deadline - t) * period < budget * runtime
>
> hence the 64x64->128 mult and 128 compare.

Fair enough.

>
>> Something like:
>>
>> uint64_t mul_64_32_shift(uint64_t a, uint32_t mult, uint32_t shift)
>> {
>>   return (uint64_t)( ((__uint128_t)a * (__uint128_t)mult) >> shift );
>> }
>
> That looks a lot like what we grew mult_frac() for, it does:
>
> /*
>  * Multiplies an integer by a fraction, while avoiding unnecessary
>  * overflow or loss of precision.
>  */
> #define mult_frac(x, numer, denom)(                     \
> {                                                       \
>        typeof(x) quot = (x) / (denom);                 \
>        typeof(x) rem  = (x) % (denom);                 \
>        (quot * (numer)) + ((rem * (numer)) / (denom)); \
> }                                                       \
> )
>
>
> and is used in __cycles_2_ns() and friends.

Yeesh.  That looks way slower, and IIRC __cycles_2_ns overflows every
few seconds on modern machines.

gcc 4.6 generates this code:

mul_64_32_shift:
        pushq   %rbp
        movq    %rsp, %rbp
        movl    %edx, %ecx
        movl    %esi, %eax
        mulq    %rdi
        movq    %rdx, %rsi
        shrq    %cl, %rsi
        shrdq   %cl, %rdx, %rax
        testb   $64, %cl
        cmovneq %rsi, %rax
        popq    %rbp
        ret

which is a bit dumb if you can make assumptions about the shift.  See
http://gcc.gnu.org/PR46514.  Some use cases might be able to guarantee
that the shift is less than 32 bits, in which case hand-written
assembly would be a few cycles faster.

--Andy

Re: [RFC][PATCH 0/3] gcc work-around and math128

[Peter Zijlstra]

On Tue, 2012-04-24 at 14:35 -0700, Andy Lutomirski wrote:
> Yeesh.  That looks way slower.

Indeed, pulled it through gcc and saw what was generated with
mult_frac :/

Re: [RFC][PATCH 2/3] math128: Introduce {mult,add,cmp}_u128

[Peter Zijlstra]

On Tue, 2012-04-24 at 12:37 -0700, Linus Torvalds wrote:
> Also, it might be worth looking at code generation, to see if it's
> better to just do
> 
>    a.hi += b.hi;
>    a.low += b.low;
>    if (a.low < b.low)
>       a.hi++;
>    return a;
> 
> because that might make it clear that there are fewer actual values
> live at any particular time. But gcc may not care. Try it.

It does indeed generate tons better code. FWIW, Mans' suggestion of: 
  a.hi += a.lo < b.lo;
horribly confuses gcc.

> Also, for the multiply, please make sure gcc knows to do a "32x32->64"
> multiplication, rather than thinking it needs to do full 64x64
> multiplies..
> 
> I'm not sure gcc understands that as you wrote it.

It does indeed grok it (as Mans also confirmed for ARM), however:

>  You are probably
> better off actually using 32-bit values, and then an explicit cast, ie
> 
>   u32 a32_0 = .. low 32 bits of a ..
>   u32 b32_0 = .. low 32 bits of b ..
>   u64 res64_0 = (u64) a32_0 * (u64) b32_0;
> 
> but if gcc understands it from the shifts and masks, I guess it doesn't matter.

that does generate slightly better code in that it avoids some masks on
64bit:

@@ -7,12 +7,11 @@
 .LFB38:
        .cfi_startproc
        movq    %rdi, %r8
-       movq    %rdi, %rdx
        movq    %rsi, %rcx
+       mov     %edi, %edx
        shrq    $32, %r8
-       andl    $4294967295, %edx
        shrq    $32, %rcx
-       andl    $4294967295, %esi
+       mov     %esi, %esi
        movq    %rcx, %rax
        imulq   %rdx, %rcx
        imulq   %rsi, %rdx

Re: [RFC][PATCH 3/3] math128, x86_64: Implement {mult,add}_u128 in 64bit asm

[Peter Zijlstra]

On Tue, 2012-04-24 at 10:20 -0700, H. Peter Anvin wrote:
> I have been told __int128 works for all versions of gcc which support
> x86-64, but I haven't verified it myself, no. 

The gcc version I have seems to grok it:

u128 mult_u64_u128(u64 a, u64 b)                                                             
{                                                                                            
        unsigned __int128 t = a;                                                             
        t *= b;                                                                              
        return U128_INIT(t >> 64, t);                                                        
}
#define mult_u64_u128 mult_u64_u128

generates:

        .p2align 4,,15
        .globl  mult_u64_u128
        .type   mult_u64_u128, @function
mult_u64_u128:
.LFB38:
        .cfi_startproc
        movq    %rsi, %rax
        pushq   %rbp
        .cfi_def_cfa_offset 16
        .cfi_offset 6, -16
        mulq    %rdi
        popq    %rbp
        .cfi_def_cfa_offset 8
        movq    %rax, %rdi
        movq    %rdx, %rax
        movq    %rdi, %rdx
        ret
        .cfi_endproc
.LFE38:
        .size   mult_u64_u128, .-mult_u64_u128

I haven't been able to make add_u128 generate sane code using __int128,
the conversion between my struct and the __int128 layout makes a horrid
mess.

Re: [RFC][PATCH 3/3] math128, x86_64: Implement {mult,add}_u128 in 64bit asm

[H. Peter Anvin]

On 04/24/2012 03:00 PM, Peter Zijlstra wrote:
> 
> I haven't been able to make add_u128 generate sane code using __int128,
> the conversion between my struct and the __int128 layout makes a horrid
> mess.
> 

Use a union, or define your type simply as __int128 if you're on a
suitable platform?

	-hpa

Re: [RFC][PATCH 2/3] math128: Introduce {mult,add,cmp}_u128

[H. Peter Anvin]

On 04/24/2012 02:54 PM, Peter Zijlstra wrote:
> -       andl    $4294967295, %edx
>         shrq    $32, %rcx
> -       andl    $4294967295, %esi
> +       mov     %esi, %esi

If you can *ever* get gcc to generate those andl instructions on x86,
then please file a gcc bug report: the constant is 0xffffffff and those
are plain zero-extension instructions which is much better done with mov.

	-hpa

Re: [RFC][PATCH 1/3] kernel,sched,time: Clean up gcc work-arounds

[Stephen Rothwell]

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

Hi Peter,

On Tue, 24 Apr 2012 18:10:40 +0200 Peter Zijlstra <a.p.zijlstra@chello.nl> wrote:
>
> We've grown various copies of a particular gcc work-around,
> consolidate them into one and add a larger comment.
> 
> Cc: Ingo Molnar <mingo@kernel.org>
> Cc: Thomas Gleixner <tglx@linutronix.de>
> Cc: Andrew Morton <akpm@linux-foundation.org>
> Cc: Linus Torvalds <torvalds@linux-foundation.org>
> Signed-off-by: Peter Zijlstra <a.p.zijlstra@chello.nl>
> ---
>  include/linux/compiler.h |   12 ++++++++++++
>  include/linux/math64.h   |    4 +---
>  kernel/sched/core.c      |    8 ++------
>  kernel/sched/fair.c      |    8 ++------
>  kernel/time.c            |   11 ++++-------

You should, of course, include linux/compiler.h into those last 4 files ...

-- 
Cheers,
Stephen Rothwell                    sfr@canb.auug.org.au

[-- Attachment #2: Type: application/pgp-signature, Size: 836 bytes --]

Re: [RFC][PATCH 2/3] math128: Introduce {mult,add,cmp}_u128

[Stephen Rothwell]

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

Hi Peter,

On Tue, 24 Apr 2012 18:10:41 +0200 Peter Zijlstra <a.p.zijlstra@chello.nl> wrote:
>
> Grow rudimentary u128 support without relying on gcc/libgcc.
> 
> Cc: Ingo Molnar <mingo@kernel.org>
> Cc: Thomas Gleixner <tglx@linutronix.de>
> Cc: Andrew Morton <akpm@linux-foundation.org>
> Cc: Linus Torvalds <torvalds@linux-foundation.org>
> Signed-off-by: Peter Zijlstra <a.p.zijlstra@chello.nl>
> ---
>  arch/alpha/include/asm/math128.h      |    4 ++
>  arch/arm/include/asm/math128.h        |    4 ++
>  arch/avr32/include/asm/math128.h      |    4 ++
>  arch/blackfin/include/asm/math128.h   |    4 ++
>  arch/c6x/include/asm/math128.h        |    4 ++
>  arch/cris/include/asm/math128.h       |    4 ++
>  arch/frv/include/asm/math128.h        |    4 ++
>  arch/h8300/include/asm/math128.h      |    4 ++
>  arch/hexagon/include/asm/math128.h    |    4 ++
>  arch/ia64/include/asm/math128.h       |    4 ++
>  arch/m32r/include/asm/math128.h       |    4 ++
>  arch/m68k/include/asm/math128.h       |    4 ++
>  arch/microblaze/include/asm/math128.h |    4 ++
>  arch/mips/include/asm/math128.h       |    4 ++
>  arch/mn10300/include/asm/math128.h    |    4 ++
>  arch/openrisc/include/asm/math128.h   |    4 ++
>  arch/parisc/include/asm/math128.h     |    4 ++
>  arch/powerpc/include/asm/math128.h    |    4 ++
>  arch/s390/include/asm/math128.h       |    4 ++
>  arch/score/include/asm/math128.h      |    4 ++
>  arch/sh/include/asm/math128.h         |    4 ++
>  arch/sparc/include/asm/math128.h      |    4 ++
>  arch/tile/include/asm/math128.h       |    4 ++
>  arch/um/include/asm/math128.h         |    4 ++
>  arch/unicore32/include/asm/math128.h  |    4 ++
>  arch/x86/include/asm/math128.h        |    4 ++
>  arch/xtensa/include/asm/math128.h     |    4 ++
>  include/linux/math128.h               |   47 ++++++++++++++++++++++++++++++++++

Isn't this what asm-generic is for?  You put the generic version in
asm-generic/math128.h and then add "generic-y += math128.h" to
arch/*/include/asm/Kbuild for each arch that wants the generic version.
Then just include asm/math128.h in linux/math128.h.  Any arch that wants
to optimise these can then just provide its own math128.h.
-- 
Cheers,
Stephen Rothwell                    sfr@canb.auug.org.au

[-- Attachment #2: Type: application/pgp-signature, Size: 836 bytes --]

Re: [RFC][PATCH 2/3] math128: Introduce {mult,add,cmp}_u128

[Linus Torvalds]

On Tue, Apr 24, 2012 at 2:54 PM, Peter Zijlstra <a.p.zijlstra@chello.nl> wrote:
>
> that does generate slightly better code in that it avoids some masks on
> 64bit:
>
> @@ -7,12 +7,11 @@
>  .LFB38:
>        .cfi_startproc
>        movq    %rdi, %r8
> -       movq    %rdi, %rdx
>        movq    %rsi, %rcx
> +       mov     %edi, %edx
>        shrq    $32, %r8
> -       andl    $4294967295, %edx
>        shrq    $32, %rcx
> -       andl    $4294967295, %esi
> +       mov     %esi, %esi

Oh christ.

What insane version of gcc is that? Can you please make a gcc bug-report?

Because a compiler that generates an instruction sequence like

    movq %rdi,%rsi
    andl $4294967295, %esi

is just so fricking stupid that it's outright buggy. That's just
crazy. It's demented. It's an "and" with all bits set.

But yeah, I do think that in general using a cast to 32-bit instead of
a mask to 32-bit is easier for the compiler. Although that still is a
particularly stupid code sequence to use.

                     Linus

Re: [RFC][PATCH 2/3] math128: Introduce {mult,add,cmp}_u128

[Peter Zijlstra]

On Wed, 2012-04-25 at 10:23 +1000, Stephen Rothwell wrote:
> Isn't this what asm-generic is for?  You put the generic version in
> asm-generic/math128.h and then add "generic-y += math128.h" to
> arch/*/include/asm/Kbuild for each arch that wants the generic version.
> Then just include asm/math128.h in linux/math128.h.  Any arch that wants
> to optimise these can then just provide its own math128.h. 

Ah, right. I didn't know that Kbuild trick. /me does:

  ls arch/*/include/asm/Kbuild | while read file; do quilt add $file;
echo "generic-y += math128.h" >> $file; done

Thanks!

Re: [RFC][PATCH 2/3] math128: Introduce {mult,add,cmp}_u128

[Peter Zijlstra]

On Tue, 2012-04-24 at 18:46 -0700, Linus Torvalds wrote:
> What insane version of gcc is that? Can you please make a gcc bug-report?

gcc (Ubuntu/Linaro 4.6.1-9ubuntu3) 4.6.1


I'll go and build me a gcc.git 4.6 and 4.7 branch compiler to see if its
still there.

Re: [RFC][PATCH 2/3] math128: Introduce {mult,add,cmp}_u128

[Peter Zijlstra]

On Tue, 2012-04-24 at 18:46 -0700, Linus Torvalds wrote:
> Can you please make a gcc bug-report?
> 
http://gcc.gnu.org/bugzilla/show_bug.cgi?id=53110

Re: [RFC][PATCH 2/3] math128: Introduce {mult,add,cmp}_u128

[Geert Uytterhoeven]

On Wed, Apr 25, 2012 at 10:11, Peter Zijlstra <a.p.zijlstra@chello.nl> wrote:
>  ls arch/*/include/asm/Kbuild | while read file; do quilt add $file;
> echo "generic-y += math128.h" >> $file; done

That may fail if your "ls" is an alias.
Better: "for file in arch/*/include/asm/Kbuild;do ..; done".

Still using quilt? I didn't regret ditching it in favor of git (yummy,
git rebase ;-).

Gr{oetje,eeting}s,

                        Geert

--
Geert Uytterhoeven -- There's lots of Linux beyond ia32 -- geert@linux-m68k.org

In personal conversations with technical people, I call myself a hacker. But
when I'm talking to journalists I just say "programmer" or something like that.
                                -- Linus Torvalds

Re: [RFC][PATCH 2/3] math128: Introduce {mult,add,cmp}_u128

[Peter Zijlstra]

On Wed, 2012-04-25 at 13:23 +0200, Geert Uytterhoeven wrote:
> On Wed, Apr 25, 2012 at 10:11, Peter Zijlstra <a.p.zijlstra@chello.nl> wrote:
> >  ls arch/*/include/asm/Kbuild | while read file; do quilt add $file;
> > echo "generic-y += math128.h" >> $file; done
> 
> That may fail if your "ls" is an alias.
> Better: "for file in arch/*/include/asm/Kbuild;do ..; done".

Agreed, still ls worked and the patch is send..

> Still using quilt? I didn't regret ditching it in favor of git (yummy,
> git rebase ;-).

Yeah, I can't seem to deal with git, I edit my patches by hand way too
often, also quilt is a _LOT_ faster pushing/popping patches than git is
(and yes I use an SSD).

Not using git also means I don't have to deal with the trainwreck that
is git-merge,.. /me runs like hell.

Re: [RFC][PATCH 2/3] math128: Introduce {mult,add,cmp}_u128

[Geert Uytterhoeven]

On Wed, Apr 25, 2012 at 13:58, Peter Zijlstra <a.p.zijlstra@chello.nl> wrote:
>> Still using quilt? I didn't regret ditching it in favor of git (yummy,
>> git rebase ;-).
>
> Yeah, I can't seem to deal with git, I edit my patches by hand way too
> often, also quilt is a _LOT_ faster pushing/popping patches than git is
> (and yes I use an SSD).
>
> Not using git also means I don't have to deal with the trainwreck that
> is git-merge,.. /me runs like hell.

But you have to deal with the quilt-oh-no-the-patch-no-longer-applies
trainwreck...

Gr{oetje,eeting}s,

                        Geert

--
Geert Uytterhoeven -- There's lots of Linux beyond ia32 -- geert@linux-m68k.org

In personal conversations with technical people, I call myself a hacker. But
when I'm talking to journalists I just say "programmer" or something like that.
                                -- Linus Torvalds

Re: [RFC][PATCH 2/3] math128: Introduce {mult,add,cmp}_u128

[Peter Zijlstra]

On Wed, 2012-04-25 at 16:35 +0200, Geert Uytterhoeven wrote:
> On Wed, Apr 25, 2012 at 13:58, Peter Zijlstra <a.p.zijlstra@chello.nl> wrote:
> >> Still using quilt? I didn't regret ditching it in favor of git (yummy,
> >> git rebase ;-).
> >
> > Yeah, I can't seem to deal with git, I edit my patches by hand way too
> > often, also quilt is a _LOT_ faster pushing/popping patches than git is
> > (and yes I use an SSD).
> >
> > Not using git also means I don't have to deal with the trainwreck that
> > is git-merge,.. /me runs like hell.
> 
> But you have to deal with the quilt-oh-no-the-patch-no-longer-applies
> trainwreck...

Yeah, but I find it much easier to deal with .rej files than with the
stuff left behind by git.