2 * PROJECT: ReactOS Kernel
3 * LICENSE: GPL v2 - See COPYING in the top level directory
4 * FILE: ntoskrnl/fsrtl/largemcb.c
5 * PURPOSE: Large Mapped Control Block (MCB) support for File System Drivers
6 * PROGRAMMERS: Aleksey Bragin <aleksey@reactos.org>
7 * Jan Kratochvil <project-captive@jankratochvil.net>
11 /* INCLUDES ******************************************************************/
17 #define MIN(x,y) (((x)<(y))?(x):(y))
18 #define MAX(x,y) (((x)>(y))?(x):(y))
20 /* GLOBALS *******************************************************************/
22 PAGED_LOOKASIDE_LIST FsRtlFirstMappingLookasideList
;
23 NPAGED_LOOKASIDE_LIST FsRtlFastMutexLookasideList
;
25 /* We use only real 'mapping' runs; we do not store 'holes' to our GTree. */
26 typedef struct _LARGE_MCB_MAPPING_ENTRY
// run
28 LARGE_INTEGER RunStartVbn
;
29 LARGE_INTEGER RunEndVbn
; /* RunStartVbn+SectorCount; that means +1 after the last sector */
30 LARGE_INTEGER StartingLbn
; /* Lbn of 'RunStartVbn' */
31 } LARGE_MCB_MAPPING_ENTRY
, *PLARGE_MCB_MAPPING_ENTRY
;
33 typedef struct _LARGE_MCB_MAPPING
// mcb_priv
35 RTL_GENERIC_TABLE Table
;
36 } LARGE_MCB_MAPPING
, *PLARGE_MCB_MAPPING
;
38 typedef struct _BASE_MCB_INTERNAL
{
39 ULONG MaximumPairCount
;
43 PLARGE_MCB_MAPPING Mapping
;
44 } BASE_MCB_INTERNAL
, *PBASE_MCB_INTERNAL
;
47 static LARGE_MCB_MAPPING_ENTRY StaticRunBelow0 = {
54 static PVOID NTAPI
McbMappingAllocate(PRTL_GENERIC_TABLE Table
, CLONG Bytes
)
57 PBASE_MCB Mcb
= (PBASE_MCB
)Table
->TableContext
;
58 Result
= ExAllocatePoolWithTag(Mcb
->PoolType
, Bytes
, 'LMCB');
59 DPRINT("McbMappingAllocate(%lu) => %p\n", Bytes
, Result
);
63 static VOID NTAPI
McbMappingFree(PRTL_GENERIC_TABLE Table
, PVOID Buffer
)
65 DPRINT("McbMappingFree(%p)\n", Buffer
);
66 ExFreePoolWithTag(Buffer
, 'LMCB');
70 RTL_GENERIC_COMPARE_RESULTS
72 McbMappingCompare(PRTL_GENERIC_TABLE Table
,
76 PLARGE_MCB_MAPPING_ENTRY A
= PtrA
, B
= PtrB
;
77 RTL_GENERIC_COMPARE_RESULTS Res
;
82 if (A
->RunStartVbn
.QuadPart
== B
->RunStartVbn
.QuadPart
&& A
->RunEndVbn
.QuadPart
== B
->RunEndVbn
.QuadPart
)
84 else if (A
->RunEndVbn
.QuadPart
<= B
->RunStartVbn
.QuadPart
)
85 Res
= GenericLessThan
;
86 else if (A
->RunEndVbn
.QuadPart
>= B
->RunStartVbn
.QuadPart
)
87 Res
= GenericGreaterThan
;
97 static RTL_GENERIC_COMPARE_RESULTS NTAPI
McbMappingIntersectCompare(PRTL_GENERIC_TABLE Table
, PVOID PtrA
, PVOID PtrB
)
99 PLARGE_MCB_MAPPING_ENTRY A
= PtrA
, B
= PtrB
;
100 RTL_GENERIC_COMPARE_RESULTS Res
;
102 if (A
->RunStartVbn
.QuadPart
<= B
->RunStartVbn
.QuadPart
&& A
->RunEndVbn
.QuadPart
> B
->RunStartVbn
.QuadPart
)
104 else if (A
->RunStartVbn
.QuadPart
>= B
->RunStartVbn
.QuadPart
&& B
->RunEndVbn
.QuadPart
> A
->RunStartVbn
.QuadPart
)
106 else if (A
->RunStartVbn
.QuadPart
< B
->RunStartVbn
.QuadPart
)
107 Res
= GenericLessThan
;
108 else if (A
->RunStartVbn
.QuadPart
> B
->RunStartVbn
.QuadPart
)
109 Res
= GenericGreaterThan
;
117 /* PUBLIC FUNCTIONS **********************************************************/
121 * @Mcb: #PLARGE_MCB initialized by FsRtlInitializeLargeMcb().
122 * %NULL value is forbidden.
123 * @Vbn: Starting virtual block number of the wished range.
124 * @Lbn: Starting logical block number of the wished range.
125 * @SectorCount: Length of the wished range.
126 * Value less or equal to %0 is forbidden; FIXME: Is the reject of %0 W32 compliant?
128 * Adds the specified range @Vbn ... @Vbn+@SectorCount-1 to @Mcb.
129 * Any mappings previously in this range are deleted first.
131 * Returns: %TRUE if successful.
135 FsRtlAddBaseMcbEntry(IN PBASE_MCB OpaqueMcb
,
138 IN LONGLONG SectorCount
)
140 BOOLEAN Result
= TRUE
;
142 PBASE_MCB_INTERNAL Mcb
= (PBASE_MCB_INTERNAL
)OpaqueMcb
;
143 LARGE_MCB_MAPPING_ENTRY Node
, NeedleRun
;
144 PLARGE_MCB_MAPPING_ENTRY LowerRun
, HigherRun
;
148 DPRINT("FsRtlAddBaseMcbEntry(%p, %I64d, %I64d, %I64d)\n", OpaqueMcb
, Vbn
, Lbn
, SectorCount
);
156 if (SectorCount
<= 0)
162 IntResult
= FsRtlLookupBaseMcbEntry(OpaqueMcb
, Vbn
, &IntLbn
, NULL
, NULL
, NULL
, NULL
);
165 if (IntLbn
!= -1 && IntLbn
!= Lbn
)
172 /* clean any possible previous entries in our range */
173 FsRtlRemoveBaseMcbEntry(OpaqueMcb
, Vbn
, SectorCount
);
175 // We need to map [Vbn, Vbn+SectorCount) to [Lbn, Lbn+SectorCount),
176 // taking in account the fact that we need to merge these runs if
177 // they are adjacent or overlap, but fail if new run fully fits into another run
179 /* initially we think we will be inserted as a separate run */
180 Node
.RunStartVbn
.QuadPart
= Vbn
;
181 Node
.RunEndVbn
.QuadPart
= Vbn
+ SectorCount
;
182 Node
.StartingLbn
.QuadPart
= Lbn
;
184 /* optionally merge with lower run */
185 NeedleRun
.RunStartVbn
.QuadPart
= Node
.RunStartVbn
.QuadPart
- 1;
186 NeedleRun
.RunEndVbn
.QuadPart
= NeedleRun
.RunStartVbn
.QuadPart
+ 1;
187 NeedleRun
.StartingLbn
.QuadPart
= ~0ULL;
188 Mcb
->Mapping
->Table
.CompareRoutine
= McbMappingIntersectCompare
;
189 if ((LowerRun
= RtlLookupElementGenericTable(&Mcb
->Mapping
->Table
, &NeedleRun
)) &&
190 (LowerRun
->StartingLbn
.QuadPart
+ (LowerRun
->RunEndVbn
.QuadPart
- LowerRun
->RunStartVbn
.QuadPart
) == Node
.StartingLbn
.QuadPart
))
192 ASSERT(LowerRun
->RunEndVbn
.QuadPart
== Node
.RunStartVbn
.QuadPart
);
193 Node
.RunStartVbn
.QuadPart
= LowerRun
->RunStartVbn
.QuadPart
;
194 Node
.StartingLbn
.QuadPart
= LowerRun
->StartingLbn
.QuadPart
;
195 Mcb
->Mapping
->Table
.CompareRoutine
= McbMappingCompare
;
196 RtlDeleteElementGenericTable(&Mcb
->Mapping
->Table
, LowerRun
);
198 DPRINT("Intersecting lower run found (%I64d,%I64d) Lbn: %I64d\n", LowerRun
->RunStartVbn
.QuadPart
, LowerRun
->RunEndVbn
.QuadPart
, LowerRun
->StartingLbn
.QuadPart
);
201 /* optionally merge with higher run */
202 NeedleRun
.RunStartVbn
.QuadPart
= Node
.RunEndVbn
.QuadPart
;
203 NeedleRun
.RunEndVbn
.QuadPart
= NeedleRun
.RunStartVbn
.QuadPart
+ 1;
204 Mcb
->Mapping
->Table
.CompareRoutine
= McbMappingIntersectCompare
;
205 if ((HigherRun
= RtlLookupElementGenericTable(&Mcb
->Mapping
->Table
, &NeedleRun
)) &&
206 (Node
.StartingLbn
.QuadPart
<= HigherRun
->StartingLbn
.QuadPart
))
208 ASSERT(HigherRun
->RunStartVbn
.QuadPart
== Node
.RunEndVbn
.QuadPart
);
209 Node
.RunEndVbn
.QuadPart
= HigherRun
->RunEndVbn
.QuadPart
;
210 Mcb
->Mapping
->Table
.CompareRoutine
= McbMappingCompare
;
211 RtlDeleteElementGenericTable(&Mcb
->Mapping
->Table
, HigherRun
);
213 DPRINT("Intersecting higher run found (%I64d,%I64d) Lbn: %I64d\n", HigherRun
->RunStartVbn
.QuadPart
, HigherRun
->RunEndVbn
.QuadPart
, HigherRun
->StartingLbn
.QuadPart
);
215 Mcb
->Mapping
->Table
.CompareRoutine
= McbMappingCompare
;
217 /* finally insert the resulting run */
218 RtlInsertElementGenericTable(&Mcb
->Mapping
->Table
, &Node
, sizeof(Node
), &NewElement
);
222 // NB: Two consecutive runs can only be merged, if actual LBNs also match!
225 Existing->RunStartVbn
233 Existing->RunStartVbn
241 Existing->RunStartVbn
249 Existing->RunStartVbn
257 Situation with holes:
258 1. Holes at both ends
259 2. Hole at the right, new run merged with the previous run
260 3. Hole at the right, new run is not merged with the previous run
261 4. Hole at the left, new run merged with the next run
262 5. Hole at the left, new run is not merged with the next run
263 6. No holes, exact fit to merge with both previous and next runs
264 7. No holes, merges only with the next run
265 8. No holes, merges only with the previous run
266 9. No holes, does not merge with next or prev runs
269 Overwriting existing mapping is not possible and results in FALSE being returned
273 DPRINT("FsRtlAddBaseMcbEntry(%p, %I64d, %I64d, %I64d) = %d\n", Mcb
, Vbn
, Lbn
, SectorCount
, Result
);
282 FsRtlAddLargeMcbEntry(IN PLARGE_MCB Mcb
,
285 IN LONGLONG SectorCount
)
289 DPRINT("FsRtlAddLargeMcbEntry(%p, %I64d, %I64d, %I64d)\n", Mcb
, Vbn
, Lbn
, SectorCount
);
291 KeAcquireGuardedMutex(Mcb
->GuardedMutex
);
292 Result
= FsRtlAddBaseMcbEntry(&(Mcb
->BaseMcb
),
296 KeReleaseGuardedMutex(Mcb
->GuardedMutex
);
298 DPRINT("FsRtlAddLargeMcbEntry(%p, %I64d, %I64d, %I64d) = %d\n", Mcb
, Vbn
, Lbn
, SectorCount
, Result
);
305 * @Mcb: #PLARGE_MCB initialized by FsRtlInitializeLargeMcb().
306 * %NULL value is forbidden.
307 * @RunIndex: Requested range index to retrieve.
308 * @Vbn: Returns the starting virtual block number of the wished range.
309 * %NULL pointer is forbidden.
310 * @Lbn: Returns the starting logical block number of the wished range (or -1 if it is a hole).
311 * %NULL pointer is forbidden.
312 * @SectorCount: Returns the length of the wished range.
313 * %NULL pointer is forbidden.
314 * Value less or equal to %0 is forbidden; FIXME: Is the reject of %0 W32 compliant?
316 * Retrieves the parameters of the specified run with index @RunIndex.
318 * Mapping %0 always starts at virtual block %0, either as 'hole' or as 'real' mapping.
319 * libcaptive does not store 'hole' information to its #GTree.
320 * Last run is always a 'real' run. 'hole' runs appear as mapping to constant @Lbn value %-1.
322 * Returns: %TRUE if successful.
326 FsRtlGetNextBaseMcbEntry(IN PBASE_MCB OpaqueMcb
,
330 OUT PLONGLONG SectorCount
)
332 BOOLEAN Result
= FALSE
;
333 PBASE_MCB_INTERNAL Mcb
= (PBASE_MCB_INTERNAL
)OpaqueMcb
;
334 PLARGE_MCB_MAPPING_ENTRY Run
= NULL
;
335 ULONG CurrentIndex
= 0;
336 ULONGLONG LastVbn
= 0;
337 ULONGLONG LastSectorCount
= 0;
340 for (Run
= (PLARGE_MCB_MAPPING_ENTRY
)RtlEnumerateGenericTable(&Mcb
->Mapping
->Table
, TRUE
);
342 Run
= (PLARGE_MCB_MAPPING_ENTRY
)RtlEnumerateGenericTable(&Mcb
->Mapping
->Table
, FALSE
))
344 // is the current index a hole?
345 if (Run
->RunStartVbn
.QuadPart
> (LastVbn
+ LastSectorCount
))
347 // Is this the index we're looking for?
348 if (RunIndex
== CurrentIndex
)
350 *Vbn
= LastVbn
+ LastSectorCount
;
352 *SectorCount
= Run
->RunStartVbn
.QuadPart
- *Vbn
;
361 if (RunIndex
== CurrentIndex
)
363 *Vbn
= Run
->RunStartVbn
.QuadPart
;
364 *Lbn
= Run
->StartingLbn
.QuadPart
;
365 *SectorCount
= Run
->RunEndVbn
.QuadPart
- Run
->RunStartVbn
.QuadPart
;
372 LastVbn
= Run
->RunStartVbn
.QuadPart
;
373 LastSectorCount
= Run
->RunEndVbn
.QuadPart
- Run
->RunStartVbn
.QuadPart
;
376 // these values are meaningless when returning false (but setting them can be helpful for debugging purposes)
379 *SectorCount
= 0xdeadbeef;
382 DPRINT("FsRtlGetNextBaseMcbEntry(%p, %d, %p, %p, %p) = %d (%I64d, %I64d, %I64d)\n", Mcb
, RunIndex
, Vbn
, Lbn
, SectorCount
, Result
, *Vbn
, *Lbn
, *SectorCount
);
391 FsRtlGetNextLargeMcbEntry(IN PLARGE_MCB Mcb
,
395 OUT PLONGLONG SectorCount
)
399 DPRINT("FsRtlGetNextLargeMcbEntry(%p, %d, %p, %p, %p)\n", Mcb
, RunIndex
, Vbn
, Lbn
, SectorCount
);
401 KeAcquireGuardedMutex(Mcb
->GuardedMutex
);
402 Result
= FsRtlGetNextBaseMcbEntry(&(Mcb
->BaseMcb
),
407 KeReleaseGuardedMutex(Mcb
->GuardedMutex
);
409 DPRINT("FsRtlGetNextLargeMcbEntry(%p, %d, %p, %p, %p) = %d (%I64d, %I64d, %I64d)\n", Mcb
, RunIndex
, Vbn
, Lbn
, SectorCount
, Result
, *Vbn
, *Lbn
, *SectorCount
);
419 FsRtlInitializeBaseMcb(IN PBASE_MCB OpaqueMcb
,
420 IN POOL_TYPE PoolType
)
422 PBASE_MCB_INTERNAL Mcb
= (PBASE_MCB_INTERNAL
)OpaqueMcb
;
424 if (PoolType
== PagedPool
)
426 Mcb
->Mapping
= ExAllocateFromPagedLookasideList(&FsRtlFirstMappingLookasideList
);
430 Mcb
->Mapping
= ExAllocatePoolWithTag(PoolType
| POOL_RAISE_IF_ALLOCATION_FAILURE
,
431 sizeof(LARGE_MCB_MAPPING
),
435 Mcb
->PoolType
= PoolType
;
437 Mcb
->MaximumPairCount
= MAXIMUM_PAIR_COUNT
;
438 RtlInitializeGenericTable(&Mcb
->Mapping
->Table
,
450 FsRtlInitializeLargeMcb(IN PLARGE_MCB Mcb
,
451 IN POOL_TYPE PoolType
)
453 DPRINT("FsRtlInitializeLargeMcb(%p, %d)\n", Mcb
, PoolType
);
455 Mcb
->GuardedMutex
= ExAllocateFromNPagedLookasideList(&FsRtlFastMutexLookasideList
);
457 KeInitializeGuardedMutex(Mcb
->GuardedMutex
);
461 FsRtlInitializeBaseMcb(&(Mcb
->BaseMcb
), PoolType
);
463 _SEH2_EXCEPT(EXCEPTION_EXECUTE_HANDLER
)
465 ExFreeToNPagedLookasideList(&FsRtlFastMutexLookasideList
,
467 Mcb
->GuardedMutex
= NULL
;
478 FsRtlInitializeLargeMcbs(VOID
)
480 /* Initialize the list for the MCB */
481 ExInitializePagedLookasideList(&FsRtlFirstMappingLookasideList
,
484 POOL_RAISE_IF_ALLOCATION_FAILURE
,
485 sizeof(LARGE_MCB_MAPPING
),
487 0); /* FIXME: Should be 4 */
489 /* Initialize the list for the guarded mutex */
490 ExInitializeNPagedLookasideList(&FsRtlFastMutexLookasideList
,
493 POOL_RAISE_IF_ALLOCATION_FAILURE
,
494 sizeof(KGUARDED_MUTEX
),
496 0); /* FIXME: Should be 32 */
504 FsRtlLookupBaseMcbEntry(IN PBASE_MCB OpaqueMcb
,
506 OUT PLONGLONG Lbn OPTIONAL
,
507 OUT PLONGLONG SectorCountFromLbn OPTIONAL
,
508 OUT PLONGLONG StartingLbn OPTIONAL
,
509 OUT PLONGLONG SectorCountFromStartingLbn OPTIONAL
,
510 OUT PULONG Index OPTIONAL
)
512 BOOLEAN Result
= FALSE
;
514 LONGLONG LastVbn
= 0, LastLbn
= 0, Count
= 0; // the last values we've found during traversal
516 DPRINT("FsRtlLookupBaseMcbEntry(%p, %I64d, %p, %p, %p, %p, %p)\n", OpaqueMcb
, Vbn
, Lbn
, SectorCountFromLbn
, StartingLbn
, SectorCountFromStartingLbn
, Index
);
518 for (i
= 0; FsRtlGetNextBaseMcbEntry(OpaqueMcb
, i
, &LastVbn
, &LastLbn
, &Count
); i
++)
520 // have we reached the target mapping?
521 if (Vbn
< LastVbn
+ Count
)
528 *Lbn
= LastLbn
+ (Vbn
- LastVbn
);
531 if (SectorCountFromLbn
)
532 *SectorCountFromLbn
= LastVbn
+ Count
- Vbn
;
534 *StartingLbn
= LastLbn
;
535 if (SectorCountFromStartingLbn
)
536 *SectorCountFromStartingLbn
= LastVbn
+ Count
- LastVbn
;
551 DPRINT("FsRtlLookupBaseMcbEntry(%p, %I64d, %p, %p, %p, %p, %p) = %d (%I64d, %I64d, %I64d, %I64d, %d)\n",
552 OpaqueMcb
, Vbn
, Lbn
, SectorCountFromLbn
, StartingLbn
, SectorCountFromStartingLbn
, Index
, Result
,
553 (Lbn
? *Lbn
: (ULONGLONG
)-1), (SectorCountFromLbn
? *SectorCountFromLbn
: (ULONGLONG
)-1), (StartingLbn
? *StartingLbn
: (ULONGLONG
)-1),
554 (SectorCountFromStartingLbn
? *SectorCountFromStartingLbn
: (ULONGLONG
)-1), (Index
? *Index
: (ULONG
)-1));
564 FsRtlLookupLargeMcbEntry(IN PLARGE_MCB Mcb
,
566 OUT PLONGLONG Lbn OPTIONAL
,
567 OUT PLONGLONG SectorCountFromLbn OPTIONAL
,
568 OUT PLONGLONG StartingLbn OPTIONAL
,
569 OUT PLONGLONG SectorCountFromStartingLbn OPTIONAL
,
570 OUT PULONG Index OPTIONAL
)
574 DPRINT("FsRtlLookupLargeMcbEntry(%p, %I64d, %p, %p, %p, %p, %p)\n", Mcb
, Vbn
, Lbn
, SectorCountFromLbn
, StartingLbn
, SectorCountFromStartingLbn
, Index
);
576 KeAcquireGuardedMutex(Mcb
->GuardedMutex
);
577 Result
= FsRtlLookupBaseMcbEntry(&(Mcb
->BaseMcb
),
582 SectorCountFromStartingLbn
,
584 KeReleaseGuardedMutex(Mcb
->GuardedMutex
);
586 DPRINT("FsRtlLookupLargeMcbEntry(%p, %I64d, %p, %p, %p, %p, %p) = %d (%I64d, %I64d, %I64d, %I64d, %d)\n",
587 Mcb
, Vbn
, Lbn
, SectorCountFromLbn
, StartingLbn
, SectorCountFromStartingLbn
, Index
, Result
,
588 (Lbn
? *Lbn
: (ULONGLONG
)-1), (SectorCountFromLbn
? *SectorCountFromLbn
: (ULONGLONG
)-1), (StartingLbn
? *StartingLbn
: (ULONGLONG
)-1),
589 (SectorCountFromStartingLbn
? *SectorCountFromStartingLbn
: (ULONGLONG
)-1), (Index
? *Index
: (ULONG
)-1));
596 FsRtlLookupLastLargeMcbEntryAndIndex_internal(IN PBASE_MCB_INTERNAL Mcb
,
599 OUT PULONG Index OPTIONAL
)
602 PLARGE_MCB_MAPPING_ENTRY Run
, RunFound
= NULL
;
603 LONGLONG LastVbn
= 0;
605 for (Run
= (PLARGE_MCB_MAPPING_ENTRY
)RtlEnumerateGenericTable(&Mcb
->Mapping
->Table
, TRUE
);
607 Run
= (PLARGE_MCB_MAPPING_ENTRY
)RtlEnumerateGenericTable(&Mcb
->Mapping
->Table
, FALSE
))
609 /* Take care when we must emulate missing 'hole' runs. */
610 if (Run
->RunStartVbn
.QuadPart
> LastVbn
)
614 LastVbn
= Run
->RunEndVbn
.QuadPart
;
626 *Vbn
= RunFound
->RunEndVbn
.QuadPart
- 1;
632 *Lbn
= RunFound
->StartingLbn
.QuadPart
+ (RunFound
->RunEndVbn
.QuadPart
- RunFound
->RunStartVbn
.QuadPart
) - 1;
641 *Index
= RunIndex
- 1;
653 FsRtlLookupLastBaseMcbEntryAndIndex(IN PBASE_MCB OpaqueMcb
,
654 IN OUT PLONGLONG LargeVbn
,
655 IN OUT PLONGLONG LargeLbn
,
659 PBASE_MCB_INTERNAL Mcb
= (PBASE_MCB_INTERNAL
)OpaqueMcb
;
661 DPRINT("FsRtlLookupLastBaseMcbEntryAndIndex(%p, %p, %p, %p)\n", OpaqueMcb
, LargeVbn
, LargeLbn
, Index
);
663 Result
= FsRtlLookupLastLargeMcbEntryAndIndex_internal(Mcb
, LargeVbn
, LargeLbn
, Index
);
665 DPRINT("FsRtlLookupLastBaseMcbEntryAndIndex(%p, %p, %p, %p) = %d (%I64d, %I64d, %d)\n", OpaqueMcb
, LargeVbn
, LargeLbn
, Index
, Result
, *LargeVbn
, *LargeLbn
, *Index
);
675 FsRtlLookupLastLargeMcbEntryAndIndex(IN PLARGE_MCB OpaqueMcb
,
676 OUT PLONGLONG LargeVbn
,
677 OUT PLONGLONG LargeLbn
,
682 DPRINT("FsRtlLookupLastLargeMcbEntryAndIndex(%p, %p, %p, %p)\n", OpaqueMcb
, LargeVbn
, LargeLbn
, Index
);
684 KeAcquireGuardedMutex(OpaqueMcb
->GuardedMutex
);
685 Result
= FsRtlLookupLastBaseMcbEntryAndIndex(&(OpaqueMcb
->BaseMcb
),
689 KeReleaseGuardedMutex(OpaqueMcb
->GuardedMutex
);
691 DPRINT("FsRtlLookupLastLargeMcbEntryAndIndex(%p, %p, %p, %p) = %d (%I64d, %I64d, %d)\n", OpaqueMcb
, LargeVbn
, LargeLbn
, Index
, Result
, *LargeVbn
, *LargeLbn
, *Index
);
701 FsRtlLookupLastBaseMcbEntry(IN PBASE_MCB OpaqueMcb
,
706 PBASE_MCB_INTERNAL Mcb
= (PBASE_MCB_INTERNAL
)OpaqueMcb
;
708 DPRINT("FsRtlLookupLastBaseMcbEntry(%p, %p, %p)\n", OpaqueMcb
, Vbn
, Lbn
);
710 Result
= FsRtlLookupLastLargeMcbEntryAndIndex_internal(Mcb
, Vbn
, Lbn
, NULL
); /* Index */
712 DPRINT("FsRtlLookupLastBaseMcbEntry(%p, %p, %p) = %d (%I64d, %I64d)\n", Mcb
, Vbn
, Lbn
, Result
, *Vbn
, *Lbn
);
722 FsRtlLookupLastLargeMcbEntry(IN PLARGE_MCB Mcb
,
728 DPRINT("FsRtlLookupLastLargeMcbEntry(%p, %p, %p)\n", Mcb
, Vbn
, Lbn
);
730 KeAcquireGuardedMutex(Mcb
->GuardedMutex
);
731 Result
= FsRtlLookupLastBaseMcbEntry(&(Mcb
->BaseMcb
),
734 KeReleaseGuardedMutex(Mcb
->GuardedMutex
);
736 DPRINT("FsRtlLookupLastLargeMcbEntry(%p, %p, %p) = %d (%I64d, %I64d)\n", Mcb
, Vbn
, Lbn
, Result
, *Vbn
, *Lbn
);
746 FsRtlNumberOfRunsInBaseMcb(IN PBASE_MCB OpaqueMcb
)
748 ULONG NumberOfRuns
= 0;
749 LONGLONG Vbn
, Lbn
, Count
;
752 DPRINT("FsRtlNumberOfRunsInBaseMcb(%p)\n", OpaqueMcb
);
754 // Count how many Mcb entries there are
755 for (i
= 0; FsRtlGetNextBaseMcbEntry(OpaqueMcb
, i
, &Vbn
, &Lbn
, &Count
); i
++)
760 DPRINT("FsRtlNumberOfRunsInBaseMcb(%p) = %d\n", OpaqueMcb
, NumberOfRuns
);
769 FsRtlNumberOfRunsInLargeMcb(IN PLARGE_MCB Mcb
)
773 DPRINT("FsRtlNumberOfRunsInLargeMcb(%p)\n", Mcb
);
775 /* Read the number of runs while holding the MCB lock */
776 KeAcquireGuardedMutex(Mcb
->GuardedMutex
);
777 NumberOfRuns
= FsRtlNumberOfRunsInBaseMcb(&(Mcb
->BaseMcb
));
778 KeReleaseGuardedMutex(Mcb
->GuardedMutex
);
780 DPRINT("FsRtlNumberOfRunsInLargeMcb(%p) = %d\n", Mcb
, NumberOfRuns
);
782 /* Return the count */
788 * @Mcb: #PLARGE_MCB initialized by FsRtlInitializeLargeMcb().
789 * %NULL value is forbidden.
790 * @Vbn: Starting virtual block number to specify the range to delete.
791 * @SectorCount: Length of the range to delete.
792 * Value less or equal to %0 is forbidden; FIXME: Is the reject of %0 W32 compliant?
794 * Deletes any possible @Mcb mappings in the given range @Vbn ... @Vbn+@SectorCount-1.
795 * This call has no problems if no mappings exist there yet.
799 FsRtlRemoveBaseMcbEntry(IN PBASE_MCB OpaqueMcb
,
801 IN LONGLONG SectorCount
)
803 PBASE_MCB_INTERNAL Mcb
= (PBASE_MCB_INTERNAL
)OpaqueMcb
;
804 LARGE_MCB_MAPPING_ENTRY NeedleRun
;
805 PLARGE_MCB_MAPPING_ENTRY HaystackRun
;
806 BOOLEAN Result
= TRUE
;
808 DPRINT("FsRtlRemoveBaseMcbEntry(%p, %I64d, %I64d)\n", OpaqueMcb
, Vbn
, SectorCount
);
810 if (Vbn
< 0 || SectorCount
<= 0)
816 if (Vbn
+ SectorCount
<= Vbn
)
822 NeedleRun
.RunStartVbn
.QuadPart
= Vbn
;
823 NeedleRun
.RunEndVbn
.QuadPart
= Vbn
+ SectorCount
;
824 NeedleRun
.StartingLbn
.QuadPart
= ~0ULL;
826 /* adjust/destroy all intersecting ranges */
827 Mcb
->Mapping
->Table
.CompareRoutine
= McbMappingIntersectCompare
;
828 while ((HaystackRun
= RtlLookupElementGenericTable(&Mcb
->Mapping
->Table
, &NeedleRun
)))
830 if (HaystackRun
->RunStartVbn
.QuadPart
< NeedleRun
.RunStartVbn
.QuadPart
)
832 ASSERT(HaystackRun
->RunEndVbn
.QuadPart
> NeedleRun
.RunStartVbn
.QuadPart
);
833 HaystackRun
->RunEndVbn
.QuadPart
= NeedleRun
.RunStartVbn
.QuadPart
;
835 else if (HaystackRun
->RunEndVbn
.QuadPart
> NeedleRun
.RunEndVbn
.QuadPart
)
837 ASSERT(HaystackRun
->RunStartVbn
.QuadPart
< NeedleRun
.RunEndVbn
.QuadPart
);
838 HaystackRun
->RunStartVbn
.QuadPart
= NeedleRun
.RunEndVbn
.QuadPart
;
842 //ASSERT(NeedleRun.RunStartVbn.QuadPart >= HaystackRun->RunStartVbn.QuadPart);
843 //ASSERT(NeedleRun.RunEndVbn.QuadPart <= HaystackRun->RunEndVbn.QuadPart);
844 Mcb
->Mapping
->Table
.CompareRoutine
= McbMappingCompare
;
845 RtlDeleteElementGenericTable(&Mcb
->Mapping
->Table
, HaystackRun
);
847 Mcb
->Mapping
->Table
.CompareRoutine
= McbMappingIntersectCompare
;
850 Mcb
->Mapping
->Table
.CompareRoutine
= McbMappingCompare
;
853 DPRINT("FsRtlRemoveBaseMcbEntry(%p, %I64d, %I64d) = %d\n", OpaqueMcb
, Vbn
, SectorCount
, Result
);
862 FsRtlRemoveLargeMcbEntry(IN PLARGE_MCB Mcb
,
864 IN LONGLONG SectorCount
)
866 DPRINT("FsRtlRemoveLargeMcbEntry(%p, %I64d, %I64d)\n", Mcb
, Vbn
, SectorCount
);
868 KeAcquireGuardedMutex(Mcb
->GuardedMutex
);
869 FsRtlRemoveBaseMcbEntry(&(Mcb
->BaseMcb
), Vbn
, SectorCount
);
870 KeReleaseGuardedMutex(Mcb
->GuardedMutex
);
878 FsRtlResetBaseMcb(IN PBASE_MCB OpaqueMcb
)
880 PBASE_MCB_INTERNAL Mcb
= (PBASE_MCB_INTERNAL
)OpaqueMcb
;
881 PLARGE_MCB_MAPPING_ENTRY Element
;
883 DPRINT("FsRtlResetBaseMcb(%p)\n", OpaqueMcb
);
885 while (RtlNumberGenericTableElements(&Mcb
->Mapping
->Table
) &&
886 (Element
= (PLARGE_MCB_MAPPING_ENTRY
)RtlGetElementGenericTable(&Mcb
->Mapping
->Table
, 0)))
888 RtlDeleteElementGenericTable(&Mcb
->Mapping
->Table
, Element
);
892 Mcb
->MaximumPairCount
= 0;
900 FsRtlResetLargeMcb(IN PLARGE_MCB Mcb
,
901 IN BOOLEAN SelfSynchronized
)
903 DPRINT("FsRtlResetLargeMcb(%p, %d)\n", Mcb
, SelfSynchronized
);
905 if (!SelfSynchronized
)
906 KeAcquireGuardedMutex(Mcb
->GuardedMutex
);
908 FsRtlResetBaseMcb(&Mcb
->BaseMcb
);
910 if (!SelfSynchronized
)
911 KeReleaseGuardedMutex(Mcb
->GuardedMutex
);
919 FsRtlSplitBaseMcb(IN PBASE_MCB OpaqueMcb
,
923 PBASE_MCB_INTERNAL Mcb
= (PBASE_MCB_INTERNAL
)OpaqueMcb
;
924 PLARGE_MCB_MAPPING_ENTRY Run
, InsertLowerRun
= NULL
, ExistingRun
= NULL
;
927 DPRINT("FsRtlSplitBaseMcb(%p, %I64d, %I64d)\n", OpaqueMcb
, Vbn
, Amount
);
929 /* Traverse the tree */
930 for (Run
= (PLARGE_MCB_MAPPING_ENTRY
)RtlEnumerateGenericTable(&Mcb
->Mapping
->Table
, TRUE
);
932 Run
= (PLARGE_MCB_MAPPING_ENTRY
)RtlEnumerateGenericTable(&Mcb
->Mapping
->Table
, FALSE
))
934 /* unaffected run? */
935 /* FIXME: performance: effective skip of all 'lower' runs without traversing them */
936 if (Vbn
>= Run
->RunEndVbn
.QuadPart
) { DPRINT("Skipping it\n"); continue; }
938 /* crossing run to be split?
939 * 'lower_run' is created on the original place; just shortened.
940 * current 'run' is shifted up later
942 if (Vbn
< Run
->RunEndVbn
.QuadPart
)
944 /* FIXME: shift 'run->Lbn_start' ? */
945 Run
->RunStartVbn
.QuadPart
= Vbn
;
947 InsertLowerRun
= NULL
;
950 /* Shift the current 'run'.
951 * Ordering is not changed in Generic Tree so I hope I do not need to reinsert it.
953 Run
->RunStartVbn
.QuadPart
+= Amount
;
954 ASSERT(Run
->RunEndVbn
.QuadPart
+ Amount
> Run
->RunEndVbn
.QuadPart
); /* overflow? */
955 Run
->RunEndVbn
.QuadPart
+= Amount
;
956 /* FIXME: shift 'run->Lbn_start' ? */
958 /* continue the traversal */
963 ExistingRun
= RtlInsertElementGenericTable(&Mcb
->Mapping
->Table
, InsertLowerRun
, sizeof(*InsertLowerRun
), &NewElement
);
967 ASSERT(ExistingRun
== NULL
);
969 DPRINT("FsRtlSplitBaseMcb(%p, %I64d, %I64d) = %d\n", OpaqueMcb
, Vbn
, Amount
, TRUE
);
979 FsRtlSplitLargeMcb(IN PLARGE_MCB Mcb
,
985 DPRINT("FsRtlSplitLargeMcb(%p, %I64d, %I64d)\n", Mcb
, Vbn
, Amount
);
987 KeAcquireGuardedMutex(Mcb
->GuardedMutex
);
988 Result
= FsRtlSplitBaseMcb(&(Mcb
->BaseMcb
),
991 KeReleaseGuardedMutex(Mcb
->GuardedMutex
);
993 DPRINT("FsRtlSplitLargeMcb(%p, %I64d, %I64d) = %d\n", Mcb
, Vbn
, Amount
, Result
);
1003 FsRtlTruncateBaseMcb(IN PBASE_MCB OpaqueMcb
,
1006 DPRINT("FsRtlTruncateBaseMcb(%p, %I64d)\n", OpaqueMcb
, Vbn
);
1008 FsRtlRemoveBaseMcbEntry(OpaqueMcb
, Vbn
, MAXLONG
- Vbn
+ 1);
1016 FsRtlTruncateLargeMcb(IN PLARGE_MCB Mcb
,
1019 DPRINT("FsRtlTruncateLargeMcb(%p, %I64d)\n", Mcb
, Vbn
);
1021 KeAcquireGuardedMutex(Mcb
->GuardedMutex
);
1022 FsRtlTruncateBaseMcb(&(Mcb
->BaseMcb
), Vbn
);
1023 KeReleaseGuardedMutex(Mcb
->GuardedMutex
);
1031 FsRtlUninitializeBaseMcb(IN PBASE_MCB Mcb
)
1033 DPRINT("FsRtlUninitializeBaseMcb(%p)\n", Mcb
);
1035 FsRtlResetBaseMcb(Mcb
);
1037 if ((Mcb
->PoolType
== PagedPool
)/* && (Mcb->MaximumPairCount == MAXIMUM_PAIR_COUNT)*/)
1039 ExFreeToPagedLookasideList(&FsRtlFirstMappingLookasideList
,
1044 ExFreePoolWithTag(Mcb
->Mapping
, 'FSBC');
1053 FsRtlUninitializeLargeMcb(IN PLARGE_MCB Mcb
)
1055 DPRINT("FsRtlUninitializeLargeMcb(%p)\n", Mcb
);
1057 if (Mcb
->GuardedMutex
)
1059 ExFreeToNPagedLookasideList(&FsRtlFastMutexLookasideList
,
1061 FsRtlUninitializeBaseMcb(&(Mcb
->BaseMcb
));