linux-kernel - Re: [PATCH 01/16] math128: Introduce various 128bit primitives

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>] [<thread-prev] [thread-next>] [day] [month] [year] [list]

Message-ID: <1351241389.12171.45.camel@twins>
Date:	Fri, 26 Oct 2012 10:49:49 +0200
From:	Peter Zijlstra <peterz@...radead.org>
To:	Linus Torvalds <torvalds@...ux-foundation.org>
Cc:	Juri Lelli <juri.lelli@...il.com>, tglx@...utronix.de,
	mingo@...hat.com, rostedt@...dmis.org, oleg@...hat.com,
	fweisbec@...il.com, darren@...art.com, johan.eker@...csson.com,
	p.faure@...tech.ch, linux-kernel@...r.kernel.org,
	claudio@...dence.eu.com, michael@...rulasolutions.com,
	fchecconi@...il.com, tommaso.cucinotta@...up.it,
	nicola.manica@...i.unitn.it, luca.abeni@...tn.it,
	dhaval.giani@...il.com, hgu1972@...il.com,
	paulmck@...ux.vnet.ibm.com, raistlin@...ux.it,
	insop.song@...csson.com, liming.wang@...driver.com,
	jkacur@...hat.com, harald.gustafsson@...csson.com,
	vincent.guittot@...aro.org, Ingo Molnar <mingo@...nel.org>,
	Andrew Morton <akpm@...ux-foundation.org>
Subject: Re: [PATCH 01/16] math128: Introduce various 128bit primitives

On Thu, 2012-10-25 at 15:26 -0700, Linus Torvalds wrote:
> it's the *rest* of the "u128" math I really object to. I also wonder
> about the u64xu64 math case for SCHED_DEADLINE, because I assume that
> it doesn't actually end up using the 128-bit result in that form, but
> scales it down again some way? 

No, it does a compare on two u128, so it doesn't loose any precision.
If it were to scale down again and loose precision I'd agree with you
that introducing the u128 stuff is pointless.

The point is (as mentioned in the comments below) overflowing an actual
u64 is rare, however since some of this (specifically the
dl_{runtime,deadline} parameters) is user specified, we have to assume
we will overflow.

---

+/*
+ * Here we check if --at time t-- an entity (which is probably being
+ * [re]activated or, in general, enqueued) can use its remaining runtime
+ * and its current deadline _without_ exceeding the bandwidth it is
+ * assigned (function returns true if it can't). We are in fact applying
+ * one of the CBS rules: when a task wakes up, if the residual runtime
+ * over residual deadline fits within the allocated bandwidth, then we
+ * can keep the current (absolute) deadline and residual budget without
+ * disrupting the schedulability of the system. Otherwise, we should
+ * refill the runtime and set the deadline a period in the future,
+ * because keeping the current (absolute) deadline of the task would
+ * result in breaking guarantees promised to other tasks.
+ *
+ * This function returns true if:
+ *
+ *   runtime / (deadline - t) > dl_runtime / dl_deadline ,
+ *
+ * IOW we can't recycle current parameters.
+ */
+static bool dl_entity_overflow(struct sched_dl_entity *dl_se, u64 t)
+{
+       u128 left, right;
+
+       /*
+        * left and right are the two sides of the equation above,
+        * after a bit of shuffling to use multiplications instead
+        * of divisions.
+        *
+        * Note that none of the time values involved in the two
+        * multiplications are absolute: dl_deadline and dl_runtime
+        * are the relative deadline and the maximum runtime of each
+        * instance, runtime is the runtime left for the last instance
+        * and (deadline - t), since t is rq->clock, is the time left
+        * to the (absolute) deadline. Therefore, overflowing the u64
+        * type is very unlikely to occur in both cases.
+        */
+       left = mul_u64_u64(dl_se->dl_deadline, dl_se->runtime);
+       right = mul_u64_u64((dl_se->deadline - t), dl_se->dl_runtime);
+
+       if (cmp_u128(left, right) > 0)
+               return true;
+
+       return false;
+}
--
To unsubscribe from this list: send the line "unsubscribe linux-kernel" in
the body of a message to majordomo@...r.kernel.org
More majordomo info at  http://vger.kernel.org/majordomo-info.html
Please read the FAQ at  http://www.tux.org/lkml/