From 84f5c0a91be7b1ce9c4f1fb1f7afba680d5451aa Mon Sep 17 00:00:00 2001 From: Sebastian Huber Date: Mon, 4 Apr 2016 09:42:15 +0200 Subject: score: Use red-black tree for active global objects Use a red-black tree to lookup active global objects by identifier or name. Update #2555. --- cpukit/sapi/include/confdefs.h | 9 - cpukit/score/include/rtems/score/object.h | 46 ++- cpukit/score/include/rtems/score/objectimpl.h | 16 +- cpukit/score/include/rtems/score/objectmp.h | 45 +-- cpukit/score/src/objectget.c | 8 +- cpukit/score/src/objectgetisr.c | 8 +- cpukit/score/src/objectinitializeinformation.c | 18 +- cpukit/score/src/objectmp.c | 375 ++++++++++++++++--------- testsuites/sptests/spsize/size.c | 5 - 9 files changed, 317 insertions(+), 213 deletions(-) diff --git a/cpukit/sapi/include/confdefs.h b/cpukit/sapi/include/confdefs.h index 2018c4eb64..e0b2a8058f 100644 --- a/cpukit/sapi/include/confdefs.h +++ b/cpukit/sapi/include/confdefs.h @@ -2964,17 +2964,8 @@ extern rtems_initialization_tasks_table Initialization_tasks[]; * This is an internal parameter. */ #ifdef CONFIGURE_MP_APPLICATION - #define CONFIGURE_OBJECT_GLOBAL_TABLE_SIZE(_max) \ - _Configure_From_workspace( \ - (CONFIGURE_MP_MAXIMUM_NODES + 1) * sizeof(Chain_Control) \ - ) - #define CONFIGURE_MEMORY_FOR_MP \ (CONFIGURE_MEMORY_FOR_PROXIES(CONFIGURE_MP_MAXIMUM_PROXIES) + \ - CONFIGURE_OBJECT_GLOBAL_TABLE_SIZE(CONFIGURE_TASKS) + \ - CONFIGURE_OBJECT_GLOBAL_TABLE_SIZE(CONFIGURE_MAXIMUM_PARTITIONS) + \ - CONFIGURE_OBJECT_GLOBAL_TABLE_SIZE(CONFIGURE_SEMAPHORES) + \ - CONFIGURE_OBJECT_GLOBAL_TABLE_SIZE(CONFIGURE_MAXIMUM_MESSAGE_QUEUES) + \ CONFIGURE_MEMORY_FOR_GLOBAL_OBJECTS(CONFIGURE_MP_MAXIMUM_GLOBAL_OBJECTS)) #else #define CONFIGURE_MEMORY_FOR_MP 0 diff --git a/cpukit/score/include/rtems/score/object.h b/cpukit/score/include/rtems/score/object.h index 70e5fe630c..c2acb2dbaa 100644 --- a/cpukit/score/include/rtems/score/object.h +++ b/cpukit/score/include/rtems/score/object.h @@ -23,6 +23,7 @@ #include #include #include +#include #ifdef __cplusplus extern "C" { @@ -240,18 +241,45 @@ typedef struct { #if defined( RTEMS_MULTIPROCESSING ) /** - * This defines the Global Object Control Block used to manage - * objects resident on other nodes. It is derived from Object. + * @brief This defines the Global Object Control Block used to manage objects + * resident on other nodes. */ typedef struct { - /** This is an object control structure. */ - Objects_Control Object; - /** This is the name of the object. Using an unsigned thirty two - * bit value is broken but works. If any API is MP with variable - * length names .. BOOM!!!! + /** + * @brief Nodes to manage active and inactive global objects. + */ + union { + /** + * @brief Inactive global objects reside on a chain. + */ + Chain_Node Inactive; + + struct { + /** + * @brief Node to lookup an active global object by identifier. + */ + RBTree_Node Id_lookup; + + /** + * @brief Node to lookup an active global object by name. + */ + RBTree_Node Name_lookup; + } Active; + } Nodes; + + /** + * @brief The global object identifier. + */ + Objects_Id id; + + /** + * @brief The global object name. + * + * Using an unsigned thirty two bit value is broken but works. If any API is + * MP with variable length names .. BOOM!!!! */ - uint32_t name; -} Objects_MP_Control; + uint32_t name; +} Objects_MP_Control; #endif /** diff --git a/cpukit/score/include/rtems/score/objectimpl.h b/cpukit/score/include/rtems/score/objectimpl.h index 786910e2e6..aed7fafad2 100644 --- a/cpukit/score/include/rtems/score/objectimpl.h +++ b/cpukit/score/include/rtems/score/objectimpl.h @@ -172,8 +172,20 @@ typedef struct { #if defined(RTEMS_MULTIPROCESSING) /** This is this object class' method called when extracting a thread. */ Objects_Thread_queue_Extract_callout extract; - /** This is this object class' pointer to the global name table */ - Chain_Control *global_table; + + /** + * @brief The global objects of this object information sorted by object + * identifier. + */ + RBTree_Control Global_by_id; + + /** + * @brief The global objects of this object information sorted by object + * name. + * + * Objects with the same name are sorted according to their identifier. + */ + RBTree_Control Global_by_name; #endif } Objects_Information; diff --git a/cpukit/score/include/rtems/score/objectmp.h b/cpukit/score/include/rtems/score/objectmp.h index a78ca82908..4f73012a04 100644 --- a/cpukit/score/include/rtems/score/objectmp.h +++ b/cpukit/score/include/rtems/score/objectmp.h @@ -147,27 +147,16 @@ Objects_Name_or_id_lookup_errors _Objects_MP_Global_name_search ( * @brief Searches the Global Object Table managed * by information for the object indicated by ID. * - * This function searches the Global Object Table managed - * by information for the object indicated by ID. If the object - * is found, then location is set to objects_remote, otherwise - * location is set to objects_error. In both cases, the_object - * is undefined. - * * @param[in] information points to the object information table for this * object class. * @param[in] the_id is the Id of the object being opened. - * @param[in] location will contain the location of the object. - * @param[in] the_object will contain a pointer to the object. * - * @retval This method fills in @a location to indicate successful location - * of the object or error. On success, @a the_object will be - * filled in. + * @retval OBJECTS_REMOTE A remote objects with this object identifier exits. + * @retval OBJECTS_ERROR Otherwise. */ -void _Objects_MP_Is_remote ( - Objects_Information *information, - Objects_Id the_id, - Objects_Locations *location, - Objects_Control **the_object +Objects_Locations _Objects_MP_Is_remote( + Objects_Information *information, + Objects_Id the_id ); /** @@ -175,37 +164,17 @@ void _Objects_MP_Is_remote ( */ extern uint32_t _Objects_MP_Maximum_global_objects; -/** - * The following chain header is used to manage the set of - * inactive global object control blocks. - */ -extern Chain_Control _Objects_MP_Inactive_global_objects; - /** * This function allocates a Global Object control block. */ -RTEMS_INLINE_ROUTINE Objects_MP_Control *_Objects_MP_Allocate_global_object ( - void -) -{ - return (Objects_MP_Control *) - _Chain_Get( &_Objects_MP_Inactive_global_objects ); -} +Objects_MP_Control *_Objects_MP_Allocate_global_object( void ); /** * This routine deallocates a Global Object control block. */ -RTEMS_INLINE_ROUTINE void _Objects_MP_Free_global_object ( - Objects_MP_Control *the_object -) -{ - _Chain_Append( - &_Objects_MP_Inactive_global_objects, - &the_object->Object.Node - ); -} +void _Objects_MP_Free_global_object( Objects_MP_Control *the_object ); /** * This function returns whether the global object is NULL or not. diff --git a/cpukit/score/src/objectget.c b/cpukit/score/src/objectget.c index 89fc59d607..276c96094c 100644 --- a/cpukit/score/src/objectget.c +++ b/cpukit/score/src/objectget.c @@ -69,12 +69,12 @@ Objects_Control *_Objects_Get( * it may be global in a multiprocessing system. But it is clearly * invalid on a single processor system. */ - *location = OBJECTS_ERROR; #if defined(RTEMS_MULTIPROCESSING) - _Objects_MP_Is_remote( information, id, location, &the_object ); - return the_object; + *location = _Objects_MP_Is_remote( information, id ); #else - return NULL; + *location = OBJECTS_ERROR; #endif + + return NULL; } diff --git a/cpukit/score/src/objectgetisr.c b/cpukit/score/src/objectgetisr.c index b1212ac9c7..3a185ce125 100644 --- a/cpukit/score/src/objectgetisr.c +++ b/cpukit/score/src/objectgetisr.c @@ -42,12 +42,12 @@ Objects_Control *_Objects_Get_isr_disable( *location = OBJECTS_ERROR; return NULL; } - *location = OBJECTS_ERROR; #if defined(RTEMS_MULTIPROCESSING) - _Objects_MP_Is_remote( information, id, location, &the_object ); - return the_object; + *location = _Objects_MP_Is_remote( information, id ); #else - return NULL; + *location = OBJECTS_ERROR; #endif + + return NULL; } diff --git a/cpukit/score/src/objectinitializeinformation.c b/cpukit/score/src/objectinitializeinformation.c index 3cd0c98af1..3149bb1df0 100644 --- a/cpukit/score/src/objectinitializeinformation.c +++ b/cpukit/score/src/objectinitializeinformation.c @@ -42,9 +42,6 @@ void _Objects_Initialize_information( static Objects_Control *null_local_table = NULL; uint32_t minimum_index; Objects_Maximum maximum_per_allocation; - #if defined(RTEMS_MULTIPROCESSING) - uint32_t index; - #endif information->the_api = the_api; information->the_class = the_class; @@ -131,18 +128,7 @@ void _Objects_Initialize_information( */ #if defined(RTEMS_MULTIPROCESSING) information->extract = extract; - - if ( (supports_global == true) && _System_state_Is_multiprocessing ) { - - information->global_table = - (Chain_Control *) _Workspace_Allocate_or_fatal_error( - (_Objects_Maximum_nodes + 1) * sizeof(Chain_Control) - ); - - for ( index=1; index <= _Objects_Maximum_nodes ; index++ ) - _Chain_Initialize_empty( &information->global_table[ index ] ); - } - else - information->global_table = NULL; + _RBTree_Initialize_empty( &information->Global_by_id ); + _RBTree_Initialize_empty( &information->Global_by_name ); #endif } diff --git a/cpukit/score/src/objectmp.c b/cpukit/score/src/objectmp.c index c8f431fa85..0df9190beb 100644 --- a/cpukit/score/src/objectmp.c +++ b/cpukit/score/src/objectmp.c @@ -20,17 +20,141 @@ #include #include -#include +#include #include #include +#define OBJECTS_MP_CONTROL_OF_ID_LOOKUP_NODE( node ) \ + RTEMS_CONTAINER_OF( node, Objects_MP_Control, Nodes.Active.Id_lookup ) + +#define OBJECTS_MP_CONTROL_OF_NAME_LOOKUP_NODE( node ) \ + RTEMS_CONTAINER_OF( node, Objects_MP_Control, Nodes.Active.Name_lookup ) + +typedef struct { + uint32_t name; + uint32_t node; +} Objects_MP_Name_and_node; + uint16_t _Objects_Local_node; uint16_t _Objects_Maximum_nodes; uint32_t _Objects_MP_Maximum_global_objects; -Chain_Control _Objects_MP_Inactive_global_objects; +static CHAIN_DEFINE_EMPTY( _Objects_MP_Inactive_global_objects ); + +ISR_LOCK_DEFINE( static, _Objects_MP_Global_lock, "MP Objects" ) + +static void _Objects_MP_Global_acquire( ISR_lock_Context *lock_context ) +{ + _ISR_lock_ISR_disable_and_acquire( &_Objects_MP_Global_lock, lock_context ); +} + +static void _Objects_MP_Global_release( ISR_lock_Context *lock_context ) +{ + _ISR_lock_Release_and_ISR_enable( &_Objects_MP_Global_lock, lock_context ); +} + +static bool _Objects_MP_Id_equal( + const void *left, + const RBTree_Node *right +) +{ + const Objects_Id *the_left; + const Objects_MP_Control *the_right; + + the_left = left; + the_right = OBJECTS_MP_CONTROL_OF_ID_LOOKUP_NODE( right ); + + return *the_left == the_right->id; +} + +static bool _Objects_MP_Id_less( + const void *left, + const RBTree_Node *right +) +{ + const Objects_Id *the_left; + const Objects_MP_Control *the_right; + + the_left = left; + the_right = OBJECTS_MP_CONTROL_OF_ID_LOOKUP_NODE( right ); + + return *the_left < the_right->id; +} + +static void *_Objects_MP_Id_map( RBTree_Node *node ) +{ + return OBJECTS_MP_CONTROL_OF_ID_LOOKUP_NODE( node ); +} + +static bool _Objects_MP_Name_equal( + const void *left, + const RBTree_Node *right +) +{ + const uint32_t *the_left; + const Objects_MP_Control *the_right; + + the_left = left; + the_right = OBJECTS_MP_CONTROL_OF_NAME_LOOKUP_NODE( right ); + + return *the_left == the_right->name; +} + +static bool _Objects_MP_Name_less( + const void *left, + const RBTree_Node *right +) +{ + const uint32_t *the_left; + const Objects_MP_Control *the_right; + + the_left = left; + the_right = OBJECTS_MP_CONTROL_OF_NAME_LOOKUP_NODE( right ); + + return *the_left < the_right->name; +} + +static void *_Objects_MP_Name_map( RBTree_Node *node ) +{ + return OBJECTS_MP_CONTROL_OF_NAME_LOOKUP_NODE( node ); +} + +static bool _Objects_MP_Name_and_node_equal( + const void *left, + const RBTree_Node *right +) +{ + const Objects_MP_Name_and_node *the_left; + const Objects_MP_Control *the_right; + + the_left = left; + the_right = OBJECTS_MP_CONTROL_OF_NAME_LOOKUP_NODE( right ); + + return the_left->name == the_right->name + && the_left->node == _Objects_Get_node( the_right->id ); +} + +static bool _Objects_MP_Name_and_node_less( + const void *left, + const RBTree_Node *right +) +{ + const Objects_MP_Name_and_node *the_left; + const Objects_MP_Control *the_right; + + the_left = left; + the_right = OBJECTS_MP_CONTROL_OF_NAME_LOOKUP_NODE( right ); + + /* + * Use > for the node to find smaller numbered nodes first in case of equal + * names. + */ + return the_left->name < the_right->name + || ( the_left->name == the_right->name + && the_left->node > _Objects_Get_node( the_right->id ) ); +} void _Objects_MP_Handler_early_initialization(void) { @@ -51,22 +175,15 @@ void _Objects_MP_Handler_early_initialization(void) _Objects_Maximum_nodes = maximum_nodes; } -/* - * _Objects_MP_Handler_initialization - * - */ - -void _Objects_MP_Handler_initialization(void) +void _Objects_MP_Handler_initialization( void ) { - - uint32_t maximum_global_objects; + uint32_t maximum_global_objects; maximum_global_objects = _Configuration_MP_table->maximum_global_objects; _Objects_MP_Maximum_global_objects = maximum_global_objects; if ( maximum_global_objects == 0 ) { - _Chain_Initialize_empty( &_Objects_MP_Inactive_global_objects ); return; } @@ -78,7 +195,6 @@ void _Objects_MP_Handler_initialization(void) maximum_global_objects, sizeof( Objects_MP_Control ) ); - } void _Objects_MP_Open ( @@ -88,16 +204,31 @@ void _Objects_MP_Open ( Objects_Id the_id ) { - the_global_object->Object.id = the_id; - the_global_object->name = the_name; + Objects_MP_Name_and_node name_and_node; + ISR_lock_Context lock_context; - _Assert( _Objects_Allocator_is_owner() ); + the_global_object->id = the_id; + the_global_object->name = the_name; - _Chain_Prepend_unprotected( - &information->global_table[ _Objects_Get_node( the_id ) ], - &the_global_object->Object.Node + name_and_node.name = the_name; + name_and_node.node = _Objects_Get_node( the_id ); + + _Objects_MP_Global_acquire( &lock_context ); + + _RBTree_Insert_inline( + &information->Global_by_id, + &the_global_object->Nodes.Active.Id_lookup, + &the_id, + _Objects_MP_Id_less + ); + _RBTree_Insert_inline( + &information->Global_by_name, + &the_global_object->Nodes.Active.Name_lookup, + &name_and_node, + _Objects_MP_Name_and_node_less ); + _Objects_MP_Global_release( &lock_context ); } bool _Objects_MP_Allocate_and_open ( @@ -133,152 +264,144 @@ void _Objects_MP_Close ( Objects_Id the_id ) { - Chain_Control *the_chain; - Chain_Node *the_node; - Objects_MP_Control *the_object; - - _Assert( _Objects_Allocator_is_owner() ); - - the_chain = &information->global_table[ _Objects_Get_node( the_id ) ]; - - for ( the_node = _Chain_First( the_chain ) ; - !_Chain_Is_tail( the_chain, the_node ) ; - the_node = _Chain_Next( the_node ) ) { + Objects_MP_Control *the_global_object; + ISR_lock_Context lock_context; - the_object = (Objects_MP_Control *) the_node; + _Objects_MP_Global_acquire( &lock_context ); - if ( _Objects_Are_ids_equal( the_object->Object.id, the_id ) ) { + the_global_object = _RBTree_Find_inline( + &information->Global_by_id, + &the_id, + _Objects_MP_Id_equal, + _Objects_MP_Id_less, + _Objects_MP_Id_map + ); - _Chain_Extract_unprotected( the_node ); - _Objects_MP_Free_global_object( the_object ); - return; - } + if ( the_global_object != NULL ) { + _RBTree_Extract( + &information->Global_by_id, + &the_global_object->Nodes.Active.Id_lookup + ); + _RBTree_Extract( + &information->Global_by_name, + &the_global_object->Nodes.Active.Name_lookup + ); + _Objects_MP_Free_global_object( the_global_object ); + _Objects_MP_Global_release( &lock_context ); + } else { + _Objects_MP_Global_release( &lock_context ); + _Terminate( + INTERNAL_ERROR_CORE, + true, + INTERNAL_ERROR_INVALID_GLOBAL_ID + ); } - - _Terminate( - INTERNAL_ERROR_CORE, - true, - INTERNAL_ERROR_INVALID_GLOBAL_ID - ); } -Objects_Name_or_id_lookup_errors _Objects_MP_Global_name_search ( +Objects_Name_or_id_lookup_errors _Objects_MP_Global_name_search( Objects_Information *information, Objects_Name the_name, uint32_t nodes_to_search, Objects_Id *the_id ) { - uint32_t low_node; - uint32_t high_node; - uint32_t node_index; - Chain_Control *the_chain; - Chain_Node *the_node; - Objects_MP_Control *the_object; - uint32_t name_to_use; + Objects_Name_or_id_lookup_errors status; + Objects_MP_Control *the_global_object; + ISR_lock_Context lock_context; - name_to_use = the_name.name_u32; /* XXX only fixed length names */ - - if ( nodes_to_search > _Objects_Maximum_nodes ) + if ( nodes_to_search > _Objects_Maximum_nodes ) { return OBJECTS_INVALID_NODE; - - if ( information->global_table == NULL ) - return OBJECTS_INVALID_NAME; - - if ( nodes_to_search == OBJECTS_SEARCH_ALL_NODES || - nodes_to_search == OBJECTS_SEARCH_OTHER_NODES ) { - low_node = 1; - high_node = _Objects_Maximum_nodes; - } else { - low_node = - high_node = nodes_to_search; } - _Objects_Allocator_lock(); - - for ( node_index = low_node ; node_index <= high_node ; node_index++ ) { + _Objects_MP_Global_acquire( &lock_context ); - /* - * NOTE: The local node was search (if necessary) by - * _Objects_Name_to_id_XXX before this was invoked. - */ - - if ( !_Objects_Is_local_node( node_index ) ) { - the_chain = &information->global_table[ node_index ]; + if ( nodes_to_search == OBJECTS_SEARCH_ALL_NODES ) { + the_global_object = _RBTree_Find_inline( + &information->Global_by_name, + &the_name.name_u32, + _Objects_MP_Name_equal, + _Objects_MP_Name_less, + _Objects_MP_Name_map + ); + } else { + Objects_MP_Name_and_node name_and_node; - for ( the_node = _Chain_First( the_chain ) ; - !_Chain_Is_tail( the_chain, the_node ) ; - the_node = _Chain_Next( the_node ) ) { + name_and_node.name = the_name.name_u32; + name_and_node.node = nodes_to_search; - the_object = (Objects_MP_Control *) the_node; + the_global_object = _RBTree_Find_inline( + &information->Global_by_name, + &name_and_node, + _Objects_MP_Name_and_node_equal, + _Objects_MP_Name_and_node_less, + _Objects_MP_Name_map + ); + } - if ( the_object->name == name_to_use ) { - *the_id = the_object->Object.id; - _Objects_Allocator_unlock(); - return OBJECTS_NAME_OR_ID_LOOKUP_SUCCESSFUL; - } - } - } + if ( the_global_object != NULL ) { + *the_id = the_global_object->id; + status = OBJECTS_NAME_OR_ID_LOOKUP_SUCCESSFUL; + } else { + status = OBJECTS_INVALID_NAME; } - _Objects_Allocator_unlock(); - return OBJECTS_INVALID_NAME; + _Objects_MP_Global_release( &lock_context ); + + return status; } -void _Objects_MP_Is_remote ( - Objects_Information *information, - Objects_Id the_id, - Objects_Locations *location, - Objects_Control **the_object +Objects_Locations _Objects_MP_Is_remote( + Objects_Information *information, + Objects_Id the_id ) { - uint32_t node; - Chain_Control *the_chain; - Chain_Node *the_node; Objects_MP_Control *the_global_object; + ISR_lock_Context lock_context; - node = _Objects_Get_node( the_id ); + _Objects_MP_Global_acquire( &lock_context ); - /* - * NOTE: The local node was search (if necessary) by - * _Objects_Name_to_id_XXX before this was invoked. - * - * The NODE field of an object id cannot be 0 - * because 0 is an invalid node number. - */ + the_global_object = _RBTree_Find_inline( + &information->Global_by_id, + &the_id, + _Objects_MP_Id_equal, + _Objects_MP_Id_less, + _Objects_MP_Id_map + ); - if ( node == 0 || - _Objects_Is_local_node( node ) || - node > _Objects_Maximum_nodes || - information->global_table == NULL ) { + _Objects_MP_Global_release( &lock_context ); - *location = OBJECTS_ERROR; - *the_object = NULL; - return; + if ( the_global_object != NULL ) { + return OBJECTS_REMOTE; + } else { + return OBJECTS_ERROR; } +} - _Objects_Allocator_lock(); +Objects_MP_Control *_Objects_MP_Allocate_global_object( void ) +{ + Objects_MP_Control *the_global_object; + ISR_lock_Context lock_context; - the_chain = &information->global_table[ node ]; + _Objects_MP_Global_acquire( &lock_context ); - for ( the_node = _Chain_First( the_chain ) ; - !_Chain_Is_tail( the_chain, the_node ) ; - the_node = _Chain_Next( the_node ) ) { + the_global_object = (Objects_MP_Control *) + _Chain_Get_unprotected( &_Objects_MP_Inactive_global_objects ); - the_global_object = (Objects_MP_Control *) the_node; + _Objects_MP_Global_release( &lock_context ); + return the_global_object; +} - if ( _Objects_Are_ids_equal( the_global_object->Object.id, the_id ) ) { - _Objects_Allocator_unlock(); - *location = OBJECTS_REMOTE; - *the_object = (Objects_Control *) the_global_object; - return; - } - } +void _Objects_MP_Free_global_object( Objects_MP_Control *the_global_object ) +{ + ISR_lock_Context lock_context; - _Objects_Allocator_unlock(); - *location = OBJECTS_ERROR; - *the_object = NULL; + _Objects_MP_Global_acquire( &lock_context ); -} + _Chain_Append_unprotected( + &_Objects_MP_Inactive_global_objects, + &the_global_object->Nodes.Inactive + ); + _Objects_MP_Global_release( &lock_context ); +} diff --git a/testsuites/sptests/spsize/size.c b/testsuites/sptests/spsize/size.c index 251ed36793..3414ec0c80 100644 --- a/testsuites/sptests/spsize/size.c +++ b/testsuites/sptests/spsize/size.c @@ -315,11 +315,6 @@ uninitialized = (sizeof _Objects_Maximum_nodes) + (sizeof _Objects_Information_table) + -#if defined(RTEMS_MULTIPROCESSING) -/*objectmp.h*/ (sizeof _Objects_MP_Maximum_global_objects) + - (sizeof _Objects_MP_Inactive_global_objects) + -#endif - /*options.h*/ 0 + /*partimpl.h*/ (sizeof _Partition_Information) + -- cgit v1.2.3