?  search:
summary | log | graphiclog1 | graphiclog2 | commit | commitdiff | tree | refs | edit | fork
blame | history | raw | HEAD
ntfs: Make byte_shift a const
[syslinux/sherbszt.git] / core / fs / ntfs / ntfs.c
blob4e6de65b61f03005f1495bb7790858901e366803
1 /*
2 * Copyright (C) 2011-2012 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 static struct ntfs_readdir_state *readdir_state;
39
40 /*** Function declarations */
41 static f_mft_record_lookup ntfs_mft_record_lookup_3_0;
42 static f_mft_record_lookup ntfs_mft_record_lookup_3_1;
43
44 /*** Function definitions */
45
46 /* Check if there are specific zero fields in an NTFS boot sector */
47 static inline int ntfs_check_zero_fields(const struct ntfs_bpb *sb)
48 {
49 return !sb->res_sectors && (!sb->zero_0[0] && !sb->zero_0[1] &&
50 !sb->zero_0[2]) && !sb->zero_1 && !sb->zero_2 &&
51 !sb->zero_3;
52 }
53
54 static inline int ntfs_check_sb_fields(const struct ntfs_bpb *sb)
55 {
56 return ntfs_check_zero_fields(sb) &&
57 (!memcmp(sb->oem_name, "NTFS ", 8) ||
58 !memcmp(sb->oem_name, "MSWIN4.0", 8) ||
59 !memcmp(sb->oem_name, "MSWIN4.1", 8));
60 }
61
62 static inline struct inode *new_ntfs_inode(struct fs_info *fs)
63 {
64 struct inode *inode;
65
66 inode = alloc_inode(fs, 0, sizeof(struct ntfs_inode));
67 if (!inode)
68 malloc_error("inode structure");
69
70 return inode;
71 }
72
73 static void ntfs_fixups_writeback(struct fs_info *fs, struct ntfs_record *nrec)
74 {
75 uint16_t *usa;
76 uint16_t usa_no;
77 uint16_t usa_count;
78 uint16_t *blk;
79
80 dprintf("in %s()\n", __func__);
81
82 if (nrec->magic != NTFS_MAGIC_FILE && nrec->magic != NTFS_MAGIC_INDX)
83 return;
84
85 /* get the Update Sequence Array offset */
86 usa = (uint16_t *)((uint8_t *)nrec + nrec->usa_ofs);
87 /* get the Update Sequence Array Number and skip it */
88 usa_no = *usa++;
89 /* get the Update Sequene Array count */
90 usa_count = nrec->usa_count - 1; /* exclude the USA number */
91 /* make it to point to the last two bytes of the RECORD's first sector */
92 blk = (uint16_t *)((uint8_t *)nrec + SECTOR_SIZE(fs) - 2);
93
94 while (usa_count--) {
95 if (*blk != usa_no)
96 break;
97
98 *blk = *usa++;
99 blk = (uint16_t *)((uint8_t *)blk + SECTOR_SIZE(fs));
100 }
101 }
102
103 /* read content from cache */
104 static int ntfs_read(struct fs_info *fs, void *buf, size_t len, uint64_t count,
105 block_t *blk, uint64_t *blk_offset,
106 uint64_t *blk_next_offset, uint64_t *lcn)
107 {
108 uint8_t *data;
109 uint64_t offset = *blk_offset;
110 const uint32_t clust_byte_shift = NTFS_SB(fs)->clust_byte_shift;
111 const uint64_t blk_size = UINT64_C(1) << BLOCK_SHIFT(fs);
112 uint64_t bytes;
113 uint64_t lbytes;
114 uint64_t loffset;
115 uint64_t k;
116
117 dprintf("in %s()\n", __func__);
118
119 if (count > len)
120 goto out;
121
122 data = (uint8_t *)get_cache(fs->fs_dev, *blk);
123 if (!data)
124 goto out;
125
126 if (!offset)
127 offset = (*lcn << clust_byte_shift) % blk_size;
128
129 dprintf("LCN: 0x%X\n", *lcn);
130 dprintf("offset: 0x%X\n", offset);
131
132 bytes = count; /* bytes to copy */
133 lbytes = blk_size - offset; /* bytes left to copy */
134 if (lbytes >= bytes) {
135 /* so there's room enough, then copy the whole content */
136 memcpy(buf, data + offset, bytes);
137 loffset = offset;
138 offset += count;
139 } else {
140 dprintf("bytes: %u\n", bytes);
141 dprintf("bytes left: %u\n", lbytes);
142 /* otherwise, let's copy it partially... */
143 k = 0;
144 while (bytes) {
145 memcpy(buf + k, data + offset, lbytes);
146 bytes -= lbytes;
147 loffset = offset;
148 offset += lbytes;
149 k += lbytes;
150 if (offset >= blk_size) {
151 /* then fetch a new FS block */
152 data = (uint8_t *)get_cache(fs->fs_dev, ++*blk);
153 if (!data)
154 goto out;
155
156 lbytes = bytes;
157 loffset = offset;
158 offset = 0;
159 }
160 }
161 }
162
163 if (loffset >= blk_size)
164 loffset = 0; /* it must be aligned on a block boundary */
165
166 *blk_offset = loffset;
167
168 if (blk_next_offset)
169 *blk_next_offset = offset;
170
171 *lcn += blk_size / count; /* update LCN */
172
173 return 0;
174
175 out:
176 return -1;
177 }
178
179 static struct ntfs_mft_record *ntfs_mft_record_lookup_3_0(struct fs_info *fs,
180 uint32_t file, block_t *blk)
181 {
182 const uint64_t mft_record_size = NTFS_SB(fs)->mft_record_size;
183 uint8_t *buf;
184 const block_t mft_blk = NTFS_SB(fs)->mft_blk;
185 block_t cur_blk;
186 block_t right_blk;
187 uint64_t offset;
188 uint64_t next_offset;
189 const uint32_t mft_record_shift = ilog2(mft_record_size);
190 const uint32_t clust_byte_shift = NTFS_SB(fs)->clust_byte_shift;
191 uint64_t lcn;
192 int err;
193 struct ntfs_mft_record *mrec;
194
195 dprintf("in %s()\n", __func__);
196
197 buf = (uint8_t *)malloc(mft_record_size);
198 if (!buf)
199 malloc_error("uint8_t *");
200
201 /* determine MFT record's LCN and block number */
202 lcn = NTFS_SB(fs)->mft_lcn + (file << mft_record_shift >> clust_byte_shift);
203 cur_blk = (lcn << clust_byte_shift >> BLOCK_SHIFT(fs)) - mft_blk;
204 offset = (file << mft_record_shift) % BLOCK_SIZE(fs);
205 for (;;) {
206 right_blk = cur_blk + mft_blk;
207 err = ntfs_read(fs, buf, mft_record_size, mft_record_size, &right_blk,
208 &offset, &next_offset, &lcn);
209 if (err) {
210 printf("Error while reading from cache.\n");
211 break;
212 }
213
214 ntfs_fixups_writeback(fs, (struct ntfs_record *)buf);
215
216 mrec = (struct ntfs_mft_record *)buf;
217 /* check if it has a valid magic number */
218 if (mrec->magic == NTFS_MAGIC_FILE) {
219 if (blk)
220 *blk = cur_blk; /* update record starting block */
221
222 return mrec; /* found MFT record */
223 }
224
225 if (next_offset >= BLOCK_SIZE(fs)) {
226 /* try the next FS block */
227 offset = 0;
228 cur_blk = right_blk - mft_blk + 1;
229 } else {
230 /* there's still content to fetch in the current block */
231 cur_blk = right_blk - mft_blk;
232 offset = next_offset; /* update FS block offset */
233 }
234 }
235
236 free(buf);
237
238 return NULL;
239 }
240
241 static struct ntfs_mft_record *ntfs_mft_record_lookup_3_1(struct fs_info *fs,
242 uint32_t file, block_t *blk)
243 {
244 const uint64_t mft_record_size = NTFS_SB(fs)->mft_record_size;
245 uint8_t *buf;
246 const block_t mft_blk = NTFS_SB(fs)->mft_blk;
247 block_t cur_blk;
248 block_t right_blk;
249 uint64_t offset;
250 uint64_t next_offset;
251 const uint32_t mft_record_shift = ilog2(mft_record_size);
252 const uint32_t clust_byte_shift = NTFS_SB(fs)->clust_byte_shift;
253 uint64_t lcn;
254 int err;
255 struct ntfs_mft_record *mrec;
256
257 dprintf("in %s()\n", __func__);
258
259 buf = (uint8_t *)malloc(mft_record_size);
260 if (!buf)
261 malloc_error("uint8_t *");
262
263 lcn = NTFS_SB(fs)->mft_lcn + (file << mft_record_shift >> clust_byte_shift);
264 cur_blk = (lcn << clust_byte_shift >> BLOCK_SHIFT(fs)) - mft_blk;
265 offset = (file << mft_record_shift) % BLOCK_SIZE(fs);
266 for (;;) {
267 right_blk = cur_blk + NTFS_SB(fs)->mft_blk;
268 err = ntfs_read(fs, buf, mft_record_size, mft_record_size, &right_blk,
269 &offset, &next_offset, &lcn);
270 if (err) {
271 printf("Error while reading from cache.\n");
272 break;
273 }
274
275 ntfs_fixups_writeback(fs, (struct ntfs_record *)buf);
276
277 mrec = (struct ntfs_mft_record *)buf;
278 /* Check if the NTFS 3.1 MFT record number matches */
279 if (mrec->magic == NTFS_MAGIC_FILE && mrec->mft_record_no == file) {
280 if (blk)
281 *blk = cur_blk; /* update record starting block */
282
283 return mrec; /* found MFT record */
284 }
285
286 if (next_offset >= BLOCK_SIZE(fs)) {
287 /* try the next FS block */
288 offset = 0;
289 cur_blk = right_blk - NTFS_SB(fs)->mft_blk + 1;
290 } else {
291 /* there's still content to fetch in the current block */
292 cur_blk = right_blk - NTFS_SB(fs)->mft_blk;
293 offset = next_offset; /* update FS block offset */
294 }
295 }
296
297 free(buf);
298
299 return NULL;
300 }
301
302 static bool ntfs_filename_cmp(const char *dname, struct ntfs_idx_entry *ie)
303 {
304 const uint16_t *entry_fn;
305 uint8_t entry_fn_len;
306 unsigned i;
307
308 dprintf("in %s()\n", __func__);
309
310 entry_fn = ie->key.file_name.file_name;
311 entry_fn_len = ie->key.file_name.file_name_len;
312
313 if (strlen(dname) != entry_fn_len)
314 return false;
315
316 /* Do case-sensitive compares for Posix file names */
317 if (ie->key.file_name.file_name_type == FILE_NAME_POSIX) {
318 for (i = 0; i < entry_fn_len; i++)
319 if (entry_fn[i] != dname[i])
320 return false;
321 } else {
322 for (i = 0; i < entry_fn_len; i++)
323 if (tolower(entry_fn[i]) != tolower(dname[i]))
324 return false;
325 }
326
327 return true;
328 }
329
330 static inline uint8_t *mapping_chunk_init(struct ntfs_attr_record *attr,
331 struct mapping_chunk *chunk,
332 uint32_t *offset)
333 {
334 memset(chunk, 0, sizeof *chunk);
335 *offset = 0U;
336
337 return (uint8_t *)attr + attr->data.non_resident.mapping_pairs_offset;
338 }
339
340 /* Parse data runs.
341 *
342 * return 0 on success or -1 on failure.
343 */
344 static int parse_data_run(const void *stream, uint32_t *offset,
345 uint8_t *attr_len, struct mapping_chunk *chunk)
346 {
347 uint8_t *buf; /* Pointer to the zero-terminated byte stream */
348 uint8_t count; /* The count byte */
349 uint8_t v, l; /* v is the number of changed low-order VCN bytes;
350 * l is the number of changed low-order LCN bytes
351 */
352 uint8_t *byte;
353 const int byte_shift = 8;
354 int mask;
355 int64_t res;
356
357 (void)attr_len;
358
359 dprintf("in %s()\n", __func__);
360
361 chunk->flags &= ~MAP_MASK;
362
363 buf = (uint8_t *)stream + *offset;
364 if (buf > attr_len || !*buf) {
365 chunk->flags |= MAP_END; /* we're done */
366 return 0;
367 }
368
369 if (!*offset)
370 chunk->flags |= MAP_START; /* initial chunk */
371
372 count = *buf;
373 v = count & 0x0F;
374 l = count >> 4;
375
376 if (v > 8 || l > 8) /* more than 8 bytes ? */
377 goto out;
378
379 byte = (uint8_t *)buf + v;
380 count = v;
381
382 res = 0LL;
383 while (count--)
384 res = (res << byte_shift) | *byte--;
385
386 chunk->len = res; /* get length data */
387
388 byte = (uint8_t *)buf + v + l;
389 count = l;
390
391 mask = 0xFFFFFFFF;
392 res = 0LL;
393 if (*byte & 0x80)
394 res |= (int64_t)mask; /* sign-extend it */
395
396 while (count--)
397 res = (res << byte_shift) | *byte--;
398
399 chunk->lcn += res;
400 /* are VCNS from cur_vcn to next_vcn - 1 unallocated ? */
401 if (!chunk->lcn)
402 chunk->flags |= MAP_UNALLOCATED;
403 else
404 chunk->flags |= MAP_ALLOCATED;
405
406 *offset += v + l + 1;
407
408 return 0;
409
410 out:
411 return -1;
412 }
413
414 static struct ntfs_mft_record *
415 ntfs_attr_list_lookup(struct fs_info *fs, struct ntfs_attr_record *attr,
416 uint32_t type, struct ntfs_mft_record *mrec)
417 {
418 uint8_t *attr_len;
419 struct mapping_chunk chunk;
420 uint32_t offset;
421 uint8_t *stream;
422 int err;
423 const uint64_t blk_size = UINT64_C(1) << BLOCK_SHIFT(fs);
424 uint8_t buf[blk_size];
425 uint64_t blk_offset;
426 int64_t vcn;
427 int64_t lcn;
428 int64_t last_lcn;
429 block_t blk;
430 struct ntfs_attr_list_entry *attr_entry;
431 uint32_t len = 0;
432 struct ntfs_mft_record *retval;
433 uint64_t start_blk = 0;
434
435 dprintf("in %s()\n", __func__);
436
437 if (attr->non_resident)
438 goto handle_non_resident_attr;
439
440 attr_entry = (struct ntfs_attr_list_entry *)
441 ((uint8_t *)attr + attr->data.resident.value_offset);
442 len = attr->data.resident.value_len;
443 for (; (uint8_t *)attr_entry < (uint8_t *)attr + len;
444 attr_entry = (struct ntfs_attr_list_entry *)((uint8_t *)attr_entry +
445 attr_entry->length)) {
446 dprintf("<$ATTRIBUTE_LIST> Attribute type: 0x%X\n",
447 attr_entry->type);
448 if (attr_entry->type == type)
449 goto found; /* We got the attribute! :-) */
450 }
451
452 printf("No attribute found.\n");
453 goto out;
454
455 handle_non_resident_attr:
456 attr_len = (uint8_t *)attr + attr->len;
457 stream = mapping_chunk_init(attr, &chunk, &offset);
458 do {
459 err = parse_data_run(stream, &offset, attr_len, &chunk);
460 if (err) {
461 printf("parse_data_run()\n");
462 goto out;
463 }
464
465 if (chunk.flags & MAP_UNALLOCATED)
466 continue;
467 if (chunk.flags & MAP_END)
468 break;
469 if (chunk.flags & MAP_ALLOCATED) {
470 vcn = 0;
471 lcn = chunk.lcn;
472 while (vcn < chunk.len) {
473 blk = (lcn + vcn) << NTFS_SB(fs)->clust_byte_shift >>
474 BLOCK_SHIFT(fs);
475 blk_offset = 0;
476 last_lcn = lcn;
477 lcn += vcn;
478 err = ntfs_read(fs, buf, blk_size, blk_size, &blk,
479 &blk_offset, NULL, (uint64_t *)&lcn);
480 if (err) {
481 printf("Error while reading from cache.\n");
482 goto out;
483 }
484
485 attr_entry = (struct ntfs_attr_list_entry *)&buf;
486 len = attr->data.non_resident.data_size;
487 for (; (uint8_t *)attr_entry < (uint8_t *)&buf[0] + len;
488 attr_entry = (struct ntfs_attr_list_entry *)
489 ((uint8_t *)attr_entry + attr_entry->length)) {
490 dprintf("<$ATTRIBUTE_LIST> Attribute type: 0x%x\n",
491 attr_entry->type);
492 if (attr_entry->type == type)
493 goto found; /* We got the attribute! :-) */
494 }
495
496 lcn = last_lcn; /* restore original LCN */
497 /* go to the next VCN */
498 vcn += (blk_size / (1 << NTFS_SB(fs)->clust_byte_shift));
499 }
500 }
501 } while (!(chunk.flags & MAP_END));
502
503 printf("No attribute found.\n");
504
505 out:
506 return NULL;
507
508 found:
509 /* At this point we have the attribute we were looking for. Now we
510 * will look for the MFT record that stores information about this
511 * attribute.
512 */
513
514 /* Check if the attribute type we're looking for is in the same
515 * MFT record. If so, we do not need to look it up again - return it.
516 */
517 if (mrec->mft_record_no == attr_entry->mft_ref)
518 return mrec;
519
520 retval = NTFS_SB(fs)->mft_record_lookup(fs, attr_entry->mft_ref,
521 &start_blk);
522 if (!retval) {
523 printf("No MFT record found!\n");
524 goto out;
525 }
526
527 /* return the found MFT record */
528 return retval;
529 }
530
531 static struct ntfs_attr_record *
532 __ntfs_attr_lookup(struct fs_info *fs, uint32_t type,
533 struct ntfs_mft_record **mrec)
534 {
535 struct ntfs_mft_record *_mrec = *mrec;
536 struct ntfs_attr_record *attr;
537 struct ntfs_attr_record *attr_list_attr;
538
539 dprintf("in %s()\n", __func__);
540
541 if (!_mrec || type == NTFS_AT_END)
542 goto out;
543
544 again:
545 attr_list_attr = NULL;
546
547 attr = (struct ntfs_attr_record *)((uint8_t *)_mrec + _mrec->attrs_offset);
548 /* walk through the file attribute records */
549 for (;; attr = (struct ntfs_attr_record *)((uint8_t *)attr + attr->len)) {
550 if (attr->type == NTFS_AT_END)
551 break;
552
553 if (attr->type == NTFS_AT_ATTR_LIST) {
554 dprintf("MFT record #%lu has an $ATTRIBUTE_LIST attribute.\n",
555 _mrec->mft_record_no);
556 attr_list_attr = attr;
557 continue;
558 }
559
560 if (attr->type == type)
561 break;
562 }
563
564 /* if the record has an $ATTRIBUTE_LIST attribute associated
565 * with it, then we need to look for the wanted attribute in
566 * it as well.
567 */
568 if (attr->type == NTFS_AT_END && attr_list_attr) {
569 struct ntfs_mft_record *retval;
570
571 retval = ntfs_attr_list_lookup(fs, attr_list_attr, type, _mrec);
572 if (!retval)
573 goto out;
574
575 _mrec = retval;
576 goto again;
577 } else if (attr->type == NTFS_AT_END && !attr_list_attr) {
578 attr = NULL;
579 }
580
581 return attr;
582
583 out:
584 return NULL;
585 }
586
587 static inline struct ntfs_attr_record *
588 ntfs_attr_lookup(struct fs_info *fs, uint32_t type,
589 struct ntfs_mft_record **mmrec,
590 struct ntfs_mft_record *mrec)
591 {
592 struct ntfs_mft_record *_mrec = mrec;
593 struct ntfs_mft_record *other = *mmrec;
594 struct ntfs_attr_record *retval = NULL;
595
596 if (mrec == other)
597 return __ntfs_attr_lookup(fs, type, &other);
598
599 retval = __ntfs_attr_lookup(fs, type, &_mrec);
600 if (!retval) {
601 _mrec = other;
602 retval = __ntfs_attr_lookup(fs, type, &other);
603 if (!retval)
604 other = _mrec;
605 } else if (retval && (_mrec != mrec)) {
606 other = _mrec;
607 }
608
609 return retval;
610 }
611
612 static inline enum dirent_type get_inode_mode(struct ntfs_mft_record *mrec)
613 {
614 return mrec->flags & MFT_RECORD_IS_DIRECTORY ? DT_DIR : DT_REG;
615 }
616
617 static int index_inode_setup(struct fs_info *fs, unsigned long mft_no,
618 struct inode *inode)
619 {
620 uint64_t start_blk = 0;
621 struct ntfs_mft_record *mrec, *lmrec;
622 struct ntfs_attr_record *attr;
623 enum dirent_type d_type;
624 uint8_t *attr_len;
625 struct mapping_chunk chunk;
626 int err;
627 uint8_t *stream;
628 uint32_t offset;
629
630 dprintf("in %s()\n", __func__);
631
632 mrec = NTFS_SB(fs)->mft_record_lookup(fs, mft_no, &start_blk);
633 if (!mrec) {
634 printf("No MFT record found.\n");
635 goto out;
636 }
637
638 lmrec = mrec;
639
640 NTFS_PVT(inode)->mft_no = mft_no;
641 NTFS_PVT(inode)->seq_no = mrec->seq_no;
642
643 NTFS_PVT(inode)->start_cluster = start_blk >> NTFS_SB(fs)->clust_shift;
644 NTFS_PVT(inode)->here = start_blk;
645
646 d_type = get_inode_mode(mrec);
647 if (d_type == DT_DIR) { /* directory stuff */
648 dprintf("Got a directory.\n");
649 attr = ntfs_attr_lookup(fs, NTFS_AT_INDEX_ROOT, &mrec, lmrec);
650 if (!attr) {
651 printf("No attribute found.\n");
652 goto out;
653 }
654
655 /* check if we have a previous allocated state structure */
656 if (readdir_state) {
657 free(readdir_state);
658 readdir_state = NULL;
659 }
660
661 /* allocate our state structure */
662 readdir_state = malloc(sizeof *readdir_state);
663 if (!readdir_state)
664 malloc_error("ntfs_readdir_state structure");
665
666 readdir_state->mft_no = mft_no;
667 /* obviously, the ntfs_readdir() caller will start from INDEX root */
668 readdir_state->in_idx_root = true;
669 } else if (d_type == DT_REG) { /* file stuff */
670 dprintf("Got a file.\n");
671 attr = ntfs_attr_lookup(fs, NTFS_AT_DATA, &mrec, lmrec);
672 if (!attr) {
673 printf("No attribute found.\n");
674 goto out;
675 }
676
677 NTFS_PVT(inode)->non_resident = attr->non_resident;
678 NTFS_PVT(inode)->type = attr->type;
679
680 if (!attr->non_resident) {
681 NTFS_PVT(inode)->data.resident.offset =
682 (uint32_t)((uint8_t *)attr + attr->data.resident.value_offset);
683 inode->size = attr->data.resident.value_len;
684 } else {
685 attr_len = (uint8_t *)attr + attr->len;
686
687 stream = mapping_chunk_init(attr, &chunk, &offset);
688 NTFS_PVT(inode)->data.non_resident.rlist = NULL;
689 for (;;) {
690 err = parse_data_run(stream, &offset, attr_len, &chunk);
691 if (err) {
692 printf("parse_data_run()\n");
693 goto out;
694 }
695
696 if (chunk.flags & MAP_UNALLOCATED)
697 continue;
698 if (chunk.flags & MAP_END)
699 break;
700 if (chunk.flags & MAP_ALLOCATED) {
701 /* append new run to the runlist */
702 runlist_append(&NTFS_PVT(inode)->data.non_resident.rlist,
703 (struct runlist_element *)&chunk);
704 /* update for next VCN */
705 chunk.vcn += chunk.len;
706 }
707 }
708
709 if (runlist_is_empty(NTFS_PVT(inode)->data.non_resident.rlist)) {
710 printf("No mapping found\n");
711 goto out;
712 }
713
714 inode->size = attr->data.non_resident.initialized_size;
715 }
716 }
717
718 inode->mode = d_type;
719
720 free(mrec);
721
722 return 0;
723
724 out:
725 free(mrec);
726
727 return -1;
728 }
729
730 static struct inode *ntfs_index_lookup(const char *dname, struct inode *dir)
731 {
732 struct fs_info *fs = dir->fs;
733 struct ntfs_mft_record *mrec, *lmrec;
734 block_t blk;
735 uint64_t blk_offset;
736 struct ntfs_attr_record *attr;
737 struct ntfs_idx_root *ir;
738 struct ntfs_idx_entry *ie;
739 const uint64_t blk_size = UINT64_C(1) << BLOCK_SHIFT(fs);
740 uint8_t buf[blk_size];
741 struct ntfs_idx_allocation *iblk;
742 int err;
743 uint8_t *stream;
744 uint8_t *attr_len;
745 struct mapping_chunk chunk;
746 uint32_t offset;
747 int64_t vcn;
748 int64_t lcn;
749 int64_t last_lcn;
750 struct inode *inode;
751
752 dprintf("in %s()\n", __func__);
753
754 mrec = NTFS_SB(fs)->mft_record_lookup(fs, NTFS_PVT(dir)->mft_no, NULL);
755 if (!mrec) {
756 printf("No MFT record found.\n");
757 goto out;
758 }
759
760 lmrec = mrec;
761 attr = ntfs_attr_lookup(fs, NTFS_AT_INDEX_ROOT, &mrec, lmrec);
762 if (!attr) {
763 printf("No attribute found.\n");
764 goto out;
765 }
766
767 ir = (struct ntfs_idx_root *)((uint8_t *)attr +
768 attr->data.resident.value_offset);
769 ie = (struct ntfs_idx_entry *)((uint8_t *)&ir->index +
770 ir->index.entries_offset);
771 for (;; ie = (struct ntfs_idx_entry *)((uint8_t *)ie + ie->len)) {
772 /* bounds checks */
773 if ((uint8_t *)ie < (uint8_t *)mrec ||
774 (uint8_t *)ie + sizeof(struct ntfs_idx_entry_header) >
775 (uint8_t *)&ir->index + ir->index.index_len ||
776 (uint8_t *)ie + ie->len >
777 (uint8_t *)&ir->index + ir->index.index_len)
778 goto index_err;
779
780 /* last entry cannot contain a key. it can however contain
781 * a pointer to a child node in the B+ tree so we just break out
782 */
783 if (ie->flags & INDEX_ENTRY_END)
784 break;
785
786 if (ntfs_filename_cmp(dname, ie))
787 goto found;
788 }
789
790 /* check for the presence of a child node */
791 if (!(ie->flags & INDEX_ENTRY_NODE)) {
792 printf("No child node, aborting...\n");
793 goto out;
794 }
795
796 /* then descend into child node */
797
798 attr = ntfs_attr_lookup(fs, NTFS_AT_INDEX_ALLOCATION, &mrec, lmrec);
799 if (!attr) {
800 printf("No attribute found.\n");
801 goto out;
802 }
803
804 if (!attr->non_resident) {
805 printf("WTF ?! $INDEX_ALLOCATION isn't really resident.\n");
806 goto out;
807 }
808
809 attr_len = (uint8_t *)attr + attr->len;
810 stream = mapping_chunk_init(attr, &chunk, &offset);
811 do {
812 err = parse_data_run(stream, &offset, attr_len, &chunk);
813 if (err)
814 break;
815
816 if (chunk.flags & MAP_UNALLOCATED)
817 continue;
818
819 if (chunk.flags & MAP_ALLOCATED) {
820 dprintf("%d cluster(s) starting at 0x%08llX\n", chunk.len,
821 chunk.lcn);
822
823 vcn = 0;
824 lcn = chunk.lcn;
825 while (vcn < chunk.len) {
826 blk = (lcn + vcn) << NTFS_SB(fs)->clust_shift <<
827 SECTOR_SHIFT(fs) >> BLOCK_SHIFT(fs);
828
829 blk_offset = 0;
830 last_lcn = lcn;
831 lcn += vcn;
832 err = ntfs_read(fs, &buf, blk_size, blk_size, &blk,
833 &blk_offset, NULL, (uint64_t *)&lcn);
834 if (err) {
835 printf("Error while reading from cache.\n");
836 goto not_found;
837 }
838
839 ntfs_fixups_writeback(fs, (struct ntfs_record *)&buf);
840
841 iblk = (struct ntfs_idx_allocation *)&buf;
842 if (iblk->magic != NTFS_MAGIC_INDX) {
843 printf("Not a valid INDX record.\n");
844 goto not_found;
845 }
846
847 ie = (struct ntfs_idx_entry *)((uint8_t *)&iblk->index +
848 iblk->index.entries_offset);
849 for (;; ie = (struct ntfs_idx_entry *)((uint8_t *)ie +
850 ie->len)) {
851 /* bounds checks */
852 if ((uint8_t *)ie < (uint8_t *)iblk || (uint8_t *)ie +
853 sizeof(struct ntfs_idx_entry_header) >
854 (uint8_t *)&iblk->index + iblk->index.index_len ||
855 (uint8_t *)ie + ie->len >
856 (uint8_t *)&iblk->index + iblk->index.index_len)
857 goto index_err;
858
859 /* last entry cannot contain a key */
860 if (ie->flags & INDEX_ENTRY_END)
861 break;
862
863 if (ntfs_filename_cmp(dname, ie))
864 goto found;
865 }
866
867 lcn = last_lcn; /* restore the original LCN */
868 /* go to the next VCN */
869 vcn += (blk_size / (1 << NTFS_SB(fs)->clust_byte_shift));
870 }
871 }
872 } while (!(chunk.flags & MAP_END));
873
874 not_found:
875 dprintf("Index not found\n");
876
877 out:
878 free(mrec);
879
880 return NULL;
881
882 found:
883 dprintf("Index found\n");
884 inode = new_ntfs_inode(fs);
885 err = index_inode_setup(fs, ie->data.dir.indexed_file, inode);
886 if (err) {
887 printf("Error in index_inode_setup()\n");
888 free(inode);
889 goto out;
890 }
891
892 free(mrec);
893
894 return inode;
895
896 index_err:
897 printf("Corrupt index. Aborting lookup...\n");
898 goto out;
899 }
900
901 /* Convert an UTF-16LE LFN to OEM LFN */
902 static uint8_t ntfs_cvt_filename(char *filename,
903 const struct ntfs_idx_entry *ie)
904 {
905 const uint16_t *entry_fn;
906 uint8_t entry_fn_len;
907 unsigned i;
908
909 entry_fn = ie->key.file_name.file_name;
910 entry_fn_len = ie->key.file_name.file_name_len;
911
912 for (i = 0; i < entry_fn_len; i++)
913 filename[i] = (char)entry_fn[i];
914
915 filename[i] = '\0';
916
917 return entry_fn_len;
918 }
919
920 static int ntfs_next_extent(struct inode *inode, uint32_t lstart)
921 {
922 struct fs_info *fs = inode->fs;
923 struct ntfs_sb_info *sbi = NTFS_SB(fs);
924 sector_t pstart = 0;
925 struct runlist *rlist;
926 struct runlist *ret;
927 const uint32_t sec_size = SECTOR_SIZE(fs);
928 const uint32_t sec_shift = SECTOR_SHIFT(fs);
929
930 dprintf("in %s()\n", __func__);
931
932 if (!NTFS_PVT(inode)->non_resident) {
933 pstart = (sbi->mft_blk + NTFS_PVT(inode)->here) << BLOCK_SHIFT(fs) >>
934 sec_shift;
935 inode->next_extent.len = (inode->size + sec_size - 1) >> sec_shift;
936 } else {
937 rlist = NTFS_PVT(inode)->data.non_resident.rlist;
938
939 if (!lstart || lstart >= NTFS_PVT(inode)->here) {
940 if (runlist_is_empty(rlist))
941 goto out; /* nothing to do ;-) */
942
943 ret = runlist_remove(&rlist);
944
945 NTFS_PVT(inode)->here =
946 ((ret->run.len << sbi->clust_byte_shift) >> sec_shift);
947
948 pstart = ret->run.lcn << sbi->clust_shift;
949 inode->next_extent.len =
950 ((ret->run.len << sbi->clust_byte_shift) + sec_size - 1) >>
951 sec_shift;
952
953 NTFS_PVT(inode)->data.non_resident.rlist = rlist;
954
955 free(ret);
956 ret = NULL;
957 }
958 }
959
960 inode->next_extent.pstart = pstart;
961
962 return 0;
963
964 out:
965 return -1;
966 }
967
968 static uint32_t ntfs_getfssec(struct file *file, char *buf, int sectors,
969 bool *have_more)
970 {
971 uint8_t non_resident;
972 uint32_t ret;
973 struct fs_info *fs = file->fs;
974 struct inode *inode = file->inode;
975 struct ntfs_mft_record *mrec, *lmrec;
976 struct ntfs_attr_record *attr;
977 char *p;
978
979 dprintf("in %s()\n", __func__);
980
981 non_resident = NTFS_PVT(inode)->non_resident;
982
983 ret = generic_getfssec(file, buf, sectors, have_more);
984 if (!ret)
985 return ret;
986
987 if (!non_resident) {
988 mrec = NTFS_SB(fs)->mft_record_lookup(fs, NTFS_PVT(inode)->mft_no,
989 NULL);
990 if (!mrec) {
991 printf("No MFT record found.\n");
992 goto out;
993 }
994
995 lmrec = mrec;
996 attr = ntfs_attr_lookup(fs, NTFS_AT_DATA, &mrec, lmrec);
997 if (!attr) {
998 printf("No attribute found.\n");
999 goto out;
1000 }
1001
1002 p = (char *)((uint8_t *)attr + attr->data.resident.value_offset);
1003
1004 /* p now points to the data offset, so let's copy it into buf */
1005 memcpy(buf, p, inode->size);
1006
1007 ret = inode->size;
1008
1009 free(mrec);
1010 }
1011
1012 return ret;
1013
1014 out:
1015 free(mrec);
1016
1017 return 0;
1018 }
1019
1020 static inline bool is_filename_printable(const char *s)
1021 {
1022 return s && (*s != '.' && *s != '$');
1023 }
1024
1025 static int ntfs_readdir(struct file *file, struct dirent *dirent)
1026 {
1027 struct fs_info *fs = file->fs;
1028 struct inode *inode = file->inode;
1029 struct ntfs_mft_record *mrec, *lmrec;
1030 block_t blk;
1031 uint64_t blk_offset;
1032 const uint64_t blk_size = UINT64_C(1) << BLOCK_SHIFT(fs);
1033 struct ntfs_attr_record *attr;
1034 struct ntfs_idx_root *ir;
1035 uint32_t count;
1036 int len;
1037 struct ntfs_idx_entry *ie = NULL;
1038 uint8_t buf[BLOCK_SIZE(fs)];
1039 struct ntfs_idx_allocation *iblk;
1040 int err;
1041 uint8_t *stream;
1042 uint8_t *attr_len;
1043 struct mapping_chunk chunk;
1044 uint32_t offset;
1045 int64_t vcn;
1046 int64_t lcn;
1047 char filename[NTFS_MAX_FILE_NAME_LEN + 1];
1048
1049 dprintf("in %s()\n", __func__);
1050
1051 mrec = NTFS_SB(fs)->mft_record_lookup(fs, NTFS_PVT(inode)->mft_no, NULL);
1052 if (!mrec) {
1053 printf("No MFT record found.\n");
1054 goto out;
1055 }
1056
1057 lmrec = mrec;
1058 attr = ntfs_attr_lookup(fs, NTFS_AT_INDEX_ROOT, &mrec, lmrec);
1059 if (!attr) {
1060 printf("No attribute found.\n");
1061 goto out;
1062 }
1063
1064 ir = (struct ntfs_idx_root *)((uint8_t *)attr +
1065 attr->data.resident.value_offset);
1066
1067 if (!file->offset && readdir_state->in_idx_root) {
1068 file->offset = (uint32_t)((uint8_t *)&ir->index +
1069 ir->index.entries_offset);
1070 }
1071
1072 idx_root_next_entry:
1073 if (readdir_state->in_idx_root) {
1074 ie = (struct ntfs_idx_entry *)(uint8_t *)file->offset;
1075 if (ie->flags & INDEX_ENTRY_END) {
1076 file->offset = 0;
1077 readdir_state->in_idx_root = false;
1078 readdir_state->idx_blks_count = 1;
1079 readdir_state->entries_count = 0;
1080 readdir_state->last_vcn = 0;
1081 goto descend_into_child_node;
1082 }
1083
1084 file->offset = (uint32_t)((uint8_t *)ie + ie->len);
1085 len = ntfs_cvt_filename(filename, ie);
1086 if (!is_filename_printable(filename))
1087 goto idx_root_next_entry;
1088
1089 goto done;
1090 }
1091
1092 descend_into_child_node:
1093 if (!(ie->flags & INDEX_ENTRY_NODE))
1094 goto out;
1095
1096 attr = ntfs_attr_lookup(fs, NTFS_AT_INDEX_ALLOCATION, &mrec, lmrec);
1097 if (!attr)
1098 goto out;
1099
1100 if (!attr->non_resident) {
1101 printf("WTF ?! $INDEX_ALLOCATION isn't really resident.\n");
1102 goto out;
1103 }
1104
1105 attr_len = (uint8_t *)attr + attr->len;
1106
1107 next_run:
1108 stream = mapping_chunk_init(attr, &chunk, &offset);
1109 count = readdir_state->idx_blks_count;
1110 while (count--) {
1111 err = parse_data_run(stream, &offset, attr_len, &chunk);
1112 if (err) {
1113 printf("Error while parsing data runs.\n");
1114 goto out;
1115 }
1116
1117 if (chunk.flags & MAP_UNALLOCATED)
1118 break;
1119 if (chunk.flags & MAP_END)
1120 goto out;
1121 }
1122
1123 if (chunk.flags & MAP_UNALLOCATED) {
1124 readdir_state->idx_blks_count++;
1125 goto next_run;
1126 }
1127
1128 next_vcn:
1129 vcn = readdir_state->last_vcn;
1130 if (vcn >= chunk.len) {
1131 readdir_state->last_vcn = 0;
1132 readdir_state->idx_blks_count++;
1133 goto next_run;
1134 }
1135
1136 lcn = chunk.lcn;
1137 blk = (lcn + vcn) << NTFS_SB(fs)->clust_shift << SECTOR_SHIFT(fs) >>
1138 BLOCK_SHIFT(fs);
1139
1140 blk_offset = 0;
1141 err = ntfs_read(fs, &buf, blk_size, blk_size, &blk, &blk_offset, NULL,
1142 (uint64_t *)&lcn);
1143 if (err) {
1144 printf("Error while reading from cache.\n");
1145 goto not_found;
1146 }
1147
1148 ntfs_fixups_writeback(fs, (struct ntfs_record *)&buf);
1149
1150 iblk = (struct ntfs_idx_allocation *)&buf;
1151 if (iblk->magic != NTFS_MAGIC_INDX) {
1152 printf("Not a valid INDX record.\n");
1153 goto not_found;
1154 }
1155
1156 idx_block_next_entry:
1157 ie = (struct ntfs_idx_entry *)((uint8_t *)&iblk->index +
1158 iblk->index.entries_offset);
1159 count = readdir_state->entries_count;
1160 for ( ; count--; ie = (struct ntfs_idx_entry *)((uint8_t *)ie + ie->len)) {
1161 /* bounds checks */
1162 if ((uint8_t *)ie < (uint8_t *)iblk || (uint8_t *)ie +
1163 sizeof(struct ntfs_idx_entry_header) >
1164 (uint8_t *)&iblk->index + iblk->index.index_len ||
1165 (uint8_t *)ie + ie->len >
1166 (uint8_t *)&iblk->index + iblk->index.index_len)
1167 goto index_err;
1168
1169 /* last entry cannot contain a key */
1170 if (ie->flags & INDEX_ENTRY_END) {
1171 /* go to the next VCN */
1172 readdir_state->last_vcn += (blk_size / (1 <<
1173 NTFS_SB(fs)->clust_byte_shift));
1174 readdir_state->entries_count = 0;
1175 goto next_vcn;
1176 }
1177 }
1178
1179 readdir_state->entries_count++;
1180
1181 /* Need to check if this entry has INDEX_ENTRY_END flag set. If
1182 * so, then it won't contain a indexed_file file, so continue the
1183 * lookup on the next VCN/LCN (if any).
1184 */
1185 if (ie->flags & INDEX_ENTRY_END)
1186 goto next_vcn;
1187
1188 len = ntfs_cvt_filename(filename, ie);
1189 if (!is_filename_printable(filename))
1190 goto idx_block_next_entry;
1191
1192 goto done;
1193
1194 out:
1195 readdir_state->in_idx_root = true;
1196
1197 free(mrec);
1198
1199 return -1;
1200
1201 done:
1202 dirent->d_ino = ie->data.dir.indexed_file;
1203 dirent->d_off = file->offset;
1204 dirent->d_reclen = offsetof(struct dirent, d_name) + len + 1;
1205
1206 free(mrec);
1207
1208 mrec = NTFS_SB(fs)->mft_record_lookup(fs, ie->data.dir.indexed_file, NULL);
1209 if (!mrec) {
1210 printf("No MFT record found.\n");
1211 goto out;
1212 }
1213
1214 dirent->d_type = get_inode_mode(mrec);
1215 memcpy(dirent->d_name, filename, len + 1);
1216
1217 free(mrec);
1218
1219 return 0;
1220
1221 not_found:
1222 printf("Index not found\n");
1223 goto out;
1224
1225 index_err:
1226 printf("Corrupt index. Aborting lookup...\n");
1227 goto out;
1228 }
1229
1230 static inline struct inode *ntfs_iget(const char *dname, struct inode *parent)
1231 {
1232 return ntfs_index_lookup(dname, parent);
1233 }
1234
1235 static struct inode *ntfs_iget_root(struct fs_info *fs)
1236 {
1237 uint64_t start_blk;
1238 struct ntfs_mft_record *mrec, *lmrec;
1239 struct ntfs_attr_record *attr;
1240 struct ntfs_vol_info *vol_info;
1241 struct inode *inode;
1242 int err;
1243
1244 dprintf("in %s()\n", __func__);
1245
1246 /* Fetch the $Volume MFT record */
1247 start_blk = 0;
1248 mrec = NTFS_SB(fs)->mft_record_lookup(fs, FILE_Volume, &start_blk);
1249 if (!mrec) {
1250 printf("Could not fetch $Volume MFT record!\n");
1251 goto err_mrec;
1252 }
1253
1254 lmrec = mrec;
1255
1256 /* Fetch the volume information attribute */
1257 attr = ntfs_attr_lookup(fs, NTFS_AT_VOL_INFO, &mrec, lmrec);
1258 if (!attr) {
1259 printf("Could not find volume info attribute!\n");
1260 goto err_attr;
1261 }
1262
1263 /* Note NTFS version and choose version-dependent functions */
1264 vol_info = (void *)((char *)attr + attr->data.resident.value_offset);
1265 NTFS_SB(fs)->major_ver = vol_info->major_ver;
1266 NTFS_SB(fs)->minor_ver = vol_info->minor_ver;
1267 if (vol_info->major_ver == 3 && vol_info->minor_ver == 0)
1268 NTFS_SB(fs)->mft_record_lookup = ntfs_mft_record_lookup_3_0;
1269 else if (vol_info->major_ver == 3 && vol_info->minor_ver == 1 &&
1270 mrec->mft_record_no == FILE_Volume)
1271 NTFS_SB(fs)->mft_record_lookup = ntfs_mft_record_lookup_3_1;
1272
1273 /* Free MFT record */
1274 free(mrec);
1275 mrec = NULL;
1276
1277 inode = new_ntfs_inode(fs);
1278 inode->fs = fs;
1279
1280 err = index_inode_setup(fs, FILE_root, inode);
1281 if (err)
1282 goto err_setup;
1283
1284 NTFS_PVT(inode)->start = NTFS_PVT(inode)->here;
1285
1286 return inode;
1287
1288 err_setup:
1289
1290 free(inode);
1291 err_attr:
1292
1293 free(mrec);
1294 err_mrec:
1295
1296 return NULL;
1297 }
1298
1299 /* Initialize the filesystem metadata and return blk size in bits */
1300 static int ntfs_fs_init(struct fs_info *fs)
1301 {
1302 int read_count;
1303 struct ntfs_bpb ntfs;
1304 struct ntfs_sb_info *sbi;
1305 struct disk *disk = fs->fs_dev->disk;
1306 uint8_t mft_record_shift;
1307
1308 dprintf("in %s()\n", __func__);
1309
1310 read_count = disk->rdwr_sectors(disk, &ntfs, 0, 1, 0);
1311 if (!read_count)
1312 return -1;
1313
1314 if (!ntfs_check_sb_fields(&ntfs))
1315 return -1;
1316
1317 SECTOR_SHIFT(fs) = disk->sector_shift;
1318
1319 /* Note: ntfs.clust_per_mft_record can be a negative number.
1320 * If negative, it represents a shift count, else it represents
1321 * a multiplier for the cluster size.
1322 */
1323 mft_record_shift = ntfs.clust_per_mft_record < 0 ?
1324 -ntfs.clust_per_mft_record :
1325 ilog2(ntfs.sec_per_clust) + SECTOR_SHIFT(fs) +
1326 ilog2(ntfs.clust_per_mft_record);
1327
1328 SECTOR_SIZE(fs) = 1 << SECTOR_SHIFT(fs);
1329
1330 sbi = malloc(sizeof *sbi);
1331 if (!sbi)
1332 malloc_error("ntfs_sb_info structure");
1333
1334 fs->fs_info = sbi;
1335
1336 sbi->clust_shift = ilog2(ntfs.sec_per_clust);
1337 sbi->clust_byte_shift = sbi->clust_shift + SECTOR_SHIFT(fs);
1338 sbi->clust_mask = ntfs.sec_per_clust - 1;
1339 sbi->clust_size = ntfs.sec_per_clust << SECTOR_SHIFT(fs);
1340 sbi->mft_record_size = 1 << mft_record_shift;
1341 sbi->clust_per_idx_record = ntfs.clust_per_idx_record;
1342
1343 BLOCK_SHIFT(fs) = ilog2(ntfs.clust_per_idx_record) + sbi->clust_byte_shift;
1344 BLOCK_SIZE(fs) = 1 << BLOCK_SHIFT(fs);
1345
1346 sbi->mft_lcn = ntfs.mft_lclust;
1347 sbi->mft_blk = ntfs.mft_lclust << sbi->clust_shift << SECTOR_SHIFT(fs) >>
1348 BLOCK_SHIFT(fs);
1349 /* 16 MFT entries reserved for metadata files (approximately 16 KiB) */
1350 sbi->mft_size = mft_record_shift << sbi->clust_shift << 4;
1351
1352 sbi->clusters = ntfs.total_sectors << SECTOR_SHIFT(fs) >> sbi->clust_shift;
1353 if (sbi->clusters > 0xFFFFFFFFFFF4ULL)
1354 sbi->clusters = 0xFFFFFFFFFFF4ULL;
1355
1356 /*
1357 * Assume NTFS version 3.0 to begin with. If we find that the
1358 * volume is a different version later on, we will adjust at
1359 * that time.
1360 */
1361 sbi->major_ver = 3;
1362 sbi->minor_ver = 0;
1363 sbi->mft_record_lookup = ntfs_mft_record_lookup_3_0;
1364
1365 /* Initialize the cache */
1366 cache_init(fs->fs_dev, BLOCK_SHIFT(fs));
1367
1368 return BLOCK_SHIFT(fs);
1369 }
1370
1371 const struct fs_ops ntfs_fs_ops = {
1372 .fs_name = "ntfs",
1373 .fs_flags = FS_USEMEM | FS_THISIND,
1374 .fs_init = ntfs_fs_init,
1375 .searchdir = NULL,
1376 .getfssec = ntfs_getfssec,
1377 .close_file = generic_close_file,
1378 .mangle_name = generic_mangle_name,
1379 .open_config = generic_open_config,
1380 .readdir = ntfs_readdir,
1381 .iget_root = ntfs_iget_root,
1382 .iget = ntfs_iget,
1383 .next_extent = ntfs_next_extent,
1384 .fs_uuid = NULL,
1385 };