From 15dbc710b62084e101bd2a46b3faa1ddc7ee417e Mon Sep 17 00:00:00 2001 From: Sebastian Huber Date: Thu, 29 Jun 2017 09:44:16 +0200 Subject: score: Add red-black tree node to Scheduler_Node 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(-) (limited to 'cpukit/score') 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 ); -- cgit v1.2.3