[PATCH 0/4] [RFC] cleanup 64bit divide API

[PATCH 0/4] [RFC] cleanup 64bit divide API

[zippel]

Hi,

The primary purpose of these patches is to introduce a signed divide,
which is useful for NTP. While I'm at it I cleaned up the API, so it
should be a little easier to use.
It uses a new header <linux/math64.h> for it instead of using
<asm-generic/div64.h>. asm-generic/div64.h has the problem of an
all-or-nothing approach, so any arch not using it has to implement the
whole API and usually it's enough to provide only one of them.
<linux/math64.h> allows to selectively functions as needed.

In the long term we can first depricate using <asm/div64.h> and even
later do_div() completely.

bye, Roman

-- 

[PATCH 1/4] introduce explicit signed/unsigned 64bit divide

[zippel]

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

The current do_div doesn't explicitly say that it's unsigned and the
signed counterpart is missing, which is e.g. needed when dealing with
time values.
This introduces 64bit signed/unsigned divide functions which also
attempts to cleanup the somewhat awkward calling API, which often
requires the use of temporary variables for the dividend. To avoid the
need for temporary variables everywhere for the remainder, each divide
variant also provides a version which doesn't return the remainder.

Each architecture can now provide optimized versions of these function,
otherwise generic fallback implementations will be used.

As an example I provided an alternative for the current x86 divide,
which avoids the asm casts and using an union allows gcc to generate
better code. It also avoids the upper divde in a few more cases, where
the result is known (i.e. upper quotient is zero).

Signed-off-by: Roman Zippel <zippel@linux-m68k.org>

---
 include/asm-x86/div64.h |   20 +++++++++++++
 include/linux/math64.h  |   72 ++++++++++++++++++++++++++++++++++++++++++++++++
 lib/div64.c             |   23 ++++++++++++++-
 3 files changed, 113 insertions(+), 2 deletions(-)

Index: linux-2.6/include/asm-x86/div64.h
===================================================================
--- linux-2.6.orig/include/asm-x86/div64.h	2008-03-11 17:15:21.000000000 +0100
+++ linux-2.6/include/asm-x86/div64.h	2008-03-12 21:21:26.000000000 +0100
@@ -50,6 +50,26 @@ div_ll_X_l_rem(long long divs, long div,
 
 }
 
+static inline u64 div_u64_rem(u64 dividend, u32 divisor, u32 *remainder)
+{
+	union {
+		u64 v64;
+		u32 v32[2];
+	} d = { dividend };
+	u32 upper;
+
+	upper = d.v32[1];
+	d.v32[1] = 0;
+	if (upper >= divisor) {
+		d.v32[1] = upper / divisor;
+		upper %= divisor;
+	}
+	asm ("divl %2" : "=a" (d.v32[0]), "=d" (*remainder) :
+		"rm" (divisor), "0" (d.v32[0]), "1" (upper));
+	return d.v64;
+}
+#define div_u64_rem	div_u64_rem
+
 extern uint64_t div64_64(uint64_t dividend, uint64_t divisor);
 
 #else
Index: linux-2.6/lib/div64.c
===================================================================
--- linux-2.6.orig/lib/div64.c	2008-03-11 17:15:21.000000000 +0100
+++ linux-2.6/lib/div64.c	2008-03-12 21:21:26.000000000 +0100
@@ -16,9 +16,8 @@
  * assembly versions such as arch/ppc/lib/div64.S and arch/sh/lib/div64.S.
  */
 
-#include <linux/types.h>
 #include <linux/module.h>
-#include <asm/div64.h>
+#include <linux/math64.h>
 
 /* Not needed on 64bit architectures */
 #if BITS_PER_LONG == 32
@@ -58,6 +57,26 @@ uint32_t __attribute__((weak)) __div64_3
 
 EXPORT_SYMBOL(__div64_32);
 
+#ifndef div_s64_rem
+s64 div_s64_rem(s64 dividend, s32 divisor, s32 *remainder)
+{
+	u64 quotient;
+
+	if (dividend < 0) {
+		quotient = div_u64_rem(-dividend, abs(divisor), (u32 *)remainder);
+		*remainder = -*remainder;
+		if (divisor > 0)
+			quotient = -quotient;
+	} else {
+		quotient = div_u64_rem(dividend, abs(divisor), (u32 *)remainder);
+		if (divisor < 0)
+			quotient = -quotient;
+	}
+	return quotient;
+}
+EXPORT_SYMBOL(div_s64_rem);
+#endif
+
 /* 64bit divisor, dividend and result. dynamic precision */
 uint64_t div64_64(uint64_t dividend, uint64_t divisor)
 {
Index: linux-2.6/include/linux/math64.h
===================================================================
--- /dev/null	1970-01-01 00:00:00.000000000 +0000
+++ linux-2.6/include/linux/math64.h	2008-03-12 21:21:26.000000000 +0100
@@ -0,0 +1,72 @@
+#ifndef _LINUX_MATH64_H
+#define _LINUX_MATH64_H
+
+#include <linux/types.h>
+#include <asm/div64.h>
+
+#if BITS_PER_LONG == 64
+
+/**
+ * div_u64_rem - unsigned 64bit divide with 32bit divisor with remainder
+ *
+ * This is commonly provided by 32bit archs to provide an optimized 64bit
+ * divide.
+ */
+static inline u64 div_u64_rem(u64 dividend, u32 divisor, u32 *remainder)
+{
+	*remainder = dividend % divisor;
+	return dividend / divisor;
+}
+
+/**
+ * div_s64_rem - signed 64bit divide with 32bit divisor with remainder
+ */
+static inline u64 div_u64_rem(u64 dividend, u32 divisor, u32 *remainder)
+{
+	*remainder = dividend % divisor;
+	return dividend / divisor;
+}
+
+#elif BITS_PER_LONG == 32
+
+#ifndef div_u64_rem
+static inline u64 div_u64_rem(u64 dividend, u32 divisor, u32 *remainder)
+{
+	*remainder = do_div(dividend, divisor);
+	return dividend;
+}
+#endif
+
+#ifndef div_s64_rem
+extern s64 div_s64_rem(s64 dividend, s32 divisor, s32 *remainder);
+#endif
+
+#endif /* BITS_PER_LONG */
+
+/**
+ * div_u64 - unsigned 64bit divide with 32bit divisor
+ *
+ * This is the most common 64bit divide and should be used if possible,
+ * as many 32bit archs can optimize this variant better than a full 64bit
+ * divide.
+ */
+#ifndef div_u64
+static inline u64 div_u64(u64 dividend, u32 divisor)
+{
+	u32 remainder;
+	return div_u64_rem(dividend, divisor, &remainder);
+}
+#endif
+
+/**
+ * div_s64 - signed 64bit divide with 32bit divisor
+ */
+#ifndef div_u64
+static inline s64 div_s64(s64 dividend, s32 divisor)
+{
+	s32 remainder;
+	return div_s64_rem(dividend, divisor, &remainder);
+}
+#endif
+
+#endif /* _LINUX_MATH64_H */

-- 

[PATCH 2/4] convert a few do_div user

[zippel]

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

This converts a few users of do_div to div_[su]64 and this demonstrates
nicely how it can reduce some expressions to one-liners.

Signed-off-by: Roman Zippel <zippel@linux-m68k.org>

---
 kernel/time.c     |   29 +++++++++--------------------
 kernel/time/ntp.c |   25 ++++++-------------------
 2 files changed, 15 insertions(+), 39 deletions(-)

Index: linux-2.6/kernel/time.c
===================================================================
--- linux-2.6.orig/kernel/time.c	2008-03-11 17:15:14.000000000 +0100
+++ linux-2.6/kernel/time.c	2008-03-12 21:21:20.000000000 +0100
@@ -35,6 +35,7 @@
 #include <linux/syscalls.h>
 #include <linux/security.h>
 #include <linux/fs.h>
+#include <linux/math64.h>
 
 #include <asm/uaccess.h>
 #include <asm/unistd.h>
@@ -585,9 +586,7 @@ clock_t jiffies_to_clock_t(long x)
 	return x / (HZ / USER_HZ);
 # endif
 #else
-	u64 tmp = (u64)x * TICK_NSEC;
-	do_div(tmp, (NSEC_PER_SEC / USER_HZ));
-	return (long)tmp;
+	return div_u64((u64)x * TICK_NSEC, NSEC_PER_SEC / USER_HZ);
 #endif
 }
 EXPORT_SYMBOL(jiffies_to_clock_t);
