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
;
25 * FUNCTION: Frees an forward information base object
27 * Object = Pointer to an forward information base structure
30 PoolFreeBuffer(Object
);
37 * FUNCTION: Destroys an forward information base entry
39 * FIBE = Pointer to FIB entry
41 * The forward information base lock must be held when called
44 TI_DbgPrint(DEBUG_ROUTER
, ("Called. FIBE (0x%X).\n", FIBE
));
46 /* Unlink the FIB entry from the list */
47 RemoveEntryList(&FIBE
->ListEntry
);
49 /* And free the FIB entry */
57 * FUNCTION: Destroys all forward information base entries
59 * The forward information base lock must be held when called
62 PLIST_ENTRY CurrentEntry
;
63 PLIST_ENTRY NextEntry
;
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 */
73 CurrentEntry
= NextEntry
;
80 PLIST_ENTRY CurrentEntry
;
81 PLIST_ENTRY NextEntry
;
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
;
95 UINT
CopyFIBs( PFIB_ENTRY Target
) {
97 PLIST_ENTRY CurrentEntry
;
98 PLIST_ENTRY NextEntry
;
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
;
115 UINT
CommonPrefixLength(
116 PIP_ADDRESS Address1
,
117 PIP_ADDRESS Address2
)
119 * FUNCTION: Computes the length of the longest prefix common to two addresses
121 * Address1 = Pointer to first address
122 * Address2 = Pointer to second address
124 * The two addresses must be of the same type
126 * Length of longest common prefix
134 TI_DbgPrint(DEBUG_ROUTER
, ("Called. Address1 (0x%X) Address2 (0x%X).\n", Address1
, Address2
));
136 /*TI_DbgPrint(DEBUG_ROUTER, ("Target (%s) \n", A2S(Address1)));*/
137 /*TI_DbgPrint(DEBUG_ROUTER, ("Adapter (%s).\n", A2S(Address2)));*/
139 if (Address1
->Type
== IP_ADDRESS_V4
)
140 Size
= sizeof(IPv4_RAW_ADDRESS
);
142 Size
= sizeof(IPv6_RAW_ADDRESS
);
144 Addr1
= (PUCHAR
)&Address1
->Address
.IPv4Address
;
145 Addr2
= (PUCHAR
)&Address2
->Address
.IPv4Address
;
147 /* Find first non-matching byte */
148 for (i
= 0; i
< Size
&& Addr1
[i
] == Addr2
[i
]; i
++);
149 if( i
== Size
) return 8 * i
;
151 /* Find first non-matching bit */
153 for (j
= 0; (Addr1
[i
] & Bitmask
) == (Addr2
[i
] & Bitmask
); j
++)
156 TI_DbgPrint(DEBUG_ROUTER
, ("Returning %d\n", 8 * i
+ j
));
162 PFIB_ENTRY
RouterAddRoute(
163 PIP_ADDRESS NetworkAddress
,
165 PNEIGHBOR_CACHE_ENTRY Router
,
168 * FUNCTION: Adds a route to the Forward Information Base (FIB)
170 * NetworkAddress = Pointer to address of network
171 * Netmask = Pointer to netmask of network
172 * Router = Pointer to NCE of router to use
173 * Metric = Cost of this route
175 * Pointer to FIB entry if the route was added, NULL if not
177 * The FIB entry references the NetworkAddress, Netmask and
178 * the NCE of the router. The caller is responsible for providing
184 TI_DbgPrint(DEBUG_ROUTER
, ("Called. NetworkAddress (0x%X) Netmask (0x%X) "
185 "Router (0x%X) Metric (%d).\n", NetworkAddress
, Netmask
, Router
, Metric
));
187 TI_DbgPrint(DEBUG_ROUTER
, ("NetworkAddress (%s) Netmask (%s) Router (%s).\n",
190 A2S(&Router
->Address
)));
192 FIBE
= PoolAllocateBuffer(sizeof(FIB_ENTRY
));
194 TI_DbgPrint(MIN_TRACE
, ("Insufficient resources.\n"));
198 INIT_TAG(Router
, TAG('R','O','U','T'));
200 RtlCopyMemory( &FIBE
->NetworkAddress
, NetworkAddress
,
201 sizeof(FIBE
->NetworkAddress
) );
202 RtlCopyMemory( &FIBE
->Netmask
, Netmask
,
203 sizeof(FIBE
->Netmask
) );
204 FIBE
->Router
= Router
;
205 FIBE
->Metric
= Metric
;
207 /* Add FIB to the forward information base */
208 TcpipInterlockedInsertTailList(&FIBListHead
, &FIBE
->ListEntry
, &FIBLock
);
214 PNEIGHBOR_CACHE_ENTRY
RouterGetRoute(PIP_ADDRESS Destination
)
216 * FUNCTION: Finds a router to use to get to Destination
218 * Destination = Pointer to destination address (NULL means don't care)
220 * Pointer to NCE for router, NULL if none was found
222 * If found the NCE is referenced
226 PLIST_ENTRY CurrentEntry
;
227 PLIST_ENTRY NextEntry
;
229 UCHAR State
, BestState
= 0;
230 UINT Length
, BestLength
= 0, MaskLength
;
231 PNEIGHBOR_CACHE_ENTRY NCE
, BestNCE
= NULL
;
233 TI_DbgPrint(DEBUG_ROUTER
, ("Called. Destination (0x%X)\n", Destination
));
235 TI_DbgPrint(DEBUG_ROUTER
, ("Destination (%s)\n", A2S(Destination
)));
237 TcpipAcquireSpinLock(&FIBLock
, &OldIrql
);
239 CurrentEntry
= FIBListHead
.Flink
;
240 while (CurrentEntry
!= &FIBListHead
) {
241 NextEntry
= CurrentEntry
->Flink
;
242 Current
= CONTAINING_RECORD(CurrentEntry
, FIB_ENTRY
, ListEntry
);
244 NCE
= Current
->Router
;
247 Length
= CommonPrefixLength(Destination
, &Current
->NetworkAddress
);
248 MaskLength
= AddrCountPrefixBits(&Current
->Netmask
);
250 TI_DbgPrint(DEBUG_ROUTER
,("This-Route: %s (Sharing %d bits)\n",
251 A2S(&NCE
->Address
), Length
));
253 if(Length
>= MaskLength
&& (Length
> BestLength
|| !BestLength
)) {
254 /* This seems to be a better router */
258 TI_DbgPrint(DEBUG_ROUTER
,("Route selected\n"));
261 CurrentEntry
= NextEntry
;
264 TcpipReleaseSpinLock(&FIBLock
, OldIrql
);
267 TI_DbgPrint(DEBUG_ROUTER
,("Routing to %s\n", A2S(&BestNCE
->Address
)));
269 TI_DbgPrint(DEBUG_ROUTER
,("Packet won't be routed\n"));
275 PNEIGHBOR_CACHE_ENTRY
RouteGetRouteToDestination(PIP_ADDRESS Destination
)
277 * FUNCTION: Locates an RCN describing a route to a destination address
279 * Destination = Pointer to destination address to find route to
280 * RCN = Address of pointer to an RCN
282 * Status of operation
284 * The RCN is referenced for the caller. The caller is responsible
285 * for dereferencing it after use
288 PNEIGHBOR_CACHE_ENTRY NCE
= NULL
;
289 PIP_INTERFACE Interface
;
291 TI_DbgPrint(DEBUG_RCACHE
, ("Called. Destination (0x%X)\n", Destination
));
293 TI_DbgPrint(DEBUG_RCACHE
, ("Destination (%s)\n", A2S(Destination
)));
296 TI_DbgPrint(MIN_TRACE
, ("Displaying tree (before).\n"));
297 PrintTree(RouteCache
);
300 /* Check if the destination is on-link */
301 Interface
= FindOnLinkInterface(Destination
);
303 /* The destination address is on-link. Check our neighbor cache */
304 NCE
= NBFindOrCreateNeighbor(Interface
, Destination
);
306 /* Destination is not on any subnets we're on. Find a router to use */
307 NCE
= RouterGetRoute(Destination
);
311 TI_DbgPrint(DEBUG_ROUTER
,("Interface->MTU: %d\n", NCE
->Interface
->MTU
));
316 NTSTATUS
RouterRemoveRoute(PIP_ADDRESS Target
, PIP_ADDRESS Router
)
318 * FUNCTION: Removes a route from the Forward Information Base (FIB)
320 * Target: The machine or network targeted by the route
321 * Router: The router used to pass the packet to the destination
323 * Searches the FIB and removes a route matching the indicated parameters.
327 PLIST_ENTRY CurrentEntry
;
328 PLIST_ENTRY NextEntry
;
330 BOOLEAN Found
= FALSE
;
331 PNEIGHBOR_CACHE_ENTRY NCE
;
333 TI_DbgPrint(DEBUG_ROUTER
, ("Called\n"));
335 TcpipAcquireSpinLock(&FIBLock
, &OldIrql
);
337 CurrentEntry
= FIBListHead
.Flink
;
338 while (CurrentEntry
!= &FIBListHead
) {
339 NextEntry
= CurrentEntry
->Flink
;
340 Current
= CONTAINING_RECORD(CurrentEntry
, FIB_ENTRY
, ListEntry
);
342 NCE
= Current
->Router
;
344 if( AddrIsEqual( &Current
->NetworkAddress
, Target
) &&
345 AddrIsEqual( &NCE
->Address
, Router
) ) {
351 CurrentEntry
= NextEntry
;
355 TI_DbgPrint(DEBUG_ROUTER
, ("Deleting route\n"));
356 DestroyFIBE( Current
);
359 TcpipReleaseSpinLock(&FIBLock
, OldIrql
);
361 TI_DbgPrint(DEBUG_ROUTER
, ("Leaving\n"));
363 return Found
? STATUS_NO_SUCH_FILE
: STATUS_SUCCESS
;
367 PFIB_ENTRY
RouterCreateRoute(
368 PIP_ADDRESS NetworkAddress
,
370 PIP_ADDRESS RouterAddress
,
371 PIP_INTERFACE Interface
,
374 * FUNCTION: Creates a route with IPv4 addresses as parameters
376 * NetworkAddress = Address of network
377 * Netmask = Netmask of network
378 * RouterAddress = Address of router to use
379 * NTE = Pointer to NTE to use
380 * Metric = Cost of this route
382 * Pointer to FIB entry if the route was created, NULL if not.
383 * The FIB entry references the NTE. The caller is responsible
384 * for providing this reference
387 PNEIGHBOR_CACHE_ENTRY NCE
;
390 /* The NCE references RouterAddress. The NCE is referenced for us */
391 NCE
= NBFindOrCreateNeighbor(Interface
, RouterAddress
);
394 /* Not enough free resources */
398 FIBE
= RouterAddRoute(NetworkAddress
, Netmask
, NCE
, Metric
);
400 /* Not enough free resources */
401 NBRemoveNeighbor(NCE
);
408 NTSTATUS
RouterStartup(
411 * FUNCTION: Initializes the routing subsystem
413 * Status of operation
416 TI_DbgPrint(DEBUG_ROUTER
, ("Called.\n"));
418 /* Initialize the Forward Information Base */
419 InitializeListHead(&FIBListHead
);
420 TcpipInitializeSpinLock(&FIBLock
);
422 return STATUS_SUCCESS
;
426 NTSTATUS
RouterShutdown(
429 * FUNCTION: Shuts down the routing subsystem
431 * Status of operation
436 TI_DbgPrint(DEBUG_ROUTER
, ("Called.\n"));
438 /* Clear Forward Information Base */
439 TcpipAcquireSpinLock(&FIBLock
, &OldIrql
);
441 TcpipReleaseSpinLock(&FIBLock
, OldIrql
);
443 return STATUS_SUCCESS
;