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