ReactOS 0.4.15-dev-7918-g2a2556c
btree.c File Reference
#include "ntfs.h"
#include <debug.h>
Include dependency graph for btree.c:

Go to the source code of this file.

Macros

#define NDEBUG
 

Functions

VOID PrintAllVCNs (PDEVICE_EXTENSION Vcb, PNTFS_ATTR_CONTEXT IndexAllocationContext, ULONG NodeSize)
 
AllocateIndexNode

@implemented

Allocates a new index record in an index allocation.

Parameters
DeviceExtPointer to the target DEVICE_EXTENSION describing the volume the node will be created on.
FileRecordPointer to a copy of the file record containing the index.
IndexBufferSizeSize of an index record for this index, in bytes. Commonly defined as 4096.
IndexAllocationCtxPointer to an NTFS_ATTR_CONTEXT describing the index allocation attribute the node will be assigned to.
IndexAllocationOffsetOffset of the index allocation attribute relative to the file record.
NewVCNPointer 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. Possible TODO: Create an empty node and write it to the allocated index node, so the index allocation is always valid.
NTSTATUS AllocateIndexNode (PDEVICE_EXTENSION DeviceExt, PFILE_RECORD_HEADER FileRecord, ULONG IndexBufferSize, PNTFS_ATTR_CONTEXT IndexAllocationCtx, ULONG IndexAllocationOffset, PULONGLONG NewVCN)
 
CreateDummyKey

@implemented

Creates the final B_TREE_KEY for a B_TREE_FILENAME_NODE. Also creates the associated index entry.

Parameters
HasChildNodeBOOLEAN to indicate if this key will have a LesserChild.
Returns
The newly-created key.
PB_TREE_KEY CreateDummyKey (BOOLEAN HasChildNode)
 
CreateEmptyBTree

@implemented

Creates an empty B-Tree, which will contain a single root node which will contain a single dummy key.

Parameters
NewTreePointer to a PB_TREE that will receive the pointer of the newly-created B-Tree.
Returns
STATUS_SUCCESS on success. STATUS_INSUFFICIENT_RESOURCES if an allocation fails.
NTSTATUS CreateEmptyBTree (PB_TREE *NewTree)
 
CompareTreeKeys

@implemented

Compare two B_TREE_KEY's to determine their order in the tree.

Parameters
Key1Pointer to a B_TREE_KEY that will be compared.
Key2Pointer to the other B_TREE_KEY that will be compared.
CaseSensitiveBoolean indicating if the function should operate in case-sensitive mode. This will be TRUE if an application created the file with the FILE_FLAG_POSIX_SEMANTICS flag.
Returns
0 if the two keys are equal. < 0 if key1 is less thank key2

‍0 if key1 is greater than key2

Remarks
Any other key is always less than the final (dummy) key in a node. Key1 must not be the dummy node.
LONG CompareTreeKeys (PB_TREE_KEY Key1, PB_TREE_KEY Key2, BOOLEAN CaseSensitive)
 
CountBTreeKeys

@implemented

Counts the number of linked B-Tree keys, starting with FirstKey.

Parameters
FirstKeyPointer to a B_TREE_KEY that will be the first key to be counted.
Returns
The number of keys in a linked-list, including FirstKey and the final dummy key.
ULONG CountBTreeKeys (PB_TREE_KEY FirstKey)
 
PB_TREE_FILENAME_NODE CreateBTreeNodeFromIndexNode (PDEVICE_EXTENSION Vcb, PINDEX_ROOT_ATTRIBUTE IndexRoot, PNTFS_ATTR_CONTEXT IndexAllocationAttributeCtx, PINDEX_ENTRY_ATTRIBUTE NodeEntry)
 
CreateBTreeFromIndex

@implemented

Parse an index and create a B-Tree in memory from it.

Parameters
IndexRootContextPointer to an NTFS_ATTR_CONTEXT that describes the location of the index root attribute.
NewTreePointer to a PB_TREE that will receive the pointer to a newly-created B-Tree.
Returns
STATUS_SUCCESS on success. STATUS_INSUFFICIENT_RESOURCES if an allocation fails.
Remarks
Allocates memory for the entire tree. Caller is responsible for destroying the tree with DestroyBTree().
NTSTATUS CreateBTreeFromIndex (PDEVICE_EXTENSION Vcb, PFILE_RECORD_HEADER FileRecordWithIndex, PNTFS_ATTR_CONTEXT IndexRootContext, PINDEX_ROOT_ATTRIBUTE IndexRoot, PB_TREE *NewTree)
 
GetSizeOfIndexEntries

@implemented

Sums the size of each index entry in every key in a B-Tree node.

Parameters
NodePointer 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)
 
CreateIndexRootFromBTree

@implemented

Parse a B-Tree in memory and convert it into an index that can be written to disk.

Parameters
DeviceExtPointer to the DEVICE_EXTENSION of the target drive.
TreePointer to a B_TREE that describes the index to be written.
MaxIndexSizeDescribes 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).

Parameters
IndexRootPointer to a PINDEX_ROOT_ATTRIBUTE that will receive a pointer to the newly-created index.
LengthPointer to a ULONG which will receive the length of the new index root.
Returns
STATUS_SUCCESS on success. STATUS_INSUFFICIENT_RESOURCES if an allocation fails. STATUS_NOT_IMPLEMENTED if the new index can't fit within MaxIndexSize.
Remarks
If the function succeeds, it's the caller's responsibility to free IndexRoot with ExFreePoolWithTag().
NTSTATUS CreateIndexRootFromBTree (PDEVICE_EXTENSION DeviceExt, PB_TREE Tree, ULONG MaxIndexSize, PINDEX_ROOT_ATTRIBUTE *IndexRoot, ULONG *Length)
 
NTSTATUS CreateIndexBufferFromBTreeNode (PDEVICE_EXTENSION DeviceExt, PB_TREE_FILENAME_NODE Node, ULONG BufferSize, BOOLEAN HasChildren, PINDEX_BUFFER IndexBuffer)
 
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.

Parameters
TreePointer 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)
 
SetIndexEntryVCN

@implemented

Sets the VCN of a given IndexEntry.

Parameters
IndexEntryPointer to an INDEX_ENTRY_ATTRIBUTE structure that will have its VCN set.
VCNVCN 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)
 
NTSTATUS UpdateIndexAllocation (PDEVICE_EXTENSION DeviceExt, PB_TREE Tree, ULONG IndexBufferSize, PFILE_RECORD_HEADER FileRecord)
 
NTSTATUS UpdateIndexNode (PDEVICE_EXTENSION DeviceExt, PFILE_RECORD_HEADER FileRecord, PB_TREE_FILENAME_NODE Node, ULONG IndexBufferSize, PNTFS_ATTR_CONTEXT IndexAllocationContext, ULONG IndexAllocationOffset)
 
PB_TREE_KEY CreateBTreeKeyFromFilename (ULONGLONG FileReference, PFILENAME_ATTRIBUTE FileNameAttribute)
 
VOID DestroyBTreeKey (PB_TREE_KEY Key)
 
VOID DestroyBTreeNode (PB_TREE_FILENAME_NODE Node)
 
DestroyBTree

@implemented

Destroys a B-Tree.

Parameters
TreePointer to the B_TREE which will be destroyed.
Remarks
Destroys every bit of data stored in the tree.
VOID DestroyBTree (PB_TREE Tree)
 
VOID DumpBTreeKey (PB_TREE Tree, PB_TREE_KEY Key, ULONG Number, ULONG Depth)
 
VOID DumpBTreeNode (PB_TREE Tree, PB_TREE_FILENAME_NODE Node, ULONG Number, ULONG Depth)
 
DumpBTree

@implemented

Displays a B-Tree.

Parameters
TreePointer to the B_TREE which will be displayed.
Remarks
Displays a diagnostic summary of a B_TREE.
VOID DumpBTree (PB_TREE Tree)
 
ULONGLONG GetAllocationOffsetFromVCN (PDEVICE_EXTENSION DeviceExt, ULONG IndexBufferSize, ULONGLONG Vcn)
 
ULONGLONG GetIndexEntryVCN (PINDEX_ENTRY_ATTRIBUTE IndexEntry)
 
NtfsInsertKey

@implemented

Inserts a FILENAME_ATTRIBUTE into a B-Tree node.

Parameters
TreePointer to the B_TREE the key (filename attribute) is being inserted into.
FileReferenceReference number to the file being added. This will be a combination of the MFT index and update sequence number.
FileNameAttributePointer to a FILENAME_ATTRIBUTE which is the data for the key that will be added to the tree. A copy will be made.
NodePointer to a B_TREE_FILENAME_NODE into which a new key will be inserted, in order.
CaseSensitiveBoolean 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.
MaxIndexRootSizeThe 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.
IndexRecordSizeThe size, in bytes, of an index record for this index. AKA an index buffer. Usually set to 4096.
MedianKeyPointer 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.
NewRightHandSiblingPointer 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.
NTSTATUS NtfsInsertKey (PB_TREE Tree, ULONGLONG FileReference, PFILENAME_ATTRIBUTE FileNameAttribute, PB_TREE_FILENAME_NODE Node, BOOLEAN CaseSensitive, ULONG MaxIndexRootSize, ULONG IndexRecordSize, PB_TREE_KEY *MedianKey, PB_TREE_FILENAME_NODE *NewRightHandSibling)
 
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.

Parameters
TreePointer to the B_TREE which contains the node being split
NodePointer to the B_TREE_FILENAME_NODE that needs to be split
MedianKeyPointer a PB_TREE_KEY that will receive the pointer to the key in the middle of the node being split
NewRightHandSiblingPointer 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.
CaseSensitiveBoolean indicating if the function should operate in case-sensitive mode. This will be TRUE if an application created the file with the FILE_FLAG_POSIX_SEMANTICS flag.
Returns
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)
 

Macro Definition Documentation

◆ NDEBUG

#define NDEBUG

Definition at line 30 of file btree.c.

Function Documentation

◆ AllocateIndexNode()

NTSTATUS AllocateIndexNode ( PDEVICE_EXTENSION  DeviceExt,
PFILE_RECORD_HEADER  FileRecord,
ULONG  IndexBufferSize,
PNTFS_ATTR_CONTEXT  IndexAllocationCtx,
ULONG  IndexAllocationOffset,
PULONGLONG  NewVCN 
)

Definition at line 117 of file btree.c.

