commit 68d04bca0de2d92746edf00037eb9802aab2806a
parent fbed86a27fbc7a64a0f445a929c552404749467c
Author: Jack Mordaunt <jackmordaunt.dev@gmail.com>
Date: Fri, 18 Sep 2026 09:19:26 -0400
ntfs: skip dead record runs using $MFT's own bitmap
A third of this volume's MFT records are deleted entries that the scan reads
in full and throws away. $MFT carries a $BITMAP marking which slots are live,
so the dead ones can be known for the cost of one 300 KB read and jumped over
instead.
Skipping is not free: each break in the sequential stream costs about 140
microseconds, so short dead runs are cheaper to read through than to avoid.
Sweeping the threshold on a live volume put the floor at a megabyte, where
16.5% of the table is skipped and the read drops from 1295 ms to 1163 ms.
Skipping every dead run instead doubles the scan time.
Diffstat:
| M | main.odin | | | 27 | +++++++++++++++++++++++++-- |
| M | ntfs/mft.odin | | | 4 | ++++ |
| A | ntfs/plan.odin | | | 89 | +++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++ |
| M | ntfs/reader.odin | | | 186 | ++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++------------------- |
4 files changed, 259 insertions(+), 47 deletions(-)
diff --git a/main.odin b/main.odin
@@ -12,6 +12,8 @@ package main
import "core:debug/trace"
import "core:fmt"
import "core:os"
+import "core:strconv"
+import "core:strings"
import "core:time"
// Only referenced inside `when ODIN_DEBUG`; @(require) keeps release builds from
@@ -47,12 +49,22 @@ run :: proc() -> int {
for arg in os.args[1:] {
switch arg {
case "-h", "--help", "/?":
- fmt.println("usage: sonar [drive-or-image] [--buffered] (default C:)")
+ fmt.println("usage: sonar [drive-or-image] [--buffered] [--no-skip] [--min-skip=<bytes>]")
return 0
case "--buffered":
opts.io_mode = .Buffered
+ case "--no-skip":
+ opts.min_skip = -1
case:
- target = arg
+ // --min-skip=<bytes> tunes how long a run of dead records must be before
+ // breaking the sequential read to jump over it pays for itself.
+ if strings.has_prefix(arg, "--min-skip=") {
+ if n, parsed := strconv.parse_int(arg[len("--min-skip="):]); parsed {
+ opts.min_skip = n
+ }
+ } else {
+ target = arg
+ }
}
}
@@ -88,6 +100,17 @@ run :: proc() -> int {
print_largest_directories(&m, prefix)
d_dirs := time.tick_since(t_dirs)
fmt.println()
+ mft_bytes := m.stats.planned_bytes + m.stats.skipped_bytes
+ if mft_bytes > 0 {
+ fmt.printfln(
+ "plan read %s of %s in %d extents, skipped %s (%.1f%%) of dead records",
+ human(m.stats.planned_bytes),
+ human(mft_bytes),
+ m.stats.extents,
+ human(m.stats.skipped_bytes),
+ 100 * f64(m.stats.skipped_bytes) / f64(mft_bytes),
+ )
+ }
fmt.printfln("phase io %.0f ms", f64(m.stats.io_ns) / 1e6)
fmt.printfln("phase parse %.0f ms", f64(m.stats.parse_ns) / 1e6)
fmt.printfln("phase bitmap %.0f ms", f64(m.stats.bitmap_ns) / 1e6)
diff --git a/ntfs/mft.odin b/ntfs/mft.odin
@@ -41,6 +41,10 @@ Mft_Stats :: struct {
// Clusters $Bitmap reports as allocated; 0 when it could not be read. This is the
// file system's own total, independent of the per-file sums.
allocated_clusters: u64,
+ // What the read plan decided, from $MFT's own $BITMAP of live record slots.
+ planned_bytes: u64,
+ skipped_bytes: u64,
+ extents: u64,
// Phase timings, nanoseconds.
io_ns: i64,
parse_ns: i64,
diff --git a/ntfs/plan.odin b/ntfs/plan.odin
@@ -0,0 +1,89 @@
+package ntfs
+
+import "core:mem"
+
+// A byte range of the MFT's logical address space that is worth reading.
+@(private)
+Read_Extent :: struct {
+ offset: u64,
+ length: u64,
+}
+
+/*
+Decide which parts of the MFT to read.
+
+$MFT carries its own $BITMAP, one bit per record slot, so which slots are dead is
+known before a single record is fetched. On a volume that has seen a lot of churn the
+dead slots can be a third of the table, and reading them is pure waste.
+
+Skipping is only a win when the dead run is long enough that not reading it beats
+breaking the sequential stream and paying for another request, so gaps shorter than
+`min_gap` are read through instead. Extents are cluster aligned because a cluster can
+hold several records and unbuffered reads must cover whole sectors; a cluster counts
+as live when any record touching it is live.
+
+A slot the bitmap calls dead may briefly hold a record the file system is still
+allocating. The reader is already looking at a live volume without a snapshot, so
+that race is the same one the whole scan lives with.
+*/
+@(private)
+plan_reads :: proc(
+ bitmap: []byte,
+ mft_bytes: u64,
+ record_size, cluster, min_gap: u64,
+ allocator: mem.Allocator,
+) -> (extents: []Read_Extent, err: Error) {
+ out := make([dynamic]Read_Extent, allocator)
+ total_clusters := (mft_bytes + cluster - 1) / cluster
+ records := mft_bytes / record_size
+
+ start, end: u64 // current extent, in clusters; end is exclusive
+ open := false
+ for c: u64 = 0; c < total_clusters; c += 1 {
+ if !cluster_has_live_record(bitmap, c, records, record_size, cluster) {
+ continue
+ }
+ switch {
+ case !open:
+ start, end, open = c, c + 1, true
+ case (c - end) * cluster < min_gap:
+ end = c + 1 // the gap is too short to be worth skipping
+ case:
+ append(&out, Read_Extent{start * cluster, (end - start) * cluster})
+ start, end = c, c + 1
+ }
+ }
+ if open {
+ append(&out, Read_Extent{start * cluster, (end - start) * cluster})
+ }
+
+ // The last extent may run past the attribute's length once rounded to a cluster.
+ if len(out) > 0 {
+ last := &out[len(out) - 1]
+ if last.offset + last.length > mft_bytes {
+ last.length = mft_bytes - last.offset
+ }
+ }
+ return out[:], .None
+}
+
+@(private)
+cluster_has_live_record :: proc "contextless" (bitmap: []byte, c, records, record_size, cluster: u64) -> bool {
+ first := c * cluster / record_size
+ last := ((c + 1) * cluster - 1) / record_size
+ for r := first; r <= last && r < records; r += 1 {
+ if bit_is_set(bitmap, r) {
+ return true
+ }
+ }
+ return false
+}
+
+@(private)
+bit_is_set :: proc "contextless" (b: []byte, i: u64) -> bool {
+ byte_index := i / 8
+ if byte_index >= u64(len(b)) {
+ return false
+ }
+ return b[byte_index] & (1 << uint(i % 8)) != 0
+}
diff --git a/ntfs/reader.odin b/ntfs/reader.odin
@@ -26,9 +26,23 @@ IO_Mode :: enum {
Buffered,
}
+/*
+Shortest run of dead MFT records worth skipping over.
+
+Breaking the sequential stream costs about 140 microseconds per extra read, measured
+by sweeping this value on a live volume, so a skip only pays when the dead run takes
+longer than that to read. Below a quarter of a megabyte the extra requests cost more
+than the bytes they save, and at four kilobytes the scan is twice as slow as reading
+the whole table. Above a megabyte the curve flattens and then slowly worsens as real
+savings are left on the table. A megabyte sat at the bottom of that curve and also
+produces the fewest extents, which keeps the work easy to split across threads later.
+*/
+DEFAULT_MIN_SKIP :: mem.Megabyte
+
Read_Options :: struct {
chunk_size: int, // bytes per volume read; 0 selects DEFAULT_CHUNK_SIZE
io_mode: IO_Mode,
+ min_skip: int, // 0 selects DEFAULT_MIN_SKIP; negative reads the whole table
}
// Open `path` (drive letter or image file) and read its whole MFT into a table.
@@ -93,34 +107,50 @@ read_mft_from_volume :: proc(v: ^Volume, opts := Read_Options{}, allocator := co
defer delete(runs, allocator)
mft_bytes: u64
found := false
+
+ // $MFT's own $BITMAP marks which record slots are live, so the dead ones can be
+ // skipped rather than read and discarded.
+ slot_bitmap: []byte
+ defer mem.free_bytes(slot_bitmap, allocator)
+
it := attributes(rec0)
for {
a, ok := next_attribute(&it)
if !ok {
break
}
- if a.type != .Data || len(a.name) != 0 {
+ if len(a.name) != 0 || a.lowest_vcn != 0 {
continue
}
- if !a.non_resident {
- return {}, .Mft_Data_Missing
- }
- if a.lowest_vcn != 0 {
- continue
- }
- decoded, run_err := decode_runlist(a.runlist, 0, allocator)
- if run_err != nil {
- return {}, run_err
- }
- runs = decoded
- mft_bytes = a.data_size
- // If the run list in record 0 stops short of the data size, the rest of the
- // mapping lives in extension records reached via $ATTRIBUTE_LIST.
- if runlist_clusters(runs) * cluster < mft_bytes {
- return {}, .Mft_Spans_Extension_Records
+ #partial switch a.type {
+ case .Data:
+ if !a.non_resident {
+ return {}, .Mft_Data_Missing
+ }
+ if found {
+ continue
+ }
+ decoded, run_err := decode_runlist(a.runlist, 0, allocator)
+ if run_err != nil {
+ return {}, run_err
+ }
+ runs = decoded
+ mft_bytes = a.data_size
+ // If the run list in record 0 stops short of the data size, the rest of the
+ // mapping lives in extension records reached via $ATTRIBUTE_LIST.
+ if runlist_clusters(runs) * cluster < mft_bytes {
+ return {}, .Mft_Spans_Extension_Records
+ }
+ found = true
+ case .Bitmap:
+ if slot_bitmap != nil {
+ continue
+ }
+ // Losing the bitmap only costs the skipping, so a failure is not fatal.
+ if bm, bm_err := read_attribute(v, a, cluster, allocator); bm_err == nil {
+ slot_bitmap = bm
+ }
}
- found = true
- break
}
if !found {
return {}, .Mft_Data_Missing
@@ -151,34 +181,63 @@ read_mft_from_volume :: proc(v: ^Volume, opts := Read_Options{}, allocator := co
}
defer mem.free_bytes(buf, allocator)
- reader := Extent_Reader{v = v, runs = runs, cluster = cluster}
- record_number: u32 = 0
- for offset: u64 = 0; offset < mft_bytes; offset += u64(chunk) {
- n := int(min(u64(chunk), mft_bytes - offset))
- // Unbuffered reads must cover whole sectors. The run list is cluster granular,
- // so rounding the last chunk up to a cluster never reads past the allocation.
- read_n := min(int((u64(n) + cluster - 1) / cluster * cluster), chunk)
- io_start := time.tick_now()
- if read_err := read_logical(&reader, offset, buf[:read_n]); read_err != nil {
- return {}, read_err
+ // Decide what to read. Without the slot bitmap, or with skipping turned off, the
+ // plan is the whole table, which is what the reader did before.
+ extents: []Read_Extent
+ defer delete(extents, allocator)
+ if slot_bitmap != nil && opts.min_skip >= 0 {
+ min_skip := u64(DEFAULT_MIN_SKIP)
+ if opts.min_skip > 0 {
+ min_skip = u64(opts.min_skip)
}
- m.stats.io_ns += i64(time.tick_since(io_start))
- parse_start := time.tick_now()
- defer m.stats.parse_ns += i64(time.tick_since(parse_start))
- for start := 0; start + record_size <= n; start += record_size {
- rec := buf[start:start + record_size]
- defer record_number += 1
- // Slots never written are all zeros; skip them silently.
- if rd32(rec, 0) != RECORD_MAGIC {
- continue
- }
- m.stats.records_read += 1
- if apply_fixups(rec) != nil {
- m.stats.records_bad += 1
- continue
+ if planned, plan_err := plan_reads(slot_bitmap, mft_bytes, u64(record_size), cluster, min_skip, allocator); plan_err == nil {
+ extents = planned
+ }
+ }
+ if extents == nil {
+ whole, extent_alloc_err := make([]Read_Extent, 1, allocator)
+ if extent_alloc_err != nil {
+ return {}, .Out_Of_Memory
+ }
+ whole[0] = Read_Extent{0, mft_bytes}
+ extents = whole
+ }
+ for e in extents {
+ m.stats.planned_bytes += e.length
+ }
+ m.stats.skipped_bytes = mft_bytes - m.stats.planned_bytes
+ m.stats.extents = u64(len(extents))
+
+ reader := Extent_Reader{v = v, runs = runs, cluster = cluster}
+ for e in extents {
+ for offset := e.offset; offset < e.offset + e.length; offset += u64(chunk) {
+ n := int(min(u64(chunk), e.offset + e.length - offset))
+ // Unbuffered reads must cover whole sectors. The run list is cluster
+ // granular, so rounding up never reads past the attribute's allocation.
+ read_n := min(int((u64(n) + cluster - 1) / cluster * cluster), chunk)
+ io_start := time.tick_now()
+ if read_err := read_logical(&reader, offset, buf[:read_n]); read_err != nil {
+ return {}, read_err
}
- if add_err := mft_add_record(&m, record_number, rec); add_err != nil {
- m.stats.records_bad += 1
+ m.stats.io_ns += i64(time.tick_since(io_start))
+ parse_start := time.tick_now()
+ defer m.stats.parse_ns += i64(time.tick_since(parse_start))
+ for start := 0; start + record_size <= n; start += record_size {
+ rec := buf[start:start + record_size]
+ // Extents may skip forward, so the slot number comes from the offset.
+ record_number := u32((offset + u64(start)) / u64(record_size))
+ // Slots never written are all zeros; skip them silently.
+ if rd32(rec, 0) != RECORD_MAGIC {
+ continue
+ }
+ m.stats.records_read += 1
+ if apply_fixups(rec) != nil {
+ m.stats.records_bad += 1
+ continue
+ }
+ if add_err := mft_add_record(&m, record_number, rec); add_err != nil {
+ m.stats.records_bad += 1
+ }
}
}
}
@@ -194,6 +253,43 @@ read_mft_from_volume :: proc(v: ^Volume, opts := Read_Options{}, allocator := co
return m, .None
}
+// Read a whole attribute into memory: a copy of the value when resident, or the
+// clusters its run list names when not. The caller frees the result.
+@(private)
+read_attribute :: proc(v: ^Volume, a: Attribute, cluster: u64, allocator: mem.Allocator) -> (data: []byte, err: Error) {
+ if !a.non_resident {
+ if len(a.value) == 0 {
+ return nil, .Bad_Record
+ }
+ out, alloc_err := mem.alloc_bytes(len(a.value), IO_ALIGN, allocator)
+ if alloc_err != nil {
+ return nil, .Out_Of_Memory
+ }
+ copy(out, a.value)
+ return out, .None
+ }
+ runs, run_err := decode_runlist(a.runlist, 0, allocator)
+ if run_err != nil {
+ return nil, run_err
+ }
+ defer delete(runs, allocator)
+ // Unbuffered reads cover whole clusters, so the buffer is rounded up to one.
+ n := min((a.data_size + cluster - 1) / cluster * cluster, runlist_clusters(runs) * cluster)
+ if n == 0 {
+ return nil, .Bad_Runlist
+ }
+ out, alloc_err := mem.alloc_bytes(int(n), IO_ALIGN, allocator)
+ if alloc_err != nil {
+ return nil, .Out_Of_Memory
+ }
+ r := Extent_Reader{v = v, runs = runs, cluster = cluster}
+ if read_err := read_logical(&r, 0, out); read_err != nil {
+ mem.free_bytes(out, allocator)
+ return nil, read_err
+ }
+ return out, .None
+}
+
@(private)
Extent_Reader :: struct {
v: ^Volume,
