07e7e8cbe627227e5163b7b6ada24d2f20049239
[reactos.git] / lib / drivers / 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 );
23 TI_DbgPrint(MID_TRACE, ("Completed\n"));
24 ExFreePoolWithTag( Packet, NEIGHBOR_PACKET_TAG );
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 UINT HashValue;
32
33 ASSERT(!(NCE->State & NUD_INCOMPLETE));
34
35 HashValue = *(PULONG)(&NCE->Address.Address);
36 HashValue ^= HashValue >> 16;
37 HashValue ^= HashValue >> 8;
38 HashValue ^= HashValue >> 4;
39 HashValue &= NB_HASHMASK;
40
41 /* Send any waiting packets */
42 while ((PacketEntry = ExInterlockedRemoveHeadList(&NCE->PacketQueue,
43 &NeighborCache[HashValue].Lock)) != NULL)
44 {
45 Packet = CONTAINING_RECORD( PacketEntry, NEIGHBOR_PACKET, Next );
46
47 TI_DbgPrint
48 (MID_TRACE,
49 ("PacketEntry: %x, NdisPacket %x\n",
50 PacketEntry, Packet->Packet));
51
52 PC(Packet->Packet)->DLComplete = NBCompleteSend;
53 PC(Packet->Packet)->Context = Packet;
54
55 NCE->Interface->Transmit
56 ( NCE->Interface->Context,
57 Packet->Packet,
58 0,
59 NCE->LinkAddress,
60 LAN_PROTO_IPv4 );
61 }
62 }
63
64 /* Must be called with table lock acquired */
65 VOID NBFlushPacketQueue( PNEIGHBOR_CACHE_ENTRY NCE,
66 NTSTATUS ErrorCode ) {
67 PLIST_ENTRY PacketEntry;
68 PNEIGHBOR_PACKET Packet;
69
70 while( !IsListEmpty(&NCE->PacketQueue) ) {
71 PacketEntry = RemoveHeadList(&NCE->PacketQueue);
72 Packet = CONTAINING_RECORD
73 ( PacketEntry, NEIGHBOR_PACKET, Next );
74
75 ASSERT_KM_POINTER(Packet);
76
77 TI_DbgPrint
78 (MID_TRACE,
79 ("PacketEntry: %x, NdisPacket %x\n",
80 PacketEntry, Packet->Packet));
81
82 ASSERT_KM_POINTER(Packet->Complete);
83 Packet->Complete( Packet->Context,
84 Packet->Packet,
85 ErrorCode );
86
87 ExFreePoolWithTag( Packet, NEIGHBOR_PACKET_TAG );
88 }
89 }
90
91 VOID NBTimeout(VOID)
92 /*
93 * FUNCTION: Neighbor address cache timeout handler
94 * NOTES:
95 * This routine is called by IPTimeout to remove outdated cache
96 * entries.
97 */
98 {
99 UINT i;
100 PNEIGHBOR_CACHE_ENTRY *PrevNCE;
101 PNEIGHBOR_CACHE_ENTRY NCE;
102 NDIS_STATUS Status;
103
104 for (i = 0; i <= NB_HASHMASK; i++) {
105 TcpipAcquireSpinLockAtDpcLevel(&NeighborCache[i].Lock);
106
107 for (PrevNCE = &NeighborCache[i].Cache;
108 (NCE = *PrevNCE) != NULL;) {
109 /* Check if event timer is running */
110 if (NCE->EventTimer > 0) {
111 ASSERT(!(NCE->State & NUD_PERMANENT));
112 NCE->EventCount++;
113 if (NCE->State & NUD_INCOMPLETE)
114 {
115 /* We desperately need an address in this state or
116 * we timeout in 5 seconds */
117 NBSendSolicit(NCE);
118 }
119 else if ((NCE->EventCount > ARP_RATE &&
120 NCE->EventCount % ARP_TIMEOUT_RETRANSMISSION == 0) ||
121 (NCE->EventCount == ARP_RATE))
122 {
123 /* We haven't gotten a packet from them in
124 * EventCount seconds so we mark them as stale
125 * and solicit now */
126 NCE->State |= NUD_STALE;
127 NBSendSolicit(NCE);
128 }
129 if (NCE->EventTimer - NCE->EventCount == 0) {
130 /* Unlink and destroy the NCE */
131 *PrevNCE = NCE->Next;
132
133 /* Choose the proper failure status */
134 if (NCE->State & NUD_INCOMPLETE)
135 {
136 /* We couldn't get an address to this IP at all */
137 Status = NDIS_STATUS_NETWORK_UNREACHABLE;
138 }
139 else
140 {
141 /* This guy was stale for way too long */
142 Status = NDIS_STATUS_REQUEST_ABORTED;
143 }
144
145 NBFlushPacketQueue(NCE, Status);
146 ExFreePoolWithTag(NCE, NCE_TAG);
147
148 continue;
149 }
150 }
151 PrevNCE = &NCE->Next;
152 }
153
154 TcpipReleaseSpinLockFromDpcLevel(&NeighborCache[i].Lock);
155 }
156 }
157
158 VOID NBStartup(VOID)
159 /*
160 * FUNCTION: Starts the neighbor cache
161 */
162 {
163 UINT i;
164
165 TI_DbgPrint(DEBUG_NCACHE, ("Called.\n"));
166
167 for (i = 0; i <= NB_HASHMASK; i++) {
168 NeighborCache[i].Cache = NULL;
169 TcpipInitializeSpinLock(&NeighborCache[i].Lock);
170 }
171 }
172
173 VOID NBShutdown(VOID)
174 /*
175 * FUNCTION: Shuts down the neighbor cache
176 */
177 {
178 PNEIGHBOR_CACHE_ENTRY NextNCE;
179 PNEIGHBOR_CACHE_ENTRY CurNCE;
180 KIRQL OldIrql;
181 UINT i;
182
183 TI_DbgPrint(DEBUG_NCACHE, ("Called.\n"));
184
185 /* Remove possible entries from the cache */
186 for (i = 0; i <= NB_HASHMASK; i++)
187 {
188 TcpipAcquireSpinLock(&NeighborCache[i].Lock, &OldIrql);
189
190 CurNCE = NeighborCache[i].Cache;
191 while (CurNCE) {
192 NextNCE = CurNCE->Next;
193
194 /* Flush wait queue */
195 NBFlushPacketQueue( CurNCE, NDIS_STATUS_NOT_ACCEPTED );
196
197 ExFreePoolWithTag(CurNCE, NCE_TAG);
198
199 CurNCE = NextNCE;
200 }
201
202 NeighborCache[i].Cache = NULL;
203
204 TcpipReleaseSpinLock(&NeighborCache[i].Lock, OldIrql);
205 }
206
207 TI_DbgPrint(MAX_TRACE, ("Leaving.\n"));
208 }
209
210 VOID NBSendSolicit(PNEIGHBOR_CACHE_ENTRY NCE)
211 /*
212 * FUNCTION: Sends a neighbor solicitation message
213 * ARGUMENTS:
214 * NCE = Pointer to NCE of neighbor to solicit
215 * NOTES:
216 * May be called with lock held on NCE's table
217 */
218 {
219 TI_DbgPrint(DEBUG_NCACHE, ("Called. NCE (0x%X).\n", NCE));
220
221 ARPTransmit(&NCE->Address,
222 (NCE->State & NUD_INCOMPLETE) ? NULL : NCE->LinkAddress,
223 NCE->Interface);
224 }
225
226 VOID NBDestroyNeighborsForInterface(PIP_INTERFACE Interface)
227 {
228 KIRQL OldIrql;
229 PNEIGHBOR_CACHE_ENTRY *PrevNCE;
230 PNEIGHBOR_CACHE_ENTRY NCE;
231 ULONG i;
232
233 KeRaiseIrql(DISPATCH_LEVEL, &OldIrql);
234 for (i = 0; i <= NB_HASHMASK; i++)
235 {
236 TcpipAcquireSpinLockAtDpcLevel(&NeighborCache[i].Lock);
237
238 for (PrevNCE = &NeighborCache[i].Cache;
239 (NCE = *PrevNCE) != NULL;)
240 {
241 if (NCE->Interface == Interface)
242 {
243 /* Unlink and destroy the NCE */
244 *PrevNCE = NCE->Next;
245
246 NBFlushPacketQueue(NCE, NDIS_STATUS_REQUEST_ABORTED);
247 ExFreePoolWithTag(NCE, NCE_TAG);
248
249 continue;
250 }
251 else
252 {
253 PrevNCE = &NCE->Next;
254 }
255 }
256
257 TcpipReleaseSpinLockFromDpcLevel(&NeighborCache[i].Lock);
258 }
259 KeLowerIrql(OldIrql);
260 }
261
262 PNEIGHBOR_CACHE_ENTRY NBAddNeighbor(
263 PIP_INTERFACE Interface,
264 PIP_ADDRESS Address,
265 PVOID LinkAddress,
266 UINT LinkAddressLength,
267 UCHAR State,
268 UINT EventTimer)
269 /*
270 * FUNCTION: Adds a neighbor to the neighbor cache
271 * ARGUMENTS:
272 * Interface = Pointer to interface
273 * Address = Pointer to IP address
274 * LinkAddress = Pointer to link address (may be NULL)
275 * LinkAddressLength = Length of link address
276 * State = State of NCE
277 * RETURNS:
278 * Pointer to NCE, NULL there is not enough free resources
279 * NOTES:
280 * The NCE if referenced for the caller if created. The NCE retains
281 * a reference to the IP address if it is created, the caller is
282 * responsible for providing this reference
283 */
284 {
285 PNEIGHBOR_CACHE_ENTRY NCE;
286 ULONG HashValue;
287 KIRQL OldIrql;
288
289 TI_DbgPrint
290 (DEBUG_NCACHE,
291 ("Called. Interface (0x%X) Address (0x%X) "
292 "LinkAddress (0x%X) LinkAddressLength (%d) State (0x%X)\n",
293 Interface, Address, LinkAddress, LinkAddressLength, State));
294
295 NCE = ExAllocatePoolWithTag
296 (NonPagedPool, sizeof(NEIGHBOR_CACHE_ENTRY) + LinkAddressLength,
297 NCE_TAG);
298 if (NCE == NULL)
299 {
300 TI_DbgPrint(MIN_TRACE, ("Insufficient resources.\n"));
301 return NULL;
302 }
303
304 NCE->Interface = Interface;
305 NCE->Address = *Address;
306 NCE->LinkAddressLength = LinkAddressLength;
307 NCE->LinkAddress = (PVOID)&NCE[1];
308 if( LinkAddress )
309 RtlCopyMemory(NCE->LinkAddress, LinkAddress, LinkAddressLength);
310 else
311 memset(NCE->LinkAddress, 0xff, LinkAddressLength);
312 NCE->State = State;
313 NCE->EventTimer = EventTimer;
314 NCE->EventCount = 0;
315 InitializeListHead( &NCE->PacketQueue );
316
317 TI_DbgPrint(MID_TRACE,("NCE: %x\n", NCE));
318
319 HashValue = *(PULONG)&Address->Address;
320 HashValue ^= HashValue >> 16;
321 HashValue ^= HashValue >> 8;
322 HashValue ^= HashValue >> 4;
323 HashValue &= NB_HASHMASK;
324
325 TcpipAcquireSpinLock(&NeighborCache[HashValue].Lock, &OldIrql);
326
327 NCE->Next = NeighborCache[HashValue].Cache;
328 NeighborCache[HashValue].Cache = NCE;
329
330 TcpipReleaseSpinLock(&NeighborCache[HashValue].Lock, OldIrql);
331
332 return NCE;
333 }
334
335 VOID NBUpdateNeighbor(
336 PNEIGHBOR_CACHE_ENTRY NCE,
337 PVOID LinkAddress,
338 UCHAR State)
339 /*
340 * FUNCTION: Update link address information in NCE
341 * ARGUMENTS:
342 * NCE = Pointer to NCE to update
343 * LinkAddress = Pointer to link address
344 * State = State of NCE
345 * NOTES:
346 * The link address and state is updated. Any waiting packets are sent
347 */
348 {
349 KIRQL OldIrql;
350 UINT HashValue;
351
352 TI_DbgPrint(DEBUG_NCACHE, ("Called. NCE (0x%X) LinkAddress (0x%X) State (0x%X).\n", NCE, LinkAddress, State));
353
354 HashValue = *(PULONG)(&NCE->Address.Address);
355 HashValue ^= HashValue >> 16;
356 HashValue ^= HashValue >> 8;
357 HashValue ^= HashValue >> 4;
358 HashValue &= NB_HASHMASK;
359
360 TcpipAcquireSpinLock(&NeighborCache[HashValue].Lock, &OldIrql);
361
362 RtlCopyMemory(NCE->LinkAddress, LinkAddress, NCE->LinkAddressLength);
363 NCE->State = State;
364 NCE->EventCount = 0;
365
366 TcpipReleaseSpinLock(&NeighborCache[HashValue].Lock, OldIrql);
367
368 if( !(NCE->State & NUD_INCOMPLETE) )
369 {
370 NCE->EventTimer = ARP_COMPLETE_TIMEOUT;
371 NBSendPackets( NCE );
372 }
373 }
374
375 VOID
376 NBResetNeighborTimeout(PIP_ADDRESS Address)
377 {
378 KIRQL OldIrql;
379 UINT HashValue;
380 PNEIGHBOR_CACHE_ENTRY NCE;
381
382 TI_DbgPrint(DEBUG_NCACHE, ("Resetting NCE timout for 0x%s\n", A2S(Address)));
383
384 HashValue = *(PULONG)(&Address->Address);
385 HashValue ^= HashValue >> 16;
386 HashValue ^= HashValue >> 8;
387 HashValue ^= HashValue >> 4;
388 HashValue &= NB_HASHMASK;
389
390 TcpipAcquireSpinLock(&NeighborCache[HashValue].Lock, &OldIrql);
391
392 for (NCE = NeighborCache[HashValue].Cache;
393 NCE != NULL;
394 NCE = NCE->Next)
395 {
396 if (AddrIsEqual(Address, &NCE->Address))
397 {
398 NCE->EventCount = 0;
399 break;
400 }
401 }
402
403 TcpipReleaseSpinLock(&NeighborCache[HashValue].Lock, OldIrql);
404 }
405
406 PNEIGHBOR_CACHE_ENTRY NBLocateNeighbor(
407 PIP_ADDRESS Address)
408 /*
409 * FUNCTION: Locates a neighbor in the neighbor cache
410 * ARGUMENTS:
411 * Address = Pointer to IP address
412 * RETURNS:
413 * Pointer to NCE, NULL if not found
414 * NOTES:
415 * If the NCE is found, it is referenced. The caller is
416 * responsible for dereferencing it again after use
417 */
418 {
419 PNEIGHBOR_CACHE_ENTRY NCE;
420 UINT HashValue;
421 KIRQL OldIrql;
422
423 TI_DbgPrint(DEBUG_NCACHE, ("Called. Address (0x%X).\n", Address));
424
425 HashValue = *(PULONG)&Address->Address;
426 HashValue ^= HashValue >> 16;
427 HashValue ^= HashValue >> 8;
428 HashValue ^= HashValue >> 4;
429 HashValue &= NB_HASHMASK;
430
431 TcpipAcquireSpinLock(&NeighborCache[HashValue].Lock, &OldIrql);
432
433 NCE = NeighborCache[HashValue].Cache;
434
435 while ((NCE) && (!AddrIsEqual(Address, &NCE->Address)))
436 {
437 NCE = NCE->Next;
438 }
439
440 TcpipReleaseSpinLock(&NeighborCache[HashValue].Lock, OldIrql);
441
442 TI_DbgPrint(MAX_TRACE, ("Leaving.\n"));
443
444 return NCE;
445 }
446
447 PNEIGHBOR_CACHE_ENTRY NBFindOrCreateNeighbor(
448 PIP_INTERFACE Interface,
449 PIP_ADDRESS Address)
450 /*
451 * FUNCTION: Tries to find a neighbor and if unsuccesful, creates a new NCE
452 * ARGUMENTS:
453 * Interface = Pointer to interface to use (in case NCE is not found)
454 * Address = Pointer to IP address
455 * RETURNS:
456 * Pointer to NCE, NULL if there is not enough free resources
457 * NOTES:
458 * The NCE is referenced if found or created. The caller is
459 * responsible for dereferencing it again after use
460 */
461 {
462 PNEIGHBOR_CACHE_ENTRY NCE;
463
464 TI_DbgPrint(DEBUG_NCACHE, ("Called. Interface (0x%X) Address (0x%X).\n", Interface, Address));
465
466 NCE = NBLocateNeighbor(Address);
467 if (NCE == NULL)
468 {
469 TI_DbgPrint(MID_TRACE,("BCAST: %s\n", A2S(&Interface->Broadcast)));
470 if( AddrIsEqual(Address, &Interface->Broadcast) ||
471 AddrIsUnspecified(Address) ) {
472 TI_DbgPrint(MID_TRACE,("Packet targeted at broadcast addr\n"));
473 NCE = NBAddNeighbor(Interface, Address, NULL,
474 Interface->AddressLength, NUD_PERMANENT, 0);
475 } else {
476 NCE = NBAddNeighbor(Interface, Address, NULL,
477 Interface->AddressLength, NUD_INCOMPLETE, ARP_INCOMPLETE_TIMEOUT);
478 if (!NCE) return NULL;
479 NBSendSolicit(NCE);
480 }
481 }
482
483 return NCE;
484 }
485
486 BOOLEAN NBQueuePacket(
487 PNEIGHBOR_CACHE_ENTRY NCE,
488 PNDIS_PACKET NdisPacket,
489 PNEIGHBOR_PACKET_COMPLETE PacketComplete,
490 PVOID PacketContext)
491 /*
492 * FUNCTION: Queues a packet on an NCE for later transmission
493 * ARGUMENTS:
494 * NCE = Pointer to NCE to queue packet on
495 * NdisPacket = Pointer to NDIS packet to queue
496 * RETURNS:
497 * TRUE if the packet was successfully queued, FALSE if not
498 */
499 {
500 KIRQL OldIrql;
501 PNEIGHBOR_PACKET Packet;
502 UINT HashValue;
503
504 TI_DbgPrint
505 (DEBUG_NCACHE,
506 ("Called. NCE (0x%X) NdisPacket (0x%X).\n", NCE, NdisPacket));
507
508 Packet = ExAllocatePoolWithTag( NonPagedPool, sizeof(NEIGHBOR_PACKET),
509 NEIGHBOR_PACKET_TAG );
510 if( !Packet ) return FALSE;
511
512 /* FIXME: Should we limit the number of queued packets? */
513
514 HashValue = *(PULONG)(&NCE->Address.Address);
515 HashValue ^= HashValue >> 16;
516 HashValue ^= HashValue >> 8;
517 HashValue ^= HashValue >> 4;
518 HashValue &= NB_HASHMASK;
519
520 TcpipAcquireSpinLock(&NeighborCache[HashValue].Lock, &OldIrql);
521
522 Packet->Complete = PacketComplete;
523 Packet->Context = PacketContext;
524 Packet->Packet = NdisPacket;
525 InsertTailList( &NCE->PacketQueue, &Packet->Next );
526
527 TcpipReleaseSpinLock(&NeighborCache[HashValue].Lock, OldIrql);
528
529 if( !(NCE->State & NUD_INCOMPLETE) )
530 NBSendPackets( NCE );
531
532 return TRUE;
533 }
534
535 VOID NBRemoveNeighbor(
536 PNEIGHBOR_CACHE_ENTRY NCE)
537 /*
538 * FUNCTION: Removes a neighbor from the neighbor cache
539 * ARGUMENTS:
540 * NCE = Pointer to NCE to remove from cache
541 * NOTES:
542 * The NCE must be in a safe state
543 */
544 {
545 PNEIGHBOR_CACHE_ENTRY *PrevNCE;
546 PNEIGHBOR_CACHE_ENTRY CurNCE;
547 ULONG HashValue;
548 KIRQL OldIrql;
549
550 TI_DbgPrint(DEBUG_NCACHE, ("Called. NCE (0x%X).\n", NCE));
551
552 HashValue = *(PULONG)(&NCE->Address.Address);
553 HashValue ^= HashValue >> 16;
554 HashValue ^= HashValue >> 8;
555 HashValue ^= HashValue >> 4;
556 HashValue &= NB_HASHMASK;
557
558 TcpipAcquireSpinLock(&NeighborCache[HashValue].Lock, &OldIrql);
559
560 /* Search the list and remove the NCE from the list if found */
561 for (PrevNCE = &NeighborCache[HashValue].Cache;
562 (CurNCE = *PrevNCE) != NULL;
563 PrevNCE = &CurNCE->Next)
564 {
565 if (CurNCE == NCE)
566 {
567 /* Found it, now unlink it from the list */
568 *PrevNCE = CurNCE->Next;
569
570 NBFlushPacketQueue( CurNCE, NDIS_STATUS_REQUEST_ABORTED );
571 ExFreePoolWithTag(CurNCE, NCE_TAG);
572
573 break;
574 }
575 }
576
577 TcpipReleaseSpinLock(&NeighborCache[HashValue].Lock, OldIrql);
578 }
579
580 ULONG NBCopyNeighbors
581 (PIP_INTERFACE Interface,
582 PIPARP_ENTRY ArpTable)
583 {
584 PNEIGHBOR_CACHE_ENTRY CurNCE;
585 KIRQL OldIrql;
586 UINT Size = 0, i;
587
588 for (i = 0; i <= NB_HASHMASK; i++) {
589 TcpipAcquireSpinLock(&NeighborCache[i].Lock, &OldIrql);
590 for( CurNCE = NeighborCache[i].Cache;
591 CurNCE;
592 CurNCE = CurNCE->Next ) {
593 if( CurNCE->Interface == Interface &&
594 !AddrIsEqual( &CurNCE->Address, &CurNCE->Interface->Unicast ) ) {
595 if( ArpTable ) {
596 ArpTable[Size].Index = Interface->Index;
597 ArpTable[Size].AddrSize = CurNCE->LinkAddressLength;
598 RtlCopyMemory
599 (ArpTable[Size].PhysAddr,
600 CurNCE->LinkAddress,
601 CurNCE->LinkAddressLength);
602 ArpTable[Size].LogAddr = CurNCE->Address.Address.IPv4Address;
603 if( CurNCE->State & NUD_PERMANENT )
604 ArpTable[Size].Type = ARP_ENTRY_STATIC;
605 else if( CurNCE->State & NUD_INCOMPLETE )
606 ArpTable[Size].Type = ARP_ENTRY_INVALID;
607 else
608 ArpTable[Size].Type = ARP_ENTRY_DYNAMIC;
609 }
610 Size++;
611 }
612 }
613 TcpipReleaseSpinLock(&NeighborCache[i].Lock, OldIrql);
614 }
615
616 return Size;
617 }