ntfs_reader/
mft.rs

1// Copyright (c) 2022, Matteo Bernacchia <dev@kikijiki.com>. All rights reserved.
2// This project is dual licensed under the Apache License 2.0 and the MIT license.
3// See the LICENSE files in the project root for details.
4
5use std::io::{Read, Seek, SeekFrom};
6use std::mem::size_of;
7
8use crate::{
9    aligned_reader::open_volume,
10    api::*,
11    attribute::{DataRun, NtfsAttribute},
12    errors::{NtfsReaderError, NtfsReaderResult},
13    file::NtfsFile,
14    volume::Volume,
15};
16
17pub struct Mft {
18    pub volume: Volume,
19    pub data: Vec<u8>,
20    pub bitmap: Vec<u8>,
21    pub max_record: u64,
22    extension_records: Vec<(u64, u64)>,
23}
24
25impl Mft {
26    pub fn new(volume: Volume) -> NtfsReaderResult<Self> {
27        let mut reader = open_volume(&volume.path)?;
28
29        let mft_record =
30            Self::get_record_fs(&mut reader, volume.file_record_size, volume.mft_position)?;
31
32        let mut data =
33            Self::read_data_fs(&volume, &mut reader, &mft_record, NtfsAttributeType::Data)?
34                .ok_or_else(|| NtfsReaderError::MissingMftAttribute("Data".to_string()))?;
35        let bitmap =
36            Self::read_data_fs(&volume, &mut reader, &mft_record, NtfsAttributeType::Bitmap)?
37                .ok_or_else(|| NtfsReaderError::MissingMftAttribute("Bitmap".to_string()))?;
38
39        let max_record = data.len() as u64 / volume.file_record_size;
40
41        // Fixup all records so we are non mutable from now on.
42        for number in 0..max_record {
43            let start = number * volume.file_record_size;
44            let end = start + volume.file_record_size;
45            let (start, end) = (start as usize, end as usize);
46            let data = &mut data[start..end];
47            Self::fixup_record(number, data)?;
48        }
49
50        let mut mft = Mft {
51            volume,
52            data,
53            bitmap,
54            max_record,
55            extension_records: Vec::new(),
56        };
57        mft.index_extension_records();
58        Ok(mft)
59    }
60
61    pub fn record_exists(&self, number: u64) -> bool {
62        if number >= self.max_record {
63            return false;
64        }
65
66        let bitmap_idx = number / 8;
67        let bitmap_off = (number % 8) as u8;
68
69        if bitmap_idx >= self.bitmap.len() as u64 {
70            return false;
71        }
72
73        let bit = self.bitmap[bitmap_idx as usize];
74        (bit & (1u8 << bitmap_off)) != 0
75    }
76
77    pub fn files(&self) -> impl Iterator<Item = NtfsFile<'_>> {
78        (FIRST_NORMAL_RECORD..self.max_record)
79            .filter(|&n| self.record_exists(n))
80            .filter_map(|n| self.get_record(n))
81            .filter(|f| f.is_used() && !f.is_extension())
82    }
83
84    /// Returns the base MFT record and all live extension records that belong
85    /// to the same logical file.
86    pub fn file_records<'a>(
87        &'a self,
88        file: &NtfsFile<'_>,
89    ) -> impl Iterator<Item = NtfsFile<'a>> + 'a {
90        let base_number = file.base_record_number().unwrap_or(file.number());
91        let base_reference = self
92            .get_record(base_number)
93            .map(|base| base.reference_number());
94        let start = self
95            .extension_records
96            .partition_point(|(base, _)| *base < base_number);
97        let end = self
98            .extension_records
99            .partition_point(|(base, _)| *base <= base_number);
100
101        std::iter::once(base_number)
102            .chain(
103                self.extension_records[start..end]
104                    .iter()
105                    .map(|(_, extension)| *extension),
106            )
107            .filter(move |number| self.record_exists(*number))
108            .filter_map(move |number| self.get_record(number))
109            .filter(move |record| {
110                record.is_used()
111                    && (record.number() == base_number
112                        || record.base_reference_number() == base_reference)
113            })
114    }
115
116    #[deprecated(since = "0.4.5", note = "use `files()` iterator instead")]
117    pub fn iterate_files<F>(&self, mut f: F)
118    where
119        F: FnMut(&NtfsFile),
120    {
121        for file in self.files() {
122            f(&file);
123        }
124    }
125
126    fn get_record_data(&self, number: u64) -> &[u8] {
127        let start = number * self.volume.file_record_size;
128        let end = start + self.volume.file_record_size;
129        &self.data[start as usize..end as usize]
130    }
131
132    pub fn get_record(&self, number: u64) -> Option<NtfsFile<'_>> {
133        if number >= self.max_record {
134            return None;
135        }
136        let data = self.get_record_data(number);
137
138        if NtfsFile::is_valid(data) {
139            return Some(NtfsFile::new(number, data));
140        }
141
142        None
143    }
144
145    fn index_extension_records(&mut self) {
146        self.extension_records = (0..self.max_record)
147            .filter(|&number| self.record_exists(number))
148            .filter_map(|number| {
149                let record = self.get_record(number)?;
150                if !record.is_used() {
151                    return None;
152                }
153                record
154                    .base_record_number()
155                    .map(|base| (base, record.number()))
156            })
157            .collect();
158        self.extension_records.sort_unstable();
159    }
160
161    pub fn get_record_fs<R>(
162        fs: &mut R,
163        file_record_size: u64,
164        position: u64,
165    ) -> NtfsReaderResult<Vec<u8>>
166    where
167        R: Seek + Read,
168    {
169        let mut data = vec![0; file_record_size as usize];
170        fs.seek(SeekFrom::Start(position))?;
171        fs.read_exact(&mut data)?;
172
173        if !NtfsFile::is_valid(&data) {
174            return Err(NtfsReaderError::InvalidMftRecord { position });
175        }
176        Self::fixup_record(0, &mut data)?;
177        Ok(data)
178    }
179
180    pub fn read_data_fs<R>(
181        volume: &Volume,
182        reader: &mut R,
183        record: &[u8],
184        attribute_type: NtfsAttributeType,
185    ) -> NtfsReaderResult<Option<Vec<u8>>>
186    where
187        R: Seek + Read,
188    {
189        let header = unsafe { &*(record.as_ptr() as *const NtfsFileRecordHeader) };
190        let mut att_offset = header.attributes_offset as usize;
191        let used = usize::min(header.used_size as usize, record.len());
192
193        // First pass: look for the attribute directly in this record
194        while att_offset < used {
195            let slice = &record[att_offset..used];
196            let attr = match NtfsAttribute::new(slice) {
197                Some(attr) => attr,
198                None => break,
199            };
200
201            if attr.header.type_id == NtfsAttributeType::End as u32 {
202                break;
203            }
204
205            if attr.header.type_id == attribute_type as u32 {
206                return Ok(Some(Self::read_attribute_data(reader, &attr, volume)?));
207            }
208
209            let attr_len = attr.len();
210            if attr_len == 0 {
211                break;
212            }
213            att_offset = match att_offset.checked_add(attr_len) {
214                Some(next) if next <= used => next,
215                _ => break,
216            };
217        }
218
219        // Second pass: if not found, check attribute list entries
220        att_offset = header.attributes_offset as usize;
221        while att_offset < used {
222            let slice = &record[att_offset..used];
223            let attr = match NtfsAttribute::new(slice) {
224                Some(attr) => attr,
225                None => break,
226            };
227
228            if attr.header.type_id == NtfsAttributeType::End as u32 {
229                break;
230            }
231
232            if attr.header.type_id == NtfsAttributeType::AttributeList as u32 {
233                let att_list_data = if attr.header.is_non_resident != 0 {
234                    Self::read_attribute_data(reader, &attr, volume)?
235                } else {
236                    match attr.as_resident_data() {
237                        Some(data) => data.to_vec(),
238                        None => break,
239                    }
240                };
241
242                let mut list_offset = 0usize;
243
244                while list_offset < att_list_data.len() {
245                    let entry_slice = &att_list_data[list_offset..];
246                    let entry = match parse_attribute_list_entry(entry_slice) {
247                        Some(entry) => entry,
248                        None => break,
249                    };
250
251                    let type_id = entry.type_id;
252                    let reference = entry.reference();
253                    let entry_len = entry.length as usize;
254
255                    if type_id == attribute_type as u32 {
256                        let record_position =
257                            volume.mft_position + (reference * volume.file_record_size);
258                        if let Ok(target_record) =
259                            Self::get_record_fs(reader, volume.file_record_size, record_position)
260                        {
261                            let target_header = unsafe {
262                                &*(target_record.as_ptr() as *const NtfsFileRecordHeader)
263                            };
264                            let mut target_offset = target_header.attributes_offset as usize;
265                            let target_used =
266                                usize::min(target_header.used_size as usize, target_record.len());
267
268                            while target_offset < target_used {
269                                let target_slice = &target_record[target_offset..target_used];
270                                let target_attr = match NtfsAttribute::new(target_slice) {
271                                    Some(attr) => attr,
272                                    None => break,
273                                };
274
275                                if target_attr.header.type_id == NtfsAttributeType::End as u32 {
276                                    break;
277                                }
278
279                                if target_attr.header.type_id == attribute_type as u32 {
280                                    return Ok(Some(Self::read_attribute_data(
281                                        reader,
282                                        &target_attr,
283                                        volume,
284                                    )?));
285                                }
286
287                                let len = target_attr.len();
288                                if len == 0 {
289                                    break;
290                                }
291                                target_offset = match target_offset.checked_add(len) {
292                                    Some(next) if next <= target_used => next,
293                                    _ => break,
294                                };
295                            }
296                        }
297                    }
298
299                    if entry_len == 0 {
300                        break;
301                    }
302                    list_offset = match list_offset.checked_add(entry_len) {
303                        Some(next) if next <= att_list_data.len() => next,
304                        _ => break,
305                    };
306                    let align = (8 - (list_offset % 8)) % 8;
307                    list_offset = match list_offset.checked_add(align) {
308                        Some(next) if next <= att_list_data.len() => next,
309                        _ => break,
310                    };
311                }
312            }
313
314            let attr_len = attr.len();
315            if attr_len == 0 {
316                break;
317            }
318            att_offset = match att_offset.checked_add(attr_len) {
319                Some(next) if next <= used => next,
320                _ => break,
321            };
322        }
323
324        Ok(None)
325    }
326
327    fn read_attribute_data<R>(
328        reader: &mut R,
329        att: &NtfsAttribute,
330        volume: &Volume,
331    ) -> NtfsReaderResult<Vec<u8>>
332    where
333        R: Seek + Read,
334    {
335        if att.header.is_non_resident == 0 {
336            let data = att
337                .as_resident_data()
338                .ok_or(NtfsReaderError::InvalidDataRun {
339                    details: "resident attribute missing value",
340                })?;
341            Ok(data.to_vec())
342        } else {
343            let (size, runs) = att.get_nonresident_data_runs(volume)?;
344            let total_size =
345                usize::try_from(size).map_err(|_| NtfsReaderError::AllocationTooLarge { size })?;
346
347            let mut data = Vec::new();
348            data.try_reserve(total_size)
349                .map_err(|_| NtfsReaderError::AllocationTooLarge { size })?;
350            let mut copied = 0u64;
351
352            for run in runs.iter() {
353                if copied >= size {
354                    break;
355                }
356
357                let buf_size = match run {
358                    DataRun::Data { lcn, length } => {
359                        let buf_size = u64::min(*length, size - copied);
360                        let start = data.len();
361                        data.resize(start + buf_size as usize, 0u8);
362
363                        reader.seek(SeekFrom::Start(*lcn))?;
364                        reader.read_exact(&mut data[start..])?;
365                        buf_size
366                    }
367                    DataRun::Sparse { length } => {
368                        let buf_size = u64::min(*length, size - copied);
369                        data.resize(data.len() + buf_size as usize, 0);
370                        buf_size
371                    }
372                };
373                copied += buf_size;
374            }
375
376            Ok(data)
377        }
378    }
379
380    fn fixup_record(record_number: u64, data: &mut [u8]) -> NtfsReaderResult<()> {
381        if data.len() < core::mem::size_of::<NtfsFileRecordHeader>() {
382            return Err(NtfsReaderError::CorruptMftRecord {
383                number: record_number,
384            });
385        }
386        let header =
387            unsafe { core::ptr::read_unaligned(data.as_ptr() as *const NtfsFileRecordHeader) };
388
389        let usn_start = header.update_sequence_offset as usize;
390        if usn_start + 2 > data.len() {
391            return Err(NtfsReaderError::CorruptMftRecord {
392                number: record_number,
393            });
394        }
395        let usa_start = usn_start + 2;
396        let usa_end =
397            usn_start.saturating_add((header.update_sequence_length as usize).saturating_mul(2));
398        if usa_end > data.len() {
399            return Err(NtfsReaderError::CorruptMftRecord {
400                number: record_number,
401            });
402        }
403
404        let usn0 = data[usn_start];
405        let usn1 = data[usn_start + 1];
406
407        let mut sector_off = SECTOR_SIZE - 2;
408        for usa_off in (usa_start..usa_end).step_by(2) {
409            if sector_off + 2 > data.len() {
410                break;
411            }
412
413            let mut usa = [0u8; 2];
414            usa.copy_from_slice(&data[usa_off..usa_off + 2]);
415
416            let d0 = data[sector_off];
417            let d1 = data[sector_off + 1];
418            if d0 != usn0 || d1 != usn1 {
419                return Err(NtfsReaderError::CorruptMftRecord {
420                    number: record_number,
421                });
422            }
423
424            data[sector_off..sector_off + 2].copy_from_slice(&usa);
425            sector_off += SECTOR_SIZE;
426        }
427        Ok(())
428    }
429}
430
431fn parse_attribute_list_entry(data: &[u8]) -> Option<&NtfsAttributeListEntry> {
432    if data.len() < size_of::<NtfsAttributeListEntry>() {
433        return None;
434    }
435    let entry = unsafe { &*(data.as_ptr() as *const NtfsAttributeListEntry) };
436    let length = entry.length as usize;
437    if length < size_of::<NtfsAttributeListEntry>() || length > data.len() {
438        return None;
439    }
440    Some(entry)
441}
442
443#[cfg(test)]
444mod tests {
445    use std::path::PathBuf;
446
447    use super::*;
448    use crate::file_info::FileInfo;
449
450    const RECORD_SIZE: usize = 1024;
451    const ATTRIBUTES_OFFSET: usize = 48;
452
453    #[test]
454    fn combines_base_and_extension_records_into_one_file() {
455        let attributes = NtfsFileNameFlags::Hidden as u32
456            | NtfsFileNameFlags::System as u32
457            | NtfsFileNameFlags::Archive as u32
458            | NtfsFileNameFlags::SparseFile as u32;
459        let file_size = 34_359_738_368u64;
460
461        let mut base = new_record(24, 7, 0);
462        let mut offset = ATTRIBUTES_OFFSET;
463        offset = add_standard_information(&mut base, offset, attributes);
464        offset = add_nonresident_data(&mut base, offset, file_size);
465        finish_record(&mut base, offset);
466
467        let base_reference = (7u64 << 48) | 24;
468        let mut extension = new_record(25, 3, base_reference);
469        let offset = add_file_name(
470            &mut extension,
471            ATTRIBUTES_OFFSET,
472            "large-fragmented.rar",
473            attributes,
474        );
475        finish_record(&mut extension, offset);
476
477        let mut data = vec![0u8; 26 * RECORD_SIZE];
478        data[24 * RECORD_SIZE..25 * RECORD_SIZE].copy_from_slice(&base);
479        data[25 * RECORD_SIZE..26 * RECORD_SIZE].copy_from_slice(&extension);
480
481        let boot_sector = unsafe { std::mem::zeroed() };
482        let volume = Volume {
483            path: PathBuf::from(r"\\.\T:"),
484            boot_sector,
485            cluster_size: 4096,
486            volume_size: 0,
487            file_record_size: RECORD_SIZE as u64,
488            mft_position: 0,
489        };
490        let mut mft = Mft {
491            volume,
492            data,
493            bitmap: vec![0, 0, 0, 0b0000_0011],
494            max_record: 26,
495            extension_records: Vec::new(),
496        };
497        mft.index_extension_records();
498
499        let files: Vec<_> = mft.files().collect();
500        assert_eq!(files.len(), 1, "extension record must not be a second file");
501        assert_eq!(files[0].number(), 24);
502        assert_eq!(mft.file_records(&files[0]).count(), 2);
503
504        let info = FileInfo::new(&mft, &files[0]);
505        assert_eq!(info.name, "large-fragmented.rar");
506        assert_eq!(info.size, file_size);
507        assert_eq!(info.file_attributes, attributes);
508    }
509
510    fn new_record(number: u64, sequence: u16, base_reference: u64) -> Vec<u8> {
511        let mut record = vec![0u8; RECORD_SIZE];
512        record[0..4].copy_from_slice(FILE_RECORD_SIGNATURE);
513        write_u16(&mut record, 4, 42);
514        write_u16(&mut record, 6, 1);
515        write_u16(&mut record, 16, sequence);
516        write_u16(&mut record, 18, 1);
517        write_u16(&mut record, 20, ATTRIBUTES_OFFSET as u16);
518        write_u16(&mut record, 22, NtfsFileFlags::InUse as u16);
519        write_u32(&mut record, 28, RECORD_SIZE as u32);
520        write_u64(&mut record, 32, base_reference);
521        write_u16(&mut record, 40, number as u16);
522        record
523    }
524
525    fn add_standard_information(record: &mut [u8], offset: usize, attributes: u32) -> usize {
526        let mut value = vec![0u8; size_of::<NtfsStandardInformation>()];
527        write_u64(&mut value, 0, EPOCH_DIFFERENCE + 10_000_000);
528        write_u64(&mut value, 8, EPOCH_DIFFERENCE + 20_000_000);
529        write_u64(&mut value, 24, EPOCH_DIFFERENCE + 30_000_000);
530        write_u32(&mut value, 32, attributes);
531        add_resident_attribute(
532            record,
533            offset,
534            NtfsAttributeType::StandardInformation,
535            0,
536            &value,
537        )
538    }
539
540    fn add_file_name(record: &mut [u8], offset: usize, name: &str, attributes: u32) -> usize {
541        let encoded: Vec<u16> = name.encode_utf16().collect();
542        let mut value = vec![0u8; size_of::<NtfsFileNameHeader>() + encoded.len() * 2];
543        write_u64(&mut value, 0, ROOT_RECORD);
544        write_u64(&mut value, 40, 34_359_738_368);
545        write_u64(&mut value, 48, 34_359_738_368);
546        write_u32(&mut value, 56, attributes);
547        value[64] = encoded.len() as u8;
548        value[65] = NtfsFileNamespace::Win32 as u8;
549        for (index, character) in encoded.into_iter().enumerate() {
550            write_u16(
551                &mut value,
552                size_of::<NtfsFileNameHeader>() + index * 2,
553                character,
554            );
555        }
556        add_resident_attribute(record, offset, NtfsAttributeType::FileName, 1, &value)
557    }
558
559    fn add_resident_attribute(
560        record: &mut [u8],
561        offset: usize,
562        attribute_type: NtfsAttributeType,
563        id: u16,
564        value: &[u8],
565    ) -> usize {
566        const VALUE_OFFSET: usize = 24;
567        let length = align_to_eight(VALUE_OFFSET + value.len());
568        write_u32(record, offset, attribute_type as u32);
569        write_u32(record, offset + 4, length as u32);
570        write_u16(record, offset + 14, id);
571        write_u32(record, offset + 16, value.len() as u32);
572        write_u16(record, offset + 20, VALUE_OFFSET as u16);
573        record[offset + VALUE_OFFSET..offset + VALUE_OFFSET + value.len()].copy_from_slice(value);
574        offset + length
575    }
576
577    fn add_nonresident_data(record: &mut [u8], offset: usize, size: u64) -> usize {
578        let length = size_of::<NtfsNonResidentAttributeHeader>();
579        write_u32(record, offset, NtfsAttributeType::Data as u32);
580        write_u32(record, offset + 4, length as u32);
581        record[offset + 8] = 1;
582        write_u16(record, offset + 14, 2);
583        write_u64(record, offset + 16, 0);
584        write_u64(record, offset + 40, size);
585        write_u64(record, offset + 48, size);
586        write_u64(record, offset + 56, size);
587        offset + length
588    }
589
590    fn finish_record(record: &mut [u8], used_size: usize) {
591        write_u32(record, 24, used_size as u32);
592    }
593
594    fn align_to_eight(value: usize) -> usize {
595        (value + 7) & !7
596    }
597
598    fn write_u16(data: &mut [u8], offset: usize, value: u16) {
599        data[offset..offset + 2].copy_from_slice(&value.to_le_bytes());
600    }
601
602    fn write_u32(data: &mut [u8], offset: usize, value: u32) {
603        data[offset..offset + 4].copy_from_slice(&value.to_le_bytes());
604    }
605
606    fn write_u64(data: &mut [u8], offset: usize, value: u64) {
607        data[offset..offset + 8].copy_from_slice(&value.to_le_bytes());
608    }
609}
ntfs_reader/mft.rs

ntfs_reader/
mft.rs
