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

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

[George Spelvin]

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@sdf.org>
Cc: Richard Weinberger <richard@nod.at>
Cc: Artem Bityutskiy <dedekind1@gmail.com>
Cc: Adrian Hunter <adrian.hunter@intel.com>
Cc: linux-mtd@lists.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


______________________________________________________
Linux MTD discussion mailing list
http://lists.infradead.org/mailman/listinfo/linux-mtd/