Optimized association lookup performance

- Updated attribute compiler to serialize association lists into binary
- Updated getAssociated call to optimally search associations
- Fixed IBSCOM unit test to look at present/functional targets
- Added association list pointers to target object
- Removed unused association types, added max association type
- Removed association direction enum
- Removed association type to attribute type mapping and container
- Removed association type to attribute type container initialization
- Removed getAssocaited helper functions (get inwards / get outwards)

Change-Id: I3b595781d881911b3808f4f91833437a5cac6eb3
RTC: 88619
Reviewed-on: http://gfw160.aus.stglabs.ibm.com:8080/gerrit/7003
Tested-by: Jenkins Server
Reviewed-by: Brian H. Horton <brianh@linux.ibm.com>
Reviewed-by: A. Patrick Williams III <iawillia@us.ibm.com>

5 files changed, 589 insertions, 274 deletions

diff --git a/src/include/usr/targeting/common/target.H b/src/include/usr/targeting/common/target.H
index ffeecd340..b85e80667 100644
--- a/src/include/usr/targeting/common/target.H
+++ b/src/include/usr/targeting/common/target.H
@@ -533,6 +533,17 @@ class Target
         // Pointer to array of void* (which point to attributes)
         TARGETING::AbstractPointer< AbstractPointer<void> > iv_pAttrValues;
 
+        // Array of pointers to target handles.  Currently there is one pointer
+        // for each supported association type.  The currently supported
+        // association types are PARENT, CHILD, PARENT_BY_AFFINITY, and
+        // CHILD_BY_AFFINTY.  The number of pointers should exactly equal value
+        // of TargetService::MAX_ASSOCIATION_TYPES defined in
+        // targeting/common/targetservice.H.  Due to the huge code changes
+        // necessary to directly use that enum value, a compile time assert in
+        // targeting/common/targetservice.C enforces that restriction.
+        TARGETING::AbstractPointer< AbstractPointer<Target> >
+            iv_ppAssociations[4];
+
     private: // Private CTORs/DTORs/Operators
 
         /**
@@ -559,6 +570,8 @@ class Target
 
         friend class PnorBuilderService;
         friend class TargetCloner;
+        friend class TargetService;
+        friend class AssociationManager;
 
         // Friend functions to allow FAPI Attribute code to directly call
         // _tryGetAttr and _trySetAttr for code size optimization
diff --git a/src/include/usr/targeting/common/targetservice.H b/src/include/usr/targeting/common/targetservice.H
index 6dd2cd2f0..a24b6eac8 100644
--- a/src/include/usr/targeting/common/targetservice.H
+++ b/src/include/usr/targeting/common/targetservice.H
@@ -177,10 +177,7 @@ class TargetService
                                 ///< Hardware affinity.  For example the child
                                 ///< of a memory controller channel target might
                                 ///< be a DIMM target
-            VOLTAGE_SUPPLIER,   ///< The result target(s) should be the voltage
-                                ///< supplier
-            VOLTAGE_CONSUMER,   ///< The result target(s) should be the voltage
-                                ///< consumer
+            MAX_ASSOCIATION_TYPES, ///< Number of types, must always be last
         };
 
     public:
@@ -488,10 +485,10 @@ class TargetService
                   EntityPath&  o_entityPath) const;
 
         /**
-         *  @brief Returns entity paths of targets associated to the specified
-         *      target in a specific way
+         *  @brief Returns handles to targets associated to the specified
+         *      target in a specific way, in depth first order
          *
-         *  Returns entity paths of targets associated to the specified target,
+         *  Returns handles to targets associated to the specified target,
          *  as indicated by an association type.  Based on the specified
          *  recursion level, the routine will determine the immediate
          *  associations, or all possible associations.  For example, if caller
@@ -499,11 +496,13 @@ class TargetService
          *  the routine will return the next set of targets in the physical
          *  hierarchy.  Conversely if the caller asks for ALL children targets
          *  for said source target, the routine will return all targets
-         *  contained within the processor chip.
+         *  contained within the processor chip.  All targets will be returned
+         *  in depth first order.
          *
          *  @param[out] o_list List of target handles that match the specified
-         *      criteria
-         *  @param[in] i_pTarget Target from which to search for other targets
+         *      criteria.  Caller's list will be cleared initially.
+         *  @param[in] i_pTarget Target from which to search for other targets.
+         *      Must not be NULL.
          *  @param[in] i_type Type of association linking the specified target
          *      to candidate result targets
          *  @param[in] i_recursionLevel Whether to return candidate targets
@@ -741,46 +740,6 @@ class TargetService
         typedef std::vector< NodeSpecificInfo > NodeInfo_t;
 
         /**
-         *  @brief Enum specifying which direction to traverse associations
-         *      between targets
-         *
-         *  Given a general class of association between targets, this enum
-         *  tells the target service which direction to search along an entity
-         *  path for the result targets
-         */
-        enum ASSOCIATION_DIRECTION
-        {
-            INWARDS,  ///< Search for associated targets of the specified target
-                      ///< that happen to be closer to the top level target
-            OUTWARDS, ///< Search for associated targets of the specified target
-                      ///< that happen to be farther from the top level target
-        };
-
-        /**
-         *  @brief Structure mapping an association type to an entity path
-         *      attribute and entity path search direction
-         *
-         *  This map allows the target service to accept an association type
-         *  from a caller and determine the appropriate entity path to search
-         *  along for the result target, and in which direction along the path
-         */
-        struct AssociationAttrMap
-        {
-            ASSOCIATION_TYPE      associationType; ///< Specifies the type of
-                                                   ///< association to traverse
-            ASSOCIATION_DIRECTION associationDir;  ///< Specifies which
-                                                   ///< direction along an
-                                                   ///< entity path to search
-            ATTRIBUTE_ID          attr;            ///< Specifies which entity
-                                                   ///< path to search along
-        };
-
-        /**
-         *  @brief Aliases a vector of association mappings
-         */
-        typedef std::vector< AssociationAttrMap > AssociationMappings_t;
-
-        /**
          *  @brief Returns the first Target from the first initialized node
          *  from the pool of targets.
          *
@@ -831,83 +790,56 @@ class TargetService
          */
         void _maxTargets(NodeSpecificInfo & io_nodeInfoContainer);
 
