[PATCH] Kill div64.h dupes, parenthesize do_div() macro params

[PATCH] Kill div64.h dupes, parenthesize do_div() macro params

[Bernardo Innocenti]

Hello Linus,

sorry for coming up with this patch in a short time frame, but
it needs to be applied in order to fix real do_div() brokenness
on many architectures.

If you'd prefer me to fix just the bugs without moving
stuff around, I'd be glad to provide another patch. I'd push
this one through a mantainer, but this patch really doesn't
belong to any specific architecture or subsystem, so...

---------------------------------------------------------------------

 - move the 64/32bit do_div() macro to a new asm-generic/div64.h
   header;

 - kill multiple copies of the generic version in architecture
   specific subdirs. Most copies were either buggy or subtly
   different from each other;

 - ensure all surviving instances of do_div() have their parameters
   correctly parenthesized to avoid funny results;

Note that the arm26, cris, m68knommu, sh, sparc and v850 architectures
are silently clipping 64bit dividend to 32bit! This patch doesn't try
to fix this because I can't test on all architectures.

Patch submitted by Bernardo Innocenti <bernie@develer.com>

Applies to 2.5.73. Backporting to 2.4.21 is trivial.


FOOT NOTE: what's the point with do_div()? Isn't gcc's long long
arithmetic support good enough on all platforms? If not, why
doesn't that get fixed in libgcc instead of polluting the kernel
with silly (and sometimes bogus) implementations?


 asm-alpha/div64.h     |   15 +--------------
 asm-arm26/div64.h     |   15 +--------------
 asm-cris/div64.h      |   17 +----------------
 asm-generic/div64.h   |   13 +++++++++++++
 asm-h8300/div64.h     |   14 +-------------
 asm-ia64/div64.h      |   21 +--------------------
 asm-m68k/div64.h      |    9 ---------
 asm-m68knommu/div64.h |   14 +-------------
 asm-mips64/div64.h    |   20 +-------------------
 asm-parisc/div64.h    |   36 ++++++++++--------------------------
 asm-ppc64/div64.h     |   19 +------------------
 asm-s390/div64.h      |    8 +-------
 asm-sh/div64.h        |   11 +----------
 asm-sparc/div64.h     |   12 +-----------
 asm-sparc64/div64.h   |   15 +--------------
 asm-v850/div64.h      |   12 +-----------
 asm-x86_64/div64.h    |   15 +--------------
 17 files changed, 37 insertions(+), 229 deletions(-)

diff -Nru linux-2.5.73-uc0/include/asm-generic/div64.h linux-2.5.x/include/asm-generic/div64.h
--- linux-2.5.73-uc0/include/asm-generic/div64.h	1970-01-01 01:00:00.000000000 +0100
+++ linux-2.5.x/include/asm-generic/div64.h	2003-06-26 01:26:49.000000000 +0200
@@ -0,0 +1,13 @@
+#ifndef _ASM_GENERIC_DIV64_H
+#define _ASM_GENERIC_DIV64_H
+
+/* n = n / base; return rem; */
+
+#define do_div(n,base) ({					\
+	int __res;						\
+	__res = ((unsigned long)(n)) % (unsigned)(base);	\
+	(n) = ((unsigned long)(n)) / (unsigned)(base);		\
+	__res;							\
+})
+
+#endif /* _ASM_GENERIC_DIV64_H */
diff -Nru linux-2.5.73-uc0/include/asm-alpha/div64.h linux-2.5.x/include/asm-alpha/div64.h
--- linux-2.5.73-uc0/include/asm-alpha/div64.h	2003-06-22 20:33:15.000000000 +0200
+++ linux-2.5.x/include/asm-alpha/div64.h	2003-06-26 01:21:03.000000000 +0200
@@ -1,14 +1 @@
-#ifndef __ALPHA_DIV64
-#define __ALPHA_DIV64
-
-/*
- * Hey, we're already 64-bit, no
- * need to play games..
- */
-#define do_div(n,base) ({ \
-	int __res; \
-	__res = ((unsigned long) (n)) % (unsigned) (base); \
-	(n) = ((unsigned long) (n)) / (unsigned) (base); \
-	__res; })
-
-#endif
+#include <asm-generic/div64.h>
diff -Nru linux-2.5.73-uc0/include/asm-arm26/div64.h linux-2.5.x/include/asm-arm26/div64.h
--- linux-2.5.73-uc0/include/asm-arm26/div64.h	2003-06-22 20:32:35.000000000 +0200
+++ linux-2.5.x/include/asm-arm26/div64.h	2003-06-26 01:21:39.000000000 +0200
@@ -1,14 +1 @@
-#ifndef __ASM_ARM_DIV64
-#define __ASM_ARM_DIV64
-
-/* We're not 64-bit, but... */
-#define do_div(n,base)						\
-({								\
-	int __res;						\
-	__res = ((unsigned long)n) % (unsigned int)base;	\
-	n = ((unsigned long)n) / (unsigned int)base;		\
-	__res;							\
-})
-
-#endif
-
+#include <asm-generic/div64.h>
diff -Nru linux-2.5.73-uc0/include/asm-cris/div64.h linux-2.5.x/include/asm-cris/div64.h
--- linux-2.5.73-uc0/include/asm-cris/div64.h	2003-06-22 20:32:35.000000000 +0200
+++ linux-2.5.x/include/asm-cris/div64.h	2003-06-26 01:21:49.000000000 +0200
@@ -1,16 +1 @@
-#ifndef __ASM_CRIS_DIV64
-#define __ASM_CRIS_DIV64
-
-/* copy from asm-arm */
-
-/* We're not 64-bit, but... */
-#define do_div(n,base)						\
-({								\
-	int __res;						\
-	__res = ((unsigned long)n) % (unsigned int)base;	\
-	n = ((unsigned long)n) / (unsigned int)base;		\
-	__res;							\
-})
-
-#endif
-
+#include <asm-generic/div64.h>
diff -Nru linux-2.5.73-uc0/include/asm-h8300/div64.h linux-2.5.x/include/asm-h8300/div64.h
--- linux-2.5.73-uc0/include/asm-h8300/div64.h	2003-06-22 20:32:28.000000000 +0200
+++ linux-2.5.x/include/asm-h8300/div64.h	2003-06-26 01:22:10.000000000 +0200
@@ -1,13 +1 @@
-#ifndef H8300_DIV64_H
-#define H8300_DIV64_H
-
-/* n = n / base; return rem; */
-
-#define do_div(n,base) ({					\
-	int __res;						\
-	__res = ((unsigned long) n) % (unsigned) base;		\
-	n = ((unsigned long) n) / (unsigned) base;		\
-	__res;							\
-})
-
-#endif /* _H8300_DIV64_H */
+#include <asm-generic/div64.h>
diff -Nru linux-2.5.73-uc0/include/asm-ia64/div64.h linux-2.5.x/include/asm-ia64/div64.h
--- linux-2.5.73-uc0/include/asm-ia64/div64.h	2003-06-22 20:33:36.000000000 +0200
+++ linux-2.5.x/include/asm-ia64/div64.h	2003-06-26 01:23:05.000000000 +0200
@@ -1,20 +1 @@
-#ifndef _ASM_IA64_DIV64_H
-#define _ASM_IA64_DIV64_H
-
-/*
- * Copyright (C) 1999 Hewlett-Packard Co
- * Copyright (C) 1999 David Mosberger-Tang <davidm@hpl.hp.com>
- *
- * vsprintf uses this to divide a 64-bit integer N by a small integer BASE.
- * This is incredibly hard on IA-64...
- */
-
-#define do_div(n,base)						\
-({								\
-	int _res;						\
-	_res = ((unsigned long) (n)) % (unsigned) (base);	\
-	(n) = ((unsigned long) (n)) / (unsigned) (base);	\
-	_res;							\
-})
-
-#endif /* _ASM_IA64_DIV64_H */
+#include <asm-generic/div64.h>
diff -Nru linux-2.5.73-uc0/include/asm-m68k/div64.h linux-2.5.x/include/asm-m68k/div64.h
--- linux-2.5.73-uc0/include/asm-m68k/div64.h	2003-06-22 20:33:17.000000000 +0200
+++ linux-2.5.x/include/asm-m68k/div64.h	2003-06-26 01:23:35.000000000 +0200
@@ -3,7 +3,6 @@
 
 /* n = n / base; return rem; */
 
-#if 1
 #define do_div(n, base) ({					\
 	union {							\
 		unsigned long n32[2];				\
@@ -23,13 +22,5 @@
 	(n) = __n.n64;						\
 	__rem;							\
 })
-#else
-#define do_div(n,base) ({					\
-	int __res;						\
-	__res = ((unsigned long) n) % (unsigned) base;		\
-	n = ((unsigned long) n) / (unsigned) base;		\
-	__res;							\
-})
-#endif
 
 #endif /* _M68K_DIV64_H */
diff -Nru linux-2.5.73-uc0/include/asm-m68knommu/div64.h linux-2.5.x/include/asm-m68knommu/div64.h
--- linux-2.5.73-uc0/include/asm-m68knommu/div64.h	2003-06-22 20:32:37.000000000 +0200
+++ linux-2.5.x/include/asm-m68knommu/div64.h	2003-06-26 01:23:54.000000000 +0200
@@ -1,13 +1 @@
-#ifndef _M68KNOMMU_DIV64_H
-#define _M68KNOMMU_DIV64_H
-
-/* n = n / base; return rem; */
-
-#define do_div(n,base) ({					\
-	int __res;						\
-	__res = ((unsigned long) n) % (unsigned) base;		\
-	n = ((unsigned long) n) / (unsigned) base;		\
-	__res;							\
-})
-
-#endif /* _M68K_DIV64_H */
+#include <asm-generic/div64.h>
diff -Nru linux-2.5.73-uc0/include/asm-mips64/div64.h linux-2.5.x/include/asm-mips64/div64.h
--- linux-2.5.73-uc0/include/asm-mips64/div64.h	2003-06-22 20:32:45.000000000 +0200
+++ linux-2.5.x/include/asm-mips64/div64.h	2003-06-26 01:24:41.000000000 +0200
@@ -1,19 +1 @@
-/*
- * This file is subject to the terms and conditions of the GNU General Public
- * License.  See the file "COPYING" in the main directory of this archive
- * for more details.
- */
-#ifndef _ASM_DIV64_H
-#define _ASM_DIV64_H
-
-/*
- * Hey, we're already 64-bit, no
- * need to play games..
- */
-#define do_div(n,base) ({ \
-	int __res; \
-	__res = ((unsigned long) n) % (unsigned) base; \
-	n = ((unsigned long) n) / (unsigned) base; \
-	__res; })
-
-#endif /* _ASM_DIV64_H */
+#include <asm-generic/div64.h>
diff -Nru linux-2.5.73-uc0/include/asm-parisc/div64.h linux-2.5.x/include/asm-parisc/div64.h
--- linux-2.5.73-uc0/include/asm-parisc/div64.h	2003-06-22 20:32:55.000000000 +0200
+++ linux-2.5.x/include/asm-parisc/div64.h	2003-06-26 01:25:25.000000000 +0200
@@ -2,23 +2,7 @@
 #define __ASM_PARISC_DIV64
 
 #ifdef __LP64__
-
-/*
- * Copyright (C) 1999 Hewlett-Packard Co
- * Copyright (C) 1999 David Mosberger-Tang <davidm@hpl.hp.com>
- *
- * vsprintf uses this to divide a 64-bit integer N by a small integer BASE.
- * This is incredibly hard on IA-64 and HPPA
- */
-
-#define do_div(n,base)						\
-({								\
-	int _res;						\
-	_res = ((unsigned long) (n)) % (unsigned) (base);	\
-	(n) = ((unsigned long) (n)) / (unsigned) (base);	\
-	_res;							\
-})
-
+#include <asm-generic/div64.h>
 #else
 /*
  * unsigned long long division.  Yuck Yuck!  What is Linux coming to?
@@ -30,21 +14,21 @@
 	__low  = (n) & 0xffffffff;					\
 	__high = (n) >> 32;						\
 	if (__high) {							\
-		__rem   = __high % (unsigned long)base;			\
-		__high  = __high / (unsigned long)base;			\
+		__rem   = __high % (unsigned long)(base);		\
+		__high  = __high / (unsigned long)(base);		\
 		__low2  = __low >> 16;					\
 		__low2 += __rem << 16;					\
-		__rem   = __low2 % (unsigned long)base;			\
-		__low2  = __low2 / (unsigned long)base;			\
+		__rem   = __low2 % (unsigned long)(base);		\
+		__low2  = __low2 / (unsigned long)(base);		\
 		__low   = __low & 0xffff;				\
 		__low  += __rem << 16;					\
-		__rem   = __low  % (unsigned long)base;			\
-		__low   = __low  / (unsigned long)base;			\
-		n = __low  + ((long long)__low2 << 16) +		\
+		__rem   = __low  % (unsigned long)(base);		\
+		__low   = __low  / (unsigned long)(base);		\
+		(n) = __low  + ((long long)__low2 << 16) +		\
 			((long long) __high << 32);			\
 	} else {							\
-		__rem = __low % (unsigned long)base;			\
-		n = (__low / (unsigned long)base);			\
+		__rem = __low % (unsigned long)(base);			\
+		(n) = (__low / (unsigned long)(base));			\
 	}								\
 	__rem;								\
 })
diff -Nru linux-2.5.73-uc0/include/asm-ppc64/div64.h linux-2.5.x/include/asm-ppc64/div64.h
--- linux-2.5.73-uc0/include/asm-ppc64/div64.h	2003-06-22 20:32:28.000000000 +0200
+++ linux-2.5.x/include/asm-ppc64/div64.h	2003-06-26 01:27:20.000000000 +0200
@@ -1,18 +1 @@
-#ifndef __PPC_DIV64
-#define __PPC_DIV64
-
-/* Copyright 2001 PPC64 Team, IBM Corp
- *
- * This program is free software; you can redistribute it and/or
- * modify it under the terms of the GNU General Public License
- * as published by the Free Software Foundation; either version
- * 2 of the License, or (at your option) any later version.
- */
-
-#define do_div(n,base) ({ \
-	int __res; \
-	__res = ((unsigned long) (n)) % (unsigned) (base); \
-	(n) = ((unsigned long) (n)) / (unsigned) (base); \
-	__res; })
-
-#endif
+#include <asm-generic/div64.h>
diff -Nru linux-2.5.73-uc0/include/asm-s390/div64.h linux-2.5.x/include/asm-s390/div64.h
--- linux-2.5.73-uc0/include/asm-s390/div64.h	2003-06-22 20:32:57.000000000 +0200
+++ linux-2.5.x/include/asm-s390/div64.h	2003-06-26 01:27:51.000000000 +0200
@@ -43,13 +43,7 @@
 })
 
 #else /* __s390x__ */
-
-#define do_div(n,base) ({ \
-int __res; \
-__res = ((unsigned long) n) % (unsigned) base; \
-n = ((unsigned long) n) / (unsigned) base; \
-__res; })
-
+#include <asm-generic/div64.h>
 #endif /* __s390x__ */
 
 #endif
diff -Nru linux-2.5.73-uc0/include/asm-sh/div64.h linux-2.5.x/include/asm-sh/div64.h
--- linux-2.5.73-uc0/include/asm-sh/div64.h	2003-06-22 20:32:28.000000000 +0200
+++ linux-2.5.x/include/asm-sh/div64.h	2003-06-26 01:28:08.000000000 +0200
@@ -1,10 +1 @@
-#ifndef __ASM_SH_DIV64
-#define __ASM_SH_DIV64
-
-#define do_div(n,base) ({ \
-int __res; \
-__res = ((unsigned long) n) % (unsigned) base; \
-n = ((unsigned long) n) / (unsigned) base; \
-__res; })
-
-#endif /* __ASM_SH_DIV64 */
+#include <asm-generic/div64.h>
diff -Nru linux-2.5.73-uc0/include/asm-sparc/div64.h linux-2.5.x/include/asm-sparc/div64.h
--- linux-2.5.73-uc0/include/asm-sparc/div64.h	2003-06-22 20:32:58.000000000 +0200
+++ linux-2.5.x/include/asm-sparc/div64.h	2003-06-26 01:28:25.000000000 +0200
@@ -1,11 +1 @@
-#ifndef __SPARC_DIV64
-#define __SPARC_DIV64
-
-/* We're not 64-bit, but... */
-#define do_div(n,base) ({ \
-	int __res; \
-	__res = ((unsigned long) n) % (unsigned) base; \
-	n = ((unsigned long) n) / (unsigned) base; \
-	__res; })
-
-#endif /* __SPARC_DIV64 */
+#include <asm-generic/div64.h>
diff -Nru linux-2.5.73-uc0/include/asm-sparc64/div64.h linux-2.5.x/include/asm-sparc64/div64.h
--- linux-2.5.73-uc0/include/asm-sparc64/div64.h	2003-06-22 20:32:42.000000000 +0200
+++ linux-2.5.x/include/asm-sparc64/div64.h	2003-06-26 01:28:47.000000000 +0200
@@ -1,14 +1 @@
-#ifndef __SPARC64_DIV64
-#define __SPARC64_DIV64
-
-/*
- * Hey, we're already 64-bit, no
- * need to play games..
- */
-#define do_div(n,base) ({ \
-	int __res; \
-	__res = ((unsigned long) n) % (unsigned) base; \
-	n = ((unsigned long) n) / (unsigned) base; \
-	__res; })
-
-#endif /* __SPARC64_DIV64 */
+#include <asm-generic/div64.h>
diff -Nru linux-2.5.73-uc0/include/asm-v850/div64.h linux-2.5.x/include/asm-v850/div64.h
--- linux-2.5.73-uc0/include/asm-v850/div64.h	2003-06-22 20:33:08.000000000 +0200
+++ linux-2.5.x/include/asm-v850/div64.h	2003-06-26 01:29:07.000000000 +0200
@@ -1,11 +1 @@
-#ifndef __V850_DIV64_H__
-#define __V850_DIV64_H__
-
-/* We're not 64-bit, but... */
-#define do_div(n,base) ({ \
-	int __res; \
-	__res = ((unsigned long) n) % (unsigned) base; \
-	n = ((unsigned long) n) / (unsigned) base; \
-	__res; })
-
-#endif /* __V850_DIV64_H__ */
+#include <asm-generic/div64.h>
diff -Nru linux-2.5.73-uc0/include/asm-x86_64/div64.h linux-2.5.x/include/asm-x86_64/div64.h
--- linux-2.5.73-uc0/include/asm-x86_64/div64.h	2003-06-22 20:33:12.000000000 +0200
+++ linux-2.5.x/include/asm-x86_64/div64.h	2003-06-26 01:29:16.000000000 +0200
@@ -1,14 +1 @@
-#ifndef __X86_64_DIV64
-#define __X86_64_DIV64
-
-/*
- * Hey, we're already 64-bit, no
- * need to play games..
- */
-#define do_div(n,base) ({ \
-	int __res; \
-	__res = ((unsigned long) (n)) % (unsigned) (base); \
-	(n) = ((unsigned long) (n)) / (unsigned) (base); \
-	__res; })
-
-#endif
+#include <asm-generic/div64.h>

