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