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 PVOID NTAPI McbMappingAllocate(PRTL_GENERIC_TABLE Table, CLONG Bytes)
  33 {
  34         PVOID Result;
  35         PBASE_MCB Mcb = (PBASE_MCB)Table->TableContext;
  36         Result = ExAllocatePoolWithTag(Mcb->PoolType, Bytes, 'LMCB');
  37         DPRINT("McbMappingAllocate(%d) => %p\n", Bytes, Result);
  38         return Result;
  39 }
  40
  41 static VOID NTAPI McbMappingFree(PRTL_GENERIC_TABLE Table, PVOID Buffer)
  42 {
  43         DPRINT("McbMappingFree(%p)\n", Buffer);
  44         ExFreePoolWithTag(Buffer, 'LMCB');
  45 }
  46
  47 static RTL_GENERIC_COMPARE_RESULTS NTAPI McbMappingCompare
  48 (RTL_GENERIC_TABLE Table, PVOID PtrA, PVOID PtrB)
  49 {
  50         PLARGE_MCB_MAPPING_ENTRY A = PtrA, B = PtrB;
  51         return
  52                 (A->RunStartVbn.QuadPart + A->SectorCount.QuadPart <
  53                  B->RunStartVbn.QuadPart) ? GenericLessThan :
  54                 (A->RunStartVbn.QuadPart >
  55                  B->RunStartVbn.QuadPart + B->SectorCount.QuadPart) ?
  56                 GenericGreaterThan : GenericEqual;
  57 }
  58
  59 /* PUBLIC FUNCTIONS **********************************************************/
  60
  61 /*
  62  * @implemented
  63  */
  64 BOOLEAN
  65 NTAPI
  66 FsRtlAddBaseMcbEntry(IN PBASE_MCB Mcb,
  67                      IN LONGLONG Vbn,
  68                      IN LONGLONG Lbn,
  69                      IN LONGLONG SectorCount)
  70 {
  71         LARGE_MCB_MAPPING_ENTRY Node;
  72         PLARGE_MCB_MAPPING_ENTRY Existing = NULL;
  73         BOOLEAN NewElement = FALSE;
  74
  75         Node.RunStartVbn.QuadPart = Vbn;
  76         Node.StartingLbn.QuadPart = Lbn;
  77         Node.SectorCount.QuadPart = SectorCount;
  78
  79         while (!NewElement)
  80         {
  81                 DPRINT("Inserting %x:%x\n", Node.RunStartVbn.LowPart, Node.SectorCount.LowPart);
  82                 Existing = RtlInsertElementGenericTable
  83                         (Mcb->Mapping, &Node, sizeof(Node), &NewElement);
  84                 DPRINT("Existing %x\n", Existing);
  85                 if (!Existing) break;
  86
  87                 DPRINT("NewElement %d\n", NewElement);
  88                 if (!NewElement)
  89                 {
  90                         // We merge the existing runs
  91                         LARGE_INTEGER StartVbn, FinalVbn;
  92                         DPRINT("Existing: %x:%x\n",
  93                                    Existing->RunStartVbn.LowPart, Node.SectorCount.LowPart);
  94                         if (Existing->RunStartVbn.QuadPart < Node.RunStartVbn.QuadPart)
  95                         {
  96                                 StartVbn = Existing->RunStartVbn;
  97                                 Node.StartingLbn = Existing->StartingLbn;
  98                         }
  99                         else
 100                         {
 101                                 StartVbn = Node.RunStartVbn;
 102                         }
 103                         DPRINT("StartVbn %x\n", StartVbn.LowPart);
 104                         if (Existing->RunStartVbn.QuadPart + Existing->SectorCount.QuadPart >
 105                                 Node.RunStartVbn.QuadPart + Node.SectorCount.QuadPart)
 106                         {
 107                                 FinalVbn.QuadPart =
 108                                         Existing->RunStartVbn.QuadPart + Existing->SectorCount.QuadPart;
 109                         }
 110                         else
 111                         {
 112                                 FinalVbn.QuadPart =
 113                                         Node.RunStartVbn.QuadPart + Node.SectorCount.QuadPart;
 114                         }
 115                         DPRINT("FinalVbn %x\n", FinalVbn.LowPart);
 116                         Node.RunStartVbn.QuadPart = StartVbn.QuadPart;
 117                         Node.SectorCount.QuadPart = FinalVbn.QuadPart - StartVbn.QuadPart;
 118                         RemoveHeadList(&Existing->Sequence);
 119                         RtlDeleteElementGenericTable(Mcb->Mapping, Existing);
 120                         Mcb->PairCount--;
 121                 }
 122                 else
 123                 {
 124                         DPRINT("Mapping added %x\n", Existing);
 125                         Mcb->MaximumPairCount++;
 126                         Mcb->PairCount++;
 127                         InsertHeadList(GET_LIST_HEAD(Mcb->Mapping), &Existing->Sequence);
 128                 }
 129         }
 130
 131         DPRINT("!!Existing %d\n", !!Existing);
 132         return !!Existing;
 133 }
 134
 135 /*
 136  * @implemented
 137  */
 138 BOOLEAN
 139 NTAPI
 140 FsRtlAddLargeMcbEntry(IN PLARGE_MCB Mcb,
 141                       IN LONGLONG Vbn,
 142                       IN LONGLONG Lbn,
 143                       IN LONGLONG SectorCount)
 144 {
 145     BOOLEAN Result;
 146
 147         DPRINT("Mcb %x Vbn %x Lbn %x SectorCount %x\n", Mcb, Vbn, Lbn, SectorCount);
 148
 149     KeAcquireGuardedMutex(Mcb->GuardedMutex);
 150     Result = FsRtlAddBaseMcbEntry(&(Mcb->BaseMcb),
 151                                   Vbn,
 152                                   Lbn,
 153                                   SectorCount);
 154     KeReleaseGuardedMutex(Mcb->GuardedMutex);
 155
 156         DPRINT("Done %d\n", Result);
 157
 158     return Result;
 159 }
 160
 161 /*
 162  * @unimplemented
 163  */
 164 BOOLEAN
 165 NTAPI
 166 FsRtlGetNextBaseMcbEntry(IN PBASE_MCB Mcb,
 167                          IN ULONG RunIndex,
 168                          OUT PLONGLONG Vbn,
 169                          OUT PLONGLONG Lbn,
 170                          OUT PLONGLONG SectorCount)
 171 {
 172         ULONG i = 0;
 173         BOOLEAN Result = FALSE;
 174         PLARGE_MCB_MAPPING_ENTRY Entry;
 175         for (Entry = (PLARGE_MCB_MAPPING_ENTRY)
 176                          RtlEnumerateGenericTable(Mcb->Mapping, TRUE);
 177                  Entry && i < RunIndex;
 178                  Entry = (PLARGE_MCB_MAPPING_ENTRY)
 179                          RtlEnumerateGenericTable(Mcb->Mapping, FALSE), i++);
 180         if (Entry)
 181         {
 182                 Result = TRUE;
 183                 if (Vbn)
 184                         *Vbn = Entry->RunStartVbn.QuadPart;
 185                 if (Lbn)
 186                         *Lbn = Entry->StartingLbn.QuadPart;
 187                 if (SectorCount)
 188                         *SectorCount = Entry->SectorCount.QuadPart;
 189         }
 190
 191         return Result;
 192 }
 193
 194 /*
 195  * @implemented
 196  */
 197 BOOLEAN
 198 NTAPI
 199 FsRtlGetNextLargeMcbEntry(IN PLARGE_MCB Mcb,
 200                           IN ULONG RunIndex,
 201                           OUT PLONGLONG Vbn,
 202                           OUT PLONGLONG Lbn,
 203                           OUT PLONGLONG SectorCount)
 204 {
 205     BOOLEAN Result;
 206
 207         DPRINT("FsRtlGetNextLargeMcbEntry Mcb %x RunIndex %x\n", Mcb, RunIndex);
 208
 209     KeAcquireGuardedMutex(Mcb->GuardedMutex);
 210     Result = FsRtlGetNextBaseMcbEntry(&(Mcb->BaseMcb),
 211                                       RunIndex,
 212                                       Vbn,
 213                                       Lbn,
 214                                       SectorCount);
 215     KeReleaseGuardedMutex(Mcb->GuardedMutex);
 216
 217         DPRINT("Done %d\n", Result);
 218
 219     return Result;
 220 }
 221
 222 /*
 223  * @implemented
 224  */
 225 VOID
 226 NTAPI
 227 FsRtlInitializeBaseMcb(IN PBASE_MCB Mcb,
 228                        IN POOL_TYPE PoolType)
 229 {
 230     Mcb->PairCount = 0;
 231
 232     if (PoolType == PagedPool)
 233     {
 234         Mcb->Mapping = ExAllocateFromPagedLookasideList(&FsRtlFirstMappingLookasideList);
 235     }
 236     else
 237     {
 238         Mcb->Mapping = ExAllocatePoolWithTag(PoolType | POOL_RAISE_IF_ALLOCATION_FAILURE,
 239                                                                                          sizeof(RTL_GENERIC_TABLE) + sizeof(LIST_ENTRY),
 240                                              'FSBC');
 241     }
 242
 243     Mcb->PoolType = PoolType;
 244     Mcb->MaximumPairCount = MAXIMUM_PAIR_COUNT;
 245         RtlInitializeGenericTable
 246                 (Mcb->Mapping,
 247                  (PRTL_GENERIC_COMPARE_ROUTINE)McbMappingCompare,
 248                  McbMappingAllocate,
 249                  McbMappingFree,
 250                  Mcb);
 251         InitializeListHead(GET_LIST_HEAD(Mcb->Mapping));
 252 }
 253
 254 /*
 255  * @implemented
 256  */
 257 VOID
 258 NTAPI
 259 FsRtlInitializeLargeMcb(IN PLARGE_MCB Mcb,
 260                         IN POOL_TYPE PoolType)
 261 {
 262     Mcb->GuardedMutex = ExAllocateFromNPagedLookasideList(&FsRtlFastMutexLookasideList);
 263
 264     KeInitializeGuardedMutex(Mcb->GuardedMutex);
 265
 266     _SEH2_TRY
 267     {
 268         FsRtlInitializeBaseMcb(&(Mcb->BaseMcb), PoolType);
 269     }
 270     _SEH2_EXCEPT(EXCEPTION_EXECUTE_HANDLER)
 271     {
 272         ExFreeToNPagedLookasideList(&FsRtlFastMutexLookasideList,
 273                                     Mcb->GuardedMutex);
 274         Mcb->GuardedMutex = NULL;
 275     }
 276     _SEH2_END;
 277 }
 278
 279 /*
 280  * @implemented
 281  */
 282 VOID
 283 NTAPI
 284 FsRtlInitializeLargeMcbs(VOID)
 285 {
 286     /* Initialize the list for the MCB */
 287     ExInitializePagedLookasideList(&FsRtlFirstMappingLookasideList,
 288                                    NULL,
 289                                    NULL,
 290                                    POOL_RAISE_IF_ALLOCATION_FAILURE,
 291                                                                    sizeof(RTL_GENERIC_TABLE) + sizeof(LIST_ENTRY),
 292                                    IFS_POOL_TAG,
 293                                    0); /* FIXME: Should be 4 */
 294
 295     /* Initialize the list for the guarded mutex */
 296     ExInitializeNPagedLookasideList(&FsRtlFastMutexLookasideList,
 297                                     NULL,
 298                                     NULL,
 299                                     POOL_RAISE_IF_ALLOCATION_FAILURE,
 300                                     sizeof(KGUARDED_MUTEX),
 301                                     IFS_POOL_TAG,
 302                                     0); /* FIXME: Should be 32 */
 303 }
 304
 305 /*
 306  * @unimplemented
 307  */
 308 BOOLEAN
 309 NTAPI
 310 FsRtlLookupBaseMcbEntry(IN PBASE_MCB Mcb,
 311                         IN LONGLONG Vbn,
 312                         OUT PLONGLONG Lbn OPTIONAL,
 313                         OUT PLONGLONG SectorCountFromLbn OPTIONAL,
 314                         OUT PLONGLONG StartingLbn OPTIONAL,
 315                         OUT PLONGLONG SectorCountFromStartingLbn OPTIONAL,
 316                         OUT PULONG Index OPTIONAL)
 317 {
 318         BOOLEAN Result = FALSE;
 319         LARGE_MCB_MAPPING_ENTRY ToLookup;
 320         PLARGE_MCB_MAPPING_ENTRY Entry;
 321
 322         ToLookup.RunStartVbn.QuadPart = Vbn;
 323         ToLookup.SectorCount.QuadPart = 1;
 324
 325         Entry = RtlLookupElementGenericTable(Mcb->Mapping, &ToLookup);
 326         if (!Entry)
 327         {
 328                 // Find out if we have a following entry.  The spec says we should return
 329                 // found with Lbn == -1 when we're beneath the largest map.
 330                 ToLookup.SectorCount.QuadPart = (1ull<<62) - ToLookup.RunStartVbn.QuadPart;
 331                 Entry = RtlLookupElementGenericTable(Mcb->Mapping, &ToLookup);
 332                 if (Entry)
 333                 {
 334                         Result = TRUE;
 335                         if (Lbn) *Lbn = ~0ull;
 336                 }
 337                 else
 338                 {
 339                         Result = FALSE;
 340                 }
 341         }
 342         else
 343         {
 344                 LARGE_INTEGER Offset;
 345                 Offset.QuadPart = Vbn - Entry->RunStartVbn.QuadPart;
 346                 Result = TRUE;
 347                 if (Lbn) *Lbn = Entry->StartingLbn.QuadPart + Offset.QuadPart;
 348                 if (SectorCountFromLbn) *SectorCountFromLbn = Entry->SectorCount.QuadPart - Offset.QuadPart;
 349                 if (StartingLbn) *StartingLbn = Entry->StartingLbn.QuadPart;
 350                 if (SectorCountFromStartingLbn) *SectorCountFromStartingLbn = Entry->SectorCount.QuadPart;
 351         }
 352
 353     return Result;
 354 }
 355
 356 /*
 357  * @implemented
 358  */
 359 BOOLEAN
 360 NTAPI
 361 FsRtlLookupLargeMcbEntry(IN PLARGE_MCB Mcb,
 362                          IN LONGLONG Vbn,
 363                          OUT PLONGLONG Lbn OPTIONAL,
 364                          OUT PLONGLONG SectorCountFromLbn OPTIONAL,
 365                          OUT PLONGLONG StartingLbn OPTIONAL,
 366                          OUT PLONGLONG SectorCountFromStartingLbn OPTIONAL,
 367                          OUT PULONG Index OPTIONAL)
 368 {
 369     BOOLEAN Result;
 370
 371         DPRINT("FsRtlLookupLargeMcbEntry Mcb %x Vbn %x\n", Mcb, (ULONG)Vbn);
 372
 373     KeAcquireGuardedMutex(Mcb->GuardedMutex);
 374     Result = FsRtlLookupBaseMcbEntry(&(Mcb->BaseMcb),
 375                                      Vbn,
 376                                      Lbn,
 377                                      SectorCountFromLbn,
 378                                      StartingLbn,
 379                                      SectorCountFromStartingLbn,
 380                                      Index);
 381     KeReleaseGuardedMutex(Mcb->GuardedMutex);
 382
 383         DPRINT("Done %d\n", Result);
 384
 385     return Result;
 386 }
 387
 388 /*
 389  * @unimplemented
 390  */
 391 BOOLEAN
 392 NTAPI
 393 FsRtlLookupLastBaseMcbEntryAndIndex(IN PBASE_MCB OpaqueMcb,
 394                                     IN OUT PLONGLONG LargeVbn,
 395                                     IN OUT PLONGLONG LargeLbn,
 396                                     IN OUT PULONG Index)
 397 {
 398         ULONG i = 0;
 399         BOOLEAN Result = FALSE;
 400         PLIST_ENTRY ListEntry;
 401         PLARGE_MCB_MAPPING_ENTRY Entry;
 402         PLARGE_MCB_MAPPING_ENTRY CountEntry;
 403
 404         ListEntry = GET_LIST_HEAD(OpaqueMcb->Mapping);
 405         if (!IsListEmpty(ListEntry))
 406         {
 407                 Entry = CONTAINING_RECORD(ListEntry->Flink, LARGE_MCB_MAPPING_ENTRY, Sequence);
 408                 Result = TRUE;
 409                 *LargeVbn = Entry->RunStartVbn.QuadPart;
 410                 *LargeLbn = Entry->StartingLbn.QuadPart;
 411
 412                 for (i = 0, CountEntry = RtlEnumerateGenericTable(OpaqueMcb->Mapping, TRUE);
 413                          CountEntry != Entry;
 414                          CountEntry = RtlEnumerateGenericTable(OpaqueMcb->Mapping, FALSE));
 415
 416                 *Index = i;
 417         }
 418
 419         return Result;
 420 }
 421
 422 /*
 423  * @implemented
 424  */
 425 BOOLEAN
 426 NTAPI
 427 FsRtlLookupLastLargeMcbEntryAndIndex(IN PLARGE_MCB OpaqueMcb,
 428                                      OUT PLONGLONG LargeVbn,
 429                                      OUT PLONGLONG LargeLbn,
 430                                      OUT PULONG Index)
 431 {
 432     BOOLEAN Result;
 433
 434         DPRINT("FsRtlLookupLastLargeMcbEntryAndIndex %x\n", OpaqueMcb);
 435
 436     KeAcquireGuardedMutex(OpaqueMcb->GuardedMutex);
 437     Result = FsRtlLookupLastBaseMcbEntryAndIndex(&(OpaqueMcb->BaseMcb),
 438                                                  LargeVbn,
 439                                                  LargeLbn,
 440                                                  Index);
 441     KeReleaseGuardedMutex(OpaqueMcb->GuardedMutex);
 442
 443         DPRINT("Done %d\n", Result);
 444
 445     return Result;
 446 }
 447
 448 /*
 449  * @unimplemented
 450  */
 451 BOOLEAN
 452 NTAPI
 453 FsRtlLookupLastBaseMcbEntry(IN PBASE_MCB Mcb,
 454                             OUT PLONGLONG Vbn,
 455                             OUT PLONGLONG Lbn)
 456 {
 457         BOOLEAN Result = FALSE;
 458         PLIST_ENTRY ListEntry;
 459         PLARGE_MCB_MAPPING_ENTRY Entry;
 460
 461         ListEntry = GET_LIST_HEAD(Mcb->Mapping);
 462         if (!IsListEmpty(ListEntry))
 463         {
 464                 Entry = CONTAINING_RECORD(ListEntry->Flink, LARGE_MCB_MAPPING_ENTRY, Sequence);
 465                 Result = TRUE;
 466                 *Vbn = Entry->RunStartVbn.QuadPart;
 467                 *Lbn = Entry->StartingLbn.QuadPart;
 468         }
 469
 470         return Result;
 471 }
 472
 473 /*
 474  * @implemented
 475  */
 476 BOOLEAN
 477 NTAPI
 478 FsRtlLookupLastLargeMcbEntry(IN PLARGE_MCB Mcb,
 479                              OUT PLONGLONG Vbn,
 480                              OUT PLONGLONG Lbn)
 481 {
 482     BOOLEAN Result;
 483
 484         DPRINT("FsRtlLookupLastLargeMcbEntry Mcb %x\n", Mcb);
 485
 486     KeAcquireGuardedMutex(Mcb->GuardedMutex);
 487     Result = FsRtlLookupLastBaseMcbEntry(&(Mcb->BaseMcb),
 488                                          Vbn,
 489                                          Lbn);
 490     KeReleaseGuardedMutex(Mcb->GuardedMutex);
 491
 492         DPRINT("Done %d\n", Result);
 493
 494     return Result;
 495 }
 496
 497 /*
 498  * @implemented
 499  */
 500 ULONG
 501 NTAPI
 502 FsRtlNumberOfRunsInBaseMcb(IN PBASE_MCB Mcb)
 503 {
 504     /* Return the count */
 505     return Mcb->PairCount;
 506 }
 507
 508 /*
 509  * @implemented
 510  */
 511 ULONG
 512 NTAPI
 513 FsRtlNumberOfRunsInLargeMcb(IN PLARGE_MCB Mcb)
 514 {
 515     ULONG NumberOfRuns;
 516
 517         DPRINT("FsRtlNumberOfRunsInLargeMcb Mcb %x\n", Mcb);
 518
 519     /* Read the number of runs while holding the MCB lock */
 520     KeAcquireGuardedMutex(Mcb->GuardedMutex);
 521     NumberOfRuns = Mcb->BaseMcb.PairCount;
 522     KeReleaseGuardedMutex(Mcb->GuardedMutex);
 523
 524         DPRINT("Done %d\n", NumberOfRuns);
 525
 526     /* Return the count */
 527     return NumberOfRuns;
 528 }
 529
 530 /*
 531  * @unimplemented
 532  */
 533 BOOLEAN
 534 NTAPI
 535 FsRtlRemoveBaseMcbEntry(IN PBASE_MCB Mcb,
 536                         IN LONGLONG Vbn,
 537                         IN LONGLONG SectorCount)
 538 {
 539         LARGE_MCB_MAPPING_ENTRY Node;
 540         PLARGE_MCB_MAPPING_ENTRY Element;
 541
 542         Node.RunStartVbn.QuadPart = Vbn;
 543         Node.SectorCount.QuadPart = SectorCount;
 544
 545         while ((Element = RtlLookupElementGenericTable(Mcb->Mapping, &Node)))
 546         {
 547                 // Must split
 548                 if (Element->RunStartVbn.QuadPart < Node.RunStartVbn.QuadPart &&
 549                         Element->SectorCount.QuadPart > Node.SectorCount.QuadPart)
 550                 {
 551                         LARGE_MCB_MAPPING_ENTRY Upper, Reinsert;
 552                         PLARGE_MCB_MAPPING_ENTRY Reinserted, Inserted;
 553                         LARGE_INTEGER StartHole = Node.RunStartVbn;
 554                         LARGE_INTEGER EndHole;
 555                         EndHole.QuadPart = Node.RunStartVbn.QuadPart + Node.SectorCount.QuadPart;
 556                         Upper.RunStartVbn.QuadPart = EndHole.QuadPart;
 557                         Upper.StartingLbn.QuadPart =
 558                                 Element->StartingLbn.QuadPart +
 559                                 EndHole.QuadPart -
 560                                 Element->RunStartVbn.QuadPart;
 561                         Upper.SectorCount.QuadPart =
 562                                 Element->SectorCount.QuadPart -
 563                                 (EndHole.QuadPart - Element->RunStartVbn.QuadPart);
 564                         Reinsert = *Element;
 565                         Reinsert.SectorCount.QuadPart =
 566                                 Element->RunStartVbn.QuadPart - StartHole.QuadPart;
 567                         RemoveEntryList(&Element->Sequence);
 568                         RtlDeleteElementGenericTable(Mcb->Mapping, Element);
 569                         Mcb->PairCount--;
 570
 571                         Reinserted = RtlInsertElementGenericTable
 572                                 (Mcb->Mapping, &Reinsert, sizeof(Reinsert), NULL);
 573                         InsertHeadList(GET_LIST_HEAD(Mcb->Mapping), &Reinserted->Sequence);
 574                         Mcb->PairCount++;
 575
 576                         Inserted = RtlInsertElementGenericTable
 577                                 (Mcb->Mapping, &Upper, sizeof(Upper), NULL);
 578                         InsertHeadList(GET_LIST_HEAD(Mcb->Mapping), &Inserted->Sequence);
 579                         Mcb->PairCount++;
 580                 }
 581                 else if (Element->RunStartVbn.QuadPart < Node.RunStartVbn.QuadPart)
 582                 {
 583                         LARGE_MCB_MAPPING_ENTRY NewElement;
 584                         PLARGE_MCB_MAPPING_ENTRY Reinserted;
 585                         LARGE_INTEGER StartHole = Node.RunStartVbn;
 586                         NewElement.RunStartVbn = Element->RunStartVbn;
 587                         NewElement.StartingLbn = Element->StartingLbn;
 588                         NewElement.SectorCount.QuadPart = StartHole.QuadPart - Element->StartingLbn.QuadPart;
 589
 590                         RemoveEntryList(&Element->Sequence);
 591                         RtlDeleteElementGenericTable(Mcb->Mapping, Element);
 592                         Mcb->PairCount--;
 593
 594                         Reinserted = RtlInsertElementGenericTable
 595                                 (Mcb->Mapping, &NewElement, sizeof(NewElement), NULL);
 596                         InsertHeadList(GET_LIST_HEAD(Mcb->Mapping), &Reinserted->Sequence);
 597                         Mcb->PairCount++;
 598                 }
 599                 else
 600                 {
 601                         LARGE_MCB_MAPPING_ENTRY NewElement;
 602                         PLARGE_MCB_MAPPING_ENTRY Reinserted;
 603                         LARGE_INTEGER EndHole = Element->RunStartVbn;
 604                         LARGE_INTEGER EndRun;
 605                         EndRun.QuadPart = Element->RunStartVbn.QuadPart + Element->SectorCount.QuadPart;
 606                         NewElement.RunStartVbn = EndHole;
 607                         NewElement.StartingLbn.QuadPart = Element->StartingLbn.QuadPart +
 608                                 (EndHole.QuadPart - Element->RunStartVbn.QuadPart);
 609                         NewElement.SectorCount.QuadPart = EndRun.QuadPart - EndHole.QuadPart;
 610
 611                         RemoveEntryList(&Element->Sequence);
 612                         RtlDeleteElementGenericTable(Mcb->Mapping, Element);
 613                         Mcb->PairCount--;
 614
 615                         Reinserted = RtlInsertElementGenericTable
 616                                 (Mcb->Mapping, &NewElement, sizeof(NewElement), NULL);
 617                         InsertHeadList(GET_LIST_HEAD(Mcb->Mapping), &Reinserted->Sequence);
 618                         Mcb->PairCount++;
 619                 }
 620         }
 621
 622         return TRUE;
 623 }
 624
 625 /*
 626  * @implemented
 627  */
 628 VOID
 629 NTAPI
 630 FsRtlRemoveLargeMcbEntry(IN PLARGE_MCB Mcb,
 631                          IN LONGLONG Vbn,
 632                          IN LONGLONG SectorCount)
 633 {
 634         DPRINT("FsRtlRemoveLargeMcbEntry Mcb %x, Vbn %x, SectorCount %x\n", Mcb, (ULONG)Vbn, (ULONG)SectorCount);
 635
 636     KeAcquireGuardedMutex(Mcb->GuardedMutex);
 637     FsRtlRemoveBaseMcbEntry(&(Mcb->BaseMcb),
 638                             Vbn,
 639                             SectorCount);
 640     KeReleaseGuardedMutex(Mcb->GuardedMutex);
 641
 642         DPRINT("Done\n");
 643 }
 644
 645 /*
 646  * @implemented
 647  */
 648 VOID
 649 NTAPI
 650 FsRtlResetBaseMcb(IN PBASE_MCB Mcb)
 651 {
 652         PLARGE_MCB_MAPPING_ENTRY Element;
 653
 654         while (RtlNumberGenericTableElements(Mcb->Mapping) &&
 655                    (Element = (PLARGE_MCB_MAPPING_ENTRY)RtlGetElementGenericTable(Mcb->Mapping, 0)))
 656         {
 657                 RtlDeleteElementGenericTable(Mcb->Mapping, Element);
 658         }
 659
 660         Mcb->PairCount = 0;
 661         Mcb->MaximumPairCount = 0;
 662 }
 663
 664 /*
 665  * @implemented
 666  */
 667 VOID
 668 NTAPI
 669 FsRtlResetLargeMcb(IN PLARGE_MCB Mcb,
 670                    IN BOOLEAN SelfSynchronized)
 671 {
 672     if (!SelfSynchronized)
 673     {
 674         KeAcquireGuardedMutex(Mcb->GuardedMutex);
 675         }
 676
 677         FsRtlResetBaseMcb(&Mcb->BaseMcb);
 678
 679
 680     if (!SelfSynchronized)
 681     {
 682                 KeReleaseGuardedMutex(Mcb->GuardedMutex);
 683     }
 684 }
 685
 686 #define MCB_BUMP_NO_MORE 0
 687 #define MCB_BUMP_AGAIN   1
 688
 689 static ULONG NTAPI McbBump(PBASE_MCB Mcb, PLARGE_MCB_MAPPING_ENTRY FixedPart)
 690 {
 691         LARGE_MCB_MAPPING_ENTRY Reimagined;
 692         PLARGE_MCB_MAPPING_ENTRY Found = NULL;
 693
 694         DPRINT("McbBump %x (%x:%x)\n", Mcb, FixedPart->RunStartVbn.LowPart, FixedPart->SectorCount.LowPart);
 695
 696         Reimagined = *FixedPart;
 697         while ((Found = RtlLookupElementGenericTable(Mcb->Mapping, &Reimagined)))
 698         {
 699                 Reimagined = *Found;
 700                 Reimagined.RunStartVbn.QuadPart =
 701                         FixedPart->RunStartVbn.QuadPart + FixedPart->SectorCount.QuadPart;
 702                 DPRINT("Reimagined %x\n", Reimagined.RunStartVbn.LowPart);
 703         }
 704
 705         DPRINT("Found %x\n", Found);
 706         if (!Found) return MCB_BUMP_NO_MORE;
 707         DPRINT1
 708                 ("Moving %x-%x to %x because %x-%x overlaps\n",
 709                  Found->RunStartVbn.LowPart,
 710                  Found->RunStartVbn.LowPart + Found->SectorCount.QuadPart,
 711                  Reimagined.RunStartVbn.LowPart + Reimagined.SectorCount.LowPart,
 712                  Reimagined.RunStartVbn.LowPart,
 713                  Reimagined.RunStartVbn.LowPart + Reimagined.SectorCount.LowPart);
 714         Found->RunStartVbn.QuadPart = Reimagined.RunStartVbn.QuadPart + Reimagined.SectorCount.QuadPart;
 715         Found->StartingLbn.QuadPart = Reimagined.StartingLbn.QuadPart + Reimagined.SectorCount.QuadPart;
 716
 717         DPRINT("Again\n");
 718         return MCB_BUMP_AGAIN;
 719 }
 720
 721 /*
 722  * @unimplemented
 723  */
 724 BOOLEAN
 725 NTAPI
 726 FsRtlSplitBaseMcb(IN PBASE_MCB Mcb,
 727                   IN LONGLONG Vbn,
 728                   IN LONGLONG Amount)
 729 {
 730         ULONG Result;
 731         LARGE_MCB_MAPPING_ENTRY Node;
 732         PLARGE_MCB_MAPPING_ENTRY Existing = NULL;
 733
 734         Node.RunStartVbn.QuadPart = Vbn;
 735         Node.SectorCount.QuadPart = 0;
 736
 737         Existing = RtlLookupElementGenericTable(Mcb->Mapping, &Node);
 738
 739         if (Existing)
 740         {
 741                 // We're in the middle of a run
 742                 LARGE_MCB_MAPPING_ENTRY UpperPart;
 743                 LARGE_MCB_MAPPING_ENTRY LowerPart;
 744                 PLARGE_MCB_MAPPING_ENTRY InsertedUpper;
 745
 746                 UpperPart.RunStartVbn.QuadPart = Node.RunStartVbn.QuadPart + Amount;
 747                 UpperPart.SectorCount.QuadPart = Existing->RunStartVbn.QuadPart +
 748                         (Existing->SectorCount.QuadPart - Node.RunStartVbn.QuadPart);
 749                 UpperPart.StartingLbn.QuadPart = Existing->StartingLbn.QuadPart +
 750                         (Node.RunStartVbn.QuadPart - Existing->RunStartVbn.QuadPart);
 751                 LowerPart.RunStartVbn.QuadPart = Existing->RunStartVbn.QuadPart;
 752                 LowerPart.SectorCount.QuadPart = Node.RunStartVbn.QuadPart - Existing->RunStartVbn.QuadPart;
 753                 LowerPart.StartingLbn.QuadPart = Existing->StartingLbn.QuadPart;
 754
 755                 Node = UpperPart;
 756
 757                 DPRINT("Loop: %x\n", Node.RunStartVbn.LowPart);
 758                 while ((Result = McbBump(Mcb, &Node)) == MCB_BUMP_AGAIN)
 759                 {
 760                         DPRINT("Node: %x\n", Node.RunStartVbn.LowPart);
 761                 }
 762                 DPRINT("Done\n");
 763
 764                 if (Result == MCB_BUMP_NO_MORE)
 765                 {
 766                         Node = *Existing;
 767                         RemoveHeadList(&Existing->Sequence);
 768                         RtlDeleteElementGenericTable(Mcb->Mapping, Existing);
 769                         Mcb->PairCount--;
 770
 771                         // Adjust the element we found.
 772                         Existing->SectorCount = LowerPart.SectorCount;
 773
 774                         InsertedUpper = RtlInsertElementGenericTable
 775                                 (Mcb->Mapping, &UpperPart, sizeof(UpperPart), NULL);
 776                         if (!InsertedUpper)
 777                         {
 778                                 // Just make it like it was
 779                                 Existing->SectorCount = Node.SectorCount;
 780                                 return FALSE;
 781                         }
 782                         InsertHeadList(GET_LIST_HEAD(Mcb->Mapping), &InsertedUpper->Sequence);
 783                         Mcb->PairCount++;
 784                 }
 785                 else
 786                 {
 787                         Node.RunStartVbn.QuadPart = Vbn;
 788                         Node.SectorCount.QuadPart = Amount;
 789                         while ((Result = McbBump(Mcb, &Node)) == MCB_BUMP_AGAIN);
 790                         return Result == MCB_BUMP_NO_MORE;
 791                 }
 792         }
 793
 794         DPRINT("Done\n");
 795
 796         return TRUE;
 797 }
 798
 799 /*
 800  * @implemented
 801  */
 802 BOOLEAN
 803 NTAPI
 804 FsRtlSplitLargeMcb(IN PLARGE_MCB Mcb,
 805                    IN LONGLONG Vbn,
 806                    IN LONGLONG Amount)
 807 {
 808     BOOLEAN Result;
 809
 810         DPRINT("FsRtlSplitLargeMcb %x, Vbn %x, Amount %x\n", Mcb, (ULONG)Vbn, (ULONG)Amount);
 811
 812     KeAcquireGuardedMutex(Mcb->GuardedMutex);
 813     Result = FsRtlSplitBaseMcb(&(Mcb->BaseMcb),
 814                                Vbn,
 815                                Amount);
 816     KeReleaseGuardedMutex(Mcb->GuardedMutex);
 817
 818         DPRINT("Done %d\n", Result);
 819
 820     return Result;
 821 }
 822
 823 /*
 824  * @unimplemented
 825  */
 826 VOID
 827 NTAPI
 828 FsRtlTruncateBaseMcb(IN PBASE_MCB Mcb,
 829                      IN LONGLONG Vbn)
 830 {
 831         if (!Vbn)
 832         {
 833                 FsRtlResetBaseMcb(Mcb);
 834         }
 835         else
 836         {
 837                 LARGE_MCB_MAPPING_ENTRY Truncate;
 838                 PLARGE_MCB_MAPPING_ENTRY Found;
 839                 Truncate.RunStartVbn.QuadPart = Vbn;
 840                 Truncate.SectorCount.QuadPart = (1ull<<62) - Truncate.RunStartVbn.QuadPart;
 841                 while ((Found = RtlLookupElementGenericTable(Mcb->Mapping, &Truncate)))
 842                 {
 843                         RemoveEntryList(&Found->Sequence);
 844                         RtlDeleteElementGenericTable(Mcb->Mapping, Found);
 845                         Mcb->PairCount--;
 846                 }
 847         }
 848 }
 849
 850 /*
 851  * @implemented
 852  */
 853 VOID
 854 NTAPI
 855 FsRtlTruncateLargeMcb(IN PLARGE_MCB Mcb,
 856                       IN LONGLONG Vbn)
 857 {
 858         DPRINT("FsRtlTruncateLargeMcb %x Vbn %x\n", Mcb, (ULONG)Vbn);
 859     KeAcquireGuardedMutex(Mcb->GuardedMutex);
 860     FsRtlTruncateBaseMcb(&(Mcb->BaseMcb),
 861                          Vbn);
 862     KeReleaseGuardedMutex(Mcb->GuardedMutex);
 863         DPRINT("Done\n");
 864 }
 865
 866 /*
 867  * @implemented
 868  */
 869 VOID
 870 NTAPI
 871 FsRtlUninitializeBaseMcb(IN PBASE_MCB Mcb)
 872 {
 873         FsRtlResetBaseMcb(Mcb);
 874
 875     if ((Mcb->PoolType == PagedPool) && (Mcb->MaximumPairCount == MAXIMUM_PAIR_COUNT))
 876     {
 877         ExFreeToPagedLookasideList(&FsRtlFirstMappingLookasideList,
 878                                    Mcb->Mapping);
 879     }
 880     else
 881     {
 882         ExFreePoolWithTag(Mcb->Mapping, 'FSBC');
 883     }
 884 }
 885
 886 /*
 887  * @implemented
 888  */
 889 VOID
 890 NTAPI
 891 FsRtlUninitializeLargeMcb(IN PLARGE_MCB Mcb)
 892 {
 893     if (Mcb->GuardedMutex)
 894     {
 895         ExFreeToNPagedLookasideList(&FsRtlFastMutexLookasideList,
 896                                     Mcb->GuardedMutex);
 897         FsRtlUninitializeBaseMcb(&(Mcb->BaseMcb));
 898     }
 899 }
 900