send-utils.c

   1 /*
   2  * Copyright (C) 2012 Alexander Block.  All rights reserved.
   3  *
   4  * This program is free software; you can redistribute it and/or
   5  * modify it under the terms of the GNU General Public
   6  * License v2 as published by the Free Software Foundation.
   7  *
   8  * This program is distributed in the hope that it will be useful,
   9  * but WITHOUT ANY WARRANTY; without even the implied warranty of
  10  * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the GNU
  11  * General Public License for more details.
  12  *
  13  * You should have received a copy of the GNU General Public
  14  * License along with this program; if not, write to the
  15  * Free Software Foundation, Inc., 59 Temple Place - Suite 330,
  16  * Boston, MA 021110-1307, USA.
  17  */
  18
  19 #include <unistd.h>
  20 #include <fcntl.h>
  21 #include <sys/ioctl.h>
  22 #include <uuid/uuid.h>
  23
  24 #include "ctree.h"
  25 #include "send-utils.h"
  26 #include "ioctl.h"
  27 #include "btrfs-list.h"
  28
  29 static int btrfs_subvolid_resolve_sub(int fd, char *path, size_t *path_len,
  30                                       u64 subvol_id);
  31
  32 static int btrfs_get_root_id_by_sub_path(int mnt_fd, const char *sub_path,
  33                                          u64 *root_id)
  34 {
  35         int ret;
  36         int subvol_fd;
  37
  38         subvol_fd = openat(mnt_fd, sub_path, O_RDONLY);
  39         if (subvol_fd < 0) {
  40                 ret = -errno;
  41                 fprintf(stderr, "ERROR: open %s failed. %s\n", sub_path,
  42                         strerror(-ret));
  43                 return ret;
  44         }
  45
  46         ret = btrfs_list_get_path_rootid(subvol_fd, root_id);
  47         close(subvol_fd);
  48         return ret;
  49 }
  50
  51 static int btrfs_read_root_item_raw(int mnt_fd, u64 root_id, size_t buf_len,
  52                                     u32 *read_len, void *buf)
  53 {
  54         int ret;
  55         struct btrfs_ioctl_search_args args;
  56         struct btrfs_ioctl_search_key *sk = &args.key;
  57         struct btrfs_ioctl_search_header *sh;
  58         unsigned long off = 0;
  59         int found = 0;
  60         int i;
  61
  62         *read_len = 0;
  63         memset(&args, 0, sizeof(args));
  64
  65         sk->tree_id = BTRFS_ROOT_TREE_OBJECTID;
  66
  67         /*
  68          * there may be more than one ROOT_ITEM key if there are
  69          * snapshots pending deletion, we have to loop through
  70          * them.
  71          */
  72         sk->min_objectid = root_id;
  73         sk->max_objectid = root_id;
  74         sk->max_type = BTRFS_ROOT_ITEM_KEY;
  75         sk->min_type = BTRFS_ROOT_ITEM_KEY;
  76         sk->max_offset = (u64)-1;
  77         sk->max_transid = (u64)-1;
  78         sk->nr_items = 4096;
  79
  80         while (1) {
  81                 ret = ioctl(mnt_fd, BTRFS_IOC_TREE_SEARCH, &args);
  82                 if (ret < 0) {
  83                         fprintf(stderr,
  84                                 "ERROR: can't perform the search - %s\n",
  85                                 strerror(errno));
  86                         return 0;
  87                 }
  88                 /* the ioctl returns the number of item it found in nr_items */
  89                 if (sk->nr_items == 0)
  90                         break;
  91
  92                 off = 0;
  93                 for (i = 0; i < sk->nr_items; i++) {
  94                         struct btrfs_root_item *item;
  95                         sh = (struct btrfs_ioctl_search_header *)(args.buf +
  96                                                                   off);
  97
  98                         off += sizeof(*sh);
  99                         item = (struct btrfs_root_item *)(args.buf + off);
 100                         off += sh->len;
 101
 102                         sk->min_objectid = sh->objectid;
 103                         sk->min_type = sh->type;
 104                         sk->min_offset = sh->offset;
 105
 106                         if (sh->objectid > root_id)
 107                                 break;
 108
 109                         if (sh->objectid == root_id &&
 110                             sh->type == BTRFS_ROOT_ITEM_KEY) {
 111                                 if (sh->len > buf_len) {
 112                                         /* btrfs-progs is too old for kernel */
 113                                         fprintf(stderr,
 114                                                 "ERROR: buf for read_root_item_raw() is too small, get newer btrfs tools!\n");
 115                                         return -EOVERFLOW;
 116                                 }
 117                                 memcpy(buf, item, sh->len);
 118                                 *read_len = sh->len;
 119                                 found = 1;
 120                         }
 121                 }
 122                 if (sk->min_offset < (u64)-1)
 123                         sk->min_offset++;
 124                 else
 125                         break;
 126
 127                 if (sk->min_type != BTRFS_ROOT_ITEM_KEY ||
 128                     sk->min_objectid != root_id)
 129                         break;
 130         }
 131
 132         return found ? 0 : -ENOENT;
 133 }
 134
 135 /*
 136  * Read a root item from the tree. In case we detect a root item smaller then
 137  * sizeof(root_item), we know it's an old version of the root structure and
 138  * initialize all new fields to zero. The same happens if we detect mismatching
 139  * generation numbers as then we know the root was once mounted with an older
 140  * kernel that was not aware of the root item structure change.
 141  */
 142 static int btrfs_read_root_item(int mnt_fd, u64 root_id,
 143                                 struct btrfs_root_item *item)
 144 {
 145         int ret;
 146         u32 read_len;
 147
 148         ret = btrfs_read_root_item_raw(mnt_fd, root_id, sizeof(*item),
 149                                        &read_len, item);
 150         if (ret)
 151                 return ret;
 152
 153         if (read_len < sizeof(*item) ||
 154             btrfs_root_generation(item) != btrfs_root_generation_v2(item))
 155                 memset(&item->generation_v2, 0,
 156                         sizeof(*item) - offsetof(struct btrfs_root_item,
 157                                                  generation_v2));
 158
 159         return 0;
 160 }
 161
 162 static struct rb_node *tree_insert(struct rb_root *root,
 163                                    struct subvol_info *si,
 164                                    enum subvol_search_type type)
 165 {
 166         struct rb_node **p = &root->rb_node;
 167         struct rb_node *parent = NULL;
 168         struct subvol_info *entry;
 169         __s64 comp;
 170
 171         while (*p) {
 172                 parent = *p;
 173                 if (type == subvol_search_by_received_uuid) {
 174                         entry = rb_entry(parent, struct subvol_info,
 175                                         rb_received_node);
 176
 177                         comp = memcmp(entry->received_uuid, si->received_uuid,
 178                                         BTRFS_UUID_SIZE);
 179                         if (!comp) {
 180                                 if (entry->stransid < si->stransid)
 181                                         comp = -1;
 182                                 else if (entry->stransid > si->stransid)
 183                                         comp = 1;
 184                                 else
 185                                         comp = 0;
 186                         }
 187                 } else if (type == subvol_search_by_uuid) {
 188                         entry = rb_entry(parent, struct subvol_info,
 189                                         rb_local_node);
 190                         comp = memcmp(entry->uuid, si->uuid, BTRFS_UUID_SIZE);
 191                 } else if (type == subvol_search_by_root_id) {
 192                         entry = rb_entry(parent, struct subvol_info,
 193                                         rb_root_id_node);
 194                         comp = entry->root_id - si->root_id;
 195                 } else if (type == subvol_search_by_path) {
 196                         entry = rb_entry(parent, struct subvol_info,
 197                                         rb_path_node);
 198                         comp = strcmp(entry->path, si->path);
 199                 } else {
 200                         BUG();
 201                 }
 202
 203                 if (comp < 0)
 204                         p = &(*p)->rb_left;
 205                 else if (comp > 0)
 206                         p = &(*p)->rb_right;
 207                 else
 208                         return parent;
 209         }
 210
 211         if (type == subvol_search_by_received_uuid) {
 212                 rb_link_node(&si->rb_received_node, parent, p);
 213                 rb_insert_color(&si->rb_received_node, root);
 214         } else if (type == subvol_search_by_uuid) {
 215                 rb_link_node(&si->rb_local_node, parent, p);
 216                 rb_insert_color(&si->rb_local_node, root);
 217         } else if (type == subvol_search_by_root_id) {
 218                 rb_link_node(&si->rb_root_id_node, parent, p);
 219                 rb_insert_color(&si->rb_root_id_node, root);
 220         } else if (type == subvol_search_by_path) {
 221                 rb_link_node(&si->rb_path_node, parent, p);
 222                 rb_insert_color(&si->rb_path_node, root);
 223         }
 224         return NULL;
 225 }
 226
 227 int btrfs_subvolid_resolve(int fd, char *path, size_t path_len, u64 subvol_id)
 228 {
 229         if (path_len < 1)
 230                 return -EOVERFLOW;
 231         path[0] = '\0';
 232         path_len--;
 233         path[path_len] = '\0';
 234         return btrfs_subvolid_resolve_sub(fd, path, &path_len, subvol_id);
 235 }
 236
 237 static int btrfs_subvolid_resolve_sub(int fd, char *path, size_t *path_len,
 238                                       u64 subvol_id)
 239 {
 240         int ret;
 241         struct btrfs_ioctl_search_args search_arg;
 242         struct btrfs_ioctl_ino_lookup_args ino_lookup_arg;
 243         struct btrfs_ioctl_search_header *search_header;
 244         struct btrfs_root_ref *backref_item;
 245
 246         if (subvol_id == BTRFS_FS_TREE_OBJECTID) {
 247                 if (*path_len < 1)
 248                         return -EOVERFLOW;
 249                 *path = '\0';
 250                 (*path_len)--;
 251                 return 0;
 252         }
 253
 254         memset(&search_arg, 0, sizeof(search_arg));
 255         search_arg.key.tree_id = BTRFS_ROOT_TREE_OBJECTID;
 256         search_arg.key.min_objectid = subvol_id;
 257         search_arg.key.max_objectid = subvol_id;
 258         search_arg.key.min_type = BTRFS_ROOT_BACKREF_KEY;
 259         search_arg.key.max_type = BTRFS_ROOT_BACKREF_KEY;
 260         search_arg.key.max_offset = (u64)-1;
 261         search_arg.key.max_transid = (u64)-1;
 262         search_arg.key.nr_items = 1;
 263         ret = ioctl(fd, BTRFS_IOC_TREE_SEARCH, &search_arg);
 264         if (ret) {
 265                 fprintf(stderr,
 266                         "ioctl(BTRFS_IOC_TREE_SEARCH, subvol_id %llu) ret=%d, error: %s\n",
 267                         (unsigned long long)subvol_id, ret, strerror(errno));
 268                 return ret;
 269         }
 270
 271         if (search_arg.key.nr_items < 1) {
 272                 fprintf(stderr,
 273                         "failed to lookup subvol_id %llu!\n",
 274                         (unsigned long long)subvol_id);
 275                 return -ENOENT;
 276         }
 277         search_header = (struct btrfs_ioctl_search_header *)search_arg.buf;
 278         backref_item = (struct btrfs_root_ref *)(search_header + 1);
 279         if (search_header->offset != BTRFS_FS_TREE_OBJECTID) {
 280                 int sub_ret;
 281
 282                 sub_ret = btrfs_subvolid_resolve_sub(fd, path, path_len,
 283                                                      search_header->offset);
 284                 if (sub_ret)
 285                         return sub_ret;
 286                 if (*path_len < 1)
 287                         return -EOVERFLOW;
 288                 strcat(path, "/");
 289                 (*path_len)--;
 290         }
 291
 292         if (btrfs_stack_root_ref_dirid(backref_item) !=
 293             BTRFS_FIRST_FREE_OBJECTID) {
 294                 int len;
 295
 296                 memset(&ino_lookup_arg, 0, sizeof(ino_lookup_arg));
 297                 ino_lookup_arg.treeid = search_header->offset;
 298                 ino_lookup_arg.objectid =
 299                         btrfs_stack_root_ref_dirid(backref_item);
 300                 ret = ioctl(fd, BTRFS_IOC_INO_LOOKUP, &ino_lookup_arg);
 301                 if (ret) {
 302                         fprintf(stderr,
 303                                 "ioctl(BTRFS_IOC_INO_LOOKUP) ret=%d, error: %s\n",
 304                                 ret, strerror(errno));
 305                         return ret;
 306                 }
 307
 308                 len = strlen(ino_lookup_arg.name);
 309                 if (*path_len < len)
 310                         return -EOVERFLOW;
 311                 strcat(path, ino_lookup_arg.name);
 312                 (*path_len) -= len;
 313         }
 314
 315         if (*path_len < btrfs_stack_root_ref_name_len(backref_item))
 316                 return -EOVERFLOW;
 317         strncat(path, (char *)(backref_item + 1),
 318                 btrfs_stack_root_ref_name_len(backref_item));
 319         (*path_len) -= btrfs_stack_root_ref_name_len(backref_item);
 320         return 0;
 321 }
 322
 323 static int count_bytes(void *buf, int len, char b)
 324 {
 325         int cnt = 0;
 326         int i;
 327
 328         for (i = 0; i < len; i++) {
 329                 if (((char *)buf)[i] == b)
 330                         cnt++;
 331         }
 332         return cnt;
 333 }
 334
 335 void subvol_uuid_search_add(struct subvol_uuid_search *s,
 336                             struct subvol_info *si)
 337 {
 338         int cnt;
 339
 340         tree_insert(&s->root_id_subvols, si, subvol_search_by_root_id);
 341         tree_insert(&s->path_subvols, si, subvol_search_by_path);
 342
 343         cnt = count_bytes(si->uuid, BTRFS_UUID_SIZE, 0);
 344         if (cnt != BTRFS_UUID_SIZE)
 345                 tree_insert(&s->local_subvols, si, subvol_search_by_uuid);
 346         cnt = count_bytes(si->received_uuid, BTRFS_UUID_SIZE, 0);
 347         if (cnt != BTRFS_UUID_SIZE)
 348                 tree_insert(&s->received_subvols, si,
 349                                 subvol_search_by_received_uuid);
 350 }
 351
 352 static struct subvol_info *tree_search(struct rb_root *root,
 353                                        u64 root_id, const u8 *uuid,
 354                                        u64 stransid, const char *path,
 355                                        enum subvol_search_type type)
 356 {
 357         struct rb_node *n = root->rb_node;
 358         struct subvol_info *entry;
 359         __s64 comp;
 360
 361         while (n) {
 362                 if (type == subvol_search_by_received_uuid) {
 363                         entry = rb_entry(n, struct subvol_info,
 364                                         rb_received_node);
 365                         comp = memcmp(entry->received_uuid, uuid,
 366                                         BTRFS_UUID_SIZE);
 367                         if (!comp) {
 368                                 if (entry->stransid < stransid)
 369                                         comp = -1;
 370                                 else if (entry->stransid > stransid)
 371                                         comp = 1;
 372                                 else
 373                                         comp = 0;
 374                         }
 375                 } else if (type == subvol_search_by_uuid) {
 376                         entry = rb_entry(n, struct subvol_info, rb_local_node);
 377                         comp = memcmp(entry->uuid, uuid, BTRFS_UUID_SIZE);
 378                 } else if (type == subvol_search_by_root_id) {
 379                         entry = rb_entry(n, struct subvol_info,
 380                                          rb_root_id_node);
 381                         comp = entry->root_id - root_id;
 382                 } else if (type == subvol_search_by_path) {
 383                         entry = rb_entry(n, struct subvol_info, rb_path_node);
 384                         comp = strcmp(entry->path, path);
 385                 } else {
 386                         BUG();
 387                 }
 388                 if (comp < 0)
 389                         n = n->rb_left;
 390                 else if (comp > 0)
 391                         n = n->rb_right;
 392                 else
 393                         return entry;
 394         }
 395         return NULL;
 396 }
 397
 398 /*
 399  * this function will be only called if kernel dosen't support uuid tree.
 400  */
 401 static struct subvol_info *subvol_uuid_search_old(struct subvol_uuid_search *s,
 402                                        u64 root_id, const u8 *uuid, u64 transid,
 403                                        const char *path,
 404                                        enum subvol_search_type type)
 405 {
 406         struct rb_root *root;
 407         if (type == subvol_search_by_received_uuid)
 408                 root = &s->received_subvols;
 409         else if (type == subvol_search_by_uuid)
 410                 root = &s->local_subvols;
 411         else if (type == subvol_search_by_root_id)
 412                 root = &s->root_id_subvols;
 413         else if (type == subvol_search_by_path)
 414                 root = &s->path_subvols;
 415         else
 416                 return NULL;
 417         return tree_search(root, root_id, uuid, transid, path, type);
 418 }
 419
 420 struct subvol_info *subvol_uuid_search(struct subvol_uuid_search *s,
 421                                        u64 root_id, const u8 *uuid, u64 transid,
 422                                        const char *path,
 423                                        enum subvol_search_type type)
 424 {
 425         int ret = 0;
 426         struct btrfs_root_item root_item;
 427         struct subvol_info *info = NULL;
 428
 429         if (!s->uuid_tree_existed)
 430                 return subvol_uuid_search_old(s, root_id, uuid, transid,
 431                                              path, type);
 432         switch (type) {
 433         case subvol_search_by_received_uuid:
 434                 ret = btrfs_lookup_uuid_received_subvol_item(s->mnt_fd, uuid,
 435                                                              &root_id);
 436                 break;
 437         case subvol_search_by_uuid:
 438                 ret = btrfs_lookup_uuid_subvol_item(s->mnt_fd, uuid, &root_id);
 439                 break;
 440         case subvol_search_by_root_id:
 441                 break;
 442         case subvol_search_by_path:
 443                 ret = btrfs_get_root_id_by_sub_path(s->mnt_fd, path, &root_id);
 444                 break;
 445         default:
 446                 ret = -EINVAL;
 447                 break;
 448         }
 449
 450         if (ret)
 451                 goto out;
 452
 453         ret = btrfs_read_root_item(s->mnt_fd, root_id, &root_item);
 454         if (ret)
 455                 goto out;
 456
 457         info = calloc(1, sizeof(*info));
 458         info->root_id = root_id;
 459         memcpy(info->uuid, root_item.uuid, BTRFS_UUID_SIZE);
 460         memcpy(info->received_uuid, root_item.received_uuid, BTRFS_UUID_SIZE);
 461         memcpy(info->parent_uuid, root_item.parent_uuid, BTRFS_UUID_SIZE);
 462         info->ctransid = btrfs_root_ctransid(&root_item);
 463         info->otransid = btrfs_root_otransid(&root_item);
 464         info->stransid = btrfs_root_stransid(&root_item);
 465         info->rtransid = btrfs_root_rtransid(&root_item);
 466         if (type == subvol_search_by_path) {
 467                 info->path = strdup(path);
 468         } else {
 469                 info->path = malloc(BTRFS_PATH_NAME_MAX);
 470                 ret = btrfs_subvolid_resolve(s->mnt_fd, info->path,
 471                                              BTRFS_PATH_NAME_MAX, root_id);
 472         }
 473
 474 out:
 475         if (ret && info) {
 476                 free(info->path);
 477                 free(info);
 478                 info = NULL;
 479         }
 480
 481         return info;
 482 }
 483
 484 static int is_uuid_tree_supported(int fd)
 485 {
 486         int ret;
 487         struct btrfs_ioctl_search_args args;
 488         struct btrfs_ioctl_search_key *sk = &args.key;
 489
 490         memset(&args, 0, sizeof(args));
 491
 492         sk->tree_id = BTRFS_ROOT_TREE_OBJECTID;
 493
 494         sk->min_objectid = BTRFS_UUID_TREE_OBJECTID;
 495         sk->max_objectid = BTRFS_UUID_TREE_OBJECTID;
 496         sk->max_type = BTRFS_ROOT_ITEM_KEY;
 497         sk->min_type = BTRFS_ROOT_ITEM_KEY;
 498         sk->max_offset = (u64)-1;
 499         sk->max_transid = (u64)-1;
 500         sk->nr_items = 1;
 501
 502         ret = ioctl(fd, BTRFS_IOC_TREE_SEARCH, &args);
 503         if (ret < 0)
 504                 return ret;
 505
 506         /* the ioctl returns the number of item it found in nr_items */
 507         if (sk->nr_items == 0)
 508                 return 0;
 509
 510         return 1;
 511 }
 512
 513 /*
 514  * this function is mainly used to read all root items
 515  * it will be only used when we use older kernel which uuid
 516  * tree is not supported yet
 517  */
 518 int subvol_uuid_search_init(int mnt_fd, struct subvol_uuid_search *s)
 519 {
 520         int ret;
 521         struct btrfs_ioctl_search_args args;
 522         struct btrfs_ioctl_search_key *sk = &args.key;
 523         struct btrfs_ioctl_search_header *sh;
 524         struct btrfs_root_item *root_item_ptr;
 525         struct btrfs_root_item root_item;
 526         struct subvol_info *si = NULL;
 527         int root_item_valid = 0;
 528         unsigned long off = 0;
 529         int i;
 530         int e;
 531         char *path;
 532
 533         s->mnt_fd = mnt_fd;
 534
 535         s->root_id_subvols = RB_ROOT;
 536         s->local_subvols = RB_ROOT;
 537         s->received_subvols = RB_ROOT;
 538         s->path_subvols = RB_ROOT;
 539
 540         ret = is_uuid_tree_supported(mnt_fd);
 541         if (ret < 0) {
 542                 fprintf(stderr,
 543                         "ERROR: check if we support uuid tree fails- %s\n",
 544                         strerror(errno));
 545                 return ret;
 546         } else if (ret) {
 547                 /* uuid tree is supported */
 548                 s->uuid_tree_existed = 1;
 549                 return 0;
 550         }
 551         memset(&args, 0, sizeof(args));
 552
 553         sk->tree_id = BTRFS_ROOT_TREE_OBJECTID;
 554
 555         sk->max_objectid = (u64)-1;
 556         sk->max_offset = (u64)-1;
 557         sk->max_transid = (u64)-1;
 558         sk->min_type = BTRFS_ROOT_ITEM_KEY;
 559         sk->max_type = BTRFS_ROOT_BACKREF_KEY;
 560         sk->nr_items = 4096;
 561
 562         while (1) {
 563                 ret = ioctl(mnt_fd, BTRFS_IOC_TREE_SEARCH, &args);
 564                 e = errno;
 565                 if (ret < 0) {
 566                         fprintf(stderr, "ERROR: can't perform the search- %s\n",
 567                                 strerror(e));
 568                         return ret;
 569                 }
 570                 if (sk->nr_items == 0)
 571                         break;
 572
 573                 off = 0;
 574
 575                 for (i = 0; i < sk->nr_items; i++) {
 576                         sh = (struct btrfs_ioctl_search_header *)(args.buf +
 577                                                                   off);
 578                         off += sizeof(*sh);
 579
 580                         if ((sh->objectid != 5 &&
 581                             sh->objectid < BTRFS_FIRST_FREE_OBJECTID) ||
 582                             sh->objectid > BTRFS_LAST_FREE_OBJECTID)
 583                                 goto skip;
 584
 585                         if (sh->type == BTRFS_ROOT_ITEM_KEY) {
 586                                 /* older kernels don't have uuids+times */
 587                                 if (sh->len < sizeof(root_item)) {
 588                                         root_item_valid = 0;
 589                                         goto skip;
 590                                 }
 591                                 root_item_ptr = (struct btrfs_root_item *)
 592                                                 (args.buf + off);
 593                                 memcpy(&root_item, root_item_ptr,
 594                                                 sizeof(root_item));
 595                                 root_item_valid = 1;
 596                         } else if (sh->type == BTRFS_ROOT_BACKREF_KEY ||
 597                                    root_item_valid) {
 598                                 if (!root_item_valid)
 599                                         goto skip;
 600
 601                                 path = btrfs_list_path_for_root(mnt_fd,
 602                                                                 sh->objectid);
 603                                 if (!path)
 604                                         path = strdup("");
 605                                 if (IS_ERR(path)) {
 606                                         ret = PTR_ERR(path);
 607                                         fprintf(stderr, "ERROR: unable to "
 608                                                         "resolve path "
 609                                                         "for root %llu\n",
 610                                                         sh->objectid);
 611                                         goto out;
 612                                 }
 613
 614                                 si = calloc(1, sizeof(*si));
 615                                 si->root_id = sh->objectid;
 616                                 memcpy(si->uuid, root_item.uuid,
 617                                                 BTRFS_UUID_SIZE);
 618                                 memcpy(si->parent_uuid, root_item.parent_uuid,
 619                                                 BTRFS_UUID_SIZE);
 620                                 memcpy(si->received_uuid,
 621                                                 root_item.received_uuid,
 622                                                 BTRFS_UUID_SIZE);
 623                                 si->ctransid = btrfs_root_ctransid(&root_item);
 624                                 si->otransid = btrfs_root_otransid(&root_item);
 625                                 si->stransid = btrfs_root_stransid(&root_item);
 626                                 si->rtransid = btrfs_root_rtransid(&root_item);
 627                                 si->path = path;
 628                                 subvol_uuid_search_add(s, si);
 629                                 root_item_valid = 0;
 630                         } else {
 631                                 goto skip;
 632                         }
 633
 634 skip:
 635                         off += sh->len;
 636
 637                         /*
 638                          * record the mins in sk so we can make sure the
 639                          * next search doesn't repeat this root
 640                          */
 641                         sk->min_objectid = sh->objectid;
 642                         sk->min_offset = sh->offset;
 643                         sk->min_type = sh->type;
 644                 }
 645                 sk->nr_items = 4096;
 646                 if (sk->min_offset < (u64)-1)
 647                         sk->min_offset++;
 648                 else if (sk->min_objectid < (u64)-1) {
 649                         sk->min_objectid++;
 650                         sk->min_offset = 0;
 651                         sk->min_type = 0;
 652                 } else
 653                         break;
 654         }
 655
 656 out:
 657         return ret;
 658 }
 659
 660 void subvol_uuid_search_finit(struct subvol_uuid_search *s)
 661 {
 662         struct rb_root *root = &s->root_id_subvols;
 663         struct rb_node *node;
 664
 665         if (!s->uuid_tree_existed)
 666                 return;
 667
 668         while ((node = rb_first(root))) {
 669                 struct subvol_info *entry =
 670                         rb_entry(node, struct subvol_info, rb_root_id_node);
 671
 672                 free(entry->path);
 673                 rb_erase(node, root);
 674                 free(entry);
 675         }
 676
 677         s->root_id_subvols = RB_ROOT;
 678         s->local_subvols = RB_ROOT;
 679         s->received_subvols = RB_ROOT;
 680         s->path_subvols = RB_ROOT;
 681 }
 682
 683 char *path_cat(const char *p1, const char *p2)
 684 {
 685         int p1_len = strlen(p1);
 686         int p2_len = strlen(p2);
 687         char *new = malloc(p1_len + p2_len + 2);
 688
 689         if (p1_len && p1[p1_len - 1] == '/')
 690                 p1_len--;
 691         if (p2_len && p2[p2_len - 1] == '/')
 692                 p2_len--;
 693         sprintf(new, "%.*s/%.*s", p1_len, p1, p2_len, p2);
 694         return new;
 695 }
 696
 697 char *path_cat3(const char *p1, const char *p2, const char *p3)
 698 {
 699         int p1_len = strlen(p1);
 700         int p2_len = strlen(p2);
 701         int p3_len = strlen(p3);
 702         char *new = malloc(p1_len + p2_len + p3_len + 3);
 703
 704         if (p1_len && p1[p1_len - 1] == '/')
 705                 p1_len--;
 706         if (p2_len && p2[p2_len - 1] == '/')
 707                 p2_len--;
 708         if (p3_len && p3[p3_len - 1] == '/')
 709                 p3_len--;
 710         sprintf(new, "%.*s/%.*s/%.*s", p1_len, p1, p2_len, p2, p3_len, p3);
 711         return new;
 712 }