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