]>
git.proxmox.com Git - mirror_edk2.git/blob - MdeModulePkg/Universal/Network/Ip4Dxe/Ip4Route.c
5bec33e5987a7658258b3a767d9c066b186d26e3
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
44 IP4_ROUTE_ENTRY
*RtEntry
;
46 RtEntry
= AllocatePool (sizeof (IP4_ROUTE_ENTRY
));
48 if (RtEntry
== NULL
) {
52 InitializeListHead (&RtEntry
->Link
);
56 RtEntry
->Netmask
= Netmask
;
57 RtEntry
->NextHop
= GateWay
;
65 Free the route table entry. It is reference counted.
67 @param RtEntry The route entry to free.
74 IN IP4_ROUTE_ENTRY
*RtEntry
77 ASSERT (RtEntry
->RefCnt
> 0);
79 if (--RtEntry
->RefCnt
== 0) {
80 gBS
->FreePool (RtEntry
);
86 Allocate and initialize an IP4 route cache entry.
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.
94 @return NULL if failed to allocate memory for the cache, other point
95 to the created route cache entry.
98 IP4_ROUTE_CACHE_ENTRY
*
99 Ip4CreateRouteCacheEntry (
106 IP4_ROUTE_CACHE_ENTRY
*RtCacheEntry
;
108 RtCacheEntry
= AllocatePool (sizeof (IP4_ROUTE_CACHE_ENTRY
));
110 if (RtCacheEntry
== NULL
) {
114 InitializeListHead (&RtCacheEntry
->Link
);
116 RtCacheEntry
->RefCnt
= 1;
117 RtCacheEntry
->Dest
= Dst
;
118 RtCacheEntry
->Src
= Src
;
119 RtCacheEntry
->NextHop
= GateWay
;
120 RtCacheEntry
->Tag
= Tag
;
127 Free the route cache entry. It is reference counted.
129 @param RtCacheEntry The route cache entry to free.
135 Ip4FreeRouteCacheEntry (
136 IN IP4_ROUTE_CACHE_ENTRY
*RtCacheEntry
139 ASSERT (RtCacheEntry
->RefCnt
> 0);
141 if (--RtCacheEntry
->RefCnt
== 0) {
142 gBS
->FreePool (RtCacheEntry
);
148 Initialize an empty route cache table.
150 @param RtCache The rotue cache table to initialize.
157 IN OUT IP4_ROUTE_CACHE
*RtCache
162 for (Index
= 0; Index
< IP4_ROUTE_CACHE_HASH
; Index
++) {
163 InitializeListHead (&(RtCache
->CacheBucket
[Index
]));
169 Clean up a route cache, that is free all the route cache
170 entries enqueued in the cache.
172 @param RtCache The route cache table to clean up
179 IN IP4_ROUTE_CACHE
*RtCache
184 IP4_ROUTE_CACHE_ENTRY
*RtCacheEntry
;
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
);
191 RemoveEntryList (Entry
);
192 Ip4FreeRouteCacheEntry (RtCacheEntry
);
200 Create an empty route table, includes its internal route cache
202 @return NULL if failed to allocate memory for the route table, otherwise
203 the point to newly created route table.
207 Ip4CreateRouteTable (
211 IP4_ROUTE_TABLE
*RtTable
;
214 RtTable
= AllocatePool (sizeof (IP4_ROUTE_TABLE
));
216 if (RtTable
== NULL
) {
221 RtTable
->TotalNum
= 0;
223 for (Index
= 0; Index
< IP4_MASK_NUM
; Index
++) {
224 InitializeListHead (&(RtTable
->RouteArea
[Index
]));
227 RtTable
->Next
= NULL
;
229 Ip4InitRouteCache (&RtTable
->Cache
);
235 Free the route table and its associated route cache. Route
236 table is reference counted.
238 @param RtTable The route table to free.
245 IN IP4_ROUTE_TABLE
*RtTable
250 IP4_ROUTE_ENTRY
*RtEntry
;
253 ASSERT (RtTable
->RefCnt
> 0);
255 if (--RtTable
->RefCnt
> 0) {
260 // Free all the route table entry and its route cache.
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
);
266 RemoveEntryList (Entry
);
267 Ip4FreeRouteEntry (RtEntry
);
271 Ip4CleanRouteCache (&RtTable
->Cache
);
273 gBS
->FreePool (RtTable
);
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.
284 @param RtCache Route cache to remove the entries from
285 @param Tag The Tag of the entries to remove
292 IN OUT IP4_ROUTE_CACHE
*RtCache
,
298 IP4_ROUTE_CACHE_ENTRY
*RtCacheEntry
;
301 for (Index
= 0; Index
< IP4_ROUTE_CACHE_HASH
; Index
++) {
302 NET_LIST_FOR_EACH_SAFE (Entry
, Next
, &RtCache
->CacheBucket
[Index
]) {
304 RtCacheEntry
= NET_LIST_USER_STRUCT (Entry
, IP4_ROUTE_CACHE_ENTRY
, Link
);
306 if (RtCacheEntry
->Tag
== Tag
) {
307 RemoveEntryList (Entry
);
308 Ip4FreeRouteCacheEntry (RtCacheEntry
);
316 Add a route entry to the route table. All the IP4_ADDRs are in
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
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.
331 IN OUT IP4_ROUTE_TABLE
*RtTable
,
339 IP4_ROUTE_ENTRY
*RtEntry
;
342 // All the route entries with the same netmask length are
343 // linke to the same route area
345 Head
= &(RtTable
->RouteArea
[NetGetMaskLength (Netmask
)]);
348 // First check whether the route exists
350 NET_LIST_FOR_EACH (Entry
, Head
) {
351 RtEntry
= NET_LIST_USER_STRUCT (Entry
, IP4_ROUTE_ENTRY
, Link
);
353 if (IP4_NET_EQUAL (RtEntry
->Dest
, Dest
, Netmask
) && (RtEntry
->NextHop
== Gateway
)) {
354 return EFI_ACCESS_DENIED
;
359 // Create a route entry and insert it to the route area.
361 RtEntry
= Ip4CreateRouteEntry (Dest
, Netmask
, Gateway
);
363 if (RtEntry
== NULL
) {
364 return EFI_OUT_OF_RESOURCES
;
367 if (Gateway
== IP4_ALLZERO_ADDRESS
) {
368 RtEntry
->Flag
= IP4_DIRECT_ROUTE
;
371 InsertHeadList (Head
, &RtEntry
->Link
);
379 Remove a route entry and all the route caches spawn from it.
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
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
393 IN OUT IP4_ROUTE_TABLE
*RtTable
,
402 IP4_ROUTE_ENTRY
*RtEntry
;
404 Head
= &(RtTable
->RouteArea
[NetGetMaskLength (Netmask
)]);
406 NET_LIST_FOR_EACH_SAFE (Entry
, Next
, Head
) {
407 RtEntry
= NET_LIST_USER_STRUCT (Entry
, IP4_ROUTE_ENTRY
, Link
);
409 if (IP4_NET_EQUAL (RtEntry
->Dest
, Dest
, Netmask
) && (RtEntry
->NextHop
== Gateway
)) {
410 Ip4PurgeRouteCache (&RtTable
->Cache
, (UINTN
) RtEntry
);
411 RemoveEntryList (Entry
);
412 Ip4FreeRouteEntry (RtEntry
);
419 return EFI_NOT_FOUND
;
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.
429 @param RtTable The route table to search the cache for
430 @param Dest The destination address
431 @param Src The source address
433 @return NULL if no route entry to the (Dest, Src). Otherwise the point
434 to the correct route cache entry.
437 IP4_ROUTE_CACHE_ENTRY
*
439 IN IP4_ROUTE_TABLE
*RtTable
,
445 IP4_ROUTE_CACHE_ENTRY
*RtCacheEntry
;
448 Index
= IP4_ROUTE_CACHE_HASH (Dest
, Src
);
450 NET_LIST_FOR_EACH (Entry
, &RtTable
->Cache
.CacheBucket
[Index
]) {
451 RtCacheEntry
= NET_LIST_USER_STRUCT (Entry
, IP4_ROUTE_CACHE_ENTRY
, Link
);
453 if ((RtCacheEntry
->Dest
== Dest
) && (RtCacheEntry
->Src
== Src
)) {
454 NET_GET_REF (RtCacheEntry
);
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
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.
472 @param RtTable The route table to search from
473 @param Dst The destionation address to search
475 @return NULL if no route matches the Dst, otherwise the point to the
476 @return most specific route to the Dst.
481 IN IP4_ROUTE_TABLE
*RtTable
,
486 IP4_ROUTE_ENTRY
*RtEntry
;
487 IP4_ROUTE_TABLE
*Table
;
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
);
497 if (IP4_NET_EQUAL (RtEntry
->Dest
, Dst
, RtEntry
->Netmask
)) {
498 NET_GET_REF (RtEntry
);
511 Search the route table to route the packet. Return/create a route
512 cache if there is a route to the destination.
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
518 @return NULL if failed to route packet, otherwise a route cache
519 entry that can be used to route packet.
522 IP4_ROUTE_CACHE_ENTRY
*
524 IN IP4_ROUTE_TABLE
*RtTable
,
532 IP4_ROUTE_CACHE_ENTRY
*RtCacheEntry
;
533 IP4_ROUTE_CACHE_ENTRY
*Cache
;
534 IP4_ROUTE_ENTRY
*RtEntry
;
538 ASSERT (RtTable
!= NULL
);
540 Head
= &RtTable
->Cache
.CacheBucket
[IP4_ROUTE_CACHE_HASH (Dest
, Src
)];
541 RtCacheEntry
= Ip4FindRouteCache (RtTable
, Dest
, Src
);
544 // If found, promote the cache entry to the head of the hash bucket. LRU
546 if (RtCacheEntry
!= NULL
) {
547 RemoveEntryList (&RtCacheEntry
->Link
);
548 InsertHeadList (Head
, &RtCacheEntry
->Link
);
553 // Search the route table for the most specific route
555 RtEntry
= Ip4FindRouteEntry (RtTable
, Dest
);
557 if (RtEntry
== NULL
) {
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.
567 if ((RtEntry
->Flag
& IP4_DIRECT_ROUTE
) != 0) {
570 NextHop
= RtEntry
->NextHop
;
573 Ip4FreeRouteEntry (RtEntry
);
576 // Create a route cache entry, and tag it as spawned from this route entry
578 RtCacheEntry
= Ip4CreateRouteCacheEntry (Dest
, Src
, NextHop
, (UINTN
) RtEntry
);
580 if (RtCacheEntry
== NULL
) {
584 InsertHeadList (Head
, &RtCacheEntry
->Link
);
585 NET_GET_REF (RtCacheEntry
);
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.
593 NET_LIST_FOR_EACH_SAFE (Entry
, Next
, Head
) {
594 if (++Count
< IP4_ROUTE_CACHE_MAX
) {
598 Cache
= NET_LIST_USER_STRUCT (Entry
, IP4_ROUTE_CACHE_ENTRY
, Link
);
600 RemoveEntryList (Entry
);
601 Ip4FreeRouteCacheEntry (Cache
);
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.
613 @param IpInstance The IP4 child that requests the route table.
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.
620 Ip4BuildEfiRouteTable (
621 IN IP4_PROTOCOL
*IpInstance
625 IP4_ROUTE_TABLE
*RtTable
;
626 IP4_ROUTE_ENTRY
*RtEntry
;
627 EFI_IP4_ROUTE_TABLE
*Table
;
631 RtTable
= IpInstance
->RouteTable
;
633 if (IpInstance
->EfiRouteTable
!= NULL
) {
634 gBS
->FreePool (IpInstance
->EfiRouteTable
);
636 IpInstance
->EfiRouteTable
= NULL
;
637 IpInstance
->EfiRouteCount
= 0;
640 Count
= RtTable
->TotalNum
;
642 if (RtTable
->Next
!= NULL
) {
643 Count
+= RtTable
->Next
->TotalNum
;
650 Table
= AllocatePool (sizeof (EFI_IP4_ROUTE_TABLE
) * Count
);
653 return EFI_OUT_OF_RESOURCES
;
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.
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
);
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
);
678 IpInstance
->EfiRouteTable
= Table
;
679 IpInstance
->EfiRouteCount
= Count
;