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           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 an 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           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 OUT 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   @return NULL if failed to allocate memory for the route table, otherwise
 203           the point to newly created route table.
 204
 205 **/
 206 IP4_ROUTE_TABLE *
 207 Ip4CreateRouteTable (
 208   VOID
 209   )
 210 {
 211   IP4_ROUTE_TABLE           *RtTable;
 212   UINT32                    Index;
 213
 214   RtTable = AllocatePool (sizeof (IP4_ROUTE_TABLE));
 215
 216   if (RtTable == NULL) {
 217     return NULL;
 218   }
 219
 220   RtTable->RefCnt   = 1;
 221   RtTable->TotalNum = 0;
 222
 223   for (Index = 0; Index < IP4_MASK_NUM; Index++) {
 224     InitializeListHead (&(RtTable->RouteArea[Index]));
 225   }
 226
 227   RtTable->Next = NULL;
 228
 229   Ip4InitRouteCache (&RtTable->Cache);
 230   return RtTable;
 231 }
 232
 233
 234 /**
 235   Free the route table and its associated route cache. Route
 236   table is reference counted.
 237
 238   @param  RtTable               The route table to free.
 239
 240   @return None
 241
 242 **/
 243 VOID
 244 Ip4FreeRouteTable (
 245   IN IP4_ROUTE_TABLE        *RtTable
 246   )
 247 {
 248   LIST_ENTRY                *Entry;
 249   LIST_ENTRY                *Next;
 250   IP4_ROUTE_ENTRY           *RtEntry;
 251   UINT32                    Index;
 252
 253   ASSERT (RtTable->RefCnt > 0);
 254
 255   if (--RtTable->RefCnt > 0) {
 256     return ;
 257   }
 258
 259   //
 260   // Free all the route table entry and its route cache.
 261   //
 262   for (Index = 0; Index < IP4_MASK_NUM; Index++) {
 263     NET_LIST_FOR_EACH_SAFE (Entry, Next, &(RtTable->RouteArea[Index])) {
 264       RtEntry = NET_LIST_USER_STRUCT (Entry, IP4_ROUTE_ENTRY, Link);
 265
 266       RemoveEntryList (Entry);
 267       Ip4FreeRouteEntry (RtEntry);
 268     }
 269   }
 270
 271   Ip4CleanRouteCache (&RtTable->Cache);
 272
 273   gBS->FreePool (RtTable);
 274 }
 275
 276
 277
 278 /**
 279   Remove all the cache entries bearing the Tag. When a route cache
 280   entry is created, it is tagged with the address of route entry
 281   from which it is spawned. When a route entry is deleted, the cache
 282   entries spawned from it are also deleted.
 283
 284   @param  RtCache               Route cache to remove the entries from
 285   @param  Tag                   The Tag of the entries to remove
 286
 287   @return None
 288
 289 **/
 290 VOID
 291 Ip4PurgeRouteCache (
 292   IN OUT IP4_ROUTE_CACHE        *RtCache,
 293   IN     UINTN                  Tag
 294   )
 295 {
 296   LIST_ENTRY                *Entry;
 297   LIST_ENTRY                *Next;
 298   IP4_ROUTE_CACHE_ENTRY     *RtCacheEntry;
 299   UINT32                    Index;
 300
 301   for (Index = 0; Index < IP4_ROUTE_CACHE_HASH; Index++) {
 302     NET_LIST_FOR_EACH_SAFE (Entry, Next, &RtCache->CacheBucket[Index]) {
 303
 304       RtCacheEntry = NET_LIST_USER_STRUCT (Entry, IP4_ROUTE_CACHE_ENTRY, Link);
 305
 306       if (RtCacheEntry->Tag == Tag) {
 307         RemoveEntryList (Entry);
 308         Ip4FreeRouteCacheEntry (RtCacheEntry);
 309       }
 310     }
 311   }
 312 }
 313
 314
 315 /**
 316   Add a route entry to the route table. All the IP4_ADDRs are in
 317   host byte order.
 318
 319   @param  RtTable               Route table to add route to
 320   @param  Dest                  The destination of the network
 321   @param  Netmask               The netmask of the destination
 322   @param  Gateway               The next hop address
 323
 324   @retval EFI_ACCESS_DENIED     The same route already exists
 325   @retval EFI_OUT_OF_RESOURCES  Failed to allocate memory for the entry
 326   @retval EFI_SUCCESS           The route is added successfully.
 327
 328 **/
 329 EFI_STATUS
 330 Ip4AddRoute (
 331   IN OUT IP4_ROUTE_TABLE        *RtTable,
 332   IN     IP4_ADDR               Dest,
 333   IN     IP4_ADDR               Netmask,
 334   IN     IP4_ADDR               Gateway
 335   )
 336 {
 337   LIST_ENTRY                *Head;
 338   LIST_ENTRY                *Entry;
 339   IP4_ROUTE_ENTRY           *RtEntry;
 340
 341   //
 342   // All the route entries with the same netmask length are
 343   // linke to the same route area
 344   //
 345   Head = &(RtTable->RouteArea[NetGetMaskLength (Netmask)]);
 346
 347   //
 348   // First check whether the route exists
 349   //
 350   NET_LIST_FOR_EACH (Entry, Head) {
 351     RtEntry = NET_LIST_USER_STRUCT (Entry, IP4_ROUTE_ENTRY, Link);
 352
 353     if (IP4_NET_EQUAL (RtEntry->Dest, Dest, Netmask) && (RtEntry->NextHop == Gateway)) {
 354       return EFI_ACCESS_DENIED;
 355     }
 356   }
 357
 358   //
 359   // Create a route entry and insert it to the route area.
 360   //
 361   RtEntry = Ip4CreateRouteEntry (Dest, Netmask, Gateway);
 362
 363   if (RtEntry == NULL) {
 364     return EFI_OUT_OF_RESOURCES;
 365   }
 366
 367   if (Gateway == IP4_ALLZERO_ADDRESS) {
 368     RtEntry->Flag = IP4_DIRECT_ROUTE;
 369   }
 370
 371   InsertHeadList (Head, &RtEntry->Link);
 372   RtTable->TotalNum++;
 373
 374   return EFI_SUCCESS;
 375 }
 376
 377
 378 /**
 379   Remove a route entry and all the route caches spawn from it.
 380
 381   @param  RtTable               The route table to remove the route from
 382   @param  Dest                  The destination network
 383   @param  Netmask               The netmask of the Dest
 384   @param  Gateway               The next hop address
 385
 386   @retval EFI_SUCCESS           The route entry is successfully removed
 387   @retval EFI_NOT_FOUND         There is no route entry in the table with that
 388                                 properity.
 389
 390 **/
 391 EFI_STATUS
 392 Ip4DelRoute (
 393   IN OUT IP4_ROUTE_TABLE      *RtTable,
 394   IN     IP4_ADDR             Dest,
 395   IN     IP4_ADDR             Netmask,
 396   IN     IP4_ADDR             Gateway
 397   )
 398 {
 399   LIST_ENTRY                *Head;
 400   LIST_ENTRY                *Entry;
 401   LIST_ENTRY                *Next;
 402   IP4_ROUTE_ENTRY           *RtEntry;
 403
 404   Head = &(RtTable->RouteArea[NetGetMaskLength (Netmask)]);
 405
 406   NET_LIST_FOR_EACH_SAFE (Entry, Next, Head) {
 407     RtEntry = NET_LIST_USER_STRUCT (Entry, IP4_ROUTE_ENTRY, Link);
 408
 409     if (IP4_NET_EQUAL (RtEntry->Dest, Dest, Netmask) && (RtEntry->NextHop == Gateway)) {
 410       Ip4PurgeRouteCache (&RtTable->Cache, (UINTN) RtEntry);
 411       RemoveEntryList (Entry);
 412       Ip4FreeRouteEntry  (RtEntry);
 413
 414       RtTable->TotalNum--;
 415       return EFI_SUCCESS;
 416     }
 417   }
 418
 419   return EFI_NOT_FOUND;
 420 }
 421
 422
 423 /**
 424   Find a route cache with the dst and src. This is used by ICMP
 425   redirect messasge process. All kinds of redirect is treated as
 426   host redirect according to RFC1122. So, only route cache entries
 427   are modified according to the ICMP redirect message.
 428
 429   @param  RtTable               The route table to search the cache for
 430   @param  Dest                  The destination address
 431   @param  Src                   The source address
 432
 433   @return NULL if no route entry to the (Dest, Src). Otherwise the point
 434           to the correct route cache entry.
 435
 436 **/
 437 IP4_ROUTE_CACHE_ENTRY *
 438 Ip4FindRouteCache (
 439   IN IP4_ROUTE_TABLE        *RtTable,
 440   IN IP4_ADDR               Dest,
 441   IN IP4_ADDR               Src
 442   )
 443 {
 444   LIST_ENTRY                *Entry;
 445   IP4_ROUTE_CACHE_ENTRY     *RtCacheEntry;
 446   UINT32                    Index;
 447
 448   Index = IP4_ROUTE_CACHE_HASH (Dest, Src);
 449
 450   NET_LIST_FOR_EACH (Entry, &RtTable->Cache.CacheBucket[Index]) {
 451     RtCacheEntry = NET_LIST_USER_STRUCT (Entry, IP4_ROUTE_CACHE_ENTRY, Link);
 452
 453     if ((RtCacheEntry->Dest == Dest) && (RtCacheEntry->Src == Src)) {
 454       NET_GET_REF (RtCacheEntry);
 455       return RtCacheEntry;
 456     }
 457   }
 458
 459   return NULL;
 460 }
 461
 462
 463 /**
 464   Search the route table for a most specific match to the Dst. It searches
 465   from the longest route area (mask length == 32) to the shortest route area
 466   (default routes). In each route area, it will first search the instance's
 467   route table, then the default route table. This is required by the following
 468   requirements:
 469   1. IP search the route table for a most specific match
 470   2. The local route entries have precedence over the default route entry.
 471
 472   @param  RtTable               The route table to search from
 473   @param  Dst                   The destionation address to search
 474
 475   @return NULL if no route matches the Dst, otherwise the point to the
 476   @return most specific route to the Dst.
 477
 478 **/
 479 IP4_ROUTE_ENTRY *
 480 Ip4FindRouteEntry (
 481   IN IP4_ROUTE_TABLE        *RtTable,
 482   IN IP4_ADDR               Dst
 483   )
 484 {
 485   LIST_ENTRY                *Entry;
 486   IP4_ROUTE_ENTRY           *RtEntry;
 487   IP4_ROUTE_TABLE           *Table;
 488   INTN                      Index;
 489
 490   RtEntry = NULL;
 491
 492   for (Index = IP4_MASK_NUM - 1; Index >= 0; Index--) {
 493     for (Table = RtTable; Table != NULL; Table = Table->Next) {
 494       NET_LIST_FOR_EACH (Entry, &Table->RouteArea[Index]) {
 495         RtEntry = NET_LIST_USER_STRUCT (Entry, IP4_ROUTE_ENTRY, Link);
 496
 497         if (IP4_NET_EQUAL (RtEntry->Dest, Dst, RtEntry->Netmask)) {
 498           NET_GET_REF (RtEntry);
 499           return RtEntry;
 500         }
 501       }
 502     }
 503   }
 504
 505
 506   return NULL;
 507 }
 508
 509
 510 /**
 511   Search the route table to route the packet. Return/create a route
 512   cache if there is a route to the destination.
 513
 514   @param  RtTable               The route table to search from
 515   @param  Dest                  The destination address to search for
 516   @param  Src                   The source address to search for
 517
 518   @return NULL if failed to route packet, otherwise a route cache
 519           entry that can be used to route packet.
 520
 521 **/
 522 IP4_ROUTE_CACHE_ENTRY *
 523 Ip4Route (
 524   IN IP4_ROUTE_TABLE        *RtTable,
 525   IN IP4_ADDR               Dest,
 526   IN IP4_ADDR               Src
 527   )
 528 {
 529   LIST_ENTRY                *Head;
 530   LIST_ENTRY                *Entry;
 531   LIST_ENTRY                *Next;
 532   IP4_ROUTE_CACHE_ENTRY     *RtCacheEntry;
 533   IP4_ROUTE_CACHE_ENTRY     *Cache;
 534   IP4_ROUTE_ENTRY           *RtEntry;
 535   IP4_ADDR                  NextHop;
 536   UINT32                    Count;
 537
 538   ASSERT (RtTable != NULL);
 539
 540   Head          = &RtTable->Cache.CacheBucket[IP4_ROUTE_CACHE_HASH (Dest, Src)];
 541   RtCacheEntry  = Ip4FindRouteCache (RtTable, Dest, Src);
 542
 543   //
 544   // If found, promote the cache entry to the head of the hash bucket. LRU
 545   //
 546   if (RtCacheEntry != NULL) {
 547     RemoveEntryList (&RtCacheEntry->Link);
 548     InsertHeadList (Head, &RtCacheEntry->Link);
 549     return RtCacheEntry;
 550   }
 551
 552   //
 553   // Search the route table for the most specific route
 554   //
 555   RtEntry = Ip4FindRouteEntry (RtTable, Dest);
 556
 557   if (RtEntry == NULL) {
 558     return NULL;
 559   }
 560
 561   //
 562   // Found a route to the Dest, if it is a direct route, the packet
 563   // will be sent directly to the destination, such as for connected
 564   // network. Otherwise, it is an indirect route, the packet will be
 565   // sent to the next hop router.
 566   //
 567   if ((RtEntry->Flag & IP4_DIRECT_ROUTE) != 0) {
 568     NextHop = Dest;
 569   } else {
 570     NextHop = RtEntry->NextHop;
 571   }
 572
 573   Ip4FreeRouteEntry (RtEntry);
 574
 575   //
 576   // Create a route cache entry, and tag it as spawned from this route entry
 577   //
 578   RtCacheEntry = Ip4CreateRouteCacheEntry (Dest, Src, NextHop, (UINTN) RtEntry);
 579
 580   if (RtCacheEntry == NULL) {
 581     return NULL;
 582   }
 583
 584   InsertHeadList (Head, &RtCacheEntry->Link);
 585   NET_GET_REF (RtCacheEntry);
 586
 587   //
 588   // Each bucket of route cache can contain at most 64 entries.
 589   // Remove the entries at the tail of the bucket. These entries
 590   // are likely to be used least.
 591   //
 592   Count = 0;
 593   NET_LIST_FOR_EACH_SAFE (Entry, Next, Head) {
 594     if (++Count < IP4_ROUTE_CACHE_MAX) {
 595       continue;
 596     }
 597
 598     Cache = NET_LIST_USER_STRUCT (Entry, IP4_ROUTE_CACHE_ENTRY, Link);
 599
 600     RemoveEntryList (Entry);
 601     Ip4FreeRouteCacheEntry (Cache);
 602   }
 603
 604   return RtCacheEntry;
 605 }
 606
 607
 608 /**
 609   Build a EFI_IP4_ROUTE_TABLE to be returned to the caller of
 610   GetModeData. The EFI_IP4_ROUTE_TABLE is clumsy to use in the
 611   internal operation of the IP4 driver.
 612
 613   @param  IpInstance            The IP4 child that requests the route table.
 614
 615   @retval EFI_SUCCESS           The route table is successfully build
 616   @retval EFI_OUT_OF_RESOURCES  Failed to allocate the memory for the rotue table.
 617
 618 **/
 619 EFI_STATUS
 620 Ip4BuildEfiRouteTable (
 621   IN IP4_PROTOCOL           *IpInstance
 622   )
 623 {
 624   LIST_ENTRY                *Entry;
 625   IP4_ROUTE_TABLE           *RtTable;
 626   IP4_ROUTE_ENTRY           *RtEntry;
 627   EFI_IP4_ROUTE_TABLE       *Table;
 628   UINT32                    Count;
 629   INT32                     Index;
 630
 631   RtTable = IpInstance->RouteTable;
 632
 633   if (IpInstance->EfiRouteTable != NULL) {
 634     gBS->FreePool (IpInstance->EfiRouteTable);
 635
 636     IpInstance->EfiRouteTable = NULL;
 637     IpInstance->EfiRouteCount = 0;
 638   }
 639
 640   Count = RtTable->TotalNum;
 641
 642   if (RtTable->Next != NULL) {
 643     Count += RtTable->Next->TotalNum;
 644   }
 645
 646   if (Count == 0) {
 647     return EFI_SUCCESS;
 648   }
 649
 650   Table = AllocatePool (sizeof (EFI_IP4_ROUTE_TABLE) * Count);
 651
 652   if (Table == NULL) {
 653     return EFI_OUT_OF_RESOURCES;
 654   }
 655
 656   //
 657   // Copy the route entry to EFI route table. Keep the order of
 658   // route entry copied from most specific to default route. That
 659   // is, interlevel the route entry from the instance's route area
 660   // and those from the default route table's route area.
 661   //
 662   Count = 0;
 663
 664   for (Index = IP4_MASK_NUM - 1; Index >= 0; Index--) {
 665     for (RtTable = IpInstance->RouteTable; RtTable != NULL; RtTable = RtTable->Next) {
 666       NET_LIST_FOR_EACH (Entry, &(RtTable->RouteArea[Index])) {
 667         RtEntry = NET_LIST_USER_STRUCT (Entry, IP4_ROUTE_ENTRY, Link);
 668
 669         EFI_IP4 (Table[Count].SubnetAddress)  = HTONL (RtEntry->Dest & RtEntry->Netmask);
 670         EFI_IP4 (Table[Count].SubnetMask)     = HTONL (RtEntry->Netmask);
 671         EFI_IP4 (Table[Count].GatewayAddress) = HTONL (RtEntry->NextHop);
 672
 673         Count++;
 674       }
 675     }
 676   }
 677
 678   IpInstance->EfiRouteTable = Table;
 679   IpInstance->EfiRouteCount = Count;
 680   return EFI_SUCCESS;
 681 }