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 <asm/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 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 */ 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 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 btrfs_mark_buffer_dirty(trans, eb); 144 145 out: 146 btrfs_free_path(path); 147 return ret; 148 } 149 150 int btrfs_uuid_tree_remove(struct btrfs_trans_handle *trans, const u8 *uuid, u8 type, 151 u64 subid) 152 { 153 struct btrfs_fs_info *fs_info = trans->fs_info; 154 struct btrfs_root *uuid_root = fs_info->uuid_root; 155 int ret; 156 struct btrfs_path *path = NULL; 157 struct btrfs_key key; 158 struct extent_buffer *eb; 159 int slot; 160 unsigned long offset; 161 u32 item_size; 162 unsigned long move_dst; 163 unsigned long move_src; 164 unsigned long move_len; 165 166 if (WARN_ON_ONCE(!uuid_root)) { 167 ret = -EINVAL; 168 goto out; 169 } 170 171 btrfs_uuid_to_key(uuid, type, &key); 172 173 path = btrfs_alloc_path(); 174 if (!path) { 175 ret = -ENOMEM; 176 goto out; 177 } 178 179 ret = btrfs_search_slot(trans, uuid_root, &key, path, -1, 1); 180 if (ret < 0) { 181 btrfs_warn(fs_info, "error %d while searching for uuid item!", 182 ret); 183 goto out; 184 } 185 if (ret > 0) { 186 ret = -ENOENT; 187 goto out; 188 } 189 190 eb = path->nodes[0]; 191 slot = path->slots[0]; 192 offset = btrfs_item_ptr_offset(eb, slot); 193 item_size = btrfs_item_size(eb, slot); 194 if (!IS_ALIGNED(item_size, sizeof(u64))) { 195 btrfs_warn(fs_info, "uuid item with illegal size %lu!", 196 (unsigned long)item_size); 197 ret = -ENOENT; 198 goto out; 199 } 200 while (item_size) { 201 __le64 read_subid; 202 203 read_extent_buffer(eb, &read_subid, offset, sizeof(read_subid)); 204 if (le64_to_cpu(read_subid) == subid) 205 break; 206 offset += sizeof(read_subid); 207 item_size -= sizeof(read_subid); 208 } 209 210 if (!item_size) { 211 ret = -ENOENT; 212 goto out; 213 } 214 215 item_size = btrfs_item_size(eb, slot); 216 if (item_size == sizeof(subid)) { 217 ret = btrfs_del_item(trans, uuid_root, path); 218 goto out; 219 } 220 221 move_dst = offset; 222 move_src = offset + sizeof(subid); 223 move_len = item_size - (move_src - btrfs_item_ptr_offset(eb, slot)); 224 memmove_extent_buffer(eb, move_dst, move_src, move_len); 225 btrfs_truncate_item(trans, path, item_size - sizeof(subid), 1); 226 227 out: 228 btrfs_free_path(path); 229 return ret; 230 } 231 232 static int btrfs_uuid_iter_rem(struct btrfs_root *uuid_root, u8 *uuid, u8 type, 233 u64 subid) 234 { 235 struct btrfs_trans_handle *trans; 236 int ret; 237 238 /* 1 - for the uuid item */ 239 trans = btrfs_start_transaction(uuid_root, 1); 240 if (IS_ERR(trans)) { 241 ret = PTR_ERR(trans); 242 goto out; 243 } 244 245 ret = btrfs_uuid_tree_remove(trans, uuid, type, subid); 246 btrfs_end_transaction(trans); 247 248 out: 249 return ret; 250 } 251 252 /* 253 * Check if there's an matching subvolume for given UUID 254 * 255 * Return: 256 * 0 check succeeded, the entry is not outdated 257 * > 0 if the check failed, the caller should remove the entry 258 * < 0 if an error occurred 259 */ 260 static int btrfs_check_uuid_tree_entry(struct btrfs_fs_info *fs_info, 261 const u8 *uuid, u8 type, u64 subvolid) 262 { 263 int ret = 0; 264 struct btrfs_root *subvol_root; 265 266 if (type != BTRFS_UUID_KEY_SUBVOL && 267 type != BTRFS_UUID_KEY_RECEIVED_SUBVOL) 268 goto out; 269 270 subvol_root = btrfs_get_fs_root(fs_info, subvolid, true); 271 if (IS_ERR(subvol_root)) { 272 ret = PTR_ERR(subvol_root); 273 if (ret == -ENOENT) 274 ret = 1; 275 goto out; 276 } 277 278 switch (type) { 279 case BTRFS_UUID_KEY_SUBVOL: 280 if (memcmp(uuid, subvol_root->root_item.uuid, BTRFS_UUID_SIZE)) 281 ret = 1; 282 break; 283 case BTRFS_UUID_KEY_RECEIVED_SUBVOL: 284 if (memcmp(uuid, subvol_root->root_item.received_uuid, 285 BTRFS_UUID_SIZE)) 286 ret = 1; 287 break; 288 } 289 btrfs_put_root(subvol_root); 290 out: 291 return ret; 292 } 293 294 int btrfs_uuid_tree_iterate(struct btrfs_fs_info *fs_info) 295 { 296 struct btrfs_root *root = fs_info->uuid_root; 297 struct btrfs_key key; 298 struct btrfs_path *path; 299 int ret = 0; 300 struct extent_buffer *leaf; 301 int slot; 302 u32 item_size; 303 unsigned long offset; 304 305 path = btrfs_alloc_path(); 306 if (!path) { 307 ret = -ENOMEM; 308 goto out; 309 } 310 311 key.objectid = 0; 312 key.type = 0; 313 key.offset = 0; 314 315 again_search_slot: 316 ret = btrfs_search_forward(root, &key, path, BTRFS_OLDEST_GENERATION); 317 if (ret) { 318 if (ret > 0) 319 ret = 0; 320 goto out; 321 } 322 323 while (1) { 324 if (btrfs_fs_closing(fs_info)) { 325 ret = -EINTR; 326 goto out; 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 goto out; 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 goto out; 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 out: 392 btrfs_free_path(path); 393 return ret; 394 } 395 396 int btrfs_uuid_scan_kthread(void *data) 397 { 398 struct btrfs_fs_info *fs_info = data; 399 struct btrfs_root *root = fs_info->tree_root; 400 struct btrfs_key key; 401 struct btrfs_path *path = NULL; 402 int ret = 0; 403 struct extent_buffer *eb; 404 int slot; 405 struct btrfs_root_item root_item; 406 u32 item_size; 407 struct btrfs_trans_handle *trans = NULL; 408 bool closing = false; 409 410 path = btrfs_alloc_path(); 411 if (!path) { 412 ret = -ENOMEM; 413 goto out; 414 } 415 416 key.objectid = 0; 417 key.type = BTRFS_ROOT_ITEM_KEY; 418 key.offset = 0; 419 420 while (1) { 421 if (btrfs_fs_closing(fs_info)) { 422 closing = true; 423 break; 424 } 425 ret = btrfs_search_forward(root, &key, path, 426 BTRFS_OLDEST_GENERATION); 427 if (ret) { 428 if (ret > 0) 429 ret = 0; 430 break; 431 } 432 433 if (key.type != BTRFS_ROOT_ITEM_KEY || 434 (key.objectid < BTRFS_FIRST_FREE_OBJECTID && 435 key.objectid != BTRFS_FS_TREE_OBJECTID) || 436 key.objectid > BTRFS_LAST_FREE_OBJECTID) 437 goto skip; 438 439 eb = path->nodes[0]; 440 slot = path->slots[0]; 441 item_size = btrfs_item_size(eb, slot); 442 if (item_size < sizeof(root_item)) 443 goto skip; 444 445 read_extent_buffer(eb, &root_item, 446 btrfs_item_ptr_offset(eb, slot), 447 (int)sizeof(root_item)); 448 if (btrfs_root_refs(&root_item) == 0) 449 goto skip; 450 451 if (!btrfs_is_empty_uuid(root_item.uuid) || 452 !btrfs_is_empty_uuid(root_item.received_uuid)) { 453 if (trans) 454 goto update_tree; 455 456 btrfs_release_path(path); 457 /* 458 * 1 - subvol uuid item 459 * 1 - received_subvol uuid item 460 */ 461 trans = btrfs_start_transaction(fs_info->uuid_root, 2); 462 if (IS_ERR(trans)) { 463 ret = PTR_ERR(trans); 464 break; 465 } 466 continue; 467 } else { 468 goto skip; 469 } 470 update_tree: 471 btrfs_release_path(path); 472 if (!btrfs_is_empty_uuid(root_item.uuid)) { 473 ret = btrfs_uuid_tree_add(trans, root_item.uuid, 474 BTRFS_UUID_KEY_SUBVOL, 475 key.objectid); 476 if (ret < 0) { 477 btrfs_warn(fs_info, "uuid_tree_add failed %d", 478 ret); 479 break; 480 } 481 } 482 483 if (!btrfs_is_empty_uuid(root_item.received_uuid)) { 484 ret = btrfs_uuid_tree_add(trans, 485 root_item.received_uuid, 486 BTRFS_UUID_KEY_RECEIVED_SUBVOL, 487 key.objectid); 488 if (ret < 0) { 489 btrfs_warn(fs_info, "uuid_tree_add failed %d", 490 ret); 491 break; 492 } 493 } 494 495 skip: 496 btrfs_release_path(path); 497 if (trans) { 498 ret = btrfs_end_transaction(trans); 499 trans = NULL; 500 if (ret) 501 break; 502 } 503 504 if (key.offset < (u64)-1) { 505 key.offset++; 506 } else if (key.type < BTRFS_ROOT_ITEM_KEY) { 507 key.offset = 0; 508 key.type = BTRFS_ROOT_ITEM_KEY; 509 } else if (key.objectid < (u64)-1) { 510 key.offset = 0; 511 key.type = BTRFS_ROOT_ITEM_KEY; 512 key.objectid++; 513 } else { 514 break; 515 } 516 cond_resched(); 517 } 518 519 out: 520 btrfs_free_path(path); 521 if (trans && !IS_ERR(trans)) 522 btrfs_end_transaction(trans); 523 if (ret) 524 btrfs_warn(fs_info, "btrfs_uuid_scan_kthread failed %d", ret); 525 else if (!closing) 526 set_bit(BTRFS_FS_UPDATE_UUID_TREE_GEN, &fs_info->flags); 527 up(&fs_info->uuid_tree_rescan_sem); 528 return 0; 529 } 530 531 int btrfs_create_uuid_tree(struct btrfs_fs_info *fs_info) 532 { 533 struct btrfs_trans_handle *trans; 534 struct btrfs_root *tree_root = fs_info->tree_root; 535 struct btrfs_root *uuid_root; 536 struct task_struct *task; 537 int ret; 538 539 /* 540 * 1 - root node 541 * 1 - root item 542 */ 543 trans = btrfs_start_transaction(tree_root, 2); 544 if (IS_ERR(trans)) 545 return PTR_ERR(trans); 546 547 uuid_root = btrfs_create_tree(trans, BTRFS_UUID_TREE_OBJECTID); 548 if (IS_ERR(uuid_root)) { 549 ret = PTR_ERR(uuid_root); 550 btrfs_abort_transaction(trans, ret); 551 btrfs_end_transaction(trans); 552 return ret; 553 } 554 555 fs_info->uuid_root = uuid_root; 556 557 ret = btrfs_commit_transaction(trans); 558 if (ret) 559 return ret; 560 561 down(&fs_info->uuid_tree_rescan_sem); 562 task = kthread_run(btrfs_uuid_scan_kthread, fs_info, "btrfs-uuid"); 563 if (IS_ERR(task)) { 564 /* fs_info->update_uuid_tree_gen remains 0 in all error case */ 565 btrfs_warn(fs_info, "failed to start uuid_scan task"); 566 up(&fs_info->uuid_tree_rescan_sem); 567 return PTR_ERR(task); 568 } 569 570 return 0; 571 } 572