-- 
  // Bernardo Innocenti - Develer S.r.l., R&D dept.
\X/  http://www.develer.com/

Please don't send Word attachments - http://www.gnu.org/philosophy/no-word-attachments.html

Re: [PATCH] Kill div64.h dupes, parenthesize do_div() macro params

[Bernardo Innocenti]

On Wednesday 02 July 2003 02:36, Andrew Morton wrote:

 > > sorry for coming up with this patch in a short time frame, but
 > > it needs to be applied in order to fix real do_div() brokenness
 > > on many architectures.
 >
 > I included this in 2.5.73-mm2.  It will percolate through after I've
 > eyeballed it more thoroughly and run it past the arch maintainers.

 Thank you very much Andrew! I was already thinking of contacting either
you or davem to pick that one up from me.

 By the way, what do you think about getting rid of the do_div() macro
altogether? I've noticed that gcc 3.3 is quite capable of guessing the
optimal instruction pattern to use even for the generic do_div()
written in C:

    rem = (unsigned long)div % (unsigned)base;
    div = (unsigned long)div / (unsigned)base;

This code makes gcc select the "udivmodsi4" pattern on the m68k
backend, which computes both the quotient and remainder with a
single instruction on some architectures. The compiler is even
smart enough to optimize the case where the remainder isn't used:

  if (find_reg_note (insn, REG_UNUSED, operands[3]))
    return \"divu%.l %2,%0\";
  else
    return \"divul%.l %2,%3:%0\";

So I don't see a performance issue here. There are even places
in the kernel where do_div() is used even when the remainder
isn't used, so it's a potential performance hit (but GCC is
again smart enough to detect that dead code and discards it ;-).

If there are architectures where gcc doesn't implement divisions
correctly, this issue should be solved in gcc, not by adding a
silly macro to the kernel.

-- 
  // Bernardo Innocenti - Develer S.r.l., R&D dept.
\X/  http://www.develer.com/

Please don't send Word attachments - http://www.gnu.org/philosophy/no-word-attachments.html

Re: [PATCH] Kill div64.h dupes, parenthesize do_div() macro params

[Andrew Morton]

Bernardo Innocenti <bernie@develer.com> wrote:
>
>  By the way, what do you think about getting rid of the do_div() macro
>  altogether?

I think we leave it the way it is because 64-bit divides are slow.

It is very easy to go accidentally adding 64-bit divides.  Say, by changing
the disk indexing to use 64-bit sector numbers as we did earlier in 2.5.

By requiring an explicit do_div we are made aware of all those 64-bit
divides and are made to think about them.

Why 64-bit divides in particular were victimised in this manner is a matter
for speculation ;)

Re: [PATCH] Kill div64.h dupes, parenthesize do_div() macro params

[Bernardo Innocenti]

On Wednesday 02 July 2003 04:32, you wrote:

 > >  By the way, what do you think about getting rid of the do_div()
 > > macro altogether?
 >
 > I think we leave it the way it is because 64-bit divides are slow.

 Wait! It's not documented at all that do_div() really does a
64bit/32bit division with 32bit remainder.

  rem = (unsigned long)div % (unsigned)base;
  div = (unsigned long)div / (unsigned)base;

What the generic version really does on 64bit architectures is a
64bit/32bit division, since "long" is usually 64bit.

What's worse, it has different semantics on different architectures:

 alpha     64/32 -> 64q + 32r (generic)
 arm       64/32 -> 64q + 32r (asm function call)
 arm26     32/32 -> 32q + 32r (generic)
 cris      32/32 -> 32q + 32r (generic)
 h8300     32/32 -> 32q + 32r (generic)
 i386      64/32 -> 64q + 32r (inline asm + C for 64bit case)
 ia64      64/32 -> 64q + 32r (generic)
 m68k      64/32 -> 64q + 32r (inline asm + C for 64bit case)
 m68knommu 32/32 -> 32q + 32r (generic)
 mips      64/32 -> 64q + 32r (inline asm)
 mips64    64/32 -> 64q + 32r (generic)
 parisc    64/32 -> 64q + 32r (inline C)
 ppc       64/32 -> 64q + 32r (inline C + call for 64bit case)
 ppc64     64/32 -> 64q + 32r (generic)
 s390      64/32 -> 64q + 32r (generic for s390x, otherwise inline asm)
 sh        32/32 -> 32q + 32r (generic)
 sparc     32/32 -> 32q + 32r (generic)
 sparc64   64/32 -> 64q + 32r (generic)
 um        like host
 v850      32/32 -> 32q + 32r (generic)
 x86_64    64/32 -> 64q + 32r (generic)
 
 This table might be incorrect for some architectures I'm not familiar with.


 > It is very easy to go accidentally adding 64-bit divides.  Say, by
 > changing the disk indexing to use 64-bit sector numbers as we did
 > earlier in 2.5.
 > By requiring an explicit do_div we are made aware of all those 64-bit
 > divides and are made to think about them.

 Nothing in div64.h prevents one from using the normal C syntax for
making divisions between long long numbers.

 Besides, using the macros is much slower on some architectures. gcc cannot
see through blocks of inline asm, therefore it won't be able to do proper
constant propagation and dead code elimination.

 > Why 64-bit divides in particular were victimised in this manner is a
 > matter for speculation ;)

 Let me guess: perhaps older gcc versions (pre 2.95) had some bugs
with long long and somone decided to fix the problem that way ;-)

-- 
  // Bernardo Innocenti - Develer S.r.l., R&D dept.
\X/  http://www.develer.com/

Please don't send Word attachments - http://www.gnu.org/philosophy/no-word-attachments.html

Re: [PATCH] Kill div64.h dupes, parenthesize do_div() macro params

[Peter Chubb]

>>>>> "Bernardo" == Bernardo Innocenti <bernie@develer.com> writes:

Bernardo> On Wednesday 02 July 2003 02:36, Andrew Morton wrote:

Bernardo> If there are architectures where gcc doesn't implement
Bernardo> divisions correctly, this issue should be solved in gcc, not
Bernardo> by adding a silly macro to the kernel.

The issue is that on 32-bit platforms, 64bit divided by 32 bit is
handed off to a subroutine _udivdi3 which isn't linked into the
kernel, and  which in any case does a full 64 bit by 64-bit division
(which is slow).

Using do_div() allows one to generate near-optimal code for a 64by32
bit division/remainder on platforms (e.g., IA32) which have problems,
and generating something sane for other platforms (e.g., IA64).

Platforms that never expect to deal with a 64-bit number just redefine
the macro in terms of long.  Which means that printing out long longs
doesn't work properly on those architectures.


--
Dr Peter Chubb  http://www.gelato.unsw.edu.au  peterc AT gelato.unsw.edu.au
You are lost in a maze of BitKeeper repositories,   all slightly different.

Re: [PATCH] Kill div64.h dupes, parenthesize do_div() macro params

[Bernardo Innocenti]

On Wednesday 02 July 2003 05:36, Peter Chubb wrote:

 > Bernardo> If there are architectures where gcc doesn't implement
 > Bernardo> divisions correctly, this issue should be solved in gcc, not
 > Bernardo> by adding a silly macro to the kernel.
 >
 > The issue is that on 32-bit platforms, 64bit divided by 32 bit is
 > handed off to a subroutine _udivdi3 which isn't linked into the
 > kernel, and  which in any case does a full 64 bit by 64-bit division
 > (which is slow).

 I see. It's ashaming that the gcc people didn't care special casing
the quite common 64/32 case in the x86 machine description or at least
in libgcc.

 > Using do_div() allows one to generate near-optimal code for a 64by32
 > bit division/remainder on platforms (e.g., IA32) which have problems,
 > and generating something sane for other platforms (e.g., IA64).

 I agree. I'd prefer to see it fixed in gcc, but until then...


 > Platforms that never expect to deal with a 64-bit number just redefine
 > the macro in terms of long.  Which means that printing out long longs
 > doesn't work properly on those architectures.

 A function which changes its semantics depending on the platform is
definitely a ugly hack.

 A cleaner way to address this problem would be using platform-specific
typedefs to reduce the size of specific objects to 32bits on smaller systems.


 In mm/vmscan.c:shrink_slab() you'll find this:

       long long delta;

       delta = scanned * shrinker->seeks;
       delta *= (*shrinker->shrinker)(0, gfp_mask);
       do_div(delta, pages + 1);
       shrinker->nr += delta;

 This is _BAD_ because delta will be 128bits on some 64bit systems
and 64bit, but truncated to 32bit in do_div(), on some other systems.

 Using at least uint64_t would solve the first problem, but anyone
looking at this code wouldn't realize the result could get truncated
by some do_div() implementations.

 What can we do about that? This time I don't have a clean solution to
advocate.

-- 
  // Bernardo Innocenti - Develer S.r.l., R&D dept.
\X/  http://www.develer.com/

Please don't send Word attachments - http://www.gnu.org/philosophy/no-word-attachments.html

Re: [PATCH] Kill div64.h dupes, parenthesize do_div() macro params

[Linus Torvalds]

On Wed, 2 Jul 2003, Bernardo Innocenti wrote:
> 
>  By the way, what do you think about getting rid of the do_div() macro
> altogether? I've noticed that gcc 3.3 is quite capable of guessing the
> optimal instruction pattern to use even for the generic do_div()
> written in C:

No thank you. 3.x is still broken enough that I don't want to force people 
to use it.

> This code makes gcc select the "udivmodsi4" pattern on the m68k
> backend

Who cares about m68k? Does it do the right thing on x86? gcc 3.2.2 does
not, it does a "call __udivdi3" + "call __umoddi3", which is a 64/64->64
thing, which is totally inappropriate, and about a million times slower 
than a single "udiv".

gcc is crap when it comes to long long. Always has been.

		Linus

Re: [PATCH] Kill div64.h dupes, parenthesize do_div() macro params

[Linus Torvalds]

On Tue, 1 Jul 2003, Andrew Morton wrote:
> 
> By requiring an explicit do_div we are made aware of all those 64-bit
> divides and are made to think about them.

do_div() is NOT a 64-bit divide.

It's a 64/32->64+32 div/mod operation, which is a totally different thing
than a full 64/64 divide, and is usually much faster to compute on most 
32-bit architectures.

> Why 64-bit divides in particular were victimised in this manner is a matter
> for speculation ;)

Because gcc historically _cannot_ generate an efficient 64/32->64 divide. 
It ends up doing a full 64/64 divide thing.

		Linus

Re: [PATCH] Kill div64.h dupes, parenthesize do_div() macro params

[Linus Torvalds]

On Wed, 2 Jul 2003, Bernardo Innocenti wrote:
>
>  Wait! It's not documented at all that do_div() really does a
> 64bit/32bit division with 32bit remainder.

Oh, it's documented all right. It's even documented by the architectures 
that do it wrong (ie chris/arm26 say "we're not 64-bit but..")

> What's worse, it has different semantics on different archictecures:

only because some architectures on purpose get it wrong, because they 
don't care.

>  i386      64/32 -> 64q + 32r (inline asm + C for 64bit case)

This is the only version that has ever been valid.

It's a 64/32->64+32. No excuses, no nothing. There is no question about 
it.

		Linus

Re: [PATCH] Kill div64.h dupes, parenthesize do_div() macro params

[Andrea Arcangeli]

On Wed, Jul 02, 2003 at 01:36:03PM +1000, Peter Chubb wrote:
> Platforms that never expect to deal with a 64-bit number just redefine
> the macro in terms of long.  Which means that printing out long longs

this doesn't even sounds safe. If it's just for printing not a big deal,
but there may be functional usages where they should not truncate the
high 32bit of the 64bit words.

Bernardo, you should definitely add an #if BITS_PER_LONG == 64 around
your implementation of do_div in asm-generic, just to make an example
sparc is still silenty broken (and that's not an embedded thing).

In the #else path of the generic implementation you can consider adding
another version that casts to (long long), then as worse it will spwan a
link compile time failure. But if it compiles it won't generate runtime
failures. so basically it's up to gcc to do the right thing then.

Andrea

Re: [PATCH] Kill div64.h dupes, parenthesize do_div() macro params

[Bernardo Innocenti]

On Wednesday 02 July 2003 07:57, Andrea Arcangeli wrote:

 > this doesn't even sounds safe. If it's just for printing not a big
 > deal, but there may be functional usages where they should not
 > truncate the high 32bit of the 64bit words.

 I've seen some of them already. Even if none were currently present,
this would easily lead to architecture specific bugs in future kernels.

 > Bernardo, you should definitely add an #if BITS_PER_LONG == 64 around
 > your implementation of do_div in asm-generic, just to make an example
 > sparc is still silenty broken (and that's not an embedded thing).
 > [...]

 How does this new patch look? The 32bit version comes from asm-ppc/div64.h
and seems to work fine on m68knommu too, so I assume it to be at least
correct.

 Ciao!


--- /dev/null	1970-01-01 01:00:00.000000000 +0100
+++ asm-generic/div64.h	2003-07-02 08:23:48.000000000 +0200
@@ -0,0 +1,66 @@
+#ifndef _ASM_GENERIC_DIV64_H
+#define _ASM_GENERIC_DIV64_H
+
+#include <linux/types.h>
+
+/*
+ * do_div() performs a 64bit/32bit unsigned division and modulo.
+ * The 64bit result is stored back in the divisor, the 32bit
+ * remainder is returned.
+ *
+ * A semantically correct implementation would do this:
+ *
+ *	static inline uint32_t do_div(uint64_t &n, uint32_t base)
+ *	{
+ *		uint32_t rem;
+ *		rem = n % base;
+ *		n = n / base;
+ *		return rem;
+ *	}
+ *
+ * We can't rely on GCC's "long long" math since it would turn
+ * everything into a full 64bit division implemented through _udivdi3(),
+ * which is much slower.
+ */
+
+#if BITS_PER_LONG == 64
+
+# define do_div(n,base) ({					\
+	uint32_t __res;						\
+	__res = ((uint64_t)(n)) % (uint32_t)(base);		\
+	(n) = ((uint64_t)(n)) / (uint32_t)(base);		\
+	__res;							\
+ })
+
+#elif BITS_PER_LONG == 32
+
+# define do_div(n,base)	({					\
+								\
+	uint32_t __low, __low2, __high, __rem;			\
+	__low  = (n) & 0xffffffff;				\
+	__high = (n) >> 32;					\
+	if (__high) {						\
+		__rem   = __high % (uint32_t)(base);		\
+		__high  = __high / (uint32_t)(base);		\
+		__low2  = __low >> 16;				\
+		__low2 += __rem << 16;				\
+		__rem   = __low2 % (uint32_t)(base);		\
+		__low2  = __low2 / (uint32_t)(base);		\
+		__low   = __low & 0xffff;			\
+		__low  += __rem << 16;				\
+		__rem   = __low  % (uint32_t)(base);		\
+		__low   = __low  / (uint32_t)(base);		\
+		(n) = __low  + ((uint64_t)__low2 << 16) +	\
+			((uint64_t) __high << 32);		\
+	} else {						\
+		__rem = __low % (uint32_t)(base);		\
+		(n) = (__low / (uint32_t)(base));		\
+	}							\
+	__rem;							\
+ })
+
+#else /* BITS_PER_LONG == ?? */
+# error do_div() does not yet support the C64
+#endif /* BITS_PER_LONG */
+
+#endif /* _ASM_GENERIC_DIV64_H */

-- 
  // Bernardo Innocenti - Develer S.r.l., R&D dept.
\X/  http://www.develer.com/

Please don't send Word attachments - http://www.gnu.org/philosophy/no-word-attachments.html

Re: [PATCH] Kill div64.h dupes, parenthesize do_div() macro params

[Bernardo Innocenti]

On Wednesday 02 July 2003 07:09, Linus Torvalds wrote:

 > > Why 64-bit divides in particular were victimised in this manner is a
 > > matter for speculation ;)
 >
 > Because gcc historically _cannot_ generate an efficient 64/32->64
 > divide. It ends up doing a full 64/64 divide thing.

 You're right here. I've been too quick in putting my faith in gcc ;-)

 Shouldn't we complain to the gcc people? The 64/32 division is a
