reactos/lib/drivers/ip/network/router.c

   1 /*
   2  * COPYRIGHT:   See COPYING in the top level directory
   3  * PROJECT:     ReactOS TCP/IP protocol driver
   4  * FILE:        network/router.c
   5  * PURPOSE:     IP routing subsystem
   6  * PROGRAMMERS: Casper S. Hornstrup (chorns@users.sourceforge.net)
   7  * NOTES:
   8  *   This file holds authoritative routing information.
   9  *   Information queries on the route table should be handled here.
  10  *   This information should always override the route cache info.
  11  * REVISIONS:
  12  *   CSH 01/08-2000 Created
  13  */
  14
  15 #include "precomp.h"
  16
  17
  18 LIST_ENTRY FIBListHead;
  19 KSPIN_LOCK FIBLock;
  20
  21 void RouterDumpRoutes() {
  22     PLIST_ENTRY CurrentEntry;
  23     PLIST_ENTRY NextEntry;
  24     PFIB_ENTRY Current;
  25     PNEIGHBOR_CACHE_ENTRY NCE;
  26
  27     TI_DbgPrint(DEBUG_ROUTER,("Dumping Routes\n"));
  28
  29     CurrentEntry = FIBListHead.Flink;
  30     while (CurrentEntry != &FIBListHead) {
  31         NextEntry = CurrentEntry->Flink;
  32         Current = CONTAINING_RECORD(CurrentEntry, FIB_ENTRY, ListEntry);
  33
  34         NCE   = Current->Router;
  35
  36         TI_DbgPrint(DEBUG_ROUTER,("Examining FIBE %x\n", Current));
  37         TI_DbgPrint(DEBUG_ROUTER,("... NetworkAddress %s\n", A2S(&Current->NetworkAddress)));
  38         TI_DbgPrint(DEBUG_ROUTER,("... NCE->Address . %s\n", A2S(&NCE->Address)));
  39
  40         CurrentEntry = NextEntry;
  41     }
  42
  43     TI_DbgPrint(DEBUG_ROUTER,("Dumping Routes ... Done\n"));
  44 }
  45
  46 VOID FreeFIB(
  47     PVOID Object)
  48 /*
  49  * FUNCTION: Frees an forward information base object
  50  * ARGUMENTS:
  51  *     Object = Pointer to an forward information base structure
  52  */
  53 {
  54     ExFreePoolWithTag(Object, FIB_TAG);
  55 }
  56
  57
  58 VOID DestroyFIBE(
  59     PFIB_ENTRY FIBE)
  60 /*
  61  * FUNCTION: Destroys an forward information base entry
  62  * ARGUMENTS:
  63  *     FIBE = Pointer to FIB entry
  64  * NOTES:
  65  *     The forward information base lock must be held when called
  66  */
  67 {
  68     TI_DbgPrint(DEBUG_ROUTER, ("Called. FIBE (0x%X).\n", FIBE));
  69
  70     /* Unlink the FIB entry from the list */
  71     RemoveEntryList(&FIBE->ListEntry);
  72
  73     /* And free the FIB entry */
  74     FreeFIB(FIBE);
  75 }
  76
  77
  78 VOID DestroyFIBEs(
  79     VOID)
  80 /*
  81  * FUNCTION: Destroys all forward information base entries
  82  * NOTES:
  83  *     The forward information base lock must be held when called
  84  */
  85 {
  86     PLIST_ENTRY CurrentEntry;
  87     PLIST_ENTRY NextEntry;
  88     PFIB_ENTRY Current;
  89
  90     /* Search the list and remove every FIB entry we find */
  91     CurrentEntry = FIBListHead.Flink;
  92     while (CurrentEntry != &FIBListHead) {
  93         NextEntry = CurrentEntry->Flink;
  94         Current = CONTAINING_RECORD(CurrentEntry, FIB_ENTRY, ListEntry);
  95         /* Destroy the FIB entry */
  96         DestroyFIBE(Current);
  97         CurrentEntry = NextEntry;
  98     }
  99 }
 100
 101
 102 UINT CountFIBs(PIP_INTERFACE IF) {
 103     UINT FibCount = 0;
 104     PLIST_ENTRY CurrentEntry;
 105     PLIST_ENTRY NextEntry;
 106     PFIB_ENTRY Current;
 107
 108     CurrentEntry = FIBListHead.Flink;
 109     while (CurrentEntry != &FIBListHead) {
 110         NextEntry = CurrentEntry->Flink;
 111         Current = CONTAINING_RECORD(CurrentEntry, FIB_ENTRY, ListEntry);
 112         if (Current->Router->Interface == IF)
 113             FibCount++;
 114         CurrentEntry = NextEntry;
 115     }
 116
 117     return FibCount;
 118 }
 119
 120
 121 UINT CopyFIBs( PIP_INTERFACE IF, PFIB_ENTRY Target ) {
 122     UINT FibCount = 0;
 123     PLIST_ENTRY CurrentEntry;
 124     PLIST_ENTRY NextEntry;
 125     PFIB_ENTRY Current;
 126
 127     CurrentEntry = FIBListHead.Flink;
 128     while (CurrentEntry != &FIBListHead) {
 129         NextEntry = CurrentEntry->Flink;
 130         Current = CONTAINING_RECORD(CurrentEntry, FIB_ENTRY, ListEntry);
 131         if (Current->Router->Interface == IF)
 132         {
 133             Target[FibCount] = *Current;
 134             FibCount++;
 135         }
 136         CurrentEntry = NextEntry;
 137     }
 138
 139     return FibCount;
 140 }
 141
 142
 143 UINT CommonPrefixLength(
 144     PIP_ADDRESS Address1,
 145     PIP_ADDRESS Address2)
 146 /*
 147  * FUNCTION: Computes the length of the longest prefix common to two addresses
 148  * ARGUMENTS:
 149  *     Address1 = Pointer to first address
 150  *     Address2 = Pointer to second address
 151  * NOTES:
 152  *     The two addresses must be of the same type
 153  * RETURNS:
 154  *     Length of longest common prefix
 155  */
 156 {
 157     PUCHAR Addr1, Addr2;
 158     UINT Size;
 159     UINT i, j;
 160     UINT Bitmask;
 161
 162     TI_DbgPrint(DEBUG_ROUTER, ("Called. Address1 (0x%X)  Address2 (0x%X).\n", Address1, Address2));
 163
 164     /*TI_DbgPrint(DEBUG_ROUTER, ("Target  (%s) \n", A2S(Address1)));*/
 165     /*TI_DbgPrint(DEBUG_ROUTER, ("Adapter (%s).\n", A2S(Address2)));*/
 166
 167     if (Address1->Type == IP_ADDRESS_V4)
 168         Size = sizeof(IPv4_RAW_ADDRESS);
 169     else
 170         Size = sizeof(IPv6_RAW_ADDRESS);
 171
 172     Addr1 = (PUCHAR)&Address1->Address.IPv4Address;
 173     Addr2 = (PUCHAR)&Address2->Address.IPv4Address;
 174
 175     /* Find first non-matching byte */
 176     for (i = 0; i < Size && Addr1[i] == Addr2[i]; i++);
 177     if( i == Size ) return 8 * i;
 178
 179     /* Find first non-matching bit */
 180     Bitmask = 0x80;
 181     for (j = 0; (Addr1[i] & Bitmask) == (Addr2[i] & Bitmask); j++)
 182         Bitmask >>= 1;
 183
 184     TI_DbgPrint(DEBUG_ROUTER, ("Returning %d\n", 8 * i + j));
 185
 186     return 8 * i + j;
 187 }
 188
 189
 190 PFIB_ENTRY RouterAddRoute(
 191     PIP_ADDRESS NetworkAddress,
 192     PIP_ADDRESS Netmask,
 193     PNEIGHBOR_CACHE_ENTRY Router,
 194     UINT Metric)
 195 /*
 196  * FUNCTION: Adds a route to the Forward Information Base (FIB)
 197  * ARGUMENTS:
 198  *     NetworkAddress = Pointer to address of network
 199  *     Netmask        = Pointer to netmask of network
 200  *     Router         = Pointer to NCE of router to use
 201  *     Metric         = Cost of this route
 202  * RETURNS:
 203  *     Pointer to FIB entry if the route was added, NULL if not
 204  * NOTES:
 205  *     The FIB entry references the NetworkAddress, Netmask and
 206  *     the NCE of the router. The caller is responsible for providing
 207  *     these references
 208  */
 209 {
 210     PFIB_ENTRY FIBE;
 211
 212     TI_DbgPrint(DEBUG_ROUTER, ("Called. NetworkAddress (0x%X)  Netmask (0x%X) "
 213         "Router (0x%X)  Metric (%d).\n", NetworkAddress, Netmask, Router, Metric));
 214
 215     TI_DbgPrint(DEBUG_ROUTER, ("NetworkAddress (%s)  Netmask (%s)  Router (%s).\n",
 216                                A2S(NetworkAddress),
 217                                A2S(Netmask),
 218                                A2S(&Router->Address)));
 219
 220     FIBE = ExAllocatePoolWithTag(NonPagedPool, sizeof(FIB_ENTRY), FIB_TAG);
 221     if (!FIBE) {
 222         TI_DbgPrint(MIN_TRACE, ("Insufficient resources.\n"));
 223         return NULL;
 224     }
 225
 226     RtlCopyMemory( &FIBE->NetworkAddress, NetworkAddress,
 227                    sizeof(FIBE->NetworkAddress) );
 228     RtlCopyMemory( &FIBE->Netmask, Netmask,
 229                    sizeof(FIBE->Netmask) );
 230     FIBE->Router         = Router;
 231     FIBE->Metric         = Metric;
 232
 233     /* Add FIB to the forward information base */
 234     TcpipInterlockedInsertTailList(&FIBListHead, &FIBE->ListEntry, &FIBLock);
 235
 236     return FIBE;
 237 }
 238
 239
 240 PNEIGHBOR_CACHE_ENTRY RouterGetRoute(PIP_ADDRESS Destination)
 241 /*
 242  * FUNCTION: Finds a router to use to get to Destination
 243  * ARGUMENTS:
 244  *     Destination = Pointer to destination address (NULL means don't care)
 245  * RETURNS:
 246  *     Pointer to NCE for router, NULL if none was found
 247  * NOTES:
 248  *     If found the NCE is referenced
 249  */
 250 {
 251     KIRQL OldIrql;
 252     PLIST_ENTRY CurrentEntry;
 253     PLIST_ENTRY NextEntry;
 254     PFIB_ENTRY Current;
 255     UCHAR State;
 256     UINT Length, BestLength = 0, MaskLength;
 257     PNEIGHBOR_CACHE_ENTRY NCE, BestNCE = NULL;
 258
 259     TI_DbgPrint(DEBUG_ROUTER, ("Called. Destination (0x%X)\n", Destination));
 260
 261     TI_DbgPrint(DEBUG_ROUTER, ("Destination (%s)\n", A2S(Destination)));
 262
 263     TcpipAcquireSpinLock(&FIBLock, &OldIrql);
 264
 265     CurrentEntry = FIBListHead.Flink;
 266     while (CurrentEntry != &FIBListHead) {
 267         NextEntry = CurrentEntry->Flink;
 268             Current = CONTAINING_RECORD(CurrentEntry, FIB_ENTRY, ListEntry);
 269
 270         NCE   = Current->Router;
 271         State = NCE->State;
 272
 273         Length = CommonPrefixLength(Destination, &Current->NetworkAddress);
 274         MaskLength = AddrCountPrefixBits(&Current->Netmask);
 275
 276         TI_DbgPrint(DEBUG_ROUTER,("This-Route: %s (Sharing %d bits)\n",
 277                                   A2S(&NCE->Address), Length));
 278
 279         if(Length >= MaskLength && (Length > BestLength || !BestNCE) &&
 280            (!(State & NUD_STALE) || !BestNCE)) {
 281             /* This seems to be a better router */
 282             BestNCE    = NCE;
 283             BestLength = Length;
 284             TI_DbgPrint(DEBUG_ROUTER,("Route selected\n"));
 285         }
 286
 287         CurrentEntry = NextEntry;
 288     }
 289
 290     TcpipReleaseSpinLock(&FIBLock, OldIrql);
 291
 292     if( BestNCE ) {
 293         TI_DbgPrint(DEBUG_ROUTER,("Routing to %s\n", A2S(&BestNCE->Address)));
 294     } else {
 295         TI_DbgPrint(DEBUG_ROUTER,("Packet won't be routed\n"));
 296     }
 297
 298     return BestNCE;
 299 }
 300
 301 PNEIGHBOR_CACHE_ENTRY RouteGetRouteToDestination(PIP_ADDRESS Destination)
 302 /*
 303  * FUNCTION: Locates an RCN describing a route to a destination address
 304  * ARGUMENTS:
 305  *     Destination = Pointer to destination address to find route to
 306  *     RCN         = Address of pointer to an RCN
 307  * RETURNS:
 308  *     Status of operation
 309  * NOTES:
 310  *     The RCN is referenced for the caller. The caller is responsible
 311  *     for dereferencing it after use
 312  */
 313 {
 314     PNEIGHBOR_CACHE_ENTRY NCE = NULL;
 315     PIP_INTERFACE Interface;
 316
 317     TI_DbgPrint(DEBUG_RCACHE, ("Called. Destination (0x%X)\n", Destination));
 318
 319     TI_DbgPrint(DEBUG_RCACHE, ("Destination (%s)\n", A2S(Destination)));
 320
 321 #if 0
 322     TI_DbgPrint(MIN_TRACE, ("Displaying tree (before).\n"));
 323     PrintTree(RouteCache);
 324 #endif
 325
 326     /* Check if the destination is on-link */
 327     Interface = FindOnLinkInterface(Destination);
 328     if (Interface) {
 329         /* The destination address is on-link. Check our neighbor cache */
 330         NCE = NBFindOrCreateNeighbor(Interface, Destination, FALSE);
 331     } else {
 332         /* Destination is not on any subnets we're on. Find a router to use */
 333         NCE = RouterGetRoute(Destination);
 334     }
 335
 336     if( NCE )
 337         TI_DbgPrint(DEBUG_ROUTER,("Interface->MTU: %d\n", NCE->Interface->MTU));
 338
 339     return NCE;
 340 }
 341
 342 VOID RouterRemoveRoutesForInterface(PIP_INTERFACE Interface)
 343 {
 344     KIRQL OldIrql;
 345     PLIST_ENTRY CurrentEntry;
 346     PLIST_ENTRY NextEntry;
 347     PFIB_ENTRY Current;
 348
 349     TcpipAcquireSpinLock(&FIBLock, &OldIrql);
 350
 351     CurrentEntry = FIBListHead.Flink;
 352     while (CurrentEntry != &FIBListHead) {
 353         NextEntry = CurrentEntry->Flink;
 354         Current = CONTAINING_RECORD(CurrentEntry, FIB_ENTRY, ListEntry);
 355
 356         if (Interface == Current->Router->Interface)
 357             DestroyFIBE(Current);
 358
 359         CurrentEntry = NextEntry;
 360     }
 361
 362     TcpipReleaseSpinLock(&FIBLock, OldIrql);
 363 }
 364
 365 NTSTATUS RouterRemoveRoute(PIP_ADDRESS Target, PIP_ADDRESS Router)
 366 /*
 367  * FUNCTION: Removes a route from the Forward Information Base (FIB)
 368  * ARGUMENTS:
 369  *     Target: The machine or network targeted by the route
 370  *     Router: The router used to pass the packet to the destination
 371  *
 372  * Searches the FIB and removes a route matching the indicated parameters.
 373  */
 374 {
 375     KIRQL OldIrql;
 376     PLIST_ENTRY CurrentEntry;
 377     PLIST_ENTRY NextEntry;
 378     PFIB_ENTRY Current;
 379     BOOLEAN Found = FALSE;
 380     PNEIGHBOR_CACHE_ENTRY NCE;
 381
 382     TI_DbgPrint(DEBUG_ROUTER, ("Called\n"));
 383     TI_DbgPrint(DEBUG_ROUTER, ("Deleting Route From: %s\n", A2S(Router)));
 384     TI_DbgPrint(DEBUG_ROUTER, ("                 To: %s\n", A2S(Target)));
 385
 386     TcpipAcquireSpinLock(&FIBLock, &OldIrql);
 387
 388     RouterDumpRoutes();
 389
 390     CurrentEntry = FIBListHead.Flink;
 391     while (CurrentEntry != &FIBListHead) {
 392         NextEntry = CurrentEntry->Flink;
 393         Current = CONTAINING_RECORD(CurrentEntry, FIB_ENTRY, ListEntry);
 394
 395         NCE   = Current->Router;
 396
 397         if( AddrIsEqual( &Current->NetworkAddress, Target ) &&
 398             AddrIsEqual( &NCE->Address, Router ) ) {
 399             Found = TRUE;
 400             break;
 401         }
 402
 403         Current = NULL;
 404         CurrentEntry = NextEntry;
 405     }
 406
 407     if( Found ) {
 408         TI_DbgPrint(DEBUG_ROUTER, ("Deleting route\n"));
 409         DestroyFIBE( Current );
 410     }
 411
 412     RouterDumpRoutes();
 413
 414     TcpipReleaseSpinLock(&FIBLock, OldIrql);
 415
 416     TI_DbgPrint(DEBUG_ROUTER, ("Leaving\n"));
 417
 418     return Found ? STATUS_SUCCESS : STATUS_UNSUCCESSFUL;
 419 }
 420
 421
 422 PFIB_ENTRY RouterCreateRoute(
 423     PIP_ADDRESS NetworkAddress,
 424     PIP_ADDRESS Netmask,
 425     PIP_ADDRESS RouterAddress,
 426     PIP_INTERFACE Interface,
 427     UINT Metric)
 428 /*
 429  * FUNCTION: Creates a route with IPv4 addresses as parameters
 430  * ARGUMENTS:
 431  *     NetworkAddress = Address of network
 432  *     Netmask        = Netmask of network
 433  *     RouterAddress  = Address of router to use
 434  *     NTE            = Pointer to NTE to use
 435  *     Metric         = Cost of this route
 436  * RETURNS:
 437  *     Pointer to FIB entry if the route was created, NULL if not.
 438  *     The FIB entry references the NTE. The caller is responsible
 439  *     for providing this reference
 440  */
 441 {
 442     KIRQL OldIrql;
 443     PLIST_ENTRY CurrentEntry;
 444     PLIST_ENTRY NextEntry;
 445     PFIB_ENTRY Current;
 446     PNEIGHBOR_CACHE_ENTRY NCE;
 447
 448     TcpipAcquireSpinLock(&FIBLock, &OldIrql);
 449
 450     CurrentEntry = FIBListHead.Flink;
 451     while (CurrentEntry != &FIBListHead) {
 452         NextEntry = CurrentEntry->Flink;
 453         Current = CONTAINING_RECORD(CurrentEntry, FIB_ENTRY, ListEntry);
 454
 455         NCE   = Current->Router;
 456
 457         if(AddrIsEqual(NetworkAddress, &Current->NetworkAddress) &&
 458            AddrIsEqual(Netmask, &Current->Netmask) &&
 459            NCE->Interface == Interface)
 460         {
 461             TI_DbgPrint(DEBUG_ROUTER,("Attempting to add duplicate route to %s\n", A2S(NetworkAddress)));
 462             TcpipReleaseSpinLock(&FIBLock, OldIrql);
 463             return NULL;
 464         }
 465
 466         CurrentEntry = NextEntry;
 467     }
 468
 469     TcpipReleaseSpinLock(&FIBLock, OldIrql);
 470
 471     /* The NCE references RouterAddress. The NCE is referenced for us */
 472     NCE = NBFindOrCreateNeighbor(Interface, RouterAddress, TRUE);
 473
 474     if (!NCE) {
 475         /* Not enough free resources */
 476         return NULL;
 477     }
 478
 479     return RouterAddRoute(NetworkAddress, Netmask, NCE, Metric);
 480 }
 481
 482
 483 NTSTATUS RouterStartup(
 484     VOID)
 485 /*
 486  * FUNCTION: Initializes the routing subsystem
 487  * RETURNS:
 488  *     Status of operation
 489  */
 490 {
 491     TI_DbgPrint(DEBUG_ROUTER, ("Called.\n"));
 492
 493     /* Initialize the Forward Information Base */
 494     InitializeListHead(&FIBListHead);
 495     TcpipInitializeSpinLock(&FIBLock);
 496
 497     return STATUS_SUCCESS;
 498 }
 499
 500
 501 NTSTATUS RouterShutdown(
 502     VOID)
 503 /*
 504  * FUNCTION: Shuts down the routing subsystem
 505  * RETURNS:
 506  *     Status of operation
 507  */
 508 {
 509     KIRQL OldIrql;
 510
 511     TI_DbgPrint(DEBUG_ROUTER, ("Called.\n"));
 512
 513     /* Clear Forward Information Base */
 514     TcpipAcquireSpinLock(&FIBLock, &OldIrql);
 515     DestroyFIBEs();
 516     TcpipReleaseSpinLock(&FIBLock, OldIrql);
 517
 518     return STATUS_SUCCESS;
 519 }
 520
 521 /* EOF */