Ros-diffs December 2017

ros-diffs@reactos.org

26 participants
355 discussions

[reactos] 01/01: [SERVMAN] fix status-bar text truncation, update german localization CORE-14092

by Joachim Henze

https://git.reactos.org/?p=reactos.git;a=commitdiff;h=8624801eb8fac8c0f361f… commit 8624801eb8fac8c0f361f74eb437c854d176e37e Author: Joachim Henze <Joachim.Henze(a)reactos.org> AuthorDate: Sun Dec 10 14:08:29 2017 +0100 [SERVMAN] fix status-bar text truncation, update german localization CORE-14092 --- base/applications/mscutils/servman/lang/de-DE.rc | 30 ++++++++++++------------ base/applications/mscutils/servman/mainwnd.c | 4 ++-- 2 files changed, 17 insertions(+), 17 deletions(-) diff --git a/base/applications/mscutils/servman/lang/de-DE.rc b/base/applications/mscutils/servman/lang/de-DE.rc index a3819c6fe6..3aa7303aaa 100644 --- a/base/applications/mscutils/servman/lang/de-DE.rc +++ b/base/applications/mscutils/servman/lang/de-DE.rc @@ -123,31 +123,31 @@ BEGIN END IDD_RECOVERY DIALOGEX 6, 6, 253, 232 -CAPTION "Recovery" +CAPTION "Wiederherstellen" FONT 8, "MS Shell Dlg", 0, 0 STYLE DS_SHELLFONT | WS_BORDER | WS_VISIBLE | WS_DLGFRAME | WS_SYSMENU | WS_GROUP | WS_TABSTOP BEGIN - LTEXT "Select the computer's response if this service fails.", IDC_STATIC, 7, 7, 238, 8 - LTEXT "&First failure:", IDC_STATIC, 7, 24, 92, 8 + LTEXT "Wählen Sie, was bei Dienstausfall durchgeführt werden soll.", IDC_STATIC, 7, 7, 238, 8 + LTEXT "&Erster Fehlschlag:", IDC_STATIC, 7, 24, 92, 8 COMBOBOX IDC_FIRST_FAILURE, 104, 22, 141, 147, WS_CHILD | WS_VISIBLE | WS_TABSTOP | CBS_DROPDOWNLIST - LTEXT "&Second failure:", IDC_STATIC, 7, 41, 92, 8 + LTEXT "Zwei&ter Fehlschlag:", IDC_STATIC, 7, 41, 92, 8 COMBOBOX IDC_SECOND_FAILURE, 104, 39, 141, 147, WS_CHILD | WS_VISIBLE | WS_TABSTOP | CBS_DROPDOWNLIST - LTEXT "Subsequent failures:", IDC_STATIC, 7, 58, 92, 8 + LTEXT "Weitere &Fehlschläge:", IDC_STATIC, 7, 58, 92, 8 COMBOBOX IDC_SUBSEQUENT_FAILURES, 104, 56, 141, 147, WS_CHILD | WS_VISIBLE | WS_TABSTOP | CBS_DROPDOWNLIST - LTEXT "Reset fail c&ounter after:", IDC_STATIC, 7, 75, 72, 8 + LTEXT "Fehlerzähler &nach", IDC_STATIC, 7, 75, 72, 8 EDITTEXT IDC_RESET_TIME, 104, 73, 40, 13, WS_CHILD | WS_VISIBLE | WS_BORDER | WS_TABSTOP | ES_LEFT | ES_AUTOHSCROLL | ES_NUMBER - LTEXT "days", IDC_STATIC, 150, 75, 95, 8 - LTEXT "Restart ser&vice after:", IDC_RESTART_TEXT1, 7, 92, 92, 8 + LTEXT "Tagen auf Null zurücksetzen", IDC_STATIC, 150, 75, 95, 8 + LTEXT "Dien&st nach", IDC_RESTART_TEXT1, 7, 92, 92, 8 EDITTEXT IDC_RESTART_TIME, 104, 90, 40, 13, WS_CHILD | WS_VISIBLE | WS_BORDER | WS_TABSTOP | ES_LEFT | ES_AUTOHSCROLL | ES_NUMBER - LTEXT "minutes", IDC_RESTART_TEXT2, 150, 92, 95, 8 - GROUPBOX "Run program", IDC_RUN_GROUPBOX, 7, 108, 238, 80 - LTEXT "&Program:", IDC_RUN_TEXT1, 14, 121, 168, 8 + LTEXT "Minuten neu starten", IDC_RESTART_TEXT2, 150, 92, 95, 8 + GROUPBOX "Programm ausführen", IDC_RUN_GROUPBOX, 7, 108, 238, 80 + LTEXT "&Programm:", IDC_RUN_TEXT1, 14, 121, 168, 8 EDITTEXT IDC_PROGRAM, 14, 131, 165, 14 - PUSHBUTTON "&Browse...", IDC_BROWSE_PROGRAM, 180, 131, 58, 14 - LTEXT "&Command line parameters:", IDC_RUN_TEXT2, 14, 155, 108, 8 + PUSHBUTTON "D&urchsuchen...", IDC_BROWSE_PROGRAM, 180, 131, 58, 14 + LTEXT "Befeh&lszeilenparameter:", IDC_RUN_TEXT2, 14, 155, 108, 8 EDITTEXT IDC_PARAMETERS, 128, 152, 110, 14 - AUTOCHECKBOX "Append fail count to &end of command line (/fail=%1%)", IDC_ADD_FAILCOUNT, 14, 171, 219, 10, WS_CHILD | WS_VISIBLE | WS_TABSTOP | BS_TOP | BS_MULTILINE - PUSHBUTTON "&Restart Computer Options...", IDC_RESTART_OPTIONS, 116, 197, 129, 14 + AUTOCHECKBOX "Fehler&zähler zur Befehlszeile hinzufügen (/fail=%1%)", IDC_ADD_FAILCOUNT, 14, 171, 219, 10, WS_CHILD | WS_VISIBLE | WS_TABSTOP | BS_TOP | BS_MULTILINE + PUSHBUTTON "Neustart&optionen...", IDC_RESTART_OPTIONS, 165, 197, 80, 14 END IDD_DLG_DEPEND DIALOGEX 6, 6, 253, 225 diff --git a/base/applications/mscutils/servman/mainwnd.c b/base/applications/mscutils/servman/mainwnd.c index a28e9c8833..9358bd4c14 100644 --- a/base/applications/mscutils/servman/mainwnd.c +++ b/base/applications/mscutils/servman/mainwnd.c @@ -3,7 +3,7 @@ * LICENSE: GPL - See COPYING in the top level directory * FILE: base/applications/mscutils/servman/mainwnd.c * PURPOSE: Main window message handler - * COPYRIGHT: Copyright 2006-20015 Ged Murphy <gedmurphy(a)reactos.org> + * COPYRIGHT: Copyright 2006-2017 Ged Murphy <gedmurphy(a)reactos.org> * */ @@ -306,7 +306,7 @@ pCreateToolbar(PMAIN_WND_INFO Info) static BOOL CreateStatusBar(PMAIN_WND_INFO Info) { - INT StatWidths[] = {110, -1}; /* widths of status bar */ + INT StatWidths[] = {130, -1}; /* widths of status bar */ Info->hStatus = CreateWindowEx(0, STATUSCLASSNAME,

6 years, 9 months

[reactos] 72/72: Merge branch 'ntfs_rebase'

by Thomas Faber

https://git.reactos.org/?p=reactos.git;a=commitdiff;h=03be7587ebb45e4e9fb49… commit 03be7587ebb45e4e9fb49b47ef25adef6fb88e20 Merge: 3a69fd4e96 b5555650a8 Author: Thomas Faber <thomas.faber(a)reactos.org> AuthorDate: Sun Dec 10 12:46:33 2017 +0100 Merge branch 'ntfs_rebase' boot/bootdata/hivesys.inf | 2 + drivers/filesystems/ntfs/CMakeLists.txt | 1 + drivers/filesystems/ntfs/attrib.c | 1391 ++++++++++++++- drivers/filesystems/ntfs/blockdev.c | 179 +- drivers/filesystems/ntfs/btree.c | 2022 ++++++++++++++++++++++ drivers/filesystems/ntfs/create.c | 454 ++++- drivers/filesystems/ntfs/dirctl.c | 34 +- drivers/filesystems/ntfs/dispatch.c | 22 +- drivers/filesystems/ntfs/fcb.c | 36 +- drivers/filesystems/ntfs/finfo.c | 389 ++++- drivers/filesystems/ntfs/fsctl.c | 22 +- drivers/filesystems/ntfs/mft.c | 2859 +++++++++++++++++++++++++++++-- drivers/filesystems/ntfs/misc.c | 58 + drivers/filesystems/ntfs/ntfs.c | 41 +- drivers/filesystems/ntfs/ntfs.h | 420 ++++- drivers/filesystems/ntfs/rw.c | 470 ++++- drivers/filesystems/ntfs/volinfo.c | 111 +- 17 files changed, 8300 insertions(+), 211 deletions(-)

6 years, 9 months

[reactos] 71/72: [NTFS] Fix the FileNamesInformation/FileNameInformation class confusion that was spotted on FastFAT. What should also be fixed is the partial return of data on first entry enumeration.

by Pierre Schweitzer

https://git.reactos.org/?p=reactos.git;a=commitdiff;h=b5555650a83d3aec7c002… commit b5555650a83d3aec7c002f2215c0759c4efac832 Author: Pierre Schweitzer <pierre(a)reactos.org> AuthorDate: Sun Dec 10 11:25:48 2017 +0100 [NTFS] Fix the FileNamesInformation/FileNameInformation class confusion that was spotted on FastFAT. What should also be fixed is the partial return of data on first entry enumeration. --- drivers/filesystems/ntfs/dirctl.c | 24 ++++++++++++------------ 1 file changed, 12 insertions(+), 12 deletions(-) diff --git a/drivers/filesystems/ntfs/dirctl.c b/drivers/filesystems/ntfs/dirctl.c index 61316cb77d..ab784fce3d 100644 --- a/drivers/filesystems/ntfs/dirctl.c +++ b/drivers/filesystems/ntfs/dirctl.c @@ -61,16 +61,16 @@ NtfsGetFileSize(PDEVICE_EXTENSION DeviceExt, static NTSTATUS -NtfsGetNameInformation(PDEVICE_EXTENSION DeviceExt, - PFILE_RECORD_HEADER FileRecord, - ULONGLONG MFTIndex, - PFILE_NAMES_INFORMATION Info, - ULONG BufferLength) +NtfsGetNamesInformation(PDEVICE_EXTENSION DeviceExt, + PFILE_RECORD_HEADER FileRecord, + ULONGLONG MFTIndex, + PFILE_NAMES_INFORMATION Info, + ULONG BufferLength) { ULONG Length; PFILENAME_ATTRIBUTE FileName; - DPRINT("NtfsGetNameInformation() called\n"); + DPRINT("NtfsGetNamesInformation() called\n"); FileName = GetBestFileNameFromRecord(DeviceExt, FileRecord); if (FileName == NULL) @@ -395,12 +395,12 @@ NtfsQueryDirectory(PNTFS_IRP_CONTEXT IrpContext) switch (FileInformationClass) { - case FileNameInformation: - Status = NtfsGetNameInformation(DeviceExtension, - FileRecord, - MFTRecord, - (PFILE_NAMES_INFORMATION)Buffer, - BufferLength); + case FileNamesInformation: + Status = NtfsGetNamesInformation(DeviceExtension, + FileRecord, + MFTRecord, + (PFILE_NAMES_INFORMATION)Buffer, + BufferLength); break; case FileDirectoryInformation:

6 years, 9 months

[reactos] 70/72: [NTFS] - Respect NTFS' file ordering when enumerating a directory. Split off part of BrowseIndexEntries() into a separate function to simplify the code. AddNewMftEntry() - Zero the (larger) buffer for the bitmap prior to reading the bitmap. BrowseIndexEntries() - Check sub-nodes before checking an index entry. Read and use the index bitmap when checking sub-nodes. +BrowseSubNodeIndexEntries() - Called for sub-nodes of an index when browsing index entries. +NtfsDumpData() - Diagn

by Trevor Thompson

