bcachefs: Fix a spurious warning

Fixes fstests generic/648

Signed-off-by: Kent Overstreet <kent.overstreet@linux.dev>

bcachefs: Fix buffered write path for generic/275

Per fstests generic/275, on -ENOSPC we're supposed write until the
filesystem is full - i.e. do a partial write instead of failing the full
write.

This is a partial fix for the buffered write path: we'll still fail on a
page boundary.

Signed-off-by: Kent Overstreet <kent.overstreet@linux.dev>

bcachefs: Journal keys overlay fixes

 - In the btree iterator code that overlays keys from the journal, we
   were incorrectly specifying level=0 instead of the btree_path's
   current level in a few places
 - When we didn't do journal replay, we shouldn't free the journal keys:
   this fixes cmd_list and cmd_dump, which run in norecovery mode

Signed-off-by: Kent Overstreet <kent.overstreet@linux.dev>

bcachefs: Fix an out-of-bounds shift

roundup_pow_of_two() is undefined for 0 - oops.

Signed-off-by: Kent Overstreet <kent.overstreet@linux.dev>

bcachefs: Make error messages more uniform

Use __func__ in error messages that refer to function name, and do so
more uniformly - suggested by checkpatch.pl

Signed-off-by: Kent Overstreet <kent.overstreet@linux.dev>

bcachefs: Convert to __packed and __aligned

Signed-off-by: Kent Overstreet <kent.overstreet@linux.dev>

bcachefs: bch2_bkey_cmp_packed_inlined()

This adds an inlined version of bch2_bkey_cmp_packed(), and uses it in
bch2_sort_keys(), where it's part of the inner loop.

Signed-off-by: Kent Overstreet <kent.overstreet@linux.dev>

bcachefs: Move bkey bkey_unpack_key() to bkey.h

Long ago, bkey_unpack_key() was added to bset.h instead of bkey.h
because bkey.h didn't include btree_types.h, which it needs for the
compiled unpack function.

This patch finally moves it to the proper location.

Signed-off-by: Kent Overstreet <kent.overstreet@linux.dev>

bcachefs: Optimize __bch2_btree_node_iter_advance()

This replaces an expensive memmove() call with an open-coded version.

Signed-off-by: Kent Overstreet <kent.overstreet@linux.dev>

bcachefs: Don't touch c->flags in bch2_trans_iter_init()

This moves the JOURNAL_REPLAY_DONE flag check from
bch2_trans_iter_init() to bch2_trans_init(), where we stash a copy in
btree_trans - gaining us a small performance improvement.

Signed-off-by: Kent Overstreet <kent.overstreet@linux.dev>

bcachefs: Assorted checkpatch fixes

checkpatch.pl gives lots of warnings that we don't want - suggested
ignore list:

 ASSIGN_IN_IF
 UNSPECIFIED_INT - bcachefs coding style prefers single token type names
 NEW_TYPEDEFS - typedefs are occasionally good
 FUNCTION_ARGUMENTS - we prefer to look at functions in .c files
  (hopefully with docbook documentation), not .h
  file prototypes
 MULTISTATEMENT_MACRO_USE_DO_WHILE
- we have _many_ x-macros and other macros where
  we can't do this

Signed-off-by: Kent Overstreet <kent.overstreet@linux.dev>

bcachefs: Optimize bch2_dev_usage_read()

 - add bch2_dev_usage_read_fast(), which doesn't return by value -
   bch_dev_usage is big enough that we don't want the silent memcpy
 - tweak the allocation path to only call bch2_dev_usage_read() once per
   bucket allocated

Signed-off-by: Kent Overstreet <kent.overstreet@linux.dev>

bcachefs: fix bch2_write_extent() crc corruption.

crc.compression_type & nouce gets reset to inside bch2_rechecksum_bio(),
we set it back to the previous values calculated. This fixes
incompressible extents being marked as uncompressed.

