path: root/src/vendorcode/amd/agesa/f12/Proc/HT/Features/htFeatRouting.c

/* $NoKeywords:$ */
/**
 * @file
 *
 * Routing Routines
 *
 * Contains routines for isomorphic topology matching,
 * routing determination, and routing initialization.
 *
 * @xrefitem bom "File Content Label" "Release Content"
 * @e project:      AGESA
 * @e sub-project:  HyperTransport
 * @e \$Revision: 44324 $   @e \$Date: 2010-12-22 17:16:51 +0800 (Wed, 22 Dec 2010) $
 *
 */
/*
*****************************************************************************
*
* Copyright (c) 2011, Advanced Micro Devices, Inc.
 * All rights reserved.
 *
 * Redistribution and use in source and binary forms, with or without
 * modification, are permitted provided that the following conditions are met:
 *     * Redistributions of source code must retain the above copyright
 *       notice, this list of conditions and the following disclaimer.
 *     * Redistributions in binary form must reproduce the above copyright
 *       notice, this list of conditions and the following disclaimer in the
 *       documentation and/or other materials provided with the distribution.
 *     * Neither the name of Advanced Micro Devices, Inc. nor the names of
 *       its contributors may be used to endorse or promote products derived
 *       from this software without specific prior written permission.
 *
 * THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS "AS IS" AND
 * ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE IMPLIED
 * WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE ARE
 * DISCLAIMED. IN NO EVENT SHALL ADVANCED MICRO DEVICES, INC. BE LIABLE FOR ANY
 * DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES
 * (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES;
 * LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND
 * ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT
 * (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE OF THIS
 * SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
* ***************************************************************************
*
*/

/*
 *----------------------------------------------------------------------------
 *                                MODULES USED
 *
 *----------------------------------------------------------------------------
 */



#include "AGESA.h"
#include "Ids.h"
#include "Topology.h"
#include "htFeat.h"
#include "htInterface.h"
#include "htNotify.h"
#include "htNb.h"
#include "htGraph.h"
#include "htFeatRouting.h"
#include "htTopologies.h"
#include "Filecode.h"
CODE_GROUP (G1_PEICC)
RDATA_GROUP (G1_PEICC)

#define FILECODE PROC_HT_FEATURES_HTFEATROUTING_FILECODE
/*----------------------------------------------------------------------------
 *                          DEFINITIONS AND MACROS
 *
 *----------------------------------------------------------------------------
 */

/*----------------------------------------------------------------------------
 *                           TYPEDEFS AND STRUCTURES
 *
 *----------------------------------------------------------------------------
 */
typedef struct {
  UINT8   **CurrentPosition;
  BOOLEAN IsCustomList;
} TOPOLOGY_CONTEXT;

/*----------------------------------------------------------------------------
 *                        PROTOTYPES OF LOCAL FUNCTIONS
 *
 *----------------------------------------------------------------------------
 */

/*----------------------------------------------------------------------------
 *                            EXPORTED FUNCTIONS
 *
 *----------------------------------------------------------------------------
 */

/*----------------------------------------------------------------------------
 *                              LOCAL FUNCTIONS
 *
 *----------------------------------------------------------------------------
 */

/***************************************************************************
 ***          ISOMORPHISM BASED ROUTING TABLE GENERATION CODE            ***
 ***************************************************************************/

/*----------------------------------------------------------------------------------------*/
/**
 * Return the Link on source Node which connects to target Node
 *
 * @param[in] SourceNode   The Node on which to find the Link
 * @param[in] TargetNode   The Link will connect to this Node
 * @param[in] State        Our global state
 *
 * @return    the Link to target
 */
UINT8
STATIC
FindLinkToNode (
  IN       UINT8        SourceNode,
  IN       UINT8        TargetNode,
  IN       STATE_DATA   *State
  )
{
  UINT8 TargetLink;
  UINT8 k;

  // A node linked to itself is not a supported topology graph, this is probably an error in the
  // topology data.  There is not going to be a portlist match for it.
  ASSERT (SourceNode != TargetNode);
  TargetLink = INVALID_LINK;
  for (k = 0; k < State->TotalLinks*2; k += 2) {
    if (((*State->PortList)[k].NodeID == SourceNode) && ((*State->PortList)[k + 1].NodeID == TargetNode)) {
      TargetLink = (*State->PortList)[k].Link;
      break;
    } else if (((*State->PortList)[k + 1].NodeID == SourceNode) && ((*State->PortList)[k].NodeID == TargetNode)) {
      TargetLink = (*State->PortList)[k + 1].Link;
      break;
    }
  }
  ASSERT (TargetLink != INVALID_LINK);

  return TargetLink;
}

