MdeModulePkg/Universal/Network/Ip4Dxe/Ip4Route.c

   1 /** @file
   2
   3 Copyright (c) 2005 - 2016, Intel Corporation. All rights reserved.<BR>
   4 SPDX-License-Identifier: BSD-2-Clause-Patent
   5
   6 **/
   7
   8 #include "Ip4Impl.h"
   9
  10
  11 /**
  12   Allocate a route entry then initialize it with the Dest/Netmaks
  13   and Gateway.
  14
  15   @param[in]  Dest                  The destination network
  16   @param[in]  Netmask               The destination network mask
  17   @param[in]  GateWay               The nexthop address
  18
  19   @return NULL if failed to allocate memeory, otherwise the newly created
  20           route entry.
  21
  22 **/
  23 IP4_ROUTE_ENTRY *
  24 Ip4CreateRouteEntry (
  25   IN IP4_ADDR               Dest,
  26   IN IP4_ADDR               Netmask,
  27   IN IP4_ADDR               GateWay
  28   )
  29 {
  30   IP4_ROUTE_ENTRY           *RtEntry;
  31
  32   RtEntry = AllocatePool (sizeof (IP4_ROUTE_ENTRY));
  33
  34   if (RtEntry == NULL) {
  35     return NULL;
  36   }
  37
  38   InitializeListHead (&RtEntry->Link);
  39
  40   RtEntry->RefCnt  = 1;
  41   RtEntry->Dest    = Dest;
  42   RtEntry->Netmask = Netmask;
  43   RtEntry->NextHop = GateWay;
  44   RtEntry->Flag    = 0;
  45
  46   return RtEntry;
  47 }
  48
  49
  50 /**
  51   Free the route table entry. It is reference counted.
  52
  53   @param  RtEntry               The route entry to free.
  54
  55 **/
  56 VOID
  57 Ip4FreeRouteEntry (
  58   IN IP4_ROUTE_ENTRY    *RtEntry
  59   )
  60 {
  61   ASSERT (RtEntry->RefCnt > 0);
  62
  63   if (--RtEntry->RefCnt == 0) {
  64     FreePool (RtEntry);
  65   }
  66 }
  67
  68
  69 /**
  70   Allocate and initialize an IP4 route cache entry.
  71
  72   @param[in]  Dst                   The destination address
  73   @param[in]  Src                   The source address
  74   @param[in]  GateWay               The next hop address
  75   @param[in]  Tag                   The tag from the caller. This marks all the cache
  76                                     entries spawned from one route table entry.
  77
  78   @return NULL if failed to allocate memory for the cache, other point
  79           to the created route cache entry.
  80
  81 **/
  82 IP4_ROUTE_CACHE_ENTRY *
  83 Ip4CreateRouteCacheEntry (
  84   IN IP4_ADDR               Dst,
  85   IN IP4_ADDR               Src,
  86   IN IP4_ADDR               GateWay,
  87   IN UINTN                  Tag
  88   )
  89 {
  90   IP4_ROUTE_CACHE_ENTRY     *RtCacheEntry;
  91
  92   RtCacheEntry = AllocatePool (sizeof (IP4_ROUTE_CACHE_ENTRY));
  93
  94   if (RtCacheEntry == NULL) {
  95     return NULL;
  96   }
  97
  98   InitializeListHead (&RtCacheEntry->Link);
  99
 100   RtCacheEntry->RefCnt  = 1;
 101   RtCacheEntry->Dest    = Dst;
 102   RtCacheEntry->Src     = Src;
 103   RtCacheEntry->NextHop = GateWay;
 104   RtCacheEntry->Tag     = Tag;
 105
 106   return RtCacheEntry;
 107 }
 108
 109
 110 /**
 111   Free the route cache entry. It is reference counted.
 112
 113   @param  RtCacheEntry          The route cache entry to free.
 114
 115 **/
 116 VOID
 117 Ip4FreeRouteCacheEntry (
 118   IN IP4_ROUTE_CACHE_ENTRY  *RtCacheEntry
 119   )
 120 {
 121   ASSERT (RtCacheEntry->RefCnt > 0);
 122
 123   if (--RtCacheEntry->RefCnt == 0) {
 124     FreePool (RtCacheEntry);
 125   }
 126 }
 127
 128
 129 /**
 130   Initialize an empty route cache table.
 131
 132   @param[in, out]  RtCache               The rotue cache table to initialize.
 133
 134 **/
 135 VOID
 136 Ip4InitRouteCache (
 137   IN OUT IP4_ROUTE_CACHE        *RtCache
 138   )
 139 {
 140   UINT32                    Index;
 141
 142   for (Index = 0; Index < IP4_ROUTE_CACHE_HASH_VALUE; Index++) {
 143     InitializeListHead (&(RtCache->CacheBucket[Index]));
 144   }
 145 }
 146
 147
 148 /**
 149   Clean up a route cache, that is free all the route cache
 150   entries enqueued in the cache.
 151
 152   @param[in]  RtCache               The route cache table to clean up
 153
 154 **/
 155 VOID
 156 Ip4CleanRouteCache (
 157   IN IP4_ROUTE_CACHE        *RtCache
 158   )
 159 {
 160   LIST_ENTRY                *Entry;
 161   LIST_ENTRY                *Next;
 162   IP4_ROUTE_CACHE_ENTRY     *RtCacheEntry;
 163   UINT32                    Index;
 164
 165   for (Index = 0; Index < IP4_ROUTE_CACHE_HASH_VALUE; Index++) {
 166     NET_LIST_FOR_EACH_SAFE (Entry, Next, &(RtCache->CacheBucket[Index])) {
 167       RtCacheEntry = NET_LIST_USER_STRUCT (Entry, IP4_ROUTE_CACHE_ENTRY, Link);
 168
 169       RemoveEntryList (Entry);
 170       Ip4FreeRouteCacheEntry (RtCacheEntry);
 171     }
 172   }
 173 }
 174
 175
 176
 177 /**
 178   Create an empty route table, includes its internal route cache
 179
 180   @return NULL if failed to allocate memory for the route table, otherwise
 181           the point to newly created route table.
 182
 183 **/
 184 IP4_ROUTE_TABLE *
 185 Ip4CreateRouteTable (
 186   VOID
 187   )
 188 {
 189   IP4_ROUTE_TABLE           *RtTable;
 190   UINT32                    Index;
 191
 192   RtTable = AllocatePool (sizeof (IP4_ROUTE_TABLE));
 193
 194   if (RtTable == NULL) {
 195     return NULL;
 196   }
 197
 198   RtTable->RefCnt   = 1;
 199   RtTable->TotalNum = 0;
 200
 201   for (Index = 0; Index <= IP4_MASK_MAX; Index++) {
 202     InitializeListHead (&(RtTable->RouteArea[Index]));
 203   }
 204
 205   RtTable->Next = NULL;
 206
 207   Ip4InitRouteCache (&RtTable->Cache);
 208   return RtTable;
 209 }
 210
 211
 212 /**
 213   Free the route table and its associated route cache. Route
 214   table is reference counted.
 215
 216   @param[in]  RtTable               The route table to free.
 217
 218 **/
 219 VOID
 220 Ip4FreeRouteTable (
 221   IN IP4_ROUTE_TABLE        *RtTable
 222   )
 223 {
 224   LIST_ENTRY                *Entry;
 225   LIST_ENTRY                *Next;
 226   IP4_ROUTE_ENTRY           *RtEntry;
 227   UINT32                    Index;
 228
 229   ASSERT (RtTable->RefCnt > 0);
 230
 231   if (--RtTable->RefCnt > 0) {
 232     return ;
 233   }
 234
 235   //
 236   // Free all the route table entry and its route cache.
 237   //
 238   for (Index = 0; Index <= IP4_MASK_MAX; Index++) {
 239     NET_LIST_FOR_EACH_SAFE (Entry, Next, &(RtTable->RouteArea[Index])) {
 240       RtEntry = NET_LIST_USER_STRUCT (Entry, IP4_ROUTE_ENTRY, Link);
 241
 242       RemoveEntryList (Entry);
 243       Ip4FreeRouteEntry (RtEntry);
 244     }
 245   }
 246
 247   Ip4CleanRouteCache (&RtTable->Cache);
 248
 249   FreePool (RtTable);
 250 }
 251
 252
 253
 254 /**
 255   Remove all the cache entries bearing the Tag. When a route cache
 256   entry is created, it is tagged with the address of route entry
 257   from which it is spawned. When a route entry is deleted, the cache
 258   entries spawned from it are also deleted.
 259
 260   @param  RtCache               Route cache to remove the entries from
 261   @param  Tag                   The Tag of the entries to remove
 262
 263 **/
 264 VOID
 265 Ip4PurgeRouteCache (
 266   IN OUT IP4_ROUTE_CACHE        *RtCache,
 267   IN     UINTN                  Tag
 268   )
 269 {
 270   LIST_ENTRY                *Entry;
 271   LIST_ENTRY                *Next;
 272   IP4_ROUTE_CACHE_ENTRY     *RtCacheEntry;
 273   UINT32                    Index;
 274
 275   for (Index = 0; Index < IP4_ROUTE_CACHE_HASH_VALUE; Index++) {
 276     NET_LIST_FOR_EACH_SAFE (Entry, Next, &RtCache->CacheBucket[Index]) {
 277
 278       RtCacheEntry = NET_LIST_USER_STRUCT (Entry, IP4_ROUTE_CACHE_ENTRY, Link);
 279
 280       if (RtCacheEntry->Tag == Tag) {
 281         RemoveEntryList (Entry);
 282         Ip4FreeRouteCacheEntry (RtCacheEntry);
 283       }
 284     }
 285   }
 286 }
 287
 288
 289 /**
 290   Add a route entry to the route table. All the IP4_ADDRs are in
 291   host byte order.
 292
 293   @param[in, out]  RtTable      Route table to add route to
 294   @param[in]       Dest         The destination of the network
 295   @param[in]       Netmask      The netmask of the destination
 296   @param[in]       Gateway      The next hop address
 297
 298   @retval EFI_ACCESS_DENIED     The same route already exists
 299   @retval EFI_OUT_OF_RESOURCES  Failed to allocate memory for the entry
 300   @retval EFI_SUCCESS           The route is added successfully.
 301
 302 **/
 303 EFI_STATUS
 304 Ip4AddRoute (
 305   IN OUT IP4_ROUTE_TABLE        *RtTable,
 306   IN     IP4_ADDR               Dest,
 307   IN     IP4_ADDR               Netmask,
 308   IN     IP4_ADDR               Gateway
 309   )
 310 {
 311   LIST_ENTRY                *Head;
 312   LIST_ENTRY                *Entry;
 313   IP4_ROUTE_ENTRY           *RtEntry;
 314
 315   //
 316   // All the route entries with the same netmask length are
 317   // linke to the same route area
 318   //
 319   Head = &(RtTable->RouteArea[NetGetMaskLength (Netmask)]);
 320
 321   //
 322   // First check whether the route exists
 323   //
 324   NET_LIST_FOR_EACH (Entry, Head) {
 325     RtEntry = NET_LIST_USER_STRUCT (Entry, IP4_ROUTE_ENTRY, Link);
 326
 327     if (IP4_NET_EQUAL (RtEntry->Dest, Dest, Netmask) && (RtEntry->NextHop == Gateway)) {
 328       return EFI_ACCESS_DENIED;
 329     }
 330   }
 331
 332   //
 333   // Create a route entry and insert it to the route area.
 334   //
 335   RtEntry = Ip4CreateRouteEntry (Dest, Netmask, Gateway);
 336
 337   if (RtEntry == NULL) {
 338     return EFI_OUT_OF_RESOURCES;
 339   }
 340
 341   if (Gateway == IP4_ALLZERO_ADDRESS) {
 342     RtEntry->Flag = IP4_DIRECT_ROUTE;
 343   }
 344
 345   InsertHeadList (Head, &RtEntry->Link);
 346   RtTable->TotalNum++;
 347
 348   return EFI_SUCCESS;
 349 }
 350
 351
 352 /**
 353   Remove a route entry and all the route caches spawn from it.
 354
 355   @param  RtTable           The route table to remove the route from
 356   @param  Dest              The destination network
 357   @param  Netmask           The netmask of the Dest
 358   @param  Gateway           The next hop address
 359
 360   @retval EFI_SUCCESS           The route entry is successfully removed
 361   @retval EFI_NOT_FOUND         There is no route entry in the table with that
 362                                 properity.
 363
 364 **/
 365 EFI_STATUS
 366 Ip4DelRoute (
 367   IN OUT IP4_ROUTE_TABLE      *RtTable,
 368   IN     IP4_ADDR             Dest,
 369   IN     IP4_ADDR             Netmask,
 370   IN     IP4_ADDR             Gateway
 371   )
 372 {
 373   LIST_ENTRY                *Head;
 374   LIST_ENTRY                *Entry;
 375   LIST_ENTRY                *Next;
 376   IP4_ROUTE_ENTRY           *RtEntry;
 377
 378   Head = &(RtTable->RouteArea[NetGetMaskLength (Netmask)]);
 379
 380   NET_LIST_FOR_EACH_SAFE (Entry, Next, Head) {
 381     RtEntry = NET_LIST_USER_STRUCT (Entry, IP4_ROUTE_ENTRY, Link);
 382
 383     if (IP4_NET_EQUAL (RtEntry->Dest, Dest, Netmask) && (RtEntry->NextHop == Gateway)) {
 384       Ip4PurgeRouteCache (&RtTable->Cache, (UINTN) RtEntry);
 385       RemoveEntryList (Entry);
 386       Ip4FreeRouteEntry  (RtEntry);
 387
 388       RtTable->TotalNum--;
 389       return EFI_SUCCESS;
 390     }
 391   }
 392
 393   return EFI_NOT_FOUND;
 394 }
 395
 396
 397 /**
 398   Find a route cache with the dst and src. This is used by ICMP
 399   redirect messasge process. All kinds of redirect is treated as
 400   host redirect according to RFC1122. So, only route cache entries
 401   are modified according to the ICMP redirect message.
 402
 403   @param[in]  RtTable               The route table to search the cache for
 404   @param[in]  Dest                  The destination address
 405   @param[in]  Src                   The source address
 406
 407   @return NULL if no route entry to the (Dest, Src). Otherwise the point
 408           to the correct route cache entry.
 409
 410 **/
 411 IP4_ROUTE_CACHE_ENTRY *
 412 Ip4FindRouteCache (
 413   IN IP4_ROUTE_TABLE        *RtTable,
 414   IN IP4_ADDR               Dest,
 415   IN IP4_ADDR               Src
 416   )
 417 {
 418   LIST_ENTRY                *Entry;
 419   IP4_ROUTE_CACHE_ENTRY     *RtCacheEntry;
 420   UINT32                    Index;
 421
 422   Index = IP4_ROUTE_CACHE_HASH (Dest, Src);
 423
 424   NET_LIST_FOR_EACH (Entry, &RtTable->Cache.CacheBucket[Index]) {
 425     RtCacheEntry = NET_LIST_USER_STRUCT (Entry, IP4_ROUTE_CACHE_ENTRY, Link);
 426
 427     if ((RtCacheEntry->Dest == Dest) && (RtCacheEntry->Src == Src)) {
 428       NET_GET_REF (RtCacheEntry);
 429       return RtCacheEntry;
 430     }
 431   }
 432
 433   return NULL;
 434 }
 435
 436
 437 /**
 438   Search the route table for a most specific match to the Dst. It searches
 439   from the longest route area (mask length == 32) to the shortest route area
 440   (default routes). In each route area, it will first search the instance's
 441   route table, then the default route table. This is required by the following
 442   requirements:
 443   1. IP search the route table for a most specific match
 444   2. The local route entries have precedence over the default route entry.
 445
 446   @param[in]  RtTable               The route table to search from
 447   @param[in]  Dst                   The destionation address to search
 448
 449   @return NULL if no route matches the Dst, otherwise the point to the
 450           most specific route to the Dst.
 451
 452 **/
 453 IP4_ROUTE_ENTRY *
 454 Ip4FindRouteEntry (
 455   IN IP4_ROUTE_TABLE        *RtTable,
 456   IN IP4_ADDR               Dst
 457   )
 458 {
 459   LIST_ENTRY                *Entry;
 460   IP4_ROUTE_ENTRY           *RtEntry;
 461   IP4_ROUTE_TABLE           *Table;
 462   INTN                      Index;
 463
 464   RtEntry = NULL;
 465
 466   for (Index = IP4_MASK_MAX; Index >= 0; Index--) {
 467     for (Table = RtTable; Table != NULL; Table = Table->Next) {
 468       NET_LIST_FOR_EACH (Entry, &Table->RouteArea[Index]) {
 469         RtEntry = NET_LIST_USER_STRUCT (Entry, IP4_ROUTE_ENTRY, Link);
 470
 471         if (IP4_NET_EQUAL (RtEntry->Dest, Dst, RtEntry->Netmask)) {
 472           NET_GET_REF (RtEntry);
 473           return RtEntry;
 474         }
 475       }
 476     }
 477   }
 478
 479
 480   return NULL;
 481 }
 482
 483
 484 /**
 485   Search the route table to route the packet. Return/create a route
 486   cache if there is a route to the destination.
 487
 488   @param[in]  RtTable               The route table to search from
 489   @param[in]  Dest                  The destination address to search for
 490   @param[in]  Src                   The source address to search for
 491   @param[in]  SubnetMask            The subnet mask of the Src address, this field is
 492                                     used to check if the station is using /32 subnet.
 493   @param[in]  AlwaysTryDestAddr     Always try to use the dest address as next hop even
 494                                     though we can't find a matching route entry. This
 495                                     field is only valid when using /32 subnet.
 496
 497   @return NULL if failed to route packet, otherwise a route cache
 498           entry that can be used to route packet.
 499
 500 **/
 501 IP4_ROUTE_CACHE_ENTRY *
 502 Ip4Route (
 503   IN IP4_ROUTE_TABLE        *RtTable,
 504   IN IP4_ADDR               Dest,
 505   IN IP4_ADDR               Src,
 506   IN IP4_ADDR               SubnetMask,
 507   IN BOOLEAN                AlwaysTryDestAddr
 508   )
 509 {
 510   LIST_ENTRY                *Head;
 511   LIST_ENTRY                *Entry;
 512   LIST_ENTRY                *Next;
 513   IP4_ROUTE_CACHE_ENTRY     *RtCacheEntry;
 514   IP4_ROUTE_CACHE_ENTRY     *Cache;
 515   IP4_ROUTE_ENTRY           *RtEntry;
 516   IP4_ADDR                  NextHop;
 517   UINT32                    Count;
 518
 519   ASSERT (RtTable != NULL);
 520
 521   Head          = &RtTable->Cache.CacheBucket[IP4_ROUTE_CACHE_HASH (Dest, Src)];
 522   RtCacheEntry  = Ip4FindRouteCache (RtTable, Dest, Src);
 523
 524   //
 525   // If found, promote the cache entry to the head of the hash bucket. LRU
 526   //
 527   if (RtCacheEntry != NULL) {
 528     RemoveEntryList (&RtCacheEntry->Link);
 529     InsertHeadList (Head, &RtCacheEntry->Link);
 530     return RtCacheEntry;
 531   }
 532
 533   //
 534   // Search the route table for the most specific route
 535   //
 536   RtEntry = Ip4FindRouteEntry (RtTable, Dest);
 537
 538   if (RtEntry == NULL) {
 539     if (SubnetMask != IP4_ALLONE_ADDRESS) {
 540       return NULL;
 541     } else if (!AlwaysTryDestAddr) {
 542       return NULL;
 543     }
 544   }
 545
 546   //
 547   // Found a route to the Dest, if it is a direct route, the packet
 548   // will be sent directly to the destination, such as for connected
 549   // network. Otherwise, it is an indirect route, the packet will be
 550   // sent to the next hop router.
 551   //
 552   // When using /32 subnet mask, the packet will always be sent to the direct
 553   // destination first, if we can't find a matching route cache.
 554   //
 555   if (SubnetMask == IP4_ALLONE_ADDRESS || ((RtEntry->Flag & IP4_DIRECT_ROUTE) != 0)) {
 556     NextHop = Dest;
 557   } else {
 558     NextHop = RtEntry->NextHop;
 559   }
 560
 561   if (RtEntry != NULL) {
 562     Ip4FreeRouteEntry (RtEntry);
 563   }
 564
 565   //
 566   // Create a route cache entry, and tag it as spawned from this route entry
 567   // For /32 subnet mask, the default route in RtEntry will be used if failed
 568   // to send the packet to driect destination address.
 569   //
 570   RtCacheEntry = Ip4CreateRouteCacheEntry (Dest, Src, NextHop, (UINTN) RtEntry);
 571
 572   if (RtCacheEntry == NULL) {
 573     return NULL;
 574   }
 575
 576   InsertHeadList (Head, &RtCacheEntry->Link);
 577   NET_GET_REF (RtCacheEntry);
 578
 579   //
 580   // Each bucket of route cache can contain at most 64 entries.
 581   // Remove the entries at the tail of the bucket. These entries
 582   // are likely to be used least.
 583   //
 584   Count = 0;
 585   NET_LIST_FOR_EACH_SAFE (Entry, Next, Head) {
 586     if (++Count < IP4_ROUTE_CACHE_MAX) {
 587       continue;
 588     }
 589
 590     Cache = NET_LIST_USER_STRUCT (Entry, IP4_ROUTE_CACHE_ENTRY, Link);
 591
 592     RemoveEntryList (Entry);
 593     Ip4FreeRouteCacheEntry (Cache);
 594   }
 595
 596   return RtCacheEntry;
 597 }
 598
 599
 600 /**
 601   Build a EFI_IP4_ROUTE_TABLE to be returned to the caller of
 602   GetModeData. The EFI_IP4_ROUTE_TABLE is clumsy to use in the
 603   internal operation of the IP4 driver.
 604
 605   @param[in]  IpInstance        The IP4 child that requests the route table.
 606
 607   @retval EFI_SUCCESS           The route table is successfully build
 608   @retval EFI_OUT_OF_RESOURCES  Failed to allocate the memory for the rotue table.
 609
 610 **/
 611 EFI_STATUS
 612 Ip4BuildEfiRouteTable (
 613   IN IP4_PROTOCOL           *IpInstance
 614   )
 615 {
 616   LIST_ENTRY                *Entry;
 617   IP4_ROUTE_TABLE           *RtTable;
 618   IP4_ROUTE_ENTRY           *RtEntry;
 619   EFI_IP4_ROUTE_TABLE       *Table;
 620   UINT32                    Count;
 621   INT32                     Index;
 622
 623   RtTable = IpInstance->RouteTable;
 624
 625   if (IpInstance->EfiRouteTable != NULL) {
 626     FreePool (IpInstance->EfiRouteTable);
 627
 628     IpInstance->EfiRouteTable = NULL;
 629     IpInstance->EfiRouteCount = 0;
 630   }
 631
 632   Count = RtTable->TotalNum;
 633
 634   if (RtTable->Next != NULL) {
 635     Count += RtTable->Next->TotalNum;
 636   }
 637
 638   if (Count == 0) {
 639     return EFI_SUCCESS;
 640   }
 641
 642   Table = AllocatePool (sizeof (EFI_IP4_ROUTE_TABLE) * Count);
 643
 644   if (Table == NULL) {
 645     return EFI_OUT_OF_RESOURCES;
 646   }
 647
 648   //
 649   // Copy the route entry to EFI route table. Keep the order of
 650   // route entry copied from most specific to default route. That
 651   // is, interlevel the route entry from the instance's route area
 652   // and those from the default route table's route area.
 653   //
 654   Count = 0;
 655
 656   for (Index = IP4_MASK_MAX; Index >= 0; Index--) {
 657     for (RtTable = IpInstance->RouteTable; RtTable != NULL; RtTable = RtTable->Next) {
 658       NET_LIST_FOR_EACH (Entry, &(RtTable->RouteArea[Index])) {
 659         RtEntry = NET_LIST_USER_STRUCT (Entry, IP4_ROUTE_ENTRY, Link);
 660
 661         EFI_IP4 (Table[Count].SubnetAddress)  = HTONL (RtEntry->Dest & RtEntry->Netmask);
 662         EFI_IP4 (Table[Count].SubnetMask)     = HTONL (RtEntry->Netmask);
 663         EFI_IP4 (Table[Count].GatewayAddress) = HTONL (RtEntry->NextHop);
 664
 665         Count++;
 666       }
 667     }
 668   }
 669
 670   IpInstance->EfiRouteTable = Table;
 671   IpInstance->EfiRouteCount = Count;
 672   return EFI_SUCCESS;
 673 }