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