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 -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
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 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
btrfs_uuid_tree_remove(struct btrfs_trans_handle * trans,const u8 * uuid,u8 type,u64 subid)133 int 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 */
btrfs_uuid_tree_check_overflow(struct btrfs_fs_info * fs_info,const u8 * uuid,u8 type)209 int 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
btrfs_uuid_iter_rem(struct btrfs_root * uuid_root,u8 * uuid,u8 type,u64 subid)240 static 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 return PTR_ERR(trans);
250
251 ret = btrfs_uuid_tree_remove(trans, uuid, type, subid);
252 btrfs_end_transaction(trans);
253 return ret;
254 }
255
256 /*
257 * Check if there's an matching subvolume for given UUID
258 *
259 * Return:
260 * 0 check succeeded, the entry is not outdated
261 * > 0 if the check failed, the caller should remove the entry
262 * < 0 if an error occurred
263 */
btrfs_check_uuid_tree_entry(struct btrfs_fs_info * fs_info,const u8 * uuid,u8 type,u64 subvolid)264 static int btrfs_check_uuid_tree_entry(struct btrfs_fs_info *fs_info,
265 const u8 *uuid, u8 type, u64 subvolid)
266 {
267 int ret = 0;
268 struct btrfs_root *subvol_root;
269
270 if (type != BTRFS_UUID_KEY_SUBVOL &&
271 type != BTRFS_UUID_KEY_RECEIVED_SUBVOL)
272 return 0;
273
274 subvol_root = btrfs_get_fs_root(fs_info, subvolid, true);
275 if (IS_ERR(subvol_root)) {
276 ret = PTR_ERR(subvol_root);
277 if (ret == -ENOENT)
278 return 1;
279 return ret;
280 }
281
282 switch (type) {
283 case BTRFS_UUID_KEY_SUBVOL:
284 if (memcmp(uuid, subvol_root->root_item.uuid, BTRFS_UUID_SIZE))
285 ret = 1;
286 break;
287 case BTRFS_UUID_KEY_RECEIVED_SUBVOL:
288 if (memcmp(uuid, subvol_root->root_item.received_uuid,
289 BTRFS_UUID_SIZE))
290 ret = 1;
291 break;
292 }
293 btrfs_put_root(subvol_root);
294
295 return ret;
296 }
297
btrfs_uuid_tree_iterate(struct btrfs_fs_info * fs_info)298 int btrfs_uuid_tree_iterate(struct btrfs_fs_info *fs_info)
299 {
300 struct btrfs_root *root = fs_info->uuid_root;
301 struct btrfs_key key;
302 BTRFS_PATH_AUTO_FREE(path);
303 int ret = 0;
304 struct extent_buffer *leaf;
305 int slot;
306 u32 item_size;
307 unsigned long offset;
308
309 path = btrfs_alloc_path();
310 if (!path)
311 return -ENOMEM;
312
313 key.objectid = 0;
314 key.type = 0;
315 key.offset = 0;
316
317 again_search_slot:
318 ret = btrfs_search_forward(root, &key, path, BTRFS_OLDEST_GENERATION);
319 if (ret < 0)
320 return ret;
321 if (ret > 0)
322 return 0;
323
324 while (1) {
325 if (btrfs_fs_closing(fs_info))
326 return -EINTR;
327
328 cond_resched();
329 leaf = path->nodes[0];
330 slot = path->slots[0];
331 btrfs_item_key_to_cpu(leaf, &key, slot);
332
333 if (key.type != BTRFS_UUID_KEY_SUBVOL &&
334 key.type != BTRFS_UUID_KEY_RECEIVED_SUBVOL)
335 goto skip;
336
337 offset = btrfs_item_ptr_offset(leaf, slot);
338 item_size = btrfs_item_size(leaf, slot);
339 if (!IS_ALIGNED(item_size, sizeof(u64))) {
340 btrfs_warn(fs_info,
341 "uuid item with illegal size %lu!",
342 (unsigned long)item_size);
343 goto skip;
344 }
345 while (item_size) {
346 u8 uuid[BTRFS_UUID_SIZE];
347 __le64 subid_le;
348 u64 subid_cpu;
349
350 put_unaligned_le64(key.objectid, uuid);
351 put_unaligned_le64(key.offset, uuid + sizeof(u64));
352 read_extent_buffer(leaf, &subid_le, offset,
353 sizeof(subid_le));
354 subid_cpu = le64_to_cpu(subid_le);
355 ret = btrfs_check_uuid_tree_entry(fs_info, uuid,
356 key.type, subid_cpu);
357 if (ret < 0)
358 return ret;
359 if (ret > 0) {
360 btrfs_release_path(path);
361 ret = btrfs_uuid_iter_rem(root, uuid, key.type,
362 subid_cpu);
363 if (ret == 0) {
364 /*
365 * this might look inefficient, but the
366 * justification is that it is an
367 * exception that check_func returns 1,
368 * and that in the regular case only one
369 * entry per UUID exists.
370 */
371 goto again_search_slot;
372 }
373 if (ret < 0 && ret != -ENOENT)
374 return ret;
375 key.offset++;
376 goto again_search_slot;
377 }
378 item_size -= sizeof(subid_le);
379 offset += sizeof(subid_le);
380 }
381
382 skip:
383 ret = btrfs_next_item(root, path);
384 if (ret == 0)
385 continue;
386 else if (ret > 0)
387 ret = 0;
388 break;
389 }
390
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