1 /*
2 * COPYRIGHT: See COPYING in the top level directory
3 * PROJECT: ReactOS TCP/IP protocol driver
4 * FILE: network/router.c
5 * PURPOSE: IP routing subsystem
6 * PROGRAMMERS: Casper S. Hornstrup (chorns@users.sourceforge.net)
7 * NOTES:
8 * This file holds authoritative routing information.
9 * Information queries on the route table should be handled here.
10 * This information should always override the route cache info.
11 * REVISIONS:
12 * CSH 01/08-2000 Created
13 */
14
15 #include "precomp.h"
16
17 LIST_ENTRY FIBListHead;
18 KSPIN_LOCK FIBLock;
19
RouterDumpRoutes()20 void RouterDumpRoutes() {
21 PLIST_ENTRY CurrentEntry;
22 PLIST_ENTRY NextEntry;
23 PFIB_ENTRY Current;
24 PNEIGHBOR_CACHE_ENTRY NCE;
25
26 TI_DbgPrint(DEBUG_ROUTER,("Dumping Routes\n"));
27
28 CurrentEntry = FIBListHead.Flink;
29 while (CurrentEntry != &FIBListHead) {
30 NextEntry = CurrentEntry->Flink;
31 Current = CONTAINING_RECORD(CurrentEntry, FIB_ENTRY, ListEntry);
32
33 NCE = Current->Router;
34
35 TI_DbgPrint(DEBUG_ROUTER,("Examining FIBE %x\n", Current));
36 TI_DbgPrint(DEBUG_ROUTER,("... NetworkAddress %s\n", A2S(&Current->NetworkAddress)));
37 TI_DbgPrint(DEBUG_ROUTER,("... NCE->Address . %s\n", A2S(&NCE->Address)));
38
39 CurrentEntry = NextEntry;
40 }
41
42 TI_DbgPrint(DEBUG_ROUTER,("Dumping Routes ... Done\n"));
43 }
44
FreeFIB(PVOID Object)45 VOID FreeFIB(
46 PVOID Object)
47 /*
48 * FUNCTION: Frees an forward information base object
49 * ARGUMENTS:
50 * Object = Pointer to an forward information base structure
51 */
52 {
53 ExFreePoolWithTag(Object, FIB_TAG);
54 }
55
56
DestroyFIBE(PFIB_ENTRY FIBE)57 VOID DestroyFIBE(
58 PFIB_ENTRY FIBE)
59 /*
60 * FUNCTION: Destroys an forward information base entry
61 * ARGUMENTS:
62 * FIBE = Pointer to FIB entry
63 * NOTES:
64 * The forward information base lock must be held when called
65 */
66 {
67 TI_DbgPrint(DEBUG_ROUTER, ("Called. FIBE (0x%X).\n", FIBE));
68
69 /* Unlink the FIB entry from the list */
70 RemoveEntryList(&FIBE->ListEntry);
71
72 /* And free the FIB entry */
73 FreeFIB(FIBE);
74 }
75
76
DestroyFIBEs(VOID)77 VOID DestroyFIBEs(
78 VOID)
79 /*
80 * FUNCTION: Destroys all forward information base entries
81 * NOTES:
82 * The forward information base lock must be held when called
83 */
84 {
85 PLIST_ENTRY CurrentEntry;
86 PLIST_ENTRY NextEntry;
87 PFIB_ENTRY Current;
88
89 /* Search the list and remove every FIB entry we find */
90 CurrentEntry = FIBListHead.Flink;
91 while (CurrentEntry != &FIBListHead) {
92 NextEntry = CurrentEntry->Flink;
93 Current = CONTAINING_RECORD(CurrentEntry, FIB_ENTRY, ListEntry);
94 /* Destroy the FIB entry */
95 DestroyFIBE(Current);
96 CurrentEntry = NextEntry;
97 }
98 }
99
100
CountFIBs(PIP_INTERFACE IF)101 UINT CountFIBs(PIP_INTERFACE IF) {
102 UINT FibCount = 0;
103 PLIST_ENTRY CurrentEntry;
104 PLIST_ENTRY NextEntry;
105 PFIB_ENTRY Current;
106
107 CurrentEntry = FIBListHead.Flink;
108 while (CurrentEntry != &FIBListHead) {
109 NextEntry = CurrentEntry->Flink;
110 Current = CONTAINING_RECORD(CurrentEntry, FIB_ENTRY, ListEntry);
111 if (Current->Router->Interface == IF)
112 FibCount++;
113 CurrentEntry = NextEntry;
114 }
115
116 return FibCount;
117 }
118
119
CopyFIBs(PIP_INTERFACE IF,PFIB_ENTRY Target)120 UINT CopyFIBs( PIP_INTERFACE IF, PFIB_ENTRY Target ) {
121 UINT FibCount = 0;
122 PLIST_ENTRY CurrentEntry;
123 PLIST_ENTRY NextEntry;
124 PFIB_ENTRY Current;
125
126 CurrentEntry = FIBListHead.Flink;
127 while (CurrentEntry != &FIBListHead) {
128 NextEntry = CurrentEntry->Flink;
129 Current = CONTAINING_RECORD(CurrentEntry, FIB_ENTRY, ListEntry);
130 if (Current->Router->Interface == IF)
131 {
132 Target[FibCount] = *Current;
133 FibCount++;
134 }
135 CurrentEntry = NextEntry;
136 }
137
138 return FibCount;
139 }
140
141
CommonPrefixLength(PIP_ADDRESS Address1,PIP_ADDRESS Address2)142 UINT CommonPrefixLength(
143 PIP_ADDRESS Address1,
144 PIP_ADDRESS Address2)
145 /*
146 * FUNCTION: Computes the length of the longest prefix common to two addresses
147 * ARGUMENTS:
148 * Address1 = Pointer to first address
149 * Address2 = Pointer to second address
150 * NOTES:
151 * The two addresses must be of the same type
152 * RETURNS:
153 * Length of longest common prefix
154 */
155 {
156 PUCHAR Addr1, Addr2;
157 UINT Size;
158 UINT i, j;
159 UINT Bitmask;
160
161 TI_DbgPrint(DEBUG_ROUTER, ("Called. Address1 (0x%X) Address2 (0x%X).\n", Address1, Address2));
162
163 /*TI_DbgPrint(DEBUG_ROUTER, ("Target (%s) \n", A2S(Address1)));*/
164 /*TI_DbgPrint(DEBUG_ROUTER, ("Adapter (%s).\n", A2S(Address2)));*/
165
166 if (Address1->Type == IP_ADDRESS_V4)
167 Size = sizeof(IPv4_RAW_ADDRESS);
168 else
169 Size = sizeof(IPv6_RAW_ADDRESS);
170
171 Addr1 = (PUCHAR)&Address1->Address.IPv4Address;
172 Addr2 = (PUCHAR)&Address2->Address.IPv4Address;
173
174 /* Find first non-matching byte */
175 for (i = 0; i < Size && Addr1[i] == Addr2[i]; i++);
176 if( i == Size ) return 8 * i;
177
178 /* Find first non-matching bit */
179 Bitmask = 0x80;
180 for (j = 0; (Addr1[i] & Bitmask) == (Addr2[i] & Bitmask); j++)
181 Bitmask >>= 1;
182
183 TI_DbgPrint(DEBUG_ROUTER, ("Returning %d\n", 8 * i + j));
184
185 return 8 * i + j;
186 }
187
188
RouterAddRoute(PIP_ADDRESS NetworkAddress,PIP_ADDRESS Netmask,PNEIGHBOR_CACHE_ENTRY Router,UINT Metric)189 PFIB_ENTRY RouterAddRoute(
190 PIP_ADDRESS NetworkAddress,
191 PIP_ADDRESS Netmask,
192 PNEIGHBOR_CACHE_ENTRY Router,
193 UINT Metric)
194 /*
195 * FUNCTION: Adds a route to the Forward Information Base (FIB)
196 * ARGUMENTS:
197 * NetworkAddress = Pointer to address of network
198 * Netmask = Pointer to netmask of network
199 * Router = Pointer to NCE of router to use
200 * Metric = Cost of this route
201 * RETURNS:
202 * Pointer to FIB entry if the route was added, NULL if not
203 * NOTES:
204 * The FIB entry references the NetworkAddress, Netmask and
205 * the NCE of the router. The caller is responsible for providing
206 * these references
207 */
208 {
209 PFIB_ENTRY FIBE;
210
211 TI_DbgPrint(DEBUG_ROUTER, ("Called. NetworkAddress (0x%X) Netmask (0x%X) "
212 "Router (0x%X) Metric (%d).\n", NetworkAddress, Netmask, Router, Metric));
213
214 TI_DbgPrint(DEBUG_ROUTER, ("NetworkAddress (%s) Netmask (%s) Router (%s).\n",
215 A2S(NetworkAddress),
216 A2S(Netmask),
217 A2S(&Router->Address)));
218
219 FIBE = ExAllocatePoolWithTag(NonPagedPool, sizeof(FIB_ENTRY), FIB_TAG);
220 if (!FIBE) {
221 TI_DbgPrint(MIN_TRACE, ("Insufficient resources.\n"));
222 return NULL;
223 }
224
225 RtlCopyMemory( &FIBE->NetworkAddress, NetworkAddress,
226 sizeof(FIBE->NetworkAddress) );
227 RtlCopyMemory( &FIBE->Netmask, Netmask,
228 sizeof(FIBE->Netmask) );
229 FIBE->Router = Router;
230 FIBE->Metric = Metric;
231
232 /* Add FIB to the forward information base */
233 TcpipInterlockedInsertTailList(&FIBListHead, &FIBE->ListEntry, &FIBLock);
234
235 return FIBE;
236 }
237
238
RouterGetRoute(PIP_ADDRESS Destination)239 PNEIGHBOR_CACHE_ENTRY RouterGetRoute(PIP_ADDRESS Destination)
240 /*
241 * FUNCTION: Finds a router to use to get to Destination
242 * ARGUMENTS:
243 * Destination = Pointer to destination address (NULL means don't care)
244 * RETURNS:
245 * Pointer to NCE for router, NULL if none was found
246 * NOTES:
247 * If found the NCE is referenced
248 */
249 {
250 KIRQL OldIrql;
251 PLIST_ENTRY CurrentEntry;
252 PLIST_ENTRY NextEntry;
253 PFIB_ENTRY Current;
254 UCHAR State;
255 UINT Length, BestLength = 0, MaskLength;
256 PNEIGHBOR_CACHE_ENTRY NCE, BestNCE = NULL;
257
258 TI_DbgPrint(DEBUG_ROUTER, ("Called. Destination (0x%X)\n", Destination));
259
260 TI_DbgPrint(DEBUG_ROUTER, ("Destination (%s)\n", A2S(Destination)));
261
262 TcpipAcquireSpinLock(&FIBLock, &OldIrql);
263
264 CurrentEntry = FIBListHead.Flink;
265 while (CurrentEntry != &FIBListHead) {
266 NextEntry = CurrentEntry->Flink;
267 Current = CONTAINING_RECORD(CurrentEntry, FIB_ENTRY, ListEntry);
268
269 NCE = Current->Router;
270 State = NCE->State;
271
272 Length = CommonPrefixLength(Destination, &Current->NetworkAddress);
273 MaskLength = AddrCountPrefixBits(&Current->Netmask);
274
275 TI_DbgPrint(DEBUG_ROUTER,("This-Route: %s (Sharing %d bits)\n",
276 A2S(&NCE->Address), Length));
277
278 if(Length >= MaskLength && (Length > BestLength || !BestNCE) &&
279 ((!(State & NUD_STALE) && !(State & NUD_INCOMPLETE)) || !BestNCE)) {
280 /* This seems to be a better router */
281 BestNCE = NCE;
282 BestLength = Length;
283 TI_DbgPrint(DEBUG_ROUTER,("Route selected\n"));
284 }
285
286 CurrentEntry = NextEntry;
287 }
288
289 TcpipReleaseSpinLock(&FIBLock, OldIrql);
290
291 if( BestNCE ) {
292 TI_DbgPrint(DEBUG_ROUTER,("Routing to %s\n", A2S(&BestNCE->Address)));
293 } else {
294 TI_DbgPrint(DEBUG_ROUTER,("Packet won't be routed\n"));
295 }
296
297 return BestNCE;
298 }
299
RouteGetRouteToDestination(PIP_ADDRESS Destination)300 PNEIGHBOR_CACHE_ENTRY RouteGetRouteToDestination(PIP_ADDRESS Destination)
301 /*
302 * FUNCTION: Locates an RCN describing a route to a destination address
303 * ARGUMENTS:
304 * Destination = Pointer to destination address to find route to
305 * RCN = Address of pointer to an RCN
306 * RETURNS:
307 * Status of operation
308 * NOTES:
309 * The RCN is referenced for the caller. The caller is responsible
310 * for dereferencing it after use
311 */
312 {
313 PNEIGHBOR_CACHE_ENTRY NCE = NULL;
314 PIP_INTERFACE Interface;
315
316 TI_DbgPrint(DEBUG_RCACHE, ("Called. Destination (0x%X)\n", Destination));
317
318 TI_DbgPrint(DEBUG_RCACHE, ("Destination (%s)\n", A2S(Destination)));
319
320 #if 0
321 TI_DbgPrint(MIN_TRACE, ("Displaying tree (before).\n"));
322 PrintTree(RouteCache);
323 #endif
324
325 /* Check if the destination is on-link */
326 Interface = FindOnLinkInterface(Destination);
327 if (Interface) {
328 /* The destination address is on-link. Check our neighbor cache */
329 NCE = NBFindOrCreateNeighbor(Interface, Destination, FALSE);
330 } else {
331 /* Destination is not on any subnets we're on. Find a router to use */
332 NCE = RouterGetRoute(Destination);
333 }
334
335 if( NCE )
336 TI_DbgPrint(DEBUG_ROUTER,("Interface->MTU: %d\n", NCE->Interface->MTU));
337
338 return NCE;
339 }
340
RouterRemoveRoutesForInterface(PIP_INTERFACE Interface)341 VOID RouterRemoveRoutesForInterface(PIP_INTERFACE Interface)
342 {
343 KIRQL OldIrql;
344 PLIST_ENTRY CurrentEntry;
345 PLIST_ENTRY NextEntry;
346 PFIB_ENTRY Current;
347
348 TcpipAcquireSpinLock(&FIBLock, &OldIrql);
349
350 CurrentEntry = FIBListHead.Flink;
351 while (CurrentEntry != &FIBListHead) {
352 NextEntry = CurrentEntry->Flink;
353 Current = CONTAINING_RECORD(CurrentEntry, FIB_ENTRY, ListEntry);
354
355 if (Interface == Current->Router->Interface)
356 DestroyFIBE(Current);
357
358 CurrentEntry = NextEntry;
359 }
360
361 TcpipReleaseSpinLock(&FIBLock, OldIrql);
362 }
363
RouterRemoveRoute(PIP_ADDRESS Target,PIP_ADDRESS Router)364 NTSTATUS RouterRemoveRoute(PIP_ADDRESS Target, PIP_ADDRESS Router)
365 /*
366 * FUNCTION: Removes a route from the Forward Information Base (FIB)
367 * ARGUMENTS:
368 * Target: The machine or network targeted by the route
369 * Router: The router used to pass the packet to the destination
370 *
371 * Searches the FIB and removes a route matching the indicated parameters.
372 */
373 {
374 KIRQL OldIrql;
375 PLIST_ENTRY CurrentEntry;
376 PLIST_ENTRY NextEntry;
377 PFIB_ENTRY Current;
378 BOOLEAN Found = FALSE;
379 PNEIGHBOR_CACHE_ENTRY NCE;
380
381 TI_DbgPrint(DEBUG_ROUTER, ("Called\n"));
382 TI_DbgPrint(DEBUG_ROUTER, ("Deleting Route From: %s\n", A2S(Router)));
383 TI_DbgPrint(DEBUG_ROUTER, (" To: %s\n", A2S(Target)));
384
385 TcpipAcquireSpinLock(&FIBLock, &OldIrql);
386
387 RouterDumpRoutes();
388
389 CurrentEntry = FIBListHead.Flink;
390 while (CurrentEntry != &FIBListHead) {
391 NextEntry = CurrentEntry->Flink;
392 Current = CONTAINING_RECORD(CurrentEntry, FIB_ENTRY, ListEntry);
393
394 NCE = Current->Router;
395
396 if( AddrIsEqual( &Current->NetworkAddress, Target ) &&
397 AddrIsEqual( &NCE->Address, Router ) ) {
398 Found = TRUE;
399 break;
400 }
401
402 Current = NULL;
403 CurrentEntry = NextEntry;
404 }
405
406 if( Found ) {
407 TI_DbgPrint(DEBUG_ROUTER, ("Deleting route\n"));
408 DestroyFIBE( Current );
409 }
410
411 RouterDumpRoutes();
412
413 TcpipReleaseSpinLock(&FIBLock, OldIrql);
414
415 TI_DbgPrint(DEBUG_ROUTER, ("Leaving\n"));
416
417 return Found ? STATUS_SUCCESS : STATUS_UNSUCCESSFUL;
418 }
419
420
RouterCreateRoute(PIP_ADDRESS NetworkAddress,PIP_ADDRESS Netmask,PIP_ADDRESS RouterAddress,PIP_INTERFACE Interface,UINT Metric)421 PFIB_ENTRY RouterCreateRoute(
422 PIP_ADDRESS NetworkAddress,
423 PIP_ADDRESS Netmask,
424 PIP_ADDRESS RouterAddress,
425 PIP_INTERFACE Interface,
426 UINT Metric)
427 /*
428 * FUNCTION: Creates a route with IPv4 addresses as parameters
429 * ARGUMENTS:
430 * NetworkAddress = Address of network
431 * Netmask = Netmask of network
432 * RouterAddress = Address of router to use
433 * NTE = Pointer to NTE to use
434 * Metric = Cost of this route
435 * RETURNS:
436 * Pointer to FIB entry if the route was created, NULL if not.
437 * The FIB entry references the NTE. The caller is responsible
438 * for providing this reference
439 */
440 {
441 KIRQL OldIrql;
442 PLIST_ENTRY CurrentEntry;
443 PLIST_ENTRY NextEntry;
444 PFIB_ENTRY Current;
445 PNEIGHBOR_CACHE_ENTRY NCE;
446
447 TcpipAcquireSpinLock(&FIBLock, &OldIrql);
448
449 CurrentEntry = FIBListHead.Flink;
450 while (CurrentEntry != &FIBListHead) {
451 NextEntry = CurrentEntry->Flink;
452 Current = CONTAINING_RECORD(CurrentEntry, FIB_ENTRY, ListEntry);
453
454 NCE = Current->Router;
455
456 if(AddrIsEqual(NetworkAddress, &Current->NetworkAddress) &&
457 AddrIsEqual(Netmask, &Current->Netmask) &&
458 NCE->Interface == Interface)
459 {
460 TI_DbgPrint(DEBUG_ROUTER,("Attempting to add duplicate route to %s\n", A2S(NetworkAddress)));
461 TcpipReleaseSpinLock(&FIBLock, OldIrql);
462 return NULL;
463 }
464
465 CurrentEntry = NextEntry;
466 }
467
468 TcpipReleaseSpinLock(&FIBLock, OldIrql);
469
470 /* The NCE references RouterAddress. The NCE is referenced for us */
471 NCE = NBFindOrCreateNeighbor(Interface, RouterAddress, TRUE);
472
473 if (!NCE) {
474 /* Not enough free resources */
475 return NULL;
476 }
477
478 return RouterAddRoute(NetworkAddress, Netmask, NCE, Metric);
479 }
480
481
RouterStartup(VOID)482 NTSTATUS RouterStartup(
483 VOID)
484 /*
485 * FUNCTION: Initializes the routing subsystem
486 * RETURNS:
487 * Status of operation
488 */
489 {
490 TI_DbgPrint(DEBUG_ROUTER, ("Called.\n"));
491
492 /* Initialize the Forward Information Base */
493 InitializeListHead(&FIBListHead);
494 TcpipInitializeSpinLock(&FIBLock);
495
496 return STATUS_SUCCESS;
497 }
498
499
RouterShutdown(VOID)500 NTSTATUS RouterShutdown(
501 VOID)
502 /*
503 * FUNCTION: Shuts down the routing subsystem
504 * RETURNS:
505 * Status of operation
506 */
507 {
508 KIRQL OldIrql;
509
510 TI_DbgPrint(DEBUG_ROUTER, ("Called.\n"));
511
512 /* Clear Forward Information Base */
513 TcpipAcquireSpinLock(&FIBLock, &OldIrql);
514 DestroyFIBEs();
515 TcpipReleaseSpinLock(&FIBLock, OldIrql);
516
517 return STATUS_SUCCESS;
518 }
519
520 /* EOF */
521