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