diff options
author | Sebastian Huber <sebastian.huber@embedded-brains.de> | 2016-07-26 10:34:21 +0200 |
---|---|---|
committer | Sebastian Huber <sebastian.huber@embedded-brains.de> | 2016-07-27 10:55:30 +0200 |
commit | d79df38c2bea50112214ade95776cb90d693e390 (patch) | |
tree | 77bcc6ae76dde57c449d808ef2cce318cd198b06 /cpukit/score/src/threadqenqueue.c | |
parent | score: Turn thread lock into thread wait lock (diff) | |
download | rtems-d79df38c2bea50112214ade95776cb90d693e390.tar.bz2 |
score: Add deadlock detection
The mutex objects use the owner field of the thread queues for the mutex
owner. Use this and add a deadlock detection to
_Thread_queue_Enqueue_critical() for thread queues with an owner.
Update #2412.
Update #2556.
Close #2765.
Diffstat (limited to 'cpukit/score/src/threadqenqueue.c')
-rw-r--r-- | cpukit/score/src/threadqenqueue.c | 265 |
1 files changed, 250 insertions, 15 deletions
diff --git a/cpukit/score/src/threadqenqueue.c b/cpukit/score/src/threadqenqueue.c index 19c345b6c5..a9b2c35af5 100644 --- a/cpukit/score/src/threadqenqueue.c +++ b/cpukit/score/src/threadqenqueue.c @@ -9,6 +9,8 @@ * COPYRIGHT (c) 1989-2014. * On-Line Applications Research Corporation (OAR). * + * Copyright (c) 2015, 2016 embedded brains GmbH. + * * The license and distribution terms for this file may be * found in the file LICENSE in this distribution or at * http://www.rtems.org/license/LICENSE. @@ -34,49 +36,275 @@ #define THREAD_QUEUE_READY_AGAIN \ (THREAD_WAIT_CLASS_OBJECT | THREAD_WAIT_STATE_READY_AGAIN) +#if defined(RTEMS_SMP) +/* + * A global registry of active thread queue links is used to provide deadlock + * detection on SMP configurations. This is simple to implement and no + * additional storage is required for the thread queues. The disadvantage is + * the global registry is not scalable and may lead to lock contention. + * However, the registry is only used in case of nested resource conflicts. In + * this case, the application is already in trouble. + */ + +typedef struct { + ISR_lock_Control Lock; + + RBTree_Control Links; +} Thread_queue_Links; + +static Thread_queue_Links _Thread_queue_Links = { + ISR_LOCK_INITIALIZER( "Thread Queue Links" ), + RBTREE_INITIALIZER_EMPTY( _Thread_queue_Links.Links ) +}; + +static bool _Thread_queue_Link_equal( + const void *left, + const RBTree_Node *right +) +{ + const Thread_queue_Queue *the_left; + const Thread_queue_Link *the_right; + + the_left = left; + the_right = (Thread_queue_Link *) right; + + return the_left == the_right->source; +} + +static bool _Thread_queue_Link_less( + const void *left, + const RBTree_Node *right +) +{ + const Thread_queue_Queue *the_left; + const Thread_queue_Link *the_right; + + the_left = left; + the_right = (Thread_queue_Link *) right; + + return (uintptr_t) the_left < (uintptr_t) the_right->source; +} + +static void *_Thread_queue_Link_map( RBTree_Node *node ) +{ + return node; +} + +static Thread_queue_Link *_Thread_queue_Link_find( + Thread_queue_Links *links, + Thread_queue_Queue *source +) +{ + return _RBTree_Find_inline( + &links->Links, + source, + _Thread_queue_Link_equal, + _Thread_queue_Link_less, + _Thread_queue_Link_map + ); +} + +static bool _Thread_queue_Link_add( + Thread_queue_Link *link, + Thread_queue_Queue *source, + Thread_queue_Queue *target +) +{ + Thread_queue_Links *links; + Thread_queue_Queue *recursive_target; + ISR_lock_Context lock_context; + + links = &_Thread_queue_Links; + recursive_target = target; + + _ISR_lock_Acquire( &links->Lock, &lock_context ); + + while ( true ) { + Thread_queue_Link *recursive_link; + + recursive_link = _Thread_queue_Link_find( links, recursive_target ); + + if ( recursive_link == NULL ) { + break; + } + + recursive_target = recursive_link->target; + + if ( recursive_target == source ) { + _ISR_lock_Release( &links->Lock, &lock_context ); + return false; + } + } + + link->source = source; + link->target = target; + _RBTree_Insert_inline( + &links->Links, + &link->Registry_node, + source, + _Thread_queue_Link_less + ); + + _ISR_lock_Release( &links->Lock, &lock_context ); + return true; +} + +static void _Thread_queue_Link_remove( Thread_queue_Link *link ) +{ + Thread_queue_Links *links; + ISR_lock_Context lock_context; + + links = &_Thread_queue_Links; + + _ISR_lock_Acquire( &links->Lock, &lock_context ); + _RBTree_Extract( &links->Links, &link->Registry_node ); + _ISR_lock_Release( &links->Lock, &lock_context ); +} +#endif + static void _Thread_queue_Path_release( Thread_queue_Path *path ) { #if defined(RTEMS_SMP) - Thread_queue_Link *link; + Chain_Node *head; + Chain_Node *node; - link = &path->Start; + head = _Chain_Head( &path->Links ); + node = _Chain_Last( &path->Links ); + + while ( head != node ) { + Thread_queue_Link *link; + + link = RTEMS_CONTAINER_OF( node, Thread_queue_Link, Path_node ); + + if ( link->Queue_context.Wait.queue_lock != NULL ) { + _Thread_queue_Link_remove( link ); + } - if ( link->owner != NULL ) { _Thread_Wait_release_critical( link->owner, &link->Queue_context ); + + node = _Chain_Previous( node ); +#if defined(RTEMS_DEBUG) + _Chain_Set_off_chain( &link->Path_node ); +#endif } #else (void) path; #endif } -static void _Thread_queue_Path_acquire( +static bool _Thread_queue_Path_acquire( Thread_Control *the_thread, Thread_queue_Queue *queue, Thread_queue_Path *path ) { -#if defined(RTEMS_SMP) Thread_Control *owner; + +#if defined(RTEMS_SMP) Thread_queue_Link *link; + Thread_queue_Queue *target; + + /* + * For an overview please look at the non-SMP part below. We basically do + * the same on SMP configurations. The fact that we may have more than one + * executing thread and each thread queue has its own SMP lock makes the task + * a bit more difficult. We have to avoid deadlocks at SMP lock level, since + * this would result in an unrecoverable deadlock of the overall system. + */ + + _Chain_Initialize_empty( &path->Links ); + _Chain_Initialize_node( &path->Start.Path_node ); + _Thread_queue_Context_initialize( &path->Start.Queue_context ); owner = queue->owner; if ( owner == NULL ) { - return; + return true; + } + + if ( owner == the_thread ) { + return false; } link = &path->Start; - link->owner = owner; - _Thread_Wait_acquire_default_critical( - owner, - &link->Queue_context.Lock_context - ); + do { + _Chain_Append_unprotected( &path->Links, &link->Path_node ); + link->owner = owner; + + _Thread_Wait_acquire_default_critical( + owner, + &link->Queue_context.Lock_context + ); + + target = owner->Wait.queue; + link->Queue_context.Wait.queue = target; + link->Queue_context.Wait.operations = owner->Wait.operations; + + if ( target != NULL ) { + if ( _Thread_queue_Link_add( link, queue, target ) ) { + link->Queue_context.Wait.queue_lock = &target->Lock; + _Chain_Append_unprotected( + &owner->Wait.Lock.Pending_requests, + &link->Queue_context.Wait.Gate.Node + ); + _Thread_Wait_release_default_critical( + owner, + &link->Queue_context.Lock_context + ); + _Thread_Wait_acquire_queue_critical( + &target->Lock, + &link->Queue_context + ); + + if ( link->Queue_context.Wait.queue == NULL ) { + return true; + } + } else { + link->Queue_context.Wait.queue_lock = NULL; + _Thread_queue_Path_release( path ); + return false; + } + } else { + link->Queue_context.Wait.queue_lock = NULL; + return true; + } + + link = &owner->Wait.Link; + queue = target; + owner = queue->owner; + } while ( owner != NULL ); #else - (void) the_thread; - (void) queue; - (void) path; + do { + owner = queue->owner; + + if ( owner == NULL ) { + return true; + } + + if ( owner == the_thread ) { + return false; + } + + queue = owner->Wait.queue; + } while ( queue != NULL ); #endif + + return true; +} + +void _Thread_queue_Deadlock_status( Thread_Control *the_thread ) +{ + the_thread->Wait.return_code = STATUS_DEADLOCK; +} + +void _Thread_queue_Deadlock_fatal( Thread_Control *the_thread ) +{ + _Terminate( + INTERNAL_ERROR_CORE, + false, + INTERNAL_ERROR_THREAD_QUEUE_DEADLOCK + ); } void _Thread_queue_Enqueue_critical( @@ -99,8 +327,15 @@ void _Thread_queue_Enqueue_critical( _Thread_Wait_claim( the_thread, queue, operations ); - _Thread_queue_Path_acquire( the_thread, queue, &path ); + if ( !_Thread_queue_Path_acquire( the_thread, queue, &path ) ) { + _Thread_Wait_restore_default( the_thread ); + _Thread_queue_Queue_release( queue, &queue_context->Lock_context ); + ( *queue_context->deadlock_callout )( the_thread ); + return; + } + ( *operations->enqueue )( queue, the_thread, &path ); + _Thread_queue_Path_release( &path ); the_thread->Wait.return_code = STATUS_SUCCESSFUL; |