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 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 out: 144 btrfs_free_path(path); 145 return ret; 146 } 147 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 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 */ 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 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 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 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