linux-kernel - [RFC PATCH v1 16/50] include/net/red.h: Simplify red

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]

Message-Id: <202003281643.02SGhDHv003972@sdf.org>
Date:   Mon, 18 Mar 2019 06:56:55 -0400
From:   George Spelvin <lkml@....org>
To:     linux-kernel@...r.kernel.org, lkml@....org
Cc:     Nogah Frankel <nogahf@...lanox.com>,
        Eric Dumazet <eric.dumazet@...il.com>,
        Aruna-Hewapathirane <aruna.hewapathirane@...il.com>
Subject: [RFC PATCH v1 16/50] include/net/red.h: Simplify red_random() TO BE
 VERIFIED

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@....org>
Cc: Nogah Frankel <nogahf@...lanox.com>
Cc: Eric Dumazet <eric.dumazet@...il.com>
Cc: Aruna-Hewapathirane <aruna.hewapathirane@...il.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