drivers/filesystems/ntfs/btree.c

   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
  38 PrintAllVCNs(PDEVICE_EXTENSION Vcb,
  39              PNTFS_ATTR_CONTEXT IndexAllocationContext,
  40              ULONG NodeSize)
  41 {
  42     ULONGLONG CurrentOffset = 0;
  43     PINDEX_BUFFER CurrentNode, Buffer;
  44     ULONGLONG BufferSize = AttributeDataLength(&IndexAllocationContext->Record);
  45     ULONGLONG i;
  46     int Count = 0;
  47
  48     Buffer = ExAllocatePoolWithTag(NonPagedPool, BufferSize, TAG_NTFS);
  49
  50     ULONG BytesRead = ReadAttribute(Vcb, IndexAllocationContext, 0, (PCHAR)Buffer, BufferSize);
  51
  52     ASSERT(BytesRead = BufferSize);
  53
  54     CurrentNode = Buffer;
  55
  56     // loop through all the nodes
  57     for (i = 0; i < BufferSize; i += NodeSize)
  58     {
  59         NTSTATUS Status = FixupUpdateSequenceArray(Vcb, &CurrentNode->Ntfs);
  60         if (!NT_SUCCESS(Status))
  61         {
  62             DPRINT1("ERROR: Fixing fixup failed!\n");
  63             continue;
  64         }
  65
  66         DPRINT1("Node #%d, VCN: %I64u\n", Count, CurrentNode->VCN);
  67
  68         CurrentNode = (PINDEX_BUFFER)((ULONG_PTR)CurrentNode + NodeSize);
  69         CurrentOffset += NodeSize;
  70         Count++;
  71     }
  72
  73     ExFreePoolWithTag(Buffer, TAG_NTFS);
  74 }
  75
  76 /**
  77 * @name CompareTreeKeys
  78 * @implemented
  79 *
  80 * Compare two B_TREE_KEY's to determine their order in the tree.
  81 *
  82 * @param Key1
  83 * Pointer to a B_TREE_KEY that will be compared.
  84 *
  85 * @param Key2
  86 * Pointer to the other B_TREE_KEY that will be compared.
  87 *
  88 * @param CaseSensitive
  89 * Boolean indicating if the function should operate in case-sensitive mode. This will be TRUE
  90 * if an application created the file with the FILE_FLAG_POSIX_SEMANTICS flag.
  91 *
  92 * @returns
  93 * 0 if the two keys are equal.
  94 * < 0 if key1 is less thank key2
  95 * > 0 if key1 is greater than key2
  96 *
  97 * @remarks
  98 * Any other key is always less than the final (dummy) key in a node. Key1 must not be the dummy node.
  99 */
 100 LONG
 101 CompareTreeKeys(PB_TREE_KEY Key1, PB_TREE_KEY Key2, BOOLEAN CaseSensitive)
 102 {
 103     UNICODE_STRING Key1Name, Key2Name;
 104     LONG Comparison;
 105
 106     // Key1 must not be the final key (AKA the dummy key)
 107     ASSERT(!(Key1->IndexEntry->Flags & NTFS_INDEX_ENTRY_END));
 108
 109     // If Key2 is the "dummy key", key 1 will always come first
 110     if (Key2->NextKey == NULL)
 111         return -1;
 112
 113     Key1Name.Buffer = Key1->IndexEntry->FileName.Name;
 114     Key1Name.Length = Key1Name.MaximumLength
 115         = Key1->IndexEntry->FileName.NameLength * sizeof(WCHAR);
 116
 117     Key2Name.Buffer = Key2->IndexEntry->FileName.Name;
 118     Key2Name.Length = Key2Name.MaximumLength
 119         = Key2->IndexEntry->FileName.NameLength * sizeof(WCHAR);
 120
 121     // Are the two keys the same length?
 122     if (Key1Name.Length == Key2Name.Length)
 123         return RtlCompareUnicodeString(&Key1Name, &Key2Name, !CaseSensitive);
 124
 125     // Is Key1 shorter?
 126     if (Key1Name.Length < Key2Name.Length)
 127     {
 128         // Truncate KeyName2 to be the same length as KeyName1
 129         Key2Name.Length = Key1Name.Length;
 130
 131         // Compare the names of the same length
 132         Comparison = RtlCompareUnicodeString(&Key1Name, &Key2Name, !CaseSensitive);
 133
 134         // If the truncated names are the same length, the shorter one comes first
 135         if (Comparison == 0)
 136             return -1;
 137     }
 138     else
 139     {
 140         // Key2 is shorter
 141         // Truncate KeyName1 to be the same length as KeyName2
 142         Key1Name.Length = Key2Name.Length;
 143
 144         // Compare the names of the same length
 145         Comparison = RtlCompareUnicodeString(&Key1Name, &Key2Name, !CaseSensitive);
 146
 147         // If the truncated names are the same length, the shorter one comes first
 148         if (Comparison == 0)
 149             return 1;
 150     }
 151
 152     return Comparison;
 153 }
 154
 155 /**
 156 * @name CreateBTreeFromIndex
 157 * @implemented
 158 *
 159 * Parse an index and create a B-Tree in memory from it.
 160 *
 161 * @param IndexRootContext
 162 * Pointer to an NTFS_ATTR_CONTEXT that describes the location of the index root attribute.
 163 *
 164 * @param NewTree
 165 * Pointer to a PB_TREE that will receive the pointer to a newly-created B-Tree.
 166 *
 167 * @returns
 168 * STATUS_SUCCESS on success.
 169 * STATUS_INSUFFICIENT_RESOURCES if an allocation fails.
 170 *
 171 * @remarks
 172 * Allocates memory for the entire tree. Caller is responsible for destroying the tree with DestroyBTree().
 173 */
 174 NTSTATUS
 175 CreateBTreeFromIndex(PNTFS_ATTR_CONTEXT IndexRootContext,
 176                      PINDEX_ROOT_ATTRIBUTE IndexRoot,
 177                      PB_TREE *NewTree)
 178 {
 179     PINDEX_ENTRY_ATTRIBUTE CurrentNodeEntry;
 180     PB_TREE Tree = ExAllocatePoolWithTag(NonPagedPool, sizeof(B_TREE), TAG_NTFS);
 181     PB_TREE_FILENAME_NODE RootNode = ExAllocatePoolWithTag(NonPagedPool, sizeof(B_TREE_FILENAME_NODE), TAG_NTFS);
 182     PB_TREE_KEY CurrentKey = ExAllocatePoolWithTag(NonPagedPool, sizeof(B_TREE_KEY), TAG_NTFS);
 183     ULONG CurrentOffset = IndexRoot->Header.FirstEntryOffset;
 184
 185     DPRINT1("CreateBTreeFromIndex(%p, %p, %p)\n", IndexRootContext, IndexRoot, NewTree);
 186
 187     if (!Tree || !RootNode || !CurrentKey)
 188     {
 189         DPRINT1("Couldn't allocate enough memory for B-Tree!\n");
 190         if (Tree)
 191             ExFreePoolWithTag(Tree, TAG_NTFS);
 192         if (CurrentKey)
 193             ExFreePoolWithTag(CurrentKey, TAG_NTFS);
 194         if (RootNode)
 195             ExFreePoolWithTag(RootNode, TAG_NTFS);
 196         return STATUS_INSUFFICIENT_RESOURCES;
 197     }
 198
 199     RtlZeroMemory(Tree, sizeof(B_TREE));
 200     RtlZeroMemory(RootNode, sizeof(B_TREE_FILENAME_NODE));
 201     RtlZeroMemory(CurrentKey, sizeof(B_TREE_KEY));
 202
 203     // Setup the Tree
 204     RootNode->FirstKey = CurrentKey;
 205     Tree->RootNode = RootNode;
 206
 207     // Make sure we won't try reading past the attribute-end
 208     if (FIELD_OFFSET(INDEX_ROOT_ATTRIBUTE, Header) + IndexRoot->Header.TotalSizeOfEntries > IndexRootContext->Record.Resident.ValueLength)
 209     {
 210         DPRINT1("Filesystem corruption detected!\n");
 211         DestroyBTree(Tree);
 212         return STATUS_FILE_CORRUPT_ERROR;
 213     }
 214
 215     // Start at the first node entry
 216     CurrentNodeEntry = (PINDEX_ENTRY_ATTRIBUTE)((ULONG_PTR)IndexRoot
 217                                                 + FIELD_OFFSET(INDEX_ROOT_ATTRIBUTE, Header)
 218                                                 + IndexRoot->Header.FirstEntryOffset);
 219
 220     // Create a key for each entry in the node
 221     while (CurrentOffset < IndexRoot->Header.TotalSizeOfEntries)
 222     {
 223         // Allocate memory for the current entry
 224         CurrentKey->IndexEntry = ExAllocatePoolWithTag(NonPagedPool, CurrentNodeEntry->Length, TAG_NTFS);
 225         if (!CurrentKey->IndexEntry)
 226         {
 227             DPRINT1("ERROR: Couldn't allocate memory for next key!\n");
 228             DestroyBTree(Tree);
 229             return STATUS_INSUFFICIENT_RESOURCES;
 230         }
 231
 232         RootNode->KeyCount++;
 233
 234         // If this isn't the last entry
 235         if (!(CurrentNodeEntry->Flags & NTFS_INDEX_ENTRY_END))
 236         {
 237             // Create the next key
 238             PB_TREE_KEY NextKey = ExAllocatePoolWithTag(NonPagedPool, sizeof(PB_TREE_KEY), TAG_NTFS);
 239             if (!NextKey)
 240             {
 241                 DPRINT1("ERROR: Couldn't allocate memory for next key!\n");
 242                 DestroyBTree(Tree);
 243                 return STATUS_INSUFFICIENT_RESOURCES;
 244             }
 245
 246             RtlZeroMemory(NextKey, sizeof(PB_TREE_KEY));
 247
 248             // Add NextKey to the end of the list
 249             CurrentKey->NextKey = NextKey;
 250
 251             // Copy the current entry to its key
 252             RtlCopyMemory(CurrentKey->IndexEntry, CurrentNodeEntry, CurrentNodeEntry->Length);
 253
 254             // Make sure this B-Tree is only one level deep (flat list)
 255             if (CurrentKey->IndexEntry->Flags & NTFS_INDEX_ENTRY_NODE)
 256             {
 257                 DPRINT1("TODO: Only directories with single-level B-Trees are supported right now!\n");
 258                 DestroyBTree(Tree);
 259                 return STATUS_NOT_IMPLEMENTED;
 260             }
 261
 262             // Advance to the next entry
 263             CurrentOffset += CurrentNodeEntry->Length;
 264             CurrentNodeEntry = (PINDEX_ENTRY_ATTRIBUTE)((ULONG_PTR)CurrentNodeEntry + CurrentNodeEntry->Length);
 265             CurrentKey = NextKey;
 266         }
 267         else
 268         {
 269             // Copy the final entry to its key
 270             RtlCopyMemory(CurrentKey->IndexEntry, CurrentNodeEntry, CurrentNodeEntry->Length);
 271             CurrentKey->NextKey = NULL;
 272
 273             // Make sure this B-Tree is only one level deep (flat list)
 274             if (CurrentKey->IndexEntry->Flags & NTFS_INDEX_ENTRY_NODE)
 275             {
 276                 DPRINT1("TODO: Only directories with single-level B-Trees are supported right now!\n");
 277                 DestroyBTree(Tree);
 278                 return STATUS_NOT_IMPLEMENTED;
 279             }
 280
 281             break;
 282         }
 283     }
 284
 285     *NewTree = Tree;
 286
 287     return STATUS_SUCCESS;
 288 }
 289
 290 /**
 291 * @name CreateIndexRootFromBTree
 292 * @implemented
 293 *
 294 * Parse a B-Tree in memory and convert it into an index that can be written to disk.
 295 *
 296 * @param DeviceExt
 297 * Pointer to the DEVICE_EXTENSION of the target drive.
 298 *
 299 * @param Tree
 300 * Pointer to a B_TREE that describes the index to be written.
 301 *
 302 * @param MaxIndexSize
 303 * Describes how large the index can be before it will take too much space in the file record.
 304 * After reaching MaxIndexSize, an index can no longer be represented with just an index root
 305 * attribute, and will require an index allocation and $I30 bitmap (TODO).
 306 *
 307 * @param IndexRoot
 308 * Pointer to a PINDEX_ROOT_ATTRIBUTE that will receive a pointer to the newly-created index.
 309 *
 310 * @param Length
 311 * Pointer to a ULONG which will receive the length of the new index root.
 312 *
 313 * @returns
 314 * STATUS_SUCCESS on success.
 315 * STATUS_INSUFFICIENT_RESOURCES if an allocation fails.
 316 * STATUS_NOT_IMPLEMENTED if the new index can't fit within MaxIndexSize.
 317 *
 318 * @remarks
 319 * If the function succeeds, it's the caller's responsibility to free IndexRoot with ExFreePoolWithTag().
 320 */
 321 NTSTATUS
 322 CreateIndexRootFromBTree(PDEVICE_EXTENSION DeviceExt,
 323                          PB_TREE Tree,
 324                          ULONG MaxIndexSize,
 325                          PINDEX_ROOT_ATTRIBUTE *IndexRoot,
 326                          ULONG *Length)
 327 {
 328     ULONG i;
 329     PB_TREE_KEY CurrentKey;
 330     PINDEX_ENTRY_ATTRIBUTE CurrentNodeEntry;
 331     PINDEX_ROOT_ATTRIBUTE NewIndexRoot = ExAllocatePoolWithTag(NonPagedPool,
 332                                                                DeviceExt->NtfsInfo.BytesPerFileRecord,
 333                                                                TAG_NTFS);
 334
 335     DPRINT1("CreateIndexRootFromBTree(%p, %p, 0x%lx, %p, %p)\n", DeviceExt, Tree, MaxIndexSize, IndexRoot, Length);
 336
 337     if (!NewIndexRoot)
 338     {
 339         DPRINT1("Failed to allocate memory for Index Root!\n");
 340         return STATUS_INSUFFICIENT_RESOURCES;
 341     }
 342
 343     // Setup the new index root
 344     RtlZeroMemory(NewIndexRoot, DeviceExt->NtfsInfo.BytesPerFileRecord);
 345
 346     NewIndexRoot->AttributeType = AttributeFileName;
 347     NewIndexRoot->CollationRule = COLLATION_FILE_NAME;
 348     NewIndexRoot->SizeOfEntry = DeviceExt->NtfsInfo.BytesPerIndexRecord;
 349     // If Bytes per index record is less than cluster size, clusters per index record becomes sectors per index
 350     if (NewIndexRoot->SizeOfEntry < DeviceExt->NtfsInfo.BytesPerCluster)
 351         NewIndexRoot->ClustersPerIndexRecord = NewIndexRoot->SizeOfEntry / DeviceExt->NtfsInfo.BytesPerSector;
 352     else
 353         NewIndexRoot->ClustersPerIndexRecord = NewIndexRoot->SizeOfEntry / DeviceExt->NtfsInfo.BytesPerCluster;
 354
 355     // Setup the Index node header
 356     NewIndexRoot->Header.FirstEntryOffset = sizeof(INDEX_HEADER_ATTRIBUTE);
 357     NewIndexRoot->Header.Flags = INDEX_ROOT_SMALL;
 358
 359     // Start summing the total size of this node's entries
 360     NewIndexRoot->Header.TotalSizeOfEntries = NewIndexRoot->Header.FirstEntryOffset;
 361
 362     // Setup each Node Entry
 363     CurrentKey = Tree->RootNode->FirstKey;
 364     CurrentNodeEntry = (PINDEX_ENTRY_ATTRIBUTE)((ULONG_PTR)NewIndexRoot
 365                                                 + FIELD_OFFSET(INDEX_ROOT_ATTRIBUTE, Header)
 366                                                 + NewIndexRoot->Header.FirstEntryOffset);
 367     for (i = 0; i < Tree->RootNode->KeyCount; i++)
 368     {
 369         // Would adding the current entry to the index increase the index size beyond the limit we've set?
 370         ULONG IndexSize = FIELD_OFFSET(INDEX_ROOT_ATTRIBUTE, Header)
 371                           + NewIndexRoot->Header.FirstEntryOffset
 372                           + NewIndexRoot->Header.TotalSizeOfEntries
 373                           + CurrentNodeEntry->Length;
 374         if (IndexSize > MaxIndexSize)
 375         {
 376             DPRINT1("TODO: Adding file would require creating an index allocation!\n");
 377             ExFreePoolWithTag(NewIndexRoot, TAG_NTFS);
 378             return STATUS_NOT_IMPLEMENTED;
 379         }
 380
 381         ASSERT(CurrentKey->IndexEntry->Length != 0);
 382
 383         // Copy the index entry
 384         RtlCopyMemory(CurrentNodeEntry, CurrentKey->IndexEntry, CurrentKey->IndexEntry->Length);
 385
 386         DPRINT1("Index Node Entry Stream Length: %u\nIndex Node Entry Length: %u\n",
 387                 CurrentNodeEntry->KeyLength,
 388                 CurrentNodeEntry->Length);
 389
 390         // Add Length of Current Entry to Total Size of Entries
 391         NewIndexRoot->Header.TotalSizeOfEntries += CurrentNodeEntry->Length;
 392
 393         // Go to the next node entry
 394         CurrentNodeEntry = (PINDEX_ENTRY_ATTRIBUTE)((ULONG_PTR)CurrentNodeEntry + CurrentNodeEntry->Length);
 395
 396         CurrentKey = CurrentKey->NextKey;
 397     }
 398
 399     NewIndexRoot->Header.AllocatedSize = NewIndexRoot->Header.TotalSizeOfEntries;
 400
 401     *IndexRoot = NewIndexRoot;
 402     *Length = NewIndexRoot->Header.AllocatedSize + FIELD_OFFSET(INDEX_ROOT_ATTRIBUTE, Header);
 403
 404     return STATUS_SUCCESS;
 405 }
 406
 407 VOID
 408 DestroyBTreeKey(PB_TREE_KEY Key)
 409 {
 410     if (Key->IndexEntry)
 411         ExFreePoolWithTag(Key->IndexEntry, TAG_NTFS);
 412
 413     // We'll destroy Key->LesserChild here after we start using it
 414
 415     ExFreePoolWithTag(Key, TAG_NTFS);
 416 }
 417
 418 VOID
 419 DestroyBTreeNode(PB_TREE_FILENAME_NODE Node)
 420 {
 421     PB_TREE_KEY NextKey;
 422     PB_TREE_KEY CurrentKey = Node->FirstKey;
 423     ULONG i;
 424     for (i = 0; i < Node->KeyCount; i++)
 425     {
 426         NT_ASSERT(CurrentKey);
 427         NextKey = CurrentKey->NextKey;
 428         DestroyBTreeKey(CurrentKey);
 429         CurrentKey = NextKey;
 430     }
 431
 432     NT_ASSERT(NextKey == NULL);
 433
 434     ExFreePoolWithTag(Node, TAG_NTFS);
 435 }
 436
 437 /**
 438 * @name DestroyBTree
 439 * @implemented
 440 *
 441 * Destroys a B-Tree.
 442 *
 443 * @param Tree
 444 * Pointer to the B_TREE which will be destroyed.
 445 *
 446 * @remarks
 447 * Destroys every bit of data stored in the tree.
 448 */
 449 VOID
 450 DestroyBTree(PB_TREE Tree)
 451 {
 452     DestroyBTreeNode(Tree->RootNode);
 453     ExFreePoolWithTag(Tree, TAG_NTFS);
 454 }
 455
 456 VOID
 457 DumpBTreeKey(PB_TREE_KEY Key, ULONG Number, ULONG Depth)
 458 {
 459     ULONG i;
 460     for (i = 0; i < Depth; i++)
 461         DbgPrint(" ");
 462     DbgPrint(" Key #%d", Number);
 463
 464     if (!(Key->IndexEntry->Flags & NTFS_INDEX_ENTRY_END))
 465     {
 466         UNICODE_STRING FileName;
 467         FileName.Length = Key->IndexEntry->FileName.NameLength * sizeof(WCHAR);
 468         FileName.MaximumLength = FileName.Length;
 469         FileName.Buffer = Key->IndexEntry->FileName.Name;
 470         DbgPrint(" '%wZ'\n", &FileName);
 471     }
 472     else
 473     {
 474         DbgPrint(" (Dummy Key)\n");
 475     }
 476 }
 477
 478 VOID
 479 DumpBTreeNode(PB_TREE_FILENAME_NODE Node, ULONG Number, ULONG Depth)
 480 {
 481     PB_TREE_KEY CurrentKey;
 482     ULONG i;
 483     for (i = 0; i < Depth; i++)
 484         DbgPrint(" ");
 485     DbgPrint("Node #%d, Depth %d\n", Number, Depth);
 486
 487     CurrentKey = Node->FirstKey;
 488     for (i = 0; i < Node->KeyCount; i++)
 489     {
 490         DumpBTreeKey(CurrentKey, i, Depth);
 491         CurrentKey = CurrentKey->NextKey;
 492     }
 493 }
 494
 495 /**
 496 * @name DumpBTree
 497 * @implemented
 498 *
 499 * Displays a B-Tree.
 500 *
 501 * @param Tree
 502 * Pointer to the B_TREE which will be displayed.
 503 *
 504 * @remarks
 505 * Displays a diagnostic summary of a B_TREE.
 506 */
 507 VOID
 508 DumpBTree(PB_TREE Tree)
 509 {
 510     DbgPrint("B_TREE @ %p\n", Tree);
 511     DumpBTreeNode(Tree->RootNode, 0, 0);
 512 }
 513
 514 // Calculates start of Index Buffer relative to the index allocation, given the node's VCN
 515 ULONGLONG
 516 GetAllocationOffsetFromVCN(PDEVICE_EXTENSION DeviceExt,
 517                            ULONG IndexBufferSize,
 518                            ULONGLONG Vcn)
 519 {
 520     if (IndexBufferSize < DeviceExt->NtfsInfo.BytesPerCluster)
 521         return Vcn * DeviceExt->NtfsInfo.BytesPerSector;
 522
 523     return Vcn * DeviceExt->NtfsInfo.BytesPerCluster;
 524 }
 525
 526 /**
 527 * @name NtfsInsertKey
 528 * @implemented
 529 *
 530 * Inserts a FILENAME_ATTRIBUTE into a B-Tree node.
 531 *
 532 * @param FileReference
 533 * Reference number to the file being added. This will be a combination of the MFT index and update sequence number.
 534 *
 535 * @param FileNameAttribute
 536 * Pointer to a FILENAME_ATTRIBUTE which is the data for the key that will be added to the tree. A copy will be made.
 537 *
 538 * @param Node
 539 * Pointer to a B_TREE_FILENAME_NODE into which a new key will be inserted, in order.
 540 *
 541 * @param CaseSensitive
 542 * Boolean indicating if the function should operate in case-sensitive mode. This will be TRUE
 543 * if an application created the file with the FILE_FLAG_POSIX_SEMANTICS flag.
 544 *
 545 * @remarks
 546 * A node is always sorted, with the least comparable filename stored first and a dummy key to mark the end.
 547 */
 548 NTSTATUS
 549 NtfsInsertKey(ULONGLONG FileReference,
 550               PFILENAME_ATTRIBUTE FileNameAttribute,
 551               PB_TREE_FILENAME_NODE Node,
 552               BOOLEAN CaseSensitive)
 553 {
 554     // Calculate size of Attribute and Index Entry
 555     ULONG AttributeSize = GetFileNameAttributeLength(FileNameAttribute);
 556     ULONG EntrySize = ALIGN_UP_BY(AttributeSize + FIELD_OFFSET(INDEX_ENTRY_ATTRIBUTE, FileName), 8);
 557     PINDEX_ENTRY_ATTRIBUTE NewEntry;
 558     PB_TREE_KEY NewKey, CurrentKey, PreviousKey;
 559     ULONG i;
 560
 561     DPRINT1("NtfsInsertKey(0x%02I64, %p, %p, %s)\n",
 562             FileReference,
 563             FileNameAttribute,
 564             Node,
 565             CaseSensitive ? "TRUE" : "FALSE");
 566
 567     // Create a new Index Entry for the file
 568     NewEntry = ExAllocatePoolWithTag(NonPagedPool, EntrySize, TAG_NTFS);
 569     if (!NewEntry)
 570     {
 571         DPRINT1("ERROR: Failed to allocate memory for Index Entry!\n");
 572         return STATUS_INSUFFICIENT_RESOURCES;
 573     }
 574
 575     // Setup the Index Entry
 576     RtlZeroMemory(NewEntry, EntrySize);
 577     NewEntry->Data.Directory.IndexedFile = FileReference;
 578     NewEntry->Length = EntrySize;
 579     NewEntry->KeyLength = AttributeSize;
 580
 581     // Copy the FileNameAttribute
 582     RtlCopyMemory(&NewEntry->FileName, FileNameAttribute, AttributeSize);
 583
 584     // Setup the New Key
 585     NewKey = ExAllocatePoolWithTag(NonPagedPool, sizeof(B_TREE_KEY), TAG_NTFS);
 586     if (!NewKey)
 587     {
 588         DPRINT1("ERROR: Failed to allocate memory for new key!\n");
 589         ExFreePoolWithTag(NewEntry, TAG_NTFS);
 590         return STATUS_INSUFFICIENT_RESOURCES;
 591     }
 592     NewKey->IndexEntry = NewEntry;
 593     NewKey->NextKey = NULL;
 594
 595     // Find where to insert the key
 596     CurrentKey = Node->FirstKey;
 597     PreviousKey = NULL;
 598     for (i = 0; i < Node->KeyCount; i++)
 599     {
 600         // Should the New Key go before the current key?
 601         LONG Comparison = CompareTreeKeys(NewKey, CurrentKey, CaseSensitive);
 602
 603         ASSERT(Comparison != 0);
 604
 605         // Is NewKey < CurrentKey?
 606         if (Comparison < 0)
 607         {
 608             // Insert New Key before Current Key
 609             NewKey->NextKey = CurrentKey;
 610
 611             // was CurrentKey the first key?
 612             if (CurrentKey == Node->FirstKey)
 613                 Node->FirstKey = NewKey;
 614             else
 615                 PreviousKey->NextKey = NewKey;
 616             break;
 617         }
 618
 619         PreviousKey = CurrentKey;
 620         CurrentKey = CurrentKey->NextKey;
 621     }
 622
 623     Node->KeyCount++;
 624
 625     // NewEntry and NewKey will be destroyed later by DestroyBTree()
 626
 627     return STATUS_SUCCESS;
 628 }