score: Add debug support to red-black trees

This helps to detect double insert and extract errors.

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 <sys/tree.h>
 #include <rtems/score/basedefs.h>
+#include <rtems/score/assert.h>
 
 #ifdef __cplusplus
 extern "C" {
@@ -69,6 +70,38 @@ typedef RB_HEAD(RBTree_Control, RBTree_Node) RBTree_Control;
   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.
  *
  * @param[in] the_rbtree The red-black tree control.
@@ -80,6 +113,21 @@ void _RBTree_Insert_color(
 );
 
 /**
+ * @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.
  *
  * @param[in] child The child 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;
 }
@@ -175,38 +224,6 @@ void _RBTree_Extract(
 );
 
 /**
- * @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.
  *
  * The root node may change after insert or extract operations.
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 ;