Author: hpoussin
Date: Thu Nov 13 20:11:05 2014
New Revision: 65398
URL: http://svn.reactos.org/svn/reactos?rev=65398&view=rev
Log:
[NTOS:FSRTL] Fix lots of problems in large MCB implementation
KM tests now pass, except one error case which is not correctly handled.
Modified:
trunk/reactos/ntoskrnl/fsrtl/largemcb.c
Modified: trunk/reactos/ntoskrnl/fsrtl/largemcb.c
URL:
http://svn.reactos.org/svn/reactos/trunk/reactos/ntoskrnl/fsrtl/largemcb.c?rev=65398&r1=65397&r2=65398&view=diff
==============================================================================
--- trunk/reactos/ntoskrnl/fsrtl/largemcb.c [iso-8859-1] (original)
+++ trunk/reactos/ntoskrnl/fsrtl/largemcb.c [iso-8859-1] Thu Nov 13
20:11:05 2014
@@ -48,13 +48,6 @@
{{-1}}, /* ignored */
};
-static PLARGE_MCB_MAPPING_ENTRY run_compare_func_last_a_run;
-static PLARGE_MCB_MAPPING_ENTRY run_compare_func_last_b_run;
-static PLARGE_MCB_MAPPING_ENTRY run_compare_func_minus_a_run; /* last run
where we returned -1 */
-static PLARGE_MCB_MAPPING_ENTRY run_compare_func_minus_b_run;
-static PLARGE_MCB_MAPPING_ENTRY run_compare_func_plus_a_run; /* last run
where we returned +1 */
-static PLARGE_MCB_MAPPING_ENTRY run_compare_func_plus_b_run;
-
static PVOID NTAPI McbMappingAllocate(PRTL_GENERIC_TABLE Table, CLONG Bytes)
{
PVOID Result;
@@ -78,76 +71,43 @@
PVOID PtrB)
{
PLARGE_MCB_MAPPING_ENTRY A = PtrA, B = PtrB;
- INT r;
RTL_GENERIC_COMPARE_RESULTS Res;
- /*return
- (A->RunStartVbn.QuadPart + A->SectorCount.QuadPart <
B->RunStartVbn.QuadPart) ? GenericLessThan :
- (A->RunStartVbn.QuadPart > B->RunStartVbn.QuadPart +
B->SectorCount.QuadPart) ? GenericGreaterThan : GenericEqual;*/
-
- /*return
- (A->RunEndVbn.QuadPart < B->RunStartVbn.QuadPart) ? GenericLessThan :
- (A->RunStartVbn.QuadPart > B->RunEndVbn.QuadPart) ? GenericGreaterThan
: GenericEqual;*/
-
- run_compare_func_last_a_run = A;
- run_compare_func_last_b_run = B;
-
- if (1
- && !(r = (A->RunStartVbn.QuadPart > B->RunStartVbn.QuadPart) -
(A->RunStartVbn.QuadPart < B->RunStartVbn.QuadPart))
- && !(r = (A->RunEndVbn.QuadPart > B->RunEndVbn.QuadPart ) -
(A->RunEndVbn.QuadPart < B->RunEndVbn.QuadPart )))
- {
- r = 0;
- }
-
- //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);
-
- /*
- negative value if a < b;
- zero if a = b;
- positive value if a > b.
- */
- if (r < 0)
+ ASSERT(A);
+ ASSERT(B);
+
+ if (A->RunStartVbn.QuadPart == B->RunStartVbn.QuadPart &&
A->RunEndVbn.QuadPart == B->RunEndVbn.QuadPart)
+ Res = GenericEqual;
+ else if (A->RunEndVbn.QuadPart <= B->RunStartVbn.QuadPart)
Res = GenericLessThan;
- else if (r > 0)
+ else if (A->RunEndVbn.QuadPart >= B->RunStartVbn.QuadPart)
+ Res = GenericGreaterThan;
+ else
+ {
+ ASSERT(FALSE);
+ Res = GenericEqual;
+ }
+
+ return Res;
+}
+
+static RTL_GENERIC_COMPARE_RESULTS NTAPI
McbMappingIntersectCompare(PRTL_GENERIC_TABLE Table, PVOID PtrA, PVOID PtrB)
+{
+ PLARGE_MCB_MAPPING_ENTRY A = PtrA, B = PtrB;
+ RTL_GENERIC_COMPARE_RESULTS Res;
+
+ if (A->RunStartVbn.QuadPart <= B->RunStartVbn.QuadPart &&
A->RunEndVbn.QuadPart > B->RunStartVbn.QuadPart)
+ Res = GenericEqual;
+ else if (A->RunStartVbn.QuadPart >= B->RunStartVbn.QuadPart &&
B->RunEndVbn.QuadPart > A->RunStartVbn.QuadPart)
+ Res = GenericEqual;
+ else if (A->RunStartVbn.QuadPart < B->RunStartVbn.QuadPart)
+ Res = GenericLessThan;
+ else if (A->RunStartVbn.QuadPart > B->RunStartVbn.QuadPart)
Res = GenericGreaterThan;
else
Res = GenericEqual;
- if (Res == GenericLessThan)
- {
- run_compare_func_minus_a_run = A;
- run_compare_func_minus_b_run = B;
- }
- else if (Res == GenericGreaterThan)
- {
- run_compare_func_plus_a_run = A;
- run_compare_func_plus_b_run = B;
- }
-
return Res;
-}
-
-static RTL_GENERIC_COMPARE_RESULTS NTAPI
McbMappingIntersectCompare(PRTL_GENERIC_TABLE Table, PVOID PtrA, PVOID PtrB)
-{
- PLARGE_MCB_MAPPING_ENTRY HaystackRun = PtrA, NeedleRun = PtrB;
- LARGE_MCB_MAPPING_ENTRY CommonRun;
- RTL_GENERIC_COMPARE_RESULTS Res;
-
- if (!HaystackRun) return GenericEqual;
- if (HaystackRun->RunEndVbn.QuadPart <= HaystackRun->RunStartVbn.QuadPart)
return GenericEqual;
-
- if (!NeedleRun) return GenericEqual;
- if (NeedleRun->RunEndVbn.QuadPart <= NeedleRun->RunStartVbn.QuadPart)
return GenericEqual;
-
- CommonRun.RunStartVbn.QuadPart = MAX(HaystackRun->RunStartVbn.QuadPart,
NeedleRun->RunStartVbn.QuadPart);
- CommonRun.RunEndVbn.QuadPart = MIN(HaystackRun->RunEndVbn.QuadPart ,
NeedleRun->RunEndVbn.QuadPart );
-
- if (CommonRun.RunEndVbn.QuadPart > CommonRun.RunStartVbn.QuadPart)
- return GenericEqual;
-
- Res = McbMappingCompare(Table, NeedleRun, HaystackRun);
- ASSERT(Res != GenericEqual); /* otherwise we would hit it by
'common_run' */
- return Res;
}
@@ -176,13 +136,11 @@
{
PBASE_MCB_INTERNAL Mcb = (PBASE_MCB_INTERNAL)OpaqueMcb;
LARGE_MCB_MAPPING_ENTRY Node, NeedleRun;
- PLARGE_MCB_MAPPING_ENTRY LowerRun, HigherRun, Existing = NULL;
+ PLARGE_MCB_MAPPING_ENTRY LowerRun, HigherRun;
BOOLEAN NewElement;
if (Vbn < 0) return FALSE;
if (SectorCount <= 0) return FALSE;
-
- //DPRINT("Mcb=%p,Vbn=%lld,Lbn=%lld,SectorCount=%lld\n", Mcb, Vbn, Lbn,
SectorCount);
/* clean any possible previous entries in our range */
FsRtlRemoveBaseMcbEntry(OpaqueMcb, Vbn, SectorCount);
@@ -199,12 +157,13 @@
/* optionally merge with lower run */
NeedleRun.RunStartVbn.QuadPart = Node.RunStartVbn.QuadPart - 1;
NeedleRun.RunEndVbn.QuadPart = NeedleRun.RunStartVbn.QuadPart + 1;
- //if ((LowerRun =
g_tree_search(Mcb_priv->gtree,(GCompareFunc)run_intersect_compare_func,
&NeedleRun)))
+ NeedleRun.StartingLbn.QuadPart = ~0ULL;
Mcb->Mapping->Table.CompareRoutine = McbMappingIntersectCompare;
if ((LowerRun = RtlLookupElementGenericTable(&Mcb->Mapping->Table,
&NeedleRun)))
{
ASSERT(LowerRun->RunEndVbn.QuadPart == Node.RunStartVbn.QuadPart);
Node.RunStartVbn.QuadPart = LowerRun->RunStartVbn.QuadPart;
+ Node.StartingLbn.QuadPart = LowerRun->StartingLbn.QuadPart;
Mcb->Mapping->Table.CompareRoutine = McbMappingCompare;
RtlDeleteElementGenericTable(&Mcb->Mapping->Table, LowerRun);
DPRINT("Intersecting lower run found (%I64d,%I64d) Lbn: %I64d\n",
LowerRun->RunStartVbn.QuadPart, LowerRun->RunEndVbn.QuadPart,
LowerRun->StartingLbn.QuadPart);
@@ -213,7 +172,6 @@
/* optionally merge with higher run */
NeedleRun.RunStartVbn.QuadPart = Node.RunEndVbn.QuadPart;
NeedleRun.RunEndVbn.QuadPart = NeedleRun.RunStartVbn.QuadPart + 1;
- //if ((HigherRun =
g_tree_search(Mcb_priv->gtree,(GCompareFunc)run_intersect_compare_func,
&NeedleRun)))
Mcb->Mapping->Table.CompareRoutine = McbMappingIntersectCompare;
if ((HigherRun = RtlLookupElementGenericTable(&Mcb->Mapping->Table,
&NeedleRun)))
{
@@ -226,9 +184,11 @@
Mcb->Mapping->Table.CompareRoutine = McbMappingCompare;
/* finally insert the resulting run */
- Existing = RtlInsertElementGenericTable(&Mcb->Mapping->Table, &Node,
sizeof(Node), &NewElement);
- DPRINT("Existing %p, NewElement %u\n", Existing, NewElement);
+ RtlInsertElementGenericTable(&Mcb->Mapping->Table, &Node, sizeof(Node),
&NewElement);
ASSERT(NewElement);
+ Node.RunStartVbn.QuadPart = Vbn;
+ Node.RunEndVbn.QuadPart = Vbn + SectorCount;
+ Node.StartingLbn.QuadPart = Lbn;
// NB: Two consecutive runs can only be merged, if actual LBNs also match!
@@ -294,7 +254,7 @@
{
BOOLEAN Result;
- DPRINT("Mcb %p Vbn %lld Lbn %lld SectorCount %lld\n", Mcb, Vbn, Lbn,
SectorCount);
+ DPRINT("Mcb %p Vbn %I64d Lbn %I64d SectorCount %I64d\n", Mcb, Vbn, Lbn,
SectorCount);
KeAcquireGuardedMutex(Mcb->GuardedMutex);
Result = FsRtlAddBaseMcbEntry(&(Mcb->BaseMcb),
@@ -584,7 +544,10 @@
if (Run->RunEndVbn.QuadPart <= Vbn)
{
RunFoundLower = Run;
- RunIndex += 2;
+ if (Run->StartingLbn.QuadPart > 0)
+ {
+ RunIndex += 2;
+ }
/* continue the traversal; not yet crossed by the run */
continue;
}
@@ -636,7 +599,7 @@
if (SectorCountFromStartingLbn)
*SectorCountFromStartingLbn = RunFoundHigher->RunStartVbn.QuadPart
- RunFoundLower->RunEndVbn.QuadPart;
if (Index)
- *Index = RunIndex;
+ *Index = RunIndex - 2;
return TRUE;
}
@@ -660,7 +623,7 @@
{
BOOLEAN Result;
- DPRINT("FsRtlLookupLargeMcbEntry Mcb %p Vbn %x\n", Mcb, (ULONG)Vbn);
+ DPRINT("FsRtlLookupLargeMcbEntry Mcb %p Vbn %I64d\n", Mcb, Vbn);
KeAcquireGuardedMutex(Mcb->GuardedMutex);
Result = FsRtlLookupBaseMcbEntry(&(Mcb->BaseMcb),
@@ -684,42 +647,47 @@
OUT PLONGLONG Lbn,
OUT PULONG Index OPTIONAL)
{
- LARGE_MCB_MAPPING_ENTRY NeedleRunTop;
- PLARGE_MCB_MAPPING_ENTRY FoundRun;
- ULONG Runs;
-
- NeedleRunTop.RunStartVbn.QuadPart = MAXLONGLONG - 1;
- NeedleRunTop.RunEndVbn.QuadPart = MAXLONGLONG;
- NeedleRunTop.StartingLbn.QuadPart = ~0ull; /* ignored*/
-
- run_compare_func_last_a_run = NULL;
- run_compare_func_last_b_run = NULL;
-
- FoundRun = RtlLookupElementGenericTable(&Mcb->Mapping->Table,
&NeedleRunTop);
- ASSERT(FoundRun == NULL);
-
- if (run_compare_func_last_a_run == NULL)
- {
- ASSERT(run_compare_func_last_b_run == NULL);
-
- *Vbn = -1;
- *Lbn = -1;
- if (Index) *Index = 0;
+ ULONG RunIndex = 0;
+ PLARGE_MCB_MAPPING_ENTRY Run, RunFound = NULL;
+ LONGLONG LastVbn = 0;
+
+ for (Run =
(PLARGE_MCB_MAPPING_ENTRY)RtlEnumerateGenericTable(&Mcb->Mapping->Table, TRUE);
+ Run;
+ Run =
(PLARGE_MCB_MAPPING_ENTRY)RtlEnumerateGenericTable(&Mcb->Mapping->Table, FALSE))
+ {
+ /* Take care when we must emulate missing 'hole' runs. */
+ if (Run->RunStartVbn.QuadPart > LastVbn)
+ {
+ RunIndex++;
+ }
+ LastVbn = Run->RunEndVbn.QuadPart;
+ RunIndex++;
+ RunFound = Run;
+ }
+
+ if (!RunFound)
+ {
return FALSE;
}
- ASSERT(run_compare_func_last_a_run != &NeedleRunTop);
- ASSERT(run_compare_func_last_b_run == &NeedleRunTop);
-
- *Vbn = run_compare_func_last_a_run->RunEndVbn.QuadPart - 1;
- *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);
-
+
+ if (Vbn)
+ {
+ *Vbn = RunFound->RunEndVbn.QuadPart - 1;
+ }
+ if (Lbn)
+ {
+ if (1)
+ {
+ *Lbn = RunFound->StartingLbn.QuadPart +
(RunFound->RunEndVbn.QuadPart - RunFound->RunStartVbn.QuadPart) - 1;
+ }
+ else
+ {
+ *Lbn = ~0ULL;
+ }
+ }
if (Index)
{
- Runs = FsRtlNumberOfRunsInBaseMcb((PBASE_MCB)Mcb);
-
- /* There must be some runs if we found _something_. */
- ASSERT(Runs > 0);
- *Index = Runs - 1;
+ *Index = RunIndex - 1;
}
return TRUE;
@@ -876,15 +844,14 @@
PLARGE_MCB_MAPPING_ENTRY HaystackRun;
if (Vbn < 0 || SectorCount <= 0) return FALSE;
- /* FIXME: We are unable to delete the absolutely last sector G_MAXINT64 by
this implementation! */
if (Vbn + SectorCount <= Vbn) return FALSE;
NeedleRun.RunStartVbn.QuadPart = Vbn;
NeedleRun.RunEndVbn.QuadPart = Vbn + SectorCount;
+ NeedleRun.StartingLbn.QuadPart = ~0ULL;
/* adjust/destroy all intersecting ranges */
Mcb->Mapping->Table.CompareRoutine = McbMappingIntersectCompare;
- //while ((HaystackRun =
g_tree_search(Mcb_priv->gtree,(GCompareFunc)run_intersect_compare_func,&needle_run)))
while ((HaystackRun = RtlLookupElementGenericTable(&Mcb->Mapping->Table,
&NeedleRun)))
{
if (HaystackRun->RunStartVbn.QuadPart < NeedleRun.RunStartVbn.QuadPart)
@@ -900,7 +867,7 @@
else
{
ASSERT(NeedleRun.RunStartVbn.QuadPart >=
HaystackRun->RunStartVbn.QuadPart);
- ASSERT(NeedleRun.RunEndVbn.QuadPart <=
HaystackRun->RunEndVbn.QuadPart);
+ //ASSERT(NeedleRun.RunEndVbn.QuadPart <=
HaystackRun->RunEndVbn.QuadPart);
Mcb->Mapping->Table.CompareRoutine = McbMappingCompare;
RtlDeleteElementGenericTable(&Mcb->Mapping->Table, HaystackRun);
Mcb->Mapping->Table.CompareRoutine = McbMappingIntersectCompare;
@@ -977,7 +944,6 @@
{
PBASE_MCB_INTERNAL Mcb = (PBASE_MCB_INTERNAL)OpaqueMcb;
PLARGE_MCB_MAPPING_ENTRY Run, InsertLowerRun = NULL, ExistingRun = NULL;
- LARGE_MCB_MAPPING_ENTRY LowerRun;
BOOLEAN NewElement;
/* Traverse the tree */
@@ -987,7 +953,7 @@
{
/* unaffected run? */
/* FIXME: performance: effective skip of all 'lower' runs without
traversing them */
- if (Vbn >= Run->RunStartVbn.QuadPart) continue;
+ if (Vbn >= Run->RunEndVbn.QuadPart) { DPRINT("Skipping it\n");
continue; }
/* crossing run to be split?
* 'lower_run' is created on the original place; just shortened.
@@ -995,12 +961,10 @@
*/
if (Vbn < Run->RunEndVbn.QuadPart)
{
- LowerRun = *Run;
- LowerRun.RunEndVbn.QuadPart = Vbn;
/* FIXME: shift 'run->Lbn_start' ? */
Run->RunStartVbn.QuadPart = Vbn;
- InsertLowerRun = &LowerRun;
+ InsertLowerRun = NULL;
}
/* Shift the current 'run'.
@@ -1019,7 +983,7 @@
ASSERT(ExistingRun == NULL);
- return (InsertLowerRun != NULL); /* the hole was successfuly created? */
+ return TRUE;
}
/*
@@ -1033,7 +997,7 @@
{
BOOLEAN Result;
- DPRINT("FsRtlSplitLargeMcb %p, Vbn %x, Amount %x\n", Mcb, (ULONG)Vbn,
(ULONG)Amount);
+ DPRINT("FsRtlSplitLargeMcb %p, Vbn %I64d, Amount %I64d\n", Mcb, Vbn,
Amount);
KeAcquireGuardedMutex(Mcb->GuardedMutex);
Result = FsRtlSplitBaseMcb(&(Mcb->BaseMcb),
@@ -1055,7 +1019,7 @@
IN LONGLONG Vbn)
{
DPRINT("Mcb=%p, Vbn=%I64d\n", OpaqueMcb, Vbn);
- FsRtlRemoveBaseMcbEntry(OpaqueMcb, Vbn, MAXLONGLONG - Vbn + 1);
+ FsRtlRemoveBaseMcbEntry(OpaqueMcb, Vbn, MAXLONG - Vbn + 1);
}
/*
@@ -1066,7 +1030,7 @@
FsRtlTruncateLargeMcb(IN PLARGE_MCB Mcb,
IN LONGLONG Vbn)
{
- DPRINT("FsRtlTruncateLargeMcb %p Vbn %x\n", Mcb, (ULONG)Vbn);
+ DPRINT("FsRtlTruncateLargeMcb %p Vbn %I64d\n", Mcb, Vbn);
KeAcquireGuardedMutex(Mcb->GuardedMutex);
FsRtlTruncateBaseMcb(&(Mcb->BaseMcb), Vbn);
KeReleaseGuardedMutex(Mcb->GuardedMutex);
