summaryrefslogtreecommitdiff
path: root/fs/bcachefs/bset.c
AgeCommit message (Collapse)Author
2023-10-22bcachefs: KEY_TYPE_discard is no longer usedKent Overstreet
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>
2023-10-22bcachefs: Inline make_bfloat() into __build_ro_aux_tree()Kent Overstreet
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>
2023-10-22bcachefs: add const annotations to bset.cKent Overstreet
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>
2023-10-22bcachefs: Drop sysfs interface to debug parametersKent Overstreet
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>
2023-10-22bcachefs: Remove some uses of PAGE_SIZE in the btree codeKent Overstreet
For portability to userspace, we should try to avoid working in kernel pages. Signed-off-by: Kent Overstreet <kent.overstreet@linux.dev>
2023-10-22bcachefs: Change bch2_dump_bset() to also print key valuesKent Overstreet
Signed-off-by: Kent Overstreet <kent.overstreet@gmail.com> Signed-off-by: Kent Overstreet <kent.overstreet@linux.dev>
2023-10-22bcachefs: Iterator debug code improvementsKent Overstreet
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>
2023-10-22bcachefs: Fix bch2_dump_bset()Kent Overstreet
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>
2023-10-22bcachefs: Improve an insert path optimizationKent Overstreet
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>
2023-10-22bcachefs: Rework iter->pos handlingKent Overstreet
- 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>
2023-10-22bcachefs: Fix bch2_verify_insert_pos()Kent Overstreet
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>
2023-10-22bcachefs: bkey noopsKent Overstreet
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>
2023-10-22bcachefs: Go back to 16 bit mantissa bkey floatsKent Overstreet
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>
2023-10-22bcachefs: Fall back to slowpath on exact comparisonKent Overstreet
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>
2023-10-22bcachefs: kill BFLOAT_FAILED_PREVKent Overstreet
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>
2023-10-22bcachefs: Pipeline binary searches and linear searchesKent Overstreet
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>
2023-10-22bcachefs: More bset.c microoptimizationKent Overstreet
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>
2023-10-22bcachefs: Fix bch2_btree_node_iter_prev_filter()Kent Overstreet
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>
2023-10-22bcachefs: Improved debug checksKent Overstreet
Signed-off-by: Kent Overstreet <kent.overstreet@linux.dev>
2023-10-22bcachefs: move some checks to expensive_debug_checksKent Overstreet
Signed-off-by: Kent Overstreet <kent.overstreet@linux.dev>
2023-10-22bcachefs: revamp to_text methodsKent Overstreet
Signed-off-by: Kent Overstreet <kent.overstreet@linux.dev>
2023-10-22bcachefs: Some fixes for building in userspaceKent Overstreet
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>
2023-10-22bcachefs: fix bch2_bkey_print_bfloatKent Overstreet
was popping an assertion in the eytzinger code Signed-off-by: Kent Overstreet <kent.overstreet@linux.dev>
2023-10-22bcachefs: Comparison function cleanupsKent Overstreet
Signed-off-by: Kent Overstreet <kent.overstreet@linux.dev>
2023-10-22bcachefs: Pass around bset_tree lessKent Overstreet
Signed-off-by: Kent Overstreet <kent.overstreet@linux.dev>
2023-10-22bcachefs: BTREE_INSERT_JOURNAL_RES_FULL is no longer possibleKent Overstreet
Signed-off-by: Kent Overstreet <kent.overstreet@linux.dev>
2023-10-22bcachefs: lift ordering restriction on 0 size extentsKent Overstreet
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>
2023-10-22bcachefs: bkey_written()Kent Overstreet
also cleanups of btree node offsets Signed-off-by: Kent Overstreet <kent.overstreet@linux.dev>
2023-10-22bcachefs: improved rw_aux_tree_bsearch()Kent Overstreet
shouldn't be any reason for an actual binary search here Signed-off-by: Kent Overstreet <kent.overstreet@linux.dev>
2023-10-22bcachefs: Initial commitKent Overstreet
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>