Author: tthompson
Date: Thu Jun 29 02:36:00 2017
New Revision: 75228
URL: http://svn.reactos.org/svn/reactos?rev=75228&view=rev
Log:
[NTFS] - Fix gcc build. Fix CompareTreeKeys(): Don't consider Key1 a possible dummy key. Don't assume filenames are the same length.
Modified:
branches/GSoC_2016/NTFS/drivers/filesystems/ntfs/btree.c
Modified: branches/GSoC_2016/NTFS/drivers/filesystems/ntfs/btree.c
URL: http://svn.reactos.org/svn/reactos/branches/GSoC_2016/NTFS/drivers/filesyst…
==============================================================================
--- branches/GSoC_2016/NTFS/drivers/filesystems/ntfs/btree.c [iso-8859-1] (original)
+++ branches/GSoC_2016/NTFS/drivers/filesystems/ntfs/btree.c [iso-8859-1] Thu Jun 29 02:36:00 2017
@@ -54,21 +54,18 @@
* > 0 if key1 is greater than key2
*
* @remarks
-* Any other key is always less than the final (dummy) key in a node.
+* Any other key is always less than the final (dummy) key in a node. Key1 must not be the dummy node.
*/
LONG
CompareTreeKeys(PB_TREE_KEY Key1, PB_TREE_KEY Key2, BOOLEAN CaseSensitive)
{
UNICODE_STRING Key1Name, Key2Name;
+ LONG Comparison;
// If Key2 is the "dummy key", key 1 will always come first
if (Key2->NextKey == NULL)
return -1;
- // If Key1 is the "dummy key", key 2 will always come first
- if (Key1->NextKey == NULL)
- return 1;
-
Key1Name.Buffer = Key1->IndexEntry->FileName.Name;
Key1Name.Length = Key1Name.MaximumLength
= Key1->IndexEntry->FileName.NameLength * sizeof(WCHAR);
@@ -77,7 +74,38 @@
Key2Name.Length = Key2Name.MaximumLength
= Key2->IndexEntry->FileName.NameLength * sizeof(WCHAR);
- return RtlCompareUnicodeString(&Key1Name, &Key2Name, !CaseSensitive);
+ // Are the two keys the same length?
+ if(Key1Name.Length == Key2Name.Length)
+ return RtlCompareUnicodeString(&Key1Name, &Key2Name, !CaseSensitive);
+
+ // Is Key1 shorter?
+ if (Key1Name.Length < Key2Name.Length)
+ {
+ // Truncate KeyName2 to be the same length as KeyName1
+ Key2Name.Length = Key1Name.Length;
+
+ // Compare the names of the same length
+ Comparison = RtlCompareUnicodeString(&Key1Name, &Key2Name, !CaseSensitive);
+
+ // If the truncated files are the same length, the shorter one comes first
+ if (Comparison == 0)
+ return -1;
+ }
+ else
+ {
+ // Key2 is shorter
+ // Truncate KeyName1 to be the same length as KeyName2
+ Key1Name.Length = Key2Name.Length;
+
+ // Compare the names of the same length
+ Comparison = RtlCompareUnicodeString(&Key1Name, &Key2Name, !CaseSensitive);
+
+ // If the truncated files are the same length, the shorter one comes first
+ if (Comparison == 0)
+ return 1;
+ }
+
+ return Comparison;
}
/**
@@ -241,6 +269,8 @@
PINDEX_ROOT_ATTRIBUTE *IndexRoot,
ULONG *Length)
{
+ int i;
+ PB_TREE_KEY CurrentKey;
PINDEX_ENTRY_ATTRIBUTE CurrentNodeEntry;
PINDEX_ROOT_ATTRIBUTE NewIndexRoot = ExAllocatePoolWithTag(NonPagedPool,
DeviceExt->NtfsInfo.BytesPerFileRecord,
@@ -274,11 +304,11 @@
NewIndexRoot->Header.TotalSizeOfEntries = NewIndexRoot->Header.FirstEntryOffset;
// Setup each Node Entry
- PB_TREE_KEY CurrentKey = Tree->RootNode->FirstKey;
+ CurrentKey = Tree->RootNode->FirstKey;
CurrentNodeEntry = (PINDEX_ENTRY_ATTRIBUTE)((ULONG_PTR)NewIndexRoot
+ FIELD_OFFSET(INDEX_ROOT_ATTRIBUTE, Header)
+ NewIndexRoot->Header.FirstEntryOffset);
- for (int i = 0; i < Tree->RootNode->KeyCount; i++)
+ for (i = 0; i < Tree->RootNode->KeyCount; i++)
{
// Would adding the current entry to the index increase the index size beyond the limit we've set?
ULONG IndexSize = FIELD_OFFSET(INDEX_ROOT_ATTRIBUTE, Header)
@@ -335,7 +365,8 @@
{
PB_TREE_KEY NextKey;
PB_TREE_KEY CurrentKey = Node->FirstKey;
- for (int i = 0; i < Node->KeyCount; i++)
+ int i;
+ for (i = 0; i < Node->KeyCount; i++)
{
NT_ASSERT(CurrentKey);
NextKey = CurrentKey->NextKey;
@@ -370,7 +401,8 @@
VOID
DumpBTreeKey(PB_TREE_KEY Key, int Number, int Depth)
{
- for (int i = 0; i < Depth; i++)
+ int i;
+ for (i = 0; i < Depth; i++)
DbgPrint(" ");
DbgPrint(" Key #%d", Number);
@@ -386,14 +418,17 @@
DbgPrint(" (Dummy Key)\n");
}
+VOID
DumpBTreeNode(PB_TREE_FILENAME_NODE Node, int Number, int Depth)
{
- for (int i = 0; i < Depth; i++)
+ PB_TREE_KEY CurrentKey;
+ int i;
+ for (i = 0; i < Depth; i++)
DbgPrint(" ");
DbgPrint("Node #%d, Depth %d\n", Number, Depth);
- PB_TREE_KEY CurrentKey = Node->FirstKey;
- for (int i = 0; i < Node->KeyCount; i++)
+ CurrentKey = Node->FirstKey;
+ for (i = 0; i < Node->KeyCount; i++)
{
DumpBTreeKey(CurrentKey, i, Depth);
CurrentKey = CurrentKey->NextKey;
@@ -451,6 +486,8 @@
ULONG AttributeSize = GetFileNameAttributeLength(FileNameAttribute);
ULONG EntrySize = ALIGN_UP_BY(AttributeSize + FIELD_OFFSET(INDEX_ENTRY_ATTRIBUTE, FileName), 8);
PINDEX_ENTRY_ATTRIBUTE NewEntry;
+ PB_TREE_KEY NewKey, CurrentKey, PreviousKey;
+ int i;
DPRINT1("NtfsInsertKey(0x%02I64, %p, %p, %s)\n",
FileReference,
@@ -476,14 +513,14 @@
RtlCopyMemory(&NewEntry->FileName, FileNameAttribute, AttributeSize);
// Setup the New Key
- PB_TREE_KEY NewKey = ExAllocatePoolWithTag(NonPagedPool, sizeof(B_TREE_KEY), TAG_NTFS);
+ NewKey = ExAllocatePoolWithTag(NonPagedPool, sizeof(B_TREE_KEY), TAG_NTFS);
NewKey->IndexEntry = NewEntry;
NewKey->NextKey = NULL;
// Find where to insert the key
- PB_TREE_KEY CurrentKey = Node->FirstKey;
- PB_TREE_KEY PreviousKey = NULL;
- for (int i = 0; i < Node->KeyCount; i++)
+ CurrentKey = Node->FirstKey;
+ PreviousKey = NULL;
+ for (i = 0; i < Node->KeyCount; i++)
{
// Should the New Key go before the current key?
LONG Comparison = CompareTreeKeys(NewKey, CurrentKey, CaseSensitive);
Author: tthompson
Date: Wed Jun 28 03:45:52 2017
New Revision: 75223
URL: http://svn.reactos.org/svn/reactos?rev=75223&view=rev
Log:
[NTFS] - Begin to implement B-Trees. Allow for creating several new files in a directory.
NtfsAddFilenameToDirectory() - Add CaseSensitive parameter. Update to use new B-Tree code: First, the index is read and converted to a B-Tree in memory. Next, a key for the new file is inserted into the tree. Finally, the tree is converted back to an index root attribute which is written to disk.
+btree.c - Includes functions related to B-Trees (AKA B*Trees).
ntfs.h - Added several structures for representing B-Trees in memory.
Known limitations: For simplicity, only trees with a depth of one are currently supported (i.e. an ordered list of filenames). Directories that have or will require an index allocation to store all their filenames are still TODO. As a consequence, the user will only be able to create about 6 files in a directory.
Added:
branches/GSoC_2016/NTFS/drivers/filesystems/ntfs/btree.c (with props)
Modified:
branches/GSoC_2016/NTFS/drivers/filesystems/ntfs/CMakeLists.txt
branches/GSoC_2016/NTFS/drivers/filesystems/ntfs/attrib.c
branches/GSoC_2016/NTFS/drivers/filesystems/ntfs/create.c
branches/GSoC_2016/NTFS/drivers/filesystems/ntfs/dirctl.c
branches/GSoC_2016/NTFS/drivers/filesystems/ntfs/ntfs.h
Modified: branches/GSoC_2016/NTFS/drivers/filesystems/ntfs/CMakeLists.txt
URL: http://svn.reactos.org/svn/reactos/branches/GSoC_2016/NTFS/drivers/filesyst…
==============================================================================
--- branches/GSoC_2016/NTFS/drivers/filesystems/ntfs/CMakeLists.txt [iso-8859-1] (original)
+++ branches/GSoC_2016/NTFS/drivers/filesystems/ntfs/CMakeLists.txt [iso-8859-1] Wed Jun 28 03:45:52 2017
@@ -1,6 +1,7 @@
list(APPEND SOURCE
attrib.c
+ btree.c
blockdev.c
cleanup.c
close.c
Modified: branches/GSoC_2016/NTFS/drivers/filesystems/ntfs/attrib.c
URL: http://svn.reactos.org/svn/reactos/branches/GSoC_2016/NTFS/drivers/filesyst…
==============================================================================
--- branches/GSoC_2016/NTFS/drivers/filesystems/ntfs/attrib.c [iso-8859-1] (original)
+++ branches/GSoC_2016/NTFS/drivers/filesystems/ntfs/attrib.c [iso-8859-1] Wed Jun 28 03:45:52 2017
@@ -1566,6 +1566,12 @@
return NULL;
}
+ULONG GetFileNameAttributeLength(PFILENAME_ATTRIBUTE FileNameAttribute)
+{
+ ULONG Length = FIELD_OFFSET(FILENAME_ATTRIBUTE, Name) + (FileNameAttribute->NameLength * sizeof(WCHAR));
+ return Length;
+}
+
PFILENAME_ATTRIBUTE
GetBestFileNameFromRecord(PDEVICE_EXTENSION Vcb,
PFILE_RECORD_HEADER FileRecord)
Added: branches/GSoC_2016/NTFS/drivers/filesystems/ntfs/btree.c
URL: http://svn.reactos.org/svn/reactos/branches/GSoC_2016/NTFS/drivers/filesyst…
==============================================================================
--- branches/GSoC_2016/NTFS/drivers/filesystems/ntfs/btree.c (added)
+++ branches/GSoC_2016/NTFS/drivers/filesystems/ntfs/btree.c [iso-8859-1] Wed Jun 28 03:45:52 2017
@@ -0,0 +1,520 @@
+/*
+* ReactOS kernel
+* Copyright (C) 2002, 2017 ReactOS Team
+*
+* This program is free software; you can redistribute it and/or modify
+* it under the terms of the GNU General Public License as published by
+* the Free Software Foundation; either version 2 of the License, or
+* (at your option) any later version.
+*
+* This program is distributed in the hope that it will be useful,
+* but WITHOUT ANY WARRANTY; without even the implied warranty of
+* MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
+* GNU General Public License for more details.
+*
+* You should have received a copy of the GNU General Public License
+* along with this program; if not, write to the Free Software
+* Foundation, Inc., 51 Franklin St, Fifth Floor, Boston, MA 02110-1301, USA.
+*
+* COPYRIGHT: See COPYING in the top level directory
+* PROJECT: ReactOS kernel
+* FILE: drivers/filesystem/ntfs/btree.c
+* PURPOSE: NTFS filesystem driver
+* PROGRAMMERS: Trevor Thompson
+*/
+
+/* INCLUDES *****************************************************************/
+
+#include "ntfs.h"
+
+#define NDEBUG
+#include <debug.h>
+
+/* FUNCTIONS ****************************************************************/
+
+/**
+* @name CompareTreeKeys
+* @implemented
+*
+* Compare two B_TREE_KEY's to determine their order in the tree.
+*
+* @param Key1
+* Pointer to a B_TREE_KEY that will be compared.
+*
+* @param Key2
+* Pointer to the other B_TREE_KEY that will be compared.
+*
+* @param CaseSensitive
+* Boolean indicating if the function should operate in case-sensitive mode. This will be TRUE
+* if an application created the file with the FILE_FLAG_POSIX_SEMANTICS flag.
+*
+* @returns
+* 0 if the two keys are equal.
+* < 0 if key1 is less thank key2
+* > 0 if key1 is greater than key2
+*
+* @remarks
+* Any other key is always less than the final (dummy) key in a node.
+*/
+LONG
+CompareTreeKeys(PB_TREE_KEY Key1, PB_TREE_KEY Key2, BOOLEAN CaseSensitive)
+{
+ UNICODE_STRING Key1Name, Key2Name;
+
+ // If Key2 is the "dummy key", key 1 will always come first
+ if (Key2->NextKey == NULL)
+ return -1;
+
+ // If Key1 is the "dummy key", key 2 will always come first
+ if (Key1->NextKey == NULL)
+ return 1;
+
+ Key1Name.Buffer = Key1->IndexEntry->FileName.Name;
+ Key1Name.Length = Key1Name.MaximumLength
+ = Key1->IndexEntry->FileName.NameLength * sizeof(WCHAR);
+
+ Key2Name.Buffer = Key2->IndexEntry->FileName.Name;
+ Key2Name.Length = Key2Name.MaximumLength
+ = Key2->IndexEntry->FileName.NameLength * sizeof(WCHAR);
+
+ return RtlCompareUnicodeString(&Key1Name, &Key2Name, !CaseSensitive);
+}
+
+/**
+* @name CreateBTreeFromIndex
+* @implemented
+*
+* Parse an index and create a B-Tree in memory from it.
+*
+* @param IndexRootContext
+* Pointer to an NTFS_ATTR_CONTEXT that describes the location of the index root attribute.
+*
+* @param NewTree
+* Pointer to a PB_TREE that will receive the pointer to a newly-created B-Tree.
+*
+* @returns
+* STATUS_SUCCESS on success.
+* STATUS_INSUFFICIENT_RESOURCES if an allocation fails.
+*
+* @remarks
+* Allocates memory for the entire tree. Caller is responsible for destroying the tree with DestroyBTree().
+*/
+NTSTATUS
+CreateBTreeFromIndex(PNTFS_ATTR_CONTEXT IndexRootContext,
+ PINDEX_ROOT_ATTRIBUTE IndexRoot,
+ PB_TREE *NewTree)
+{
+ PINDEX_ENTRY_ATTRIBUTE CurrentNodeEntry;
+ PB_TREE Tree = ExAllocatePoolWithTag(NonPagedPool, sizeof(B_TREE), TAG_NTFS);
+ PB_TREE_FILENAME_NODE RootNode = ExAllocatePoolWithTag(NonPagedPool, sizeof(B_TREE_FILENAME_NODE), TAG_NTFS);
+ PB_TREE_KEY CurrentKey = ExAllocatePoolWithTag(NonPagedPool, sizeof(B_TREE_KEY), TAG_NTFS);
+
+ DPRINT1("CreateBTreeFromIndex(%p, %p, %p)\n", IndexRootContext, IndexRoot, NewTree);
+
+ if (!Tree || !RootNode || !CurrentKey)
+ {
+ DPRINT1("Couldn't allocate enough memory for B-Tree!\n");
+ if (Tree)
+ ExFreePoolWithTag(Tree, TAG_NTFS);
+ if (CurrentKey)
+ ExFreePoolWithTag(CurrentKey, TAG_NTFS);
+ if (RootNode)
+ ExFreePoolWithTag(RootNode, TAG_NTFS);
+ return STATUS_INSUFFICIENT_RESOURCES;
+ }
+
+ RtlZeroMemory(Tree, sizeof(B_TREE));
+ RtlZeroMemory(RootNode, sizeof(B_TREE_FILENAME_NODE));
+ RtlZeroMemory(CurrentKey, sizeof(B_TREE_KEY));
+
+ // Setup the Tree
+ RootNode->FirstKey = CurrentKey;
+ Tree->RootNode = RootNode;
+
+ // Create a key for each entry in the node
+ CurrentNodeEntry = (PINDEX_ENTRY_ATTRIBUTE)((ULONG_PTR)IndexRoot
+ + FIELD_OFFSET(INDEX_ROOT_ATTRIBUTE, Header)
+ + IndexRoot->Header.FirstEntryOffset);
+ while (TRUE)
+ {
+ // Allocate memory for the current entry
+ CurrentKey->IndexEntry = ExAllocatePoolWithTag(NonPagedPool, CurrentNodeEntry->Length, TAG_NTFS);
+ if (!CurrentKey->IndexEntry)
+ {
+ DPRINT1("ERROR: Couldn't allocate memory for next key!\n");
+ DestroyBTree(Tree);
+ return STATUS_INSUFFICIENT_RESOURCES;
+ }
+
+ RootNode->KeyCount++;
+
+ // If this isn't the last entry
+ if (!(CurrentNodeEntry->Flags & NTFS_INDEX_ENTRY_END))
+ {
+ // Create the next key
+ PB_TREE_KEY NextKey = ExAllocatePoolWithTag(NonPagedPool, sizeof(PB_TREE_KEY), TAG_NTFS);
+ if (!NextKey)
+ {
+ DPRINT1("ERROR: Couldn't allocate memory for next key!\n");
+ DestroyBTree(Tree);
+ return STATUS_INSUFFICIENT_RESOURCES;
+ }
+
+ RtlZeroMemory(NextKey, sizeof(PB_TREE_KEY));
+
+ // Add NextKey to the end of the list
+ CurrentKey->NextKey = NextKey;
+
+ // Copy the current entry to its key
+ RtlCopyMemory(CurrentKey->IndexEntry, CurrentNodeEntry, CurrentNodeEntry->Length);
+
+ // Make sure this B-Tree is only one level deep (flat list)
+ if (CurrentKey->IndexEntry->Flags & NTFS_INDEX_ENTRY_NODE)
+ {
+ DPRINT1("TODO: Only directories with single-level B-Trees are supported right now!\n");
+ DestroyBTree(Tree);
+ return STATUS_NOT_IMPLEMENTED;
+ }
+
+ // Advance to the next entry
+ CurrentNodeEntry = (PINDEX_ENTRY_ATTRIBUTE)((ULONG_PTR)CurrentNodeEntry + CurrentNodeEntry->Length);
+ CurrentKey = NextKey;
+ }
+ else
+ {
+ // Copy the final entry to its key
+ RtlCopyMemory(CurrentKey->IndexEntry, CurrentNodeEntry, CurrentNodeEntry->Length);
+ CurrentKey->NextKey = NULL;
+
+ // Make sure this B-Tree is only one level deep (flat list)
+ if (CurrentKey->IndexEntry->Flags & NTFS_INDEX_ENTRY_NODE)
+ {
+ DPRINT1("TODO: Only directories with single-level B-Trees are supported right now!\n");
+ DestroyBTree(Tree);
+ return STATUS_NOT_IMPLEMENTED;
+ }
+
+ break;
+ }
+ }
+
+ *NewTree = Tree;
+
+ return STATUS_SUCCESS;
+}
+
+/**
+* @name CreateIndexRootFromBTree
+* @implemented
+*
+* Parse a B-Tree in memory and convert it into an index that can be written to disk.
+*
+* @param DeviceExt
+* Pointer to the DEVICE_EXTENSION of the target drive.
+*
+* @param Tree
+* Pointer to a B_TREE that describes the index to be written.
+*
+* @param MaxIndexSize
+* Describes how large the index can be before it will take too much space in the file record.
+* After reaching MaxIndexSize, an index can no longer be represented with just an index root
+* attribute, and will require an index allocation and $I30 bitmap (TODO).
+*
+* @param IndexRoot
+* Pointer to a PINDEX_ROOT_ATTRIBUTE that will receive a pointer to the newly-created index.
+*
+* @param Length
+* Pointer to a ULONG which will receive the length of the new index root.
+*
+* @returns
+* STATUS_SUCCESS on success.
+* STATUS_INSUFFICIENT_RESOURCES if an allocation fails.
+* STATUS_NOT_IMPLEMENTED if the new index can't fit within MaxIndexSize.
+*
+* @remarks
+* If the function succeeds, it's the caller's responsibility to free IndexRoot with ExFreePoolWithTag().
+*/
+NTSTATUS
+CreateIndexRootFromBTree(PDEVICE_EXTENSION DeviceExt,
+ PB_TREE Tree,
+ ULONG MaxIndexSize,
+ PINDEX_ROOT_ATTRIBUTE *IndexRoot,
+ ULONG *Length)
+{
+ PINDEX_ENTRY_ATTRIBUTE CurrentNodeEntry;
+ PINDEX_ROOT_ATTRIBUTE NewIndexRoot = ExAllocatePoolWithTag(NonPagedPool,
+ DeviceExt->NtfsInfo.BytesPerFileRecord,
+ TAG_NTFS);
+
+ DPRINT1("CreateIndexRootFromBTree(%p, %p, 0x%lx, %p, %p)\n", DeviceExt, Tree, MaxIndexSize, IndexRoot, Length);
+
+ if (!NewIndexRoot)
+ {
+ DPRINT1("Failed to allocate memory for Index Root!\n");
+ return STATUS_INSUFFICIENT_RESOURCES;
+ }
+
+ // Setup the new index root
+ RtlZeroMemory(NewIndexRoot, DeviceExt->NtfsInfo.BytesPerFileRecord);
+
+ NewIndexRoot->AttributeType = AttributeFileName;
+ NewIndexRoot->CollationRule = COLLATION_FILE_NAME;
+ NewIndexRoot->SizeOfEntry = DeviceExt->NtfsInfo.BytesPerIndexRecord;
+ // If Bytes per index record is less than cluster size, clusters per index record becomes sectors per index
+ if (NewIndexRoot->SizeOfEntry < DeviceExt->NtfsInfo.BytesPerCluster)
+ NewIndexRoot->ClustersPerIndexRecord = NewIndexRoot->SizeOfEntry / DeviceExt->NtfsInfo.BytesPerSector;
+ else
+ NewIndexRoot->ClustersPerIndexRecord = NewIndexRoot->SizeOfEntry / DeviceExt->NtfsInfo.BytesPerCluster;
+
+ // Setup the Index node header
+ NewIndexRoot->Header.FirstEntryOffset = sizeof(INDEX_HEADER_ATTRIBUTE);
+ NewIndexRoot->Header.Flags = INDEX_ROOT_SMALL;
+
+ // Start summing the total size of this node's entries
+ NewIndexRoot->Header.TotalSizeOfEntries = NewIndexRoot->Header.FirstEntryOffset;
+
+ // Setup each Node Entry
+ PB_TREE_KEY CurrentKey = Tree->RootNode->FirstKey;
+ CurrentNodeEntry = (PINDEX_ENTRY_ATTRIBUTE)((ULONG_PTR)NewIndexRoot
+ + FIELD_OFFSET(INDEX_ROOT_ATTRIBUTE, Header)
+ + NewIndexRoot->Header.FirstEntryOffset);
+ for (int i = 0; i < Tree->RootNode->KeyCount; i++)
+ {
+ // Would adding the current entry to the index increase the index size beyond the limit we've set?
+ ULONG IndexSize = FIELD_OFFSET(INDEX_ROOT_ATTRIBUTE, Header)
+ + NewIndexRoot->Header.FirstEntryOffset
+ + NewIndexRoot->Header.TotalSizeOfEntries
+ + CurrentNodeEntry->Length;
+ if (IndexSize > MaxIndexSize)
+ {
+ DPRINT1("TODO: Adding file would require creating an index allocation!\n");
+ ExFreePoolWithTag(NewIndexRoot, TAG_NTFS);
+ return STATUS_NOT_IMPLEMENTED;
+ }
+
+ // Copy the index entry
+ if (CurrentKey->IndexEntry->Length > 0)
+ RtlCopyMemory(CurrentNodeEntry, CurrentKey->IndexEntry, CurrentKey->IndexEntry->Length);
+ else
+ DPRINT1("DRIVER ERROR: CurrentKey->IndexEntry->Length <= 0 !\n");
+
+ DPRINT1("Index Node Entry Stream Length: %u\nIndex Node Entry Length: %u\n",
+ CurrentNodeEntry->KeyLength,
+ CurrentNodeEntry->Length);
+
+ // Add Length of Current Entry to Total Size of Entries
+ NewIndexRoot->Header.TotalSizeOfEntries += CurrentNodeEntry->Length;
+
+ // Go to the next node
+ CurrentNodeEntry = (PINDEX_ENTRY_ATTRIBUTE)((ULONG_PTR)CurrentNodeEntry + CurrentNodeEntry->Length);
+
+ CurrentKey = CurrentKey->NextKey;
+ }
+
+ NewIndexRoot->Header.AllocatedSize = NewIndexRoot->Header.TotalSizeOfEntries;
+
+ *IndexRoot = NewIndexRoot;
+ *Length = NewIndexRoot->Header.AllocatedSize + FIELD_OFFSET(INDEX_ROOT_ATTRIBUTE, Header);
+
+ return STATUS_SUCCESS;
+}
+
+VOID
+DestroyBTreeKey(PB_TREE_KEY Key)
+{
+ if (Key->IndexEntry)
+ ExFreePoolWithTag(Key->IndexEntry, TAG_NTFS);
+
+ // We'll destroy Key->LesserChild here after we start using it
+
+ ExFreePoolWithTag(Key, TAG_NTFS);
+}
+
+VOID
+DestroyBTreeNode(PB_TREE_FILENAME_NODE Node)
+{
+ PB_TREE_KEY NextKey;
+ PB_TREE_KEY CurrentKey = Node->FirstKey;
+ for (int i = 0; i < Node->KeyCount; i++)
+ {
+ NT_ASSERT(CurrentKey);
+ NextKey = CurrentKey->NextKey;
+ DestroyBTreeKey(CurrentKey);
+ CurrentKey = NextKey;
+ }
+
+ NT_ASSERT(NextKey == NULL);
+
+ ExFreePoolWithTag(Node, TAG_NTFS);
+}
+
+/**
+* @name DestroyBTree
+* @implemented
+*
+* Destroys a B-Tree.
+*
+* @param Tree
+* Pointer to the B_TREE which will be destroyed.
+*
+* @remarks
+* Destroys every bit of data stored in the tree.
+*/
+VOID
+DestroyBTree(PB_TREE Tree)
+{
+ DestroyBTreeNode(Tree->RootNode);
+ ExFreePoolWithTag(Tree, TAG_NTFS);
+}
+
+VOID
+DumpBTreeKey(PB_TREE_KEY Key, int Number, int Depth)
+{
+ for (int i = 0; i < Depth; i++)
+ DbgPrint(" ");
+ DbgPrint(" Key #%d", Number);
+
+ if (!(Key->IndexEntry->Flags & NTFS_INDEX_ENTRY_END))
+ {
+ UNICODE_STRING FileName;
+ FileName.Length = Key->IndexEntry->FileName.NameLength * 2;
+ FileName.MaximumLength = FileName.Length;
+ FileName.Buffer = Key->IndexEntry->FileName.Name;
+ DbgPrint(" '%wZ'\n", &FileName);
+ }
+ else
+ DbgPrint(" (Dummy Key)\n");
+}
+
+DumpBTreeNode(PB_TREE_FILENAME_NODE Node, int Number, int Depth)
+{
+ for (int i = 0; i < Depth; i++)
+ DbgPrint(" ");
+ DbgPrint("Node #%d, Depth %d\n", Number, Depth);
+
+ PB_TREE_KEY CurrentKey = Node->FirstKey;
+ for (int i = 0; i < Node->KeyCount; i++)
+ {
+ DumpBTreeKey(CurrentKey, i, Depth);
+ CurrentKey = CurrentKey->NextKey;
+ }
+}
+
+/**
+* @name DumpBTree
+* @implemented
+*
+* Displays a B-Tree.
+*
+* @param Tree
+* Pointer to the B_TREE which will be displayed.
+*
+* @remarks
+* Displays a diagnostic summary of a B_TREE.
+*/
+VOID
+DumpBTree(PB_TREE Tree)
+{
+ DbgPrint("B_TREE @ %p\n", Tree);
+ DumpBTreeNode(Tree->RootNode, 0, 0);
+}
+
+/**
+* @name NtfsInsertKey
+* @implemented
+*
+* Inserts a FILENAME_ATTRIBUTE into a B-Tree node.
+*
+* @param FileReference
+* Reference number to the file being added. This will be a combination of the MFT index and update sequence number.
+*
+* @param FileNameAttribute
+* Pointer to a FILENAME_ATTRIBUTE which is the data for the key that will be added to the tree. A copy will be made.
+*
+* @param Node
+* Pointer to a B_TREE_FILENAME_NODE into which a new key will be inserted, in order.
+*
+* @param CaseSensitive
+* Boolean indicating if the function should operate in case-sensitive mode. This will be TRUE
+* if an application created the file with the FILE_FLAG_POSIX_SEMANTICS flag.
+*
+* @remarks
+* A node is always sorted, with the least comparable filename stored first and a dummy key to mark the end.
+*/
+NTSTATUS
+NtfsInsertKey(ULONGLONG FileReference,
+ PFILENAME_ATTRIBUTE FileNameAttribute,
+ PB_TREE_FILENAME_NODE Node,
+ BOOLEAN CaseSensitive)
+{
+ // Calculate size of Attribute and Index Entry
+ ULONG AttributeSize = GetFileNameAttributeLength(FileNameAttribute);
+ ULONG EntrySize = ALIGN_UP_BY(AttributeSize + FIELD_OFFSET(INDEX_ENTRY_ATTRIBUTE, FileName), 8);
+ PINDEX_ENTRY_ATTRIBUTE NewEntry;
+
+ DPRINT1("NtfsInsertKey(0x%02I64, %p, %p, %s)\n",
+ FileReference,
+ FileNameAttribute,
+ Node,
+ CaseSensitive ? "TRUE" : "FALSE");
+
+ // Create a new Index Entry for the file
+ NewEntry = ExAllocatePoolWithTag(NonPagedPool, EntrySize, TAG_NTFS);
+ if (!NewEntry)
+ {
+ DPRINT1("ERROR: Failed to allocate memory for Index Entry!\n");
+ return STATUS_INSUFFICIENT_RESOURCES;
+ }
+
+ // Setup the Index Entry
+ RtlZeroMemory(NewEntry, EntrySize);
+ NewEntry->Data.Directory.IndexedFile = FileReference;
+ NewEntry->Length = EntrySize;
+ NewEntry->KeyLength = AttributeSize;
+
+ // Copy the FileNameAttribute
+ RtlCopyMemory(&NewEntry->FileName, FileNameAttribute, AttributeSize);
+
+ // Setup the New Key
+ PB_TREE_KEY NewKey = ExAllocatePoolWithTag(NonPagedPool, sizeof(B_TREE_KEY), TAG_NTFS);
+ NewKey->IndexEntry = NewEntry;
+ NewKey->NextKey = NULL;
+
+ // Find where to insert the key
+ PB_TREE_KEY CurrentKey = Node->FirstKey;
+ PB_TREE_KEY PreviousKey = NULL;
+ for (int i = 0; i < Node->KeyCount; i++)
+ {
+ // Should the New Key go before the current key?
+ LONG Comparison = CompareTreeKeys(NewKey, CurrentKey, CaseSensitive);
+ if (Comparison == 0)
+ {
+ DPRINT1("DRIVER ERROR: Asked to insert key into tree that already has it!\n");
+ ExFreePoolWithTag(NewKey, TAG_NTFS);
+ ExFreePoolWithTag(NewEntry, TAG_NTFS);
+ return STATUS_INVALID_PARAMETER;
+ }
+ if (Comparison < 0)
+ {
+ // NewKey is < CurrentKey
+ // Insert New Key before Current Key
+ NewKey->NextKey = CurrentKey;
+
+ // was CurrentKey the first key?
+ if (CurrentKey == Node->FirstKey)
+ Node->FirstKey = NewKey;
+ else
+ PreviousKey->NextKey = NewKey;
+ break;
+ }
+
+ PreviousKey = CurrentKey;
+ CurrentKey = CurrentKey->NextKey;
+ }
+
+ Node->KeyCount++;
+
+ // NewEntry and NewKey will be destroyed later by DestroyBTree()
+
+ return STATUS_SUCCESS;
+}
Propchange: branches/GSoC_2016/NTFS/drivers/filesystems/ntfs/btree.c
------------------------------------------------------------------------------
svn:eol-style = native
Modified: branches/GSoC_2016/NTFS/drivers/filesystems/ntfs/create.c
URL: http://svn.reactos.org/svn/reactos/branches/GSoC_2016/NTFS/drivers/filesyst…
==============================================================================
--- branches/GSoC_2016/NTFS/drivers/filesystems/ntfs/create.c [iso-8859-1] (original)
+++ branches/GSoC_2016/NTFS/drivers/filesystems/ntfs/create.c [iso-8859-1] Wed Jun 28 03:45:52 2017
@@ -747,7 +747,8 @@
Status = NtfsAddFilenameToDirectory(DeviceExt,
ParentMftIndex,
FileMftIndex,
- FilenameAttribute);
+ FilenameAttribute,
+ CaseSensitive);
}
ExFreePoolWithTag(FileRecord, TAG_NTFS);
Modified: branches/GSoC_2016/NTFS/drivers/filesystems/ntfs/dirctl.c
URL: http://svn.reactos.org/svn/reactos/branches/GSoC_2016/NTFS/drivers/filesyst…
==============================================================================
--- branches/GSoC_2016/NTFS/drivers/filesystems/ntfs/dirctl.c [iso-8859-1] (original)
+++ branches/GSoC_2016/NTFS/drivers/filesystems/ntfs/dirctl.c [iso-8859-1] Wed Jun 28 03:45:52 2017
@@ -53,13 +53,17 @@
* @param FilenameAttribute
* Pointer to the FILENAME_ATTRIBUTE of the file being added to the directory.
*
+* @param CaseSensitive
+* Boolean indicating if the function should operate in case-sensitive mode. This will be TRUE
+* if an application created the file with the FILE_FLAG_POSIX_SEMANTICS flag.
+*
* @return
* STATUS_SUCCESS on success.
* STATUS_INSUFFICIENT_RESOURCES if an allocation fails.
* STATUS_NOT_IMPLEMENTED if target address isn't at the end of the given file record.
*
* @remarks
-* WIP - Can only support an empty directory.
+* WIP - Can only support a few files in a directory.
* One FILENAME_ATTRIBUTE is added to the directory's index for each link to that file. So, each
* file which contains one FILENAME_ATTRIBUTE for a long name and another for the 8.3 name, will
* get both attributes added to its parent directory.
@@ -68,7 +72,8 @@
NtfsAddFilenameToDirectory(PDEVICE_EXTENSION DeviceExt,
ULONGLONG DirectoryMftIndex,
ULONGLONG FileReferenceNumber,
- PFILENAME_ATTRIBUTE FilenameAttribute)
+ PFILENAME_ATTRIBUTE FilenameAttribute,
+ BOOLEAN CaseSensitive)
{
NTSTATUS Status = STATUS_SUCCESS;
PFILE_RECORD_HEADER ParentFileRecord;
@@ -76,12 +81,14 @@
PINDEX_ROOT_ATTRIBUTE I30IndexRoot;
ULONG IndexRootOffset;
ULONGLONG I30IndexRootLength;
- PINDEX_ENTRY_ATTRIBUTE IndexNodeEntry;
ULONG LengthWritten;
PNTFS_ATTR_RECORD DestinationAttribute;
PINDEX_ROOT_ATTRIBUTE NewIndexRoot;
ULONG AttributeLength;
PNTFS_ATTR_RECORD NextAttribute;
+ PB_TREE NewTree;
+ ULONG BtreeIndexLength;
+ ULONG MaxIndexSize;
// Allocate memory for the parent directory
ParentFileRecord = ExAllocatePoolWithTag(NonPagedPool,
@@ -122,9 +129,15 @@
return Status;
}
+ // Find the maximum index size given what the file record can hold
+ MaxIndexSize = DeviceExt->NtfsInfo.BytesPerFileRecord
+ - IndexRootOffset
+ - IndexRootContext->Record.Resident.ValueOffset
+ - FIELD_OFFSET(INDEX_ROOT_ATTRIBUTE, Header)
+ - (sizeof(ULONG) * 2);
+
+ // Allocate memory for the index root data
I30IndexRootLength = AttributeDataLength(&IndexRootContext->Record);
-
- // Allocate memory for the index root data
I30IndexRoot = (PINDEX_ROOT_ATTRIBUTE)ExAllocatePoolWithTag(NonPagedPool, I30IndexRootLength, TAG_NTFS);
if (!I30IndexRoot)
{
@@ -144,82 +157,59 @@
return Status;
}
- // Make sure it's empty (temporarily)
- IndexNodeEntry = (PINDEX_ENTRY_ATTRIBUTE)((ULONG_PTR)I30IndexRoot + I30IndexRoot->Header.FirstEntryOffset + 0x10);
- if (IndexNodeEntry->Data.Directory.IndexedFile != 0 || IndexNodeEntry->Flags != 2)
- {
- DPRINT1("FIXME: File-creation is only supported in empty directories right now! Be patient! :)\n");
+ // Convert the index to a B*Tree
+ Status = CreateBTreeFromIndex(IndexRootContext, I30IndexRoot, &NewTree);
+ if (!NT_SUCCESS(Status))
+ {
+ DPRINT1("ERROR: Failed to create B-Tree from Index!\n");
ReleaseAttributeContext(IndexRootContext);
ExFreePoolWithTag(I30IndexRoot, TAG_NTFS);
ExFreePoolWithTag(ParentFileRecord, TAG_NTFS);
- return STATUS_NOT_IMPLEMENTED;
- }
-
- // Now we need to setup a new index root attribute to replace the old one
- NewIndexRoot = ExAllocatePoolWithTag(NonPagedPool, DeviceExt->NtfsInfo.BytesPerIndexRecord, TAG_NTFS);
- if (!NewIndexRoot)
- {
- DPRINT1("ERROR: Unable to allocate memory for new index root attribute!\n");
+ return Status;
+ }
+
+ DumpBTree(NewTree);
+
+ // Insert the key for the file we're adding
+ Status = NtfsInsertKey(FileReferenceNumber, FilenameAttribute, NewTree->RootNode, CaseSensitive);
+ if (!NT_SUCCESS(Status))
+ {
+ DPRINT1("ERROR: Failed to insert key into B-Tree!\n");
+ DestroyBTree(NewTree);
ReleaseAttributeContext(IndexRootContext);
ExFreePoolWithTag(I30IndexRoot, TAG_NTFS);
ExFreePoolWithTag(ParentFileRecord, TAG_NTFS);
- return STATUS_INSUFFICIENT_RESOURCES;
- }
+ return Status;
+ }
+
+ DumpBTree(NewTree);
- // Setup the new index record
- RtlZeroMemory(NewIndexRoot, DeviceExt->NtfsInfo.BytesPerIndexRecord); // shouldn't be necessary but aids in debugging
-
- NewIndexRoot->AttributeType = AttributeFileName;
- NewIndexRoot->CollationRule = COLLATION_FILE_NAME;
- NewIndexRoot->SizeOfEntry = DeviceExt->NtfsInfo.BytesPerIndexRecord;
- // If Bytes per index record is less than cluster size, clusters per index record becomes sectors per index
- if(NewIndexRoot->SizeOfEntry < DeviceExt->NtfsInfo.BytesPerCluster)
- NewIndexRoot->ClustersPerIndexRecord = NewIndexRoot->SizeOfEntry / DeviceExt->NtfsInfo.BytesPerSector;
- else
- NewIndexRoot->ClustersPerIndexRecord = NewIndexRoot->SizeOfEntry / DeviceExt->NtfsInfo.BytesPerCluster;
-
- // Setup the Index node header
- NewIndexRoot->Header.FirstEntryOffset = 0x10;
- NewIndexRoot->Header.Flags = INDEX_ROOT_SMALL;
- // still need to calculate sizes
-
- // The first index node entry will be for the filename we're adding
- IndexNodeEntry = (PINDEX_ENTRY_ATTRIBUTE)((ULONG_PTR)NewIndexRoot + NewIndexRoot->Header.FirstEntryOffset + 0x10);
- IndexNodeEntry->Data.Directory.IndexedFile = FileReferenceNumber;
- IndexNodeEntry->Flags = INDEX_ROOT_SMALL;
- IndexNodeEntry->KeyLength = FIELD_OFFSET(FILENAME_ATTRIBUTE, Name) + (2 * FilenameAttribute->NameLength);
- IndexNodeEntry->Length = ALIGN_UP_BY(IndexNodeEntry->KeyLength, 8) + FIELD_OFFSET(INDEX_ENTRY_ATTRIBUTE, FileName);
-
- // Now we can calculate the Node length (temp logic)
- NewIndexRoot->Header.TotalSizeOfEntries = NewIndexRoot->Header.FirstEntryOffset + IndexNodeEntry->Length + 0x10;
- NewIndexRoot->Header.AllocatedSize = NewIndexRoot->Header.TotalSizeOfEntries;
-
- DPRINT1("New Index Node Entry Stream Length: %u\nNew Inde Node Entry Length: %u\n",
- IndexNodeEntry->KeyLength,
- IndexNodeEntry->Length);
-
- // copy over the attribute proper
- RtlCopyMemory(&IndexNodeEntry->FileName, FilenameAttribute, IndexNodeEntry->KeyLength);
-
- // Now setup the dummy key
- IndexNodeEntry = (PINDEX_ENTRY_ATTRIBUTE)((ULONG_PTR)IndexNodeEntry + IndexNodeEntry->Length);
-
- IndexNodeEntry->Data.Directory.IndexedFile = 0;
- IndexNodeEntry->Length = 0x10;
- IndexNodeEntry->KeyLength = 0;
- IndexNodeEntry->Flags = NTFS_INDEX_ENTRY_END;
-
- // This is when we'd normally setup the length (already done above)
+ // Convert B*Tree back to Index Root
+ Status = CreateIndexRootFromBTree(DeviceExt, NewTree, MaxIndexSize, &NewIndexRoot, &BtreeIndexLength);
+ if (!NT_SUCCESS(Status))
+ {
+ DPRINT1("ERROR: Failed to create Index root from B-Tree!\n");
+ DestroyBTree(NewTree);
+ ReleaseAttributeContext(IndexRootContext);
+ ExFreePoolWithTag(I30IndexRoot, TAG_NTFS);
+ ExFreePoolWithTag(ParentFileRecord, TAG_NTFS);
+ return Status;
+ }
+
+ // We're done with the B-Tree now
+ DestroyBTree(NewTree);
// Write back the new index root attribute to the parent directory file record
- // First, we need to make sure the attribute is large enough.
+ // First, we need to resize the attribute.
+ // CreateIndexRootFromBTree() should have verified that the index root fits within MaxIndexSize.
// We can't set the size as we normally would, because if we extend past the file record,
// we must create an index allocation and index bitmap (TODO). Also TODO: support file records with
// $ATTRIBUTE_LIST's.
AttributeLength = NewIndexRoot->Header.AllocatedSize + FIELD_OFFSET(INDEX_ROOT_ATTRIBUTE, Header);
DestinationAttribute = (PNTFS_ATTR_RECORD)((ULONG_PTR)ParentFileRecord + IndexRootOffset);
+ // Find the attribute (or attribute-end marker) after the index root
NextAttribute = (PNTFS_ATTR_RECORD)((ULONG_PTR)DestinationAttribute + DestinationAttribute->Length);
if (NextAttribute->Type != AttributeEnd)
{
@@ -230,24 +220,27 @@
ExFreePoolWithTag(ParentFileRecord, TAG_NTFS);
return STATUS_NOT_IMPLEMENTED;
}
-
+
// Update the length of the attribute in the file record of the parent directory
InternalSetResidentAttributeLength(IndexRootContext,
ParentFileRecord,
IndexRootOffset,
AttributeLength);
+ NT_ASSERT(ParentFileRecord->BytesInUse <= DeviceExt->NtfsInfo.BytesPerFileRecord);
+
Status = UpdateFileRecord(DeviceExt, DirectoryMftIndex, ParentFileRecord);
if (!NT_SUCCESS(Status))
{
DPRINT1("ERROR: Failed to update file record of directory with index: %llx\n", DirectoryMftIndex);
ExFreePoolWithTag(ParentFileRecord, TAG_NTFS);
ExFreePoolWithTag(NewIndexRoot, TAG_NTFS);
+ ReleaseAttributeContext(IndexRootContext);
ExFreePoolWithTag(I30IndexRoot, TAG_NTFS);
return Status;
}
- // Update the parent directory with the new index root
+ // Write the new index root to disk
Status = WriteAttribute(DeviceExt,
IndexRootContext,
0,
Modified: branches/GSoC_2016/NTFS/drivers/filesystems/ntfs/ntfs.h
URL: http://svn.reactos.org/svn/reactos/branches/GSoC_2016/NTFS/drivers/filesyst…
==============================================================================
--- branches/GSoC_2016/NTFS/drivers/filesystems/ntfs/ntfs.h [iso-8859-1] (original)
+++ branches/GSoC_2016/NTFS/drivers/filesystems/ntfs/ntfs.h [iso-8859-1] Wed Jun 28 03:45:52 2017
@@ -395,6 +395,28 @@
FILENAME_ATTRIBUTE FileName;
} INDEX_ENTRY_ATTRIBUTE, *PINDEX_ENTRY_ATTRIBUTE;
+// Keys are arranged in nodes as an ordered, linked list
+typedef struct _B_TREE_KEY
+{
+ struct _B_TREE_KEY *NextKey;
+ // PB_TREE_FILENAME_NODE LesserChild; // we aren't worried about multi-level trees yet
+ PINDEX_ENTRY_ATTRIBUTE IndexEntry; // must be last member for FIELD_OFFSET
+}B_TREE_KEY, *PB_TREE_KEY;
+
+// Every Node is just an ordered list of keys.
+// Sub-nodes can be found attached to a key (if they exist).
+// A key's sub-node precedes that key in the ordered list.
+typedef struct
+{
+ int KeyCount;
+ PB_TREE_KEY FirstKey;
+} B_TREE_FILENAME_NODE, *PB_TREE_FILENAME_NODE;
+
+typedef struct
+{
+ PB_TREE_FILENAME_NODE RootNode;
+} B_TREE, *PB_TREE;
+
typedef struct
{
ULONGLONG Unknown1;
@@ -559,6 +581,8 @@
LONGLONG *DataRunOffset,
ULONGLONG *DataRunLength);
+ULONG GetFileNameAttributeLength(PFILENAME_ATTRIBUTE FileNameAttribute);
+
VOID
NtfsDumpDataRuns(PVOID StartOfRun,
ULONGLONG CurrentLCN);
@@ -645,6 +669,38 @@
IN BOOLEAN Override);
+/* btree.c */
+
+LONG
+CompareTreeKeys(PB_TREE_KEY Key1,
+ PB_TREE_KEY Key2,
+ BOOLEAN CaseSensitive);
+
+NTSTATUS
+CreateBTreeFromIndex(/*PDEVICE_EXTENSION Vcb,*/
+ PNTFS_ATTR_CONTEXT IndexRootContext,
+ PINDEX_ROOT_ATTRIBUTE IndexRoot,
+ PB_TREE *NewTree);
+
+NTSTATUS
+CreateIndexRootFromBTree(PDEVICE_EXTENSION DeviceExt,
+ PB_TREE Tree,
+ ULONG MaxIndexSize,
+ PINDEX_ROOT_ATTRIBUTE *IndexRoot,
+ ULONG *Length);
+
+VOID
+DestroyBTree(PB_TREE Tree);
+
+VOID
+DumpBTree(PB_TREE Tree);
+
+NTSTATUS
+NtfsInsertKey(ULONGLONG FileReference,
+ PFILENAME_ATTRIBUTE FileNameAttribute,
+ PB_TREE_FILENAME_NODE Node,
+ BOOLEAN CaseSensitive);
+
/* close.c */
NTSTATUS
@@ -683,8 +739,9 @@
NTSTATUS
NtfsAddFilenameToDirectory(PDEVICE_EXTENSION DeviceExt,
ULONGLONG DirectoryMftIndex,
- ULONGLONG FileMftIndex,
- PFILENAME_ATTRIBUTE FilenameAttribute);
+ ULONGLONG FileReferenceNumber,
+ PFILENAME_ATTRIBUTE FilenameAttribute,
+ BOOLEAN CaseSensitive);
ULONGLONG
NtfsGetFileSize(PDEVICE_EXTENSION DeviceExt,
Author: hbelusca
Date: Wed Jun 28 00:04:13 2017
New Revision: 75222
URL: http://svn.reactos.org/svn/reactos?rev=75222&view=rev
Log:
[CMLIB]: Addendum to r63495: Fix the CmpCopyKeyValueList() helper to make it what it is supposed to do: copy the list of values of a given key: this means, also copying the values themselves!!
For that aim I also introduce a CmpCopyValue() helper that allows copying the value data of a given registry value, taking into account whether the value is "small", normal or "big" (we don't support "big values" yet). This function allocates and copies the necessary hive cells corresponding to the given value. Only then, we add a new entry into the registry key value list that is grown dynamically.
Cleanup is performed in case of failure.
Now we can export registry sub-trees as registry hives, and successfully re-mount them in the registry.
CORE-13476 CORE-8259 CORE-10793
Modified:
trunk/reactos/sdk/lib/cmlib/cmvalue.c
Modified: trunk/reactos/sdk/lib/cmlib/cmvalue.c
URL: http://svn.reactos.org/svn/reactos/trunk/reactos/sdk/lib/cmlib/cmvalue.c?re…
==============================================================================
--- trunk/reactos/sdk/lib/cmlib/cmvalue.c [iso-8859-1] (original)
+++ trunk/reactos/sdk/lib/cmlib/cmvalue.c [iso-8859-1] Wed Jun 28 00:04:13 2017
@@ -190,7 +190,7 @@
return NULL;
}
- /* This should never happen!*/
+ /* This should never happen! */
if (BufferAllocated)
{
/* Free the buffer and bugcheck */
@@ -379,6 +379,7 @@
PCELL_DATA DestinationData = NULL;
HCELL_INDEX DestinationCell = HCELL_NIL;
LONG DataSize;
+
PAGED_CODE();
/* Get the data and the size of the source cell */
@@ -401,11 +402,115 @@
Cleanup:
/* Release the cells */
+ if (DestinationData) HvReleaseCell(DestinationHive, DestinationCell);
if (SourceData) HvReleaseCell(SourceHive, SourceCell);
- if (DestinationData) HvReleaseCell(DestinationHive, DestinationCell);
/* Return the destination cell index */
return DestinationCell;
+}
+
+HCELL_INDEX
+NTAPI
+CmpCopyValue(IN PHHIVE SourceHive,
+ IN HCELL_INDEX SourceValueCell,
+ IN PHHIVE DestinationHive,
+ IN HSTORAGE_TYPE StorageType)
+{
+ PCM_KEY_VALUE Value, NewValue;
+ HCELL_INDEX NewValueCell, NewDataCell;
+ PCELL_DATA CellData;
+ ULONG SmallData;
+ ULONG DataSize;
+ BOOLEAN IsSmall;
+
+ PAGED_CODE();
+
+ /* Get the actual source data */
+ Value = (PCM_KEY_VALUE)HvGetCell(SourceHive, SourceValueCell);
+ if (!Value) ASSERT(FALSE);
+
+ /* Copy the value cell body */
+ NewValueCell = CmpCopyCell(SourceHive,
+ SourceValueCell,
+ DestinationHive,
+ StorageType);
+ if (NewValueCell == HCELL_NIL)
+ {
+ /* Not enough storage space */
+ goto Quit;
+ }
+
+ /* Copy the value data */
+ IsSmall = CmpIsKeyValueSmall(&DataSize, Value->DataLength);
+ if (DataSize == 0)
+ {
+ /* Nothing to copy */
+
+ NewValue = (PCM_KEY_VALUE)HvGetCell(DestinationHive, NewValueCell);
+ ASSERT(NewValue);
+ NewValue->DataLength = 0;
+ NewValue->Data = HCELL_NIL;
+ HvReleaseCell(DestinationHive, NewValueCell);
+
+ goto Quit;
+ }
+
+ if (DataSize <= CM_KEY_VALUE_SMALL)
+ {
+ if (IsSmall)
+ {
+ /* Small value, copy directly */
+ SmallData = Value->Data;
+ }
+ else
+ {
+ /* The value is small, but was stored in a regular cell. Get the data from it. */
+ CellData = HvGetCell(SourceHive, Value->Data);
+ ASSERT(CellData);
+ SmallData = *(PULONG)CellData;
+ HvReleaseCell(SourceHive, Value->Data);
+ }
+
+ /* This is a small key, set the data directly inside */
+ NewValue = (PCM_KEY_VALUE)HvGetCell(DestinationHive, NewValueCell);
+ ASSERT(NewValue);
+ NewValue->DataLength = DataSize + CM_KEY_VALUE_SPECIAL_SIZE;
+ NewValue->Data = SmallData;
+ HvReleaseCell(DestinationHive, NewValueCell);
+ }
+ else
+ {
+ /* Big keys are currently unsupported */
+ ASSERT_VALUE_BIG(SourceHive, DataSize);
+ // Should use CmpGetValueData and CmpSetValueDataNew for big values!
+
+ /* Regular value */
+
+ /* Copy the data cell */
+ NewDataCell = CmpCopyCell(SourceHive,
+ Value->Data,
+ DestinationHive,
+ StorageType);
+ if (NewDataCell == HCELL_NIL)
+ {
+ /* Not enough storage space */
+ HvFreeCell(DestinationHive, NewValueCell);
+ NewValueCell = HCELL_NIL;
+ goto Quit;
+ }
+
+ NewValue = (PCM_KEY_VALUE)HvGetCell(DestinationHive, NewValueCell);
+ ASSERT(NewValue);
+ NewValue->DataLength = DataSize;
+ NewValue->Data = NewDataCell;
+ HvReleaseCell(DestinationHive, NewValueCell);
+ }
+
+Quit:
+ HvReleaseCell(SourceHive, SourceValueCell);
+
+ /* Return the copied value body cell index */
+ return NewValueCell;
}
NTSTATUS
@@ -417,51 +522,82 @@
IN HSTORAGE_TYPE StorageType)
{
NTSTATUS Status = STATUS_SUCCESS;
- HCELL_INDEX CellIndex = HCELL_NIL;
+ PCELL_DATA SrcListData = NULL, DestListData = NULL;
+ HCELL_INDEX NewValue;
ULONG Index;
- PCELL_DATA SrcListData = NULL;
- PCELL_DATA DestListData = NULL;
-
- PAGED_CODE();
-
- /* Set the count */
- DestValueList->Count = SrcValueList->Count;
+
+ PAGED_CODE();
+
+ /* Reset the destination value list */
+ DestValueList->Count = 0;
+ DestValueList->List = HCELL_NIL;
/* Check if the list is empty */
- if (!DestValueList->Count)
- {
- DestValueList->List = HCELL_NIL;
+ if (!SrcValueList->Count)
return STATUS_SUCCESS;
- }
-
- /* Create a simple copy of the list */
- CellIndex = CmpCopyCell(SourceHive,
- SrcValueList->List,
- DestinationHive,
- StorageType);
- if (CellIndex == HCELL_NIL) return STATUS_INSUFFICIENT_RESOURCES;
-
- /* Get the source and the destination value list */
+
+ /* Get the source value list */
SrcListData = HvGetCell(SourceHive, SrcValueList->List);
- DestListData = HvGetCell(DestinationHive, CellIndex);
+ ASSERT(SrcListData);
/* Copy the actual values */
for (Index = 0; Index < SrcValueList->Count; Index++)
{
- DestListData->u.KeyList[Index] = CmpCopyCell(SourceHive,
- SrcListData->u.KeyList[Index],
- DestinationHive,
- StorageType);
- if (DestListData->u.KeyList[Index] == HCELL_NIL)
- {
+ NewValue = CmpCopyValue(SourceHive,
+ SrcListData->u.KeyList[Index],
+ DestinationHive,
+ StorageType);
+ if (NewValue == HCELL_NIL)
+ {
+ /* Not enough storage space, stop there and cleanup afterwards */
Status = STATUS_INSUFFICIENT_RESOURCES;
break;
}
+
+ /* Add this value cell to the child list */
+ Status = CmpAddValueToList(DestinationHive,
+ NewValue,
+ Index,
+ StorageType,
+ DestValueList);
+ if (!NT_SUCCESS(Status))
+ {
+ /* Not enough storage space, stop there */
+
+ /* Cleanup the newly-created value here, the other ones will be cleaned up afterwards */
+ if (!CmpFreeValue(DestinationHive, NewValue))
+ HvFreeCell(DestinationHive, NewValue);
+ break;
+ }
+ }
+
+ /* Revert-cleanup if failure */
+ if (!NT_SUCCESS(Status) && (DestValueList->List != HCELL_NIL))
+ {
+ /* Do not use CmpRemoveValueFromList but directly delete the data */
+
+ /* Get the destination value list */
+ DestListData = HvGetCell(DestinationHive, DestValueList->List);
+ ASSERT(DestListData);
+
+ /* Delete each copied value */
+ while (Index--)
+ {
+ NewValue = DestListData->u.KeyList[Index];
+ if (!CmpFreeValue(DestinationHive, NewValue))
+ HvFreeCell(DestinationHive, NewValue);
+ }
+
+ /* Release and free the list */
+ HvReleaseCell(DestinationHive, DestValueList->List);
+ HvFreeCell(DestinationHive, DestValueList->List);
+
+ DestValueList->Count = 0;
+ DestValueList->List = HCELL_NIL;
}
/* Release the cells */
- if (SrcListData) HvReleaseCell(SourceHive, SrcValueList->List);
- if (DestListData) HvReleaseCell(DestinationHive, CellIndex);
+ HvReleaseCell(SourceHive, SrcValueList->List);
return Status;
}