https://git.reactos.org/?p=reactos.git;a=commitdiff;h=1ac7128da037b1a770ab1… commit 1ac7128da037b1a770ab1468e604fe44c8857ec3 Author: Trevor Thompson <tmt256(a)email.vccs.edu> AuthorDate: Sat Sep 9 23:10:52 2017 +0000 [NTFS] - Respect NTFS' file ordering when enumerating a directory. Split off part of BrowseIndexEntries() into a separate function to simplify the code. AddNewMftEntry() - Zero the (larger) buffer for the bitmap prior to reading the bitmap. BrowseIndexEntries() - Check sub-nodes before checking an index entry. Read and use the index bitmap when checking sub-nodes. +BrowseSubNodeIndexEntries() - Called for sub-nodes of an index when browsing index entries. +NtfsDumpData() - Diagnostic function which allows for visualizing a series of bytes. svn path=/branches/GSoC_2016/NTFS/; revision=75817 --- drivers/filesystems/ntfs/mft.c | 340 ++++++++++++++++++++++++++++++++-------- drivers/filesystems/ntfs/ntfs.h | 6 + 2 files changed, 284 insertions(+), 62 deletions(-) diff --git a/drivers/filesystems/ntfs/mft.c b/drivers/filesystems/ntfs/mft.c index 9d96bad239..4896d6d550 100644 --- a/drivers/filesystems/ntfs/mft.c +++ b/drivers/filesystems/ntfs/mft.c @@ -1988,6 +1988,7 @@ AddNewMftEntry(PFILE_RECORD_HEADER FileRecord, ReleaseAttributeContext(BitmapContext); return STATUS_INSUFFICIENT_RESOURCES; } + RtlZeroMemory(BitmapBuffer, BitmapDataSize + sizeof(ULONG)); // Get a ULONG-aligned pointer for the bitmap itself BitmapData = (PUCHAR)ALIGN_UP_BY((ULONG_PTR)BitmapBuffer, sizeof(ULONG)); @@ -2765,10 +2766,158 @@ DumpIndexEntry(PINDEX_ENTRY_ATTRIBUTE IndexEntry) } #endif +NTSTATUS +BrowseSubNodeIndexEntries(PNTFS_VCB Vcb, + PFILE_RECORD_HEADER MftRecord, + ULONG IndexBlockSize, + PUNICODE_STRING FileName, + PNTFS_ATTR_CONTEXT IndexAllocationContext, + PRTL_BITMAP Bitmap, + ULONGLONG VCN, + PULONG StartEntry, + PULONG CurrentEntry, + BOOLEAN DirSearch, + BOOLEAN CaseSensitive, + ULONGLONG *OutMFTIndex) +{ + PINDEX_BUFFER IndexRecord; + ULONGLONG Offset; + ULONG BytesRead; + PINDEX_ENTRY_ATTRIBUTE FirstEntry; + PINDEX_ENTRY_ATTRIBUTE LastEntry; + PINDEX_ENTRY_ATTRIBUTE IndexEntry; + ULONG NodeNumber; + NTSTATUS Status; + + DPRINT("BrowseSubNodeIndexEntries(%p, %p, %lu, %wZ, %p, %p, %I64d, %lu, %lu, %s, %s, %p)\n", + Vcb, + MftRecord, + IndexBlockSize, + FileName, + IndexAllocationContext, + Bitmap, + VCN, + *StartEntry, + *CurrentEntry, + "FALSE", + DirSearch ? "TRUE" : "FALSE", + CaseSensitive ? "TRUE" : "FALSE", + OutMFTIndex); + + // Calculate node number as VCN / Clusters per index record + NodeNumber = VCN / (Vcb->NtfsInfo.BytesPerIndexRecord / Vcb->NtfsInfo.BytesPerCluster); + + // Is the bit for this node clear in the bitmap? + if (!RtlCheckBit(Bitmap, NodeNumber)) + { + DPRINT1("File system corruption detected, node with VCN %I64u is being reused or is marked as deleted.\n", VCN); + return STATUS_DATA_ERROR; + } + + // Clear the bit for this node so it can't be recursively referenced + RtlClearBits(Bitmap, NodeNumber, 1); + + // Allocate memory for the index record + IndexRecord = ExAllocatePoolWithTag(NonPagedPool, IndexBlockSize, TAG_NTFS); + if (!IndexRecord) + { + DPRINT1("Unable to allocate memory for index record!\n"); + return STATUS_INSUFFICIENT_RESOURCES; + } + + // Calculate offset of index record + Offset = VCN * Vcb->NtfsInfo.BytesPerCluster; + + // Read the index record + BytesRead = ReadAttribute(Vcb, IndexAllocationContext, Offset, (PCHAR)IndexRecord, IndexBlockSize); + if (BytesRead != IndexBlockSize) + { + DPRINT1("Unable to read index record!\n"); + ExFreePoolWithTag(IndexRecord, TAG_NTFS); + return STATUS_UNSUCCESSFUL; + } + + // Assert that we're dealing with an index record here + ASSERT(IndexRecord->Ntfs.Type == NRH_INDX_TYPE); + + // Apply the fixup array to the index record + Status = FixupUpdateSequenceArray(Vcb, &((PFILE_RECORD_HEADER)IndexRecord)->Ntfs); + if (!NT_SUCCESS(Status)) + { + ExFreePoolWithTag(IndexRecord, TAG_NTFS); + DPRINT1("Failed to apply fixup array!\n"); + return Status; + } + + ASSERT(IndexRecord->Header.AllocatedSize + FIELD_OFFSET(INDEX_BUFFER, Header) == IndexBlockSize); + FirstEntry = (PINDEX_ENTRY_ATTRIBUTE)((ULONG_PTR)&IndexRecord->Header + IndexRecord->Header.FirstEntryOffset); + LastEntry = (PINDEX_ENTRY_ATTRIBUTE)((ULONG_PTR)&IndexRecord->Header + IndexRecord->Header.TotalSizeOfEntries); + ASSERT(LastEntry <= (PINDEX_ENTRY_ATTRIBUTE)((ULONG_PTR)IndexRecord + IndexBlockSize)); + + // Loop through all Index Entries of index, starting with FirstEntry + IndexEntry = FirstEntry; + while (IndexEntry <= LastEntry) + { + // Does IndexEntry have a sub-node? + if (IndexEntry->Flags & NTFS_INDEX_ENTRY_NODE) + { + if (!(IndexRecord->Header.Flags & INDEX_NODE_LARGE) || !IndexAllocationContext) + { + DPRINT1("Filesystem corruption detected!\n"); + } + else + { + Status = BrowseSubNodeIndexEntries(Vcb, + MftRecord, + IndexBlockSize, + FileName, + IndexAllocationContext, + Bitmap, + GetIndexEntryVCN(IndexEntry), + StartEntry, + CurrentEntry, + DirSearch, + CaseSensitive, + OutMFTIndex); + if (NT_SUCCESS(Status)) + { + ExFreePoolWithTag(IndexRecord, TAG_NTFS); + return Status; + } + } + } + + // Are we done? + if (IndexEntry->Flags & NTFS_INDEX_ENTRY_END) + break; + + // If we've found a file whose index is greater than or equal to StartEntry that matches the search criteria + if ((IndexEntry->Data.Directory.IndexedFile & NTFS_MFT_MASK) >= NTFS_FILE_FIRST_USER_FILE && + *CurrentEntry >= *StartEntry && + IndexEntry->FileName.NameType != NTFS_FILE_NAME_DOS && + CompareFileName(FileName, IndexEntry, DirSearch, CaseSensitive)) + { + *StartEntry = *CurrentEntry; + *OutMFTIndex = (IndexEntry->Data.Directory.IndexedFile & NTFS_MFT_MASK); + ExFreePoolWithTag(IndexRecord, TAG_NTFS); + return STATUS_SUCCESS; + } + + // Advance to the next index entry + (*CurrentEntry) += 1; + ASSERT(IndexEntry->Length >= sizeof(INDEX_ENTRY_ATTRIBUTE)); + IndexEntry = (PINDEX_ENTRY_ATTRIBUTE)((PCHAR)IndexEntry + IndexEntry->Length); + } + + ExFreePoolWithTag(IndexRecord, TAG_NTFS); + + return STATUS_OBJECT_PATH_NOT_FOUND; +} + NTSTATUS BrowseIndexEntries(PDEVICE_EXTENSION Vcb, PFILE_RECORD_HEADER MftRecord, - PCHAR IndexRecord, + PINDEX_ROOT_ATTRIBUTE IndexRecord, ULONG IndexBlockSize, PINDEX_ENTRY_ATTRIBUTE FirstEntry, PINDEX_ENTRY_ATTRIBUTE LastEntry, @@ -2780,11 +2929,12 @@ BrowseIndexEntries(PDEVICE_EXTENSION Vcb, ULONGLONG *OutMFTIndex) { NTSTATUS Status; - ULONG RecordOffset; PINDEX_ENTRY_ATTRIBUTE IndexEntry; - PNTFS_ATTR_CONTEXT IndexAllocationCtx; - ULONGLONG IndexAllocationSize; - PINDEX_BUFFER IndexBuffer; + PNTFS_ATTR_CONTEXT IndexAllocationContext; + PNTFS_ATTR_CONTEXT BitmapContext; + PCHAR *BitmapMem; + ULONG *BitmapPtr; + RTL_BITMAP Bitmap; DPRINT("BrowseIndexEntries(%p, %p, %p, %lu, %p, %p, %wZ, %lu, %lu, %s, %s, %p)\n", Vcb, @@ -2800,10 +2950,100 @@ BrowseIndexEntries(PDEVICE_EXTENSION Vcb, CaseSensitive ? "TRUE" : "FALSE", OutMFTIndex); + // Find the $I30 index allocation, if there is one + Status = FindAttribute(Vcb, MftRecord, AttributeIndexAllocation, L"$I30", 4, &IndexAllocationContext, NULL); + if (NT_SUCCESS(Status)) + { + ULONGLONG BitmapLength; + // Find the bitmap attribute for the index + Status = FindAttribute(Vcb, MftRecord, AttributeBitmap, L"$I30", 4, &BitmapContext, NULL); + if (!NT_SUCCESS(Status)) + { + DPRINT1("Potential file system corruption detected!\n"); + ReleaseAttributeContext(IndexAllocationContext); + return Status; + } + + // Get the length of the bitmap attribute + BitmapLength = AttributeDataLength(BitmapContext->pRecord); + + // Allocate memory for the bitmap, including some padding; RtlInitializeBitmap() wants a pointer + // that's ULONG-aligned, and it wants the size of the memory allocated for it to be a ULONG-multiple. + BitmapMem = ExAllocatePoolWithTag(NonPagedPool, BitmapLength + sizeof(ULONG), TAG_NTFS); + if (!BitmapMem) + { + DPRINT1("Error: failed to allocate bitmap!"); + ReleaseAttributeContext(BitmapContext); + ReleaseAttributeContext(IndexAllocationContext); + return STATUS_INSUFFICIENT_RESOURCES; + } + + RtlZeroMemory(BitmapMem, BitmapLength + sizeof(ULONG)); + + // RtlInitializeBitmap() wants a pointer that's ULONG-aligned. + BitmapPtr = (PULONG)ALIGN_UP_BY((ULONG_PTR)BitmapMem, sizeof(ULONG)); + + // Read the existing bitmap data + Status = ReadAttribute(Vcb, BitmapContext, 0, (PCHAR)BitmapPtr, BitmapLength); + if (!NT_SUCCESS(Status)) + { + DPRINT1("ERROR: Failed to read bitmap attribute!\n"); + ExFreePoolWithTag(BitmapMem, TAG_NTFS); + ReleaseAttributeContext(BitmapContext); + ReleaseAttributeContext(IndexAllocationContext); + return Status; + } + + // Initialize bitmap + RtlInitializeBitMap(&Bitmap, BitmapPtr, BitmapLength * 8); + } + else + { + // Couldn't find an index allocation + IndexAllocationContext = NULL; + } + + + // Loop through all Index Entries of index, starting with FirstEntry IndexEntry = FirstEntry; - while (IndexEntry < LastEntry && - !(IndexEntry->Flags & NTFS_INDEX_ENTRY_END)) + while (IndexEntry <= LastEntry) { + // Does IndexEntry have a sub-node? + if (IndexEntry->Flags & NTFS_INDEX_ENTRY_NODE) + { + if (!(IndexRecord->Header.Flags & INDEX_ROOT_LARGE) || !IndexAllocationContext) + { + DPRINT1("Filesystem corruption detected!\n"); + } + else + { + Status = BrowseSubNodeIndexEntries(Vcb, + MftRecord, + IndexBlockSize, + FileName, + IndexAllocationContext, + &Bitmap, + GetIndexEntryVCN(IndexEntry), + StartEntry, + CurrentEntry, + DirSearch, + CaseSensitive, + OutMFTIndex); + if (NT_SUCCESS(Status)) + { + ExFreePoolWithTag(BitmapMem, TAG_NTFS); + ReleaseAttributeContext(BitmapContext); + ReleaseAttributeContext(IndexAllocationContext); + return Status; + } + } + } + + // Are we done? + if (IndexEntry->Flags & NTFS_INDEX_ENTRY_END) + break; + + // If we've found a file whose index is greater than or equal to StartEntry that matches the search criteria if ((IndexEntry->Data.Directory.IndexedFile & NTFS_MFT_MASK) >= NTFS_FILE_FIRST_USER_FILE && *CurrentEntry >= *StartEntry && IndexEntry->FileName.NameType != NTFS_FILE_NAME_DOS && @@ -2811,71 +3051,29 @@ BrowseIndexEntries(PDEVICE_EXTENSION Vcb, { *StartEntry = *CurrentEntry; *OutMFTIndex = (IndexEntry->Data.Directory.IndexedFile & NTFS_MFT_MASK); + if (IndexAllocationContext) + { + ExFreePoolWithTag(BitmapMem, TAG_NTFS); + ReleaseAttributeContext(BitmapContext); + ReleaseAttributeContext(IndexAllocationContext); + } return STATUS_SUCCESS; } + // Advance to the next index entry (*CurrentEntry) += 1; ASSERT(IndexEntry->Length >= sizeof(INDEX_ENTRY_ATTRIBUTE)); IndexEntry = (PINDEX_ENTRY_ATTRIBUTE)((PCHAR)IndexEntry + IndexEntry->Length); } - /* If we're already browsing a subnode */ - if (IndexRecord == NULL) - { - return STATUS_OBJECT_PATH_NOT_FOUND; - } - - /* If there's no subnode */ - if (!(IndexEntry->Flags & NTFS_INDEX_ENTRY_NODE)) - { - return STATUS_OBJECT_PATH_NOT_FOUND; - } - - Status = FindAttribute(Vcb, MftRecord, AttributeIndexAllocation, L"$I30", 4, &IndexAllocationCtx, NULL); - if (!NT_SUCCESS(Status)) + if (IndexAllocationContext) { - DPRINT1("Corrupted filesystem!\n"); - return Status; - } - - IndexAllocationSize = AttributeDataLength(IndexAllocationCtx->pRecord); - Status = STATUS_OBJECT_PATH_NOT_FOUND; - for (RecordOffset = 0; RecordOffset < IndexAllocationSize; RecordOffset += IndexBlockSize) - { - ReadAttribute(Vcb, IndexAllocationCtx, RecordOffset, IndexRecord, IndexBlockSize); - Status = FixupUpdateSequenceArray(Vcb, &((PFILE_RECORD_HEADER)IndexRecord)->Ntfs); - if (!NT_SUCCESS(Status)) - { - break; - } - - IndexBuffer = (PINDEX_BUFFER)IndexRecord; - ASSERT(IndexBuffer->Ntfs.Type == NRH_INDX_TYPE); - ASSERT(IndexBuffer->Header.AllocatedSize + FIELD_OFFSET(INDEX_BUFFER, Header) == IndexBlockSize); - FirstEntry = (PINDEX_ENTRY_ATTRIBUTE)((ULONG_PTR)&IndexBuffer->Header + IndexBuffer->Header.FirstEntryOffset); - LastEntry = (PINDEX_ENTRY_ATTRIBUTE)((ULONG_PTR)&IndexBuffer->Header + IndexBuffer->Header.TotalSizeOfEntries); - ASSERT(LastEntry <= (PINDEX_ENTRY_ATTRIBUTE)((ULONG_PTR)IndexBuffer + IndexBlockSize)); - - Status = BrowseIndexEntries(NULL, - NULL, - NULL, - 0, - FirstEntry, - LastEntry, - FileName, - StartEntry, - CurrentEntry, - DirSearch, - CaseSensitive, - OutMFTIndex); - if (NT_SUCCESS(Status)) - { - break; - } + ExFreePoolWithTag(BitmapMem, TAG_NTFS); + ReleaseAttributeContext(BitmapContext); + ReleaseAttributeContext(IndexAllocationContext); } - ReleaseAttributeContext(IndexAllocationCtx); - return Status; + return STATUS_OBJECT_PATH_NOT_FOUND; } NTSTATUS @@ -2946,7 +3144,7 @@ NtfsFindMftRecord(PDEVICE_EXTENSION Vcb, Status = BrowseIndexEntries(Vcb, MftRecord, - IndexRecord, + (PINDEX_ROOT_ATTRIBUTE)IndexRecord, IndexRoot->SizeOfEntry, IndexEntry, IndexEntryEnd, @@ -3031,6 +3229,24 @@ NtfsLookupFile(PDEVICE_EXTENSION Vcb, return NtfsLookupFileAt(Vcb, PathName, CaseSensitive, FileRecord, MFTIndex, NTFS_FILE_ROOT); } +void +NtfsDumpData(ULONG_PTR Buffer, ULONG Length) +{ + ULONG i, j; + + // dump binary data, 8 bytes at a time + for (i = 0; i < Length; i += 8) + { + // display current offset, in hex + DbgPrint("\t%03x\t", i); + + // display hex value of each of the next 8 bytes + for (j = 0; j < 8; j++) + DbgPrint("%02x ", *(PUCHAR)(Buffer + i + j)); + DbgPrint("\n"); + } +} + /** * @name NtfsDumpFileRecord * @implemented diff --git a/drivers/filesystems/ntfs/ntfs.h b/drivers/filesystems/ntfs/ntfs.h index 5c709c61e9..97f4acd1d6 100644 --- a/drivers/filesystems/ntfs/ntfs.h +++ b/drivers/filesystems/ntfs/ntfs.h @@ -769,6 +769,9 @@ GetAllocationOffsetFromVCN(PDEVICE_EXTENSION DeviceExt, ULONG IndexBufferSize, ULONGLONG Vcn); +ULONGLONG +GetIndexEntryVCN(PINDEX_ENTRY_ATTRIBUTE IndexEntry); + ULONG GetSizeOfIndexEntries(PB_TREE_FILENAME_NODE Node); @@ -1002,6 +1005,9 @@ AddNewMftEntry(PFILE_RECORD_HEADER FileRecord, PULONGLONG DestinationIndex, BOOLEAN CanWait); +VOID +NtfsDumpData(ULONG_PTR Buffer, ULONG Length); + PNTFS_ATTR_CONTEXT PrepareAttributeContext(PNTFS_ATTR_RECORD AttrRecord);

6 years, 9 months

[reactos] 69/72: [NTFS] - Fix some errors that break building in C89 mode, and remove an extraneous "ninja livecd" that got inserted in a comment. Thanks to Doug Lyons for spotting these errors. SplitBTree() - comment-out redundant code for finding the median key and improve comments.

by Trevor Thompson

https://git.reactos.org/?p=reactos.git;a=commitdiff;h=a40ba448d401e53788db2… commit a40ba448d401e53788db2356108130e81b597a6f Author: Trevor Thompson <tmt256(a)email.vccs.edu> AuthorDate: Fri Sep 1 00:27:34 2017 +0000 [NTFS] - Fix some errors that break building in C89 mode, and remove an extraneous "ninja livecd" that got inserted in a comment. Thanks to Doug Lyons for spotting these errors. SplitBTree() - comment-out redundant code for finding the median key and improve comments. svn path=/branches/GSoC_2016/NTFS/; revision=75727 --- drivers/filesystems/ntfs/btree.c | 30 ++++++++++++++++++++++-------- drivers/filesystems/ntfs/mft.c | 10 ++++++---- 2 files changed, 28 insertions(+), 12 deletions(-) diff --git a/drivers/filesystems/ntfs/btree.c b/drivers/filesystems/ntfs/btree.c index bb745c5e9e..9fb1b29c0f 100644 --- a/drivers/filesystems/ntfs/btree.c +++ b/drivers/filesystems/ntfs/btree.c @@ -1139,7 +1139,7 @@ DemoteBTreeRoot(PB_TREE Tree) #ifndef NDEBUG DumpBTree(Tree); -#endif; +#endif return STATUS_SUCCESS; } @@ -1779,7 +1779,7 @@ NtfsInsertKey(PB_TREE Tree, #ifndef NDEBUG DumpBTree(Tree); -#endif NDEBUG +#endif } } else @@ -1880,6 +1880,9 @@ SplitBTreeNode(PB_TREE Tree, { ULONG MedianKeyIndex; PB_TREE_KEY LastKeyBeforeMedian, FirstKeyAfterMedian; + ULONG KeyCount; + ULONG HalfSize; + ULONG SizeSum; ULONG i; DPRINT1("SplitBTreeNode(%p, %p, %p, %p, %s) called\n", @@ -1889,7 +1892,9 @@ SplitBTreeNode(PB_TREE Tree, NewRightHandSibling, CaseSensitive ? "TRUE" : "FALSE"); - //DumpBTreeNode(Node, 0, 0); +#ifndef NDEBUG + DumpBTreeNode(Node, 0, 0); +#endif // Create the right hand sibling *NewRightHandSibling = ExAllocatePoolWithTag(NonPagedPool, sizeof(B_TREE_FILENAME_NODE), TAG_NTFS); @@ -1901,20 +1906,29 @@ SplitBTreeNode(PB_TREE Tree, RtlZeroMemory(*NewRightHandSibling, sizeof(B_TREE_FILENAME_NODE)); (*NewRightHandSibling)->DiskNeedsUpdating = TRUE; + + // Find the last key before the median + + // This is roughly how NTFS-3G calculates median, and it's not congruent with what Windows does: + /* // find the median key index MedianKeyIndex = (Node->KeyCount + 1) / 2; MedianKeyIndex--; - // Find the last key before the median LastKeyBeforeMedian = Node->FirstKey; for (i = 0; i < MedianKeyIndex - 1; i++) - LastKeyBeforeMedian = LastKeyBeforeMedian->NextKey; + LastKeyBeforeMedian = LastKeyBeforeMedian->NextKey;*/ + + // The method we'll use is a little bit closer to how Windows determines the median but it's not identical. + // What Windows does is actually more complicated than this, I think because Windows allocates more slack space to Odd-numbered + // Index Records, leaving less room for index entries in these records (I haven't discovered why this is done). + // (Neither Windows nor chkdsk complain if we choose a different median than Windows would have chosen, as our median will be in the ballpark) // Use size to locate the median key / index - ULONG HalfSize = 2016; // half the allocated size after subtracting the first index entry offset (TODO: MATH) - ULONG SizeSum = 0; LastKeyBeforeMedian = Node->FirstKey; MedianKeyIndex = 0; + HalfSize = 2016; // half the allocated size after subtracting the first index entry offset (TODO: MATH) + SizeSum = 0; for (i = 0; i < Node->KeyCount; i++) { SizeSum += LastKeyBeforeMedian->IndexEntry->Length; @@ -1989,7 +2003,7 @@ SplitBTreeNode(PB_TREE Tree, // Update Node's KeyCount (remember to add 1 for the new dummy key) Node->KeyCount = MedianKeyIndex + 2; - ULONG KeyCount = CountBTreeKeys(Node->FirstKey); + KeyCount = CountBTreeKeys(Node->FirstKey); ASSERT(Node->KeyCount == KeyCount); // everything to the right of MedianKey becomes the right hand sibling of Node diff --git a/drivers/filesystems/ntfs/mft.c b/drivers/filesystems/ntfs/mft.c index c4328a0491..9d96bad239 100644 --- a/drivers/filesystems/ntfs/mft.c +++ b/drivers/filesystems/ntfs/mft.c @@ -2138,6 +2138,9 @@ NtfsAddFilenameToDirectory(PDEVICE_EXTENSION DeviceExt, ULONG MaxIndexRootSize; PB_TREE_KEY NewLeftKey; PB_TREE_FILENAME_NODE NewRightHandNode; + LARGE_INTEGER MinIndexRootSize; + ULONG NewMaxIndexRootSize; + ULONG NodeSize; // Allocate memory for the parent directory ParentFileRecord = ExAllocatePoolWithTag(NonPagedPool, @@ -2287,7 +2290,6 @@ NtfsAddFilenameToDirectory(PDEVICE_EXTENSION DeviceExt, // This a bit hacky, but it seems to be functional. // Calculate the minimum size of the index root attribute, considering one dummy key and one VCN - LARGE_INTEGER MinIndexRootSize; MinIndexRootSize.QuadPart = sizeof(INDEX_ROOT_ATTRIBUTE) // size of the index root headers + 0x18; // Size of dummy key with a VCN for a subnode ASSERT(MinIndexRootSize.QuadPart % ATTR_RECORD_ALIGNMENT == 0); @@ -2335,7 +2337,7 @@ NtfsAddFilenameToDirectory(PDEVICE_EXTENSION DeviceExt, // Find the maximum index root size given what the file record can hold // First, find the max index size assuming index root is the last attribute - ULONG NewMaxIndexRootSize = + NewMaxIndexRootSize = DeviceExt->NtfsInfo.BytesPerFileRecord // Start with the size of a file record - IndexRootOffset // Subtract the length of everything that comes before index root - IndexRootContext->pRecord->Resident.ValueOffset // Subtract the length of the attribute header for index root @@ -2361,7 +2363,7 @@ NtfsAddFilenameToDirectory(PDEVICE_EXTENSION DeviceExt, // The index allocation and index bitmap may have grown, leaving less room for the index root, // so now we need to double-check that index root isn't too large - ULONG NodeSize = GetSizeOfIndexEntries(NewTree->RootNode); + NodeSize = GetSizeOfIndexEntries(NewTree->RootNode); if (NodeSize > NewMaxIndexRootSize) { DPRINT1("Demoting index root.\nNodeSize: 0x%lx\nNewMaxIndexRootSize: 0x%lx\n", NodeSize, NewMaxIndexRootSize); @@ -2624,7 +2626,7 @@ CompareFileName(PUNICODE_STRING FileName, * @param Vcb * Pointer to an NTFS_VCB for the volume whose Mft mirror is being updated. * -* @returninja livecd +* @return * STATUS_SUCCESS on success. * STATUS_INSUFFICIENT_RESOURCES if an allocation failed.

6 years, 9 months

[reactos] 68/72: [NTFS] - Add some helper functions for new features. Add some fixes. Add support for creating an index allocation, splitting a b-tree node, or "demoting" the index root. This allows for file creation without functional limitations. +AddBitmap() - adds a $BITMAP attribute to a file record. +AddIndexAllocation() - adds an $INDEX_ALLOCATION attribute to a file record. +CountBTreeKeys() - Counts the number of linked B-Tree keys. CreateIndexBufferFromBTreeNode() - Set INDEX_NODE_LARG

by Trevor Thompson

