Zygo Blaxell [Sun, 11 Oct 2026 06:57:35 +0000 (02:57 -0400)]
rewrite: tie canonical-src consolidation to a non-zero ref-op-cost
rewrite.prefer-canonical-src was only safe together with a non-zero
ref-op-cost: unpriced, consolidation piles references onto canonical
extents up to refs-max and re-canonicalizes along a chain. Yet config
version 1 shipped it enabled with ref-op-cost = 0, the unsafe pairing,
and not the v0.11 behaviour that version 1 is meant to reproduce.
Remove the option. The equal-reach tie-break and the Plan B pivot now
run exactly when ref-op-cost > 0, so version 1 (ref-op-cost = 0) spreads
references as v0.11 did, and version 2 (ref-op-cost = 53) consolidates as
before. A config that still sets the key loads unchanged; the key is
ignored. config-parse keeps the name in its kind table.
Zygo Blaxell [Sun, 11 Oct 2026 01:44:55 +0000 (21:44 -0400)]
test/integration/07: wait for the deduped files to agree on a bytenr
The test VMs run with bg_reclaim_threshold set, and the block group that
holds the shared extent is often relocated just as bees exits. Read
mid-relocation, one file already points at the new copy and the other at
the old, and the test reports a failed dedupe that succeeded.
Poll for up to 60 seconds until both files report the same bytenr. A
failed dedupe never converges, so the check still catches it.
Zygo Blaxell [Sun, 11 Oct 2026 01:09:06 +0000 (21:09 -0400)]
config-v2: default rewrite.ref-op-cost to 53
Version 2 defaults prefer-canonical-src to yes, which is only safe with a
non-zero ref-op-cost: the tie-break concentrates references onto canonical
extents, and ref-op-cost is the term that prices moving them. With
ref-op-cost = 0, a references corpus run did about 70 times the
reference-redirect work of a build without the tie-break (56.7M vs 804K
redirects).
Use 53, the same weight as ref-cost and extent-cost: one rewritten
reference costs about one extent item. Version 1 keeps 0.
Zygo Blaxell [Sat, 10 Oct 2026 23:55:27 +0000 (19:55 -0400)]
fdcache: throw on open errors other than ENOENT
open_root and open_root_ino returned an empty Fd for every failure, so a
caller could not tell a deleted file from an I/O error, and the scan-next
executor skipped a dst ref that failed with EIO instead of aborting the
dst plan.
ENOENT stays a quiet empty Fd: deleted files and subvols are common, and
logging each one would flood the log. Every other INO_PATHS or openat
error now throws, and so does a validation failure (wrong inode, root, or
device). For a file with several paths, a failed path is remembered and
the rest are tried; the error is thrown only if none opens.
Zygo Blaxell [Sat, 10 Oct 2026 23:54:05 +0000 (19:54 -0400)]
roots: sleep before the first crawl state writeback
The writeback thread saved beespoint.ini as soon as it started, before
any crawler existed, and logged "Crawl state empty!" at every startup.
Sleep for the checkpoint interval first. A stop during the sleep still
flushes the crawl state.
Zygo Blaxell [Sat, 10 Oct 2026 23:07:14 +0000 (19:07 -0400)]
scan-next: abort a dst plan on any error but a missing file
The executor ran each dst plan under catch_all, which swallowed
Borrower::Dead along with everything else, and treated every failed
dedupe the same way: a DATA_DIFFERS aborted the dst plan, while the
ref-slice build hid every error from a ref's extent data fetch.
Apply one rule everywhere a dst plan executes:
- ENOENT means the ref's file is gone. Skip that ref and keep going
(plan_ref_enoent).
- DATA_DIFFERS is not an error. The refs come from the commit root,
so they lag live data, and a live change is expected. Keep going
and let verification count the ref if it survives.
- Any other error, and a read-only dst, aborts that dst plan
(plan_dst_abort). Other dst plans in the same ExtentPlan still run.
Zygo Blaxell [Sat, 10 Oct 2026 23:04:50 +0000 (19:04 -0400)]
extent-layer: skip hash table refs quietly in the block map
The hash table file is blacklisted so that bees never dedupes it, and
block_map_fetch skips every blacklisted ref. The skip logs a full extent
dump saying the crawler should not have reached the extent, which is true
of a temp file (the transid floor keeps the crawler off those) but not of
beeshash.dat, whose extents the crawler reaches like any other.
Remember the hash table's file id when it is blacklisted, and skip its
refs with their own counter, block_map_ref_hashtable, before the temp
file trap.
Zygo Blaxell [Sat, 10 Oct 2026 20:15:12 +0000 (16:15 -0400)]
test/integration/05: re-enable phase 10 as SubExtent-of-SuperExtent
Phase 10 built a SubExtent across both parts of a SuperExtent and was
disabled because the constructor rejects it. That rejection is
correct: such a range has no single bytenr and no btrfs operation that
produces it. Rewrite the phase to test what is valid now:
- a SubExtent inside either part reads that part's blocks, reports
two data blocks with hashes, and stays insertable;
- a SubExtent across the parts is rejected.
Add it_assert_repl_out_grep to check the REPL's output, where command
errors are reported, for the rejection.
Zygo Blaxell [Sat, 10 Oct 2026 20:15:12 +0000 (16:15 -0400)]
extent-tree: allow a SubExtent within one part of a SuperExtent
A SubExtent delegates bytenr() to its child, so it was forbidden over a
SuperExtent, which has no single bytenr. But a range that lies inside
one part of the SuperExtent does have one: it is that part's child,
narrowed. BeesExtent::subextent() now resolves such a range to a
SubExtent of the part's child at the offset the part maps to, so a
SuperExtent can be decomposed into its constituent SubExtents.
A range that crosses parts still throws. It has no btrfs counterpart;
data drawn from several extents has to be copied into one, which is
what a TempExtent or MaterializedExtent represents.
Zygo Blaxell [Sat, 10 Oct 2026 20:11:14 +0000 (16:11 -0400)]
filter: indent rule-building bodies with tabs
Nine lines in the dedupe, readonly-match and prealloc-match
parsing were indented with two tabs and eight spaces instead of three
tabs. Whitespace only.
Zygo Blaxell [Sat, 10 Oct 2026 20:11:14 +0000 (16:11 -0400)]
bees-config: log rewrite.candidate-max-bytes once
load() logs every key it reads, and candidate-max-bytes was then logged
a second time in pretty form, so startup showed the key twice: once as
a raw byte count and once as a size. Read it with get() so only the
pretty line is logged.
Version 2 lowered total-max from 100 to 10. On the same build, kernel
and corpus, 10 stopped at 64.6 GB freed while 100 reached 87.3 GB: a
low cap leaves every extent that needs more than ten operations
undeduped. The 10 run ended sooner only because it gave up on that
work.
plan: reject impossible coverings before the search
Every data region needs at least one dedupe or copy edge, since a copy
run never crosses the hole between regions, and every hole is already
one op. When that floor exceeds rewrite.total-max no covering exists,
but the search only found out after walking the whole extent, which is
O(V^2) in its boundary count.
With total-max = 10, a reference run on a disk-image corpus counted
582,604 searches ending with no covering under the limit (270 at
total-max = 100). Check the floor up front and count the rejection the
same way.
docs: document the refs_pending and pending_ref_* counters
Commit 8f596c838d5be453734c5ecd2dea309a792a8057
("verification: carry pending references in the verification ring")
added these counters without an entry in docs/event-counters.md.
verification: carry pending references in the verification ring
The record of references bees created that a resolve cannot yet report
had its own expiry: a counter of observed transid changes and a fixed
four-change lifetime. The verification tracker already answers the
same question -- how many transid changes must pass before the effects
of a dedupe are in the commit root -- with a ring sized by
loop.verify-delay, and it rotates on the same observation from the same
thread. Two mechanisms for one wait is one too many, and the fixed
lifetime was not operator-tunable where verify-delay is.
Record each created reference into the ring slot currently being
filled, and drop the slot's record when it retires, at the same moment
the dsts recorded into it are checked for deletion. A resolve unions
the record from every slot. BeesPendingRefs goes away; the ring's own
mutex covers the map alongside the extents and locks it already holds.
scan-next: keep our own dedupes' references visible until they commit
An extent that has just served as a dedupe src has gained references
that no LOGICAL_INO walk of the commit root can report until the
transaction commits. When that extent is then chosen as a dst -- it
arrives by hash match, so neither the crawler's transid discipline nor
the dst lock applies -- the plan is built from the short list, redirects
only the references it can see, and the extent survives the dedupe that
was supposed to free it. The verification tracker reports these as
failures. With resolve.commit-root every resolve walks the commit
root, so this happens at every src-then-dst transition inside one
transid: on a 129-ref synthetic corpus, 40 verify failures and 1.6 GiB
less recovered than the live-root run of the same binary. It is also
possible without the flag, because the kernel silently answers from the
commit root whenever it cannot attach to a running transaction.
The existing repair_refs() mechanism was meant to cover this by merging
the dst's reference list into the src's after each plan. Instrumenting
it shows it cannot: a dst reference deduped in N segments creates N new
src references at N different item offsets, and the donor carries only
the dst item's old offset, so at most one of the N is represented and
the rest are foreign entries every consumer skips. Two more gaps: srcs
outside m_src_bytenrs (the temp-file extents behind copy segments) got
no repair at all, and the repaired list did not survive the per-transid
cache clear, whose refetch can land in the window after the crawl
thread sees the new transid and before the kernel swaps the commit
roots, and so comes back one commit staler than the transid suggests.
Replace it with a record of the references bees itself creates. Every
successful dedupe walks the src file's EXTENT_DATA items over the
deduped range and records, per src extent, the (root, inum, offset) of
the new dst item -- the kernel creates one per src item overlapped,
each at the corresponding dst offset, which is the same key LOGICAL_INO
reports. refs_fetch unions the record into every result for that
bytenr, whichever tree the kernel walked.
Entries expire after four observed transid changes, counted, not
computed from transid values. The transid the crawl thread reads is
the generation of the root-tree leaf holding one subvol's item, which
moves only when an item in that leaf is rewritten; it sat still for
thirteen transactions in one run and then jumped, and a first version
of this change that stamped entries with its value expired 168 fresh
entries the moment the thread caught up. Counting changes is immune:
the first change after an add may only be the thread catching up, every
later one is a transaction the dedupe's has been followed by, and a
transaction is fully committed before the one after its successor can
begin, so the third change is proof and the fourth is margin.
repair_refs and merge_refs go away with their only caller. The
"recovered less space" observation in the docs and comments predates
this fix and is dropped; the comparison needs re-measuring.
scan-next: record why the ceiling hash erase can be one-way
Erasing a ceiling extent's hash cells cannot be undone: deleting
references can put the extent back under the ceiling, but its hashes are
gone and the crawler will not revisit it to reinsert them, because
removing a reference does not change the extent item's generation. That
is worth stating next to the erase, since it is the obvious objection to
it and the answer is not in the code.
An extent that reached the ceiling from a single subvol's references
crosses it again on the next snapshot, which multiplies the reference
count rather than adding to it, so the window in which it is usable
again is narrow and closes on its own. Where the references came from
originally-unique blocks there are other low-reference candidates to
dedupe against, at a bounded cost: with refs-max 9999, 15000 identical
copies collapse to two extents instead of one. Where they came from
another application's reflinks or snapshots the data was already shared
and bees had nothing to do with it.
scan-next: erase hash cells pointing at a ceiling extent
An extent at or above rewrite.refs-max cannot take another reference, so
it can never serve as a dedupe src again. Its block hashes stay in the
hash table regardless, and every later scan that shares one of them pays
a lookup and an extent resolve to rediscover that the extent is
unusable. Nothing ever clears this: the crawler advances past the
extent and will not return, because nothing about the extent changes.
Erase the cell instead. The candidate search already erases cells that
resolve into a gap between extents, and normalizes cells that point into
the middle of an extent; a ceiling extent belongs in the first category
rather than the second, since normalizing its address only preserves a
pointer to something that has permanently withdrawn from dedupe.
This erases only the hashes that actually surface in a lookup, which is
the complete set of hashes that cost anything -- a hash nobody looks up
is free to leave in place. It also needs no reference list, which
matters here because a ceiling extent has none to offer.
Telling a ceiling extent apart from a freed one needs the same
disambiguation the start-extent path needed, so the candidate gate now
asks refs_at_ceiling() as well, and counts the two separately.
Document the candidate event group, which was missing entirely.
scan-next: do not claim a ceiling extent was deleted
refs_fetch() suppresses the reference list of an extent at or above
rewrite.refs-max and reports it as having none, so that every caller
that checks for references treats it as unusable. That leaves an empty
reference list carrying two opposite meanings: the extent has no
references left and is gone, or the extent has more references than any
other on the filesystem and is never going away.
scan_next_plan_start()'s early exit read the first meaning
unconditionally. It recorded the extent with the verification tracker,
which is a claim that the extent should be deleted within
loop.verify-delay transid changes. A ceiling extent cannot be deleted
and was not deduped -- nothing was even attempted on it -- so the claim
always fails. Every scan of every ceiling extent therefore produced a
"verify FAILED" for an extent bees deliberately declined to touch, and
went on producing one on every later pass, since nothing about the
extent changes.
Record why the list is empty at the point where that is known, and have
the early exit ask. An extent at the ceiling is skipped silently and
counted as extent_refs_at_ceiling; it is just as inert as before, only
without the deletion claim. extent_zero_ref keeps its original meaning
of an extent whose references are actually gone.
The new state is a lazy field alongside m_refs: written by the layer
when it publishes the list, cleared by invalidate_refs() with it, and
empty until the refs are fetched, since "why is this list empty" has no
answer before there is a list.
docs: update thread option defaults for config version 2
thread.thread-max is 4 from version 2 onward, so --thread-factor no
longer feeds any default expression. Say so in both option entries, and
name the version 1 expression as the way back to a CPU-relative count.
Zygo Blaxell [Sun, 11 Oct 2026 00:25:57 +0000 (20:25 -0400)]
test/integration: pin free-min in the small rewrite tests
Version 2 raised rewrite.free-min from 50% to 128K in 941be6a85
("config-v2: update defaults for the scan_next extent scanner"). Tests 09,
10 and 14 build a 128K extent whose rewrite frees 32K, and their configs
do not set a version, so the planner now rejects the rewrite and each test
fails. Pin free-min at 50%, as test 24 already does.
config-v2: update defaults for the scan_next extent scanner
Version 2 takes a position on the defaults that the extent-scan work has
settled on:
thread.thread-max 4 (was one thread per CPU)
tempfile.compression zstd (was yes, i.e. zlib in practice)
state.hash.randomize-lru no (was yes)
rewrite.total-max 10 (was 100)
rewrite.free-min 128K (was 50%)
scan.extent.*.method 1 (was 0)
method = 1 makes scan_next_extent, and therefore filter chains, the
default; the key remains as a compatibility fallback for configurations
pinned to version 1 or v0.11. Version 1 keeps every old value, so
--config-version v0.11 still reproduces v0.11 behaviour.
docs/config-file.md states both the new default and the version-1 value
for each key, and the filter callouts no longer tell the reader that
method must be set by hand.
config-parse classified tempfile.compression as a bool, which it never
was: it accepts yes/no/empty/inherit or a compression type string. It
is free-form.
docs: add a configuration setup guide and make the filter prerequisites visible
A first-time user's experience with the scratch build found several
things the reference did not say, or said only where nobody would look:
- A configuration file should hold only the keys being changed. Copying
--show-builtin-config output into it produces duplicate-key errors as
soon as a section is added, and [config] is optional rather than a
required header.
- A [filter.NAME] section does nothing until a scan.extent.*.filter
chain names it (without the "filter." prefix), and no chain is
evaluated unless method = 1, which --scan-mode 4 does not set.
- Backslashes in name-pattern are consumed by value escape processing,
so a regexp \. has to be written \\. -- the regexp example in the
format reference itself had this wrong.
- hash.NAME.priority is an ordering for future multi-domain lookup and
csum-tree support, not a weight or a hardware capability probe.
- --show-config takes the filesystem root, and why.
Add a "Writing a configuration file" section with a minimal file, the
multi-line --option form, and worked examples for excluding by
extension, excluding a subvolume, and switching hash function, and add
callouts at the filter and method keys. Point at the filter_* event
counters and [log.filter] for confirming a rule matches.
Keys that version 2 introduces are defined in bees-config-v1.cc, at the
value that keeps v0.11 behaviour; bees-config-v2.cc states only those
whose version 2 default differs.
bees: explain what --show-config ROOT_PATH requires when it is unusable
--show-config takes the filesystem root, not a configuration file, and
a wrong argument used to fail with whatever errno surfaced first from
context setup (realpath, or an O_NOATIME open refused with EPERM), with
no hint about what the option actually wanted.
Check the cheap requirements up front -- the path exists, is a
directory, and is on btrfs -- and name the failed one. Permission
problems surface as the EACCES/EPERM from stat() or statfs(); bees
never reads the directory, so only search permission is needed. Wrap
the remaining checks in set_root_path (subvol id 5, FS_INFO) the same
way.
Every failure ends with the same statement of why a filesystem is
needed at all: the merged configuration depends on it through the
${ROOT}/${UUID}/${LABEL}/${FS_BYTES} interpolations, the local
configuration filename, and limits validated against the filesystem
block size. The statement is wrapped at 80 columns and written to
stderr directly, together with the specific failure in a single
insertion, so a command-line usage error is visible regardless of the
log configuration and its lines cannot interleave with other output.
filter: count verdicts and add the [log.filter] log category
There was no way to tell whether a configured filter rule ever decided
anything: the only trace of chain evaluation was buried in the planner
log at its highest level, which produces gigabytes of unrelated output.
Account for every chain evaluation at the memoized call site in
BeesFilterCache, which runs the chain once per extent per dedupe role
per planner pass. Each evaluation bumps filter_<role>_<verdict> and
filter_<role>_<verdict>_<rule>, where rule is the name of the rule that
ended the chain or the ACCEPT/REJECT terminal token when nothing did.
The counters cost a map lookup per evaluation and answer the common
question ("is my REJECT rule matching anything?") from the stats file.
Add a `filter` log category. INFO emits one line per evaluation with
the extent, role, verdict, deciding rule and chain spec; DEBUG adds the
existing condition-by-condition trace, built only when that level is
enabled.
hash: close lost-update window in flush_dirty_extent
flush_dirty_extent() copied the extent under its lock, released the
lock for the pwrite, then re-locked and cleared the dirty flag. A
set_extent_dirty_locked() that landed during the write window was
therefore erased: the on-disk copy predates the modification, and with
the flag cleared neither the writeback loop nor the shutdown flush
revisits the extent until something else dirties it.
This is benign in practice. The hash table is a lossy best-effort
cache, every hit is content-verified before dedupe, and the flush at
exit already accepts losing updates from Tasks still running during the
final pass. It is also easy to close.
Clear the dirty flag before taking the snapshot, while the extent lock
is still held. A modification during the write window sets the flag
again, so the extent is written on a later pass; the worst case is an
occasional duplicate extent write.
Do not restore the flag if the write fails. Re-marking the extent dirty
would retry the same write on every flush pass (a pass runs whenever any
hash update signals the writeback thread), so a persistently failing
write (ENOSPC on the hash table filesystem, for example) becomes a burst
of failing pwrites and logged exceptions per pass. Leave the extent
clean instead: the on-disk copy stays stale until the next update to
that extent dirties it again, the same best-effort loss accepted at
shutdown, and each failure is logged once per dirtying.
Rate limit failed attempts as well. flush_dirty_extents() only slept
after a successful write, so a slow pass over a table whose writes all
fail degenerated into back-to-back failures. Charge a failed attempt
the same 128 KiB slot as a successful one so the failure rate is bounded
by the same writeback rate limit.
roots: stop polling on planner lock-contention restarts
scan_one_extent_item returned true for every Borrower::Dead, and the
scan task lambda responds to true with Task::current_task().run() —
an immediate unconditional self-reschedule. Planner tasks therefore
never actually waited on the Exclusion rendezvous that try_lock had
established for them: they polled. At endgame, when the surviving
work is a few overlapping ref clusters, four such tasks can occupy
the entire worker pool with retry churn (measured at ~55k restarts/s,
borrower_dead_reacquire=332M in one stalled run) while the dedupe
rate collapses.
Self-reschedule only for limited() restarts (hash insert conflicts),
which genuinely have no rendezvous. For lock contention, return
false and let the rendezvous wake the task when the lock's owning
task completes — the retry rate becomes bounded by the winner's
progress instead of by how fast the loser can spin.
An alternative was tried first: parking waiters on the Exclusion
itself and waking on final lock release (with both wake-all and
wake-one variants). Both livelocked precisely because of this
polling — the planner tasks never consumed their wakeups, and the
parked-waiter bookkeeping interacted badly with the retry storm.
Removing the poll attacks the actual defect.
task: wake one Exclusion waiter per release, not all of them
Waking every parked waiter on each final release turned out to be
self-amplifying: a woken task's failed batch reacquire transiently
takes and releases locks (including the peek's lost-race case, which
takes a lock only to drop it), every such release re-broadcast a
wake to all waiters of that lock, and each of those wakeups caused
more transient takes. Four contending planner tasks sustained this
cycle indefinitely — a livelock retrying the batch reacquire at
~55k/s (borrower_dead_reacquire reached 332M) with zero dedupe
progress, where the pre-parking code made progress because wakes
were bounded by task-completion frequency and scheduled in sorted
task-id order.
Wake exactly one waiter per release instead. Liveness is preserved
because a woken task retries its entire memoized lock set: any lock
it acquires and then releases on the way to failure or completion
hands a wake onward to that lock's next waiter, so parked tasks are
served one release at a time instead of racing in synchronized
rounds.
bees: consume a token in RateLimiter is_ready log guards
RateLimiter::is_ready() reports token availability without consuming
anything, so a bare `if (limiter.is_ready()) log` never throttles:
the balance never goes negative and the guard is always true. The
borrower contention lines and the crawl temp-transid hold report all
used the bare form; a full-corpus run logged 2.87M "memo reacquire
contention" lines through a 10/s limiter that was doing nothing.
Follow is_ready() with borrow() so each emitted line spends a token
and the limiter engages.
borrower: update rendezvous comments for Exclusion waiter parking
Exclusion contenders now park on the lock's waiter list and wake on
final release, not on the owning Task's post-exec queue. Update the
Borrower documentation that described the old mechanism.
task: park Exclusion waiters on the lock, wake on final release
A Task that lost try_lock was appended to the owning Task's post-exec
queue and rescheduled whenever that Task finished an execution. That
wakes every waiter at once, and it fires at the wrong times: a planner
task that restarts wakes its whole waiter herd on every iteration, and
a move_lock handoff chain wakes all waiters at every intermediate task
completion while the lock is still held. At endgame, when the
remaining work is a few highly-shared ref clusters, these spurious
wake-all events feed a retry storm in which the woken tasks mostly
fail, requeue, and wake each other again.
Park waiters on the Exclusion itself instead. The owner token
(ExclusionOwner) is shared by all ExclusionLocks of one acquisition;
when the last lock is released, its destructor wakes the parked
waiters via Task::run(). A move_lock retag installs a replacement
owner, so the old owner's destructor sees a live successor and wakes
nobody — waiters sleep through handoffs and wake exactly when the
lock is free. Waiters are deduped by task id, so a task that dies
repeatedly on the same lock parks once.
The Exclusion's mutex, owner and waiter list move into a shared
ExclusionState so outstanding locks and parked waiters survive
destruction of the Exclusion object itself. Owner references are
always dropped after the state mutex is released — a shared_ptr
returned by weak_ptr::lock() can be the last reference, and
~ExclusionOwner takes the same mutex (the initial version of this
change deadlocked test_exclusion exactly that way).
borrower: make failed batch reacquires ordered, side-effect-free, quiet
At endgame the only remaining work is a handful of highly-shared ref
clusters, and every planner task restart wakes the whole post-exec
waiter herd of the task that finished. Each woken task re-ran the
batch reacquire, taking memoized locks one by one until one failed,
then releasing them all — knocking over the locks the other woken
tasks were about to succeed on. Two tasks whose two-lock memos
overlap in opposite orders can ping-pong this way for minutes,
re-waking their full waiter sets on every iteration. A full-corpus
run logged 4.36M "memo reacquire contention" lines (64% of the log)
in a 13-minute tail during which the dedupe rate collapsed and CPU
burned on retry churn and log formatting.
Three changes to the batch reacquire in the Borrower constructor:
- Sort the memoized set into canonical (pointer) order, so tasks with
overlapping memos contend on their lowest common Exclusion first,
forming one queue on one lock instead of a swap cycle.
- Peek the whole set with Exclusion::locked_by_another before
acquiring anything. A wakeup that cannot proceed now touches only
the failing Exclusion (to establish the restart rendezvous) and
disturbs no other locks.
- Rate-limit the contention log line to 10/s. The
borrower_dead_reacquire counter is unconditional as before; the
pass-2 race path logs under its own limiter as "memo reacquire
race" so the two causes stay distinguishable.
task: add Exclusion::locked_by_another, a side-effect-free peek
Callers that batch-acquire several Exclusions currently discover
contention by acquiring locks one at a time until one fails, then
releasing everything. The transient take-and-release perturbs locks
that other contenders are concurrently probing, cascading their
failures.
Add a peek that reports whether an Exclusion is owned by a live Task
other than the caller, without acquiring and without establishing a
rendezvous. The answer can be stale by the time the caller acts on
it, so callers must still handle try_lock failing (or succeeding)
after a peek.
scan-next: compose the plan tree from the searched edges
Variant "edges" of the compose/search reconciliation comparison.
Carry each selected edge's used dst sub-span through ChosenPlan
(m_selected_spans, index-aligned with m_selected_matches) and hand
both to scan_next_compose_plan_tree, which now walks the edge spans
instead of re-deriving slices from the matches' full dst spans. The
edges say exactly which dst bytes each match serves, so the composer
emits the slices the search validated verbatim — closing the DP-slice
vs compose-emission mismatch that fired the once-only compose trap on
dst-overlapping selected matches. The compose-time trap stays as the
final invariant check; it should now never fire.
The match-alone sort in scan_next_try_build_dst_plan is removed: it
would break the match/span index alignment, and the selector already
returns both sorted by span begin (joint permutation sort).
plan: report the dst sub-span of each selected edge
The covering search's result reported only match indices, discarding
the dst sub-span each edge actually used. When selected matches
overlap in dst space that information is not recoverable downstream:
scan_next_compose_plan_tree re-derives slices with a sorted-match
sweep and can emit from a different match, or at different boundaries,
than the search validated — the source of the residual once-only
compose-trap throws (259 in a full-corpus run).
Replace PlanSearchResult's index vector with PlanSearchEdge records
carrying the match index plus the used dst span. The greedy fallback
records its [pos, best_end) step directly; the exact DP recovers the
span from the src slice already stored in the back-trace edge (the
slice is src_begin + (a - dst_begin), so the inverse is exact).
Behavior-neutral: the one consumer keeps reading only the match
index. Follow-up commits make composition consume the spans.
docs: document the plan_src_edge_blocked and plan_src_overlap counters
Commit 66f12b67e54f19cf9e72e8b2c2e97576b32e63eb
("plan: enforce the src once-only rule inside the covering search")
added these counters without an entry in docs/event-counters.md.
plan: enforce the src once-only rule inside the covering search
Teach the covering search the no-reuse-src-regions rule instead of
throwing after plan selection:
- PlanSearchMatch carries the src identity (bytenr, or node address
with the top bit set for synthetic extents) and src interval.
- The exact DP refuses a dedupe edge whose src slice overlaps a slice
already consumed along the path on the same src key
(plan_src_edge_blocked counts refusals). The check walks the
state's back-trace, O(path) per tentative edge. Dominance pruning
still ignores src usage, so this is an admission heuristic, not an
exact src-aware search: a pruned state could in principle have
avoided a later conflict.
- The greedy fallback keeps a live set of absorbed matches and picks
the farthest-reaching one whose src slice is still free, instead of
the src-blind running argmax.
Because the search admits src-overlapping matches whose used slices
are disjoint, the whole-interval pre-compose check would false-fire;
the once-only trap moves into scan_next_compose_plan_tree, checking
the src slice of each emitted dedupe child (the exact bytes sent to
the kernel) and throwing on overlap.
This supersedes the whole-interval throw-and-skip added by 0913df4a45 "scan-next: enforce the src once-only rule at plan
composition" (removed here). A three-way comparison on
the same corpus showed the throw-and-skip variant discarding 640849
otherwise-buildable plans and freeing 28% less space at equal IO than
the pre-enforcement baseline, while enforcing inside the search freed
20% more space at equal IO than that baseline and finished the run
fastest of all variants (77.6M edges refused, only 259 residual
compose-trap throws from DP-slice vs compose-emission mismatch on
overlapping dst matches - a follow-up refinement).
Unit-test harness: make_inputs gives each synthetic match a distinct
src key with a src interval mirroring its dst interval, so existing
single-src-per-match scenarios are unaffected by the new check.
roots: name the temp files behind a temp_transid crawler hold
An integration run livelocked in the endgame: the 128K crawler sat
held below a temp file transid for hours with an empty work queue and
all workers idle. The hold-release path is already in place -- the
tempfile pool's checkin handler calls reset(), which erases the
context's temp_transid entry when the pool handle is returned -- so a
persistent hold with idle workers means some live reference (a
BeesTempExtent holds a copy of the pool handle) kept the temp file
checked out of the pool, and the entry could never be erased. No new
dedupe work will ever arrive to reset it: the crawler waits on the
temp file, and the temp file waits on work the crawler cannot
produce.
The log did not identify which temp file held the crawler or what
retained it. Add BeesContext::temp_transid_report() and log the held
(fid, transid) pairs, rate limited to once a minute, when the hold
actually binds the crawl window. Debug level: a hold is normal while
dedupe is in flight and needs no operator action; the report exists
so the retainer of a stuck temp file can be identified from the log
the next time the endgame livelock appears.
tempfile: erase the temp_transid hold in the destructor
note_data_transid() registers the tempfile's transid in
BeesContext::m_temp_transid so the extent crawler cannot advance into
the range where the tempfile's extents are still acquiring refs.
reset() erases the entry at the start of each mutation cycle, but the
destructor did not: a BeesTempFile destroyed while holding data (a
worker thread torn down, or an exception unwinding past the dedupe
that would have reset it) left its entry in the map forever. The
dead entry pins temp_transid_min() at that transid, and the crawler
stalls permanently behind a file that no longer exists
(crawl_temp_transid_hold counts the held polls).
Erase the entry in the destructor alongside the fd-cache and
blacklist cleanup.
demote duplicate-scan and temp-file-ref log events to debug level
The crawl_extent_dup duplicate-queue drop and the block_map_fetch
temp-file ref skip are diagnostic events: bees handles both cases
itself and operators do not need to take action, as they might with
a warning. Log them at debug level instead of warn.
scan-next: enforce the src once-only rule at plan composition
Each src block may be referenced at most once across the dedupe edges
of a single dst plan. Overlapping src references within one plan
stack multiple new refs onto the same physical blocks, exploding
reference counts on extremely common data. The rule has existed as a
design constraint but had no enforcement: the recent prefer-canonical-
src pivot bug produced plans that violated it freely, and only the
kernel's byte comparison stopped them (as "NO Dedup!" rejections).
Add scan_next_enforce_src_once_only(), called from
scan_next_try_build_dst_plan() on the chosen match list before the
plan tree is composed. It groups the selected matches' src intervals
by src extent (bytenr when present, node identity for synthetic
extents) and checks each group for pairwise overlap. On violation it
logs the full match table, bumps the plan_src_overlap counter, and
throws, so a violating plan is rejected before it can reach the
kernel and the callers' existing exception handling logs the trace
and skips the extent.
Every observed violation of the rule has also been a planner bug that
paired a dst with data the src never had, so this doubles as an early
loud failure for any future match-transposition defect.
scan-next: restrict prefer-canonical-src pivot to strict whole-extent duplicates
The pivot in BeesStartAsSrcPlan::finalize() re-centers the dedupe star
on a higher-ref candidate, and build_onto_center() then transposes the
other dsts' matches onto the center by swapping only the src extent
identity, keeping the start-extent offsets. That transposition is
sound only when the center is byte-identical to the start at the same
offsets over the start's whole extent.
The eligibility test accepted any candidate whose own extent was
covered by a single dedupe op against the start. A small candidate
fully matched by a window inside a larger start (or a larger candidate
covering the start elsewhere) qualifies under that test without
satisfying the transposition's premise. Every match transposed onto
such a center indexes bytes the center never had; the resulting plans
execute as dedupe requests the kernel rejects with
BTRFS_SAME_DATA_DIFFERS ("NO Dedup!"), deterministically, on data
with self-similar or repeated content where windowed whole-candidate
coverage is common. Diagnosed by stamping block maps with build
sequence numbers: bad matches carried a src map built under the start
extent's bytenr while naming the pivot center as m_src.
Tighten the test to the strict form: equal logical sizes and a
full-length match anchored at offset zero on both sides.
A dedupe miss (FIDEDUPERANGE returning BTRFS_SAME_DATA_DIFFERS) means
the planner paired two ranges whose data does not match. Today the
only record of that event is the one-line "NO Dedup!" log entry,
which names the file offsets but nothing about how the planner
composed the pair. Field reports of dedupe failures on identical,
inactive files therefore arrive with no actionable planner state.
Call BeesTracer::trace_now() on the miss path so the caller's live
BEESTRACE stack is dumped at the moment of the miss. Unlike the
unwind-time dump, this needs no exception, so callers that swallow
the false return still produce a trace. Misses are rare, so an
unconditional dump per miss is cheap.
Enrich the stack that dump walks with planner state that was
previously invisible:
- scan_next_execute_pairs: one frame per pair, with the batch index
and count, so the dump identifies which pair of the batch failed
and how far the batch had progressed;
- scan_next_execute_dst_plan: the plan's cost accounting (op counts
and byte totals), so the dump can be compared against what the
cost model predicted;
- scan_next_sweep_join_pairs: the current dst ref and sweep cursor,
for throws raised while pairs are being manufactured.
Together with the existing lazy plan-tree and materialized-tree trace
frames, every NO Dedup event now emits the full planner context as
long-term field data collection infrastructure.
extent-layer: enforce that block map hash regions are dense
A block map is an offset index of regions; within a region the hash
vector is dense, index k being the block at m_begin + k *
BLOCK_SIZE_SUMS. Unreachable and zero blocks are not holes inside a
region, they are ranges the packed regions do not cover. Every
consumer depends on that: tree_slice_block_map converts a byte offset
to a vector index, visible_hashes advances one block per hash and
publishes an address for each, and the matcher's extension loop walks
two regions in lockstep by index.
Neither end enforced it. The producer built a data region's vector
with a conditional push, so a data block without a hash would be
skipped rather than represented, shifting every later hash down one
block. The slicer then clamped its upper bound to the vector's actual
size, which turns a short vector into a short result instead of an
error -- and a short vector does not drop hashes, it moves them, so the
clamp converts a detectable inconsistency into a silent wrong answer
that surfaces much later as a FIDEDUPERANGE rejection.
Make the invariant explicit at both ends: the producer throws if a data
block has no hash and checks the finished vector against the region's
block count, and the slicer throws rather than clamping when the
computed subrange would run past the end. Both name the extent, so a
violation identifies itself instead of propagating.
No violation has been observed yet -- in the current producer a data
block always receives a hash in the same statement that sets its state.
These are traps for an invariant that was being relied on without being
stated.
extent-layer: merge repaired refs through the node interface
repair_refs() reached for the concrete node type to read and publish
m_refs:
auto *node = dynamic_cast<BeesBtrfsExtentNode *>(extent.extent_sp().get());
The read never needed it -- refs() and refs(BeesExtentLayer &) are both
virtual on BeesBaseExtentNode. Only publishing a merged list had no
base-class expression, so add one: merge_refs() appends refs whose
(root, inum, offset) the node does not already hold, under the node's
own lock, and returns how many were added. Node types with no btrfs ref
list inherit a no-op, which is the right answer for them rather than
something a cast has to exclude by returning early.
Constructing the ref nodes stays in the layer. The donors describe file
ranges but their nodes still name the dst extent they came from, so each
one is rebased onto this extent first, and setting a ref node's identity
is the layer's privilege -- it is the friend that refs_fetch() uses for
exactly this.
Commit 296bceeee2085aba7919cb2a967519bc6e80554c
("scan-next: do not map a dedupe pair across a gap in the src refs")
added the counter without an entry in docs/event-counters.md.
scan-next: do not map a dedupe pair across a gap in the src refs
BeesExtentSlice::refs() walks forward from the slice start and is
permitted to skip regions that carry no ref, so the first leaf can begin
after the cursor. scan_next_sweep_join_pairs assumed it never does:
const auto src_file_begin = src_ref.file_begin() + cursor - src_ref.begin();
With a gap, "cursor - src_ref.begin()" is an unsigned subtraction that
wraps, and adding it moves src_file_begin backwards by the size of the
gap. The result is a plausible-looking file offset that points at data
the matcher never examined, so the pair is built against the wrong
bytes and FIDEDUPERANGE rejects it. covered was also set on that path,
so the region with no src ref was reported as covered.
This was dormant: an instrumented baseline run over the reference
corpus recorded zero gaps in a million dedupe operations. It stopped
being dormant once extent_data_fetch began leaving foreign refs
undetermined. Callers skip refs with no geometry, so refs that used to
resolve -- to the wrong extent, silently -- now leave holes in the ref
coverage instead, and holes are exactly what produces a leaf beginning
after the cursor. Measured on the same corpus: 40 gaps in 920k dedupes
with that change alone, and the NO Dedup rate rose from 17 to 45.
A gap means there is no src ref for [cursor, src_ref.begin()), so the
plan cannot be executed as planned. Abandon it the same way a vanished
ref is abandoned, and count it as plan_src_gap.
roots: log both extents when a duplicate scan is dropped
crawl_extent_dup recorded that a duplicate was dropped but nothing
about what was dropped or what it collided with, which discards the
informative part. The duplicates seen on the reference corpus
disagreed about the extent itself:
Task ID 19464 32M_2889dba000_12M waiting 1473s
Task ID 27833 32M_2889dba000_20.121M waiting 1245s
Same tier, same bytenr, different sizes -- two scans built from
different views of what extent lives at that address, which is a
different fault from one extent queued twice from a single view. A
counter cannot tell those apart.
Carry the identifying detail in the claim and report both sides:
crawl_extent_dup: extent already queued for scanning
in flight: tier 32M bytenr 0x2889dba000 size 12M gen 1611 queued 1473s ago
dropped: tier 32M bytenr 0x2889dba000 size 20.121M gen 1618 queued 0s ago
The claim holds scalars rather than a BeesExtent, so it does not pin a
node in the layer cache for the lifetime of the scan.
roots: start each crawl window one transid past the last
Both ends of a crawl window are inclusive: find_next_extent rejects
extents below m_min_transid as crawl_gen_low and above m_max_transid as
crawl_gen_high. Successive windows were built as [min, max] followed by
[max, next_max], so every extent whose generation landed exactly on a
window boundary was scanned twice -- once as one window's upper bound
and again as the next window's lower bound. On the reference corpus
that is 519 restarts worth of boundary transids.
The overlap was load-bearing while the crawler could reach the open
transid: an extent created at gen == max_transid during a sweep, at a
bytenr the cursor had already passed, would be missed by that window,
and a disjoint next window would never look at that transid again.
It is not load-bearing now. temp_transid_min() is floored at the
current transid, so effective_transid_max() is always strictly below
it and every window covers only committed transactions. A committed
transaction's extent set cannot grow, so everything at the window's
upper bound already existed when the sweep started and the sweep will
reach it. The open transid is the only one whose membership in the
scan set is in doubt, and it is now never scanned.
Start the next window at max + 1. The comment records the dependency
so the overlap is restored if that floor ever goes away.
Commit fe1bdaaae0624b53ce95bae083dfe0a2fcf743aa
("roots: do not queue the same extent twice for scanning")
added the counter without an entry in docs/event-counters.md.
roots: do not queue the same extent twice for scanning
A task report from a healthy run showed 22 bytenrs carrying more than
one distinct scan Task, some three deep and waiting over twenty
minutes:
Task ID 19464 32M_2889dba000_12M 2x 1473.09s wait
Task ID 27833 32M_2889dba000_20.121M 1x 1244.94s wait
Task ID 29193 32M_2889dba000_20.121M 1x 1211.26s wait
Successive crawl cycles re-derive overlapping extent sets, so an extent
that has not finished scanning is queued again on the next pass. The
duplicate cannot make progress -- it parks on the same Exclusion the
first Task holds -- but it is not harmless: each one holds a crawl
progress hold, and a crawler only reports itself idle once
m_state.begin() catches up to m_state.end(). Duplicates that can never
run therefore keep the crawler permanently non-idle, which is one way
loop.exit-when-finished fails to fire on an otherwise finished
filesystem.
Claim the bytenr before creating the Task and drop the extent if it is
already claimed, releasing the claim when the Task and its closure
copies are destroyed. crawl_extent_dup counts the drops.
Note the differing sizes at one bytenr above: the two Tasks were built
from different views of what extent lives at that address, so this also
stops two disagreeing descriptions of one extent being scanned as if
they were separate work.
extent-layer: report temp file refs instead of quietly skipping them
Two corrections to the temp file handling.
A ref into a temp file reaching block_map_fetch() is not a routine
condition to be counted and dropped. The crawler is held below live
temp file transids precisely so this cannot happen, so an occurrence
means that bound failed and bees is looking at an extent it should
never have reached. Log it with the full extent dump. Skipping is
still the right action -- the data is not ours to hash -- but it is now
impossible to miss, and the dump identifies the extent that got
through. Left as a warning rather than a throw only because a real
extent legitimately carries a temp file ref between materialization
and the reset that drops it; if this proves quiet in practice it should
become an exception.
temp_transid_min() must never return zero. An empty registry does not
mean there is nothing to avoid: the scan is running now, and a planner
can materialize a temp file before the next transid bump, creating
extents in the current transaction. Returning zero lifted the bound
entirely and allowed the crawler into the transaction that created
them, which is the case the bound exists to prevent. Floor it at the
current transid, so with nothing registered the crawler still stays
strictly below the running transaction, and a registered temp file only
lowers it further.
docs: document the crawl_temp_transid_hold event counter
Commit e1140bd74c9a124efa078db19610dc289ef403b0
("roots: hold the extent crawler below live temp file transids")
added the counter without an entry in docs/event-counters.md.
roots: hold the extent crawler below live temp file transids
A temp file's writes create ordinary btrfs extents, so an extent scan
picks them up like anything else once a temp file outlives a
transaction boundary and reaches the scan queue. Skipping their refs
during block map construction stops bees hashing recycled data, but it
does not address the earlier problem: those extents are still being
built. Refs are added to them as the dedupes consuming the temp file
complete, so an extent scanned mid-construction has an incomplete ref
list. It fails as a dedupe dst, and offers an incomplete src ref map
to whatever does match it.
loop.transid-age-min can paper over this by making every extent wait a
fixed number of transids before it is eligible, but that is a blunt
instrument: it delays every extent on the filesystem to avoid a
condition that applies to a handful, and the operator has to guess a
number that is large enough.
Connect the two directly instead. A temp file samples transid_max() at
its first write after a reset -- the earliest transaction its extents
can belong to -- and publishes it to the context, keyed by BeesFileId
like the blacklist it already registers in. effective_transid_max()
holds every crawler strictly below the earliest such transid. The
entry is dropped in reset(), which the pool's checkin handler calls as
soon as the borrowing planner is done, so the bound applies only while
a temp file actually holds data and costs nothing otherwise.
docs: document the block_map_ref_tempfile event counter
Commit f7d5d91e96f5a68270af3173ee44091ba292abed
("extent-layer: do not hash refs that point into a temp file")
added the counter without an entry in docs/event-counters.md.
extent-layer: do not hash refs that point into a temp file
A temp file's extents are ordinary btrfs extents, so an extent scan can
pick one up like any other. That happens when a temp file outlives a
transaction boundary and reaches the scan queue, and it was observed on
a 176G test corpus: an extent entered the scan queue as a start_extent
whose only ref named a temp file inode at offset 0x1000, the reserved
first block temp files are truncated back to. The same ref claimed
19.699M of an 8.824M extent, the inconsistent-ref-coverage shape.
Refs into temp files do not stay valid. resize() truncates the file
back to its reserved block and the space is rewritten with unrelated
data on the next use. No extent Exclusion covers that: the mutation is
a truncate of a file, not a dedupe of the locked extent, so holding the
extent lock does not prevent the refs from going stale underneath.
block_map_fetch then preads whatever the next user of the temp file
wrote and publishes those hashes under the scanned extent's bytenr.
Every temp file is already registered on the blacklist by its
BeesFileId, so recognising these refs costs a lookup. Skip them in the
data-coverage pass: they add no coverage, and pass 2 does not pread a
range with no usable ref.
extent-tree: trap block map construction on a retired dedupe dst
Once a dedupe redirects a dst extent's refs to the src, the dst must
take no further part in dedupe: its cached ref list names file ranges
another extent now owns. Building a block map from it preads through
those refs, hashes another file's data, and publishes the result under
this extent's bytenr, where it waits to be matched against something it
does not resemble.
Nothing about that is loud. Every stale ref still resolves -- there is
a real EXTENT_DATA item at that (root, inum, offset), just belonging to
a different extent -- so the failure surfaces much later as a kernel
byte-compare rejection ("NO Dedup!") with no path back to the extent
that produced the bad hashes.
Mark the dst retired when it is evicted from the cache layers, and
throw if anything reaches block_map_fetch() on a retired extent.
Eviction already prevents new lookups from finding it; the flag covers
holders that obtained a shared_ptr before retirement, and converts a
silently wrong block map into a backtrace naming the caller.
Retirement is deliberately one-way and deliberately does not drop the
ref list: the verification cycle still reads those refs to confirm the
extent went away.
Commit fc23c4e8ac43ec2816a6d93329dd9b84ddf22f6b
("extent-layer: stop dedupe from leaving refs that describe other extents")
added the counter without an entry in docs/event-counters.md.
extent-layer: stop dedupe from leaving refs that describe other extents
A BeesRef is a (root, inum, offset) tuple; its geometry is fetched
lazily from whatever EXTENT_DATA item sits at that file offset. A
successful dedupe redirects the dst file range to src, so from that
moment every dst ref names a range another extent owns. Nothing
noticed. extent_data_fetch adopted the foreign item wholesale --
including overwriting m_bytenr -- and propagated its ram_bytes into the
dst extent as that extent's logical size. block_map_fetch then pread
through those refs and published hashes for data the extent does not
contain, and the planner paired dst ranges against src ranges that hold
something else. The kernel's own byte compare rejected the result, so
the visible symptom was "NO Dedup!" and an abandoned plan, several
extent-tree constraint failures away from the cause.
Three changes, which only work as a set:
Refuse foreign refs. extent_data_fetch now compares the fetched
file_extent_bytenr against the owning extent and, on a mismatch, leaves
the cached fields undetermined instead of adopting them. Callers
already skip refs whose geometry is not determined, so a redirected ref
reads as absent rather than as a lie.
Retire the dst. A dedupe dst must take no further part in dedupe, so
evict it from every cache layer once its hashes are dropped. Its
BeesExtent survives in the verification tracker with the ref list intact
for the delayed removal check and no block map to pay for, which is also
where the donor refs for the next part come from.
Repair the src. Invalidating the src ref list is not enough on its own:
LOGICAL_INO answers from the commit root whenever it cannot attach to a
running transaction (btrfs_attach_transaction returns -ENOENT, and
find_parent_nodes then sets search_commit_root and skips delayed refs),
so a dedupe that has not reached a commit can be invisible to a refetch,
with nothing in the result to say so. bees knows what it just created,
so repair_refs() adds the redirected dst refs to the src list directly.
Donors that btrfs already reported are skipped as duplicates, and donors
belonging to a different src are harmless because the first change
leaves them undetermined.
The guard alone would shrink ref lists and cost dedupe coverage; the
repair alone would add refs the old fetch path could still misresolve.
A 4h45m run over a 176G corpus on the reference test filesystem, one
million dedupe operations, produced 17 "NO Dedup!" events, 30
inconsistent-logical-size failures and 5 self-overlapping range pairs.
Reading both sides back at failure time showed 15 of the 17 differing in
95-99% of their bytes from the first byte or near it -- unrelated data,
not misaligned data -- and none of them compared equal on readback, so
these were not races between the compare and the ioctl.
Zygo Blaxell [Mon, 24 Aug 2026 19:20:34 +0000 (15:20 -0400)]
test: rebuild the test programs when localconf changes
../localconf overrides CC, CXX and CCFLAGS but was not a prerequisite of
anything test/Makefile builds with them, so editing it recompiled
nothing and left the tree able to link objects from two compilers.
Under -flto that surfaces at link time as "plugin needed to handle lto
object", which names neither localconf nor the compilers.
test/Makefile gains BUILD_CONF and uses it wherever ../makeflags
appeared in a prerequisite list, including the link rules, and the .dep
rules that previously depended on neither file. localconf is optional
and has no rule to create it, so $(wildcard) names it only when it
exists.
The same change to lib/Makefile and src/Makefile is already on next.
Only test/Makefile is left here: next carries a much smaller set of test
programs, so its version of this file converted only the rules that
exist there, and the rules this branch adds still needed converting.
Verified that an unchanged tree still does no recompiles, that touching
localconf now rebuilds, and that `make test' and `make build-check' both
pass afterwards.
Zygo Blaxell [Sun, 23 Aug 2026 05:20:07 +0000 (01:20 -0400)]
config: cap rewrite.read-size at the maximum data extent size
rewrite.read-size sets the buffer for source-side reads in the
materialize copy loop and the block-map hashing pass. It was validated
only for being a positive multiple of the sectorsize, so nothing stopped
an operator from asking for a buffer larger than any transfer that could
usefully be made with it.
btrfs will not create a data extent larger than 128 MiB, so a copy
buffer bigger than that cannot produce one larger extent: the write is
split into 128 MiB extents regardless, and the surplus only holds dirty
memory, once per worker thread. Preallocated extents can reach 256 MiB
(BLOCK_SIZE_MAX_EXTENT, for the fallocate limit introduced by kernel
commit 24542bf7ea5e4fdfdb5157ff544c093fa4dcb536), but a prealloc extent
cannot be replaced by a single write either, so that larger number is
not a useful buffer size.
Add BLOCK_SIZE_MAX_DATA_EXTENT for the 128 MiB figure, reject anything
above it at config load next to the existing alignment check, state the
maximum in the built-in config comment, and explain in docs/config-file.md
why the useful ceiling is the smaller of the two extent limits.
The cap also keeps the copy loop's writes under BLOCK_SIZE_MAX_TRANSFER,
which pwrite_or_die() enforces.
Keys that version 2 introduces are defined in bees-config-v1.cc, at the
value that keeps v0.11 behaviour; bees-config-v2.cc states only those
whose version 2 default differs.
Zygo Blaxell [Wed, 5 Aug 2026 16:38:50 +0000 (12:38 -0400)]
docs: document the plan_snap_extra event counter
Commit 6dc9fb00061e3b864805056b9e86675c2fbcb046
("scan_next: price snapshot metadata unsharing in the space debt")
added the counter without an entry in docs/event-counters.md.
Zygo Blaxell [Wed, 5 Aug 2026 16:38:50 +0000 (12:38 -0400)]
scan_next: price snapshot metadata unsharing in the space debt
Charge the snapshot-sharing undercharge in the do-nothing cost model.
refs_added credits one removed item per rewritten ref, but when k refs
through k subvols of one snapshot family are a single shared metadata
item, replacing the group writes k*F private items and removes only
the one shared item (freed by btrfs once the last sharer replaces its
ref) — the per-logical-ref accounting is short by exactly k-1 per
group, independent of F. Without the charge the planner performs
dedupes in snapshotted subvols whose physical win is smaller than the
metadata pages they unshare.
New CostReport::m_snap_extra carries the per-dst sum of (k-1) over
(cluster, inode, offset) ref groups, priced in space_debt() as
snap_extra * ref-cost * rewrite.snapshot-sharing. The term is a
per-dst constant (no F or op-mix dependence), so the state-collapse
invariant holds and the covering search is unchanged; it also makes
orientation snapshot-aware — a snapshot-family extent is cheaper as
src than as dst. Both debt paths marshal it through the shared
scan_next_debt_fields builder; the Plan B per-dst do-nothing gate and
aggregate pick it up, and the prefer-canonical-src pivot swaps the
start's and center's contributions along with their roles.
rewrite.snapshot-sharing is the expected ratio of subvol metadata
sharing: 1.0 (default) = undiverged snapshots, exactly cancelling the
invalid removal credit; 0 disables the term and the cluster-map work;
outside [0,1] scales for unusually expensive or cheap metadata. Refs
of snapshots that diverged past matching vanish from the dst ref list,
so they stop being charged with no special handling.
The plan: line grows a trailing 'snap <N>' field (appended, so
analyze-bees-log.sh parsing is unaffected), documented in running.md.
Unit tests pin the worked example at sharing 1.0 / 0 / 10, the
disabled path, and shared-builder carriage of snap_extra.
Keys that version 2 introduces are defined in bees-config-v1.cc, at the
value that keeps v0.11 behaviour; bees-config-v2.cc states only those
whose version 2 default differs.
Zygo Blaxell [Wed, 5 Aug 2026 16:31:07 +0000 (12:31 -0400)]
docs: document the layer_snap_cluster_build event counter
Commit 327fd7c4212a929202aee5036f0b27fa8e3beaf8
("scan_next: detect snapshot families for the sharing cost model")
added the counter without an entry in docs/event-counters.md.
Zygo Blaxell [Wed, 5 Aug 2026 16:31:07 +0000 (12:31 -0400)]
scan_next: detect snapshot families for the sharing cost model
Undiverged snapshots share metadata pages, so k refs to the same
(inode, offset) through k subvols of one snapshot family are one
physical metadata item, not k items. The space-debt model needs to
know which subvols can share pages — and with which other subvols,
since grouping refs by (inode, offset) is only sound within one
family.
Add scan_next_snap_cluster_map(): union-find over root_item uuid
values, joining each subvol's uuid to its nonzero parent_uuid.
Joining uuid values rather than subvols makes the sibling rule
automatic — two children of a deleted parent meet at the parent's
uuid with no surviving subvol needed. Only families with two or more
existing members are published (root id -> lowest member root id), so
a no-snapshots filesystem carries one empty map. A deleted middle
link in a snapshot-of-a-snapshot chain breaks the join; accepted,
since real topologies are stars or rolling chains where the last two
generations coexist. scan_next_snap_extra() computes the resulting
undercharge: sum of (k - 1) over groups of identical (cluster, inode,
offset) keys.
Expose the map through the extent layer as snap_cluster(root):
default 0 (no families), btrfs base builds it lazily from one
ROOT_ITEM sweep under its own mutex and bulk-clears it at transid
change (snapshot create/delete only becomes visible at a commit, so
per-transid granularity is exact), overlay delegates to its parent.
Both helpers are layer-free and pinned by unit tests covering the
star, orphan-sibling, sole-survivor, chain, deleted-middle,
independent-family, and legacy zero-uuid cases.
Zygo Blaxell [Wed, 5 Aug 2026 16:22:11 +0000 (12:22 -0400)]
crucible: add root_uuid/root_parent_uuid accessors to BtrfsTreeItem
Decode the uuid and parent_uuid members of a ROOT_ITEM payload. These
identify snapshot relationships between subvols: parent_uuid is
nonzero only for snapshots and names the uuid of the subvol the
snapshot was taken from.
The UUID members live in the extended part of btrfs_root_item added
with subvol_uuids; a legacy short item (payload ends at generation_v2)
yields the zero UUID instead of throwing, matching the kernel's
treatment of invalidated extended fields. btrfs_get_member cannot be
used here — it returns by value through le_to_cpu, which has no
sensible meaning for a 16-octet array — so the helper bounds-checks
and copies the octets directly.
Zygo Blaxell [Tue, 4 Aug 2026 17:48:39 +0000 (13:48 -0400)]
scan-next: abandon dst plans quietly when a source ref vanishes
The sweep-join pair builder threw "Plan incomplete: no valid source
reference covers range" when a planned source window had no usable
ref, producing a full trace dump with two extent tree prints per
occurrence. This is not a planner bug: the plan is built from one
transid cycle's cached snapshot, and layer caches are bulk-cleared at
transid change, so by execution time the refetched refs list can be
missing refs that were deleted on disk in between (file range
overwritten, file or snapshot deleted). Nothing can prevent this
race — filesystem users delete refs whenever they like — so it is
expected churn, like the unopenable refs excluded from block map
coverage during map generation.
Replace the throw with a quiet abandon: count the failure, log a
single debug line, and return an empty optional through
scan_next_build_tree_pairs so scan_next_execute_dst_plan skips the
dst without executing any pairs. The abandon happens during pair
building, before any FIDEDUPERANGE runs, so the dst extent is left
untouched and gets rescanned in a later cycle once the churn
settles. Abandoning the whole dst rather than skipping the
uncovered range keeps the plan's cost model honest: partial
execution would create refs without freeing the dst extent.
Two counters split the failure by class, mirroring the pread
instrumentation: plan_src_gone (no covering ref at all — the ref
vanished from the refs list) and plan_src_open_fail (covering refs
present but none opened — deleted-but-listed churn).
Zygo Blaxell [Tue, 4 Aug 2026 17:47:22 +0000 (13:47 -0400)]
scan-next: return early from the sweep-join source walk on an unopenable ref
Invert the source open check into an early "keep walking" return, so the
path that builds the pair is no longer nested inside it. No behaviour
change: the check already tests the Fd with !!, so an unopenable source
ref is skipped and the walk tries the other overlapping refs.
Zygo Blaxell [Mon, 3 Aug 2026 03:28:53 +0000 (23:28 -0400)]
extent-layer: exclude unopenable refs from block map coverage
Refs in deleted files or snapshots linger in an extent's ref list
until the last open fd closes or the subvol cleaner runs. Blocks
covered only by such refs cannot be read through any ref, and
block_map_fetch pass 2 would fail the whole block map with a noisy
"no usable ref covers extent offset" exception for a condition that
is ordinary filesystem churn.
Require data refs to open successfully before they contribute to
pass 1's coverage union. Blocks whose only covering refs fail to
open are now classified as unreachable, the same as blocks with no
covering ref at all, and map generation proceeds quietly. Prealloc
classification is unchanged: it is purely structural and pass 2
never reads prealloc-only ranges.
Probe cost is bounded: a ref that adds no new coverage beyond
already-covered blocks is skipped without probing, so heavily
overlapping ref clusters do not open every referencing file, and
the fd cache stores negative results, so a dead (root, ino) pair
costs one failed resolution however many refs point to it.
Count weeded refs as block_map_ref_unopenable. The residual
pread_no_ref_open exception now only indicates a file or subvol
that disappeared between pass 1's probe and pass 2's read.
Zygo Blaxell [Mon, 3 Aug 2026 03:17:55 +0000 (23:17 -0400)]
extent-tree: instrument "no usable ref covers extent offset" failures
BeesBtrfsExtentNode::pread throws "no usable ref covers extent offset"
on some live systems, but the exception trace shows only the bytenr
from block_map_fetch's BEESTRACE frame -- none of the structure being
processed is visible, and the failure cannot be classified from the
log.
Blocks with no covering ref at all are expected and never reach
pread: block_map_fetch pass 1 leaves them unreachable and pass 2
skips them. The exception therefore indicates one of two abnormal
conditions, which the log could not previously distinguish:
- every ref covering the offset failed to open (the referencing
files or subvols went away between the metadata fetch and the
read), or
- no candidate ref covers the offset at all, meaning the caller's
coverage model disagrees with the ref list pread built from the
same cached refs.
Distinguish the two cases with new event counters (pread_no_ref_open,
pread_no_ref_gap, plus non-fatal pread_ref_open_fail for individual
open failures that another covering ref absorbs), and report both
counts along with candidate and ref totals in the exception message.
At the throw site, dump the refs that failed to open (capped at
BEES_PREAD_REF_LOG_MAX so the dump cannot scale with ref count --
extents can carry tens of thousands of refs), and for the gap case
dump the candidates bracketing the uncovered offset.
Add BEESTRACE frames so an unwinding exception shows the structure
being processed: pread's want range, ref/candidate counts, and live
cursor; block_map_fetch's logical size, block count, pass 1
classification summary (data/prealloc block counts), and the data
run whose read failed.
The case landed as 21-eof-tail-no-churn but 21 was already taken by
21-scan-first-transid, so two cases shared the number. Move it to the
next free slot (22 and 23 exist) and update IT_TEST_NAME to match.
test: isolate integration cases from the host global config
bees loads config.global-config-filename (default /etc/bees/bees.conf)
and config.local-config-filename as fallback layers UNDER the per-run
--config, so any key a case does not set inherits the host value. The
test host's /etc/bees/bees.conf had drifted to [state] persistent = no
(anonymous hash table -> no beeshash.dat / beespoint.ini) and [rewrite]
free-min = 128K (the "cap threshold at extent size" clause then demands
freeing 100% of any sub-128K extent). Both silently changed the baseline
of every case that did not override them:
- persistent = no: 02, 03, 04, 05, 20 (missing state files), and the
delayed-verify tracker in 18/19 (no persisted verify batch)
- free-min = 128K: 09, 10, 14 (partial-free rewrites rejected, so the
expected hole / dedupe never happened)
Disable the fallback layers in each case's config with empty
config.global-config-filename / config.local-config-filename, so defaults
come from the build (persistent = yes, free-min = 50%). The repl case
(05) cannot pass an empty token and reading /dev/null trips a size > 0
check, so it uses boot-layer overrides (set path.home, set
state.persistent yes) which outrank the fallback; it also fixes a stale
key (paths.home -> path.home) that only worked while /etc/bees supplied
[path] home.
No product code change. Validated on the integration host: all listed
cases pass.
test: guard against rewriting a zero-gain EOF-tail extent
An extent whose reachable data ends mid-block at EOF has a past-EOF
unreachable tail. When that tail is entirely sub-block it frees no whole
block, so a cleanup copy that relocates the data gains nothing and must
lose to do-nothing. The phantom-block bug rounded the tail up to one
freeable block, so at free-min 50% a single-block extent was rewritten for
pure ref churn.
Add an integration case built from btrfs's inability to partially free a
data extent: write, commit, truncate within the extent, commit -- leaving
whole blocks past EOF allocated-but-unreachable for bees to reclaim. A
setup assertion confirms the physical allocation stayed whole by reading
the EXTENT_ITEM key length, so a kernel that ever frees the tail eagerly
fails loudly rather than silently voiding the fixture.
Three cases at free-min 50%:
A 4096 -> 2990 0 whole blocks freed -> must NOT be rewritten
B 8192 -> 2990 1 whole block freed -> rewritten (compacted)
C 16384 -> 6000 2 whole blocks freed -> rewritten (compacted)
A is the regression guard (the only shape that flips at 50%); B and C
prove real gains still fire and exercise the executor's bare past-EOF tail
path. free-min is pinned to 50% so the test is independent of any host
global rewrite.free-min. Validated on the integration host: passes on
current HEAD, and A is rewritten (fails) at the pre-fix commit.
The executor backed the past-EOF unreachable tail with its own zero temp
so the tail hole carried an openable ref, because a btrfs EXTENT_DATA
num_bytes is sector-aligned and a dst ref therefore spans into the
past-EOF padding of its last block — sweep_join walked into the tail and
demanded a source, even though make_clipped_file_pair then dropped the
pair at the file's i_size. The temp was pure scaffolding for a range
that produces no dedupe.
Make the tail genuinely ref-less from the executor's view instead: clamp
dst-ref enumeration to reachable_size (the end of the last non-unreachable
region = the mid-block EOF) in scan_next_build_tree_pairs, so the sweep
never enters the padding. The tail's plan-tree hole is then left as a
bare HoleExtent — no backing temp — preserving the src_size == dst_lsize
span check as a ref-less no-op. The clamp equals logical_size whenever
there is no trailing unreachable region, so the common path is unchanged;
it can never truncate a reachable region, since reachable_size is the max
end over all non-unreachable regions.
Also make the shared reachable hole temp lazy: an extent whose only hole
is the past-EOF tail now allocates no temp at all (the single all-data
block with a mid-block EOF), where before it built an unused reachable
temp. Interior genuinely-ref-less regions were already free — no back
reference names them, so dst enumeration never emitted a ref there; this
brings the sector-aligned EOF tail into the same no-op category.
scan-next: drop the phantom U from the plan bar's EOF tail
The plan-line disposition bar rounded every part's size up to a whole
block so a real sub-block dedupe/copy tail (e.g. a 971-byte final block)
still showed. That round-up also emitted a spurious "U" for the
sub-block past-EOF unreachable tail the EOF clip inserts: one physical
block rendered as both the data/copy char and a phantom unreachable char,
e.g. "[CU]" with 0d1c0p1u for a single 4K block that is entirely data.
Route the bar through scan_next_region_block_count like the cost metrics:
an unreachable part rounds down, so the sub-block past-EOF tail floors to
zero blocks and drops out of the bar (the C/D/0 char for that block
already represents it), while every other kind keeps rounding up so real
sub-block tails still appear. Determine the hole part's sub-kind before
counting to pick the rounding.
Display only; no change to planning, cost, or dedupe behavior. The tail
was already a materialize-time no-op: back_holes gives a past-EOF hole its
own zero temp, and scan_next_make_clipped_file_pair clips every pair to
the files' real i_size, so a dst range at or past EOF yields no
FIDEDUPERANGE.
scan-next: count the EOF tail's shared block as data, not freeable
The unaligned-EOF clip in block_map_fetch splits one physical block into
a reachable region (data / zero / prealloc) that ends mid-block at the
file's EOF, plus an inserted unreachable region covering the past-EOF
remainder of that same block. The cost accounting then rounded every
region's byte span up to a whole block independently, so this single
physical block was counted twice: once as a data block (copied) and once
as an unreachable block (freed).
The phantom unreachable block corrupted two gates at once. It inflated
good_blocks, so free-min saw 1 freed / 2 total = 50% and admitted a
rewrite that frees nothing; and it fed physical_freed = clone_alignment
into the debt, flipping a net-zero relocate into an apparent win. A
production instance: a 4K uncompressed dst holding 2990 bytes of data
with a mid-block EOF planned as 0d1c0p1u with debt -3787 (ref-op-cost
128), when the truthful accounting is one data block, nothing freeable.
Count cost metrics in whole blocks with the reachable side owning the
shared EOF block: round data / zero / prealloc up so they claim it, and
round the unreachable remainder down so it claims nothing. The
unaligned-EOF split is the only source of a non-block-aligned region
length, and the inserted unreachable region is always the far side of
that one boundary, so flooring it can never zero out a genuinely freeable
block-aligned region -- only the phantom tail. Every other region is
block-aligned, where floor and ceil coincide.
The rule lives in one pure helper, scan_next_region_block_count, shared
by scan_next_plan_init and the diagnostic probe so the two can't drift;
matched-block counting already rounds up (matches are data), keeping
bad_blocks = initial_data - matched balanced at the EOF block.
bees-plan: let force-rewrite rewrite compressed extents via copy
A force-marked compressed extent with no dedupe cover crashed the
planner with a per-extent exception:
plans.size() = 0 failed constraint check (!plans.empty())
at bees-scan-next.cc:3778
The do-nothing null floor is suppressed for a force-marked start
(forced_floor), on the assumption that the forced FullRewrite Plan A is
unconditionally viable and always survives the viability filter. That
assumption is false for a compressed dst: the coverage search forbids
all copy edges on a compressed extent (copy_front_path, the greedy
fallback, and the build-time compressed-dst-with-copy reject all enforce
"no copy on compressed"). A rewrite of a compressed extent that no
dedupe match covers needs a copy, so the selector returns no covering,
Plan A reports !viable(), the ballot empties, and the invariant throws.
This is exactly the documented zlib-to-zstd re-encode use case
(force-rewrite = yes with a compression condition), which the code never
actually delivered for compressed extents.
Lift the compressed-dst copy prohibition when the extent is force-marked.
The prohibition exists to stop compressed extents from being fragmented
by partial copies; force-rewrite is a per-filter opt-in, so the operator
has scoped exactly which extents must be rewritten and accepts the
fragmentation cost. The numeric [rewrite] op limits still bind: a forced
rewrite is still prevented when no covering fits within copy-max /
total-max, and the operator caps fragmentation with copy-max (= 1 for
whole-extent-only rewrites).
Thread the flag through PlanSearchInputs (covers the exact DP and the
greedy fallback) and re-add the force_rewrite parameter to
scan_next_reject_reason for the build-time gate. When op limits leave no
viable forced plan, fall back to the do-nothing floor instead of throwing
(new counter plan_force_rewrite_unrealizable), so force-rewrite stays
best-effort rather than aborting the scan.
test: link bench-bees-plan against the sectioned bees-util rebuild
bench-bees-plan links no bees-util object at all, so it never resolved the
BeesStats::s_global / add_count symbols that the instrumented
test-bees-plan-lib.o it shares with test-bees-plan references. Link
test-bees-util-lib.o, the function-sectioned rebuild of bees-util.cc that
test-bees-plan already uses, so --gc-sections keeps only BeesStats here too.
Also drop the backslash line-continuations from bench-bees-plan.cc's build-
recipe comment: a '\' at the end of a // line is a multi-line comment that
gcc's -Wcomment rejects under -Werror. Point the comment at `make
bench-bees-plan` instead of a stale hand-build command.
scan-next: log real dedupes the do-nothing floor declines
plan_accept_null counts every extent where the do-nothing floor wins, but
that lumps together the common no-duplicates case with the diagnostically
interesting one: an extent where a real covering was built and then lost
to the floor because its reference/extent cost outweighed the space it
would free. Only the counter moved; nothing said which extents, how much
they would have freed, or why the floor rejected them.
Emit a "plan: null" log line when the floor wins and the best competing
real plan has a non-zero operation count. The zero-op case (no duplicate
found, or none surviving the gates) ties the floor at debt 0 and stays
silent, so the line does not fire for every scanned extent. When it does
fire the losing plan's debt is necessarily >= 0 (a negative-debt plan
would have displaced the floor), so the line reports the aggregate cost
that sank it: bytes_freed found, physical_freed earned, refs_added /
refs_created spent, extents_delta, and the positive space debt. This is
the ref-cost-vs-physical-freed breakdown that names the cause -- a
compressed dst freed wholesale earns little physical credit against the
references its removal must rewrite.
Add plan_null_declined alongside so the interesting subset of
plan_accept_null is countable without grepping.
scan_next: count planner coverage-search and plan decisions
The planner made several branch decisions that were invisible in the event
counters. The existing plan_* counters track only the plan lifecycle
(plan_start / plan_execute / plan_empty / plan_dst_executed), not which
path was taken or why a plan was declined, so a workload where the planner
constantly bails looked identical in the stats to one sailing through.
Add three families of counters, all in the plan group:
- coverage search (bees-plan.cc): plan_cover_exact / plan_cover_greedy
record which algorithm ran, so the rate at which rewrite.plan-max-vertices
trips is now visible; plan_cover_none_{compressed,hole,limit} record why a
search produced no covering. The whole file was previously uninstrumented.
- reject reasons (scan_next_reject_reason): plan_reject_* — one per enumerated
rejection string, which were logged at DEBUG but never counted. Knowing
which limit binds (dedupe/copy/hole/total or a compressed-dst rule) is the
actionable signal.
- accept by plan type: a new pure-virtual BeesPlan::count_accepted(), called
once on the winning plan, so plan_accept_{start_as_dst,start_as_src,null}
record which strategy won each ballot. Pure virtual so a future plan type
cannot be silently uncounted.
Document the whole plan group in docs/event-counters.md (the pre-existing
plan_* counters were undocumented too).
bees-plan.cc was deliberately kept linkable without the bees daemon so the
coverage search can be unit-tested against a brute-force oracle; BEESCOUNT
pulls in BeesStats::s_global / add_count, which test-bees-plan has to resolve
from somewhere. Link a test-local, function-sectioned rebuild of
bees-util.cc (test-bees-util-lib.o, mirroring test-bees-plan-lib.o) rather
than the stock ../src/bees-util.o: that object is built without
-ffunction-sections, so GNU ld cannot prune within it and would keep the
whole translation unit once add_count is referenced, dragging in unresolved
bees-side symbols it also defines (BeesNote, bees_log_emit, bees_log_cat_level,
pretty, BeesFileRange::fid). With per-function sections --gc-sections keeps
only BeesStats on both toolchains.
extent-tree: try_lock in BtrfsExtentNode::print to avoid a status deadlock
BeesBtrfsExtentNode::print() takes the node's m_lazy_mutex to snapshot the lazy
compress/generation/datacow fields ("extent-tree: lock m_lazy_mutex in
BtrfsExtentNode print/dump_tree"). But print() runs from the
per-thread status callbacks invoked by BeesNote::get_status(), which hold
BeesNote::s_mutex the whole time, while a reference-fetching worker holds the
same node's m_lazy_mutex and then takes s_mutex via the BEESNOTE inside
refs_fetch — the opposite lock order. The reporter and the fetcher deadlock:
the reporter holds s_mutex waiting for the node lock, the fetcher holds the node
lock waiting for s_mutex. Observed as a hung daemon with the reporter in
get_status -> operator<<(BeesExtent) -> print and a worker in
node::refs -> refs_fetch -> BEESNOTE.
A status printer must never block on a data lock. Acquire m_lazy_mutex with
try_to_lock and, when it is held by a concurrent fetch, leave the lazy fields
unknown (the stream formatting already handles the empty optionals). A
best-effort status line is worth more than a hang. The lazy-field snapshot is
still race-free — it only reads when the lock was actually acquired.
scan_next: tag re-centered Plan B plans in the log
Add a "pivot" marker to the plan: line for destinations of a re-centered Plan B
(prefer-canonical-src pivoted the star onto a higher-ref whole-extent duplicate),
so re-centered plans are greppable when validating the pivot against a run.
DstPlan carries an m_pivoted flag set on each pivoted destination at build time;
the plan: line prints " pivot" when it is set. Document the tag in running.md.
scan_next: pivot Plan B onto the highest-ref whole-extent duplicate
Plan B fixes the start as the src, so scanning a fresh low-ref extent that
matches an older high-ref canonical drained the canonical onto the newcomer —
re-canonicalization — because Plan B can aggregate several destinations and
out-free single-dst Plan A even while moving the canonical's whole reference
set. The right operation isn't a choice between the two existing orientations;
it is to re-center the dedupe star on the canonical, making the start just
another destination.
When prefer-canonical-src is set, finalize() picks the star center as the
highest-reference member of {start} ∪ whole-extent-matching candidates — a
single argmax over the accepted entries, O(N), no pairwise search. Centering on
the max-ref member minimizes the references the plan moves (Σrefs − center_refs);
for a set of equivalent whole-extent duplicates that churn is the only cost that
differs between orientations, so the members free equal physical space and only
refs_created changes, dropping by center_refs − start_refs. With ref-op-cost on,
the existing debt ordering then prefers the pivot automatically; the argmax is
only decisive at ref-op-cost = 0 where the churn is unpriced.
The center is byte-identical to the start over the whole extent, so at build
time each destination's match transposes onto it by swapping the src extent, and
the start's own destination is a whole-extent match. The center is a real
dedupe src (m_src_bytenrs push-to-front hash refresh, like a Plan A src); the
start does not survive. Limited to whole-extent centers, where the star is a
clean set of interchangeable duplicates; partial matches keep the ordinary
orientation. Off unless prefer-canonical-src is set.
test: have clean remove the non-PROGRAMS build products
clean removes everything derived from $(PROGRAMS), plus
test-bees-plan-lib.o by name. It misses the rest of what the explicit
rules produce: the two generated .dep files, and the bench object and
binary. A .dep left behind is the worse of the two, since it is
`-include`d on the next build and names header paths from the tree it
was generated in.
rewrite: make the canonical-src tie-break configurable (prefer-canonical-src)
The equal-reach source tie-break — prefer the source with the most references
so duplicates consolidate onto a canonical extent — has been unconditional. It
is only safe when ref-op-cost prices the reference movement that consolidation
drives: with ref-op-cost = 0 (the default) it concentrates references onto a few
extents up to refs-max with nothing to bound the resulting re-canonicalization,
doing far more reference-rewriting work than spreading references across sources
would. A t100 / ref-op-cost = 0 run showed ~70x the reference redirects of a
build without the tie-break, piled onto the refs-max ceiling.
Add a boolean rewrite.prefer-canonical-src so the tie-break can be enabled or
disabled — for an A/B test confirming it is the cause, and as the knob operators
use to pair it with a non-zero ref-op-cost. When disabled the flattener leaves
each match's src ref count at 0, which the coverage search already reads as "no
preference" (ties resolve first-match, as before) and which also skips the
per-candidate refs() lookup. Default yes preserves current behavior; the docs
and config comment note it is only safe with a non-zero ref-op-cost.
Keys that version 2 introduces are defined in bees-config-v1.cc, at the
value that keeps v0.11 behaviour; bees-config-v2.cc states only those
whose version 2 default differs.
docs: document the extent-scan dedup/plan log lines
Describe the dedup: source/destination lines, the {bytenr+offset[:compression]
[/generation]} physical-extent token (including why the allocation generation is
logged and not file_extent_generation), and the plan: line fields, notably the
refs / rc / debt diagnostics that expose which references a plan rewrites and the
signed space-debt that admitted it.
scan_next: gate each Plan B dst on its own debt, not the aggregate
Plan B executes each destination independently — each is a reversed Plan A
against the single start src — but its cost was evaluated only in aggregate: the
per-candidate debts were summed and the plan admitted if the sum beat
do-nothing. That let a batch of profitable singleton dedupes subsidize an
individually-catastrophic drain. The instrumentation showed it directly: one
Plan B emitted 130 dst lines sharing one aggregate debt, 129 of them 1-ref
extents (each a real space win) and one a 9912-ref extent whose own debt is
~+521k (redirecting 9912 references onto a fresh src, priced by ref-op-cost).
The group summed to -7197, so the fat drain rode along — re-canonicalizing a
near-canonical extent instead of leaving it to accumulate and retire.
Gate each candidate on its own signed space-debt at accept time: drop it unless
its per-entry debt beats the do-nothing floor (< 0). The profitable singletons
are unaffected; the high-ref drain is declined, so the fat extent stays the
canonical src, keeps absorbing, and retires at refs-max as intended. A
force-marked candidate bypasses the gate, mirroring the FullRewrite floor's
benefit-gate bypass, since force means "rewrite regardless of benefit".
This is the last of the reference-cluster cost-model defects: retirement
(refs_fetch) settles clusters, refs_created makes ref-op-cost price ref moves,
and this gate stops Plan B from subsidizing a drain past that price.
scan_next: log selection-time refs_created on the plan: line
The debt on the plan: line showed that fat whole-extent drains are admitted with
a strongly negative debt, i.e. the refs_created * ref_op_cost term is absent even
though ref-op-cost is configured non-zero and wired into both plan orientations.
The remaining unknown is whether refs_created was itself ~0 at selection — the
planner pricing the dst against a stale or reduced reference view — versus the
weight being lost.
Add m_sel_refs_created to DstPlan, captured from the winning plan's cost() at
build time, and log it as "rc" beside the build-time "refs":
... [Dddddd] refs 4125 rc 0 debt -6708.0
refs is read fresh at build; rc is what the cost model actually charged. rc far
below refs on a fat drain pins the cause to a stale/reduced ref count reaching
scan_next_dst_debt at cost time, not the weight or the wiring.
scan_next: log dst ref count and plan debt on the plan: line
The plan: line reported the op counts and timing of an accepted plan but not
why it was chosen, so a re-canonicalization drain (a high-ref extent selected as
a dst) was invisible without inferring ref counts from the dst redirect lines.
Capture two diagnostics on DstPlan at build time — the winning plan's signed
space-debt (the value that beat the other orientations and the do-nothing floor)
and this dst's reference count as the planner saw it, pre-execution — and append
them to the plan: line:
refs is read at build time, before the dedupe moves the dst's references, so it
is the decision-time count, not the post-execution remainder. A whole-extent
drain of a fat extent now shows its ref count and the debt that admitted it
directly: if that debt is negative on a high refs value, the cost model
mispriced the drain; if positive, the plan won a ballot it should have lost.
scan_next: unify the two space-debt input builders into one
The four do-nothing space-debt input fields were computed twice: once in
scan_next_covering_debt (the search's covering selection) and once in
scan_next_dst_debt (the plan cost that drives orientation selection). The two
had to mirror each other field-for-field, and when they drifted — m_refs_created
present in the search builder but missing from the plan builder — ref-op-cost
silently went inert in selection. A comment claimed the two were
reconciliation-checked, but no such check existed.
Extract the arithmetic into one shared builder, scan_next_debt_fields(), that
takes raw scalars and returns a CostReport with the four fields set. Both paths
now marshal their inputs into it:
- scan_next_covering_debt() becomes a thin wrapper that prices the result.
- scan_next_dst_debt() returns the builder's CostReport directly; the
ScanNextDstDebt mirror struct is deleted (Plan A/B read the same field names,
so their cost assembly is unchanged).
The extents_delta test collapses to copy_ops > 0 ? +1 : -1; for a complete
covering — the only input either caller passes — copy_ops > 0 iff unmatched data
remains, so this equals the plan path's former bad_blocks()==0 form. With one
source of truth a term can no longer exist in one path but not the other.
test-bees-plan gains test_debt_fields_shared_builder, pinning the field
arithmetic directly (including refs_created at F=1) and asserting the builder
and scan_next_covering_debt agree for the same covering.
scan_next: wire refs_created into the plan-cost path so ref-op-cost applies
ref-op-cost weights CostReport::m_refs_created, but that field was only ever
set by scan_next_covering_debt (bees-plan.cc), on a throwaway CostReport used
for the shortest-path search's internal covering order. The plan-level cost
that drives orientation selection is built from scan_next_dst_debt, whose
ScanNextDstDebt struct never carried m_refs_created — so every plan reaching
min_element/cheaper_than had m_refs_created == 0, and the refs_created *
ref_op_cost term of space_debt() was always zero. ref-op-cost has been inert
in the runtime planner since it was added.
The consequence is a re-canonicalization blow-up: for a fresh start matching a
high-ref candidate, Plan B (drain the fat candidate as dst) scores
refs_added = dst_ref_count*(F-1) = 0 for a whole-extent (F=1) dedupe,
refs_created = dst_ref_count*F uncharged, extents_delta = -1, physical_freed
positive — a strongly negative debt, so draining a 9650-ref extent looks free
and beats both Plan A (accumulate) and do-nothing. Observed in the t10 stress
run as extents accumulating to ~9650 as src then immediately being drained as
dst, the same cluster relaying down a chain of identical extents.
Add m_refs_created to ScanNextDstDebt and compute it as dst_ref_count *
frag_count (unguarded, matching scan_next_covering_debt), then propagate it
into Plan A's cost and Plan B's per-entry and aggregate costs. With the term
live, draining a 9650-ref dst costs ~9650*ref_op_cost of debt and loses to
accumulation, so a canonical extent grows until it reaches refs-max and
retires instead of relaying its cluster. The ScanNextDstDebt doc note now
states the mirror-scan_next_covering_debt invariant this violated.
scan_next: retire over-limit extents in refs_fetch, drop the ceiling gate
An extent whose reference count reaches rewrite.refs-max is unusable: deduping
onto it would push it past the limit, and the LOGICAL_INO buffer (sized to
refs-max) can no longer enumerate it in full. scan_one handles this in its own
logical_ino wrapper — an over-limit resolve is treated as a failure so the
extent's refs are never inserted and it disappears from consideration
(bees-roots.cc). The method-1 layer path had no such retirement: refs_fetch
returned every ref it got, so a full extent stayed a live candidate.
Combined with the additive ceiling gate this produced the reference-stacking
blow-up the t10 validation caught. The gate stopped a dedupe at src+dst >
refs-max, so an extent parked one ref short of the limit — still reporting its
refs, still eligible — and thousands of them churned at the wall (a staircase of
extents pinned at refs-max, absorbing and draining ~refs-max references each)
instead of a full extent retiring as a stable canonical sink.
Retire the extent at logical_ino time instead: when the reference count reaches
refs-max, refs_fetch reports it as having no references. Nothing can use it —
it reads exactly like an extent whose refs were all deleted, and the callers'
existing 0-ref handling (scan_next's early exit for the start, the candidate
drop that also dodges the datacow_fetch throw) makes it inert: not locatable as
a src, no refs to redirect as a dst. A dedupe may now run to completion even
when it takes the src to at most 2*refs-max references, after which the src
itself retires; refs-max bounds the inputs, not the output.
With retirement doing the work, the additive gate (scan_next_refs_would_exceed
and its two process_candidate sites) and the truncated-refs dst guard are both
redundant — they were compensating for the missing retirement at the wrong
layer — so remove them, along with the now-obsolete test_refs_ceiling_gate.
The high-ref-src tie-break stays: with saturated srcs retired, it consolidates
onto the highest non-full src, which then fills and retires, converging a
duplicate cluster onto a series of full canonical sinks.
scan_next: prefer the higher-ref src on equal-reach ties
The coverage search charges only the dst extent's fragmentation, so among
matches that reach equally far it recorded whichever it met first — an
arbitrary src choice. For a whole-extent dedupe (F=1) every candidate src
reaches the full extent, so they all tie on reach, and the arbitrary pick
lets dedupe chain through low-ref extents. That feeds the rolling
re-canonicalization the low-total-max stress run exhibited: an extent absorbs
references as a src, is later eliminated as a dst, and drains them elsewhere,
never converging.
Carry each match's src reference count into PlanSearchMatch and break
equal-reach ties in the per-vertex reach precompute (and the greedy fallback)
toward the higher-ref src, consolidating dedupe onto the already-canonical
extent. Reach stays the primary key — a farther-reaching low-ref src still
wins, because trading reach for src refs would raise the fragment count, a
real debt term rather than an equal-cost tie. The src choice never changes
an edge's debt, so the tie-break is free in the O(M+V) sweep and leaves every
covering's debt (and all existing debt reconciliations) untouched.
This is Feature #1 of the reference-cluster cost model, following the
ref-op-cost soft cost (#2) and the additive ref ceiling (#3). The A/B stress
runs showed #2 brakes the churn but leaves a bounded both-hot residual (one
extent absorbing ~5800 and draining ~8900 refs); this rule targets that
residual by orienting each dedupe toward the canonical src.
test-bees-plan gains test_search_prefers_high_ref_src, pinning the tie-break
on both the exact DP and greedy paths (order-independently) and the
reach-primacy guard that keeps a full-span low-ref src ahead of a short
high-ref one.