[reactos] 63/72: [NTFS] - Allow for creating a file when the index root gets too large and needs to be moved into an index record. Add some helper functions. +AllocateIndexNode() - Allocates a new index record in an index allocation. +CreateDummyKey() - Creates the final B_TREE_KEY for a B_TREE_FILENAME_NODE. Also creates the associated index entry. GetSizeOfIndexEntries() - Sums the size of each index entry in every key in a B-Tree node. +SetIndexEntryVCN() - Sets the VCN of a given IndexEntry.

[Trevor Thompson]

https://git.reactos.org/?p=reactos.git;a=commitdiff;h=88a7c3d14b5f74300baac…

commit 88a7c3d14b5f74300baacff3486b377901c2467f
Author: Trevor Thompson <tmt256(a)email.vccs.edu>
AuthorDate: Tue Aug 15 19:57:55 2017 +0000

    [NTFS] - Allow for creating a file when the index root gets too large and needs to be
moved into an index record. Add some helper functions.
    +AllocateIndexNode() - Allocates a new index record in an index allocation.
    +CreateDummyKey() - Creates the final B_TREE_KEY for a B_TREE_FILENAME_NODE. Also
creates the associated index entry.
    GetSizeOfIndexEntries() - Sums the size of each index entry in every key in a B-Tree
node.
    +SetIndexEntryVCN() - Sets the VCN of a given IndexEntry.
    NtfsInsertKey() - Handle instance when the index root grows too large. If it does, add
its contents to a new sub-node, and replace contents with a dummy-key whose child is the
new node.
    UpdateIndexAllocation() - Update index entry if a key has just been assigned a child
allocation.
    UpdateIndexNode() - Make sure the node exists on disk, and allocate an index record
for it if it doesn't.
    
    svn path=/branches/GSoC_2016/NTFS/; revision=75557
---
 drivers/filesystems/ntfs/btree.c | 520 ++++++++++++++++++++++++++++++++++++---
 drivers/filesystems/ntfs/mft.c   |  35 ++-
 drivers/filesystems/ntfs/ntfs.h  |   8 +-
 3 files changed, 519 insertions(+), 44 deletions(-)

diff --git a/drivers/filesystems/ntfs/btree.c b/drivers/filesystems/ntfs/btree.c
index 648111d9c0..727c147a2a 100644
--- a/drivers/filesystems/ntfs/btree.c
+++ b/drivers/filesystems/ntfs/btree.c
@@ -80,6 +80,237 @@ PrintAllVCNs(PDEVICE_EXTENSION Vcb,
     ExFreePoolWithTag(Buffer, TAG_NTFS);
 }
 
