Kill div64.h dupes, parenthesize do_div() macro params
Subsystems (2)
PATCH 1/1 Kill div64.h dupes, parenthesize do_div() macro params
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 <[email protected]>
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(-)
include/asm-generic/div64.h +13 -0
@@ -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 */
include/asm-alpha/div64.h +1 -14
@@ -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>
include/asm-arm26/div64.h +1 -14
@@ -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>
include/asm-cris/div64.h +1 -16
@@ -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>
include/asm-h8300/div64.h +1 -13
@@ -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>
include/asm-ia64/div64.h +1 -20
@@ -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 <[email protected]> -* -* 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>
include/asm-m68k/div64.h +0 -9
@@ -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 */
include/asm-m68knommu/div64.h +1 -13
@@ -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>
include/asm-mips64/div64.h +1 -19
@@ -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>
include/asm-parisc/div64.h +10 -26
@@ -2,23 +2,7 @@#define __ASM_PARISC_DIV64#ifdef __LP64__ - -/* -* Copyright (C) 1999 Hewlett-Packard Co -* Copyright (C) 1999 David Mosberger-Tang <[email protected]> -* -* 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; \ })
include/asm-ppc64/div64.h +1 -18
@@ -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>
include/asm-s390/div64.h +1 -7
@@ -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
include/asm-sh/div64.h +1 -10
@@ -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>
include/asm-sparc/div64.h +1 -11
@@ -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>
include/asm-sparc64/div64.h +1 -14
@@ -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>
include/asm-v850/div64.h +1 -11
@@ -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>
include/asm-x86_64/div64.h +1 -14
@@ -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>
Signature · 4 lines
// 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
A message that is not in the archive (sent off-list or not yet received): [email protected]
Quoted 6 lines · Andrew Morton
Quoted 3 lines
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.
Signature · 4 lines
// 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
Quoted 3 lines · Bernardo Innocenti
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 ;)
Quoted 4 lines · you
Quoted 2 lines
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.
Quoted 5 lines
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 explicitdo_divwe 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.
Quoted 2 lines
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 ;-)
Signature · 4 lines
// 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
Quoted 3 lines · Bernardo Innocenti
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..")
Quoted 1 line
What's worse, it has different semantics on different archictecures:
only because some architectures on purpose get it wrong, because they don't care.
Quoted 1 line
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
Quoted 1 line · Bernardo Innocenti
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.
Quoted 2 lines
arm 64/32 -> 64q + 32r (asm function call)
arm26 32/32 -> 32q + 32r (generic)
arm26 needs fixing in the same way arm recently was.
Signature · 2 lines
Russell King ([email protected]) The developer of ARM Linux http://www.arm.linux.org.uk/personal/aboutme.html
Quoted 11 lines · On Wed, 2 Jul 2003 08:53:02 +0100 Russell King <[email protected]> wrote:
Quoted 1 line · Bernardo Innocenti
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_divmust now be a 64/32 -> 64q + 32r implementation.Quoted 2 lines
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?
Signature · 4 lines
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.
Quoted 3 lines · Andrew Morton
By requiring an explicit
do_divwe 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.
Quoted 2 lines
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
Quoted 5 lines · Linus Torvalds
Quoted 2 lines
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().
Signature · 4 lines
// 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
Quoted 7 lines · Bernardo Innocenti
Quoted 5 lines · Linus Torvalds
Quoted 2 lines
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.
Quoted 6 lines
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 ofdo_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.
Quoted 3 lines
Signature · 2 lines
// Bernardo Innocenti - Develer S.r.l., R&D dept. \X/ http://www.develer.com/
/Matti Aarnio
Quoted 1 line
Quoted 1 line
Quoted 1 line
Quoted 1 line
Quoted 1 line
"Bernardo" == Bernardo Innocenti <[email protected]> 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.
Quoted 8 lines · Peter Chubb
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
_udivdi3which 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.
Quoted 3 lines
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...
Quoted 3 lines
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.
Signature · 4 lines
// 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
Quoted 2 lines · Peter Chubb
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
Quoted 3 lines · Andrea Arcangeli
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.
Quoted 4 lines
Bernardo, you should definitely add an #if
BITS_PER_LONG== 64 around your implementation ofdo_divin 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!
div64.h new file +66 -0
@@ -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 */
Signature · 4 lines
// 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
Quoted 1 line · Bernardo Innocenti
+ * static inline
uint32_tdo_div(uint64_t &n, uint32_t base)
c++ ;)
Quoted 1 line
+# 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
Quoted 4 lines · you
Quoted 1 line · Bernardo Innocenti
+ * static inline
uint32_tdo_div(uint64_t &n, uint32_t base)c++ ;)
Oops! Shall I send a new patch? ;-)
Quoted 6 lines
Quoted 1 line
+# 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! */
Signature · 4 lines
// 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
Quoted 7 lines · Bernardo Innocenti
Quoted 4 lines · you
Quoted 1 line · Bernardo Innocenti
+ * static inline
uint32_tdo_div(uint64_t &n, uint32_t base)c++ ;)
Oops! Shall I send a new patch? ;-)
I guess no ;).
Quoted 5 lines
Quoted 5 lines
Quoted 2 lines
+# error
do_div()does not yet support the C64;)
Quoted 8 lines
Quoted 2 lines
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 manydo_div()variants. Guess what happened whenshrink_slab()did this (pages = 0):do_div(delta, pages + 1); /* Ouch! */
I see.
Andrea
Quoted 16 lines · Bernardo Innocenti
div64.h new file +16
-0+#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; \
div64.h line 60
Quoted 10 lines
div64.h new file +10
-0+ __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 1/1 Fix do_div() for all architectures
Quoted 9 lines · Linus Torvalds
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.aor 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(-)
include/asm-alpha/div64.h +1 -14
@@ -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>
include/asm-arm26/div64.h +1 -14
@@ -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>
include/asm-cris/div64.h +1 -16
@@ -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>
include/asm-generic/div64.h +53 -0
53 lines not on this page · raw message
include/asm-h8300/div64.h +1 -13
@@ -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>
include/asm-ia64/div64.h +1 -20
@@ -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 <[email protected]> -* -* 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>
include/asm-m68k/div64.h +0 -9
@@ -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 */
include/asm-m68knommu/div64.h +1 -13
@@ -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>
include/asm-mips64/div64.h +1 -18
@@ -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 */
include/asm-parisc/div64.h +1 -54
55 lines not on this page · raw message
include/asm-ppc/div64.h +1 -23
@@ -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>
include/asm-ppc64/div64.h +1 -18
@@ -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>
include/asm-s390/div64.h +1 -7
@@ -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
include/asm-sh/div64.h +1 -20
@@ -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>
include/asm-sparc/div64.h +1 -11
@@ -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>
include/asm-sparc64/div64.h +1 -14
@@ -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>
include/asm-v850/div64.h +1 -11
@@ -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>
include/asm-x86_64/div64.h +1 -14
@@ -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>
lib/Makefile +1 -1
@@ -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
lib/div64.c +45 -0
45 lines not on this page · raw message
Quoted 1 line · Andrea Arcangeli
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.
Signature · 2 lines
Russell King ([email protected]) The developer of ARM Linux http://www.arm.linux.org.uk/personal/aboutme.html
Quoted 5 lines · Bernardo Innocenti
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 genericdo_div()written in C:
No thank you. 3.x is still broken enough that I don't want to force people to use it.
Quoted 2 lines
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
Quoted 5 lines · Linus Torvalds
Quoted 2 lines · Bernardo Innocenti
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 -- [email protected]
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