linux-kernel - [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 for Android: free password hash cracker in your pocket

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

Message-ID: <20120209154819.32070.93358.stgit@warthog.procyon.org.uk>
Date:	Thu, 09 Feb 2012 15:48:20 +0000
From:	David Howells <dhowells@...hat.com>
To:	adobriyan@...il.com
Cc:	torvalds@...ux-foundation.org, dhowells@...hat.com,
	linux-kernel@...r.kernel.org
Subject: [PATCH] Reduce the number of expensive division instructions done by
 _parse_integer()

_parse_integer() does one or two division instructions (which are slow) per
digit parsed to perform the overflow check.

Furthermore, these are particularly expensive examples of division instruction
as the number of clock cycles required to complete them may go up with the
position of the most significant set bit in the dividend:

	if (*res > div_u64(ULLONG_MAX - val, base))

which is as maximal as possible.

Worse, on 32-bit arches, more than one of these division instructions may be
required per digit.

So, assuming we don't support a base of more than 16, skip the check if the
top nibble of the result is not set at this point.

Signed-off-by: David Howells <dhowells@...hat.com>
---

 lib/kstrtox.c |    2 +-
 1 files changed, 1 insertions(+), 1 deletions(-)

diff --git a/lib/kstrtox.c b/lib/kstrtox.c
index 7a94c8f..f80c896 100644
--- a/lib/kstrtox.c
+++ b/lib/kstrtox.c
@@ -64,7 +64,7 @@ unsigned int _parse_integer(const char *s, unsigned int base, unsigned long long
 
 		if (val >= base)
 			break;
-		if (*res > div_u64(ULLONG_MAX - val, base))
+		if (unlikely(*res >> 60) && *res > div_u64(ULLONG_MAX - val, base))
 			overflow = 1;
 		*res = *res * base + val;
 		rv++;

--
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/