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 #include <errno.h>
  25
  26 #include "ctree.h"
  27 #include "send-utils.h"
  28 #include "ioctl.h"
  29 #include "btrfs-list.h"
  30
  31 static int btrfs_subvolid_resolve_sub(int fd, char *path, size_t *path_len,
  32                                       u64 subvol_id);
  33
  34 static int btrfs_get_root_id_by_sub_path(int mnt_fd, const char *sub_path,
  35                                          u64 *root_id)
  36 {
  37         int ret;
  38         int subvol_fd;
  39
  40         subvol_fd = openat(mnt_fd, sub_path, O_RDONLY);
  41         if (subvol_fd < 0) {
  42                 ret = -errno;
  43                 fprintf(stderr, "ERROR: open %s failed. %s\n", sub_path,
  44                         strerror(-ret));
  45                 return ret;
  46         }
  47
  48         ret = btrfs_list_get_path_rootid(subvol_fd, root_id);
  49         close(subvol_fd);
  50         return ret;
  51 }
  52
  53 static int btrfs_read_root_item_raw(int mnt_fd, u64 root_id, size_t buf_len,
  54                                     u32 *read_len, void *buf)
  55 {
  56         int ret;
  57         struct btrfs_ioctl_search_args args;
  58         struct btrfs_ioctl_search_key *sk = &args.key;
  59         struct btrfs_ioctl_search_header *sh;
  60         unsigned long off = 0;
  61         int found = 0;
  62         int i;
  63
  64         *read_len = 0;
  65         memset(&args, 0, sizeof(args));
  66
  67         sk->tree_id = BTRFS_ROOT_TREE_OBJECTID;
  68
  69         /*
  70          * there may be more than one ROOT_ITEM key if there are
  71          * snapshots pending deletion, we have to loop through
  72          * them.
  73          */
  74         sk->min_objectid = root_id;
  75         sk->max_objectid = root_id;
  76         sk->max_type = BTRFS_ROOT_ITEM_KEY;
  77         sk->min_type = BTRFS_ROOT_ITEM_KEY;
  78         sk->max_offset = (u64)-1;
  79         sk->max_transid = (u64)-1;
  80         sk->nr_items = 4096;
  81
  82         while (1) {
  83                 ret = ioctl(mnt_fd, BTRFS_IOC_TREE_SEARCH, &args);
  84                 if (ret < 0) {
  85                         fprintf(stderr,
  86                                 "ERROR: can't perform the search - %m\n");
  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 += btrfs_search_header_len(sh);
 102
 103                         sk->min_objectid = btrfs_search_header_objectid(sh);
 104                         sk->min_type = btrfs_search_header_type(sh);
 105                         sk->min_offset = btrfs_search_header_offset(sh);
 106
 107                         if (btrfs_search_header_objectid(sh) > root_id)
 108                                 break;
 109
 110                         if (btrfs_search_header_objectid(sh) == root_id &&
 111                             btrfs_search_header_type(sh) == BTRFS_ROOT_ITEM_KEY) {
 112                                 if (btrfs_search_header_len(sh) > 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, btrfs_search_header_len(sh));
 119                                 *read_len = btrfs_search_header_len(sh);
 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 < 0) {
 268                 fprintf(stderr,
 269                         "ioctl(BTRFS_IOC_TREE_SEARCH, subvol_id %llu) ret=%d, error: %m\n",
 270                         (unsigned long long)subvol_id, ret);
 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 (btrfs_search_header_offset(search_header)
 283             != BTRFS_FS_TREE_OBJECTID) {
 284                 int sub_ret;
 285
 286                 sub_ret = btrfs_subvolid_resolve_sub(fd, path, path_len,
 287                                 btrfs_search_header_offset(search_header));
 288                 if (sub_ret)
 289                         return sub_ret;
 290                 if (*path_len < 1)
 291                         return -EOVERFLOW;
 292                 strcat(path, "/");
 293                 (*path_len)--;
 294         }
 295
 296         if (btrfs_stack_root_ref_dirid(backref_item) !=
 297             BTRFS_FIRST_FREE_OBJECTID) {
 298                 int len;
 299
 300                 memset(&ino_lookup_arg, 0, sizeof(ino_lookup_arg));
 301                 ino_lookup_arg.treeid =
 302                         btrfs_search_header_offset(search_header);
 303                 ino_lookup_arg.objectid =
 304                         btrfs_stack_root_ref_dirid(backref_item);
 305                 ret = ioctl(fd, BTRFS_IOC_INO_LOOKUP, &ino_lookup_arg);
 306                 if (ret < 0) {
 307                         fprintf(stderr,
 308                                 "ioctl(BTRFS_IOC_INO_LOOKUP) ret=%d, error: %m\n",
 309                                 ret);
 310                         return ret;
 311                 }
 312
 313                 len = strlen(ino_lookup_arg.name);
 314                 if (*path_len < len)
 315                         return -EOVERFLOW;
 316                 strcat(path, ino_lookup_arg.name);
 317                 (*path_len) -= len;
 318         }
 319
 320         if (*path_len < btrfs_stack_root_ref_name_len(backref_item))
 321                 return -EOVERFLOW;
 322         strncat(path, (char *)(backref_item + 1),
 323                 btrfs_stack_root_ref_name_len(backref_item));
 324         (*path_len) -= btrfs_stack_root_ref_name_len(backref_item);
 325         return 0;
 326 }
 327
 328 #ifdef BTRFS_COMPAT_SEND_NO_UUID_TREE
 329 static int count_bytes(void *buf, int len, char b)
 330 {
 331         int cnt = 0;
 332         int i;
 333
 334         for (i = 0; i < len; i++) {
 335                 if (((char *)buf)[i] == b)
 336                         cnt++;
 337         }
 338         return cnt;
 339 }
 340
 341 void subvol_uuid_search_add(struct subvol_uuid_search *s,
 342                             struct subvol_info *si)
 343 {
 344         int cnt;
 345
 346         tree_insert(&s->root_id_subvols, si, subvol_search_by_root_id);
 347         tree_insert(&s->path_subvols, si, subvol_search_by_path);
 348
 349         cnt = count_bytes(si->uuid, BTRFS_UUID_SIZE, 0);
 350         if (cnt != BTRFS_UUID_SIZE)
 351                 tree_insert(&s->local_subvols, si, subvol_search_by_uuid);
 352         cnt = count_bytes(si->received_uuid, BTRFS_UUID_SIZE, 0);
 353         if (cnt != BTRFS_UUID_SIZE)
 354                 tree_insert(&s->received_subvols, si,
 355                                 subvol_search_by_received_uuid);
 356 }
 357
 358 static struct subvol_info *tree_search(struct rb_root *root,
 359                                        u64 root_id, const u8 *uuid,
 360                                        u64 stransid, const char *path,
 361                                        enum subvol_search_type type)
 362 {
 363         struct rb_node *n = root->rb_node;
 364         struct subvol_info *entry;
 365         __s64 comp;
 366
 367         while (n) {
 368                 if (type == subvol_search_by_received_uuid) {
 369                         entry = rb_entry(n, struct subvol_info,
 370                                         rb_received_node);
 371                         comp = memcmp(entry->received_uuid, uuid,
 372                                         BTRFS_UUID_SIZE);
 373                         if (!comp) {
 374                                 if (entry->stransid < stransid)
 375                                         comp = -1;
 376                                 else if (entry->stransid > stransid)
 377                                         comp = 1;
 378                                 else
 379                                         comp = 0;
 380                         }
 381                 } else if (type == subvol_search_by_uuid) {
 382                         entry = rb_entry(n, struct subvol_info, rb_local_node);
 383                         comp = memcmp(entry->uuid, uuid, BTRFS_UUID_SIZE);
 384                 } else if (type == subvol_search_by_root_id) {
 385                         entry = rb_entry(n, struct subvol_info,
 386                                          rb_root_id_node);
 387                         comp = entry->root_id - root_id;
 388                 } else if (type == subvol_search_by_path) {
 389                         entry = rb_entry(n, struct subvol_info, rb_path_node);
 390                         comp = strcmp(entry->path, path);
 391                 } else {
 392                         BUG();
 393                 }
 394                 if (comp < 0)
 395                         n = n->rb_left;
 396                 else if (comp > 0)
 397                         n = n->rb_right;
 398                 else
 399                         return entry;
 400         }
 401         return NULL;
 402 }
 403
 404 /*
 405  * this function will be only called if kernel doesn't support uuid tree.
 406  */
 407 static struct subvol_info *subvol_uuid_search_old(struct subvol_uuid_search *s,
 408                                        u64 root_id, const u8 *uuid, u64 transid,
 409                                        const char *path,
 410                                        enum subvol_search_type type)
 411 {
 412         struct rb_root *root;
 413         if (type == subvol_search_by_received_uuid)
 414                 root = &s->received_subvols;
 415         else if (type == subvol_search_by_uuid)
 416                 root = &s->local_subvols;
 417         else if (type == subvol_search_by_root_id)
 418                 root = &s->root_id_subvols;
 419         else if (type == subvol_search_by_path)
 420                 root = &s->path_subvols;
 421         else
 422                 return NULL;
 423         return tree_search(root, root_id, uuid, transid, path, type);
 424 }
 425 #else
 426 void subvol_uuid_search_add(struct subvol_uuid_search *s,
 427                             struct subvol_info *si)
 428 {
 429         if (si) {
 430                 free(si->path);
 431                 free(si);
 432         }
 433 }
 434 #endif
 435
 436 struct subvol_info *subvol_uuid_search(struct subvol_uuid_search *s,
 437                                        u64 root_id, const u8 *uuid, u64 transid,
 438                                        const char *path,
 439                                        enum subvol_search_type type)
 440 {
 441         struct subvol_info *si;
 442
 443         si = subvol_uuid_search2(s, root_id, uuid, transid, path, type);
 444         if (IS_ERR(si))
 445                 return NULL;
 446         return si;
 447 }
 448
 449 struct subvol_info *subvol_uuid_search2(struct subvol_uuid_search *s,
 450                                        u64 root_id, const u8 *uuid, u64 transid,
 451                                        const char *path,
 452                                        enum subvol_search_type type)
 453 {
 454         int ret = 0;
 455         struct btrfs_root_item root_item;
 456         struct subvol_info *info = NULL;
 457
 458 #ifdef BTRFS_COMPAT_SEND_NO_UUID_TREE
 459         if (!s->uuid_tree_existed)
 460                 return subvol_uuid_search_old(s, root_id, uuid, transid,
 461                                              path, type);
 462 #endif
 463         switch (type) {
 464         case subvol_search_by_received_uuid:
 465                 ret = btrfs_lookup_uuid_received_subvol_item(s->mnt_fd, uuid,
 466                                                              &root_id);
 467                 break;
 468         case subvol_search_by_uuid:
 469                 ret = btrfs_lookup_uuid_subvol_item(s->mnt_fd, uuid, &root_id);
 470                 break;
 471         case subvol_search_by_root_id:
 472                 break;
 473         case subvol_search_by_path:
 474                 ret = btrfs_get_root_id_by_sub_path(s->mnt_fd, path, &root_id);
 475                 break;
 476         default:
 477                 ret = -EINVAL;
 478                 break;
 479         }
 480
 481         if (ret)
 482                 goto out;
 483
 484         ret = btrfs_read_root_item(s->mnt_fd, root_id, &root_item);
 485         if (ret)
 486                 goto out;
 487
 488         info = calloc(1, sizeof(*info));
 489         if (!info) {
 490                 ret = -ENOMEM;
 491                 goto out;
 492         }
 493         info->root_id = root_id;
 494         memcpy(info->uuid, root_item.uuid, BTRFS_UUID_SIZE);
 495         memcpy(info->received_uuid, root_item.received_uuid, BTRFS_UUID_SIZE);
 496         memcpy(info->parent_uuid, root_item.parent_uuid, BTRFS_UUID_SIZE);
 497         info->ctransid = btrfs_root_ctransid(&root_item);
 498         info->otransid = btrfs_root_otransid(&root_item);
 499         info->stransid = btrfs_root_stransid(&root_item);
 500         info->rtransid = btrfs_root_rtransid(&root_item);
 501         if (type == subvol_search_by_path) {
 502                 info->path = strdup(path);
 503                 if (!info->path) {
 504                         ret = -ENOMEM;
 505                         goto out;
 506                 }
 507         } else {
 508                 info->path = malloc(PATH_MAX);
 509                 if (!info->path) {
 510                         ret = -ENOMEM;
 511                         goto out;
 512                 }
 513                 ret = btrfs_subvolid_resolve(s->mnt_fd, info->path,
 514                                              PATH_MAX, root_id);
 515         }
 516
 517 out:
 518         if (ret) {
 519                 if (info) {
 520                         free(info->path);
 521                         free(info);
 522                 }
 523                 return ERR_PTR(ret);
 524         }
 525
 526         return info;
 527 }
 528
 529 #ifdef BTRFS_COMPAT_SEND_NO_UUID_TREE
 530 static int is_uuid_tree_supported(int fd)
 531 {
 532         int ret;
 533         struct btrfs_ioctl_search_args args;
 534         struct btrfs_ioctl_search_key *sk = &args.key;
 535
 536         memset(&args, 0, sizeof(args));
 537
 538         sk->tree_id = BTRFS_ROOT_TREE_OBJECTID;
 539
 540         sk->min_objectid = BTRFS_UUID_TREE_OBJECTID;
 541         sk->max_objectid = BTRFS_UUID_TREE_OBJECTID;
 542         sk->max_type = BTRFS_ROOT_ITEM_KEY;
 543         sk->min_type = BTRFS_ROOT_ITEM_KEY;
 544         sk->max_offset = (u64)-1;
 545         sk->max_transid = (u64)-1;
 546         sk->nr_items = 1;
 547
 548         ret = ioctl(fd, BTRFS_IOC_TREE_SEARCH, &args);
 549         if (ret < 0)
 550                 return ret;
 551
 552         /* the ioctl returns the number of item it found in nr_items */
 553         if (sk->nr_items == 0)
 554                 return 0;
 555
 556         return 1;
 557 }
 558
 559 /*
 560  * this function is mainly used to read all root items
 561  * it will be only used when we use older kernel which uuid
 562  * tree is not supported yet
 563  */
 564 int subvol_uuid_search_init(int mnt_fd, struct subvol_uuid_search *s)
 565 {
 566         int ret;
 567         struct btrfs_ioctl_search_args args;
 568         struct btrfs_ioctl_search_key *sk = &args.key;
 569         struct btrfs_ioctl_search_header *sh;
 570         struct btrfs_root_item *root_item_ptr;
 571         struct btrfs_root_item root_item = {};
 572         struct subvol_info *si = NULL;
 573         int root_item_valid = 0;
 574         unsigned long off = 0;
 575         int i;
 576         char *path;
 577
 578         s->mnt_fd = mnt_fd;
 579
 580         s->root_id_subvols = RB_ROOT;
 581         s->local_subvols = RB_ROOT;
 582         s->received_subvols = RB_ROOT;
 583         s->path_subvols = RB_ROOT;
 584
 585         ret = is_uuid_tree_supported(mnt_fd);
 586         if (ret < 0) {
 587                 fprintf(stderr,
 588                         "ERROR: check if we support uuid tree fails - %m\n");
 589                 return ret;
 590         } else if (ret) {
 591                 /* uuid tree is supported */
 592                 s->uuid_tree_existed = 1;
 593                 return 0;
 594         }
 595         memset(&args, 0, sizeof(args));
 596
 597         sk->tree_id = BTRFS_ROOT_TREE_OBJECTID;
 598
 599         sk->max_objectid = (u64)-1;
 600         sk->max_offset = (u64)-1;
 601         sk->max_transid = (u64)-1;
 602         sk->min_type = BTRFS_ROOT_ITEM_KEY;
 603         sk->max_type = BTRFS_ROOT_BACKREF_KEY;
 604         sk->nr_items = 4096;
 605
 606         while (1) {
 607                 ret = ioctl(mnt_fd, BTRFS_IOC_TREE_SEARCH, &args);
 608                 if (ret < 0) {
 609                         fprintf(stderr, "ERROR: can't perform the search - %m\n");
 610                         return ret;
 611                 }
 612                 if (sk->nr_items == 0)
 613                         break;
 614
 615                 off = 0;
 616
 617                 for (i = 0; i < sk->nr_items; i++) {
 618                         sh = (struct btrfs_ioctl_search_header *)(args.buf +
 619                                                                   off);
 620                         off += sizeof(*sh);
 621
 622                         if ((btrfs_search_header_objectid(sh) != 5 &&
 623                              btrfs_search_header_objectid(sh)
 624                              < BTRFS_FIRST_FREE_OBJECTID) ||
 625                             btrfs_search_header_objectid(sh)
 626                             > BTRFS_LAST_FREE_OBJECTID) {
 627                                 goto skip;
 628                         }
 629
 630                         if (btrfs_search_header_type(sh)
 631                             == BTRFS_ROOT_ITEM_KEY) {
 632                                 /* older kernels don't have uuids+times */
 633                                 if (btrfs_search_header_len(sh)
 634                                     < sizeof(root_item)) {
 635                                         root_item_valid = 0;
 636                                         goto skip;
 637                                 }
 638                                 root_item_ptr = (struct btrfs_root_item *)
 639                                                 (args.buf + off);
 640                                 memcpy(&root_item, root_item_ptr,
 641                                                 sizeof(root_item));
 642                                 root_item_valid = 1;
 643                         } else if (btrfs_search_header_type(sh)
 644                                    == BTRFS_ROOT_BACKREF_KEY ||
 645                                    root_item_valid) {
 646                                 if (!root_item_valid)
 647                                         goto skip;
 648
 649                                 path = btrfs_list_path_for_root(mnt_fd,
 650                                         btrfs_search_header_objectid(sh));
 651                                 if (!path)
 652                                         path = strdup("");
 653                                 if (IS_ERR(path)) {
 654                                         ret = PTR_ERR(path);
 655                                         fprintf(stderr, "ERROR: unable to "
 656                                                         "resolve path "
 657                                                         "for root %llu\n",
 658                                                 btrfs_search_header_objectid(sh));
 659                                         goto out;
 660                                 }
 661
 662                                 si = calloc(1, sizeof(*si));
 663                                 si->root_id = btrfs_search_header_objectid(sh);
 664                                 memcpy(si->uuid, root_item.uuid,
 665                                                 BTRFS_UUID_SIZE);
 666                                 memcpy(si->parent_uuid, root_item.parent_uuid,
 667                                                 BTRFS_UUID_SIZE);
 668                                 memcpy(si->received_uuid,
 669                                                 root_item.received_uuid,
 670                                                 BTRFS_UUID_SIZE);
 671                                 si->ctransid = btrfs_root_ctransid(&root_item);
 672                                 si->otransid = btrfs_root_otransid(&root_item);
 673                                 si->stransid = btrfs_root_stransid(&root_item);
 674                                 si->rtransid = btrfs_root_rtransid(&root_item);
 675                                 si->path = path;
 676                                 subvol_uuid_search_add(s, si);
 677                                 root_item_valid = 0;
 678                         } else {
 679                                 goto skip;
 680                         }
 681
 682 skip:
 683                         off += btrfs_search_header_len(sh);
 684
 685                         /*
 686                          * record the mins in sk so we can make sure the
 687                          * next search doesn't repeat this root
 688                          */
 689                         sk->min_objectid = btrfs_search_header_objectid(sh);
 690                         sk->min_offset = btrfs_search_header_offset(sh);
 691                         sk->min_type = btrfs_search_header_type(sh);
 692                 }
 693                 sk->nr_items = 4096;
 694                 if (sk->min_offset < (u64)-1)
 695                         sk->min_offset++;
 696                 else if (sk->min_objectid < (u64)-1) {
 697                         sk->min_objectid++;
 698                         sk->min_offset = 0;
 699                         sk->min_type = 0;
 700                 } else
 701                         break;
 702         }
 703
 704 out:
 705         return ret;
 706 }
 707
 708 void subvol_uuid_search_finit(struct subvol_uuid_search *s)
 709 {
 710         struct rb_root *root = &s->root_id_subvols;
 711         struct rb_node *node;
 712
 713         if (!s->uuid_tree_existed)
 714                 return;
 715
 716         while ((node = rb_first(root))) {
 717                 struct subvol_info *entry =
 718                         rb_entry(node, struct subvol_info, rb_root_id_node);
 719
 720                 free(entry->path);
 721                 rb_erase(node, root);
 722                 free(entry);
 723         }
 724
 725         s->root_id_subvols = RB_ROOT;
 726         s->local_subvols = RB_ROOT;
 727         s->received_subvols = RB_ROOT;
 728         s->path_subvols = RB_ROOT;
 729 }
 730 #else
 731 int subvol_uuid_search_init(int mnt_fd, struct subvol_uuid_search *s)
 732 {
 733         s->mnt_fd = mnt_fd;
 734
 735         return 0;
 736 }
 737
 738 void subvol_uuid_search_finit(struct subvol_uuid_search *s)
 739 {
 740 }
 741 #endif
 742
 743 int path_cat_out(char *out, const char *p1, const char *p2)
 744 {
 745         int p1_len = strlen(p1);
 746         int p2_len = strlen(p2);
 747
 748         if (p1_len + p2_len + 2 >= PATH_MAX)
 749                 return -ENAMETOOLONG;
 750
 751         if (p1_len && p1[p1_len - 1] == '/')
 752                 p1_len--;
 753         if (p2_len && p2[p2_len - 1] == '/')
 754                 p2_len--;
 755         sprintf(out, "%.*s/%.*s", p1_len, p1, p2_len, p2);
 756
 757         return 0;
 758 }
 759
 760 int path_cat3_out(char *out, const char *p1, const char *p2, const char *p3)
 761 {
 762         int p1_len = strlen(p1);
 763         int p2_len = strlen(p2);
 764         int p3_len = strlen(p3);
 765
 766         if (p1_len + p2_len + p3_len + 3 >= PATH_MAX)
 767                 return -ENAMETOOLONG;
 768
 769         if (p1_len && p1[p1_len - 1] == '/')
 770                 p1_len--;
 771         if (p2_len && p2[p2_len - 1] == '/')
 772                 p2_len--;
 773         if (p3_len && p3[p3_len - 1] == '/')
 774                 p3_len--;
 775         sprintf(out, "%.*s/%.*s/%.*s", p1_len, p1, p2_len, p2, p3_len, p3);
 776
 777         return 0;
 778 }