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