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     exFreePool(Object);
  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 = exAllocatePool(NonPagedPool, sizeof(FIB_ENTRY));
 221     if (!FIBE) {
 222         TI_DbgPrint(MIN_TRACE, ("Insufficient resources.\n"));
 223         return NULL;
 224     }
 225
 226     INIT_TAG(Router, 'TUOR');
 227
 228     RtlCopyMemory( &FIBE->NetworkAddress, NetworkAddress,
 229                    sizeof(FIBE->NetworkAddress) );
 230     RtlCopyMemory( &FIBE->Netmask, Netmask,
 231                    sizeof(FIBE->Netmask) );
 232     FIBE->Router         = Router;
 233     FIBE->Metric         = Metric;
 234
 235     /* Add FIB to the forward information base */
 236     TcpipInterlockedInsertTailList(&FIBListHead, &FIBE->ListEntry, &FIBLock);
 237
 238     return FIBE;
 239 }
 240
 241
 242 PNEIGHBOR_CACHE_ENTRY RouterGetRoute(PIP_ADDRESS Destination)
 243 /*
 244  * FUNCTION: Finds a router to use to get to Destination
 245  * ARGUMENTS:
 246  *     Destination = Pointer to destination address (NULL means don't care)
 247  * RETURNS:
 248  *     Pointer to NCE for router, NULL if none was found
 249  * NOTES:
 250  *     If found the NCE is referenced
 251  */
 252 {
 253     KIRQL OldIrql;
 254     PLIST_ENTRY CurrentEntry;
 255     PLIST_ENTRY NextEntry;
 256     PFIB_ENTRY Current;
 257     UCHAR State, BestState = 0;
 258     UINT Length, BestLength = 0, MaskLength;
 259     PNEIGHBOR_CACHE_ENTRY NCE, BestNCE = NULL;
 260
 261     TI_DbgPrint(DEBUG_ROUTER, ("Called. Destination (0x%X)\n", Destination));
 262
 263     TI_DbgPrint(DEBUG_ROUTER, ("Destination (%s)\n", A2S(Destination)));
 264
 265     TcpipAcquireSpinLock(&FIBLock, &OldIrql);
 266
 267     CurrentEntry = FIBListHead.Flink;
 268     while (CurrentEntry != &FIBListHead) {
 269         NextEntry = CurrentEntry->Flink;
 270             Current = CONTAINING_RECORD(CurrentEntry, FIB_ENTRY, ListEntry);
 271
 272         NCE   = Current->Router;
 273         State = NCE->State;
 274
 275         Length = CommonPrefixLength(Destination, &Current->NetworkAddress);
 276         MaskLength = AddrCountPrefixBits(&Current->Netmask);
 277
 278         TI_DbgPrint(DEBUG_ROUTER,("This-Route: %s (Sharing %d bits)\n",
 279                                   A2S(&NCE->Address), Length));
 280
 281         if(Length >= MaskLength && (Length > BestLength || !BestNCE) &&
 282            (!(State & NUD_STALE) || !BestNCE)) {
 283             /* This seems to be a better router */
 284             BestNCE    = NCE;
 285             BestLength = Length;
 286             BestState  = State;
 287             TI_DbgPrint(DEBUG_ROUTER,("Route selected\n"));
 288         }
 289
 290         CurrentEntry = NextEntry;
 291     }
 292
 293     TcpipReleaseSpinLock(&FIBLock, OldIrql);
 294
 295     if( BestNCE ) {
 296         TI_DbgPrint(DEBUG_ROUTER,("Routing to %s\n", A2S(&BestNCE->Address)));
 297     } else {
 298         TI_DbgPrint(DEBUG_ROUTER,("Packet won't be routed\n"));
 299     }
 300
 301     return BestNCE;
 302 }
 303
 304 PNEIGHBOR_CACHE_ENTRY RouteGetRouteToDestination(PIP_ADDRESS Destination)
 305 /*
 306  * FUNCTION: Locates an RCN describing a route to a destination address
 307  * ARGUMENTS:
 308  *     Destination = Pointer to destination address to find route to
 309  *     RCN         = Address of pointer to an RCN
 310  * RETURNS:
 311  *     Status of operation
 312  * NOTES:
 313  *     The RCN is referenced for the caller. The caller is responsible
 314  *     for dereferencing it after use
 315  */
 316 {
 317     PNEIGHBOR_CACHE_ENTRY NCE = NULL;
 318     PIP_INTERFACE Interface;
 319
 320     TI_DbgPrint(DEBUG_RCACHE, ("Called. Destination (0x%X)\n", Destination));
 321
 322     TI_DbgPrint(DEBUG_RCACHE, ("Destination (%s)\n", A2S(Destination)));
 323
 324 #if 0
 325     TI_DbgPrint(MIN_TRACE, ("Displaying tree (before).\n"));
 326     PrintTree(RouteCache);
 327 #endif
 328
 329     /* Check if the destination is on-link */
 330     Interface = FindOnLinkInterface(Destination);
 331     if (Interface) {
 332         /* The destination address is on-link. Check our neighbor cache */
 333         NCE = NBFindOrCreateNeighbor(Interface, Destination);
 334     } else {
 335         /* Destination is not on any subnets we're on. Find a router to use */
 336         NCE = RouterGetRoute(Destination);
 337     }
 338
 339     if( NCE )
 340         TI_DbgPrint(DEBUG_ROUTER,("Interface->MTU: %d\n", NCE->Interface->MTU));
 341
 342     return NCE;
 343 }
 344
 345 NTSTATUS RouterRemoveRoute(PIP_ADDRESS Target, PIP_ADDRESS Router)
 346 /*
 347  * FUNCTION: Removes a route from the Forward Information Base (FIB)
 348  * ARGUMENTS:
 349  *     Target: The machine or network targeted by the route
 350  *     Router: The router used to pass the packet to the destination
 351  *
 352  * Searches the FIB and removes a route matching the indicated parameters.
 353  */
 354 {
 355     KIRQL OldIrql;
 356     PLIST_ENTRY CurrentEntry;
 357     PLIST_ENTRY NextEntry;
 358     PFIB_ENTRY Current;
 359     BOOLEAN Found = FALSE;
 360     PNEIGHBOR_CACHE_ENTRY NCE;
 361
 362     TI_DbgPrint(DEBUG_ROUTER, ("Called\n"));
 363     TI_DbgPrint(DEBUG_ROUTER, ("Deleting Route From: %s\n", A2S(Router)));
 364     TI_DbgPrint(DEBUG_ROUTER, ("                 To: %s\n", A2S(Target)));
 365
 366     TcpipAcquireSpinLock(&FIBLock, &OldIrql);
 367
 368     RouterDumpRoutes();
 369
 370     CurrentEntry = FIBListHead.Flink;
 371     while (CurrentEntry != &FIBListHead) {
 372         NextEntry = CurrentEntry->Flink;
 373         Current = CONTAINING_RECORD(CurrentEntry, FIB_ENTRY, ListEntry);
 374
 375         NCE   = Current->Router;
 376
 377         if( AddrIsEqual( &Current->NetworkAddress, Target ) &&
 378             AddrIsEqual( &NCE->Address, Router ) ) {
 379             Found = TRUE;
 380             break;
 381         }
 382
 383         Current = NULL;
 384         CurrentEntry = NextEntry;
 385     }
 386
 387     if( Found ) {
 388         TI_DbgPrint(DEBUG_ROUTER, ("Deleting route\n"));
 389         DestroyFIBE( Current );
 390     }
 391
 392     RouterDumpRoutes();
 393
 394     TcpipReleaseSpinLock(&FIBLock, OldIrql);
 395
 396     TI_DbgPrint(DEBUG_ROUTER, ("Leaving\n"));
 397
 398     return Found ? STATUS_SUCCESS : STATUS_UNSUCCESSFUL;
 399 }
 400
 401
 402 PFIB_ENTRY RouterCreateRoute(
 403     PIP_ADDRESS NetworkAddress,
 404     PIP_ADDRESS Netmask,
 405     PIP_ADDRESS RouterAddress,
 406     PIP_INTERFACE Interface,
 407     UINT Metric)
 408 /*
 409  * FUNCTION: Creates a route with IPv4 addresses as parameters
 410  * ARGUMENTS:
 411  *     NetworkAddress = Address of network
 412  *     Netmask        = Netmask of network
 413  *     RouterAddress  = Address of router to use
 414  *     NTE            = Pointer to NTE to use
 415  *     Metric         = Cost of this route
 416  * RETURNS:
 417  *     Pointer to FIB entry if the route was created, NULL if not.
 418  *     The FIB entry references the NTE. The caller is responsible
 419  *     for providing this reference
 420  */
 421 {
 422     KIRQL OldIrql;
 423     PLIST_ENTRY CurrentEntry;
 424     PLIST_ENTRY NextEntry;
 425     PFIB_ENTRY Current;
 426     PNEIGHBOR_CACHE_ENTRY NCE;
 427
 428     TcpipAcquireSpinLock(&FIBLock, &OldIrql);
 429
 430     CurrentEntry = FIBListHead.Flink;
 431     while (CurrentEntry != &FIBListHead) {
 432         NextEntry = CurrentEntry->Flink;
 433         Current = CONTAINING_RECORD(CurrentEntry, FIB_ENTRY, ListEntry);
 434
 435         NCE   = Current->Router;
 436
 437         if( AddrIsEqual(NetworkAddress, &Current->NetworkAddress) &&
 438             AddrIsEqual(Netmask, &Current->Netmask) ) {
 439             TI_DbgPrint(DEBUG_ROUTER,("Attempting to add duplicate route to %s\n", A2S(NetworkAddress)));
 440             TcpipReleaseSpinLock(&FIBLock, OldIrql);
 441             return NULL;
 442         }
 443
 444         CurrentEntry = NextEntry;
 445     }
 446
 447     TcpipReleaseSpinLock(&FIBLock, OldIrql);
 448
 449     /* The NCE references RouterAddress. The NCE is referenced for us */
 450     NCE = NBFindOrCreateNeighbor(Interface, RouterAddress);
 451
 452     if (!NCE) {
 453         /* Not enough free resources */
 454         return NULL;
 455     }
 456
 457     return RouterAddRoute(NetworkAddress, Netmask, NCE, Metric);
 458 }
 459
 460
 461 NTSTATUS RouterStartup(
 462     VOID)
 463 /*
 464  * FUNCTION: Initializes the routing subsystem
 465  * RETURNS:
 466  *     Status of operation
 467  */
 468 {
 469     TI_DbgPrint(DEBUG_ROUTER, ("Called.\n"));
 470
 471     /* Initialize the Forward Information Base */
 472     InitializeListHead(&FIBListHead);
 473     TcpipInitializeSpinLock(&FIBLock);
 474
 475     return STATUS_SUCCESS;
 476 }
 477
 478
 479 NTSTATUS RouterShutdown(
 480     VOID)
 481 /*
 482  * FUNCTION: Shuts down the routing subsystem
 483  * RETURNS:
 484  *     Status of operation
 485  */
 486 {
 487     KIRQL OldIrql;
 488
 489     TI_DbgPrint(DEBUG_ROUTER, ("Called.\n"));
 490
 491     /* Clear Forward Information Base */
 492     TcpipAcquireSpinLock(&FIBLock, &OldIrql);
 493     DestroyFIBEs();
 494     TcpipReleaseSpinLock(&FIBLock, OldIrql);
 495
 496     return STATUS_SUCCESS;
 497 }
 498
 499 /* EOF */