https://git.reactos.org/?p=reactos.git;a=commitdiff;h=52c30fdf37d3fd9a1583d… commit 52c30fdf37d3fd9a1583d4052f6b11365099613c Author: Trevor Thompson <tmt256(a)email.vccs.edu> AuthorDate: Tue Aug 29 15:51:14 2017 +0000 [NTFS] - Add some helper functions for new features. Add some fixes. Add support for creating an index allocation, splitting a b-tree node, or "demoting" the index root. This allows for file creation without functional limitations. +AddBitmap() - adds a $BITMAP attribute to a file record. +AddIndexAllocation() - adds an $INDEX_ALLOCATION attribute to a file record. +CountBTreeKeys() - Counts the number of linked B-Tree keys. CreateIndexBufferFromBTreeNode() - Set INDEX_NODE_LARGE if the node has sub-nodes. CreateIndexRootFromBTree() - Simplify the usage and math of MaxIndexSize; make it only account for the cumulative size of the index entries. +DemoteBTreeRoot() - Replaces the contents of an index root with a dummy key, and puts those contents in a new node, which is made a child of the dummy key. This is done when an index root grows too large. +GetIndexEntryVCN() - Retrieves the VCN from an index entry. NtfsAddFilenameToDirectory() - Fix math for MaxIndexRootSize. NtfsInsertKey() - Add support for splitting a B-Tree node. Don't check size of index root (that will be handled later). +SplitBTreeNode() - Called when a B-Tree node grows too large. UpdateIndexAllocation() - Create an $I30 index allocation attribute and bitmap attribute if needed. UpdateIndexNode() - Update children before updating the current node. Store VCN of child nodes in the index entries of their respective keys. svn path=/branches/GSoC_2016/NTFS/; revision=75707 --- drivers/filesystems/ntfs/attrib.c | 193 ++++++++++++ drivers/filesystems/ntfs/btree.c | 597 ++++++++++++++++++++++++++++++-------- drivers/filesystems/ntfs/mft.c | 186 +++++++++++- drivers/filesystems/ntfs/ntfs.h | 35 ++- 4 files changed, 886 insertions(+), 125 deletions(-) diff --git a/drivers/filesystems/ntfs/attrib.c b/drivers/filesystems/ntfs/attrib.c index 34bee2a060..846c16da80 100644 --- a/drivers/filesystems/ntfs/attrib.c +++ b/drivers/filesystems/ntfs/attrib.c @@ -36,6 +36,100 @@ /* FUNCTIONS ****************************************************************/ +/** +* @name AddBitmap +* @implemented +* +* Adds a $BITMAP attribute to a given FileRecord. +* +* @param Vcb +* Pointer to an NTFS_VCB for the destination volume. +* +* @param FileRecord +* Pointer to a complete file record to add the attribute to. +* +* @param AttributeAddress +* Pointer to the region of memory that will receive the $INDEX_ALLOCATION attribute. +* This address must reside within FileRecord. Must be aligned to an 8-byte boundary (relative to FileRecord). +* +* @param Name +* Pointer to a string of 16-bit Unicode characters naming the attribute. Most often L"$I30". +* +* @param NameLength +* The number of wide-characters in the name. L"$I30" Would use 4 here. +* +* @return +* STATUS_SUCCESS on success. STATUS_NOT_IMPLEMENTED if target address isn't at the end +* of the given file record, or if the file record isn't large enough for the attribute. +* +* @remarks +* Only adding the attribute to the end of the file record is supported; AttributeAddress must +* be of type AttributeEnd. +* This could be improved by adding an $ATTRIBUTE_LIST to the file record if there's not enough space. +* +*/ +NTSTATUS +AddBitmap(PNTFS_VCB Vcb, + PFILE_RECORD_HEADER FileRecord, + PNTFS_ATTR_RECORD AttributeAddress, + PCWSTR Name, + USHORT NameLength) +{ + ULONG AttributeLength; + // Calculate the header length + ULONG ResidentHeaderLength = FIELD_OFFSET(NTFS_ATTR_RECORD, Resident.Reserved) + sizeof(UCHAR); + ULONG FileRecordEnd = AttributeAddress->Length; + ULONG NameOffset; + ULONG ValueOffset; + // We'll start out with 8 bytes of bitmap data + ULONG ValueLength = 8; + ULONG BytesAvailable; + + if (AttributeAddress->Type != AttributeEnd) + { + DPRINT1("FIXME: Can only add $BITMAP attribute to the end of a file record.\n"); + return STATUS_NOT_IMPLEMENTED; + } + + NameOffset = ResidentHeaderLength; + + // Calculate ValueOffset, which will be aligned to a 4-byte boundary + ValueOffset = ALIGN_UP_BY(NameOffset + (sizeof(WCHAR) * NameLength), VALUE_OFFSET_ALIGNMENT); + + // Calculate length of attribute + AttributeLength = ValueOffset + ValueLength; + AttributeLength = ALIGN_UP_BY(AttributeLength, ATTR_RECORD_ALIGNMENT); + + // Make sure the file record is large enough for the new attribute + BytesAvailable = Vcb->NtfsInfo.BytesPerFileRecord - FileRecord->BytesInUse; + if (BytesAvailable < AttributeLength) + { + DPRINT1("FIXME: Not enough room in file record for index allocation attribute!\n"); + return STATUS_NOT_IMPLEMENTED; + } + + // Set Attribute fields + RtlZeroMemory(AttributeAddress, AttributeLength); + + AttributeAddress->Type = AttributeBitmap; + AttributeAddress->Length = AttributeLength; + AttributeAddress->NameLength = NameLength; + AttributeAddress->NameOffset = NameOffset; + AttributeAddress->Instance = FileRecord->NextAttributeNumber++; + + AttributeAddress->Resident.ValueLength = ValueLength; + AttributeAddress->Resident.ValueOffset = ValueOffset; + + // Set the name + RtlCopyMemory((PCHAR)((ULONG_PTR)AttributeAddress + NameOffset), Name, NameLength * sizeof(WCHAR)); + + // move the attribute-end and file-record-end markers to the end of the file record + AttributeAddress = (PNTFS_ATTR_RECORD)((ULONG_PTR)AttributeAddress + AttributeAddress->Length); + SetFileRecordEnd(FileRecord, AttributeAddress, FileRecordEnd); + + return STATUS_SUCCESS; +} + /** * @name AddData * @implemented @@ -258,6 +352,105 @@ AddFileName(PFILE_RECORD_HEADER FileRecord, return Status; } +/** +* @name AddIndexAllocation +* @implemented +* +* Adds an $INDEX_ALLOCATION attribute to a given FileRecord. +* +* @param Vcb +* Pointer to an NTFS_VCB for the destination volume. +* +* @param FileRecord +* Pointer to a complete file record to add the attribute to. +* +* @param AttributeAddress +* Pointer to the region of memory that will receive the $INDEX_ALLOCATION attribute. +* This address must reside within FileRecord. Must be aligned to an 8-byte boundary (relative to FileRecord). +* +* @param Name +* Pointer to a string of 16-bit Unicode characters naming the attribute. Most often, this will be L"$I30". +* +* @param NameLength +* The number of wide-characters in the name. L"$I30" Would use 4 here. +* +* @return +* STATUS_SUCCESS on success. STATUS_NOT_IMPLEMENTED if target address isn't at the end +* of the given file record, or if the file record isn't large enough for the attribute. +* +* @remarks +* Only adding the attribute to the end of the file record is supported; AttributeAddress must +* be of type AttributeEnd. +* This could be improved by adding an $ATTRIBUTE_LIST to the file record if there's not enough space. +* +*/ +NTSTATUS +AddIndexAllocation(PNTFS_VCB Vcb, + PFILE_RECORD_HEADER FileRecord, + PNTFS_ATTR_RECORD AttributeAddress, + PCWSTR Name, + USHORT NameLength) +{ + ULONG RecordLength; + ULONG FileRecordEnd; + ULONG NameOffset; + ULONG DataRunOffset; + ULONG BytesAvailable; + + if (AttributeAddress->Type != AttributeEnd) + { + DPRINT1("FIXME: Can only add $INDEX_ALLOCATION attribute to the end of a file record.\n"); + return STATUS_NOT_IMPLEMENTED; + } + + // Calculate the name offset + NameOffset = FIELD_OFFSET(NTFS_ATTR_RECORD, NonResident.CompressedSize); + + // Calculate the offset to the first data run + DataRunOffset = (sizeof(WCHAR) * NameLength) + NameOffset; + // The data run offset must be aligned to a 4-byte boundary + DataRunOffset = ALIGN_UP_BY(DataRunOffset, DATA_RUN_ALIGNMENT); + + // Calculate the length of the new attribute; the empty data run will consist of a single byte + RecordLength = DataRunOffset + 1; + + // The size of the attribute itself must be aligned to an 8 - byte boundary + RecordLength = ALIGN_UP_BY(RecordLength, ATTR_RECORD_ALIGNMENT); + + // Back up the last 4-bytes of the file record (even though this value doesn't matter) + FileRecordEnd = AttributeAddress->Length; + + // Make sure the file record can contain the new attribute + BytesAvailable = Vcb->NtfsInfo.BytesPerFileRecord - FileRecord->BytesInUse; + if (BytesAvailable < RecordLength) + { + DPRINT1("FIXME: Not enough room in file record for index allocation attribute!\n"); + return STATUS_NOT_IMPLEMENTED; + } + + // Set fields of attribute header + RtlZeroMemory(AttributeAddress, RecordLength); + + AttributeAddress->Type = AttributeIndexAllocation; + AttributeAddress->Length = RecordLength; + AttributeAddress->IsNonResident = TRUE; + AttributeAddress->NameLength = NameLength; + AttributeAddress->NameOffset = NameOffset; + AttributeAddress->Instance = FileRecord->NextAttributeNumber++; + + AttributeAddress->NonResident.MappingPairsOffset = DataRunOffset; + AttributeAddress->NonResident.HighestVCN = (LONGLONG)-1; + + // Set the name + RtlCopyMemory((PCHAR)((ULONG_PTR)AttributeAddress + NameOffset), Name, NameLength * sizeof(WCHAR)); + + // move the attribute-end and file-record-end markers to the end of the file record + AttributeAddress = (PNTFS_ATTR_RECORD)((ULONG_PTR)AttributeAddress + AttributeAddress->Length); + SetFileRecordEnd(FileRecord, AttributeAddress, FileRecordEnd); + + return STATUS_SUCCESS; +} + /** * @name AddIndexRoot * @implemented diff --git a/drivers/filesystems/ntfs/btree.c b/drivers/filesystems/ntfs/btree.c index cd9cf35069..bb745c5e9e 100644 --- a/drivers/filesystems/ntfs/btree.c +++ b/drivers/filesystems/ntfs/btree.c @@ -468,6 +468,33 @@ CompareTreeKeys(PB_TREE_KEY Key1, PB_TREE_KEY Key2, BOOLEAN CaseSensitive) return Comparison; } +/** +* @name CountBTreeKeys +* @implemented +* +* Counts the number of linked B-Tree keys, starting with FirstKey. +* +* @param FirstKey +* Pointer to a B_TREE_KEY that will be the first key to be counted. +* +* @return +* The number of keys in a linked-list, including FirstKey and the final dummy key. +*/ +ULONG +CountBTreeKeys(PB_TREE_KEY FirstKey) +{ + ULONG Count = 0; + PB_TREE_KEY Current = FirstKey; + + while (Current != NULL) + { + Count++; + Current = Current->NextKey; + } + + return Count; +} + PB_TREE_FILENAME_NODE CreateBTreeNodeFromIndexNode(PDEVICE_EXTENSION Vcb, PINDEX_ROOT_ATTRIBUTE IndexRoot, @@ -852,6 +879,9 @@ GetSizeOfIndexEntries(PB_TREE_FILENAME_NODE Node) * * @param MaxIndexSize * Describes how large the index can be before it will take too much space in the file record. +* This is strictly the sum of the sizes of all index entries; it does not include the space +* required by the index root header (INDEX_ROOT_ATTRIBUTE), since that size will be constant. +* * After reaching MaxIndexSize, an index can no longer be represented with just an index root * attribute, and will require an index allocation and $I30 bitmap (TODO). * @@ -885,6 +915,10 @@ CreateIndexRootFromBTree(PDEVICE_EXTENSION DeviceExt, DPRINT1("CreateIndexRootFromBTree(%p, %p, 0x%lx, %p, %p)\n", DeviceExt, Tree, MaxIndexSize, IndexRoot, Length); +#ifndef NDEBUG + DumpBTree(Tree); +#endif + if (!NewIndexRoot) { DPRINT1("Failed to allocate memory for Index Root!\n"); @@ -918,12 +952,10 @@ CreateIndexRootFromBTree(PDEVICE_EXTENSION DeviceExt, for (i = 0; i < Tree->RootNode->KeyCount; i++) { // Would adding the current entry to the index increase the index size beyond the limit we've set? - ULONG IndexSize = FIELD_OFFSET(INDEX_ROOT_ATTRIBUTE, Header) - + NewIndexRoot->Header.TotalSizeOfEntries - + CurrentNodeEntry->Length; + ULONG IndexSize = NewIndexRoot->Header.TotalSizeOfEntries - NewIndexRoot->Header.FirstEntryOffset + CurrentKey->IndexEntry->Length; if (IndexSize > MaxIndexSize) { - DPRINT1("TODO: Adding file would require creating an index allocation!\n"); + DPRINT1("TODO: Adding file would require creating an attribute list!\n"); ExFreePoolWithTag(NewIndexRoot, TAG_NTFS); return STATUS_NOT_IMPLEMENTED; } @@ -962,6 +994,7 @@ NTSTATUS CreateIndexBufferFromBTreeNode(PDEVICE_EXTENSION DeviceExt, PB_TREE_FILENAME_NODE Node, ULONG BufferSize, + BOOLEAN HasChildren, PINDEX_BUFFER IndexBuffer) { ULONG i; @@ -1014,7 +1047,9 @@ CreateIndexBufferFromBTreeNode(PDEVICE_EXTENSION DeviceExt, // Add Length of Current Entry to Total Size of Entries IndexBuffer->Header.TotalSizeOfEntries += CurrentNodeEntry->Length; - // TODO: Check for child nodes + // Check for child nodes + if (HasChildren) + IndexBuffer->Header.Flags = INDEX_NODE_LARGE; // Go to the next node entry CurrentNodeEntry = (PINDEX_ENTRY_ATTRIBUTE)((ULONG_PTR)CurrentNodeEntry + CurrentNodeEntry->Length); @@ -1026,6 +1061,89 @@ CreateIndexBufferFromBTreeNode(PDEVICE_EXTENSION DeviceExt, return Status; } +/** +* @name DemoteBTreeRoot +* @implemented +* +* Demoting the root means first putting all the keys in the root node into a new node, and making +* the new node a child of a dummy key. The dummy key then becomes the sole contents of the root node. +* The B-Tree gets one level deeper. This operation is needed when an index root grows too large for its file record. +* Demotion is my own term; I might change the name later if I think of something more descriptive or can find +* an appropriate name for this operation in existing B-Tree literature. +* +* @param Tree +* Pointer to the B_TREE whose root is being demoted +* +* @returns +* STATUS_SUCCESS on success. +* STATUS_INSUFFICIENT_RESOURCES if an allocation fails. +*/ +NTSTATUS +DemoteBTreeRoot(PB_TREE Tree) +{ + PB_TREE_FILENAME_NODE NewSubNode, NewIndexRoot; + PB_TREE_KEY DummyKey; + + DPRINT1("Collapsing Index Root into sub-node.\n"); + +#ifndef NDEBUG + DumpBTree(Tree); +#endif + + // Create a new node that will hold the keys currently in index root + NewSubNode = ExAllocatePoolWithTag(NonPagedPool, sizeof(B_TREE_FILENAME_NODE), TAG_NTFS); + if (!NewSubNode) + { + DPRINT1("ERROR: Couldn't allocate memory for new sub-node.\n"); + return STATUS_INSUFFICIENT_RESOURCES; + } + RtlZeroMemory(NewSubNode, sizeof(B_TREE_FILENAME_NODE)); + + // Copy the applicable data from the old index root node + NewSubNode->KeyCount = Tree->RootNode->KeyCount; + NewSubNode->FirstKey = Tree->RootNode->FirstKey; + NewSubNode->DiskNeedsUpdating = TRUE; + + // Create a new dummy key, and make the new node it's child + DummyKey = CreateDummyKey(TRUE); + if (!DummyKey) + { + DPRINT1("ERROR: Couldn't allocate memory for new root node.\n"); + ExFreePoolWithTag(NewSubNode, TAG_NTFS); + return STATUS_INSUFFICIENT_RESOURCES; + } + + // Make the new node a child of the dummy key + DummyKey->LesserChild = NewSubNode; + + // Create a new index root node + NewIndexRoot = ExAllocatePoolWithTag(NonPagedPool, sizeof(B_TREE_FILENAME_NODE), TAG_NTFS); + if (!NewIndexRoot) + { + DPRINT1("ERROR: Couldn't allocate memory for new index root.\n"); + ExFreePoolWithTag(NewSubNode, TAG_NTFS); + ExFreePoolWithTag(DummyKey, TAG_NTFS); + return STATUS_INSUFFICIENT_RESOURCES; + } + RtlZeroMemory(NewIndexRoot, sizeof(B_TREE_FILENAME_NODE)); + + NewIndexRoot->DiskNeedsUpdating = TRUE; + + // Insert the dummy key into the new node + NewIndexRoot->FirstKey = DummyKey; + NewIndexRoot->KeyCount = 1; + NewIndexRoot->DiskNeedsUpdating = TRUE; + + // Make the new node the Tree's root node + Tree->RootNode = NewIndexRoot; + +#ifndef NDEBUG + DumpBTree(Tree); +#endif; + + return STATUS_SUCCESS; +} + /** * @name SetIndexEntryVCN * @implemented @@ -1060,7 +1178,7 @@ UpdateIndexAllocation(PDEVICE_EXTENSION DeviceExt, PFILE_RECORD_HEADER FileRecord) { // Find the index allocation and bitmap - PNTFS_ATTR_CONTEXT IndexAllocationContext, BitmapContext; + PNTFS_ATTR_CONTEXT IndexAllocationContext; PB_TREE_KEY CurrentKey; NTSTATUS Status; BOOLEAN HasIndexAllocation = FALSE; @@ -1074,14 +1192,12 @@ UpdateIndexAllocation(PDEVICE_EXTENSION DeviceExt, { HasIndexAllocation = TRUE; +#ifndef NDEBUG PrintAllVCNs(DeviceExt, IndexAllocationContext, IndexBufferSize); +#endif } - - // TODO: Handle bitmap - BitmapContext = NULL; - // Walk through the root node and update all the sub-nodes CurrentKey = Tree->RootNode->FirstKey; for (i = 0; i < Tree->RootNode->KeyCount; i++) @@ -1090,8 +1206,46 @@ UpdateIndexAllocation(PDEVICE_EXTENSION DeviceExt, { if (!HasIndexAllocation) { - DPRINT1("FIXME: Need to add index allocation\n"); - return STATUS_NOT_IMPLEMENTED; + // We need to add an index allocation to the file record + PNTFS_ATTR_RECORD EndMarker = (PNTFS_ATTR_RECORD)((ULONG_PTR)FileRecord + FileRecord->BytesInUse - (sizeof(ULONG) * 2)); + DPRINT1("Adding index allocation...\n"); + + // Add index allocation to the very end of the file record + Status = AddIndexAllocation(DeviceExt, + FileRecord, + EndMarker, + L"$I30", + 4); + if (!NT_SUCCESS(Status)) + { + DPRINT1("ERROR: Failed to add index allocation!\n"); + return Status; + } + + // Find the new attribute + Status = FindAttribute(DeviceExt, FileRecord, AttributeIndexAllocation, L"$I30", 4, &IndexAllocationContext, &IndexAllocationOffset); + if (!NT_SUCCESS(Status)) + { + DPRINT1("ERROR: Couldn't find newly-created index allocation!\n"); + return Status; + } + + // Advance end marker + EndMarker = (PNTFS_ATTR_RECORD)((ULONG_PTR)EndMarker + EndMarker->Length); + + // Add index bitmap to the very end of the file record + Status = AddBitmap(DeviceExt, + FileRecord, + EndMarker, + L"$I30", + 4); + if (!NT_SUCCESS(Status)) + { + DPRINT1("ERROR: Failed to add index bitmap!\n"); + return Status; + } + + HasIndexAllocation = TRUE; } // Is the Index Entry large enough to store the VCN? @@ -1122,7 +1276,7 @@ UpdateIndexAllocation(PDEVICE_EXTENSION DeviceExt, } // Update the sub-node - Status = UpdateIndexNode(DeviceExt, FileRecord, CurrentKey->LesserChild, IndexBufferSize, IndexAllocationContext, IndexAllocationOffset, BitmapContext); + Status = UpdateIndexNode(DeviceExt, FileRecord, CurrentKey->LesserChild, IndexBufferSize, IndexAllocationContext, IndexAllocationOffset); if (!NT_SUCCESS(Status)) { DPRINT1("ERROR: Failed to update index node!\n"); @@ -1136,12 +1290,17 @@ UpdateIndexAllocation(PDEVICE_EXTENSION DeviceExt, CurrentKey = CurrentKey->NextKey; } +#ifndef NDEBUG + DumpBTree(Tree); +#endif + if (HasIndexAllocation) { +#ifndef NDEBUG PrintAllVCNs(DeviceExt, IndexAllocationContext, IndexBufferSize); - +#endif ReleaseAttributeContext(IndexAllocationContext); } @@ -1154,22 +1313,74 @@ UpdateIndexNode(PDEVICE_EXTENSION DeviceExt, PB_TREE_FILENAME_NODE Node, ULONG IndexBufferSize, PNTFS_ATTR_CONTEXT IndexAllocationContext, - ULONG IndexAllocationOffset, - PNTFS_ATTR_CONTEXT BitmapContext) + ULONG IndexAllocationOffset) { ULONG i; PB_TREE_KEY CurrentKey = Node->FirstKey; + BOOLEAN HasChildren = FALSE; NTSTATUS Status; - DPRINT1("UpdateIndexNode(%p, %p, %p, %lu, %p, %lu, %p) called for index node with VCN %I64u\n", - DeviceExt, - FileRecord, - Node, - IndexBufferSize, - IndexAllocationContext, - IndexAllocationOffset, - BitmapContext, - Node->VCN); + + DPRINT("UpdateIndexNode(%p, %p, %p, %lu, %p, %lu) called for index node with VCN %I64u\n", + DeviceExt, + FileRecord, + Node, + IndexBufferSize, + IndexAllocationContext, + IndexAllocationOffset, + Node->VCN); + + // Walk through the node and look for children to update + for (i = 0; i < Node->KeyCount; i++) + { + ASSERT(CurrentKey); + + // If there's a child node + if (CurrentKey->LesserChild) + { + HasChildren = TRUE; + + // Update the child node on disk + Status = UpdateIndexNode(DeviceExt, FileRecord, CurrentKey->LesserChild, IndexBufferSize, IndexAllocationContext, IndexAllocationOffset); + if (!NT_SUCCESS(Status)) + { + DPRINT1("ERROR: Failed to update child node!\n"); + return Status; + } + + // Is the Index Entry large enough to store the VCN? + if (!CurrentKey->IndexEntry->Flags & NTFS_INDEX_ENTRY_NODE) + { + // Allocate memory for the larger index entry + PINDEX_ENTRY_ATTRIBUTE NewEntry = ExAllocatePoolWithTag(NonPagedPool, + CurrentKey->IndexEntry->Length + sizeof(ULONGLONG), + TAG_NTFS); + if (!NewEntry) + { + DPRINT1("ERROR: Unable to allocate memory for new index entry!\n"); + return STATUS_INSUFFICIENT_RESOURCES; + } + + // Copy the old entry to the new one + RtlCopyMemory(NewEntry, CurrentKey->IndexEntry, CurrentKey->IndexEntry->Length); + + NewEntry->Length += sizeof(ULONGLONG); + + // Free the old memory + ExFreePoolWithTag(CurrentKey->IndexEntry, TAG_NTFS); + + CurrentKey->IndexEntry = NewEntry; + } + + // Update the VCN stored in the index entry of CurrentKey + SetIndexEntryVCN(CurrentKey->IndexEntry, CurrentKey->LesserChild->VCN); + + CurrentKey->IndexEntry->Flags |= NTFS_INDEX_ENTRY_NODE; + } + + CurrentKey = CurrentKey->NextKey; + } + // Do we need to write this node to disk? if (Node->DiskNeedsUpdating) @@ -1206,7 +1417,7 @@ UpdateIndexNode(PDEVICE_EXTENSION DeviceExt, } // Create the index buffer we'll be writing to disk to represent this node - Status = CreateIndexBufferFromBTreeNode(DeviceExt, Node, IndexBufferSize, IndexBuffer); + Status = CreateIndexBufferFromBTreeNode(DeviceExt, Node, IndexBufferSize, HasChildren, IndexBuffer); if (!NT_SUCCESS(Status)) { DPRINT1("ERROR: Failed to create index buffer from node!\n"); @@ -1235,26 +1446,6 @@ UpdateIndexNode(PDEVICE_EXTENSION DeviceExt, ExFreePoolWithTag(IndexBuffer, TAG_NTFS); } - // Walk through the node and look for children to update - for (i = 0; i < Node->KeyCount; i++) - { - ASSERT(CurrentKey); - - // If there's a child node - if (CurrentKey->LesserChild) - { - // Update the child node on disk - Status = UpdateIndexNode(DeviceExt, FileRecord, CurrentKey->LesserChild, IndexBufferSize, IndexAllocationContext, IndexAllocationOffset, BitmapContext); - if (!NT_SUCCESS(Status)) - { - DPRINT1("ERROR: Failed to update child node!\n"); - return Status; - } - } - - CurrentKey = CurrentKey->NextKey; - } - return STATUS_SUCCESS; } @@ -1438,6 +1629,16 @@ GetAllocationOffsetFromVCN(PDEVICE_EXTENSION DeviceExt, return Vcn * DeviceExt->NtfsInfo.BytesPerCluster; } +ULONGLONG +GetIndexEntryVCN(PINDEX_ENTRY_ATTRIBUTE IndexEntry) +{ + PULONGLONG Destination = (PULONGLONG)((ULONG_PTR)IndexEntry + IndexEntry->Length - sizeof(ULONGLONG)); + + ASSERT(IndexEntry->Flags & NTFS_INDEX_ENTRY_NODE); + + return *Destination; +} + /** * @name NtfsInsertKey * @implemented @@ -1464,6 +1665,17 @@ GetAllocationOffsetFromVCN(PDEVICE_EXTENSION DeviceExt, * The maximum size, in bytes, of node entries that can be stored in the index root before it will grow too large for * the file record. This number is just the size of the entries, without any headers for the attribute or index root. * +* @param IndexRecordSize +* The size, in bytes, of an index record for this index. AKA an index buffer. Usually set to 4096. +* +* @param MedianKey +* Pointer to a PB_TREE_KEY that will receive a pointer to the median key, should the node grow too large and need to be split. +* Will be set to NULL if the node isn't split. +* +* @param NewRightHandSibling +* Pointer to a PB_TREE_FILENAME_NODE that will receive a pointer to a newly-created right-hand sibling node, +* should the node grow too large and need to be split. Will be set to NULL if the node isn't split. +* * @remarks * A node is always sorted, with the least comparable filename stored first and a dummy key to mark the end. */ @@ -1473,7 +1685,10 @@ NtfsInsertKey(PB_TREE Tree, PFILENAME_ATTRIBUTE FileNameAttribute, PB_TREE_FILENAME_NODE Node, BOOLEAN CaseSensitive, - ULONG MaxIndexRootSize) + ULONG MaxIndexRootSize, + ULONG IndexRecordSize, + PB_TREE_KEY *MedianKey, + PB_TREE_FILENAME_NODE *NewRightHandSibling) { PB_TREE_KEY NewKey, CurrentKey, PreviousKey; NTSTATUS Status = STATUS_SUCCESS; @@ -1482,13 +1697,19 @@ NtfsInsertKey(PB_TREE Tree, ULONG MaxNodeSizeWithoutHeader; ULONG i; - DPRINT1("NtfsInsertKey(%p, 0x%I64x, %p, %p, %s, %lu)\n", + *MedianKey = NULL; + *NewRightHandSibling = NULL; + + DPRINT1("NtfsInsertKey(%p, 0x%I64x, %p, %p, %s, %lu, %lu, %p, %p)\n", Tree, FileReference, FileNameAttribute, Node, CaseSensitive ? "TRUE" : "FALSE", - MaxIndexRootSize); + MaxIndexRootSize, + IndexRecordSize, + MedianKey, + NewRightHandSibling); // Create the key for the filename attribute NewKey = CreateBTreeKeyFromFilename(FileReference, FileNameAttribute); @@ -1513,12 +1734,22 @@ NtfsInsertKey(PB_TREE Tree, // Is NewKey < CurrentKey? if (Comparison < 0) { - // Does CurrentKey have a sub-node? if (CurrentKey->LesserChild) { + PB_TREE_KEY NewLeftKey; + PB_TREE_FILENAME_NODE NewChild; + // Insert the key into the child node - Status = NtfsInsertKey(Tree, FileReference, FileNameAttribute, CurrentKey->LesserChild, CaseSensitive, 0); + Status = NtfsInsertKey(Tree, + FileReference, + FileNameAttribute, + CurrentKey->LesserChild, + CaseSensitive, + MaxIndexRootSize, + IndexRecordSize, + &NewLeftKey, + &NewChild); if (!NT_SUCCESS(Status)) { DPRINT1("ERROR: Failed to insert key.\n"); @@ -1526,6 +1757,30 @@ NtfsInsertKey(PB_TREE Tree, return Status; } + // Did the child node get split? + if (NewLeftKey) + { + ASSERT(NewChild != NULL); + + // Insert the new left key to the left of the current key + NewLeftKey->NextKey = CurrentKey; + + // Is CurrentKey the first key? + if (!PreviousKey) + Node->FirstKey = NewLeftKey; + else + PreviousKey->NextKey = NewLeftKey; + + // CurrentKey->LesserChild will be the right-hand sibling + CurrentKey->LesserChild = NewChild; + + Node->KeyCount++; + Node->DiskNeedsUpdating = TRUE; + +#ifndef NDEBUG + DumpBTree(Tree); +#endif NDEBUG + } } else { @@ -1541,8 +1796,8 @@ NtfsInsertKey(PB_TREE Tree, Node->FirstKey = NewKey; else PreviousKey->NextKey = NewKey; - break; } + break; } PreviousKey = CurrentKey; @@ -1552,88 +1807,202 @@ NtfsInsertKey(PB_TREE Tree, // Determine how much space the index entries will need NodeSize = GetSizeOfIndexEntries(Node); - // Is Node the root node? - if (Node == Tree->RootNode) + // Is Node not the root node? + if (Node != Tree->RootNode) { - // Is the index root too large for the file record? - if (NodeSize > MaxIndexRootSize) - { - PB_TREE_FILENAME_NODE NewSubNode, NewIndexRoot; - PB_TREE_KEY DummyKey; + // Calculate maximum size of index entries without any headers + AllocatedNodeSize = IndexRecordSize - FIELD_OFFSET(INDEX_BUFFER, Header); - DPRINT1("Collapsing Index Root into sub-node.\n") ; + // TODO: Replace magic with math + MaxNodeSizeWithoutHeader = AllocatedNodeSize - 0x28; + + // Has the node grown larger than its allocated size? + if (NodeSize > MaxNodeSizeWithoutHeader) + { + NTSTATUS Status; - DumpBTree(Tree); - - // Create a new node that will hold the keys currently in index root - NewSubNode = ExAllocatePoolWithTag(NonPagedPool, sizeof(B_TREE_FILENAME_NODE), TAG_NTFS); - if (!NewSubNode) + Status = SplitBTreeNode(Tree, Node, MedianKey, NewRightHandSibling, CaseSensitive); + if (!NT_SUCCESS(Status)) { - DPRINT1("ERROR: Couldn't allocate memory for new sub-node.\n"); - return STATUS_INSUFFICIENT_RESOURCES; + DPRINT1("ERROR: Failed to split B-Tree node!\n"); + return Status; } - RtlZeroMemory(NewSubNode, sizeof(B_TREE_FILENAME_NODE)); - // Copy the applicable data from the old index root node - NewSubNode->KeyCount = Node->KeyCount; - NewSubNode->FirstKey = Node->FirstKey; - NewSubNode->DiskNeedsUpdating = TRUE; + return Status; + } + } - // Create a new dummy key, and make the new node it's child - DummyKey = CreateDummyKey(TRUE); - if (!DummyKey) - { - DPRINT1("ERROR: Couldn't allocate memory for new root node.\n"); - ExFreePoolWithTag(NewSubNode, TAG_NTFS); - return STATUS_INSUFFICIENT_RESOURCES; - } + // NewEntry and NewKey will be destroyed later by DestroyBTree() - // Make the new node a child of the dummy key - DummyKey->LesserChild = NewSubNode; + return Status; +} - // Create a new index root node - NewIndexRoot = ExAllocatePoolWithTag(NonPagedPool, sizeof(B_TREE_FILENAME_NODE), TAG_NTFS); - if (!NewIndexRoot) - { - DPRINT1("ERROR: Couldn't allocate memory for new index root.\n"); - ExFreePoolWithTag(NewSubNode, TAG_NTFS); - ExFreePoolWithTag(DummyKey, TAG_NTFS); - return STATUS_INSUFFICIENT_RESOURCES; - } - RtlZeroMemory(NewIndexRoot, sizeof(B_TREE_FILENAME_NODE)); - NewIndexRoot->DiskNeedsUpdating = TRUE; - // Insert the dummy key into the new node - NewIndexRoot->FirstKey = DummyKey; - NewIndexRoot->KeyCount = 1; - NewIndexRoot->DiskNeedsUpdating = TRUE; +/** +* @name SplitBTreeNode +* @implemented +* +* Splits a B-Tree node that has grown too large. Finds the median key and sets up a right-hand-sibling +* node to contain the keys to the right of the median key. +* +* @param Tree +* Pointer to the B_TREE which contains the node being split +* +* @param Node +* Pointer to the B_TREE_FILENAME_NODE that needs to be split +* +* @param MedianKey +* Pointer a PB_TREE_KEY that will receive the pointer to the key in the middle of the node being split +* +* @param NewRightHandSibling +* Pointer to a PB_TREE_FILENAME_NODE that will receive a pointer to a newly-created B_TREE_FILENAME_NODE +* containing the keys to the right of MedianKey. +* +* @param CaseSensitive +* Boolean indicating if the function should operate in case-sensitive mode. This will be TRUE +* if an application created the file with the FILE_FLAG_POSIX_SEMANTICS flag. +* +* @return +* STATUS_SUCCESS on success. +* STATUS_INSUFFICIENT_RESOURCES if an allocation fails. +* +* @remarks +* It's the responsibility of the caller to insert the new median key into the parent node, as well as making the +* NewRightHandSibling the lesser child of the node that is currently Node's parent. +*/ +NTSTATUS +SplitBTreeNode(PB_TREE Tree, + PB_TREE_FILENAME_NODE Node, + PB_TREE_KEY *MedianKey, + PB_TREE_FILENAME_NODE *NewRightHandSibling, + BOOLEAN CaseSensitive) +{ + ULONG MedianKeyIndex; + PB_TREE_KEY LastKeyBeforeMedian, FirstKeyAfterMedian; + ULONG i; - // Make the new node the Tree's root node - Tree->RootNode = NewIndexRoot; + DPRINT1("SplitBTreeNode(%p, %p, %p, %p, %s) called\n", + Tree, + Node, + MedianKey, + NewRightHandSibling, + CaseSensitive ? "TRUE" : "FALSE"); - DumpBTree(Tree); + //DumpBTreeNode(Node, 0, 0); - return STATUS_SUCCESS; - } + // Create the right hand sibling + *NewRightHandSibling = ExAllocatePoolWithTag(NonPagedPool, sizeof(B_TREE_FILENAME_NODE), TAG_NTFS); + if (*NewRightHandSibling == NULL) + { + DPRINT1("Error: Failed to allocate memory for right hand sibling!\n"); + return STATUS_INSUFFICIENT_RESOURCES; + } + RtlZeroMemory(*NewRightHandSibling, sizeof(B_TREE_FILENAME_NODE)); + (*NewRightHandSibling)->DiskNeedsUpdating = TRUE; + + // find the median key index + MedianKeyIndex = (Node->KeyCount + 1) / 2; + MedianKeyIndex--; + + // Find the last key before the median + LastKeyBeforeMedian = Node->FirstKey; + for (i = 0; i < MedianKeyIndex - 1; i++) + LastKeyBeforeMedian = LastKeyBeforeMedian->NextKey; + + // Use size to locate the median key / index + ULONG HalfSize = 2016; // half the allocated size after subtracting the first index entry offset (TODO: MATH) + ULONG SizeSum = 0; + LastKeyBeforeMedian = Node->FirstKey; + MedianKeyIndex = 0; + for (i = 0; i < Node->KeyCount; i++) + { + SizeSum += LastKeyBeforeMedian->IndexEntry->Length; + + if (SizeSum > HalfSize) + break; + + MedianKeyIndex++; + LastKeyBeforeMedian = LastKeyBeforeMedian->NextKey; + } + + // Now we can get the median key and the key that follows it + *MedianKey = LastKeyBeforeMedian->NextKey; + FirstKeyAfterMedian = (*MedianKey)->NextKey; + + DPRINT1("%lu keys, %lu median\n", Node->KeyCount, MedianKeyIndex); + DPRINT1("\t\tMedian: %.*S\n", (*MedianKey)->IndexEntry->FileName.NameLength, (*MedianKey)->IndexEntry->FileName.Name); + + // "Node" will be the left hand sibling after the split, containing all keys prior to the median key + + // We need to create a dummy pointer at the end of the LHS. The dummy's child will be the median's child. + LastKeyBeforeMedian->NextKey = CreateDummyKey(BooleanFlagOn((*MedianKey)->IndexEntry->Flags, NTFS_INDEX_ENTRY_NODE)); + if (LastKeyBeforeMedian->NextKey == NULL) + { + DPRINT1("Error: Couldn't allocate dummy key!\n"); + LastKeyBeforeMedian->NextKey = *MedianKey; + ExFreePoolWithTag(*NewRightHandSibling, TAG_NTFS); + return STATUS_INSUFFICIENT_RESOURCES; + } + + // Did the median key have a child node? + if ((*MedianKey)->IndexEntry->Flags & NTFS_INDEX_ENTRY_NODE) + { + // Set the child of the new dummy key + LastKeyBeforeMedian->NextKey->LesserChild = (*MedianKey)->LesserChild; + + // Give the dummy key's index entry the same sub-node VCN the median + SetIndexEntryVCN(LastKeyBeforeMedian->NextKey->IndexEntry, GetIndexEntryVCN((*MedianKey)->IndexEntry)); } else { - // TEMPTEMP: TODO: MATH - AllocatedNodeSize = 0xfe8; - MaxNodeSizeWithoutHeader = AllocatedNodeSize - 0x28; - - // Has the node grown larger than its allocated size? - if (NodeSize > MaxNodeSizeWithoutHeader) + // Median key didn't have a child node, but it will. Create a new index entry large enough to store a VCN. + PINDEX_ENTRY_ATTRIBUTE NewIndexEntry = ExAllocatePoolWithTag(NonPagedPool, + (*MedianKey)->IndexEntry->Length + sizeof(ULONGLONG), + TAG_NTFS); + if (!NewIndexEntry) { - DPRINT1("FIXME: Splitting a node is still a WIP!\n"); - //SplitBTreeNode(NULL, Node); - //DumpBTree(Tree); - return STATUS_NOT_IMPLEMENTED; + DPRINT1("Unable to allocate memory for new index entry!\n"); + LastKeyBeforeMedian->NextKey = *MedianKey; + ExFreePoolWithTag(*NewRightHandSibling, TAG_NTFS); + return STATUS_INSUFFICIENT_RESOURCES; } + + // Copy the old index entry to the new one + RtlCopyMemory(NewIndexEntry, (*MedianKey)->IndexEntry, (*MedianKey)->IndexEntry->Length); + + // Use the new index entry after freeing the old one + ExFreePoolWithTag((*MedianKey)->IndexEntry, TAG_NTFS); + (*MedianKey)->IndexEntry = NewIndexEntry; + + // Update the length for the VCN + (*MedianKey)->IndexEntry->Length += sizeof(ULONGLONG); + + // Set the node flag + (*MedianKey)->IndexEntry->Flags |= NTFS_INDEX_ENTRY_NODE; } - // NewEntry and NewKey will be destroyed later by DestroyBTree() + // "Node" will become the child of the median key + (*MedianKey)->LesserChild = Node; + SetIndexEntryVCN((*MedianKey)->IndexEntry, Node->VCN); - return Status; + // Update Node's KeyCount (remember to add 1 for the new dummy key) + Node->KeyCount = MedianKeyIndex + 2; + + ULONG KeyCount = CountBTreeKeys(Node->FirstKey); + ASSERT(Node->KeyCount == KeyCount); + + // everything to the right of MedianKey becomes the right hand sibling of Node + (*NewRightHandSibling)->FirstKey = FirstKeyAfterMedian; + (*NewRightHandSibling)->KeyCount = CountBTreeKeys(FirstKeyAfterMedian); + +#ifndef NDEBUG + DPRINT1("Left-hand node after split:\n"); + DumpBTreeNode(Node, 0, 0); + + DPRINT1("Right-hand sibling node after split:\n"); + DumpBTreeNode(*NewRightHandSibling, 0, 0); +#endif + + return STATUS_SUCCESS; } \ No newline at end of file diff --git a/drivers/filesystems/ntfs/mft.c b/drivers/filesystems/ntfs/mft.c index 547ab64a2b..c4328a0491 100644 --- a/drivers/filesystems/ntfs/mft.c +++ b/drivers/filesystems/ntfs/mft.c @@ -786,6 +786,11 @@ SetNonResidentAttributeDataLength(PDEVICE_EXTENSION Vcb, DestinationAttribute->NonResident.AllocatedSize = AllocationSize; DestinationAttribute->NonResident.DataSize = DataSize->QuadPart; DestinationAttribute->NonResident.InitializedSize = DataSize->QuadPart; + + // HighestVCN seems to be set incorrectly somewhere. Apply a hack-fix to reset it. + // HACKHACK FIXME: Fix for sparse files; this math won't work in that case. + AttrContext->pRecord->NonResident.HighestVCN = ((ULONGLONG)AllocationSize / Vcb->NtfsInfo.BytesPerCluster) - 1; + DestinationAttribute->NonResident.HighestVCN = AttrContext->pRecord->NonResident.HighestVCN; DPRINT("Allocated Size: %I64u\n", DestinationAttribute->NonResident.AllocatedSize); @@ -2131,6 +2136,8 @@ NtfsAddFilenameToDirectory(PDEVICE_EXTENSION DeviceExt, PB_TREE NewTree; ULONG BtreeIndexLength; ULONG MaxIndexRootSize; + PB_TREE_KEY NewLeftKey; + PB_TREE_FILENAME_NODE NewRightHandNode; // Allocate memory for the parent directory ParentFileRecord = ExAllocatePoolWithTag(NonPagedPool, @@ -2152,8 +2159,10 @@ NtfsAddFilenameToDirectory(PDEVICE_EXTENSION DeviceExt, return Status; } +#ifndef NDEBUG DPRINT1("Dumping old parent file record:\n"); NtfsDumpFileRecord(DeviceExt, ParentFileRecord); +#endif // Find the index root attribute for the directory Status = FindAttribute(DeviceExt, @@ -2176,7 +2185,7 @@ NtfsAddFilenameToDirectory(PDEVICE_EXTENSION DeviceExt, MaxIndexRootSize = DeviceExt->NtfsInfo.BytesPerFileRecord // Start with the size of a file record - IndexRootOffset // Subtract the length of everything that comes before index root - IndexRootContext->pRecord->Resident.ValueOffset // Subtract the length of the attribute header for index root - - FIELD_OFFSET(INDEX_ROOT_ATTRIBUTE, Header) // Subtract the length of the index header for index root + - sizeof(INDEX_ROOT_ATTRIBUTE) // Subtract the length of the index root header - (sizeof(ULONG) * 2); // Subtract the length of the file record end marker and padding // Are there attributes after this one? @@ -2233,10 +2242,20 @@ NtfsAddFilenameToDirectory(PDEVICE_EXTENSION DeviceExt, return Status; } +#ifndef NDEBUG DumpBTree(NewTree); +#endif // Insert the key for the file we're adding - Status = NtfsInsertKey(NewTree, FileReferenceNumber, FilenameAttribute, NewTree->RootNode, CaseSensitive, MaxIndexRootSize); + Status = NtfsInsertKey(NewTree, + FileReferenceNumber, + FilenameAttribute, + NewTree->RootNode, + CaseSensitive, + MaxIndexRootSize, + I30IndexRoot->SizeOfEntry, + &NewLeftKey, + &NewRightHandNode); if (!NT_SUCCESS(Status)) { DPRINT1("ERROR: Failed to insert key into B-Tree!\n"); @@ -2247,9 +2266,57 @@ NtfsAddFilenameToDirectory(PDEVICE_EXTENSION DeviceExt, return Status; } +#ifndef NDEBUG DumpBTree(NewTree); +#endif + + // The root node can't be split + ASSERT(NewLeftKey == NULL); + ASSERT(NewRightHandNode == NULL); + + // Convert B*Tree back to Index + + // Updating the index allocation can change the size available for the index root, + // And if the index root is demoted, the index allocation will need to be updated again, + // which may change the size available for index root... etc. + // My solution is to decrease index root to the size it would be if it was demoted, + // then UpdateIndexAllocation will have an accurate representation of the maximum space + // it can use in the file record. There's still a chance that the act of allocating an + // index node after demoting the index root will increase the size of the file record beyond + // it's limit, but if that happens, an attribute-list will most definitely be needed. + // This a bit hacky, but it seems to be functional. + + // Calculate the minimum size of the index root attribute, considering one dummy key and one VCN + LARGE_INTEGER MinIndexRootSize; + MinIndexRootSize.QuadPart = sizeof(INDEX_ROOT_ATTRIBUTE) // size of the index root headers + + 0x18; // Size of dummy key with a VCN for a subnode + ASSERT(MinIndexRootSize.QuadPart % ATTR_RECORD_ALIGNMENT == 0); + + // Temporarily shrink the index root to it's minimal size + AttributeLength = MinIndexRootSize.LowPart; + AttributeLength += sizeof(INDEX_ROOT_ATTRIBUTE); + + + // FIXME: IndexRoot will probably be invalid until we're finished. If we fail before we finish, the directory will probably be toast. + // The potential for catastrophic data-loss exists!!! :) + + // Update the length of the attribute in the file record of the parent directory + Status = InternalSetResidentAttributeLength(DeviceExt, + IndexRootContext, + ParentFileRecord, + IndexRootOffset, + AttributeLength); + if (!NT_SUCCESS(Status)) + { + DPRINT1("ERROR: Unable to set length of index root!\n"); + DestroyBTree(NewTree); + ReleaseAttributeContext(IndexRootContext); + ExFreePoolWithTag(I30IndexRoot, TAG_NTFS); + ExFreePoolWithTag(ParentFileRecord, TAG_NTFS); + return Status; + } - // Convert B*Tree back to Index, starting with the index allocation + // Update the index allocation Status = UpdateIndexAllocation(DeviceExt, NewTree, I30IndexRoot->SizeOfEntry, ParentFileRecord); if (!NT_SUCCESS(Status)) { @@ -2261,8 +2328,99 @@ NtfsAddFilenameToDirectory(PDEVICE_EXTENSION DeviceExt, return Status; } +#ifndef NDEBUG + DPRINT1("Index Allocation updated\n"); + DumpBTree(NewTree); +#endif + + // Find the maximum index root size given what the file record can hold + // First, find the max index size assuming index root is the last attribute + ULONG NewMaxIndexRootSize = + DeviceExt->NtfsInfo.BytesPerFileRecord // Start with the size of a file record + - IndexRootOffset // Subtract the length of everything that comes before index root + - IndexRootContext->pRecord->Resident.ValueOffset // Subtract the length of the attribute header for index root + - sizeof(INDEX_ROOT_ATTRIBUTE) // Subtract the length of the index root header + - (sizeof(ULONG) * 2); // Subtract the length of the file record end marker and padding + + // Are there attributes after this one? + NextAttribute = (PNTFS_ATTR_RECORD)((ULONG_PTR)ParentFileRecord + IndexRootOffset + IndexRootContext->pRecord->Length); + if (NextAttribute->Type != AttributeEnd) + { + // Find the length of all attributes after this one, not counting the end marker + ULONG LengthOfAttributes = 0; + PNTFS_ATTR_RECORD CurrentAttribute = NextAttribute; + while (CurrentAttribute->Type != AttributeEnd) + { + LengthOfAttributes += CurrentAttribute->Length; + CurrentAttribute = (PNTFS_ATTR_RECORD)((ULONG_PTR)CurrentAttribute + CurrentAttribute->Length); + } + + // Leave room for the existing attributes + NewMaxIndexRootSize -= LengthOfAttributes; + } + + // The index allocation and index bitmap may have grown, leaving less room for the index root, + // so now we need to double-check that index root isn't too large + ULONG NodeSize = GetSizeOfIndexEntries(NewTree->RootNode); + if (NodeSize > NewMaxIndexRootSize) + { + DPRINT1("Demoting index root.\nNodeSize: 0x%lx\nNewMaxIndexRootSize: 0x%lx\n", NodeSize, NewMaxIndexRootSize); + + Status = DemoteBTreeRoot(NewTree); + if (!NT_SUCCESS(Status)) + { + DPRINT1("ERROR: Failed to demote index root!\n"); + DestroyBTree(NewTree); + ReleaseAttributeContext(IndexRootContext); + ExFreePoolWithTag(I30IndexRoot, TAG_NTFS); + ExFreePoolWithTag(ParentFileRecord, TAG_NTFS); + return Status; + } + + // We need to update the index allocation once more + Status = UpdateIndexAllocation(DeviceExt, NewTree, I30IndexRoot->SizeOfEntry, ParentFileRecord); + if (!NT_SUCCESS(Status)) + { + DPRINT1("ERROR: Failed to update index allocation from B-Tree!\n"); + DestroyBTree(NewTree); + ReleaseAttributeContext(IndexRootContext); + ExFreePoolWithTag(I30IndexRoot, TAG_NTFS); + ExFreePoolWithTag(ParentFileRecord, TAG_NTFS); + return Status; + } + + // re-recalculate max size of index root + NewMaxIndexRootSize = + // Find the maximum index size given what the file record can hold + // First, find the max index size assuming index root is the last attribute + DeviceExt->NtfsInfo.BytesPerFileRecord // Start with the size of a file record + - IndexRootOffset // Subtract the length of everything that comes before index root + - IndexRootContext->pRecord->Resident.ValueOffset // Subtract the length of the attribute header for index root + - sizeof(INDEX_ROOT_ATTRIBUTE) // Subtract the length of the index root header + - (sizeof(ULONG) * 2); // Subtract the length of the file record end marker and padding + + // Are there attributes after this one? + NextAttribute = (PNTFS_ATTR_RECORD)((ULONG_PTR)ParentFileRecord + IndexRootOffset + IndexRootContext->pRecord->Length); + if (NextAttribute->Type != AttributeEnd) + { + // Find the length of all attributes after this one, not counting the end marker + ULONG LengthOfAttributes = 0; + PNTFS_ATTR_RECORD CurrentAttribute = NextAttribute; + while (CurrentAttribute->Type != AttributeEnd) + { + LengthOfAttributes += CurrentAttribute->Length; + CurrentAttribute = (PNTFS_ATTR_RECORD)((ULONG_PTR)CurrentAttribute + CurrentAttribute->Length); + } + + // Leave room for the existing attributes + NewMaxIndexRootSize -= LengthOfAttributes; + } + + + } + // Create the Index Root from the B*Tree - Status = CreateIndexRootFromBTree(DeviceExt, NewTree, MaxIndexRootSize, &NewIndexRoot, &BtreeIndexLength); + Status = CreateIndexRootFromBTree(DeviceExt, NewTree, NewMaxIndexRootSize, &NewIndexRoot, &BtreeIndexLength); if (!NT_SUCCESS(Status)) { DPRINT1("ERROR: Failed to create Index root from B-Tree!\n"); @@ -2280,9 +2438,7 @@ NtfsAddFilenameToDirectory(PDEVICE_EXTENSION DeviceExt, // First, we need to resize the attribute. // CreateIndexRootFromBTree() should have verified that the index root fits within MaxIndexSize. - // We can't set the size as we normally would, because if we extend past the file record, - // we must create an index allocation and index bitmap (TODO). Also TODO: support file records with - // $ATTRIBUTE_LIST's. + // We can't set the size as we normally would, because $INDEX_ROOT must always be resident. AttributeLength = NewIndexRoot->Header.AllocatedSize + FIELD_OFFSET(INDEX_ROOT_ATTRIBUTE, Header); if (AttributeLength != IndexRootContext->pRecord->Resident.ValueLength) @@ -2344,8 +2500,22 @@ NtfsAddFilenameToDirectory(PDEVICE_EXTENSION DeviceExt, } else { - DPRINT1("Dumping new parent file record:\n"); +#ifndef NDEBUG + DPRINT1("Dumping new B-Tree:\n"); + + Status = CreateBTreeFromIndex(DeviceExt, ParentFileRecord, IndexRootContext, NewIndexRoot, &NewTree); + if (!NT_SUCCESS(Status)) + { + DPRINT1("ERROR: Couldn't re-create b-tree\n"); + return Status; + } + + DumpBTree(NewTree); + + DestroyBTree(NewTree); + NtfsDumpFileRecord(DeviceExt, ParentFileRecord); +#endif } // Cleanup diff --git a/drivers/filesystems/ntfs/ntfs.h b/drivers/filesystems/ntfs/ntfs.h index aba8b29196..5c709c61e9 100644 --- a/drivers/filesystems/ntfs/ntfs.h +++ b/drivers/filesystems/ntfs/ntfs.h @@ -564,6 +564,13 @@ NtfsMarkIrpContextForQueue(PNTFS_IRP_CONTEXT IrpContext) //VOID //NtfsDumpAttribute(PATTRIBUTE Attribute); +NTSTATUS +AddBitmap(PNTFS_VCB Vcb, + PFILE_RECORD_HEADER FileRecord, + PNTFS_ATTR_RECORD AttributeAddress, + PCWSTR Name, + USHORT NameLength); + NTSTATUS AddData(PFILE_RECORD_HEADER FileRecord, PNTFS_ATTR_RECORD AttributeAddress); @@ -576,6 +583,13 @@ AddRun(PNTFS_VCB Vcb, ULONGLONG NextAssignedCluster, ULONG RunLength); +NTSTATUS +AddIndexAllocation(PNTFS_VCB Vcb, + PFILE_RECORD_HEADER FileRecord, + PNTFS_ATTR_RECORD AttributeAddress, + PCWSTR Name, + USHORT NameLength); + NTSTATUS AddIndexRoot(PNTFS_VCB Vcb, PFILE_RECORD_HEADER FileRecord, @@ -723,6 +737,9 @@ CreateIndexRootFromBTree(PDEVICE_EXTENSION DeviceExt, PINDEX_ROOT_ATTRIBUTE *IndexRoot, ULONG *Length); +NTSTATUS +DemoteBTreeRoot(PB_TREE Tree); + VOID DestroyBTree(PB_TREE Tree); @@ -752,13 +769,26 @@ GetAllocationOffsetFromVCN(PDEVICE_EXTENSION DeviceExt, ULONG IndexBufferSize, ULONGLONG Vcn); +ULONG +GetSizeOfIndexEntries(PB_TREE_FILENAME_NODE Node); + NTSTATUS NtfsInsertKey(PB_TREE Tree, ULONGLONG FileReference, PFILENAME_ATTRIBUTE FileNameAttribute, PB_TREE_FILENAME_NODE Node, BOOLEAN CaseSensitive, - ULONG MaxIndexRootSize); + ULONG MaxIndexRootSize, + ULONG IndexRecordSize, + PB_TREE_KEY *MedianKey, + PB_TREE_FILENAME_NODE *NewRightHandSibling); + +NTSTATUS +SplitBTreeNode(PB_TREE Tree, + PB_TREE_FILENAME_NODE Node, + PB_TREE_KEY *MedianKey, + PB_TREE_FILENAME_NODE *NewRightHandSibling, + BOOLEAN CaseSensitive); NTSTATUS UpdateIndexAllocation(PDEVICE_EXTENSION DeviceExt, @@ -772,8 +802,7 @@ UpdateIndexNode(PDEVICE_EXTENSION DeviceExt, PB_TREE_FILENAME_NODE Node, ULONG IndexBufferSize, PNTFS_ATTR_CONTEXT IndexAllocationContext, - ULONG IndexAllocationOffset, - PNTFS_ATTR_CONTEXT BitmapContext); + ULONG IndexAllocationOffset); /* close.c */