+
+        //@NEBA
         /**
-         *  @brief Returns handles to the targets associated to the
-         *      target represented by the specified entity path such that the
-         *      results are closer to the top level target than the source
-         *
-         *  Returns handles to the targets associated to the target represented
-         *  by the specified entity path such that the results are closer to the
-         *  top level target than the source.  An IMMEDIATE recursion level
-         *  returns handles to targets that are one association away from the
-         *  target referenced by the supplied entity path.  A recursion level of
-         *  ALL recursively returns results.
-         *
-         *  @param[in] i_attr Entity path attribute that is used as the basis
-         *      for lookups on candidate targets
-         *  @param[in] i_recursionLevel Whether to provide immediate or
-         *      recursive results
-         *  @param[in] i_entityPath Entity path to start search from
-         *  @param[in] i_pPredicate Pointer to a predicate to be evaluated 
-         *      against each candidate target.  If the predicate returns true, 
-         *      the target will be added to the result list.  A value of NULL 
-         *      acts as a predicate that always returns true.
-         *  @param[out] o_list List of returned target handles
+         *  @brief Returns handles targets associated to the specified target in
+         *      a specific way as indicated by the input parameters.  Returns
+         *      results in depth first order.
          *
-         *  @pre Target service must be initialized
+         *  Returns handles to targets associated to the specified target,
+         *  as indicated by an association type.  Based on the specified
+         *  recursion level, the routine will determine the immediate
+         *  associations, or all possible associations.  For example, if caller
+         *  supplies a processor chip target and asks for its children targets,
+         *  the routine will return the next set of targets in the physical
+         *  hierarchy.  Conversely if the caller asks for ALL children targets
+         *  for said source target, the routine will return all targets
+         *  contained within the processor chip.  All searching is peformed as a
+         *  depth first search.  This routine will not clear the caller's input
+         *  list when returning results.
          *
-         *  @post List of target handles corresponding to targets closer to the
-         *      top level target than the one referenced by the specified entity
-         *      path returned
-         */
-        void _getInwards(
-                  ATTRIBUTE_ID      i_attr,
-                  RECURSION_LEVEL   i_recursionLevel,
-                  EntityPath        i_entityPath,
-            const PredicateBase*    i_pPredicate,
-                  TargetHandleList& o_list) const;
-
-        /**
-         *  @brief Returns handles to the targets associated to the
-         *      target represented by the specified entity path such that the
-         *      results are farther from the top level target than the source
-         *
-         *  Returns handles to the targets associated to the target represented
-         *  by the specified entity path such that the results are farther from
-         *  the top level target than the source.  An IMMEDIATE recursion level
-         *  returns handles to targets that are one association away from the
-         *  target referenced by the supplied entity path.  A recursion level of
-         *  ALL recursively returns results.
-         *
-         *  @param[in] i_attr Entity path attribute that is used as the basis
-         *      for lookups on candidate targets
-         *  @param[in] i_recursionLevel Whether to provide immediate or
-         *      recursive results
-         *  @param[in] i_entityPath Entity path to look from
-         *  @param[in] i_pPredicate Pointer to a predicate to be evaluated 
-         *      against each candidate target.  If the predicate returns true, 
-         *      the target will be added to the result list.  A value of NULL 
-         *      acts as a predicate that always returns true.
-         *  @param[out] o_list List of returned target handles
+         *  @param[out] o_list List of target handles that match the specified
+         *      criteria, not cleared by this function.
+         *  @param[in] i_pSourceTarget Target from which to search for other
+         *      targets.  Must not be NULL.  Function presumes caller has
+         *      already screened out NULL targets.
+         *  @param[in] i_type Type of association linking the specified target
+         *      to candidate result targets
+         *  @param[in] i_recursionLevel Whether to return candidate targets
+         *      immediately associated to the specified target or recursively
+         *      associated to it.
+         *  @param[in] i_pPredicate Pointer to a predicate to be evaluated
+         *      against each candidate target (as determined by the source
+         *      target, type, and recursion level parameters).  If the predicate
+         *      returns true, the target will be added to the result list.  A
+         *      value of NULL acts as a predicate that always returns true.
          *
-         *  @pre Target service must be initialized
+         *  @pre Input target must not be NULL
          *
-         *  @post List of target handles corresponding to targets farther from
-         *      the top level target than the one referenced by the specified
-         *      entity path returned.
+         *  @post List of target handles matching the specified criteria
+         *      added to end of caller's list
          */
-        void _getOutwards(
-                  ATTRIBUTE_ID      i_attr,
-                  RECURSION_LEVEL   i_recursionLevel,
-                  EntityPath        i_entityPath,
-            const PredicateBase*    i_pPredicate,
-                  TargetHandleList& o_list ) const;
+        void _getAssociationsViaDfs(
+                  TargetHandleList&    o_list,
+            const Target* const        i_pSourceTarget,
+            const ASSOCIATION_TYPE     i_type,
+            const RECURSION_LEVEL      i_recursionLevel,
+            const PredicateBase* const i_pPredicate) const;
 
         // Instance variables
         bool        iv_initialized; ///< Is service initialized or not
 
