From: Trevor Thompson Date: Tue, 15 Aug 2017 19:57:55 +0000 (+0000) Subject: [NTFS] - Allow for creating a file when the index root gets too large and needs to... X-Git-Tag: 0.4.9-dev~693^2~8 X-Git-Url: https://git.reactos.org/?p=reactos.git;a=commitdiff_plain;h=88a7c3d14b5f74300baacff3486b377901c2467f [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 --- diff --git a/drivers/filesystems/ntfs/btree.c b/drivers/filesystems/ntfs/btree.c index 648111d9c05..727c147a2a4 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 aeee447e33b..0cd2767efb9 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 4d436a699e1..030b777c22d 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 */