diff options
Diffstat (limited to 'src/vendorcode/amd/agesa/f14/Proc/HT/Features/htFeatRouting.c')
-rw-r--r-- | src/vendorcode/amd/agesa/f14/Proc/HT/Features/htFeatRouting.c | 493 |
1 files changed, 493 insertions, 0 deletions
diff --git a/src/vendorcode/amd/agesa/f14/Proc/HT/Features/htFeatRouting.c b/src/vendorcode/amd/agesa/f14/Proc/HT/Features/htFeatRouting.c new file mode 100644 index 0000000000..cad07435f0 --- /dev/null +++ b/src/vendorcode/amd/agesa/f14/Proc/HT/Features/htFeatRouting.c @@ -0,0 +1,493 @@ +/* $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: 35978 $ @e \$Date: 2010-08-07 02:18:50 +0800 (Sat, 07 Aug 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; + } + } + } + } +} |