#
812a9297 |
|
26-Mar-2024 |
Kent Overstreet <kent.overstreet@linux.dev> |
bcachefs: Fix btree node keys accounting in topology repair path When dropping keys now outside a now because we're changing the node min/max, we need to redo the node's accounting as well. Signed-off-by: Kent Overstreet <kent.overstreet@linux.dev>
|
#
ec4edd7b |
|
16-Jan-2024 |
Kent Overstreet <kent.overstreet@linux.dev> |
bcachefs: Prep work for variable size btree node buffers bcachefs btree nodes are big - typically 256k - and btree roots are pinned in memory. As we're now up to 18 btrees, we now have significant memory overhead in mostly empty btree roots. And in the future we're going to start enforcing that certain btree node boundaries exist, to solve lock contention issues - analagous to XFS's AGIs. Thus, we need to start allocating smaller btree node buffers when we can. This patch changes code that refers to the filesystem constant c->opts.btree_node_size to refer to the btree node buffer size - btree_buf_bytes() - where appropriate. Signed-off-by: Kent Overstreet <kent.overstreet@linux.dev>
|
#
3fe8a186 |
|
06-Jan-2024 |
Kent Overstreet <kent.overstreet@linux.dev> |
bcachefs: eytzinger_for_each() declares loop iter Signed-off-by: Kent Overstreet <kent.overstreet@linux.dev>
|
#
d04d2727 |
|
05-Jan-2024 |
Kent Overstreet <kent.overstreet@linux.dev> |
bcachefs: bch2_dump_bset() doesn't choke on u64s == 0 Signed-off-by: Kent Overstreet <kent.overstreet@linux.dev>
|
#
439c172b |
|
13-Sep-2023 |
Kent Overstreet <kent.overstreet@linux.dev> |
bcachefs: Kill other unreachable() uses Per previous commit, bare unreachable() considered harmful, convert to BUG() Signed-off-by: Kent Overstreet <kent.overstreet@linux.dev>
|
#
96dea3d5 |
|
12-Sep-2023 |
Kent Overstreet <kent.overstreet@linux.dev> |
bcachefs: Fix W=12 build errors Signed-off-by: Kent Overstreet <kent.overstreet@linux.dev>
|
#
5cfd6977 |
|
09-Sep-2023 |
Kent Overstreet <kent.overstreet@linux.dev> |
bcachefs: Array bounds fixes It's no longer legal to use a zero size array as a flexible array member - this causes UBSAN to complain. This patch switches our zero size arrays to normal flexible array members when possible, and inserts casts in other places (e.g. where we use the zero size array as a marker partway through an array). Signed-off-by: Kent Overstreet <kent.overstreet@linux.dev>
|
#
73bd774d |
|
06-Jul-2023 |
Kent Overstreet <kent.overstreet@linux.dev> |
bcachefs: Assorted sparse fixes - endianness fixes - mark some things static - fix a few __percpu annotations - fix silent enum conversions Signed-off-by: Kent Overstreet <kent.overstreet@linux.dev>
|
#
d598a9b7 |
|
13-May-2023 |
Kent Overstreet <kent.overstreet@linux.dev> |
bcachefs: Use memcpy_u64s_small() for copying keys Small performance optimization; an open coded loop is better than rep ; movsq for small copies. Signed-off-by: Kent Overstreet <kent.overstreet@linux.dev>
|
#
a345b0f3 |
|
06-Mar-2023 |
Kent Overstreet <kent.overstreet@linux.dev> |
bcachefs: bch2_btree_node_to_text() const correctness This is for the Rust interface - Rust cares more about const than C does. Signed-off-by: Kent Overstreet <kent.overstreet@linux.dev>
|
#
ac2ccddc |
|
04-Mar-2023 |
Kent Overstreet <kent.overstreet@linux.dev> |
bcachefs: Drop some anonymous structs, unions Rust bindgen doesn't cope well with anonymous structs and unions. This patch drops the fancy anonymous structs & unions in bkey_i that let us use the same helpers for bkey_i and bkey_packed; since bkey_packed is an internal type that's never exposed to outside code, it's only a minor inconvenienc. Signed-off-by: Kent Overstreet <kent.overstreet@linux.dev>
|
#
e88a75eb |
|
24-Nov-2022 |
Kent Overstreet <kent.overstreet@linux.dev> |
bcachefs: New bpos_cmp(), bkey_cmp() replacements This patch introduces - bpos_eq() - bpos_lt() - bpos_le() - bpos_gt() - bpos_ge() and equivalent replacements for bkey_cmp(). Looking at the generated assembly these could probably be improved further, but we already see a significant code size improvement with this patch. Signed-off-by: Kent Overstreet <kent.overstreet@linux.dev>
|
#
005def8f |
|
21-Oct-2022 |
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>
|
#
3e3e02e6 |
|
19-Oct-2022 |
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>
|
#
401ec4db |
|
03-Feb-2023 |
Kent Overstreet <kent.overstreet@linux.dev> |
bcachefs: Printbuf rework This converts bcachefs to the modern printbuf interface/implementation, synced with the version to be submitted upstream. Signed-off-by: Kent Overstreet <kent.overstreet@linux.dev>
|
#
fa8e94fa |
|
25-Feb-2022 |
Kent Overstreet <kent.overstreet@gmail.com> |
bcachefs: Heap allocate printbufs This patch changes printbufs dynamically allocate and reallocate a buffer as needed. Stack usage has become a bit of a problem, and a major cause of that has been static size string buffers on the stack. The most involved part of this refactoring is that printbufs must now be exited with printbuf_exit(). Signed-off-by: Kent Overstreet <kent.overstreet@linux.dev>
|
#
72492d55 |
|
02-Jan-2022 |
Kent Overstreet <kent.overstreet@gmail.com> |
bcachefs: Make eytzinger size parameter more conventional Signed-off-by: Kent Overstreet <kent.overstreet@gmail.com>
|
#
17563164 |
|
02-Jan-2022 |
Kent Overstreet <kent.overstreet@gmail.com> |
bcachefs: Kill bch2_bset_fix_invalidated_key() Was dead code, so delete it. Signed-off-by: Kent Overstreet <kent.overstreet@gmail.com>
|
#
67e0dd8f |
|
30-Aug-2021 |
Kent Overstreet <kent.overstreet@gmail.com> |
bcachefs: btree_path This splits btree_iter into two components: btree_iter is now the externally visible componont, and it points to a btree_path which is now reference counted. This means we no longer have to clone iterators up front if they might be mutated - btree_path can be shared by multiple iterators, and cloned if an iterator would mutate a shared btree_path. This will help us use iterators more efficiently, as well as slimming down the main long lived state in btree_trans, and significantly cleans up the logic for iterator lifetimes. Signed-off-by: Kent Overstreet <kent.overstreet@linux.dev>
|
#
6f152b0f |
|
02-Jul-2021 |
Dan Robertson <dan@dlrobertson.com> |
bcachefs: fix ifdef for x86_64 asm The implementation of prefetch_four_cachelines should use ifdef CONFIG_X86_64 to conditionally compile x86_64 asm. Signed-off-by: Dan Robertson <dan@dlrobertson.com> Signed-off-by: Kent Overstreet <kent.overstreet@linux.dev>
|
#
2eba51a6 |
|
21-May-2021 |
Brett Holman <bpholman5@gmail.com> |
bcachefs: rewrote prefetch asm in gas syntax for clang compatibility Signed-off-by: Brett Holman <bpholman5@gmail.com> Signed-off-by: Kent Overstreet <kent.overstreet@linux.dev>
|
#
2cd05634 |
|
16-May-2021 |
Brett Holman <bpholman5@gmail.com> |
bcachefs: made changes to support clang, fixed a couple bugs fs/bcachefs/bset.c edited prefetch macro to add clang support fs/bcachefs/btree_iter.c bugfix: initialize iter->real_pos in bch2_btree_iter_init for later use fs/bcachefs/io.c bugfix: eliminated undefined behavior (negative bitshift) fs/bcachefs/buckets.c bugfix: invert sign to handle 64bit abs() Signed-off-by: Brett Holman <bpholman5@gmail.com> Signed-off-by: Kent Overstreet <kent.overstreet@linux.dev>
|
#
3ce8b463 |
|
03-Apr-2021 |
Kent Overstreet <kent.overstreet@gmail.com> |
bcachefs: kill bset_tree->max_key Since we now ensure a btree node's max key fits in its packed format, this isn't needed for the reasons it used to be - and, it was being used inconsistently. Also reorder struct btree a bit for performance, and kill some dead code. Signed-off-by: Kent Overstreet <kent.overstreet@gmail.com> Signed-off-by: Kent Overstreet <kent.overstreet@linux.dev>
|
#
e751c01a |
|
24-Mar-2021 |
Kent Overstreet <kent.overstreet@gmail.com> |
bcachefs: Start using bpos.snapshot field This patch starts treating the bpos.snapshot field like part of the key in the btree code: * bpos_successor() and bpos_predecessor() now include the snapshot field * Keys in btrees that will be using snapshots (extents, inodes, dirents and xattrs) now always have their snapshot field set to U32_MAX The btree iterator code gets a new flag, BTREE_ITER_ALL_SNAPSHOTS, that determines whether we're iterating over keys in all snapshots or not - internally, this controlls whether bkey_(successor|predecessor) increment/decrement the snapshot field, or only the higher bits of the key. We add a new member to struct btree_iter, iter->snapshot: when BTREE_ITER_ALL_SNAPSHOTS is not set, iter->pos.snapshot should always equal iter->snapshot, which will be 0 for btrees that don't use snapshots, and alsways U32_MAX for btrees that will use snapshots (until we enable snapshot creation). This patch also introduces a new metadata version number, and compat code for reading from/writing to older versions - this isn't a forced upgrade (yet). Signed-off-by: Kent Overstreet <kent.overstreet@gmail.com> Signed-off-by: Kent Overstreet <kent.overstreet@linux.dev>
|
#
4cf91b02 |
|
04-Mar-2021 |
Kent Overstreet <kent.overstreet@gmail.com> |
bcachefs: Split out bpos_cmp() and bkey_cmp() With snapshots, we're going to need to differentiate between comparisons that should and shouldn't include the snapshot field. bpos_cmp is now the comparison function that does include the snapshot field, used by core btree code. Upper level filesystem code generally does _not_ want to compare against the snapshot field - that code wants keys to compare as equal even when one of them is in an ancestor snapshot. Signed-off-by: Kent Overstreet <kent.overstreet@gmail.com> Signed-off-by: Kent Overstreet <kent.overstreet@linux.dev>
|
#
2649b514 |
|
27-Mar-2021 |
Kent Overstreet <kent.overstreet@gmail.com> |
bcachefs: Simplify btree_node_iter_init_pack_failed() Since we now make sure to always generate packed bkey formats that can pack the min_key of a btree node, this path should actually never happen. Signed-off-by: Kent Overstreet <kent.overstreet@gmail.com> Signed-off-by: Kent Overstreet <kent.overstreet@linux.dev>
|
#
c7e04e22 |
|
26-Mar-2021 |
Kent Overstreet <kent.overstreet@gmail.com> |
bcachefs: Fix building of aux search trees We weren't packing the min/max keys, which was a major oversight and completely disabled generating bkey_floats for adjacent nodes. Signed-off-by: Kent Overstreet <kent.overstreet@gmail.com> Signed-off-by: Kent Overstreet <kent.overstreet@linux.dev>
|
#
0390ea8a |
|
24-Mar-2021 |
Kent Overstreet <kent.overstreet@gmail.com> |
bcachefs: Drop bkey noops Bkey noops were introduced to deal with trimming inline data extents in place in the btree: if the u64s field of a bkey was 0, that u64 was a noop and we'd start looking for the next bkey immediately after it. But extent handling has been lifted above the btree - we no longer modify existing extents in place in the btree, and the compatibilty code for old style extent btree nodes is gone, so we can completely drop this code. Signed-off-by: Kent Overstreet <kent.overstreet@gmail.com> Signed-off-by: Kent Overstreet <kent.overstreet@linux.dev>
|
#
f020bfcd |
|
04-Mar-2021 |
Kent Overstreet <kent.overstreet@gmail.com> |
bcachefs: Use bch2_bpos_to_text() more consistently Signed-off-by: Kent Overstreet <kent.overstreet@gmail.com> Signed-off-by: Kent Overstreet <kent.overstreet@linux.dev>
|
#
c052cf82 |
|
19-Feb-2021 |
Kent Overstreet <kent.overstreet@gmail.com> |
bcachefs: KEY_TYPE_discard is no longer used KEY_TYPE_discard used to be used for extent whiteouts, but when handling over overlapping extents was lifted above the core btree code it became unused. This patch updates various code to reflect that. Signed-off-by: Kent Overstreet <kent.overstreet@gmail.com> Signed-off-by: Kent Overstreet <kent.overstreet@linux.dev>
|
#
9ae82fe6 |
|
07-Nov-2020 |
Kent Overstreet <kent.overstreet@gmail.com> |
bcachefs: Inline make_bfloat() into __build_ro_aux_tree() This is a fast path - also, lift out the checks/init for min/max key. Signed-off-by: Kent Overstreet <kent.overstreet@gmail.com> Signed-off-by: Kent Overstreet <kent.overstreet@linux.dev>
|
#
d108efc2 |
|
02-Nov-2020 |
Kent Overstreet <kent.overstreet@gmail.com> |
bcachefs: add const annotations to bset.c perhaps a bit silly, but some debug assertions we want to add need const propagated a bit more. Signed-off-by: Kent Overstreet <kent.overstreet@gmail.com> Signed-off-by: Kent Overstreet <kent.overstreet@linux.dev>
|
#
29364f34 |
|
02-Nov-2020 |
Kent Overstreet <kent.overstreet@gmail.com> |
bcachefs: Drop sysfs interface to debug parameters It's not used much anymore, the module paramter interface is better. Signed-off-by: Kent Overstreet <kent.overstreet@gmail.com> Signed-off-by: Kent Overstreet <kent.overstreet@linux.dev>
|
#
4580baec |
|
25-Jul-2020 |
Kent Overstreet <kent.overstreet@gmail.com> |
bcachefs: Remove some uses of PAGE_SIZE in the btree code For portability to userspace, we should try to avoid working in kernel pages. Signed-off-by: Kent Overstreet <kent.overstreet@linux.dev>
|
#
a34782a0 |
|
17-Jun-2020 |
Kent Overstreet <kent.overstreet@gmail.com> |
bcachefs: Change bch2_dump_bset() to also print key values Signed-off-by: Kent Overstreet <kent.overstreet@gmail.com> Signed-off-by: Kent Overstreet <kent.overstreet@linux.dev>
|
#
2dac0eae |
|
18-Feb-2020 |
Kent Overstreet <kent.overstreet@gmail.com> |
bcachefs: Iterator debug code improvements More aggressively checking iterator invariants, and fixing the resulting bugs. Also greatly simplifying iter_next() and iter_next_slot() - they were hyper optimized before, but the optimizations were getting too brittle. Signed-off-by: Kent Overstreet <kent.overstreet@gmail.com> Signed-off-by: Kent Overstreet <kent.overstreet@linux.dev>
|
#
24e0c3f8 |
|
07-Mar-2020 |
Kent Overstreet <kent.overstreet@gmail.com> |
bcachefs: Fix bch2_dump_bset() It's used in the write path when the bset isn't in the btree node buffer. Signed-off-by: Kent Overstreet <kent.overstreet@gmail.com> Signed-off-by: Kent Overstreet <kent.overstreet@linux.dev>
|
#
fdf22400 |
|
30-Jan-2020 |
Kent Overstreet <kent.overstreet@gmail.com> |
bcachefs: Improve an insert path optimization The insert path had an optimization to short circuit lookup table/iterator fixups when overwriting an existing key with the same size value - but it was incorrect when other key fields (size/version) were changing. This is important for the upcoming rework to have extent updates use the same insert path as regular keys. Signed-off-by: Kent Overstreet <kent.overstreet@gmail.com> Signed-off-by: Kent Overstreet <kent.overstreet@linux.dev>
|
#
9626aeb1 |
|
06-Jan-2020 |
Kent Overstreet <kent.overstreet@gmail.com> |
bcachefs: Rework iter->pos handling - Rework some of the helper comparison functions for consistency - Currently trying to refactor all the logic that's different for extents in the btree iterator code. The main difference is that for non extents we search for a key greater than or equal to the search key, while for extents we search for a key strictly greater than the search key (iter->pos). So that logic is now handled by btree_iter_search_key(), which computes the real search key based on iter->pos and whether or not we're searching for a key >= or > iter->pos. Signed-off-by: Kent Overstreet <kent.overstreet@gmail.com> Signed-off-by: Kent Overstreet <kent.overstreet@linux.dev>
|
#
c201e2d9 |
|
26-Nov-2019 |
Kent Overstreet <kent.overstreet@gmail.com> |
bcachefs: Fix bch2_verify_insert_pos() We were calling __btree_node_key_to_offset() on a key that wasn't in the btree node. Signed-off-by: Kent Overstreet <kent.overstreet@gmail.com> Signed-off-by: Kent Overstreet <kent.overstreet@linux.dev>
|
#
ad44bdc3 |
|
09-Nov-2019 |
Kent Overstreet <kent.overstreet@gmail.com> |
bcachefs: bkey noops For upcoming inline data extents, we're going to need to be able to shorten the value of existing bkeys in the btree - and to make that work we're going to be able to need to pad out the space the value previously took up with something. This patch changes the various code that iterates over bkeys to handle k->u64s == 0 as meaning "skip the next 8 bytes". Signed-off-by: Kent Overstreet <kent.overstreet@gmail.com> Signed-off-by: Kent Overstreet <kent.overstreet@linux.dev>
|
#
b904a799 |
|
06-Nov-2019 |
Kent Overstreet <kent.overstreet@gmail.com> |
bcachefs: Go back to 16 bit mantissa bkey floats The previous optimizations means using 32 bit mantissas are now a net loss - having bkey_float be only 4 bytes is good for prefetching. Signed-off-by: Kent Overstreet <kent.overstreet@gmail.com> Signed-off-by: Kent Overstreet <kent.overstreet@linux.dev>
|
#
58404bb2 |
|
23-Oct-2019 |
Kent Overstreet <kent.overstreet@gmail.com> |
bcachefs: Fall back to slowpath on exact comparison This is basically equivalent to the original strategy of falling back to checking against the original key when the original key and previous key didn't differ in the required bits - except, now we only fall back when the search key doesn't differ in the required bits, which ends up being a bit faster. Signed-off-by: Kent Overstreet <kent.overstreet@gmail.com> Signed-off-by: Kent Overstreet <kent.overstreet@linux.dev>
|
#
1bdb67e8 |
|
06-Nov-2019 |
Kent Overstreet <kent.overstreet@gmail.com> |
bcachefs: kill BFLOAT_FAILED_PREV The assumption underlying BFLOAT_FAILED_PREV was wrong; the comparison we're doing in bset_search_tree() doesn't have to tell the pivot apart from the previous key, it just has to tell if search is definitely greater than or equal to the pivot. Signed-off-by: Kent Overstreet <kent.overstreet@gmail.com> Signed-off-by: Kent Overstreet <kent.overstreet@linux.dev>
|
#
c4537686 |
|
07-Nov-2019 |
Kent Overstreet <kent.overstreet@gmail.com> |
bcachefs: Pipeline binary searches and linear searches This makes prefetching for the linear search at the end of the lookup much more effective, and is a couple percent speedup. Signed-off-by: Kent Overstreet <kent.overstreet@gmail.com> Signed-off-by: Kent Overstreet <kent.overstreet@linux.dev>
|
#
c4e065c2 |
|
23-Oct-2019 |
Kent Overstreet <kent.overstreet@gmail.com> |
bcachefs: More bset.c microoptimization Improve a few paper cuts that've shown up during profiling. Signed-off-by: Kent Overstreet <kent.overstreet@gmail.com> Signed-off-by: Kent Overstreet <kent.overstreet@linux.dev>
|
#
e67ab045 |
|
19-Aug-2019 |
Kent Overstreet <kent.overstreet@gmail.com> |
bcachefs: Fix bch2_btree_node_iter_prev_filter() bch2_btree_node_iter_prev_filter() tried to be smart about iterating backwards when skipping over whiteouts/discards - but unfortunately, doing so can leave the node iterator in an inconsistent state; the sane solution is to just always iterate backwards one key at a time. But we compact btree nodes when more than a quarter of the keys are whiteouts/discards, so the optimization wasn't buying us that much anyways. Signed-off-by: Kent Overstreet <kent.overstreet@linux.dev>
|
#
63f1a598 |
|
17-Aug-2019 |
Kent Overstreet <kent.overstreet@gmail.com> |
bcachefs: Improved debug checks Signed-off-by: Kent Overstreet <kent.overstreet@linux.dev>
|
#
f13f5a8c |
|
27-Mar-2019 |
Kent Overstreet <kent.overstreet@gmail.com> |
bcachefs: move some checks to expensive_debug_checks Signed-off-by: Kent Overstreet <kent.overstreet@linux.dev>
|
#
319f9ac3 |
|
08-Nov-2018 |
Kent Overstreet <kent.overstreet@gmail.com> |
bcachefs: revamp to_text methods Signed-off-by: Kent Overstreet <kent.overstreet@linux.dev>
|
#
ac10a961 |
|
03-Nov-2018 |
Kent Overstreet <kent.overstreet@gmail.com> |
bcachefs: Some fixes for building in userspace userspace allocators don't align allocations as nicely as kernel allocators, which meant that in some cases we weren't allocating big enough bvec arrays - just make the calculations more rigorous and explicit to fix it. Signed-off-by: Kent Overstreet <kent.overstreet@linux.dev>
|
#
b564513c |
|
01-Nov-2018 |
Kent Overstreet <kent.overstreet@gmail.com> |
bcachefs: fix bch2_bkey_print_bfloat was popping an assertion in the eytzinger code Signed-off-by: Kent Overstreet <kent.overstreet@linux.dev>
|
#
a00fd8c5 |
|
21-Aug-2018 |
Kent Overstreet <kent.overstreet@gmail.com> |
bcachefs: Comparison function cleanups Signed-off-by: Kent Overstreet <kent.overstreet@linux.dev>
|
#
216c9fac |
|
11-Aug-2018 |
Kent Overstreet <kent.overstreet@gmail.com> |
bcachefs: Pass around bset_tree less Signed-off-by: Kent Overstreet <kent.overstreet@linux.dev>
|
#
cc1add4a |
|
05-Aug-2018 |
Kent Overstreet <kent.overstreet@gmail.com> |
bcachefs: BTREE_INSERT_JOURNAL_RES_FULL is no longer possible Signed-off-by: Kent Overstreet <kent.overstreet@linux.dev>
|
#
271a3d3a |
|
21-Jul-2016 |
Kent Overstreet <kent.overstreet@gmail.com> |
bcachefs: lift ordering restriction on 0 size extents This lifts the restriction that 0 size extents must not overlap with other extents, which means we can now sort extents and non extents the same way, and will let us simplify a bunch of other stuff as well. Signed-off-by: Kent Overstreet <kent.overstreet@linux.dev>
|
#
1fe08f31 |
|
05-Aug-2018 |
Kent Overstreet <kent.overstreet@gmail.com> |
bcachefs: bkey_written() also cleanups of btree node offsets Signed-off-by: Kent Overstreet <kent.overstreet@linux.dev>
|
#
617391ba |
|
05-Aug-2018 |
Kent Overstreet <kent.overstreet@gmail.com> |
bcachefs: improved rw_aux_tree_bsearch() shouldn't be any reason for an actual binary search here Signed-off-by: Kent Overstreet <kent.overstreet@linux.dev>
|
#
1c6fdbd8 |
|
17-Mar-2017 |
Kent Overstreet <kent.overstreet@gmail.com> |
bcachefs: Initial commit Initially forked from drivers/md/bcache, bcachefs is a new copy-on-write filesystem with every feature you could possibly want. Website: https://bcachefs.org Signed-off-by: Kent Overstreet <kent.overstreet@linux.dev>
|