NetworkPkg/Ip6Dxe/Ip6Route.c

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