3 Copyright (c) 2005 - 2016, Intel Corporation. All rights reserved.<BR>
4 SPDX-License-Identifier: BSD-2-Clause-Patent
12 Allocate a route entry then initialize it with the Dest/Netmaks
15 @param[in] Dest The destination network
16 @param[in] Netmask The destination network mask
17 @param[in] GateWay The nexthop address
19 @return NULL if failed to allocate memeory, otherwise the newly created
30 IP4_ROUTE_ENTRY
*RtEntry
;
32 RtEntry
= AllocatePool (sizeof (IP4_ROUTE_ENTRY
));
34 if (RtEntry
== NULL
) {
38 InitializeListHead (&RtEntry
->Link
);
42 RtEntry
->Netmask
= Netmask
;
43 RtEntry
->NextHop
= GateWay
;
51 Free the route table entry. It is reference counted.
53 @param RtEntry The route entry to free.
58 IN IP4_ROUTE_ENTRY
*RtEntry
61 ASSERT (RtEntry
->RefCnt
> 0);
63 if (--RtEntry
->RefCnt
== 0) {
70 Allocate and initialize an IP4 route cache entry.
72 @param[in] Dst The destination address
73 @param[in] Src The source address
74 @param[in] GateWay The next hop address
75 @param[in] Tag The tag from the caller. This marks all the cache
76 entries spawned from one route table entry.
78 @return NULL if failed to allocate memory for the cache, other point
79 to the created route cache entry.
82 IP4_ROUTE_CACHE_ENTRY
*
83 Ip4CreateRouteCacheEntry (
90 IP4_ROUTE_CACHE_ENTRY
*RtCacheEntry
;
92 RtCacheEntry
= AllocatePool (sizeof (IP4_ROUTE_CACHE_ENTRY
));
94 if (RtCacheEntry
== NULL
) {
98 InitializeListHead (&RtCacheEntry
->Link
);
100 RtCacheEntry
->RefCnt
= 1;
101 RtCacheEntry
->Dest
= Dst
;
102 RtCacheEntry
->Src
= Src
;
103 RtCacheEntry
->NextHop
= GateWay
;
104 RtCacheEntry
->Tag
= Tag
;
111 Free the route cache entry. It is reference counted.
113 @param RtCacheEntry The route cache entry to free.
117 Ip4FreeRouteCacheEntry (
118 IN IP4_ROUTE_CACHE_ENTRY
*RtCacheEntry
121 ASSERT (RtCacheEntry
->RefCnt
> 0);
123 if (--RtCacheEntry
->RefCnt
== 0) {
124 FreePool (RtCacheEntry
);
130 Initialize an empty route cache table.
132 @param[in, out] RtCache The rotue cache table to initialize.
137 IN OUT IP4_ROUTE_CACHE
*RtCache
142 for (Index
= 0; Index
< IP4_ROUTE_CACHE_HASH_VALUE
; Index
++) {
143 InitializeListHead (&(RtCache
->CacheBucket
[Index
]));
149 Clean up a route cache, that is free all the route cache
150 entries enqueued in the cache.
152 @param[in] RtCache The route cache table to clean up
157 IN IP4_ROUTE_CACHE
*RtCache
162 IP4_ROUTE_CACHE_ENTRY
*RtCacheEntry
;
165 for (Index
= 0; Index
< IP4_ROUTE_CACHE_HASH_VALUE
; Index
++) {
166 NET_LIST_FOR_EACH_SAFE (Entry
, Next
, &(RtCache
->CacheBucket
[Index
])) {
167 RtCacheEntry
= NET_LIST_USER_STRUCT (Entry
, IP4_ROUTE_CACHE_ENTRY
, Link
);
169 RemoveEntryList (Entry
);
170 Ip4FreeRouteCacheEntry (RtCacheEntry
);
178 Create an empty route table, includes its internal route cache
180 @return NULL if failed to allocate memory for the route table, otherwise
181 the point to newly created route table.
185 Ip4CreateRouteTable (
189 IP4_ROUTE_TABLE
*RtTable
;
192 RtTable
= AllocatePool (sizeof (IP4_ROUTE_TABLE
));
194 if (RtTable
== NULL
) {
199 RtTable
->TotalNum
= 0;
201 for (Index
= 0; Index
<= IP4_MASK_MAX
; Index
++) {
202 InitializeListHead (&(RtTable
->RouteArea
[Index
]));
205 RtTable
->Next
= NULL
;
207 Ip4InitRouteCache (&RtTable
->Cache
);
213 Free the route table and its associated route cache. Route
214 table is reference counted.
216 @param[in] RtTable The route table to free.
221 IN IP4_ROUTE_TABLE
*RtTable
226 IP4_ROUTE_ENTRY
*RtEntry
;
229 ASSERT (RtTable
->RefCnt
> 0);
231 if (--RtTable
->RefCnt
> 0) {
236 // Free all the route table entry and its route cache.
238 for (Index
= 0; Index
<= IP4_MASK_MAX
; Index
++) {
239 NET_LIST_FOR_EACH_SAFE (Entry
, Next
, &(RtTable
->RouteArea
[Index
])) {
240 RtEntry
= NET_LIST_USER_STRUCT (Entry
, IP4_ROUTE_ENTRY
, Link
);
242 RemoveEntryList (Entry
);
243 Ip4FreeRouteEntry (RtEntry
);
247 Ip4CleanRouteCache (&RtTable
->Cache
);
255 Remove all the cache entries bearing the Tag. When a route cache
256 entry is created, it is tagged with the address of route entry
257 from which it is spawned. When a route entry is deleted, the cache
258 entries spawned from it are also deleted.
260 @param RtCache Route cache to remove the entries from
261 @param Tag The Tag of the entries to remove
266 IN OUT IP4_ROUTE_CACHE
*RtCache
,
272 IP4_ROUTE_CACHE_ENTRY
*RtCacheEntry
;
275 for (Index
= 0; Index
< IP4_ROUTE_CACHE_HASH_VALUE
; Index
++) {
276 NET_LIST_FOR_EACH_SAFE (Entry
, Next
, &RtCache
->CacheBucket
[Index
]) {
278 RtCacheEntry
= NET_LIST_USER_STRUCT (Entry
, IP4_ROUTE_CACHE_ENTRY
, Link
);
280 if (RtCacheEntry
->Tag
== Tag
) {
281 RemoveEntryList (Entry
);
282 Ip4FreeRouteCacheEntry (RtCacheEntry
);
290 Add a route entry to the route table. All the IP4_ADDRs are in
293 @param[in, out] RtTable Route table to add route to
294 @param[in] Dest The destination of the network
295 @param[in] Netmask The netmask of the destination
296 @param[in] Gateway The next hop address
298 @retval EFI_ACCESS_DENIED The same route already exists
299 @retval EFI_OUT_OF_RESOURCES Failed to allocate memory for the entry
300 @retval EFI_SUCCESS The route is added successfully.
305 IN OUT IP4_ROUTE_TABLE
*RtTable
,
313 IP4_ROUTE_ENTRY
*RtEntry
;
316 // All the route entries with the same netmask length are
317 // linke to the same route area
319 Head
= &(RtTable
->RouteArea
[NetGetMaskLength (Netmask
)]);
322 // First check whether the route exists
324 NET_LIST_FOR_EACH (Entry
, Head
) {
325 RtEntry
= NET_LIST_USER_STRUCT (Entry
, IP4_ROUTE_ENTRY
, Link
);
327 if (IP4_NET_EQUAL (RtEntry
->Dest
, Dest
, Netmask
) && (RtEntry
->NextHop
== Gateway
)) {
328 return EFI_ACCESS_DENIED
;
333 // Create a route entry and insert it to the route area.
335 RtEntry
= Ip4CreateRouteEntry (Dest
, Netmask
, Gateway
);
337 if (RtEntry
== NULL
) {
338 return EFI_OUT_OF_RESOURCES
;
341 if (Gateway
== IP4_ALLZERO_ADDRESS
) {
342 RtEntry
->Flag
= IP4_DIRECT_ROUTE
;
345 InsertHeadList (Head
, &RtEntry
->Link
);
353 Remove a route entry and all the route caches spawn from it.
355 @param RtTable The route table to remove the route from
356 @param Dest The destination network
357 @param Netmask The netmask of the Dest
358 @param Gateway The next hop address
360 @retval EFI_SUCCESS The route entry is successfully removed
361 @retval EFI_NOT_FOUND There is no route entry in the table with that
367 IN OUT IP4_ROUTE_TABLE
*RtTable
,
376 IP4_ROUTE_ENTRY
*RtEntry
;
378 Head
= &(RtTable
->RouteArea
[NetGetMaskLength (Netmask
)]);
380 NET_LIST_FOR_EACH_SAFE (Entry
, Next
, Head
) {
381 RtEntry
= NET_LIST_USER_STRUCT (Entry
, IP4_ROUTE_ENTRY
, Link
);
383 if (IP4_NET_EQUAL (RtEntry
->Dest
, Dest
, Netmask
) && (RtEntry
->NextHop
== Gateway
)) {
384 Ip4PurgeRouteCache (&RtTable
->Cache
, (UINTN
) RtEntry
);
385 RemoveEntryList (Entry
);
386 Ip4FreeRouteEntry (RtEntry
);
393 return EFI_NOT_FOUND
;
398 Find a route cache with the dst and src. This is used by ICMP
399 redirect messasge process. All kinds of redirect is treated as
400 host redirect according to RFC1122. So, only route cache entries
401 are modified according to the ICMP redirect message.
403 @param[in] RtTable The route table to search the cache for
404 @param[in] Dest The destination address
405 @param[in] Src The source address
407 @return NULL if no route entry to the (Dest, Src). Otherwise the point
408 to the correct route cache entry.
411 IP4_ROUTE_CACHE_ENTRY
*
413 IN IP4_ROUTE_TABLE
*RtTable
,
419 IP4_ROUTE_CACHE_ENTRY
*RtCacheEntry
;
422 Index
= IP4_ROUTE_CACHE_HASH (Dest
, Src
);
424 NET_LIST_FOR_EACH (Entry
, &RtTable
->Cache
.CacheBucket
[Index
]) {
425 RtCacheEntry
= NET_LIST_USER_STRUCT (Entry
, IP4_ROUTE_CACHE_ENTRY
, Link
);
427 if ((RtCacheEntry
->Dest
== Dest
) && (RtCacheEntry
->Src
== Src
)) {
428 NET_GET_REF (RtCacheEntry
);
438 Search the route table for a most specific match to the Dst. It searches
439 from the longest route area (mask length == 32) to the shortest route area
440 (default routes). In each route area, it will first search the instance's
441 route table, then the default route table. This is required by the following
443 1. IP search the route table for a most specific match
444 2. The local route entries have precedence over the default route entry.
446 @param[in] RtTable The route table to search from
447 @param[in] Dst The destionation address to search
449 @return NULL if no route matches the Dst, otherwise the point to the
450 most specific route to the Dst.
455 IN IP4_ROUTE_TABLE
*RtTable
,
460 IP4_ROUTE_ENTRY
*RtEntry
;
461 IP4_ROUTE_TABLE
*Table
;
466 for (Index
= IP4_MASK_MAX
; Index
>= 0; Index
--) {
467 for (Table
= RtTable
; Table
!= NULL
; Table
= Table
->Next
) {
468 NET_LIST_FOR_EACH (Entry
, &Table
->RouteArea
[Index
]) {
469 RtEntry
= NET_LIST_USER_STRUCT (Entry
, IP4_ROUTE_ENTRY
, Link
);
471 if (IP4_NET_EQUAL (RtEntry
->Dest
, Dst
, RtEntry
->Netmask
)) {
472 NET_GET_REF (RtEntry
);
485 Search the route table to route the packet. Return/create a route
486 cache if there is a route to the destination.
488 @param[in] RtTable The route table to search from
489 @param[in] Dest The destination address to search for
490 @param[in] Src The source address to search for
491 @param[in] SubnetMask The subnet mask of the Src address, this field is
492 used to check if the station is using /32 subnet.
493 @param[in] AlwaysTryDestAddr Always try to use the dest address as next hop even
494 though we can't find a matching route entry. This
495 field is only valid when using /32 subnet.
497 @return NULL if failed to route packet, otherwise a route cache
498 entry that can be used to route packet.
501 IP4_ROUTE_CACHE_ENTRY
*
503 IN IP4_ROUTE_TABLE
*RtTable
,
506 IN IP4_ADDR SubnetMask
,
507 IN BOOLEAN AlwaysTryDestAddr
513 IP4_ROUTE_CACHE_ENTRY
*RtCacheEntry
;
514 IP4_ROUTE_CACHE_ENTRY
*Cache
;
515 IP4_ROUTE_ENTRY
*RtEntry
;
519 ASSERT (RtTable
!= NULL
);
521 Head
= &RtTable
->Cache
.CacheBucket
[IP4_ROUTE_CACHE_HASH (Dest
, Src
)];
522 RtCacheEntry
= Ip4FindRouteCache (RtTable
, Dest
, Src
);
525 // If found, promote the cache entry to the head of the hash bucket. LRU
527 if (RtCacheEntry
!= NULL
) {
528 RemoveEntryList (&RtCacheEntry
->Link
);
529 InsertHeadList (Head
, &RtCacheEntry
->Link
);
534 // Search the route table for the most specific route
536 RtEntry
= Ip4FindRouteEntry (RtTable
, Dest
);
538 if (RtEntry
== NULL
) {
539 if (SubnetMask
!= IP4_ALLONE_ADDRESS
) {
541 } else if (!AlwaysTryDestAddr
) {
547 // Found a route to the Dest, if it is a direct route, the packet
548 // will be sent directly to the destination, such as for connected
549 // network. Otherwise, it is an indirect route, the packet will be
550 // sent to the next hop router.
552 // When using /32 subnet mask, the packet will always be sent to the direct
553 // destination first, if we can't find a matching route cache.
555 if (SubnetMask
== IP4_ALLONE_ADDRESS
|| ((RtEntry
->Flag
& IP4_DIRECT_ROUTE
) != 0)) {
558 NextHop
= RtEntry
->NextHop
;
561 if (RtEntry
!= NULL
) {
562 Ip4FreeRouteEntry (RtEntry
);
566 // Create a route cache entry, and tag it as spawned from this route entry
567 // For /32 subnet mask, the default route in RtEntry will be used if failed
568 // to send the packet to driect destination address.
570 RtCacheEntry
= Ip4CreateRouteCacheEntry (Dest
, Src
, NextHop
, (UINTN
) RtEntry
);
572 if (RtCacheEntry
== NULL
) {
576 InsertHeadList (Head
, &RtCacheEntry
->Link
);
577 NET_GET_REF (RtCacheEntry
);
580 // Each bucket of route cache can contain at most 64 entries.
581 // Remove the entries at the tail of the bucket. These entries
582 // are likely to be used least.
585 NET_LIST_FOR_EACH_SAFE (Entry
, Next
, Head
) {
586 if (++Count
< IP4_ROUTE_CACHE_MAX
) {
590 Cache
= NET_LIST_USER_STRUCT (Entry
, IP4_ROUTE_CACHE_ENTRY
, Link
);
592 RemoveEntryList (Entry
);
593 Ip4FreeRouteCacheEntry (Cache
);
601 Build a EFI_IP4_ROUTE_TABLE to be returned to the caller of
602 GetModeData. The EFI_IP4_ROUTE_TABLE is clumsy to use in the
603 internal operation of the IP4 driver.
605 @param[in] IpInstance The IP4 child that requests the route table.
607 @retval EFI_SUCCESS The route table is successfully build
608 @retval EFI_OUT_OF_RESOURCES Failed to allocate the memory for the rotue table.
612 Ip4BuildEfiRouteTable (
613 IN IP4_PROTOCOL
*IpInstance
617 IP4_ROUTE_TABLE
*RtTable
;
618 IP4_ROUTE_ENTRY
*RtEntry
;
619 EFI_IP4_ROUTE_TABLE
*Table
;
623 RtTable
= IpInstance
->RouteTable
;
625 if (IpInstance
->EfiRouteTable
!= NULL
) {
626 FreePool (IpInstance
->EfiRouteTable
);
628 IpInstance
->EfiRouteTable
= NULL
;
629 IpInstance
->EfiRouteCount
= 0;
632 Count
= RtTable
->TotalNum
;
634 if (RtTable
->Next
!= NULL
) {
635 Count
+= RtTable
->Next
->TotalNum
;
642 Table
= AllocatePool (sizeof (EFI_IP4_ROUTE_TABLE
) * Count
);
645 return EFI_OUT_OF_RESOURCES
;
649 // Copy the route entry to EFI route table. Keep the order of
650 // route entry copied from most specific to default route. That
651 // is, interlevel the route entry from the instance's route area
652 // and those from the default route table's route area.
656 for (Index
= IP4_MASK_MAX
; Index
>= 0; Index
--) {
657 for (RtTable
= IpInstance
->RouteTable
; RtTable
!= NULL
; RtTable
= RtTable
->Next
) {
658 NET_LIST_FOR_EACH (Entry
, &(RtTable
->RouteArea
[Index
])) {
659 RtEntry
= NET_LIST_USER_STRUCT (Entry
, IP4_ROUTE_ENTRY
, Link
);
661 EFI_IP4 (Table
[Count
].SubnetAddress
) = HTONL (RtEntry
->Dest
& RtEntry
->Netmask
);
662 EFI_IP4 (Table
[Count
].SubnetMask
) = HTONL (RtEntry
->Netmask
);
663 EFI_IP4 (Table
[Count
].GatewayAddress
) = HTONL (RtEntry
->NextHop
);
670 IpInstance
->EfiRouteTable
= Table
;
671 IpInstance
->EfiRouteCount
= Count
;