174 lines · c
1// SPDX-License-Identifier: GPL-2.02#include "bcachefs.h"3#include "btree_update.h"4#include "btree_update_interior.h"5#include "buckets.h"6#include "debug.h"7#include "extents.h"8#include "extent_update.h"9 10/*11 * This counts the number of iterators to the alloc & ec btrees we'll need12 * inserting/removing this extent:13 */14static unsigned bch2_bkey_nr_alloc_ptrs(struct bkey_s_c k)15{16 struct bkey_ptrs_c ptrs = bch2_bkey_ptrs_c(k);17 const union bch_extent_entry *entry;18 unsigned ret = 0, lru = 0;19 20 bkey_extent_entry_for_each(ptrs, entry) {21 switch (__extent_entry_type(entry)) {22 case BCH_EXTENT_ENTRY_ptr:23 /* Might also be updating LRU btree */24 if (entry->ptr.cached)25 lru++;26 27 fallthrough;28 case BCH_EXTENT_ENTRY_stripe_ptr:29 ret++;30 }31 }32 33 /*34 * Updating keys in the alloc btree may also update keys in the35 * freespace or discard btrees:36 */37 return lru + ret * 2;38}39 40static int count_iters_for_insert(struct btree_trans *trans,41 struct bkey_s_c k,42 unsigned offset,43 struct bpos *end,44 unsigned *nr_iters,45 unsigned max_iters)46{47 int ret = 0, ret2 = 0;48 49 if (*nr_iters >= max_iters) {50 *end = bpos_min(*end, k.k->p);51 ret = 1;52 }53 54 switch (k.k->type) {55 case KEY_TYPE_extent:56 case KEY_TYPE_reflink_v:57 *nr_iters += bch2_bkey_nr_alloc_ptrs(k);58 59 if (*nr_iters >= max_iters) {60 *end = bpos_min(*end, k.k->p);61 ret = 1;62 }63 64 break;65 case KEY_TYPE_reflink_p: {66 struct bkey_s_c_reflink_p p = bkey_s_c_to_reflink_p(k);67 u64 idx = le64_to_cpu(p.v->idx);68 unsigned sectors = bpos_min(*end, p.k->p).offset -69 bkey_start_offset(p.k);70 struct btree_iter iter;71 struct bkey_s_c r_k;72 73 for_each_btree_key_norestart(trans, iter,74 BTREE_ID_reflink, POS(0, idx + offset),75 BTREE_ITER_slots, r_k, ret2) {76 if (bkey_ge(bkey_start_pos(r_k.k), POS(0, idx + sectors)))77 break;78 79 /* extent_update_to_keys(), for the reflink_v update */80 *nr_iters += 1;81 82 *nr_iters += 1 + bch2_bkey_nr_alloc_ptrs(r_k);83 84 if (*nr_iters >= max_iters) {85 struct bpos pos = bkey_start_pos(k.k);86 pos.offset += min_t(u64, k.k->size,87 r_k.k->p.offset - idx);88 89 *end = bpos_min(*end, pos);90 ret = 1;91 break;92 }93 }94 bch2_trans_iter_exit(trans, &iter);95 96 break;97 }98 }99 100 return ret2 ?: ret;101}102 103#define EXTENT_ITERS_MAX (BTREE_ITER_INITIAL / 3)104 105int bch2_extent_atomic_end(struct btree_trans *trans,106 struct btree_iter *iter,107 struct bkey_i *insert,108 struct bpos *end)109{110 struct btree_iter copy;111 struct bkey_s_c k;112 unsigned nr_iters = 0;113 int ret;114 115 ret = bch2_btree_iter_traverse(iter);116 if (ret)117 return ret;118 119 *end = insert->k.p;120 121 /* extent_update_to_keys(): */122 nr_iters += 1;123 124 ret = count_iters_for_insert(trans, bkey_i_to_s_c(insert), 0, end,125 &nr_iters, EXTENT_ITERS_MAX / 2);126 if (ret < 0)127 return ret;128 129 bch2_trans_copy_iter(©, iter);130 131 for_each_btree_key_upto_continue_norestart(copy, insert->k.p, 0, k, ret) {132 unsigned offset = 0;133 134 if (bkey_gt(bkey_start_pos(&insert->k), bkey_start_pos(k.k)))135 offset = bkey_start_offset(&insert->k) -136 bkey_start_offset(k.k);137 138 /* extent_handle_overwrites(): */139 switch (bch2_extent_overlap(&insert->k, k.k)) {140 case BCH_EXTENT_OVERLAP_ALL:141 case BCH_EXTENT_OVERLAP_FRONT:142 nr_iters += 1;143 break;144 case BCH_EXTENT_OVERLAP_BACK:145 case BCH_EXTENT_OVERLAP_MIDDLE:146 nr_iters += 2;147 break;148 }149 150 ret = count_iters_for_insert(trans, k, offset, end,151 &nr_iters, EXTENT_ITERS_MAX);152 if (ret)153 break;154 }155 156 bch2_trans_iter_exit(trans, ©);157 return ret < 0 ? ret : 0;158}159 160int bch2_extent_trim_atomic(struct btree_trans *trans,161 struct btree_iter *iter,162 struct bkey_i *k)163{164 struct bpos end;165 int ret;166 167 ret = bch2_extent_atomic_end(trans, iter, k, &end);168 if (ret)169 return ret;170 171 bch2_cut_back(end, k);172 return 0;173}174