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>
10 /* INCLUDES ******************************************************************/
16 #define MIN(x,y) (((x)<(y))?(x):(y))
17 #define MAX(x,y) (((x)>(y))?(x):(y))
19 /* GLOBALS *******************************************************************/
21 PAGED_LOOKASIDE_LIST FsRtlFirstMappingLookasideList
;
22 NPAGED_LOOKASIDE_LIST FsRtlFastMutexLookasideList
;
24 /* We use only real 'mapping' runs; we do not store 'holes' to our GTree. */
25 typedef struct _LARGE_MCB_MAPPING_ENTRY
// run
27 LARGE_INTEGER RunStartVbn
;
28 LARGE_INTEGER RunEndVbn
; /* RunStartVbn+SectorCount; that means +1 after the last sector */
29 LARGE_INTEGER StartingLbn
; /* Lbn of 'RunStartVbn' */
30 } LARGE_MCB_MAPPING_ENTRY
, *PLARGE_MCB_MAPPING_ENTRY
;
32 typedef struct _LARGE_MCB_MAPPING
// mcb_priv
34 RTL_GENERIC_TABLE Table
;
35 } LARGE_MCB_MAPPING
, *PLARGE_MCB_MAPPING
;
37 typedef struct _BASE_MCB_INTERNAL
{
38 ULONG MaximumPairCount
;
42 PLARGE_MCB_MAPPING Mapping
;
43 } BASE_MCB_INTERNAL
, *PBASE_MCB_INTERNAL
;
45 static LARGE_MCB_MAPPING_ENTRY StaticRunBelow0
= {
51 static PVOID NTAPI
McbMappingAllocate(PRTL_GENERIC_TABLE Table
, CLONG Bytes
)
54 PBASE_MCB Mcb
= (PBASE_MCB
)Table
->TableContext
;
55 Result
= ExAllocatePoolWithTag(Mcb
->PoolType
, Bytes
, 'LMCB');
56 DPRINT("McbMappingAllocate(%lu) => %p\n", Bytes
, Result
);
60 static VOID NTAPI
McbMappingFree(PRTL_GENERIC_TABLE Table
, PVOID Buffer
)
62 DPRINT("McbMappingFree(%p)\n", Buffer
);
63 ExFreePoolWithTag(Buffer
, 'LMCB');
67 RTL_GENERIC_COMPARE_RESULTS
69 McbMappingCompare(PRTL_GENERIC_TABLE Table
,
73 PLARGE_MCB_MAPPING_ENTRY A
= PtrA
, B
= PtrB
;
74 RTL_GENERIC_COMPARE_RESULTS Res
;
79 if (A
->RunStartVbn
.QuadPart
== B
->RunStartVbn
.QuadPart
&& A
->RunEndVbn
.QuadPart
== B
->RunEndVbn
.QuadPart
)
81 else if (A
->RunEndVbn
.QuadPart
<= B
->RunStartVbn
.QuadPart
)
82 Res
= GenericLessThan
;
83 else if (A
->RunEndVbn
.QuadPart
>= B
->RunStartVbn
.QuadPart
)
84 Res
= GenericGreaterThan
;
94 static RTL_GENERIC_COMPARE_RESULTS NTAPI
McbMappingIntersectCompare(PRTL_GENERIC_TABLE Table
, PVOID PtrA
, PVOID PtrB
)
96 PLARGE_MCB_MAPPING_ENTRY A
= PtrA
, B
= PtrB
;
97 RTL_GENERIC_COMPARE_RESULTS Res
;
99 if (A
->RunStartVbn
.QuadPart
<= B
->RunStartVbn
.QuadPart
&& A
->RunEndVbn
.QuadPart
> B
->RunStartVbn
.QuadPart
)
101 else if (A
->RunStartVbn
.QuadPart
>= B
->RunStartVbn
.QuadPart
&& B
->RunEndVbn
.QuadPart
> A
->RunStartVbn
.QuadPart
)
103 else if (A
->RunStartVbn
.QuadPart
< B
->RunStartVbn
.QuadPart
)
104 Res
= GenericLessThan
;
105 else if (A
->RunStartVbn
.QuadPart
> B
->RunStartVbn
.QuadPart
)
106 Res
= GenericGreaterThan
;
114 /* PUBLIC FUNCTIONS **********************************************************/
118 * @Mcb: #PLARGE_MCB initialized by FsRtlInitializeLargeMcb().
119 * %NULL value is forbidden.
120 * @Vbn: Starting virtual block number of the wished range.
121 * @Lbn: Starting logical block number of the wished range.
122 * @SectorCount: Length of the wished range.
123 * Value less or equal to %0 is forbidden; FIXME: Is the reject of %0 W32 compliant?
125 * Adds the specified range @Vbn ... @Vbn+@SectorCount-1 to @Mcb.
126 * Any mappings previously in this range are deleted first.
128 * Returns: %TRUE if successful.
132 FsRtlAddBaseMcbEntry(IN PBASE_MCB OpaqueMcb
,
135 IN LONGLONG SectorCount
)
137 PBASE_MCB_INTERNAL Mcb
= (PBASE_MCB_INTERNAL
)OpaqueMcb
;
138 LARGE_MCB_MAPPING_ENTRY Node
, NeedleRun
;
139 PLARGE_MCB_MAPPING_ENTRY LowerRun
, HigherRun
;
142 if (Vbn
< 0) return FALSE
;
143 if (SectorCount
<= 0) return FALSE
;
145 /* clean any possible previous entries in our range */
146 FsRtlRemoveBaseMcbEntry(OpaqueMcb
, Vbn
, SectorCount
);
148 // We need to map [Vbn, Vbn+SectorCount) to [Lbn, Lbn+SectorCount),
149 // taking in account the fact that we need to merge these runs if
150 // they are adjacent or overlap, but fail if new run fully fits into another run
152 /* initially we think we will be inserted as a separate run */
153 Node
.RunStartVbn
.QuadPart
= Vbn
;
154 Node
.RunEndVbn
.QuadPart
= Vbn
+ SectorCount
;
155 Node
.StartingLbn
.QuadPart
= Lbn
;
157 /* optionally merge with lower run */
158 NeedleRun
.RunStartVbn
.QuadPart
= Node
.RunStartVbn
.QuadPart
- 1;
159 NeedleRun
.RunEndVbn
.QuadPart
= NeedleRun
.RunStartVbn
.QuadPart
+ 1;
160 NeedleRun
.StartingLbn
.QuadPart
= ~0ULL;
161 Mcb
->Mapping
->Table
.CompareRoutine
= McbMappingIntersectCompare
;
162 if ((LowerRun
= RtlLookupElementGenericTable(&Mcb
->Mapping
->Table
, &NeedleRun
)))
164 ASSERT(LowerRun
->RunEndVbn
.QuadPart
== Node
.RunStartVbn
.QuadPart
);
165 Node
.RunStartVbn
.QuadPart
= LowerRun
->RunStartVbn
.QuadPart
;
166 Node
.StartingLbn
.QuadPart
= LowerRun
->StartingLbn
.QuadPart
;
167 Mcb
->Mapping
->Table
.CompareRoutine
= McbMappingCompare
;
168 RtlDeleteElementGenericTable(&Mcb
->Mapping
->Table
, LowerRun
);
169 DPRINT("Intersecting lower run found (%I64d,%I64d) Lbn: %I64d\n", LowerRun
->RunStartVbn
.QuadPart
, LowerRun
->RunEndVbn
.QuadPart
, LowerRun
->StartingLbn
.QuadPart
);
172 /* optionally merge with higher run */
173 NeedleRun
.RunStartVbn
.QuadPart
= Node
.RunEndVbn
.QuadPart
;
174 NeedleRun
.RunEndVbn
.QuadPart
= NeedleRun
.RunStartVbn
.QuadPart
+ 1;
175 Mcb
->Mapping
->Table
.CompareRoutine
= McbMappingIntersectCompare
;
176 if ((HigherRun
= RtlLookupElementGenericTable(&Mcb
->Mapping
->Table
, &NeedleRun
)))
178 ASSERT(HigherRun
->RunStartVbn
.QuadPart
== Node
.RunEndVbn
.QuadPart
);
179 Node
.RunEndVbn
.QuadPart
= HigherRun
->RunEndVbn
.QuadPart
;
180 Mcb
->Mapping
->Table
.CompareRoutine
= McbMappingCompare
;
181 RtlDeleteElementGenericTable(&Mcb
->Mapping
->Table
, HigherRun
);
182 DPRINT("Intersecting higher run found (%I64d,%I64d) Lbn: %I64d\n", HigherRun
->RunStartVbn
.QuadPart
, HigherRun
->RunEndVbn
.QuadPart
, HigherRun
->StartingLbn
.QuadPart
);
184 Mcb
->Mapping
->Table
.CompareRoutine
= McbMappingCompare
;
186 /* finally insert the resulting run */
187 RtlInsertElementGenericTable(&Mcb
->Mapping
->Table
, &Node
, sizeof(Node
), &NewElement
);
189 Node
.RunStartVbn
.QuadPart
= Vbn
;
190 Node
.RunEndVbn
.QuadPart
= Vbn
+ SectorCount
;
191 Node
.StartingLbn
.QuadPart
= Lbn
;
193 // NB: Two consecutive runs can only be merged, if actual LBNs also match!
196 Existing->RunStartVbn
204 Existing->RunStartVbn
212 Existing->RunStartVbn
220 Existing->RunStartVbn
228 Situation with holes:
229 1. Holes at both ends
230 2. Hole at the right, new run merged with the previous run
231 3. Hole at the right, new run is not merged with the previous run
232 4. Hole at the left, new run merged with the next run
233 5. Hole at the left, new run is not merged with the next run
234 6. No holes, exact fit to merge with both previous and next runs
235 7. No holes, merges only with the next run
236 8. No holes, merges only with the previous run
237 9. No holes, does not merge with next or prev runs
240 Overwriting existing mapping is not possible and results in FALSE being returned
250 FsRtlAddLargeMcbEntry(IN PLARGE_MCB Mcb
,
253 IN LONGLONG SectorCount
)
257 DPRINT("Mcb %p Vbn %I64d Lbn %I64d SectorCount %I64d\n", Mcb
, Vbn
, Lbn
, SectorCount
);
259 KeAcquireGuardedMutex(Mcb
->GuardedMutex
);
260 Result
= FsRtlAddBaseMcbEntry(&(Mcb
->BaseMcb
),
264 KeReleaseGuardedMutex(Mcb
->GuardedMutex
);
266 DPRINT("Done %u\n", Result
);
273 * @Mcb: #PLARGE_MCB initialized by FsRtlInitializeLargeMcb().
274 * %NULL value is forbidden.
275 * @RunIndex: Requested range index to retrieve.
276 * @Vbn: Returns the starting virtual block number of the wished range.
277 * %NULL pointer is forbidden.
278 * @Lbn: Returns the starting logical block number of the wished range (or -1 if it is a hole).
279 * %NULL pointer is forbidden.
280 * @SectorCount: Returns the length of the wished range.
281 * %NULL pointer is forbidden.
282 * Value less or equal to %0 is forbidden; FIXME: Is the reject of %0 W32 compliant?
284 * Retrieves the parameters of the specified run with index @RunIndex.
286 * Mapping %0 always starts at virtual block %0, either as 'hole' or as 'real' mapping.
287 * libcaptive does not store 'hole' information to its #GTree.
288 * Last run is always a 'real' run. 'hole' runs appear as mapping to constant @Lbn value %-1.
290 * Returns: %TRUE if successful.
294 FsRtlGetNextBaseMcbEntry(IN PBASE_MCB OpaqueMcb
,
298 OUT PLONGLONG SectorCount
)
300 PBASE_MCB_INTERNAL Mcb
= (PBASE_MCB_INTERNAL
)OpaqueMcb
;
301 ULONG RunIndexRemaining
;
302 PLARGE_MCB_MAPPING_ENTRY Run
, RunFound
= NULL
, RunFoundLower
= NULL
, RunFoundHigher
= NULL
;
303 BOOLEAN First
= TRUE
;
305 RunIndexRemaining
= RunIndex
;
307 /* Traverse the tree */
308 for (Run
= (PLARGE_MCB_MAPPING_ENTRY
)RtlEnumerateGenericTable(&Mcb
->Mapping
->Table
, TRUE
);
310 Run
= (PLARGE_MCB_MAPPING_ENTRY
)RtlEnumerateGenericTable(&Mcb
->Mapping
->Table
, FALSE
))
314 /* Take care when we must emulate missing 'hole' run at start of our run list. */
315 if (Run
->RunStartVbn
.QuadPart
> 0)
317 if (RunIndexRemaining
== 0)
319 RunFoundLower
= &StaticRunBelow0
;
320 RunFoundHigher
= Run
;
322 /* stop the traversal */
325 /* If someone wants RunIndex #1 we are already on it. */
331 if (RunIndexRemaining
> 0)
333 /* FIXME: performance: non-linear direct seek to the requested RunIndex */
335 if (RunIndexRemaining
== 0)
340 /* continue the traversal */
345 RunFoundHigher
= Run
;
349 /* stop the traversal */
353 if (RunFound
) DPRINT("RunFound(%lu %lu %lu)\n", RunFound
->RunStartVbn
.LowPart
, RunFound
->RunEndVbn
.LowPart
, RunFound
->StartingLbn
.LowPart
);
354 if (RunFoundLower
) DPRINT("RunFoundLower(%lu %lu %lu)\n", RunFoundLower
->RunStartVbn
.LowPart
, RunFoundLower
->RunEndVbn
.LowPart
, RunFoundLower
->StartingLbn
.LowPart
);
355 if (RunFoundHigher
) DPRINT("RunFoundHigher(%lu %lu %lu)\n", RunFoundHigher
->RunStartVbn
.LowPart
, RunFoundHigher
->RunEndVbn
.LowPart
, RunFoundHigher
->StartingLbn
.LowPart
);
359 ASSERT(RunFoundLower
== NULL
);
360 ASSERT(RunFoundHigher
== NULL
);
363 *Vbn
= RunFound
->RunStartVbn
.QuadPart
;
365 *Lbn
= RunFound
->StartingLbn
.QuadPart
;
367 *SectorCount
= RunFound
->RunEndVbn
.QuadPart
- RunFound
->RunStartVbn
.QuadPart
;
372 if (RunFoundLower
&& RunFoundHigher
)
374 //ASSERT(RunFoundHigher != NULL);
377 *Vbn
= RunFoundLower
->RunEndVbn
.QuadPart
;
381 *SectorCount
= RunFoundHigher
->RunStartVbn
.QuadPart
- RunFoundLower
->RunEndVbn
.QuadPart
;
386 ASSERT(RunFoundHigher
== NULL
);
395 FsRtlGetNextLargeMcbEntry(IN PLARGE_MCB Mcb
,
399 OUT PLONGLONG SectorCount
)
403 DPRINT("FsRtlGetNextLargeMcbEntry Mcb %p RunIndex %lu\n", Mcb
, RunIndex
);
405 KeAcquireGuardedMutex(Mcb
->GuardedMutex
);
406 Result
= FsRtlGetNextBaseMcbEntry(&(Mcb
->BaseMcb
),
411 KeReleaseGuardedMutex(Mcb
->GuardedMutex
);
413 DPRINT("Done %u\n", Result
);
423 FsRtlInitializeBaseMcb(IN PBASE_MCB OpaqueMcb
,
424 IN POOL_TYPE PoolType
)
426 PBASE_MCB_INTERNAL Mcb
= (PBASE_MCB_INTERNAL
)OpaqueMcb
;
428 if (PoolType
== PagedPool
)
430 Mcb
->Mapping
= ExAllocateFromPagedLookasideList(&FsRtlFirstMappingLookasideList
);
434 Mcb
->Mapping
= ExAllocatePoolWithTag(PoolType
| POOL_RAISE_IF_ALLOCATION_FAILURE
,
435 sizeof(LARGE_MCB_MAPPING
),
439 Mcb
->PoolType
= PoolType
;
441 Mcb
->MaximumPairCount
= MAXIMUM_PAIR_COUNT
;
442 RtlInitializeGenericTable(&Mcb
->Mapping
->Table
,
454 FsRtlInitializeLargeMcb(IN PLARGE_MCB Mcb
,
455 IN POOL_TYPE PoolType
)
457 Mcb
->GuardedMutex
= ExAllocateFromNPagedLookasideList(&FsRtlFastMutexLookasideList
);
459 KeInitializeGuardedMutex(Mcb
->GuardedMutex
);
463 FsRtlInitializeBaseMcb(&(Mcb
->BaseMcb
), PoolType
);
465 _SEH2_EXCEPT(EXCEPTION_EXECUTE_HANDLER
)
467 ExFreeToNPagedLookasideList(&FsRtlFastMutexLookasideList
,
469 Mcb
->GuardedMutex
= NULL
;
479 FsRtlInitializeLargeMcbs(VOID
)
481 /* Initialize the list for the MCB */
482 ExInitializePagedLookasideList(&FsRtlFirstMappingLookasideList
,
485 POOL_RAISE_IF_ALLOCATION_FAILURE
,
486 sizeof(LARGE_MCB_MAPPING
),
488 0); /* FIXME: Should be 4 */
490 /* Initialize the list for the guarded mutex */
491 ExInitializeNPagedLookasideList(&FsRtlFastMutexLookasideList
,
494 POOL_RAISE_IF_ALLOCATION_FAILURE
,
495 sizeof(KGUARDED_MUTEX
),
497 0); /* FIXME: Should be 32 */
505 FsRtlLookupBaseMcbEntry(IN PBASE_MCB OpaqueMcb
,
507 OUT PLONGLONG Lbn OPTIONAL
,
508 OUT PLONGLONG SectorCountFromLbn OPTIONAL
,
509 OUT PLONGLONG StartingLbn OPTIONAL
,
510 OUT PLONGLONG SectorCountFromStartingLbn OPTIONAL
,
511 OUT PULONG Index OPTIONAL
)
513 PBASE_MCB_INTERNAL Mcb
= (PBASE_MCB_INTERNAL
)OpaqueMcb
;
517 PLARGE_MCB_MAPPING_ENTRY Run
, RunFound
= NULL
, RunFoundLower
= NULL
, RunFoundHigher
= NULL
;
518 BOOLEAN First
= TRUE
;
520 /* Traverse the tree */
521 for (Run
= (PLARGE_MCB_MAPPING_ENTRY
)RtlEnumerateGenericTable(&Mcb
->Mapping
->Table
, TRUE
);
523 Run
= (PLARGE_MCB_MAPPING_ENTRY
)RtlEnumerateGenericTable(&Mcb
->Mapping
->Table
, FALSE
))
527 /* Take care when we must emulate missing 'hole' run at start of our run list. */
528 if (Run
->RunStartVbn
.QuadPart
> 0)
531 RunFoundLower
= &StaticRunBelow0
;
536 if (Run
->RunStartVbn
.QuadPart
<= Vbn
&& Vbn
< Run
->RunEndVbn
.QuadPart
)
539 RunFoundLower
= NULL
;
540 /* stop the traversal; hit */
544 if (Run
->RunEndVbn
.QuadPart
<= Vbn
)
547 if (Run
->StartingLbn
.QuadPart
> 0)
551 /* continue the traversal; not yet crossed by the run */
555 if (Vbn
< Run
->RunStartVbn
.QuadPart
)
557 RunFoundHigher
= Run
;
559 /* stop the traversal; the run skipped us */
564 /* stop the traversal */
570 ASSERT(RunFoundLower
== NULL
);
571 ASSERT(RunFoundHigher
== NULL
);
574 *Lbn
= RunFound
->StartingLbn
.QuadPart
+ (Vbn
- RunFound
->RunStartVbn
.QuadPart
);
576 if (SectorCountFromLbn
) /* FIXME: 'after' means including current 'Lbn' or without it? */
577 *SectorCountFromLbn
= RunFound
->RunEndVbn
.QuadPart
- Vbn
;
579 *StartingLbn
= RunFound
->StartingLbn
.QuadPart
;
580 if (SectorCountFromStartingLbn
)
581 *SectorCountFromStartingLbn
= RunFound
->RunEndVbn
.QuadPart
- RunFound
->RunStartVbn
.QuadPart
;
590 /* search for hole */
591 ASSERT(RunFoundLower
!= NULL
);
595 if (SectorCountFromLbn
) /* FIXME: 'after' means including current 'Lbn' or without it? */
596 *SectorCountFromLbn
= RunFoundHigher
->RunStartVbn
.QuadPart
- Vbn
;
598 *StartingLbn
= ~0ull;
599 if (SectorCountFromStartingLbn
)
600 *SectorCountFromStartingLbn
= RunFoundHigher
->RunStartVbn
.QuadPart
- RunFoundLower
->RunEndVbn
.QuadPart
;
602 *Index
= RunIndex
- 2;
607 /* We may have some 'RunFoundLower'. */
616 FsRtlLookupLargeMcbEntry(IN PLARGE_MCB Mcb
,
618 OUT PLONGLONG Lbn OPTIONAL
,
619 OUT PLONGLONG SectorCountFromLbn OPTIONAL
,
620 OUT PLONGLONG StartingLbn OPTIONAL
,
621 OUT PLONGLONG SectorCountFromStartingLbn OPTIONAL
,
622 OUT PULONG Index OPTIONAL
)
626 DPRINT("FsRtlLookupLargeMcbEntry Mcb %p Vbn %I64d\n", Mcb
, Vbn
);
628 KeAcquireGuardedMutex(Mcb
->GuardedMutex
);
629 Result
= FsRtlLookupBaseMcbEntry(&(Mcb
->BaseMcb
),
634 SectorCountFromStartingLbn
,
636 KeReleaseGuardedMutex(Mcb
->GuardedMutex
);
638 DPRINT("Done %u\n", Result
);
645 FsRtlLookupLastLargeMcbEntryAndIndex_internal(IN PBASE_MCB_INTERNAL Mcb
,
648 OUT PULONG Index OPTIONAL
)
651 PLARGE_MCB_MAPPING_ENTRY Run
, RunFound
= NULL
;
652 LONGLONG LastVbn
= 0;
654 for (Run
= (PLARGE_MCB_MAPPING_ENTRY
)RtlEnumerateGenericTable(&Mcb
->Mapping
->Table
, TRUE
);
656 Run
= (PLARGE_MCB_MAPPING_ENTRY
)RtlEnumerateGenericTable(&Mcb
->Mapping
->Table
, FALSE
))
658 /* Take care when we must emulate missing 'hole' runs. */
659 if (Run
->RunStartVbn
.QuadPart
> LastVbn
)
663 LastVbn
= Run
->RunEndVbn
.QuadPart
;
675 *Vbn
= RunFound
->RunEndVbn
.QuadPart
- 1;
681 *Lbn
= RunFound
->StartingLbn
.QuadPart
+ (RunFound
->RunEndVbn
.QuadPart
- RunFound
->RunStartVbn
.QuadPart
) - 1;
690 *Index
= RunIndex
- 1;
702 FsRtlLookupLastBaseMcbEntryAndIndex(IN PBASE_MCB OpaqueMcb
,
703 IN OUT PLONGLONG LargeVbn
,
704 IN OUT PLONGLONG LargeLbn
,
707 PBASE_MCB_INTERNAL Mcb
= (PBASE_MCB_INTERNAL
)OpaqueMcb
;
709 return FsRtlLookupLastLargeMcbEntryAndIndex_internal(Mcb
, LargeVbn
, LargeLbn
, Index
);
717 FsRtlLookupLastLargeMcbEntryAndIndex(IN PLARGE_MCB OpaqueMcb
,
718 OUT PLONGLONG LargeVbn
,
719 OUT PLONGLONG LargeLbn
,
724 DPRINT("FsRtlLookupLastLargeMcbEntryAndIndex %p\n", OpaqueMcb
);
726 KeAcquireGuardedMutex(OpaqueMcb
->GuardedMutex
);
727 Result
= FsRtlLookupLastBaseMcbEntryAndIndex(&(OpaqueMcb
->BaseMcb
),
731 KeReleaseGuardedMutex(OpaqueMcb
->GuardedMutex
);
733 DPRINT("Done %u\n", Result
);
743 FsRtlLookupLastBaseMcbEntry(IN PBASE_MCB OpaqueMcb
,
747 PBASE_MCB_INTERNAL Mcb
= (PBASE_MCB_INTERNAL
)OpaqueMcb
;
749 return FsRtlLookupLastLargeMcbEntryAndIndex_internal(Mcb
, Vbn
, Lbn
, NULL
); /* Index */
757 FsRtlLookupLastLargeMcbEntry(IN PLARGE_MCB Mcb
,
763 DPRINT("FsRtlLookupLastLargeMcbEntry Mcb %p\n", Mcb
);
765 KeAcquireGuardedMutex(Mcb
->GuardedMutex
);
766 Result
= FsRtlLookupLastBaseMcbEntry(&(Mcb
->BaseMcb
),
769 KeReleaseGuardedMutex(Mcb
->GuardedMutex
);
771 DPRINT("Done %u\n", Result
);
781 FsRtlNumberOfRunsInBaseMcb(IN PBASE_MCB OpaqueMcb
)
783 PBASE_MCB_INTERNAL Mcb
= (PBASE_MCB_INTERNAL
)OpaqueMcb
;
784 LONGLONG LbnAtVbn0
= -1;
785 ULONG Nodes
= RtlNumberGenericTableElements(&Mcb
->Mapping
->Table
);
787 if (Nodes
== 0) return 0;
789 FsRtlLookupBaseMcbEntry(OpaqueMcb
,
791 &LbnAtVbn0
, /* Lbn */
792 NULL
, NULL
, NULL
, NULL
); /* 4 output arguments - not interested in them */
795 /* Return the count */
796 //return Mcb->PairCount;
797 /* Return the number of 'real' and 'hole' runs.
798 * If we do not have sector 0 as 'real' emulate a 'hole' there.
800 return Nodes
* 2 - (LbnAtVbn0
!= -1 ? 1 : 0); /* include holes as runs */
808 FsRtlNumberOfRunsInLargeMcb(IN PLARGE_MCB Mcb
)
812 DPRINT("FsRtlNumberOfRunsInLargeMcb Mcb %p\n", Mcb
);
814 /* Read the number of runs while holding the MCB lock */
815 KeAcquireGuardedMutex(Mcb
->GuardedMutex
);
816 NumberOfRuns
= FsRtlNumberOfRunsInBaseMcb(&(Mcb
->BaseMcb
));
817 KeReleaseGuardedMutex(Mcb
->GuardedMutex
);
819 DPRINT("Done %lu\n", NumberOfRuns
);
821 /* Return the count */
827 * @Mcb: #PLARGE_MCB initialized by FsRtlInitializeLargeMcb().
828 * %NULL value is forbidden.
829 * @Vbn: Starting virtual block number to specify the range to delete.
830 * @SectorCount: Length of the range to delete.
831 * Value less or equal to %0 is forbidden; FIXME: Is the reject of %0 W32 compliant?
833 * Deletes any possible @Mcb mappings in the given range @Vbn ... @Vbn+@SectorCount-1.
834 * This call has no problems if no mappings exist there yet.
838 FsRtlRemoveBaseMcbEntry(IN PBASE_MCB OpaqueMcb
,
840 IN LONGLONG SectorCount
)
842 PBASE_MCB_INTERNAL Mcb
= (PBASE_MCB_INTERNAL
)OpaqueMcb
;
843 LARGE_MCB_MAPPING_ENTRY NeedleRun
;
844 PLARGE_MCB_MAPPING_ENTRY HaystackRun
;
846 if (Vbn
< 0 || SectorCount
<= 0) return FALSE
;
847 if (Vbn
+ SectorCount
<= Vbn
) return FALSE
;
849 NeedleRun
.RunStartVbn
.QuadPart
= Vbn
;
850 NeedleRun
.RunEndVbn
.QuadPart
= Vbn
+ SectorCount
;
851 NeedleRun
.StartingLbn
.QuadPart
= ~0ULL;
853 /* adjust/destroy all intersecting ranges */
854 Mcb
->Mapping
->Table
.CompareRoutine
= McbMappingIntersectCompare
;
855 while ((HaystackRun
= RtlLookupElementGenericTable(&Mcb
->Mapping
->Table
, &NeedleRun
)))
857 if (HaystackRun
->RunStartVbn
.QuadPart
< NeedleRun
.RunStartVbn
.QuadPart
)
859 ASSERT(HaystackRun
->RunEndVbn
.QuadPart
> NeedleRun
.RunStartVbn
.QuadPart
);
860 HaystackRun
->RunEndVbn
.QuadPart
= NeedleRun
.RunStartVbn
.QuadPart
;
862 else if (HaystackRun
->RunEndVbn
.QuadPart
> NeedleRun
.RunEndVbn
.QuadPart
)
864 ASSERT(HaystackRun
->RunStartVbn
.QuadPart
< NeedleRun
.RunEndVbn
.QuadPart
);
865 HaystackRun
->RunStartVbn
.QuadPart
= NeedleRun
.RunEndVbn
.QuadPart
;
869 ASSERT(NeedleRun
.RunStartVbn
.QuadPart
>= HaystackRun
->RunStartVbn
.QuadPart
);
870 //ASSERT(NeedleRun.RunEndVbn.QuadPart <= HaystackRun->RunEndVbn.QuadPart);
871 Mcb
->Mapping
->Table
.CompareRoutine
= McbMappingCompare
;
872 RtlDeleteElementGenericTable(&Mcb
->Mapping
->Table
, HaystackRun
);
873 Mcb
->Mapping
->Table
.CompareRoutine
= McbMappingIntersectCompare
;
876 Mcb
->Mapping
->Table
.CompareRoutine
= McbMappingCompare
;
886 FsRtlRemoveLargeMcbEntry(IN PLARGE_MCB Mcb
,
888 IN LONGLONG SectorCount
)
890 DPRINT("FsRtlRemoveLargeMcbEntry Mcb %p, Vbn %I64d, SectorCount %I64d\n", Mcb
, Vbn
, SectorCount
);
892 KeAcquireGuardedMutex(Mcb
->GuardedMutex
);
893 FsRtlRemoveBaseMcbEntry(&(Mcb
->BaseMcb
), Vbn
, SectorCount
);
894 KeReleaseGuardedMutex(Mcb
->GuardedMutex
);
904 FsRtlResetBaseMcb(IN PBASE_MCB OpaqueMcb
)
906 PBASE_MCB_INTERNAL Mcb
= (PBASE_MCB_INTERNAL
)OpaqueMcb
;
907 PLARGE_MCB_MAPPING_ENTRY Element
;
909 while (RtlNumberGenericTableElements(&Mcb
->Mapping
->Table
) &&
910 (Element
= (PLARGE_MCB_MAPPING_ENTRY
)RtlGetElementGenericTable(&Mcb
->Mapping
->Table
, 0)))
912 RtlDeleteElementGenericTable(&Mcb
->Mapping
->Table
, Element
);
916 Mcb
->MaximumPairCount
= 0;
924 FsRtlResetLargeMcb(IN PLARGE_MCB Mcb
,
925 IN BOOLEAN SelfSynchronized
)
927 if (!SelfSynchronized
)
928 KeAcquireGuardedMutex(Mcb
->GuardedMutex
);
930 FsRtlResetBaseMcb(&Mcb
->BaseMcb
);
932 if (!SelfSynchronized
)
933 KeReleaseGuardedMutex(Mcb
->GuardedMutex
);
941 FsRtlSplitBaseMcb(IN PBASE_MCB OpaqueMcb
,
945 PBASE_MCB_INTERNAL Mcb
= (PBASE_MCB_INTERNAL
)OpaqueMcb
;
946 PLARGE_MCB_MAPPING_ENTRY Run
, InsertLowerRun
= NULL
, ExistingRun
= NULL
;
949 /* Traverse the tree */
950 for (Run
= (PLARGE_MCB_MAPPING_ENTRY
)RtlEnumerateGenericTable(&Mcb
->Mapping
->Table
, TRUE
);
952 Run
= (PLARGE_MCB_MAPPING_ENTRY
)RtlEnumerateGenericTable(&Mcb
->Mapping
->Table
, FALSE
))
954 /* unaffected run? */
955 /* FIXME: performance: effective skip of all 'lower' runs without traversing them */
956 if (Vbn
>= Run
->RunEndVbn
.QuadPart
) { DPRINT("Skipping it\n"); continue; }
958 /* crossing run to be split?
959 * 'lower_run' is created on the original place; just shortened.
960 * current 'run' is shifted up later
962 if (Vbn
< Run
->RunEndVbn
.QuadPart
)
964 /* FIXME: shift 'run->Lbn_start' ? */
965 Run
->RunStartVbn
.QuadPart
= Vbn
;
967 InsertLowerRun
= NULL
;
970 /* Shift the current 'run'.
971 * Ordering is not changed in Generic Tree so I hope I do not need to reinsert it.
973 Run
->RunStartVbn
.QuadPart
+= Amount
;
974 ASSERT(Run
->RunEndVbn
.QuadPart
+ Amount
> Run
->RunEndVbn
.QuadPart
); /* overflow? */
975 Run
->RunEndVbn
.QuadPart
+= Amount
;
976 /* FIXME: shift 'run->Lbn_start' ? */
978 /* continue the traversal */
982 ExistingRun
= RtlInsertElementGenericTable(&Mcb
->Mapping
->Table
, InsertLowerRun
, sizeof(*InsertLowerRun
), &NewElement
);
984 ASSERT(ExistingRun
== NULL
);
994 FsRtlSplitLargeMcb(IN PLARGE_MCB Mcb
,
1000 DPRINT("FsRtlSplitLargeMcb %p, Vbn %I64d, Amount %I64d\n", Mcb
, Vbn
, Amount
);
1002 KeAcquireGuardedMutex(Mcb
->GuardedMutex
);
1003 Result
= FsRtlSplitBaseMcb(&(Mcb
->BaseMcb
),
1006 KeReleaseGuardedMutex(Mcb
->GuardedMutex
);
1008 DPRINT("Done %u\n", Result
);
1018 FsRtlTruncateBaseMcb(IN PBASE_MCB OpaqueMcb
,
1021 DPRINT("Mcb=%p, Vbn=%I64d\n", OpaqueMcb
, Vbn
);
1022 FsRtlRemoveBaseMcbEntry(OpaqueMcb
, Vbn
, MAXLONG
- Vbn
+ 1);
1030 FsRtlTruncateLargeMcb(IN PLARGE_MCB Mcb
,
1033 DPRINT("FsRtlTruncateLargeMcb %p Vbn %I64d\n", Mcb
, Vbn
);
1034 KeAcquireGuardedMutex(Mcb
->GuardedMutex
);
1035 FsRtlTruncateBaseMcb(&(Mcb
->BaseMcb
), Vbn
);
1036 KeReleaseGuardedMutex(Mcb
->GuardedMutex
);
1045 FsRtlUninitializeBaseMcb(IN PBASE_MCB Mcb
)
1047 FsRtlResetBaseMcb(Mcb
);
1049 if ((Mcb
->PoolType
== PagedPool
)/* && (Mcb->MaximumPairCount == MAXIMUM_PAIR_COUNT)*/)
1051 ExFreeToPagedLookasideList(&FsRtlFirstMappingLookasideList
,
1056 ExFreePoolWithTag(Mcb
->Mapping
, 'FSBC');
1065 FsRtlUninitializeLargeMcb(IN PLARGE_MCB Mcb
)
1067 if (Mcb
->GuardedMutex
)
1069 ExFreeToNPagedLookasideList(&FsRtlFastMutexLookasideList
,
1071 FsRtlUninitializeBaseMcb(&(Mcb
->BaseMcb
));