Signed-off-by: Daniel Hill <daniel@gluo.nz>
Signed-off-by: Kent Overstreet <kent.overstreet@linux.dev>

bcachefs: fix security warning in pr_name_and_units

Signed-off-by: Daniel Hill <daniel@gluo.nz>
Signed-off-by: Kent Overstreet <kent.overstreet@linux.dev>

bcachefs: Don't issue transaction restart on key cache realloc

This shouldn't be needed anymore, since we don't rely on the pointer
validity that this was guarding against anymore - we get a new good
reference and save it right after this function.

Signed-off-by: Kent Overstreet <kent.overstreet@linux.dev>

bcachefs: Separate out flush_new_cached_update()

This separates out the slowpath of bch2_trans_update_by_path_trace()
into a new non-inlined helper.

Signed-off-by: Kent Overstreet <kent.overstreet@linux.dev>

bcachefs: Optimize __bkey_unpack_key_format_checked()

Delete some code when CONFIG_BCACHEFS_DEBUG=n

Signed-off-by: Kent Overstreet <kent.overstreet@linux.dev>

bcachefs: Inline bch2_inode_pack()

It's mainly used from bch2_inode_write(), so inline it there.

Signed-off-by: Kent Overstreet <kent.overstreet@linux.dev>

bcachefs: bucket_alloc_fail tracepoint should only fire when we have to block

We don't want to fire the bucket_alloc_fail tracepoint on transaction
restart, when we can retry immediately - only when we the allocation
actually has to block.

Also, switch from sched_clock() to local_clock(), as we've been doing
elsewhere.

Signed-off-by: Kent Overstreet <kent.overstreet@linux.dev>

bcachefs: Optimize bch2_trans_init()

Now we store the transaction's fn idx in a local variable, instead of
redoing the lookup every time we call bch2_trans_init().

Signed-off-by: Kent Overstreet <kent.overstreet@linux.dev>

bcachefs: Split out __btree_path_up_until_good_node()

This breaks up btree_path_up_until_good_node() so that only the fastpath
gets inlined.

Signed-off-by: Kent Overstreet <kent.overstreet@linux.dev>

bcachefs: Btree key cache shrinker fix

The shrinker assumes freed key cache items are ordered by age, so that
it doesn't have to scan the full list to find items that are old enough
(according to the srcu code) to be freed.

But percpu freelists broke this ordering; this patch fixes this by
ensuring we insert items into the proper position.

Signed-off-by: Kent Overstreet <kent.overstreet@linux.dev>

bcachefs: __bio_compress() fix up.

A single block can't be compressed, so it's incompressible.
This stops rebalance repeatably marking extents as uncompressed.

Signed-off-by: Daniel Hill <daniel@gluo.nz>
Signed-off-by: Kent Overstreet <kent.overstreet@linux.dev>

bcachefs: make durability a read-write sysfs option

Sometimes the user may need to change durability after formatting to
match current hardware setup, this option provides a quick and flexible
alternative to removing then adding the device.
It is HIGHLY ADVISED TO RUN REREPLICATE after changing this value so the
system doesn't remain degraded.

Signed-off-by: Daniel Hill <daniel@gluo.nz>
Signed-off-by: Kent Overstreet <kent.overstreet@linux.dev>

bcachefs: improve behaviour of btree_cache_scan()

Appending new nodes to the end of the list means we're more likely to
evict old entries when btree_cache_scan() is started.

Signed-off-by: Daniel Hill <daniel@gluo.nz>
Signed-off-by: Kent Overstreet <kent.overstreet@linux.dev>

bcachefs: Quota fixes

 - We now correctly allow soft limits to be exceeded, instead of always
   returning -EDQUOT
 - Disk quota grate times/warnings can now be set, not just the
   systemwide defaults

Signed-off-by: Kent Overstreet <kent.overstreet@linux.dev>

bcachefs: Switch to local_clock() for fastpath time source

local_clock() isn't always completely accurate - e.g. on machines with
TSC drift - but ktime_get_ns() overhead is too high, unfortunately.

