score: Add Resource Handler

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.

5 files changed, 491 insertions, 0 deletions

diff --git a/cpukit/score/Makefile.am b/cpukit/score/Makefile.am
index b9a9f28514..70760c57cd 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 0000000000..ecf84a7275
--- /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@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 0000000000..69e9a3c5f8
--- /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@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 );
+}
+
+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;
+}
+
+/**
+ * @brief Returns true if this is the most recently obtained resource of the
+ * node, and false otherwise.
+ *
+ * Resources are organized in last in first out order (LIFO).
+ *
+ * @param[in] resource The resource in question.
+ * @param[in] node The node that obtained the resource.
+ */
+RTEMS_INLINE_ROUTINE bool _Resource_Is_most_recently_obtained(
+  const Resource_Control *resource,
+  const Resource_Node    *node
+)
+{
+  return &resource->Node == _Chain_Immutable_first( &node->Resources );
+}
+
+/** @} */
+
+#ifdef __cplusplus
+}
+#endif /* __cplusplus */
+
+#endif /* _RTEMS_SCORE_RESOURCEIMPL_H */
diff --git a/cpukit/score/preinstall.am b/cpukit/score/preinstall.am
index 45a0ce730f..f5474c5406 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 0000000000..26f923491d
--- /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@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 );
+}