ReactOS  0.4.14-dev-337-gf981a68
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");
157  return STATUS_NOT_IMPLEMENTED;
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,
258  &BytesWritten,
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 }
signed char * PCHAR
Definition: retypes.h:7
_Must_inspect_result_ _In_ PFILE_OBJECT _In_opt_ PLARGE_INTEGER _In_ ULONG _In_ FLT_IO_OPERATION_FLAGS _Out_opt_ PULONG BytesWritten
Definition: fltkernel.h:1293
NTSYSAPI void WINAPI RtlInitializeBitMap(PRTL_BITMAP, PULONG, ULONG)
#define STATUS_INSUFFICIENT_RESOURCES
Definition: udferr_usr.h:158
#define ALIGN_UP(size, type)
Definition: umtypes.h:91
#define STATUS_NOT_IMPLEMENTED
Definition: ntstatus.h:225
unsigned char * PUCHAR
Definition: retypes.h:3
LONG NTSTATUS
Definition: precomp.h:26
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
uint32_t ULONG_PTR
Definition: typedefs.h:63
NTSTATUS SetResidentAttributeDataLength(PDEVICE_EXTENSION Vcb, PNTFS_ATTR_CONTEXT AttrContext, ULONG AttrOffset, PFILE_RECORD_HEADER FileRecord, PLARGE_INTEGER DataSize)
Definition: mft.c:891
void DPRINT(...)
Definition: polytest.cpp:61
#define ATTR_RECORD_ALIGNMENT
Definition: ntfs.h:316
#define NT_SUCCESS(StatCode)
Definition: apphelp.c:32
uint64_t ULONGLONG
Definition: typedefs.h:65
NTSTATUS SetNonResidentAttributeDataLength(PDEVICE_EXTENSION Vcb, PNTFS_ATTR_CONTEXT AttrContext, ULONG AttrOffset, PFILE_RECORD_HEADER FileRecord, PLARGE_INTEGER DataSize)
Definition: mft.c:756
#define TAG_NTFS
Definition: ntfs.h:12
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
#define ExAllocatePoolWithTag(hernya, size, tag)
Definition: env_spec_w32.h:350
static const WCHAR L[]
Definition: oid.c:1250
Status
Definition: gdiplustypes.h:24
VOID ReleaseAttributeContext(PNTFS_ATTR_CONTEXT Context)
Definition: mft.c:104
NTSTATUS UpdateFileRecord(PDEVICE_EXTENSION Vcb, ULONGLONG MftIndex, PFILE_RECORD_HEADER FileRecord)
Definition: mft.c:1931
unsigned int * PULONG
Definition: retypes.h:1
ULONG ReadAttribute(PDEVICE_EXTENSION Vcb, PNTFS_ATTR_CONTEXT Context, ULONGLONG Offset, PCHAR Buffer, ULONG Length)
Definition: mft.c:1065
#define DPRINT1
Definition: precomp.h:8
unsigned int ULONG
Definition: retypes.h:1
#define RtlZeroMemory(Destination, Length)
Definition: typedefs.h:261
#define ALIGN_UP_BY(size, align)
NTSYSAPI void WINAPI RtlSetBits(PRTL_BITMAP, ULONG, ULONG)
#define ExFreePoolWithTag(_P, _T)
Definition: module.h:1099
ULONGLONG AttributeDataLength(PNTFS_ATTR_RECORD AttrRecord)
Definition: mft.c:259
_In_ NDIS_STATUS _In_ ULONG _In_ USHORT _In_opt_ PVOID _In_ ULONG DataSize
Definition: ndis.h:4751

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 }
FILENAME_ATTRIBUTE FileName
Definition: ntfs.h:423
USHORT MaximumLength
Definition: env_spec_w32.h:370
WCHAR Name[1]
Definition: ntfs.h:375
UCHAR NameLength
Definition: ntfs.h:373
#define NTFS_INDEX_ENTRY_END
Definition: ntfs.h:61
long LONG
Definition: pedump.c:60
smooth NULL
Definition: ftsmooth.c:416
struct _B_TREE_KEY * NextKey
Definition: ntfs.h:432
__wchar_t WCHAR
Definition: xmlstorage.h:180
ASSERT((InvokeOnSuccess||InvokeOnError||InvokeOnCancel) ?(CompletionRoutine !=NULL) :TRUE)
USHORT Flags
Definition: ntfs.h:421
ULONG RtlCompareUnicodeString(PUNICODE_STRING s1, PUNICODE_STRING s2, BOOLEAN UpCase)
Definition: string_lib.cpp:31
PINDEX_ENTRY_ATTRIBUTE IndexEntry
Definition: ntfs.h:434

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 }
_Inout_ __drv_aliasesMem PSLIST_ENTRY _Inout_ PSLIST_ENTRY _In_ ULONG Count
Definition: exfuncs.h:1015
smooth NULL
Definition: ftsmooth.c:416
struct _B_TREE_KEY * NextKey
Definition: ntfs.h:432
unsigned int ULONG
Definition: retypes.h:1

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 
832 Cleanup:
833  if (IndexAllocationContext)
834  ReleaseAttributeContext(IndexAllocationContext);
835 
836  return Status;
837 }
NTSYSAPI VOID NTAPI RtlCopyMemory(VOID UNALIGNED *Destination, CONST VOID UNALIGNED *Source, ULONG Length)
#define STATUS_INSUFFICIENT_RESOURCES
Definition: udferr_usr.h:158
#define STATUS_NOT_IMPLEMENTED
Definition: ntstatus.h:225
LONG NTSTATUS
Definition: precomp.h:26
USHORT Length
Definition: ntfs.h:419
Definition: ntfs.h:404
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
#define NTFS_INDEX_ENTRY_END
Definition: ntfs.h:61
uint32_t ULONG_PTR
Definition: typedefs.h:63
ULONG FirstEntryOffset
Definition: ntfs.h:380
#define STATUS_FILE_CORRUPT_ERROR
Definition: udferr_usr.h:168
Definition: Header.h:8
smooth NULL
Definition: ftsmooth.c:416
void DPRINT(...)
Definition: polytest.cpp:61
struct _B_TREE_KEY * NextKey
Definition: ntfs.h:432
B_TREE_FILENAME_NODE * LesserChild
Definition: ntfs.h:433
#define NT_SUCCESS(StatCode)
Definition: apphelp.c:32
#define Vcb
Definition: cdprocs.h:1425
INDEX_HEADER_ATTRIBUTE Header
Definition: ntfs.h:394
CRegistryTree Tree
#define TAG_NTFS
Definition: ntfs.h:12
#define ExAllocatePoolWithTag(hernya, size, tag)
Definition: env_spec_w32.h:350
USHORT Flags
Definition: ntfs.h:421
static const WCHAR L[]
Definition: oid.c:1250
ULONG TotalSizeOfEntries
Definition: ntfs.h:381
static const WCHAR Cleanup[]
Definition: register.c:80
#define NTFS_INDEX_ENTRY_NODE
Definition: ntfs.h:60
Status
Definition: gdiplustypes.h:24
VOID DestroyBTree(PB_TREE Tree)
Definition: btree.c:1542
VOID ReleaseAttributeContext(PNTFS_ATTR_CONTEXT Context)
Definition: mft.c:104
#define FIELD_OFFSET(t, f)
Definition: typedefs.h:254
Definition: ntfs.h:449
#define DPRINT1
Definition: precomp.h:8
unsigned int ULONG
Definition: retypes.h:1
#define RtlZeroMemory(Destination, Length)
Definition: typedefs.h:261
PINDEX_ENTRY_ATTRIBUTE IndexEntry
Definition: ntfs.h:434
PB_TREE_FILENAME_NODE CreateBTreeNodeFromIndexNode(PDEVICE_EXTENSION Vcb, PINDEX_ROOT_ATTRIBUTE IndexRoot, PNTFS_ATTR_CONTEXT IndexAllocationAttributeCtx, PINDEX_ENTRY_ATTRIBUTE NodeEntry)
Definition: btree.c:499
#define ExFreePoolWithTag(_P, _T)
Definition: module.h:1099
return STATUS_SUCCESS
Definition: btrfs.c:2938
struct INDEX_ENTRY_ATTRIBUTE * PINDEX_ENTRY_ATTRIBUTE
PCONFIGURATION_COMPONENT_DATA RootNode
Definition: macharm.c:19

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 }
NTSYSAPI VOID NTAPI RtlCopyMemory(VOID UNALIGNED *Destination, CONST VOID UNALIGNED *Source, ULONG Length)
FILENAME_ATTRIBUTE FileName
Definition: ntfs.h:423
USHORT Length
Definition: ntfs.h:419
Definition: ntfs.h:404
_In_ UCHAR EntrySize
Definition: iofuncs.h:640
USHORT KeyLength
Definition: ntfs.h:420
struct INDEX_ENTRY_ATTRIBUTE::@761::@762 Directory
smooth NULL
Definition: ftsmooth.c:416
struct _B_TREE_KEY * NextKey
Definition: ntfs.h:432
#define TAG_NTFS
Definition: ntfs.h:12
#define ExAllocatePoolWithTag(hernya, size, tag)
Definition: env_spec_w32.h:350
#define FIELD_OFFSET(t, f)
Definition: typedefs.h:254
#define DPRINT1
Definition: precomp.h:8
unsigned int ULONG
Definition: retypes.h:1
#define RtlZeroMemory(Destination, Length)
Definition: typedefs.h:261
#define ALIGN_UP_BY(size, align)
PINDEX_ENTRY_ATTRIBUTE IndexEntry
Definition: ntfs.h:434
#define ExFreePoolWithTag(_P, _T)
Definition: module.h:1099
union INDEX_ENTRY_ATTRIBUTE::@761 Data
ULONG GetFileNameAttributeLength(PFILENAME_ATTRIBUTE FileNameAttribute)
Definition: attrib.c:1978

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
535  CurrentKey = ExAllocatePoolWithTag(NonPagedPool, sizeof(B_TREE_KEY), TAG_NTFS);
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 }
signed char * PCHAR
Definition: retypes.h:7
#define TRUE
Definition: types.h:120
NTSYSAPI VOID NTAPI RtlCopyMemory(VOID UNALIGNED *Destination, CONST VOID UNALIGNED *Source, ULONG Length)
LONG NTSTATUS
Definition: precomp.h:26
PB_TREE_KEY FirstKey
Definition: ntfs.h:446
USHORT Length
Definition: ntfs.h:419
ULONGLONG VCN
Definition: ntfs.h:445
Definition: ntfs.h:404
ULONGLONG VCN
Definition: ntfs.h:400
#define NTFS_INDEX_ENTRY_END
Definition: ntfs.h:61
uint32_t ULONG_PTR
Definition: typedefs.h:63
ULONG FirstEntryOffset
Definition: ntfs.h:380
Definition: Header.h:8
INDEX_HEADER_ATTRIBUTE Header
Definition: ntfs.h:401
smooth NULL
Definition: ftsmooth.c:416
struct _B_TREE_KEY * NextKey
Definition: ntfs.h:432
B_TREE_FILENAME_NODE * LesserChild
Definition: ntfs.h:433
VOID DestroyBTreeNode(PB_TREE_FILENAME_NODE Node)
Definition: btree.c:1511
#define NT_SUCCESS(StatCode)
Definition: apphelp.c:32
uint64_t ULONGLONG
Definition: typedefs.h:65
#define Vcb
Definition: cdprocs.h:1425
#define TAG_NTFS
Definition: ntfs.h:12
NTSTATUS FixupUpdateSequenceArray(PDEVICE_EXTENSION Vcb, PNTFS_RECORD_HEADER Record)
Definition: mft.c:1965
ASSERT((InvokeOnSuccess||InvokeOnError||InvokeOnCancel) ?(CompletionRoutine !=NULL) :TRUE)
#define ExAllocatePoolWithTag(hernya, size, tag)
Definition: env_spec_w32.h:350
USHORT Flags
Definition: ntfs.h:421
ULONGLONG GetAllocationOffsetFromVCN(PDEVICE_EXTENSION DeviceExt, ULONG IndexBufferSize, ULONGLONG Vcn)
Definition: btree.c:1630
#define NTFS_INDEX_ENTRY_NODE
Definition: ntfs.h:60
#define NRH_INDX_TYPE
Definition: ntfs.h:243
Status
Definition: gdiplustypes.h:24
ULONG ReadAttribute(PDEVICE_EXTENSION Vcb, PNTFS_ATTR_CONTEXT Context, ULONGLONG Offset, PCHAR Buffer, ULONG Length)
Definition: mft.c:1065
#define DPRINT1
Definition: precomp.h:8
__GNU_EXTENSION typedef unsigned __int64 * PULONGLONG
Definition: ntbasedef.h:390
unsigned int ULONG
Definition: retypes.h:1
#define RtlZeroMemory(Destination, Length)
Definition: typedefs.h:261
NTFS_RECORD_HEADER Ntfs
Definition: ntfs.h:399
PINDEX_ENTRY_ATTRIBUTE IndexEntry
Definition: ntfs.h:434
PB_TREE_FILENAME_NODE CreateBTreeNodeFromIndexNode(PDEVICE_EXTENSION Vcb, PINDEX_ROOT_ATTRIBUTE IndexRoot, PNTFS_ATTR_CONTEXT IndexAllocationAttributeCtx, PINDEX_ENTRY_ATTRIBUTE NodeEntry)
Definition: btree.c:499
#define ExFreePoolWithTag(_P, _T)
Definition: module.h:1099
struct INDEX_ENTRY_ATTRIBUTE * PINDEX_ENTRY_ATTRIBUTE
_Must_inspect_result_ _In_ PFILE_OBJECT _In_opt_ PLARGE_INTEGER _In_ ULONG _In_ FLT_IO_OPERATION_FLAGS _Out_opt_ PULONG BytesRead
Definition: fltkernel.h:1255
BOOLEAN HasValidVCN
Definition: ntfs.h:443
#define NT_ASSERT
Definition: rtlfuncs.h:3312

