fs/btrfs/uuid-tree.c

   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         btrfs_mark_buffer_dirty(trans, eb);
 144
 145 out:
 146         btrfs_free_path(path);
 147         return ret;
 148 }
 149
 150 int btrfs_uuid_tree_remove(struct btrfs_trans_handle *trans, const u8 *uuid, u8 type,
 151                         u64 subid)
 152 {
 153         struct btrfs_fs_info *fs_info = trans->fs_info;
 154         struct btrfs_root *uuid_root = fs_info->uuid_root;
 155         int ret;
 156         struct btrfs_path *path = NULL;
 157         struct btrfs_key key;
 158         struct extent_buffer *eb;
 159         int slot;
 160         unsigned long offset;
 161         u32 item_size;
 162         unsigned long move_dst;
 163         unsigned long move_src;
 164         unsigned long move_len;
 165
 166         if (WARN_ON_ONCE(!uuid_root)) {
 167                 ret = -EINVAL;
 168                 goto out;
 169         }
 170
 171         btrfs_uuid_to_key(uuid, type, &key);
 172
 173         path = btrfs_alloc_path();
 174         if (!path) {
 175                 ret = -ENOMEM;
 176                 goto out;
 177         }
 178
 179         ret = btrfs_search_slot(trans, uuid_root, &key, path, -1, 1);
 180         if (ret < 0) {
 181                 btrfs_warn(fs_info, "error %d while searching for uuid item!",
 182                            ret);
 183                 goto out;
 184         }
 185         if (ret > 0) {
 186                 ret = -ENOENT;
 187                 goto out;
 188         }
 189
 190         eb = path->nodes[0];
 191         slot = path->slots[0];
 192         offset = btrfs_item_ptr_offset(eb, slot);
 193         item_size = btrfs_item_size(eb, slot);
 194         if (!IS_ALIGNED(item_size, sizeof(u64))) {
 195                 btrfs_warn(fs_info, "uuid item with illegal size %lu!",
 196                            (unsigned long)item_size);
 197                 ret = -ENOENT;
 198                 goto out;
 199         }
 200         while (item_size) {
 201                 __le64 read_subid;
 202
 203                 read_extent_buffer(eb, &read_subid, offset, sizeof(read_subid));
 204                 if (le64_to_cpu(read_subid) == subid)
 205                         break;
 206                 offset += sizeof(read_subid);
 207                 item_size -= sizeof(read_subid);
 208         }
 209
 210         if (!item_size) {
 211                 ret = -ENOENT;
 212                 goto out;
 213         }
 214
 215         item_size = btrfs_item_size(eb, slot);
 216         if (item_size == sizeof(subid)) {
 217                 ret = btrfs_del_item(trans, uuid_root, path);
 218                 goto out;
 219         }
 220
 221         move_dst = offset;
 222         move_src = offset + sizeof(subid);
 223         move_len = item_size - (move_src - btrfs_item_ptr_offset(eb, slot));
 224         memmove_extent_buffer(eb, move_dst, move_src, move_len);
 225         btrfs_truncate_item(trans, path, item_size - sizeof(subid), 1);
 226
 227 out:
 228         btrfs_free_path(path);
 229         return ret;
 230 }
 231
 232 static int btrfs_uuid_iter_rem(struct btrfs_root *uuid_root, u8 *uuid, u8 type,
 233                                u64 subid)
 234 {
 235         struct btrfs_trans_handle *trans;
 236         int ret;
 237
 238         /* 1 - for the uuid item */
 239         trans = btrfs_start_transaction(uuid_root, 1);
 240         if (IS_ERR(trans)) {
 241                 ret = PTR_ERR(trans);
 242                 goto out;
 243         }
 244
 245         ret = btrfs_uuid_tree_remove(trans, uuid, type, subid);
 246         btrfs_end_transaction(trans);
 247
 248 out:
 249         return ret;
 250 }
 251
 252 /*
 253  * Check if there's an matching subvolume for given UUID
 254  *
 255  * Return:
 256  * 0    check succeeded, the entry is not outdated
 257  * > 0  if the check failed, the caller should remove the entry
 258  * < 0  if an error occurred
 259  */
 260 static int btrfs_check_uuid_tree_entry(struct btrfs_fs_info *fs_info,
 261                                        const u8 *uuid, u8 type, u64 subvolid)
 262 {
 263         int ret = 0;
 264         struct btrfs_root *subvol_root;
 265
 266         if (type != BTRFS_UUID_KEY_SUBVOL &&
 267             type != BTRFS_UUID_KEY_RECEIVED_SUBVOL)
 268                 goto out;
 269
 270         subvol_root = btrfs_get_fs_root(fs_info, subvolid, true);
 271         if (IS_ERR(subvol_root)) {
 272                 ret = PTR_ERR(subvol_root);
 273                 if (ret == -ENOENT)
 274                         ret = 1;
 275                 goto out;
 276         }
 277
 278         switch (type) {
 279         case BTRFS_UUID_KEY_SUBVOL:
 280                 if (memcmp(uuid, subvol_root->root_item.uuid, BTRFS_UUID_SIZE))
 281                         ret = 1;
 282                 break;
 283         case BTRFS_UUID_KEY_RECEIVED_SUBVOL:
 284                 if (memcmp(uuid, subvol_root->root_item.received_uuid,
 285                            BTRFS_UUID_SIZE))
 286                         ret = 1;
 287                 break;
 288         }
 289         btrfs_put_root(subvol_root);
 290 out:
 291         return ret;
 292 }
 293
 294 int btrfs_uuid_tree_iterate(struct btrfs_fs_info *fs_info)
 295 {
 296         struct btrfs_root *root = fs_info->uuid_root;
 297         struct btrfs_key key;
 298         struct btrfs_path *path;
 299         int ret = 0;
 300         struct extent_buffer *leaf;
 301         int slot;
 302         u32 item_size;
 303         unsigned long offset;
 304
 305         path = btrfs_alloc_path();
 306         if (!path) {
 307                 ret = -ENOMEM;
 308                 goto out;
 309         }
 310
 311         key.objectid = 0;
 312         key.type = 0;
 313         key.offset = 0;
 314
 315 again_search_slot:
 316         ret = btrfs_search_forward(root, &key, path, BTRFS_OLDEST_GENERATION);
 317         if (ret) {
 318                 if (ret > 0)
 319                         ret = 0;
 320                 goto out;
 321         }
 322
 323         while (1) {
 324                 if (btrfs_fs_closing(fs_info)) {
 325                         ret = -EINTR;
 326                         goto out;
 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                                 goto out;
 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                                         goto out;
 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 out:
 392         btrfs_free_path(path);
 393         return ret;
 394 }
 395
 396 int btrfs_uuid_scan_kthread(void *data)
 397 {
 398         struct btrfs_fs_info *fs_info = data;
 399         struct btrfs_root *root = fs_info->tree_root;
 400         struct btrfs_key key;
 401         struct btrfs_path *path = NULL;
 402         int ret = 0;
 403         struct extent_buffer *eb;
 404         int slot;
 405         struct btrfs_root_item root_item;
 406         u32 item_size;
 407         struct btrfs_trans_handle *trans = NULL;
 408         bool closing = false;
 409
 410         path = btrfs_alloc_path();
 411         if (!path) {
 412                 ret = -ENOMEM;
 413                 goto out;
 414         }
 415
 416         key.objectid = 0;
 417         key.type = BTRFS_ROOT_ITEM_KEY;
 418         key.offset = 0;
 419
 420         while (1) {
 421                 if (btrfs_fs_closing(fs_info)) {
 422                         closing = true;
 423                         break;
 424                 }
 425                 ret = btrfs_search_forward(root, &key, path,
 426                                 BTRFS_OLDEST_GENERATION);
 427                 if (ret) {
 428                         if (ret > 0)
 429                                 ret = 0;
 430                         break;
 431                 }
 432
 433                 if (key.type != BTRFS_ROOT_ITEM_KEY ||
 434                     (key.objectid < BTRFS_FIRST_FREE_OBJECTID &&
 435                      key.objectid != BTRFS_FS_TREE_OBJECTID) ||
 436                     key.objectid > BTRFS_LAST_FREE_OBJECTID)
 437                         goto skip;
 438
 439                 eb = path->nodes[0];
 440                 slot = path->slots[0];
 441                 item_size = btrfs_item_size(eb, slot);
 442                 if (item_size < sizeof(root_item))
 443                         goto skip;
 444
 445                 read_extent_buffer(eb, &root_item,
 446                                    btrfs_item_ptr_offset(eb, slot),
 447                                    (int)sizeof(root_item));
 448                 if (btrfs_root_refs(&root_item) == 0)
 449                         goto skip;
 450
 451                 if (!btrfs_is_empty_uuid(root_item.uuid) ||
 452                     !btrfs_is_empty_uuid(root_item.received_uuid)) {
 453                         if (trans)
 454                                 goto update_tree;
 455
 456                         btrfs_release_path(path);
 457                         /*
 458                          * 1 - subvol uuid item
 459                          * 1 - received_subvol uuid item
 460                          */
 461                         trans = btrfs_start_transaction(fs_info->uuid_root, 2);
 462                         if (IS_ERR(trans)) {
 463                                 ret = PTR_ERR(trans);
 464                                 break;
 465                         }
 466                         continue;
 467                 } else {
 468                         goto skip;
 469                 }
 470 update_tree:
 471                 btrfs_release_path(path);
 472                 if (!btrfs_is_empty_uuid(root_item.uuid)) {
 473                         ret = btrfs_uuid_tree_add(trans, root_item.uuid,
 474                                                   BTRFS_UUID_KEY_SUBVOL,
 475                                                   key.objectid);
 476                         if (ret < 0) {
 477                                 btrfs_warn(fs_info, "uuid_tree_add failed %d",
 478                                         ret);
 479                                 break;
 480                         }
 481                 }
 482
 483                 if (!btrfs_is_empty_uuid(root_item.received_uuid)) {
 484                         ret = btrfs_uuid_tree_add(trans,
 485                                                   root_item.received_uuid,
 486                                                  BTRFS_UUID_KEY_RECEIVED_SUBVOL,
 487                                                   key.objectid);
 488                         if (ret < 0) {
 489                                 btrfs_warn(fs_info, "uuid_tree_add failed %d",
 490                                         ret);
 491                                 break;
 492                         }
 493                 }
 494
 495 skip:
 496                 btrfs_release_path(path);
 497                 if (trans) {
 498                         ret = btrfs_end_transaction(trans);
 499                         trans = NULL;
 500                         if (ret)
 501                                 break;
 502                 }
 503
 504                 if (key.offset < (u64)-1) {
 505                         key.offset++;
 506                 } else if (key.type < BTRFS_ROOT_ITEM_KEY) {
 507                         key.offset = 0;
 508                         key.type = BTRFS_ROOT_ITEM_KEY;
 509                 } else if (key.objectid < (u64)-1) {
 510                         key.offset = 0;
 511                         key.type = BTRFS_ROOT_ITEM_KEY;
 512                         key.objectid++;
 513                 } else {
 514                         break;
 515                 }
 516                 cond_resched();
 517         }
 518
 519 out:
 520         btrfs_free_path(path);
 521         if (trans && !IS_ERR(trans))
 522                 btrfs_end_transaction(trans);
 523         if (ret)
 524                 btrfs_warn(fs_info, "btrfs_uuid_scan_kthread failed %d", ret);
 525         else if (!closing)
 526                 set_bit(BTRFS_FS_UPDATE_UUID_TREE_GEN, &fs_info->flags);
 527         up(&fs_info->uuid_tree_rescan_sem);
 528         return 0;
 529 }
 530
 531 int btrfs_create_uuid_tree(struct btrfs_fs_info *fs_info)
 532 {
 533         struct btrfs_trans_handle *trans;
 534         struct btrfs_root *tree_root = fs_info->tree_root;
 535         struct btrfs_root *uuid_root;
 536         struct task_struct *task;
 537         int ret;
 538
 539         /*
 540          * 1 - root node
 541          * 1 - root item
 542          */
 543         trans = btrfs_start_transaction(tree_root, 2);
 544         if (IS_ERR(trans))
 545                 return PTR_ERR(trans);
 546
 547         uuid_root = btrfs_create_tree(trans, BTRFS_UUID_TREE_OBJECTID);
 548         if (IS_ERR(uuid_root)) {
 549                 ret = PTR_ERR(uuid_root);
 550                 btrfs_abort_transaction(trans, ret);
 551                 btrfs_end_transaction(trans);
 552                 return ret;
 553         }
 554
 555         fs_info->uuid_root = uuid_root;
 556
 557         ret = btrfs_commit_transaction(trans);
 558         if (ret)
 559                 return ret;
 560
 561         down(&fs_info->uuid_tree_rescan_sem);
 562         task = kthread_run(btrfs_uuid_scan_kthread, fs_info, "btrfs-uuid");
 563         if (IS_ERR(task)) {
 564                 /* fs_info->update_uuid_tree_gen remains 0 in all error case */
 565                 btrfs_warn(fs_info, "failed to start uuid_scan task");
 566                 up(&fs_info->uuid_tree_rescan_sem);
 567                 return PTR_ERR(task);
 568         }
 569
 570         return 0;
 571 }