rather common operation in many applications besides the kernel, so
you'd expect gcc to get it right without polluting every single
project with reimplementations of do_div().

-- 
  // Bernardo Innocenti - Develer S.r.l., R&D dept.
\X/  http://www.develer.com/

Please don't send Word attachments - http://www.gnu.org/philosophy/no-word-attachments.html

Re: [PATCH] Kill div64.h dupes, parenthesize do_div() macro params

[Andrea Arcangeli]

On Wed, Jul 02, 2003 at 08:52:17AM +0200, Bernardo Innocenti wrote:
> + *	static inline uint32_t do_div(uint64_t &n, uint32_t base)

c++ ;)

> +# error do_div() does not yet support the C64

;)

this new version looks good to me since it will fix bugs and it's not
only a cleanup avoiding code duplication. thanks.

ciao

Andrea

Re: [PATCH] Kill div64.h dupes, parenthesize do_div() macro params

[Bernardo Innocenti]

On Wednesday 02 July 2003 09:19, you wrote:
 > On Wed, Jul 02, 2003 at 08:52:17AM +0200, Bernardo Innocenti wrote:
 > > + *	static inline uint32_t do_div(uint64_t &n, uint32_t base)
 >
 > c++ ;)

 Oops! Shall I send a new patch? ;-)

 > > +# error do_div() does not yet support the C64
 >
 > ;)
 >
 > this new version looks good to me since it will fix bugs and it's not
 > only a cleanup avoiding code duplication. thanks.

 The previous patch was not just a cleanup: it actually added parenthes
that were missing around parameters in many do_div() variants. Guess
what happened when shrink_slab() did this (pages = 0):

   do_div(delta, pages + 1); /* Ouch! */

-- 
  // Bernardo Innocenti - Develer S.r.l., R&D dept.
\X/  http://www.develer.com/

Please don't send Word attachments - http://www.gnu.org/philosophy/no-word-attachments.html

Re: [PATCH] Kill div64.h dupes, parenthesize do_div() macro params

[Russell King]

On Wed, Jul 02, 2003 at 05:15:17AM +0200, Bernardo Innocenti wrote:
> What's worse, it has different semantics on different architectures:

Any arch which does 32/32 -> 32q + 32r will break in the new time code;
it certainly did for ARM.  do_div must now be a 64/32 -> 64q + 32r
implementation.

>  arm       64/32 -> 64q + 32r (asm function call)
>  arm26     32/32 -> 32q + 32r (generic)

arm26 needs fixing in the same way arm recently was.

-- 
Russell King (rmk@arm.linux.org.uk)                The developer of ARM Linux
             http://www.arm.linux.org.uk/personal/aboutme.html

Re: [PATCH] Kill div64.h dupes, parenthesize do_div() macro params

[Matti Aarnio]

On Wed, Jul 02, 2003 at 09:02:05AM +0200, Bernardo Innocenti wrote:
> On Wednesday 02 July 2003 07:09, Linus Torvalds wrote:
>  > > Why 64-bit divides in particular were victimised in this manner is a
>  > > matter for speculation ;)
>  >
>  > Because gcc historically _cannot_ generate an efficient 64/32->64
>  > divide. It ends up doing a full 64/64 divide thing.
> 
>  You're right here. I've been too quick in putting my faith in gcc ;-)
> 
>  Shouldn't we complain to the gcc people? The 64/32 division is a
> rather common operation in many applications besides the kernel, so
> you'd expect gcc to get it right without polluting every single
> project with reimplementations of do_div().

The thinking behind there has been:
 a) arbitrary 64/32 division is _rare_, and shall be used only
    in places that are non-critical to system speed
 b) all places in filesystems, etc. should handle things by
    doing these things with  >>  operators, which of course,
    requires divisor to be power of two, and given as log2()
    of the divisor.
 c) to see usage of sub-optimal speed things, linkage against
    libgcc is expressly forbidden in kernel.

Thus when you see that  _divxyz3()  can not be linked in, the
bug is in its _need_, and thus the code, not in lack of library
to supply it!   The  do_div64()  is there to supply those non-
speed-critical rare uses.

At some platforms there is no way around this rule, but Linux's
primary platform is i386, and there those enforcements are shown.

To an extent, for example  Alpha  platform got several libgcc
functions copied in its arch library, to solve some unavoidable
builtin function needs, while still not blindly linking with
libgcc.

> -- 
>   // Bernardo Innocenti - Develer S.r.l., R&D dept.
> \X/  http://www.develer.com/

/Matti Aarnio

Re: [PATCH] Kill div64.h dupes, parenthesize do_div() macro params

[Russell King]

On Wed, Jul 02, 2003 at 07:57:59AM +0200, Andrea Arcangeli wrote:
> this doesn't even sounds safe. If it's just for printing not a big deal,

It used to be only used in vsprintf.  However, now it features in the
kernels time code, and that rather screws things up if its implemented
as a 32 by 32 operation.

Therefore, if architectures want a stable time subsystem, all
architectures must provide a do_div() which is a 64 by 32 operation.

-- 
Russell King (rmk@arm.linux.org.uk)                The developer of ARM Linux
             http://www.arm.linux.org.uk/personal/aboutme.html

Re: [PATCH] Kill div64.h dupes, parenthesize do_div() macro params

[Ian Molton]

On Wed, 2 Jul 2003 08:53:02 +0100
Russell King <rmk@arm.linux.org.uk> wrote:

> On Wed, Jul 02, 2003 at 05:15:17AM +0200, Bernardo Innocenti wrote:
> > What's worse, it has different semantics on different architectures:
> 
> Any arch which does 32/32 -> 32q + 32r will break in the new time
> code; it certainly did for ARM.  do_div must now be a 64/32 -> 64q +
> 32r implementation.
> 
> >  arm       64/32 -> 64q + 32r (asm function call)
> >  arm26     32/32 -> 32q + 32r (generic)
> 
> arm26 needs fixing in the same way arm recently was.

Thanks for the heads-up. Im not familiar with the time stuff yet, could
someone send me the full text of the partially snipped post above so I
have some background?


-- 
Spyros lair: http://www.mnementh.co.uk/   ||||   Maintainer: arm26 linux

Do not meddle in the affairs of Dragons, for you are tasty and good with
ketchup.

Re: [PATCH] Kill div64.h dupes, parenthesize do_div() macro params

[Andrea Arcangeli]

On Wed, Jul 02, 2003 at 09:28:38AM +0200, Bernardo Innocenti wrote:
> On Wednesday 02 July 2003 09:19, you wrote:
>  > On Wed, Jul 02, 2003 at 08:52:17AM +0200, Bernardo Innocenti wrote:
>  > > + *	static inline uint32_t do_div(uint64_t &n, uint32_t base)
>  >
>  > c++ ;)
> 
>  Oops! Shall I send a new patch? ;-)

I guess no ;).

> 
>  > > +# error do_div() does not yet support the C64
>  >
>  > ;)
>  >
>  > this new version looks good to me since it will fix bugs and it's not
>  > only a cleanup avoiding code duplication. thanks.
> 
>  The previous patch was not just a cleanup: it actually added parenthes
> that were missing around parameters in many do_div() variants. Guess
> what happened when shrink_slab() did this (pages = 0):
> 
>    do_div(delta, pages + 1); /* Ouch! */

I see.

Andrea

Re: [PATCH] Kill div64.h dupes, parenthesize do_div() macro params

[Geert Uytterhoeven]

On Tue, 1 Jul 2003, Linus Torvalds wrote:
> On Wed, 2 Jul 2003, Bernardo Innocenti wrote:
> > This code makes gcc select the "udivmodsi4" pattern on the m68k
> > backend
> 
> Who cares about m68k? Does it do the right thing on x86? gcc 3.2.2 does

Just for the record, I do ;-)

Gr{oetje,eeting}s,

						Geert

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

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

Re: [PATCH] Kill div64.h dupes, parenthesize do_div() macro params

[Linus Torvalds]

On Wed, 2 Jul 2003, Bernardo Innocenti wrote:
> +#elif BITS_PER_LONG == 32
> +
> +# define do_div(n,base)	({					\
> +								\
> +	uint32_t __low, __low2, __high, __rem;			\
> +	__low  = (n) & 0xffffffff;				\
> +	__high = (n) >> 32;					\
> +	if (__high) {						\
> +		__rem   = __high % (uint32_t)(base);		\
> +		__high  = __high / (uint32_t)(base);		\
> +		__low2  = __low >> 16;				\
> +		__low2 += __rem << 16;				\
> +		__rem   = __low2 % (uint32_t)(base);		\
> +		__low2  = __low2 / (uint32_t)(base);		\
> +		__low   = __low & 0xffff;			\
> +		__low  += __rem << 16;				\
> +		__rem   = __low  % (uint32_t)(base);		\
> +		__low   = __low  / (uint32_t)(base);		\
> +		(n) = __low  + ((uint64_t)__low2 << 16) +	\
> +			((uint64_t) __high << 32);		\
> +	} else {						\
> +		__rem = __low % (uint32_t)(base);		\
> +		(n) = (__low / (uint32_t)(base));		\
> +	}							\
> +	__rem;							\
> + })

Don't do this as a in-line thing. Do it as an out-of-line function, 
something like

	#define do_div64(n,base) ({			\
		u32 __rem;				\
		n = lib_do_div64(n, base, &__rem);	\
		__rem; })

instead. Add the out-of-line thing to lib/lib.a or something.

		Linus

[PATCH] Fix do_div() for all architectures

[Bernardo Innocenti]

On Wednesday 02 July 2003 18:16, Linus Torvalds wrote:

 > Don't do this as a in-line thing. Do it as an out-of-line function,
 > something like
 >
 > 	#define do_div64(n,base) ({			\
 > 		u32 __rem;				\
 > 		n = lib_do_div64(n, base, &__rem);	\
 > 		__rem; })
 >
 > instead. Add the out-of-line thing to lib/lib.a or something.

Good point, however I feel the fast path for n <= 32bit
should still be left inline for best performance.

Full patch against 2.5.74 follows. I will provide a 2.4
backport after it has received some testing in 2.5.

I've used C99 types instead of Linux specific types because
I somewhat prefer them. Is using C99 types in the kernel ok?

Both ppc and sh were already providing an assembly
optimized __div64_32(). I called my function the same, so
it will automatically override mine in lib.a.

I've only tested extensively on m68knommu (uClinux) and made
sure generated code is reasonably short. Should be ok also on
parisc, since it's the same algorithm they were using before.

  // Bernardo Innocenti - Develer S.r.l., R&D dept.
\X/  http://www.develer.com/

-----------------------------------------------------------------

 - add generic C implementations of the do_div() for 32bit and 64bit
   archs in asm-generic/div64.h;

 - add generic library support function __div64_32() to handle the
   full 64/32 case on 32bit archs;

 - kill multiple copies of generic do_div() in architecture
   specific subdirs. Most copies were either buggy or not doing
   what they were supposed to do;

 - ensure all surviving instances of do_div() have their parameters
   correctly parenthesized to avoid funny side-effects;

 include/asm-alpha/div64.h     |   15 -----------
 include/asm-arm26/div64.h     |   15 -----------
 include/asm-cris/div64.h      |   17 ------------
 include/asm-generic/div64.h   |   53 ++++++++++++++++++++++++++++++++++++++++
 include/asm-h8300/div64.h     |   14 ----------
 include/asm-ia64/div64.h      |   21 ----------------
 include/asm-m68k/div64.h      |    9 ------
 include/asm-m68knommu/div64.h |   14 ----------
 include/asm-mips64/div64.h    |   19 --------------
 include/asm-parisc/div64.h    |   55 ------------------------------------------
 include/asm-ppc/div64.h       |   24 ------------------
 include/asm-ppc64/div64.h     |   19 --------------
 include/asm-s390/div64.h      |    8 ------
 include/asm-sh/div64.h        |   21 ----------------
 include/asm-sparc/div64.h     |   12 ---------
 include/asm-sparc64/div64.h   |   15 -----------
 include/asm-v850/div64.h      |   12 ---------
 include/asm-x86_64/div64.h    |   15 -----------
 lib/Makefile                  |    2 -
 lib/div64.c                   |   45 ++++++++++++++++++++++++++++++++++
 20 files changed, 115 insertions(+), 290 deletions(-)

diff -Nru linux-2.5.74-uc0/include/asm-alpha/div64.h linux-2.5.74-uc0-develer/include/asm-alpha/div64.h
--- linux-2.5.74-uc0/include/asm-alpha/div64.h	2003-07-02 22:54:43.000000000 +0200
+++ linux-2.5.74-uc0-develer/include/asm-alpha/div64.h	2003-07-03 09:37:22.000000000 +0200
@@ -1,14 +1 @@
-#ifndef __ALPHA_DIV64
-#define __ALPHA_DIV64
-
-/*
- * Hey, we're already 64-bit, no
- * need to play games..
- */
-#define do_div(n,base) ({ \
-	int __res; \
-	__res = ((unsigned long) (n)) % (unsigned) (base); \
-	(n) = ((unsigned long) (n)) / (unsigned) (base); \
-	__res; })
-
-#endif
+#include <asm-generic/div64.h>
diff -Nru linux-2.5.74-uc0/include/asm-arm26/div64.h linux-2.5.74-uc0-develer/include/asm-arm26/div64.h
--- linux-2.5.74-uc0/include/asm-arm26/div64.h	2003-07-02 22:42:11.000000000 +0200
+++ linux-2.5.74-uc0-develer/include/asm-arm26/div64.h	2003-07-03 09:37:22.000000000 +0200
@@ -1,14 +1 @@
-#ifndef __ASM_ARM_DIV64
-#define __ASM_ARM_DIV64
-
-/* We're not 64-bit, but... */
-#define do_div(n,base)						\
-({								\
-	int __res;						\
-	__res = ((unsigned long)n) % (unsigned int)base;	\
-	n = ((unsigned long)n) / (unsigned int)base;		\
-	__res;							\
-})
-
-#endif
-
+#include <asm-generic/div64.h>
diff -Nru linux-2.5.74-uc0/include/asm-cris/div64.h linux-2.5.74-uc0-develer/include/asm-cris/div64.h
--- linux-2.5.74-uc0/include/asm-cris/div64.h	2003-07-02 22:42:06.000000000 +0200
+++ linux-2.5.74-uc0-develer/include/asm-cris/div64.h	2003-07-03 09:37:22.000000000 +0200
@@ -1,16 +1 @@
-#ifndef __ASM_CRIS_DIV64
-#define __ASM_CRIS_DIV64
-
-/* copy from asm-arm */
-
-/* We're not 64-bit, but... */
-#define do_div(n,base)						\
-({								\
-	int __res;						\
-	__res = ((unsigned long)n) % (unsigned int)base;	\
-	n = ((unsigned long)n) / (unsigned int)base;		\
-	__res;							\
-})
-
-#endif
-
+#include <asm-generic/div64.h>
diff -Nru linux-2.5.74-uc0/include/asm-generic/div64.h linux-2.5.74-uc0-develer/include/asm-generic/div64.h
--- linux-2.5.74-uc0/include/asm-generic/div64.h	1970-01-01 01:00:00.000000000 +0100
+++ linux-2.5.74-uc0-develer/include/asm-generic/div64.h	2003-07-03 09:55:04.000000000 +0200
@@ -0,0 +1,53 @@
+#ifndef _ASM_GENERIC_DIV64_H
+#define _ASM_GENERIC_DIV64_H
+/*
+ * Copyright (C) 2003 Bernardo Innocenti <bernie@develer.com>
+ * Based on former asm-ppc/div64.h and asm-m68knommu/div64.h
+ *
+ * The semantics of do_div() are:
+ *
+ * uint32_t do_div(uint64_t *n, uint32_t base)
+ * {
+ * 	uint32_t remainder = *n % base;
+ * 	*n = *n / base;
+ * 	return remainder;
+ * }
+ *
+ * NOTE: macro parameter n is evaluated multiple times,
+ *       beware of side effects!
+ */
+
+#include <linux/types.h>
+
+#if BITS_PER_LONG == 64
+
+# define do_div(n,base) ({					\
+	uint32_t __base = (base);				\
+	uint32_t __rem;						\
+	__rem = ((uint64_t)(n)) % __base;			\
+	(n) = ((uint64_t)(n)) / __base;				\
+	__rem;							\
+ })
+
+#elif BITS_PER_LONG == 32
+
+extern uint32_t __div64_32(uint64_t *dividend, uint32_t divisor);
+
+# define do_div(n,base) ({				\
+	uint32_t __base = (base);			\
+	uint32_t __rem;					\
+	if (((n) >> 32) == 0) {				\
+		__rem = (uint32_t)(n) % __base;		\
+		(n) = (uint32_t)(n) / __base;		\
+	} else 						\
+		__rem = __div64_32(&(n), __base);	\
+	__rem;						\
+ })
+
+#else /* BITS_PER_LONG == ?? */
+
+# error do_div() does not yet support the C64
+
+#endif /* BITS_PER_LONG */
+
+#endif /* _ASM_GENERIC_DIV64_H */
diff -Nru linux-2.5.74-uc0/include/asm-h8300/div64.h linux-2.5.74-uc0-develer/include/asm-h8300/div64.h
--- linux-2.5.74-uc0/include/asm-h8300/div64.h	2003-07-02 22:39:25.000000000 +0200
+++ linux-2.5.74-uc0-develer/include/asm-h8300/div64.h	2003-07-03 09:37:22.000000000 +0200
@@ -1,13 +1 @@
-#ifndef H8300_DIV64_H
-#define H8300_DIV64_H
-
-/* n = n / base; return rem; */
-
-#define do_div(n,base) ({					\
-	int __res;						\
-	__res = ((unsigned long) n) % (unsigned) base;		\
-	n = ((unsigned long) n) / (unsigned) base;		\
-	__res;							\
-})
-
-#endif /* _H8300_DIV64_H */
+#include <asm-generic/div64.h>
diff -Nru linux-2.5.74-uc0/include/asm-ia64/div64.h linux-2.5.74-uc0-develer/include/asm-ia64/div64.h
--- linux-2.5.74-uc0/include/asm-ia64/div64.h	2003-07-02 22:58:14.000000000 +0200
+++ linux-2.5.74-uc0-develer/include/asm-ia64/div64.h	2003-07-03 09:37:22.000000000 +0200
@@ -1,20 +1 @@
-#ifndef _ASM_IA64_DIV64_H
-#define _ASM_IA64_DIV64_H
-
-/*
- * Copyright (C) 1999 Hewlett-Packard Co
- * Copyright (C) 1999 David Mosberger-Tang <davidm@hpl.hp.com>
- *
- * vsprintf uses this to divide a 64-bit integer N by a small integer BASE.
- * This is incredibly hard on IA-64...
- */
-
-#define do_div(n,base)						\
-({								\
-	int _res;						\
-	_res = ((unsigned long) (n)) % (unsigned) (base);	\
-	(n) = ((unsigned long) (n)) / (unsigned) (base);	\
-	_res;							\
-})
-
-#endif /* _ASM_IA64_DIV64_H */
+#include <asm-generic/div64.h>
diff -Nru linux-2.5.74-uc0/include/asm-m68k/div64.h linux-2.5.74-uc0-develer/include/asm-m68k/div64.h
--- linux-2.5.74-uc0/include/asm-m68k/div64.h	2003-07-02 22:55:53.000000000 +0200
+++ linux-2.5.74-uc0-develer/include/asm-m68k/div64.h	2003-07-03 09:37:22.000000000 +0200
@@ -3,7 +3,6 @@
 
 /* n = n / base; return rem; */
 
