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
;
255 UCHAR State
, BestState
= 0;
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 */
285 TI_DbgPrint(DEBUG_ROUTER
,("Route selected\n"));
288 CurrentEntry
= NextEntry
;
291 TcpipReleaseSpinLock(&FIBLock
, OldIrql
);
294 TI_DbgPrint(DEBUG_ROUTER
,("Routing to %s\n", A2S(&BestNCE
->Address
)));
296 TI_DbgPrint(DEBUG_ROUTER
,("Packet won't be routed\n"));
302 PNEIGHBOR_CACHE_ENTRY
RouteGetRouteToDestination(PIP_ADDRESS Destination
)
304 * FUNCTION: Locates an RCN describing a route to a destination address
306 * Destination = Pointer to destination address to find route to
307 * RCN = Address of pointer to an RCN
309 * Status of operation
311 * The RCN is referenced for the caller. The caller is responsible
312 * for dereferencing it after use
315 PNEIGHBOR_CACHE_ENTRY NCE
= NULL
;
316 PIP_INTERFACE Interface
;
318 TI_DbgPrint(DEBUG_RCACHE
, ("Called. Destination (0x%X)\n", Destination
));
320 TI_DbgPrint(DEBUG_RCACHE
, ("Destination (%s)\n", A2S(Destination
)));
323 TI_DbgPrint(MIN_TRACE
, ("Displaying tree (before).\n"));
324 PrintTree(RouteCache
);
327 /* Check if the destination is on-link */
328 Interface
= FindOnLinkInterface(Destination
);
330 /* The destination address is on-link. Check our neighbor cache */
331 NCE
= NBFindOrCreateNeighbor(Interface
, Destination
);
333 /* Destination is not on any subnets we're on. Find a router to use */
334 NCE
= RouterGetRoute(Destination
);
338 TI_DbgPrint(DEBUG_ROUTER
,("Interface->MTU: %d\n", NCE
->Interface
->MTU
));
343 NTSTATUS
RouterRemoveRoute(PIP_ADDRESS Target
, PIP_ADDRESS Router
)
345 * FUNCTION: Removes a route from the Forward Information Base (FIB)
347 * Target: The machine or network targeted by the route
348 * Router: The router used to pass the packet to the destination
350 * Searches the FIB and removes a route matching the indicated parameters.
354 PLIST_ENTRY CurrentEntry
;
355 PLIST_ENTRY NextEntry
;
357 BOOLEAN Found
= FALSE
;
358 PNEIGHBOR_CACHE_ENTRY NCE
;
360 TI_DbgPrint(DEBUG_ROUTER
, ("Called\n"));
361 TI_DbgPrint(DEBUG_ROUTER
, ("Deleting Route From: %s\n", A2S(Router
)));
362 TI_DbgPrint(DEBUG_ROUTER
, (" To: %s\n", A2S(Target
)));
364 TcpipAcquireSpinLock(&FIBLock
, &OldIrql
);
368 CurrentEntry
= FIBListHead
.Flink
;
369 while (CurrentEntry
!= &FIBListHead
) {
370 NextEntry
= CurrentEntry
->Flink
;
371 Current
= CONTAINING_RECORD(CurrentEntry
, FIB_ENTRY
, ListEntry
);
373 NCE
= Current
->Router
;
375 if( AddrIsEqual( &Current
->NetworkAddress
, Target
) &&
376 AddrIsEqual( &NCE
->Address
, Router
) ) {
382 CurrentEntry
= NextEntry
;
386 TI_DbgPrint(DEBUG_ROUTER
, ("Deleting route\n"));
387 DestroyFIBE( Current
);
392 TcpipReleaseSpinLock(&FIBLock
, OldIrql
);
394 TI_DbgPrint(DEBUG_ROUTER
, ("Leaving\n"));
396 return Found
? STATUS_SUCCESS
: STATUS_UNSUCCESSFUL
;
400 PFIB_ENTRY
RouterCreateRoute(
401 PIP_ADDRESS NetworkAddress
,
403 PIP_ADDRESS RouterAddress
,
404 PIP_INTERFACE Interface
,
407 * FUNCTION: Creates a route with IPv4 addresses as parameters
409 * NetworkAddress = Address of network
410 * Netmask = Netmask of network
411 * RouterAddress = Address of router to use
412 * NTE = Pointer to NTE to use
413 * Metric = Cost of this route
415 * Pointer to FIB entry if the route was created, NULL if not.
416 * The FIB entry references the NTE. The caller is responsible
417 * for providing this reference
421 PLIST_ENTRY CurrentEntry
;
422 PLIST_ENTRY NextEntry
;
424 PNEIGHBOR_CACHE_ENTRY NCE
;
426 TcpipAcquireSpinLock(&FIBLock
, &OldIrql
);
428 CurrentEntry
= FIBListHead
.Flink
;
429 while (CurrentEntry
!= &FIBListHead
) {
430 NextEntry
= CurrentEntry
->Flink
;
431 Current
= CONTAINING_RECORD(CurrentEntry
, FIB_ENTRY
, ListEntry
);
433 NCE
= Current
->Router
;
435 if( AddrIsEqual(NetworkAddress
, &Current
->NetworkAddress
) &&
436 AddrIsEqual(Netmask
, &Current
->Netmask
) ) {
437 TI_DbgPrint(DEBUG_ROUTER
,("Attempting to add duplicate route to %s\n", A2S(NetworkAddress
)));
438 TcpipReleaseSpinLock(&FIBLock
, OldIrql
);
442 CurrentEntry
= NextEntry
;
445 TcpipReleaseSpinLock(&FIBLock
, OldIrql
);
447 /* The NCE references RouterAddress. The NCE is referenced for us */
448 NCE
= NBFindOrCreateNeighbor(Interface
, RouterAddress
);
451 /* Not enough free resources */
455 return RouterAddRoute(NetworkAddress
, Netmask
, NCE
, Metric
);
459 NTSTATUS
RouterStartup(
462 * FUNCTION: Initializes the routing subsystem
464 * Status of operation
467 TI_DbgPrint(DEBUG_ROUTER
, ("Called.\n"));
469 /* Initialize the Forward Information Base */
470 InitializeListHead(&FIBListHead
);
471 TcpipInitializeSpinLock(&FIBLock
);
473 return STATUS_SUCCESS
;
477 NTSTATUS
RouterShutdown(
480 * FUNCTION: Shuts down the routing subsystem
482 * Status of operation
487 TI_DbgPrint(DEBUG_ROUTER
, ("Called.\n"));
489 /* Clear Forward Information Base */
490 TcpipAcquireSpinLock(&FIBLock
, &OldIrql
);
492 TcpipReleaseSpinLock(&FIBLock
, OldIrql
);
494 return STATUS_SUCCESS
;