fed1983515188affe0bc57f836f2c130c22c1580
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
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.
26 Allocate a route entry then initialize it with the Dest/Netmaks
29 @param Dest The destination network
30 @param Netmask The destination network mask
31 @param GateWay The nexthop address
33 @return NULL if failed to allocate memeory, otherwise the newly created
45 IP4_ROUTE_ENTRY
*RtEntry
;
47 RtEntry
= AllocatePool (sizeof (IP4_ROUTE_ENTRY
));
49 if (RtEntry
== NULL
) {
53 InitializeListHead (&RtEntry
->Link
);
57 RtEntry
->Netmask
= Netmask
;
58 RtEntry
->NextHop
= GateWay
;
66 Free the route table entry. It is reference counted.
68 @param RtEntry The route entry to free.
76 IN IP4_ROUTE_ENTRY
*RtEntry
79 ASSERT (RtEntry
->RefCnt
> 0);
81 if (--RtEntry
->RefCnt
== 0) {
82 gBS
->FreePool (RtEntry
);
88 Allocate and initialize a IP4 route cache entry.
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.
96 @return NULL if failed to allocate memory for the cache, other point
97 @return to the created route cache entry.
101 IP4_ROUTE_CACHE_ENTRY
*
102 Ip4CreateRouteCacheEntry (
109 IP4_ROUTE_CACHE_ENTRY
*RtCacheEntry
;
111 RtCacheEntry
= AllocatePool (sizeof (IP4_ROUTE_CACHE_ENTRY
));
113 if (RtCacheEntry
== NULL
) {
117 InitializeListHead (&RtCacheEntry
->Link
);
119 RtCacheEntry
->RefCnt
= 1;
120 RtCacheEntry
->Dest
= Dst
;
121 RtCacheEntry
->Src
= Src
;
122 RtCacheEntry
->NextHop
= GateWay
;
123 RtCacheEntry
->Tag
= Tag
;
130 Free the route cache entry. It is reference counted.
132 @param RtCacheEntry The route cache entry to free.
138 Ip4FreeRouteCacheEntry (
139 IN IP4_ROUTE_CACHE_ENTRY
*RtCacheEntry
142 ASSERT (RtCacheEntry
->RefCnt
> 0);
144 if (--RtCacheEntry
->RefCnt
== 0) {
145 gBS
->FreePool (RtCacheEntry
);
151 Initialize an empty route cache table.
153 @param RtCache The rotue cache table to initialize.
160 IN IP4_ROUTE_CACHE
*RtCache
165 for (Index
= 0; Index
< IP4_ROUTE_CACHE_HASH
; Index
++) {
166 InitializeListHead (&(RtCache
->CacheBucket
[Index
]));
172 Clean up a route cache, that is free all the route cache
173 entries enqueued in the cache.
175 @param RtCache The route cache table to clean up
182 IN IP4_ROUTE_CACHE
*RtCache
187 IP4_ROUTE_CACHE_ENTRY
*RtCacheEntry
;
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
);
194 RemoveEntryList (Entry
);
195 Ip4FreeRouteCacheEntry (RtCacheEntry
);
203 Create an empty route table, includes its internal route cache
207 @return NULL if failed to allocate memory for the route table, otherwise
208 @return the point to newly created route table.
212 Ip4CreateRouteTable (
216 IP4_ROUTE_TABLE
*RtTable
;
219 RtTable
= AllocatePool (sizeof (IP4_ROUTE_TABLE
));
221 if (RtTable
== NULL
) {
226 RtTable
->TotalNum
= 0;
228 for (Index
= 0; Index
< IP4_MASK_NUM
; Index
++) {
229 InitializeListHead (&(RtTable
->RouteArea
[Index
]));
232 RtTable
->Next
= NULL
;
234 Ip4InitRouteCache (&RtTable
->Cache
);
240 Free the route table and its associated route cache. Route
241 table is reference counted.
243 @param RtTable The route table to free.
250 IN IP4_ROUTE_TABLE
*RtTable
255 IP4_ROUTE_ENTRY
*RtEntry
;
258 ASSERT (RtTable
->RefCnt
> 0);
260 if (--RtTable
->RefCnt
> 0) {
265 // Free all the route table entry and its route cache.
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
);
271 RemoveEntryList (Entry
);
272 Ip4FreeRouteEntry (RtEntry
);
276 Ip4CleanRouteCache (&RtTable
->Cache
);
278 gBS
->FreePool (RtTable
);
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.
289 @param RtCache Route cache to remove the entries from
290 @param Tag The Tag of the entries to remove
298 IN IP4_ROUTE_CACHE
*RtCache
,
304 IP4_ROUTE_CACHE_ENTRY
*RtCacheEntry
;
307 for (Index
= 0; Index
< IP4_ROUTE_CACHE_HASH
; Index
++) {
308 NET_LIST_FOR_EACH_SAFE (Entry
, Next
, &RtCache
->CacheBucket
[Index
]) {
310 RtCacheEntry
= NET_LIST_USER_STRUCT (Entry
, IP4_ROUTE_CACHE_ENTRY
, Link
);
312 if (RtCacheEntry
->Tag
== Tag
) {
313 RemoveEntryList (Entry
);
314 Ip4FreeRouteCacheEntry (RtCacheEntry
);
322 Add a route entry to the route table. All the IP4_ADDRs are in
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
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.
337 IN IP4_ROUTE_TABLE
*RtTable
,
345 IP4_ROUTE_ENTRY
*RtEntry
;
348 // All the route entries with the same netmask length are
349 // linke to the same route area
351 Head
= &(RtTable
->RouteArea
[NetGetMaskLength (Netmask
)]);
354 // First check whether the route exists
356 NET_LIST_FOR_EACH (Entry
, Head
) {
357 RtEntry
= NET_LIST_USER_STRUCT (Entry
, IP4_ROUTE_ENTRY
, Link
);
359 if (IP4_NET_EQUAL (RtEntry
->Dest
, Dest
, Netmask
) && (RtEntry
->NextHop
== Gateway
)) {
360 return EFI_ACCESS_DENIED
;
365 // Create a route entry and insert it to the route area.
367 RtEntry
= Ip4CreateRouteEntry (Dest
, Netmask
, Gateway
);
369 if (RtEntry
== NULL
) {
370 return EFI_OUT_OF_RESOURCES
;
373 if (Gateway
== IP4_ALLZERO_ADDRESS
) {
374 RtEntry
->Flag
= IP4_DIRECT_ROUTE
;
377 InsertHeadList (Head
, &RtEntry
->Link
);
385 Remove a route entry and all the route caches spawn from it.
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
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
399 IN IP4_ROUTE_TABLE
*RtTable
,
408 IP4_ROUTE_ENTRY
*RtEntry
;
410 Head
= &(RtTable
->RouteArea
[NetGetMaskLength (Netmask
)]);
412 NET_LIST_FOR_EACH_SAFE (Entry
, Next
, Head
) {
413 RtEntry
= NET_LIST_USER_STRUCT (Entry
, IP4_ROUTE_ENTRY
, Link
);
415 if (IP4_NET_EQUAL (RtEntry
->Dest
, Dest
, Netmask
) && (RtEntry
->NextHop
== Gateway
)) {
416 Ip4PurgeRouteCache (&RtTable
->Cache
, (UINTN
) RtEntry
);
417 RemoveEntryList (Entry
);
418 Ip4FreeRouteEntry (RtEntry
);
425 return EFI_NOT_FOUND
;
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.
435 @param RtTable The route table to search the cache for
436 @param Dest The destination address
437 @param Src The source address
439 @return NULL if no route entry to the (Dest, Src). Otherwise the point
440 @return to the correct route cache entry.
443 IP4_ROUTE_CACHE_ENTRY
*
445 IN IP4_ROUTE_TABLE
*RtTable
,
451 IP4_ROUTE_CACHE_ENTRY
*RtCacheEntry
;
454 Index
= IP4_ROUTE_CACHE_HASH (Dest
, Src
);
456 NET_LIST_FOR_EACH (Entry
, &RtTable
->Cache
.CacheBucket
[Index
]) {
457 RtCacheEntry
= NET_LIST_USER_STRUCT (Entry
, IP4_ROUTE_CACHE_ENTRY
, Link
);
459 if ((RtCacheEntry
->Dest
== Dest
) && (RtCacheEntry
->Src
== Src
)) {
460 NET_GET_REF (RtCacheEntry
);
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
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.
478 @param RtTable The route table to search from
479 @param Dst The destionation address to search
481 @return NULL if no route matches the Dst, otherwise the point to the
482 @return most specific route to the Dst.
488 IN IP4_ROUTE_TABLE
*RtTable
,
493 IP4_ROUTE_ENTRY
*RtEntry
;
494 IP4_ROUTE_TABLE
*Table
;
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
);
504 if (IP4_NET_EQUAL (RtEntry
->Dest
, Dst
, RtEntry
->Netmask
)) {
505 NET_GET_REF (RtEntry
);
518 Search the route table to route the packet. Return/creat a route
519 cache if there is a route to the destination.
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
525 @return NULL if failed to route packet, otherwise a route cache
526 @return entry that can be used to route packet.
529 IP4_ROUTE_CACHE_ENTRY
*
531 IN IP4_ROUTE_TABLE
*RtTable
,
539 IP4_ROUTE_CACHE_ENTRY
*RtCacheEntry
;
540 IP4_ROUTE_CACHE_ENTRY
*Cache
;
541 IP4_ROUTE_ENTRY
*RtEntry
;
545 ASSERT (RtTable
!= NULL
);
547 Head
= &RtTable
->Cache
.CacheBucket
[IP4_ROUTE_CACHE_HASH (Dest
, Src
)];
548 RtCacheEntry
= Ip4FindRouteCache (RtTable
, Dest
, Src
);
551 // If found, promote the cache entry to the head of the hash bucket. LRU
553 if (RtCacheEntry
!= NULL
) {
554 RemoveEntryList (&RtCacheEntry
->Link
);
555 InsertHeadList (Head
, &RtCacheEntry
->Link
);
560 // Search the route table for the most specific route
562 RtEntry
= Ip4FindRouteEntry (RtTable
, Dest
);
564 if (RtEntry
== NULL
) {
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.
574 if (RtEntry
->Flag
& IP4_DIRECT_ROUTE
) {
577 NextHop
= RtEntry
->NextHop
;
580 Ip4FreeRouteEntry (RtEntry
);
583 // Create a route cache entry, and tag it as spawned from this route entry
585 RtCacheEntry
= Ip4CreateRouteCacheEntry (Dest
, Src
, NextHop
, (UINTN
) RtEntry
);
587 if (RtCacheEntry
== NULL
) {
591 InsertHeadList (Head
, &RtCacheEntry
->Link
);
592 NET_GET_REF (RtCacheEntry
);
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.
600 NET_LIST_FOR_EACH_SAFE (Entry
, Next
, Head
) {
601 if (++Count
< IP4_ROUTE_CACHE_MAX
) {
605 Cache
= NET_LIST_USER_STRUCT (Entry
, IP4_ROUTE_CACHE_ENTRY
, Link
);
607 RemoveEntryList (Entry
);
608 Ip4FreeRouteCacheEntry (Cache
);
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.
620 @param IpInstance The IP4 child that requests the route table.
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.
627 Ip4BuildEfiRouteTable (
628 IN IP4_PROTOCOL
*IpInstance
632 IP4_ROUTE_TABLE
*RtTable
;
633 IP4_ROUTE_ENTRY
*RtEntry
;
634 EFI_IP4_ROUTE_TABLE
*Table
;
638 RtTable
= IpInstance
->RouteTable
;
640 if (IpInstance
->EfiRouteTable
!= NULL
) {
641 gBS
->FreePool (IpInstance
->EfiRouteTable
);
643 IpInstance
->EfiRouteTable
= NULL
;
644 IpInstance
->EfiRouteCount
= 0;
647 Count
= RtTable
->TotalNum
;
649 if (RtTable
->Next
!= NULL
) {
650 Count
+= RtTable
->Next
->TotalNum
;
657 Table
= AllocatePool (sizeof (EFI_IP4_ROUTE_TABLE
) * Count
);
660 return EFI_OUT_OF_RESOURCES
;
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.
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
);
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
);
685 IpInstance
->EfiRouteTable
= Table
;
686 IpInstance
->EfiRouteCount
= Count
;