3 Copyright (c) 2005 - 2016, Intel Corporation. All rights reserved.<BR>
4 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
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.
18 Allocate a route entry then initialize it with the Dest/Netmaks
21 @param[in] Dest The destination network
22 @param[in] Netmask The destination network mask
23 @param[in] GateWay The nexthop address
25 @return NULL if failed to allocate memeory, otherwise the newly created
36 IP4_ROUTE_ENTRY
*RtEntry
;
38 RtEntry
= AllocatePool (sizeof (IP4_ROUTE_ENTRY
));
40 if (RtEntry
== NULL
) {
44 InitializeListHead (&RtEntry
->Link
);
48 RtEntry
->Netmask
= Netmask
;
49 RtEntry
->NextHop
= GateWay
;
57 Free the route table entry. It is reference counted.
59 @param RtEntry The route entry to free.
64 IN IP4_ROUTE_ENTRY
*RtEntry
67 ASSERT (RtEntry
->RefCnt
> 0);
69 if (--RtEntry
->RefCnt
== 0) {
76 Allocate and initialize an IP4 route cache entry.
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.
84 @return NULL if failed to allocate memory for the cache, other point
85 to the created route cache entry.
88 IP4_ROUTE_CACHE_ENTRY
*
89 Ip4CreateRouteCacheEntry (
96 IP4_ROUTE_CACHE_ENTRY
*RtCacheEntry
;
98 RtCacheEntry
= AllocatePool (sizeof (IP4_ROUTE_CACHE_ENTRY
));
100 if (RtCacheEntry
== NULL
) {
104 InitializeListHead (&RtCacheEntry
->Link
);
106 RtCacheEntry
->RefCnt
= 1;
107 RtCacheEntry
->Dest
= Dst
;
108 RtCacheEntry
->Src
= Src
;
109 RtCacheEntry
->NextHop
= GateWay
;
110 RtCacheEntry
->Tag
= Tag
;
117 Free the route cache entry. It is reference counted.
119 @param RtCacheEntry The route cache entry to free.
123 Ip4FreeRouteCacheEntry (
124 IN IP4_ROUTE_CACHE_ENTRY
*RtCacheEntry
127 ASSERT (RtCacheEntry
->RefCnt
> 0);
129 if (--RtCacheEntry
->RefCnt
== 0) {
130 FreePool (RtCacheEntry
);
136 Initialize an empty route cache table.
138 @param[in, out] RtCache The rotue cache table to initialize.
143 IN OUT IP4_ROUTE_CACHE
*RtCache
148 for (Index
= 0; Index
< IP4_ROUTE_CACHE_HASH_VALUE
; Index
++) {
149 InitializeListHead (&(RtCache
->CacheBucket
[Index
]));
155 Clean up a route cache, that is free all the route cache
156 entries enqueued in the cache.
158 @param[in] RtCache The route cache table to clean up
163 IN IP4_ROUTE_CACHE
*RtCache
168 IP4_ROUTE_CACHE_ENTRY
*RtCacheEntry
;
171 for (Index
= 0; Index
< IP4_ROUTE_CACHE_HASH_VALUE
; Index
++) {
172 NET_LIST_FOR_EACH_SAFE (Entry
, Next
, &(RtCache
->CacheBucket
[Index
])) {
173 RtCacheEntry
= NET_LIST_USER_STRUCT (Entry
, IP4_ROUTE_CACHE_ENTRY
, Link
);
175 RemoveEntryList (Entry
);
176 Ip4FreeRouteCacheEntry (RtCacheEntry
);
184 Create an empty route table, includes its internal route cache
186 @return NULL if failed to allocate memory for the route table, otherwise
187 the point to newly created route table.
191 Ip4CreateRouteTable (
195 IP4_ROUTE_TABLE
*RtTable
;
198 RtTable
= AllocatePool (sizeof (IP4_ROUTE_TABLE
));
200 if (RtTable
== NULL
) {
205 RtTable
->TotalNum
= 0;
207 for (Index
= 0; Index
<= IP4_MASK_MAX
; Index
++) {
208 InitializeListHead (&(RtTable
->RouteArea
[Index
]));
211 RtTable
->Next
= NULL
;
213 Ip4InitRouteCache (&RtTable
->Cache
);
219 Free the route table and its associated route cache. Route
220 table is reference counted.
222 @param[in] RtTable The route table to free.
227 IN IP4_ROUTE_TABLE
*RtTable
232 IP4_ROUTE_ENTRY
*RtEntry
;
235 ASSERT (RtTable
->RefCnt
> 0);
237 if (--RtTable
->RefCnt
> 0) {
242 // Free all the route table entry and its route cache.
244 for (Index
= 0; Index
<= IP4_MASK_MAX
; Index
++) {
245 NET_LIST_FOR_EACH_SAFE (Entry
, Next
, &(RtTable
->RouteArea
[Index
])) {
246 RtEntry
= NET_LIST_USER_STRUCT (Entry
, IP4_ROUTE_ENTRY
, Link
);
248 RemoveEntryList (Entry
);
249 Ip4FreeRouteEntry (RtEntry
);
253 Ip4CleanRouteCache (&RtTable
->Cache
);
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.
266 @param RtCache Route cache to remove the entries from
267 @param Tag The Tag of the entries to remove
272 IN OUT IP4_ROUTE_CACHE
*RtCache
,
278 IP4_ROUTE_CACHE_ENTRY
*RtCacheEntry
;
281 for (Index
= 0; Index
< IP4_ROUTE_CACHE_HASH_VALUE
; Index
++) {
282 NET_LIST_FOR_EACH_SAFE (Entry
, Next
, &RtCache
->CacheBucket
[Index
]) {
284 RtCacheEntry
= NET_LIST_USER_STRUCT (Entry
, IP4_ROUTE_CACHE_ENTRY
, Link
);
286 if (RtCacheEntry
->Tag
== Tag
) {
287 RemoveEntryList (Entry
);
288 Ip4FreeRouteCacheEntry (RtCacheEntry
);
296 Add a route entry to the route table. All the IP4_ADDRs are in
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
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.
311 IN OUT IP4_ROUTE_TABLE
*RtTable
,
319 IP4_ROUTE_ENTRY
*RtEntry
;
322 // All the route entries with the same netmask length are
323 // linke to the same route area
325 Head
= &(RtTable
->RouteArea
[NetGetMaskLength (Netmask
)]);
328 // First check whether the route exists
330 NET_LIST_FOR_EACH (Entry
, Head
) {
331 RtEntry
= NET_LIST_USER_STRUCT (Entry
, IP4_ROUTE_ENTRY
, Link
);
333 if (IP4_NET_EQUAL (RtEntry
->Dest
, Dest
, Netmask
) && (RtEntry
->NextHop
== Gateway
)) {
334 return EFI_ACCESS_DENIED
;
339 // Create a route entry and insert it to the route area.
341 RtEntry
= Ip4CreateRouteEntry (Dest
, Netmask
, Gateway
);
343 if (RtEntry
== NULL
) {
344 return EFI_OUT_OF_RESOURCES
;
347 if (Gateway
== IP4_ALLZERO_ADDRESS
) {
348 RtEntry
->Flag
= IP4_DIRECT_ROUTE
;
351 InsertHeadList (Head
, &RtEntry
->Link
);
359 Remove a route entry and all the route caches spawn from it.
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
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
373 IN OUT IP4_ROUTE_TABLE
*RtTable
,
382 IP4_ROUTE_ENTRY
*RtEntry
;
384 Head
= &(RtTable
->RouteArea
[NetGetMaskLength (Netmask
)]);
386 NET_LIST_FOR_EACH_SAFE (Entry
, Next
, Head
) {
387 RtEntry
= NET_LIST_USER_STRUCT (Entry
, IP4_ROUTE_ENTRY
, Link
);
389 if (IP4_NET_EQUAL (RtEntry
->Dest
, Dest
, Netmask
) && (RtEntry
->NextHop
== Gateway
)) {
390 Ip4PurgeRouteCache (&RtTable
->Cache
, (UINTN
) RtEntry
);
391 RemoveEntryList (Entry
);
392 Ip4FreeRouteEntry (RtEntry
);
399 return EFI_NOT_FOUND
;
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.
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
413 @return NULL if no route entry to the (Dest, Src). Otherwise the point
414 to the correct route cache entry.
417 IP4_ROUTE_CACHE_ENTRY
*
419 IN IP4_ROUTE_TABLE
*RtTable
,
425 IP4_ROUTE_CACHE_ENTRY
*RtCacheEntry
;
428 Index
= IP4_ROUTE_CACHE_HASH (Dest
, Src
);
430 NET_LIST_FOR_EACH (Entry
, &RtTable
->Cache
.CacheBucket
[Index
]) {
431 RtCacheEntry
= NET_LIST_USER_STRUCT (Entry
, IP4_ROUTE_CACHE_ENTRY
, Link
);
433 if ((RtCacheEntry
->Dest
== Dest
) && (RtCacheEntry
->Src
== Src
)) {
434 NET_GET_REF (RtCacheEntry
);
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
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.
452 @param[in] RtTable The route table to search from
453 @param[in] Dst The destionation address to search
455 @return NULL if no route matches the Dst, otherwise the point to the
456 most specific route to the Dst.
461 IN IP4_ROUTE_TABLE
*RtTable
,
466 IP4_ROUTE_ENTRY
*RtEntry
;
467 IP4_ROUTE_TABLE
*Table
;
472 for (Index
= IP4_MASK_MAX
; 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
);
477 if (IP4_NET_EQUAL (RtEntry
->Dest
, Dst
, RtEntry
->Netmask
)) {
478 NET_GET_REF (RtEntry
);
491 Search the route table to route the packet. Return/create a route
492 cache if there is a route to the destination.
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 @param[in] SubnetMask The subnet mask of the Src address, this field is
498 used to check if the station is using /32 subnet.
499 @param[in] AlwaysTryDestAddr Always try to use the dest address as next hop even
500 though we can't find a matching route entry. This
501 field is only valid when using /32 subnet.
503 @return NULL if failed to route packet, otherwise a route cache
504 entry that can be used to route packet.
507 IP4_ROUTE_CACHE_ENTRY
*
509 IN IP4_ROUTE_TABLE
*RtTable
,
512 IN IP4_ADDR SubnetMask
,
513 IN BOOLEAN AlwaysTryDestAddr
519 IP4_ROUTE_CACHE_ENTRY
*RtCacheEntry
;
520 IP4_ROUTE_CACHE_ENTRY
*Cache
;
521 IP4_ROUTE_ENTRY
*RtEntry
;
525 ASSERT (RtTable
!= NULL
);
527 Head
= &RtTable
->Cache
.CacheBucket
[IP4_ROUTE_CACHE_HASH (Dest
, Src
)];
528 RtCacheEntry
= Ip4FindRouteCache (RtTable
, Dest
, Src
);
531 // If found, promote the cache entry to the head of the hash bucket. LRU
533 if (RtCacheEntry
!= NULL
) {
534 RemoveEntryList (&RtCacheEntry
->Link
);
535 InsertHeadList (Head
, &RtCacheEntry
->Link
);
540 // Search the route table for the most specific route
542 RtEntry
= Ip4FindRouteEntry (RtTable
, Dest
);
544 if (RtEntry
== NULL
) {
545 if (SubnetMask
!= IP4_ALLONE_ADDRESS
) {
547 } else if (!AlwaysTryDestAddr
) {
553 // Found a route to the Dest, if it is a direct route, the packet
554 // will be sent directly to the destination, such as for connected
555 // network. Otherwise, it is an indirect route, the packet will be
556 // sent to the next hop router.
558 // When using /32 subnet mask, the packet will always be sent to the direct
559 // destination first, if we can't find a matching route cache.
561 if (SubnetMask
== IP4_ALLONE_ADDRESS
|| ((RtEntry
->Flag
& IP4_DIRECT_ROUTE
) != 0)) {
564 NextHop
= RtEntry
->NextHop
;
567 if (RtEntry
!= NULL
) {
568 Ip4FreeRouteEntry (RtEntry
);
572 // Create a route cache entry, and tag it as spawned from this route entry
573 // For /32 subnet mask, the default route in RtEntry will be used if failed
574 // to send the packet to driect destination address.
576 RtCacheEntry
= Ip4CreateRouteCacheEntry (Dest
, Src
, NextHop
, (UINTN
) RtEntry
);
578 if (RtCacheEntry
== NULL
) {
582 InsertHeadList (Head
, &RtCacheEntry
->Link
);
583 NET_GET_REF (RtCacheEntry
);
586 // Each bucket of route cache can contain at most 64 entries.
587 // Remove the entries at the tail of the bucket. These entries
588 // are likely to be used least.
591 NET_LIST_FOR_EACH_SAFE (Entry
, Next
, Head
) {
592 if (++Count
< IP4_ROUTE_CACHE_MAX
) {
596 Cache
= NET_LIST_USER_STRUCT (Entry
, IP4_ROUTE_CACHE_ENTRY
, Link
);
598 RemoveEntryList (Entry
);
599 Ip4FreeRouteCacheEntry (Cache
);
607 Build a EFI_IP4_ROUTE_TABLE to be returned to the caller of
608 GetModeData. The EFI_IP4_ROUTE_TABLE is clumsy to use in the
609 internal operation of the IP4 driver.
611 @param[in] IpInstance The IP4 child that requests the route table.
613 @retval EFI_SUCCESS The route table is successfully build
614 @retval EFI_OUT_OF_RESOURCES Failed to allocate the memory for the rotue table.
618 Ip4BuildEfiRouteTable (
619 IN IP4_PROTOCOL
*IpInstance
623 IP4_ROUTE_TABLE
*RtTable
;
624 IP4_ROUTE_ENTRY
*RtEntry
;
625 EFI_IP4_ROUTE_TABLE
*Table
;
629 RtTable
= IpInstance
->RouteTable
;
631 if (IpInstance
->EfiRouteTable
!= NULL
) {
632 FreePool (IpInstance
->EfiRouteTable
);
634 IpInstance
->EfiRouteTable
= NULL
;
635 IpInstance
->EfiRouteCount
= 0;
638 Count
= RtTable
->TotalNum
;
640 if (RtTable
->Next
!= NULL
) {
641 Count
+= RtTable
->Next
->TotalNum
;
648 Table
= AllocatePool (sizeof (EFI_IP4_ROUTE_TABLE
) * Count
);
651 return EFI_OUT_OF_RESOURCES
;
655 // Copy the route entry to EFI route table. Keep the order of
656 // route entry copied from most specific to default route. That
657 // is, interlevel the route entry from the instance's route area
658 // and those from the default route table's route area.
662 for (Index
= IP4_MASK_MAX
; Index
>= 0; Index
--) {
663 for (RtTable
= IpInstance
->RouteTable
; RtTable
!= NULL
; RtTable
= RtTable
->Next
) {
664 NET_LIST_FOR_EACH (Entry
, &(RtTable
->RouteArea
[Index
])) {
665 RtEntry
= NET_LIST_USER_STRUCT (Entry
, IP4_ROUTE_ENTRY
, Link
);
667 EFI_IP4 (Table
[Count
].SubnetAddress
) = HTONL (RtEntry
->Dest
& RtEntry
->Netmask
);
668 EFI_IP4 (Table
[Count
].SubnetMask
) = HTONL (RtEntry
->Netmask
);
669 EFI_IP4 (Table
[Count
].GatewayAddress
) = HTONL (RtEntry
->NextHop
);
676 IpInstance
->EfiRouteTable
= Table
;
677 IpInstance
->EfiRouteCount
= Count
;