Signed-off-by: Kent Overstreet <kent.overstreet@linux.dev>

bcachefs: Btree key cache improvements

 - In userspace, we don't have real percpu variables; this patch
   disables the percpu freelists in userspace
 - add some error messages for the asserts in
   bch2_fs_btree_key_cache_exit(); we've been hitting this (only in
   userspace, oddly), perhaps this will help us track down the error.
 - bkey_cached_reuse() should likely be taking the key cache lock, and
   it's a slowpath so it doesn't hurt to

Signed-off-by: Kent Overstreet <kent.overstreet@linux.dev>

bcachefs: Fix btree node prefetchig

We were forgetting to count down the number of nodes to prefetch, firing
off _way_ more than intended - whoops.

Signed-off-by: Kent Overstreet <kent.overstreet@linux.dev>

bcachefs: bch2_btree_key_cache_scan() doesn't need trylock

We don't actually allocate memory under the btree key cache lock - so
there's no recursion concerns, and the shrinker can just use
mutex_lock().

Signed-off-by: Kent Overstreet <kent.overstreet@linux.dev>

bcachefs: Defer full journal entry validation

On journal read, previously we would do full journal entry validation
immediately after reading a journal entry.

However, this would lead to errors for journal entries we weren't
actually going to use, either because they were too old or too new
(newer than the most recent flush).

We've observed write tearing on journal entries newer than the newest
flush - which makes sense, prior to a flush there's no guarantees about
write persistence.

This patch defers full journal entry validation until the end of the
journal read path, when we know which journal entries we'll want to use.

Signed-off-by: Kent Overstreet <kent.overstreet@linux.dev>

bcachefs: Improve journal_entry_add()

Prep work for the next patch, to defer journal entry validation: we now
track for each replica whether we had a good checksum.

Signed-off-by: Kent Overstreet <kent.overstreet@linux.dev>

bcachefs: time stats now uses the mean_and_variance module.

Signed-off-by: Daniel Hill <daniel@gluo.nz>
Signed-off-by: Kent Overstreet <kent.overstreet@linux.dev>

bcachefs: Mean and variance

This module provides a fast 64bit implementation of basic statistics
functions, including mean, variance and standard deviation in both
weighted and unweighted variants, the unweighted variant has a 32bit
limitation per sample to prevent overflow when squaring.

Signed-off-by: Daniel Hill <daniel@gluo.nz>
Signed-off-by: Kent Overstreet <kent.overstreet@linux.dev>

bcachefs: Fix for not dropping privs in fallocate

When modifying a file, we may be required to drop the suid/sgid bits -
we were missing a file_modified() call to do this.

Signed-off-by: Kent Overstreet <kent.overstreet@linux.dev>

bcachefs: Fix bch2_write_begin()

An error case was jumping to the wrong label, creating an infinite loop
- oops.

This fixes fstests generic/648.

Signed-off-by: Kent Overstreet <kent.overstreet@linux.dev>

fixup bcachefs: Deadlock cycle detector

Signed-off-by: Kent Overstreet <kent.overstreet@linux.dev>

fixup bcachefs: Deadlock cycle detector

Signed-off-by: Kent Overstreet <kent.overstreet@linux.dev>

bcachefs: Fix lock_graph_remove_non_waiters()

We were removing 1 more entry than we were supposed to - oops.

Also some other simplifications and cleanups, and bring back the abort
preference code in a better fashion.

Signed-off-by: Kent Overstreet <kent.overstreet@linux.dev>

bcachefs: Support FS_XFLAG_PROJINHERIT

We already have support for the flag's semantics: inode options are
inherited by children if they were explicitly set on the parent. This
patch just maps the FS_XFLAG_PROJINHERIT flag to the "this option was
epxlicitly set" bit.

Signed-off-by: Kent Overstreet <kent.overstreet@linux.dev>

