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 VOID
 478 NTAPI
 479 FsRtlInitializeLargeMcbs(VOID)
 480 {
 481     /* Initialize the list for the MCB */
 482     ExInitializePagedLookasideList(&FsRtlFirstMappingLookasideList,
 483                                    NULL,
 484                                    NULL,
 485                                    POOL_RAISE_IF_ALLOCATION_FAILURE,
 486                                    sizeof(LARGE_MCB_MAPPING),
 487                                    IFS_POOL_TAG,
 488                                    0); /* FIXME: Should be 4 */
 489
 490     /* Initialize the list for the guarded mutex */
 491     ExInitializeNPagedLookasideList(&FsRtlFastMutexLookasideList,
 492                                     NULL,
 493                                     NULL,
 494                                     POOL_RAISE_IF_ALLOCATION_FAILURE,
 495                                     sizeof(KGUARDED_MUTEX),
 496                                     IFS_POOL_TAG,
 497                                     0); /* FIXME: Should be 32 */
 498 }
 499
 500 /*
 501  * @unimplemented
 502  */
 503 BOOLEAN
 504 NTAPI
 505 FsRtlLookupBaseMcbEntry(IN PBASE_MCB OpaqueMcb,
 506                         IN LONGLONG Vbn,
 507                         OUT PLONGLONG Lbn OPTIONAL,
 508                         OUT PLONGLONG SectorCountFromLbn OPTIONAL,
 509                         OUT PLONGLONG StartingLbn OPTIONAL,
 510                         OUT PLONGLONG SectorCountFromStartingLbn OPTIONAL,
 511                         OUT PULONG Index OPTIONAL)
 512 {
 513     PBASE_MCB_INTERNAL Mcb = (PBASE_MCB_INTERNAL)OpaqueMcb;
 514
 515
 516     ULONG RunIndex = 0;
 517     PLARGE_MCB_MAPPING_ENTRY Run, RunFound = NULL, RunFoundLower = NULL, RunFoundHigher = NULL;
 518     BOOLEAN First = TRUE;
 519
 520     /* Traverse the tree */
 521     for (Run = (PLARGE_MCB_MAPPING_ENTRY)RtlEnumerateGenericTable(&Mcb->Mapping->Table, TRUE);
 522         Run;
 523         Run = (PLARGE_MCB_MAPPING_ENTRY)RtlEnumerateGenericTable(&Mcb->Mapping->Table, FALSE))
 524     {
 525         if (First)
 526         {
 527             /* Take care when we must emulate missing 'hole' run at start of our run list. */
 528             if (Run->RunStartVbn.QuadPart > 0)
 529             {
 530                 RunIndex++;
 531                 RunFoundLower = &StaticRunBelow0;
 532             }
 533             First = FALSE;
 534         }
 535
 536         if (Run->RunStartVbn.QuadPart <= Vbn && Vbn < Run->RunEndVbn.QuadPart)
 537         {
 538             RunFound = Run;
 539             RunFoundLower = NULL;
 540             /* stop the traversal; hit */
 541             break;
 542         }
 543
 544         if (Run->RunEndVbn.QuadPart <= Vbn)
 545         {
 546             RunFoundLower = Run;
 547             if (Run->StartingLbn.QuadPart > 0)
 548             {
 549               RunIndex += 2;
 550             }
 551             /* continue the traversal; not yet crossed by the run */
 552             continue;
 553         }
 554
 555         if (Vbn < Run->RunStartVbn.QuadPart)
 556         {
 557             RunFoundHigher = Run;
 558             RunIndex++;
 559             /* stop the traversal; the run skipped us */
 560             break;
 561         }
 562
 563         ASSERT(FALSE);
 564         /* stop the traversal */
 565         break;
 566     }
 567
 568     if (RunFound)
 569     {
 570         ASSERT(RunFoundLower == NULL);
 571         ASSERT(RunFoundHigher == NULL);
 572
 573         if (Lbn)
 574             *Lbn = RunFound->StartingLbn.QuadPart + (Vbn - RunFound->RunStartVbn.QuadPart);
 575
 576         if (SectorCountFromLbn) /* FIXME: 'after' means including current 'Lbn' or without it? */
 577             *SectorCountFromLbn = RunFound->RunEndVbn.QuadPart - Vbn;
 578         if (StartingLbn)
 579             *StartingLbn = RunFound->StartingLbn.QuadPart;
 580         if (SectorCountFromStartingLbn)
 581             *SectorCountFromStartingLbn = RunFound->RunEndVbn.QuadPart - RunFound->RunStartVbn.QuadPart;
 582         if (Index)
 583             *Index = RunIndex;
 584
 585         return TRUE;
 586     }
 587
 588     if (RunFoundHigher)
 589     {
 590         /* search for hole */
 591         ASSERT(RunFoundLower != NULL);
 592
 593         if (Lbn)
 594             *Lbn = ~0ull;
 595         if (SectorCountFromLbn) /* FIXME: 'after' means including current 'Lbn' or without it? */
 596             *SectorCountFromLbn = RunFoundHigher->RunStartVbn.QuadPart - Vbn;
 597         if (StartingLbn)
 598             *StartingLbn = ~0ull;
 599         if (SectorCountFromStartingLbn)
 600             *SectorCountFromStartingLbn = RunFoundHigher->RunStartVbn.QuadPart - RunFoundLower->RunEndVbn.QuadPart;
 601         if (Index)
 602             *Index = RunIndex - 2;
 603
 604         return TRUE;
 605     }
 606
 607     /* We may have some 'RunFoundLower'. */
 608     return FALSE;
 609 }
 610
 611 /*
 612  * @implemented
 613  */
 614 BOOLEAN
 615 NTAPI
 616 FsRtlLookupLargeMcbEntry(IN PLARGE_MCB Mcb,
 617                          IN LONGLONG Vbn,
 618                          OUT PLONGLONG Lbn OPTIONAL,
 619                          OUT PLONGLONG SectorCountFromLbn OPTIONAL,
 620                          OUT PLONGLONG StartingLbn OPTIONAL,
 621                          OUT PLONGLONG SectorCountFromStartingLbn OPTIONAL,
 622                          OUT PULONG Index OPTIONAL)
 623 {
 624     BOOLEAN Result;
 625
 626     DPRINT("FsRtlLookupLargeMcbEntry Mcb %p Vbn %I64d\n", Mcb, Vbn);
 627
 628     KeAcquireGuardedMutex(Mcb->GuardedMutex);
 629     Result = FsRtlLookupBaseMcbEntry(&(Mcb->BaseMcb),
 630                                      Vbn,
 631                                      Lbn,
 632                                      SectorCountFromLbn,
 633                                      StartingLbn,
 634                                      SectorCountFromStartingLbn,
 635                                      Index);
 636     KeReleaseGuardedMutex(Mcb->GuardedMutex);
 637
 638     DPRINT("Done %u\n", Result);
 639
 640     return Result;
 641 }
 642
 643 static BOOLEAN
 644 NTAPI
 645 FsRtlLookupLastLargeMcbEntryAndIndex_internal(IN PBASE_MCB_INTERNAL Mcb,
 646                                               OUT PLONGLONG Vbn,
 647                                               OUT PLONGLONG Lbn,
 648                                               OUT PULONG Index OPTIONAL)
 649 {
 650     ULONG RunIndex = 0;
 651     PLARGE_MCB_MAPPING_ENTRY Run, RunFound = NULL;
 652     LONGLONG LastVbn = 0;
 653
 654     for (Run = (PLARGE_MCB_MAPPING_ENTRY)RtlEnumerateGenericTable(&Mcb->Mapping->Table, TRUE);
 655         Run;
 656         Run = (PLARGE_MCB_MAPPING_ENTRY)RtlEnumerateGenericTable(&Mcb->Mapping->Table, FALSE))
 657     {
 658         /* Take care when we must emulate missing 'hole' runs. */
 659         if (Run->RunStartVbn.QuadPart > LastVbn)
 660         {
 661             RunIndex++;
 662         }
 663         LastVbn = Run->RunEndVbn.QuadPart;
 664         RunIndex++;
 665         RunFound = Run;
 666     }
 667
 668     if (!RunFound)
 669     {
 670         return FALSE;
 671     }
 672
 673     if (Vbn)
 674     {
 675         *Vbn = RunFound->RunEndVbn.QuadPart - 1;
 676     }
 677     if (Lbn)
 678     {
 679         if (1)
 680         {
 681             *Lbn = RunFound->StartingLbn.QuadPart + (RunFound->RunEndVbn.QuadPart - RunFound->RunStartVbn.QuadPart) - 1;
 682         }
 683         else
 684         {
 685             *Lbn = ~0ULL;
 686         }
 687     }
 688     if (Index)
 689     {
 690         *Index = RunIndex - 1;
 691     }
 692
 693     return TRUE;
 694 }
 695
 696
 697 /*
 698  * @implemented
 699  */
 700 BOOLEAN
 701 NTAPI
 702 FsRtlLookupLastBaseMcbEntryAndIndex(IN PBASE_MCB OpaqueMcb,
 703                                     IN OUT PLONGLONG LargeVbn,
 704                                     IN OUT PLONGLONG LargeLbn,
 705                                     IN OUT PULONG Index)
 706 {
 707     PBASE_MCB_INTERNAL Mcb = (PBASE_MCB_INTERNAL)OpaqueMcb;
 708
 709     return FsRtlLookupLastLargeMcbEntryAndIndex_internal(Mcb, LargeVbn, LargeLbn, Index);
 710 }
 711
 712 /*
 713  * @implemented
 714  */
 715 BOOLEAN
 716 NTAPI
 717 FsRtlLookupLastLargeMcbEntryAndIndex(IN PLARGE_MCB OpaqueMcb,
 718                                      OUT PLONGLONG LargeVbn,
 719                                      OUT PLONGLONG LargeLbn,
 720                                      OUT PULONG Index)
 721 {
 722     BOOLEAN Result;
 723
 724     DPRINT("FsRtlLookupLastLargeMcbEntryAndIndex %p\n", OpaqueMcb);
 725
 726     KeAcquireGuardedMutex(OpaqueMcb->GuardedMutex);
 727     Result = FsRtlLookupLastBaseMcbEntryAndIndex(&(OpaqueMcb->BaseMcb),
 728                                                  LargeVbn,
 729                                                  LargeLbn,
 730                                                  Index);
 731     KeReleaseGuardedMutex(OpaqueMcb->GuardedMutex);
 732
 733     DPRINT("Done %u\n", Result);
 734
 735     return Result;
 736 }
 737
 738 /*
 739  * @unimplemented
 740  */
 741 BOOLEAN
 742 NTAPI
 743 FsRtlLookupLastBaseMcbEntry(IN PBASE_MCB OpaqueMcb,
 744                             OUT PLONGLONG Vbn,
 745                             OUT PLONGLONG Lbn)
 746 {
 747     PBASE_MCB_INTERNAL Mcb = (PBASE_MCB_INTERNAL)OpaqueMcb;
 748
 749     return FsRtlLookupLastLargeMcbEntryAndIndex_internal(Mcb, Vbn, Lbn, NULL); /* Index */
 750 }
 751
 752 /*
 753  * @implemented
 754  */
 755 BOOLEAN
 756 NTAPI
 757 FsRtlLookupLastLargeMcbEntry(IN PLARGE_MCB Mcb,
 758                              OUT PLONGLONG Vbn,
 759                              OUT PLONGLONG Lbn)
 760 {
 761     BOOLEAN Result;
 762
 763     DPRINT("FsRtlLookupLastLargeMcbEntry Mcb %p\n", Mcb);
 764
 765     KeAcquireGuardedMutex(Mcb->GuardedMutex);
 766     Result = FsRtlLookupLastBaseMcbEntry(&(Mcb->BaseMcb),
 767                                          Vbn,
 768                                          Lbn);
 769     KeReleaseGuardedMutex(Mcb->GuardedMutex);
 770
 771     DPRINT("Done %u\n", Result);
 772
 773     return Result;
 774 }
 775
 776 /*
 777  * @implemented
 778  */
 779 ULONG
 780 NTAPI
 781 FsRtlNumberOfRunsInBaseMcb(IN PBASE_MCB OpaqueMcb)
 782 {
 783     PBASE_MCB_INTERNAL Mcb = (PBASE_MCB_INTERNAL)OpaqueMcb;
 784     LONGLONG LbnAtVbn0 = -1;
 785     ULONG Nodes = RtlNumberGenericTableElements(&Mcb->Mapping->Table);
 786
 787     if (Nodes == 0) return 0;
 788
 789     FsRtlLookupBaseMcbEntry(OpaqueMcb,
 790         0,                           /* Vbn */
 791         &LbnAtVbn0,                  /* Lbn */
 792         NULL, NULL, NULL, NULL);     /* 4 output arguments - not interested in them */
 793
 794
 795     /* Return the count */
 796     //return Mcb->PairCount;
 797         /* Return the number of 'real' and 'hole' runs.
 798          * If we do not have sector 0 as 'real' emulate a 'hole' there.
 799          */
 800         return Nodes * 2 - (LbnAtVbn0 != -1 ? 1 : 0);   /* include holes as runs */
 801 }
 802
 803 /*
 804  * @implemented
 805  */
 806 ULONG
 807 NTAPI
 808 FsRtlNumberOfRunsInLargeMcb(IN PLARGE_MCB Mcb)
 809 {
 810     ULONG NumberOfRuns;
 811
 812     DPRINT("FsRtlNumberOfRunsInLargeMcb Mcb %p\n", Mcb);
 813
 814     /* Read the number of runs while holding the MCB lock */
 815     KeAcquireGuardedMutex(Mcb->GuardedMutex);
 816     NumberOfRuns = FsRtlNumberOfRunsInBaseMcb(&(Mcb->BaseMcb));
 817     KeReleaseGuardedMutex(Mcb->GuardedMutex);
 818
 819     DPRINT("Done %lu\n", NumberOfRuns);
 820
 821     /* Return the count */
 822     return NumberOfRuns;
 823 }
 824
 825 /*
 826  * @implemented
 827  * @Mcb: #PLARGE_MCB initialized by FsRtlInitializeLargeMcb().
 828  * %NULL value is forbidden.
 829  * @Vbn: Starting virtual block number to specify the range to delete.
 830  * @SectorCount: Length of the range to delete.
 831  * Value less or equal to %0 is forbidden; FIXME: Is the reject of %0 W32 compliant?
 832  *
 833  * Deletes any possible @Mcb mappings in the given range @Vbn ... @Vbn+@SectorCount-1.
 834  * This call has no problems if no mappings exist there yet.
 835  */
 836 BOOLEAN
 837 NTAPI
 838 FsRtlRemoveBaseMcbEntry(IN PBASE_MCB OpaqueMcb,
 839                         IN LONGLONG Vbn,
 840                         IN LONGLONG SectorCount)
 841 {
 842     PBASE_MCB_INTERNAL Mcb = (PBASE_MCB_INTERNAL)OpaqueMcb;
 843     LARGE_MCB_MAPPING_ENTRY NeedleRun;
 844     PLARGE_MCB_MAPPING_ENTRY HaystackRun;
 845
 846     if (Vbn < 0 || SectorCount <= 0) return FALSE;
 847     if (Vbn + SectorCount <= Vbn) return FALSE;
 848
 849     NeedleRun.RunStartVbn.QuadPart = Vbn;
 850     NeedleRun.RunEndVbn.QuadPart = Vbn + SectorCount;
 851     NeedleRun.StartingLbn.QuadPart = ~0ULL;
 852
 853     /* adjust/destroy all intersecting ranges */
 854     Mcb->Mapping->Table.CompareRoutine = McbMappingIntersectCompare;
 855     while ((HaystackRun = RtlLookupElementGenericTable(&Mcb->Mapping->Table, &NeedleRun)))
 856     {
 857         if (HaystackRun->RunStartVbn.QuadPart < NeedleRun.RunStartVbn.QuadPart)
 858         {
 859             ASSERT(HaystackRun->RunEndVbn.QuadPart > NeedleRun.RunStartVbn.QuadPart);
 860             HaystackRun->RunEndVbn.QuadPart = NeedleRun.RunStartVbn.QuadPart;
 861         }
 862         else if (HaystackRun->RunEndVbn.QuadPart > NeedleRun.RunEndVbn.QuadPart)
 863         {
 864             ASSERT(HaystackRun->RunStartVbn.QuadPart < NeedleRun.RunEndVbn.QuadPart);
 865             HaystackRun->RunStartVbn.QuadPart = NeedleRun.RunEndVbn.QuadPart;
 866         }
 867         else
 868         {
 869             ASSERT(NeedleRun.RunStartVbn.QuadPart >= HaystackRun->RunStartVbn.QuadPart);
 870             //ASSERT(NeedleRun.RunEndVbn.QuadPart <= HaystackRun->RunEndVbn.QuadPart);
 871             Mcb->Mapping->Table.CompareRoutine = McbMappingCompare;
 872             RtlDeleteElementGenericTable(&Mcb->Mapping->Table, HaystackRun);
 873             Mcb->Mapping->Table.CompareRoutine = McbMappingIntersectCompare;
 874         }
 875     }
 876     Mcb->Mapping->Table.CompareRoutine = McbMappingCompare;
 877
 878     return TRUE;
 879 }
 880
 881 /*
 882  * @implemented
 883  */
 884 VOID
 885 NTAPI
 886 FsRtlRemoveLargeMcbEntry(IN PLARGE_MCB Mcb,
 887                          IN LONGLONG Vbn,
 888                          IN LONGLONG SectorCount)
 889 {
 890     DPRINT("FsRtlRemoveLargeMcbEntry Mcb %p, Vbn %I64d, SectorCount %I64d\n", Mcb, Vbn, SectorCount);
 891
 892     KeAcquireGuardedMutex(Mcb->GuardedMutex);
 893     FsRtlRemoveBaseMcbEntry(&(Mcb->BaseMcb), Vbn, SectorCount);
 894     KeReleaseGuardedMutex(Mcb->GuardedMutex);
 895
 896     DPRINT("Done\n");
 897 }
 898
 899 /*
 900  * @implemented
 901  */
 902 VOID
 903 NTAPI
 904 FsRtlResetBaseMcb(IN PBASE_MCB OpaqueMcb)
 905 {
 906     PBASE_MCB_INTERNAL Mcb = (PBASE_MCB_INTERNAL)OpaqueMcb;
 907     PLARGE_MCB_MAPPING_ENTRY Element;
 908
 909     while (RtlNumberGenericTableElements(&Mcb->Mapping->Table) &&
 910            (Element = (PLARGE_MCB_MAPPING_ENTRY)RtlGetElementGenericTable(&Mcb->Mapping->Table, 0)))
 911     {
 912         RtlDeleteElementGenericTable(&Mcb->Mapping->Table, Element);
 913     }
 914
 915     Mcb->PairCount = 0;
 916     Mcb->MaximumPairCount = 0;
 917 }
 918
 919 /*
 920  * @implemented
 921  */
 922 VOID
 923 NTAPI
 924 FsRtlResetLargeMcb(IN PLARGE_MCB Mcb,
 925                    IN BOOLEAN SelfSynchronized)
 926 {
 927     if (!SelfSynchronized)
 928         KeAcquireGuardedMutex(Mcb->GuardedMutex);
 929
 930     FsRtlResetBaseMcb(&Mcb->BaseMcb);
 931
 932     if (!SelfSynchronized)
 933         KeReleaseGuardedMutex(Mcb->GuardedMutex);
 934 }
 935
 936 /*
 937  * @unimplemented
 938  */
 939 BOOLEAN
 940 NTAPI
 941 FsRtlSplitBaseMcb(IN PBASE_MCB OpaqueMcb,
 942                   IN LONGLONG Vbn,
 943                   IN LONGLONG Amount)
 944 {
 945     PBASE_MCB_INTERNAL Mcb = (PBASE_MCB_INTERNAL)OpaqueMcb;
 946     PLARGE_MCB_MAPPING_ENTRY Run, InsertLowerRun = NULL, ExistingRun = NULL;
 947     BOOLEAN NewElement;
 948
 949     /* Traverse the tree */
 950     for (Run = (PLARGE_MCB_MAPPING_ENTRY)RtlEnumerateGenericTable(&Mcb->Mapping->Table, TRUE);
 951         Run;
 952         Run = (PLARGE_MCB_MAPPING_ENTRY)RtlEnumerateGenericTable(&Mcb->Mapping->Table, FALSE))
 953     {
 954         /* unaffected run? */
 955         /* FIXME: performance: effective skip of all 'lower' runs without traversing them */
 956         if (Vbn >= Run->RunEndVbn.QuadPart) { DPRINT("Skipping it\n"); continue; }
 957
 958         /* crossing run to be split?
 959         * 'lower_run' is created on the original place; just shortened.
 960         * current 'run' is shifted up later
 961         */
 962         if (Vbn < Run->RunEndVbn.QuadPart)
 963         {
 964             /* FIXME: shift 'run->Lbn_start' ? */
 965             Run->RunStartVbn.QuadPart = Vbn;
 966
 967             InsertLowerRun = NULL;
 968         }
 969
 970         /* Shift the current 'run'.
 971         * Ordering is not changed in Generic Tree so I hope I do not need to reinsert it.
 972         */
 973         Run->RunStartVbn.QuadPart += Amount;
 974         ASSERT(Run->RunEndVbn.QuadPart + Amount > Run->RunEndVbn.QuadPart); /* overflow? */
 975         Run->RunEndVbn.QuadPart += Amount;
 976         /* FIXME: shift 'run->Lbn_start' ? */
 977
 978         /* continue the traversal */
 979     }
 980
 981     if (InsertLowerRun)
 982         ExistingRun = RtlInsertElementGenericTable(&Mcb->Mapping->Table, InsertLowerRun, sizeof(*InsertLowerRun), &NewElement);
 983
 984     ASSERT(ExistingRun == NULL);
 985
 986     return TRUE;
 987 }
 988
 989 /*
 990  * @implemented
 991  */
 992 BOOLEAN
 993 NTAPI
 994 FsRtlSplitLargeMcb(IN PLARGE_MCB Mcb,
 995                    IN LONGLONG Vbn,
 996                    IN LONGLONG Amount)
 997 {
 998     BOOLEAN Result;
 999
1000     DPRINT("FsRtlSplitLargeMcb %p, Vbn %I64d, Amount %I64d\n", Mcb, Vbn, Amount);
1001
1002     KeAcquireGuardedMutex(Mcb->GuardedMutex);
1003     Result = FsRtlSplitBaseMcb(&(Mcb->BaseMcb),
1004                                Vbn,
1005                                Amount);
1006     KeReleaseGuardedMutex(Mcb->GuardedMutex);
1007
1008     DPRINT("Done %u\n", Result);
1009
1010     return Result;
1011 }
1012
1013 /*
1014  * @unimplemented
1015  */
1016 VOID
1017 NTAPI
1018 FsRtlTruncateBaseMcb(IN PBASE_MCB OpaqueMcb,
1019                      IN LONGLONG Vbn)
1020 {
1021     DPRINT("Mcb=%p, Vbn=%I64d\n", OpaqueMcb, Vbn);
1022     FsRtlRemoveBaseMcbEntry(OpaqueMcb, Vbn, MAXLONG - Vbn + 1);
1023 }
1024
1025 /*
1026  * @implemented
1027  */
1028 VOID
1029 NTAPI
1030 FsRtlTruncateLargeMcb(IN PLARGE_MCB Mcb,
1031                       IN LONGLONG Vbn)
1032 {
1033     DPRINT("FsRtlTruncateLargeMcb %p Vbn %I64d\n", Mcb, Vbn);
1034     KeAcquireGuardedMutex(Mcb->GuardedMutex);
1035     FsRtlTruncateBaseMcb(&(Mcb->BaseMcb), Vbn);
1036     KeReleaseGuardedMutex(Mcb->GuardedMutex);
1037     DPRINT("Done\n");
1038 }
1039
1040 /*
1041  * @implemented
1042  */
1043 VOID
1044 NTAPI
1045 FsRtlUninitializeBaseMcb(IN PBASE_MCB Mcb)
1046 {
1047     FsRtlResetBaseMcb(Mcb);
1048
1049     if ((Mcb->PoolType == PagedPool)/* && (Mcb->MaximumPairCount == MAXIMUM_PAIR_COUNT)*/)
1050     {
1051         ExFreeToPagedLookasideList(&FsRtlFirstMappingLookasideList,
1052                                    Mcb->Mapping);
1053     }
1054     else
1055     {
1056         ExFreePoolWithTag(Mcb->Mapping, 'FSBC');
1057     }
1058 }
1059
1060 /*
1061  * @implemented
1062  */
1063 VOID
1064 NTAPI
1065 FsRtlUninitializeLargeMcb(IN PLARGE_MCB Mcb)
1066 {
1067     if (Mcb->GuardedMutex)
1068     {
1069         ExFreeToNPagedLookasideList(&FsRtlFastMutexLookasideList,
1070                                     Mcb->GuardedMutex);
1071         FsRtlUninitializeBaseMcb(&(Mcb->BaseMcb));
1072     }
1073 }