From aaaf9610db1a3cb0b01b86dc1a4f1e6b12f43126 Mon Sep 17 00:00:00 2001 From: Sebastian Huber Date: Mon, 8 Aug 2016 08:44:51 +0200 Subject: score: Add debug support to red-black trees This helps to detect double insert and extract errors. --- cpukit/libfs/src/jffs2/include/linux/rbtree.h | 1 + cpukit/posix/src/keysetspecific.c | 2 + cpukit/sapi/src/rbtreeinsert.c | 1 + cpukit/score/include/rtems/score/rbtree.h | 81 ++++++++++++++++----------- cpukit/score/src/rbtreeextract.c | 3 + cpukit/score/src/scheduleredfnodeinit.c | 1 + cpukit/score/src/threadinitialize.c | 1 + cpukit/score/src/threadmp.c | 1 + cpukit/score/src/threadqenqueue.c | 1 + cpukit/score/src/threadqops.c | 1 + cpukit/score/src/watchdoginsert.c | 1 + testsuites/sptests/sprbtree01/init.c | 1 - 12 files changed, 62 insertions(+), 33 deletions(-) diff --git a/cpukit/libfs/src/jffs2/include/linux/rbtree.h b/cpukit/libfs/src/jffs2/include/linux/rbtree.h index bbf285377a..2268434939 100644 --- a/cpukit/libfs/src/jffs2/include/linux/rbtree.h +++ b/cpukit/libfs/src/jffs2/include/linux/rbtree.h @@ -117,6 +117,7 @@ static inline void rb_link_node( struct rb_node **link ) { + _RBTree_Initialize_node( (RBTree_Node *) node ); _RBTree_Add_child( (RBTree_Node *) node, (RBTree_Node *) parent, diff --git a/cpukit/posix/src/keysetspecific.c b/cpukit/posix/src/keysetspecific.c index 7ccef1fdb9..391dc85b2d 100644 --- a/cpukit/posix/src/keysetspecific.c +++ b/cpukit/posix/src/keysetspecific.c @@ -57,6 +57,8 @@ static int _POSIX_Keys_Create_value( key_value_pair->thread = executing; key_value_pair->value = RTEMS_DECONST( void *, value ); + _RBTree_Initialize_node( &key_value_pair->Lookup_node ); + _Chain_Initialize_node( &key_value_pair->Key_node ); _Chain_Append_unprotected( &the_key->Key_value_pairs, diff --git a/cpukit/sapi/src/rbtreeinsert.c b/cpukit/sapi/src/rbtreeinsert.c index 38b2f5b4ca..db55e4358b 100644 --- a/cpukit/sapi/src/rbtreeinsert.c +++ b/cpukit/sapi/src/rbtreeinsert.c @@ -50,6 +50,7 @@ rtems_rbtree_node *rtems_rbtree_insert( } } + _RBTree_Initialize_node( the_node ); _RBTree_Add_child( the_node, parent, which ); _RBTree_Insert_color( the_rbtree, the_node ); diff --git a/cpukit/score/include/rtems/score/rbtree.h b/cpukit/score/include/rtems/score/rbtree.h index e7e65f7b91..e94560ea88 100644 --- a/cpukit/score/include/rtems/score/rbtree.h +++ b/cpukit/score/include/rtems/score/rbtree.h @@ -20,6 +20,7 @@ #include #include +#include #ifdef __cplusplus extern "C" { @@ -68,6 +69,38 @@ typedef RB_HEAD(RBTree_Control, RBTree_Node) RBTree_Control; #define RBTREE_DEFINE_EMPTY( name ) \ RBTree_Control name = RBTREE_INITIALIZER_EMPTY( name ) +/** + * @brief Sets a red-black tree node as off-tree. + * + * Do not use this function on nodes which are a part of a tree. + * + * @param[in] the_node The node to set off-tree. + * + * @see _RBTree_Is_node_off_tree(). + */ +RTEMS_INLINE_ROUTINE void _RBTree_Set_off_tree( RBTree_Node *the_node ) +{ + RB_COLOR( the_node, Node ) = -1; +} + +/** + * @brief Returns true, if this red-black tree node is off-tree, and false + * otherwise. + * + * @param[in] the_node The node to test. + * + * @retval true The node is not a part of a tree (off-tree). + * @retval false Otherwise. + * + * @see _RBTree_Set_off_tree(). + */ +RTEMS_INLINE_ROUTINE bool _RBTree_Is_node_off_tree( + const RBTree_Node *the_node +) +{ + return RB_COLOR( the_node, Node ) == -1; +} + /** * @brief Rebalances the red-black tree after insertion of the node. * @@ -79,6 +112,21 @@ void _RBTree_Insert_color( RBTree_Node *the_node ); +/** + * @brief Initializes a red-black tree node. + * + * In debug configurations, the node is set off tree. In all other + * configurations, this function does nothing. + * + * @param[in] the_node The red-black tree node to initialize. + */ +RTEMS_INLINE_ROUTINE void _RBTree_Initialize_node( RBTree_Node *the_node ) +{ +#if defined(RTEMS_DEBUG) + _RBTree_Set_off_tree( the_node ); +#endif +} + /** * @brief Adds a child node to a parent node. * @@ -92,6 +140,7 @@ RTEMS_INLINE_ROUTINE void _RBTree_Add_child( RBTree_Node **link ) { + _Assert( _RBTree_Is_node_off_tree( child ) ); RB_SET( child, parent, Node ); *link = child; } @@ -174,38 +223,6 @@ void _RBTree_Extract( RBTree_Node *the_node ); -/** - * @brief Sets a red-black tree node as off-tree. - * - * Do not use this function on nodes which are a part of a tree. - * - * @param[in] the_node The node to set off-tree. - * - * @see _RBTree_Is_node_off_tree(). - */ -RTEMS_INLINE_ROUTINE void _RBTree_Set_off_tree( RBTree_Node *the_node ) -{ - RB_COLOR( the_node, Node ) = -1; -} - -/** - * @brief Returns true, if this red-black tree node is off-tree, and false - * otherwise. - * - * @param[in] the_node The node to test. - * - * @retval true The node is not a part of a tree (off-tree). - * @retval false Otherwise. - * - * @see _RBTree_Set_off_tree(). - */ -RTEMS_INLINE_ROUTINE bool _RBTree_Is_node_off_tree( - const RBTree_Node *the_node -) -{ - return RB_COLOR( the_node, Node ) == -1; -} - /** * @brief Returns a pointer to root node of the red-black tree. * diff --git a/cpukit/score/src/rbtreeextract.c b/cpukit/score/src/rbtreeextract.c index 4d8a8f8eed..3905f64900 100644 --- a/cpukit/score/src/rbtreeextract.c +++ b/cpukit/score/src/rbtreeextract.c @@ -22,4 +22,7 @@ void _RBTree_Extract( ) { RB_REMOVE( RBTree_Control, the_rbtree, the_node ); +#if defined(RTEMS_DEBUG) + _RBTree_Set_off_tree( the_node ); +#endif } diff --git a/cpukit/score/src/scheduleredfnodeinit.c b/cpukit/score/src/scheduleredfnodeinit.c index bde25c18d7..d290bd74fd 100644 --- a/cpukit/score/src/scheduleredfnodeinit.c +++ b/cpukit/score/src/scheduleredfnodeinit.c @@ -35,4 +35,5 @@ void _Scheduler_EDF_Node_initialize( the_node = _Scheduler_EDF_Node_downcast( node ); the_node->thread = the_thread; + _RBTree_Initialize_node( &the_node->Node ); } diff --git a/cpukit/score/src/threadinitialize.c b/cpukit/score/src/threadinitialize.c index b5fef590fc..8b5d9431e5 100644 --- a/cpukit/score/src/threadinitialize.c +++ b/cpukit/score/src/threadinitialize.c @@ -187,6 +187,7 @@ bool _Thread_Initialize( "Thread Wait Default Lock" ); _Thread_queue_Gate_open( &the_thread->Wait.Lock.Tranquilizer ); + _RBTree_Initialize_node( &the_thread->Wait.Link.Registry_node ); _SMP_lock_Stats_initialize( &the_thread->Potpourri_stats, "Thread Potpourri" ); #endif diff --git a/cpukit/score/src/threadmp.c b/cpukit/score/src/threadmp.c index a991d03760..f5253560a6 100644 --- a/cpukit/score/src/threadmp.c +++ b/cpukit/score/src/threadmp.c @@ -72,6 +72,7 @@ void _Thread_MP_Handler_initialization ( proxy = (Thread_Proxy_control *) ( proxies + i * proxy_size ); _Thread_Timer_initialize( &proxy->Timer, _Per_CPU_Get_by_index( 0 ) ); + _RBTree_Initialize_node( &proxy->Active ); proxy->Wait.spare_heads = &proxy->Thread_queue_heads[ 0 ]; _Thread_queue_Heads_initialize( proxy->Wait.spare_heads ); diff --git a/cpukit/score/src/threadqenqueue.c b/cpukit/score/src/threadqenqueue.c index 54d3a42d9a..1897c6346f 100644 --- a/cpukit/score/src/threadqenqueue.c +++ b/cpukit/score/src/threadqenqueue.c @@ -251,6 +251,7 @@ static bool _Thread_queue_Path_acquire( return false; } + _RBTree_Initialize_node( &path->Start.Registry_node ); _Chain_Initialize_node( &path->Start.Path_node ); _Thread_queue_Context_initialize( &path->Start.Queue_context ); link = &path->Start; diff --git a/cpukit/score/src/threadqops.c b/cpukit/score/src/threadqops.c index d6e42fda8f..df7054f0c8 100644 --- a/cpukit/score/src/threadqops.c +++ b/cpukit/score/src/threadqops.c @@ -242,6 +242,7 @@ static void _Thread_queue_Priority_do_enqueue( #endif current_priority = the_thread->current_priority; + _RBTree_Initialize_node( &the_thread->Wait.Node.RBTree ); _RBTree_Insert_inline( &priority_queue->Queue, &the_thread->Wait.Node.RBTree, diff --git a/cpukit/score/src/watchdoginsert.c b/cpukit/score/src/watchdoginsert.c index 22fc7a5f76..b9f5eb88fb 100644 --- a/cpukit/score/src/watchdoginsert.c +++ b/cpukit/score/src/watchdoginsert.c @@ -60,6 +60,7 @@ void _Watchdog_Insert( } header->first = new_first; + _RBTree_Initialize_node( &the_watchdog->Node.RBTree ); _RBTree_Add_child( &the_watchdog->Node.RBTree, parent, link ); _RBTree_Insert_color( &header->Watchdogs, &the_watchdog->Node.RBTree ); } diff --git a/testsuites/sptests/sprbtree01/init.c b/testsuites/sptests/sprbtree01/init.c index c58c6d56af..fd3737ced5 100644 --- a/testsuites/sptests/sprbtree01/init.c +++ b/testsuites/sptests/sprbtree01/init.c @@ -1801,7 +1801,6 @@ rtems_task Init( rtems_task_argument ignored ) puts( "INIT - rtems_rbtree_extract failed"); rtems_test_exit(0); } - rtems_test_assert( !rtems_rbtree_is_node_off_tree( p ) ); rb_insert_unique(&rbtree1, p); for ( p = rtems_rbtree_get_min(&rbtree1), id = 1 ; p ; -- cgit v1.2.3