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