123{
125 PNTFS_ATTR_CONTEXT BitmapCtx;
126 ULONGLONG IndexAllocationLength, BitmapLength;
127 ULONG BitmapOffset;
128 ULONGLONG NextNodeNumber;
129 PCHAR *BitmapMem;
130 ULONG *BitmapPtr;
133 ULONG BytesNeeded;
135
136 DPRINT1("AllocateIndexNode(%p, %p, %lu, %p, %lu, %p) called.\n", DeviceExt,
137 FileRecord,
138 IndexBufferSize,
139 IndexAllocationCtx,
140 IndexAllocationOffset,
141 NewVCN);
142
143 // Get the length of the attribute allocation
144 IndexAllocationLength = AttributeDataLength(IndexAllocationCtx->pRecord);
145
146 // Find the bitmap attribute for the index
147 Status = FindAttribute(DeviceExt,
148 FileRecord,
150 L"$I30",
151 4,
152 &BitmapCtx,
153 &BitmapOffset);
154 if (!NT_SUCCESS(Status))
155 {
156 DPRINT1("FIXME: Need to add bitmap attribute!\n");
158 }
159
160 // Get the length of the bitmap attribute
161 BitmapLength = AttributeDataLength(BitmapCtx->pRecord);
162
163 NextNodeNumber = IndexAllocationLength / DeviceExt->NtfsInfo.BytesPerIndexRecord;
164
165 // TODO: Find unused allocation in bitmap and use that space first
166
167 // Add another bit to bitmap
168
169 // See how many bytes we need to store the amount of bits we'll have
170 BytesNeeded = NextNodeNumber / 8;
171 BytesNeeded++;
172
173 // Windows seems to allocate the bitmap in 8-byte chunks to keep any bytes from being wasted on padding
174 BytesNeeded = ALIGN_UP(BytesNeeded, ATTR_RECORD_ALIGNMENT);
175
176 // Allocate memory for the bitmap, including some padding; RtlInitializeBitmap() wants a pointer
177 // that's ULONG-aligned, and it wants the size of the memory allocated for it to be a ULONG-multiple.
178 BitmapMem = ExAllocatePoolWithTag(NonPagedPool, BytesNeeded + sizeof(ULONG), TAG_NTFS);
179 if (!BitmapMem)
180 {
181 DPRINT1("Error: failed to allocate bitmap!");
182 ReleaseAttributeContext(BitmapCtx);
184 }
185 // RtlInitializeBitmap() wants a pointer that's ULONG-aligned.
186 BitmapPtr = (PULONG)ALIGN_UP_BY((ULONG_PTR)BitmapMem, sizeof(ULONG));
187
188 RtlZeroMemory(BitmapPtr, BytesNeeded);
189
190 // Read the existing bitmap data
191 Status = ReadAttribute(DeviceExt, BitmapCtx, 0, (PCHAR)BitmapPtr, BitmapLength);
192
193 // Initialize bitmap
194 RtlInitializeBitMap(&Bitmap, BitmapPtr, NextNodeNumber);
195
196 // Do we need to enlarge the bitmap?
197 if (BytesNeeded > BitmapLength)
198 {
199 // TODO: handle synchronization issues that could occur from changing the directory's file record
200 // Change bitmap size
201 DataSize.QuadPart = BytesNeeded;
202 if (BitmapCtx->pRecord->IsNonResident)
203 {
205 BitmapCtx,
206 BitmapOffset,
207 FileRecord,
208 &DataSize);
209 }
210 else
211 {
213 BitmapCtx,
214 BitmapOffset,
215 FileRecord,
216 &DataSize);
217 }
218 if (!NT_SUCCESS(Status))
219 {
220 DPRINT1("ERROR: Failed to set length of bitmap attribute!\n");
221 ReleaseAttributeContext(BitmapCtx);
222 return Status;
223 }
224 }
225
226 // Enlarge Index Allocation attribute
227 DataSize.QuadPart = IndexAllocationLength + IndexBufferSize;
229 IndexAllocationCtx,
230 IndexAllocationOffset,
231 FileRecord,
232 &DataSize);
233 if (!NT_SUCCESS(Status))
234 {
235 DPRINT1("ERROR: Failed to set length of index allocation!\n");
236 ReleaseAttributeContext(BitmapCtx);
237 return Status;
238 }
239
240 // Update file record on disk
241 Status = UpdateFileRecord(DeviceExt, IndexAllocationCtx->FileMFTIndex, FileRecord);
242 if (!NT_SUCCESS(Status))
243 {
244 DPRINT1("ERROR: Failed to update file record!\n");
245 ReleaseAttributeContext(BitmapCtx);
246 return Status;
247 }
248
249 // Set the bit for the new index record
250 RtlSetBits(&Bitmap, NextNodeNumber, 1);
251
252 // Write the new bitmap attribute
253 Status = WriteAttribute(DeviceExt,
254 BitmapCtx,
255 0,
256 (const PUCHAR)BitmapPtr,
257 BytesNeeded,
259 FileRecord);
260 if (!NT_SUCCESS(Status))
261 {
262 DPRINT1("ERROR: Unable to write to $I30 bitmap attribute!\n");
263 }
264
265 // Calculate VCN of new node number
266 *NewVCN = NextNodeNumber * (IndexBufferSize / DeviceExt->NtfsInfo.BytesPerCluster);
267
268 DPRINT("New VCN: %I64u\n", *NewVCN);
269
270 ExFreePoolWithTag(BitmapMem, TAG_NTFS);
271 ReleaseAttributeContext(BitmapCtx);
272
273 return Status;
274}
#define ALIGN_UP_BY(size, align)
LONG NTSTATUS
Definition: precomp.h:26
#define DPRINT1
Definition: precomp.h:8
#define NT_SUCCESS(StatCode)
Definition: apphelp.c:32
@ AttributeBitmap
Definition: ntfs.h:171
#define TAG_NTFS
Definition: ntfs.h:12
#define ATTR_RECORD_ALIGNMENT
Definition: ntfs.h:320
#define ExAllocatePoolWithTag(hernya, size, tag)
Definition: env_spec_w32.h:350
#define NonPagedPool
Definition: env_spec_w32.h:307
Status
Definition: gdiplustypes.h:25
NTSYSAPI void WINAPI RtlInitializeBitMap(PRTL_BITMAP, PULONG, ULONG)
NTSYSAPI void WINAPI RtlSetBits(PRTL_BITMAP, ULONG, ULONG)
NTSTATUS UpdateFileRecord(PDEVICE_EXTENSION Vcb, ULONGLONG MftIndex, PFILE_RECORD_HEADER FileRecord)
Definition: mft.c:1931
VOID ReleaseAttributeContext(PNTFS_ATTR_CONTEXT Context)
Definition: mft.c:104
ULONGLONG AttributeDataLength(PNTFS_ATTR_RECORD AttrRecord)
Definition: mft.c:259
NTSTATUS FindAttribute(PDEVICE_EXTENSION Vcb, PFILE_RECORD_HEADER MftRecord, ULONG Type, PCWSTR Name, ULONG NameLength, PNTFS_ATTR_CONTEXT *AttrCtx, PULONG Offset)
Definition: mft.c:131
ULONG ReadAttribute(PDEVICE_EXTENSION Vcb, PNTFS_ATTR_CONTEXT Context, ULONGLONG Offset, PCHAR Buffer, ULONG Length)
Definition: mft.c:1065
NTSTATUS WriteAttribute(PDEVICE_EXTENSION Vcb, PNTFS_ATTR_CONTEXT Context, ULONGLONG Offset, const PUCHAR Buffer, ULONG Length, PULONG RealLengthWritten, PFILE_RECORD_HEADER FileRecord)
Definition: mft.c:1315
NTSTATUS SetNonResidentAttributeDataLength(PDEVICE_EXTENSION Vcb, PNTFS_ATTR_CONTEXT AttrContext, ULONG AttrOffset, PFILE_RECORD_HEADER FileRecord, PLARGE_INTEGER DataSize)
Definition: mft.c:756
NTSTATUS SetResidentAttributeDataLength(PDEVICE_EXTENSION Vcb, PNTFS_ATTR_CONTEXT AttrContext, ULONG AttrOffset, PFILE_RECORD_HEADER FileRecord, PLARGE_INTEGER DataSize)
Definition: mft.c:891
#define ExFreePoolWithTag(_P, _T)
Definition: module.h:1109
_In_ NDIS_STATUS _In_ ULONG _In_ USHORT _In_opt_ PVOID _In_ ULONG DataSize
Definition: ndis.h:4755
#define STATUS_NOT_IMPLEMENTED
Definition: ntstatus.h:239
#define L(x)
Definition: ntvdm.h:50
#define DPRINT
Definition: sndvol32.h:71
uint32_t * PULONG
Definition: typedefs.h:59
#define RtlZeroMemory(Destination, Length)
Definition: typedefs.h:262
uint32_t ULONG_PTR
Definition: typedefs.h:65
unsigned char * PUCHAR
Definition: typedefs.h:53
uint32_t ULONG
Definition: typedefs.h:59
uint64_t ULONGLONG
Definition: typedefs.h:67
char * PCHAR
Definition: typedefs.h:51
#define STATUS_INSUFFICIENT_RESOURCES
Definition: udferr_usr.h:158
#define ALIGN_UP(size, type)
Definition: umtypes.h:91
_Must_inspect_result_ _In_ WDFIOTARGET _In_opt_ WDFREQUEST _In_opt_ PWDF_MEMORY_DESCRIPTOR _In_opt_ PLONGLONG _In_opt_ PWDF_REQUEST_SEND_OPTIONS _Out_opt_ PULONG_PTR BytesWritten
Definition: wdfiotarget.h:960

Referenced by UpdateIndexNode().

◆ CompareTreeKeys()

LONG CompareTreeKeys ( PB_TREE_KEY  Key1,
PB_TREE_KEY  Key2,
BOOLEAN  CaseSensitive 
)

Definition at line 417 of file btree.c.

418{
419 UNICODE_STRING Key1Name, Key2Name;
420 LONG Comparison;
421
422 // Key1 must not be the final key (AKA the dummy key)
424
425 // If Key2 is the "dummy key", key 1 will always come first
426 if (Key2->NextKey == NULL)
427 return -1;
428
429 Key1Name.Buffer = Key1->IndexEntry->FileName.Name;
430 Key1Name.Length = Key1Name.MaximumLength
431 = Key1->IndexEntry->FileName.NameLength * sizeof(WCHAR);
432
433 Key2Name.Buffer = Key2->IndexEntry->FileName.Name;
434 Key2Name.Length = Key2Name.MaximumLength
435 = Key2->IndexEntry->FileName.NameLength * sizeof(WCHAR);
436
437 // Are the two keys the same length?
438 if (Key1Name.Length == Key2Name.Length)
439 return RtlCompareUnicodeString(&Key1Name, &Key2Name, !CaseSensitive);
440
441 // Is Key1 shorter?
442 if (Key1Name.Length < Key2Name.Length)
443 {
444 // Truncate KeyName2 to be the same length as KeyName1
445 Key2Name.Length = Key1Name.Length;
446
447 // Compare the names of the same length
448 Comparison = RtlCompareUnicodeString(&Key1Name, &Key2Name, !CaseSensitive);
449
450 // If the truncated names are the same length, the shorter one comes first
451 if (Comparison == 0)
452 return -1;
453 }
454 else
455 {
456 // Key2 is shorter
457 // Truncate KeyName1 to be the same length as KeyName2
458 Key1Name.Length = Key2Name.Length;
459
460 // Compare the names of the same length
461 Comparison = RtlCompareUnicodeString(&Key1Name, &Key2Name, !CaseSensitive);
462
463 // If the truncated names are the same length, the shorter one comes first
464 if (Comparison == 0)
465 return 1;
466 }
467
468 return Comparison;
469}
#define NTFS_INDEX_ENTRY_END
Definition: ntfs.h:61
#define NULL
Definition: types.h:112
ULONG RtlCompareUnicodeString(PUNICODE_STRING s1, PUNICODE_STRING s2, BOOLEAN UpCase)
Definition: string_lib.cpp:31
#define ASSERT(a)
Definition: mode.c:44
long LONG
Definition: pedump.c:60
UCHAR NameLength
Definition: ntfs.h:377
WCHAR Name[1]
Definition: ntfs.h:379
FILENAME_ATTRIBUTE FileName
Definition: ntfs.h:427
USHORT Flags
Definition: ntfs.h:425
struct _B_TREE_KEY * NextKey
Definition: ntfs.h:436
PINDEX_ENTRY_ATTRIBUTE IndexEntry
Definition: ntfs.h:438
USHORT MaximumLength
Definition: env_spec_w32.h:370
__wchar_t WCHAR
Definition: xmlstorage.h:180

Referenced by NtfsInsertKey().

◆ CountBTreeKeys()

ULONG CountBTreeKeys ( PB_TREE_KEY  FirstKey)

Definition at line 484 of file btree.c.

485{
486 ULONG Count = 0;
487 PB_TREE_KEY Current = FirstKey;
488
489 while (Current != NULL)
490 {
491 Count++;
492 Current = Current->NextKey;
493 }
494
495 return Count;
496}
int Count
Definition: noreturn.cpp:7

Referenced by SplitBTreeNode().

◆ CreateBTreeFromIndex()

NTSTATUS CreateBTreeFromIndex ( PDEVICE_EXTENSION  Vcb,
PFILE_RECORD_HEADER  FileRecordWithIndex,
PNTFS_ATTR_CONTEXT  IndexRootContext,
PINDEX_ROOT_ATTRIBUTE  IndexRoot,
PB_TREE NewTree 
)

Definition at line 682 of file btree.c.

