CloverBootloader/NetworkPkg/Ip6Dxe/Ip6Route.c

628 lines
17 KiB
C

/** @file
The functions and routines to handle the route caches and route table.
Copyright (c) 2009 - 2016, Intel Corporation. All rights reserved.<BR>
SPDX-License-Identifier: BSD-2-Clause-Patent
**/
#include "Ip6Impl.h"
/**
This is the worker function for IP6_ROUTE_CACHE_HASH(). It calculates the value
as the index of the route cache bucket according to the prefix of two IPv6 addresses.
@param[in] Ip1 The IPv6 address.
@param[in] Ip2 The IPv6 address.
@return The hash value of the prefix of two IPv6 addresses.
**/
UINT32
Ip6RouteCacheHash (
IN EFI_IPv6_ADDRESS *Ip1,
IN EFI_IPv6_ADDRESS *Ip2
)
{
UINT32 Prefix1;
UINT32 Prefix2;
Prefix1 = *((UINT32 *)((UINTN *)(Ip1)));
Prefix2 = *((UINT32 *)((UINTN *)(Ip2)));
return ((UINT32)(Prefix1 ^ Prefix2) % IP6_ROUTE_CACHE_HASH_SIZE);
}
/**
Allocate a route entry then initialize it with the Destination/PrefixLength
and Gateway.
@param[in] Destination The IPv6 destination address. This is an optional
parameter that may be NULL.
@param[in] PrefixLength The destination network's prefix length.
@param[in] GatewayAddress The next hop address. This is an optional parameter
that may be NULL.
@return NULL if failed to allocate memory; otherwise, the newly created route entry.
**/
IP6_ROUTE_ENTRY *
Ip6CreateRouteEntry (
IN EFI_IPv6_ADDRESS *Destination OPTIONAL,
IN UINT8 PrefixLength,
IN EFI_IPv6_ADDRESS *GatewayAddress OPTIONAL
)
{
IP6_ROUTE_ENTRY *RtEntry;
RtEntry = AllocateZeroPool (sizeof (IP6_ROUTE_ENTRY));
if (RtEntry == NULL) {
return NULL;
}
RtEntry->RefCnt = 1;
RtEntry->Flag = 0;
RtEntry->PrefixLength = PrefixLength;
if (Destination != NULL) {
IP6_COPY_ADDRESS (&RtEntry->Destination, Destination);
}
if (GatewayAddress != NULL) {
IP6_COPY_ADDRESS (&RtEntry->NextHop, GatewayAddress);
}
return RtEntry;
}
/**
Free the route table entry. It is reference counted.
@param[in, out] RtEntry The route entry to free.
**/
VOID
Ip6FreeRouteEntry (
IN OUT IP6_ROUTE_ENTRY *RtEntry
)
{
ASSERT ((RtEntry != NULL) && (RtEntry->RefCnt > 0));
if (--RtEntry->RefCnt == 0) {
FreePool (RtEntry);
}
}
/**
Search the route table for a most specific match to the Dst. It searches
from the longest route area (prefix length == 128) 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 per 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] Destination The destination address to search. If NULL, search
the route table by NextHop.
@param[in] NextHop The next hop address. If NULL, search the route table
by Destination.
@return NULL if no route matches the Dst. Otherwise, the point to the
@return most specific route to the Dst.
**/
IP6_ROUTE_ENTRY *
Ip6FindRouteEntry (
IN IP6_ROUTE_TABLE *RtTable,
IN EFI_IPv6_ADDRESS *Destination OPTIONAL,
IN EFI_IPv6_ADDRESS *NextHop OPTIONAL
)
{
LIST_ENTRY *Entry;
IP6_ROUTE_ENTRY *RtEntry;
INTN Index;
ASSERT (Destination != NULL || NextHop != NULL);
RtEntry = NULL;
for (Index = IP6_PREFIX_MAX; Index >= 0; Index--) {
NET_LIST_FOR_EACH (Entry, &RtTable->RouteArea[Index]) {
RtEntry = NET_LIST_USER_STRUCT (Entry, IP6_ROUTE_ENTRY, Link);
if (Destination != NULL) {
if (NetIp6IsNetEqual (Destination, &RtEntry->Destination, RtEntry->PrefixLength)) {
NET_GET_REF (RtEntry);
return RtEntry;
}
} else if (NextHop != NULL) {
if (NetIp6IsNetEqual (NextHop, &RtEntry->NextHop, RtEntry->PrefixLength)) {
NET_GET_REF (RtEntry);
return RtEntry;
}
}
}
}
return NULL;
}
/**
Allocate and initialize a IP6 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. Otherwise, point
to the created route cache entry.
**/
IP6_ROUTE_CACHE_ENTRY *
Ip6CreateRouteCacheEntry (
IN EFI_IPv6_ADDRESS *Dst,
IN EFI_IPv6_ADDRESS *Src,
IN EFI_IPv6_ADDRESS *GateWay,
IN UINTN Tag
)
{
IP6_ROUTE_CACHE_ENTRY *RtCacheEntry;
RtCacheEntry = AllocatePool (sizeof (IP6_ROUTE_CACHE_ENTRY));
if (RtCacheEntry == NULL) {
return NULL;
}
RtCacheEntry->RefCnt = 1;
RtCacheEntry->Tag = Tag;
IP6_COPY_ADDRESS (&RtCacheEntry->Destination, Dst);
IP6_COPY_ADDRESS (&RtCacheEntry->Source, Src);
IP6_COPY_ADDRESS (&RtCacheEntry->NextHop, GateWay);
return RtCacheEntry;
}
/**
Free the route cache entry. It is reference counted.
@param[in, out] RtCacheEntry The route cache entry to free.
**/
VOID
Ip6FreeRouteCacheEntry (
IN OUT IP6_ROUTE_CACHE_ENTRY *RtCacheEntry
)
{
ASSERT (RtCacheEntry->RefCnt > 0);
if (--RtCacheEntry->RefCnt == 0) {
FreePool (RtCacheEntry);
}
}
/**
Find a route cache with the destination and source address. This is
used by the ICMPv6 redirect message process.
@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 pointer
to the correct route cache entry.
**/
IP6_ROUTE_CACHE_ENTRY *
Ip6FindRouteCache (
IN IP6_ROUTE_TABLE *RtTable,
IN EFI_IPv6_ADDRESS *Dest,
IN EFI_IPv6_ADDRESS *Src
)
{
LIST_ENTRY *Entry;
IP6_ROUTE_CACHE_ENTRY *RtCacheEntry;
UINT32 Index;
Index = IP6_ROUTE_CACHE_HASH (Dest, Src);
NET_LIST_FOR_EACH (Entry, &RtTable->Cache.CacheBucket[Index]) {
RtCacheEntry = NET_LIST_USER_STRUCT (Entry, IP6_ROUTE_CACHE_ENTRY, Link);
if (EFI_IP6_EQUAL (Dest, &RtCacheEntry->Destination) && EFI_IP6_EQUAL (Src, &RtCacheEntry->Source)) {
NET_GET_REF (RtCacheEntry);
return RtCacheEntry;
}
}
return NULL;
}
/**
Build an array of EFI_IP6_ROUTE_TABLE to be returned to the caller. The number
of EFI_IP6_ROUTE_TABLE is also returned.
@param[in] RouteTable The pointer of IP6_ROUTE_TABLE internal used.
@param[out] EfiRouteCount The number of returned route entries.
@param[out] EfiRouteTable The pointer to the array of EFI_IP6_ROUTE_TABLE.
If NULL, only the route entry count is returned.
@retval EFI_SUCCESS The EFI_IP6_ROUTE_TABLE successfully built.
@retval EFI_OUT_OF_RESOURCES Failed to allocate the memory for the route table.
**/
EFI_STATUS
Ip6BuildEfiRouteTable (
IN IP6_ROUTE_TABLE *RouteTable,
OUT UINT32 *EfiRouteCount,
OUT EFI_IP6_ROUTE_TABLE **EfiRouteTable OPTIONAL
)
{
LIST_ENTRY *Entry;
IP6_ROUTE_ENTRY *RtEntry;
EFI_IP6_ROUTE_TABLE *EfiTable;
UINT32 Count;
INT32 Index;
ASSERT (EfiRouteCount != NULL);
Count = RouteTable->TotalNum;
*EfiRouteCount = Count;
if ((EfiRouteTable == NULL) || (Count == 0)) {
return EFI_SUCCESS;
}
if (*EfiRouteTable == NULL) {
*EfiRouteTable = AllocatePool (sizeof (EFI_IP6_ROUTE_TABLE) * Count);
if (*EfiRouteTable == NULL) {
return EFI_OUT_OF_RESOURCES;
}
}
EfiTable = *EfiRouteTable;
//
// Copy the route entry to EFI route table.
//
Count = 0;
for (Index = IP6_PREFIX_MAX; Index >= 0; Index--) {
NET_LIST_FOR_EACH (Entry, &(RouteTable->RouteArea[Index])) {
RtEntry = NET_LIST_USER_STRUCT (Entry, IP6_ROUTE_ENTRY, Link);
Ip6CopyAddressByPrefix (
&EfiTable[Count].Destination,
&RtEntry->Destination,
RtEntry->PrefixLength
);
IP6_COPY_ADDRESS (&EfiTable[Count].Gateway, &RtEntry->NextHop);
EfiTable[Count].PrefixLength = RtEntry->PrefixLength;
Count++;
}
}
ASSERT (Count == RouteTable->TotalNum);
return EFI_SUCCESS;
}
/**
Create an empty route table. This includes its internal route cache.
@return NULL if failed to allocate memory for the route table. Otherwise,
the point to newly created route table.
**/
IP6_ROUTE_TABLE *
Ip6CreateRouteTable (
VOID
)
{
IP6_ROUTE_TABLE *RtTable;
UINT32 Index;
RtTable = AllocatePool (sizeof (IP6_ROUTE_TABLE));
if (RtTable == NULL) {
return NULL;
}
RtTable->RefCnt = 1;
RtTable->TotalNum = 0;
for (Index = 0; Index <= IP6_PREFIX_MAX; Index++) {
InitializeListHead (&RtTable->RouteArea[Index]);
}
for (Index = 0; Index < IP6_ROUTE_CACHE_HASH_SIZE; Index++) {
InitializeListHead (&RtTable->Cache.CacheBucket[Index]);
RtTable->Cache.CacheNum[Index] = 0;
}
return RtTable;
}
/**
Free the route table and its associated route cache. Route
table is reference counted.
@param[in, out] RtTable The route table to free.
**/
VOID
Ip6CleanRouteTable (
IN OUT IP6_ROUTE_TABLE *RtTable
)
{
LIST_ENTRY *Entry;
LIST_ENTRY *Next;
IP6_ROUTE_ENTRY *RtEntry;
IP6_ROUTE_CACHE_ENTRY *RtCacheEntry;
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 <= IP6_PREFIX_MAX; Index++) {
NET_LIST_FOR_EACH_SAFE (Entry, Next, &RtTable->RouteArea[Index]) {
RtEntry = NET_LIST_USER_STRUCT (Entry, IP6_ROUTE_ENTRY, Link);
RemoveEntryList (Entry);
Ip6FreeRouteEntry (RtEntry);
}
}
for (Index = 0; Index < IP6_ROUTE_CACHE_HASH_SIZE; Index++) {
NET_LIST_FOR_EACH_SAFE (Entry, Next, &RtTable->Cache.CacheBucket[Index]) {
RtCacheEntry = NET_LIST_USER_STRUCT (Entry, IP6_ROUTE_CACHE_ENTRY, Link);
RemoveEntryList (Entry);
Ip6FreeRouteCacheEntry (RtCacheEntry);
}
}
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[in] RtCache Route cache to remove the entries from.
@param[in] Tag The Tag of the entries to remove.
**/
VOID
Ip6PurgeRouteCache (
IN IP6_ROUTE_CACHE *RtCache,
IN UINTN Tag
)
{
LIST_ENTRY *Entry;
LIST_ENTRY *Next;
IP6_ROUTE_CACHE_ENTRY *RtCacheEntry;
UINT32 Index;
for (Index = 0; Index < IP6_ROUTE_CACHE_HASH_SIZE; Index++) {
NET_LIST_FOR_EACH_SAFE (Entry, Next, &RtCache->CacheBucket[Index]) {
RtCacheEntry = NET_LIST_USER_STRUCT (Entry, IP6_ROUTE_CACHE_ENTRY, Link);
if (RtCacheEntry->Tag == Tag) {
RemoveEntryList (Entry);
Ip6FreeRouteCacheEntry (RtCacheEntry);
}
}
}
}
/**
Add a route entry to the route table. It is the help function for EfiIp6Routes.
@param[in, out] RtTable Route table to add route to.
@param[in] Destination The destination of the network.
@param[in] PrefixLength The PrefixLength of the destination.
@param[in] GatewayAddress 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 was added successfully.
**/
EFI_STATUS
Ip6AddRoute (
IN OUT IP6_ROUTE_TABLE *RtTable,
IN EFI_IPv6_ADDRESS *Destination,
IN UINT8 PrefixLength,
IN EFI_IPv6_ADDRESS *GatewayAddress
)
{
LIST_ENTRY *ListHead;
LIST_ENTRY *Entry;
IP6_ROUTE_ENTRY *Route;
ListHead = &RtTable->RouteArea[PrefixLength];
//
// First check whether the route exists
//
NET_LIST_FOR_EACH (Entry, ListHead) {
Route = NET_LIST_USER_STRUCT (Entry, IP6_ROUTE_ENTRY, Link);
if (NetIp6IsNetEqual (Destination, &Route->Destination, PrefixLength) &&
EFI_IP6_EQUAL (GatewayAddress, &Route->NextHop))
{
return EFI_ACCESS_DENIED;
}
}
//
// Create a route entry and insert it to the route area.
//
Route = Ip6CreateRouteEntry (Destination, PrefixLength, GatewayAddress);
if (Route == NULL) {
return EFI_OUT_OF_RESOURCES;
}
if (NetIp6IsUnspecifiedAddr (GatewayAddress)) {
Route->Flag = IP6_DIRECT_ROUTE;
}
InsertHeadList (ListHead, &Route->Link);
RtTable->TotalNum++;
return EFI_SUCCESS;
}
/**
Remove a route entry and all the route caches spawn from it.
It is the help function for EfiIp6Routes.
@param[in, out] RtTable The route table to remove the route from.
@param[in] Destination The destination network.
@param[in] PrefixLength The PrefixLength of the Destination.
@param[in] GatewayAddress The next hop address.
@retval EFI_SUCCESS The route entry was successfully removed.
@retval EFI_NOT_FOUND There is no route entry in the table with that
property.
**/
EFI_STATUS
Ip6DelRoute (
IN OUT IP6_ROUTE_TABLE *RtTable,
IN EFI_IPv6_ADDRESS *Destination,
IN UINT8 PrefixLength,
IN EFI_IPv6_ADDRESS *GatewayAddress
)
{
LIST_ENTRY *ListHead;
LIST_ENTRY *Entry;
LIST_ENTRY *Next;
IP6_ROUTE_ENTRY *Route;
UINT32 TotalNum;
ListHead = &RtTable->RouteArea[PrefixLength];
TotalNum = RtTable->TotalNum;
NET_LIST_FOR_EACH_SAFE (Entry, Next, ListHead) {
Route = NET_LIST_USER_STRUCT (Entry, IP6_ROUTE_ENTRY, Link);
if ((Destination != NULL) && !NetIp6IsNetEqual (Destination, &Route->Destination, PrefixLength)) {
continue;
}
if ((GatewayAddress != NULL) && !EFI_IP6_EQUAL (GatewayAddress, &Route->NextHop)) {
continue;
}
Ip6PurgeRouteCache (&RtTable->Cache, (UINTN)Route);
RemoveEntryList (Entry);
Ip6FreeRouteEntry (Route);
ASSERT (RtTable->TotalNum > 0);
RtTable->TotalNum--;
}
return TotalNum == RtTable->TotalNum ? EFI_NOT_FOUND : EFI_SUCCESS;
}
/**
Search the route table to route the packet. Return/create a route
cache if there is a route to the destination.
@param[in] IpSb The IP6 service data.
@param[in] Dest The destination address to search for.
@param[in] Src The source address to search for.
@return NULL if it failed to route the packet. Otherwise, a route cache
entry that can be used to route packets.
**/
IP6_ROUTE_CACHE_ENTRY *
Ip6Route (
IN IP6_SERVICE *IpSb,
IN EFI_IPv6_ADDRESS *Dest,
IN EFI_IPv6_ADDRESS *Src
)
{
IP6_ROUTE_TABLE *RtTable;
LIST_ENTRY *ListHead;
IP6_ROUTE_CACHE_ENTRY *RtCacheEntry;
IP6_ROUTE_ENTRY *RtEntry;
EFI_IPv6_ADDRESS NextHop;
UINT32 Index;
RtTable = IpSb->RouteTable;
ASSERT (RtTable != NULL);
//
// Search the destination cache in IP6_ROUTE_TABLE.
//
Index = IP6_ROUTE_CACHE_HASH (Dest, Src);
ListHead = &RtTable->Cache.CacheBucket[Index];
RtCacheEntry = Ip6FindRouteCache (RtTable, Dest, Src);
//
// If found, promote the cache entry to the head of the hash bucket.
//
if (RtCacheEntry != NULL) {
RemoveEntryList (&RtCacheEntry->Link);
InsertHeadList (ListHead, &RtCacheEntry->Link);
return RtCacheEntry;
}
//
// Search the route table for the most specific route
//
RtEntry = Ip6FindRouteEntry (RtTable, Dest, NULL);
if (RtEntry == NULL) {
return NULL;
}
//
// Found a route to the Dest, if it is a direct route, the packet
// will be send directly to the destination, such as for connected
// network. Otherwise, it is an indirect route, the packet will be
// send the next hop router.
//
if ((RtEntry->Flag & IP6_DIRECT_ROUTE) == IP6_DIRECT_ROUTE) {
IP6_COPY_ADDRESS (&NextHop, Dest);
} else {
IP6_COPY_ADDRESS (&NextHop, &RtEntry->NextHop);
}
Ip6FreeRouteEntry (RtEntry);
//
// Create a route cache entry, and tag it as spawned from this route entry
//
RtCacheEntry = Ip6CreateRouteCacheEntry (Dest, Src, &NextHop, (UINTN)RtEntry);
if (RtCacheEntry == NULL) {
return NULL;
}
InsertHeadList (ListHead, &RtCacheEntry->Link);
NET_GET_REF (RtCacheEntry);
RtTable->Cache.CacheNum[Index]++;
return RtCacheEntry;
}