6 years, 9 months

[reactos] 67/72: [NTFS] - Fix increasing the mft size, to keep chkdsk happy. IncreaseMftSize() - Add some fixes. Write blank records to newly-allocated mft entries, and update $MFTMirr when finished; these changes are needed for chkdsk. Increase size by 64 records instead of 8. +UpdateMftMirror() - Backs up the first ~4 master file table entries to the $MFTMirr file.

by Trevor Thompson

https://git.reactos.org/?p=reactos.git;a=commitdiff;h=5e7c11842ad0b24a9a7bc… commit 5e7c11842ad0b24a9a7bc847e938a9cda0b2748e Author: Trevor Thompson <tmt256(a)email.vccs.edu> AuthorDate: Mon Aug 28 03:11:38 2017 +0000 [NTFS] - Fix increasing the mft size, to keep chkdsk happy. IncreaseMftSize() - Add some fixes. Write blank records to newly-allocated mft entries, and update $MFTMirr when finished; these changes are needed for chkdsk. Increase size by 64 records instead of 8. +UpdateMftMirror() - Backs up the first ~4 master file table entries to the $MFTMirr file. svn path=/branches/GSoC_2016/NTFS/; revision=75694 --- drivers/filesystems/ntfs/mft.c | 200 ++++++++++++++++++++++++++++++++++++++-- drivers/filesystems/ntfs/ntfs.h | 3 + 2 files changed, 195 insertions(+), 8 deletions(-) diff --git a/drivers/filesystems/ntfs/mft.c b/drivers/filesystems/ntfs/mft.c index 7d0157a761..547ab64a2b 100644 --- a/drivers/filesystems/ntfs/mft.c +++ b/drivers/filesystems/ntfs/mft.c @@ -30,6 +30,7 @@ /* INCLUDES *****************************************************************/ #include "ntfs.h" +#include <ntintsafe.h> #define NDEBUG #include <debug.h> @@ -228,7 +229,7 @@ AttributeDataLength(PNTFS_ATTR_RECORD AttrRecord) * STATUS_CANT_WAIT if CanWait was FALSE and the function could not get immediate, exclusive access to the MFT. * * @remarks -* Increases the size of the Master File Table by 8 records. Bitmap entries for the new records are cleared, +* Increases the size of the Master File Table by 64 records. Bitmap entries for the new records are cleared, * and the bitmap is also enlarged if needed. Mimicking Windows' behavior when enlarging the mft is still TODO. * This function will wait for exlusive access to the volume fcb. */ @@ -239,13 +240,17 @@ IncreaseMftSize(PDEVICE_EXTENSION Vcb, BOOLEAN CanWait) LARGE_INTEGER BitmapSize; LARGE_INTEGER DataSize; LONGLONG BitmapSizeDifference; - ULONG DataSizeDifference = Vcb->NtfsInfo.BytesPerFileRecord * 8; + ULONG NewRecords = ATTR_RECORD_ALIGNMENT * 8; // Allocate one new record for every bit of every byte we'll be adding to the bitmap + ULONG DataSizeDifference = Vcb->NtfsInfo.BytesPerFileRecord * NewRecords; ULONG BitmapOffset; PUCHAR BitmapBuffer; ULONGLONG BitmapBytes; ULONGLONG NewBitmapSize; + ULONGLONG FirstNewMftIndex; ULONG BytesRead; ULONG LengthWritten; + PFILE_RECORD_HEADER BlankFileRecord; + ULONG i; NTSTATUS Status; DPRINT1("IncreaseMftSize(%p, %s)\n", Vcb, CanWait ? "TRUE" : "FALSE"); @@ -256,11 +261,23 @@ IncreaseMftSize(PDEVICE_EXTENSION Vcb, BOOLEAN CanWait) return STATUS_CANT_WAIT; } + // Create a blank file record that will be used later + BlankFileRecord = NtfsCreateEmptyFileRecord(Vcb); + if (!BlankFileRecord) + { + DPRINT1("Error: Unable to create empty file record!\n"); + return STATUS_INSUFFICIENT_RESOURCES; + } + + // Clear the flags (file record is not in use) + BlankFileRecord->Flags = 0; + // Find the bitmap attribute of master file table - Status = FindAttribute(Vcb, Vcb->MasterFileTable, AttributeBitmap, L"", 0, &BitmapContext, &BitmapOffset); + Status = FindAttribute(Vcb, Vcb->MasterFileTable, AttributeBitmap, L"", 0, &BitmapContext, NULL); if (!NT_SUCCESS(Status)) { DPRINT1("ERROR: Couldn't find $BITMAP attribute of Mft!\n"); + ExFreePoolWithTag(BlankFileRecord, TAG_NTFS); ExReleaseResourceLite(&(Vcb->DirResource)); return Status; } @@ -271,9 +288,17 @@ IncreaseMftSize(PDEVICE_EXTENSION Vcb, BOOLEAN CanWait) // Calculate the new mft size DataSize.QuadPart = AttributeDataLength(Vcb->MFTContext->pRecord) + DataSizeDifference; + // Find the index of the first Mft entry that will be created + FirstNewMftIndex = AttributeDataLength(Vcb->MFTContext->pRecord) / Vcb->NtfsInfo.BytesPerFileRecord; + // Determine how many bytes will make up the bitmap BitmapBytes = DataSize.QuadPart / Vcb->NtfsInfo.BytesPerFileRecord / 8; - + if ((DataSize.QuadPart / Vcb->NtfsInfo.BytesPerFileRecord) % 8 != 0) + BitmapBytes++; + + // Windows will always keep the number of bytes in a bitmap as a multiple of 8, so no bytes are wasted on slack + BitmapBytes = ALIGN_UP_BY(BitmapBytes, ATTR_RECORD_ALIGNMENT); + // Determine how much we need to adjust the bitmap size (it's possible we don't) BitmapSizeDifference = BitmapBytes - BitmapSize.QuadPart; NewBitmapSize = max(BitmapSize.QuadPart + BitmapSizeDifference, BitmapSize.QuadPart); @@ -283,6 +308,7 @@ IncreaseMftSize(PDEVICE_EXTENSION Vcb, BOOLEAN CanWait) if (!BitmapBuffer) { DPRINT1("ERROR: Unable to allocate memory for bitmap attribute!\n"); + ExFreePoolWithTag(BlankFileRecord, TAG_NTFS); ExReleaseResourceLite(&(Vcb->DirResource)); ReleaseAttributeContext(BitmapContext); return STATUS_INSUFFICIENT_RESOURCES; @@ -300,6 +326,7 @@ IncreaseMftSize(PDEVICE_EXTENSION Vcb, BOOLEAN CanWait) if (BytesRead != BitmapSize.LowPart) { DPRINT1("ERROR: Bytes read != Bitmap size!\n"); + ExFreePoolWithTag(BlankFileRecord, TAG_NTFS); ExReleaseResourceLite(&(Vcb->DirResource)); ExFreePoolWithTag(BitmapBuffer, TAG_NTFS); ReleaseAttributeContext(BitmapContext); @@ -311,17 +338,29 @@ IncreaseMftSize(PDEVICE_EXTENSION Vcb, BOOLEAN CanWait) if (!NT_SUCCESS(Status)) { DPRINT1("ERROR: Failed to set size of $MFT data attribute!\n"); + ExFreePoolWithTag(BlankFileRecord, TAG_NTFS); ExReleaseResourceLite(&(Vcb->DirResource)); ExFreePoolWithTag(BitmapBuffer, TAG_NTFS); ReleaseAttributeContext(BitmapContext); return Status; } + + // We'll need to find the bitmap again, because its offset will have changed after resizing the data attribute + ReleaseAttributeContext(BitmapContext); + Status = FindAttribute(Vcb, Vcb->MasterFileTable, AttributeBitmap, L"", 0, &BitmapContext, &BitmapOffset); + if (!NT_SUCCESS(Status)) + { + DPRINT1("ERROR: Couldn't find $BITMAP attribute of Mft!\n"); + ExFreePoolWithTag(BlankFileRecord, TAG_NTFS); + ExReleaseResourceLite(&(Vcb->DirResource)); + return Status; + } // If the bitmap grew if (BitmapSizeDifference > 0) { // Set the new bitmap size - BitmapSize.QuadPart += BitmapSizeDifference; + BitmapSize.QuadPart = NewBitmapSize; if (BitmapContext->pRecord->IsNonResident) Status = SetNonResidentAttributeDataLength(Vcb, BitmapContext, BitmapOffset, Vcb->MasterFileTable, &BitmapSize); else @@ -330,6 +369,7 @@ IncreaseMftSize(PDEVICE_EXTENSION Vcb, BOOLEAN CanWait) if (!NT_SUCCESS(Status)) { DPRINT1("ERROR: Failed to set size of bitmap attribute!\n"); + ExFreePoolWithTag(BlankFileRecord, TAG_NTFS); ExReleaseResourceLite(&(Vcb->DirResource)); ExFreePoolWithTag(BitmapBuffer, TAG_NTFS); ReleaseAttributeContext(BitmapContext); @@ -337,13 +377,14 @@ IncreaseMftSize(PDEVICE_EXTENSION Vcb, BOOLEAN CanWait) } } - //NtfsDumpFileAttributes(Vcb, FileRecord); + NtfsDumpFileAttributes(Vcb, Vcb->MasterFileTable); // Update the file record with the new attribute sizes Status = UpdateFileRecord(Vcb, Vcb->VolumeFcb->MFTIndex, Vcb->MasterFileTable); if (!NT_SUCCESS(Status)) { DPRINT1("ERROR: Failed to update $MFT file record!\n"); + ExFreePoolWithTag(BlankFileRecord, TAG_NTFS); ExReleaseResourceLite(&(Vcb->DirResource)); ExFreePoolWithTag(BitmapBuffer, TAG_NTFS); ReleaseAttributeContext(BitmapContext); @@ -351,9 +392,10 @@ IncreaseMftSize(PDEVICE_EXTENSION Vcb, BOOLEAN CanWait) } // Write out the new bitmap - Status = WriteAttribute(Vcb, BitmapContext, BitmapOffset, BitmapBuffer, BitmapSize.LowPart, &LengthWritten, Vcb->MasterFileTable); + Status = WriteAttribute(Vcb, BitmapContext, 0, BitmapBuffer, NewBitmapSize, &LengthWritten, Vcb->MasterFileTable); if (!NT_SUCCESS(Status)) { + ExFreePoolWithTag(BlankFileRecord, TAG_NTFS); ExReleaseResourceLite(&(Vcb->DirResource)); ExFreePoolWithTag(BitmapBuffer, TAG_NTFS); ReleaseAttributeContext(BitmapContext); @@ -361,12 +403,31 @@ IncreaseMftSize(PDEVICE_EXTENSION Vcb, BOOLEAN CanWait) return Status; } + // Create blank records for the new file record entries. + for (i = 0; i < NewRecords; i++) + { + Status = UpdateFileRecord(Vcb, FirstNewMftIndex + i, BlankFileRecord); + if (!NT_SUCCESS(Status)) + { + DPRINT1("ERROR: Failed to write blank file record!\n"); + ExFreePoolWithTag(BlankFileRecord, TAG_NTFS); + ExReleaseResourceLite(&(Vcb->DirResource)); + ExFreePoolWithTag(BitmapBuffer, TAG_NTFS); + ReleaseAttributeContext(BitmapContext); + return Status; + } + } + + // Update the mft mirror + Status = UpdateMftMirror(Vcb); + // Cleanup + ExFreePoolWithTag(BlankFileRecord, TAG_NTFS); ExReleaseResourceLite(&(Vcb->DirResource)); ExFreePoolWithTag(BitmapBuffer, TAG_NTFS); ReleaseAttributeContext(BitmapContext); - return STATUS_SUCCESS; + return Status; } /** @@ -2384,6 +2445,129 @@ CompareFileName(PUNICODE_STRING FileName, } } +/** +* @name UpdateMftMirror +* @implemented +* +* Backs-up the first ~4 master file table entries to the $MFTMirr file. +* +* @param Vcb +* Pointer to an NTFS_VCB for the volume whose Mft mirror is being updated. +* +* @returninja livecd + +* STATUS_SUCCESS on success. +* STATUS_INSUFFICIENT_RESOURCES if an allocation failed. +* STATUS_UNSUCCESSFUL if we couldn't read the master file table. +* +* @remarks +* NTFS maintains up-to-date copies of the first several mft entries in the $MFTMirr file. Usually, the first 4 file +* records from the mft are stored. The exact number of entries is determined by the size of $MFTMirr's $DATA. +* If $MFTMirr is not up-to-date, chkdsk will reject every change it can find prior to when $MFTMirr was last updated. +* Therefore, it's recommended to call this function if the volume changes considerably. For instance, IncreaseMftSize() +* relies on this function to keep chkdsk from deleting the mft entries it creates. Note that under most instances, creating +* or deleting a file will not affect the first ~four mft entries, and so will not require updating the mft mirror. +*/ +NTSTATUS +UpdateMftMirror(PNTFS_VCB Vcb) +{ + PFILE_RECORD_HEADER MirrorFileRecord; + PNTFS_ATTR_CONTEXT MirrDataContext; + PNTFS_ATTR_CONTEXT MftDataContext; + PCHAR DataBuffer; + ULONGLONG DataLength; + NTSTATUS Status; + ULONG BytesRead; + ULONG LengthWritten; + + // Allocate memory for the Mft mirror file record + MirrorFileRecord = ExAllocatePoolWithTag(NonPagedPool, Vcb->NtfsInfo.BytesPerFileRecord, TAG_NTFS); + if (!MirrorFileRecord) + { + DPRINT1("Error: Failed to allocate memory for $MFTMirr!\n"); + return STATUS_INSUFFICIENT_RESOURCES; + } + + // Read the Mft Mirror file record + Status = ReadFileRecord(Vcb, NTFS_FILE_MFTMIRR, MirrorFileRecord); + if (!NT_SUCCESS(Status)) + { + DPRINT1("ERROR: Failed to read $MFTMirr!\n"); + ExFreePoolWithTag(MirrorFileRecord, TAG_NTFS); + return Status; + } + + // Find the $DATA attribute of $MFTMirr + Status = FindAttribute(Vcb, MirrorFileRecord, AttributeData, L"", 0, &MirrDataContext, NULL); + if (!NT_SUCCESS(Status)) + { + DPRINT1("ERROR: Couldn't find $DATA attribute!\n"); + ExFreePoolWithTag(MirrorFileRecord, TAG_NTFS); + return Status; + } + + // Find the $DATA attribute of $MFT + Status = FindAttribute(Vcb, Vcb->MasterFileTable, AttributeData, L"", 0, &MftDataContext, NULL); + if (!NT_SUCCESS(Status)) + { + DPRINT1("ERROR: Couldn't find $DATA attribute!\n"); + ReleaseAttributeContext(MirrDataContext); + ExFreePoolWithTag(MirrorFileRecord, TAG_NTFS); + return Status; + } + + // Get the size of the mirror's $DATA attribute + DataLength = AttributeDataLength(MirrDataContext->pRecord); + + ASSERT(DataLength % Vcb->NtfsInfo.BytesPerFileRecord == 0); + + // Create buffer for the mirror's $DATA attribute + DataBuffer = ExAllocatePoolWithTag(NonPagedPool, DataLength, TAG_NTFS); + if (!DataBuffer) + { + DPRINT1("Error: Couldn't allocate memory for $DATA buffer!\n"); + ReleaseAttributeContext(MftDataContext); + ReleaseAttributeContext(MirrDataContext); + ExFreePoolWithTag(MirrorFileRecord, TAG_NTFS); + return STATUS_INSUFFICIENT_RESOURCES; + } + + ASSERT(DataLength < ULONG_MAX); + + // Back up the first several entries of the Mft's $DATA Attribute + BytesRead = ReadAttribute(Vcb, MftDataContext, 0, DataBuffer, (ULONG)DataLength); + if (BytesRead != (ULONG)DataLength) + { + DPRINT1("Error: Failed to read $DATA for $MFTMirr!\n"); + ReleaseAttributeContext(MftDataContext); + ReleaseAttributeContext(MirrDataContext); + ExFreePoolWithTag(DataBuffer, TAG_NTFS); + ExFreePoolWithTag(MirrorFileRecord, TAG_NTFS); + return STATUS_UNSUCCESSFUL; + } + + // Write the mirror's $DATA attribute + Status = WriteAttribute(Vcb, + MirrDataContext, + 0, + (PUCHAR)DataBuffer, + DataLength, + &LengthWritten, + MirrorFileRecord); + if (!NT_SUCCESS(Status)) + { + DPRINT1("ERROR: Failed to write $DATA attribute of $MFTMirr!\n"); + } + + // Cleanup + ReleaseAttributeContext(MftDataContext); + ReleaseAttributeContext(MirrDataContext); + ExFreePoolWithTag(DataBuffer, TAG_NTFS); + ExFreePoolWithTag(MirrorFileRecord, TAG_NTFS); + + return Status; +} + #if 0 static VOID diff --git a/drivers/filesystems/ntfs/ntfs.h b/drivers/filesystems/ntfs/ntfs.h index abd2d2791d..aba8b29196 100644 --- a/drivers/filesystems/ntfs/ntfs.h +++ b/drivers/filesystems/ntfs/ntfs.h @@ -1047,6 +1047,9 @@ CompareFileName(PUNICODE_STRING FileName, BOOLEAN DirSearch, BOOLEAN CaseSensitive); +NTSTATUS +UpdateMftMirror(PNTFS_VCB Vcb); + NTSTATUS ReadFileRecord(PDEVICE_EXTENSION Vcb, ULONGLONG index,

