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