- Removed prefix.c and the prefix list. Adapter and route netmasks are now
[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 InvalidateNCEOnSubtree(
297 PNEIGHBOR_CACHE_ENTRY NCE,
298 PROUTE_CACHE_NODE Node)
299 /*
300 * FUNCTION: Removes all RCNs with references to an NCE on a subtree
301 * ARGUMENNTS:
302 * NCE = Pointer to NCE 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. NCE (0x%X) Node (0x%X).\n", NCE, Node));
309
310 if (IsInternalRCN(Node)) {
311 /* Traverse left subtree */
312 InvalidateNCEOnSubtree(NCE, Node->Left);
313
314 /* Traverse right subtree */
315 InvalidateNCEOnSubtree(NCE, Node->Right);
316
317 /* Finally check the node itself */
318 if (Node->NCE == NCE)
319 RemoveRouteToDestination(Node);
320 }
321 }
322
323
324 VOID RemoveSubtree(
325 PROUTE_CACHE_NODE Node)
326 /*
327 * FUNCTION: Removes a subtree from the tree using recursion
328 * ARGUMENNTS:
329 * Node = Pointer to RCN to start removing nodes at
330 * NOTES:
331 * This function must be called with the route cache lock held
332 */
333 {
334 TI_DbgPrint(DEBUG_RCACHE, ("Called. Node (0x%X).\n", Node));
335
336 if (IsInternalRCN(Node)) {
337 /* Traverse left subtree */
338 RemoveSubtree(Node->Left);
339
340 /* Traverse right subtree */
341 RemoveSubtree(Node->Right);
342 }
343 }
344
345
346 NTSTATUS RouteStartup(
347 VOID)
348 /*
349 * FUNCTION: Initializes the routing subsystem
350 * RETURNS:
351 * Status of operation
352 */
353 {
354 TI_DbgPrint(DEBUG_RCACHE, ("Called.\n"));
355
356 ExInitializeNPagedLookasideList(
357 &IPRCNList, /* Lookaside list */
358 NULL, /* Allocate routine */
359 NULL, /* Free routine */
360 0, /* Flags */
361 sizeof(ROUTE_CACHE_NODE), /* Size of each entry */
362 TAG('I','P','R','C'), /* Tag */
363 0); /* Depth */
364
365 /* Initialize the pseudo external route cache node */
366 ExternalRCN = ExAllocateFromNPagedLookasideList(&IPRCNList);
367 if (!ExternalRCN) {
368 TI_DbgPrint(MIN_TRACE, ("Insufficient resources.\n"));
369 return STATUS_INSUFFICIENT_RESOURCES;
370 }
371 INIT_TAG(ExternalRCN, TAG('R','C','N',' '));
372
373 ExternalRCN->Free = FreeRCN;
374 ExternalRCN->Parent = NULL;
375 ExternalRCN->Left = NULL;
376 ExternalRCN->Right = NULL;
377
378 /* Initialize the route cache root */
379 RouteCache = ExternalRCN;
380
381 KeInitializeSpinLock(&RouteCacheLock);
382
383 #if 0
384 TI_DbgPrint(MIN_TRACE, ("Displaying tree.\n"));
385 PrintTree(RouteCache);
386 #endif
387 return STATUS_SUCCESS;
388 }
389
390
391 NTSTATUS RouteShutdown(
392 VOID)
393 /*
394 * FUNCTION: Shuts down the routing subsystem
395 * RETURNS:
396 * Status of operation
397 */
398 {
399 KIRQL OldIrql;
400
401 TI_DbgPrint(DEBUG_RCACHE, ("Called.\n"));
402
403 TcpipAcquireSpinLock(&RouteCacheLock, &OldIrql);
404 #if 0
405 TI_DbgPrint(MIN_TRACE, ("Displaying tree.\n"));
406 PrintTree(RouteCache);
407 #endif
408 /* Clear route cache */
409 RemoveSubtree(RouteCache);
410
411 FreeRCN(ExternalRCN);
412
413 TcpipReleaseSpinLock(&RouteCacheLock, OldIrql);
414
415 ExDeleteNPagedLookasideList(&IPRCNList);
416
417 return STATUS_SUCCESS;
418 }
419
420
421 UINT RouteGetRouteToDestination
422 (PIP_ADDRESS Destination, PROUTE_CACHE_NODE *RCN)
423 /*
424 * FUNCTION: Locates an RCN describing a route to a destination address
425 * ARGUMENTS:
426 * Destination = Pointer to destination address to find route to
427 * RCN = Address of pointer to an RCN
428 * RETURNS:
429 * Status of operation
430 * NOTES:
431 * The RCN is referenced for the caller. The caller is responsible
432 * for dereferencing it after use
433 */
434 {
435 KIRQL OldIrql;
436 PROUTE_CACHE_NODE RCN2;
437 PNEIGHBOR_CACHE_ENTRY NCE;
438 PIP_INTERFACE Interface;
439
440 TI_DbgPrint(DEBUG_RCACHE, ("Called. Destination (0x%X)\n", Destination));
441
442 TI_DbgPrint(DEBUG_RCACHE, ("Destination (%s)\n", A2S(Destination)));
443
444 TcpipAcquireSpinLock(&RouteCacheLock, &OldIrql);
445
446 #if 0
447 TI_DbgPrint(MIN_TRACE, ("Displaying tree (before).\n"));
448 PrintTree(RouteCache);
449 #endif
450
451 ExternalRCN->Left = NULL;
452 RCN2 = SearchRouteCache(Destination, RouteCache);
453 if (IsExternalRCN(RCN2)) {
454 /* No route was found in the cache */
455
456 /* Check if the destination is on-link */
457 Interface = FindOnLinkInterface(Destination);
458 if (Interface) {
459 /* The destination address is on-link. Check our neighbor cache */
460 NCE = NBFindOrCreateNeighbor(Interface, Destination);
461 if (!NCE) {
462 TcpipReleaseSpinLock(&RouteCacheLock, OldIrql);
463 return IP_NO_RESOURCES;
464 }
465 } else {
466 /* Destination is not on any subnets we're on. Find a router to use */
467 NCE = RouterGetRoute(Destination);
468 if (!NCE) {
469 /* We cannot get to the specified destination. Return error */
470 TcpipReleaseSpinLock(&RouteCacheLock, OldIrql);
471 return IP_NO_ROUTE_TO_DESTINATION;
472 }
473 }
474
475 /* Add the new route to the route cache */
476 if (RCN2 == RouteCache) {
477 RCN2 = ExpandExternalRCN();
478 RouteCache = RCN2;
479 } else
480 RCN2 = ExpandExternalRCN();
481 if (!RCN2) {
482 TcpipReleaseSpinLock(&RouteCacheLock, OldIrql);
483 return IP_NO_RESOURCES;
484 }
485
486 RCN2->State = RCN_STATE_COMPUTED;
487 RtlCopyMemory(&RCN2->Destination, Destination, sizeof(IP_ADDRESS));
488 RCN2->PathMTU = NCE->Interface->MTU;
489 RCN2->NCE = NCE;
490
491 /* The route cache node references the NTE and the NCE. The
492 NTE was referenced before and NCE is already referenced by
493 RouteGetRoute() or NBFindOrCreateNeighbor() so we don't
494 reference them here */
495 }
496
497 TcpipReleaseSpinLock(&RouteCacheLock, OldIrql);
498
499 *RCN = RCN2;
500 TI_DbgPrint(MID_TRACE,("RCN->PathMTU: %d\n", RCN2->PathMTU));
501
502 return IP_SUCCESS;
503 }
504
505
506 PROUTE_CACHE_NODE RouteAddRouteToDestination(
507 PIP_ADDRESS Destination,
508 PIP_INTERFACE IF,
509 PNEIGHBOR_CACHE_ENTRY NCE)
510 /*
511 * FUNCTION: Adds a (permanent) route to a destination
512 * ARGUMENTS:
513 * Destination = Pointer to destination address
514 * IF = Pointer to interface to use
515 * NCE = Pointer to first hop to destination
516 * RETURNS:
517 * Pointer to RCN if the route was added, NULL if not.
518 * There can be at most one RCN per destination address / interface pair
519 */
520 {
521 KIRQL OldIrql;
522 PROUTE_CACHE_NODE RCN;
523
524 TI_DbgPrint(DEBUG_RCACHE, ("Called. Destination (0x%X) IF (0x%X) NCE (0x%X).\n",
525 Destination, IF, NCE));
526
527 TI_DbgPrint(DEBUG_RCACHE, ("Destination (%s) NCE (%s).\n",
528 A2S(Destination),
529 A2S(&NCE->Address)));
530
531 TcpipAcquireSpinLock(&RouteCacheLock, &OldIrql);
532
533 /* Locate an external RCN we can expand */
534 RCN = RouteCache;
535 ExternalRCN->Left = NULL;
536 for (;;) {
537 RCN = SearchRouteCache(Destination, RCN);
538 if (IsInternalRCN(RCN)) {
539 ExternalRCN->Left = (PROUTE_CACHE_NODE)&RCN->Right;
540 /* This is an internal node, continue the search to the right */
541 RCN = RCN->Right;
542 } else
543 /* This is an external node, we've found an empty spot */
544 break;
545 }
546
547 /* Expand the external node */
548 if (RCN == RouteCache) {
549 RCN = ExpandExternalRCN();
550 RouteCache = RCN;
551 } else
552 RCN = ExpandExternalRCN();
553 if (!RCN) {
554 TcpipReleaseSpinLock(&RouteCacheLock, OldIrql);
555 return NULL;
556 }
557
558 /* Initialize the newly created internal node */
559
560 INIT_TAG(RCN, TAG('R','C','N',' '));
561
562 /* Reference once for beeing alive */
563 RCN->State = RCN_STATE_PERMANENT;
564 RtlCopyMemory(&RCN->Destination, Destination, sizeof(IP_ADDRESS));
565 RCN->PathMTU = IF->MTU;
566 RCN->NCE = NCE;
567
568 TcpipReleaseSpinLock(&RouteCacheLock, OldIrql);
569
570 return RCN;
571 }
572
573
574 VOID RouteRemoveRouteToDestination(
575 PROUTE_CACHE_NODE RCN)
576 /*
577 * FUNCTION: Removes a route to a destination
578 * ARGUMENTS:
579 * RCN = Pointer to route cache node to remove
580 */
581 {
582 KIRQL OldIrql;
583
584 TI_DbgPrint(DEBUG_RCACHE, ("Called. RCN (0x%X).\n", RCN));
585
586 TcpipAcquireSpinLock(&RouteCacheLock, &OldIrql);
587
588 RemoveRouteToDestination(RCN);
589
590 TcpipReleaseSpinLock(&RouteCacheLock, OldIrql);
591 }
592
593 VOID RouteInvalidateNCE(
594 PNEIGHBOR_CACHE_ENTRY NCE)
595 /*
596 * FUNCTION: Removes all RCNs with references to an NCE
597 * ARGUMENTS:
598 * NCE = Pointer to neighbor cache entry to invalidate
599 */
600 {
601 KIRQL OldIrql;
602
603 TI_DbgPrint(DEBUG_RCACHE, ("Called. NCE (0x%X).\n", NCE));
604
605 TcpipAcquireSpinLock(&RouteCacheLock, &OldIrql);
606 InvalidateNCEOnSubtree(NCE, RouteCache);
607 TcpipReleaseSpinLock(&RouteCacheLock, OldIrql);
608 }
609
610 NTSTATUS
611 RouteFriendlyAddRoute( PIPROUTE_ENTRY ire ) {
612 KIRQL OldIrql;
613
614
615 /* Find IF */
616 TcpipAcquireSpinLock(&InterfaceListLock, &OldIrql);
617 //RouteAddRouteToDestination(&Dest,Nte,If,Nce);
618 TcpipReleaseSpinLock(&InterfaceListLock, OldIrql);
619
620 return STATUS_SUCCESS;
621 }
622
623 /* EOF */