drivers/net/tcpip/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 #include <tcpip.h>
  11 #include <neighbor.h>
  12 #include <routines.h>
  13 #include <neighbor.h>
  14 #include <transmit.h>
  15 #include <address.h>
  16 #include <route.h>
  17 #include <pool.h>
  18 #include <arp.h>
  19 #include <ip.h>
  20
  21
  22 NEIGHBOR_CACHE_TABLE NeighborCache[NB_HASHMASK + 1];
  23
  24
  25 VOID FreeNCE(
  26     PVOID Object)
  27 {
  28     ExFreePool(Object);
  29 }
  30
  31
  32 VOID NCETimeout(
  33     PNEIGHBOR_CACHE_ENTRY NCE)
  34 /*
  35  * FUNCTION: Neighbor cache entry timeout handler
  36  * NOTES:
  37  *     The neighbor cache lock must be held
  38  */
  39 {
  40     PNDIS_PACKET NdisPacket, Next;
  41
  42     TI_DbgPrint(DEBUG_NCACHE, ("Called. NCE (0x%X).\n", NCE));
  43
  44     TI_DbgPrint(DEBUG_NCACHE, ("NCE->State is (0x%X).\n", NCE->State));
  45
  46     switch (NCE->State) {
  47     case NUD_INCOMPLETE:
  48         /* Retransmission timer expired */
  49         if (NCE->EventCount++ > MAX_MULTICAST_SOLICIT) {
  50             /* We have retransmitted too many times */
  51
  52             /* Calling IPSendComplete with cache lock held is not
  53                a great thing to do. We don't get here very often
  54                so maybe it's not that big a problem */
  55
  56             /* Flush packet queue */
  57             NdisPacket = NCE->WaitQueue;
  58             while (NdisPacket) {
  59                 Next = (PNDIS_PACKET)PC(NdisPacket)->DLComplete;
  60                 IPSendComplete((PVOID)NCE->Interface, NdisPacket,
  61                     NDIS_STATUS_REQUEST_ABORTED);
  62                 NdisPacket = Next;
  63             }
  64             NCE->WaitQueue = NULL;
  65
  66             NCE->EventCount = 0;
  67
  68             /* Remove route cache entries with references to this NCE.
  69                Remember that neighbor cache lock is taken before
  70                route cache lock */
  71             RouteInvalidateNCE(NCE);
  72         } else
  73             /* Retransmit request */
  74             NBSendSolicit(NCE);
  75         break;
  76
  77     case NUD_DELAY:
  78         /* FIXME: Delayed state */
  79         TI_DbgPrint(DEBUG_NCACHE, ("NCE delay state.\n"));
  80         break;
  81
  82     case NUD_PROBE:
  83         /* FIXME: Probe state */
  84         TI_DbgPrint(DEBUG_NCACHE, ("NCE probe state.\n"));
  85         break;
  86
  87     default:
  88         /* Should not happen since other states don't use the event timer */
  89         TI_DbgPrint(MIN_TRACE, ("Invalid NCE state (%d).\n", NCE->State));
  90         break;
  91     }
  92 }
  93
  94
  95 VOID NBTimeout(
  96     VOID)
  97 /*
  98  * FUNCTION: Neighbor address cache timeout handler
  99  * NOTES:
 100  *     This routine is called by IPTimeout to remove outdated cache
 101  *     entries.
 102  */
 103 {
 104     UINT i;
 105     KIRQL OldIrql;
 106     PNEIGHBOR_CACHE_ENTRY NCE;
 107
 108     for (i = 0; i <= NB_HASHMASK; i++) {
 109         KeAcquireSpinLock(&NeighborCache[i].Lock, &OldIrql);
 110
 111         for (NCE = NeighborCache[i].Cache;
 112             NCE != NULL; NCE = NCE->Next) {
 113             /* Check if event timer is running */
 114             if (NCE->EventTimer != 0)  {
 115                 if (--NCE->EventTimer == 0) {
 116                     /* Call timeout handler for NCE */
 117                     NCETimeout(NCE);
 118                 }
 119             }
 120         }
 121
 122         KeReleaseSpinLock(&NeighborCache[i].Lock, OldIrql);
 123     }
 124 }
 125
 126
 127 VOID NBStartup(
 128     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         KeInitializeSpinLock(&NeighborCache[i].Lock);
 140     }
 141 }
 142
 143
 144 VOID NBShutdown(
 145     VOID)
 146 /*
 147  * FUNCTION: Shuts down the neighbor cache
 148  */
 149 {
 150         UINT i;
 151     KIRQL OldIrql;
 152     PNDIS_PACKET NdisPacket, Next;
 153     PNEIGHBOR_CACHE_ENTRY CurNCE, NextNCE;
 154
 155     TI_DbgPrint(DEBUG_NCACHE, ("Called.\n"));
 156
 157     /* Remove possible entries from the cache */
 158     for (i = 0; i <= NB_HASHMASK; i++) {
 159         KeAcquireSpinLock(&NeighborCache[i].Lock, &OldIrql);
 160
 161         CurNCE = NeighborCache[i].Cache;
 162         while (CurNCE) {
 163             NextNCE = CurNCE->Next;
 164
 165             /* Remove all references from route cache */
 166             RouteInvalidateNCE(CurNCE);
 167
 168             /* Flush wait queue */
 169             NdisPacket = CurNCE->WaitQueue;
 170             while (NdisPacket) {
 171                 Next = (PNDIS_PACKET)PC(NdisPacket)->DLComplete;
 172                 FreeNdisPacket(NdisPacket);
 173                 NdisPacket = Next;
 174             }
 175
 176 #if DBG
 177             if (CurNCE->RefCount != 1) {
 178                 TI_DbgPrint(DEBUG_REFCOUNT, ("NCE at (0x%X) has (%d) references (should be 1).\n", CurNCE, CurNCE->RefCount));
 179             }
 180 #endif
 181
 182             /* Remove reference for being alive */
 183             DereferenceObject(CurNCE);
 184
 185             CurNCE = NextNCE;
 186         }
 187         NeighborCache[i].Cache = NULL;
 188
 189         KeReleaseSpinLock(&NeighborCache[i].Lock, OldIrql);
 190     }
 191
 192     TI_DbgPrint(MAX_TRACE, ("Leaving.\n"));
 193 }
 194
 195
 196 VOID NBSendSolicit(
 197     PNEIGHBOR_CACHE_ENTRY NCE)
 198 /*
 199  * FUNCTION: Sends a neighbor solicitation message
 200  * ARGUMENTS:
 201  *     NCE = Pointer to NCE of neighbor to solicit
 202  * NOTES:
 203  *     May be called with lock held on NCE's table
 204  */
 205 {
 206     PLIST_ENTRY CurrentEntry;
 207     PNET_TABLE_ENTRY NTE;
 208
 209     TI_DbgPrint(DEBUG_NCACHE, ("Called. NCE (0x%X).\n", NCE));
 210
 211     if (NCE->State == NUD_INCOMPLETE) {
 212         /* This is the first solicitation of this neighbor. Broadcast
 213            a request for the neighbor */
 214
 215         /* FIXME: Choose first NTE. We might want to give an NTE as argument */
 216         CurrentEntry = NCE->Interface->NTEListHead.Flink;
 217         if (!IsListEmpty(CurrentEntry)) {
 218             NTE = CONTAINING_RECORD(CurrentEntry, NET_TABLE_ENTRY, IFListEntry);
 219             ARPTransmit(NCE->Address, NTE);
 220         } else {
 221             TI_DbgPrint(MIN_TRACE, ("Interface at 0x%X has zero NTE.\n", NCE->Interface));
 222         }
 223     } else {
 224         /* FIXME: Unicast solicitation since we have a cached address */
 225         TI_DbgPrint(MIN_TRACE, ("Uninplemented unicast solicitation.\n"));
 226     }
 227 }
 228
 229
 230 PNEIGHBOR_CACHE_ENTRY NBAddNeighbor(
 231     PIP_INTERFACE Interface,
 232     PIP_ADDRESS Address,
 233     PVOID LinkAddress,
 234     UINT LinkAddressLength,
 235     UCHAR State)
 236 /*
 237  * FUNCTION: Adds a neighbor to the neighbor cache
 238  * ARGUMENTS:
 239  *     Interface         = Pointer to interface
 240  *     Address           = Pointer to IP address
 241  *     LinkAddress       = Pointer to link address (may be NULL)
 242  *     LinkAddressLength = Length of link address
 243  *     State             = State of NCE
 244  * RETURNS:
 245  *     Pointer to NCE, NULL there is not enough free resources
 246  * NOTES:
 247  *     The NCE if referenced for the caller if created. The NCE retains
 248  *     a reference to the IP address if it is created, the caller is
 249  *     responsible for providing this reference
 250  */
 251 {
 252     ULONG HashValue;
 253     KIRQL OldIrql;
 254     PNEIGHBOR_CACHE_ENTRY NCE;
 255
 256     TI_DbgPrint(DEBUG_NCACHE, ("Called. Interface (0x%X)  Address (0x%X)  "
 257         "LinkAddress (0x%X)  LinkAddressLength (%d)  State (0x%X)\n",
 258         Interface, Address, LinkAddress, LinkAddressLength, State));
 259
 260     NCE = ExAllocatePool(NonPagedPool, sizeof(NEIGHBOR_CACHE_ENTRY) + LinkAddressLength);
 261     if (!NCE) {
 262         TI_DbgPrint(MIN_TRACE, ("Insufficient resources.\n"));
 263         return NULL;
 264     }
 265
 266     INIT_TAG(NCE, TAG('N','C','E',' '));
 267
 268     /* Initialize NCE free routine */
 269     NCE->Free = FreeNCE;
 270
 271     /* Reference once for beeing alive and once for the caller */
 272     NCE->RefCount  = 2;
 273     NCE->Interface = Interface;
 274     NCE->Address   = Address;
 275     NCE->LinkAddressLength = LinkAddressLength;
 276     NCE->LinkAddress       = (PVOID)((ULONG_PTR)NCE + sizeof(NEIGHBOR_CACHE_ENTRY));
 277     if (LinkAddress)
 278         RtlCopyMemory(NCE->LinkAddress, LinkAddress, LinkAddressLength);
 279     NCE->State      = State;
 280     NCE->EventTimer = 0; /* Not in use */
 281     NCE->WaitQueue  = NULL;
 282
 283     HashValue  = *(PULONG)&Address->Address;
 284     HashValue ^= HashValue >> 16;
 285     HashValue ^= HashValue >> 8;
 286     HashValue ^= HashValue >> 4;
 287     HashValue &= NB_HASHMASK;
 288
 289     NCE->Table = &NeighborCache[HashValue];
 290
 291     KeAcquireSpinLock(&NeighborCache[HashValue].Lock, &OldIrql);
 292
 293     NCE->Next = NeighborCache[HashValue].Cache;
 294     NeighborCache[HashValue].Cache = NCE;
 295
 296     KeReleaseSpinLock(&NeighborCache[HashValue].Lock, OldIrql);
 297
 298     return NCE;
 299 }
 300
 301
 302 VOID NBUpdateNeighbor(
 303     PNEIGHBOR_CACHE_ENTRY NCE,
 304     PVOID LinkAddress,
 305     UCHAR State)
 306 /*
 307  * FUNCTION: Update link address information in NCE
 308  * ARGUMENTS:
 309  *     NCE         = Pointer to NCE to update
 310  *     LinkAddress = Pointer to link address
 311  *     State       = State of NCE
 312  * NOTES:
 313  *     The link address and state is updated. Any waiting packets are sent
 314  */
 315 {
 316     KIRQL OldIrql;
 317     PNDIS_PACKET Current;
 318     PNDIS_PACKET Next;
 319
 320     TI_DbgPrint(DEBUG_NCACHE, ("Called. NCE (0x%X)  LinkAddress (0x%X)  State (0x%X).\n", NCE, LinkAddress, State));
 321
 322     KeAcquireSpinLock(&NCE->Table->Lock, &OldIrql);
 323
 324     RtlCopyMemory(NCE->LinkAddress, LinkAddress, NCE->LinkAddressLength);
 325     NCE->State     = State;
 326     Current        = NCE->WaitQueue;
 327     NCE->WaitQueue = NULL;
 328
 329     KeReleaseSpinLock(&NCE->Table->Lock, OldIrql);
 330 #if 1
 331     /* Send any waiting packets */
 332     while (Current) {
 333         /* Our link to the next packet is broken by the
 334            datalink layer code so we must save it here */
 335         Next = (PNDIS_PACKET)PC(Current)->DLComplete;
 336         IPSendFragment(Current, NCE);
 337         Current = Next;
 338     }
 339 #endif
 340 }
 341
 342
 343 PNEIGHBOR_CACHE_ENTRY NBLocateNeighbor(
 344     PIP_ADDRESS Address)
 345 /*
 346  * FUNCTION: Locates a neighbor in the neighbor cache
 347  * ARGUMENTS:
 348  *     Address = Pointer to IP address
 349  * RETURNS:
 350  *     Pointer to NCE, NULL if not found
 351  * NOTES:
 352  *     If the NCE is found, it is referenced. The caller is
 353  *     responsible for dereferencing it again after use
 354  */
 355 {
 356     UINT HashValue;
 357     KIRQL OldIrql;
 358     PNEIGHBOR_CACHE_ENTRY NCE;
 359
 360     TI_DbgPrint(DEBUG_NCACHE, ("Called. Address (0x%X).\n", Address));
 361
 362     HashValue  = *(PULONG)&Address->Address;
 363     HashValue ^= HashValue >> 16;
 364     HashValue ^= HashValue >> 8;
 365     HashValue ^= HashValue >> 4;
 366     HashValue &= NB_HASHMASK;
 367
 368     KeAcquireSpinLock(&NeighborCache[HashValue].Lock, &OldIrql);
 369
 370     NCE = NeighborCache[HashValue].Cache;
 371
 372     while ((NCE) && (!AddrIsEqual(Address, NCE->Address)))
 373         NCE = NCE->Next;
 374
 375     if (NCE)
 376         ReferenceObject(NCE);
 377
 378     KeReleaseSpinLock(&NeighborCache[HashValue].Lock, OldIrql);
 379
 380     TI_DbgPrint(MAX_TRACE, ("Leaving.\n"));
 381
 382     return NCE;
 383 }
 384
 385
 386 PNEIGHBOR_CACHE_ENTRY NBFindOrCreateNeighbor(
 387     PIP_INTERFACE Interface,
 388     PIP_ADDRESS Address)
 389 /*
 390  * FUNCTION: Tries to find a neighbor and if unsuccesful, creates a new NCE
 391  * ARGUMENTS:
 392  *     Interface = Pointer to interface to use (if NCE is not found)
 393  *     Address   = Pointer to IP address
 394  * RETURNS:
 395  *     Pointer to NCE, NULL if there is not enough free resources
 396  * NOTES:
 397  *     The NCE is referenced if found or created. The caller is
 398  *     responsible for dereferencing it again after use
 399  */
 400 {
 401     PNEIGHBOR_CACHE_ENTRY NCE;
 402
 403     TI_DbgPrint(DEBUG_NCACHE, ("Called. Interface (0x%X)  Address (0x%X).\n", Interface, Address));
 404
 405     NCE = NBLocateNeighbor(Address);
 406     if (!NCE) {
 407         ReferenceObject(Address);
 408         NCE = NBAddNeighbor(Interface, Address, NULL,
 409             Interface->AddressLength, NUD_INCOMPLETE);
 410         NCE->EventTimer = 1;
 411         NCE->EventCount = 0;
 412     }
 413
 414     return NCE;
 415 }
 416
 417
 418 BOOLEAN NBQueuePacket(
 419     PNEIGHBOR_CACHE_ENTRY NCE,
 420     PNDIS_PACKET NdisPacket)
 421 /*
 422  * FUNCTION: Queues a packet on an NCE for later transmission
 423  * ARGUMENTS:
 424  *     NCE        = Pointer to NCE to queue packet on
 425  *     NdisPacket = Pointer to NDIS packet to queue
 426  * RETURNS:
 427  *     TRUE if the packet was successfully queued, FALSE if not
 428  */
 429 {
 430     KIRQL OldIrql;
 431     PKSPIN_LOCK Lock;
 432
 433     TI_DbgPrint(DEBUG_NCACHE, ("Called. NCE (0x%X)  NdisPacket (0x%X).\n", NCE, NdisPacket));
 434
 435     /* FIXME: Should we limit the number of queued packets? */
 436
 437     Lock = &NCE->Table->Lock;
 438
 439     KeAcquireSpinLock(Lock, &OldIrql);
 440
 441     /* Use data link level completion handler pointer to link
 442        queued packets together */
 443     PC(NdisPacket)->DLComplete = (PACKET_COMPLETION_ROUTINE)NCE->WaitQueue;
 444     NCE->WaitQueue = NdisPacket;
 445
 446     KeReleaseSpinLock(Lock, OldIrql);
 447
 448     return TRUE;
 449 }
 450
 451
 452 VOID NBRemoveNeighbor(
 453     PNEIGHBOR_CACHE_ENTRY NCE)
 454 /*
 455  * FUNCTION: Removes a neighbor from the neighbor cache
 456  * ARGUMENTS:
 457  *     NCE = Pointer to NCE to remove from cache
 458  * NOTES:
 459  *     The NCE must be in a safe state
 460  */
 461 {
 462     ULONG HashValue;
 463     KIRQL OldIrql;
 464     PNEIGHBOR_CACHE_ENTRY *PrevNCE;
 465     PNEIGHBOR_CACHE_ENTRY CurNCE;
 466     PNDIS_PACKET NdisPacket, Next;
 467
 468     TI_DbgPrint(DEBUG_NCACHE, ("Called. NCE (0x%X).\n", NCE));
 469
 470           HashValue  = *(PULONG)(&NCE->Address->Address);
 471     HashValue ^= HashValue >> 16;
 472           HashValue ^= HashValue >> 8;
 473           HashValue ^= HashValue >> 4;
 474           HashValue &= NB_HASHMASK;
 475
 476     KeAcquireSpinLock(&NeighborCache[HashValue].Lock, &OldIrql);
 477
 478     /* Search the list and remove the NCE from the list if found */
 479     for (PrevNCE = &NeighborCache[HashValue].Cache;
 480         (CurNCE  = *PrevNCE) != NULL;
 481         PrevNCE  = &CurNCE->Next) {
 482         if (CurNCE == NCE) {
 483             /* Found it, now unlink it from the list */
 484             *PrevNCE = CurNCE->Next;
 485
 486             /* Purge wait queue */
 487             NdisPacket = CurNCE->WaitQueue;
 488             while (NdisPacket) {
 489                 Next = (PNDIS_PACKET)PC(NdisPacket)->DLComplete;
 490                 FreeNdisPacket(NdisPacket);
 491                 NdisPacket = Next;
 492             }
 493
 494             /* Remove all references from route cache */
 495             RouteInvalidateNCE(CurNCE);
 496
 497             /* Remove reference to the address */
 498             DereferenceObject(CurNCE->Address);
 499
 500 #if DBG
 501             CurNCE->RefCount--;
 502
 503             if (CurNCE->RefCount != 0) {
 504                 TI_DbgPrint(DEBUG_REFCOUNT, ("NCE at (0x%X) has (%d) references (should be 0).\n", CurNCE, CurNCE->RefCount));
 505             }
 506 #endif
 507             ExFreePool(CurNCE);
 508
 509             KeReleaseSpinLock(&NeighborCache[HashValue].Lock, OldIrql);
 510
 511             return;
 512         }
 513     }
 514
 515     KeReleaseSpinLock(&NeighborCache[HashValue].Lock, OldIrql);
 516 }
 517
 518 /* EOF */