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