295ac908cfd6141831ab44984ae429aa35d8715c
[reactos.git] / reactos / 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 exFreePool( 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 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 exFreePool( Packet );
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 KIRQL OldIrql;
101 PNEIGHBOR_CACHE_ENTRY *PrevNCE;
102 PNEIGHBOR_CACHE_ENTRY NCE;
103
104 for (i = 0; i <= NB_HASHMASK; i++) {
105 TcpipAcquireSpinLock(&NeighborCache[i].Lock, &OldIrql);
106
107 for (PrevNCE = &NeighborCache[i].Cache;
108 (NCE = *PrevNCE) != NULL;
109 PrevNCE = &NCE->Next) {
110 /* Check if event timer is running */
111 if (NCE->EventTimer > 0) {
112 ASSERT(!(NCE->State & NUD_PERMANENT));
113 NCE->EventCount++;
114 if (NCE->EventCount % ARP_RATE == 0)
115 NBSendSolicit(NCE);
116 if (NCE->EventTimer - NCE->EventCount == 0) {
117 NCE->State |= NUD_STALE;
118
119 NCE->EventCount = 0;
120 }
121 }
122 }
123
124 TcpipReleaseSpinLock(&NeighborCache[i].Lock, OldIrql);
125 }
126 }
127
128 VOID NBStartup(VOID)
129 /*
130 * FUNCTION: Starts the neighbor cache
131 */
132 {
133 UINT i;
134
135 TI_DbgPrint(DEBUG_NCACHE, ("Called.\n"));
136
137 for (i = 0; i <= NB_HASHMASK; i++) {
138 NeighborCache[i].Cache = NULL;
139 TcpipInitializeSpinLock(&NeighborCache[i].Lock);
140 }
141 }
142
143 VOID NBShutdown(VOID)
144 /*
145 * FUNCTION: Shuts down the neighbor cache
146 */
147 {
148 PNEIGHBOR_CACHE_ENTRY NextNCE;
149 PNEIGHBOR_CACHE_ENTRY CurNCE;
150 KIRQL OldIrql;
151 UINT i;
152
153 TI_DbgPrint(DEBUG_NCACHE, ("Called.\n"));
154
155 /* Remove possible entries from the cache */
156 for (i = 0; i <= NB_HASHMASK; i++)
157 {
158 TcpipAcquireSpinLock(&NeighborCache[i].Lock, &OldIrql);
159
160 CurNCE = NeighborCache[i].Cache;
161 while (CurNCE) {
162 NextNCE = CurNCE->Next;
163
164 /* Flush wait queue */
165 NBFlushPacketQueue( CurNCE, NDIS_STATUS_NOT_ACCEPTED );
166
167 exFreePool(CurNCE);
168
169 CurNCE = NextNCE;
170 }
171
172 NeighborCache[i].Cache = NULL;
173
174 TcpipReleaseSpinLock(&NeighborCache[i].Lock, OldIrql);
175 }
176
177 TI_DbgPrint(MAX_TRACE, ("Leaving.\n"));
178 }
179
180 VOID NBSendSolicit(PNEIGHBOR_CACHE_ENTRY NCE)
181 /*
182 * FUNCTION: Sends a neighbor solicitation message
183 * ARGUMENTS:
184 * NCE = Pointer to NCE of neighbor to solicit
185 * NOTES:
186 * May be called with lock held on NCE's table
187 */
188 {
189 TI_DbgPrint(DEBUG_NCACHE, ("Called. NCE (0x%X).\n", NCE));
190
191 ARPTransmit(&NCE->Address, NCE->Interface);
192 }
193
194 PNEIGHBOR_CACHE_ENTRY NBAddNeighbor(
195 PIP_INTERFACE Interface,
196 PIP_ADDRESS Address,
197 PVOID LinkAddress,
198 UINT LinkAddressLength,
199 UCHAR State,
200 UINT EventTimer)
201 /*
202 * FUNCTION: Adds a neighbor to the neighbor cache
203 * ARGUMENTS:
204 * Interface = Pointer to interface
205 * Address = Pointer to IP address
206 * LinkAddress = Pointer to link address (may be NULL)
207 * LinkAddressLength = Length of link address
208 * State = State of NCE
209 * RETURNS:
210 * Pointer to NCE, NULL there is not enough free resources
211 * NOTES:
212 * The NCE if referenced for the caller if created. The NCE retains
213 * a reference to the IP address if it is created, the caller is
214 * responsible for providing this reference
215 */
216 {
217 PNEIGHBOR_CACHE_ENTRY NCE;
218 ULONG HashValue;
219 KIRQL OldIrql;
220
221 TI_DbgPrint
222 (DEBUG_NCACHE,
223 ("Called. Interface (0x%X) Address (0x%X) "
224 "LinkAddress (0x%X) LinkAddressLength (%d) State (0x%X)\n",
225 Interface, Address, LinkAddress, LinkAddressLength, State));
226
227 NCE = exAllocatePool
228 (NonPagedPool, sizeof(NEIGHBOR_CACHE_ENTRY) + LinkAddressLength);
229 if (NCE == NULL)
230 {
231 TI_DbgPrint(MIN_TRACE, ("Insufficient resources.\n"));
232 return NULL;
233 }
234
235 INIT_TAG(NCE, ' ECN');
236
237 NCE->Interface = Interface;
238 NCE->Address = *Address;
239 NCE->LinkAddressLength = LinkAddressLength;
240 NCE->LinkAddress = (PVOID)&NCE[1];
241 if( LinkAddress )
242 RtlCopyMemory(NCE->LinkAddress, LinkAddress, LinkAddressLength);
243 else
244 memset(NCE->LinkAddress, 0xff, LinkAddressLength);
245 NCE->State = State;
246 NCE->EventTimer = EventTimer;
247 NCE->EventCount = 0;
248 InitializeListHead( &NCE->PacketQueue );
249
250 TI_DbgPrint(MID_TRACE,("NCE: %x\n", NCE));
251
252 HashValue = *(PULONG)&Address->Address;
253 HashValue ^= HashValue >> 16;
254 HashValue ^= HashValue >> 8;
255 HashValue ^= HashValue >> 4;
256 HashValue &= NB_HASHMASK;
257
258 TcpipAcquireSpinLock(&NeighborCache[HashValue].Lock, &OldIrql);
259
260 NCE->Next = NeighborCache[HashValue].Cache;
261 NeighborCache[HashValue].Cache = NCE;
262
263 TcpipReleaseSpinLock(&NeighborCache[HashValue].Lock, OldIrql);
264
265 return NCE;
266 }
267
268 VOID NBUpdateNeighbor(
269 PNEIGHBOR_CACHE_ENTRY NCE,
270 PVOID LinkAddress,
271 UCHAR State)
272 /*
273 * FUNCTION: Update link address information in NCE
274 * ARGUMENTS:
275 * NCE = Pointer to NCE to update
276 * LinkAddress = Pointer to link address
277 * State = State of NCE
278 * NOTES:
279 * The link address and state is updated. Any waiting packets are sent
280 */
281 {
282 KIRQL OldIrql;
283 UINT HashValue;
284
285 TI_DbgPrint(DEBUG_NCACHE, ("Called. NCE (0x%X) LinkAddress (0x%X) State (0x%X).\n", NCE, LinkAddress, State));
286
287 HashValue = *(PULONG)(&NCE->Address.Address);
288 HashValue ^= HashValue >> 16;
289 HashValue ^= HashValue >> 8;
290 HashValue ^= HashValue >> 4;
291 HashValue &= NB_HASHMASK;
292
293 TcpipAcquireSpinLock(&NeighborCache[HashValue].Lock, &OldIrql);
294
295 RtlCopyMemory(NCE->LinkAddress, LinkAddress, NCE->LinkAddressLength);
296 NCE->State = State;
297 NCE->EventCount = 0;
298
299 TcpipReleaseSpinLock(&NeighborCache[HashValue].Lock, OldIrql);
300
301 if( !(NCE->State & NUD_INCOMPLETE) )
302 NBSendPackets( NCE );
303 }
304
305 PNEIGHBOR_CACHE_ENTRY NBLocateNeighbor(
306 PIP_ADDRESS Address)
307 /*
308 * FUNCTION: Locates a neighbor in the neighbor cache
309 * ARGUMENTS:
310 * Address = Pointer to IP address
311 * RETURNS:
312 * Pointer to NCE, NULL if not found
313 * NOTES:
314 * If the NCE is found, it is referenced. The caller is
315 * responsible for dereferencing it again after use
316 */
317 {
318 PNEIGHBOR_CACHE_ENTRY NCE;
319 UINT HashValue;
320 KIRQL OldIrql;
321
322 TI_DbgPrint(DEBUG_NCACHE, ("Called. Address (0x%X).\n", Address));
323
324 HashValue = *(PULONG)&Address->Address;
325 HashValue ^= HashValue >> 16;
326 HashValue ^= HashValue >> 8;
327 HashValue ^= HashValue >> 4;
328 HashValue &= NB_HASHMASK;
329
330 TcpipAcquireSpinLock(&NeighborCache[HashValue].Lock, &OldIrql);
331
332 NCE = NeighborCache[HashValue].Cache;
333
334 while ((NCE) && (!AddrIsEqual(Address, &NCE->Address)))
335 {
336 NCE = NCE->Next;
337 }
338
339 TcpipReleaseSpinLock(&NeighborCache[HashValue].Lock, OldIrql);
340
341 TI_DbgPrint(MAX_TRACE, ("Leaving.\n"));
342
343 return NCE;
344 }
345
346 PNEIGHBOR_CACHE_ENTRY NBFindOrCreateNeighbor(
347 PIP_INTERFACE Interface,
348 PIP_ADDRESS Address)
349 /*
350 * FUNCTION: Tries to find a neighbor and if unsuccesful, creates a new NCE
351 * ARGUMENTS:
352 * Interface = Pointer to interface to use (in case NCE is not found)
353 * Address = Pointer to IP address
354 * RETURNS:
355 * Pointer to NCE, NULL if there is not enough free resources
356 * NOTES:
357 * The NCE is referenced if found or created. The caller is
358 * responsible for dereferencing it again after use
359 */
360 {
361 PNEIGHBOR_CACHE_ENTRY NCE;
362
363 TI_DbgPrint(DEBUG_NCACHE, ("Called. Interface (0x%X) Address (0x%X).\n", Interface, Address));
364
365 NCE = NBLocateNeighbor(Address);
366 if (NCE == NULL)
367 {
368 TI_DbgPrint(MID_TRACE,("BCAST: %s\n", A2S(&Interface->Broadcast)));
369 if( AddrIsEqual(Address, &Interface->Broadcast) ||
370 AddrIsUnspecified(Address) ) {
371 TI_DbgPrint(MID_TRACE,("Packet targeted at broadcast addr\n"));
372 NCE = NBAddNeighbor(Interface, Address, NULL,
373 Interface->AddressLength, NUD_PERMANENT, 0);
374 } else {
375 NCE = NBAddNeighbor(Interface, Address, NULL,
376 Interface->AddressLength, NUD_INCOMPLETE, ARP_TIMEOUT);
377 if (!NCE) return NULL;
378 NBSendSolicit(NCE);
379 }
380 }
381
382 return NCE;
383 }
384
385 BOOLEAN NBQueuePacket(
386 PNEIGHBOR_CACHE_ENTRY NCE,
387 PNDIS_PACKET NdisPacket,
388 PNEIGHBOR_PACKET_COMPLETE PacketComplete,
389 PVOID PacketContext)
390 /*
391 * FUNCTION: Queues a packet on an NCE for later transmission
392 * ARGUMENTS:
393 * NCE = Pointer to NCE to queue packet on
394 * NdisPacket = Pointer to NDIS packet to queue
395 * RETURNS:
396 * TRUE if the packet was successfully queued, FALSE if not
397 */
398 {
399 KIRQL OldIrql;
400 PNEIGHBOR_PACKET Packet;
401 UINT HashValue;
402
403 TI_DbgPrint
404 (DEBUG_NCACHE,
405 ("Called. NCE (0x%X) NdisPacket (0x%X).\n", NCE, NdisPacket));
406
407 Packet = exAllocatePool( NonPagedPool, sizeof(NEIGHBOR_PACKET) );
408 if( !Packet ) return FALSE;
409
410 /* FIXME: Should we limit the number of queued packets? */
411
412 HashValue = *(PULONG)(&NCE->Address.Address);
413 HashValue ^= HashValue >> 16;
414 HashValue ^= HashValue >> 8;
415 HashValue ^= HashValue >> 4;
416 HashValue &= NB_HASHMASK;
417
418 TcpipAcquireSpinLock(&NeighborCache[HashValue].Lock, &OldIrql);
419
420 Packet->Complete = PacketComplete;
421 Packet->Context = PacketContext;
422 Packet->Packet = NdisPacket;
423 InsertTailList( &NCE->PacketQueue, &Packet->Next );
424
425 TcpipReleaseSpinLock(&NeighborCache[HashValue].Lock, OldIrql);
426
427 if( !(NCE->State & NUD_INCOMPLETE) )
428 NBSendPackets( NCE );
429
430 return TRUE;
431 }
432
433 VOID NBRemoveNeighbor(
434 PNEIGHBOR_CACHE_ENTRY NCE)
435 /*
436 * FUNCTION: Removes a neighbor from the neighbor cache
437 * ARGUMENTS:
438 * NCE = Pointer to NCE to remove from cache
439 * NOTES:
440 * The NCE must be in a safe state
441 */
442 {
443 PNEIGHBOR_CACHE_ENTRY *PrevNCE;
444 PNEIGHBOR_CACHE_ENTRY CurNCE;
445 ULONG HashValue;
446 KIRQL OldIrql;
447
448 TI_DbgPrint(DEBUG_NCACHE, ("Called. NCE (0x%X).\n", NCE));
449
450 HashValue = *(PULONG)(&NCE->Address.Address);
451 HashValue ^= HashValue >> 16;
452 HashValue ^= HashValue >> 8;
453 HashValue ^= HashValue >> 4;
454 HashValue &= NB_HASHMASK;
455
456 TcpipAcquireSpinLock(&NeighborCache[HashValue].Lock, &OldIrql);
457
458 /* Search the list and remove the NCE from the list if found */
459 for (PrevNCE = &NeighborCache[HashValue].Cache;
460 (CurNCE = *PrevNCE) != NULL;
461 PrevNCE = &CurNCE->Next)
462 {
463 if (CurNCE == NCE)
464 {
465 /* Found it, now unlink it from the list */
466 *PrevNCE = CurNCE->Next;
467
468 NBFlushPacketQueue( CurNCE, NDIS_STATUS_REQUEST_ABORTED );
469 exFreePool(CurNCE);
470
471 break;
472 }
473 }
474
475 TcpipReleaseSpinLock(&NeighborCache[HashValue].Lock, OldIrql);
476 }
477
478 ULONG NBCopyNeighbors
479 (PIP_INTERFACE Interface,
480 PIPARP_ENTRY ArpTable)
481 {
482 PNEIGHBOR_CACHE_ENTRY CurNCE;
483 KIRQL OldIrql;
484 UINT Size = 0, i;
485
486 for (i = 0; i <= NB_HASHMASK; i++) {
487 TcpipAcquireSpinLock(&NeighborCache[i].Lock, &OldIrql);
488 for( CurNCE = NeighborCache[i].Cache;
489 CurNCE;
490 CurNCE = CurNCE->Next ) {
491 if( CurNCE->Interface == Interface &&
492 !AddrIsEqual( &CurNCE->Address, &CurNCE->Interface->Unicast ) ) {
493 if( ArpTable ) {
494 ArpTable[Size].Index = Interface->Index;
495 ArpTable[Size].AddrSize = CurNCE->LinkAddressLength;
496 RtlCopyMemory
497 (ArpTable[Size].PhysAddr,
498 CurNCE->LinkAddress,
499 CurNCE->LinkAddressLength);
500 ArpTable[Size].LogAddr = CurNCE->Address.Address.IPv4Address;
501 if( CurNCE->State & NUD_PERMANENT )
502 ArpTable[Size].Type = ARP_ENTRY_STATIC;
503 else if( CurNCE->State & NUD_INCOMPLETE )
504 ArpTable[Size].Type = ARP_ENTRY_INVALID;
505 else
506 ArpTable[Size].Type = ARP_ENTRY_DYNAMIC;
507 }
508 Size++;
509 }
510 }
511 TcpipReleaseSpinLock(&NeighborCache[i].Lock, OldIrql);
512 }
513
514 return Size;
515 }