* [RFC PATCH v1 19/50] net/sched/sch_netem: Simplify get_crandom
@ 2019-03-18 18:50 George Spelvin
0 siblings, 0 replies; only message in thread
From: George Spelvin @ 2019-03-18 18:50 UTC (permalink / raw)
To: linux-kernel, lkml; +Cc: Jamal Hadi Salim, Cong Wang, Jiri Pirko, netdev
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
^ permalink raw reply related [flat|nested] only message in thread
only message in thread, other threads:[~2020-03-28 16:43 UTC | newest]
Thread overview: (only message) (download: mbox.gz / follow: Atom feed)
-- links below jump to the message on this page --
2019-03-18 18:50 [RFC PATCH v1 19/50] net/sched/sch_netem: Simplify get_crandom George Spelvin
This is an external index of several public inboxes,
see mirroring instructions on how to clone and mirror
all data and code used by this external index.