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