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