6 years, 9 months

[reactos] 66/72: [NTFS] - Fix for C89 compliance.

by Trevor Thompson

https://git.reactos.org/?p=reactos.git;a=commitdiff;h=9a91a51f17c3baf5c510e… commit 9a91a51f17c3baf5c510effb869e4d6fb4097e6c Author: Trevor Thompson <tmt256(a)email.vccs.edu> AuthorDate: Sun Aug 27 14:43:35 2017 +0000 [NTFS] - Fix for C89 compliance. svn path=/branches/GSoC_2016/NTFS/; revision=75693 --- drivers/filesystems/ntfs/create.c | 7 ++++--- 1 file changed, 4 insertions(+), 3 deletions(-) diff --git a/drivers/filesystems/ntfs/create.c b/drivers/filesystems/ntfs/create.c index 55e1e95a38..b591b79073 100644 --- a/drivers/filesystems/ntfs/create.c +++ b/drivers/filesystems/ntfs/create.c @@ -698,6 +698,7 @@ NtfsCreateDirectory(PDEVICE_EXTENSION DeviceExt, ULONGLONG FileMftIndex; PB_TREE Tree; PINDEX_ROOT_ATTRIBUTE NewIndexRoot; + ULONG MaxIndexRootSize; ULONG RootLength; DPRINT1("NtfsCreateFileRecord(%p, %p, %s, %s)\n", @@ -745,9 +746,9 @@ NtfsCreateDirectory(PDEVICE_EXTENSION DeviceExt, } // Calculate maximum size of index root - ULONG MaxIndexRootSize = DeviceExt->NtfsInfo.BytesPerFileRecord - - ((ULONG_PTR)NextAttribute - (ULONG_PTR)FileRecord) - - sizeof(ULONG) * 2; + MaxIndexRootSize = DeviceExt->NtfsInfo.BytesPerFileRecord + - ((ULONG_PTR)NextAttribute - (ULONG_PTR)FileRecord) + - sizeof(ULONG) * 2; // Create a new index record from the tree Status = CreateIndexRootFromBTree(DeviceExt,

