[mirror_edk2.git] / NetworkPkg / Ip6Dxe / Ip6Route.c

/** @file\r
  The functions and routines to handle the route caches and route table.\r
\r
  Copyright (c) 2009 - 2016, Intel Corporation. All rights reserved.<BR>\r
\r
  SPDX-License-Identifier: BSD-2-Clause-Patent\r
\r
**/\r
\r
#include "Ip6Impl.h"\r
\r
/**\r
  This is the worker function for IP6_ROUTE_CACHE_HASH(). It calculates the value\r
  as the index of the route cache bucket according to the prefix of two IPv6 addresses.\r
\r
  @param[in]  Ip1     The IPv6 address.\r
  @param[in]  Ip2     The IPv6 address.\r
\r
  @return The hash value of the prefix of two IPv6 addresses.\r
\r
**/\r
UINT32\r
Ip6RouteCacheHash (\r
  IN EFI_IPv6_ADDRESS  *Ip1,\r
  IN EFI_IPv6_ADDRESS  *Ip2\r
  )\r
{\r
  UINT32  Prefix1;\r
  UINT32  Prefix2;\r
\r
  Prefix1 = *((UINT32 *)((UINTN *)(Ip1)));\r
  Prefix2 = *((UINT32 *)((UINTN *)(Ip2)));\r
\r
  return ((UINT32)(Prefix1 ^ Prefix2) % IP6_ROUTE_CACHE_HASH_SIZE);\r
}\r
\r
/**\r
  Allocate a route entry then initialize it with the Destination/PrefixLength\r
  and Gateway.\r
\r
  @param[in]  Destination     The IPv6 destination address. This is an optional\r
                              parameter that may be NULL.\r
  @param[in]  PrefixLength    The destination network's prefix length.\r
  @param[in]  GatewayAddress  The next hop address. This is an optional parameter\r
                              that may be NULL.\r
\r
  @return NULL if failed to allocate memory; otherwise, the newly created route entry.\r
\r
**/\r
IP6_ROUTE_ENTRY *\r
Ip6CreateRouteEntry (\r
  IN EFI_IPv6_ADDRESS  *Destination    OPTIONAL,\r
  IN UINT8             PrefixLength,\r
  IN EFI_IPv6_ADDRESS  *GatewayAddress OPTIONAL\r
  )\r
{\r
  IP6_ROUTE_ENTRY  *RtEntry;\r
\r
  RtEntry = AllocateZeroPool (sizeof (IP6_ROUTE_ENTRY));\r
\r
  if (RtEntry == NULL) {\r
    return NULL;\r
  }\r
\r
  RtEntry->RefCnt       = 1;\r
  RtEntry->Flag         = 0;\r
  RtEntry->PrefixLength = PrefixLength;\r
\r
  if (Destination != NULL) {\r
    IP6_COPY_ADDRESS (&RtEntry->Destination, Destination);\r
  }\r
\r
  if (GatewayAddress != NULL) {\r
    IP6_COPY_ADDRESS (&RtEntry->NextHop, GatewayAddress);\r
  }\r
\r
  return RtEntry;\r
}\r
\r
/**\r
  Free the route table entry. It is reference counted.\r
\r
  @param[in, out]  RtEntry  The route entry to free.\r
\r
**/\r
VOID\r
Ip6FreeRouteEntry (\r
  IN OUT IP6_ROUTE_ENTRY  *RtEntry\r
  )\r
{\r
  ASSERT ((RtEntry != NULL) && (RtEntry->RefCnt > 0));\r
\r
  if (--RtEntry->RefCnt == 0) {\r
    FreePool (RtEntry);\r
  }\r
}\r
\r
/**\r
  Search the route table for a most specific match to the Dst. It searches\r
  from the longest route area (prefix length == 128) to the shortest route area\r
  (default routes). In each route area, it will first search the instance's\r
  route table, then the default route table. This is required per the following\r
  requirements:\r
  1. IP search the route table for a most specific match.\r
  2. The local route entries have precedence over the default route entry.\r
\r
  @param[in]  RtTable       The route table to search from.\r
  @param[in]  Destination   The destination address to search. If NULL, search\r
                            the route table by NextHop.\r
  @param[in]  NextHop       The next hop address. If NULL, search the route table\r
                            by Destination.\r
\r
  @return NULL if no route matches the Dst. Otherwise, the point to the\r
  @return most specific route to the Dst.\r
\r
**/\r
IP6_ROUTE_ENTRY *\r
Ip6FindRouteEntry (\r
  IN IP6_ROUTE_TABLE   *RtTable,\r
  IN EFI_IPv6_ADDRESS  *Destination OPTIONAL,\r
  IN EFI_IPv6_ADDRESS  *NextHop     OPTIONAL\r
  )\r
{\r
  LIST_ENTRY       *Entry;\r
  IP6_ROUTE_ENTRY  *RtEntry;\r
  INTN             Index;\r
\r
  ASSERT (Destination != NULL || NextHop != NULL);\r
\r
  RtEntry = NULL;\r
\r
  for (Index = IP6_PREFIX_MAX; Index >= 0; Index--) {\r
    NET_LIST_FOR_EACH (Entry, &RtTable->RouteArea[Index]) {\r
      RtEntry = NET_LIST_USER_STRUCT (Entry, IP6_ROUTE_ENTRY, Link);\r
\r
      if (Destination != NULL) {\r
        if (NetIp6IsNetEqual (Destination, &RtEntry->Destination, RtEntry->PrefixLength)) {\r
          NET_GET_REF (RtEntry);\r
          return RtEntry;\r
        }\r
      } else if (NextHop != NULL) {\r
        if (NetIp6IsNetEqual (NextHop, &RtEntry->NextHop, RtEntry->PrefixLength)) {\r
          NET_GET_REF (RtEntry);\r
          return RtEntry;\r
        }\r
      }\r
    }\r
  }\r
\r
  return NULL;\r
}\r
\r
/**\r
  Allocate and initialize a IP6 route cache entry.\r
\r
  @param[in]  Dst           The destination address.\r
  @param[in]  Src           The source address.\r
  @param[in]  GateWay       The next hop address.\r
  @param[in]  Tag           The tag from the caller. This marks all the cache entries\r
                            spawned from one route table entry.\r
\r
  @return NULL if failed to allocate memory for the cache. Otherwise, point\r
          to the created route cache entry.\r
\r
**/\r
IP6_ROUTE_CACHE_ENTRY *\r
Ip6CreateRouteCacheEntry (\r
  IN EFI_IPv6_ADDRESS  *Dst,\r
  IN EFI_IPv6_ADDRESS  *Src,\r
  IN EFI_IPv6_ADDRESS  *GateWay,\r
  IN UINTN             Tag\r
  )\r
{\r
  IP6_ROUTE_CACHE_ENTRY  *RtCacheEntry;\r
\r
  RtCacheEntry = AllocatePool (sizeof (IP6_ROUTE_CACHE_ENTRY));\r
\r
  if (RtCacheEntry == NULL) {\r
    return NULL;\r
  }\r
\r
  RtCacheEntry->RefCnt = 1;\r
  RtCacheEntry->Tag    = Tag;\r
\r
  IP6_COPY_ADDRESS (&RtCacheEntry->Destination, Dst);\r
  IP6_COPY_ADDRESS (&RtCacheEntry->Source, Src);\r
  IP6_COPY_ADDRESS (&RtCacheEntry->NextHop, GateWay);\r
\r
  return RtCacheEntry;\r
}\r
\r
/**\r
  Free the route cache entry. It is reference counted.\r
\r
  @param[in, out]  RtCacheEntry  The route cache entry to free.\r
\r
**/\r
VOID\r
Ip6FreeRouteCacheEntry (\r
  IN OUT IP6_ROUTE_CACHE_ENTRY  *RtCacheEntry\r
  )\r
{\r
  ASSERT (RtCacheEntry->RefCnt > 0);\r
\r
  if (--RtCacheEntry->RefCnt == 0) {\r
    FreePool (RtCacheEntry);\r
  }\r
}\r
\r
/**\r
  Find a route cache with the destination and source address. This is\r
  used by the ICMPv6 redirect message process.\r
\r
  @param[in]  RtTable       The route table to search the cache for.\r
  @param[in]  Dest          The destination address.\r
  @param[in]  Src           The source address.\r
\r
  @return NULL if no route entry to the (Dest, Src). Otherwise, the pointer\r
          to the correct route cache entry.\r
\r
**/\r
IP6_ROUTE_CACHE_ENTRY *\r
Ip6FindRouteCache (\r
  IN IP6_ROUTE_TABLE   *RtTable,\r
  IN EFI_IPv6_ADDRESS  *Dest,\r
  IN EFI_IPv6_ADDRESS  *Src\r
  )\r
{\r
  LIST_ENTRY             *Entry;\r
  IP6_ROUTE_CACHE_ENTRY  *RtCacheEntry;\r
  UINT32                 Index;\r
\r
  Index = IP6_ROUTE_CACHE_HASH (Dest, Src);\r
\r
  NET_LIST_FOR_EACH (Entry, &RtTable->Cache.CacheBucket[Index]) {\r
    RtCacheEntry = NET_LIST_USER_STRUCT (Entry, IP6_ROUTE_CACHE_ENTRY, Link);\r
\r
    if (EFI_IP6_EQUAL (Dest, &RtCacheEntry->Destination) && EFI_IP6_EQUAL (Src, &RtCacheEntry->Source)) {\r
      NET_GET_REF (RtCacheEntry);\r
      return RtCacheEntry;\r
    }\r
  }\r
\r
  return NULL;\r
}\r
\r
/**\r
  Build an array of EFI_IP6_ROUTE_TABLE to be returned to the caller. The number\r
  of EFI_IP6_ROUTE_TABLE is also returned.\r
\r
  @param[in]  RouteTable        The pointer of IP6_ROUTE_TABLE internal used.\r
  @param[out] EfiRouteCount     The number of returned route entries.\r
  @param[out] EfiRouteTable     The pointer to the array of EFI_IP6_ROUTE_TABLE.\r
                                If NULL, only the route entry count is returned.\r
\r
  @retval EFI_SUCCESS           The EFI_IP6_ROUTE_TABLE successfully built.\r
  @retval EFI_OUT_OF_RESOURCES  Failed to allocate the memory for the route table.\r
\r
**/\r
EFI_STATUS\r
Ip6BuildEfiRouteTable (\r
  IN IP6_ROUTE_TABLE       *RouteTable,\r
  OUT UINT32               *EfiRouteCount,\r
  OUT EFI_IP6_ROUTE_TABLE  **EfiRouteTable OPTIONAL\r
  )\r
{\r
  LIST_ENTRY           *Entry;\r
  IP6_ROUTE_ENTRY      *RtEntry;\r
  EFI_IP6_ROUTE_TABLE  *EfiTable;\r
  UINT32               Count;\r
  INT32                Index;\r
\r
  ASSERT (EfiRouteCount != NULL);\r
\r
  Count          = RouteTable->TotalNum;\r
  *EfiRouteCount = Count;\r
\r
  if ((EfiRouteTable == NULL) || (Count == 0)) {\r
    return EFI_SUCCESS;\r
  }\r
\r
  if (*EfiRouteTable == NULL) {\r
    *EfiRouteTable = AllocatePool (sizeof (EFI_IP6_ROUTE_TABLE) * Count);\r
    if (*EfiRouteTable == NULL) {\r
      return EFI_OUT_OF_RESOURCES;\r
    }\r
  }\r
\r
  EfiTable = *EfiRouteTable;\r
\r
  //\r
  // Copy the route entry to EFI route table.\r
  //\r
  Count = 0;\r
\r
  for (Index = IP6_PREFIX_MAX; Index >= 0; Index--) {\r
    NET_LIST_FOR_EACH (Entry, &(RouteTable->RouteArea[Index])) {\r
      RtEntry = NET_LIST_USER_STRUCT (Entry, IP6_ROUTE_ENTRY, Link);\r
\r
      Ip6CopyAddressByPrefix (\r
        &EfiTable[Count].Destination,\r
        &RtEntry->Destination,\r
        RtEntry->PrefixLength\r
        );\r
\r
      IP6_COPY_ADDRESS (&EfiTable[Count].Gateway, &RtEntry->NextHop);\r
      EfiTable[Count].PrefixLength = RtEntry->PrefixLength;\r
\r
      Count++;\r
    }\r
  }\r
\r
  ASSERT (Count == RouteTable->TotalNum);\r
\r
  return EFI_SUCCESS;\r
}\r
\r
/**\r
  Create an empty route table. This includes its internal route cache.\r
\r
  @return NULL if failed to allocate memory for the route table. Otherwise,\r
          the point to newly created route table.\r
\r
**/\r
IP6_ROUTE_TABLE *\r
Ip6CreateRouteTable (\r
  VOID\r
  )\r
{\r
  IP6_ROUTE_TABLE  *RtTable;\r
  UINT32           Index;\r
\r
  RtTable = AllocatePool (sizeof (IP6_ROUTE_TABLE));\r
  if (RtTable == NULL) {\r
    return NULL;\r
  }\r
\r
  RtTable->RefCnt   = 1;\r
  RtTable->TotalNum = 0;\r
\r
  for (Index = 0; Index <= IP6_PREFIX_MAX; Index++) {\r
    InitializeListHead (&RtTable->RouteArea[Index]);\r
  }\r
\r
  for (Index = 0; Index < IP6_ROUTE_CACHE_HASH_SIZE; Index++) {\r
    InitializeListHead (&RtTable->Cache.CacheBucket[Index]);\r
    RtTable->Cache.CacheNum[Index] = 0;\r
  }\r
\r
  return RtTable;\r
}\r
\r
/**\r
  Free the route table and its associated route cache. Route\r
  table is reference counted.\r
\r
  @param[in, out]  RtTable      The route table to free.\r
\r
**/\r
VOID\r
Ip6CleanRouteTable (\r
  IN OUT IP6_ROUTE_TABLE  *RtTable\r
  )\r
{\r
  LIST_ENTRY             *Entry;\r
  LIST_ENTRY             *Next;\r
  IP6_ROUTE_ENTRY        *RtEntry;\r
  IP6_ROUTE_CACHE_ENTRY  *RtCacheEntry;\r
  UINT32                 Index;\r
\r
  ASSERT (RtTable->RefCnt > 0);\r
\r
  if (--RtTable->RefCnt > 0) {\r
    return;\r
  }\r
\r
  //\r
  // Free all the route table entry and its route cache.\r
  //\r
  for (Index = 0; Index <= IP6_PREFIX_MAX; Index++) {\r
    NET_LIST_FOR_EACH_SAFE (Entry, Next, &RtTable->RouteArea[Index]) {\r
      RtEntry = NET_LIST_USER_STRUCT (Entry, IP6_ROUTE_ENTRY, Link);\r
      RemoveEntryList (Entry);\r
      Ip6FreeRouteEntry (RtEntry);\r
    }\r
  }\r
\r
  for (Index = 0; Index < IP6_ROUTE_CACHE_HASH_SIZE; Index++) {\r
    NET_LIST_FOR_EACH_SAFE (Entry, Next, &RtTable->Cache.CacheBucket[Index]) {\r
      RtCacheEntry = NET_LIST_USER_STRUCT (Entry, IP6_ROUTE_CACHE_ENTRY, Link);\r
      RemoveEntryList (Entry);\r
      Ip6FreeRouteCacheEntry (RtCacheEntry);\r
    }\r
  }\r
\r
  FreePool (RtTable);\r
}\r
\r
/**\r
  Remove all the cache entries bearing the Tag. When a route cache\r
  entry is created, it is tagged with the address of route entry\r
  from which it is spawned. When a route entry is deleted, the cache\r
  entries spawned from it are also deleted.\r
\r
  @param[in]  RtCache       Route cache to remove the entries from.\r
  @param[in]  Tag           The Tag of the entries to remove.\r
\r
**/\r
VOID\r
Ip6PurgeRouteCache (\r
  IN IP6_ROUTE_CACHE  *RtCache,\r
  IN UINTN            Tag\r
  )\r
{\r
  LIST_ENTRY             *Entry;\r
  LIST_ENTRY             *Next;\r
  IP6_ROUTE_CACHE_ENTRY  *RtCacheEntry;\r
  UINT32                 Index;\r
\r
  for (Index = 0; Index < IP6_ROUTE_CACHE_HASH_SIZE; Index++) {\r
    NET_LIST_FOR_EACH_SAFE (Entry, Next, &RtCache->CacheBucket[Index]) {\r
      RtCacheEntry = NET_LIST_USER_STRUCT (Entry, IP6_ROUTE_CACHE_ENTRY, Link);\r
\r
      if (RtCacheEntry->Tag == Tag) {\r
        RemoveEntryList (Entry);\r
        Ip6FreeRouteCacheEntry (RtCacheEntry);\r
      }\r
    }\r
  }\r
}\r
\r
/**\r
  Add a route entry to the route table. It is the help function for EfiIp6Routes.\r
\r
  @param[in, out]  RtTable        Route table to add route to.\r
  @param[in]       Destination    The destination of the network.\r
  @param[in]       PrefixLength   The PrefixLength of the destination.\r
  @param[in]       GatewayAddress The next hop address.\r
\r
  @retval EFI_ACCESS_DENIED     The same route already exists.\r
  @retval EFI_OUT_OF_RESOURCES  Failed to allocate memory for the entry.\r
  @retval EFI_SUCCESS           The route was added successfully.\r
\r
**/\r
EFI_STATUS\r
Ip6AddRoute (\r
  IN OUT IP6_ROUTE_TABLE  *RtTable,\r
  IN EFI_IPv6_ADDRESS     *Destination,\r
  IN UINT8                PrefixLength,\r
  IN EFI_IPv6_ADDRESS     *GatewayAddress\r
  )\r
{\r
  LIST_ENTRY       *ListHead;\r
  LIST_ENTRY       *Entry;\r
  IP6_ROUTE_ENTRY  *Route;\r
\r
  ListHead = &RtTable->RouteArea[PrefixLength];\r
\r
  //\r
  // First check whether the route exists\r
  //\r
  NET_LIST_FOR_EACH (Entry, ListHead) {\r
    Route = NET_LIST_USER_STRUCT (Entry, IP6_ROUTE_ENTRY, Link);\r
\r
    if (NetIp6IsNetEqual (Destination, &Route->Destination, PrefixLength) &&\r
        EFI_IP6_EQUAL (GatewayAddress, &Route->NextHop))\r
    {\r
      return EFI_ACCESS_DENIED;\r
    }\r
  }\r
\r
  //\r
  // Create a route entry and insert it to the route area.\r
  //\r
  Route = Ip6CreateRouteEntry (Destination, PrefixLength, GatewayAddress);\r
\r
  if (Route == NULL) {\r
    return EFI_OUT_OF_RESOURCES;\r
  }\r
\r
  if (NetIp6IsUnspecifiedAddr (GatewayAddress)) {\r
    Route->Flag = IP6_DIRECT_ROUTE;\r
  }\r
\r
  InsertHeadList (ListHead, &Route->Link);\r
  RtTable->TotalNum++;\r
\r
  return EFI_SUCCESS;\r
}\r
\r
/**\r
  Remove a route entry and all the route caches spawn from it.\r
  It is the help function for EfiIp6Routes.\r
\r
  @param[in, out] RtTable           The route table to remove the route from.\r
  @param[in]      Destination       The destination network.\r
  @param[in]      PrefixLength      The PrefixLength of the Destination.\r
  @param[in]      GatewayAddress    The next hop address.\r
\r
  @retval EFI_SUCCESS           The route entry was successfully removed.\r
  @retval EFI_NOT_FOUND         There is no route entry in the table with that\r
                                property.\r
\r
**/\r
EFI_STATUS\r
Ip6DelRoute (\r
  IN OUT IP6_ROUTE_TABLE  *RtTable,\r
  IN EFI_IPv6_ADDRESS     *Destination,\r
  IN UINT8                PrefixLength,\r
  IN EFI_IPv6_ADDRESS     *GatewayAddress\r
  )\r
{\r
  LIST_ENTRY       *ListHead;\r
  LIST_ENTRY       *Entry;\r
  LIST_ENTRY       *Next;\r
  IP6_ROUTE_ENTRY  *Route;\r
  UINT32           TotalNum;\r
\r
  ListHead = &RtTable->RouteArea[PrefixLength];\r
  TotalNum = RtTable->TotalNum;\r
\r
  NET_LIST_FOR_EACH_SAFE (Entry, Next, ListHead) {\r
    Route = NET_LIST_USER_STRUCT (Entry, IP6_ROUTE_ENTRY, Link);\r
\r
    if ((Destination != NULL) && !NetIp6IsNetEqual (Destination, &Route->Destination, PrefixLength)) {\r
      continue;\r
    }\r
\r
    if ((GatewayAddress != NULL) && !EFI_IP6_EQUAL (GatewayAddress, &Route->NextHop)) {\r
      continue;\r
    }\r
\r
    Ip6PurgeRouteCache (&RtTable->Cache, (UINTN)Route);\r
    RemoveEntryList (Entry);\r
    Ip6FreeRouteEntry (Route);\r
\r
    ASSERT (RtTable->TotalNum > 0);\r
    RtTable->TotalNum--;\r
  }\r
\r
  return TotalNum == RtTable->TotalNum ? EFI_NOT_FOUND : EFI_SUCCESS;\r
}\r
\r
/**\r
  Search the route table to route the packet. Return/create a route\r
  cache if there is a route to the destination.\r
\r
  @param[in]  IpSb          The IP6 service data.\r
  @param[in]  Dest          The destination address to search for.\r
  @param[in]  Src           The source address to search for.\r
\r
  @return NULL if it failed to route the packet. Otherwise, a route cache\r
          entry that can be used to route packets.\r
\r
**/\r
IP6_ROUTE_CACHE_ENTRY *\r
Ip6Route (\r
  IN IP6_SERVICE       *IpSb,\r
  IN EFI_IPv6_ADDRESS  *Dest,\r
  IN EFI_IPv6_ADDRESS  *Src\r
  )\r
{\r
  IP6_ROUTE_TABLE        *RtTable;\r
  LIST_ENTRY             *ListHead;\r
  IP6_ROUTE_CACHE_ENTRY  *RtCacheEntry;\r
  IP6_ROUTE_ENTRY        *RtEntry;\r
  EFI_IPv6_ADDRESS       NextHop;\r
  UINT32                 Index;\r
\r
  RtTable = IpSb->RouteTable;\r
\r
  ASSERT (RtTable != NULL);\r
\r
  //\r
  // Search the destination cache in IP6_ROUTE_TABLE.\r
  //\r
  Index    = IP6_ROUTE_CACHE_HASH (Dest, Src);\r
  ListHead = &RtTable->Cache.CacheBucket[Index];\r
\r
  RtCacheEntry = Ip6FindRouteCache (RtTable, Dest, Src);\r
\r
  //\r
  // If found, promote the cache entry to the head of the hash bucket.\r
  //\r
  if (RtCacheEntry != NULL) {\r
    RemoveEntryList (&RtCacheEntry->Link);\r
    InsertHeadList (ListHead, &RtCacheEntry->Link);\r
    return RtCacheEntry;\r
  }\r
\r
  //\r
  // Search the route table for the most specific route\r
  //\r
  RtEntry = Ip6FindRouteEntry (RtTable, Dest, NULL);\r
  if (RtEntry == NULL) {\r
    return NULL;\r
  }\r
\r
  //\r
  // Found a route to the Dest, if it is a direct route, the packet\r
  // will be send directly to the destination, such as for connected\r
  // network. Otherwise, it is an indirect route, the packet will be\r
  // send the next hop router.\r
  //\r
  if ((RtEntry->Flag & IP6_DIRECT_ROUTE) == IP6_DIRECT_ROUTE) {\r
    IP6_COPY_ADDRESS (&NextHop, Dest);\r
  } else {\r
    IP6_COPY_ADDRESS (&NextHop, &RtEntry->NextHop);\r
  }\r
\r
  Ip6FreeRouteEntry (RtEntry);\r
\r
  //\r
  // Create a route cache entry, and tag it as spawned from this route entry\r
  //\r
  RtCacheEntry = Ip6CreateRouteCacheEntry (Dest, Src, &NextHop, (UINTN)RtEntry);\r
\r
  if (RtCacheEntry == NULL) {\r
    return NULL;\r
  }\r
\r
  InsertHeadList (ListHead, &RtCacheEntry->Link);\r
  NET_GET_REF (RtCacheEntry);\r
  RtTable->Cache.CacheNum[Index]++;\r
\r
  return RtCacheEntry;\r
}\r
Commit	Line	Data
a3bcde70 HT	1	/** @file\r
	2	The functions and routines to handle the route caches and route table.\r
	3	\r
c720da28	4	Copyright (c) 2009 - 2016, Intel Corporation. All rights reserved.<BR>\r
a3bcde70	5	\r
ecf98fbc	6	SPDX-License-Identifier: BSD-2-Clause-Patent\r
a3bcde70 HT	7	\r
	8	**/\r
	9	\r
	10	#include "Ip6Impl.h"\r
	11	\r
	12	/**\r
	13	This is the worker function for IP6_ROUTE_CACHE_HASH(). It calculates the value\r
	14	as the index of the route cache bucket according to the prefix of two IPv6 addresses.\r
	15	\r
	16	@param[in] Ip1 The IPv6 address.\r
	17	@param[in] Ip2 The IPv6 address.\r
	18	\r
	19	@return The hash value of the prefix of two IPv6 addresses.\r
	20	\r
	21	**/\r
	22	UINT32\r
	23	Ip6RouteCacheHash (\r
d1050b9d MK	24	IN EFI_IPv6_ADDRESS *Ip1,\r
d1050b9d MK	25	IN EFI_IPv6_ADDRESS *Ip2\r
a3bcde70 HT	26	)\r
a3bcde70 HT	27	{\r
d1050b9d MK	28	UINT32 Prefix1;\r
d1050b9d MK	29	UINT32 Prefix2;\r
a3bcde70	30	\r
d1050b9d MK	31	Prefix1 = ((UINT32 )((UINTN *)(Ip1)));\r
d1050b9d MK	32	Prefix2 = ((UINT32 )((UINTN *)(Ip2)));\r
a3bcde70	33	\r
d1050b9d	34	return ((UINT32)(Prefix1 ^ Prefix2) % IP6_ROUTE_CACHE_HASH_SIZE);\r
a3bcde70 HT	35	}\r
	36	\r
	37	/**\r
	38	Allocate a route entry then initialize it with the Destination/PrefixLength\r
	39	and Gateway.\r
	40	\r
	41	@param[in] Destination The IPv6 destination address. This is an optional\r
	42	parameter that may be NULL.\r
	43	@param[in] PrefixLength The destination network's prefix length.\r
	44	@param[in] GatewayAddress The next hop address. This is an optional parameter\r
	45	that may be NULL.\r
	46	\r
7de8045a	47	@return NULL if failed to allocate memory; otherwise, the newly created route entry.\r
a3bcde70 HT	48	\r
	49	**/\r
	50	IP6_ROUTE_ENTRY *\r
	51	Ip6CreateRouteEntry (\r
d1050b9d MK	52	IN EFI_IPv6_ADDRESS *Destination OPTIONAL,\r
	53	IN UINT8 PrefixLength,\r
	54	IN EFI_IPv6_ADDRESS *GatewayAddress OPTIONAL\r
a3bcde70 HT	55	)\r
a3bcde70 HT	56	{\r
d1050b9d	57	IP6_ROUTE_ENTRY *RtEntry;\r
a3bcde70 HT	58	\r
	59	RtEntry = AllocateZeroPool (sizeof (IP6_ROUTE_ENTRY));\r
	60	\r
	61	if (RtEntry == NULL) {\r
	62	return NULL;\r
	63	}\r
	64	\r
	65	RtEntry->RefCnt = 1;\r
	66	RtEntry->Flag = 0;\r
	67	RtEntry->PrefixLength = PrefixLength;\r
	68	\r
	69	if (Destination != NULL) {\r
	70	IP6_COPY_ADDRESS (&RtEntry->Destination, Destination);\r
	71	}\r
	72	\r
	73	if (GatewayAddress != NULL) {\r
	74	IP6_COPY_ADDRESS (&RtEntry->NextHop, GatewayAddress);\r
	75	}\r
	76	\r
	77	return RtEntry;\r
	78	}\r
	79	\r
	80	/**\r
	81	Free the route table entry. It is reference counted.\r
	82	\r
	83	@param[in, out] RtEntry The route entry to free.\r
	84	\r
	85	**/\r
	86	VOID\r
	87	Ip6FreeRouteEntry (\r
d1050b9d	88	IN OUT IP6_ROUTE_ENTRY *RtEntry\r
a3bcde70 HT	89	)\r
	90	{\r
	91	ASSERT ((RtEntry != NULL) && (RtEntry->RefCnt > 0));\r
	92	\r
	93	if (--RtEntry->RefCnt == 0) {\r
	94	FreePool (RtEntry);\r
	95	}\r
	96	}\r
	97	\r
	98	/**\r
	99	Search the route table for a most specific match to the Dst. It searches\r
	100	from the longest route area (prefix length == 128) to the shortest route area\r
	101	(default routes). In each route area, it will first search the instance's\r
	102	route table, then the default route table. This is required per the following\r
	103	requirements:\r
	104	1. IP search the route table for a most specific match.\r
	105	2. The local route entries have precedence over the default route entry.\r
	106	\r
	107	@param[in] RtTable The route table to search from.\r
7de8045a	108	@param[in] Destination The destination address to search. If NULL, search\r
a3bcde70 HT	109	the route table by NextHop.\r
	110	@param[in] NextHop The next hop address. If NULL, search the route table\r
	111	by Destination.\r
	112	\r
	113	@return NULL if no route matches the Dst. Otherwise, the point to the\r
	114	@return most specific route to the Dst.\r
	115	\r
	116	**/\r
	117	IP6_ROUTE_ENTRY *\r
	118	Ip6FindRouteEntry (\r
d1050b9d MK	119	IN IP6_ROUTE_TABLE *RtTable,\r
	120	IN EFI_IPv6_ADDRESS *Destination OPTIONAL,\r
	121	IN EFI_IPv6_ADDRESS *NextHop OPTIONAL\r
a3bcde70 HT	122	)\r
a3bcde70 HT	123	{\r
d1050b9d MK	124	LIST_ENTRY *Entry;\r
	125	IP6_ROUTE_ENTRY *RtEntry;\r
	126	INTN Index;\r
a3bcde70 HT	127	\r
	128	ASSERT (Destination != NULL \|\| NextHop != NULL);\r
	129	\r
	130	RtEntry = NULL;\r
	131	\r
c720da28	132	for (Index = IP6_PREFIX_MAX; Index >= 0; Index--) {\r
a3bcde70 HT	133	NET_LIST_FOR_EACH (Entry, &RtTable->RouteArea[Index]) {\r
	134	RtEntry = NET_LIST_USER_STRUCT (Entry, IP6_ROUTE_ENTRY, Link);\r
	135	\r
	136	if (Destination != NULL) {\r
	137	if (NetIp6IsNetEqual (Destination, &RtEntry->Destination, RtEntry->PrefixLength)) {\r
	138	NET_GET_REF (RtEntry);\r
	139	return RtEntry;\r
	140	}\r
	141	} else if (NextHop != NULL) {\r
	142	if (NetIp6IsNetEqual (NextHop, &RtEntry->NextHop, RtEntry->PrefixLength)) {\r
	143	NET_GET_REF (RtEntry);\r
	144	return RtEntry;\r
	145	}\r
	146	}\r
a3bcde70 HT	147	}\r
	148	}\r
	149	\r
	150	return NULL;\r
	151	}\r
	152	\r
	153	/**\r
	154	Allocate and initialize a IP6 route cache entry.\r
	155	\r
	156	@param[in] Dst The destination address.\r
	157	@param[in] Src The source address.\r
	158	@param[in] GateWay The next hop address.\r
	159	@param[in] Tag The tag from the caller. This marks all the cache entries\r
	160	spawned from one route table entry.\r
	161	\r
	162	@return NULL if failed to allocate memory for the cache. Otherwise, point\r
	163	to the created route cache entry.\r
	164	\r
	165	**/\r
	166	IP6_ROUTE_CACHE_ENTRY *\r
	167	Ip6CreateRouteCacheEntry (\r
d1050b9d MK	168	IN EFI_IPv6_ADDRESS *Dst,\r
	169	IN EFI_IPv6_ADDRESS *Src,\r
	170	IN EFI_IPv6_ADDRESS *GateWay,\r
	171	IN UINTN Tag\r
a3bcde70 HT	172	)\r
a3bcde70 HT	173	{\r
d1050b9d	174	IP6_ROUTE_CACHE_ENTRY *RtCacheEntry;\r
a3bcde70 HT	175	\r
	176	RtCacheEntry = AllocatePool (sizeof (IP6_ROUTE_CACHE_ENTRY));\r
	177	\r
	178	if (RtCacheEntry == NULL) {\r
	179	return NULL;\r
	180	}\r
	181	\r
	182	RtCacheEntry->RefCnt = 1;\r
	183	RtCacheEntry->Tag = Tag;\r
	184	\r
	185	IP6_COPY_ADDRESS (&RtCacheEntry->Destination, Dst);\r
	186	IP6_COPY_ADDRESS (&RtCacheEntry->Source, Src);\r
	187	IP6_COPY_ADDRESS (&RtCacheEntry->NextHop, GateWay);\r
	188	\r
	189	return RtCacheEntry;\r
	190	}\r
	191	\r
	192	/**\r
	193	Free the route cache entry. It is reference counted.\r
	194	\r
	195	@param[in, out] RtCacheEntry The route cache entry to free.\r
	196	\r
	197	**/\r
	198	VOID\r
	199	Ip6FreeRouteCacheEntry (\r
	200	IN OUT IP6_ROUTE_CACHE_ENTRY *RtCacheEntry\r
	201	)\r
	202	{\r
	203	ASSERT (RtCacheEntry->RefCnt > 0);\r
	204	\r
	205	if (--RtCacheEntry->RefCnt == 0) {\r
	206	FreePool (RtCacheEntry);\r
	207	}\r
	208	}\r
	209	\r
	210	/**\r
	211	Find a route cache with the destination and source address. This is\r
7de8045a	212	used by the ICMPv6 redirect message process.\r
a3bcde70 HT	213	\r
	214	@param[in] RtTable The route table to search the cache for.\r
	215	@param[in] Dest The destination address.\r
	216	@param[in] Src The source address.\r
	217	\r
	218	@return NULL if no route entry to the (Dest, Src). Otherwise, the pointer\r
	219	to the correct route cache entry.\r
	220	\r
	221	**/\r
	222	IP6_ROUTE_CACHE_ENTRY *\r
	223	Ip6FindRouteCache (\r
d1050b9d MK	224	IN IP6_ROUTE_TABLE *RtTable,\r
	225	IN EFI_IPv6_ADDRESS *Dest,\r
	226	IN EFI_IPv6_ADDRESS *Src\r
a3bcde70 HT	227	)\r
a3bcde70 HT	228	{\r
d1050b9d MK	229	LIST_ENTRY *Entry;\r
	230	IP6_ROUTE_CACHE_ENTRY *RtCacheEntry;\r
	231	UINT32 Index;\r
a3bcde70 HT	232	\r
	233	Index = IP6_ROUTE_CACHE_HASH (Dest, Src);\r
	234	\r
	235	NET_LIST_FOR_EACH (Entry, &RtTable->Cache.CacheBucket[Index]) {\r
	236	RtCacheEntry = NET_LIST_USER_STRUCT (Entry, IP6_ROUTE_CACHE_ENTRY, Link);\r
	237	\r
d1050b9d	238	if (EFI_IP6_EQUAL (Dest, &RtCacheEntry->Destination) && EFI_IP6_EQUAL (Src, &RtCacheEntry->Source)) {\r
a3bcde70 HT	239	NET_GET_REF (RtCacheEntry);\r
	240	return RtCacheEntry;\r
	241	}\r
	242	}\r
	243	\r
	244	return NULL;\r
	245	}\r
	246	\r
	247	/**\r
	248	Build an array of EFI_IP6_ROUTE_TABLE to be returned to the caller. The number\r
	249	of EFI_IP6_ROUTE_TABLE is also returned.\r
	250	\r
	251	@param[in] RouteTable The pointer of IP6_ROUTE_TABLE internal used.\r
	252	@param[out] EfiRouteCount The number of returned route entries.\r
	253	@param[out] EfiRouteTable The pointer to the array of EFI_IP6_ROUTE_TABLE.\r
	254	If NULL, only the route entry count is returned.\r
	255	\r
	256	@retval EFI_SUCCESS The EFI_IP6_ROUTE_TABLE successfully built.\r
	257	@retval EFI_OUT_OF_RESOURCES Failed to allocate the memory for the route table.\r
	258	\r
	259	**/\r
	260	EFI_STATUS\r
	261	Ip6BuildEfiRouteTable (\r
d1050b9d MK	262	IN IP6_ROUTE_TABLE *RouteTable,\r
	263	OUT UINT32 *EfiRouteCount,\r
	264	OUT EFI_IP6_ROUTE_TABLE **EfiRouteTable OPTIONAL\r
a3bcde70 HT	265	)\r
a3bcde70 HT	266	{\r
d1050b9d MK	267	LIST_ENTRY *Entry;\r
	268	IP6_ROUTE_ENTRY *RtEntry;\r
	269	EFI_IP6_ROUTE_TABLE *EfiTable;\r
	270	UINT32 Count;\r
	271	INT32 Index;\r
a3bcde70 HT	272	\r
	273	ASSERT (EfiRouteCount != NULL);\r
	274	\r
	275	Count = RouteTable->TotalNum;\r
	276	*EfiRouteCount = Count;\r
	277	\r
	278	if ((EfiRouteTable == NULL) \|\| (Count == 0)) {\r
	279	return EFI_SUCCESS;\r
	280	}\r
	281	\r
	282	if (*EfiRouteTable == NULL) {\r
	283	EfiRouteTable = AllocatePool (sizeof (EFI_IP6_ROUTE_TABLE) Count);\r
	284	if (*EfiRouteTable == NULL) {\r
	285	return EFI_OUT_OF_RESOURCES;\r
	286	}\r
	287	}\r
	288	\r
	289	EfiTable = *EfiRouteTable;\r
	290	\r
	291	//\r
	292	// Copy the route entry to EFI route table.\r
	293	//\r
	294	Count = 0;\r
	295	\r
c720da28	296	for (Index = IP6_PREFIX_MAX; Index >= 0; Index--) {\r
a3bcde70 HT	297	NET_LIST_FOR_EACH (Entry, &(RouteTable->RouteArea[Index])) {\r
	298	RtEntry = NET_LIST_USER_STRUCT (Entry, IP6_ROUTE_ENTRY, Link);\r
	299	\r
	300	Ip6CopyAddressByPrefix (\r
	301	&EfiTable[Count].Destination,\r
	302	&RtEntry->Destination,\r
	303	RtEntry->PrefixLength\r
	304	);\r
	305	\r
	306	IP6_COPY_ADDRESS (&EfiTable[Count].Gateway, &RtEntry->NextHop);\r
	307	EfiTable[Count].PrefixLength = RtEntry->PrefixLength;\r
	308	\r
	309	Count++;\r
	310	}\r
	311	}\r
	312	\r
	313	ASSERT (Count == RouteTable->TotalNum);\r
	314	\r
	315	return EFI_SUCCESS;\r
	316	}\r
	317	\r
	318	/**\r
	319	Create an empty route table. This includes its internal route cache.\r
	320	\r
	321	@return NULL if failed to allocate memory for the route table. Otherwise,\r
	322	the point to newly created route table.\r
	323	\r
	324	**/\r
	325	IP6_ROUTE_TABLE *\r
	326	Ip6CreateRouteTable (\r
	327	VOID\r
	328	)\r
	329	{\r
d1050b9d MK	330	IP6_ROUTE_TABLE *RtTable;\r
d1050b9d MK	331	UINT32 Index;\r
a3bcde70 HT	332	\r
	333	RtTable = AllocatePool (sizeof (IP6_ROUTE_TABLE));\r
	334	if (RtTable == NULL) {\r
	335	return NULL;\r
	336	}\r
	337	\r
	338	RtTable->RefCnt = 1;\r
	339	RtTable->TotalNum = 0;\r
	340	\r
c720da28	341	for (Index = 0; Index <= IP6_PREFIX_MAX; Index++) {\r
a3bcde70 HT	342	InitializeListHead (&RtTable->RouteArea[Index]);\r
	343	}\r
	344	\r
	345	for (Index = 0; Index < IP6_ROUTE_CACHE_HASH_SIZE; Index++) {\r
	346	InitializeListHead (&RtTable->Cache.CacheBucket[Index]);\r
	347	RtTable->Cache.CacheNum[Index] = 0;\r
	348	}\r
	349	\r
	350	return RtTable;\r
	351	}\r
	352	\r
	353	/**\r
	354	Free the route table and its associated route cache. Route\r
	355	table is reference counted.\r
	356	\r
	357	@param[in, out] RtTable The route table to free.\r
	358	\r
	359	**/\r
	360	VOID\r
	361	Ip6CleanRouteTable (\r
d1050b9d	362	IN OUT IP6_ROUTE_TABLE *RtTable\r
a3bcde70 HT	363	)\r
a3bcde70 HT	364	{\r
d1050b9d MK	365	LIST_ENTRY *Entry;\r
	366	LIST_ENTRY *Next;\r
	367	IP6_ROUTE_ENTRY *RtEntry;\r
	368	IP6_ROUTE_CACHE_ENTRY *RtCacheEntry;\r
	369	UINT32 Index;\r
a3bcde70 HT	370	\r
	371	ASSERT (RtTable->RefCnt > 0);\r
	372	\r
	373	if (--RtTable->RefCnt > 0) {\r
d1050b9d	374	return;\r
a3bcde70 HT	375	}\r
	376	\r
	377	//\r
	378	// Free all the route table entry and its route cache.\r
	379	//\r
c720da28	380	for (Index = 0; Index <= IP6_PREFIX_MAX; Index++) {\r
a3bcde70 HT	381	NET_LIST_FOR_EACH_SAFE (Entry, Next, &RtTable->RouteArea[Index]) {\r
	382	RtEntry = NET_LIST_USER_STRUCT (Entry, IP6_ROUTE_ENTRY, Link);\r
	383	RemoveEntryList (Entry);\r
	384	Ip6FreeRouteEntry (RtEntry);\r
	385	}\r
	386	}\r
	387	\r
	388	for (Index = 0; Index < IP6_ROUTE_CACHE_HASH_SIZE; Index++) {\r
	389	NET_LIST_FOR_EACH_SAFE (Entry, Next, &RtTable->Cache.CacheBucket[Index]) {\r
	390	RtCacheEntry = NET_LIST_USER_STRUCT (Entry, IP6_ROUTE_CACHE_ENTRY, Link);\r
	391	RemoveEntryList (Entry);\r
	392	Ip6FreeRouteCacheEntry (RtCacheEntry);\r
	393	}\r
	394	}\r
	395	\r
	396	FreePool (RtTable);\r
	397	}\r
	398	\r
	399	/**\r
	400	Remove all the cache entries bearing the Tag. When a route cache\r
	401	entry is created, it is tagged with the address of route entry\r
	402	from which it is spawned. When a route entry is deleted, the cache\r
	403	entries spawned from it are also deleted.\r
	404	\r
	405	@param[in] RtCache Route cache to remove the entries from.\r
	406	@param[in] Tag The Tag of the entries to remove.\r
	407	\r
	408	**/\r
	409	VOID\r
	410	Ip6PurgeRouteCache (\r
d1050b9d MK	411	IN IP6_ROUTE_CACHE *RtCache,\r
d1050b9d MK	412	IN UINTN Tag\r
a3bcde70 HT	413	)\r
a3bcde70 HT	414	{\r
d1050b9d MK	415	LIST_ENTRY *Entry;\r
	416	LIST_ENTRY *Next;\r
	417	IP6_ROUTE_CACHE_ENTRY *RtCacheEntry;\r
	418	UINT32 Index;\r
a3bcde70 HT	419	\r
	420	for (Index = 0; Index < IP6_ROUTE_CACHE_HASH_SIZE; Index++) {\r
	421	NET_LIST_FOR_EACH_SAFE (Entry, Next, &RtCache->CacheBucket[Index]) {\r
a3bcde70 HT	422	RtCacheEntry = NET_LIST_USER_STRUCT (Entry, IP6_ROUTE_CACHE_ENTRY, Link);\r
	423	\r
	424	if (RtCacheEntry->Tag == Tag) {\r
	425	RemoveEntryList (Entry);\r
	426	Ip6FreeRouteCacheEntry (RtCacheEntry);\r
	427	}\r
	428	}\r
	429	}\r
	430	}\r
	431	\r
	432	/**\r
	433	Add a route entry to the route table. It is the help function for EfiIp6Routes.\r
	434	\r
	435	@param[in, out] RtTable Route table to add route to.\r
	436	@param[in] Destination The destination of the network.\r
	437	@param[in] PrefixLength The PrefixLength of the destination.\r
	438	@param[in] GatewayAddress The next hop address.\r
	439	\r
	440	@retval EFI_ACCESS_DENIED The same route already exists.\r
	441	@retval EFI_OUT_OF_RESOURCES Failed to allocate memory for the entry.\r
	442	@retval EFI_SUCCESS The route was added successfully.\r
	443	\r
	444	**/\r
	445	EFI_STATUS\r
	446	Ip6AddRoute (\r
d1050b9d MK	447	IN OUT IP6_ROUTE_TABLE *RtTable,\r
	448	IN EFI_IPv6_ADDRESS *Destination,\r
	449	IN UINT8 PrefixLength,\r
	450	IN EFI_IPv6_ADDRESS *GatewayAddress\r
a3bcde70 HT	451	)\r
a3bcde70 HT	452	{\r
d1050b9d MK	453	LIST_ENTRY *ListHead;\r
	454	LIST_ENTRY *Entry;\r
	455	IP6_ROUTE_ENTRY *Route;\r
a3bcde70 HT	456	\r
	457	ListHead = &RtTable->RouteArea[PrefixLength];\r
	458	\r
	459	//\r
	460	// First check whether the route exists\r
	461	//\r
	462	NET_LIST_FOR_EACH (Entry, ListHead) {\r
	463	Route = NET_LIST_USER_STRUCT (Entry, IP6_ROUTE_ENTRY, Link);\r
	464	\r
	465	if (NetIp6IsNetEqual (Destination, &Route->Destination, PrefixLength) &&\r
d1050b9d MK	466	EFI_IP6_EQUAL (GatewayAddress, &Route->NextHop))\r
d1050b9d MK	467	{\r
a3bcde70 HT	468	return EFI_ACCESS_DENIED;\r
	469	}\r
	470	}\r
	471	\r
	472	//\r
	473	// Create a route entry and insert it to the route area.\r
	474	//\r
	475	Route = Ip6CreateRouteEntry (Destination, PrefixLength, GatewayAddress);\r
	476	\r
	477	if (Route == NULL) {\r
	478	return EFI_OUT_OF_RESOURCES;\r
	479	}\r
	480	\r
	481	if (NetIp6IsUnspecifiedAddr (GatewayAddress)) {\r
	482	Route->Flag = IP6_DIRECT_ROUTE;\r
	483	}\r
	484	\r
	485	InsertHeadList (ListHead, &Route->Link);\r
	486	RtTable->TotalNum++;\r
	487	\r
	488	return EFI_SUCCESS;\r
	489	}\r
	490	\r
	491	/**\r
	492	Remove a route entry and all the route caches spawn from it.\r
	493	It is the help function for EfiIp6Routes.\r
	494	\r
	495	@param[in, out] RtTable The route table to remove the route from.\r
	496	@param[in] Destination The destination network.\r
	497	@param[in] PrefixLength The PrefixLength of the Destination.\r
	498	@param[in] GatewayAddress The next hop address.\r
	499	\r
	500	@retval EFI_SUCCESS The route entry was successfully removed.\r
	501	@retval EFI_NOT_FOUND There is no route entry in the table with that\r
	502	property.\r
	503	\r
	504	**/\r
	505	EFI_STATUS\r
	506	Ip6DelRoute (\r
d1050b9d MK	507	IN OUT IP6_ROUTE_TABLE *RtTable,\r
	508	IN EFI_IPv6_ADDRESS *Destination,\r
	509	IN UINT8 PrefixLength,\r
	510	IN EFI_IPv6_ADDRESS *GatewayAddress\r
a3bcde70 HT	511	)\r
a3bcde70 HT	512	{\r
d1050b9d MK	513	LIST_ENTRY *ListHead;\r
	514	LIST_ENTRY *Entry;\r
	515	LIST_ENTRY *Next;\r
	516	IP6_ROUTE_ENTRY *Route;\r
	517	UINT32 TotalNum;\r
a3bcde70 HT	518	\r
	519	ListHead = &RtTable->RouteArea[PrefixLength];\r
	520	TotalNum = RtTable->TotalNum;\r
	521	\r
	522	NET_LIST_FOR_EACH_SAFE (Entry, Next, ListHead) {\r
	523	Route = NET_LIST_USER_STRUCT (Entry, IP6_ROUTE_ENTRY, Link);\r
	524	\r
d1050b9d	525	if ((Destination != NULL) && !NetIp6IsNetEqual (Destination, &Route->Destination, PrefixLength)) {\r
a3bcde70 HT	526	continue;\r
a3bcde70 HT	527	}\r
d1050b9d MK	528	\r
d1050b9d MK	529	if ((GatewayAddress != NULL) && !EFI_IP6_EQUAL (GatewayAddress, &Route->NextHop)) {\r
a3bcde70 HT	530	continue;\r
	531	}\r
	532	\r
d1050b9d	533	Ip6PurgeRouteCache (&RtTable->Cache, (UINTN)Route);\r
a3bcde70 HT	534	RemoveEntryList (Entry);\r
	535	Ip6FreeRouteEntry (Route);\r
	536	\r
	537	ASSERT (RtTable->TotalNum > 0);\r
	538	RtTable->TotalNum--;\r
	539	}\r
	540	\r
	541	return TotalNum == RtTable->TotalNum ? EFI_NOT_FOUND : EFI_SUCCESS;\r
	542	}\r
	543	\r
	544	/**\r
	545	Search the route table to route the packet. Return/create a route\r
	546	cache if there is a route to the destination.\r
	547	\r
	548	@param[in] IpSb The IP6 service data.\r
	549	@param[in] Dest The destination address to search for.\r
	550	@param[in] Src The source address to search for.\r
	551	\r
	552	@return NULL if it failed to route the packet. Otherwise, a route cache\r
	553	entry that can be used to route packets.\r
	554	\r
	555	**/\r
	556	IP6_ROUTE_CACHE_ENTRY *\r
	557	Ip6Route (\r
d1050b9d MK	558	IN IP6_SERVICE *IpSb,\r
	559	IN EFI_IPv6_ADDRESS *Dest,\r
	560	IN EFI_IPv6_ADDRESS *Src\r
a3bcde70 HT	561	)\r
a3bcde70 HT	562	{\r
d1050b9d MK	563	IP6_ROUTE_TABLE *RtTable;\r
	564	LIST_ENTRY *ListHead;\r
	565	IP6_ROUTE_CACHE_ENTRY *RtCacheEntry;\r
	566	IP6_ROUTE_ENTRY *RtEntry;\r
	567	EFI_IPv6_ADDRESS NextHop;\r
	568	UINT32 Index;\r
a3bcde70 HT	569	\r
	570	RtTable = IpSb->RouteTable;\r
	571	\r
	572	ASSERT (RtTable != NULL);\r
	573	\r
	574	//\r
	575	// Search the destination cache in IP6_ROUTE_TABLE.\r
	576	//\r
	577	Index = IP6_ROUTE_CACHE_HASH (Dest, Src);\r
	578	ListHead = &RtTable->Cache.CacheBucket[Index];\r
	579	\r
	580	RtCacheEntry = Ip6FindRouteCache (RtTable, Dest, Src);\r
	581	\r
	582	//\r
	583	// If found, promote the cache entry to the head of the hash bucket.\r
	584	//\r
	585	if (RtCacheEntry != NULL) {\r
	586	RemoveEntryList (&RtCacheEntry->Link);\r
	587	InsertHeadList (ListHead, &RtCacheEntry->Link);\r
	588	return RtCacheEntry;\r
	589	}\r
	590	\r
	591	//\r
	592	// Search the route table for the most specific route\r
	593	//\r
	594	RtEntry = Ip6FindRouteEntry (RtTable, Dest, NULL);\r
	595	if (RtEntry == NULL) {\r
	596	return NULL;\r
	597	}\r
	598	\r
	599	//\r
	600	// Found a route to the Dest, if it is a direct route, the packet\r
	601	// will be send directly to the destination, such as for connected\r
	602	// network. Otherwise, it is an indirect route, the packet will be\r
	603	// send the next hop router.\r
	604	//\r
	605	if ((RtEntry->Flag & IP6_DIRECT_ROUTE) == IP6_DIRECT_ROUTE) {\r
	606	IP6_COPY_ADDRESS (&NextHop, Dest);\r
	607	} else {\r
	608	IP6_COPY_ADDRESS (&NextHop, &RtEntry->NextHop);\r
	609	}\r
	610	\r
	611	Ip6FreeRouteEntry (RtEntry);\r
	612	\r
	613	//\r
	614	// Create a route cache entry, and tag it as spawned from this route entry\r
	615	//\r
d1050b9d	616	RtCacheEntry = Ip6CreateRouteCacheEntry (Dest, Src, &NextHop, (UINTN)RtEntry);\r
a3bcde70 HT	617	\r
	618	if (RtCacheEntry == NULL) {\r
	619	return NULL;\r
	620	}\r
	621	\r
	622	InsertHeadList (ListHead, &RtCacheEntry->Link);\r
	623	NET_GET_REF (RtCacheEntry);\r
	624	RtTable->Cache.CacheNum[Index]++;\r
	625	\r
	626	return RtCacheEntry;\r
	627	}\r