core/fs/ntfs/ntfs.c

   1 /*
   2  * Copyright (C) Paulo Alcantara <pcacjr@gmail.com>
   3  *
   4  * This program is free software; you can redistribute it and/or modify
   5  * it under the terms of the GNU General Public License as published by
   6  * the Free Software Foundation; either version 2 of the License, or
   7  * (at your option) any later version.
   8  *
   9  * This program is distributed in the hope that it will be useful,
  10  * but WITHOUT ANY WARRANTY; without even the implied warranty of
  11  * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
  12  * GNU General Public License for more details.
  13  *
  14  * You should have received a copy of the GNU General Public License
  15  * along with this program; if not, write to the
  16  * Free Software Foundation, Inc.,
  17  * 59 Temple Place - Suite 330, Boston, MA 02111-1307, USA.
  18 */
  19
  20 /* Note: No support for compressed files */
  21
  22 #include <dprintf.h>
  23 #include <stdio.h>
  24 #include <string.h>
  25 #include <sys/dirent.h>
  26 #include <cache.h>
  27 #include <core.h>
  28 #include <disk.h>
  29 #include <fs.h>
  30 #include <ilog2.h>
  31 #include <klibc/compiler.h>
  32 #include <ctype.h>
  33
  34 #include "codepage.h"
  35 #include "ntfs.h"
  36 #include "runlist.h"
  37
  38 /* Check if there are specific zero fields in an NTFS boot sector */
  39 static inline int ntfs_check_zero_fields(const struct ntfs_bpb *sb)
  40 {
  41     return !sb->res_sectors && (!sb->zero_0[0] && !sb->zero_0[1] &&
  42             !sb->zero_0[2]) && !sb->zero_1 && !sb->zero_2 &&
  43             !sb->zero_3;
  44 }
  45
  46 static inline int ntfs_check_sb_fields(const struct ntfs_bpb *sb)
  47 {
  48     return ntfs_check_zero_fields(sb) &&
  49             (!memcmp(sb->oem_name, "NTFS    ", 8) ||
  50              !memcmp(sb->oem_name, "MSWIN4.0", 8) ||
  51              !memcmp(sb->oem_name, "MSWIN4.1", 8));
  52 }
  53
  54 static inline struct inode *new_ntfs_inode(struct fs_info *fs)
  55 {
  56     struct inode *inode;
  57
  58     inode = alloc_inode(fs, 0, sizeof(struct ntfs_inode));
  59     if (!inode)
  60         malloc_error("inode structure");
  61
  62     return inode;
  63 }
  64
  65 static void ntfs_fixups_writeback(struct fs_info *fs, NTFS_RECORD *nrec)
  66 {
  67     uint16_t *usa;
  68     uint16_t usa_no;
  69     uint16_t usa_count;
  70     uint16_t *blk;
  71
  72     if (nrec->magic != NTFS_MAGIC_FILE && nrec->magic != NTFS_MAGIC_INDX)
  73         return;
  74
  75     /* get the Update Sequence Array offset */
  76     usa = (uint16_t *)((uint8_t *)nrec + nrec->usa_ofs);
  77     /* get the Update Sequence Array Number and skip it */
  78     usa_no = *usa++;
  79     /* get the Update Sequene Array count */
  80     usa_count = nrec->usa_count - 1;    /* exclude the USA number */
  81     /* make it to point to the last two bytes of the RECORD's first sector */
  82     blk = (uint16_t *)((uint8_t *)nrec + SECTOR_SIZE(fs) - 2);
  83
  84     while (usa_count--) {
  85         if (*blk != usa_no)
  86             break;
  87
  88         *blk = *usa++;
  89         blk = (uint16_t *)((uint8_t *)blk + SECTOR_SIZE(fs));
  90     }
  91 }
  92
  93 /* read content from cache */
  94 static int ntfs_read(struct fs_info *fs, void *buf, size_t len, uint64_t count,
  95                     block_t *blk, uint64_t *blk_offset,
  96                     uint64_t *blk_next_offset, uint64_t *lcn)
  97 {
  98     uint8_t *data;
  99     uint64_t offset = *blk_offset;
 100     const uint32_t clust_byte_shift = NTFS_SB(fs)->clust_byte_shift;
 101     const uint64_t blk_size = UINT64_C(1) << BLOCK_SHIFT(fs);
 102     uint64_t bytes;
 103     uint64_t lbytes;
 104     uint64_t loffset;
 105     uint64_t k;
 106
 107     if (count > len)
 108         goto out;
 109
 110     data = (uint8_t *)get_cache(fs->fs_dev, *blk);
 111     if (!data)
 112         goto out;
 113
 114     if (!offset)
 115         offset = (*lcn << clust_byte_shift) % blk_size;
 116
 117     dprintf("LCN:            0x%X\n", *lcn);
 118     dprintf("offset:         0x%X\n", offset);
 119
 120     bytes = count;              /* bytes to copy */
 121     lbytes = blk_size - offset; /* bytes left to copy */
 122     if (lbytes >= bytes) {
 123         /* so there's room enough, then copy the whole content */
 124         memcpy(buf, data + offset, bytes);
 125         loffset = offset;
 126         offset += count;
 127     } else {
 128         dprintf("bytes:             %u\n", bytes);
 129         dprintf("bytes left:        %u\n", lbytes);
 130         /* otherwise, let's copy it partially... */
 131         k = 0;
 132         while (bytes) {
 133             memcpy(buf + k, data + offset, lbytes);
 134             bytes -= lbytes;
 135             loffset = offset;
 136             offset += lbytes;
 137             k += lbytes;
 138             if (offset >= blk_size) {
 139                 /* then fetch a new FS block */
 140                 data = (uint8_t *)get_cache(fs->fs_dev, ++*blk);
 141                 if (!data)
 142                     goto out;
 143
 144                 lbytes = bytes;
 145                 loffset = offset;
 146                 offset = 0;
 147             }
 148         }
 149     }
 150
 151     if (loffset >= blk_size)
 152         loffset = 0;    /* it must be aligned on a block boundary */
 153
 154     *blk_offset = loffset;
 155
 156     if (blk_next_offset)
 157         *blk_next_offset = offset;
 158
 159     *lcn += blk_size / count;   /* update LCN */
 160
 161     return 0;
 162
 163 out:
 164     return -1;
 165 }
 166
 167 static MFT_RECORD *ntfs_mft_record_lookup(struct fs_info *fs, uint32_t file, block_t *blk)
 168 {
 169     const uint64_t mft_record_size = NTFS_SB(fs)->mft_record_size;
 170     uint8_t *buf;
 171     const block_t mft_blk = NTFS_SB(fs)->mft_blk;
 172     block_t cur_blk;
 173     block_t right_blk;
 174     uint64_t offset = 0;
 175     uint64_t next_offset;
 176     const unsigned mft_record_shift = ilog2(mft_record_size);
 177     const unsigned clust_byte_shift = NTFS_SB(fs)->clust_byte_shift;
 178     uint64_t lcn = NTFS_SB(fs)->mft_lcn;
 179     int err;
 180     MFT_RECORD *mrec;
 181
 182     buf = (uint8_t *)malloc(mft_record_size);
 183     if (!buf)
 184         malloc_error("uint8_t *");
 185
 186     /* determine MFT record's LCN and block number */
 187     lcn = NTFS_SB(fs)->mft_lcn + (file << mft_record_shift >> clust_byte_shift);
 188     cur_blk = (lcn << clust_byte_shift >> BLOCK_SHIFT(fs)) - mft_blk - 1;
 189     for (;;) {
 190         right_blk = cur_blk + mft_blk;
 191         err = ntfs_read(fs, buf, mft_record_size, mft_record_size, &right_blk,
 192                         &offset, &next_offset, &lcn);
 193         if (err) {
 194             printf("Error on reading from cache.\n");
 195             break;
 196         }
 197
 198         ntfs_fixups_writeback(fs, (NTFS_RECORD *)buf);
 199
 200         mrec = (MFT_RECORD *)buf;
 201         if (mrec->mft_record_no == file) {
 202             if (blk)
 203                 *blk = cur_blk;     /* update record starting block */
 204
 205             return mrec;            /* found MFT record */
 206         }
 207
 208         if (next_offset >= BLOCK_SIZE(fs)) {
 209             /* try the next FS block */
 210             offset = 0;
 211             cur_blk = right_blk - mft_blk + 1;
 212         } else {
 213             /* there's still content to fetch in the current block */
 214             cur_blk = right_blk - mft_blk;
 215             offset = next_offset;   /* update FS block offset */
 216         }
 217     }
 218
 219     free(buf);
 220
 221     return NULL;
 222 }
 223
 224 static ATTR_RECORD *ntfs_attr_lookup(uint32_t type, const MFT_RECORD *mrec)
 225 {
 226     ATTR_RECORD *attr;
 227
 228     /* sanity check */
 229     if (!mrec || type == NTFS_AT_END)
 230         return NULL;
 231
 232     attr = (ATTR_RECORD *)((uint8_t *)mrec + mrec->attrs_offset);
 233     /* walk through the file attribute records */
 234     for (;; attr = (ATTR_RECORD *)((uint8_t *)attr + attr->len)) {
 235         if (attr->type == NTFS_AT_END)
 236             return NULL;
 237
 238         if (attr->type == type)
 239             break;
 240     }
 241
 242     return attr;
 243 }
 244
 245 static bool ntfs_filename_cmp(const char *dname, INDEX_ENTRY *ie)
 246 {
 247     const uint16_t *entry_fn;
 248     uint8_t entry_fn_len;
 249     unsigned i;
 250
 251     entry_fn = ie->key.file_name.file_name;
 252     entry_fn_len = ie->key.file_name.file_name_len;
 253
 254     if (strlen(dname) != entry_fn_len)
 255         return false;
 256
 257     /* Do case-sensitive compares for Posix file names */
 258     if (ie->key.file_name.file_name_type == FILE_NAME_POSIX) {
 259         for (i = 0; i < entry_fn_len; i++)
 260             if (entry_fn[i] != dname[i])
 261                 return false;
 262     } else {
 263         for (i = 0; i < entry_fn_len; i++)
 264             if (tolower(entry_fn[i]) != tolower(dname[i]))
 265                 return false;
 266     }
 267
 268     return true;
 269 }
 270
 271 static inline uint8_t *mapping_chunk_init(ATTR_RECORD *attr,
 272                                     struct mapping_chunk *chunk,
 273                                     uint32_t *offset)
 274 {
 275     memset(chunk, 0, sizeof *chunk);
 276     *offset = 0U;
 277
 278     return (uint8_t *)attr + attr->data.non_resident.mapping_pairs_offset;
 279 }
 280
 281 /* Parse data runs.
 282  *
 283  * return 0 on success or -1 on failure.
 284  */
 285 static int parse_data_run(const void *stream, uint32_t *offset,
 286                             uint8_t *attr_len, struct mapping_chunk *chunk)
 287 {
 288     uint8_t *buf;   /* Pointer to the zero-terminated byte stream */
 289     uint8_t count;  /* The count byte */
 290     uint8_t v, l;   /* v is the number of changed low-order VCN bytes;
 291                      * l is the number of changed low-order LCN bytes
 292                      */
 293     uint8_t *byte;
 294     int byte_shift = 8;
 295     int mask;
 296     uint8_t val;
 297     int64_t res;
 298
 299     (void)attr_len;
 300
 301     chunk->flags &= ~MAP_MASK;
 302
 303     buf = (uint8_t *)stream + *offset;
 304     if (buf > attr_len || !*buf) {
 305         chunk->flags |= MAP_END;    /* we're done */
 306         return 0;
 307     }
 308
 309     if (!*offset)
 310         chunk->flags |= MAP_START;  /* initial chunk */
 311
 312     count = *buf;
 313     v = count & 0x0F;
 314     l = count >> 4;
 315
 316     if (v > 8 || l > 8) /* more than 8 bytes ? */
 317         goto out;
 318
 319     byte = (uint8_t *)buf + v;
 320     count = v;
 321
 322     res = 0LL;
 323     while (count--) {
 324         val = *byte--;
 325         mask = val >> (byte_shift - 1);
 326         res = (res << byte_shift) | ((val + mask) ^ mask);
 327     }
 328
 329     chunk->len = res;   /* get length data */
 330
 331     byte = (uint8_t *)buf + v + l;
 332     count = l;
 333
 334     mask = 0xFFFFFFFF;
 335     res = 0LL;
 336     if (*byte & 0x80)
 337         res |= (int64_t)mask;   /* sign-extend it */
 338
 339     while (count--)
 340         res = (res << byte_shift) | *byte--;
 341
 342     chunk->lcn += res;
 343     /* are VCNS from cur_vcn to next_vcn - 1 unallocated ? */
 344     if (!chunk->lcn)
 345         chunk->flags |= MAP_UNALLOCATED;
 346     else
 347         chunk->flags |= MAP_ALLOCATED;
 348
 349     *offset += v + l + 1;
 350
 351     return 0;
 352
 353 out:
 354     return -1;
 355 }
 356
 357 static inline enum dirent_type get_inode_mode(MFT_RECORD *mrec)
 358 {
 359     return mrec->flags & MFT_RECORD_IS_DIRECTORY ? DT_DIR : DT_REG;
 360 }
 361
 362 static int index_inode_setup(struct fs_info *fs, unsigned long mft_no,
 363                             struct inode *inode)
 364 {
 365     uint64_t start_blk = 0;
 366     MFT_RECORD *mrec;
 367     ATTR_RECORD *attr;
 368     enum dirent_type d_type;
 369     uint32_t len;
 370     INDEX_ROOT *ir;
 371     uint32_t clust_size;
 372     uint8_t *attr_len;
 373     struct mapping_chunk chunk;
 374     int err;
 375     uint8_t *stream;
 376     uint32_t offset;
 377
 378     mrec = ntfs_mft_record_lookup(fs, mft_no, &start_blk);
 379     if (!mrec) {
 380         printf("No MFT record found.\n");
 381         goto out;
 382     }
 383
 384     NTFS_PVT(inode)->mft_no = mft_no;
 385     NTFS_PVT(inode)->seq_no = mrec->seq_no;
 386
 387     NTFS_PVT(inode)->start_cluster = start_blk >> NTFS_SB(fs)->clust_shift;
 388     NTFS_PVT(inode)->here = start_blk;
 389
 390     d_type = get_inode_mode(mrec);
 391     if (d_type == DT_DIR) {    /* directory stuff */
 392         dprintf("Got a directory.\n");
 393         attr = ntfs_attr_lookup(NTFS_AT_INDEX_ROOT, mrec);
 394         if (!attr) {
 395             printf("No attribute found.\n");
 396             goto out;
 397         }
 398
 399         /* note: INDEX_ROOT is always resident */
 400         ir = (INDEX_ROOT *)((uint8_t *)attr +
 401                                     attr->data.resident.value_offset);
 402         len = attr->data.resident.value_len;
 403         if ((uint8_t *)ir + len > (uint8_t *)mrec +
 404                         NTFS_SB(fs)->mft_record_size) {
 405             dprintf("Corrupt index\n");
 406             goto out;
 407         }
 408
 409         NTFS_PVT(inode)->itype.index.collation_rule = ir->collation_rule;
 410         NTFS_PVT(inode)->itype.index.blk_size = ir->index_block_size;
 411         NTFS_PVT(inode)->itype.index.blk_size_shift =
 412                             ilog2(NTFS_PVT(inode)->itype.index.blk_size);
 413
 414         /* determine the size of a vcn in the index */
 415         clust_size = NTFS_PVT(inode)->itype.index.blk_size;
 416         if (NTFS_SB(fs)->clust_size <= clust_size) {
 417             NTFS_PVT(inode)->itype.index.vcn_size = NTFS_SB(fs)->clust_size;
 418             NTFS_PVT(inode)->itype.index.vcn_size_shift =
 419                                         NTFS_SB(fs)->clust_shift;
 420         } else {
 421             NTFS_PVT(inode)->itype.index.vcn_size = BLOCK_SIZE(fs);
 422             NTFS_PVT(inode)->itype.index.vcn_size_shift = BLOCK_SHIFT(fs);
 423         }
 424
 425         NTFS_PVT(inode)->in_idx_root = true;
 426     } else if (d_type == DT_REG) {        /* file stuff */
 427         dprintf("Got a file.\n");
 428         attr = ntfs_attr_lookup(NTFS_AT_DATA, mrec);
 429         if (!attr) {
 430             printf("No attribute found.\n");
 431             goto out;
 432         }
 433
 434         NTFS_PVT(inode)->non_resident = attr->non_resident;
 435         NTFS_PVT(inode)->type = attr->type;
 436
 437         if (!attr->non_resident) {
 438             NTFS_PVT(inode)->data.resident.offset =
 439                 (uint32_t)((uint8_t *)attr + attr->data.resident.value_offset);
 440             inode->size = attr->data.resident.value_len;
 441         } else {
 442             attr_len = (uint8_t *)attr + attr->len;
 443
 444             stream = mapping_chunk_init(attr, &chunk, &offset);
 445             NTFS_PVT(inode)->data.non_resident.rlist = NULL;
 446             for (;;) {
 447                 err = parse_data_run(stream, &offset, attr_len, &chunk);
 448                 if (err) {
 449                     printf("parse_data_run()\n");
 450                     goto out;
 451                 }
 452
 453                 if (chunk.flags & MAP_UNALLOCATED)
 454                     continue;
 455                 if (chunk.flags & MAP_END)
 456                     break;
 457                 if (chunk.flags &  MAP_ALLOCATED) {
 458                     /* append new run to the runlist */
 459                     runlist_append(&NTFS_PVT(inode)->data.non_resident.rlist,
 460                                     (struct runlist_element *)&chunk);
 461                     /* update for next VCN */
 462                     chunk.vcn += chunk.len;
 463                 }
 464             }
 465
 466             if (runlist_is_empty(NTFS_PVT(inode)->data.non_resident.rlist)) {
 467                 printf("No mapping found\n");
 468                 goto out;
 469             }
 470
 471             inode->size = attr->data.non_resident.initialized_size;
 472         }
 473     }
 474
 475     inode->mode = d_type;
 476
 477     free(mrec);
 478
 479     return 0;
 480
 481 out:
 482     free(mrec);
 483
 484     return -1;
 485 }
 486
 487 static struct inode *ntfs_index_lookup(const char *dname, struct inode *dir)
 488 {
 489     struct fs_info *fs = dir->fs;
 490     MFT_RECORD *mrec;
 491     block_t blk;
 492     uint64_t blk_offset;
 493     ATTR_RECORD *attr;
 494     INDEX_ROOT *ir;
 495     uint32_t len;
 496     INDEX_ENTRY *ie;
 497     const uint64_t blk_size = UINT64_C(1) << BLOCK_SHIFT(fs);
 498     uint8_t buf[blk_size];
 499     INDEX_BLOCK *iblk;
 500     int err;
 501     uint8_t *stream;
 502     uint8_t *attr_len;
 503     struct mapping_chunk chunk;
 504     uint32_t offset;
 505     int64_t vcn;
 506     int64_t lcn;
 507     int64_t last_lcn;
 508     struct inode *inode;
 509
 510     dprintf("ntfs_index_lookup() - mft record number: %d\n",
 511             NTFS_PVT(dir)->mft_no);
 512     mrec = ntfs_mft_record_lookup(fs, NTFS_PVT(dir)->mft_no, NULL);
 513     if (!mrec) {
 514         printf("No MFT record found.\n");
 515         goto out;
 516     }
 517
 518     attr = ntfs_attr_lookup(NTFS_AT_INDEX_ROOT, mrec);
 519     if (!attr) {
 520         printf("No attribute found.\n");
 521         goto out;
 522     }
 523
 524     ir = (INDEX_ROOT *)((uint8_t *)attr +
 525                             attr->data.resident.value_offset);
 526     len = attr->data.resident.value_len;
 527     /* sanity check */
 528     if ((uint8_t *)ir + len > (uint8_t *)mrec + NTFS_SB(fs)->mft_record_size)
 529         goto index_err;
 530
 531     ie = (INDEX_ENTRY *)((uint8_t *)&ir->index +
 532                                 ir->index.entries_offset);
 533     for (;; ie = (INDEX_ENTRY *)((uint8_t *)ie + ie->len)) {
 534         /* bounds checks */
 535         if ((uint8_t *)ie < (uint8_t *)mrec ||
 536             (uint8_t *)ie + sizeof(INDEX_ENTRY_HEADER) >
 537             (uint8_t *)&ir->index + ir->index.index_len ||
 538             (uint8_t *)ie + ie->len >
 539             (uint8_t *)&ir->index + ir->index.index_len)
 540             goto index_err;
 541
 542         /* last entry cannot contain a key. it can however contain
 543          * a pointer to a child node in the B+ tree so we just break out
 544          */
 545         dprintf("(0) ie->flags:          0x%X\n", ie->flags);
 546         if (ie->flags & INDEX_ENTRY_END)
 547             break;
 548
 549         if (ntfs_filename_cmp(dname, ie))
 550             goto found;
 551     }
 552
 553     /* check for the presence of a child node */
 554     if (!(ie->flags & INDEX_ENTRY_NODE)) {
 555         printf("No child node, aborting...\n");
 556         goto out;
 557     }
 558
 559     /* then descend into child node */
 560
 561     attr = ntfs_attr_lookup(NTFS_AT_INDEX_ALLOCATION, mrec);
 562     if (!attr) {
 563         printf("No attribute found.\n");
 564         goto out;
 565     }
 566
 567     if (!attr->non_resident) {
 568         printf("WTF ?! $INDEX_ALLOCATION isn't really resident.\n");
 569         goto out;
 570     }
 571
 572     attr_len = (uint8_t *)attr + attr->len;
 573     stream = mapping_chunk_init(attr, &chunk, &offset);
 574     do {
 575         err = parse_data_run(stream, &offset, attr_len, &chunk);
 576         if (err)
 577             break;
 578
 579         if (chunk.flags & MAP_UNALLOCATED)
 580             continue;
 581
 582         if (chunk.flags & MAP_ALLOCATED) {
 583             dprintf("%d cluster(s) starting at 0x%08llX\n", chunk.len,
 584                     chunk.lcn);
 585
 586             vcn = 0;
 587             lcn = chunk.lcn;
 588             while (vcn < chunk.len) {
 589                 blk = (lcn + vcn) << NTFS_SB(fs)->clust_shift <<
 590                     SECTOR_SHIFT(fs) >> BLOCK_SHIFT(fs);
 591
 592                 blk_offset = 0;
 593                 last_lcn = lcn;
 594                 lcn += vcn;
 595                 err = ntfs_read(fs, &buf, blk_size, blk_size, &blk,
 596                                 &blk_offset, NULL, (uint64_t *)&lcn);
 597                 if (err) {
 598                     printf("Error on reading from cache.\n");
 599                     goto not_found;
 600                 }
 601
 602                 ntfs_fixups_writeback(fs, (NTFS_RECORD *)&buf);
 603
 604                 iblk = (INDEX_BLOCK *)&buf;
 605                 if (iblk->magic != NTFS_MAGIC_INDX) {
 606                     printf("Not a valid INDX record.\n");
 607                     goto not_found;
 608                 }
 609
 610                 ie = (INDEX_ENTRY *)((uint8_t *)&iblk->index +
 611                                             iblk->index.entries_offset);
 612                 for (;; ie = (INDEX_ENTRY *)((uint8_t *)ie + ie->len)) {
 613                     /* bounds checks */
 614                     if ((uint8_t *)ie < (uint8_t *)iblk || (uint8_t *)ie +
 615                         sizeof(INDEX_ENTRY_HEADER) >
 616                         (uint8_t *)&iblk->index + iblk->index.index_len ||
 617                         (uint8_t *)ie + ie->len >
 618                         (uint8_t *)&iblk->index + iblk->index.index_len)
 619                         goto index_err;
 620
 621                     /* last entry cannot contain a key */
 622                     if (ie->flags & INDEX_ENTRY_END)
 623                         break;
 624
 625                     /* Do case-sensitive compares for Posix file names */
 626                     if (ie->key.file_name.file_name_type == FILE_NAME_POSIX) {
 627                         if (ie->key.file_name.file_name[0] > *dname)
 628                             break;
 629                     } else {
 630                         if (tolower(ie->key.file_name.file_name[0]) >
 631                             tolower(*dname))
 632                             break;
 633                     }
 634
 635                     if (ntfs_filename_cmp(dname, ie))
 636                         goto found;
 637                 }
 638
 639                 lcn = last_lcn; /* restore the original LCN */
 640                 /* go to the next VCN */
 641                 vcn += (blk_size / (1 << NTFS_SB(fs)->clust_byte_shift));
 642             }
 643         }
 644     } while (!(chunk.flags & MAP_END));
 645
 646 not_found:
 647     dprintf("Index not found\n");
 648
 649 out:
 650     dprintf("%s not found!\n", dname);
 651
 652     free(mrec);
 653
 654     return NULL;
 655
 656 found:
 657     dprintf("Index found\n");
 658     inode = new_ntfs_inode(fs);
 659     err = index_inode_setup(fs, ie->data.dir.indexed_file, inode);
 660     if (err) {
 661         printf("Error in index_inode_setup()\n");
 662         free(inode);
 663         goto out;
 664     }
 665
 666     dprintf("%s found!\n", dname);
 667
 668     free(mrec);
 669
 670     return inode;
 671
 672 index_err:
 673     printf("Corrupt index. Aborting lookup...\n");
 674     goto out;
 675 }
 676
 677 /* Convert an UTF-16LE LFN to OEM LFN */
 678 static uint8_t ntfs_cvt_filename(char *filename, INDEX_ENTRY *ie)
 679 {
 680     const uint16_t *entry_fn;
 681     uint8_t entry_fn_len;
 682     unsigned i;
 683
 684     entry_fn = ie->key.file_name.file_name;
 685     entry_fn_len = ie->key.file_name.file_name_len;
 686
 687     for (i = 0; i < entry_fn_len; i++)
 688         filename[i] = (char)entry_fn[i];
 689
 690     filename[i] = '\0';
 691
 692     return entry_fn_len;
 693 }
 694
 695 static int ntfs_next_extent(struct inode *inode, uint32_t lstart)
 696 {
 697     struct fs_info *fs = inode->fs;
 698     struct ntfs_sb_info *sbi = NTFS_SB(fs);
 699     sector_t pstart = 0;
 700     struct runlist *rlist;
 701     struct runlist *ret;
 702     const uint32_t sec_size = SECTOR_SIZE(fs);
 703     const uint32_t sec_shift = SECTOR_SHIFT(fs);
 704
 705     if (!NTFS_PVT(inode)->non_resident) {
 706         pstart = (sbi->mft_blk + NTFS_PVT(inode)->here) << BLOCK_SHIFT(fs) >>
 707                 sec_shift;
 708         inode->next_extent.len = (inode->size + sec_size - 1) >> sec_shift;
 709     } else {
 710         rlist = NTFS_PVT(inode)->data.non_resident.rlist;
 711
 712         if (!lstart || lstart >= NTFS_PVT(inode)->here) {
 713             if (runlist_is_empty(rlist))
 714                 goto out;   /* nothing to do ;-) */
 715
 716             ret = runlist_remove(&rlist);
 717
 718             NTFS_PVT(inode)->here =
 719                 ((ret->run.len << sbi->clust_byte_shift) >> sec_shift);
 720
 721             pstart = ret->run.lcn << sbi->clust_shift;
 722             inode->next_extent.len =
 723                 ((ret->run.len << sbi->clust_byte_shift) + sec_size - 1) >>
 724                 sec_shift;
 725
 726             NTFS_PVT(inode)->data.non_resident.rlist = rlist;
 727
 728             free(ret);
 729             ret = NULL;
 730         }
 731     }
 732
 733     inode->next_extent.pstart = pstart;
 734
 735     return 0;
 736
 737 out:
 738     return -1;
 739 }
 740
 741 static uint32_t ntfs_getfssec(struct file *file, char *buf, int sectors,
 742                                 bool *have_more)
 743 {
 744     uint8_t non_resident;
 745     uint32_t ret;
 746     struct fs_info *fs = file->fs;
 747     struct inode *inode = file->inode;
 748     MFT_RECORD *mrec;
 749     ATTR_RECORD *attr;
 750     char *p;
 751
 752     non_resident = NTFS_PVT(inode)->non_resident;
 753
 754     ret = generic_getfssec(file, buf, sectors, have_more);
 755     if (!ret)
 756         return ret;
 757
 758     if (!non_resident) {
 759         mrec = ntfs_mft_record_lookup(fs, NTFS_PVT(inode)->mft_no, NULL);
 760         if (!mrec) {
 761             printf("No MFT record found.\n");
 762             goto out;
 763         }
 764
 765         attr = ntfs_attr_lookup(NTFS_AT_DATA, mrec);
 766         if (!attr) {
 767             printf("No attribute found.\n");
 768             goto out;
 769         }
 770
 771         p = (char *)((uint8_t *)attr + attr->data.resident.value_offset);
 772
 773         /* p now points to the data offset, so let's copy it into buf */
 774         memcpy(buf, p, inode->size);
 775
 776         ret = inode->size;
 777
 778         free(mrec);
 779     }
 780
 781     return ret;
 782
 783 out:
 784     free(mrec);
 785
 786     return 0;
 787 }
 788
 789 static inline bool is_filename_printable(const char *s)
 790 {
 791     return s && (*s != '.' && *s != '$');
 792 }
 793
 794 static int ntfs_readdir(struct file *file, struct dirent *dirent)
 795 {
 796     struct fs_info *fs = file->fs;
 797     struct inode *inode = file->inode;
 798     MFT_RECORD *mrec;
 799     block_t blk;
 800     uint64_t blk_offset;
 801     const uint64_t blk_size = UINT64_C(1) << BLOCK_SHIFT(fs);
 802     ATTR_RECORD *attr;
 803     INDEX_ROOT *ir;
 804     uint32_t count;
 805     int len;
 806     INDEX_ENTRY *ie = NULL;
 807     uint8_t buf[BLOCK_SIZE(fs)];
 808     INDEX_BLOCK *iblk;
 809     int err;
 810     uint8_t *stream;
 811     uint8_t *attr_len;
 812     struct mapping_chunk chunk;
 813     uint32_t offset;
 814     int64_t vcn;
 815     int64_t lcn;
 816     char filename[NTFS_MAX_FILE_NAME_LEN + 1];
 817
 818     mrec = ntfs_mft_record_lookup(fs, NTFS_PVT(inode)->mft_no, NULL);
 819     if (!mrec) {
 820         printf("No MFT record found.\n");
 821         goto out;
 822     }
 823
 824     attr = ntfs_attr_lookup(NTFS_AT_INDEX_ROOT, mrec);
 825     if (!attr) {
 826         printf("No attribute found.\n");
 827         goto out;
 828     }
 829
 830     ir = (INDEX_ROOT *)((uint8_t *)attr +
 831                             attr->data.resident.value_offset);
 832     len = attr->data.resident.value_len;
 833     /* sanity check */
 834     if ((uint8_t *)ir + len > (uint8_t *)mrec + NTFS_SB(fs)->mft_record_size)
 835         goto index_err;
 836
 837     if (!file->offset && NTFS_PVT(inode)->in_idx_root) {
 838         file->offset = (uint32_t)((uint8_t *)&ir->index +
 839                                         ir->index.entries_offset);
 840     }
 841
 842 idx_root_next_entry:
 843     if (NTFS_PVT(inode)->in_idx_root) {
 844         ie = (INDEX_ENTRY *)(uint8_t *)file->offset;
 845         if (ie->flags & INDEX_ENTRY_END) {
 846             file->offset = 0;
 847             NTFS_PVT(inode)->in_idx_root = false;
 848             NTFS_PVT(inode)->idx_blks_count = 1;
 849             NTFS_PVT(inode)->entries_count = 0;
 850             NTFS_PVT(inode)->last_vcn = 0;
 851             goto descend_into_child_node;
 852         }
 853
 854         file->offset = (uint32_t)((uint8_t *)ie + ie->len);
 855         len = ntfs_cvt_filename(filename, ie);
 856         if (!is_filename_printable(filename))
 857             goto idx_root_next_entry;
 858
 859         goto done;
 860     }
 861
 862 descend_into_child_node:
 863     if (!(ie->flags & INDEX_ENTRY_NODE))
 864         goto out;
 865
 866     attr = ntfs_attr_lookup(NTFS_AT_INDEX_ALLOCATION, mrec);
 867     if (!attr)
 868         goto out;
 869
 870     if (!attr->non_resident) {
 871         printf("WTF ?! $INDEX_ALLOCATION isn't really resident.\n");
 872         goto out;
 873     }
 874
 875     attr_len = (uint8_t *)attr + attr->len;
 876
 877 next_run:
 878     stream = mapping_chunk_init(attr, &chunk, &offset);
 879     count = NTFS_PVT(inode)->idx_blks_count;
 880     while (count--) {
 881         err = parse_data_run(stream, &offset, attr_len, &chunk);
 882         if (err) {
 883             printf("Error on parsing data runs.\n");
 884             goto out;
 885         }
 886
 887         if (chunk.flags & MAP_UNALLOCATED)
 888             break;
 889         if (chunk.flags & MAP_END)
 890             goto out;
 891     }
 892
 893     if (chunk.flags & MAP_UNALLOCATED) {
 894        NTFS_PVT(inode)->idx_blks_count++;
 895        goto next_run;
 896     }
 897
 898 next_vcn:
 899     vcn = NTFS_PVT(inode)->last_vcn;
 900     if (vcn >= chunk.len) {
 901         NTFS_PVT(inode)->last_vcn = 0;
 902         NTFS_PVT(inode)->idx_blks_count++;
 903         goto next_run;
 904     }
 905
 906     lcn = chunk.lcn;
 907     blk = (lcn + vcn) << NTFS_SB(fs)->clust_shift << SECTOR_SHIFT(fs) >>
 908             BLOCK_SHIFT(fs);
 909
 910     blk_offset = 0;
 911     err = ntfs_read(fs, &buf, blk_size, blk_size, &blk, &blk_offset, NULL,
 912                     (uint64_t *)&lcn);
 913     if (err) {
 914         printf("Error on reading from cache.\n");
 915         goto not_found;
 916     }
 917
 918     ntfs_fixups_writeback(fs, (NTFS_RECORD *)&buf);
 919
 920     iblk = (INDEX_BLOCK *)&buf;
 921     if (iblk->magic != NTFS_MAGIC_INDX) {
 922         printf("Not a valid INDX record.\n");
 923         goto not_found;
 924     }
 925
 926 idx_block_next_entry:
 927     ie = (INDEX_ENTRY *)((uint8_t *)&iblk->index +
 928                         iblk->index.entries_offset);
 929     count = NTFS_PVT(inode)->entries_count;
 930     for ( ; count--; ie = (INDEX_ENTRY *)((uint8_t *)ie + ie->len)) {
 931         /* bounds checks */
 932         if ((uint8_t *)ie < (uint8_t *)iblk || (uint8_t *)ie +
 933             sizeof(INDEX_ENTRY_HEADER) >
 934             (uint8_t *)&iblk->index + iblk->index.index_len ||
 935             (uint8_t *)ie + ie->len >
 936             (uint8_t *)&iblk->index + iblk->index.index_len)
 937             goto index_err;
 938
 939         /* last entry cannot contain a key */
 940         if (ie->flags & INDEX_ENTRY_END) {
 941             /* go to the next VCN */
 942             NTFS_PVT(inode)->last_vcn += (blk_size / (1 <<
 943                                 NTFS_SB(fs)->clust_byte_shift));
 944             NTFS_PVT(inode)->entries_count = 0;
 945             goto next_vcn;
 946         }
 947     }
 948
 949     NTFS_PVT(inode)->entries_count++;
 950     len = ntfs_cvt_filename(filename, ie);
 951     if (!is_filename_printable(filename))
 952         goto idx_block_next_entry;
 953
 954     goto done;
 955
 956 out:
 957     NTFS_PVT(inode)->in_idx_root = true;
 958
 959     free(mrec);
 960
 961     return -1;
 962
 963 done:
 964     dirent->d_ino = ie->data.dir.indexed_file;
 965     dirent->d_off = file->offset;
 966     dirent->d_reclen = offsetof(struct dirent, d_name) + len + 1;
 967
 968     free(mrec);
 969
 970     mrec = ntfs_mft_record_lookup(fs, ie->data.dir.indexed_file, NULL);
 971     if (!mrec) {
 972         printf("No MFT record found.\n");
 973         goto out;
 974     }
 975
 976     dirent->d_type = get_inode_mode(mrec);
 977     memcpy(dirent->d_name, filename, len + 1);
 978
 979     free(mrec);
 980
 981     return 0;
 982
 983 not_found:
 984     printf("Index not found\n");
 985     goto out;
 986
 987 index_err:
 988     printf("Corrupt index. Aborting lookup...\n");
 989     goto out;
 990 }
 991
 992 static struct inode *ntfs_iget(const char *dname, struct inode *parent)
 993 {
 994     return ntfs_index_lookup(dname, parent);
 995 }
 996
 997 static struct inode *ntfs_iget_root(struct fs_info *fs)
 998 {
 999     struct inode *inode = new_ntfs_inode(fs);
1000     int err;
1001
1002     inode->fs = fs;
1003
1004     err = index_inode_setup(fs, FILE_root, inode);
1005     if (err)
1006         goto free_out;
1007
1008     NTFS_PVT(inode)->start = NTFS_PVT(inode)->here;
1009
1010     return inode;
1011
1012 free_out:
1013     free(inode);
1014
1015     return NULL;
1016 }
1017
1018 /* Initialize the filesystem metadata and return blk size in bits */
1019 static int ntfs_fs_init(struct fs_info *fs)
1020 {
1021     struct ntfs_bpb ntfs;
1022     struct ntfs_sb_info *sbi;
1023     struct disk *disk = fs->fs_dev->disk;
1024     uint8_t mft_record_shift;
1025
1026     disk->rdwr_sectors(disk, &ntfs, 0, 1, 0);
1027
1028     /* sanity check */
1029     if (!ntfs_check_sb_fields(&ntfs))
1030         return -1;
1031
1032     SECTOR_SHIFT(fs) = disk->sector_shift;
1033
1034     /* Note: ntfs.clust_per_mft_record can be a negative number.
1035      * If negative, it represents a shift count, else it represents
1036      * a multiplier for the cluster size.
1037      */
1038     mft_record_shift = ntfs.clust_per_mft_record < 0 ?
1039                     -ntfs.clust_per_mft_record :
1040                     ilog2(ntfs.sec_per_clust) + SECTOR_SHIFT(fs) +
1041                     ilog2(ntfs.clust_per_mft_record);
1042
1043     SECTOR_SIZE(fs) = 1 << SECTOR_SHIFT(fs);
1044
1045     sbi = malloc(sizeof *sbi);
1046     if (!sbi)
1047         malloc_error("ntfs_sb_info structure");
1048
1049     fs->fs_info = sbi;
1050
1051     sbi->clust_shift            = ilog2(ntfs.sec_per_clust);
1052     sbi->clust_byte_shift       = sbi->clust_shift + SECTOR_SHIFT(fs);
1053     sbi->clust_mask             = ntfs.sec_per_clust - 1;
1054     sbi->clust_size             = ntfs.sec_per_clust << SECTOR_SHIFT(fs);
1055     sbi->mft_record_size        = 1 << mft_record_shift;
1056     sbi->clust_per_idx_record   = ntfs.clust_per_idx_record;
1057
1058     BLOCK_SHIFT(fs) = ilog2(ntfs.clust_per_idx_record) + sbi->clust_byte_shift;
1059     BLOCK_SIZE(fs) = 1 << BLOCK_SHIFT(fs);
1060
1061     sbi->mft_lcn = ntfs.mft_lclust;
1062     sbi->mft_blk = ntfs.mft_lclust << sbi->clust_shift <<
1063                     SECTOR_SHIFT(fs) >> BLOCK_SHIFT(fs);
1064     /* 16 MFT entries reserved for metadata files (approximately 16 KiB) */
1065     sbi->mft_size = mft_record_shift << sbi->clust_shift << 4;
1066
1067     sbi->clusters = ntfs.total_sectors << SECTOR_SHIFT(fs) >> sbi->clust_shift;
1068     if (sbi->clusters > 0xFFFFFFFFFFF4ULL)
1069         sbi->clusters = 0xFFFFFFFFFFF4ULL;
1070
1071     /* Initialize the cache */
1072     cache_init(fs->fs_dev, BLOCK_SHIFT(fs));
1073
1074     return BLOCK_SHIFT(fs);
1075 }
1076
1077 const struct fs_ops ntfs_fs_ops = {
1078     .fs_name        = "ntfs",
1079     .fs_flags       = FS_USEMEM | FS_THISIND,
1080     .fs_init        = ntfs_fs_init,
1081     .searchdir      = NULL,
1082     .getfssec       = ntfs_getfssec,
1083     .close_file     = generic_close_file,
1084     .mangle_name    = generic_mangle_name,
1085     .load_config    = generic_load_config,
1086     .readdir        = ntfs_readdir,
1087     .iget_root      = ntfs_iget_root,
1088     .iget           = ntfs_iget,
1089     .next_extent    = ntfs_next_extent,
1090 };