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 PLARGE_MCB_MAPPING_ENTRY run_compare_func_last_a_run
;
52 static PLARGE_MCB_MAPPING_ENTRY run_compare_func_last_b_run
;
53 static PLARGE_MCB_MAPPING_ENTRY run_compare_func_minus_a_run
; /* last run where we returned -1 */
54 static PLARGE_MCB_MAPPING_ENTRY run_compare_func_minus_b_run
;
55 static PLARGE_MCB_MAPPING_ENTRY run_compare_func_plus_a_run
; /* last run where we returned +1 */
56 static PLARGE_MCB_MAPPING_ENTRY run_compare_func_plus_b_run
;
58 static PVOID NTAPI
McbMappingAllocate(PRTL_GENERIC_TABLE Table
, CLONG Bytes
)
61 PBASE_MCB Mcb
= (PBASE_MCB
)Table
->TableContext
;
62 Result
= ExAllocatePoolWithTag(Mcb
->PoolType
, Bytes
, 'LMCB');
63 DPRINT("McbMappingAllocate(%lu) => %p\n", Bytes
, Result
);
67 static VOID NTAPI
McbMappingFree(PRTL_GENERIC_TABLE Table
, PVOID Buffer
)
69 DPRINT("McbMappingFree(%p)\n", Buffer
);
70 ExFreePoolWithTag(Buffer
, 'LMCB');
74 RTL_GENERIC_COMPARE_RESULTS
76 McbMappingCompare(PRTL_GENERIC_TABLE Table
,
80 PLARGE_MCB_MAPPING_ENTRY A
= PtrA
, B
= PtrB
;
82 RTL_GENERIC_COMPARE_RESULTS Res
;
85 (A->RunStartVbn.QuadPart + A->SectorCount.QuadPart < B->RunStartVbn.QuadPart) ? GenericLessThan :
86 (A->RunStartVbn.QuadPart > B->RunStartVbn.QuadPart + B->SectorCount.QuadPart) ? GenericGreaterThan : GenericEqual;*/
89 (A->RunEndVbn.QuadPart < B->RunStartVbn.QuadPart) ? GenericLessThan :
90 (A->RunStartVbn.QuadPart > B->RunEndVbn.QuadPart) ? GenericGreaterThan : GenericEqual;*/
92 run_compare_func_last_a_run
= A
;
93 run_compare_func_last_b_run
= B
;
96 && !(r
= (A
->RunStartVbn
.QuadPart
> B
->RunStartVbn
.QuadPart
) - (A
->RunStartVbn
.QuadPart
< B
->RunStartVbn
.QuadPart
))
97 && !(r
= (A
->RunEndVbn
.QuadPart
> B
->RunEndVbn
.QuadPart
) - (A
->RunEndVbn
.QuadPart
< B
->RunEndVbn
.QuadPart
)))
102 //DPRINT("A(%d-%d,%d) %p, B(%d-%d,%d) %p, Res %d\n", A->RunStartVbn.LowPart, A->RunEndVbn.LowPart, A->StartingLbn.LowPart, A, B->RunStartVbn.LowPart, B->RunEndVbn.LowPart, B->StartingLbn.LowPart, B, r);
105 negative value if a < b;
107 positive value if a > b.
110 Res
= GenericLessThan
;
112 Res
= GenericGreaterThan
;
116 if (Res
== GenericLessThan
)
118 run_compare_func_minus_a_run
= A
;
119 run_compare_func_minus_b_run
= B
;
121 else if (Res
== GenericGreaterThan
)
123 run_compare_func_plus_a_run
= A
;
124 run_compare_func_plus_b_run
= B
;
130 static RTL_GENERIC_COMPARE_RESULTS NTAPI
McbMappingIntersectCompare(PRTL_GENERIC_TABLE Table
, PVOID PtrA
, PVOID PtrB
)
132 PLARGE_MCB_MAPPING_ENTRY HaystackRun
= PtrA
, NeedleRun
= PtrB
;
133 LARGE_MCB_MAPPING_ENTRY CommonRun
;
134 RTL_GENERIC_COMPARE_RESULTS Res
;
136 if (!HaystackRun
) return GenericEqual
;
137 if (HaystackRun
->RunEndVbn
.QuadPart
<= HaystackRun
->RunStartVbn
.QuadPart
) return GenericEqual
;
139 if (!NeedleRun
) return GenericEqual
;
140 if (NeedleRun
->RunEndVbn
.QuadPart
<= NeedleRun
->RunStartVbn
.QuadPart
) return GenericEqual
;
142 CommonRun
.RunStartVbn
.QuadPart
= MAX(HaystackRun
->RunStartVbn
.QuadPart
, NeedleRun
->RunStartVbn
.QuadPart
);
143 CommonRun
.RunEndVbn
.QuadPart
= MIN(HaystackRun
->RunEndVbn
.QuadPart
, NeedleRun
->RunEndVbn
.QuadPart
);
145 if (CommonRun
.RunEndVbn
.QuadPart
> CommonRun
.RunStartVbn
.QuadPart
)
148 Res
= McbMappingCompare(Table
, NeedleRun
, HaystackRun
);
149 ASSERT(Res
!= GenericEqual
); /* otherwise we would hit it by 'common_run' */
154 /* PUBLIC FUNCTIONS **********************************************************/
158 * @Mcb: #PLARGE_MCB initialized by FsRtlInitializeLargeMcb().
159 * %NULL value is forbidden.
160 * @Vbn: Starting virtual block number of the wished range.
161 * @Lbn: Starting logical block number of the wished range.
162 * @SectorCount: Length of the wished range.
163 * Value less or equal to %0 is forbidden; FIXME: Is the reject of %0 W32 compliant?
165 * Adds the specified range @Vbn ... @Vbn+@SectorCount-1 to @Mcb.
166 * Any mappings previously in this range are deleted first.
168 * Returns: %TRUE if successful.
172 FsRtlAddBaseMcbEntry(IN PBASE_MCB OpaqueMcb
,
175 IN LONGLONG SectorCount
)
177 PBASE_MCB_INTERNAL Mcb
= (PBASE_MCB_INTERNAL
)OpaqueMcb
;
178 LARGE_MCB_MAPPING_ENTRY Node
, NeedleRun
;
179 PLARGE_MCB_MAPPING_ENTRY LowerRun
, HigherRun
, Existing
= NULL
;
182 if (Vbn
< 0) return FALSE
;
183 if (SectorCount
<= 0) return FALSE
;
185 //DPRINT("Mcb=%p,Vbn=%lld,Lbn=%lld,SectorCount=%lld\n", Mcb, Vbn, Lbn, SectorCount);
187 /* clean any possible previous entries in our range */
188 FsRtlRemoveBaseMcbEntry(OpaqueMcb
, Vbn
, SectorCount
);
190 // We need to map [Vbn, Vbn+SectorCount) to [Lbn, Lbn+SectorCount),
191 // taking in account the fact that we need to merge these runs if
192 // they are adjacent or overlap, but fail if new run fully fits into another run
194 /* initially we think we will be inserted as a separate run */
195 Node
.RunStartVbn
.QuadPart
= Vbn
;
196 Node
.RunEndVbn
.QuadPart
= Vbn
+ SectorCount
;
197 Node
.StartingLbn
.QuadPart
= Lbn
;
199 /* optionally merge with lower run */
200 NeedleRun
.RunStartVbn
.QuadPart
= Node
.RunStartVbn
.QuadPart
- 1;
201 NeedleRun
.RunEndVbn
.QuadPart
= NeedleRun
.RunStartVbn
.QuadPart
+ 1;
202 //if ((LowerRun = g_tree_search(Mcb_priv->gtree,(GCompareFunc)run_intersect_compare_func, &NeedleRun)))
203 Mcb
->Mapping
->Table
.CompareRoutine
= McbMappingIntersectCompare
;
204 if ((LowerRun
= RtlLookupElementGenericTable(&Mcb
->Mapping
->Table
, &NeedleRun
)))
206 ASSERT(LowerRun
->RunEndVbn
.QuadPart
== Node
.RunStartVbn
.QuadPart
);
207 Node
.RunStartVbn
.QuadPart
= LowerRun
->RunStartVbn
.QuadPart
;
208 Mcb
->Mapping
->Table
.CompareRoutine
= McbMappingCompare
;
209 RtlDeleteElementGenericTable(&Mcb
->Mapping
->Table
, LowerRun
);
210 DPRINT("Intersecting lower run found (%I64d,%I64d) Lbn: %I64d\n", LowerRun
->RunStartVbn
.QuadPart
, LowerRun
->RunEndVbn
.QuadPart
, LowerRun
->StartingLbn
.QuadPart
);
213 /* optionally merge with higher run */
214 NeedleRun
.RunStartVbn
.QuadPart
= Node
.RunEndVbn
.QuadPart
;
215 NeedleRun
.RunEndVbn
.QuadPart
= NeedleRun
.RunStartVbn
.QuadPart
+ 1;
216 //if ((HigherRun = g_tree_search(Mcb_priv->gtree,(GCompareFunc)run_intersect_compare_func, &NeedleRun)))
217 Mcb
->Mapping
->Table
.CompareRoutine
= McbMappingIntersectCompare
;
218 if ((HigherRun
= RtlLookupElementGenericTable(&Mcb
->Mapping
->Table
, &NeedleRun
)))
220 ASSERT(HigherRun
->RunStartVbn
.QuadPart
== Node
.RunEndVbn
.QuadPart
);
221 Node
.RunEndVbn
.QuadPart
= HigherRun
->RunEndVbn
.QuadPart
;
222 Mcb
->Mapping
->Table
.CompareRoutine
= McbMappingCompare
;
223 RtlDeleteElementGenericTable(&Mcb
->Mapping
->Table
, HigherRun
);
224 DPRINT("Intersecting higher run found (%I64d,%I64d) Lbn: %I64d\n", HigherRun
->RunStartVbn
.QuadPart
, HigherRun
->RunEndVbn
.QuadPart
, HigherRun
->StartingLbn
.QuadPart
);
226 Mcb
->Mapping
->Table
.CompareRoutine
= McbMappingCompare
;
228 /* finally insert the resulting run */
229 Existing
= RtlInsertElementGenericTable(&Mcb
->Mapping
->Table
, &Node
, sizeof(Node
), &NewElement
);
230 DPRINT("Existing %p, NewElement %u\n", Existing
, NewElement
);
233 // NB: Two consecutive runs can only be merged, if actual LBNs also match!
236 Existing->RunStartVbn
244 Existing->RunStartVbn
252 Existing->RunStartVbn
260 Existing->RunStartVbn
268 Situation with holes:
269 1. Holes at both ends
270 2. Hole at the right, new run merged with the previous run
271 3. Hole at the right, new run is not merged with the previous run
272 4. Hole at the left, new run merged with the next run
273 5. Hole at the left, new run is not merged with the next run
274 6. No holes, exact fit to merge with both previous and next runs
275 7. No holes, merges only with the next run
276 8. No holes, merges only with the previous run
277 9. No holes, does not merge with next or prev runs
280 Overwriting existing mapping is not possible and results in FALSE being returned
290 FsRtlAddLargeMcbEntry(IN PLARGE_MCB Mcb
,
293 IN LONGLONG SectorCount
)
297 DPRINT("Mcb %p Vbn %lld Lbn %lld SectorCount %lld\n", Mcb
, Vbn
, Lbn
, SectorCount
);
299 KeAcquireGuardedMutex(Mcb
->GuardedMutex
);
300 Result
= FsRtlAddBaseMcbEntry(&(Mcb
->BaseMcb
),
304 KeReleaseGuardedMutex(Mcb
->GuardedMutex
);
306 DPRINT("Done %u\n", Result
);
313 * @Mcb: #PLARGE_MCB initialized by FsRtlInitializeLargeMcb().
314 * %NULL value is forbidden.
315 * @RunIndex: Requested range index to retrieve.
316 * @Vbn: Returns the starting virtual block number of the wished range.
317 * %NULL pointer is forbidden.
318 * @Lbn: Returns the starting logical block number of the wished range (or -1 if it is a hole).
319 * %NULL pointer is forbidden.
320 * @SectorCount: Returns the length of the wished range.
321 * %NULL pointer is forbidden.
322 * Value less or equal to %0 is forbidden; FIXME: Is the reject of %0 W32 compliant?
324 * Retrieves the parameters of the specified run with index @RunIndex.
326 * Mapping %0 always starts at virtual block %0, either as 'hole' or as 'real' mapping.
327 * libcaptive does not store 'hole' information to its #GTree.
328 * Last run is always a 'real' run. 'hole' runs appear as mapping to constant @Lbn value %-1.
330 * Returns: %TRUE if successful.
334 FsRtlGetNextBaseMcbEntry(IN PBASE_MCB OpaqueMcb
,
338 OUT PLONGLONG SectorCount
)
340 PBASE_MCB_INTERNAL Mcb
= (PBASE_MCB_INTERNAL
)OpaqueMcb
;
341 ULONG RunIndexRemaining
;
342 PLARGE_MCB_MAPPING_ENTRY Run
, RunFound
= NULL
, RunFoundLower
= NULL
, RunFoundHigher
= NULL
;
343 BOOLEAN First
= TRUE
;
345 RunIndexRemaining
= RunIndex
;
347 /* Traverse the tree */
348 for (Run
= (PLARGE_MCB_MAPPING_ENTRY
)RtlEnumerateGenericTable(&Mcb
->Mapping
->Table
, TRUE
);
350 Run
= (PLARGE_MCB_MAPPING_ENTRY
)RtlEnumerateGenericTable(&Mcb
->Mapping
->Table
, FALSE
))
354 /* Take care when we must emulate missing 'hole' run at start of our run list. */
355 if (Run
->RunStartVbn
.QuadPart
> 0)
357 if (RunIndexRemaining
== 0)
359 RunFoundLower
= &StaticRunBelow0
;
360 RunFoundHigher
= Run
;
362 /* stop the traversal */
365 /* If someone wants RunIndex #1 we are already on it. */
371 if (RunIndexRemaining
> 0)
373 /* FIXME: performance: non-linear direct seek to the requested RunIndex */
375 if (RunIndexRemaining
== 0)
380 /* continue the traversal */
385 RunFoundHigher
= Run
;
389 /* stop the traversal */
393 if (RunFound
) DPRINT("RunFound(%lu %lu %lu)\n", RunFound
->RunStartVbn
.LowPart
, RunFound
->RunEndVbn
.LowPart
, RunFound
->StartingLbn
.LowPart
);
394 if (RunFoundLower
) DPRINT("RunFoundLower(%lu %lu %lu)\n", RunFoundLower
->RunStartVbn
.LowPart
, RunFoundLower
->RunEndVbn
.LowPart
, RunFoundLower
->StartingLbn
.LowPart
);
395 if (RunFoundHigher
) DPRINT("RunFoundHigher(%lu %lu %lu)\n", RunFoundHigher
->RunStartVbn
.LowPart
, RunFoundHigher
->RunEndVbn
.LowPart
, RunFoundHigher
->StartingLbn
.LowPart
);
399 ASSERT(RunFoundLower
== NULL
);
400 ASSERT(RunFoundHigher
== NULL
);
403 *Vbn
= RunFound
->RunStartVbn
.QuadPart
;
405 *Lbn
= RunFound
->StartingLbn
.QuadPart
;
407 *SectorCount
= RunFound
->RunEndVbn
.QuadPart
- RunFound
->RunStartVbn
.QuadPart
;
412 if (RunFoundLower
&& RunFoundHigher
)
414 //ASSERT(RunFoundHigher != NULL);
417 *Vbn
= RunFoundLower
->RunEndVbn
.QuadPart
;
421 *SectorCount
= RunFoundHigher
->RunStartVbn
.QuadPart
- RunFoundLower
->RunEndVbn
.QuadPart
;
426 ASSERT(RunFoundHigher
== NULL
);
435 FsRtlGetNextLargeMcbEntry(IN PLARGE_MCB Mcb
,
439 OUT PLONGLONG SectorCount
)
443 DPRINT("FsRtlGetNextLargeMcbEntry Mcb %p RunIndex %lu\n", Mcb
, RunIndex
);
445 KeAcquireGuardedMutex(Mcb
->GuardedMutex
);
446 Result
= FsRtlGetNextBaseMcbEntry(&(Mcb
->BaseMcb
),
451 KeReleaseGuardedMutex(Mcb
->GuardedMutex
);
453 DPRINT("Done %u\n", Result
);
463 FsRtlInitializeBaseMcb(IN PBASE_MCB OpaqueMcb
,
464 IN POOL_TYPE PoolType
)
466 PBASE_MCB_INTERNAL Mcb
= (PBASE_MCB_INTERNAL
)OpaqueMcb
;
468 if (PoolType
== PagedPool
)
470 Mcb
->Mapping
= ExAllocateFromPagedLookasideList(&FsRtlFirstMappingLookasideList
);
474 Mcb
->Mapping
= ExAllocatePoolWithTag(PoolType
| POOL_RAISE_IF_ALLOCATION_FAILURE
,
475 sizeof(LARGE_MCB_MAPPING
),
479 Mcb
->PoolType
= PoolType
;
481 Mcb
->MaximumPairCount
= MAXIMUM_PAIR_COUNT
;
482 RtlInitializeGenericTable(&Mcb
->Mapping
->Table
,
494 FsRtlInitializeLargeMcb(IN PLARGE_MCB Mcb
,
495 IN POOL_TYPE PoolType
)
497 Mcb
->GuardedMutex
= ExAllocateFromNPagedLookasideList(&FsRtlFastMutexLookasideList
);
499 KeInitializeGuardedMutex(Mcb
->GuardedMutex
);
503 FsRtlInitializeBaseMcb(&(Mcb
->BaseMcb
), PoolType
);
505 _SEH2_EXCEPT(EXCEPTION_EXECUTE_HANDLER
)
507 ExFreeToNPagedLookasideList(&FsRtlFastMutexLookasideList
,
509 Mcb
->GuardedMutex
= NULL
;
519 FsRtlInitializeLargeMcbs(VOID
)
521 /* Initialize the list for the MCB */
522 ExInitializePagedLookasideList(&FsRtlFirstMappingLookasideList
,
525 POOL_RAISE_IF_ALLOCATION_FAILURE
,
526 sizeof(LARGE_MCB_MAPPING
),
528 0); /* FIXME: Should be 4 */
530 /* Initialize the list for the guarded mutex */
531 ExInitializeNPagedLookasideList(&FsRtlFastMutexLookasideList
,
534 POOL_RAISE_IF_ALLOCATION_FAILURE
,
535 sizeof(KGUARDED_MUTEX
),
537 0); /* FIXME: Should be 32 */
545 FsRtlLookupBaseMcbEntry(IN PBASE_MCB OpaqueMcb
,
547 OUT PLONGLONG Lbn OPTIONAL
,
548 OUT PLONGLONG SectorCountFromLbn OPTIONAL
,
549 OUT PLONGLONG StartingLbn OPTIONAL
,
550 OUT PLONGLONG SectorCountFromStartingLbn OPTIONAL
,
551 OUT PULONG Index OPTIONAL
)
553 PBASE_MCB_INTERNAL Mcb
= (PBASE_MCB_INTERNAL
)OpaqueMcb
;
557 PLARGE_MCB_MAPPING_ENTRY Run
, RunFound
= NULL
, RunFoundLower
= NULL
, RunFoundHigher
= NULL
;
558 BOOLEAN First
= TRUE
;
560 /* Traverse the tree */
561 for (Run
= (PLARGE_MCB_MAPPING_ENTRY
)RtlEnumerateGenericTable(&Mcb
->Mapping
->Table
, TRUE
);
563 Run
= (PLARGE_MCB_MAPPING_ENTRY
)RtlEnumerateGenericTable(&Mcb
->Mapping
->Table
, FALSE
))
567 /* Take care when we must emulate missing 'hole' run at start of our run list. */
568 if (Run
->RunStartVbn
.QuadPart
> 0)
571 RunFoundLower
= &StaticRunBelow0
;
576 if (Run
->RunStartVbn
.QuadPart
<= Vbn
&& Vbn
< Run
->RunEndVbn
.QuadPart
)
579 RunFoundLower
= NULL
;
580 /* stop the traversal; hit */
584 if (Run
->RunEndVbn
.QuadPart
<= Vbn
)
588 /* continue the traversal; not yet crossed by the run */
592 if (Vbn
< Run
->RunStartVbn
.QuadPart
)
594 RunFoundHigher
= Run
;
596 /* stop the traversal; the run skipped us */
601 /* stop the traversal */
607 ASSERT(RunFoundLower
== NULL
);
608 ASSERT(RunFoundHigher
== NULL
);
611 *Lbn
= RunFound
->StartingLbn
.QuadPart
+ (Vbn
- RunFound
->RunStartVbn
.QuadPart
);
613 if (SectorCountFromLbn
) /* FIXME: 'after' means including current 'Lbn' or without it? */
614 *SectorCountFromLbn
= RunFound
->RunEndVbn
.QuadPart
- Vbn
;
616 *StartingLbn
= RunFound
->StartingLbn
.QuadPart
;
617 if (SectorCountFromStartingLbn
)
618 *SectorCountFromStartingLbn
= RunFound
->RunEndVbn
.QuadPart
- RunFound
->RunStartVbn
.QuadPart
;
627 /* search for hole */
628 ASSERT(RunFoundLower
!= NULL
);
632 if (SectorCountFromLbn
) /* FIXME: 'after' means including current 'Lbn' or without it? */
633 *SectorCountFromLbn
= RunFoundHigher
->RunStartVbn
.QuadPart
- Vbn
;
635 *StartingLbn
= ~0ull;
636 if (SectorCountFromStartingLbn
)
637 *SectorCountFromStartingLbn
= RunFoundHigher
->RunStartVbn
.QuadPart
- RunFoundLower
->RunEndVbn
.QuadPart
;
644 /* We may have some 'RunFoundLower'. */
653 FsRtlLookupLargeMcbEntry(IN PLARGE_MCB Mcb
,
655 OUT PLONGLONG Lbn OPTIONAL
,
656 OUT PLONGLONG SectorCountFromLbn OPTIONAL
,
657 OUT PLONGLONG StartingLbn OPTIONAL
,
658 OUT PLONGLONG SectorCountFromStartingLbn OPTIONAL
,
659 OUT PULONG Index OPTIONAL
)
663 DPRINT("FsRtlLookupLargeMcbEntry Mcb %p Vbn %x\n", Mcb
, (ULONG
)Vbn
);
665 KeAcquireGuardedMutex(Mcb
->GuardedMutex
);
666 Result
= FsRtlLookupBaseMcbEntry(&(Mcb
->BaseMcb
),
671 SectorCountFromStartingLbn
,
673 KeReleaseGuardedMutex(Mcb
->GuardedMutex
);
675 DPRINT("Done %u\n", Result
);
682 FsRtlLookupLastLargeMcbEntryAndIndex_internal(IN PBASE_MCB_INTERNAL Mcb
,
685 OUT PULONG Index OPTIONAL
)
687 LARGE_MCB_MAPPING_ENTRY NeedleRunTop
;
688 PLARGE_MCB_MAPPING_ENTRY FoundRun
;
691 NeedleRunTop
.RunStartVbn
.QuadPart
= MAXLONGLONG
- 1;
692 NeedleRunTop
.RunEndVbn
.QuadPart
= MAXLONGLONG
;
693 NeedleRunTop
.StartingLbn
.QuadPart
= ~0ull; /* ignored*/
695 run_compare_func_last_a_run
= NULL
;
696 run_compare_func_last_b_run
= NULL
;
698 FoundRun
= RtlLookupElementGenericTable(&Mcb
->Mapping
->Table
, &NeedleRunTop
);
699 ASSERT(FoundRun
== NULL
);
701 if (run_compare_func_last_a_run
== NULL
)
703 ASSERT(run_compare_func_last_b_run
== NULL
);
707 if (Index
) *Index
= 0;
710 ASSERT(run_compare_func_last_a_run
!= &NeedleRunTop
);
711 ASSERT(run_compare_func_last_b_run
== &NeedleRunTop
);
713 *Vbn
= run_compare_func_last_a_run
->RunEndVbn
.QuadPart
- 1;
714 *Lbn
= run_compare_func_last_a_run
->StartingLbn
.QuadPart
+ ((run_compare_func_last_a_run
->RunEndVbn
.QuadPart
- 1) - run_compare_func_last_a_run
->RunStartVbn
.QuadPart
);
718 Runs
= FsRtlNumberOfRunsInBaseMcb((PBASE_MCB
)Mcb
);
720 /* There must be some runs if we found _something_. */
734 FsRtlLookupLastBaseMcbEntryAndIndex(IN PBASE_MCB OpaqueMcb
,
735 IN OUT PLONGLONG LargeVbn
,
736 IN OUT PLONGLONG LargeLbn
,
739 PBASE_MCB_INTERNAL Mcb
= (PBASE_MCB_INTERNAL
)OpaqueMcb
;
741 return FsRtlLookupLastLargeMcbEntryAndIndex_internal(Mcb
, LargeVbn
, LargeLbn
, Index
);
749 FsRtlLookupLastLargeMcbEntryAndIndex(IN PLARGE_MCB OpaqueMcb
,
750 OUT PLONGLONG LargeVbn
,
751 OUT PLONGLONG LargeLbn
,
756 DPRINT("FsRtlLookupLastLargeMcbEntryAndIndex %p\n", OpaqueMcb
);
758 KeAcquireGuardedMutex(OpaqueMcb
->GuardedMutex
);
759 Result
= FsRtlLookupLastBaseMcbEntryAndIndex(&(OpaqueMcb
->BaseMcb
),
763 KeReleaseGuardedMutex(OpaqueMcb
->GuardedMutex
);
765 DPRINT("Done %u\n", Result
);
775 FsRtlLookupLastBaseMcbEntry(IN PBASE_MCB OpaqueMcb
,
779 PBASE_MCB_INTERNAL Mcb
= (PBASE_MCB_INTERNAL
)OpaqueMcb
;
781 return FsRtlLookupLastLargeMcbEntryAndIndex_internal(Mcb
, Vbn
, Lbn
, NULL
); /* Index */
789 FsRtlLookupLastLargeMcbEntry(IN PLARGE_MCB Mcb
,
795 DPRINT("FsRtlLookupLastLargeMcbEntry Mcb %p\n", Mcb
);
797 KeAcquireGuardedMutex(Mcb
->GuardedMutex
);
798 Result
= FsRtlLookupLastBaseMcbEntry(&(Mcb
->BaseMcb
),
801 KeReleaseGuardedMutex(Mcb
->GuardedMutex
);
803 DPRINT("Done %u\n", Result
);
813 FsRtlNumberOfRunsInBaseMcb(IN PBASE_MCB OpaqueMcb
)
815 PBASE_MCB_INTERNAL Mcb
= (PBASE_MCB_INTERNAL
)OpaqueMcb
;
816 LONGLONG LbnAtVbn0
= -1;
817 ULONG Nodes
= RtlNumberGenericTableElements(&Mcb
->Mapping
->Table
);
819 if (Nodes
== 0) return 0;
821 FsRtlLookupBaseMcbEntry(OpaqueMcb
,
823 &LbnAtVbn0
, /* Lbn */
824 NULL
, NULL
, NULL
, NULL
); /* 4 output arguments - not interested in them */
827 /* Return the count */
828 //return Mcb->PairCount;
829 /* Return the number of 'real' and 'hole' runs.
830 * If we do not have sector 0 as 'real' emulate a 'hole' there.
832 return Nodes
* 2 - (LbnAtVbn0
!= -1 ? 1 : 0); /* include holes as runs */
840 FsRtlNumberOfRunsInLargeMcb(IN PLARGE_MCB Mcb
)
844 DPRINT("FsRtlNumberOfRunsInLargeMcb Mcb %p\n", Mcb
);
846 /* Read the number of runs while holding the MCB lock */
847 KeAcquireGuardedMutex(Mcb
->GuardedMutex
);
848 NumberOfRuns
= FsRtlNumberOfRunsInBaseMcb(&(Mcb
->BaseMcb
));
849 KeReleaseGuardedMutex(Mcb
->GuardedMutex
);
851 DPRINT("Done %lu\n", NumberOfRuns
);
853 /* Return the count */
859 * @Mcb: #PLARGE_MCB initialized by FsRtlInitializeLargeMcb().
860 * %NULL value is forbidden.
861 * @Vbn: Starting virtual block number to specify the range to delete.
862 * @SectorCount: Length of the range to delete.
863 * Value less or equal to %0 is forbidden; FIXME: Is the reject of %0 W32 compliant?
865 * Deletes any possible @Mcb mappings in the given range @Vbn ... @Vbn+@SectorCount-1.
866 * This call has no problems if no mappings exist there yet.
870 FsRtlRemoveBaseMcbEntry(IN PBASE_MCB OpaqueMcb
,
872 IN LONGLONG SectorCount
)
874 PBASE_MCB_INTERNAL Mcb
= (PBASE_MCB_INTERNAL
)OpaqueMcb
;
875 LARGE_MCB_MAPPING_ENTRY NeedleRun
;
876 PLARGE_MCB_MAPPING_ENTRY HaystackRun
;
878 if (Vbn
< 0 || SectorCount
<= 0) return FALSE
;
879 /* FIXME: We are unable to delete the absolutely last sector G_MAXINT64 by this implementation! */
880 if (Vbn
+ SectorCount
<= Vbn
) return FALSE
;
882 NeedleRun
.RunStartVbn
.QuadPart
= Vbn
;
883 NeedleRun
.RunEndVbn
.QuadPart
= Vbn
+ SectorCount
;
885 /* adjust/destroy all intersecting ranges */
886 Mcb
->Mapping
->Table
.CompareRoutine
= McbMappingIntersectCompare
;
887 //while ((HaystackRun = g_tree_search(Mcb_priv->gtree,(GCompareFunc)run_intersect_compare_func,&needle_run)))
888 while ((HaystackRun
= RtlLookupElementGenericTable(&Mcb
->Mapping
->Table
, &NeedleRun
)))
890 if (HaystackRun
->RunStartVbn
.QuadPart
< NeedleRun
.RunStartVbn
.QuadPart
)
892 ASSERT(HaystackRun
->RunEndVbn
.QuadPart
> NeedleRun
.RunStartVbn
.QuadPart
);
893 HaystackRun
->RunEndVbn
.QuadPart
= NeedleRun
.RunStartVbn
.QuadPart
;
895 else if (HaystackRun
->RunEndVbn
.QuadPart
> NeedleRun
.RunEndVbn
.QuadPart
)
897 ASSERT(HaystackRun
->RunStartVbn
.QuadPart
< NeedleRun
.RunEndVbn
.QuadPart
);
898 HaystackRun
->RunStartVbn
.QuadPart
= NeedleRun
.RunEndVbn
.QuadPart
;
902 ASSERT(NeedleRun
.RunStartVbn
.QuadPart
>= HaystackRun
->RunStartVbn
.QuadPart
);
903 ASSERT(NeedleRun
.RunEndVbn
.QuadPart
<= HaystackRun
->RunEndVbn
.QuadPart
);
904 Mcb
->Mapping
->Table
.CompareRoutine
= McbMappingCompare
;
905 RtlDeleteElementGenericTable(&Mcb
->Mapping
->Table
, HaystackRun
);
906 Mcb
->Mapping
->Table
.CompareRoutine
= McbMappingIntersectCompare
;
909 Mcb
->Mapping
->Table
.CompareRoutine
= McbMappingCompare
;
919 FsRtlRemoveLargeMcbEntry(IN PLARGE_MCB Mcb
,
921 IN LONGLONG SectorCount
)
923 DPRINT("FsRtlRemoveLargeMcbEntry Mcb %p, Vbn %I64d, SectorCount %I64d\n", Mcb
, Vbn
, SectorCount
);
925 KeAcquireGuardedMutex(Mcb
->GuardedMutex
);
926 FsRtlRemoveBaseMcbEntry(&(Mcb
->BaseMcb
), Vbn
, SectorCount
);
927 KeReleaseGuardedMutex(Mcb
->GuardedMutex
);
937 FsRtlResetBaseMcb(IN PBASE_MCB OpaqueMcb
)
939 PBASE_MCB_INTERNAL Mcb
= (PBASE_MCB_INTERNAL
)OpaqueMcb
;
940 PLARGE_MCB_MAPPING_ENTRY Element
;
942 while (RtlNumberGenericTableElements(&Mcb
->Mapping
->Table
) &&
943 (Element
= (PLARGE_MCB_MAPPING_ENTRY
)RtlGetElementGenericTable(&Mcb
->Mapping
->Table
, 0)))
945 RtlDeleteElementGenericTable(&Mcb
->Mapping
->Table
, Element
);
949 Mcb
->MaximumPairCount
= 0;
957 FsRtlResetLargeMcb(IN PLARGE_MCB Mcb
,
958 IN BOOLEAN SelfSynchronized
)
960 if (!SelfSynchronized
)
961 KeAcquireGuardedMutex(Mcb
->GuardedMutex
);
963 FsRtlResetBaseMcb(&Mcb
->BaseMcb
);
965 if (!SelfSynchronized
)
966 KeReleaseGuardedMutex(Mcb
->GuardedMutex
);
974 FsRtlSplitBaseMcb(IN PBASE_MCB OpaqueMcb
,
978 PBASE_MCB_INTERNAL Mcb
= (PBASE_MCB_INTERNAL
)OpaqueMcb
;
979 PLARGE_MCB_MAPPING_ENTRY Run
, InsertLowerRun
= NULL
, ExistingRun
= NULL
;
980 LARGE_MCB_MAPPING_ENTRY LowerRun
;
983 /* Traverse the tree */
984 for (Run
= (PLARGE_MCB_MAPPING_ENTRY
)RtlEnumerateGenericTable(&Mcb
->Mapping
->Table
, TRUE
);
986 Run
= (PLARGE_MCB_MAPPING_ENTRY
)RtlEnumerateGenericTable(&Mcb
->Mapping
->Table
, FALSE
))
988 /* unaffected run? */
989 /* FIXME: performance: effective skip of all 'lower' runs without traversing them */
990 if (Vbn
>= Run
->RunStartVbn
.QuadPart
) continue;
992 /* crossing run to be split?
993 * 'lower_run' is created on the original place; just shortened.
994 * current 'run' is shifted up later
996 if (Vbn
< Run
->RunEndVbn
.QuadPart
)
999 LowerRun
.RunEndVbn
.QuadPart
= Vbn
;
1000 /* FIXME: shift 'run->Lbn_start' ? */
1001 Run
->RunStartVbn
.QuadPart
= Vbn
;
1003 InsertLowerRun
= &LowerRun
;
1006 /* Shift the current 'run'.
1007 * Ordering is not changed in Generic Tree so I hope I do not need to reinsert it.
1009 Run
->RunStartVbn
.QuadPart
+= Amount
;
1010 ASSERT(Run
->RunEndVbn
.QuadPart
+ Amount
> Run
->RunEndVbn
.QuadPart
); /* overflow? */
1011 Run
->RunEndVbn
.QuadPart
+= Amount
;
1012 /* FIXME: shift 'run->Lbn_start' ? */
1014 /* continue the traversal */
1018 ExistingRun
= RtlInsertElementGenericTable(&Mcb
->Mapping
->Table
, InsertLowerRun
, sizeof(*InsertLowerRun
), &NewElement
);
1020 ASSERT(ExistingRun
== NULL
);
1022 return (InsertLowerRun
!= NULL
); /* the hole was successfuly created? */
1030 FsRtlSplitLargeMcb(IN PLARGE_MCB Mcb
,
1036 DPRINT("FsRtlSplitLargeMcb %p, Vbn %x, Amount %x\n", Mcb
, (ULONG
)Vbn
, (ULONG
)Amount
);
1038 KeAcquireGuardedMutex(Mcb
->GuardedMutex
);
1039 Result
= FsRtlSplitBaseMcb(&(Mcb
->BaseMcb
),
1042 KeReleaseGuardedMutex(Mcb
->GuardedMutex
);
1044 DPRINT("Done %u\n", Result
);
1054 FsRtlTruncateBaseMcb(IN PBASE_MCB OpaqueMcb
,
1057 DPRINT("Mcb=%p, Vbn=%I64d\n", OpaqueMcb
, Vbn
);
1058 FsRtlRemoveBaseMcbEntry(OpaqueMcb
, Vbn
, MAXLONGLONG
- Vbn
+ 1);
1066 FsRtlTruncateLargeMcb(IN PLARGE_MCB Mcb
,
1069 DPRINT("FsRtlTruncateLargeMcb %p Vbn %x\n", Mcb
, (ULONG
)Vbn
);
1070 KeAcquireGuardedMutex(Mcb
->GuardedMutex
);
1071 FsRtlTruncateBaseMcb(&(Mcb
->BaseMcb
), Vbn
);
1072 KeReleaseGuardedMutex(Mcb
->GuardedMutex
);
1081 FsRtlUninitializeBaseMcb(IN PBASE_MCB Mcb
)
1083 FsRtlResetBaseMcb(Mcb
);
1085 if ((Mcb
->PoolType
== PagedPool
)/* && (Mcb->MaximumPairCount == MAXIMUM_PAIR_COUNT)*/)
1087 ExFreeToPagedLookasideList(&FsRtlFirstMappingLookasideList
,
1092 ExFreePoolWithTag(Mcb
->Mapping
, 'FSBC');
1101 FsRtlUninitializeLargeMcb(IN PLARGE_MCB Mcb
)
1103 if (Mcb
->GuardedMutex
)
1105 ExFreeToNPagedLookasideList(&FsRtlFastMutexLookasideList
,
1107 FsRtlUninitializeBaseMcb(&(Mcb
->BaseMcb
));