/* 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
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
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,
*
* @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).
*
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");
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;
}
CreateIndexBufferFromBTreeNode(PDEVICE_EXTENSION DeviceExt,
PB_TREE_FILENAME_NODE Node,
ULONG BufferSize,
+ BOOLEAN HasChildren,
PINDEX_BUFFER IndexBuffer)
{
ULONG i;
// 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);
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
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;
{
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++)
{
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?
}
// 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");
CurrentKey = CurrentKey->NextKey;
}
+#ifndef NDEBUG
+ DumpBTree(Tree);
+#endif
+
if (HasIndexAllocation)
{
+#ifndef NDEBUG
PrintAllVCNs(DeviceExt,
IndexAllocationContext,
IndexBufferSize);
-
+#endif
ReleaseAttributeContext(IndexAllocationContext);
}
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)
}
// 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");
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;
}
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
* 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.
*/
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;
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);
// 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");
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
{
Node->FirstKey = NewKey;
else
PreviousKey->NextKey = NewKey;
- break;
}
+ break;
}
PreviousKey = CurrentKey;
// 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
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);
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,
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,
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?
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");
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))
{
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");
// 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)
}
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
projects / reactos.git / commitdiff