-        AssociationMappings_t iv_associationMappings; ///< Association map
-
         NodeInfo_t iv_nodeInfo;
 
         // Disable copy constructor / assignment operator
diff --git a/src/usr/ibscom/test/ibscomtest.H b/src/usr/ibscom/test/ibscomtest.H
index 2988233a9..44e2d7e66 100644
--- a/src/usr/ibscom/test/ibscomtest.H
+++ b/src/usr/ibscom/test/ibscomtest.H
@@ -66,9 +66,11 @@ class IBscomTest: public CxxTest::TestSuite
         TARGETING::PredicateCTM l_cent(TARGETING::CLASS_CHIP,
                                        TARGETING::TYPE_MEMBUF,
                                        TARGETING::MODEL_NA);
-        TARGETING::PredicatePostfixExpr cent_query;
-        cent_query.push(&l_cent);
+        TARGETING::PredicateHwas functionalPredicate;
+        functionalPredicate.functional(true);
 
+        TARGETING::PredicatePostfixExpr cent_query;
+        cent_query.push(&l_cent).push(&functionalPredicate).And();
 
         TARGETING::TargetHandleList centaur_list;
         TARGETING::targetService().
diff --git a/src/usr/targeting/common/targetservice.C b/src/usr/targeting/common/targetservice.C
index 8b699c29a..923b46459 100644
--- a/src/usr/targeting/common/targetservice.C
+++ b/src/usr/targeting/common/targetservice.C
@@ -107,6 +107,19 @@ TargetService::TargetService() :
 {
     #define TARG_FN "TargetService()"
 
+    // Target class in targeting/common/target.H has an array of pointers to
+    // target handles.  Currently there is one pointer for each supported
+    // association type.  The currently supported association types are PARENT,
+    // CHILD. PARENT_BY_AFFINITY, and CHILD_BY_AFFINTY.  The number of pointers
+    // should exactly equal value of TargetService::MAX_ASSOCIATION_TYPES
+    // defined in targeting/common/targetservice.H.  Due to the huge code
+    // changes necessary to directly use that enum value, this compile time
+    // assert enforces that restriction.
+    CPPASSERT(
+     (   (  sizeof( reinterpret_cast<Target*>(0)->iv_ppAssociations)
+          / sizeof( reinterpret_cast<Target*>(0)->iv_ppAssociations[0]) )
+      == (TargetService::MAX_ASSOCIATION_TYPES) ));
+
     #undef TARG_FN
 }
 