-#if 1
 #define do_div(n, base) ({					\
 	union {							\
 		unsigned long n32[2];				\
@@ -23,13 +22,5 @@
 	(n) = __n.n64;						\
 	__rem;							\
 })
-#else
-#define do_div(n,base) ({					\
-	int __res;						\
-	__res = ((unsigned long) n) % (unsigned) base;		\
-	n = ((unsigned long) n) / (unsigned) base;		\
-	__res;							\
-})
-#endif
 
 #endif /* _M68K_DIV64_H */
diff -Nru linux-2.5.74-uc0/include/asm-m68knommu/div64.h linux-2.5.74-uc0-develer/include/asm-m68knommu/div64.h
--- linux-2.5.74-uc0/include/asm-m68knommu/div64.h	2003-07-03 10:40:35.000000000 +0200
+++ linux-2.5.74-uc0-develer/include/asm-m68knommu/div64.h	2003-07-03 09:37:22.000000000 +0200
@@ -1,13 +1 @@
-#ifndef _M68KNOMMU_DIV64_H
-#define _M68KNOMMU_DIV64_H
-
-/* n = n / base; return rem; */
-
-#define do_div(n,base) ({					\
-	int __res;						\
-	__res = ((unsigned long) n) % (unsigned) base;		\
-	n = ((unsigned long) n) / (unsigned) base;		\
-	__res;							\
-})
-
-#endif /* _M68K_DIV64_H */
+#include <asm-generic/div64.h>
diff -Nru linux-2.5.74-uc0/include/asm-mips64/div64.h linux-2.5.74-uc0-develer/include/asm-mips64/div64.h
--- linux-2.5.74-uc0/include/asm-mips64/div64.h	2003-07-02 22:47:26.000000000 +0200
+++ linux-2.5.74-uc0-develer/include/asm-mips64/div64.h	2003-07-03 09:39:28.000000000 +0200
@@ -27,23 +27,6 @@
 	(res) = __quot; \
 	__mod; })
 
-/*
- * Hey, we're already 64-bit, no
- * need to play games..
- */
-#define do_div(n, base) ({ \
-	unsigned long __quot; \
-	unsigned int __mod; \
-	unsigned long __div; \
-	unsigned int __base; \
-	\
-	__div = (n); \
-	__base = (base); \
-	\
-	__mod = __div % __base; \
-	__quot = __div / __base; \
-	\
-	(n) = __quot; \
-	__mod; })
+#include <asm-generic.h>
 
 #endif /* _ASM_DIV64_H */
diff -Nru linux-2.5.74-uc0/include/asm-parisc/div64.h linux-2.5.74-uc0-develer/include/asm-parisc/div64.h
--- linux-2.5.74-uc0/include/asm-parisc/div64.h	2003-07-02 22:48:40.000000000 +0200
+++ linux-2.5.74-uc0-develer/include/asm-parisc/div64.h	2003-07-03 09:37:22.000000000 +0200
@@ -1,54 +1 @@
-#ifndef __ASM_PARISC_DIV64
-#define __ASM_PARISC_DIV64
-
-#ifdef __LP64__
-
-/*
- * Copyright (C) 1999 Hewlett-Packard Co
- * Copyright (C) 1999 David Mosberger-Tang <davidm@hpl.hp.com>
- *
- * vsprintf uses this to divide a 64-bit integer N by a small integer BASE.
- * This is incredibly hard on IA-64 and HPPA
- */
-
-#define do_div(n,base)						\
-({								\
-	int _res;						\
-	_res = ((unsigned long) (n)) % (unsigned) (base);	\
-	(n) = ((unsigned long) (n)) / (unsigned) (base);	\
-	_res;							\
-})
-
-#else
-/*
- * unsigned long long division.  Yuck Yuck!  What is Linux coming to?
- * This is 100% disgusting
- */
-#define do_div(n,base)							\
-({									\
-	unsigned long __low, __low2, __high, __rem;			\
-	__low  = (n) & 0xffffffff;					\
-	__high = (n) >> 32;						\
-	if (__high) {							\
-		__rem   = __high % (unsigned long)base;			\
-		__high  = __high / (unsigned long)base;			\
-		__low2  = __low >> 16;					\
-		__low2 += __rem << 16;					\
-		__rem   = __low2 % (unsigned long)base;			\
-		__low2  = __low2 / (unsigned long)base;			\
-		__low   = __low & 0xffff;				\
-		__low  += __rem << 16;					\
-		__rem   = __low  % (unsigned long)base;			\
-		__low   = __low  / (unsigned long)base;			\
-		n = __low  + ((long long)__low2 << 16) +		\
-			((long long) __high << 32);			\
-	} else {							\
-		__rem = __low % (unsigned long)base;			\
-		n = (__low / (unsigned long)base);			\
-	}								\
-	__rem;								\
-})
-#endif
-
-#endif
-
+#include <asm-generic/div64.h>
diff -Nru linux-2.5.74-uc0/include/asm-ppc/div64.h linux-2.5.74-uc0-develer/include/asm-ppc/div64.h
--- linux-2.5.74-uc0/include/asm-ppc/div64.h	2003-07-02 22:57:06.000000000 +0200
+++ linux-2.5.74-uc0-develer/include/asm-ppc/div64.h	2003-07-03 09:37:22.000000000 +0200
@@ -1,23 +1 @@
-#ifndef __PPC_DIV64
-#define __PPC_DIV64
-
-#include <linux/types.h>
-
-extern u32 __div64_32(u64 *dividend, u32 div);
-
-#define do_div(n, div)	({			\
-	u64 __n = (n);				\
-	u32 __d = (div);			\
-	u32 __q, __r;				\
-	if ((__n >> 32) == 0) {			\
-		__q = (u32)__n / __d;		\
-		__r = (u32)__n - __q * __d;	\
-		(n) = __q;			\
-	} else {				\
-		__r = __div64_32(&__n, __d);	\
-		(n) = __n;			\
-	}					\
-	__r;					\
-})
-
-#endif
+#include <asm-generic/div64.h>
diff -Nru linux-2.5.74-uc0/include/asm-ppc64/div64.h linux-2.5.74-uc0-develer/include/asm-ppc64/div64.h
--- linux-2.5.74-uc0/include/asm-ppc64/div64.h	2003-07-02 22:39:34.000000000 +0200
+++ linux-2.5.74-uc0-develer/include/asm-ppc64/div64.h	2003-07-03 09:37:22.000000000 +0200
@@ -1,18 +1 @@
-#ifndef __PPC_DIV64
-#define __PPC_DIV64
-
-/* Copyright 2001 PPC64 Team, IBM Corp
- *
- * This program is free software; you can redistribute it and/or
- * modify it under the terms of the GNU General Public License
- * as published by the Free Software Foundation; either version
- * 2 of the License, or (at your option) any later version.
- */
-
-#define do_div(n,base) ({ \
-	int __res; \
-	__res = ((unsigned long) (n)) % (unsigned) (base); \
-	(n) = ((unsigned long) (n)) / (unsigned) (base); \
-	__res; })
-
-#endif
+#include <asm-generic/div64.h>
diff -Nru linux-2.5.74-uc0/include/asm-s390/div64.h linux-2.5.74-uc0-develer/include/asm-s390/div64.h
--- linux-2.5.74-uc0/include/asm-s390/div64.h	2003-07-02 22:50:17.000000000 +0200
+++ linux-2.5.74-uc0-develer/include/asm-s390/div64.h	2003-07-03 09:37:22.000000000 +0200
@@ -43,13 +43,7 @@
 })
 
 #else /* __s390x__ */
-
-#define do_div(n,base) ({ \
-int __res; \
-__res = ((unsigned long) n) % (unsigned) base; \
-n = ((unsigned long) n) / (unsigned) base; \
-__res; })
-
+#include <asm-generic/div64.h>
 #endif /* __s390x__ */
 
 #endif
diff -Nru linux-2.5.74-uc0/include/asm-sh/div64.h linux-2.5.74-uc0-develer/include/asm-sh/div64.h
--- linux-2.5.74-uc0/include/asm-sh/div64.h	2003-07-02 22:39:36.000000000 +0200
+++ linux-2.5.74-uc0-develer/include/asm-sh/div64.h	2003-07-03 09:38:59.000000000 +0200
@@ -1,20 +1 @@
-#ifndef __ASM_SH_DIV64
-#define __ASM_SH_DIV64
-
-extern u64 __div64_32(u64 n, u32 d);
-
-#define do_div(n,base) ({ \
-u64 __n = (n), __q; \
-u32 __base = (base); \
-u32 __res; \
-if ((__n >> 32) == 0) { \
-	__res = ((unsigned long) __n) % (unsigned) __base; \
-	(n) = ((unsigned long) __n) / (unsigned) __base; \
-} else { \
-	__q = __div64_32(__n, __base); \
-	__res = __n - __q * __base; \
-	(n) = __q; \
-} \
-__res; })
-
-#endif /* __ASM_SH_DIV64 */
+#include <asm-generic/div64.h>
diff -Nru linux-2.5.74-uc0/include/asm-sparc/div64.h linux-2.5.74-uc0-develer/include/asm-sparc/div64.h
--- linux-2.5.74-uc0/include/asm-sparc/div64.h	2003-07-02 22:51:01.000000000 +0200
+++ linux-2.5.74-uc0-develer/include/asm-sparc/div64.h	2003-07-03 09:37:22.000000000 +0200
@@ -1,11 +1 @@
-#ifndef __SPARC_DIV64
-#define __SPARC_DIV64
-
-/* We're not 64-bit, but... */
-#define do_div(n,base) ({ \
-	int __res; \
-	__res = ((unsigned long) n) % (unsigned) base; \
-	n = ((unsigned long) n) / (unsigned) base; \
-	__res; })
-
-#endif /* __SPARC_DIV64 */
+#include <asm-generic/div64.h>
diff -Nru linux-2.5.74-uc0/include/asm-sparc64/div64.h linux-2.5.74-uc0-develer/include/asm-sparc64/div64.h
--- linux-2.5.74-uc0/include/asm-sparc64/div64.h	2003-07-02 22:46:06.000000000 +0200
+++ linux-2.5.74-uc0-develer/include/asm-sparc64/div64.h	2003-07-03 09:37:22.000000000 +0200
@@ -1,14 +1 @@
-#ifndef __SPARC64_DIV64
-#define __SPARC64_DIV64
-
-/*
- * Hey, we're already 64-bit, no
- * need to play games..
- */
-#define do_div(n,base) ({ \
-	int __res; \
-	__res = ((unsigned long) n) % (unsigned) base; \
-	n = ((unsigned long) n) / (unsigned) base; \
-	__res; })
-
-#endif /* __SPARC64_DIV64 */
+#include <asm-generic/div64.h>
diff -Nru linux-2.5.74-uc0/include/asm-v850/div64.h linux-2.5.74-uc0-develer/include/asm-v850/div64.h
--- linux-2.5.74-uc0/include/asm-v850/div64.h	2003-07-02 22:53:46.000000000 +0200
+++ linux-2.5.74-uc0-develer/include/asm-v850/div64.h	2003-07-03 09:37:22.000000000 +0200
@@ -1,11 +1 @@
-#ifndef __V850_DIV64_H__
-#define __V850_DIV64_H__
-
-/* We're not 64-bit, but... */
-#define do_div(n,base) ({ \
-	int __res; \
-	__res = ((unsigned long) n) % (unsigned) base; \
-	n = ((unsigned long) n) / (unsigned) base; \
-	__res; })
-
-#endif /* __V850_DIV64_H__ */
+#include <asm-generic/div64.h>
diff -Nru linux-2.5.74-uc0/include/asm-x86_64/div64.h linux-2.5.74-uc0-develer/include/asm-x86_64/div64.h
--- linux-2.5.74-uc0/include/asm-x86_64/div64.h	2003-07-02 22:54:30.000000000 +0200
+++ linux-2.5.74-uc0-develer/include/asm-x86_64/div64.h	2003-07-03 09:37:22.000000000 +0200
@@ -1,14 +1 @@
-#ifndef __X86_64_DIV64
-#define __X86_64_DIV64
-
-/*
- * Hey, we're already 64-bit, no
- * need to play games..
- */
-#define do_div(n,base) ({ \
-	int __res; \
-	__res = ((unsigned long) (n)) % (unsigned) (base); \
-	(n) = ((unsigned long) (n)) / (unsigned) (base); \
-	__res; })
-
-#endif
+#include <asm-generic/div64.h>
diff -Nru linux-2.5.74-uc0/lib/Makefile linux-2.5.74-uc0-develer/lib/Makefile
--- linux-2.5.74-uc0/lib/Makefile	2003-07-02 22:40:29.000000000 +0200
+++ linux-2.5.74-uc0-develer/lib/Makefile	2003-07-03 09:37:22.000000000 +0200
@@ -5,7 +5,7 @@
 
 lib-y := errno.o ctype.o string.o vsprintf.o cmdline.o \
 	 bust_spinlocks.o rbtree.o radix-tree.o dump_stack.o \
-	 kobject.o idr.o
+	 kobject.o idr.o div64.o
 
 lib-$(CONFIG_RWSEM_GENERIC_SPINLOCK) += rwsem-spinlock.o
 lib-$(CONFIG_RWSEM_XCHGADD_ALGORITHM) += rwsem.o
diff -Nru linux-2.5.74-uc0/lib/div64.c linux-2.5.74-uc0-develer/lib/div64.c
--- linux-2.5.74-uc0/lib/div64.c	1970-01-01 01:00:00.000000000 +0100
+++ linux-2.5.74-uc0-develer/lib/div64.c	2003-07-03 09:37:22.000000000 +0200
@@ -0,0 +1,45 @@
+/*
+ * Copyright (C) 2003 Bernardo Innocenti <bernie@develer.com>
+ *
+ * Based on former do_div() implementation from asm-parisc/div64.h:
+ *	Copyright (C) 1999 Hewlett-Packard Co
+ *	Copyright (C) 1999 David Mosberger-Tang <davidm@hpl.hp.com>
+ *
+ *
+ * Generic C version of 64bit/32bit division and modulo, with
+ * 64bit result and 32bit remainder.
+ *
+ * The fast case for (n>>32 == 0) is handled inline by do_div(). 
+ *
+ * Code generated for this function might be very inefficient
+ * for some CPUs. div64_32() can be overridden by linking arch-specific
+ * assembly versions such as arch/ppc/lib/div64.S and arch/sh/lib/div64.S.
+ */
+
+#include <linux/types.h>
+#include <asm/div64.h>
+
+uint32_t __div64_32(uint64_t *n, uint32_t base)
+{
+	uint32_t low, low2, high, rem;
+
+	low   = *n   & 0xffffffff;
+	high  = *n  >> 32;
+	rem   = high % (uint32_t)base;
+	high  = high / (uint32_t)base;
+	low2  = low >> 16;
+	low2 += rem << 16;
+	rem   = low2 % (uint32_t)base;
+	low2  = low2 / (uint32_t)base;
+	low   = low  & 0xffff;
+	low  += rem << 16;
+	rem   = low  % (uint32_t)base;
+	low   = low  / (uint32_t)base;
+
+	*n = low +
+		((uint64_t)low2 << 16) +
+		((uint64_t)high << 32);
+
+	return rem;
+}
+

Re: [PATCH] Fix do_div() for all architectures

[Bernardo Innocenti]