6 years, 9 months

[reactos] 65/72: [NTFS] - Add support for directory creation. Add some helper functions, some comments, and some fixes. +AddIndexRoot() - Creates an $INDEX_ROOT attribute and adds it to a file record. AddNewMftEntry() - Make sure the buffer used by RtlInitializeBitmap() is ULONG-aligned, and a ULONG-multiple in size, per MSDN. AllocateIndexNode() - Calculate BytesNeeded correctly. Read $BITMAP attribute before increasing its length, in anticipation of a future commit that will check for a free b

by Trevor Thompson

https://git.reactos.org/?p=reactos.git;a=commitdiff;h=b033f00f58c48d139a866… commit b033f00f58c48d139a86688818d5c3a7692037aa Author: Trevor Thompson <tmt256(a)email.vccs.edu> AuthorDate: Sun Aug 27 14:37:17 2017 +0000 [NTFS] - Add support for directory creation. Add some helper functions, some comments, and some fixes. +AddIndexRoot() - Creates an $INDEX_ROOT attribute and adds it to a file record. AddNewMftEntry() - Make sure the buffer used by RtlInitializeBitmap() is ULONG-aligned, and a ULONG-multiple in size, per MSDN. AllocateIndexNode() - Calculate BytesNeeded correctly. Read $BITMAP attribute before increasing its length, in anticipation of a future commit that will check for a free bit before assigning a new index record to the end of the allocation. Use appropriate Set*AttributeDataLength() function, as $BITMAP can be resident or non-resident. B_TREE_FILENAME_NODE - Give two members more accurate names: change "ExistsOnDisk" member to "HasValidVCN" and rename "NodeNumber" member "VCN." +CreateEmptyBTree() - Creates a B-Tree to represent an empty directory (for AddIndexRoot). +NtfsCreateEmptyFileRecord() - Creates an empty file record in memory, with no attributes. CreateIndexRootFromBTree() - Fix TotalSizeOfEntries calculation. +NtfsCreateDirectory() - Creates a file record for an empty directory and adds it to the mft. svn path=/branches/GSoC_2016/NTFS/; revision=75692 --- drivers/filesystems/ntfs/attrib.c | 112 +++++++++++++++++- drivers/filesystems/ntfs/btree.c | 208 +++++++++++++++++++++++---------- drivers/filesystems/ntfs/create.c | 239 ++++++++++++++++++++++++++++++++++---- drivers/filesystems/ntfs/mft.c | 32 +++-- drivers/filesystems/ntfs/ntfs.h | 40 ++++++- 5 files changed, 530 insertions(+), 101 deletions(-) diff --git a/drivers/filesystems/ntfs/attrib.c b/drivers/filesystems/ntfs/attrib.c index e830264ad6..34bee2a060 100644 --- a/drivers/filesystems/ntfs/attrib.c +++ b/drivers/filesystems/ntfs/attrib.c @@ -167,7 +167,11 @@ AddFileName(PFILE_RECORD_HEADER FileRecord, FileNameAttribute->LastWriteTime = SystemTime.QuadPart; FileNameAttribute->LastAccessTime = SystemTime.QuadPart; - FileNameAttribute->FileAttributes = NTFS_FILE_TYPE_ARCHIVE; + // Is this a directory? + if(FileRecord->Flags & FRH_DIRECTORY) + FileNameAttribute->FileAttributes = NTFS_FILE_TYPE_DIRECTORY; + else + FileNameAttribute->FileAttributes = NTFS_FILE_TYPE_ARCHIVE; // we need to extract the filename from the path DPRINT1("Pathname: %wZ\n", &FileObject->FileName); @@ -254,6 +258,112 @@ AddFileName(PFILE_RECORD_HEADER FileRecord, return Status; } +/** +* @name AddIndexRoot +* @implemented +* +* Adds an $INDEX_ROOT attribute to a given FileRecord. +* +* @param Vcb +* Pointer to an NTFS_VCB for the destination volume. +* +* @param FileRecord +* Pointer to a complete file record to add the attribute to. Caller is responsible for +* ensuring FileRecord is large enough to contain $INDEX_ROOT. +* +* @param AttributeAddress +* Pointer to the region of memory that will receive the $INDEX_ROOT attribute. +* This address must reside within FileRecord. Must be aligned to an 8-byte boundary (relative to FileRecord). +* +* @param NewIndexRoot +* Pointer to an INDEX_ROOT_ATTRIBUTE containing the index root that will be copied to the new attribute. +* +* @param RootLength +* The length of NewIndexRoot, in bytes. +* +* @param Name +* Pointer to a string of 16-bit Unicode characters naming the attribute. Most often, this will be L"$I30". +* +* @param NameLength +* The number of wide-characters in the name. L"$I30" Would use 4 here. +* +* @return +* STATUS_SUCCESS on success. STATUS_NOT_IMPLEMENTED if target address isn't at the end +* of the given file record. +* +* @remarks +* This function is intended to assist in creating new folders. +* Only adding the attribute to the end of the file record is supported; AttributeAddress must +* be of type AttributeEnd. +* It's the caller's responsibility to ensure the given file record has enough memory allocated +* for the attribute, and this memory must have been zeroed. +*/ +NTSTATUS +AddIndexRoot(PNTFS_VCB Vcb, + PFILE_RECORD_HEADER FileRecord, + PNTFS_ATTR_RECORD AttributeAddress, + PINDEX_ROOT_ATTRIBUTE NewIndexRoot, + ULONG RootLength, + PCWSTR Name, + USHORT NameLength) +{ + ULONG AttributeLength; + // Calculate the header length + ULONG ResidentHeaderLength = FIELD_OFFSET(NTFS_ATTR_RECORD, Resident.Reserved) + sizeof(UCHAR); + // Back up the file record's final ULONG (even though it doesn't matter) + ULONG FileRecordEnd = AttributeAddress->Length; + ULONG NameOffset; + ULONG ValueOffset; + ULONG BytesAvailable; + + if (AttributeAddress->Type != AttributeEnd) + { + DPRINT1("FIXME: Can only add $DATA attribute to the end of a file record.\n"); + return STATUS_NOT_IMPLEMENTED; + } + + NameOffset = ResidentHeaderLength; + + // Calculate ValueOffset, which will be aligned to a 4-byte boundary + ValueOffset = ALIGN_UP_BY(NameOffset + (sizeof(WCHAR) * NameLength), VALUE_OFFSET_ALIGNMENT); + + // Calculate length of attribute + AttributeLength = ValueOffset + RootLength; + AttributeLength = ALIGN_UP_BY(AttributeLength, ATTR_RECORD_ALIGNMENT); + + // Make sure the file record is large enough for the new attribute + BytesAvailable = Vcb->NtfsInfo.BytesPerFileRecord - FileRecord->BytesInUse; + if (BytesAvailable < AttributeLength) + { + DPRINT1("FIXME: Not enough room in file record for index allocation attribute!\n"); + return STATUS_NOT_IMPLEMENTED; + } + + // Set Attribute fields + RtlZeroMemory(AttributeAddress, AttributeLength); + + AttributeAddress->Type = AttributeIndexRoot; + AttributeAddress->Length = AttributeLength; + AttributeAddress->NameLength = NameLength; + AttributeAddress->NameOffset = NameOffset; + AttributeAddress->Instance = FileRecord->NextAttributeNumber++; + + AttributeAddress->Resident.ValueLength = RootLength; + AttributeAddress->Resident.ValueOffset = ValueOffset; + + // Set the name + RtlCopyMemory((PCHAR)((ULONG_PTR)AttributeAddress + NameOffset), Name, NameLength * sizeof(WCHAR)); + + // Copy the index root attribute + RtlCopyMemory((PCHAR)((ULONG_PTR)AttributeAddress + ValueOffset), NewIndexRoot, RootLength); + + // move the attribute-end and file-record-end markers to the end of the file record + AttributeAddress = (PNTFS_ATTR_RECORD)((ULONG_PTR)AttributeAddress + AttributeAddress->Length); + SetFileRecordEnd(FileRecord, AttributeAddress, FileRecordEnd); + + return STATUS_SUCCESS; +} + /** * @name AddRun * @implemented diff --git a/drivers/filesystems/ntfs/btree.c b/drivers/filesystems/ntfs/btree.c index 727c147a2a..cd9cf35069 100644 --- a/drivers/filesystems/ntfs/btree.c +++ b/drivers/filesystems/ntfs/btree.c @@ -111,6 +111,7 @@ PrintAllVCNs(PDEVICE_EXTENSION Vcb, * @remarks * AllocateIndexNode() doesn't write any data to the index record it creates. Called by UpdateIndexNode(). * Don't call PrintAllVCNs() or NtfsDumpFileRecord() after calling AllocateIndexNode() before UpdateIndexNode() finishes. +* Possible TODO: Create an empty node and write it to the allocated index node, so the index allocation is always valid. */ NTSTATUS AllocateIndexNode(PDEVICE_EXTENSION DeviceExt, @@ -167,11 +168,30 @@ AllocateIndexNode(PDEVICE_EXTENSION DeviceExt, // See how many bytes we need to store the amount of bits we'll have BytesNeeded = NextNodeNumber / 8; - if (NextNodeNumber % 8 != 0) - BytesNeeded++; + BytesNeeded++; // Windows seems to allocate the bitmap in 8-byte chunks to keep any bytes from being wasted on padding - ALIGN_UP(BytesNeeded, ATTR_RECORD_ALIGNMENT); + BytesNeeded = ALIGN_UP(BytesNeeded, ATTR_RECORD_ALIGNMENT); + + // Allocate memory for the bitmap, including some padding; RtlInitializeBitmap() wants a pointer + // that's ULONG-aligned, and it wants the size of the memory allocated for it to be a ULONG-multiple. + BitmapMem = ExAllocatePoolWithTag(NonPagedPool, BytesNeeded + sizeof(ULONG), TAG_NTFS); + if (!BitmapMem) + { + DPRINT1("Error: failed to allocate bitmap!"); + ReleaseAttributeContext(BitmapCtx); + return STATUS_INSUFFICIENT_RESOURCES; + } + // RtlInitializeBitmap() wants a pointer that's ULONG-aligned. + BitmapPtr = (PULONG)ALIGN_UP_BY((ULONG_PTR)BitmapMem, sizeof(ULONG)); + + RtlZeroMemory(BitmapPtr, BytesNeeded); + + // Read the existing bitmap data + Status = ReadAttribute(DeviceExt, BitmapCtx, 0, (PCHAR)BitmapPtr, BitmapLength); + + // Initialize bitmap + RtlInitializeBitMap(&Bitmap, BitmapPtr, NextNodeNumber); // Do we need to enlarge the bitmap? if (BytesNeeded > BitmapLength) @@ -179,11 +199,22 @@ AllocateIndexNode(PDEVICE_EXTENSION DeviceExt, // TODO: handle synchronization issues that could occur from changing the directory's file record // Change bitmap size DataSize.QuadPart = BytesNeeded; - Status = SetResidentAttributeDataLength(DeviceExt, - BitmapCtx, - BitmapOffset, - FileRecord, - &DataSize); + if (BitmapCtx->pRecord->IsNonResident) + { + Status = SetNonResidentAttributeDataLength(DeviceExt, + BitmapCtx, + BitmapOffset, + FileRecord, + &DataSize); + } + else + { + Status = SetResidentAttributeDataLength(DeviceExt, + BitmapCtx, + BitmapOffset, + FileRecord, + &DataSize); + } if (!NT_SUCCESS(Status)) { DPRINT1("ERROR: Failed to set length of bitmap attribute!\n"); @@ -215,18 +246,6 @@ AllocateIndexNode(PDEVICE_EXTENSION DeviceExt, return Status; } - // Allocate memory for the bitmap. RtlInitializeBitmap() wants a pointer that's ULONG-aligned - BitmapMem = ExAllocatePoolWithTag(NonPagedPool, BytesNeeded + sizeof(ULONG) - 1, TAG_NTFS); - BitmapPtr = (PULONG)ALIGN_UP_BY((ULONG_PTR)BitmapMem, sizeof(ULONG)); - - RtlZeroMemory(BitmapPtr, BytesNeeded); - - // Read the existing bitmap data - Status = ReadAttribute(DeviceExt, BitmapCtx, 0, (PCHAR)BitmapPtr, BitmapLength); - - // Initialize bitmap - RtlInitializeBitMap(&Bitmap, BitmapPtr, BytesNeeded); - // Set the bit for the new index record RtlSetBits(&Bitmap, NextNodeNumber, 1); @@ -246,6 +265,8 @@ AllocateIndexNode(PDEVICE_EXTENSION DeviceExt, // Calculate VCN of new node number *NewVCN = NextNodeNumber * (IndexBufferSize / DeviceExt->NtfsInfo.BytesPerCluster); + DPRINT("New VCN: %I64u\n", *NewVCN); + ExFreePoolWithTag(BitmapMem, TAG_NTFS); ReleaseAttributeContext(BitmapCtx); @@ -311,6 +332,63 @@ CreateDummyKey(BOOLEAN HasChildNode) return NewDummyKey; } +/** +* @name CreateEmptyBTree +* @implemented +* +* Creates an empty B-Tree, which will contain a single root node which will contain a single dummy key. +* +* @param NewTree +* Pointer to a PB_TREE that will receive the pointer of the newly-created B-Tree. +* +* @return +* STATUS_SUCCESS on success. STATUS_INSUFFICIENT_RESOURCES if an allocation fails. +*/ +NTSTATUS +CreateEmptyBTree(PB_TREE *NewTree) +{ + PB_TREE Tree = ExAllocatePoolWithTag(NonPagedPool, sizeof(B_TREE), TAG_NTFS); + PB_TREE_FILENAME_NODE RootNode = ExAllocatePoolWithTag(NonPagedPool, sizeof(B_TREE_FILENAME_NODE), TAG_NTFS); + PB_TREE_KEY DummyKey; + + DPRINT1("CreateEmptyBTree(%p) called\n", NewTree); + + if (!Tree || !RootNode) + { + DPRINT1("Couldn't allocate enough memory for B-Tree!\n"); + if (Tree) + ExFreePoolWithTag(Tree, TAG_NTFS); + if (RootNode) + ExFreePoolWithTag(RootNode, TAG_NTFS); + return STATUS_INSUFFICIENT_RESOURCES; + } + + // Create the dummy key + DummyKey = CreateDummyKey(FALSE); + if (!DummyKey) + { + DPRINT1("ERROR: Failed to create dummy key!\n"); + ExFreePoolWithTag(Tree, TAG_NTFS); + ExFreePoolWithTag(RootNode, TAG_NTFS); + return STATUS_INSUFFICIENT_RESOURCES; + } + + RtlZeroMemory(Tree, sizeof(B_TREE)); + RtlZeroMemory(RootNode, sizeof(B_TREE_FILENAME_NODE)); + + // Setup the Tree + RootNode->FirstKey = DummyKey; + RootNode->KeyCount = 1; + RootNode->DiskNeedsUpdating = TRUE; + Tree->RootNode = RootNode; + + *NewTree = Tree; + + // Memory will be freed when DestroyBTree() is called + + return STATUS_SUCCESS; +} + /** * @name CompareTreeKeys * @implemented @@ -402,7 +480,7 @@ CreateBTreeNodeFromIndexNode(PDEVICE_EXTENSION Vcb, ULONG CurrentEntryOffset = 0; PINDEX_BUFFER NodeBuffer; ULONG IndexBufferSize = Vcb->NtfsInfo.BytesPerIndexRecord; - PULONGLONG NodeNumber; + PULONGLONG VCN; PB_TREE_KEY CurrentKey; NTSTATUS Status; ULONGLONG IndexNodeOffset; @@ -415,10 +493,9 @@ CreateBTreeNodeFromIndexNode(PDEVICE_EXTENSION Vcb, } // Get the node number from the end of the node entry - NodeNumber = (PULONGLONG)((ULONG_PTR)NodeEntry + NodeEntry->Length - sizeof(ULONGLONG)); + VCN = (PULONGLONG)((ULONG_PTR)NodeEntry + NodeEntry->Length - sizeof(ULONGLONG)); // Create the new tree node - DPRINT1("About to allocate %ld for NewNode\n", sizeof(B_TREE_FILENAME_NODE)); NewNode = ExAllocatePoolWithTag(NonPagedPool, sizeof(B_TREE_FILENAME_NODE), TAG_NTFS); if (!NewNode) { @@ -449,7 +526,7 @@ CreateBTreeNodeFromIndexNode(PDEVICE_EXTENSION Vcb, } // Calculate offset into index allocation - IndexNodeOffset = GetAllocationOffsetFromVCN(Vcb, IndexBufferSize, *NodeNumber); + IndexNodeOffset = GetAllocationOffsetFromVCN(Vcb, IndexBufferSize, *VCN); // TODO: Confirm index bitmap has this node marked as in-use @@ -462,7 +539,7 @@ CreateBTreeNodeFromIndexNode(PDEVICE_EXTENSION Vcb, ASSERT(BytesRead == IndexBufferSize); NT_ASSERT(NodeBuffer->Ntfs.Type == NRH_INDX_TYPE); - NT_ASSERT(NodeBuffer->VCN == *NodeNumber); + NT_ASSERT(NodeBuffer->VCN == *VCN); // Apply the fixup array to the node buffer Status = FixupUpdateSequenceArray(Vcb, &NodeBuffer->Ntfs); @@ -516,8 +593,6 @@ CreateBTreeNodeFromIndexNode(PDEVICE_EXTENSION Vcb, // See if the current key has a sub-node if (CurrentKey->IndexEntry->Flags & NTFS_INDEX_ENTRY_NODE) { - DPRINT1("TODO: Only a node with a single-level is supported right now!\n"); - // Needs debugging: CurrentKey->LesserChild = CreateBTreeNodeFromIndexNode(Vcb, IndexRoot, IndexAllocationAttributeCtx, @@ -535,8 +610,6 @@ CreateBTreeNodeFromIndexNode(PDEVICE_EXTENSION Vcb, // See if the current key has a sub-node if (CurrentKey->IndexEntry->Flags & NTFS_INDEX_ENTRY_NODE) { - DPRINT1("TODO: Only a node with a single-level is supported right now!\n"); - // Needs debugging: CurrentKey->LesserChild = CreateBTreeNodeFromIndexNode(Vcb, IndexRoot, IndexAllocationAttributeCtx, @@ -551,8 +624,8 @@ CreateBTreeNodeFromIndexNode(PDEVICE_EXTENSION Vcb, CurrentNodeEntry = (PINDEX_ENTRY_ATTRIBUTE)((ULONG_PTR)CurrentNodeEntry + CurrentNodeEntry->Length); } - NewNode->NodeNumber = *NodeNumber; - NewNode->ExistsOnDisk = TRUE; + NewNode->VCN = *VCN; + NewNode->HasValidVCN = TRUE; ExFreePoolWithTag(NodeBuffer, TAG_NTFS); @@ -622,8 +695,6 @@ CreateBTreeFromIndex(PDEVICE_EXTENSION Vcb, NULL); if (!NT_SUCCESS(Status)) IndexAllocationContext = NULL; - else - PrintAllVCNs(Vcb, IndexAllocationContext, IndexRoot->SizeOfEntry); // Setup the Tree RootNode->FirstKey = CurrentKey; @@ -871,7 +942,7 @@ CreateIndexRootFromBTree(PDEVICE_EXTENSION DeviceExt, NewIndexRoot->Header.Flags = INDEX_ROOT_LARGE; // Add Length of Current Entry to Total Size of Entries - NewIndexRoot->Header.TotalSizeOfEntries += CurrentNodeEntry->Length; + NewIndexRoot->Header.TotalSizeOfEntries += CurrentKey->IndexEntry->Length; // Go to the next node entry CurrentNodeEntry = (PINDEX_ENTRY_ATTRIBUTE)((ULONG_PTR)CurrentNodeEntry + CurrentNodeEntry->Length); @@ -905,10 +976,12 @@ CreateIndexBufferFromBTreeNode(PDEVICE_EXTENSION DeviceExt, IndexBuffer->Ntfs.UsaCount = 9; // TODO: Check bitmap for VCN - ASSERT(Node->ExistsOnDisk); - IndexBuffer->VCN = Node->NodeNumber; + ASSERT(Node->HasValidVCN); + IndexBuffer->VCN = Node->VCN; - IndexBuffer->Header.FirstEntryOffset = 0x28; + // Windows seems to alternate between using 0x28 and 0x40 for the first entry offset of each index buffer. + // Interestingly, neither Windows nor chkdsk seem to mind if we just use 0x28 for every index record. + IndexBuffer->Header.FirstEntryOffset = 0x28; IndexBuffer->Header.AllocatedSize = BufferSize - FIELD_OFFSET(INDEX_BUFFER, Header); // Start summing the total size of this node's entries @@ -934,9 +1007,9 @@ CreateIndexBufferFromBTreeNode(PDEVICE_EXTENSION DeviceExt, // Copy the index entry RtlCopyMemory(CurrentNodeEntry, CurrentKey->IndexEntry, CurrentKey->IndexEntry->Length); - DPRINT1("Index Node Entry Stream Length: %u\nIndex Node Entry Length: %u\n", - CurrentNodeEntry->KeyLength, - CurrentNodeEntry->Length); + DPRINT("Index Node Entry Stream Length: %u\nIndex Node Entry Length: %u\n", + CurrentNodeEntry->KeyLength, + CurrentNodeEntry->Length); // Add Length of Current Entry to Total Size of Entries IndexBuffer->Header.TotalSizeOfEntries += CurrentNodeEntry->Length; @@ -1020,14 +1093,6 @@ UpdateIndexAllocation(PDEVICE_EXTENSION DeviceExt, DPRINT1("FIXME: Need to add index allocation\n"); return STATUS_NOT_IMPLEMENTED; } - - Status = UpdateIndexNode(DeviceExt, FileRecord, CurrentKey->LesserChild, IndexBufferSize, IndexAllocationContext, IndexAllocationOffset, BitmapContext); - if (!NT_SUCCESS(Status)) - { - DPRINT1("ERROR: Failed to update index node!\n"); - ReleaseAttributeContext(IndexAllocationContext); - return Status; - } // Is the Index Entry large enough to store the VCN? if (!CurrentKey->IndexEntry->Flags & NTFS_INDEX_ENTRY_NODE) @@ -1056,9 +1121,17 @@ UpdateIndexAllocation(PDEVICE_EXTENSION DeviceExt, CurrentKey->IndexEntry->Flags |= NTFS_INDEX_ENTRY_NODE; } - // Update the VCN stored in the index entry of CurrentKey - SetIndexEntryVCN(CurrentKey->IndexEntry, CurrentKey->LesserChild->NodeNumber); + // Update the sub-node + Status = UpdateIndexNode(DeviceExt, FileRecord, CurrentKey->LesserChild, IndexBufferSize, IndexAllocationContext, IndexAllocationOffset, BitmapContext); + if (!NT_SUCCESS(Status)) + { + DPRINT1("ERROR: Failed to update index node!\n"); + ReleaseAttributeContext(IndexAllocationContext); + return Status; + } + // Update the VCN stored in the index entry of CurrentKey + SetIndexEntryVCN(CurrentKey->IndexEntry, CurrentKey->LesserChild->VCN); } CurrentKey = CurrentKey->NextKey; } @@ -1096,7 +1169,7 @@ UpdateIndexNode(PDEVICE_EXTENSION DeviceExt, IndexAllocationContext, IndexAllocationOffset, BitmapContext, - Node->NodeNumber); + Node->VCN); // Do we need to write this node to disk? if (Node->DiskNeedsUpdating) @@ -1106,7 +1179,7 @@ UpdateIndexNode(PDEVICE_EXTENSION DeviceExt, PINDEX_BUFFER IndexBuffer; // Does the node need to be assigned a VCN? - if (!Node->ExistsOnDisk) + if (!Node->HasValidVCN) { // Allocate the node Status = AllocateIndexNode(DeviceExt, @@ -1114,14 +1187,14 @@ UpdateIndexNode(PDEVICE_EXTENSION DeviceExt, IndexBufferSize, IndexAllocationContext, IndexAllocationOffset, - &Node->NodeNumber); + &Node->VCN); if (!NT_SUCCESS(Status)) { DPRINT1("ERROR: Failed to allocate index record in index allocation!\n"); return Status; } - Node->ExistsOnDisk = TRUE; + Node->HasValidVCN = TRUE; } // Allocate memory for an index buffer @@ -1142,7 +1215,7 @@ UpdateIndexNode(PDEVICE_EXTENSION DeviceExt, } // Get Offset of index buffer in index allocation - NodeOffset = GetAllocationOffsetFromVCN(DeviceExt, IndexBufferSize, Node->NodeNumber); + NodeOffset = GetAllocationOffsetFromVCN(DeviceExt, IndexBufferSize, Node->VCN); // Write the buffer to the index allocation Status = WriteAttribute(DeviceExt, IndexAllocationContext, NodeOffset, (const PUCHAR)IndexBuffer, IndexBufferSize, &LengthWritten, FileRecord); @@ -1274,7 +1347,7 @@ DestroyBTree(PB_TREE Tree) } VOID -DumpBTreeKey(PB_TREE_KEY Key, ULONG Number, ULONG Depth) +DumpBTreeKey(PB_TREE Tree, PB_TREE_KEY Key, ULONG Number, ULONG Depth) { ULONG i; for (i = 0; i < Depth; i++) @@ -1298,7 +1371,7 @@ DumpBTreeKey(PB_TREE_KEY Key, ULONG Number, ULONG Depth) if (Key->IndexEntry->Flags & NTFS_INDEX_ENTRY_NODE) { if (Key->LesserChild) - DumpBTreeNode(Key->LesserChild, Number, Depth + 1); + DumpBTreeNode(Tree, Key->LesserChild, Number, Depth + 1); else { // This will be an assert once nodes with arbitrary depth are debugged @@ -1308,18 +1381,28 @@ DumpBTreeKey(PB_TREE_KEY Key, ULONG Number, ULONG Depth) } VOID -DumpBTreeNode(PB_TREE_FILENAME_NODE Node, ULONG Number, ULONG Depth) +DumpBTreeNode(PB_TREE Tree, + PB_TREE_FILENAME_NODE Node, + ULONG Number, + ULONG Depth) { PB_TREE_KEY CurrentKey; ULONG i; for (i = 0; i < Depth; i++) DbgPrint(" "); - DbgPrint("Node #%d, Depth %d, has %d key%s\n", Number, Depth, Node->KeyCount, Node->KeyCount == 1 ? "" : "s"); + DbgPrint("Node #%d, Depth %d, has %d key%s", Number, Depth, Node->KeyCount, Node->KeyCount == 1 ? "" : "s"); + + if (Node->HasValidVCN) + DbgPrint(" VCN: %I64u\n", Node->VCN); + else if (Tree->RootNode == Node) + DbgPrint(" Index Root"); + else + DbgPrint(" NOT ASSIGNED VCN YET\n"); CurrentKey = Node->FirstKey; - for (i = 1; i <= Node->KeyCount; i++) + for (i = 0; i < Node->KeyCount; i++) { - DumpBTreeKey(CurrentKey, i, Depth); + DumpBTreeKey(Tree, CurrentKey, i, Depth); CurrentKey = CurrentKey->NextKey; } } @@ -1340,7 +1423,7 @@ VOID DumpBTree(PB_TREE Tree) { DbgPrint("B_TREE @ %p\n", Tree); - DumpBTreeNode(Tree->RootNode, 0, 0); + DumpBTreeNode(Tree, Tree->RootNode, 0, 0); } // Calculates start of Index Buffer relative to the index allocation, given the node's VCN @@ -1525,7 +1608,6 @@ NtfsInsertKey(PB_TREE Tree, NewIndexRoot->FirstKey = DummyKey; NewIndexRoot->KeyCount = 1; NewIndexRoot->DiskNeedsUpdating = TRUE; - NewIndexRoot->ExistsOnDisk = TRUE; // Make the new node the Tree's root node Tree->RootNode = NewIndexRoot; diff --git a/drivers/filesystems/ntfs/create.c b/drivers/filesystems/ntfs/create.c index e8d0b1eb14..55e1e95a38 100644 --- a/drivers/filesystems/ntfs/create.c +++ b/drivers/filesystems/ntfs/create.c @@ -569,25 +569,31 @@ NtfsCreateFile(PDEVICE_OBJECT DeviceObject, return STATUS_ACCESS_DENIED; } - // We can't create directories yet + // Was the user trying to create a directory? if (RequestedOptions & FILE_DIRECTORY_FILE) { - DPRINT1("FIXME: Folder creation is still TODO!\n"); - return STATUS_NOT_IMPLEMENTED; + // Create the directory on disk + Status = NtfsCreateDirectory(DeviceExt, + FileObject, + BooleanFlagOn(Stack->Flags, SL_CASE_SENSITIVE), + BooleanFlagOn(IrpContext->Flags, IRPCONTEXT_CANWAIT)); + } + else + { + // Create the file record on disk + Status = NtfsCreateFileRecord(DeviceExt, + FileObject, + BooleanFlagOn(Stack->Flags, SL_CASE_SENSITIVE), + BooleanFlagOn(IrpContext->Flags, IRPCONTEXT_CANWAIT)); } - // Create the file record on disk - Status = NtfsCreateFileRecord(DeviceExt, - FileObject, - BooleanFlagOn(Stack->Flags, SL_CASE_SENSITIVE), - BooleanFlagOn(IrpContext->Flags,IRPCONTEXT_CANWAIT)); if (!NT_SUCCESS(Status)) { DPRINT1("ERROR: Couldn't create file record!\n"); return Status; } - // Before we open the file we just created, we need to change the disposition (upper 8 bits of ULONG) + // Before we open the file/directory we just created, we need to change the disposition (upper 8 bits of ULONG) // from create to open, since we already created the file Stack->Parameters.Create.Options = (ULONG)FILE_OPEN << 24 | RequestedOptions; @@ -651,40 +657,48 @@ NtfsCreate(PNTFS_IRP_CONTEXT IrpContext) } /** -* @name NtfsCreateFileRecord() +* @name NtfsCreateDirectory() * @implemented * -* Creates a file record and saves it to the MFT. Adds the filename attribute of the -* created file to the parent directory's index. +* Creates a file record for a new directory and saves it to the MFT. Adds the filename attribute of the +* created directory to the parent directory's index. * * @param DeviceExt * Points to the target disk's DEVICE_EXTENSION * * @param FileObject -* Pointer to a FILE_OBJECT describing the file to be created +* Pointer to a FILE_OBJECT describing the directory to be created +* +* @param CaseSensitive +* Boolean indicating if the function should operate in case-sensitive mode. This will be TRUE +* if an application created the folder with the FILE_FLAG_POSIX_SEMANTICS flag. * * @param CanWait * Boolean indicating if the function is allowed to wait for exclusive access to the master file table. * This will only be relevant if the MFT doesn't have any free file records and needs to be enlarged. -* +* * @return -* STATUS_SUCCESS on success. +* STATUS_SUCCESS on success. * STATUS_INSUFFICIENT_RESOURCES if unable to allocate memory for the file record. -* STATUS_CANT_WAIT if CanWait was FALSE and the function needed to resize the MFT but +* STATUS_CANT_WAIT if CanWait was FALSE and the function needed to resize the MFT but * couldn't get immediate, exclusive access to it. */ NTSTATUS -NtfsCreateFileRecord(PDEVICE_EXTENSION DeviceExt, - PFILE_OBJECT FileObject, - BOOLEAN CaseSensitive, - BOOLEAN CanWait) +NtfsCreateDirectory(PDEVICE_EXTENSION DeviceExt, + PFILE_OBJECT FileObject, + BOOLEAN CaseSensitive, + BOOLEAN CanWait) { + NTSTATUS Status = STATUS_SUCCESS; PFILE_RECORD_HEADER FileRecord; PNTFS_ATTR_RECORD NextAttribute; PFILENAME_ATTRIBUTE FilenameAttribute; ULONGLONG ParentMftIndex; ULONGLONG FileMftIndex; + PB_TREE Tree; + PINDEX_ROOT_ATTRIBUTE NewIndexRoot; + ULONG RootLength; DPRINT1("NtfsCreateFileRecord(%p, %p, %s, %s)\n", DeviceExt, @@ -692,6 +706,126 @@ NtfsCreateFileRecord(PDEVICE_EXTENSION DeviceExt, CaseSensitive ? "TRUE" : "FALSE", CanWait ? "TRUE" : "FALSE"); + // Start with an empty file record + FileRecord = NtfsCreateEmptyFileRecord(DeviceExt); + if (!FileRecord) + { + DPRINT1("ERROR: Unable to allocate memory for file record!\n"); + return STATUS_INSUFFICIENT_RESOURCES; + } + + // Set the directory flag + FileRecord->Flags |= FRH_DIRECTORY; + + // find where the first attribute will be added + NextAttribute = (PNTFS_ATTR_RECORD)((ULONG_PTR)FileRecord + FileRecord->AttributeOffset); + + // add first attribute, $STANDARD_INFORMATION + AddStandardInformation(FileRecord, NextAttribute); + + // advance NextAttribute pointer to the next attribute + NextAttribute = (PNTFS_ATTR_RECORD)((ULONG_PTR)NextAttribute + (ULONG_PTR)NextAttribute->Length); + + // Add the $FILE_NAME attribute + AddFileName(FileRecord, NextAttribute, DeviceExt, FileObject, CaseSensitive, &ParentMftIndex); + + // save a pointer to the filename attribute + FilenameAttribute = (PFILENAME_ATTRIBUTE)((ULONG_PTR)NextAttribute + NextAttribute->Resident.ValueOffset); + + // advance NextAttribute pointer to the next attribute + NextAttribute = (PNTFS_ATTR_RECORD)((ULONG_PTR)NextAttribute + (ULONG_PTR)NextAttribute->Length); + + // Create an empty b-tree to represent our new index + Status = CreateEmptyBTree(&Tree); + if (!NT_SUCCESS(Status)) + { + DPRINT1("ERROR: Failed to create empty B-Tree!\n"); + ExFreePoolWithTag(FileRecord, TAG_NTFS); + return Status; + } + + // Calculate maximum size of index root + ULONG MaxIndexRootSize = DeviceExt->NtfsInfo.BytesPerFileRecord + - ((ULONG_PTR)NextAttribute - (ULONG_PTR)FileRecord) + - sizeof(ULONG) * 2; + + // Create a new index record from the tree + Status = CreateIndexRootFromBTree(DeviceExt, + Tree, + MaxIndexRootSize, + &NewIndexRoot, + &RootLength); + if (!NT_SUCCESS(Status)) + { + DPRINT1("ERROR: Unable to create empty index root!\n"); + DestroyBTree(Tree); + ExFreePoolWithTag(FileRecord, TAG_NTFS); + return Status; + } + + // We're done with the B-Tree + DestroyBTree(Tree); + + // add the $INDEX_ROOT attribute + Status = AddIndexRoot(DeviceExt, FileRecord, NextAttribute, NewIndexRoot, RootLength, L"$I30", 4); + if (!NT_SUCCESS(Status)) + { + DPRINT1("ERROR: Failed to add index root to new file record!\n"); + ExFreePoolWithTag(FileRecord, TAG_NTFS); + return Status; + } + + +#ifndef NDEBUG + NtfsDumpFileRecord(DeviceExt, FileRecord); +#endif + + // Now that we've built the file record in memory, we need to store it in the MFT. + Status = AddNewMftEntry(FileRecord, DeviceExt, &FileMftIndex, CanWait); + if (NT_SUCCESS(Status)) + { + // The highest 2 bytes should be the sequence number, unless the parent happens to be root + if (FileMftIndex == NTFS_FILE_ROOT) + FileMftIndex = FileMftIndex + ((ULONGLONG)NTFS_FILE_ROOT << 48); + else + FileMftIndex = FileMftIndex + ((ULONGLONG)FileRecord->SequenceNumber << 48); + + DPRINT1("New File Reference: 0x%016I64x\n", FileMftIndex); + + // Add the filename attribute to the filename-index of the parent directory + Status = NtfsAddFilenameToDirectory(DeviceExt, + ParentMftIndex, + FileMftIndex, + FilenameAttribute, + CaseSensitive); + } + + ExFreePoolWithTag(NewIndexRoot, TAG_NTFS); + ExFreePoolWithTag(FileRecord, TAG_NTFS); + + return Status; +} + +/** +* @name NtfsCreateEmptyFileRecord +* @implemented +* +* Creates a new, empty file record, with no attributes. +* +* @param DeviceExt +* Pointer to the DEVICE_EXTENSION of the target volume the file record will be stored on. +* +* @return +* A pointer to the newly-created FILE_RECORD_HEADER if the function succeeds, NULL otherwise. +*/ +PFILE_RECORD_HEADER +NtfsCreateEmptyFileRecord(PDEVICE_EXTENSION DeviceExt) +{ + PFILE_RECORD_HEADER FileRecord; + PNTFS_ATTR_RECORD NextAttribute; + + DPRINT1("NtfsCreateEmptyFileRecord(%p)\n", DeviceExt); + // allocate memory for file record FileRecord = ExAllocatePoolWithTag(NonPagedPool, DeviceExt->NtfsInfo.BytesPerFileRecord, @@ -699,7 +833,7 @@ NtfsCreateFileRecord(PDEVICE_EXTENSION DeviceExt, if (!FileRecord) { DPRINT1("ERROR: Unable to allocate memory for file record!\n"); - return STATUS_INSUFFICIENT_RESOURCES; + return NULL; } RtlZeroMemory(FileRecord, DeviceExt->NtfsInfo.BytesPerFileRecord); @@ -719,7 +853,7 @@ NtfsCreateFileRecord(PDEVICE_EXTENSION DeviceExt, FileRecord->AttributeOffset = ALIGN_UP_BY(FileRecord->AttributeOffset, ATTR_RECORD_ALIGNMENT); FileRecord->Flags = FRH_IN_USE; FileRecord->BytesInUse = FileRecord->AttributeOffset + sizeof(ULONG) * 2; - + // find where the first attribute will be added NextAttribute = (PNTFS_ATTR_RECORD)((ULONG_PTR)FileRecord + FileRecord->AttributeOffset); @@ -727,9 +861,66 @@ NtfsCreateFileRecord(PDEVICE_EXTENSION DeviceExt, NextAttribute->Type = AttributeEnd; NextAttribute->Length = FILE_RECORD_END; + return FileRecord; +} + + +/** +* @name NtfsCreateFileRecord() +* @implemented +* +* Creates a file record and saves it to the MFT. Adds the filename attribute of the +* created file to the parent directory's index. +* +* @param DeviceExt +* Points to the target disk's DEVICE_EXTENSION +* +* @param FileObject +* Pointer to a FILE_OBJECT describing the file to be created +* +* @param CanWait +* Boolean indicating if the function is allowed to wait for exclusive access to the master file table. +* This will only be relevant if the MFT doesn't have any free file records and needs to be enlarged. +* +* @return +* STATUS_SUCCESS on success. +* STATUS_INSUFFICIENT_RESOURCES if unable to allocate memory for the file record. +* STATUS_CANT_WAIT if CanWait was FALSE and the function needed to resize the MFT but +* couldn't get immediate, exclusive access to it. +*/ +NTSTATUS +NtfsCreateFileRecord(PDEVICE_EXTENSION DeviceExt, + PFILE_OBJECT FileObject, + BOOLEAN CaseSensitive, + BOOLEAN CanWait) +{ + NTSTATUS Status = STATUS_SUCCESS; + PFILE_RECORD_HEADER FileRecord; + PNTFS_ATTR_RECORD NextAttribute; + PFILENAME_ATTRIBUTE FilenameAttribute; + ULONGLONG ParentMftIndex; + ULONGLONG FileMftIndex; + + DPRINT1("NtfsCreateFileRecord(%p, %p, %s, %s)\n", + DeviceExt, + FileObject, + CaseSensitive ? "TRUE" : "FALSE", + CanWait ? "TRUE" : "FALSE"); + + // allocate memory for file record + FileRecord = NtfsCreateEmptyFileRecord(DeviceExt); + if (!FileRecord) + { + DPRINT1("ERROR: Unable to allocate memory for file record!\n"); + return STATUS_INSUFFICIENT_RESOURCES; + } + + // find where the first attribute will be added + NextAttribute = (PNTFS_ATTR_RECORD)((ULONG_PTR)FileRecord + FileRecord->AttributeOffset); + // add first attribute, $STANDARD_INFORMATION AddStandardInformation(FileRecord, NextAttribute); - + // advance NextAttribute pointer to the next attribute NextAttribute = (PNTFS_ATTR_RECORD)((ULONG_PTR)NextAttribute + (ULONG_PTR)NextAttribute->Length); @@ -745,8 +936,10 @@ NtfsCreateFileRecord(PDEVICE_EXTENSION DeviceExt, // add the $DATA attribute AddData(FileRecord, NextAttribute); +#ifndef NDEBUG // dump file record in memory (for debugging) NtfsDumpFileRecord(DeviceExt, FileRecord); +#endif // Now that we've built the file record in memory, we need to store it in the MFT. Status = AddNewMftEntry(FileRecord, DeviceExt, &FileMftIndex, CanWait); diff --git a/drivers/filesystems/ntfs/mft.c b/drivers/filesystems/ntfs/mft.c index 0cd2767efb..7d0157a761 100644 --- a/drivers/filesystems/ntfs/mft.c +++ b/drivers/filesystems/ntfs/mft.c @@ -1893,6 +1893,7 @@ AddNewMftEntry(PFILE_RECORD_HEADER FileRecord, ULONGLONG BitmapDataSize; ULONGLONG AttrBytesRead; PUCHAR BitmapData; + PUCHAR BitmapBuffer; ULONG LengthWritten; PNTFS_ATTR_CONTEXT BitmapContext; LARGE_INTEGER BitmapBits; @@ -1901,6 +1902,8 @@ AddNewMftEntry(PFILE_RECORD_HEADER FileRecord, DPRINT1("AddNewMftEntry(%p, %p, %p, %s)\n", FileRecord, DeviceExt, DestinationIndex, CanWait ? "TRUE" : "FALSE"); // First, we have to read the mft's $Bitmap attribute + + // Find the attribute Status = FindAttribute(DeviceExt, DeviceExt->MasterFileTable, AttributeBitmap, L"", 0, &BitmapContext, NULL); if (!NT_SUCCESS(Status)) { @@ -1908,22 +1911,28 @@ AddNewMftEntry(PFILE_RECORD_HEADER FileRecord, return Status; } - // allocate a buffer for the $Bitmap attribute + // Get size of bitmap BitmapDataSize = AttributeDataLength(BitmapContext->pRecord); - BitmapData = ExAllocatePoolWithTag(NonPagedPool, BitmapDataSize, TAG_NTFS); - if (!BitmapData) + + // RtlInitializeBitmap wants a ULONG-aligned pointer, and wants the memory passed to it to be a ULONG-multiple + // Allocate a buffer for the $Bitmap attribute plus enough to ensure we can get a ULONG-aligned pointer + BitmapBuffer = ExAllocatePoolWithTag(NonPagedPool, BitmapDataSize + sizeof(ULONG), TAG_NTFS); + if (!BitmapBuffer) { ReleaseAttributeContext(BitmapContext); return STATUS_INSUFFICIENT_RESOURCES; } + // Get a ULONG-aligned pointer for the bitmap itself + BitmapData = (PUCHAR)ALIGN_UP_BY((ULONG_PTR)BitmapBuffer, sizeof(ULONG)); + // read $Bitmap attribute AttrBytesRead = ReadAttribute(DeviceExt, BitmapContext, 0, (PCHAR)BitmapData, BitmapDataSize); - if (AttrBytesRead == 0) + if (AttrBytesRead != BitmapDataSize) { DPRINT1("ERROR: Unable to read $Bitmap attribute of master file table!\n"); - ExFreePoolWithTag(BitmapData, TAG_NTFS); + ExFreePoolWithTag(BitmapBuffer, TAG_NTFS); ReleaseAttributeContext(BitmapContext); return STATUS_OBJECT_NAME_NOT_FOUND; } @@ -1939,7 +1948,8 @@ AddNewMftEntry(PFILE_RECORD_HEADER FileRecord, if (BitmapBits.HighPart != 0) { DPRINT1("\tFIXME: bitmap sizes beyond 32bits are not yet supported! (Your NTFS volume is too large)\n"); - ExFreePoolWithTag(BitmapData, TAG_NTFS); + NtfsGlobalData->EnableWriteSupport = FALSE; + ExFreePoolWithTag(BitmapBuffer, TAG_NTFS); ReleaseAttributeContext(BitmapContext); return STATUS_NOT_IMPLEMENTED; } @@ -1953,7 +1963,7 @@ AddNewMftEntry(PFILE_RECORD_HEADER FileRecord, { DPRINT1("Couldn't find free space in MFT for file record, increasing MFT size.\n"); - ExFreePoolWithTag(BitmapData, TAG_NTFS); + ExFreePoolWithTag(BitmapBuffer, TAG_NTFS); ReleaseAttributeContext(BitmapContext); // Couldn't find a free record in the MFT, add some blank records and try again @@ -1982,7 +1992,7 @@ AddNewMftEntry(PFILE_RECORD_HEADER FileRecord, if (!NT_SUCCESS(Status)) { DPRINT1("ERROR encountered when writing $Bitmap attribute!\n"); - ExFreePoolWithTag(BitmapData, TAG_NTFS); + ExFreePoolWithTag(BitmapBuffer, TAG_NTFS); ReleaseAttributeContext(BitmapContext); return Status; } @@ -1993,14 +2003,14 @@ AddNewMftEntry(PFILE_RECORD_HEADER FileRecord, if (!NT_SUCCESS(Status)) { DPRINT1("ERROR: Unable to write file record!\n"); - ExFreePoolWithTag(BitmapData, TAG_NTFS); + ExFreePoolWithTag(BitmapBuffer, TAG_NTFS); ReleaseAttributeContext(BitmapContext); return Status; } *DestinationIndex = MftIndex; - ExFreePoolWithTag(BitmapData, TAG_NTFS); + ExFreePoolWithTag(BitmapBuffer, TAG_NTFS); ReleaseAttributeContext(BitmapContext); return Status; @@ -2255,7 +2265,7 @@ NtfsAddFilenameToDirectory(PDEVICE_EXTENSION DeviceExt, AttributeLength, &LengthWritten, ParentFileRecord); - if (!NT_SUCCESS(Status)) + if (!NT_SUCCESS(Status) || LengthWritten != AttributeLength) { DPRINT1("ERROR: Unable to write new index root attribute to parent directory!\n"); ExFreePoolWithTag(NewIndexRoot, TAG_NTFS); diff --git a/drivers/filesystems/ntfs/ntfs.h b/drivers/filesystems/ntfs/ntfs.h index 030b777c22..abd2d2791d 100644 --- a/drivers/filesystems/ntfs/ntfs.h +++ b/drivers/filesystems/ntfs/ntfs.h @@ -304,6 +304,12 @@ typedef struct // relative to the beginning of the file record. #define ATTR_RECORD_ALIGNMENT 8 +// Data runs are aligned to a 4-byte boundary, relative to the start of the attribute record +#define DATA_RUN_ALIGNMENT 4 + +// Value offset is aligned to a 4-byte boundary, relative to the start of the attribute record +#define VALUE_OFFSET_ALIGNMENT 4 + typedef struct { ULONGLONG CreationTime; @@ -423,9 +429,9 @@ typedef struct _B_TREE_KEY typedef struct _B_TREE_FILENAME_NODE { ULONG KeyCount; - BOOLEAN ExistsOnDisk; + BOOLEAN HasValidVCN; BOOLEAN DiskNeedsUpdating; - ULONGLONG NodeNumber; + ULONGLONG VCN; PB_TREE_KEY FirstKey; } B_TREE_FILENAME_NODE, *PB_TREE_FILENAME_NODE; @@ -570,6 +576,15 @@ AddRun(PNTFS_VCB Vcb, ULONGLONG NextAssignedCluster, ULONG RunLength); +NTSTATUS +AddIndexRoot(PNTFS_VCB Vcb, + PFILE_RECORD_HEADER FileRecord, + PNTFS_ATTR_RECORD AttributeAddress, + PINDEX_ROOT_ATTRIBUTE NewIndexRoot, + ULONG RootLength, + PCWSTR Name, + USHORT NameLength); + NTSTATUS AddFileName(PFILE_RECORD_HEADER FileRecord, PNTFS_ATTR_RECORD AttributeAddress, @@ -718,10 +733,20 @@ VOID DumpBTree(PB_TREE Tree); VOID -DumpBTreeNode(PB_TREE_FILENAME_NODE Node, +DumpBTreeKey(PB_TREE Tree, + PB_TREE_KEY Key, + ULONG Number, + ULONG Depth); + +VOID +DumpBTreeNode(PB_TREE Tree, + PB_TREE_FILENAME_NODE Node, ULONG Number, ULONG Depth); +NTSTATUS +CreateEmptyBTree(PB_TREE *NewTree); + ULONGLONG GetAllocationOffsetFromVCN(PDEVICE_EXTENSION DeviceExt, ULONG IndexBufferSize, @@ -771,6 +796,15 @@ NtfsClose(PNTFS_IRP_CONTEXT IrpContext); NTSTATUS NtfsCreate(PNTFS_IRP_CONTEXT IrpContext); +NTSTATUS +NtfsCreateDirectory(PDEVICE_EXTENSION DeviceExt, + PFILE_OBJECT FileObject, + BOOLEAN CaseSensitive, + BOOLEAN CanWait); + +PFILE_RECORD_HEADER +NtfsCreateEmptyFileRecord(PDEVICE_EXTENSION DeviceExt); + NTSTATUS NtfsCreateFileRecord(PDEVICE_EXTENSION DeviceExt, PFILE_OBJECT FileObject,