Referenced by CreateBTreeFromIndex().

◆ 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 }
USHORT Length
Definition: ntfs.h:419
Definition: ntfs.h:404
_In_ UCHAR EntrySize
Definition: iofuncs.h:640
#define NTFS_INDEX_ENTRY_END
Definition: ntfs.h:61
smooth NULL
Definition: ftsmooth.c:416
uint64_t ULONGLONG
Definition: typedefs.h:65
#define TAG_NTFS
Definition: ntfs.h:12
#define ExAllocatePoolWithTag(hernya, size, tag)
Definition: env_spec_w32.h:350
USHORT Flags
Definition: ntfs.h:421
#define NTFS_INDEX_ENTRY_NODE
Definition: ntfs.h:60
#define FIELD_OFFSET(t, f)
Definition: typedefs.h:254
#define DPRINT1
Definition: precomp.h:8
unsigned int ULONG
Definition: retypes.h:1
#define RtlZeroMemory(Destination, Length)
Definition: typedefs.h:261
#define ALIGN_UP_BY(size, align)
PINDEX_ENTRY_ATTRIBUTE IndexEntry
Definition: ntfs.h:434
#define ExFreePoolWithTag(_P, _T)
Definition: module.h:1099

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 }
#define TRUE
Definition: types.h:120
#define STATUS_INSUFFICIENT_RESOURCES
Definition: udferr_usr.h:158
PB_TREE_KEY CreateDummyKey(BOOLEAN HasChildNode)
Definition: btree.c:289
CRegistryTree Tree
#define TAG_NTFS
Definition: ntfs.h:12
#define ExAllocatePoolWithTag(hernya, size, tag)
Definition: env_spec_w32.h:350
Definition: ntfs.h:449
#define DPRINT1
Definition: precomp.h:8
#define RtlZeroMemory(Destination, Length)
Definition: typedefs.h:261
#define ExFreePoolWithTag(_P, _T)
Definition: module.h:1099
return STATUS_SUCCESS
Definition: btrfs.c:2938
PCONFIGURATION_COMPONENT_DATA RootNode
Definition: macharm.c:19

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;
1010  NTSTATUS Status;
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?
1036  ULONG IndexSize = FIELD_OFFSET(INDEX_BUFFER, Header)
1037  + IndexBuffer->Header.TotalSizeOfEntries
1038  + CurrentNodeEntry->Length;
1039  if (IndexSize > BufferSize)
1040  {
1041  DPRINT1("TODO: Adding file would require creating a new node!\n");
1042  return STATUS_NOT_IMPLEMENTED;
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 }
NTSTATUS AddFixupArray(PDEVICE_EXTENSION Vcb, PNTFS_RECORD_HEADER Record)
Definition: mft.c:2603
NTSYSAPI VOID NTAPI RtlCopyMemory(VOID UNALIGNED *Destination, CONST VOID UNALIGNED *Source, ULONG Length)
#define STATUS_NOT_IMPLEMENTED
Definition: ntstatus.h:225
LONG NTSTATUS
Definition: precomp.h:26
USHORT Length
Definition: ntfs.h:419
Definition: ntfs.h:404
ULONGLONG VCN
Definition: ntfs.h:400
USHORT KeyLength
Definition: ntfs.h:420
uint32_t ULONG_PTR
Definition: typedefs.h:63
ULONG FirstEntryOffset
Definition: ntfs.h:380
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
Definition: Header.h:8
INDEX_HEADER_ATTRIBUTE Header
Definition: ntfs.h:401
void DPRINT(...)
Definition: polytest.cpp:61
struct _B_TREE_KEY * NextKey
Definition: ntfs.h:432
#define BufferSize
Definition: classpnp.h:419
ASSERT((InvokeOnSuccess||InvokeOnError||InvokeOnCancel) ?(CompletionRoutine !=NULL) :TRUE)
ULONG TotalSizeOfEntries
Definition: ntfs.h:381
USHORT UsaCount
Definition: ntfs.h:237
#define NRH_INDX_TYPE
Definition: ntfs.h:243
Status
Definition: gdiplustypes.h:24
#define FIELD_OFFSET(t, f)
Definition: typedefs.h:254
#define DPRINT1
Definition: precomp.h:8
unsigned int ULONG
Definition: retypes.h:1
#define RtlZeroMemory(Destination, Length)
Definition: typedefs.h:261
NTFS_RECORD_HEADER Ntfs
Definition: ntfs.h:399
#define INDEX_NODE_LARGE
Definition: ntfs.h:212
PINDEX_ENTRY_ATTRIBUTE IndexEntry
Definition: ntfs.h:434
USHORT UsaOffset
Definition: ntfs.h:236
struct INDEX_ENTRY_ATTRIBUTE * PINDEX_ENTRY_ATTRIBUTE
Definition: dlist.c:348

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
926  DumpBTree(Tree);
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);
967  return STATUS_NOT_IMPLEMENTED;
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 }
ULONG CollationRule
Definition: ntfs.h:390
NTSYSAPI VOID NTAPI RtlCopyMemory(VOID UNALIGNED *Destination, CONST VOID UNALIGNED *Source, ULONG Length)
#define STATUS_INSUFFICIENT_RESOURCES
Definition: udferr_usr.h:158
#define STATUS_NOT_IMPLEMENTED
Definition: ntstatus.h:225
USHORT Length
Definition: ntfs.h:419
Definition: ntfs.h:404
USHORT KeyLength
Definition: ntfs.h:420
uint32_t ULONG_PTR
Definition: typedefs.h:63
ULONG FirstEntryOffset
Definition: ntfs.h:380
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
Definition: Header.h:8
void DPRINT(...)
Definition: polytest.cpp:61
struct _B_TREE_KEY * NextKey
Definition: ntfs.h:432
B_TREE_FILENAME_NODE * LesserChild
Definition: ntfs.h:433
ULONG SizeOfEntry
Definition: ntfs.h:391
ULONG AttributeType
Definition: ntfs.h:389
_In_ ULONG _In_ ULONG _In_ ULONG Length
Definition: ntddpcm.h:101
INDEX_HEADER_ATTRIBUTE Header
Definition: ntfs.h:394
CRegistryTree Tree
#define TAG_NTFS
Definition: ntfs.h:12
VOID DumpBTree(PB_TREE Tree)
Definition: btree.c:1622
ASSERT((InvokeOnSuccess||InvokeOnError||InvokeOnCancel) ?(CompletionRoutine !=NULL) :TRUE)
#define ExAllocatePoolWithTag(hernya, size, tag)
Definition: env_spec_w32.h:350
ULONG TotalSizeOfEntries
Definition: ntfs.h:381
#define INDEX_ROOT_LARGE
Definition: ntfs.h:209
UCHAR ClustersPerIndexRecord
Definition: ntfs.h:392
#define INDEX_ROOT_SMALL
Definition: ntfs.h:208
#define FIELD_OFFSET(t, f)
Definition: typedefs.h:254
#define DPRINT1
Definition: precomp.h:8
unsigned int ULONG
Definition: retypes.h:1
#define RtlZeroMemory(Destination, Length)
Definition: typedefs.h:261
PINDEX_ENTRY_ATTRIBUTE IndexEntry
Definition: ntfs.h:434
#define ExFreePoolWithTag(_P, _T)
Definition: module.h:1099
return STATUS_SUCCESS
Definition: btrfs.c:2938
#define COLLATION_FILE_NAME
Definition: ntfs.h:201
struct INDEX_ENTRY_ATTRIBUTE * PINDEX_ENTRY_ATTRIBUTE

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 }
#define TRUE
Definition: types.h:120
#define STATUS_INSUFFICIENT_RESOURCES
Definition: udferr_usr.h:158
PB_TREE_KEY FirstKey
Definition: ntfs.h:446
PB_TREE_KEY CreateDummyKey(BOOLEAN HasChildNode)
Definition: btree.c:289
void DPRINT(...)
Definition: polytest.cpp:61
B_TREE_FILENAME_NODE * LesserChild
Definition: ntfs.h:433
BOOLEAN DiskNeedsUpdating
Definition: ntfs.h:444
CRegistryTree Tree
#define TAG_NTFS
Definition: ntfs.h:12
VOID DumpBTree(PB_TREE Tree)
Definition: btree.c:1622
#define ExAllocatePoolWithTag(hernya, size, tag)
Definition: env_spec_w32.h:350
#define DPRINT1
Definition: precomp.h:8
#define RtlZeroMemory(Destination, Length)
Definition: typedefs.h:261
#define ExFreePoolWithTag(_P, _T)
Definition: module.h:1099
return STATUS_SUCCESS
Definition: btrfs.c:2938

