2 The functions and routines to handle the route caches and route table.
4 Copyright (c) 2009 - 2016, Intel Corporation. All rights reserved.<BR>
6 SPDX-License-Identifier: BSD-2-Clause-Patent
13 This is the worker function for IP6_ROUTE_CACHE_HASH(). It calculates the value
14 as the index of the route cache bucket according to the prefix of two IPv6 addresses.
16 @param[in] Ip1 The IPv6 address.
17 @param[in] Ip2 The IPv6 address.
19 @return The hash value of the prefix of two IPv6 addresses.
24 IN EFI_IPv6_ADDRESS
*Ip1
,
25 IN EFI_IPv6_ADDRESS
*Ip2
31 Prefix1
= *((UINT32
*) ((UINTN
*) (Ip1
)));
32 Prefix2
= *((UINT32
*) ((UINTN
*) (Ip2
)));
34 return ((UINT32
) (Prefix1
^ Prefix2
) % IP6_ROUTE_CACHE_HASH_SIZE
);
38 Allocate a route entry then initialize it with the Destination/PrefixLength
41 @param[in] Destination The IPv6 destination address. This is an optional
42 parameter that may be NULL.
43 @param[in] PrefixLength The destination network's prefix length.
44 @param[in] GatewayAddress The next hop address. This is an optional parameter
47 @return NULL if failed to allocate memory; otherwise, the newly created route entry.
52 IN EFI_IPv6_ADDRESS
*Destination OPTIONAL
,
53 IN UINT8 PrefixLength
,
54 IN EFI_IPv6_ADDRESS
*GatewayAddress OPTIONAL
57 IP6_ROUTE_ENTRY
*RtEntry
;
59 RtEntry
= AllocateZeroPool (sizeof (IP6_ROUTE_ENTRY
));
61 if (RtEntry
== NULL
) {
67 RtEntry
->PrefixLength
= PrefixLength
;
69 if (Destination
!= NULL
) {
70 IP6_COPY_ADDRESS (&RtEntry
->Destination
, Destination
);
73 if (GatewayAddress
!= NULL
) {
74 IP6_COPY_ADDRESS (&RtEntry
->NextHop
, GatewayAddress
);
81 Free the route table entry. It is reference counted.
83 @param[in, out] RtEntry The route entry to free.
88 IN OUT IP6_ROUTE_ENTRY
*RtEntry
91 ASSERT ((RtEntry
!= NULL
) && (RtEntry
->RefCnt
> 0));
93 if (--RtEntry
->RefCnt
== 0) {
99 Search the route table for a most specific match to the Dst. It searches
100 from the longest route area (prefix length == 128) to the shortest route area
101 (default routes). In each route area, it will first search the instance's
102 route table, then the default route table. This is required per the following
104 1. IP search the route table for a most specific match.
105 2. The local route entries have precedence over the default route entry.
107 @param[in] RtTable The route table to search from.
108 @param[in] Destination The destination address to search. If NULL, search
109 the route table by NextHop.
110 @param[in] NextHop The next hop address. If NULL, search the route table
113 @return NULL if no route matches the Dst. Otherwise, the point to the
114 @return most specific route to the Dst.
119 IN IP6_ROUTE_TABLE
*RtTable
,
120 IN EFI_IPv6_ADDRESS
*Destination OPTIONAL
,
121 IN EFI_IPv6_ADDRESS
*NextHop OPTIONAL
125 IP6_ROUTE_ENTRY
*RtEntry
;
128 ASSERT (Destination
!= NULL
|| NextHop
!= NULL
);
132 for (Index
= IP6_PREFIX_MAX
; Index
>= 0; Index
--) {
133 NET_LIST_FOR_EACH (Entry
, &RtTable
->RouteArea
[Index
]) {
134 RtEntry
= NET_LIST_USER_STRUCT (Entry
, IP6_ROUTE_ENTRY
, Link
);
136 if (Destination
!= NULL
) {
137 if (NetIp6IsNetEqual (Destination
, &RtEntry
->Destination
, RtEntry
->PrefixLength
)) {
138 NET_GET_REF (RtEntry
);
141 } else if (NextHop
!= NULL
) {
142 if (NetIp6IsNetEqual (NextHop
, &RtEntry
->NextHop
, RtEntry
->PrefixLength
)) {
143 NET_GET_REF (RtEntry
);
155 Allocate and initialize a IP6 route cache entry.
157 @param[in] Dst The destination address.
158 @param[in] Src The source address.
159 @param[in] GateWay The next hop address.
160 @param[in] Tag The tag from the caller. This marks all the cache entries
161 spawned from one route table entry.
163 @return NULL if failed to allocate memory for the cache. Otherwise, point
164 to the created route cache entry.
167 IP6_ROUTE_CACHE_ENTRY
*
168 Ip6CreateRouteCacheEntry (
169 IN EFI_IPv6_ADDRESS
*Dst
,
170 IN EFI_IPv6_ADDRESS
*Src
,
171 IN EFI_IPv6_ADDRESS
*GateWay
,
175 IP6_ROUTE_CACHE_ENTRY
*RtCacheEntry
;
177 RtCacheEntry
= AllocatePool (sizeof (IP6_ROUTE_CACHE_ENTRY
));
179 if (RtCacheEntry
== NULL
) {
183 RtCacheEntry
->RefCnt
= 1;
184 RtCacheEntry
->Tag
= Tag
;
186 IP6_COPY_ADDRESS (&RtCacheEntry
->Destination
, Dst
);
187 IP6_COPY_ADDRESS (&RtCacheEntry
->Source
, Src
);
188 IP6_COPY_ADDRESS (&RtCacheEntry
->NextHop
, GateWay
);
194 Free the route cache entry. It is reference counted.
196 @param[in, out] RtCacheEntry The route cache entry to free.
200 Ip6FreeRouteCacheEntry (
201 IN OUT IP6_ROUTE_CACHE_ENTRY
*RtCacheEntry
204 ASSERT (RtCacheEntry
->RefCnt
> 0);
206 if (--RtCacheEntry
->RefCnt
== 0) {
207 FreePool (RtCacheEntry
);
212 Find a route cache with the destination and source address. This is
213 used by the ICMPv6 redirect message process.
215 @param[in] RtTable The route table to search the cache for.
216 @param[in] Dest The destination address.
217 @param[in] Src The source address.
219 @return NULL if no route entry to the (Dest, Src). Otherwise, the pointer
220 to the correct route cache entry.
223 IP6_ROUTE_CACHE_ENTRY
*
225 IN IP6_ROUTE_TABLE
*RtTable
,
226 IN EFI_IPv6_ADDRESS
*Dest
,
227 IN EFI_IPv6_ADDRESS
*Src
231 IP6_ROUTE_CACHE_ENTRY
*RtCacheEntry
;
234 Index
= IP6_ROUTE_CACHE_HASH (Dest
, Src
);
236 NET_LIST_FOR_EACH (Entry
, &RtTable
->Cache
.CacheBucket
[Index
]) {
237 RtCacheEntry
= NET_LIST_USER_STRUCT (Entry
, IP6_ROUTE_CACHE_ENTRY
, Link
);
239 if (EFI_IP6_EQUAL (Dest
, &RtCacheEntry
->Destination
)&& EFI_IP6_EQUAL (Src
, &RtCacheEntry
->Source
)) {
240 NET_GET_REF (RtCacheEntry
);
249 Build an array of EFI_IP6_ROUTE_TABLE to be returned to the caller. The number
250 of EFI_IP6_ROUTE_TABLE is also returned.
252 @param[in] RouteTable The pointer of IP6_ROUTE_TABLE internal used.
253 @param[out] EfiRouteCount The number of returned route entries.
254 @param[out] EfiRouteTable The pointer to the array of EFI_IP6_ROUTE_TABLE.
255 If NULL, only the route entry count is returned.
257 @retval EFI_SUCCESS The EFI_IP6_ROUTE_TABLE successfully built.
258 @retval EFI_OUT_OF_RESOURCES Failed to allocate the memory for the route table.
262 Ip6BuildEfiRouteTable (
263 IN IP6_ROUTE_TABLE
*RouteTable
,
264 OUT UINT32
*EfiRouteCount
,
265 OUT EFI_IP6_ROUTE_TABLE
**EfiRouteTable OPTIONAL
269 IP6_ROUTE_ENTRY
*RtEntry
;
270 EFI_IP6_ROUTE_TABLE
*EfiTable
;
274 ASSERT (EfiRouteCount
!= NULL
);
276 Count
= RouteTable
->TotalNum
;
277 *EfiRouteCount
= Count
;
279 if ((EfiRouteTable
== NULL
) || (Count
== 0)) {
283 if (*EfiRouteTable
== NULL
) {
284 *EfiRouteTable
= AllocatePool (sizeof (EFI_IP6_ROUTE_TABLE
) * Count
);
285 if (*EfiRouteTable
== NULL
) {
286 return EFI_OUT_OF_RESOURCES
;
290 EfiTable
= *EfiRouteTable
;
293 // Copy the route entry to EFI route table.
297 for (Index
= IP6_PREFIX_MAX
; Index
>= 0; Index
--) {
299 NET_LIST_FOR_EACH (Entry
, &(RouteTable
->RouteArea
[Index
])) {
300 RtEntry
= NET_LIST_USER_STRUCT (Entry
, IP6_ROUTE_ENTRY
, Link
);
302 Ip6CopyAddressByPrefix (
303 &EfiTable
[Count
].Destination
,
304 &RtEntry
->Destination
,
305 RtEntry
->PrefixLength
308 IP6_COPY_ADDRESS (&EfiTable
[Count
].Gateway
, &RtEntry
->NextHop
);
309 EfiTable
[Count
].PrefixLength
= RtEntry
->PrefixLength
;
315 ASSERT (Count
== RouteTable
->TotalNum
);
321 Create an empty route table. This includes its internal route cache.
323 @return NULL if failed to allocate memory for the route table. Otherwise,
324 the point to newly created route table.
328 Ip6CreateRouteTable (
332 IP6_ROUTE_TABLE
*RtTable
;
335 RtTable
= AllocatePool (sizeof (IP6_ROUTE_TABLE
));
336 if (RtTable
== NULL
) {
341 RtTable
->TotalNum
= 0;
343 for (Index
= 0; Index
<= IP6_PREFIX_MAX
; Index
++) {
344 InitializeListHead (&RtTable
->RouteArea
[Index
]);
347 for (Index
= 0; Index
< IP6_ROUTE_CACHE_HASH_SIZE
; Index
++) {
348 InitializeListHead (&RtTable
->Cache
.CacheBucket
[Index
]);
349 RtTable
->Cache
.CacheNum
[Index
] = 0;
356 Free the route table and its associated route cache. Route
357 table is reference counted.
359 @param[in, out] RtTable The route table to free.
364 IN OUT IP6_ROUTE_TABLE
*RtTable
369 IP6_ROUTE_ENTRY
*RtEntry
;
370 IP6_ROUTE_CACHE_ENTRY
*RtCacheEntry
;
373 ASSERT (RtTable
->RefCnt
> 0);
375 if (--RtTable
->RefCnt
> 0) {
380 // Free all the route table entry and its route cache.
382 for (Index
= 0; Index
<= IP6_PREFIX_MAX
; Index
++) {
383 NET_LIST_FOR_EACH_SAFE (Entry
, Next
, &RtTable
->RouteArea
[Index
]) {
384 RtEntry
= NET_LIST_USER_STRUCT (Entry
, IP6_ROUTE_ENTRY
, Link
);
385 RemoveEntryList (Entry
);
386 Ip6FreeRouteEntry (RtEntry
);
390 for (Index
= 0; Index
< IP6_ROUTE_CACHE_HASH_SIZE
; Index
++) {
391 NET_LIST_FOR_EACH_SAFE (Entry
, Next
, &RtTable
->Cache
.CacheBucket
[Index
]) {
392 RtCacheEntry
= NET_LIST_USER_STRUCT (Entry
, IP6_ROUTE_CACHE_ENTRY
, Link
);
393 RemoveEntryList (Entry
);
394 Ip6FreeRouteCacheEntry (RtCacheEntry
);
402 Remove all the cache entries bearing the Tag. When a route cache
403 entry is created, it is tagged with the address of route entry
404 from which it is spawned. When a route entry is deleted, the cache
405 entries spawned from it are also deleted.
407 @param[in] RtCache Route cache to remove the entries from.
408 @param[in] Tag The Tag of the entries to remove.
413 IN IP6_ROUTE_CACHE
*RtCache
,
419 IP6_ROUTE_CACHE_ENTRY
*RtCacheEntry
;
422 for (Index
= 0; Index
< IP6_ROUTE_CACHE_HASH_SIZE
; Index
++) {
423 NET_LIST_FOR_EACH_SAFE (Entry
, Next
, &RtCache
->CacheBucket
[Index
]) {
425 RtCacheEntry
= NET_LIST_USER_STRUCT (Entry
, IP6_ROUTE_CACHE_ENTRY
, Link
);
427 if (RtCacheEntry
->Tag
== Tag
) {
428 RemoveEntryList (Entry
);
429 Ip6FreeRouteCacheEntry (RtCacheEntry
);
436 Add a route entry to the route table. It is the help function for EfiIp6Routes.
438 @param[in, out] RtTable Route table to add route to.
439 @param[in] Destination The destination of the network.
440 @param[in] PrefixLength The PrefixLength of the destination.
441 @param[in] GatewayAddress The next hop address.
443 @retval EFI_ACCESS_DENIED The same route already exists.
444 @retval EFI_OUT_OF_RESOURCES Failed to allocate memory for the entry.
445 @retval EFI_SUCCESS The route was added successfully.
450 IN OUT IP6_ROUTE_TABLE
*RtTable
,
451 IN EFI_IPv6_ADDRESS
*Destination
,
452 IN UINT8 PrefixLength
,
453 IN EFI_IPv6_ADDRESS
*GatewayAddress
456 LIST_ENTRY
*ListHead
;
458 IP6_ROUTE_ENTRY
*Route
;
460 ListHead
= &RtTable
->RouteArea
[PrefixLength
];
463 // First check whether the route exists
465 NET_LIST_FOR_EACH (Entry
, ListHead
) {
466 Route
= NET_LIST_USER_STRUCT (Entry
, IP6_ROUTE_ENTRY
, Link
);
468 if (NetIp6IsNetEqual (Destination
, &Route
->Destination
, PrefixLength
) &&
469 EFI_IP6_EQUAL (GatewayAddress
, &Route
->NextHop
)) {
470 return EFI_ACCESS_DENIED
;
475 // Create a route entry and insert it to the route area.
477 Route
= Ip6CreateRouteEntry (Destination
, PrefixLength
, GatewayAddress
);
480 return EFI_OUT_OF_RESOURCES
;
483 if (NetIp6IsUnspecifiedAddr (GatewayAddress
)) {
484 Route
->Flag
= IP6_DIRECT_ROUTE
;
487 InsertHeadList (ListHead
, &Route
->Link
);
494 Remove a route entry and all the route caches spawn from it.
495 It is the help function for EfiIp6Routes.
497 @param[in, out] RtTable The route table to remove the route from.
498 @param[in] Destination The destination network.
499 @param[in] PrefixLength The PrefixLength of the Destination.
500 @param[in] GatewayAddress The next hop address.
502 @retval EFI_SUCCESS The route entry was successfully removed.
503 @retval EFI_NOT_FOUND There is no route entry in the table with that
509 IN OUT IP6_ROUTE_TABLE
*RtTable
,
510 IN EFI_IPv6_ADDRESS
*Destination
,
511 IN UINT8 PrefixLength
,
512 IN EFI_IPv6_ADDRESS
*GatewayAddress
515 LIST_ENTRY
*ListHead
;
518 IP6_ROUTE_ENTRY
*Route
;
521 ListHead
= &RtTable
->RouteArea
[PrefixLength
];
522 TotalNum
= RtTable
->TotalNum
;
524 NET_LIST_FOR_EACH_SAFE (Entry
, Next
, ListHead
) {
525 Route
= NET_LIST_USER_STRUCT (Entry
, IP6_ROUTE_ENTRY
, Link
);
527 if (Destination
!= NULL
&& !NetIp6IsNetEqual (Destination
, &Route
->Destination
, PrefixLength
)) {
530 if (GatewayAddress
!= NULL
&& !EFI_IP6_EQUAL (GatewayAddress
, &Route
->NextHop
)) {
534 Ip6PurgeRouteCache (&RtTable
->Cache
, (UINTN
) Route
);
535 RemoveEntryList (Entry
);
536 Ip6FreeRouteEntry (Route
);
538 ASSERT (RtTable
->TotalNum
> 0);
542 return TotalNum
== RtTable
->TotalNum
? EFI_NOT_FOUND
: EFI_SUCCESS
;
546 Search the route table to route the packet. Return/create a route
547 cache if there is a route to the destination.
549 @param[in] IpSb The IP6 service data.
550 @param[in] Dest The destination address to search for.
551 @param[in] Src The source address to search for.
553 @return NULL if it failed to route the packet. Otherwise, a route cache
554 entry that can be used to route packets.
557 IP6_ROUTE_CACHE_ENTRY
*
559 IN IP6_SERVICE
*IpSb
,
560 IN EFI_IPv6_ADDRESS
*Dest
,
561 IN EFI_IPv6_ADDRESS
*Src
564 IP6_ROUTE_TABLE
*RtTable
;
565 LIST_ENTRY
*ListHead
;
566 IP6_ROUTE_CACHE_ENTRY
*RtCacheEntry
;
567 IP6_ROUTE_ENTRY
*RtEntry
;
568 EFI_IPv6_ADDRESS NextHop
;
571 RtTable
= IpSb
->RouteTable
;
573 ASSERT (RtTable
!= NULL
);
576 // Search the destination cache in IP6_ROUTE_TABLE.
578 Index
= IP6_ROUTE_CACHE_HASH (Dest
, Src
);
579 ListHead
= &RtTable
->Cache
.CacheBucket
[Index
];
581 RtCacheEntry
= Ip6FindRouteCache (RtTable
, Dest
, Src
);
584 // If found, promote the cache entry to the head of the hash bucket.
586 if (RtCacheEntry
!= NULL
) {
587 RemoveEntryList (&RtCacheEntry
->Link
);
588 InsertHeadList (ListHead
, &RtCacheEntry
->Link
);
593 // Search the route table for the most specific route
595 RtEntry
= Ip6FindRouteEntry (RtTable
, Dest
, NULL
);
596 if (RtEntry
== NULL
) {
601 // Found a route to the Dest, if it is a direct route, the packet
602 // will be send directly to the destination, such as for connected
603 // network. Otherwise, it is an indirect route, the packet will be
604 // send the next hop router.
606 if ((RtEntry
->Flag
& IP6_DIRECT_ROUTE
) == IP6_DIRECT_ROUTE
) {
607 IP6_COPY_ADDRESS (&NextHop
, Dest
);
609 IP6_COPY_ADDRESS (&NextHop
, &RtEntry
->NextHop
);
612 Ip6FreeRouteEntry (RtEntry
);
615 // Create a route cache entry, and tag it as spawned from this route entry
617 RtCacheEntry
= Ip6CreateRouteCacheEntry (Dest
, Src
, &NextHop
, (UINTN
) RtEntry
);
619 if (RtCacheEntry
== NULL
) {
623 InsertHeadList (ListHead
, &RtCacheEntry
->Link
);
624 NET_GET_REF (RtCacheEntry
);
625 RtTable
->Cache
.CacheNum
[Index
]++;