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 <sys/ioctl.h>
  20
  21 #include "ctree.h"
  22 #include "send-utils.h"
  23 #include "ioctl.h"
  24 #include "btrfs-list.h"
  25
  26 static int btrfs_subvolid_resolve_sub(int fd, char *path, size_t *path_len,
  27                                       u64 subvol_id);
  28
  29 int btrfs_subvolid_resolve(int fd, char *path, size_t path_len, u64 subvol_id)
  30 {
  31         if (path_len < 1)
  32                 return -EOVERFLOW;
  33         path[0] = '\0';
  34         path_len--;
  35         path[path_len] = '\0';
  36         return btrfs_subvolid_resolve_sub(fd, path, &path_len, subvol_id);
  37 }
  38
  39 static int btrfs_subvolid_resolve_sub(int fd, char *path, size_t *path_len,
  40                                       u64 subvol_id)
  41 {
  42         int ret;
  43         struct btrfs_ioctl_search_args search_arg;
  44         struct btrfs_ioctl_ino_lookup_args ino_lookup_arg;
  45         struct btrfs_ioctl_search_header *search_header;
  46         struct btrfs_root_ref *backref_item;
  47
  48         if (subvol_id == BTRFS_FS_TREE_OBJECTID) {
  49                 if (*path_len < 1)
  50                         return -EOVERFLOW;
  51                 *path = '\0';
  52                 (*path_len)--;
  53                 return 0;
  54         }
  55
  56         memset(&search_arg, 0, sizeof(search_arg));
  57         search_arg.key.tree_id = BTRFS_ROOT_TREE_OBJECTID;
  58         search_arg.key.min_objectid = subvol_id;
  59         search_arg.key.max_objectid = subvol_id;
  60         search_arg.key.min_type = BTRFS_ROOT_BACKREF_KEY;
  61         search_arg.key.max_type = BTRFS_ROOT_BACKREF_KEY;
  62         search_arg.key.max_offset = (u64)-1;
  63         search_arg.key.max_transid = (u64)-1;
  64         search_arg.key.nr_items = 1;
  65         ret = ioctl(fd, BTRFS_IOC_TREE_SEARCH, &search_arg);
  66         if (ret) {
  67                 fprintf(stderr,
  68                         "ioctl(BTRFS_IOC_TREE_SEARCH, subvol_id %llu) ret=%d, error: %s\n",
  69                         (unsigned long long)subvol_id, ret, strerror(errno));
  70                 return ret;
  71         }
  72
  73         if (search_arg.key.nr_items < 1) {
  74                 fprintf(stderr,
  75                         "failed to lookup subvol_id %llu!\n",
  76                         (unsigned long long)subvol_id);
  77                 return -ENOENT;
  78         }
  79         search_header = (struct btrfs_ioctl_search_header *)search_arg.buf;
  80         backref_item = (struct btrfs_root_ref *)(search_header + 1);
  81         if (search_header->offset != BTRFS_FS_TREE_OBJECTID) {
  82                 int sub_ret;
  83
  84                 sub_ret = btrfs_subvolid_resolve_sub(fd, path, path_len,
  85                                                      search_header->offset);
  86                 if (sub_ret)
  87                         return sub_ret;
  88                 if (*path_len < 1)
  89                         return -EOVERFLOW;
  90                 strcat(path, "/");
  91                 (*path_len)--;
  92         }
  93
  94         if (btrfs_stack_root_ref_dirid(backref_item) !=
  95             BTRFS_FIRST_FREE_OBJECTID) {
  96                 int len;
  97
  98                 memset(&ino_lookup_arg, 0, sizeof(ino_lookup_arg));
  99                 ino_lookup_arg.treeid = search_header->offset;
 100                 ino_lookup_arg.objectid =
 101                         btrfs_stack_root_ref_dirid(backref_item);
 102                 ret = ioctl(fd, BTRFS_IOC_INO_LOOKUP, &ino_lookup_arg);
 103                 if (ret) {
 104                         fprintf(stderr,
 105                                 "ioctl(BTRFS_IOC_INO_LOOKUP) ret=%d, error: %s\n",
 106                                 ret, strerror(errno));
 107                         return ret;
 108                 }
 109
 110                 len = strlen(ino_lookup_arg.name);
 111                 if (*path_len < len)
 112                         return -EOVERFLOW;
 113                 strcat(path, ino_lookup_arg.name);
 114                 (*path_len) -= len;
 115         }
 116
 117         if (*path_len < btrfs_stack_root_ref_name_len(backref_item))
 118                 return -EOVERFLOW;
 119         strncat(path, (char *)(backref_item + 1),
 120                 btrfs_stack_root_ref_name_len(backref_item));
 121         (*path_len) -= btrfs_stack_root_ref_name_len(backref_item);
 122         return 0;
 123 }
 124
 125 static struct rb_node *tree_insert(struct rb_root *root,
 126                                    struct subvol_info *si,
 127                                    enum subvol_search_type type)
 128 {
 129         struct rb_node ** p = &root->rb_node;
 130         struct rb_node * parent = NULL;
 131         struct subvol_info *entry;
 132         __s64 comp;
 133
 134         while(*p) {
 135                 parent = *p;
 136                 if (type == subvol_search_by_received_uuid) {
 137                         entry = rb_entry(parent, struct subvol_info,
 138                                         rb_received_node);
 139
 140                         comp = memcmp(entry->received_uuid, si->received_uuid,
 141                                         BTRFS_UUID_SIZE);
 142                         if (!comp) {
 143                                 if (entry->stransid < si->stransid)
 144                                         comp = -1;
 145                                 else if (entry->stransid > si->stransid)
 146                                         comp = 1;
 147                                 else
 148                                         comp = 0;
 149                         }
 150                 } else if (type == subvol_search_by_uuid) {
 151                         entry = rb_entry(parent, struct subvol_info,
 152                                         rb_local_node);
 153                         comp = memcmp(entry->uuid, si->uuid, BTRFS_UUID_SIZE);
 154                 } else if (type == subvol_search_by_root_id) {
 155                         entry = rb_entry(parent, struct subvol_info,
 156                                         rb_root_id_node);
 157                         comp = entry->root_id - si->root_id;
 158                 } else if (type == subvol_search_by_path) {
 159                         entry = rb_entry(parent, struct subvol_info,
 160                                         rb_path_node);
 161                         comp = strcmp(entry->path, si->path);
 162                 } else {
 163                         BUG();
 164                 }
 165
 166                 if (comp < 0)
 167                         p = &(*p)->rb_left;
 168                 else if (comp > 0)
 169                         p = &(*p)->rb_right;
 170                 else
 171                         return parent;
 172         }
 173
 174         if (type == subvol_search_by_received_uuid) {
 175                 rb_link_node(&si->rb_received_node, parent, p);
 176                 rb_insert_color(&si->rb_received_node, root);
 177         } else if (type == subvol_search_by_uuid) {
 178                 rb_link_node(&si->rb_local_node, parent, p);
 179                 rb_insert_color(&si->rb_local_node, root);
 180         } else if (type == subvol_search_by_root_id) {
 181                 rb_link_node(&si->rb_root_id_node, parent, p);
 182                 rb_insert_color(&si->rb_root_id_node, root);
 183         } else if (type == subvol_search_by_path) {
 184                 rb_link_node(&si->rb_path_node, parent, p);
 185                 rb_insert_color(&si->rb_path_node, root);
 186         }
 187         return NULL;
 188 }
 189
 190 static struct subvol_info *tree_search(struct rb_root *root,
 191                                        u64 root_id, const u8 *uuid,
 192                                        u64 stransid, const char *path,
 193                                        enum subvol_search_type type)
 194 {
 195         struct rb_node * n = root->rb_node;
 196         struct subvol_info *entry;
 197         __s64 comp;
 198
 199         while(n) {
 200                 if (type == subvol_search_by_received_uuid) {
 201                         entry = rb_entry(n, struct subvol_info,
 202                                         rb_received_node);
 203                         comp = memcmp(entry->received_uuid, uuid,
 204                                         BTRFS_UUID_SIZE);
 205                         if (!comp) {
 206                                 if (entry->stransid < stransid)
 207                                         comp = -1;
 208                                 else if (entry->stransid > stransid)
 209                                         comp = 1;
 210                                 else
 211                                         comp = 0;
 212                         }
 213                 } else if (type == subvol_search_by_uuid) {
 214                         entry = rb_entry(n, struct subvol_info, rb_local_node);
 215                         comp = memcmp(entry->uuid, uuid, BTRFS_UUID_SIZE);
 216                 } else if (type == subvol_search_by_root_id) {
 217                         entry = rb_entry(n, struct subvol_info, rb_root_id_node);
 218                         comp = entry->root_id - root_id;
 219                 } else if (type == subvol_search_by_path) {
 220                         entry = rb_entry(n, struct subvol_info, rb_path_node);
 221                         comp = strcmp(entry->path, path);
 222                 } else {
 223                         BUG();
 224                 }
 225                 if (comp < 0)
 226                         n = n->rb_left;
 227                 else if (comp > 0)
 228                         n = n->rb_right;
 229                 else
 230                         return entry;
 231         }
 232         return NULL;
 233 }
 234
 235 static int count_bytes(void *buf, int len, char b)
 236 {
 237         int cnt = 0;
 238         int i;
 239         for (i = 0; i < len; i++) {
 240                 if (((char*)buf)[i] == b)
 241                         cnt++;
 242         }
 243         return cnt;
 244 }
 245
 246 void subvol_uuid_search_add(struct subvol_uuid_search *s,
 247                             struct subvol_info *si)
 248 {
 249         int cnt;
 250
 251         tree_insert(&s->root_id_subvols, si, subvol_search_by_root_id);
 252         tree_insert(&s->path_subvols, si, subvol_search_by_path);
 253
 254         cnt = count_bytes(si->uuid, BTRFS_UUID_SIZE, 0);
 255         if (cnt != BTRFS_UUID_SIZE)
 256                 tree_insert(&s->local_subvols, si, subvol_search_by_uuid);
 257         cnt = count_bytes(si->received_uuid, BTRFS_UUID_SIZE, 0);
 258         if (cnt != BTRFS_UUID_SIZE)
 259                 tree_insert(&s->received_subvols, si,
 260                                 subvol_search_by_received_uuid);
 261 }
 262
 263 struct subvol_info *subvol_uuid_search(struct subvol_uuid_search *s,
 264                                        u64 root_id, const u8 *uuid, u64 transid,
 265                                        const char *path,
 266                                        enum subvol_search_type type)
 267 {
 268         struct rb_root *root;
 269         if (type == subvol_search_by_received_uuid)
 270                 root = &s->received_subvols;
 271         else if (type == subvol_search_by_uuid)
 272                 root = &s->local_subvols;
 273         else if (type == subvol_search_by_root_id)
 274                 root = &s->root_id_subvols;
 275         else if (type == subvol_search_by_path)
 276                 root = &s->path_subvols;
 277         else
 278                 return NULL;
 279         return tree_search(root, root_id, uuid, transid, path, type);
 280 }
 281
 282 int subvol_uuid_search_init(int mnt_fd, struct subvol_uuid_search *s)
 283 {
 284         int ret;
 285         struct btrfs_ioctl_search_args args;
 286         struct btrfs_ioctl_search_key *sk = &args.key;
 287         struct btrfs_ioctl_search_header *sh;
 288         struct btrfs_root_item *root_item_ptr;
 289         struct btrfs_root_item root_item;
 290         struct subvol_info *si = NULL;
 291         int root_item_valid = 0;
 292         unsigned long off = 0;
 293         int i;
 294         int e;
 295         char *path;
 296
 297         memset(&args, 0, sizeof(args));
 298
 299         sk->tree_id = BTRFS_ROOT_TREE_OBJECTID;
 300
 301         sk->max_objectid = (u64)-1;
 302         sk->max_offset = (u64)-1;
 303         sk->max_transid = (u64)-1;
 304         sk->min_type = BTRFS_ROOT_ITEM_KEY;
 305         sk->max_type = BTRFS_ROOT_BACKREF_KEY;
 306         sk->nr_items = 4096;
 307
 308         while(1) {
 309                 ret = ioctl(mnt_fd, BTRFS_IOC_TREE_SEARCH, &args);
 310                 e = errno;
 311                 if (ret < 0) {
 312                         fprintf(stderr, "ERROR: can't perform the search- %s\n",
 313                                 strerror(e));
 314                         return ret;
 315                 }
 316                 if (sk->nr_items == 0)
 317                         break;
 318
 319                 off = 0;
 320
 321                 for (i = 0; i < sk->nr_items; i++) {
 322                         sh = (struct btrfs_ioctl_search_header *)(args.buf +
 323                                                                   off);
 324                         off += sizeof(*sh);
 325
 326                         if ((sh->objectid != 5 &&
 327                             sh->objectid < BTRFS_FIRST_FREE_OBJECTID) ||
 328                             sh->objectid > BTRFS_LAST_FREE_OBJECTID)
 329                                 goto skip;
 330
 331                         if (sh->type == BTRFS_ROOT_ITEM_KEY) {
 332                                 /* older kernels don't have uuids+times */
 333                                 if (sh->len < sizeof(root_item)) {
 334                                         root_item_valid = 0;
 335                                         goto skip;
 336                                 }
 337                                 root_item_ptr = (struct btrfs_root_item *)
 338                                                 (args.buf + off);
 339                                 memcpy(&root_item, root_item_ptr,
 340                                                 sizeof(root_item));
 341                                 root_item_valid = 1;
 342                         } else if (sh->type == BTRFS_ROOT_BACKREF_KEY ||
 343                                    root_item_valid) {
 344                                 if (!root_item_valid)
 345                                         goto skip;
 346
 347                                 path = btrfs_list_path_for_root(mnt_fd,
 348                                                                 sh->objectid);
 349                                 if (!path)
 350                                         path = strdup("");
 351                                 if (IS_ERR(path)) {
 352                                         ret = PTR_ERR(path);
 353                                         fprintf(stderr, "ERROR: unable to "
 354                                                         "resolve path "
 355                                                         "for root %llu\n",
 356                                                         sh->objectid);
 357                                         goto out;
 358                                 }
 359
 360                                 si = calloc(1, sizeof(*si));
 361                                 si->root_id = sh->objectid;
 362                                 memcpy(si->uuid, root_item.uuid,
 363                                                 BTRFS_UUID_SIZE);
 364                                 memcpy(si->parent_uuid, root_item.parent_uuid,
 365                                                 BTRFS_UUID_SIZE);
 366                                 memcpy(si->received_uuid,
 367                                                 root_item.received_uuid,
 368                                                 BTRFS_UUID_SIZE);
 369                                 si->ctransid = btrfs_root_ctransid(&root_item);
 370                                 si->otransid = btrfs_root_otransid(&root_item);
 371                                 si->stransid = btrfs_root_stransid(&root_item);
 372                                 si->rtransid = btrfs_root_rtransid(&root_item);
 373                                 si->path = path;
 374                                 subvol_uuid_search_add(s, si);
 375                                 root_item_valid = 0;
 376                         } else {
 377                                 goto skip;
 378                         }
 379
 380 skip:
 381                         off += sh->len;
 382
 383                         /*
 384                          * record the mins in sk so we can make sure the
 385                          * next search doesn't repeat this root
 386                          */
 387                         sk->min_objectid = sh->objectid;
 388                         sk->min_offset = sh->offset;
 389                         sk->min_type = sh->type;
 390                 }
 391                 sk->nr_items = 4096;
 392                 if (sk->min_offset < (u64)-1)
 393                         sk->min_offset++;
 394                 else if (sk->min_objectid < (u64)-1) {
 395                         sk->min_objectid++;
 396                         sk->min_offset = 0;
 397                         sk->min_type = 0;
 398                 } else
 399                         break;
 400         }
 401
 402 out:
 403         return ret;
 404 }
 405
 406 /*
 407  * It's safe to call this function even without the subvol_uuid_search_init()
 408  * call before as long as the subvol_uuid_search structure is all-zero.
 409  */
 410 void subvol_uuid_search_finit(struct subvol_uuid_search *s)
 411 {
 412         struct rb_root *root = &s->root_id_subvols;
 413         struct rb_node *node;
 414
 415         while ((node = rb_first(root))) {
 416                 struct subvol_info *entry =
 417                         rb_entry(node, struct subvol_info, rb_root_id_node);
 418
 419                 free(entry->path);
 420                 rb_erase(node, root);
 421                 free(entry);
 422         }
 423
 424         s->root_id_subvols = RB_ROOT;
 425         s->local_subvols = RB_ROOT;
 426         s->received_subvols = RB_ROOT;
 427         s->path_subvols = RB_ROOT;
 428 }
 429
 430 char *path_cat(const char *p1, const char *p2)
 431 {
 432         int p1_len = strlen(p1);
 433         int p2_len = strlen(p2);
 434         char *new = malloc(p1_len + p2_len + 2);
 435
 436         if (p1_len && p1[p1_len - 1] == '/')
 437                 p1_len--;
 438         if (p2_len && p2[p2_len - 1] == '/')
 439                 p2_len--;
 440         sprintf(new, "%.*s/%.*s", p1_len, p1, p2_len, p2);
 441         return new;
 442 }
 443
 444
 445 char *path_cat3(const char *p1, const char *p2, const char *p3)
 446 {
 447         int p1_len = strlen(p1);
 448         int p2_len = strlen(p2);
 449         int p3_len = strlen(p3);
 450         char *new = malloc(p1_len + p2_len + p3_len + 3);
 451
 452         if (p1_len && p1[p1_len - 1] == '/')
 453                 p1_len--;
 454         if (p2_len && p2[p2_len - 1] == '/')
 455                 p2_len--;
 456         if (p3_len && p3[p3_len - 1] == '/')
 457                 p3_len--;
 458         sprintf(new, "%.*s/%.*s/%.*s", p1_len, p1, p2_len, p2, p3_len, p3);
 459         return new;
 460 }
 461