[ros-diffs] [tthompson] 71407: [FsRtl] -Rewrote FsRtlGetNextBaseMcbEntry(), FsRtlLookupBaseMcbEntry(), and FsRtlNumberOfRunsInBaseMcb() using simpler logic. -Commented-out StaticRunBelow0, since it's no longer...

Author: tthompson
Date: Thu May 26 12:27:16 2016
New Revision: 71407

URL: http://svn.reactos.org/svn/reactos?rev=71407&view=rev
Log:
[FsRtl]
-Rewrote FsRtlGetNextBaseMcbEntry(), FsRtlLookupBaseMcbEntry(), and
FsRtlNumberOfRunsInBaseMcb() using simpler logic.
-Commented-out StaticRunBelow0, since it's no longer used.

These changes enable kmtest_ FsRtlMcb to run without failure.

Modified:
    branches/GSoC_2016/NTFS/ntoskrnl/fsrtl/largemcb.c

Modified: branches/GSoC_2016/NTFS/ntoskrnl/fsrtl/largemcb.c
URL:
http://svn.reactos.org/svn/reactos/branches/GSoC_2016/NTFS/ntoskrnl/fsrtl/l…
==============================================================================
--- branches/GSoC_2016/NTFS/ntoskrnl/fsrtl/largemcb.c	[iso-8859-1] (original)
+++ branches/GSoC_2016/NTFS/ntoskrnl/fsrtl/largemcb.c	[iso-8859-1] Thu May 26 12:27:16
2016
@@ -42,11 +42,13 @@
     PLARGE_MCB_MAPPING Mapping;
 } BASE_MCB_INTERNAL, *PBASE_MCB_INTERNAL;
 
+/*
 static LARGE_MCB_MAPPING_ENTRY StaticRunBelow0 = {
-    {{-1}}, /* ignored */
+    {{-1}}, // ignored
     {{0}},
-    {{-1}}, /* ignored */
+    {{-1}}, // ignored
 };