6 years, 9 months

[reactos] 64/72: [NTFS] - When creating files: -Don't add a preceding backslash when creating files on root. -Use NTFS_FILE_NAME_POSIX name type if CaseSensitive option is specified. -Don't try to create a file when a folder is requested (folder creation is still TODO).

by Trevor Thompson

https://git.reactos.org/?p=reactos.git;a=commitdiff;h=c63e7e54b5a1808d7f126… commit c63e7e54b5a1808d7f126911d75ac996dbb8093c Author: Trevor Thompson <tmt256(a)email.vccs.edu> AuthorDate: Fri Aug 25 17:16:04 2017 +0000 [NTFS] - When creating files: -Don't add a preceding backslash when creating files on root. -Use NTFS_FILE_NAME_POSIX name type if CaseSensitive option is specified. -Don't try to create a file when a folder is requested (folder creation is still TODO). svn path=/branches/GSoC_2016/NTFS/; revision=75671 --- drivers/filesystems/ntfs/attrib.c | 8 ++++---- drivers/filesystems/ntfs/create.c | 7 +++++++ 2 files changed, 11 insertions(+), 4 deletions(-) diff --git a/drivers/filesystems/ntfs/attrib.c b/drivers/filesystems/ntfs/attrib.c index e6d3483553..e830264ad6 100644 --- a/drivers/filesystems/ntfs/attrib.c +++ b/drivers/filesystems/ntfs/attrib.c @@ -172,11 +172,11 @@ AddFileName(PFILE_RECORD_HEADER FileRecord, // we need to extract the filename from the path DPRINT1("Pathname: %wZ\n", &FileObject->FileName); - FilenameNoPath.Buffer = FileObject->FileName.Buffer; - FilenameNoPath.MaximumLength = FilenameNoPath.Length = FileObject->FileName.Length; - FsRtlDissectName(FileObject->FileName, &Current, &Remaining); + FilenameNoPath.Buffer = Current.Buffer; + FilenameNoPath.MaximumLength = FilenameNoPath.Length = Current.Length; + while (Current.Length != 0) { DPRINT1("Current: %wZ\n", &Current); @@ -232,7 +232,7 @@ AddFileName(PFILE_RECORD_HEADER FileRecord, // For now, we're emulating the way Windows behaves when 8.3 name generation is disabled // TODO: add DOS Filename as needed - if (RtlIsNameLegalDOS8Dot3(&FilenameNoPath, NULL, NULL)) + if (!CaseSensitive && RtlIsNameLegalDOS8Dot3(&FilenameNoPath, NULL, NULL)) FileNameAttribute->NameType = NTFS_FILE_NAME_WIN32_AND_DOS; else FileNameAttribute->NameType = NTFS_FILE_NAME_POSIX; diff --git a/drivers/filesystems/ntfs/create.c b/drivers/filesystems/ntfs/create.c index a98afc67b7..e8d0b1eb14 100644 --- a/drivers/filesystems/ntfs/create.c +++ b/drivers/filesystems/ntfs/create.c @@ -569,6 +569,13 @@ NtfsCreateFile(PDEVICE_OBJECT DeviceObject, return STATUS_ACCESS_DENIED; } + // We can't create directories yet + if (RequestedOptions & FILE_DIRECTORY_FILE) + { + DPRINT1("FIXME: Folder creation is still TODO!\n"); + return STATUS_NOT_IMPLEMENTED; + } + // Create the file record on disk Status = NtfsCreateFileRecord(DeviceExt, FileObject,

6 years, 9 months

← Newer
1
...
18
19
20
21
22
23
24
...
36
Older →

Jump to page:

2024

2023

2022

2021

2020

2019

2018

2017

2016

2015

2014

2013

2012

2011

2010

2009

2008

2007

2006

2005

2004

Ros-diffs December 2017