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