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