On Fri, Apr 15, 2016 at 5:16 AM, Sebastian Huber
<sebastian.hu...@embedded-brains.de> wrote:
> Add a chain iterator for safe iteration of chains with concurrent node
> extraction.
> ---
> cpukit/score/include/rtems/score/chainimpl.h | 186
> +++++++++++++++++++++++++++
> testsuites/sptests/spchain/init.c | 119 +++++++++++++++++
> testsuites/sptests/spchain/spchain.doc | 6 +
> testsuites/sptests/spchain/spchain.scn | 5 +-
> 4 files changed, 314 insertions(+), 2 deletions(-)
>
> diff --git a/cpukit/score/include/rtems/score/chainimpl.h
> b/cpukit/score/include/rtems/score/chainimpl.h
> index ff66d46..6210ea5 100644
> --- a/cpukit/score/include/rtems/score/chainimpl.h
> +++ b/cpukit/score/include/rtems/score/chainimpl.h
> @@ -800,6 +800,192 @@ RTEMS_INLINE_ROUTINE void
> _Chain_Insert_ordered_unprotected(
> _Chain_Insert_unprotected( _Chain_Previous( next ), to_insert );
> }
>
> +/**
> + * @brief The chain iterator direction.
> + */
> +typedef enum {
> + /**
> + * @brief Iteration from head to tail.
> + */
> + CHAIN_ITERATOR_FORWARD,
> +
> + /**
> + * @brief Iteration from tail to head.
> + */
> + CHAIN_ITERATOR_BACKWARD
> +} Chain_Iterator_direction;
> +
> +/**
> + * @brief A chain iterator which is updated during node extraction if it is
> + * properly registered.
> + *
> + * @see _Chain_Iterator_initialize().
> + */
> +typedef struct {
> + /**
> + * @brief Node for registration.
> + *
> + * Used during _Chain_Iterator_initialize() and _Chain_Iterator_destroy().
> + */
> + Chain_Node Registry_node;
> +
> + /**
> + * @brief The direction of this iterator.
> + *
> + * Immutable after initialization via _Chain_Iterator_initialize().
> + */
> + Chain_Iterator_direction direction;
> +
> + /**
> + * @brief The current position of this iterator.
> + *
> + * The position is initialized via _Chain_Iterator_initialize(). It must
> be
> + * explicitly set after one valid iteration step, e.g. in case a next node
> in
> + * the iterator direction existed. It is updated through the registration
> in
> + * case a node is extracted via _Chain_Iterator_registry_update().
> + */
> + Chain_Node *position;
> +} Chain_Iterator;
> +
> +/**
> + * @brief A registry for chain iterators.
> + *
> + * Should be attached to a chain control to enable safe iteration through a
> + * chain in case of concurrent node extractions.
> + */
> +typedef struct {
> + Chain_Control Iterators;
> +} Chain_Iterator_registry;
> +
> +/**
> + * @brief Chain iterator registry initializer for static initialization.
> + *
> + * @param name The designator of the chain iterator registry.
> + */
> +#define CHAIN_ITERATOR_REGISTRY_INITIALIZER( name ) \
> + { CHAIN_INITIALIZER_EMPTY( name.Iterators ) }
> +
> +/**
> + * @brief Initializes a chain iterator registry.
> + */
> +RTEMS_INLINE_ROUTINE void _Chain_Iterator_registry_initialize(
> + Chain_Iterator_registry *the_registry
> +)
> +{
> + _Chain_Initialize_empty( &the_registry->Iterators );
> +}
> +
> +/**
> + * @brief Updates all iterators present in the chain iterator registry in
> case
> + * of a node extraction.
> + *
> + * Must be called before _Chain_Extract_unprotected().
> + */
> +RTEMS_INLINE_ROUTINE void _Chain_Iterator_registry_update(
> + Chain_Iterator_registry *the_registry,
> + Chain_Node *the_node_to_extract
> +)
> +{
> + Chain_Node *iter_node;
> + Chain_Node *iter_tail;
> +
> + iter_node = _Chain_Head( &the_registry->Iterators );
> + iter_tail = _Chain_Tail( &the_registry->Iterators );
> +
> + while ( ( iter_node = _Chain_Next( iter_node ) ) != iter_tail ) {
> + Chain_Iterator *iter;
> +
> + iter = (Chain_Iterator *) iter_node;
> +
> + if ( iter->position == the_node_to_extract ) {
> + if ( iter->direction == CHAIN_ITERATOR_FORWARD ) {
> + iter->position = _Chain_Previous( the_node_to_extract );
> + } else {
> + iter->position = _Chain_Next( the_node_to_extract );
> + }
> + }
> + }
> +}
Is there any reason not to make this function also do the extract?
Is linear search really the best thing to do here? I guess the
alternatives lead to something like RCU... I'm not opposed to the
linear search/simplicity of this approach, but the usage must be
documented clearly I think. Speaking of which, this function, like
other chain functions, is not thread-safe.
> +
> +/**
> + * @brief Initializes the chain iterator.
> + *
> + * @param the_chain The chain to iterate.
> + * @param the_registry The registry for the chain iterator.
> + * @param the_iterator The chain iterator to initialize.
> + * @param direction The iteration direction.
> + *
> + * @see _Chain_Iterator_next(), _Chain_Iterator_set_position() and
> + * Chain_Iterator_destroy().
> + */
> +RTEMS_INLINE_ROUTINE void _Chain_Iterator_initialize(
> + Chain_Control *the_chain,
> + Chain_Iterator_registry *the_registry,
> + Chain_Iterator *the_iterator,
> + Chain_Iterator_direction direction
> +)
> +{
> + _Chain_Append_unprotected(
> + &the_registry->Iterators,
> + &the_iterator->Registry_node
> + );
> +
> + the_iterator->direction = direction;
> +
> + if ( direction == CHAIN_ITERATOR_FORWARD ) {
> + the_iterator->position = _Chain_Head( the_chain );
> + } else {
> + the_iterator->position = _Chain_Tail( the_chain );
> + }
> +}
> +
> +/**
> + * @brief Returns the next node in the iterator direction.
> + *
> + * In case a next node exits, then the iterator should be updated via
typo, exists
> + * _Chain_Iterator_set_position() to start the next iteration step.
> + *
> + * @param the_iterator The chain iterator.
> + */
> +RTEMS_INLINE_ROUTINE Chain_Node *_Chain_Iterator_next(
> + Chain_Iterator *the_iterator
> +)
> +{
> + if ( the_iterator->direction == CHAIN_ITERATOR_FORWARD ) {
> + return _Chain_Next( the_iterator->position );
> + } else {
> + return _Chain_Previous( the_iterator->position );
> + }
> +}
> +
> +/**
> + * @brief Sets the iterator position.
> + *
> + * @param the_iterator The chain iterator.
> + * @param the_node The new iterator position.
> + */
> +RTEMS_INLINE_ROUTINE void _Chain_Iterator_set_position(
> + Chain_Iterator *the_iterator,
> + Chain_Node *the_node
> +)
> +{
> + the_iterator->position = the_node;
> +}
> +
> +/**
> + * @brief Destroys the iterator.
> + *
> + * Removes the iterator from its registry.
> + *
> + * @param the_iterator The chain iterator.
> + */
> +RTEMS_INLINE_ROUTINE void _Chain_Iterator_destroy(
> + Chain_Iterator *the_iterator
> +)
> +{
> + _Chain_Extract_unprotected( &the_iterator->Registry_node );
> +}
> +
> /** @} */
>
> #ifdef __cplusplus
> diff --git a/testsuites/sptests/spchain/init.c
> b/testsuites/sptests/spchain/init.c
> index 476629b..dd46d68 100644
> --- a/testsuites/sptests/spchain/init.c
> +++ b/testsuites/sptests/spchain/init.c
> @@ -16,6 +16,124 @@
>
> const char rtems_test_name[] = "SPCHAIN";
>
> +static void update_registry_and_extract(
> + Chain_Iterator_registry *reg,
> + Chain_Node *n
> +)
> +{
> + _Chain_Iterator_registry_update( reg, n );
> + _Chain_Extract_unprotected( n );
> +}
> +
> +static Chain_Iterator_registry static_reg =
> + CHAIN_ITERATOR_REGISTRY_INITIALIZER( static_reg );
> +
> +static void test_chain_iterator( void )
> +{
> + Chain_Control chain;
> + Chain_Iterator_registry reg;
> + Chain_Iterator fit;
> + Chain_Iterator bit;
> + Chain_Node a;
> + Chain_Node b;
> + Chain_Node c;
> +
> + puts( "INIT - Verify Chain_Iterator" );
> +
> + rtems_test_assert( _Chain_Is_empty( &static_reg.Iterators ));
> +
> + _Chain_Initialize_empty( &chain );
> + _Chain_Iterator_registry_initialize( ® );
> + _Chain_Iterator_initialize( &chain, ®, &fit, CHAIN_ITERATOR_FORWARD );
> + _Chain_Iterator_initialize( &chain, ®, &bit, CHAIN_ITERATOR_BACKWARD );
> +
> + rtems_test_assert( _Chain_Iterator_next( &fit ) == _Chain_Tail( &chain ));
> + rtems_test_assert( _Chain_Iterator_next( &bit ) == _Chain_Head( &chain ));
> +
> + _Chain_Iterator_set_position( &fit, _Chain_Head( &chain ) );
> + _Chain_Iterator_set_position( &bit, _Chain_Tail( &chain ) );
> + rtems_test_assert( _Chain_Iterator_next( &fit ) == _Chain_Tail( &chain ));
> + rtems_test_assert( _Chain_Iterator_next( &bit ) == _Chain_Head( &chain ));
> +
> + _Chain_Append_unprotected( &chain, &a );
> + rtems_test_assert( _Chain_Iterator_next( &fit ) == &a );
> + rtems_test_assert( _Chain_Iterator_next( &bit ) == &a );
> +
> + _Chain_Append_unprotected( &chain, &b );
> + rtems_test_assert( _Chain_Iterator_next( &fit ) == &a );
> + rtems_test_assert( _Chain_Iterator_next( &bit ) == &b );
> +
> + _Chain_Append_unprotected( &chain, &c );
> + rtems_test_assert( _Chain_Iterator_next( &fit ) == &a );
> + rtems_test_assert( _Chain_Iterator_next( &bit ) == &c );
> +
> + update_registry_and_extract( ®, &b );
> + rtems_test_assert( _Chain_Iterator_next( &fit ) == &a );
> + rtems_test_assert( _Chain_Iterator_next( &bit ) == &c );
> +
> + _Chain_Insert_unprotected( &a, &b );
> + rtems_test_assert( _Chain_Iterator_next( &fit ) == &a );
> + rtems_test_assert( _Chain_Iterator_next( &bit ) == &c );
> +
> + update_registry_and_extract( ®, &c );
> + rtems_test_assert( _Chain_Iterator_next( &fit ) == &a );
> + rtems_test_assert( _Chain_Iterator_next( &bit ) == &b );
> +
> + _Chain_Append_unprotected( &chain, &c );
> + rtems_test_assert( _Chain_Iterator_next( &fit ) == &a );
> + rtems_test_assert( _Chain_Iterator_next( &bit ) == &c );
> +
> + update_registry_and_extract( ®, &a );
> + rtems_test_assert( _Chain_Iterator_next( &fit ) == &b );
> + rtems_test_assert( _Chain_Iterator_next( &bit ) == &c );
> +
> + _Chain_Prepend_unprotected( &chain, &a );
> + rtems_test_assert( _Chain_Iterator_next( &fit ) == &a );
> + rtems_test_assert( _Chain_Iterator_next( &bit ) == &c );
> +
> + update_registry_and_extract( ®, &a );
> + rtems_test_assert( _Chain_Iterator_next( &fit ) == &b );
> + rtems_test_assert( _Chain_Iterator_next( &bit ) == &c );
> +
> + update_registry_and_extract( ®, &b );
> + rtems_test_assert( _Chain_Iterator_next( &fit ) == &c );
> + rtems_test_assert( _Chain_Iterator_next( &bit ) == &c );
> +
> + update_registry_and_extract( ®, &c );
> + rtems_test_assert( _Chain_Iterator_next( &fit ) == _Chain_Tail( &chain ));
> + rtems_test_assert( _Chain_Iterator_next( &bit ) == _Chain_Head( &chain ));
> +
> + _Chain_Append_unprotected( &chain, &a );
> + rtems_test_assert( _Chain_Iterator_next( &fit ) == &a );
> + rtems_test_assert( _Chain_Iterator_next( &bit ) == &a );
> +
> + _Chain_Append_unprotected( &chain, &b );
> + rtems_test_assert( _Chain_Iterator_next( &fit ) == &a );
> + rtems_test_assert( _Chain_Iterator_next( &bit ) == &b );
> +
> + _Chain_Append_unprotected( &chain, &c );
> + rtems_test_assert( _Chain_Iterator_next( &fit ) == &a );
> + rtems_test_assert( _Chain_Iterator_next( &bit ) == &c );
> +
> + update_registry_and_extract( ®, &c );
> + rtems_test_assert( _Chain_Iterator_next( &fit ) == &a );
> + rtems_test_assert( _Chain_Iterator_next( &bit ) == &b );
> +
> + update_registry_and_extract( ®, &b );
> + rtems_test_assert( _Chain_Iterator_next( &fit ) == &a );
> + rtems_test_assert( _Chain_Iterator_next( &bit ) == &a );
> +
> + update_registry_and_extract( ®, &a );
> + rtems_test_assert( _Chain_Iterator_next( &fit ) == _Chain_Tail( &chain ));
> + rtems_test_assert( _Chain_Iterator_next( &bit ) == _Chain_Head( &chain ));
> +
> + rtems_test_assert( !_Chain_Is_empty( ®.Iterators ));
> + _Chain_Iterator_destroy( &fit );
> + rtems_test_assert( !_Chain_Is_empty( ®.Iterators ));
> + _Chain_Iterator_destroy( &bit );
> + rtems_test_assert( _Chain_Is_empty( ®.Iterators ));
> +}
> +
> /* forward declarations to avoid warnings */
> rtems_task Init(rtems_task_argument argument);
>
> @@ -341,6 +459,7 @@ rtems_task Init(
> test_chain_control_initializer();
> test_chain_node_count();
> test_chain_insert_ordered();
> + test_chain_iterator();
>
> TEST_END();
> rtems_test_exit(0);
> diff --git a/testsuites/sptests/spchain/spchain.doc
> b/testsuites/sptests/spchain/spchain.doc
> index 511e0b5..4962426 100644
> --- a/testsuites/sptests/spchain/spchain.doc
> +++ b/testsuites/sptests/spchain/spchain.doc
> @@ -25,6 +25,12 @@ directives:
> rtems_chain_get_with_wait
> rtems_chain_node_count_unprotected
> _Chain_Insert_ordered_unprotected
> + _Chain_Iterator_registry_initialize
> + _Chain_Iterator_registry_update
> + _Chain_Iterator_initialize
> + _Chain_Iterator_next
> + _Chain_Iterator_set_position
> + _Chain_Iterator_destroy
>
> concepts:
>
> diff --git a/testsuites/sptests/spchain/spchain.scn
> b/testsuites/sptests/spchain/spchain.scn
> index 39f3795..4aff306 100644
> --- a/testsuites/sptests/spchain/spchain.scn
> +++ b/testsuites/sptests/spchain/spchain.scn
> @@ -1,4 +1,4 @@
> -*** TEST OF RTEMS CHAIN API ***
> +*** BEGIN OF TEST SPCHAIN ***
> Init - Initialize chain empty
> INIT - Verify rtems_chain_insert
> INIT - Verify rtems_chain_is_first
> @@ -14,4 +14,5 @@ INIT - Verify rtems_chain_control layout
> INIT - Verify rtems_chain_control initializer
> INIT - Verify rtems_chain_node_count_unprotected
> INIT - Verify _Chain_Insert_ordered_unprotected
> -*** END OF RTEMS CHAIN API TEST ***
> +INIT - Verify Chain_Iterator
> +*** END OF TEST SPCHAIN ***
> --
> 1.8.4.5
>
> _______________________________________________
> devel mailing list
> devel@rtems.org
> http://lists.rtems.org/mailman/listinfo/devel
_______________________________________________
devel mailing list
devel@rtems.org
http://lists.rtems.org/mailman/listinfo/devel
