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}