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 This program and the accompanying materials
7 are licensed and made available under the terms and conditions of the BSD License
8 which accompanies this distribution. The full text of the license may be found at
9 http://opensource.org/licenses/bsd-license.php.
11 THE PROGRAM IS DISTRIBUTED UNDER THE BSD LICENSE ON AN "AS IS" BASIS,
12 WITHOUT WARRANTIES OR REPRESENTATIONS OF ANY KIND, EITHER EXPRESS OR IMPLIED.
19 This is the worker function for IP6_ROUTE_CACHE_HASH(). It calculates the value
20 as the index of the route cache bucket according to the prefix of two IPv6 addresses.
22 @param[in] Ip1 The IPv6 address.
23 @param[in] Ip2 The IPv6 address.
25 @return The hash value of the prefix of two IPv6 addresses.
30 IN EFI_IPv6_ADDRESS
*Ip1
,
31 IN EFI_IPv6_ADDRESS
*Ip2
37 Prefix1
= *((UINT32
*) ((UINTN
*) (Ip1
)));
38 Prefix2
= *((UINT32
*) ((UINTN
*) (Ip2
)));
40 return ((UINT32
) (Prefix1
^ Prefix2
) % IP6_ROUTE_CACHE_HASH_SIZE
);
44 Allocate a route entry then initialize it with the Destination/PrefixLength
47 @param[in] Destination The IPv6 destination address. This is an optional
48 parameter that may be NULL.
49 @param[in] PrefixLength The destination network's prefix length.
50 @param[in] GatewayAddress The next hop address. This is an optional parameter
53 @return NULL if failed to allocate memeory; otherwise, the newly created route entry.
58 IN EFI_IPv6_ADDRESS
*Destination OPTIONAL
,
59 IN UINT8 PrefixLength
,
60 IN EFI_IPv6_ADDRESS
*GatewayAddress OPTIONAL
63 IP6_ROUTE_ENTRY
*RtEntry
;
65 RtEntry
= AllocateZeroPool (sizeof (IP6_ROUTE_ENTRY
));
67 if (RtEntry
== NULL
) {
73 RtEntry
->PrefixLength
= PrefixLength
;
75 if (Destination
!= NULL
) {
76 IP6_COPY_ADDRESS (&RtEntry
->Destination
, Destination
);
79 if (GatewayAddress
!= NULL
) {
80 IP6_COPY_ADDRESS (&RtEntry
->NextHop
, GatewayAddress
);
87 Free the route table entry. It is reference counted.
89 @param[in, out] RtEntry The route entry to free.
94 IN OUT IP6_ROUTE_ENTRY
*RtEntry
97 ASSERT ((RtEntry
!= NULL
) && (RtEntry
->RefCnt
> 0));
99 if (--RtEntry
->RefCnt
== 0) {
105 Search the route table for a most specific match to the Dst. It searches
106 from the longest route area (prefix length == 128) to the shortest route area
107 (default routes). In each route area, it will first search the instance's
108 route table, then the default route table. This is required per the following
110 1. IP search the route table for a most specific match.
111 2. The local route entries have precedence over the default route entry.
113 @param[in] RtTable The route table to search from.
114 @param[in] Destination The destionation address to search. If NULL, search
115 the route table by NextHop.
116 @param[in] NextHop The next hop address. If NULL, search the route table
119 @return NULL if no route matches the Dst. Otherwise, the point to the
120 @return most specific route to the Dst.
125 IN IP6_ROUTE_TABLE
*RtTable
,
126 IN EFI_IPv6_ADDRESS
*Destination OPTIONAL
,
127 IN EFI_IPv6_ADDRESS
*NextHop OPTIONAL
131 IP6_ROUTE_ENTRY
*RtEntry
;
134 ASSERT (Destination
!= NULL
|| NextHop
!= NULL
);
138 for (Index
= IP6_PREFIX_MAX
; Index
>= 0; Index
--) {
139 NET_LIST_FOR_EACH (Entry
, &RtTable
->RouteArea
[Index
]) {
140 RtEntry
= NET_LIST_USER_STRUCT (Entry
, IP6_ROUTE_ENTRY
, Link
);
142 if (Destination
!= NULL
) {
143 if (NetIp6IsNetEqual (Destination
, &RtEntry
->Destination
, RtEntry
->PrefixLength
)) {
144 NET_GET_REF (RtEntry
);
147 } else if (NextHop
!= NULL
) {
148 if (NetIp6IsNetEqual (NextHop
, &RtEntry
->NextHop
, RtEntry
->PrefixLength
)) {
149 NET_GET_REF (RtEntry
);
161 Allocate and initialize a IP6 route cache entry.
163 @param[in] Dst The destination address.
164 @param[in] Src The source address.
165 @param[in] GateWay The next hop address.
166 @param[in] Tag The tag from the caller. This marks all the cache entries
167 spawned from one route table entry.
169 @return NULL if failed to allocate memory for the cache. Otherwise, point
170 to the created route cache entry.
173 IP6_ROUTE_CACHE_ENTRY
*
174 Ip6CreateRouteCacheEntry (
175 IN EFI_IPv6_ADDRESS
*Dst
,
176 IN EFI_IPv6_ADDRESS
*Src
,
177 IN EFI_IPv6_ADDRESS
*GateWay
,
181 IP6_ROUTE_CACHE_ENTRY
*RtCacheEntry
;
183 RtCacheEntry
= AllocatePool (sizeof (IP6_ROUTE_CACHE_ENTRY
));
185 if (RtCacheEntry
== NULL
) {
189 RtCacheEntry
->RefCnt
= 1;
190 RtCacheEntry
->Tag
= Tag
;
192 IP6_COPY_ADDRESS (&RtCacheEntry
->Destination
, Dst
);
193 IP6_COPY_ADDRESS (&RtCacheEntry
->Source
, Src
);
194 IP6_COPY_ADDRESS (&RtCacheEntry
->NextHop
, GateWay
);
200 Free the route cache entry. It is reference counted.
202 @param[in, out] RtCacheEntry The route cache entry to free.
206 Ip6FreeRouteCacheEntry (
207 IN OUT IP6_ROUTE_CACHE_ENTRY
*RtCacheEntry
210 ASSERT (RtCacheEntry
->RefCnt
> 0);
212 if (--RtCacheEntry
->RefCnt
== 0) {
213 FreePool (RtCacheEntry
);
218 Find a route cache with the destination and source address. This is
219 used by the ICMPv6 redirect messasge process.
221 @param[in] RtTable The route table to search the cache for.
222 @param[in] Dest The destination address.
223 @param[in] Src The source address.
225 @return NULL if no route entry to the (Dest, Src). Otherwise, the pointer
226 to the correct route cache entry.
229 IP6_ROUTE_CACHE_ENTRY
*
231 IN IP6_ROUTE_TABLE
*RtTable
,
232 IN EFI_IPv6_ADDRESS
*Dest
,
233 IN EFI_IPv6_ADDRESS
*Src
237 IP6_ROUTE_CACHE_ENTRY
*RtCacheEntry
;
240 Index
= IP6_ROUTE_CACHE_HASH (Dest
, Src
);
242 NET_LIST_FOR_EACH (Entry
, &RtTable
->Cache
.CacheBucket
[Index
]) {
243 RtCacheEntry
= NET_LIST_USER_STRUCT (Entry
, IP6_ROUTE_CACHE_ENTRY
, Link
);
245 if (EFI_IP6_EQUAL (Dest
, &RtCacheEntry
->Destination
)&& EFI_IP6_EQUAL (Src
, &RtCacheEntry
->Source
)) {
246 NET_GET_REF (RtCacheEntry
);
255 Build an array of EFI_IP6_ROUTE_TABLE to be returned to the caller. The number
256 of EFI_IP6_ROUTE_TABLE is also returned.
258 @param[in] RouteTable The pointer of IP6_ROUTE_TABLE internal used.
259 @param[out] EfiRouteCount The number of returned route entries.
260 @param[out] EfiRouteTable The pointer to the array of EFI_IP6_ROUTE_TABLE.
261 If NULL, only the route entry count is returned.
263 @retval EFI_SUCCESS The EFI_IP6_ROUTE_TABLE successfully built.
264 @retval EFI_OUT_OF_RESOURCES Failed to allocate the memory for the route table.
268 Ip6BuildEfiRouteTable (
269 IN IP6_ROUTE_TABLE
*RouteTable
,
270 OUT UINT32
*EfiRouteCount
,
271 OUT EFI_IP6_ROUTE_TABLE
**EfiRouteTable OPTIONAL
275 IP6_ROUTE_ENTRY
*RtEntry
;
276 EFI_IP6_ROUTE_TABLE
*EfiTable
;
280 ASSERT (EfiRouteCount
!= NULL
);
282 Count
= RouteTable
->TotalNum
;
283 *EfiRouteCount
= Count
;
285 if ((EfiRouteTable
== NULL
) || (Count
== 0)) {
289 if (*EfiRouteTable
== NULL
) {
290 *EfiRouteTable
= AllocatePool (sizeof (EFI_IP6_ROUTE_TABLE
) * Count
);
291 if (*EfiRouteTable
== NULL
) {
292 return EFI_OUT_OF_RESOURCES
;
296 EfiTable
= *EfiRouteTable
;
299 // Copy the route entry to EFI route table.
303 for (Index
= IP6_PREFIX_MAX
; Index
>= 0; Index
--) {
305 NET_LIST_FOR_EACH (Entry
, &(RouteTable
->RouteArea
[Index
])) {
306 RtEntry
= NET_LIST_USER_STRUCT (Entry
, IP6_ROUTE_ENTRY
, Link
);
308 Ip6CopyAddressByPrefix (
309 &EfiTable
[Count
].Destination
,
310 &RtEntry
->Destination
,
311 RtEntry
->PrefixLength
314 IP6_COPY_ADDRESS (&EfiTable
[Count
].Gateway
, &RtEntry
->NextHop
);
315 EfiTable
[Count
].PrefixLength
= RtEntry
->PrefixLength
;
321 ASSERT (Count
== RouteTable
->TotalNum
);
327 Create an empty route table. This includes its internal route cache.
329 @return NULL if failed to allocate memory for the route table. Otherwise,
330 the point to newly created route table.
334 Ip6CreateRouteTable (
338 IP6_ROUTE_TABLE
*RtTable
;
341 RtTable
= AllocatePool (sizeof (IP6_ROUTE_TABLE
));
342 if (RtTable
== NULL
) {
347 RtTable
->TotalNum
= 0;
349 for (Index
= 0; Index
<= IP6_PREFIX_MAX
; Index
++) {
350 InitializeListHead (&RtTable
->RouteArea
[Index
]);
353 for (Index
= 0; Index
< IP6_ROUTE_CACHE_HASH_SIZE
; Index
++) {
354 InitializeListHead (&RtTable
->Cache
.CacheBucket
[Index
]);
355 RtTable
->Cache
.CacheNum
[Index
] = 0;
362 Free the route table and its associated route cache. Route
363 table is reference counted.
365 @param[in, out] RtTable The route table to free.
370 IN OUT IP6_ROUTE_TABLE
*RtTable
375 IP6_ROUTE_ENTRY
*RtEntry
;
376 IP6_ROUTE_CACHE_ENTRY
*RtCacheEntry
;
379 ASSERT (RtTable
->RefCnt
> 0);
381 if (--RtTable
->RefCnt
> 0) {
386 // Free all the route table entry and its route cache.
388 for (Index
= 0; Index
<= IP6_PREFIX_MAX
; Index
++) {
389 NET_LIST_FOR_EACH_SAFE (Entry
, Next
, &RtTable
->RouteArea
[Index
]) {
390 RtEntry
= NET_LIST_USER_STRUCT (Entry
, IP6_ROUTE_ENTRY
, Link
);
391 RemoveEntryList (Entry
);
392 Ip6FreeRouteEntry (RtEntry
);
396 for (Index
= 0; Index
< IP6_ROUTE_CACHE_HASH_SIZE
; Index
++) {
397 NET_LIST_FOR_EACH_SAFE (Entry
, Next
, &RtTable
->Cache
.CacheBucket
[Index
]) {
398 RtCacheEntry
= NET_LIST_USER_STRUCT (Entry
, IP6_ROUTE_CACHE_ENTRY
, Link
);
399 RemoveEntryList (Entry
);
400 Ip6FreeRouteCacheEntry (RtCacheEntry
);
408 Remove all the cache entries bearing the Tag. When a route cache
409 entry is created, it is tagged with the address of route entry
410 from which it is spawned. When a route entry is deleted, the cache
411 entries spawned from it are also deleted.
413 @param[in] RtCache Route cache to remove the entries from.
414 @param[in] Tag The Tag of the entries to remove.
419 IN IP6_ROUTE_CACHE
*RtCache
,
425 IP6_ROUTE_CACHE_ENTRY
*RtCacheEntry
;
428 for (Index
= 0; Index
< IP6_ROUTE_CACHE_HASH_SIZE
; Index
++) {
429 NET_LIST_FOR_EACH_SAFE (Entry
, Next
, &RtCache
->CacheBucket
[Index
]) {
431 RtCacheEntry
= NET_LIST_USER_STRUCT (Entry
, IP6_ROUTE_CACHE_ENTRY
, Link
);
433 if (RtCacheEntry
->Tag
== Tag
) {
434 RemoveEntryList (Entry
);
435 Ip6FreeRouteCacheEntry (RtCacheEntry
);
442 Add a route entry to the route table. It is the help function for EfiIp6Routes.
444 @param[in, out] RtTable Route table to add route to.
445 @param[in] Destination The destination of the network.
446 @param[in] PrefixLength The PrefixLength of the destination.
447 @param[in] GatewayAddress The next hop address.
449 @retval EFI_ACCESS_DENIED The same route already exists.
450 @retval EFI_OUT_OF_RESOURCES Failed to allocate memory for the entry.
451 @retval EFI_SUCCESS The route was added successfully.
456 IN OUT IP6_ROUTE_TABLE
*RtTable
,
457 IN EFI_IPv6_ADDRESS
*Destination
,
458 IN UINT8 PrefixLength
,
459 IN EFI_IPv6_ADDRESS
*GatewayAddress
462 LIST_ENTRY
*ListHead
;
464 IP6_ROUTE_ENTRY
*Route
;
466 ListHead
= &RtTable
->RouteArea
[PrefixLength
];
469 // First check whether the route exists
471 NET_LIST_FOR_EACH (Entry
, ListHead
) {
472 Route
= NET_LIST_USER_STRUCT (Entry
, IP6_ROUTE_ENTRY
, Link
);
474 if (NetIp6IsNetEqual (Destination
, &Route
->Destination
, PrefixLength
) &&
475 EFI_IP6_EQUAL (GatewayAddress
, &Route
->NextHop
)) {
476 return EFI_ACCESS_DENIED
;
481 // Create a route entry and insert it to the route area.
483 Route
= Ip6CreateRouteEntry (Destination
, PrefixLength
, GatewayAddress
);
486 return EFI_OUT_OF_RESOURCES
;
489 if (NetIp6IsUnspecifiedAddr (GatewayAddress
)) {
490 Route
->Flag
= IP6_DIRECT_ROUTE
;
493 InsertHeadList (ListHead
, &Route
->Link
);
500 Remove a route entry and all the route caches spawn from it.
501 It is the help function for EfiIp6Routes.
503 @param[in, out] RtTable The route table to remove the route from.
504 @param[in] Destination The destination network.
505 @param[in] PrefixLength The PrefixLength of the Destination.
506 @param[in] GatewayAddress The next hop address.
508 @retval EFI_SUCCESS The route entry was successfully removed.
509 @retval EFI_NOT_FOUND There is no route entry in the table with that
515 IN OUT IP6_ROUTE_TABLE
*RtTable
,
516 IN EFI_IPv6_ADDRESS
*Destination
,
517 IN UINT8 PrefixLength
,
518 IN EFI_IPv6_ADDRESS
*GatewayAddress
521 LIST_ENTRY
*ListHead
;
524 IP6_ROUTE_ENTRY
*Route
;
527 ListHead
= &RtTable
->RouteArea
[PrefixLength
];
528 TotalNum
= RtTable
->TotalNum
;
530 NET_LIST_FOR_EACH_SAFE (Entry
, Next
, ListHead
) {
531 Route
= NET_LIST_USER_STRUCT (Entry
, IP6_ROUTE_ENTRY
, Link
);
533 if (Destination
!= NULL
&& !NetIp6IsNetEqual (Destination
, &Route
->Destination
, PrefixLength
)) {
536 if (GatewayAddress
!= NULL
&& !EFI_IP6_EQUAL (GatewayAddress
, &Route
->NextHop
)) {
540 Ip6PurgeRouteCache (&RtTable
->Cache
, (UINTN
) Route
);
541 RemoveEntryList (Entry
);
542 Ip6FreeRouteEntry (Route
);
544 ASSERT (RtTable
->TotalNum
> 0);
548 return TotalNum
== RtTable
->TotalNum
? EFI_NOT_FOUND
: EFI_SUCCESS
;
552 Search the route table to route the packet. Return/create a route
553 cache if there is a route to the destination.
555 @param[in] IpSb The IP6 service data.
556 @param[in] Dest The destination address to search for.
557 @param[in] Src The source address to search for.
559 @return NULL if it failed to route the packet. Otherwise, a route cache
560 entry that can be used to route packets.
563 IP6_ROUTE_CACHE_ENTRY
*
565 IN IP6_SERVICE
*IpSb
,
566 IN EFI_IPv6_ADDRESS
*Dest
,
567 IN EFI_IPv6_ADDRESS
*Src
570 IP6_ROUTE_TABLE
*RtTable
;
571 LIST_ENTRY
*ListHead
;
572 IP6_ROUTE_CACHE_ENTRY
*RtCacheEntry
;
573 IP6_ROUTE_ENTRY
*RtEntry
;
574 EFI_IPv6_ADDRESS NextHop
;
577 RtTable
= IpSb
->RouteTable
;
579 ASSERT (RtTable
!= NULL
);
582 // Search the destination cache in IP6_ROUTE_TABLE.
584 Index
= IP6_ROUTE_CACHE_HASH (Dest
, Src
);
585 ListHead
= &RtTable
->Cache
.CacheBucket
[Index
];
587 RtCacheEntry
= Ip6FindRouteCache (RtTable
, Dest
, Src
);
590 // If found, promote the cache entry to the head of the hash bucket.
592 if (RtCacheEntry
!= NULL
) {
593 RemoveEntryList (&RtCacheEntry
->Link
);
594 InsertHeadList (ListHead
, &RtCacheEntry
->Link
);
599 // Search the route table for the most specific route
601 RtEntry
= Ip6FindRouteEntry (RtTable
, Dest
, NULL
);
602 if (RtEntry
== NULL
) {
607 // Found a route to the Dest, if it is a direct route, the packet
608 // will be send directly to the destination, such as for connected
609 // network. Otherwise, it is an indirect route, the packet will be
610 // send the next hop router.
612 if ((RtEntry
->Flag
& IP6_DIRECT_ROUTE
) == IP6_DIRECT_ROUTE
) {
613 IP6_COPY_ADDRESS (&NextHop
, Dest
);
615 IP6_COPY_ADDRESS (&NextHop
, &RtEntry
->NextHop
);
618 Ip6FreeRouteEntry (RtEntry
);
621 // Create a route cache entry, and tag it as spawned from this route entry
623 RtCacheEntry
= Ip6CreateRouteCacheEntry (Dest
, Src
, &NextHop
, (UINTN
) RtEntry
);
625 if (RtCacheEntry
== NULL
) {
629 InsertHeadList (ListHead
, &RtCacheEntry
->Link
);
630 NET_GET_REF (RtCacheEntry
);
631 RtTable
->Cache
.CacheNum
[Index
]++;