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

[Peter Zijlstra <peterz@infradead.org>]

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;
+}