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