[hpoussin] 65398: [NTOS:FSRTL] Fix lots of problems in large MCB implementation KM tests now pass, except one error case which is not correctly handled.

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?…
==============================================================================
--- 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);