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.02SGhDHv003972@sdf.org>
From:   George Spelvin <lkml@sdf.org>
Date:   Mon, 18 Mar 2019 06:56:55 -0400
Subject: [RFC PATCH v1 16/50] include/net/red.h: Simplify red_random() TO BE
 VERIFIED
To:     linux-kernel@vger.kernel.org, lkml@sdf.org
Cc:     Nogah Frankel <nogahf@mellanox.com>,
        Eric Dumazet <eric.dumazet@gmail.com>,
        Aruna-Hewapathirane <aruna.hewapathirane@gmail.com>
Sender: linux-kernel-owner@vger.kernel.org
Precedence: bulk

The existing code goes to some trouble to optimize the
computation of prandom_u32()/(p->max_P/p->qth_delta).

But given that the first division is already an approximation,
there's no need for the fiddly shifting included in
reciprocal_divide().  Just compute p->qth_delta / p->max_P
and do a 32-bit multiply and 32-bit shift.

This code is subtle, so I'm not certain I didn't break
something; review definitely appreciated!

Signed-off-by: George Spelvin <lkml@sdf.org>
Cc: Nogah Frankel <nogahf@mellanox.com>
Cc: Eric Dumazet <eric.dumazet@gmail.com>
Cc: Aruna-Hewapathirane <aruna.hewapathirane@gmail.com>
---
 include/net/red.h | 22 +++++++++++-----------
 1 file changed, 11 insertions(+), 11 deletions(-)

diff --git a/include/net/red.h b/include/net/red.h
index 9665582c4687e..a357ddb227433 100644
--- a/include/net/red.h
+++ b/include/net/red.h
@@ -131,8 +131,7 @@ struct red_parms {
 	u32		qth_max;	/* Max avg length threshold: Wlog scaled */
 	u32		Scell_max;
 	u32		max_P;		/* probability, [0 .. 1.0] 32 scaled */
-	/* reciprocal_value(max_P / qth_delta) */
-	struct reciprocal_value	max_P_reciprocal;
+	u32		delta_max_p;	/* (qth_delta << 32) / max_P */
 	u32		qth_delta;	/* max_th - min_th */
 	u32		target_min;	/* min_th + 0.4*(max_th - min_th) */
 	u32		target_max;	/* min_th + 0.6*(max_th - min_th) */
@@ -184,7 +183,6 @@ static inline void red_set_parms(struct red_parms *p,
 				 u8 Scell_log, u8 *stab, u32 max_P)
 {
 	int delta = qth_max - qth_min;
-	u32 max_p_delta;
 
 	p->qth_min	= qth_min << Wlog;
 	p->qth_max	= qth_max << Wlog;
@@ -198,9 +196,10 @@ static inline void red_set_parms(struct red_parms *p,
 		max_P *= delta; /* max_P = (qth_max - qth_min)/2^Plog */
 	}
 	p->max_P = max_P;
-	max_p_delta = max_P / delta;
-	max_p_delta = max(max_p_delta, 1U);
-	p->max_P_reciprocal  = reciprocal_value(max_p_delta);
+	if (delta >= max_P)
+		p->delta_max_p = 0xffffffff;
+	else
+		p->delta_max_p = DIV_ROUND_CLOSEST_ULL((u64)delta << 32, max_P);
 
 	/* RED Adaptative target :
 	 * [min_th + 0.4*(min_th - max_th),
@@ -316,7 +315,7 @@ static inline unsigned long red_calc_qavg(const struct red_parms *p,
 
 static inline u32 red_random(const struct red_parms *p)
 {
-	return reciprocal_divide(prandom_u32(), p->max_P_reciprocal);
+	return reciprocal_scale(prandom_u32(), p->delta_max_p);
 }
 
 static inline int red_mark_probability(const struct red_parms *p,
@@ -397,7 +396,6 @@ static inline int red_action(const struct red_parms *p,
 static inline void red_adaptative_algo(struct red_parms *p, struct red_vars *v)
 {
 	unsigned long qavg;
-	u32 max_p_delta;
 
 	qavg = v->qavg;
 	if (red_is_idling(v))
@@ -411,8 +409,10 @@ static inline void red_adaptative_algo(struct red_parms *p, struct red_vars *v)
 	else if (qavg < p->target_min && p->max_P >= MAX_P_MIN)
 		p->max_P = (p->max_P/10)*9; /* maxp = maxp * Beta */
 
-	max_p_delta = DIV_ROUND_CLOSEST(p->max_P, p->qth_delta);
-	max_p_delta = max(max_p_delta, 1U);
-	p->max_P_reciprocal = reciprocal_value(max_p_delta);
+	if (p->qth_delta >= p->max_P)
+		p->delta_max_p = 0xffffffff;
+	else
+		p->delta_max_p = DIV_ROUND_CLOSEST_ULL((u64)p->qth_delta << 32,
+						       p->max_P);
 }
 #endif
-- 
2.26.0