- struct bkey_s_c_extent e = bkey_s_c_to_extent(k);
- const struct bch_extent_ptr *ptr;
- unsigned seq;
- const char *err;
- char buf[160];
- struct bucket_mark mark;
- struct bch_dev *ca;
- unsigned replicas = 0;
- bool bad;
-
- extent_for_each_ptr(e, ptr) {
- ca = bch_dev_bkey_exists(c, ptr->dev);
- replicas++;
-
- if (!test_bit(BCH_FS_ALLOC_READ_DONE, &c->flags))
- continue;
-
- err = "stale";
- if (ptr_stale(ca, ptr))
- goto err;
-
- do {
- seq = read_seqcount_begin(&c->gc_pos_lock);
- mark = ptr_bucket_mark(ca, ptr);
-
- bad = gc_pos_cmp(c->gc_pos, gc_pos_btree_node(b)) > 0 &&
- (mark.data_type != BCH_DATA_BTREE ||
- mark.dirty_sectors < c->opts.btree_node_size);
- } while (read_seqcount_retry(&c->gc_pos_lock, seq));
-
- err = "inconsistent";
- if (bad)
- goto err;
- }
-
- if (!bch2_bkey_replicas_marked(c, BCH_DATA_BTREE, e.s_c)) {
- bch2_bkey_val_to_text(c, btree_node_type(b),
- buf, sizeof(buf), k);
- bch2_fs_bug(c,
- "btree key bad (replicas not marked in superblock):\n%s",
- buf);
- return;
- }
-
- return;
-err:
- bch2_bkey_val_to_text(c, btree_node_type(b), buf, sizeof(buf), k);
- bch2_fs_bug(c, "%s btree pointer %s: bucket %zi "
- "gen %i mark %08x",
- err, buf, PTR_BUCKET_NR(ca, ptr),
- mark.gen, (unsigned) mark.counter);
-}
-
-static void bch2_btree_ptr_to_text(struct bch_fs *c, char *buf,
- size_t size, struct bkey_s_c k)
-{
- char *out = buf, *end = buf + size;
- const char *invalid;
-
-#define p(...) (out += scnprintf(out, end - out, __VA_ARGS__))
-
- if (bkey_extent_is_data(k.k))
- out += extent_print_ptrs(c, buf, size, bkey_s_c_to_extent(k));
-
- invalid = bch2_btree_ptr_invalid(c, k);
- if (invalid)
- p(" invalid: %s", invalid);
-#undef p
-}
-
-struct extent_pick_ptr
-bch2_btree_pick_ptr(struct bch_fs *c, const struct btree *b,
- struct bch_devs_mask *avoid)
-{
- struct extent_pick_ptr pick = { .ca = NULL };
-
- extent_pick_read_device(c, bkey_i_to_s_c_extent(&b->key),
- avoid, &pick);
-
- return pick;
-}
-
-const struct bkey_ops bch2_bkey_btree_ops = {
- .key_invalid = bch2_btree_ptr_invalid,
- .key_debugcheck = btree_ptr_debugcheck,
- .val_to_text = bch2_btree_ptr_to_text,
- .swab = bch2_ptr_swab,
-};
-
-/* Extents */
-
-static bool __bch2_cut_front(struct bpos where, struct bkey_s k)
-{
- u64 len = 0;
-
- if (bkey_cmp(where, bkey_start_pos(k.k)) <= 0)
- return false;
-
- EBUG_ON(bkey_cmp(where, k.k->p) > 0);
-
- len = k.k->p.offset - where.offset;
-
- BUG_ON(len > k.k->size);
-
- /*
- * Don't readjust offset if the key size is now 0, because that could
- * cause offset to point to the next bucket:
- */
- if (!len)
- __set_bkey_deleted(k.k);
- else if (bkey_extent_is_data(k.k)) {
- struct bkey_s_extent e = bkey_s_to_extent(k);
- union bch_extent_entry *entry;
- bool seen_crc = false;
-
- extent_for_each_entry(e, entry) {
- switch (extent_entry_type(entry)) {
- case BCH_EXTENT_ENTRY_ptr:
- if (!seen_crc)
- entry->ptr.offset += e.k->size - len;
- break;
- case BCH_EXTENT_ENTRY_crc32:
- entry->crc32.offset += e.k->size - len;
- break;
- case BCH_EXTENT_ENTRY_crc64:
- entry->crc64.offset += e.k->size - len;
- break;
- case BCH_EXTENT_ENTRY_crc128:
- entry->crc128.offset += e.k->size - len;
- break;
- }
-
- if (extent_entry_is_crc(entry))
- seen_crc = true;
- }
- }
-
- k.k->size = len;
-
- return true;
-}
-
-bool bch2_cut_front(struct bpos where, struct bkey_i *k)
-{
- return __bch2_cut_front(where, bkey_i_to_s(k));
-}
-
-bool bch2_cut_back(struct bpos where, struct bkey *k)
-{
- u64 len = 0;
-
- if (bkey_cmp(where, k->p) >= 0)
- return false;
-
- EBUG_ON(bkey_cmp(where, bkey_start_pos(k)) < 0);
-
- len = where.offset - bkey_start_offset(k);
-
- BUG_ON(len > k->size);
-
- k->p = where;
- k->size = len;
-
- if (!len)
- __set_bkey_deleted(k);
-
- return true;
-}
-
-/**
- * bch_key_resize - adjust size of @k
- *
- * bkey_start_offset(k) will be preserved, modifies where the extent ends
- */
-void bch2_key_resize(struct bkey *k,
- unsigned new_size)
-{
- k->p.offset -= k->size;
- k->p.offset += new_size;
- k->size = new_size;
-}
-
-/*
- * In extent_sort_fix_overlapping(), insert_fixup_extent(),
- * extent_merge_inline() - we're modifying keys in place that are packed. To do
- * that we have to unpack the key, modify the unpacked key - then this
- * copies/repacks the unpacked to the original as necessary.
- */
-static bool __extent_save(struct btree *b, struct btree_node_iter *iter,
- struct bkey_packed *dst, struct bkey *src)
-{
- struct bkey_format *f = &b->format;
- struct bkey_i *dst_unpacked;
- bool ret;
-
- if ((dst_unpacked = packed_to_bkey(dst))) {
- dst_unpacked->k = *src;
- ret = true;
- } else {
- ret = bch2_bkey_pack_key(dst, src, f);
- }
-
- if (ret && iter)
- bch2_verify_key_order(b, iter, dst);
-
- return ret;
-}
-
-static void extent_save(struct btree *b, struct btree_node_iter *iter,
- struct bkey_packed *dst, struct bkey *src)
-{
- BUG_ON(!__extent_save(b, iter, dst, src));
-}
-
-/*
- * 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.
- */
-#define extent_sort_cmp(h, l, r) \
-({ \
- struct bkey _ul = bkey_unpack_key(b, \
- __btree_node_offset_to_key(b, (l).k)); \
- struct bkey _ur = bkey_unpack_key(b, \
- __btree_node_offset_to_key(b, (r).k)); \
- \
- bkey_cmp(bkey_start_pos(&_ul), \
- bkey_start_pos(&_ur)) ?: (r).k - (l).k; \
-})
-
-static inline void extent_sort_sift(struct btree_node_iter *iter,
- struct btree *b, size_t i)
-{
- heap_sift_down(iter, i, extent_sort_cmp);
-}
-
-static inline void extent_sort_next(struct btree_node_iter *iter,
- struct btree *b,
- struct btree_node_iter_set *i)
-{
- sort_key_next(iter, b, i);
- heap_sift_down(iter, i - iter->data, extent_sort_cmp);
-}
-
-static void extent_sort_append(struct bch_fs *c,
- struct btree *b,
- struct btree_nr_keys *nr,
- struct bkey_packed *start,
- struct bkey_packed **prev,
- struct bkey_packed *k)
-{
- struct bkey_format *f = &b->format;
- BKEY_PADDED(k) tmp;
-
- if (bkey_whiteout(k))
- return;
-
- bch2_bkey_unpack(b, &tmp.k, k);
-
- if (*prev &&
- bch2_extent_merge(c, b, (void *) *prev, &tmp.k))
- return;
-
- if (*prev) {
- bch2_bkey_pack(*prev, (void *) *prev, f);
-
- btree_keys_account_key_add(nr, 0, *prev);
- *prev = bkey_next(*prev);
- } else {
- *prev = start;
- }
-
- bkey_copy(*prev, &tmp.k);
-}
-
-struct btree_nr_keys bch2_extent_sort_fix_overlapping(struct bch_fs *c,
- struct bset *dst,
- struct btree *b,
- struct btree_node_iter *iter)
-{
- struct bkey_format *f = &b->format;
- struct btree_node_iter_set *_l = iter->data, *_r;
- struct bkey_packed *prev = NULL, *out, *lk, *rk;
- struct bkey l_unpacked, r_unpacked;
- struct bkey_s l, r;
- struct btree_nr_keys nr;
-
- memset(&nr, 0, sizeof(nr));
-
- heap_resort(iter, extent_sort_cmp);
-
- while (!bch2_btree_node_iter_end(iter)) {
- lk = __btree_node_offset_to_key(b, _l->k);
-
- if (iter->used == 1) {
- extent_sort_append(c, b, &nr, dst->start, &prev, lk);
- extent_sort_next(iter, b, _l);
- continue;
- }
-
- _r = iter->data + 1;
- if (iter->used > 2 &&
- extent_sort_cmp(iter, _r[0], _r[1]) >= 0)
- _r++;
-
- rk = __btree_node_offset_to_key(b, _r->k);
-
- l = __bkey_disassemble(b, lk, &l_unpacked);
- r = __bkey_disassemble(b, rk, &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, b, &nr, dst->start, &prev, lk);
- extent_sort_next(iter, b, _l);
- continue;
- }
-
- /* Skip 0 size keys */
- if (!r.k->size) {
- extent_sort_next(iter, b, _r);
- 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) {
- sort_key_next(iter, b, _r);
- } else {
- __bch2_cut_front(l.k->p, r);
- extent_save(b, NULL, rk, r.k);
- }
-
- extent_sort_sift(iter, b, _r - iter->data);
- } else if (bkey_cmp(l.k->p, r.k->p) > 0) {
- BKEY_PADDED(k) tmp;
-
- /*
- * r wins, but it overlaps in the middle of l - split l:
- */
- bkey_reassemble(&tmp.k, l.s_c);
- bch2_cut_back(bkey_start_pos(r.k), &tmp.k.k);
-
- __bch2_cut_front(r.k->p, l);
- extent_save(b, NULL, lk, l.k);
-
- extent_sort_sift(iter, b, 0);
-
- extent_sort_append(c, b, &nr, dst->start, &prev,
- bkey_to_packed(&tmp.k));
- } else {
- bch2_cut_back(bkey_start_pos(r.k), l.k);
- extent_save(b, NULL, lk, l.k);
- }
- }
-
- if (prev) {
- bch2_bkey_pack(prev, (void *) prev, f);
- btree_keys_account_key_add(&nr, 0, prev);
- out = bkey_next(prev);
- } else {
- out = dst->start;
- }
-
- dst->u64s = cpu_to_le16((u64 *) out - dst->_data);
- return nr;
-}
-
-struct extent_insert_state {
- struct btree_insert *trans;
- struct btree_insert_entry *insert;
- struct bpos committed;
- struct bch_fs_usage stats;
-
- /* for deleting: */
- struct bkey_i whiteout;
- bool do_journal;
- bool deleting;
-};
-
-static void bch2_add_sectors(struct extent_insert_state *s,
- struct bkey_s_c k, u64 offset, s64 sectors)
-{
- struct bch_fs *c = s->trans->c;
- struct btree *b = s->insert->iter->l[0].b;
-
- EBUG_ON(bkey_cmp(bkey_start_pos(k.k), b->data->min_key) < 0);
-
- if (!sectors)
- return;
-
- bch2_mark_key(c, k, sectors, false, gc_pos_btree_node(b),
- &s->stats, s->trans->journal_res.seq, 0);
-}
-
-static void bch2_subtract_sectors(struct extent_insert_state *s,
- struct bkey_s_c k, u64 offset, s64 sectors)
-{
- bch2_add_sectors(s, k, offset, -sectors);
-}
-
-/* These wrappers subtract exactly the sectors that we're removing from @k */
-static void bch2_cut_subtract_back(struct extent_insert_state *s,
- struct bpos where, struct bkey_s k)
-{
- bch2_subtract_sectors(s, k.s_c, where.offset,
- k.k->p.offset - where.offset);
- bch2_cut_back(where, k.k);
-}
-
-static void bch2_cut_subtract_front(struct extent_insert_state *s,
- struct bpos where, struct bkey_s k)
-{
- bch2_subtract_sectors(s, k.s_c, bkey_start_offset(k.k),
- where.offset - bkey_start_offset(k.k));
- __bch2_cut_front(where, k);
-}
-
-static void bch2_drop_subtract(struct extent_insert_state *s, struct bkey_s k)
-{
- if (k.k->size)
- bch2_subtract_sectors(s, k.s_c,
- bkey_start_offset(k.k), k.k->size);
- k.k->size = 0;
- __set_bkey_deleted(k.k);
-}
-
-static bool bch2_extent_merge_inline(struct bch_fs *,
- struct btree_iter *,
- struct bkey_packed *,
- struct bkey_packed *,
- bool);
-
-#define MAX_LOCK_HOLD_TIME (5 * NSEC_PER_MSEC)
-
-static enum btree_insert_ret
-extent_insert_should_stop(struct extent_insert_state *s)
-{
- struct btree *b = s->insert->iter->l[0].b;
-
- /*
- * Check if we have sufficient space in both the btree node and the
- * journal reservation:
- *
- * Each insert checks for room in the journal entry, but we check for
- * room in the btree node up-front. In the worst case, bkey_cmpxchg()
- * will insert two keys, and one iteration of this room will insert one
- * key, so we need room for three keys.
- */
- if (!bch2_btree_node_insert_fits(s->trans->c, b, s->insert->k->k.u64s))
- return BTREE_INSERT_BTREE_NODE_FULL;
- else if (!journal_res_insert_fits(s->trans, s->insert))
- return BTREE_INSERT_JOURNAL_RES_FULL; /* XXX worth tracing */
- else
- return BTREE_INSERT_OK;
-}
-
-static void extent_bset_insert(struct bch_fs *c, struct btree_iter *iter,
- struct bkey_i *insert)
-{
- struct btree_iter_level *l = &iter->l[0];
- struct bset_tree *t = bset_tree_last(l->b);
- struct bkey_packed *where =
- bch2_btree_node_iter_bset_pos(&l->iter, l->b, t);
- struct bkey_packed *prev = bch2_bkey_prev(l->b, t, where);
- struct bkey_packed *next_live_key = where;
- unsigned clobber_u64s;
-
- if (prev)
- where = bkey_next(prev);
-
- while (next_live_key != btree_bkey_last(l->b, t) &&
- bkey_deleted(next_live_key))
- next_live_key = bkey_next(next_live_key);
-
- /*
- * Everything between where and next_live_key is now deleted keys, and
- * is overwritten:
- */
- clobber_u64s = (u64 *) next_live_key - (u64 *) where;
-
- if (prev &&
- bch2_extent_merge_inline(c, iter, prev, bkey_to_packed(insert), true))
- goto drop_deleted_keys;
-
- if (next_live_key != btree_bkey_last(l->b, t) &&
- bch2_extent_merge_inline(c, iter, bkey_to_packed(insert),
- next_live_key, false))
- goto drop_deleted_keys;
-
- bch2_bset_insert(l->b, &l->iter, where, insert, clobber_u64s);
- bch2_btree_node_iter_fix(iter, l->b, &l->iter, t, where,
- clobber_u64s, where->u64s);
- return;
-drop_deleted_keys:
- bch2_bset_delete(l->b, where, clobber_u64s);
- bch2_btree_node_iter_fix(iter, l->b, &l->iter, t,
- where, clobber_u64s, 0);
-}
-
-static void extent_insert_committed(struct extent_insert_state *s)
-{
- struct bch_fs *c = s->trans->c;
- struct btree_iter *iter = s->insert->iter;
- struct bkey_i *insert = !s->deleting
- ? s->insert->k
- : &s->whiteout;
- BKEY_PADDED(k) split;
-
- EBUG_ON(bkey_cmp(insert->k.p, s->committed) < 0);
- EBUG_ON(bkey_cmp(s->committed, bkey_start_pos(&insert->k)) < 0);
-
- if (!bkey_cmp(s->committed, bkey_start_pos(&insert->k)))
- return;
-
- if (s->deleting && !s->do_journal) {
- bch2_cut_front(s->committed, insert);
- goto done;
- }
-
- EBUG_ON(bkey_deleted(&insert->k) || !insert->k.size);
-
- bkey_copy(&split.k, insert);
-
- if (!(s->trans->flags & BTREE_INSERT_JOURNAL_REPLAY) &&
- bkey_cmp(s->committed, insert->k.p) &&
- bch2_extent_is_compressed(bkey_i_to_s_c(insert))) {
- /* XXX: possibly need to increase our reservation? */
- bch2_cut_subtract_back(s, s->committed,
- bkey_i_to_s(&split.k));
- bch2_cut_front(s->committed, insert);
- bch2_add_sectors(s, bkey_i_to_s_c(insert),
- bkey_start_offset(&insert->k),
- insert->k.size);
- } else {
- bch2_cut_back(s->committed, &split.k.k);
- bch2_cut_front(s->committed, insert);
- }
-
- if (debug_check_bkeys(c))
- bch2_bkey_debugcheck(c, iter->l[0].b, bkey_i_to_s_c(&split.k));
-
- bch2_btree_journal_key(s->trans, iter, &split.k);
-
- if (!s->deleting)
- extent_bset_insert(c, iter, &split.k);
-done:
- bch2_btree_iter_set_pos_same_leaf(iter, s->committed);
-
- insert->k.needs_whiteout = false;
- s->do_journal = false;
- s->trans->did_work = true;
-}
-
-static enum btree_insert_ret
-__extent_insert_advance_pos(struct extent_insert_state *s,
- struct bpos next_pos,
- struct bkey_s_c k)
-{
- struct extent_insert_hook *hook = s->trans->hook;
- enum btree_insert_ret ret;
-
- if (hook)
- ret = hook->fn(hook, s->committed, next_pos, k, s->insert->k);
- else
- ret = BTREE_INSERT_OK;
-
- EBUG_ON(bkey_deleted(&s->insert->k->k) || !s->insert->k->k.size);
-
- if (ret == BTREE_INSERT_OK)
- s->committed = next_pos;
-
- return ret;
-}
-
-/*
- * Update iter->pos, marking how much of @insert we've processed, and call hook
- * fn:
- */
-static enum btree_insert_ret
-extent_insert_advance_pos(struct extent_insert_state *s, struct bkey_s_c k)
-{
- struct btree *b = s->insert->iter->l[0].b;
- struct bpos next_pos = bpos_min(s->insert->k->k.p,
- k.k ? k.k->p : b->key.k.p);
- enum btree_insert_ret ret;
-
- if (race_fault())
- return BTREE_INSERT_NEED_TRAVERSE;
-
- /* hole? */
- if (k.k && bkey_cmp(s->committed, bkey_start_pos(k.k)) < 0) {
- ret = __extent_insert_advance_pos(s, bkey_start_pos(k.k),
- bkey_s_c_null);
- if (ret != BTREE_INSERT_OK)
- return ret;
- }
-
- /* avoid redundant calls to hook fn: */
- if (!bkey_cmp(s->committed, next_pos))
- return BTREE_INSERT_OK;
-
- return __extent_insert_advance_pos(s, next_pos, k);
-}
-
-static enum btree_insert_ret
-extent_insert_check_split_compressed(struct extent_insert_state *s,
- struct bkey_s_c k,
- enum bch_extent_overlap overlap)
-{
- struct bch_fs *c = s->trans->c;
- unsigned sectors;
-
- if (overlap == BCH_EXTENT_OVERLAP_MIDDLE &&
- (sectors = bch2_extent_is_compressed(k))) {
- int flags = BCH_DISK_RESERVATION_BTREE_LOCKS_HELD;
-
- if (s->trans->flags & BTREE_INSERT_NOFAIL)
- flags |= BCH_DISK_RESERVATION_NOFAIL;
-
- switch (bch2_disk_reservation_add(c,
- s->trans->disk_res,
- sectors * bch2_extent_nr_dirty_ptrs(k),
- flags)) {
- case 0:
- break;
- case -ENOSPC:
- return BTREE_INSERT_ENOSPC;
- case -EINTR:
- return BTREE_INSERT_NEED_GC_LOCK;
- default:
- BUG();
- }
- }
-
- return BTREE_INSERT_OK;
-}
-
-static enum btree_insert_ret
-extent_squash(struct extent_insert_state *s, struct bkey_i *insert,
- struct bset_tree *t, struct bkey_packed *_k, struct bkey_s k,
- enum bch_extent_overlap overlap)
-{
- struct bch_fs *c = s->trans->c;
- struct btree_iter *iter = s->insert->iter;
- struct btree_iter_level *l = &iter->l[0];
- struct btree *b = l->b;
- struct btree_node_iter *node_iter = &l->iter;
- enum btree_insert_ret ret;
-
- switch (overlap) {
- case BCH_EXTENT_OVERLAP_FRONT:
- /* insert overlaps with start of k: */
- bch2_cut_subtract_front(s, insert->k.p, k);
- BUG_ON(bkey_deleted(k.k));
- extent_save(b, node_iter, _k, k.k);
- break;
-
- case BCH_EXTENT_OVERLAP_BACK:
- /* insert overlaps with end of k: */
- bch2_cut_subtract_back(s, bkey_start_pos(&insert->k), k);
- BUG_ON(bkey_deleted(k.k));
- extent_save(b, node_iter, _k, k.k);
-
- /*
- * As the auxiliary tree is indexed by the end of the
- * key and we've just changed the end, update the
- * auxiliary tree.
- */
- bch2_bset_fix_invalidated_key(b, t, _k);
- bch2_btree_node_iter_fix(iter, b, node_iter, t,
- _k, _k->u64s, _k->u64s);
- break;
-
- case BCH_EXTENT_OVERLAP_ALL: {
- struct bpos orig_pos = k.k->p;
-
- /* The insert key completely covers k, invalidate k */
- if (!bkey_whiteout(k.k))
- btree_keys_account_key_drop(&b->nr,
- t - b->set, _k);
-
- bch2_drop_subtract(s, k);
- k.k->p = bkey_start_pos(&insert->k);
- if (!__extent_save(b, node_iter, _k, k.k)) {
- /*
- * Couldn't repack: we aren't necessarily able
- * to repack if the new key is outside the range
- * of the old extent, so we have to split
- * @insert:
- */
- k.k->p = orig_pos;
- extent_save(b, node_iter, _k, k.k);
-
- ret = extent_insert_advance_pos(s, k.s_c);
- if (ret != BTREE_INSERT_OK)
- return ret;
-
- extent_insert_committed(s);
- /*
- * We split and inserted upto at k.k->p - that
- * has to coincide with iter->pos, so that we
- * don't have anything more we have to insert
- * until we recheck our journal reservation:
- */
- EBUG_ON(bkey_cmp(s->committed, k.k->p));
- } else {
- bch2_bset_fix_invalidated_key(b, t, _k);
- bch2_btree_node_iter_fix(iter, b, node_iter, t,
- _k, _k->u64s, _k->u64s);
- }
-
- break;
- }
- case BCH_EXTENT_OVERLAP_MIDDLE: {
- BKEY_PADDED(k) split;
- /*
- * The insert key falls 'in the middle' of k
- * The insert key splits k in 3:
- * - start only in k, preserve
- * - middle common section, invalidate in k
- * - end only in k, preserve
- *
- * We update the old key to preserve the start,
- * insert will be the new common section,
- * we manually insert the end that we are preserving.
- *
- * modify k _before_ doing the insert (which will move
- * what k points to)
- */
- bkey_reassemble(&split.k, k.s_c);
- split.k.k.needs_whiteout |= bset_written(b, bset(b, t));
-
- bch2_cut_back(bkey_start_pos(&insert->k), &split.k.k);
- BUG_ON(bkey_deleted(&split.k.k));
-
- bch2_cut_subtract_front(s, insert->k.p, k);
- BUG_ON(bkey_deleted(k.k));
- extent_save(b, node_iter, _k, k.k);
-
- bch2_add_sectors(s, bkey_i_to_s_c(&split.k),
- bkey_start_offset(&split.k.k),
- split.k.k.size);
- extent_bset_insert(c, iter, &split.k);
- break;
- }
- }
-
- return BTREE_INSERT_OK;
-}
-
-static enum btree_insert_ret
-bch2_delete_fixup_extent(struct extent_insert_state *s)
-{
- struct bch_fs *c = s->trans->c;
- struct btree_iter *iter = s->insert->iter;
- struct btree_iter_level *l = &iter->l[0];
- struct btree *b = l->b;
- struct btree_node_iter *node_iter = &l->iter;
- struct bkey_packed *_k;
- struct bkey unpacked;
- struct bkey_i *insert = s->insert->k;
- enum btree_insert_ret ret = BTREE_INSERT_OK;
-
- EBUG_ON(bkey_cmp(iter->pos, bkey_start_pos(&insert->k)));
-
- s->whiteout = *insert;
- s->do_journal = false;
-
- while (bkey_cmp(s->committed, insert->k.p) < 0 &&
- (ret = extent_insert_should_stop(s)) == BTREE_INSERT_OK &&
- (_k = bch2_btree_node_iter_peek_all(node_iter, b))) {
- struct bset_tree *t = bch2_bkey_to_bset(b, _k);
- struct bkey_s k = __bkey_disassemble(b, _k, &unpacked);
- enum bch_extent_overlap overlap;
-
- EBUG_ON(bkey_cmp(iter->pos, bkey_start_pos(&insert->k)));
- EBUG_ON(bkey_cmp(iter->pos, k.k->p) >= 0);
-
- if (bkey_cmp(bkey_start_pos(k.k), insert->k.p) >= 0)
- break;
-
- if (bkey_whiteout(k.k)) {
- s->committed = bpos_min(insert->k.p, k.k->p);
- goto next;
- }
-
- overlap = bch2_extent_overlap(&insert->k, k.k);
-
- ret = extent_insert_check_split_compressed(s, k.s_c, overlap);
- if (ret != BTREE_INSERT_OK)
- goto stop;
-
- ret = extent_insert_advance_pos(s, k.s_c);
- if (ret)
- goto stop;
-
- s->do_journal = true;
-
- if (overlap == BCH_EXTENT_OVERLAP_ALL) {
- btree_keys_account_key_drop(&b->nr,
- t - b->set, _k);
- bch2_subtract_sectors(s, k.s_c,
- bkey_start_offset(k.k), k.k->size);
- _k->type = KEY_TYPE_DISCARD;
- reserve_whiteout(b, t, _k);
- } else if (k.k->needs_whiteout ||
- bset_written(b, bset(b, t))) {
- struct bkey_i discard = *insert;
-
- switch (overlap) {
- case BCH_EXTENT_OVERLAP_FRONT:
- bch2_cut_front(bkey_start_pos(k.k), &discard);
- break;
- case BCH_EXTENT_OVERLAP_BACK:
- bch2_cut_back(k.k->p, &discard.k);
- break;
- default:
- break;
- }
-
- discard.k.needs_whiteout = true;
-
- ret = extent_squash(s, insert, t, _k, k, overlap);
- BUG_ON(ret != BTREE_INSERT_OK);
-
- extent_bset_insert(c, iter, &discard);
- } else {
- ret = extent_squash(s, insert, t, _k, k, overlap);
- BUG_ON(ret != BTREE_INSERT_OK);
- }
-next:
- bch2_cut_front(s->committed, insert);
- bch2_btree_iter_set_pos_same_leaf(iter, s->committed);
- }
-
- if (ret == BTREE_INSERT_OK &&
- bkey_cmp(s->committed, insert->k.p) < 0)
- ret = extent_insert_advance_pos(s, bkey_s_c_null);
-stop:
- extent_insert_committed(s);
-
- bch2_fs_usage_apply(c, &s->stats, s->trans->disk_res,
- gc_pos_btree_node(b));
-
- EBUG_ON(bkey_cmp(iter->pos, s->committed));
- EBUG_ON((bkey_cmp(iter->pos, b->key.k.p) == 0) !=
- !!(iter->flags & BTREE_ITER_AT_END_OF_LEAF));
-
- bch2_cut_front(iter->pos, insert);
-
- if (insert->k.size && (iter->flags & BTREE_ITER_AT_END_OF_LEAF))
- ret = BTREE_INSERT_NEED_TRAVERSE;
-
- EBUG_ON(insert->k.size && ret == BTREE_INSERT_OK);
-
- return ret;
-}
-
-/**
- * bch_extent_insert_fixup - insert a new extent and deal with overlaps
- *
- * this may result in not actually doing the insert, or inserting some subset
- * of the insert key. For cmpxchg operations this is where that logic lives.
- *
- * All subsets of @insert that need to be inserted are inserted using
- * bch2_btree_insert_and_journal(). If @b or @res fills up, this function
- * returns false, setting @iter->pos for the prefix of @insert that actually got
- * inserted.
- *
- * BSET INVARIANTS: this function is responsible for maintaining all the
- * invariants for bsets of extents in memory. things get really hairy with 0
- * size extents
- *
- * within one bset:
- *
- * bkey_start_pos(bkey_next(k)) >= k
- * or bkey_start_offset(bkey_next(k)) >= k->offset
- *
- * i.e. strict ordering, no overlapping extents.
- *
- * multiple bsets (i.e. full btree node):
- *
- * ∀ k, j
- * k.size != 0 ∧ j.size != 0 →
- * ¬ (k > bkey_start_pos(j) ∧ k < j)
- *
- * i.e. no two overlapping keys _of nonzero size_
- *
- * We can't realistically maintain this invariant for zero size keys because of
- * the key merging done in bch2_btree_insert_key() - for two mergeable keys k, j
- * there may be another 0 size key between them in another bset, and it will
- * thus overlap with the merged key.
- *
- * In addition, the end of iter->pos indicates how much has been processed.
- * If the end of iter->pos is not the same as the end of insert, then
- * key insertion needs to continue/be retried.
- */
-enum btree_insert_ret
-bch2_insert_fixup_extent(struct btree_insert *trans,
- struct btree_insert_entry *insert)
-{
- struct bch_fs *c = trans->c;
- struct btree_iter *iter = insert->iter;
- struct btree_iter_level *l = &iter->l[0];
- struct btree *b = l->b;
- struct btree_node_iter *node_iter = &l->iter;
- struct bkey_packed *_k;
- struct bkey unpacked;
- enum btree_insert_ret ret = BTREE_INSERT_OK;
-
- struct extent_insert_state s = {
- .trans = trans,
- .insert = insert,
- .committed = insert->iter->pos,
- .deleting = bkey_whiteout(&insert->k->k),
- };
-
- EBUG_ON(iter->level);
- EBUG_ON(bkey_deleted(&insert->k->k) || !insert->k->k.size);
-
- if (s.deleting)
- return bch2_delete_fixup_extent(&s);
-
- /*
- * As we process overlapping extents, we advance @iter->pos both to
- * signal to our caller (btree_insert_key()) how much of @insert->k has
- * been inserted, and also to keep @iter->pos consistent with
- * @insert->k and the node iterator that we're advancing:
- */
- EBUG_ON(bkey_cmp(iter->pos, bkey_start_pos(&insert->k->k)));
-
- if (!(trans->flags & BTREE_INSERT_JOURNAL_REPLAY))
- bch2_add_sectors(&s, bkey_i_to_s_c(insert->k),
- bkey_start_offset(&insert->k->k),
- insert->k->k.size);
-
- while (bkey_cmp(s.committed, insert->k->k.p) < 0 &&
- (ret = extent_insert_should_stop(&s)) == BTREE_INSERT_OK &&
- (_k = bch2_btree_node_iter_peek_all(node_iter, b))) {
- struct bset_tree *t = bch2_bkey_to_bset(b, _k);
- struct bkey_s k = __bkey_disassemble(b, _k, &unpacked);
- enum bch_extent_overlap overlap;
-
- EBUG_ON(bkey_cmp(iter->pos, bkey_start_pos(&insert->k->k)));
- EBUG_ON(bkey_cmp(iter->pos, k.k->p) >= 0);
-
- if (bkey_cmp(bkey_start_pos(k.k), insert->k->k.p) >= 0)
- break;
-
- overlap = bch2_extent_overlap(&insert->k->k, k.k);
-
- ret = extent_insert_check_split_compressed(&s, k.s_c, overlap);
- if (ret != BTREE_INSERT_OK)
- goto stop;
-
- if (!k.k->size)
- goto squash;
-
- /*
- * Only call advance pos & call hook for nonzero size extents:
- */
- ret = extent_insert_advance_pos(&s, k.s_c);
- if (ret != BTREE_INSERT_OK)
- goto stop;
-
- if (k.k->size &&
- (k.k->needs_whiteout || bset_written(b, bset(b, t))))
- insert->k->k.needs_whiteout = true;
-
- if (overlap == BCH_EXTENT_OVERLAP_ALL &&
- bkey_whiteout(k.k) &&
- k.k->needs_whiteout) {
- unreserve_whiteout(b, t, _k);
- _k->needs_whiteout = false;
- }
-squash:
- ret = extent_squash(&s, insert->k, t, _k, k, overlap);
- if (ret != BTREE_INSERT_OK)
- goto stop;
- }
-
- if (ret == BTREE_INSERT_OK &&
- bkey_cmp(s.committed, insert->k->k.p) < 0)
- ret = extent_insert_advance_pos(&s, bkey_s_c_null);
-stop:
- extent_insert_committed(&s);
- /*
- * Subtract any remaining sectors from @insert, if we bailed out early
- * and didn't fully insert @insert:
- */
- if (insert->k->k.size &&
- !(trans->flags & BTREE_INSERT_JOURNAL_REPLAY))
- bch2_subtract_sectors(&s, bkey_i_to_s_c(insert->k),
- bkey_start_offset(&insert->k->k),
- insert->k->k.size);
-
- bch2_fs_usage_apply(c, &s.stats, trans->disk_res,
- gc_pos_btree_node(b));
-
- EBUG_ON(bkey_cmp(iter->pos, bkey_start_pos(&insert->k->k)));
- EBUG_ON(bkey_cmp(iter->pos, s.committed));
- EBUG_ON((bkey_cmp(iter->pos, b->key.k.p) == 0) !=
- !!(iter->flags & BTREE_ITER_AT_END_OF_LEAF));
-
- if (insert->k->k.size && (iter->flags & BTREE_ITER_AT_END_OF_LEAF))
- ret = BTREE_INSERT_NEED_TRAVERSE;
-
- EBUG_ON(insert->k->k.size && ret == BTREE_INSERT_OK);
-
- return ret;
-}
-
-static const char *bch2_extent_invalid(const struct bch_fs *c,
- struct bkey_s_c k)
-{
- if (bkey_val_u64s(k.k) > BKEY_EXTENT_VAL_U64s_MAX)
- return "value too big";
-
- if (!k.k->size)
- return "zero key size";
-
- switch (k.k->type) {
- case BCH_EXTENT:
- case BCH_EXTENT_CACHED: {
- struct bkey_s_c_extent e = bkey_s_c_to_extent(k);
- const union bch_extent_entry *entry;
- struct bch_extent_crc_unpacked crc;
- const struct bch_extent_ptr *ptr;
- unsigned size_ondisk = e.k->size;
- const char *reason;
- unsigned nonce = UINT_MAX;
-
- extent_for_each_entry(e, entry) {
- if (__extent_entry_type(entry) >= BCH_EXTENT_ENTRY_MAX)
- return "invalid extent entry type";
-
- if (extent_entry_is_crc(entry)) {
- crc = bch2_extent_crc_unpack(e.k, entry_to_crc(entry));
-
- if (crc.offset + e.k->size >
- crc.uncompressed_size)
- return "checksum offset + key size > uncompressed size";
-
- size_ondisk = crc.compressed_size;
-
- if (!bch2_checksum_type_valid(c, crc.csum_type))
- return "invalid checksum type";
-
- if (crc.compression_type >= BCH_COMPRESSION_NR)
- return "invalid compression type";
-
- if (bch2_csum_type_is_encryption(crc.csum_type)) {
- if (nonce == UINT_MAX)
- nonce = crc.offset + crc.nonce;
- else if (nonce != crc.offset + crc.nonce)
- return "incorrect nonce";
- }
- } else {
- ptr = entry_to_ptr(entry);
-
- reason = extent_ptr_invalid(c, e, &entry->ptr,
- size_ondisk, false);
- if (reason)
- return reason;
- }
- }
-
- return NULL;
- }
-
- case BCH_RESERVATION: {
- struct bkey_s_c_reservation r = bkey_s_c_to_reservation(k);
-
- if (bkey_val_bytes(k.k) != sizeof(struct bch_reservation))
- return "incorrect value size";
-
- if (!r.v->nr_replicas || r.v->nr_replicas > BCH_REPLICAS_MAX)
- return "invalid nr_replicas";
-
- return NULL;
- }
-
- default:
- return "invalid value type";
- }
-}
-
-static void bch2_extent_debugcheck_extent(struct bch_fs *c, struct btree *b,
- struct bkey_s_c_extent e)
-{
- const struct bch_extent_ptr *ptr;
- struct bch_dev *ca;
- struct bucket_mark mark;
- unsigned seq, stale;
- char buf[160];
- bool bad;
- unsigned ptrs_per_tier[BCH_TIER_MAX];
- unsigned replicas = 0;