linux-kernel - [RFC PATCH v1 19/50] net/sched/sch_netem: Simplify get

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

Date:   Mon, 18 Mar 2019 14:50:35 -0400
From:   George Spelvin <lkml@....org>
To:     linux-kernel@...r.kernel.org, lkml@....org
Cc:     Jamal Hadi Salim <jhs@...atatu.com>,
        Cong Wang <xiyou.wangcong@...il.com>,
        Jiri Pirko <jiri@...nulli.us>, netdev@...r.kernel.org
Subject: [RFC PATCH v1 19/50] net/sched/sch_netem: Simplify get_crandom

This can be done with a single 32x32-bit multiply, rather
than a 64x64 as previously written.

One conditional subtract is required to handle the 33rd bit
of value - state->last, but that's cheaper than the wider multiply
even on 64-bit platforms, and much cheaper on 32-bit.

The need for a 33rd bit to hold rho+1 is avoided by using ~rho
instead.

(Found while auditing prandom_u32() callers.)

Signed-off-by: George Spelvin <lkml@....org>
Cc: Jamal Hadi Salim <jhs@...atatu.com>
Cc: Cong Wang <xiyou.wangcong@...il.com>
Cc: Jiri Pirko <jiri@...nulli.us>
Cc: netdev@...r.kernel.org
---
 net/sched/sch_netem.c | 16 +++++++---------
 1 file changed, 7 insertions(+), 9 deletions(-)

diff --git a/net/sched/sch_netem.c b/net/sched/sch_netem.c
index 7b7503326faf5..fa41601538b21 100644
--- a/net/sched/sch_netem.c
+++ b/net/sched/sch_netem.c
@@ -180,17 +180,15 @@ static void init_crandom(struct crndstate *state, unsigned long rho)
  */
 static u32 get_crandom(struct crndstate *state)
 {
-	u64 value, rho;
-	unsigned long answer;
+	u32 value = prandom_u32(), last, rho, answer;
 
-	if (!state || state->rho == 0)	/* no correlation */
-		return prandom_u32();
+	if (!state || (rho = state->rho) == 0)	/* no correlation */
+		return value;
+	last = state->last;
+	answer = last + reciprocal_scale(value - last, ~rho);
 
-	value = prandom_u32();
-	rho = (u64)state->rho + 1;
-	answer = (value * ((1ull<<32) - rho) + state->last * rho) >> 32;
-	state->last = answer;
-	return answer;
+	/* Handle 33rd bit of difference */
+	return state->last = value >= last ? answer : answer - ~rho;
 }
 
 /* loss_4state - 4-state model loss generator
-- 
2.26.0