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