123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869707172737475767778798081828384858687888990919293949596979899100101102103104105106107108109110111112113114115116117118119120121122123124125126127128129130131132133134135136137138139140141142143144145146147148149150151152153154155156157158159160161162163164165166167168169170171172173174175176177178179180181182183184185186187188189190191192193194195196197198199200201202203204205206207208209210211212213214215216217218219220221222223224225226227228229230231232233234235236237238239240241242243244245246247248249250251252253254255256257258259260261262263264265266267268269270271272273274275276277278279280281282283284285286287288289290291292293294295296297298299300301302303304305306307308309310311312313314315316317318319320321322323324325326327328329330331332333334335336337338339340341342343344345346347348349350351352353354355356357358359360361362363364365366367368369370371372373374375376377378379380381382383384385386387388389390391392393394395396397398399400401402403404405406407408409410411412413414415416417418419420421422423424425426427428429430431432433434435436437438439440441442443444445446447448449450451452453454455456457458459460461462463464465466467468469470471472473474475476477478479480481482483484485486487488489490491492493494495496497498499500501502503504505506507508509510511512513514515516517518519520521522523524525526527528529530531532533534535536537538539540541542543544545546547548549550551552553554555556557558559560561562563564565566567568569570571572573574575576577578579580581582583584585586587588589590591592593594595596597598599600601602603604605606607608609610611612613614615616617618619620621622623624625626627 |
- /** @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;
- }
|