MdeModulePkg/Universal/Network/Ip4Dxe/Ip4Route.c

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