From: Stephen Hemminger <shemminger@linux-foundation.org>
To: Jan Engelhardt <jengelh@linux01.gwdg.de>
Cc: linux-kernel@vger.kernel.org, netdev@vger.kernel.org
Subject: Re: [RFC] div64_64 support
Date: Mon, 26 Feb 2007 14:31:27 -0800 [thread overview]
Message-ID: <20070226143127.5c74bec9@freekitty> (raw)
In-Reply-To: <Pine.LNX.4.61.0702262108010.23355@yvahk01.tjqt.qr>
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);
next prev parent reply other threads:[~2007-02-26 22:31 UTC|newest]
Thread overview: 62+ messages / expand[flat|nested] mbox.gz Atom feed top
2007-02-24 1:05 [RFC] div64_64 support Stephen Hemminger
2007-02-24 16:19 ` Sami Farin
2007-02-26 19:28 ` Stephen Hemminger
2007-02-26 19:39 ` David Miller
2007-02-26 20:09 ` Jan Engelhardt
2007-02-26 21:28 ` Stephen Hemminger
2007-02-27 1:20 ` H. Peter Anvin
2007-02-27 3:45 ` Segher Boessenkool
2007-02-26 22:31 ` Stephen Hemminger [this message]
2007-02-26 23:02 ` Jan Engelhardt
2007-02-26 23:44 ` Stephen Hemminger
2007-02-27 0:05 ` Jan Engelhardt
2007-02-27 0:07 ` Stephen Hemminger
2007-02-27 0:14 ` Jan Engelhardt
2007-02-27 6:21 ` Dan Williams
2007-03-03 2:31 ` Andi Kleen
2007-03-05 23:57 ` Stephen Hemminger
2007-03-06 0:25 ` David Miller
2007-03-06 13:36 ` Andi Kleen
2007-03-06 14:04 ` [RFC] div64_64 support II Andi Kleen
2007-03-06 17:43 ` Dagfinn Ilmari Mannsåker
2007-03-06 18:25 ` David Miller
2007-03-06 18:48 ` H. Peter Anvin
2007-03-06 13:34 ` [RFC] div64_64 support Andi Kleen
2007-03-06 14:19 ` Eric Dumazet
2007-03-06 14:45 ` Andi Kleen
2007-03-06 15:10 ` Roland Kuhn
2007-03-06 18:29 ` Stephen Hemminger
2007-03-06 19:48 ` Andi Kleen
2007-03-06 20:04 ` Stephen Hemminger
2007-03-06 21:53 ` Sami Farin
2007-03-06 22:24 ` Sami Farin
2007-03-07 0:00 ` Stephen Hemminger
2007-03-07 0:05 ` David Miller
2007-03-07 0:05 ` Sami Farin
2007-03-07 16:11 ` Chuck Ebbert
2007-03-07 18:32 ` Sami Farin
2007-03-08 18:23 ` asm volatile [Was: [RFC] div64_64 support] Sami Farin
2007-03-08 22:01 ` asm volatile David Miller
2007-03-06 21:58 ` [RFC] div64_64 support David Miller
2007-03-06 22:47 ` [PATCH] tcp_cubic: faster cube root Stephen Hemminger
2007-03-06 22:58 ` cube root benchmark code Stephen Hemminger
2007-03-07 6:08 ` Update to " Willy Tarreau
2007-03-08 1:07 ` [PATCH] tcp_cubic: use 32 bit math Stephen Hemminger
2007-03-08 2:55 ` David Miller
2007-03-08 3:10 ` Stephen Hemminger
2007-03-08 3:51 ` David Miller
2007-03-10 11:48 ` Willy Tarreau
2007-03-12 21:11 ` Stephen Hemminger
2007-03-13 20:50 ` Willy Tarreau
2007-03-21 18:54 ` Stephen Hemminger
2007-03-21 19:15 ` Willy Tarreau
2007-03-21 19:58 ` Stephen Hemminger
2007-03-21 20:15 ` [PATCH 1/2] div64_64 optimization Stephen Hemminger
2007-03-21 20:17 ` [PATCH 2/2] tcp: cubic optimization Stephen Hemminger
2007-03-22 19:11 ` David Miller
2007-03-22 19:11 ` [PATCH 1/2] div64_64 optimization David Miller
2007-03-08 4:16 ` [PATCH] tcp_cubic: use 32 bit math Willy Tarreau
2007-03-07 4:20 ` [PATCH] tcp_cubic: faster cube root David Miller
2007-03-07 12:12 ` Andi Kleen
2007-03-07 19:33 ` David Miller
2007-03-06 18:50 ` [RFC] div64_64 support H. Peter Anvin
Reply instructions:
You may reply publicly to this message via plain-text email
using any one of the following methods:
* Save the following mbox file, import it into your mail client,
and reply-to-all from there: mbox
Avoid top-posting and favor interleaved quoting:
https://en.wikipedia.org/wiki/Posting_style#Interleaved_style
* Reply using the --to, --cc, and --in-reply-to
switches of git-send-email(1):
git send-email \
--in-reply-to=20070226143127.5c74bec9@freekitty \
--to=shemminger@linux-foundation.org \
--cc=jengelh@linux01.gwdg.de \
--cc=linux-kernel@vger.kernel.org \
--cc=netdev@vger.kernel.org \
/path/to/YOUR_REPLY
https://kernel.org/pub/software/scm/git/docs/git-send-email.html
* If your mail client supports setting the In-Reply-To header
via mailto: links, try the mailto: link
Be sure your reply has a Subject: header at the top and a blank line
before the message body.
This is an external index of several public inboxes,
see mirroring instructions on how to clone and mirror
all data and code used by this external index.