/*----------------------------------------------------------------------------------------*/
/**
 *      Is graphA isomorphic to graphB?
 *
 *  If this function returns true, then Perm will contain the permutation
 *  required to transform graphB into graphA.
 *  We also use the degree of each Node, that is the number of connections it has, to
 *  speed up rejection of non-isomorphic graphs (if there is a Node in graphA with n
 *  connections, there must be at least one unmatched in graphB with n connections).
 *
 * @param[in]     Node     the discovered Node which we are trying to match
 *                      with a permutation the topology
 * @param[in,out] State our global state, degree and adjacency matrix,
 *                      output a permutation if successful
 * @retval TRUE         the graphs are isomorphic
 * @retval FALSE        the graphs are not isomorphic
 *
 */
BOOLEAN
STATIC
IsIsomorphic (
  IN       UINT8         Node,
  IN OUT   STATE_DATA    *State
  )
{
  UINT8 j;
  UINT8 k;
  UINT8 Nodecnt;

  // We have only been called if Nodecnt == pSelected->size !
  Nodecnt = State->NodesDiscovered + 1;

  if (Node != Nodecnt) {
    // Keep building the permutation
    for (j = 0; j < Nodecnt; j++) {
      // Make sure the degree matches
      if (State->Fabric->SysDegree[Node] != State->Fabric->DbDegree[j]) {
        continue;
      }

      // Make sure that j hasn't been used yet (ought to use a "used"
      // array instead, might be faster)
      for (k = 0; k < Node; k++) {
        if (State->Fabric->Perm[k] == j) {
          break;
        }
      }
      if (k != Node) {
        continue;
      }
      State->Fabric->Perm[Node] = j;
      if (IsIsomorphic (Node + 1, State)) {
        return TRUE;
      }
    }
    return FALSE;
  } else {
    // Test to see if the permutation is isomorphic
    for (j = 0; j < Nodecnt; j++) {
      for (k = 0; k < Nodecnt; k++) {
        if (State->Fabric->SysMatrix[j][k] != State->Fabric->DbMatrix[State->Fabric->Perm[j]][State->Fabric->Perm[k]] ) {
          return FALSE;
        }
      }
    }
    return TRUE;
  }
}

/*----------------------------------------------------------------------------------------*/
/**
 * Set Topology List iterator context to the Beginning and provide the first topology.
 *
 * Check the interface for a custom topology list.  If one is found, set context to the
 * first item, and return that item. Otherwise return the first item in the built in list.
 *
 * @param[in,out] TopologyContextHandle  Initialize this context to beginning of lists.
 * @param[out]     NextTopology           The next topology, NULL if end.
 * @param[in]      State                  Access to interface, handles.
 *
 */
VOID
STATIC
BeginTopologies (
     OUT   TOPOLOGY_CONTEXT  *TopologyContextHandle,
     OUT   UINT8             **NextTopology,
  IN       STATE_DATA        *State
  )
{
  if (State->HtBlock->Topolist != NULL) {
    // Start with a custom list
    TopologyContextHandle->CurrentPosition = State->HtBlock->Topolist;
    TopologyContextHandle->IsCustomList = TRUE;
  } else {
    // Start with the built in list
    GetAmdTopolist (&TopologyContextHandle->CurrentPosition);
    TopologyContextHandle->IsCustomList = FALSE;
  }
  *NextTopology = *TopologyContextHandle->CurrentPosition;
}

/*----------------------------------------------------------------------------------------*/
/**
 * Iterate through available topologies.
 *
 * Increment to the next list item.  If we are doing a custom list, when we reach the end
 * switch to the built in list.
 *
 * @param[in,out]  TopologyContextHandle  Maintain iterator's context from one call to the next
 * @param[out]     NextTopology           The next topology, NULL if end.
 *
 */
VOID
STATIC
GetNextTopology (
  IN OUT   TOPOLOGY_CONTEXT  *TopologyContextHandle,
     OUT   UINT8             **NextTopology
  )
{
  // Not valid to continue calling this routine after reaching the end.
  ASSERT (TopologyContextHandle->CurrentPosition != NULL);

  if (TopologyContextHandle->IsCustomList) {
    // We are iterating the custom list from the interface.
    TopologyContextHandle->CurrentPosition++;
    if (*TopologyContextHandle->CurrentPosition == NULL) {
      // We are at the end of the custom list, switch to the built in list.
      TopologyContextHandle->IsCustomList = FALSE;
      GetAmdTopolist (&TopologyContextHandle->CurrentPosition);
    }
  } else {
    // We are iterating the built in list
    TopologyContextHandle->CurrentPosition++;
    // If we are at the end of the built in list, NextTopology == NULL is the AtEnd.
  }
  *NextTopology = *TopologyContextHandle->CurrentPosition;
}