688{
689 PINDEX_ENTRY_ATTRIBUTE CurrentNodeEntry;
693 ULONG CurrentOffset = IndexRoot->Header.FirstEntryOffset;
694 PNTFS_ATTR_CONTEXT IndexAllocationContext = NULL;
696
697 DPRINT("CreateBTreeFromIndex(%p, %p)\n", IndexRoot, NewTree);
698
699 if (!Tree || !RootNode || !CurrentKey)
700 {
701 DPRINT1("Couldn't allocate enough memory for B-Tree!\n");
702 if (Tree)
704 if (CurrentKey)
705 ExFreePoolWithTag(CurrentKey, TAG_NTFS);
706 if (RootNode)
709 }
710
711 RtlZeroMemory(Tree, sizeof(B_TREE));
713 RtlZeroMemory(CurrentKey, sizeof(B_TREE_KEY));
714
715 // See if the file record has an attribute allocation
717 FileRecordWithIndex,
719 L"$I30",
720 4,
721 &IndexAllocationContext,
722 NULL);
723 if (!NT_SUCCESS(Status))
724 IndexAllocationContext = NULL;
725
726 // Setup the Tree
727 RootNode->FirstKey = CurrentKey;
728 Tree->RootNode = RootNode;
729
730 // Make sure we won't try reading past the attribute-end
731 if (FIELD_OFFSET(INDEX_ROOT_ATTRIBUTE, Header) + IndexRoot->Header.TotalSizeOfEntries > IndexRootContext->pRecord->Resident.ValueLength)
732 {
733 DPRINT1("Filesystem corruption detected!\n");
736 goto Cleanup;
737 }
738
739 // Start at the first node entry
740 CurrentNodeEntry = (PINDEX_ENTRY_ATTRIBUTE)((ULONG_PTR)IndexRoot
742 + IndexRoot->Header.FirstEntryOffset);
743
744 // Create a key for each entry in the node
745 while (CurrentOffset < IndexRoot->Header.TotalSizeOfEntries)
746 {
747 // Allocate memory for the current entry
748 CurrentKey->IndexEntry = ExAllocatePoolWithTag(NonPagedPool, CurrentNodeEntry->Length, TAG_NTFS);
749 if (!CurrentKey->IndexEntry)
750 {
751 DPRINT1("ERROR: Couldn't allocate memory for next key!\n");
754 goto Cleanup;
755 }
756
757 RootNode->KeyCount++;
758
759 // If this isn't the last entry
760 if (!(CurrentNodeEntry->Flags & NTFS_INDEX_ENTRY_END))
761 {
762 // Create the next key
764 if (!NextKey)
765 {
766 DPRINT1("ERROR: Couldn't allocate memory for next key!\n");
769 goto Cleanup;
770 }
771
772 RtlZeroMemory(NextKey, sizeof(B_TREE_KEY));
773
774 // Add NextKey to the end of the list
775 CurrentKey->NextKey = NextKey;
776
777 // Copy the current entry to its key
778 RtlCopyMemory(CurrentKey->IndexEntry, CurrentNodeEntry, CurrentNodeEntry->Length);
779
780 // Does this key have a sub-node?
781 if (CurrentKey->IndexEntry->Flags & NTFS_INDEX_ENTRY_NODE)
782 {
783 // Create the child node
785 IndexRoot,
786 IndexAllocationContext,
787 CurrentKey->IndexEntry);
788 if (!CurrentKey->LesserChild)
789 {
790 DPRINT1("ERROR: Couldn't create child node!\n");
793 goto Cleanup;
794 }
795 }
796
797 // Advance to the next entry
798 CurrentOffset += CurrentNodeEntry->Length;
799 CurrentNodeEntry = (PINDEX_ENTRY_ATTRIBUTE)((ULONG_PTR)CurrentNodeEntry + CurrentNodeEntry->Length);
800 CurrentKey = NextKey;
801 }
802 else
803 {
804 // Copy the final entry to its key
805 RtlCopyMemory(CurrentKey->IndexEntry, CurrentNodeEntry, CurrentNodeEntry->Length);
806 CurrentKey->NextKey = NULL;
807
808 // Does this key have a sub-node?
809 if (CurrentKey->IndexEntry->Flags & NTFS_INDEX_ENTRY_NODE)
810 {
811 // Create the child node
813 IndexRoot,
814 IndexAllocationContext,
815 CurrentKey->IndexEntry);
816 if (!CurrentKey->LesserChild)
817 {
818 DPRINT1("ERROR: Couldn't create child node!\n");
821 goto Cleanup;
822 }
823 }
824
825 break;
826 }
827 }
828
829 *NewTree = Tree;
831
832Cleanup:
833 if (IndexAllocationContext)
834 ReleaseAttributeContext(IndexAllocationContext);
835
836 return Status;
837}
CRegistryTree Tree
#define NTFS_INDEX_ENTRY_NODE
Definition: ntfs.h:60
PB_TREE_FILENAME_NODE CreateBTreeNodeFromIndexNode(PDEVICE_EXTENSION Vcb, PINDEX_ROOT_ATTRIBUTE IndexRoot, PNTFS_ATTR_CONTEXT IndexAllocationAttributeCtx, PINDEX_ENTRY_ATTRIBUTE NodeEntry)
Definition: btree.c:499
VOID DestroyBTree(PB_TREE Tree)
Definition: btree.c:1542
Definition: Header.h:9
static const WCHAR Cleanup[]
Definition: register.c:80
struct INDEX_ENTRY_ATTRIBUTE * PINDEX_ENTRY_ATTRIBUTE
@ AttributeIndexAllocation
Definition: ntfs.h:170
PCONFIGURATION_COMPONENT_DATA RootNode
Definition: macharm.c:19
#define Vcb
Definition: cdprocs.h:1415
#define STATUS_SUCCESS
Definition: shellext.h:65
Definition: ntfs.h:454
Definition: ntfs.h:409
USHORT Length
Definition: ntfs.h:423
ULONG FirstEntryOffset
Definition: ntfs.h:384
ULONG TotalSizeOfEntries
Definition: ntfs.h:385
INDEX_HEADER_ATTRIBUTE Header
Definition: ntfs.h:398
B_TREE_FILENAME_NODE * LesserChild
Definition: ntfs.h:437
#define FIELD_OFFSET(t, f)
Definition: typedefs.h:255
#define RtlCopyMemory(Destination, Source, Length)
Definition: typedefs.h:263
#define STATUS_FILE_CORRUPT_ERROR
Definition: udferr_usr.h:168

Referenced by NtfsAddFilenameToDirectory().

◆ CreateBTreeKeyFromFilename()

PB_TREE_KEY CreateBTreeKeyFromFilename ( ULONGLONG  FileReference,
PFILENAME_ATTRIBUTE  FileNameAttribute 
)

Definition at line 1461 of file btree.c.

1462{
1463 PB_TREE_KEY NewKey;
1464 ULONG AttributeSize = GetFileNameAttributeLength(FileNameAttribute);
1466
1467 // Create a new Index Entry for the file
1469 if (!NewEntry)
1470 {
1471 DPRINT1("ERROR: Failed to allocate memory for Index Entry!\n");
1472 return NULL;
1473 }
1474
1475 // Setup the Index Entry
1476 RtlZeroMemory(NewEntry, EntrySize);
1477 NewEntry->Data.Directory.IndexedFile = FileReference;
1478 NewEntry->Length = EntrySize;
1479 NewEntry->KeyLength = AttributeSize;
1480
1481 // Copy the FileNameAttribute
1482 RtlCopyMemory(&NewEntry->FileName, FileNameAttribute, AttributeSize);
1483
1484 // Setup the New Key
1486 if (!NewKey)
1487 {
1488 DPRINT1("ERROR: Failed to allocate memory for new key!\n");
1489 ExFreePoolWithTag(NewEntry, TAG_NTFS);
1490 return NULL;
1491 }
1492 NewKey->IndexEntry = NewEntry;
1493 NewKey->NextKey = NULL;
1494
1495 return NewKey;
1496}
ULONG GetFileNameAttributeLength(PFILENAME_ATTRIBUTE FileNameAttribute)
Definition: attrib.c:1978
struct INDEX_ENTRY_ATTRIBUTE::@763::@764 Directory
USHORT KeyLength
Definition: ntfs.h:424
union INDEX_ENTRY_ATTRIBUTE::@763 Data
_In_ UCHAR EntrySize
Definition: iofuncs.h:642

Referenced by NtfsInsertKey().

◆ CreateBTreeNodeFromIndexNode()

PB_TREE_FILENAME_NODE CreateBTreeNodeFromIndexNode ( PDEVICE_EXTENSION  Vcb,
PINDEX_ROOT_ATTRIBUTE  IndexRoot,
PNTFS_ATTR_CONTEXT  IndexAllocationAttributeCtx,
PINDEX_ENTRY_ATTRIBUTE  NodeEntry 
)

Definition at line 499 of file btree.c.

