[PATCH 1/4] score: Add Resource Handler
Gedare Bloom
gedare at rtems.org
Wed May 28 21:48:51 UTC 2014
On Wed, May 28, 2014 at 10:29 AM, Sebastian Huber
<sebastian.huber at embedded-brains.de> wrote:
> A resource is something that has at most one owner at a time and may
> have multiple rivals in case an owner is present. The owner and rivals
> are impersonated via resource nodes. A resource is represented via the
> resource control structure. The resource controls and nodes are
> organized as trees. It is possible to detect deadlocks via such a
> resource tree. The _Resource_Iterate() function can be used to iterate
> through such a resource tree starting at a top node.
> ---
> cpukit/score/Makefile.am | 3 +
> cpukit/score/include/rtems/score/resource.h | 211 ++++++++++++++
> cpukit/score/include/rtems/score/resourceimpl.h | 163 +++++++++++
> cpukit/score/preinstall.am | 8 +
> cpukit/score/src/resourceiterate.c | 106 +++++++
> testsuites/sptests/Makefile.am | 1 +
> testsuites/sptests/configure.ac | 1 +
> testsuites/sptests/spresource01/Makefile.am | 19 ++
> testsuites/sptests/spresource01/init.c | 319 ++++++++++++++++++++++
> testsuites/sptests/spresource01/spresource01.doc | 11 +
> testsuites/sptests/spresource01/spresource01.scn | 94 +++++++
> 11 files changed, 936 insertions(+), 0 deletions(-)
> create mode 100644 cpukit/score/include/rtems/score/resource.h
> create mode 100644 cpukit/score/include/rtems/score/resourceimpl.h
> create mode 100644 cpukit/score/src/resourceiterate.c
> create mode 100644 testsuites/sptests/spresource01/Makefile.am
> create mode 100644 testsuites/sptests/spresource01/init.c
> create mode 100644 testsuites/sptests/spresource01/spresource01.doc
> create mode 100644 testsuites/sptests/spresource01/spresource01.scn
>
> diff --git a/cpukit/score/Makefile.am b/cpukit/score/Makefile.am
> index b9a9f28..70760c5 100644
> --- a/cpukit/score/Makefile.am
> +++ b/cpukit/score/Makefile.am
> @@ -51,6 +51,8 @@ include_rtems_score_HEADERS += include/rtems/score/prioritybitmapimpl.h
> include_rtems_score_HEADERS += include/rtems/score/profiling.h
> include_rtems_score_HEADERS += include/rtems/score/rbtree.h
> include_rtems_score_HEADERS += include/rtems/score/rbtreeimpl.h
> +include_rtems_score_HEADERS += include/rtems/score/resource.h
> +include_rtems_score_HEADERS += include/rtems/score/resourceimpl.h
> include_rtems_score_HEADERS += include/rtems/score/scheduler.h
> include_rtems_score_HEADERS += include/rtems/score/schedulerimpl.h
> include_rtems_score_HEADERS += include/rtems/score/schedulercbs.h
> @@ -337,6 +339,7 @@ libscore_a_SOURCES += src/apiext.c src/chain.c src/chainappend.c \
> libscore_a_SOURCES += src/debugisownerofallocator.c
> libscore_a_SOURCES += src/profilingisrentryexit.c
> libscore_a_SOURCES += src/once.c
> +libscore_a_SOURCES += src/resourceiterate.c
>
> EXTRA_DIST = src/Unlimited.txt
>
> diff --git a/cpukit/score/include/rtems/score/resource.h b/cpukit/score/include/rtems/score/resource.h
> new file mode 100644
> index 0000000..ecf84a7
> --- /dev/null
> +++ b/cpukit/score/include/rtems/score/resource.h
> @@ -0,0 +1,211 @@
> +/*
> + * Copyright (c) 2014 embedded brains GmbH. All rights reserved.
> + *
> + * embedded brains GmbH
> + * Dornierstr. 4
> + * 82178 Puchheim
> + * Germany
> + * <rtems at embedded-brains.de>
> + *
> + * The license and distribution terms for this file may be
> + * found in the file LICENSE in this distribution or at
> + * http://www.rtems.org/license/LICENSE.
> + */
> +
> +#ifndef _RTEMS_SCORE_RESOURCE_H
> +#define _RTEMS_SCORE_RESOURCE_H
> +
> +#include <rtems/score/basedefs.h>
> +#include <rtems/score/chain.h>
> +
> +#ifdef __cplusplus
> +extern "C" {
> +#endif /* __cplusplus */
> +
> +/**
> + * @defgroup ScoreResource Resource Handler
> + *
> + * @ingroup Score
> + *
> + * @brief Support for resource dependency management.
> + *
> + * A resource is something that has at most one owner at a time and may have
> + * multiple rivals in case an owner is present. The owner and rivals are
> + * impersonated via resource nodes. A resource is represented via the resource
> + * control structure. The resource controls and nodes are organized as trees.
> + * It is possible to detect deadlocks via such a resource tree. The
> + * _Resource_Iterate() function can be used to iterate through such a resource
> + * tree starting at a top node.
> + *
> + * The following diagram shows an example resource tree with sixteen resource
> + * nodes n0 up to n15 and sixteen resources r0 up to r15. The root of this
> + * tree is n0. As a use case threads can be associated with resource nodes.
> + * In this case a thread represented by node n0 owns resources r0, r1, r2, r3,
> + * r6, r11 and r12 and is in the ready state. The threads represented by nodes
> + * n1 up to n15 wait directly or indirectly via resources owned by n0 and are
> + * in a blocked state.
> + *
> + * @dot
> + * digraph {
> + * n0 [style=filled, fillcolor=green];
> + * n0 -> r0;
> + * subgraph {
> + * rank=same;
> + * n1 [style=filled, fillcolor=green];
> + * r0 -> n1;
> + * n2 [style=filled, fillcolor=green];
> + * n1 -> n2;
> + * n4 [style=filled, fillcolor=green];
> + * n2 -> n4;
> + * n6 [style=filled, fillcolor=green];
> + * n4 -> n6;
> + * n8 [style=filled, fillcolor=green];
> + * n6 -> n8;
> + * n15 [style=filled, fillcolor=green];
> + * n8 -> n15;
> + * }
> + * n1 -> r5;
> + * subgraph {
> + * rank=same;
> + * n3 [style=filled, fillcolor=green];
> + * r5 -> n3;
> + * n12 [style=filled, fillcolor=green];
> + * n3 -> n12;
> + * }
> + * n3 -> r10;
> + * r10 -> r13;
> + * r13 -> r15;
> + * subgraph {
> + * rank=same;
> + * n10 [style=filled, fillcolor=green];
> + * r15 -> n10;
> + * }
> + * r5 -> r7;
> + * subgraph {
> + * rank=same;
> + * n11 [style=filled, fillcolor=green];
> + * r7 -> n11;
> + * n14 [style=filled, fillcolor=green];
> + * n11 -> n14;
> + * }
> + * n14 -> r4;
> + * r7 -> r8;
> + * subgraph {
> + * rank=same;
> + * n13 [style=filled, fillcolor=green];
> + * r8 -> n13;
> + * }
> + * r8 -> r9;
> + * n8 -> r14;
> + * r0 -> r1;
> + * subgraph {
> + * rank=same;
> + * n7 [style=filled, fillcolor=green];
> + * r1 -> n7;
> + * }
> + * r1 -> r2;
> + * r2 -> r3;
> + * r3 -> r6;
> + * r6 -> r11;
> + * r11 -> r12;
> + * subgraph {
> + * rank=same;
> + * n5 [style=filled, fillcolor=green];
> + * r12 -> n5;
> + * n9 [style=filled, fillcolor=green];
> + * n5 -> n9;
> + * }
> + * }
> + * @enddot
> + *
> + * The following example illustrates a deadlock situation. The root of the
> + * tree tries to get ownership of a resource owned by one of its children.
> + *
> + * @dot
> + * digraph {
> + * n0 [style=filled, fillcolor=green];
> + * n0 -> r0;
> + * subgraph {
> + * rank=same;
> + * n1 [style=filled, fillcolor=green];
> + * r0 -> n1;
> + * }
> + * n1 -> r1;
> + * n0 -> r1 [label=deadlock, style=dotted];
> + * }
> + * @enddot
> + *
> + * @{
> + */
> +
> +typedef struct Resource_Node Resource_Node;
> +
> +typedef struct Resource_Control Resource_Control;
> +
> +/**
> + * @brief Resource node to reflect ownership of resources and a dependency on a
> + * resource.
> + */
> +struct Resource_Node {
> + /**
> + * @brief Node to build a chain of rivals depending on a resource.
> + *
> + * @see Resource_Control::Rivals.
> + */
> + Chain_Node Node;
> +
> + /**
> + * @brief A chain of resources owned by this node.
> + *
> + * @see Resource_Control::Node.
> + */
> + Chain_Control Resources;
> +
> + /**
> + * @brief Reference to a resource in case this node has to wait for ownership
> + * of this resource.
> + *
> + * It is @c NULL in case this node has no open resource dependency.
> + */
> + Resource_Control *dependency;
> +
> + /**
> + * @brief Reference to the root of the resource tree.
> + *
> + * The root references itself.
> + */
> + Resource_Node *root;
> +};
> +
> +/**
> + * @brief Resource control to manage ownership and rival nodes depending on a
> + * resource.
> + */
> +struct Resource_Control {
> + /**
> + * @brief Node to build a chain of resources owned by a resource node.
> + *
> + * @see Resource_Node::Resources.
> + */
> + Chain_Node Node;
> +
> + /**
> + * @brief A chain of rivals waiting for resource ownership.
> + *
> + * @see Resource_Node::Node.
> + */
> + Chain_Control Rivals;
> +
> + /**
> + * @brief The owner of this resource.
> + */
> + Resource_Node *owner;
> +};
> +
> +/** @} */
> +
> +#ifdef __cplusplus
> +}
> +#endif /* __cplusplus */
> +
> +#endif /* _RTEMS_SCORE_RESOURCE_H */
> diff --git a/cpukit/score/include/rtems/score/resourceimpl.h b/cpukit/score/include/rtems/score/resourceimpl.h
> new file mode 100644
> index 0000000..4f5a8d8
> --- /dev/null
> +++ b/cpukit/score/include/rtems/score/resourceimpl.h
> @@ -0,0 +1,163 @@
> +/*
> + * Copyright (c) 2014 embedded brains GmbH. All rights reserved.
> + *
> + * embedded brains GmbH
> + * Dornierstr. 4
> + * 82178 Puchheim
> + * Germany
> + * <rtems at embedded-brains.de>
> + *
> + * The license and distribution terms for this file may be
> + * found in the file LICENSE in this distribution or at
> + * http://www.rtems.org/license/LICENSE.
> + */
> +
> +#ifndef _RTEMS_SCORE_RESOURCEIMPL_H
> +#define _RTEMS_SCORE_RESOURCEIMPL_H
> +
> +#include <rtems/score/resource.h>
> +#include <rtems/score/chainimpl.h>
> +
> +#ifdef __cplusplus
> +extern "C" {
> +#endif /* __cplusplus */
> +
> +/**
> + * @addtogroup ScoreResource
> + *
> + * @{
> + */
> +
> +/**
> + * @brief Visitor function for resource node iteration.
> + *
> + * The visitor is allowed to extract the node.
> + *
> + * @param[in] node The current resource node.
> + * @param[in] arg The argument passed to _Resource_Iterate().
> + *
> + * @retval true Stop the iteration.
> + * @retval false Continue the iteration.
> + */
> +typedef bool (*Resource_Node_visitor)( Resource_Node *node, void *arg );
> +
> +/**
> + * @brief Iterates over all nodes of a resource dependency tree.
> + *
> + * @param[in] top The top node to start the iteration. The visitor function is
> + * not invoked for the top node.
> + * @param[in] visitor The visitor function.
> + * @param[in] arg The argument for the visitor function.
> + */
> +void _Resource_Iterate(
> + Resource_Node *top,
> + Resource_Node_visitor visitor,
> + void *arg
> +);
> +
> +RTEMS_INLINE_ROUTINE void _Resource_Node_initialize( Resource_Node *node )
> +{
> + node->dependency = NULL;
> + node->root = node;
> + _Chain_Initialize_empty( &node->Resources );
> +}
> +
> +RTEMS_INLINE_ROUTINE void _Resource_Node_set_dependency(
> + Resource_Node *node,
> + Resource_Control *dependency
> +)
> +{
> + node->dependency = dependency;
> +}
> +
> +RTEMS_INLINE_ROUTINE Resource_Node *_Resource_Node_get_root(
> + const Resource_Node *node
> +)
> +{
> + return node->root;
> +}
> +
> +RTEMS_INLINE_ROUTINE void _Resource_Node_set_root(
> + Resource_Node *node,
> + Resource_Node *root
> +)
> +{
> + node->root = root;
> +}
> +
> +RTEMS_INLINE_ROUTINE bool _Resource_Node_owns_resources( const Resource_Node *node )
> +{
> + return !_Chain_Is_empty( &node->Resources );
> +}
> +
> +RTEMS_INLINE_ROUTINE void _Resource_Node_add_resource(
> + Resource_Node *node,
> + Resource_Control *resource
> +)
> +{
> + _Chain_Prepend_unprotected( &node->Resources, &resource->Node );
> +}
> +
> +/**
> + * @brief Returns true if this is the most recent resource of the node, and
> + * false otherwise.
> + *
> + * Resources are organized in last in first out order (LIFO).
> + *
> + * @param[in] node The node containing the resource.
> + * @param[in] resource The resource in question.
> + */
> +RTEMS_INLINE_ROUTINE bool _Resource_Is_most_recent_resource_of_node(
> + const Resource_Node *node,
> + const Resource_Control *resource
> +)
At first this function name confused me when I saw it used. I'm not
sure if a better name exists but it may be worth considering. Also,
this whole Resource handler is a bit odd compared to other data
structures in RTEMS, in that the interface functions take a Node first
and a Control second. Usually the Control comes first.
> +{
> + return &resource->Node == _Chain_Immutable_first( &node->Resources );
> +}
> +
> +RTEMS_INLINE_ROUTINE void _Resource_Node_extract( Resource_Node *node )
> +{
> + _Chain_Extract_unprotected( &node->Node );
> +}
> +
> +RTEMS_INLINE_ROUTINE void _Resource_Initialize( Resource_Control *resource )
> +{
> + resource->owner = NULL;
> + _Chain_Initialize_empty( &resource->Rivals );
> +}
> +
> +RTEMS_INLINE_ROUTINE void _Resource_Add_rival(
> + Resource_Control *resource,
> + Resource_Node *node
> +)
> +{
> + _Chain_Append_unprotected( &resource->Rivals, &node->Node );
> +}
> +
> +RTEMS_INLINE_ROUTINE void _Resource_Extract( Resource_Control *resource )
> +{
> + _Chain_Extract_unprotected( &resource->Node );
> +}
> +
> +RTEMS_INLINE_ROUTINE Resource_Node *_Resource_Get_owner(
> + const Resource_Control *resource
> +)
> +{
> + return resource->owner;
> +}
> +
> +RTEMS_INLINE_ROUTINE void _Resource_Set_owner(
> + Resource_Control *resource,
> + Resource_Node *owner
> +)
> +{
> + resource->owner = owner;
> +}
> +
> +/** @} */
> +
> +#ifdef __cplusplus
> +}
> +#endif /* __cplusplus */
> +
> +#endif /* _RTEMS_SCORE_RESOURCEIMPL_H */
> diff --git a/cpukit/score/preinstall.am b/cpukit/score/preinstall.am
> index 45a0ce7..f5474c5 100644
> --- a/cpukit/score/preinstall.am
> +++ b/cpukit/score/preinstall.am
> @@ -187,6 +187,14 @@ $(PROJECT_INCLUDE)/rtems/score/rbtreeimpl.h: include/rtems/score/rbtreeimpl.h $(
> $(INSTALL_DATA) $< $(PROJECT_INCLUDE)/rtems/score/rbtreeimpl.h
> PREINSTALL_FILES += $(PROJECT_INCLUDE)/rtems/score/rbtreeimpl.h
>
> +$(PROJECT_INCLUDE)/rtems/score/resource.h: include/rtems/score/resource.h $(PROJECT_INCLUDE)/rtems/score/$(dirstamp)
> + $(INSTALL_DATA) $< $(PROJECT_INCLUDE)/rtems/score/resource.h
> +PREINSTALL_FILES += $(PROJECT_INCLUDE)/rtems/score/resource.h
> +
> +$(PROJECT_INCLUDE)/rtems/score/resourceimpl.h: include/rtems/score/resourceimpl.h $(PROJECT_INCLUDE)/rtems/score/$(dirstamp)
> + $(INSTALL_DATA) $< $(PROJECT_INCLUDE)/rtems/score/resourceimpl.h
> +PREINSTALL_FILES += $(PROJECT_INCLUDE)/rtems/score/resourceimpl.h
> +
> $(PROJECT_INCLUDE)/rtems/score/scheduler.h: include/rtems/score/scheduler.h $(PROJECT_INCLUDE)/rtems/score/$(dirstamp)
> $(INSTALL_DATA) $< $(PROJECT_INCLUDE)/rtems/score/scheduler.h
> PREINSTALL_FILES += $(PROJECT_INCLUDE)/rtems/score/scheduler.h
> diff --git a/cpukit/score/src/resourceiterate.c b/cpukit/score/src/resourceiterate.c
> new file mode 100644
> index 0000000..26f9234
> --- /dev/null
> +++ b/cpukit/score/src/resourceiterate.c
> @@ -0,0 +1,106 @@
> +/*
> + * Copyright (c) 2014 embedded brains GmbH. All rights reserved.
> + *
> + * embedded brains GmbH
> + * Dornierstr. 4
> + * 82178 Puchheim
> + * Germany
> + * <rtems at embedded-brains.de>
> + *
> + * The license and distribution terms for this file may be
> + * found in the file LICENSE in this distribution or at
> + * http://www.rtems.org/license/LICENSE.
> + */
> +
> +#include <rtems/score/resourceimpl.h>
> +
> +static Resource_Control *_Resource_Rival_head_to_resource( Chain_Node *head )
> +{
> + return (Resource_Control *)
> + ( (char *) head - offsetof( Resource_Control, Rivals.Head.Node ) );
> +}
> +
> +static Resource_Node *_Resource_Resource_tail_to_rival( Chain_Node *tail )
> +{
> + return (Resource_Node *)
> + ( (char *) tail - offsetof( Resource_Node, Resources.Tail.Node ) );
> +}
> +
> +void _Resource_Iterate(
> + Resource_Node *top,
> + Resource_Node_visitor visitor,
> + void *arg
> +)
> +{
> + Chain_Node *resource_tail = _Chain_Tail( &top->Resources );
> + Resource_Control *resource =
> + (Resource_Control *) _Chain_Head( &top->Resources );
> +
> + Chain_Node *rival_stop = NULL;
> + Resource_Node *rival = NULL;
> +
> + enum {
> + NODE_FORWARD,
> + NODE_BACKWARD,
> + RESOURCE_FORWARD
> + } dir = RESOURCE_FORWARD;
> +
> + bool stop = false;
> +
> + do {
> + switch ( dir ) {
> + case NODE_FORWARD:
> + while ( !stop && &rival->Node != rival_stop ) {
> + Resource_Node *current = rival;
> +
> + rival = (Resource_Node *) _Chain_Next( &rival->Node );
> + stop = ( *visitor )( current, arg );
> + }
> +
> + rival_stop = _Chain_Head( &resource->Rivals );
> + dir = NODE_BACKWARD;
> + break;
> + case NODE_BACKWARD:
> + rival = (Resource_Node *) _Chain_Previous( &rival->Node );
> +
> + while (
> + &rival->Node != rival_stop
> + && _Chain_Is_empty( &rival->Resources )
> + ) {
> + rival = (Resource_Node *) _Chain_Previous( &rival->Node );
> + }
> +
> + if ( &rival->Node != rival_stop ) {
> + resource_tail = _Chain_Tail( &rival->Resources );
> + resource = (Resource_Control *) _Chain_Head( &rival->Resources );
> + } else {
> + resource = _Resource_Rival_head_to_resource( rival_stop );
> + resource_tail = _Chain_Tail( &resource->owner->Resources );
> + }
> +
> + dir = RESOURCE_FORWARD;
> + break;
> + case RESOURCE_FORWARD:
> + resource = (Resource_Control *) _Chain_Next( &resource->Node );
> +
> + while (
> + &resource->Node != resource_tail
> + && _Chain_Is_empty( &resource->Rivals )
> + ) {
> + resource = (Resource_Control *) _Chain_Next( &resource->Node );
> + }
> +
> + if ( &resource->Node != resource_tail ) {
> + rival_stop = _Chain_Tail( &resource->Rivals );
> + rival = (Resource_Node *) _Chain_First( &resource->Rivals );
> + dir = NODE_FORWARD;
> + } else {
> + rival = _Resource_Resource_tail_to_rival( resource_tail );
> + rival_stop = _Chain_Head( &rival->dependency->Rivals );
> + dir = NODE_BACKWARD;
> + }
> +
> + break;
> + }
> + } while ( !stop && rival != top );
> +}
> diff --git a/testsuites/sptests/Makefile.am b/testsuites/sptests/Makefile.am
> index cc5ed26..e55061e 100644
> --- a/testsuites/sptests/Makefile.am
> +++ b/testsuites/sptests/Makefile.am
> @@ -37,6 +37,7 @@ if HAS_SMP
> else
> _SUBDIRS += sp29
> endif
> +_SUBDIRS += spresource01
> _SUBDIRS += spmrsp01
> _SUBDIRS += spscheduler01
> _SUBDIRS += spprofiling01
> diff --git a/testsuites/sptests/configure.ac b/testsuites/sptests/configure.ac
> index ebc81ed..42fb87f 100644
> --- a/testsuites/sptests/configure.ac
> +++ b/testsuites/sptests/configure.ac
> @@ -40,6 +40,7 @@ AM_CONDITIONAL(HAS_SMP,test "$rtems_cv_RTEMS_SMP" = "yes")
>
> # Explicitly list all Makefiles here
> AC_CONFIG_FILES([Makefile
> +spresource01/Makefile
> spmrsp01/Makefile
> spscheduler01/Makefile
> spfatal28/Makefile
> diff --git a/testsuites/sptests/spresource01/Makefile.am b/testsuites/sptests/spresource01/Makefile.am
> new file mode 100644
> index 0000000..292dd05
> --- /dev/null
> +++ b/testsuites/sptests/spresource01/Makefile.am
> @@ -0,0 +1,19 @@
> +rtems_tests_PROGRAMS = spresource01
> +spresource01_SOURCES = init.c
> +
> +dist_rtems_tests_DATA = spresource01.scn spresource01.doc
> +
> +include $(RTEMS_ROOT)/make/custom/@RTEMS_BSP at .cfg
> +include $(top_srcdir)/../automake/compile.am
> +include $(top_srcdir)/../automake/leaf.am
> +
> +AM_CPPFLAGS += -I$(top_srcdir)/../support/include
> +
> +LINK_OBJS = $(spresource01_OBJECTS)
> +LINK_LIBS = $(spresource01_LDLIBS)
> +
> +spresource01$(EXEEXT): $(spresource01_OBJECTS) $(spresource01_DEPENDENCIES)
> + @rm -f spresource01$(EXEEXT)
> + $(make-exe)
> +
> +include $(top_srcdir)/../automake/local.am
> diff --git a/testsuites/sptests/spresource01/init.c b/testsuites/sptests/spresource01/init.c
> new file mode 100644
> index 0000000..be0ade7
> --- /dev/null
> +++ b/testsuites/sptests/spresource01/init.c
> @@ -0,0 +1,319 @@
> +/*
> + * Copyright (c) 2014 embedded brains GmbH. All rights reserved.
> + *
> + * embedded brains GmbH
> + * Dornierstr. 4
> + * 82178 Puchheim
> + * Germany
> + * <rtems at embedded-brains.de>
> + *
> + * The license and distribution terms for this file may be
> + * found in the file LICENSE in this distribution or at
> + * http://www.rtems.org/license/LICENSE.
> + */
> +
> +#ifdef HAVE_CONFIG_H
> + #include "config.h"
> +#endif
> +
> +#include <stdio.h>
> +
> +#include <rtems.h>
> +#include <rtems/score/resourceimpl.h>
> +
> +#include "tmacros.h"
> +
> +const char rtems_test_name[] = "SPRESOURCE 1";
> +
> +static Resource_Control rt[16];
> +
> +static Resource_Node nt[16];
> +
> +#define RESOURCE_COUNT RTEMS_ARRAY_SIZE(rt)
> +
> +#define NODE_COUNT RTEMS_ARRAY_SIZE(nt)
> +
> +static size_t ri(Resource_Control *r)
> +{
> + return (size_t) (r - &rt[0]);
> +}
> +
> +static size_t ni(Resource_Node *n)
> +{
> + return (size_t) (n - &nt[0]);
> +}
> +
> +static void print_node(Resource_Node *n);
> +
> +static void print_resource(Resource_Control *r)
> +{
> + Chain_Control *rivals = &r->Rivals;
> +
> + if (!_Chain_Is_empty(rivals)) {
> + const Chain_Node *tail = _Chain_Immutable_tail(rivals);
> + Resource_Node *last = (Resource_Node *) _Chain_First(rivals);
> + Resource_Node *next = (Resource_Node *) _Chain_Next(&last->Node);
> +
> + printf(
> + " subgraph {\n"
> + " rank=same;\n"
> + " n%zi [style=filled, fillcolor=green];\n"
> + " r%zi -> n%zi;\n",
> + ni(last),
> + ri(r),
> + ni(last)
> + );
> +
> + while (&next->Node != tail) {
> + printf(
> + " n%zi [style=filled, fillcolor=green];\n"
> + " n%zi -> n%zi;\n",
> + ni(next),
> + ni(last),
> + ni(next)
> + );
> +
> + last = next;
> + next = (Resource_Node *) _Chain_Next(&next->Node);
> + }
> +
> + printf(" }\n");
> +
> + next = (Resource_Node *) _Chain_First(rivals);
> + while (&next->Node != tail) {
> + print_node(next);
> +
> + next = (Resource_Node *) _Chain_Next(&next->Node);
> + }
> + }
> +}
> +
> +static void print_node(Resource_Node *n)
> +{
> + Chain_Control *resources = &n->Resources;
> +
> + if (!_Chain_Is_empty(resources)) {
> + const Chain_Node *tail = _Chain_Immutable_tail(resources);
> + Resource_Control *last = (Resource_Control *) _Chain_First(resources);
> + Resource_Control *next = (Resource_Control *) _Chain_Next(&last->Node);
> +
> + printf(" n%zi -> r%zi;\n", ni(n), ri(last));
> + print_resource(last);
> +
> + while (&next->Node != tail) {
> + printf(" r%zi -> r%zi;\n", ri(last), ri(next));
> + print_resource(next);
> +
> + last = next;
> + next = (Resource_Control *) _Chain_Next(&next->Node);
> + }
> + }
> +}
> +
> +static const size_t node_seq[NODE_COUNT - 1] =
> + { 1, 2, 4, 6, 8, 15, 3, 12, 10, 11, 14, 13, 7, 5, 9 };
> +
> +static bool visitor_all(Resource_Node *n, void *arg)
> +{
> + size_t *index = arg;
> + size_t i = *index;
> +
> + printf("n%zi\n", ni(n));
> +
> + rtems_test_assert(i < RTEMS_ARRAY_SIZE(node_seq));
> + rtems_test_assert(node_seq[i] == ni(n));
> +
> + *index = i + 1;
> +
> + return false;
> +}
> +
> +static bool visitor_seven(Resource_Node *n, void *arg)
> +{
> + size_t *index = arg;
> + size_t i = *index;
> +
> + printf("n%zi\n", ni(n));
> +
> + rtems_test_assert(i < 7);
> + rtems_test_assert(node_seq[i] == ni(n));
> +
> + *index = i + 1;
> +
> + return i + 1 >= 7;
> +}
> +
> +static const bool owns_resources[RESOURCE_COUNT] = {
> + true, true, false, true, false, false, false, false, true, false, false,
> + false, false, false, true, false
> +};
> +
> +static void add_resource(Resource_Node *n, Resource_Control *r)
> +{
> + _Resource_Node_add_resource(n, r);
> + _Resource_Set_owner(r, n);
> +}
> +
> +static void add_rival(Resource_Control *r, Resource_Node *n)
> +{
> + _Resource_Add_rival(r, n);
> + _Resource_Node_set_dependency(n, r);
> + _Resource_Node_set_root(n, &nt[0]);
> +}
> +
> +static void test_resource_iterate(void)
> +{
> + Resource_Node *root = &nt[0];
> + size_t i;
> +
> + printf("digraph {\n");
> +
> + for (i = 0; i < RESOURCE_COUNT; ++i) {
> + _Resource_Initialize(&rt[i]);
> + }
> +
> + for (i = 0; i < NODE_COUNT; ++i) {
> + _Resource_Node_initialize(&nt[i]);
> + }
> +
> + add_resource(&nt[0], &rt[12]);
> + add_resource(&nt[0], &rt[11]);
> + add_resource(&nt[0], &rt[6]);
> + add_resource(&nt[0], &rt[3]);
> + add_resource(&nt[0], &rt[2]);
> + add_resource(&nt[0], &rt[1]);
> + add_resource(&nt[0], &rt[0]);
> +
> + add_resource(&nt[1], &rt[9]);
> + add_resource(&nt[1], &rt[8]);
> + add_resource(&nt[1], &rt[7]);
> + add_resource(&nt[1], &rt[5]);
> +
> + add_resource(&nt[3], &rt[15]);
> + add_resource(&nt[3], &rt[13]);
> + add_resource(&nt[3], &rt[10]);
> +
> + add_resource(&nt[8], &rt[14]);
> +
> + add_resource(&nt[14], &rt[4]);
> +
> + add_rival(&rt[0], &nt[1]);
> + add_rival(&rt[0], &nt[2]);
> + add_rival(&rt[0], &nt[4]);
> + add_rival(&rt[0], &nt[6]);
> + add_rival(&rt[0], &nt[8]);
> + add_rival(&rt[0], &nt[15]);
> +
> + add_rival(&rt[1], &nt[7]);
> +
> + add_rival(&rt[5], &nt[3]);
> + add_rival(&rt[5], &nt[12]);
> +
> + add_rival(&rt[7], &nt[11]);
> + add_rival(&rt[7], &nt[14]);
> +
> + add_rival(&rt[8], &nt[13]);
> +
> + add_rival(&rt[12], &nt[5]);
> + add_rival(&rt[12], &nt[9]);
> +
> + add_rival(&rt[15], &nt[10]);
> +
> + for (i = 0; i < NODE_COUNT; ++i) {
> + rtems_test_assert(
> + _Resource_Node_owns_resources(&nt[i]) == owns_resources[i]
> + );
> + }
> +
> + printf(" n%zi [style=filled, fillcolor=green];\n", ni(root));
> + print_node(root);
> +
> + printf("}\n");
> +
> + i = 0;
> + _Resource_Iterate(root, visitor_all, &i);
> + rtems_test_assert(i == 15);
> +
> + i = 0;
> + _Resource_Iterate(root, visitor_seven, &i);
> + rtems_test_assert(i == 7);
> +}
> +
> +static void test_resource_simple(void)
> +{
> + Resource_Control r0;
> + Resource_Control r1;
> + Resource_Node n0;
> +
> + _Resource_Node_initialize(&n0);
> + rtems_test_assert(!_Resource_Node_owns_resources(&n0));
> + rtems_test_assert(_Resource_Node_get_root(&n0) == &n0);
> + rtems_test_assert(n0.dependency == NULL);
> +
> + _Resource_Node_set_root(&n0, NULL);
> + rtems_test_assert(_Resource_Node_get_root(&n0) == NULL);
> + _Resource_Node_set_root(&n0, &n0);
> + rtems_test_assert(_Resource_Node_get_root(&n0) == &n0);
> +
> + _Resource_Initialize(&r0);
> + rtems_test_assert(_Resource_Get_owner(&r0) == NULL);
> + rtems_test_assert(_Chain_Is_empty(&r0.Rivals));
> +
> + _Resource_Set_owner(&r0, &n0);
> + rtems_test_assert(_Resource_Get_owner(&r0) == &n0);
> + _Resource_Set_owner(&r0, NULL);
> + rtems_test_assert(_Resource_Get_owner(&r0) == NULL);
> +
> + _Resource_Initialize(&r1);
> +
> + _Resource_Node_add_resource(&n0, &r0);
> + rtems_test_assert(_Resource_Node_owns_resources(&n0));
> + rtems_test_assert(_Resource_Is_most_recent_resource_of_node(&n0, &r0));
> +
> + _Resource_Node_add_resource(&n0, &r1);
> + rtems_test_assert(_Resource_Node_owns_resources(&n0));
> + rtems_test_assert(!_Resource_Is_most_recent_resource_of_node(&n0, &r0));
> + rtems_test_assert(_Resource_Is_most_recent_resource_of_node(&n0, &r1));
> +
> + _Resource_Extract(&r1);
> + rtems_test_assert(_Resource_Node_owns_resources(&n0));
> + rtems_test_assert(_Resource_Is_most_recent_resource_of_node(&n0, &r0));
> + rtems_test_assert(!_Resource_Is_most_recent_resource_of_node(&n0, &r1));
> +
> + _Resource_Extract(&r0);
> + rtems_test_assert(!_Resource_Node_owns_resources(&n0));
> + rtems_test_assert(!_Resource_Is_most_recent_resource_of_node(&n0, &r0));
> + rtems_test_assert(!_Resource_Is_most_recent_resource_of_node(&n0, &r1));
> +
> + _Resource_Add_rival(&r0, &n0);
> + rtems_test_assert(!_Chain_Is_empty(&r0.Rivals));
> +
> + _Resource_Node_extract(&n0);
> + rtems_test_assert(_Chain_Is_empty(&r0.Rivals));
> +}
> +
> +static void Init(rtems_task_argument arg)
> +{
> + TEST_BEGIN();
> +
> + test_resource_simple();
> + test_resource_iterate();
> +
> + TEST_END();
> + rtems_test_exit(0);
> +}
> +
> +#define CONFIGURE_APPLICATION_DOES_NOT_NEED_CLOCK_DRIVER
> +#define CONFIGURE_APPLICATION_NEEDS_CONSOLE_DRIVER
> +
> +#define CONFIGURE_USE_IMFS_AS_BASE_FILESYSTEM
> +
> +#define CONFIGURE_MAXIMUM_TASKS 1
> +
> +#define CONFIGURE_INITIAL_EXTENSIONS RTEMS_TEST_INITIAL_EXTENSION
> +
> +#define CONFIGURE_RTEMS_INIT_TASKS_TABLE
> +
> +#define CONFIGURE_INIT
> +
> +#include <rtems/confdefs.h>
> diff --git a/testsuites/sptests/spresource01/spresource01.doc b/testsuites/sptests/spresource01/spresource01.doc
> new file mode 100644
> index 0000000..eda0f12
> --- /dev/null
> +++ b/testsuites/sptests/spresource01/spresource01.doc
> @@ -0,0 +1,11 @@
> +This file describes the directives and concepts tested by this test set.
> +
> +test set name: spresource01
> +
> +directives:
> +
> + - _Resource_Iterate()
> +
> +concepts:
> +
> + - Ensure that interation over resource nodes works.
> diff --git a/testsuites/sptests/spresource01/spresource01.scn b/testsuites/sptests/spresource01/spresource01.scn
> new file mode 100644
> index 0000000..6a4f8de
> --- /dev/null
> +++ b/testsuites/sptests/spresource01/spresource01.scn
> @@ -0,0 +1,94 @@
> +*** BEGIN OF TEST SPRESOURCE 1 ***
> +digraph {
> + n0 [style=filled, fillcolor=green];
> + n0 -> r0;
> + subgraph {
> + rank=same;
> + n1 [style=filled, fillcolor=green];
> + r0 -> n1;
> + n2 [style=filled, fillcolor=green];
> + n1 -> n2;
> + n4 [style=filled, fillcolor=green];
> + n2 -> n4;
> + n6 [style=filled, fillcolor=green];
> + n4 -> n6;
> + n8 [style=filled, fillcolor=green];
> + n6 -> n8;
> + n15 [style=filled, fillcolor=green];
> + n8 -> n15;
> + }
> + n1 -> r5;
> + subgraph {
> + rank=same;
> + n3 [style=filled, fillcolor=green];
> + r5 -> n3;
> + n12 [style=filled, fillcolor=green];
> + n3 -> n12;
> + }
> + n3 -> r10;
> + r10 -> r13;
> + r13 -> r15;
> + subgraph {
> + rank=same;
> + n10 [style=filled, fillcolor=green];
> + r15 -> n10;
> + }
> + r5 -> r7;
> + subgraph {
> + rank=same;
> + n11 [style=filled, fillcolor=green];
> + r7 -> n11;
> + n14 [style=filled, fillcolor=green];
> + n11 -> n14;
> + }
> + n14 -> r4;
> + r7 -> r8;
> + subgraph {
> + rank=same;
> + n13 [style=filled, fillcolor=green];
> + r8 -> n13;
> + }
> + r8 -> r9;
> + n8 -> r14;
> + r0 -> r1;
> + subgraph {
> + rank=same;
> + n7 [style=filled, fillcolor=green];
> + r1 -> n7;
> + }
> + r1 -> r2;
> + r2 -> r3;
> + r3 -> r6;
> + r6 -> r11;
> + r11 -> r12;
> + subgraph {
> + rank=same;
> + n5 [style=filled, fillcolor=green];
> + r12 -> n5;
> + n9 [style=filled, fillcolor=green];
> + n5 -> n9;
> + }
> +}
> +n1
> +n2
> +n4
> +n6
> +n8
> +n15
> +n3
> +n12
> +n10
> +n11
> +n14
> +n13
> +n7
> +n5
> +n9
> +n1
> +n2
> +n4
> +n6
> +n8
> +n15
> +n3
> +*** END OF TEST SPRESOURCE 1 ***
> --
> 1.7.7
>
> _______________________________________________
> rtems-devel mailing list
> rtems-devel at rtems.org
> http://www.rtems.org/mailman/listinfo/rtems-devel
More information about the devel
mailing list