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