Since there already two users of full 64 bit division in the kernel,
and other places maybe hiding out as well. Add a full 64/64 bit divide.
Yes this expensive, but there are places where it is necessary.
It is not clear if doing the scaling buys any advantage on 64 bit platforms,
so for them a full divide is done.
---
include/asm-arm/div64.h | 2 ++
include/asm-generic/div64.h | 8 ++++++++
include/asm-m68k/div64.h | 2 ++
include/asm-mips/div64.h | 8 ++++++++
include/asm-um/div64.h | 1 +
include/asm-xtensa/div64.h | 1 +
lib/div64.c | 22 ++++++++++++++++++++++
net/ipv4/tcp_cubic.c | 22 ----------------------
net/netfilter/xt_connbytes.c | 16 ----------------
9 files changed, 44 insertions(+), 38 deletions(-)
--- linux-2.6.21-rc1.orig/include/asm-arm/div64.h 2007-02-23 16:44:41.000000000 -0800
+++ linux-2.6.21-rc1/include/asm-arm/div64.h 2007-02-23 16:57:36.000000000 -0800
@@ -221,6 +221,8 @@
__nr; \
})
+extern uint64_t div64_64(uint64_t dividend, uint64_t divisor);
+
#endif
#endif
--- linux-2.6.21-rc1.orig/include/asm-generic/div64.h 2007-02-23 16:35:27.000000000 -0800
+++ linux-2.6.21-rc1/include/asm-generic/div64.h 2007-02-23 16:56:40.000000000 -0800
@@ -30,9 +30,17 @@
__rem; \
})
+/*
+ * div64_64 - Divide two 64 bit numbers
+ */
+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);
+extern uint64_t div64_64(uint64_t dividend, uint64_t divisor);
/* The unnecessary pointer compare is there
* to check for type safety (n must be 64bit)
--- linux-2.6.21-rc1.orig/include/asm-m68k/div64.h 2007-02-23 16:45:20.000000000 -0800
+++ linux-2.6.21-rc1/include/asm-m68k/div64.h 2007-02-23 16:56:27.000000000 -0800
@@ -23,4 +23,6 @@
__rem; \
})
+extern uint64_t div64_64(uint64_t dividend, uint64_t divisor);
+
#endif /* _M68K_DIV64_H */
--- linux-2.6.21-rc1.orig/include/asm-mips/div64.h 2007-02-23 16:45:25.000000000 -0800
+++ linux-2.6.21-rc1/include/asm-mips/div64.h 2007-02-23 16:59:52.000000000 -0800
@@ -78,6 +78,9 @@
__quot = __quot << 32 | __low; \
(n) = __quot; \
__mod; })
+
+extern uint64_t div64_64(uint64_t dividend, uint64_t divisor);
+
#endif /* (_MIPS_SZLONG == 32) */
#if (_MIPS_SZLONG == 64)
@@ -101,6 +104,11 @@
(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 */
--- linux-2.6.21-rc1.orig/include/asm-um/div64.h 2007-02-23 16:45:37.000000000 -0800
+++ linux-2.6.21-rc1/include/asm-um/div64.h 2007-02-23 16:58:29.000000000 -0800
@@ -3,4 +3,5 @@
#include "asm/arch/div64.h"
+extern uint64_t div64_64(uint64_t dividend, uint64_t divisor);
#endif
--- linux-2.6.21-rc1.orig/include/asm-xtensa/div64.h 2007-02-23 16:45:43.000000000 -0800
+++ linux-2.6.21-rc1/include/asm-xtensa/div64.h 2007-02-23 16:58:04.000000000 -0800
@@ -16,4 +16,5 @@
n /= (unsigned int) base; \
__res; })
+extern uint64_t div64_64(uint64_t dividend, uint64_t divisor);
#endif
--- linux-2.6.21-rc1.orig/lib/div64.c 2007-02-23 16:50:40.000000000 -0800
+++ linux-2.6.21-rc1/lib/div64.c 2007-02-23 16:54:56.000000000 -0800
@@ -18,6 +18,7 @@
#include <linux/types.h>
#include <linux/module.h>
+#include <asm/bitops.h>
#include <asm/div64.h>
/* Not needed on 64bit architectures */
@@ -58,4 +59,25 @@
EXPORT_SYMBOL(__div64_32);
+/* Use scaling to do a full 64 bit division */
+uint64_t div64_64(uint64_t dividend, uint64_t divisor)
+{
+ uint32_t d = divisor;
+
+ if (divisor > 0xffffffffULL) {
+ unsigned int shift = fls(divisor >> 32);
+
+ d = divisor >> shift;
+ dividend >>= shift;
+ }
+
+ /* avoid 64 bit division if possible */
+ if (dividend >> 32)
+ do_div(dividend, d);
+ else
+ dividend = (uint32_t) dividend / d;
+
+ return dividend;
+}
+
#endif /* BITS_PER_LONG == 32 */
--- linux-2.6.21-rc1.orig/net/ipv4/tcp_cubic.c 2007-02-23 16:33:52.000000000 -0800
+++ linux-2.6.21-rc1/net/ipv4/tcp_cubic.c 2007-02-23 16:45:50.000000000 -0800
@@ -51,7 +51,6 @@
module_param(tcp_friendliness, int, 0644);
MODULE_PARM_DESC(tcp_friendliness, "turn on/off tcp friendliness");
-#include <asm/div64.h>
/* BIC TCP Parameters */
struct bictcp {
@@ -93,27 +92,6 @@
tcp_sk(sk)->snd_ssthresh = initial_ssthresh;
}
-/* 64bit divisor, dividend and result. dynamic precision */
-static inline u_int64_t div64_64(u_int64_t dividend, u_int64_t divisor)
-{
- u_int32_t d = divisor;
-
- if (divisor > 0xffffffffULL) {
- unsigned int shift = fls(divisor >> 32);
-
- d = divisor >> shift;
- dividend >>= shift;
- }
-
- /* avoid 64 bit division if possible */
- if (dividend >> 32)
- do_div(dividend, d);
- else
- dividend = (uint32_t) dividend / d;
-
- return dividend;
-}
-
/*
* calculate the cubic root of x using Newton-Raphson
*/
--- linux-2.6.21-rc1.orig/net/netfilter/xt_connbytes.c 2007-02-23 16:40:57.000000000 -0800
+++ linux-2.6.21-rc1/net/netfilter/xt_connbytes.c 2007-02-23 16:41:09.000000000 -0800
@@ -24,22 +24,6 @@
MODULE_DESCRIPTION("iptables match for matching number of pkts/bytes per connection");
MODULE_ALIAS("ipt_connbytes");
-/* 64bit divisor, dividend and result. dynamic precision */
-static u_int64_t div64_64(u_int64_t dividend, u_int64_t divisor)
-{
- u_int32_t d = divisor;
-
- if (divisor > 0xffffffffULL) {
- unsigned int shift = fls(divisor >> 32);
-
- d = divisor >> shift;
- dividend >>= shift;
- }
-
- do_div(dividend, d);
- return dividend;
-}
-
static int
match(const struct sk_buff *skb,
const struct net_device *in,
On Fri, Feb 23, 2007 at 17:05:27 -0800, Stephen Hemminger wrote:
> Since there already two users of full 64 bit division in the kernel,
> and other places maybe hiding out as well. Add a full 64/64 bit divide.
>
> Yes this expensive, but there are places where it is necessary.
> It is not clear if doing the scaling buys any advantage on 64 bit platforms,
> so for them a full divide is done.
Still does not work after these fixes... how came?
WARNING: "div64_64" [net/netfilter/xt_connbytes.ko] undefined!
WARNING: "div64_64" [net/ipv4/tcp_cubic.ko] undefined!
--- linux-2.6.19/include/asm-i386/div64.h.bak 2006-11-29 23:57:37.000000000 +0200
+++ linux-2.6.19/include/asm-i386/div64.h 2007-02-24 16:24:55.822529880 +0200
@@ -45,4 +45,7 @@ div_ll_X_l_rem(long long divs, long div,
return dum2;
}
+
+extern uint64_t div64_64(uint64_t dividend, uint64_t divisor);
+
#endif
--- linux-2.6.19/lib/div64.c.bak 2007-02-24 16:10:03.686084000 +0200
+++ linux-2.6.19/lib/div64.c 2007-02-24 17:01:11.224517353 +0200
@@ -80,4 +80,6 @@ uint64_t div64_64(uint64_t dividend, uin
return dividend;
}
+EXPORT_SYMBOL(div64_64);
+
#endif /* BITS_PER_LONG == 32 */
--
asm-i386.h/div64 and div64.o needs to move in Makefile to get this to work
on i386.
---
include/asm-arm/div64.h | 2 ++
include/asm-generic/div64.h | 8 ++++++++
include/asm-i386/div64.h | 5 +++++
include/asm-m68k/div64.h | 2 ++
include/asm-mips/div64.h | 8 ++++++++
include/asm-um/div64.h | 1 +
include/asm-xtensa/div64.h | 1 +
lib/Makefile | 5 +++--
lib/div64.c | 23 +++++++++++++++++++++++
net/ipv4/tcp_cubic.c | 22 ----------------------
net/netfilter/xt_connbytes.c | 16 ----------------
11 files changed, 53 insertions(+), 40 deletions(-)
--- sky2.orig/include/asm-arm/div64.h 2007-02-26 10:17:33.000000000 -0800
+++ sky2/include/asm-arm/div64.h 2007-02-26 10:17:50.000000000 -0800
@@ -221,6 +221,8 @@
__nr; \
})
+extern uint64_t div64_64(uint64_t dividend, uint64_t divisor);
+
#endif
#endif
--- sky2.orig/include/asm-generic/div64.h 2007-02-26 10:17:33.000000000 -0800
+++ sky2/include/asm-generic/div64.h 2007-02-26 10:17:50.000000000 -0800
@@ -30,9 +30,17 @@
__rem; \
})
+/*
+ * div64_64 - Divide two 64 bit numbers
+ */
+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);
+extern uint64_t div64_64(uint64_t dividend, uint64_t divisor);
/* The unnecessary pointer compare is there
* to check for type safety (n must be 64bit)
--- sky2.orig/include/asm-m68k/div64.h 2007-02-26 10:17:33.000000000 -0800
+++ sky2/include/asm-m68k/div64.h 2007-02-26 10:17:50.000000000 -0800
@@ -23,4 +23,6 @@
__rem; \
})
+extern uint64_t div64_64(uint64_t dividend, uint64_t divisor);
+
#endif /* _M68K_DIV64_H */
--- sky2.orig/include/asm-mips/div64.h 2007-02-26 10:17:33.000000000 -0800
+++ sky2/include/asm-mips/div64.h 2007-02-26 10:17:50.000000000 -0800
@@ -78,6 +78,9 @@
__quot = __quot << 32 | __low; \
(n) = __quot; \
__mod; })
+
+extern uint64_t div64_64(uint64_t dividend, uint64_t divisor);
+
#endif /* (_MIPS_SZLONG == 32) */
#if (_MIPS_SZLONG == 64)
@@ -101,6 +104,11 @@
(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 */
--- sky2.orig/include/asm-um/div64.h 2007-02-26 10:17:33.000000000 -0800
+++ sky2/include/asm-um/div64.h 2007-02-26 10:17:50.000000000 -0800
@@ -3,4 +3,5 @@
#include "asm/arch/div64.h"
+extern uint64_t div64_64(uint64_t dividend, uint64_t divisor);
#endif
--- sky2.orig/include/asm-xtensa/div64.h 2007-02-26 10:17:33.000000000 -0800
+++ sky2/include/asm-xtensa/div64.h 2007-02-26 10:17:50.000000000 -0800
@@ -16,4 +16,5 @@
n /= (unsigned int) base; \
__res; })
+extern uint64_t div64_64(uint64_t dividend, uint64_t divisor);
#endif
--- sky2.orig/lib/div64.c 2007-02-26 10:17:33.000000000 -0800
+++ sky2/lib/div64.c 2007-02-26 10:31:49.000000000 -0800
@@ -18,6 +18,7 @@
#include <linux/types.h>
#include <linux/module.h>
+#include <asm/bitops.h>
#include <asm/div64.h>
/* Not needed on 64bit architectures */
@@ -58,4 +59,26 @@
EXPORT_SYMBOL(__div64_32);
+/* Use scaling to do a full 64 bit division */
+uint64_t div64_64(uint64_t dividend, uint64_t divisor)
+{
+ uint32_t d = divisor;
+
+ if (divisor > 0xffffffffULL) {
+ unsigned int shift = fls(divisor >> 32);
+
+ d = divisor >> shift;
+ dividend >>= shift;
+ }
+
+ /* avoid 64 bit division if possible */
+ if (dividend >> 32)
+ do_div(dividend, d);
+ else
+ dividend = (uint32_t) dividend / d;
+
+ return dividend;
+}
+EXPORT_SYMBOL(div64_64);
+
#endif /* BITS_PER_LONG == 32 */
--- sky2.orig/net/ipv4/tcp_cubic.c 2007-02-26 10:17:33.000000000 -0800
+++ sky2/net/ipv4/tcp_cubic.c 2007-02-26 10:17:50.000000000 -0800
@@ -51,7 +51,6 @@
module_param(tcp_friendliness, int, 0644);
MODULE_PARM_DESC(tcp_friendliness, "turn on/off tcp friendliness");
-#include <asm/div64.h>
/* BIC TCP Parameters */
struct bictcp {
@@ -93,27 +92,6 @@
tcp_sk(sk)->snd_ssthresh = initial_ssthresh;
}
-/* 64bit divisor, dividend and result. dynamic precision */
-static inline u_int64_t div64_64(u_int64_t dividend, u_int64_t divisor)
-{
- u_int32_t d = divisor;
-
- if (divisor > 0xffffffffULL) {
- unsigned int shift = fls(divisor >> 32);
-
- d = divisor >> shift;
- dividend >>= shift;
- }
-
- /* avoid 64 bit division if possible */
- if (dividend >> 32)
- do_div(dividend, d);
- else
- dividend = (uint32_t) dividend / d;
-
- return dividend;
-}
-
/*
* calculate the cubic root of x using Newton-Raphson
*/
--- sky2.orig/net/netfilter/xt_connbytes.c 2007-02-26 10:17:33.000000000 -0800
+++ sky2/net/netfilter/xt_connbytes.c 2007-02-26 10:17:50.000000000 -0800
@@ -24,22 +24,6 @@
MODULE_DESCRIPTION("iptables match for matching number of pkts/bytes per connection");
MODULE_ALIAS("ipt_connbytes");
-/* 64bit divisor, dividend and result. dynamic precision */
-static u_int64_t div64_64(u_int64_t dividend, u_int64_t divisor)
-{
- u_int32_t d = divisor;
-
- if (divisor > 0xffffffffULL) {
- unsigned int shift = fls(divisor >> 32);
-
- d = divisor >> shift;
- dividend >>= shift;
- }
-
- do_div(dividend, d);
- return dividend;
-}
-
static int
match(const struct sk_buff *skb,
const struct net_device *in,
--- sky2.orig/include/asm-i386/div64.h 2007-02-26 10:36:29.000000000 -0800
+++ sky2/include/asm-i386/div64.h 2007-02-26 11:07:47.000000000 -0800
@@ -1,6 +1,8 @@
#ifndef __I386_DIV64
#define __I386_DIV64
+#include <linux/types.h>
+
/*
* do_div() is NOT a C function. It wants to return
* two values (the quotient and the remainder), but
@@ -45,4 +47,7 @@
return dum2;
}
+
+extern uint64_t div64_64(uint64_t dividend, uint64_t divisor);
+
#endif
--- sky2.orig/lib/Makefile 2007-02-26 11:24:48.000000000 -0800
+++ sky2/lib/Makefile 2007-02-26 11:26:57.000000000 -0800
@@ -4,7 +4,7 @@
lib-y := ctype.o string.o vsprintf.o cmdline.o \
rbtree.o radix-tree.o dump_stack.o \
- idr.o div64.o int_sqrt.o bitmap.o extable.o prio_tree.o \
+ idr.o int_sqrt.o bitmap.o extable.o prio_tree.o \
sha1.o irq_regs.o reciprocal_div.o
lib-$(CONFIG_MMU) += ioremap.o
@@ -12,7 +12,8 @@
lib-y += kobject.o kref.o kobject_uevent.o klist.o
-obj-y += sort.o parser.o halfmd4.o debug_locks.o random32.o bust_spinlocks.o
+obj-y += sort.o parser.o div64.o halfmd4.o debug_locks.o random32.o \
+ bust_spinlocks.o
ifeq ($(CONFIG_DEBUG_KOBJECT),y)
CFLAGS_kobject.o += -DDEBUG
From: Stephen Hemminger <[email protected]>
Date: Mon, 26 Feb 2007 11:28:18 -0800
> asm-i386.h/div64 and div64.o needs to move in Makefile to get this to work
> on i386.
This looks great to me:
Signed-off-by: David S. Miller <[email protected]>
On Feb 23 2007 17:05, Stephen Hemminger wrote:
>
>Since there already two users of full 64 bit division in the kernel,
>and other places maybe hiding out as well. Add a full 64/64 bit divide.
>
>Yes this expensive, but there are places where it is necessary.
>It is not clear if doing the scaling buys any advantage on 64 bit platforms,
>so for them a full divide is done.
>
>---
> include/asm-arm/div64.h | 2 ++
> include/asm-generic/div64.h | 8 ++++++++
> include/asm-m68k/div64.h | 2 ++
> include/asm-mips/div64.h | 8 ++++++++
> include/asm-um/div64.h | 1 +
> include/asm-xtensa/div64.h | 1 +
> lib/div64.c | 22 ++++++++++++++++++++++
> net/ipv4/tcp_cubic.c | 22 ----------------------
> net/netfilter/xt_connbytes.c | 16 ----------------
> 9 files changed, 44 insertions(+), 38 deletions(-)
Actually, there is udivdi3 support in the kernel
./arch/arm26/lib/udivdi3.c
./arch/sh/lib/udivdi3.c
./arch/sparc/lib/udivdi3.S
should not this be consolidated too?
Jan
--
ft: http://freshmeat.net/p/chaostables/
On Mon, 26 Feb 2007 21:09:26 +0100 (MET)
Jan Engelhardt <[email protected]> wrote:
>
> On Feb 23 2007 17:05, Stephen Hemminger wrote:
> >
> >Since there already two users of full 64 bit division in the kernel,
> >and other places maybe hiding out as well. Add a full 64/64 bit divide.
> >
> >Yes this expensive, but there are places where it is necessary.
> >It is not clear if doing the scaling buys any advantage on 64 bit platforms,
> >so for them a full divide is done.
> >
> >---
> > include/asm-arm/div64.h | 2 ++
> > include/asm-generic/div64.h | 8 ++++++++
> > include/asm-m68k/div64.h | 2 ++
> > include/asm-mips/div64.h | 8 ++++++++
> > include/asm-um/div64.h | 1 +
> > include/asm-xtensa/div64.h | 1 +
> > lib/div64.c | 22 ++++++++++++++++++++++
> > net/ipv4/tcp_cubic.c | 22 ----------------------
> > net/netfilter/xt_connbytes.c | 16 ----------------
> > 9 files changed, 44 insertions(+), 38 deletions(-)
>
> Actually, there is udivdi3 support in the kernel
>
> ./arch/arm26/lib/udivdi3.c
> ./arch/sh/lib/udivdi3.c
> ./arch/sparc/lib/udivdi3.S
>
> should not this be consolidated too?
Hmm. Those are the GCC internal versions, that are picked up but
doing divide in place. Do we want to allow general 64 bit in kernel to
be easily used? It could cause sloppy slow code, but it would look
cleaner.
--
Stephen Hemminger <[email protected]>
Here is another way to handle the 64 bit divide case.
It allows full 64 bit divide by adding the support routine
GCC needs.
---
arch/alpha/Kconfig | 4 ++++
arch/arm/Kconfig | 4 ++++
arch/arm26/Kconfig | 4 ++++
arch/avr32/Kconfig | 4 ++++
arch/cris/Kconfig | 4 ++++
arch/frv/Kconfig | 4 ++++
arch/h8300/Kconfig | 4 ++++
arch/i386/Kconfig | 4 ++++
arch/m32r/Kconfig | 4 ++++
arch/m68k/Kconfig | 4 ++++
arch/m68knommu/Kconfig | 4 ++++
arch/mips/Kconfig | 4 ++++
arch/parisc/Kconfig | 4 ++++
arch/powerpc/Kconfig | 4 ++++
arch/ppc/Kconfig | 4 ++++
arch/s390/Kconfig | 4 ++++
arch/sh64/Kconfig | 4 ++++
arch/v850/Kconfig | 3 +++
arch/xtensa/Kconfig | 4 ++++
lib/Makefile | 1 +
lib/udivdi3.c | 37 +++++++++++++++++++++++++++++++++++++
net/ipv4/tcp_cubic.c | 26 ++------------------------
net/netfilter/xt_connbytes.c | 19 +------------------
23 files changed, 116 insertions(+), 42 deletions(-)
--- pktgen.orig/net/ipv4/tcp_cubic.c 2007-02-26 13:40:08.000000000 -0800
+++ pktgen/net/ipv4/tcp_cubic.c 2007-02-26 14:30:00.000000000 -0800
@@ -51,7 +51,6 @@
module_param(tcp_friendliness, int, 0644);
MODULE_PARM_DESC(tcp_friendliness, "turn on/off tcp friendliness");
-#include <asm/div64.h>
/* BIC TCP Parameters */
struct bictcp {
@@ -93,27 +92,6 @@
tcp_sk(sk)->snd_ssthresh = initial_ssthresh;
}
-/* 64bit divisor, dividend and result. dynamic precision */
-static inline u_int64_t div64_64(u_int64_t dividend, u_int64_t divisor)
-{
- u_int32_t d = divisor;
-
- if (divisor > 0xffffffffULL) {
- unsigned int shift = fls(divisor >> 32);
-
- d = divisor >> shift;
- dividend >>= shift;
- }
-
- /* avoid 64 bit division if possible */
- if (dividend >> 32)
- do_div(dividend, d);
- else
- dividend = (uint32_t) dividend / d;
-
- return dividend;
-}
-
/*
* calculate the cubic root of x using Newton-Raphson
*/
@@ -134,7 +112,7 @@
*/
do {
x1 = x;
- x = (2 * x + (uint32_t) div64_64(a, x*x)) / 3;
+ x = (2 * x + (u32) (a / x*x)) / 3;
} while (abs(x1 - x) > 1);
return x;
--- pktgen.orig/net/netfilter/xt_connbytes.c 2007-02-26 13:40:08.000000000 -0800
+++ pktgen/net/netfilter/xt_connbytes.c 2007-02-26 14:29:13.000000000 -0800
@@ -16,7 +16,6 @@
#include <linux/netfilter/x_tables.h>
#include <linux/netfilter/xt_connbytes.h>
-#include <asm/div64.h>
#include <asm/bitops.h>
MODULE_LICENSE("GPL");
@@ -24,22 +23,6 @@
MODULE_DESCRIPTION("iptables match for matching number of pkts/bytes per connection");
MODULE_ALIAS("ipt_connbytes");
-/* 64bit divisor, dividend and result. dynamic precision */
-static u_int64_t div64_64(u_int64_t dividend, u_int64_t divisor)
-{
- u_int32_t d = divisor;
-
- if (divisor > 0xffffffffULL) {
- unsigned int shift = fls(divisor >> 32);
-
- d = divisor >> shift;
- dividend >>= shift;
- }
-
- do_div(dividend, d);
- return dividend;
-}
-
static int
match(const struct sk_buff *skb,
const struct net_device *in,
@@ -106,7 +89,7 @@
break;
}
if (pkts != 0)
- what = div64_64(bytes, pkts);
+ what = bytes / pkts;
break;
}
--- pktgen.orig/lib/Makefile 2007-02-26 13:40:08.000000000 -0800
+++ pktgen/lib/Makefile 2007-02-26 14:17:31.000000000 -0800
@@ -28,6 +28,7 @@
lib-$(CONFIG_SEMAPHORE_SLEEPERS) += semaphore-sleepers.o
lib-$(CONFIG_GENERIC_FIND_NEXT_BIT) += find_next_bit.o
obj-$(CONFIG_GENERIC_HWEIGHT) += hweight.o
+obj-$(CONFIG_GENERIC_UDIVDI3) += udivdi3.o
obj-$(CONFIG_LOCK_KERNEL) += kernel_lock.o
obj-$(CONFIG_PLIST) += plist.o
obj-$(CONFIG_DEBUG_PREEMPT) += smp_processor_id.o
--- pktgen.orig/arch/alpha/Kconfig 2007-02-26 13:51:29.000000000 -0800
+++ pktgen/arch/alpha/Kconfig 2007-02-26 13:54:35.000000000 -0800
@@ -33,6 +33,10 @@
bool
default n
+config GENERIC_UDIVDI3
+ bool
+ default y
+
config GENERIC_FIND_NEXT_BIT
bool
default y
--- pktgen.orig/arch/arm/Kconfig 2007-02-26 13:51:29.000000000 -0800
+++ pktgen/arch/arm/Kconfig 2007-02-26 13:54:57.000000000 -0800
@@ -90,6 +90,10 @@
bool
default n
+config GENERIC_UDIVDI3
+ bool
+ default y
+
config GENERIC_HWEIGHT
bool
default y
--- pktgen.orig/arch/arm26/Kconfig 2007-02-26 13:48:46.000000000 -0800
+++ pktgen/arch/arm26/Kconfig 2007-02-26 13:55:24.000000000 -0800
@@ -49,6 +49,10 @@
bool
default n
+config GENERIC_UDIVDI3
+ bool
+ default y
+
config GENERIC_HWEIGHT
bool
default y
--- pktgen.orig/arch/avr32/Kconfig 2007-02-26 13:51:29.000000000 -0800
+++ pktgen/arch/avr32/Kconfig 2007-02-26 13:55:39.000000000 -0800
@@ -53,6 +53,10 @@
bool
default n
+config GENERIC_UDIVDI3
+ bool
+ default y
+
config GENERIC_BUST_SPINLOCK
bool
--- pktgen.orig/arch/cris/Kconfig 2007-02-26 13:51:29.000000000 -0800
+++ pktgen/arch/cris/Kconfig 2007-02-26 13:55:53.000000000 -0800
@@ -28,6 +28,10 @@
bool
default n
+config GENERIC_UDIVDI3
+ bool
+ default y
+
config GENERIC_FIND_NEXT_BIT
bool
default y
--- pktgen.orig/arch/frv/Kconfig 2007-02-26 13:51:29.000000000 -0800
+++ pktgen/arch/frv/Kconfig 2007-02-26 13:56:09.000000000 -0800
@@ -53,6 +53,10 @@
bool
default y
+config GENERIC_UDIVDI3
+ bool
+ default y
+
mainmenu "Fujitsu FR-V Kernel Configuration"
source "init/Kconfig"
--- pktgen.orig/arch/h8300/Kconfig 2007-02-26 13:51:29.000000000 -0800
+++ pktgen/arch/h8300/Kconfig 2007-02-26 13:56:20.000000000 -0800
@@ -41,6 +41,10 @@
bool
default n
+config GENERIC_UDIVDI3
+ bool
+ default y
+
config GENERIC_FIND_NEXT_BIT
bool
default y
--- pktgen.orig/arch/i386/Kconfig 2007-02-26 14:01:59.000000000 -0800
+++ pktgen/arch/i386/Kconfig 2007-02-26 14:02:28.000000000 -0800
@@ -75,6 +75,10 @@
bool
default y
+config GENERIC_UDIVDI3
+ bool
+ default y
+
config ARCH_MAY_HAVE_PC_FDC
bool
default y
--- pktgen.orig/arch/m32r/Kconfig 2007-02-26 13:51:29.000000000 -0800
+++ pktgen/arch/m32r/Kconfig 2007-02-26 13:56:43.000000000 -0800
@@ -229,6 +229,10 @@
bool
default n
+config GENERIC_UDIVDI3
+ bool
+ default y
+
config GENERIC_FIND_NEXT_BIT
bool
default y
--- pktgen.orig/arch/m68k/Kconfig 2007-02-26 13:51:29.000000000 -0800
+++ pktgen/arch/m68k/Kconfig 2007-02-26 13:56:56.000000000 -0800
@@ -25,6 +25,10 @@
bool
default n
+config GENERIC_UDIVDI3
+ bool
+ default y
+
config GENERIC_HWEIGHT
bool
default y
--- pktgen.orig/arch/m68knommu/Kconfig 2007-02-26 13:51:29.000000000 -0800
+++ pktgen/arch/m68knommu/Kconfig 2007-02-26 13:57:05.000000000 -0800
@@ -37,6 +37,10 @@
bool
default n
+config GENERIC_UDIVDI3
+ bool
+ default y
+
config GENERIC_FIND_NEXT_BIT
bool
default y
--- pktgen.orig/arch/mips/Kconfig 2007-02-26 13:51:29.000000000 -0800
+++ pktgen/arch/mips/Kconfig 2007-02-26 13:57:13.000000000 -0800
@@ -843,6 +843,10 @@
bool
default n
+config GENERIC_UDIVDI3
+ bool
+ default y
+
config GENERIC_FIND_NEXT_BIT
bool
default y
--- pktgen.orig/arch/parisc/Kconfig 2007-02-26 13:51:29.000000000 -0800
+++ pktgen/arch/parisc/Kconfig 2007-02-26 13:57:21.000000000 -0800
@@ -33,6 +33,10 @@
bool
default n
+config GENERIC_UDIVDI3
+ bool
+ default y
+
config GENERIC_FIND_NEXT_BIT
bool
default y
--- pktgen.orig/arch/powerpc/Kconfig 2007-02-26 13:51:29.000000000 -0800
+++ pktgen/arch/powerpc/Kconfig 2007-02-26 13:57:31.000000000 -0800
@@ -49,6 +49,10 @@
bool
default y if 64BIT
+config GENERIC_UDIVDI3
+ bool
+ default y
+
config GENERIC_HWEIGHT
bool
default y
--- pktgen.orig/arch/ppc/Kconfig 2007-02-26 13:51:29.000000000 -0800
+++ pktgen/arch/ppc/Kconfig 2007-02-26 13:57:44.000000000 -0800
@@ -27,6 +27,10 @@
bool
default n
+config GENERIC_UDIVDI3
+ bool
+ default y
+
config GENERIC_HWEIGHT
bool
default y
--- pktgen.orig/arch/s390/Kconfig 2007-02-26 13:51:29.000000000 -0800
+++ pktgen/arch/s390/Kconfig 2007-02-26 13:57:53.000000000 -0800
@@ -34,6 +34,10 @@
bool
default n
+config GENERIC_UDIVDI3
+ bool
+ default y
+
config GENERIC_HWEIGHT
bool
default y
--- pktgen.orig/arch/sh64/Kconfig 2007-02-26 13:51:29.000000000 -0800
+++ pktgen/arch/sh64/Kconfig 2007-02-26 14:00:32.000000000 -0800
@@ -21,6 +21,10 @@
bool
default y
+config GENERIC_UDIVDI3
+ bool
+ default y
+
config GENERIC_FIND_NEXT_BIT
bool
default y
--- pktgen.orig/arch/v850/Kconfig 2007-02-26 13:51:29.000000000 -0800
+++ pktgen/arch/v850/Kconfig 2007-02-26 13:59:29.000000000 -0800
@@ -19,6 +19,9 @@
config RWSEM_XCHGADD_ALGORITHM
bool
default n
+config GENERIC_UDIVDI3
+ bool
+ default y
config GENERIC_FIND_NEXT_BIT
bool
default y
--- pktgen.orig/arch/xtensa/Kconfig 2007-02-26 13:51:29.000000000 -0800
+++ pktgen/arch/xtensa/Kconfig 2007-02-26 13:59:45.000000000 -0800
@@ -26,6 +26,10 @@
bool
default y
+config GENERIC_UDIVDI3
+ bool
+ default y
+
config GENERIC_FIND_NEXT_BIT
bool
default y
--- /dev/null 1970-01-01 00:00:00.000000000 +0000
+++ pktgen/lib/udivdi3.c 2007-02-26 14:14:13.000000000 -0800
@@ -0,0 +1,37 @@
+/*
+ * Generic C version of full 64 bit by 64 bit division
+ * Extracted from version used by netfilter connection tracking
+ *
+ * This program is free software; you can redistribute it and/or
+ * modify it under the terms of the GNU General Public License
+ * version 2 as published by the Free Software Foundation.
+ *
+ * Code generated for this function might be very inefficient
+ * for some CPUs, can be overridden by linking arch-specific
+ * assembly versions such as arch/sparc/lib/udivdi.S
+ */
+#include <linux/types.h>
+#include <linux/module.h>
+#include <asm/div64.h>
+
+uint64_t __udivdi3(uint64_t dividend, uint64_t divisor)
+{
+ uint32_t d = divisor;
+
+ /* Scale divisor to 32 bits */
+ if (divisor > 0xffffffffULL) {
+ unsigned int shift = fls(divisor >> 32);
+
+ d = divisor >> shift;
+ dividend >>= shift;
+ }
+
+ /* avoid 64 bit division if possible */
+ if (dividend >> 32)
+ do_div(dividend, d);
+ else
+ dividend = (uint32_t) dividend / d;
+
+ return dividend;
+}
+EXPORT_SYMBOL(__udivdi3);
On Feb 26 2007 13:28, Stephen Hemminger wrote:
>>
>> ./arch/arm26/lib/udivdi3.c
>> ./arch/sh/lib/udivdi3.c
>> ./arch/sparc/lib/udivdi3.S
>>
>> should not this be consolidated too?
>
>Hmm. Those are the GCC internal versions, that are picked up but
>doing divide in place. Do we want to allow general 64 bit in kernel to
>be easily used? It could cause sloppy slow code, but it would look
>cleaner.
Then our reviewers should catch it, and if not, the janitors will
(/me winks at R.P.J.Day and trivial@).
>@@ -134,7 +112,7 @@
> */
> do {
> x1 = x;
>- x = (2 * x + (uint32_t) div64_64(a, x*x)) / 3;
>+ x = (2 * x + (u32) (a / x*x)) / 3;
Eye see a bug.
Previously there was div64_64(a, x*x) which is equivalent to
(a)/(x*x), or just: a/(x^2). But now you do a/x*x, which is
equivalent to a*x/x (in the domain of real numbers). Furthermore,
a/x*x is a-(a%x), which does not even remotely match a/(x^2).
Please keep the math intact, thank you ;-)
Jan
--
On Tue, 27 Feb 2007 00:02:50 +0100 (MET)
Jan Engelhardt <[email protected]> wrote:
>
> On Feb 26 2007 13:28, Stephen Hemminger wrote:
> >>
> >> ./arch/arm26/lib/udivdi3.c
> >> ./arch/sh/lib/udivdi3.c
> >> ./arch/sparc/lib/udivdi3.S
> >>
> >> should not this be consolidated too?
> >
> >Hmm. Those are the GCC internal versions, that are picked up but
> >doing divide in place. Do we want to allow general 64 bit in kernel to
> >be easily used? It could cause sloppy slow code, but it would look
> >cleaner.
>
> Then our reviewers should catch it, and if not, the janitors will
> (/me winks at R.P.J.Day and trivial@).
>
> >@@ -134,7 +112,7 @@
> > */
> > do {
> > x1 = x;
> >- x = (2 * x + (uint32_t) div64_64(a, x*x)) / 3;
> >+ x = (2 * x + (u32) (a / x*x)) / 3;
>
> Eye see a bug.
>
> Previously there was div64_64(a, x*x) which is equivalent to
> (a)/(x*x), or just: a/(x^2). But now you do a/x*x, which is
> equivalent to a*x/x (in the domain of real numbers). Furthermore,
> a/x*x is a-(a%x), which does not even remotely match a/(x^2).
>
> Please keep the math intact, thank you ;-)
Been there, done that, don't want to repeat it...
--
Stephen Hemminger <[email protected]>
On Feb 26 2007 15:44, Stephen Hemminger wrote:
>> >- x = (2 * x + (uint32_t) div64_64(a, x*x)) / 3;
>> >+ x = (2 * x + (u32) (a / x*x)) / 3;
>>
>> Previously there was div64_64(a, x*x) which is equivalent to
>> (a)/(x*x), or just: a/(x^2). But now you do a/x*x, which is
>> equivalent to a*x/x (in the domain of real numbers). Furthermore,
>> a/x*x is a-(a%x), which does not even remotely match a/(x^2).
>>
>Been there, done that, don't want to repeat it...
I am sorry I don't quite follow.
Jan
--
On Tue, 27 Feb 2007 01:05:26 +0100 (MET)
Jan Engelhardt <[email protected]> wrote:
>
> On Feb 26 2007 15:44, Stephen Hemminger wrote:
> >> >- x = (2 * x + (uint32_t) div64_64(a, x*x)) / 3;
> >> >+ x = (2 * x + (u32) (a / x*x)) / 3;
> >>
> >> Previously there was div64_64(a, x*x) which is equivalent to
> >> (a)/(x*x), or just: a/(x^2). But now you do a/x*x, which is
> >> equivalent to a*x/x (in the domain of real numbers). Furthermore,
> >> a/x*x is a-(a%x), which does not even remotely match a/(x^2).
> >>
> >Been there, done that, don't want to repeat it...
>
> I am sorry I don't quite follow.
Once before a missed paren's caused a TCP congestion window bug that
took 6 months before it was found...
--
Stephen Hemminger <[email protected]>
On Feb 26 2007 16:07, Stephen Hemminger wrote:
>> On Feb 26 2007 15:44, Stephen Hemminger wrote:
>> >> >- x = (2 * x + (uint32_t) div64_64(a, x*x)) / 3;
>> >> >+ x = (2 * x + (u32) (a / x*x)) / 3;
>> >>
>> >> Previously there was div64_64(a, x*x) which is equivalent to
>> >> (a)/(x*x), or just: a/(x^2). But now you do a/x*x, which is
>> >> equivalent to a*x/x (in the domain of real numbers). Furthermore,
>> >> a/x*x is a-(a%x), which does not even remotely match a/(x^2).
>> >>
>> >Been there, done that, don't want to repeat it...
>>
>> I am sorry I don't quite follow.
>
>Once before a missed paren's caused a TCP congestion window bug that
>took 6 months before it was found...
Hah, just as I expected.
|On Tue, 27 Feb 2007 00:02:50 +0100 (MET), Jan Engelhardt wrote:
|>Then our reviewers should catch it, and if not, the janitors will.
Jan
--
Stephen Hemminger wrote:
>
> Hmm. Those are the GCC internal versions, that are picked up but
> doing divide in place. Do we want to allow general 64 bit in kernel to
> be easily used? It could cause sloppy slow code, but it would look
> cleaner.
>
... and it would handle datatypes which may be architecture-dependent a
lot cleaner.
I thought the motivation for div64() was that a 64:32->32 divide could
be done a lot faster on a number of platforms (including the important
x86) than a generic 64:64->64 divide, but gcc doesn't handle the
devolution automatically -- there is no such libgcc function.
-hpa
> I thought the motivation for div64() was that a 64:32->32 divide could
> be done a lot faster on a number of platforms (including the important
> x86) than a generic 64:64->64 divide, but gcc doesn't handle the
> devolution automatically -- there is no such libgcc function.
That there's no such function in libgcc doesn't mean GCC
cannot handle this; libgcc is a bunch of library functions
that are really needed for generated code (because you
really don't want to expand those functions inline
everywhere) -- you won't find an addsi3 in libgcc either.
There does exist a divmoddisi4, sort of.
It used to be defined in three GCC targets, but commented
out in all three. The NS32k is long gone. For Vax, a
comment says the machine insn for this isn't used because
it is just too slow. And the i386 version is disabled
because it returns the wrong result on overflow (not the
truncated 64-bit result, required by the implicit cast
to 32-bit, but the i386 arch traps to the overflow handler).
The only way to express the semantics you want in (GNU) C
is to use asm() -- and that's exactly what div64() does :-)
Blame it on the C language, but not on GCC. Not this time.
Segher
On 2/26/07, Stephen Hemminger <[email protected]> wrote:
> Here is another way to handle the 64 bit divide case.
> It allows full 64 bit divide by adding the support routine
> GCC needs.
>
<snip>
I know ARM already went through the process of removing __udivdi3 support:
http://www.arm.linux.org.uk/developer/patches/viewpatch.php?id=2723/2
Copying Russell and Nicolas as a heads up.
--
Dan