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