commit e47006ad123714c9601ce80cf7dd4ba0189c2e09
parent caf098ddba148a3c3b24df91a2d2bfdf1f737f9c
Author: Jack Mordaunt <jackmordaunt.dev@gmail.com>
Date: Fri, 18 Sep 2026 12:28:26 -0400
main: keep directory totals across frames instead of rebuilding them
Recomputing cost the whole tree every frame, so the simulated UI climbed from
14 ms to 50 as the table filled, which is three frames of budget. Totals now
carry over and each node is charged once, so a frame costs what changed. It
holds flat at 8 to 13 ms for the whole scan.
Charging once is only correct if the chain is final, and it often is not:
workers publish out of order, so a child frequently arrives before the
directory holding it. A node whose parent is merely late would be rooted at
itself and its bytes would never reach its ancestors. So a node carries
whether its parent link can still change, the projection sets that only once
the parent has been published, and a node is charged to every ancestor at once
or held back and retried. Pending peaks around 31,000 and drains to nothing.
A settled record is then skipped, which also means its size is never re-read,
and extension records add to a base record after it was published. That cost
106 GiB of a badly fragmented volume. The scan-complete frame therefore resets
the projection and recomputes exactly; live and batch now agree to the byte.
Diffstat:
7 files changed, 235 insertions(+), 35 deletions(-)
diff --git a/live.odin b/live.odin
@@ -54,8 +54,9 @@ run_live :: proc(volume: string, mount: string, opts: ntfs.Read_Options) -> int
defer scan.tree_destroy(&t)
projection: ntfs.Projection
- totals: [dynamic]u64
- defer delete(totals)
+ defer ntfs.projection_destroy(&projection)
+ roll: Rollup
+ defer rollup_destroy(&roll)
start := time.tick_now()
frames := 0
@@ -72,14 +73,12 @@ run_live :: proc(volume: string, mount: string, opts: ntfs.Read_Options) -> int
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[:])
+ // Only what became final this frame, plus whatever is still waiting on an
+ // ancestor. Totals carry over rather than being rebuilt.
+ rollup_advance(&roll, &t, projection.fresh[:])
top: [TOP_N]Sized
- count := rank(&t, totals[:], top[:])
+ count := rank(&t, roll.totals[:], top[:])
if count > 0 {
scan.node(&t, t.root).name = mount
}
@@ -92,12 +91,13 @@ run_live :: proc(volume: string, mount: string, opts: ntfs.Read_Options) -> int
previous = top
fmt.printfln(
- "frame %3d %6.0f ms %8d nodes %10s top1 %s frame cost %.1f ms settled %d",
+ "frame %3d %6.0f ms %8d nodes %6d fresh %6d pending %10s cost %5.1f ms stable %d",
frames,
time.duration_milliseconds(time.tick_since(start)),
t.nodes_done,
+ len(projection.fresh),
+ len(roll.pending),
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,
)
@@ -115,14 +115,31 @@ run_live :: proc(volume: string, mount: string, opts: ntfs.Read_Options) -> int
}
thread.join(worker)
+ // The scan is over, so anything still pending was waiting on a parent that will
+ // never come, and extension records may have grown a size after it was charged.
+ // One exact pass settles both.
+ if ntfs.mft_ready(&m) {
+ // Redo every record: a size settled mid-scan misses whatever extension
+ // records added to it afterwards.
+ ntfs.projection_reset(&projection)
+ t.count = 0
+ ntfs.to_tree(&m, &t, &projection)
+ resize(&roll.totals, int(t.count))
+ for i in 0 ..< len(roll.totals) {
+ roll.totals[i] = 0
+ }
+ roll_up(&t, roll.totals[:])
+ scan.node(&t, t.root).name = mount
+ }
+
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)
+ print_largest(&t, roll.totals[:], .files)
+ print_largest(&t, roll.totals[:], .directories)
return 0
}
diff --git a/main.odin b/main.odin
@@ -151,6 +151,7 @@ run :: proc() -> int {
}
have_mft = true
projection: ntfs.Projection
+ defer ntfs.projection_destroy(&projection)
if err := ntfs.to_tree(&m, &t, &projection); err != nil {
fmt.eprintfln("error: %v", err)
return 1
diff --git a/ntfs/mft.odin b/ntfs/mft.odin
@@ -144,6 +144,31 @@ entry_published :: proc(e: ^Entry) -> bool {
return .In_Use in transmute(Record_Flags)sync.atomic_load((^u16)(&e.flags))
}
+/*
+An entry's parent, and whether that answer can still change.
+
+A parent record that has not been published yet may turn out to hold this name, so
+the link is not final until it appears. One that has been published and does not
+match never will be, which is just as final as a valid answer and lets the node be
+charged instead of waiting forever.
+
+The returned index is the entry's own when it has no usable parent.
+*/
+entry_parent_settled :: proc(m: ^Mft, i: u32) -> (parent: u32, settled: bool) {
+ e := &m.entries[i]
+ if int(e.parent) >= len(m.entries) || e.parent == i {
+ return i, true
+ }
+ p := &m.entries[e.parent]
+ if !entry_published(p) {
+ return i, false
+ }
+ if .Directory in p.flags && p.sequence == e.parent_sequence {
+ return e.parent, true
+ }
+ return i, true
+}
+
// 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) {
diff --git a/ntfs/tree.odin b/ntfs/tree.odin
@@ -1,9 +1,52 @@
package ntfs
+import "core:mem"
+
import "../scan"
/*
-Project a finished table into the normalised tree.
+Carried between projections so repeating one is cheap and adds nothing twice.
+
+`settled` remembers which records have been folded in for good. A record is only
+finished with once its parent reference is final, because a parent not yet published
+may still turn out to hold the name, and a node written before then would be left
+rooted at itself forever.
+
+`fresh` is what became final since the last call, which is the only work an
+incremental consumer has to do.
+*/
+Projection :: struct {
+ links_done: int,
+ settled: []u64, // one bit per record
+ fresh: [dynamic]u32,
+ allocator: mem.Allocator,
+}
+
+/*
+Forget what has been projected, so the next call redoes every record.
+
+A settled record is skipped on later calls, which is what makes a frame cheap, but it
+also means its size is never re-read. Extension records add to a base record after it
+was published, and a badly fragmented file can hold most of its allocation there, so
+a projection taken during a scan under-reports them. Call this once the scan has
+finished to get an exact answer.
+*/
+projection_reset :: proc(p: ^Projection) {
+ for i in 0 ..< len(p.settled) {
+ p.settled[i] = 0
+ }
+ p.links_done = 0
+ clear(&p.fresh)
+}
+
+projection_destroy :: proc(p: ^Projection) {
+ delete(p.settled, p.allocator)
+ delete(p.fresh)
+ p^ = {}
+}
+
+/*
+Project a table into the normalised tree, or bring an earlier projection up to date.
The table stays the native form and keeps what only NTFS has: record and sequence
numbers, per-stream allocation, the resident-file accounting. A caller wanting the
@@ -13,31 +56,43 @@ with the other readers.
Record numbers become node indices unchanged, so the tree has a slot per record slot,
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.
-*/
-/*
-Carried between projections so repeating one is cheap and adds nothing twice.
-*/
-Projection :: struct {
- links_done: int,
-}
+Safe to call while a scan runs: only records the reader has finished with are read,
+and names are borrowed from the table's arenas rather than copied, so repeating this
+allocates nothing. The table must therefore outlive the tree.
+*/
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
}
+ if p.settled == nil {
+ p.allocator = t.allocator
+ bits, err := make([]u64, (len(m.entries) + 63) / 64, p.allocator)
+ if err != nil {
+ return .Out_Of_Memory
+ }
+ p.settled = bits
+ p.fresh.allocator = p.allocator
+ }
+ clear(&p.fresh)
+
w := scan.writer(t, 0)
used, bytes: u64
- for i in 0 ..< len(m.entries) {
+ for i in 0 ..< u32(len(m.entries)) {
+ if marked(p.settled, i) {
+ used += 1
+ bytes += m.entries[i].allocated
+ continue
+ }
e := &m.entries[i]
- // Only entries the reader has finished with, so a name is never half written.
+ // Only records 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 := scan.node(t, i)
// 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.
+ // life, so repeating this projection allocates nothing.
n.name = e.name
n.size = e.size
n.disk = e.allocated
@@ -48,17 +103,22 @@ to_tree :: proc(m: ^Mft, t: ^scan.Tree, p: ^Projection) -> scan.Error {
if .Reparse_Point in e.attributes {
n.flags |= {.Reparse}
}
- // 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)
+
+ parent, settled := entry_parent_settled(m, i)
+ n.parent = parent
+ if settled {
+ n.flags |= {.Settled}
+ mark(p.settled, i)
+ append(&p.fresh, 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.
- // 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.
+ // be found at every path it has, but their bytes must not be counted twice. Only
+ // the ones not done before, or repeating this would add a node per link each
+ // time. Links are merged when the scan ends, so this is empty until then.
for l in m.links[p.links_done:] {
index, err := scan.claim(&w, 1)
if err != nil {
@@ -69,14 +129,25 @@ to_tree :: proc(m: ^Mft, t: ^scan.Tree, p: ^Projection) -> scan.Error {
n.name = l.name
n.disk = m.entries[l.record].allocated
n.size = m.entries[l.record].size
- n.flags = {.Used, .Extra_Name}
+ n.flags = {.Used, .Settled, .Extra_Name}
+ append(&p.fresh, index)
}
+ p.links_done = len(m.links)
// 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
t.nodes_done = used
t.bytes_done = bytes
return .None
}
+
+@(private)
+marked :: proc(b: []u64, i: u32) -> bool {
+ return b[i >> 6] & (1 << uint(i & 63)) != 0
+}
+
+@(private)
+mark :: proc(b: []u64, i: u32) {
+ b[i >> 6] |= 1 << uint(i & 63)
+}
diff --git a/rollup.odin b/rollup.odin
@@ -0,0 +1,81 @@
+package main
+
+import "core:slice"
+
+import "scan"
+
+/*
+Directory totals maintained across frames.
+
+Recomputing from scratch costs the whole tree every time, which is what made the
+simulated UI's frames climb from 14 ms to 50. Totals are never cleared here; each
+node is charged once, and a frame costs what changed rather than what exists.
+
+`pending` holds nodes that could not be charged yet because an ancestor had not been
+published. They are retried each frame and drain away as the scan fills in.
+*/
+Rollup :: struct {
+ totals: [dynamic]u64,
+ pending: [dynamic]u32,
+}
+
+rollup_destroy :: proc(r: ^Rollup) {
+ delete(r.totals)
+ delete(r.pending)
+ r^ = {}
+}
+
+// Charge everything newly settled, and retry what could not be charged before.
+rollup_advance :: proc(r: ^Rollup, t: ^scan.Tree, fresh: []u32) {
+ if int(t.count) > len(r.totals) {
+ resize(&r.totals, int(t.count))
+ }
+ retry := slice.clone(r.pending[:], context.temp_allocator)
+ clear(&r.pending)
+ for i in retry {
+ charge(r, t, i)
+ }
+ for i in fresh {
+ charge(r, t, i)
+ }
+}
+
+/*
+Charge a node to every ancestor at once, or to none of them.
+
+Stopping halfway would mean resuming from the middle once the rest of the chain
+arrives, which needs a record per node of how far it got. Waiting costs a re-walk
+instead, and the chain is a handful of links.
+
+Every node on the way up must be settled, not merely present: an unsettled one is
+rooted at itself for now and would look like the top of the tree.
+*/
+@(private = "file")
+charge :: proc(r: ^Rollup, t: ^scan.Tree, i: u32) {
+ n := scan.node(t, i)
+ if .Extra_Name in n.flags {
+ return // another name for a file already charged
+ }
+ chain: [64]u32
+ depth := 0
+ cur := i
+ for depth < len(chain) {
+ c := scan.node(t, cur)
+ if .Settled not_in c.flags {
+ append(&r.pending, i)
+ return
+ }
+ if c.parent == cur {
+ break // a root, or an orphan: the chain ends here
+ }
+ chain[depth] = c.parent
+ depth += 1
+ cur = c.parent
+ }
+ if .Directory in n.flags {
+ r.totals[i] += n.disk
+ }
+ for j in 0 ..< depth {
+ r.totals[chain[j]] += n.disk
+ }
+}
diff --git a/scan/tree.odin b/scan/tree.odin
@@ -18,6 +18,10 @@ Node :: struct {
Node_Flag :: enum u8 {
Used, // written by a reader; an untouched slot has this clear
+ // The parent link is final. A reader that learns of a child before its holding
+ // directory leaves this clear until the parent turns up, because until then the
+ // node cannot be told apart from one that has no parent at all.
+ Settled,
Directory,
Reparse, // junction, symlink or cloud placeholder: its target is counted elsewhere
Extra_Name, // another name for a node already counted, so rolling up must skip it
diff --git a/walk/walk.odin b/walk/walk.odin
@@ -54,7 +54,7 @@ scan :: proc(root: string, t: ^scan.Tree, cfg := Config{}) -> Error {
n := scan.node(t, first)
n.parent = first // a root holds itself
n.name = scan.intern(&w, root)
- n.flags = {.Used, .Directory}
+ n.flags = {.Used, .Settled, .Directory}
t.root = first
workers := cfg.workers
@@ -158,7 +158,8 @@ walk_dir :: proc(d: Dir, w: ^Worker) -> bool {
n.parent = d.index
n.name = scan.intern(&w.writer, info.name)
n.size = u64(max(info.size, 0))
- n.flags = {.Used}
+ // A walker reaches a child through its parent, so the link is never in doubt.
+ n.flags = {.Used, .Settled}
switch info.type {
case .Directory:
