[PATCH 1/4] score: Add Resource Handler

Sebastian Huber sebastian.huber at embedded-brains.de
Wed May 28 14:29:25 UTC 2014


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
+)
+{
+  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




More information about the devel mailing list