ntoskrnl/fsrtl/largemcb.c

   1 /*
   2  * PROJECT:         ReactOS Kernel
   3  * LICENSE:         GPL v2 - See COPYING in the top level directory
   4  * FILE:            ntoskrnl/fsrtl/largemcb.c
   5  * PURPOSE:         Large Mapped Control Block (MCB) support for File System Drivers
   6  * PROGRAMMERS:     Aleksey Bragin <aleksey@reactos.org>
   7  *                  Jan Kratochvil <project-captive@jankratochvil.net>
   8  *                  Trevor Thompson
   9  */
  10
  11 /* INCLUDES ******************************************************************/
  12
  13 #include <ntoskrnl.h>
  14 #define NDEBUG
  15 #include <debug.h>
  16
  17 #define MIN(x,y) (((x)<(y))?(x):(y))
  18 #define MAX(x,y) (((x)>(y))?(x):(y))
  19
  20 /* GLOBALS *******************************************************************/
  21
  22 PAGED_LOOKASIDE_LIST FsRtlFirstMappingLookasideList;
  23 NPAGED_LOOKASIDE_LIST FsRtlFastMutexLookasideList;
  24
  25 /* We use only real 'mapping' runs; we do not store 'holes' to our GTree. */
  26 typedef struct _LARGE_MCB_MAPPING_ENTRY // run
  27 {
  28     LARGE_INTEGER RunStartVbn;
  29     LARGE_INTEGER RunEndVbn;   /* RunStartVbn+SectorCount; that means +1 after the last sector */
  30     LARGE_INTEGER StartingLbn; /* Lbn of 'RunStartVbn' */
  31 } LARGE_MCB_MAPPING_ENTRY, *PLARGE_MCB_MAPPING_ENTRY;
  32
  33 typedef struct _LARGE_MCB_MAPPING // mcb_priv
  34 {
  35     RTL_GENERIC_TABLE Table;
  36 } LARGE_MCB_MAPPING, *PLARGE_MCB_MAPPING;
  37
  38 typedef struct _BASE_MCB_INTERNAL {
  39     ULONG MaximumPairCount;
  40     ULONG PairCount;
  41     USHORT PoolType;
  42     USHORT Flags;
  43     PLARGE_MCB_MAPPING Mapping;
  44 } BASE_MCB_INTERNAL, *PBASE_MCB_INTERNAL;
  45
  46 /*
  47 static LARGE_MCB_MAPPING_ENTRY StaticRunBelow0 = {
  48     {{-1}}, // ignored
  49     {{0}},
  50     {{-1}}, // ignored
  51 };
  52 */
  53
  54 static PVOID NTAPI McbMappingAllocate(PRTL_GENERIC_TABLE Table, CLONG Bytes)
  55 {
  56     PVOID Result;
  57     PBASE_MCB Mcb = (PBASE_MCB)Table->TableContext;
  58     Result = ExAllocatePoolWithTag(Mcb->PoolType, Bytes, 'LMCB');
  59     DPRINT("McbMappingAllocate(%lu) => %p\n", Bytes, Result);
  60     return Result;
  61 }
  62
  63 static VOID NTAPI McbMappingFree(PRTL_GENERIC_TABLE Table, PVOID Buffer)
  64 {
  65     DPRINT("McbMappingFree(%p)\n", Buffer);
  66     ExFreePoolWithTag(Buffer, 'LMCB');
  67 }
  68
  69 static
  70 RTL_GENERIC_COMPARE_RESULTS
  71 NTAPI
  72 McbMappingCompare(PRTL_GENERIC_TABLE Table,
  73                   PVOID PtrA,
  74                   PVOID PtrB)
  75 {
  76     PLARGE_MCB_MAPPING_ENTRY A = PtrA, B = PtrB;
  77     RTL_GENERIC_COMPARE_RESULTS Res;
  78
  79     ASSERT(A);
  80     ASSERT(B);
  81
  82     if (A->RunStartVbn.QuadPart == B->RunStartVbn.QuadPart && A->RunEndVbn.QuadPart == B->RunEndVbn.QuadPart)
  83         Res = GenericEqual;
  84     else if (A->RunEndVbn.QuadPart <= B->RunStartVbn.QuadPart)
  85         Res = GenericLessThan;
  86     else if (A->RunEndVbn.QuadPart >= B->RunStartVbn.QuadPart)
  87         Res = GenericGreaterThan;
  88     else
  89     {
  90         ASSERT(FALSE);
  91         Res = GenericEqual;
  92     }
  93
  94     return Res;
  95 }
  96
  97 static RTL_GENERIC_COMPARE_RESULTS NTAPI McbMappingIntersectCompare(PRTL_GENERIC_TABLE Table, PVOID PtrA, PVOID PtrB)
  98 {
  99     PLARGE_MCB_MAPPING_ENTRY A = PtrA, B = PtrB;
 100     RTL_GENERIC_COMPARE_RESULTS Res;
 101
 102     if (A->RunStartVbn.QuadPart <= B->RunStartVbn.QuadPart && A->RunEndVbn.QuadPart > B->RunStartVbn.QuadPart)
 103         Res = GenericEqual;
 104     else if (A->RunStartVbn.QuadPart >= B->RunStartVbn.QuadPart && B->RunEndVbn.QuadPart > A->RunStartVbn.QuadPart)
 105         Res = GenericEqual;
 106     else if (A->RunStartVbn.QuadPart < B->RunStartVbn.QuadPart)
 107         Res = GenericLessThan;
 108     else if (A->RunStartVbn.QuadPart > B->RunStartVbn.QuadPart)
 109         Res = GenericGreaterThan;
 110     else
 111         Res = GenericEqual;
 112
 113     return Res;
 114 }
 115
 116
 117 /* PUBLIC FUNCTIONS **********************************************************/
 118
 119 /*
 120  * @implemented
 121  * @Mcb: #PLARGE_MCB initialized by FsRtlInitializeLargeMcb().
 122  * %NULL value is forbidden.
 123  * @Vbn: Starting virtual block number of the wished range.
 124  * @Lbn: Starting logical block number of the wished range.
 125  * @SectorCount: Length of the wished range.
 126  * Value less or equal to %0 is forbidden; FIXME: Is the reject of %0 W32 compliant?
 127  *
 128  * Adds the specified range @Vbn ... @Vbn+@SectorCount-1 to @Mcb.
 129  * Any mappings previously in this range are deleted first.
 130  *
 131  * Returns: %TRUE if successful.
 132  */
 133 BOOLEAN
 134 NTAPI
 135 FsRtlAddBaseMcbEntry(IN PBASE_MCB OpaqueMcb,
 136                      IN LONGLONG Vbn,
 137                      IN LONGLONG Lbn,
 138                      IN LONGLONG SectorCount)
 139 {
 140     BOOLEAN Result = TRUE;
 141     BOOLEAN IntResult;
 142     PBASE_MCB_INTERNAL Mcb = (PBASE_MCB_INTERNAL)OpaqueMcb;
 143     LARGE_MCB_MAPPING_ENTRY Node, NeedleRun;
 144     PLARGE_MCB_MAPPING_ENTRY LowerRun, HigherRun;
 145     BOOLEAN NewElement;
 146     LONGLONG IntLbn;
 147
 148     DPRINT("FsRtlAddBaseMcbEntry(%p, %I64d, %I64d, %I64d)\n", OpaqueMcb, Vbn, Lbn, SectorCount);
 149
 150     if (Vbn < 0)
 151     {
 152         Result = FALSE;
 153         goto quit;
 154     }
 155
 156     if (SectorCount <= 0)
 157     {
 158         Result = FALSE;
 159         goto quit;
 160     }
 161
 162     IntResult = FsRtlLookupBaseMcbEntry(OpaqueMcb, Vbn, &IntLbn, NULL, NULL, NULL, NULL);
 163     if (IntResult)
 164     {
 165         if (IntLbn != -1 && IntLbn != Lbn)
 166         {
 167             Result = FALSE;
 168             goto quit;
 169         }
 170     }
 171
 172     /* clean any possible previous entries in our range */
 173     FsRtlRemoveBaseMcbEntry(OpaqueMcb, Vbn, SectorCount);
 174
 175     // We need to map [Vbn, Vbn+SectorCount) to [Lbn, Lbn+SectorCount),
 176     // taking in account the fact that we need to merge these runs if
 177     // they are adjacent or overlap, but fail if new run fully fits into another run
 178
 179     /* initially we think we will be inserted as a separate run */
 180     Node.RunStartVbn.QuadPart = Vbn;
 181     Node.RunEndVbn.QuadPart = Vbn + SectorCount;
 182     Node.StartingLbn.QuadPart = Lbn;
 183
 184     /* optionally merge with lower run */
 185     NeedleRun.RunStartVbn.QuadPart = Node.RunStartVbn.QuadPart - 1;
 186     NeedleRun.RunEndVbn.QuadPart = NeedleRun.RunStartVbn.QuadPart + 1;
 187     NeedleRun.StartingLbn.QuadPart = ~0ULL;
 188     Mcb->Mapping->Table.CompareRoutine = McbMappingIntersectCompare;
 189     if ((LowerRun = RtlLookupElementGenericTable(&Mcb->Mapping->Table, &NeedleRun)) &&
 190         (LowerRun->StartingLbn.QuadPart + (LowerRun->RunEndVbn.QuadPart - LowerRun->RunStartVbn.QuadPart) == Node.StartingLbn.QuadPart))
 191     {
 192         ASSERT(LowerRun->RunEndVbn.QuadPart == Node.RunStartVbn.QuadPart);
 193         Node.RunStartVbn.QuadPart = LowerRun->RunStartVbn.QuadPart;
 194         Node.StartingLbn.QuadPart = LowerRun->StartingLbn.QuadPart;
 195         Mcb->Mapping->Table.CompareRoutine = McbMappingCompare;
 196         RtlDeleteElementGenericTable(&Mcb->Mapping->Table, LowerRun);
 197         --Mcb->PairCount;
 198         DPRINT("Intersecting lower run found (%I64d,%I64d) Lbn: %I64d\n", LowerRun->RunStartVbn.QuadPart, LowerRun->RunEndVbn.QuadPart, LowerRun->StartingLbn.QuadPart);
 199     }
 200
 201     /* optionally merge with higher run */
 202     NeedleRun.RunStartVbn.QuadPart = Node.RunEndVbn.QuadPart;
 203     NeedleRun.RunEndVbn.QuadPart = NeedleRun.RunStartVbn.QuadPart + 1;
 204     Mcb->Mapping->Table.CompareRoutine = McbMappingIntersectCompare;
 205     if ((HigherRun = RtlLookupElementGenericTable(&Mcb->Mapping->Table, &NeedleRun)) &&
 206         (Node.StartingLbn.QuadPart <= HigherRun->StartingLbn.QuadPart))
 207     {
 208         ASSERT(HigherRun->RunStartVbn.QuadPart == Node.RunEndVbn.QuadPart);
 209         Node.RunEndVbn.QuadPart = HigherRun->RunEndVbn.QuadPart;
 210         Mcb->Mapping->Table.CompareRoutine = McbMappingCompare;
 211         RtlDeleteElementGenericTable(&Mcb->Mapping->Table, HigherRun);
 212         --Mcb->PairCount;
 213         DPRINT("Intersecting higher run found (%I64d,%I64d) Lbn: %I64d\n", HigherRun->RunStartVbn.QuadPart, HigherRun->RunEndVbn.QuadPart, HigherRun->StartingLbn.QuadPart);
 214     }
 215     Mcb->Mapping->Table.CompareRoutine = McbMappingCompare;
 216
 217     /* finally insert the resulting run */
 218     RtlInsertElementGenericTable(&Mcb->Mapping->Table, &Node, sizeof(Node), &NewElement);
 219     ++Mcb->PairCount;
 220     ASSERT(NewElement);
 221
 222     // NB: Two consecutive runs can only be merged, if actual LBNs also match!
 223
 224     /* 1.
 225             Existing->RunStartVbn
 226             |
 227             |///////|
 228                 |/////////////|
 229                 |
 230                 Node->RunStartVbn
 231
 232         2.
 233             Existing->RunStartVbn
 234             |
 235             |///////|
 236         |//////|
 237         |
 238         Node->RunStartVbn
 239
 240         3.
 241             Existing->RunStartVbn
 242             |
 243             |///////|
 244                 |///|
 245                 |
 246                 Node->RunStartVbn
 247
 248         4.
 249             Existing->RunStartVbn
 250             |
 251             |///////|
 252         |///////////////|
 253         |
 254         Node->RunStartVbn
 255
 256
 257     Situation with holes:
 258     1. Holes at both ends
 259     2. Hole at the right, new run merged with the previous run
 260     3. Hole at the right, new run is not merged with the previous run
 261     4. Hole at the left, new run merged with the next run
 262     5. Hole at the left, new run is not merged with the next run
 263     6. No holes, exact fit to merge with both previous and next runs
 264     7. No holes, merges only with the next run
 265     8. No holes, merges only with the previous run
 266     9. No holes, does not merge with next or prev runs
 267
 268
 269     Overwriting existing mapping is not possible and results in FALSE being returned
 270     */
 271
 272 quit:
 273     DPRINT("FsRtlAddBaseMcbEntry(%p, %I64d, %I64d, %I64d) = %d\n", Mcb, Vbn, Lbn, SectorCount, Result);
 274     return Result;
 275 }
 276
 277 /*
 278  * @implemented
 279  */
 280 BOOLEAN
 281 NTAPI
 282 FsRtlAddLargeMcbEntry(IN PLARGE_MCB Mcb,
 283                       IN LONGLONG Vbn,
 284                       IN LONGLONG Lbn,
 285                       IN LONGLONG SectorCount)
 286 {
 287     BOOLEAN Result;
 288
 289     DPRINT("FsRtlAddLargeMcbEntry(%p, %I64d, %I64d, %I64d)\n", Mcb, Vbn, Lbn, SectorCount);
 290
 291     KeAcquireGuardedMutex(Mcb->GuardedMutex);
 292     Result = FsRtlAddBaseMcbEntry(&(Mcb->BaseMcb),
 293                                   Vbn,
 294                                   Lbn,
 295                                   SectorCount);
 296     KeReleaseGuardedMutex(Mcb->GuardedMutex);
 297
 298     DPRINT("FsRtlAddLargeMcbEntry(%p, %I64d, %I64d, %I64d) = %d\n", Mcb, Vbn, Lbn, SectorCount, Result);
 299
 300     return Result;
 301 }
 302
 303 /*
 304  * @implemented
 305  * @Mcb: #PLARGE_MCB initialized by FsRtlInitializeLargeMcb().
 306  * %NULL value is forbidden.
 307  * @RunIndex: Requested range index to retrieve.
 308  * @Vbn: Returns the starting virtual block number of the wished range.
 309  * %NULL pointer is forbidden.
 310  * @Lbn: Returns the starting logical block number of the wished range (or -1 if it is a hole).
 311  * %NULL pointer is forbidden.
 312  * @SectorCount: Returns the length of the wished range.
 313  * %NULL pointer is forbidden.
 314  * Value less or equal to %0 is forbidden; FIXME: Is the reject of %0 W32 compliant?
 315  *
 316  * Retrieves the parameters of the specified run with index @RunIndex.
 317  *
 318  * Mapping %0 always starts at virtual block %0, either as 'hole' or as 'real' mapping.
 319  * libcaptive does not store 'hole' information to its #GTree.
 320  * Last run is always a 'real' run. 'hole' runs appear as mapping to constant @Lbn value %-1.
 321  *
 322  * Returns: %TRUE if successful.
 323  */
 324 BOOLEAN
 325 NTAPI
 326 FsRtlGetNextBaseMcbEntry(IN PBASE_MCB OpaqueMcb,
 327     IN ULONG RunIndex,
 328     OUT PLONGLONG Vbn,
 329     OUT PLONGLONG Lbn,
 330     OUT PLONGLONG SectorCount)
 331 {
 332     BOOLEAN Result = FALSE;
 333     PBASE_MCB_INTERNAL Mcb = (PBASE_MCB_INTERNAL)OpaqueMcb;
 334     PLARGE_MCB_MAPPING_ENTRY Run = NULL;
 335     ULONG CurrentIndex = 0;
 336     ULONGLONG LastVbn = 0;
 337     ULONGLONG LastSectorCount = 0;
 338
 339     // Traverse the tree
 340     for (Run = (PLARGE_MCB_MAPPING_ENTRY)RtlEnumerateGenericTable(&Mcb->Mapping->Table, TRUE);
 341     Run;
 342         Run = (PLARGE_MCB_MAPPING_ENTRY)RtlEnumerateGenericTable(&Mcb->Mapping->Table, FALSE))
 343     {
 344         // is the current index a hole?
 345         if (Run->RunStartVbn.QuadPart > (LastVbn + LastSectorCount))
 346         {
 347             // Is this the index we're looking for?
 348             if (RunIndex == CurrentIndex)
 349             {
 350                 *Vbn = LastVbn + LastSectorCount;
 351                 *Lbn = -1;
 352                 *SectorCount = Run->RunStartVbn.QuadPart - *Vbn;
 353
 354                 Result = TRUE;
 355                 goto quit;
 356             }
 357
 358             CurrentIndex++;
 359         }
 360
 361         if (RunIndex == CurrentIndex)
 362         {
 363             *Vbn = Run->RunStartVbn.QuadPart;
 364             *Lbn = Run->StartingLbn.QuadPart;
 365             *SectorCount = Run->RunEndVbn.QuadPart - Run->RunStartVbn.QuadPart;
 366
 367             Result = TRUE;
 368             goto quit;
 369         }
 370
 371         CurrentIndex++;
 372         LastVbn = Run->RunStartVbn.QuadPart;
 373         LastSectorCount = Run->RunEndVbn.QuadPart - Run->RunStartVbn.QuadPart;
 374     }
 375
 376     // these values are meaningless when returning false (but setting them can be helpful for debugging purposes)
 377     *Vbn = 0xdeadbeef;
 378     *Lbn = 0xdeadbeef;
 379     *SectorCount = 0xdeadbeef;
 380
 381 quit:
 382     DPRINT("FsRtlGetNextBaseMcbEntry(%p, %d, %p, %p, %p) = %d (%I64d, %I64d, %I64d)\n", Mcb, RunIndex, Vbn, Lbn, SectorCount, Result, *Vbn, *Lbn, *SectorCount);
 383     return Result;
 384 }
 385
 386 /*
 387  * @implemented
 388  */
 389 BOOLEAN
 390 NTAPI
 391 FsRtlGetNextLargeMcbEntry(IN PLARGE_MCB Mcb,
 392                           IN ULONG RunIndex,
 393                           OUT PLONGLONG Vbn,
 394                           OUT PLONGLONG Lbn,
 395                           OUT PLONGLONG SectorCount)
 396 {
 397     BOOLEAN Result;
 398
 399     DPRINT("FsRtlGetNextLargeMcbEntry(%p, %d, %p, %p, %p)\n", Mcb, RunIndex, Vbn, Lbn, SectorCount);
 400
 401     KeAcquireGuardedMutex(Mcb->GuardedMutex);
 402     Result = FsRtlGetNextBaseMcbEntry(&(Mcb->BaseMcb),
 403                                       RunIndex,
 404                                       Vbn,
 405                                       Lbn,
 406                                       SectorCount);
 407     KeReleaseGuardedMutex(Mcb->GuardedMutex);
 408
 409     DPRINT("FsRtlGetNextLargeMcbEntry(%p, %d, %p, %p, %p) = %d (%I64d, %I64d, %I64d)\n", Mcb, RunIndex, Vbn, Lbn, SectorCount, Result, *Vbn, *Lbn, *SectorCount);
 410
 411     return Result;
 412 }
 413
 414 /*
 415  * @implemented
 416  */
 417 VOID
 418 NTAPI
 419 FsRtlInitializeBaseMcb(IN PBASE_MCB OpaqueMcb,
 420                        IN POOL_TYPE PoolType)
 421 {
 422     PBASE_MCB_INTERNAL Mcb = (PBASE_MCB_INTERNAL)OpaqueMcb;
 423
 424     if (PoolType == PagedPool)
 425     {
 426         Mcb->Mapping = ExAllocateFromPagedLookasideList(&FsRtlFirstMappingLookasideList);
 427     }
 428     else
 429     {
 430         Mcb->Mapping = ExAllocatePoolWithTag(PoolType | POOL_RAISE_IF_ALLOCATION_FAILURE,
 431                                              sizeof(LARGE_MCB_MAPPING),
 432                                              'FSBC');
 433     }
 434
 435     Mcb->PoolType = PoolType;
 436     Mcb->PairCount = 0;
 437     Mcb->MaximumPairCount = MAXIMUM_PAIR_COUNT;
 438     RtlInitializeGenericTable(&Mcb->Mapping->Table,
 439                               McbMappingCompare,
 440                               McbMappingAllocate,
 441                               McbMappingFree,
 442                               Mcb);
 443 }
 444
 445 /*
 446  * @implemented
 447  */
 448 VOID
 449 NTAPI
 450 FsRtlInitializeLargeMcb(IN PLARGE_MCB Mcb,
 451                         IN POOL_TYPE PoolType)
 452 {
 453     DPRINT("FsRtlInitializeLargeMcb(%p, %d)\n", Mcb, PoolType);
 454
 455     Mcb->GuardedMutex = ExAllocateFromNPagedLookasideList(&FsRtlFastMutexLookasideList);
 456
 457     KeInitializeGuardedMutex(Mcb->GuardedMutex);
 458
 459     _SEH2_TRY
 460     {
 461         FsRtlInitializeBaseMcb(&(Mcb->BaseMcb), PoolType);
 462     }
 463     _SEH2_EXCEPT(EXCEPTION_EXECUTE_HANDLER)
 464     {
 465         ExFreeToNPagedLookasideList(&FsRtlFastMutexLookasideList,
 466                                     Mcb->GuardedMutex);
 467         Mcb->GuardedMutex = NULL;
 468     }
 469     _SEH2_END;
 470 }
 471
 472 /*
 473  * @implemented
 474  */
 475 INIT_FUNCTION
 476 VOID
 477 NTAPI
 478 FsRtlInitializeLargeMcbs(VOID)
 479 {
 480     /* Initialize the list for the MCB */
 481     ExInitializePagedLookasideList(&FsRtlFirstMappingLookasideList,
 482                                    NULL,
 483                                    NULL,
 484                                    POOL_RAISE_IF_ALLOCATION_FAILURE,
 485                                    sizeof(LARGE_MCB_MAPPING),
 486                                    IFS_POOL_TAG,
 487                                    0); /* FIXME: Should be 4 */
 488
 489     /* Initialize the list for the guarded mutex */
 490     ExInitializeNPagedLookasideList(&FsRtlFastMutexLookasideList,
 491                                     NULL,
 492                                     NULL,
 493                                     POOL_RAISE_IF_ALLOCATION_FAILURE,
 494                                     sizeof(KGUARDED_MUTEX),
 495                                     IFS_POOL_TAG,
 496                                     0); /* FIXME: Should be 32 */
 497 }
 498
 499 /*
 500  * @implemented
 501  */
 502 BOOLEAN
 503 NTAPI
 504 FsRtlLookupBaseMcbEntry(IN PBASE_MCB OpaqueMcb,
 505     IN LONGLONG Vbn,
 506     OUT PLONGLONG Lbn OPTIONAL,
 507     OUT PLONGLONG SectorCountFromLbn OPTIONAL,
 508     OUT PLONGLONG StartingLbn OPTIONAL,
 509     OUT PLONGLONG SectorCountFromStartingLbn OPTIONAL,
 510     OUT PULONG Index OPTIONAL)
 511 {
 512     BOOLEAN Result = FALSE;
 513     ULONG i;
 514     LONGLONG LastVbn = 0, LastLbn = 0, Count = 0;   // the last values we've found during traversal
 515
 516     DPRINT("FsRtlLookupBaseMcbEntry(%p, %I64d, %p, %p, %p, %p, %p)\n", OpaqueMcb, Vbn, Lbn, SectorCountFromLbn, StartingLbn, SectorCountFromStartingLbn, Index);
 517
 518     for (i = 0; FsRtlGetNextBaseMcbEntry(OpaqueMcb, i, &LastVbn, &LastLbn, &Count); i++)
 519     {
 520         // have we reached the target mapping?
 521         if (Vbn < LastVbn + Count)
 522         {
 523             if (Lbn)
 524             {
 525                 if (LastLbn == -1)
 526                     *Lbn = -1;
 527                 else
 528                     *Lbn = LastLbn + (Vbn - LastVbn);
 529             }
 530
 531             if (SectorCountFromLbn)
 532                 *SectorCountFromLbn = LastVbn + Count - Vbn;
 533             if (StartingLbn)
 534                 *StartingLbn = LastLbn;
 535             if (SectorCountFromStartingLbn)
 536                 *SectorCountFromStartingLbn = LastVbn + Count - LastVbn;
 537             if (Index)
 538                 *Index = i;
 539
 540             Result = TRUE;
 541             goto quit;
 542         }
 543     }
 544
 545     if (Lbn)
 546         *Lbn = -1;
 547     if (StartingLbn)
 548         *StartingLbn = -1;
 549
 550 quit:
 551     DPRINT("FsRtlLookupBaseMcbEntry(%p, %I64d, %p, %p, %p, %p, %p) = %d (%I64d, %I64d, %I64d, %I64d, %d)\n",
 552            OpaqueMcb, Vbn, Lbn, SectorCountFromLbn, StartingLbn, SectorCountFromStartingLbn, Index, Result,
 553            (Lbn ? *Lbn : (ULONGLONG)-1), (SectorCountFromLbn ? *SectorCountFromLbn : (ULONGLONG)-1), (StartingLbn ? *StartingLbn : (ULONGLONG)-1),
 554            (SectorCountFromStartingLbn ? *SectorCountFromStartingLbn : (ULONGLONG)-1), (Index ? *Index : (ULONG)-1));
 555
 556     return Result;
 557 }
 558
 559 /*
 560  * @implemented
 561  */
 562 BOOLEAN
 563 NTAPI
 564 FsRtlLookupLargeMcbEntry(IN PLARGE_MCB Mcb,
 565                          IN LONGLONG Vbn,
 566                          OUT PLONGLONG Lbn OPTIONAL,
 567                          OUT PLONGLONG SectorCountFromLbn OPTIONAL,
 568                          OUT PLONGLONG StartingLbn OPTIONAL,
 569                          OUT PLONGLONG SectorCountFromStartingLbn OPTIONAL,
 570                          OUT PULONG Index OPTIONAL)
 571 {
 572     BOOLEAN Result;
 573
 574     DPRINT("FsRtlLookupLargeMcbEntry(%p, %I64d, %p, %p, %p, %p, %p)\n", Mcb, Vbn, Lbn, SectorCountFromLbn, StartingLbn, SectorCountFromStartingLbn, Index);
 575
 576     KeAcquireGuardedMutex(Mcb->GuardedMutex);
 577     Result = FsRtlLookupBaseMcbEntry(&(Mcb->BaseMcb),
 578                                      Vbn,
 579                                      Lbn,
 580                                      SectorCountFromLbn,
 581                                      StartingLbn,
 582                                      SectorCountFromStartingLbn,
 583                                      Index);
 584     KeReleaseGuardedMutex(Mcb->GuardedMutex);
 585
 586     DPRINT("FsRtlLookupLargeMcbEntry(%p, %I64d, %p, %p, %p, %p, %p) = %d (%I64d, %I64d, %I64d, %I64d, %d)\n",
 587            Mcb, Vbn, Lbn, SectorCountFromLbn, StartingLbn, SectorCountFromStartingLbn, Index, Result,
 588            (Lbn ? *Lbn : (ULONGLONG)-1), (SectorCountFromLbn ? *SectorCountFromLbn : (ULONGLONG)-1), (StartingLbn ? *StartingLbn : (ULONGLONG)-1),
 589            (SectorCountFromStartingLbn ? *SectorCountFromStartingLbn : (ULONGLONG)-1), (Index ? *Index : (ULONG)-1));
 590
 591     return Result;
 592 }
 593
 594 static BOOLEAN
 595 NTAPI
 596 FsRtlLookupLastLargeMcbEntryAndIndex_internal(IN PBASE_MCB_INTERNAL Mcb,
 597                                               OUT PLONGLONG Vbn,
 598                                               OUT PLONGLONG Lbn,
 599                                               OUT PULONG Index OPTIONAL)
 600 {
 601     ULONG RunIndex = 0;
 602     PLARGE_MCB_MAPPING_ENTRY Run, RunFound = NULL;
 603     LONGLONG LastVbn = 0;
 604
 605     for (Run = (PLARGE_MCB_MAPPING_ENTRY)RtlEnumerateGenericTable(&Mcb->Mapping->Table, TRUE);
 606         Run;
 607         Run = (PLARGE_MCB_MAPPING_ENTRY)RtlEnumerateGenericTable(&Mcb->Mapping->Table, FALSE))
 608     {
 609         /* Take care when we must emulate missing 'hole' runs. */
 610         if (Run->RunStartVbn.QuadPart > LastVbn)
 611         {
 612             RunIndex++;
 613         }
 614         LastVbn = Run->RunEndVbn.QuadPart;
 615         RunIndex++;
 616         RunFound = Run;
 617     }
 618
 619     if (!RunFound)
 620     {
 621         return FALSE;
 622     }
 623
 624     if (Vbn)
 625     {
 626         *Vbn = RunFound->RunEndVbn.QuadPart - 1;
 627     }
 628     if (Lbn)
 629     {
 630         if (1)
 631         {
 632             *Lbn = RunFound->StartingLbn.QuadPart + (RunFound->RunEndVbn.QuadPart - RunFound->RunStartVbn.QuadPart) - 1;
 633         }
 634         else
 635         {
 636             *Lbn = ~0ULL;
 637         }
 638     }
 639     if (Index)
 640     {
 641         *Index = RunIndex - 1;
 642     }
 643
 644     return TRUE;
 645 }
 646
 647
 648 /*
 649  * @implemented
 650  */
 651 BOOLEAN
 652 NTAPI
 653 FsRtlLookupLastBaseMcbEntryAndIndex(IN PBASE_MCB OpaqueMcb,
 654                                     IN OUT PLONGLONG LargeVbn,
 655                                     IN OUT PLONGLONG LargeLbn,
 656                                     IN OUT PULONG Index)
 657 {
 658     BOOLEAN Result;
 659     PBASE_MCB_INTERNAL Mcb = (PBASE_MCB_INTERNAL)OpaqueMcb;
 660
 661     DPRINT("FsRtlLookupLastBaseMcbEntryAndIndex(%p, %p, %p, %p)\n", OpaqueMcb, LargeVbn, LargeLbn, Index);
 662
 663     Result = FsRtlLookupLastLargeMcbEntryAndIndex_internal(Mcb, LargeVbn, LargeLbn, Index);
 664
 665     DPRINT("FsRtlLookupLastBaseMcbEntryAndIndex(%p, %p, %p, %p) = %d (%I64d, %I64d, %d)\n", OpaqueMcb, LargeVbn, LargeLbn, Index, Result, *LargeVbn, *LargeLbn, *Index);
 666
 667     return Result;
 668 }
 669
 670 /*
 671  * @implemented
 672  */
 673 BOOLEAN
 674 NTAPI
 675 FsRtlLookupLastLargeMcbEntryAndIndex(IN PLARGE_MCB OpaqueMcb,
 676                                      OUT PLONGLONG LargeVbn,
 677                                      OUT PLONGLONG LargeLbn,
 678                                      OUT PULONG Index)
 679 {
 680     BOOLEAN Result;
 681
 682     DPRINT("FsRtlLookupLastLargeMcbEntryAndIndex(%p, %p, %p, %p)\n", OpaqueMcb, LargeVbn, LargeLbn, Index);
 683
 684     KeAcquireGuardedMutex(OpaqueMcb->GuardedMutex);
 685     Result = FsRtlLookupLastBaseMcbEntryAndIndex(&(OpaqueMcb->BaseMcb),
 686                                                  LargeVbn,
 687                                                  LargeLbn,
 688                                                  Index);
 689     KeReleaseGuardedMutex(OpaqueMcb->GuardedMutex);
 690
 691     DPRINT("FsRtlLookupLastLargeMcbEntryAndIndex(%p, %p, %p, %p) = %d (%I64d, %I64d, %d)\n", OpaqueMcb, LargeVbn, LargeLbn, Index, Result, *LargeVbn, *LargeLbn, *Index);
 692
 693     return Result;
 694 }
 695
 696 /*
 697  * @unimplemented
 698  */
 699 BOOLEAN
 700 NTAPI
 701 FsRtlLookupLastBaseMcbEntry(IN PBASE_MCB OpaqueMcb,
 702                             OUT PLONGLONG Vbn,
 703                             OUT PLONGLONG Lbn)
 704 {
 705     BOOLEAN Result;
 706     PBASE_MCB_INTERNAL Mcb = (PBASE_MCB_INTERNAL)OpaqueMcb;
 707
 708     DPRINT("FsRtlLookupLastBaseMcbEntry(%p, %p, %p)\n", OpaqueMcb, Vbn, Lbn);
 709
 710     Result = FsRtlLookupLastLargeMcbEntryAndIndex_internal(Mcb, Vbn, Lbn, NULL); /* Index */
 711
 712     DPRINT("FsRtlLookupLastBaseMcbEntry(%p, %p, %p) = %d (%I64d, %I64d)\n", Mcb, Vbn, Lbn, Result, *Vbn, *Lbn);
 713
 714     return Result;
 715 }
 716
 717 /*
 718  * @implemented
 719  */
 720 BOOLEAN
 721 NTAPI
 722 FsRtlLookupLastLargeMcbEntry(IN PLARGE_MCB Mcb,
 723                              OUT PLONGLONG Vbn,
 724                              OUT PLONGLONG Lbn)
 725 {
 726     BOOLEAN Result;
 727
 728     DPRINT("FsRtlLookupLastLargeMcbEntry(%p, %p, %p)\n", Mcb, Vbn, Lbn);
 729
 730     KeAcquireGuardedMutex(Mcb->GuardedMutex);
 731     Result = FsRtlLookupLastBaseMcbEntry(&(Mcb->BaseMcb),
 732                                          Vbn,
 733                                          Lbn);
 734     KeReleaseGuardedMutex(Mcb->GuardedMutex);
 735
 736     DPRINT("FsRtlLookupLastLargeMcbEntry(%p, %p, %p) = %d (%I64d, %I64d)\n", Mcb, Vbn, Lbn, Result, *Vbn, *Lbn);
 737
 738     return Result;
 739 }
 740
 741 /*
 742  * @implemented
 743  */
 744 ULONG
 745 NTAPI
 746 FsRtlNumberOfRunsInBaseMcb(IN PBASE_MCB OpaqueMcb)
 747 {
 748     ULONG NumberOfRuns = 0;
 749     LONGLONG Vbn, Lbn, Count;
 750     int i;
 751
 752     DPRINT("FsRtlNumberOfRunsInBaseMcb(%p)\n", OpaqueMcb);
 753
 754     // Count how many Mcb entries there are
 755     for (i = 0; FsRtlGetNextBaseMcbEntry(OpaqueMcb, i, &Vbn, &Lbn, &Count); i++)
 756     {
 757         NumberOfRuns++;
 758     }
 759
 760     DPRINT("FsRtlNumberOfRunsInBaseMcb(%p) = %d\n", OpaqueMcb, NumberOfRuns);
 761     return NumberOfRuns;
 762 }
 763
 764 /*
 765  * @implemented
 766  */
 767 ULONG
 768 NTAPI
 769 FsRtlNumberOfRunsInLargeMcb(IN PLARGE_MCB Mcb)
 770 {
 771     ULONG NumberOfRuns;
 772
 773     DPRINT("FsRtlNumberOfRunsInLargeMcb(%p)\n", Mcb);
 774
 775     /* Read the number of runs while holding the MCB lock */
 776     KeAcquireGuardedMutex(Mcb->GuardedMutex);
 777     NumberOfRuns = FsRtlNumberOfRunsInBaseMcb(&(Mcb->BaseMcb));
 778     KeReleaseGuardedMutex(Mcb->GuardedMutex);
 779
 780     DPRINT("FsRtlNumberOfRunsInLargeMcb(%p) = %d\n", Mcb, NumberOfRuns);
 781
 782     /* Return the count */
 783     return NumberOfRuns;
 784 }
 785
 786 /*
 787  * @implemented
 788  * @Mcb: #PLARGE_MCB initialized by FsRtlInitializeLargeMcb().
 789  * %NULL value is forbidden.
 790  * @Vbn: Starting virtual block number to specify the range to delete.
 791  * @SectorCount: Length of the range to delete.
 792  * Value less or equal to %0 is forbidden; FIXME: Is the reject of %0 W32 compliant?
 793  *
 794  * Deletes any possible @Mcb mappings in the given range @Vbn ... @Vbn+@SectorCount-1.
 795  * This call has no problems if no mappings exist there yet.
 796  */
 797 BOOLEAN
 798 NTAPI
 799 FsRtlRemoveBaseMcbEntry(IN PBASE_MCB OpaqueMcb,
 800                         IN LONGLONG Vbn,
 801                         IN LONGLONG SectorCount)
 802 {
 803     PBASE_MCB_INTERNAL Mcb = (PBASE_MCB_INTERNAL)OpaqueMcb;
 804     LARGE_MCB_MAPPING_ENTRY NeedleRun;
 805     PLARGE_MCB_MAPPING_ENTRY HaystackRun;
 806     BOOLEAN Result = TRUE;
 807
 808     DPRINT("FsRtlRemoveBaseMcbEntry(%p, %I64d, %I64d)\n", OpaqueMcb, Vbn, SectorCount);
 809
 810     if (Vbn < 0 || SectorCount <= 0)
 811     {
 812         Result = FALSE;
 813         goto quit;
 814     }
 815
 816     if (Vbn + SectorCount <= Vbn)
 817     {
 818         Result = FALSE;
 819         goto quit;
 820     }
 821
 822     NeedleRun.RunStartVbn.QuadPart = Vbn;
 823     NeedleRun.RunEndVbn.QuadPart = Vbn + SectorCount;
 824     NeedleRun.StartingLbn.QuadPart = ~0ULL;
 825
 826     /* adjust/destroy all intersecting ranges */
 827     Mcb->Mapping->Table.CompareRoutine = McbMappingIntersectCompare;
 828     while ((HaystackRun = RtlLookupElementGenericTable(&Mcb->Mapping->Table, &NeedleRun)))
 829     {
 830         if (HaystackRun->RunStartVbn.QuadPart < NeedleRun.RunStartVbn.QuadPart)
 831         {
 832             ASSERT(HaystackRun->RunEndVbn.QuadPart > NeedleRun.RunStartVbn.QuadPart);
 833             HaystackRun->RunEndVbn.QuadPart = NeedleRun.RunStartVbn.QuadPart;
 834         }
 835         else if (HaystackRun->RunEndVbn.QuadPart > NeedleRun.RunEndVbn.QuadPart)
 836         {
 837             ASSERT(HaystackRun->RunStartVbn.QuadPart < NeedleRun.RunEndVbn.QuadPart);
 838             HaystackRun->RunStartVbn.QuadPart = NeedleRun.RunEndVbn.QuadPart;
 839         }
 840         else
 841         {
 842             //ASSERT(NeedleRun.RunStartVbn.QuadPart >= HaystackRun->RunStartVbn.QuadPart);
 843             //ASSERT(NeedleRun.RunEndVbn.QuadPart <= HaystackRun->RunEndVbn.QuadPart);
 844             Mcb->Mapping->Table.CompareRoutine = McbMappingCompare;
 845             RtlDeleteElementGenericTable(&Mcb->Mapping->Table, HaystackRun);
 846             --Mcb->PairCount;
 847             Mcb->Mapping->Table.CompareRoutine = McbMappingIntersectCompare;
 848         }
 849     }
 850     Mcb->Mapping->Table.CompareRoutine = McbMappingCompare;
 851
 852 quit:
 853     DPRINT("FsRtlRemoveBaseMcbEntry(%p, %I64d, %I64d) = %d\n", OpaqueMcb, Vbn, SectorCount, Result);
 854     return Result;
 855 }
 856
 857 /*
 858  * @implemented
 859  */
 860 VOID
 861 NTAPI
 862 FsRtlRemoveLargeMcbEntry(IN PLARGE_MCB Mcb,
 863                          IN LONGLONG Vbn,
 864                          IN LONGLONG SectorCount)
 865 {
 866     DPRINT("FsRtlRemoveLargeMcbEntry(%p, %I64d, %I64d)\n", Mcb, Vbn, SectorCount);
 867
 868     KeAcquireGuardedMutex(Mcb->GuardedMutex);
 869     FsRtlRemoveBaseMcbEntry(&(Mcb->BaseMcb), Vbn, SectorCount);
 870     KeReleaseGuardedMutex(Mcb->GuardedMutex);
 871 }
 872
 873 /*
 874  * @implemented
 875  */
 876 VOID
 877 NTAPI
 878 FsRtlResetBaseMcb(IN PBASE_MCB OpaqueMcb)
 879 {
 880     PBASE_MCB_INTERNAL Mcb = (PBASE_MCB_INTERNAL)OpaqueMcb;
 881     PLARGE_MCB_MAPPING_ENTRY Element;
 882
 883     DPRINT("FsRtlResetBaseMcb(%p)\n", OpaqueMcb);
 884
 885     while (RtlNumberGenericTableElements(&Mcb->Mapping->Table) &&
 886            (Element = (PLARGE_MCB_MAPPING_ENTRY)RtlGetElementGenericTable(&Mcb->Mapping->Table, 0)))
 887     {
 888         RtlDeleteElementGenericTable(&Mcb->Mapping->Table, Element);
 889     }
 890
 891     Mcb->PairCount = 0;
 892     Mcb->MaximumPairCount = 0;
 893 }
 894
 895 /*
 896  * @implemented
 897  */
 898 VOID
 899 NTAPI
 900 FsRtlResetLargeMcb(IN PLARGE_MCB Mcb,
 901                    IN BOOLEAN SelfSynchronized)
 902 {
 903     DPRINT("FsRtlResetLargeMcb(%p, %d)\n", Mcb, SelfSynchronized);
 904
 905     if (!SelfSynchronized)
 906         KeAcquireGuardedMutex(Mcb->GuardedMutex);
 907
 908     FsRtlResetBaseMcb(&Mcb->BaseMcb);
 909
 910     if (!SelfSynchronized)
 911         KeReleaseGuardedMutex(Mcb->GuardedMutex);
 912 }
 913
 914 /*
 915  * @unimplemented
 916  */
 917 BOOLEAN
 918 NTAPI
 919 FsRtlSplitBaseMcb(IN PBASE_MCB OpaqueMcb,
 920                   IN LONGLONG Vbn,
 921                   IN LONGLONG Amount)
 922 {
 923     PBASE_MCB_INTERNAL Mcb = (PBASE_MCB_INTERNAL)OpaqueMcb;
 924     PLARGE_MCB_MAPPING_ENTRY Run, InsertLowerRun = NULL, ExistingRun = NULL;
 925     BOOLEAN NewElement;
 926
 927     DPRINT("FsRtlSplitBaseMcb(%p, %I64d, %I64d)\n", OpaqueMcb, Vbn, Amount);
 928
 929     /* Traverse the tree */
 930     for (Run = (PLARGE_MCB_MAPPING_ENTRY)RtlEnumerateGenericTable(&Mcb->Mapping->Table, TRUE);
 931         Run;
 932         Run = (PLARGE_MCB_MAPPING_ENTRY)RtlEnumerateGenericTable(&Mcb->Mapping->Table, FALSE))
 933     {
 934         /* unaffected run? */
 935         /* FIXME: performance: effective skip of all 'lower' runs without traversing them */
 936         if (Vbn >= Run->RunEndVbn.QuadPart) { DPRINT("Skipping it\n"); continue; }
 937
 938         /* crossing run to be split?
 939         * 'lower_run' is created on the original place; just shortened.
 940         * current 'run' is shifted up later
 941         */
 942         if (Vbn < Run->RunEndVbn.QuadPart)
 943         {
 944             /* FIXME: shift 'run->Lbn_start' ? */
 945             Run->RunStartVbn.QuadPart = Vbn;
 946
 947             InsertLowerRun = NULL;
 948         }
 949
 950         /* Shift the current 'run'.
 951         * Ordering is not changed in Generic Tree so I hope I do not need to reinsert it.
 952         */
 953         Run->RunStartVbn.QuadPart += Amount;
 954         ASSERT(Run->RunEndVbn.QuadPart + Amount > Run->RunEndVbn.QuadPart); /* overflow? */
 955         Run->RunEndVbn.QuadPart += Amount;
 956         /* FIXME: shift 'run->Lbn_start' ? */
 957
 958         /* continue the traversal */
 959     }
 960
 961     if (InsertLowerRun)
 962     {
 963         ExistingRun = RtlInsertElementGenericTable(&Mcb->Mapping->Table, InsertLowerRun, sizeof(*InsertLowerRun), &NewElement);
 964         ++Mcb->PairCount;
 965     }
 966
 967     ASSERT(ExistingRun == NULL);
 968
 969     DPRINT("FsRtlSplitBaseMcb(%p, %I64d, %I64d) = %d\n", OpaqueMcb, Vbn, Amount, TRUE);
 970
 971     return TRUE;
 972 }
 973
 974 /*
 975  * @implemented
 976  */
 977 BOOLEAN
 978 NTAPI
 979 FsRtlSplitLargeMcb(IN PLARGE_MCB Mcb,
 980                    IN LONGLONG Vbn,
 981                    IN LONGLONG Amount)
 982 {
 983     BOOLEAN Result;
 984
 985     DPRINT("FsRtlSplitLargeMcb(%p, %I64d, %I64d)\n", Mcb, Vbn, Amount);
 986
 987     KeAcquireGuardedMutex(Mcb->GuardedMutex);
 988     Result = FsRtlSplitBaseMcb(&(Mcb->BaseMcb),
 989                                Vbn,
 990                                Amount);
 991     KeReleaseGuardedMutex(Mcb->GuardedMutex);
 992
 993     DPRINT("FsRtlSplitLargeMcb(%p, %I64d, %I64d) = %d\n", Mcb, Vbn, Amount, Result);
 994
 995     return Result;
 996 }
 997
 998 /*
 999  * @unimplemented
1000  */
1001 VOID
1002 NTAPI
1003 FsRtlTruncateBaseMcb(IN PBASE_MCB OpaqueMcb,
1004                      IN LONGLONG Vbn)
1005 {
1006     DPRINT("FsRtlTruncateBaseMcb(%p, %I64d)\n", OpaqueMcb, Vbn);
1007
1008     FsRtlRemoveBaseMcbEntry(OpaqueMcb, Vbn, MAXLONG - Vbn + 1);
1009 }
1010
1011 /*
1012  * @implemented
1013  */
1014 VOID
1015 NTAPI
1016 FsRtlTruncateLargeMcb(IN PLARGE_MCB Mcb,
1017                       IN LONGLONG Vbn)
1018 {
1019     DPRINT("FsRtlTruncateLargeMcb(%p, %I64d)\n", Mcb, Vbn);
1020
1021     KeAcquireGuardedMutex(Mcb->GuardedMutex);
1022     FsRtlTruncateBaseMcb(&(Mcb->BaseMcb), Vbn);
1023     KeReleaseGuardedMutex(Mcb->GuardedMutex);
1024 }
1025
1026 /*
1027  * @implemented
1028  */
1029 VOID
1030 NTAPI
1031 FsRtlUninitializeBaseMcb(IN PBASE_MCB Mcb)
1032 {
1033     DPRINT("FsRtlUninitializeBaseMcb(%p)\n", Mcb);
1034
1035     FsRtlResetBaseMcb(Mcb);
1036
1037     if ((Mcb->PoolType == PagedPool)/* && (Mcb->MaximumPairCount == MAXIMUM_PAIR_COUNT)*/)
1038     {
1039         ExFreeToPagedLookasideList(&FsRtlFirstMappingLookasideList,
1040                                    Mcb->Mapping);
1041     }
1042     else
1043     {
1044         ExFreePoolWithTag(Mcb->Mapping, 'FSBC');
1045     }
1046 }
1047
1048 /*
1049  * @implemented
1050  */
1051 VOID
1052 NTAPI
1053 FsRtlUninitializeLargeMcb(IN PLARGE_MCB Mcb)
1054 {
1055     DPRINT("FsRtlUninitializeLargeMcb(%p)\n", Mcb);
1056
1057     if (Mcb->GuardedMutex)
1058     {
1059         ExFreeToNPagedLookasideList(&FsRtlFastMutexLookasideList,
1060                                     Mcb->GuardedMutex);
1061         FsRtlUninitializeBaseMcb(&(Mcb->BaseMcb));
1062     }
1063 }