drivers/net/tcpip/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  * REVISIONS:
   8  *   CSH 01/08-2000 Created
   9  */
  10 #include <tcpip.h>
  11 #include <address.h>
  12 #include <router.h>
  13 #include <pool.h>
  14
  15
  16 LIST_ENTRY FIBListHead;
  17 KSPIN_LOCK FIBLock;
  18
  19
  20 VOID FreeFIB(
  21     PVOID Object)
  22 /*
  23  * FUNCTION: Frees an forward information base object
  24  * ARGUMENTS:
  25  *     Object = Pointer to an forward information base structure
  26  */
  27 {
  28     ExFreePool(Object);
  29 }
  30
  31
  32 VOID DestroyFIBE(
  33     PFIB_ENTRY FIBE)
  34 /*
  35  * FUNCTION: Destroys an forward information base entry
  36  * ARGUMENTS:
  37  *     FIBE = Pointer to FIB entry
  38  * NOTES:
  39  *     The forward information base lock must be held when called
  40  */
  41 {
  42     TI_DbgPrint(DEBUG_ROUTER, ("Called. FIBE (0x%X).\n", FIBE));
  43
  44     /* Unlink the FIB entry from the list */
  45     RemoveEntryList(&FIBE->ListEntry);
  46
  47     /* Dereference the referenced objects */
  48     DereferenceObject(FIBE->NetworkAddress);
  49     DereferenceObject(FIBE->Netmask);
  50     DereferenceObject(FIBE->Router);
  51     DereferenceObject(FIBE->NTE);
  52
  53 #ifdef DBG
  54     FIBE->RefCount--;
  55
  56     if (FIBE->RefCount != 0) {
  57         TI_DbgPrint(MIN_TRACE, ("FIB entry at (0x%X) has (%d) references (Should be 0).\n", FIBE, FIBE->RefCount));
  58     }
  59 #endif
  60
  61     /* And free the FIB entry */
  62     FreeFIB(FIBE);
  63 }
  64
  65
  66 VOID DestroyFIBEs(
  67     VOID)
  68 /*
  69  * FUNCTION: Destroys all forward information base entries
  70  * NOTES:
  71  *     The forward information base lock must be held when called
  72  */
  73 {
  74     PLIST_ENTRY CurrentEntry;
  75     PLIST_ENTRY NextEntry;
  76     PFIB_ENTRY Current;
  77
  78     /* Search the list and remove every FIB entry we find */
  79     CurrentEntry = FIBListHead.Flink;
  80     while (CurrentEntry != &FIBListHead) {
  81         NextEntry = CurrentEntry->Flink;
  82             Current = CONTAINING_RECORD(CurrentEntry, FIB_ENTRY, ListEntry);
  83         /* Destroy the FIB entry */
  84         DestroyFIBE(Current);
  85         CurrentEntry = NextEntry;
  86     }
  87 }
  88
  89
  90 UINT CommonPrefixLength(
  91     PIP_ADDRESS Address1,
  92     PIP_ADDRESS Address2)
  93 /*
  94  * FUNCTION: Computes the length of the longest prefix common to two addresses
  95  * ARGUMENTS:
  96  *     Address1 = Pointer to first address
  97  *     Address2 = Pointer to second address
  98  * NOTES:
  99  *     The two addresses must be of the same type
 100  * RETURNS:
 101  *     Length of longest common prefix
 102  */
 103 {
 104     PUCHAR Addr1, Addr2;
 105     UINT Size;
 106     UINT i, j;
 107     UINT Bitmask;
 108
 109     TI_DbgPrint(DEBUG_ROUTER, ("Called. Address1 (0x%X)  Address2 (0x%X).\n", Address1, Address2));
 110
 111     TI_DbgPrint(DEBUG_ROUTER, ("Address1 (%s)  Address2 (%s).\n",
 112         A2S(Address1), A2S(Address2)));
 113
 114     if (Address1->Type == IP_ADDRESS_V4)
 115         Size = sizeof(IPv4_RAW_ADDRESS);
 116     else
 117         Size = sizeof(IPv6_RAW_ADDRESS);
 118
 119     Addr1 = (PUCHAR)&Address1->Address;
 120     Addr2 = (PUCHAR)&Address2->Address;
 121
 122     /* Find first non-matching byte */
 123     for (i = 0; ; i++) {
 124         if (i == Size)
 125             return 8 * i; /* The two addresses are equal */
 126
 127         if (Addr1[i] != Addr2[i])
 128             break;
 129     }
 130
 131     /* Find first non-matching bit */
 132     Bitmask = 0x80;
 133     for (j = 0; ; j++) {
 134         if ((Addr1[i] & Bitmask) != (Addr2[i] & Bitmask))
 135             break;
 136         Bitmask >>= 1;
 137     }
 138
 139     return 8 * i + j;
 140 }
 141
 142
 143 BOOLEAN HasPrefix(
 144     PIP_ADDRESS Address,
 145     PIP_ADDRESS Prefix,
 146     UINT Length)
 147 /*
 148  * FUNCTION: Determines wether an address has an given prefix
 149  * ARGUMENTS:
 150  *     Address = Pointer to address to use
 151  *     Prefix  = Pointer to prefix to check for
 152  *     Length  = Length of prefix
 153  * RETURNS:
 154  *     TRUE if the address has the prefix, FALSE if not
 155  * NOTES:
 156  *     The two addresses must be of the same type
 157  */
 158 {
 159     PUCHAR pAddress = (PUCHAR)&Address->Address;
 160     PUCHAR pPrefix  = (PUCHAR)&Prefix->Address;
 161
 162     TI_DbgPrint(DEBUG_ROUTER, ("Called. Address (0x%X)  Prefix (0x%X)  Length (%d).\n", Address, Prefix, Length));
 163
 164     TI_DbgPrint(DEBUG_ROUTER, ("Address (%s)  Prefix (%s).\n",
 165         A2S(Address), A2S(Prefix)));
 166
 167     /* Check that initial integral bytes match */
 168     while (Length > 8) {
 169         if (*pAddress++ != *pPrefix++)
 170             return FALSE;
 171         Length -= 8;
 172     }
 173
 174     /* Check any remaining bits */
 175     if ((Length > 0) && ((*pAddress >> (8 - Length)) != (*pPrefix >> (8 - Length))))
 176         return FALSE;
 177
 178     return TRUE;
 179 }
 180
 181
 182 PNET_TABLE_ENTRY RouterFindBestNTE(
 183     PIP_INTERFACE Interface,
 184     PIP_ADDRESS Destination)
 185 /*
 186  * FUNCTION: Checks all on-link prefixes to find out if an address is on-link
 187  * ARGUMENTS:
 188  *     Interface   = Pointer to interface to use
 189  *     Destination = Pointer to destination address
 190  * NOTES:
 191  *     If found the NTE if referenced
 192  * RETURNS:
 193  *     Pointer to NTE if found, NULL if not
 194  */
 195 {
 196     KIRQL OldIrql;
 197     PLIST_ENTRY CurrentEntry;
 198     PNET_TABLE_ENTRY Current;
 199     UINT Length, BestLength  = 0;
 200     PNET_TABLE_ENTRY BestNTE = NULL;
 201
 202     TI_DbgPrint(DEBUG_ROUTER, ("Called. Interface (0x%X)  Destination (0x%X).\n", Interface, Destination));
 203
 204     TI_DbgPrint(DEBUG_ROUTER, ("Destination (%s).\n", A2S(Destination)));
 205
 206     KeAcquireSpinLock(&Interface->Lock, &OldIrql);
 207
 208     CurrentEntry = Interface->NTEListHead.Flink;
 209     while (CurrentEntry != &Interface->NTEListHead) {
 210             Current = CONTAINING_RECORD(CurrentEntry, NET_TABLE_ENTRY, IFListEntry);
 211
 212         Length = CommonPrefixLength(Destination, Current->Address);
 213         if (BestNTE) {
 214             if (Length > BestLength) {
 215                 /* This seems to be a better NTE */
 216                 DereferenceObject(BestNTE);
 217                 ReferenceObject(Current);
 218                 BestNTE    = Current;
 219                 BestLength = Length;
 220             }
 221         } else {
 222             /* First suitable NTE found, save it */
 223             ReferenceObject(Current);
 224             BestNTE    = Current;
 225             BestLength = Length;
 226         }
 227         CurrentEntry = CurrentEntry->Flink;
 228     }
 229
 230     KeReleaseSpinLock(&Interface->Lock, OldIrql);
 231
 232     return BestNTE;
 233 }
 234
 235
 236 PIP_INTERFACE RouterFindOnLinkInterface(
 237     PIP_ADDRESS Address,
 238     PNET_TABLE_ENTRY NTE)
 239 /*
 240  * FUNCTION: Checks all on-link prefixes to find out if an address is on-link
 241  * ARGUMENTS:
 242  *     Address = Pointer to address to check
 243  *     NTE     = Pointer to NTE to check (NULL = check all interfaces)
 244  * RETURNS:
 245  *     Pointer to interface if address is on-link, NULL if not
 246  */
 247 {
 248     PLIST_ENTRY CurrentEntry;
 249     PPREFIX_LIST_ENTRY Current;
 250
 251     TI_DbgPrint(DEBUG_ROUTER, ("Called. Address (0x%X)  NTE (0x%X).\n", Address, NTE));
 252
 253     TI_DbgPrint(DEBUG_ROUTER, ("Address (%s)  NTE (%s).\n",
 254         A2S(Address), A2S(NTE->Address)));
 255
 256     CurrentEntry = PrefixListHead.Flink;
 257     while (CurrentEntry != &PrefixListHead) {
 258             Current = CONTAINING_RECORD(CurrentEntry, PREFIX_LIST_ENTRY, ListEntry);
 259
 260         if (HasPrefix(Address, Current->Prefix, Current->PrefixLength) &&
 261             ((!NTE) || (NTE->Interface == Current->Interface)))
 262             return Current->Interface;
 263
 264         CurrentEntry = CurrentEntry->Flink;
 265     }
 266
 267     return NULL;
 268 }
 269
 270
 271 PFIB_ENTRY RouterAddRoute(
 272     PIP_ADDRESS NetworkAddress,
 273     PIP_ADDRESS Netmask,
 274     PNET_TABLE_ENTRY NTE,
 275     PNEIGHBOR_CACHE_ENTRY Router,
 276     UINT Metric)
 277 /*
 278  * FUNCTION: Adds a route to the Forward Information Base (FIB)
 279  * ARGUMENTS:
 280  *     NetworkAddress = Pointer to address of network
 281  *     Netmask        = Pointer to netmask of network
 282  *     NTE            = Pointer to NTE to use
 283  *     Router         = Pointer to NCE of router to use
 284  *     Metric         = Cost of this route
 285  * RETURNS:
 286  *     Pointer to FIB entry if the route was added, NULL if not
 287  * NOTES:
 288  *     The FIB entry references the NetworkAddress, Netmask, NTE and
 289  *     the NCE of the router. The caller is responsible for providing
 290  *     these references
 291  */
 292 {
 293     PFIB_ENTRY FIBE;
 294
 295     TI_DbgPrint(DEBUG_ROUTER, ("Called. NetworkAddress (0x%X)  Netmask (0x%X)  NTE (0x%X)  "
 296         "Router (0x%X)  Metric (%d).\n", NetworkAddress, Netmask, NTE, Router, Metric));
 297
 298     TI_DbgPrint(DEBUG_ROUTER, ("NetworkAddress (%s)  Netmask (%s)  NTE (%s)  Router (%s).\n",
 299         A2S(NetworkAddress), A2S(Netmask), A2S(NTE->Address), A2S(Router->Address)));
 300
 301     FIBE = ExAllocatePool(NonPagedPool, sizeof(FIB_ENTRY));
 302     if (!FIBE) {
 303         TI_DbgPrint(MIN_TRACE, ("Insufficient resources.\n"));
 304         return NULL;
 305     }
 306
 307    INIT_TAG(NTE, TAG('N','T','E',' '));
 308    INIT_TAG(Router, TAG('R','O','U','T'));
 309
 310     FIBE->Free           = FreeFIB;
 311     FIBE->NetworkAddress = NetworkAddress;
 312     FIBE->Netmask        = Netmask;
 313     FIBE->NTE            = NTE;
 314     FIBE->Router         = Router;
 315     FIBE->Metric         = Metric;
 316
 317     /* Add FIB to the forward information base */
 318     ExInterlockedInsertTailList(&FIBListHead, &FIBE->ListEntry, &FIBLock);
 319
 320     return FIBE;
 321 }
 322
 323
 324 PNEIGHBOR_CACHE_ENTRY RouterGetRoute(
 325     PIP_ADDRESS Destination,
 326     PNET_TABLE_ENTRY NTE)
 327 /*
 328  * FUNCTION: Finds a router to use to get to Destination
 329  * ARGUMENTS:
 330  *     Destination = Pointer to destination address (NULL means don't care)
 331  *     NTE         = Pointer to NTE describing net to send on
 332  *                   (NULL means don't care)
 333  * RETURNS:
 334  *     Pointer to NCE for router, NULL if none was found
 335  * NOTES:
 336  *     If found the NCE is referenced
 337  */
 338 {
 339     KIRQL OldIrql;
 340     PLIST_ENTRY CurrentEntry;
 341     PLIST_ENTRY NextEntry;
 342     PFIB_ENTRY Current;
 343     UCHAR State, BestState = 0;
 344     UINT Length, BestLength = 0;
 345     PNEIGHBOR_CACHE_ENTRY NCE, BestNCE = NULL;
 346
 347     TI_DbgPrint(DEBUG_ROUTER, ("Called. Destination (0x%X)  NTE (0x%X).\n", Destination, NTE));
 348
 349     TI_DbgPrint(DEBUG_ROUTER, ("Destination (%s)  NTE (%s).\n",
 350         A2S(Destination), A2S(NTE->Address)));
 351
 352     KeAcquireSpinLock(&FIBLock, &OldIrql);
 353
 354     CurrentEntry = FIBListHead.Flink;
 355     while (CurrentEntry != &FIBListHead) {
 356         NextEntry = CurrentEntry->Flink;
 357             Current = CONTAINING_RECORD(CurrentEntry, FIB_ENTRY, ListEntry);
 358
 359         NCE   = Current->Router;
 360         State = NCE->State;
 361
 362         if ((!NTE) || (NTE->Interface == NCE->Interface)) {
 363             if (Destination)
 364                 Length = CommonPrefixLength(Destination, NCE->Address);
 365             else
 366                 Length = 0;
 367
 368             if (BestNCE) {
 369                 if ((State  > BestState)  ||
 370                     ((State == BestState) &&
 371                     (Length > BestLength))) {
 372                     /* This seems to be a better router */
 373                     DereferenceObject(BestNCE);
 374                     ReferenceObject(NCE);
 375                     BestNCE    = NCE;
 376                     BestLength = Length;
 377                     BestState  = State;
 378                 }
 379             } else {
 380                 /* First suitable router found, save it */
 381                 ReferenceObject(NCE);
 382                 BestNCE    = NCE;
 383                 BestLength = Length;
 384                 BestState  = State;
 385             }
 386         }
 387         CurrentEntry = NextEntry;
 388     }
 389
 390     KeReleaseSpinLock(&FIBLock, OldIrql);
 391
 392     return BestNCE;
 393 }
 394
 395
 396 VOID RouterRemoveRoute(
 397     PFIB_ENTRY FIBE)
 398 /*
 399  * FUNCTION: Removes a route from the Forward Information Base (FIB)
 400  * ARGUMENTS:
 401  *     FIBE = Pointer to FIB entry describing route
 402  */
 403 {
 404     KIRQL OldIrql;
 405
 406     TI_DbgPrint(DEBUG_ROUTER, ("Called. FIBE (0x%X).\n", FIBE));
 407
 408     TI_DbgPrint(DEBUG_ROUTER, ("FIBE (%s).\n", A2S(FIBE->NetworkAddress)));
 409
 410     KeAcquireSpinLock(&FIBLock, &OldIrql);
 411     DestroyFIBE(FIBE);
 412     KeReleaseSpinLock(&FIBLock, OldIrql);
 413 }
 414
 415
 416 PFIB_ENTRY RouterCreateRouteIPv4(
 417     IPv4_RAW_ADDRESS NetworkAddress,
 418     IPv4_RAW_ADDRESS Netmask,
 419     IPv4_RAW_ADDRESS RouterAddress,
 420     PNET_TABLE_ENTRY NTE,
 421     UINT Metric)
 422 /*
 423  * FUNCTION: Creates a route with IPv4 addresses as parameters
 424  * ARGUMENTS:
 425  *     NetworkAddress = Address of network
 426  *     Netmask        = Netmask of network
 427  *     RouterAddress  = Address of router to use
 428  *     NTE            = Pointer to NTE to use
 429  *     Metric         = Cost of this route
 430  * RETURNS:
 431  *     Pointer to FIB entry if the route was created, NULL if not.
 432  *     The FIB entry references the NTE. The caller is responsible
 433  *     for providing this reference
 434  */
 435 {
 436     PIP_ADDRESS pNetworkAddress;
 437     PIP_ADDRESS pNetmask;
 438     PIP_ADDRESS pRouterAddress;
 439     PNEIGHBOR_CACHE_ENTRY NCE;
 440     PFIB_ENTRY FIBE;
 441
 442     pNetworkAddress = AddrBuildIPv4(NetworkAddress);
 443     if (!pNetworkAddress) {
 444         TI_DbgPrint(MIN_TRACE, ("Insufficient resources.\n"));
 445         return NULL;
 446     }
 447
 448     pNetmask = AddrBuildIPv4(Netmask);
 449     if (!pNetmask) {
 450         TI_DbgPrint(MIN_TRACE, ("Insufficient resources.\n"));
 451         DereferenceObject(pNetworkAddress);
 452         return NULL;
 453     }
 454
 455     pRouterAddress = AddrBuildIPv4(RouterAddress);
 456     if (!pRouterAddress) {
 457         TI_DbgPrint(MIN_TRACE, ("Insufficient resources.\n"));
 458         DereferenceObject(pNetworkAddress);
 459         DereferenceObject(pNetmask);
 460         return NULL;
 461     }
 462
 463     /* The NCE references RouterAddress. The NCE is referenced for us */
 464     NCE = NBAddNeighbor(NTE->Interface,
 465                         pRouterAddress,
 466                         NULL,
 467                         NTE->Interface->AddressLength,
 468                         NUD_PROBE);
 469     if (!NCE) {
 470         /* Not enough free resources */
 471         DereferenceObject(pNetworkAddress);
 472         DereferenceObject(pNetmask);
 473         DereferenceObject(pRouterAddress);
 474         return NULL;
 475     }
 476
 477     ReferenceObject(pNetworkAddress);
 478     ReferenceObject(pNetmask);
 479     FIBE = RouterAddRoute(pNetworkAddress, pNetmask, NTE, NCE, 1);
 480     if (!FIBE) {
 481         /* Not enough free resources */
 482         NBRemoveNeighbor(NCE);
 483         DereferenceObject(pNetworkAddress);
 484         DereferenceObject(pNetmask);
 485         DereferenceObject(pRouterAddress);
 486
 487         (pNetworkAddress->Free)(pNetworkAddress);
 488         (pNetmask->Free)(pNetmask);
 489         (pRouterAddress->Free)(pRouterAddress);
 490     }
 491
 492     return FIBE;
 493 }
 494
 495
 496 NTSTATUS RouterStartup(
 497     VOID)
 498 /*
 499  * FUNCTION: Initializes the routing subsystem
 500  * RETURNS:
 501  *     Status of operation
 502  */
 503 {
 504     TI_DbgPrint(DEBUG_ROUTER, ("Called.\n"));
 505
 506     /* Initialize the Forward Information Base */
 507     InitializeListHead(&FIBListHead);
 508     KeInitializeSpinLock(&FIBLock);
 509
 510 #if 0
 511     /* TEST: Create a test route */
 512     /* Network is 10.0.0.0  */
 513     /* Netmask is 255.0.0.0 */
 514     /* Router is 10.0.0.1   */
 515     RouterCreateRouteIPv4(0x0000000A, 0x000000FF, 0x0100000A, NTE?, 1);
 516 #endif
 517     return STATUS_SUCCESS;
 518 }
 519
 520
 521 NTSTATUS RouterShutdown(
 522     VOID)
 523 /*
 524  * FUNCTION: Shuts down the routing subsystem
 525  * RETURNS:
 526  *     Status of operation
 527  */
 528 {
 529     KIRQL OldIrql;
 530
 531     TI_DbgPrint(DEBUG_ROUTER, ("Called.\n"));
 532
 533     /* Clear Forward Information Base */
 534     KeAcquireSpinLock(&FIBLock, &OldIrql);
 535     DestroyFIBEs();
 536     KeReleaseSpinLock(&FIBLock, OldIrql);
 537
 538     return STATUS_SUCCESS;
 539 }
 540
 541 /* EOF */