Kent Overstreet [Sat, 21 May 2022 17:10:39 +0000 (13:10 -0400)]
bcachefs: Fix journal_keys_search() overhead
Previously, on every btree_iter_peek() operation we were searching the
journal keys, doing a full binary search - which was slow.
This patch fixes that by saving our position in the journal keys, so
that we only do a full binary search when moving our position backwards
or a large jump forwards.
Signed-off-by: Kent Overstreet <kent.overstreet@gmail.com>
Kent Overstreet [Tue, 24 May 2022 02:37:01 +0000 (22:37 -0400)]
bcachefs: Fix encryption path on arm
flush_dcache_page() is not a noop on arm, but we were using
virt_to_page() instead of vmalloc_to_page() for an address on the kernel
stack - vmalloc memory, leading to an oops in flush_dcache_page().
Signed-off-by: Kent Overstreet <kent.overstreet@gmail.com>
Kent Overstreet [Sat, 14 May 2022 11:00:22 +0000 (07:00 -0400)]
bcachefs: Switch to key_type_user, not logon
The only difference key_type_logon and key_type_user is that
key_type_logon keys can't be read by userspace.
However, userspace has actually been adding keys to both the logon and
user keychains, because userspace fsck requires the keychain interface -
so we might as well just use user and drop the logon keychain.
Signed-off-by: Kent Overstreet <kent.overstreet@gmail.com>
Kent Overstreet [Mon, 25 Apr 2022 03:03:02 +0000 (23:03 -0400)]
bcachefs: Fix extent merging
When merging extents, we have to check that we won't overflow size
fields in any CRC entries - but the check for this was wrong, because in
the loop it was in we weren't keeping a pointer to the (packed, encoded)
CRC field.
Fix this by moving it to its own loop.
Signed-off-by: Kent Overstreet <kent.overstreet@gmail.com>
Kent Overstreet [Tue, 19 Apr 2022 03:43:08 +0000 (23:43 -0400)]
bcachefs: Improve invalid bkey error message
Bkeys have gotten a lot bigger since this code was written and now are
often formatted across multiple lines - while the reason a bkey is
invalid will still be short and fit on a single line. This patch prints
the error bfore the bkey, making it a bit more readable.
Signed-off-by: Kent Overstreet <kent.overstreet@gmail.com>
Kent Overstreet [Thu, 21 Apr 2022 04:34:58 +0000 (00:34 -0400)]
bcachefs: Fix journal_iters_fix()
journal_iters_fix() was incorrectly rewinding iterators past keys they
had already returned, leading to those keys being double counted in the
bch2_gc() path - oops.
Signed-off-by: Kent Overstreet <kent.overstreet@gmail.com>
Kent Overstreet [Thu, 21 Apr 2022 17:13:57 +0000 (13:13 -0400)]
bcachefs: Go RW before bch2_check_lrus()
btree updates before going RW are expensive if they're in random order,
since they use the list of keys for journal replay to insert, which is
just a gap buffer.
This patch improves the bucket invalidate path so that if
bch2_check_lrus() hasn't finished it only prints warnings instead of
doing an emergency shutdown, which means we can now set BCH_FS_MAY_GO_RW
before bch2_check_lrus().
Also, the filesystem state bits are reorganized a bit.
Signed-off-by: Kent Overstreet <kent.overstreet@gmail.com>
Kent Overstreet [Sun, 17 Apr 2022 21:30:49 +0000 (17:30 -0400)]
bcachefs: Shutdown path improvements
We're seeing occasional firings of the assertion in the key cache
shutdown code that nr_dirty == 0, which means we must sometimes be doing
transaction commits after we've gone read only.
Cleanups & changes:
- BCH_FS_ALLOC_CLEAN renamed to BCH_FS_CLEAN_SHUTDOWN
- new helper bch2_btree_interior_updates_flush(), which returns true if
it had to wait
- bch2_btree_flush_writes() now also returns true if there were btree
writes in flight
- __bch2_fs_read_only now checks if btree writes were in flight in the
shutdown loop: btree write completion does a transaction update, to
update the pointer in the parent node
- assert that !BCH_FS_CLEAN_SHUTDOWN in __bch2_trans_commit
Signed-off-by: Kent Overstreet <kent.overstreet@gmail.com>
Kent Overstreet [Sun, 17 Apr 2022 21:50:47 +0000 (17:50 -0400)]
bcachefs: Allocate some extra room in btree_key_cache_fill()
If we allocate a buffer that's a bit bigger than necessary the
transaction commit path will be much less likely to have to reallocate -
which requires a transaction restart.
Signed-off-by: Kent Overstreet <kent.overstreet@gmail.com>
Kent Overstreet [Tue, 12 Apr 2022 22:04:08 +0000 (18:04 -0400)]
bcachefs: bch2_btree_iter_peek_all_levels()
This adds bch2_btree_iter_peek_all_levels(), which returns keys from
every level of the btree - interior nodes included - in monotonically
increasing order, soon to be used by the backpointers check & repair
code.
- BTREE_ITER_ALL_LEVELS can now be passed to for_each_btree_key() to
iterate thusly, much like BTREE_ITER_SLOTS
- The existing algorithm in bch2_btree_iter_advance() doesn't work with
peek_all_levels(): we have to defer the actual advancing until the
next time we call peek, where we have the btree path traversed and
uptodate. So, we add an advanced bit to btree_iter; when
BTREE_ITER_ALL_LEVELS is set bch2_btree_iter_advanced() just marks
the iterator as advanced.
Signed-off-by: Kent Overstreet <kent.overstreet@linux.dev>
Kent Overstreet [Thu, 14 Apr 2022 19:45:00 +0000 (15:45 -0400)]
bcachefs: bch2_btree_iter_peek_slot() now works on interior nodes
The new backpointers code will be using bch2_btree_iter_peek_slot() on
interior nodes - this patch updates peek_slot() to make that work.
- Pass the correct level to bch2_journal_keys_peek_slot()
- We should only set BTREE_ITER_CACHED or BTREE_ITER_WITH_KEY_CACHE
when using bch2_trans_iter_init(), not bch2_trans_node_iter_init()
- Update assertions
Signed-off-by: Kent Overstreet <kent.overstreet@gmail.com>
Kent Overstreet [Thu, 14 Apr 2022 19:37:16 +0000 (15:37 -0400)]
bcachefs: btree_update_interior.c prep for backpointers
Previously, btree_update_interior.c passed keys to bch2_trans_mark_*
that hadn't been fully initialized - they didn't have the key field
filled out, just the value.
With backpointers, we need to make sure keys are fully initialized
before marking them - because the backpointer points back to the
original key.
This patch tweaks the interior update paths to fix this.
Signed-off-by: Kent Overstreet <kent.overstreet@gmail.com>
Kent Overstreet [Tue, 12 Apr 2022 17:09:09 +0000 (13:09 -0400)]
bcachefs: In fsck, pass BTREE_UPDATE_INTERNAL_SNAPSHOT_NODE when deleting dirents
A user reported an error where we hit an assertion due to deleting a key
in an internal snapshot node, when deleting a dirent that points to a
nonexisting inode.
We try to avoid doing updates to keys for internal snapshot nodes, but
upon inspection of the places where we remove dirents in fsck it appears
BTREE_UPDATE_INTERNAL_SNAPSHOT_NODE is correct for all of them: either
the target dirent doesn't exist, or it's a directory with multiple
dirents pointing to it.
Signed-off-by: Kent Overstreet <kent.overstreet@gmail.com>
Kent Overstreet [Tue, 12 Apr 2022 05:31:33 +0000 (01:31 -0400)]
bcachefs: Fix for getting stuck in journal replay
In journal replay, we weren't immediately dropping journal pins when we
start doing updates that ewern't from journal replay - leading to
journal reclaim getting stuck.
Signed-off-by: Kent Overstreet <kent.overstreet@gmail.com>
When we detect a filesystem inconsistency, we should include the
relevent keys in the error message. This patch adds a parameter to pass
the key with the lru entry to bch2_lru_delete(), so that it can be
printed.
Signed-off-by: Kent Overstreet <kent.overstreet@gmail.com>
When many journal replay keys have been overwritten,
bch2_journal_keys_peek() was taking excessively long to scan before it
found a key to return.
Fix this by introducing bch2_journal_keys_peek_upto() which takes a
parameter for the end of the range we want, so that we can terminate the
search much sooner, and replace all uses of bch2_journal_keys_peek()
with peek_upto() or peek_slot().
Signed-off-by: Kent Overstreet <kent.overstreet@gmail.com>
Kent Overstreet [Mon, 11 Apr 2022 21:23:39 +0000 (17:23 -0400)]
bcachefs: Improve error message when alloc key doesn't match lru entry
Error messages should always print out the full key when available -
this gives us a starting point when looking through the journal to debug
what went wrong.
Signed-off-by: Kent Overstreet <kent.overstreet@gmail.com>
Kent Overstreet [Sun, 10 Apr 2022 20:26:34 +0000 (16:26 -0400)]
bcachefs: Fix CPU usage in journal read path
In journal_entry_add(), we were repeatedly scanning the journal entries
radix tree to scan for old entries that can be freed, with O(n^2)
behaviour. This patch tweaks things to remember the previous last_seq,
so we don't have to scan for entries to free from the start.
Signed-off-by: Kent Overstreet <kent.overstreet@gmail.com>
Kent Overstreet [Sun, 10 Apr 2022 04:48:36 +0000 (00:48 -0400)]
bcachefs: Don't trigger extra assertions in journal replay
We now pass a rw argument to .key_invalid methods so they can trigger
assertions for updates but not on existing keys. We shouldn't trigger
these extra assertions in journal replay - this patch changes the
transaction commit path accordingly.
Signed-off-by: Kent Overstreet <kent.overstreet@gmail.com>
Kent Overstreet [Sat, 9 Apr 2022 19:15:36 +0000 (15:15 -0400)]
bcachefs: Minor device removal fixes
- We weren't clearing the LRU btree
- bch2_alloc_read() runs before bch2_check_alloc_key() deletes alloc
keys for devices/buckets that don't exists, so it needs to check for
that
- bch2_check_lrus() needs to check that buckets exists
- improve some error messages
Signed-off-by: Kent Overstreet <kent.overstreet@gmail.com>
Kent Overstreet [Sat, 9 Apr 2022 05:23:50 +0000 (01:23 -0400)]
bcachefs: Initialize ec work structs early
We need to ensure that work structs in bch_fs always get initialized -
otherwise an error in filesystem initialization can pop a warning in the
workqueue code when we try to cancel a work struct that wasn't
initialized.
Signed-off-by: Kent Overstreet <kent.overstreet@gmail.com>
Kent Overstreet [Mon, 21 Mar 2022 04:15:53 +0000 (00:15 -0400)]
bcachefs: Use a genradix for reading journal entries
Previously, the journal read path used a linked list for storing the
journal entries we read from disk. But there's been a bug that's been
causing journal_flush_delay to incorrectly be set to 0, leading to far
more journal entries than is normal being written out, which then means
filesystems are no longer able to start due to the O(n^2) behaviour of
inserting into/searching that linked list.
Fix this by switching to a radix tree.
Signed-off-by: Kent Overstreet <kent.overstreet@gmail.com>
Kent Overstreet [Fri, 1 Apr 2022 05:29:59 +0000 (01:29 -0400)]
bcachefs: Fold bucket_state in to BCH_DATA_TYPES()
Previously, we were missing accounting for buckets in need_gc_gens and
need_discard states. This matters because buckets in those states need
other btree operations done before they can be used, so they can't be
conuted when checking current number of free buckets against the
allocation watermark.
Also, we weren't directly counting free buckets at all. Now, data type 0
== BCH_DATA_free, and free buckets are counted; this means we can get
rid of the separate (poorly defined) count of unavailable buckets.
This is a new on disk format version, with upgrade and fsck required for
the accounting changes.
Signed-off-by: Kent Overstreet <kent.overstreet@gmail.com>
Kent Overstreet [Thu, 7 Apr 2022 21:41:02 +0000 (17:41 -0400)]
bcachefs: Topology repair fixes
- We were failing to start topology repair, because we hadn't set the
superblock flag indicating it needed to run
- set_node_min() forget to update the btree node's key
- bch2_gc_alloc_reset() didn't reset data type, leading to inserting an
invalid key that was empty but had nonzero data type
Signed-off-by: Kent Overstreet <kent.overstreet@gmail.com>
Kent Overstreet [Wed, 6 Apr 2022 21:22:47 +0000 (17:22 -0400)]
bcachefs: Check for read_time == 0 in bch2_alloc_v4_invalid()
We've been seeing this error in fsck and we weren't able to track down
where it came from - but now that .key_invalid methods take a rw
argument, we can safely check for this.
Signed-off-by: Kent Overstreet <kent.overstreet@gmail.com>
Kent Overstreet [Wed, 6 Apr 2022 18:35:10 +0000 (14:35 -0400)]
bcachefs: fsck: Work around transaction restarts
In check_extents() and check_dirents(), we're working towards only
handling transaction restarts in one place, at the top level - but we're
not there yet. check_i_sectors() and check_subdir_count() handle
transaction restarts locally, which means the iterator for the
dirent/extent is left unlocked (should_be_locked == 0), leading to
asserts popping when we go to do updates.
This patch hacks around this for now, until we can delete the offending
code.
Signed-off-by: Kent Overstreet <kent.overstreet@gmail.com>
Kent Overstreet [Mon, 4 Apr 2022 01:50:25 +0000 (21:50 -0400)]
bcachefs: Add rw to .key_invalid()
This adds a new parameter to .key_invalid() methods for whether the key
is being read or written; the idea being that methods can do more
aggressive checks when a key is newly created and being written, when we
wouldn't want to delete the key because of those checks.
Signed-off-by: Kent Overstreet <kent.overstreet@gmail.com>
Kent Overstreet [Tue, 5 Apr 2022 17:44:18 +0000 (13:44 -0400)]
bcachefs: More improvements for alloc info checks
- Move checks for whether the device & bucket are valid from the
.key_invalid method to bch2_check_alloc_key(). This is because
.key_invalid() is called on keys that may no longer exist (post
journal replay), which is a problem when removing/resizing devices.
- We weren't checking the need_discard btree to ensure that every set
bucket has a corresponding alloc key. This refactors the code for
checking the freespace btree, so that it now checks both.
Signed-off-by: Kent Overstreet <kent.overstreet@gmail.com>
Kent Overstreet [Mon, 4 Apr 2022 05:09:26 +0000 (01:09 -0400)]
bcachefs: Gap buffer for journal keys
Btree updates before we go RW work by inserting into the array of keys
that journal replay will insert - but inserting into a flat array is
O(n), meaning if btree_gc needs to update many alloc keys, we're O(n^2).
Fortunately, the updates btree_gc does happens in sequential order,
which means a gap buffer works nicely here - this patch implements a gap
buffer for journal keys.
Signed-off-by: Kent Overstreet <kent.overstreet@gmail.com>
Kent Overstreet [Mon, 4 Apr 2022 00:36:32 +0000 (20:36 -0400)]
bcachefs: Don't normalize to pages in btree cache shrinker
This behavior dates from the early, early days of bcache, and upon
further delving appears to not make any sense. The shrinker only works
in terms of 'objects' of unknown size; normalizing to pages only had the
effect of changing the batch size, which we could do directly - if we
wanted; we probably don't. Normalizing to pages meant our batch size was
very small, which seems to have been keeping us from doing as much
shrinking as we should be under heavy memory pressure; this patch
appears to alleviate some OOMs we've been seeing.
Signed-off-by: Kent Overstreet <kent.overstreet@gmail.com>
With printbufs, it's now easy to build up multi-line log messages and
emit them with one call, which is good because it prevents multiple
multi-line log messages from getting Interspersed in the log buffer;
this patch also improves the formatting and converts it to latest style.
Signed-off-by: Kent Overstreet <kent.overstreet@gmail.com>
Kent Overstreet [Mon, 14 Feb 2022 05:07:38 +0000 (00:07 -0500)]
bcachefs: Kill struct bucket_mark
This switches struct bucket to using a lock, instead of cmpxchg. And now
that the protected members no longer need to fit into a u64, we can
expand the sector counts to 32 bits.
Signed-off-by: Kent Overstreet <kent.overstreet@linux.dev>
Kent Overstreet [Fri, 11 Feb 2022 00:09:40 +0000 (19:09 -0500)]
bcachefs: bch2_dev_usage_update() no longer depends on bucket_mark
This is one of the last steps in getting rid of the main in-memory
bucket array.
This changes bch2_dev_usage_update() to take bkey_alloc_unpacked instead
of bucket_mark, and for the places where we are in fact working with
bucket_mark and don't have bkey_alloc_unpacked, we add a wrapper that
takes bucket_mark and converts to bkey_alloc_unpacked.
Signed-off-by: Kent Overstreet <kent.overstreet@linux.dev>
Kent Overstreet [Thu, 10 Feb 2022 23:18:41 +0000 (18:18 -0500)]
bcachefs: New bucket invalidate path
In the old allocator code, preparing an existing empty bucket was part
of the same code path that invalidated buckets containing cached data.
In the new allocator code this is no longer the case: the main allocator
path finds empty buckets (via the new freespace btree), and can't
allocate buckets that contain cached data.
We now need a separate code path to invalidate buckets containing cached
data when we're low on empty buckets, which this patch implements. When
the number of free buckets decreases that triggers the new invalidate
path to run, which uses the LRU btree to pick cached data buckets to
invalidate until we're above our watermark.
Signed-off-by: Kent Overstreet <kent.overstreet@linux.dev>
Kent Overstreet [Thu, 10 Feb 2022 09:32:19 +0000 (04:32 -0500)]
bcachefs: New discard implementation
In the old allocator code, buckets would be discarded just prior to
being used - this made sense in bcache where we were discarding buckets
just after invalidating the cached data they contain, but in a
filesystem where we typically have more free space we want to be
discarding buckets when they become empty.
This patch implements the new behaviour - it checks the need_discard
btree for buckets awaiting discards, and then clears the appropriate
bit in the alloc btree, which moves the buckets to the freespace btree.
Additionally, discards are now enabled by default.
Signed-off-by: Kent Overstreet <kent.overstreet@linux.dev>
Kent Overstreet [Mon, 10 Jan 2022 01:48:31 +0000 (20:48 -0500)]
bcachefs: Kill allocator threads & freelists
Now that we have new persistent data structures for the allocator, this
patch converts the allocator to use them.
Now, foreground bucket allocation uses the freespace btree to find
buckets to allocate, instead of popping buckets off the freelist.
The background allocator threads are no longer needed and are deleted,
as well as the allocator freelists. Now we only need background tasks
for invalidating buckets containing cached data (when we are low on
empty buckets), and for issuing discards.
Signed-off-by: Kent Overstreet <kent.overstreet@linux.dev>
Kent Overstreet [Sat, 1 Jan 2022 01:03:29 +0000 (20:03 -0500)]
bcachefs: KEY_TYPE_alloc_v4
This introduces a new alloc key which doesn't use varints. Soon we'll be
adding backpointers and storing them in alloc keys, which means our
pack/unpack workflow for alloc keys won't really work - we'll need to be
mutating alloc keys in place.
Instead of bch2_alloc_unpack(), we now have bch2_alloc_to_v4() that
converts older types of alloc keys to v4 if needed.
Signed-off-by: Kent Overstreet <kent.overstreet@linux.dev>
Kent Overstreet [Mon, 31 Oct 2022 20:13:05 +0000 (16:13 -0400)]
bcachefs: Run btree updates after write out of write_point
In the write path, after the write to the block device(s) complete we
have to punt to process context to do the btree update.
Instead of using the work item embedded in op->cl, this patch switches
to a per write-point work item. This helps with two different issues:
- lock contention: btree updates to the same writepoint will (usually)
be updating the same alloc keys
- context switch overhead: when we're bottlenecked on btree updates,
having a thread (running out of a work item) checking the write point
for completed ops is cheaper than queueing up a new work item and
waking up a kworker.
In an arbitrary benchmark, 4k random writes with fio running inside a
VM, this patch resulted in a 10% improvement in total iops.
Signed-off-by: Kent Overstreet <kent.overstreet@linux.dev>
Kent Overstreet [Tue, 15 Mar 2022 01:48:42 +0000 (21:48 -0400)]
bcachefs: Introduce a separate journal watermark for copygc
Since journal reclaim -> btree key cache flushing may require the
allocation of new btree nodes, it has an implicit dependency on copygc
in order to make forward progress - so we should avoid blocking copygc
unless the journal is really close to full.
This introduces watermarks to replace our single MAY_GET_UNRESERVED bit
in the journal, and adds a watermark for copygc and plumbs it through.
Signed-off-by: Kent Overstreet <kent.overstreet@linux.dev>
Kent Overstreet [Tue, 15 Mar 2022 20:40:55 +0000 (16:40 -0400)]
bcachefs: Copygc allocations shouldn't be nowait
We don't actually want copygc allocations to be nowait - an allocation
for copygc might fail and then later succeed due to a bucket needing to
wait on journal commit, or to be discarded.
Signed-off-by: Kent Overstreet <kent.overstreet@gmail.com>
Kent Overstreet [Thu, 5 Jan 2023 15:13:37 +0000 (10:13 -0500)]
bcachefs: Fix bch2_journal_pin_set()
When bch2_journal_pin_set() is updating an existing pin, we shouldn't
call bch2_journal_reclaim_fast() after dropping the old pin and before
dropping the new pin - that could reclaim the entry we're trying to pin.
Signed-off-by: Kent Overstreet <kent.overstreet@linux.dev>
Kent Overstreet [Thu, 31 Mar 2022 03:39:48 +0000 (23:39 -0400)]
bcachefs: Run overwrite triggers before insert
For backpointers, we'll need to delete old backpointers before adding
new backpointers - otherwise we'll run into spurious duplicate
backpointer errors.
Signed-off-by: Kent Overstreet <kent.overstreet@gmail.com>
Kent Overstreet [Thu, 31 Mar 2022 04:03:37 +0000 (00:03 -0400)]
bcachefs: Move deletion of refcount=0 indirect extents to their triggers
For backpointers, we need to switch the order triggers are run in: we
need to run triggers for deletions/overwrites before triggers for
inserts.
To avoid breaking the reflink triggers, this patch moves deleting of
indirect extents with refcount=0 to their triggers, instead of doing it
when we update those keys.
Signed-off-by: Kent Overstreet <kent.overstreet@gmail.com>
This fixes a bug where __bch2_btree_node_update_key() wasn't clearing
should_be_locked, leading to bch2_btree_path_traverse() always failing -
all callers of btree_path_make_mut() want should_be_locked cleared, so
do it there.
Signed-off-by: Kent Overstreet <kent.overstreet@gmail.com>
Kent Overstreet [Wed, 30 Mar 2022 17:10:03 +0000 (13:10 -0400)]
bcachefs: Add a missing btree_path_set_dirty() calls
bch2_btree_iter_next_node() was mucking with other btree_path state
without setting path->update to be consistent with the fact that the
path is very much no longer uptodate - oops.
Signed-off-by: Kent Overstreet <kent.overstreet@gmail.com>
Kent Overstreet [Mon, 28 Mar 2022 20:21:26 +0000 (16:21 -0400)]
bcachefs: Work around a journal self-deadlock
bch2_journal_space_available -> bch2_journal_halt() self deadlocks on
journal lock; work around this by dropping/retaking journal lock before
we call bch2_fatal_error().
Signed-off-by: Kent Overstreet <kent.overstreet@gmail.com>
Kent Overstreet [Mon, 28 Mar 2022 16:31:22 +0000 (12:31 -0400)]
bcachefs: Heap code fix
When deleting an entry from a heap that was at entry h->used - 1, we'd
end up calling heap_sift() on an entry outside the heap - the entry we
just removed - which would end up re-adding it to the heap and deleting
something we didn't want to delete. Oops...
Signed-off-by: Kent Overstreet <kent.overstreet@gmail.com>
Kent Overstreet [Mon, 21 Mar 2022 07:03:03 +0000 (03:03 -0400)]
bcachefs: Reset journal flush delay to default value if zeroed
We've been seeing a very strange bug where journal flush & reclaim delay
end up getting inexplicably zeroed, in the superblock. We're now
validating all the options in bch2_validate_super(), and 0 is no longer
a valid value for those options, but we need to be careful not to
prevent people's filesystems from mounting because of the new
validation.
Signed-off-by: Kent Overstreet <kent.overstreet@gmail.com>
projects / thirdparty / kernel / linux.git / log
