reactos/ntoskrnl/fsrtl/largemcb.c

   1 /*
   2  * PROJECT:         ReactOS Kernel
   3  * LICENSE:         GPL - 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:     Alex Ionescu (alex.ionescu@reactos.org)
   7  *                  Pierre Schweitzer (heis_spiter@hotmail.com)
   8  *                  Art Yerkes (art.yerkes@gmail.com)
   9  */
  10
  11 /* INCLUDES ******************************************************************/
  12
  13 #include <ntoskrnl.h>
  14 #define NDEBUG
  15 #include <debug.h>
  16
  17 /* GLOBALS *******************************************************************/
  18
  19 #define GET_LIST_HEAD(x) ((PLIST_ENTRY)(&((PRTL_GENERIC_TABLE)x)[1]))
  20
  21 PAGED_LOOKASIDE_LIST FsRtlFirstMappingLookasideList;
  22 NPAGED_LOOKASIDE_LIST FsRtlFastMutexLookasideList;
  23
  24 typedef struct _LARGE_MCB_MAPPING_ENTRY
  25 {
  26         LARGE_INTEGER RunStartVbn;
  27         LARGE_INTEGER SectorCount;
  28         LARGE_INTEGER StartingLbn;
  29         LIST_ENTRY Sequence;
  30 } LARGE_MCB_MAPPING_ENTRY, *PLARGE_MCB_MAPPING_ENTRY;
  31
  32 static VOID McbPrintTree(PBASE_MCB Mcb)
  33 {
  34         PLARGE_MCB_MAPPING_ENTRY Entry;
  35         for (Entry = (PLARGE_MCB_MAPPING_ENTRY)
  36                          RtlEnumerateGenericTable(Mcb->Mapping, TRUE);
  37                  Entry;
  38                  Entry = (PLARGE_MCB_MAPPING_ENTRY)
  39                          RtlEnumerateGenericTable(Mcb->Mapping, FALSE))
  40         {
  41                 DPRINT1
  42                         ("Vbn %x Lbn %x Count %x\n",
  43                          Entry->RunStartVbn.LowPart,
  44                          Entry->StartingLbn.LowPart,
  45                          Entry->SectorCount.LowPart);
  46         }
  47 }
  48
  49 static PVOID NTAPI McbMappingAllocate(PRTL_GENERIC_TABLE Table, CLONG Bytes)
  50 {
  51         PVOID Result;
  52         PBASE_MCB Mcb = (PBASE_MCB)Table->TableContext;
  53         Result = ExAllocatePoolWithTag(Mcb->PoolType, Bytes, 'LMCB');
  54         DPRINT("McbMappingAllocate(%d) => %p\n", Bytes, Result);
  55         return Result;
  56 }
  57
  58 static VOID NTAPI McbMappingFree(PRTL_GENERIC_TABLE Table, PVOID Buffer)
  59 {
  60         DPRINT("McbMappingFree(%p)\n", Buffer);
  61         ExFreePoolWithTag(Buffer, 'LMCB');
  62 }
  63
  64 static RTL_GENERIC_COMPARE_RESULTS NTAPI McbMappingCompare
  65 (PRTL_GENERIC_TABLE Table, PVOID PtrA, PVOID PtrB)
  66 {
  67         PLARGE_MCB_MAPPING_ENTRY A = PtrA, B = PtrB;
  68         RTL_GENERIC_COMPARE_RESULTS Result;
  69         DPRINT("Starting to compare element %x to element %x\n", PtrA, PtrB);
  70         Result =
  71                 (A->RunStartVbn.QuadPart + A->SectorCount.QuadPart <=
  72                  B->RunStartVbn.QuadPart) ? GenericLessThan :
  73                 (A->RunStartVbn.QuadPart >=
  74                  B->RunStartVbn.QuadPart + B->SectorCount.QuadPart) ?
  75                 GenericGreaterThan : GenericEqual;
  76         DPRINT("Compare(%x:%x): %x:%x to %x:%x => %d\n",
  77                    A,B,
  78                    A->RunStartVbn.LowPart, A->SectorCount.LowPart,
  79                    B->RunStartVbn.LowPart, B->SectorCount.LowPart,
  80                    Result);
  81         return Result;
  82 }
  83
  84 /* PUBLIC FUNCTIONS **********************************************************/
  85
  86 /*
  87  * @implemented
  88  */
  89 BOOLEAN
  90 NTAPI
  91 FsRtlAddBaseMcbEntry(IN PBASE_MCB Mcb,
  92                      IN LONGLONG Vbn,
  93                      IN LONGLONG Lbn,
  94                      IN LONGLONG SectorCount)
  95 {
  96         LARGE_MCB_MAPPING_ENTRY Node;
  97         PLARGE_MCB_MAPPING_ENTRY Existing = NULL;
  98         BOOLEAN NewElement = FALSE;
  99
 100         McbPrintTree(Mcb);
 101
 102         Node.RunStartVbn.QuadPart = Vbn;
 103         Node.StartingLbn.QuadPart = Lbn;
 104         Node.SectorCount.QuadPart = SectorCount;
 105
 106         DPRINT("RunStartVbn %x\n", Node.RunStartVbn.LowPart);
 107         DPRINT("StartingLbn %x\n", Node.StartingLbn.LowPart);
 108         DPRINT("SectorCount %x\n", Node.SectorCount.LowPart);
 109
 110         while (!NewElement)
 111         {
 112                 DPRINT("Inserting %x:%x\n", Node.RunStartVbn.LowPart, Node.SectorCount.LowPart);
 113                 Existing = RtlInsertElementGenericTable
 114                         (Mcb->Mapping, &Node, sizeof(Node), &NewElement);
 115                 DPRINT("Existing %x\n", Existing);
 116                 if (!Existing) break;
 117
 118                 DPRINT("NewElement %d\n", NewElement);
 119                 if (!NewElement)
 120                 {
 121                         // We merge the existing runs
 122                         LARGE_INTEGER StartVbn, FinalVbn;
 123                         DPRINT("Existing: %x:%x\n",
 124                                    Existing->RunStartVbn.LowPart, Node.SectorCount.LowPart);
 125                         if (Existing->RunStartVbn.QuadPart < Node.RunStartVbn.QuadPart)
 126                         {
 127                                 StartVbn = Existing->RunStartVbn;
 128                                 Node.StartingLbn = Existing->StartingLbn;
 129                         }
 130                         else
 131                         {
 132                                 StartVbn = Node.RunStartVbn;
 133                         }
 134                         DPRINT("StartVbn %x\n", StartVbn.LowPart);
 135                         if (Existing->RunStartVbn.QuadPart + Existing->SectorCount.QuadPart >
 136                                 Node.RunStartVbn.QuadPart + Node.SectorCount.QuadPart)
 137                         {
 138                                 FinalVbn.QuadPart =
 139                                         Existing->RunStartVbn.QuadPart + Existing->SectorCount.QuadPart;
 140                         }
 141                         else
 142                         {
 143                                 FinalVbn.QuadPart =
 144                                         Node.RunStartVbn.QuadPart + Node.SectorCount.QuadPart;
 145                         }
 146                         DPRINT("FinalVbn %x\n", FinalVbn.LowPart);
 147                         Node.RunStartVbn.QuadPart = StartVbn.QuadPart;
 148                         Node.SectorCount.QuadPart = FinalVbn.QuadPart - StartVbn.QuadPart;
 149                         RemoveHeadList(&Existing->Sequence);
 150                         RtlDeleteElementGenericTable(Mcb->Mapping, Existing);
 151                         Mcb->PairCount--;
 152                 }
 153                 else
 154                 {
 155                         DPRINT("Mapping added %x\n", Existing);
 156                         Mcb->MaximumPairCount++;
 157                         Mcb->PairCount++;
 158                         InsertHeadList(GET_LIST_HEAD(Mcb->Mapping), &Existing->Sequence);
 159                 }
 160         }
 161
 162         DPRINT("!!Existing %d\n", !!Existing);
 163         McbPrintTree(Mcb);
 164         return !!Existing;
 165 }
 166
 167 /*
 168  * @implemented
 169  */
 170 BOOLEAN
 171 NTAPI
 172 FsRtlAddLargeMcbEntry(IN PLARGE_MCB Mcb,
 173                       IN LONGLONG Vbn,
 174                       IN LONGLONG Lbn,
 175                       IN LONGLONG SectorCount)
 176 {
 177     BOOLEAN Result;
 178
 179         DPRINT
 180                 ("Mcb %x Vbn %x Lbn %x SectorCount %x\n",
 181                  Mcb, (ULONG)Vbn, (ULONG)Lbn, (ULONG)SectorCount);
 182
 183     KeAcquireGuardedMutex(Mcb->GuardedMutex);
 184     Result = FsRtlAddBaseMcbEntry(&(Mcb->BaseMcb),
 185                                   Vbn,
 186                                   Lbn,
 187                                   SectorCount);
 188     KeReleaseGuardedMutex(Mcb->GuardedMutex);
 189
 190         DPRINT("Done %d\n", Result);
 191
 192     return Result;
 193 }
 194
 195 /*
 196  * @unimplemented
 197  */
 198 BOOLEAN
 199 NTAPI
 200 FsRtlGetNextBaseMcbEntry(IN PBASE_MCB Mcb,
 201                          IN ULONG RunIndex,
 202                          OUT PLONGLONG Vbn,
 203                          OUT PLONGLONG Lbn,
 204                          OUT PLONGLONG SectorCount)
 205 {
 206         ULONG i = 0;
 207         BOOLEAN Result = FALSE;
 208         PLARGE_MCB_MAPPING_ENTRY Entry;
 209         for (Entry = (PLARGE_MCB_MAPPING_ENTRY)
 210                          RtlEnumerateGenericTable(Mcb->Mapping, TRUE);
 211                  Entry && i < RunIndex;
 212                  Entry = (PLARGE_MCB_MAPPING_ENTRY)
 213                          RtlEnumerateGenericTable(Mcb->Mapping, FALSE), i++);
 214         if (Entry)
 215         {
 216                 Result = TRUE;
 217                 if (Vbn)
 218                         *Vbn = Entry->RunStartVbn.QuadPart;
 219                 if (Lbn)
 220                         *Lbn = Entry->StartingLbn.QuadPart;
 221                 if (SectorCount)
 222                         *SectorCount = Entry->SectorCount.QuadPart;
 223         }
 224
 225         return Result;
 226 }
 227
 228 /*
 229  * @implemented
 230  */
 231 BOOLEAN
 232 NTAPI
 233 FsRtlGetNextLargeMcbEntry(IN PLARGE_MCB Mcb,
 234                           IN ULONG RunIndex,
 235                           OUT PLONGLONG Vbn,
 236                           OUT PLONGLONG Lbn,
 237                           OUT PLONGLONG SectorCount)
 238 {
 239     BOOLEAN Result;
 240
 241         DPRINT("FsRtlGetNextLargeMcbEntry Mcb %x RunIndex %x\n", Mcb, RunIndex);
 242
 243     KeAcquireGuardedMutex(Mcb->GuardedMutex);
 244     Result = FsRtlGetNextBaseMcbEntry(&(Mcb->BaseMcb),
 245                                       RunIndex,
 246                                       Vbn,
 247                                       Lbn,
 248                                       SectorCount);
 249     KeReleaseGuardedMutex(Mcb->GuardedMutex);
 250
 251         DPRINT("Done %d\n", Result);
 252
 253     return Result;
 254 }
 255
 256 /*
 257  * @implemented
 258  */
 259 VOID
 260 NTAPI
 261 FsRtlInitializeBaseMcb(IN PBASE_MCB Mcb,
 262                        IN POOL_TYPE PoolType)
 263 {
 264     Mcb->PairCount = 0;
 265
 266     if (PoolType == PagedPool)
 267     {
 268         Mcb->Mapping = ExAllocateFromPagedLookasideList(&FsRtlFirstMappingLookasideList);
 269                 DPRINT("Get from lookaside list\n");
 270     }
 271     else
 272     {
 273         Mcb->Mapping = ExAllocatePoolWithTag(PoolType | POOL_RAISE_IF_ALLOCATION_FAILURE,
 274                                                                                          sizeof(RTL_GENERIC_TABLE) + sizeof(LIST_ENTRY),
 275                                              'FSBC');
 276                 DPRINT("Allocate\n");
 277     }
 278
 279         DPRINT("Mcb->Mapping %x\n", Mcb->Mapping);
 280     Mcb->PoolType = PoolType;
 281     Mcb->MaximumPairCount = MAXIMUM_PAIR_COUNT;
 282         RtlInitializeGenericTable
 283                 (Mcb->Mapping,
 284                  McbMappingCompare,
 285                  McbMappingAllocate,
 286                  McbMappingFree,
 287                  Mcb);
 288         InitializeListHead(GET_LIST_HEAD(Mcb->Mapping));
 289 }
 290
 291 /*
 292  * @implemented
 293  */
 294 VOID
 295 NTAPI
 296 FsRtlInitializeLargeMcb(IN PLARGE_MCB Mcb,
 297                         IN POOL_TYPE PoolType)
 298 {
 299     Mcb->GuardedMutex = ExAllocateFromNPagedLookasideList(&FsRtlFastMutexLookasideList);
 300
 301     KeInitializeGuardedMutex(Mcb->GuardedMutex);
 302
 303     _SEH2_TRY
 304     {
 305         FsRtlInitializeBaseMcb(&(Mcb->BaseMcb), PoolType);
 306     }
 307     _SEH2_EXCEPT(EXCEPTION_EXECUTE_HANDLER)
 308     {
 309         ExFreeToNPagedLookasideList(&FsRtlFastMutexLookasideList,
 310                                     Mcb->GuardedMutex);
 311         Mcb->GuardedMutex = NULL;
 312     }
 313     _SEH2_END;
 314 }
 315
 316 /*
 317  * @implemented
 318  */
 319 VOID
 320 NTAPI
 321 FsRtlInitializeLargeMcbs(VOID)
 322 {
 323     /* Initialize the list for the MCB */
 324     ExInitializePagedLookasideList(&FsRtlFirstMappingLookasideList,
 325                                    NULL,
 326                                    NULL,
 327                                    POOL_RAISE_IF_ALLOCATION_FAILURE,
 328                                                                    sizeof(RTL_GENERIC_TABLE) + sizeof(LIST_ENTRY),
 329                                    IFS_POOL_TAG,
 330                                    0); /* FIXME: Should be 4 */
 331
 332     /* Initialize the list for the guarded mutex */
 333     ExInitializeNPagedLookasideList(&FsRtlFastMutexLookasideList,
 334                                     NULL,
 335                                     NULL,
 336                                     POOL_RAISE_IF_ALLOCATION_FAILURE,
 337                                     sizeof(KGUARDED_MUTEX),
 338                                     IFS_POOL_TAG,
 339                                     0); /* FIXME: Should be 32 */
 340 }
 341
 342 /*
 343  * @unimplemented
 344  */
 345 BOOLEAN
 346 NTAPI
 347 FsRtlLookupBaseMcbEntry(IN PBASE_MCB Mcb,
 348                         IN LONGLONG Vbn,
 349                         OUT PLONGLONG Lbn OPTIONAL,
 350                         OUT PLONGLONG SectorCountFromLbn OPTIONAL,
 351                         OUT PLONGLONG StartingLbn OPTIONAL,
 352                         OUT PLONGLONG SectorCountFromStartingLbn OPTIONAL,
 353                         OUT PULONG Index OPTIONAL)
 354 {
 355         BOOLEAN Result = FALSE;
 356         LARGE_MCB_MAPPING_ENTRY ToLookup;
 357         PLARGE_MCB_MAPPING_ENTRY Entry;
 358
 359         ToLookup.RunStartVbn.QuadPart = Vbn;
 360         ToLookup.SectorCount.QuadPart = 1;
 361
 362         Entry = RtlLookupElementGenericTable(Mcb->Mapping, &ToLookup);
 363         if (!Entry)
 364         {
 365                 // Find out if we have a following entry.  The spec says we should return
 366                 // found with Lbn == -1 when we're beneath the largest map.
 367                 ToLookup.SectorCount.QuadPart = (1ull<<62) - ToLookup.RunStartVbn.QuadPart;
 368                 Entry = RtlLookupElementGenericTable(Mcb->Mapping, &ToLookup);
 369                 if (Entry)
 370                 {
 371                         Result = TRUE;
 372                         if (Lbn) *Lbn = ~0ull;
 373                 }
 374                 else
 375                 {
 376                         Result = FALSE;
 377                 }
 378         }
 379         else
 380         {
 381                 LARGE_INTEGER Offset;
 382                 Offset.QuadPart = Vbn - Entry->RunStartVbn.QuadPart;
 383                 Result = TRUE;
 384                 if (Lbn) *Lbn = Entry->StartingLbn.QuadPart + Offset.QuadPart;
 385                 if (SectorCountFromLbn) *SectorCountFromLbn = Entry->SectorCount.QuadPart - Offset.QuadPart;
 386                 if (StartingLbn) *StartingLbn = Entry->StartingLbn.QuadPart;
 387                 if (SectorCountFromStartingLbn) *SectorCountFromStartingLbn = Entry->SectorCount.QuadPart;
 388         }
 389
 390     return Result;
 391 }
 392
 393 /*
 394  * @implemented
 395  */
 396 BOOLEAN
 397 NTAPI
 398 FsRtlLookupLargeMcbEntry(IN PLARGE_MCB Mcb,
 399                          IN LONGLONG Vbn,
 400                          OUT PLONGLONG Lbn OPTIONAL,
 401                          OUT PLONGLONG SectorCountFromLbn OPTIONAL,
 402                          OUT PLONGLONG StartingLbn OPTIONAL,
 403                          OUT PLONGLONG SectorCountFromStartingLbn OPTIONAL,
 404                          OUT PULONG Index OPTIONAL)
 405 {
 406     BOOLEAN Result;
 407
 408         DPRINT("FsRtlLookupLargeMcbEntry Mcb %x Vbn %x\n", Mcb, (ULONG)Vbn);
 409
 410     KeAcquireGuardedMutex(Mcb->GuardedMutex);
 411     Result = FsRtlLookupBaseMcbEntry(&(Mcb->BaseMcb),
 412                                      Vbn,
 413                                      Lbn,
 414                                      SectorCountFromLbn,
 415                                      StartingLbn,
 416                                      SectorCountFromStartingLbn,
 417                                      Index);
 418     KeReleaseGuardedMutex(Mcb->GuardedMutex);
 419
 420         DPRINT("Done %d (%x)\n", Result, Lbn ? (ULONG)*Lbn : 0);
 421
 422     return Result;
 423 }
 424
 425 /*
 426  * @unimplemented
 427  */
 428 BOOLEAN
 429 NTAPI
 430 FsRtlLookupLastBaseMcbEntryAndIndex(IN PBASE_MCB OpaqueMcb,
 431                                     IN OUT PLONGLONG LargeVbn,
 432                                     IN OUT PLONGLONG LargeLbn,
 433                                     IN OUT PULONG Index)
 434 {
 435         ULONG i = 0;
 436         BOOLEAN Result = FALSE;
 437         PLIST_ENTRY ListEntry;
 438         PLARGE_MCB_MAPPING_ENTRY Entry;
 439         PLARGE_MCB_MAPPING_ENTRY CountEntry;
 440
 441         ListEntry = GET_LIST_HEAD(OpaqueMcb->Mapping);
 442         if (!IsListEmpty(ListEntry))
 443         {
 444                 Entry = CONTAINING_RECORD(ListEntry->Flink, LARGE_MCB_MAPPING_ENTRY, Sequence);
 445                 Result = TRUE;
 446                 *LargeVbn = Entry->RunStartVbn.QuadPart;
 447                 *LargeLbn = Entry->StartingLbn.QuadPart;
 448
 449                 for (i = 0, CountEntry = RtlEnumerateGenericTable(OpaqueMcb->Mapping, TRUE);
 450                          CountEntry != Entry;
 451                          CountEntry = RtlEnumerateGenericTable(OpaqueMcb->Mapping, FALSE));
 452
 453                 *Index = i;
 454         }
 455
 456         return Result;
 457 }
 458
 459 /*
 460  * @implemented
 461  */
 462 BOOLEAN
 463 NTAPI
 464 FsRtlLookupLastLargeMcbEntryAndIndex(IN PLARGE_MCB OpaqueMcb,
 465                                      OUT PLONGLONG LargeVbn,
 466                                      OUT PLONGLONG LargeLbn,
 467                                      OUT PULONG Index)
 468 {
 469     BOOLEAN Result;
 470
 471         DPRINT("FsRtlLookupLastLargeMcbEntryAndIndex %x\n", OpaqueMcb);
 472
 473     KeAcquireGuardedMutex(OpaqueMcb->GuardedMutex);
 474     Result = FsRtlLookupLastBaseMcbEntryAndIndex(&(OpaqueMcb->BaseMcb),
 475                                                  LargeVbn,
 476                                                  LargeLbn,
 477                                                  Index);
 478     KeReleaseGuardedMutex(OpaqueMcb->GuardedMutex);
 479
 480         DPRINT("Done %d\n", Result);
 481
 482     return Result;
 483 }
 484
 485 /*
 486  * @unimplemented
 487  */
 488 BOOLEAN
 489 NTAPI
 490 FsRtlLookupLastBaseMcbEntry(IN PBASE_MCB Mcb,
 491                             OUT PLONGLONG Vbn,
 492                             OUT PLONGLONG Lbn)
 493 {
 494         BOOLEAN Result = FALSE;
 495         PLIST_ENTRY ListEntry;
 496         PLARGE_MCB_MAPPING_ENTRY Entry;
 497
 498         ListEntry = GET_LIST_HEAD(Mcb->Mapping);
 499         if (!IsListEmpty(ListEntry))
 500         {
 501                 Entry = CONTAINING_RECORD(ListEntry->Flink, LARGE_MCB_MAPPING_ENTRY, Sequence);
 502                 Result = TRUE;
 503                 *Vbn = Entry->RunStartVbn.QuadPart;
 504                 *Lbn = Entry->StartingLbn.QuadPart;
 505         }
 506
 507         return Result;
 508 }
 509
 510 /*
 511  * @implemented
 512  */
 513 BOOLEAN
 514 NTAPI
 515 FsRtlLookupLastLargeMcbEntry(IN PLARGE_MCB Mcb,
 516                              OUT PLONGLONG Vbn,
 517                              OUT PLONGLONG Lbn)
 518 {
 519     BOOLEAN Result;
 520
 521         DPRINT("FsRtlLookupLastLargeMcbEntry Mcb %x\n", Mcb);
 522
 523     KeAcquireGuardedMutex(Mcb->GuardedMutex);
 524     Result = FsRtlLookupLastBaseMcbEntry(&(Mcb->BaseMcb),
 525                                          Vbn,
 526                                          Lbn);
 527     KeReleaseGuardedMutex(Mcb->GuardedMutex);
 528
 529         DPRINT("Done %d\n", Result);
 530
 531     return Result;
 532 }
 533
 534 /*
 535  * @implemented
 536  */
 537 ULONG
 538 NTAPI
 539 FsRtlNumberOfRunsInBaseMcb(IN PBASE_MCB Mcb)
 540 {
 541     /* Return the count */
 542     return Mcb->PairCount;
 543 }
 544
 545 /*
 546  * @implemented
 547  */
 548 ULONG
 549 NTAPI
 550 FsRtlNumberOfRunsInLargeMcb(IN PLARGE_MCB Mcb)
 551 {
 552     ULONG NumberOfRuns;
 553
 554         DPRINT("FsRtlNumberOfRunsInLargeMcb Mcb %x\n", Mcb);
 555
 556     /* Read the number of runs while holding the MCB lock */
 557     KeAcquireGuardedMutex(Mcb->GuardedMutex);
 558     NumberOfRuns = Mcb->BaseMcb.PairCount;
 559     KeReleaseGuardedMutex(Mcb->GuardedMutex);
 560
 561         DPRINT("Done %d\n", NumberOfRuns);
 562
 563     /* Return the count */
 564     return NumberOfRuns;
 565 }
 566
 567 /*
 568  * @unimplemented
 569  */
 570 VOID
 571 NTAPI
 572 FsRtlRemoveBaseMcbEntry(IN PBASE_MCB Mcb,
 573                         IN LONGLONG Vbn,
 574                         IN LONGLONG SectorCount)
 575 {
 576         LARGE_MCB_MAPPING_ENTRY Node;
 577         PLARGE_MCB_MAPPING_ENTRY Element;
 578
 579         Node.RunStartVbn.QuadPart = Vbn;
 580         Node.SectorCount.QuadPart = SectorCount;
 581
 582         while ((Element = RtlLookupElementGenericTable(Mcb->Mapping, &Node)))
 583         {
 584                 // Must split
 585                 if (Element->RunStartVbn.QuadPart < Node.RunStartVbn.QuadPart &&
 586                         Element->SectorCount.QuadPart > Node.SectorCount.QuadPart)
 587                 {
 588                         LARGE_MCB_MAPPING_ENTRY Upper, Reinsert;
 589                         PLARGE_MCB_MAPPING_ENTRY Reinserted, Inserted;
 590                         LARGE_INTEGER StartHole = Node.RunStartVbn;
 591                         LARGE_INTEGER EndHole;
 592                         EndHole.QuadPart = Node.RunStartVbn.QuadPart + Node.SectorCount.QuadPart;
 593                         Upper.RunStartVbn.QuadPart = EndHole.QuadPart;
 594                         Upper.StartingLbn.QuadPart =
 595                                 Element->StartingLbn.QuadPart +
 596                                 EndHole.QuadPart -
 597                                 Element->RunStartVbn.QuadPart;
 598                         Upper.SectorCount.QuadPart =
 599                                 Element->SectorCount.QuadPart -
 600                                 (EndHole.QuadPart - Element->RunStartVbn.QuadPart);
 601                         Reinsert = *Element;
 602                         Reinsert.SectorCount.QuadPart =
 603                                 Element->RunStartVbn.QuadPart - StartHole.QuadPart;
 604                         RemoveEntryList(&Element->Sequence);
 605                         RtlDeleteElementGenericTable(Mcb->Mapping, Element);
 606                         Mcb->PairCount--;
 607
 608                         Reinserted = RtlInsertElementGenericTable
 609                                 (Mcb->Mapping, &Reinsert, sizeof(Reinsert), NULL);
 610                         InsertHeadList(GET_LIST_HEAD(Mcb->Mapping), &Reinserted->Sequence);
 611                         Mcb->PairCount++;
 612
 613                         Inserted = RtlInsertElementGenericTable
 614                                 (Mcb->Mapping, &Upper, sizeof(Upper), NULL);
 615                         InsertHeadList(GET_LIST_HEAD(Mcb->Mapping), &Inserted->Sequence);
 616                         Mcb->PairCount++;
 617                 }
 618                 else if (Element->RunStartVbn.QuadPart < Node.RunStartVbn.QuadPart)
 619                 {
 620                         LARGE_MCB_MAPPING_ENTRY NewElement;
 621                         PLARGE_MCB_MAPPING_ENTRY Reinserted;
 622                         LARGE_INTEGER StartHole = Node.RunStartVbn;
 623                         NewElement.RunStartVbn = Element->RunStartVbn;
 624                         NewElement.StartingLbn = Element->StartingLbn;
 625                         NewElement.SectorCount.QuadPart = StartHole.QuadPart - Element->StartingLbn.QuadPart;
 626
 627                         RemoveEntryList(&Element->Sequence);
 628                         RtlDeleteElementGenericTable(Mcb->Mapping, Element);
 629                         Mcb->PairCount--;
 630
 631                         Reinserted = RtlInsertElementGenericTable
 632                                 (Mcb->Mapping, &NewElement, sizeof(NewElement), NULL);
 633                         InsertHeadList(GET_LIST_HEAD(Mcb->Mapping), &Reinserted->Sequence);
 634                         Mcb->PairCount++;
 635                 }
 636                 else
 637                 {
 638                         LARGE_MCB_MAPPING_ENTRY NewElement;
 639                         PLARGE_MCB_MAPPING_ENTRY Reinserted;
 640                         LARGE_INTEGER EndHole = Element->RunStartVbn;
 641                         LARGE_INTEGER EndRun;
 642                         EndRun.QuadPart = Element->RunStartVbn.QuadPart + Element->SectorCount.QuadPart;
 643                         NewElement.RunStartVbn = EndHole;
 644                         NewElement.StartingLbn.QuadPart = Element->StartingLbn.QuadPart +
 645                                 (EndHole.QuadPart - Element->RunStartVbn.QuadPart);
 646                         NewElement.SectorCount.QuadPart = EndRun.QuadPart - EndHole.QuadPart;
 647
 648                         RemoveEntryList(&Element->Sequence);
 649                         RtlDeleteElementGenericTable(Mcb->Mapping, Element);
 650                         Mcb->PairCount--;
 651
 652                         Reinserted = RtlInsertElementGenericTable
 653                                 (Mcb->Mapping, &NewElement, sizeof(NewElement), NULL);
 654                         InsertHeadList(GET_LIST_HEAD(Mcb->Mapping), &Reinserted->Sequence);
 655                         Mcb->PairCount++;
 656                 }
 657         }
 658 }
 659
 660 /*
 661  * @implemented
 662  */
 663 VOID
 664 NTAPI
 665 FsRtlRemoveLargeMcbEntry(IN PLARGE_MCB Mcb,
 666                          IN LONGLONG Vbn,
 667                          IN LONGLONG SectorCount)
 668 {
 669         DPRINT("FsRtlRemoveLargeMcbEntry Mcb %x, Vbn %x, SectorCount %x\n", Mcb, (ULONG)Vbn, (ULONG)SectorCount);
 670
 671     KeAcquireGuardedMutex(Mcb->GuardedMutex);
 672     FsRtlRemoveBaseMcbEntry(&(Mcb->BaseMcb),
 673                             Vbn,
 674                             SectorCount);
 675     KeReleaseGuardedMutex(Mcb->GuardedMutex);
 676
 677         DPRINT("Done\n");
 678 }
 679
 680 /*
 681  * @implemented
 682  */
 683 VOID
 684 NTAPI
 685 FsRtlResetBaseMcb(IN PBASE_MCB Mcb)
 686 {
 687         PLARGE_MCB_MAPPING_ENTRY Element;
 688
 689         DPRINT("Reset MCB %x\n", Mcb);
 690         while (RtlNumberGenericTableElements(Mcb->Mapping) &&
 691                    (Element = (PLARGE_MCB_MAPPING_ENTRY)RtlGetElementGenericTable(Mcb->Mapping, 0)))
 692         {
 693                 DPRINT("Deleting %x\n", Element);
 694                 RtlDeleteElementGenericTable(Mcb->Mapping, Element);
 695         }
 696
 697         Mcb->PairCount = 0;
 698         Mcb->MaximumPairCount = 0;
 699         DPRINT("Done\n");
 700 }
 701
 702 /*
 703  * @implemented
 704  */
 705 VOID
 706 NTAPI
 707 FsRtlResetLargeMcb(IN PLARGE_MCB Mcb,
 708                    IN BOOLEAN SelfSynchronized)
 709 {
 710     if (!SelfSynchronized)
 711     {
 712         KeAcquireGuardedMutex(Mcb->GuardedMutex);
 713         }
 714
 715         FsRtlResetBaseMcb(&Mcb->BaseMcb);
 716
 717
 718     if (!SelfSynchronized)
 719     {
 720                 KeReleaseGuardedMutex(Mcb->GuardedMutex);
 721     }
 722 }
 723
 724 #define MCB_BUMP_NO_MORE 0
 725 #define MCB_BUMP_AGAIN   1
 726
 727 static ULONG NTAPI McbBump(PBASE_MCB Mcb, PLARGE_MCB_MAPPING_ENTRY FixedPart)
 728 {
 729         LARGE_MCB_MAPPING_ENTRY Reimagined;
 730         PLARGE_MCB_MAPPING_ENTRY Found = NULL;
 731
 732         DPRINT("McbBump %x (%x:%x)\n", Mcb, FixedPart->RunStartVbn.LowPart, FixedPart->SectorCount.LowPart);
 733
 734         Reimagined = *FixedPart;
 735         while ((Found = RtlLookupElementGenericTable(Mcb->Mapping, &Reimagined)))
 736         {
 737                 Reimagined = *Found;
 738                 Reimagined.RunStartVbn.QuadPart =
 739                         FixedPart->RunStartVbn.QuadPart + FixedPart->SectorCount.QuadPart;
 740                 DPRINT("Reimagined %x\n", Reimagined.RunStartVbn.LowPart);
 741         }
 742
 743         DPRINT("Found %x\n", Found);
 744         if (!Found) return MCB_BUMP_NO_MORE;
 745         DPRINT1
 746                 ("Moving %x-%x to %x because %x-%x overlaps\n",
 747                  Found->RunStartVbn.LowPart,
 748                  Found->RunStartVbn.LowPart + Found->SectorCount.QuadPart,
 749                  Reimagined.RunStartVbn.LowPart + Reimagined.SectorCount.LowPart,
 750                  Reimagined.RunStartVbn.LowPart,
 751                  Reimagined.RunStartVbn.LowPart + Reimagined.SectorCount.LowPart);
 752         Found->RunStartVbn.QuadPart = Reimagined.RunStartVbn.QuadPart + Reimagined.SectorCount.QuadPart;
 753         Found->StartingLbn.QuadPart = Reimagined.StartingLbn.QuadPart + Reimagined.SectorCount.QuadPart;
 754
 755         DPRINT("Again\n");
 756         return MCB_BUMP_AGAIN;
 757 }
 758
 759 /*
 760  * @unimplemented
 761  */
 762 BOOLEAN
 763 NTAPI
 764 FsRtlSplitBaseMcb(IN PBASE_MCB Mcb,
 765                   IN LONGLONG Vbn,
 766                   IN LONGLONG Amount)
 767 {
 768         ULONG Result;
 769         LARGE_MCB_MAPPING_ENTRY Node;
 770         PLARGE_MCB_MAPPING_ENTRY Existing = NULL;
 771
 772         Node.RunStartVbn.QuadPart = Vbn;
 773         Node.SectorCount.QuadPart = 0;
 774
 775         Existing = RtlLookupElementGenericTable(Mcb->Mapping, &Node);
 776
 777         if (Existing)
 778         {
 779                 // We're in the middle of a run
 780                 LARGE_MCB_MAPPING_ENTRY UpperPart;
 781                 LARGE_MCB_MAPPING_ENTRY LowerPart;
 782                 PLARGE_MCB_MAPPING_ENTRY InsertedUpper;
 783
 784                 UpperPart.RunStartVbn.QuadPart = Node.RunStartVbn.QuadPart + Amount;
 785                 UpperPart.SectorCount.QuadPart = Existing->RunStartVbn.QuadPart +
 786                         (Existing->SectorCount.QuadPart - Node.RunStartVbn.QuadPart);
 787                 UpperPart.StartingLbn.QuadPart = Existing->StartingLbn.QuadPart +
 788                         (Node.RunStartVbn.QuadPart - Existing->RunStartVbn.QuadPart);
 789                 LowerPart.RunStartVbn.QuadPart = Existing->RunStartVbn.QuadPart;
 790                 LowerPart.SectorCount.QuadPart = Node.RunStartVbn.QuadPart - Existing->RunStartVbn.QuadPart;
 791                 LowerPart.StartingLbn.QuadPart = Existing->StartingLbn.QuadPart;
 792
 793                 Node = UpperPart;
 794
 795                 DPRINT("Loop: %x\n", Node.RunStartVbn.LowPart);
 796                 while ((Result = McbBump(Mcb, &Node)) == MCB_BUMP_AGAIN)
 797                 {
 798                         DPRINT("Node: %x\n", Node.RunStartVbn.LowPart);
 799                 }
 800                 DPRINT("Done\n");
 801
 802                 if (Result == MCB_BUMP_NO_MORE)
 803                 {
 804                         Node = *Existing;
 805                         RemoveHeadList(&Existing->Sequence);
 806                         RtlDeleteElementGenericTable(Mcb->Mapping, Existing);
 807                         Mcb->PairCount--;
 808
 809                         // Adjust the element we found.
 810                         Existing->SectorCount = LowerPart.SectorCount;
 811
 812                         InsertedUpper = RtlInsertElementGenericTable
 813                                 (Mcb->Mapping, &UpperPart, sizeof(UpperPart), NULL);
 814                         if (!InsertedUpper)
 815                         {
 816                                 // Just make it like it was
 817                                 Existing->SectorCount = Node.SectorCount;
 818                                 return FALSE;
 819                         }
 820                         InsertHeadList(GET_LIST_HEAD(Mcb->Mapping), &InsertedUpper->Sequence);
 821                         Mcb->PairCount++;
 822                 }
 823                 else
 824                 {
 825                         Node.RunStartVbn.QuadPart = Vbn;
 826                         Node.SectorCount.QuadPart = Amount;
 827                         while ((Result = McbBump(Mcb, &Node)) == MCB_BUMP_AGAIN);
 828                         return Result == MCB_BUMP_NO_MORE;
 829                 }
 830         }
 831
 832         DPRINT("Done\n");
 833
 834         return TRUE;
 835 }
 836
 837 /*
 838  * @implemented
 839  */
 840 BOOLEAN
 841 NTAPI
 842 FsRtlSplitLargeMcb(IN PLARGE_MCB Mcb,
 843                    IN LONGLONG Vbn,
 844                    IN LONGLONG Amount)
 845 {
 846     BOOLEAN Result;
 847
 848         DPRINT("FsRtlSplitLargeMcb %x, Vbn %x, Amount %x\n", Mcb, (ULONG)Vbn, (ULONG)Amount);
 849
 850     KeAcquireGuardedMutex(Mcb->GuardedMutex);
 851     Result = FsRtlSplitBaseMcb(&(Mcb->BaseMcb),
 852                                Vbn,
 853                                Amount);
 854     KeReleaseGuardedMutex(Mcb->GuardedMutex);
 855
 856         DPRINT("Done %d\n", Result);
 857
 858     return Result;
 859 }
 860
 861 /*
 862  * @unimplemented
 863  */
 864 VOID
 865 NTAPI
 866 FsRtlTruncateBaseMcb(IN PBASE_MCB Mcb,
 867                      IN LONGLONG Vbn)
 868 {
 869         DPRINT("FsRtlTruncateBaseMcb(%x,%x)\n", Mcb, (ULONG)Vbn);
 870         if (!Vbn)
 871         {
 872                 DPRINT("Resetting\n");
 873                 FsRtlResetBaseMcb(Mcb);
 874         }
 875         else
 876         {
 877                 LARGE_MCB_MAPPING_ENTRY Truncate;
 878                 PLARGE_MCB_MAPPING_ENTRY Found;
 879                 Truncate.RunStartVbn.QuadPart = Vbn;
 880                 Truncate.SectorCount.QuadPart = (1ull<<62) - Truncate.RunStartVbn.QuadPart;
 881                 while ((Found = RtlLookupElementGenericTable(Mcb->Mapping, &Truncate)))
 882                 {
 883                         DPRINT("Deleting %x\n", Found);
 884                         RemoveEntryList(&Found->Sequence);
 885                         RtlDeleteElementGenericTable(Mcb->Mapping, Found);
 886                         Mcb->PairCount--;
 887                 }
 888         }
 889         DPRINT("Done\n");
 890 }
 891
 892 /*
 893  * @implemented
 894  */
 895 VOID
 896 NTAPI
 897 FsRtlTruncateLargeMcb(IN PLARGE_MCB Mcb,
 898                       IN LONGLONG Vbn)
 899 {
 900         DPRINT("FsRtlTruncateLargeMcb %x Vbn %x\n", Mcb, (ULONG)Vbn);
 901     KeAcquireGuardedMutex(Mcb->GuardedMutex);
 902     FsRtlTruncateBaseMcb(&(Mcb->BaseMcb),
 903                          Vbn);
 904     KeReleaseGuardedMutex(Mcb->GuardedMutex);
 905         DPRINT("Done\n");
 906 }
 907
 908 /*
 909  * @implemented
 910  */
 911 VOID
 912 NTAPI
 913 FsRtlUninitializeBaseMcb(IN PBASE_MCB Mcb)
 914 {
 915         DPRINT("FsRtlUninitializeBaseMcb(%x)\n", Mcb);
 916         FsRtlResetBaseMcb(Mcb);
 917
 918         DPRINT("Mcb->Mapping %x\n", Mcb->Mapping);
 919     if (Mcb->PoolType == PagedPool)
 920     {
 921                 DPRINT("Deallocate to lookaside list\n");
 922         ExFreeToPagedLookasideList(&FsRtlFirstMappingLookasideList,
 923                                    Mcb->Mapping);
 924     }
 925     else
 926     {
 927                 DPRINT("Deallocate\n");
 928         ExFreePoolWithTag(Mcb->Mapping, 'FSBC');
 929     }
 930         Mcb->Mapping = NULL;
 931         DPRINT("Done\n");
 932 }
 933
 934 /*
 935  * @implemented
 936  */
 937 VOID
 938 NTAPI
 939 FsRtlUninitializeLargeMcb(IN PLARGE_MCB Mcb)
 940 {
 941     if (Mcb->GuardedMutex)
 942     {
 943         ExFreeToNPagedLookasideList(&FsRtlFastMutexLookasideList,
 944                                     Mcb->GuardedMutex);
 945                 Mcb->GuardedMutex = NULL;
 946         FsRtlUninitializeBaseMcb(&(Mcb->BaseMcb));
 947     }
 948 }
 949
 950 // MCB
 951
 952 /*
 953  * @implemented
 954  */
 955 BOOLEAN
 956 NTAPI
 957 FsRtlAddMcbEntry(IN PMCB Mcb,
 958                  IN VBN Vbn,
 959                  IN LBN Lbn,
 960                  IN ULONG SectorCount)
 961 {
 962     /* Call the newer function */
 963     return FsRtlAddLargeMcbEntry(&Mcb->
 964                                  DummyFieldThatSizesThisStructureCorrectly,
 965                                  (LONGLONG)Vbn,
 966                                  (LONGLONG)Lbn,
 967                                  (LONGLONG)SectorCount);
 968 }
 969
 970 /*
 971  * @implemented
 972  */
 973 BOOLEAN
 974 NTAPI
 975 FsRtlGetNextMcbEntry(IN PMCB Mcb,
 976                      IN ULONG RunIndex,
 977                      OUT PVBN Vbn,
 978                      OUT PLBN Lbn,
 979                      OUT PULONG SectorCount)
 980 {
 981     BOOLEAN Return = FALSE;
 982     LONGLONG llVbn;
 983     LONGLONG llLbn;
 984     LONGLONG llSectorCount;
 985
 986     /* Call the Large version */
 987     Return = FsRtlGetNextLargeMcbEntry(
 988         &Mcb->DummyFieldThatSizesThisStructureCorrectly,
 989         RunIndex,
 990         &llVbn,
 991         &llLbn,
 992         &llSectorCount);
 993
 994     /* Return the lower 32 bits */
 995     *Vbn = (ULONG)llVbn;
 996     *Lbn = (ULONG)llLbn;
 997     *SectorCount = (ULONG)llSectorCount;
 998
 999     /* And return the original value */
1000     return Return;
1001 }
1002
1003 /*
1004  * @implemented
1005  */
1006 VOID
1007 NTAPI
1008 FsRtlInitializeMcb(IN PMCB Mcb,
1009                    IN POOL_TYPE PoolType)
1010 {
1011     /* Call the newer function */
1012     FsRtlInitializeLargeMcb(&Mcb->DummyFieldThatSizesThisStructureCorrectly,
1013                             PoolType);
1014 }
1015
1016 /*
1017  * @implemented
1018  */
1019 BOOLEAN
1020 NTAPI
1021 FsRtlLookupLastMcbEntry(IN PMCB Mcb,
1022                         OUT PVBN Vbn,
1023                         OUT PLBN Lbn)
1024 {
1025     BOOLEAN Return = FALSE;
1026     LONGLONG llVbn = 0;
1027     LONGLONG llLbn = 0;
1028
1029     /* Call the Large version */
1030     Return = FsRtlLookupLastLargeMcbEntry(
1031         &Mcb->DummyFieldThatSizesThisStructureCorrectly,
1032         &llVbn,
1033         &llLbn);
1034
1035     /* Return the lower 32-bits */
1036     *Vbn = (ULONG)llVbn;
1037     *Lbn = (ULONG)llLbn;
1038
1039     /* And return the original value */
1040     return Return;
1041 }
1042
1043 /*
1044  * @implemented
1045  */
1046 BOOLEAN
1047 NTAPI
1048 FsRtlLookupMcbEntry(IN PMCB Mcb,
1049                     IN VBN Vbn,
1050                     OUT PLBN Lbn,
1051                     OUT PULONG SectorCount OPTIONAL,
1052                     OUT PULONG Index)
1053 {
1054     BOOLEAN Return = FALSE;
1055     LONGLONG llLbn;
1056     LONGLONG llSectorCount;
1057
1058     /* Call the Large version */
1059     Return = FsRtlLookupLargeMcbEntry(&Mcb->
1060                                       DummyFieldThatSizesThisStructureCorrectly,
1061                                       (LONGLONG)Vbn,
1062                                       &llLbn,
1063                                       &llSectorCount,
1064                                       NULL,
1065                                       NULL,
1066                                       Index);
1067
1068     /* Return the lower 32-bits */
1069     *Lbn = (ULONG)llLbn;
1070     if (SectorCount) *SectorCount = (ULONG)llSectorCount;
1071
1072     /* And return the original value */
1073     return Return;
1074 }
1075
1076 /*
1077  * @implemented
1078  */
1079 ULONG
1080 NTAPI
1081 FsRtlNumberOfRunsInMcb(IN PMCB Mcb)
1082 {
1083     /* Call the newer function */
1084     return FsRtlNumberOfRunsInLargeMcb(
1085         &Mcb->DummyFieldThatSizesThisStructureCorrectly);
1086 }
1087
1088 /*
1089  * @implemented
1090  */
1091 VOID
1092 NTAPI
1093 FsRtlRemoveMcbEntry(IN PMCB Mcb,
1094                     IN VBN Vbn,
1095                     IN ULONG SectorCount)
1096 {
1097     /* Call the large function */
1098     FsRtlRemoveLargeMcbEntry(&Mcb->DummyFieldThatSizesThisStructureCorrectly,
1099                              (LONGLONG)Vbn,
1100                              (LONGLONG)SectorCount);
1101 }
1102
1103 /*
1104  * @implemented
1105  */
1106 VOID
1107 NTAPI
1108 FsRtlTruncateMcb(IN PMCB Mcb,
1109                  IN VBN  Vbn)
1110 {
1111     /* Call the newer function */
1112     FsRtlTruncateLargeMcb(&Mcb->DummyFieldThatSizesThisStructureCorrectly,
1113                           (LONGLONG)Vbn);
1114 }
1115
1116 /*
1117  * @implemented
1118  */
1119 VOID
1120 NTAPI
1121 FsRtlUninitializeMcb(IN PMCB Mcb)
1122 {
1123     /* Call the newer function */
1124     FsRtlUninitializeLargeMcb(&Mcb->DummyFieldThatSizesThisStructureCorrectly);
1125 }
1126