On Thursday 10 July 2003 17:40, Richard Henderson wrote:
 > On Tue, Jul 08, 2003 at 08:27:26PM +0200, Bernardo Innocenti wrote:
 > > +extern uint32_t __div64_32(uint64_t *dividend, uint32_t divisor)
 > > __attribute_pure__;
 >
 > ...
 >
 > > +		__rem = __div64_32(&(n), __base);	\
 >
 > The pure declaration is very incorrect.  You're writing to N.

Here comes the obvious fix. Mea culpa, mea culpa, mea maxima culpa!

NOTE: I've intentionally left the __attribute_pure__ definition in
linux/compiler.h since it might apply to many other functions.


Linus, please apply and forgive me for getting this simple patch wrong
so many times in a row.

-------------------------------------------------------------------------

 - remove incorrect __attribute_pure__ from __div64_32() since it obviously
   clobbers memory through &(n);


diff -Nru linux-2.5.74-bk4.orig/include/asm-generic/div64.h linux-2.5.74-bk4/include/asm-generic/div64.h
--- linux-2.5.74-bk4.orig/include/asm-generic/div64.h   2003-07-11 01:00:44.000000000 +0200
+++ linux-2.5.74-bk4/include/asm-generic/div64.h        2003-07-11 00:59:52.000000000 +0200
@@ -32,7 +32,7 @@

 #elif BITS_PER_LONG == 32

-extern uint32_t __div64_32(uint64_t *dividend, uint32_t divisor) __attribute_pure__;
+extern uint32_t __div64_32(uint64_t *dividend, uint32_t divisor);

 # define do_div(n,base) ({                             \
        uint32_t __base = (base);                       \

-- 
  // Bernardo Innocenti - Develer S.r.l., R&D dept.
\X/  http://www.develer.com/

Please don't send Word attachments - http://www.gnu.org/philosophy/no-word-attachments.html

Re: [PATCH] Fix do_div() for all architectures

[Bernardo Innocenti]

On Thursday 10 July 2003 22:19, Andrea Arcangeli wrote:

 > >  Without type based alias analysis, the compiler is forced to flush
 > > all registers containing copies of memory objects before function
 > > call and reloading values from memory afterwards.
 >
 > the kernel isn't complaint with the alias analysis, that's why it has
 > to be turned off (-fnostrict-aliasing) or stuff would break.

Yeah, I noticed. Writing low-level code without breaking strict aliasing
rules can be quite difficult if you don't want to give up any of your clever
tricks. I have a set of macros for handling linked lists that I can't get to
compile without those damn alias warnings with the latest GCC versions.

Besides, pushing our philosophycal discussion forward, what the generic
do_div() is doing might be vary bad for performance. After extracting the
address of n, the compiler must conservatively assume that any following
pointer dereference or function call could alter the contents of n.

Since strict aliasing is turned off, access to the divisor will become
slow as hell. Almost as if it was declared volatile.

Ok, as Richard said, it's just the generic version for those who don't
care enough to write their own optimized version.

 > > Boy, that's ugly! It's too bad C can't do it the Perl way:
 > >
 > >     (n,rem) = __div64_32(n, base);
 >
 > or the python way:
 >
 > 	n, rem = __div64_32(n, base)
 >
 > ;)

 You beat me!

-- 
  // Bernardo Innocenti - Develer S.r.l., R&D dept.
\X/  http://www.develer.com/

Please don't send Word attachments - http://www.gnu.org/philosophy/no-word-attachments.html

Re: [PATCH] Fix do_div() for all architectures

[Richard Henderson]

On Thu, Jul 10, 2003 at 09:31:45PM +0200, Bernardo Innocenti wrote:
> Just to open some interesting speculation, do you think we'd
> get better code by just getting rid of __attribute__((pure))
> or by changing __do_div64() to do something like this?
> 
>  typedef struct { uint64_t quot, uint32_t rem } __quotrem64;
>  __quotrem64 __do_div64(uint64_t div, uint32_t base) __attribute__((const));

No.  Most targets require structures be returned in memory.

If people really care beyond the generic, they'll write
special assembly for it.


r~

Re: [PATCH] Fix do_div() for all architectures

[Andrea Arcangeli]

On Thu, Jul 10, 2003 at 09:31:45PM +0200, Bernardo Innocenti wrote:
> On Thursday 10 July 2003 18:39, Richard Henderson wrote:
> 
>  > On Thu, Jul 10, 2003 at 06:18:59PM +0200, Andrea Arcangeli wrote:
>  > > On Thu, Jul 10, 2003 at 08:40:19AM -0700, Richard Henderson wrote:
>  > > > On Tue, Jul 08, 2003 at 08:27:26PM +0200, Bernardo Innocenti wrote:
>  > > > > +extern uint32_t __div64_32(uint64_t *dividend, uint32_t
>  > > > > divisor) __attribute_pure__;
>  > > >
>  > > > ...
>  > > >
>  > > > > +		__rem = __div64_32(&(n), __base);	\
>  > > >
>  > > > The pure declaration is very incorrect.  You're writing to N.
>  > >
>  > > now pure sounds more reasonable, I wondered how could gcc keep track
>  > > of the stuff pointed by the parameters (especially if this stuff
>  > > points to other stuff etc.. ;).
> 
>  The compiler could easily tell what memory can be clobbered by a pointer
> by applying type-based aliasing rules. For example, a function taking a
> "char *" can't clobber memory objects declared as "long bar" or
> "struct foo".
> 
>  Without type based alias analysis, the compiler is forced to flush
> all registers containing copies of memory objects before function
> call and reloading values from memory afterwards.

the kernel isn't complaint with the alias analysis, that's why it has to
be turned off (-fnostrict-aliasing) or stuff would break.

> Boy, that's ugly! It's too bad C can't do it the Perl way:
> 
>     (n,rem) = __div64_32(n, base);

or the python way:

	n, rem = __div64_32(n, base)

;)

Andrea

Re: [PATCH] Fix do_div() for all architectures

[Dale Johannesen]

On Thursday, July 10, 2003, at 12:31  PM, Bernardo Innocenti wrote:
>
>  The compiler could easily tell what memory can be clobbered by a 
> pointer
> by applying type-based aliasing rules. For example, a function taking a
> "char *" can't clobber memory objects declared as "long bar" or
> "struct foo".

No, for two reasons.  First, anything can be aliased by a char.  Second,
the restriction is on the type of the eventual memory reference,
not on the type of the pointer.  Assuming an int* p, you can still do 
*((char*)p) and
that may alias anything.  So you must check each dereference; this 
can't be
done easily at function entry.

Re: [PATCH] Fix do_div() for all architectures

[Bernardo Innocenti]

On Thursday 10 July 2003 18:39, Richard Henderson wrote:

 > On Thu, Jul 10, 2003 at 06:18:59PM +0200, Andrea Arcangeli wrote:
 > > On Thu, Jul 10, 2003 at 08:40:19AM -0700, Richard Henderson wrote:
 > > > On Tue, Jul 08, 2003 at 08:27:26PM +0200, Bernardo Innocenti wrote:
 > > > > +extern uint32_t __div64_32(uint64_t *dividend, uint32_t
 > > > > divisor) __attribute_pure__;
 > > >
 > > > ...
 > > >
 > > > > +		__rem = __div64_32(&(n), __base);	\
 > > >
 > > > The pure declaration is very incorrect.  You're writing to N.
 > >
 > > now pure sounds more reasonable, I wondered how could gcc keep track
 > > of the stuff pointed by the parameters (especially if this stuff
 > > points to other stuff etc.. ;).

 The compiler could easily tell what memory can be clobbered by a pointer
by applying type-based aliasing rules. For example, a function taking a
"char *" can't clobber memory objects declared as "long bar" or
"struct foo".

 Without type based alias analysis, the compiler is forced to flush
all registers containing copies of memory objects before function
call and reloading values from memory afterwards.


 > Bernardo mis-interpreted the documentation. [...]

 I'm afraid you're right. Here's a code snippet from gcc/calls.c that
shows what the compiler _really_ does for pure calls:

  /* If the result of a pure or const function call is ignored (or void),
     and none of its arguments are volatile, we can avoid expanding the
     call and just evaluate the arguments for side-effects.  */
  if ((flags & (ECF_CONST | ECF_PURE))
      && (ignore || target == const0_rtx
          || TYPE_MODE (TREE_TYPE (exp)) == VOIDmode))
    {
      bool volatilep = false;
      tree arg;

      for (arg = actparms; arg; arg = TREE_CHAIN (arg))
        if (TREE_THIS_VOLATILE (TREE_VALUE (arg)))
          {
            volatilep = true;
            break;
          }

      if (! volatilep)
        {
          for (arg = actparms; arg; arg = TREE_CHAIN (arg))
            expand_expr (TREE_VALUE (arg), const0_rtx,
                         VOIDmode, EXPAND_NORMAL);
          return const0_rtx;
        }
    }


Therefore this optimization is to be undone. Would it work if
we could use references instead of pointers? I think it
wouldn't. A new attribute would be needed for this case.

Just to open some interesting speculation, do you think we'd
get better code by just getting rid of __attribute__((pure))
or by changing __do_div64() to do something like this?

 typedef struct { uint64_t quot, uint32_t rem } __quotrem64;
 __quotrem64 __do_div64(uint64_t div, uint32_t base) __attribute__((const));

 #define do_div(n,base) ({                                        \
        uint32_t __base = (base);                                 \
        uint32_t __rem;                                           \
        if (likely(((n) >> 32) == 0)) {                           \
                __rem = (uint32_t)(n) % __base;                   \
                (n) = (uint32_t)(n) / __base;                     \
        } else {                                                  \
                __quotrem64 __qr = __div64_32((n), __base);       \
                (n) = __qr.quot;                                  \
                __rem = __qr.rem;                                 \
        }                                                         \
        __rem;                                                    \
 })

Boy, that's ugly! It's too bad C can't do it the Perl way:

    (n,rem) = __div64_32(n, base);

-- 
  // Bernardo Innocenti - Develer S.r.l., R&D dept.
\X/  http://www.develer.com/

Please don't send Word attachments - http://www.gnu.org/philosophy/no-word-attachments.html

Re: [PATCH] Fix do_div() for all architectures

[Richard Henderson]

On Thu, Jul 10, 2003 at 06:18:59PM +0200, Andrea Arcangeli wrote:
> On Thu, Jul 10, 2003 at 08:40:19AM -0700, Richard Henderson wrote:
> > On Tue, Jul 08, 2003 at 08:27:26PM +0200, Bernardo Innocenti wrote:
> > > +extern uint32_t __div64_32(uint64_t *dividend, uint32_t divisor)
> > > __attribute_pure__;
> > ...
> > > +		__rem = __div64_32(&(n), __base);	\
> > 
> > The pure declaration is very incorrect.  You're writing to N.
> 
> now pure sounds more reasonable, I wondered how could gcc keep track of
> the stuff pointed by the parameters (especially if this stuff points to
> other stuff etc.. ;).

Bernardo mis-interpreted the documentation.

Define "local memory" as memory from the current stack frame.

Define "non-local memory" as anything else (including stack memory from
another function, or a different instantiation of the current function).

Any function can read/write local memory (since that is not visible to
anyone outside the function).

A "const" function cannot read or write to non-local memory.  There are
further constraints on not returning abnormally or not returning at all
that I'll not go into now.

A "pure" function can read non-local memory, but cannot write to it.

We use those conditions to determine if two invocations of a function
can be collapsed or moved or removed.



r~

Re: [PATCH] Fix do_div() for all architectures

[Andrea Arcangeli]

On Thu, Jul 10, 2003 at 08:40:19AM -0700, Richard Henderson wrote:
> On Tue, Jul 08, 2003 at 08:27:26PM +0200, Bernardo Innocenti wrote:
> > +extern uint32_t __div64_32(uint64_t *dividend, uint32_t divisor)
> > __attribute_pure__;
> ...
> > +		__rem = __div64_32(&(n), __base);	\
> 
> The pure declaration is very incorrect.  You're writing to N.

now pure sounds more reasonable, I wondered how could gcc keep track of
the stuff pointed by the parameters (especially if this stuff points to
other stuff etc.. ;). So only the pointer passed as parameter can
change, not the memory pointed by the pointer as in this case.

Andrea

Re: [PATCH] Fix do_div() for all architectures

[Richard Henderson]

On Tue, Jul 08, 2003 at 08:27:26PM +0200, Bernardo Innocenti wrote:
> +extern uint32_t __div64_32(uint64_t *dividend, uint32_t divisor)
> __attribute_pure__;
...
> +		__rem = __div64_32(&(n), __base);	\

The pure declaration is very incorrect.  You're writing to N.


r~

Re: [PATCH] Fix do_div() for all architectures

[Bernardo Innocenti]

On Tuesday 08 July 2003 20:31, Andrew Morton wrote:
 > Bernardo Innocenti <bernie@develer.com> wrote:
 > >  Andrew, would you like to pick this patch up for me and forward it
 > > to Linus after it received some testing in -mm?
 >
 > It got merged ages ago ;)  Linus simply removed the pure thing.

 Oops. He didn't remove it, he just picked up my older version
which also missed an important bug fix.

 Here's an incremental patch against 2.5.74-bk4. Please apply.

---------------------------------------------------------------------

Fix problem introduced by previous do_div() patch:

 - export the __div64_32 symbol for modules;

 - add likely() to the fast path (divisor>>32 == 0);

 - add __attribute__((pure)) to __div64_32() prototype so
   the compiler knows global memory isn't clobbered;

 - avoid building __div64_32() on 64bit architectures.


diff -Nru linux-2.5.74-bk4.orig/include/asm-generic/div64.h linux-2.5.74-bk4/include/asm-generic/div64.h
--- linux-2.5.74-bk4.orig/include/asm-generic/div64.h	2003-07-08 22:29:32.000000000 +0200
+++ linux-2.5.74-bk4/include/asm-generic/div64.h	2003-07-08 22:45:21.000000000 +0200
@@ -18,6 +18,7 @@
  */
 
 #include <linux/types.h>
+#include <linux/compiler.h>
 
 #if BITS_PER_LONG == 64
 
@@ -31,12 +32,12 @@
 
 #elif BITS_PER_LONG == 32
 
-extern uint32_t __div64_32(uint64_t *dividend, uint32_t divisor);
+extern uint32_t __div64_32(uint64_t *dividend, uint32_t divisor) __attribute_pure__;
 
 # define do_div(n,base) ({				\
 	uint32_t __base = (base);			\
 	uint32_t __rem;					\
-	if (((n) >> 32) == 0) {				\
+	if (likely(((n) >> 32) == 0)) {			\
 		__rem = (uint32_t)(n) % __base;		\
 		(n) = (uint32_t)(n) / __base;		\
 	} else 						\
diff -Nru linux-2.5.74-bk4.orig/include/linux/compiler.h linux-2.5.74-bk4/include/linux/compiler.h
--- linux-2.5.74-bk4.orig/include/linux/compiler.h	2003-07-08 22:23:25.000000000 +0200
+++ linux-2.5.74-bk4/include/linux/compiler.h	2003-07-08 22:45:21.000000000 +0200
@@ -56,6 +56,24 @@
 #define __attribute_used__	__attribute__((__unused__))
 #endif
 
+/*
+ * From the GCC manual:
+ *
+ * Many functions have no effects except the return value and their
+ * return value depends only on the parameters and/or global
+ * variables.  Such a function can be subject to common subexpression
+ * elimination and loop optimization just as an arithmetic operator
+ * would be.
+ * [...]
+ * The attribute `pure' is not implemented in GCC versions earlier
+ * than 2.96.
+ */
+#if (__GNUC__ == 2 && __GNUC_MINOR >= 96) || __GNUC__ > 2
+#define __attribute_pure__	__attribute__((pure))
+#else
+#define __attribute_pure__	/* unimplemented */
+#endif
+
 /* This macro obfuscates arithmetic on a variable address so that gcc
    shouldn't recognize the original var, and make assumptions about it */
 #define RELOC_HIDE(ptr, off)					\
diff -Nru linux-2.5.74-bk4.orig/lib/div64.c linux-2.5.74-bk4/lib/div64.c
--- linux-2.5.74-bk4.orig/lib/div64.c	2003-07-08 22:29:32.000000000 +0200
+++ linux-2.5.74-bk4/lib/div64.c	2003-07-08 22:45:21.000000000 +0200
@@ -12,13 +12,17 @@
  * The fast case for (n>>32 == 0) is handled inline by do_div(). 
  *
  * Code generated for this function might be very inefficient
- * for some CPUs. div64_32() can be overridden by linking arch-specific
+ * for some CPUs. __div64_32() can be overridden by linking arch-specific
  * 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>
 
+/* Not needed on 64bit architectures */
+#if BITS_PER_LONG == 32
+
 uint32_t __div64_32(uint64_t *n, uint32_t base)
 {
 	uint32_t low, low2, high, rem;
@@ -43,3 +47,6 @@
 	return rem;
 }
 
+EXPORT_SYMBOL(__div64_32);
+
+#endif /* BITS_PER_LONG == 32 */



-- 
  // Bernardo Innocenti - Develer S.r.l., R&D dept.
\X/  http://www.develer.com/

Please don't send Word attachments - http://www.gnu.org/philosophy/no-word-attachments.html

Re: [PATCH] Fix do_div() for all architectures

[Andrew Morton]

Bernardo Innocenti <bernie@develer.com> wrote:
>
>  Andrew, would you like to pick this patch up for me and forward it
> to Linus after it received some testing in -mm?

It got merged ages ago ;)  Linus simply removed the pure thing.

Re: [PATCH] Fix do_div() for all architectures

[Bernardo Innocenti]

