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