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 static int btrfs_uuid_iter_rem(struct btrfs_root *uuid_root, u8 *uuid, u8 type, 203 u64 subid) 204 { 205 struct btrfs_trans_handle *trans; 206 int ret; 207 208 /* 1 - for the uuid item */ 209 trans = btrfs_start_transaction(uuid_root, 1); 210 if (IS_ERR(trans)) { 211 ret = PTR_ERR(trans); 212 goto out; 213 } 214 215 ret = btrfs_uuid_tree_remove(trans, uuid, type, subid); 216 btrfs_end_transaction(trans); 217 218 out: 219 return ret; 220 } 221 222 /* 223 * Check if there's an matching subvolume for given UUID 224 * 225 * Return: 226 * 0 check succeeded, the entry is not outdated 227 * > 0 if the check failed, the caller should remove the entry 228 * < 0 if an error occurred 229 */ 230 static int btrfs_check_uuid_tree_entry(struct btrfs_fs_info *fs_info, 231 const u8 *uuid, u8 type, u64 subvolid) 232 { 233 int ret = 0; 234 struct btrfs_root *subvol_root; 235 236 if (type != BTRFS_UUID_KEY_SUBVOL && 237 type != BTRFS_UUID_KEY_RECEIVED_SUBVOL) 238 goto out; 239 240 subvol_root = btrfs_get_fs_root(fs_info, subvolid, true); 241 if (IS_ERR(subvol_root)) { 242 ret = PTR_ERR(subvol_root); 243 if (ret == -ENOENT) 244 ret = 1; 245 goto out; 246 } 247 248 switch (type) { 249 case BTRFS_UUID_KEY_SUBVOL: 250 if (memcmp(uuid, subvol_root->root_item.uuid, BTRFS_UUID_SIZE)) 251 ret = 1; 252 break; 253 case BTRFS_UUID_KEY_RECEIVED_SUBVOL: 254 if (memcmp(uuid, subvol_root->root_item.received_uuid, 255 BTRFS_UUID_SIZE)) 256 ret = 1; 257 break; 258 } 259 btrfs_put_root(subvol_root); 260 out: 261 return ret; 262 } 263 264 int btrfs_uuid_tree_iterate(struct btrfs_fs_info *fs_info) 265 { 266 struct btrfs_root *root = fs_info->uuid_root; 267 struct btrfs_key key; 268 BTRFS_PATH_AUTO_FREE(path); 269 int ret = 0; 270 struct extent_buffer *leaf; 271 int slot; 272 u32 item_size; 273 unsigned long offset; 274 275 path = btrfs_alloc_path(); 276 if (!path) 277 return -ENOMEM; 278 279 key.objectid = 0; 280 key.type = 0; 281 key.offset = 0; 282 283 again_search_slot: 284 ret = btrfs_search_forward(root, &key, path, BTRFS_OLDEST_GENERATION); 285 if (ret < 0) 286 return ret; 287 if (ret > 0) 288 return 0; 289 290 while (1) { 291 if (btrfs_fs_closing(fs_info)) 292 return -EINTR; 293 294 cond_resched(); 295 leaf = path->nodes[0]; 296 slot = path->slots[0]; 297 btrfs_item_key_to_cpu(leaf, &key, slot); 298 299 if (key.type != BTRFS_UUID_KEY_SUBVOL && 300 key.type != BTRFS_UUID_KEY_RECEIVED_SUBVOL) 301 goto skip; 302 303 offset = btrfs_item_ptr_offset(leaf, slot); 304 item_size = btrfs_item_size(leaf, slot); 305 if (!IS_ALIGNED(item_size, sizeof(u64))) { 306 btrfs_warn(fs_info, 307 "uuid item with illegal size %lu!", 308 (unsigned long)item_size); 309 goto skip; 310 } 311 while (item_size) { 312 u8 uuid[BTRFS_UUID_SIZE]; 313 __le64 subid_le; 314 u64 subid_cpu; 315 316 put_unaligned_le64(key.objectid, uuid); 317 put_unaligned_le64(key.offset, uuid + sizeof(u64)); 318 read_extent_buffer(leaf, &subid_le, offset, 319 sizeof(subid_le)); 320 subid_cpu = le64_to_cpu(subid_le); 321 ret = btrfs_check_uuid_tree_entry(fs_info, uuid, 322 key.type, subid_cpu); 323 if (ret < 0) 324 return ret; 325 if (ret > 0) { 326 btrfs_release_path(path); 327 ret = btrfs_uuid_iter_rem(root, uuid, key.type, 328 subid_cpu); 329 if (ret == 0) { 330 /* 331 * this might look inefficient, but the 332 * justification is that it is an 333 * exception that check_func returns 1, 334 * and that in the regular case only one 335 * entry per UUID exists. 336 */ 337 goto again_search_slot; 338 } 339 if (ret < 0 && ret != -ENOENT) 340 return ret; 341 key.offset++; 342 goto again_search_slot; 343 } 344 item_size -= sizeof(subid_le); 345 offset += sizeof(subid_le); 346 } 347 348 skip: 349 ret = btrfs_next_item(root, path); 350 if (ret == 0) 351 continue; 352 else if (ret > 0) 353 ret = 0; 354 break; 355 } 356 357 return ret; 358 } 359 360 int btrfs_uuid_scan_kthread(void *data) 361 { 362 struct btrfs_fs_info *fs_info = data; 363 struct btrfs_root *root = fs_info->tree_root; 364 struct btrfs_key key; 365 struct btrfs_path *path = NULL; 366 int ret = 0; 367 struct extent_buffer *eb; 368 int slot; 369 struct btrfs_root_item root_item; 370 u32 item_size; 371 struct btrfs_trans_handle *trans = NULL; 372 bool closing = false; 373 374 path = btrfs_alloc_path(); 375 if (!path) { 376 ret = -ENOMEM; 377 goto out; 378 } 379 380 key.objectid = 0; 381 key.type = BTRFS_ROOT_ITEM_KEY; 382 key.offset = 0; 383 384 while (1) { 385 if (btrfs_fs_closing(fs_info)) { 386 closing = true; 387 break; 388 } 389 ret = btrfs_search_forward(root, &key, path, 390 BTRFS_OLDEST_GENERATION); 391 if (ret) { 392 if (ret > 0) 393 ret = 0; 394 break; 395 } 396 397 if (key.type != BTRFS_ROOT_ITEM_KEY || 398 (key.objectid < BTRFS_FIRST_FREE_OBJECTID && 399 key.objectid != BTRFS_FS_TREE_OBJECTID) || 400 key.objectid > BTRFS_LAST_FREE_OBJECTID) 401 goto skip; 402 403 eb = path->nodes[0]; 404 slot = path->slots[0]; 405 item_size = btrfs_item_size(eb, slot); 406 if (item_size < sizeof(root_item)) 407 goto skip; 408 409 read_extent_buffer(eb, &root_item, 410 btrfs_item_ptr_offset(eb, slot), 411 (int)sizeof(root_item)); 412 if (btrfs_root_refs(&root_item) == 0) 413 goto skip; 414 415 if (!btrfs_is_empty_uuid(root_item.uuid) || 416 !btrfs_is_empty_uuid(root_item.received_uuid)) { 417 if (trans) 418 goto update_tree; 419 420 btrfs_release_path(path); 421 /* 422 * 1 - subvol uuid item 423 * 1 - received_subvol uuid item 424 */ 425 trans = btrfs_start_transaction(fs_info->uuid_root, 2); 426 if (IS_ERR(trans)) { 427 ret = PTR_ERR(trans); 428 break; 429 } 430 continue; 431 } else { 432 goto skip; 433 } 434 update_tree: 435 btrfs_release_path(path); 436 if (!btrfs_is_empty_uuid(root_item.uuid)) { 437 ret = btrfs_uuid_tree_add(trans, root_item.uuid, 438 BTRFS_UUID_KEY_SUBVOL, 439 key.objectid); 440 if (ret < 0) { 441 btrfs_warn(fs_info, "uuid_tree_add failed %d", 442 ret); 443 break; 444 } 445 } 446 447 if (!btrfs_is_empty_uuid(root_item.received_uuid)) { 448 ret = btrfs_uuid_tree_add(trans, 449 root_item.received_uuid, 450 BTRFS_UUID_KEY_RECEIVED_SUBVOL, 451 key.objectid); 452 if (ret < 0) { 453 btrfs_warn(fs_info, "uuid_tree_add failed %d", 454 ret); 455 break; 456 } 457 } 458 459 skip: 460 btrfs_release_path(path); 461 if (trans) { 462 ret = btrfs_end_transaction(trans); 463 trans = NULL; 464 if (ret) 465 break; 466 } 467 468 if (key.offset < (u64)-1) { 469 key.offset++; 470 } else if (key.type < BTRFS_ROOT_ITEM_KEY) { 471 key.offset = 0; 472 key.type = BTRFS_ROOT_ITEM_KEY; 473 } else if (key.objectid < (u64)-1) { 474 key.offset = 0; 475 key.type = BTRFS_ROOT_ITEM_KEY; 476 key.objectid++; 477 } else { 478 break; 479 } 480 cond_resched(); 481 } 482 483 out: 484 btrfs_free_path(path); 485 if (trans && !IS_ERR(trans)) 486 btrfs_end_transaction(trans); 487 if (ret) 488 btrfs_warn(fs_info, "btrfs_uuid_scan_kthread failed %d", ret); 489 else if (!closing) 490 set_bit(BTRFS_FS_UPDATE_UUID_TREE_GEN, &fs_info->flags); 491 up(&fs_info->uuid_tree_rescan_sem); 492 return 0; 493 } 494 495 int btrfs_create_uuid_tree(struct btrfs_fs_info *fs_info) 496 { 497 struct btrfs_trans_handle *trans; 498 struct btrfs_root *tree_root = fs_info->tree_root; 499 struct btrfs_root *uuid_root; 500 struct task_struct *task; 501 int ret; 502 503 /* 504 * 1 - root node 505 * 1 - root item 506 */ 507 trans = btrfs_start_transaction(tree_root, 2); 508 if (IS_ERR(trans)) 509 return PTR_ERR(trans); 510 511 uuid_root = btrfs_create_tree(trans, BTRFS_UUID_TREE_OBJECTID); 512 if (IS_ERR(uuid_root)) { 513 ret = PTR_ERR(uuid_root); 514 btrfs_abort_transaction(trans, ret); 515 btrfs_end_transaction(trans); 516 return ret; 517 } 518 519 fs_info->uuid_root = uuid_root; 520 521 ret = btrfs_commit_transaction(trans); 522 if (ret) 523 return ret; 524 525 down(&fs_info->uuid_tree_rescan_sem); 526 task = kthread_run(btrfs_uuid_scan_kthread, fs_info, "btrfs-uuid"); 527 if (IS_ERR(task)) { 528 /* fs_info->update_uuid_tree_gen remains 0 in all error case */ 529 btrfs_warn(fs_info, "failed to start uuid_scan task"); 530 up(&fs_info->uuid_tree_rescan_sem); 531 return PTR_ERR(task); 532 } 533 534 return 0; 535 } 536