Received-SPF: pass (google.com: best guess record for domain of linux-kernel-owner@vger.kernel.org designates 209.132.180.67 as permitted sender) client-ip=209.132.180.67;
Message-Id: <202003281643.02SGhE5I022872@sdf.org>
From:   George Spelvin <lkml@sdf.org>
Date:   Mon, 18 Mar 2019 14:50:35 -0400
Subject: [RFC PATCH v1 19/50] net/sched/sch_netem: Simplify get_crandom
To:     linux-kernel@vger.kernel.org, lkml@sdf.org
Cc:     Jamal Hadi Salim <jhs@mojatatu.com>,
        Cong Wang <xiyou.wangcong@gmail.com>,
        Jiri Pirko <jiri@resnulli.us>, netdev@vger.kernel.org
Sender: linux-kernel-owner@vger.kernel.org
Precedence: bulk

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@sdf.org>
Cc: Jamal Hadi Salim <jhs@mojatatu.com>
Cc: Cong Wang <xiyou.wangcong@gmail.com>
Cc: Jiri Pirko <jiri@resnulli.us>
Cc: netdev@vger.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