503{
504 PB_TREE_FILENAME_NODE NewNode;
505 PINDEX_ENTRY_ATTRIBUTE CurrentNodeEntry;
506 PINDEX_ENTRY_ATTRIBUTE FirstNodeEntry;
507 ULONG CurrentEntryOffset = 0;
508 PINDEX_BUFFER NodeBuffer;
509 ULONG IndexBufferSize = Vcb->NtfsInfo.BytesPerIndexRecord;
510 PULONGLONG VCN;
511 PB_TREE_KEY CurrentKey;
513 ULONGLONG IndexNodeOffset;
515
516 if (IndexAllocationAttributeCtx == NULL)
517 {
518 DPRINT1("ERROR: Couldn't find index allocation attribute even though there should be one!\n");
519 return NULL;
520 }
521
522 // Get the node number from the end of the node entry
523 VCN = (PULONGLONG)((ULONG_PTR)NodeEntry + NodeEntry->Length - sizeof(ULONGLONG));
524
525 // Create the new tree node
527 if (!NewNode)
528 {
529 DPRINT1("ERROR: Couldn't allocate memory for new filename node.\n");
530 return NULL;
531 }
532 RtlZeroMemory(NewNode, sizeof(B_TREE_FILENAME_NODE));
533
534 // Create the first key
536 if (!CurrentKey)
537 {
538 DPRINT1("ERROR: Failed to allocate memory for key!\n");
539 ExFreePoolWithTag(NewNode, TAG_NTFS);
540 return NULL;
541 }
542 RtlZeroMemory(CurrentKey, sizeof(B_TREE_KEY));
543 NewNode->FirstKey = CurrentKey;
544
545 // Allocate memory for the node buffer
546 NodeBuffer = ExAllocatePoolWithTag(NonPagedPool, IndexBufferSize, TAG_NTFS);
547 if (!NodeBuffer)
548 {
549 DPRINT1("ERROR: Couldn't allocate memory for node buffer!\n");
550 ExFreePoolWithTag(CurrentKey, TAG_NTFS);
551 ExFreePoolWithTag(NewNode, TAG_NTFS);
552 return NULL;
553 }
554
555 // Calculate offset into index allocation
556 IndexNodeOffset = GetAllocationOffsetFromVCN(Vcb, IndexBufferSize, *VCN);
557
558 // TODO: Confirm index bitmap has this node marked as in-use
559
560 // Read the node
562 IndexAllocationAttributeCtx,
563 IndexNodeOffset,
564 (PCHAR)NodeBuffer,
565 IndexBufferSize);
566
567 ASSERT(BytesRead == IndexBufferSize);
568 NT_ASSERT(NodeBuffer->Ntfs.Type == NRH_INDX_TYPE);
569 NT_ASSERT(NodeBuffer->VCN == *VCN);
570
571 // Apply the fixup array to the node buffer
572 Status = FixupUpdateSequenceArray(Vcb, &NodeBuffer->Ntfs);
573 if (!NT_SUCCESS(Status))
574 {
575 DPRINT1("ERROR: Couldn't apply fixup array to index node buffer!\n");
576 ExFreePoolWithTag(NodeBuffer, TAG_NTFS);
577 ExFreePoolWithTag(CurrentKey, TAG_NTFS);
578 ExFreePoolWithTag(NewNode, TAG_NTFS);
579 return NULL;
580 }
581
582 // Walk through the index and create keys for all the entries
583 FirstNodeEntry = (PINDEX_ENTRY_ATTRIBUTE)((ULONG_PTR)(&NodeBuffer->Header)
584 + NodeBuffer->Header.FirstEntryOffset);
585 CurrentNodeEntry = FirstNodeEntry;
586 while (CurrentEntryOffset < NodeBuffer->Header.TotalSizeOfEntries)
587 {
588 // Allocate memory for the current entry
589 CurrentKey->IndexEntry = ExAllocatePoolWithTag(NonPagedPool, CurrentNodeEntry->Length, TAG_NTFS);
590 if (!CurrentKey->IndexEntry)
591 {
592 DPRINT1("ERROR: Couldn't allocate memory for next key!\n");
593 DestroyBTreeNode(NewNode);
594 ExFreePoolWithTag(NodeBuffer, TAG_NTFS);
595 return NULL;
596 }
597
598 NewNode->KeyCount++;
599
600 // If this isn't the last entry
601 if (!(CurrentNodeEntry->Flags & NTFS_INDEX_ENTRY_END))
602 {
603 // Create the next key
605 if (!NextKey)
606 {
607 DPRINT1("ERROR: Couldn't allocate memory for next key!\n");
608 DestroyBTreeNode(NewNode);
609 ExFreePoolWithTag(NodeBuffer, TAG_NTFS);
610 return NULL;
611 }
612 RtlZeroMemory(NextKey, sizeof(B_TREE_KEY));
613
614 // Add NextKey to the end of the list
615 CurrentKey->NextKey = NextKey;
616
617 // Copy the current entry to its key
618 RtlCopyMemory(CurrentKey->IndexEntry, CurrentNodeEntry, CurrentNodeEntry->Length);
619
620 // See if the current key has a sub-node
621 if (CurrentKey->IndexEntry->Flags & NTFS_INDEX_ENTRY_NODE)
622 {
624 IndexRoot,
625 IndexAllocationAttributeCtx,
626 CurrentKey->IndexEntry);
627 }
628
629 CurrentKey = NextKey;
630 }
631 else
632 {
633 // Copy the final entry to its key
634 RtlCopyMemory(CurrentKey->IndexEntry, CurrentNodeEntry, CurrentNodeEntry->Length);
635 CurrentKey->NextKey = NULL;
636
637 // See if the current key has a sub-node
638 if (CurrentKey->IndexEntry->Flags & NTFS_INDEX_ENTRY_NODE)
639 {
641 IndexRoot,
642 IndexAllocationAttributeCtx,
643 CurrentKey->IndexEntry);
644 }
645
646 break;
647 }
648
649 // Advance to the next entry
650 CurrentEntryOffset += CurrentNodeEntry->Length;
651 CurrentNodeEntry = (PINDEX_ENTRY_ATTRIBUTE)((ULONG_PTR)CurrentNodeEntry + CurrentNodeEntry->Length);
652 }
653
654 NewNode->VCN = *VCN;
655 NewNode->HasValidVCN = TRUE;
656
657 ExFreePoolWithTag(NodeBuffer, TAG_NTFS);
658
659 return NewNode;
660}
VOID DestroyBTreeNode(PB_TREE_FILENAME_NODE Node)
Definition: btree.c:1511
ULONGLONG GetAllocationOffsetFromVCN(PDEVICE_EXTENSION DeviceExt, ULONG IndexBufferSize, ULONGLONG Vcn)
Definition: btree.c:1630
#define TRUE
Definition: types.h:120
#define NRH_INDX_TYPE
Definition: ntfs.h:247
NTSTATUS FixupUpdateSequenceArray(PDEVICE_EXTENSION Vcb, PNTFS_RECORD_HEADER Record)
Definition: mft.c:1965
__GNU_EXTENSION typedef unsigned __int64 * PULONGLONG
Definition: ntbasedef.h:383
INDEX_HEADER_ATTRIBUTE Header
Definition: ntfs.h:405
ULONGLONG VCN
Definition: ntfs.h:404
NTFS_RECORD_HEADER Ntfs
Definition: ntfs.h:403
ULONGLONG VCN
Definition: ntfs.h:449
BOOLEAN HasValidVCN
Definition: ntfs.h:447
PB_TREE_KEY FirstKey
Definition: ntfs.h:450
_Must_inspect_result_ _In_ WDFIOTARGET _In_opt_ WDFREQUEST _In_opt_ PWDF_MEMORY_DESCRIPTOR _In_opt_ PLONGLONG _In_opt_ PWDF_REQUEST_SEND_OPTIONS _Out_opt_ PULONG_PTR BytesRead
Definition: wdfiotarget.h:870
#define NT_ASSERT
Definition: rtlfuncs.h:3310

Referenced by CreateBTreeFromIndex(), and CreateBTreeNodeFromIndexNode().

◆ CreateDummyKey()

PB_TREE_KEY CreateDummyKey ( BOOLEAN  HasChildNode)

Definition at line 289 of file btree.c.

290{
291 PINDEX_ENTRY_ATTRIBUTE NewIndexEntry;
292 PB_TREE_KEY NewDummyKey;
293
294 // Calculate max size of a dummy key
296 EntrySize += sizeof(ULONGLONG); // for VCN
297
298 // Create the index entry for the key
300 if (!NewIndexEntry)
301 {
302 DPRINT1("Couldn't allocate memory for dummy key index entry!\n");
303 return NULL;
304 }
305
306 RtlZeroMemory(NewIndexEntry, EntrySize);
307
308 if (HasChildNode)
309 {
311 }
312 else
313 {
314 NewIndexEntry->Flags = NTFS_INDEX_ENTRY_END;
315 EntrySize -= sizeof(ULONGLONG); // no VCN
316 }
317
318 NewIndexEntry->Length = EntrySize;
319
320 // Create the key
321 NewDummyKey = ExAllocatePoolWithTag(NonPagedPool, sizeof(B_TREE_KEY), TAG_NTFS);
322 if (!NewDummyKey)
323 {
324 DPRINT1("Unable to allocate dummy key!\n");
325 ExFreePoolWithTag(NewIndexEntry, TAG_NTFS);
326 return NULL;
327 }
328 RtlZeroMemory(NewDummyKey, sizeof(B_TREE_KEY));
329
330 NewDummyKey->IndexEntry = NewIndexEntry;
331
332 return NewDummyKey;
333}

Referenced by CreateEmptyBTree(), DemoteBTreeRoot(), and SplitBTreeNode().

◆ CreateEmptyBTree()

NTSTATUS CreateEmptyBTree ( PB_TREE NewTree)

Definition at line 348 of file btree.c.

349{
352 PB_TREE_KEY DummyKey;
353
354 DPRINT1("CreateEmptyBTree(%p) called\n", NewTree);
355
356 if (!Tree || !RootNode)
357 {
358 DPRINT1("Couldn't allocate enough memory for B-Tree!\n");
359 if (Tree)
361 if (RootNode)
364 }
365
366 // Create the dummy key
367 DummyKey = CreateDummyKey(FALSE);
368 if (!DummyKey)
369 {
370 DPRINT1("ERROR: Failed to create dummy key!\n");
374 }
375
376 RtlZeroMemory(Tree, sizeof(B_TREE));
378
379 // Setup the Tree
380 RootNode->FirstKey = DummyKey;
381 RootNode->KeyCount = 1;
382 RootNode->DiskNeedsUpdating = TRUE;
383 Tree->RootNode = RootNode;
384
385 *NewTree = Tree;
386
387 // Memory will be freed when DestroyBTree() is called
388
389 return STATUS_SUCCESS;
390}
PB_TREE_KEY CreateDummyKey(BOOLEAN HasChildNode)
Definition: btree.c:289
#define FALSE
Definition: types.h:117

Referenced by NtfsCreateDirectory().

◆ CreateIndexBufferFromBTreeNode()

NTSTATUS CreateIndexBufferFromBTreeNode ( PDEVICE_EXTENSION  DeviceExt,
PB_TREE_FILENAME_NODE  Node,
ULONG  BufferSize,
BOOLEAN  HasChildren,
PINDEX_BUFFER  IndexBuffer 
)

Definition at line 1001 of file btree.c.

1006{
1007 ULONG i;
1008 PB_TREE_KEY CurrentKey;
1009 PINDEX_ENTRY_ATTRIBUTE CurrentNodeEntry;
1011
1012 // TODO: Fix magic, do math
1013 RtlZeroMemory(IndexBuffer, BufferSize);
1014 IndexBuffer->Ntfs.Type = NRH_INDX_TYPE;
1015 IndexBuffer->Ntfs.UsaOffset = 0x28;
1016 IndexBuffer->Ntfs.UsaCount = 9;
1017
1018 // TODO: Check bitmap for VCN
1019 ASSERT(Node->HasValidVCN);
1020 IndexBuffer->VCN = Node->VCN;
1021
1022 // Windows seems to alternate between using 0x28 and 0x40 for the first entry offset of each index buffer.
1023 // Interestingly, neither Windows nor chkdsk seem to mind if we just use 0x28 for every index record.
1024 IndexBuffer->Header.FirstEntryOffset = 0x28;
1026
1027 // Start summing the total size of this node's entries
1028 IndexBuffer->Header.TotalSizeOfEntries = IndexBuffer->Header.FirstEntryOffset;
1029
1030 CurrentKey = Node->FirstKey;
1031 CurrentNodeEntry = (PINDEX_ENTRY_ATTRIBUTE)((ULONG_PTR)&(IndexBuffer->Header)
1032 + IndexBuffer->Header.FirstEntryOffset);
1033 for (i = 0; i < Node->KeyCount; i++)
1034 {
1035 // Would adding the current entry to the index increase the node size beyond the allocation size?
1037 + IndexBuffer->Header.TotalSizeOfEntries
1038 + CurrentNodeEntry->Length;
1039 if (IndexSize > BufferSize)
1040 {
1041 DPRINT1("TODO: Adding file would require creating a new node!\n");
1043 }
1044
1045 ASSERT(CurrentKey->IndexEntry->Length != 0);
1046
1047 // Copy the index entry
1048 RtlCopyMemory(CurrentNodeEntry, CurrentKey->IndexEntry, CurrentKey->IndexEntry->Length);
1049
1050 DPRINT("Index Node Entry Stream Length: %u\nIndex Node Entry Length: %u\n",
1051 CurrentNodeEntry->KeyLength,
1052 CurrentNodeEntry->Length);
1053
1054 // Add Length of Current Entry to Total Size of Entries
1055 IndexBuffer->Header.TotalSizeOfEntries += CurrentNodeEntry->Length;
1056
1057 // Check for child nodes
1058 if (HasChildren)
1059 IndexBuffer->Header.Flags = INDEX_NODE_LARGE;
1060
1061 // Go to the next node entry
1062 CurrentNodeEntry = (PINDEX_ENTRY_ATTRIBUTE)((ULONG_PTR)CurrentNodeEntry + CurrentNodeEntry->Length);
1063 CurrentKey = CurrentKey->NextKey;
1064 }
1065
1066 Status = AddFixupArray(DeviceExt, &IndexBuffer->Ntfs);
1067
1068 return Status;
1069}
#define INDEX_NODE_LARGE
Definition: ntfs.h:212
GLsizei GLenum const GLvoid GLsizei GLenum GLbyte GLbyte GLbyte GLdouble GLdouble GLdouble GLfloat GLfloat GLfloat GLint GLint GLint GLshort GLshort GLshort GLubyte GLubyte GLubyte GLuint GLuint GLuint GLushort GLushort GLushort GLbyte GLbyte GLbyte GLbyte GLdouble GLdouble GLdouble GLdouble GLfloat GLfloat GLfloat GLfloat GLint GLint GLint GLint GLshort GLshort GLshort GLshort GLubyte GLubyte GLubyte GLubyte GLuint GLuint GLuint GLuint GLushort GLushort GLushort GLushort GLboolean const GLdouble const GLfloat const GLint const GLshort const GLbyte const GLdouble const GLfloat const GLint const GLshort const GLdouble const GLfloat const GLint const GLshort const GLdouble const GLfloat const GLint const GLshort const GLdouble const GLfloat const GLint const GLshort const GLdouble const GLdouble const GLfloat const GLfloat const GLint const GLint const GLshort const GLshort const GLdouble const GLfloat const GLint const GLshort const GLdouble const GLfloat const GLint const GLshort const GLdouble const GLfloat const GLint const GLshort const GLdouble const GLfloat const GLint const GLshort const GLdouble const GLfloat const GLint const GLshort const GLdouble const GLfloat const GLint const GLshort const GLdouble const GLfloat const GLint const GLshort GLenum GLenum GLenum GLfloat GLenum GLint GLenum GLenum GLenum GLfloat GLenum GLenum GLint GLenum GLfloat GLenum GLint GLint GLushort GLenum GLenum GLfloat GLenum GLenum GLint GLfloat const GLubyte GLenum GLenum GLenum const GLfloat GLenum GLenum const GLint GLenum GLint GLint GLsizei GLsizei GLint GLenum GLenum const GLvoid GLenum GLenum const GLfloat GLenum GLenum const GLint GLenum GLenum const GLdouble GLenum GLenum const GLfloat GLenum GLenum const GLint GLsizei GLuint GLfloat GLuint GLbitfield GLfloat GLint GLuint GLboolean GLenum GLfloat GLenum GLbitfield GLenum GLfloat GLfloat GLint GLint const GLfloat GLenum GLfloat GLfloat GLint GLint GLfloat GLfloat GLint GLint const GLfloat GLint GLfloat GLfloat GLint GLfloat GLfloat GLint GLfloat GLfloat const GLdouble const GLfloat const GLdouble const GLfloat GLint i
Definition: glfuncs.h:248
NTSTATUS AddFixupArray(PDEVICE_EXTENSION Vcb, PNTFS_RECORD_HEADER Record)
Definition: mft.c:2603
USHORT UsaCount
Definition: ntfs.h:241
USHORT UsaOffset
Definition: ntfs.h:240
Definition: dlist.c:348
_In_ WDFMEMORY _Out_opt_ size_t * BufferSize
Definition: wdfmemory.h:254