bcachefs: Don't allow hardlinks when inherited attrs would change

This is the right thing to do, and conforms with our own behaviour on
rename and xfs's behaviour on hardlink.

Signed-off-by: Kent Overstreet <kent.overstreet@linux.dev>

bcachefs: Initialize sb_quota with default 1 week timer

For compliance with other quota implementations, we should be
initializing quota information with a default 1 week timelimit: this
fixes fstests generic/235.

Also, this adds to_text() functions for some quota structs - useful
debugging aids.

Signed-off-by: Kent Overstreet <kent.overstreet@linux.dev>

bcachefs: Call bch2_btree_update_add_new_node() before dropping write lock

btree nodes can be written by other threads (shrinker, journal reclaim)
with only a read lock, but brand new nodes should only be written by the
thread doing the split/interior update. bch2_btree_update_add_new_node()
sets btree node flags to indicate that this is a new node and should not
be written out by other threads, thus we need to call it before dropping
our write lock.

Signed-off-by: Kent Overstreet <kent.overstreet@linux.dev>

bcachefs: Reflink now respects quotas

This adds a new helper, quota_reserve_range(), which takes a quota
reservation for unallocated blocks in a given file range, and uses it in
bch2_remap_file_range().

Signed-off-by: Kent Overstreet <kent.overstreet@linux.dev>

bcachefs: Fix a rare path in bch2_btree_path_peek_slot()

In the drop_alloc tests, we may end up calling
bch2_btree_iter_peek_slot() on an interior level that doesn't exist.
Previously, this would hit the path->uptodate assertion in
bch2_btree_path_peek_slot(); this path first checks a NULL btree node,
which is how we know we're at the end of the btree.

Signed-off-by: Kent Overstreet <kent.overstreet@linux.dev>

bcachefs: bch2_path_put_nokeep()

The btree iterator code may allocate extra btree paths, temporarily,
that do not refer to keys being returned: we don't need to wait until
transaction restart to drop these, when they're not referenced they
should be deleted right away.

This fixes a transaction path overflow bug.

Signed-off-by: Kent Overstreet <kent.overstreet@linux.dev>

bcachefs: Fix cached data accounting

Negating without casting to a signed integer means the value wasn't
getting sign extended properly - oops.

Signed-off-by: Kent Overstreet <kent.overstreet@linux.dev>

bcachefs: Btree splits now only take the locks they need

Previously, bch2_btree_update_start() would always take all intent
locks, all the way up to the root.

We've finally got data from users where this became a scalability issue
- so, this patch fixes bch2_btree_update_start() to only take the locks
we need.

Signed-off-by: Kent Overstreet <kent.overstreet@linux.dev>

bcachefs: bch2_btree_iter_peek() now works with interior nodes

Needed by the next patch, which will be iterating over keys in nodes at
level 1.

Signed-off-by: Kent Overstreet <kent.overstreet@linux.dev>

bcachefs: bch2_btree_insert_node() no longer uses lock_write_nofail

Now that we have an error path plumbed through, there's no need to be
using bch2_btree_node_lock_write_nofail().

Signed-off-by: Kent Overstreet <kent.overstreet@linux.dev>

bcachefs: Add error path to btree_split()

The next patch in the series is (finally!) going to change btree splits
(and interior updates in general) to not take intent locks all the way
up to the root - instead only locking the nodes they'll need to modify.

However, this will be introducing a race since if we're not holding a
write lock on a btree node it can be written out by another thread, and
then we might not have enough space for a new bset entry.

We can handle this by retrying - we just need to introduce a new error
path.

Signed-off-by: Kent Overstreet <kent.overstreet@linux.dev>

bcachefs: Write new btree nodes after parent update

In order to avoid locking all btree nodes up to the root for btree node
splits, we're going to have to introduce a new error path into
bch2_btree_insert_node(); this mean we can't have done any writes or
modified global state before that point.

Signed-off-by: Kent Overstreet <kent.overstreet@linux.dev>

