ReactOS  0.4.14-dev-98-gb0d4763
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
37 VOID
39  PNTFS_ATTR_CONTEXT IndexAllocationContext,
40  ULONG NodeSize)
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 }
82 
116 NTSTATUS
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");
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 }
275 
289 CreateDummyKey(BOOLEAN HasChildNode)
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 
347 NTSTATUS
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 
416 LONG
417 CompareTreeKeys(PB_TREE_KEY Key1, PB_TREE_KEY Key2, BOOLEAN CaseSensitive)
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 
483 ULONG
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
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 }
661 
681 NTSTATUS
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 
832 Cleanup:
833  if (IndexAllocationContext)
834  ReleaseAttributeContext(IndexAllocationContext);
835 
836  return Status;
837 }
838 
854 ULONG
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 
909 NTSTATUS
911  PB_TREE Tree,
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
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 }
999 
1000 NTSTATUS
1003  ULONG BufferSize,
1004  BOOLEAN HasChildren,
1005  PINDEX_BUFFER IndexBuffer)
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 }
1070 
1088 NTSTATUS
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 
1171 VOID
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 
1181 NTSTATUS
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;
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 }
1317 
1318 NTSTATUS
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;
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 }
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 
1498 VOID
1500 {
1501  if (Key->IndexEntry)
1502  ExFreePoolWithTag(Key->IndexEntry, TAG_NTFS);
1503 
1504  if (Key->LesserChild)
1505  DestroyBTreeNode(Key->LesserChild);
1506 
1508 }
1509 
1510 VOID
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 
1541 VOID
1543 {
1544  DestroyBTreeNode(Tree->RootNode);
1546 }
1547 
1548 VOID
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 
1582 VOID
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 
1621 VOID
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
1629 ULONGLONG
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 
1640 ULONGLONG
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 
1690 NTSTATUS
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  {
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 }
1847 
1848 
1849 
1882 NTSTATUS
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(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 }
signed char * PCHAR
Definition: retypes.h:7
ULONG CountBTreeKeys(PB_TREE_KEY FirstKey)
Definition: btree.c:484
_In_opt_ PALLOCATE_FUNCTION _In_opt_ PFREE_FUNCTION _In_ ULONG _In_ SIZE_T _In_ ULONG _In_ USHORT Depth
Definition: exfuncs.h:656
ULONG CollationRule
Definition: ntfs.h:390
NTSTATUS AddFixupArray(PDEVICE_EXTENSION Vcb, PNTFS_RECORD_HEADER Record)
Definition: mft.c:2603
_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
#define TRUE
Definition: types.h:120
NTSYSAPI VOID NTAPI RtlCopyMemory(VOID UNALIGNED *Destination, CONST VOID UNALIGNED *Source, ULONG Length)
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
NTSTATUS AllocateIndexNode(PDEVICE_EXTENSION DeviceExt, PFILE_RECORD_HEADER FileRecord, ULONG IndexBufferSize, PNTFS_ATTR_CONTEXT IndexAllocationCtx, ULONG IndexAllocationOffset, PULONGLONG NewVCN)
Definition: btree.c:117
FILENAME_ATTRIBUTE FileName
Definition: ntfs.h:423
#define STATUS_NOT_IMPLEMENTED
Definition: ntstatus.h:225
#define DbgPrint
Definition: loader.c:25
USHORT MaximumLength
Definition: env_spec_w32.h:370
WCHAR Name[1]
Definition: ntfs.h:375
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
unsigned char * PUCHAR
Definition: retypes.h:3
LONG NTSTATUS
Definition: precomp.h:26
PB_TREE_KEY FirstKey
Definition: ntfs.h:446
USHORT Length
Definition: ntfs.h:419
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
_Inout_ __drv_aliasesMem PSLIST_ENTRY _Inout_ PSLIST_ENTRY _In_ ULONG Count
Definition: exfuncs.h:1015
struct INDEX_ENTRY_ATTRIBUTE::@750::@751 Directory
ULONG BytesInUse
Definition: ntfs.h:253
VOID DumpBTreeKey(PB_TREE Tree, PB_TREE_KEY Key, ULONG Number, ULONG Depth)
Definition: btree.c:1549
ULONGLONG VCN
Definition: ntfs.h:445
UCHAR NameLength
Definition: ntfs.h:373
NTSTATUS DemoteBTreeRoot(PB_TREE Tree)
Definition: btree.c:1089
Definition: ntfs.h:404
LONG CompareTreeKeys(PB_TREE_KEY Key1, PB_TREE_KEY Key2, BOOLEAN CaseSensitive)
Definition: btree.c:417
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
_In_ UCHAR EntrySize
Definition: iofuncs.h:640
ULONGLONG VCN
Definition: ntfs.h:400
#define NTFS_INDEX_ENTRY_END
Definition: ntfs.h:61
NTSTATUS CreateBTreeFromIndex(PDEVICE_EXTENSION Vcb, PFILE_RECORD_HEADER FileRecordWithIndex, PNTFS_ATTR_CONTEXT IndexRootContext, PINDEX_ROOT_ATTRIBUTE IndexRoot, PB_TREE *NewTree)
Definition: btree.c:682
USHORT KeyLength
Definition: ntfs.h:420
#define STATUS_END_OF_FILE
Definition: shellext.h:62
uint32_t ULONG_PTR
Definition: typedefs.h:63
union INDEX_ENTRY_ATTRIBUTE::@750 Data
NTSTATUS SetResidentAttributeDataLength(PDEVICE_EXTENSION Vcb, PNTFS_ATTR_CONTEXT AttrContext, ULONG AttrOffset, PFILE_RECORD_HEADER FileRecord, PLARGE_INTEGER DataSize)
Definition: mft.c:891
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
#define STATUS_FILE_CORRUPT_ERROR
Definition: udferr_usr.h:168
NTSTATUS CreateEmptyBTree(PB_TREE *NewTree)
Definition: btree.c:348
Definition: Header.h:8
ULONG Length
Definition: ntfs.h:123
long LONG
Definition: pedump.c:60
PB_TREE_KEY CreateDummyKey(BOOLEAN HasChildNode)
Definition: btree.c:289
union node Node
Definition: types.h:1255
INDEX_HEADER_ATTRIBUTE Header
Definition: ntfs.h:401
unsigned char BOOLEAN
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
Definition: bufpool.h:45
B_TREE_FILENAME_NODE * LesserChild
Definition: ntfs.h:433
ULONG SizeOfEntry
Definition: ntfs.h:391
ULONGLONG GetIndexEntryVCN(PINDEX_ENTRY_ATTRIBUTE IndexEntry)
Definition: btree.c:1641
NTSTATUS AddBitmap(PNTFS_VCB Vcb, PFILE_RECORD_HEADER FileRecord, PNTFS_ATTR_RECORD AttributeAddress, PCWSTR Name, USHORT NameLength)
Definition: attrib.c:72
VOID DestroyBTreeNode(PB_TREE_FILENAME_NODE Node)
Definition: btree.c:1511
BOOLEAN DiskNeedsUpdating
Definition: ntfs.h:444
__wchar_t WCHAR
Definition: xmlstorage.h:180
#define ATTR_RECORD_ALIGNMENT
Definition: ntfs.h:316
#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
ULONG AttributeType
Definition: ntfs.h:389
_In_ PUNICODE_STRING _Inout_ PUNICODE_STRING Destination
Definition: rtlfuncs.h:2891
NTSTATUS SetNonResidentAttributeDataLength(PDEVICE_EXTENSION Vcb, PNTFS_ATTR_CONTEXT AttrContext, ULONG AttrOffset, PFILE_RECORD_HEADER FileRecord, PLARGE_INTEGER DataSize)
Definition: mft.c:756
_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
ULONG GetSizeOfIndexEntries(PB_TREE_FILENAME_NODE Node)
Definition: btree.c:855
NTSTATUS FixupUpdateSequenceArray(PDEVICE_EXTENSION Vcb, PNTFS_RECORD_HEADER Record)
Definition: mft.c:1965
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
VOID DestroyBTreeKey(PB_TREE_KEY Key)
Definition: btree.c:1499
NTSTATUS CreateIndexRootFromBTree(PDEVICE_EXTENSION DeviceExt, PB_TREE Tree, ULONG MaxIndexSize, PINDEX_ROOT_ATTRIBUTE *IndexRoot, ULONG *Length)
Definition: btree.c:910
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
ULONG RtlCompareUnicodeString(PUNICODE_STRING s1, PUNICODE_STRING s2, BOOLEAN UpCase)
Definition: string_lib.cpp:31
NTSTATUS UpdateIndexAllocation(PDEVICE_EXTENSION DeviceExt, PB_TREE Tree, ULONG IndexBufferSize, PFILE_RECORD_HEADER FileRecord)
Definition: btree.c:1182
ULONG TotalSizeOfEntries
Definition: ntfs.h:381
USHORT UsaCount
Definition: ntfs.h:237
#define INDEX_ROOT_LARGE
Definition: ntfs.h:209
static const WCHAR Cleanup[]
Definition: register.c:80
UCHAR ClustersPerIndexRecord
Definition: ntfs.h:392
_In_opt_ PENTER_STATE_SYSTEM_HANDLER _In_opt_ PVOID _In_ LONG _In_opt_ LONG volatile * Number
Definition: ntpoapi.h:204
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
VOID DestroyBTree(PB_TREE Tree)
Definition: btree.c:1542
NTSTATUS CreateIndexBufferFromBTreeNode(PDEVICE_EXTENSION DeviceExt, PB_TREE_FILENAME_NODE Node, ULONG BufferSize, BOOLEAN HasChildren, PINDEX_BUFFER IndexBuffer)
Definition: btree.c:1001
struct _FileName FileName
Definition: fatprocs.h:884
PB_TREE_KEY CreateBTreeKeyFromFilename(ULONGLONG FileReference, PFILENAME_ATTRIBUTE FileNameAttribute)
Definition: btree.c:1461
VOID ReleaseAttributeContext(PNTFS_ATTR_CONTEXT Context)
Definition: mft.c:104
#define INDEX_ROOT_SMALL
Definition: ntfs.h:208
NTSTATUS UpdateFileRecord(PDEVICE_EXTENSION Vcb, ULONGLONG MftIndex, PFILE_RECORD_HEADER FileRecord)
Definition: mft.c:1931
#define FIELD_OFFSET(t, f)
Definition: typedefs.h:254
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
struct INDEX_BUFFER * PINDEX_BUFFER
Definition: ntfs.h:449
#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
__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
#define ALIGN_UP_BY(size, align)
NTSYSAPI void WINAPI RtlSetBits(PRTL_BITMAP, ULONG, ULONG)
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
PB_TREE_FILENAME_NODE CreateBTreeNodeFromIndexNode(PDEVICE_EXTENSION Vcb, PINDEX_ROOT_ATTRIBUTE IndexRoot, PNTFS_ATTR_CONTEXT IndexAllocationAttributeCtx, PINDEX_ENTRY_ATTRIBUTE NodeEntry)
Definition: btree.c:499
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
ULONG GetFileNameAttributeLength(PFILENAME_ATTRIBUTE FileNameAttribute)
Definition: attrib.c:1978
VOID DumpBTreeNode(PB_TREE Tree, PB_TREE_FILENAME_NODE Node, ULONG Number, ULONG Depth)
Definition: btree.c:1583
IN BOOLEAN OUT PSTR Buffer
Definition: progress.h:34
return STATUS_SUCCESS
Definition: btrfs.c:2966
#define COLLATION_FILE_NAME
Definition: ntfs.h:201
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
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
PCONFIGURATION_COMPONENT_DATA RootNode
Definition: macharm.c:19
Definition: dlist.c:348
BOOLEAN HasValidVCN
Definition: ntfs.h:443
#define NT_ASSERT
Definition: rtlfuncs.h:3312