MdeModulePkg/Universal/Network/Ip4Dxe/Ip4Route.c

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