commit caf098ddba148a3c3b24df91a2d2bfdf1f737f9c
parent bbd06a1f05949b10b0f6a248e07d525a3a3a5506
Author: Jack Mordaunt <jackmordaunt.dev@gmail.com>
Date: Fri, 18 Sep 2026 12:05:02 -0400
ntfs: let a scan be watched while it runs, and watch one
Nothing could see a scan until it ended, so a UI had to wait the whole 1.4
seconds before it had anything to draw. Three things stood in the way, and
none can be changed without the others, so they land together.
The caller now owns the table and passes it in, holding the pointer from the
start rather than receiving it at the end. Folding writes an entry's flags
last and atomically, so a watcher seeing them set is looking at a record whose
name and sizes are already there; without that order it could catch a name
half written, being a pointer and a length stored separately. The projection
borrows names instead of copying them, so repeating it allocates nothing.
live.odin is what those changes are for: the reader on its own thread, the
tree polled from the main one every 16 ms. Results appear 308 ms into a 1364
ms scan with the largest directory already correct. It also found the next
problem, which is what it was built for: per-frame cost climbs from 14 ms to
50 as the tree fills, because rolling up re-walks every ancestor chain and
re-zeroes every total each frame.
Diffstat:
| A | live.odin | | | 143 | +++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++ |
| M | main.odin | | | 35 | +++++++++++++++++++++++++++++++---- |
| M | ntfs/mft.odin | | | 30 | ++++++++++++++++++++++++++++-- |
| M | ntfs/reader.odin | | | 60 | +++++++++++++++++++++++++++++++++--------------------------- |
| M | ntfs/tree.odin | | | 32 | ++++++++++++++++++++++++-------- |
5 files changed, 259 insertions(+), 41 deletions(-)
diff --git a/live.odin b/live.odin
@@ -0,0 +1,143 @@
+package main
+
+import "core:fmt"
+import "core:sync"
+import "core:thread"
+import "core:time"
+
+import "ntfs"
+import "scan"
+
+/*
+Stand in for a UI.
+
+A real one repaints on a timer and must never block on the scan, so this runs the
+reader on its own thread and polls from here at the frame interval. What it prints
+each frame is what a UI could draw at that moment: the answer as it stood, not the
+answer it will eventually be.
+
+The point is to find out what the seam has to provide. Everything the loop touches
+has to be safe to read while a reader is writing it, and cheap enough to do sixty
+times a second.
+*/
+FRAME :: 16 * time.Millisecond
+
+Live :: struct {
+ volume: string,
+ opts: ntfs.Read_Options,
+ table: ^ntfs.Mft,
+ err: ntfs.Error,
+ done: b32,
+}
+
+run_live :: proc(volume: string, mount: string, opts: ntfs.Read_Options) -> int {
+ m: ntfs.Mft
+ defer ntfs.mft_destroy(&m)
+
+ l := Live {
+ volume = volume,
+ opts = opts,
+ table = &m,
+ }
+ worker := thread.create_and_start_with_poly_data(&l, scan_thread)
+ if worker == nil {
+ fmt.eprintln("error: could not start the scan")
+ return 1
+ }
+ defer thread.destroy(worker)
+
+ t: scan.Tree
+ if err := scan.tree_init(&t, 1); err != nil {
+ fmt.eprintfln("error: %v", err)
+ return 1
+ }
+ defer scan.tree_destroy(&t)
+
+ projection: ntfs.Projection
+ totals: [dynamic]u64
+ defer delete(totals)
+
+ start := time.tick_now()
+ frames := 0
+ settled := 0 // consecutive frames whose top twenty has not moved
+ previous: [TOP_N]Sized
+
+ for {
+ finished := bool(sync.atomic_load(&l.done))
+ frame_start := time.tick_now()
+
+ if ntfs.mft_ready(&m) {
+ // Both of these have to be cheap, because they run every frame.
+ if err := ntfs.to_tree(&m, &t, &projection); err != nil {
+ fmt.eprintfln("error: %v", err)
+ return 1
+ }
+ resize(&totals, int(t.count))
+ for i in 0 ..< len(totals) {
+ totals[i] = 0
+ }
+ roll_up(&t, totals[:])
+
+ top: [TOP_N]Sized
+ count := rank(&t, totals[:], top[:])
+ if count > 0 {
+ scan.node(&t, t.root).name = mount
+ }
+
+ if same_ranking(top, previous) {
+ settled += 1
+ } else {
+ settled = 0
+ }
+ previous = top
+
+ fmt.printfln(
+ "frame %3d %6.0f ms %8d nodes %10s top1 %s frame cost %.1f ms settled %d",
+ frames,
+ time.duration_milliseconds(time.tick_since(start)),
+ t.nodes_done,
+ human(count > 0 ? top[0].bytes : 0),
+ count > 0 ? scan.path(&t, top[0].record, context.temp_allocator) : "-",
+ time.duration_milliseconds(time.tick_since(frame_start)),
+ settled,
+ )
+ free_all(context.temp_allocator)
+ }
+ frames += 1
+
+ if finished {
+ break
+ }
+ // Sleep the rest of the frame, or not at all if the work overran it.
+ if spent := time.tick_since(frame_start); spent < FRAME {
+ time.sleep(FRAME - spent)
+ }
+ }
+ thread.join(worker)
+
+ if l.err != nil {
+ fmt.eprintfln("error: %v", l.err)
+ return 1
+ }
+ fmt.println()
+ fmt.printfln("scan finished in %.0f ms over %d frames", time.duration_milliseconds(time.tick_since(start)), frames)
+ print_largest(&t, totals[:], .files)
+ print_largest(&t, totals[:], .directories)
+ return 0
+}
+
+@(private = "file")
+scan_thread :: proc(l: ^Live) {
+ l.err = ntfs.read_mft(l.volume, l.table, l.opts)
+ sync.atomic_store(&l.done, true)
+}
+
+@(private = "file")
+same_ranking :: proc(a, b: [TOP_N]Sized) -> bool {
+ for i in 0 ..< TOP_N {
+ if a[i].record != b[i].record {
+ return false
+ }
+ }
+ return true
+}
diff --git a/main.odin b/main.odin
@@ -49,11 +49,14 @@ run :: proc() -> int {
target := "C:"
opts: ntfs.Read_Options
wcfg: walk.Config
+ live := false
for arg in os.args[1:] {
switch arg {
case "-h", "--help", "/?":
- fmt.println("usage: sonar [drive] [--buffered] [--no-skip] [--min-skip=N] [--workers=N] [--chunk=N]")
+ fmt.println("usage: sonar [drive] [--live] [--buffered] [--no-skip] [--min-skip=N] [--workers=N] [--chunk=N]")
return 0
+ case "--live":
+ live = true
case "--buffered":
opts.io_mode = .Buffered
case "--no-skip":
@@ -110,6 +113,14 @@ run :: proc() -> int {
return 1
}
+ if live {
+ if choice.engine != .Mft {
+ fmt.eprintln("error: live mode needs the MFT reader")
+ return 1
+ }
+ return run_live(resolved.volume, strings.trim_suffix(resolved.mount, `\`), opts)
+ }
+
t: scan.Tree
if err := scan.tree_init(&t, 8); err != nil {
fmt.eprintfln("error: %v", err)
@@ -124,7 +135,7 @@ run :: proc() -> int {
have_mft := false
switch choice.engine {
case .Mft:
- table, err := ntfs.read_mft(resolved.volume, opts)
+ err := ntfs.read_mft(resolved.volume, &m, opts)
if err != nil {
#partial switch err {
case .Access_Denied:
@@ -138,9 +149,9 @@ run :: proc() -> int {
}
return 1
}
- m = table
have_mft = true
- if err := ntfs.to_tree(&m, &t); err != nil {
+ projection: ntfs.Projection
+ if err := ntfs.to_tree(&m, &t, &projection); err != nil {
fmt.eprintfln("error: %v", err)
return 1
}
@@ -208,6 +219,22 @@ Kind :: enum {
directories,
}
+// The directories that hold the most, largest first.
+rank :: proc(t: ^scan.Tree, totals: []u64, top: []Sized) -> int {
+ count := 0
+ for i in 0 ..< t.count {
+ n := scan.node(t, i)
+ if .Used not_in n.flags || .Directory not_in n.flags {
+ continue
+ }
+ if totals[i] == 0 {
+ continue
+ }
+ top_n(top, &count, Sized{bytes = totals[i], record = i})
+ }
+ return count
+}
+
print_largest :: proc(t: ^scan.Tree, totals: []u64, kind: Kind) {
top: [TOP_N]Sized
count := 0
diff --git a/ntfs/mft.odin b/ntfs/mft.odin
@@ -3,6 +3,7 @@ package ntfs
import "core:mem"
import "core:mem/virtual"
import "core:strings"
+import "core:sync"
import "core:unicode/utf16"
import "core:unicode/utf8"
@@ -86,6 +87,7 @@ Mft :: struct {
bytes_per_cluster: u64,
stats: Mft_Stats,
allocator: mem.Allocator,
+ ready: b32, // the table exists and may be read while it fills
}
mft_init :: proc(m: ^Mft, record_count: int, bytes_per_cluster: u64, sinks := 1, allocator := context.allocator) -> Error {
@@ -122,6 +124,26 @@ mft_destroy :: proc(m: ^Mft) {
m^ = {}
}
+// Say the table is sized and safe to watch. Until then there is nothing to read.
+mft_set_ready :: proc(m: ^Mft) {
+ sync.atomic_store(&m.ready, true)
+}
+
+mft_ready :: proc(m: ^Mft) -> bool {
+ return bool(sync.atomic_load(&m.ready))
+}
+
+/*
+Whether an entry is finished and safe for another thread to read.
+
+Folding writes an entry's flags last, so a reader that sees them set is looking at a
+record whose name and sizes are already in place. Without that order a watcher could
+catch a half-written name, which is a pointer and a length written separately.
+*/
+entry_published :: proc(e: ^Entry) -> bool {
+ return .In_Use in transmute(Record_Flags)sync.atomic_load((^u16)(&e.flags))
+}
+
// Fold each worker's private results into the table. Only these needed merging;
// entries were written into slots no other worker could reach.
mft_merge_sinks :: proc(m: ^Mft) {
@@ -176,10 +198,10 @@ mft_add_record :: proc(m: ^Mft, record_number: u32, rec: []byte, sink: ^Sink) ->
return .Bad_Record
}
e := &m.entries[owner]
- if owner == record_number {
+ publish := owner == record_number
+ if publish {
e.sequence = h.sequence
e.link_count = h.link_count
- e.flags = h.flags
sink.stats.in_use += 1
if .Directory in h.flags {
sink.stats.directories += 1
@@ -219,6 +241,10 @@ mft_add_record :: proc(m: ^Mft, record_number: u32, rec: []byte, sink: ^Sink) ->
e.allocated += attr_disk_size(a, m.bytes_per_cluster)
}
}
+ // Last, and atomically: this is what tells a watching thread the entry is whole.
+ if publish {
+ sync.atomic_store((^u16)(&e.flags), transmute(u16)h.flags)
+ }
return .None
}
diff --git a/ntfs/reader.odin b/ntfs/reader.odin
@@ -65,14 +65,19 @@ Read_Options :: struct {
workers: int, // 0 selects DEFAULT_WORKERS
}
-// Open `path` (drive letter or image file) and read its whole MFT into a table.
-read_mft :: proc(path: string, opts := Read_Options{}, allocator := context.allocator) -> (m: Mft, err: Error) {
+/*
+Open `path` (drive letter or image file) and read its whole MFT into `m`.
+
+The caller owns the table rather than receiving it at the end, so another thread can
+watch it fill. `mft_ready` says when there is anything to watch.
+*/
+read_mft :: proc(path: string, m: ^Mft, opts := Read_Options{}, allocator := context.allocator) -> Error {
v, open_err := volume_open(path, opts.io_mode)
if open_err != nil {
- return {}, open_err
+ return open_err
}
defer volume_close(&v)
- return read_mft_from_volume(&v, opts, allocator)
+ return read_mft_from_volume(&v, m, opts, allocator)
}
/*
@@ -88,19 +93,19 @@ The MFT is addressed as a contiguous logical byte range and `read_logical` maps
chunk onto physical runs, so a record straddling two runs (possible when a cluster is
smaller than a record) is handled without special cases.
*/
-read_mft_from_volume :: proc(v: ^Volume, opts := Read_Options{}, allocator := context.allocator) -> (m: Mft, err: Error) {
+read_mft_from_volume :: proc(v: ^Volume, m: ^Mft, opts := Read_Options{}, allocator := context.allocator) -> Error {
// 1. Boot sector.
boot_buf, boot_alloc_err := mem.alloc_bytes(IO_ALIGN, IO_ALIGN, allocator)
if boot_alloc_err != nil {
- return {}, .Out_Of_Memory
+ return .Out_Of_Memory
}
defer mem.free_bytes(boot_buf, allocator)
if read_err := volume_read_at(v, boot_buf, 0); read_err != nil {
- return {}, read_err
+ return read_err
}
boot, boot_err := parse_boot_sector(boot_buf)
if boot_err != nil {
- return {}, boot_err
+ return boot_err
}
cluster := u64(boot.bytes_per_cluster)
record_size := int(boot.record_size)
@@ -109,18 +114,18 @@ read_mft_from_volume :: proc(v: ^Volume, opts := Read_Options{}, allocator := co
rec0_len := max(record_size, IO_ALIGN)
rec0_buf, rec0_alloc_err := mem.alloc_bytes(rec0_len, IO_ALIGN, allocator)
if rec0_alloc_err != nil {
- return {}, .Out_Of_Memory
+ return .Out_Of_Memory
}
defer mem.free_bytes(rec0_buf, allocator)
if read_err := volume_read_at(v, rec0_buf, boot.mft_lcn * cluster); read_err != nil {
- return {}, read_err
+ return read_err
}
rec0 := rec0_buf[:record_size]
if fix_err := apply_fixups(rec0); fix_err != nil {
- return {}, fix_err
+ return fix_err
}
if .In_Use not_in record_header(rec0).flags {
- return {}, .Bad_Record
+ return .Bad_Record
}
runs: []Run
@@ -145,21 +150,21 @@ read_mft_from_volume :: proc(v: ^Volume, opts := Read_Options{}, allocator := co
#partial switch a.type {
case .Data:
if !a.non_resident {
- return {}, .Mft_Data_Missing
+ return .Mft_Data_Missing
}
if found {
continue
}
decoded, run_err := decode_runlist(a.runlist, 0, allocator)
if run_err != nil {
- return {}, run_err
+ 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
+ return .Mft_Spans_Extension_Records
}
found = true
case .Bitmap:
@@ -173,7 +178,7 @@ read_mft_from_volume :: proc(v: ^Volume, opts := Read_Options{}, allocator := co
}
}
if !found {
- return {}, .Mft_Data_Missing
+ return .Mft_Data_Missing
}
// 3. Plan what to read, and cut it into chunks small enough to hand out.
@@ -200,7 +205,7 @@ read_mft_from_volume :: proc(v: ^Volume, opts := Read_Options{}, allocator := co
if extents == nil {
whole, extent_alloc_err := make([]Read_Extent, 1, allocator)
if extent_alloc_err != nil {
- return {}, .Out_Of_Memory
+ return .Out_Of_Memory
}
whole[0] = Read_Extent{0, mft_bytes}
extents = whole
@@ -221,14 +226,15 @@ read_mft_from_volume :: proc(v: ^Volume, opts := Read_Options{}, allocator := co
worker_count := flow.width(len(chunks), .Io, limit = opts.workers if opts.workers > 0 else DEFAULT_WORKERS)
record_count := int(mft_bytes / u64(record_size))
- if init_err := mft_init(&m, record_count, cluster, worker_count, allocator); init_err != nil {
- return {}, init_err
+ if init_err := mft_init(m, record_count, cluster, worker_count, allocator); init_err != nil {
+ return init_err
}
m.boot = boot
+ mft_set_ready(m)
// From here on, failures must release the table.
ok := false
defer if !ok {
- mft_destroy(&m)
+ mft_destroy(m)
}
m.stats.planned_bytes = planned_bytes
m.stats.skipped_bytes = mft_bytes - planned_bytes
@@ -236,7 +242,7 @@ read_mft_from_volume :: proc(v: ^Volume, opts := Read_Options{}, allocator := co
workers, workers_err := make([]Worker, worker_count, allocator)
if workers_err != nil {
- return {}, .Out_Of_Memory
+ return .Out_Of_Memory
}
defer delete(workers, allocator)
@@ -245,7 +251,7 @@ read_mft_from_volume :: proc(v: ^Volume, opts := Read_Options{}, allocator := co
live := 0
for i in 0 ..< worker_count {
w := &workers[i]
- w.mft = &m
+ w.mft = m
w.sink = &m.sinks[i]
w.record_size = record_size
w.cluster = cluster
@@ -269,7 +275,7 @@ read_mft_from_volume :: proc(v: ^Volume, opts := Read_Options{}, allocator := co
w := &workers[0]
wbuf, buf_err := mem.alloc_bytes(chunk, IO_ALIGN, allocator)
if buf_err != nil {
- return {}, .Out_Of_Memory
+ return .Out_Of_Memory
}
w.volume = v^
w.buf = wbuf
@@ -293,7 +299,7 @@ read_mft_from_volume :: proc(v: ^Volume, opts := Read_Options{}, allocator := co
flow.each(chunks[:], workers[:live], read_chunk, .Io)
for &w in workers[:live] {
if w.err != nil {
- return {}, w.err
+ return w.err
}
}
@@ -301,7 +307,7 @@ read_mft_from_volume :: proc(v: ^Volume, opts := Read_Options{}, allocator := co
// worker may own. Every base record is in place now, so they fold in serially.
for &w in workers[:live] {
for d in w.sink.deferred {
- if add_err := mft_add_record(&m, d.record, d.bytes, w.sink); add_err != nil {
+ if add_err := mft_add_record(m, d.record, d.bytes, w.sink); add_err != nil {
w.sink.stats.records_bad += 1
}
}
@@ -316,9 +322,9 @@ read_mft_from_volume :: proc(v: ^Volume, opts := Read_Options{}, allocator := co
}
m.stats.bitmap_ns = i64(time.tick_since(bitmap_start))
- mft_merge_sinks(&m)
+ mft_merge_sinks(m)
ok = true
- return m, .None
+ return .None
}
// A slice of the MFT's logical address space small enough to be one read, and the
diff --git a/ntfs/tree.odin b/ntfs/tree.odin
@@ -14,19 +14,31 @@ Record numbers become node indices unchanged, so the tree has a slot per record
including the dead ones. That wastes the slots but keeps every parent reference valid
without a second mapping, and a dead slot is simply not marked used.
*/
-to_tree :: proc(m: ^Mft, t: ^scan.Tree) -> scan.Error {
+/*
+Carried between projections so repeating one is cheap and adds nothing twice.
+*/
+Projection :: struct {
+ links_done: int,
+}
+
+to_tree :: proc(m: ^Mft, t: ^scan.Tree, p: ^Projection) -> scan.Error {
if err := scan.reserve(t, u32(len(m.entries))); err != nil {
return err
}
w := scan.writer(t, 0)
used, bytes: u64
- for e, i in m.entries {
- if .In_Use not_in e.flags || e.name == "" {
+ for i in 0 ..< len(m.entries) {
+ e := &m.entries[i]
+ // Only entries the reader has finished with, so a name is never half written.
+ if !entry_published(e) || e.name == "" {
continue
}
n := scan.node(t, u32(i))
- n.name = scan.intern(&w, e.name)
+ // Borrowed, not copied: names live in the table's arenas and stay put for its
+ // life, so repeating this projection allocates nothing. The table must
+ // therefore outlive the tree.
+ n.name = e.name
n.size = e.size
n.disk = e.allocated
n.flags = {.Used}
@@ -38,21 +50,23 @@ to_tree :: proc(m: ^Mft, t: ^scan.Tree) -> scan.Error {
}
// A parent that has been recycled since this name was written points at a
// different file now, so the node is rooted at itself and reads as orphaned.
- n.parent = e.parent if entry_parent_valid(m, e) else u32(i)
+ n.parent = e.parent if entry_parent_valid(m, e^) else u32(i)
used += 1
bytes += e.allocated
}
// Extra names for a file already counted. They belong in the tree so a file can
// be found at every path it has, but their bytes must not be counted twice.
- for l in m.links {
+ // Only the ones not projected before, or repeating this would add a node per
+ // link every time. Links are merged when the scan ends, so this is empty until.
+ for l in m.links[p.links_done:] {
index, err := scan.claim(&w, 1)
if err != nil {
return err
}
n := scan.node(t, index)
n.parent = l.parent
- n.name = scan.intern(&w, l.name)
+ n.name = l.name
n.disk = m.entries[l.record].allocated
n.size = m.entries[l.record].size
n.flags = {.Used, .Extra_Name}
@@ -60,7 +74,9 @@ to_tree :: proc(m: ^Mft, t: ^scan.Tree) -> scan.Error {
// NTFS names its root ".", which says nothing useful in a path. The caller knows
// where the volume is mounted and renames it.
+ p.links_done = len(m.links)
t.root = RECORD_ROOT
- scan.progress(t, used, bytes)
+ t.nodes_done = used
+ t.bytes_done = bytes
return .None
}
