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