Zygo Blaxell [Sun, 3 May 2026 18:52:19 +0000 (14:52 -0400)]
progress: work around GCC-16 -Warray-bounds bug
`make_shared<ProgressTrackerState>()` keeps triggering GCC bugs.
The latest failure on GCC-16.0 and GCC-16.1:
/usr/include/c++/16.1.1/bits/stl_tree.h:1383:19: error: array subscript 1 is outside array bounds of ‘std::_Sp_counted_ptr_inplace<crucible::ProgressTracker<long unsigned int>::ProgressHolderState, std::allocator<void>, __gnu_cxx::_S_atomic> [1]’ [-Werror=array-bounds=]
../include/crucible/progress.h:46:24: error: array subscript ‘crucible::ProgressTracker<long unsigned int>::ProgressTrackerState[0]’ is partly outside array bounds of ‘unsigned char [40]’ [-Werror=array-bounds=]
The regression is already reported to the GCC project:
https://www.mail-archive.com/gcc-bugs%40gcc.gnu.org/msg895281.html
https://gcc.gnu.org/bugzilla/show_bug.cgi?id=123912
(and its duplicates)
The problem is that GCC's static analyzer forgets that make_shared
intentionally allocated a control block and an object in the same
allocation, and thinks that accesses beyond the end of the control block
are out-of-bounds array accesses.
This workaround is the shortest: start with a unique_ptr (which has no
control block but does have an exception-safe allocator), then convert
to shared_ptr. This breaks the allocation into two parts so that GCC
is no longer confused. As there are typically fewer than 10k progress
tracking items, the separate control blocks will only add a few hundred
KiB of RAM usage.
Zygo Blaxell [Fri, 1 May 2026 08:01:34 +0000 (04:01 -0400)]
openat2: remove throw() specifier
This removes the obsolete throw() specifier from the openat2() declaration in
include/crucible/openat2.h and its definition in lib/openat2.cc. C++11 and
later deprecates throw() and C++17 removes it in favor of noexcept.
Zygo Blaxell [Fri, 15 Aug 2025 02:05:29 +0000 (22:05 -0400)]
bees: handle --version and --help/-h before bees initialisation
Introduce the standard --version option to print version and exit 0.
Adjust --help/-h to do the same.
Scan argv in main() for standard options before calling bees_main().
This avoids going through config parsing and Chatter log setup that we're
going to throw away immediately.
If neither option appears, write the version on stderr as before.
Since the version string may be critical to debugging the configuration
parsing code, the version string output is unconditional, and occurs
prior to the start of config parsing.
Zygo Blaxell [Sun, 15 Mar 2026 03:21:54 +0000 (23:21 -0400)]
bees-roots: fix off-by-one objectid in subvol scanner crawl_one_inode
peek_front() -> fetch_extents() advances m_state.m_objectid to
found_inode + scale_size before crawl_one_inode() calls get_state_end().
The resulting this_state.m_objectid is one past the actual inode, but
BeesFileCrawl uses it with BtrfsExtentDataFetcher which requires an
exact objectid match. The net effect: every inode is scanned with the
objectid of the *next* inode, finding nothing.
Fix: derive bfc_state from this_state but override m_objectid with the
actual inode extracted from this_range.fid().ino(). The crawl's own
set_state() call at the end of crawl_one_inode() still uses this_state
(objectid = found_inode + 1), correctly positioning the next search.
Co-Authored-By: Claude Sonnet 4.6 <noreply@anthropic.com>
Zygo Blaxell [Fri, 13 Mar 2026 23:06:32 +0000 (19:06 -0400)]
hash: fix FLAGS_CREATE_FILE O_WRONLY preventing pread on new hash table
FLAGS_CREATE_FILE used O_WRONLY|O_CREAT|O_EXCL. On a fresh beeshome,
open_file() creates beeshash.dat through this flag and assigns the
write-only fd to m_fd. The prefetch thread then calls pread_or_die(m_fd)
and gets EBADF because pread() requires O_RDONLY or O_RDWR.
In production, beesd and OpenRC pre-create beeshash.dat with truncate(1)
before exec'ing bees, so the creation branch in open_file() was never
exercised. Integration tests exposed this by starting bees on a fresh
$BEESHOME.
Change FLAGS_CREATE_FILE from O_WRONLY to O_RDWR. The name still
describes the intent (O_CREAT|O_EXCL ensure exclusive creation); O_RDWR
simply allows reading the file back after writing it.
chatter, fd: drop unused ChatterTraits specializations
Remove three template specializations that turned out to be dead
code on inspection:
- ChatterTraits<const Argument *> in chatter.h: the pointer
pretty-print that emitted "(pointer to TypeName)(0xaddr)".
A link-time audit (extern undefined symbol inserted in the
template body, full build) confirmed no translation unit in
either the library or its consumers instantiates this
specialization. The format had not been used anywhere in
practice.
- ChatterTraits<const char *> in chatter.h: existed only to
override the pointer specialization for C-strings (which would
otherwise pretty-print every literal as "(pointer to char)
(0xaddr)"). Once the pointer specialization is gone, the
primary ChatterTraits<T> template's `c.get_os() << arg` falls
through to `ostream::operator<<(const char *)`, producing the
same correct output without a dedicated specialization.
- ChatterTraits<Fd> in fd.cc: transitively dead. Its body
contained `c << &fd` where `&fd` has type `const Fd *`, which
would have triggered the now-removed pointer specialization
had any caller used it. The author's own comment
(`// XXX: necessary? useful?`) reflected the same uncertainty;
the audit confirmed the answer. Callers that need to print
an Fd in a log message can use Fd::operator int() for the
file-descriptor number or name_fd(const Fd&) for the resolved
path — both already in the public API.
Three template specializations removed; the primary ChatterTraits<T>
template that delegates to `ostream::operator<<` remains as the
single dispatch path. No behavior change for any existing caller
(audit guarantees these specializations were unreachable).
Co-Authored-By: Claude Opus 4.7 <noreply@anthropic.com>
Zygo Blaxell [Mon, 23 Mar 2026 07:43:26 +0000 (03:43 -0400)]
btrfs-free: fix rlower_bound failing to find items at offset zero
rlower_bound initialized closest_logical to 0, so a matching item at
offset 0 never passed the `this_logical > closest_logical` check.
Add a `have_closest` flag so the first match is always accepted.
This caused ref_backward to return null when the previous extent was
at offset 0 in the file, which is the common case for the first
extent of any inode.
This has been subtly breaking subvol scans since the extent scan rework
exposed the bug; however, fixing this still doesn't help subvol scans
work at scale, so they're still deprecated.
Co-Authored-By: Claude Sonnet 4.6 <noreply@anthropic.com> Signed-off-by: Zygo Blaxell <bees@furryterror.org>
Add docs/scan-one-algorithm.md describing the v0.11 scan_one
algorithm for bees users — how the hash table size, data extent
size, 50% must-free threshold, and random-insertion LRU interact in
practice — and link it from README.md and docs/index.md.
Co-Authored-By: Claude Opus 4.7 <noreply@anthropic.com>
Zygo Blaxell [Sat, 14 Feb 2026 05:05:29 +0000 (00:05 -0500)]
bees: adjust BLOCK_SIZE_MAX_EXTENT to work around kernel bug
In kernel commit 24542bf7ea5e4fdfdb5157ff544c093fa4dcb536 ("btrfs:
limit fallocate extent reservation to 256MB"), the maximum size of a
prealloc extent is set to 256MB. This exceeds BTRFS_MAX_EXTENT_SIZE,
which is 128MB.
This causes some problems with parts of bees code which guard against
problems that arise when metadata is corrupted. One manifestation of
that problem is a potential infinite (or very large finite) loop, caused
by the extent mapping code repeatedly trying to compute a dedupe solution
for a >128M extent, but being unable to do so because it is interrupted
when it hits the self-imposed 128M extent size limit. This may be the
cause of issues such as [#325](https://github.com/Zygo/bees/issues/325).
Since the kernel bug is 14 years old, it's de facto part of the
filesystem spec now. Increase the limit to the largest expected size
of btrfs extents.
bees: separate BEES_MAX_EXTENT_TASK_COUNT from BEES_MAX_EXTENT_REF_COUNT
They are both roughly the right number, but the number of tasks is not the
same as the number of refs:
* in extent scan mode, each extent Task has all of the extent's refs
* in subvol scan mode, each Task handles inodes, not extents or refs
Making the extent task count smaller reduces parallel and out-of-order
task execution. This helps prevent a wide gap from forming between the
current progress checkpoint (lowest extent in the queue) and the head
of the crawl (highest extent in the queue). This makes restarts repeat
less work, which may help make forward progress if bees is run for very
short intervals between restarts, but it will make the scans take longer
due to more sequential processing.
Zygo Blaxell [Tue, 11 Mar 2025 18:46:40 +0000 (14:46 -0400)]
readahead: flush the readahead cache based on time, not extent count
If the extent wasn't read in the last second, chances are high that
it was evicted from the page cache. If the extents have been evicted
from the cache by the time we grow or dedupe them, we'll take a serious
performance hit as we read them back in, one page at a time.
Use a 5-second delay to match the default writeback interval.
readahead: ignore large and unproductive readahead requests
Sometimes there are absurdly large readahead requests (e.g. 32G),
which tie up a thread holding the readahead lock for a long time (not
to mention the IO the reading hammers the rest of the system with).
These are likely an artifact of the legacy ExtentWalker code interacting
with concurrent filesystem changes.
The maximum btrfs extent size is 128M, so cap the length of readahead
requests at that size.
roots: filter out NODATASUM files before attempting to scan them
Add a cheap check for `FS_NOCOW_FL` when we first encounter
each extent. In the raw btrfs inode flags, the offending flag is
`BTRFS_INODE_NODATASUM`, because the restriction that prevents reflink
between datacow and "nodatacow" files is that a single inode is allowed
to have csums or not have csums, but must apply that choice to _all_
of its extents.
This extra check is cheaper than opening a file for each individual
reference to the extent, and then discovering that the file is
`FS_NOCOW_FL`, and then closing the file, over and over again. It will
also avoid emitting a lot of noisy log messages.
Skip the kernel version check and test for the definition of `SYS_openat2`
directly. If it's not there, plug in the constant so we can send the
call directly to the kernel, bypassing libc completely.
Adds a `BINDIR` Make variable, defaulting to `sbin`, allowing packagers
to override the install location of `beesd` for systems that do not use
`/sbin`. This affects the install path and systemd unit template.
Build fails on 32-bit Slackware because GCC 11's `-Werror=sign-compare`
is stricter than necessary:
cc -Wall -Wextra -Werror -O3 -I../include -D_FILE_OFFSET_BITS=64 -std=c99 -O2 -march=i586 -mtune=i686 -o bees-version.o -c bees-version.c
bees.cc: In function 'void bees_fsync(int)':
bees.cc:426:24: error: comparison of integer expressions of different signedness: '__fsword_t' {aka 'int'} and 'unsigned int' [-Werror=sign-compare]
426 | if (stf.f_type != BTRFS_SUPER_MAGIC) {
| ^
To work around this, cast `stf.f_type` to the same type as
`BTRFS_SUPER_MAGIC`, so it has the same number of bits that we're looking
for in the magic value.
Zygo Blaxell [Tue, 25 Feb 2025 08:16:27 +0000 (03:16 -0500)]
tempfile: make sure FS_COMPR_FL stays set
btrfs will set the FS_NOCOMP_FL flag when all of the following are true:
1. The filesystem is not mounted with the `compress-force` option
2. Heuristic analysis of the data suggests the data is compressible
3. Compression fails to produce a result that is smaller than the original
If the compression ratio is 40%, and the original data is 128K long,
then compressed data will be about 52K long (rounded up to 4K), so item
3 is usually false; however, if the original data is 8K long, then the
compressed data will be 8K long too, and btrfs will set FS_NOCOMP_FL.
To work around that, keep setting FS_COMPR_FL and clearing FS_NOCOMP_FL
every time a TempFile is reset.
Zygo Blaxell [Sun, 29 Jun 2025 20:30:03 +0000 (16:30 -0400)]
tempfile: clear FS_NOCOW_FL while setting FS_COMPR_FL
FS_NOCOW_FL can be inherited from the subvol root directory, and it
conflicts with FS_COMPR_FL.
We can only dedupe when FS_NOCOW_FL is the same on src and dst, which
means we can only dedupe when FS_NOCOW_FL is clear, so we should clear
FS_NOCOW_FL on the temporary files we create for dedupe.
Zygo Blaxell [Thu, 19 Jun 2025 02:52:05 +0000 (22:52 -0400)]
roots: make the "idle" label useful
Apply the "idle" label only when the crawl is finished _and_ its
transid_max is up to date. This makes the keyword "idle" better reflect
when bees is not only finished crawling, but also scanning the crawled
extents in the queue.
Zygo Blaxell [Thu, 19 Jun 2025 02:16:12 +0000 (22:16 -0400)]
progress: move the "idle" cell to the next cycle ETA column
When all extents within a size tier have been queued, and all the
extents belong to the same file, the queue might take a long time to
fully process. Also, any progress that is made will be obscured by
the "idle" tag in the "point" column.
Move "idle" to the next cycle ETA column, since the ETA duration will
be zero, and no useful information is lost since we would have "-"
there anyway.
Since the "point" column can now display the maximum value, lower
that maximum to 999999 so that we don't use an extra column.
Zygo Blaxell [Sun, 15 Jun 2025 07:19:33 +0000 (03:19 -0400)]
extent scan: log the bfr when removing a prealloc extent
With subvol scan, the crawl task name is the subvol/inode pair
corresponding to the file offset in the log message. The identity of
the file can be determined by looking up the subvol/inode pair in the
log message.
With extent scan, the crawl task name is the extent bytenr corresponding
to the file offset in the log message. This extent is deleted when the
log message is emitted, so a later lookup on the extent bytenr will not
find any references to the extent, and the identity of the file cannot
be determined.
Log the bfr, which does a /proc lookup on the name of the fd, so the
filename is logged.
Zygo Blaxell [Thu, 13 Feb 2025 02:26:33 +0000 (21:26 -0500)]
seeker: harden against changes in the data during binary search
During the search, the region between `upper_bound` and `target_pos`
should contain no data items. The search lowers `upper_bound` and raises
`lower_bound` until they both point to the last item before `target_pos`.
The `lower_bound` is increased to the position of the last item returned
by a search (`high_pos`) when that item is lower than `target_pos`.
This avoids some loop iterations compared to a strict binary search
algorithm, which would increase `lower_bound` only as far as `probe_pos`.
When the search runs over live extent items, occasionally a new extent
will appear between `upper_bound` and `target_pos`. When this happens,
`lower_bound` is bumped up to the position of one of the new items, but
that position is in the "unoccupied" space between `upper_bound` and
`target_pos`, where no items are supposed to exist, so `seek_backward`
throws an exception.
To cut down on the noise, only increase `lower_bound` as far as
`upper_bound`. This avoids the exception without increasing the number
of loop iterations for normal cases.
In the exceptional cases, extra loop iterations are needed to skip over
the new items. This raises the worst-case number of loop iterations
by one.
...but here, we found 6821963835 and 6821963841, which are between 6821963646 and 6822575316. They were not there before, so the binary
search result is now invalid because new extent items were added while
it was running. This results in an exception:
lower_bound = high_pos 6821963841
--- BEGIN TRACE --- exception ---
objectid = 27942759813120, adjusted to 27942793363456 at bees-roots.cc:1103
Crawling extent BeesCrawlState 250:0 offset 0x0 transid 1311734..1311735 at bees-roots.cc:991
get_state_end at bees-roots.cc:988
find_next_extent 250 at bees-roots.cc:929
--- END TRACE --- exception ---
*** EXCEPTION ***
exception type std::out_of_range: lower_bound = 6821963841, upper_bound = 6821963646 failed constraint check (lower_bound <= upper_bound) at ../include/crucible/seeker.h:139
The exception prevents the result of seek_backward from returning a value,
which prevents a nonsense result from a consumer of that value.
Copy the details of this search into a test case. Note that the test
case won't reproduce the exception because the simulation of fetch()
is not changing the results part way through.
Zygo Blaxell [Thu, 13 Feb 2025 03:00:21 +0000 (22:00 -0500)]
extent scan: integrate seeker debug output stream
Send both tree_search ioctl and `seek_backward` debug logs to the
same output stream, but only write that stream to the debug log if
there is an exception.
Zygo Blaxell [Tue, 11 Feb 2025 05:04:35 +0000 (00:04 -0500)]
btrfs-tree: clean up the fetch function's return set
Commit d32f31f411eeb1a8624b99dab223af69f0c8453e ("btrfs-tree: harden
`rlower_bound` against exceptional objects") passes the first btrfs item
in the result set that is above upper_bound up to `seek_backward`.
This is somewhat wasteful as `seek_backward` cannot use such a result.
Reverse that change in behavior, while keeping the rest of the other
commit.
This introduces a new case, where the search ioctl is producing items
that are above upper bound, but there are no items in the result set,
which continues looping until the end of the filesystem is reached.
Handle that by setting an explicit exit variable.
Zygo Blaxell [Fri, 14 Feb 2025 22:17:40 +0000 (17:17 -0500)]
extent scan: drop out-of-date comment
The comment describes an earlier version which submitted each extent
ref as a separate Task, but now all extent refs are handled by the same
Task to minimize the amount of time between processing the first and
last reference to an extent.
Zygo Blaxell [Tue, 18 Feb 2025 01:02:18 +0000 (20:02 -0500)]
extent scan: extra check to make sure no Tasks are started when throttled
Previously `scan()` would run the extent scan loop once, and enqueue one
extent, before checking for throttling. Do an extra check before that,
and bail out so that zero extents are enqueued when throttled.
Zygo Blaxell [Mon, 16 Jun 2025 11:30:05 +0000 (07:30 -0400)]
progress: fix ETA calculations
The "tm_left" field was the estimated _total_ duration of the crawl,
not the amount of time remaining. The ETA timestamp was then calculated
based on the estimated time to run the crawl if it started _now_, not
at the start timestamp.
Steven Allen [Wed, 26 Mar 2025 15:02:42 +0000 (15:02 +0000)]
Make the runtime directory private
The status file contains sensitive information like filenames and duplicate chunk ranges. It might also make sense to set the process-wide `UMask=`, but that may have other unintended side effects.
Zygo Blaxell [Fri, 14 Feb 2025 04:41:31 +0000 (23:41 -0500)]
extent scan: don't divide by zero if there were no loops
Commit 183b6a5361e040d7cc70c3b3391f43e0d126bc33 ("extent scan: refactor
BeesCrawl, BeesScanMode*") moved some statistics calculations out of
the loop in `find_next_extent`, but did not ensure that the statistics
would not be calculated if the loop had not executed any iterations.
In rare instances, the function returns without entering the loop at all,
which results in divide by zero. Add a check just before doing that.
Zygo Blaxell [Thu, 13 Feb 2025 03:01:31 +0000 (22:01 -0500)]
trace: deprecate BEESLOGTRACE, align trace logs with exception notices
Exceptions were logged at level NOTICE while the stack traces were logged
at level DEBUG. That produced useless noise in the output with `-v5`
or `-v6`, where there were exception headings logged, but no details.
Fix that by placing the exceptions and traces at level DEBUG, but prefix
them with `TRACE:` for easy grepping.
Most of the events associated with BEESLOGTRACE either never happen,
or they are harmless (e.g. trying to open deleted files or subvols).
Reassign them to ordinary BEESLOGDEBUG, with one exception for
unrecognized Extent flags that should be debugged if any appear.
Zygo Blaxell [Thu, 13 Feb 2025 01:10:12 +0000 (20:10 -0500)]
trace: avoid one copy in every trace function
While investigating https://github.com/Zygo/bees/issues/282 I noticed that
we're doing at least one unnecessary extra copy of the functor in BEESTRACE.
Get rid of it with a const reference.
Zygo Blaxell [Tue, 11 Feb 2025 02:00:35 +0000 (21:00 -0500)]
BeesStringFile: figure out when to call--or _not_ call--fsync
Older kernel versions featured some bugs in btrfs `fsync`, which could
leave behind "ghost dirents", orphan filename items that did not have
a corresponding inode. These dirents were created during log replay
during the first mount after a crash due to several different bugs in
the log tree and its use over the years. The last known bug of this
kind was fixed in kernel 5.16. As of this writing, no fixes for this
bug have been backported to any earlier LTS kernel.
Some filesystems, including btrfs, will flush the contents of a new
file before renaming it over an old file. On paper, btrfs can do this
very cheaply since the contents of the new file are not referenced, and
the old file not dereferenced, until a tree commit which includes both
actions atomically; however, in real life, btrfs provides `fsync`-like
semantics and uses the log-tree infrastructure to implement them, which
compromises performance and acts as a magnet for bugs.
The benefit of this trade-off is that `rename` can be used as a
synchronization point for data outside of the btrfs, which would not
happen if everything `rename` does was simply deferred to the next
tree commit. The cost of this trade-off is that for the first 8 years
of its existence, bees would trigger the bug so often that the project
recommended its users put $BEESHOME in its own subvol to make it easy
to remove ghost dirents left behind by the bug.
Some other filesystems, such as xfs, don't have any special semantics for
`rename`, and require `fsync` to avoid garbage or missing data after
a crash. Even filesystems which do have a special case for `rename`
can be configured to turn it off.
btrfs will silently delete data from files in the event that an
unrecoverable data block write error occurs. Kernel version 6.2 adds
important new and unexpected cases where this can happen on filesystems
using raid56 data, but it also happens in all usable btrfs versions
(the silent deletion behavior was introduced in kernel version 3.9).
Unrecoverable write errors are currently reported to userspace only
through `fsync`. Since the failed extents are deleted, they cannot be
detected via csum failures or scrub after the fact--and it's too late
by then, the data is already gone. `fsync` is the last opportunity
to detect the write failure before the `rename`. If the error is not
detected, the contents of the file will be silently discarded in btrfs.
The impact on bees is that scans will abruptly restart from zero after
a crash combined with some other reasonably common failures.
Putting all of this together leads to a rather complex workaround:
if the filesystem under $BEESHOME (specifically, the filesystem where
BeesStringFile objects such as `beescrawl.dat` are written) is a btrfs
filesystem, and the host kernel is a version prior to 5.16, then don't
call `fsync` before `rename`. In all other cases, do call `fsync`,
and prevent dependent writes (i.e. the following `rename`) in the event
of errors.
Since present kernel versions still require `fsync`, we don't need
an upper bound on the kernel version check until someone fixes btrfs
`rename` (or perhaps adds a flag to `renameat2` which prevents use of
the log tree) in the kernel. Once that fix happens, we can drop the
`fsync` call for kernels after that fixed version.
Zygo Blaxell [Thu, 6 Feb 2025 06:17:09 +0000 (01:17 -0500)]
main: unconditionally enable workaround for the logical_ino-vs-clone kernel bug
This obviously doesn't fix or prevent the kernel bug, but it does prevent
bees from triggering the bug without assitance from another application.
The bug can still be triggered by running bees at the same time as an
application which uses clone or LOGICAL_INO. `btdu` uses LOGICAL_INO,
while `cp` from coreutils (and many others) use clone (reflink copy).
Zygo Blaxell [Mon, 3 Feb 2025 04:30:26 +0000 (23:30 -0500)]
roots: drop unnecessary mutex unlock in stop_request
In commit 31b2aa3c0dcf042559fa495b63a1bf22bac4d55d ("context: speed
up orderly process termination"), the stop request was split into two
methods after the mutex unlock.
Now that there's nothing after the mutex unlock in `stop_request`,
there's no need for an explicit unlock to do what the destructor would
have done anyway.
Zygo Blaxell [Tue, 4 Feb 2025 04:09:32 +0000 (23:09 -0500)]
extent scan: implement an experimental ordered scan mode
Parallel scan runs each extent size tier in a separate thread. The
threads compete to process extents within the tier's size range.
Ordered scan processes each extent size tier completely before moving on
to the next. In theory, this means large extents always get processed
quickly, especially when new ones appear, and the queue does not fill up
with small extents.
In practice, the multi-threaded scanner massively outperforms the
single-threaded scanner, unless the number of worker threads is very
small (i.e. one).
Disable most of the feature for now, but leave the code in place so it
can be easily reactivated for future testing.
Ordered scan introduces a parallelized extent mapper Task. Keep that in
parallel scan mode, which further enhances the parallelism. The extent
scan crawl threads now run at 'idle' priority while the map tasks run
at normal priority, so the map tasks don't flood the task queue.
Zygo Blaxell [Mon, 3 Feb 2025 23:28:55 +0000 (18:28 -0500)]
crawl: deprecate use of BeesCrawl to search the extent tree
BeesScanModeExtent can do that by itself now. Overloading the subvol
crawl code resulted in an ugly, inefficient hack, and we definitely
don't want to accidentally continue to use it.
Remove the support for reading the extent tree and add some `assert`s
to make sure it isn't still used somewhere.
Zygo Blaxell [Tue, 28 Jan 2025 01:11:06 +0000 (20:11 -0500)]
extent scan: refactor BeesCrawl, BeesScanMode*
The main gains here are:
* Move extent tree searches into BeesScanModeExtent so that they are
not slowed down by the BeesCrawl code, which was designed for the
much more specialized metadata in subvol trees.
* Enable short extent skipping now that BeesCrawl is out of the way.
* Stop enumerating btrfs subvols when in extent scan mode.
All this gets rid of >99% of unnecessary extent tree searches.
Incremental extent scan cycles now finish in milliseconds instead
of minutes.
BeesCrawl was never designed to cope with the structure and content of
the extent tree. It would waste thousands of tree-search ioctl calls
reading and ignoring metadata items.
Performance was particularly bad when a binary search was involved, as any
binary search probe that landed in a metadata block group would read and
discard all the metadata items in the block group, sequentially, repeated
for each level of the binary search. This was blocking implementation of
short extent skipping optimization for large extent size tiers, because
the skips were using thousands of tree searches to skip over only a few
hundred extent items.
Extent scan also had to read every extent item twice to do the
transid filtering, because BeesCrawl's interface discarded the relevant
information when it converted a `BtrfsTreeItem` into a `BeesFileRange`.
The cost of this extra fetch was negligible, but it could have been zero.
Fix this by:
* Copy the equivalent of `fetch_extents` from BeesCrawl into
`BeesScanModeExtent`, then give each of the extent scan crawlers its
own `BtrfsDataExtentTreeFetcher` instance. This enables extent tree
searches to avoid pure (non-mixed) metadata block groups. `BeesCrawl`
is now used only for its interface to `BeesRoots` for saving state in
`beescrawl.dat`, and never to determine the next extent tree item.
* Move subvol-specific parts of `BeesRoots` into a new class
`BeesScanModeSubvol` so that `BtrfsScanModeExtent` doesn't have to enable
or support them. In particular, `bees -m4` no longer enumerates all
of the _subvol_ crawlers. `BeesRoots` is still used to save and load
crawl state.
* Move several members from `BtrfsScanModeExtent` into a per-crawler
state object `SizeTier` to eliminate the need for some locks and to
maintain separate cache state for `BtrfsDataExtentTreeFetcher`.
* Reuse the `BtrfsTreeItem` to get the generation field for the transid
range filter.
* Avoid a few corner cases when handling errors, where extent scan might
drop an extent without scanning it, or fail to advance to the next extent.
* Enable the extent-skipping algorithm for large size tiers, now that
`BeesCrawl::fetch_extents` is no longer slowing it down.
* Add a debug stream interface which developers can easily turn on when
needed to inspect the decisions that extent scan is making.
* Track metrics that are more useful, particularly searches per extent
scanned, and fraction of extents that are skipped.
Zygo Blaxell [Tue, 28 Jan 2025 01:04:13 +0000 (20:04 -0500)]
btrfs-tree: harden `rlower_bound` against exceptional objects
Rearrange the logic in `rlower_bound` so it can cope with a tree
that contains mostly block-aligned objects, with a few exceptions
filtered out by `hdr_stop`.
Zygo Blaxell [Mon, 27 Jan 2025 07:10:39 +0000 (02:10 -0500)]
btrfs-tree: connect methods to the debug stream interface
In some cases functions already had existing debug stream support
which can be redirected to the new interface. In other cases, new
debug messages are added.
Zygo Blaxell [Sun, 26 Jan 2025 19:54:08 +0000 (14:54 -0500)]
btrfs-tree: drop BtrfsFsTreeFetcher and clean up class comments
BtrfsFsTreeFetcher was used for early versions of the extent scanner, but
neither subvol nor extent scan now needs an object that is both persistent
and configured to access only one subvol. BtrfsExtentDataFetcher does
the same thing in that case.
Clarify the comments on what the remaining classes do, so that
BtrfsFsTreeFetcher doesn't get inadvertently reinvented in the future.
Zygo Blaxell [Tue, 28 Jan 2025 00:54:07 +0000 (19:54 -0500)]
btrfs-tree: introduce BtrfsDataExtentTreeFetcher to read data extents without metadata
Binary searches can be extremely slow if the target bytenr is near a
metadata block group, because metadata items are not visible to the
binary search algorithm. In a non-mixed-bg filesystem, there can be
hundreds of thousands of metadata items between data extent items, and
since the binary search algorithm can't see them, it will run searches
that iterate over hundreds of thousands of objects about a dozen times.
This is less of a problem for mixed-bg filesystems because the data and
metadata blocks are not isolated from each other. The binary search
algorithm still can't see the metadata items, but there are usually
some data items close by to prevent the linear item filter from running
too long.
Introduce a new fetcher class (all the good names were taken) that tracks
where the end of the current block group is. When the end of the current
block group is reached in the linear search, skip ahead to a block group
that can contain data items.
Zygo Blaxell [Mon, 27 Jan 2025 16:39:36 +0000 (11:39 -0500)]
main: the base directory for `--strip-paths` should be root_fd, not cwd
The cwd is where core dumps and various profiling and verification
libraries want to write their data, whereas root_fd is the root of the
target filesystem. These are often intentionally different. When
they are different, `--strip-paths` sets the wrong prefix to strip
from paths.
Once the root fd has been established, we can set the path prefix to
the string prefix that we'll get from future calls to `name_fd`.
Zygo Blaxell [Mon, 27 Jan 2025 02:59:07 +0000 (21:59 -0500)]
hash: handle $BEESHOME on non-btrfs
bees explicitly supports storing $BEESHOME on another filesystem, and
does not require that filesystem to be btrfs; however, if $BEESHOME
is on a non-btrfs filesystem, there is an exception on every startup
when trying to identify the subvol root of the hash table file in order
to blacklist it, because non-btrfs filesystems don't have subvol roots.
Fix by checking not only whether $BEESHOME is on btrfs, but whether it
is on the _same_ btrfs, as the bees root, without throwing an exception.
The hash table is blacklisted only when both filesystems are btrfs and
have the same fsid.
Zygo Blaxell [Mon, 27 Jan 2025 00:18:21 +0000 (19:18 -0500)]
seeker: turn off debug logging
The debug log is only revealed when something goes wrong, but it is
created and discarded every time `seek_backward` is called, and it
is quite CPU-intensive.
Zygo Blaxell [Tue, 21 Jan 2025 03:48:25 +0000 (22:48 -0500)]
progress: adjust minimum thresholds for ETA to 10 seconds and 1 GiB of data
1% is a lot of data on a petabyte filesystem, and a long time to wait for an
ETA.
After 1 GiB we should have some idea of how fast we're reading the data.
Increase the time to 10 seconds to avoid a nonsense result just after a scan
starts.
Zygo Blaxell [Mon, 20 Jan 2025 05:15:38 +0000 (00:15 -0500)]
scripts/beesd: harden the mount options
* `nodev`: This reduces rename attack surface by preventing bees from
opening any device file on the target filesystem.
* `noexec`: This prevents access to the mount point from being leveraged
to execute setuid binaries, or execute anything at all through the
mount point.
These options are not required because they duplicate features in the
bees binary (assuming that the mount namespace remains private):
* `noatime`: bees always opens every file with `O_NOATIME`, making
this option redundant.
* `nosymfollow`: bees uses `openat2` on kernels 5.6 and later with
flags that prevent symlink attacks. `nosymfollow` was introduced in
kernel 5.10, so every kernel that can do `nosymfollow` can already do
`openat2`. Also, historically, `$BEESHOME` can be a relative path with
symlinks in any path component except the last one, and `nosymfollow`
doesn't allow that.
Between `openat2` and `nodev`, all symlink attacks are prevented, and
rename attacks cannot be used to force bees to open a device file.
Zygo Blaxell [Mon, 20 Jan 2025 05:24:25 +0000 (00:24 -0500)]
scripts/beesd: no need for `$BEESHOME` to be a subvol
We _recommend_ that `$BEESHOME` should be a subvol, and we'll create a
subvol if no directory exists; however, there's no reason to reject an
existing plain directory if the user chooses to use one.
Zygo Blaxell [Mon, 20 Jan 2025 02:13:21 +0000 (21:13 -0500)]
extent scan: make sure we run every extent crawler once per transaction
There's a pathological case where all of the extent scan crawlers except
one are at the end of a crawl cycle, but the one crawler that is still
running is keeping the Task queue full. The result is that bees never
starts the other extent scan crawlers, because the queue is always
full at the instant a new transid triggers the start of a new scan.
That's bad because it will result in bees falling behind when new data
from the inactive size tiers appears.
To fix this, check for throttling _after_ creating at least one scan task
in each crawler. That will keep the crawlers running, and possibly allow
them to claw back some space in the Task queue. It slightly overcommits
the Task queue, so there will be a few more Tasks than nominally allowed.
Also (re)introduce some hysteresis in the queue size limit and reduce it
a little, so that bees isn't continually stopping and restarting crawls
every time one task is created or completed, and so that we stay under
the configured Task limit despite overcommitting.
Kai Krakow [Sun, 30 Jun 2024 14:27:20 +0000 (16:27 +0200)]
context: demote "abandoned toxic match" to debug log level
This log message creates a overwhelmingly lot of messages in the system
journal, leading to write-back flushing storms under high activity. As
it is a work-around message, it is probably only useful to developers,
thus demote to debug level.
This fixes latency spikes in desktop usage after adding a lot of new
files, especially since systemd-journal starts to flush caches if it
sees memory pressure.
Zygo Blaxell [Sun, 12 Jan 2025 23:40:14 +0000 (18:40 -0500)]
task: fixes for priority and idle Tasks
Tasks are not allowed to be queued more than once, but it is allowed
to queue a Task while it's already running, which means a Task can be
executed on two threads in parallel. Tasks detect this and handle it
by queueing the Task on its own post-exec queue. That in turn leads
to Workers which continually execute the same Task if that Task doesn't
create any new Tasks, while other Tasks sit on the Master queue waiting
for a Worker to dequeue them.
For idle Tasks, we don't want the Task to be rescheduled immediately.
We want the idle Task to execute again after every available Task on
both the main and idle queues has been executed.
Fix these by having each Task reschedule itself on the appropriate
queue when it finishes executing.
Priority queued Tasks should executed in priority order not just one
Task's post-exec queue, but the entire local queue of the TaskConsumer.
Fix this by moving the sort into either the TaskConsumer that receives
a post-exec queue, if there is one, or into the Task that is created
to insert the post-exec queue into a TaskConsumer when one becomes
available in the future.
Zygo Blaxell [Sun, 12 Jan 2025 23:23:44 +0000 (18:23 -0500)]
Revert "roots: use a non-idle task for next_transid"
next_transid tasks don't respect queue selection very well, because
they effectively end up spinning in a loop until all other worker
threads become busy.
Back this out, and fix the priority handling in the Task library.
Zygo Blaxell [Sun, 12 Jan 2025 18:54:54 +0000 (13:54 -0500)]
task: flatten queues of dependent Tasks
Suppose Task A, B, and C are created in that order, and currently running.
Task T acquires Exclusion E. Task B, A, and C attempt to acquire the
same Exclusion, in that order, but fail because Task T holds it.
The result is Task T with a post-exec queue:
T, [ B, A, C ] sort_requested
Now suppose Task U acquires Exclusion F, then Task T attempts to acquire
Exclusion F. Task T fails to acquire F, so T is inserted into U's
post-exec queue. The result at the end of the execution of T is a tree:
U, [ T ] sort_requested
\-> [ B, A, C ] sort_requested
Task T exits after failing to acquire a lock. When T exits, T will
sort its post-exec queue and submit the post-exec queue for execution
immediately:
Worker 1: U, [ T ] sort_requested
Worker 2: A, B, C
This isn't ideal because T, A, B, and C all depend on at least one
common Exclusion, so they are likely to immediately conflict with T
when U exits and T runs again.
Ideally, A, B, and C would at least remain in a common queue with T,
and ideally that queue is sorted.
Instead of inserting T into U's post-exec queue, insert T and all
of T's post-exec queue, which creates a single flattened Task list:
U, [ T, B, A, C ] sort_requested
Then when U exits, it will sort [ T, B, A, C ] into [ A, B, C, T ],
and run all of the queued Tasks in age priority order:
Zygo Blaxell [Sun, 12 Jan 2025 04:21:31 +0000 (23:21 -0500)]
task: add an `insert` method for priority-queueing Tasks by age
Task started out as a self-organizing parallel-make algorithm, but ended
up becoming a half-broken wait-die algorithm. When a contended object
is already locked, Tasks enter a FIFO queue to restart and acquire the
lock. This is the "die" part of wait-die (all locks on an Exclusion are
non-blocking, so no Task ever does "wait"). The lock queue is FIFO wrt
_lock acquisition order_, not _Task age_ as required by the wait-die
algorithm.
Make it a 25%-broken wait-die algorithm by sorting the Tasks on lock
queues in order of Task ID, i.e. oldest-first, or FIFO wrt Task age.
This ensures the oldest Task waiting for an object is the one to get
it when it becomes available, as expected from the wait-die algorithm.
This should reduce the amount of time Tasks spend on the execution queue,
and reduce memory usage by avoiding the accumulation of Tasks that cannot
make forward progress.
Note that turning `TaskQueue` into an ordered container would have
undesirable side-effects:
* `std::list` has some useful properties wrt stability of object
location and cost of splicing. Other containers may not have these,
and `std::list` does have a `sort` method.
* Some Task objects are created at the beginning and reused continually,
but we really do want those Tasks to be executed in FIFO order wrt
submission, not Task ID. We can exclude these tasks by only doing the
sorting when a Task is queued for an Exclusin object.
Zygo Blaxell [Sat, 11 Jan 2025 07:09:30 +0000 (02:09 -0500)]
docs: expand "Threads and load management" to suggest not running bees so much
One of the more obvious ways to reduce bees load is to simply not run
it all the time. Explicitly state using maintenance windows as a load
management option.
SIGUSR1 and SIGUSR2 should have been documented somewhere else before now.
Better late than never.
Zygo Blaxell [Sat, 11 Jan 2025 06:29:16 +0000 (01:29 -0500)]
docs: config.md updates
The theories behind bees slowing down when presented with a larger has
table turned out to be wrong. The real cause was a very old bug which
submitted thousands of `LOGICAL_INO` requests when only a handful of
requests were needed.
"Compression on the filesystem" -> "Compression in files"
Don't be so "dramatic". Be "rapid" instead.
Remove "cannot avoid modifying read-only snapshots" as a distinction
between subvol and extent scans. Both modes support send workaround
and send waiting with no significant distinction.
Emphasize extent scan's better handling of many snapshots. Also reflinks.
Zygo Blaxell [Sat, 11 Jan 2025 05:41:32 +0000 (00:41 -0500)]
docs: update kernel bugs page for January 2025
"Kernel" -> "Linux kernel". If you can run bees on a kernel that isn't
Linux, congratulations!
Emphasize the age of the data corruption warnings. Once 5.4 reaches
EOL we can remove those.
Simplify the discussion of old kernels and API levels. There's a
new optional kernel API for `openat2` support at 5.6. The absolute
minimum kernel version is still 4.2, and will not increase to 4.15
until the subvol scanners are removed.
Remove discussion of bees support for kernels 4.19 (which recently
reached EOL) and earlier.
The `LOGICAL_INO` vs dedupe bug is actually a `LOGICAL_INO` vs clone bug.
Dedupe isn't necessary to reproduce it.
Remove a stray ')'.
Strip out most of the discussion of slow backrefs, as they are no longer a
concern on the range of supported kernel versions. Leave some description
there because bees still has some vestigial workarounds.
Remove `btrfs send` from the "Unfixed kernel bugs" section, which makes
the section empty, so remove the section too. bees now handles send on
a subvol reasonably well.
projects / bees / log