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
498 @return NULL if failed to route packet, otherwise a route cache
499 entry that can be used to route packet.
502 IP4_ROUTE_CACHE_ENTRY
*
504 IN IP4_ROUTE_TABLE
*RtTable
,
512 IP4_ROUTE_CACHE_ENTRY
*RtCacheEntry
;
513 IP4_ROUTE_CACHE_ENTRY
*Cache
;
514 IP4_ROUTE_ENTRY
*RtEntry
;
518 ASSERT (RtTable
!= NULL
);
520 Head
= &RtTable
->Cache
.CacheBucket
[IP4_ROUTE_CACHE_HASH (Dest
, Src
)];
521 RtCacheEntry
= Ip4FindRouteCache (RtTable
, Dest
, Src
);
524 // If found, promote the cache entry to the head of the hash bucket. LRU
526 if (RtCacheEntry
!= NULL
) {
527 RemoveEntryList (&RtCacheEntry
->Link
);
528 InsertHeadList (Head
, &RtCacheEntry
->Link
);
533 // Search the route table for the most specific route
535 RtEntry
= Ip4FindRouteEntry (RtTable
, Dest
);
537 if (RtEntry
== NULL
) {
542 // Found a route to the Dest, if it is a direct route, the packet
543 // will be sent directly to the destination, such as for connected
544 // network. Otherwise, it is an indirect route, the packet will be
545 // sent to the next hop router.
547 if ((RtEntry
->Flag
& IP4_DIRECT_ROUTE
) != 0) {
550 NextHop
= RtEntry
->NextHop
;
553 Ip4FreeRouteEntry (RtEntry
);
556 // Create a route cache entry, and tag it as spawned from this route entry
558 RtCacheEntry
= Ip4CreateRouteCacheEntry (Dest
, Src
, NextHop
, (UINTN
) RtEntry
);
560 if (RtCacheEntry
== NULL
) {
564 InsertHeadList (Head
, &RtCacheEntry
->Link
);
565 NET_GET_REF (RtCacheEntry
);
568 // Each bucket of route cache can contain at most 64 entries.
569 // Remove the entries at the tail of the bucket. These entries
570 // are likely to be used least.
573 NET_LIST_FOR_EACH_SAFE (Entry
, Next
, Head
) {
574 if (++Count
< IP4_ROUTE_CACHE_MAX
) {
578 Cache
= NET_LIST_USER_STRUCT (Entry
, IP4_ROUTE_CACHE_ENTRY
, Link
);
580 RemoveEntryList (Entry
);
581 Ip4FreeRouteCacheEntry (Cache
);
589 Build a EFI_IP4_ROUTE_TABLE to be returned to the caller of
590 GetModeData. The EFI_IP4_ROUTE_TABLE is clumsy to use in the
591 internal operation of the IP4 driver.
593 @param[in] IpInstance The IP4 child that requests the route table.
595 @retval EFI_SUCCESS The route table is successfully build
596 @retval EFI_OUT_OF_RESOURCES Failed to allocate the memory for the rotue table.
600 Ip4BuildEfiRouteTable (
601 IN IP4_PROTOCOL
*IpInstance
605 IP4_ROUTE_TABLE
*RtTable
;
606 IP4_ROUTE_ENTRY
*RtEntry
;
607 EFI_IP4_ROUTE_TABLE
*Table
;
611 RtTable
= IpInstance
->RouteTable
;
613 if (IpInstance
->EfiRouteTable
!= NULL
) {
614 FreePool (IpInstance
->EfiRouteTable
);
616 IpInstance
->EfiRouteTable
= NULL
;
617 IpInstance
->EfiRouteCount
= 0;
620 Count
= RtTable
->TotalNum
;
622 if (RtTable
->Next
!= NULL
) {
623 Count
+= RtTable
->Next
->TotalNum
;
630 Table
= AllocatePool (sizeof (EFI_IP4_ROUTE_TABLE
) * Count
);
633 return EFI_OUT_OF_RESOURCES
;
637 // Copy the route entry to EFI route table. Keep the order of
638 // route entry copied from most specific to default route. That
639 // is, interlevel the route entry from the instance's route area
640 // and those from the default route table's route area.
644 for (Index
= IP4_MASK_MAX
; Index
>= 0; Index
--) {
645 for (RtTable
= IpInstance
->RouteTable
; RtTable
!= NULL
; RtTable
= RtTable
->Next
) {
646 NET_LIST_FOR_EACH (Entry
, &(RtTable
->RouteArea
[Index
])) {
647 RtEntry
= NET_LIST_USER_STRUCT (Entry
, IP4_ROUTE_ENTRY
, Link
);
649 EFI_IP4 (Table
[Count
].SubnetAddress
) = HTONL (RtEntry
->Dest
& RtEntry
->Netmask
);
650 EFI_IP4 (Table
[Count
].SubnetMask
) = HTONL (RtEntry
->Netmask
);
651 EFI_IP4 (Table
[Count
].GatewayAddress
) = HTONL (RtEntry
->NextHop
);
658 IpInstance
->EfiRouteTable
= Table
;
659 IpInstance
->EfiRouteCount
= Count
;