10 Dec
2017
10 Dec
'17
11:50 a.m.
https://git.reactos.org/?p=reactos.git;a=commitdiff;h=54f5c3b6ec26f1758b878…
commit 54f5c3b6ec26f1758b878b901f4a2f3f9a1a47cc
Author: Trevor Thompson <tmt256(a)email.vccs.edu>
AuthorDate: Wed Jun 28 03:45:52 2017 +0000
[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.
svn path=/branches/GSoC_2016/NTFS/; revision=75223
---
drivers/filesystems/ntfs/CMakeLists.txt | 1 +
drivers/filesystems/ntfs/attrib.c | 6 +
drivers/filesystems/ntfs/btree.c | 520 ++++++++++++++++++++++++++++++++
drivers/filesystems/ntfs/create.c | 3 +-
drivers/filesystems/ntfs/dirctl.c | 117 ++++---
drivers/filesystems/ntfs/ntfs.h | 61 +++-
6 files changed, 643 insertions(+), 65 deletions(-)
diff --git a/drivers/filesystems/ntfs/CMakeLists.txt
b/drivers/filesystems/ntfs/CMakeLists.txt
index ff3b35f647..b9c72a72e7 100644
--- a/drivers/filesystems/ntfs/CMakeLists.txt
+++ b/drivers/filesystems/ntfs/CMakeLists.txt
@@ -1,6 +1,7 @@
list(APPEND SOURCE
attrib.c
+ btree.c
blockdev.c
cleanup.c
close.c
diff --git a/drivers/filesystems/ntfs/attrib.c b/drivers/filesystems/ntfs/attrib.c
index 90e20d3819..239e1c0400 100644
--- a/drivers/filesystems/ntfs/attrib.c
+++ b/drivers/filesystems/ntfs/attrib.c
@@ -1566,6 +1566,12 @@ GetStandardInformationFromRecord(PDEVICE_EXTENSION Vcb,
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)
diff --git a/drivers/filesystems/ntfs/btree.c b/drivers/filesystems/ntfs/btree.c
new file mode 100644
index 0000000000..604c02c290
--- /dev/null
+++ b/drivers/filesystems/ntfs/btree.c
@@ -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;
+}
\ No newline at end of file
diff --git a/drivers/filesystems/ntfs/create.c b/drivers/filesystems/ntfs/create.c
index f52cd7d187..586da89b36 100644
--- a/drivers/filesystems/ntfs/create.c
+++ b/drivers/filesystems/ntfs/create.c
@@ -747,7 +747,8 @@ NtfsCreateFileRecord(PDEVICE_EXTENSION DeviceExt,
Status = NtfsAddFilenameToDirectory(DeviceExt,
ParentMftIndex,
FileMftIndex,
- FilenameAttribute);
+ FilenameAttribute,
+ CaseSensitive);
}
ExFreePoolWithTag(FileRecord, TAG_NTFS);
diff --git a/drivers/filesystems/ntfs/dirctl.c b/drivers/filesystems/ntfs/dirctl.c
index 4d19052ac9..ba7231dc80 100644
--- a/drivers/filesystems/ntfs/dirctl.c
+++ b/drivers/filesystems/ntfs/dirctl.c
@@ -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 @@ NTSTATUS
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 @@ NtfsAddFilenameToDirectory(PDEVICE_EXTENSION DeviceExt,
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 @@ NtfsAddFilenameToDirectory(PDEVICE_EXTENSION DeviceExt,
return Status;
}
- I30IndexRootLength = AttributeDataLength(&IndexRootContext->Record);
+ // 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);
I30IndexRoot = (PINDEX_ROOT_ATTRIBUTE)ExAllocatePoolWithTag(NonPagedPool,
I30IndexRootLength, TAG_NTFS);
if (!I30IndexRoot)
{
@@ -144,82 +157,59 @@ NtfsAddFilenameToDirectory(PDEVICE_EXTENSION DeviceExt,
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)
+ // Convert the index to a B*Tree
+ Status = CreateBTreeFromIndex(IndexRootContext, I30IndexRoot, &NewTree);
+ if (!NT_SUCCESS(Status))
{
- DPRINT1("FIXME: File-creation is only supported in empty directories right
now! Be patient! :)\n");
+ DPRINT1("ERROR: Failed to create B-Tree from Index!\n");
ReleaseAttributeContext(IndexRootContext);
ExFreePoolWithTag(I30IndexRoot, TAG_NTFS);
ExFreePoolWithTag(ParentFileRecord, TAG_NTFS);
- return STATUS_NOT_IMPLEMENTED;
+ return Status;
}
-
- // 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)
+
+ DumpBTree(NewTree);
+
+ // Insert the key for the file we're adding
+ Status = NtfsInsertKey(FileReferenceNumber, FilenameAttribute, NewTree->RootNode,
CaseSensitive);
+ if (!NT_SUCCESS(Status))
{
- DPRINT1("ERROR: Unable to allocate memory for new index root
attribute!\n");
+ 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 @@ NtfsAddFilenameToDirectory(PDEVICE_EXTENSION DeviceExt,
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,
diff --git a/drivers/filesystems/ntfs/ntfs.h b/drivers/filesystems/ntfs/ntfs.h
index d738ef5fe2..3e01f469a4 100644
--- a/drivers/filesystems/ntfs/ntfs.h
+++ b/drivers/filesystems/ntfs/ntfs.h
@@ -395,6 +395,28 @@ typedef struct
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 @@ DecodeRun(PUCHAR DataRun,
LONGLONG *DataRunOffset,
ULONGLONG *DataRunLength);
+ULONG GetFileNameAttributeLength(PFILENAME_ATTRIBUTE FileNameAttribute);
+
VOID
NtfsDumpDataRuns(PVOID StartOfRun,
ULONGLONG CurrentLCN);
@@ -645,6 +669,38 @@ NtfsDeviceIoControl(IN PDEVICE_OBJECT DeviceObject,
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 @@ NtfsDeviceControl(PNTFS_IRP_CONTEXT IrpContext);
NTSTATUS
NtfsAddFilenameToDirectory(PDEVICE_EXTENSION DeviceExt,
ULONGLONG DirectoryMftIndex,
- ULONGLONG FileMftIndex,
- PFILENAME_ATTRIBUTE FilenameAttribute);
+ ULONGLONG FileReferenceNumber,
+ PFILENAME_ATTRIBUTE FilenameAttribute,
+ BOOLEAN CaseSensitive);
ULONGLONG
NtfsGetFileSize(PDEVICE_EXTENSION DeviceExt,