diff options
| -rw-r--r-- | fs/bcachefs/bkey_sort.c | 278 | ||||
| -rw-r--r-- | fs/bcachefs/bkey_sort.h | 8 | ||||
| -rw-r--r-- | fs/bcachefs/btree_io.c | 195 | ||||
| -rw-r--r-- | fs/bcachefs/btree_types.h | 2 | ||||
| -rw-r--r-- | fs/bcachefs/btree_update_interior.c | 9 | ||||
| -rw-r--r-- | fs/bcachefs/recovery.c | 6 |
6 files changed, 30 insertions, 468 deletions
diff --git a/fs/bcachefs/bkey_sort.c b/fs/bcachefs/bkey_sort.c index 2e1d9cd65f43..a88670753cb0 100644 --- a/fs/bcachefs/bkey_sort.c +++ b/fs/bcachefs/bkey_sort.c @@ -14,9 +14,8 @@ static inline bool sort_iter_end(struct sort_iter *iter) return !iter->used; } -static inline void __sort_iter_sift(struct sort_iter *iter, - unsigned from, - sort_cmp_fn cmp) +static inline void sort_iter_sift(struct sort_iter *iter, unsigned from, + sort_cmp_fn cmp) { unsigned i; @@ -27,18 +26,12 @@ static inline void __sort_iter_sift(struct sort_iter *iter, swap(iter->data[i], iter->data[i + 1]); } -static inline void sort_iter_sift(struct sort_iter *iter, sort_cmp_fn cmp) -{ - - __sort_iter_sift(iter, 0, cmp); -} - static inline void sort_iter_sort(struct sort_iter *iter, sort_cmp_fn cmp) { unsigned i = iter->used; while (i--) - __sort_iter_sift(iter, i, cmp); + sort_iter_sift(iter, i, cmp); } static inline struct bkey_packed *sort_iter_peek(struct sort_iter *iter) @@ -46,26 +39,20 @@ static inline struct bkey_packed *sort_iter_peek(struct sort_iter *iter) return !sort_iter_end(iter) ? iter->data->k : NULL; } -static inline void __sort_iter_advance(struct sort_iter *iter, - unsigned idx, sort_cmp_fn cmp) +static inline void sort_iter_advance(struct sort_iter *iter, sort_cmp_fn cmp) { - struct sort_iter_set *i = iter->data + idx; + struct sort_iter_set *i = iter->data; - BUG_ON(idx >= iter->used); + BUG_ON(!iter->used); i->k = bkey_next_skip_noops(i->k, i->end); BUG_ON(i->k > i->end); if (i->k == i->end) - array_remove_item(iter->data, iter->used, idx); + array_remove_item(iter->data, iter->used, 0); else - __sort_iter_sift(iter, idx, cmp); -} - -static inline void sort_iter_advance(struct sort_iter *iter, sort_cmp_fn cmp) -{ - __sort_iter_advance(iter, 0, cmp); + sort_iter_sift(iter, 0, cmp); } static inline struct bkey_packed *sort_iter_next(struct sort_iter *iter, @@ -264,252 +251,3 @@ unsigned bch2_sort_keys(struct bkey_packed *dst, return (u64 *) out - (u64 *) dst; } - -/* Compat code for btree_node_old_extent_overwrite: */ - -/* - * If keys compare equal, compare by pointer order: - * - * Necessary for sort_fix_overlapping() - if there are multiple keys that - * compare equal in different sets, we have to process them newest to oldest. - */ -static inline int extent_sort_fix_overlapping_cmp(struct btree *b, - struct bkey_packed *l, - struct bkey_packed *r) -{ - struct bkey ul = bkey_unpack_key(b, l); - struct bkey ur = bkey_unpack_key(b, r); - - return bkey_cmp(bkey_start_pos(&ul), - bkey_start_pos(&ur)) ?: - cmp_int((unsigned long) r, (unsigned long) l); -} - -/* - * The algorithm in extent_sort_fix_overlapping() relies on keys in the same - * bset being ordered by start offset - but 0 size whiteouts (which are always - * KEY_TYPE_deleted) break this ordering, so we need to skip over them: - */ -static void extent_iter_advance(struct sort_iter *iter, unsigned idx) -{ - struct sort_iter_set *i = iter->data + idx; - - do { - i->k = bkey_next_skip_noops(i->k, i->end); - } while (i->k != i->end && bkey_deleted(i->k)); - - if (i->k == i->end) - array_remove_item(iter->data, iter->used, idx); - else - __sort_iter_sift(iter, idx, extent_sort_fix_overlapping_cmp); -} - -struct btree_nr_keys -bch2_extent_sort_fix_overlapping(struct bch_fs *c, struct bset *dst, - struct sort_iter *iter) -{ - struct btree *b = iter->b; - struct bkey_format *f = &b->format; - struct sort_iter_set *_l = iter->data, *_r = iter->data + 1; - struct bkey_packed *out = dst->start; - struct bkey l_unpacked, r_unpacked; - struct bkey_s l, r; - struct btree_nr_keys nr; - struct bkey_buf split; - unsigned i; - - memset(&nr, 0, sizeof(nr)); - bch2_bkey_buf_init(&split); - - sort_iter_sort(iter, extent_sort_fix_overlapping_cmp); - for (i = 0; i < iter->used;) { - if (bkey_deleted(iter->data[i].k)) - __sort_iter_advance(iter, i, - extent_sort_fix_overlapping_cmp); - else - i++; - } - - while (!sort_iter_end(iter)) { - l = __bkey_disassemble(b, _l->k, &l_unpacked); - - if (iter->used == 1) { - extent_sort_append(c, f, &nr, &out, l); - extent_iter_advance(iter, 0); - continue; - } - - r = __bkey_disassemble(b, _r->k, &r_unpacked); - - /* If current key and next key don't overlap, just append */ - if (bkey_cmp(l.k->p, bkey_start_pos(r.k)) <= 0) { - extent_sort_append(c, f, &nr, &out, l); - extent_iter_advance(iter, 0); - continue; - } - - /* Skip 0 size keys */ - if (!r.k->size) { - extent_iter_advance(iter, 1); - continue; - } - - /* - * overlap: keep the newer key and trim the older key so they - * don't overlap. comparing pointers tells us which one is - * newer, since the bsets are appended one after the other. - */ - - /* can't happen because of comparison func */ - BUG_ON(_l->k < _r->k && - !bkey_cmp(bkey_start_pos(l.k), bkey_start_pos(r.k))); - - if (_l->k > _r->k) { - /* l wins, trim r */ - if (bkey_cmp(l.k->p, r.k->p) >= 0) { - extent_iter_advance(iter, 1); - } else { - bch2_cut_front_s(l.k->p, r); - extent_save(b, _r->k, r.k); - __sort_iter_sift(iter, 1, - extent_sort_fix_overlapping_cmp); - } - } else if (bkey_cmp(l.k->p, r.k->p) > 0) { - - /* - * r wins, but it overlaps in the middle of l - split l: - */ - bch2_bkey_buf_reassemble(&split, c, l.s_c); - bch2_cut_back(bkey_start_pos(r.k), split.k); - - bch2_cut_front_s(r.k->p, l); - extent_save(b, _l->k, l.k); - - __sort_iter_sift(iter, 0, - extent_sort_fix_overlapping_cmp); - - extent_sort_append(c, f, &nr, &out, - bkey_i_to_s(split.k)); - } else { - bch2_cut_back_s(bkey_start_pos(r.k), l); - extent_save(b, _l->k, l.k); - } - } - - dst->u64s = cpu_to_le16((u64 *) out - dst->_data); - - bch2_bkey_buf_exit(&split, c); - return nr; -} - -static inline int sort_extents_cmp(struct btree *b, - struct bkey_packed *l, - struct bkey_packed *r) -{ - return bch2_bkey_cmp_packed(b, l, r) ?: - (int) bkey_deleted(l) - (int) bkey_deleted(r); -} - -unsigned bch2_sort_extents(struct bkey_packed *dst, - struct sort_iter *iter, - bool filter_whiteouts) -{ - struct bkey_packed *in, *out = dst; - - sort_iter_sort(iter, sort_extents_cmp); - - while ((in = sort_iter_next(iter, sort_extents_cmp))) { - if (bkey_deleted(in)) - continue; - - if (bkey_whiteout(in) && - (filter_whiteouts || !in->needs_whiteout)) - continue; - - bkey_copy(out, in); - out = bkey_next(out); - } - - return (u64 *) out - (u64 *) dst; -} - -static inline int sort_extent_whiteouts_cmp(struct btree *b, - struct bkey_packed *l, - struct bkey_packed *r) -{ - struct bkey ul = bkey_unpack_key(b, l); - struct bkey ur = bkey_unpack_key(b, r); - - return bkey_cmp(bkey_start_pos(&ul), bkey_start_pos(&ur)); -} - -unsigned bch2_sort_extent_whiteouts(struct bkey_packed *dst, - struct sort_iter *iter) -{ - const struct bkey_format *f = &iter->b->format; - struct bkey_packed *in, *out = dst; - struct bkey_i l, r; - bool prev = false, l_packed = false; - u64 max_packed_size = bkey_field_max(f, BKEY_FIELD_SIZE); - u64 max_packed_offset = bkey_field_max(f, BKEY_FIELD_OFFSET); - u64 new_size; - - max_packed_size = min_t(u64, max_packed_size, KEY_SIZE_MAX); - - sort_iter_sort(iter, sort_extent_whiteouts_cmp); - - while ((in = sort_iter_next(iter, sort_extent_whiteouts_cmp))) { - if (bkey_deleted(in)) - continue; - - EBUG_ON(bkeyp_val_u64s(f, in)); - EBUG_ON(in->type != KEY_TYPE_discard); - - r.k = bkey_unpack_key(iter->b, in); - - if (prev && - bkey_cmp(l.k.p, bkey_start_pos(&r.k)) >= 0) { - if (bkey_cmp(l.k.p, r.k.p) >= 0) - continue; - - new_size = l_packed - ? min(max_packed_size, max_packed_offset - - bkey_start_offset(&l.k)) - : KEY_SIZE_MAX; - - new_size = min(new_size, r.k.p.offset - - bkey_start_offset(&l.k)); - - BUG_ON(new_size < l.k.size); - - bch2_key_resize(&l.k, new_size); - - if (bkey_cmp(l.k.p, r.k.p) >= 0) - continue; - - bch2_cut_front(l.k.p, &r); - } - - if (prev) { - if (!bch2_bkey_pack(out, &l, f)) { - BUG_ON(l_packed); - bkey_copy(out, &l); - } - out = bkey_next(out); - } - - l = r; - prev = true; - l_packed = bkey_packed(in); - } - - if (prev) { - if (!bch2_bkey_pack(out, &l, f)) { - BUG_ON(l_packed); - bkey_copy(out, &l); - } - out = bkey_next(out); - } - - return (u64 *) out - (u64 *) dst; -} diff --git a/fs/bcachefs/bkey_sort.h b/fs/bcachefs/bkey_sort.h index 458a051fdac5..1059996dac78 100644 --- a/fs/bcachefs/bkey_sort.h +++ b/fs/bcachefs/bkey_sort.h @@ -32,9 +32,6 @@ static inline void sort_iter_add(struct sort_iter *iter, struct btree_nr_keys bch2_key_sort_fix_overlapping(struct bch_fs *, struct bset *, struct sort_iter *); -struct btree_nr_keys -bch2_extent_sort_fix_overlapping(struct bch_fs *, struct bset *, - struct sort_iter *); struct btree_nr_keys bch2_sort_repack(struct bset *, struct btree *, @@ -48,10 +45,5 @@ bch2_sort_repack_merge(struct bch_fs *, unsigned bch2_sort_keys(struct bkey_packed *, struct sort_iter *, bool); -unsigned bch2_sort_extents(struct bkey_packed *, - struct sort_iter *, bool); - -unsigned bch2_sort_extent_whiteouts(struct bkey_packed *, - struct sort_iter *); #endif /* _BCACHEFS_BKEY_SORT_H */ diff --git a/fs/bcachefs/btree_io.c b/fs/bcachefs/btree_io.c index c7c91c1d5b23..b3743a16973c 100644 --- a/fs/bcachefs/btree_io.c +++ b/fs/bcachefs/btree_io.c @@ -24,8 +24,7 @@ static void verify_no_dups(struct btree *b, struct bkey_packed *start, - struct bkey_packed *end, - bool extents) + struct bkey_packed *end) { #ifdef CONFIG_BCACHEFS_DEBUG struct bkey_packed *k, *p; @@ -39,10 +38,7 @@ static void verify_no_dups(struct btree *b, struct bkey l = bkey_unpack_key(b, p); struct bkey r = bkey_unpack_key(b, k); - BUG_ON(extents - ? bkey_cmp(l.p, bkey_start_pos(&r)) > 0 - : bkey_cmp(l.p, bkey_start_pos(&r)) >= 0); - //BUG_ON(bch2_bkey_cmp_packed(&b->format, p, k) >= 0); + BUG_ON(bkey_cmp(l.p, bkey_start_pos(&r)) >= 0); } #endif } @@ -150,8 +146,7 @@ static void bch2_sort_whiteouts(struct bch_fs *c, struct btree *b) } verify_no_dups(b, new_whiteouts, - (void *) ((u64 *) new_whiteouts + b->whiteout_u64s), - btree_node_old_extent_overwrite(b)); + (void *) ((u64 *) new_whiteouts + b->whiteout_u64s)); memcpy_u64s(unwritten_whiteouts_start(c, b), new_whiteouts, b->whiteout_u64s); @@ -176,144 +171,6 @@ static bool should_compact_bset(struct btree *b, struct bset_tree *t, } } -static bool bch2_compact_extent_whiteouts(struct bch_fs *c, - struct btree *b, - enum compact_mode mode) -{ - const struct bkey_format *f = &b->format; - struct bset_tree *t; - struct bkey_packed *whiteouts = NULL; - struct bkey_packed *u_start, *u_pos; - struct sort_iter sort_iter; - unsigned bytes, whiteout_u64s = 0, u64s; - bool used_mempool, compacting = false; - - BUG_ON(!btree_node_is_extents(b)); - - for_each_bset(b, t) - if (should_compact_bset(b, t, whiteout_u64s != 0, mode)) - whiteout_u64s += bset_dead_u64s(b, t); - - if (!whiteout_u64s) - return false; - - bch2_sort_whiteouts(c, b); - - sort_iter_init(&sort_iter, b); - - whiteout_u64s += b->whiteout_u64s; - bytes = whiteout_u64s * sizeof(u64); - - whiteouts = btree_bounce_alloc(c, bytes, &used_mempool); - u_start = u_pos = whiteouts; - - memcpy_u64s(u_pos, unwritten_whiteouts_start(c, b), - b->whiteout_u64s); - u_pos = (void *) u_pos + b->whiteout_u64s * sizeof(u64); - - sort_iter_add(&sort_iter, u_start, u_pos); - - for_each_bset(b, t) { - struct bset *i = bset(b, t); - struct bkey_packed *k, *n, *out, *start, *end; - struct btree_node_entry *src = NULL, *dst = NULL; - - if (t != b->set && !bset_written(b, i)) { - src = container_of(i, struct btree_node_entry, keys); - dst = max(write_block(b), - (void *) btree_bkey_last(b, t - 1)); - } - - if (src != dst) - compacting = true; - - if (!should_compact_bset(b, t, compacting, mode)) { - if (src != dst) { - memmove(dst, src, sizeof(*src) + - le16_to_cpu(src->keys.u64s) * - sizeof(u64)); - i = &dst->keys; - set_btree_bset(b, t, i); - } - continue; - } - - compacting = true; - u_start = u_pos; - start = i->start; - end = vstruct_last(i); - - if (src != dst) { - memmove(dst, src, sizeof(*src)); - i = &dst->keys; - set_btree_bset(b, t, i); - } - - out = i->start; - - for (k = start; k != end; k = n) { - n = bkey_next_skip_noops(k, end); - - if (bkey_deleted(k)) - continue; - - BUG_ON(bkey_whiteout(k) && - k->needs_whiteout && - bkey_written(b, k)); - - if (bkey_whiteout(k) && !k->needs_whiteout) - continue; - - if (bkey_whiteout(k)) { - memcpy_u64s(u_pos, k, bkeyp_key_u64s(f, k)); - set_bkeyp_val_u64s(f, u_pos, 0); - u_pos = bkey_next(u_pos); - } else { - bkey_copy(out, k); - out = bkey_next(out); - } - } - - sort_iter_add(&sort_iter, u_start, u_pos); - - i->u64s = cpu_to_le16((u64 *) out - i->_data); - set_btree_bset_end(b, t); - bch2_bset_set_no_aux_tree(b, t); - } - - b->whiteout_u64s = (u64 *) u_pos - (u64 *) whiteouts; - - BUG_ON((void *) unwritten_whiteouts_start(c, b) < - (void *) btree_bkey_last(b, bset_tree_last(b))); - - u64s = bch2_sort_extent_whiteouts(unwritten_whiteouts_start(c, b), - &sort_iter); - - BUG_ON(u64s > b->whiteout_u64s); - BUG_ON(u_pos != whiteouts && !u64s); - - if (u64s != b->whiteout_u64s) { - void *src = unwritten_whiteouts_start(c, b); - - b->whiteout_u64s = u64s; - memmove_u64s_up(unwritten_whiteouts_start(c, b), src, u64s); - } - - verify_no_dups(b, - unwritten_whiteouts_start(c, b), - unwritten_whiteouts_end(c, b), - true); - - btree_bounce_free(c, bytes, used_mempool, whiteouts); - - bch2_btree_build_aux_trees(b); - - bch_btree_keys_u64s_remaining(c, b); - bch2_verify_btree_nr_keys(b); - - return true; -} - static bool bch2_drop_whiteouts(struct btree *b, enum compact_mode mode) { struct bset_tree *t; @@ -382,9 +239,7 @@ static bool bch2_drop_whiteouts(struct btree *b, enum compact_mode mode) bool bch2_compact_whiteouts(struct bch_fs *c, struct btree *b, enum compact_mode mode) { - return !btree_node_old_extent_overwrite(b) - ? bch2_drop_whiteouts(b, mode) - : bch2_compact_extent_whiteouts(c, b, mode); + return bch2_drop_whiteouts(b, mode); } static void btree_node_sort(struct bch_fs *c, struct btree *b, @@ -422,14 +277,7 @@ static void btree_node_sort(struct bch_fs *c, struct btree *b, start_time = local_clock(); - if (btree_node_old_extent_overwrite(b)) - filter_whiteouts = bset_written(b, start_bset); - - u64s = (btree_node_old_extent_overwrite(b) - ? bch2_sort_extents - : bch2_sort_keys)(out->keys.start, - &sort_iter, - filter_whiteouts); + u64s = bch2_sort_keys(out->keys.start, &sort_iter, filter_whiteouts); out->keys.u64s = cpu_to_le16(u64s); @@ -971,11 +819,10 @@ int bch2_btree_node_read_done(struct bch_fs *c, struct bch_dev *ca, bset_encrypt(c, i, b->written << 9); - if (btree_node_is_extents(b) && - !BTREE_NODE_NEW_EXTENT_OVERWRITE(b->data)) { - set_btree_node_old_extent_overwrite(b); - set_btree_node_need_rewrite(b); - } + btree_err_on(btree_node_is_extents(b) && + !BTREE_NODE_NEW_EXTENT_OVERWRITE(b->data), + BTREE_ERR_FATAL, c, NULL, b, NULL, + "btree node does not have NEW_EXTENT_OVERWRITE set"); sectors = vstruct_sectors(b->data, c->block_bits); } else { @@ -1052,9 +899,7 @@ int bch2_btree_node_read_done(struct bch_fs *c, struct bch_dev *ca, set_btree_bset(b, b->set, &b->data->keys); - b->nr = (btree_node_old_extent_overwrite(b) - ? bch2_extent_sort_fix_overlapping - : bch2_key_sort_fix_overlapping)(c, &sorted->keys, iter); + b->nr = bch2_key_sort_fix_overlapping(c, &sorted->keys, iter); u64s = le16_to_cpu(sorted->keys.u64s); *sorted = *b->data; @@ -1598,24 +1443,14 @@ void __bch2_btree_node_write(struct bch_fs *c, struct btree *b, i->journal_seq = cpu_to_le64(seq); i->u64s = 0; - if (!btree_node_old_extent_overwrite(b)) { - sort_iter_add(&sort_iter, - unwritten_whiteouts_start(c, b), - unwritten_whiteouts_end(c, b)); - SET_BSET_SEPARATE_WHITEOUTS(i, false); - } else { - memcpy_u64s(i->start, - unwritten_whiteouts_start(c, b), - b->whiteout_u64s); - i->u64s = cpu_to_le16(b->whiteout_u64s); - SET_BSET_SEPARATE_WHITEOUTS(i, true); - } + sort_iter_add(&sort_iter, + unwritten_whiteouts_start(c, b), + unwritten_whiteouts_end(c, b)); + SET_BSET_SEPARATE_WHITEOUTS(i, false); b->whiteout_u64s = 0; - u64s = btree_node_old_extent_overwrite(b) - ? bch2_sort_extents(vstruct_last(i), &sort_iter, false) - : bch2_sort_keys(i->start, &sort_iter, false); + u64s = bch2_sort_keys(i->start, &sort_iter, false); le16_add_cpu(&i->u64s, u64s); set_needs_whiteout(i, false); diff --git a/fs/bcachefs/btree_types.h b/fs/bcachefs/btree_types.h index 38414d19e71e..35511d47ae97 100644 --- a/fs/bcachefs/btree_types.h +++ b/fs/bcachefs/btree_types.h @@ -418,7 +418,6 @@ enum btree_flags { BTREE_NODE_just_written, BTREE_NODE_dying, BTREE_NODE_fake, - BTREE_NODE_old_extent_overwrite, BTREE_NODE_need_rewrite, BTREE_NODE_never_write, }; @@ -433,7 +432,6 @@ BTREE_FLAG(write_in_flight); BTREE_FLAG(just_written); BTREE_FLAG(dying); BTREE_FLAG(fake); -BTREE_FLAG(old_extent_overwrite); BTREE_FLAG(need_rewrite); BTREE_FLAG(never_write); diff --git a/fs/bcachefs/btree_update_interior.c b/fs/bcachefs/btree_update_interior.c index 989ba81207c9..63cda00bb4ad 100644 --- a/fs/bcachefs/btree_update_interior.c +++ b/fs/bcachefs/btree_update_interior.c @@ -303,14 +303,7 @@ static struct btree *bch2_btree_node_alloc(struct btree_update *as, unsigned lev bp->v.sectors_written = 0; } - if (c->sb.features & (1ULL << BCH_FEATURE_new_extent_overwrite)) - SET_BTREE_NODE_NEW_EXTENT_OVERWRITE(b->data, true); - - if (btree_node_is_extents(b) && - !BTREE_NODE_NEW_EXTENT_OVERWRITE(b->data)) { - set_btree_node_old_extent_overwrite(b); - set_btree_node_need_rewrite(b); - } + SET_BTREE_NODE_NEW_EXTENT_OVERWRITE(b->data, true); bch2_btree_build_aux_trees(b); diff --git a/fs/bcachefs/recovery.c b/fs/bcachefs/recovery.c index 740fdeafe1a2..4d7badcc568b 100644 --- a/fs/bcachefs/recovery.c +++ b/fs/bcachefs/recovery.c @@ -983,6 +983,12 @@ int bch2_fs_recovery(struct bch_fs *c) bch_info(c, "recovering from clean shutdown, journal seq %llu", le64_to_cpu(clean->journal_seq)); + if (!(c->sb.features & (1ULL << BCH_FEATURE_new_extent_overwrite))) { + bch_err(c, "feature new_extent_overwrite not set, filesystem no longer supported"); + ret = -EINVAL; + goto err; + } + if (!(c->sb.features & (1ULL << BCH_FEATURE_alloc_v2))) { bch_info(c, "alloc_v2 feature bit not set, fsck required"); c->opts.fsck = true; |