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 PoolFreeBuffer(Object
);
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
;
104 PLIST_ENTRY CurrentEntry
;
105 PLIST_ENTRY NextEntry
;
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
;
119 UINT
CopyFIBs( PFIB_ENTRY Target
) {
121 PLIST_ENTRY CurrentEntry
;
122 PLIST_ENTRY NextEntry
;
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
;
139 UINT
CommonPrefixLength(
140 PIP_ADDRESS Address1
,
141 PIP_ADDRESS Address2
)
143 * FUNCTION: Computes the length of the longest prefix common to two addresses
145 * Address1 = Pointer to first address
146 * Address2 = Pointer to second address
148 * The two addresses must be of the same type
150 * Length of longest common prefix
158 TI_DbgPrint(DEBUG_ROUTER
, ("Called. Address1 (0x%X) Address2 (0x%X).\n", Address1
, Address2
));
160 /*TI_DbgPrint(DEBUG_ROUTER, ("Target (%s) \n", A2S(Address1)));*/
161 /*TI_DbgPrint(DEBUG_ROUTER, ("Adapter (%s).\n", A2S(Address2)));*/
163 if (Address1
->Type
== IP_ADDRESS_V4
)
164 Size
= sizeof(IPv4_RAW_ADDRESS
);
166 Size
= sizeof(IPv6_RAW_ADDRESS
);
168 Addr1
= (PUCHAR
)&Address1
->Address
.IPv4Address
;
169 Addr2
= (PUCHAR
)&Address2
->Address
.IPv4Address
;
171 /* Find first non-matching byte */
172 for (i
= 0; i
< Size
&& Addr1
[i
] == Addr2
[i
]; i
++);
173 if( i
== Size
) return 8 * i
;
175 /* Find first non-matching bit */
177 for (j
= 0; (Addr1
[i
] & Bitmask
) == (Addr2
[i
] & Bitmask
); j
++)
180 TI_DbgPrint(DEBUG_ROUTER
, ("Returning %d\n", 8 * i
+ j
));
186 PFIB_ENTRY
RouterAddRoute(
187 PIP_ADDRESS NetworkAddress
,
189 PNEIGHBOR_CACHE_ENTRY Router
,
192 * FUNCTION: Adds a route to the Forward Information Base (FIB)
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
199 * Pointer to FIB entry if the route was added, NULL if not
201 * The FIB entry references the NetworkAddress, Netmask and
202 * the NCE of the router. The caller is responsible for providing
208 TI_DbgPrint(DEBUG_ROUTER
, ("Called. NetworkAddress (0x%X) Netmask (0x%X) "
209 "Router (0x%X) Metric (%d).\n", NetworkAddress
, Netmask
, Router
, Metric
));
211 TI_DbgPrint(DEBUG_ROUTER
, ("NetworkAddress (%s) Netmask (%s) Router (%s).\n",
214 A2S(&Router
->Address
)));
216 FIBE
= PoolAllocateBuffer(sizeof(FIB_ENTRY
));
218 TI_DbgPrint(MIN_TRACE
, ("Insufficient resources.\n"));
222 INIT_TAG(Router
, TAG('R','O','U','T'));
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
;
231 /* Add FIB to the forward information base */
232 TcpipInterlockedInsertTailList(&FIBListHead
, &FIBE
->ListEntry
, &FIBLock
);
238 PNEIGHBOR_CACHE_ENTRY
RouterGetRoute(PIP_ADDRESS Destination
)
240 * FUNCTION: Finds a router to use to get to Destination
242 * Destination = Pointer to destination address (NULL means don't care)
244 * Pointer to NCE for router, NULL if none was found
246 * If found the NCE is referenced
250 PLIST_ENTRY CurrentEntry
;
251 PLIST_ENTRY NextEntry
;
253 UCHAR State
, BestState
= 0;
254 UINT Length
, BestLength
= 0, MaskLength
;
255 PNEIGHBOR_CACHE_ENTRY NCE
, BestNCE
= NULL
;
257 TI_DbgPrint(DEBUG_ROUTER
, ("Called. Destination (0x%X)\n", Destination
));
259 TI_DbgPrint(DEBUG_ROUTER
, ("Destination (%s)\n", A2S(Destination
)));
261 TcpipAcquireSpinLock(&FIBLock
, &OldIrql
);
263 CurrentEntry
= FIBListHead
.Flink
;
264 while (CurrentEntry
!= &FIBListHead
) {
265 NextEntry
= CurrentEntry
->Flink
;
266 Current
= CONTAINING_RECORD(CurrentEntry
, FIB_ENTRY
, ListEntry
);
268 NCE
= Current
->Router
;
271 Length
= CommonPrefixLength(Destination
, &Current
->NetworkAddress
);
272 MaskLength
= AddrCountPrefixBits(&Current
->Netmask
);
274 TI_DbgPrint(DEBUG_ROUTER
,("This-Route: %s (Sharing %d bits)\n",
275 A2S(&NCE
->Address
), Length
));
277 if(Length
>= MaskLength
&& (Length
> BestLength
|| !BestLength
)) {
278 /* This seems to be a better router */
282 TI_DbgPrint(DEBUG_ROUTER
,("Route selected\n"));
285 CurrentEntry
= NextEntry
;
288 TcpipReleaseSpinLock(&FIBLock
, OldIrql
);
291 TI_DbgPrint(DEBUG_ROUTER
,("Routing to %s\n", A2S(&BestNCE
->Address
)));
293 TI_DbgPrint(DEBUG_ROUTER
,("Packet won't be routed\n"));
299 PNEIGHBOR_CACHE_ENTRY
RouteGetRouteToDestination(PIP_ADDRESS Destination
)
301 * FUNCTION: Locates an RCN describing a route to a destination address
303 * Destination = Pointer to destination address to find route to
304 * RCN = Address of pointer to an RCN
306 * Status of operation
308 * The RCN is referenced for the caller. The caller is responsible
309 * for dereferencing it after use
312 PNEIGHBOR_CACHE_ENTRY NCE
= NULL
;
313 PIP_INTERFACE Interface
;
315 TI_DbgPrint(DEBUG_RCACHE
, ("Called. Destination (0x%X)\n", Destination
));
317 TI_DbgPrint(DEBUG_RCACHE
, ("Destination (%s)\n", A2S(Destination
)));
320 TI_DbgPrint(MIN_TRACE
, ("Displaying tree (before).\n"));
321 PrintTree(RouteCache
);
324 /* Check if the destination is on-link */
325 Interface
= FindOnLinkInterface(Destination
);
327 /* The destination address is on-link. Check our neighbor cache */
328 NCE
= NBFindOrCreateNeighbor(Interface
, Destination
);
330 /* Destination is not on any subnets we're on. Find a router to use */
331 NCE
= RouterGetRoute(Destination
);
335 TI_DbgPrint(DEBUG_ROUTER
,("Interface->MTU: %d\n", NCE
->Interface
->MTU
));
340 NTSTATUS
RouterRemoveRoute(PIP_ADDRESS Target
, PIP_ADDRESS Router
)
342 * FUNCTION: Removes a route from the Forward Information Base (FIB)
344 * Target: The machine or network targeted by the route
345 * Router: The router used to pass the packet to the destination
347 * Searches the FIB and removes a route matching the indicated parameters.
351 PLIST_ENTRY CurrentEntry
;
352 PLIST_ENTRY NextEntry
;
354 BOOLEAN Found
= FALSE
;
355 PNEIGHBOR_CACHE_ENTRY NCE
;
357 TI_DbgPrint(DEBUG_ROUTER
, ("Called\n"));
358 TI_DbgPrint(DEBUG_ROUTER
, ("Deleting Route From: %s\n", A2S(Router
)));
359 TI_DbgPrint(DEBUG_ROUTER
, (" To: %s\n", A2S(Target
)));
361 TcpipAcquireSpinLock(&FIBLock
, &OldIrql
);
365 CurrentEntry
= FIBListHead
.Flink
;
366 while (CurrentEntry
!= &FIBListHead
) {
367 NextEntry
= CurrentEntry
->Flink
;
368 Current
= CONTAINING_RECORD(CurrentEntry
, FIB_ENTRY
, ListEntry
);
370 NCE
= Current
->Router
;
372 if( AddrIsEqual( &Current
->NetworkAddress
, Target
) &&
373 AddrIsEqual( &NCE
->Address
, Router
) ) {
379 CurrentEntry
= NextEntry
;
383 TI_DbgPrint(DEBUG_ROUTER
, ("Deleting route\n"));
384 DestroyFIBE( Current
);
389 TcpipReleaseSpinLock(&FIBLock
, OldIrql
);
391 TI_DbgPrint(DEBUG_ROUTER
, ("Leaving\n"));
393 return Found
? STATUS_SUCCESS
: STATUS_UNSUCCESSFUL
;
397 PFIB_ENTRY
RouterCreateRoute(
398 PIP_ADDRESS NetworkAddress
,
400 PIP_ADDRESS RouterAddress
,
401 PIP_INTERFACE Interface
,
404 * FUNCTION: Creates a route with IPv4 addresses as parameters
406 * NetworkAddress = Address of network
407 * Netmask = Netmask of network
408 * RouterAddress = Address of router to use
409 * NTE = Pointer to NTE to use
410 * Metric = Cost of this route
412 * Pointer to FIB entry if the route was created, NULL if not.
413 * The FIB entry references the NTE. The caller is responsible
414 * for providing this reference
419 PLIST_ENTRY CurrentEntry
;
420 PLIST_ENTRY NextEntry
;
422 PNEIGHBOR_CACHE_ENTRY NCE
;
424 TcpipAcquireSpinLock(&FIBLock
, &OldIrql
);
426 CurrentEntry
= FIBListHead
.Flink
;
427 while (CurrentEntry
!= &FIBListHead
) {
428 NextEntry
= CurrentEntry
->Flink
;
429 Current
= CONTAINING_RECORD(CurrentEntry
, FIB_ENTRY
, ListEntry
);
431 NCE
= Current
->Router
;
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
);
440 CurrentEntry
= NextEntry
;
443 TcpipReleaseSpinLock(&FIBLock
, OldIrql
);
445 /* The NCE references RouterAddress. The NCE is referenced for us */
446 NCE
= NBFindOrCreateNeighbor(Interface
, RouterAddress
);
449 /* Not enough free resources */
453 FIBE
= RouterAddRoute(NetworkAddress
, Netmask
, NCE
, Metric
);
455 /* Not enough free resources */
456 NBRemoveNeighbor(NCE
);
463 NTSTATUS
RouterStartup(
466 * FUNCTION: Initializes the routing subsystem
468 * Status of operation
471 TI_DbgPrint(DEBUG_ROUTER
, ("Called.\n"));
473 /* Initialize the Forward Information Base */
474 InitializeListHead(&FIBListHead
);
475 TcpipInitializeSpinLock(&FIBLock
);
477 return STATUS_SUCCESS
;
481 NTSTATUS
RouterShutdown(
484 * FUNCTION: Shuts down the routing subsystem
486 * Status of operation
491 TI_DbgPrint(DEBUG_ROUTER
, ("Called.\n"));
493 /* Clear Forward Information Base */
494 TcpipAcquireSpinLock(&FIBLock
, &OldIrql
);
496 TcpipReleaseSpinLock(&FIBLock
, OldIrql
);
498 return STATUS_SUCCESS
;