[Bug 2174] New: Memory corruption with EDF scheduler and thread priority queues

[bugzilla-daemon at rtems.org]

https://www.rtems.org/bugzilla/show_bug.cgi?id=2174

             Bug #: 2174
           Summary: Memory corruption with EDF scheduler and thread
                    priority queues
    Classification: Unclassified
           Product: RTEMS
           Version: HEAD
          Platform: All
        OS/Version: RTEMS
            Status: NEW
          Severity: normal
          Priority: P3
         Component: cpukit
        AssignedTo: joel.sherrill at oarcorp.com
        ReportedBy: sebastian.huber at embedded-brains.de


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.

-- 
Configure bugmail: https://www.rtems.org/bugzilla/userprefs.cgi?tab=email
------- You are receiving this mail because: -------
You are watching all bug changes.