- Removed prefix.c and the prefix list. Adapter and route netmasks are now
[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 TI_DbgPrint(DEBUG_ROUTER, ("Returning %d\n", 8 * i + j));
157
158 return 8 * i + j;
159 }
160
161
162 PFIB_ENTRY RouterAddRoute(
163 PIP_ADDRESS NetworkAddress,
164 PIP_ADDRESS Netmask,
165 PNEIGHBOR_CACHE_ENTRY Router,
166 UINT Metric)
167 /*
168 * FUNCTION: Adds a route to the Forward Information Base (FIB)
169 * ARGUMENTS:
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
174 * RETURNS:
175 * Pointer to FIB entry if the route was added, NULL if not
176 * NOTES:
177 * The FIB entry references the NetworkAddress, Netmask and
178 * the NCE of the router. The caller is responsible for providing
179 * these references
180 */
181 {
182 PFIB_ENTRY FIBE;
183
184 TI_DbgPrint(DEBUG_ROUTER, ("Called. NetworkAddress (0x%X) Netmask (0x%X) "
185 "Router (0x%X) Metric (%d).\n", NetworkAddress, Netmask, Router, Metric));
186
187 TI_DbgPrint(DEBUG_ROUTER, ("NetworkAddress (%s) Netmask (%s) Router (%s).\n",
188 A2S(NetworkAddress),
189 A2S(Netmask),
190 A2S(&Router->Address)));
191
192 FIBE = PoolAllocateBuffer(sizeof(FIB_ENTRY));
193 if (!FIBE) {
194 TI_DbgPrint(MIN_TRACE, ("Insufficient resources.\n"));
195 return NULL;
196 }
197
198 INIT_TAG(Router, TAG('R','O','U','T'));
199
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;
206
207 /* Add FIB to the forward information base */
208 TcpipInterlockedInsertTailList(&FIBListHead, &FIBE->ListEntry, &FIBLock);
209
210 return FIBE;
211 }
212
213
214 PNEIGHBOR_CACHE_ENTRY RouterGetRoute(PIP_ADDRESS Destination)
215 /*
216 * FUNCTION: Finds a router to use to get to Destination
217 * ARGUMENTS:
218 * Destination = Pointer to destination address (NULL means don't care)
219 * RETURNS:
220 * Pointer to NCE for router, NULL if none was found
221 * NOTES:
222 * If found the NCE is referenced
223 */
224 {
225 KIRQL OldIrql;
226 PLIST_ENTRY CurrentEntry;
227 PLIST_ENTRY NextEntry;
228 PFIB_ENTRY Current;
229 UCHAR State, BestState = 0;
230 UINT Length, BestLength = 0;
231 PNEIGHBOR_CACHE_ENTRY NCE, BestNCE = NULL;
232
233 TI_DbgPrint(DEBUG_ROUTER, ("Called. Destination (0x%X)\n", Destination));
234
235 TI_DbgPrint(DEBUG_ROUTER, ("Destination (%s)\n", A2S(Destination)));
236
237 TcpipAcquireSpinLock(&FIBLock, &OldIrql);
238
239 CurrentEntry = FIBListHead.Flink;
240 while (CurrentEntry != &FIBListHead) {
241 NextEntry = CurrentEntry->Flink;
242 Current = CONTAINING_RECORD(CurrentEntry, FIB_ENTRY, ListEntry);
243
244 NCE = Current->Router;
245 State = NCE->State;
246
247 if (Destination)
248 Length = CommonPrefixLength(Destination, &NCE->Address);
249 else
250 Length = 0;
251
252 if (BestNCE) {
253 if ((State > BestState) ||
254 ((State == BestState) &&
255 (Length > BestLength))) {
256 /* This seems to be a better router */
257 BestNCE = NCE;
258 BestLength = Length;
259 BestState = State;
260 }
261 } else {
262 /* First suitable router found, save it */
263 BestNCE = NCE;
264 BestLength = Length;
265 BestState = State;
266 }
267
268 CurrentEntry = NextEntry;
269 }
270
271 TcpipReleaseSpinLock(&FIBLock, OldIrql);
272
273 return BestNCE;
274 }
275
276
277 VOID RouterRemoveRoute(
278 PFIB_ENTRY FIBE)
279 /*
280 * FUNCTION: Removes a route from the Forward Information Base (FIB)
281 * ARGUMENTS:
282 * FIBE = Pointer to FIB entry describing route
283 */
284 {
285 KIRQL OldIrql;
286
287 TI_DbgPrint(DEBUG_ROUTER, ("Called. FIBE (0x%X).\n", FIBE));
288
289 TI_DbgPrint(DEBUG_ROUTER, ("FIBE (%s).\n", A2S(&FIBE->NetworkAddress)));
290
291 TcpipAcquireSpinLock(&FIBLock, &OldIrql);
292 DestroyFIBE(FIBE);
293 TcpipReleaseSpinLock(&FIBLock, OldIrql);
294 }
295
296
297 PFIB_ENTRY RouterCreateRoute(
298 IP_ADDRESS NetworkAddress,
299 IP_ADDRESS Netmask,
300 IP_ADDRESS RouterAddress,
301 PIP_INTERFACE Interface,
302 UINT Metric)
303 /*
304 * FUNCTION: Creates a route with IPv4 addresses as parameters
305 * ARGUMENTS:
306 * NetworkAddress = Address of network
307 * Netmask = Netmask of network
308 * RouterAddress = Address of router to use
309 * NTE = Pointer to NTE to use
310 * Metric = Cost of this route
311 * RETURNS:
312 * Pointer to FIB entry if the route was created, NULL if not.
313 * The FIB entry references the NTE. The caller is responsible
314 * for providing this reference
315 */
316 {
317 PNEIGHBOR_CACHE_ENTRY NCE;
318 PFIB_ENTRY FIBE;
319
320 /* The NCE references RouterAddress. The NCE is referenced for us */
321 NCE = NBAddNeighbor(Interface,
322 &RouterAddress,
323 NULL,
324 Interface->AddressLength,
325 NUD_PROBE);
326 if (!NCE) {
327 /* Not enough free resources */
328 return NULL;
329 }
330
331 FIBE = RouterAddRoute(&NetworkAddress, &Netmask, NCE, 1);
332 if (!FIBE) {
333 /* Not enough free resources */
334 NBRemoveNeighbor(NCE);
335 }
336
337 return FIBE;
338 }
339
340
341 NTSTATUS RouterStartup(
342 VOID)
343 /*
344 * FUNCTION: Initializes the routing subsystem
345 * RETURNS:
346 * Status of operation
347 */
348 {
349 TI_DbgPrint(DEBUG_ROUTER, ("Called.\n"));
350
351 /* Initialize the Forward Information Base */
352 InitializeListHead(&FIBListHead);
353 TcpipInitializeSpinLock(&FIBLock);
354
355 #if 0
356 /* TEST: Create a test route */
357 /* Network is 10.0.0.0 */
358 /* Netmask is 255.0.0.0 */
359 /* Router is 10.0.0.1 */
360 RouterCreateRouteIPv4(0x0000000A, 0x000000FF, 0x0100000A, NTE?, 1);
361 #endif
362 return STATUS_SUCCESS;
363 }
364
365
366 NTSTATUS RouterShutdown(
367 VOID)
368 /*
369 * FUNCTION: Shuts down the routing subsystem
370 * RETURNS:
371 * Status of operation
372 */
373 {
374 KIRQL OldIrql;
375
376 TI_DbgPrint(DEBUG_ROUTER, ("Called.\n"));
377
378 /* Clear Forward Information Base */
379 TcpipAcquireSpinLock(&FIBLock, &OldIrql);
380 DestroyFIBEs();
381 TcpipReleaseSpinLock(&FIBLock, OldIrql);
382
383 return STATUS_SUCCESS;
384 }
385
386 /* EOF */