commit 60efb2ca4d52b4907e976ebe1c948315dcf570bd
parent 564dc3c0f4b56980178e084cb56e54f8b85adbe9
Author: Jack Mordaunt <jackmordaunt.dev@gmail.com>
Date: Sun, 20 Sep 2026 15:11:51 -0300
main: let any reader fill a live scan
The builder folded an ntfs.Mft itself and charged from the projection's list of
what had settled, so watching a scan only ever worked for one reader. It now
charges whatever the tree says is settled and knows nothing else; live.odin picks
a filler with the same switch the batch path already uses, and a walk can be
watched.
Watching a tree means it has to be safe to watch, which it was not: readers now
publish a node's flags last and atomically, `slots` stops at what is both claimed
and backed by a block, and hard links are folded only once the table says nothing
more is coming. Each of those raced the moment a second thread read the tree.
Diffstat:
| M | builder.odin | | | 68 | +++++++++++++++++++++++++------------------------------------------- |
| M | live.odin | | | 164 | ++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++------------- |
| M | main.odin | | | 54 | ++++++++++++++++++++++++++---------------------------- |
| M | ntfs/mft.odin | | | 11 | +++++++++++ |
| M | ntfs/reader.odin | | | 1 | + |
| M | ntfs/tree.odin | | | 32 | ++++++++++++++++---------------- |
| M | rollup.odin | | | 91 | +++++++++++++++++++++++++++++++++++++++++++++++++++++++------------------------- |
| M | scan/tree.odin | | | 54 | +++++++++++++++++++++++++++++++++++++++++++++++++++++- |
| M | walk/walk.odin | | | 10 | ++++++---- |
9 files changed, 338 insertions(+), 147 deletions(-)
diff --git a/builder.odin b/builder.odin
@@ -3,11 +3,10 @@ package main
import "core:sync"
import "core:time"
-import "ntfs"
import "scan"
/*
-Owns the tree and everything derived from it.
+Owns everything derived from the tree.
Between the readers and the UI there has to be somewhere the graph work happens.
Ancestors are shared between readers, so charging one from several threads would need
@@ -15,20 +14,20 @@ atomics on every total; giving a single thread sole ownership removes that entir
The UI is kept out for the opposite reason: its frame must cost the same whatever the
volume holds, so it reads a published snapshot rather than the tree.
-This runs as fast as it can rather than on a clock. Each pass folds whatever the
-readers have finished with, charges it, and publishes. If a pass takes longer than a
-frame the UI simply draws the previous answer.
+Nothing here knows which reader is filling the tree. A reader settles nodes and, if it
+has to correct itself, restates; those two are the whole of what passes between them.
+
+This runs as fast as it can rather than on a clock. Each pass charges whatever is newly
+settled, ranks it, and publishes. If a pass takes longer than a frame the UI simply
+draws the previous answer.
*/
Builder :: struct {
- table: ^ntfs.Mft,
- tree: ^scan.Tree,
- out: ^scan.Publisher,
- mount: string,
- scanning: ^b32, // cleared by the reader thread when the table is finished
- started: time.Tick,
- projection: ntfs.Projection,
- roll: Rollup,
- done: b32,
+ tree: ^scan.Tree,
+ out: ^scan.Publisher,
+ scanning: ^b32, // cleared once nothing is filling the tree any more
+ started: time.Tick,
+ roll: Rollup,
+ done: b32,
}
builder_run :: proc(b: ^Builder) {
@@ -41,41 +40,24 @@ builder_run :: proc(b: ^Builder) {
// still sees everything and this loop takes one more turn rather than missing
// the last of it.
finished := !bool(sync.atomic_load(b.scanning))
-
- if ntfs.mft_ready(b.table) {
- b.projection.root_name = b.mount
- builder_pass(b, exact = finished)
- }
+ builder_pass(b, complete = finished)
if finished {
return
}
}
}
-// One pass: fold what is newly readable, charge it, rank it, publish it.
+// One pass: charge what is newly settled, rank it, publish it.
@(private = "file")
-builder_pass :: proc(b: ^Builder, exact: bool) {
- if exact {
- // A record settled mid-scan misses whatever extension records added to it
- // afterwards, so the last pass redoes every one of them. The tree is not
- // emptied first: a UI resolves the paths of the rows it drew from it, and an
- // empty tree would hand that thread a truncated one. Redoing a projection
- // rewrites each slot where it already sat.
- ntfs.projection_reset(&b.projection)
- }
- if err := ntfs.to_tree(b.table, b.tree, &b.projection); err != nil {
- return
- }
- if exact {
- resize(&b.roll.totals, int(b.tree.count))
- for i in 0 ..< len(b.roll.totals) {
- b.roll.totals[i] = 0
- }
- clear(&b.roll.pending)
- roll_up(b.tree, b.roll.totals[:])
- } else {
- rollup_advance(&b.roll, b.tree, b.projection.fresh[:])
+builder_pass :: proc(b: ^Builder, complete: bool) {
+ // A reader that corrects itself invalidates every total drawn from what it said
+ // before, so those start again rather than being added to. It restates only once
+ // the rewrite is finished, so one pass over the tree is enough to replace them.
+ if scan.taken_restated(b.tree) {
+ rollup_restate(&b.roll)
}
+ rollup_advance(&b.roll, b.tree)
+
top: [scan.TOP_ROWS]Sized
count := rank(b.tree, b.roll.totals[:], top[:])
@@ -83,9 +65,9 @@ builder_pass :: proc(b: ^Builder, exact: bool) {
count = count,
nodes = b.tree.nodes_done,
bytes = b.tree.bytes_done,
- pending = len(b.roll.pending),
+ pending = b.roll.pending,
elapsed = time.duration_milliseconds(time.tick_since(b.started)),
- complete = exact,
+ complete = complete,
}
for i in 0 ..< count {
s.rows[i] = {
diff --git a/live.odin b/live.odin
@@ -7,35 +7,55 @@ import "core:time"
import "ntfs"
import "scan"
+import "walk"
/*
Stand in for a UI.
-Three threads, as the scan is meant to run: readers filling the table, a builder
-owning the tree and everything derived from it, and this loop drawing. The point of
-the arrangement is that a frame costs the same whatever the volume holds, because it
-reads a published snapshot of twenty rows rather than the tree.
+Three jobs, as the scan is meant to run: a reader filling the tree, a builder owning
+everything derived from it, and this loop drawing. The point of the arrangement is
+that a frame costs the same whatever the volume holds, because it reads a published
+snapshot of twenty rows rather than the tree.
+
+Which reader fills it is decided in one switch below and nowhere else. The builder is
+told nothing about it: a reader settles nodes, and restates if it has to correct
+itself, and that is the whole of the conversation.
Nothing here waits on the builder. If a build pass is mid-write the loop draws the
answer from the last one.
*/
FRAME :: 16 * time.Millisecond
+// A reader filling the tree, and what it left behind. Only the fields its own engine
+// uses are set.
@(private = "file")
-Reader :: struct {
+Fill :: struct {
+ tree: ^scan.Tree,
+ table: ^ntfs.Mft,
volume: string,
+ // Where a walk starts, or what an MFT calls its root. One reader runs, and it
+ // reads the one that means something to it.
+ root: string,
opts: ntfs.Read_Options,
- table: ^ntfs.Mft,
- err: ntfs.Error,
- scanning: b32,
+ wcfg: walk.Config,
+ mft_err: ntfs.Error,
+ walk_err: walk.Error,
+ tree_err: scan.Error,
+ reading: b32, // the table is still being read
+ scanning: b32, // the tree is still being filled
}
-run_live :: proc(volume: string, mount: string, opts: ntfs.Read_Options) -> int {
+run_live :: proc(
+ target: scan.Target,
+ choice: scan.Choice,
+ opts: ntfs.Read_Options,
+ wcfg: walk.Config,
+) -> int {
m: ntfs.Mft
defer ntfs.mft_destroy(&m)
t: scan.Tree
- if err := scan.tree_init(&t, 1); err != nil {
+ if err := scan.tree_init(&t, 8); err != nil {
fmt.eprintfln("error: %v", err)
return 1
}
@@ -44,27 +64,47 @@ run_live :: proc(volume: string, mount: string, opts: ntfs.Read_Options) -> int
out: scan.Publisher
started := time.tick_now()
- r := Reader {
- volume = volume,
- opts = opts,
+ f := Fill {
+ tree = &t,
table = &m,
+ volume = target.volume,
+ opts = opts,
+ wcfg = wcfg,
scanning = true,
}
b := Builder {
- table = &m,
tree = &t,
out = &out,
- mount = mount,
- scanning = &r.scanning,
+ scanning = &f.scanning,
started = started,
}
- reader := thread.create_and_start_with_poly_data(&r, read_thread)
- if reader == nil {
+ // Freed at function scope. A defer inside the switch below would run as the case
+ // ended, with the reader still holding the string.
+ owned_root: string
+ defer if owned_root != "" {
+ delete(owned_root)
+ }
+
+ // The one place a reader is chosen for a live scan, as in the batch path.
+ filler: ^thread.Thread
+ switch choice.engine {
+ case .Mft:
+ f.root = scan.top(target)
+ filler = thread.create_and_start_with_poly_data(&f, mft_fill)
+ case .Walk:
+ owned_root = scan.location(target, context.allocator)
+ f.root = owned_root
+ filler = thread.create_and_start_with_poly_data(&f, walk_fill)
+ case .None:
+ fmt.eprintln("error: nothing here can be scanned")
+ return 1
+ }
+ if filler == nil {
fmt.eprintln("error: could not start the reader")
return 1
}
- defer thread.destroy(reader)
+ defer thread.destroy(filler)
builder := thread.create_and_start_with_poly_data(&b, build_thread)
if builder == nil {
@@ -72,7 +112,6 @@ run_live :: proc(volume: string, mount: string, opts: ntfs.Read_Options) -> int
return 1
}
defer thread.destroy(builder)
- defer ntfs.projection_destroy(&b.projection)
defer rollup_destroy(&b.roll)
frames, drawn, missed := 0, 0, 0
@@ -83,7 +122,6 @@ run_live :: proc(volume: string, mount: string, opts: ntfs.Read_Options) -> int
frame_start := time.tick_now()
finished := bool(sync.atomic_load(&b.done))
- // The whole frame. Everything below is twenty rows and their paths.
if s, ok := scan.current(&out); ok {
last = s
have = true
@@ -91,6 +129,7 @@ run_live :: proc(volume: string, mount: string, opts: ntfs.Read_Options) -> int
} else {
missed += 1
}
+
if have && last.count > 0 {
fmt.printfln(
"frame %3d %6.0f ms %8d nodes %6d pending %10s %s frame %5.2f ms%s",
@@ -110,17 +149,28 @@ run_live :: proc(volume: string, mount: string, opts: ntfs.Read_Options) -> int
if finished {
break
}
+
if spent := time.tick_since(frame_start); spent < FRAME {
time.sleep(FRAME - spent)
}
}
- thread.join(reader)
+
+ thread.join(filler)
thread.join(builder)
- if r.err != nil {
- fmt.eprintfln("error: %v", r.err)
+ if f.mft_err != nil {
+ fmt.eprintfln("error: %v", f.mft_err)
+ return 1
+ }
+ if f.walk_err != nil {
+ fmt.eprintfln("error: %v", f.walk_err)
+ return 1
+ }
+ if f.tree_err != nil {
+ fmt.eprintfln("error: %v", f.tree_err)
return 1
}
+
fmt.println()
fmt.printfln(
"scan finished in %.0f ms over %d frames, %d drawn, %d skipped mid-write",
@@ -129,15 +179,75 @@ run_live :: proc(volume: string, mount: string, opts: ntfs.Read_Options) -> int
drawn,
missed,
)
+
print_largest(&t, b.roll.totals[:], .files)
print_largest(&t, b.roll.totals[:], .directories)
+
return 0
}
+/*
+Read the table on its own threads, folding it into the tree as it fills.
+
+read_mft blocks until the whole table is read, so it gets a thread and this one folds
+beside it. A record settled part way through misses whatever extension records added
+to it afterwards, so once the reading is over every record is folded again and the
+tree restated, which is how the builder learns its totals have to start over.
+*/
+@(private = "file")
+mft_fill :: proc(f: ^Fill) {
+ defer sync.atomic_store(&f.scanning, false)
+
+ sync.atomic_store(&f.reading, true)
+ reader := thread.create_and_start_with_poly_data(f, mft_read)
+ if reader == nil {
+ f.mft_err = .Open_Failed
+ return
+ }
+ defer thread.destroy(reader)
+
+ p: ntfs.Projection
+ p.root_name = f.root
+ defer ntfs.projection_destroy(&p)
+
+ for {
+ // Read first, so a table that finishes mid-fold still gets one more pass.
+ reading := bool(sync.atomic_load(&f.reading))
+ if ntfs.mft_ready(f.table) {
+ if err := ntfs.to_tree(f.table, f.tree, &p); err != nil {
+ f.tree_err = err
+ break
+ }
+ }
+ if !reading {
+ break
+ }
+ }
+ thread.join(reader)
+ if f.mft_err != nil || f.tree_err != nil {
+ return
+ }
+
+ ntfs.projection_reset(&p)
+ if err := ntfs.to_tree(f.table, f.tree, &p); err != nil {
+ f.tree_err = err
+ return
+ }
+ scan.restate(f.tree)
+}
+
+@(private = "file")
+mft_read :: proc(f: ^Fill) {
+ f.mft_err = ntfs.read_mft(f.volume, f.table, f.opts)
+ sync.atomic_store(&f.reading, false)
+}
+
+// Walk directories straight into the tree. Nothing is restated: a walk reaches a child
+// through its parent, so a node is final when it is written.
@(private = "file")
-read_thread :: proc(r: ^Reader) {
- r.err = ntfs.read_mft(r.volume, r.table, r.opts)
- sync.atomic_store(&r.scanning, false)
+walk_fill :: proc(f: ^Fill) {
+ defer sync.atomic_store(&f.scanning, false)
+ f.walk_err = walk.scan(f.root, f.tree, f.wcfg)
}
@(private = "file")
diff --git a/main.odin b/main.odin
@@ -69,9 +69,9 @@ run :: proc() -> int {
return 0 if asked_for_help else 1
}
- target := opt.target
- if target == "" {
- target = os.user_home_dir(context.temp_allocator) or_else "/"
+ target_str := opt.target
+ if target_str == "" {
+ target_str = os.user_home_dir(context.temp_allocator) or_else "/"
}
opts := ntfs.Read_Options {
chunk_size = opt.chunk,
@@ -84,44 +84,40 @@ run :: proc() -> int {
workers = opt.walk_workers,
}
- // Resolve once, so the reader is chosen from what the OS says rather than from
- // the shape of the string, and comes back with it.
- resolved, choice, resolve_err := scan.resolve(target)
+ target, engine, resolve_err := scan.resolve(target_str)
if resolve_err != nil {
- fmt.eprintfln("error: cannot scan %s: %v", target, resolve_err)
+ fmt.eprintfln("error: cannot scan %s: %v", target_str, resolve_err)
return 1
}
- defer scan.target_destroy(&resolved)
+ defer scan.target_destroy(&target)
fmt.printfln(
"sonar: %s on %s (%v, %v engine, %v io)",
- scan.location(resolved, context.temp_allocator),
- resolved.volume,
- resolved.fs,
- choice.engine,
+ scan.location(target, context.temp_allocator),
+ target.volume,
+ target.fs,
+ engine.engine,
opts.io_mode,
)
- if choice.permission_would_help {
+
+ if engine.permission_would_help {
when ODIN_OS == .Windows {
fmt.eprintln("note: this volume reads far faster from an administrator prompt")
} else {
fmt.eprintfln(
"note: this volume reads far faster with permission to open %s directly",
- resolved.volume,
+ target.volume,
)
}
}
- if choice.engine == .None {
+
+ if engine.engine == .None {
fmt.eprintfln("error: nothing here can be scanned")
return 1
}
if opt.live {
- if choice.engine != .Mft {
- fmt.eprintln("error: live mode needs the MFT reader")
- return 1
- }
- return run_live(resolved.volume, scan.top(resolved), opts)
+ return run_live(target, engine, opts, wcfg)
}
t: scan.Tree
@@ -141,9 +137,9 @@ run :: proc() -> int {
defer if have_mft {
ntfs.mft_destroy(&m)
}
- switch choice.engine {
+ switch engine.engine {
case .Mft:
- err := ntfs.read_mft(resolved.volume, &m, opts)
+ err := ntfs.read_mft(target.volume, &m, opts)
if err != nil {
#partial switch err {
case .Access_Denied:
@@ -153,7 +149,7 @@ run :: proc() -> int {
case .Not_Ntfs:
fmt.eprintln("error: not an NTFS volume")
case .Open_Failed:
- fmt.eprintfln("error: could not open %s", resolved.volume)
+ fmt.eprintfln("error: could not open %s", target.volume)
case:
fmt.eprintfln("error: %v", err)
}
@@ -168,9 +164,9 @@ run :: proc() -> int {
}
// The table calls its root ".", so paths would lose the volume it came from.
rw := scan.writer(&t, 0)
- scan.node(&t, t.root).name = scan.intern(&rw, scan.top(resolved))
+ scan.node(&t, t.root).name = scan.intern(&rw, scan.top(target))
case .Walk:
- root := scan.location(resolved, context.temp_allocator)
+ root := scan.location(target, context.temp_allocator)
if err := walk.scan(root, &t, wcfg); err != nil {
fmt.eprintfln("error: walking %s: %v", root, err)
return 1
@@ -235,9 +231,11 @@ Kind :: enum {
// 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 {
+ // Bounded by the totals rather than the tree: a reader may hand out more slots
+ // while this runs, and those have not been charged yet.
+ for i in 0 ..< u32(len(totals)) {
+ f := scan.node_flags(scan.node(t, i))
+ if .Used not_in f || .Directory not_in f {
continue
}
if totals[i] == 0 {
diff --git a/ntfs/mft.odin b/ntfs/mft.odin
@@ -88,6 +88,7 @@ Mft :: struct {
stats: Mft_Stats,
allocator: mem.Allocator,
ready: b32, // the table exists and may be read while it fills
+ complete: b32, // nothing further will be added to it
}
mft_init :: proc(
@@ -139,6 +140,16 @@ mft_ready :: proc(m: ^Mft) -> bool {
return bool(sync.atomic_load(&m.ready))
}
+// Say the table is finished. Hard links are merged in at the very end, so anything
+// reading them concurrently has to wait for this.
+mft_set_complete :: proc(m: ^Mft) {
+ sync.atomic_store(&m.complete, true)
+}
+
+mft_complete :: proc(m: ^Mft) -> bool {
+ return bool(sync.atomic_load(&m.complete))
+}
+
/*
Whether an entry is finished and safe for another thread to read.
diff --git a/ntfs/reader.odin b/ntfs/reader.odin
@@ -353,6 +353,7 @@ read_mft_from_volume :: proc(
m.stats.bitmap_ns = i64(time.tick_since(bitmap_start))
mft_merge_sinks(m)
+ mft_set_complete(m)
ok = true
return .None
}
diff --git a/ntfs/tree.odin b/ntfs/tree.odin
@@ -22,7 +22,6 @@ Projection :: struct {
root_name: string,
links_done: int,
settled: []u64, // one bit per record
- fresh: [dynamic]u32,
allocator: mem.Allocator,
}
@@ -40,12 +39,10 @@ projection_reset :: proc(p: ^Projection) {
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^ = {}
}
@@ -66,10 +63,15 @@ and names are borrowed from the table's arenas rather than copied, so repeating
allocates nothing. The table must therefore outlive the tree.
*/
to_tree :: proc(m: ^Mft, t: ^scan.Tree, p: ^Projection) -> scan.Error {
+ // Hard links are merged into the table in one go at the very end, so reading them
+ // before that would race the reader appending them, and would size the tree from
+ // a count that was still growing.
+ links := len(m.links) if mft_complete(m) else 0
+
// Records take slot per slot, extra names the range directly above them. Sizing
// for both up front is what lets a replay land on the same slots as the pass
// before it, so repeating one never has to empty the tree first.
- if err := scan.reserve(t, u32(len(m.entries) + len(m.links))); err != nil {
+ if err := scan.reserve(t, u32(len(m.entries) + links)); err != nil {
return err
}
if p.settled == nil {
@@ -79,9 +81,7 @@ to_tree :: proc(m: ^Mft, t: ^scan.Tree, p: ^Projection) -> scan.Error {
return .Out_Of_Memory
}
p.settled = bits
- p.fresh.allocator = p.allocator
}
- clear(&p.fresh)
used, bytes: u64
@@ -102,21 +102,22 @@ to_tree :: proc(m: ^Mft, t: ^scan.Tree, p: ^Projection) -> scan.Error {
n.name = e.name
n.size = e.size
n.disk = e.allocated
- n.flags = {.Used}
+
+ flags := scan.Node_Flags{.Used}
if .Directory in e.flags {
- n.flags |= {.Directory}
+ flags |= {.Directory}
}
if .Reparse_Point in e.attributes {
- n.flags |= {.Reparse}
+ flags |= {.Reparse}
}
-
parent, settled := entry_parent_settled(m, i)
n.parent = parent
if settled {
- n.flags |= {.Settled}
+ flags |= {.Settled}
mark(p.settled, i)
- append(&p.fresh, i)
}
+ // Last, so a builder watching this tree never sees a node before its parent.
+ scan.node_publish(n, flags)
used += 1
bytes += e.allocated
}
@@ -126,17 +127,16 @@ to_tree :: proc(m: ^Mft, t: ^scan.Tree, p: ^Projection) -> scan.Error {
// sits at its ordinal above the record range, so a link written twice is written
// to the same slot. Links are merged when the scan ends, so this is empty
// until then.
- for l, k in m.links[p.links_done:] {
+ for l, k in m.links[p.links_done:links] {
index := u32(len(m.entries) + p.links_done + k)
n := scan.node(t, index)
n.parent = l.parent
n.name = l.name
n.disk = m.entries[l.record].allocated
n.size = m.entries[l.record].size
- n.flags = {.Used, .Settled, .Extra_Name}
- append(&p.fresh, index)
+ scan.node_publish(n, {.Used, .Settled, .Extra_Name})
}
- p.links_done = len(m.links)
+ p.links_done = links
t.root = RECORD_ROOT
if p.root_name != "" {
diff --git a/rollup.odin b/rollup.odin
@@ -1,42 +1,65 @@
package main
-import "core:slice"
-
import "scan"
/*
-Directory totals maintained across frames.
+Directory totals maintained across passes.
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.
+simulated UI's frames climb from 14 ms to 50. Totals are never cleared here; each node
+is charged once and stays charged.
-`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.
+Which nodes those are is read off the tree rather than told: a reader says a node is
+settled, and `charged` remembers whether this has acted on it yet. That keeps the
+arithmetic the same whichever reader ran, and a node whose ancestors have not arrived
+is simply left unmarked and reached again next pass.
*/
Rollup :: struct {
totals: [dynamic]u64,
- pending: [dynamic]u32,
+ charged: [dynamic]u64, // one bit per node
+ pending: int, // settled nodes still waiting on an ancestor, as of the last pass
}
rollup_destroy :: proc(r: ^Rollup) {
delete(r.totals)
- delete(r.pending)
+ delete(r.charged)
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))
+// Forget every total, for a reader that has restated what it already said.
+rollup_restate :: proc(r: ^Rollup) {
+ for i in 0 ..< len(r.totals) {
+ r.totals[i] = 0
+ }
+ for i in 0 ..< len(r.charged) {
+ r.charged[i] = 0
}
- retry := slice.clone(r.pending[:], context.temp_allocator)
- clear(&r.pending)
- for i in retry {
- charge(r, t, i)
+ r.pending = 0
+}
+
+// Charge every settled node not charged already.
+rollup_advance :: proc(r: ^Rollup, t: ^scan.Tree) {
+ count := int(scan.slots(t))
+ if count > len(r.totals) {
+ resize(&r.totals, count)
}
- for i in fresh {
- charge(r, t, i)
+ if words := (count + 63) / 64; words > len(r.charged) {
+ resize(&r.charged, words)
+ }
+ r.pending = 0
+ for i in 0 ..< u32(count) {
+ if marked(r.charged[:], i) {
+ continue
+ }
+ f := scan.node_flags(scan.node(t, i))
+ if .Used not_in f || .Settled not_in f {
+ continue
+ }
+ if charge(r, t, i) {
+ mark(r.charged[:], i)
+ } else {
+ r.pending += 1
+ }
}
}
@@ -48,37 +71,49 @@ arrives, which needs a record per node of how far it got. Waiting costs a re-wal
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.
+rooted at itself for now and would look like the top of the tree. Returning false
+leaves it uncharged, which is the whole of what has to be remembered about it.
*/
@(private = "file")
-charge :: proc(r: ^Rollup, t: ^scan.Tree, i: u32) {
+charge :: proc(r: ^Rollup, t: ^scan.Tree, i: u32) -> bool {
n := scan.node(t, i)
- if .Extra_Name in n.flags {
- return // another name for a file already charged
+ flags := scan.node_flags(n)
+ if .Extra_Name in flags {
+ return true // 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 .Settled not_in scan.node_flags(c) {
+ return false
}
// A root, an orphan, or a parent that leaves the tree: the chain ends here.
// The batch roll-up and path rebuilding both stop on the same conditions, and
// this is the one that runs while a reader is still filling slots in.
- if c.parent == cur || c.parent >= t.count {
+ if c.parent == cur || c.parent >= u32(len(r.totals)) {
break
}
chain[depth] = c.parent
depth += 1
cur = c.parent
}
- if .Directory in n.flags {
+ if .Directory in flags {
r.totals[i] += n.disk
}
for j in 0 ..< depth {
r.totals[chain[j]] += n.disk
}
+ return true
+}
+
+@(private = "file")
+marked :: proc(b: []u64, i: u32) -> bool {
+ return b[i >> 6] & (1 << uint(i & 63)) != 0
+}
+
+@(private = "file")
+mark :: proc(b: []u64, i: u32) {
+ b[i >> 6] |= 1 << uint(i & 63)
}
diff --git a/scan/tree.odin b/scan/tree.odin
@@ -58,6 +58,7 @@ Tree :: struct {
nodes_done: u64,
bytes_done: u64,
cancel: b32,
+ restated: b32,
allocator: mem.Allocator,
}
@@ -122,6 +123,23 @@ node :: proc(t: ^Tree, i: u32) -> ^Node {
return &t.blocks[i >> BLOCK_SHIFT][i & (BLOCK_NODES - 1)]
}
+/*
+Finish a node, once everything else about it is written.
+
+Flags go last and atomically, so a reader that sees them is looking at a node whose
+name, sizes and parent are already in place. Without that order a watcher could charge
+a node for a size that had not been stored yet.
+*/
+node_publish :: proc(n: ^Node, flags: Node_Flags) {
+ sync.atomic_store((^u8)(&n.flags), transmute(u8)flags)
+}
+
+// A node's flags, read as a watcher must. Pairs with `node_publish`: an untouched slot
+// reads back empty, and a written one reads back whole.
+node_flags :: proc(n: ^Node) -> Node_Flags {
+ return transmute(Node_Flags)sync.atomic_load((^u8)(&n.flags))
+}
+
// Copy a name into this writer's arena, where it stays valid for the tree's life.
intern :: proc(w: ^Writer, name: string) -> string {
buf, err := make([]byte, len(name), virtual.arena_allocator(w.arena))
@@ -160,6 +178,17 @@ width_for :: proc(items, most: int) -> int {
return max(min(items, most), 1)
}
+/*
+Slots that can be addressed right now.
+
+`claim` takes its range before allocating the block that backs it, so the count alone
+runs ahead of what exists. Whichever is smaller is the part a watcher may look at; a
+slot claimed but not yet written reads back with no flags set and is simply skipped.
+*/
+slots :: proc(t: ^Tree) -> u32 {
+ return min(sync.atomic_load(&t.count), sync.atomic_load(&t.committed))
+}
+
// A reader checks this between units of work so a UI can call the scan off.
cancelled :: proc(t: ^Tree) -> bool {
return bool(sync.atomic_load(&t.cancel))
@@ -169,6 +198,25 @@ cancel :: proc(t: ^Tree) {
sync.atomic_store(&t.cancel, true)
}
+/*
+Say that what was read out of this tree before may be wrong.
+
+A reader that can only learn a node's final size late has to write some of them twice,
+and anything derived from the first writing has to be thrown away rather than added
+to. Set once the restatement is complete, so whoever acts on it sees the finished
+tree rather than one mid-rewrite.
+
+This is the only thing above the readers that has to be understood about any of them.
+*/
+restate :: proc(t: ^Tree) {
+ sync.atomic_store(&t.restated, true)
+}
+
+// Whether the tree has been restated since this was last asked, clearing it.
+taken_restated :: proc(t: ^Tree) -> bool {
+ return bool(sync.atomic_exchange(&t.restated, false))
+}
+
progress :: proc(t: ^Tree, nodes, bytes: u64) {
sync.atomic_add(&t.nodes_done, nodes)
sync.atomic_add(&t.bytes_done, bytes)
@@ -216,7 +264,7 @@ path :: proc(t: ^Tree, i: u32, allocator := context.allocator) -> string {
chain[depth] = cur
depth += 1
n := node(t, cur)
- if n.parent == cur || n.parent >= t.count {
+ if n.parent == cur || n.parent >= slots(t) {
break
}
cur = n.parent
@@ -224,6 +272,10 @@ path :: proc(t: ^Tree, i: u32, allocator := context.allocator) -> string {
sb := strings.builder_make(allocator)
for j := depth - 1; j >= 0; j -= 1 {
+ // Reading the flags first is what makes the name safe to read at all.
+ if .Used not_in node_flags(node(t, chain[j])) {
+ continue
+ }
name := node(t, chain[j]).name
if name == "" {
continue
diff --git a/walk/walk.odin b/walk/walk.odin
@@ -175,18 +175,20 @@ record :: proc(w: ^Worker, parent: u32, e: Entry) -> (index: u32, descend: bool,
n.parent = parent
n.name = scan.intern(&w.writer, e.name)
n.size = e.size
- // A walker reaches a child through its parent, so the link is never in doubt.
- n.flags = {.Used, .Settled}
+ // A walker reaches a child through its parent, so the link is never in doubt.
+ flags := scan.Node_Flags{.Used, .Settled}
switch {
case e.directory:
- n.flags |= {.Directory}
+ flags |= {.Directory}
descend = true
case e.symlink:
- n.flags |= {.Reparse}
+ flags |= {.Reparse}
descend = w.follow
case:
n.disk = e.disk
}
+ // Last, so a builder watching this tree never sees a node before its size.
+ scan.node_publish(n, flags)
return index, descend, true
}
