[reactos] 68/72: [NTFS] - Add some helper functions for new features. Add some fixes. Add support for creating an index allocation, splitting a b-tree node, or "demoting" the index root. This allows for file creation without functional limitations. +AddBitmap() - adds a $BITMAP attribute to a file record. +AddIndexAllocation() - adds an $INDEX_ALLOCATION attribute to a file record. +CountBTreeKeys() - Counts the number of linked B-Tree keys. CreateIndexBufferFromBTreeNode() - Set INDEX_NODE_LARG
10 Dec
2017
10 Dec
'17
11:50 a.m.
https://git.reactos.org/?p=reactos.git;a=commitdiff;h=52c30fdf37d3fd9a1583d…
commit 52c30fdf37d3fd9a1583d4052f6b11365099613c
Author: Trevor Thompson <tmt256(a)email.vccs.edu>
AuthorDate: Tue Aug 29 15:51:14 2017 +0000
[NTFS] - Add some helper functions for new features. Add some fixes. Add support for
creating an index allocation, splitting a b-tree node, or "demoting" the index
root. This allows for file creation without functional limitations.
+AddBitmap() - adds a $BITMAP attribute to a file record.
+AddIndexAllocation() - adds an $INDEX_ALLOCATION attribute to a file record.
+CountBTreeKeys() - Counts the number of linked B-Tree keys.
CreateIndexBufferFromBTreeNode() - Set INDEX_NODE_LARGE if the node has sub-nodes.
CreateIndexRootFromBTree() - Simplify the usage and math of MaxIndexSize; make it only
account for the cumulative size of the index entries.
+DemoteBTreeRoot() - Replaces the contents of an index root with a dummy key, and puts
those contents in a new node, which is made a child of the dummy key. This is done when an
index root grows too large.
+GetIndexEntryVCN() - Retrieves the VCN from an index entry.
NtfsAddFilenameToDirectory() - Fix math for MaxIndexRootSize.
NtfsInsertKey() - Add support for splitting a B-Tree node. Don't check size of
index root (that will be handled later).
+SplitBTreeNode() - Called when a B-Tree node grows too large.
UpdateIndexAllocation() - Create an $I30 index allocation attribute and bitmap
attribute if needed.
UpdateIndexNode() - Update children before updating the current node. Store VCN of
child nodes in the index entries of their respective keys.
svn path=/branches/GSoC_2016/NTFS/; revision=75707
---
drivers/filesystems/ntfs/attrib.c | 193 ++++++++++++
drivers/filesystems/ntfs/btree.c | 597 ++++++++++++++++++++++++++++++--------
drivers/filesystems/ntfs/mft.c | 186 +++++++++++-
drivers/filesystems/ntfs/ntfs.h | 35 ++-
4 files changed, 886 insertions(+), 125 deletions(-)
diff --git a/drivers/filesystems/ntfs/attrib.c b/drivers/filesystems/ntfs/attrib.c
index 34bee2a060..846c16da80 100644
--- a/drivers/filesystems/ntfs/attrib.c
+++ b/drivers/filesystems/ntfs/attrib.c
@@ -36,6 +36,100 @@
/* FUNCTIONS ****************************************************************/
+/**
+* @name AddBitmap
+* @implemented
+*
+* Adds a $BITMAP attribute to a given FileRecord.
+*
+* @param Vcb
+* Pointer to an NTFS_VCB for the destination volume.
+*
+* @param FileRecord
+* Pointer to a complete file record to add the attribute to.
+*
+* @param AttributeAddress
+* Pointer to the region of memory that will receive the $INDEX_ALLOCATION attribute.
+* This address must reside within FileRecord. Must be aligned to an 8-byte boundary
(relative to FileRecord).
+*
+* @param Name
+* Pointer to a string of 16-bit Unicode characters naming the attribute. Most often
L"$I30".
+*
+* @param NameLength
+* The number of wide-characters in the name. L"$I30" Would use 4 here.
+*
+* @return
+* STATUS_SUCCESS on success. STATUS_NOT_IMPLEMENTED if target address isn't at the
end
+* of the given file record, or if the file record isn't large enough for the
attribute.
+*
+* @remarks
+* Only adding the attribute to the end of the file record is supported; AttributeAddress
must
+* be of type AttributeEnd.
+* This could be improved by adding an $ATTRIBUTE_LIST to the file record if there's
not enough space.
+*
+*/
+NTSTATUS
+AddBitmap(PNTFS_VCB Vcb,
+ PFILE_RECORD_HEADER FileRecord,
+ PNTFS_ATTR_RECORD AttributeAddress,
+ PCWSTR Name,
+ USHORT NameLength)
+{
+ ULONG AttributeLength;
+ // Calculate the header length
+ ULONG ResidentHeaderLength = FIELD_OFFSET(NTFS_ATTR_RECORD, Resident.Reserved) +
sizeof(UCHAR);
+ ULONG FileRecordEnd = AttributeAddress->Length;
+ ULONG NameOffset;
+ ULONG ValueOffset;
+ // We'll start out with 8 bytes of bitmap data
+ ULONG ValueLength = 8;
+ ULONG BytesAvailable;
+
+ if (AttributeAddress->Type != AttributeEnd)
+ {
+ DPRINT1("FIXME: Can only add $BITMAP attribute to the end of a file
record.\n");
+ return STATUS_NOT_IMPLEMENTED;
+ }
+
+ NameOffset = ResidentHeaderLength;
+
+ // Calculate ValueOffset, which will be aligned to a 4-byte boundary
+ ValueOffset = ALIGN_UP_BY(NameOffset + (sizeof(WCHAR) * NameLength),
VALUE_OFFSET_ALIGNMENT);
+
+ // Calculate length of attribute
+ AttributeLength = ValueOffset + ValueLength;
+ AttributeLength = ALIGN_UP_BY(AttributeLength, ATTR_RECORD_ALIGNMENT);
+
+ // Make sure the file record is large enough for the new attribute
+ BytesAvailable = Vcb->NtfsInfo.BytesPerFileRecord - FileRecord->BytesInUse;
+ if (BytesAvailable < AttributeLength)
+ {
+ DPRINT1("FIXME: Not enough room in file record for index allocation
attribute!\n");
+ return STATUS_NOT_IMPLEMENTED;
+ }
+
+ // Set Attribute fields
+ RtlZeroMemory(AttributeAddress, AttributeLength);
+
+ AttributeAddress->Type = AttributeBitmap;
+ AttributeAddress->Length = AttributeLength;
+ AttributeAddress->NameLength = NameLength;
+ AttributeAddress->NameOffset = NameOffset;
+ AttributeAddress->Instance = FileRecord->NextAttributeNumber++;
+
+ AttributeAddress->Resident.ValueLength = ValueLength;
+ AttributeAddress->Resident.ValueOffset = ValueOffset;
+
+ // Set the name
+ RtlCopyMemory((PCHAR)((ULONG_PTR)AttributeAddress + NameOffset), Name, NameLength *
sizeof(WCHAR));
+
+ // move the attribute-end and file-record-end markers to the end of the file record
+ AttributeAddress = (PNTFS_ATTR_RECORD)((ULONG_PTR)AttributeAddress +
AttributeAddress->Length);
+ SetFileRecordEnd(FileRecord, AttributeAddress, FileRecordEnd);
+
+ return STATUS_SUCCESS;
+}
+
/**
* @name AddData
* @implemented
@@ -258,6 +352,105 @@ AddFileName(PFILE_RECORD_HEADER FileRecord,
return Status;
}
+/**
+* @name AddIndexAllocation
+* @implemented
+*
+* Adds an $INDEX_ALLOCATION attribute to a given FileRecord.
+*
+* @param Vcb
+* Pointer to an NTFS_VCB for the destination volume.
+*
+* @param FileRecord
+* Pointer to a complete file record to add the attribute to.
+*
+* @param AttributeAddress
+* Pointer to the region of memory that will receive the $INDEX_ALLOCATION attribute.
+* This address must reside within FileRecord. Must be aligned to an 8-byte boundary
(relative to FileRecord).
+*
+* @param Name
+* Pointer to a string of 16-bit Unicode characters naming the attribute. Most often, this
will be L"$I30".
+*
+* @param NameLength
+* The number of wide-characters in the name. L"$I30" Would use 4 here.
+*
+* @return
+* STATUS_SUCCESS on success. STATUS_NOT_IMPLEMENTED if target address isn't at the
end
+* of the given file record, or if the file record isn't large enough for the
attribute.
+*
+* @remarks
+* Only adding the attribute to the end of the file record is supported; AttributeAddress
must
+* be of type AttributeEnd.
+* This could be improved by adding an $ATTRIBUTE_LIST to the file record if there's
not enough space.
+*
+*/
+NTSTATUS
+AddIndexAllocation(PNTFS_VCB Vcb,
+ PFILE_RECORD_HEADER FileRecord,
+ PNTFS_ATTR_RECORD AttributeAddress,
+ PCWSTR Name,
+ USHORT NameLength)
+{
+ ULONG RecordLength;
+ ULONG FileRecordEnd;
+ ULONG NameOffset;
+ ULONG DataRunOffset;
+ ULONG BytesAvailable;
+
+ if (AttributeAddress->Type != AttributeEnd)
+ {
+ DPRINT1("FIXME: Can only add $INDEX_ALLOCATION attribute to the end of a
file record.\n");
+ return STATUS_NOT_IMPLEMENTED;
+ }
+
+ // Calculate the name offset
+ NameOffset = FIELD_OFFSET(NTFS_ATTR_RECORD, NonResident.CompressedSize);
+
+ // Calculate the offset to the first data run
+ DataRunOffset = (sizeof(WCHAR) * NameLength) + NameOffset;
+ // The data run offset must be aligned to a 4-byte boundary
+ DataRunOffset = ALIGN_UP_BY(DataRunOffset, DATA_RUN_ALIGNMENT);
+
+ // Calculate the length of the new attribute; the empty data run will consist of a
single byte
+ RecordLength = DataRunOffset + 1;
+
+ // The size of the attribute itself must be aligned to an 8 - byte boundary
+ RecordLength = ALIGN_UP_BY(RecordLength, ATTR_RECORD_ALIGNMENT);
+
+ // Back up the last 4-bytes of the file record (even though this value doesn't
matter)
+ FileRecordEnd = AttributeAddress->Length;
+
+ // Make sure the file record can contain the new attribute
+ BytesAvailable = Vcb->NtfsInfo.BytesPerFileRecord - FileRecord->BytesInUse;
+ if (BytesAvailable < RecordLength)
+ {
+ DPRINT1("FIXME: Not enough room in file record for index allocation
attribute!\n");
+ return STATUS_NOT_IMPLEMENTED;
+ }
+
+ // Set fields of attribute header
+ RtlZeroMemory(AttributeAddress, RecordLength);
+
+ AttributeAddress->Type = AttributeIndexAllocation;
+ AttributeAddress->Length = RecordLength;
+ AttributeAddress->IsNonResident = TRUE;
+ AttributeAddress->NameLength = NameLength;
+ AttributeAddress->NameOffset = NameOffset;
+ AttributeAddress->Instance = FileRecord->NextAttributeNumber++;
+
+ AttributeAddress->NonResident.MappingPairsOffset = DataRunOffset;
+ AttributeAddress->NonResident.HighestVCN = (LONGLONG)-1;
+
+ // Set the name
+ RtlCopyMemory((PCHAR)((ULONG_PTR)AttributeAddress + NameOffset), Name, NameLength *
sizeof(WCHAR));
+
+ // move the attribute-end and file-record-end markers to the end of the file record
+ AttributeAddress = (PNTFS_ATTR_RECORD)((ULONG_PTR)AttributeAddress +
AttributeAddress->Length);
+ SetFileRecordEnd(FileRecord, AttributeAddress, FileRecordEnd);
+
+ return STATUS_SUCCESS;
+}
+
/**
* @name AddIndexRoot
* @implemented
diff --git a/drivers/filesystems/ntfs/btree.c b/drivers/filesystems/ntfs/btree.c
index cd9cf35069..bb745c5e9e 100644
--- a/drivers/filesystems/ntfs/btree.c
+++ b/drivers/filesystems/ntfs/btree.c
@@ -468,6 +468,33 @@ CompareTreeKeys(PB_TREE_KEY Key1, PB_TREE_KEY Key2, BOOLEAN
CaseSensitive)
return Comparison;
}
+/**
+* @name CountBTreeKeys
+* @implemented
+*
+* Counts the number of linked B-Tree keys, starting with FirstKey.
+*
+* @param FirstKey
+* Pointer to a B_TREE_KEY that will be the first key to be counted.
+*
+* @return
+* The number of keys in a linked-list, including FirstKey and the final dummy key.
+*/
+ULONG
+CountBTreeKeys(PB_TREE_KEY FirstKey)
+{
+ ULONG Count = 0;
+ PB_TREE_KEY Current = FirstKey;
+
+ while (Current != NULL)
+ {
+ Count++;
+ Current = Current->NextKey;
+ }
+
+ return Count;
+}
+
PB_TREE_FILENAME_NODE
CreateBTreeNodeFromIndexNode(PDEVICE_EXTENSION Vcb,
PINDEX_ROOT_ATTRIBUTE IndexRoot,
@@ -852,6 +879,9 @@ GetSizeOfIndexEntries(PB_TREE_FILENAME_NODE Node)
*
* @param MaxIndexSize
* Describes how large the index can be before it will take too much space in the file
record.
+* This is strictly the sum of the sizes of all index entries; it does not include the
space
+* required by the index root header (INDEX_ROOT_ATTRIBUTE), since that size will be
constant.
+*
* 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).
*
@@ -885,6 +915,10 @@ CreateIndexRootFromBTree(PDEVICE_EXTENSION DeviceExt,
DPRINT1("CreateIndexRootFromBTree(%p, %p, 0x%lx, %p, %p)\n", DeviceExt,
Tree, MaxIndexSize, IndexRoot, Length);
+#ifndef NDEBUG
+ DumpBTree(Tree);
+#endif
+
if (!NewIndexRoot)
{
DPRINT1("Failed to allocate memory for Index Root!\n");
@@ -918,12 +952,10 @@ CreateIndexRootFromBTree(PDEVICE_EXTENSION DeviceExt,
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)
- + NewIndexRoot->Header.TotalSizeOfEntries
- + CurrentNodeEntry->Length;
+ ULONG IndexSize = NewIndexRoot->Header.TotalSizeOfEntries -
NewIndexRoot->Header.FirstEntryOffset + CurrentKey->IndexEntry->Length;
if (IndexSize > MaxIndexSize)
{
- DPRINT1("TODO: Adding file would require creating an index
allocation!\n");
+ DPRINT1("TODO: Adding file would require creating an attribute
list!\n");
ExFreePoolWithTag(NewIndexRoot, TAG_NTFS);
return STATUS_NOT_IMPLEMENTED;
}
@@ -962,6 +994,7 @@ NTSTATUS
CreateIndexBufferFromBTreeNode(PDEVICE_EXTENSION DeviceExt,
PB_TREE_FILENAME_NODE Node,
ULONG BufferSize,
+ BOOLEAN HasChildren,
PINDEX_BUFFER IndexBuffer)
{
ULONG i;
@@ -1014,7 +1047,9 @@ CreateIndexBufferFromBTreeNode(PDEVICE_EXTENSION DeviceExt,
// Add Length of Current Entry to Total Size of Entries
IndexBuffer->Header.TotalSizeOfEntries += CurrentNodeEntry->Length;
- // TODO: Check for child nodes
+ // Check for child nodes
+ if (HasChildren)
+ IndexBuffer->Header.Flags = INDEX_NODE_LARGE;
// Go to the next node entry
CurrentNodeEntry = (PINDEX_ENTRY_ATTRIBUTE)((ULONG_PTR)CurrentNodeEntry +
CurrentNodeEntry->Length);
@@ -1026,6 +1061,89 @@ CreateIndexBufferFromBTreeNode(PDEVICE_EXTENSION DeviceExt,
return Status;
}
+/**
+* @name DemoteBTreeRoot
+* @implemented
+*
+* Demoting the root means first putting all the keys in the root node into a new node,
and making
+* the new node a child of a dummy key. The dummy key then becomes the sole contents of
the root node.
+* The B-Tree gets one level deeper. This operation is needed when an index root grows too
large for its file record.
+* Demotion is my own term; I might change the name later if I think of something more
descriptive or can find
+* an appropriate name for this operation in existing B-Tree literature.
+*
+* @param Tree
+* Pointer to the B_TREE whose root is being demoted
+*
+* @returns
+* STATUS_SUCCESS on success.
+* STATUS_INSUFFICIENT_RESOURCES if an allocation fails.
+*/
+NTSTATUS
+DemoteBTreeRoot(PB_TREE Tree)
+{
+ PB_TREE_FILENAME_NODE NewSubNode, NewIndexRoot;
+ PB_TREE_KEY DummyKey;
+
+ DPRINT1("Collapsing Index Root into sub-node.\n");
+
+#ifndef NDEBUG
+ DumpBTree(Tree);
+#endif
+
+ // Create a new node that will hold the keys currently in index root
+ NewSubNode = ExAllocatePoolWithTag(NonPagedPool, sizeof(B_TREE_FILENAME_NODE),
TAG_NTFS);
+ if (!NewSubNode)
+ {
+ DPRINT1("ERROR: Couldn't allocate memory for new sub-node.\n");
+ return STATUS_INSUFFICIENT_RESOURCES;
+ }
+ RtlZeroMemory(NewSubNode, sizeof(B_TREE_FILENAME_NODE));
+
+ // Copy the applicable data from the old index root node
+ NewSubNode->KeyCount = Tree->RootNode->KeyCount;
+ NewSubNode->FirstKey = Tree->RootNode->FirstKey;
+ NewSubNode->DiskNeedsUpdating = TRUE;
+
+ // Create a new dummy key, and make the new node it's child
+ DummyKey = CreateDummyKey(TRUE);
+ if (!DummyKey)
+ {
+ DPRINT1("ERROR: Couldn't allocate memory for new root node.\n");
+ ExFreePoolWithTag(NewSubNode, TAG_NTFS);
+ return STATUS_INSUFFICIENT_RESOURCES;
+ }
+
+ // Make the new node a child of the dummy key
+ DummyKey->LesserChild = NewSubNode;
+
+ // Create a new index root node
+ NewIndexRoot = ExAllocatePoolWithTag(NonPagedPool, sizeof(B_TREE_FILENAME_NODE),
TAG_NTFS);
+ if (!NewIndexRoot)
+ {
+ DPRINT1("ERROR: Couldn't allocate memory for new index root.\n");
+ ExFreePoolWithTag(NewSubNode, TAG_NTFS);
+ ExFreePoolWithTag(DummyKey, TAG_NTFS);
+ return STATUS_INSUFFICIENT_RESOURCES;
+ }
+ RtlZeroMemory(NewIndexRoot, sizeof(B_TREE_FILENAME_NODE));
+
+ NewIndexRoot->DiskNeedsUpdating = TRUE;
+
+ // Insert the dummy key into the new node
+ NewIndexRoot->FirstKey = DummyKey;
+ NewIndexRoot->KeyCount = 1;
+ NewIndexRoot->DiskNeedsUpdating = TRUE;
+
+ // Make the new node the Tree's root node
+ Tree->RootNode = NewIndexRoot;
+
+#ifndef NDEBUG
+ DumpBTree(Tree);
+#endif;
+
+ return STATUS_SUCCESS;
+}
+
/**
* @name SetIndexEntryVCN
* @implemented
@@ -1060,7 +1178,7 @@ UpdateIndexAllocation(PDEVICE_EXTENSION DeviceExt,
PFILE_RECORD_HEADER FileRecord)
{
// Find the index allocation and bitmap
- PNTFS_ATTR_CONTEXT IndexAllocationContext, BitmapContext;
+ PNTFS_ATTR_CONTEXT IndexAllocationContext;
PB_TREE_KEY CurrentKey;
NTSTATUS Status;
BOOLEAN HasIndexAllocation = FALSE;
@@ -1074,14 +1192,12 @@ UpdateIndexAllocation(PDEVICE_EXTENSION DeviceExt,
{
HasIndexAllocation = TRUE;
+#ifndef NDEBUG
PrintAllVCNs(DeviceExt,
IndexAllocationContext,
IndexBufferSize);
+#endif
}
-
- // TODO: Handle bitmap
- BitmapContext = NULL;
-
// Walk through the root node and update all the sub-nodes
CurrentKey = Tree->RootNode->FirstKey;
for (i = 0; i < Tree->RootNode->KeyCount; i++)
@@ -1090,8 +1206,46 @@ UpdateIndexAllocation(PDEVICE_EXTENSION DeviceExt,
{
if (!HasIndexAllocation)
{
- DPRINT1("FIXME: Need to add index allocation\n");
- return STATUS_NOT_IMPLEMENTED;
+ // We need to add an index allocation to the file record
+ PNTFS_ATTR_RECORD EndMarker = (PNTFS_ATTR_RECORD)((ULONG_PTR)FileRecord +
FileRecord->BytesInUse - (sizeof(ULONG) * 2));
+ DPRINT1("Adding index allocation...\n");
+
+ // Add index allocation to the very end of the file record
+ Status = AddIndexAllocation(DeviceExt,
+ FileRecord,
+ EndMarker,
+ L"$I30",
+ 4);
+ if (!NT_SUCCESS(Status))
+ {
+ DPRINT1("ERROR: Failed to add index allocation!\n");
+ return Status;
+ }
+
+ // Find the new attribute
+ Status = FindAttribute(DeviceExt, FileRecord, AttributeIndexAllocation,
L"$I30", 4, &IndexAllocationContext, &IndexAllocationOffset);
+ if (!NT_SUCCESS(Status))
+ {
+ DPRINT1("ERROR: Couldn't find newly-created index
allocation!\n");
+ return Status;
+ }
+
+ // Advance end marker
+ EndMarker = (PNTFS_ATTR_RECORD)((ULONG_PTR)EndMarker +
EndMarker->Length);
+
+ // Add index bitmap to the very end of the file record
+ Status = AddBitmap(DeviceExt,
+ FileRecord,
+ EndMarker,
+ L"$I30",
+ 4);
+ if (!NT_SUCCESS(Status))
+ {
+ DPRINT1("ERROR: Failed to add index bitmap!\n");
+ return Status;
+ }
+
+ HasIndexAllocation = TRUE;
}
// Is the Index Entry large enough to store the VCN?
@@ -1122,7 +1276,7 @@ UpdateIndexAllocation(PDEVICE_EXTENSION DeviceExt,
}
// Update the sub-node
- Status = UpdateIndexNode(DeviceExt, FileRecord, CurrentKey->LesserChild,
IndexBufferSize, IndexAllocationContext, IndexAllocationOffset, BitmapContext);
+ Status = UpdateIndexNode(DeviceExt, FileRecord, CurrentKey->LesserChild,
IndexBufferSize, IndexAllocationContext, IndexAllocationOffset);
if (!NT_SUCCESS(Status))
{
DPRINT1("ERROR: Failed to update index node!\n");
@@ -1136,12 +1290,17 @@ UpdateIndexAllocation(PDEVICE_EXTENSION DeviceExt,
CurrentKey = CurrentKey->NextKey;
}
+#ifndef NDEBUG
+ DumpBTree(Tree);
+#endif
+
if (HasIndexAllocation)
{
+#ifndef NDEBUG
PrintAllVCNs(DeviceExt,
IndexAllocationContext,
IndexBufferSize);
-
+#endif
ReleaseAttributeContext(IndexAllocationContext);
}
@@ -1154,22 +1313,74 @@ UpdateIndexNode(PDEVICE_EXTENSION DeviceExt,
PB_TREE_FILENAME_NODE Node,
ULONG IndexBufferSize,
PNTFS_ATTR_CONTEXT IndexAllocationContext,
- ULONG IndexAllocationOffset,
- PNTFS_ATTR_CONTEXT BitmapContext)
+ ULONG IndexAllocationOffset)
{
ULONG i;
PB_TREE_KEY CurrentKey = Node->FirstKey;
+ BOOLEAN HasChildren = FALSE;
NTSTATUS Status;
- DPRINT1("UpdateIndexNode(%p, %p, %p, %lu, %p, %lu, %p) called for index node
with VCN %I64u\n",
- DeviceExt,
- FileRecord,
- Node,
- IndexBufferSize,
- IndexAllocationContext,
- IndexAllocationOffset,
- BitmapContext,
- Node->VCN);
+
+ DPRINT("UpdateIndexNode(%p, %p, %p, %lu, %p, %lu) called for index node with VCN
%I64u\n",
+ DeviceExt,
+ FileRecord,
+ Node,
+ IndexBufferSize,
+ IndexAllocationContext,
+ IndexAllocationOffset,
+ Node->VCN);
+
+ // Walk through the node and look for children to update
+ for (i = 0; i < Node->KeyCount; i++)
+ {
+ ASSERT(CurrentKey);
+
+ // If there's a child node
+ if (CurrentKey->LesserChild)
+ {
+ HasChildren = TRUE;
+
+ // Update the child node on disk
+ Status = UpdateIndexNode(DeviceExt, FileRecord, CurrentKey->LesserChild,
IndexBufferSize, IndexAllocationContext, IndexAllocationOffset);
+ if (!NT_SUCCESS(Status))
+ {
+ DPRINT1("ERROR: Failed to update child node!\n");
+ return Status;
+ }
+
+ // Is the Index Entry large enough to store the VCN?
+ if (!CurrentKey->IndexEntry->Flags & NTFS_INDEX_ENTRY_NODE)
+ {
+ // Allocate memory for the larger index entry
+ PINDEX_ENTRY_ATTRIBUTE NewEntry = ExAllocatePoolWithTag(NonPagedPool,
+
CurrentKey->IndexEntry->Length + sizeof(ULONGLONG),
+ TAG_NTFS);
+ if (!NewEntry)
+ {
+ DPRINT1("ERROR: Unable to allocate memory for new index
entry!\n");
+ return STATUS_INSUFFICIENT_RESOURCES;
+ }
+
+ // Copy the old entry to the new one
+ RtlCopyMemory(NewEntry, CurrentKey->IndexEntry,
CurrentKey->IndexEntry->Length);
+
+ NewEntry->Length += sizeof(ULONGLONG);
+
+ // Free the old memory
+ ExFreePoolWithTag(CurrentKey->IndexEntry, TAG_NTFS);
+
+ CurrentKey->IndexEntry = NewEntry;
+ }
+
+ // Update the VCN stored in the index entry of CurrentKey
+ SetIndexEntryVCN(CurrentKey->IndexEntry,
CurrentKey->LesserChild->VCN);
+
+ CurrentKey->IndexEntry->Flags |= NTFS_INDEX_ENTRY_NODE;
+ }
+
+ CurrentKey = CurrentKey->NextKey;
+ }
+
// Do we need to write this node to disk?
if (Node->DiskNeedsUpdating)
@@ -1206,7 +1417,7 @@ UpdateIndexNode(PDEVICE_EXTENSION DeviceExt,
}
// Create the index buffer we'll be writing to disk to represent this node
- Status = CreateIndexBufferFromBTreeNode(DeviceExt, Node, IndexBufferSize,
IndexBuffer);
+ Status = CreateIndexBufferFromBTreeNode(DeviceExt, Node, IndexBufferSize,
HasChildren, IndexBuffer);
if (!NT_SUCCESS(Status))
{
DPRINT1("ERROR: Failed to create index buffer from node!\n");
@@ -1235,26 +1446,6 @@ UpdateIndexNode(PDEVICE_EXTENSION DeviceExt,
ExFreePoolWithTag(IndexBuffer, TAG_NTFS);
}
- // Walk through the node and look for children to update
- for (i = 0; i < Node->KeyCount; i++)
- {
- ASSERT(CurrentKey);
-
- // If there's a child node
- if (CurrentKey->LesserChild)
- {
- // Update the child node on disk
- Status = UpdateIndexNode(DeviceExt, FileRecord, CurrentKey->LesserChild,
IndexBufferSize, IndexAllocationContext, IndexAllocationOffset, BitmapContext);
- if (!NT_SUCCESS(Status))
- {
- DPRINT1("ERROR: Failed to update child node!\n");
- return Status;
- }
- }
-
- CurrentKey = CurrentKey->NextKey;
- }
-
return STATUS_SUCCESS;
}
@@ -1438,6 +1629,16 @@ GetAllocationOffsetFromVCN(PDEVICE_EXTENSION DeviceExt,
return Vcn * DeviceExt->NtfsInfo.BytesPerCluster;
}
+ULONGLONG
+GetIndexEntryVCN(PINDEX_ENTRY_ATTRIBUTE IndexEntry)
+{
+ PULONGLONG Destination = (PULONGLONG)((ULONG_PTR)IndexEntry + IndexEntry->Length -
sizeof(ULONGLONG));
+
+ ASSERT(IndexEntry->Flags & NTFS_INDEX_ENTRY_NODE);
+
+ return *Destination;
+}
+
/**
* @name NtfsInsertKey
* @implemented
@@ -1464,6 +1665,17 @@ GetAllocationOffsetFromVCN(PDEVICE_EXTENSION DeviceExt,
* The maximum size, in bytes, of node entries that can be stored in the index root before
it will grow too large for
* the file record. This number is just the size of the entries, without any headers for
the attribute or index root.
*
+* @param IndexRecordSize
+* The size, in bytes, of an index record for this index. AKA an index buffer. Usually set
to 4096.
+*
+* @param MedianKey
+* Pointer to a PB_TREE_KEY that will receive a pointer to the median key, should the node
grow too large and need to be split.
+* Will be set to NULL if the node isn't split.
+*
+* @param NewRightHandSibling
+* Pointer to a PB_TREE_FILENAME_NODE that will receive a pointer to a newly-created
right-hand sibling node,
+* should the node grow too large and need to be split. Will be set to NULL if the node
isn't split.
+*
* @remarks
* A node is always sorted, with the least comparable filename stored first and a dummy
key to mark the end.
*/
@@ -1473,7 +1685,10 @@ NtfsInsertKey(PB_TREE Tree,
PFILENAME_ATTRIBUTE FileNameAttribute,
PB_TREE_FILENAME_NODE Node,
BOOLEAN CaseSensitive,
- ULONG MaxIndexRootSize)
+ ULONG MaxIndexRootSize,
+ ULONG IndexRecordSize,
+ PB_TREE_KEY *MedianKey,
+ PB_TREE_FILENAME_NODE *NewRightHandSibling)
{
PB_TREE_KEY NewKey, CurrentKey, PreviousKey;
NTSTATUS Status = STATUS_SUCCESS;
@@ -1482,13 +1697,19 @@ NtfsInsertKey(PB_TREE Tree,
ULONG MaxNodeSizeWithoutHeader;
ULONG i;
- DPRINT1("NtfsInsertKey(%p, 0x%I64x, %p, %p, %s, %lu)\n",
+ *MedianKey = NULL;
+ *NewRightHandSibling = NULL;
+
+ DPRINT1("NtfsInsertKey(%p, 0x%I64x, %p, %p, %s, %lu, %lu, %p, %p)\n",
Tree,
FileReference,
FileNameAttribute,
Node,
CaseSensitive ? "TRUE" : "FALSE",
- MaxIndexRootSize);
+ MaxIndexRootSize,
+ IndexRecordSize,
+ MedianKey,
+ NewRightHandSibling);
// Create the key for the filename attribute
NewKey = CreateBTreeKeyFromFilename(FileReference, FileNameAttribute);
@@ -1513,12 +1734,22 @@ NtfsInsertKey(PB_TREE Tree,
// Is NewKey < CurrentKey?
if (Comparison < 0)
{
-
// Does CurrentKey have a sub-node?
if (CurrentKey->LesserChild)
{
+ PB_TREE_KEY NewLeftKey;
+ PB_TREE_FILENAME_NODE NewChild;
+
// Insert the key into the child node
- Status = NtfsInsertKey(Tree, FileReference, FileNameAttribute,
CurrentKey->LesserChild, CaseSensitive, 0);
+ Status = NtfsInsertKey(Tree,
+ FileReference,
+ FileNameAttribute,
+ CurrentKey->LesserChild,
+ CaseSensitive,
+ MaxIndexRootSize,
+ IndexRecordSize,
+ &NewLeftKey,
+ &NewChild);
if (!NT_SUCCESS(Status))
{
DPRINT1("ERROR: Failed to insert key.\n");
@@ -1526,6 +1757,30 @@ NtfsInsertKey(PB_TREE Tree,
return Status;
}
+ // Did the child node get split?
+ if (NewLeftKey)
+ {
+ ASSERT(NewChild != NULL);
+
+ // Insert the new left key to the left of the current key
+ NewLeftKey->NextKey = CurrentKey;
+
+ // Is CurrentKey the first key?
+ if (!PreviousKey)
+ Node->FirstKey = NewLeftKey;
+ else
+ PreviousKey->NextKey = NewLeftKey;
+
+ // CurrentKey->LesserChild will be the right-hand sibling
+ CurrentKey->LesserChild = NewChild;
+
+ Node->KeyCount++;
+ Node->DiskNeedsUpdating = TRUE;
+
+#ifndef NDEBUG
+ DumpBTree(Tree);
+#endif NDEBUG
+ }
}
else
{
@@ -1541,8 +1796,8 @@ NtfsInsertKey(PB_TREE Tree,
Node->FirstKey = NewKey;
else
PreviousKey->NextKey = NewKey;
- break;
}
+ break;
}
PreviousKey = CurrentKey;
@@ -1552,88 +1807,202 @@ NtfsInsertKey(PB_TREE Tree,
// Determine how much space the index entries will need
NodeSize = GetSizeOfIndexEntries(Node);
- // Is Node the root node?
- if (Node == Tree->RootNode)
+ // Is Node not the root node?
+ if (Node != Tree->RootNode)
{
- // Is the index root too large for the file record?
- if (NodeSize > MaxIndexRootSize)
- {
- PB_TREE_FILENAME_NODE NewSubNode, NewIndexRoot;
- PB_TREE_KEY DummyKey;
+ // Calculate maximum size of index entries without any headers
+ AllocatedNodeSize = IndexRecordSize - FIELD_OFFSET(INDEX_BUFFER, Header);
- DPRINT1("Collapsing Index Root into sub-node.\n") ;
+ // TODO: Replace magic with math
+ MaxNodeSizeWithoutHeader = AllocatedNodeSize - 0x28;
+
+ // Has the node grown larger than its allocated size?
+ if (NodeSize > MaxNodeSizeWithoutHeader)
+ {
+ NTSTATUS Status;
- DumpBTree(Tree);
-
- // Create a new node that will hold the keys currently in index root
- NewSubNode = ExAllocatePoolWithTag(NonPagedPool,
sizeof(B_TREE_FILENAME_NODE), TAG_NTFS);
- if (!NewSubNode)
+ Status = SplitBTreeNode(Tree, Node, MedianKey, NewRightHandSibling,
CaseSensitive);
+ if (!NT_SUCCESS(Status))
{
- DPRINT1("ERROR: Couldn't allocate memory for new
sub-node.\n");
- return STATUS_INSUFFICIENT_RESOURCES;
+ DPRINT1("ERROR: Failed to split B-Tree node!\n");
+ return Status;
}
- RtlZeroMemory(NewSubNode, sizeof(B_TREE_FILENAME_NODE));
- // Copy the applicable data from the old index root node
- NewSubNode->KeyCount = Node->KeyCount;
- NewSubNode->FirstKey = Node->FirstKey;
- NewSubNode->DiskNeedsUpdating = TRUE;
+ return Status;
+ }
+ }
- // Create a new dummy key, and make the new node it's child
- DummyKey = CreateDummyKey(TRUE);
- if (!DummyKey)
- {
- DPRINT1("ERROR: Couldn't allocate memory for new root
node.\n");
- ExFreePoolWithTag(NewSubNode, TAG_NTFS);
- return STATUS_INSUFFICIENT_RESOURCES;
- }
+ // NewEntry and NewKey will be destroyed later by DestroyBTree()
- // Make the new node a child of the dummy key
- DummyKey->LesserChild = NewSubNode;
+ return Status;
+}
- // Create a new index root node
- NewIndexRoot = ExAllocatePoolWithTag(NonPagedPool,
sizeof(B_TREE_FILENAME_NODE), TAG_NTFS);
- if (!NewIndexRoot)
- {
- DPRINT1("ERROR: Couldn't allocate memory for new index
root.\n");
- ExFreePoolWithTag(NewSubNode, TAG_NTFS);
- ExFreePoolWithTag(DummyKey, TAG_NTFS);
- return STATUS_INSUFFICIENT_RESOURCES;
- }
- RtlZeroMemory(NewIndexRoot, sizeof(B_TREE_FILENAME_NODE));
- NewIndexRoot->DiskNeedsUpdating = TRUE;
- // Insert the dummy key into the new node
- NewIndexRoot->FirstKey = DummyKey;
- NewIndexRoot->KeyCount = 1;
- NewIndexRoot->DiskNeedsUpdating = TRUE;
+/**
+* @name SplitBTreeNode
+* @implemented
+*
+* Splits a B-Tree node that has grown too large. Finds the median key and sets up a
right-hand-sibling
+* node to contain the keys to the right of the median key.
+*
+* @param Tree
+* Pointer to the B_TREE which contains the node being split
+*
+* @param Node
+* Pointer to the B_TREE_FILENAME_NODE that needs to be split
+*
+* @param MedianKey
+* Pointer a PB_TREE_KEY that will receive the pointer to the key in the middle of the
node being split
+*
+* @param NewRightHandSibling
+* Pointer to a PB_TREE_FILENAME_NODE that will receive a pointer to a newly-created
B_TREE_FILENAME_NODE
+* containing the keys to the right of MedianKey.
+*
+* @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.
+*
+* @remarks
+* It's the responsibility of the caller to insert the new median key into the parent
node, as well as making the
+* NewRightHandSibling the lesser child of the node that is currently Node's parent.
+*/
+NTSTATUS
+SplitBTreeNode(PB_TREE Tree,
+ PB_TREE_FILENAME_NODE Node,
+ PB_TREE_KEY *MedianKey,
+ PB_TREE_FILENAME_NODE *NewRightHandSibling,
+ BOOLEAN CaseSensitive)
+{
+ ULONG MedianKeyIndex;
+ PB_TREE_KEY LastKeyBeforeMedian, FirstKeyAfterMedian;
+ ULONG i;
- // Make the new node the Tree's root node
- Tree->RootNode = NewIndexRoot;
+ DPRINT1("SplitBTreeNode(%p, %p, %p, %p, %s) called\n",
+ Tree,
+ Node,
+ MedianKey,
+ NewRightHandSibling,
+ CaseSensitive ? "TRUE" : "FALSE");
- DumpBTree(Tree);
+ //DumpBTreeNode(Node, 0, 0);
- return STATUS_SUCCESS;
- }
+ // Create the right hand sibling
+ *NewRightHandSibling = ExAllocatePoolWithTag(NonPagedPool,
sizeof(B_TREE_FILENAME_NODE), TAG_NTFS);
+ if (*NewRightHandSibling == NULL)
+ {
+ DPRINT1("Error: Failed to allocate memory for right hand sibling!\n");
+ return STATUS_INSUFFICIENT_RESOURCES;
+ }
+ RtlZeroMemory(*NewRightHandSibling, sizeof(B_TREE_FILENAME_NODE));
+ (*NewRightHandSibling)->DiskNeedsUpdating = TRUE;
+
+ // find the median key index
+ MedianKeyIndex = (Node->KeyCount + 1) / 2;
+ MedianKeyIndex--;
+
+ // Find the last key before the median
+ LastKeyBeforeMedian = Node->FirstKey;
+ for (i = 0; i < MedianKeyIndex - 1; i++)
+ LastKeyBeforeMedian = LastKeyBeforeMedian->NextKey;
+
+ // Use size to locate the median key / index
+ ULONG HalfSize = 2016; // half the allocated size after subtracting the first index
entry offset (TODO: MATH)
+ ULONG SizeSum = 0;
+ LastKeyBeforeMedian = Node->FirstKey;
+ MedianKeyIndex = 0;
+ for (i = 0; i < Node->KeyCount; i++)
+ {
+ SizeSum += LastKeyBeforeMedian->IndexEntry->Length;
+
+ if (SizeSum > HalfSize)
+ break;
+
+ MedianKeyIndex++;
+ LastKeyBeforeMedian = LastKeyBeforeMedian->NextKey;
+ }
+
+ // Now we can get the median key and the key that follows it
+ *MedianKey = LastKeyBeforeMedian->NextKey;
+ FirstKeyAfterMedian = (*MedianKey)->NextKey;
+
+ DPRINT1("%lu keys, %lu median\n", Node->KeyCount, MedianKeyIndex);
+ DPRINT1("\t\tMedian: %.*S\n",
(*MedianKey)->IndexEntry->FileName.NameLength,
(*MedianKey)->IndexEntry->FileName.Name);
+
+ // "Node" will be the left hand sibling after the split, containing all
keys prior to the median key
+
+ // We need to create a dummy pointer at the end of the LHS. The dummy's child
will be the median's child.
+ LastKeyBeforeMedian->NextKey =
CreateDummyKey(BooleanFlagOn((*MedianKey)->IndexEntry->Flags,
NTFS_INDEX_ENTRY_NODE));
+ if (LastKeyBeforeMedian->NextKey == NULL)
+ {
+ DPRINT1("Error: Couldn't allocate dummy key!\n");
+ LastKeyBeforeMedian->NextKey = *MedianKey;
+ ExFreePoolWithTag(*NewRightHandSibling, TAG_NTFS);
+ return STATUS_INSUFFICIENT_RESOURCES;
+ }
+
+ // Did the median key have a child node?
+ if ((*MedianKey)->IndexEntry->Flags & NTFS_INDEX_ENTRY_NODE)
+ {
+ // Set the child of the new dummy key
+ LastKeyBeforeMedian->NextKey->LesserChild = (*MedianKey)->LesserChild;
+
+ // Give the dummy key's index entry the same sub-node VCN the median
+ SetIndexEntryVCN(LastKeyBeforeMedian->NextKey->IndexEntry,
GetIndexEntryVCN((*MedianKey)->IndexEntry));
}
else
{
- // TEMPTEMP: TODO: MATH
- AllocatedNodeSize = 0xfe8;
- MaxNodeSizeWithoutHeader = AllocatedNodeSize - 0x28;
-
- // Has the node grown larger than its allocated size?
- if (NodeSize > MaxNodeSizeWithoutHeader)
+ // Median key didn't have a child node, but it will. Create a new index entry
large enough to store a VCN.
+ PINDEX_ENTRY_ATTRIBUTE NewIndexEntry = ExAllocatePoolWithTag(NonPagedPool,
+
(*MedianKey)->IndexEntry->Length + sizeof(ULONGLONG),
+ TAG_NTFS);
+ if (!NewIndexEntry)
{
- DPRINT1("FIXME: Splitting a node is still a WIP!\n");
- //SplitBTreeNode(NULL, Node);
- //DumpBTree(Tree);
- return STATUS_NOT_IMPLEMENTED;
+ DPRINT1("Unable to allocate memory for new index entry!\n");
+ LastKeyBeforeMedian->NextKey = *MedianKey;
+ ExFreePoolWithTag(*NewRightHandSibling, TAG_NTFS);
+ return STATUS_INSUFFICIENT_RESOURCES;
}
+
+ // Copy the old index entry to the new one
+ RtlCopyMemory(NewIndexEntry, (*MedianKey)->IndexEntry,
(*MedianKey)->IndexEntry->Length);
+
+ // Use the new index entry after freeing the old one
+ ExFreePoolWithTag((*MedianKey)->IndexEntry, TAG_NTFS);
+ (*MedianKey)->IndexEntry = NewIndexEntry;
+
+ // Update the length for the VCN
+ (*MedianKey)->IndexEntry->Length += sizeof(ULONGLONG);
+
+ // Set the node flag
+ (*MedianKey)->IndexEntry->Flags |= NTFS_INDEX_ENTRY_NODE;
}
- // NewEntry and NewKey will be destroyed later by DestroyBTree()
+ // "Node" will become the child of the median key
+ (*MedianKey)->LesserChild = Node;
+ SetIndexEntryVCN((*MedianKey)->IndexEntry, Node->VCN);
- return Status;
+ // Update Node's KeyCount (remember to add 1 for the new dummy key)
+ Node->KeyCount = MedianKeyIndex + 2;
+
+ ULONG KeyCount = CountBTreeKeys(Node->FirstKey);
+ ASSERT(Node->KeyCount == KeyCount);
+
+ // everything to the right of MedianKey becomes the right hand sibling of Node
+ (*NewRightHandSibling)->FirstKey = FirstKeyAfterMedian;
+ (*NewRightHandSibling)->KeyCount = CountBTreeKeys(FirstKeyAfterMedian);
+
+#ifndef NDEBUG
+ DPRINT1("Left-hand node after split:\n");
+ DumpBTreeNode(Node, 0, 0);
+
+ DPRINT1("Right-hand sibling node after split:\n");
+ DumpBTreeNode(*NewRightHandSibling, 0, 0);
+#endif
+
+ return STATUS_SUCCESS;
}
\ No newline at end of file
diff --git a/drivers/filesystems/ntfs/mft.c b/drivers/filesystems/ntfs/mft.c
index 547ab64a2b..c4328a0491 100644
--- a/drivers/filesystems/ntfs/mft.c
+++ b/drivers/filesystems/ntfs/mft.c
@@ -786,6 +786,11 @@ SetNonResidentAttributeDataLength(PDEVICE_EXTENSION Vcb,
DestinationAttribute->NonResident.AllocatedSize = AllocationSize;
DestinationAttribute->NonResident.DataSize = DataSize->QuadPart;
DestinationAttribute->NonResident.InitializedSize = DataSize->QuadPart;
+
+ // HighestVCN seems to be set incorrectly somewhere. Apply a hack-fix to reset it.
+ // HACKHACK FIXME: Fix for sparse files; this math won't work in that case.
+ AttrContext->pRecord->NonResident.HighestVCN = ((ULONGLONG)AllocationSize /
Vcb->NtfsInfo.BytesPerCluster) - 1;
+ DestinationAttribute->NonResident.HighestVCN =
AttrContext->pRecord->NonResident.HighestVCN;
DPRINT("Allocated Size: %I64u\n",
DestinationAttribute->NonResident.AllocatedSize);
@@ -2131,6 +2136,8 @@ NtfsAddFilenameToDirectory(PDEVICE_EXTENSION DeviceExt,
PB_TREE NewTree;
ULONG BtreeIndexLength;
ULONG MaxIndexRootSize;
+ PB_TREE_KEY NewLeftKey;
+ PB_TREE_FILENAME_NODE NewRightHandNode;
// Allocate memory for the parent directory
ParentFileRecord = ExAllocatePoolWithTag(NonPagedPool,
@@ -2152,8 +2159,10 @@ NtfsAddFilenameToDirectory(PDEVICE_EXTENSION DeviceExt,
return Status;
}
+#ifndef NDEBUG
DPRINT1("Dumping old parent file record:\n");
NtfsDumpFileRecord(DeviceExt, ParentFileRecord);
+#endif
// Find the index root attribute for the directory
Status = FindAttribute(DeviceExt,
@@ -2176,7 +2185,7 @@ NtfsAddFilenameToDirectory(PDEVICE_EXTENSION DeviceExt,
MaxIndexRootSize = DeviceExt->NtfsInfo.BytesPerFileRecord // Start
with the size of a file record
- IndexRootOffset // Subtract
the length of everything that comes before index root
- IndexRootContext->pRecord->Resident.ValueOffset //
Subtract the length of the attribute header for index root
- - FIELD_OFFSET(INDEX_ROOT_ATTRIBUTE, Header) // Subtract
the length of the index header for index root
+ - sizeof(INDEX_ROOT_ATTRIBUTE) // Subtract
the length of the index root header
- (sizeof(ULONG) * 2); // Subtract
the length of the file record end marker and padding
// Are there attributes after this one?
@@ -2233,10 +2242,20 @@ NtfsAddFilenameToDirectory(PDEVICE_EXTENSION DeviceExt,
return Status;
}
+#ifndef NDEBUG
DumpBTree(NewTree);
+#endif
// Insert the key for the file we're adding
- Status = NtfsInsertKey(NewTree, FileReferenceNumber, FilenameAttribute,
NewTree->RootNode, CaseSensitive, MaxIndexRootSize);
+ Status = NtfsInsertKey(NewTree,
+ FileReferenceNumber,
+ FilenameAttribute,
+ NewTree->RootNode,
+ CaseSensitive,
+ MaxIndexRootSize,
+ I30IndexRoot->SizeOfEntry,
+ &NewLeftKey,
+ &NewRightHandNode);
if (!NT_SUCCESS(Status))
{
DPRINT1("ERROR: Failed to insert key into B-Tree!\n");
@@ -2247,9 +2266,57 @@ NtfsAddFilenameToDirectory(PDEVICE_EXTENSION DeviceExt,
return Status;
}
+#ifndef NDEBUG
DumpBTree(NewTree);
+#endif
+
+ // The root node can't be split
+ ASSERT(NewLeftKey == NULL);
+ ASSERT(NewRightHandNode == NULL);
+
+ // Convert B*Tree back to Index
+
+ // Updating the index allocation can change the size available for the index root,
+ // And if the index root is demoted, the index allocation will need to be updated
again,
+ // which may change the size available for index root... etc.
+ // My solution is to decrease index root to the size it would be if it was demoted,
+ // then UpdateIndexAllocation will have an accurate representation of the maximum
space
+ // it can use in the file record. There's still a chance that the act of
allocating an
+ // index node after demoting the index root will increase the size of the file record
beyond
+ // it's limit, but if that happens, an attribute-list will most definitely be
needed.
+ // This a bit hacky, but it seems to be functional.
+
+ // Calculate the minimum size of the index root attribute, considering one dummy key
and one VCN
+ LARGE_INTEGER MinIndexRootSize;
+ MinIndexRootSize.QuadPart = sizeof(INDEX_ROOT_ATTRIBUTE) // size of the index root
headers
+ + 0x18; // Size of dummy key with a VCN for a subnode
+ ASSERT(MinIndexRootSize.QuadPart % ATTR_RECORD_ALIGNMENT == 0);
+
+ // Temporarily shrink the index root to it's minimal size
+ AttributeLength = MinIndexRootSize.LowPart;
+ AttributeLength += sizeof(INDEX_ROOT_ATTRIBUTE);
+
+
+ // FIXME: IndexRoot will probably be invalid until we're finished. If we fail
before we finish, the directory will probably be toast.
+ // The potential for catastrophic data-loss exists!!! :)
+
+ // Update the length of the attribute in the file record of the parent directory
+ Status = InternalSetResidentAttributeLength(DeviceExt,
+ IndexRootContext,
+ ParentFileRecord,
+ IndexRootOffset,
+ AttributeLength);
+ if (!NT_SUCCESS(Status))
+ {
+ DPRINT1("ERROR: Unable to set length of index root!\n");
+ DestroyBTree(NewTree);
+ ReleaseAttributeContext(IndexRootContext);
+ ExFreePoolWithTag(I30IndexRoot, TAG_NTFS);
+ ExFreePoolWithTag(ParentFileRecord, TAG_NTFS);
+ return Status;
+ }
- // Convert B*Tree back to Index, starting with the index allocation
+ // Update the index allocation
Status = UpdateIndexAllocation(DeviceExt, NewTree, I30IndexRoot->SizeOfEntry,
ParentFileRecord);
if (!NT_SUCCESS(Status))
{
@@ -2261,8 +2328,99 @@ NtfsAddFilenameToDirectory(PDEVICE_EXTENSION DeviceExt,
return Status;
}
+#ifndef NDEBUG
+ DPRINT1("Index Allocation updated\n");
+ DumpBTree(NewTree);
+#endif
+
+ // Find the maximum index root size given what the file record can hold
+ // First, find the max index size assuming index root is the last attribute
+ ULONG NewMaxIndexRootSize =
+ DeviceExt->NtfsInfo.BytesPerFileRecord // Start with the size of
a file record
+ - IndexRootOffset // Subtract the length of
everything that comes before index root
+ - IndexRootContext->pRecord->Resident.ValueOffset // Subtract the length
of the attribute header for index root
+ - sizeof(INDEX_ROOT_ATTRIBUTE) // Subtract the length of
the index root header
+ - (sizeof(ULONG) * 2); // Subtract the length of
the file record end marker and padding
+
+ // Are there attributes after this one?
+ NextAttribute = (PNTFS_ATTR_RECORD)((ULONG_PTR)ParentFileRecord + IndexRootOffset +
IndexRootContext->pRecord->Length);
+ if (NextAttribute->Type != AttributeEnd)
+ {
+ // Find the length of all attributes after this one, not counting the end marker
+ ULONG LengthOfAttributes = 0;
+ PNTFS_ATTR_RECORD CurrentAttribute = NextAttribute;
+ while (CurrentAttribute->Type != AttributeEnd)
+ {
+ LengthOfAttributes += CurrentAttribute->Length;
+ CurrentAttribute = (PNTFS_ATTR_RECORD)((ULONG_PTR)CurrentAttribute +
CurrentAttribute->Length);
+ }
+
+ // Leave room for the existing attributes
+ NewMaxIndexRootSize -= LengthOfAttributes;
+ }
+
+ // The index allocation and index bitmap may have grown, leaving less room for the
index root,
+ // so now we need to double-check that index root isn't too large
+ ULONG NodeSize = GetSizeOfIndexEntries(NewTree->RootNode);
+ if (NodeSize > NewMaxIndexRootSize)
+ {
+ DPRINT1("Demoting index root.\nNodeSize: 0x%lx\nNewMaxIndexRootSize:
0x%lx\n", NodeSize, NewMaxIndexRootSize);
+
+ Status = DemoteBTreeRoot(NewTree);
+ if (!NT_SUCCESS(Status))
+ {
+ DPRINT1("ERROR: Failed to demote index root!\n");
+ DestroyBTree(NewTree);
+ ReleaseAttributeContext(IndexRootContext);
+ ExFreePoolWithTag(I30IndexRoot, TAG_NTFS);
+ ExFreePoolWithTag(ParentFileRecord, TAG_NTFS);
+ return Status;
+ }
+
+ // We need to update the index allocation once more
+ Status = UpdateIndexAllocation(DeviceExt, NewTree, I30IndexRoot->SizeOfEntry,
ParentFileRecord);
+ if (!NT_SUCCESS(Status))
+ {
+ DPRINT1("ERROR: Failed to update index allocation from
B-Tree!\n");
+ DestroyBTree(NewTree);
+ ReleaseAttributeContext(IndexRootContext);
+ ExFreePoolWithTag(I30IndexRoot, TAG_NTFS);
+ ExFreePoolWithTag(ParentFileRecord, TAG_NTFS);
+ return Status;
+ }
+
+ // re-recalculate max size of index root
+ NewMaxIndexRootSize =
+ // Find the maximum index size given what the file record can hold
+ // First, find the max index size assuming index root is the last attribute
+ DeviceExt->NtfsInfo.BytesPerFileRecord // Start with the
size of a file record
+ - IndexRootOffset // Subtract the length
of everything that comes before index root
+ - IndexRootContext->pRecord->Resident.ValueOffset // Subtract the
length of the attribute header for index root
+ - sizeof(INDEX_ROOT_ATTRIBUTE) // Subtract the length
of the index root header
+ - (sizeof(ULONG) * 2); // Subtract the length
of the file record end marker and padding
+
+ // Are there attributes
after this one?
+ NextAttribute = (PNTFS_ATTR_RECORD)((ULONG_PTR)ParentFileRecord + IndexRootOffset
+ IndexRootContext->pRecord->Length);
+ if (NextAttribute->Type != AttributeEnd)
+ {
+ // Find the length of all attributes after this one, not counting the end
marker
+ ULONG LengthOfAttributes = 0;
+ PNTFS_ATTR_RECORD CurrentAttribute = NextAttribute;
+ while (CurrentAttribute->Type != AttributeEnd)
+ {
+ LengthOfAttributes += CurrentAttribute->Length;
+ CurrentAttribute = (PNTFS_ATTR_RECORD)((ULONG_PTR)CurrentAttribute +
CurrentAttribute->Length);
+ }
+
+ // Leave room for the existing attributes
+ NewMaxIndexRootSize -= LengthOfAttributes;
+ }
+
+
+ }
+
// Create the Index Root from the B*Tree
- Status = CreateIndexRootFromBTree(DeviceExt, NewTree, MaxIndexRootSize,
&NewIndexRoot, &BtreeIndexLength);
+ Status = CreateIndexRootFromBTree(DeviceExt, NewTree, NewMaxIndexRootSize,
&NewIndexRoot, &BtreeIndexLength);
if (!NT_SUCCESS(Status))
{
DPRINT1("ERROR: Failed to create Index root from B-Tree!\n");
@@ -2280,9 +2438,7 @@ NtfsAddFilenameToDirectory(PDEVICE_EXTENSION DeviceExt,
// 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.
+ // We can't set the size as we normally would, because $INDEX_ROOT must always be
resident.
AttributeLength = NewIndexRoot->Header.AllocatedSize +
FIELD_OFFSET(INDEX_ROOT_ATTRIBUTE, Header);
if (AttributeLength != IndexRootContext->pRecord->Resident.ValueLength)
@@ -2344,8 +2500,22 @@ NtfsAddFilenameToDirectory(PDEVICE_EXTENSION DeviceExt,
}
else
{
- DPRINT1("Dumping new parent file record:\n");
+#ifndef NDEBUG
+ DPRINT1("Dumping new B-Tree:\n");
+
+ Status = CreateBTreeFromIndex(DeviceExt, ParentFileRecord, IndexRootContext,
NewIndexRoot, &NewTree);
+ if (!NT_SUCCESS(Status))
+ {
+ DPRINT1("ERROR: Couldn't re-create b-tree\n");
+ return Status;
+ }
+
+ DumpBTree(NewTree);
+
+ DestroyBTree(NewTree);
+
NtfsDumpFileRecord(DeviceExt, ParentFileRecord);
+#endif
}
// Cleanup
diff --git a/drivers/filesystems/ntfs/ntfs.h b/drivers/filesystems/ntfs/ntfs.h
index aba8b29196..5c709c61e9 100644
--- a/drivers/filesystems/ntfs/ntfs.h
+++ b/drivers/filesystems/ntfs/ntfs.h
@@ -564,6 +564,13 @@ NtfsMarkIrpContextForQueue(PNTFS_IRP_CONTEXT IrpContext)
//VOID
//NtfsDumpAttribute(PATTRIBUTE Attribute);
+NTSTATUS
+AddBitmap(PNTFS_VCB Vcb,
+ PFILE_RECORD_HEADER FileRecord,
+ PNTFS_ATTR_RECORD AttributeAddress,
+ PCWSTR Name,
+ USHORT NameLength);
+
NTSTATUS
AddData(PFILE_RECORD_HEADER FileRecord,
PNTFS_ATTR_RECORD AttributeAddress);
@@ -576,6 +583,13 @@ AddRun(PNTFS_VCB Vcb,
ULONGLONG NextAssignedCluster,
ULONG RunLength);
+NTSTATUS
+AddIndexAllocation(PNTFS_VCB Vcb,
+ PFILE_RECORD_HEADER FileRecord,
+ PNTFS_ATTR_RECORD AttributeAddress,
+ PCWSTR Name,
+ USHORT NameLength);
+
NTSTATUS
AddIndexRoot(PNTFS_VCB Vcb,
PFILE_RECORD_HEADER FileRecord,
@@ -723,6 +737,9 @@ CreateIndexRootFromBTree(PDEVICE_EXTENSION DeviceExt,
PINDEX_ROOT_ATTRIBUTE *IndexRoot,
ULONG *Length);
+NTSTATUS
+DemoteBTreeRoot(PB_TREE Tree);
+
VOID
DestroyBTree(PB_TREE Tree);
@@ -752,13 +769,26 @@ GetAllocationOffsetFromVCN(PDEVICE_EXTENSION DeviceExt,
ULONG IndexBufferSize,
ULONGLONG Vcn);
+ULONG
+GetSizeOfIndexEntries(PB_TREE_FILENAME_NODE Node);
+
NTSTATUS
NtfsInsertKey(PB_TREE Tree,
ULONGLONG FileReference,
PFILENAME_ATTRIBUTE FileNameAttribute,
PB_TREE_FILENAME_NODE Node,
BOOLEAN CaseSensitive,
- ULONG MaxIndexRootSize);
+ ULONG MaxIndexRootSize,
+ ULONG IndexRecordSize,
+ PB_TREE_KEY *MedianKey,
+ PB_TREE_FILENAME_NODE *NewRightHandSibling);
+
+NTSTATUS
+SplitBTreeNode(PB_TREE Tree,
+ PB_TREE_FILENAME_NODE Node,
+ PB_TREE_KEY *MedianKey,
+ PB_TREE_FILENAME_NODE *NewRightHandSibling,
+ BOOLEAN CaseSensitive);
NTSTATUS
UpdateIndexAllocation(PDEVICE_EXTENSION DeviceExt,
@@ -772,8 +802,7 @@ UpdateIndexNode(PDEVICE_EXTENSION DeviceExt,
PB_TREE_FILENAME_NODE Node,
ULONG IndexBufferSize,
PNTFS_ATTR_CONTEXT IndexAllocationContext,
- ULONG IndexAllocationOffset,
- PNTFS_ATTR_CONTEXT BitmapContext);
+ ULONG IndexAllocationOffset);
/* close.c */
2531
days inactive
2531
days old
0 comments
1 participants
participants (1)
-
Trevor Thompson