+/**
+* @name AllocateIndexNode
+* @implemented
+*
+* Allocates a new index record in an index allocation.
+*
+* @param DeviceExt
+* Pointer to the target DEVICE_EXTENSION describing the volume the node will be created
on.
+*
+* @param FileRecord
+* Pointer to a copy of the file record containing the index.
+*
+* @param IndexBufferSize
+* Size of an index record for this index, in bytes. Commonly defined as 4096.
+*
+* @param IndexAllocationCtx
+* Pointer to an NTFS_ATTR_CONTEXT describing the index allocation attribute the node will
be assigned to.
+*
+* @param IndexAllocationOffset
+* Offset of the index allocation attribute relative to the file record.
+*
+* @param NewVCN
+* Pointer to a ULONGLONG which will receive the VCN of the newly-assigned index record
+*
+* @returns
+* STATUS_SUCCESS in case of success.
+* STATUS_NOT_IMPLEMENTED if there's no $I30 bitmap attribute in the file record.
+* 
+* @remarks
+* AllocateIndexNode() doesn't write any data to the index record it creates. Called
by UpdateIndexNode().
+* Don't call PrintAllVCNs() or NtfsDumpFileRecord() after calling AllocateIndexNode()
before UpdateIndexNode() finishes.
+*/
+NTSTATUS
+AllocateIndexNode(PDEVICE_EXTENSION DeviceExt,
+                  PFILE_RECORD_HEADER FileRecord,
+                  ULONG IndexBufferSize,
+                  PNTFS_ATTR_CONTEXT IndexAllocationCtx,
+                  ULONG IndexAllocationOffset,
+                  PULONGLONG NewVCN)
+{
+    NTSTATUS Status;
+    PNTFS_ATTR_CONTEXT BitmapCtx;
+    ULONGLONG IndexAllocationLength, BitmapLength;
+    ULONG BitmapOffset;
+    ULONGLONG NextNodeNumber;
+    PCHAR *BitmapMem;
+    ULONG *BitmapPtr;
+    RTL_BITMAP Bitmap;
+    ULONG BytesWritten;
+    ULONG BytesNeeded;
+    LARGE_INTEGER DataSize;
+
+    DPRINT1("AllocateIndexNode(%p, %p, %lu, %p, %lu, %p) called.\n",
DeviceExt,
+            FileRecord,
+            IndexBufferSize,
+            IndexAllocationCtx,
+            IndexAllocationOffset,
+            NewVCN);
+
+    // Get the length of the attribute allocation
+    IndexAllocationLength = AttributeDataLength(IndexAllocationCtx->pRecord);
+
+    // Find the bitmap attribute for the index
+    Status = FindAttribute(DeviceExt,
+                           FileRecord,
+                           AttributeBitmap,
+                           L"$I30",
+                           4,
+                           &BitmapCtx,
+                           &BitmapOffset);
+    if (!NT_SUCCESS(Status))
+    {
+        DPRINT1("FIXME: Need to add bitmap attribute!\n");
+        return STATUS_NOT_IMPLEMENTED;
+    }
+
+    // Get the length of the bitmap attribute
+    BitmapLength = AttributeDataLength(BitmapCtx->pRecord);
+
+    NextNodeNumber = IndexAllocationLength / DeviceExt->NtfsInfo.BytesPerIndexRecord;
+
+    // TODO: Find unused allocation in bitmap and use that space first
+
+    // Add another bit to bitmap
+
+    // See how many bytes we need to store the amount of bits we'll have
+    BytesNeeded = NextNodeNumber / 8;
+    if (NextNodeNumber % 8 != 0)
+        BytesNeeded++;
+
+    // Windows seems to allocate the bitmap in 8-byte chunks to keep any bytes from being
wasted on padding
+    ALIGN_UP(BytesNeeded, ATTR_RECORD_ALIGNMENT);
+
+    // Do we need to enlarge the bitmap?
+    if (BytesNeeded > BitmapLength)
+    {
+        // TODO: handle synchronization issues that could occur from changing the
directory's file record
+        // Change bitmap size
+        DataSize.QuadPart = BytesNeeded;
+        Status = SetResidentAttributeDataLength(DeviceExt,
+                                                BitmapCtx,
+                                                BitmapOffset,
+                                                FileRecord,
+                                                &DataSize);
+        if (!NT_SUCCESS(Status))
+        {
+            DPRINT1("ERROR: Failed to set length of bitmap attribute!\n");
+            ReleaseAttributeContext(BitmapCtx);
+            return Status;
+        }
+    }
+
+    // Enlarge Index Allocation attribute
+    DataSize.QuadPart = IndexAllocationLength + IndexBufferSize;
+    Status = SetNonResidentAttributeDataLength(DeviceExt,
+                                               IndexAllocationCtx,
+                                               IndexAllocationOffset,
+                                               FileRecord,
+                                               &DataSize);
+    if (!NT_SUCCESS(Status))
+    {
+        DPRINT1("ERROR: Failed to set length of index allocation!\n");
+        ReleaseAttributeContext(BitmapCtx);
+        return Status;
+    }
+
+    // Update file record on disk
+    Status = UpdateFileRecord(DeviceExt, IndexAllocationCtx->FileMFTIndex,
FileRecord);
+    if (!NT_SUCCESS(Status))
+    {
+        DPRINT1("ERROR: Failed to update file record!\n");
+        ReleaseAttributeContext(BitmapCtx);
+        return Status;
+    }
+
+    // Allocate memory for the bitmap. RtlInitializeBitmap() wants a pointer that's
ULONG-aligned
+    BitmapMem = ExAllocatePoolWithTag(NonPagedPool, BytesNeeded + sizeof(ULONG) - 1,
TAG_NTFS);
+    BitmapPtr = (PULONG)ALIGN_UP_BY((ULONG_PTR)BitmapMem, sizeof(ULONG));
+
+    RtlZeroMemory(BitmapPtr, BytesNeeded);
+
+    // Read the existing bitmap data
+    Status = ReadAttribute(DeviceExt, BitmapCtx, 0, (PCHAR)BitmapPtr, BitmapLength);
+
+    // Initialize bitmap
+    RtlInitializeBitMap(&Bitmap, BitmapPtr, BytesNeeded);
+
+    // Set the bit for the new index record
+    RtlSetBits(&Bitmap, NextNodeNumber, 1);
+  
+    // Write the new bitmap attribute
+    Status = WriteAttribute(DeviceExt,
+                            BitmapCtx,
+                            0,
+                            (const PUCHAR)BitmapPtr,
+                            BytesNeeded,
+                            &BytesWritten,
+                            FileRecord);
+    if (!NT_SUCCESS(Status))
+    {
+        DPRINT1("ERROR: Unable to write to $I30 bitmap attribute!\n");
+    }
+
+    // Calculate VCN of new node number
+    *NewVCN = NextNodeNumber * (IndexBufferSize /
DeviceExt->NtfsInfo.BytesPerCluster);
+
+    ExFreePoolWithTag(BitmapMem, TAG_NTFS);
+    ReleaseAttributeContext(BitmapCtx);
+
+    return Status;
+}
+
+/**
+* @name CreateDummyKey
+* @implemented
+*
+* Creates the final B_TREE_KEY for a B_TREE_FILENAME_NODE. Also creates the associated
index entry.
+*
+* @param HasChildNode
+* BOOLEAN to indicate if this key will have a LesserChild.
+*
+* @return
+* The newly-created key.
+*/
+PB_TREE_KEY
+CreateDummyKey(BOOLEAN HasChildNode)
+{
+    PINDEX_ENTRY_ATTRIBUTE NewIndexEntry;
+    PB_TREE_KEY NewDummyKey;
+
+    // Calculate max size of a dummy key
+    ULONG EntrySize = ALIGN_UP_BY(FIELD_OFFSET(INDEX_ENTRY_ATTRIBUTE, FileName), 8);
+    EntrySize += sizeof(ULONGLONG); // for VCN
+
+    // Create the index entry for the key
+    NewIndexEntry = ExAllocatePoolWithTag(NonPagedPool, EntrySize, TAG_NTFS);
+    if (!NewIndexEntry)
+    {
+        DPRINT1("Couldn't allocate memory for dummy key index entry!\n");
+        return NULL;
+    }
+
+    RtlZeroMemory(NewIndexEntry, EntrySize);
+    
+    if (HasChildNode)
+    {
+        NewIndexEntry->Flags = NTFS_INDEX_ENTRY_NODE | NTFS_INDEX_ENTRY_END;
+    }
+    else
+    {
+        NewIndexEntry->Flags = NTFS_INDEX_ENTRY_END;
+        EntrySize -= sizeof(ULONGLONG); // no VCN
+    }
+
+    NewIndexEntry->Length = EntrySize;
+
+    // Create the key
+    NewDummyKey = ExAllocatePoolWithTag(NonPagedPool, sizeof(B_TREE_KEY), TAG_NTFS);
+    if (!NewDummyKey)
+    {
+        DPRINT1("Unable to allocate dummy key!\n");
+        ExFreePoolWithTag(NewIndexEntry, TAG_NTFS);
+        return NULL;
+    }
+    RtlZeroMemory(NewDummyKey, sizeof(B_TREE_KEY));
+
+    NewDummyKey->IndexEntry = NewIndexEntry;
+
+    return NewDummyKey;
+}
+
 /**
 * @name CompareTreeKeys
 * @implemented
@@ -500,6 +731,42 @@ CreateBTreeFromIndex(PDEVICE_EXTENSION Vcb,
     return STATUS_SUCCESS;
 }
 
+/**
+* @name GetSizeOfIndexEntries
+* @implemented
+*
+* Sums the size of each index entry in every key in a B-Tree node.
+*
+* @param Node
+* Pointer to a B_TREE_FILENAME_NODE. The size of this node's index entries will be
returned.
+*
+* @returns
+* The sum of the sizes of every index entry for each key in the B-Tree node.
+*
+* @remarks
+* Gets only the size of the index entries; doesn't include the size of any headers
that would be added to an index record.
+*/
+ULONG
+GetSizeOfIndexEntries(PB_TREE_FILENAME_NODE Node)
+{
+    // Start summing the total size of this node's entries
+    ULONG NodeSize = 0;
+
+    // Walk through the list of Node Entries
+    PB_TREE_KEY CurrentKey = Node->FirstKey;
+    ULONG i;
+    for (i = 0; i < Node->KeyCount; i++)
+    {        
+        ASSERT(CurrentKey->IndexEntry->Length != 0);
+
+        // Add the length of the current node
+        NodeSize += CurrentKey->IndexEntry->Length;
+        CurrentKey = CurrentKey->NextKey;
+    }
+
+    return NodeSize;
+}
+
 /**
 * @name CreateIndexRootFromBTree
 * @implemented
@@ -686,6 +953,33 @@ CreateIndexBufferFromBTreeNode(PDEVICE_EXTENSION DeviceExt,
     return Status;
 }
 
+/**
+* @name SetIndexEntryVCN
+* @implemented
+*
+* Sets the VCN of a given IndexEntry.
+*
+* @param IndexEntry
+* Pointer to an INDEX_ENTRY_ATTRIBUTE structure that will have its VCN set.
+*
+* @param VCN
+* VCN to store in the index entry.
+*
+* @remarks
+* The index entry must have enough memory allocated to store the VCN, and must have the
NTFS_INDEX_ENTRY_NODE flag set.
+* The VCN of an index entry is stored at the very end of the structure, after the
filename attribute. Since the filename
+* attribute can be a variable size, this function makes setting this member easy.
+*/
+VOID
+SetIndexEntryVCN(PINDEX_ENTRY_ATTRIBUTE IndexEntry, ULONGLONG VCN)
+{
+    PULONGLONG Destination = (PULONGLONG)((ULONG_PTR)IndexEntry + IndexEntry->Length -
sizeof(ULONGLONG));
+
+    ASSERT(IndexEntry->Flags & NTFS_INDEX_ENTRY_NODE);
+
+    *Destination = VCN;
+}
+
 NTSTATUS
 UpdateIndexAllocation(PDEVICE_EXTENSION DeviceExt,
                       PB_TREE Tree,
@@ -698,13 +992,20 @@ UpdateIndexAllocation(PDEVICE_EXTENSION DeviceExt,
     NTSTATUS Status;
     BOOLEAN HasIndexAllocation = FALSE;
     ULONG i;
+    ULONG IndexAllocationOffset;
 
-    DPRINT1("UpdateIndexAllocations() called.\n");
+    DPRINT1("UpdateIndexAllocation() called.\n");
 
-    Status = FindAttribute(DeviceExt, FileRecord, AttributeIndexAllocation,
L"$I30", 4, &IndexAllocationContext, NULL);
+    Status = FindAttribute(DeviceExt, FileRecord, AttributeIndexAllocation,
L"$I30", 4, &IndexAllocationContext, &IndexAllocationOffset);
     if (NT_SUCCESS(Status))
+    {
         HasIndexAllocation = TRUE;
 
+        PrintAllVCNs(DeviceExt,
+                     IndexAllocationContext,
+                     IndexBufferSize);
+    }
+
     // TODO: Handle bitmap
     BitmapContext = NULL;
 
@@ -719,48 +1020,112 @@ UpdateIndexAllocation(PDEVICE_EXTENSION DeviceExt,
                 DPRINT1("FIXME: Need to add index allocation\n");
                 return STATUS_NOT_IMPLEMENTED;
             }
-            else
+           
+            Status = UpdateIndexNode(DeviceExt, FileRecord, CurrentKey->LesserChild,
IndexBufferSize, IndexAllocationContext, IndexAllocationOffset, BitmapContext);
+            if (!NT_SUCCESS(Status))
             {
-                Status = UpdateIndexNode(DeviceExt, CurrentKey->LesserChild,
IndexBufferSize, IndexAllocationContext, BitmapContext);
-                if (!NT_SUCCESS(Status))
+                DPRINT1("ERROR: Failed to update index node!\n");
+                ReleaseAttributeContext(IndexAllocationContext);
+                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: Failed to update index node!\n");
-                    ReleaseAttributeContext(IndexAllocationContext);
-                    return Status;
+                    DPRINT1("ERROR: Unable to allocate memory for new index
entry!\n");
+                    if (HasIndexAllocation)
+                        ReleaseAttributeContext(IndexAllocationContext);
+                    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;
+                CurrentKey->IndexEntry->Flags |= NTFS_INDEX_ENTRY_NODE;
             }
 
+            // Update the VCN stored in the index entry of CurrentKey
+            SetIndexEntryVCN(CurrentKey->IndexEntry,
CurrentKey->LesserChild->NodeNumber);
+
         }
         CurrentKey = CurrentKey->NextKey;
     }
 
-    if(HasIndexAllocation)
+    if (HasIndexAllocation)
+    {
+        PrintAllVCNs(DeviceExt,
+                     IndexAllocationContext,
+                     IndexBufferSize);
+
         ReleaseAttributeContext(IndexAllocationContext);
+    }
 
     return STATUS_SUCCESS;
 }
 
 NTSTATUS
 UpdateIndexNode(PDEVICE_EXTENSION DeviceExt,
+                PFILE_RECORD_HEADER FileRecord,
                 PB_TREE_FILENAME_NODE Node,
                 ULONG IndexBufferSize,
                 PNTFS_ATTR_CONTEXT IndexAllocationContext,
+                ULONG IndexAllocationOffset,
                 PNTFS_ATTR_CONTEXT BitmapContext)
 {
     ULONG i;
     PB_TREE_KEY CurrentKey = Node->FirstKey;
     NTSTATUS Status;
 
-    DPRINT1("UpdateIndexNode(%p, %p, %lu, %p, %p) called for index node with VCN
%I64u\n", DeviceExt, Node, IndexBufferSize, IndexAllocationContext, BitmapContext,
Node->NodeNumber);
+    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->NodeNumber);
 
     // Do we need to write this node to disk?
     if (Node->DiskNeedsUpdating)
     {
         ULONGLONG NodeOffset;
         ULONG LengthWritten;
+        PINDEX_BUFFER IndexBuffer;
+
+        // Does the node need to be assigned a VCN?
+        if (!Node->ExistsOnDisk)
+        {
+            // Allocate the node
+            Status = AllocateIndexNode(DeviceExt,
+                                       FileRecord,
+                                       IndexBufferSize,
+                                       IndexAllocationContext,
+                                       IndexAllocationOffset,
+                                       &Node->NodeNumber);
+            if (!NT_SUCCESS(Status))
+            {
+                DPRINT1("ERROR: Failed to allocate index record in index
allocation!\n");
+                return Status;
+            }
+
+            Node->ExistsOnDisk = TRUE;
+        }
 
         // Allocate memory for an index buffer
-        PINDEX_BUFFER IndexBuffer = ExAllocatePoolWithTag(NonPagedPool, IndexBufferSize,
TAG_NTFS);
+        IndexBuffer = ExAllocatePoolWithTag(NonPagedPool, IndexBufferSize, TAG_NTFS);
         if (!IndexBuffer)
         {
             DPRINT1("ERROR: Failed to allocate %lu bytes for index buffer!\n",
IndexBufferSize);
@@ -780,7 +1145,7 @@ UpdateIndexNode(PDEVICE_EXTENSION DeviceExt,
         NodeOffset = GetAllocationOffsetFromVCN(DeviceExt, IndexBufferSize,
Node->NodeNumber);
 
         // Write the buffer to the index allocation
-        Status = WriteAttribute(DeviceExt, IndexAllocationContext, NodeOffset, (const
PUCHAR)IndexBuffer, IndexBufferSize, &LengthWritten, NULL);
+        Status = WriteAttribute(DeviceExt, IndexAllocationContext, NodeOffset, (const
PUCHAR)IndexBuffer, IndexBufferSize, &LengthWritten, FileRecord);
         if (!NT_SUCCESS(Status) || LengthWritten != IndexBufferSize)
         {
             DPRINT1("ERROR: Failed to update index allocation!\n");
@@ -806,7 +1171,7 @@ UpdateIndexNode(PDEVICE_EXTENSION DeviceExt,
         if (CurrentKey->LesserChild)
         {
             // Update the child node on disk
-            Status = UpdateIndexNode(DeviceExt, CurrentKey->LesserChild,
IndexBufferSize, IndexAllocationContext, BitmapContext);
+            Status = UpdateIndexNode(DeviceExt, FileRecord, CurrentKey->LesserChild,
IndexBufferSize, IndexAllocationContext, IndexAllocationOffset, BitmapContext);
             if (!NT_SUCCESS(Status))
             {
                 DPRINT1("ERROR: Failed to update child node!\n");
@@ -996,6 +1361,9 @@ GetAllocationOffsetFromVCN(PDEVICE_EXTENSION DeviceExt,
 *
 * Inserts a FILENAME_ATTRIBUTE into a B-Tree node.
 *
+* @param Tree
+* Pointer to the B_TREE the key (filename attribute) is being inserted into.
+*
 * @param FileReference
 * Reference number to the file being added. This will be a combination of the MFT index
and update sequence number.
 *
@@ -1009,27 +1377,35 @@ GetAllocationOffsetFromVCN(PDEVICE_EXTENSION DeviceExt,
 * 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.
 *
+* @param MaxIndexRootSize
+* 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.
+*
 * @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,
+NtfsInsertKey(PB_TREE Tree,
+              ULONGLONG FileReference,
               PFILENAME_ATTRIBUTE FileNameAttribute,
               PB_TREE_FILENAME_NODE Node,
-              BOOLEAN CaseSensitive)
+              BOOLEAN CaseSensitive,
+              ULONG MaxIndexRootSize)
 {
     PB_TREE_KEY NewKey, CurrentKey, PreviousKey;
-    NTSTATUS Status = STATUS_SUCCESS; 
+    NTSTATUS Status = STATUS_SUCCESS;
     ULONG NodeSize;
     ULONG AllocatedNodeSize;
     ULONG MaxNodeSizeWithoutHeader;
     ULONG i;
 
-    DPRINT1("NtfsInsertKey(0x%I64x, %p, %p, %s)\n",
+    DPRINT1("NtfsInsertKey(%p, 0x%I64x, %p, %p, %s, %lu)\n",
+            Tree,
             FileReference,
             FileNameAttribute,
             Node,
-            CaseSensitive ? "TRUE" : "FALSE");
+            CaseSensitive ? "TRUE" : "FALSE",
+            MaxIndexRootSize);
 
     // Create the key for the filename attribute
     NewKey = CreateBTreeKeyFromFilename(FileReference, FileNameAttribute);
@@ -1044,6 +1420,11 @@ NtfsInsertKey(ULONGLONG FileReference,
         // Should the New Key go before the current key?
         LONG Comparison = CompareTreeKeys(NewKey, CurrentKey, CaseSensitive);
 
+        if (Comparison == 0)
+        {
+            DPRINT1("\t\tComparison == 0: %.*S\n",
NewKey->IndexEntry->FileName.NameLength, NewKey->IndexEntry->FileName.Name);
+            DPRINT1("\t\tComparison == 0: %.*S\n",
CurrentKey->IndexEntry->FileName.NameLength,
CurrentKey->IndexEntry->FileName.Name);
+        }
         ASSERT(Comparison != 0);
 
         // Is NewKey < CurrentKey?
@@ -1054,7 +1435,14 @@ NtfsInsertKey(ULONGLONG FileReference,
             if (CurrentKey->LesserChild)
             {
                 // Insert the key into the child node
-                Status = NtfsInsertKey(FileReference, FileNameAttribute,
CurrentKey->LesserChild, CaseSensitive);
+                Status = NtfsInsertKey(Tree, FileReference, FileNameAttribute,
CurrentKey->LesserChild, CaseSensitive, 0);
+                if (!NT_SUCCESS(Status))
+                {
+                    DPRINT1("ERROR: Failed to insert key.\n");
+                    ExFreePoolWithTag(NewKey, TAG_NTFS);
+                    return Status;
+                }
+
             }
             else
             {
@@ -1078,25 +1466,89 @@ NtfsInsertKey(ULONGLONG FileReference,
         CurrentKey = CurrentKey->NextKey;
     }
 
-    // Is the node larger than its allocated size?
-    NodeSize = 0; 
-    CurrentKey = Node->FirstKey;
-    for (i = 0; i < Node->KeyCount; i++)
+    // Determine how much space the index entries will need
+    NodeSize = GetSizeOfIndexEntries(Node);
+
+    // Is Node the root node?
+    if (Node == Tree->RootNode)
     {
-        NodeSize += CurrentKey->IndexEntry->Length;
-        CurrentKey = CurrentKey->NextKey;
-    }
+        // Is the index root too large for the file record?
+        if (NodeSize > MaxIndexRootSize)
+        {
+            PB_TREE_FILENAME_NODE NewSubNode, NewIndexRoot;
+            PB_TREE_KEY DummyKey;
+
+            DPRINT1("Collapsing Index Root into sub-node.\n") ;
+
+            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)
+            {
+                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 = Node->KeyCount;
+            NewSubNode->FirstKey = Node->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;
+            NewIndexRoot->ExistsOnDisk = TRUE;
 
-    // TEMPTEMP: TODO: MATH
-    AllocatedNodeSize = 0xfe8;
-    MaxNodeSizeWithoutHeader = AllocatedNodeSize - 0x28;
+            // Make the new node the Tree's root node
+            Tree->RootNode = NewIndexRoot;
 
-    if (NodeSize > MaxNodeSizeWithoutHeader)
+            DumpBTree(Tree);
+
+            return STATUS_SUCCESS;
+        }
+    }
+    else
     {
-        DPRINT1("FIXME: Splitting a node is still a WIP!\n");
-        //SplitBTreeNode(NULL, Node);
-        //DumpBTree(Tree);
-        return STATUS_NOT_IMPLEMENTED;
+        // TEMPTEMP: TODO: MATH
+        AllocatedNodeSize = 0xfe8;
+        MaxNodeSizeWithoutHeader = AllocatedNodeSize - 0x28;
+        
+        // Has the node grown larger than its allocated size?
+        if (NodeSize > MaxNodeSizeWithoutHeader)
+        {
+            DPRINT1("FIXME: Splitting a node is still a WIP!\n");
+            //SplitBTreeNode(NULL, Node);
+            //DumpBTree(Tree);
+            return STATUS_NOT_IMPLEMENTED;
+        }
     }
 
     // NewEntry and NewKey will be destroyed later by DestroyBTree()
diff --git a/drivers/filesystems/ntfs/mft.c b/drivers/filesystems/ntfs/mft.c
index aeee447e33..0cd2767efb 100644
--- a/drivers/filesystems/ntfs/mft.c
+++ b/drivers/filesystems/ntfs/mft.c
@@ -2056,9 +2056,10 @@ NtfsAddFilenameToDirectory(PDEVICE_EXTENSION DeviceExt,
     ULONG LengthWritten;
     PINDEX_ROOT_ATTRIBUTE NewIndexRoot;
     ULONG AttributeLength;
+    PNTFS_ATTR_RECORD NextAttribute;
     PB_TREE NewTree;
     ULONG BtreeIndexLength;
-    ULONG MaxIndexSize;
+    ULONG MaxIndexRootSize;
 
     // Allocate memory for the parent directory
     ParentFileRecord = ExAllocatePoolWithTag(NonPagedPool,
@@ -2100,11 +2101,29 @@ NtfsAddFilenameToDirectory(PDEVICE_EXTENSION DeviceExt,
     }
 
     // Find the maximum index size given what the file record can hold
-    MaxIndexSize = DeviceExt->NtfsInfo.BytesPerFileRecord
-        - IndexRootOffset
-        - IndexRootContext->pRecord->Resident.ValueOffset
-        - FIELD_OFFSET(INDEX_ROOT_ATTRIBUTE, Header)
-        - (sizeof(ULONG) * 2);
+    // First, find the max index size assuming index root is the last attribute
+    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(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
+        MaxIndexRootSize -= LengthOfAttributes;
+    }
 
     // Allocate memory for the index root data
     I30IndexRootLength = AttributeDataLength(IndexRootContext->pRecord);
@@ -2146,7 +2165,7 @@ NtfsAddFilenameToDirectory(PDEVICE_EXTENSION DeviceExt,
     DumpBTree(NewTree);
 
     // Insert the key for the file we're adding
-    Status = NtfsInsertKey(FileReferenceNumber, FilenameAttribute, NewTree->RootNode,
CaseSensitive);
+    Status = NtfsInsertKey(NewTree, FileReferenceNumber, FilenameAttribute,
NewTree->RootNode, CaseSensitive, MaxIndexRootSize);
     if (!NT_SUCCESS(Status))
     {
         DPRINT1("ERROR: Failed to insert key into B-Tree!\n");
@@ -2172,7 +2191,7 @@ NtfsAddFilenameToDirectory(PDEVICE_EXTENSION DeviceExt,
     }
 
     // Create the Index Root from the B*Tree
-    Status = CreateIndexRootFromBTree(DeviceExt, NewTree, MaxIndexSize,
&NewIndexRoot, &BtreeIndexLength);
+    Status = CreateIndexRootFromBTree(DeviceExt, NewTree, MaxIndexRootSize,
&NewIndexRoot, &BtreeIndexLength);
     if (!NT_SUCCESS(Status))
     {
         DPRINT1("ERROR: Failed to create Index root from B-Tree!\n");
diff --git a/drivers/filesystems/ntfs/ntfs.h b/drivers/filesystems/ntfs/ntfs.h
index 4d436a699e..030b777c22 100644
--- a/drivers/filesystems/ntfs/ntfs.h
+++ b/drivers/filesystems/ntfs/ntfs.h
@@ -728,10 +728,12 @@ GetAllocationOffsetFromVCN(PDEVICE_EXTENSION DeviceExt,
                            ULONGLONG Vcn);
 
 NTSTATUS
-NtfsInsertKey(ULONGLONG FileReference,
+NtfsInsertKey(PB_TREE Tree,
+              ULONGLONG FileReference,
               PFILENAME_ATTRIBUTE FileNameAttribute,
               PB_TREE_FILENAME_NODE Node,
-              BOOLEAN CaseSensitive);
+              BOOLEAN CaseSensitive,
+              ULONG MaxIndexRootSize);
 
 NTSTATUS
 UpdateIndexAllocation(PDEVICE_EXTENSION DeviceExt,
@@ -741,9 +743,11 @@ UpdateIndexAllocation(PDEVICE_EXTENSION DeviceExt,
 
 NTSTATUS
 UpdateIndexNode(PDEVICE_EXTENSION DeviceExt,
+                PFILE_RECORD_HEADER FileRecord,
                 PB_TREE_FILENAME_NODE Node,
                 ULONG IndexBufferSize,
                 PNTFS_ATTR_CONTEXT IndexAllocationContext,
+                ULONG IndexAllocationOffset,
                 PNTFS_ATTR_CONTEXT BitmapContext);
 
 /* close.c */