drivers/filesystems/ntfs/mft.c

   1 /*
   2  *  ReactOS kernel
   3  *  Copyright (C) 2002, 2014 ReactOS Team
   4  *
   5  *  This program is free software; you can redistribute it and/or modify
   6  *  it under the terms of the GNU General Public License as published by
   7  *  the Free Software Foundation; either version 2 of the License, or
   8  *  (at your option) any later version.
   9  *
  10  *  This program is distributed in the hope that it will be useful,
  11  *  but WITHOUT ANY WARRANTY; without even the implied warranty of
  12  *  MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
  13  *  GNU General Public License for more details.
  14  *
  15  *  You should have received a copy of the GNU General Public License
  16  *  along with this program; if not, write to the Free Software
  17  *  Foundation, Inc., 51 Franklin St, Fifth Floor, Boston, MA 02110-1301, USA.
  18  *
  19  * COPYRIGHT:        See COPYING in the top level directory
  20  * PROJECT:          ReactOS kernel
  21  * FILE:             drivers/filesystem/ntfs/mft.c
  22  * PURPOSE:          NTFS filesystem driver
  23  * PROGRAMMERS:      Eric Kohl
  24  *                   Valentin Verkhovsky
  25  *                   Pierre Schweitzer (pierre@reactos.org)
  26  *                   Hervé Poussineau (hpoussin@reactos.org)
  27  *                   Trevor Thompson
  28  */
  29
  30 /* INCLUDES *****************************************************************/
  31
  32 #include "ntfs.h"
  33
  34 #define NDEBUG
  35 #include <debug.h>
  36
  37 /* FUNCTIONS ****************************************************************/
  38
  39 PNTFS_ATTR_CONTEXT
  40 PrepareAttributeContext(PNTFS_ATTR_RECORD AttrRecord)
  41 {
  42     PNTFS_ATTR_CONTEXT Context;
  43
  44     Context = ExAllocatePoolWithTag(NonPagedPool,
  45                                     FIELD_OFFSET(NTFS_ATTR_CONTEXT, Record) + AttrRecord->Length,
  46                                     TAG_NTFS);
  47     RtlCopyMemory(&Context->Record, AttrRecord, AttrRecord->Length);
  48     if (AttrRecord->IsNonResident)
  49     {
  50         LONGLONG DataRunOffset;
  51         ULONGLONG DataRunLength;
  52         ULONGLONG NextVBN = 0;
  53         PUCHAR DataRun = (PUCHAR)&Context->Record + Context->Record.NonResident.MappingPairsOffset;
  54
  55         Context->CacheRun = DataRun;
  56         Context->CacheRunOffset = 0;
  57         Context->CacheRun = DecodeRun(Context->CacheRun, &DataRunOffset, &DataRunLength);
  58         Context->CacheRunLength = DataRunLength;
  59         if (DataRunOffset != -1)
  60         {
  61             /* Normal run. */
  62             Context->CacheRunStartLCN =
  63             Context->CacheRunLastLCN = DataRunOffset;
  64         }
  65         else
  66         {
  67             /* Sparse run. */
  68             Context->CacheRunStartLCN = -1;
  69             Context->CacheRunLastLCN = 0;
  70         }
  71         Context->CacheRunCurrentOffset = 0;
  72
  73         // Convert the data runs to a map control block
  74         if (!NT_SUCCESS(ConvertDataRunsToLargeMCB(DataRun, &Context->DataRunsMCB, &NextVBN)))
  75         {
  76             DPRINT1("Unable to convert data runs to MCB!\n");
  77             ExFreePoolWithTag(Context, TAG_NTFS);
  78             return NULL;
  79         }
  80     }
  81
  82     return Context;
  83 }
  84
  85
  86 VOID
  87 ReleaseAttributeContext(PNTFS_ATTR_CONTEXT Context)
  88 {
  89     if (Context->Record.IsNonResident)
  90     {
  91         FsRtlUninitializeLargeMcb(&Context->DataRunsMCB);
  92     }
  93
  94     ExFreePoolWithTag(Context, TAG_NTFS);
  95 }
  96
  97
  98 /**
  99 * @name FindAttribute
 100 * @implemented
 101 *
 102 * Searches a file record for an attribute matching the given type and name.
 103 *
 104 * @param Offset
 105 * Optional pointer to a ULONG that will receive the offset of the found attribute
 106 * from the beginning of the record. Can be set to NULL.
 107 */
 108 NTSTATUS
 109 FindAttribute(PDEVICE_EXTENSION Vcb,
 110               PFILE_RECORD_HEADER MftRecord,
 111               ULONG Type,
 112               PCWSTR Name,
 113               ULONG NameLength,
 114               PNTFS_ATTR_CONTEXT * AttrCtx,
 115               PULONG Offset)
 116 {
 117     BOOLEAN Found;
 118     NTSTATUS Status;
 119     FIND_ATTR_CONTXT Context;
 120     PNTFS_ATTR_RECORD Attribute;
 121
 122     DPRINT("FindAttribute(%p, %p, 0x%x, %S, %u, %p)\n", Vcb, MftRecord, Type, Name, NameLength, AttrCtx);
 123
 124     Found = FALSE;
 125     Status = FindFirstAttribute(&Context, Vcb, MftRecord, FALSE, &Attribute);
 126     while (NT_SUCCESS(Status))
 127     {
 128         if (Attribute->Type == Type && Attribute->NameLength == NameLength)
 129         {
 130             if (NameLength != 0)
 131             {
 132                 PWCHAR AttrName;
 133
 134                 AttrName = (PWCHAR)((PCHAR)Attribute + Attribute->NameOffset);
 135                 DPRINT("%.*S, %.*S\n", Attribute->NameLength, AttrName, NameLength, Name);
 136                 if (RtlCompareMemory(AttrName, Name, NameLength << 1) == (NameLength << 1))
 137                 {
 138                     Found = TRUE;
 139                 }
 140             }
 141             else
 142             {
 143                 Found = TRUE;
 144             }
 145
 146             if (Found)
 147             {
 148                 /* Found it, fill up the context and return. */
 149                 DPRINT("Found context\n");
 150                 *AttrCtx = PrepareAttributeContext(Attribute);
 151
 152                 (*AttrCtx)->FileMFTIndex = MftRecord->MFTRecordNumber;
 153
 154                 if (Offset != NULL)
 155                     *Offset = Context.Offset;
 156
 157                 FindCloseAttribute(&Context);
 158                 return STATUS_SUCCESS;
 159             }
 160         }
 161
 162         Status = FindNextAttribute(&Context, &Attribute);
 163     }
 164
 165     FindCloseAttribute(&Context);
 166     return STATUS_OBJECT_NAME_NOT_FOUND;
 167 }
 168
 169
 170 ULONGLONG
 171 AttributeAllocatedLength(PNTFS_ATTR_RECORD AttrRecord)
 172 {
 173     if (AttrRecord->IsNonResident)
 174         return AttrRecord->NonResident.AllocatedSize;
 175     else
 176         return AttrRecord->Resident.ValueLength;
 177 }
 178
 179
 180 ULONGLONG
 181 AttributeDataLength(PNTFS_ATTR_RECORD AttrRecord)
 182 {
 183     if (AttrRecord->IsNonResident)
 184         return AttrRecord->NonResident.DataSize;
 185     else
 186         return AttrRecord->Resident.ValueLength;
 187 }
 188
 189 /**
 190 * @name IncreaseMftSize
 191 * @implemented
 192 *
 193 * Increases the size of the master file table on a volume, increasing the space available for file records.
 194 *
 195 * @param Vcb
 196 * Pointer to the VCB (DEVICE_EXTENSION) of the target volume.
 197 *
 198 * @return
 199 * STATUS_SUCCESS on success.
 200 * STATUS_INSUFFICIENT_RESOURCES if an allocation fails.
 201 * STATUS_INVALID_PARAMETER if there was an error reading the Mft's bitmap.
 202 *
 203 * @remarks
 204 * Increases the size of the Master File Table by 8 records. Bitmap entries for the new records are cleared,
 205 * and the bitmap is also enlarged if needed. Mimicking Windows' behavior when enlarging the mft is still TODO.
 206 * This function will wait for exlusive access to the volume fcb.
 207 */
 208 NTSTATUS
 209 IncreaseMftSize(PDEVICE_EXTENSION Vcb)
 210 {
 211     PNTFS_ATTR_CONTEXT BitmapContext;
 212     LARGE_INTEGER BitmapSize;
 213     LARGE_INTEGER DataSize;
 214     LONGLONG BitmapSizeDifference;
 215     ULONG DataSizeDifference = Vcb->NtfsInfo.BytesPerFileRecord * 8;
 216     ULONG BitmapOffset;
 217     PUCHAR BitmapBuffer;
 218     ULONGLONG BitmapBytes;
 219     ULONGLONG NewBitmapSize;
 220     ULONG BytesRead;
 221     ULONG LengthWritten;
 222     NTSTATUS Status;
 223
 224     DPRINT1("IncreaseMftSize(%p)\n", Vcb);
 225
 226     // We need exclusive access to the mft while we change its size
 227     if (!ExAcquireResourceExclusiveLite(&(Vcb->DirResource), TRUE))
 228     {
 229         return STATUS_CANT_WAIT;
 230     }
 231
 232     // Find the bitmap attribute of master file table
 233     Status = FindAttribute(Vcb, Vcb->MasterFileTable, AttributeBitmap, L"", 0, &BitmapContext, &BitmapOffset);
 234     if (!NT_SUCCESS(Status))
 235     {
 236         DPRINT1("ERROR: Couldn't find $BITMAP attribute of Mft!\n");
 237         ExReleaseResourceLite(&(Vcb->DirResource));
 238         return Status;
 239     }
 240
 241     // Get size of Bitmap Attribute
 242     BitmapSize.QuadPart = AttributeDataLength(&BitmapContext->Record);
 243
 244     // Calculate the new mft size
 245     DataSize.QuadPart = AttributeDataLength(&(Vcb->MFTContext->Record)) + DataSizeDifference;
 246
 247     // Determine how many bytes will make up the bitmap
 248     BitmapBytes = DataSize.QuadPart / Vcb->NtfsInfo.BytesPerFileRecord / 8;
 249
 250     // Determine how much we need to adjust the bitmap size (it's possible we don't)
 251     BitmapSizeDifference = BitmapBytes - BitmapSize.QuadPart;
 252     NewBitmapSize = max(BitmapSize.QuadPart + BitmapSizeDifference, BitmapSize.QuadPart);
 253
 254     // Allocate memory for the bitmap
 255     BitmapBuffer = ExAllocatePoolWithTag(NonPagedPool, NewBitmapSize, TAG_NTFS);
 256     if (!BitmapBuffer)
 257     {
 258         DPRINT1("ERROR: Unable to allocate memory for bitmap attribute!\n");
 259         ExReleaseResourceLite(&(Vcb->DirResource));
 260         ReleaseAttributeContext(BitmapContext);
 261         return STATUS_INSUFFICIENT_RESOURCES;
 262     }
 263
 264     // Zero the bytes we'll be adding
 265     RtlZeroMemory((PUCHAR)((ULONG_PTR)BitmapBuffer), NewBitmapSize);
 266
 267     // Read the bitmap attribute
 268     BytesRead = ReadAttribute(Vcb,
 269                               BitmapContext,
 270                               0,
 271                               (PCHAR)BitmapBuffer,
 272                               BitmapSize.LowPart);
 273     if (BytesRead != BitmapSize.LowPart)
 274     {
 275         DPRINT1("ERROR: Bytes read != Bitmap size!\n");
 276         ExReleaseResourceLite(&(Vcb->DirResource));
 277         ExFreePoolWithTag(BitmapBuffer, TAG_NTFS);
 278         ReleaseAttributeContext(BitmapContext);
 279         return STATUS_INVALID_PARAMETER;
 280     }
 281
 282     // Increase the mft size
 283     Status = SetNonResidentAttributeDataLength(Vcb, Vcb->MFTContext, Vcb->MftDataOffset, Vcb->MasterFileTable, &DataSize);
 284     if (!NT_SUCCESS(Status))
 285     {
 286         DPRINT1("ERROR: Failed to set size of $MFT data attribute!\n");
 287         ExReleaseResourceLite(&(Vcb->DirResource));
 288         ExFreePoolWithTag(BitmapBuffer, TAG_NTFS);
 289         ReleaseAttributeContext(BitmapContext);
 290         return Status;
 291     }
 292
 293     // If the bitmap grew
 294     if (BitmapSizeDifference > 0)
 295     {
 296         // Set the new bitmap size
 297         BitmapSize.QuadPart += BitmapSizeDifference;
 298         if (BitmapContext->Record.IsNonResident)
 299             Status = SetNonResidentAttributeDataLength(Vcb, BitmapContext, BitmapOffset, Vcb->MasterFileTable, &BitmapSize);
 300         else
 301             Status = SetResidentAttributeDataLength(Vcb, BitmapContext, BitmapOffset, Vcb->MasterFileTable, &BitmapSize);
 302
 303         if (!NT_SUCCESS(Status))
 304         {
 305             DPRINT1("ERROR: Failed to set size of bitmap attribute!\n");
 306             ExReleaseResourceLite(&(Vcb->DirResource));
 307             ExFreePoolWithTag(BitmapBuffer, TAG_NTFS);
 308             ReleaseAttributeContext(BitmapContext);
 309             return Status;
 310         }
 311     }
 312
 313     //NtfsDumpFileAttributes(Vcb, FileRecord);
 314
 315     // Update the file record with the new attribute sizes
 316     Status = UpdateFileRecord(Vcb, Vcb->VolumeFcb->MFTIndex, Vcb->MasterFileTable);
 317     if (!NT_SUCCESS(Status))
 318     {
 319         DPRINT1("ERROR: Failed to update $MFT file record!\n");
 320         ExReleaseResourceLite(&(Vcb->DirResource));
 321         ExFreePoolWithTag(BitmapBuffer, TAG_NTFS);
 322         ReleaseAttributeContext(BitmapContext);
 323         return Status;
 324     }
 325
 326     // Write out the new bitmap
 327     Status = WriteAttribute(Vcb, BitmapContext, BitmapOffset, BitmapBuffer, BitmapSize.LowPart, &LengthWritten);
 328     if (!NT_SUCCESS(Status))
 329     {
 330         ExReleaseResourceLite(&(Vcb->DirResource));
 331         ExFreePoolWithTag(BitmapBuffer, TAG_NTFS);
 332         ReleaseAttributeContext(BitmapContext);
 333         DPRINT1("ERROR: Couldn't write to bitmap attribute of $MFT!\n");
 334     }
 335
 336     // Cleanup
 337     ExReleaseResourceLite(&(Vcb->DirResource));
 338     ExFreePoolWithTag(BitmapBuffer, TAG_NTFS);
 339     ReleaseAttributeContext(BitmapContext);
 340
 341     return STATUS_SUCCESS;
 342 }
 343
 344 VOID
 345 InternalSetResidentAttributeLength(PNTFS_ATTR_CONTEXT AttrContext,
 346                                    PFILE_RECORD_HEADER FileRecord,
 347                                    ULONG AttrOffset,
 348                                    ULONG DataSize)
 349 {
 350     PNTFS_ATTR_RECORD Destination = (PNTFS_ATTR_RECORD)((ULONG_PTR)FileRecord + AttrOffset);
 351     ULONG NextAttributeOffset;
 352
 353     DPRINT("InternalSetResidentAttributeLength( %p, %p, %lu, %lu )\n", AttrContext, FileRecord, AttrOffset, DataSize);
 354
 355     // update ValueLength Field
 356     AttrContext->Record.Resident.ValueLength =
 357     Destination->Resident.ValueLength = DataSize;
 358
 359     // calculate the record length and end marker offset
 360     AttrContext->Record.Length =
 361     Destination->Length = DataSize + AttrContext->Record.Resident.ValueOffset;
 362     NextAttributeOffset = AttrOffset + AttrContext->Record.Length;
 363
 364     // Ensure NextAttributeOffset is aligned to an 8-byte boundary
 365     if (NextAttributeOffset % 8 != 0)
 366     {
 367         USHORT Padding = 8 - (NextAttributeOffset % 8);
 368         NextAttributeOffset += Padding;
 369         AttrContext->Record.Length += Padding;
 370         Destination->Length += Padding;
 371     }
 372
 373     // advance Destination to the final "attribute" and set the file record end
 374     Destination = (PNTFS_ATTR_RECORD)((ULONG_PTR)Destination + Destination->Length);
 375     SetFileRecordEnd(FileRecord, Destination, FILE_RECORD_END);
 376 }
 377
 378 /**
 379 *   @parameter FileRecord
 380 *   Pointer to a file record. Must be a full record at least
 381 *   Fcb->Vcb->NtfsInfo.BytesPerFileRecord bytes large, not just the header.
 382 */
 383 NTSTATUS
 384 SetAttributeDataLength(PFILE_OBJECT FileObject,
 385                        PNTFS_FCB Fcb,
 386                        PNTFS_ATTR_CONTEXT AttrContext,
 387                        ULONG AttrOffset,
 388                        PFILE_RECORD_HEADER FileRecord,
 389                        PLARGE_INTEGER DataSize)
 390 {
 391     NTSTATUS Status = STATUS_SUCCESS;
 392
 393     // are we truncating the file?
 394     if (DataSize->QuadPart < AttributeDataLength(&AttrContext->Record))
 395     {
 396         if (!MmCanFileBeTruncated(FileObject->SectionObjectPointer, DataSize))
 397         {
 398             DPRINT1("Can't truncate a memory-mapped file!\n");
 399             return STATUS_USER_MAPPED_FILE;
 400         }
 401     }
 402
 403     if (AttrContext->Record.IsNonResident)
 404     {
 405         Status = SetNonResidentAttributeDataLength(Fcb->Vcb,
 406                                                    AttrContext,
 407                                                    AttrOffset,
 408                                                    FileRecord,
 409                                                    DataSize);
 410     }
 411     else
 412     {
 413         // resident attribute
 414         Status = SetResidentAttributeDataLength(Fcb->Vcb,
 415                                                 AttrContext,
 416                                                 AttrOffset,
 417                                                 FileRecord,
 418                                                 DataSize);
 419     }
 420
 421     if (!NT_SUCCESS(Status))
 422     {
 423         DPRINT1("ERROR: Failed to set size of attribute!\n");
 424         return Status;
 425     }
 426
 427     //NtfsDumpFileAttributes(Fcb->Vcb, FileRecord);
 428
 429     // write the updated file record back to disk
 430     Status = UpdateFileRecord(Fcb->Vcb, Fcb->MFTIndex, FileRecord);
 431
 432     if (NT_SUCCESS(Status))
 433     {
 434         if(AttrContext->Record.IsNonResident)
 435             Fcb->RFCB.AllocationSize.QuadPart = AttrContext->Record.NonResident.AllocatedSize;
 436         else
 437             Fcb->RFCB.AllocationSize = *DataSize;
 438         Fcb->RFCB.FileSize = *DataSize;
 439         Fcb->RFCB.ValidDataLength = *DataSize;
 440         CcSetFileSizes(FileObject, (PCC_FILE_SIZES)&Fcb->RFCB.AllocationSize);
 441     }
 442
 443     return STATUS_SUCCESS;
 444 }
 445
 446 /**
 447 * @name SetFileRecordEnd
 448 * @implemented
 449 *
 450 * This small function sets a new endpoint for the file record. It set's the final
 451 * AttrEnd->Type to AttributeEnd and recalculates the bytes used by the file record.
 452 *
 453 * @param FileRecord
 454 * Pointer to the file record whose endpoint (length) will be set.
 455 *
 456 * @param AttrEnd
 457 * Pointer to section of memory that will receive the AttributeEnd marker. This must point
 458 * to memory allocated for the FileRecord. Must be aligned to an 8-byte boundary (relative to FileRecord).
 459 *
 460 * @param EndMarker
 461 * This value will be written after AttributeEnd but isn't critical at all. When Windows resizes
 462 * a file record, it preserves the final ULONG that previously ended the record, even though this
 463 * value is (to my knowledge) never used. We emulate this behavior.
 464 *
 465 */
 466 VOID
 467 SetFileRecordEnd(PFILE_RECORD_HEADER FileRecord,
 468                  PNTFS_ATTR_RECORD AttrEnd,
 469                  ULONG EndMarker)
 470 {
 471     // mark the end of attributes
 472     AttrEnd->Type = AttributeEnd;
 473
 474     // Restore the "file-record-end marker." The value is never checked but this behavior is consistent with Win2k3.
 475     AttrEnd->Length = EndMarker;
 476
 477     // recalculate bytes in use
 478     FileRecord->BytesInUse = (ULONG_PTR)AttrEnd - (ULONG_PTR)FileRecord + sizeof(ULONG) * 2;
 479 }
 480
 481 /**
 482 * @name SetNonResidentAttributeDataLength
 483 * @implemented
 484 *
 485 * Called by SetAttributeDataLength() to set the size of a non-resident attribute. Doesn't update the file record.
 486 *
 487 * @param Vcb
 488 * Pointer to a DEVICE_EXTENSION describing the target disk.
 489 *
 490 * @param AttrContext
 491 * PNTFS_ATTR_CONTEXT describing the location of the attribute whose size is being set.
 492 *
 493 * @param AttrOffset
 494 * Offset, from the beginning of the record, of the attribute being sized.
 495 *
 496 * @param FileRecord
 497 * Pointer to a file record containing the attribute to be resized. Must be a complete file record,
 498 * not just the header.
 499 *
 500 * @param DataSize
 501 * Pointer to a LARGE_INTEGER describing the new size of the attribute's data.
 502 *
 503 * @return
 504 * STATUS_SUCCESS on success;
 505 * STATUS_INSUFFICIENT_RESOURCES if an allocation fails.
 506 * STATUS_INVALID_PARAMETER if we can't find the last cluster in the data run.
 507 *
 508 * @remarks
 509 * Called by SetAttributeDataLength() and IncreaseMftSize(). Use SetAttributeDataLength() unless you have a good
 510 * reason to use this. Doesn't update the file record on disk. Doesn't inform the cache controller of changes with
 511 * any associated files. Synchronization is the callers responsibility.
 512 */
 513 NTSTATUS
 514 SetNonResidentAttributeDataLength(PDEVICE_EXTENSION Vcb,
 515                                   PNTFS_ATTR_CONTEXT AttrContext,
 516                                   ULONG AttrOffset,
 517                                   PFILE_RECORD_HEADER FileRecord,
 518                                   PLARGE_INTEGER DataSize)
 519 {
 520     NTSTATUS Status = STATUS_SUCCESS;
 521     ULONG BytesPerCluster = Vcb->NtfsInfo.BytesPerCluster;
 522     ULONGLONG AllocationSize = ROUND_UP(DataSize->QuadPart, BytesPerCluster);
 523     PNTFS_ATTR_RECORD DestinationAttribute = (PNTFS_ATTR_RECORD)((ULONG_PTR)FileRecord + AttrOffset);
 524     ULONG ExistingClusters = AttrContext->Record.NonResident.AllocatedSize / BytesPerCluster;
 525
 526     if (!AttrContext->Record.IsNonResident)
 527     {
 528         DPRINT1("ERROR: SetNonResidentAttributeDataLength() called for resident attribute!\n");
 529         return STATUS_INVALID_PARAMETER;
 530     }
 531
 532     // do we need to increase the allocation size?
 533     if (AttrContext->Record.NonResident.AllocatedSize < AllocationSize)
 534     {
 535         ULONG ClustersNeeded = (AllocationSize / BytesPerCluster) - ExistingClusters;
 536         LARGE_INTEGER LastClusterInDataRun;
 537         ULONG NextAssignedCluster;
 538         ULONG AssignedClusters;
 539
 540         if (ExistingClusters == 0)
 541         {
 542             LastClusterInDataRun.QuadPart = 0;
 543         }
 544         else
 545         {
 546             if (!FsRtlLookupLargeMcbEntry(&AttrContext->DataRunsMCB,
 547                                           (LONGLONG)AttrContext->Record.NonResident.HighestVCN,
 548                                           (PLONGLONG)&LastClusterInDataRun.QuadPart,
 549                                           NULL,
 550                                           NULL,
 551                                           NULL,
 552                                           NULL))
 553             {
 554                 DPRINT1("Error looking up final large MCB entry!\n");
 555
 556                 // Most likely, HighestVCN went above the largest mapping
 557                 DPRINT1("Highest VCN of record: %I64u\n", AttrContext->Record.NonResident.HighestVCN);
 558                 return STATUS_INVALID_PARAMETER;
 559             }
 560         }
 561
 562         DPRINT("LastClusterInDataRun: %I64u\n", LastClusterInDataRun.QuadPart);
 563         DPRINT("Highest VCN of record: %I64u\n", AttrContext->Record.NonResident.HighestVCN);
 564
 565         while (ClustersNeeded > 0)
 566         {
 567             Status = NtfsAllocateClusters(Vcb,
 568                                           LastClusterInDataRun.LowPart + 1,
 569                                           ClustersNeeded,
 570                                           &NextAssignedCluster,
 571                                           &AssignedClusters);
 572
 573             if (!NT_SUCCESS(Status))
 574             {
 575                 DPRINT1("Error: Unable to allocate requested clusters!\n");
 576                 return Status;
 577             }
 578
 579             // now we need to add the clusters we allocated to the data run
 580             Status = AddRun(Vcb, AttrContext, AttrOffset, FileRecord, NextAssignedCluster, AssignedClusters);
 581             if (!NT_SUCCESS(Status))
 582             {
 583                 DPRINT1("Error: Unable to add data run!\n");
 584                 return Status;
 585             }
 586
 587             ClustersNeeded -= AssignedClusters;
 588             LastClusterInDataRun.LowPart = NextAssignedCluster + AssignedClusters - 1;
 589         }
 590     }
 591     else if (AttrContext->Record.NonResident.AllocatedSize > AllocationSize)
 592     {
 593         // shrink allocation size
 594         ULONG ClustersToFree = ExistingClusters - (AllocationSize / BytesPerCluster);
 595         Status = FreeClusters(Vcb, AttrContext, AttrOffset, FileRecord, ClustersToFree);
 596     }
 597
 598     // TODO: is the file compressed, encrypted, or sparse?
 599
 600     AttrContext->Record.NonResident.AllocatedSize = AllocationSize;
 601     AttrContext->Record.NonResident.DataSize = DataSize->QuadPart;
 602     AttrContext->Record.NonResident.InitializedSize = DataSize->QuadPart;
 603
 604     DestinationAttribute->NonResident.AllocatedSize = AllocationSize;
 605     DestinationAttribute->NonResident.DataSize = DataSize->QuadPart;
 606     DestinationAttribute->NonResident.InitializedSize = DataSize->QuadPart;
 607
 608     DPRINT("Allocated Size: %I64u\n", DestinationAttribute->NonResident.AllocatedSize);
 609
 610     return Status;
 611 }
 612
 613 /**
 614 * @name SetResidentAttributeDataLength
 615 * @implemented
 616 *
 617 * Called by SetAttributeDataLength() to set the size of a non-resident attribute. Doesn't update the file record.
 618 *
 619 * @param Vcb
 620 * Pointer to a DEVICE_EXTENSION describing the target disk.
 621 *
 622 * @param AttrContext
 623 * PNTFS_ATTR_CONTEXT describing the location of the attribute whose size is being set.
 624 *
 625 * @param AttrOffset
 626 * Offset, from the beginning of the record, of the attribute being sized.
 627 *
 628 * @param FileRecord
 629 * Pointer to a file record containing the attribute to be resized. Must be a complete file record,
 630 * not just the header.
 631 *
 632 * @param DataSize
 633 * Pointer to a LARGE_INTEGER describing the new size of the attribute's data.
 634 *
 635 * @return
 636 * STATUS_SUCCESS on success;
 637 * STATUS_INSUFFICIENT_RESOURCES if an allocation fails.
 638 * STATUS_INVALID_PARAMETER if AttrContext describes a non-resident attribute.
 639 * STATUS_NOT_IMPLEMENTED if requested to decrease the size of an attribute that isn't the
 640 * last attribute listed in the file record.
 641 *
 642 * @remarks
 643 * Called by SetAttributeDataLength() and IncreaseMftSize(). Use SetAttributeDataLength() unless you have a good
 644 * reason to use this. Doesn't update the file record on disk. Doesn't inform the cache controller of changes with
 645 * any associated files. Synchronization is the callers responsibility.
 646 */
 647 NTSTATUS
 648 SetResidentAttributeDataLength(PDEVICE_EXTENSION Vcb,
 649                                PNTFS_ATTR_CONTEXT AttrContext,
 650                                ULONG AttrOffset,
 651                                PFILE_RECORD_HEADER FileRecord,
 652                                PLARGE_INTEGER DataSize)
 653 {
 654     NTSTATUS Status;
 655
 656     // find the next attribute
 657     ULONG NextAttributeOffset = AttrOffset + AttrContext->Record.Length;
 658     PNTFS_ATTR_RECORD NextAttribute = (PNTFS_ATTR_RECORD)((PCHAR)FileRecord + NextAttributeOffset);
 659
 660     if (AttrContext->Record.IsNonResident)
 661     {
 662         DPRINT1("ERROR: SetResidentAttributeDataLength() called for non-resident attribute!\n");
 663         return STATUS_INVALID_PARAMETER;
 664     }
 665
 666     //NtfsDumpFileAttributes(Vcb, FileRecord);
 667
 668     // Do we need to increase the data length?
 669     if (DataSize->QuadPart > AttrContext->Record.Resident.ValueLength)
 670     {
 671         // There's usually padding at the end of a record. Do we need to extend past it?
 672         ULONG MaxValueLength = AttrContext->Record.Length - AttrContext->Record.Resident.ValueOffset;
 673         if (MaxValueLength < DataSize->LowPart)
 674         {
 675             // If this is the last attribute, we could move the end marker to the very end of the file record
 676             MaxValueLength += Vcb->NtfsInfo.BytesPerFileRecord - NextAttributeOffset - (sizeof(ULONG) * 2);
 677
 678             if (MaxValueLength < DataSize->LowPart || NextAttribute->Type != AttributeEnd)
 679             {
 680                 // convert attribute to non-resident
 681                 PNTFS_ATTR_RECORD Destination = (PNTFS_ATTR_RECORD)((ULONG_PTR)FileRecord + AttrOffset);
 682                 LARGE_INTEGER AttribDataSize;
 683                 PVOID AttribData;
 684                 ULONG EndAttributeOffset;
 685                 ULONG LengthWritten;
 686
 687                 DPRINT1("Converting attribute to non-resident.\n");
 688
 689                 AttribDataSize.QuadPart = AttrContext->Record.Resident.ValueLength;
 690
 691                 // Is there existing data we need to back-up?
 692                 if (AttribDataSize.QuadPart > 0)
 693                 {
 694                     AttribData = ExAllocatePoolWithTag(NonPagedPool, AttribDataSize.QuadPart, TAG_NTFS);
 695                     if (AttribData == NULL)
 696                     {
 697                         DPRINT1("ERROR: Couldn't allocate memory for attribute data. Can't migrate to non-resident!\n");
 698                         return STATUS_INSUFFICIENT_RESOURCES;
 699                     }
 700
 701                     // read data to temp buffer
 702                     Status = ReadAttribute(Vcb, AttrContext, 0, AttribData, AttribDataSize.QuadPart);
 703                     if (!NT_SUCCESS(Status))
 704                     {
 705                         DPRINT1("ERROR: Unable to read attribute before migrating!\n");
 706                         ExFreePoolWithTag(AttribData, TAG_NTFS);
 707                         return Status;
 708                     }
 709                 }
 710
 711                 // Start by turning this attribute into a 0-length, non-resident attribute, then enlarge it.
 712
 713                 // Zero out the NonResident structure
 714                 RtlZeroMemory(&AttrContext->Record.NonResident.LowestVCN,
 715                               FIELD_OFFSET(NTFS_ATTR_RECORD, NonResident.CompressedSize) - FIELD_OFFSET(NTFS_ATTR_RECORD, NonResident.LowestVCN));
 716                 RtlZeroMemory(&Destination->NonResident.LowestVCN,
 717                               FIELD_OFFSET(NTFS_ATTR_RECORD, NonResident.CompressedSize) - FIELD_OFFSET(NTFS_ATTR_RECORD, NonResident.LowestVCN));
 718
 719                 // update the mapping pairs offset, which will be 0x40 + length in bytes of the name
 720                 AttrContext->Record.NonResident.MappingPairsOffset = Destination->NonResident.MappingPairsOffset = 0x40 + (Destination->NameLength * 2);
 721
 722                 // mark the attribute as non-resident
 723                 AttrContext->Record.IsNonResident = Destination->IsNonResident = 1;
 724
 725                 // update the end of the file record
 726                 // calculate position of end markers (1 byte for empty data run)
 727                 EndAttributeOffset = AttrOffset + AttrContext->Record.NonResident.MappingPairsOffset + 1;
 728                 EndAttributeOffset = ALIGN_UP_BY(EndAttributeOffset, 8);
 729
 730                 // Update the length
 731                 Destination->Length = EndAttributeOffset - AttrOffset;
 732                 AttrContext->Record.Length = Destination->Length;
 733
 734                 // Update the file record end
 735                 SetFileRecordEnd(FileRecord,
 736                                  (PNTFS_ATTR_RECORD)((ULONG_PTR)FileRecord + EndAttributeOffset),
 737                                  FILE_RECORD_END);
 738
 739                 // update file record on disk
 740                 Status = UpdateFileRecord(Vcb, AttrContext->FileMFTIndex, FileRecord);
 741                 if (!NT_SUCCESS(Status))
 742                 {
 743                     DPRINT1("ERROR: Couldn't update file record to continue migration!\n");
 744                     if (AttribDataSize.QuadPart > 0)
 745                         ExFreePoolWithTag(AttribData, TAG_NTFS);
 746                     return Status;
 747                 }
 748
 749                 // Initialize the MCB, potentially catch an exception
 750                 _SEH2_TRY{
 751                     FsRtlInitializeLargeMcb(&AttrContext->DataRunsMCB, NonPagedPool);
 752                 } _SEH2_EXCEPT(EXCEPTION_EXECUTE_HANDLER) {
 753                     _SEH2_YIELD(return _SEH2_GetExceptionCode());
 754                 } _SEH2_END;
 755
 756                 // Now we can treat the attribute as non-resident and enlarge it normally
 757                 Status = SetNonResidentAttributeDataLength(Vcb, AttrContext, AttrOffset, FileRecord, DataSize);
 758                 if (!NT_SUCCESS(Status))
 759                 {
 760                     DPRINT1("ERROR: Unable to migrate resident attribute!\n");
 761                     if (AttribDataSize.QuadPart > 0)
 762                         ExFreePoolWithTag(AttribData, TAG_NTFS);
 763                     return Status;
 764                 }
 765
 766                 // restore the back-up attribute, if we made one
 767                 if (AttribDataSize.QuadPart > 0)
 768                 {
 769                     Status = WriteAttribute(Vcb, AttrContext, 0, AttribData, AttribDataSize.QuadPart, &LengthWritten);
 770                     if (!NT_SUCCESS(Status))
 771                     {
 772                         DPRINT1("ERROR: Unable to write attribute data to non-resident clusters during migration!\n");
 773                         // TODO: Reverse migration so no data is lost
 774                         ExFreePoolWithTag(AttribData, TAG_NTFS);
 775                         return Status;
 776                     }
 777
 778                     ExFreePoolWithTag(AttribData, TAG_NTFS);
 779                 }
 780             }
 781         }
 782     }
 783     else if (DataSize->LowPart < AttrContext->Record.Resident.ValueLength)
 784     {
 785         // we need to decrease the length
 786         if (NextAttribute->Type != AttributeEnd)
 787         {
 788             DPRINT1("FIXME: Don't know how to decrease length of resident attribute unless it's the final attribute!\n");
 789             return STATUS_NOT_IMPLEMENTED;
 790         }
 791     }
 792
 793     // set the new length of the resident attribute (if we didn't migrate it)
 794     if (!AttrContext->Record.IsNonResident)
 795         InternalSetResidentAttributeLength(AttrContext, FileRecord, AttrOffset, DataSize->LowPart);
 796
 797     return STATUS_SUCCESS;
 798 }
 799
 800 ULONG
 801 ReadAttribute(PDEVICE_EXTENSION Vcb,
 802               PNTFS_ATTR_CONTEXT Context,
 803               ULONGLONG Offset,
 804               PCHAR Buffer,
 805               ULONG Length)
 806 {
 807     ULONGLONG LastLCN;
 808     PUCHAR DataRun;
 809     LONGLONG DataRunOffset;
 810     ULONGLONG DataRunLength;
 811     LONGLONG DataRunStartLCN;
 812     ULONGLONG CurrentOffset;
 813     ULONG ReadLength;
 814     ULONG AlreadyRead;
 815     NTSTATUS Status;
 816
 817     //TEMPTEMP
 818     PUCHAR TempBuffer;
 819
 820     if (!Context->Record.IsNonResident)
 821     {
 822         if (Offset > Context->Record.Resident.ValueLength)
 823             return 0;
 824         if (Offset + Length > Context->Record.Resident.ValueLength)
 825             Length = (ULONG)(Context->Record.Resident.ValueLength - Offset);
 826         RtlCopyMemory(Buffer, (PCHAR)&Context->Record + Context->Record.Resident.ValueOffset + Offset, Length);
 827         return Length;
 828     }
 829
 830     /*
 831      * Non-resident attribute
 832      */
 833
 834     /*
 835      * I. Find the corresponding start data run.
 836      */
 837
 838     AlreadyRead = 0;
 839
 840     // FIXME: Cache seems to be non-working. Disable it for now
 841     //if(Context->CacheRunOffset <= Offset && Offset < Context->CacheRunOffset + Context->CacheRunLength * Volume->ClusterSize)
 842     if (0)
 843     {
 844         DataRun = Context->CacheRun;
 845         LastLCN = Context->CacheRunLastLCN;
 846         DataRunStartLCN = Context->CacheRunStartLCN;
 847         DataRunLength = Context->CacheRunLength;
 848         CurrentOffset = Context->CacheRunCurrentOffset;
 849     }
 850     else
 851     {
 852         //TEMPTEMP
 853         ULONG UsedBufferSize;
 854         TempBuffer = ExAllocatePoolWithTag(NonPagedPool, Vcb->NtfsInfo.BytesPerFileRecord, TAG_NTFS);
 855
 856         LastLCN = 0;
 857         CurrentOffset = 0;
 858
 859         // This will be rewritten in the next iteration to just use the DataRuns MCB directly
 860         ConvertLargeMCBToDataRuns(&Context->DataRunsMCB,
 861                                   TempBuffer,
 862                                   Vcb->NtfsInfo.BytesPerFileRecord,
 863                                   &UsedBufferSize);
 864
 865         DataRun = TempBuffer;
 866
 867         while (1)
 868         {
 869             DataRun = DecodeRun(DataRun, &DataRunOffset, &DataRunLength);
 870             if (DataRunOffset != -1)
 871             {
 872                 /* Normal data run. */
 873                 DataRunStartLCN = LastLCN + DataRunOffset;
 874                 LastLCN = DataRunStartLCN;
 875             }
 876             else
 877             {
 878                 /* Sparse data run. */
 879                 DataRunStartLCN = -1;
 880             }
 881
 882             if (Offset >= CurrentOffset &&
 883                 Offset < CurrentOffset + (DataRunLength * Vcb->NtfsInfo.BytesPerCluster))
 884             {
 885                 break;
 886             }
 887
 888             if (*DataRun == 0)
 889             {
 890                 return AlreadyRead;
 891             }
 892
 893             CurrentOffset += DataRunLength * Vcb->NtfsInfo.BytesPerCluster;
 894         }
 895     }
 896
 897     /*
 898      * II. Go through the run list and read the data
 899      */
 900
 901     ReadLength = (ULONG)min(DataRunLength * Vcb->NtfsInfo.BytesPerCluster - (Offset - CurrentOffset), Length);
 902     if (DataRunStartLCN == -1)
 903     {
 904         RtlZeroMemory(Buffer, ReadLength);
 905         Status = STATUS_SUCCESS;
 906     }
 907     else
 908     {
 909         Status = NtfsReadDisk(Vcb->StorageDevice,
 910                               DataRunStartLCN * Vcb->NtfsInfo.BytesPerCluster + Offset - CurrentOffset,
 911                               ReadLength,
 912                               Vcb->NtfsInfo.BytesPerSector,
 913                               (PVOID)Buffer,
 914                               FALSE);
 915     }
 916     if (NT_SUCCESS(Status))
 917     {
 918         Length -= ReadLength;
 919         Buffer += ReadLength;
 920         AlreadyRead += ReadLength;
 921
 922         if (ReadLength == DataRunLength * Vcb->NtfsInfo.BytesPerCluster - (Offset - CurrentOffset))
 923         {
 924             CurrentOffset += DataRunLength * Vcb->NtfsInfo.BytesPerCluster;
 925             DataRun = DecodeRun(DataRun, &DataRunOffset, &DataRunLength);
 926             if (DataRunOffset != (ULONGLONG)-1)
 927             {
 928                 DataRunStartLCN = LastLCN + DataRunOffset;
 929                 LastLCN = DataRunStartLCN;
 930             }
 931             else
 932                 DataRunStartLCN = -1;
 933         }
 934
 935         while (Length > 0)
 936         {
 937             ReadLength = (ULONG)min(DataRunLength * Vcb->NtfsInfo.BytesPerCluster, Length);
 938             if (DataRunStartLCN == -1)
 939                 RtlZeroMemory(Buffer, ReadLength);
 940             else
 941             {
 942                 Status = NtfsReadDisk(Vcb->StorageDevice,
 943                                       DataRunStartLCN * Vcb->NtfsInfo.BytesPerCluster,
 944                                       ReadLength,
 945                                       Vcb->NtfsInfo.BytesPerSector,
 946                                       (PVOID)Buffer,
 947                                       FALSE);
 948                 if (!NT_SUCCESS(Status))
 949                     break;
 950             }
 951
 952             Length -= ReadLength;
 953             Buffer += ReadLength;
 954             AlreadyRead += ReadLength;
 955
 956             /* We finished this request, but there still data in this data run. */
 957             if (Length == 0 && ReadLength != DataRunLength * Vcb->NtfsInfo.BytesPerCluster)
 958                 break;
 959
 960             /*
 961              * Go to next run in the list.
 962              */
 963
 964             if (*DataRun == 0)
 965                 break;
 966             CurrentOffset += DataRunLength * Vcb->NtfsInfo.BytesPerCluster;
 967             DataRun = DecodeRun(DataRun, &DataRunOffset, &DataRunLength);
 968             if (DataRunOffset != -1)
 969             {
 970                 /* Normal data run. */
 971                 DataRunStartLCN = LastLCN + DataRunOffset;
 972                 LastLCN = DataRunStartLCN;
 973             }
 974             else
 975             {
 976                 /* Sparse data run. */
 977                 DataRunStartLCN = -1;
 978             }
 979         } /* while */
 980
 981     } /* if Disk */
 982
 983     // TEMPTEMP
 984     if (Context->Record.IsNonResident)
 985         ExFreePoolWithTag(TempBuffer, TAG_NTFS);
 986
 987     Context->CacheRun = DataRun;
 988     Context->CacheRunOffset = Offset + AlreadyRead;
 989     Context->CacheRunStartLCN = DataRunStartLCN;
 990     Context->CacheRunLength = DataRunLength;
 991     Context->CacheRunLastLCN = LastLCN;
 992     Context->CacheRunCurrentOffset = CurrentOffset;
 993
 994     return AlreadyRead;
 995 }
 996
 997
 998 /**
 999 * @name WriteAttribute
1000 * @implemented
1001 *
1002 * Writes an NTFS attribute to the disk. It presently borrows a lot of code from ReadAttribute(),
1003 * and it still needs more documentation / cleaning up.
1004 *
1005 * @param Vcb
1006 * Volume Control Block indicating which volume to write the attribute to
1007 *
1008 * @param Context
1009 * Pointer to an NTFS_ATTR_CONTEXT that has information about the attribute
1010 *
1011 * @param Offset
1012 * Offset, in bytes, from the beginning of the attribute indicating where to start
1013 * writing data
1014 *
1015 * @param Buffer
1016 * The data that's being written to the device
1017 *
1018 * @param Length
1019 * How much data will be written, in bytes
1020 *
1021 * @param RealLengthWritten
1022 * Pointer to a ULONG which will receive how much data was written, in bytes
1023 *
1024 * @return
1025 * STATUS_SUCCESS if successful, an error code otherwise. STATUS_NOT_IMPLEMENTED if
1026 * writing to a sparse file.
1027 *
1028 * @remarks Note that in this context the word "attribute" isn't referring read-only, hidden,
1029 * etc. - the file's data is actually stored in an attribute in NTFS parlance.
1030 *
1031 */
1032
1033 NTSTATUS
1034 WriteAttribute(PDEVICE_EXTENSION Vcb,
1035                PNTFS_ATTR_CONTEXT Context,
1036                ULONGLONG Offset,
1037                const PUCHAR Buffer,
1038                ULONG Length,
1039                PULONG RealLengthWritten)
1040 {
1041     ULONGLONG LastLCN;
1042     PUCHAR DataRun;
1043     LONGLONG DataRunOffset;
1044     ULONGLONG DataRunLength;
1045     LONGLONG DataRunStartLCN;
1046     ULONGLONG CurrentOffset;
1047     ULONG WriteLength;
1048     NTSTATUS Status;
1049     PUCHAR SourceBuffer = Buffer;
1050     LONGLONG StartingOffset;
1051
1052     //TEMPTEMP
1053     PUCHAR TempBuffer;
1054
1055
1056     DPRINT("WriteAttribute(%p, %p, %I64u, %p, %lu, %p)\n", Vcb, Context, Offset, Buffer, Length, RealLengthWritten);
1057
1058     *RealLengthWritten = 0;
1059
1060     // is this a resident attribute?
1061     if (!Context->Record.IsNonResident)
1062     {
1063         ULONG AttributeOffset;
1064         PNTFS_ATTR_CONTEXT FoundContext;
1065         PFILE_RECORD_HEADER FileRecord;
1066
1067         if (Offset + Length > Context->Record.Resident.ValueLength)
1068         {
1069             DPRINT1("DRIVER ERROR: Attribute is too small!\n");
1070             return STATUS_INVALID_PARAMETER;
1071         }
1072
1073         FileRecord = ExAllocatePoolWithTag(NonPagedPool, Vcb->NtfsInfo.BytesPerFileRecord, TAG_NTFS);
1074
1075         if (!FileRecord)
1076         {
1077             DPRINT1("Error: Couldn't allocate file record!\n");
1078             return STATUS_NO_MEMORY;
1079         }
1080
1081         // read the file record
1082         ReadFileRecord(Vcb, Context->FileMFTIndex, FileRecord);
1083
1084         // find where to write the attribute data to
1085         Status = FindAttribute(Vcb, FileRecord,
1086                                Context->Record.Type,
1087                                (PCWSTR)((PCHAR)&Context->Record + Context->Record.NameOffset),
1088                                Context->Record.NameLength,
1089                                &FoundContext,
1090                                &AttributeOffset);
1091
1092         if (!NT_SUCCESS(Status))
1093         {
1094             DPRINT1("ERROR: Couldn't find matching attribute!\n");
1095             ExFreePoolWithTag(FileRecord, TAG_NTFS);
1096             return Status;
1097         }
1098
1099         DPRINT("Offset: %I64u, AttributeOffset: %u, ValueOffset: %u\n", Offset, AttributeOffset, Context->Record.Resident.ValueLength);
1100         Offset += AttributeOffset + Context->Record.Resident.ValueOffset;
1101
1102         if (Offset + Length > Vcb->NtfsInfo.BytesPerFileRecord)
1103         {
1104             DPRINT1("DRIVER ERROR: Data being written extends past end of file record!\n");
1105             ReleaseAttributeContext(FoundContext);
1106             ExFreePoolWithTag(FileRecord, TAG_NTFS);
1107             return STATUS_INVALID_PARAMETER;
1108         }
1109
1110         // copy the data being written into the file record
1111         RtlCopyMemory((PCHAR)FileRecord + Offset, Buffer, Length);
1112
1113         Status = UpdateFileRecord(Vcb, Context->FileMFTIndex, FileRecord);
1114
1115         ReleaseAttributeContext(FoundContext);
1116         ExFreePoolWithTag(FileRecord, TAG_NTFS);
1117
1118         if (NT_SUCCESS(Status))
1119             *RealLengthWritten = Length;
1120
1121         return Status;
1122     }
1123
1124     // This is a non-resident attribute.
1125
1126     // I. Find the corresponding start data run.
1127
1128     // FIXME: Cache seems to be non-working. Disable it for now
1129     //if(Context->CacheRunOffset <= Offset && Offset < Context->CacheRunOffset + Context->CacheRunLength * Volume->ClusterSize)
1130     /*if (0)
1131     {
1132     DataRun = Context->CacheRun;
1133     LastLCN = Context->CacheRunLastLCN;
1134     DataRunStartLCN = Context->CacheRunStartLCN;
1135     DataRunLength = Context->CacheRunLength;
1136     CurrentOffset = Context->CacheRunCurrentOffset;
1137     }
1138     else*/
1139     {
1140         ULONG UsedBufferSize;
1141         LastLCN = 0;
1142         CurrentOffset = 0;
1143
1144         // This will be rewritten in the next iteration to just use the DataRuns MCB directly
1145         TempBuffer = ExAllocatePoolWithTag(NonPagedPool, Vcb->NtfsInfo.BytesPerFileRecord, TAG_NTFS);
1146
1147         ConvertLargeMCBToDataRuns(&Context->DataRunsMCB,
1148                                   TempBuffer,
1149                                   Vcb->NtfsInfo.BytesPerFileRecord,
1150                                   &UsedBufferSize);
1151
1152         DataRun = TempBuffer;
1153
1154         while (1)
1155         {
1156             DataRun = DecodeRun(DataRun, &DataRunOffset, &DataRunLength);
1157             if (DataRunOffset != -1)
1158             {
1159                 // Normal data run.
1160                 // DPRINT1("Writing to normal data run, LastLCN %I64u DataRunOffset %I64d\n", LastLCN, DataRunOffset);
1161                 DataRunStartLCN = LastLCN + DataRunOffset;
1162                 LastLCN = DataRunStartLCN;
1163             }
1164             else
1165             {
1166                 // Sparse data run. We can't support writing to sparse files yet
1167                 // (it may require increasing the allocation size).
1168                 DataRunStartLCN = -1;
1169                 DPRINT1("FIXME: Writing to sparse files is not supported yet!\n");
1170                 return STATUS_NOT_IMPLEMENTED;
1171             }
1172
1173             // Have we reached the data run we're trying to write to?
1174             if (Offset >= CurrentOffset &&
1175                 Offset < CurrentOffset + (DataRunLength * Vcb->NtfsInfo.BytesPerCluster))
1176             {
1177                 break;
1178             }
1179
1180             if (*DataRun == 0)
1181             {
1182                 // We reached the last assigned cluster
1183                 // TODO: assign new clusters to the end of the file.
1184                 // (Presently, this code will rarely be reached, the write will usually have already failed by now)
1185                 // [We can reach here by creating a new file record when the MFT isn't large enough]
1186                 DPRINT1("FIXME: Master File Table needs to be enlarged.\n");
1187                 return STATUS_END_OF_FILE;
1188             }
1189
1190             CurrentOffset += DataRunLength * Vcb->NtfsInfo.BytesPerCluster;
1191         }
1192     }
1193
1194     // II. Go through the run list and write the data
1195
1196     /* REVIEWME -- As adapted from NtfsReadAttribute():
1197     We seem to be making a special case for the first applicable data run, but I'm not sure why.
1198     Does it have something to do with (not) caching? Is this strategy equally applicable to writing? */
1199
1200     WriteLength = (ULONG)min(DataRunLength * Vcb->NtfsInfo.BytesPerCluster - (Offset - CurrentOffset), Length);
1201
1202     StartingOffset = DataRunStartLCN * Vcb->NtfsInfo.BytesPerCluster + Offset - CurrentOffset;
1203
1204     // Write the data to the disk
1205     Status = NtfsWriteDisk(Vcb->StorageDevice,
1206                            StartingOffset,
1207                            WriteLength,
1208                            Vcb->NtfsInfo.BytesPerSector,
1209                            (PVOID)SourceBuffer);
1210
1211     // Did the write fail?
1212     if (!NT_SUCCESS(Status))
1213     {
1214         Context->CacheRun = DataRun;
1215         Context->CacheRunOffset = Offset;
1216         Context->CacheRunStartLCN = DataRunStartLCN;
1217         Context->CacheRunLength = DataRunLength;
1218         Context->CacheRunLastLCN = LastLCN;
1219         Context->CacheRunCurrentOffset = CurrentOffset;
1220
1221         return Status;
1222     }
1223
1224     Length -= WriteLength;
1225     SourceBuffer += WriteLength;
1226     *RealLengthWritten += WriteLength;
1227
1228     // Did we write to the end of the data run?
1229     if (WriteLength == DataRunLength * Vcb->NtfsInfo.BytesPerCluster - (Offset - CurrentOffset))
1230     {
1231         // Advance to the next data run
1232         CurrentOffset += DataRunLength * Vcb->NtfsInfo.BytesPerCluster;
1233         DataRun = DecodeRun(DataRun, &DataRunOffset, &DataRunLength);
1234
1235         if (DataRunOffset != (ULONGLONG)-1)
1236         {
1237             DataRunStartLCN = LastLCN + DataRunOffset;
1238             LastLCN = DataRunStartLCN;
1239         }
1240         else
1241             DataRunStartLCN = -1;
1242     }
1243
1244     // Do we have more data to write?
1245     while (Length > 0)
1246     {
1247         // Make sure we don't write past the end of the current data run
1248         WriteLength = (ULONG)min(DataRunLength * Vcb->NtfsInfo.BytesPerCluster, Length);
1249
1250         // Are we dealing with a sparse data run?
1251         if (DataRunStartLCN == -1)
1252         {
1253             DPRINT1("FIXME: Don't know how to write to sparse files yet! (DataRunStartLCN == -1)\n");
1254             return STATUS_NOT_IMPLEMENTED;
1255         }
1256         else
1257         {
1258             // write the data to the disk
1259             Status = NtfsWriteDisk(Vcb->StorageDevice,
1260                                    DataRunStartLCN * Vcb->NtfsInfo.BytesPerCluster,
1261                                    WriteLength,
1262                                    Vcb->NtfsInfo.BytesPerSector,
1263                                    (PVOID)SourceBuffer);
1264             if (!NT_SUCCESS(Status))
1265                 break;
1266         }
1267
1268         Length -= WriteLength;
1269         SourceBuffer += WriteLength;
1270         *RealLengthWritten += WriteLength;
1271
1272         // We finished this request, but there's still data in this data run.
1273         if (Length == 0 && WriteLength != DataRunLength * Vcb->NtfsInfo.BytesPerCluster)
1274             break;
1275
1276         // Go to next run in the list.
1277
1278         if (*DataRun == 0)
1279         {
1280             // that was the last run
1281             if (Length > 0)
1282             {
1283                 // Failed sanity check.
1284                 DPRINT1("Encountered EOF before expected!\n");
1285                 return STATUS_END_OF_FILE;
1286             }
1287
1288             break;
1289         }
1290
1291         // Advance to the next data run
1292         CurrentOffset += DataRunLength * Vcb->NtfsInfo.BytesPerCluster;
1293         DataRun = DecodeRun(DataRun, &DataRunOffset, &DataRunLength);
1294         if (DataRunOffset != -1)
1295         {
1296             // Normal data run.
1297             DataRunStartLCN = LastLCN + DataRunOffset;
1298             LastLCN = DataRunStartLCN;
1299         }
1300         else
1301         {
1302             // Sparse data run.
1303             DataRunStartLCN = -1;
1304         }
1305     } // end while (Length > 0) [more data to write]
1306
1307     // TEMPTEMP
1308     if(Context->Record.IsNonResident)
1309         ExFreePoolWithTag(TempBuffer, TAG_NTFS);
1310
1311     Context->CacheRun = DataRun;
1312     Context->CacheRunOffset = Offset + *RealLengthWritten;
1313     Context->CacheRunStartLCN = DataRunStartLCN;
1314     Context->CacheRunLength = DataRunLength;
1315     Context->CacheRunLastLCN = LastLCN;
1316     Context->CacheRunCurrentOffset = CurrentOffset;
1317
1318     return Status;
1319 }
1320
1321 NTSTATUS
1322 ReadFileRecord(PDEVICE_EXTENSION Vcb,
1323                ULONGLONG index,
1324                PFILE_RECORD_HEADER file)
1325 {
1326     ULONGLONG BytesRead;
1327
1328     DPRINT("ReadFileRecord(%p, %I64x, %p)\n", Vcb, index, file);
1329
1330     BytesRead = ReadAttribute(Vcb, Vcb->MFTContext, index * Vcb->NtfsInfo.BytesPerFileRecord, (PCHAR)file, Vcb->NtfsInfo.BytesPerFileRecord);
1331     if (BytesRead != Vcb->NtfsInfo.BytesPerFileRecord)
1332     {
1333         DPRINT1("ReadFileRecord failed: %I64u read, %u expected\n", BytesRead, Vcb->NtfsInfo.BytesPerFileRecord);
1334         return STATUS_PARTIAL_COPY;
1335     }
1336
1337     /* Apply update sequence array fixups. */
1338     DPRINT("Sequence number: %u\n", file->SequenceNumber);
1339     return FixupUpdateSequenceArray(Vcb, &file->Ntfs);
1340 }
1341
1342
1343 /**
1344 * Searches a file's parent directory (given the parent's index in the mft)
1345 * for the given file. Upon finding an index entry for that file, updates
1346 * Data Size and Allocated Size values in the $FILE_NAME attribute of that entry.
1347 *
1348 * (Most of this code was copied from NtfsFindMftRecord)
1349 */
1350 NTSTATUS
1351 UpdateFileNameRecord(PDEVICE_EXTENSION Vcb,
1352                      ULONGLONG ParentMFTIndex,
1353                      PUNICODE_STRING FileName,
1354                      BOOLEAN DirSearch,
1355                      ULONGLONG NewDataSize,
1356                      ULONGLONG NewAllocationSize)
1357 {
1358     PFILE_RECORD_HEADER MftRecord;
1359     PNTFS_ATTR_CONTEXT IndexRootCtx;
1360     PINDEX_ROOT_ATTRIBUTE IndexRoot;
1361     PCHAR IndexRecord;
1362     PINDEX_ENTRY_ATTRIBUTE IndexEntry, IndexEntryEnd;
1363     NTSTATUS Status;
1364     ULONG CurrentEntry = 0;
1365
1366     DPRINT("UpdateFileNameRecord(%p, %I64d, %wZ, %u, %I64u, %I64u)\n", Vcb, ParentMFTIndex, FileName, DirSearch, NewDataSize, NewAllocationSize);
1367
1368     MftRecord = ExAllocatePoolWithTag(NonPagedPool,
1369                                       Vcb->NtfsInfo.BytesPerFileRecord,
1370                                       TAG_NTFS);
1371     if (MftRecord == NULL)
1372     {
1373         return STATUS_INSUFFICIENT_RESOURCES;
1374     }
1375
1376     Status = ReadFileRecord(Vcb, ParentMFTIndex, MftRecord);
1377     if (!NT_SUCCESS(Status))
1378     {
1379         ExFreePoolWithTag(MftRecord, TAG_NTFS);
1380         return Status;
1381     }
1382
1383     ASSERT(MftRecord->Ntfs.Type == NRH_FILE_TYPE);
1384     Status = FindAttribute(Vcb, MftRecord, AttributeIndexRoot, L"$I30", 4, &IndexRootCtx, NULL);
1385     if (!NT_SUCCESS(Status))
1386     {
1387         ExFreePoolWithTag(MftRecord, TAG_NTFS);
1388         return Status;
1389     }
1390
1391     IndexRecord = ExAllocatePoolWithTag(NonPagedPool, Vcb->NtfsInfo.BytesPerIndexRecord, TAG_NTFS);
1392     if (IndexRecord == NULL)
1393     {
1394         ReleaseAttributeContext(IndexRootCtx);
1395         ExFreePoolWithTag(MftRecord, TAG_NTFS);
1396         return STATUS_INSUFFICIENT_RESOURCES;
1397     }
1398
1399     ReadAttribute(Vcb, IndexRootCtx, 0, IndexRecord, Vcb->NtfsInfo.BytesPerIndexRecord);
1400     IndexRoot = (PINDEX_ROOT_ATTRIBUTE)IndexRecord;
1401     IndexEntry = (PINDEX_ENTRY_ATTRIBUTE)((PCHAR)&IndexRoot->Header + IndexRoot->Header.FirstEntryOffset);
1402     // Index root is always resident.
1403     IndexEntryEnd = (PINDEX_ENTRY_ATTRIBUTE)(IndexRecord + IndexRoot->Header.TotalSizeOfEntries);
1404
1405     DPRINT("IndexRecordSize: %x IndexBlockSize: %x\n", Vcb->NtfsInfo.BytesPerIndexRecord, IndexRoot->SizeOfEntry);
1406
1407     Status = UpdateIndexEntryFileNameSize(Vcb,
1408                                           MftRecord,
1409                                           IndexRecord,
1410                                           IndexRoot->SizeOfEntry,
1411                                           IndexEntry,
1412                                           IndexEntryEnd,
1413                                           FileName,
1414                                           &CurrentEntry,
1415                                           &CurrentEntry,
1416                                           DirSearch,
1417                                           NewDataSize,
1418                                           NewAllocationSize);
1419
1420     ReleaseAttributeContext(IndexRootCtx);
1421     ExFreePoolWithTag(IndexRecord, TAG_NTFS);
1422     ExFreePoolWithTag(MftRecord, TAG_NTFS);
1423
1424     return Status;
1425 }
1426
1427 /**
1428 * Recursively searches directory index and applies the size update to the $FILE_NAME attribute of the
1429 * proper index entry.
1430 * (Heavily based on BrowseIndexEntries)
1431 */
1432 NTSTATUS
1433 UpdateIndexEntryFileNameSize(PDEVICE_EXTENSION Vcb,
1434                              PFILE_RECORD_HEADER MftRecord,
1435                              PCHAR IndexRecord,
1436                              ULONG IndexBlockSize,
1437                              PINDEX_ENTRY_ATTRIBUTE FirstEntry,
1438                              PINDEX_ENTRY_ATTRIBUTE LastEntry,
1439                              PUNICODE_STRING FileName,
1440                              PULONG StartEntry,
1441                              PULONG CurrentEntry,
1442                              BOOLEAN DirSearch,
1443                              ULONGLONG NewDataSize,
1444                              ULONGLONG NewAllocatedSize)
1445 {
1446     NTSTATUS Status;
1447     ULONG RecordOffset;
1448     PINDEX_ENTRY_ATTRIBUTE IndexEntry;
1449     PNTFS_ATTR_CONTEXT IndexAllocationCtx;
1450     ULONGLONG IndexAllocationSize;
1451     PINDEX_BUFFER IndexBuffer;
1452
1453     DPRINT("UpdateIndexEntrySize(%p, %p, %p, %u, %p, %p, %wZ, %u, %u, %u, %I64u, %I64u)\n", Vcb, MftRecord, IndexRecord, IndexBlockSize, FirstEntry, LastEntry, FileName, *StartEntry, *CurrentEntry, DirSearch, NewDataSize, NewAllocatedSize);
1454
1455     // find the index entry responsible for the file we're trying to update
1456     IndexEntry = FirstEntry;
1457     while (IndexEntry < LastEntry &&
1458            !(IndexEntry->Flags & NTFS_INDEX_ENTRY_END))
1459     {
1460         if ((IndexEntry->Data.Directory.IndexedFile & NTFS_MFT_MASK) > 0x10 &&
1461             *CurrentEntry >= *StartEntry &&
1462             IndexEntry->FileName.NameType != NTFS_FILE_NAME_DOS &&
1463             CompareFileName(FileName, IndexEntry, DirSearch))
1464         {
1465             *StartEntry = *CurrentEntry;
1466             IndexEntry->FileName.DataSize = NewDataSize;
1467             IndexEntry->FileName.AllocatedSize = NewAllocatedSize;
1468             // indicate that the caller will still need to write the structure to the disk
1469             return STATUS_PENDING;
1470         }
1471
1472         (*CurrentEntry) += 1;
1473         ASSERT(IndexEntry->Length >= sizeof(INDEX_ENTRY_ATTRIBUTE));
1474         IndexEntry = (PINDEX_ENTRY_ATTRIBUTE)((PCHAR)IndexEntry + IndexEntry->Length);
1475     }
1476
1477     /* If we're already browsing a subnode */
1478     if (IndexRecord == NULL)
1479     {
1480         return STATUS_OBJECT_PATH_NOT_FOUND;
1481     }
1482
1483     /* If there's no subnode */
1484     if (!(IndexEntry->Flags & NTFS_INDEX_ENTRY_NODE))
1485     {
1486         return STATUS_OBJECT_PATH_NOT_FOUND;
1487     }
1488
1489     Status = FindAttribute(Vcb, MftRecord, AttributeIndexAllocation, L"$I30", 4, &IndexAllocationCtx, NULL);
1490     if (!NT_SUCCESS(Status))
1491     {
1492         DPRINT("Corrupted filesystem!\n");
1493         return Status;
1494     }
1495
1496     IndexAllocationSize = AttributeDataLength(&IndexAllocationCtx->Record);
1497     Status = STATUS_OBJECT_PATH_NOT_FOUND;
1498     for (RecordOffset = 0; RecordOffset < IndexAllocationSize; RecordOffset += IndexBlockSize)
1499     {
1500         ReadAttribute(Vcb, IndexAllocationCtx, RecordOffset, IndexRecord, IndexBlockSize);
1501         Status = FixupUpdateSequenceArray(Vcb, &((PFILE_RECORD_HEADER)IndexRecord)->Ntfs);
1502         if (!NT_SUCCESS(Status))
1503         {
1504             break;
1505         }
1506
1507         IndexBuffer = (PINDEX_BUFFER)IndexRecord;
1508         ASSERT(IndexBuffer->Ntfs.Type == NRH_INDX_TYPE);
1509         ASSERT(IndexBuffer->Header.AllocatedSize + FIELD_OFFSET(INDEX_BUFFER, Header) == IndexBlockSize);
1510         FirstEntry = (PINDEX_ENTRY_ATTRIBUTE)((ULONG_PTR)&IndexBuffer->Header + IndexBuffer->Header.FirstEntryOffset);
1511         LastEntry = (PINDEX_ENTRY_ATTRIBUTE)((ULONG_PTR)&IndexBuffer->Header + IndexBuffer->Header.TotalSizeOfEntries);
1512         ASSERT(LastEntry <= (PINDEX_ENTRY_ATTRIBUTE)((ULONG_PTR)IndexBuffer + IndexBlockSize));
1513
1514         Status = UpdateIndexEntryFileNameSize(NULL, NULL, NULL, 0, FirstEntry, LastEntry, FileName, StartEntry, CurrentEntry, DirSearch, NewDataSize, NewAllocatedSize);
1515         if (Status == STATUS_PENDING)
1516         {
1517             // write the index record back to disk
1518             ULONG Written;
1519
1520             // first we need to update the fixup values for the index block
1521             Status = AddFixupArray(Vcb, &((PFILE_RECORD_HEADER)IndexRecord)->Ntfs);
1522             if (!NT_SUCCESS(Status))
1523             {
1524                 DPRINT1("Error: Failed to update fixup sequence array!\n");
1525                 break;
1526             }
1527
1528             Status = WriteAttribute(Vcb, IndexAllocationCtx, RecordOffset, (const PUCHAR)IndexRecord, IndexBlockSize, &Written);
1529             if (!NT_SUCCESS(Status))
1530             {
1531                 DPRINT1("ERROR Performing write!\n");
1532                 break;
1533             }
1534
1535             Status = STATUS_SUCCESS;
1536             break;
1537         }
1538         if (NT_SUCCESS(Status))
1539         {
1540             break;
1541         }
1542     }
1543
1544     ReleaseAttributeContext(IndexAllocationCtx);
1545     return Status;
1546 }
1547
1548 /**
1549 * @name UpdateFileRecord
1550 * @implemented
1551 *
1552 * Writes a file record to the master file table, at a given index.
1553 *
1554 * @param Vcb
1555 * Pointer to the DEVICE_EXTENSION of the target drive being written to.
1556 *
1557 * @param MftIndex
1558 * Target index in the master file table to store the file record.
1559 *
1560 * @param FileRecord
1561 * Pointer to the complete file record which will be written to the master file table.
1562 *
1563 * @return
1564 * STATUS_SUCCESSFUL on success. An error passed from WriteAttribute() otherwise.
1565 *
1566 */
1567 NTSTATUS
1568 UpdateFileRecord(PDEVICE_EXTENSION Vcb,
1569                  ULONGLONG MftIndex,
1570                  PFILE_RECORD_HEADER FileRecord)
1571 {
1572     ULONG BytesWritten;
1573     NTSTATUS Status = STATUS_SUCCESS;
1574
1575     DPRINT("UpdateFileRecord(%p, 0x%I64x, %p)\n", Vcb, MftIndex, FileRecord);
1576
1577     // Add the fixup array to prepare the data for writing to disk
1578     AddFixupArray(Vcb, &FileRecord->Ntfs);
1579
1580     // write the file record to the master file table
1581     Status = WriteAttribute(Vcb, Vcb->MFTContext, MftIndex * Vcb->NtfsInfo.BytesPerFileRecord, (const PUCHAR)FileRecord, Vcb->NtfsInfo.BytesPerFileRecord, &BytesWritten);
1582
1583     if (!NT_SUCCESS(Status))
1584     {
1585         DPRINT1("UpdateFileRecord failed: %lu written, %lu expected\n", BytesWritten, Vcb->NtfsInfo.BytesPerFileRecord);
1586     }
1587
1588     // remove the fixup array (so the file record pointer can still be used)
1589     FixupUpdateSequenceArray(Vcb, &FileRecord->Ntfs);
1590
1591     return Status;
1592 }
1593
1594
1595 NTSTATUS
1596 FixupUpdateSequenceArray(PDEVICE_EXTENSION Vcb,
1597                          PNTFS_RECORD_HEADER Record)
1598 {
1599     USHORT *USA;
1600     USHORT USANumber;
1601     USHORT USACount;
1602     USHORT *Block;
1603
1604     USA = (USHORT*)((PCHAR)Record + Record->UsaOffset);
1605     USANumber = *(USA++);
1606     USACount = Record->UsaCount - 1; /* Exclude the USA Number. */
1607     Block = (USHORT*)((PCHAR)Record + Vcb->NtfsInfo.BytesPerSector - 2);
1608
1609     DPRINT("FixupUpdateSequenceArray(%p, %p)\nUSANumber: %u\tUSACount: %u\n", Vcb, Record, USANumber, USACount);
1610
1611     while (USACount)
1612     {
1613         if (*Block != USANumber)
1614         {
1615             DPRINT1("Mismatch with USA: %u read, %u expected\n" , *Block, USANumber);
1616             return STATUS_UNSUCCESSFUL;
1617         }
1618         *Block = *(USA++);
1619         Block = (USHORT*)((PCHAR)Block + Vcb->NtfsInfo.BytesPerSector);
1620         USACount--;
1621     }
1622
1623     return STATUS_SUCCESS;
1624 }
1625
1626 /**
1627 * @name AddNewMftEntry
1628 * @implemented
1629 *
1630 * Adds a file record to the master file table of a given device.
1631 *
1632 * @param FileRecord
1633 * Pointer to a complete file record which will be saved to disk.
1634 *
1635 * @param DeviceExt
1636 * Pointer to the DEVICE_EXTENSION of the target drive.
1637 *
1638 * @param DestinationIndex
1639 * Pointer to a ULONGLONG which will receive the MFT index where the file record was stored.
1640 *
1641 * @return
1642 * STATUS_SUCCESS on success.
1643 * STATUS_OBJECT_NAME_NOT_FOUND if we can't find the MFT's $Bitmap or if we weren't able
1644 * to read the attribute.
1645 * STATUS_INSUFFICIENT_RESOURCES if we can't allocate enough memory for a copy of $Bitmap.
1646 *
1647 */
1648 NTSTATUS
1649 AddNewMftEntry(PFILE_RECORD_HEADER FileRecord,
1650                PDEVICE_EXTENSION DeviceExt,
1651                PULONGLONG DestinationIndex)
1652 {
1653     NTSTATUS Status = STATUS_SUCCESS;
1654     ULONGLONG MftIndex;
1655     RTL_BITMAP Bitmap;
1656     ULONGLONG BitmapDataSize;
1657     ULONGLONG AttrBytesRead;
1658     PVOID BitmapData;
1659     ULONG LengthWritten;
1660     PNTFS_ATTR_CONTEXT BitmapContext;
1661     LARGE_INTEGER BitmapBits;
1662     UCHAR SystemReservedBits;
1663
1664     DPRINT1("AddNewMftEntry(%p, %p, %p)\n", FileRecord, DeviceExt, DestinationIndex);
1665
1666     // First, we have to read the mft's $Bitmap attribute
1667     Status = FindAttribute(DeviceExt, DeviceExt->MasterFileTable, AttributeBitmap, L"", 0, &BitmapContext, NULL);
1668     if (!NT_SUCCESS(Status))
1669     {
1670         DPRINT1("ERROR: Couldn't find $Bitmap attribute of master file table!\n");
1671         return Status;
1672     }
1673
1674     // allocate a buffer for the $Bitmap attribute
1675     BitmapDataSize = AttributeDataLength(&BitmapContext->Record);
1676     BitmapData = ExAllocatePoolWithTag(NonPagedPool, BitmapDataSize, TAG_NTFS);
1677     if (!BitmapData)
1678     {
1679         ReleaseAttributeContext(BitmapContext);
1680         return STATUS_INSUFFICIENT_RESOURCES;
1681     }
1682
1683     // read $Bitmap attribute
1684     AttrBytesRead = ReadAttribute(DeviceExt, BitmapContext, 0, BitmapData, BitmapDataSize);
1685
1686     if (AttrBytesRead == 0)
1687     {
1688         DPRINT1("ERROR: Unable to read $Bitmap attribute of master file table!\n");
1689         ExFreePoolWithTag(BitmapData, TAG_NTFS);
1690         ReleaseAttributeContext(BitmapContext);
1691         return STATUS_OBJECT_NAME_NOT_FOUND;
1692     }
1693
1694     // we need to backup the bits for records 0x10 - 0x17 and leave them unassigned if they aren't assigned
1695     RtlCopyMemory(&SystemReservedBits, (PVOID)((ULONG_PTR)BitmapData + 2), 1);
1696     RtlFillMemory((PVOID)((ULONG_PTR)BitmapData + 2), 1, (UCHAR)0xFF);
1697
1698     // Calculate bit count
1699     BitmapBits.QuadPart = AttributeDataLength(&(DeviceExt->MFTContext->Record)) /
1700                           DeviceExt->NtfsInfo.BytesPerFileRecord;
1701     if (BitmapBits.HighPart != 0)
1702     {
1703         DPRINT1("\tFIXME: bitmap sizes beyond 32bits are not yet supported!\n");
1704         BitmapBits.LowPart = 0xFFFFFFFF;
1705     }
1706
1707     // convert buffer into bitmap
1708     RtlInitializeBitMap(&Bitmap, (PULONG)BitmapData, BitmapBits.LowPart);
1709
1710     // set next available bit, preferrably after 23rd bit
1711     MftIndex = RtlFindClearBitsAndSet(&Bitmap, 1, 24);
1712     if ((LONG)MftIndex == -1)
1713     {
1714         DPRINT1("Couldn't find free space in MFT for file record, increasing MFT size.\n");
1715
1716         ExFreePoolWithTag(BitmapData, TAG_NTFS);
1717         ReleaseAttributeContext(BitmapContext);
1718
1719         // Couldn't find a free record in the MFT, add some blank records and try again
1720         Status = IncreaseMftSize(DeviceExt);
1721         if (!NT_SUCCESS(Status))
1722         {
1723             DPRINT1("ERROR: Couldn't find space in MFT for file or increase MFT size!\n");
1724             return Status;
1725         }
1726
1727         return AddNewMftEntry(FileRecord, DeviceExt, DestinationIndex);
1728     }
1729
1730     DPRINT1("Creating file record at MFT index: %I64u\n", MftIndex);
1731
1732     // update file record with index
1733     FileRecord->MFTRecordNumber = MftIndex;
1734
1735     // [BitmapData should have been updated via RtlFindClearBitsAndSet()]
1736
1737     // Restore the system reserved bits
1738     RtlCopyMemory((PVOID)((ULONG_PTR)BitmapData + 2), &SystemReservedBits, 1);
1739
1740     // write the bitmap back to the MFT's $Bitmap attribute
1741     Status = WriteAttribute(DeviceExt, BitmapContext, 0, BitmapData, BitmapDataSize, &LengthWritten);
1742     if (!NT_SUCCESS(Status))
1743     {
1744         DPRINT1("ERROR encountered when writing $Bitmap attribute!\n");
1745         ExFreePoolWithTag(BitmapData, TAG_NTFS);
1746         ReleaseAttributeContext(BitmapContext);
1747         return Status;
1748     }
1749
1750     // update the file record (write it to disk)
1751     Status = UpdateFileRecord(DeviceExt, MftIndex, FileRecord);
1752
1753     if (!NT_SUCCESS(Status))
1754     {
1755         DPRINT1("ERROR: Unable to write file record!\n");
1756         ExFreePoolWithTag(BitmapData, TAG_NTFS);
1757         ReleaseAttributeContext(BitmapContext);
1758         return Status;
1759     }
1760
1761     *DestinationIndex = MftIndex;
1762
1763     ExFreePoolWithTag(BitmapData, TAG_NTFS);
1764     ReleaseAttributeContext(BitmapContext);
1765
1766     return Status;
1767 }
1768
1769 NTSTATUS
1770 AddFixupArray(PDEVICE_EXTENSION Vcb,
1771               PNTFS_RECORD_HEADER Record)
1772 {
1773     USHORT *pShortToFixUp;
1774     unsigned int ArrayEntryCount = Record->UsaCount - 1;
1775     unsigned int Offset = Vcb->NtfsInfo.BytesPerSector - 2;
1776     int i;
1777
1778     PFIXUP_ARRAY fixupArray = (PFIXUP_ARRAY)((UCHAR*)Record + Record->UsaOffset);
1779
1780     DPRINT("AddFixupArray(%p, %p)\n fixupArray->USN: %u, ArrayEntryCount: %u\n", Vcb, Record, fixupArray->USN, ArrayEntryCount);
1781
1782     fixupArray->USN++;
1783
1784     for (i = 0; i < ArrayEntryCount; i++)
1785     {
1786         DPRINT("USN: %u\tOffset: %u\n", fixupArray->USN, Offset);
1787
1788         pShortToFixUp = (USHORT*)((PCHAR)Record + Offset);
1789         fixupArray->Array[i] = *pShortToFixUp;
1790         *pShortToFixUp = fixupArray->USN;
1791         Offset += Vcb->NtfsInfo.BytesPerSector;
1792     }
1793
1794     return STATUS_SUCCESS;
1795 }
1796
1797 NTSTATUS
1798 ReadLCN(PDEVICE_EXTENSION Vcb,
1799         ULONGLONG lcn,
1800         ULONG count,
1801         PVOID buffer)
1802 {
1803     LARGE_INTEGER DiskSector;
1804
1805     DiskSector.QuadPart = lcn;
1806
1807     return NtfsReadSectors(Vcb->StorageDevice,
1808                            DiskSector.u.LowPart * Vcb->NtfsInfo.SectorsPerCluster,
1809                            count * Vcb->NtfsInfo.SectorsPerCluster,
1810                            Vcb->NtfsInfo.BytesPerSector,
1811                            buffer,
1812                            FALSE);
1813 }
1814
1815
1816 BOOLEAN
1817 CompareFileName(PUNICODE_STRING FileName,
1818                 PINDEX_ENTRY_ATTRIBUTE IndexEntry,
1819                 BOOLEAN DirSearch)
1820 {
1821     BOOLEAN Ret, Alloc = FALSE;
1822     UNICODE_STRING EntryName;
1823
1824     EntryName.Buffer = IndexEntry->FileName.Name;
1825     EntryName.Length =
1826     EntryName.MaximumLength = IndexEntry->FileName.NameLength * sizeof(WCHAR);
1827
1828     if (DirSearch)
1829     {
1830         UNICODE_STRING IntFileName;
1831         if (IndexEntry->FileName.NameType != NTFS_FILE_NAME_POSIX)
1832         {
1833             NT_VERIFY(NT_SUCCESS(RtlUpcaseUnicodeString(&IntFileName, FileName, TRUE)));
1834             Alloc = TRUE;
1835         }
1836         else
1837         {
1838             IntFileName = *FileName;
1839         }
1840
1841         Ret = FsRtlIsNameInExpression(&IntFileName, &EntryName, (IndexEntry->FileName.NameType != NTFS_FILE_NAME_POSIX), NULL);
1842
1843         if (Alloc)
1844         {
1845             RtlFreeUnicodeString(&IntFileName);
1846         }
1847
1848         return Ret;
1849     }
1850     else
1851     {
1852         return (RtlCompareUnicodeString(FileName, &EntryName, (IndexEntry->FileName.NameType != NTFS_FILE_NAME_POSIX)) == 0);
1853     }
1854 }
1855
1856 #if 0
1857 static
1858 VOID
1859 DumpIndexEntry(PINDEX_ENTRY_ATTRIBUTE IndexEntry)
1860 {
1861     DPRINT1("Entry: %p\n", IndexEntry);
1862     DPRINT1("\tData.Directory.IndexedFile: %I64x\n", IndexEntry->Data.Directory.IndexedFile);
1863     DPRINT1("\tLength: %u\n", IndexEntry->Length);
1864     DPRINT1("\tKeyLength: %u\n", IndexEntry->KeyLength);
1865     DPRINT1("\tFlags: %x\n", IndexEntry->Flags);
1866     DPRINT1("\tReserved: %x\n", IndexEntry->Reserved);
1867     DPRINT1("\t\tDirectoryFileReferenceNumber: %I64x\n", IndexEntry->FileName.DirectoryFileReferenceNumber);
1868     DPRINT1("\t\tCreationTime: %I64u\n", IndexEntry->FileName.CreationTime);
1869     DPRINT1("\t\tChangeTime: %I64u\n", IndexEntry->FileName.ChangeTime);
1870     DPRINT1("\t\tLastWriteTime: %I64u\n", IndexEntry->FileName.LastWriteTime);
1871     DPRINT1("\t\tLastAccessTime: %I64u\n", IndexEntry->FileName.LastAccessTime);
1872     DPRINT1("\t\tAllocatedSize: %I64u\n", IndexEntry->FileName.AllocatedSize);
1873     DPRINT1("\t\tDataSize: %I64u\n", IndexEntry->FileName.DataSize);
1874     DPRINT1("\t\tFileAttributes: %x\n", IndexEntry->FileName.FileAttributes);
1875     DPRINT1("\t\tNameLength: %u\n", IndexEntry->FileName.NameLength);
1876     DPRINT1("\t\tNameType: %x\n", IndexEntry->FileName.NameType);
1877     DPRINT1("\t\tName: %.*S\n", IndexEntry->FileName.NameLength, IndexEntry->FileName.Name);
1878 }
1879 #endif
1880
1881 NTSTATUS
1882 BrowseIndexEntries(PDEVICE_EXTENSION Vcb,
1883                    PFILE_RECORD_HEADER MftRecord,
1884                    PCHAR IndexRecord,
1885                    ULONG IndexBlockSize,
1886                    PINDEX_ENTRY_ATTRIBUTE FirstEntry,
1887                    PINDEX_ENTRY_ATTRIBUTE LastEntry,
1888                    PUNICODE_STRING FileName,
1889                    PULONG StartEntry,
1890                    PULONG CurrentEntry,
1891                    BOOLEAN DirSearch,
1892                    ULONGLONG *OutMFTIndex)
1893 {
1894     NTSTATUS Status;
1895     ULONG RecordOffset;
1896     PINDEX_ENTRY_ATTRIBUTE IndexEntry;
1897     PNTFS_ATTR_CONTEXT IndexAllocationCtx;
1898     ULONGLONG IndexAllocationSize;
1899     PINDEX_BUFFER IndexBuffer;
1900
1901     DPRINT("BrowseIndexEntries(%p, %p, %p, %u, %p, %p, %wZ, %u, %u, %u, %p)\n", Vcb, MftRecord, IndexRecord, IndexBlockSize, FirstEntry, LastEntry, FileName, *StartEntry, *CurrentEntry, DirSearch, OutMFTIndex);
1902
1903     IndexEntry = FirstEntry;
1904     while (IndexEntry < LastEntry &&
1905            !(IndexEntry->Flags & NTFS_INDEX_ENTRY_END))
1906     {
1907         if ((IndexEntry->Data.Directory.IndexedFile & NTFS_MFT_MASK) >= 0x10 &&
1908             *CurrentEntry >= *StartEntry &&
1909             IndexEntry->FileName.NameType != NTFS_FILE_NAME_DOS &&
1910             CompareFileName(FileName, IndexEntry, DirSearch))
1911         {
1912             *StartEntry = *CurrentEntry;
1913             *OutMFTIndex = (IndexEntry->Data.Directory.IndexedFile & NTFS_MFT_MASK);
1914             return STATUS_SUCCESS;
1915         }
1916
1917         (*CurrentEntry) += 1;
1918         ASSERT(IndexEntry->Length >= sizeof(INDEX_ENTRY_ATTRIBUTE));
1919         IndexEntry = (PINDEX_ENTRY_ATTRIBUTE)((PCHAR)IndexEntry + IndexEntry->Length);
1920     }
1921
1922     /* If we're already browsing a subnode */
1923     if (IndexRecord == NULL)
1924     {
1925         return STATUS_OBJECT_PATH_NOT_FOUND;
1926     }
1927
1928     /* If there's no subnode */
1929     if (!(IndexEntry->Flags & NTFS_INDEX_ENTRY_NODE))
1930     {
1931         return STATUS_OBJECT_PATH_NOT_FOUND;
1932     }
1933
1934     Status = FindAttribute(Vcb, MftRecord, AttributeIndexAllocation, L"$I30", 4, &IndexAllocationCtx, NULL);
1935     if (!NT_SUCCESS(Status))
1936     {
1937         DPRINT("Corrupted filesystem!\n");
1938         return Status;
1939     }
1940
1941     IndexAllocationSize = AttributeDataLength(&IndexAllocationCtx->Record);
1942     Status = STATUS_OBJECT_PATH_NOT_FOUND;
1943     for (RecordOffset = 0; RecordOffset < IndexAllocationSize; RecordOffset += IndexBlockSize)
1944     {
1945         ReadAttribute(Vcb, IndexAllocationCtx, RecordOffset, IndexRecord, IndexBlockSize);
1946         Status = FixupUpdateSequenceArray(Vcb, &((PFILE_RECORD_HEADER)IndexRecord)->Ntfs);
1947         if (!NT_SUCCESS(Status))
1948         {
1949             break;
1950         }
1951
1952         IndexBuffer = (PINDEX_BUFFER)IndexRecord;
1953         ASSERT(IndexBuffer->Ntfs.Type == NRH_INDX_TYPE);
1954         ASSERT(IndexBuffer->Header.AllocatedSize + FIELD_OFFSET(INDEX_BUFFER, Header) == IndexBlockSize);
1955         FirstEntry = (PINDEX_ENTRY_ATTRIBUTE)((ULONG_PTR)&IndexBuffer->Header + IndexBuffer->Header.FirstEntryOffset);
1956         LastEntry = (PINDEX_ENTRY_ATTRIBUTE)((ULONG_PTR)&IndexBuffer->Header + IndexBuffer->Header.TotalSizeOfEntries);
1957         ASSERT(LastEntry <= (PINDEX_ENTRY_ATTRIBUTE)((ULONG_PTR)IndexBuffer + IndexBlockSize));
1958
1959         Status = BrowseIndexEntries(NULL, NULL, NULL, 0, FirstEntry, LastEntry, FileName, StartEntry, CurrentEntry, DirSearch, OutMFTIndex);
1960         if (NT_SUCCESS(Status))
1961         {
1962             break;
1963         }
1964     }
1965
1966     ReleaseAttributeContext(IndexAllocationCtx);
1967     return Status;
1968 }
1969
1970 NTSTATUS
1971 NtfsFindMftRecord(PDEVICE_EXTENSION Vcb,
1972                   ULONGLONG MFTIndex,
1973                   PUNICODE_STRING FileName,
1974                   PULONG FirstEntry,
1975                   BOOLEAN DirSearch,
1976                   ULONGLONG *OutMFTIndex)
1977 {
1978     PFILE_RECORD_HEADER MftRecord;
1979     PNTFS_ATTR_CONTEXT IndexRootCtx;
1980     PINDEX_ROOT_ATTRIBUTE IndexRoot;
1981     PCHAR IndexRecord;
1982     PINDEX_ENTRY_ATTRIBUTE IndexEntry, IndexEntryEnd;
1983     NTSTATUS Status;
1984     ULONG CurrentEntry = 0;
1985
1986     DPRINT("NtfsFindMftRecord(%p, %I64d, %wZ, %u, %u, %p)\n", Vcb, MFTIndex, FileName, *FirstEntry, DirSearch, OutMFTIndex);
1987
1988     MftRecord = ExAllocatePoolWithTag(NonPagedPool,
1989                                       Vcb->NtfsInfo.BytesPerFileRecord,
1990                                       TAG_NTFS);
1991     if (MftRecord == NULL)
1992     {
1993         return STATUS_INSUFFICIENT_RESOURCES;
1994     }
1995
1996     Status = ReadFileRecord(Vcb, MFTIndex, MftRecord);
1997     if (!NT_SUCCESS(Status))
1998     {
1999         ExFreePoolWithTag(MftRecord, TAG_NTFS);
2000         return Status;
2001     }
2002
2003     ASSERT(MftRecord->Ntfs.Type == NRH_FILE_TYPE);
2004     Status = FindAttribute(Vcb, MftRecord, AttributeIndexRoot, L"$I30", 4, &IndexRootCtx, NULL);
2005     if (!NT_SUCCESS(Status))
2006     {
2007         ExFreePoolWithTag(MftRecord, TAG_NTFS);
2008         return Status;
2009     }
2010
2011     IndexRecord = ExAllocatePoolWithTag(NonPagedPool, Vcb->NtfsInfo.BytesPerIndexRecord, TAG_NTFS);
2012     if (IndexRecord == NULL)
2013     {
2014         ReleaseAttributeContext(IndexRootCtx);
2015         ExFreePoolWithTag(MftRecord, TAG_NTFS);
2016         return STATUS_INSUFFICIENT_RESOURCES;
2017     }
2018
2019     ReadAttribute(Vcb, IndexRootCtx, 0, IndexRecord, Vcb->NtfsInfo.BytesPerIndexRecord);
2020     IndexRoot = (PINDEX_ROOT_ATTRIBUTE)IndexRecord;
2021     IndexEntry = (PINDEX_ENTRY_ATTRIBUTE)((PCHAR)&IndexRoot->Header + IndexRoot->Header.FirstEntryOffset);
2022     /* Index root is always resident. */
2023     IndexEntryEnd = (PINDEX_ENTRY_ATTRIBUTE)(IndexRecord + IndexRoot->Header.TotalSizeOfEntries);
2024     ReleaseAttributeContext(IndexRootCtx);
2025
2026     DPRINT("IndexRecordSize: %x IndexBlockSize: %x\n", Vcb->NtfsInfo.BytesPerIndexRecord, IndexRoot->SizeOfEntry);
2027
2028     Status = BrowseIndexEntries(Vcb, MftRecord, IndexRecord, IndexRoot->SizeOfEntry, IndexEntry, IndexEntryEnd, FileName, FirstEntry, &CurrentEntry, DirSearch, OutMFTIndex);
2029
2030     ExFreePoolWithTag(IndexRecord, TAG_NTFS);
2031     ExFreePoolWithTag(MftRecord, TAG_NTFS);
2032
2033     return Status;
2034 }
2035
2036 NTSTATUS
2037 NtfsLookupFileAt(PDEVICE_EXTENSION Vcb,
2038                  PUNICODE_STRING PathName,
2039                  PFILE_RECORD_HEADER *FileRecord,
2040                  PULONGLONG MFTIndex,
2041                  ULONGLONG CurrentMFTIndex)
2042 {
2043     UNICODE_STRING Current, Remaining;
2044     NTSTATUS Status;
2045     ULONG FirstEntry = 0;
2046
2047     DPRINT("NtfsLookupFileAt(%p, %wZ, %p, %I64x)\n", Vcb, PathName, FileRecord, CurrentMFTIndex);
2048
2049     FsRtlDissectName(*PathName, &Current, &Remaining);
2050
2051     while (Current.Length != 0)
2052     {
2053         DPRINT("Current: %wZ\n", &Current);
2054
2055         Status = NtfsFindMftRecord(Vcb, CurrentMFTIndex, &Current, &FirstEntry, FALSE, &CurrentMFTIndex);
2056         if (!NT_SUCCESS(Status))
2057         {
2058             return Status;
2059         }
2060
2061         if (Remaining.Length == 0)
2062             break;
2063
2064         FsRtlDissectName(Current, &Current, &Remaining);
2065     }
2066
2067     *FileRecord = ExAllocatePoolWithTag(NonPagedPool, Vcb->NtfsInfo.BytesPerFileRecord, TAG_NTFS);
2068     if (*FileRecord == NULL)
2069     {
2070         DPRINT("NtfsLookupFileAt: Can't allocate MFT record\n");
2071         return STATUS_INSUFFICIENT_RESOURCES;
2072     }
2073
2074     Status = ReadFileRecord(Vcb, CurrentMFTIndex, *FileRecord);
2075     if (!NT_SUCCESS(Status))
2076     {
2077         DPRINT("NtfsLookupFileAt: Can't read MFT record\n");
2078         ExFreePoolWithTag(*FileRecord, TAG_NTFS);
2079         return Status;
2080     }
2081
2082     *MFTIndex = CurrentMFTIndex;
2083
2084     return STATUS_SUCCESS;
2085 }
2086
2087 NTSTATUS
2088 NtfsLookupFile(PDEVICE_EXTENSION Vcb,
2089                PUNICODE_STRING PathName,
2090                PFILE_RECORD_HEADER *FileRecord,
2091                PULONGLONG MFTIndex)
2092 {
2093     return NtfsLookupFileAt(Vcb, PathName, FileRecord, MFTIndex, NTFS_FILE_ROOT);
2094 }
2095
2096 /**
2097 * @name NtfsDumpFileRecord
2098 * @implemented
2099 *
2100 * Provides diagnostic information about a file record. Prints a hex dump
2101 * of the entire record (based on the size reported by FileRecord->ByesInUse),
2102 * then prints a dump of each attribute.
2103 *
2104 * @param Vcb
2105 * Pointer to a DEVICE_EXTENSION describing the volume.
2106 *
2107 * @param FileRecord
2108 * Pointer to the file record to be analyzed.
2109 *
2110 * @remarks
2111 * FileRecord must be a complete file record at least FileRecord->BytesAllocated
2112 * in size, and not just the header.
2113 *
2114 */
2115 VOID
2116 NtfsDumpFileRecord(PDEVICE_EXTENSION Vcb,
2117                    PFILE_RECORD_HEADER FileRecord)
2118 {
2119     ULONG i, j;
2120
2121     // dump binary data, 8 bytes at a time
2122     for (i = 0; i < FileRecord->BytesInUse; i += 8)
2123     {
2124         // display current offset, in hex
2125         DbgPrint("\t%03x\t", i);
2126
2127         // display hex value of each of the next 8 bytes
2128         for (j = 0; j < 8; j++)
2129             DbgPrint("%02x ", *(PUCHAR)((ULONG_PTR)FileRecord + i + j));
2130         DbgPrint("\n");
2131     }
2132
2133     NtfsDumpFileAttributes(Vcb, FileRecord);
2134 }
2135
2136 NTSTATUS
2137 NtfsFindFileAt(PDEVICE_EXTENSION Vcb,
2138                PUNICODE_STRING SearchPattern,
2139                PULONG FirstEntry,
2140                PFILE_RECORD_HEADER *FileRecord,
2141                PULONGLONG MFTIndex,
2142                ULONGLONG CurrentMFTIndex)
2143 {
2144     NTSTATUS Status;
2145
2146     DPRINT("NtfsFindFileAt(%p, %wZ, %u, %p, %p, %I64x)\n", Vcb, SearchPattern, *FirstEntry, FileRecord, MFTIndex, CurrentMFTIndex);
2147
2148     Status = NtfsFindMftRecord(Vcb, CurrentMFTIndex, SearchPattern, FirstEntry, TRUE, &CurrentMFTIndex);
2149     if (!NT_SUCCESS(Status))
2150     {
2151         DPRINT("NtfsFindFileAt: NtfsFindMftRecord() failed with status 0x%08lx\n", Status);
2152         return Status;
2153     }
2154
2155     *FileRecord = ExAllocatePoolWithTag(NonPagedPool, Vcb->NtfsInfo.BytesPerFileRecord, TAG_NTFS);
2156     if (*FileRecord == NULL)
2157     {
2158         DPRINT("NtfsFindFileAt: Can't allocate MFT record\n");
2159         return STATUS_INSUFFICIENT_RESOURCES;
2160     }
2161
2162     Status = ReadFileRecord(Vcb, CurrentMFTIndex, *FileRecord);
2163     if (!NT_SUCCESS(Status))
2164     {
2165         DPRINT("NtfsFindFileAt: Can't read MFT record\n");
2166         ExFreePoolWithTag(*FileRecord, TAG_NTFS);
2167         return Status;
2168     }
2169
2170     *MFTIndex = CurrentMFTIndex;
2171
2172     return STATUS_SUCCESS;
2173 }
2174
2175 /* EOF */