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