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