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)
8 * CSH 01/08-2000 Created
13 NEIGHBOR_CACHE_TABLE NeighborCache
[NB_HASHMASK
+ 1];
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"));
28 VOID
NBSendPackets( PNEIGHBOR_CACHE_ENTRY NCE
) {
29 PLIST_ENTRY PacketEntry
;
30 PNEIGHBOR_PACKET Packet
;
32 /* Send any waiting packets */
33 PacketEntry
= ExInterlockedRemoveHeadList(&NCE
->PacketQueue
,
35 if( PacketEntry
!= NULL
) {
36 Packet
= CONTAINING_RECORD( PacketEntry
, NEIGHBOR_PACKET
, Next
);
40 ("PacketEntry: %x, NdisPacket %x\n",
41 PacketEntry
, Packet
->Packet
));
43 PC(Packet
->Packet
)->DLComplete
= NBCompleteSend
;
44 PC(Packet
->Packet
)->Context
= Packet
;
46 NCE
->Interface
->Transmit
47 ( NCE
->Interface
->Context
,
55 /* Must be called with table lock acquired */
56 VOID
NBFlushPacketQueue( PNEIGHBOR_CACHE_ENTRY NCE
,
58 NTSTATUS ErrorCode
) {
59 PLIST_ENTRY PacketEntry
;
60 PNEIGHBOR_PACKET Packet
;
62 while( !IsListEmpty(&NCE
->PacketQueue
) ) {
63 PacketEntry
= RemoveHeadList(&NCE
->PacketQueue
);
64 Packet
= CONTAINING_RECORD
65 ( PacketEntry
, NEIGHBOR_PACKET
, Next
);
67 ASSERT_KM_POINTER(Packet
);
71 ("PacketEntry: %x, NdisPacket %x\n",
72 PacketEntry
, Packet
->Packet
));
76 ASSERT_KM_POINTER(Packet
->Complete
);
77 Packet
->Complete( Packet
->Context
,
79 NDIS_STATUS_REQUEST_ABORTED
);
82 PoolFreeBuffer( Packet
);
87 PNEIGHBOR_CACHE_ENTRY NCE
)
89 * FUNCTION: Neighbor cache entry timeout handler
91 * The neighbor cache lock must be held
94 TI_DbgPrint(DEBUG_NCACHE
, ("Called. NCE (0x%X).\n", NCE
));
95 TI_DbgPrint(DEBUG_NCACHE
, ("NCE->State is (0x%X).\n", NCE
->State
));
100 /* Retransmission timer expired */
101 if (NCE
->EventCount
++ > MAX_MULTICAST_SOLICIT
)
103 /* We have retransmitted too many times */
105 /* Calling IPSendComplete with cache lock held is not
106 a great thing to do. We don't get here very often
107 so maybe it's not that big a problem */
109 /* Flush packet queue */
110 NBFlushPacketQueue( NCE
, TRUE
, NDIS_STATUS_REQUEST_ABORTED
);
115 /* Retransmit request */
121 /* FIXME: Delayed state */
122 TI_DbgPrint(DEBUG_NCACHE
, ("NCE delay state.\n"));
126 /* FIXME: Probe state */
127 TI_DbgPrint(DEBUG_NCACHE
, ("NCE probe state.\n"));
131 /* Should not happen since the event timer is not used in the other states */
132 TI_DbgPrint(MIN_TRACE
, ("Invalid NCE state (%d).\n", NCE
->State
));
140 * FUNCTION: Neighbor address cache timeout handler
142 * This routine is called by IPTimeout to remove outdated cache
148 PNEIGHBOR_CACHE_ENTRY NCE
;
150 for (i
= 0; i
<= NB_HASHMASK
; i
++) {
151 TcpipAcquireSpinLock(&NeighborCache
[i
].Lock
, &OldIrql
);
153 for (NCE
= NeighborCache
[i
].Cache
;
154 NCE
!= NULL
; NCE
= NCE
->Next
) {
155 /* Check if event timer is running */
156 if (NCE
->EventTimer
> 0) {
158 if (NCE
->EventTimer
== 0) {
159 /* Call timeout handler for NCE */
165 TcpipReleaseSpinLock(&NeighborCache
[i
].Lock
, OldIrql
);
171 * FUNCTION: Starts the neighbor cache
176 TI_DbgPrint(DEBUG_NCACHE
, ("Called.\n"));
178 for (i
= 0; i
<= NB_HASHMASK
; i
++) {
179 NeighborCache
[i
].Cache
= NULL
;
180 TcpipInitializeSpinLock(&NeighborCache
[i
].Lock
);
184 VOID
NBShutdown(VOID
)
186 * FUNCTION: Shuts down the neighbor cache
189 PNEIGHBOR_CACHE_ENTRY NextNCE
;
190 PNEIGHBOR_CACHE_ENTRY CurNCE
;
194 TI_DbgPrint(DEBUG_NCACHE
, ("Called.\n"));
196 /* Remove possible entries from the cache */
197 for (i
= 0; i
<= NB_HASHMASK
; i
++)
199 TcpipAcquireSpinLock(&NeighborCache
[i
].Lock
, &OldIrql
);
201 CurNCE
= NeighborCache
[i
].Cache
;
203 NextNCE
= CurNCE
->Next
;
205 /* Flush wait queue */
206 NBFlushPacketQueue( CurNCE
, FALSE
, STATUS_SUCCESS
);
211 NeighborCache
[i
].Cache
= NULL
;
213 TcpipReleaseSpinLock(&NeighborCache
[i
].Lock
, OldIrql
);
216 TI_DbgPrint(MAX_TRACE
, ("Leaving.\n"));
219 VOID
NBSendSolicit(PNEIGHBOR_CACHE_ENTRY NCE
)
221 * FUNCTION: Sends a neighbor solicitation message
223 * NCE = Pointer to NCE of neighbor to solicit
225 * May be called with lock held on NCE's table
228 TI_DbgPrint(DEBUG_NCACHE
, ("Called. NCE (0x%X).\n", NCE
));
230 if (NCE
->State
== NUD_INCOMPLETE
)
232 /* This is the first solicitation of this neighbor. Broadcast
233 a request for the neighbor */
235 TI_DbgPrint(MID_TRACE
,("NCE: %x\n", NCE
));
237 ARPTransmit(&NCE
->Address
, NCE
->Interface
);
239 /* FIXME: Unicast solicitation since we have a cached address */
240 TI_DbgPrint(MIN_TRACE
, ("Uninplemented unicast solicitation.\n"));
244 PNEIGHBOR_CACHE_ENTRY
NBAddNeighbor(
245 PIP_INTERFACE Interface
,
248 UINT LinkAddressLength
,
251 * FUNCTION: Adds a neighbor to the neighbor cache
253 * Interface = Pointer to interface
254 * Address = Pointer to IP address
255 * LinkAddress = Pointer to link address (may be NULL)
256 * LinkAddressLength = Length of link address
257 * State = State of NCE
259 * Pointer to NCE, NULL there is not enough free resources
261 * The NCE if referenced for the caller if created. The NCE retains
262 * a reference to the IP address if it is created, the caller is
263 * responsible for providing this reference
266 PNEIGHBOR_CACHE_ENTRY NCE
;
272 ("Called. Interface (0x%X) Address (0x%X) "
273 "LinkAddress (0x%X) LinkAddressLength (%d) State (0x%X)\n",
274 Interface
, Address
, LinkAddress
, LinkAddressLength
, State
));
277 (NonPagedPool
, sizeof(NEIGHBOR_CACHE_ENTRY
) + LinkAddressLength
);
280 TI_DbgPrint(MIN_TRACE
, ("Insufficient resources.\n"));
284 INIT_TAG(NCE
, TAG('N','C','E',' '));
286 NCE
->Interface
= Interface
;
287 NCE
->Address
= *Address
;
288 NCE
->LinkAddressLength
= LinkAddressLength
;
289 NCE
->LinkAddress
= (PVOID
)&NCE
[1];
291 RtlCopyMemory(NCE
->LinkAddress
, LinkAddress
, LinkAddressLength
);
293 memset(NCE
->LinkAddress
, 0xff, LinkAddressLength
);
295 NCE
->EventTimer
= 0; /* Not in use */
296 InitializeListHead( &NCE
->PacketQueue
);
298 TI_DbgPrint(MID_TRACE
,("NCE: %x\n", NCE
));
300 HashValue
= *(PULONG
)&Address
->Address
;
301 HashValue
^= HashValue
>> 16;
302 HashValue
^= HashValue
>> 8;
303 HashValue
^= HashValue
>> 4;
304 HashValue
&= NB_HASHMASK
;
306 NCE
->Table
= &NeighborCache
[HashValue
];
308 TcpipAcquireSpinLock(&NeighborCache
[HashValue
].Lock
, &OldIrql
);
310 NCE
->Next
= NeighborCache
[HashValue
].Cache
;
311 NeighborCache
[HashValue
].Cache
= NCE
;
313 TcpipReleaseSpinLock(&NeighborCache
[HashValue
].Lock
, OldIrql
);
318 VOID
NBUpdateNeighbor(
319 PNEIGHBOR_CACHE_ENTRY NCE
,
323 * FUNCTION: Update link address information in NCE
325 * NCE = Pointer to NCE to update
326 * LinkAddress = Pointer to link address
327 * State = State of NCE
329 * The link address and state is updated. Any waiting packets are sent
334 TI_DbgPrint(DEBUG_NCACHE
, ("Called. NCE (0x%X) LinkAddress (0x%X) State (0x%X).\n", NCE
, LinkAddress
, State
));
336 TcpipAcquireSpinLock(&NCE
->Table
->Lock
, &OldIrql
);
338 RtlCopyMemory(NCE
->LinkAddress
, LinkAddress
, NCE
->LinkAddressLength
);
341 TcpipReleaseSpinLock(&NCE
->Table
->Lock
, OldIrql
);
343 if( NCE
->State
& NUD_CONNECTED
)
344 NBSendPackets( NCE
);
347 PNEIGHBOR_CACHE_ENTRY
NBLocateNeighbor(
350 * FUNCTION: Locates a neighbor in the neighbor cache
352 * Address = Pointer to IP address
354 * Pointer to NCE, NULL if not found
356 * If the NCE is found, it is referenced. The caller is
357 * responsible for dereferencing it again after use
360 PNEIGHBOR_CACHE_ENTRY NCE
;
364 TI_DbgPrint(DEBUG_NCACHE
, ("Called. Address (0x%X).\n", Address
));
366 HashValue
= *(PULONG
)&Address
->Address
;
367 HashValue
^= HashValue
>> 16;
368 HashValue
^= HashValue
>> 8;
369 HashValue
^= HashValue
>> 4;
370 HashValue
&= NB_HASHMASK
;
372 TcpipAcquireSpinLock(&NeighborCache
[HashValue
].Lock
, &OldIrql
);
374 NCE
= NeighborCache
[HashValue
].Cache
;
376 while ((NCE
) && (!AddrIsEqual(Address
, &NCE
->Address
)))
381 TcpipReleaseSpinLock(&NeighborCache
[HashValue
].Lock
, OldIrql
);
383 TI_DbgPrint(MAX_TRACE
, ("Leaving.\n"));
388 PNEIGHBOR_CACHE_ENTRY
NBFindOrCreateNeighbor(
389 PIP_INTERFACE Interface
,
392 * FUNCTION: Tries to find a neighbor and if unsuccesful, creates a new NCE
394 * Interface = Pointer to interface to use (in case NCE is not found)
395 * Address = Pointer to IP address
397 * Pointer to NCE, NULL if there is not enough free resources
399 * The NCE is referenced if found or created. The caller is
400 * responsible for dereferencing it again after use
403 PNEIGHBOR_CACHE_ENTRY NCE
;
405 TI_DbgPrint(DEBUG_NCACHE
, ("Called. Interface (0x%X) Address (0x%X).\n", Interface
, Address
));
407 NCE
= NBLocateNeighbor(Address
);
410 TI_DbgPrint(MID_TRACE
,("BCAST: %s\n", A2S(&Interface
->Broadcast
)));
411 if( AddrIsEqual(Address
, &Interface
->Broadcast
) ) {
412 TI_DbgPrint(MID_TRACE
,("Packet targeted at broadcast addr\n"));
413 NCE
= NBAddNeighbor(Interface
, Address
, NULL
,
414 Interface
->AddressLength
, NUD_CONNECTED
);
418 NCE
= NBAddNeighbor(Interface
, Address
, NULL
,
419 Interface
->AddressLength
, NUD_INCOMPLETE
);
428 BOOLEAN
NBQueuePacket(
429 PNEIGHBOR_CACHE_ENTRY NCE
,
430 PNDIS_PACKET NdisPacket
,
431 PNEIGHBOR_PACKET_COMPLETE PacketComplete
,
434 * FUNCTION: Queues a packet on an NCE for later transmission
436 * NCE = Pointer to NCE to queue packet on
437 * NdisPacket = Pointer to NDIS packet to queue
439 * TRUE if the packet was successfully queued, FALSE if not
444 PNEIGHBOR_PACKET Packet
;
448 ("Called. NCE (0x%X) NdisPacket (0x%X).\n", NCE
, NdisPacket
));
450 Packet
= PoolAllocateBuffer( sizeof(NEIGHBOR_PACKET
) );
451 if( !Packet
) return FALSE
;
453 /* FIXME: Should we limit the number of queued packets? */
455 Lock
= &NCE
->Table
->Lock
;
457 TcpipAcquireSpinLock(Lock
, &OldIrql
);
459 Packet
->Complete
= PacketComplete
;
460 Packet
->Context
= PacketContext
;
461 Packet
->Packet
= NdisPacket
;
462 InsertTailList( &NCE
->PacketQueue
, &Packet
->Next
);
464 TcpipReleaseSpinLock(Lock
, OldIrql
);
466 if( NCE
->State
& NUD_CONNECTED
)
467 NBSendPackets( NCE
);
473 VOID
NBRemoveNeighbor(
474 PNEIGHBOR_CACHE_ENTRY NCE
)
476 * FUNCTION: Removes a neighbor from the neighbor cache
478 * NCE = Pointer to NCE to remove from cache
480 * The NCE must be in a safe state
483 PNEIGHBOR_CACHE_ENTRY
*PrevNCE
;
484 PNEIGHBOR_CACHE_ENTRY CurNCE
;
488 TI_DbgPrint(DEBUG_NCACHE
, ("Called. NCE (0x%X).\n", NCE
));
490 HashValue
= *(PULONG
)(&NCE
->Address
.Address
);
491 HashValue
^= HashValue
>> 16;
492 HashValue
^= HashValue
>> 8;
493 HashValue
^= HashValue
>> 4;
494 HashValue
&= NB_HASHMASK
;
496 TcpipAcquireSpinLock(&NeighborCache
[HashValue
].Lock
, &OldIrql
);
498 /* Search the list and remove the NCE from the list if found */
499 for (PrevNCE
= &NeighborCache
[HashValue
].Cache
;
500 (CurNCE
= *PrevNCE
) != NULL
;
501 PrevNCE
= &CurNCE
->Next
)
505 /* Found it, now unlink it from the list */
506 *PrevNCE
= CurNCE
->Next
;
508 NBFlushPacketQueue( CurNCE
, TRUE
, NDIS_STATUS_REQUEST_ABORTED
);
515 TcpipReleaseSpinLock(&NeighborCache
[HashValue
].Lock
, OldIrql
);