NetworkPkg: Replace BSD License with BSD+Patent License

[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 memeory; 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 destionation 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
\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 messasge 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
\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
\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
      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
    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
\r