- Removed prefix.c and the prefix list. Adapter and route netmasks are now
[reactos.git] / reactos / drivers / lib / ip / network / neighbor.c
1 /*
2 * COPYRIGHT: See COPYING in the top level directory
3 * PROJECT: ReactOS TCP/IP protocol driver
4 * FILE: network/neighbor.c
5 * PURPOSE: Neighbor address cache
6 * PROGRAMMERS: Casper S. Hornstrup (chorns@users.sourceforge.net)
7 * REVISIONS:
8 * CSH 01/08-2000 Created
9 */
10
11 #include "precomp.h"
12
13 NEIGHBOR_CACHE_TABLE NeighborCache[NB_HASHMASK + 1];
14
15 VOID NBCompleteSend( PVOID Context,
16 PNDIS_PACKET NdisPacket,
17 NDIS_STATUS Status ) {
18 PNEIGHBOR_PACKET Packet = (PNEIGHBOR_PACKET)Context;
19 TI_DbgPrint(MID_TRACE, ("Called\n"));
20 ASSERT_KM_POINTER(Packet);
21 ASSERT_KM_POINTER(Packet->Complete);
22 Packet->Complete( Packet->Context, Packet->Packet, STATUS_SUCCESS );
23 TI_DbgPrint(MID_TRACE, ("Completed\n"));
24 PoolFreeBuffer( Packet );
25 TI_DbgPrint(MID_TRACE, ("Freed\n"));
26 }
27
28 VOID NBSendPackets( PNEIGHBOR_CACHE_ENTRY NCE ) {
29 PLIST_ENTRY PacketEntry;
30 PNEIGHBOR_PACKET Packet;
31
32 /* Send any waiting packets */
33 if( !IsListEmpty( &NCE->PacketQueue ) ) {
34 PacketEntry = RemoveHeadList( &NCE->PacketQueue );
35 Packet = CONTAINING_RECORD( PacketEntry, NEIGHBOR_PACKET, Next );
36
37 TI_DbgPrint
38 (MID_TRACE,
39 ("PacketEntry: %x, NdisPacket %x\n",
40 PacketEntry, Packet->Packet));
41
42 PC(Packet->Packet)->DLComplete = NBCompleteSend;
43 PC(Packet->Packet)->Context = Packet;
44
45 NCE->Interface->Transmit
46 ( NCE->Interface->Context,
47 Packet->Packet,
48 MaxLLHeaderSize,
49 NCE->LinkAddress,
50 LAN_PROTO_IPv4 );
51 }
52 }
53
54 VOID NBFlushPacketQueue( PNEIGHBOR_CACHE_ENTRY NCE,
55 BOOL CallComplete,
56 NTSTATUS ErrorCode ) {
57 PLIST_ENTRY PacketEntry;
58 PNEIGHBOR_PACKET Packet;
59
60 while( !IsListEmpty( &NCE->PacketQueue ) ) {
61 PacketEntry = RemoveHeadList( &NCE->PacketQueue );
62 Packet = CONTAINING_RECORD
63 ( PacketEntry, NEIGHBOR_PACKET, Next );
64
65 ASSERT_KM_POINTER(Packet);
66
67 TI_DbgPrint
68 (MID_TRACE,
69 ("PacketEntry: %x, NdisPacket %x\n",
70 PacketEntry, Packet->Packet));
71
72 if( CallComplete )
73 {
74 ASSERT_KM_POINTER(Packet->Complete);
75 Packet->Complete( Packet->Context,
76 Packet->Packet,
77 NDIS_STATUS_REQUEST_ABORTED );
78 }
79
80 PoolFreeBuffer( Packet );
81 }
82 }
83
84 VOID NCETimeout(
85 PNEIGHBOR_CACHE_ENTRY NCE)
86 /*
87 * FUNCTION: Neighbor cache entry timeout handler
88 * NOTES:
89 * The neighbor cache lock must be held
90 */
91 {
92 TI_DbgPrint(DEBUG_NCACHE, ("Called. NCE (0x%X).\n", NCE));
93 TI_DbgPrint(DEBUG_NCACHE, ("NCE->State is (0x%X).\n", NCE->State));
94
95 switch (NCE->State)
96 {
97 case NUD_INCOMPLETE:
98 /* Retransmission timer expired */
99 if (NCE->EventCount++ > MAX_MULTICAST_SOLICIT)
100 {
101 /* We have retransmitted too many times */
102
103 /* Calling IPSendComplete with cache lock held is not
104 a great thing to do. We don't get here very often
105 so maybe it's not that big a problem */
106
107 /* Flush packet queue */
108 NBFlushPacketQueue( NCE, TRUE, NDIS_STATUS_REQUEST_ABORTED );
109 NCE->EventCount = 0;
110
111 /* Remove route cache entries with references to this NCE.
112 Remember that neighbor cache lock is acquired before the
113 route cache lock */
114 RouteInvalidateNCE(NCE);
115 }
116 else
117 {
118 /* Retransmit request */
119 NBSendSolicit(NCE);
120 }
121 break;
122
123 case NUD_DELAY:
124 /* FIXME: Delayed state */
125 TI_DbgPrint(DEBUG_NCACHE, ("NCE delay state.\n"));
126 break;
127
128 case NUD_PROBE:
129 /* FIXME: Probe state */
130 TI_DbgPrint(DEBUG_NCACHE, ("NCE probe state.\n"));
131 break;
132
133 default:
134 /* Should not happen since the event timer is not used in the other states */
135 TI_DbgPrint(MIN_TRACE, ("Invalid NCE state (%d).\n", NCE->State));
136 break;
137 }
138 }
139
140
141 VOID NBTimeout(VOID)
142 /*
143 * FUNCTION: Neighbor address cache timeout handler
144 * NOTES:
145 * This routine is called by IPTimeout to remove outdated cache
146 * entries.
147 */
148 {
149 UINT i;
150 KIRQL OldIrql;
151 PNEIGHBOR_CACHE_ENTRY NCE;
152
153 for (i = 0; i <= NB_HASHMASK; i++) {
154 TcpipAcquireSpinLock(&NeighborCache[i].Lock, &OldIrql);
155
156 for (NCE = NeighborCache[i].Cache;
157 NCE != NULL; NCE = NCE->Next) {
158 /* Check if event timer is running */
159 if (NCE->EventTimer > 0) {
160 NCE->EventTimer--;
161 if (NCE->EventTimer == 0) {
162 /* Call timeout handler for NCE */
163 NCETimeout(NCE);
164 }
165 }
166 }
167
168 TcpipReleaseSpinLock(&NeighborCache[i].Lock, OldIrql);
169 }
170 }
171
172 VOID NBStartup(VOID)
173 /*
174 * FUNCTION: Starts the neighbor cache
175 */
176 {
177 UINT i;
178
179 TI_DbgPrint(DEBUG_NCACHE, ("Called.\n"));
180
181 for (i = 0; i <= NB_HASHMASK; i++) {
182 NeighborCache[i].Cache = NULL;
183 TcpipInitializeSpinLock(&NeighborCache[i].Lock);
184 }
185 }
186
187 VOID NBShutdown(VOID)
188 /*
189 * FUNCTION: Shuts down the neighbor cache
190 */
191 {
192 PNEIGHBOR_CACHE_ENTRY NextNCE;
193 PNEIGHBOR_CACHE_ENTRY CurNCE;
194 KIRQL OldIrql;
195 UINT i;
196
197 TI_DbgPrint(DEBUG_NCACHE, ("Called.\n"));
198
199 /* Remove possible entries from the cache */
200 for (i = 0; i <= NB_HASHMASK; i++)
201 {
202 TcpipAcquireSpinLock(&NeighborCache[i].Lock, &OldIrql);
203
204 CurNCE = NeighborCache[i].Cache;
205 while (CurNCE) {
206 NextNCE = CurNCE->Next;
207
208 /* Remove all references from route cache */
209 RouteInvalidateNCE(CurNCE);
210
211 /* Flush wait queue */
212 NBFlushPacketQueue( CurNCE, FALSE, STATUS_SUCCESS );
213
214 CurNCE = NextNCE;
215 }
216
217 NeighborCache[i].Cache = NULL;
218
219 TcpipReleaseSpinLock(&NeighborCache[i].Lock, OldIrql);
220 }
221
222 TI_DbgPrint(MAX_TRACE, ("Leaving.\n"));
223 }
224
225 VOID NBSendSolicit(PNEIGHBOR_CACHE_ENTRY NCE)
226 /*
227 * FUNCTION: Sends a neighbor solicitation message
228 * ARGUMENTS:
229 * NCE = Pointer to NCE of neighbor to solicit
230 * NOTES:
231 * May be called with lock held on NCE's table
232 */
233 {
234 TI_DbgPrint(DEBUG_NCACHE, ("Called. NCE (0x%X).\n", NCE));
235
236 if (NCE->State == NUD_INCOMPLETE)
237 {
238 /* This is the first solicitation of this neighbor. Broadcast
239 a request for the neighbor */
240
241 TI_DbgPrint(MID_TRACE,("NCE: %x\n", NCE));
242
243 ARPTransmit(&NCE->Address, NCE->Interface);
244 } else {
245 /* FIXME: Unicast solicitation since we have a cached address */
246 TI_DbgPrint(MIN_TRACE, ("Uninplemented unicast solicitation.\n"));
247 }
248 }
249
250 PNEIGHBOR_CACHE_ENTRY NBAddNeighbor(
251 PIP_INTERFACE Interface,
252 PIP_ADDRESS Address,
253 PVOID LinkAddress,
254 UINT LinkAddressLength,
255 UCHAR State)
256 /*
257 * FUNCTION: Adds a neighbor to the neighbor cache
258 * ARGUMENTS:
259 * Interface = Pointer to interface
260 * Address = Pointer to IP address
261 * LinkAddress = Pointer to link address (may be NULL)
262 * LinkAddressLength = Length of link address
263 * State = State of NCE
264 * RETURNS:
265 * Pointer to NCE, NULL there is not enough free resources
266 * NOTES:
267 * The NCE if referenced for the caller if created. The NCE retains
268 * a reference to the IP address if it is created, the caller is
269 * responsible for providing this reference
270 */
271 {
272 PNEIGHBOR_CACHE_ENTRY NCE;
273 ULONG HashValue;
274 KIRQL OldIrql;
275
276 TI_DbgPrint
277 (DEBUG_NCACHE,
278 ("Called. Interface (0x%X) Address (0x%X) "
279 "LinkAddress (0x%X) LinkAddressLength (%d) State (0x%X)\n",
280 Interface, Address, LinkAddress, LinkAddressLength, State));
281
282 NCE = ExAllocatePool
283 (NonPagedPool, sizeof(NEIGHBOR_CACHE_ENTRY) + LinkAddressLength);
284 if (NCE == NULL)
285 {
286 TI_DbgPrint(MIN_TRACE, ("Insufficient resources.\n"));
287 return NULL;
288 }
289
290 INIT_TAG(NCE, TAG('N','C','E',' '));
291
292 NCE->Interface = Interface;
293 NCE->Address = *Address;
294 NCE->LinkAddressLength = LinkAddressLength;
295 NCE->LinkAddress = (PVOID)&NCE[1];
296 if( LinkAddress )
297 RtlCopyMemory(NCE->LinkAddress, LinkAddress, LinkAddressLength);
298 NCE->State = State;
299 NCE->EventTimer = 0; /* Not in use */
300 InitializeListHead( &NCE->PacketQueue );
301
302 TI_DbgPrint(MID_TRACE,("NCE: %x\n", NCE));
303
304 HashValue = *(PULONG)&Address->Address;
305 HashValue ^= HashValue >> 16;
306 HashValue ^= HashValue >> 8;
307 HashValue ^= HashValue >> 4;
308 HashValue &= NB_HASHMASK;
309
310 NCE->Table = &NeighborCache[HashValue];
311
312 TcpipAcquireSpinLock(&NeighborCache[HashValue].Lock, &OldIrql);
313
314 NCE->Next = NeighborCache[HashValue].Cache;
315 NeighborCache[HashValue].Cache = NCE;
316
317 TcpipReleaseSpinLock(&NeighborCache[HashValue].Lock, OldIrql);
318
319 return NCE;
320 }
321
322 VOID NBUpdateNeighbor(
323 PNEIGHBOR_CACHE_ENTRY NCE,
324 PVOID LinkAddress,
325 UCHAR State)
326 /*
327 * FUNCTION: Update link address information in NCE
328 * ARGUMENTS:
329 * NCE = Pointer to NCE to update
330 * LinkAddress = Pointer to link address
331 * State = State of NCE
332 * NOTES:
333 * The link address and state is updated. Any waiting packets are sent
334 */
335 {
336 KIRQL OldIrql;
337
338 TI_DbgPrint(DEBUG_NCACHE, ("Called. NCE (0x%X) LinkAddress (0x%X) State (0x%X).\n", NCE, LinkAddress, State));
339
340 TcpipAcquireSpinLock(&NCE->Table->Lock, &OldIrql);
341
342 RtlCopyMemory(NCE->LinkAddress, LinkAddress, NCE->LinkAddressLength);
343 NCE->State = State;
344
345 TcpipReleaseSpinLock(&NCE->Table->Lock, OldIrql);
346
347 if( NCE->State & NUD_CONNECTED )
348 NBSendPackets( NCE );
349 }
350
351 PNEIGHBOR_CACHE_ENTRY NBLocateNeighbor(
352 PIP_ADDRESS Address)
353 /*
354 * FUNCTION: Locates a neighbor in the neighbor cache
355 * ARGUMENTS:
356 * Address = Pointer to IP address
357 * RETURNS:
358 * Pointer to NCE, NULL if not found
359 * NOTES:
360 * If the NCE is found, it is referenced. The caller is
361 * responsible for dereferencing it again after use
362 */
363 {
364 PNEIGHBOR_CACHE_ENTRY NCE;
365 UINT HashValue;
366 KIRQL OldIrql;
367
368 TI_DbgPrint(DEBUG_NCACHE, ("Called. Address (0x%X).\n", Address));
369
370 HashValue = *(PULONG)&Address->Address;
371 HashValue ^= HashValue >> 16;
372 HashValue ^= HashValue >> 8;
373 HashValue ^= HashValue >> 4;
374 HashValue &= NB_HASHMASK;
375
376 TcpipAcquireSpinLock(&NeighborCache[HashValue].Lock, &OldIrql);
377
378 NCE = NeighborCache[HashValue].Cache;
379
380 while ((NCE) && (!AddrIsEqual(Address, &NCE->Address)))
381 {
382 NCE = NCE->Next;
383 }
384
385 TcpipReleaseSpinLock(&NeighborCache[HashValue].Lock, OldIrql);
386
387 TI_DbgPrint(MAX_TRACE, ("Leaving.\n"));
388
389 return NCE;
390 }
391
392 PNEIGHBOR_CACHE_ENTRY NBFindOrCreateNeighbor(
393 PIP_INTERFACE Interface,
394 PIP_ADDRESS Address)
395 /*
396 * FUNCTION: Tries to find a neighbor and if unsuccesful, creates a new NCE
397 * ARGUMENTS:
398 * Interface = Pointer to interface to use (in case NCE is not found)
399 * Address = Pointer to IP address
400 * RETURNS:
401 * Pointer to NCE, NULL if there is not enough free resources
402 * NOTES:
403 * The NCE is referenced if found or created. The caller is
404 * responsible for dereferencing it again after use
405 */
406 {
407 PNEIGHBOR_CACHE_ENTRY NCE;
408
409 TI_DbgPrint(DEBUG_NCACHE, ("Called. Interface (0x%X) Address (0x%X).\n", Interface, Address));
410
411 NCE = NBLocateNeighbor(Address);
412 if (NCE == NULL)
413 {
414 NCE = NBAddNeighbor(Interface, Address, NULL,
415 Interface->AddressLength, NUD_INCOMPLETE);
416 NCE->EventTimer = 1;
417 NCE->EventCount = 0;
418 }
419
420 return NCE;
421 }
422
423 BOOLEAN NBQueuePacket(
424 PNEIGHBOR_CACHE_ENTRY NCE,
425 PNDIS_PACKET NdisPacket,
426 PNEIGHBOR_PACKET_COMPLETE PacketComplete,
427 PVOID PacketContext)
428 /*
429 * FUNCTION: Queues a packet on an NCE for later transmission
430 * ARGUMENTS:
431 * NCE = Pointer to NCE to queue packet on
432 * NdisPacket = Pointer to NDIS packet to queue
433 * RETURNS:
434 * TRUE if the packet was successfully queued, FALSE if not
435 */
436 {
437 PKSPIN_LOCK Lock;
438 KIRQL OldIrql;
439 PNEIGHBOR_PACKET Packet;
440
441 TI_DbgPrint
442 (DEBUG_NCACHE,
443 ("Called. NCE (0x%X) NdisPacket (0x%X).\n", NCE, NdisPacket));
444
445 Packet = PoolAllocateBuffer( sizeof(NEIGHBOR_PACKET) );
446 if( !Packet ) return FALSE;
447
448 /* FIXME: Should we limit the number of queued packets? */
449
450 Lock = &NCE->Table->Lock;
451
452 TcpipAcquireSpinLock(Lock, &OldIrql);
453
454 Packet->Complete = PacketComplete;
455 Packet->Context = PacketContext;
456 Packet->Packet = NdisPacket;
457 InsertTailList( &NCE->PacketQueue, &Packet->Next );
458
459 if( NCE->State & NUD_CONNECTED )
460 NBSendPackets( NCE );
461
462 TcpipReleaseSpinLock(Lock, OldIrql);
463
464 return TRUE;
465 }
466
467
468 VOID NBRemoveNeighbor(
469 PNEIGHBOR_CACHE_ENTRY NCE)
470 /*
471 * FUNCTION: Removes a neighbor from the neighbor cache
472 * ARGUMENTS:
473 * NCE = Pointer to NCE to remove from cache
474 * NOTES:
475 * The NCE must be in a safe state
476 */
477 {
478 PNEIGHBOR_CACHE_ENTRY *PrevNCE;
479 PNEIGHBOR_CACHE_ENTRY CurNCE;
480 ULONG HashValue;
481 KIRQL OldIrql;
482
483 TI_DbgPrint(DEBUG_NCACHE, ("Called. NCE (0x%X).\n", NCE));
484
485 HashValue = *(PULONG)(&NCE->Address.Address);
486 HashValue ^= HashValue >> 16;
487 HashValue ^= HashValue >> 8;
488 HashValue ^= HashValue >> 4;
489 HashValue &= NB_HASHMASK;
490
491 TcpipAcquireSpinLock(&NeighborCache[HashValue].Lock, &OldIrql);
492
493 /* Search the list and remove the NCE from the list if found */
494 for (PrevNCE = &NeighborCache[HashValue].Cache;
495 (CurNCE = *PrevNCE) != NULL;
496 PrevNCE = &CurNCE->Next)
497 {
498 if (CurNCE == NCE)
499 {
500 /* Found it, now unlink it from the list */
501 *PrevNCE = CurNCE->Next;
502
503 NBFlushPacketQueue( CurNCE, TRUE, NDIS_STATUS_REQUEST_ABORTED );
504
505 /* Remove all references from route cache */
506 RouteInvalidateNCE(CurNCE);
507 ExFreePool(CurNCE);
508
509 break;
510 }
511 }
512
513 TcpipReleaseSpinLock(&NeighborCache[HashValue].Lock, OldIrql);
514 }