[PATCH 2/6] score: Add red-black tree node to Scheduler_Node
Sebastian Huber
sebastian.huber at embedded-brains.de
Thu Jun 29 13:23:14 UTC 2017
In SMP configurations, add a red-black tree node to Scheduler_Node to
enable an EDF scheduler implementation.
Update #3056.
---
cpukit/score/include/rtems/score/schedulernode.h | 14 ++++++++------
.../include/rtems/score/schedulerprioritysmpimpl.h | 14 +++++++-------
cpukit/score/include/rtems/score/schedulersmpimpl.h | 18 +++++++++---------
cpukit/score/src/schedulerpriorityaffinitysmp.c | 8 +++++++-
cpukit/score/src/schedulersimplesmp.c | 16 ++++++++--------
cpukit/score/src/schedulersmpstartidle.c | 2 +-
cpukit/score/src/schedulerstrongapa.c | 14 +++++++-------
7 files changed, 47 insertions(+), 39 deletions(-)
diff --git a/cpukit/score/include/rtems/score/schedulernode.h b/cpukit/score/include/rtems/score/schedulernode.h
index 09d03d4e59..1474b0c13c 100644
--- a/cpukit/score/include/rtems/score/schedulernode.h
+++ b/cpukit/score/include/rtems/score/schedulernode.h
@@ -67,14 +67,16 @@ struct Scheduler_Node {
/**
* @brief Chain node for usage in various scheduler data structures.
*
- * Strictly this is the wrong place for this field since the data structures
+ * Strictly, this is the wrong place for this field since the data structures
* to manage scheduler nodes belong to the particular scheduler
- * implementation. Currently all SMP scheduler implementations use chains.
- * The node is here to simplify things, just like the object node in the
- * thread control block. It may be replaced with a union to add a red-black
- * tree node in the future.
+ * implementation. Currently, all SMP scheduler implementations use chains
+ * or red-black trees. The node is here to simplify things, just like the
+ * object node in the thread control block.
*/
- Chain_Node Node;
+ union {
+ Chain_Node Chain;
+ RBTree_Node RBTree;
+ } Node;
/**
* @brief The sticky level determines if this scheduler node should use an
diff --git a/cpukit/score/include/rtems/score/schedulerprioritysmpimpl.h b/cpukit/score/include/rtems/score/schedulerprioritysmpimpl.h
index 5136565bbe..f37414c7a8 100644
--- a/cpukit/score/include/rtems/score/schedulerprioritysmpimpl.h
+++ b/cpukit/score/include/rtems/score/schedulerprioritysmpimpl.h
@@ -75,9 +75,9 @@ static inline void _Scheduler_priority_SMP_Move_from_scheduled_to_ready(
Scheduler_priority_SMP_Node *node =
_Scheduler_priority_SMP_Node_downcast( scheduled_to_ready );
- _Chain_Extract_unprotected( &node->Base.Base.Node );
+ _Chain_Extract_unprotected( &node->Base.Base.Node.Chain );
_Scheduler_priority_Ready_queue_enqueue_first(
- &node->Base.Base.Node,
+ &node->Base.Base.Node.Chain,
&node->Ready_queue,
&self->Bit_map
);
@@ -94,13 +94,13 @@ static inline void _Scheduler_priority_SMP_Move_from_ready_to_scheduled(
_Scheduler_priority_SMP_Node_downcast( ready_to_scheduled );
_Scheduler_priority_Ready_queue_extract(
- &node->Base.Base.Node,
+ &node->Base.Base.Node.Chain,
&node->Ready_queue,
&self->Bit_map
);
_Chain_Insert_ordered_unprotected(
&self->Base.Scheduled,
- &node->Base.Base.Node,
+ &node->Base.Base.Node.Chain,
_Scheduler_SMP_Insert_priority_fifo_order
);
}
@@ -116,7 +116,7 @@ static inline void _Scheduler_priority_SMP_Insert_ready_lifo(
_Scheduler_priority_SMP_Node_downcast( thread );
_Scheduler_priority_Ready_queue_enqueue(
- &node->Base.Base.Node,
+ &node->Base.Base.Node.Chain,
&node->Ready_queue,
&self->Bit_map
);
@@ -133,7 +133,7 @@ static inline void _Scheduler_priority_SMP_Insert_ready_fifo(
_Scheduler_priority_SMP_Node_downcast( thread );
_Scheduler_priority_Ready_queue_enqueue_first(
- &node->Base.Base.Node,
+ &node->Base.Base.Node.Chain,
&node->Ready_queue,
&self->Bit_map
);
@@ -150,7 +150,7 @@ static inline void _Scheduler_priority_SMP_Extract_from_ready(
_Scheduler_priority_SMP_Node_downcast( thread );
_Scheduler_priority_Ready_queue_extract(
- &node->Base.Base.Node,
+ &node->Base.Base.Node.Chain,
&node->Ready_queue,
&self->Bit_map
);
diff --git a/cpukit/score/include/rtems/score/schedulersmpimpl.h b/cpukit/score/include/rtems/score/schedulersmpimpl.h
index d91a62c3ca..b90c359d4c 100644
--- a/cpukit/score/include/rtems/score/schedulersmpimpl.h
+++ b/cpukit/score/include/rtems/score/schedulersmpimpl.h
@@ -608,9 +608,9 @@ static inline Scheduler_Node *_Scheduler_SMP_Get_lowest_scheduled(
(void) filter;
(void) order;
- _Assert( &lowest_scheduled->Node != _Chain_Tail( scheduled ) );
+ _Assert( &lowest_scheduled->Node.Chain != _Chain_Tail( scheduled ) );
_Assert(
- _Chain_Next( &lowest_scheduled->Node ) == _Chain_Tail( scheduled )
+ _Chain_Next( &lowest_scheduled->Node.Chain ) == _Chain_Tail( scheduled )
);
return lowest_scheduled;
@@ -708,7 +708,7 @@ static inline bool _Scheduler_SMP_Enqueue_ordered(
lowest_scheduled = ( *get_lowest_scheduled )( context, node, order );
- if ( ( *order )( &node->Node, &lowest_scheduled->Node ) ) {
+ if ( ( *order )( &node->Node.Chain, &lowest_scheduled->Node.Chain ) ) {
_Scheduler_SMP_Enqueue_to_scheduled(
context,
node,
@@ -769,7 +769,7 @@ static inline bool _Scheduler_SMP_Enqueue_scheduled_ordered(
*/
if (
node->sticky_level > 0
- && ( *order )( &node->Node, &highest_ready->Node )
+ && ( *order )( &node->Node.Chain, &highest_ready->Node.Chain )
) {
( *insert_scheduled )( context, node );
@@ -859,7 +859,7 @@ static inline void _Scheduler_SMP_Extract_from_scheduled(
Scheduler_Node *node
)
{
- _Chain_Extract_unprotected( &node->Node );
+ _Chain_Extract_unprotected( &node->Node.Chain );
}
static inline void _Scheduler_SMP_Schedule_highest_ready(
@@ -1109,7 +1109,7 @@ static inline void _Scheduler_SMP_Insert_scheduled_lifo(
_Chain_Insert_ordered_unprotected(
&self->Scheduled,
- &node_to_insert->Node,
+ &node_to_insert->Node.Chain,
_Scheduler_SMP_Insert_priority_lifo_order
);
}
@@ -1123,7 +1123,7 @@ static inline void _Scheduler_SMP_Insert_scheduled_fifo(
_Chain_Insert_ordered_unprotected(
&self->Scheduled,
- &node_to_insert->Node,
+ &node_to_insert->Node.Chain,
_Scheduler_SMP_Insert_priority_fifo_order
);
}
@@ -1154,7 +1154,7 @@ static inline bool _Scheduler_SMP_Ask_for_help(
node_state = _Scheduler_SMP_Node_state( node );
if ( node_state == SCHEDULER_SMP_NODE_BLOCKED ) {
- if ( ( *order )( &node->Node, &lowest_scheduled->Node ) ) {
+ if ( ( *order )( &node->Node.Chain, &lowest_scheduled->Node.Chain ) ) {
_Thread_Scheduler_cancel_need_for_help(
thread,
_Thread_Get_CPU( thread )
@@ -1297,7 +1297,7 @@ static inline void _Scheduler_SMP_Add_processor(
if ( ( *has_ready )( &self->Base ) ) {
( *enqueue_scheduled_fifo )( &self->Base, node );
} else {
- _Chain_Append_unprotected( &self->Scheduled, &node->Node );
+ _Chain_Append_unprotected( &self->Scheduled, &node->Node.Chain );
}
}
diff --git a/cpukit/score/src/schedulerpriorityaffinitysmp.c b/cpukit/score/src/schedulerpriorityaffinitysmp.c
index 45afb571ef..1fa5dbf920 100644
--- a/cpukit/score/src/schedulerpriorityaffinitysmp.c
+++ b/cpukit/score/src/schedulerpriorityaffinitysmp.c
@@ -248,8 +248,14 @@ static Scheduler_Node * _Scheduler_priority_affinity_SMP_Get_lowest_scheduled(
* than filter thread is, then we can't schedule the filter thread
* to execute.
*/
- if ( (*order)( &node->Base.Base.Base.Node, &filter->Base.Base.Base.Node ) )
+ if (
+ (*order)(
+ &node->Base.Base.Base.Node.Chain,
+ &filter->Base.Base.Base.Node.Chain
+ )
+ ) {
break;
+ }
/* cpu_index is the processor number thread is executing on */
thread = _Scheduler_Node_get_owner( &node->Base.Base.Base );
diff --git a/cpukit/score/src/schedulersimplesmp.c b/cpukit/score/src/schedulersimplesmp.c
index 41eb491019..2884876381 100644
--- a/cpukit/score/src/schedulersimplesmp.c
+++ b/cpukit/score/src/schedulersimplesmp.c
@@ -88,7 +88,7 @@ static Scheduler_Node *_Scheduler_simple_SMP_Get_highest_ready(
(void) node;
- _Assert( &first->Node != _Chain_Tail( &self->Ready ) );
+ _Assert( &first->Node.Chain != _Chain_Tail( &self->Ready ) );
return first;
}
@@ -101,10 +101,10 @@ static void _Scheduler_simple_SMP_Move_from_scheduled_to_ready(
Scheduler_simple_SMP_Context *self =
_Scheduler_simple_SMP_Get_self( context );
- _Chain_Extract_unprotected( &scheduled_to_ready->Node );
+ _Chain_Extract_unprotected( &scheduled_to_ready->Node.Chain );
_Chain_Insert_ordered_unprotected(
&self->Ready,
- &scheduled_to_ready->Node,
+ &scheduled_to_ready->Node.Chain,
_Scheduler_SMP_Insert_priority_lifo_order
);
}
@@ -117,10 +117,10 @@ static void _Scheduler_simple_SMP_Move_from_ready_to_scheduled(
Scheduler_simple_SMP_Context *self =
_Scheduler_simple_SMP_Get_self( context );
- _Chain_Extract_unprotected( &ready_to_scheduled->Node );
+ _Chain_Extract_unprotected( &ready_to_scheduled->Node.Chain );
_Chain_Insert_ordered_unprotected(
&self->Base.Scheduled,
- &ready_to_scheduled->Node,
+ &ready_to_scheduled->Node.Chain,
_Scheduler_SMP_Insert_priority_fifo_order
);
}
@@ -135,7 +135,7 @@ static void _Scheduler_simple_SMP_Insert_ready_lifo(
_Chain_Insert_ordered_unprotected(
&self->Ready,
- &node_to_insert->Node,
+ &node_to_insert->Node.Chain,
_Scheduler_SMP_Insert_priority_lifo_order
);
}
@@ -150,7 +150,7 @@ static void _Scheduler_simple_SMP_Insert_ready_fifo(
_Chain_Insert_ordered_unprotected(
&self->Ready,
- &node_to_insert->Node,
+ &node_to_insert->Node.Chain,
_Scheduler_SMP_Insert_priority_fifo_order
);
}
@@ -162,7 +162,7 @@ static void _Scheduler_simple_SMP_Extract_from_ready(
{
(void) context;
- _Chain_Extract_unprotected( &node_to_extract->Node );
+ _Chain_Extract_unprotected( &node_to_extract->Node.Chain );
}
void _Scheduler_simple_SMP_Block(
diff --git a/cpukit/score/src/schedulersmpstartidle.c b/cpukit/score/src/schedulersmpstartidle.c
index d34ba12a43..d396a159fe 100644
--- a/cpukit/score/src/schedulersmpstartidle.c
+++ b/cpukit/score/src/schedulersmpstartidle.c
@@ -30,6 +30,6 @@ void _Scheduler_SMP_Start_idle(
node->state = SCHEDULER_SMP_NODE_SCHEDULED;
_Thread_Set_CPU( idle, cpu );
- _Chain_Append_unprotected( &self->Scheduled, &node->Base.Node );
+ _Chain_Append_unprotected( &self->Scheduled, &node->Base.Node.Chain );
_Scheduler_SMP_Release_idle_thread( &self->Base, idle );
}
diff --git a/cpukit/score/src/schedulerstrongapa.c b/cpukit/score/src/schedulerstrongapa.c
index d8d3280ed9..f6313584f6 100644
--- a/cpukit/score/src/schedulerstrongapa.c
+++ b/cpukit/score/src/schedulerstrongapa.c
@@ -51,9 +51,9 @@ static void _Scheduler_strong_APA_Move_from_scheduled_to_ready(
Scheduler_strong_APA_Node *node =
_Scheduler_strong_APA_Node_downcast( scheduled_to_ready );
- _Chain_Extract_unprotected( &node->Base.Base.Node );
+ _Chain_Extract_unprotected( &node->Base.Base.Node.Chain );
_Scheduler_priority_Ready_queue_enqueue_first(
- &node->Base.Base.Node,
+ &node->Base.Base.Node.Chain,
&node->Ready_queue,
&self->Bit_map
);
@@ -70,13 +70,13 @@ static void _Scheduler_strong_APA_Move_from_ready_to_scheduled(
_Scheduler_strong_APA_Node_downcast( ready_to_scheduled );
_Scheduler_priority_Ready_queue_extract(
- &node->Base.Base.Node,
+ &node->Base.Base.Node.Chain,
&node->Ready_queue,
&self->Bit_map
);
_Chain_Insert_ordered_unprotected(
&self->Base.Scheduled,
- &node->Base.Base.Node,
+ &node->Base.Base.Node.Chain,
_Scheduler_SMP_Insert_priority_fifo_order
);
}
@@ -92,7 +92,7 @@ static void _Scheduler_strong_APA_Insert_ready_lifo(
_Scheduler_strong_APA_Node_downcast( the_thread );
_Scheduler_priority_Ready_queue_enqueue(
- &node->Base.Base.Node,
+ &node->Base.Base.Node.Chain,
&node->Ready_queue,
&self->Bit_map
);
@@ -109,7 +109,7 @@ static void _Scheduler_strong_APA_Insert_ready_fifo(
_Scheduler_strong_APA_Node_downcast( the_thread );
_Scheduler_priority_Ready_queue_enqueue_first(
- &node->Base.Base.Node,
+ &node->Base.Base.Node.Chain,
&node->Ready_queue,
&self->Bit_map
);
@@ -126,7 +126,7 @@ static void _Scheduler_strong_APA_Extract_from_ready(
_Scheduler_strong_APA_Node_downcast( the_thread );
_Scheduler_priority_Ready_queue_extract(
- &node->Base.Base.Node,
+ &node->Base.Base.Node.Chain,
&node->Ready_queue,
&self->Bit_map
);
--
2.12.3
More information about the devel
mailing list