3 * Copyright (C) 2002, 2017 ReactOS Team
5 * This program is free software; you can redistribute it and/or modify
6 * it under the terms of the GNU General Public License as published by
7 * the Free Software Foundation; either version 2 of the License, or
8 * (at your option) any later version.
10 * This program is distributed in the hope that it will be useful,
11 * but WITHOUT ANY WARRANTY; without even the implied warranty of
12 * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
13 * GNU General Public License for more details.
15 * You should have received a copy of the GNU General Public License
16 * along with this program; if not, write to the Free Software
17 * Foundation, Inc., 51 Franklin St, Fifth Floor, Boston, MA 02110-1301, USA.
19 * COPYRIGHT: See COPYING in the top level directory
20 * PROJECT: ReactOS kernel
21 * FILE: drivers/filesystem/ntfs/btree.c
22 * PURPOSE: NTFS filesystem driver
23 * PROGRAMMERS: Trevor Thompson
26 /* INCLUDES *****************************************************************/
33 /* FUNCTIONS ****************************************************************/
35 // TEMP FUNCTION for diagnostic purposes.
36 // Prints VCN of every node in an index allocation
38 PrintAllVCNs(PDEVICE_EXTENSION Vcb
,
39 PNTFS_ATTR_CONTEXT IndexAllocationContext
,
42 ULONGLONG CurrentOffset
= 0;
43 PINDEX_BUFFER CurrentNode
, Buffer
;
44 ULONGLONG BufferSize
= AttributeDataLength(IndexAllocationContext
->pRecord
);
51 DPRINT1("Index Allocation is empty.\n");
55 Buffer
= ExAllocatePoolWithTag(NonPagedPool
, BufferSize
, TAG_NTFS
);
57 BytesRead
= ReadAttribute(Vcb
, IndexAllocationContext
, 0, (PCHAR
)Buffer
, BufferSize
);
59 ASSERT(BytesRead
= BufferSize
);
63 // loop through all the nodes
64 for (i
= 0; i
< BufferSize
; i
+= NodeSize
)
66 NTSTATUS Status
= FixupUpdateSequenceArray(Vcb
, &CurrentNode
->Ntfs
);
67 if (!NT_SUCCESS(Status
))
69 DPRINT1("ERROR: Fixing fixup failed!\n");
73 DPRINT1("Node #%d, VCN: %I64u\n", Count
, CurrentNode
->VCN
);
75 CurrentNode
= (PINDEX_BUFFER
)((ULONG_PTR
)CurrentNode
+ NodeSize
);
76 CurrentOffset
+= NodeSize
;
80 ExFreePoolWithTag(Buffer
, TAG_NTFS
);
84 * @name CompareTreeKeys
87 * Compare two B_TREE_KEY's to determine their order in the tree.
90 * Pointer to a B_TREE_KEY that will be compared.
93 * Pointer to the other B_TREE_KEY that will be compared.
95 * @param CaseSensitive
96 * Boolean indicating if the function should operate in case-sensitive mode. This will be TRUE
97 * if an application created the file with the FILE_FLAG_POSIX_SEMANTICS flag.
100 * 0 if the two keys are equal.
101 * < 0 if key1 is less thank key2
102 * > 0 if key1 is greater than key2
105 * Any other key is always less than the final (dummy) key in a node. Key1 must not be the dummy node.
108 CompareTreeKeys(PB_TREE_KEY Key1
, PB_TREE_KEY Key2
, BOOLEAN CaseSensitive
)
110 UNICODE_STRING Key1Name
, Key2Name
;
113 // Key1 must not be the final key (AKA the dummy key)
114 ASSERT(!(Key1
->IndexEntry
->Flags
& NTFS_INDEX_ENTRY_END
));
116 // If Key2 is the "dummy key", key 1 will always come first
117 if (Key2
->NextKey
== NULL
)
120 Key1Name
.Buffer
= Key1
->IndexEntry
->FileName
.Name
;
121 Key1Name
.Length
= Key1Name
.MaximumLength
122 = Key1
->IndexEntry
->FileName
.NameLength
* sizeof(WCHAR
);
124 Key2Name
.Buffer
= Key2
->IndexEntry
->FileName
.Name
;
125 Key2Name
.Length
= Key2Name
.MaximumLength
126 = Key2
->IndexEntry
->FileName
.NameLength
* sizeof(WCHAR
);
128 // Are the two keys the same length?
129 if (Key1Name
.Length
== Key2Name
.Length
)
130 return RtlCompareUnicodeString(&Key1Name
, &Key2Name
, !CaseSensitive
);
133 if (Key1Name
.Length
< Key2Name
.Length
)
135 // Truncate KeyName2 to be the same length as KeyName1
136 Key2Name
.Length
= Key1Name
.Length
;
138 // Compare the names of the same length
139 Comparison
= RtlCompareUnicodeString(&Key1Name
, &Key2Name
, !CaseSensitive
);
141 // If the truncated names are the same length, the shorter one comes first
148 // Truncate KeyName1 to be the same length as KeyName2
149 Key1Name
.Length
= Key2Name
.Length
;
151 // Compare the names of the same length
152 Comparison
= RtlCompareUnicodeString(&Key1Name
, &Key2Name
, !CaseSensitive
);
154 // If the truncated names are the same length, the shorter one comes first
162 PB_TREE_FILENAME_NODE
163 CreateBTreeNodeFromIndexNode(PDEVICE_EXTENSION Vcb
,
164 PINDEX_ROOT_ATTRIBUTE IndexRoot
,
165 PNTFS_ATTR_CONTEXT IndexAllocationAttributeCtx
,
166 PINDEX_ENTRY_ATTRIBUTE NodeEntry
)
168 PB_TREE_FILENAME_NODE NewNode
;
169 PINDEX_ENTRY_ATTRIBUTE CurrentNodeEntry
;
170 PINDEX_ENTRY_ATTRIBUTE FirstNodeEntry
;
171 ULONG CurrentEntryOffset
= 0;
172 PINDEX_BUFFER NodeBuffer
;
173 ULONG IndexBufferSize
= Vcb
->NtfsInfo
.BytesPerIndexRecord
;
174 PULONGLONG NodeNumber
;
175 PB_TREE_KEY CurrentKey
;
177 ULONGLONG IndexNodeOffset
;
180 if (IndexAllocationAttributeCtx
== NULL
)
182 DPRINT1("ERROR: Couldn't find index allocation attribute even though there should be one!\n");
186 // Get the node number from the end of the node entry
187 NodeNumber
= (PULONGLONG
)((ULONG_PTR
)NodeEntry
+ NodeEntry
->Length
- sizeof(ULONGLONG
));
189 // Create the new tree node
190 DPRINT1("About to allocate %ld for NewNode\n", sizeof(B_TREE_FILENAME_NODE
));
191 NewNode
= ExAllocatePoolWithTag(NonPagedPool
, sizeof(B_TREE_FILENAME_NODE
), TAG_NTFS
);
194 DPRINT1("ERROR: Couldn't allocate memory for new filename node.\n");
197 RtlZeroMemory(NewNode
, sizeof(B_TREE_FILENAME_NODE
));
199 // Create the first key
200 CurrentKey
= ExAllocatePoolWithTag(NonPagedPool
, sizeof(B_TREE_KEY
), TAG_NTFS
);
203 DPRINT1("ERROR: Failed to allocate memory for key!\n");
204 ExFreePoolWithTag(NewNode
, TAG_NTFS
);
207 RtlZeroMemory(CurrentKey
, sizeof(B_TREE_KEY
));
208 NewNode
->FirstKey
= CurrentKey
;
210 // Allocate memory for the node buffer
211 NodeBuffer
= ExAllocatePoolWithTag(NonPagedPool
, IndexBufferSize
, TAG_NTFS
);
214 DPRINT1("ERROR: Couldn't allocate memory for node buffer!\n");
215 ExFreePoolWithTag(CurrentKey
, TAG_NTFS
);
216 ExFreePoolWithTag(NewNode
, TAG_NTFS
);
220 // Calculate offset into index allocation
221 IndexNodeOffset
= GetAllocationOffsetFromVCN(Vcb
, IndexBufferSize
, *NodeNumber
);
223 // TODO: Confirm index bitmap has this node marked as in-use
226 BytesRead
= ReadAttribute(Vcb
,
227 IndexAllocationAttributeCtx
,
232 ASSERT(BytesRead
== IndexBufferSize
);
233 NT_ASSERT(NodeBuffer
->Ntfs
.Type
== NRH_INDX_TYPE
);
234 NT_ASSERT(NodeBuffer
->VCN
== *NodeNumber
);
236 // Apply the fixup array to the node buffer
237 Status
= FixupUpdateSequenceArray(Vcb
, &NodeBuffer
->Ntfs
);
238 if (!NT_SUCCESS(Status
))
240 DPRINT1("ERROR: Couldn't apply fixup array to index node buffer!\n");
241 ExFreePoolWithTag(NodeBuffer
, TAG_NTFS
);
242 ExFreePoolWithTag(CurrentKey
, TAG_NTFS
);
243 ExFreePoolWithTag(NewNode
, TAG_NTFS
);
247 // Walk through the index and create keys for all the entries
248 FirstNodeEntry
= (PINDEX_ENTRY_ATTRIBUTE
)((ULONG_PTR
)(&NodeBuffer
->Header
)
249 + NodeBuffer
->Header
.FirstEntryOffset
);
250 CurrentNodeEntry
= FirstNodeEntry
;
251 while (CurrentEntryOffset
< NodeBuffer
->Header
.TotalSizeOfEntries
)
253 // Allocate memory for the current entry
254 CurrentKey
->IndexEntry
= ExAllocatePoolWithTag(NonPagedPool
, CurrentNodeEntry
->Length
, TAG_NTFS
);
255 if (!CurrentKey
->IndexEntry
)
257 DPRINT1("ERROR: Couldn't allocate memory for next key!\n");
258 DestroyBTreeNode(NewNode
);
259 ExFreePoolWithTag(NodeBuffer
, TAG_NTFS
);
265 // If this isn't the last entry
266 if (!(CurrentNodeEntry
->Flags
& NTFS_INDEX_ENTRY_END
))
268 // Create the next key
269 PB_TREE_KEY NextKey
= ExAllocatePoolWithTag(NonPagedPool
, sizeof(B_TREE_KEY
), TAG_NTFS
);
272 DPRINT1("ERROR: Couldn't allocate memory for next key!\n");
273 DestroyBTreeNode(NewNode
);
274 ExFreePoolWithTag(NodeBuffer
, TAG_NTFS
);
277 RtlZeroMemory(NextKey
, sizeof(B_TREE_KEY
));
279 // Add NextKey to the end of the list
280 CurrentKey
->NextKey
= NextKey
;
282 // Copy the current entry to its key
283 RtlCopyMemory(CurrentKey
->IndexEntry
, CurrentNodeEntry
, CurrentNodeEntry
->Length
);
285 // See if the current key has a sub-node
286 if (CurrentKey
->IndexEntry
->Flags
& NTFS_INDEX_ENTRY_NODE
)
288 DPRINT1("TODO: Only a node with a single-level is supported right now!\n");
290 CurrentKey
->LesserChild
= CreateBTreeNodeFromIndexNode(Vcb
,
292 IndexAllocationAttributeCtx
,
293 CurrentKey
->IndexEntry
);
296 CurrentKey
= NextKey
;
300 // Copy the final entry to its key
301 RtlCopyMemory(CurrentKey
->IndexEntry
, CurrentNodeEntry
, CurrentNodeEntry
->Length
);
302 CurrentKey
->NextKey
= NULL
;
304 // See if the current key has a sub-node
305 if (CurrentKey
->IndexEntry
->Flags
& NTFS_INDEX_ENTRY_NODE
)
307 DPRINT1("TODO: Only a node with a single-level is supported right now!\n");
309 CurrentKey
->LesserChild
= CreateBTreeNodeFromIndexNode(Vcb
,
311 IndexAllocationAttributeCtx
,
312 CurrentKey
->IndexEntry
);
318 // Advance to the next entry
319 CurrentEntryOffset
+= CurrentNodeEntry
->Length
;
320 CurrentNodeEntry
= (PINDEX_ENTRY_ATTRIBUTE
)((ULONG_PTR
)CurrentNodeEntry
+ CurrentNodeEntry
->Length
);
323 NewNode
->NodeNumber
= *NodeNumber
;
324 NewNode
->ExistsOnDisk
= TRUE
;
326 ExFreePoolWithTag(NodeBuffer
, TAG_NTFS
);
332 * @name CreateBTreeFromIndex
335 * Parse an index and create a B-Tree in memory from it.
337 * @param IndexRootContext
338 * Pointer to an NTFS_ATTR_CONTEXT that describes the location of the index root attribute.
341 * Pointer to a PB_TREE that will receive the pointer to a newly-created B-Tree.
344 * STATUS_SUCCESS on success.
345 * STATUS_INSUFFICIENT_RESOURCES if an allocation fails.
348 * Allocates memory for the entire tree. Caller is responsible for destroying the tree with DestroyBTree().
351 CreateBTreeFromIndex(PDEVICE_EXTENSION Vcb
,
352 PFILE_RECORD_HEADER FileRecordWithIndex
,
353 /*PCWSTR IndexName,*/
354 PNTFS_ATTR_CONTEXT IndexRootContext
,
355 PINDEX_ROOT_ATTRIBUTE IndexRoot
,
358 PINDEX_ENTRY_ATTRIBUTE CurrentNodeEntry
;
359 PB_TREE Tree
= ExAllocatePoolWithTag(NonPagedPool
, sizeof(B_TREE
), TAG_NTFS
);
360 PB_TREE_FILENAME_NODE RootNode
= ExAllocatePoolWithTag(NonPagedPool
, sizeof(B_TREE_FILENAME_NODE
), TAG_NTFS
);
361 PB_TREE_KEY CurrentKey
= ExAllocatePoolWithTag(NonPagedPool
, sizeof(B_TREE_KEY
), TAG_NTFS
);
362 ULONG CurrentOffset
= IndexRoot
->Header
.FirstEntryOffset
;
363 PNTFS_ATTR_CONTEXT IndexAllocationContext
= NULL
;
366 DPRINT1("CreateBTreeFromIndex(%p, %p)\n", IndexRoot
, NewTree
);
368 if (!Tree
|| !RootNode
|| !CurrentKey
)
370 DPRINT1("Couldn't allocate enough memory for B-Tree!\n");
372 ExFreePoolWithTag(Tree
, TAG_NTFS
);
374 ExFreePoolWithTag(CurrentKey
, TAG_NTFS
);
376 ExFreePoolWithTag(RootNode
, TAG_NTFS
);
377 return STATUS_INSUFFICIENT_RESOURCES
;
380 RtlZeroMemory(Tree
, sizeof(B_TREE
));
381 RtlZeroMemory(RootNode
, sizeof(B_TREE_FILENAME_NODE
));
382 RtlZeroMemory(CurrentKey
, sizeof(B_TREE_KEY
));
384 // See if the file record has an attribute allocation
385 Status
= FindAttribute(Vcb
,
387 AttributeIndexAllocation
,
390 &IndexAllocationContext
,
392 if (!NT_SUCCESS(Status
))
393 IndexAllocationContext
= NULL
;
395 PrintAllVCNs(Vcb
, IndexAllocationContext
, IndexRoot
->SizeOfEntry
);
398 RootNode
->FirstKey
= CurrentKey
;
399 Tree
->RootNode
= RootNode
;
401 // Make sure we won't try reading past the attribute-end
402 if (FIELD_OFFSET(INDEX_ROOT_ATTRIBUTE
, Header
) + IndexRoot
->Header
.TotalSizeOfEntries
> IndexRootContext
->pRecord
->Resident
.ValueLength
)
404 DPRINT1("Filesystem corruption detected!\n");
406 return STATUS_FILE_CORRUPT_ERROR
;
409 // Start at the first node entry
410 CurrentNodeEntry
= (PINDEX_ENTRY_ATTRIBUTE
)((ULONG_PTR
)IndexRoot
411 + FIELD_OFFSET(INDEX_ROOT_ATTRIBUTE
, Header
)
412 + IndexRoot
->Header
.FirstEntryOffset
);
414 // Create a key for each entry in the node
415 while (CurrentOffset
< IndexRoot
->Header
.TotalSizeOfEntries
)
417 // Allocate memory for the current entry
418 CurrentKey
->IndexEntry
= ExAllocatePoolWithTag(NonPagedPool
, CurrentNodeEntry
->Length
, TAG_NTFS
);
419 if (!CurrentKey
->IndexEntry
)
421 DPRINT1("ERROR: Couldn't allocate memory for next key!\n");
423 return STATUS_INSUFFICIENT_RESOURCES
;
426 RootNode
->KeyCount
++;
428 // If this isn't the last entry
429 if (!(CurrentNodeEntry
->Flags
& NTFS_INDEX_ENTRY_END
))
431 // Create the next key
432 PB_TREE_KEY NextKey
= ExAllocatePoolWithTag(NonPagedPool
, sizeof(B_TREE_KEY
), TAG_NTFS
);
435 DPRINT1("ERROR: Couldn't allocate memory for next key!\n");
437 return STATUS_INSUFFICIENT_RESOURCES
;
440 RtlZeroMemory(NextKey
, sizeof(B_TREE_KEY
));
442 // Add NextKey to the end of the list
443 CurrentKey
->NextKey
= NextKey
;
445 // Copy the current entry to its key
446 RtlCopyMemory(CurrentKey
->IndexEntry
, CurrentNodeEntry
, CurrentNodeEntry
->Length
);
448 // Does this key have a sub-node?
449 if (CurrentKey
->IndexEntry
->Flags
& NTFS_INDEX_ENTRY_NODE
)
451 // Create the child node
452 CurrentKey
->LesserChild
= CreateBTreeNodeFromIndexNode(Vcb
,
454 IndexAllocationContext
,
455 CurrentKey
->IndexEntry
);
456 if (!CurrentKey
->LesserChild
)
458 DPRINT1("ERROR: Couldn't create child node!\n");
460 return STATUS_NOT_IMPLEMENTED
;
464 // Advance to the next entry
465 CurrentOffset
+= CurrentNodeEntry
->Length
;
466 CurrentNodeEntry
= (PINDEX_ENTRY_ATTRIBUTE
)((ULONG_PTR
)CurrentNodeEntry
+ CurrentNodeEntry
->Length
);
467 CurrentKey
= NextKey
;
471 // Copy the final entry to its key
472 RtlCopyMemory(CurrentKey
->IndexEntry
, CurrentNodeEntry
, CurrentNodeEntry
->Length
);
473 CurrentKey
->NextKey
= NULL
;
475 // Does this key have a sub-node?
476 if (CurrentKey
->IndexEntry
->Flags
& NTFS_INDEX_ENTRY_NODE
)
478 // Create the child node
479 CurrentKey
->LesserChild
= CreateBTreeNodeFromIndexNode(Vcb
,
481 IndexAllocationContext
,
482 CurrentKey
->IndexEntry
);
483 if (!CurrentKey
->LesserChild
)
485 DPRINT1("ERROR: Couldn't create child node!\n");
487 return STATUS_NOT_IMPLEMENTED
;
497 if (IndexAllocationContext
)
498 ReleaseAttributeContext(IndexAllocationContext
);
500 return STATUS_SUCCESS
;
504 * @name CreateIndexRootFromBTree
507 * Parse a B-Tree in memory and convert it into an index that can be written to disk.
510 * Pointer to the DEVICE_EXTENSION of the target drive.
513 * Pointer to a B_TREE that describes the index to be written.
515 * @param MaxIndexSize
516 * Describes how large the index can be before it will take too much space in the file record.
517 * After reaching MaxIndexSize, an index can no longer be represented with just an index root
518 * attribute, and will require an index allocation and $I30 bitmap (TODO).
521 * Pointer to a PINDEX_ROOT_ATTRIBUTE that will receive a pointer to the newly-created index.
524 * Pointer to a ULONG which will receive the length of the new index root.
527 * STATUS_SUCCESS on success.
528 * STATUS_INSUFFICIENT_RESOURCES if an allocation fails.
529 * STATUS_NOT_IMPLEMENTED if the new index can't fit within MaxIndexSize.
532 * If the function succeeds, it's the caller's responsibility to free IndexRoot with ExFreePoolWithTag().
535 CreateIndexRootFromBTree(PDEVICE_EXTENSION DeviceExt
,
538 PINDEX_ROOT_ATTRIBUTE
*IndexRoot
,
542 PB_TREE_KEY CurrentKey
;
543 PINDEX_ENTRY_ATTRIBUTE CurrentNodeEntry
;
544 PINDEX_ROOT_ATTRIBUTE NewIndexRoot
= ExAllocatePoolWithTag(NonPagedPool
,
545 DeviceExt
->NtfsInfo
.BytesPerFileRecord
,
548 DPRINT1("CreateIndexRootFromBTree(%p, %p, 0x%lx, %p, %p)\n", DeviceExt
, Tree
, MaxIndexSize
, IndexRoot
, Length
);
552 DPRINT1("Failed to allocate memory for Index Root!\n");
553 return STATUS_INSUFFICIENT_RESOURCES
;
556 // Setup the new index root
557 RtlZeroMemory(NewIndexRoot
, DeviceExt
->NtfsInfo
.BytesPerFileRecord
);
559 NewIndexRoot
->AttributeType
= AttributeFileName
;
560 NewIndexRoot
->CollationRule
= COLLATION_FILE_NAME
;
561 NewIndexRoot
->SizeOfEntry
= DeviceExt
->NtfsInfo
.BytesPerIndexRecord
;
562 // If Bytes per index record is less than cluster size, clusters per index record becomes sectors per index
563 if (NewIndexRoot
->SizeOfEntry
< DeviceExt
->NtfsInfo
.BytesPerCluster
)
564 NewIndexRoot
->ClustersPerIndexRecord
= NewIndexRoot
->SizeOfEntry
/ DeviceExt
->NtfsInfo
.BytesPerSector
;
566 NewIndexRoot
->ClustersPerIndexRecord
= NewIndexRoot
->SizeOfEntry
/ DeviceExt
->NtfsInfo
.BytesPerCluster
;
568 // Setup the Index node header
569 NewIndexRoot
->Header
.FirstEntryOffset
= sizeof(INDEX_HEADER_ATTRIBUTE
);
570 NewIndexRoot
->Header
.Flags
= INDEX_ROOT_SMALL
;
572 // Start summing the total size of this node's entries
573 NewIndexRoot
->Header
.TotalSizeOfEntries
= NewIndexRoot
->Header
.FirstEntryOffset
;
575 // Setup each Node Entry
576 CurrentKey
= Tree
->RootNode
->FirstKey
;
577 CurrentNodeEntry
= (PINDEX_ENTRY_ATTRIBUTE
)((ULONG_PTR
)NewIndexRoot
578 + FIELD_OFFSET(INDEX_ROOT_ATTRIBUTE
, Header
)
579 + NewIndexRoot
->Header
.FirstEntryOffset
);
580 for (i
= 0; i
< Tree
->RootNode
->KeyCount
; i
++)
582 // Would adding the current entry to the index increase the index size beyond the limit we've set?
583 ULONG IndexSize
= FIELD_OFFSET(INDEX_ROOT_ATTRIBUTE
, Header
)
584 + NewIndexRoot
->Header
.TotalSizeOfEntries
585 + CurrentNodeEntry
->Length
;
586 if (IndexSize
> MaxIndexSize
)
588 DPRINT1("TODO: Adding file would require creating an index allocation!\n");
589 ExFreePoolWithTag(NewIndexRoot
, TAG_NTFS
);
590 return STATUS_NOT_IMPLEMENTED
;
593 ASSERT(CurrentKey
->IndexEntry
->Length
!= 0);
595 // Copy the index entry
596 RtlCopyMemory(CurrentNodeEntry
, CurrentKey
->IndexEntry
, CurrentKey
->IndexEntry
->Length
);
598 DPRINT1("Index Node Entry Stream Length: %u\nIndex Node Entry Length: %u\n",
599 CurrentNodeEntry
->KeyLength
,
600 CurrentNodeEntry
->Length
);
602 // Does the current key have any sub-nodes?
603 if (CurrentKey
->LesserChild
)
604 NewIndexRoot
->Header
.Flags
= INDEX_ROOT_LARGE
;
606 // Add Length of Current Entry to Total Size of Entries
607 NewIndexRoot
->Header
.TotalSizeOfEntries
+= CurrentNodeEntry
->Length
;
609 // Go to the next node entry
610 CurrentNodeEntry
= (PINDEX_ENTRY_ATTRIBUTE
)((ULONG_PTR
)CurrentNodeEntry
+ CurrentNodeEntry
->Length
);
612 CurrentKey
= CurrentKey
->NextKey
;
615 NewIndexRoot
->Header
.AllocatedSize
= NewIndexRoot
->Header
.TotalSizeOfEntries
;
617 *IndexRoot
= NewIndexRoot
;
618 *Length
= NewIndexRoot
->Header
.AllocatedSize
+ FIELD_OFFSET(INDEX_ROOT_ATTRIBUTE
, Header
);
620 return STATUS_SUCCESS
;
624 CreateIndexBufferFromBTreeNode(PDEVICE_EXTENSION DeviceExt
,
625 PB_TREE_FILENAME_NODE Node
,
627 PINDEX_BUFFER IndexBuffer
)
630 PB_TREE_KEY CurrentKey
;
631 PINDEX_ENTRY_ATTRIBUTE CurrentNodeEntry
;
634 // TODO: Fix magic, do math
635 RtlZeroMemory(IndexBuffer
, BufferSize
);
636 IndexBuffer
->Ntfs
.Type
= NRH_INDX_TYPE
;
637 IndexBuffer
->Ntfs
.UsaOffset
= 0x28;
638 IndexBuffer
->Ntfs
.UsaCount
= 9;
640 // TODO: Check bitmap for VCN
641 ASSERT(Node
->ExistsOnDisk
);
642 IndexBuffer
->VCN
= Node
->NodeNumber
;
644 IndexBuffer
->Header
.FirstEntryOffset
= 0x28;
645 IndexBuffer
->Header
.AllocatedSize
= BufferSize
- FIELD_OFFSET(INDEX_BUFFER
, Header
);
647 // Start summing the total size of this node's entries
648 IndexBuffer
->Header
.TotalSizeOfEntries
= IndexBuffer
->Header
.FirstEntryOffset
;
650 CurrentKey
= Node
->FirstKey
;
651 CurrentNodeEntry
= (PINDEX_ENTRY_ATTRIBUTE
)((ULONG_PTR
)&(IndexBuffer
->Header
)
652 + IndexBuffer
->Header
.FirstEntryOffset
);
653 for (i
= 0; i
< Node
->KeyCount
; i
++)
655 // Would adding the current entry to the index increase the node size beyond the allocation size?
656 ULONG IndexSize
= FIELD_OFFSET(INDEX_BUFFER
, Header
)
657 + IndexBuffer
->Header
.TotalSizeOfEntries
658 + CurrentNodeEntry
->Length
;
659 if (IndexSize
> BufferSize
)
661 DPRINT1("TODO: Adding file would require creating a new node!\n");
662 return STATUS_NOT_IMPLEMENTED
;
665 ASSERT(CurrentKey
->IndexEntry
->Length
!= 0);
667 // Copy the index entry
668 RtlCopyMemory(CurrentNodeEntry
, CurrentKey
->IndexEntry
, CurrentKey
->IndexEntry
->Length
);
670 DPRINT1("Index Node Entry Stream Length: %u\nIndex Node Entry Length: %u\n",
671 CurrentNodeEntry
->KeyLength
,
672 CurrentNodeEntry
->Length
);
674 // Add Length of Current Entry to Total Size of Entries
675 IndexBuffer
->Header
.TotalSizeOfEntries
+= CurrentNodeEntry
->Length
;
677 // TODO: Check for child nodes
679 // Go to the next node entry
680 CurrentNodeEntry
= (PINDEX_ENTRY_ATTRIBUTE
)((ULONG_PTR
)CurrentNodeEntry
+ CurrentNodeEntry
->Length
);
681 CurrentKey
= CurrentKey
->NextKey
;
684 Status
= AddFixupArray(DeviceExt
, &IndexBuffer
->Ntfs
);
690 UpdateIndexAllocation(PDEVICE_EXTENSION DeviceExt
,
692 ULONG IndexBufferSize
,
693 PFILE_RECORD_HEADER FileRecord
)
695 // Find the index allocation and bitmap
696 PNTFS_ATTR_CONTEXT IndexAllocationContext
, BitmapContext
;
697 PB_TREE_KEY CurrentKey
;
699 BOOLEAN HasIndexAllocation
= FALSE
;
702 DPRINT1("UpdateIndexAllocations() called.\n");
704 Status
= FindAttribute(DeviceExt
, FileRecord
, AttributeIndexAllocation
, L
"$I30", 4, &IndexAllocationContext
, NULL
);
705 if (NT_SUCCESS(Status
))
706 HasIndexAllocation
= TRUE
;
708 // TODO: Handle bitmap
709 BitmapContext
= NULL
;
711 // Walk through the root node and update all the sub-nodes
712 CurrentKey
= Tree
->RootNode
->FirstKey
;
713 for (i
= 0; i
< Tree
->RootNode
->KeyCount
; i
++)
715 if (CurrentKey
->LesserChild
)
717 if (!HasIndexAllocation
)
719 DPRINT1("FIXME: Need to add index allocation\n");
720 return STATUS_NOT_IMPLEMENTED
;
724 Status
= UpdateIndexNode(DeviceExt
, CurrentKey
->LesserChild
, IndexBufferSize
, IndexAllocationContext
, BitmapContext
);
725 if (!NT_SUCCESS(Status
))
727 DPRINT1("ERROR: Failed to update index node!\n");
728 ReleaseAttributeContext(IndexAllocationContext
);
734 CurrentKey
= CurrentKey
->NextKey
;
737 if(HasIndexAllocation
)
738 ReleaseAttributeContext(IndexAllocationContext
);
740 return STATUS_SUCCESS
;
744 UpdateIndexNode(PDEVICE_EXTENSION DeviceExt
,
745 PB_TREE_FILENAME_NODE Node
,
746 ULONG IndexBufferSize
,
747 PNTFS_ATTR_CONTEXT IndexAllocationContext
,
748 PNTFS_ATTR_CONTEXT BitmapContext
)
751 PB_TREE_KEY CurrentKey
= Node
->FirstKey
;
754 DPRINT1("UpdateIndexNode(%p, %p, %lu, %p, %p) called for index node with VCN %I64u\n", DeviceExt
, Node
, IndexBufferSize
, IndexAllocationContext
, BitmapContext
, Node
->NodeNumber
);
756 // Do we need to write this node to disk?
757 if (Node
->DiskNeedsUpdating
)
759 ULONGLONG NodeOffset
;
762 // Allocate memory for an index buffer
763 PINDEX_BUFFER IndexBuffer
= ExAllocatePoolWithTag(NonPagedPool
, IndexBufferSize
, TAG_NTFS
);
766 DPRINT1("ERROR: Failed to allocate %lu bytes for index buffer!\n", IndexBufferSize
);
767 return STATUS_INSUFFICIENT_RESOURCES
;
770 // Create the index buffer we'll be writing to disk to represent this node
771 Status
= CreateIndexBufferFromBTreeNode(DeviceExt
, Node
, IndexBufferSize
, IndexBuffer
);
772 if (!NT_SUCCESS(Status
))
774 DPRINT1("ERROR: Failed to create index buffer from node!\n");
775 ExFreePoolWithTag(IndexBuffer
, TAG_NTFS
);
779 // Get Offset of index buffer in index allocation
780 NodeOffset
= GetAllocationOffsetFromVCN(DeviceExt
, IndexBufferSize
, Node
->NodeNumber
);
782 // Write the buffer to the index allocation
783 Status
= WriteAttribute(DeviceExt
, IndexAllocationContext
, NodeOffset
, (const PUCHAR
)IndexBuffer
, IndexBufferSize
, &LengthWritten
, NULL
);
784 if (!NT_SUCCESS(Status
) || LengthWritten
!= IndexBufferSize
)
786 DPRINT1("ERROR: Failed to update index allocation!\n");
787 ExFreePoolWithTag(IndexBuffer
, TAG_NTFS
);
788 if (!NT_SUCCESS(Status
))
791 return STATUS_END_OF_FILE
;
794 Node
->DiskNeedsUpdating
= FALSE
;
796 // Free the index buffer
797 ExFreePoolWithTag(IndexBuffer
, TAG_NTFS
);
800 // Walk through the node and look for children to update
801 for (i
= 0; i
< Node
->KeyCount
; i
++)
805 // If there's a child node
806 if (CurrentKey
->LesserChild
)
808 // Update the child node on disk
809 Status
= UpdateIndexNode(DeviceExt
, CurrentKey
->LesserChild
, IndexBufferSize
, IndexAllocationContext
, BitmapContext
);
810 if (!NT_SUCCESS(Status
))
812 DPRINT1("ERROR: Failed to update child node!\n");
817 CurrentKey
= CurrentKey
->NextKey
;
820 return STATUS_SUCCESS
;
824 CreateBTreeKeyFromFilename(ULONGLONG FileReference
, PFILENAME_ATTRIBUTE FileNameAttribute
)
827 ULONG AttributeSize
= GetFileNameAttributeLength(FileNameAttribute
);
828 ULONG EntrySize
= ALIGN_UP_BY(AttributeSize
+ FIELD_OFFSET(INDEX_ENTRY_ATTRIBUTE
, FileName
), 8);
830 // Create a new Index Entry for the file
831 PINDEX_ENTRY_ATTRIBUTE NewEntry
= ExAllocatePoolWithTag(NonPagedPool
, EntrySize
, TAG_NTFS
);
834 DPRINT1("ERROR: Failed to allocate memory for Index Entry!\n");
838 // Setup the Index Entry
839 RtlZeroMemory(NewEntry
, EntrySize
);
840 NewEntry
->Data
.Directory
.IndexedFile
= FileReference
;
841 NewEntry
->Length
= EntrySize
;
842 NewEntry
->KeyLength
= AttributeSize
;
844 // Copy the FileNameAttribute
845 RtlCopyMemory(&NewEntry
->FileName
, FileNameAttribute
, AttributeSize
);
848 NewKey
= ExAllocatePoolWithTag(NonPagedPool
, sizeof(B_TREE_KEY
), TAG_NTFS
);
851 DPRINT1("ERROR: Failed to allocate memory for new key!\n");
852 ExFreePoolWithTag(NewEntry
, TAG_NTFS
);
855 NewKey
->IndexEntry
= NewEntry
;
856 NewKey
->NextKey
= NULL
;
862 DestroyBTreeKey(PB_TREE_KEY Key
)
865 ExFreePoolWithTag(Key
->IndexEntry
, TAG_NTFS
);
867 if (Key
->LesserChild
)
868 DestroyBTreeNode(Key
->LesserChild
);
870 ExFreePoolWithTag(Key
, TAG_NTFS
);
874 DestroyBTreeNode(PB_TREE_FILENAME_NODE Node
)
877 PB_TREE_KEY CurrentKey
= Node
->FirstKey
;
879 for (i
= 0; i
< Node
->KeyCount
; i
++)
881 NT_ASSERT(CurrentKey
);
882 NextKey
= CurrentKey
->NextKey
;
883 DestroyBTreeKey(CurrentKey
);
884 CurrentKey
= NextKey
;
887 NT_ASSERT(NextKey
== NULL
);
889 ExFreePoolWithTag(Node
, TAG_NTFS
);
899 * Pointer to the B_TREE which will be destroyed.
902 * Destroys every bit of data stored in the tree.
905 DestroyBTree(PB_TREE Tree
)
907 DestroyBTreeNode(Tree
->RootNode
);
908 ExFreePoolWithTag(Tree
, TAG_NTFS
);
912 DumpBTreeKey(PB_TREE_KEY Key
, ULONG Number
, ULONG Depth
)
915 for (i
= 0; i
< Depth
; i
++)
917 DbgPrint(" Key #%d", Number
);
919 if (!(Key
->IndexEntry
->Flags
& NTFS_INDEX_ENTRY_END
))
921 UNICODE_STRING FileName
;
922 FileName
.Length
= Key
->IndexEntry
->FileName
.NameLength
* sizeof(WCHAR
);
923 FileName
.MaximumLength
= FileName
.Length
;
924 FileName
.Buffer
= Key
->IndexEntry
->FileName
.Name
;
925 DbgPrint(" '%wZ'\n", &FileName
);
929 DbgPrint(" (Dummy Key)\n");
932 // Is there a child node?
933 if (Key
->IndexEntry
->Flags
& NTFS_INDEX_ENTRY_NODE
)
935 if (Key
->LesserChild
)
936 DumpBTreeNode(Key
->LesserChild
, Number
, Depth
+ 1);
939 // This will be an assert once nodes with arbitrary depth are debugged
940 DPRINT1("DRIVER ERROR: No Key->LesserChild despite Key->IndexEntry->Flags indicating this is a node!\n");
946 DumpBTreeNode(PB_TREE_FILENAME_NODE Node
, ULONG Number
, ULONG Depth
)
948 PB_TREE_KEY CurrentKey
;
950 for (i
= 0; i
< Depth
; i
++)
952 DbgPrint("Node #%d, Depth %d, has %d key%s\n", Number
, Depth
, Node
->KeyCount
, Node
->KeyCount
== 1 ? "" : "s");
954 CurrentKey
= Node
->FirstKey
;
955 for (i
= 1; i
<= Node
->KeyCount
; i
++)
957 DumpBTreeKey(CurrentKey
, i
, Depth
);
958 CurrentKey
= CurrentKey
->NextKey
;
969 * Pointer to the B_TREE which will be displayed.
972 * Displays a diagnostic summary of a B_TREE.
975 DumpBTree(PB_TREE Tree
)
977 DbgPrint("B_TREE @ %p\n", Tree
);
978 DumpBTreeNode(Tree
->RootNode
, 0, 0);
981 // Calculates start of Index Buffer relative to the index allocation, given the node's VCN
983 GetAllocationOffsetFromVCN(PDEVICE_EXTENSION DeviceExt
,
984 ULONG IndexBufferSize
,
987 if (IndexBufferSize
< DeviceExt
->NtfsInfo
.BytesPerCluster
)
988 return Vcn
* DeviceExt
->NtfsInfo
.BytesPerSector
;
990 return Vcn
* DeviceExt
->NtfsInfo
.BytesPerCluster
;
994 * @name NtfsInsertKey
997 * Inserts a FILENAME_ATTRIBUTE into a B-Tree node.
999 * @param FileReference
1000 * Reference number to the file being added. This will be a combination of the MFT index and update sequence number.
1002 * @param FileNameAttribute
1003 * Pointer to a FILENAME_ATTRIBUTE which is the data for the key that will be added to the tree. A copy will be made.
1006 * Pointer to a B_TREE_FILENAME_NODE into which a new key will be inserted, in order.
1008 * @param CaseSensitive
1009 * Boolean indicating if the function should operate in case-sensitive mode. This will be TRUE
1010 * if an application created the file with the FILE_FLAG_POSIX_SEMANTICS flag.
1013 * A node is always sorted, with the least comparable filename stored first and a dummy key to mark the end.
1016 NtfsInsertKey(ULONGLONG FileReference
,
1017 PFILENAME_ATTRIBUTE FileNameAttribute
,
1018 PB_TREE_FILENAME_NODE Node
,
1019 BOOLEAN CaseSensitive
)
1021 PB_TREE_KEY NewKey
, CurrentKey
, PreviousKey
;
1022 NTSTATUS Status
= STATUS_SUCCESS
;
1024 ULONG AllocatedNodeSize
;
1025 ULONG MaxNodeSizeWithoutHeader
;
1028 DPRINT1("NtfsInsertKey(0x%I64x, %p, %p, %s)\n",
1032 CaseSensitive
? "TRUE" : "FALSE");
1034 // Create the key for the filename attribute
1035 NewKey
= CreateBTreeKeyFromFilename(FileReference
, FileNameAttribute
);
1037 return STATUS_INSUFFICIENT_RESOURCES
;
1039 // Find where to insert the key
1040 CurrentKey
= Node
->FirstKey
;
1042 for (i
= 0; i
< Node
->KeyCount
; i
++)
1044 // Should the New Key go before the current key?
1045 LONG Comparison
= CompareTreeKeys(NewKey
, CurrentKey
, CaseSensitive
);
1047 ASSERT(Comparison
!= 0);
1049 // Is NewKey < CurrentKey?
1053 // Does CurrentKey have a sub-node?
1054 if (CurrentKey
->LesserChild
)
1056 // Insert the key into the child node
1057 Status
= NtfsInsertKey(FileReference
, FileNameAttribute
, CurrentKey
->LesserChild
, CaseSensitive
);
1061 // Insert New Key before Current Key
1062 NewKey
->NextKey
= CurrentKey
;
1064 // Increase KeyCount and mark node as dirty
1066 Node
->DiskNeedsUpdating
= TRUE
;
1068 // was CurrentKey the first key?
1069 if (CurrentKey
== Node
->FirstKey
)
1070 Node
->FirstKey
= NewKey
;
1072 PreviousKey
->NextKey
= NewKey
;
1077 PreviousKey
= CurrentKey
;
1078 CurrentKey
= CurrentKey
->NextKey
;
1081 // Is the node larger than its allocated size?
1083 CurrentKey
= Node
->FirstKey
;
1084 for (i
= 0; i
< Node
->KeyCount
; i
++)
1086 NodeSize
+= CurrentKey
->IndexEntry
->Length
;
1087 CurrentKey
= CurrentKey
->NextKey
;
1090 // TEMPTEMP: TODO: MATH
1091 AllocatedNodeSize
= 0xfe8;
1092 MaxNodeSizeWithoutHeader
= AllocatedNodeSize
- 0x28;
1094 if (NodeSize
> MaxNodeSizeWithoutHeader
)
1096 DPRINT1("FIXME: Splitting a node is still a WIP!\n");
1097 //SplitBTreeNode(NULL, Node);
1099 return STATUS_NOT_IMPLEMENTED
;
1102 // NewEntry and NewKey will be destroyed later by DestroyBTree()