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