Zygo Blaxell [Tue, 7 Feb 2023 03:46:46 +0000 (22:46 -0500)]
roots: make sure transid_max's computed value isn't max
We check the result of transid_max_nocache(), but not the result of
transid_max(). The latter is a computed result that is even more likely
to be wrong[citation needed].
Zygo Blaxell [Tue, 21 Feb 2023 04:44:20 +0000 (23:44 -0500)]
fs: allow BtrfsIoctlLogicalInoArgs to be reused, remove virtual methods
Some malloc implementations will try to mmap() and munmap() large buffers
every time they are used, causing a severe loss of performance.
Nothing ever overrode the virtual methods, and there was no virtual
destructor, so they cause compiler warnings at build time when used with
a template that tries to delete pointers to them.
Zygo Blaxell [Fri, 24 Feb 2023 03:33:35 +0000 (22:33 -0500)]
ProgressTracker: reduce memory usage with long-running work items
ProgressTracker was only freeing memory for work items when they reach
the head of the work tracking queue. If the first work item takes
hours to complete, and thousands of items are processed every second,
this leads to millions of completed items tracked in memory at a time,
wasting gigabytes of system RAM.
Rewrite ProgressHolderState methods to keep only incomplete work items
in memory, regardless of the order in which they are added or removed.
Also fix the unit tests which were relying on the memory leak to work,
and add test cases for code coverage.
Zygo Blaxell [Mon, 20 Feb 2023 16:13:18 +0000 (11:13 -0500)]
roots: don't share a RootFetcher between threads
If the send workaround is enabled, it is possible for two threads (a
thread running the crawl_new task, and a thread attempting to apply the
send workaround) to access the same RootFetcher object at the same time.
That never ends well.
Give each function its own BtrfsRootFetcher object.
Zygo Blaxell [Mon, 23 Jan 2023 04:44:51 +0000 (23:44 -0500)]
hash: flush the table more slowly
With SIGTERM and fast exit, the trickle writeback is less important.
We don't want to flood people's IO subsystems with continuous writes.
This really should be configurable at runtime.
Zygo Blaxell [Tue, 14 Dec 2021 06:18:39 +0000 (01:18 -0500)]
fd: FS_IOC_SETFLAGS takes an int* argument not a long*
According to ioctl_iflags(2):
The type of the argument given to the FS_IOC_GETFLAGS and
FS_IOC_SETFLAGS operations is int *, notwithstanding the
implication in the kernel source file include/uapi/linux/fs.h
that the argument is long *.
Zygo Blaxell [Thu, 4 Nov 2021 05:48:53 +0000 (01:48 -0400)]
fiemap, fiewalk: drop dead example/test code
These tools are obsolete. fiemap was a thin wrapper around FIEMAP,
but FIEMAP is not useful on btrfs. fiewalk was a thin wrapper around
BtrfsExtentWalker, but development on BtrfsExtentWalker has been
abandoned.
Zygo Blaxell [Thu, 19 Jan 2023 14:24:48 +0000 (09:24 -0500)]
hash: don't spin when writes fail
When a hash table write fails, we skip over the write throttling because
we didn't report that we successfully wrote an extent. This can be bad
if the filesystem is full and the allocations for writes are burning a
lot of CPU time searching for free space.
We also don't retry the write later on since we assume the extent is
clean after a write attempt whether it was successful or not, so the
extent might not be written out later when writes are possible again.
Check whether a hash extent is dirty, and always throttle after
attempting the write.
If a write fails, leave the extent dirty so we attempt to write it out
the next time flush cycles through the hash table. During shutdown
this will reattempt each failing write once, after that the updated hash
table data will be dropped.
Zygo Blaxell [Fri, 30 Dec 2022 19:36:55 +0000 (14:36 -0500)]
readahead: report the original size in BEESTOOLONG
BEESTOOLONG was always reporting a size of zero, and the offset of the
end of the readahead region. Report the original size instead (and also
in BEESTRACE and BEESNOTE).
Zygo Blaxell [Thu, 29 Dec 2022 09:02:41 +0000 (04:02 -0500)]
task: use pthread_setname_np correctly
It turns out I've been using pthread_setname_np wrong the whole time:
* on Linux, the thread name length is 15 characters.
TASK_COMM_LEN is 16 bytes, and the last one is always 0.
This is now hardcoded in many places and cannot be changed.
* pthread_setname_np doesn't return -errno, so DIE_IF_MINUS_ERRNO
was the wrong macro. On the other hand, we never want to do anything
differently when pthread_setname_np fails, so we never needed to
check the return value.
Also, libc silently ignores attempts to set the thread name when it is too
long. That's almost certainly a libc bug, but libc probably suppresses
the error result for the same reasons I ignore the error result.
Wrap the pthread_setname function with a C++ std::string overload that
truncates the argument at 15 characters, so we at least get the first
part of the task name in the thread name field. Later commits can deal
with making the bees thread names shorter.
Zygo Blaxell [Thu, 22 Dec 2022 05:07:49 +0000 (00:07 -0500)]
context: don't forget to retry locked extents
The caller of scan_forward has to stop advancing the BeesFileCrawl
position when an extent lock blocks a scan, so that it will resume
from the same position when the Task is scheduled again; otherwise,
bees simply skips over the extent and leave it incompletely deduped.
Zygo Blaxell [Wed, 30 Nov 2022 03:44:42 +0000 (22:44 -0500)]
roots: replace BEES_TRANSID_FACTOR with BEES_TRANSID_POLL_INTERVAL
Restart crawl_more (and update crawl roots and flush FD caches) every
time the transid changes, and only when the transid changes, but
not more often than a reasonable minimum poll interval.
Clean up the log message: use the proper thread name and remove
the wildly inaccurate estimate of when crawl will resume.
Zygo Blaxell [Fri, 3 Dec 2021 04:56:46 +0000 (23:56 -0500)]
roots: run insert_new_crawl from within a Task
If we have loadavg targeting enabled, there may be no worker threads
available to respond to new subvols, so we should not bother updating
the subvols list.
Put insert_new_crawl into a Task so it only executes when a worker
is available.
Zygo Blaxell [Mon, 19 Dec 2022 05:19:18 +0000 (00:19 -0500)]
roots: disable recent sorting by max_transid
On large filesystems where the min_transid of all subvols gets stuck at 0,
bees may lose the ability to effectively track recent data. A secondary sort
by max_transid will allow scanning newer subvols that were created after bees
started running on the filesystem, but before bees completed the first scan
of all subvols.
On the other hand, the secondary sort does a reverse version of the
sequential scan mode, and the sequential scan mode is simply awful.
Zygo Blaxell [Mon, 14 Nov 2022 18:01:41 +0000 (13:01 -0500)]
roots: reimplement scan modes using virtual base and methods
Split each scan mode into two distinct phases:
1. A heavy discovery phase, where we search the entire filesystem
for something (new items in subvol trees in this case).
2. A light consuming phase, where we fetch extents to dedupe
from places that we found in the discovery phase.
Part 1 recomputes the subvol ordering every time there is a new transid.
For some scan modes this computation is quite expensive, far too costly
to pay for every extent, so we do it no more than once per transaction.
Part 2 is run every time a worker thread hits the crawl_more Task.
It simply pulls one extent from the first crawler off a sorted list,
removing the crawler from the list when the crawler runs out of data.
Part 1 creates a new structure and swaps it into place, while Part 2
continues to run using the previous strucuture. Neither of these
need to block the other, so they don't.
The separate class and base pointer also make it easer to add new scan
modes that are not based on subvol trees or that don't use BeesCrawl.
While we're here, fix up some method visibility in BeesRoots.
Zygo Blaxell [Mon, 29 Nov 2021 05:41:29 +0000 (00:41 -0500)]
roots: add 'recent' crawl mode for a mix of new and old data
Crawl mode 3 'recent' prioritizes data from new updates to previously
scanned subvols over subvols that have not been completely scanned yet.
If no such new data exists, falls back to a variation of 'lockstep'
scan mode.
This enables us to keep up with new data as it arrives, a key weakness
of all the other scan modes, and worth violating our unwritten "no new
scan modes until we have extent-tree dedupe working" policy for.
Zygo Blaxell [Sun, 20 Nov 2022 17:01:16 +0000 (12:01 -0500)]
context: don't let multiple worker Tasks get stuck on a single extent or inode
When two Tasks attempt to lock the same extent, append the later Task
to the earlier Task's post-exec work queue. This will guarantee that
all Tasks which attempt to manipulate the same extent will execute
sequentially, and free up threads to process other extents.
Similarly, if two scanner threads operate on the same inode, any dedupe
they perform will lock out other scanner threads in btrfs. Avoid this
by serializing Task objects that reference the same file.
This does theoretically use an unbounded amount of memory, but in practice
a Task that encounters a contended extent or inode quickly stops spawning
new Tasks that might increase the queue size, and all Tasks that might
contend for the same lock(s) end up on a single FIFO queue.
Note that the scope of inode locks is intentionally global, i.e. when
an inode is locked, it locks every inode with the same number in every
subvol. This avoids significant lock contention and task queue growth
when the same inode with the same file extents appear in snapshots.
Zygo Blaxell [Wed, 1 Dec 2021 19:42:42 +0000 (14:42 -0500)]
roots: organize scan workers by inode instead of extent
Split crawlers into two separate Tasks:
1. a Task which locates the next inode with a new data extent.
2. a Task which scans every new extent in that inode.
This simplifies some lock contention and execution ordering issues.
Files are read sequentially. Workers dynamically scale up or
down as needed, without creating thousands of deferred Task objects.
Workers obtain inode locks for different inodes in btrfs, so they
can work in parallel instead of waiting for each other.
This change in behavior comes with new names for the worker Tasks:
"crawl_master" is now "crawl_more", the singular Task which
creates inode-scanning Tasks.
Zygo Blaxell [Wed, 24 Oct 2018 05:43:22 +0000 (01:43 -0400)]
roots: use symbolic names for SCAN_MODEs
This was done on the development branch three years ago, and
has been creating annoying merge conflicts ever since. Sync
up the branches so they have the same names for these.
Zygo Blaxell [Tue, 14 Dec 2021 04:56:44 +0000 (23:56 -0500)]
bytevector: add some fugly mutexes
We are using ByteVectors from multiple threads in some cases. Mostly
these are the status and progress threads which read the ByteVector
object references embedded in BEESNOTE macros.
Since it's not clear what the data race implications are, protect
the shared_ptr in ByteVector with a mutex for now.
Zygo Blaxell [Sat, 19 Nov 2022 07:00:17 +0000 (02:00 -0500)]
bees: drop the balance/logical workaround that has been disabled for two years
Kernels that needed the balance workaround frankly are too buggy
to run bees at all. The workaround also makes the locking stories
around logical_ino calls and process exit complicated, so get rid of
it completely.
Zygo Blaxell [Sat, 19 Nov 2022 07:45:15 +0000 (02:45 -0500)]
context: speed up orderly process termination
Quite often bees exceeds its service timeout for termination because
it is waiting for a loop embedded in a Task to finish some long-running
btrfs operation. This can cause bees to be aborted by SIGKILL before
it can completely flush the hash table or save crawl state.
There are only two important things SIGTERM does when bees terminates:
1. Save crawl progress
2. Flush out the hash table
Everything else is automatically handled by the kernel when the process
is terminated by SIGKILL, so we don't have to bother doing it ourselves.
This can save considerable time at shutdown since we don't have to wait
for every thread to reach a point where it becomes idle, or force loops
to terminate by throwing exceptions, or check a condition every time we
access a pointer. Instead, we need do only the things in the list
above, and then call _exit() to clean up everything else.
Hash table and crawl state writeback can happen in their background
threads instead of the foreground one. Separate the "stop" method for
these classes into "stop_request" and "stop_wait" so that these writebacks
can run at the same time.
Deprecate and remove all references to the BeesHalt exception, and remove
several unnecessary checks for BeesContext::stop_requested.
Pause the task queue instead of cancelling it, which preserves the
crawl progress state and stops new Tasks from competing for iops and
CPU during writeback.
Zygo Blaxell [Mon, 5 Dec 2022 05:22:29 +0000 (00:22 -0500)]
context: dump current load tracking stats
Dump the instantaneous load (last 5 seconds, extracted from load average)
and the computed target worker count (before rounding and truncation)
on the same status line as the task and worker thread count.
This should give better visibility into Task's thread count calculation
algorithm.
Zygo Blaxell [Mon, 5 Dec 2022 04:56:35 +0000 (23:56 -0500)]
task: use exponential backoff algorithm to set thread count
Tasks are often running longer than 5 seconds (especially extents with
multiple references requiring copy operations), so the load tracking
algorithm needs to average several samples over a longer period of time
than 5 seconds. If the sample period is 60 seconds, we end up recomputing
the original load average from current_load, so skip the rounding error
and use the original load average value.
Arguably the real fix is to break up the more complex extent operations
over several downstream Task objects, but that's a more significant
design change.
Tweak the attack and decay rates so that threads are started a little
more slowly, but still stopped rapidly when load spikes up.
Remove the hysteresis to provide support for load average targets
below 1, or with fractional components, with a PWM-like effect.
Zygo Blaxell [Sun, 18 Dec 2022 05:30:37 +0000 (00:30 -0500)]
task: rescue post-exec queue on Task destruction
task1.append(task2) is supposed to run task2 after task1 is executed;
however, if task1 was just executed, and its last reference was owned by
a TaskConsumer, then task2 will be appended to a Task that will never
run again.
A similar problem arises in Exclusion, which can cause blocked tasks
to occasionally be dropped without executing them.
Zygo Blaxell [Tue, 7 Dec 2021 05:17:57 +0000 (00:17 -0500)]
task: don't hold the mutex while disposing of pending Tasks
In the event that someday Barrier allows users to force execution of
its pending tasks prior to the destruction of the BarrierState object,
we'll be ready to submit those Tasks for execution without waiting for
the BarrierState mutex lock.
Zygo Blaxell [Wed, 30 Nov 2022 03:06:54 +0000 (22:06 -0500)]
task: get rid of separate Exclusion and ExclusionState
Exclusion was generating a new Task every time a lock was contended.
That results in thousands of empty Task objects which contain a single
Task item.
Get rid of ExclusionState. Exclusion is now a simple weak_ptr to a Task.
If the weak_ptr is expired, the Exclusion is unlocked. If the weak_ptr
is not expired, it points to the Task which owns the Exclusion.
try_lock now appends the Task attempting to lock the Exclusion directly
to the owning Task, eliminating the need for Exclusion to have one.
This also removes the need to call insert_task separately, though
insert_task remains for other use cases.
With no ExclusionState there is no need for a string argument to
Exclusion's constructor, so get rid of that too.
Zygo Blaxell [Thu, 17 Nov 2022 04:46:14 +0000 (23:46 -0500)]
bees: use MultiLocker to serialize dedupe and logical_ino
In current kernels there is a bug which leads to an infinite loop in
add_all_parents(). The bug is triggered by one thread running dedupe
while another runs logical_ino.
Work around this by ensuring that bees process never runs dedupe and
logical_ino ioctls at the same time. Any number of either can run
at the same time, but not one of both.
For performance or workaround reasons we sometimes have to avoid doing
two conflicting operations at the same time, but we can still run any
number of non-conflicting operations in parallel.
MultiLocker (suggestions for a better class name welcome) blocks the
calling thread until there are no threads attempting to run a conflicting
operation.
Zygo Blaxell [Sun, 27 Nov 2022 03:45:24 +0000 (22:45 -0500)]
bees: drop bees_sync, we will not need it
bees_sync() was an exception-trapping wrapper around fsync() which is
not needed in any of the contexts from which it was called:
1. dedupe operations implicitly flush the src data, so there is
no need to call fsync() to do that twice.
2. crawl position is written to a temporary file and renamed
over the original, which always forces a flush when the original
exists. On the first write, where there is no original, a
crash would result in starting over with an empty or hole-filled
beescrawl file, which is the initial state of bees. There is also
a long history of kernel bugs triggered by fsync() in this case.
3. we use unreadahead to trigger writeback for flushing the
hash table to persistent storage. Here is a space where we might
use fsync after all, as part of bees_unreadahead's emulation of
POSIX_FADV_DONTNEED, but we need to get read-once behavior from
the scanner before we can use this capability.
Zygo Blaxell [Sun, 27 Nov 2022 04:16:13 +0000 (23:16 -0500)]
roots: correctly track crawl dirty state
If there's an error while writing the crawl state, the state should
remain dirty. If the crawl state is successfully written, the state
is only clean if there were no changes to crawl state since the write
was committed. We need to release the lock while writing the state but
correctly set the dirty flag when the state is written successfully.
Replace the bool with a version number counter. Track the last version
successfully saved and the current version of the crawl state. The state
is dirty if these counters disagree and clean if they agree.
Zygo Blaxell [Sun, 20 Nov 2022 00:18:29 +0000 (19:18 -0500)]
namedptr: add some doxygen, fix the #endif comment
Document the overall purpose of the class and what some of the methods do,
particularly the ones with terrible names like 'insert_item' (which only
inserts an item after calling the Function).
projects / bees / log