fmf_core\index/
mod.rs

1//! In-memory per-volume index: struct-of-arrays, two string pools with shared
2//! offsets, FRN map, and pre-sorted permutations for instant sorting
3//! (docs/ARCHITECTURE.md).
4//!
5//! Mutation model (keeps the permutation arrays merge-only):
6//! - create  → append entry + merge into permutations
7//! - delete  → tombstone flag only
8//! - rename  → files: tombstone old + append new entry (same FRN);
9//!   dirs: in-place (children point at the `EntryId`), repositioned in `perm_name`
10//! - move    → rewrite `parent` only (no permutation depends on the path)
11//!
12//! Tombstones accumulate until compaction (M2), which bumps
13//! `structural_generation` and invalidates open result handles. Ordinary
14//! batches bump `content_generation` only; open results stay readable.
15
16mod builder;
17mod compact;
18mod core;
19mod frn;
20mod mutate;
21mod snapshot;
22#[cfg(any(test, feature = "testutil"))]
23pub mod testutil;
24
25pub use self::builder::{FinishTimings, VolumeIndexBuilder};
26pub use self::core::VolumeIndex;
27
28/// Dense, append-only index into the struct-of-arrays entry columns.
29pub type EntryId = u32;
30/// Sentinel `parent` value for an entry attached to the volume root (no parent).
31pub const NO_PARENT: EntryId = u32::MAX;
32
33/// Per-entry flag bits packed into the index's `flags` column (one `u8`).
34pub mod flags {
35    /// This entry is a directory.
36    pub const IS_DIR: u8 = 1;
37    /// This entry is deleted but not yet compacted away.
38    pub const TOMBSTONE: u8 = 2;
39    /// This entry is a reparse point (symlink, junction, mount point).
40    pub const REPARSE: u8 = 4;
41    /// Raw `FILE_ATTRIBUTE_HIDDEN`.
42    pub const HIDDEN: u8 = 8;
43    /// Raw `FILE_ATTRIBUTE_SYSTEM`.
44    pub const SYSTEM: u8 = 16;
45    /// Computed: this entry or any ancestor carries HIDDEN|SYSTEM.
46    ///
47    /// Queries skip these by default (toggleable). Kept in sync on
48    /// insert/move; a subtree moved out of an excluded branch keeps stale
49    /// bits until the next full rescan (same accepted-limitation class as dir
50    /// renames).
51    pub const EXCLUDED: u8 = 32;
52}
53
54/// A full 64-bit NTFS file reference number: `(sequence << 48) | record`.
55///
56/// The identity that survives a rename (the FRN is kept); NTFS reuses the
57/// low-48-bit record number, and the sequence distinguishes generations.
58#[derive(Clone, Copy, PartialEq, Eq, Hash, Debug, Default)]
59#[repr(transparent)]
60pub struct Frn(pub u64);
61
62/// An MFT record number — an [`Frn`]'s low 48 bits.
63///
64/// The index's lookup key: liveness (not the sequence) resolves NTFS record
65/// reuse, so the key is just the record number.
66#[derive(Clone, Copy, PartialEq, Eq, PartialOrd, Ord, Hash, Debug, Default)]
67#[repr(transparent)]
68pub struct RecordNo(pub u64);
69
70impl Frn {
71    /// The record number this reference points at — its low 48 bits.
72    #[inline]
73    #[must_use]
74    pub const fn record(self) -> RecordNo {
75        RecordNo(self.0 & 0x0000_FFFF_FFFF_FFFF)
76    }
77}
78
79impl From<u64> for RecordNo {
80    /// Wrap a value already known to be a record number — the ergonomic
81    /// entry point for name lookups ([`VolumeIndex::entry_by_record`]) and
82    /// test fixtures. Derive one from a full reference with [`Frn::record`],
83    /// never by truncating a raw `u64` here.
84    #[inline]
85    fn from(record: u64) -> Self {
86        Self(record)
87    }
88}
89
90/// `reserve_exact` with a `len/64` floor, for merge-only arrays that grow a
91/// small batch at a time: bounds both copy frequency and permanent slack to
92/// ~1.6% (doubling would pin up to 2× as slack against the B/entry RAM gate).
93fn reserve_bounded<T>(v: &mut Vec<T>, additional: usize) {
94    let want = v.len() + additional;
95    if want > v.capacity() {
96        v.reserve_exact(additional.max(v.len() / 64));
97    }
98}
99
100/// Merge sorted `batch` into `perm` in place: each batch element
101/// binary-searches its insertion point and the segments between insertion
102/// points move once with `copy_within` — O(batch·log n) comparisons +
103/// O(moved) memmove + no allocation (ADR-0008).
104///
105/// Old elements are never reordered, and on a sorted array the strict
106/// total order (`cmp` id tie-break) makes the result the unique sorted
107/// merge. Arrays ordered by size/mtime can be locally stale-sorted
108/// (in-place `update_stat` never repositions an entry); placement there is
109/// deterministic best-effort.
110pub(crate) fn merge_sorted_tail(
111    perm: &mut Vec<EntryId>,
112    batch: &[EntryId],
113    cmp: impl Fn(EntryId, EntryId) -> std::cmp::Ordering,
114) {
115    if batch.is_empty() {
116        return;
117    }
118    let old = perm.len();
119    reserve_bounded(perm, batch.len());
120    perm.resize(old + batch.len(), 0);
121    let mut hi = old; // unmoved prefix of the old array (exclusive end)
122    let mut k = old + batch.len(); // write cursor (exclusive end)
123    for j in (0..batch.len()).rev() {
124        let b = batch[j];
125        // First old index whose element orders after `b`.
126        let pos = perm[..hi].partition_point(|&x| !cmp(x, b).is_gt());
127        let seg = hi - pos;
128        perm.copy_within(pos..hi, k - seg);
129        k -= seg + 1;
130        perm[k] = b;
131        hi = pos;
132    }
133    // k - hi == unplaced batch elements throughout; both cursors meet here.
134    debug_assert_eq!(k, hi, "merge cursors must close");
135}
136
137/// One record produced by an initial-scan source (raw $MFT today, `ReFS`
138/// enumeration in the future).
139pub struct RawEntry<'a> {
140    /// The parent directory's full reference — its `.record()` resolves the
141    /// parent (an unknown parent attaches the entry to the root).
142    pub parent_frn: Frn,
143    /// This entry's full reference; its `.record()` is the identity key.
144    pub frn: Frn,
145    /// The file name as raw UTF-16 code units (as stored in the MFT).
146    pub name_utf16: &'a [u16],
147    /// Whether this entry is a directory.
148    pub is_dir: bool,
149    /// Whether this entry is a reparse point (symlink, junction, mount point).
150    pub is_reparse: bool,
151    /// Raw `FILE_ATTRIBUTE_HIDDEN`.
152    pub is_hidden: bool,
153    /// Raw `FILE_ATTRIBUTE_SYSTEM`.
154    pub is_system: bool,
155    /// File size in bytes.
156    pub size: u64,
157    /// FILETIME (100ns ticks since 1601, UTC).
158    pub mtime: i64,
159}
160
161/// A [`RawEntry`] whose name is already WTF-8 encoded.
162///
163/// Parallel scan workers encode off the builder thread, the builder just
164/// memcpys. `name_wtf8`/`lower_wtf8` must come from
165/// [`crate::wtf8::push_wtf8_pair`] (equal lengths, shared offsets).
166pub struct EncodedEntry<'a> {
167    /// The parent directory's full reference — its `.record()` resolves the
168    /// parent (an unknown parent attaches the entry to the root).
169    pub parent_frn: Frn,
170    /// This entry's full reference; its `.record()` is the identity key.
171    pub frn: Frn,
172    /// The file name, WTF-8 encoded (paired with `lower_wtf8`, shared offsets).
173    pub name_wtf8: &'a [u8],
174    /// The lowercased file name, WTF-8 encoded (same length as `name_wtf8`).
175    pub lower_wtf8: &'a [u8],
176    /// Whether this entry is a directory.
177    pub is_dir: bool,
178    /// Whether this entry is a reparse point (symlink, junction, mount point).
179    pub is_reparse: bool,
180    /// Raw `FILE_ATTRIBUTE_HIDDEN`.
181    pub is_hidden: bool,
182    /// Raw `FILE_ATTRIBUTE_SYSTEM`.
183    pub is_system: bool,
184    /// File size in bytes.
185    pub size: u64,
186    /// FILETIME (100ns ticks since 1601, UTC).
187    pub mtime: i64,
188}
189
190// The sort key is contract surface (FmfQueryOptions.sort carries it as
191// u32) — the index uses the canonical definition directly (ADR-0018).
192pub use fmf_contract::options::SortKey;
fmf_core\index/mod.rs

fmf_core\index/
mod.rs
