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