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