@@ -137,22 +150,6 @@ void TargetService::init(const size_t i_maxNodes)
     {
         TARG_INF("Max Nodes to initialize is [%d]", i_maxNodes);
 
-        // Build the association mappings
-        AssociationAttrMap a1 = {PARENT, INWARDS, ATTR_PHYS_PATH};
-        AssociationAttrMap a2 = {CHILD, OUTWARDS, ATTR_PHYS_PATH};
-        AssociationAttrMap a3 = {PARENT_BY_AFFINITY,
-            INWARDS,ATTR_AFFINITY_PATH};
-        AssociationAttrMap a4 = {CHILD_BY_AFFINITY,
-            OUTWARDS,ATTR_AFFINITY_PATH};
-        AssociationAttrMap a5 = {VOLTAGE_SUPPLIER, INWARDS, ATTR_POWER_PATH};
-        AssociationAttrMap a6 = {VOLTAGE_CONSUMER, OUTWARDS, ATTR_POWER_PATH};
-        iv_associationMappings.push_back(a1);
-        iv_associationMappings.push_back(a2);
-        iv_associationMappings.push_back(a3);
-        iv_associationMappings.push_back(a4);
-        iv_associationMappings.push_back(a5);
-        iv_associationMappings.push_back(a6);
-
         for(uint8_t l_nodeCnt=0; l_nodeCnt<i_maxNodes; l_nodeCnt++)
         {
             NodeSpecificInfo l_nodeInfo;
@@ -818,6 +815,59 @@ bool TargetService::tryGetPath(
 }
 
 //******************************************************************************
+// TargetService::_getAssociationsViaDfs
+//******************************************************************************
+
+void TargetService::_getAssociationsViaDfs(
+          TargetHandleList&    o_list,
+    const Target* const        i_pSourceTarget,
+    const ASSOCIATION_TYPE     i_type,
+    const RECURSION_LEVEL      i_recursionLevel,
+    const PredicateBase* const i_pPredicate) const
+{
+    AbstractPointer<Target>* pDestinationTargetItr =
+        TARG_TO_PLAT_PTR(i_pSourceTarget->iv_ppAssociations[i_type]);
+
+    if(TARG_ADDR_TRANSLATION_REQUIRED)
+    {
+        pDestinationTargetItr = static_cast< AbstractPointer<Target>* >(
+            TARG_GET_SINGLETON(TARGETING::theAttrRP).translateAddr(
+                pDestinationTargetItr, i_pSourceTarget));
+    }
+
+    while( static_cast<uint64_t>(*pDestinationTargetItr) )
+    {
+        Target* pDestinationTarget = TARG_TO_PLAT_PTR(
+            *pDestinationTargetItr);
+
+        if(TARG_ADDR_TRANSLATION_REQUIRED)
+        {
+            pDestinationTarget = static_cast<Target*>(
+                TARG_GET_SINGLETON(TARGETING::theAttrRP).translateAddr(
+                    pDestinationTarget, i_pSourceTarget));
+        }
+
+        if(   (!i_pPredicate)
+           || ((*i_pPredicate)(pDestinationTarget)))
+        {
+            o_list.push_back(pDestinationTarget);
+        }
+
+        if(i_recursionLevel == ALL)
+        {
+            (void)_getAssociationsViaDfs(
+                o_list,
+                pDestinationTarget,
+                i_type,
+                i_recursionLevel,
+                i_pPredicate);
+        }
+
+        ++pDestinationTargetItr;
+    }
+}
+
+//******************************************************************************
 // TargetService::getAssociated
 //******************************************************************************
 
@@ -844,43 +894,8 @@ void TargetService::getAssociated(
     // Start with no elements
     o_list.clear();
 
-    // Figure out which attribute to look up
-    for (AssociationMappings_t::const_iterator
-            assocIter = iv_associationMappings.begin();
-            assocIter != iv_associationMappings.end();
-            ++assocIter)
-    {
-        if (i_type == (*assocIter).associationType)
-        {
-            EntityPath l_entityPath;
-
-            bool l_exist = tryGetPath((*assocIter).attr,
-                i_pTarget, l_entityPath);
-
-            if (l_exist)
-            {
-                if ((*assocIter).associationDir == INWARDS)
-                {
-                    (void) _getInwards((*assocIter).attr,
-                        i_recursionLevel, l_entityPath, i_pPredicate, o_list);
-                }
-                else if ((*assocIter).associationDir == OUTWARDS)
-                {
-                    (void) _getOutwards((*assocIter).attr,
-                        i_recursionLevel, l_entityPath, i_pPredicate, o_list);
-                }
-                else
-                {
-                    TARG_ASSERT(0, TARG_LOC
-                           "(*assocIter).associationDir "
-                           "= 0x%X not supported",
-                           (*assocIter).associationDir);
-                }
-            }
-            break;
-        }
-    }
-
+    (void)_getAssociationsViaDfs(
+        o_list,i_pTarget,i_type,i_recursionLevel,i_pPredicate);
     } while (0);
 
     #undef TARG_FN
@@ -1113,107 +1128,6 @@ void TargetService::_maxTargets(NodeSpecificInfo& io_nodeInfoContainer)
 }
 
 //******************************************************************************
-// TargetService::_getInwards
-//******************************************************************************
-
-void TargetService::_getInwards(
-    const ATTRIBUTE_ID         i_attr,
-    const RECURSION_LEVEL      i_recursionLevel,
-          EntityPath           i_entityPath,
-    const PredicateBase* const i_pPredicate,
-          TargetHandleList&    o_list) const
-{
-    #define TARG_FN "_getInwards(...)"
-
-    while (i_entityPath.size() > 1)
-    {
-        i_entityPath.removeLast();
-
-        TargetIterator l_allTargets;
-
-        for(l_allTargets = targetService().begin();
-            l_allTargets != targetService().end();
-            ++l_allTargets)
-        {
-            EntityPath l_candidatePath;
-            bool l_candidateFound = false;
-
-            l_candidateFound = tryGetPath(i_attr,
-                                   (*l_allTargets),
-                                   l_candidatePath);
-
-            if ( (l_candidateFound)
-                    && (l_candidatePath == i_entityPath)
-                    && (   (i_pPredicate == NULL)
-                        || (*i_pPredicate)(*l_allTargets) ) )
-            {
-                o_list.push_back(*l_allTargets);
-                break;
-            }
-        }
-
-        if (i_recursionLevel == IMMEDIATE)
-        {
-            break;
-        }
-    }
-
-    #undef TARG_FN
-}
-
-//******************************************************************************
-// TargetService::_getOutwards
-//******************************************************************************
-
-void TargetService::_getOutwards(
-    const ATTRIBUTE_ID         i_attr,
-    const RECURSION_LEVEL      i_recursionLevel,
-          EntityPath           i_entityPath,
-    const PredicateBase* const i_pPredicate,
-          TargetHandleList&    o_list) const
-{
-    #define TARG_FN "_getOutwards(...)"
-    do
-    {
-        // If at max depth (a leaf path element), no children possible
-        if (i_entityPath.size() >= EntityPath::MAX_PATH_ELEMENTS)
-        {
-            break;
-        }
-
-        // Find the children (immediate, or all), depending on recursion level
-        TargetIterator l_allTargets;
-
-        for(l_allTargets = targetService().begin();
-            l_allTargets != targetService().end();
-            ++l_allTargets)
-        {
-            EntityPath l_candidatePath;
-            bool l_candidateFound = tryGetPath(i_attr, *l_allTargets,
-                                        l_candidatePath);
-            if (l_candidateFound)
-            {
-                if ( ( (i_recursionLevel == IMMEDIATE)
-                          && (l_candidatePath.size() == i_entityPath.size() +1))
-                        || (   (i_recursionLevel == ALL)
-                            && (l_candidatePath.size() > i_entityPath.size())))
-                {
-                    if (i_entityPath.equals(l_candidatePath,i_entityPath.size())
-                           && (  (i_pPredicate == NULL)
-                                || (*i_pPredicate)(*l_allTargets) ) )
-                    {
-                        o_list.push_back(*l_allTargets);
-                    }
-                }
-            }
-        }
-
-    } while (0);
-
-    #undef TARG_FN
-}
-
-//******************************************************************************
 // TargetService::setMasterNode
 //******************************************************************************
 errlHndl_t TargetService::setMasterNode(const Target* i_pTarget)
diff --git a/src/usr/targeting/common/xmltohb/xmltohb.pl b/src/usr/targeting/common/xmltohb/xmltohb.pl
index ddf4f8775..e2fa6e6f1 100755
--- a/src/usr/targeting/common/xmltohb/xmltohb.pl
+++ b/src/usr/targeting/common/xmltohb/xmltohb.pl
@@ -45,6 +45,7 @@ use XML::Simple;
 use Text::Wrap;
 use Data::Dumper;
 use POSIX;
+use Env;
 
 ################################################################################
 # Set PREFERRED_PARSER to XML::Parser. Otherwise it uses XML::SAX which contains
@@ -119,6 +120,34 @@ if($cfgVerbose)
 use constant INVALID_HUID=>0xffffffff;
 use constant PEER_HUID_NOT_PRESENT=>0xfffffffe;
 
+# When computing associations between targets, always store the association list
+# pointers in this exact order within each target object.  It also must be the
+# case that the ASSOCIATION_TYPE enum in the target service header must declare
+# the corresponding enum values in this order as well
+use constant PARENT_BY_CONTAINMENT => "ParentByContainment";
+use constant CHILD_BY_CONTAINMENT => "ChildByContainment";
+use constant PARENT_BY_AFFINITY => "ParentByAffinity";
+use constant CHILD_BY_AFFINITY => "ChildByAffinity";
+my @associationTypes = ( PARENT_BY_CONTAINMENT,
+    CHILD_BY_CONTAINMENT, PARENT_BY_AFFINITY, CHILD_BY_AFFINITY );
+
+# Constants for attribute names (minus ATTR_ prefix)
+use constant ATTR_PHYS_PATH => "PHYS_PATH";
+use constant ATTR_AFFINITY_PATH => "AFFINITY_PATH";
+use constant ATTR_UNKNOWN => "UnknownAttributeName";
+
+# Data manipulation constants
+use constant BITS_PER_BYTE => 8;
+use constant LOW_BYTE_MASK => 0xFF;
+use constant BYTE_RIGHT_BIT_INDEX => BITS_PER_BYTE - 1;
+use constant BYTES_PER_ABSTRACT_POINTER => 8;
+
+# This is the maximum total sum of (compute nodes + control nodes) possible for
+# any known system using this attribute compiler.  It is used to reserve
+# space in each system target's CHILD + CHILD_BY_AFFINITY association lists
+# so that FSP can link a system target to multiple nodes
+use constant MAX_COMPUTE_AND_CONTROL_NODE_SUM => 5;
+
 my $xml = new XML::Simple (KeyAttr=>[]);
 use Digest::MD5 qw(md5_hex);
 
@@ -4646,6 +4675,308 @@ sub getPnorBaseAddress {
 }
 
 ################################################################################
+# Given a number, return a decimal/hexidecimal pair (for debug)
+################################################################################
+
+sub toDecAndHex
+{
+    my ($val) = @_;
+    return "$val/" .  sprintf("0x%016X",$val);
+}
+
+################################################################################
+# Trace association code entry (for debug)
+################################################################################
+
+sub ASSOC_ENTER
+{
+    if($ENV{"ASSOC_FUNC"} eq "1")
+    {
+        my ($trace) = @_;
+        my ($package, $filename, $line, $undef, $hasargs, $wantarray, $evaltext,
+            $is_require, $hints, $bitmask, $hinthash) = caller (0);
+        my (undef,undef,undef,$subroutine) = caller (1);
+        print STDERR "ENTER>> Function $subroutine, Line: $line\n";
+        print STDERR "    " . $trace . "\n";
+    }
+}
+
+################################################################################
+# Trace association code exit (for debug)
+################################################################################
+
+sub ASSOC_EXIT
+{
+    if($ENV{"ASSOC_FUNC"} eq "1")
+    {
+        my ($trace) = @_;
+        my ($package, $filename, $line, $undef, $hasargs, $wantarray, $evaltext,
+            $is_require, $hints, $bitmask, $hinthash) = caller (0);
+        my (undef,undef,undef,$subroutine) = caller (1);
+        print STDERR "EXIT>> Function $subroutine, Line: $line\n";
+        print STDERR "    " . $trace . "\n";
+    }
+}
+
+################################################################################
+# Trace association code debug statements
+################################################################################
+
+sub ASSOC_DBG
+{
+    if($ENV{"ASSOC_DBG"} eq "1")
+    {
+        my ($trace) = @_;
+        my ($package, $filename, $line, $subroutine, $hasargs, $wantarray,
+            $evaltext, $is_require, $hints, $bitmask, $hinthash) = caller (0);
+        print STDERR "DEBUG($line): " . $trace . "\n";
+    }
+}
+
+################################################################################
+# Trace association code important statements
+################################################################################
+
+sub ASSOC_IMP
+{
+    if($ENV{"ASSOC_IMP"} eq "1")
+    {
+        my ($trace) = @_;
+        my ($package, $filename, $line, $subroutine, $hasargs, $wantarray,
+            $evaltext, $is_require, $hints, $bitmask, $hinthash) = caller (0);
+        print STDERR "IMP($line): " . $trace . "\n";
+    }
+}
+
+################################################################################
+# Given an association type, return name of corresponding attribute
+################################################################################
+
+sub getAttributeNameForAssociationTypeOf
+{
+    my ($associationType) = @_;
+
+    my $attributeName = ATTR_UNKNOWN;
+    if(   ($associationType eq PARENT_BY_CONTAINMENT)
+       || ($associationType eq CHILD_BY_CONTAINMENT))
+    {
+        $attributeName = ATTR_PHYS_PATH;
+    }
+    elsif (   ($associationType eq PARENT_BY_AFFINITY)
+           || ($associationType eq CHILD_BY_AFFINITY))
+    {
+        $attributeName = ATTR_AFFINITY_PATH;
+    }
+    else
+    {
+        fatal (  "FATAL ERROR! Couldn't determine attribute name for "
+               . "$associationType associationType");
+    }
+    return $attributeName;
+}
+
+################################################################################
+# For a given target, compute parent/children of given type
+################################################################################
+
+sub buildAssociations
+{
+    my ($targetAddrHashRef, $targetId,
+        $associationType, $offsetToTargetsInBinary) = @_;
+
+    ASSOC_ENTER("targetId = $targetId, associationType = $associationType, " .
+        "offsetToTargetsInBinary = " . toDecAndHex($offsetToTargetsInBinary) );
+
+    my $attributeName = getAttributeNameForAssociationTypeOf($associationType);
+
+    # Look at all targets except the one given as input, and see if any
+    # of them have entity paths which are immediate children or parents
+    # of this target
+    foreach my $id (keys %$targetAddrHashRef)
+    {
+        # Skip input target
+        if($id eq $targetId)
+        {
+            next;
+        }
+
+        if($attributeName eq ATTR_PHYS_PATH)
+        {
+            my $destPath = $targetAddrHashRef->{$id}{$attributeName};
+            my $targetPath = $targetAddrHashRef->{$targetId}{$attributeName};
+            if($associationType eq PARENT_BY_CONTAINMENT)
+            {
+                # Parent path matches current target's entity path except
+                # missing last path component
+                my $index = rindex $targetPath, "/";
+                my $parentPath = substr $targetPath , 0, $index;
+                ASSOC_DBG("GIVEN: Current physical path = $targetPath");
+                ASSOC_DBG("CHECKING: Candidate parent physical path "
+                          . "= $destPath");
+                ASSOC_DBG("CHECKING: Parent of current physical path "
+                          . "= $parentPath");
+                if($parentPath eq $destPath)
+                {
+                    ASSOC_IMP("FOUND: parent physical path "
+                              . "= $destPath ($targetPath)");
+                    unshift
+                         @ { $targetAddrHashRef->{$targetId}
+                                 {ParentByContainmentAssociations} },
+                         $offsetToTargetsInBinary + $targetAddrHashRef->{$id}
+                            {OffsetToTargetWithinTargetList};
+                    last;
+                }
+            }
+            elsif($associationType eq CHILD_BY_CONTAINMENT)
+            {
+                # Child path matches current target's entity path except there
+                # is one extraneous path component at end
+                my $index = rindex $destPath , "/";
+                my $parentOfDestPath = substr $destPath , 0, $index;
+                ASSOC_DBG("GIVEN: Current physical path = $targetPath");
+                ASSOC_DBG("CHECKING: Candidate child physical path "
+                          . "= $destPath");
+                ASSOC_DBG("CHECKING: Parent of child physical path "
+                          . "= $parentOfDestPath");
+                if($parentOfDestPath eq $targetPath )
+                {
+                    ASSOC_IMP("FOUND: Child physical path "
+                              . "= $destPath ($targetPath)");
+                    unshift
+                         @ { $targetAddrHashRef->{$targetId}
+                                 {ChildByContainmentAssociations} },
+                        $offsetToTargetsInBinary + $targetAddrHashRef->{$id}
+                            {OffsetToTargetWithinTargetList};
+                }
+            }
+        }
+        elsif($attributeName eq ATTR_AFFINITY_PATH)
+        {
+            my $destPath = $targetAddrHashRef->{$id}{$attributeName};
+            my $targetPath = $targetAddrHashRef->{$targetId}{$attributeName};
+            if($associationType eq PARENT_BY_AFFINITY)
+            {
+                # Parent path matches current target's entity path except
+                # missing last path component
+                my $index = rindex $targetPath, "/";
+                my $parentPath = substr $targetPath , 0, $index;
+                ASSOC_DBG("GIVEN: Current affinty path = $targetPath");
+                ASSOC_DBG("CHECKING: Candidate parent affinity path "
+                          . "= $destPath");
+                ASSOC_DBG("CHECKING: Parent of current affinity path "
+                          . "= $parentPath");
+                if($parentPath eq $destPath)
+                {
+                    ASSOC_IMP("FOUND: parent affinty path "
+                              . "= $destPath ($targetPath)");
+                    unshift
+                         @ { $targetAddrHashRef->{$targetId}
+                                 {ParentByAffinityAssociations} },
+                         $offsetToTargetsInBinary + $targetAddrHashRef->{$id}
+                             {OffsetToTargetWithinTargetList};
+                    last;
+                }
+            }
+            elsif($associationType eq CHILD_BY_AFFINITY)
+            {
+                # Child path matches current target's entity path except there
+                # is one extraneous path component at end
+                my $index = rindex $destPath , "/";
+                my $parentOfDestPath = substr $destPath , 0, $index;
+                ASSOC_DBG("GIVEN: Current affinty path = $targetPath");
+                ASSOC_DBG("CHECKING: Candidate child affinity path "
+                          . "= $destPath");
+                ASSOC_DBG("CHECKING: Parent of child affinty path "
+                          . "= $parentOfDestPath");
+                if($parentOfDestPath eq $targetPath )
+                {
+                    ASSOC_IMP("FOUND: Child affinity path "
+                              . "= $destPath ($targetPath)");
+                    unshift
+                         @ { $targetAddrHashRef->{$targetId}
+                                 {ChildByAffinityAssociations} },
+                        $offsetToTargetsInBinary + $targetAddrHashRef->{$id}
+                            {OffsetToTargetWithinTargetList};
+                }
+            }
+        }
+    }
+    ASSOC_EXIT();
+}
+
+################################################################################
+# Update dummy pointers with real pointers in binary blob of target structs
+################################################################################
+
+sub updateTargetAssociationPointers
+{
+    my ( $targetAddrHashRef, $targetsBinDataRef ) = @_;
+
+    ASSOC_ENTER();
+
+    foreach my $id ( keys %$targetAddrHashRef )
+    {
+        ASSOC_DBG("Fixing up target with ID = $id");
+        foreach my $associationType (@associationTypes)
+        {
+            # Seek to pointer location within target object and replace the
+            # dummy value with the real value
+            my $seek = $targetAddrHashRef->{$id}{
+                "offsetToPtrTo" . $associationType . "Associations"};
+            my $pointer = $targetAddrHashRef->{$id}{ $associationType . "Ptr" };
+            ASSOC_DBG("Seeking to offset: $seek");
+            ASSOC_DBG("Writing pointer value of: " . toDecAndHex($pointer) );
+            for(my $pointerByte=0; $pointerByte<8; ++$pointerByte)
+            {
+                vec($$targetsBinDataRef, $seek+$pointerByte,BITS_PER_BYTE) =
+                    (($pointer >> ((BYTE_RIGHT_BIT_INDEX-$pointerByte)
+                        *BITS_PER_BYTE)) & LOW_BYTE_MASK);
+            }
+        }
+    }
+
+    ASSOC_EXIT();
+}
+
+################################################################################
+# Serialize association data into a binary blob
+################################################################################
+
+sub serializeAssociations
+{
+    my ($offsetWithinBinary, $targetsAoHRef, $targetAddrHashRef,
+        $associationsBinDataRef ) = @_;
+    ASSOC_ENTER();
+
+    foreach my $targetInstance (@$targetsAoHRef)
+    {
+        my $id = $targetInstance->{id};
+        ASSOC_DBG("Serializing target = $id");
+        foreach my $associationType (@associationTypes)
+        {
+            $targetAddrHashRef->{$id}{ $associationType . "Ptr" }
+                = $offsetWithinBinary;
+            ASSOC_DBG("Offset within binary = $offsetWithinBinary");
+            my $pointers = "Association = $associationType, pointers = ";
+            foreach my $pointer ( @ { $targetAddrHashRef->{$id}
+                                          { $associationType . "Associations"}})
+            {
+                $$associationsBinDataRef .= pack8byte($pointer);
+                $offsetWithinBinary += BYTES_PER_ABSTRACT_POINTER;
+                $pointers .= toDecAndHex($pointer);
+                $pointers .= ", ";
+            }
+            chomp($pointers);
+            chomp($pointers);
+            ASSOC_DBG($pointers);
+        }
+    }
+    my $associationsBinDataSize = length $$associationsBinDataRef;
+    ASSOC_IMP("Size of association section = $associationsBinDataSize");
+    ASSOC_EXIT();
+}
+
+################################################################################
 # Write the PNOR targeting image
 ################################################################################
 
@@ -4819,6 +5150,11 @@ sub generateTargetingImage {
     # Ensure consistent ordering of target instances
     my $attrAddr = $pnorRoBaseAddress + $startOfAttributePointers;
 
+    # Configure globals for computing associations
+    my %targetAddrHash = ();
+    my $offsetWithinTargets = 0;
+    my @NullPtrArray = ( 0 ) ;
+
     foreach my $targetInstance (@targetsAoH)
     {
         my $data;
@@ -4829,6 +5165,10 @@ sub generateTargetingImage {
          # print "        offset:  ",
          # $attributeListTypeHoH{$targetInstance->{type}}{offset}, "\n" ;
 
+        # Keep track of where this target is from start of targets
+        $targetAddrHash{$targetInstance->{id}}{OffsetToTargetWithinTargetList}
+            = $offsetWithinTargets;
+
         # Create target record
         $data .= pack4byte(
             $attributeListTypeHoH{$targetInstance->{type}}{elements});
@@ -4836,11 +5176,69 @@ sub generateTargetingImage {
               $attributeListTypeHoH{$targetInstance->{type}}{offset}
             + $pnorRoBaseAddress);
         $data .= pack8byte($attrAddr);
+
+        # Make note of the offsets within the blob of targets where each pointer
+        # for each association list is.  Also reserve each pointer with an
+        # invalid value for now.
+        use constant INVALID_POINTER => 0;
+        my $ptrToParentByContainmentAssociations = INVALID_POINTER;
+        my $ptrToChildByContainmentAssociations = INVALID_POINTER;
+        my $ptrToParentByAffinityAssociations = INVALID_POINTER;
+        my $ptrToChildByAffinityAssociations = INVALID_POINTER;
+
+        my $id = $targetInstance->{id};
+        $targetAddrHash{$id}{offsetToPtrToParentByContainmentAssociations} =
+            $offsetWithinTargets + length $data;
+        $data .= pack8byte($ptrToParentByContainmentAssociations);
+
+        $targetAddrHash{$id}{offsetToPtrToChildByContainmentAssociations} =
+            $offsetWithinTargets + length $data;
+        $data .= pack8byte($ptrToChildByContainmentAssociations);
+
+        $targetAddrHash{$id}{offsetToPtrToParentByAffinityAssociations} =
+            $offsetWithinTargets + length $data;
+        $data .= pack8byte($ptrToParentByAffinityAssociations);
+
+        $targetAddrHash{$id}{offsetToPtrToChildByAffinityAssociations} =
+            $offsetWithinTargets + length $data;
+        $data .= pack8byte($ptrToChildByAffinityAssociations);
+
+        $targetAddrHash{$id}{ParentByContainmentAssociations} = [@NullPtrArray];
+        $targetAddrHash{$id}{ChildByContainmentAssociations} = [@NullPtrArray];
+        $targetAddrHash{$id}{ParentByAffinityAssociations} = [@NullPtrArray];
+        $targetAddrHash{$id}{ChildByAffinityAssociations} = [@NullPtrArray];
+
+        if($id =~/^sys\d+$/)
+        {
+            ASSOC_DBG("Found system target of $id, reserving space");
+            for(my $reserved = 0;
+                $reserved < MAX_COMPUTE_AND_CONTROL_NODE_SUM - 1; ++$reserved)
+            {
+                unshift
+                    @ { $targetAddrHash{$id}{ChildByContainmentAssociations} },
+                    0;
+                unshift
+                    @ { $targetAddrHash{$id}{ChildByAffinityAssociations} },
+                    0;
+            }
+        }
+
+        ASSOC_DBG("Target ID = $id");
+        ASSOC_DBG("Offset within targets to ptr to parent containment list = "
+        . "$targetAddrHash{$id}{offsetToPtrToParentByContainmentAssociations}");
+        ASSOC_DBG("Offset within targets to ptr to child containment list = "
+        . "$targetAddrHash{$id}{offsetToPtrToChildByContainmentAssociations}");
+        ASSOC_DBG("Offset within targets to ptr to parent affinit list = "
+        . "$targetAddrHash{$id}{offsetToPtrToParentByAffinityAssociations}");
+        ASSOC_DBG("Offset within targets to ptr to child affinity list = "
+        . "$targetAddrHash{$id}{offsetToPtrToChildByAffinityAssociations}");
+
         $attrAddr += $attributeListTypeHoH{$targetInstance->{type}}{elements}
             * (length pack8byte(0));
 
         # Increment the offset
         $offset += (length $data);
+        $offsetWithinTargets += (length $data);
 
         # Add it to the target sub-section
         $targetsBinData .= $data;
@@ -4894,6 +5292,15 @@ sub generateTargetingImage {
                 (keys %attrhash)
             )
         {
+            # Save each target's physical + affinity path for association
+            # processing later on
+            if(   ($attributeId eq ATTR_PHYS_PATH)
+               || ($attributeId eq ATTR_AFFINITY_PATH) )
+            {
+                $targetAddrHash{$targetInstance->{id}}{$attributeId} =
+                    $attrhash{$attributeId}->{default};
+            }
+
             my $attrValue =
             enumNameToValue($attributeIdEnumeration,$attributeId);
             $attrValue = sprintf ("%0x", $attrValue);
@@ -4982,7 +5389,12 @@ sub generateTargetingImage {
                     ($attrhash{$attributeId}->{default} != 0))
                 {
                     my $index = $attrhash{$attributeId}->{default} - 1;
-                    $index *= 20; # length(N + quad + quad)
+
+                    # Each target is 4 bytes # attributes, 8 bytes pointer
+                    # to attribute list, 8 bytes pointer to attribute pointer
+                    # list, 4 x 8 byte pointers to association lists, for total
+                    # of 20 + 32 = 52 bytes per target
+                    $index *= (20 + 32); # length(N + quad + quad + 4x quad)
                     $attrhash{$attributeId}->{default} = $index + $firstTgtPtr;
                 }
 
@@ -5233,6 +5645,35 @@ sub generateTargetingImage {
               . "what was written to PNOR, $attributesWritten.");
     }
 
+    # Build the parent/child relationships for all targets
+    foreach my $targetInstance (@targetsAoH)
+    {
+        foreach my $associationType (@associationTypes)
+        {
+            buildAssociations(
+                \%targetAddrHash,
+                $targetInstance->{id},
+                $associationType,
+                $firstTgtPtr)
+        }
+    }
+
+    # Serialize the association lists into a blob
+    my $associationsBinData;
+    my $offsetToAssociationsFromTargets =
+        (length $targetsBinData) + (length $roAttrBinData);
+    serializeAssociations( $firstTgtPtr + $offsetToAssociationsFromTargets,
+        \@targetsAoH, \%targetAddrHash, \$associationsBinData);
+    my $associationsBinDataSize = length $associationsBinData;
+    ASSOC_IMP("Size of association section, redundant calculation "
+              . "= $associationsBinDataSize");
+
+    # Fix up the target bin blob to point to the right association lists
+    updateTargetAssociationPointers(\%targetAddrHash, \$targetsBinData);
+
+    # Size of PNOR RO increases by size of associations
+    $offset += $associationsBinDataSize;
+
     # Build header data
 
     my $headerBinData;
@@ -5369,8 +5810,21 @@ sub generateTargetingImage {
     $outFile .= $attributeListBinData;
     $outFile .= $attributePointerBinData;
     $outFile .= $numTargetsBinData;
+
+    my $offsetOfTargets = length $outFile;
+    my $sizeOfTargets = length $targetsBinData;
+    my $offsetToAssociationsFromTargets =
+        (length $targetsBinData) + (length $roAttrBinData);
+    ASSOC_DBG("Offset of targets within targeting binary = $offsetOfTargets");
+    ASSOC_DBG("Size of targets within targeting binary = $sizeOfTargets");
+    ASSOC_DBG("Offset to associations from start of targets "
+              . "= $offsetToAssociationsFromTargets");
+
     $outFile .= $targetsBinData;
     $outFile .= $roAttrBinData;
+
+    $outFile .= $associationsBinData;
+
     $outFile .= pack ("@".($sectionHoH{pnorRo}{size} - $offset));
 
     # Serialize PNOR RW section to multiple of 4k page size (pad if necessary)