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 struct rb_node *tree_insert(struct rb_root *root,
  27                                    struct subvol_info *si,
  28                                    enum subvol_search_type type)
  29 {
  30         struct rb_node ** p = &root->rb_node;
  31         struct rb_node * parent = NULL;
  32         struct subvol_info *entry;
  33         __s64 comp;
  34
  35         while(*p) {
  36                 parent = *p;
  37                 if (type == subvol_search_by_received_uuid) {
  38                         entry = rb_entry(parent, struct subvol_info,
  39                                         rb_received_node);
  40
  41                         comp = memcmp(entry->received_uuid, si->received_uuid,
  42                                         BTRFS_UUID_SIZE);
  43                         if (!comp) {
  44                                 if (entry->stransid < si->stransid)
  45                                         comp = -1;
  46                                 else if (entry->stransid > si->stransid)
  47                                         comp = 1;
  48                                 else
  49                                         comp = 0;
  50                         }
  51                 } else if (type == subvol_search_by_uuid) {
  52                         entry = rb_entry(parent, struct subvol_info,
  53                                         rb_local_node);
  54                         comp = memcmp(entry->uuid, si->uuid, BTRFS_UUID_SIZE);
  55                 } else if (type == subvol_search_by_root_id) {
  56                         entry = rb_entry(parent, struct subvol_info,
  57                                         rb_root_id_node);
  58                         comp = entry->root_id - si->root_id;
  59                 } else if (type == subvol_search_by_path) {
  60                         entry = rb_entry(parent, struct subvol_info,
  61                                         rb_path_node);
  62                         comp = strcmp(entry->path, si->path);
  63                 } else {
  64                         BUG();
  65                 }
  66
  67                 if (comp < 0)
  68                         p = &(*p)->rb_left;
  69                 else if (comp > 0)
  70                         p = &(*p)->rb_right;
  71                 else
  72                         return parent;
  73         }
  74
  75         if (type == subvol_search_by_received_uuid) {
  76                 rb_link_node(&si->rb_received_node, parent, p);
  77                 rb_insert_color(&si->rb_received_node, root);
  78         } else if (type == subvol_search_by_uuid) {
  79                 rb_link_node(&si->rb_local_node, parent, p);
  80                 rb_insert_color(&si->rb_local_node, root);
  81         } else if (type == subvol_search_by_root_id) {
  82                 rb_link_node(&si->rb_root_id_node, parent, p);
  83                 rb_insert_color(&si->rb_root_id_node, root);
  84         } else if (type == subvol_search_by_path) {
  85                 rb_link_node(&si->rb_path_node, parent, p);
  86                 rb_insert_color(&si->rb_path_node, root);
  87         }
  88         return NULL;
  89 }
  90
  91 static struct subvol_info *tree_search(struct rb_root *root,
  92                                        u64 root_id, const u8 *uuid,
  93                                        u64 stransid, const char *path,
  94                                        enum subvol_search_type type)
  95 {
  96         struct rb_node * n = root->rb_node;
  97         struct subvol_info *entry;
  98         __s64 comp;
  99
 100         while(n) {
 101                 if (type == subvol_search_by_received_uuid) {
 102                         entry = rb_entry(n, struct subvol_info,
 103                                         rb_received_node);
 104                         comp = memcmp(entry->received_uuid, uuid,
 105                                         BTRFS_UUID_SIZE);
 106                         if (!comp) {
 107                                 if (entry->stransid < stransid)
 108                                         comp = -1;
 109                                 else if (entry->stransid > stransid)
 110                                         comp = 1;
 111                                 else
 112                                         comp = 0;
 113                         }
 114                 } else if (type == subvol_search_by_uuid) {
 115                         entry = rb_entry(n, struct subvol_info, rb_local_node);
 116                         comp = memcmp(entry->uuid, uuid, BTRFS_UUID_SIZE);
 117                 } else if (type == subvol_search_by_root_id) {
 118                         entry = rb_entry(n, struct subvol_info, rb_root_id_node);
 119                         comp = entry->root_id - root_id;
 120                 } else if (type == subvol_search_by_path) {
 121                         entry = rb_entry(n, struct subvol_info, rb_path_node);
 122                         comp = strcmp(entry->path, path);
 123                 } else {
 124                         BUG();
 125                 }
 126                 if (comp < 0)
 127                         n = n->rb_left;
 128                 else if (comp > 0)
 129                         n = n->rb_right;
 130                 else
 131                         return entry;
 132         }
 133         return NULL;
 134 }
 135
 136 static int count_bytes(void *buf, int len, char b)
 137 {
 138         int cnt = 0;
 139         int i;
 140         for (i = 0; i < len; i++) {
 141                 if (((char*)buf)[i] == b)
 142                         cnt++;
 143         }
 144         return cnt;
 145 }
 146
 147 void subvol_uuid_search_add(struct subvol_uuid_search *s,
 148                             struct subvol_info *si)
 149 {
 150         int cnt;
 151
 152         tree_insert(&s->root_id_subvols, si, subvol_search_by_root_id);
 153         tree_insert(&s->path_subvols, si, subvol_search_by_path);
 154
 155         cnt = count_bytes(si->uuid, BTRFS_UUID_SIZE, 0);
 156         if (cnt != BTRFS_UUID_SIZE)
 157                 tree_insert(&s->local_subvols, si, subvol_search_by_uuid);
 158         cnt = count_bytes(si->received_uuid, BTRFS_UUID_SIZE, 0);
 159         if (cnt != BTRFS_UUID_SIZE)
 160                 tree_insert(&s->received_subvols, si,
 161                                 subvol_search_by_received_uuid);
 162 }
 163
 164 struct subvol_info *subvol_uuid_search(struct subvol_uuid_search *s,
 165                                        u64 root_id, const u8 *uuid, u64 transid,
 166                                        const char *path,
 167                                        enum subvol_search_type type)
 168 {
 169         struct rb_root *root;
 170         if (type == subvol_search_by_received_uuid)
 171                 root = &s->received_subvols;
 172         else if (type == subvol_search_by_uuid)
 173                 root = &s->local_subvols;
 174         else if (type == subvol_search_by_root_id)
 175                 root = &s->root_id_subvols;
 176         else if (type == subvol_search_by_path)
 177                 root = &s->path_subvols;
 178         else
 179                 return NULL;
 180         return tree_search(root, root_id, uuid, transid, path, type);
 181 }
 182
 183 int subvol_uuid_search_init(int mnt_fd, struct subvol_uuid_search *s)
 184 {
 185         int ret;
 186         struct btrfs_ioctl_search_args args;
 187         struct btrfs_ioctl_search_key *sk = &args.key;
 188         struct btrfs_ioctl_search_header *sh;
 189         struct btrfs_root_item *root_item_ptr;
 190         struct btrfs_root_item root_item;
 191         struct subvol_info *si = NULL;
 192         int root_item_valid = 0;
 193         unsigned long off = 0;
 194         int i;
 195         int e;
 196         char *path;
 197
 198         memset(&args, 0, sizeof(args));
 199
 200         sk->tree_id = BTRFS_ROOT_TREE_OBJECTID;
 201
 202         sk->max_objectid = (u64)-1;
 203         sk->max_offset = (u64)-1;
 204         sk->max_transid = (u64)-1;
 205         sk->min_type = BTRFS_ROOT_ITEM_KEY;
 206         sk->max_type = BTRFS_ROOT_BACKREF_KEY;
 207         sk->nr_items = 4096;
 208
 209         while(1) {
 210                 ret = ioctl(mnt_fd, BTRFS_IOC_TREE_SEARCH, &args);
 211                 e = errno;
 212                 if (ret < 0) {
 213                         fprintf(stderr, "ERROR: can't perform the search- %s\n",
 214                                 strerror(e));
 215                         return ret;
 216                 }
 217                 if (sk->nr_items == 0)
 218                         break;
 219
 220                 off = 0;
 221
 222                 for (i = 0; i < sk->nr_items; i++) {
 223                         sh = (struct btrfs_ioctl_search_header *)(args.buf +
 224                                                                   off);
 225                         off += sizeof(*sh);
 226
 227                         if ((sh->objectid != 5 &&
 228                             sh->objectid < BTRFS_FIRST_FREE_OBJECTID) ||
 229                             sh->objectid > BTRFS_LAST_FREE_OBJECTID)
 230                                 goto skip;
 231
 232                         if (sh->type == BTRFS_ROOT_ITEM_KEY) {
 233                                 /* older kernels don't have uuids+times */
 234                                 if (sh->len < sizeof(root_item)) {
 235                                         root_item_valid = 0;
 236                                         goto skip;
 237                                 }
 238                                 root_item_ptr = (struct btrfs_root_item *)
 239                                                 (args.buf + off);
 240                                 memcpy(&root_item, root_item_ptr,
 241                                                 sizeof(root_item));
 242                                 root_item_valid = 1;
 243                         } else if (sh->type == BTRFS_ROOT_BACKREF_KEY ||
 244                                    root_item_valid) {
 245                                 if (!root_item_valid)
 246                                         goto skip;
 247
 248                                 path = btrfs_list_path_for_root(mnt_fd,
 249                                                                 sh->objectid);
 250                                 if (!path)
 251                                         path = strdup("");
 252                                 if (IS_ERR(path)) {
 253                                         ret = PTR_ERR(path);
 254                                         fprintf(stderr, "ERROR: unable to "
 255                                                         "resolve path "
 256                                                         "for root %llu\n",
 257                                                         sh->objectid);
 258                                         goto out;
 259                                 }
 260
 261                                 si = calloc(1, sizeof(*si));
 262                                 si->root_id = sh->objectid;
 263                                 memcpy(si->uuid, root_item.uuid,
 264                                                 BTRFS_UUID_SIZE);
 265                                 memcpy(si->parent_uuid, root_item.parent_uuid,
 266                                                 BTRFS_UUID_SIZE);
 267                                 memcpy(si->received_uuid,
 268                                                 root_item.received_uuid,
 269                                                 BTRFS_UUID_SIZE);
 270                                 si->ctransid = btrfs_root_ctransid(&root_item);
 271                                 si->otransid = btrfs_root_otransid(&root_item);
 272                                 si->stransid = btrfs_root_stransid(&root_item);
 273                                 si->rtransid = btrfs_root_rtransid(&root_item);
 274                                 si->path = path;
 275                                 subvol_uuid_search_add(s, si);
 276                                 root_item_valid = 0;
 277                         } else {
 278                                 goto skip;
 279                         }
 280
 281 skip:
 282                         off += sh->len;
 283
 284                         /*
 285                          * record the mins in sk so we can make sure the
 286                          * next search doesn't repeat this root
 287                          */
 288                         sk->min_objectid = sh->objectid;
 289                         sk->min_offset = sh->offset;
 290                         sk->min_type = sh->type;
 291                 }
 292                 sk->nr_items = 4096;
 293                 if (sk->min_offset < (u64)-1)
 294                         sk->min_offset++;
 295                 else if (sk->min_objectid < (u64)-1) {
 296                         sk->min_objectid++;
 297                         sk->min_offset = 0;
 298                         sk->min_type = 0;
 299                 } else
 300                         break;
 301         }
 302
 303 out:
 304         return ret;
 305 }
 306
 307 /*
 308  * It's safe to call this function even without the subvol_uuid_search_init()
 309  * call before as long as the subvol_uuid_search structure is all-zero.
 310  */
 311 void subvol_uuid_search_finit(struct subvol_uuid_search *s)
 312 {
 313         struct rb_root *root = &s->root_id_subvols;
 314         struct rb_node *node;
 315
 316         while ((node = rb_first(root))) {
 317                 struct subvol_info *entry =
 318                         rb_entry(node, struct subvol_info, rb_root_id_node);
 319
 320                 free(entry->path);
 321                 rb_erase(node, root);
 322                 free(entry);
 323         }
 324
 325         s->root_id_subvols = RB_ROOT;
 326         s->local_subvols = RB_ROOT;
 327         s->received_subvols = RB_ROOT;
 328         s->path_subvols = RB_ROOT;
 329 }
 330
 331 char *path_cat(const char *p1, const char *p2)
 332 {
 333         int p1_len = strlen(p1);
 334         int p2_len = strlen(p2);
 335         char *new = malloc(p1_len + p2_len + 3);
 336
 337         if (p1_len && p1[p1_len - 1] == '/')
 338                 p1_len--;
 339         if (p2_len && p2[p2_len - 1] == '/')
 340                 p2_len--;
 341         sprintf(new, "%.*s/%.*s", p1_len, p1, p2_len, p2);
 342         return new;
 343 }
 344
 345
 346 char *path_cat3(const char *p1, const char *p2, const char *p3)
 347 {
 348         int p1_len = strlen(p1);
 349         int p2_len = strlen(p2);
 350         int p3_len = strlen(p3);
 351         char *new = malloc(p1_len + p2_len + p3_len + 4);
 352
 353         if (p1_len && p1[p1_len - 1] == '/')
 354                 p1_len--;
 355         if (p2_len && p2[p2_len - 1] == '/')
 356                 p2_len--;
 357         if (p3_len && p3[p3_len - 1] == '/')
 358                 p3_len--;
 359         sprintf(new, "%.*s/%.*s/%.*s", p1_len, p1, p2_len, p2, p3_len, p3);
 360         return new;
 361 }
 362