bcachefs: Simplify break_cycle()

We'd like to prioritize aborting transactions that have done less work -
however, it appears breaking cycles by telling other threads to abort
may still be buggy, so disable that for now.

Signed-off-by: Kent Overstreet <kent.overstreet@linux.dev>

bcachefs: Print cycle on unrecoverable deadlock

Some lock operations can't fail; a cycle of nofail locks is impossible
to recover from. So we want to get rid of these nofail locking
operations, but as this is tricky it'll be done incrementally.

If such a cycle happens, this patch prints out which codepaths are
involved so we know what to work on next.

Signed-off-by: Kent Overstreet <kent.overstreet@linux.dev>

bcachefs: Handle dropping pointers in data_update path

Cached pointers are generally dropped, not moved: this led to an
assertion firing in the data update path when there were no new replicas
being written.

This path adds a data_options field for pointers to be dropped, and
tweaks move_extent() to check if we're only dropping pointers, not
writing new ones, before kicking off a data update operation.

Signed-off-by: Kent Overstreet <kent.overstreet@linux.dev>

bcachefs: Ratelimit ec error message

We should fix this, but for now this makes this more usable.

Signed-off-by: Kent Overstreet <kent.overstreet@linux.dev>

bcachefs: Use btree_type_has_ptrs() more consistently

Signed-off-by: Kent Overstreet <kent.overstreet@linux.dev>

bcachefs: Fix "multiple types of data in same bucket" with ec

Signed-off-by: Kent Overstreet <kent.overstreet@linux.dev>

bcachefs: Ensure fsck error is printed before panic

When errors=panic, we want to make sure we print the error before
calling bch2_inconsistent_error().

Signed-off-by: Kent Overstreet <kent.overstreet@linux.dev>

bcachefs: Fix a deadlock in btree_update_nodes_written()

btree_node_lock_nopath() is something we'd like to get rid of, it's
always prone to deadlocks if we accidentally are holding other locks,
because it doesn't mark the lock it's taking in a path: we'll want to
get rid of it in the future, but for now this patch works it by calling
bch2_trans_unlock().

Signed-off-by: Kent Overstreet <kent.overstreet@linux.dev>

bcachefs: bch2_trans_locked()

Useful debugging function.

Signed-off-by: Kent Overstreet <kent.overstreet@linux.dev>

bcachefs: Improve btree_deadlock debugfs output

This changes bch2_check_for_deadlock() to print the longest chains it
finds - when we have a deadlock because the cycle detector isn't finding
something, this will let us see what it's missing.

Signed-off-by: Kent Overstreet <kent.overstreet@linux.dev>

bcachefs: Don't quash error in bch2_bucket_alloc_set_trans()

We were incorrectly returning -BCH_ERR_insufficient_devices when we'd
received a different error from bch2_bucket_alloc_trans(), which
(erronously) turns into -EROFS further up the call chain.

Signed-off-by: Kent Overstreet <kent.overstreet@linux.dev>

bcachefs: Fix a trans path overflow in bch2_btree_delete_range_trans()

bch2_btree_delete_range_trans() was using btree_trans_too_many_iters()
to avoid path overflow, but this was buggy here (and also
btree_trans_too_many_iters() is suspect in general).

btree_trans_too_many_iters() only returns true when we're close to the
maximum number of paths - within 8 - but extent insert/delete assumes
that it can use more paths than that.

Instead, we need to call bch2_trans_begin() on every loop iteration.
Since we don't want to call bch2_trans_begin() (restarting the outer
transaction) if the call was a no-op - if we had no work to do - we have
to structure things a bit oddly.

Signed-off-by: Kent Overstreet <kent.overstreet@linux.dev>

bcachefs: bucket_alloc_state

This refactoring puts our various allocation path counters into a
dedicated struct - the upcoming nocow patch is going to add another
counter.

Signed-off-by: Kent Overstreet <kent.overstreet@linux.dev>

