Messages in this thread | | | Date | Mon, 23 Apr 2012 16:43:33 +0200 | From | Juri Lelli <> | Subject | Re: [PATCH 05/16] sched: SCHED_DEADLINE policy implementation. |
| |
On 04/23/2012 01:55 PM, Peter Zijlstra wrote: > On Fri, 2012-04-06 at 09:14 +0200, Juri Lelli wrote: >> +/* >> + * 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). >> + * >> + * For this to hold, we must check if: >> + * runtime / (deadline - t)< dl_runtime / dl_deadline . > > It might be good to put a few words in as to why that is.. I know I > always forget (but know where to find it by now), also might be good to > refer those papers Tommaso listed when Steven asked this a while back. >
Ok, I'll fix the comment, extend it and add T.'s references in the Documentation.
>> + */ >> +static bool dl_entity_overflow(struct sched_dl_entity *dl_se, u64 t) >> +{ >> + u64 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 = dl_se->dl_deadline * dl_se->runtime; >> + right = (dl_se->deadline - t) * dl_se->dl_runtime; > > > From what I can see there are no constraints on the values in > __setparam_dl() so the above left term can be constructed to be an > overflow. >
Yes, could happen :-\.
> Ideally we'd use u128 here, but I don't think people will let us :/ >
Do we need to do something about that? If we cannot go for bigger space probably limit dl_deadline (or warn the user)..
>> + return dl_time_before(right, left); >> +}
| |