/*----------------------------------------------------------------------------------------*/
/**
 * Using the description of the fabric topology we discovered, try to find a match
 * among the supported topologies.
 *
 * @HtFeatMethod{::F_LOOKUP_COMPUTE_AND_LOAD_ROUTING_TABLES}
 *
 * A supported topology description matches the discovered fabric if the Nodes can be
 * matched in such a way that all the Nodes connected in one set are exactly the
 * Nodes connected in the other (formally, that the graphs are isomorphic).  Which
 * Links are used is not really important to matching.  If the graphs match, then
 * there is a permutation of one that translates the Node positions and Linkages to
 * the other.
 *
 * In order to make the isomorphism test efficient, we test for matched number of Nodes
 * (a 4 Node fabric is not isomorphic to a 2 Node topology), and provide degrees of Nodes
 * to the isomorphism test.
 *
 * The generic routing table solution for any topology is predetermined and represented
 * as part of the topology.  The permutation we computed tells us how to interpret the
 * routing onto the fabric we discovered.  We do this working backward from the last
 * Node discovered to the BSP, writing the routing tables as we go.
 *
 * @param[in,out]    State    the discovered fabric, degree matrix, permutation
 *
 */
VOID
LookupComputeAndLoadRoutingTables (
  IN OUT   STATE_DATA    *State
  )
{
  TOPOLOGY_CONTEXT   TopologyContextHandle;
  UINT8 *Selected;
  UINT8 Size;
  UINT8 PairCounter;
  UINT8 ReqTargetLink;
  UINT8 RspTargetLink;
  UINT8 ReqTargetNode;
  UINT8 RspTargetNode;
  UINT8 AbstractBcTargetNodes;
  UINT32 BcTargetLinks;
  UINT8 NodeCounter;
  UINT8 NodeBeingRouted;
  UINT8 NodeRoutedTo;
  UINT8 BroadcastSourceNode;

  Size = State->NodesDiscovered + 1;
  BeginTopologies (&TopologyContextHandle, &Selected, State);
  while (Selected != NULL) {
    if (GraphHowManyNodes (Selected) == Size) {
      // Build Degree vector and Adjacency Matrix for this entry
      for (NodeCounter = 0; NodeCounter < Size; NodeCounter++) {
        State->Fabric->DbDegree[NodeCounter] = 0;
        for (PairCounter = 0; PairCounter < Size; PairCounter++) {
          if (GraphIsAdjacent (Selected, NodeCounter, PairCounter)) {
            State->Fabric->DbMatrix[NodeCounter][PairCounter] = TRUE;
            State->Fabric->DbDegree[NodeCounter]++;
          } else {
            State->Fabric->DbMatrix[NodeCounter][PairCounter] = FALSE;
          }
        }
      }

      if (IsIsomorphic (0, State)) {
        break;  // A matching topology was found
      }
    }
    GetNextTopology (&TopologyContextHandle, &Selected);
  }

  if (Selected != NULL) {
    // Compute the reverse Permutation
    for (NodeCounter = 0; NodeCounter < Size; NodeCounter++) {
      State->Fabric->ReversePerm[State->Fabric->Perm[NodeCounter]] = NodeCounter;
    }

    // Start with the last discovered Node, and move towards the BSP
    for (NodeCounter = 0; NodeCounter < Size; NodeCounter++) {
      NodeBeingRouted = ((Size - 1) - NodeCounter);
      for (NodeRoutedTo = 0; NodeRoutedTo < Size; NodeRoutedTo++) {
        BcTargetLinks = 0;
        AbstractBcTargetNodes = GraphGetBc (Selected, State->Fabric->Perm[NodeBeingRouted], State->Fabric->Perm[NodeRoutedTo]);

        for (BroadcastSourceNode = 0; BroadcastSourceNode < MAX_NODES; BroadcastSourceNode++) {
          if ((AbstractBcTargetNodes & ((UINT32)1 << BroadcastSourceNode)) != 0) {
            // Accepting broadcast from yourself is handled in Nb, so in the topology graph it is an error.
            ASSERT (NodeBeingRouted != State->Fabric->ReversePerm[BroadcastSourceNode]);
            BcTargetLinks |= (UINT32)1 << FindLinkToNode (NodeBeingRouted, State->Fabric->ReversePerm[BroadcastSourceNode], State);
          }
        }

        if (NodeBeingRouted == NodeRoutedTo) {
          ReqTargetLink = ROUTE_TO_SELF;
          RspTargetLink = ROUTE_TO_SELF;
        } else {
          ReqTargetNode = GraphGetReq (Selected, State->Fabric->Perm[NodeBeingRouted], State->Fabric->Perm[NodeRoutedTo]);
          ReqTargetLink = FindLinkToNode (NodeBeingRouted, State->Fabric->ReversePerm[ReqTargetNode], State);

          RspTargetNode = GraphGetRsp (Selected, State->Fabric->Perm[NodeBeingRouted], State->Fabric->Perm[NodeRoutedTo]);
          RspTargetLink = FindLinkToNode (NodeBeingRouted, State->Fabric->ReversePerm[RspTargetNode], State);
        }
        State->Nb->WriteFullRoutingTable (NodeBeingRouted, NodeRoutedTo, ReqTargetLink, RspTargetLink, BcTargetLinks, State->Nb);
      }
      //  Clean up discovery 'footprint' that otherwise remains in the routing table.  It didn't hurt
      // anything, but might cause confusion during debug and validation.  Do this by setting the
      // route back to all self routes. Since it's the Node that would be one more than actually installed,
      // this only applies if less than MaxNodes were found.
      //
      if (Size < MAX_NODES) {
        State->Nb->WriteFullRoutingTable (NodeBeingRouted, Size, ROUTE_TO_SELF, ROUTE_TO_SELF, 0, State->Nb);
      }
    }
  } else {
    //
    // No Matching Topology was found
    // Error Strategy:
    // Auto recovery doesn't seem likely, Force boot as 1P.
    // For reporting, logging, provide number of Nodes
    // If not implemented or returns, boot as BSP uniprocessor.
    //
    // This can be caused by not supplying an additional topology list, if your board is not one of the built-in topologies.
    //
    NotifyErrorCohNoTopology (State->NodesDiscovered, State);
    IDS_ERROR_TRAP;
    // Force 1P
    State->NodesDiscovered = 0;
    State->TotalLinks = 0;
    State->Nb->EnableRoutingTables (0, State->Nb);
    State->HtInterface->CleanMapsAfterError (State);
  }
  // Save the topology pointer, or NULL, for other features
  State->Fabric->MatchedTopology = Selected;
  IDS_HDT_CONSOLE (
    HT_TRACE,
    "System routed as %s.\n",
    ((TopologyContextHandle.IsCustomList) ?
     "custom topology" :
     (((Selected == amdHtTopologySingleNode) || (Selected == NULL)) ?
      "single node" :
      ((Selected == amdHtTopologyDualNode) ?
       "dual node" :
       ((Selected == amdHtTopologyFourSquare) ?
        "four node box" :
        ((Selected == amdHtTopologyFourKite) ?
         "four node kite" :
         ((Selected == amdHtTopologyFourFully) ?
          "fully connected four-way" :
          ((Selected == amdHtTopologyEightDoubloon) ?
           "MCM max performance" :
           ((Selected == amdHtTopologyEightTwinFullyFourWays) ?
            "MCM max I/O" :
            "AMD builtin topology"))))))))
    );
}

