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 #ifdef BTRFS_COMPAT_SEND_NO_UUID_TREE
 163 static struct rb_node *tree_insert(struct rb_root *root,
 164                                    struct subvol_info *si,
 165                                    enum subvol_search_type type)
 166 {
 167         struct rb_node **p = &root->rb_node;
 168         struct rb_node *parent = NULL;
 169         struct subvol_info *entry;
 170         __s64 comp;
 171
 172         while (*p) {
 173                 parent = *p;
 174                 if (type == subvol_search_by_received_uuid) {
 175                         entry = rb_entry(parent, struct subvol_info,
 176                                         rb_received_node);
 177
 178                         comp = memcmp(entry->received_uuid, si->received_uuid,
 179                                         BTRFS_UUID_SIZE);
 180                         if (!comp) {
 181                                 if (entry->stransid < si->stransid)
 182                                         comp = -1;
 183                                 else if (entry->stransid > si->stransid)
 184                                         comp = 1;
 185                                 else
 186                                         comp = 0;
 187                         }
 188                 } else if (type == subvol_search_by_uuid) {
 189                         entry = rb_entry(parent, struct subvol_info,
 190                                         rb_local_node);
 191                         comp = memcmp(entry->uuid, si->uuid, BTRFS_UUID_SIZE);
 192                 } else if (type == subvol_search_by_root_id) {
 193                         entry = rb_entry(parent, struct subvol_info,
 194                                         rb_root_id_node);
 195                         comp = entry->root_id - si->root_id;
 196                 } else if (type == subvol_search_by_path) {
 197                         entry = rb_entry(parent, struct subvol_info,
 198                                         rb_path_node);
 199                         comp = strcmp(entry->path, si->path);
 200                 } else {
 201                         BUG();
 202                 }
 203
 204                 if (comp < 0)
 205                         p = &(*p)->rb_left;
 206                 else if (comp > 0)
 207                         p = &(*p)->rb_right;
 208                 else
 209                         return parent;
 210         }
 211
 212         if (type == subvol_search_by_received_uuid) {
 213                 rb_link_node(&si->rb_received_node, parent, p);
 214                 rb_insert_color(&si->rb_received_node, root);
 215         } else if (type == subvol_search_by_uuid) {
 216                 rb_link_node(&si->rb_local_node, parent, p);
 217                 rb_insert_color(&si->rb_local_node, root);
 218         } else if (type == subvol_search_by_root_id) {
 219                 rb_link_node(&si->rb_root_id_node, parent, p);
 220                 rb_insert_color(&si->rb_root_id_node, root);
 221         } else if (type == subvol_search_by_path) {
 222                 rb_link_node(&si->rb_path_node, parent, p);
 223                 rb_insert_color(&si->rb_path_node, root);
 224         }
 225         return NULL;
 226 }
 227 #endif
 228
 229 int btrfs_subvolid_resolve(int fd, char *path, size_t path_len, u64 subvol_id)
 230 {
 231         if (path_len < 1)
 232                 return -EOVERFLOW;
 233         path[0] = '\0';
 234         path_len--;
 235         path[path_len] = '\0';
 236         return btrfs_subvolid_resolve_sub(fd, path, &path_len, subvol_id);
 237 }
 238
 239 static int btrfs_subvolid_resolve_sub(int fd, char *path, size_t *path_len,
 240                                       u64 subvol_id)
 241 {
 242         int ret;
 243         struct btrfs_ioctl_search_args search_arg;
 244         struct btrfs_ioctl_ino_lookup_args ino_lookup_arg;
 245         struct btrfs_ioctl_search_header *search_header;
 246         struct btrfs_root_ref *backref_item;
 247
 248         if (subvol_id == BTRFS_FS_TREE_OBJECTID) {
 249                 if (*path_len < 1)
 250                         return -EOVERFLOW;
 251                 *path = '\0';
 252                 (*path_len)--;
 253                 return 0;
 254         }
 255
 256         memset(&search_arg, 0, sizeof(search_arg));
 257         search_arg.key.tree_id = BTRFS_ROOT_TREE_OBJECTID;
 258         search_arg.key.min_objectid = subvol_id;
 259         search_arg.key.max_objectid = subvol_id;
 260         search_arg.key.min_type = BTRFS_ROOT_BACKREF_KEY;
 261         search_arg.key.max_type = BTRFS_ROOT_BACKREF_KEY;
 262         search_arg.key.max_offset = (u64)-1;
 263         search_arg.key.max_transid = (u64)-1;
 264         search_arg.key.nr_items = 1;
 265         ret = ioctl(fd, BTRFS_IOC_TREE_SEARCH, &search_arg);
 266         if (ret) {
 267                 fprintf(stderr,
 268                         "ioctl(BTRFS_IOC_TREE_SEARCH, subvol_id %llu) ret=%d, error: %s\n",
 269                         (unsigned long long)subvol_id, ret, strerror(errno));
 270                 return ret;
 271         }
 272
 273         if (search_arg.key.nr_items < 1) {
 274                 fprintf(stderr,
 275                         "failed to lookup subvol_id %llu!\n",
 276                         (unsigned long long)subvol_id);
 277                 return -ENOENT;
 278         }
 279         search_header = (struct btrfs_ioctl_search_header *)search_arg.buf;
 280         backref_item = (struct btrfs_root_ref *)(search_header + 1);
 281         if (search_header->offset != BTRFS_FS_TREE_OBJECTID) {
 282                 int sub_ret;
 283
 284                 sub_ret = btrfs_subvolid_resolve_sub(fd, path, path_len,
 285                                                      search_header->offset);
 286                 if (sub_ret)
 287                         return sub_ret;
 288                 if (*path_len < 1)
 289                         return -EOVERFLOW;
 290                 strcat(path, "/");
 291                 (*path_len)--;
 292         }
 293
 294         if (btrfs_stack_root_ref_dirid(backref_item) !=
 295             BTRFS_FIRST_FREE_OBJECTID) {
 296                 int len;
 297
 298                 memset(&ino_lookup_arg, 0, sizeof(ino_lookup_arg));
 299                 ino_lookup_arg.treeid = search_header->offset;
 300                 ino_lookup_arg.objectid =
 301                         btrfs_stack_root_ref_dirid(backref_item);
 302                 ret = ioctl(fd, BTRFS_IOC_INO_LOOKUP, &ino_lookup_arg);
 303                 if (ret) {
 304                         fprintf(stderr,
 305                                 "ioctl(BTRFS_IOC_INO_LOOKUP) ret=%d, error: %s\n",
 306                                 ret, strerror(errno));
 307                         return ret;
 308                 }
 309
 310                 len = strlen(ino_lookup_arg.name);
 311                 if (*path_len < len)
 312                         return -EOVERFLOW;
 313                 strcat(path, ino_lookup_arg.name);
 314                 (*path_len) -= len;
 315         }
 316
 317         if (*path_len < btrfs_stack_root_ref_name_len(backref_item))
 318                 return -EOVERFLOW;
 319         strncat(path, (char *)(backref_item + 1),
 320                 btrfs_stack_root_ref_name_len(backref_item));
 321         (*path_len) -= btrfs_stack_root_ref_name_len(backref_item);
 322         return 0;
 323 }
 324
 325 #ifdef BTRFS_COMPAT_SEND_NO_UUID_TREE
 326 static int count_bytes(void *buf, int len, char b)
 327 {
 328         int cnt = 0;
 329         int i;
 330
 331         for (i = 0; i < len; i++) {
 332                 if (((char *)buf)[i] == b)
 333                         cnt++;
 334         }
 335         return cnt;
 336 }
 337
 338 void subvol_uuid_search_add(struct subvol_uuid_search *s,
 339                             struct subvol_info *si)
 340 {
 341         int cnt;
 342
 343         tree_insert(&s->root_id_subvols, si, subvol_search_by_root_id);
 344         tree_insert(&s->path_subvols, si, subvol_search_by_path);
 345
 346         cnt = count_bytes(si->uuid, BTRFS_UUID_SIZE, 0);
 347         if (cnt != BTRFS_UUID_SIZE)
 348                 tree_insert(&s->local_subvols, si, subvol_search_by_uuid);
 349         cnt = count_bytes(si->received_uuid, BTRFS_UUID_SIZE, 0);
 350         if (cnt != BTRFS_UUID_SIZE)
 351                 tree_insert(&s->received_subvols, si,
 352                                 subvol_search_by_received_uuid);
 353 }
 354
 355 static struct subvol_info *tree_search(struct rb_root *root,
 356                                        u64 root_id, const u8 *uuid,
 357                                        u64 stransid, const char *path,
 358                                        enum subvol_search_type type)
 359 {
 360         struct rb_node *n = root->rb_node;
 361         struct subvol_info *entry;
 362         __s64 comp;
 363
 364         while (n) {
 365                 if (type == subvol_search_by_received_uuid) {
 366                         entry = rb_entry(n, struct subvol_info,
 367                                         rb_received_node);
 368                         comp = memcmp(entry->received_uuid, uuid,
 369                                         BTRFS_UUID_SIZE);
 370                         if (!comp) {
 371                                 if (entry->stransid < stransid)
 372                                         comp = -1;
 373                                 else if (entry->stransid > stransid)
 374                                         comp = 1;
 375                                 else
 376                                         comp = 0;
 377                         }
 378                 } else if (type == subvol_search_by_uuid) {
 379                         entry = rb_entry(n, struct subvol_info, rb_local_node);
 380                         comp = memcmp(entry->uuid, uuid, BTRFS_UUID_SIZE);
 381                 } else if (type == subvol_search_by_root_id) {
 382                         entry = rb_entry(n, struct subvol_info,
 383                                          rb_root_id_node);
 384                         comp = entry->root_id - root_id;
 385                 } else if (type == subvol_search_by_path) {
 386                         entry = rb_entry(n, struct subvol_info, rb_path_node);
 387                         comp = strcmp(entry->path, path);
 388                 } else {
 389                         BUG();
 390                 }
 391                 if (comp < 0)
 392                         n = n->rb_left;
 393                 else if (comp > 0)
 394                         n = n->rb_right;
 395                 else
 396                         return entry;
 397         }
 398         return NULL;
 399 }
 400
 401 /*
 402  * this function will be only called if kernel dosen't support uuid tree.
 403  */
 404 static struct subvol_info *subvol_uuid_search_old(struct subvol_uuid_search *s,
 405                                        u64 root_id, const u8 *uuid, u64 transid,
 406                                        const char *path,
 407                                        enum subvol_search_type type)
 408 {
 409         struct rb_root *root;
 410         if (type == subvol_search_by_received_uuid)
 411                 root = &s->received_subvols;
 412         else if (type == subvol_search_by_uuid)
 413                 root = &s->local_subvols;
 414         else if (type == subvol_search_by_root_id)
 415                 root = &s->root_id_subvols;
 416         else if (type == subvol_search_by_path)
 417                 root = &s->path_subvols;
 418         else
 419                 return NULL;
 420         return tree_search(root, root_id, uuid, transid, path, type);
 421 }
 422 #else
 423 void subvol_uuid_search_add(struct subvol_uuid_search *s,
 424                             struct subvol_info *si)
 425 {
 426         if (si) {
 427                 free(si->path);
 428                 free(si);
 429         }
 430 }
 431 #endif
 432
 433 struct subvol_info *subvol_uuid_search(struct subvol_uuid_search *s,
 434                                        u64 root_id, const u8 *uuid, u64 transid,
 435                                        const char *path,
 436                                        enum subvol_search_type type)
 437 {
 438         int ret = 0;
 439         struct btrfs_root_item root_item;
 440         struct subvol_info *info = NULL;
 441
 442 #ifdef BTRFS_COMPAT_SEND_NO_UUID_TREE
 443         if (!s->uuid_tree_existed)
 444                 return subvol_uuid_search_old(s, root_id, uuid, transid,
 445                                              path, type);
 446 #endif
 447         switch (type) {
 448         case subvol_search_by_received_uuid:
 449                 ret = btrfs_lookup_uuid_received_subvol_item(s->mnt_fd, uuid,
 450                                                              &root_id);
 451                 break;
 452         case subvol_search_by_uuid:
 453                 ret = btrfs_lookup_uuid_subvol_item(s->mnt_fd, uuid, &root_id);
 454                 break;
 455         case subvol_search_by_root_id:
 456                 break;
 457         case subvol_search_by_path:
 458                 ret = btrfs_get_root_id_by_sub_path(s->mnt_fd, path, &root_id);
 459                 break;
 460         default:
 461                 ret = -EINVAL;
 462                 break;
 463         }
 464
 465         if (ret)
 466                 goto out;
 467
 468         ret = btrfs_read_root_item(s->mnt_fd, root_id, &root_item);
 469         if (ret)
 470                 goto out;
 471
 472         info = calloc(1, sizeof(*info));
 473         info->root_id = root_id;
 474         memcpy(info->uuid, root_item.uuid, BTRFS_UUID_SIZE);
 475         memcpy(info->received_uuid, root_item.received_uuid, BTRFS_UUID_SIZE);
 476         memcpy(info->parent_uuid, root_item.parent_uuid, BTRFS_UUID_SIZE);
 477         info->ctransid = btrfs_root_ctransid(&root_item);
 478         info->otransid = btrfs_root_otransid(&root_item);
 479         info->stransid = btrfs_root_stransid(&root_item);
 480         info->rtransid = btrfs_root_rtransid(&root_item);
 481         if (type == subvol_search_by_path) {
 482                 info->path = strdup(path);
 483         } else {
 484                 info->path = malloc(BTRFS_PATH_NAME_MAX);
 485                 ret = btrfs_subvolid_resolve(s->mnt_fd, info->path,
 486                                              BTRFS_PATH_NAME_MAX, root_id);
 487         }
 488
 489 out:
 490         if (ret && info) {
 491                 free(info->path);
 492                 free(info);
 493                 info = NULL;
 494         }
 495
 496         return info;
 497 }
 498
 499 #ifdef BTRFS_COMPAT_SEND_NO_UUID_TREE
 500 static int is_uuid_tree_supported(int fd)
 501 {
 502         int ret;
 503         struct btrfs_ioctl_search_args args;
 504         struct btrfs_ioctl_search_key *sk = &args.key;
 505
 506         memset(&args, 0, sizeof(args));
 507
 508         sk->tree_id = BTRFS_ROOT_TREE_OBJECTID;
 509
 510         sk->min_objectid = BTRFS_UUID_TREE_OBJECTID;
 511         sk->max_objectid = BTRFS_UUID_TREE_OBJECTID;
 512         sk->max_type = BTRFS_ROOT_ITEM_KEY;
 513         sk->min_type = BTRFS_ROOT_ITEM_KEY;
 514         sk->max_offset = (u64)-1;
 515         sk->max_transid = (u64)-1;
 516         sk->nr_items = 1;
 517
 518         ret = ioctl(fd, BTRFS_IOC_TREE_SEARCH, &args);
 519         if (ret < 0)
 520                 return ret;
 521
 522         /* the ioctl returns the number of item it found in nr_items */
 523         if (sk->nr_items == 0)
 524                 return 0;
 525
 526         return 1;
 527 }
 528
 529 /*
 530  * this function is mainly used to read all root items
 531  * it will be only used when we use older kernel which uuid
 532  * tree is not supported yet
 533  */
 534 int subvol_uuid_search_init(int mnt_fd, struct subvol_uuid_search *s)
 535 {
 536         int ret;
 537         struct btrfs_ioctl_search_args args;
 538         struct btrfs_ioctl_search_key *sk = &args.key;
 539         struct btrfs_ioctl_search_header *sh;
 540         struct btrfs_root_item *root_item_ptr;
 541         struct btrfs_root_item root_item = {};
 542         struct subvol_info *si = NULL;
 543         int root_item_valid = 0;
 544         unsigned long off = 0;
 545         int i;
 546         int e;
 547         char *path;
 548
 549         s->mnt_fd = mnt_fd;
 550
 551         s->root_id_subvols = RB_ROOT;
 552         s->local_subvols = RB_ROOT;
 553         s->received_subvols = RB_ROOT;
 554         s->path_subvols = RB_ROOT;
 555
 556         ret = is_uuid_tree_supported(mnt_fd);
 557         if (ret < 0) {
 558                 fprintf(stderr,
 559                         "ERROR: check if we support uuid tree fails - %s\n",
 560                         strerror(errno));
 561                 return ret;
 562         } else if (ret) {
 563                 /* uuid tree is supported */
 564                 s->uuid_tree_existed = 1;
 565                 return 0;
 566         }
 567         memset(&args, 0, sizeof(args));
 568
 569         sk->tree_id = BTRFS_ROOT_TREE_OBJECTID;
 570
 571         sk->max_objectid = (u64)-1;
 572         sk->max_offset = (u64)-1;
 573         sk->max_transid = (u64)-1;
 574         sk->min_type = BTRFS_ROOT_ITEM_KEY;
 575         sk->max_type = BTRFS_ROOT_BACKREF_KEY;
 576         sk->nr_items = 4096;
 577
 578         while (1) {
 579                 ret = ioctl(mnt_fd, BTRFS_IOC_TREE_SEARCH, &args);
 580                 e = errno;
 581                 if (ret < 0) {
 582                         fprintf(stderr, "ERROR: can't perform the search - %s\n",
 583                                 strerror(e));
 584                         return ret;
 585                 }
 586                 if (sk->nr_items == 0)
 587                         break;
 588
 589                 off = 0;
 590
 591                 for (i = 0; i < sk->nr_items; i++) {
 592                         sh = (struct btrfs_ioctl_search_header *)(args.buf +
 593                                                                   off);
 594                         off += sizeof(*sh);
 595
 596                         if ((sh->objectid != 5 &&
 597                             sh->objectid < BTRFS_FIRST_FREE_OBJECTID) ||
 598                             sh->objectid > BTRFS_LAST_FREE_OBJECTID)
 599                                 goto skip;
 600
 601                         if (sh->type == BTRFS_ROOT_ITEM_KEY) {
 602                                 /* older kernels don't have uuids+times */
 603                                 if (sh->len < sizeof(root_item)) {
 604                                         root_item_valid = 0;
 605                                         goto skip;
 606                                 }
 607                                 root_item_ptr = (struct btrfs_root_item *)
 608                                                 (args.buf + off);
 609                                 memcpy(&root_item, root_item_ptr,
 610                                                 sizeof(root_item));
 611                                 root_item_valid = 1;
 612                         } else if (sh->type == BTRFS_ROOT_BACKREF_KEY ||
 613                                    root_item_valid) {
 614                                 if (!root_item_valid)
 615                                         goto skip;
 616
 617                                 path = btrfs_list_path_for_root(mnt_fd,
 618                                                                 sh->objectid);
 619                                 if (!path)
 620                                         path = strdup("");
 621                                 if (IS_ERR(path)) {
 622                                         ret = PTR_ERR(path);
 623                                         fprintf(stderr, "ERROR: unable to "
 624                                                         "resolve path "
 625                                                         "for root %llu\n",
 626                                                         sh->objectid);
 627                                         goto out;
 628                                 }
 629
 630                                 si = calloc(1, sizeof(*si));
 631                                 si->root_id = sh->objectid;
 632                                 memcpy(si->uuid, root_item.uuid,
 633                                                 BTRFS_UUID_SIZE);
 634                                 memcpy(si->parent_uuid, root_item.parent_uuid,
 635                                                 BTRFS_UUID_SIZE);
 636                                 memcpy(si->received_uuid,
 637                                                 root_item.received_uuid,
 638                                                 BTRFS_UUID_SIZE);
 639                                 si->ctransid = btrfs_root_ctransid(&root_item);
 640                                 si->otransid = btrfs_root_otransid(&root_item);
 641                                 si->stransid = btrfs_root_stransid(&root_item);
 642                                 si->rtransid = btrfs_root_rtransid(&root_item);
 643                                 si->path = path;
 644                                 subvol_uuid_search_add(s, si);
 645                                 root_item_valid = 0;
 646                         } else {
 647                                 goto skip;
 648                         }
 649
 650 skip:
 651                         off += sh->len;
 652
 653                         /*
 654                          * record the mins in sk so we can make sure the
 655                          * next search doesn't repeat this root
 656                          */
 657                         sk->min_objectid = sh->objectid;
 658                         sk->min_offset = sh->offset;
 659                         sk->min_type = sh->type;
 660                 }
 661                 sk->nr_items = 4096;
 662                 if (sk->min_offset < (u64)-1)
 663                         sk->min_offset++;
 664                 else if (sk->min_objectid < (u64)-1) {
 665                         sk->min_objectid++;
 666                         sk->min_offset = 0;
 667                         sk->min_type = 0;
 668                 } else
 669                         break;
 670         }
 671
 672 out:
 673         return ret;
 674 }
 675
 676 void subvol_uuid_search_finit(struct subvol_uuid_search *s)
 677 {
 678         struct rb_root *root = &s->root_id_subvols;
 679         struct rb_node *node;
 680
 681         if (!s->uuid_tree_existed)
 682                 return;
 683
 684         while ((node = rb_first(root))) {
 685                 struct subvol_info *entry =
 686                         rb_entry(node, struct subvol_info, rb_root_id_node);
 687
 688                 free(entry->path);
 689                 rb_erase(node, root);
 690                 free(entry);
 691         }
 692
 693         s->root_id_subvols = RB_ROOT;
 694         s->local_subvols = RB_ROOT;
 695         s->received_subvols = RB_ROOT;
 696         s->path_subvols = RB_ROOT;
 697 }
 698 #else
 699 int subvol_uuid_search_init(int mnt_fd, struct subvol_uuid_search *s)
 700 {
 701         s->mnt_fd = mnt_fd;
 702
 703         return 0;
 704 }
 705
 706 void subvol_uuid_search_finit(struct subvol_uuid_search *s)
 707 {
 708 }
 709 #endif
 710
 711 char *path_cat(const char *p1, const char *p2)
 712 {
 713         int p1_len = strlen(p1);
 714         int p2_len = strlen(p2);
 715         char *new = malloc(p1_len + p2_len + 2);
 716
 717         if (p1_len && p1[p1_len - 1] == '/')
 718                 p1_len--;
 719         if (p2_len && p2[p2_len - 1] == '/')
 720                 p2_len--;
 721         sprintf(new, "%.*s/%.*s", p1_len, p1, p2_len, p2);
 722         return new;
 723 }
 724
 725 char *path_cat3(const char *p1, const char *p2, const char *p3)
 726 {
 727         int p1_len = strlen(p1);
 728         int p2_len = strlen(p2);
 729         int p3_len = strlen(p3);
 730         char *new = malloc(p1_len + p2_len + p3_len + 3);
 731
 732         if (p1_len && p1[p1_len - 1] == '/')
 733                 p1_len--;
 734         if (p2_len && p2[p2_len - 1] == '/')
 735                 p2_len--;
 736         if (p3_len && p3[p3_len - 1] == '/')
 737                 p3_len--;
 738         sprintf(new, "%.*s/%.*s/%.*s", p1_len, p1, p2_len, p2, p3_len, p3);
 739         return new;
 740 }