1 /** @file
2   The functions and routines to handle the route caches and route table.
3 
4   Copyright (c) 2009 - 2010, Intel Corporation. All rights reserved.<BR>
5 
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.
10 
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.
13 
14 **/
15 
16 #include "Ip6Impl.h"
17 
18 /**
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.
21 
22   @param[in]  Ip1     The IPv6 address.
23   @param[in]  Ip2     The IPv6 address.
24 
25   @return The hash value of the prefix of two IPv6 addresses.
26 
27 **/
28 UINT32
Ip6RouteCacheHash(IN EFI_IPv6_ADDRESS * Ip1,IN EFI_IPv6_ADDRESS * Ip2)29 Ip6RouteCacheHash (
30   IN EFI_IPv6_ADDRESS       *Ip1,
31   IN EFI_IPv6_ADDRESS       *Ip2
32   )
33 {
34   UINT32 Prefix1;
35   UINT32 Prefix2;
36 
37   Prefix1 = *((UINT32 *) ((UINTN *) (Ip1)));
38   Prefix2 = *((UINT32 *) ((UINTN *) (Ip2)));
39 
40   return ((UINT32) (Prefix1 ^ Prefix2) % IP6_ROUTE_CACHE_HASH_SIZE);
41 }
42 
43 /**
44   Allocate a route entry then initialize it with the Destination/PrefixLength
45   and Gateway.
46 
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
51                               that may be NULL.
52 
53   @return NULL if failed to allocate memeory; otherwise, the newly created route entry.
54 
55 **/
56 IP6_ROUTE_ENTRY *
Ip6CreateRouteEntry(IN EFI_IPv6_ADDRESS * Destination OPTIONAL,IN UINT8 PrefixLength,IN EFI_IPv6_ADDRESS * GatewayAddress OPTIONAL)57 Ip6CreateRouteEntry (
58   IN EFI_IPv6_ADDRESS       *Destination    OPTIONAL,
59   IN UINT8                  PrefixLength,
60   IN EFI_IPv6_ADDRESS       *GatewayAddress OPTIONAL
61   )
62 {
63   IP6_ROUTE_ENTRY           *RtEntry;
64 
65   RtEntry = AllocateZeroPool (sizeof (IP6_ROUTE_ENTRY));
66 
67   if (RtEntry == NULL) {
68     return NULL;
69   }
70 
71   RtEntry->RefCnt       = 1;
72   RtEntry->Flag         = 0;
73   RtEntry->PrefixLength = PrefixLength;
74 
75   if (Destination != NULL) {
76     IP6_COPY_ADDRESS (&RtEntry->Destination, Destination);
77   }
78 
79   if (GatewayAddress != NULL) {
80     IP6_COPY_ADDRESS (&RtEntry->NextHop, GatewayAddress);
81   }
82 
83   return RtEntry;
84 }
85 
86 /**
87   Free the route table entry. It is reference counted.
88 
89   @param[in, out]  RtEntry  The route entry to free.
90 
91 **/
92 VOID
Ip6FreeRouteEntry(IN OUT IP6_ROUTE_ENTRY * RtEntry)93 Ip6FreeRouteEntry (
94   IN OUT IP6_ROUTE_ENTRY    *RtEntry
95   )
96 {
97   ASSERT ((RtEntry != NULL) && (RtEntry->RefCnt > 0));
98 
99   if (--RtEntry->RefCnt == 0) {
100     FreePool (RtEntry);
101   }
102 }
103 
104 /**
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
109   requirements:
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.
112 
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
117                             by Destination.
118 
119   @return NULL if no route matches the Dst. Otherwise, the point to the
120   @return most specific route to the Dst.
121 
122 **/
123 IP6_ROUTE_ENTRY *
Ip6FindRouteEntry(IN IP6_ROUTE_TABLE * RtTable,IN EFI_IPv6_ADDRESS * Destination OPTIONAL,IN EFI_IPv6_ADDRESS * NextHop OPTIONAL)124 Ip6FindRouteEntry (
125   IN IP6_ROUTE_TABLE        *RtTable,
126   IN EFI_IPv6_ADDRESS       *Destination OPTIONAL,
127   IN EFI_IPv6_ADDRESS       *NextHop     OPTIONAL
128   )
129 {
130   LIST_ENTRY                *Entry;
131   IP6_ROUTE_ENTRY           *RtEntry;
132   INTN                      Index;
133 
134   ASSERT (Destination != NULL || NextHop != NULL);
135 
136   RtEntry = NULL;
137 
138   for (Index = IP6_PREFIX_NUM - 1; Index >= 0; Index--) {
139     NET_LIST_FOR_EACH (Entry, &RtTable->RouteArea[Index]) {
140       RtEntry = NET_LIST_USER_STRUCT (Entry, IP6_ROUTE_ENTRY, Link);
141 
142       if (Destination != NULL) {
143         if (NetIp6IsNetEqual (Destination, &RtEntry->Destination, RtEntry->PrefixLength)) {
144           NET_GET_REF (RtEntry);
145           return RtEntry;
146         }
147       } else if (NextHop != NULL) {
148         if (NetIp6IsNetEqual (NextHop, &RtEntry->NextHop, RtEntry->PrefixLength)) {
149           NET_GET_REF (RtEntry);
150           return RtEntry;
151         }
152       }
153 
154     }
155   }
156 
157   return NULL;
158 }
159 
160 /**
161   Allocate and initialize a IP6 route cache entry.
162 
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.
168 
169   @return NULL if failed to allocate memory for the cache. Otherwise, point
170           to the created route cache entry.
171 
172 **/
173 IP6_ROUTE_CACHE_ENTRY *
Ip6CreateRouteCacheEntry(IN EFI_IPv6_ADDRESS * Dst,IN EFI_IPv6_ADDRESS * Src,IN EFI_IPv6_ADDRESS * GateWay,IN UINTN Tag)174 Ip6CreateRouteCacheEntry (
175   IN EFI_IPv6_ADDRESS       *Dst,
176   IN EFI_IPv6_ADDRESS       *Src,
177   IN EFI_IPv6_ADDRESS       *GateWay,
178   IN UINTN                  Tag
179   )
180 {
181   IP6_ROUTE_CACHE_ENTRY     *RtCacheEntry;
182 
183   RtCacheEntry = AllocatePool (sizeof (IP6_ROUTE_CACHE_ENTRY));
184 
185   if (RtCacheEntry == NULL) {
186     return NULL;
187   }
188 
189   RtCacheEntry->RefCnt = 1;
190   RtCacheEntry->Tag    = Tag;
191 
192   IP6_COPY_ADDRESS (&RtCacheEntry->Destination, Dst);
193   IP6_COPY_ADDRESS (&RtCacheEntry->Source, Src);
194   IP6_COPY_ADDRESS (&RtCacheEntry->NextHop, GateWay);
195 
196   return RtCacheEntry;
197 }
198 
199 /**
200   Free the route cache entry. It is reference counted.
201 
202   @param[in, out]  RtCacheEntry  The route cache entry to free.
203 
204 **/
205 VOID
Ip6FreeRouteCacheEntry(IN OUT IP6_ROUTE_CACHE_ENTRY * RtCacheEntry)206 Ip6FreeRouteCacheEntry (
207   IN OUT IP6_ROUTE_CACHE_ENTRY  *RtCacheEntry
208   )
209 {
210   ASSERT (RtCacheEntry->RefCnt > 0);
211 
212   if (--RtCacheEntry->RefCnt == 0) {
213     FreePool (RtCacheEntry);
214   }
215 }
216 
217 /**
218   Find a route cache with the destination and source address. This is
219   used by the ICMPv6 redirect messasge process.
220 
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.
224 
225   @return NULL if no route entry to the (Dest, Src). Otherwise, the pointer
226           to the correct route cache entry.
227 
228 **/
229 IP6_ROUTE_CACHE_ENTRY *
Ip6FindRouteCache(IN IP6_ROUTE_TABLE * RtTable,IN EFI_IPv6_ADDRESS * Dest,IN EFI_IPv6_ADDRESS * Src)230 Ip6FindRouteCache (
231   IN IP6_ROUTE_TABLE        *RtTable,
232   IN EFI_IPv6_ADDRESS       *Dest,
233   IN EFI_IPv6_ADDRESS       *Src
234   )
235 {
236   LIST_ENTRY                *Entry;
237   IP6_ROUTE_CACHE_ENTRY     *RtCacheEntry;
238   UINT32                    Index;
239 
240   Index = IP6_ROUTE_CACHE_HASH (Dest, Src);
241 
242   NET_LIST_FOR_EACH (Entry, &RtTable->Cache.CacheBucket[Index]) {
243     RtCacheEntry = NET_LIST_USER_STRUCT (Entry, IP6_ROUTE_CACHE_ENTRY, Link);
244 
245     if (EFI_IP6_EQUAL (Dest, &RtCacheEntry->Destination)&& EFI_IP6_EQUAL (Src, &RtCacheEntry->Source)) {
246       NET_GET_REF (RtCacheEntry);
247       return RtCacheEntry;
248     }
249   }
250 
251   return NULL;
252 }
253 
254 /**
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.
257 
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.
262 
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.
265 
266 **/
267 EFI_STATUS
Ip6BuildEfiRouteTable(IN IP6_ROUTE_TABLE * RouteTable,OUT UINT32 * EfiRouteCount,OUT EFI_IP6_ROUTE_TABLE ** EfiRouteTable OPTIONAL)268 Ip6BuildEfiRouteTable (
269   IN IP6_ROUTE_TABLE        *RouteTable,
270   OUT UINT32                *EfiRouteCount,
271   OUT EFI_IP6_ROUTE_TABLE   **EfiRouteTable OPTIONAL
272   )
273 {
274   LIST_ENTRY                *Entry;
275   IP6_ROUTE_ENTRY           *RtEntry;
276   EFI_IP6_ROUTE_TABLE       *EfiTable;
277   UINT32                    Count;
278   INT32                     Index;
279 
280   ASSERT (EfiRouteCount != NULL);
281 
282   Count          = RouteTable->TotalNum;
283   *EfiRouteCount = Count;
284 
285   if ((EfiRouteTable == NULL) || (Count == 0)) {
286     return EFI_SUCCESS;
287   }
288 
289   if (*EfiRouteTable == NULL) {
290     *EfiRouteTable = AllocatePool (sizeof (EFI_IP6_ROUTE_TABLE) * Count);
291     if (*EfiRouteTable == NULL) {
292       return EFI_OUT_OF_RESOURCES;
293     }
294   }
295 
296   EfiTable = *EfiRouteTable;
297 
298   //
299   // Copy the route entry to EFI route table.
300   //
301   Count = 0;
302 
303   for (Index = IP6_PREFIX_NUM - 1; Index >= 0; Index--) {
304 
305     NET_LIST_FOR_EACH (Entry, &(RouteTable->RouteArea[Index])) {
306       RtEntry = NET_LIST_USER_STRUCT (Entry, IP6_ROUTE_ENTRY, Link);
307 
308       Ip6CopyAddressByPrefix (
309         &EfiTable[Count].Destination,
310         &RtEntry->Destination,
311         RtEntry->PrefixLength
312         );
313 
314       IP6_COPY_ADDRESS (&EfiTable[Count].Gateway, &RtEntry->NextHop);
315       EfiTable[Count].PrefixLength = RtEntry->PrefixLength;
316 
317       Count++;
318     }
319   }
320 
321   ASSERT (Count == RouteTable->TotalNum);
322 
323   return EFI_SUCCESS;
324 }
325 
326 /**
327   Create an empty route table. This includes its internal route cache.
328 
329   @return NULL if failed to allocate memory for the route table. Otherwise,
330           the point to newly created route table.
331 
332 **/
333 IP6_ROUTE_TABLE *
Ip6CreateRouteTable(VOID)334 Ip6CreateRouteTable (
335   VOID
336   )
337 {
338   IP6_ROUTE_TABLE           *RtTable;
339   UINT32                    Index;
340 
341   RtTable = AllocatePool (sizeof (IP6_ROUTE_TABLE));
342   if (RtTable == NULL) {
343     return NULL;
344   }
345 
346   RtTable->RefCnt   = 1;
347   RtTable->TotalNum = 0;
348 
349   for (Index = 0; Index < IP6_PREFIX_NUM; Index++) {
350     InitializeListHead (&RtTable->RouteArea[Index]);
351   }
352 
353   for (Index = 0; Index < IP6_ROUTE_CACHE_HASH_SIZE; Index++) {
354     InitializeListHead (&RtTable->Cache.CacheBucket[Index]);
355     RtTable->Cache.CacheNum[Index] = 0;
356   }
357 
358   return RtTable;
359 }
360 
361 /**
362   Free the route table and its associated route cache. Route
363   table is reference counted.
364 
365   @param[in, out]  RtTable      The route table to free.
366 
367 **/
368 VOID
Ip6CleanRouteTable(IN OUT IP6_ROUTE_TABLE * RtTable)369 Ip6CleanRouteTable (
370   IN OUT IP6_ROUTE_TABLE        *RtTable
371   )
372 {
373   LIST_ENTRY                *Entry;
374   LIST_ENTRY                *Next;
375   IP6_ROUTE_ENTRY           *RtEntry;
376   IP6_ROUTE_CACHE_ENTRY     *RtCacheEntry;
377   UINT32                    Index;
378 
379   ASSERT (RtTable->RefCnt > 0);
380 
381   if (--RtTable->RefCnt > 0) {
382     return ;
383   }
384 
385   //
386   // Free all the route table entry and its route cache.
387   //
388   for (Index = 0; Index < IP6_PREFIX_NUM; 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);
393     }
394   }
395 
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);
401     }
402   }
403 
404   FreePool (RtTable);
405 }
406 
407 /**
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.
412 
413   @param[in]  RtCache       Route cache to remove the entries from.
414   @param[in]  Tag           The Tag of the entries to remove.
415 
416 **/
417 VOID
Ip6PurgeRouteCache(IN IP6_ROUTE_CACHE * RtCache,IN UINTN Tag)418 Ip6PurgeRouteCache (
419   IN IP6_ROUTE_CACHE        *RtCache,
420   IN UINTN                  Tag
421   )
422 {
423   LIST_ENTRY                *Entry;
424   LIST_ENTRY                *Next;
425   IP6_ROUTE_CACHE_ENTRY     *RtCacheEntry;
426   UINT32                    Index;
427 
428   for (Index = 0; Index < IP6_ROUTE_CACHE_HASH_SIZE; Index++) {
429     NET_LIST_FOR_EACH_SAFE (Entry, Next, &RtCache->CacheBucket[Index]) {
430 
431       RtCacheEntry = NET_LIST_USER_STRUCT (Entry, IP6_ROUTE_CACHE_ENTRY, Link);
432 
433       if (RtCacheEntry->Tag == Tag) {
434         RemoveEntryList (Entry);
435         Ip6FreeRouteCacheEntry (RtCacheEntry);
436       }
437     }
438   }
439 }
440 
441 /**
442   Add a route entry to the route table. It is the help function for EfiIp6Routes.
443 
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.
448 
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.
452 
453 **/
454 EFI_STATUS
Ip6AddRoute(IN OUT IP6_ROUTE_TABLE * RtTable,IN EFI_IPv6_ADDRESS * Destination,IN UINT8 PrefixLength,IN EFI_IPv6_ADDRESS * GatewayAddress)455 Ip6AddRoute (
456   IN OUT IP6_ROUTE_TABLE    *RtTable,
457   IN EFI_IPv6_ADDRESS       *Destination,
458   IN UINT8                  PrefixLength,
459   IN EFI_IPv6_ADDRESS       *GatewayAddress
460   )
461 {
462   LIST_ENTRY                *ListHead;
463   LIST_ENTRY                *Entry;
464   IP6_ROUTE_ENTRY           *Route;
465 
466   ListHead = &RtTable->RouteArea[PrefixLength];
467 
468   //
469   // First check whether the route exists
470   //
471   NET_LIST_FOR_EACH (Entry, ListHead) {
472     Route = NET_LIST_USER_STRUCT (Entry, IP6_ROUTE_ENTRY, Link);
473 
474     if (NetIp6IsNetEqual (Destination, &Route->Destination, PrefixLength) &&
475         EFI_IP6_EQUAL (GatewayAddress, &Route->NextHop)) {
476       return EFI_ACCESS_DENIED;
477     }
478   }
479 
480   //
481   // Create a route entry and insert it to the route area.
482   //
483   Route = Ip6CreateRouteEntry (Destination, PrefixLength, GatewayAddress);
484 
485   if (Route == NULL) {
486     return EFI_OUT_OF_RESOURCES;
487   }
488 
489   if (NetIp6IsUnspecifiedAddr (GatewayAddress)) {
490     Route->Flag = IP6_DIRECT_ROUTE;
491   }
492 
493   InsertHeadList (ListHead, &Route->Link);
494   RtTable->TotalNum++;
495 
496   return EFI_SUCCESS;
497 }
498 
499 /**
500   Remove a route entry and all the route caches spawn from it.
501   It is the help function for EfiIp6Routes.
502 
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.
507 
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
510                                 property.
511 
512 **/
513 EFI_STATUS
Ip6DelRoute(IN OUT IP6_ROUTE_TABLE * RtTable,IN EFI_IPv6_ADDRESS * Destination,IN UINT8 PrefixLength,IN EFI_IPv6_ADDRESS * GatewayAddress)514 Ip6DelRoute (
515   IN OUT IP6_ROUTE_TABLE    *RtTable,
516   IN EFI_IPv6_ADDRESS       *Destination,
517   IN UINT8                  PrefixLength,
518   IN EFI_IPv6_ADDRESS       *GatewayAddress
519   )
520 {
521   LIST_ENTRY                *ListHead;
522   LIST_ENTRY                *Entry;
523   LIST_ENTRY                *Next;
524   IP6_ROUTE_ENTRY           *Route;
525   UINT32                    TotalNum;
526 
527   ListHead = &RtTable->RouteArea[PrefixLength];
528   TotalNum = RtTable->TotalNum;
529 
530   NET_LIST_FOR_EACH_SAFE (Entry, Next, ListHead) {
531     Route = NET_LIST_USER_STRUCT (Entry, IP6_ROUTE_ENTRY, Link);
532 
533     if (Destination != NULL && !NetIp6IsNetEqual (Destination, &Route->Destination, PrefixLength)) {
534       continue;
535     }
536     if (GatewayAddress != NULL && !EFI_IP6_EQUAL (GatewayAddress, &Route->NextHop)) {
537       continue;
538     }
539 
540     Ip6PurgeRouteCache (&RtTable->Cache, (UINTN) Route);
541     RemoveEntryList (Entry);
542     Ip6FreeRouteEntry (Route);
543 
544     ASSERT (RtTable->TotalNum > 0);
545     RtTable->TotalNum--;
546   }
547 
548   return TotalNum == RtTable->TotalNum ? EFI_NOT_FOUND : EFI_SUCCESS;
549 }
550 
551 /**
552   Search the route table to route the packet. Return/create a route
553   cache if there is a route to the destination.
554 
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.
558 
559   @return NULL if it failed to route the packet. Otherwise, a route cache
560           entry that can be used to route packets.
561 
562 **/
563 IP6_ROUTE_CACHE_ENTRY *
Ip6Route(IN IP6_SERVICE * IpSb,IN EFI_IPv6_ADDRESS * Dest,IN EFI_IPv6_ADDRESS * Src)564 Ip6Route (
565   IN IP6_SERVICE            *IpSb,
566   IN EFI_IPv6_ADDRESS       *Dest,
567   IN EFI_IPv6_ADDRESS       *Src
568   )
569 {
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;
575   UINT32                    Index;
576 
577   RtTable = IpSb->RouteTable;
578 
579   ASSERT (RtTable != NULL);
580 
581   //
582   // Search the destination cache in IP6_ROUTE_TABLE.
583   //
584   Index    = IP6_ROUTE_CACHE_HASH (Dest, Src);
585   ListHead = &RtTable->Cache.CacheBucket[Index];
586 
587   RtCacheEntry = Ip6FindRouteCache (RtTable, Dest, Src);
588 
589   //
590   // If found, promote the cache entry to the head of the hash bucket.
591   //
592   if (RtCacheEntry != NULL) {
593     RemoveEntryList (&RtCacheEntry->Link);
594     InsertHeadList (ListHead, &RtCacheEntry->Link);
595     return RtCacheEntry;
596   }
597 
598   //
599   // Search the route table for the most specific route
600   //
601   RtEntry = Ip6FindRouteEntry (RtTable, Dest, NULL);
602   if (RtEntry == NULL) {
603     return NULL;
604   }
605 
606   //
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.
611   //
612   if ((RtEntry->Flag & IP6_DIRECT_ROUTE) == IP6_DIRECT_ROUTE) {
613     IP6_COPY_ADDRESS (&NextHop, Dest);
614   } else {
615     IP6_COPY_ADDRESS (&NextHop, &RtEntry->NextHop);
616   }
617 
618   Ip6FreeRouteEntry (RtEntry);
619 
620   //
621   // Create a route cache entry, and tag it as spawned from this route entry
622   //
623   RtCacheEntry = Ip6CreateRouteCacheEntry (Dest, Src, &NextHop, (UINTN) RtEntry);
624 
625   if (RtCacheEntry == NULL) {
626     return NULL;
627   }
628 
629   InsertHeadList (ListHead, &RtCacheEntry->Link);
630   NET_GET_REF (RtCacheEntry);
631   RtTable->Cache.CacheNum[Index]++;
632 
633   return RtCacheEntry;
634 }
635 
636