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)
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.
12 * CSH 01/08-2000 Created
18 LIST_ENTRY FIBListHead
;
21 void RouterDumpRoutes() {
22 PLIST_ENTRY CurrentEntry
;
23 PLIST_ENTRY NextEntry
;
25 PNEIGHBOR_CACHE_ENTRY NCE
;
27 TI_DbgPrint(DEBUG_ROUTER
,("Dumping Routes\n"));
29 CurrentEntry
= FIBListHead
.Flink
;
30 while (CurrentEntry
!= &FIBListHead
) {
31 NextEntry
= CurrentEntry
->Flink
;
32 Current
= CONTAINING_RECORD(CurrentEntry
, FIB_ENTRY
, ListEntry
);
34 NCE
= Current
->Router
;
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
)));
40 CurrentEntry
= NextEntry
;
43 TI_DbgPrint(DEBUG_ROUTER
,("Dumping Routes ... Done\n"));
49 * FUNCTION: Frees an forward information base object
51 * Object = Pointer to an forward information base structure
54 ExFreePoolWithTag(Object
, FIB_TAG
);
61 * FUNCTION: Destroys an forward information base entry
63 * FIBE = Pointer to FIB entry
65 * The forward information base lock must be held when called
68 TI_DbgPrint(DEBUG_ROUTER
, ("Called. FIBE (0x%X).\n", FIBE
));
70 /* Unlink the FIB entry from the list */
71 RemoveEntryList(&FIBE
->ListEntry
);
73 /* And free the FIB entry */
81 * FUNCTION: Destroys all forward information base entries
83 * The forward information base lock must be held when called
86 PLIST_ENTRY CurrentEntry
;
87 PLIST_ENTRY NextEntry
;
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 */
97 CurrentEntry
= NextEntry
;
102 UINT
CountFIBs(PIP_INTERFACE IF
) {
104 PLIST_ENTRY CurrentEntry
;
105 PLIST_ENTRY NextEntry
;
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
)
114 CurrentEntry
= NextEntry
;
121 UINT
CopyFIBs( PIP_INTERFACE IF
, PFIB_ENTRY Target
) {
123 PLIST_ENTRY CurrentEntry
;
124 PLIST_ENTRY NextEntry
;
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
)
133 Target
[FibCount
] = *Current
;
136 CurrentEntry
= NextEntry
;
143 UINT
CommonPrefixLength(
144 PIP_ADDRESS Address1
,
145 PIP_ADDRESS Address2
)
147 * FUNCTION: Computes the length of the longest prefix common to two addresses
149 * Address1 = Pointer to first address
150 * Address2 = Pointer to second address
152 * The two addresses must be of the same type
154 * Length of longest common prefix
162 TI_DbgPrint(DEBUG_ROUTER
, ("Called. Address1 (0x%X) Address2 (0x%X).\n", Address1
, Address2
));
164 /*TI_DbgPrint(DEBUG_ROUTER, ("Target (%s) \n", A2S(Address1)));*/
165 /*TI_DbgPrint(DEBUG_ROUTER, ("Adapter (%s).\n", A2S(Address2)));*/
167 if (Address1
->Type
== IP_ADDRESS_V4
)
168 Size
= sizeof(IPv4_RAW_ADDRESS
);
170 Size
= sizeof(IPv6_RAW_ADDRESS
);
172 Addr1
= (PUCHAR
)&Address1
->Address
.IPv4Address
;
173 Addr2
= (PUCHAR
)&Address2
->Address
.IPv4Address
;
175 /* Find first non-matching byte */
176 for (i
= 0; i
< Size
&& Addr1
[i
] == Addr2
[i
]; i
++);
177 if( i
== Size
) return 8 * i
;
179 /* Find first non-matching bit */
181 for (j
= 0; (Addr1
[i
] & Bitmask
) == (Addr2
[i
] & Bitmask
); j
++)
184 TI_DbgPrint(DEBUG_ROUTER
, ("Returning %d\n", 8 * i
+ j
));
190 PFIB_ENTRY
RouterAddRoute(
191 PIP_ADDRESS NetworkAddress
,
193 PNEIGHBOR_CACHE_ENTRY Router
,
196 * FUNCTION: Adds a route to the Forward Information Base (FIB)
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
203 * Pointer to FIB entry if the route was added, NULL if not
205 * The FIB entry references the NetworkAddress, Netmask and
206 * the NCE of the router. The caller is responsible for providing
212 TI_DbgPrint(DEBUG_ROUTER
, ("Called. NetworkAddress (0x%X) Netmask (0x%X) "
213 "Router (0x%X) Metric (%d).\n", NetworkAddress
, Netmask
, Router
, Metric
));
215 TI_DbgPrint(DEBUG_ROUTER
, ("NetworkAddress (%s) Netmask (%s) Router (%s).\n",
218 A2S(&Router
->Address
)));
220 FIBE
= ExAllocatePoolWithTag(NonPagedPool
, sizeof(FIB_ENTRY
), FIB_TAG
);
222 TI_DbgPrint(MIN_TRACE
, ("Insufficient resources.\n"));
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
;
233 /* Add FIB to the forward information base */
234 TcpipInterlockedInsertTailList(&FIBListHead
, &FIBE
->ListEntry
, &FIBLock
);
240 PNEIGHBOR_CACHE_ENTRY
RouterGetRoute(PIP_ADDRESS Destination
)
242 * FUNCTION: Finds a router to use to get to Destination
244 * Destination = Pointer to destination address (NULL means don't care)
246 * Pointer to NCE for router, NULL if none was found
248 * If found the NCE is referenced
252 PLIST_ENTRY CurrentEntry
;
253 PLIST_ENTRY NextEntry
;
256 UINT Length
, BestLength
= 0, MaskLength
;
257 PNEIGHBOR_CACHE_ENTRY NCE
, BestNCE
= NULL
;
259 TI_DbgPrint(DEBUG_ROUTER
, ("Called. Destination (0x%X)\n", Destination
));
261 TI_DbgPrint(DEBUG_ROUTER
, ("Destination (%s)\n", A2S(Destination
)));
263 TcpipAcquireSpinLock(&FIBLock
, &OldIrql
);
265 CurrentEntry
= FIBListHead
.Flink
;
266 while (CurrentEntry
!= &FIBListHead
) {
267 NextEntry
= CurrentEntry
->Flink
;
268 Current
= CONTAINING_RECORD(CurrentEntry
, FIB_ENTRY
, ListEntry
);
270 NCE
= Current
->Router
;
273 Length
= CommonPrefixLength(Destination
, &Current
->NetworkAddress
);
274 MaskLength
= AddrCountPrefixBits(&Current
->Netmask
);
276 TI_DbgPrint(DEBUG_ROUTER
,("This-Route: %s (Sharing %d bits)\n",
277 A2S(&NCE
->Address
), Length
));
279 if(Length
>= MaskLength
&& (Length
> BestLength
|| !BestNCE
) &&
280 (!(State
& NUD_STALE
) || !BestNCE
)) {
281 /* This seems to be a better router */
284 TI_DbgPrint(DEBUG_ROUTER
,("Route selected\n"));
287 CurrentEntry
= NextEntry
;
290 TcpipReleaseSpinLock(&FIBLock
, OldIrql
);
293 TI_DbgPrint(DEBUG_ROUTER
,("Routing to %s\n", A2S(&BestNCE
->Address
)));
295 TI_DbgPrint(DEBUG_ROUTER
,("Packet won't be routed\n"));
301 PNEIGHBOR_CACHE_ENTRY
RouteGetRouteToDestination(PIP_ADDRESS Destination
)
303 * FUNCTION: Locates an RCN describing a route to a destination address
305 * Destination = Pointer to destination address to find route to
306 * RCN = Address of pointer to an RCN
308 * Status of operation
310 * The RCN is referenced for the caller. The caller is responsible
311 * for dereferencing it after use
314 PNEIGHBOR_CACHE_ENTRY NCE
= NULL
;
315 PIP_INTERFACE Interface
;
317 TI_DbgPrint(DEBUG_RCACHE
, ("Called. Destination (0x%X)\n", Destination
));
319 TI_DbgPrint(DEBUG_RCACHE
, ("Destination (%s)\n", A2S(Destination
)));
322 TI_DbgPrint(MIN_TRACE
, ("Displaying tree (before).\n"));
323 PrintTree(RouteCache
);
326 /* Check if the destination is on-link */
327 Interface
= FindOnLinkInterface(Destination
);
329 /* The destination address is on-link. Check our neighbor cache */
330 NCE
= NBFindOrCreateNeighbor(Interface
, Destination
, FALSE
);
332 /* Destination is not on any subnets we're on. Find a router to use */
333 NCE
= RouterGetRoute(Destination
);
337 TI_DbgPrint(DEBUG_ROUTER
,("Interface->MTU: %d\n", NCE
->Interface
->MTU
));
342 VOID
RouterRemoveRoutesForInterface(PIP_INTERFACE Interface
)
345 PLIST_ENTRY CurrentEntry
;
346 PLIST_ENTRY NextEntry
;
349 TcpipAcquireSpinLock(&FIBLock
, &OldIrql
);
351 CurrentEntry
= FIBListHead
.Flink
;
352 while (CurrentEntry
!= &FIBListHead
) {
353 NextEntry
= CurrentEntry
->Flink
;
354 Current
= CONTAINING_RECORD(CurrentEntry
, FIB_ENTRY
, ListEntry
);
356 if (Interface
== Current
->Router
->Interface
)
357 DestroyFIBE(Current
);
359 CurrentEntry
= NextEntry
;
362 TcpipReleaseSpinLock(&FIBLock
, OldIrql
);
365 NTSTATUS
RouterRemoveRoute(PIP_ADDRESS Target
, PIP_ADDRESS Router
)
367 * FUNCTION: Removes a route from the Forward Information Base (FIB)
369 * Target: The machine or network targeted by the route
370 * Router: The router used to pass the packet to the destination
372 * Searches the FIB and removes a route matching the indicated parameters.
376 PLIST_ENTRY CurrentEntry
;
377 PLIST_ENTRY NextEntry
;
379 BOOLEAN Found
= FALSE
;
380 PNEIGHBOR_CACHE_ENTRY NCE
;
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
)));
386 TcpipAcquireSpinLock(&FIBLock
, &OldIrql
);
390 CurrentEntry
= FIBListHead
.Flink
;
391 while (CurrentEntry
!= &FIBListHead
) {
392 NextEntry
= CurrentEntry
->Flink
;
393 Current
= CONTAINING_RECORD(CurrentEntry
, FIB_ENTRY
, ListEntry
);
395 NCE
= Current
->Router
;
397 if( AddrIsEqual( &Current
->NetworkAddress
, Target
) &&
398 AddrIsEqual( &NCE
->Address
, Router
) ) {
404 CurrentEntry
= NextEntry
;
408 TI_DbgPrint(DEBUG_ROUTER
, ("Deleting route\n"));
409 DestroyFIBE( Current
);
414 TcpipReleaseSpinLock(&FIBLock
, OldIrql
);
416 TI_DbgPrint(DEBUG_ROUTER
, ("Leaving\n"));
418 return Found
? STATUS_SUCCESS
: STATUS_UNSUCCESSFUL
;
422 PFIB_ENTRY
RouterCreateRoute(
423 PIP_ADDRESS NetworkAddress
,
425 PIP_ADDRESS RouterAddress
,
426 PIP_INTERFACE Interface
,
429 * FUNCTION: Creates a route with IPv4 addresses as parameters
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
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
443 PLIST_ENTRY CurrentEntry
;
444 PLIST_ENTRY NextEntry
;
446 PNEIGHBOR_CACHE_ENTRY NCE
;
448 TcpipAcquireSpinLock(&FIBLock
, &OldIrql
);
450 CurrentEntry
= FIBListHead
.Flink
;
451 while (CurrentEntry
!= &FIBListHead
) {
452 NextEntry
= CurrentEntry
->Flink
;
453 Current
= CONTAINING_RECORD(CurrentEntry
, FIB_ENTRY
, ListEntry
);
455 NCE
= Current
->Router
;
457 if(AddrIsEqual(NetworkAddress
, &Current
->NetworkAddress
) &&
458 AddrIsEqual(Netmask
, &Current
->Netmask
) &&
459 NCE
->Interface
== Interface
)
461 TI_DbgPrint(DEBUG_ROUTER
,("Attempting to add duplicate route to %s\n", A2S(NetworkAddress
)));
462 TcpipReleaseSpinLock(&FIBLock
, OldIrql
);
466 CurrentEntry
= NextEntry
;
469 TcpipReleaseSpinLock(&FIBLock
, OldIrql
);
471 /* The NCE references RouterAddress. The NCE is referenced for us */
472 NCE
= NBFindOrCreateNeighbor(Interface
, RouterAddress
, TRUE
);
475 /* Not enough free resources */
479 return RouterAddRoute(NetworkAddress
, Netmask
, NCE
, Metric
);
483 NTSTATUS
RouterStartup(
486 * FUNCTION: Initializes the routing subsystem
488 * Status of operation
491 TI_DbgPrint(DEBUG_ROUTER
, ("Called.\n"));
493 /* Initialize the Forward Information Base */
494 InitializeListHead(&FIBListHead
);
495 TcpipInitializeSpinLock(&FIBLock
);
497 return STATUS_SUCCESS
;
501 NTSTATUS
RouterShutdown(
504 * FUNCTION: Shuts down the routing subsystem
506 * Status of operation
511 TI_DbgPrint(DEBUG_ROUTER
, ("Called.\n"));
513 /* Clear Forward Information Base */
514 TcpipAcquireSpinLock(&FIBLock
, &OldIrql
);
516 TcpipReleaseSpinLock(&FIBLock
, OldIrql
);
518 return STATUS_SUCCESS
;