linux-kernel - [RFC PATCH v1 06/50] ubi/debug: Optimize computation of odds

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>] [day] [month] [year] [list]

Message-Id: <202003281643.02SGh8XV025558@sdf.org>
Date:   Mon, 18 Mar 2019 04:22:17 -0400
From:   George Spelvin <lkml@....org>
To:     linux-kernel@...r.kernel.org, lkml@....org
Cc:     Richard Weinberger <richard@....at>,
        Artem Bityutskiy <dedekind1@...il.com>,
        Adrian Hunter <adrian.hunter@...el.com>,
        linux-mtd@...ts.infradead.org
Subject: [RFC PATCH v1 06/50] ubi/debug: Optimize computation of odds

Not only is "prandom_u32() % d" an inefficient way to obtain
a random number, but "prandom_u32_max(d) < n" is an inefficient
way to return true with probability n/d.

Where n and d are compile-time constants, the efficient way to
do this test is "prandom_u32() < ((u64)n << 32)/d.

If n == 1 and d is not a power of 2, then 0xffffffff/d == 0x100000000/d
works just as well and avoids some 64-bit arithmetic.

Signed-off-by: George Spelvin <lkml@....org>
Cc: Richard Weinberger <richard@....at>
Cc: Artem Bityutskiy <dedekind1@...il.com>
Cc: Adrian Hunter <adrian.hunter@...el.com>
Cc: linux-mtd@...ts.infradead.org
---
 drivers/mtd/ubi/debug.h | 6 +++---
 fs/ubifs/debug.c        | 5 +++--
 2 files changed, 6 insertions(+), 5 deletions(-)

diff --git a/drivers/mtd/ubi/debug.h b/drivers/mtd/ubi/debug.h
index 118248a5d7d48..d19671c1a098c 100644
--- a/drivers/mtd/ubi/debug.h
+++ b/drivers/mtd/ubi/debug.h
@@ -73,7 +73,7 @@ static inline int ubi_dbg_is_bgt_disabled(const struct ubi_device *ubi)
 static inline int ubi_dbg_is_bitflip(const struct ubi_device *ubi)
 {
 	if (ubi->dbg.emulate_bitflips)
-		return !(prandom_u32() % 200);
+		return prandom_u32() < 0xffffffff/200;
 	return 0;
 }
 
@@ -87,7 +87,7 @@ static inline int ubi_dbg_is_bitflip(const struct ubi_device *ubi)
 static inline int ubi_dbg_is_write_failure(const struct ubi_device *ubi)
 {
 	if (ubi->dbg.emulate_io_failures)
-		return !(prandom_u32() % 500);
+		return prandom_u32() < 0xffffffff/500;
 	return 0;
 }
 
@@ -101,7 +101,7 @@ static inline int ubi_dbg_is_write_failure(const struct ubi_device *ubi)
 static inline int ubi_dbg_is_erase_failure(const struct ubi_device *ubi)
 {
 	if (ubi->dbg.emulate_io_failures)
-		return !(prandom_u32() % 400);
+		return prandom_u32() < 0xffffffff/400;
 	return 0;
 }
 
diff --git a/fs/ubifs/debug.c b/fs/ubifs/debug.c
index 0f5a480fe264f..3d8d8eaea6c66 100644
--- a/fs/ubifs/debug.c
+++ b/fs/ubifs/debug.c
@@ -2444,9 +2444,10 @@ int dbg_check_nondata_nodes_order(struct ubifs_info *c, struct list_head *head)
 	return 0;
 }
 
-static inline int chance(unsigned int n, unsigned int out_of)
+static bool chance(unsigned int n, unsigned int out_of)
 {
-	return !!((prandom_u32() % out_of) + 1 <= n);
+	/* RHS is a constant expression */
+	return prandom_u32() < ((u64)n << 32) / out_of;
 
 }
 
-- 
2.26.0