On Sunday 06 July 2003 01:33, Bernardo Innocenti wrote:

 > >  - add __attribute__((pure)) to __div64_32() prototype so
 > >    the compiler knows global memory isn't clobbered;
 >
 >  Hmmm... I've just found out that the pure attribute wasn't
 > supported until gcc 2.96. Shall I get rid of it or maybe add
 > something in linux/compiler.h?

 Ok, I've now placed a new __attribute_pure__ macro in
linux/compiler.h to workaround this. New patch follows.

 Andrew, would you like to pick this patch up for me and forward it
to Linus after it received some testing in -mm?

-----------------------------------------------------------------

 - add generic C implementations of the do_div() for 32bit and 64bit
   archs in asm-generic/div64.h;

 - add generic library support function __div64_32() to handle the
   full 64/32 case on 32bit archs;

 - kill multiple copies of generic do_div() in architecture
   specific subdirs. Most copies were either buggy or not doing
   what they were supposed to do;

 - ensure all surviving instances of do_div() have their parameters
   correctly parenthesized to avoid funny side-effects;

 include/asm-alpha/div64.h     |   15 -----------
 include/asm-arm26/div64.h     |   15 -----------
 include/asm-cris/div64.h      |   17 ------------
 include/asm-generic/div64.h   |   54 +++++++++++++++++++++++++++++++++++++++++
 include/asm-h8300/div64.h     |   14 ----------
 include/asm-ia64/div64.h      |   21 ----------------
 include/asm-m68k/div64.h      |    9 ------
 include/asm-m68knommu/div64.h |   14 ----------
 include/asm-mips64/div64.h    |   19 --------------
 include/asm-parisc/div64.h    |   55 ------------------------------------------
 include/asm-ppc/div64.h       |   24 ------------------
 include/asm-ppc64/div64.h     |   19 --------------
 include/asm-s390/div64.h      |    8 ------
 include/asm-sh/div64.h        |   21 ----------------
 include/asm-sparc/div64.h     |   12 ---------
 include/asm-sparc64/div64.h   |   15 -----------
 include/asm-v850/div64.h      |   12 ---------
 include/asm-x86_64/div64.h    |   15 -----------
 include/linux/compiler.h      |   18 +++++++++++++
 lib/Makefile                  |    2 -
 lib/div64.c                   |   52 +++++++++++++++++++++++++++++++++++++++
 21 files changed, 141 insertions(+), 290 deletions(-)

diff -Nru linux-2.5.74.orig/include/asm-generic/div64.h linux-2.5.74/include/asm-generic/div64.h
--- linux-2.5.74.orig/include/asm-generic/div64.h	1970-01-01 01:00:00.000000000 +0100
+++ linux-2.5.74/include/asm-generic/div64.h	2003-07-03 09:55:04.000000000 +0200
@@ -0,0 +1,54 @@
+#ifndef _ASM_GENERIC_DIV64_H
+#define _ASM_GENERIC_DIV64_H
+/*
+ * Copyright (C) 2003 Bernardo Innocenti <bernie@develer.com>
+ * Based on former asm-ppc/div64.h and asm-m68knommu/div64.h
+ *
+ * The semantics of do_div() are:
+ *
+ * uint32_t do_div(uint64_t *n, uint32_t base)
+ * {
+ * 	uint32_t remainder = *n % base;
+ * 	*n = *n / base;
+ * 	return remainder;
+ * }
+ *
+ * NOTE: macro parameter n is evaluated multiple times,
+ *       beware of side effects!
+ */
+
+#include <linux/types.h>
+#include <linux/compiler.h>
+
+#if BITS_PER_LONG == 64
+
+# define do_div(n,base) ({					\
+	uint32_t __base = (base);				\
+	uint32_t __rem;						\
+	__rem = ((uint64_t)(n)) % __base;			\
+	(n) = ((uint64_t)(n)) / __base;				\
+	__rem;							\
+ })
+
+#elif BITS_PER_LONG == 32
+
+extern uint32_t __div64_32(uint64_t *dividend, uint32_t divisor) __attribute_pure__;
+
+# define do_div(n,base) ({				\
+	uint32_t __base = (base);			\
+	uint32_t __rem;					\
+	if (likely(((n) >> 32) == 0)) {			\
+		__rem = (uint32_t)(n) % __base;		\
+		(n) = (uint32_t)(n) / __base;		\
+	} else 						\
+		__rem = __div64_32(&(n), __base);	\
+	__rem;						\
+ })
+
+#else /* BITS_PER_LONG == ?? */
+
+# error do_div() does not yet support the C64
+
+#endif /* BITS_PER_LONG */
+
+#endif /* _ASM_GENERIC_DIV64_H */
diff -Nru linux-2.5.74.orig/include/linux/compiler.h linux-2.5.74/include/linux/compiler.h
--- linux-2.5.74.orig/include/linux/compiler.h	2003-07-02 22:50:12.000000000 +0200
+++ linux-2.5.74/include/linux/compiler.h	2003-07-08 19:24:41.000000000 +0200
@@ -56,6 +56,24 @@
 #define __attribute_used__	__attribute__((__unused__))
 #endif
 
+/*
+ * From the GCC manual:
+ *
+ * Many functions have no effects except the return value and their
+ * return value depends only on the parameters and/or global
+ * variables.  Such a function can be subject to common subexpression
+ * elimination and loop optimization just as an arithmetic operator
+ * would be.
+ * [...]
+ * The attribute `pure' is not implemented in GCC versions earlier
+ * than 2.96.
+ */
+#if (__GNUC__ == 2 && __GNUC_MINOR >= 96) || __GNUC__ > 2
+#define __attribute_pure__	__attribute__((pure))
+#else
+#define __attribute_pure__	/* unimplemented */
+#endif
+
 /* This macro obfuscates arithmetic on a variable address so that gcc
    shouldn't recognize the original var, and make assumptions about it */
 #define RELOC_HIDE(ptr, off)					\
diff -Nru linux-2.5.74.orig/lib/div64.c linux-2.5.74/lib/div64.c
--- linux-2.5.74.orig/lib/div64.c	1970-01-01 01:00:00.000000000 +0100
+++ linux-2.5.74/lib/div64.c	2003-07-03 09:37:22.000000000 +0200
@@ -0,0 +1,52 @@
+/*
+ * Copyright (C) 2003 Bernardo Innocenti <bernie@develer.com>
+ *
+ * Based on former do_div() implementation from asm-parisc/div64.h:
+ *	Copyright (C) 1999 Hewlett-Packard Co
+ *	Copyright (C) 1999 David Mosberger-Tang <davidm@hpl.hp.com>
+ *
+ *
+ * Generic C version of 64bit/32bit division and modulo, with
+ * 64bit result and 32bit remainder.
+ *
+ * The fast case for (n>>32 == 0) is handled inline by do_div(). 
+ *
+ * Code generated for this function might be very inefficient
+ * for some CPUs. __div64_32() can be overridden by linking arch-specific
+ * 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>
+
+/* Not needed on 64bit architectures */
+#if BITS_PER_LONG == 32
+
+uint32_t __div64_32(uint64_t *n, uint32_t base)
+{
+	uint32_t low, low2, high, rem;
+
+	low   = *n   & 0xffffffff;
+	high  = *n  >> 32;
+	rem   = high % (uint32_t)base;
+	high  = high / (uint32_t)base;
+	low2  = low >> 16;
+	low2 += rem << 16;
+	rem   = low2 % (uint32_t)base;
+	low2  = low2 / (uint32_t)base;
+	low   = low  & 0xffff;
+	low  += rem << 16;
+	rem   = low  % (uint32_t)base;
+	low   = low  / (uint32_t)base;
+
+	*n = low +
+		((uint64_t)low2 << 16) +
+		((uint64_t)high << 32);
+
+	return rem;
+}
+
+EXPORT_SYMBOL(__div64_32);
+
+#endif /* BITS_PER_LONG == 32 */
diff -Nru linux-2.5.74.orig/include/asm-alpha/div64.h linux-2.5.74/include/asm-alpha/div64.h
--- linux-2.5.74.orig/include/asm-alpha/div64.h	2003-07-02 22:54:43.000000000 +0200
+++ linux-2.5.74/include/asm-alpha/div64.h	2003-07-03 09:37:22.000000000 +0200
@@ -1,14 +1 @@
-#ifndef __ALPHA_DIV64
-#define __ALPHA_DIV64
-
-/*
- * Hey, we're already 64-bit, no
- * need to play games..
- */
-#define do_div(n,base) ({ \
-	int __res; \
-	__res = ((unsigned long) (n)) % (unsigned) (base); \
-	(n) = ((unsigned long) (n)) / (unsigned) (base); \
-	__res; })
-
-#endif
+#include <asm-generic/div64.h>
diff -Nru linux-2.5.74.orig/include/asm-arm26/div64.h linux-2.5.74/include/asm-arm26/div64.h
--- linux-2.5.74.orig/include/asm-arm26/div64.h	2003-07-02 22:42:11.000000000 +0200
+++ linux-2.5.74/include/asm-arm26/div64.h	2003-07-03 09:37:22.000000000 +0200
@@ -1,14 +1 @@
-#ifndef __ASM_ARM_DIV64
-#define __ASM_ARM_DIV64
-
-/* We're not 64-bit, but... */
-#define do_div(n,base)						\
-({								\
-	int __res;						\
-	__res = ((unsigned long)n) % (unsigned int)base;	\
-	n = ((unsigned long)n) / (unsigned int)base;		\
-	__res;							\
-})
-
-#endif
-
+#include <asm-generic/div64.h>
diff -Nru linux-2.5.74.orig/include/asm-cris/div64.h linux-2.5.74/include/asm-cris/div64.h
--- linux-2.5.74.orig/include/asm-cris/div64.h	2003-07-02 22:42:06.000000000 +0200
+++ linux-2.5.74/include/asm-cris/div64.h	2003-07-03 09:37:22.000000000 +0200
@@ -1,16 +1 @@
-#ifndef __ASM_CRIS_DIV64
-#define __ASM_CRIS_DIV64
-
-/* copy from asm-arm */
-
-/* We're not 64-bit, but... */
-#define do_div(n,base)						\
-({								\
-	int __res;						\
-	__res = ((unsigned long)n) % (unsigned int)base;	\
-	n = ((unsigned long)n) / (unsigned int)base;		\
-	__res;							\
-})
-
-#endif
-
+#include <asm-generic/div64.h>
diff -Nru linux-2.5.74.orig/include/asm-h8300/div64.h linux-2.5.74/include/asm-h8300/div64.h
--- linux-2.5.74.orig/include/asm-h8300/div64.h	2003-07-02 22:39:25.000000000 +0200
+++ linux-2.5.74/include/asm-h8300/div64.h	2003-07-03 09:37:22.000000000 +0200
@@ -1,13 +1 @@
-#ifndef H8300_DIV64_H
-#define H8300_DIV64_H
-
-/* n = n / base; return rem; */
-
-#define do_div(n,base) ({					\
-	int __res;						\
-	__res = ((unsigned long) n) % (unsigned) base;		\
-	n = ((unsigned long) n) / (unsigned) base;		\
-	__res;							\
-})
-
-#endif /* _H8300_DIV64_H */
+#include <asm-generic/div64.h>
diff -Nru linux-2.5.74.orig/include/asm-ia64/div64.h linux-2.5.74/include/asm-ia64/div64.h
--- linux-2.5.74.orig/include/asm-ia64/div64.h	2003-07-02 22:58:14.000000000 +0200
+++ linux-2.5.74/include/asm-ia64/div64.h	2003-07-03 09:37:22.000000000 +0200
@@ -1,20 +1 @@
-#ifndef _ASM_IA64_DIV64_H
-#define _ASM_IA64_DIV64_H
-
-/*
- * Copyright (C) 1999 Hewlett-Packard Co
- * Copyright (C) 1999 David Mosberger-Tang <davidm@hpl.hp.com>
- *
- * vsprintf uses this to divide a 64-bit integer N by a small integer BASE.
- * This is incredibly hard on IA-64...
- */
-
-#define do_div(n,base)						\
-({								\
-	int _res;						\
-	_res = ((unsigned long) (n)) % (unsigned) (base);	\
-	(n) = ((unsigned long) (n)) / (unsigned) (base);	\
-	_res;							\
-})
-
-#endif /* _ASM_IA64_DIV64_H */
+#include <asm-generic/div64.h>
diff -Nru linux-2.5.74.orig/include/asm-m68k/div64.h linux-2.5.74/include/asm-m68k/div64.h
--- linux-2.5.74.orig/include/asm-m68k/div64.h	2003-07-02 22:55:53.000000000 +0200
+++ linux-2.5.74/include/asm-m68k/div64.h	2003-07-03 09:37:22.000000000 +0200
@@ -3,7 +3,6 @@
 
 /* n = n / base; return rem; */
 
-#if 1
 #define do_div(n, base) ({					\
 	union {							\
 		unsigned long n32[2];				\
@@ -23,13 +22,5 @@
 	(n) = __n.n64;						\
 	__rem;							\
 })
-#else
-#define do_div(n,base) ({					\
-	int __res;						\
-	__res = ((unsigned long) n) % (unsigned) base;		\
-	n = ((unsigned long) n) / (unsigned) base;		\
-	__res;							\
-})
-#endif
 
 #endif /* _M68K_DIV64_H */
diff -Nru linux-2.5.74.orig/include/asm-m68knommu/div64.h linux-2.5.74/include/asm-m68knommu/div64.h
--- linux-2.5.74.orig/include/asm-m68knommu/div64.h	2003-07-03 10:40:35.000000000 +0200
+++ linux-2.5.74/include/asm-m68knommu/div64.h	2003-07-03 09:37:22.000000000 +0200
@@ -1,13 +1 @@
-#ifndef _M68KNOMMU_DIV64_H
-#define _M68KNOMMU_DIV64_H
-
-/* n = n / base; return rem; */
-
-#define do_div(n,base) ({					\
-	int __res;						\
-	__res = ((unsigned long) n) % (unsigned) base;		\
-	n = ((unsigned long) n) / (unsigned) base;		\
-	__res;							\
-})
-
-#endif /* _M68K_DIV64_H */
+#include <asm-generic/div64.h>
diff -Nru linux-2.5.74.orig/include/asm-mips64/div64.h linux-2.5.74/include/asm-mips64/div64.h
--- linux-2.5.74.orig/include/asm-mips64/div64.h	2003-07-02 22:47:26.000000000 +0200
+++ linux-2.5.74/include/asm-mips64/div64.h	2003-07-03 09:39:28.000000000 +0200
@@ -27,23 +27,6 @@
 	(res) = __quot; \
 	__mod; })
 
-/*
- * Hey, we're already 64-bit, no
- * need to play games..
- */
-#define do_div(n, base) ({ \
-	unsigned long __quot; \
-	unsigned int __mod; \
-	unsigned long __div; \
-	unsigned int __base; \
-	\
-	__div = (n); \
-	__base = (base); \
-	\
-	__mod = __div % __base; \
-	__quot = __div / __base; \
-	\
-	(n) = __quot; \
-	__mod; })
+#include <asm-generic.h>
 
 #endif /* _ASM_DIV64_H */
diff -Nru linux-2.5.74.orig/include/asm-parisc/div64.h linux-2.5.74/include/asm-parisc/div64.h
--- linux-2.5.74.orig/include/asm-parisc/div64.h	2003-07-02 22:48:40.000000000 +0200
+++ linux-2.5.74/include/asm-parisc/div64.h	2003-07-03 09:37:22.000000000 +0200
@@ -1,54 +1 @@
-#ifndef __ASM_PARISC_DIV64
-#define __ASM_PARISC_DIV64
-
-#ifdef __LP64__
-
-/*
- * Copyright (C) 1999 Hewlett-Packard Co
- * Copyright (C) 1999 David Mosberger-Tang <davidm@hpl.hp.com>
- *
- * vsprintf uses this to divide a 64-bit integer N by a small integer BASE.
- * This is incredibly hard on IA-64 and HPPA
- */
-
-#define do_div(n,base)						\
-({								\
-	int _res;						\
-	_res = ((unsigned long) (n)) % (unsigned) (base);	\
-	(n) = ((unsigned long) (n)) / (unsigned) (base);	\
-	_res;							\
-})
-
-#else
-/*
- * unsigned long long division.  Yuck Yuck!  What is Linux coming to?
- * This is 100% disgusting
- */
-#define do_div(n,base)							\
-({									\
-	unsigned long __low, __low2, __high, __rem;			\
-	__low  = (n) & 0xffffffff;					\
-	__high = (n) >> 32;						\
-	if (__high) {							\
-		__rem   = __high % (unsigned long)base;			\
-		__high  = __high / (unsigned long)base;			\
-		__low2  = __low >> 16;					\
-		__low2 += __rem << 16;					\
-		__rem   = __low2 % (unsigned long)base;			\
-		__low2  = __low2 / (unsigned long)base;			\
-		__low   = __low & 0xffff;				\
-		__low  += __rem << 16;					\
-		__rem   = __low  % (unsigned long)base;			\
-		__low   = __low  / (unsigned long)base;			\
-		n = __low  + ((long long)__low2 << 16) +		\
-			((long long) __high << 32);			\
-	} else {							\
-		__rem = __low % (unsigned long)base;			\
-		n = (__low / (unsigned long)base);			\
-	}								\
-	__rem;								\
-})
-#endif
-
-#endif
-
+#include <asm-generic/div64.h>
diff -Nru linux-2.5.74.orig/include/asm-ppc/div64.h linux-2.5.74/include/asm-ppc/div64.h
--- linux-2.5.74.orig/include/asm-ppc/div64.h	2003-07-02 22:57:06.000000000 +0200
+++ linux-2.5.74/include/asm-ppc/div64.h	2003-07-03 09:37:22.000000000 +0200
@@ -1,23 +1 @@
-#ifndef __PPC_DIV64
-#define __PPC_DIV64
-
-#include <linux/types.h>
-
-extern u32 __div64_32(u64 *dividend, u32 div);
-
-#define do_div(n, div)	({			\
-	u64 __n = (n);				\
-	u32 __d = (div);			\
-	u32 __q, __r;				\
-	if ((__n >> 32) == 0) {			\
-		__q = (u32)__n / __d;		\
-		__r = (u32)__n - __q * __d;	\
-		(n) = __q;			\
-	} else {				\
-		__r = __div64_32(&__n, __d);	\
-		(n) = __n;			\
-	}					\
-	__r;					\
-})
-
-#endif
+#include <asm-generic/div64.h>
diff -Nru linux-2.5.74.orig/include/asm-ppc64/div64.h linux-2.5.74/include/asm-ppc64/div64.h
--- linux-2.5.74.orig/include/asm-ppc64/div64.h	2003-07-02 22:39:34.000000000 +0200
+++ linux-2.5.74/include/asm-ppc64/div64.h	2003-07-03 09:37:22.000000000 +0200
@@ -1,18 +1 @@
-#ifndef __PPC_DIV64
-#define __PPC_DIV64
-
-/* Copyright 2001 PPC64 Team, IBM Corp
- *
- * This program is free software; you can redistribute it and/or
- * modify it under the terms of the GNU General Public License
- * as published by the Free Software Foundation; either version
- * 2 of the License, or (at your option) any later version.
- */
-
-#define do_div(n,base) ({ \
-	int __res; \
-	__res = ((unsigned long) (n)) % (unsigned) (base); \
-	(n) = ((unsigned long) (n)) / (unsigned) (base); \
-	__res; })
-
-#endif
+#include <asm-generic/div64.h>
diff -Nru linux-2.5.74.orig/include/asm-s390/div64.h linux-2.5.74/include/asm-s390/div64.h
--- linux-2.5.74.orig/include/asm-s390/div64.h	2003-07-02 22:50:17.000000000 +0200
+++ linux-2.5.74/include/asm-s390/div64.h	2003-07-03 09:37:22.000000000 +0200
@@ -43,13 +43,7 @@
 })
 
 #else /* __s390x__ */
