Loading...
1// SPDX-License-Identifier: GPL-2.0
2/*
3 * Copyright (C) 2023 Western Digital Corporation or its affiliates.
4 */
5
6#include <linux/btrfs_tree.h>
7#include "ctree.h"
8#include "fs.h"
9#include "accessors.h"
10#include "transaction.h"
11#include "disk-io.h"
12#include "raid-stripe-tree.h"
13#include "volumes.h"
14#include "print-tree.h"
15
16static int btrfs_partially_delete_raid_extent(struct btrfs_trans_handle *trans,
17 struct btrfs_path *path,
18 const struct btrfs_key *oldkey,
19 u64 newlen, u64 frontpad)
20{
21 struct btrfs_root *stripe_root = trans->fs_info->stripe_root;
22 struct btrfs_stripe_extent *extent, *newitem;
23 struct extent_buffer *leaf;
24 int slot;
25 size_t item_size;
26 struct btrfs_key newkey = {
27 .objectid = oldkey->objectid + frontpad,
28 .type = BTRFS_RAID_STRIPE_KEY,
29 .offset = newlen,
30 };
31 int ret;
32
33 ASSERT(oldkey->type == BTRFS_RAID_STRIPE_KEY);
34
35 leaf = path->nodes[0];
36 slot = path->slots[0];
37 item_size = btrfs_item_size(leaf, slot);
38
39 newitem = kzalloc(item_size, GFP_NOFS);
40 if (!newitem)
41 return -ENOMEM;
42
43 extent = btrfs_item_ptr(leaf, slot, struct btrfs_stripe_extent);
44
45 for (int i = 0; i < btrfs_num_raid_stripes(item_size); i++) {
46 struct btrfs_raid_stride *stride = &extent->strides[i];
47 u64 phys;
48
49 phys = btrfs_raid_stride_physical(leaf, stride) + frontpad;
50 btrfs_set_stack_raid_stride_physical(&newitem->strides[i], phys);
51 }
52
53 ret = btrfs_del_item(trans, stripe_root, path);
54 if (ret)
55 goto out;
56
57 btrfs_release_path(path);
58 ret = btrfs_insert_item(trans, stripe_root, &newkey, newitem, item_size);
59
60out:
61 kfree(newitem);
62 return ret;
63}
64
65int btrfs_delete_raid_extent(struct btrfs_trans_handle *trans, u64 start, u64 length)
66{
67 struct btrfs_fs_info *fs_info = trans->fs_info;
68 struct btrfs_root *stripe_root = fs_info->stripe_root;
69 struct btrfs_path *path;
70 struct btrfs_key key;
71 struct extent_buffer *leaf;
72 u64 found_start;
73 u64 found_end;
74 u64 end = start + length;
75 int slot;
76 int ret;
77
78 if (!stripe_root)
79 return 0;
80
81 path = btrfs_alloc_path();
82 if (!path)
83 return -ENOMEM;
84
85 while (1) {
86 key.objectid = start;
87 key.type = BTRFS_RAID_STRIPE_KEY;
88 key.offset = 0;
89
90 ret = btrfs_search_slot(trans, stripe_root, &key, path, -1, 1);
91 if (ret < 0)
92 break;
93
94 if (path->slots[0] == btrfs_header_nritems(path->nodes[0]))
95 path->slots[0]--;
96
97 leaf = path->nodes[0];
98 slot = path->slots[0];
99 btrfs_item_key_to_cpu(leaf, &key, slot);
100 found_start = key.objectid;
101 found_end = found_start + key.offset;
102 ret = 0;
103
104 if (key.type != BTRFS_RAID_STRIPE_KEY)
105 break;
106
107 /* That stripe ends before we start, we're done. */
108 if (found_end <= start)
109 break;
110
111 trace_btrfs_raid_extent_delete(fs_info, start, end,
112 found_start, found_end);
113
114 /*
115 * The stripe extent starts before the range we want to delete:
116 *
117 * |--- RAID Stripe Extent ---|
118 * |--- keep ---|--- drop ---|
119 *
120 * This means we have to duplicate the tree item, truncate the
121 * length to the new size and then re-insert the item.
122 */
123 if (found_start < start) {
124 u64 diff = start - found_start;
125
126 btrfs_partially_delete_raid_extent(trans, path, &key,
127 diff, 0);
128 break;
129 }
130
131 /*
132 * The stripe extent ends after the range we want to delete:
133 *
134 * |--- RAID Stripe Extent ---|
135 * |--- drop ---|--- keep ---|
136 *
137 * This means we have to duplicate the tree item, truncate the
138 * length to the new size and then re-insert the item.
139 */
140 if (found_end > end) {
141 u64 diff = found_end - end;
142
143 btrfs_partially_delete_raid_extent(trans, path, &key,
144 diff, diff);
145 break;
146 }
147
148 ret = btrfs_del_item(trans, stripe_root, path);
149 if (ret)
150 break;
151
152 start += key.offset;
153 length -= key.offset;
154 if (length == 0)
155 break;
156
157 btrfs_release_path(path);
158 }
159
160 btrfs_free_path(path);
161 return ret;
162}
163
164static int update_raid_extent_item(struct btrfs_trans_handle *trans,
165 struct btrfs_key *key,
166 struct btrfs_stripe_extent *stripe_extent,
167 const size_t item_size)
168{
169 struct btrfs_path *path;
170 struct extent_buffer *leaf;
171 int ret;
172 int slot;
173
174 path = btrfs_alloc_path();
175 if (!path)
176 return -ENOMEM;
177
178 ret = btrfs_search_slot(trans, trans->fs_info->stripe_root, key, path,
179 0, 1);
180 if (ret)
181 return (ret == 1 ? ret : -EINVAL);
182
183 leaf = path->nodes[0];
184 slot = path->slots[0];
185
186 write_extent_buffer(leaf, stripe_extent, btrfs_item_ptr_offset(leaf, slot),
187 item_size);
188 btrfs_mark_buffer_dirty(trans, leaf);
189 btrfs_free_path(path);
190
191 return ret;
192}
193
194EXPORT_FOR_TESTS
195int btrfs_insert_one_raid_extent(struct btrfs_trans_handle *trans,
196 struct btrfs_io_context *bioc)
197{
198 struct btrfs_fs_info *fs_info = trans->fs_info;
199 struct btrfs_key stripe_key;
200 struct btrfs_root *stripe_root = fs_info->stripe_root;
201 const int num_stripes = btrfs_bg_type_to_factor(bioc->map_type);
202 struct btrfs_stripe_extent *stripe_extent;
203 const size_t item_size = struct_size(stripe_extent, strides, num_stripes);
204 int ret;
205
206 stripe_extent = kzalloc(item_size, GFP_NOFS);
207 if (!stripe_extent) {
208 btrfs_abort_transaction(trans, -ENOMEM);
209 btrfs_end_transaction(trans);
210 return -ENOMEM;
211 }
212
213 trace_btrfs_insert_one_raid_extent(fs_info, bioc->logical, bioc->size,
214 num_stripes);
215 for (int i = 0; i < num_stripes; i++) {
216 u64 devid = bioc->stripes[i].dev->devid;
217 u64 physical = bioc->stripes[i].physical;
218 u64 length = bioc->stripes[i].length;
219 struct btrfs_raid_stride *raid_stride = &stripe_extent->strides[i];
220
221 if (length == 0)
222 length = bioc->size;
223
224 btrfs_set_stack_raid_stride_devid(raid_stride, devid);
225 btrfs_set_stack_raid_stride_physical(raid_stride, physical);
226 }
227
228 stripe_key.objectid = bioc->logical;
229 stripe_key.type = BTRFS_RAID_STRIPE_KEY;
230 stripe_key.offset = bioc->size;
231
232 ret = btrfs_insert_item(trans, stripe_root, &stripe_key, stripe_extent,
233 item_size);
234 if (ret == -EEXIST)
235 ret = update_raid_extent_item(trans, &stripe_key, stripe_extent,
236 item_size);
237 if (ret)
238 btrfs_abort_transaction(trans, ret);
239
240 kfree(stripe_extent);
241
242 return ret;
243}
244
245int btrfs_insert_raid_extent(struct btrfs_trans_handle *trans,
246 struct btrfs_ordered_extent *ordered_extent)
247{
248 struct btrfs_io_context *bioc;
249 int ret;
250
251 if (!btrfs_fs_incompat(trans->fs_info, RAID_STRIPE_TREE))
252 return 0;
253
254 list_for_each_entry(bioc, &ordered_extent->bioc_list, rst_ordered_entry) {
255 ret = btrfs_insert_one_raid_extent(trans, bioc);
256 if (ret)
257 return ret;
258 }
259
260 while (!list_empty(&ordered_extent->bioc_list)) {
261 bioc = list_first_entry(&ordered_extent->bioc_list,
262 typeof(*bioc), rst_ordered_entry);
263 list_del(&bioc->rst_ordered_entry);
264 btrfs_put_bioc(bioc);
265 }
266
267 return 0;
268}
269
270int btrfs_get_raid_extent_offset(struct btrfs_fs_info *fs_info,
271 u64 logical, u64 *length, u64 map_type,
272 u32 stripe_index, struct btrfs_io_stripe *stripe)
273{
274 struct btrfs_root *stripe_root = fs_info->stripe_root;
275 struct btrfs_stripe_extent *stripe_extent;
276 struct btrfs_key stripe_key;
277 struct btrfs_key found_key;
278 struct btrfs_path *path;
279 struct extent_buffer *leaf;
280 const u64 end = logical + *length;
281 int num_stripes;
282 u64 offset;
283 u64 found_logical;
284 u64 found_length;
285 u64 found_end;
286 int slot;
287 int ret;
288
289 stripe_key.objectid = logical;
290 stripe_key.type = BTRFS_RAID_STRIPE_KEY;
291 stripe_key.offset = 0;
292
293 path = btrfs_alloc_path();
294 if (!path)
295 return -ENOMEM;
296
297 if (stripe->rst_search_commit_root) {
298 path->skip_locking = 1;
299 path->search_commit_root = 1;
300 }
301
302 ret = btrfs_search_slot(NULL, stripe_root, &stripe_key, path, 0, 0);
303 if (ret < 0)
304 goto free_path;
305 if (ret) {
306 if (path->slots[0] != 0)
307 path->slots[0]--;
308 }
309
310 while (1) {
311 leaf = path->nodes[0];
312 slot = path->slots[0];
313
314 btrfs_item_key_to_cpu(leaf, &found_key, slot);
315 found_logical = found_key.objectid;
316 found_length = found_key.offset;
317 found_end = found_logical + found_length;
318
319 if (found_logical > end) {
320 ret = -ENODATA;
321 goto out;
322 }
323
324 if (in_range(logical, found_logical, found_length))
325 break;
326
327 ret = btrfs_next_item(stripe_root, path);
328 if (ret)
329 goto out;
330 }
331
332 offset = logical - found_logical;
333
334 /*
335 * If we have a logically contiguous, but physically non-continuous
336 * range, we need to split the bio. Record the length after which we
337 * must split the bio.
338 */
339 if (end > found_end)
340 *length -= end - found_end;
341
342 num_stripes = btrfs_num_raid_stripes(btrfs_item_size(leaf, slot));
343 stripe_extent = btrfs_item_ptr(leaf, slot, struct btrfs_stripe_extent);
344
345 for (int i = 0; i < num_stripes; i++) {
346 struct btrfs_raid_stride *stride = &stripe_extent->strides[i];
347 u64 devid = btrfs_raid_stride_devid(leaf, stride);
348 u64 physical = btrfs_raid_stride_physical(leaf, stride);
349
350 if (devid != stripe->dev->devid)
351 continue;
352
353 if ((map_type & BTRFS_BLOCK_GROUP_DUP) && stripe_index != i)
354 continue;
355
356 stripe->physical = physical + offset;
357
358 trace_btrfs_get_raid_extent_offset(fs_info, logical, *length,
359 stripe->physical, devid);
360
361 ret = 0;
362 goto free_path;
363 }
364
365 /* If we're here, we haven't found the requested devid in the stripe. */
366 ret = -ENODATA;
367out:
368 if (ret > 0)
369 ret = -ENODATA;
370 if (ret && ret != -EIO && !stripe->rst_search_commit_root) {
371 btrfs_debug(fs_info,
372 "cannot find raid-stripe for logical [%llu, %llu] devid %llu, profile %s",
373 logical, logical + *length, stripe->dev->devid,
374 btrfs_bg_type_to_raid_name(map_type));
375 }
376free_path:
377 btrfs_free_path(path);
378
379 return ret;
380}
1// SPDX-License-Identifier: GPL-2.0
2/*
3 * Copyright (C) 2023 Western Digital Corporation or its affiliates.
4 */
5
6#include <linux/btrfs_tree.h>
7#include "ctree.h"
8#include "fs.h"
9#include "accessors.h"
10#include "transaction.h"
11#include "disk-io.h"
12#include "raid-stripe-tree.h"
13#include "volumes.h"
14#include "print-tree.h"
15
16int btrfs_delete_raid_extent(struct btrfs_trans_handle *trans, u64 start, u64 length)
17{
18 struct btrfs_fs_info *fs_info = trans->fs_info;
19 struct btrfs_root *stripe_root = fs_info->stripe_root;
20 struct btrfs_path *path;
21 struct btrfs_key key;
22 struct extent_buffer *leaf;
23 u64 found_start;
24 u64 found_end;
25 u64 end = start + length;
26 int slot;
27 int ret;
28
29 if (!stripe_root)
30 return 0;
31
32 path = btrfs_alloc_path();
33 if (!path)
34 return -ENOMEM;
35
36 while (1) {
37 key.objectid = start;
38 key.type = BTRFS_RAID_STRIPE_KEY;
39 key.offset = length;
40
41 ret = btrfs_search_slot(trans, stripe_root, &key, path, -1, 1);
42 if (ret < 0)
43 break;
44 if (ret > 0) {
45 ret = 0;
46 if (path->slots[0] == 0)
47 break;
48 path->slots[0]--;
49 }
50
51 leaf = path->nodes[0];
52 slot = path->slots[0];
53 btrfs_item_key_to_cpu(leaf, &key, slot);
54 found_start = key.objectid;
55 found_end = found_start + key.offset;
56
57 /* That stripe ends before we start, we're done. */
58 if (found_end <= start)
59 break;
60
61 trace_btrfs_raid_extent_delete(fs_info, start, end,
62 found_start, found_end);
63
64 ASSERT(found_start >= start && found_end <= end);
65 ret = btrfs_del_item(trans, stripe_root, path);
66 if (ret)
67 break;
68
69 btrfs_release_path(path);
70 }
71
72 btrfs_free_path(path);
73 return ret;
74}
75
76static int btrfs_insert_one_raid_extent(struct btrfs_trans_handle *trans,
77 struct btrfs_io_context *bioc)
78{
79 struct btrfs_fs_info *fs_info = trans->fs_info;
80 struct btrfs_key stripe_key;
81 struct btrfs_root *stripe_root = fs_info->stripe_root;
82 const int num_stripes = btrfs_bg_type_to_factor(bioc->map_type);
83 u8 encoding = btrfs_bg_flags_to_raid_index(bioc->map_type);
84 struct btrfs_stripe_extent *stripe_extent;
85 const size_t item_size = struct_size(stripe_extent, strides, num_stripes);
86 int ret;
87
88 stripe_extent = kzalloc(item_size, GFP_NOFS);
89 if (!stripe_extent) {
90 btrfs_abort_transaction(trans, -ENOMEM);
91 btrfs_end_transaction(trans);
92 return -ENOMEM;
93 }
94
95 trace_btrfs_insert_one_raid_extent(fs_info, bioc->logical, bioc->size,
96 num_stripes);
97 btrfs_set_stack_stripe_extent_encoding(stripe_extent, encoding);
98 for (int i = 0; i < num_stripes; i++) {
99 u64 devid = bioc->stripes[i].dev->devid;
100 u64 physical = bioc->stripes[i].physical;
101 u64 length = bioc->stripes[i].length;
102 struct btrfs_raid_stride *raid_stride = &stripe_extent->strides[i];
103
104 if (length == 0)
105 length = bioc->size;
106
107 btrfs_set_stack_raid_stride_devid(raid_stride, devid);
108 btrfs_set_stack_raid_stride_physical(raid_stride, physical);
109 }
110
111 stripe_key.objectid = bioc->logical;
112 stripe_key.type = BTRFS_RAID_STRIPE_KEY;
113 stripe_key.offset = bioc->size;
114
115 ret = btrfs_insert_item(trans, stripe_root, &stripe_key, stripe_extent,
116 item_size);
117 if (ret)
118 btrfs_abort_transaction(trans, ret);
119
120 kfree(stripe_extent);
121
122 return ret;
123}
124
125int btrfs_insert_raid_extent(struct btrfs_trans_handle *trans,
126 struct btrfs_ordered_extent *ordered_extent)
127{
128 struct btrfs_io_context *bioc;
129 int ret;
130
131 if (!btrfs_fs_incompat(trans->fs_info, RAID_STRIPE_TREE))
132 return 0;
133
134 list_for_each_entry(bioc, &ordered_extent->bioc_list, rst_ordered_entry) {
135 ret = btrfs_insert_one_raid_extent(trans, bioc);
136 if (ret)
137 return ret;
138 }
139
140 while (!list_empty(&ordered_extent->bioc_list)) {
141 bioc = list_first_entry(&ordered_extent->bioc_list,
142 typeof(*bioc), rst_ordered_entry);
143 list_del(&bioc->rst_ordered_entry);
144 btrfs_put_bioc(bioc);
145 }
146
147 return 0;
148}
149
150int btrfs_get_raid_extent_offset(struct btrfs_fs_info *fs_info,
151 u64 logical, u64 *length, u64 map_type,
152 u32 stripe_index, struct btrfs_io_stripe *stripe)
153{
154 struct btrfs_root *stripe_root = fs_info->stripe_root;
155 struct btrfs_stripe_extent *stripe_extent;
156 struct btrfs_key stripe_key;
157 struct btrfs_key found_key;
158 struct btrfs_path *path;
159 struct extent_buffer *leaf;
160 const u64 end = logical + *length;
161 int num_stripes;
162 u8 encoding;
163 u64 offset;
164 u64 found_logical;
165 u64 found_length;
166 u64 found_end;
167 int slot;
168 int ret;
169
170 stripe_key.objectid = logical;
171 stripe_key.type = BTRFS_RAID_STRIPE_KEY;
172 stripe_key.offset = 0;
173
174 path = btrfs_alloc_path();
175 if (!path)
176 return -ENOMEM;
177
178 if (stripe->is_scrub) {
179 path->skip_locking = 1;
180 path->search_commit_root = 1;
181 }
182
183 ret = btrfs_search_slot(NULL, stripe_root, &stripe_key, path, 0, 0);
184 if (ret < 0)
185 goto free_path;
186 if (ret) {
187 if (path->slots[0] != 0)
188 path->slots[0]--;
189 }
190
191 while (1) {
192 leaf = path->nodes[0];
193 slot = path->slots[0];
194
195 btrfs_item_key_to_cpu(leaf, &found_key, slot);
196 found_logical = found_key.objectid;
197 found_length = found_key.offset;
198 found_end = found_logical + found_length;
199
200 if (found_logical > end) {
201 ret = -ENOENT;
202 goto out;
203 }
204
205 if (in_range(logical, found_logical, found_length))
206 break;
207
208 ret = btrfs_next_item(stripe_root, path);
209 if (ret)
210 goto out;
211 }
212
213 offset = logical - found_logical;
214
215 /*
216 * If we have a logically contiguous, but physically non-continuous
217 * range, we need to split the bio. Record the length after which we
218 * must split the bio.
219 */
220 if (end > found_end)
221 *length -= end - found_end;
222
223 num_stripes = btrfs_num_raid_stripes(btrfs_item_size(leaf, slot));
224 stripe_extent = btrfs_item_ptr(leaf, slot, struct btrfs_stripe_extent);
225 encoding = btrfs_stripe_extent_encoding(leaf, stripe_extent);
226
227 if (encoding != btrfs_bg_flags_to_raid_index(map_type)) {
228 ret = -EUCLEAN;
229 btrfs_handle_fs_error(fs_info, ret,
230 "on-disk stripe encoding %d doesn't match RAID index %d",
231 encoding,
232 btrfs_bg_flags_to_raid_index(map_type));
233 goto out;
234 }
235
236 for (int i = 0; i < num_stripes; i++) {
237 struct btrfs_raid_stride *stride = &stripe_extent->strides[i];
238 u64 devid = btrfs_raid_stride_devid(leaf, stride);
239 u64 physical = btrfs_raid_stride_physical(leaf, stride);
240
241 if (devid != stripe->dev->devid)
242 continue;
243
244 if ((map_type & BTRFS_BLOCK_GROUP_DUP) && stripe_index != i)
245 continue;
246
247 stripe->physical = physical + offset;
248
249 trace_btrfs_get_raid_extent_offset(fs_info, logical, *length,
250 stripe->physical, devid);
251
252 ret = 0;
253 goto free_path;
254 }
255
256 /* If we're here, we haven't found the requested devid in the stripe. */
257 ret = -ENOENT;
258out:
259 if (ret > 0)
260 ret = -ENOENT;
261 if (ret && ret != -EIO && !stripe->is_scrub) {
262 if (IS_ENABLED(CONFIG_BTRFS_DEBUG))
263 btrfs_print_tree(leaf, 1);
264 btrfs_err(fs_info,
265 "cannot find raid-stripe for logical [%llu, %llu] devid %llu, profile %s",
266 logical, logical + *length, stripe->dev->devid,
267 btrfs_bg_type_to_raid_name(map_type));
268 }
269free_path:
270 btrfs_free_path(path);
271
272 return ret;
273}