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 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 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 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 */ 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 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 */ 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 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 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