LKML Archive on lore.kernel.org
help / color / mirror / Atom feed
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 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 \
--subject='Re: [RFC] div64_64 support' \
/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
This is a public inbox, see mirroring instructions
for how to clone and mirror all data and code used for this inbox;
as well as URLs for NNTP newsgroup(s).