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