#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

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.

comment:2 Changed on 11/23/14 at 16:26:56 by Joel Sherrill

Description: modified (diff)
Resolution: wontfix
Status: newclosed

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: closedreopened

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:

  1. Make the tick since boot uint64_t.
  1. Make the Thread_Control::current_priority and Thread_Control::real_priority int64_t (to support easy comparison operations for RB tree insert and search).
  1. 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: HEAD4.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:7 Changed on 03/02/15 at 20:42:45 by Gedare Bloom

Milestone: 4.114.11.1

bump milestone

comment:8 Changed on 06/22/16 at 12:47:47 by Sebastian Huber <sebastian.huber@…>

In 77ff5599e0d8e6d91190a379be21a332f83252b0/rtems:

score: Introduce map priority scheduler operation

Introduce map/unmap priority scheduler operations to map thread priority
values from/to the user domain to/from the scheduler domain. Use the
map priority operation to validate the thread priority. The EDF
schedulers use this new operation to distinguish between normal
priorities and priorities obtain through a job release.

Update #2173.
Update #2556.

comment:9 Changed on 06/22/16 at 12:47:57 by Sebastian Huber <sebastian.huber@…>

In 7ec66e0890c65f3fdfed9db91a4ae59de6a8ff18/rtems:

score: Remove hidden deadline overrule for CBS

Do what the user commands. Maybe we should add a rtems_cbs_period()
that calls rtems_rate_monotonic_period() with the right parameter.

Update #2173.

comment:10 Changed on 06/22/16 at 12:48:06 by Sebastian Huber <sebastian.huber@…>

In 9a78f8a5076687a8744991998ee6119f87db12a8/rtems:

score: Modify release job scheduler operation

Pass the deadline in watchdog ticks to the scheduler.

Update #2173.

comment:11 Changed on 06/22/16 at 12:48:16 by Sebastian Huber <sebastian.huber@…>

In 99fc1d1d1b44e70a0bed4c94a514bd3f3b5df64f/rtems:

score: Rework EDF scheduler

Use inline red-black tree insert. Do not use shifting priorities since
this is not supported by the thread queues. Due to the 32-bit
Priority_Control this currently limits the uptime to 49days with a 1ms
clock tick.

Update #2173.

comment:12 Changed on 01/26/17 at 07:16:00 by Sebastian Huber

Milestone: 4.11.14.11.2

comment:13 Changed on 01/31/17 at 09:18:55 by Sebastian Huber

Description: modified (diff)
Milestone: 4.11.24.12
Resolution: fixed
Status: reopenedclosed

comment:14 Changed on 05/11/17 at 07:31:02 by Sebastian Huber

Milestone: 4.124.12.0

comment:15 Changed on 11/09/17 at 06:27:14 by Sebastian Huber

Milestone: 4.12.05.1

Milestone renamed

Note: See TracTickets for help on using tickets.