/*
* PROJECT: ReactOS Kernel
- * LICENSE: GPL - See COPYING in the top level directory
+ * LICENSE: GPL v2 - See COPYING in the top level directory
* FILE: ntoskrnl/fsrtl/largemcb.c
* PURPOSE: Large Mapped Control Block (MCB) support for File System Drivers
- * PROGRAMMERS: Alex Ionescu (alex.ionescu@reactos.org)
- * Pierre Schweitzer (heis_spiter@hotmail.com)
- * Art Yerkes (art.yerkes@gmail.com)
+ * PROGRAMMERS: Aleksey Bragin <aleksey@reactos.org>
+ * Jan Kratochvil <project-captive@jankratochvil.net>
+ * Trevor Thompson
*/
/* INCLUDES ******************************************************************/
#include <ntoskrnl.h>
-//#define NDEBUG
+#define NDEBUG
#include <debug.h>
-/* GLOBALS *******************************************************************/
+#define MIN(x,y) (((x)<(y))?(x):(y))
+#define MAX(x,y) (((x)>(y))?(x):(y))
-#define GET_LIST_HEAD(x) ((PLIST_ENTRY)(&((PRTL_GENERIC_TABLE)x)[1]))
+/* GLOBALS *******************************************************************/
PAGED_LOOKASIDE_LIST FsRtlFirstMappingLookasideList;
NPAGED_LOOKASIDE_LIST FsRtlFastMutexLookasideList;
-typedef struct _LARGE_MCB_MAPPING_ENTRY
+/* We use only real 'mapping' runs; we do not store 'holes' to our GTree. */
+typedef struct _LARGE_MCB_MAPPING_ENTRY // run
{
- LARGE_INTEGER RunStartVbn;
- LARGE_INTEGER SectorCount;
- LARGE_INTEGER StartingLbn;
- LIST_ENTRY Sequence;
+ LARGE_INTEGER RunStartVbn;
+ LARGE_INTEGER RunEndVbn; /* RunStartVbn+SectorCount; that means +1 after the last sector */
+ LARGE_INTEGER StartingLbn; /* Lbn of 'RunStartVbn' */
} LARGE_MCB_MAPPING_ENTRY, *PLARGE_MCB_MAPPING_ENTRY;
+typedef struct _LARGE_MCB_MAPPING // mcb_priv
+{
+ RTL_GENERIC_TABLE Table;
+} LARGE_MCB_MAPPING, *PLARGE_MCB_MAPPING;
+
+typedef struct _BASE_MCB_INTERNAL {
+ ULONG MaximumPairCount;
+ ULONG PairCount;
+ USHORT PoolType;
+ USHORT Flags;
+ PLARGE_MCB_MAPPING Mapping;
+} BASE_MCB_INTERNAL, *PBASE_MCB_INTERNAL;
+
+/*
+static LARGE_MCB_MAPPING_ENTRY StaticRunBelow0 = {
+ {{-1}}, // ignored
+ {{0}},
+ {{-1}}, // ignored
+};
+*/
+
static PVOID NTAPI McbMappingAllocate(PRTL_GENERIC_TABLE Table, CLONG Bytes)
{
- PVOID Result;
- PBASE_MCB Mcb = (PBASE_MCB)Table->TableContext;
- Result = ExAllocatePoolWithTag(Mcb->PoolType, Bytes, 'LMCB');
- DPRINT("McbMappingAllocate(%d) => %p\n", Bytes, Result);
- return Result;
+ PVOID Result;
+ PBASE_MCB Mcb = (PBASE_MCB)Table->TableContext;
+ Result = ExAllocatePoolWithTag(Mcb->PoolType, Bytes, 'LMCB');
+ DPRINT("McbMappingAllocate(%lu) => %p\n", Bytes, Result);
+ return Result;
}
static VOID NTAPI McbMappingFree(PRTL_GENERIC_TABLE Table, PVOID Buffer)
{
- DPRINT("McbMappingFree(%p)\n", Buffer);
- ExFreePoolWithTag(Buffer, 'LMCB');
+ DPRINT("McbMappingFree(%p)\n", Buffer);
+ ExFreePoolWithTag(Buffer, 'LMCB');
}
-static RTL_GENERIC_COMPARE_RESULTS NTAPI McbMappingCompare
-(RTL_GENERIC_TABLE Table, PVOID PtrA, PVOID PtrB)
+static
+RTL_GENERIC_COMPARE_RESULTS
+NTAPI
+McbMappingCompare(PRTL_GENERIC_TABLE Table,
+ PVOID PtrA,
+ PVOID PtrB)
{
- PLARGE_MCB_MAPPING_ENTRY A = PtrA, B = PtrB;
- return
- (A->RunStartVbn.QuadPart + A->SectorCount.QuadPart <
- B->RunStartVbn.QuadPart) ? GenericLessThan :
- (A->RunStartVbn.QuadPart >
- B->RunStartVbn.QuadPart + B->SectorCount.QuadPart) ?
- GenericGreaterThan : GenericEqual;
+ PLARGE_MCB_MAPPING_ENTRY A = PtrA, B = PtrB;
+ RTL_GENERIC_COMPARE_RESULTS Res;
+
+ 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 (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;
+
+ return Res;
}
+
/* PUBLIC FUNCTIONS **********************************************************/
/*
* @implemented
+ * @Mcb: #PLARGE_MCB initialized by FsRtlInitializeLargeMcb().
+ * %NULL value is forbidden.
+ * @Vbn: Starting virtual block number of the wished range.
+ * @Lbn: Starting logical block number of the wished range.
+ * @SectorCount: Length of the wished range.
+ * Value less or equal to %0 is forbidden; FIXME: Is the reject of %0 W32 compliant?
+ *
+ * Adds the specified range @Vbn ... @Vbn+@SectorCount-1 to @Mcb.
+ * Any mappings previously in this range are deleted first.
+ *
+ * Returns: %TRUE if successful.
*/
BOOLEAN
NTAPI
-FsRtlAddBaseMcbEntry(IN PBASE_MCB Mcb,
+FsRtlAddBaseMcbEntry(IN PBASE_MCB OpaqueMcb,
IN LONGLONG Vbn,
IN LONGLONG Lbn,
IN LONGLONG SectorCount)
{
- LARGE_MCB_MAPPING_ENTRY Node;
- PLARGE_MCB_MAPPING_ENTRY Existing = NULL;
- BOOLEAN NewElement = FALSE;
-
- Node.RunStartVbn.QuadPart = Vbn;
- Node.StartingLbn.QuadPart = Lbn;
- Node.SectorCount.QuadPart = SectorCount;
-
- while (!NewElement)
- {
- DPRINT("Inserting %x:%x\n", Node.RunStartVbn.LowPart, Node.SectorCount.LowPart);
- Existing = RtlInsertElementGenericTable
- (Mcb->Mapping, &Node, sizeof(Node), &NewElement);
- DPRINT("Existing %x\n", Existing);
- if (!Existing) break;
-
- DPRINT("NewElement %d\n", NewElement);
- if (!NewElement)
- {
- // We merge the existing runs
- LARGE_INTEGER StartVbn, FinalVbn;
- DPRINT("Existing: %x:%x\n",
- Existing->RunStartVbn.LowPart, Node.SectorCount.LowPart);
- if (Existing->RunStartVbn.QuadPart < Node.RunStartVbn.QuadPart)
- {
- StartVbn = Existing->RunStartVbn;
- Node.StartingLbn = Existing->StartingLbn;
- }
- else
- {
- StartVbn = Node.RunStartVbn;
- }
- DPRINT("StartVbn %x\n", StartVbn.LowPart);
- if (Existing->RunStartVbn.QuadPart + Existing->SectorCount.QuadPart >
- Node.RunStartVbn.QuadPart + Node.SectorCount.QuadPart)
- {
- FinalVbn.QuadPart =
- Existing->RunStartVbn.QuadPart + Existing->SectorCount.QuadPart;
- }
- else
- {
- FinalVbn.QuadPart =
- Node.RunStartVbn.QuadPart + Node.SectorCount.QuadPart;
- }
- DPRINT("FinalVbn %x\n", FinalVbn.LowPart);
- Node.RunStartVbn.QuadPart = StartVbn.QuadPart;
- Node.SectorCount.QuadPart = FinalVbn.QuadPart - StartVbn.QuadPart;
- RemoveHeadList(&Existing->Sequence);
- RtlDeleteElementGenericTable(Mcb->Mapping, Existing);
- Mcb->PairCount--;
- }
- else
- {
- DPRINT("Mapping added %x\n", Existing);
- Mcb->MaximumPairCount++;
- Mcb->PairCount++;
- InsertHeadList(GET_LIST_HEAD(Mcb->Mapping), &Existing->Sequence);
- }
- }
-
- DPRINT("!!Existing %d\n", !!Existing);
- return !!Existing;
+ BOOLEAN Result = TRUE;
+ BOOLEAN IntResult;
+ PBASE_MCB_INTERNAL Mcb = (PBASE_MCB_INTERNAL)OpaqueMcb;
+ LARGE_MCB_MAPPING_ENTRY Node, NeedleRun;
+ PLARGE_MCB_MAPPING_ENTRY LowerRun, HigherRun;
+ BOOLEAN NewElement;
+ LONGLONG IntLbn;
+
+ DPRINT("FsRtlAddBaseMcbEntry(%p, %I64d, %I64d, %I64d)\n", OpaqueMcb, Vbn, Lbn, SectorCount);
+
+ if (Vbn < 0)
+ {
+ Result = FALSE;
+ goto quit;
+ }
+
+ if (SectorCount <= 0)
+ {
+ Result = FALSE;
+ goto quit;
+ }
+
+ IntResult = FsRtlLookupBaseMcbEntry(OpaqueMcb, Vbn, &IntLbn, NULL, NULL, NULL, NULL);
+ if (IntResult)
+ {
+ if (IntLbn != -1 && IntLbn != Lbn)
+ {
+ Result = FALSE;
+ goto quit;
+ }
+ }
+
+ /* clean any possible previous entries in our range */
+ FsRtlRemoveBaseMcbEntry(OpaqueMcb, Vbn, SectorCount);
+
+ // We need to map [Vbn, Vbn+SectorCount) to [Lbn, Lbn+SectorCount),
+ // taking in account the fact that we need to merge these runs if
+ // they are adjacent or overlap, but fail if new run fully fits into another run
+
+ /* initially we think we will be inserted as a separate run */
+ Node.RunStartVbn.QuadPart = Vbn;
+ Node.RunEndVbn.QuadPart = Vbn + SectorCount;
+ Node.StartingLbn.QuadPart = Lbn;
+
+ /* optionally merge with lower run */
+ NeedleRun.RunStartVbn.QuadPart = Node.RunStartVbn.QuadPart - 1;
+ NeedleRun.RunEndVbn.QuadPart = NeedleRun.RunStartVbn.QuadPart + 1;
+ NeedleRun.StartingLbn.QuadPart = ~0ULL;
+ Mcb->Mapping->Table.CompareRoutine = McbMappingIntersectCompare;
+ if ((LowerRun = RtlLookupElementGenericTable(&Mcb->Mapping->Table, &NeedleRun)) &&
+ (LowerRun->StartingLbn.QuadPart + (LowerRun->RunEndVbn.QuadPart - LowerRun->RunStartVbn.QuadPart) == Node.StartingLbn.QuadPart))
+ {
+ 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);
+ --Mcb->PairCount;
+ DPRINT("Intersecting lower run found (%I64d,%I64d) Lbn: %I64d\n", LowerRun->RunStartVbn.QuadPart, LowerRun->RunEndVbn.QuadPart, LowerRun->StartingLbn.QuadPart);
+ }
+
+ /* optionally merge with higher run */
+ NeedleRun.RunStartVbn.QuadPart = Node.RunEndVbn.QuadPart;
+ NeedleRun.RunEndVbn.QuadPart = NeedleRun.RunStartVbn.QuadPart + 1;
+ Mcb->Mapping->Table.CompareRoutine = McbMappingIntersectCompare;
+ if ((HigherRun = RtlLookupElementGenericTable(&Mcb->Mapping->Table, &NeedleRun)) &&
+ (Node.StartingLbn.QuadPart <= HigherRun->StartingLbn.QuadPart))
+ {
+ ASSERT(HigherRun->RunStartVbn.QuadPart == Node.RunEndVbn.QuadPart);
+ Node.RunEndVbn.QuadPart = HigherRun->RunEndVbn.QuadPart;
+ Mcb->Mapping->Table.CompareRoutine = McbMappingCompare;
+ RtlDeleteElementGenericTable(&Mcb->Mapping->Table, HigherRun);
+ --Mcb->PairCount;
+ DPRINT("Intersecting higher run found (%I64d,%I64d) Lbn: %I64d\n", HigherRun->RunStartVbn.QuadPart, HigherRun->RunEndVbn.QuadPart, HigherRun->StartingLbn.QuadPart);
+ }
+ Mcb->Mapping->Table.CompareRoutine = McbMappingCompare;
+
+ /* finally insert the resulting run */
+ RtlInsertElementGenericTable(&Mcb->Mapping->Table, &Node, sizeof(Node), &NewElement);
+ ++Mcb->PairCount;
+ ASSERT(NewElement);
+
+ // NB: Two consecutive runs can only be merged, if actual LBNs also match!
+
+ /* 1.
+ Existing->RunStartVbn
+ |
+ |///////|
+ |/////////////|
+ |
+ Node->RunStartVbn
+
+ 2.
+ Existing->RunStartVbn
+ |
+ |///////|
+ |//////|
+ |
+ Node->RunStartVbn
+
+ 3.
+ Existing->RunStartVbn
+ |
+ |///////|
+ |///|
+ |
+ Node->RunStartVbn
+
+ 4.
+ Existing->RunStartVbn
+ |
+ |///////|
+ |///////////////|
+ |
+ Node->RunStartVbn
+
+
+ Situation with holes:
+ 1. Holes at both ends
+ 2. Hole at the right, new run merged with the previous run
+ 3. Hole at the right, new run is not merged with the previous run
+ 4. Hole at the left, new run merged with the next run
+ 5. Hole at the left, new run is not merged with the next run
+ 6. No holes, exact fit to merge with both previous and next runs
+ 7. No holes, merges only with the next run
+ 8. No holes, merges only with the previous run
+ 9. No holes, does not merge with next or prev runs
+
+
+ Overwriting existing mapping is not possible and results in FALSE being returned
+ */
+
+quit:
+ DPRINT("FsRtlAddBaseMcbEntry(%p, %I64d, %I64d, %I64d) = %d\n", Mcb, Vbn, Lbn, SectorCount, Result);
+ return Result;
}
/*
{
BOOLEAN Result;
- DPRINT("Mcb %x Vbn %x Lbn %x SectorCount %x\n", Mcb, Vbn, Lbn, SectorCount);
+ DPRINT("FsRtlAddLargeMcbEntry(%p, %I64d, %I64d, %I64d)\n", Mcb, Vbn, Lbn, SectorCount);
KeAcquireGuardedMutex(Mcb->GuardedMutex);
Result = FsRtlAddBaseMcbEntry(&(Mcb->BaseMcb),
SectorCount);
KeReleaseGuardedMutex(Mcb->GuardedMutex);
- DPRINT("Done %d\n", Result);
+ DPRINT("FsRtlAddLargeMcbEntry(%p, %I64d, %I64d, %I64d) = %d\n", Mcb, Vbn, Lbn, SectorCount, Result);
return Result;
}
/*
- * @unimplemented
+ * @implemented
+ * @Mcb: #PLARGE_MCB initialized by FsRtlInitializeLargeMcb().
+ * %NULL value is forbidden.
+ * @RunIndex: Requested range index to retrieve.
+ * @Vbn: Returns the starting virtual block number of the wished range.
+ * %NULL pointer is forbidden.
+ * @Lbn: Returns the starting logical block number of the wished range (or -1 if it is a hole).
+ * %NULL pointer is forbidden.
+ * @SectorCount: Returns the length of the wished range.
+ * %NULL pointer is forbidden.
+ * Value less or equal to %0 is forbidden; FIXME: Is the reject of %0 W32 compliant?
+ *
+ * Retrieves the parameters of the specified run with index @RunIndex.
+ *
+ * Mapping %0 always starts at virtual block %0, either as 'hole' or as 'real' mapping.
+ * libcaptive does not store 'hole' information to its #GTree.
+ * Last run is always a 'real' run. 'hole' runs appear as mapping to constant @Lbn value %-1.
+ *
+ * Returns: %TRUE if successful.
*/
BOOLEAN
NTAPI
-FsRtlGetNextBaseMcbEntry(IN PBASE_MCB Mcb,
- IN ULONG RunIndex,
- OUT PLONGLONG Vbn,
- OUT PLONGLONG Lbn,
- OUT PLONGLONG SectorCount)
-{
- ULONG i = 0;
- BOOLEAN Result = FALSE;
- PLARGE_MCB_MAPPING_ENTRY Entry;
- for (Entry = (PLARGE_MCB_MAPPING_ENTRY)
- RtlEnumerateGenericTable(Mcb->Mapping, TRUE);
- Entry && i < RunIndex;
- Entry = (PLARGE_MCB_MAPPING_ENTRY)
- RtlEnumerateGenericTable(Mcb->Mapping, FALSE), i++);
- if (Entry)
- {
- Result = TRUE;
- if (Vbn)
- *Vbn = Entry->RunStartVbn.QuadPart;
- if (Lbn)
- *Lbn = Entry->StartingLbn.QuadPart;
- if (SectorCount)
- *SectorCount = Entry->SectorCount.QuadPart;
- }
-
- return Result;
+FsRtlGetNextBaseMcbEntry(IN PBASE_MCB OpaqueMcb,
+ IN ULONG RunIndex,
+ OUT PLONGLONG Vbn,
+ OUT PLONGLONG Lbn,
+ OUT PLONGLONG SectorCount)
+{
+ BOOLEAN Result = FALSE;
+ PBASE_MCB_INTERNAL Mcb = (PBASE_MCB_INTERNAL)OpaqueMcb;
+ PLARGE_MCB_MAPPING_ENTRY Run = NULL;
+ ULONG CurrentIndex = 0;
+ ULONGLONG LastVbn = 0;
+ ULONGLONG LastSectorCount = 0;
+
+ // 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))
+ {
+ // is the current index a hole?
+ if (Run->RunStartVbn.QuadPart > (LastVbn + LastSectorCount))
+ {
+ // Is this the index we're looking for?
+ if (RunIndex == CurrentIndex)
+ {
+ *Vbn = LastVbn + LastSectorCount;
+ *Lbn = -1;
+ *SectorCount = Run->RunStartVbn.QuadPart - *Vbn;
+
+ Result = TRUE;
+ goto quit;
+ }
+
+ CurrentIndex++;
+ }
+
+ if (RunIndex == CurrentIndex)
+ {
+ *Vbn = Run->RunStartVbn.QuadPart;
+ *Lbn = Run->StartingLbn.QuadPart;
+ *SectorCount = Run->RunEndVbn.QuadPart - Run->RunStartVbn.QuadPart;
+
+ Result = TRUE;
+ goto quit;
+ }
+
+ 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 = 0xdeadbeef;
+ *Lbn = 0xdeadbeef;
+ *SectorCount = 0xdeadbeef;
+
+quit:
+ DPRINT("FsRtlGetNextBaseMcbEntry(%p, %d, %p, %p, %p) = %d (%I64d, %I64d, %I64d)\n", Mcb, RunIndex, Vbn, Lbn, SectorCount, Result, *Vbn, *Lbn, *SectorCount);
+ return Result;
}
/*
{
BOOLEAN Result;
- DPRINT("FsRtlGetNextLargeMcbEntry Mcb %x RunIndex %x\n", Mcb, RunIndex);
+ DPRINT("FsRtlGetNextLargeMcbEntry(%p, %d, %p, %p, %p)\n", Mcb, RunIndex, Vbn, Lbn, SectorCount);
KeAcquireGuardedMutex(Mcb->GuardedMutex);
Result = FsRtlGetNextBaseMcbEntry(&(Mcb->BaseMcb),
SectorCount);
KeReleaseGuardedMutex(Mcb->GuardedMutex);
- DPRINT("Done %d\n", Result);
+ DPRINT("FsRtlGetNextLargeMcbEntry(%p, %d, %p, %p, %p) = %d (%I64d, %I64d, %I64d)\n", Mcb, RunIndex, Vbn, Lbn, SectorCount, Result, *Vbn, *Lbn, *SectorCount);
return Result;
}
*/
VOID
NTAPI
-FsRtlInitializeBaseMcb(IN PBASE_MCB Mcb,
+FsRtlInitializeBaseMcb(IN PBASE_MCB OpaqueMcb,
IN POOL_TYPE PoolType)
{
- Mcb->PairCount = 0;
+ PBASE_MCB_INTERNAL Mcb = (PBASE_MCB_INTERNAL)OpaqueMcb;
if (PoolType == PagedPool)
{
else
{
Mcb->Mapping = ExAllocatePoolWithTag(PoolType | POOL_RAISE_IF_ALLOCATION_FAILURE,
- sizeof(RTL_GENERIC_TABLE) + sizeof(LIST_ENTRY),
+ sizeof(LARGE_MCB_MAPPING),
'FSBC');
}
Mcb->PoolType = PoolType;
+ Mcb->PairCount = 0;
Mcb->MaximumPairCount = MAXIMUM_PAIR_COUNT;
- RtlInitializeGenericTable
- (Mcb->Mapping,
- (PRTL_GENERIC_COMPARE_ROUTINE)McbMappingCompare,
- McbMappingAllocate,
- McbMappingFree,
- Mcb);
- InitializeListHead(GET_LIST_HEAD(Mcb->Mapping));
+ RtlInitializeGenericTable(&Mcb->Mapping->Table,
+ McbMappingCompare,
+ McbMappingAllocate,
+ McbMappingFree,
+ Mcb);
}
/*
FsRtlInitializeLargeMcb(IN PLARGE_MCB Mcb,
IN POOL_TYPE PoolType)
{
+ DPRINT("FsRtlInitializeLargeMcb(%p, %d)\n", Mcb, PoolType);
+
Mcb->GuardedMutex = ExAllocateFromNPagedLookasideList(&FsRtlFastMutexLookasideList);
KeInitializeGuardedMutex(Mcb->GuardedMutex);
/*
* @implemented
*/
+INIT_FUNCTION
VOID
NTAPI
FsRtlInitializeLargeMcbs(VOID)
NULL,
NULL,
POOL_RAISE_IF_ALLOCATION_FAILURE,
- sizeof(RTL_GENERIC_TABLE) + sizeof(LIST_ENTRY),
+ sizeof(LARGE_MCB_MAPPING),
IFS_POOL_TAG,
0); /* FIXME: Should be 4 */
}
/*
- * @unimplemented
+ * @implemented
*/
BOOLEAN
NTAPI
-FsRtlLookupBaseMcbEntry(IN PBASE_MCB Mcb,
- 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;
- LARGE_MCB_MAPPING_ENTRY ToLookup;
- PLARGE_MCB_MAPPING_ENTRY Entry;
-
- ToLookup.RunStartVbn.QuadPart = Vbn;
- ToLookup.SectorCount.QuadPart = 1;
-
- Entry = RtlLookupElementGenericTable(Mcb->Mapping, &ToLookup);
- if (!Entry)
- {
- // Find out if we have a following entry. The spec says we should return
- // found with Lbn == -1 when we're beneath the largest map.
- ToLookup.SectorCount.QuadPart = (1ull<<62) - ToLookup.RunStartVbn.QuadPart;
- Entry = RtlLookupElementGenericTable(Mcb->Mapping, &ToLookup);
- if (Entry)
- {
- Result = TRUE;
- if (Lbn) *Lbn = ~0ull;
- }
- else
- {
- Result = FALSE;
- }
- }
- else
- {
- LARGE_INTEGER Offset;
- Offset.QuadPart = Vbn - Entry->RunStartVbn.QuadPart;
- Result = TRUE;
- if (Lbn) *Lbn = Entry->StartingLbn.QuadPart + Offset.QuadPart;
- if (SectorCountFromLbn) *SectorCountFromLbn = Entry->SectorCount.QuadPart - Offset.QuadPart;
- if (StartingLbn) *StartingLbn = Entry->StartingLbn.QuadPart;
- if (SectorCountFromStartingLbn) *SectorCountFromStartingLbn = Entry->SectorCount.QuadPart;
- }
-
+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;
+ ULONG i;
+ LONGLONG LastVbn = 0, LastLbn = 0, Count = 0; // the last values we've found during traversal
+
+ DPRINT("FsRtlLookupBaseMcbEntry(%p, %I64d, %p, %p, %p, %p, %p)\n", OpaqueMcb, Vbn, Lbn, SectorCountFromLbn, StartingLbn, SectorCountFromStartingLbn, Index);
+
+ for (i = 0; FsRtlGetNextBaseMcbEntry(OpaqueMcb, i, &LastVbn, &LastLbn, &Count); i++)
+ {
+ // have we reached the target mapping?
+ if (Vbn < LastVbn + Count)
+ {
+ if (Lbn)
+ {
+ if (LastLbn == -1)
+ *Lbn = -1;
+ else
+ *Lbn = LastLbn + (Vbn - LastVbn);
+ }
+
+ if (SectorCountFromLbn)
+ *SectorCountFromLbn = LastVbn + Count - Vbn;
+ if (StartingLbn)
+ *StartingLbn = LastLbn;
+ if (SectorCountFromStartingLbn)
+ *SectorCountFromStartingLbn = LastVbn + Count - LastVbn;
+ if (Index)
+ *Index = i;
+
+ Result = TRUE;
+ goto quit;
+ }
+ }
+
+ if (Lbn)
+ *Lbn = -1;
+ if (StartingLbn)
+ *StartingLbn = -1;
+
+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;
}
{
BOOLEAN Result;
- DPRINT("FsRtlLookupLargeMcbEntry Mcb %x Vbn %x\n", Mcb, (ULONG)Vbn);
+ DPRINT("FsRtlLookupLargeMcbEntry(%p, %I64d, %p, %p, %p, %p, %p)\n", Mcb, Vbn, Lbn, SectorCountFromLbn, StartingLbn, SectorCountFromStartingLbn, Index);
KeAcquireGuardedMutex(Mcb->GuardedMutex);
Result = FsRtlLookupBaseMcbEntry(&(Mcb->BaseMcb),
Index);
KeReleaseGuardedMutex(Mcb->GuardedMutex);
- DPRINT("Done %d\n", Result);
+ DPRINT("FsRtlLookupLargeMcbEntry(%p, %I64d, %p, %p, %p, %p, %p) = %d (%I64d, %I64d, %I64d, %I64d, %d)\n",
+ Mcb, 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;
}
+static BOOLEAN
+NTAPI
+FsRtlLookupLastLargeMcbEntryAndIndex_internal(IN PBASE_MCB_INTERNAL Mcb,
+ OUT PLONGLONG Vbn,
+ OUT PLONGLONG Lbn,
+ OUT PULONG Index OPTIONAL)
+{
+ 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;
+ }
+
+ 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)
+ {
+ *Index = RunIndex - 1;
+ }
+
+ return TRUE;
+}
+
+
/*
- * @unimplemented
+ * @implemented
*/
BOOLEAN
NTAPI
IN OUT PLONGLONG LargeLbn,
IN OUT PULONG Index)
{
- ULONG i = 0;
- BOOLEAN Result = FALSE;
- PLIST_ENTRY ListEntry;
- PLARGE_MCB_MAPPING_ENTRY Entry;
- PLARGE_MCB_MAPPING_ENTRY CountEntry;
+ BOOLEAN Result;
+ PBASE_MCB_INTERNAL Mcb = (PBASE_MCB_INTERNAL)OpaqueMcb;
- ListEntry = GET_LIST_HEAD(OpaqueMcb->Mapping);
- if (!IsListEmpty(ListEntry))
- {
- Entry = CONTAINING_RECORD(ListEntry->Flink, LARGE_MCB_MAPPING_ENTRY, Sequence);
- Result = TRUE;
- *LargeVbn = Entry->RunStartVbn.QuadPart;
- *LargeLbn = Entry->StartingLbn.QuadPart;
+ DPRINT("FsRtlLookupLastBaseMcbEntryAndIndex(%p, %p, %p, %p)\n", OpaqueMcb, LargeVbn, LargeLbn, Index);
- for (i = 0, CountEntry = RtlEnumerateGenericTable(OpaqueMcb->Mapping, TRUE);
- CountEntry != Entry;
- CountEntry = RtlEnumerateGenericTable(OpaqueMcb->Mapping, FALSE));
+ Result = FsRtlLookupLastLargeMcbEntryAndIndex_internal(Mcb, LargeVbn, LargeLbn, Index);
- *Index = i;
- }
+ DPRINT("FsRtlLookupLastBaseMcbEntryAndIndex(%p, %p, %p, %p) = %d (%I64d, %I64d, %d)\n", OpaqueMcb, LargeVbn, LargeLbn, Index, Result, *LargeVbn, *LargeLbn, *Index);
- return Result;
+ return Result;
}
/*
{
BOOLEAN Result;
- DPRINT("FsRtlLookupLastLargeMcbEntryAndIndex %x\n", OpaqueMcb);
+ DPRINT("FsRtlLookupLastLargeMcbEntryAndIndex(%p, %p, %p, %p)\n", OpaqueMcb, LargeVbn, LargeLbn, Index);
KeAcquireGuardedMutex(OpaqueMcb->GuardedMutex);
Result = FsRtlLookupLastBaseMcbEntryAndIndex(&(OpaqueMcb->BaseMcb),
Index);
KeReleaseGuardedMutex(OpaqueMcb->GuardedMutex);
- DPRINT("Done %d\n", Result);
+ DPRINT("FsRtlLookupLastLargeMcbEntryAndIndex(%p, %p, %p, %p) = %d (%I64d, %I64d, %d)\n", OpaqueMcb, LargeVbn, LargeLbn, Index, Result, *LargeVbn, *LargeLbn, *Index);
return Result;
}
*/
BOOLEAN
NTAPI
-FsRtlLookupLastBaseMcbEntry(IN PBASE_MCB Mcb,
+FsRtlLookupLastBaseMcbEntry(IN PBASE_MCB OpaqueMcb,
OUT PLONGLONG Vbn,
OUT PLONGLONG Lbn)
{
- BOOLEAN Result = FALSE;
- PLIST_ENTRY ListEntry;
- PLARGE_MCB_MAPPING_ENTRY Entry;
-
- ListEntry = GET_LIST_HEAD(Mcb->Mapping);
- if (!IsListEmpty(ListEntry))
- {
- Entry = CONTAINING_RECORD(ListEntry->Flink, LARGE_MCB_MAPPING_ENTRY, Sequence);
- Result = TRUE;
- *Vbn = Entry->RunStartVbn.QuadPart;
- *Lbn = Entry->StartingLbn.QuadPart;
- }
-
- return Result;
+ BOOLEAN Result;
+ PBASE_MCB_INTERNAL Mcb = (PBASE_MCB_INTERNAL)OpaqueMcb;
+
+ DPRINT("FsRtlLookupLastBaseMcbEntry(%p, %p, %p)\n", OpaqueMcb, Vbn, Lbn);
+
+ Result = FsRtlLookupLastLargeMcbEntryAndIndex_internal(Mcb, Vbn, Lbn, NULL); /* Index */
+
+ DPRINT("FsRtlLookupLastBaseMcbEntry(%p, %p, %p) = %d (%I64d, %I64d)\n", Mcb, Vbn, Lbn, Result, *Vbn, *Lbn);
+
+ return Result;
}
/*
{
BOOLEAN Result;
- DPRINT("FsRtlLookupLastLargeMcbEntry Mcb %x\n", Mcb);
+ DPRINT("FsRtlLookupLastLargeMcbEntry(%p, %p, %p)\n", Mcb, Vbn, Lbn);
KeAcquireGuardedMutex(Mcb->GuardedMutex);
Result = FsRtlLookupLastBaseMcbEntry(&(Mcb->BaseMcb),
Lbn);
KeReleaseGuardedMutex(Mcb->GuardedMutex);
- DPRINT("Done %d\n", Result);
+ DPRINT("FsRtlLookupLastLargeMcbEntry(%p, %p, %p) = %d (%I64d, %I64d)\n", Mcb, Vbn, Lbn, Result, *Vbn, *Lbn);
return Result;
}
*/
ULONG
NTAPI
-FsRtlNumberOfRunsInBaseMcb(IN PBASE_MCB Mcb)
+FsRtlNumberOfRunsInBaseMcb(IN PBASE_MCB OpaqueMcb)
{
- /* Return the count */
- return Mcb->PairCount;
+ ULONG NumberOfRuns = 0;
+ LONGLONG Vbn, Lbn, Count;
+ int i;
+
+ DPRINT("FsRtlNumberOfRunsInBaseMcb(%p)\n", OpaqueMcb);
+
+ // 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;
}
/*
{
ULONG NumberOfRuns;
- DPRINT("FsRtlNumberOfRunsInLargeMcb Mcb %x\n", Mcb);
+ DPRINT("FsRtlNumberOfRunsInLargeMcb(%p)\n", Mcb);
/* Read the number of runs while holding the MCB lock */
KeAcquireGuardedMutex(Mcb->GuardedMutex);
- NumberOfRuns = Mcb->BaseMcb.PairCount;
+ NumberOfRuns = FsRtlNumberOfRunsInBaseMcb(&(Mcb->BaseMcb));
KeReleaseGuardedMutex(Mcb->GuardedMutex);
- DPRINT("Done %d\n", NumberOfRuns);
+ DPRINT("FsRtlNumberOfRunsInLargeMcb(%p) = %d\n", Mcb, NumberOfRuns);
/* Return the count */
return NumberOfRuns;
}
/*
- * @unimplemented
+ * @implemented
+ * @Mcb: #PLARGE_MCB initialized by FsRtlInitializeLargeMcb().
+ * %NULL value is forbidden.
+ * @Vbn: Starting virtual block number to specify the range to delete.
+ * @SectorCount: Length of the range to delete.
+ * Value less or equal to %0 is forbidden; FIXME: Is the reject of %0 W32 compliant?
+ *
+ * Deletes any possible @Mcb mappings in the given range @Vbn ... @Vbn+@SectorCount-1.
+ * This call has no problems if no mappings exist there yet.
*/
BOOLEAN
NTAPI
-FsRtlRemoveBaseMcbEntry(IN PBASE_MCB Mcb,
+FsRtlRemoveBaseMcbEntry(IN PBASE_MCB OpaqueMcb,
IN LONGLONG Vbn,
IN LONGLONG SectorCount)
{
- LARGE_MCB_MAPPING_ENTRY Node;
- PLARGE_MCB_MAPPING_ENTRY Element;
-
- Node.RunStartVbn.QuadPart = Vbn;
- Node.SectorCount.QuadPart = SectorCount;
-
- while ((Element = RtlLookupElementGenericTable(Mcb->Mapping, &Node)))
- {
- // Must split
- if (Element->RunStartVbn.QuadPart < Node.RunStartVbn.QuadPart &&
- Element->SectorCount.QuadPart > Node.SectorCount.QuadPart)
- {
- LARGE_MCB_MAPPING_ENTRY Upper, Reinsert;
- PLARGE_MCB_MAPPING_ENTRY Reinserted, Inserted;
- LARGE_INTEGER StartHole = Node.RunStartVbn;
- LARGE_INTEGER EndHole;
- EndHole.QuadPart = Node.RunStartVbn.QuadPart + Node.SectorCount.QuadPart;
- Upper.RunStartVbn.QuadPart = EndHole.QuadPart;
- Upper.StartingLbn.QuadPart =
- Element->StartingLbn.QuadPart +
- EndHole.QuadPart -
- Element->RunStartVbn.QuadPart;
- Upper.SectorCount.QuadPart =
- Element->SectorCount.QuadPart -
- (EndHole.QuadPart - Element->RunStartVbn.QuadPart);
- Reinsert = *Element;
- Reinsert.SectorCount.QuadPart =
- Element->RunStartVbn.QuadPart - StartHole.QuadPart;
- RemoveEntryList(&Element->Sequence);
- RtlDeleteElementGenericTable(Mcb->Mapping, Element);
- Mcb->PairCount--;
-
- Reinserted = RtlInsertElementGenericTable
- (Mcb->Mapping, &Reinsert, sizeof(Reinsert), NULL);
- InsertHeadList(GET_LIST_HEAD(Mcb->Mapping), &Reinserted->Sequence);
- Mcb->PairCount++;
-
- Inserted = RtlInsertElementGenericTable
- (Mcb->Mapping, &Upper, sizeof(Upper), NULL);
- InsertHeadList(GET_LIST_HEAD(Mcb->Mapping), &Inserted->Sequence);
- Mcb->PairCount++;
- }
- else if (Element->RunStartVbn.QuadPart < Node.RunStartVbn.QuadPart)
- {
- LARGE_MCB_MAPPING_ENTRY NewElement;
- PLARGE_MCB_MAPPING_ENTRY Reinserted;
- LARGE_INTEGER StartHole = Node.RunStartVbn;
- NewElement.RunStartVbn = Element->RunStartVbn;
- NewElement.StartingLbn = Element->StartingLbn;
- NewElement.SectorCount.QuadPart = StartHole.QuadPart - Element->StartingLbn.QuadPart;
-
- RemoveEntryList(&Element->Sequence);
- RtlDeleteElementGenericTable(Mcb->Mapping, Element);
- Mcb->PairCount--;
-
- Reinserted = RtlInsertElementGenericTable
- (Mcb->Mapping, &NewElement, sizeof(NewElement), NULL);
- InsertHeadList(GET_LIST_HEAD(Mcb->Mapping), &Reinserted->Sequence);
- Mcb->PairCount++;
- }
- else
- {
- LARGE_MCB_MAPPING_ENTRY NewElement;
- PLARGE_MCB_MAPPING_ENTRY Reinserted;
- LARGE_INTEGER EndHole = Element->RunStartVbn;
- LARGE_INTEGER EndRun;
- EndRun.QuadPart = Element->RunStartVbn.QuadPart + Element->SectorCount.QuadPart;
- NewElement.RunStartVbn = EndHole;
- NewElement.StartingLbn.QuadPart = Element->StartingLbn.QuadPart +
- (EndHole.QuadPart - Element->RunStartVbn.QuadPart);
- NewElement.SectorCount.QuadPart = EndRun.QuadPart - EndHole.QuadPart;
-
- RemoveEntryList(&Element->Sequence);
- RtlDeleteElementGenericTable(Mcb->Mapping, Element);
- Mcb->PairCount--;
-
- Reinserted = RtlInsertElementGenericTable
- (Mcb->Mapping, &NewElement, sizeof(NewElement), NULL);
- InsertHeadList(GET_LIST_HEAD(Mcb->Mapping), &Reinserted->Sequence);
- Mcb->PairCount++;
- }
- }
-
- return TRUE;
+ PBASE_MCB_INTERNAL Mcb = (PBASE_MCB_INTERNAL)OpaqueMcb;
+ LARGE_MCB_MAPPING_ENTRY NeedleRun;
+ PLARGE_MCB_MAPPING_ENTRY HaystackRun;
+ BOOLEAN Result = TRUE;
+
+ DPRINT("FsRtlRemoveBaseMcbEntry(%p, %I64d, %I64d)\n", OpaqueMcb, Vbn, SectorCount);
+
+ if (Vbn < 0 || SectorCount <= 0)
+ {
+ Result = FALSE;
+ goto quit;
+ }
+
+ if (Vbn + SectorCount <= Vbn)
+ {
+ Result = FALSE;
+ goto quit;
+ }
+
+ 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 = RtlLookupElementGenericTable(&Mcb->Mapping->Table, &NeedleRun)))
+ {
+ if (HaystackRun->RunStartVbn.QuadPart < NeedleRun.RunStartVbn.QuadPart)
+ {
+ ASSERT(HaystackRun->RunEndVbn.QuadPart > NeedleRun.RunStartVbn.QuadPart);
+ HaystackRun->RunEndVbn.QuadPart = NeedleRun.RunStartVbn.QuadPart;
+ }
+ else if (HaystackRun->RunEndVbn.QuadPart > NeedleRun.RunEndVbn.QuadPart)
+ {
+ ASSERT(HaystackRun->RunStartVbn.QuadPart < NeedleRun.RunEndVbn.QuadPart);
+ HaystackRun->RunStartVbn.QuadPart = NeedleRun.RunEndVbn.QuadPart;
+ }
+ else
+ {
+ //ASSERT(NeedleRun.RunStartVbn.QuadPart >= HaystackRun->RunStartVbn.QuadPart);
+ //ASSERT(NeedleRun.RunEndVbn.QuadPart <= HaystackRun->RunEndVbn.QuadPart);
+ Mcb->Mapping->Table.CompareRoutine = McbMappingCompare;
+ RtlDeleteElementGenericTable(&Mcb->Mapping->Table, HaystackRun);
+ --Mcb->PairCount;
+ Mcb->Mapping->Table.CompareRoutine = McbMappingIntersectCompare;
+ }
+ }
+ Mcb->Mapping->Table.CompareRoutine = McbMappingCompare;
+
+quit:
+ DPRINT("FsRtlRemoveBaseMcbEntry(%p, %I64d, %I64d) = %d\n", OpaqueMcb, Vbn, SectorCount, Result);
+ return Result;
}
/*
IN LONGLONG Vbn,
IN LONGLONG SectorCount)
{
- DPRINT("FsRtlRemoveLargeMcbEntry Mcb %x, Vbn %x, SectorCount %x\n", Mcb, (ULONG)Vbn, (ULONG)SectorCount);
+ DPRINT("FsRtlRemoveLargeMcbEntry(%p, %I64d, %I64d)\n", Mcb, Vbn, SectorCount);
KeAcquireGuardedMutex(Mcb->GuardedMutex);
- FsRtlRemoveBaseMcbEntry(&(Mcb->BaseMcb),
- Vbn,
- SectorCount);
+ FsRtlRemoveBaseMcbEntry(&(Mcb->BaseMcb), Vbn, SectorCount);
KeReleaseGuardedMutex(Mcb->GuardedMutex);
-
- DPRINT("Done\n");
}
/*
*/
VOID
NTAPI
-FsRtlResetBaseMcb(IN PBASE_MCB Mcb)
+FsRtlResetBaseMcb(IN PBASE_MCB OpaqueMcb)
{
- PLARGE_MCB_MAPPING_ENTRY Element;
+ PBASE_MCB_INTERNAL Mcb = (PBASE_MCB_INTERNAL)OpaqueMcb;
+ PLARGE_MCB_MAPPING_ENTRY Element;
- while (RtlNumberGenericTableElements(Mcb->Mapping) &&
- (Element = (PLARGE_MCB_MAPPING_ENTRY)RtlGetElementGenericTable(Mcb->Mapping, 0)))
- {
- RtlDeleteElementGenericTable(Mcb->Mapping, Element);
- }
+ DPRINT("FsRtlResetBaseMcb(%p)\n", OpaqueMcb);
- Mcb->PairCount = 0;
- Mcb->MaximumPairCount = 0;
+ while (RtlNumberGenericTableElements(&Mcb->Mapping->Table) &&
+ (Element = (PLARGE_MCB_MAPPING_ENTRY)RtlGetElementGenericTable(&Mcb->Mapping->Table, 0)))
+ {
+ RtlDeleteElementGenericTable(&Mcb->Mapping->Table, Element);
+ }
+
+ Mcb->PairCount = 0;
+ Mcb->MaximumPairCount = 0;
}
/*
FsRtlResetLargeMcb(IN PLARGE_MCB Mcb,
IN BOOLEAN SelfSynchronized)
{
+ DPRINT("FsRtlResetLargeMcb(%p, %d)\n", Mcb, SelfSynchronized);
+
if (!SelfSynchronized)
- {
KeAcquireGuardedMutex(Mcb->GuardedMutex);
- }
-
- FsRtlResetBaseMcb(&Mcb->BaseMcb);
+ FsRtlResetBaseMcb(&Mcb->BaseMcb);
if (!SelfSynchronized)
- {
- KeReleaseGuardedMutex(Mcb->GuardedMutex);
- }
-}
-
-#define MCB_BUMP_NO_MORE 0
-#define MCB_BUMP_AGAIN 1
-
-static ULONG NTAPI McbBump(PBASE_MCB Mcb, PLARGE_MCB_MAPPING_ENTRY FixedPart)
-{
- LARGE_MCB_MAPPING_ENTRY Reimagined;
- PLARGE_MCB_MAPPING_ENTRY Found = NULL;
-
- DPRINT("McbBump %x (%x:%x)\n", Mcb, FixedPart->RunStartVbn.LowPart, FixedPart->SectorCount.LowPart);
-
- Reimagined = *FixedPart;
- while ((Found = RtlLookupElementGenericTable(Mcb->Mapping, &Reimagined)))
- {
- Reimagined = *Found;
- Reimagined.RunStartVbn.QuadPart =
- FixedPart->RunStartVbn.QuadPart + FixedPart->SectorCount.QuadPart;
- DPRINT("Reimagined %x\n", Reimagined.RunStartVbn.LowPart);
- }
-
- DPRINT("Found %x\n", Found);
- if (!Found) return MCB_BUMP_NO_MORE;
- DPRINT1
- ("Moving %x-%x to %x because %x-%x overlaps\n",
- Found->RunStartVbn.LowPart,
- Found->RunStartVbn.LowPart + Found->SectorCount.QuadPart,
- Reimagined.RunStartVbn.LowPart + Reimagined.SectorCount.LowPart,
- Reimagined.RunStartVbn.LowPart,
- Reimagined.RunStartVbn.LowPart + Reimagined.SectorCount.LowPart);
- Found->RunStartVbn.QuadPart = Reimagined.RunStartVbn.QuadPart + Reimagined.SectorCount.QuadPart;
- Found->StartingLbn.QuadPart = Reimagined.StartingLbn.QuadPart + Reimagined.SectorCount.QuadPart;
-
- DPRINT("Again\n");
- return MCB_BUMP_AGAIN;
+ KeReleaseGuardedMutex(Mcb->GuardedMutex);
}
/*
*/
BOOLEAN
NTAPI
-FsRtlSplitBaseMcb(IN PBASE_MCB Mcb,
+FsRtlSplitBaseMcb(IN PBASE_MCB OpaqueMcb,
IN LONGLONG Vbn,
IN LONGLONG Amount)
{
- ULONG Result;
- LARGE_MCB_MAPPING_ENTRY Node;
- PLARGE_MCB_MAPPING_ENTRY Existing = NULL;
-
- Node.RunStartVbn.QuadPart = Vbn;
- Node.SectorCount.QuadPart = 0;
-
- Existing = RtlLookupElementGenericTable(Mcb->Mapping, &Node);
-
- if (Existing)
- {
- // We're in the middle of a run
- LARGE_MCB_MAPPING_ENTRY UpperPart;
- LARGE_MCB_MAPPING_ENTRY LowerPart;
- PLARGE_MCB_MAPPING_ENTRY InsertedUpper;
-
- UpperPart.RunStartVbn.QuadPart = Node.RunStartVbn.QuadPart + Amount;
- UpperPart.SectorCount.QuadPart = Existing->RunStartVbn.QuadPart +
- (Existing->SectorCount.QuadPart - Node.RunStartVbn.QuadPart);
- UpperPart.StartingLbn.QuadPart = Existing->StartingLbn.QuadPart +
- (Node.RunStartVbn.QuadPart - Existing->RunStartVbn.QuadPart);
- LowerPart.RunStartVbn.QuadPart = Existing->RunStartVbn.QuadPart;
- LowerPart.SectorCount.QuadPart = Node.RunStartVbn.QuadPart - Existing->RunStartVbn.QuadPart;
- LowerPart.StartingLbn.QuadPart = Existing->StartingLbn.QuadPart;
-
- Node = UpperPart;
-
- DPRINT("Loop: %x\n", Node.RunStartVbn.LowPart);
- while ((Result = McbBump(Mcb, &Node)) == MCB_BUMP_AGAIN)
- {
- DPRINT("Node: %x\n", Node.RunStartVbn.LowPart);
- }
- DPRINT("Done\n");
-
- if (Result == MCB_BUMP_NO_MORE)
- {
- Node = *Existing;
- RemoveHeadList(&Existing->Sequence);
- RtlDeleteElementGenericTable(Mcb->Mapping, Existing);
- Mcb->PairCount--;
-
- // Adjust the element we found.
- Existing->SectorCount = LowerPart.SectorCount;
-
- InsertedUpper = RtlInsertElementGenericTable
- (Mcb->Mapping, &UpperPart, sizeof(UpperPart), NULL);
- if (!InsertedUpper)
- {
- // Just make it like it was
- Existing->SectorCount = Node.SectorCount;
- return FALSE;
- }
- InsertHeadList(GET_LIST_HEAD(Mcb->Mapping), &InsertedUpper->Sequence);
- Mcb->PairCount++;
- }
- else
- {
- Node.RunStartVbn.QuadPart = Vbn;
- Node.SectorCount.QuadPart = Amount;
- while ((Result = McbBump(Mcb, &Node)) == MCB_BUMP_AGAIN);
- return Result == MCB_BUMP_NO_MORE;
- }
- }
-
- DPRINT("Done\n");
-
- return TRUE;
+ PBASE_MCB_INTERNAL Mcb = (PBASE_MCB_INTERNAL)OpaqueMcb;
+ PLARGE_MCB_MAPPING_ENTRY Run, InsertLowerRun = NULL, ExistingRun = NULL;
+ BOOLEAN NewElement;
+
+ DPRINT("FsRtlSplitBaseMcb(%p, %I64d, %I64d)\n", OpaqueMcb, Vbn, Amount);
+
+ /* 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))
+ {
+ /* unaffected run? */
+ /* FIXME: performance: effective skip of all 'lower' runs without traversing them */
+ 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.
+ * current 'run' is shifted up later
+ */
+ if (Vbn < Run->RunEndVbn.QuadPart)
+ {
+ /* FIXME: shift 'run->Lbn_start' ? */
+ Run->RunStartVbn.QuadPart = Vbn;
+
+ InsertLowerRun = NULL;
+ }
+
+ /* Shift the current 'run'.
+ * Ordering is not changed in Generic Tree so I hope I do not need to reinsert it.
+ */
+ Run->RunStartVbn.QuadPart += Amount;
+ ASSERT(Run->RunEndVbn.QuadPart + Amount > Run->RunEndVbn.QuadPart); /* overflow? */
+ Run->RunEndVbn.QuadPart += Amount;
+ /* FIXME: shift 'run->Lbn_start' ? */
+
+ /* continue the traversal */
+ }
+
+ if (InsertLowerRun)
+ {
+ ExistingRun = RtlInsertElementGenericTable(&Mcb->Mapping->Table, InsertLowerRun, sizeof(*InsertLowerRun), &NewElement);
+ ++Mcb->PairCount;
+ }
+
+ ASSERT(ExistingRun == NULL);
+
+ DPRINT("FsRtlSplitBaseMcb(%p, %I64d, %I64d) = %d\n", OpaqueMcb, Vbn, Amount, TRUE);
+
+ return TRUE;
}
/*
{
BOOLEAN Result;
- DPRINT("FsRtlSplitLargeMcb %x, Vbn %x, Amount %x\n", Mcb, (ULONG)Vbn, (ULONG)Amount);
+ DPRINT("FsRtlSplitLargeMcb(%p, %I64d, %I64d)\n", Mcb, Vbn, Amount);
KeAcquireGuardedMutex(Mcb->GuardedMutex);
Result = FsRtlSplitBaseMcb(&(Mcb->BaseMcb),
Amount);
KeReleaseGuardedMutex(Mcb->GuardedMutex);
- DPRINT("Done %d\n", Result);
+ DPRINT("FsRtlSplitLargeMcb(%p, %I64d, %I64d) = %d\n", Mcb, Vbn, Amount, Result);
return Result;
}
*/
VOID
NTAPI
-FsRtlTruncateBaseMcb(IN PBASE_MCB Mcb,
+FsRtlTruncateBaseMcb(IN PBASE_MCB OpaqueMcb,
IN LONGLONG Vbn)
{
- if (!Vbn)
- {
- FsRtlResetBaseMcb(Mcb);
- }
- else
- {
- LARGE_MCB_MAPPING_ENTRY Truncate;
- PLARGE_MCB_MAPPING_ENTRY Found;
- Truncate.RunStartVbn.QuadPart = Vbn;
- Truncate.SectorCount.QuadPart = (1ull<<62) - Truncate.RunStartVbn.QuadPart;
- while ((Found = RtlLookupElementGenericTable(Mcb->Mapping, &Truncate)))
- {
- RemoveEntryList(&Found->Sequence);
- RtlDeleteElementGenericTable(Mcb->Mapping, Found);
- Mcb->PairCount--;
- }
- }
+ DPRINT("FsRtlTruncateBaseMcb(%p, %I64d)\n", OpaqueMcb, Vbn);
+
+ FsRtlRemoveBaseMcbEntry(OpaqueMcb, Vbn, MAXLONG - Vbn + 1);
}
/*
FsRtlTruncateLargeMcb(IN PLARGE_MCB Mcb,
IN LONGLONG Vbn)
{
- DPRINT("FsRtlTruncateLargeMcb %x Vbn %x\n", Mcb, (ULONG)Vbn);
+ DPRINT("FsRtlTruncateLargeMcb(%p, %I64d)\n", Mcb, Vbn);
+
KeAcquireGuardedMutex(Mcb->GuardedMutex);
- FsRtlTruncateBaseMcb(&(Mcb->BaseMcb),
- Vbn);
+ FsRtlTruncateBaseMcb(&(Mcb->BaseMcb), Vbn);
KeReleaseGuardedMutex(Mcb->GuardedMutex);
- DPRINT("Done\n");
}
/*
NTAPI
FsRtlUninitializeBaseMcb(IN PBASE_MCB Mcb)
{
- FsRtlResetBaseMcb(Mcb);
+ DPRINT("FsRtlUninitializeBaseMcb(%p)\n", Mcb);
+
+ FsRtlResetBaseMcb(Mcb);
- if ((Mcb->PoolType == PagedPool) && (Mcb->MaximumPairCount == MAXIMUM_PAIR_COUNT))
+ if ((Mcb->PoolType == PagedPool)/* && (Mcb->MaximumPairCount == MAXIMUM_PAIR_COUNT)*/)
{
ExFreeToPagedLookasideList(&FsRtlFirstMappingLookasideList,
Mcb->Mapping);
NTAPI
FsRtlUninitializeLargeMcb(IN PLARGE_MCB Mcb)
{
+ DPRINT("FsRtlUninitializeLargeMcb(%p)\n", Mcb);
+
if (Mcb->GuardedMutex)
{
ExFreeToNPagedLookasideList(&FsRtlFastMutexLookasideList,
FsRtlUninitializeBaseMcb(&(Mcb->BaseMcb));
}
}
-