bcachefs: Fix bch2_btree_path_up_until_good_node()

There was a rare bug when path->locks_want was nonzero, but not
BTREE_MAX_DEPTH, where we'd return on a valid node that wasn't locked -
oops.

Signed-off-by: Kent Overstreet <kent.overstreet@linux.dev>

bcachefs: Factor out bch2_write_drop_io_error_ptrs()

Move slowpath code to a separate, non-inline function.

Signed-off-by: Kent Overstreet <kent.overstreet@linux.dev>

bcachefs: Break out bch2_btree_path_traverse_cached_slowpath()

Prep work for further refactoring.

Signed-off-by: Kent Overstreet <kent.overstreet@linux.dev>

bcachefs: Kill io_in_flight semaphore

This used to be needed more for buffered IO, but now the block layer has
writeback throttling - we can delete this now.

Signed-off-by: Kent Overstreet <kent.overstreet@linux.dev>

bcachefs: Improve bucket_alloc tracepoint

It now includes more info - whether the bucket was for metadata or data
- and also call it in the same place as the bucket_alloc_fail
tracepoint.

Signed-off-by: Kent Overstreet <kent.overstreet@linux.dev>

bcachefs; Mark __bch2_trans_iter_init as inline

This function is fairly small and only used in two places: one very hot,
the other cold, so it should definitely be inlined.

Signed-off-by: Kent Overstreet <kent.overstreet@linux.dev>

bcachefs: Inline fast path of check_pos_snapshot_overwritten()

This moves the slowpath of check_pos_snapshot_overwritten() to a
separate function, and inlines the fast path - helping performance on
btrees that don't use snapshot and for users that aren't using
snapshots.

Signed-off-by: Kent Overstreet <kent.overstreet@linux.dev>

bcachefs: Improve jset_validate()

Previously, jset_validate() was formatting the initial part of an error
string for every entry it validating - expensive.

This moves that code to journal_entry_err_msg(), which is now only
called if there's an actual error.

Signed-off-by: Kent Overstreet <kent.overstreet@linux.dev>

bcachefs: Optimize btree_path_alloc()

 - move slowpath code to a separate function, btree_path_overflow()
 - no need to use hweight64
 - copy nr_max_paths from btree_transaction_stats to btree_trans,
   avoiding a data dependency in the fast path

Signed-off-by: Kent Overstreet <kent.overstreet@linux.dev>

bcachefs: Inline bch2_trans_kmalloc() fast path

Small performance optimization.

Signed-off-by: Kent Overstreet <kent.overstreet@linux.dev>

bcachefs: Run bch2_fs_counters_init() earlier

We need counters to be initialized before initializing shrinkers - the
shrinker callbacks will update those counters. This fixes a segfault in
userspace.

Signed-off-by: Kent Overstreet <kent.overstreet@linux.dev>

bcachefs: btree_err() now uses bch2_print_string_as_lines()

We've seen long error messages get truncated here, so convert to the new
bch2_print_string_as_lines().

Signed-off-by: Kent Overstreet <kent.overstreet@linux.dev>

bcachefs: Improve bch2_fsck_err()

 - factor out fsck_err_get()
 - if the "bcachefs (%s):" prefix has already been applied, don't
   duplicate it
 - convert to printbufs instead of static char arrays
 - tidy up control flow a bit
 - use bch2_print_string_as_lines(), to avoid messages getting truncated

Signed-off-by: Kent Overstreet <kent.overstreet@linux.dev>

bcachefs: bch2_print_string_as_lines()

This adds a helper for printing a large buffer one line at a time, to
avoid the 1k printk limit.

Signed-off-by: Kent Overstreet <kent.overstreet@linux.dev>

bcachefs: bch2_btree_node_relock_notrace()

Most of the node_relock_fail trace events are generated from
bch2_btree_path_verify_level(), when debugcheck_iterators is enabled -
but we're not interested in these trace events, they don't indicate that
we're in a slowpath.

