1 /* ----------------------------------------------------------------------- *
3 * Copyright 2011 Paulo Alcantara <pcacjr@gmail.com>
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, Inc., 53 Temple Place Ste 330,
8 * Boston MA 02111-1307, USA; either version 2 of the License, or
9 * (at your option) any later version; incorporated herein by reference.
11 * ----------------------------------------------------------------------- */
14 * ntfs.c - The NTFS filesystem functions
20 #include <sys/dirent.h>
26 #include <klibc/compiler.h>
31 /* Check if there are specific zero fields in an NTFS boot sector */
32 static inline int ntfs_check_zero_fields(const struct ntfs_bpb *sb)
34 return !sb->res_sectors && (!sb->zero_0[0] && !sb->zero_0[1] &&
35 !sb->zero_0[2]) && !sb->zero_1 && !sb->zero_2 &&
39 static inline int ntfs_check_sb_fields(const struct ntfs_bpb *sb)
41 return ntfs_check_zero_fields(sb) &&
42 (!memcmp(sb->oem_name, "NTFS ", 8) ||
43 !memcmp(sb->oem_name, "MSWIN4.0", 8) ||
44 !memcmp(sb->oem_name, "MSWIN4.1", 8));
47 static inline struct inode *new_ntfs_inode(struct fs_info *fs)
51 inode = alloc_inode(fs, 0, sizeof(struct ntfs_inode));
53 malloc_error("inode structure");
58 static inline const void *get_right_block(struct fs_info *fs,
61 return get_cache(fs->fs_dev, NTFS_SB(fs)->mft_block + block);
64 static int fixups_writeback(struct fs_info *fs, NTFS_RECORD *nrec)
71 if (nrec->magic != NTFS_MAGIC_FILE && nrec->magic != NTFS_MAGIC_INDX) {
72 printf("Not a valid NTFS record\n");
76 /* get the Update Sequence Array offset */
77 usa = (uint16_t *)((uint8_t *)nrec + nrec->usa_ofs);
78 /* get the Update Sequence Array Number and skip it */
80 /* get the Update Sequene Array count */
81 usa_count = nrec->usa_count - 1; /* exclude the USA number */
82 /* make it to point to the last two bytes of the RECORD's first sector */
83 block = (uint16_t *)((uint8_t *)nrec + SECTOR_SIZE(fs) - 2);
90 block = (uint16_t *)((uint8_t *)block + SECTOR_SIZE(fs));
99 static int64_t mft_record_lookup(uint32_t file, struct fs_info *fs,
100 block_t *block, void *data)
105 const uint64_t blk_size = UINT64_C(1) << BLOCK_SHIFT(fs);
111 err = fixups_writeback(fs, (NTFS_RECORD *)((uint8_t *)data + offset));
113 printf("Error in fixups_writeback()\n");
117 mrec = (MFT_RECORD *)((uint8_t *)data + offset);
118 if (mrec->mft_record_no == file)
119 return offset; /* MFT record found! */
121 offset += mrec->bytes_allocated;
122 if (offset >= BLOCK_SIZE(fs)) {
124 offset -= BLOCK_SIZE(fs);
126 ret = get_right_block(fs, *block);
130 memcpy(data, ret, blk_size);
137 static ATTR_RECORD *attr_lookup(uint32_t type, const MFT_RECORD *mrec)
142 if (!mrec || type == NTFS_AT_END)
145 attr = (ATTR_RECORD *)((uint8_t *)mrec + mrec->attrs_offset);
146 /* walk through the file attribute records */
147 for (;; attr = (ATTR_RECORD *)((uint8_t *)attr + attr->len)) {
148 if (attr->type == NTFS_AT_END)
151 if (attr->type == type)
158 static bool ntfs_match_longname(const char *str, const uint16_t *match, int len)
160 unsigned char c = -1; /* Nonzero: we have not yet seen NULL */
163 dprintf("Matching: %s\n", str);
172 if (cp != codepage.uni[0][c] && cp != codepage.uni[1][c])
180 if (*match++ != 0xFFFF)
189 static inline uint8_t *mapping_chunk_init(ATTR_RECORD *attr,
190 struct mapping_chunk *chunk,
193 memset(chunk, 0, sizeof *chunk);
196 return (uint8_t *)attr + attr->data.non_resident.mapping_pairs_offset;
201 * return 0 on success or -1 on failure.
203 static int parse_data_run(const void *stream, uint32_t *offset,
204 uint8_t *attr_len, struct mapping_chunk *chunk)
206 uint8_t *buf; /* Pointer to the zero-terminated byte stream */
207 uint8_t count; /* The count byte */
208 uint8_t v, l; /* v is the number of changed low-order VCN bytes;
209 * l is the number of changed low-order LCN bytes
219 chunk->flags &= ~MAP_MASK;
221 buf = (uint8_t *)stream + *offset;
222 if (buf > attr_len || !*buf) {
223 chunk->flags |= MAP_END; /* we're done */
228 chunk->flags |= MAP_START; /* initial chunk */
234 if (v > 8 || l > 8) /* more than 8 bytes ? */
237 byte = (uint8_t *)buf + v;
243 mask = val >> (byte_shift - 1);
244 res = (res << byte_shift) | ((val + mask) ^ mask);
247 chunk->len = res; /* get length data */
249 byte = (uint8_t *)buf + v + l;
255 res |= (int64_t)mask; /* sign-extend it */
258 res = (res << byte_shift) | *byte--;
261 /* are VCNS from cur_vcn to next_vcn - 1 unallocated ? */
263 chunk->flags |= MAP_UNALLOCATED;
265 chunk->flags |= MAP_ALLOCATED;
267 *offset += v + l + 1;
275 static enum dirent_type get_inode_mode(MFT_RECORD *mrec)
280 uint32_t dir_mask, root_mask, file_mask;
281 uint32_t dir, root, file;
283 attr = attr_lookup(NTFS_AT_FILENAME, mrec);
285 printf("No attribute found.\n");
289 fn = (FILE_NAME_ATTR *)((uint8_t *)attr +
290 attr->data.resident.value_offset);
291 dprintf("File attributes: 0x%X\n", fn->file_attrs);
293 dir_mask = NTFS_FILE_ATTR_ARCHIVE |
294 NTFS_FILE_ATTR_DUP_FILE_NAME_INDEX_PRESENT;
295 root_mask = NTFS_FILE_ATTR_READONLY | NTFS_FILE_ATTR_HIDDEN |
296 NTFS_FILE_ATTR_SYSTEM |
297 NTFS_FILE_ATTR_DUP_FILE_NAME_INDEX_PRESENT;
298 file_mask = NTFS_FILE_ATTR_ARCHIVE;
300 dir = fn->file_attrs & ~dir_mask;
301 root = fn->file_attrs & ~root_mask;
302 file = fn->file_attrs & ~file_mask;
304 dprintf("dir = 0x%X\n", dir);
305 dprintf("root= 0x%X\n", root);
306 dprintf("file = 0x%X\n", file);
307 if (((!dir && root) || (!dir && !root)) && !file)
310 return infile ? DT_REG : DT_DIR;
313 static int index_inode_setup(struct fs_info *fs, block_t start_block,
314 unsigned long mft_no, struct inode *inode)
316 uint8_t data[BLOCK_SIZE(fs)];
320 enum dirent_type d_type;
325 struct mapping_chunk chunk;
330 offset = mft_record_lookup(mft_no, fs, &start_block, &data);
332 printf("No MFT record found.\n");
336 mrec = (MFT_RECORD *)&data[offset];
338 NTFS_PVT(inode)->mft_no = mft_no;
339 NTFS_PVT(inode)->seq_no = mrec->seq_no;
341 NTFS_PVT(inode)->start_cluster = start_block >> NTFS_SB(fs)->clust_shift;
342 NTFS_PVT(inode)->here = start_block;
344 d_type = get_inode_mode(mrec);
345 if (d_type == DT_UNKNOWN) {
346 dprintf("Failed on determining inode's mode\n");
350 if (d_type == DT_DIR) { /* directory stuff */
351 dprintf("Got a directory.\n");
352 attr = attr_lookup(NTFS_AT_INDEX_ROOT, mrec);
354 printf("No attribute found.\n");
358 /* note: INDEX_ROOT is always resident */
359 ir = (INDEX_ROOT *)((uint8_t *)attr +
360 attr->data.resident.value_offset);
361 len = attr->data.resident.value_len;
362 if ((uint8_t *)ir + len > (uint8_t *)mrec +
363 NTFS_SB(fs)->mft_record_size) {
364 dprintf("Corrupt index\n");
368 NTFS_PVT(inode)->itype.index.collation_rule = ir->collation_rule;
369 NTFS_PVT(inode)->itype.index.block_size = ir->index_block_size;
370 NTFS_PVT(inode)->itype.index.block_size_shift =
371 ilog2(NTFS_PVT(inode)->itype.index.block_size);
373 /* determine the size of a vcn in the index */
374 clust_size = NTFS_PVT(inode)->itype.index.block_size;
375 if (NTFS_SB(fs)->clust_size <= clust_size) {
376 NTFS_PVT(inode)->itype.index.vcn_size = NTFS_SB(fs)->clust_size;
377 NTFS_PVT(inode)->itype.index.vcn_size_shift =
378 NTFS_SB(fs)->clust_shift;
380 NTFS_PVT(inode)->itype.index.vcn_size = BLOCK_SIZE(fs);
381 NTFS_PVT(inode)->itype.index.vcn_size_shift = BLOCK_SHIFT(fs);
383 } else if (d_type == DT_REG) { /* file stuff */
384 dprintf("Got a file.\n");
385 attr = attr_lookup(NTFS_AT_DATA, mrec);
387 printf("No attribute found.\n");
391 NTFS_PVT(inode)->non_resident = attr->non_resident;
392 NTFS_PVT(inode)->type = attr->type;
394 if (!attr->non_resident) {
395 NTFS_PVT(inode)->data.resident.offset =
396 (uint32_t)((uint8_t *)attr + attr->data.resident.value_offset);
397 inode->size = attr->data.resident.value_len;
399 attr_len = (uint8_t *)attr + attr->len;
401 stream = mapping_chunk_init(attr, &chunk, &droffset);
403 err = parse_data_run(stream, &droffset, attr_len, &chunk);
405 printf("parse_data_run()\n");
409 if (chunk.flags & MAP_UNALLOCATED)
411 if (chunk.flags & (MAP_ALLOCATED | MAP_END))
415 if (chunk.flags & MAP_END) {
416 dprintf("No mapping found\n");
420 NTFS_PVT(inode)->data.non_resident.len = chunk.len;
421 NTFS_PVT(inode)->data.non_resident.lcn = chunk.lcn;
422 inode->size = attr->data.non_resident.initialized_size;
426 inode->mode = d_type;
434 static struct inode *index_lookup(const char *dname, struct inode *dir)
436 struct fs_info *fs = dir->fs;
437 const uint64_t blk_size = BLOCK_SIZE(fs);
438 uint8_t data[blk_size];
451 struct mapping_chunk chunk;
453 struct mapping_chunk *chunks;
454 unsigned chunks_count;
460 block = NTFS_PVT(dir)->start;
461 dprintf("index_lookup() - mft record number: %d\n", NTFS_PVT(dir)->mft_no);
462 offset = mft_record_lookup(NTFS_PVT(dir)->mft_no, fs, &block, &data);
464 printf("No MFT record found.\n");
468 mrec = (MFT_RECORD *)&data[offset];
470 attr = attr_lookup(NTFS_AT_INDEX_ROOT, mrec);
472 printf("No attribute found.\n");
476 ir = (INDEX_ROOT *)((uint8_t *)attr +
477 attr->data.resident.value_offset);
478 len = attr->data.resident.value_len;
480 if ((uint8_t *)ir + len > (uint8_t *)mrec + NTFS_SB(fs)->mft_record_size)
483 ie = (INDEX_ENTRY *)((uint8_t *)&ir->index +
484 ir->index.entries_offset);
485 for (;; ie = (INDEX_ENTRY *)((uint8_t *)ie + ie->len)) {
487 if ((uint8_t *)ie < (uint8_t *)mrec ||
488 (uint8_t *)ie + sizeof(INDEX_ENTRY_HEADER) >
489 (uint8_t *)&ir->index + ir->index.index_len ||
490 (uint8_t *)ie + ie->len >
491 (uint8_t *)&ir->index + ir->index.index_len)
494 /* last entry cannot contain a key. it can however contain
495 * a pointer to a child node in the B+ tree so we just break out
497 dprintf("(0) ie->flags: 0x%X\n", ie->flags);
498 if (ie->flags & INDEX_ENTRY_END)
501 if (ntfs_match_longname(dname, ie->key.file_name.file_name,
503 dprintf("Filename matches up!\n");
504 dprintf("MFT record number = %d\n", ie->data.dir.indexed_file);
509 /* check for the presence of a child node */
510 if (!(ie->flags & INDEX_ENTRY_NODE)) {
511 printf("No child node, aborting...\n");
515 /* then descend into child node */
517 attr = attr_lookup(NTFS_AT_INDEX_ALLOCATION, mrec);
519 printf("No attribute found.\n");
523 if (!attr->non_resident) {
524 printf("WTF ?! $INDEX_ALLOCATION isn't really resident.\n");
528 attr_len = (uint8_t *)attr + attr->len;
530 stream = mapping_chunk_init(attr, &chunk, &droffset);
533 err = parse_data_run(stream, &droffset, attr_len, &chunk);
537 if (chunk.flags & MAP_UNALLOCATED)
540 if (chunk.flags & MAP_ALLOCATED)
543 } while (!(chunk.flags & MAP_END));
546 printf("No data runs found, but claims non-resident attribute\n");
550 chunks = malloc(chunks_count * sizeof *chunks);
552 malloc_error("mapping_chunk structure");
554 stream = mapping_chunk_init(attr, &chunk, &droffset);
557 err = parse_data_run(stream, &droffset, attr_len, &chunk);
561 if (chunk.flags & MAP_UNALLOCATED)
564 if (chunk.flags & MAP_ALLOCATED) {
565 dprintf("%d cluster(s) starting at 0x%X\n", chunk.len, chunk.lcn);
566 memcpy(&chunks[i++], &chunk, sizeof chunk);
569 } while (!(chunk.flags & MAP_END));
572 while (chunks_count--) {
575 while (vcn < chunks[i].len) {
576 block = ((lcn + vcn) << NTFS_SB(fs)->clust_shift) <<
577 SECTOR_SHIFT(fs) >> BLOCK_SHIFT(fs);
579 ret = (uint8_t *)get_cache(fs->fs_dev, block);
581 printf("get_cache() returned NULL\n");
585 memcpy(data, ret, blk_size);
587 err = fixups_writeback(fs, (NTFS_RECORD *)&data[0]);
589 printf("Error in fixups_writeback()\n");
593 iblock = (INDEX_BLOCK *)&data[0];
594 if (iblock->magic != NTFS_MAGIC_INDX) {
595 printf("Not a valid INDX record\n");
599 ie = (INDEX_ENTRY *)((uint8_t *)&iblock->index +
600 iblock->index.entries_offset);
601 for (;; ie = (INDEX_ENTRY *)((uint8_t *)ie + ie->len)) {
603 if ((uint8_t *)ie < (uint8_t *)iblock || (uint8_t *)ie +
604 sizeof(INDEX_ENTRY_HEADER) >
605 (uint8_t *)&iblock->index + iblock->index.index_len ||
606 (uint8_t *)ie + ie->len >
607 (uint8_t *)&iblock->index + iblock->index.index_len)
610 /* last entry cannot contain a key */
611 if (ie->flags & INDEX_ENTRY_END)
614 if (ntfs_match_longname(dname, ie->key.file_name.file_name,
616 dprintf("Filename matches up!\n");
621 vcn++; /* go to the next VCN */
624 i++; /* go to the next chunk */
628 dprintf("Index not found\n");
631 printf("%s not found!\n", dname);
636 dprintf("Index found\n");
637 inode = new_ntfs_inode(fs);
638 err = index_inode_setup(fs, NTFS_PVT(dir)->here, ie->data.dir.indexed_file,
645 dprintf("%s found!\n", dname);
650 printf("Corrupt index. Aborting lookup...\n");
655 * Convert an UTF-16LE longname to the system codepage; return
656 * the length on success or -1 on failure.
658 static int ntfs_cvt_longname(char *entry_name, const uint16_t *long_name)
664 static struct unicache unicache[256];
668 char *p = entry_name;
672 uc = &unicache[cp % 256];
674 if (__likely(uc->utf16 == cp)) {
677 for (c = 0; c < 512; c++) {
678 if (codepage.uni[0][c] == cp) {
680 *p++ = uc->cp = (uint8_t)c;
691 return (p - entry_name) - 1;
694 static int ntfs_next_extent(struct inode *inode, uint32_t lstart)
696 struct fs_info *fs = inode->fs;
697 struct ntfs_sb_info *sbi = NTFS_SB(fs);
698 uint32_t mcluster = lstart >> sbi->clust_shift;
700 const uint32_t cluster_bytes = UINT32_C(1) << sbi->clust_byte_shift;
702 const uint32_t sec_size = SECTOR_SIZE(fs);
703 const uint32_t sec_shift = SECTOR_SHIFT(fs);
705 tcluster = (inode->size + cluster_bytes - 1) >> sbi->clust_byte_shift;
706 if (mcluster >= tcluster)
707 goto out; /* Requested cluster beyond end of file */
709 if (!NTFS_PVT(inode)->non_resident) {
710 pstart = sbi->mft_block + NTFS_PVT(inode)->here;
711 pstart <<= BLOCK_SHIFT(fs) >> sec_shift;
713 pstart = NTFS_PVT(inode)->data.non_resident.lcn << sbi->clust_shift;
716 inode->next_extent.len = (inode->size + sec_size - 1) >> sec_shift;
717 inode->next_extent.pstart = pstart;
725 static uint32_t ntfs_getfssec(struct file *file, char *buf, int sectors,
728 uint8_t non_resident;
731 struct fs_info *fs = file->fs;
732 uint8_t data[BLOCK_SIZE(fs)];
733 struct inode *inode = file->inode;
739 non_resident = NTFS_PVT(inode)->non_resident;
741 ret = generic_getfssec(file, buf, sectors, have_more);
746 block = NTFS_PVT(inode)->here;
747 offset = mft_record_lookup(NTFS_PVT(inode)->mft_no, fs, &block, &data);
749 printf("No MFT record found.\n");
753 mrec = (MFT_RECORD *)&data[offset];
755 attr = attr_lookup(NTFS_AT_DATA, mrec);
757 printf("No attribute found.\n");
761 p = (char *)((uint8_t *)attr + attr->data.resident.value_offset);
763 /* p now points to the data offset, so let's copy it into buf */
764 memcpy(buf, p, inode->size);
775 static int ntfs_readdir(struct file *file, struct dirent *dirent)
778 struct fs_info *fs = file->fs;
779 uint8_t data[BLOCK_SIZE(fs)];
781 struct inode *inode = file->inode;
785 char filename[NTFS_MAX_FILE_NAME_LEN + 1];
788 offset = mft_record_lookup(NTFS_PVT(inode)->mft_no, fs, &block, &data);
790 printf("No MFT record found.\n");
794 mrec = (MFT_RECORD *)&data[offset];
796 attr = attr_lookup(NTFS_AT_FILENAME, mrec);
798 printf("No attribute found.\n");
802 fn = (FILE_NAME_ATTR *)((uint8_t *)attr +
803 attr->data.resident.value_offset);
805 len = ntfs_cvt_longname(filename, fn->file_name);
806 if (len < 0 || len != fn->file_name_len) {
807 printf("Failed on converting UTF-16LE LFN to OEM LFN\n");
811 dirent->d_ino = NTFS_PVT(inode)->mft_no;
812 dirent->d_off = file->offset++;
813 dirent->d_reclen = offsetof(struct dirent, d_name) + len + 1;
814 dirent->d_type = get_inode_mode(mrec);
815 memcpy(dirent->d_name, filename, len + 1);
823 static struct inode *ntfs_iget(const char *dname, struct inode *parent)
825 return index_lookup(dname, parent);
828 static struct inode *ntfs_iget_root(struct fs_info *fs)
830 struct inode *inode = new_ntfs_inode(fs);
835 err = index_inode_setup(fs, 0, FILE_root, inode);
839 NTFS_PVT(inode)->start = NTFS_PVT(inode)->here;
849 /* Initialize the filesystem metadata and return block size in bits */
850 static int ntfs_fs_init(struct fs_info *fs)
852 struct ntfs_bpb ntfs;
853 struct ntfs_sb_info *sbi;
854 struct disk *disk = fs->fs_dev->disk;
855 uint8_t clust_per_mft_record;
857 disk->rdwr_sectors(disk, &ntfs, 0, 1, 0);
860 if (!ntfs_check_sb_fields(&ntfs))
863 /* Note: clust_per_mft_record can be a negative number */
864 clust_per_mft_record = ntfs.clust_per_mft_record < 0 ?
865 -ntfs.clust_per_mft_record : ntfs.clust_per_mft_record;
867 SECTOR_SHIFT(fs) = disk->sector_shift;
869 /* We need _at least_ 1 KiB to read the whole MFT record */
870 BLOCK_SHIFT(fs) = ilog2(ntfs.sec_per_clust) + SECTOR_SHIFT(fs);
871 if (BLOCK_SHIFT(fs) < clust_per_mft_record)
872 BLOCK_SHIFT(fs) = clust_per_mft_record;
874 SECTOR_SIZE(fs) = 1 << SECTOR_SHIFT(fs);
875 BLOCK_SIZE(fs) = 1 << BLOCK_SHIFT(fs);
877 sbi = malloc(sizeof *sbi);
879 malloc_error("ntfs_sb_info structure");
883 sbi->clust_shift = ilog2(ntfs.sec_per_clust);
884 sbi->clust_byte_shift = sbi->clust_shift + SECTOR_SHIFT(fs);
885 sbi->clust_mask = ntfs.sec_per_clust - 1;
886 sbi->clust_size = ntfs.sec_per_clust << SECTOR_SHIFT(fs);
887 sbi->mft_record_size = 1 << clust_per_mft_record;
889 sbi->mft_block = ntfs.mft_lclust << sbi->clust_shift <<
890 SECTOR_SHIFT(fs) >> BLOCK_SHIFT(fs);
891 /* 16 MFT entries reserved for metadata files (approximately 16 KiB) */
892 sbi->mft_size = (clust_per_mft_record << sbi->clust_shift) << 4;
894 sbi->clusters = ntfs.total_sectors << SECTOR_SHIFT(fs) >> sbi->clust_shift;
895 if (sbi->clusters > 0xFFFFFFFFFFF4ULL)
896 sbi->clusters = 0xFFFFFFFFFFF4ULL;
898 /* Initialize the cache */
899 cache_init(fs->fs_dev, BLOCK_SHIFT(fs));
901 return BLOCK_SHIFT(fs);
904 const struct fs_ops ntfs_fs_ops = {
906 .fs_flags = FS_USEMEM | FS_THISIND,
907 .fs_init = ntfs_fs_init,
909 .getfssec = ntfs_getfssec,
910 .close_file = generic_close_file,
911 .mangle_name = generic_mangle_name,
912 .load_config = generic_load_config,
913 .readdir = ntfs_readdir,
914 .iget_root = ntfs_iget_root,
916 .next_extent = ntfs_next_extent,