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                 }
  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                 }
 124                 if (comp < 0)
 125                         n = n->rb_left;
 126                 else if (comp > 0)
 127                         n = n->rb_right;
 128                 else
 129                         return entry;
 130         }
 131         return NULL;
 132 }
 133
 134 static int count_bytes(void *buf, int len, char b)
 135 {
 136         int cnt = 0;
 137         int i;
 138         for (i = 0; i < len; i++) {
 139                 if (((char*)buf)[i] == b)
 140                         cnt++;
 141         }
 142         return cnt;
 143 }
 144
 145 void subvol_uuid_search_add(struct subvol_uuid_search *s,
 146                             struct subvol_info *si)
 147 {
 148         int cnt;
 149
 150         tree_insert(&s->root_id_subvols, si, subvol_search_by_root_id);
 151         tree_insert(&s->path_subvols, si, subvol_search_by_path);
 152
 153         cnt = count_bytes(si->uuid, BTRFS_UUID_SIZE, 0);
 154         if (cnt != BTRFS_UUID_SIZE)
 155                 tree_insert(&s->local_subvols, si, subvol_search_by_uuid);
 156         cnt = count_bytes(si->received_uuid, BTRFS_UUID_SIZE, 0);
 157         if (cnt != BTRFS_UUID_SIZE)
 158                 tree_insert(&s->received_subvols, si,
 159                                 subvol_search_by_received_uuid);
 160 }
 161
 162 struct subvol_info *subvol_uuid_search(struct subvol_uuid_search *s,
 163                                        u64 root_id, const u8 *uuid, u64 transid,
 164                                        const char *path,
 165                                        enum subvol_search_type type)
 166 {
 167         struct rb_root *root;
 168         if (type == subvol_search_by_received_uuid)
 169                 root = &s->received_subvols;
 170         else if (type == subvol_search_by_uuid)
 171                 root = &s->local_subvols;
 172         else if (type == subvol_search_by_root_id)
 173                 root = &s->root_id_subvols;
 174         else if (type == subvol_search_by_path)
 175                 root = &s->path_subvols;
 176         else
 177                 return NULL;
 178         return tree_search(root, root_id, uuid, transid, path, type);
 179 }
 180
 181 int subvol_uuid_search_init(int mnt_fd, struct subvol_uuid_search *s)
 182 {
 183         int ret;
 184         struct btrfs_ioctl_search_args args;
 185         struct btrfs_ioctl_search_key *sk = &args.key;
 186         struct btrfs_ioctl_search_header *sh;
 187         struct btrfs_root_item *root_item_ptr;
 188         struct btrfs_root_item root_item;
 189         struct subvol_info *si = NULL;
 190         int root_item_valid = 0;
 191         unsigned long off = 0;
 192         int i;
 193         int e;
 194         char *path;
 195
 196         memset(&args, 0, sizeof(args));
 197
 198         sk->tree_id = BTRFS_ROOT_TREE_OBJECTID;
 199
 200         sk->max_objectid = (u64)-1;
 201         sk->max_offset = (u64)-1;
 202         sk->max_transid = (u64)-1;
 203         sk->min_type = BTRFS_ROOT_ITEM_KEY;
 204         sk->max_type = BTRFS_ROOT_BACKREF_KEY;
 205         sk->nr_items = 4096;
 206
 207         while(1) {
 208                 ret = ioctl(mnt_fd, BTRFS_IOC_TREE_SEARCH, &args);
 209                 e = errno;
 210                 if (ret < 0) {
 211                         fprintf(stderr, "ERROR: can't perform the search- %s\n",
 212                                 strerror(e));
 213                         return ret;
 214                 }
 215                 if (sk->nr_items == 0)
 216                         break;
 217
 218                 off = 0;
 219
 220                 for (i = 0; i < sk->nr_items; i++) {
 221                         sh = (struct btrfs_ioctl_search_header *)(args.buf +
 222                                                                   off);
 223                         off += sizeof(*sh);
 224
 225                         if ((sh->objectid != 5 &&
 226                             sh->objectid < BTRFS_FIRST_FREE_OBJECTID) ||
 227                             sh->objectid == BTRFS_FREE_INO_OBJECTID)
 228                                 goto skip;
 229
 230                         if (sh->type == BTRFS_ROOT_ITEM_KEY) {
 231                                 /* older kernels don't have uuids+times */
 232                                 if (sh->len < sizeof(root_item)) {
 233                                         root_item_valid = 0;
 234                                         goto skip;
 235                                 }
 236                                 root_item_ptr = (struct btrfs_root_item *)
 237                                                 (args.buf + off);
 238                                 memcpy(&root_item, root_item_ptr,
 239                                                 sizeof(root_item));
 240                                 root_item_valid = 1;
 241                         } else if (sh->type == BTRFS_ROOT_BACKREF_KEY) {
 242                                 if (!root_item_valid)
 243                                         goto skip;
 244
 245                                 path = path_for_root(mnt_fd, sh->objectid);
 246                                 if (!path)
 247                                         path = strdup("");
 248                                 if (IS_ERR(path)) {
 249                                         ret = PTR_ERR(path);
 250                                         fprintf(stderr, "ERROR: unable to "
 251                                                         "resolve path "
 252                                                         "for root %llu\n",
 253                                                         sh->objectid);
 254                                         goto out;
 255                                 }
 256
 257                                 si = calloc(1, sizeof(*si));
 258                                 si->root_id = sh->objectid;
 259                                 memcpy(si->uuid, root_item.uuid,
 260                                                 BTRFS_UUID_SIZE);
 261                                 memcpy(si->parent_uuid, root_item.parent_uuid,
 262                                                 BTRFS_UUID_SIZE);
 263                                 memcpy(si->received_uuid,
 264                                                 root_item.received_uuid,
 265                                                 BTRFS_UUID_SIZE);
 266                                 si->ctransid = btrfs_root_ctransid(&root_item);
 267                                 si->otransid = btrfs_root_otransid(&root_item);
 268                                 si->stransid = btrfs_root_stransid(&root_item);
 269                                 si->rtransid = btrfs_root_rtransid(&root_item);
 270                                 si->path = path;
 271                                 subvol_uuid_search_add(s, si);
 272                                 root_item_valid = 0;
 273                         } else {
 274                                 root_item_valid = 0;
 275                                 goto skip;
 276                         }
 277
 278 skip:
 279                         off += sh->len;
 280
 281                         /*
 282                          * record the mins in sk so we can make sure the
 283                          * next search doesn't repeat this root
 284                          */
 285                         sk->min_objectid = sh->objectid;
 286                         sk->min_offset = sh->offset;
 287                         sk->min_type = sh->type;
 288                 }
 289                 sk->nr_items = 4096;
 290                 if (sk->min_offset < (u64)-1)
 291                         sk->min_offset++;
 292                 else if (sk->min_objectid < (u64)-1) {
 293                         sk->min_objectid++;
 294                         sk->min_offset = 0;
 295                         sk->min_type = 0;
 296                 } else
 297                         break;
 298         }
 299
 300 out:
 301         return ret;
 302 }
 303
 304
 305 char *path_cat(const char *p1, const char *p2)
 306 {
 307         int p1_len = strlen(p1);
 308         int p2_len = strlen(p2);
 309         char *new = malloc(p1_len + p2_len + 3);
 310
 311         if (p1_len && p1[p1_len - 1] == '/')
 312                 p1_len--;
 313         if (p2_len && p2[p2_len - 1] == '/')
 314                 p2_len--;
 315         sprintf(new, "%.*s/%.*s", p1_len, p1, p2_len, p2);
 316         return new;
 317 }
 318
 319
 320 char *path_cat3(const char *p1, const char *p2, const char *p3)
 321 {
 322         int p1_len = strlen(p1);
 323         int p2_len = strlen(p2);
 324         int p3_len = strlen(p3);
 325         char *new = malloc(p1_len + p2_len + p3_len + 4);
 326
 327         if (p1_len && p1[p1_len - 1] == '/')
 328                 p1_len--;
 329         if (p2_len && p2[p2_len - 1] == '/')
 330                 p2_len--;
 331         if (p3_len && p3[p3_len - 1] == '/')
 332                 p3_len--;
 333         sprintf(new, "%.*s/%.*s/%.*s", p1_len, p1, p2_len, p2, p3_len, p3);
 334         return new;
 335 }
 336