ReactOS 0.4.15-dev-7842-g558ab78
btree.c
Go to the documentation of this file.
1/*
2* ReactOS kernel
3* Copyright (C) 2002, 2017 ReactOS Team
4*
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.
9*
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.
14*
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.
18*
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
24*/
25
26/* INCLUDES *****************************************************************/
27
28#include "ntfs.h"
29
30#define NDEBUG
31#include <debug.h>
32
33/* FUNCTIONS ****************************************************************/
34
35// TEMP FUNCTION for diagnostic purposes.
36// Prints VCN of every node in an index allocation
37VOID
39 PNTFS_ATTR_CONTEXT IndexAllocationContext,
40 ULONG NodeSize)
41{
42 ULONGLONG CurrentOffset = 0;
43 PINDEX_BUFFER CurrentNode, Buffer;
44 ULONGLONG BufferSize = AttributeDataLength(IndexAllocationContext->pRecord);
47 int Count = 0;
48
49 if (BufferSize == 0)
50 {
51 DPRINT1("Index Allocation is empty.\n");
52 return;
53 }
54
56
57 BytesRead = ReadAttribute(Vcb, IndexAllocationContext, 0, (PCHAR)Buffer, BufferSize);
58
60
61 CurrentNode = Buffer;
62
63 // loop through all the nodes
64 for (i = 0; i < BufferSize; i += NodeSize)
65 {
67 if (!NT_SUCCESS(Status))
68 {
69 DPRINT1("ERROR: Fixing fixup failed!\n");
70 continue;
71 }
72
73 DPRINT1("Node #%d, VCN: %I64u\n", Count, CurrentNode->VCN);
74
75 CurrentNode = (PINDEX_BUFFER)((ULONG_PTR)CurrentNode + NodeSize);
76 CurrentOffset += NodeSize;
77 Count++;
78 }
79
81}
82
118 PFILE_RECORD_HEADER FileRecord,
119 ULONG IndexBufferSize,
120 PNTFS_ATTR_CONTEXT IndexAllocationCtx,
121 ULONG IndexAllocationOffset,
122 PULONGLONG NewVCN)
123{
125 PNTFS_ATTR_CONTEXT BitmapCtx;
126 ULONGLONG IndexAllocationLength, BitmapLength;
127 ULONG BitmapOffset;
128 ULONGLONG NextNodeNumber;
129 PCHAR *BitmapMem;
130 ULONG *BitmapPtr;
133 ULONG BytesNeeded;
135
136 DPRINT1("AllocateIndexNode(%p, %p, %lu, %p, %lu, %p) called.\n", DeviceExt,
137 FileRecord,
138 IndexBufferSize,
139 IndexAllocationCtx,
140 IndexAllocationOffset,
141 NewVCN);
142
143 // Get the length of the attribute allocation
144 IndexAllocationLength = AttributeDataLength(IndexAllocationCtx->pRecord);
145
146 // Find the bitmap attribute for the index
147 Status = FindAttribute(DeviceExt,
148 FileRecord,
150 L"$I30",
151 4,
152 &BitmapCtx,
153 &BitmapOffset);
154 if (!NT_SUCCESS(Status))
155 {
156 DPRINT1("FIXME: Need to add bitmap attribute!\n");
158 }
159
160 // Get the length of the bitmap attribute
161 BitmapLength = AttributeDataLength(BitmapCtx->pRecord);
162
163 NextNodeNumber = IndexAllocationLength / DeviceExt->NtfsInfo.BytesPerIndexRecord;
164
165 // TODO: Find unused allocation in bitmap and use that space first
166
167 // Add another bit to bitmap
168
169 // See how many bytes we need to store the amount of bits we'll have
170 BytesNeeded = NextNodeNumber / 8;
171 BytesNeeded++;
172
173 // Windows seems to allocate the bitmap in 8-byte chunks to keep any bytes from being wasted on padding
174 BytesNeeded = ALIGN_UP(BytesNeeded, ATTR_RECORD_ALIGNMENT);
175
176 // Allocate memory for the bitmap, including some padding; RtlInitializeBitmap() wants a pointer
177 // that's ULONG-aligned, and it wants the size of the memory allocated for it to be a ULONG-multiple.
178 BitmapMem = ExAllocatePoolWithTag(NonPagedPool, BytesNeeded + sizeof(ULONG), TAG_NTFS);
179 if (!BitmapMem)
180 {
181 DPRINT1("Error: failed to allocate bitmap!");
182 ReleaseAttributeContext(BitmapCtx);
184 }
185 // RtlInitializeBitmap() wants a pointer that's ULONG-aligned.
186 BitmapPtr = (PULONG)ALIGN_UP_BY((ULONG_PTR)BitmapMem, sizeof(ULONG));
187
188 RtlZeroMemory(BitmapPtr, BytesNeeded);
189
190 // Read the existing bitmap data
191 Status = ReadAttribute(DeviceExt, BitmapCtx, 0, (PCHAR)BitmapPtr, BitmapLength);
192
193 // Initialize bitmap
194 RtlInitializeBitMap(&Bitmap, BitmapPtr, NextNodeNumber);
195
196 // Do we need to enlarge the bitmap?
197 if (BytesNeeded > BitmapLength)
198 {
199 // TODO: handle synchronization issues that could occur from changing the directory's file record
200 // Change bitmap size
201 DataSize.QuadPart = BytesNeeded;
202 if (BitmapCtx->pRecord->IsNonResident)
203 {
205 BitmapCtx,
206 BitmapOffset,
207 FileRecord,
208 &DataSize);
209 }
210 else
211 {
213 BitmapCtx,
214 BitmapOffset,
215 FileRecord,
216 &DataSize);
217 }
218 if (!NT_SUCCESS(Status))
219 {
220 DPRINT1("ERROR: Failed to set length of bitmap attribute!\n");
221 ReleaseAttributeContext(BitmapCtx);
222 return Status;
223 }
224 }
225
226 // Enlarge Index Allocation attribute
227 DataSize.QuadPart = IndexAllocationLength + IndexBufferSize;
229 IndexAllocationCtx,
230 IndexAllocationOffset,
231 FileRecord,
232 &DataSize);
233 if (!NT_SUCCESS(Status))
234 {
235 DPRINT1("ERROR: Failed to set length of index allocation!\n");
236 ReleaseAttributeContext(BitmapCtx);
237 return Status;
238 }
239
240 // Update file record on disk
241 Status = UpdateFileRecord(DeviceExt, IndexAllocationCtx->FileMFTIndex, FileRecord);
242 if (!NT_SUCCESS(Status))
243 {
244 DPRINT1("ERROR: Failed to update file record!\n");
245 ReleaseAttributeContext(BitmapCtx);
246 return Status;
247 }
248
249 // Set the bit for the new index record
250 RtlSetBits(&Bitmap, NextNodeNumber, 1);
251
252 // Write the new bitmap attribute
253 Status = WriteAttribute(DeviceExt,
254 BitmapCtx,
255 0,
256 (const PUCHAR)BitmapPtr,
257 BytesNeeded,
259 FileRecord);
260 if (!NT_SUCCESS(Status))
261 {
262 DPRINT1("ERROR: Unable to write to $I30 bitmap attribute!\n");
263 }
264
265 // Calculate VCN of new node number
266 *NewVCN = NextNodeNumber * (IndexBufferSize / DeviceExt->NtfsInfo.BytesPerCluster);
267
268 DPRINT("New VCN: %I64u\n", *NewVCN);
269
270 ExFreePoolWithTag(BitmapMem, TAG_NTFS);
271 ReleaseAttributeContext(BitmapCtx);
272
273 return Status;
274}
275
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}
334
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}
391
416LONG
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}
470
483ULONG
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}
497
500 PINDEX_ROOT_ATTRIBUTE IndexRoot,
501 PNTFS_ATTR_CONTEXT IndexAllocationAttributeCtx,
502 PINDEX_ENTRY_ATTRIBUTE NodeEntry)
503{
504 PB_TREE_FILENAME_NODE NewNode;
505 PINDEX_ENTRY_ATTRIBUTE CurrentNodeEntry;
506 PINDEX_ENTRY_ATTRIBUTE FirstNodeEntry;
507 ULONG CurrentEntryOffset = 0;
508 PINDEX_BUFFER NodeBuffer;
509 ULONG IndexBufferSize = Vcb->NtfsInfo.BytesPerIndexRecord;
510 PULONGLONG VCN;
511 PB_TREE_KEY CurrentKey;
513 ULONGLONG IndexNodeOffset;
515
516 if (IndexAllocationAttributeCtx == NULL)
517 {
518 DPRINT1("ERROR: Couldn't find index allocation attribute even though there should be one!\n");
519 return NULL;
520 }
521
522 // Get the node number from the end of the node entry
523 VCN = (PULONGLONG)((ULONG_PTR)NodeEntry + NodeEntry->Length - sizeof(ULONGLONG));
524
525 // Create the new tree node
527 if (!NewNode)
528 {
529 DPRINT1("ERROR: Couldn't allocate memory for new filename node.\n");
530 return NULL;
531 }
532 RtlZeroMemory(NewNode, sizeof(B_TREE_FILENAME_NODE));
533
534 // Create the first key
536 if (!CurrentKey)
537 {
538 DPRINT1("ERROR: Failed to allocate memory for key!\n");
539 ExFreePoolWithTag(NewNode, TAG_NTFS);
540 return NULL;
541 }
542 RtlZeroMemory(CurrentKey, sizeof(B_TREE_KEY));
543 NewNode->FirstKey = CurrentKey;
544
545 // Allocate memory for the node buffer
546 NodeBuffer = ExAllocatePoolWithTag(NonPagedPool, IndexBufferSize, TAG_NTFS);
547 if (!NodeBuffer)
548 {
549 DPRINT1("ERROR: Couldn't allocate memory for node buffer!\n");
550 ExFreePoolWithTag(CurrentKey, TAG_NTFS);
551 ExFreePoolWithTag(NewNode, TAG_NTFS);
552 return NULL;
553 }
554
555 // Calculate offset into index allocation
556 IndexNodeOffset = GetAllocationOffsetFromVCN(Vcb, IndexBufferSize, *VCN);
557
558 // TODO: Confirm index bitmap has this node marked as in-use
559
560 // Read the node
562 IndexAllocationAttributeCtx,
563 IndexNodeOffset,
564 (PCHAR)NodeBuffer,
565 IndexBufferSize);
566
567 ASSERT(BytesRead == IndexBufferSize);
568 NT_ASSERT(NodeBuffer->Ntfs.Type == NRH_INDX_TYPE);
569 NT_ASSERT(NodeBuffer->VCN == *VCN);
570
571 // Apply the fixup array to the node buffer
572 Status = FixupUpdateSequenceArray(Vcb, &NodeBuffer->Ntfs);
573 if (!NT_SUCCESS(Status))
574 {
575 DPRINT1("ERROR: Couldn't apply fixup array to index node buffer!\n");
576 ExFreePoolWithTag(NodeBuffer, TAG_NTFS);
577 ExFreePoolWithTag(CurrentKey, TAG_NTFS);
578 ExFreePoolWithTag(NewNode, TAG_NTFS);
579 return NULL;
580 }
581
582 // Walk through the index and create keys for all the entries
583 FirstNodeEntry = (PINDEX_ENTRY_ATTRIBUTE)((ULONG_PTR)(&NodeBuffer->Header)
584 + NodeBuffer->Header.FirstEntryOffset);
585 CurrentNodeEntry = FirstNodeEntry;
586 while (CurrentEntryOffset < NodeBuffer->Header.TotalSizeOfEntries)
587 {
588 // Allocate memory for the current entry
589 CurrentKey->IndexEntry = ExAllocatePoolWithTag(NonPagedPool, CurrentNodeEntry->Length, TAG_NTFS);
590 if (!CurrentKey->IndexEntry)
591 {
592 DPRINT1("ERROR: Couldn't allocate memory for next key!\n");
593 DestroyBTreeNode(NewNode);
594 ExFreePoolWithTag(NodeBuffer, TAG_NTFS);
595 return NULL;
596 }
597
598 NewNode->KeyCount++;
599
600 // If this isn't the last entry
601 if (!(CurrentNodeEntry->Flags & NTFS_INDEX_ENTRY_END))
602 {
603 // Create the next key
605 if (!NextKey)
606 {
607 DPRINT1("ERROR: Couldn't allocate memory for next key!\n");
608 DestroyBTreeNode(NewNode);
609 ExFreePoolWithTag(NodeBuffer, TAG_NTFS);
610 return NULL;
611 }
612 RtlZeroMemory(NextKey, sizeof(B_TREE_KEY));
613
614 // Add NextKey to the end of the list
615 CurrentKey->NextKey = NextKey;
616
617 // Copy the current entry to its key
618 RtlCopyMemory(CurrentKey->IndexEntry, CurrentNodeEntry, CurrentNodeEntry->Length);
619
620 // See if the current key has a sub-node
621 if (CurrentKey->IndexEntry->Flags & NTFS_INDEX_ENTRY_NODE)
622 {
624 IndexRoot,
625 IndexAllocationAttributeCtx,
626 CurrentKey->IndexEntry);
627 }
628
629 CurrentKey = NextKey;
630 }
631 else
632 {
633 // Copy the final entry to its key
634 RtlCopyMemory(CurrentKey->IndexEntry, CurrentNodeEntry, CurrentNodeEntry->Length);
635 CurrentKey->NextKey = NULL;
636
637 // See if the current key has a sub-node
638 if (CurrentKey->IndexEntry->Flags & NTFS_INDEX_ENTRY_NODE)
639 {
641 IndexRoot,
642 IndexAllocationAttributeCtx,
643 CurrentKey->IndexEntry);
644 }
645
646 break;
647 }
648
649 // Advance to the next entry
650 CurrentEntryOffset += CurrentNodeEntry->Length;
651 CurrentNodeEntry = (PINDEX_ENTRY_ATTRIBUTE)((ULONG_PTR)CurrentNodeEntry + CurrentNodeEntry->Length);
652 }
653
654 NewNode->VCN = *VCN;
655 NewNode->HasValidVCN = TRUE;
656
657 ExFreePoolWithTag(NodeBuffer, TAG_NTFS);
658
659 return NewNode;
660}
661
683 PFILE_RECORD_HEADER FileRecordWithIndex,
684 /*PCWSTR IndexName,*/
685 PNTFS_ATTR_CONTEXT IndexRootContext,
686 PINDEX_ROOT_ATTRIBUTE IndexRoot,
687 PB_TREE *NewTree)
688{
689 PINDEX_ENTRY_ATTRIBUTE CurrentNodeEntry;
693 ULONG CurrentOffset = IndexRoot->Header.FirstEntryOffset;
694 PNTFS_ATTR_CONTEXT IndexAllocationContext = NULL;
696
697 DPRINT("CreateBTreeFromIndex(%p, %p)\n", IndexRoot, NewTree);
698
699 if (!Tree || !RootNode || !CurrentKey)
700 {
701 DPRINT1("Couldn't allocate enough memory for B-Tree!\n");
702 if (Tree)
704 if (CurrentKey)
705 ExFreePoolWithTag(CurrentKey, TAG_NTFS);
706 if (RootNode)
709 }
710
711 RtlZeroMemory(Tree, sizeof(B_TREE));
713 RtlZeroMemory(CurrentKey, sizeof(B_TREE_KEY));
714
715 // See if the file record has an attribute allocation
717 FileRecordWithIndex,
719 L"$I30",
720 4,
721 &IndexAllocationContext,
722 NULL);
723 if (!NT_SUCCESS(Status))
724 IndexAllocationContext = NULL;
725
726 // Setup the Tree
727 RootNode->FirstKey = CurrentKey;
728 Tree->RootNode = RootNode;
729
730 // Make sure we won't try reading past the attribute-end
731 if (FIELD_OFFSET(INDEX_ROOT_ATTRIBUTE, Header) + IndexRoot->Header.TotalSizeOfEntries > IndexRootContext->pRecord->Resident.ValueLength)
732 {
733 DPRINT1("Filesystem corruption detected!\n");
736 goto Cleanup;
737 }
738
739 // Start at the first node entry
740 CurrentNodeEntry = (PINDEX_ENTRY_ATTRIBUTE)((ULONG_PTR)IndexRoot
742 + IndexRoot->Header.FirstEntryOffset);
743
744 // Create a key for each entry in the node
745 while (CurrentOffset < IndexRoot->Header.TotalSizeOfEntries)
746 {
747 // Allocate memory for the current entry
748 CurrentKey->IndexEntry = ExAllocatePoolWithTag(NonPagedPool, CurrentNodeEntry->Length, TAG_NTFS);
749 if (!CurrentKey->IndexEntry)
750 {
751 DPRINT1("ERROR: Couldn't allocate memory for next key!\n");
754 goto Cleanup;
755 }
756
757 RootNode->KeyCount++;
758
759 // If this isn't the last entry
760 if (!(CurrentNodeEntry->Flags & NTFS_INDEX_ENTRY_END))
761 {
762 // Create the next key
764 if (!NextKey)
765 {
766 DPRINT1("ERROR: Couldn't allocate memory for next key!\n");
769 goto Cleanup;
770 }
771
772 RtlZeroMemory(NextKey, sizeof(B_TREE_KEY));
773
774 // Add NextKey to the end of the list
775 CurrentKey->NextKey = NextKey;
776
777 // Copy the current entry to its key
778 RtlCopyMemory(CurrentKey->IndexEntry, CurrentNodeEntry, CurrentNodeEntry->Length);
779
780 // Does this key have a sub-node?
781 if (CurrentKey->IndexEntry->Flags & NTFS_INDEX_ENTRY_NODE)
782 {
783 // Create the child node
785 IndexRoot,
786 IndexAllocationContext,
787 CurrentKey->IndexEntry);
788 if (!CurrentKey->LesserChild)
789 {
790 DPRINT1("ERROR: Couldn't create child node!\n");
793 goto Cleanup;
794 }
795 }
796
797 // Advance to the next entry
798 CurrentOffset += CurrentNodeEntry->Length;
799 CurrentNodeEntry = (PINDEX_ENTRY_ATTRIBUTE)((ULONG_PTR)CurrentNodeEntry + CurrentNodeEntry->Length);
800 CurrentKey = NextKey;
801 }
802 else
803 {
804 // Copy the final entry to its key
805 RtlCopyMemory(CurrentKey->IndexEntry, CurrentNodeEntry, CurrentNodeEntry->Length);
806 CurrentKey->NextKey = NULL;
807
808 // Does this key have a sub-node?
809 if (CurrentKey->IndexEntry->Flags & NTFS_INDEX_ENTRY_NODE)
810 {
811 // Create the child node
813 IndexRoot,
814 IndexAllocationContext,
815 CurrentKey->IndexEntry);
816 if (!CurrentKey->LesserChild)
817 {
818 DPRINT1("ERROR: Couldn't create child node!\n");
821 goto Cleanup;
822 }
823 }
824
825 break;
826 }
827 }
828
829 *NewTree = Tree;
831
832Cleanup:
833 if (IndexAllocationContext)
834 ReleaseAttributeContext(IndexAllocationContext);
835
836 return Status;
837}
838
854ULONG
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}
874
912 ULONG MaxIndexSize,
913 PINDEX_ROOT_ATTRIBUTE *IndexRoot,
914 ULONG *Length)
915{
916 ULONG i;
917 PB_TREE_KEY CurrentKey;
918 PINDEX_ENTRY_ATTRIBUTE CurrentNodeEntry;
920 DeviceExt->NtfsInfo.BytesPerFileRecord,
921 TAG_NTFS);
922
923 DPRINT("CreateIndexRootFromBTree(%p, %p, 0x%lx, %p, %p)\n", DeviceExt, Tree, MaxIndexSize, IndexRoot, Length);
924
925#ifndef NDEBUG
927#endif
928
929 if (!NewIndexRoot)
930 {
931 DPRINT1("Failed to allocate memory for Index Root!\n");
933 }
934
935 // Setup the new index root
936 RtlZeroMemory(NewIndexRoot, DeviceExt->NtfsInfo.BytesPerFileRecord);
937
938 NewIndexRoot->AttributeType = AttributeFileName;
939 NewIndexRoot->CollationRule = COLLATION_FILE_NAME;
940 NewIndexRoot->SizeOfEntry = DeviceExt->NtfsInfo.BytesPerIndexRecord;
941 // If Bytes per index record is less than cluster size, clusters per index record becomes sectors per index
942 if (NewIndexRoot->SizeOfEntry < DeviceExt->NtfsInfo.BytesPerCluster)
943 NewIndexRoot->ClustersPerIndexRecord = NewIndexRoot->SizeOfEntry / DeviceExt->NtfsInfo.BytesPerSector;
944 else
945 NewIndexRoot->ClustersPerIndexRecord = NewIndexRoot->SizeOfEntry / DeviceExt->NtfsInfo.BytesPerCluster;
946
947 // Setup the Index node header
948 NewIndexRoot->Header.FirstEntryOffset = sizeof(INDEX_HEADER_ATTRIBUTE);
949 NewIndexRoot->Header.Flags = INDEX_ROOT_SMALL;
950
951 // Start summing the total size of this node's entries
952 NewIndexRoot->Header.TotalSizeOfEntries = NewIndexRoot->Header.FirstEntryOffset;
953
954 // Setup each Node Entry
955 CurrentKey = Tree->RootNode->FirstKey;
956 CurrentNodeEntry = (PINDEX_ENTRY_ATTRIBUTE)((ULONG_PTR)NewIndexRoot
958 + NewIndexRoot->Header.FirstEntryOffset);
959 for (i = 0; i < Tree->RootNode->KeyCount; i++)
960 {
961 // Would adding the current entry to the index increase the index size beyond the limit we've set?
962 ULONG IndexSize = NewIndexRoot->Header.TotalSizeOfEntries - NewIndexRoot->Header.FirstEntryOffset + CurrentKey->IndexEntry->Length;
963 if (IndexSize > MaxIndexSize)
964 {
965 DPRINT1("TODO: Adding file would require creating an attribute list!\n");
966 ExFreePoolWithTag(NewIndexRoot, TAG_NTFS);
968 }
969
970 ASSERT(CurrentKey->IndexEntry->Length != 0);
971
972 // Copy the index entry
973 RtlCopyMemory(CurrentNodeEntry, CurrentKey->IndexEntry, CurrentKey->IndexEntry->Length);
974
975 DPRINT1("Index Node Entry Stream Length: %u\nIndex Node Entry Length: %u\n",
976 CurrentNodeEntry->KeyLength,
977 CurrentNodeEntry->Length);
978
979 // Does the current key have any sub-nodes?
980 if (CurrentKey->LesserChild)
981 NewIndexRoot->Header.Flags = INDEX_ROOT_LARGE;
982
983 // Add Length of Current Entry to Total Size of Entries
984 NewIndexRoot->Header.TotalSizeOfEntries += CurrentKey->IndexEntry->Length;
985
986 // Go to the next node entry
987 CurrentNodeEntry = (PINDEX_ENTRY_ATTRIBUTE)((ULONG_PTR)CurrentNodeEntry + CurrentNodeEntry->Length);
988
989 CurrentKey = CurrentKey->NextKey;
990 }
991
992 NewIndexRoot->Header.AllocatedSize = NewIndexRoot->Header.TotalSizeOfEntries;
993
994 *IndexRoot = NewIndexRoot;
996
997 return STATUS_SUCCESS;
998}
999
1004 BOOLEAN HasChildren,
1005 PINDEX_BUFFER IndexBuffer)
1006{
1007 ULONG i;
1008 PB_TREE_KEY CurrentKey;
1009 PINDEX_ENTRY_ATTRIBUTE CurrentNodeEntry;
1011
1012 // TODO: Fix magic, do math
1013 RtlZeroMemory(IndexBuffer, BufferSize);
1014 IndexBuffer->Ntfs.Type = NRH_INDX_TYPE;
1015 IndexBuffer->Ntfs.UsaOffset = 0x28;
1016 IndexBuffer->Ntfs.UsaCount = 9;
1017
1018 // TODO: Check bitmap for VCN
1019 ASSERT(Node->HasValidVCN);
1020 IndexBuffer->VCN = Node->VCN;
1021
1022 // Windows seems to alternate between using 0x28 and 0x40 for the first entry offset of each index buffer.
1023 // Interestingly, neither Windows nor chkdsk seem to mind if we just use 0x28 for every index record.
1024 IndexBuffer->Header.FirstEntryOffset = 0x28;
1026
1027 // Start summing the total size of this node's entries
1028 IndexBuffer->Header.TotalSizeOfEntries = IndexBuffer->Header.FirstEntryOffset;
1029
1030 CurrentKey = Node->FirstKey;
1031 CurrentNodeEntry = (PINDEX_ENTRY_ATTRIBUTE)((ULONG_PTR)&(IndexBuffer->Header)
1032 + IndexBuffer->Header.FirstEntryOffset);
1033 for (i = 0; i < Node->KeyCount; i++)
1034 {
1035 // Would adding the current entry to the index increase the node size beyond the allocation size?
1037 + IndexBuffer->Header.TotalSizeOfEntries
1038 + CurrentNodeEntry->Length;
1039 if (IndexSize > BufferSize)
1040 {
1041 DPRINT1("TODO: Adding file would require creating a new node!\n");
1043 }
1044
1045 ASSERT(CurrentKey->IndexEntry->Length != 0);
1046
1047 // Copy the index entry
1048 RtlCopyMemory(CurrentNodeEntry, CurrentKey->IndexEntry, CurrentKey->IndexEntry->Length);
1049
1050 DPRINT("Index Node Entry Stream Length: %u\nIndex Node Entry Length: %u\n",
1051 CurrentNodeEntry->KeyLength,
1052 CurrentNodeEntry->Length);
1053
1054 // Add Length of Current Entry to Total Size of Entries
1055 IndexBuffer->Header.TotalSizeOfEntries += CurrentNodeEntry->Length;
1056
1057 // Check for child nodes
1058 if (HasChildren)
1059 IndexBuffer->Header.Flags = INDEX_NODE_LARGE;
1060
1061 // Go to the next node entry
1062 CurrentNodeEntry = (PINDEX_ENTRY_ATTRIBUTE)((ULONG_PTR)CurrentNodeEntry + CurrentNodeEntry->Length);
1063 CurrentKey = CurrentKey->NextKey;
1064 }
1065
1066 Status = AddFixupArray(DeviceExt, &IndexBuffer->Ntfs);
1067
1068 return Status;
1069}
1070
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}
1153
1171VOID
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}
1180
1183 PB_TREE Tree,
1184 ULONG IndexBufferSize,
1185 PFILE_RECORD_HEADER FileRecord)
1186{
1187 // Find the index allocation and bitmap
1188 PNTFS_ATTR_CONTEXT IndexAllocationContext;
1189 PB_TREE_KEY CurrentKey;
1191 BOOLEAN HasIndexAllocation = FALSE;
1192 ULONG i;
1193 ULONG IndexAllocationOffset;
1194
1195 DPRINT("UpdateIndexAllocation() called.\n");
1196
1197 Status = FindAttribute(DeviceExt, FileRecord, AttributeIndexAllocation, L"$I30", 4, &IndexAllocationContext, &IndexAllocationOffset);
1198 if (NT_SUCCESS(Status))
1199 {
1200 HasIndexAllocation = TRUE;
1201
1202#ifndef NDEBUG
1203 PrintAllVCNs(DeviceExt,
1204 IndexAllocationContext,
1205 IndexBufferSize);
1206#endif
1207 }
1208 // Walk through the root node and update all the sub-nodes
1209 CurrentKey = Tree->RootNode->FirstKey;
1210 for (i = 0; i < Tree->RootNode->KeyCount; i++)
1211 {
1212 if (CurrentKey->LesserChild)
1213 {
1214 if (!HasIndexAllocation)
1215 {
1216 // We need to add an index allocation to the file record
1217 PNTFS_ATTR_RECORD EndMarker = (PNTFS_ATTR_RECORD)((ULONG_PTR)FileRecord + FileRecord->BytesInUse - (sizeof(ULONG) * 2));
1218 DPRINT1("Adding index allocation...\n");
1219
1220 // Add index allocation to the very end of the file record
1221 Status = AddIndexAllocation(DeviceExt,
1222 FileRecord,
1223 EndMarker,
1224 L"$I30",
1225 4);
1226 if (!NT_SUCCESS(Status))
1227 {
1228 DPRINT1("ERROR: Failed to add index allocation!\n");
1229 return Status;
1230 }
1231
1232 // Find the new attribute
1233 Status = FindAttribute(DeviceExt, FileRecord, AttributeIndexAllocation, L"$I30", 4, &IndexAllocationContext, &IndexAllocationOffset);
1234 if (!NT_SUCCESS(Status))
1235 {
1236 DPRINT1("ERROR: Couldn't find newly-created index allocation!\n");
1237 return Status;
1238 }
1239
1240 // Advance end marker
1241 EndMarker = (PNTFS_ATTR_RECORD)((ULONG_PTR)EndMarker + EndMarker->Length);
1242
1243 // Add index bitmap to the very end of the file record
1244 Status = AddBitmap(DeviceExt,
1245 FileRecord,
1246 EndMarker,
1247 L"$I30",
1248 4);
1249 if (!NT_SUCCESS(Status))
1250 {
1251 DPRINT1("ERROR: Failed to add index bitmap!\n");
1252 ReleaseAttributeContext(IndexAllocationContext);
1253 return Status;
1254 }
1255
1256 HasIndexAllocation = TRUE;
1257 }
1258
1259 // Is the Index Entry large enough to store the VCN?
1261 {
1262 // Allocate memory for the larger index entry
1264 CurrentKey->IndexEntry->Length + sizeof(ULONGLONG),
1265 TAG_NTFS);
1266 if (!NewEntry)
1267 {
1268 DPRINT1("ERROR: Unable to allocate memory for new index entry!\n");
1269 if (HasIndexAllocation)
1270 ReleaseAttributeContext(IndexAllocationContext);
1272 }
1273
1274 // Copy the old entry to the new one
1275 RtlCopyMemory(NewEntry, CurrentKey->IndexEntry, CurrentKey->IndexEntry->Length);
1276
1277 NewEntry->Length += sizeof(ULONGLONG);
1278
1279 // Free the old memory
1281
1282 CurrentKey->IndexEntry = NewEntry;
1283 CurrentKey->IndexEntry->Flags |= NTFS_INDEX_ENTRY_NODE;
1284 }
1285
1286 // Update the sub-node
1287 Status = UpdateIndexNode(DeviceExt, FileRecord, CurrentKey->LesserChild, IndexBufferSize, IndexAllocationContext, IndexAllocationOffset);
1288 if (!NT_SUCCESS(Status))
1289 {
1290 DPRINT1("ERROR: Failed to update index node!\n");
1291 ReleaseAttributeContext(IndexAllocationContext);
1292 return Status;
1293 }
1294
1295 // Update the VCN stored in the index entry of CurrentKey
1296 SetIndexEntryVCN(CurrentKey->IndexEntry, CurrentKey->LesserChild->VCN);
1297 }
1298 CurrentKey = CurrentKey->NextKey;
1299 }
1300
1301#ifndef NDEBUG
1302 DumpBTree(Tree);
1303#endif
1304
1305 if (HasIndexAllocation)
1306 {
1307#ifndef NDEBUG
1308 PrintAllVCNs(DeviceExt,
1309 IndexAllocationContext,
1310 IndexBufferSize);
1311#endif
1312 ReleaseAttributeContext(IndexAllocationContext);
1313 }
1314
1315 return STATUS_SUCCESS;
1316}
1317
1320 PFILE_RECORD_HEADER FileRecord,
1322 ULONG IndexBufferSize,
1323 PNTFS_ATTR_CONTEXT IndexAllocationContext,
1324 ULONG IndexAllocationOffset)
1325{
1326 ULONG i;
1327 PB_TREE_KEY CurrentKey = Node->FirstKey;
1328 BOOLEAN HasChildren = FALSE;
1330
1331
1332 DPRINT("UpdateIndexNode(%p, %p, %p, %lu, %p, %lu) called for index node with VCN %I64u\n",
1333 DeviceExt,
1334 FileRecord,
1335 Node,
1336 IndexBufferSize,
1337 IndexAllocationContext,
1338 IndexAllocationOffset,
1339 Node->VCN);
1340
1341 // Walk through the node and look for children to update
1342 for (i = 0; i < Node->KeyCount; i++)
1343 {
1344 ASSERT(CurrentKey);
1345
1346 // If there's a child node
1347 if (CurrentKey->LesserChild)
1348 {
1349 HasChildren = TRUE;
1350
1351 // Update the child node on disk
1352 Status = UpdateIndexNode(DeviceExt, FileRecord, CurrentKey->LesserChild, IndexBufferSize, IndexAllocationContext, IndexAllocationOffset);
1353 if (!NT_SUCCESS(Status))
1354 {
1355 DPRINT1("ERROR: Failed to update child node!\n");
1356 return Status;
1357 }
1358
1359 // Is the Index Entry large enough to store the VCN?
1361 {
1362 // Allocate memory for the larger index entry
1364 CurrentKey->IndexEntry->Length + sizeof(ULONGLONG),
1365 TAG_NTFS);
1366 if (!NewEntry)
1367 {
1368 DPRINT1("ERROR: Unable to allocate memory for new index entry!\n");
1370 }
1371
1372 // Copy the old entry to the new one
1373 RtlCopyMemory(NewEntry, CurrentKey->IndexEntry, CurrentKey->IndexEntry->Length);
1374
1375 NewEntry->Length += sizeof(ULONGLONG);
1376
1377 // Free the old memory
1379
1380 CurrentKey->IndexEntry = NewEntry;
1381 }
1382
1383 // Update the VCN stored in the index entry of CurrentKey
1384 SetIndexEntryVCN(CurrentKey->IndexEntry, CurrentKey->LesserChild->VCN);
1385
1386 CurrentKey->IndexEntry->Flags |= NTFS_INDEX_ENTRY_NODE;
1387 }
1388
1389 CurrentKey = CurrentKey->NextKey;
1390 }
1391
1392
1393 // Do we need to write this node to disk?
1394 if (Node->DiskNeedsUpdating)
1395 {
1396 ULONGLONG NodeOffset;
1397 ULONG LengthWritten;
1398 PINDEX_BUFFER IndexBuffer;
1399
1400 // Does the node need to be assigned a VCN?
1401 if (!Node->HasValidVCN)
1402 {
1403 // Allocate the node
1404 Status = AllocateIndexNode(DeviceExt,
1405 FileRecord,
1406 IndexBufferSize,
1407 IndexAllocationContext,
1408 IndexAllocationOffset,
1409 &Node->VCN);
1410 if (!NT_SUCCESS(Status))
1411 {
1412 DPRINT1("ERROR: Failed to allocate index record in index allocation!\n");
1413 return Status;
1414 }
1415
1416 Node->HasValidVCN = TRUE;
1417 }
1418
1419 // Allocate memory for an index buffer
1420 IndexBuffer = ExAllocatePoolWithTag(NonPagedPool, IndexBufferSize, TAG_NTFS);
1421 if (!IndexBuffer)
1422 {
1423 DPRINT1("ERROR: Failed to allocate %lu bytes for index buffer!\n", IndexBufferSize);
1425 }
1426
1427 // Create the index buffer we'll be writing to disk to represent this node
1428 Status = CreateIndexBufferFromBTreeNode(DeviceExt, Node, IndexBufferSize, HasChildren, IndexBuffer);
1429 if (!NT_SUCCESS(Status))
1430 {
1431 DPRINT1("ERROR: Failed to create index buffer from node!\n");
1432 ExFreePoolWithTag(IndexBuffer, TAG_NTFS);
1433 return Status;
1434 }
1435
1436 // Get Offset of index buffer in index allocation
1437 NodeOffset = GetAllocationOffsetFromVCN(DeviceExt, IndexBufferSize, Node->VCN);
1438
1439 // Write the buffer to the index allocation
1440 Status = WriteAttribute(DeviceExt, IndexAllocationContext, NodeOffset, (const PUCHAR)IndexBuffer, IndexBufferSize, &LengthWritten, FileRecord);
1441 if (!NT_SUCCESS(Status) || LengthWritten != IndexBufferSize)
1442 {
1443 DPRINT1("ERROR: Failed to update index allocation!\n");
1444 ExFreePoolWithTag(IndexBuffer, TAG_NTFS);
1445 if (!NT_SUCCESS(Status))
1446 return Status;
1447 else
1448 return STATUS_END_OF_FILE;
1449 }
1450
1451 Node->DiskNeedsUpdating = FALSE;
1452
1453 // Free the index buffer
1454 ExFreePoolWithTag(IndexBuffer, TAG_NTFS);
1455 }
1456
1457 return STATUS_SUCCESS;
1458}
1459
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}
1497
1498VOID
1500{
1501 if (Key->IndexEntry)
1502 ExFreePoolWithTag(Key->IndexEntry, TAG_NTFS);
1503
1504 if (Key->LesserChild)
1505 DestroyBTreeNode(Key->LesserChild);
1506
1508}
1509
1510VOID
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}
1528
1541VOID
1543{
1544 DestroyBTreeNode(Tree->RootNode);
1546}
1547
1548VOID
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}
1581
1582VOID
1585 ULONG Number,
1586 ULONG Depth)
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}
1608
1621VOID
1623{
1624 DbgPrint("B_TREE @ %p\n", Tree);
1625 DumpBTreeNode(Tree, Tree->RootNode, 0, 0);
1626}
1627
1628// Calculates start of Index Buffer relative to the index allocation, given the node's VCN
1631 ULONG IndexBufferSize,
1632 ULONGLONG Vcn)
1633{
1634 if (IndexBufferSize < DeviceExt->NtfsInfo.BytesPerCluster)
1635 return Vcn * DeviceExt->NtfsInfo.BytesPerSector;
1636
1637 return Vcn * DeviceExt->NtfsInfo.BytesPerCluster;
1638}
1639
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}
1649
1692 ULONGLONG FileReference,
1693 PFILENAME_ATTRIBUTE FileNameAttribute,
1695 BOOLEAN CaseSensitive,
1696 ULONG MaxIndexRootSize,
1697 ULONG IndexRecordSize,
1698 PB_TREE_KEY *MedianKey,
1699 PB_TREE_FILENAME_NODE *NewRightHandSibling)
1700{
1701 PB_TREE_KEY NewKey, CurrentKey, PreviousKey;
1703 ULONG NodeSize;
1704 ULONG AllocatedNodeSize;
1705 ULONG MaxNodeSizeWithoutHeader;
1706 ULONG i;
1707
1708 *MedianKey = NULL;
1709 *NewRightHandSibling = NULL;
1710
1711 DPRINT("NtfsInsertKey(%p, 0x%I64x, %p, %p, %s, %lu, %lu, %p, %p)\n",
1712 Tree,
1713 FileReference,
1714 FileNameAttribute,
1715 Node,
1716 CaseSensitive ? "TRUE" : "FALSE",
1717 MaxIndexRootSize,
1718 IndexRecordSize,
1719 MedianKey,
1720 NewRightHandSibling);
1721
1722 // Create the key for the filename attribute
1723 NewKey = CreateBTreeKeyFromFilename(FileReference, FileNameAttribute);
1724 if (!NewKey)
1726
1727 // Find where to insert the key
1728 CurrentKey = Node->FirstKey;
1729 PreviousKey = NULL;
1730 for (i = 0; i < Node->KeyCount; i++)
1731 {
1732 // Should the New Key go before the current key?
1733 LONG Comparison = CompareTreeKeys(NewKey, CurrentKey, CaseSensitive);
1734
1735 if (Comparison == 0)
1736 {
1737 DPRINT1("\t\tComparison == 0: %.*S\n", NewKey->IndexEntry->FileName.NameLength, NewKey->IndexEntry->FileName.Name);
1738 DPRINT1("\t\tComparison == 0: %.*S\n", CurrentKey->IndexEntry->FileName.NameLength, CurrentKey->IndexEntry->FileName.Name);
1739 }
1740 ASSERT(Comparison != 0);
1741
1742 // Is NewKey < CurrentKey?
1743 if (Comparison < 0)
1744 {
1745 // Does CurrentKey have a sub-node?
1746 if (CurrentKey->LesserChild)
1747 {
1748 PB_TREE_KEY NewLeftKey;
1749 PB_TREE_FILENAME_NODE NewChild;
1750
1751 // Insert the key into the child node
1753 FileReference,
1754 FileNameAttribute,
1755 CurrentKey->LesserChild,
1756 CaseSensitive,
1757 MaxIndexRootSize,
1758 IndexRecordSize,
1759 &NewLeftKey,
1760 &NewChild);
1761 if (!NT_SUCCESS(Status))
1762 {
1763 DPRINT1("ERROR: Failed to insert key.\n");
1764 ExFreePoolWithTag(NewKey, TAG_NTFS);
1765 return Status;
1766 }
1767
1768 // Did the child node get split?
1769 if (NewLeftKey)
1770 {
1771 ASSERT(NewChild != NULL);
1772
1773 // Insert the new left key to the left of the current key
1774 NewLeftKey->NextKey = CurrentKey;
1775
1776 // Is CurrentKey the first key?
1777 if (!PreviousKey)
1778 Node->FirstKey = NewLeftKey;
1779 else
1780 PreviousKey->NextKey = NewLeftKey;
1781
1782 // CurrentKey->LesserChild will be the right-hand sibling
1783 CurrentKey->LesserChild = NewChild;
1784
1785 Node->KeyCount++;
1786 Node->DiskNeedsUpdating = TRUE;
1787
1788#ifndef NDEBUG
1789 DumpBTree(Tree);
1790#endif
1791 }
1792 }
1793 else
1794 {
1795 // Insert New Key before Current Key
1796 NewKey->NextKey = CurrentKey;
1797
1798 // Increase KeyCount and mark node as dirty
1799 Node->KeyCount++;
1800 Node->DiskNeedsUpdating = TRUE;
1801
1802 // was CurrentKey the first key?
1803 if (CurrentKey == Node->FirstKey)
1804 Node->FirstKey = NewKey;
1805 else
1806 PreviousKey->NextKey = NewKey;
1807 }
1808 break;
1809 }
1810
1811 PreviousKey = CurrentKey;
1812 CurrentKey = CurrentKey->NextKey;
1813 }
1814
1815 // Determine how much space the index entries will need
1816 NodeSize = GetSizeOfIndexEntries(Node);
1817
1818 // Is Node not the root node?
1819 if (Node != Tree->RootNode)
1820 {
1821 // Calculate maximum size of index entries without any headers
1822 AllocatedNodeSize = IndexRecordSize - FIELD_OFFSET(INDEX_BUFFER, Header);
1823
1824 // TODO: Replace magic with math
1825 MaxNodeSizeWithoutHeader = AllocatedNodeSize - 0x28;
1826
1827 // Has the node grown larger than its allocated size?
1828 if (NodeSize > MaxNodeSizeWithoutHeader)
1829 {
1831
1832 Status = SplitBTreeNode(Tree, Node, MedianKey, NewRightHandSibling, CaseSensitive);
1833 if (!NT_SUCCESS(Status))
1834 {
1835 DPRINT1("ERROR: Failed to split B-Tree node!\n");
1836 return Status;
1837 }
1838
1839 return Status;
1840 }
1841 }
1842
1843 // NewEntry and NewKey will be destroyed later by DestroyBTree()
1844
1845 return Status;
1846}
1847
1848
1849
1885 PB_TREE_KEY *MedianKey,
1886 PB_TREE_FILENAME_NODE *NewRightHandSibling,
1887 BOOLEAN CaseSensitive)
1888{
1889 ULONG MedianKeyIndex;
1890 PB_TREE_KEY LastKeyBeforeMedian, FirstKeyAfterMedian;
1891 ULONG KeyCount;
1892 ULONG HalfSize;
1893 ULONG SizeSum;
1894 ULONG i;
1895
1896 DPRINT("SplitBTreeNode(%p, %p, %p, %p, %s) called\n",
1897 Tree,
1898 Node,
1899 MedianKey,
1900 NewRightHandSibling,
1901 CaseSensitive ? "TRUE" : "FALSE");
1902
1903#ifndef NDEBUG
1904 DumpBTreeNode(Tree, Node, 0, 0);
1905#endif
1906
1907 // Create the right hand sibling
1908 *NewRightHandSibling = ExAllocatePoolWithTag(NonPagedPool, sizeof(B_TREE_FILENAME_NODE), TAG_NTFS);
1909 if (*NewRightHandSibling == NULL)
1910 {
1911 DPRINT1("Error: Failed to allocate memory for right hand sibling!\n");
1913 }
1914 RtlZeroMemory(*NewRightHandSibling, sizeof(B_TREE_FILENAME_NODE));
1915 (*NewRightHandSibling)->DiskNeedsUpdating = TRUE;
1916
1917
1918 // Find the last key before the median
1919
1920 // This is roughly how NTFS-3G calculates median, and it's not congruent with what Windows does:
1921 /*
1922 // find the median key index
1923 MedianKeyIndex = (Node->KeyCount + 1) / 2;
1924 MedianKeyIndex--;
1925
1926 LastKeyBeforeMedian = Node->FirstKey;
1927 for (i = 0; i < MedianKeyIndex - 1; i++)
1928 LastKeyBeforeMedian = LastKeyBeforeMedian->NextKey;*/
1929
1930 // The method we'll use is a little bit closer to how Windows determines the median but it's not identical.
1931 // What Windows does is actually more complicated than this, I think because Windows allocates more slack space to Odd-numbered
1932 // Index Records, leaving less room for index entries in these records (I haven't discovered why this is done).
1933 // (Neither Windows nor chkdsk complain if we choose a different median than Windows would have chosen, as our median will be in the ballpark)
1934
1935 // Use size to locate the median key / index
1936 LastKeyBeforeMedian = Node->FirstKey;
1937 MedianKeyIndex = 0;
1938 HalfSize = 2016; // half the allocated size after subtracting the first index entry offset (TODO: MATH)
1939 SizeSum = 0;
1940 for (i = 0; i < Node->KeyCount; i++)
1941 {
1942 SizeSum += LastKeyBeforeMedian->IndexEntry->Length;
1943
1944 if (SizeSum > HalfSize)
1945 break;
1946
1947 MedianKeyIndex++;
1948 LastKeyBeforeMedian = LastKeyBeforeMedian->NextKey;
1949 }
1950
1951 // Now we can get the median key and the key that follows it
1952 *MedianKey = LastKeyBeforeMedian->NextKey;
1953 FirstKeyAfterMedian = (*MedianKey)->NextKey;
1954
1955 DPRINT1("%lu keys, %lu median\n", Node->KeyCount, MedianKeyIndex);
1956 DPRINT1("\t\tMedian: %.*S\n", (*MedianKey)->IndexEntry->FileName.NameLength, (*MedianKey)->IndexEntry->FileName.Name);
1957
1958 // "Node" will be the left hand sibling after the split, containing all keys prior to the median key
1959
1960 // We need to create a dummy pointer at the end of the LHS. The dummy's child will be the median's child.
1961 LastKeyBeforeMedian->NextKey = CreateDummyKey(BooleanFlagOn((*MedianKey)->IndexEntry->Flags, NTFS_INDEX_ENTRY_NODE));
1962 if (LastKeyBeforeMedian->NextKey == NULL)
1963 {
1964 DPRINT1("Error: Couldn't allocate dummy key!\n");
1965 LastKeyBeforeMedian->NextKey = *MedianKey;
1966 ExFreePoolWithTag(*NewRightHandSibling, TAG_NTFS);
1968 }
1969
1970 // Did the median key have a child node?
1971 if ((*MedianKey)->IndexEntry->Flags & NTFS_INDEX_ENTRY_NODE)
1972 {
1973 // Set the child of the new dummy key
1974 LastKeyBeforeMedian->NextKey->LesserChild = (*MedianKey)->LesserChild;
1975
1976 // Give the dummy key's index entry the same sub-node VCN the median
1977 SetIndexEntryVCN(LastKeyBeforeMedian->NextKey->IndexEntry, GetIndexEntryVCN((*MedianKey)->IndexEntry));
1978 }
1979 else
1980 {
1981 // Median key didn't have a child node, but it will. Create a new index entry large enough to store a VCN.
1983 (*MedianKey)->IndexEntry->Length + sizeof(ULONGLONG),
1984 TAG_NTFS);
1985 if (!NewIndexEntry)
1986 {
1987 DPRINT1("Unable to allocate memory for new index entry!\n");
1988 LastKeyBeforeMedian->NextKey = *MedianKey;
1989 ExFreePoolWithTag(*NewRightHandSibling, TAG_NTFS);
1991 }
1992
1993 // Copy the old index entry to the new one
1994 RtlCopyMemory(NewIndexEntry, (*MedianKey)->IndexEntry, (*MedianKey)->IndexEntry->Length);
1995
1996 // Use the new index entry after freeing the old one
1997 ExFreePoolWithTag((*MedianKey)->IndexEntry, TAG_NTFS);
1998 (*MedianKey)->IndexEntry = NewIndexEntry;
1999
2000 // Update the length for the VCN
2001 (*MedianKey)->IndexEntry->Length += sizeof(ULONGLONG);
2002
2003 // Set the node flag
2004 (*MedianKey)->IndexEntry->Flags |= NTFS_INDEX_ENTRY_NODE;
2005 }
2006
2007 // "Node" will become the child of the median key
2008 (*MedianKey)->LesserChild = Node;
2009 SetIndexEntryVCN((*MedianKey)->IndexEntry, Node->VCN);
2010
2011 // Update Node's KeyCount (remember to add 1 for the new dummy key)
2012 Node->KeyCount = MedianKeyIndex + 2;
2013
2014 KeyCount = CountBTreeKeys(Node->FirstKey);
2015 ASSERT(Node->KeyCount == KeyCount);
2016
2017 // everything to the right of MedianKey becomes the right hand sibling of Node
2018 (*NewRightHandSibling)->FirstKey = FirstKeyAfterMedian;
2019 (*NewRightHandSibling)->KeyCount = CountBTreeKeys(FirstKeyAfterMedian);
2020
2021#ifndef NDEBUG
2022 DPRINT1("Left-hand node after split:\n");
2023 DumpBTreeNode(Tree, Node, 0, 0);
2024
2025 DPRINT1("Right-hand sibling node after split:\n");
2026 DumpBTreeNode(Tree, *NewRightHandSibling, 0, 0);
2027#endif
2028
2029 return STATUS_SUCCESS;
2030}
CRegistryTree Tree
#define ALIGN_UP_BY(size, align)
unsigned char BOOLEAN
LONG NTSTATUS
Definition: precomp.h:26
#define DPRINT1
Definition: precomp.h:8
struct NTFS_ATTR_RECORD * PNTFS_ATTR_RECORD
#define NTFS_INDEX_ENTRY_NODE
Definition: ntfs.h:60
#define NTFS_INDEX_ENTRY_END
Definition: ntfs.h:61
VOID DumpBTreeNode(PB_TREE Tree, PB_TREE_FILENAME_NODE Node, ULONG Number, ULONG Depth)
Definition: btree.c:1583
PB_TREE_FILENAME_NODE CreateBTreeNodeFromIndexNode(PDEVICE_EXTENSION Vcb, PINDEX_ROOT_ATTRIBUTE IndexRoot, PNTFS_ATTR_CONTEXT IndexAllocationAttributeCtx, PINDEX_ENTRY_ATTRIBUTE NodeEntry)
Definition: btree.c:499
ULONG CountBTreeKeys(PB_TREE_KEY FirstKey)
Definition: btree.c:484
VOID DestroyBTreeNode(PB_TREE_FILENAME_NODE Node)
Definition: btree.c:1511
NTSTATUS CreateBTreeFromIndex(PDEVICE_EXTENSION Vcb, PFILE_RECORD_HEADER FileRecordWithIndex, PNTFS_ATTR_CONTEXT IndexRootContext, PINDEX_ROOT_ATTRIBUTE IndexRoot, PB_TREE *NewTree)
Definition: btree.c:682
LONG CompareTreeKeys(PB_TREE_KEY Key1, PB_TREE_KEY Key2, BOOLEAN CaseSensitive)
Definition: btree.c:417
NTSTATUS SplitBTreeNode(PB_TREE Tree, PB_TREE_FILENAME_NODE Node, PB_TREE_KEY *MedianKey, PB_TREE_FILENAME_NODE *NewRightHandSibling, BOOLEAN CaseSensitive)
Definition: btree.c:1883
VOID DestroyBTreeKey(PB_TREE_KEY Key)
Definition: btree.c:1499
NTSTATUS AllocateIndexNode(PDEVICE_EXTENSION DeviceExt, PFILE_RECORD_HEADER FileRecord, ULONG IndexBufferSize, PNTFS_ATTR_CONTEXT IndexAllocationCtx, ULONG IndexAllocationOffset, PULONGLONG NewVCN)
Definition: btree.c:117
ULONGLONG GetIndexEntryVCN(PINDEX_ENTRY_ATTRIBUTE IndexEntry)
Definition: btree.c:1641
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
ULONGLONG GetAllocationOffsetFromVCN(PDEVICE_EXTENSION DeviceExt, ULONG IndexBufferSize, ULONGLONG Vcn)
Definition: btree.c:1630
NTSTATUS UpdateIndexAllocation(PDEVICE_EXTENSION DeviceExt, PB_TREE Tree, ULONG IndexBufferSize, PFILE_RECORD_HEADER FileRecord)
Definition: btree.c:1182
VOID DestroyBTree(PB_TREE Tree)
Definition: btree.c:1542
VOID PrintAllVCNs(PDEVICE_EXTENSION Vcb, PNTFS_ATTR_CONTEXT IndexAllocationContext, ULONG NodeSize)
Definition: btree.c:38
NTSTATUS CreateIndexBufferFromBTreeNode(PDEVICE_EXTENSION DeviceExt, PB_TREE_FILENAME_NODE Node, ULONG BufferSize, BOOLEAN HasChildren, PINDEX_BUFFER IndexBuffer)
Definition: btree.c:1001
NTSTATUS DemoteBTreeRoot(PB_TREE Tree)
Definition: btree.c:1089
ULONG GetSizeOfIndexEntries(PB_TREE_FILENAME_NODE Node)
Definition: btree.c:855
PB_TREE_KEY CreateDummyKey(BOOLEAN HasChildNode)
Definition: btree.c:289
VOID DumpBTree(PB_TREE Tree)
Definition: btree.c:1622
NTSTATUS CreateEmptyBTree(PB_TREE *NewTree)
Definition: btree.c:348
NTSTATUS CreateIndexRootFromBTree(PDEVICE_EXTENSION DeviceExt, PB_TREE Tree, ULONG MaxIndexSize, PINDEX_ROOT_ATTRIBUTE *IndexRoot, ULONG *Length)
Definition: btree.c:910
VOID SetIndexEntryVCN(PINDEX_ENTRY_ATTRIBUTE IndexEntry, ULONGLONG VCN)
Definition: btree.c:1172
PB_TREE_KEY CreateBTreeKeyFromFilename(ULONGLONG FileReference, PFILENAME_ATTRIBUTE FileNameAttribute)
Definition: btree.c:1461
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
VOID DumpBTreeKey(PB_TREE Tree, PB_TREE_KEY Key, ULONG Number, ULONG Depth)
Definition: btree.c:1549
Definition: bufpool.h:45
Definition: Header.h:9
#define BufferSize
Definition: mmc.h:75
#define NULL
Definition: types.h:112
#define TRUE
Definition: types.h:120
#define FALSE
Definition: types.h:117
#define NT_SUCCESS(StatCode)
Definition: apphelp.c:32
union node Node
Definition: types.h:1255
static const WCHAR Cleanup[]
Definition: register.c:80
ULONG GetFileNameAttributeLength(PFILENAME_ATTRIBUTE FileNameAttribute)
Definition: attrib.c:1978
NTSTATUS AddBitmap(PNTFS_VCB Vcb, PFILE_RECORD_HEADER FileRecord, PNTFS_ATTR_RECORD AttributeAddress, PCWSTR Name, USHORT NameLength)
Definition: attrib.c:72
NTSTATUS AddIndexAllocation(PNTFS_VCB Vcb, PFILE_RECORD_HEADER FileRecord, PNTFS_ATTR_RECORD AttributeAddress, PCWSTR Name, USHORT NameLength)
Definition: attrib.c:388
struct INDEX_BUFFER * PINDEX_BUFFER
#define INDEX_ROOT_SMALL
Definition: ntfs.h:208
struct INDEX_ENTRY_ATTRIBUTE * PINDEX_ENTRY_ATTRIBUTE
#define COLLATION_FILE_NAME
Definition: ntfs.h:201
#define INDEX_NODE_LARGE
Definition: ntfs.h:212
#define INDEX_ROOT_LARGE
Definition: ntfs.h:209
#define NRH_INDX_TYPE
Definition: ntfs.h:247
@ AttributeFileName
Definition: ntfs.h:163
@ AttributeIndexAllocation
Definition: ntfs.h:170
@ AttributeBitmap
Definition: ntfs.h:171
#define TAG_NTFS
Definition: ntfs.h:12
#define ATTR_RECORD_ALIGNMENT
Definition: ntfs.h:320
#define ExAllocatePoolWithTag(hernya, size, tag)
Definition: env_spec_w32.h:350
ULONG RtlCompareUnicodeString(PUNICODE_STRING s1, PUNICODE_STRING s2, BOOLEAN UpCase)
Definition: string_lib.cpp:31
#define NonPagedPool
Definition: env_spec_w32.h:307
#define BooleanFlagOn(F, SF)
Definition: ext2fs.h:183
struct _FileName FileName
Definition: fatprocs.h:896
Status
Definition: gdiplustypes.h:25
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
#define DbgPrint
Definition: hal.h:12
NTSYSAPI void WINAPI RtlInitializeBitMap(PRTL_BITMAP, PULONG, ULONG)
NTSYSAPI void WINAPI RtlSetBits(PRTL_BITMAP, ULONG, ULONG)
PCONFIGURATION_COMPONENT_DATA RootNode
Definition: macharm.c:19
NTSTATUS UpdateFileRecord(PDEVICE_EXTENSION Vcb, ULONGLONG MftIndex, PFILE_RECORD_HEADER FileRecord)
Definition: mft.c:1931
VOID ReleaseAttributeContext(PNTFS_ATTR_CONTEXT Context)
Definition: mft.c:104
ULONGLONG AttributeDataLength(PNTFS_ATTR_RECORD AttrRecord)
Definition: mft.c:259
NTSTATUS FindAttribute(PDEVICE_EXTENSION Vcb, PFILE_RECORD_HEADER MftRecord, ULONG Type, PCWSTR Name, ULONG NameLength, PNTFS_ATTR_CONTEXT *AttrCtx, PULONG Offset)
Definition: mft.c:131
ULONG ReadAttribute(PDEVICE_EXTENSION Vcb, PNTFS_ATTR_CONTEXT Context, ULONGLONG Offset, PCHAR Buffer, ULONG Length)
Definition: mft.c:1065
NTSTATUS WriteAttribute(PDEVICE_EXTENSION Vcb, PNTFS_ATTR_CONTEXT Context, ULONGLONG Offset, const PUCHAR Buffer, ULONG Length, PULONG RealLengthWritten, PFILE_RECORD_HEADER FileRecord)
Definition: mft.c:1315
NTSTATUS AddFixupArray(PDEVICE_EXTENSION Vcb, PNTFS_RECORD_HEADER Record)
Definition: mft.c:2603
NTSTATUS SetNonResidentAttributeDataLength(PDEVICE_EXTENSION Vcb, PNTFS_ATTR_CONTEXT AttrContext, ULONG AttrOffset, PFILE_RECORD_HEADER FileRecord, PLARGE_INTEGER DataSize)
Definition: mft.c:756
NTSTATUS SetResidentAttributeDataLength(PDEVICE_EXTENSION Vcb, PNTFS_ATTR_CONTEXT AttrContext, ULONG AttrOffset, PFILE_RECORD_HEADER FileRecord, PLARGE_INTEGER DataSize)
Definition: mft.c:891
NTSTATUS FixupUpdateSequenceArray(PDEVICE_EXTENSION Vcb, PNTFS_RECORD_HEADER Record)
Definition: mft.c:1965
#define ASSERT(a)
Definition: mode.c:44
#define ExFreePoolWithTag(_P, _T)
Definition: module.h:1109
_In_ NDIS_STATUS _In_ ULONG _In_ USHORT _In_opt_ PVOID _In_ ULONG DataSize
Definition: ndis.h:4755
_In_ PUNICODE_STRING _Inout_ PUNICODE_STRING Destination
Definition: rtlfuncs.h:3004
int Count
Definition: noreturn.cpp:7
__GNU_EXTENSION typedef unsigned __int64 * PULONGLONG
Definition: ntbasedef.h:383
_In_ ULONG _In_ ULONG _In_ ULONG Length
Definition: ntddpcm.h:102
_In_opt_ PENTER_STATE_SYSTEM_HANDLER _In_opt_ PVOID _In_ LONG _In_opt_ LONG volatile * Number
Definition: ntpoapi.h:207
#define STATUS_NOT_IMPLEMENTED
Definition: ntstatus.h:239
#define L(x)
Definition: ntvdm.h:50
long LONG
Definition: pedump.c:60
#define Vcb
Definition: cdprocs.h:1415
#define STATUS_END_OF_FILE
Definition: shellext.h:67
#define STATUS_SUCCESS
Definition: shellext.h:65
#define DPRINT
Definition: sndvol32.h:71
Definition: ntfs.h:454
UCHAR NameLength
Definition: ntfs.h:377
WCHAR Name[1]
Definition: ntfs.h:379
INDEX_HEADER_ATTRIBUTE Header
Definition: ntfs.h:405
ULONGLONG VCN
Definition: ntfs.h:404
NTFS_RECORD_HEADER Ntfs
Definition: ntfs.h:403
Definition: ntfs.h:409
union INDEX_ENTRY_ATTRIBUTE::@762 Data
FILENAME_ATTRIBUTE FileName
Definition: ntfs.h:427
USHORT Length
Definition: ntfs.h:423
USHORT KeyLength
Definition: ntfs.h:424
struct INDEX_ENTRY_ATTRIBUTE::@762::@763 Directory
USHORT Flags
Definition: ntfs.h:425
ULONG FirstEntryOffset
Definition: ntfs.h:384
ULONG TotalSizeOfEntries
Definition: ntfs.h:385
ULONG AttributeType
Definition: ntfs.h:393
ULONG CollationRule
Definition: ntfs.h:394
INDEX_HEADER_ATTRIBUTE Header
Definition: ntfs.h:398
UCHAR ClustersPerIndexRecord
Definition: ntfs.h:396
ULONG SizeOfEntry
Definition: ntfs.h:395
ULONG Length
Definition: ntfs.h:127
USHORT UsaCount
Definition: ntfs.h:241
USHORT UsaOffset
Definition: ntfs.h:240
ULONGLONG VCN
Definition: ntfs.h:449
BOOLEAN HasValidVCN
Definition: ntfs.h:447
BOOLEAN DiskNeedsUpdating
Definition: ntfs.h:448
PB_TREE_KEY FirstKey
Definition: ntfs.h:450
struct _B_TREE_KEY * NextKey
Definition: ntfs.h:436
B_TREE_FILENAME_NODE * LesserChild
Definition: ntfs.h:437
PINDEX_ENTRY_ATTRIBUTE IndexEntry
Definition: ntfs.h:438
ULONG BytesInUse
Definition: ntfs.h:257
USHORT MaximumLength
Definition: env_spec_w32.h:370
uint32_t * PULONG
Definition: typedefs.h:59
#define FIELD_OFFSET(t, f)
Definition: typedefs.h:255
#define RtlCopyMemory(Destination, Source, Length)
Definition: typedefs.h:263
#define RtlZeroMemory(Destination, Length)
Definition: typedefs.h:262
uint32_t ULONG_PTR
Definition: typedefs.h:65
unsigned char * PUCHAR
Definition: typedefs.h:53
uint32_t ULONG
Definition: typedefs.h:59
uint64_t ULONGLONG
Definition: typedefs.h:67
char * PCHAR
Definition: typedefs.h:51
#define STATUS_FILE_CORRUPT_ERROR
Definition: udferr_usr.h:168
#define STATUS_INSUFFICIENT_RESOURCES
Definition: udferr_usr.h:158
#define ALIGN_UP(size, type)
Definition: umtypes.h:91
Definition: dlist.c:348
_Must_inspect_result_ _In_ WDFIOTARGET _In_opt_ WDFREQUEST _In_opt_ PWDF_MEMORY_DESCRIPTOR _In_opt_ PLONGLONG _In_opt_ PWDF_REQUEST_SEND_OPTIONS _Out_opt_ PULONG_PTR BytesWritten
Definition: wdfiotarget.h:960
_Must_inspect_result_ _In_ WDFIOTARGET _In_opt_ WDFREQUEST _In_opt_ PWDF_MEMORY_DESCRIPTOR _In_opt_ PLONGLONG _In_opt_ PWDF_REQUEST_SEND_OPTIONS _Out_opt_ PULONG_PTR BytesRead
Definition: wdfiotarget.h:870
_In_ WDFMEMORY _Out_opt_ size_t * BufferSize
Definition: wdfmemory.h:254
_In_opt_ PALLOCATE_FUNCTION _In_opt_ PFREE_FUNCTION _In_ ULONG _In_ SIZE_T _In_ ULONG _In_ USHORT Depth
Definition: exfuncs.h:819
_In_ UCHAR EntrySize
Definition: iofuncs.h:642
#define NT_ASSERT
Definition: rtlfuncs.h:3310
__wchar_t WCHAR
Definition: xmlstorage.h:180