Referenced by UpdateIndexNode().

◆ CreateIndexRootFromBTree()

NTSTATUS CreateIndexRootFromBTree ( PDEVICE_EXTENSION  DeviceExt,
PB_TREE  Tree,
ULONG  MaxIndexSize,
PINDEX_ROOT_ATTRIBUTE IndexRoot,
ULONG Length 
)

Definition at line 910 of file btree.c.

915{
916 ULONG i;
917 PB_TREE_KEY CurrentKey;
918 PINDEX_ENTRY_ATTRIBUTE CurrentNodeEntry;
920 DeviceExt->NtfsInfo.BytesPerFileRecord,
921 TAG_NTFS);
922
923 DPRINT("CreateIndexRootFromBTree(%p, %p, 0x%lx, %p, %p)\n", DeviceExt, Tree, MaxIndexSize, IndexRoot, Length);
924
925#ifndef NDEBUG
927#endif
928
929 if (!NewIndexRoot)
930 {
931 DPRINT1("Failed to allocate memory for Index Root!\n");
933 }
934
935 // Setup the new index root
936 RtlZeroMemory(NewIndexRoot, DeviceExt->NtfsInfo.BytesPerFileRecord);
937
938 NewIndexRoot->AttributeType = AttributeFileName;
939 NewIndexRoot->CollationRule = COLLATION_FILE_NAME;
940 NewIndexRoot->SizeOfEntry = DeviceExt->NtfsInfo.BytesPerIndexRecord;
941 // If Bytes per index record is less than cluster size, clusters per index record becomes sectors per index
942 if (NewIndexRoot->SizeOfEntry < DeviceExt->NtfsInfo.BytesPerCluster)
943 NewIndexRoot->ClustersPerIndexRecord = NewIndexRoot->SizeOfEntry / DeviceExt->NtfsInfo.BytesPerSector;
944 else
945 NewIndexRoot->ClustersPerIndexRecord = NewIndexRoot->SizeOfEntry / DeviceExt->NtfsInfo.BytesPerCluster;
946
947 // Setup the Index node header
948 NewIndexRoot->Header.FirstEntryOffset = sizeof(INDEX_HEADER_ATTRIBUTE);
949 NewIndexRoot->Header.Flags = INDEX_ROOT_SMALL;
950
951 // Start summing the total size of this node's entries
952 NewIndexRoot->Header.TotalSizeOfEntries = NewIndexRoot->Header.FirstEntryOffset;
953
954 // Setup each Node Entry
955 CurrentKey = Tree->RootNode->FirstKey;
956 CurrentNodeEntry = (PINDEX_ENTRY_ATTRIBUTE)((ULONG_PTR)NewIndexRoot
958 + NewIndexRoot->Header.FirstEntryOffset);
959 for (i = 0; i < Tree->RootNode->KeyCount; i++)
960 {
961 // Would adding the current entry to the index increase the index size beyond the limit we've set?
962 ULONG IndexSize = NewIndexRoot->Header.TotalSizeOfEntries - NewIndexRoot->Header.FirstEntryOffset + CurrentKey->IndexEntry->Length;
963 if (IndexSize > MaxIndexSize)
964 {
965 DPRINT1("TODO: Adding file would require creating an attribute list!\n");
966 ExFreePoolWithTag(NewIndexRoot, TAG_NTFS);
968 }
969
970 ASSERT(CurrentKey->IndexEntry->Length != 0);
971
972 // Copy the index entry
973 RtlCopyMemory(CurrentNodeEntry, CurrentKey->IndexEntry, CurrentKey->IndexEntry->Length);
974
975 DPRINT1("Index Node Entry Stream Length: %u\nIndex Node Entry Length: %u\n",
976 CurrentNodeEntry->KeyLength,
977 CurrentNodeEntry->Length);
978
979 // Does the current key have any sub-nodes?
980 if (CurrentKey->LesserChild)
981 NewIndexRoot->Header.Flags = INDEX_ROOT_LARGE;
982
983 // Add Length of Current Entry to Total Size of Entries
984 NewIndexRoot->Header.TotalSizeOfEntries += CurrentKey->IndexEntry->Length;
985
986 // Go to the next node entry
987 CurrentNodeEntry = (PINDEX_ENTRY_ATTRIBUTE)((ULONG_PTR)CurrentNodeEntry + CurrentNodeEntry->Length);
988
989 CurrentKey = CurrentKey->NextKey;
990 }
991
992 NewIndexRoot->Header.AllocatedSize = NewIndexRoot->Header.TotalSizeOfEntries;
993
994 *IndexRoot = NewIndexRoot;
996
997 return STATUS_SUCCESS;
998}
VOID DumpBTree(PB_TREE Tree)
Definition: btree.c:1622
#define INDEX_ROOT_SMALL
Definition: ntfs.h:208
#define COLLATION_FILE_NAME
Definition: ntfs.h:201
#define INDEX_ROOT_LARGE
Definition: ntfs.h:209
@ AttributeFileName
Definition: ntfs.h:163
_In_ ULONG _In_ ULONG _In_ ULONG Length
Definition: ntddpcm.h:102
ULONG AttributeType
Definition: ntfs.h:393
ULONG CollationRule
Definition: ntfs.h:394
UCHAR ClustersPerIndexRecord
Definition: ntfs.h:396
ULONG SizeOfEntry
Definition: ntfs.h:395

Referenced by NtfsAddFilenameToDirectory(), and NtfsCreateDirectory().

◆ DemoteBTreeRoot()

NTSTATUS DemoteBTreeRoot ( PB_TREE  Tree)

Definition at line 1089 of file btree.c.

1090{
1091 PB_TREE_FILENAME_NODE NewSubNode, NewIndexRoot;
1092 PB_TREE_KEY DummyKey;
1093
1094 DPRINT("Collapsing Index Root into sub-node.\n");
1095
1096#ifndef NDEBUG
1097 DumpBTree(Tree);
1098#endif
1099
1100 // Create a new node that will hold the keys currently in index root
1102 if (!NewSubNode)
1103 {
1104 DPRINT1("ERROR: Couldn't allocate memory for new sub-node.\n");
1106 }
1107 RtlZeroMemory(NewSubNode, sizeof(B_TREE_FILENAME_NODE));
1108
1109 // Copy the applicable data from the old index root node
1110 NewSubNode->KeyCount = Tree->RootNode->KeyCount;
1111 NewSubNode->FirstKey = Tree->RootNode->FirstKey;
1112 NewSubNode->DiskNeedsUpdating = TRUE;
1113
1114 // Create a new dummy key, and make the new node it's child
1115 DummyKey = CreateDummyKey(TRUE);
1116 if (!DummyKey)
1117 {
1118 DPRINT1("ERROR: Couldn't allocate memory for new root node.\n");
1119 ExFreePoolWithTag(NewSubNode, TAG_NTFS);
1121 }
1122
1123 // Make the new node a child of the dummy key
1124 DummyKey->LesserChild = NewSubNode;
1125
1126 // Create a new index root node
1128 if (!NewIndexRoot)
1129 {
1130 DPRINT1("ERROR: Couldn't allocate memory for new index root.\n");
1131 ExFreePoolWithTag(NewSubNode, TAG_NTFS);
1132 ExFreePoolWithTag(DummyKey, TAG_NTFS);
1134 }
1135 RtlZeroMemory(NewIndexRoot, sizeof(B_TREE_FILENAME_NODE));
1136
1137 NewIndexRoot->DiskNeedsUpdating = TRUE;
1138
1139 // Insert the dummy key into the new node
1140 NewIndexRoot->FirstKey = DummyKey;
1141 NewIndexRoot->KeyCount = 1;
1142 NewIndexRoot->DiskNeedsUpdating = TRUE;
1143
1144 // Make the new node the Tree's root node
1145 Tree->RootNode = NewIndexRoot;
1146
1147#ifndef NDEBUG
1148 DumpBTree(Tree);
1149#endif
1150
1151 return STATUS_SUCCESS;
1152}
BOOLEAN DiskNeedsUpdating
Definition: ntfs.h:448

Referenced by NtfsAddFilenameToDirectory().

◆ DestroyBTree()

VOID DestroyBTree ( PB_TREE  Tree)

Definition at line 1542 of file btree.c.

1543{
1544 DestroyBTreeNode(Tree->RootNode);
1546}

Referenced by CreateBTreeFromIndex(), NtfsAddFilenameToDirectory(), and NtfsCreateDirectory().

◆ DestroyBTreeKey()

VOID DestroyBTreeKey ( PB_TREE_KEY  Key)

Definition at line 1499 of file btree.c.

1500{
1501 if (Key->IndexEntry)
1502 ExFreePoolWithTag(Key->IndexEntry, TAG_NTFS);
1503
1504 if (Key->LesserChild)
1505 DestroyBTreeNode(Key->LesserChild);
1506
1508}

Referenced by DestroyBTreeNode().

◆ DestroyBTreeNode()

VOID DestroyBTreeNode ( PB_TREE_FILENAME_NODE  Node)

Definition at line 1511 of file btree.c.

1512{
1513 PB_TREE_KEY NextKey;
1514 PB_TREE_KEY CurrentKey = Node->FirstKey;
1515 ULONG i;
1516 for (i = 0; i < Node->KeyCount; i++)
1517 {
1518 NT_ASSERT(CurrentKey);
1519 NextKey = CurrentKey->NextKey;
1520 DestroyBTreeKey(CurrentKey);
1521 CurrentKey = NextKey;
1522 }
1523
1524 NT_ASSERT(NextKey == NULL);
1525
1527}
VOID DestroyBTreeKey(PB_TREE_KEY Key)
Definition: btree.c:1499

Referenced by CreateBTreeNodeFromIndexNode(), DestroyBTree(), and DestroyBTreeKey().

◆ DumpBTree()

VOID DumpBTree ( PB_TREE  Tree)

Definition at line 1622 of file btree.c.