-
-#define do_div(n,base) ({ \
-int __res; \
-__res = ((unsigned long) n) % (unsigned) base; \
-n = ((unsigned long) n) / (unsigned) base; \
-__res; })
-
+#include <asm-generic/div64.h>
 #endif /* __s390x__ */
 
 #endif
diff -Nru linux-2.5.74.orig/include/asm-sh/div64.h linux-2.5.74/include/asm-sh/div64.h
--- linux-2.5.74.orig/include/asm-sh/div64.h	2003-07-02 22:39:36.000000000 +0200
+++ linux-2.5.74/include/asm-sh/div64.h	2003-07-03 09:38:59.000000000 +0200
@@ -1,20 +1 @@
-#ifndef __ASM_SH_DIV64
-#define __ASM_SH_DIV64
-
-extern u64 __div64_32(u64 n, u32 d);
-
-#define do_div(n,base) ({ \
-u64 __n = (n), __q; \
-u32 __base = (base); \
-u32 __res; \
-if ((__n >> 32) == 0) { \
-	__res = ((unsigned long) __n) % (unsigned) __base; \
-	(n) = ((unsigned long) __n) / (unsigned) __base; \
-} else { \
-	__q = __div64_32(__n, __base); \
-	__res = __n - __q * __base; \
-	(n) = __q; \
-} \
-__res; })
-
-#endif /* __ASM_SH_DIV64 */
+#include <asm-generic/div64.h>
diff -Nru linux-2.5.74.orig/include/asm-sparc/div64.h linux-2.5.74/include/asm-sparc/div64.h
--- linux-2.5.74.orig/include/asm-sparc/div64.h	2003-07-02 22:51:01.000000000 +0200
+++ linux-2.5.74/include/asm-sparc/div64.h	2003-07-03 09:37:22.000000000 +0200
@@ -1,11 +1 @@
-#ifndef __SPARC_DIV64
-#define __SPARC_DIV64
-
-/* We're not 64-bit, but... */
-#define do_div(n,base) ({ \
-	int __res; \
-	__res = ((unsigned long) n) % (unsigned) base; \
-	n = ((unsigned long) n) / (unsigned) base; \
-	__res; })
-
-#endif /* __SPARC_DIV64 */
+#include <asm-generic/div64.h>
diff -Nru linux-2.5.74.orig/include/asm-sparc64/div64.h linux-2.5.74/include/asm-sparc64/div64.h
--- linux-2.5.74.orig/include/asm-sparc64/div64.h	2003-07-02 22:46:06.000000000 +0200
+++ linux-2.5.74/include/asm-sparc64/div64.h	2003-07-03 09:37:22.000000000 +0200
@@ -1,14 +1 @@
-#ifndef __SPARC64_DIV64
-#define __SPARC64_DIV64
-
-/*
- * Hey, we're already 64-bit, no
- * need to play games..
- */
-#define do_div(n,base) ({ \
-	int __res; \
-	__res = ((unsigned long) n) % (unsigned) base; \
-	n = ((unsigned long) n) / (unsigned) base; \
-	__res; })
-
-#endif /* __SPARC64_DIV64 */
+#include <asm-generic/div64.h>
diff -Nru linux-2.5.74.orig/include/asm-v850/div64.h linux-2.5.74/include/asm-v850/div64.h
--- linux-2.5.74.orig/include/asm-v850/div64.h	2003-07-02 22:53:46.000000000 +0200
+++ linux-2.5.74/include/asm-v850/div64.h	2003-07-03 09:37:22.000000000 +0200
@@ -1,11 +1 @@
-#ifndef __V850_DIV64_H__
-#define __V850_DIV64_H__
-
-/* We're not 64-bit, but... */
-#define do_div(n,base) ({ \
-	int __res; \
-	__res = ((unsigned long) n) % (unsigned) base; \
-	n = ((unsigned long) n) / (unsigned) base; \
-	__res; })
-
-#endif /* __V850_DIV64_H__ */
+#include <asm-generic/div64.h>
diff -Nru linux-2.5.74.orig/include/asm-x86_64/div64.h linux-2.5.74/include/asm-x86_64/div64.h
--- linux-2.5.74.orig/include/asm-x86_64/div64.h	2003-07-02 22:54:30.000000000 +0200
+++ linux-2.5.74/include/asm-x86_64/div64.h	2003-07-03 09:37:22.000000000 +0200
@@ -1,14 +1 @@
-#ifndef __X86_64_DIV64
-#define __X86_64_DIV64
-
-/*
- * Hey, we're already 64-bit, no
- * need to play games..
- */
-#define do_div(n,base) ({ \
-	int __res; \
-	__res = ((unsigned long) (n)) % (unsigned) (base); \
-	(n) = ((unsigned long) (n)) / (unsigned) (base); \
-	__res; })
-
-#endif
+#include <asm-generic/div64.h>
diff -Nru linux-2.5.74.orig/lib/Makefile linux-2.5.74/lib/Makefile
--- linux-2.5.74.orig/lib/Makefile	2003-07-02 22:40:29.000000000 +0200
+++ linux-2.5.74/lib/Makefile	2003-07-03 09:37:22.000000000 +0200
@@ -5,7 +5,7 @@
 
 lib-y := errno.o ctype.o string.o vsprintf.o cmdline.o \
 	 bust_spinlocks.o rbtree.o radix-tree.o dump_stack.o \
-	 kobject.o idr.o
+	 kobject.o idr.o div64.o
 
 lib-$(CONFIG_RWSEM_GENERIC_SPINLOCK) += rwsem-spinlock.o
 lib-$(CONFIG_RWSEM_XCHGADD_ALGORITHM) += rwsem.o

-- 
  // Bernardo Innocenti - Develer S.r.l., R&D dept.
\X/  http://www.develer.com/

Please don't send Word attachments - http://www.gnu.org/philosophy/no-word-attachments.html

Re: [PATCH] Fix do_div() for all architectures

[Bernardo Innocenti]

On Sunday 06 July 2003 01:33, Bernardo Innocenti wrote:

 >  - add __attribute__((pure)) to __div64_32() prototype so
 >    the compiler knows global memory isn't clobbered;

 Hmmm... I've just found out that the pure attribute wasn't
supported until gcc 2.96. Shall I get rid of it or maybe add
something in linux/compiler.h?

 Please note that __attribute__((const)) is not applicable
to this case according to gcc documentation.

-- 
  // Bernardo Innocenti - Develer S.r.l., R&D dept.
\X/  http://www.develer.com/

Please don't send Word attachments - http://www.gnu.org/philosophy/no-word-attachments.html

Re: [PATCH] Fix do_div() for all architectures

[Ian Molton]

On Sun, 6 Jul 2003 08:47:50 +0100
Russell King <rmk@arm.linux.org.uk> wrote:

> 
> > second iteration of the div64.h cleanup + bug fixing.
> > Contains the following changes since the previous release:
> 
> arm26 is Ian Molton.  Please copy Ian on ARM26 matters, not myself.
> Thanks.

FWIW, theres a patch to MAINTAINERS on its way to linus since a week ago
:-)

John Appleby might like to be copied on ARM26 things also.

-- 
Spyros lair: http://www.mnementh.co.uk/   ||||   Maintainer: arm26 linux

Do not meddle in the affairs of Dragons, for you are tasty and good with
ketchup.

Re: [PATCH] Fix do_div() for all architectures

[Russell King]

On Sun, Jul 06, 2003 at 01:33:15AM +0200, Bernardo Innocenti wrote:
> Hello everybody,
> 
> second iteration of the div64.h cleanup + bug fixing.
> Contains the following changes since the previous release:

arm26 is Ian Molton.  Please copy Ian on ARM26 matters, not myself.
Thanks.

-- 
Russell King (rmk@arm.linux.org.uk)                The developer of ARM Linux
             http://www.arm.linux.org.uk/personal/aboutme.html

[PATCH] Fix do_div() for all architectures

[Bernardo Innocenti]

Hello everybody,

second iteration of the div64.h cleanup + bug fixing.
Contains the following changes since the previous release:

 - add likely() to the fast path (divisor>>32 == 0);

 - add __attribute__((pure)) to __div64_32() prototype so
   the compiler knows global memory isn't clobbered;

 - export the __div64_32 symbol for modules;

The generic do_div() code is now tested on m68knommu, arm
and even i386 (by manually replacing real asm-i386/div64.h
with the generic version).

Applies to 2.5.74 and 2.5.74-bk2. I'll provide a 2.4
backport once it has been tested in 2.5.

  // Bernardo Innocenti - Develer S.r.l., R&D dept.
\X/  http://www.develer.com/

-----------------------------------------------------------------

 - add generic C implementations of the do_div() for 32bit and 64bit
   archs in asm-generic/div64.h;

 - add generic library support function __div64_32() to handle the
   full 64/32 case on 32bit archs;

 - kill multiple copies of generic do_div() in architecture
   specific subdirs. Most copies were either buggy or not doing
   what they were supposed to do;

 - ensure all surviving instances of do_div() have their parameters
   correctly parenthesized to avoid funny side-effects;

 include/asm-generic/div64.h   |   53 ++++++++++++++++++++++++++++++++++++++++
 lib/div64.c                   |   47 ++++++++++++++++++++++++++++++++++
 include/asm-alpha/div64.h     |   15 -----------
 include/asm-arm26/div64.h     |   15 -----------
 include/asm-cris/div64.h      |   17 ------------
 include/asm-h8300/div64.h     |   14 ----------
 include/asm-ia64/div64.h      |   21 ----------------
 include/asm-m68k/div64.h      |    9 ------
 include/asm-m68knommu/div64.h |   14 ----------
 include/asm-mips64/div64.h    |   19 --------------
 include/asm-parisc/div64.h    |   55 ------------------------------------------
 include/asm-ppc/div64.h       |   24 ------------------
 include/asm-ppc64/div64.h     |   19 --------------
 include/asm-s390/div64.h      |    8 ------
 include/asm-sh/div64.h        |   21 ----------------
 include/asm-sparc/div64.h     |   12 ---------
 include/asm-sparc64/div64.h   |   15 -----------
 include/asm-v850/div64.h      |   12 ---------
 include/asm-x86_64/div64.h    |   15 -----------
 lib/Makefile                  |    2 -
 20 files changed, 115 insertions(+), 290 deletions(-)

diff -Nru linux-2.5.74-uc0/include/asm-generic/div64.h linux-2.5.74-uc0-develer/include/asm-generic/div64.h
--- linux-2.5.74-uc0/include/asm-generic/div64.h	1970-01-01 01:00:00.000000000 +0100
+++ linux-2.5.74-uc0-develer/include/asm-generic/div64.h	2003-07-03 09:55:04.000000000 +0200
@@ -0,0 +1,53 @@
+#ifndef _ASM_GENERIC_DIV64_H
+#define _ASM_GENERIC_DIV64_H
+/*
+ * Copyright (C) 2003 Bernardo Innocenti <bernie@develer.com>
+ * Based on former asm-ppc/div64.h and asm-m68knommu/div64.h
+ *
+ * The semantics of do_div() are:
+ *
+ * uint32_t do_div(uint64_t *n, uint32_t base)
+ * {
+ * 	uint32_t remainder = *n % base;
+ * 	*n = *n / base;
+ * 	return remainder;
+ * }
+ *
+ * NOTE: macro parameter n is evaluated multiple times,
+ *       beware of side effects!
+ */
+
+#include <linux/types.h>
+
+#if BITS_PER_LONG == 64
+
+# define do_div(n,base) ({					\
+	uint32_t __base = (base);				\
+	uint32_t __rem;						\
+	__rem = ((uint64_t)(n)) % __base;			\
+	(n) = ((uint64_t)(n)) / __base;				\
+	__rem;							\
+ })
+
+#elif BITS_PER_LONG == 32
+
+extern uint32_t __div64_32(uint64_t *dividend, uint32_t divisor) __attribute__((pure));
+
+# define do_div(n,base) ({				\
+	uint32_t __base = (base);			\
+	uint32_t __rem;					\
+	if (likely(((n) >> 32) == 0)) {			\
+		__rem = (uint32_t)(n) % __base;		\
+		(n) = (uint32_t)(n) / __base;		\
+	} else 						\
+		__rem = __div64_32(&(n), __base);	\
+	__rem;						\
+ })
+
+#else /* BITS_PER_LONG == ?? */
+
+# error do_div() does not yet support the C64
+
+#endif /* BITS_PER_LONG */
+
+#endif /* _ASM_GENERIC_DIV64_H */
diff -Nru linux-2.5.74-uc0/lib/div64.c linux-2.5.74-uc0-develer/lib/div64.c
--- linux-2.5.74-uc0/lib/div64.c	1970-01-01 01:00:00.000000000 +0100
+++ linux-2.5.74-uc0-develer/lib/div64.c	2003-07-03 09:37:22.000000000 +0200
@@ -0,0 +1,47 @@
+/*
+ * Copyright (C) 2003 Bernardo Innocenti <bernie@develer.com>
+ *
+ * Based on former do_div() implementation from asm-parisc/div64.h:
+ *	Copyright (C) 1999 Hewlett-Packard Co
+ *	Copyright (C) 1999 David Mosberger-Tang <davidm@hpl.hp.com>
+ *
+ *
+ * Generic C version of 64bit/32bit division and modulo, with
+ * 64bit result and 32bit remainder.
+ *
+ * The fast case for (n>>32 == 0) is handled inline by do_div(). 
+ *
+ * Code generated for this function might be very inefficient
+ * for some CPUs. __div64_32() can be overridden by linking arch-specific
+ * 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>
+
+uint32_t __div64_32(uint64_t *n, uint32_t base)
+{
+	uint32_t low, low2, high, rem;
+
+	low   = *n   & 0xffffffff;
+	high  = *n  >> 32;
+	rem   = high % (uint32_t)base;
+	high  = high / (uint32_t)base;
+	low2  = low >> 16;
+	low2 += rem << 16;
+	rem   = low2 % (uint32_t)base;
+	low2  = low2 / (uint32_t)base;
+	low   = low  & 0xffff;
+	low  += rem << 16;
+	rem   = low  % (uint32_t)base;
+	low   = low  / (uint32_t)base;
+
+	*n = low +
+		((uint64_t)low2 << 16) +
+		((uint64_t)high << 32);
+
+	return rem;
+}
+
+EXPORT_SYMBOL(__div64_32);
diff -Nru linux-2.5.74-uc0/include/asm-alpha/div64.h linux-2.5.74-uc0-develer/include/asm-alpha/div64.h
--- linux-2.5.74-uc0/include/asm-alpha/div64.h	2003-07-02 22:54:43.000000000 +0200
+++ linux-2.5.74-uc0-develer/include/asm-alpha/div64.h	2003-07-03 09:37:22.000000000 +0200
@@ -1,14 +1 @@
-#ifndef __ALPHA_DIV64
-#define __ALPHA_DIV64
-
-/*
- * Hey, we're already 64-bit, no
- * need to play games..
- */
-#define do_div(n,base) ({ \
-	int __res; \
-	__res = ((unsigned long) (n)) % (unsigned) (base); \
-	(n) = ((unsigned long) (n)) / (unsigned) (base); \
-	__res; })
-
-#endif
+#include <asm-generic/div64.h>
diff -Nru linux-2.5.74-uc0/include/asm-arm26/div64.h linux-2.5.74-uc0-develer/include/asm-arm26/div64.h
--- linux-2.5.74-uc0/include/asm-arm26/div64.h	2003-07-02 22:42:11.000000000 +0200
+++ linux-2.5.74-uc0-develer/include/asm-arm26/div64.h	2003-07-03 09:37:22.000000000 +0200
@@ -1,14 +1 @@
-#ifndef __ASM_ARM_DIV64
-#define __ASM_ARM_DIV64
-
-/* We're not 64-bit, but... */
-#define do_div(n,base)						\
-({								\
-	int __res;						\
-	__res = ((unsigned long)n) % (unsigned int)base;	\
-	n = ((unsigned long)n) / (unsigned int)base;		\
-	__res;							\
-})
-
-#endif
-
+#include <asm-generic/div64.h>
diff -Nru linux-2.5.74-uc0/include/asm-cris/div64.h linux-2.5.74-uc0-develer/include/asm-cris/div64.h
--- linux-2.5.74-uc0/include/asm-cris/div64.h	2003-07-02 22:42:06.000000000 +0200
+++ linux-2.5.74-uc0-develer/include/asm-cris/div64.h	2003-07-03 09:37:22.000000000 +0200
@@ -1,16 +1 @@
-#ifndef __ASM_CRIS_DIV64
-#define __ASM_CRIS_DIV64
-
-/* copy from asm-arm */
-
-/* We're not 64-bit, but... */
-#define do_div(n,base)						\
-({								\
-	int __res;						\
-	__res = ((unsigned long)n) % (unsigned int)base;	\
-	n = ((unsigned long)n) / (unsigned int)base;		\
-	__res;							\
-})
-
-#endif
-
+#include <asm-generic/div64.h>
diff -Nru linux-2.5.74-uc0/include/asm-h8300/div64.h linux-2.5.74-uc0-develer/include/asm-h8300/div64.h
--- linux-2.5.74-uc0/include/asm-h8300/div64.h	2003-07-02 22:39:25.000000000 +0200
+++ linux-2.5.74-uc0-develer/include/asm-h8300/div64.h	2003-07-03 09:37:22.000000000 +0200
@@ -1,13 +1 @@
-#ifndef H8300_DIV64_H
-#define H8300_DIV64_H
-
-/* n = n / base; return rem; */
-
-#define do_div(n,base) ({					\
-	int __res;						\
-	__res = ((unsigned long) n) % (unsigned) base;		\
-	n = ((unsigned long) n) / (unsigned) base;		\
-	__res;							\
-})
-
-#endif /* _H8300_DIV64_H */
+#include <asm-generic/div64.h>
diff -Nru linux-2.5.74-uc0/include/asm-ia64/div64.h linux-2.5.74-uc0-develer/include/asm-ia64/div64.h
--- linux-2.5.74-uc0/include/asm-ia64/div64.h	2003-07-02 22:58:14.000000000 +0200
+++ linux-2.5.74-uc0-develer/include/asm-ia64/div64.h	2003-07-03 09:37:22.000000000 +0200
@@ -1,20 +1 @@
-#ifndef _ASM_IA64_DIV64_H
-#define _ASM_IA64_DIV64_H
-
-/*
- * Copyright (C) 1999 Hewlett-Packard Co
- * Copyright (C) 1999 David Mosberger-Tang <davidm@hpl.hp.com>
- *
- * vsprintf uses this to divide a 64-bit integer N by a small integer BASE.
- * This is incredibly hard on IA-64...
- */
-
-#define do_div(n,base)						\
-({								\
-	int _res;						\
-	_res = ((unsigned long) (n)) % (unsigned) (base);	\
-	(n) = ((unsigned long) (n)) / (unsigned) (base);	\
-	_res;							\
-})
-
-#endif /* _ASM_IA64_DIV64_H */
+#include <asm-generic/div64.h>
diff -Nru linux-2.5.74-uc0/include/asm-m68k/div64.h linux-2.5.74-uc0-develer/include/asm-m68k/div64.h
--- linux-2.5.74-uc0/include/asm-m68k/div64.h	2003-07-02 22:55:53.000000000 +0200
+++ linux-2.5.74-uc0-develer/include/asm-m68k/div64.h	2003-07-03 09:37:22.000000000 +0200
@@ -3,7 +3,6 @@
 
 /* n = n / base; return rem; */
 