+*/
 
 static PVOID NTAPI McbMappingAllocate(PRTL_GENERIC_TABLE Table, CLONG Bytes)
 {
@@ -321,107 +323,60 @@
 BOOLEAN
 NTAPI
 FsRtlGetNextBaseMcbEntry(IN PBASE_MCB OpaqueMcb,
-                         IN ULONG RunIndex,
-                         OUT PLONGLONG Vbn,
-                         OUT PLONGLONG Lbn,
-                         OUT PLONGLONG SectorCount)
-{
-    BOOLEAN Result = FALSE;
+    IN ULONG RunIndex,
+    OUT PLONGLONG Vbn,
+    OUT PLONGLONG Lbn,
+    OUT PLONGLONG SectorCount)
+{
     PBASE_MCB_INTERNAL Mcb = (PBASE_MCB_INTERNAL)OpaqueMcb;
-    ULONG RunIndexRemaining;
-    PLARGE_MCB_MAPPING_ENTRY Run, RunFound = NULL, RunFoundLower = NULL, RunFoundHigher =
NULL;
-    BOOLEAN First = TRUE;
-
-    DPRINT("FsRtlGetNextBaseMcbEntry(%p, %d, %p, %p, %p)\n", OpaqueMcb,
RunIndex, Vbn, Lbn, SectorCount);
-
-    RunIndexRemaining = RunIndex;
-
-    /* Traverse the tree */
+    PLARGE_MCB_MAPPING_ENTRY Run = NULL;
+    ULONG CurrentIndex = 0;
+    ULONGLONG LastVbn = 0;
+    ULONGLONG LastSectorCount = 0;
+    ULONG TableElementsConsumed = 0;
+
+    // Traverse the tree 
     for (Run =
(PLARGE_MCB_MAPPING_ENTRY)RtlEnumerateGenericTable(&Mcb->Mapping->Table, TRUE);
-        Run;
+    Run;
         Run =
(PLARGE_MCB_MAPPING_ENTRY)RtlEnumerateGenericTable(&Mcb->Mapping->Table,
FALSE))
     {
-        if (First)
+        TableElementsConsumed++; // we consume one element in the table everytime we call
RtlEnumeratGenericTable
+
+        // is the current index a hole?
+        if (Run->RunStartVbn.QuadPart > (LastVbn + LastSectorCount))
         {
-            /* Take care when we must emulate missing 'hole' run at start of our
run list. */
-            if (Run->RunStartVbn.QuadPart > 0)
+            // Is this the index we're looking for?
+            if (RunIndex == CurrentIndex)
             {
-                if (RunIndexRemaining == 0)
-                {
-                    RunFoundLower = &StaticRunBelow0;
-                    RunFoundHigher = Run;
-
-                    /* stop the traversal */
-                    break;
-                }
-                /* If someone wants RunIndex #1 we are already on it. */
-                RunIndexRemaining--;
+                *Vbn = LastVbn + LastSectorCount;
+                *Lbn = -1;
+                *SectorCount = Run->RunStartVbn.QuadPart - *Vbn;
+
+                return TRUE;
             }
-            First = FALSE;
+
+            CurrentIndex++;
         }
 
-        if (RunIndexRemaining > 0)
+        if (RunIndex == CurrentIndex)
         {
-            /* FIXME: performance: non-linear direct seek to the requested RunIndex */
-            RunIndexRemaining--;
-            if (RunIndexRemaining == 0)
-                RunFoundLower = Run;
-            else
-                RunIndexRemaining--;
-
-            /* continue the traversal */
-            continue;
+            *Vbn = Run->RunStartVbn.QuadPart;
+            *Lbn = Run->StartingLbn.QuadPart;
+            *SectorCount = Run->RunEndVbn.QuadPart - Run->RunStartVbn.QuadPart;
+
+            return TRUE;
         }
 
-        if (RunFoundLower)
-            RunFoundHigher = Run;
-        else
-            RunFound = Run;
-
-        /* stop the traversal */
-        break;
-    }
-
-    if (RunFound) DPRINT("RunFound(%lu %lu %lu)\n",
RunFound->RunStartVbn.LowPart, RunFound->RunEndVbn.LowPart,
RunFound->StartingLbn.LowPart);
-    if (RunFoundLower) DPRINT("RunFoundLower(%lu %lu %lu)\n",
RunFoundLower->RunStartVbn.LowPart, RunFoundLower->RunEndVbn.LowPart,
RunFoundLower->StartingLbn.LowPart);
-    if (RunFoundHigher) DPRINT("RunFoundHigher(%lu %lu %lu)\n",
RunFoundHigher->RunStartVbn.LowPart, RunFoundHigher->RunEndVbn.LowPart,
RunFoundHigher->StartingLbn.LowPart);
-
-    if (RunFound)
-    {
-        ASSERT(RunFoundLower == NULL);
-        ASSERT(RunFoundHigher == NULL);
-
-        if (Vbn)
-            *Vbn = RunFound->RunStartVbn.QuadPart;
-        if (Lbn)
-            *Lbn = RunFound->StartingLbn.QuadPart;
-        if (SectorCount)
-            *SectorCount = RunFound->RunEndVbn.QuadPart -
RunFound->RunStartVbn.QuadPart;
-
-        Result = TRUE;
-        goto quit;
-    }
-
-    if (RunFoundLower && RunFoundHigher)
-    {
-        //ASSERT(RunFoundHigher != NULL);
-
-        if (Vbn)
-            *Vbn = RunFoundLower->RunEndVbn.QuadPart;
-        if (Lbn)
-            *Lbn = -1;
-        if (SectorCount)
-            *SectorCount = RunFoundHigher->RunStartVbn.QuadPart -
RunFoundLower->RunEndVbn.QuadPart;
-
-        Result = TRUE;
-        goto quit;
-    }
-
-    ASSERT(RunFoundHigher == NULL);
-
-quit:
-    DPRINT("FsRtlGetNextBaseMcbEntry(%p, %d, %p, %p, %p) = %d (%I64d, %I64d,
%I64d)\n", Mcb, RunIndex, Vbn, Lbn, SectorCount, Result, *Vbn, *Lbn, *SectorCount);
-    return Result;
+        CurrentIndex++;
+        LastVbn = Run->RunStartVbn.QuadPart;
+        LastSectorCount = Run->RunEndVbn.QuadPart - Run->RunStartVbn.QuadPart;
+    }
+
+    // these values are meaningless when returning false (but setting them can be helpful
for debugging purposes)
+    *Vbn = -7777;
+    *Lbn = -7777;
+    *SectorCount = -7777;
+    return FALSE;
 }
 
 /*
@@ -538,125 +493,53 @@
 }
 
 /*
- * @unimplemented
+ * @implemented
  */
 BOOLEAN
 NTAPI
 FsRtlLookupBaseMcbEntry(IN PBASE_MCB OpaqueMcb,
-                        IN LONGLONG Vbn,
-                        OUT PLONGLONG Lbn OPTIONAL,
-                        OUT PLONGLONG SectorCountFromLbn OPTIONAL,
-                        OUT PLONGLONG StartingLbn OPTIONAL,
-                        OUT PLONGLONG SectorCountFromStartingLbn OPTIONAL,
-                        OUT PULONG Index OPTIONAL)
-{
-    BOOLEAN Result = FALSE;
-    PBASE_MCB_INTERNAL Mcb = (PBASE_MCB_INTERNAL)OpaqueMcb;
-
-    ULONG RunIndex = 0;
-    PLARGE_MCB_MAPPING_ENTRY Run, RunFound = NULL, RunFoundLower = NULL, RunFoundHigher =
NULL;
-    BOOLEAN First = TRUE;
-
-    DPRINT("FsRtlLookupBaseMcbEntry(%p, %I64d, %p, %p, %p, %p, %p)\n",
OpaqueMcb, Vbn, Lbn, SectorCountFromLbn, StartingLbn, SectorCountFromStartingLbn, Index);
-
-    /* Traverse the tree */
-    for (Run =
(PLARGE_MCB_MAPPING_ENTRY)RtlEnumerateGenericTable(&Mcb->Mapping->Table, TRUE);
-        Run;
-        Run =
(PLARGE_MCB_MAPPING_ENTRY)RtlEnumerateGenericTable(&Mcb->Mapping->Table,
FALSE))
-    {
-        if (First)
+    IN LONGLONG Vbn,
+    OUT PLONGLONG Lbn OPTIONAL,
+    OUT PLONGLONG SectorCountFromLbn OPTIONAL,
+    OUT PLONGLONG StartingLbn OPTIONAL,
+    OUT PLONGLONG SectorCountFromStartingLbn OPTIONAL,
+    OUT PULONG Index OPTIONAL)
+{
+    ULONG i;
+    LONGLONG LastVbn = 0, LastLbn = 0, Count = 0;   // the last values we've found
during traversal
+
+    for (i = 0; FsRtlGetNextBaseMcbEntry(OpaqueMcb, i, &LastVbn, &LastLbn,
&Count); i++)
+    {
+        // have we reached the target mapping?
+        if (Vbn < LastVbn + Count)
         {
-            /* Take care when we must emulate missing 'hole' run at start of our
run list. */
-            if (Run->RunStartVbn.QuadPart > 0)
+            if (Lbn)
             {
-                RunIndex++;
-                RunFoundLower = &StaticRunBelow0;
+                if (LastLbn == -1)
+                    *Lbn = -1;
+                else
+                    *Lbn = LastLbn + (Vbn - LastVbn);
             }
-            First = FALSE;
+
+            if (SectorCountFromLbn)
+                *SectorCountFromLbn = LastVbn + Count - Vbn;
+            if (StartingLbn)
+                *StartingLbn = LastLbn;
+            if (SectorCountFromStartingLbn)
+                *SectorCountFromStartingLbn = LastVbn + Count - LastVbn;
+            if (Index)
+                *Index = i;
+
+            return TRUE;
         }
-
-        if (Run->RunStartVbn.QuadPart <= Vbn && Vbn <
Run->RunEndVbn.QuadPart)
-        {
-            RunFound = Run;
-            RunFoundLower = NULL;
-            /* stop the traversal; hit */
-            break;
-        }
-
-        if (Run->RunEndVbn.QuadPart <= Vbn)
-        {
-            RunFoundLower = Run;
-            if (Run->StartingLbn.QuadPart > 0)
-            {
-              RunIndex += 2;
-            }
-            /* continue the traversal; not yet crossed by the run */
-            continue;
-        }
-
-        if (Vbn < Run->RunStartVbn.QuadPart)
-        {
-            RunFoundHigher = Run;
-            RunIndex++;
-            /* stop the traversal; the run skipped us */
-            break;
-        }
-
-        ASSERT(FALSE);
-        /* stop the traversal */
-        break;
-    }
-
-    if (RunFound)
-    {
-        ASSERT(RunFoundLower == NULL);
-        ASSERT(RunFoundHigher == NULL);
-
-        if (Lbn)
-            *Lbn = RunFound->StartingLbn.QuadPart + (Vbn -
RunFound->RunStartVbn.QuadPart);
-
-        if (SectorCountFromLbn)	/* FIXME: 'after' means including current
'Lbn' or without it? */
-            *SectorCountFromLbn = RunFound->RunEndVbn.QuadPart - Vbn;
-        if (StartingLbn)
-            *StartingLbn = RunFound->StartingLbn.QuadPart;
-        if (SectorCountFromStartingLbn)
-            *SectorCountFromStartingLbn = RunFound->RunEndVbn.QuadPart -
RunFound->RunStartVbn.QuadPart;
-        if (Index)
-            *Index = RunIndex;
-
-        Result = TRUE;
-        goto quit;
-    }
-
-    if (RunFoundHigher)
-    {
-        /* search for hole */
-        ASSERT(RunFoundLower != NULL);
-
-        if (Lbn)
-            *Lbn = ~0ull;
-        if (SectorCountFromLbn)	/* FIXME: 'after' means including current
'Lbn' or without it? */
-            *SectorCountFromLbn = RunFoundHigher->RunStartVbn.QuadPart - Vbn;
-        if (StartingLbn)
-            *StartingLbn = ~0ull;
-        if (SectorCountFromStartingLbn)
-            *SectorCountFromStartingLbn = RunFoundHigher->RunStartVbn.QuadPart -
RunFoundLower->RunEndVbn.QuadPart;
-        if (Index)
-            *Index = RunIndex - 2;
-
-        Result = TRUE;
-        goto quit;
-    }
-
-    /* We may have some 'RunFoundLower'. */
-
-quit:
-    DPRINT("FsRtlLookupBaseMcbEntry(%p, %I64d, %p, %p, %p, %p, %p) = %d (%I64d,
%I64d, %I64d, %I64d, %d)\n",
-           OpaqueMcb, Vbn, Lbn, SectorCountFromLbn, StartingLbn,
SectorCountFromStartingLbn, Index, Result,
-           (Lbn ? *Lbn : (ULONGLONG)-1), (SectorCountFromLbn ? *SectorCountFromLbn :
(ULONGLONG)-1), (StartingLbn ? *StartingLbn : (ULONGLONG)-1),
-           (SectorCountFromStartingLbn ? *SectorCountFromStartingLbn : (ULONGLONG)-1),
(Index ? *Index : (ULONG)-1));
-
-    return Result;
+    }
+
+    if (Lbn)
+        *Lbn = -1;
+    if (StartingLbn)
+        *StartingLbn = -1;
+
+    return FALSE;
 }
 
 /*
@@ -848,28 +731,18 @@
 NTAPI
 FsRtlNumberOfRunsInBaseMcb(IN PBASE_MCB OpaqueMcb)
 {
-    PBASE_MCB_INTERNAL Mcb = (PBASE_MCB_INTERNAL)OpaqueMcb;
-    LONGLONG LbnAtVbn0 = -1;
     ULONG NumberOfRuns = 0;
+    LONGLONG Vbn, Lbn, Count;
+    int i;
 
     DPRINT("FsRtlNumberOfRunsInBaseMcb(%p)\n", OpaqueMcb);
 
-    if (Mcb->PairCount == 0) goto quit;
-
-    FsRtlLookupBaseMcbEntry(OpaqueMcb,
-        0,                           /* Vbn */
-        &LbnAtVbn0,                  /* Lbn */
-        NULL, NULL, NULL, NULL);     /* 4 output arguments - not interested in them */
-
-
-    /* Return the count */
-    //return Mcb->PairCount;
-	/* Return the number of 'real' and 'hole' runs.
-	 * If we do not have sector 0 as 'real' emulate a 'hole' there.
-	 */
-    NumberOfRuns = Mcb->PairCount * 2 - (LbnAtVbn0 != -1 ? 1 : 0);	/* include holes as
runs */
-
-quit:
+    // Count how many Mcb entries there are
+    for (i = 0; FsRtlGetNextBaseMcbEntry(OpaqueMcb, i, &Vbn, &Lbn, &Count);
i++)
+    {
+        NumberOfRuns++;
+    }
+
     DPRINT("FsRtlNumberOfRunsInBaseMcb(%p) = %d\n", OpaqueMcb, NumberOfRuns);
     return NumberOfRuns;
 }