#2173 closed defect (fixed)
Potential integer overflow problem in EDF scheduler
Reported by: | Sebastian Huber | Owned by: | Joel Sherrill |
---|---|---|---|
Priority: | normal | Milestone: | 5.1 |
Component: | score | Version: | 4.11 |
Severity: | normal | Keywords: | |
Cc: | Blocked By: | ||
Blocking: |
Description (last modified by Sebastian Huber)
On 2014-03-21 14:46, Gedare Bloom wrote:> On Fri, Mar 21, 2014 at 9:43 AM, Sebastian Huber
<sebastian.huber@…> wrote:
[...]
I have another question regarding the EDF scheduler. Does this work in case
_Watchdog_Ticks_since_boot overflows?
No. For this, I think we need to use "deadline folding" which is just
modulo arithmetic.
void _Scheduler_EDF_Release_job(
Thread_Control *the_thread,
uint32_t deadline
)
{
Priority_Control new_priority;
if (deadline) {
/* Initializing or shifting deadline. */
new_priority = (_Watchdog_Ticks_since_boot + deadline)
& ~SCHEDULER_EDF_PRIO_MSB;
}
else {
/* Switch back to background priority. */
new_priority = the_thread->Start.initial_priority;
}
the_thread->real_priority = new_priority;
_Thread_Change_priority(the_thread, new_priority, true);
}
_Watchdog_Ticks_since_boot us uint32_t and overflows after 49 days with a one millisecond clock tick.
Change History (15)
comment:1 Changed on 03/24/14 at 06:06:34 by Sebastian Huber
comment:2 Changed on 11/23/14 at 16:26:56 by Joel Sherrill
Description: | modified (diff) |
---|---|
Resolution: | → wontfix |
Status: | new → closed |
Sebastian noted this was a hardware problem. Seems to indicate problem is NA now.
comment:3 Changed on 11/24/14 at 07:28:07 by Sebastian Huber
Resolution: | wontfix |
---|---|
Status: | closed → reopened |
Actually the Bugzilla to trac conversion seems to have a lot of errors.
This was not a hardware problem. This is still an open issue.
Without much consideration I would fix it like this:
- Make the tick since boot uint64_t.
- Make the Thread_Control::current_priority and Thread_Control::real_priority int64_t (to support easy comparison operations for RB tree insert and search).
- Remove the Scheduler_Operations::priority_compare operation.
With a system tick of 1ns the system can run 146years before something overflows.
comment:4 Changed on 11/24/14 at 18:58:28 by Gedare Bloom
Version: | HEAD → 4.11 |
---|
Replace Version=HEAD with Version=4.11 for the tickets with Milestone >= 4.11
comment:5 Changed on 11/24/14 at 19:35:19 by Joel Sherrill
The EDF scheduler should NOT use priority to store the deadline. That is one issue and it shows itself by bogus values being returned when you obtain the current priority. So #2 is NOT acceptable to me. The EDF scheduler should use its own internal stored value to sort the threads.
Why can't the scheduler use uptime and not ticks since boot?
The EDF scheduler is broken in assuming it can rewrite a thread priority with a deadline.
comment:6 Changed on 11/24/14 at 19:44:23 by Gedare Bloom
Why not rewrite thread (current) priority?
Priority should be an opaque notion of a scheduler in general, which should export information needed for synchronization modules (locks) to implement PI/PC protocols. The priority of a thread being scheduled according to EDF increases (toward 0) as its deadline draws closer.
That said, I'm not opposed to putting the absolute deadline into the scheduler-specific portion of the TCB. I just don't understand the strong negative reaction to letting the scheduler determine what priority means.
comment:8 Changed on 06/22/16 at 12:47:47 by Sebastian Huber <sebastian.huber@…>
comment:9 Changed on 06/22/16 at 12:47:57 by Sebastian Huber <sebastian.huber@…>
comment:10 Changed on 06/22/16 at 12:48:06 by Sebastian Huber <sebastian.huber@…>
comment:11 Changed on 06/22/16 at 12:48:16 by Sebastian Huber <sebastian.huber@…>
comment:12 Changed on 01/26/17 at 07:16:00 by Sebastian Huber
Milestone: | 4.11.1 → 4.11.2 |
---|
comment:13 Changed on 01/31/17 at 09:18:55 by Sebastian Huber
Description: | modified (diff) |
---|---|
Milestone: | 4.11.2 → 4.12 |
Resolution: | → fixed |
Status: | reopened → closed |
comment:14 Changed on 05/11/17 at 07:31:02 by Sebastian Huber
Milestone: | 4.12 → 4.12.0 |
---|
comment:15 Changed on 11/09/17 at 06:27:14 by Sebastian Huber
Milestone: | 4.12.0 → 5.1 |
---|
Milestone renamed
On 2014-03-21 14:46, Gedare Bloom wrote:> On Fri, Mar 21, 2014 at 9:43 AM, Sebastian Huber
[...]
_Watchdog_Ticks_since_boot us uint32_t and overflows after 49 days with a one millisecond clock tick.