1623{
1624 DbgPrint("B_TREE @ %p\n", Tree);
1625 DumpBTreeNode(Tree, Tree->RootNode, 0, 0);
1626}
VOID DumpBTreeNode(PB_TREE Tree, PB_TREE_FILENAME_NODE Node, ULONG Number, ULONG Depth)
Definition: btree.c:1583
#define DbgPrint
Definition: hal.h:12

Referenced by CreateIndexRootFromBTree(), DemoteBTreeRoot(), NtfsAddFilenameToDirectory(), NtfsInsertKey(), and UpdateIndexAllocation().

◆ DumpBTreeKey()

VOID DumpBTreeKey ( PB_TREE  Tree,
PB_TREE_KEY  Key,
ULONG  Number,
ULONG  Depth 
)

Definition at line 1549 of file btree.c.

1550{
1551 ULONG i;
1552 for (i = 0; i < Depth; i++)
1553 DbgPrint(" ");
1554 DbgPrint(" Key #%d", Number);
1555
1556 if (!(Key->IndexEntry->Flags & NTFS_INDEX_ENTRY_END))
1557 {
1559 FileName.Length = Key->IndexEntry->FileName.NameLength * sizeof(WCHAR);
1560 FileName.MaximumLength = FileName.Length;
1561 FileName.Buffer = Key->IndexEntry->FileName.Name;
1562 DbgPrint(" '%wZ'\n", &FileName);
1563 }
1564 else
1565 {
1566 DbgPrint(" (Dummy Key)\n");
1567 }
1568
1569 // Is there a child node?
1570 if (Key->IndexEntry->Flags & NTFS_INDEX_ENTRY_NODE)
1571 {
1572 if (Key->LesserChild)
1573 DumpBTreeNode(Tree, Key->LesserChild, Number, Depth + 1);
1574 else
1575 {
1576 // This will be an assert once nodes with arbitrary depth are debugged
1577 DPRINT1("DRIVER ERROR: No Key->LesserChild despite Key->IndexEntry->Flags indicating this is a node!\n");
1578 }
1579 }
1580}
struct _FileName FileName
Definition: fatprocs.h:896
_In_opt_ PENTER_STATE_SYSTEM_HANDLER _In_opt_ PVOID _In_ LONG _In_opt_ LONG volatile * Number
Definition: ntpoapi.h:207
_In_opt_ PALLOCATE_FUNCTION _In_opt_ PFREE_FUNCTION _In_ ULONG _In_ SIZE_T _In_ ULONG _In_ USHORT Depth
Definition: exfuncs.h:819

Referenced by DumpBTreeNode().

◆ DumpBTreeNode()

VOID DumpBTreeNode ( PB_TREE  Tree,
PB_TREE_FILENAME_NODE  Node,
ULONG  Number,
ULONG  Depth 
)

Definition at line 1583 of file btree.c.

1587{
1588 PB_TREE_KEY CurrentKey;
1589 ULONG i;
1590 for (i = 0; i < Depth; i++)
1591 DbgPrint(" ");
1592 DbgPrint("Node #%d, Depth %d, has %d key%s", Number, Depth, Node->KeyCount, Node->KeyCount == 1 ? "" : "s");
1593
1594 if (Node->HasValidVCN)
1595 DbgPrint(" VCN: %I64u\n", Node->VCN);
1596 else if (Tree->RootNode == Node)
1597 DbgPrint(" Index Root");
1598 else
1599 DbgPrint(" NOT ASSIGNED VCN YET\n");
1600
1601 CurrentKey = Node->FirstKey;
1602 for (i = 0; i < Node->KeyCount; i++)
1603 {
1604 DumpBTreeKey(Tree, CurrentKey, i, Depth);
1605 CurrentKey = CurrentKey->NextKey;
1606 }
1607}
VOID DumpBTreeKey(PB_TREE Tree, PB_TREE_KEY Key, ULONG Number, ULONG Depth)
Definition: btree.c:1549

Referenced by DumpBTree(), DumpBTreeKey(), and SplitBTreeNode().

◆ GetAllocationOffsetFromVCN()

ULONGLONG GetAllocationOffsetFromVCN ( PDEVICE_EXTENSION  DeviceExt,
ULONG  IndexBufferSize,
ULONGLONG  Vcn 
)

Definition at line 1630 of file btree.c.

1633{
1634 if (IndexBufferSize < DeviceExt->NtfsInfo.BytesPerCluster)
1635 return Vcn * DeviceExt->NtfsInfo.BytesPerSector;
1636
1637 return Vcn * DeviceExt->NtfsInfo.BytesPerCluster;
1638}

Referenced by CreateBTreeNodeFromIndexNode(), and UpdateIndexNode().

◆ GetIndexEntryVCN()

ULONGLONG GetIndexEntryVCN ( PINDEX_ENTRY_ATTRIBUTE  IndexEntry)

Definition at line 1641 of file btree.c.

1642{
1643 PULONGLONG Destination = (PULONGLONG)((ULONG_PTR)IndexEntry + IndexEntry->Length - sizeof(ULONGLONG));
1644
1645 ASSERT(IndexEntry->Flags & NTFS_INDEX_ENTRY_NODE);
1646
1647 return *Destination;
1648}
_In_ PUNICODE_STRING _Inout_ PUNICODE_STRING Destination
Definition: rtlfuncs.h:3004

Referenced by BrowseIndexEntries(), BrowseSubNodeIndexEntries(), and SplitBTreeNode().

◆ GetSizeOfIndexEntries()

ULONG GetSizeOfIndexEntries ( PB_TREE_FILENAME_NODE  Node)

Definition at line 855 of file btree.c.

856{
857 // Start summing the total size of this node's entries
858 ULONG NodeSize = 0;
859
860 // Walk through the list of Node Entries
861 PB_TREE_KEY CurrentKey = Node->FirstKey;
862 ULONG i;
863 for (i = 0; i < Node->KeyCount; i++)
864 {
865 ASSERT(CurrentKey->IndexEntry->Length != 0);
866
867 // Add the length of the current node
868 NodeSize += CurrentKey->IndexEntry->Length;
869 CurrentKey = CurrentKey->NextKey;
870 }
871
872 return NodeSize;
873}

Referenced by NtfsAddFilenameToDirectory(), and NtfsInsertKey().

◆ NtfsInsertKey()

NTSTATUS NtfsInsertKey ( PB_TREE  Tree,
ULONGLONG  FileReference,
PFILENAME_ATTRIBUTE  FileNameAttribute,
PB_TREE_FILENAME_NODE  Node,
BOOLEAN  CaseSensitive,
ULONG  MaxIndexRootSize,
ULONG  IndexRecordSize,
PB_TREE_KEY MedianKey,
PB_TREE_FILENAME_NODE NewRightHandSibling 
)

Definition at line 1691 of file btree.c.

1700{
1701 PB_TREE_KEY NewKey, CurrentKey, PreviousKey;
1703 ULONG NodeSize;
1704 ULONG AllocatedNodeSize;
1705 ULONG MaxNodeSizeWithoutHeader;
1706 ULONG i;
1707
1708 *MedianKey = NULL;
1709 *NewRightHandSibling = NULL;
1710
1711 DPRINT("NtfsInsertKey(%p, 0x%I64x, %p, %p, %s, %lu, %lu, %p, %p)\n",
1712 Tree,
1713 FileReference,
1714 FileNameAttribute,
1715 Node,
1716 CaseSensitive ? "TRUE" : "FALSE",
1717 MaxIndexRootSize,
1718 IndexRecordSize,
1719 MedianKey,
1720 NewRightHandSibling);
1721
1722 // Create the key for the filename attribute
1723 NewKey = CreateBTreeKeyFromFilename(FileReference, FileNameAttribute);
1724 if (!NewKey)
1726
1727 // Find where to insert the key
1728 CurrentKey = Node->FirstKey;
1729 PreviousKey = NULL;
1730 for (i = 0; i < Node->KeyCount; i++)
1731 {
1732 // Should the New Key go before the current key?
1733 LONG Comparison = CompareTreeKeys(NewKey, CurrentKey, CaseSensitive);
1734
1735 if (Comparison == 0)
1736 {
1737 DPRINT1("\t\tComparison == 0: %.*S\n", NewKey->IndexEntry->FileName.NameLength, NewKey->IndexEntry->FileName.Name);
1738 DPRINT1("\t\tComparison == 0: %.*S\n", CurrentKey->IndexEntry->FileName.NameLength, CurrentKey->IndexEntry->FileName.Name);
1739 }
1740 ASSERT(Comparison != 0);
1741
1742 // Is NewKey < CurrentKey?
1743 if (Comparison < 0)
1744 {
1745 // Does CurrentKey have a sub-node?
1746 if (CurrentKey->LesserChild)
1747 {
1748 PB_TREE_KEY NewLeftKey;
1749 PB_TREE_FILENAME_NODE NewChild;
1750
1751 // Insert the key into the child node
1753 FileReference,
1754 FileNameAttribute,
1755 CurrentKey->LesserChild,
1756 CaseSensitive,
1757 MaxIndexRootSize,
1758 IndexRecordSize,
1759 &NewLeftKey,
1760 &NewChild);
1761 if (!NT_SUCCESS(Status))
1762 {
1763 DPRINT1("ERROR: Failed to insert key.\n");
1764 ExFreePoolWithTag(NewKey, TAG_NTFS);
1765 return Status;
1766 }
1767
1768 // Did the child node get split?
1769 if (NewLeftKey)
1770 {
1771 ASSERT(NewChild != NULL);
1772
1773 // Insert the new left key to the left of the current key
1774 NewLeftKey->NextKey = CurrentKey;
1775
1776 // Is CurrentKey the first key?
1777 if (!PreviousKey)
1778 Node->FirstKey = NewLeftKey;
1779 else
1780 PreviousKey->NextKey = NewLeftKey;
1781
1782 // CurrentKey->LesserChild will be the right-hand sibling
1783 CurrentKey->LesserChild = NewChild;
1784
1785 Node->KeyCount++;
1786 Node->DiskNeedsUpdating = TRUE;
1787
1788#ifndef NDEBUG
1789 DumpBTree(Tree);
1790#endif
1791 }
1792 }
1793 else
1794 {
1795 // Insert New Key before Current Key
1796 NewKey->NextKey = CurrentKey;
1797
1798 // Increase KeyCount and mark node as dirty
1799 Node->KeyCount++;
1800 Node->DiskNeedsUpdating = TRUE;
1801
1802 // was CurrentKey the first key?
1803 if (CurrentKey == Node->FirstKey)
1804 Node->FirstKey = NewKey;
1805 else
1806 PreviousKey->NextKey = NewKey;
1807 }
1808 break;
1809 }
1810
1811 PreviousKey = CurrentKey;
1812 CurrentKey = CurrentKey->NextKey;
1813 }
1814
1815 // Determine how much space the index entries will need
1816 NodeSize = GetSizeOfIndexEntries(Node);
1817
1818 // Is Node not the root node?
1819 if (Node != Tree->RootNode)
1820 {
1821 // Calculate maximum size of index entries without any headers
1822 AllocatedNodeSize = IndexRecordSize - FIELD_OFFSET(INDEX_BUFFER, Header);
1823
1824 // TODO: Replace magic with math
1825 MaxNodeSizeWithoutHeader = AllocatedNodeSize - 0x28;
1826
1827 // Has the node grown larger than its allocated size?
1828 if (NodeSize > MaxNodeSizeWithoutHeader)
1829 {
1831
1832 Status = SplitBTreeNode(Tree, Node, MedianKey, NewRightHandSibling, CaseSensitive);
1833 if (!NT_SUCCESS(Status))
1834 {
1835 DPRINT1("ERROR: Failed to split B-Tree node!\n");
1836 return Status;
1837 }
1838
1839 return Status;
1840 }
1841 }
1842
1843 // NewEntry and NewKey will be destroyed later by DestroyBTree()
1844
1845 return Status;
1846}
LONG CompareTreeKeys(PB_TREE_KEY Key1, PB_TREE_KEY Key2, BOOLEAN CaseSensitive)
Definition: btree.c:417
NTSTATUS SplitBTreeNode(PB_TREE Tree, PB_TREE_FILENAME_NODE Node, PB_TREE_KEY *MedianKey, PB_TREE_FILENAME_NODE *NewRightHandSibling, BOOLEAN CaseSensitive)
Definition: btree.c:1883
NTSTATUS NtfsInsertKey(PB_TREE Tree, ULONGLONG FileReference, PFILENAME_ATTRIBUTE FileNameAttribute, PB_TREE_FILENAME_NODE Node, BOOLEAN CaseSensitive, ULONG MaxIndexRootSize, ULONG IndexRecordSize, PB_TREE_KEY *MedianKey, PB_TREE_FILENAME_NODE *NewRightHandSibling)
Definition: btree.c:1691
ULONG GetSizeOfIndexEntries(PB_TREE_FILENAME_NODE Node)
Definition: btree.c:855
PB_TREE_KEY CreateBTreeKeyFromFilename(ULONGLONG FileReference, PFILENAME_ATTRIBUTE FileNameAttribute)
Definition: btree.c:1461