Referenced by NtfsAddFilenameToDirectory().

◆ DestroyBTree()

VOID DestroyBTree ( PB_TREE  Tree)

Definition at line 1542 of file btree.c.

1543 {
1544  DestroyBTreeNode(Tree->RootNode);
1546 }
VOID DestroyBTreeNode(PB_TREE_FILENAME_NODE Node)
Definition: btree.c:1511
CRegistryTree Tree
#define TAG_NTFS
Definition: ntfs.h:12
#define ExFreePoolWithTag(_P, _T)
Definition: module.h:1099

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 }
VOID DestroyBTreeNode(PB_TREE_FILENAME_NODE Node)
Definition: btree.c:1511
#define TAG_NTFS
Definition: ntfs.h:12
#define ExFreePoolWithTag(_P, _T)
Definition: module.h:1099

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 }
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
smooth NULL
Definition: ftsmooth.c:416
struct _B_TREE_KEY * NextKey
Definition: ntfs.h:432
#define TAG_NTFS
Definition: ntfs.h:12
VOID DestroyBTreeKey(PB_TREE_KEY Key)
Definition: btree.c:1499
unsigned int ULONG
Definition: retypes.h:1
#define ExFreePoolWithTag(_P, _T)
Definition: module.h:1099
Definition: dlist.c:348
#define NT_ASSERT
Definition: rtlfuncs.h:3312

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 }
#define DbgPrint
Definition: loader.c:25
CRegistryTree Tree
VOID DumpBTreeNode(PB_TREE Tree, PB_TREE_FILENAME_NODE Node, ULONG Number, ULONG Depth)
Definition: btree.c:1583

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 }
_In_opt_ PALLOCATE_FUNCTION _In_opt_ PFREE_FUNCTION _In_ ULONG _In_ SIZE_T _In_ ULONG _In_ USHORT Depth
Definition: exfuncs.h:656
#define DbgPrint
Definition: loader.c:25
#define NTFS_INDEX_ENTRY_END
Definition: ntfs.h:61
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
__wchar_t WCHAR
Definition: xmlstorage.h:180
CRegistryTree Tree
_In_opt_ PENTER_STATE_SYSTEM_HANDLER _In_opt_ PVOID _In_ LONG _In_opt_ LONG volatile * Number
Definition: ntpoapi.h:204
#define NTFS_INDEX_ENTRY_NODE
Definition: ntfs.h:60
struct _FileName FileName
Definition: fatprocs.h:884
#define DPRINT1
Definition: precomp.h:8
unsigned int ULONG
Definition: retypes.h:1
VOID DumpBTreeNode(PB_TREE Tree, PB_TREE_FILENAME_NODE Node, ULONG Number, ULONG Depth)
Definition: btree.c:1583

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 }
_In_opt_ PALLOCATE_FUNCTION _In_opt_ PFREE_FUNCTION _In_ ULONG _In_ SIZE_T _In_ ULONG _In_ USHORT Depth
Definition: exfuncs.h:656
#define DbgPrint
Definition: loader.c:25
VOID DumpBTreeKey(PB_TREE Tree, PB_TREE_KEY Key, ULONG Number, ULONG Depth)
Definition: btree.c:1549
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
struct _B_TREE_KEY * NextKey
Definition: ntfs.h:432
CRegistryTree Tree
_In_opt_ PENTER_STATE_SYSTEM_HANDLER _In_opt_ PVOID _In_ LONG _In_opt_ LONG volatile * Number
Definition: ntpoapi.h:204
unsigned int ULONG
Definition: retypes.h:1
Definition: dlist.c:348

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 }
USHORT Length
Definition: ntfs.h:419
uint32_t ULONG_PTR
Definition: typedefs.h:63
uint64_t ULONGLONG
Definition: typedefs.h:65
_In_ PUNICODE_STRING _Inout_ PUNICODE_STRING Destination
Definition: rtlfuncs.h:2891
ASSERT((InvokeOnSuccess||InvokeOnError||InvokeOnCancel) ?(CompletionRoutine !=NULL) :TRUE)
USHORT Flags
Definition: ntfs.h:421
#define NTFS_INDEX_ENTRY_NODE
Definition: ntfs.h:60
__GNU_EXTENSION typedef unsigned __int64 * PULONGLONG
Definition: ntbasedef.h:390

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 }
USHORT Length
Definition: ntfs.h:419
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
struct _B_TREE_KEY * NextKey
Definition: ntfs.h:432
ASSERT((InvokeOnSuccess||InvokeOnError||InvokeOnCancel) ?(CompletionRoutine !=NULL) :TRUE)
unsigned int ULONG
Definition: retypes.h:1
PINDEX_ENTRY_ATTRIBUTE IndexEntry
Definition: ntfs.h:434
Definition: dlist.c:348

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  {
1830  NTSTATUS Status;
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 }
#define TRUE
Definition: types.h:120
#define STATUS_INSUFFICIENT_RESOURCES
Definition: udferr_usr.h:158
FILENAME_ATTRIBUTE FileName
Definition: ntfs.h:423
WCHAR Name[1]
Definition: ntfs.h:375
LONG NTSTATUS
Definition: precomp.h:26
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
UCHAR NameLength
Definition: ntfs.h:373
LONG CompareTreeKeys(PB_TREE_KEY Key1, PB_TREE_KEY Key2, BOOLEAN CaseSensitive)
Definition: btree.c:417
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
Definition: Header.h:8
long LONG
Definition: pedump.c:60
smooth NULL
Definition: ftsmooth.c:416
void DPRINT(...)
Definition: polytest.cpp:61
struct _B_TREE_KEY * NextKey
Definition: ntfs.h:432
B_TREE_FILENAME_NODE * LesserChild
Definition: ntfs.h:433
#define NT_SUCCESS(StatCode)
Definition: apphelp.c:32
CRegistryTree Tree
#define TAG_NTFS
Definition: ntfs.h:12
VOID DumpBTree(PB_TREE Tree)
Definition: btree.c:1622
ULONG GetSizeOfIndexEntries(PB_TREE_FILENAME_NODE Node)
Definition: btree.c:855
ASSERT((InvokeOnSuccess||InvokeOnError||InvokeOnCancel) ?(CompletionRoutine !=NULL) :TRUE)
Status
Definition: gdiplustypes.h:24
PB_TREE_KEY CreateBTreeKeyFromFilename(ULONGLONG FileReference, PFILENAME_ATTRIBUTE FileNameAttribute)
Definition: btree.c:1461
#define FIELD_OFFSET(t, f)
Definition: typedefs.h:254
#define DPRINT1
Definition: precomp.h:8
unsigned int ULONG
Definition: retypes.h:1
PINDEX_ENTRY_ATTRIBUTE IndexEntry
Definition: ntfs.h:434
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
#define ExFreePoolWithTag(_P, _T)
Definition: module.h:1099
return STATUS_SUCCESS
Definition: btrfs.c:2938
Definition: dlist.c:348

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);
46  ULONGLONG i;
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 }
signed char * PCHAR
Definition: retypes.h:7
LONG NTSTATUS
Definition: precomp.h:26
_Inout_ __drv_aliasesMem PSLIST_ENTRY _Inout_ PSLIST_ENTRY _In_ ULONG Count
Definition: exfuncs.h:1015
ULONGLONG VCN
Definition: ntfs.h:400
uint32_t ULONG_PTR
Definition: typedefs.h:63
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
Definition: bufpool.h:45
#define NT_SUCCESS(StatCode)
Definition: apphelp.c:32
uint64_t ULONGLONG
Definition: typedefs.h:65
#define Vcb
Definition: cdprocs.h:1425
#define BufferSize
Definition: classpnp.h:419
#define TAG_NTFS
Definition: ntfs.h:12
NTSTATUS FixupUpdateSequenceArray(PDEVICE_EXTENSION Vcb, PNTFS_RECORD_HEADER Record)
Definition: mft.c:1965
ASSERT((InvokeOnSuccess||InvokeOnError||InvokeOnCancel) ?(CompletionRoutine !=NULL) :TRUE)
#define ExAllocatePoolWithTag(hernya, size, tag)
Definition: env_spec_w32.h:350
Status
Definition: gdiplustypes.h:24
ULONG ReadAttribute(PDEVICE_EXTENSION Vcb, PNTFS_ATTR_CONTEXT Context, ULONGLONG Offset, PCHAR Buffer, ULONG Length)
Definition: mft.c:1065
struct INDEX_BUFFER * PINDEX_BUFFER
#define DPRINT1
Definition: precomp.h:8
unsigned int ULONG
Definition: retypes.h:1
NTFS_RECORD_HEADER Ntfs
Definition: ntfs.h:399
#define ExFreePoolWithTag(_P, _T)
Definition: module.h:1099
IN BOOLEAN OUT PSTR Buffer
Definition: progress.h:34
ULONGLONG AttributeDataLength(PNTFS_ATTR_RECORD AttrRecord)
Definition: mft.c:259
_Must_inspect_result_ _In_ PFILE_OBJECT _In_opt_ PLARGE_INTEGER _In_ ULONG _In_ FLT_IO_OPERATION_FLAGS _Out_opt_ PULONG BytesRead
Definition: fltkernel.h:1255

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 }
USHORT Length
Definition: ntfs.h:419
uint32_t ULONG_PTR
Definition: typedefs.h:63
uint64_t ULONGLONG
Definition: typedefs.h:65
_In_ PUNICODE_STRING _Inout_ PUNICODE_STRING Destination
Definition: rtlfuncs.h:2891
ASSERT((InvokeOnSuccess||InvokeOnError||InvokeOnCancel) ?(CompletionRoutine !=NULL) :TRUE)
USHORT Flags
Definition: ntfs.h:421
#define NTFS_INDEX_ENTRY_NODE
Definition: ntfs.h:60
__GNU_EXTENSION typedef unsigned __int64 * PULONGLONG
Definition: ntbasedef.h:390

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(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(Node, 0, 0);
2024 
2025  DPRINT1("Right-hand sibling node after split:\n");
2026  DumpBTreeNode(*NewRightHandSibling, 0, 0);
2027 #endif
2028 
2029  return STATUS_SUCCESS;
2030 }
ULONG CountBTreeKeys(PB_TREE_KEY FirstKey)
Definition: btree.c:484
#define TRUE
Definition: types.h:120
NTSYSAPI VOID NTAPI RtlCopyMemory(VOID UNALIGNED *Destination, CONST VOID UNALIGNED *Source, ULONG Length)
#define STATUS_INSUFFICIENT_RESOURCES
Definition: udferr_usr.h:158
#define BooleanFlagOn(F, SF)
Definition: ext2fs.h:183
USHORT Length
Definition: ntfs.h:419
Definition: ntfs.h:404
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
PB_TREE_KEY CreateDummyKey(BOOLEAN HasChildNode)
Definition: btree.c:289
union node Node
Definition: types.h:1255
smooth NULL
Definition: ftsmooth.c:416
void DPRINT(...)
Definition: polytest.cpp:61
struct _B_TREE_KEY * NextKey
Definition: ntfs.h:432
VOID SetIndexEntryVCN(PINDEX_ENTRY_ATTRIBUTE IndexEntry, ULONGLONG VCN)
Definition: btree.c:1172
ULONGLONG GetIndexEntryVCN(PINDEX_ENTRY_ATTRIBUTE IndexEntry)
Definition: btree.c:1641
uint64_t ULONGLONG
Definition: typedefs.h:65
CRegistryTree Tree
#define TAG_NTFS
Definition: ntfs.h:12
ASSERT((InvokeOnSuccess||InvokeOnError||InvokeOnCancel) ?(CompletionRoutine !=NULL) :TRUE)
#define ExAllocatePoolWithTag(hernya, size, tag)
Definition: env_spec_w32.h:350
#define NTFS_INDEX_ENTRY_NODE
Definition: ntfs.h:60
#define DPRINT1
Definition: precomp.h:8
unsigned int ULONG
Definition: retypes.h:1
#define RtlZeroMemory(Destination, Length)
Definition: typedefs.h:261
PINDEX_ENTRY_ATTRIBUTE IndexEntry
Definition: ntfs.h:434
#define ExFreePoolWithTag(_P, _T)
Definition: module.h:1099
VOID DumpBTreeNode(PB_TREE Tree, PB_TREE_FILENAME_NODE Node, ULONG Number, ULONG Depth)
Definition: btree.c:1583
return STATUS_SUCCESS
Definition: btrfs.c:2938
Definition: dlist.c:348

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;
1190  NTSTATUS Status;
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
1280  ExFreePoolWithTag(CurrentKey->IndexEntry, TAG_NTFS);
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 }
#define TRUE
Definition: types.h:120
NTSYSAPI VOID NTAPI RtlCopyMemory(VOID UNALIGNED *Destination, CONST VOID UNALIGNED *Source, ULONG Length)
#define STATUS_INSUFFICIENT_RESOURCES
Definition: udferr_usr.h:158
struct NTFS_ATTR_RECORD * PNTFS_ATTR_RECORD
#define BooleanFlagOn(F, SF)
Definition: ext2fs.h:183
VOID PrintAllVCNs(PDEVICE_EXTENSION Vcb, PNTFS_ATTR_CONTEXT IndexAllocationContext, ULONG NodeSize)
Definition: btree.c:38
LONG NTSTATUS
Definition: precomp.h:26
USHORT Length
Definition: ntfs.h:419
ULONG BytesInUse
Definition: ntfs.h:253
ULONGLONG VCN
Definition: ntfs.h:445
Definition: ntfs.h:404
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
uint32_t ULONG_PTR
Definition: typedefs.h:63
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
ULONG Length
Definition: ntfs.h:123
unsigned char BOOLEAN
void DPRINT(...)
Definition: polytest.cpp:61
struct _B_TREE_KEY * NextKey
Definition: ntfs.h:432
VOID SetIndexEntryVCN(PINDEX_ENTRY_ATTRIBUTE IndexEntry, ULONGLONG VCN)
Definition: btree.c:1172
B_TREE_FILENAME_NODE * LesserChild
Definition: ntfs.h:433
NTSTATUS AddBitmap(PNTFS_VCB Vcb, PFILE_RECORD_HEADER FileRecord, PNTFS_ATTR_RECORD AttributeAddress, PCWSTR Name, USHORT NameLength)
Definition: attrib.c:72
#define NT_SUCCESS(StatCode)
Definition: apphelp.c:32
uint64_t ULONGLONG
Definition: typedefs.h:65
CRegistryTree Tree
#define TAG_NTFS
Definition: ntfs.h:12
VOID DumpBTree(PB_TREE Tree)
Definition: btree.c:1622
#define ExAllocatePoolWithTag(hernya, size, tag)
Definition: env_spec_w32.h:350
USHORT Flags
Definition: ntfs.h:421
static const WCHAR L[]
Definition: oid.c:1250
NTSTATUS AddIndexAllocation(PNTFS_VCB Vcb, PFILE_RECORD_HEADER FileRecord, PNTFS_ATTR_RECORD AttributeAddress, PCWSTR Name, USHORT NameLength)
Definition: attrib.c:388
#define NTFS_INDEX_ENTRY_NODE
Definition: ntfs.h:60
Status
Definition: gdiplustypes.h:24
VOID ReleaseAttributeContext(PNTFS_ATTR_CONTEXT Context)
Definition: mft.c:104
#define DPRINT1
Definition: precomp.h:8
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
unsigned int ULONG
Definition: retypes.h:1
PINDEX_ENTRY_ATTRIBUTE IndexEntry
Definition: ntfs.h:434
#define ExFreePoolWithTag(_P, _T)
Definition: module.h:1099
return STATUS_SUCCESS
Definition: btrfs.c:2938

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;
1329  NTSTATUS Status;
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
1378  ExFreePoolWithTag(CurrentKey->IndexEntry, TAG_NTFS);
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 }
#define TRUE
Definition: types.h:120
NTSYSAPI VOID NTAPI RtlCopyMemory(VOID UNALIGNED *Destination, CONST VOID UNALIGNED *Source, ULONG Length)
#define STATUS_INSUFFICIENT_RESOURCES
Definition: udferr_usr.h:158
NTSTATUS AllocateIndexNode(PDEVICE_EXTENSION DeviceExt, PFILE_RECORD_HEADER FileRecord, ULONG IndexBufferSize, PNTFS_ATTR_CONTEXT IndexAllocationCtx, ULONG IndexAllocationOffset, PULONGLONG NewVCN)
Definition: btree.c:117
#define BooleanFlagOn(F, SF)
Definition: ext2fs.h:183
unsigned char * PUCHAR
Definition: retypes.h:3
LONG NTSTATUS
Definition: precomp.h:26
USHORT Length
Definition: ntfs.h:419
ULONGLONG VCN
Definition: ntfs.h:445
Definition: ntfs.h:404
#define STATUS_END_OF_FILE
Definition: shellext.h:67
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
unsigned char BOOLEAN
void DPRINT(...)
Definition: polytest.cpp:61
struct _B_TREE_KEY * NextKey
Definition: ntfs.h:432
VOID SetIndexEntryVCN(PINDEX_ENTRY_ATTRIBUTE IndexEntry, ULONGLONG VCN)
Definition: btree.c:1172
B_TREE_FILENAME_NODE * LesserChild
Definition: ntfs.h:433
#define NT_SUCCESS(StatCode)
Definition: apphelp.c:32
uint64_t ULONGLONG
Definition: typedefs.h:65
#define TAG_NTFS
Definition: ntfs.h:12
ASSERT((InvokeOnSuccess||InvokeOnError||InvokeOnCancel) ?(CompletionRoutine !=NULL) :TRUE)
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
#define ExAllocatePoolWithTag(hernya, size, tag)
Definition: env_spec_w32.h:350
USHORT Flags
Definition: ntfs.h:421
ULONGLONG GetAllocationOffsetFromVCN(PDEVICE_EXTENSION DeviceExt, ULONG IndexBufferSize, ULONGLONG Vcn)
Definition: btree.c:1630
#define NTFS_INDEX_ENTRY_NODE
Definition: ntfs.h:60
Status
Definition: gdiplustypes.h:24
NTSTATUS CreateIndexBufferFromBTreeNode(PDEVICE_EXTENSION DeviceExt, PB_TREE_FILENAME_NODE Node, ULONG BufferSize, BOOLEAN HasChildren, PINDEX_BUFFER IndexBuffer)
Definition: btree.c:1001
#define DPRINT1
Definition: precomp.h:8
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
unsigned int ULONG
Definition: retypes.h:1
PINDEX_ENTRY_ATTRIBUTE IndexEntry
Definition: ntfs.h:434
#define ExFreePoolWithTag(_P, _T)
Definition: module.h:1099
return STATUS_SUCCESS
Definition: btrfs.c:2938
Definition: dlist.c:348

Referenced by UpdateIndexAllocation(), and UpdateIndexNode().