/*----------------------------------------------------------------------------------------*/
/**
 * Make a Hop Count Table for the installed topology.
 *
 * @HtFeatMethod{::F_MAKE_HOP_COUNT_TABLE}
 *
 * For SLIT, create a node x node matrix with the number of hops.  We can do this
 * using the topology and the permutation, counting the nodes visited in the routes between
 * nodes.
 *
 * @param[in,out]   State    access topology, permutation, update hop table
 *
 */
VOID
MakeHopCountTable (
  IN OUT   STATE_DATA    *State
  )
{
  UINT8 Origin;
  UINT8 Target;
  UINT8 Current;
  UINT8 Hops;
  UINT8 Size;

  ASSERT (State->Fabric != NULL);
  if (State->HopCountTable != NULL) {
    if (State->Fabric->MatchedTopology != NULL) {
      Size = GraphHowManyNodes (State->Fabric->MatchedTopology);
      State->HopCountTable->Size = Size;
      //
      // For each node, targeting each node, follow the request path through the database graph,
      // counting the number of edges.
      //
      for (Origin = 0; Origin < Size; Origin++) {
        for (Target = 0; Target < Size; Target++) {
          // If both nodes are the same the answer will be zero
          Hops = 0;
          // Current starts as the database node corresponding to system node Origin.
          Current = State->Fabric->Perm[Origin];
          // Stop if Current is the database node corresponding to system node Target
          while (Current != State->Fabric->Perm[Target]) {
            // This is a hop, so count it. Move Current to the next intermediate database node.
            Hops++;
            Current = GraphGetReq (State->Fabric->MatchedTopology, Current, State->Fabric->Perm[Target]);
          }
          // Put the hop count in the table.
          State->HopCountTable->Hops[ ((Origin * Size) + Target)] = Hops;
        }
      }
    }
  }
}