uuid-tree.c

  1// SPDX-License-Identifier: GPL-2.0
  2/*
  3 * Copyright (C) STRATO AG 2013.  All rights reserved.
  4 */
  5
  6#include <linux/kthread.h>
  7#include <linux/uuid.h>
  8#include <linux/unaligned.h>
  9#include "messages.h"
 10#include "ctree.h"
 11#include "transaction.h"
 12#include "disk-io.h"
 13#include "fs.h"
 14#include "accessors.h"
 15#include "uuid-tree.h"
 16#include "ioctl.h"
 17
 18static void btrfs_uuid_to_key(const u8 *uuid, u8 type, struct btrfs_key *key)
 19{
 20	key->type = type;
 21	key->objectid = get_unaligned_le64(uuid);
 22	key->offset = get_unaligned_le64(uuid + sizeof(u64));
 23}
 24
 25/* return -ENOENT for !found, < 0 for errors, or 0 if an item was found */
 26static int btrfs_uuid_tree_lookup(struct btrfs_root *uuid_root, const u8 *uuid,
 27				  u8 type, u64 subid)
 28{
 29	int ret;
 30	BTRFS_PATH_AUTO_FREE(path);
 31	struct extent_buffer *eb;
 32	int slot;
 33	u32 item_size;
 34	unsigned long offset;
 35	struct btrfs_key key;
 36
 37	if (WARN_ON_ONCE(!uuid_root))
 38		return -ENOENT;
 39
 40	path = btrfs_alloc_path();
 41	if (!path)
 42		return -ENOMEM;
 43
 44	btrfs_uuid_to_key(uuid, type, &key);
 45	ret = btrfs_search_slot(NULL, uuid_root, &key, path, 0, 0);
 46	if (ret < 0)
 47		return ret;
 48	if (ret > 0)
 49		return -ENOENT;
 50
 51	eb = path->nodes[0];
 52	slot = path->slots[0];
 53	item_size = btrfs_item_size(eb, slot);
 54	offset = btrfs_item_ptr_offset(eb, slot);
 55	ret = -ENOENT;
 56
 57	if (!IS_ALIGNED(item_size, sizeof(u64))) {
 58		btrfs_warn(uuid_root->fs_info,
 59			   "uuid item with illegal size %lu!",
 60			   (unsigned long)item_size);
 61		return ret;
 62	}
 63	while (item_size) {
 64		__le64 data;
 65
 66		read_extent_buffer(eb, &data, offset, sizeof(data));
 67		if (le64_to_cpu(data) == subid) {
 68			ret = 0;
 69			break;
 70		}
 71		offset += sizeof(data);
 72		item_size -= sizeof(data);
 73	}
 74
 75	return ret;
 76}
 77
 78int btrfs_uuid_tree_add(struct btrfs_trans_handle *trans, const u8 *uuid, u8 type,
 79			u64 subid_cpu)
 80{
 81	struct btrfs_fs_info *fs_info = trans->fs_info;
 82	struct btrfs_root *uuid_root = fs_info->uuid_root;
 83	int ret;
 84	BTRFS_PATH_AUTO_FREE(path);
 85	struct btrfs_key key;
 86	struct extent_buffer *eb;
 87	int slot;
 88	unsigned long offset;
 89	__le64 subid_le;
 90
 91	ret = btrfs_uuid_tree_lookup(uuid_root, uuid, type, subid_cpu);
 92	if (ret != -ENOENT)
 93		return ret;
 94
 95	if (WARN_ON_ONCE(!uuid_root))
 96		return -EINVAL;
 97
 98	btrfs_uuid_to_key(uuid, type, &key);
 99
100	path = btrfs_alloc_path();
101	if (!path)
102		return -ENOMEM;
103
104	ret = btrfs_insert_empty_item(trans, uuid_root, path, &key,
105				      sizeof(subid_le));
106	if (ret == 0) {
107		/* Add an item for the type for the first time */
108		eb = path->nodes[0];
109		slot = path->slots[0];
110		offset = btrfs_item_ptr_offset(eb, slot);
111	} else if (ret == -EEXIST) {
112		/*
113		 * An item with that type already exists.
114		 * Extend the item and store the new subid at the end.
115		 */
116		btrfs_extend_item(trans, path, sizeof(subid_le));
117		eb = path->nodes[0];
118		slot = path->slots[0];
119		offset = btrfs_item_ptr_offset(eb, slot);
120		offset += btrfs_item_size(eb, slot) - sizeof(subid_le);
121	} else {
122		btrfs_warn(fs_info,
123			   "insert uuid item failed %d (0x%016llx, 0x%016llx) type %u!",
124			   ret, key.objectid, key.offset, type);
125		return ret;
126	}
127
128	subid_le = cpu_to_le64(subid_cpu);
129	write_extent_buffer(eb, &subid_le, offset, sizeof(subid_le));
130	return 0;
131}
132
133int btrfs_uuid_tree_remove(struct btrfs_trans_handle *trans, const u8 *uuid, u8 type,
134			u64 subid)
135{
136	struct btrfs_fs_info *fs_info = trans->fs_info;
137	struct btrfs_root *uuid_root = fs_info->uuid_root;
138	int ret;
139	BTRFS_PATH_AUTO_FREE(path);
140	struct btrfs_key key;
141	struct extent_buffer *eb;
142	int slot;
143	unsigned long offset;
144	u32 item_size;
145	unsigned long move_dst;
146	unsigned long move_src;
147	unsigned long move_len;
148
149	if (WARN_ON_ONCE(!uuid_root))
150		return -EINVAL;
151
152	btrfs_uuid_to_key(uuid, type, &key);
153
154	path = btrfs_alloc_path();
155	if (!path)
156		return -ENOMEM;
157
158	ret = btrfs_search_slot(trans, uuid_root, &key, path, -1, 1);
159	if (ret < 0) {
160		btrfs_warn(fs_info, "error %d while searching for uuid item!",
161			   ret);
162		return ret;
163	}
164	if (ret > 0)
165		return -ENOENT;
166
167	eb = path->nodes[0];
168	slot = path->slots[0];
169	offset = btrfs_item_ptr_offset(eb, slot);
170	item_size = btrfs_item_size(eb, slot);
171	if (!IS_ALIGNED(item_size, sizeof(u64))) {
172		btrfs_warn(fs_info, "uuid item with illegal size %lu!",
173			   (unsigned long)item_size);
174		return -ENOENT;
175	}
176	while (item_size) {
177		__le64 read_subid;
178
179		read_extent_buffer(eb, &read_subid, offset, sizeof(read_subid));
180		if (le64_to_cpu(read_subid) == subid)
181			break;
182		offset += sizeof(read_subid);
183		item_size -= sizeof(read_subid);
184	}
185
186	if (!item_size)
187		return -ENOENT;
188
189	item_size = btrfs_item_size(eb, slot);
190	if (item_size == sizeof(subid))
191		return btrfs_del_item(trans, uuid_root, path);
192
193	move_dst = offset;
194	move_src = offset + sizeof(subid);
195	move_len = item_size - (move_src - btrfs_item_ptr_offset(eb, slot));
196	memmove_extent_buffer(eb, move_dst, move_src, move_len);
197	btrfs_truncate_item(trans, path, item_size - sizeof(subid), 1);
198
199	return 0;
200}
201
202/*
203 * Check if we can add one root ID to a UUID key.
204 * If the key does not yet exists, we can, otherwise only if extended item does
205 * not exceeds the maximum item size permitted by the leaf size.
206 *
207 * Returns 0 on success, negative value on error.
208 */
209int btrfs_uuid_tree_check_overflow(struct btrfs_fs_info *fs_info,
210				   const u8 *uuid, u8 type)
211{
212	BTRFS_PATH_AUTO_FREE(path);
213	int ret;
214	u32 item_size;
215	struct btrfs_key key;
216
217	if (WARN_ON_ONCE(!fs_info->uuid_root))
218		return -EINVAL;
219
220	path = btrfs_alloc_path();
221	if (!path)
222		return -ENOMEM;
223
224	btrfs_uuid_to_key(uuid, type, &key);
225	ret = btrfs_search_slot(NULL, fs_info->uuid_root, &key, path, 0, 0);
226	if (ret < 0)
227		return ret;
228	if (ret > 0)
229		return 0;
230
231	item_size = btrfs_item_size(path->nodes[0], path->slots[0]);
232
233	if (sizeof(struct btrfs_item) + item_size + sizeof(u64) >
234	    BTRFS_LEAF_DATA_SIZE(fs_info))
235		return -EOVERFLOW;
236
237	return 0;
238}
239
240static int btrfs_uuid_iter_rem(struct btrfs_root *uuid_root, u8 *uuid, u8 type,
241			       u64 subid)
242{
243	struct btrfs_trans_handle *trans;
244	int ret;
245
246	/* 1 - for the uuid item */
247	trans = btrfs_start_transaction(uuid_root, 1);
248	if (IS_ERR(trans)) {
249		ret = PTR_ERR(trans);
250		goto out;
251	}
252
253	ret = btrfs_uuid_tree_remove(trans, uuid, type, subid);
254	btrfs_end_transaction(trans);
255
256out:
257	return ret;
258}
259
260/*
261 * Check if there's an matching subvolume for given UUID
262 *
263 * Return:
264 * 0	check succeeded, the entry is not outdated
265 * > 0	if the check failed, the caller should remove the entry
266 * < 0	if an error occurred
267 */
268static int btrfs_check_uuid_tree_entry(struct btrfs_fs_info *fs_info,
269				       const u8 *uuid, u8 type, u64 subvolid)
270{
271	int ret = 0;
272	struct btrfs_root *subvol_root;
273
274	if (type != BTRFS_UUID_KEY_SUBVOL &&
275	    type != BTRFS_UUID_KEY_RECEIVED_SUBVOL)
276		goto out;
277
278	subvol_root = btrfs_get_fs_root(fs_info, subvolid, true);
279	if (IS_ERR(subvol_root)) {
280		ret = PTR_ERR(subvol_root);
281		if (ret == -ENOENT)
282			ret = 1;
283		goto out;
284	}
285
286	switch (type) {
287	case BTRFS_UUID_KEY_SUBVOL:
288		if (memcmp(uuid, subvol_root->root_item.uuid, BTRFS_UUID_SIZE))
289			ret = 1;
290		break;
291	case BTRFS_UUID_KEY_RECEIVED_SUBVOL:
292		if (memcmp(uuid, subvol_root->root_item.received_uuid,
293			   BTRFS_UUID_SIZE))
294			ret = 1;
295		break;
296	}
297	btrfs_put_root(subvol_root);
298out:
299	return ret;
300}
301
302int btrfs_uuid_tree_iterate(struct btrfs_fs_info *fs_info)
303{
304	struct btrfs_root *root = fs_info->uuid_root;
305	struct btrfs_key key;
306	BTRFS_PATH_AUTO_FREE(path);
307	int ret = 0;
308	struct extent_buffer *leaf;
309	int slot;
310	u32 item_size;
311	unsigned long offset;
312
313	path = btrfs_alloc_path();
314	if (!path)
315		return -ENOMEM;
316
317	key.objectid = 0;
318	key.type = 0;
319	key.offset = 0;
320
321again_search_slot:
322	ret = btrfs_search_forward(root, &key, path, BTRFS_OLDEST_GENERATION);
323	if (ret < 0)
324		return ret;
325	if (ret > 0)
326		return 0;
327
328	while (1) {
329		if (btrfs_fs_closing(fs_info))
330			return -EINTR;
331
332		cond_resched();
333		leaf = path->nodes[0];
334		slot = path->slots[0];
335		btrfs_item_key_to_cpu(leaf, &key, slot);
336
337		if (key.type != BTRFS_UUID_KEY_SUBVOL &&
338		    key.type != BTRFS_UUID_KEY_RECEIVED_SUBVOL)
339			goto skip;
340
341		offset = btrfs_item_ptr_offset(leaf, slot);
342		item_size = btrfs_item_size(leaf, slot);
343		if (!IS_ALIGNED(item_size, sizeof(u64))) {
344			btrfs_warn(fs_info,
345				   "uuid item with illegal size %lu!",
346				   (unsigned long)item_size);
347			goto skip;
348		}
349		while (item_size) {
350			u8 uuid[BTRFS_UUID_SIZE];
351			__le64 subid_le;
352			u64 subid_cpu;
353
354			put_unaligned_le64(key.objectid, uuid);
355			put_unaligned_le64(key.offset, uuid + sizeof(u64));
356			read_extent_buffer(leaf, &subid_le, offset,
357					   sizeof(subid_le));
358			subid_cpu = le64_to_cpu(subid_le);
359			ret = btrfs_check_uuid_tree_entry(fs_info, uuid,
360							  key.type, subid_cpu);
361			if (ret < 0)
362				return ret;
363			if (ret > 0) {
364				btrfs_release_path(path);
365				ret = btrfs_uuid_iter_rem(root, uuid, key.type,
366							  subid_cpu);
367				if (ret == 0) {
368					/*
369					 * this might look inefficient, but the
370					 * justification is that it is an
371					 * exception that check_func returns 1,
372					 * and that in the regular case only one
373					 * entry per UUID exists.
374					 */
375					goto again_search_slot;
376				}
377				if (ret < 0 && ret != -ENOENT)
378					return ret;
379				key.offset++;
380				goto again_search_slot;
381			}
382			item_size -= sizeof(subid_le);
383			offset += sizeof(subid_le);
384		}
385
386skip:
387		ret = btrfs_next_item(root, path);
388		if (ret == 0)
389			continue;
390		else if (ret > 0)
391			ret = 0;
392		break;
393	}
394
395	return ret;
396}
397
398int btrfs_uuid_scan_kthread(void *data)
399{
400	struct btrfs_fs_info *fs_info = data;
401	struct btrfs_root *root = fs_info->tree_root;
402	struct btrfs_key key;
403	struct btrfs_path *path = NULL;
404	int ret = 0;
405	struct extent_buffer *eb;
406	int slot;
407	struct btrfs_root_item root_item;
408	u32 item_size;
409	struct btrfs_trans_handle *trans = NULL;
410	bool closing = false;
411
412	path = btrfs_alloc_path();
413	if (!path) {
414		ret = -ENOMEM;
415		goto out;
416	}
417
418	key.objectid = 0;
419	key.type = BTRFS_ROOT_ITEM_KEY;
420	key.offset = 0;
421
422	while (1) {
423		if (btrfs_fs_closing(fs_info)) {
424			closing = true;
425			break;
426		}
427		ret = btrfs_search_forward(root, &key, path,
428				BTRFS_OLDEST_GENERATION);
429		if (ret) {
430			if (ret > 0)
431				ret = 0;
432			break;
433		}
434
435		if (key.type != BTRFS_ROOT_ITEM_KEY ||
436		    (key.objectid < BTRFS_FIRST_FREE_OBJECTID &&
437		     key.objectid != BTRFS_FS_TREE_OBJECTID) ||
438		    key.objectid > BTRFS_LAST_FREE_OBJECTID)
439			goto skip;
440
441		eb = path->nodes[0];
442		slot = path->slots[0];
443		item_size = btrfs_item_size(eb, slot);
444		if (item_size < sizeof(root_item))
445			goto skip;
446
447		read_extent_buffer(eb, &root_item,
448				   btrfs_item_ptr_offset(eb, slot),
449				   (int)sizeof(root_item));
450		if (btrfs_root_refs(&root_item) == 0)
451			goto skip;
452
453		if (!btrfs_is_empty_uuid(root_item.uuid) ||
454		    !btrfs_is_empty_uuid(root_item.received_uuid)) {
455			if (trans)
456				goto update_tree;
457
458			btrfs_release_path(path);
459			/*
460			 * 1 - subvol uuid item
461			 * 1 - received_subvol uuid item
462			 */
463			trans = btrfs_start_transaction(fs_info->uuid_root, 2);
464			if (IS_ERR(trans)) {
465				ret = PTR_ERR(trans);
466				break;
467			}
468			continue;
469		} else {
470			goto skip;
471		}
472update_tree:
473		btrfs_release_path(path);
474		if (!btrfs_is_empty_uuid(root_item.uuid)) {
475			ret = btrfs_uuid_tree_add(trans, root_item.uuid,
476						  BTRFS_UUID_KEY_SUBVOL,
477						  key.objectid);
478			if (ret < 0) {
479				btrfs_warn(fs_info, "uuid_tree_add failed %d",
480					ret);
481				break;
482			}
483		}
484
485		if (!btrfs_is_empty_uuid(root_item.received_uuid)) {
486			ret = btrfs_uuid_tree_add(trans,
487						  root_item.received_uuid,
488						 BTRFS_UUID_KEY_RECEIVED_SUBVOL,
489						  key.objectid);
490			if (ret < 0) {
491				btrfs_warn(fs_info, "uuid_tree_add failed %d",
492					ret);
493				break;
494			}
495		}
496
497skip:
498		btrfs_release_path(path);
499		if (trans) {
500			ret = btrfs_end_transaction(trans);
501			trans = NULL;
502			if (ret)
503				break;
504		}
505
506		if (key.offset < (u64)-1) {
507			key.offset++;
508		} else if (key.type < BTRFS_ROOT_ITEM_KEY) {
509			key.offset = 0;
510			key.type = BTRFS_ROOT_ITEM_KEY;
511		} else if (key.objectid < (u64)-1) {
512			key.offset = 0;
513			key.type = BTRFS_ROOT_ITEM_KEY;
514			key.objectid++;
515		} else {
516			break;
517		}
518		cond_resched();
519	}
520
521out:
522	btrfs_free_path(path);
523	if (trans && !IS_ERR(trans))
524		btrfs_end_transaction(trans);
525	if (ret)
526		btrfs_warn(fs_info, "btrfs_uuid_scan_kthread failed %d", ret);
527	else if (!closing)
528		set_bit(BTRFS_FS_UPDATE_UUID_TREE_GEN, &fs_info->flags);
529	up(&fs_info->uuid_tree_rescan_sem);
530	return 0;
531}
532
533int btrfs_create_uuid_tree(struct btrfs_fs_info *fs_info)
534{
535	struct btrfs_trans_handle *trans;
536	struct btrfs_root *tree_root = fs_info->tree_root;
537	struct btrfs_root *uuid_root;
538	struct task_struct *task;
539	int ret;
540
541	/*
542	 * 1 - root node
543	 * 1 - root item
544	 */
545	trans = btrfs_start_transaction(tree_root, 2);
546	if (IS_ERR(trans))
547		return PTR_ERR(trans);
548
549	uuid_root = btrfs_create_tree(trans, BTRFS_UUID_TREE_OBJECTID);
550	if (IS_ERR(uuid_root)) {
551		ret = PTR_ERR(uuid_root);
552		btrfs_abort_transaction(trans, ret);
553		btrfs_end_transaction(trans);
554		return ret;
555	}
556
557	fs_info->uuid_root = uuid_root;
558
559	ret = btrfs_commit_transaction(trans);
560	if (ret)
561		return ret;
562
563	down(&fs_info->uuid_tree_rescan_sem);
564	task = kthread_run(btrfs_uuid_scan_kthread, fs_info, "btrfs-uuid");
565	if (IS_ERR(task)) {
566		/* fs_info->update_uuid_tree_gen remains 0 in all error case */
567		btrfs_warn(fs_info, "failed to start uuid_scan task");
568		up(&fs_info->uuid_tree_rescan_sem);
569		return PTR_ERR(task);
570	}
571
572	return 0;
573}