00da1d8a5a83aced730be149138710b142565920
[reactos.git] / reactos / drivers / lib / ip / network / route.c
1 /*
2 * COPYRIGHT: See COPYING in the top level directory
3 * PROJECT: ReactOS TCP/IP protocol driver
4 * FILE: network/route.c
5 * PURPOSE: Route cache
6 * PROGRAMMERS: Casper S. Hornstrup (chorns@users.sourceforge.net)
7 * NOTES: The route cache is implemented as a binary search
8 * tree to obtain fast searches
9 *
10 * This data is not authoritative. It is a searchable cache that allows
11 * quick access to route information to selected hosts. This information
12 * should always defer to the FIB.
13 *
14 * REVISIONS:
15 * CSH 01/08-2000 Created
16 */
17
18 #include "precomp.h"
19
20
21 /* This RCN is shared by all external nodes. It complicates things,
22 but the memory requirements are reduced by approximately 50%.
23 The RCN is protected by the route cache spin lock */
24 PROUTE_CACHE_NODE ExternalRCN;
25 PROUTE_CACHE_NODE RouteCache;
26 KSPIN_LOCK RouteCacheLock;
27 NPAGED_LOOKASIDE_LIST IPRCNList;
28
29
30 #ifdef DBG
31 VOID PrintTree(
32 PROUTE_CACHE_NODE Node)
33 /*
34 * FUNCTION: Prints all nodes on tree
35 * ARGUMENTS:
36 * Node = Pointer to root node of tree
37 * NOTES:
38 * This function must be called with the route cache lock held.
39 */
40 {
41 if (IsInternalRCN(Node)) {
42 /* Traverse left subtree */
43 PrintTree(Node->Left);
44
45 /* Traverse right subtree */
46 PrintTree(Node->Right);
47
48 /* Finally check the node itself */
49 TI_DbgPrint(MIN_TRACE, ("(Internal) Self,Parent,Left,Right,Data = (%08X, %08X, %08X, %08X, %08X).\n",
50 Node, Node->Parent, Node->Left, Node->Right, (ULONG_PTR)Node->Destination.Address.IPv4Address));
51 } else
52 TI_DbgPrint(MIN_TRACE, ("(External) Self,Parent,Left,Right = (%08X, %08X, %08X, %08X).\n",
53 Node, Node->Parent, Node->Left, Node->Right));
54 }
55 #endif
56
57 UINT CountRouteNodes( PROUTE_CACHE_NODE Node ) {
58 if( !Node ) Node = RouteCache;
59 if( IsInternalRCN(Node) )
60 return
61 /* Traverse left subtree */
62 CountRouteNodes(Node->Left) +
63 /* Traverse right subtree */
64 CountRouteNodes(Node->Right) + 1;
65 else
66 return 0;
67 }
68
69 VOID FreeRCN(
70 PVOID Object)
71 /*
72 * FUNCTION: Frees an route cache node object
73 * ARGUMENTS:
74 * Object = Pointer to an route cache node structure
75 */
76 {
77 ExFreeToNPagedLookasideList(&IPRCNList, Object);
78 }
79
80
81 VOID RemoveAboveExternal(VOID)
82 /*
83 * FUNCTION: Removes the parent node of the selected external node from the route cache tree
84 * NOTES:
85 * This function must be called with the route cache lock held.
86 * ExternalRCN->Parent must be initialized
87 */
88 {
89 PROUTE_CACHE_NODE Parent;
90 PROUTE_CACHE_NODE Sibling;
91
92 TI_DbgPrint(DEBUG_RCACHE, ("Called.\n"));
93
94 #if 0
95 TI_DbgPrint(MIN_TRACE, ("Displaying tree (before).\n"));
96 PrintTree(RouteCache);
97 #endif
98
99 Parent = ExternalRCN->Parent;
100 /* Find sibling of external node */
101 if (ExternalRCN == Parent->Left)
102 Sibling = Parent->Right;
103 else
104 Sibling = Parent->Left;
105
106 /* Replace parent node with sibling of external node */
107 if (Parent != RouteCache) {
108 if (Parent->Parent->Left == Parent)
109 Parent->Parent->Left = Sibling;
110 else
111 Parent->Parent->Right = Sibling;
112 /* Give sibling a new parent */
113 Sibling->Parent = Parent->Parent;
114 } else {
115 /* This is the root we're removing */
116 RouteCache = Sibling;
117 Sibling->Parent = NULL;
118 }
119 }
120
121
122 PROUTE_CACHE_NODE SearchRouteCache(
123 PIP_ADDRESS Destination,
124 PROUTE_CACHE_NODE Node)
125 /*
126 * FUNCTION: Searches route cache for a RCN for a destination address
127 * ARGUMENTS:
128 * Destination = Pointer to destination address (key)
129 * Node = Pointer to start route cache node
130 * NOTES:
131 * This function must be called with the route cache lock held
132 * RETURNS:
133 * Pointer to internal node if a matching node was found, or
134 * external node where it should be if none was found
135 */
136 {
137 INT Value;
138
139 TI_DbgPrint(DEBUG_RCACHE, ("Called. Destination (0x%X) Node (0x%X)\n", Destination, Node));
140
141 /* Is this an external node? */
142 if (IsExternalRCN(Node))
143 return Node;
144
145 /* Is it this node we are looking for? */
146 Value = AddrCompare(Destination, &Node->Destination);
147 if (Value == 0)
148 return Node;
149
150 /* Traverse down the left subtree if the key is smaller than
151 the key of the node, otherwise traverse the right subtree */
152 if (Value < 0) {
153 Node->Left->Parent = Node;
154 ExternalRCN->Left = (PROUTE_CACHE_NODE)&Node->Left;
155 return SearchRouteCache(Destination, Node->Left);
156 } else {
157 Node->Right->Parent = Node;
158 ExternalRCN->Left = (PROUTE_CACHE_NODE)&Node->Right;
159 return SearchRouteCache(Destination, Node->Right);
160 }
161 }
162
163
164 PROUTE_CACHE_NODE ExpandExternalRCN(VOID)
165 /*
166 * FUNCTION: Expands an external route cache node
167 * NOTES:
168 * This function must be called with the route cache lock held.
169 * We cheat a little here to save memory. We don't actually allocate memory
170 * for external nodes. We wait until they're turned into internal nodes.
171 * ExternalRCN->Parent must be initialized
172 * ExternalRCN->Left must be a pointer to the correct child link of it's parent
173 * RETURNS:
174 * Pointer to new internal node if the external node was expanded, NULL if not
175 */
176 {
177 PROUTE_CACHE_NODE RCN;
178
179 MTMARK();
180
181 TI_DbgPrint(DEBUG_RCACHE, ("Called.\n"));
182
183 RCN = ExAllocateFromNPagedLookasideList(&IPRCNList);
184 if (!RCN) {
185 TI_DbgPrint(MIN_TRACE, ("Insufficient resources.\n"));
186 return NULL;
187 }
188
189 MTMARK();
190
191 RCN->Free = FreeRCN;
192
193 if (ExternalRCN->Left)
194 /* Register RCN as a child with it's parent */
195 *(PROUTE_CACHE_NODE*)ExternalRCN->Left = RCN;
196
197 RCN->Parent = ExternalRCN->Parent;
198 RCN->Left = ExternalRCN;
199 RCN->Right = ExternalRCN;
200
201 MTMARK();
202
203 return RCN;
204 }
205
206 #if 0
207 VOID SwapRCN(
208 PROUTE_CACHE_NODE *Node1,
209 PROUTE_CACHE_NODE *Node2)
210 /*
211 * FUNCTION: Swaps two nodes
212 * ARGUMENTS:
213 * Node1 = Address of pointer to first node
214 * Node2 = Address of pointer to second node
215 */
216 {
217 PROUTE_CACHE_NODE Temp;
218
219 Temp = *Node2;
220 *Node2 = *Node1;
221 *Node1 = Temp;
222 }
223 #endif
224
225 /*
226 * FUNCTION: Removes a route to a destination
227 * ARGUMENTS:
228 * RCN = Pointer to route cache node to remove
229 * NOTES:
230 * Internal version. Route cache lock must be held
231 */
232 VOID RemoveRouteToDestination(
233 PROUTE_CACHE_NODE RCN)
234 {
235 PROUTE_CACHE_NODE RemNode, Parent, SwapNode;
236
237 TI_DbgPrint(DEBUG_RCACHE, ("Called. RCN (0x%X).\n", RCN));
238
239 if (IsExternalRCN(RCN->Left)) {
240 /* Left node is external */
241 RemNode = RCN->Left;
242 RemNode->Parent = RCN;
243 } else if (IsExternalRCN(RCN->Right)) {
244 /* Right node is external */
245 RemNode = RCN->Right;
246 RemNode->Parent = RCN;
247 } else {
248 /* The node has internal children */
249
250 /* Normally we would replace the item of RCN with the item
251 of the leftmost external node on the right subtree of
252 RCN. This we cannot do here because there may be
253 references directly to that node. Instead we swap pointer
254 values (parent, left and right) of the two nodes */
255 RemNode = RCN->Right;
256 do {
257 Parent = RemNode;
258 RemNode = RemNode->Left;
259 } while (IsInternalRCN(RemNode));
260 RemNode->Parent = Parent;
261
262 SwapNode = RemNode->Parent;
263 #if 0
264 if (RCN != RouteCache) {
265 /* Set SwapNode to be child of RCN's parent instead of RCN */
266 Parent = RCN->Parent;
267 if (RCN == Parent->Left)
268 Parent->Left = SwapNode;
269 else
270 Parent->Right = SwapNode;
271 } else
272 /* SwapNode is the new cache root */
273 RouteCache = SwapNode;
274
275 /* Set RCN to be child of SwapNode's parent instead of SwapNode */
276 Parent = SwapNode->Parent;
277 if (SwapNode == Parent->Left)
278 Parent->Left = RCN;
279 else
280 Parent->Right = RCN;
281
282 /* Swap parents */
283 SwapRCN(&SwapNode->Parent, &RCN->Parent);
284 /* Swap children */
285 SwapRCN(&SwapNode->Left, &RCN->Left);
286 SwapRCN(&SwapNode->Right, &RCN->Right);
287 #endif
288 }
289
290 ExternalRCN->Parent = RemNode->Parent;
291
292 RemoveAboveExternal();
293 }
294
295
296 VOID InvalidateNTEOnSubtree(
297 PNET_TABLE_ENTRY NTE,
298 PROUTE_CACHE_NODE Node)
299 /*
300 * FUNCTION: Removes all RCNs with references to an NTE on a subtree
301 * ARGUMENNTS:
302 * NTE = Pointer to NTE to invalidate
303 * Node = Pointer to RCN to start removing nodes at
304 * NOTES:
305 * This function must be called with the route cache lock held.
306 */
307 {
308 TI_DbgPrint(DEBUG_RCACHE, ("Called. NTE (0x%X) Node (0x%X).\n", NTE, Node));
309
310 if (IsInternalRCN(Node)) {
311 /* Traverse left subtree */
312 InvalidateNTEOnSubtree(NTE, Node->Left);
313
314 /* Traverse right subtree */
315 InvalidateNTEOnSubtree(NTE, Node->Right);
316
317 /* Finally check the node itself */
318 if (Node->NTE == NTE)
319 RemoveRouteToDestination(Node);
320 }
321 }
322
323
324 VOID InvalidateNCEOnSubtree(
325 PNEIGHBOR_CACHE_ENTRY NCE,
326 PROUTE_CACHE_NODE Node)
327 /*
328 * FUNCTION: Removes all RCNs with references to an NCE on a subtree
329 * ARGUMENNTS:
330 * NCE = Pointer to NCE to invalidate
331 * Node = Pointer to RCN to start removing nodes at
332 * NOTES:
333 * This function must be called with the route cache lock held
334 */
335 {
336 TI_DbgPrint(DEBUG_RCACHE, ("Called. NCE (0x%X) Node (0x%X).\n", NCE, Node));
337
338 if (IsInternalRCN(Node)) {
339 /* Traverse left subtree */
340 InvalidateNCEOnSubtree(NCE, Node->Left);
341
342 /* Traverse right subtree */
343 InvalidateNCEOnSubtree(NCE, Node->Right);
344
345 /* Finally check the node itself */
346 if (Node->NCE == NCE)
347 RemoveRouteToDestination(Node);
348 }
349 }
350
351
352 VOID RemoveSubtree(
353 PROUTE_CACHE_NODE Node)
354 /*
355 * FUNCTION: Removes a subtree from the tree using recursion
356 * ARGUMENNTS:
357 * Node = Pointer to RCN to start removing nodes at
358 * NOTES:
359 * This function must be called with the route cache lock held
360 */
361 {
362 TI_DbgPrint(DEBUG_RCACHE, ("Called. Node (0x%X).\n", Node));
363
364 if (IsInternalRCN(Node)) {
365 /* Traverse left subtree */
366 RemoveSubtree(Node->Left);
367
368 /* Traverse right subtree */
369 RemoveSubtree(Node->Right);
370 }
371 }
372
373
374 NTSTATUS RouteStartup(
375 VOID)
376 /*
377 * FUNCTION: Initializes the routing subsystem
378 * RETURNS:
379 * Status of operation
380 */
381 {
382 TI_DbgPrint(DEBUG_RCACHE, ("Called.\n"));
383
384 ExInitializeNPagedLookasideList(
385 &IPRCNList, /* Lookaside list */
386 NULL, /* Allocate routine */
387 NULL, /* Free routine */
388 0, /* Flags */
389 sizeof(ROUTE_CACHE_NODE), /* Size of each entry */
390 TAG('I','P','R','C'), /* Tag */
391 0); /* Depth */
392
393 /* Initialize the pseudo external route cache node */
394 ExternalRCN = ExAllocateFromNPagedLookasideList(&IPRCNList);
395 if (!ExternalRCN) {
396 TI_DbgPrint(MIN_TRACE, ("Insufficient resources.\n"));
397 return STATUS_INSUFFICIENT_RESOURCES;
398 }
399 INIT_TAG(ExternalRCN, TAG('R','C','N',' '));
400
401 ExternalRCN->Free = FreeRCN;
402 ExternalRCN->Parent = NULL;
403 ExternalRCN->Left = NULL;
404 ExternalRCN->Right = NULL;
405
406 /* Initialize the route cache root */
407 RouteCache = ExternalRCN;
408
409 KeInitializeSpinLock(&RouteCacheLock);
410
411 #if 0
412 TI_DbgPrint(MIN_TRACE, ("Displaying tree.\n"));
413 PrintTree(RouteCache);
414 #endif
415 return STATUS_SUCCESS;
416 }
417
418
419 NTSTATUS RouteShutdown(
420 VOID)
421 /*
422 * FUNCTION: Shuts down the routing subsystem
423 * RETURNS:
424 * Status of operation
425 */
426 {
427 KIRQL OldIrql;
428
429 TI_DbgPrint(DEBUG_RCACHE, ("Called.\n"));
430
431 TcpipAcquireSpinLock(&RouteCacheLock, &OldIrql);
432 #if 0
433 TI_DbgPrint(MIN_TRACE, ("Displaying tree.\n"));
434 PrintTree(RouteCache);
435 #endif
436 /* Clear route cache */
437 RemoveSubtree(RouteCache);
438
439 FreeRCN(ExternalRCN);
440
441 TcpipReleaseSpinLock(&RouteCacheLock, OldIrql);
442
443 ExDeleteNPagedLookasideList(&IPRCNList);
444
445 return STATUS_SUCCESS;
446 }
447
448
449 UINT RouteGetRouteToDestination(
450 PIP_ADDRESS Destination,
451 PNET_TABLE_ENTRY NTE,
452 PROUTE_CACHE_NODE *RCN)
453 /*
454 * FUNCTION: Locates an RCN describing a route to a destination address
455 * ARGUMENTS:
456 * Destination = Pointer to destination address to find route to
457 * NTE = Pointer to NTE describing net to send on
458 * (NULL means routing module choose NTE to send on)
459 * RCN = Address of pointer to an RCN
460 * RETURNS:
461 * Status of operation
462 * NOTES:
463 * The RCN is referenced for the caller. The caller is responsible
464 * for dereferencing it after use
465 */
466 {
467 KIRQL OldIrql;
468 PROUTE_CACHE_NODE RCN2;
469 PNEIGHBOR_CACHE_ENTRY NCE;
470 PIP_INTERFACE Interface;
471
472 TI_DbgPrint(DEBUG_RCACHE, ("Called. Destination (0x%X) NTE (0x%X).\n",
473 Destination, NTE));
474
475 TI_DbgPrint(DEBUG_RCACHE, ("Destination (%s) NTE (%s).\n",
476 A2S(Destination), NTE ? A2S(NTE->Address) : ""));
477
478 TcpipAcquireSpinLock(&RouteCacheLock, &OldIrql);
479
480 #if 0
481 TI_DbgPrint(MIN_TRACE, ("Displaying tree (before).\n"));
482 PrintTree(RouteCache);
483 #endif
484
485 ExternalRCN->Left = NULL;
486 RCN2 = SearchRouteCache(Destination, RouteCache);
487 if (IsExternalRCN(RCN2)) {
488 /* No route was found in the cache */
489
490 /* Check if the destination is on-link */
491 Interface = RouterFindOnLinkInterface(Destination, NTE);
492 if (Interface) {
493 if (!NTE) {
494 NTE = RouterFindBestNTE(Interface, Destination);
495 if (!NTE) {
496 /* We cannot get to the specified destination. Return error */
497 TcpipReleaseSpinLock(&RouteCacheLock, OldIrql);
498 return IP_NO_ROUTE_TO_DESTINATION;
499 }
500 }
501
502 /* The destination address is on-link. Check our neighbor cache */
503 NCE = NBFindOrCreateNeighbor(Interface, Destination);
504 if (!NCE) {
505 TcpipReleaseSpinLock(&RouteCacheLock, OldIrql);
506 return IP_NO_RESOURCES;
507 }
508 } else {
509 /* Destination is not on any subnets we're on. Find a router to use */
510 NCE = RouterGetRoute(Destination, NTE);
511 if (!NCE) {
512 /* We cannot get to the specified destination. Return error */
513 TcpipReleaseSpinLock(&RouteCacheLock, OldIrql);
514 return IP_NO_ROUTE_TO_DESTINATION;
515 }
516 }
517
518 /* Add the new route to the route cache */
519 if (RCN2 == RouteCache) {
520 RCN2 = ExpandExternalRCN();
521 RouteCache = RCN2;
522 } else
523 RCN2 = ExpandExternalRCN();
524 if (!RCN2) {
525 TcpipReleaseSpinLock(&RouteCacheLock, OldIrql);
526 return IP_NO_RESOURCES;
527 }
528
529 RCN2->State = RCN_STATE_COMPUTED;
530 RCN2->NTE = NTE;
531 RtlCopyMemory(&RCN2->Destination, Destination, sizeof(IP_ADDRESS));
532 RCN2->PathMTU = NCE->Interface->MTU;
533 RCN2->NCE = NCE;
534
535 /* The route cache node references the NTE and the NCE. The
536 NTE was referenced before and NCE is already referenced by
537 RouteGetRoute() or NBFindOrCreateNeighbor() so we don't
538 reference them here */
539 }
540
541 TcpipReleaseSpinLock(&RouteCacheLock, OldIrql);
542
543 *RCN = RCN2;
544 TI_DbgPrint(MID_TRACE,("RCN->PathMTU: %d\n", RCN2->PathMTU));
545
546 return IP_SUCCESS;
547 }
548
549
550 PROUTE_CACHE_NODE RouteAddRouteToDestination(
551 PIP_ADDRESS Destination,
552 PNET_TABLE_ENTRY NTE,
553 PIP_INTERFACE IF,
554 PNEIGHBOR_CACHE_ENTRY NCE)
555 /*
556 * FUNCTION: Adds a (permanent) route to a destination
557 * ARGUMENTS:
558 * Destination = Pointer to destination address
559 * NTE = Pointer to net table entry
560 * IF = Pointer to interface to use
561 * NCE = Pointer to first hop to destination
562 * RETURNS:
563 * Pointer to RCN if the route was added, NULL if not.
564 * There can be at most one RCN per destination address / interface pair
565 */
566 {
567 KIRQL OldIrql;
568 PROUTE_CACHE_NODE RCN;
569
570 TI_DbgPrint(DEBUG_RCACHE, ("Called. Destination (0x%X) NTE (0x%X) IF (0x%X) NCE (0x%X).\n",
571 Destination, NTE, IF, NCE));
572
573 TI_DbgPrint(DEBUG_RCACHE, ("Destination (%s) NTE (%s) NCE (%s).\n",
574 A2S(Destination),
575 A2S(NTE->Address),
576 A2S(&NCE->Address)));
577
578 TcpipAcquireSpinLock(&RouteCacheLock, &OldIrql);
579
580 /* Locate an external RCN we can expand */
581 RCN = RouteCache;
582 ExternalRCN->Left = NULL;
583 for (;;) {
584 RCN = SearchRouteCache(Destination, RCN);
585 if (IsInternalRCN(RCN)) {
586 ExternalRCN->Left = (PROUTE_CACHE_NODE)&RCN->Right;
587 /* This is an internal node, continue the search to the right */
588 RCN = RCN->Right;
589 } else
590 /* This is an external node, we've found an empty spot */
591 break;
592 }
593
594 /* Expand the external node */
595 if (RCN == RouteCache) {
596 RCN = ExpandExternalRCN();
597 RouteCache = RCN;
598 } else
599 RCN = ExpandExternalRCN();
600 if (!RCN) {
601 TcpipReleaseSpinLock(&RouteCacheLock, OldIrql);
602 return NULL;
603 }
604
605 /* Initialize the newly created internal node */
606
607 INIT_TAG(RCN, TAG('R','C','N',' '));
608
609 /* Reference once for beeing alive */
610 RCN->State = RCN_STATE_PERMANENT;
611 RCN->NTE = NTE;
612 RtlCopyMemory(&RCN->Destination, Destination, sizeof(IP_ADDRESS));
613 RCN->PathMTU = IF->MTU;
614 RCN->NCE = NCE;
615
616 TcpipReleaseSpinLock(&RouteCacheLock, OldIrql);
617
618 return RCN;
619 }
620
621
622 VOID RouteRemoveRouteToDestination(
623 PROUTE_CACHE_NODE RCN)
624 /*
625 * FUNCTION: Removes a route to a destination
626 * ARGUMENTS:
627 * RCN = Pointer to route cache node to remove
628 */
629 {
630 KIRQL OldIrql;
631
632 TI_DbgPrint(DEBUG_RCACHE, ("Called. RCN (0x%X).\n", RCN));
633
634 TcpipAcquireSpinLock(&RouteCacheLock, &OldIrql);
635
636 RemoveRouteToDestination(RCN);
637
638 TcpipReleaseSpinLock(&RouteCacheLock, OldIrql);
639 }
640
641
642 VOID RouteInvalidateNTE(
643 PNET_TABLE_ENTRY NTE)
644 /*
645 * FUNCTION: Removes all RCNs with references to an NTE
646 * ARGUMENTS:
647 * NTE = Pointer to net table entry to invalidate
648 */
649 {
650 KIRQL OldIrql;
651
652 TI_DbgPrint(DEBUG_RCACHE, ("Called. NTE (0x%X).\n", NTE));
653
654 TcpipAcquireSpinLock(&RouteCacheLock, &OldIrql);
655 InvalidateNTEOnSubtree(NTE, RouteCache);
656 TcpipReleaseSpinLock(&RouteCacheLock, OldIrql);
657 }
658
659
660 VOID RouteInvalidateNCE(
661 PNEIGHBOR_CACHE_ENTRY NCE)
662 /*
663 * FUNCTION: Removes all RCNs with references to an NCE
664 * ARGUMENTS:
665 * NCE = Pointer to neighbor cache entry to invalidate
666 */
667 {
668 KIRQL OldIrql;
669
670 TI_DbgPrint(DEBUG_RCACHE, ("Called. NCE (0x%X).\n", NCE));
671
672 TcpipAcquireSpinLock(&RouteCacheLock, &OldIrql);
673 InvalidateNCEOnSubtree(NCE, RouteCache);
674 TcpipReleaseSpinLock(&RouteCacheLock, OldIrql);
675 }
676
677 NTSTATUS
678 RouteFriendlyAddRoute( PIPROUTE_ENTRY ire ) {
679 KIRQL OldIrql;
680
681
682 /* Find IF */
683 TcpipAcquireSpinLock(&InterfaceListLock, &OldIrql);
684 //RouteAddRouteToDestination(&Dest,Nte,If,Nce);
685 TcpipReleaseSpinLock(&InterfaceListLock, OldIrql);
686
687 return STATUS_SUCCESS;
688 }
689
690 /* EOF */