@@ -599,16 +598,12 @@ unsigned long clock_t_to_jiffies(unsigne
 		return ~0UL;
 	return x * (HZ / USER_HZ);
 #else
-	u64 jif;
-
 	/* Don't worry about loss of precision here .. */
 	if (x >= ~0UL / HZ * USER_HZ)
 		return ~0UL;
 
 	/* .. but do try to contain it here */
-	jif = x * (u64) HZ;
-	do_div(jif, USER_HZ);
-	return jif;
+	return div_u64((u64)x * HZ, USER_HZ);
 #endif
 }
 EXPORT_SYMBOL(clock_t_to_jiffies);
@@ -617,10 +612,9 @@ u64 jiffies_64_to_clock_t(u64 x)
 {
 #if (TICK_NSEC % (NSEC_PER_SEC / USER_HZ)) == 0
 # if HZ < USER_HZ
-	x *= USER_HZ;
-	do_div(x, HZ);
+	x = div_u64(x * USER_HZ, HZ);
 # elif HZ > USER_HZ
-	do_div(x, HZ / USER_HZ);
+	x = div_u64(x, HZ / USER_HZ);
 # else
 	/* Nothing to do */
 # endif
@@ -630,8 +624,7 @@ u64 jiffies_64_to_clock_t(u64 x)
 	 * but even this doesn't overflow in hundreds of years
 	 * in 64 bits, so..
 	 */
-	x *= TICK_NSEC;
-	do_div(x, (NSEC_PER_SEC / USER_HZ));
+	x = div_u64(x * TICK_NSEC, (NSEC_PER_SEC / USER_HZ));
 #endif
 	return x;
 }
@@ -640,21 +633,17 @@ EXPORT_SYMBOL(jiffies_64_to_clock_t);
 u64 nsec_to_clock_t(u64 x)
 {
 #if (NSEC_PER_SEC % USER_HZ) == 0
-	do_div(x, (NSEC_PER_SEC / USER_HZ));
+	return div_u64(x, NSEC_PER_SEC / USER_HZ);
 #elif (USER_HZ % 512) == 0
-	x *= USER_HZ/512;
-	do_div(x, (NSEC_PER_SEC / 512));
+	return div_u64(x * USER_HZ / 512, NSEC_PER_SEC / 512);
 #else
 	/*
          * max relative error 5.7e-8 (1.8s per year) for USER_HZ <= 1024,
          * overflow after 64.99 years.
          * exact for HZ=60, 72, 90, 120, 144, 180, 300, 600, 900, ...
          */
-	x *= 9;
-	do_div(x, (unsigned long)((9ull * NSEC_PER_SEC + (USER_HZ/2)) /
-				  USER_HZ));
+	return div_u64(x * 9, (9ull * NSEC_PER_SEC + (USER_HZ / 2)) / USER_HZ);
 #endif
-	return x;
 }
 
 #if (BITS_PER_LONG < 64)
Index: linux-2.6/kernel/time/ntp.c
===================================================================
--- linux-2.6.orig/kernel/time/ntp.c	2008-03-11 17:15:14.000000000 +0100
+++ linux-2.6/kernel/time/ntp.c	2008-03-12 21:21:20.000000000 +0100
@@ -15,7 +15,7 @@
 #include <linux/jiffies.h>
 #include <linux/hrtimer.h>
 #include <linux/capability.h>
-#include <asm/div64.h>
+#include <linux/math64.h>
 #include <asm/timex.h>
 
 /*
@@ -53,10 +53,8 @@ static void ntp_update_frequency(void)
 
 	tick_length_base = second_length;
 
-	do_div(second_length, HZ);
-	tick_nsec = second_length >> TICK_LENGTH_SHIFT;
-
-	do_div(tick_length_base, NTP_INTERVAL_FREQ);
+	tick_nsec = div_u64(second_length, HZ) >> TICK_LENGTH_SHIFT;
+	tick_length_base = div_u64(tick_length_base, NTP_INTERVAL_FREQ);
 }
 
 /**
@@ -237,7 +235,7 @@ static inline void notify_cmos_timer(voi
 int do_adjtimex(struct timex *txc)
 {
 	long mtemp, save_adjust, rem;
-	s64 freq_adj, temp64;
+	s64 freq_adj;
 	int result;
 
 	/* In order to modify anything, you gotta be super-user! */
@@ -342,19 +340,8 @@ int do_adjtimex(struct timex *txc)
 		    freq_adj = time_offset * mtemp;
 		    freq_adj = shift_right(freq_adj, time_constant * 2 +
 					   (SHIFT_PLL + 2) * 2 - SHIFT_NSEC);
-		    if (mtemp >= MINSEC && (time_status & STA_FLL || mtemp > MAXSEC)) {
-			u64 utemp64;
-			temp64 = time_offset << (SHIFT_NSEC - SHIFT_FLL);
-			if (time_offset < 0) {
-			    utemp64 = -temp64;
-			    do_div(utemp64, mtemp);
-			    freq_adj -= utemp64;
-			} else {
-			    utemp64 = temp64;
-			    do_div(utemp64, mtemp);
-			    freq_adj += utemp64;
-			}
-		    }
+		    if (mtemp >= MINSEC && (time_status & STA_FLL || mtemp > MAXSEC))
+			freq_adj += div_s64(time_offset << (SHIFT_NSEC - SHIFT_FLL), mtemp);
 		    freq_adj += time_freq;
 		    freq_adj = min(freq_adj, (s64)MAXFREQ_NSEC);
 		    time_freq = max(freq_adj, (s64)-MAXFREQ_NSEC);

-- 

[PATCH 3/4] rename div64_64 to div64_u64

[zippel]

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

Rename div64_64 to div64_u64 to make it consistent with the other divide
functions, so it clearly includes the type of the divide.
Move its definition to math64.h as currently no architecture overrides
the generic implementation. They can still override it of course, but
the duplicated declarations are avoided.

Signed-off-by: Roman Zippel <zippel@linux-m68k.org>

---
 arch/x86/kvm/lapic.c         |    6 +++---
 include/asm-arm/div64.h      |    2 --
 include/asm-generic/div64.h  |    7 -------
 include/asm-m68k/div64.h     |    1 -
 include/asm-mips/div64.h     |    6 ------
 include/asm-mn10300/div64.h  |    3 ---
 include/asm-um/div64.h       |    1 -
 include/asm-x86/div64.h      |    2 --
 include/linux/math64.h       |   14 +++++++++++++-
 kernel/sched.c               |    7 ++++---
 kernel/sched_debug.c         |    4 ++--
 lib/div64.c                  |   12 ++++++------
 net/ipv4/tcp_cubic.c         |    4 ++--
 net/netfilter/xt_connbytes.c |    5 ++---
 14 files changed, 32 insertions(+), 42 deletions(-)

