lkml.org 
[lkml]   [2010]   [Aug]   [9]   [last100]   RSS Feed
Views: [wrap][no wrap]   [headers]  [forward] 
 
Messages in this thread
    Patch in this message
    /
    From
    Subject[PATCH] Make div64_u64() precise on 32bit platforms
    Date
    --nextPart3079728.g0KSIjXtV0
    Content-Type: text/plain;
    charset="iso-8859-1"
    Content-Transfer-Encoding: quoted-printable
    Content-Disposition: inline


    > On Mon, 2 Aug 2010 18:09:51 +0200
    >
    > Oleg Nesterov <oleg@redhat.com> wrote:
    > > We have a bugreport which blames div64_u64() on 32bit platforms.
    > >
    > > However, the code obviously doesn't even try to pretend it can do
    > > the 64bit division precisely. If there is something in the high
    > > word of divisor, div64_u64() just shifts both arguments and throws
    > > out the low bits.
    >
    > Well that was a bit lazy of us - I wonder how hard it is to fix.
    >
    > At present people will test their code on 64-bit only to find out later
    > that it doesn't work correctly on 32-bit. Bad. Perhaps we should
    > similarly break the 64-bit version :)

    Here's an even crazier idea, let's just fix the 32-bit version. :)

    The attached patch fully implements div64_u64() such that it will return=20
    precisely the right quotient even when the divisor exceeds 32-bits. The=20
    patch also adds a div64_s64() function to fully support signed 64-bit=20
    division.

    Because this fix is non-obvious I have also included a unsigned and signed=
    =20
    regression test to verify the correctness of the patch. Using a vanilla=20
    2.6.35 kernel the unsigned regression tests fails on 32-bit platforms. Wit=
    h=20
    the proposed patch applied both the unsigned and signed tests pass.

    =2D-=20
    Thanks,
    Brian

    --nextPart3079728.g0KSIjXtV0
    Content-Type: application/pgp-signature

    -----BEGIN PGP SIGNATURE-----
    Version: GnuPG v1.4.5 (GNU/Linux)

    iD8DBQBMYC1ACrnpkcavZYsRAlxqAJ9mgyCP/C7zAKNckUMkJ8JFLvmlswCfSGk5
    4LikuHrRL7An6rkrF3EgBBM=
    =j+nk
    -----END PGP SIGNATURE-----

    --nextPart3079728.g0KSIjXtV0--
    From 3b30f1cf78f88b40360dd65816941cf2be9dd60d Mon Sep 17 00:00:00 2001
    From: Brian Behlendorf <behlendorf1@llnl.gov>
    Date: Thu, 5 Aug 2010 14:59:11 -0700
    Subject: [PATCH] Fix div64_u64 for 32bit platforms

    The current implementation of div64_u64 for 32bit systems returns
    an approximately correct result when the divisor exceeds 32bits.
    Since doing 64bit division using 32bit hardware is a long since
    solved problem we just use one of the existing proven methods.

    Additionally, add a div64_s64 function to correctly handle doing
    signed 64bit division.

    ---
    include/linux/kernel.h | 5 +++
    include/linux/math64.h | 12 +++++++++
    lib/div64.c | 64 +++++++++++++++++++++++++++++++++++++++--------
    3 files changed, 70 insertions(+), 11 deletions(-)

    diff --git a/include/linux/kernel.h b/include/linux/kernel.h
    index 5de838b..7a00dff 100644
    --- a/include/linux/kernel.h
    +++ b/include/linux/kernel.h
    @@ -162,6 +162,11 @@ extern int _cond_resched(void);
    (__x < 0) ? -__x : __x; \
    })

    +#define abs64(x) ({ \
    + s64 __x = (x); \
    + (__x < 0) ? -__x : __x; \
    + })
    +
    #ifdef CONFIG_PROVE_LOCKING
    void might_fault(void);
    #else
    diff --git a/include/linux/math64.h b/include/linux/math64.h
    index c87f152..23fcdfc 100644
    --- a/include/linux/math64.h
    +++ b/include/linux/math64.h
    @@ -35,6 +35,14 @@ static inline u64 div64_u64(u64 dividend, u64 divisor)
    return dividend / divisor;
    }

    +/**
    + * div64_s64 - signed 64bit divide with 64bit divisor
    + */
    +static inline s64 div64_s64(s64 dividend, s64 divisor)
    +{
    + return dividend / divisor;
    +}
    +
    #elif BITS_PER_LONG == 32

    #ifndef div_u64_rem
    @@ -53,6 +61,10 @@ extern s64 div_s64_rem(s64 dividend, s32 divisor, s32 *remainder);
    extern u64 div64_u64(u64 dividend, u64 divisor);
    #endif

    +#ifndef div64_s64
    +extern s64 div64_s64(s64 dividend, s64 divisor);
    +#endif
    +
    #endif /* BITS_PER_LONG */

    /**
    diff --git a/lib/div64.c b/lib/div64.c
    index a111eb8..e4e7fc6 100644
    --- a/lib/div64.c
    +++ b/lib/div64.c
    @@ -77,26 +77,68 @@ s64 div_s64_rem(s64 dividend, s32 divisor, s32 *remainder)
    EXPORT_SYMBOL(div_s64_rem);
    #endif

    -/* 64bit divisor, dividend and result. dynamic precision */
    +/**
    + * div64_u64 - unsigned 64bit divide with 64bit divisor
    + * @dividend: 64bit dividend
    + * @divisor: 64bit divisor
    + *
    + * This implementation is a modified version of the algorithm proposed
    + * by the book 'Hacker's Delight'. The original source and full proof
    + * can be found here and is available for use without restriction.
    + *
    + * 'http://www.hackersdelight.org/HDcode/newCode/divDouble.c'
    + */
    #ifndef div64_u64
    u64 div64_u64(u64 dividend, u64 divisor)
    {
    - u32 high, d;
    -
    - high = divisor >> 32;
    - if (high) {
    - unsigned int shift = fls(high);
    + u64 u0, quot0, quot1;
    + u32 rem;
    + int n;
    +
    + if (divisor >> 32 == 0) {
    + if (dividend >> 32 < divisor) {
    + return div_u64_rem(dividend, divisor, &rem);
    + } else {
    + u0 = dividend & 0xFFFFFFFF;
    + quot1 = div_u64_rem(dividend >> 32, divisor, &rem);
    + u0 += ((u64)rem << 32);
    + quot0 = div_u64_rem(u0, divisor, &rem);
    + return (quot1 << 32) + quot0;
    + }
    + } else {
    + n = __builtin_clzll(divisor);
    + quot1 = div_u64_rem(dividend >> 1, (divisor << n) >> 32, &rem);
    + quot0 = (quot1 << n) >> 31;

    - d = divisor >> shift;
    - dividend >>= shift;
    - } else
    - d = divisor;
    + if (quot0 != 0)
    + quot0 = quot0 - 1;
    + if ((dividend - quot0 * divisor) >= divisor)
    + quot0 = quot0 + 1;

    - return div_u64(dividend, d);
    + return quot0;
    + }
    }
    EXPORT_SYMBOL(div64_u64);
    #endif

    +/**
    + * div64_s64 - signed 64bit divide with 64bit divisor
    + * @dividend: 64bit dividend
    + * @divisor: 64bit divisor
    + */
    +#ifndef div64_s64
    +s64 div64_s64(s64 dividend, s64 divisor)
    +{
    + s64 quot, t;
    +
    + quot = div64_u64(abs64(dividend), abs64(divisor));
    + t = (dividend ^ divisor) >> 63;
    +
    + return (quot ^ t) - t;
    +}
    +EXPORT_SYMBOL(div64_s64);
    +#endif
    +
    #endif /* BITS_PER_LONG == 32 */

    /*
    --
    1.5.4.5
    #include <linux/module.h>

    /*
    * Verification test for div64_u64.
    */

    #ifndef abs64
    #define abs64(x) ({ \
    s64 __x = (x); \
    (__x < 0) ? -__x : __x; \
    })
    #endif

    int div64_u64_test(void)
    {
    u64 uu, vu, qu, ru;
    int n, i, j, errors = 0;
    const u64 tabu[] = {
    0, 1, 2, 3, 4, 5, 6, 7, 8, 9,
    10, 11, 12, 13, 14, 15, 16, 1000, 2003,
    32765, 32766, 32767, 32768, 32769, 32760,
    65533, 65534, 65535, 65536, 65537, 65538,
    0x7ffffffeULL, 0x7fffffffULL, 0x80000000ULL, 0x80000001ULL,
    0x7000000000000000ULL, 0x7000000080000000ULL, 0x7000000080000001ULL,
    0x7fffffffffffffffULL, 0x7fffffff8fffffffULL, 0x7fffffff8ffffff1ULL,
    0x7fffffff00000000ULL, 0x7fffffff80000000ULL, 0x7fffffff00000001ULL,
    0x8000000000000000ULL, 0x8000000080000000ULL, 0x8000000080000001ULL,
    0xc000000000000000ULL, 0xc000000080000000ULL, 0xc000000080000001ULL,
    0xfffffffffffffffdULL, 0xfffffffffffffffeULL, 0xffffffffffffffffULL,
    };

    printk("%s", "Testing unsigned 64-bit division.\n");
    n = sizeof(tabu) / sizeof(tabu[0]);
    for (i = 0; i < n; i++) {
    for (j = 1; j < n; j++) {
    uu = tabu[i];
    vu = tabu[j];
    qu = div64_u64(uu, vu);
    ru = uu - qu * vu;
    if (qu > uu || ru >= vu) {
    printk("%016llx/%016llx != %016llx "
    "rem %016llx\n", uu, vu, qu, ru);
    errors++;
    }
    }
    }

    if (errors) {
    printk("Failed %d/%d tests\n", errors, n * (n - 1));
    } else {
    printk("Passed all %d tests\n", n * (n - 1));
    }

    return 0;
    }

    void div64_u64_exit(void) { }

    module_init(div64_u64_test);
    module_exit(div64_u64_exit);
    #include <linux/module.h>

    /*
    * Verification test for div64_s64.
    */

    #ifndef abs64
    #define abs64(x) ({ \
    s64 __x = (x); \
    (__x < 0) ? -__x : __x; \
    })
    #endif

    int div64_s64_test(void)
    {
    s64 u, v, q, r;
    int n, i, j, k, errors = 0;
    const s64 tabs[] = {
    0, 1, 2, 3, 4, 5, 6, 7, 8, 9,
    10, 11, 12, 13, 14, 15, 16, 1000, 2003,
    32765, 32766, 32767, 32768, 32769, 32760,
    65533, 65534, 65535, 65536, 65537, 65538,
    0x7ffffffeLL, 0x7fffffffLL, 0x80000000LL, 0x80000001LL,
    0x7000000000000000LL, 0x7000000080000000LL, 0x7000000080000001LL,
    0x7fffffffffffffffLL, 0x7fffffff8fffffffLL, 0x7fffffff8ffffff1LL,
    0x7fffffff00000000LL, 0x7fffffff80000000LL, 0x7fffffff00000001LL,
    0x0123456789abcdefLL, 0x00000000abcdef01LL, 0x0000000012345678LL,
    };

    printk("%s", "Testing signed 64-bit division.\n");
    n = sizeof(tabs) / sizeof(tabs[0]);
    for (i = 0; i < n; i++) {
    for (j = 1; j < n; j++) {
    for (k = 0; k <= 3; k++) {
    u = (k & 1) ? -tabs[i] : tabs[i];
    v = (k >= 2) ? -tabs[j] : tabs[j];

    q = div64_s64(u, v);
    r = u - q * v;
    if (abs64(q) > abs64(u) ||
    abs64(r) >= abs64(v) ||
    (r != 0 && (r ^ u) < 0)) {
    printk("%016llx/%016llx != %016llx "
    "rem %016llx\n", u, v, q, r);
    errors++;
    }
    }
    }
    }

    if (errors) {
    printk("Failed %d/%d tests\n", errors, n * (n - 1));
    } else {
    printk("Passed all %d tests\n", n * (n - 1));
    }

    return 0;
    }

    void div64_s64_exit(void) { }

    module_init(div64_s64_test);
    module_exit(div64_s64_exit);
    linux-2.6.35

    Testing Summary | x86_64 | x86 |
    --------------------+-----------------+
    linux-2.6.35 | PASS | FAIL |
    linux-2.6.35+patch | PASS | PASS |


    Testing Details (x86_64)
    --------------------------------------------------------------------------
    * PASS - linux-2.6.35
    Testing unsigned 64-bit division.
    Passed all 2756 tests

    * PASS - linux-2.6.35+patch
    Testing unsigned 64-bit division.
    Passed all 2756 tests
    Testing signed 64-bit division.
    Passed all 2162 tests


    Testing Details (x86)
    --------------------------------------------------------------------------
    * FAIL - linux-2.6.35
    Testing unsigned 64-bit division.
    7000000080000000/7000000080000001 != 0000000000000001 rem ffffffffffffffff
    7fffffff8fffffff/7fffffffffffffff != 0000000000000001 rem ffffffff90000000
    7fffffff8ffffff1/7fffffffffffffff != 0000000000000001 rem ffffffff8ffffff2
    7fffffff8ffffff1/7fffffff8fffffff != 0000000000000001 rem fffffffffffffff2
    7fffffff00000000/7fffffff00000001 != 0000000000000001 rem ffffffffffffffff
    7fffffff80000000/7fffffffffffffff != 0000000000000001 rem ffffffff80000001
    7fffffff80000000/7fffffff8fffffff != 0000000000000001 rem fffffffff0000001
    7fffffff80000000/7fffffff8ffffff1 != 0000000000000001 rem fffffffff000000f
    8000000000000000/8000000080000000 != 0000000000000001 rem ffffffff80000000
    8000000000000000/8000000080000001 != 0000000000000001 rem ffffffff7fffffff
    8000000080000000/8000000080000001 != 0000000000000001 rem ffffffffffffffff
    c000000000000000/c000000080000000 != 0000000000000001 rem ffffffff80000000
    c000000000000000/c000000080000001 != 0000000000000001 rem ffffffff7fffffff
    c000000080000000/c000000080000001 != 0000000000000001 rem ffffffffffffffff
    fffffffffffffffd/7fffffffffffffff != 0000000000000002 rem ffffffffffffffff
    fffffffffffffffd/fffffffffffffffe != 0000000000000001 rem ffffffffffffffff
    fffffffffffffffe/ffffffffffffffff != 0000000000000001 rem ffffffffffffffff
    Failed 17/2756 tests

    * PASS - linux-2.6.35+patch
    Testing unsigned 64-bit division.
    Passed all 2756 tests
    Testing signed 64-bit division.
    Passed all 2162 tests

    \
     
     \ /
      Last update: 2010-08-09 18:43    [W:0.042 / U:8.724 seconds]
    ©2003-2016 Jasper Spaans. hosted at Digital OceanAdvertise on this site