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  PHC 
Open Source and information security mailing list archives
 
Hash Suite: Windows password security audit tool. GUI, reports in PDF.
[<prev] [next>] [<thread-prev] [thread-next>] [day] [month] [year] [list]
Date:	Sat,  5 Nov 2011 03:32:49 +0100
From:	Michal Soltys <soltys@....info>
To:	kaber@...sh.net
Cc:	davem@...emloft.net, netdev@...r.kernel.org
Subject: [PATCH 03/11] sch_hfsc.c: rtsc_min() convex/convex case fixup

The condition, which chooses smaller curve in convex/convex case is a bit too
simple. If we actually have intersecting curves, and base the test on initial
(x,y), instead of (x+dx,y+dy), the we can choose wrong curve:

                     +
                *   +
               *++++
       x,y  ++*+
    new ++++ *
            *
        ****
old ****

>From the above art, (x,y) will win the comparison and old curve will be chosen,
but it's new that should be selected (as its infinite 2nd segment is below the
old one).

Another possibility is to flatten the 1st segment (see hfsc paper), which has
an effect for *y2x() functions to return max x such that f(x) = y. In this way
the old curve would take precedence on the initial part. Worth considering for
another patch.

Signed-off-by: Michal Soltys <soltys@....info>
---
 net/sched/sch_hfsc.c |   22 +++++++++++++++-------
 1 files changed, 15 insertions(+), 7 deletions(-)

diff --git a/net/sched/sch_hfsc.c b/net/sched/sch_hfsc.c
index 6b73725..710cbda 100644
--- a/net/sched/sch_hfsc.c
+++ b/net/sched/sch_hfsc.c
@@ -559,13 +559,21 @@ rtsc_min(struct runtime_sc *rtsc, struct internal_sc *isc, u64 x, u64 y)
 	u32 dsm;
 
 	if (isc->sm1 <= isc->sm2) {
-		/* service curve is convex */
-		y1 = rtsc_x2y(rtsc, x);
-		if (y1 < y)
-			/* the current rtsc is smaller */
-			return;
-		rtsc->x = x;
-		rtsc->y = y;
+		/* service curve is convex or linear */
+		y1 = rtsc_x2y(rtsc, x + isc->dx);
+		if (y1 > y + isc->dy) {
+			/*
+			 * sm1/sm2 junction point is below the old curve, so
+			 * update the curve with ours; note that for strictly
+			 * convex curves a brief part of the first segment
+			 * might be above, but it's important that 2nd infinite
+			 * segment wins (which is below the old curve in this
+			 * case)
+			 */
+			rtsc->x = x;
+			rtsc->y = y;
+		}
+		/* else: the current rtsc is smaller */
 		return;
 	}
 
-- 
1.7.7.1

--
To unsubscribe from this list: send the line "unsubscribe netdev" in
the body of a message to majordomo@...r.kernel.org
More majordomo info at  http://vger.kernel.org/majordomo-info.html

Powered by blists - more mailing lists