-#if 1
 #define do_div(n, base) ({					\
 	union {							\
 		unsigned long n32[2];				\
@@ -23,13 +22,5 @@
 	(n) = __n.n64;						\
 	__rem;							\
 })
-#else
-#define do_div(n,base) ({					\
-	int __res;						\
-	__res = ((unsigned long) n) % (unsigned) base;		\
-	n = ((unsigned long) n) / (unsigned) base;		\
-	__res;							\
-})
-#endif
 
 #endif /* _M68K_DIV64_H */
diff -Nru linux-2.5.74-uc0/include/asm-m68knommu/div64.h linux-2.5.74-uc0-develer/include/asm-m68knommu/div64.h
--- linux-2.5.74-uc0/include/asm-m68knommu/div64.h	2003-07-03 10:40:35.000000000 +0200
+++ linux-2.5.74-uc0-develer/include/asm-m68knommu/div64.h	2003-07-03 09:37:22.000000000 +0200
@@ -1,13 +1 @@
-#ifndef _M68KNOMMU_DIV64_H
-#define _M68KNOMMU_DIV64_H
-
-/* n = n / base; return rem; */
-
-#define do_div(n,base) ({					\
-	int __res;						\
-	__res = ((unsigned long) n) % (unsigned) base;		\
-	n = ((unsigned long) n) / (unsigned) base;		\
-	__res;							\
-})
-
-#endif /* _M68K_DIV64_H */
+#include <asm-generic/div64.h>
diff -Nru linux-2.5.74-uc0/include/asm-mips64/div64.h linux-2.5.74-uc0-develer/include/asm-mips64/div64.h
--- linux-2.5.74-uc0/include/asm-mips64/div64.h	2003-07-02 22:47:26.000000000 +0200
+++ linux-2.5.74-uc0-develer/include/asm-mips64/div64.h	2003-07-03 09:39:28.000000000 +0200
@@ -27,23 +27,6 @@
 	(res) = __quot; \
 	__mod; })
 
-/*
- * Hey, we're already 64-bit, no
- * need to play games..
- */
-#define do_div(n, base) ({ \
-	unsigned long __quot; \
-	unsigned int __mod; \
-	unsigned long __div; \
-	unsigned int __base; \
-	\
-	__div = (n); \
-	__base = (base); \
-	\
-	__mod = __div % __base; \
-	__quot = __div / __base; \
-	\
-	(n) = __quot; \
-	__mod; })
+#include <asm-generic.h>
 
 #endif /* _ASM_DIV64_H */
diff -Nru linux-2.5.74-uc0/include/asm-parisc/div64.h linux-2.5.74-uc0-develer/include/asm-parisc/div64.h
--- linux-2.5.74-uc0/include/asm-parisc/div64.h	2003-07-02 22:48:40.000000000 +0200
+++ linux-2.5.74-uc0-develer/include/asm-parisc/div64.h	2003-07-03 09:37:22.000000000 +0200
@@ -1,54 +1 @@
-#ifndef __ASM_PARISC_DIV64
-#define __ASM_PARISC_DIV64
-
-#ifdef __LP64__
-
-/*
- * Copyright (C) 1999 Hewlett-Packard Co
- * Copyright (C) 1999 David Mosberger-Tang <davidm@hpl.hp.com>
- *
- * vsprintf uses this to divide a 64-bit integer N by a small integer BASE.
- * This is incredibly hard on IA-64 and HPPA
- */
-
-#define do_div(n,base)						\
-({								\
-	int _res;						\
-	_res = ((unsigned long) (n)) % (unsigned) (base);	\
-	(n) = ((unsigned long) (n)) / (unsigned) (base);	\
-	_res;							\
-})
-
-#else
-/*
- * unsigned long long division.  Yuck Yuck!  What is Linux coming to?
- * This is 100% disgusting
- */
-#define do_div(n,base)							\
-({									\
-	unsigned long __low, __low2, __high, __rem;			\
-	__low  = (n) & 0xffffffff;					\
-	__high = (n) >> 32;						\
-	if (__high) {							\
-		__rem   = __high % (unsigned long)base;			\
-		__high  = __high / (unsigned long)base;			\
-		__low2  = __low >> 16;					\
-		__low2 += __rem << 16;					\
-		__rem   = __low2 % (unsigned long)base;			\
-		__low2  = __low2 / (unsigned long)base;			\
-		__low   = __low & 0xffff;				\
-		__low  += __rem << 16;					\
-		__rem   = __low  % (unsigned long)base;			\
-		__low   = __low  / (unsigned long)base;			\
-		n = __low  + ((long long)__low2 << 16) +		\
-			((long long) __high << 32);			\
-	} else {							\
-		__rem = __low % (unsigned long)base;			\
-		n = (__low / (unsigned long)base);			\
-	}								\
-	__rem;								\
-})
-#endif
-
-#endif
-
+#include <asm-generic/div64.h>
diff -Nru linux-2.5.74-uc0/include/asm-ppc/div64.h linux-2.5.74-uc0-develer/include/asm-ppc/div64.h
--- linux-2.5.74-uc0/include/asm-ppc/div64.h	2003-07-02 22:57:06.000000000 +0200
+++ linux-2.5.74-uc0-develer/include/asm-ppc/div64.h	2003-07-03 09:37:22.000000000 +0200
@@ -1,23 +1 @@
-#ifndef __PPC_DIV64
-#define __PPC_DIV64
-
-#include <linux/types.h>
-
-extern u32 __div64_32(u64 *dividend, u32 div);
-
-#define do_div(n, div)	({			\
-	u64 __n = (n);				\
-	u32 __d = (div);			\
-	u32 __q, __r;				\
-	if ((__n >> 32) == 0) {			\
-		__q = (u32)__n / __d;		\
-		__r = (u32)__n - __q * __d;	\
-		(n) = __q;			\
-	} else {				\
-		__r = __div64_32(&__n, __d);	\
-		(n) = __n;			\
-	}					\
-	__r;					\
-})
-
-#endif
+#include <asm-generic/div64.h>
diff -Nru linux-2.5.74-uc0/include/asm-ppc64/div64.h linux-2.5.74-uc0-develer/include/asm-ppc64/div64.h
--- linux-2.5.74-uc0/include/asm-ppc64/div64.h	2003-07-02 22:39:34.000000000 +0200
+++ linux-2.5.74-uc0-develer/include/asm-ppc64/div64.h	2003-07-03 09:37:22.000000000 +0200
@@ -1,18 +1 @@
-#ifndef __PPC_DIV64
-#define __PPC_DIV64
-
-/* Copyright 2001 PPC64 Team, IBM Corp
- *
- * This program is free software; you can redistribute it and/or
- * modify it under the terms of the GNU General Public License
- * as published by the Free Software Foundation; either version
- * 2 of the License, or (at your option) any later version.
- */
-
-#define do_div(n,base) ({ \
-	int __res; \
-	__res = ((unsigned long) (n)) % (unsigned) (base); \
-	(n) = ((unsigned long) (n)) / (unsigned) (base); \
-	__res; })
-
-#endif
+#include <asm-generic/div64.h>
diff -Nru linux-2.5.74-uc0/include/asm-s390/div64.h linux-2.5.74-uc0-develer/include/asm-s390/div64.h
--- linux-2.5.74-uc0/include/asm-s390/div64.h	2003-07-02 22:50:17.000000000 +0200
+++ linux-2.5.74-uc0-develer/include/asm-s390/div64.h	2003-07-03 09:37:22.000000000 +0200
@@ -43,13 +43,7 @@
 })
 
 #else /* __s390x__ */
-
-#define do_div(n,base) ({ \
-int __res; \
-__res = ((unsigned long) n) % (unsigned) base; \
-n = ((unsigned long) n) / (unsigned) base; \
-__res; })
-
+#include <asm-generic/div64.h>
 #endif /* __s390x__ */
 
 #endif
diff -Nru linux-2.5.74-uc0/include/asm-sh/div64.h linux-2.5.74-uc0-develer/include/asm-sh/div64.h
--- linux-2.5.74-uc0/include/asm-sh/div64.h	2003-07-02 22:39:36.000000000 +0200
+++ linux-2.5.74-uc0-develer/include/asm-sh/div64.h	2003-07-03 09:38:59.000000000 +0200
@@ -1,20 +1 @@
-#ifndef __ASM_SH_DIV64
-#define __ASM_SH_DIV64
-
-extern u64 __div64_32(u64 n, u32 d);
-
-#define do_div(n,base) ({ \
-u64 __n = (n), __q; \
-u32 __base = (base); \
-u32 __res; \
-if ((__n >> 32) == 0) { \
-	__res = ((unsigned long) __n) % (unsigned) __base; \
-	(n) = ((unsigned long) __n) / (unsigned) __base; \
-} else { \
-	__q = __div64_32(__n, __base); \
-	__res = __n - __q * __base; \
-	(n) = __q; \
-} \
-__res; })
-
-#endif /* __ASM_SH_DIV64 */
+#include <asm-generic/div64.h>
diff -Nru linux-2.5.74-uc0/include/asm-sparc/div64.h linux-2.5.74-uc0-develer/include/asm-sparc/div64.h
--- linux-2.5.74-uc0/include/asm-sparc/div64.h	2003-07-02 22:51:01.000000000 +0200
+++ linux-2.5.74-uc0-develer/include/asm-sparc/div64.h	2003-07-03 09:37:22.000000000 +0200
@@ -1,11 +1 @@
-#ifndef __SPARC_DIV64
-#define __SPARC_DIV64
-
-/* We're not 64-bit, but... */
-#define do_div(n,base) ({ \
-	int __res; \
-	__res = ((unsigned long) n) % (unsigned) base; \
-	n = ((unsigned long) n) / (unsigned) base; \
-	__res; })
-
-#endif /* __SPARC_DIV64 */
+#include <asm-generic/div64.h>
diff -Nru linux-2.5.74-uc0/include/asm-sparc64/div64.h linux-2.5.74-uc0-develer/include/asm-sparc64/div64.h
--- linux-2.5.74-uc0/include/asm-sparc64/div64.h	2003-07-02 22:46:06.000000000 +0200
+++ linux-2.5.74-uc0-develer/include/asm-sparc64/div64.h	2003-07-03 09:37:22.000000000 +0200
@@ -1,14 +1 @@
-#ifndef __SPARC64_DIV64
-#define __SPARC64_DIV64
-
-/*
- * Hey, we're already 64-bit, no
- * need to play games..
- */
-#define do_div(n,base) ({ \
-	int __res; \
-	__res = ((unsigned long) n) % (unsigned) base; \
-	n = ((unsigned long) n) / (unsigned) base; \
-	__res; })
-
-#endif /* __SPARC64_DIV64 */
+#include <asm-generic/div64.h>
diff -Nru linux-2.5.74-uc0/include/asm-v850/div64.h linux-2.5.74-uc0-develer/include/asm-v850/div64.h
--- linux-2.5.74-uc0/include/asm-v850/div64.h	2003-07-02 22:53:46.000000000 +0200
+++ linux-2.5.74-uc0-develer/include/asm-v850/div64.h	2003-07-03 09:37:22.000000000 +0200
@@ -1,11 +1 @@
-#ifndef __V850_DIV64_H__
-#define __V850_DIV64_H__
-
-/* We're not 64-bit, but... */
-#define do_div(n,base) ({ \
-	int __res; \
-	__res = ((unsigned long) n) % (unsigned) base; \
-	n = ((unsigned long) n) / (unsigned) base; \
-	__res; })
-
-#endif /* __V850_DIV64_H__ */
+#include <asm-generic/div64.h>
diff -Nru linux-2.5.74-uc0/include/asm-x86_64/div64.h linux-2.5.74-uc0-develer/include/asm-x86_64/div64.h
--- linux-2.5.74-uc0/include/asm-x86_64/div64.h	2003-07-02 22:54:30.000000000 +0200
+++ linux-2.5.74-uc0-develer/include/asm-x86_64/div64.h	2003-07-03 09:37:22.000000000 +0200
@@ -1,14 +1 @@
-#ifndef __X86_64_DIV64
-#define __X86_64_DIV64
-
-/*
- * Hey, we're already 64-bit, no
- * need to play games..
- */
-#define do_div(n,base) ({ \
-	int __res; \
-	__res = ((unsigned long) (n)) % (unsigned) (base); \
-	(n) = ((unsigned long) (n)) / (unsigned) (base); \
-	__res; })
-
-#endif
+#include <asm-generic/div64.h>
diff -Nru linux-2.5.74-uc0/lib/Makefile linux-2.5.74-uc0-develer/lib/Makefile
--- linux-2.5.74-uc0/lib/Makefile	2003-07-02 22:40:29.000000000 +0200
+++ linux-2.5.74-uc0-develer/lib/Makefile	2003-07-03 09:37:22.000000000 +0200
@@ -5,7 +5,7 @@
 
 lib-y := errno.o ctype.o string.o vsprintf.o cmdline.o \
 	 bust_spinlocks.o rbtree.o radix-tree.o dump_stack.o \
-	 kobject.o idr.o
+	 kobject.o idr.o div64.o
 
 lib-$(CONFIG_RWSEM_GENERIC_SPINLOCK) += rwsem-spinlock.o
 lib-$(CONFIG_RWSEM_XCHGADD_ALGORITHM) += rwsem.o