Referenced by NtfsAddFilenameToDirectory(), and NtfsInsertKey().

◆ PrintAllVCNs()

VOID PrintAllVCNs ( PDEVICE_EXTENSION  Vcb,
PNTFS_ATTR_CONTEXT  IndexAllocationContext,
ULONG  NodeSize 
)

Definition at line 38 of file btree.c.

41{
42 ULONGLONG CurrentOffset = 0;
43 PINDEX_BUFFER CurrentNode, Buffer;
44 ULONGLONG BufferSize = AttributeDataLength(IndexAllocationContext->pRecord);
47 int Count = 0;
48
49 if (BufferSize == 0)
50 {
51 DPRINT1("Index Allocation is empty.\n");
52 return;
53 }
54
56
57 BytesRead = ReadAttribute(Vcb, IndexAllocationContext, 0, (PCHAR)Buffer, BufferSize);
58
60
61 CurrentNode = Buffer;
62
63 // loop through all the nodes
64 for (i = 0; i < BufferSize; i += NodeSize)
65 {
67 if (!NT_SUCCESS(Status))
68 {
69 DPRINT1("ERROR: Fixing fixup failed!\n");
70 continue;
71 }
72
73 DPRINT1("Node #%d, VCN: %I64u\n", Count, CurrentNode->VCN);
74
75 CurrentNode = (PINDEX_BUFFER)((ULONG_PTR)CurrentNode + NodeSize);
76 CurrentOffset += NodeSize;
77 Count++;
78 }
79
81}
Definition: bufpool.h:45
#define BufferSize
Definition: mmc.h:75
struct INDEX_BUFFER * PINDEX_BUFFER

Referenced by UpdateIndexAllocation().

◆ SetIndexEntryVCN()

VOID SetIndexEntryVCN ( PINDEX_ENTRY_ATTRIBUTE  IndexEntry,
ULONGLONG  VCN 
)

Definition at line 1172 of file btree.c.

1173{
1174 PULONGLONG Destination = (PULONGLONG)((ULONG_PTR)IndexEntry + IndexEntry->Length - sizeof(ULONGLONG));
1175
1176 ASSERT(IndexEntry->Flags & NTFS_INDEX_ENTRY_NODE);
1177
1178 *Destination = VCN;
1179}

Referenced by SplitBTreeNode(), UpdateIndexAllocation(), and UpdateIndexNode().

◆ SplitBTreeNode()

NTSTATUS SplitBTreeNode ( PB_TREE  Tree,
PB_TREE_FILENAME_NODE  Node,
PB_TREE_KEY MedianKey,
PB_TREE_FILENAME_NODE NewRightHandSibling,
BOOLEAN  CaseSensitive 
)

Definition at line 1883 of file btree.c.

1888{
1889 ULONG MedianKeyIndex;
1890 PB_TREE_KEY LastKeyBeforeMedian, FirstKeyAfterMedian;
1891 ULONG KeyCount;
1892 ULONG HalfSize;
1893 ULONG SizeSum;
1894 ULONG i;
1895
1896 DPRINT("SplitBTreeNode(%p, %p, %p, %p, %s) called\n",
1897 Tree,
1898 Node,
1899 MedianKey,
1900 NewRightHandSibling,
1901 CaseSensitive ? "TRUE" : "FALSE");
1902
1903#ifndef NDEBUG
1904 DumpBTreeNode(Tree, Node, 0, 0);
1905#endif
1906
1907 // Create the right hand sibling
1908 *NewRightHandSibling = ExAllocatePoolWithTag(NonPagedPool, sizeof(B_TREE_FILENAME_NODE), TAG_NTFS);
1909 if (*NewRightHandSibling == NULL)
1910 {
1911 DPRINT1("Error: Failed to allocate memory for right hand sibling!\n");
1913 }
1914 RtlZeroMemory(*NewRightHandSibling, sizeof(B_TREE_FILENAME_NODE));
1915 (*NewRightHandSibling)->DiskNeedsUpdating = TRUE;
1916
1917
1918 // Find the last key before the median
1919
1920 // This is roughly how NTFS-3G calculates median, and it's not congruent with what Windows does:
1921 /*
1922 // find the median key index
1923 MedianKeyIndex = (Node->KeyCount + 1) / 2;
1924 MedianKeyIndex--;
1925
1926 LastKeyBeforeMedian = Node->FirstKey;
1927 for (i = 0; i < MedianKeyIndex - 1; i++)
1928 LastKeyBeforeMedian = LastKeyBeforeMedian->NextKey;*/
1929
1930 // The method we'll use is a little bit closer to how Windows determines the median but it's not identical.
1931 // What Windows does is actually more complicated than this, I think because Windows allocates more slack space to Odd-numbered
1932 // Index Records, leaving less room for index entries in these records (I haven't discovered why this is done).
1933 // (Neither Windows nor chkdsk complain if we choose a different median than Windows would have chosen, as our median will be in the ballpark)
1934
1935 // Use size to locate the median key / index
1936 LastKeyBeforeMedian = Node->FirstKey;
1937 MedianKeyIndex = 0;
1938 HalfSize = 2016; // half the allocated size after subtracting the first index entry offset (TODO: MATH)
1939 SizeSum = 0;
1940 for (i = 0; i < Node->KeyCount; i++)
1941 {
1942 SizeSum += LastKeyBeforeMedian->IndexEntry->Length;
1943
1944 if (SizeSum > HalfSize)
1945 break;
1946
1947 MedianKeyIndex++;
1948 LastKeyBeforeMedian = LastKeyBeforeMedian->NextKey;
1949 }
1950
1951 // Now we can get the median key and the key that follows it
1952 *MedianKey = LastKeyBeforeMedian->NextKey;
1953 FirstKeyAfterMedian = (*MedianKey)->NextKey;
1954
1955 DPRINT1("%lu keys, %lu median\n", Node->KeyCount, MedianKeyIndex);
1956 DPRINT1("\t\tMedian: %.*S\n", (*MedianKey)->IndexEntry->FileName.NameLength, (*MedianKey)->IndexEntry->FileName.Name);
1957
1958 // "Node" will be the left hand sibling after the split, containing all keys prior to the median key
1959
1960 // We need to create a dummy pointer at the end of the LHS. The dummy's child will be the median's child.
1961 LastKeyBeforeMedian->NextKey = CreateDummyKey(BooleanFlagOn((*MedianKey)->IndexEntry->Flags, NTFS_INDEX_ENTRY_NODE));
1962 if (LastKeyBeforeMedian->NextKey == NULL)
1963 {
1964 DPRINT1("Error: Couldn't allocate dummy key!\n");
1965 LastKeyBeforeMedian->NextKey = *MedianKey;
1966 ExFreePoolWithTag(*NewRightHandSibling, TAG_NTFS);
1968 }
1969
1970 // Did the median key have a child node?
1971 if ((*MedianKey)->IndexEntry->Flags & NTFS_INDEX_ENTRY_NODE)
1972 {
1973 // Set the child of the new dummy key
1974 LastKeyBeforeMedian->NextKey->LesserChild = (*MedianKey)->LesserChild;
1975
1976 // Give the dummy key's index entry the same sub-node VCN the median
1977 SetIndexEntryVCN(LastKeyBeforeMedian->NextKey->IndexEntry, GetIndexEntryVCN((*MedianKey)->IndexEntry));
1978 }
1979 else
1980 {
1981 // Median key didn't have a child node, but it will. Create a new index entry large enough to store a VCN.
1983 (*MedianKey)->IndexEntry->Length + sizeof(ULONGLONG),
1984 TAG_NTFS);
1985 if (!NewIndexEntry)
1986 {
1987 DPRINT1("Unable to allocate memory for new index entry!\n");
1988 LastKeyBeforeMedian->NextKey = *MedianKey;
1989 ExFreePoolWithTag(*NewRightHandSibling, TAG_NTFS);
1991 }
1992
1993 // Copy the old index entry to the new one
1994 RtlCopyMemory(NewIndexEntry, (*MedianKey)->IndexEntry, (*MedianKey)->IndexEntry->Length);
1995
1996 // Use the new index entry after freeing the old one
1997 ExFreePoolWithTag((*MedianKey)->IndexEntry, TAG_NTFS);
1998 (*MedianKey)->IndexEntry = NewIndexEntry;
1999
2000 // Update the length for the VCN
2001 (*MedianKey)->IndexEntry->Length += sizeof(ULONGLONG);
2002
2003 // Set the node flag
2004 (*MedianKey)->IndexEntry->Flags |= NTFS_INDEX_ENTRY_NODE;
2005 }
2006
2007 // "Node" will become the child of the median key
2008 (*MedianKey)->LesserChild = Node;
2009 SetIndexEntryVCN((*MedianKey)->IndexEntry, Node->VCN);
2010
2011 // Update Node's KeyCount (remember to add 1 for the new dummy key)
2012 Node->KeyCount = MedianKeyIndex + 2;
2013
2014 KeyCount = CountBTreeKeys(Node->FirstKey);
2015 ASSERT(Node->KeyCount == KeyCount);
2016
2017 // everything to the right of MedianKey becomes the right hand sibling of Node
2018 (*NewRightHandSibling)->FirstKey = FirstKeyAfterMedian;
2019 (*NewRightHandSibling)->KeyCount = CountBTreeKeys(FirstKeyAfterMedian);
2020
2021#ifndef NDEBUG
2022 DPRINT1("Left-hand node after split:\n");
2023 DumpBTreeNode(Tree, Node, 0, 0);
2024
2025 DPRINT1("Right-hand sibling node after split:\n");
2026 DumpBTreeNode(Tree, *NewRightHandSibling, 0, 0);
2027#endif
2028
2029 return STATUS_SUCCESS;
2030}
ULONG CountBTreeKeys(PB_TREE_KEY FirstKey)
Definition: btree.c:484
ULONGLONG GetIndexEntryVCN(PINDEX_ENTRY_ATTRIBUTE IndexEntry)
Definition: btree.c:1641
VOID SetIndexEntryVCN(PINDEX_ENTRY_ATTRIBUTE IndexEntry, ULONGLONG VCN)
Definition: btree.c:1172
union node Node
Definition: types.h:1255
#define BooleanFlagOn(F, SF)
Definition: ext2fs.h:183

Referenced by NtfsInsertKey().

◆ UpdateIndexAllocation()

NTSTATUS UpdateIndexAllocation ( PDEVICE_EXTENSION  DeviceExt,
PB_TREE  Tree,
ULONG  IndexBufferSize,
PFILE_RECORD_HEADER  FileRecord 
)

Definition at line 1182 of file btree.c.

