From af1a266670d040d2f4083ff309d732d648afba2a Mon Sep 17 00:00:00 2001 From: Angelos Mouzakitis Date: Tue, 10 Oct 2023 14:33:42 +0000 Subject: Add submodule dependency files Change-Id: Iaf8d18082d3991dec7c0ebbea540f092188eb4ec --- roms/edk2/NetworkPkg/Ip4Dxe/Ip4Route.c | 673 +++++++++++++++++++++++++++++++++ 1 file changed, 673 insertions(+) create mode 100644 roms/edk2/NetworkPkg/Ip4Dxe/Ip4Route.c (limited to 'roms/edk2/NetworkPkg/Ip4Dxe/Ip4Route.c') diff --git a/roms/edk2/NetworkPkg/Ip4Dxe/Ip4Route.c b/roms/edk2/NetworkPkg/Ip4Dxe/Ip4Route.c new file mode 100644 index 000000000..386011934 --- /dev/null +++ b/roms/edk2/NetworkPkg/Ip4Dxe/Ip4Route.c @@ -0,0 +1,673 @@ +/** @file + +Copyright (c) 2005 - 2016, Intel Corporation. All rights reserved.
+SPDX-License-Identifier: BSD-2-Clause-Patent + +**/ + +#include "Ip4Impl.h" + + +/** + Allocate a route entry then initialize it with the Dest/Netmask + and Gateway. + + @param[in] Dest The destination network + @param[in] Netmask The destination network mask + @param[in] GateWay The nexthop address + + @return NULL if failed to allocate memory, otherwise the newly created + route entry. + +**/ +IP4_ROUTE_ENTRY * +Ip4CreateRouteEntry ( + IN IP4_ADDR Dest, + IN IP4_ADDR Netmask, + IN IP4_ADDR GateWay + ) +{ + IP4_ROUTE_ENTRY *RtEntry; + + RtEntry = AllocatePool (sizeof (IP4_ROUTE_ENTRY)); + + if (RtEntry == NULL) { + return NULL; + } + + InitializeListHead (&RtEntry->Link); + + RtEntry->RefCnt = 1; + RtEntry->Dest = Dest; + RtEntry->Netmask = Netmask; + RtEntry->NextHop = GateWay; + RtEntry->Flag = 0; + + return RtEntry; +} + + +/** + Free the route table entry. It is reference counted. + + @param RtEntry The route entry to free. + +**/ +VOID +Ip4FreeRouteEntry ( + IN IP4_ROUTE_ENTRY *RtEntry + ) +{ + ASSERT (RtEntry->RefCnt > 0); + + if (--RtEntry->RefCnt == 0) { + FreePool (RtEntry); + } +} + + +/** + Allocate and initialize an IP4 route cache entry. + + @param[in] Dst The destination address + @param[in] Src The source address + @param[in] GateWay The next hop address + @param[in] Tag The tag from the caller. This marks all the cache + entries spawned from one route table entry. + + @return NULL if failed to allocate memory for the cache, other point + to the created route cache entry. + +**/ +IP4_ROUTE_CACHE_ENTRY * +Ip4CreateRouteCacheEntry ( + IN IP4_ADDR Dst, + IN IP4_ADDR Src, + IN IP4_ADDR GateWay, + IN UINTN Tag + ) +{ + IP4_ROUTE_CACHE_ENTRY *RtCacheEntry; + + RtCacheEntry = AllocatePool (sizeof (IP4_ROUTE_CACHE_ENTRY)); + + if (RtCacheEntry == NULL) { + return NULL; + } + + InitializeListHead (&RtCacheEntry->Link); + + RtCacheEntry->RefCnt = 1; + RtCacheEntry->Dest = Dst; + RtCacheEntry->Src = Src; + RtCacheEntry->NextHop = GateWay; + RtCacheEntry->Tag = Tag; + + return RtCacheEntry; +} + + +/** + Free the route cache entry. It is reference counted. + + @param RtCacheEntry The route cache entry to free. + +**/ +VOID +Ip4FreeRouteCacheEntry ( + IN IP4_ROUTE_CACHE_ENTRY *RtCacheEntry + ) +{ + ASSERT (RtCacheEntry->RefCnt > 0); + + if (--RtCacheEntry->RefCnt == 0) { + FreePool (RtCacheEntry); + } +} + + +/** + Initialize an empty route cache table. + + @param[in, out] RtCache The route cache table to initialize. + +**/ +VOID +Ip4InitRouteCache ( + IN OUT IP4_ROUTE_CACHE *RtCache + ) +{ + UINT32 Index; + + for (Index = 0; Index < IP4_ROUTE_CACHE_HASH_VALUE; Index++) { + InitializeListHead (&(RtCache->CacheBucket[Index])); + } +} + + +/** + Clean up a route cache, that is free all the route cache + entries enqueued in the cache. + + @param[in] RtCache The route cache table to clean up + +**/ +VOID +Ip4CleanRouteCache ( + IN IP4_ROUTE_CACHE *RtCache + ) +{ + LIST_ENTRY *Entry; + LIST_ENTRY *Next; + IP4_ROUTE_CACHE_ENTRY *RtCacheEntry; + UINT32 Index; + + for (Index = 0; Index < IP4_ROUTE_CACHE_HASH_VALUE; Index++) { + NET_LIST_FOR_EACH_SAFE (Entry, Next, &(RtCache->CacheBucket[Index])) { + RtCacheEntry = NET_LIST_USER_STRUCT (Entry, IP4_ROUTE_CACHE_ENTRY, Link); + + RemoveEntryList (Entry); + Ip4FreeRouteCacheEntry (RtCacheEntry); + } + } +} + + + +/** + Create an empty route table, includes its internal route cache + + @return NULL if failed to allocate memory for the route table, otherwise + the point to newly created route table. + +**/ +IP4_ROUTE_TABLE * +Ip4CreateRouteTable ( + VOID + ) +{ + IP4_ROUTE_TABLE *RtTable; + UINT32 Index; + + RtTable = AllocatePool (sizeof (IP4_ROUTE_TABLE)); + + if (RtTable == NULL) { + return NULL; + } + + RtTable->RefCnt = 1; + RtTable->TotalNum = 0; + + for (Index = 0; Index <= IP4_MASK_MAX; Index++) { + InitializeListHead (&(RtTable->RouteArea[Index])); + } + + RtTable->Next = NULL; + + Ip4InitRouteCache (&RtTable->Cache); + return RtTable; +} + + +/** + Free the route table and its associated route cache. Route + table is reference counted. + + @param[in] RtTable The route table to free. + +**/ +VOID +Ip4FreeRouteTable ( + IN IP4_ROUTE_TABLE *RtTable + ) +{ + LIST_ENTRY *Entry; + LIST_ENTRY *Next; + IP4_ROUTE_ENTRY *RtEntry; + UINT32 Index; + + ASSERT (RtTable->RefCnt > 0); + + if (--RtTable->RefCnt > 0) { + return ; + } + + // + // Free all the route table entry and its route cache. + // + for (Index = 0; Index <= IP4_MASK_MAX; Index++) { + NET_LIST_FOR_EACH_SAFE (Entry, Next, &(RtTable->RouteArea[Index])) { + RtEntry = NET_LIST_USER_STRUCT (Entry, IP4_ROUTE_ENTRY, Link); + + RemoveEntryList (Entry); + Ip4FreeRouteEntry (RtEntry); + } + } + + Ip4CleanRouteCache (&RtTable->Cache); + + FreePool (RtTable); +} + + + +/** + Remove all the cache entries bearing the Tag. When a route cache + entry is created, it is tagged with the address of route entry + from which it is spawned. When a route entry is deleted, the cache + entries spawned from it are also deleted. + + @param RtCache Route cache to remove the entries from + @param Tag The Tag of the entries to remove + +**/ +VOID +Ip4PurgeRouteCache ( + IN OUT IP4_ROUTE_CACHE *RtCache, + IN UINTN Tag + ) +{ + LIST_ENTRY *Entry; + LIST_ENTRY *Next; + IP4_ROUTE_CACHE_ENTRY *RtCacheEntry; + UINT32 Index; + + for (Index = 0; Index < IP4_ROUTE_CACHE_HASH_VALUE; Index++) { + NET_LIST_FOR_EACH_SAFE (Entry, Next, &RtCache->CacheBucket[Index]) { + + RtCacheEntry = NET_LIST_USER_STRUCT (Entry, IP4_ROUTE_CACHE_ENTRY, Link); + + if (RtCacheEntry->Tag == Tag) { + RemoveEntryList (Entry); + Ip4FreeRouteCacheEntry (RtCacheEntry); + } + } + } +} + + +/** + Add a route entry to the route table. All the IP4_ADDRs are in + host byte order. + + @param[in, out] RtTable Route table to add route to + @param[in] Dest The destination of the network + @param[in] Netmask The netmask of the destination + @param[in] Gateway The next hop address + + @retval EFI_ACCESS_DENIED The same route already exists + @retval EFI_OUT_OF_RESOURCES Failed to allocate memory for the entry + @retval EFI_SUCCESS The route is added successfully. + +**/ +EFI_STATUS +Ip4AddRoute ( + IN OUT IP4_ROUTE_TABLE *RtTable, + IN IP4_ADDR Dest, + IN IP4_ADDR Netmask, + IN IP4_ADDR Gateway + ) +{ + LIST_ENTRY *Head; + LIST_ENTRY *Entry; + IP4_ROUTE_ENTRY *RtEntry; + + // + // All the route entries with the same netmask length are + // linke to the same route area + // + Head = &(RtTable->RouteArea[NetGetMaskLength (Netmask)]); + + // + // First check whether the route exists + // + NET_LIST_FOR_EACH (Entry, Head) { + RtEntry = NET_LIST_USER_STRUCT (Entry, IP4_ROUTE_ENTRY, Link); + + if (IP4_NET_EQUAL (RtEntry->Dest, Dest, Netmask) && (RtEntry->NextHop == Gateway)) { + return EFI_ACCESS_DENIED; + } + } + + // + // Create a route entry and insert it to the route area. + // + RtEntry = Ip4CreateRouteEntry (Dest, Netmask, Gateway); + + if (RtEntry == NULL) { + return EFI_OUT_OF_RESOURCES; + } + + if (Gateway == IP4_ALLZERO_ADDRESS) { + RtEntry->Flag = IP4_DIRECT_ROUTE; + } + + InsertHeadList (Head, &RtEntry->Link); + RtTable->TotalNum++; + + return EFI_SUCCESS; +} + + +/** + Remove a route entry and all the route caches spawn from it. + + @param RtTable The route table to remove the route from + @param Dest The destination network + @param Netmask The netmask of the Dest + @param Gateway The next hop address + + @retval EFI_SUCCESS The route entry is successfully removed + @retval EFI_NOT_FOUND There is no route entry in the table with that + property. + +**/ +EFI_STATUS +Ip4DelRoute ( + IN OUT IP4_ROUTE_TABLE *RtTable, + IN IP4_ADDR Dest, + IN IP4_ADDR Netmask, + IN IP4_ADDR Gateway + ) +{ + LIST_ENTRY *Head; + LIST_ENTRY *Entry; + LIST_ENTRY *Next; + IP4_ROUTE_ENTRY *RtEntry; + + Head = &(RtTable->RouteArea[NetGetMaskLength (Netmask)]); + + NET_LIST_FOR_EACH_SAFE (Entry, Next, Head) { + RtEntry = NET_LIST_USER_STRUCT (Entry, IP4_ROUTE_ENTRY, Link); + + if (IP4_NET_EQUAL (RtEntry->Dest, Dest, Netmask) && (RtEntry->NextHop == Gateway)) { + Ip4PurgeRouteCache (&RtTable->Cache, (UINTN) RtEntry); + RemoveEntryList (Entry); + Ip4FreeRouteEntry (RtEntry); + + RtTable->TotalNum--; + return EFI_SUCCESS; + } + } + + return EFI_NOT_FOUND; +} + + +/** + Find a route cache with the dst and src. This is used by ICMP + redirect message process. All kinds of redirect is treated as + host redirect according to RFC1122. So, only route cache entries + are modified according to the ICMP redirect message. + + @param[in] RtTable The route table to search the cache for + @param[in] Dest The destination address + @param[in] Src The source address + + @return NULL if no route entry to the (Dest, Src). Otherwise the point + to the correct route cache entry. + +**/ +IP4_ROUTE_CACHE_ENTRY * +Ip4FindRouteCache ( + IN IP4_ROUTE_TABLE *RtTable, + IN IP4_ADDR Dest, + IN IP4_ADDR Src + ) +{ + LIST_ENTRY *Entry; + IP4_ROUTE_CACHE_ENTRY *RtCacheEntry; + UINT32 Index; + + Index = IP4_ROUTE_CACHE_HASH (Dest, Src); + + NET_LIST_FOR_EACH (Entry, &RtTable->Cache.CacheBucket[Index]) { + RtCacheEntry = NET_LIST_USER_STRUCT (Entry, IP4_ROUTE_CACHE_ENTRY, Link); + + if ((RtCacheEntry->Dest == Dest) && (RtCacheEntry->Src == Src)) { + NET_GET_REF (RtCacheEntry); + return RtCacheEntry; + } + } + + return NULL; +} + + +/** + Search the route table for a most specific match to the Dst. It searches + from the longest route area (mask length == 32) to the shortest route area + (default routes). In each route area, it will first search the instance's + route table, then the default route table. This is required by the following + requirements: + 1. IP search the route table for a most specific match + 2. The local route entries have precedence over the default route entry. + + @param[in] RtTable The route table to search from + @param[in] Dst The destination address to search + + @return NULL if no route matches the Dst, otherwise the point to the + most specific route to the Dst. + +**/ +IP4_ROUTE_ENTRY * +Ip4FindRouteEntry ( + IN IP4_ROUTE_TABLE *RtTable, + IN IP4_ADDR Dst + ) +{ + LIST_ENTRY *Entry; + IP4_ROUTE_ENTRY *RtEntry; + IP4_ROUTE_TABLE *Table; + INTN Index; + + RtEntry = NULL; + + for (Index = IP4_MASK_MAX; Index >= 0; Index--) { + for (Table = RtTable; Table != NULL; Table = Table->Next) { + NET_LIST_FOR_EACH (Entry, &Table->RouteArea[Index]) { + RtEntry = NET_LIST_USER_STRUCT (Entry, IP4_ROUTE_ENTRY, Link); + + if (IP4_NET_EQUAL (RtEntry->Dest, Dst, RtEntry->Netmask)) { + NET_GET_REF (RtEntry); + return RtEntry; + } + } + } + } + + + return NULL; +} + + +/** + Search the route table to route the packet. Return/create a route + cache if there is a route to the destination. + + @param[in] RtTable The route table to search from + @param[in] Dest The destination address to search for + @param[in] Src The source address to search for + @param[in] SubnetMask The subnet mask of the Src address, this field is + used to check if the station is using /32 subnet. + @param[in] AlwaysTryDestAddr Always try to use the dest address as next hop even + though we can't find a matching route entry. This + field is only valid when using /32 subnet. + + @return NULL if failed to route packet, otherwise a route cache + entry that can be used to route packet. + +**/ +IP4_ROUTE_CACHE_ENTRY * +Ip4Route ( + IN IP4_ROUTE_TABLE *RtTable, + IN IP4_ADDR Dest, + IN IP4_ADDR Src, + IN IP4_ADDR SubnetMask, + IN BOOLEAN AlwaysTryDestAddr + ) +{ + LIST_ENTRY *Head; + LIST_ENTRY *Entry; + LIST_ENTRY *Next; + IP4_ROUTE_CACHE_ENTRY *RtCacheEntry; + IP4_ROUTE_CACHE_ENTRY *Cache; + IP4_ROUTE_ENTRY *RtEntry; + IP4_ADDR NextHop; + UINT32 Count; + + ASSERT (RtTable != NULL); + + Head = &RtTable->Cache.CacheBucket[IP4_ROUTE_CACHE_HASH (Dest, Src)]; + RtCacheEntry = Ip4FindRouteCache (RtTable, Dest, Src); + + // + // If found, promote the cache entry to the head of the hash bucket. LRU + // + if (RtCacheEntry != NULL) { + RemoveEntryList (&RtCacheEntry->Link); + InsertHeadList (Head, &RtCacheEntry->Link); + return RtCacheEntry; + } + + // + // Search the route table for the most specific route + // + RtEntry = Ip4FindRouteEntry (RtTable, Dest); + + if (RtEntry == NULL) { + if (SubnetMask != IP4_ALLONE_ADDRESS) { + return NULL; + } else if (!AlwaysTryDestAddr) { + return NULL; + } + } + + // + // Found a route to the Dest, if it is a direct route, the packet + // will be sent directly to the destination, such as for connected + // network. Otherwise, it is an indirect route, the packet will be + // sent to the next hop router. + // + // When using /32 subnet mask, the packet will always be sent to the direct + // destination first, if we can't find a matching route cache. + // + if (SubnetMask == IP4_ALLONE_ADDRESS || ((RtEntry->Flag & IP4_DIRECT_ROUTE) != 0)) { + NextHop = Dest; + } else { + NextHop = RtEntry->NextHop; + } + + if (RtEntry != NULL) { + Ip4FreeRouteEntry (RtEntry); + } + + // + // Create a route cache entry, and tag it as spawned from this route entry + // For /32 subnet mask, the default route in RtEntry will be used if failed + // to send the packet to driect destination address. + // + RtCacheEntry = Ip4CreateRouteCacheEntry (Dest, Src, NextHop, (UINTN) RtEntry); + + if (RtCacheEntry == NULL) { + return NULL; + } + + InsertHeadList (Head, &RtCacheEntry->Link); + NET_GET_REF (RtCacheEntry); + + // + // Each bucket of route cache can contain at most 64 entries. + // Remove the entries at the tail of the bucket. These entries + // are likely to be used least. + // + Count = 0; + NET_LIST_FOR_EACH_SAFE (Entry, Next, Head) { + if (++Count < IP4_ROUTE_CACHE_MAX) { + continue; + } + + Cache = NET_LIST_USER_STRUCT (Entry, IP4_ROUTE_CACHE_ENTRY, Link); + + RemoveEntryList (Entry); + Ip4FreeRouteCacheEntry (Cache); + } + + return RtCacheEntry; +} + + +/** + Build a EFI_IP4_ROUTE_TABLE to be returned to the caller of + GetModeData. The EFI_IP4_ROUTE_TABLE is clumsy to use in the + internal operation of the IP4 driver. + + @param[in] IpInstance The IP4 child that requests the route table. + + @retval EFI_SUCCESS The route table is successfully build + @retval EFI_OUT_OF_RESOURCES Failed to allocate the memory for the route table. + +**/ +EFI_STATUS +Ip4BuildEfiRouteTable ( + IN IP4_PROTOCOL *IpInstance + ) +{ + LIST_ENTRY *Entry; + IP4_ROUTE_TABLE *RtTable; + IP4_ROUTE_ENTRY *RtEntry; + EFI_IP4_ROUTE_TABLE *Table; + UINT32 Count; + INT32 Index; + + RtTable = IpInstance->RouteTable; + + if (IpInstance->EfiRouteTable != NULL) { + FreePool (IpInstance->EfiRouteTable); + + IpInstance->EfiRouteTable = NULL; + IpInstance->EfiRouteCount = 0; + } + + Count = RtTable->TotalNum; + + if (RtTable->Next != NULL) { + Count += RtTable->Next->TotalNum; + } + + if (Count == 0) { + return EFI_SUCCESS; + } + + Table = AllocatePool (sizeof (EFI_IP4_ROUTE_TABLE) * Count); + + if (Table == NULL) { + return EFI_OUT_OF_RESOURCES; + } + + // + // Copy the route entry to EFI route table. Keep the order of + // route entry copied from most specific to default route. That + // is, interlevel the route entry from the instance's route area + // and those from the default route table's route area. + // + Count = 0; + + for (Index = IP4_MASK_MAX; Index >= 0; Index--) { + for (RtTable = IpInstance->RouteTable; RtTable != NULL; RtTable = RtTable->Next) { + NET_LIST_FOR_EACH (Entry, &(RtTable->RouteArea[Index])) { + RtEntry = NET_LIST_USER_STRUCT (Entry, IP4_ROUTE_ENTRY, Link); + + EFI_IP4 (Table[Count].SubnetAddress) = HTONL (RtEntry->Dest & RtEntry->Netmask); + EFI_IP4 (Table[Count].SubnetMask) = HTONL (RtEntry->Netmask); + EFI_IP4 (Table[Count].GatewayAddress) = HTONL (RtEntry->NextHop); + + Count++; + } + } + } + + IpInstance->EfiRouteTable = Table; + IpInstance->EfiRouteCount = Count; + return EFI_SUCCESS; +} -- cgit 1.2.3-korg