Author: fireball
Date: Mon Sep 8 07:56:08 2008
New Revision: 36053
URL: http://svn.reactos.org/svn/reactos?rev=36053&view=rev
Log:
- Implement a linear search in CmpFindSubKeyInRoot (until cells are stored in a lexically sorted way).
- Implement Leaf->Root index conversion (leaf selecting algorithm, splitting the leaf if necessary).
See issue #3418 for more details.
Modified:
trunk/reactos/ntoskrnl/config/cmindex.c
Modified: trunk/reactos/ntoskrnl/config/cmindex.c
URL: http://svn.reactos.org/svn/reactos/trunk/reactos/ntoskrnl/config/cmindex.c?…
==============================================================================
--- trunk/reactos/ntoskrnl/config/cmindex.c [iso-8859-1] (original)
+++ trunk/reactos/ntoskrnl/config/cmindex.c [iso-8859-1] Mon Sep 8 07:56:08 2008
@@ -145,13 +145,12 @@
IN PCUNICODE_STRING SearchName,
IN PHCELL_INDEX SubKey)
{
- ULONG High, Low = 0, i, ReturnIndex;
+ ULONG High, Low = 0, i = 0, ReturnIndex;
HCELL_INDEX LeafCell;
PCM_KEY_INDEX Leaf;
LONG Result;
/* Verify Index for validity */
- ASSERTMSG("We don't do a linear search yet!\n", FALSE);
ASSERT(Index->Count != 0);
ASSERT(Index->Signature == CM_KEY_INDEX_ROOT);
@@ -160,7 +159,9 @@
while (TRUE)
{
/* Choose next entry */
+#ifdef SOMEONE_WAS_NICE_ENOUGH_TO_MAKE_OUR_CELLS_LEXICALLY_SORTED
i = ((High - Low) / 2) + Low;
+#endif
/* Get the leaf cell and then the leaf itself */
LeafCell = Index->List[i];
@@ -190,6 +191,7 @@
goto Return;
}
+#ifdef SOMEONE_WAS_NICE_ENOUGH_TO_MAKE_OUR_CELLS_LEXICALLY_SORTED
/* Check for negative result */
if (Result < 0)
{
@@ -228,6 +230,7 @@
/* Update the base to this index, since we know it's not lower. */
Low = i;
}
+#endif
}
else
{
@@ -242,6 +245,16 @@
/* Release the leaf cell */
HvReleaseCell(Hive, LeafCell);
+
+#ifndef SOMEONE_WAS_NICE_ENOUGH_TO_MAKE_OUR_CELLS_LEXICALLY_SORTED
+ /* Go to the next index, and return failure if we reach the end */
+ if (++i > High)
+ {
+ /* Return failure */
+ *SubKey = HCELL_NIL;
+ return 0;
+ }
+#endif
}
/* Make sure we got here for the right reasons */
@@ -1114,6 +1127,366 @@
/* Update the leaf count and return the new cell */
Leaf->Count += 1;
return NewCell;
+}
+
+HCELL_INDEX
+NTAPI
+CmpSplitLeaf(IN PHHIVE Hive,
+ IN HCELL_INDEX RootCell,
+ IN ULONG RootSelect,
+ IN HSTORAGE_TYPE Type)
+{
+ PCM_KEY_INDEX IndexKey, LeafKey, NewKey;
+ PCM_KEY_FAST_INDEX FastLeaf;
+ HCELL_INDEX LeafCell, NewCell;
+ ULONG FirstHalf, LastHalf;
+ ULONG EntrySize, TotalSize;
+
+ /* Get the cell */
+ IndexKey = (PCM_KEY_INDEX)HvGetCell(Hive, RootCell);
+
+ /* Check if we've got valid IndexKey */
+ if (!IndexKey) return HCELL_NIL;
+
+ /* Get the leaf cell and key */
+ LeafCell = IndexKey->List[RootSelect];
+ LeafKey = (PCM_KEY_INDEX)HvGetCell(Hive, LeafCell);
+
+ /* Check if we've got valid LeafKey */
+ if (!LeafKey) return HCELL_NIL;
+
+ /* We are going to divide this leaf into two halves */
+ FirstHalf = (LeafKey->Count / 2);
+ LastHalf = LeafKey->Count - FirstHalf;
+
+ /* Now check what kind of hive we're dealing with,
+ * and compute entry size
+ */
+ if (Hive->Version >= 5)
+ {
+ /* XP Hive: Use hash leaf */
+ ASSERT(LeafKey->Signature == CM_KEY_HASH_LEAF);
+ EntrySize = sizeof(CM_INDEX);
+ }
+ else
+ {
+ /* Use index leaf */
+ ASSERT(LeafKey->Signature == CM_KEY_INDEX_LEAF);
+ EntrySize = sizeof(HCELL_INDEX);
+ }
+
+ /* Compute the total size */
+ TotalSize = (EntrySize * LastHalf) + FIELD_OFFSET(CM_KEY_INDEX, List) + 1;
+
+ /* Mark the leaf cell dirty */
+ HvMarkCellDirty(Hive, LeafCell, FALSE);
+
+ /* Make sure its type is the same */
+ ASSERT(HvGetCellType(LeafCell) == Type);
+
+ /* Allocate the cell, fail in case of error */
+ NewCell = HvAllocateCell(Hive, TotalSize, Type, LeafCell);
+ if (NewCell == HCELL_NIL) return NewCell;
+
+ /* Get the key */
+ NewKey = (PCM_KEY_INDEX)HvGetCell(Hive, NewCell);
+ if (!NewKey)
+ {
+ /* Free the cell and exit - should not happen! */
+ ASSERT(FALSE);
+ HvFreeCell(Hive, NewCell);
+ return HCELL_NIL;
+ }
+
+ /* Release the newly created cell */
+ HvReleaseCell(Hive, NewCell);
+
+ /* Set its signature according to the version of the hive */
+ if (Hive->Version >= 5)
+ {
+ /* XP Hive: Use hash leaf signature */
+ NewKey->Signature = CM_KEY_HASH_LEAF;
+ }
+ else
+ {
+ /* Use index leaf signature */
+ NewKey->Signature = CM_KEY_INDEX_LEAF;
+ }
+
+ /* Calculate the size of the free entries in the root key */
+ TotalSize = HvGetCellSize(Hive, IndexKey) -
+ (IndexKey->Count * sizeof(HCELL_INDEX)) -
+ FIELD_OFFSET(CM_KEY_INDEX, List);
+
+ /* Check if we're out of space */
+ if (TotalSize / sizeof(HCELL_INDEX) < 1)
+ {
+ /* Grow the leaf by one more entry */
+ TotalSize = HvGetCellSize(Hive, IndexKey) + sizeof(HCELL_INDEX);
+
+ /* Re-allocate the root */
+ RootCell = HvReallocateCell(Hive, RootCell, TotalSize);
+ if (RootCell == HCELL_NIL)
+ {
+ /* Free the cell and exit */
+ HvFreeCell(Hive, NewCell);
+ return HCELL_NIL;
+ }
+
+ /* Get the leaf cell */
+ IndexKey = (PCM_KEY_INDEX)HvGetCell(Hive, RootCell);
+ if (!IndexKey)
+ {
+ /* This shouldn't happen */
+ ASSERT(FALSE);
+ return HCELL_NIL;
+ }
+ }
+
+ /* Splitting is done, now we need to copy the contents,
+ * according to the hive version
+ */
+ if (Hive->Version >= 5)
+ {
+ /* Copy the fast indexes */
+ FastLeaf = (PCM_KEY_FAST_INDEX)LeafKey;
+ RtlMoveMemory(&NewKey->List[0],
+ &FastLeaf->List[FirstHalf],
+ LastHalf * EntrySize);
+ }
+ else
+ {
+ /* Copy the indexes themselves */
+ RtlMoveMemory(&NewKey->List[0],
+ &LeafKey->List[FirstHalf],
+ LastHalf * EntrySize);
+ }
+
+ /* Shift the data inside the root key */
+ if (RootSelect < (IndexKey->Count - 1))
+ {
+ RtlMoveMemory(&IndexKey->List[RootSelect + 2],
+ &IndexKey->List[RootSelect + 1],
+ IndexKey->Count -
+ (RootSelect + 1) * sizeof(HCELL_INDEX));
+ }
+
+ /* Make sure both old and new computed counts are valid */
+ ASSERT(FirstHalf != 0);
+ ASSERT(LastHalf != 0);
+
+ /* Update the count value of old and new keys */
+ LeafKey->Count = FirstHalf;
+ NewKey->Count = LastHalf;
+
+ /* Increase the count value of the root key */
+ IndexKey->Count++;
+
+ /* Set the new cell in root's list */
+ IndexKey->List[RootSelect + 1] = NewCell;
+
+ /* Return the root cell */
+ return RootCell;
+}
+
+HCELL_INDEX
+NTAPI
+CmpSelectLeaf(IN PHHIVE Hive,
+ IN PCM_KEY_NODE KeyNode,
+ IN PUNICODE_STRING Name,
+ IN HSTORAGE_TYPE Type,
+ IN PHCELL_INDEX *RootCell)
+{
+ PCM_KEY_INDEX IndexKey, LeafKey;
+ PCM_KEY_FAST_INDEX FastLeaf;
+ HCELL_INDEX LeafCell, CurrentCell;
+ ULONG SubKeyIndex;
+ LONG Result;
+
+ /* Mark it as dirty */
+ HvMarkCellDirty(Hive, KeyNode->SubKeyLists[Type], FALSE);
+
+ /* Get the cell */
+ IndexKey = (PCM_KEY_INDEX)HvGetCell(Hive, KeyNode->SubKeyLists[Type]);
+
+ /* Check if we've got a valid key */
+ if (!IndexKey)
+ {
+ /* Should not happen! */
+ ASSERTMSG("IndexKey = NULL!, it should not happen!\n", FALSE);
+ return HCELL_NIL;
+ }
+
+ /* Sanity check */
+ ASSERT(IndexKey->Signature == CM_KEY_INDEX_ROOT);
+
+ while (TRUE)
+ {
+ /* Find subkey */
+ SubKeyIndex = CmpFindSubKeyInRoot(Hive, IndexKey, Name, &LeafCell);
+
+ /* Make sure we found something valid */
+ if (SubKeyIndex & 0x80000000) return HCELL_NIL;
+
+ /* Try to fit it into the LeafCell, if it was found */
+ if (LeafCell != HCELL_NIL)
+ {
+ /* Get the leaf key */
+ LeafKey = (PCM_KEY_INDEX)HvGetCell(Hive, LeafCell);
+
+ /* Check for failure */
+ if (!LeafKey) return HCELL_NIL;
+
+ /* Check if it fits into this leaf and break */
+ if (LeafKey->Count < CmpMaxIndexPerHblock)
+ {
+ /* Fill in the result and return it */
+ *RootCell = &IndexKey->List[SubKeyIndex];
+ return LeafCell;
+ }
+ }
+ else
+ {
+ /* Get the leaf cell at the very end */
+ LeafCell = IndexKey->List[SubKeyIndex];
+ LeafKey = (PCM_KEY_INDEX)HvGetCell(Hive, LeafCell);
+
+ /* Return an error in case of problems */
+ if (!LeafKey) return HCELL_NIL;
+
+ /* Choose the cell to search from depending on the key type */
+ if ((LeafKey->Signature == CM_KEY_FAST_LEAF) ||
+ (LeafKey->Signature == CM_KEY_HASH_LEAF))
+ {
+ FastLeaf = (PCM_KEY_FAST_INDEX)LeafKey;
+ CurrentCell = FastLeaf->List[0].Cell;
+ }
+ else
+ {
+ /* Make sure it's an index leaf */
+ ASSERT(LeafKey->Signature == CM_KEY_INDEX_LEAF);
+ CurrentCell = LeafKey->List[0];
+ }
+
+ /* Do a name compare */
+ Result = CmpDoCompareKeyName(Hive, Name, CurrentCell);
+
+ /* Check for failure */
+ if (Result == 2) return HCELL_NIL;
+
+ /* Names can't be equal, ensure that */
+ ASSERT(Result != 0);
+
+ /* Check if it's above */
+ if (Result >= 0)
+ {
+ /* Get the first cell in the index */
+ LeafCell = IndexKey->List[0];
+ LeafKey = (PCM_KEY_INDEX)HvGetCell(Hive, LeafCell);
+
+ /* Return an error in case of problems */
+ if (!LeafKey) return HCELL_NIL;
+
+ /* Check if it fits into this leaf and break */
+ if (LeafKey->Count < CmpMaxIndexPerHblock)
+ {
+ /* Fill in the result and return the cell */
+ *RootCell = &IndexKey->List[SubKeyIndex + 1];
+ return LeafCell;
+ }
+
+ /* No, it doesn't fit, check the other leaf */
+ if (SubKeyIndex < (IndexKey->Count - 1))
+ {
+ /* Yes, there is space */
+ LeafCell = IndexKey->List[SubKeyIndex + 1];
+ LeafKey = (PCM_KEY_INDEX)HvGetCell(Hive, LeafCell);
+
+ /* Return an error in case of problems */
+ if (!LeafKey) return HCELL_NIL;
+
+ /* Check if it fits and break */
+ if (LeafKey->Count < CmpMaxIndexPerHblock)
+ {
+ /* Fill in the result and return the cell */
+ *RootCell = &IndexKey->List[SubKeyIndex + 1];
+ return LeafCell;
+ }
+ }
+ }
+ else
+ {
+ /* No, it's below, check the subkey index */
+ if (SubKeyIndex > 0)
+ {
+ /* There should be space at the leaf one before that */
+ LeafCell = IndexKey->List[SubKeyIndex - 1];
+ LeafKey = (PCM_KEY_INDEX)HvGetCell(Hive, LeafCell);
+
+ /* Return an error in case of problems */
+ if (!LeafKey) return HCELL_NIL;
+
+ /* Check if it fits and break */
+ if (LeafKey->Count < CmpMaxIndexPerHblock)
+ {
+ /* Decrement the subkey index */
+ SubKeyIndex--;
+
+ /* Fill in the result and return the cell */
+ *RootCell = &IndexKey->List[SubKeyIndex];
+ return LeafCell;
+ }
+ }
+ else
+ {
+ /* Use the first leaf, if possible */
+ LeafCell = IndexKey->List[0];
+ LeafKey = (PCM_KEY_INDEX)HvGetCell(Hive, LeafCell);
+
+ /* Return an error in case of problems */
+ if (!LeafKey) return HCELL_NIL;
+
+ /* Check if it fits and break */
+ if (LeafKey->Count < CmpMaxIndexPerHblock)
+ {
+ /* Fill in the result and return the cell */
+ *RootCell = &IndexKey->List[0];
+ return LeafCell;
+ }
+ }
+
+ /* It didn't fit into either, so proceed to splitting */
+ }
+ }
+
+ /* We need to split */
+ CurrentCell = CmpSplitLeaf(Hive,
+ KeyNode->SubKeyLists[Type],
+ SubKeyIndex,
+ Type);
+
+ /* Return failure in case splitting failed */
+ if (CurrentCell == HCELL_NIL) return CurrentCell;
+
+ /* Set the SubKeyLists value with the new key */
+ KeyNode->SubKeyLists[Type] = CurrentCell;
+
+ /* Get the new cell */
+ IndexKey = (PCM_KEY_INDEX)HvGetCell(Hive, KeyNode->SubKeyLists[Type]);
+
+ /* Return in case of failure */
+ if (!IndexKey) return HCELL_NIL;
+
+ /* Make sure the new key became index root */
+ ASSERT(IndexKey->Signature == CM_KEY_INDEX_ROOT);
+
+ /* Now loop over with the new IndexKey value, which definately
+ * has the space now
+ */
+ }
+
+ /* Shouldn't come here */
+ return HCELL_NIL;
}
BOOLEAN
@@ -1253,7 +1626,7 @@
/* Convert */
OldIndex = (PCM_KEY_FAST_INDEX)Index;
- for (i=0; i < OldIndex->Count; i++)
+ for (i = 0; i < OldIndex->Count; i++)
{
Index->List[i] = OldIndex->List[i].Cell;
}
@@ -1299,9 +1672,17 @@
/* Check if we turned the index into a root */
if (Index->Signature == CM_KEY_INDEX_ROOT)
{
- /* Not handled yet */
- DPRINT1("Leaf->Root Index Conversion not yet implemented!\n");
- ASSERT(FALSE);
+ DPRINT("Leaf->Root Index Conversion\n");
+
+ /* Get the leaf where to add the new entry (the routine will do
+ * the splitting if necessary)
+ */
+ LeafCell = CmpSelectLeaf(Hive, KeyNode, &Name, Type, &RootPointer);
+ if (LeafCell == HCELL_NIL)
+ {
+ /* Not handled */
+ ASSERT(FALSE);
+ }
}
/* Add our leaf cell */
Author: fireball
Date: Mon Sep 8 07:34:01 2008
New Revision: 36050
URL: http://svn.reactos.org/svn/reactos?rev=36050&view=rev
Log:
- Comment out the assert which is hit in some cases ("advapi32_winetest.exe registry" being one of them), because there is no locking operation performed in CmpBuildHashStackAndLookupCache yet.
- Use a CmpIsKcbLockedExclusive macro in that assert.
Modified:
trunk/reactos/ntoskrnl/config/cmalloc.c
Modified: trunk/reactos/ntoskrnl/config/cmalloc.c
URL: http://svn.reactos.org/svn/reactos/trunk/reactos/ntoskrnl/config/cmalloc.c?…
==============================================================================
--- trunk/reactos/ntoskrnl/config/cmalloc.c [iso-8859-1] (original)
+++ trunk/reactos/ntoskrnl/config/cmalloc.c [iso-8859-1] Mon Sep 8 07:34:01 2008
@@ -70,9 +70,8 @@
KeAcquireGuardedMutex(&CmpAllocBucketLock);
/* Sanity check on lock ownership */
- ASSERT((GET_HASH_ENTRY(CmpCacheTable, Kcb->ConvKey).Owner ==
- KeGetCurrentThread()) ||
- (CmpTestRegistryLockExclusive() == TRUE));
+ //ASSERT((CmpIsKcbLockedExclusive(Kcb) == TRUE) ||
+ // (CmpTestRegistryLockExclusive() == TRUE));
/* Add us to the free list */
InsertTailList(&CmpFreeKCBListHead, &Kcb->FreeListEntry);
Author: sginsberg
Date: Mon Sep 8 06:52:33 2008
New Revision: 36047
URL: http://svn.reactos.org/svn/reactos?rev=36047&view=rev
Log:
- NtQueryInformationFile and NtSetInformationFile: Don't clear the IRP_SYNCHRONOUS_API flag if it has been set previously! This should obsolete the hack in irp.c!IopCompleteRequest.
- If you still see "Not an executive event -- should not be dereferenced" after this patch then please report to me.
Modified:
trunk/reactos/ntoskrnl/io/iomgr/iofunc.c
Modified: trunk/reactos/ntoskrnl/io/iomgr/iofunc.c
URL: http://svn.reactos.org/svn/reactos/trunk/reactos/ntoskrnl/io/iomgr/iofunc.c…
==============================================================================
--- trunk/reactos/ntoskrnl/io/iomgr/iofunc.c [iso-8859-1] (original)
+++ trunk/reactos/ntoskrnl/io/iomgr/iofunc.c [iso-8859-1] Mon Sep 8 06:52:33 2008
@@ -1809,10 +1809,10 @@
if (!NT_SUCCESS(Status)) return Status;
/* Set the flags */
- Irp->Flags = (IRP_BUFFERED_IO |
- IRP_DEALLOCATE_BUFFER |
- IRP_INPUT_OPERATION |
- IRP_DEFER_IO_COMPLETION);
+ Irp->Flags |= (IRP_BUFFERED_IO |
+ IRP_DEALLOCATE_BUFFER |
+ IRP_INPUT_OPERATION |
+ IRP_DEFER_IO_COMPLETION);
/* Set the Parameters */
StackPtr->Parameters.QueryFile.FileInformationClass = FileInformationClass;
@@ -2405,9 +2405,9 @@
if (!NT_SUCCESS(Status)) return Status;
/* Set the flags */
- Irp->Flags = (IRP_BUFFERED_IO |
- IRP_DEALLOCATE_BUFFER |
- IRP_DEFER_IO_COMPLETION);
+ Irp->Flags |= (IRP_BUFFERED_IO |
+ IRP_DEALLOCATE_BUFFER |
+ IRP_DEFER_IO_COMPLETION);
/* Set the Parameters */
StackPtr->Parameters.SetFile.FileInformationClass = FileInformationClass;