Index: linux-2.6/arch/x86/kvm/lapic.c
===================================================================
--- linux-2.6.orig/arch/x86/kvm/lapic.c	2008-03-11 17:15:14.000000000 +0100
+++ linux-2.6/arch/x86/kvm/lapic.c	2008-03-11 17:55:00.000000000 +0100
@@ -25,13 +25,13 @@
 #include <linux/hrtimer.h>
 #include <linux/io.h>
 #include <linux/module.h>
+#include <linux/math64.h>
 #include <asm/processor.h>
 #include <asm/msr.h>
 #include <asm/page.h>
 #include <asm/current.h>
 #include <asm/apicdef.h>
 #include <asm/atomic.h>
-#include <asm/div64.h>
 #include "irq.h"
 
 #define PRId64 "d"
@@ -526,8 +526,8 @@ static u32 apic_get_tmcct(struct kvm_lap
 	} else
 		passed = ktime_sub(now, apic->timer.last_update);
 
-	counter_passed = div64_64(ktime_to_ns(passed),
-				  (APIC_BUS_CYCLE_NS * apic->timer.divide_count));
+	counter_passed = div64_u64(ktime_to_ns(passed),
+				   (APIC_BUS_CYCLE_NS * apic->timer.divide_count));
 
 	if (counter_passed > tmcct) {
 		if (unlikely(!apic_lvtt_period(apic))) {
Index: linux-2.6/include/asm-arm/div64.h
===================================================================
--- linux-2.6.orig/include/asm-arm/div64.h	2008-03-11 17:15:14.000000000 +0100
+++ linux-2.6/include/asm-arm/div64.h	2008-03-11 17:53:57.000000000 +0100
@@ -224,6 +224,4 @@
 
 #endif
 
-extern uint64_t div64_64(uint64_t dividend, uint64_t divisor);
-
 #endif
Index: linux-2.6/include/asm-generic/div64.h
===================================================================
--- linux-2.6.orig/include/asm-generic/div64.h	2008-03-11 17:15:21.000000000 +0100
+++ linux-2.6/include/asm-generic/div64.h	2008-03-11 17:53:57.000000000 +0100
@@ -30,11 +30,6 @@
 	__rem;							\
  })
 
-static inline uint64_t div64_64(uint64_t dividend, uint64_t divisor)
-{
-	return dividend / divisor;
-}
-
 #elif BITS_PER_LONG == 32
 
 extern uint32_t __div64_32(uint64_t *dividend, uint32_t divisor);
@@ -54,8 +49,6 @@ extern uint32_t __div64_32(uint64_t *div
 	__rem;						\
  })
 
-extern uint64_t div64_64(uint64_t dividend, uint64_t divisor);
-
 #else /* BITS_PER_LONG == ?? */
 
 # error do_div() does not yet support the C64
Index: linux-2.6/include/asm-m68k/div64.h
===================================================================
--- linux-2.6.orig/include/asm-m68k/div64.h	2008-03-11 17:15:14.000000000 +0100
+++ linux-2.6/include/asm-m68k/div64.h	2008-03-11 17:53:57.000000000 +0100
@@ -25,5 +25,4 @@
 	__rem;							\
 })
 
-extern uint64_t div64_64(uint64_t dividend, uint64_t divisor);
 #endif /* _M68K_DIV64_H */
Index: linux-2.6/include/asm-mips/div64.h
===================================================================
--- linux-2.6.orig/include/asm-mips/div64.h	2008-03-11 17:15:14.000000000 +0100
+++ linux-2.6/include/asm-mips/div64.h	2008-03-11 17:53:57.000000000 +0100
@@ -82,7 +82,6 @@
 	(n) = __quot; \
 	__mod; })
 
-extern uint64_t div64_64(uint64_t dividend, uint64_t divisor);
 #endif /* (_MIPS_SZLONG == 32) */
 
 #if (_MIPS_SZLONG == 64)
@@ -106,11 +105,6 @@ extern uint64_t div64_64(uint64_t divide
 	(n) = __quot; \
 	__mod; })
 
-static inline uint64_t div64_64(uint64_t dividend, uint64_t divisor)
-{
-	return dividend / divisor;
-}
-
 #endif /* (_MIPS_SZLONG == 64) */
 
 #endif /* _ASM_DIV64_H */
Index: linux-2.6/include/asm-mn10300/div64.h
===================================================================
--- linux-2.6.orig/include/asm-mn10300/div64.h	2008-03-11 17:15:14.000000000 +0100
+++ linux-2.6/include/asm-mn10300/div64.h	2008-03-11 17:53:57.000000000 +0100
@@ -97,7 +97,4 @@ signed __muldiv64s(signed val, signed mu
 	return result;
 }
 
-extern __attribute__((const))
-uint64_t div64_64(uint64_t dividend, uint64_t divisor);
-
 #endif /* _ASM_DIV64 */
Index: linux-2.6/include/asm-um/div64.h
===================================================================
--- linux-2.6.orig/include/asm-um/div64.h	2008-03-11 17:15:14.000000000 +0100
+++ linux-2.6/include/asm-um/div64.h	2008-03-11 17:53:57.000000000 +0100
@@ -3,5 +3,4 @@
 
 #include "asm/arch/div64.h"
 
-extern uint64_t div64_64(uint64_t dividend, uint64_t divisor);
 #endif
Index: linux-2.6/include/asm-x86/div64.h
===================================================================
--- linux-2.6.orig/include/asm-x86/div64.h	2008-03-11 17:15:31.000000000 +0100
+++ linux-2.6/include/asm-x86/div64.h	2008-03-12 21:21:20.000000000 +0100
@@ -70,8 +70,6 @@ static inline u64 div_u64_rem(u64 divide
 }
 #define div_u64_rem	div_u64_rem
 
-extern uint64_t div64_64(uint64_t dividend, uint64_t divisor);
-
 #else
 # include <asm-generic/div64.h>
 #endif /* CONFIG_X86_32 */
