a220db84e17400b04bc77a062957385930b38589
[reactos.git] / reactos / 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 exFreePool(Object);
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() {
103 UINT FibCount = 0;
104 PLIST_ENTRY CurrentEntry;
105 PLIST_ENTRY NextEntry;
106
107 /* Search the list and remove every FIB entry we find */
108 CurrentEntry = FIBListHead.Flink;
109 while (CurrentEntry != &FIBListHead) {
110 NextEntry = CurrentEntry->Flink;
111 CurrentEntry = NextEntry;
112 FibCount++;
113 }
114
115 return FibCount;
116 }
117
118
119 UINT CopyFIBs( PFIB_ENTRY Target ) {
120 UINT FibCount = 0;
121 PLIST_ENTRY CurrentEntry;
122 PLIST_ENTRY NextEntry;
123 PFIB_ENTRY Current;
124
125 /* Search the list and remove every FIB entry we find */
126 CurrentEntry = FIBListHead.Flink;
127 while (CurrentEntry != &FIBListHead) {
128 NextEntry = CurrentEntry->Flink;
129 Current = CONTAINING_RECORD(CurrentEntry, FIB_ENTRY, ListEntry);
130 Target[FibCount] = *Current;
131 CurrentEntry = NextEntry;
132 FibCount++;
133 }
134
135 return FibCount;
136 }
137
138
139 UINT CommonPrefixLength(
140 PIP_ADDRESS Address1,
141 PIP_ADDRESS Address2)
142 /*
143 * FUNCTION: Computes the length of the longest prefix common to two addresses
144 * ARGUMENTS:
145 * Address1 = Pointer to first address
146 * Address2 = Pointer to second address
147 * NOTES:
148 * The two addresses must be of the same type
149 * RETURNS:
150 * Length of longest common prefix
151 */
152 {
153 PUCHAR Addr1, Addr2;
154 UINT Size;
155 UINT i, j;
156 UINT Bitmask;
157
158 TI_DbgPrint(DEBUG_ROUTER, ("Called. Address1 (0x%X) Address2 (0x%X).\n", Address1, Address2));
159
160 /*TI_DbgPrint(DEBUG_ROUTER, ("Target (%s) \n", A2S(Address1)));*/
161 /*TI_DbgPrint(DEBUG_ROUTER, ("Adapter (%s).\n", A2S(Address2)));*/
162
163 if (Address1->Type == IP_ADDRESS_V4)
164 Size = sizeof(IPv4_RAW_ADDRESS);
165 else
166 Size = sizeof(IPv6_RAW_ADDRESS);
167
168 Addr1 = (PUCHAR)&Address1->Address.IPv4Address;
169 Addr2 = (PUCHAR)&Address2->Address.IPv4Address;
170
171 /* Find first non-matching byte */
172 for (i = 0; i < Size && Addr1[i] == Addr2[i]; i++);
173 if( i == Size ) return 8 * i;
174
175 /* Find first non-matching bit */
176 Bitmask = 0x80;
177 for (j = 0; (Addr1[i] & Bitmask) == (Addr2[i] & Bitmask); j++)
178 Bitmask >>= 1;
179
180 TI_DbgPrint(DEBUG_ROUTER, ("Returning %d\n", 8 * i + j));
181
182 return 8 * i + j;
183 }
184
185
186 PFIB_ENTRY RouterAddRoute(
187 PIP_ADDRESS NetworkAddress,
188 PIP_ADDRESS Netmask,
189 PNEIGHBOR_CACHE_ENTRY Router,
190 UINT Metric)
191 /*
192 * FUNCTION: Adds a route to the Forward Information Base (FIB)
193 * ARGUMENTS:
194 * NetworkAddress = Pointer to address of network
195 * Netmask = Pointer to netmask of network
196 * Router = Pointer to NCE of router to use
197 * Metric = Cost of this route
198 * RETURNS:
199 * Pointer to FIB entry if the route was added, NULL if not
200 * NOTES:
201 * The FIB entry references the NetworkAddress, Netmask and
202 * the NCE of the router. The caller is responsible for providing
203 * these references
204 */
205 {
206 PFIB_ENTRY FIBE;
207
208 TI_DbgPrint(DEBUG_ROUTER, ("Called. NetworkAddress (0x%X) Netmask (0x%X) "
209 "Router (0x%X) Metric (%d).\n", NetworkAddress, Netmask, Router, Metric));
210
211 TI_DbgPrint(DEBUG_ROUTER, ("NetworkAddress (%s) Netmask (%s) Router (%s).\n",
212 A2S(NetworkAddress),
213 A2S(Netmask),
214 A2S(&Router->Address)));
215
216 FIBE = exAllocatePool(NonPagedPool, sizeof(FIB_ENTRY));
217 if (!FIBE) {
218 TI_DbgPrint(MIN_TRACE, ("Insufficient resources.\n"));
219 return NULL;
220 }
221
222 INIT_TAG(Router, 'TUOR');
223
224 RtlCopyMemory( &FIBE->NetworkAddress, NetworkAddress,
225 sizeof(FIBE->NetworkAddress) );
226 RtlCopyMemory( &FIBE->Netmask, Netmask,
227 sizeof(FIBE->Netmask) );
228 FIBE->Router = Router;
229 FIBE->Metric = Metric;
230
231 /* Add FIB to the forward information base */
232 TcpipInterlockedInsertTailList(&FIBListHead, &FIBE->ListEntry, &FIBLock);
233
234 return FIBE;
235 }
236
237
238 PNEIGHBOR_CACHE_ENTRY RouterGetRoute(PIP_ADDRESS Destination)
239 /*
240 * FUNCTION: Finds a router to use to get to Destination
241 * ARGUMENTS:
242 * Destination = Pointer to destination address (NULL means don't care)
243 * RETURNS:
244 * Pointer to NCE for router, NULL if none was found
245 * NOTES:
246 * If found the NCE is referenced
247 */
248 {
249 KIRQL OldIrql;
250 PLIST_ENTRY CurrentEntry;
251 PLIST_ENTRY NextEntry;
252 PFIB_ENTRY Current;
253 UCHAR State, BestState = 0;
254 UINT Length, BestLength = 0, MaskLength;
255 PNEIGHBOR_CACHE_ENTRY NCE, BestNCE = NULL;
256
257 TI_DbgPrint(DEBUG_ROUTER, ("Called. Destination (0x%X)\n", Destination));
258
259 TI_DbgPrint(DEBUG_ROUTER, ("Destination (%s)\n", A2S(Destination)));
260
261 TcpipAcquireSpinLock(&FIBLock, &OldIrql);
262
263 CurrentEntry = FIBListHead.Flink;
264 while (CurrentEntry != &FIBListHead) {
265 NextEntry = CurrentEntry->Flink;
266 Current = CONTAINING_RECORD(CurrentEntry, FIB_ENTRY, ListEntry);
267
268 NCE = Current->Router;
269 State = NCE->State;
270
271 Length = CommonPrefixLength(Destination, &Current->NetworkAddress);
272 MaskLength = AddrCountPrefixBits(&Current->Netmask);
273
274 TI_DbgPrint(DEBUG_ROUTER,("This-Route: %s (Sharing %d bits)\n",
275 A2S(&NCE->Address), Length));
276
277 if(Length >= MaskLength && (Length > BestLength || !BestNCE) &&
278 (!(State & NUD_STALE) || !BestNCE)) {
279 /* This seems to be a better router */
280 BestNCE = NCE;
281 BestLength = Length;
282 BestState = State;
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
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);
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
341 NTSTATUS RouterRemoveRoute(PIP_ADDRESS Target, PIP_ADDRESS Router)
342 /*
343 * FUNCTION: Removes a route from the Forward Information Base (FIB)
344 * ARGUMENTS:
345 * Target: The machine or network targeted by the route
346 * Router: The router used to pass the packet to the destination
347 *
348 * Searches the FIB and removes a route matching the indicated parameters.
349 */
350 {
351 KIRQL OldIrql;
352 PLIST_ENTRY CurrentEntry;
353 PLIST_ENTRY NextEntry;
354 PFIB_ENTRY Current;
355 BOOLEAN Found = FALSE;
356 PNEIGHBOR_CACHE_ENTRY NCE;
357
358 TI_DbgPrint(DEBUG_ROUTER, ("Called\n"));
359 TI_DbgPrint(DEBUG_ROUTER, ("Deleting Route From: %s\n", A2S(Router)));
360 TI_DbgPrint(DEBUG_ROUTER, (" To: %s\n", A2S(Target)));
361
362 TcpipAcquireSpinLock(&FIBLock, &OldIrql);
363
364 RouterDumpRoutes();
365
366 CurrentEntry = FIBListHead.Flink;
367 while (CurrentEntry != &FIBListHead) {
368 NextEntry = CurrentEntry->Flink;
369 Current = CONTAINING_RECORD(CurrentEntry, FIB_ENTRY, ListEntry);
370
371 NCE = Current->Router;
372
373 if( AddrIsEqual( &Current->NetworkAddress, Target ) &&
374 AddrIsEqual( &NCE->Address, Router ) ) {
375 Found = TRUE;
376 break;
377 }
378
379 Current = NULL;
380 CurrentEntry = NextEntry;
381 }
382
383 if( Found ) {
384 TI_DbgPrint(DEBUG_ROUTER, ("Deleting route\n"));
385 DestroyFIBE( Current );
386 }
387
388 RouterDumpRoutes();
389
390 TcpipReleaseSpinLock(&FIBLock, OldIrql);
391
392 TI_DbgPrint(DEBUG_ROUTER, ("Leaving\n"));
393
394 return Found ? STATUS_SUCCESS : STATUS_UNSUCCESSFUL;
395 }
396
397
398 PFIB_ENTRY RouterCreateRoute(
399 PIP_ADDRESS NetworkAddress,
400 PIP_ADDRESS Netmask,
401 PIP_ADDRESS RouterAddress,
402 PIP_INTERFACE Interface,
403 UINT Metric)
404 /*
405 * FUNCTION: Creates a route with IPv4 addresses as parameters
406 * ARGUMENTS:
407 * NetworkAddress = Address of network
408 * Netmask = Netmask of network
409 * RouterAddress = Address of router to use
410 * NTE = Pointer to NTE to use
411 * Metric = Cost of this route
412 * RETURNS:
413 * Pointer to FIB entry if the route was created, NULL if not.
414 * The FIB entry references the NTE. The caller is responsible
415 * for providing this reference
416 */
417 {
418 KIRQL OldIrql;
419 PLIST_ENTRY CurrentEntry;
420 PLIST_ENTRY NextEntry;
421 PFIB_ENTRY Current;
422 PNEIGHBOR_CACHE_ENTRY NCE;
423
424 TcpipAcquireSpinLock(&FIBLock, &OldIrql);
425
426 CurrentEntry = FIBListHead.Flink;
427 while (CurrentEntry != &FIBListHead) {
428 NextEntry = CurrentEntry->Flink;
429 Current = CONTAINING_RECORD(CurrentEntry, FIB_ENTRY, ListEntry);
430
431 NCE = Current->Router;
432
433 if( AddrIsEqual(NetworkAddress, &Current->NetworkAddress) &&
434 AddrIsEqual(Netmask, &Current->Netmask) ) {
435 TI_DbgPrint(DEBUG_ROUTER,("Attempting to add duplicate route to %s\n", A2S(NetworkAddress)));
436 TcpipReleaseSpinLock(&FIBLock, OldIrql);
437 return NULL;
438 }
439
440 CurrentEntry = NextEntry;
441 }
442
443 TcpipReleaseSpinLock(&FIBLock, OldIrql);
444
445 /* The NCE references RouterAddress. The NCE is referenced for us */
446 NCE = NBFindOrCreateNeighbor(Interface, RouterAddress);
447
448 if (!NCE) {
449 /* Not enough free resources */
450 return NULL;
451 }
452
453 return RouterAddRoute(NetworkAddress, Netmask, NCE, Metric);
454 }
455
456
457 NTSTATUS RouterStartup(
458 VOID)
459 /*
460 * FUNCTION: Initializes the routing subsystem
461 * RETURNS:
462 * Status of operation
463 */
464 {
465 TI_DbgPrint(DEBUG_ROUTER, ("Called.\n"));
466
467 /* Initialize the Forward Information Base */
468 InitializeListHead(&FIBListHead);
469 TcpipInitializeSpinLock(&FIBLock);
470
471 return STATUS_SUCCESS;
472 }
473
474
475 NTSTATUS RouterShutdown(
476 VOID)
477 /*
478 * FUNCTION: Shuts down the routing subsystem
479 * RETURNS:
480 * Status of operation
481 */
482 {
483 KIRQL OldIrql;
484
485 TI_DbgPrint(DEBUG_ROUTER, ("Called.\n"));
486
487 /* Clear Forward Information Base */
488 TcpipAcquireSpinLock(&FIBLock, &OldIrql);
489 DestroyFIBEs();
490 TcpipReleaseSpinLock(&FIBLock, OldIrql);
491
492 return STATUS_SUCCESS;
493 }
494
495 /* EOF */