reactos/boot/freeldr/freeldr/fs/ntfs.c

   1 /*
   2  *  FreeLoader NTFS support
   3  *  Copyright (C) 2004  Filip Navara  <xnavara@volny.cz>
   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 along
  16  *  with this program; if not, write to the Free Software Foundation, Inc.,
  17  *  51 Franklin Street, Fifth Floor, Boston, MA 02110-1301 USA.
  18  */
  19
  20 /*
  21  * Limitations:
  22  * - No support for compressed files.
  23  * - May crash on corrupted filesystem.
  24  */
  25
  26 #include <freeldr.h>
  27 #include <debug.h>
  28
  29 typedef struct _NTFS_VOLUME_INFO
  30 {
  31     NTFS_BOOTSECTOR BootSector;
  32     ULONG ClusterSize;
  33     ULONG MftRecordSize;
  34     ULONG IndexRecordSize;
  35     PNTFS_MFT_RECORD MasterFileTable;
  36     /* FIXME: MFTContext is never freed. */
  37     PNTFS_ATTR_CONTEXT MFTContext;
  38     ULONG DeviceId;
  39 } NTFS_VOLUME_INFO;
  40
  41 PNTFS_VOLUME_INFO NtfsVolumes[MAX_FDS];
  42
  43 static ULONGLONG NtfsGetAttributeSize(PNTFS_ATTR_RECORD AttrRecord)
  44 {
  45     if (AttrRecord->IsNonResident)
  46         return AttrRecord->NonResident.DataSize;
  47     else
  48         return AttrRecord->Resident.ValueLength;
  49 }
  50
  51 static PUCHAR NtfsDecodeRun(PUCHAR DataRun, LONGLONG *DataRunOffset, ULONGLONG *DataRunLength)
  52 {
  53     UCHAR DataRunOffsetSize;
  54     UCHAR DataRunLengthSize;
  55     CHAR i;
  56
  57     DataRunOffsetSize = (*DataRun >> 4) & 0xF;
  58     DataRunLengthSize = *DataRun & 0xF;
  59     *DataRunOffset = 0;
  60     *DataRunLength = 0;
  61     DataRun++;
  62     for (i = 0; i < DataRunLengthSize; i++)
  63     {
  64         *DataRunLength += *DataRun << (i << 3);
  65         DataRun++;
  66     }
  67
  68     /* NTFS 3+ sparse files */
  69     if (DataRunOffsetSize == 0)
  70     {
  71         *DataRunOffset = -1;
  72     }
  73     else
  74     {
  75         for (i = 0; i < DataRunOffsetSize - 1; i++)
  76         {
  77             *DataRunOffset += *DataRun << (i << 3);
  78             DataRun++;
  79         }
  80         /* The last byte contains sign so we must process it different way. */
  81         *DataRunOffset = ((CHAR)(*(DataRun++)) << (i << 3)) + *DataRunOffset;
  82     }
  83
  84     DPRINTM(DPRINT_FILESYSTEM, "DataRunOffsetSize: %x\n", DataRunOffsetSize);
  85     DPRINTM(DPRINT_FILESYSTEM, "DataRunLengthSize: %x\n", DataRunLengthSize);
  86     DPRINTM(DPRINT_FILESYSTEM, "DataRunOffset: %x\n", *DataRunOffset);
  87     DPRINTM(DPRINT_FILESYSTEM, "DataRunLength: %x\n", *DataRunLength);
  88
  89     return DataRun;
  90 }
  91
  92 static PNTFS_ATTR_CONTEXT NtfsPrepareAttributeContext(PNTFS_ATTR_RECORD AttrRecord)
  93 {
  94     PNTFS_ATTR_CONTEXT Context;
  95
  96     Context = MmHeapAlloc(FIELD_OFFSET(NTFS_ATTR_CONTEXT, Record) + AttrRecord->Length);
  97     RtlCopyMemory(&Context->Record, AttrRecord, AttrRecord->Length);
  98     if (AttrRecord->IsNonResident)
  99     {
 100         LONGLONG DataRunOffset;
 101         ULONGLONG DataRunLength;
 102
 103         Context->CacheRun = (PUCHAR)&Context->Record + Context->Record.NonResident.MappingPairsOffset;
 104         Context->CacheRunOffset = 0;
 105         Context->CacheRun = NtfsDecodeRun(Context->CacheRun, &DataRunOffset, &DataRunLength);
 106         Context->CacheRunLength = DataRunLength;
 107         if (DataRunOffset != -1)
 108         {
 109             /* Normal run. */
 110             Context->CacheRunStartLCN =
 111             Context->CacheRunLastLCN = DataRunOffset;
 112         }
 113         else
 114         {
 115             /* Sparse run. */
 116             Context->CacheRunStartLCN = -1;
 117             Context->CacheRunLastLCN = 0;
 118         }
 119         Context->CacheRunCurrentOffset = 0;
 120     }
 121
 122     return Context;
 123 }
 124
 125 static VOID NtfsReleaseAttributeContext(PNTFS_ATTR_CONTEXT Context)
 126 {
 127     MmHeapFree(Context);
 128 }
 129
 130 static BOOLEAN NtfsDiskRead(PNTFS_VOLUME_INFO Volume, ULONGLONG Offset, ULONGLONG Length, PCHAR Buffer)
 131 {
 132     LARGE_INTEGER Position;
 133     ULONG Count;
 134     USHORT ReadLength;
 135     LONG ret;
 136
 137     DPRINTM(DPRINT_FILESYSTEM, "NtfsDiskRead - Offset: %I64d Length: %I64d\n", Offset, Length);
 138
 139     //
 140     // I. Read partial first sector if needed
 141     //
 142     if (Offset % Volume->BootSector.BytesPerSector)
 143     {
 144         Position.HighPart = 0;
 145         Position.LowPart = Offset & ~(Volume->BootSector.BytesPerSector - 1);
 146         ret = ArcSeek(Volume->DeviceId, &Position, SeekAbsolute);
 147         if (ret != ESUCCESS)
 148             return FALSE;
 149         ReadLength = min(Length, Volume->BootSector.BytesPerSector - (Offset % Volume->BootSector.BytesPerSector));
 150         ret = ArcRead(Volume->DeviceId, Buffer, ReadLength, &Count);
 151         if (ret != ESUCCESS || Count != ReadLength)
 152             return FALSE;
 153
 154         //
 155         // Move to unfilled buffer part
 156         //
 157         Buffer += ReadLength;
 158         Length -= ReadLength;
 159         Offset += ReadLength;
 160     }
 161
 162     //
 163     // II. Read all complete blocks
 164     //
 165     if (Length >= Volume->BootSector.BytesPerSector)
 166     {
 167         Position.HighPart = 0;
 168         Position.LowPart = Offset;
 169         ret = ArcSeek(Volume->DeviceId, &Position, SeekAbsolute);
 170         if (ret != ESUCCESS)
 171             return FALSE;
 172         ReadLength = Length & ~(Volume->BootSector.BytesPerSector - 1);
 173         ret = ArcRead(Volume->DeviceId, Buffer, ReadLength, &Count);
 174         if (ret != ESUCCESS || Count != ReadLength)
 175             return FALSE;
 176
 177         //
 178         // Move to unfilled buffer part
 179         //
 180         Buffer += ReadLength;
 181         Length -= ReadLength;
 182         Offset += ReadLength;
 183     }
 184
 185     //
 186     // III. Read the rest of data
 187     //
 188     if (Length)
 189     {
 190         Position.HighPart = 0;
 191         Position.LowPart = Offset;
 192         ret = ArcSeek(Volume->DeviceId, &Position, SeekAbsolute);
 193         if (ret != ESUCCESS)
 194             return FALSE;
 195         ret = ArcRead(Volume->DeviceId, Buffer, Length, &Count);
 196         if (ret != ESUCCESS || Count != Length)
 197             return FALSE;
 198     }
 199
 200     return TRUE;
 201 }
 202
 203 static ULONGLONG NtfsReadAttribute(PNTFS_VOLUME_INFO Volume, PNTFS_ATTR_CONTEXT Context, ULONGLONG Offset, PCHAR Buffer, ULONGLONG Length)
 204 {
 205     ULONGLONG LastLCN;
 206     PUCHAR DataRun;
 207     LONGLONG DataRunOffset;
 208     ULONGLONG DataRunLength;
 209     LONGLONG DataRunStartLCN;
 210     ULONGLONG CurrentOffset;
 211     ULONGLONG ReadLength;
 212     ULONGLONG AlreadyRead;
 213
 214     if (!Context->Record.IsNonResident)
 215     {
 216         if (Offset > Context->Record.Resident.ValueLength)
 217             return 0;
 218         if (Offset + Length > Context->Record.Resident.ValueLength)
 219             Length = Context->Record.Resident.ValueLength - Offset;
 220         RtlCopyMemory(Buffer, (PCHAR)&Context->Record + Context->Record.Resident.ValueOffset + Offset, Length);
 221         return Length;
 222     }
 223
 224     /*
 225      * Non-resident attribute
 226      */
 227
 228     /*
 229      * I. Find the corresponding start data run.
 230      */
 231
 232     AlreadyRead = 0;
 233
 234     if(Context->CacheRunOffset <= Offset && Offset < Context->CacheRunOffset + Context->CacheRunLength * Volume->ClusterSize)
 235     {
 236         DataRun = Context->CacheRun;
 237         LastLCN = Context->CacheRunLastLCN;
 238         DataRunStartLCN = Context->CacheRunStartLCN;
 239         DataRunLength = Context->CacheRunLength;
 240         CurrentOffset = Context->CacheRunCurrentOffset;
 241     }
 242     else
 243     {
 244         LastLCN = 0;
 245         DataRun = (PUCHAR)&Context->Record + Context->Record.NonResident.MappingPairsOffset;
 246         CurrentOffset = 0;
 247
 248         while (1)
 249         {
 250             DataRun = NtfsDecodeRun(DataRun, &DataRunOffset, &DataRunLength);
 251             if (DataRunOffset != -1)
 252             {
 253                 /* Normal data run. */
 254                 DataRunStartLCN = LastLCN + DataRunOffset;
 255                 LastLCN = DataRunStartLCN;
 256             }
 257             else
 258             {
 259                 /* Sparse data run. */
 260                 DataRunStartLCN = -1;
 261             }
 262
 263             if (Offset >= CurrentOffset &&
 264                 Offset < CurrentOffset + (DataRunLength * Volume->ClusterSize))
 265             {
 266                 break;
 267             }
 268
 269             if (*DataRun == 0)
 270             {
 271                 return AlreadyRead;
 272             }
 273
 274             CurrentOffset += DataRunLength * Volume->ClusterSize;
 275         }
 276     }
 277
 278     /*
 279      * II. Go through the run list and read the data
 280      */
 281
 282     ReadLength = min(DataRunLength * Volume->ClusterSize - (Offset - CurrentOffset), Length);
 283     if (DataRunStartLCN == -1)
 284     RtlZeroMemory(Buffer, ReadLength);
 285     if (NtfsDiskRead(Volume, DataRunStartLCN * Volume->ClusterSize + Offset - CurrentOffset, ReadLength, Buffer))
 286     {
 287         Length -= ReadLength;
 288         Buffer += ReadLength;
 289         AlreadyRead += ReadLength;
 290
 291         if (ReadLength == DataRunLength * Volume->ClusterSize - (Offset - CurrentOffset))
 292         {
 293             CurrentOffset += DataRunLength * Volume->ClusterSize;
 294             DataRun = NtfsDecodeRun(DataRun, &DataRunOffset, &DataRunLength);
 295             if (DataRunLength != (ULONGLONG)-1)
 296             {
 297                 DataRunStartLCN = LastLCN + DataRunOffset;
 298                 LastLCN = DataRunStartLCN;
 299             }
 300             else
 301                 DataRunStartLCN = -1;
 302
 303             if (*DataRun == 0)
 304                 return AlreadyRead;
 305         }
 306
 307         while (Length > 0)
 308         {
 309             ReadLength = min(DataRunLength * Volume->ClusterSize, Length);
 310             if (DataRunStartLCN == -1)
 311                 RtlZeroMemory(Buffer, ReadLength);
 312             else if (!NtfsDiskRead(Volume, DataRunStartLCN * Volume->ClusterSize, ReadLength, Buffer))
 313                 break;
 314
 315             Length -= ReadLength;
 316             Buffer += ReadLength;
 317             AlreadyRead += ReadLength;
 318
 319             /* We finished this request, but there still data in this data run. */
 320             if (Length == 0 && ReadLength != DataRunLength * Volume->ClusterSize)
 321                 break;
 322
 323             /*
 324              * Go to next run in the list.
 325              */
 326
 327             if (*DataRun == 0)
 328                 break;
 329             CurrentOffset += DataRunLength * Volume->ClusterSize;
 330             DataRun = NtfsDecodeRun(DataRun, &DataRunOffset, &DataRunLength);
 331             if (DataRunOffset != -1)
 332             {
 333                 /* Normal data run. */
 334                 DataRunStartLCN = LastLCN + DataRunOffset;
 335                 LastLCN = DataRunStartLCN;
 336             }
 337             else
 338             {
 339                 /* Sparse data run. */
 340                 DataRunStartLCN = -1;
 341             }
 342         } /* while */
 343
 344     } /* if Disk */
 345
 346     Context->CacheRun = DataRun;
 347     Context->CacheRunOffset = Offset + AlreadyRead;
 348     Context->CacheRunStartLCN = DataRunStartLCN;
 349     Context->CacheRunLength = DataRunLength;
 350     Context->CacheRunLastLCN = LastLCN;
 351     Context->CacheRunCurrentOffset = CurrentOffset;
 352
 353     return AlreadyRead;
 354 }
 355
 356 static PNTFS_ATTR_CONTEXT NtfsFindAttributeHelper(PNTFS_VOLUME_INFO Volume, PNTFS_ATTR_RECORD AttrRecord, PNTFS_ATTR_RECORD AttrRecordEnd, ULONG Type, const WCHAR *Name, ULONG NameLength)
 357 {
 358     while (AttrRecord < AttrRecordEnd)
 359     {
 360         if (AttrRecord->Type == NTFS_ATTR_TYPE_END)
 361             break;
 362
 363         if (AttrRecord->Type == NTFS_ATTR_TYPE_ATTRIBUTE_LIST)
 364         {
 365             PNTFS_ATTR_CONTEXT Context;
 366             PNTFS_ATTR_CONTEXT ListContext;
 367             PVOID ListBuffer;
 368             ULONGLONG ListSize;
 369             PNTFS_ATTR_RECORD ListAttrRecord;
 370             PNTFS_ATTR_RECORD ListAttrRecordEnd;
 371
 372             ListContext = NtfsPrepareAttributeContext(AttrRecord);
 373
 374             ListSize = NtfsGetAttributeSize(&ListContext->Record);
 375             ListBuffer = MmHeapAlloc(ListSize);
 376
 377             ListAttrRecord = (PNTFS_ATTR_RECORD)ListBuffer;
 378             ListAttrRecordEnd = (PNTFS_ATTR_RECORD)((PCHAR)ListBuffer + ListSize);
 379
 380             if (NtfsReadAttribute(Volume, ListContext, 0, ListBuffer, ListSize) == ListSize)
 381             {
 382                 Context = NtfsFindAttributeHelper(Volume, ListAttrRecord, ListAttrRecordEnd,
 383                                                   Type, Name, NameLength);
 384
 385                 NtfsReleaseAttributeContext(ListContext);
 386                 MmHeapFree(ListBuffer);
 387
 388                 if (Context != NULL)
 389                     return Context;
 390             }
 391         }
 392
 393         if (AttrRecord->Type == Type)
 394         {
 395             if (AttrRecord->NameLength == NameLength)
 396             {
 397                 PWCHAR AttrName;
 398
 399                 AttrName = (PWCHAR)((PCHAR)AttrRecord + AttrRecord->NameOffset);
 400                 if (RtlEqualMemory(AttrName, Name, NameLength << 1))
 401                 {
 402                     /* Found it, fill up the context and return. */
 403                     return NtfsPrepareAttributeContext(AttrRecord);
 404                 }
 405             }
 406         }
 407
 408         if (AttrRecord->Length == 0)
 409             return NULL;
 410         AttrRecord = (PNTFS_ATTR_RECORD)((PCHAR)AttrRecord + AttrRecord->Length);
 411     }
 412
 413     return NULL;
 414 }
 415
 416 static PNTFS_ATTR_CONTEXT NtfsFindAttribute(PNTFS_VOLUME_INFO Volume, PNTFS_MFT_RECORD MftRecord, ULONG Type, const WCHAR *Name)
 417 {
 418     PNTFS_ATTR_RECORD AttrRecord;
 419     PNTFS_ATTR_RECORD AttrRecordEnd;
 420     ULONG NameLength;
 421
 422     AttrRecord = (PNTFS_ATTR_RECORD)((PCHAR)MftRecord + MftRecord->AttributesOffset);
 423     AttrRecordEnd = (PNTFS_ATTR_RECORD)((PCHAR)MftRecord + Volume->MftRecordSize);
 424     for (NameLength = 0; Name[NameLength] != 0; NameLength++)
 425         ;
 426
 427     return NtfsFindAttributeHelper(Volume, AttrRecord, AttrRecordEnd, Type, Name, NameLength);
 428 }
 429
 430 static BOOLEAN NtfsFixupRecord(PNTFS_VOLUME_INFO Volume, PNTFS_RECORD Record)
 431 {
 432     USHORT *USA;
 433     USHORT USANumber;
 434     USHORT USACount;
 435     USHORT *Block;
 436
 437     USA = (USHORT*)((PCHAR)Record + Record->USAOffset);
 438     USANumber = *(USA++);
 439     USACount = Record->USACount - 1; /* Exclude the USA Number. */
 440     Block = (USHORT*)((PCHAR)Record + Volume->BootSector.BytesPerSector - 2);
 441
 442     while (USACount)
 443     {
 444         if (*Block != USANumber)
 445             return FALSE;
 446         *Block = *(USA++);
 447         Block = (USHORT*)((PCHAR)Block + Volume->BootSector.BytesPerSector);
 448         USACount--;
 449     }
 450
 451     return TRUE;
 452 }
 453
 454 static BOOLEAN NtfsReadMftRecord(PNTFS_VOLUME_INFO Volume, ULONG MFTIndex, PNTFS_MFT_RECORD Buffer)
 455 {
 456     ULONGLONG BytesRead;
 457
 458     BytesRead = NtfsReadAttribute(Volume, Volume->MFTContext, MFTIndex * Volume->MftRecordSize, (PCHAR)Buffer, Volume->MftRecordSize);
 459     if (BytesRead != Volume->MftRecordSize)
 460         return FALSE;
 461
 462     /* Apply update sequence array fixups. */
 463     return NtfsFixupRecord(Volume, (PNTFS_RECORD)Buffer);
 464 }
 465
 466 #if DBG
 467 VOID NtfsPrintFile(PNTFS_INDEX_ENTRY IndexEntry)
 468 {
 469     PWCHAR FileName;
 470     UCHAR FileNameLength;
 471     CHAR AnsiFileName[256];
 472     UCHAR i;
 473
 474     FileName = IndexEntry->FileName.FileName;
 475     FileNameLength = IndexEntry->FileName.FileNameLength;
 476
 477     for (i = 0; i < FileNameLength; i++)
 478         AnsiFileName[i] = FileName[i];
 479     AnsiFileName[i] = 0;
 480
 481     DPRINTM(DPRINT_FILESYSTEM, "- %s (%x)\n", AnsiFileName, IndexEntry->Data.Directory.IndexedFile);
 482 }
 483 #endif
 484
 485 static BOOLEAN NtfsCompareFileName(PCHAR FileName, PNTFS_INDEX_ENTRY IndexEntry)
 486 {
 487     PWCHAR EntryFileName;
 488     UCHAR EntryFileNameLength;
 489     UCHAR i;
 490
 491     EntryFileName = IndexEntry->FileName.FileName;
 492     EntryFileNameLength = IndexEntry->FileName.FileNameLength;
 493
 494 #if DBG
 495     NtfsPrintFile(IndexEntry);
 496 #endif
 497
 498     if (strlen(FileName) != EntryFileNameLength)
 499         return FALSE;
 500
 501     /* Do case-sensitive compares for Posix file names. */
 502     if (IndexEntry->FileName.FileNameType == NTFS_FILE_NAME_POSIX)
 503     {
 504         for (i = 0; i < EntryFileNameLength; i++)
 505             if (EntryFileName[i] != FileName[i])
 506                 return FALSE;
 507     }
 508     else
 509     {
 510         for (i = 0; i < EntryFileNameLength; i++)
 511             if (tolower(EntryFileName[i]) != tolower(FileName[i]))
 512                 return FALSE;
 513     }
 514
 515     return TRUE;
 516 }
 517
 518 static BOOLEAN NtfsFindMftRecord(PNTFS_VOLUME_INFO Volume, ULONG MFTIndex, PCHAR FileName, ULONG *OutMFTIndex)
 519 {
 520     PNTFS_MFT_RECORD MftRecord;
 521     ULONG Magic;
 522     PNTFS_ATTR_CONTEXT IndexRootCtx;
 523     PNTFS_ATTR_CONTEXT IndexBitmapCtx;
 524     PNTFS_ATTR_CONTEXT IndexAllocationCtx;
 525     PNTFS_INDEX_ROOT IndexRoot;
 526     ULONGLONG BitmapDataSize;
 527     ULONGLONG IndexAllocationSize;
 528     PCHAR BitmapData;
 529     PCHAR IndexRecord;
 530     PNTFS_INDEX_ENTRY IndexEntry, IndexEntryEnd;
 531     ULONG RecordOffset;
 532     ULONG IndexBlockSize;
 533
 534     MftRecord = MmHeapAlloc(Volume->MftRecordSize);
 535     if (MftRecord == NULL)
 536     {
 537         return FALSE;
 538     }
 539
 540     if (NtfsReadMftRecord(Volume, MFTIndex, MftRecord))
 541     {
 542         Magic = MftRecord->Magic;
 543
 544         IndexRootCtx = NtfsFindAttribute(Volume, MftRecord, NTFS_ATTR_TYPE_INDEX_ROOT, L"$I30");
 545         if (IndexRootCtx == NULL)
 546         {
 547             MmHeapFree(MftRecord);
 548             return FALSE;
 549         }
 550
 551         IndexRecord = MmHeapAlloc(Volume->IndexRecordSize);
 552         if (IndexRecord == NULL)
 553         {
 554             MmHeapFree(MftRecord);
 555             return FALSE;
 556         }
 557
 558         NtfsReadAttribute(Volume, IndexRootCtx, 0, IndexRecord, Volume->IndexRecordSize);
 559         IndexRoot = (PNTFS_INDEX_ROOT)IndexRecord;
 560         IndexEntry = (PNTFS_INDEX_ENTRY)((PCHAR)&IndexRoot->IndexHeader + IndexRoot->IndexHeader.EntriesOffset);
 561         /* Index root is always resident. */
 562         IndexEntryEnd = (PNTFS_INDEX_ENTRY)(IndexRecord + IndexRootCtx->Record.Resident.ValueLength);
 563         NtfsReleaseAttributeContext(IndexRootCtx);
 564
 565         DPRINTM(DPRINT_FILESYSTEM, "IndexRecordSize: %x IndexBlockSize: %x\n", Volume->IndexRecordSize, IndexRoot->IndexBlockSize);
 566
 567         while (IndexEntry < IndexEntryEnd &&
 568                !(IndexEntry->Flags & NTFS_INDEX_ENTRY_END))
 569         {
 570             if (NtfsCompareFileName(FileName, IndexEntry))
 571             {
 572                 *OutMFTIndex = IndexEntry->Data.Directory.IndexedFile;
 573                 MmHeapFree(IndexRecord);
 574                 MmHeapFree(MftRecord);
 575                 return TRUE;
 576             }
 577             IndexEntry = (PNTFS_INDEX_ENTRY)((PCHAR)IndexEntry + IndexEntry->Length);
 578         }
 579
 580         if (IndexRoot->IndexHeader.Flags & NTFS_LARGE_INDEX)
 581         {
 582             DPRINTM(DPRINT_FILESYSTEM, "Large Index!\n");
 583
 584             IndexBlockSize = IndexRoot->IndexBlockSize;
 585
 586             IndexBitmapCtx = NtfsFindAttribute(Volume, MftRecord, NTFS_ATTR_TYPE_BITMAP, L"$I30");
 587             if (IndexBitmapCtx == NULL)
 588             {
 589                 DPRINTM(DPRINT_FILESYSTEM, "Corrupted filesystem!\n");
 590                 MmHeapFree(MftRecord);
 591                 return FALSE;
 592             }
 593             BitmapDataSize = NtfsGetAttributeSize(&IndexBitmapCtx->Record);
 594             DPRINTM(DPRINT_FILESYSTEM, "BitmapDataSize: %x\n", BitmapDataSize);
 595             BitmapData = MmHeapAlloc(BitmapDataSize);
 596             if (BitmapData == NULL)
 597             {
 598                 MmHeapFree(IndexRecord);
 599                 MmHeapFree(MftRecord);
 600                 return FALSE;
 601             }
 602             NtfsReadAttribute(Volume, IndexBitmapCtx, 0, BitmapData, BitmapDataSize);
 603             NtfsReleaseAttributeContext(IndexBitmapCtx);
 604
 605             IndexAllocationCtx = NtfsFindAttribute(Volume, MftRecord, NTFS_ATTR_TYPE_INDEX_ALLOCATION, L"$I30");
 606             if (IndexAllocationCtx == NULL)
 607             {
 608                 DPRINTM(DPRINT_FILESYSTEM, "Corrupted filesystem!\n");
 609                 MmHeapFree(BitmapData);
 610                 MmHeapFree(IndexRecord);
 611                 MmHeapFree(MftRecord);
 612                 return FALSE;
 613             }
 614             IndexAllocationSize = NtfsGetAttributeSize(&IndexAllocationCtx->Record);
 615
 616             RecordOffset = 0;
 617
 618             for (;;)
 619             {
 620                 DPRINTM(DPRINT_FILESYSTEM, "RecordOffset: %x IndexAllocationSize: %x\n", RecordOffset, IndexAllocationSize);
 621                 for (; RecordOffset < IndexAllocationSize;)
 622                 {
 623                     UCHAR Bit = 1 << ((RecordOffset / IndexBlockSize) & 7);
 624                     ULONG Byte = (RecordOffset / IndexBlockSize) >> 3;
 625                     if ((BitmapData[Byte] & Bit))
 626                         break;
 627                     RecordOffset += IndexBlockSize;
 628                 }
 629
 630                 if (RecordOffset >= IndexAllocationSize)
 631                 {
 632                     break;
 633                 }
 634
 635                 NtfsReadAttribute(Volume, IndexAllocationCtx, RecordOffset, IndexRecord, IndexBlockSize);
 636
 637                 if (!NtfsFixupRecord(Volume, (PNTFS_RECORD)IndexRecord))
 638                 {
 639                     break;
 640                 }
 641
 642                 /* FIXME */
 643                 IndexEntry = (PNTFS_INDEX_ENTRY)(IndexRecord + 0x18 + *(USHORT *)(IndexRecord + 0x18));
 644                 IndexEntryEnd = (PNTFS_INDEX_ENTRY)(IndexRecord + IndexBlockSize);
 645
 646                 while (IndexEntry < IndexEntryEnd &&
 647                        !(IndexEntry->Flags & NTFS_INDEX_ENTRY_END))
 648                 {
 649                     if (NtfsCompareFileName(FileName, IndexEntry))
 650                     {
 651                         DPRINTM(DPRINT_FILESYSTEM, "File found\n");
 652                         *OutMFTIndex = IndexEntry->Data.Directory.IndexedFile;
 653                         MmHeapFree(BitmapData);
 654                         MmHeapFree(IndexRecord);
 655                         MmHeapFree(MftRecord);
 656                         NtfsReleaseAttributeContext(IndexAllocationCtx);
 657                         return TRUE;
 658                     }
 659                     IndexEntry = (PNTFS_INDEX_ENTRY)((PCHAR)IndexEntry + IndexEntry->Length);
 660                 }
 661
 662                 RecordOffset += IndexBlockSize;
 663             }
 664
 665             NtfsReleaseAttributeContext(IndexAllocationCtx);
 666             MmHeapFree(BitmapData);
 667         }
 668
 669         MmHeapFree(IndexRecord);
 670     }
 671     else
 672     {
 673         DPRINTM(DPRINT_FILESYSTEM, "Can't read MFT record\n");
 674     }
 675     MmHeapFree(MftRecord);
 676
 677     return FALSE;
 678 }
 679
 680 static BOOLEAN NtfsLookupFile(PNTFS_VOLUME_INFO Volume, PCSTR FileName, PNTFS_MFT_RECORD MftRecord, PNTFS_ATTR_CONTEXT *DataContext)
 681 {
 682     ULONG NumberOfPathParts;
 683     CHAR PathPart[261];
 684     ULONG CurrentMFTIndex;
 685     UCHAR i;
 686
 687     DPRINTM(DPRINT_FILESYSTEM, "NtfsLookupFile() FileName = %s\n", FileName);
 688
 689     CurrentMFTIndex = NTFS_FILE_ROOT;
 690     NumberOfPathParts = FsGetNumPathParts(FileName);
 691     for (i = 0; i < NumberOfPathParts; i++)
 692     {
 693         FsGetFirstNameFromPath(PathPart, FileName);
 694
 695         for (; (*FileName != '\\') && (*FileName != '/') && (*FileName != '\0'); FileName++)
 696             ;
 697         FileName++;
 698
 699         DPRINTM(DPRINT_FILESYSTEM, "- Lookup: %s\n", PathPart);
 700         if (!NtfsFindMftRecord(Volume, CurrentMFTIndex, PathPart, &CurrentMFTIndex))
 701         {
 702             DPRINTM(DPRINT_FILESYSTEM, "- Failed\n");
 703             return FALSE;
 704         }
 705         DPRINTM(DPRINT_FILESYSTEM, "- Lookup: %x\n", CurrentMFTIndex);
 706     }
 707
 708     if (!NtfsReadMftRecord(Volume, CurrentMFTIndex, MftRecord))
 709     {
 710         DPRINTM(DPRINT_FILESYSTEM, "NtfsLookupFile: Can't read MFT record\n");
 711         return FALSE;
 712     }
 713
 714     *DataContext = NtfsFindAttribute(Volume, MftRecord, NTFS_ATTR_TYPE_DATA, L"");
 715     if (*DataContext == NULL)
 716     {
 717         DPRINTM(DPRINT_FILESYSTEM, "NtfsLookupFile: Can't find data attribute\n");
 718         return FALSE;
 719     }
 720
 721     return TRUE;
 722 }
 723
 724 LONG NtfsClose(ULONG FileId)
 725 {
 726     PNTFS_FILE_HANDLE FileHandle = FsGetDeviceSpecific(FileId);
 727
 728     NtfsReleaseAttributeContext(FileHandle->DataContext);
 729     MmHeapFree(FileHandle);
 730
 731     return ESUCCESS;
 732 }
 733
 734 LONG NtfsGetFileInformation(ULONG FileId, FILEINFORMATION* Information)
 735 {
 736     PNTFS_FILE_HANDLE FileHandle = FsGetDeviceSpecific(FileId);
 737
 738     RtlZeroMemory(Information, sizeof(FILEINFORMATION));
 739     Information->EndingAddress.LowPart = (ULONG)NtfsGetAttributeSize(&FileHandle->DataContext->Record);
 740     Information->CurrentAddress.LowPart = FileHandle->Offset;
 741
 742     DPRINTM(DPRINT_FILESYSTEM, "NtfsGetFileInformation() FileSize = %d\n",
 743         Information->EndingAddress.LowPart);
 744     DPRINTM(DPRINT_FILESYSTEM, "NtfsGetFileInformation() FilePointer = %d\n",
 745         Information->CurrentAddress.LowPart);
 746
 747     return ESUCCESS;
 748 }
 749
 750 LONG NtfsOpen(CHAR* Path, OPENMODE OpenMode, ULONG* FileId)
 751 {
 752     PNTFS_VOLUME_INFO Volume;
 753     PNTFS_FILE_HANDLE FileHandle;
 754     PNTFS_MFT_RECORD MftRecord;
 755     ULONG DeviceId;
 756
 757     //
 758     // Check parameters
 759     //
 760     if (OpenMode != OpenReadOnly)
 761         return EACCES;
 762
 763     //
 764     // Get underlying device
 765     //
 766     DeviceId = FsGetDeviceId(*FileId);
 767     Volume = NtfsVolumes[DeviceId];
 768
 769     DPRINTM(DPRINT_FILESYSTEM, "NtfsOpen() FileName = %s\n", Path);
 770
 771     //
 772     // Allocate file structure
 773     //
 774     FileHandle = MmHeapAlloc(sizeof(NTFS_FILE_HANDLE) + Volume->MftRecordSize);
 775     if (!FileHandle)
 776     {
 777         return ENOMEM;
 778     }
 779     RtlZeroMemory(FileHandle, sizeof(NTFS_FILE_HANDLE) + Volume->MftRecordSize);
 780     FileHandle->Volume = Volume;
 781
 782     //
 783     // Search file entry
 784     //
 785     MftRecord = (PNTFS_MFT_RECORD)(FileHandle + 1);
 786     if (!NtfsLookupFile(Volume, Path, MftRecord, &FileHandle->DataContext))
 787     {
 788         MmHeapFree(FileHandle);
 789         return ENOENT;
 790     }
 791
 792     return ESUCCESS;
 793 }
 794
 795 LONG NtfsRead(ULONG FileId, VOID* Buffer, ULONG N, ULONG* Count)
 796 {
 797     PNTFS_FILE_HANDLE FileHandle = FsGetDeviceSpecific(FileId);
 798     ULONGLONG BytesRead64;
 799
 800     //
 801     // Read file
 802     //
 803     BytesRead64 = NtfsReadAttribute(FileHandle->Volume, FileHandle->DataContext, FileHandle->Offset, Buffer, N);
 804     *Count = (ULONG)BytesRead64;
 805
 806     //
 807     // Check for success
 808     //
 809     if (BytesRead64 > 0)
 810         return ESUCCESS;
 811     else
 812         return EIO;
 813 }
 814
 815 LONG NtfsSeek(ULONG FileId, LARGE_INTEGER* Position, SEEKMODE SeekMode)
 816 {
 817     PNTFS_FILE_HANDLE FileHandle = FsGetDeviceSpecific(FileId);
 818
 819     DPRINTM(DPRINT_FILESYSTEM, "NtfsSeek() NewFilePointer = %lu\n", Position->LowPart);
 820
 821     if (SeekMode != SeekAbsolute)
 822         return EINVAL;
 823     if (Position->HighPart != 0)
 824         return EINVAL;
 825     if (Position->LowPart >= (ULONG)NtfsGetAttributeSize(&FileHandle->DataContext->Record))
 826         return EINVAL;
 827
 828     FileHandle->Offset = Position->LowPart;
 829     return ESUCCESS;
 830 }
 831
 832 const DEVVTBL NtfsFuncTable =
 833 {
 834     NtfsClose,
 835     NtfsGetFileInformation,
 836     NtfsOpen,
 837     NtfsRead,
 838     NtfsSeek,
 839     L"ntfs",
 840 };
 841
 842 const DEVVTBL* NtfsMount(ULONG DeviceId)
 843 {
 844     PNTFS_VOLUME_INFO Volume;
 845     LARGE_INTEGER Position;
 846     ULONG Count;
 847     LONG ret;
 848
 849     //
 850     // Allocate data for volume information
 851     //
 852     Volume = MmHeapAlloc(sizeof(NTFS_VOLUME_INFO));
 853     if (!Volume)
 854         return NULL;
 855     RtlZeroMemory(Volume, sizeof(NTFS_VOLUME_INFO));
 856
 857     //
 858     // Read the BootSector
 859     //
 860     Position.HighPart = 0;
 861     Position.LowPart = 0;
 862     ret = ArcSeek(DeviceId, &Position, SeekAbsolute);
 863     if (ret != ESUCCESS)
 864     {
 865         MmHeapFree(Volume);
 866         return NULL;
 867     }
 868     ret = ArcRead(DeviceId, &Volume->BootSector, sizeof(Volume->BootSector), &Count);
 869     if (ret != ESUCCESS || Count != sizeof(Volume->BootSector))
 870     {
 871         MmHeapFree(Volume);
 872         return NULL;
 873     }
 874
 875     //
 876     // Check if BootSector is valid. If no, return early
 877     //
 878     if (!RtlEqualMemory(Volume->BootSector.SystemId, "NTFS", 4))
 879     {
 880         MmHeapFree(Volume);
 881         return NULL;
 882     }
 883
 884     //
 885     // Calculate cluster size and MFT record size
 886     //
 887     Volume->ClusterSize = Volume->BootSector.SectorsPerCluster * Volume->BootSector.BytesPerSector;
 888     if (Volume->BootSector.ClustersPerMftRecord > 0)
 889         Volume->MftRecordSize = Volume->BootSector.ClustersPerMftRecord * Volume->ClusterSize;
 890     else
 891         Volume->MftRecordSize = 1 << (-Volume->BootSector.ClustersPerMftRecord);
 892     if (Volume->BootSector.ClustersPerIndexRecord > 0)
 893         Volume->IndexRecordSize = Volume->BootSector.ClustersPerIndexRecord * Volume->ClusterSize;
 894     else
 895         Volume->IndexRecordSize = 1 << (-Volume->BootSector.ClustersPerIndexRecord);
 896
 897     DPRINTM(DPRINT_FILESYSTEM, "ClusterSize: 0x%x\n", Volume->ClusterSize);
 898     DPRINTM(DPRINT_FILESYSTEM, "ClustersPerMftRecord: %d\n", Volume->BootSector.ClustersPerMftRecord);
 899     DPRINTM(DPRINT_FILESYSTEM, "ClustersPerIndexRecord: %d\n", Volume->BootSector.ClustersPerIndexRecord);
 900     DPRINTM(DPRINT_FILESYSTEM, "MftRecordSize: 0x%x\n", Volume->MftRecordSize);
 901     DPRINTM(DPRINT_FILESYSTEM, "IndexRecordSize: 0x%x\n", Volume->IndexRecordSize);
 902
 903     //
 904     // Read MFT index
 905     //
 906     DPRINTM(DPRINT_FILESYSTEM, "Reading MFT index...\n");
 907     Volume->MasterFileTable = MmHeapAlloc(Volume->MftRecordSize);
 908     if (!Volume->MasterFileTable)
 909     {
 910         MmHeapFree(Volume);
 911         return NULL;
 912     }
 913     Position.HighPart = 0;
 914     Position.LowPart = Volume->BootSector.MftLocation * Volume->ClusterSize;
 915     ret = ArcSeek(DeviceId, &Position, SeekAbsolute);
 916     if (ret != ESUCCESS)
 917     {
 918         FileSystemError("Failed to seek to Master File Table record.");
 919         MmHeapFree(Volume->MasterFileTable);
 920         MmHeapFree(Volume);
 921         return NULL;
 922     }
 923     ret = ArcRead(DeviceId, Volume->MasterFileTable, Volume->MftRecordSize, &Count);
 924     if (ret != ESUCCESS || Count != Volume->MftRecordSize)
 925     {
 926         FileSystemError("Failed to read the Master File Table record.");
 927         MmHeapFree(Volume->MasterFileTable);
 928         MmHeapFree(Volume);
 929         return NULL;
 930     }
 931
 932     //
 933     // Keep device id
 934     //
 935     Volume->DeviceId = DeviceId;
 936
 937     //
 938     // Search DATA attribute
 939     //
 940     DPRINTM(DPRINT_FILESYSTEM, "Searching for DATA attribute...\n");
 941     Volume->MFTContext = NtfsFindAttribute(Volume, Volume->MasterFileTable, NTFS_ATTR_TYPE_DATA, L"");
 942     if (!Volume->MFTContext)
 943     {
 944         FileSystemError("Can't find data attribute for Master File Table.");
 945         MmHeapFree(Volume->MasterFileTable);
 946         MmHeapFree(Volume);
 947         return NULL;
 948     }
 949
 950     //
 951     // Remember NTFS volume information
 952     //
 953     NtfsVolumes[DeviceId] = Volume;
 954
 955     //
 956     // Return success
 957     //
 958     return &NtfsFuncTable;
 959 }