Signed-off-by: Kent Overstreet <kent.overstreet@linux.dev>

bcachefs: bch2_btree_cache_scan() improvement

We're still seeing OOM issues caused by the btree node cache shrinker
not sufficiently freeing memory: thus, this patch changes the shrinker
to not exit if __GFP_FS was not supplied.

Instead, tweak btree node memory allocation so that we never invoke
memory reclaim while holding the btree node cache lock.

Signed-off-by: Kent Overstreet <kent.overstreet@linux.dev>

bcachefs: Fix blocking with locks held

This is a major oopsy - we should always be unlocking before calling
closure_sync(), else we'll cause a deadlock.

Signed-off-by: Kent Overstreet <kent.overstreet@linux.dev>

bcachefs: btree_update_nodes_written() needs BTREE_INSERT_USE_RESERVE

This fixes an obvious deadlock - whoops.

Signed-off-by: Kent Overstreet <kent.overstreet@linux.dev>

bcachefs: Fix error handling in bch2_btree_update_start()

We were checking for -EAGAIN, but we're not returned that when we didn't
pass a closure to wait with - oops.

Signed-off-by: Kent Overstreet <kent.overstreet@linux.dev>

bcachefs: Improve bch2_btree_trans_to_text()

This is just a formatting/readability improvement.

Signed-off-by: Kent Overstreet <kent.overstreet@linux.dev>

bcachefs: Kill normalize_read_intent_locks()

Before we had the deadlock cycle detector, we didn't want to be holding
read locks when taking intent locks, because blocking on an intent lock
while holding a read lock was a lock ordering violation that could
cause a deadlock.

With the cycle detector this is no longer an issue, so this code can be
deleted.

Signed-off-by: Kent Overstreet <kent.overstreet@gmail.com>

bcachefs: Ensure bch2_btree_node_lock_write_nofail() never fails

In order for bch2_btree_node_lock_write_nofail() to never produce a
deadlock, we must ensure we're never holding read locks when using it.
Fortunately, it's only used from code paths where any read locks may be
safely dropped.

Signed-off-by: Kent Overstreet <kent.overstreet@linux.dev>

bcachefs: Delete old deadlock avoidance code

This deletes our old lock ordering based deadlock avoidance code.

Signed-off-by: Kent Overstreet <kent.overstreet@gmail.com>

bcachefs: Print deadlock cycle in debugfs

In the event that we're not finished debugging the cycle detector, this
adds a new file to debugfs that shows what the cycle detector finds, if
anything. By comparing this with btree_transactions, which shows held
locks for every btree_transaction, we'll be able to determine if it's
the cycle detector that's buggy or something else.

Signed-off-by: Kent Overstreet <kent.overstreet@linux.dev>

bcachefs: Deadlock cycle detector

We've outgrown our own deadlock avoidance strategy.

The btree iterator API provides an interface where the user doesn't need
to concern themselves with lock ordering - different btree iterators can
be traversed in any order. Without special care, this will lead to
deadlocks.

Our previous strategy was to define a lock ordering internally, and
whenever we attempt to take a lock and trylock() fails, we'd check if
the current btree transaction is holding any locks that cause a lock
ordering violation. If so, we'd issue a transaction restart, and then
bch2_trans_begin() would re-traverse all previously used iterators, but
in the correct order.

That approach had some issues, though.
 - Sometimes we'd issue transaction restarts unnecessarily, when no
   deadlock would have actually occured. Lock ordering restarts have
   become our primary cause of transaction restarts, on some workloads
   totally 20% of actual transaction commits.

 - To avoid deadlock or livelock, we'd often have to take intent locks
   when we only wanted a read lock: with the lock ordering approach, it
   is actually illegal to hold _any_ read lock while blocking on an intent
   lock, and this has been causing us unnecessary lock contention.

 - It was getting fragile - the various lock ordering rules are not
   trivial, and we'd been seeing occasional livelock issues related to
   this machinery.

