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     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 PNEIGHBOR_CACHE_ENTRY NBAddNeighbor(
 227   PIP_INTERFACE Interface,
 228   PIP_ADDRESS Address,
 229   PVOID LinkAddress,
 230   UINT LinkAddressLength,
 231   UCHAR State,
 232   UINT EventTimer)
 233 /*
 234  * FUNCTION: Adds a neighbor to the neighbor cache
 235  * ARGUMENTS:
 236  *   Interface         = Pointer to interface
 237  *   Address           = Pointer to IP address
 238  *   LinkAddress       = Pointer to link address (may be NULL)
 239  *   LinkAddressLength = Length of link address
 240  *   State             = State of NCE
 241  * RETURNS:
 242  *   Pointer to NCE, NULL there is not enough free resources
 243  * NOTES:
 244  *   The NCE if referenced for the caller if created. The NCE retains
 245  *   a reference to the IP address if it is created, the caller is
 246  *   responsible for providing this reference
 247  */
 248 {
 249   PNEIGHBOR_CACHE_ENTRY NCE;
 250   ULONG HashValue;
 251   KIRQL OldIrql;
 252
 253   TI_DbgPrint
 254       (DEBUG_NCACHE,
 255        ("Called. Interface (0x%X)  Address (0x%X)  "
 256         "LinkAddress (0x%X)  LinkAddressLength (%d)  State (0x%X)\n",
 257         Interface, Address, LinkAddress, LinkAddressLength, State));
 258
 259   NCE = ExAllocatePoolWithTag
 260       (NonPagedPool, sizeof(NEIGHBOR_CACHE_ENTRY) + LinkAddressLength,
 261        NCE_TAG);
 262   if (NCE == NULL)
 263     {
 264       TI_DbgPrint(MIN_TRACE, ("Insufficient resources.\n"));
 265       return NULL;
 266     }
 267
 268   NCE->Interface = Interface;
 269   NCE->Address = *Address;
 270   NCE->LinkAddressLength = LinkAddressLength;
 271   NCE->LinkAddress = (PVOID)&NCE[1];
 272   if( LinkAddress )
 273       RtlCopyMemory(NCE->LinkAddress, LinkAddress, LinkAddressLength);
 274   else
 275       memset(NCE->LinkAddress, 0xff, LinkAddressLength);
 276   NCE->State = State;
 277   NCE->EventTimer = EventTimer;
 278   NCE->EventCount = 0;
 279   InitializeListHead( &NCE->PacketQueue );
 280
 281   TI_DbgPrint(MID_TRACE,("NCE: %x\n", NCE));
 282
 283   HashValue = *(PULONG)&Address->Address;
 284   HashValue ^= HashValue >> 16;
 285   HashValue ^= HashValue >> 8;
 286   HashValue ^= HashValue >> 4;
 287   HashValue &= NB_HASHMASK;
 288
 289   TcpipAcquireSpinLock(&NeighborCache[HashValue].Lock, &OldIrql);
 290
 291   NCE->Next = NeighborCache[HashValue].Cache;
 292   NeighborCache[HashValue].Cache = NCE;
 293
 294   TcpipReleaseSpinLock(&NeighborCache[HashValue].Lock, OldIrql);
 295
 296   return NCE;
 297 }
 298
 299 VOID NBUpdateNeighbor(
 300   PNEIGHBOR_CACHE_ENTRY NCE,
 301   PVOID LinkAddress,
 302   UCHAR State)
 303 /*
 304  * FUNCTION: Update link address information in NCE
 305  * ARGUMENTS:
 306  *   NCE         = Pointer to NCE to update
 307  *   LinkAddress = Pointer to link address
 308  *   State       = State of NCE
 309  * NOTES:
 310  *   The link address and state is updated. Any waiting packets are sent
 311  */
 312 {
 313     KIRQL OldIrql;
 314     UINT HashValue;
 315
 316     TI_DbgPrint(DEBUG_NCACHE, ("Called. NCE (0x%X)  LinkAddress (0x%X)  State (0x%X).\n", NCE, LinkAddress, State));
 317
 318     HashValue  = *(PULONG)(&NCE->Address.Address);
 319     HashValue ^= HashValue >> 16;
 320     HashValue ^= HashValue >> 8;
 321     HashValue ^= HashValue >> 4;
 322     HashValue &= NB_HASHMASK;
 323
 324     TcpipAcquireSpinLock(&NeighborCache[HashValue].Lock, &OldIrql);
 325
 326     RtlCopyMemory(NCE->LinkAddress, LinkAddress, NCE->LinkAddressLength);
 327     NCE->State = State;
 328     NCE->EventCount = 0;
 329
 330     TcpipReleaseSpinLock(&NeighborCache[HashValue].Lock, OldIrql);
 331
 332     if( !(NCE->State & NUD_INCOMPLETE) )
 333     {
 334         NCE->EventTimer = ARP_COMPLETE_TIMEOUT;
 335         NBSendPackets( NCE );
 336     }
 337 }
 338
 339 VOID
 340 NBResetNeighborTimeout(PIP_ADDRESS Address)
 341 {
 342     KIRQL OldIrql;
 343     UINT HashValue;
 344     PNEIGHBOR_CACHE_ENTRY NCE;
 345
 346     TI_DbgPrint(DEBUG_NCACHE, ("Resetting NCE timout for 0x%s\n", A2S(Address)));
 347
 348     HashValue  = *(PULONG)(&Address->Address);
 349     HashValue ^= HashValue >> 16;
 350     HashValue ^= HashValue >> 8;
 351     HashValue ^= HashValue >> 4;
 352     HashValue &= NB_HASHMASK;
 353
 354     TcpipAcquireSpinLock(&NeighborCache[HashValue].Lock, &OldIrql);
 355
 356     for (NCE = NeighborCache[HashValue].Cache;
 357          NCE != NULL;
 358          NCE = NCE->Next)
 359     {
 360          if (AddrIsEqual(Address, &NCE->Address))
 361          {
 362              NCE->EventCount = 0;
 363              break;
 364          }
 365     }
 366
 367     TcpipReleaseSpinLock(&NeighborCache[HashValue].Lock, OldIrql);
 368 }
 369
 370 PNEIGHBOR_CACHE_ENTRY NBLocateNeighbor(
 371   PIP_ADDRESS Address)
 372 /*
 373  * FUNCTION: Locates a neighbor in the neighbor cache
 374  * ARGUMENTS:
 375  *   Address = Pointer to IP address
 376  * RETURNS:
 377  *   Pointer to NCE, NULL if not found
 378  * NOTES:
 379  *   If the NCE is found, it is referenced. The caller is
 380  *   responsible for dereferencing it again after use
 381  */
 382 {
 383   PNEIGHBOR_CACHE_ENTRY NCE;
 384   UINT HashValue;
 385   KIRQL OldIrql;
 386
 387   TI_DbgPrint(DEBUG_NCACHE, ("Called. Address (0x%X).\n", Address));
 388
 389   HashValue = *(PULONG)&Address->Address;
 390   HashValue ^= HashValue >> 16;
 391   HashValue ^= HashValue >> 8;
 392   HashValue ^= HashValue >> 4;
 393   HashValue &= NB_HASHMASK;
 394
 395   TcpipAcquireSpinLock(&NeighborCache[HashValue].Lock, &OldIrql);
 396
 397   NCE = NeighborCache[HashValue].Cache;
 398
 399   while ((NCE) && (!AddrIsEqual(Address, &NCE->Address)))
 400     {
 401       NCE = NCE->Next;
 402     }
 403
 404   TcpipReleaseSpinLock(&NeighborCache[HashValue].Lock, OldIrql);
 405
 406   TI_DbgPrint(MAX_TRACE, ("Leaving.\n"));
 407
 408   return NCE;
 409 }
 410
 411 PNEIGHBOR_CACHE_ENTRY NBFindOrCreateNeighbor(
 412   PIP_INTERFACE Interface,
 413   PIP_ADDRESS Address)
 414 /*
 415  * FUNCTION: Tries to find a neighbor and if unsuccesful, creates a new NCE
 416  * ARGUMENTS:
 417  *   Interface = Pointer to interface to use (in case NCE is not found)
 418  *   Address   = Pointer to IP address
 419  * RETURNS:
 420  *   Pointer to NCE, NULL if there is not enough free resources
 421  * NOTES:
 422  *   The NCE is referenced if found or created. The caller is
 423  *   responsible for dereferencing it again after use
 424  */
 425 {
 426   PNEIGHBOR_CACHE_ENTRY NCE;
 427
 428   TI_DbgPrint(DEBUG_NCACHE, ("Called. Interface (0x%X)  Address (0x%X).\n", Interface, Address));
 429
 430   NCE = NBLocateNeighbor(Address);
 431   if (NCE == NULL)
 432     {
 433         TI_DbgPrint(MID_TRACE,("BCAST: %s\n", A2S(&Interface->Broadcast)));
 434         if( AddrIsEqual(Address, &Interface->Broadcast) ||
 435             AddrIsUnspecified(Address) ) {
 436             TI_DbgPrint(MID_TRACE,("Packet targeted at broadcast addr\n"));
 437             NCE = NBAddNeighbor(Interface, Address, NULL,
 438                                 Interface->AddressLength, NUD_PERMANENT, 0);
 439         } else {
 440             NCE = NBAddNeighbor(Interface, Address, NULL,
 441                                 Interface->AddressLength, NUD_INCOMPLETE, ARP_INCOMPLETE_TIMEOUT);
 442             if (!NCE) return NULL;
 443             NBSendSolicit(NCE);
 444         }
 445     }
 446
 447   return NCE;
 448 }
 449
 450 BOOLEAN NBQueuePacket(
 451   PNEIGHBOR_CACHE_ENTRY NCE,
 452   PNDIS_PACKET NdisPacket,
 453   PNEIGHBOR_PACKET_COMPLETE PacketComplete,
 454   PVOID PacketContext)
 455 /*
 456  * FUNCTION: Queues a packet on an NCE for later transmission
 457  * ARGUMENTS:
 458  *   NCE        = Pointer to NCE to queue packet on
 459  *   NdisPacket = Pointer to NDIS packet to queue
 460  * RETURNS:
 461  *   TRUE if the packet was successfully queued, FALSE if not
 462  */
 463 {
 464   KIRQL OldIrql;
 465   PNEIGHBOR_PACKET Packet;
 466   UINT HashValue;
 467
 468   TI_DbgPrint
 469       (DEBUG_NCACHE,
 470        ("Called. NCE (0x%X)  NdisPacket (0x%X).\n", NCE, NdisPacket));
 471
 472   Packet = ExAllocatePoolWithTag( NonPagedPool, sizeof(NEIGHBOR_PACKET),
 473                                   NEIGHBOR_PACKET_TAG );
 474   if( !Packet ) return FALSE;
 475
 476   /* FIXME: Should we limit the number of queued packets? */
 477
 478   HashValue  = *(PULONG)(&NCE->Address.Address);
 479   HashValue ^= HashValue >> 16;
 480   HashValue ^= HashValue >> 8;
 481   HashValue ^= HashValue >> 4;
 482   HashValue &= NB_HASHMASK;
 483
 484   TcpipAcquireSpinLock(&NeighborCache[HashValue].Lock, &OldIrql);
 485
 486   Packet->Complete = PacketComplete;
 487   Packet->Context = PacketContext;
 488   Packet->Packet = NdisPacket;
 489   InsertTailList( &NCE->PacketQueue, &Packet->Next );
 490
 491   TcpipReleaseSpinLock(&NeighborCache[HashValue].Lock, OldIrql);
 492
 493   if( !(NCE->State & NUD_INCOMPLETE) )
 494       NBSendPackets( NCE );
 495
 496   return TRUE;
 497 }
 498
 499 VOID NBRemoveNeighbor(
 500   PNEIGHBOR_CACHE_ENTRY NCE)
 501 /*
 502  * FUNCTION: Removes a neighbor from the neighbor cache
 503  * ARGUMENTS:
 504  *   NCE = Pointer to NCE to remove from cache
 505  * NOTES:
 506  *   The NCE must be in a safe state
 507  */
 508 {
 509   PNEIGHBOR_CACHE_ENTRY *PrevNCE;
 510   PNEIGHBOR_CACHE_ENTRY CurNCE;
 511   ULONG HashValue;
 512   KIRQL OldIrql;
 513
 514   TI_DbgPrint(DEBUG_NCACHE, ("Called. NCE (0x%X).\n", NCE));
 515
 516   HashValue  = *(PULONG)(&NCE->Address.Address);
 517   HashValue ^= HashValue >> 16;
 518   HashValue ^= HashValue >> 8;
 519   HashValue ^= HashValue >> 4;
 520   HashValue &= NB_HASHMASK;
 521
 522   TcpipAcquireSpinLock(&NeighborCache[HashValue].Lock, &OldIrql);
 523
 524   /* Search the list and remove the NCE from the list if found */
 525   for (PrevNCE = &NeighborCache[HashValue].Cache;
 526     (CurNCE = *PrevNCE) != NULL;
 527     PrevNCE = &CurNCE->Next)
 528     {
 529       if (CurNCE == NCE)
 530         {
 531           /* Found it, now unlink it from the list */
 532           *PrevNCE = CurNCE->Next;
 533
 534           NBFlushPacketQueue( CurNCE, NDIS_STATUS_REQUEST_ABORTED );
 535           ExFreePoolWithTag(CurNCE, NCE_TAG);
 536
 537           break;
 538         }
 539     }
 540
 541   TcpipReleaseSpinLock(&NeighborCache[HashValue].Lock, OldIrql);
 542 }
 543
 544 ULONG NBCopyNeighbors
 545 (PIP_INTERFACE Interface,
 546  PIPARP_ENTRY ArpTable)
 547 {
 548   PNEIGHBOR_CACHE_ENTRY CurNCE;
 549   KIRQL OldIrql;
 550   UINT Size = 0, i;
 551
 552   for (i = 0; i <= NB_HASHMASK; i++) {
 553       TcpipAcquireSpinLock(&NeighborCache[i].Lock, &OldIrql);
 554       for( CurNCE = NeighborCache[i].Cache;
 555            CurNCE;
 556            CurNCE = CurNCE->Next ) {
 557           if( CurNCE->Interface == Interface &&
 558               !AddrIsEqual( &CurNCE->Address, &CurNCE->Interface->Unicast ) ) {
 559               if( ArpTable ) {
 560                   ArpTable[Size].Index = Interface->Index;
 561                   ArpTable[Size].AddrSize = CurNCE->LinkAddressLength;
 562                   RtlCopyMemory
 563                       (ArpTable[Size].PhysAddr,
 564                        CurNCE->LinkAddress,
 565                        CurNCE->LinkAddressLength);
 566                   ArpTable[Size].LogAddr = CurNCE->Address.Address.IPv4Address;
 567                   if( CurNCE->State & NUD_PERMANENT )
 568                       ArpTable[Size].Type = ARP_ENTRY_STATIC;
 569                   else if( CurNCE->State & NUD_INCOMPLETE )
 570                       ArpTable[Size].Type = ARP_ENTRY_INVALID;
 571                   else
 572                       ArpTable[Size].Type = ARP_ENTRY_DYNAMIC;
 573               }
 574               Size++;
 575           }
 576       }
 577       TcpipReleaseSpinLock(&NeighborCache[i].Lock, OldIrql);
 578   }
 579
 580   return Size;
 581 }