[RTEMS Project] #2174: Memory corruption with EDF scheduler and thread priority queues

[RTEMS trac]

#2174: Memory corruption with EDF scheduler and thread priority queues
-----------------------------+-----------------------
 Reporter:  sebastian.huber  |       Owner:  gedare
     Type:  defect           |      Status:  assigned
 Priority:  normal           |   Milestone:  4.11
Component:  cpukit           |     Version:  HEAD
 Severity:  normal           |  Resolution:
 Keywords:                   |
-----------------------------+-----------------------
Changes (by joel.sherrill):

 * owner:  joel.sherrill => gedare
 * status:  new => assigned


Old description:

> On 2014-03-21 14:51, Gedare Bloom wrote:> On Fri, Mar 21, 2014 at 9:32
> AM, Sebastian Huber
> > <sebastian.huber at embedded-brains.de>  wrote:
> >> >Hello,
> >> >
> >> >I changed the objects allocate/free to use the allocator mutex.  This
> change
> >> >is very important since otherwise the thread dispatch latency depends
> on the
> >> >heap fragmentation.  I noticed now a problem with the thread priority
> queues
> >> >and the EDF scheduler.  The EDF scheduler uses priority values
> greater than
> >> >255.  Now we have a problem in _Thread_queue_Enqueue_priority():
> >> >
> >> >Thread_blocking_operation_States _Thread_queue_Enqueue_priority (
> >> >   Thread_queue_Control *the_thread_queue,
> >> >   Thread_Control       *the_thread,
> >> >   ISR_Level            *level_p
> >> >)
> >> >{
> >> >[...]
> >> >   _Chain_Initialize_empty( &the_thread->Wait.Block2n );
> >> >
> >> >   priority     = the_thread->current_priority;
> >> >   header_index = _Thread_queue_Header_number( priority );
> >> >   header       = &the_thread_queue->Queues.Priority[ header_index ];
> >> >
> >> >The header_index is now out of range.
> >> >
> >> >Should the EDF scheduler work with thread priority queues?
> >> >
> > This is tricky. I can see a few possibilities:
> > 1) Do not permit blocking with priority for EDF at least for periodic
> > tasks.  I'm not sure how to enforce this. For non-periodic tasks, the
> > priority can be set to <255 but I forget if the upper-bit is used in
> > current_priority for distinguishing the background from periodic. If
> > so there needs to be a _Thread_Current_priority() function to abstract
> > this out.
> >
> > 2) Use deadline folding [hardware-implemented version described in
> > this paper behind pay wall:http://dl.acm.org/citation.cfm?id=829010  ]
> > with a max absolute deadline of 256. This permits relative deadlines
> > between 1 and 127 to be useable. Probably this is OK, but I am not
> > sure the complexity involved. Again, this requires adding some
> > abstraction layer to getting priority from TCB.
> >
> > 3) Make the thread priority queue use a more scalable solution.
> > Probably this can be done by front-loading the cost on the enqueue
> > path so that dequeue is O(1). Usually, these thread priority queues
> > should be quite small so the O() may not matter too much.

New description:

 On 2014-03-21 14:51, Gedare Bloom wrote:> On Fri, Mar 21, 2014 at 9:32 AM,
 Sebastian Huber
 > <sebastian.huber at embedded-brains.de>  wrote:
 >> >Hello,
 >> >
 >> >I changed the objects allocate/free to use the allocator mutex.  This
 change
 >> >is very important since otherwise the thread dispatch latency depends
 on the
 >> >heap fragmentation.  I noticed now a problem with the thread priority
 queues
 >> >and the EDF scheduler.  The EDF scheduler uses priority values greater
 than
 >> >255.  Now we have a problem in _Thread_queue_Enqueue_priority():
 >> >
 >> >Thread_blocking_operation_States _Thread_queue_Enqueue_priority (
 >> >   Thread_queue_Control *the_thread_queue,
 >> >   Thread_Control       *the_thread,
 >> >   ISR_Level            *level_p
 >> >)
 >> >{
 >> >[...]
 >> >   _Chain_Initialize_empty( &the_thread->Wait.Block2n );
 >> >
 >> >   priority     = the_thread->current_priority;
 >> >   header_index = _Thread_queue_Header_number( priority );
 >> >   header       = &the_thread_queue->Queues.Priority[ header_index ];
 >> >
 >> >The header_index is now out of range.
 >> >
 >> >Should the EDF scheduler work with thread priority queues?
 >> >
 > This is tricky. I can see a few possibilities:
 > 1) Do not permit blocking with priority for EDF at least for periodic
 > tasks.  I'm not sure how to enforce this. For non-periodic tasks, the
 > priority can be set to <255 but I forget if the upper-bit is used in
 > current_priority for distinguishing the background from periodic. If
 > so there needs to be a _Thread_Current_priority() function to abstract
 > this out.
 >
 > 2) Use deadline folding [hardware-implemented version described in
 > this paper behind pay wall:http://dl.acm.org/citation.cfm?id=829010  ]
 > with a max absolute deadline of 256. This permits relative deadlines
 > between 1 and 127 to be useable. Probably this is OK, but I am not
 > sure the complexity involved. Again, this requires adding some
 > abstraction layer to getting priority from TCB.
 >
 > 3) Make the thread priority queue use a more scalable solution.
 > Probably this can be done by front-loading the cost on the enqueue
 > path so that dequeue is O(1). Usually, these thread priority queues
 > should be quite small so the O() may not matter too much.

--

Comment:

 Gedare... you are more familiar with this code than I am. Is it fixed?

--
Ticket URL: <http://devel.rtems.org/ticket/2174#comment:3>
RTEMS Project <http://www.rtems.org/>
RTEMS Project