So, since bcachefs is already a relational database masquerading as a
filesystem, we're stealing the next traditional database technique and
switching to a cycle detector for avoiding deadlocks.

When we block taking a btree lock, after adding ourself to the waitlist
but before sleeping, we do a DFS of btree transactions waiting on other
btree transactions, starting with the current transaction and walking
our held locks, and transactions blocking on our held locks.

If we find a cycle, we emit a transaction restart. Occasionally (e.g.
the btree split path) we can not allow the lock() operation to fail, so
if necessary we'll tell another transaction that it has to fail.

Result: trans_restart_would_deadlock events are reduced by a factor of
10 to 100, and we'll be able to delete a whole bunch of grotty, fragile
code.

Signed-off-by: Kent Overstreet <kent.overstreet@gmail.com>

bcachefs: Fix bch2_btree_node_upgrade()

Previously, if we were trying to upgrade from a read to an intent lock
but we held an additional read lock via another btree_path,
bch2_btree_node_upgrade() would always fail, in six_lock_tryupgrade().

This patch factors out the code that __bch2_btree_node_lock_write() uses
to temporarily drop extra read locks, so that six_lock_tryupgrade() can
succeed.

Signed-off-by: Kent Overstreet <kent.overstreet@gmail.com>

bcachefs: Add a debug assert

Chasing down a strange locking bug.

Signed-off-by: Kent Overstreet <kent.overstreet@linux.dev>

six locks: Wakeup now takes lock on behalf of waiter

This brings back an important optimization, to avoid touching the wait
lists an extra time, while preserving the property that a thread is on a
lock waitlist iff it is waiting - it is never removed from the waitlist
until it has the lock.

Signed-off-by: Kent Overstreet <kent.overstreet@linux.dev>

six locks: Fix a lost wakeup

There was a lost wakeup between a read unlock in percpu mode and a write
lock. The unlock path unlocks, then executes a barrier, then checks for
waiters; correspondingly, the lock side should set the wait bit and
execute a barrier, then attempt to take the lock.

Signed-off-by: Kent Overstreet <kent.overstreet@linux.dev>

six locks: Enable lockdep

Now that we have lockdep_set_no_check_recursion(), we can enable lockdep
checking.

Signed-off-by: Kent Overstreet <kent.overstreet@linux.dev>

six locks: Add start_time to six_lock_waiter

This is needed by the cycle detector in bcachefs - we need a way to
iterater over waitlist entries while dropping and retaking the waitlist
lock.

Signed-off-by: Kent Overstreet <kent.overstreet@linux.dev>

six locks: six_lock_waiter()

This allows passing in the wait list entry - to be used for a deadlock
cycle detector.

Signed-off-by: Kent Overstreet <kent.overstreet@linux.dev>

six locks: Simplify wait lists

This switches to a single list of waiters, instead of separate lists for
read and intent, and switches write locks to also use the wait lists
instead of being handled differently.

Also, removal from the wait list is now done by the process waiting on
the lock, not the process doing the wakeup. This is needed for the new
deadlock cycle detector - we need tasks to stay on the waitlist until
they've successfully acquired the lock.

Signed-off-by: Kent Overstreet <kent.overstreet@linux.dev>

bcachefs: Add private error codes for ENOSPC

Continuing the saga of introducing private dedicated error codes for
each error path, this patch converts ENOSPC to error codes that are
subtypes of ENOSPC. We've recently had a test failure where we got
-ENOSPC where we shouldn't have, and didn't have enough information to
tell where it came from, so this patch will solve that problem.

Signed-off-by: Kent Overstreet <kent.overstreet@linux.dev>

bcachefs: Errcodes can now subtype standard error codes

The next patch is going to be adding private error codes for all the
places we return -ENOSPC.

Additionally, this patch updates return paths at all module boundaries
to call bch2_err_class(), to return the standard error code.

Signed-off-by: Kent Overstreet <kent.overstreet@linux.dev>