Index: linux-2.6/include/linux/math64.h
===================================================================
--- linux-2.6.orig/include/linux/math64.h	2008-03-11 17:47:20.000000000 +0100
+++ linux-2.6/include/linux/math64.h	2008-03-11 19:59:58.000000000 +0100
@@ -21,12 +21,20 @@ static inline u64 div_u64_rem(u64 divide
 /**
  * div_s64_rem - signed 64bit divide with 32bit divisor with remainder
  */
-static inline u64 div_u64_rem(u64 dividend, u32 divisor, u32 *remainder)
+static inline s64 div_s64_rem(s64 dividend, s32 divisor, s32 *remainder)
 {
 	*remainder = dividend % divisor;
 	return dividend / divisor;
 }
 
+/**
+ * div64_u64 - unsigned 64bit divide with 64bit divisor
+ */
+static inline u64 div64_u64(u64 dividend, u64 divisor)
+{
+	return dividend / divisor;
+}
+
 #elif BITS_PER_LONG == 32
 
 #ifndef div_u64_rem
@@ -69,4 +77,8 @@ static inline s64 div_s64(s64 dividend, 
 }
 #endif
 
+#ifndef div64_u64
+extern u64 div64_u64(u64 dividend, u64 divisor);
+#endif
+
 #endif /* _LINUX_MATH64_H */
Index: linux-2.6/kernel/sched.c
===================================================================
--- linux-2.6.orig/kernel/sched.c	2008-03-11 17:15:14.000000000 +0100
+++ linux-2.6/kernel/sched.c	2008-03-11 17:55:57.000000000 +0100
@@ -7112,7 +7113,7 @@ static void init_tg_cfs_entry(struct rq 
 	se->cfs_rq = &rq->cfs;
 	se->my_q = cfs_rq;
 	se->load.weight = tg->shares;
-	se->load.inv_weight = div64_64(1ULL<<32, se->load.weight);
+	se->load.inv_weight = div64_u64(1ULL<<32, se->load.weight);
 	se->parent = NULL;
 }
 #endif
@@ -7649,7 +7650,7 @@ static void set_se_shares(struct sched_e
 		dequeue_entity(cfs_rq, se, 0);
 
 	se->load.weight = shares;
-	se->load.inv_weight = div64_64((1ULL<<32), shares);
+	se->load.inv_weight = div64_u64((1ULL<<32), shares);
 
 	if (on_rq)
 		enqueue_entity(cfs_rq, se, 0);
@@ -7722,7 +7723,7 @@ static unsigned long to_ratio(u64 period
 	if (runtime == RUNTIME_INF)
 		return 1ULL << 16;
 
-	return div64_64(runtime << 16, period);
+	return div64_u64(runtime << 16, period);
 }
 
 static int __rt_schedulable(struct task_group *tg, u64 period, u64 runtime)
Index: linux-2.6/kernel/sched_debug.c
===================================================================
--- linux-2.6.orig/kernel/sched_debug.c	2008-03-11 17:15:14.000000000 +0100
+++ linux-2.6/kernel/sched_debug.c	2008-03-11 17:53:57.000000000 +0100
@@ -331,8 +331,8 @@ void proc_sched_show_task(struct task_st
 
 		avg_per_cpu = p->se.sum_exec_runtime;
 		if (p->se.nr_migrations) {
-			avg_per_cpu = div64_64(avg_per_cpu,
-					       p->se.nr_migrations);
+			avg_per_cpu = div64_u64(avg_per_cpu,
+						p->se.nr_migrations);
 		} else {
 			avg_per_cpu = -1LL;
 		}
Index: linux-2.6/lib/div64.c
===================================================================
--- linux-2.6.orig/lib/div64.c	2008-03-11 17:48:17.000000000 +0100
+++ linux-2.6/lib/div64.c	2008-03-11 17:53:57.000000000 +0100
@@ -78,9 +78,10 @@ EXPORT_SYMBOL(div_s64_rem);
 #endif
 
 /* 64bit divisor, dividend and result. dynamic precision */
-uint64_t div64_64(uint64_t dividend, uint64_t divisor)
+#ifndef div64_u64
+u64 div64_u64(u64 dividend, u64 divisor)
 {
-	uint32_t high, d;
+	u32 high, d;
 
 	high = divisor >> 32;
 	if (high) {
@@ -91,10 +92,9 @@ uint64_t div64_64(uint64_t dividend, uin
 	} else
 		d = divisor;
 
-	do_div(dividend, d);
-
-	return dividend;
+	return div_u64(dividend, d);
 }
-EXPORT_SYMBOL(div64_64);
+EXPORT_SYMBOL(div64_u64);
+#endif
 
 #endif /* BITS_PER_LONG == 32 */
Index: linux-2.6/net/ipv4/tcp_cubic.c
===================================================================
--- linux-2.6.orig/net/ipv4/tcp_cubic.c	2008-03-11 17:15:14.000000000 +0100
+++ linux-2.6/net/ipv4/tcp_cubic.c	2008-03-11 17:53:57.000000000 +0100
@@ -14,8 +14,8 @@
 
 #include <linux/mm.h>
 #include <linux/module.h>
+#include <linux/math64.h>
 #include <net/tcp.h>
-#include <asm/div64.h>
 
 #define BICTCP_BETA_SCALE    1024	/* Scale factor beta calculation
 					 * max_cwnd = snd_cwnd * beta
@@ -134,7 +134,7 @@ static u32 cubic_root(u64 a)
 	 * x    = ( 2 * x  +  a / x  ) / 3
 	 *  k+1          k         k
 	 */
-	x = (2 * x + (u32)div64_64(a, (u64)x * (u64)(x - 1)));
+	x = (2 * x + (u32)div64_u64(a, (u64)x * (u64)(x - 1)));
 	x = ((x * 341) >> 10);
 	return x;
 }
Index: linux-2.6/net/netfilter/xt_connbytes.c
===================================================================
--- linux-2.6.orig/net/netfilter/xt_connbytes.c	2008-03-11 17:15:14.000000000 +0100
+++ linux-2.6/net/netfilter/xt_connbytes.c	2008-03-11 17:53:57.000000000 +0100
@@ -4,12 +4,11 @@
 #include <linux/module.h>
 #include <linux/bitops.h>
 #include <linux/skbuff.h>
+#include <linux/math64.h>
 #include <linux/netfilter/x_tables.h>
 #include <linux/netfilter/xt_connbytes.h>
 #include <net/netfilter/nf_conntrack.h>
 
-#include <asm/div64.h>
-
 MODULE_LICENSE("GPL");
 MODULE_AUTHOR("Harald Welte <laforge@netfilter.org>");
 MODULE_DESCRIPTION("Xtables: Number of packets/bytes per connection matching");
@@ -82,7 +81,7 @@ connbytes_mt(const struct sk_buff *skb, 
 			break;
 		}
 		if (pkts != 0)
-			what = div64_64(bytes, pkts);
+			what = div64_u64(bytes, pkts);
 		break;
 	}
 

-- 

[PATCH 4/4] remove div_long_long_rem

[zippel]

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

x86 is the only arch right now, which provides an optimized for
div_long_long_rem and it has the downside that one has to be very
careful that the divide doesn't overflow.
The API is a little akward, as the arguments for the unsigned divide
are signed. The signed version also doesn't handle a negative divisor
and produces worse code on 64bit archs.
There is little incentive to keep this API alive, so this converts the
few users to the new API.

Signed-off-by: Roman Zippel <zippel@linux-m68k.org>

---
 arch/mips/kernel/binfmt_elfn32.c |    5 ++-
 arch/mips/kernel/binfmt_elfo32.c |    5 ++-
 drivers/char/mmtimer.c           |   24 ++++++++-----------
 include/asm-x86/div64.h          |   19 ---------------
 include/linux/calc64.h           |   49 ---------------------------------------
 include/linux/jiffies.h          |    2 -
 kernel/posix-cpu-timers.c        |   11 +++-----
 kernel/time.c                    |   25 +++++++++++--------
 kernel/time/ntp.c                |    6 +---
 mm/slub.c                        |    9 +++----
 10 files changed, 44 insertions(+), 111 deletions(-)

Index: linux-2.6/arch/mips/kernel/binfmt_elfn32.c
===================================================================
--- linux-2.6.orig/arch/mips/kernel/binfmt_elfn32.c	2008-03-12 17:20:15.000000000 +0100
+++ linux-2.6/arch/mips/kernel/binfmt_elfn32.c	2008-03-12 17:21:47.000000000 +0100
@@ -54,6 +54,7 @@ typedef elf_fpreg_t elf_fpregset_t[ELF_N
 #include <linux/module.h>
 #include <linux/elfcore.h>
 #include <linux/compat.h>
+#include <linux/math64.h>
 
 #define elf_prstatus elf_prstatus32
 struct elf_prstatus32
@@ -102,8 +103,8 @@ jiffies_to_compat_timeval(unsigned long 
 	 * one divide.
 	 */
 	u64 nsec = (u64)jiffies * TICK_NSEC;
-	long rem;
-	value->tv_sec = div_long_long_rem(nsec, NSEC_PER_SEC, &rem);
+	u32 rem;
+	value->tv_sec = div_u64_rem(nsec, NSEC_PER_SEC, &rem);
 	value->tv_usec = rem / NSEC_PER_USEC;
 }
 
Index: linux-2.6/arch/mips/kernel/binfmt_elfo32.c
===================================================================
--- linux-2.6.orig/arch/mips/kernel/binfmt_elfo32.c	2008-03-12 17:20:16.000000000 +0100
+++ linux-2.6/arch/mips/kernel/binfmt_elfo32.c	2008-03-12 17:21:47.000000000 +0100
@@ -56,6 +56,7 @@ typedef elf_fpreg_t elf_fpregset_t[ELF_N
 #include <linux/module.h>
 #include <linux/elfcore.h>
 #include <linux/compat.h>
+#include <linux/math64.h>
 
 #define elf_prstatus elf_prstatus32
 struct elf_prstatus32
@@ -104,8 +105,8 @@ jiffies_to_compat_timeval(unsigned long 
 	 * one divide.
 	 */
 	u64 nsec = (u64)jiffies * TICK_NSEC;
-	long rem;
-	value->tv_sec = div_long_long_rem(nsec, NSEC_PER_SEC, &rem);
+	u32 rem;
+	value->tv_sec = div_u64_rem(nsec, NSEC_PER_SEC, &rem);
 	value->tv_usec = rem / NSEC_PER_USEC;
 }
 
Index: linux-2.6/drivers/char/mmtimer.c
===================================================================
--- linux-2.6.orig/drivers/char/mmtimer.c	2008-03-12 17:20:15.000000000 +0100
+++ linux-2.6/drivers/char/mmtimer.c	2008-03-12 17:21:47.000000000 +0100
@@ -30,6 +30,8 @@
 #include <linux/miscdevice.h>
 #include <linux/posix-timers.h>
 #include <linux/interrupt.h>
+#include <linux/time.h>
+#include <linux/math64.h>
 
 #include <asm/uaccess.h>
 #include <asm/sn/addrs.h>
@@ -366,8 +368,8 @@ static int sgi_clock_get(clockid_t clock
 
 	nsec = rtc_time() * sgi_clock_period
 			+ sgi_clock_offset.tv_nsec;
-	tp->tv_sec = div_long_long_rem(nsec, NSEC_PER_SEC, &tp->tv_nsec)
-			+ sgi_clock_offset.tv_sec;
+	*tp = ns_to_timespec(nsec);
+	tp->tv_sec += sgi_clock_offset.tv_sec;
 	return 0;
 };
 
@@ -375,11 +377,11 @@ static int sgi_clock_set(clockid_t clock
 {
 
 	u64 nsec;
-	u64 rem;
+	u32 rem;
 
 	nsec = rtc_time() * sgi_clock_period;
 
-	sgi_clock_offset.tv_sec = tp->tv_sec - div_long_long_rem(nsec, NSEC_PER_SEC, &rem);
+	sgi_clock_offset.tv_sec = tp->tv_sec - div_u64_rem(nsec, NSEC_PER_SEC, &rem);
 
 	if (rem <= tp->tv_nsec)
 		sgi_clock_offset.tv_nsec = tp->tv_sec - rem;
@@ -532,9 +534,6 @@ static int sgi_timer_del(struct k_itimer
 	return 0;
 }
 
-#define timespec_to_ns(x) ((x).tv_nsec + (x).tv_sec * NSEC_PER_SEC)
-#define ns_to_timespec(ts, nsec) (ts).tv_sec = div_long_long_rem(nsec, NSEC_PER_SEC, &(ts).tv_nsec)
-
 /* Assumption: it_lock is already held with irq's disabled */
 static void sgi_timer_get(struct k_itimer *timr, struct itimerspec *cur_setting)
 {
@@ -547,9 +546,8 @@ static void sgi_timer_get(struct k_itime
 		return;
 	}
 
-	ns_to_timespec(cur_setting->it_interval, timr->it.mmtimer.incr * sgi_clock_period);
-	ns_to_timespec(cur_setting->it_value, (timr->it.mmtimer.expires - rtc_time())* sgi_clock_period);
-	return;
+	cur_setting->it_interval = ns_to_timespec(timr->it.mmtimer.incr * sgi_clock_period);
+	cur_setting->it_value = ns_to_timespec((timr->it.mmtimer.expires - rtc_time()) * sgi_clock_period);
 }
 
 
@@ -568,8 +566,8 @@ static int sgi_timer_set(struct k_itimer
 		sgi_timer_get(timr, old_setting);
 
 	sgi_timer_del(timr);
-	when = timespec_to_ns(new_setting->it_value);
-	period = timespec_to_ns(new_setting->it_interval);
+	when = timespec_to_ns(&new_setting->it_value);
+	period = timespec_to_ns(&new_setting->it_interval);
 
 	if (when == 0)
 		/* Clear timer */
@@ -580,7 +578,7 @@ static int sgi_timer_set(struct k_itimer
 		unsigned long now;
 
 		getnstimeofday(&n);
-		now = timespec_to_ns(n);
+		now = timespec_to_ns(&n);
 		if (when > now)
 			when -= now;
 		else
Index: linux-2.6/include/asm-x86/div64.h
===================================================================
--- linux-2.6.orig/include/asm-x86/div64.h	2008-03-12 17:20:15.000000000 +0100
+++ linux-2.6/include/asm-x86/div64.h	2008-03-12 17:21:47.000000000 +0100
@@ -31,25 +31,6 @@
 	__mod; \
 })
 
-/*
- * (long)X = ((long long)divs) / (long)div
- * (long)rem = ((long long)divs) % (long)div
- *
- * Warning, this will do an exception if X overflows.
- */
-#define div_long_long_rem(a,b,c) div_ll_X_l_rem(a,b,c)
-
-static inline long
-div_ll_X_l_rem(long long divs, long div, long *rem)
-{
-	long dum2;
-      __asm__("divl %2":"=a"(dum2), "=d"(*rem)
-      :	"rm"(div), "A"(divs));
-
-	return dum2;
-
-}
-
 static inline u64 div_u64_rem(u64 dividend, u32 divisor, u32 *remainder)
 {
 	union {
Index: linux-2.6/include/linux/calc64.h
===================================================================
--- linux-2.6.orig/include/linux/calc64.h	2008-03-12 17:20:15.000000000 +0100
+++ /dev/null	1970-01-01 00:00:00.000000000 +0000
@@ -1,49 +0,0 @@
-#ifndef _LINUX_CALC64_H
-#define _LINUX_CALC64_H
-
-#include <linux/types.h>
-#include <asm/div64.h>
-
-/*
- * This is a generic macro which is used when the architecture
- * specific div64.h does not provide a optimized one.
- *
- * The 64bit dividend is divided by the divisor (data type long), the
- * result is returned and the remainder stored in the variable
- * referenced by remainder (data type long *). In contrast to the
- * do_div macro the dividend is kept intact.
- */
-#ifndef div_long_long_rem
-#define div_long_long_rem(dividend, divisor, remainder)	\
-	do_div_llr((dividend), divisor, remainder)
-
-static inline unsigned long do_div_llr(const long long dividend,
-				       const long divisor, long *remainder)
-{
-	u64 result = dividend;
-
-	*(remainder) = do_div(result, divisor);
-	return (unsigned long) result;
-}
-#endif
-
-/*
- * Sign aware variation of the above. On some architectures a
- * negative dividend leads to an divide overflow exception, which
- * is avoided by the sign check.
- */
-static inline long div_long_long_rem_signed(const long long dividend,
-					    const long divisor, long *remainder)
-{
-	long res;
-
-	if (unlikely(dividend < 0)) {
-		res = -div_long_long_rem(-dividend, divisor, remainder);
-		*remainder = -(*remainder);
-	} else
-		res = div_long_long_rem(dividend, divisor, remainder);
-
-	return res;
-}
-
-#endif
Index: linux-2.6/include/linux/jiffies.h
===================================================================
--- linux-2.6.orig/include/linux/jiffies.h	2008-03-12 17:20:15.000000000 +0100
+++ linux-2.6/include/linux/jiffies.h	2008-03-12 17:21:47.000000000 +0100
@@ -1,7 +1,7 @@
 #ifndef _LINUX_JIFFIES_H
 #define _LINUX_JIFFIES_H
 
-#include <linux/calc64.h>
+#include <linux/math64.h>
 #include <linux/kernel.h>
 #include <linux/types.h>
 #include <linux/time.h>
Index: linux-2.6/kernel/posix-cpu-timers.c
===================================================================
--- linux-2.6.orig/kernel/posix-cpu-timers.c	2008-03-12 17:20:16.000000000 +0100
+++ linux-2.6/kernel/posix-cpu-timers.c	2008-03-12 17:21:47.000000000 +0100
@@ -4,8 +4,9 @@
 
 #include <linux/sched.h>
 #include <linux/posix-timers.h>
-#include <asm/uaccess.h>
 #include <linux/errno.h>
+#include <linux/math64.h>
+#include <asm/uaccess.h>
 
 static int check_clock(const clockid_t which_clock)
 {
@@ -47,12 +48,10 @@ static void sample_to_timespec(const clo
 			       union cpu_time_count cpu,
 			       struct timespec *tp)
 {
-	if (CPUCLOCK_WHICH(which_clock) == CPUCLOCK_SCHED) {
-		tp->tv_sec = div_long_long_rem(cpu.sched,
-					       NSEC_PER_SEC, &tp->tv_nsec);
-	} else {
+	if (CPUCLOCK_WHICH(which_clock) == CPUCLOCK_SCHED)
+		*tp = ns_to_timespec(cpu.sched);
+	else
 		cputime_to_timespec(cpu.cpu, tp);
-	}
 }
 
 static inline int cpu_time_before(const clockid_t which_clock,
Index: linux-2.6/kernel/time.c
===================================================================
--- linux-2.6.orig/kernel/time.c	2008-03-12 17:20:16.000000000 +0100
+++ linux-2.6/kernel/time.c	2008-03-12 17:21:47.000000000 +0100
@@ -390,13 +390,17 @@ void set_normalized_timespec(struct time
 struct timespec ns_to_timespec(const s64 nsec)
 {
 	struct timespec ts;
+	s32 rem;
 
 	if (!nsec)
 		return (struct timespec) {0, 0};
 
-	ts.tv_sec = div_long_long_rem_signed(nsec, NSEC_PER_SEC, &ts.tv_nsec);
-	if (unlikely(nsec < 0))
-		set_normalized_timespec(&ts, ts.tv_sec, ts.tv_nsec);
+	ts.tv_sec = div_s64_rem(nsec, NSEC_PER_SEC, &rem);
+	if (unlikely(rem < 0)) {
+		ts.tv_sec--;
+		rem += NSEC_PER_SEC;
+	}
+	ts.tv_nsec = rem;
 
 	return ts;
 }
@@ -526,8 +530,10 @@ jiffies_to_timespec(const unsigned long 
 	 * Convert jiffies to nanoseconds and separate with
 	 * one divide.
 	 */
-	u64 nsec = (u64)jiffies * TICK_NSEC;
-	value->tv_sec = div_long_long_rem(nsec, NSEC_PER_SEC, &value->tv_nsec);
+	u32 rem;
+	value->tv_sec = div_u64_rem((u64)jiffies * TICK_NSEC,
+				    NSEC_PER_SEC, &rem);
+	value->tv_nsec = rem;
 }
 EXPORT_SYMBOL(jiffies_to_timespec);
 
@@ -565,12 +571,11 @@ void jiffies_to_timeval(const unsigned l
 	 * Convert jiffies to nanoseconds and separate with
 	 * one divide.
 	 */
-	u64 nsec = (u64)jiffies * TICK_NSEC;
-	long tv_usec;
+	u32 rem;
 
-	value->tv_sec = div_long_long_rem(nsec, NSEC_PER_SEC, &tv_usec);
-	tv_usec /= NSEC_PER_USEC;
-	value->tv_usec = tv_usec;
+	value->tv_sec = div_u64_rem((u64)jiffies * TICK_NSEC,
+				    NSEC_PER_SEC, &rem);
+	value->tv_usec = rem / NSEC_PER_USEC;
 }
 EXPORT_SYMBOL(jiffies_to_timeval);
 
Index: linux-2.6/kernel/time/ntp.c
===================================================================
--- linux-2.6.orig/kernel/time/ntp.c	2008-03-12 17:20:16.000000000 +0100
+++ linux-2.6/kernel/time/ntp.c	2008-03-12 17:21:47.000000000 +0100
@@ -234,7 +234,7 @@ static inline void notify_cmos_timer(voi
  */
 int do_adjtimex(struct timex *txc)
 {
-	long mtemp, save_adjust, rem;
+	long mtemp, save_adjust;
 	s64 freq_adj;
 	int result;
 
@@ -345,9 +345,7 @@ int do_adjtimex(struct timex *txc)
 		    freq_adj += time_freq;
 		    freq_adj = min(freq_adj, (s64)MAXFREQ_NSEC);
 		    time_freq = max(freq_adj, (s64)-MAXFREQ_NSEC);
-		    time_offset = div_long_long_rem_signed(time_offset,
-							   NTP_INTERVAL_FREQ,
-							   &rem);
+		    time_offset = div_s64(time_offset, NTP_INTERVAL_FREQ);
 		    time_offset <<= SHIFT_UPDATE;
 		} /* STA_PLL */
 	    } /* txc->modes & ADJ_OFFSET */
Index: linux-2.6/mm/slub.c
===================================================================
--- linux-2.6.orig/mm/slub.c	2008-03-12 17:20:15.000000000 +0100
+++ linux-2.6/mm/slub.c	2008-03-12 17:21:47.000000000 +0100
@@ -21,6 +21,7 @@
 #include <linux/ctype.h>
 #include <linux/kallsyms.h>
 #include <linux/memory.h>
+#include <linux/math64.h>
 
 /*
  * Lock order:
@@ -3515,12 +3516,10 @@ static int list_locations(struct kmem_ca
 			len += sprintf(buf + len, "<not-available>");
 
 		if (l->sum_time != l->min_time) {
-			unsigned long remainder;
-
 			len += sprintf(buf + len, " age=%ld/%ld/%ld",
-			l->min_time,
-			div_long_long_rem(l->sum_time, l->count, &remainder),
-			l->max_time);
+				l->min_time,
+				(long)div_u64(l->sum_time, l->count),
+				l->max_time);
 		} else
 			len += sprintf(buf + len, " age=%ld",
 				l->min_time);

-- 

[PATCH 5/4] 2.6.25-rc5-mm1 specifc div64_u64 fixes

[zippel]

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

Rename a few more div64_u64 which are only in -mm.

Signed-off-by: Roman Zippel <zippel@linux-m68k.org>

---
 arch/x86/kvm/i8254.c |    6 +++---
 kernel/time.c        |    2 +-
 2 files changed, 4 insertions(+), 4 deletions(-)

Index: linux-2.6-mm/arch/x86/kvm/i8254.c
===================================================================
--- linux-2.6-mm.orig/arch/x86/kvm/i8254.c
+++ linux-2.6-mm/arch/x86/kvm/i8254.c
@@ -35,7 +35,7 @@
 #include "i8254.h"
 
 #ifndef CONFIG_X86_64
-#define mod_64(x, y) ((x) - (y) * div64_64(x, y))
+#define mod_64(x, y) ((x) - (y) * div64_u64(x, y))
 #else
 #define mod_64(x, y) ((x) % (y))
 #endif
@@ -60,8 +60,8 @@ static u64 muldiv64(u64 a, u32 b, u32 c)
 	rl = (u64)u.l.low * (u64)b;
 	rh = (u64)u.l.high * (u64)b;
 	rh += (rl >> 32);
-	res.l.high = div64_64(rh, c);
-	res.l.low = div64_64(((mod_64(rh, c) << 32) + (rl & 0xffffffff)), c);
+	res.l.high = div64_u64(rh, c);
+	res.l.low = div64_u64(((mod_64(rh, c) << 32) + (rl & 0xffffffff)), c);
 	return res.ll;
 }
 
Index: linux-2.6-mm/kernel/time.c
===================================================================
--- linux-2.6-mm.orig/kernel/time.c
+++ linux-2.6-mm/kernel/time.c
@@ -272,7 +272,7 @@ EXPORT_SYMBOL(jiffies_to_usecs);
 
 u64 jiffies_64_to_usecs(const u64 j)
 {
-	return div64_64(j*HZ_TO_USEC_NUM + HZ_TO_USEC_DEN-1, HZ_TO_USEC_DEN);
+	return div64_u64(j*HZ_TO_USEC_NUM + HZ_TO_USEC_DEN-1, HZ_TO_USEC_DEN);
 }
 EXPORT_SYMBOL(jiffies_64_to_usecs);
 

-- 

Re: [PATCH 1/4] introduce explicit signed/unsigned 64bit divide

[Geert Uytterhoeven]

[-- Attachment #1: Type: TEXT/PLAIN, Size: 1961 bytes --]

On Thu, 13 Mar 2008, zippel@linux-m68k.org wrote:
> --- /dev/null	1970-01-01 00:00:00.000000000 +0000
> +++ linux-2.6/include/linux/math64.h	2008-03-12 21:21:26.000000000 +0100
> @@ -0,0 +1,72 @@
> +#ifndef _LINUX_MATH64_H
> +#define _LINUX_MATH64_H
> +
> +#include <linux/types.h>
> +#include <asm/div64.h>
> +
> +#if BITS_PER_LONG == 64
> +
> +/**
> + * div_u64_rem - unsigned 64bit divide with 32bit divisor with remainder
> + *
> + * This is commonly provided by 32bit archs to provide an optimized 64bit
> + * divide.
> + */
> +static inline u64 div_u64_rem(u64 dividend, u32 divisor, u32 *remainder)
> +{
> +	*remainder = dividend % divisor;
> +	return dividend / divisor;
> +}
> +
> +/**
> + * div_s64_rem - signed 64bit divide with 32bit divisor with remainder
> + */
> +static inline u64 div_u64_rem(u64 dividend, u32 divisor, u32 *remainder)
                 ^       ^       ^             ^            ^
		 s64 div_s64_rem s64           s32          s32
> +{
> +	*remainder = dividend % divisor;
> +	return dividend / divisor;
> +}
> +
> +#elif BITS_PER_LONG == 32
> +
> +#ifndef div_u64_rem
> +static inline u64 div_u64_rem(u64 dividend, u32 divisor, u32 *remainder)
> +{
> +	*remainder = do_div(dividend, divisor);
> +	return dividend;
> +}
> +#endif
> +
> +#ifndef div_s64_rem
> +extern s64 div_s64_rem(s64 dividend, s32 divisor, s32 *remainder);
> +#endif

With kind regards,

Geert Uytterhoeven
Software Architect

Sony Network and Software Technology Center Europe
The Corporate Village · Da Vincilaan 7-D1 · B-1935 Zaventem · Belgium

Phone:    +32 (0)2 700 8453
Fax:      +32 (0)2 700 8622
E-mail:   Geert.Uytterhoeven@sonycom.com
Internet: http://www.sony-europe.com/

Sony Network and Software Technology Center Europe
A division of Sony Service Centre (Europe) N.V.
Registered office: Technologielaan 7 · B-1840 Londerzeel · Belgium
VAT BE 0413.825.160 · RPR Brussels
Fortis Bank Zaventem · Swift GEBABEBB08A · IBAN BE39001382358619

Re: [PATCH 1/4] introduce explicit signed/unsigned 64bit divide

[Roman Zippel]

Hi,

On Thu, 13 Mar 2008, Geert Uytterhoeven wrote:

> > +static inline u64 div_u64_rem(u64 dividend, u32 divisor, u32 *remainder)
>                  ^       ^       ^             ^            ^
> 		 s64 div_s64_rem s64           s32          s32

Thanks for noticing.
I'm quite sure I fixed this before, as I compiled this also for 
64bit, so I'm not sure how it got back. Anyway, new patch below.

bye, Roman



[PATCH 1/4] introduce explicit signed/unsigned 64bit divide

The current do_div doesn't explicitly say that it's unsigned and the
signed counterpart is missing, which is e.g. needed when dealing with
time values.
This introduces 64bit signed/unsigned divide functions which also
attempts to cleanup the somewhat awkward calling API, which often
requires the use of temporary variables for the dividend. To avoid the
need for temporary variables everywhere for the remainder, each divide
variant also provides a version which doesn't return the remainder.

Each architecture can now provide optimized versions of these function,
otherwise generic fallback implementations will be used.

As an example I provided an alternative for the current x86 divide,
which avoids the asm casts and using an union allows gcc to generate
better code. It also avoids the upper divde in a few more cases, where
the result is known (i.e. upper quotient is zero).

Signed-off-by: Roman Zippel <zippel@linux-m68k.org>

---
 include/asm-x86/div64.h |   20 +++++++++++++
 include/linux/math64.h  |   72 ++++++++++++++++++++++++++++++++++++++++++++++++
 lib/div64.c             |   23 ++++++++++++++-
 3 files changed, 113 insertions(+), 2 deletions(-)

Index: linux-2.6/include/asm-x86/div64.h
===================================================================
--- linux-2.6.orig/include/asm-x86/div64.h	2008-03-11 17:15:21.000000000 +0100
+++ linux-2.6/include/asm-x86/div64.h	2008-03-12 21:21:26.000000000 +0100
@@ -50,6 +50,26 @@ div_ll_X_l_rem(long long divs, long div,
 
 }
 
+static inline u64 div_u64_rem(u64 dividend, u32 divisor, u32 *remainder)
+{
+	union {
+		u64 v64;
+		u32 v32[2];
+	} d = { dividend };
+	u32 upper;
+
+	upper = d.v32[1];
+	d.v32[1] = 0;
+	if (upper >= divisor) {
+		d.v32[1] = upper / divisor;
+		upper %= divisor;
+	}
+	asm ("divl %2" : "=a" (d.v32[0]), "=d" (*remainder) :
+		"rm" (divisor), "0" (d.v32[0]), "1" (upper));
+	return d.v64;
+}
+#define div_u64_rem	div_u64_rem
+
 extern uint64_t div64_64(uint64_t dividend, uint64_t divisor);
 
 #else
Index: linux-2.6/lib/div64.c
===================================================================
--- linux-2.6.orig/lib/div64.c	2008-03-11 17:15:21.000000000 +0100
+++ linux-2.6/lib/div64.c	2008-03-12 21:21:26.000000000 +0100
@@ -16,9 +16,8 @@
  * assembly versions such as arch/ppc/lib/div64.S and arch/sh/lib/div64.S.
  */
 
-#include <linux/types.h>
 #include <linux/module.h>
-#include <asm/div64.h>
+#include <linux/math64.h>
 
 /* Not needed on 64bit architectures */
 #if BITS_PER_LONG == 32
@@ -58,6 +57,26 @@ uint32_t __attribute__((weak)) __div64_3
 
 EXPORT_SYMBOL(__div64_32);
 
+#ifndef div_s64_rem
+s64 div_s64_rem(s64 dividend, s32 divisor, s32 *remainder)
+{
+	u64 quotient;
+
+	if (dividend < 0) {
+		quotient = div_u64_rem(-dividend, abs(divisor), (u32 *)remainder);
+		*remainder = -*remainder;
+		if (divisor > 0)
+			quotient = -quotient;
+	} else {
+		quotient = div_u64_rem(dividend, abs(divisor), (u32 *)remainder);
+		if (divisor < 0)
+			quotient = -quotient;
+	}
+	return quotient;
+}
+EXPORT_SYMBOL(div_s64_rem);
+#endif
+
 /* 64bit divisor, dividend and result. dynamic precision */
 uint64_t div64_64(uint64_t dividend, uint64_t divisor)
 {
Index: linux-2.6/include/linux/math64.h
===================================================================
--- /dev/null	1970-01-01 00:00:00.000000000 +0000
+++ linux-2.6/include/linux/math64.h	2008-03-12 21:21:26.000000000 +0100
@@ -0,0 +1,72 @@
+#ifndef _LINUX_MATH64_H
+#define _LINUX_MATH64_H
+
+#include <linux/types.h>
+#include <asm/div64.h>
+
+#if BITS_PER_LONG == 64
+
+/**
+ * div_u64_rem - unsigned 64bit divide with 32bit divisor with remainder
+ *
+ * This is commonly provided by 32bit archs to provide an optimized 64bit
+ * divide.
+ */
+static inline u64 div_u64_rem(u64 dividend, u32 divisor, u32 *remainder)
+{
+	*remainder = dividend % divisor;
+	return dividend / divisor;
+}
+
+/**
+ * div_s64_rem - signed 64bit divide with 32bit divisor with remainder
+ */
+static inline s64 div_s64_rem(s64 dividend, s32 divisor, s32 *remainder)
+{
+	*remainder = dividend % divisor;
+	return dividend / divisor;
+}
+
+#elif BITS_PER_LONG == 32
+
+#ifndef div_u64_rem
+static inline u64 div_u64_rem(u64 dividend, u32 divisor, u32 *remainder)
+{
+	*remainder = do_div(dividend, divisor);
+	return dividend;
+}
+#endif
+
+#ifndef div_s64_rem
+extern s64 div_s64_rem(s64 dividend, s32 divisor, s32 *remainder);
+#endif
+
+#endif /* BITS_PER_LONG */
+
+/**
+ * div_u64 - unsigned 64bit divide with 32bit divisor
+ *
+ * This is the most common 64bit divide and should be used if possible,
+ * as many 32bit archs can optimize this variant better than a full 64bit
+ * divide.
+ */
+#ifndef div_u64
+static inline u64 div_u64(u64 dividend, u32 divisor)
+{
+	u32 remainder;
+	return div_u64_rem(dividend, divisor, &remainder);
+}
+#endif
+
+/**
+ * div_s64 - signed 64bit divide with 32bit divisor
+ */
+#ifndef div_s64
+static inline s64 div_s64(s64 dividend, s32 divisor)
+{
+	s32 remainder;
+	return div_s64_rem(dividend, divisor, &remainder);
+}
+#endif
+
+#endif /* _LINUX_MATH64_H */

Re: [PATCH 1/4] introduce explicit signed/unsigned 64bit divide

[Andrew Morton]

On Thu, 13 Mar 2008 15:59:27 +0100 (CET)
Roman Zippel <zippel@linux-m68k.org> wrote:

> On Thu, 13 Mar 2008, Geert Uytterhoeven wrote:
> 
> > > +static inline u64 div_u64_rem(u64 dividend, u32 divisor, u32 *remainder)
> >                  ^       ^       ^             ^            ^
> > 		 s64 div_s64_rem s64           s32          s32
> 
> Thanks for noticing.
> I'm quite sure I fixed this before, as I compiled this also for 
> 64bit, so I'm not sure how it got back. Anyway, new patch below.

I think what happened was that [patch 3/4] fixed this up.  Of course,
that patch doesn't apply on this updated [1/4].  I _could_ just take the
old [1/4] (I think), but I don't know if that wouild be bisection-friendly.

Anyway, please redo&resend?  Thanks.



Please have a think about that code in arch/x86/kvm/i8254.c too.  It is
painful to see remote subsystems (re)implementing generic infrastructure.
Can KVM use existing code?  Should we hoist what KVM has done there into
generic code?  Did it have to use a(nother bleeding) macro?

Re: [PATCH 1/4] introduce explicit signed/unsigned 64bit divide

[Roman Zippel]

Hi,

On Thu, 13 Mar 2008, Andrew Morton wrote:

> I think what happened was that [patch 3/4] fixed this up.  Of course,
> that patch doesn't apply on this updated [1/4].  I _could_ just take the
> old [1/4] (I think), but I don't know if that wouild be bisection-friendly.
> 
> Anyway, please redo&resend?  Thanks.

Done.

> Please have a think about that code in arch/x86/kvm/i8254.c too.  It is
> painful to see remote subsystems (re)implementing generic infrastructure.
> Can KVM use existing code?  Should we hoist what KVM has done there into
> generic code?  Did it have to use a(nother bleeding) macro?

Looker closer at it, div64_u64() seems to be a bit overkill, as the 
divisor is a 32bit value, so the following should do the same job (only 
compile tested):

u64 muldiv64(u64 a, u32 b, u32 c)
{       
	union { 
		u64 ll;
		struct {
			u32 low, high;
		};
	} u, res, rl, rh;

	u.ll = a;
	rl.ll = (u64)b * u.low;
	rh.ll = (u64)b * u.high;
	rh.ll += rl.high;
	res.high = div_u64_rem(rh.ll, c, &rl.high);
	res.low = div_u64(rl.ll, c);
	return res.ll;
}

Moving it to a more generic location shouldn't be a big problem.

bye, Roman

Re: [PATCH 2/4] convert a few do_div user

[Jörg-Volker Peetz]

zippel@linux-m68k.org wrote:
> This converts a few users of do_div to div_[su]64 and this demonstrates
> nicely how it can reduce some expressions to one-liners.
> 
> Signed-off-by: Roman Zippel <zippel@linux-m68k.org>
> 
> ---
>  kernel/time.c     |   29 +++++++++--------------------
>  kernel/time/ntp.c |   25 ++++++-------------------
>  2 files changed, 15 insertions(+), 39 deletions(-)
> 
<snip>
> Index: linux-2.6/kernel/time/ntp.c
> ===================================================================
> --- linux-2.6.orig/kernel/time/ntp.c	2008-03-11 17:15:14.000000000 +0100
> +++ linux-2.6/kernel/time/ntp.c	2008-03-12 21:21:20.000000000 +0100
<snip>
>  /*
> @@ -53,10 +53,8 @@ static void ntp_update_frequency(void)
>  
>  	tick_length_base = second_length;
>  
> -	do_div(second_length, HZ);
> -	tick_nsec = second_length >> TICK_LENGTH_SHIFT;
> -
> -	do_div(tick_length_base, NTP_INTERVAL_FREQ);
> +	tick_nsec = div_u64(second_length, HZ) >> TICK_LENGTH_SHIFT;
> +	tick_length_base = div_u64(tick_length_base, NTP_INTERVAL_FREQ);
>  }
>  

Probably the compiler would optimize it, but maybe its clearer to change it this 
way:

- 	tick_length_base = second_length;

-	do_div(second_length, HZ);
-	tick_nsec = second_length >> TICK_LENGTH_SHIFT;
-
-	do_div(tick_length_base, NTP_INTERVAL_FREQ);
+	tick_nsec = div_u64(second_length, HZ) >> TICK_LENGTH_SHIFT;
+	tick_length_base = div_u64(second_length, NTP_INTERVAL_FREQ);

-- 
Regards,
Jörg-Volker.



<snip>