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   return NULL;
 151 }
 152
 153 /**
 154   Allocate and initialize a IP6 route cache entry.
 155
 156   @param[in]  Dst           The destination address.
 157   @param[in]  Src           The source address.
 158   @param[in]  GateWay       The next hop address.
 159   @param[in]  Tag           The tag from the caller. This marks all the cache entries
 160                             spawned from one route table entry.
 161
 162   @return NULL if failed to allocate memory for the cache. Otherwise, point
 163           to the created route cache entry.
 164
 165 **/
 166 IP6_ROUTE_CACHE_ENTRY *
 167 Ip6CreateRouteCacheEntry (
 168   IN EFI_IPv6_ADDRESS  *Dst,
 169   IN EFI_IPv6_ADDRESS  *Src,
 170   IN EFI_IPv6_ADDRESS  *GateWay,
 171   IN UINTN             Tag
 172   )
 173 {
 174   IP6_ROUTE_CACHE_ENTRY  *RtCacheEntry;
 175
 176   RtCacheEntry = AllocatePool (sizeof (IP6_ROUTE_CACHE_ENTRY));
 177
 178   if (RtCacheEntry == NULL) {
 179     return NULL;
 180   }
 181
 182   RtCacheEntry->RefCnt = 1;
 183   RtCacheEntry->Tag    = Tag;
 184
 185   IP6_COPY_ADDRESS (&RtCacheEntry->Destination, Dst);
 186   IP6_COPY_ADDRESS (&RtCacheEntry->Source, Src);
 187   IP6_COPY_ADDRESS (&RtCacheEntry->NextHop, GateWay);
 188
 189   return RtCacheEntry;
 190 }
 191
 192 /**
 193   Free the route cache entry. It is reference counted.
 194
 195   @param[in, out]  RtCacheEntry  The route cache entry to free.
 196
 197 **/
 198 VOID
 199 Ip6FreeRouteCacheEntry (
 200   IN OUT IP6_ROUTE_CACHE_ENTRY  *RtCacheEntry
 201   )
 202 {
 203   ASSERT (RtCacheEntry->RefCnt > 0);
 204
 205   if (--RtCacheEntry->RefCnt == 0) {
 206     FreePool (RtCacheEntry);
 207   }
 208 }
 209
 210 /**
 211   Find a route cache with the destination and source address. This is
 212   used by the ICMPv6 redirect message process.
 213
 214   @param[in]  RtTable       The route table to search the cache for.
 215   @param[in]  Dest          The destination address.
 216   @param[in]  Src           The source address.
 217
 218   @return NULL if no route entry to the (Dest, Src). Otherwise, the pointer
 219           to the correct route cache entry.
 220
 221 **/
 222 IP6_ROUTE_CACHE_ENTRY *
 223 Ip6FindRouteCache (
 224   IN IP6_ROUTE_TABLE   *RtTable,
 225   IN EFI_IPv6_ADDRESS  *Dest,
 226   IN EFI_IPv6_ADDRESS  *Src
 227   )
 228 {
 229   LIST_ENTRY             *Entry;
 230   IP6_ROUTE_CACHE_ENTRY  *RtCacheEntry;
 231   UINT32                 Index;
 232
 233   Index = IP6_ROUTE_CACHE_HASH (Dest, Src);
 234
 235   NET_LIST_FOR_EACH (Entry, &RtTable->Cache.CacheBucket[Index]) {
 236     RtCacheEntry = NET_LIST_USER_STRUCT (Entry, IP6_ROUTE_CACHE_ENTRY, Link);
 237
 238     if (EFI_IP6_EQUAL (Dest, &RtCacheEntry->Destination) && EFI_IP6_EQUAL (Src, &RtCacheEntry->Source)) {
 239       NET_GET_REF (RtCacheEntry);
 240       return RtCacheEntry;
 241     }
 242   }
 243
 244   return NULL;
 245 }
 246
 247 /**
 248   Build an array of EFI_IP6_ROUTE_TABLE to be returned to the caller. The number
 249   of EFI_IP6_ROUTE_TABLE is also returned.
 250
 251   @param[in]  RouteTable        The pointer of IP6_ROUTE_TABLE internal used.
 252   @param[out] EfiRouteCount     The number of returned route entries.
 253   @param[out] EfiRouteTable     The pointer to the array of EFI_IP6_ROUTE_TABLE.
 254                                 If NULL, only the route entry count is returned.
 255
 256   @retval EFI_SUCCESS           The EFI_IP6_ROUTE_TABLE successfully built.
 257   @retval EFI_OUT_OF_RESOURCES  Failed to allocate the memory for the route table.
 258
 259 **/
 260 EFI_STATUS
 261 Ip6BuildEfiRouteTable (
 262   IN IP6_ROUTE_TABLE       *RouteTable,
 263   OUT UINT32               *EfiRouteCount,
 264   OUT EFI_IP6_ROUTE_TABLE  **EfiRouteTable OPTIONAL
 265   )
 266 {
 267   LIST_ENTRY           *Entry;
 268   IP6_ROUTE_ENTRY      *RtEntry;
 269   EFI_IP6_ROUTE_TABLE  *EfiTable;
 270   UINT32               Count;
 271   INT32                Index;
 272
 273   ASSERT (EfiRouteCount != NULL);
 274
 275   Count          = RouteTable->TotalNum;
 276   *EfiRouteCount = Count;
 277
 278   if ((EfiRouteTable == NULL) || (Count == 0)) {
 279     return EFI_SUCCESS;
 280   }
 281
 282   if (*EfiRouteTable == NULL) {
 283     *EfiRouteTable = AllocatePool (sizeof (EFI_IP6_ROUTE_TABLE) * Count);
 284     if (*EfiRouteTable == NULL) {
 285       return EFI_OUT_OF_RESOURCES;
 286     }
 287   }
 288
 289   EfiTable = *EfiRouteTable;
 290
 291   //
 292   // Copy the route entry to EFI route table.
 293   //
 294   Count = 0;
 295
 296   for (Index = IP6_PREFIX_MAX; Index >= 0; Index--) {
 297     NET_LIST_FOR_EACH (Entry, &(RouteTable->RouteArea[Index])) {
 298       RtEntry = NET_LIST_USER_STRUCT (Entry, IP6_ROUTE_ENTRY, Link);
 299
 300       Ip6CopyAddressByPrefix (
 301         &EfiTable[Count].Destination,
 302         &RtEntry->Destination,
 303         RtEntry->PrefixLength
 304         );
 305
 306       IP6_COPY_ADDRESS (&EfiTable[Count].Gateway, &RtEntry->NextHop);
 307       EfiTable[Count].PrefixLength = RtEntry->PrefixLength;
 308
 309       Count++;
 310     }
 311   }
 312
 313   ASSERT (Count == RouteTable->TotalNum);
 314
 315   return EFI_SUCCESS;
 316 }
 317
 318 /**
 319   Create an empty route table. This includes its internal route cache.
 320
 321   @return NULL if failed to allocate memory for the route table. Otherwise,
 322           the point to newly created route table.
 323
 324 **/
 325 IP6_ROUTE_TABLE *
 326 Ip6CreateRouteTable (
 327   VOID
 328   )
 329 {
 330   IP6_ROUTE_TABLE  *RtTable;
 331   UINT32           Index;
 332
 333   RtTable = AllocatePool (sizeof (IP6_ROUTE_TABLE));
 334   if (RtTable == NULL) {
 335     return NULL;
 336   }
 337
 338   RtTable->RefCnt   = 1;
 339   RtTable->TotalNum = 0;
 340
 341   for (Index = 0; Index <= IP6_PREFIX_MAX; Index++) {
 342     InitializeListHead (&RtTable->RouteArea[Index]);
 343   }
 344
 345   for (Index = 0; Index < IP6_ROUTE_CACHE_HASH_SIZE; Index++) {
 346     InitializeListHead (&RtTable->Cache.CacheBucket[Index]);
 347     RtTable->Cache.CacheNum[Index] = 0;
 348   }
 349
 350   return RtTable;
 351 }
 352
 353 /**
 354   Free the route table and its associated route cache. Route
 355   table is reference counted.
 356
 357   @param[in, out]  RtTable      The route table to free.
 358
 359 **/
 360 VOID
 361 Ip6CleanRouteTable (
 362   IN OUT IP6_ROUTE_TABLE  *RtTable
 363   )
 364 {
 365   LIST_ENTRY             *Entry;
 366   LIST_ENTRY             *Next;
 367   IP6_ROUTE_ENTRY        *RtEntry;
 368   IP6_ROUTE_CACHE_ENTRY  *RtCacheEntry;
 369   UINT32                 Index;
 370
 371   ASSERT (RtTable->RefCnt > 0);
 372
 373   if (--RtTable->RefCnt > 0) {
 374     return;
 375   }
 376
 377   //
 378   // Free all the route table entry and its route cache.
 379   //
 380   for (Index = 0; Index <= IP6_PREFIX_MAX; Index++) {
 381     NET_LIST_FOR_EACH_SAFE (Entry, Next, &RtTable->RouteArea[Index]) {
 382       RtEntry = NET_LIST_USER_STRUCT (Entry, IP6_ROUTE_ENTRY, Link);
 383       RemoveEntryList (Entry);
 384       Ip6FreeRouteEntry (RtEntry);
 385     }
 386   }
 387
 388   for (Index = 0; Index < IP6_ROUTE_CACHE_HASH_SIZE; Index++) {
 389     NET_LIST_FOR_EACH_SAFE (Entry, Next, &RtTable->Cache.CacheBucket[Index]) {
 390       RtCacheEntry = NET_LIST_USER_STRUCT (Entry, IP6_ROUTE_CACHE_ENTRY, Link);
 391       RemoveEntryList (Entry);
 392       Ip6FreeRouteCacheEntry (RtCacheEntry);
 393     }
 394   }
 395
 396   FreePool (RtTable);
 397 }
 398
 399 /**
 400   Remove all the cache entries bearing the Tag. When a route cache
 401   entry is created, it is tagged with the address of route entry
 402   from which it is spawned. When a route entry is deleted, the cache
 403   entries spawned from it are also deleted.
 404
 405   @param[in]  RtCache       Route cache to remove the entries from.
 406   @param[in]  Tag           The Tag of the entries to remove.
 407
 408 **/
 409 VOID
 410 Ip6PurgeRouteCache (
 411   IN IP6_ROUTE_CACHE  *RtCache,
 412   IN UINTN            Tag
 413   )
 414 {
 415   LIST_ENTRY             *Entry;
 416   LIST_ENTRY             *Next;
 417   IP6_ROUTE_CACHE_ENTRY  *RtCacheEntry;
 418   UINT32                 Index;
 419
 420   for (Index = 0; Index < IP6_ROUTE_CACHE_HASH_SIZE; Index++) {
 421     NET_LIST_FOR_EACH_SAFE (Entry, Next, &RtCache->CacheBucket[Index]) {
 422       RtCacheEntry = NET_LIST_USER_STRUCT (Entry, IP6_ROUTE_CACHE_ENTRY, Link);
 423
 424       if (RtCacheEntry->Tag == Tag) {
 425         RemoveEntryList (Entry);
 426         Ip6FreeRouteCacheEntry (RtCacheEntry);
 427       }
 428     }
 429   }
 430 }
 431
 432 /**
 433   Add a route entry to the route table. It is the help function for EfiIp6Routes.
 434
 435   @param[in, out]  RtTable        Route table to add route to.
 436   @param[in]       Destination    The destination of the network.
 437   @param[in]       PrefixLength   The PrefixLength of the destination.
 438   @param[in]       GatewayAddress The next hop address.
 439
 440   @retval EFI_ACCESS_DENIED     The same route already exists.
 441   @retval EFI_OUT_OF_RESOURCES  Failed to allocate memory for the entry.
 442   @retval EFI_SUCCESS           The route was added successfully.
 443
 444 **/
 445 EFI_STATUS
 446 Ip6AddRoute (
 447   IN OUT IP6_ROUTE_TABLE  *RtTable,
 448   IN EFI_IPv6_ADDRESS     *Destination,
 449   IN UINT8                PrefixLength,
 450   IN EFI_IPv6_ADDRESS     *GatewayAddress
 451   )
 452 {
 453   LIST_ENTRY       *ListHead;
 454   LIST_ENTRY       *Entry;
 455   IP6_ROUTE_ENTRY  *Route;
 456
 457   ListHead = &RtTable->RouteArea[PrefixLength];
 458
 459   //
 460   // First check whether the route exists
 461   //
 462   NET_LIST_FOR_EACH (Entry, ListHead) {
 463     Route = NET_LIST_USER_STRUCT (Entry, IP6_ROUTE_ENTRY, Link);
 464
 465     if (NetIp6IsNetEqual (Destination, &Route->Destination, PrefixLength) &&
 466         EFI_IP6_EQUAL (GatewayAddress, &Route->NextHop))
 467     {
 468       return EFI_ACCESS_DENIED;
 469     }
 470   }
 471
 472   //
 473   // Create a route entry and insert it to the route area.
 474   //
 475   Route = Ip6CreateRouteEntry (Destination, PrefixLength, GatewayAddress);
 476
 477   if (Route == NULL) {
 478     return EFI_OUT_OF_RESOURCES;
 479   }
 480
 481   if (NetIp6IsUnspecifiedAddr (GatewayAddress)) {
 482     Route->Flag = IP6_DIRECT_ROUTE;
 483   }
 484
 485   InsertHeadList (ListHead, &Route->Link);
 486   RtTable->TotalNum++;
 487
 488   return EFI_SUCCESS;
 489 }
 490
 491 /**
 492   Remove a route entry and all the route caches spawn from it.
 493   It is the help function for EfiIp6Routes.
 494
 495   @param[in, out] RtTable           The route table to remove the route from.
 496   @param[in]      Destination       The destination network.
 497   @param[in]      PrefixLength      The PrefixLength of the Destination.
 498   @param[in]      GatewayAddress    The next hop address.
 499
 500   @retval EFI_SUCCESS           The route entry was successfully removed.
 501   @retval EFI_NOT_FOUND         There is no route entry in the table with that
 502                                 property.
 503
 504 **/
 505 EFI_STATUS
 506 Ip6DelRoute (
 507   IN OUT IP6_ROUTE_TABLE  *RtTable,
 508   IN EFI_IPv6_ADDRESS     *Destination,
 509   IN UINT8                PrefixLength,
 510   IN EFI_IPv6_ADDRESS     *GatewayAddress
 511   )
 512 {
 513   LIST_ENTRY       *ListHead;
 514   LIST_ENTRY       *Entry;
 515   LIST_ENTRY       *Next;
 516   IP6_ROUTE_ENTRY  *Route;
 517   UINT32           TotalNum;
 518
 519   ListHead = &RtTable->RouteArea[PrefixLength];
 520   TotalNum = RtTable->TotalNum;
 521
 522   NET_LIST_FOR_EACH_SAFE (Entry, Next, ListHead) {
 523     Route = NET_LIST_USER_STRUCT (Entry, IP6_ROUTE_ENTRY, Link);
 524
 525     if ((Destination != NULL) && !NetIp6IsNetEqual (Destination, &Route->Destination, PrefixLength)) {
 526       continue;
 527     }
 528
 529     if ((GatewayAddress != NULL) && !EFI_IP6_EQUAL (GatewayAddress, &Route->NextHop)) {
 530       continue;
 531     }
 532
 533     Ip6PurgeRouteCache (&RtTable->Cache, (UINTN)Route);
 534     RemoveEntryList (Entry);
 535     Ip6FreeRouteEntry (Route);
 536
 537     ASSERT (RtTable->TotalNum > 0);
 538     RtTable->TotalNum--;
 539   }
 540
 541   return TotalNum == RtTable->TotalNum ? EFI_NOT_FOUND : EFI_SUCCESS;
 542 }
 543
 544 /**
 545   Search the route table to route the packet. Return/create a route
 546   cache if there is a route to the destination.
 547
 548   @param[in]  IpSb          The IP6 service data.
 549   @param[in]  Dest          The destination address to search for.
 550   @param[in]  Src           The source address to search for.
 551
 552   @return NULL if it failed to route the packet. Otherwise, a route cache
 553           entry that can be used to route packets.
 554
 555 **/
 556 IP6_ROUTE_CACHE_ENTRY *
 557 Ip6Route (
 558   IN IP6_SERVICE       *IpSb,
 559   IN EFI_IPv6_ADDRESS  *Dest,
 560   IN EFI_IPv6_ADDRESS  *Src
 561   )
 562 {
 563   IP6_ROUTE_TABLE        *RtTable;
 564   LIST_ENTRY             *ListHead;
 565   IP6_ROUTE_CACHE_ENTRY  *RtCacheEntry;
 566   IP6_ROUTE_ENTRY        *RtEntry;
 567   EFI_IPv6_ADDRESS       NextHop;
 568   UINT32                 Index;
 569
 570   RtTable = IpSb->RouteTable;
 571
 572   ASSERT (RtTable != NULL);
 573
 574   //
 575   // Search the destination cache in IP6_ROUTE_TABLE.
 576   //
 577   Index    = IP6_ROUTE_CACHE_HASH (Dest, Src);
 578   ListHead = &RtTable->Cache.CacheBucket[Index];
 579
 580   RtCacheEntry = Ip6FindRouteCache (RtTable, Dest, Src);
 581
 582   //
 583   // If found, promote the cache entry to the head of the hash bucket.
 584   //
 585   if (RtCacheEntry != NULL) {
 586     RemoveEntryList (&RtCacheEntry->Link);
 587     InsertHeadList (ListHead, &RtCacheEntry->Link);
 588     return RtCacheEntry;
 589   }
 590
 591   //
 592   // Search the route table for the most specific route
 593   //
 594   RtEntry = Ip6FindRouteEntry (RtTable, Dest, NULL);
 595   if (RtEntry == NULL) {
 596     return NULL;
 597   }
 598
 599   //
 600   // Found a route to the Dest, if it is a direct route, the packet
 601   // will be send directly to the destination, such as for connected
 602   // network. Otherwise, it is an indirect route, the packet will be
 603   // send the next hop router.
 604   //
 605   if ((RtEntry->Flag & IP6_DIRECT_ROUTE) == IP6_DIRECT_ROUTE) {
 606     IP6_COPY_ADDRESS (&NextHop, Dest);
 607   } else {
 608     IP6_COPY_ADDRESS (&NextHop, &RtEntry->NextHop);
 609   }
 610
 611   Ip6FreeRouteEntry (RtEntry);
 612
 613   //
 614   // Create a route cache entry, and tag it as spawned from this route entry
 615   //
 616   RtCacheEntry = Ip6CreateRouteCacheEntry (Dest, Src, &NextHop, (UINTN)RtEntry);
 617
 618   if (RtCacheEntry == NULL) {
 619     return NULL;
 620   }
 621
 622   InsertHeadList (ListHead, &RtCacheEntry->Link);
 623   NET_GET_REF (RtCacheEntry);
 624   RtTable->Cache.CacheNum[Index]++;
 625
 626   return RtCacheEntry;
 627 }