1186{
1187 // Find the index allocation and bitmap
1188 PNTFS_ATTR_CONTEXT IndexAllocationContext;
1189 PB_TREE_KEY CurrentKey;
1191 BOOLEAN HasIndexAllocation = FALSE;
1192 ULONG i;
1193 ULONG IndexAllocationOffset;
1194
1195 DPRINT("UpdateIndexAllocation() called.\n");
1196
1197 Status = FindAttribute(DeviceExt, FileRecord, AttributeIndexAllocation, L"$I30", 4, &IndexAllocationContext, &IndexAllocationOffset);
1198 if (NT_SUCCESS(Status))
1199 {
1200 HasIndexAllocation = TRUE;
1201
1202#ifndef NDEBUG
1203 PrintAllVCNs(DeviceExt,
1204 IndexAllocationContext,
1205 IndexBufferSize);
1206#endif
1207 }
1208 // Walk through the root node and update all the sub-nodes
1209 CurrentKey = Tree->RootNode->FirstKey;
1210 for (i = 0; i < Tree->RootNode->KeyCount; i++)
1211 {
1212 if (CurrentKey->LesserChild)
1213 {
1214 if (!HasIndexAllocation)
1215 {
1216 // We need to add an index allocation to the file record
1217 PNTFS_ATTR_RECORD EndMarker = (PNTFS_ATTR_RECORD)((ULONG_PTR)FileRecord + FileRecord->BytesInUse - (sizeof(ULONG) * 2));
1218 DPRINT1("Adding index allocation...\n");
1219
1220 // Add index allocation to the very end of the file record
1221 Status = AddIndexAllocation(DeviceExt,
1222 FileRecord,
1223 EndMarker,
1224 L"$I30",
1225 4);
1226 if (!NT_SUCCESS(Status))
1227 {
1228 DPRINT1("ERROR: Failed to add index allocation!\n");
1229 return Status;
1230 }
1231
1232 // Find the new attribute
1233 Status = FindAttribute(DeviceExt, FileRecord, AttributeIndexAllocation, L"$I30", 4, &IndexAllocationContext, &IndexAllocationOffset);
1234 if (!NT_SUCCESS(Status))
1235 {
1236 DPRINT1("ERROR: Couldn't find newly-created index allocation!\n");
1237 return Status;
1238 }
1239
1240 // Advance end marker
1241 EndMarker = (PNTFS_ATTR_RECORD)((ULONG_PTR)EndMarker + EndMarker->Length);
1242
1243 // Add index bitmap to the very end of the file record
1244 Status = AddBitmap(DeviceExt,
1245 FileRecord,
1246 EndMarker,
1247 L"$I30",
1248 4);
1249 if (!NT_SUCCESS(Status))
1250 {
1251 DPRINT1("ERROR: Failed to add index bitmap!\n");
1252 ReleaseAttributeContext(IndexAllocationContext);
1253 return Status;
1254 }
1255
1256 HasIndexAllocation = TRUE;
1257 }
1258
1259 // Is the Index Entry large enough to store the VCN?
1261 {
1262 // Allocate memory for the larger index entry
1264 CurrentKey->IndexEntry->Length + sizeof(ULONGLONG),
1265 TAG_NTFS);
1266 if (!NewEntry)
1267 {
1268 DPRINT1("ERROR: Unable to allocate memory for new index entry!\n");
1269 if (HasIndexAllocation)
1270 ReleaseAttributeContext(IndexAllocationContext);
1272 }
1273
1274 // Copy the old entry to the new one
1275 RtlCopyMemory(NewEntry, CurrentKey->IndexEntry, CurrentKey->IndexEntry->Length);
1276
1277 NewEntry->Length += sizeof(ULONGLONG);
1278
1279 // Free the old memory
1281
1282 CurrentKey->IndexEntry = NewEntry;
1283 CurrentKey->IndexEntry->Flags |= NTFS_INDEX_ENTRY_NODE;
1284 }
1285
1286 // Update the sub-node
1287 Status = UpdateIndexNode(DeviceExt, FileRecord, CurrentKey->LesserChild, IndexBufferSize, IndexAllocationContext, IndexAllocationOffset);
1288 if (!NT_SUCCESS(Status))
1289 {
1290 DPRINT1("ERROR: Failed to update index node!\n");
1291 ReleaseAttributeContext(IndexAllocationContext);
1292 return Status;
1293 }
1294
1295 // Update the VCN stored in the index entry of CurrentKey
1296 SetIndexEntryVCN(CurrentKey->IndexEntry, CurrentKey->LesserChild->VCN);
1297 }
1298 CurrentKey = CurrentKey->NextKey;
1299 }
1300
1301#ifndef NDEBUG
1302 DumpBTree(Tree);
1303#endif
1304
1305 if (HasIndexAllocation)
1306 {
1307#ifndef NDEBUG
1308 PrintAllVCNs(DeviceExt,
1309 IndexAllocationContext,
1310 IndexBufferSize);
1311#endif
1312 ReleaseAttributeContext(IndexAllocationContext);
1313 }
1314
1315 return STATUS_SUCCESS;
1316}
unsigned char BOOLEAN
struct NTFS_ATTR_RECORD * PNTFS_ATTR_RECORD
VOID PrintAllVCNs(PDEVICE_EXTENSION Vcb, PNTFS_ATTR_CONTEXT IndexAllocationContext, ULONG NodeSize)
Definition: btree.c:38
NTSTATUS UpdateIndexNode(PDEVICE_EXTENSION DeviceExt, PFILE_RECORD_HEADER FileRecord, PB_TREE_FILENAME_NODE Node, ULONG IndexBufferSize, PNTFS_ATTR_CONTEXT IndexAllocationContext, ULONG IndexAllocationOffset)
Definition: btree.c:1319
NTSTATUS AddBitmap(PNTFS_VCB Vcb, PFILE_RECORD_HEADER FileRecord, PNTFS_ATTR_RECORD AttributeAddress, PCWSTR Name, USHORT NameLength)
Definition: attrib.c:72
NTSTATUS AddIndexAllocation(PNTFS_VCB Vcb, PFILE_RECORD_HEADER FileRecord, PNTFS_ATTR_RECORD AttributeAddress, PCWSTR Name, USHORT NameLength)
Definition: attrib.c:388
ULONG Length
Definition: ntfs.h:127
ULONG BytesInUse
Definition: ntfs.h:257

Referenced by NtfsAddFilenameToDirectory().

◆ UpdateIndexNode()

NTSTATUS UpdateIndexNode ( PDEVICE_EXTENSION  DeviceExt,
PFILE_RECORD_HEADER  FileRecord,
PB_TREE_FILENAME_NODE  Node,
ULONG  IndexBufferSize,
PNTFS_ATTR_CONTEXT  IndexAllocationContext,
ULONG  IndexAllocationOffset 
)

Definition at line 1319 of file btree.c.

1325{
1326 ULONG i;
1327 PB_TREE_KEY CurrentKey = Node->FirstKey;
1328 BOOLEAN HasChildren = FALSE;
1330
1331
1332 DPRINT("UpdateIndexNode(%p, %p, %p, %lu, %p, %lu) called for index node with VCN %I64u\n",
1333 DeviceExt,
1334 FileRecord,
1335 Node,
1336 IndexBufferSize,
1337 IndexAllocationContext,
1338 IndexAllocationOffset,
1339 Node->VCN);
1340
1341 // Walk through the node and look for children to update
1342 for (i = 0; i < Node->KeyCount; i++)
1343 {
1344 ASSERT(CurrentKey);
1345
1346 // If there's a child node
1347 if (CurrentKey->LesserChild)
1348 {
1349 HasChildren = TRUE;
1350
1351 // Update the child node on disk
1352 Status = UpdateIndexNode(DeviceExt, FileRecord, CurrentKey->LesserChild, IndexBufferSize, IndexAllocationContext, IndexAllocationOffset);
1353 if (!NT_SUCCESS(Status))
1354 {
1355 DPRINT1("ERROR: Failed to update child node!\n");
1356 return Status;
1357 }
1358
1359 // Is the Index Entry large enough to store the VCN?
1361 {
1362 // Allocate memory for the larger index entry
1364 CurrentKey->IndexEntry->Length + sizeof(ULONGLONG),
1365 TAG_NTFS);
1366 if (!NewEntry)
1367 {
1368 DPRINT1("ERROR: Unable to allocate memory for new index entry!\n");
1370 }
1371
1372 // Copy the old entry to the new one
1373 RtlCopyMemory(NewEntry, CurrentKey->IndexEntry, CurrentKey->IndexEntry->Length);
1374
1375 NewEntry->Length += sizeof(ULONGLONG);
1376
1377 // Free the old memory
1379
1380 CurrentKey->IndexEntry = NewEntry;
1381 }
1382
1383 // Update the VCN stored in the index entry of CurrentKey
1384 SetIndexEntryVCN(CurrentKey->IndexEntry, CurrentKey->LesserChild->VCN);
1385
1386 CurrentKey->IndexEntry->Flags |= NTFS_INDEX_ENTRY_NODE;
1387 }
1388
1389 CurrentKey = CurrentKey->NextKey;
1390 }
1391
1392
1393 // Do we need to write this node to disk?
1394 if (Node->DiskNeedsUpdating)
1395 {
1396 ULONGLONG NodeOffset;
1397 ULONG LengthWritten;
1398 PINDEX_BUFFER IndexBuffer;
1399
1400 // Does the node need to be assigned a VCN?
1401 if (!Node->HasValidVCN)
1402 {
1403 // Allocate the node
1404 Status = AllocateIndexNode(DeviceExt,
1405 FileRecord,
1406 IndexBufferSize,
1407 IndexAllocationContext,
1408 IndexAllocationOffset,
1409 &Node->VCN);
1410 if (!NT_SUCCESS(Status))
1411 {
1412 DPRINT1("ERROR: Failed to allocate index record in index allocation!\n");
1413 return Status;
1414 }
1415
1416 Node->HasValidVCN = TRUE;
1417 }
1418
1419 // Allocate memory for an index buffer
1420 IndexBuffer = ExAllocatePoolWithTag(NonPagedPool, IndexBufferSize, TAG_NTFS);
1421 if (!IndexBuffer)
1422 {
1423 DPRINT1("ERROR: Failed to allocate %lu bytes for index buffer!\n", IndexBufferSize);
1425 }
1426
1427 // Create the index buffer we'll be writing to disk to represent this node
1428 Status = CreateIndexBufferFromBTreeNode(DeviceExt, Node, IndexBufferSize, HasChildren, IndexBuffer);
1429 if (!NT_SUCCESS(Status))
1430 {
1431 DPRINT1("ERROR: Failed to create index buffer from node!\n");
1432 ExFreePoolWithTag(IndexBuffer, TAG_NTFS);
1433 return Status;
1434 }
1435
1436 // Get Offset of index buffer in index allocation
1437 NodeOffset = GetAllocationOffsetFromVCN(DeviceExt, IndexBufferSize, Node->VCN);
1438
1439 // Write the buffer to the index allocation
1440 Status = WriteAttribute(DeviceExt, IndexAllocationContext, NodeOffset, (const PUCHAR)IndexBuffer, IndexBufferSize, &LengthWritten, FileRecord);
1441 if (!NT_SUCCESS(Status) || LengthWritten != IndexBufferSize)
1442 {
1443 DPRINT1("ERROR: Failed to update index allocation!\n");
1444 ExFreePoolWithTag(IndexBuffer, TAG_NTFS);
1445 if (!NT_SUCCESS(Status))
1446 return Status;
1447 else
1448 return STATUS_END_OF_FILE;
1449 }
1450
1451 Node->DiskNeedsUpdating = FALSE;
1452
1453 // Free the index buffer
1454 ExFreePoolWithTag(IndexBuffer, TAG_NTFS);
1455 }
1456
1457 return STATUS_SUCCESS;
1458}
NTSTATUS AllocateIndexNode(PDEVICE_EXTENSION DeviceExt, PFILE_RECORD_HEADER FileRecord, ULONG IndexBufferSize, PNTFS_ATTR_CONTEXT IndexAllocationCtx, ULONG IndexAllocationOffset, PULONGLONG NewVCN)
Definition: btree.c:117
NTSTATUS CreateIndexBufferFromBTreeNode(PDEVICE_EXTENSION DeviceExt, PB_TREE_FILENAME_NODE Node, ULONG BufferSize, BOOLEAN HasChildren, PINDEX_BUFFER IndexBuffer)
Definition: btree.c:1001
#define STATUS_END_OF_FILE
Definition: shellext.h:67

Referenced by UpdateIndexAllocation(), and UpdateIndexNode().