[rtems commit] score: Add debug support to red-black trees
Sebastian Huber
sebh at rtems.org
Mon Aug 8 07:36:13 UTC 2016
Module: rtems
Branch: master
Commit: aaaf9610db1a3cb0b01b86dc1a4f1e6b12f43126
Changeset: http://git.rtems.org/rtems/commit/?id=aaaf9610db1a3cb0b01b86dc1a4f1e6b12f43126
Author: Sebastian Huber <sebastian.huber at embedded-brains.de>
Date: Mon Aug 8 08:44:51 2016 +0200
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 bbf2853..2268434 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 7ccef1f..391dc85 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 38b2f5b..db55e43 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 e7e65f7..e94560e 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 4d8a8f8..3905f64 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 bde25c1..d290bd7 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 b5fef59..8b5d943 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 a991d03..f525356 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 54d3a42..1897c63 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 d6e42fd..df7054f 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 22fc7a5..b9f5eb8 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 c58c6d5..fd3737c 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 ;
More information about the vc
mailing list