linux-kernel - Re: [PATCH] Reduce the number of expensive division instructions done by _parse

lists.openwall.net		lists / announce owl-users owl-dev john-users john-dev passwdqc-users yescrypt popa3d-users / oss-security kernel-hardening musl sabotage tlsify passwords / crypt-dev xvendor / Bugtraq Full-Disclosure linux-kernel linux-netdev linux-ext4 linux-hardening linux-cve-announce PHC
Open Source and information security mailing list archives

Hash Suite: Windows password security audit tool. GUI, reports in PDF.

[<prev] [next>] [<thread-prev] [thread-next>] [day] [month] [year] [list]

Message-ID: <CA+55aFxHdFa4otDWJg4f+8sKEP3MBZqKBQCnH0Q8LXYtpdt1EA@mail.gmail.com>
Date:	Thu, 9 Feb 2012 08:58:37 -0800
From:	Linus Torvalds <torvalds@...ux-foundation.org>
To:	Eric Dumazet <eric.dumazet@...il.com>
Cc:	David Howells <dhowells@...hat.com>, adobriyan@...il.com,
	linux-kernel@...r.kernel.org
Subject: Re: [PATCH] Reduce the number of expensive division instructions done
 by _parse_integer()

On Thu, Feb 9, 2012 at 8:28 AM, Eric Dumazet <eric.dumazet@...il.com> wrote:
>
> You could avoid the divide and have cleaner code I think.
>
>        unsigned long long next = *res * base + val;
>
>        if (next < *res)
>                overflow = 1;
>        *res = next;

No. That pattern only works for a single addition.

For multiplication, you can overflow *and* still be bigger than the
starting value.

You either need to do the multiplication in a wider type (which would
be the natural way to do it on many 64-bit architectures, since they
often support 64x64->128 bit multiplies, and then doing a carry-add is
trivial), or you need to check the value before the multiplication. Or
you need to have a multiply that gives you overflow information, which
most don't.

So David's patch looks ok, although if this really is
performance-critical (and I could imagine some crazy /proc or /sys
access loads where the divide really does show up very clearly) I do
think it could be even done more efficiently. But probably only if we
start doing some arch-specific stuff.

                  Linus
--
To unsubscribe from this list: send the line "unsubscribe linux-kernel" in
the body of a message to majordomo@...r.kernel.org
More majordomo info at  http://vger.kernel.org/majordomo-info.html
Please read the FAQ at  http://www.tux.org/lkml/