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               MaxLLHeaderSize,
  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 }