fs/btrfs/send.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 <linux/bsearch.h>
  20 #include <linux/fs.h>
  21 #include <linux/file.h>
  22 #include <linux/sort.h>
  23 #include <linux/mount.h>
  24 #include <linux/xattr.h>
  25 #include <linux/posix_acl_xattr.h>
  26 #include <linux/radix-tree.h>
  27 #include <linux/crc32c.h>
  28 #include <linux/vmalloc.h>
  29
  30 #include "send.h"
  31 #include "backref.h"
  32 #include "locking.h"
  33 #include "disk-io.h"
  34 #include "btrfs_inode.h"
  35 #include "transaction.h"
  36
  37 static int g_verbose = 0;
  38
  39 #define verbose_printk(...) if (g_verbose) printk(__VA_ARGS__)
  40
  41 /*
  42  * A fs_path is a helper to dynamically build path names with unknown size.
  43  * It reallocates the internal buffer on demand.
  44  * It allows fast adding of path elements on the right side (normal path) and
  45  * fast adding to the left side (reversed path). A reversed path can also be
  46  * unreversed if needed.
  47  */
  48 struct fs_path {
  49         union {
  50                 struct {
  51                         char *start;
  52                         char *end;
  53                         char *prepared;
  54
  55                         char *buf;
  56                         int buf_len;
  57                         int reversed:1;
  58                         int virtual_mem:1;
  59                         char inline_buf[];
  60                 };
  61                 char pad[PAGE_SIZE];
  62         };
  63 };
  64 #define FS_PATH_INLINE_SIZE \
  65         (sizeof(struct fs_path) - offsetof(struct fs_path, inline_buf))
  66
  67
  68 /* reused for each extent */
  69 struct clone_root {
  70         struct btrfs_root *root;
  71         u64 ino;
  72         u64 offset;
  73
  74         u64 found_refs;
  75 };
  76
  77 #define SEND_CTX_MAX_NAME_CACHE_SIZE 128
  78 #define SEND_CTX_NAME_CACHE_CLEAN_SIZE (SEND_CTX_MAX_NAME_CACHE_SIZE * 2)
  79
  80 struct send_ctx {
  81         struct file *send_filp;
  82         loff_t send_off;
  83         char *send_buf;
  84         u32 send_size;
  85         u32 send_max_size;
  86         u64 total_send_size;
  87         u64 cmd_send_size[BTRFS_SEND_C_MAX + 1];
  88
  89         struct vfsmount *mnt;
  90
  91         struct btrfs_root *send_root;
  92         struct btrfs_root *parent_root;
  93         struct clone_root *clone_roots;
  94         int clone_roots_cnt;
  95
  96         /* current state of the compare_tree call */
  97         struct btrfs_path *left_path;
  98         struct btrfs_path *right_path;
  99         struct btrfs_key *cmp_key;
 100
 101         /*
 102          * infos of the currently processed inode. In case of deleted inodes,
 103          * these are the values from the deleted inode.
 104          */
 105         u64 cur_ino;
 106         u64 cur_inode_gen;
 107         int cur_inode_new;
 108         int cur_inode_new_gen;
 109         int cur_inode_deleted;
 110         int cur_inode_first_ref_orphan;
 111         u64 cur_inode_size;
 112         u64 cur_inode_mode;
 113
 114         u64 send_progress;
 115
 116         struct list_head new_refs;
 117         struct list_head deleted_refs;
 118
 119         struct radix_tree_root name_cache;
 120         struct list_head name_cache_list;
 121         int name_cache_size;
 122
 123         struct file *cur_inode_filp;
 124         char *read_buf;
 125 };
 126
 127 struct name_cache_entry {
 128         struct list_head list;
 129         struct list_head use_list;
 130         u64 ino;
 131         u64 gen;
 132         u64 parent_ino;
 133         u64 parent_gen;
 134         int ret;
 135         int need_later_update;
 136         int name_len;
 137         char name[];
 138 };
 139
 140 static void fs_path_reset(struct fs_path *p)
 141 {
 142         if (p->reversed) {
 143                 p->start = p->buf + p->buf_len - 1;
 144                 p->end = p->start;
 145                 *p->start = 0;
 146         } else {
 147                 p->start = p->buf;
 148                 p->end = p->start;
 149                 *p->start = 0;
 150         }
 151 }
 152
 153 static struct fs_path *fs_path_alloc(struct send_ctx *sctx)
 154 {
 155         struct fs_path *p;
 156
 157         p = kmalloc(sizeof(*p), GFP_NOFS);
 158         if (!p)
 159                 return NULL;
 160         p->reversed = 0;
 161         p->virtual_mem = 0;
 162         p->buf = p->inline_buf;
 163         p->buf_len = FS_PATH_INLINE_SIZE;
 164         fs_path_reset(p);
 165         return p;
 166 }
 167
 168 static struct fs_path *fs_path_alloc_reversed(struct send_ctx *sctx)
 169 {
 170         struct fs_path *p;
 171
 172         p = fs_path_alloc(sctx);
 173         if (!p)
 174                 return NULL;
 175         p->reversed = 1;
 176         fs_path_reset(p);
 177         return p;
 178 }
 179
 180 static void fs_path_free(struct send_ctx *sctx, struct fs_path *p)
 181 {
 182         if (!p)
 183                 return;
 184         if (p->buf != p->inline_buf) {
 185                 if (p->virtual_mem)
 186                         vfree(p->buf);
 187                 else
 188                         kfree(p->buf);
 189         }
 190         kfree(p);
 191 }
 192
 193 static int fs_path_len(struct fs_path *p)
 194 {
 195         return p->end - p->start;
 196 }
 197
 198 static int fs_path_ensure_buf(struct fs_path *p, int len)
 199 {
 200         char *tmp_buf;
 201         int path_len;
 202         int old_buf_len;
 203
 204         len++;
 205
 206         if (p->buf_len >= len)
 207                 return 0;
 208
 209         path_len = p->end - p->start;
 210         old_buf_len = p->buf_len;
 211         len = PAGE_ALIGN(len);
 212
 213         if (p->buf == p->inline_buf) {
 214                 tmp_buf = kmalloc(len, GFP_NOFS);
 215                 if (!tmp_buf) {
 216                         tmp_buf = vmalloc(len);
 217                         if (!tmp_buf)
 218                                 return -ENOMEM;
 219                         p->virtual_mem = 1;
 220                 }
 221                 memcpy(tmp_buf, p->buf, p->buf_len);
 222                 p->buf = tmp_buf;
 223                 p->buf_len = len;
 224         } else {
 225                 if (p->virtual_mem) {
 226                         tmp_buf = vmalloc(len);
 227                         if (!tmp_buf)
 228                                 return -ENOMEM;
 229                         memcpy(tmp_buf, p->buf, p->buf_len);
 230                         vfree(p->buf);
 231                 } else {
 232                         tmp_buf = krealloc(p->buf, len, GFP_NOFS);
 233                         if (!tmp_buf) {
 234                                 tmp_buf = vmalloc(len);
 235                                 if (!tmp_buf)
 236                                         return -ENOMEM;
 237                                 memcpy(tmp_buf, p->buf, p->buf_len);
 238                                 kfree(p->buf);
 239                                 p->virtual_mem = 1;
 240                         }
 241                 }
 242                 p->buf = tmp_buf;
 243                 p->buf_len = len;
 244         }
 245         if (p->reversed) {
 246                 tmp_buf = p->buf + old_buf_len - path_len - 1;
 247                 p->end = p->buf + p->buf_len - 1;
 248                 p->start = p->end - path_len;
 249                 memmove(p->start, tmp_buf, path_len + 1);
 250         } else {
 251                 p->start = p->buf;
 252                 p->end = p->start + path_len;
 253         }
 254         return 0;
 255 }
 256
 257 static int fs_path_prepare_for_add(struct fs_path *p, int name_len)
 258 {
 259         int ret;
 260         int new_len;
 261
 262         new_len = p->end - p->start + name_len;
 263         if (p->start != p->end)
 264                 new_len++;
 265         ret = fs_path_ensure_buf(p, new_len);
 266         if (ret < 0)
 267                 goto out;
 268
 269         if (p->reversed) {
 270                 if (p->start != p->end)
 271                         *--p->start = '/';
 272                 p->start -= name_len;
 273                 p->prepared = p->start;
 274         } else {
 275                 if (p->start != p->end)
 276                         *p->end++ = '/';
 277                 p->prepared = p->end;
 278                 p->end += name_len;
 279                 *p->end = 0;
 280         }
 281
 282 out:
 283         return ret;
 284 }
 285
 286 static int fs_path_add(struct fs_path *p, const char *name, int name_len)
 287 {
 288         int ret;
 289
 290         ret = fs_path_prepare_for_add(p, name_len);
 291         if (ret < 0)
 292                 goto out;
 293         memcpy(p->prepared, name, name_len);
 294         p->prepared = NULL;
 295
 296 out:
 297         return ret;
 298 }
 299
 300 static int fs_path_add_path(struct fs_path *p, struct fs_path *p2)
 301 {
 302         int ret;
 303
 304         ret = fs_path_prepare_for_add(p, p2->end - p2->start);
 305         if (ret < 0)
 306                 goto out;
 307         memcpy(p->prepared, p2->start, p2->end - p2->start);
 308         p->prepared = NULL;
 309
 310 out:
 311         return ret;
 312 }
 313
 314 static int fs_path_add_from_extent_buffer(struct fs_path *p,
 315                                           struct extent_buffer *eb,
 316                                           unsigned long off, int len)
 317 {
 318         int ret;
 319
 320         ret = fs_path_prepare_for_add(p, len);
 321         if (ret < 0)
 322                 goto out;
 323
 324         read_extent_buffer(eb, p->prepared, off, len);
 325         p->prepared = NULL;
 326
 327 out:
 328         return ret;
 329 }
 330
 331 static void fs_path_remove(struct fs_path *p)
 332 {
 333         BUG_ON(p->reversed);
 334         while (p->start != p->end && *p->end != '/')
 335                 p->end--;
 336         *p->end = 0;
 337 }
 338
 339 static int fs_path_copy(struct fs_path *p, struct fs_path *from)
 340 {
 341         int ret;
 342
 343         p->reversed = from->reversed;
 344         fs_path_reset(p);
 345
 346         ret = fs_path_add_path(p, from);
 347
 348         return ret;
 349 }
 350
 351
 352 static void fs_path_unreverse(struct fs_path *p)
 353 {
 354         char *tmp;
 355         int len;
 356
 357         if (!p->reversed)
 358                 return;
 359
 360         tmp = p->start;
 361         len = p->end - p->start;
 362         p->start = p->buf;
 363         p->end = p->start + len;
 364         memmove(p->start, tmp, len + 1);
 365         p->reversed = 0;
 366 }
 367
 368 static struct btrfs_path *alloc_path_for_send(void)
 369 {
 370         struct btrfs_path *path;
 371
 372         path = btrfs_alloc_path();
 373         if (!path)
 374                 return NULL;
 375         path->search_commit_root = 1;
 376         path->skip_locking = 1;
 377         return path;
 378 }
 379
 380 static int write_buf(struct send_ctx *sctx, const void *buf, u32 len)
 381 {
 382         int ret;
 383         mm_segment_t old_fs;
 384         u32 pos = 0;
 385
 386         old_fs = get_fs();
 387         set_fs(KERNEL_DS);
 388
 389         while (pos < len) {
 390                 ret = vfs_write(sctx->send_filp, (char *)buf + pos, len - pos,
 391                                 &sctx->send_off);
 392                 /* TODO handle that correctly */
 393                 /*if (ret == -ERESTARTSYS) {
 394                         continue;
 395                 }*/
 396                 if (ret < 0)
 397                         goto out;
 398                 if (ret == 0) {
 399                         ret = -EIO;
 400                         goto out;
 401                 }
 402                 pos += ret;
 403         }
 404
 405         ret = 0;
 406
 407 out:
 408         set_fs(old_fs);
 409         return ret;
 410 }
 411
 412 static int tlv_put(struct send_ctx *sctx, u16 attr, const void *data, int len)
 413 {
 414         struct btrfs_tlv_header *hdr;
 415         int total_len = sizeof(*hdr) + len;
 416         int left = sctx->send_max_size - sctx->send_size;
 417
 418         if (unlikely(left < total_len))
 419                 return -EOVERFLOW;
 420
 421         hdr = (struct btrfs_tlv_header *) (sctx->send_buf + sctx->send_size);
 422         hdr->tlv_type = cpu_to_le16(attr);
 423         hdr->tlv_len = cpu_to_le16(len);
 424         memcpy(hdr + 1, data, len);
 425         sctx->send_size += total_len;
 426
 427         return 0;
 428 }
 429
 430 #if 0
 431 static int tlv_put_u8(struct send_ctx *sctx, u16 attr, u8 value)
 432 {
 433         return tlv_put(sctx, attr, &value, sizeof(value));
 434 }
 435
 436 static int tlv_put_u16(struct send_ctx *sctx, u16 attr, u16 value)
 437 {
 438         __le16 tmp = cpu_to_le16(value);
 439         return tlv_put(sctx, attr, &tmp, sizeof(tmp));
 440 }
 441
 442 static int tlv_put_u32(struct send_ctx *sctx, u16 attr, u32 value)
 443 {
 444         __le32 tmp = cpu_to_le32(value);
 445         return tlv_put(sctx, attr, &tmp, sizeof(tmp));
 446 }
 447 #endif
 448
 449 static int tlv_put_u64(struct send_ctx *sctx, u16 attr, u64 value)
 450 {
 451         __le64 tmp = cpu_to_le64(value);
 452         return tlv_put(sctx, attr, &tmp, sizeof(tmp));
 453 }
 454
 455 static int tlv_put_string(struct send_ctx *sctx, u16 attr,
 456                           const char *str, int len)
 457 {
 458         if (len == -1)
 459                 len = strlen(str);
 460         return tlv_put(sctx, attr, str, len);
 461 }
 462
 463 static int tlv_put_uuid(struct send_ctx *sctx, u16 attr,
 464                         const u8 *uuid)
 465 {
 466         return tlv_put(sctx, attr, uuid, BTRFS_UUID_SIZE);
 467 }
 468
 469 #if 0
 470 static int tlv_put_timespec(struct send_ctx *sctx, u16 attr,
 471                             struct timespec *ts)
 472 {
 473         struct btrfs_timespec bts;
 474         bts.sec = cpu_to_le64(ts->tv_sec);
 475         bts.nsec = cpu_to_le32(ts->tv_nsec);
 476         return tlv_put(sctx, attr, &bts, sizeof(bts));
 477 }
 478 #endif
 479
 480 static int tlv_put_btrfs_timespec(struct send_ctx *sctx, u16 attr,
 481                                   struct extent_buffer *eb,
 482                                   struct btrfs_timespec *ts)
 483 {
 484         struct btrfs_timespec bts;
 485         read_extent_buffer(eb, &bts, (unsigned long)ts, sizeof(bts));
 486         return tlv_put(sctx, attr, &bts, sizeof(bts));
 487 }
 488
 489
 490 #define TLV_PUT(sctx, attrtype, attrlen, data) \
 491         do { \
 492                 ret = tlv_put(sctx, attrtype, attrlen, data); \
 493                 if (ret < 0) \
 494                         goto tlv_put_failure; \
 495         } while (0)
 496
 497 #define TLV_PUT_INT(sctx, attrtype, bits, value) \
 498         do { \
 499                 ret = tlv_put_u##bits(sctx, attrtype, value); \
 500                 if (ret < 0) \
 501                         goto tlv_put_failure; \
 502         } while (0)
 503
 504 #define TLV_PUT_U8(sctx, attrtype, data) TLV_PUT_INT(sctx, attrtype, 8, data)
 505 #define TLV_PUT_U16(sctx, attrtype, data) TLV_PUT_INT(sctx, attrtype, 16, data)
 506 #define TLV_PUT_U32(sctx, attrtype, data) TLV_PUT_INT(sctx, attrtype, 32, data)
 507 #define TLV_PUT_U64(sctx, attrtype, data) TLV_PUT_INT(sctx, attrtype, 64, data)
 508 #define TLV_PUT_STRING(sctx, attrtype, str, len) \
 509         do { \
 510                 ret = tlv_put_string(sctx, attrtype, str, len); \
 511                 if (ret < 0) \
 512                         goto tlv_put_failure; \
 513         } while (0)
 514 #define TLV_PUT_PATH(sctx, attrtype, p) \
 515         do { \
 516                 ret = tlv_put_string(sctx, attrtype, p->start, \
 517                         p->end - p->start); \
 518                 if (ret < 0) \
 519                         goto tlv_put_failure; \
 520         } while(0)
 521 #define TLV_PUT_UUID(sctx, attrtype, uuid) \
 522         do { \
 523                 ret = tlv_put_uuid(sctx, attrtype, uuid); \
 524                 if (ret < 0) \
 525                         goto tlv_put_failure; \
 526         } while (0)
 527 #define TLV_PUT_TIMESPEC(sctx, attrtype, ts) \
 528         do { \
 529                 ret = tlv_put_timespec(sctx, attrtype, ts); \
 530                 if (ret < 0) \
 531                         goto tlv_put_failure; \
 532         } while (0)
 533 #define TLV_PUT_BTRFS_TIMESPEC(sctx, attrtype, eb, ts) \
 534         do { \
 535                 ret = tlv_put_btrfs_timespec(sctx, attrtype, eb, ts); \
 536                 if (ret < 0) \
 537                         goto tlv_put_failure; \
 538         } while (0)
 539
 540 static int send_header(struct send_ctx *sctx)
 541 {
 542         struct btrfs_stream_header hdr;
 543
 544         strcpy(hdr.magic, BTRFS_SEND_STREAM_MAGIC);
 545         hdr.version = cpu_to_le32(BTRFS_SEND_STREAM_VERSION);
 546
 547         return write_buf(sctx, &hdr, sizeof(hdr));
 548 }
 549
 550 /*
 551  * For each command/item we want to send to userspace, we call this function.
 552  */
 553 static int begin_cmd(struct send_ctx *sctx, int cmd)
 554 {
 555         struct btrfs_cmd_header *hdr;
 556
 557         if (!sctx->send_buf) {
 558                 WARN_ON(1);
 559                 return -EINVAL;
 560         }
 561
 562         BUG_ON(sctx->send_size);
 563
 564         sctx->send_size += sizeof(*hdr);
 565         hdr = (struct btrfs_cmd_header *)sctx->send_buf;
 566         hdr->cmd = cpu_to_le16(cmd);
 567
 568         return 0;
 569 }
 570
 571 static int send_cmd(struct send_ctx *sctx)
 572 {
 573         int ret;
 574         struct btrfs_cmd_header *hdr;
 575         u32 crc;
 576
 577         hdr = (struct btrfs_cmd_header *)sctx->send_buf;
 578         hdr->len = cpu_to_le32(sctx->send_size - sizeof(*hdr));
 579         hdr->crc = 0;
 580
 581         crc = crc32c(0, (unsigned char *)sctx->send_buf, sctx->send_size);
 582         hdr->crc = cpu_to_le32(crc);
 583
 584         ret = write_buf(sctx, sctx->send_buf, sctx->send_size);
 585
 586         sctx->total_send_size += sctx->send_size;
 587         sctx->cmd_send_size[le16_to_cpu(hdr->cmd)] += sctx->send_size;
 588         sctx->send_size = 0;
 589
 590         return ret;
 591 }
 592
 593 /*
 594  * Sends a move instruction to user space
 595  */
 596 static int send_rename(struct send_ctx *sctx,
 597                      struct fs_path *from, struct fs_path *to)
 598 {
 599         int ret;
 600
 601 verbose_printk("btrfs: send_rename %s -> %s\n", from->start, to->start);
 602
 603         ret = begin_cmd(sctx, BTRFS_SEND_C_RENAME);
 604         if (ret < 0)
 605                 goto out;
 606
 607         TLV_PUT_PATH(sctx, BTRFS_SEND_A_PATH, from);
 608         TLV_PUT_PATH(sctx, BTRFS_SEND_A_PATH_TO, to);
 609
 610         ret = send_cmd(sctx);
 611
 612 tlv_put_failure:
 613 out:
 614         return ret;
 615 }
 616
 617 /*
 618  * Sends a link instruction to user space
 619  */
 620 static int send_link(struct send_ctx *sctx,
 621                      struct fs_path *path, struct fs_path *lnk)
 622 {
 623         int ret;
 624
 625 verbose_printk("btrfs: send_link %s -> %s\n", path->start, lnk->start);
 626
 627         ret = begin_cmd(sctx, BTRFS_SEND_C_LINK);
 628         if (ret < 0)
 629                 goto out;
 630
 631         TLV_PUT_PATH(sctx, BTRFS_SEND_A_PATH, path);
 632         TLV_PUT_PATH(sctx, BTRFS_SEND_A_PATH_LINK, lnk);
 633
 634         ret = send_cmd(sctx);
 635
 636 tlv_put_failure:
 637 out:
 638         return ret;
 639 }
 640
 641 /*
 642  * Sends an unlink instruction to user space
 643  */
 644 static int send_unlink(struct send_ctx *sctx, struct fs_path *path)
 645 {
 646         int ret;
 647
 648 verbose_printk("btrfs: send_unlink %s\n", path->start);
 649
 650         ret = begin_cmd(sctx, BTRFS_SEND_C_UNLINK);
 651         if (ret < 0)
 652                 goto out;
 653
 654         TLV_PUT_PATH(sctx, BTRFS_SEND_A_PATH, path);
 655
 656         ret = send_cmd(sctx);
 657
 658 tlv_put_failure:
 659 out:
 660         return ret;
 661 }
 662
 663 /*
 664  * Sends a rmdir instruction to user space
 665  */
 666 static int send_rmdir(struct send_ctx *sctx, struct fs_path *path)
 667 {
 668         int ret;
 669
 670 verbose_printk("btrfs: send_rmdir %s\n", path->start);
 671
 672         ret = begin_cmd(sctx, BTRFS_SEND_C_RMDIR);
 673         if (ret < 0)
 674                 goto out;
 675
 676         TLV_PUT_PATH(sctx, BTRFS_SEND_A_PATH, path);
 677
 678         ret = send_cmd(sctx);
 679
 680 tlv_put_failure:
 681 out:
 682         return ret;
 683 }
 684
 685 /*
 686  * Helper function to retrieve some fields from an inode item.
 687  */
 688 static int get_inode_info(struct btrfs_root *root,
 689                           u64 ino, u64 *size, u64 *gen,
 690                           u64 *mode, u64 *uid, u64 *gid,
 691                           u64 *rdev)
 692 {
 693         int ret;
 694         struct btrfs_inode_item *ii;
 695         struct btrfs_key key;
 696         struct btrfs_path *path;
 697
 698         path = alloc_path_for_send();
 699         if (!path)
 700                 return -ENOMEM;
 701
 702         key.objectid = ino;
 703         key.type = BTRFS_INODE_ITEM_KEY;
 704         key.offset = 0;
 705         ret = btrfs_search_slot(NULL, root, &key, path, 0, 0);
 706         if (ret < 0)
 707                 goto out;
 708         if (ret) {
 709                 ret = -ENOENT;
 710                 goto out;
 711         }
 712
 713         ii = btrfs_item_ptr(path->nodes[0], path->slots[0],
 714                         struct btrfs_inode_item);
 715         if (size)
 716                 *size = btrfs_inode_size(path->nodes[0], ii);
 717         if (gen)
 718                 *gen = btrfs_inode_generation(path->nodes[0], ii);
 719         if (mode)
 720                 *mode = btrfs_inode_mode(path->nodes[0], ii);
 721         if (uid)
 722                 *uid = btrfs_inode_uid(path->nodes[0], ii);
 723         if (gid)
 724                 *gid = btrfs_inode_gid(path->nodes[0], ii);
 725         if (rdev)
 726                 *rdev = btrfs_inode_rdev(path->nodes[0], ii);
 727
 728 out:
 729         btrfs_free_path(path);
 730         return ret;
 731 }
 732
 733 typedef int (*iterate_inode_ref_t)(int num, u64 dir, int index,
 734                                    struct fs_path *p,
 735                                    void *ctx);
 736
 737 /*
 738  * Helper function to iterate the entries in ONE btrfs_inode_ref.
 739  * The iterate callback may return a non zero value to stop iteration. This can
 740  * be a negative value for error codes or 1 to simply stop it.
 741  *
 742  * path must point to the INODE_REF when called.
 743  */
 744 static int iterate_inode_ref(struct send_ctx *sctx,
 745                              struct btrfs_root *root, struct btrfs_path *path,
 746                              struct btrfs_key *found_key, int resolve,
 747                              iterate_inode_ref_t iterate, void *ctx)
 748 {
 749         struct extent_buffer *eb;
 750         struct btrfs_item *item;
 751         struct btrfs_inode_ref *iref;
 752         struct btrfs_path *tmp_path;
 753         struct fs_path *p;
 754         u32 cur;
 755         u32 len;
 756         u32 total;
 757         int slot;
 758         u32 name_len;
 759         char *start;
 760         int ret = 0;
 761         int num;
 762         int index;
 763
 764         p = fs_path_alloc_reversed(sctx);
 765         if (!p)
 766                 return -ENOMEM;
 767
 768         tmp_path = alloc_path_for_send();
 769         if (!tmp_path) {
 770                 fs_path_free(sctx, p);
 771                 return -ENOMEM;
 772         }
 773
 774         eb = path->nodes[0];
 775         slot = path->slots[0];
 776         item = btrfs_item_nr(eb, slot);
 777         iref = btrfs_item_ptr(eb, slot, struct btrfs_inode_ref);
 778         cur = 0;
 779         len = 0;
 780         total = btrfs_item_size(eb, item);
 781
 782         num = 0;
 783         while (cur < total) {
 784                 fs_path_reset(p);
 785
 786                 name_len = btrfs_inode_ref_name_len(eb, iref);
 787                 index = btrfs_inode_ref_index(eb, iref);
 788                 if (resolve) {
 789                         start = btrfs_iref_to_path(root, tmp_path, iref, eb,
 790                                                 found_key->offset, p->buf,
 791                                                 p->buf_len);
 792                         if (IS_ERR(start)) {
 793                                 ret = PTR_ERR(start);
 794                                 goto out;
 795                         }
 796                         if (start < p->buf) {
 797                                 /* overflow , try again with larger buffer */
 798                                 ret = fs_path_ensure_buf(p,
 799                                                 p->buf_len + p->buf - start);
 800                                 if (ret < 0)
 801                                         goto out;
 802                                 start = btrfs_iref_to_path(root, tmp_path, iref,
 803                                                 eb, found_key->offset, p->buf,
 804                                                 p->buf_len);
 805                                 if (IS_ERR(start)) {
 806                                         ret = PTR_ERR(start);
 807                                         goto out;
 808                                 }
 809                                 BUG_ON(start < p->buf);
 810                         }
 811                         p->start = start;
 812                 } else {
 813                         ret = fs_path_add_from_extent_buffer(p, eb,
 814                                         (unsigned long)(iref + 1), name_len);
 815                         if (ret < 0)
 816                                 goto out;
 817                 }
 818
 819
 820                 len = sizeof(*iref) + name_len;
 821                 iref = (struct btrfs_inode_ref *)((char *)iref + len);
 822                 cur += len;
 823
 824                 ret = iterate(num, found_key->offset, index, p, ctx);
 825                 if (ret)
 826                         goto out;
 827
 828                 num++;
 829         }
 830
 831 out:
 832         btrfs_free_path(tmp_path);
 833         fs_path_free(sctx, p);
 834         return ret;
 835 }
 836
 837 typedef int (*iterate_dir_item_t)(int num, struct btrfs_key *di_key,
 838                                   const char *name, int name_len,
 839                                   const char *data, int data_len,
 840                                   u8 type, void *ctx);
 841
 842 /*
 843  * Helper function to iterate the entries in ONE btrfs_dir_item.
 844  * The iterate callback may return a non zero value to stop iteration. This can
 845  * be a negative value for error codes or 1 to simply stop it.
 846  *
 847  * path must point to the dir item when called.
 848  */
 849 static int iterate_dir_item(struct send_ctx *sctx,
 850                             struct btrfs_root *root, struct btrfs_path *path,
 851                             struct btrfs_key *found_key,
 852                             iterate_dir_item_t iterate, void *ctx)
 853 {
 854         int ret = 0;
 855         struct extent_buffer *eb;
 856         struct btrfs_item *item;
 857         struct btrfs_dir_item *di;
 858         struct btrfs_path *tmp_path = NULL;
 859         struct btrfs_key di_key;
 860         char *buf = NULL;
 861         char *buf2 = NULL;
 862         int buf_len;
 863         int buf_virtual = 0;
 864         u32 name_len;
 865         u32 data_len;
 866         u32 cur;
 867         u32 len;
 868         u32 total;
 869         int slot;
 870         int num;
 871         u8 type;
 872
 873         buf_len = PAGE_SIZE;
 874         buf = kmalloc(buf_len, GFP_NOFS);
 875         if (!buf) {
 876                 ret = -ENOMEM;
 877                 goto out;
 878         }
 879
 880         tmp_path = alloc_path_for_send();
 881         if (!tmp_path) {
 882                 ret = -ENOMEM;
 883                 goto out;
 884         }
 885
 886         eb = path->nodes[0];
 887         slot = path->slots[0];
 888         item = btrfs_item_nr(eb, slot);
 889         di = btrfs_item_ptr(eb, slot, struct btrfs_dir_item);
 890         cur = 0;
 891         len = 0;
 892         total = btrfs_item_size(eb, item);
 893
 894         num = 0;
 895         while (cur < total) {
 896                 name_len = btrfs_dir_name_len(eb, di);
 897                 data_len = btrfs_dir_data_len(eb, di);
 898                 type = btrfs_dir_type(eb, di);
 899                 btrfs_dir_item_key_to_cpu(eb, di, &di_key);
 900
 901                 if (name_len + data_len > buf_len) {
 902                         buf_len = PAGE_ALIGN(name_len + data_len);
 903                         if (buf_virtual) {
 904                                 buf2 = vmalloc(buf_len);
 905                                 if (!buf2) {
 906                                         ret = -ENOMEM;
 907                                         goto out;
 908                                 }
 909                                 vfree(buf);
 910                         } else {
 911                                 buf2 = krealloc(buf, buf_len, GFP_NOFS);
 912                                 if (!buf2) {
 913                                         buf2 = vmalloc(buf_len);
 914                                         if (!buf2) {
 915                                                 ret = -ENOMEM;
 916                                                 goto out;
 917                                         }
 918                                         kfree(buf);
 919                                         buf_virtual = 1;
 920                                 }
 921                         }
 922
 923                         buf = buf2;
 924                         buf2 = NULL;
 925                 }
 926
 927                 read_extent_buffer(eb, buf, (unsigned long)(di + 1),
 928                                 name_len + data_len);
 929
 930                 len = sizeof(*di) + name_len + data_len;
 931                 di = (struct btrfs_dir_item *)((char *)di + len);
 932                 cur += len;
 933
 934                 ret = iterate(num, &di_key, buf, name_len, buf + name_len,
 935                                 data_len, type, ctx);
 936                 if (ret < 0)
 937                         goto out;
 938                 if (ret) {
 939                         ret = 0;
 940                         goto out;
 941                 }
 942
 943                 num++;
 944         }
 945
 946 out:
 947         btrfs_free_path(tmp_path);
 948         if (buf_virtual)
 949                 vfree(buf);
 950         else
 951                 kfree(buf);
 952         return ret;
 953 }
 954
 955 static int __copy_first_ref(int num, u64 dir, int index,
 956                             struct fs_path *p, void *ctx)
 957 {
 958         int ret;
 959         struct fs_path *pt = ctx;
 960
 961         ret = fs_path_copy(pt, p);
 962         if (ret < 0)
 963                 return ret;
 964
 965         /* we want the first only */
 966         return 1;
 967 }
 968
 969 /*
 970  * Retrieve the first path of an inode. If an inode has more then one
 971  * ref/hardlink, this is ignored.
 972  */
 973 static int get_inode_path(struct send_ctx *sctx, struct btrfs_root *root,
 974                           u64 ino, struct fs_path *path)
 975 {
 976         int ret;
 977         struct btrfs_key key, found_key;
 978         struct btrfs_path *p;
 979
 980         p = alloc_path_for_send();
 981         if (!p)
 982                 return -ENOMEM;
 983
 984         fs_path_reset(path);
 985
 986         key.objectid = ino;
 987         key.type = BTRFS_INODE_REF_KEY;
 988         key.offset = 0;
 989
 990         ret = btrfs_search_slot_for_read(root, &key, p, 1, 0);
 991         if (ret < 0)
 992                 goto out;
 993         if (ret) {
 994                 ret = 1;
 995                 goto out;
 996         }
 997         btrfs_item_key_to_cpu(p->nodes[0], &found_key, p->slots[0]);
 998         if (found_key.objectid != ino ||
 999                 found_key.type != BTRFS_INODE_REF_KEY) {
1000                 ret = -ENOENT;
1001                 goto out;
1002         }
1003
1004         ret = iterate_inode_ref(sctx, root, p, &found_key, 1,
1005                         __copy_first_ref, path);
1006         if (ret < 0)
1007                 goto out;
1008         ret = 0;
1009
1010 out:
1011         btrfs_free_path(p);
1012         return ret;
1013 }
1014
1015 struct backref_ctx {
1016         struct send_ctx *sctx;
1017
1018         /* number of total found references */
1019         u64 found;
1020
1021         /*
1022          * used for clones found in send_root. clones found behind cur_objectid
1023          * and cur_offset are not considered as allowed clones.
1024          */
1025         u64 cur_objectid;
1026         u64 cur_offset;
1027
1028         /* may be truncated in case it's the last extent in a file */
1029         u64 extent_len;
1030
1031         /* Just to check for bugs in backref resolving */
1032         int found_in_send_root;
1033 };
1034
1035 static int __clone_root_cmp_bsearch(const void *key, const void *elt)
1036 {
1037         u64 root = (u64)key;
1038         struct clone_root *cr = (struct clone_root *)elt;
1039
1040         if (root < cr->root->objectid)
1041                 return -1;
1042         if (root > cr->root->objectid)
1043                 return 1;
1044         return 0;
1045 }
1046
1047 static int __clone_root_cmp_sort(const void *e1, const void *e2)
1048 {
1049         struct clone_root *cr1 = (struct clone_root *)e1;
1050         struct clone_root *cr2 = (struct clone_root *)e2;
1051
1052         if (cr1->root->objectid < cr2->root->objectid)
1053                 return -1;
1054         if (cr1->root->objectid > cr2->root->objectid)
1055                 return 1;
1056         return 0;
1057 }
1058
1059 /*
1060  * Called for every backref that is found for the current extent.
1061  */
1062 static int __iterate_backrefs(u64 ino, u64 offset, u64 root, void *ctx_)
1063 {
1064         struct backref_ctx *bctx = ctx_;
1065         struct clone_root *found;
1066         int ret;
1067         u64 i_size;
1068
1069         /* First check if the root is in the list of accepted clone sources */
1070         found = bsearch((void *)root, bctx->sctx->clone_roots,
1071                         bctx->sctx->clone_roots_cnt,
1072                         sizeof(struct clone_root),
1073                         __clone_root_cmp_bsearch);
1074         if (!found)
1075                 return 0;
1076
1077         if (found->root == bctx->sctx->send_root &&
1078             ino == bctx->cur_objectid &&
1079             offset == bctx->cur_offset) {
1080                 bctx->found_in_send_root = 1;
1081         }
1082
1083         /*
1084          * There are inodes that have extents that lie behind it's i_size. Don't
1085          * accept clones from these extents.
1086          */
1087         ret = get_inode_info(found->root, ino, &i_size, NULL, NULL, NULL, NULL,
1088                         NULL);
1089         if (ret < 0)
1090                 return ret;
1091
1092         if (offset + bctx->extent_len > i_size)
1093                 return 0;
1094
1095         /*
1096          * Make sure we don't consider clones from send_root that are
1097          * behind the current inode/offset.
1098          */
1099         if (found->root == bctx->sctx->send_root) {
1100                 /*
1101                  * TODO for the moment we don't accept clones from the inode
1102                  * that is currently send. We may change this when
1103                  * BTRFS_IOC_CLONE_RANGE supports cloning from and to the same
1104                  * file.
1105                  */
1106                 if (ino >= bctx->cur_objectid)
1107                         return 0;
1108                 /*if (ino > ctx->cur_objectid)
1109                         return 0;
1110                 if (offset + ctx->extent_len > ctx->cur_offset)
1111                         return 0;*/
1112
1113                 bctx->found++;
1114                 found->found_refs++;
1115                 found->ino = ino;
1116                 found->offset = offset;
1117                 return 0;
1118         }
1119
1120         bctx->found++;
1121         found->found_refs++;
1122         if (ino < found->ino) {
1123                 found->ino = ino;
1124                 found->offset = offset;
1125         } else if (found->ino == ino) {
1126                 /*
1127                  * same extent found more then once in the same file.
1128                  */
1129                 if (found->offset > offset + bctx->extent_len)
1130                         found->offset = offset;
1131         }
1132
1133         return 0;
1134 }
1135
1136 /*
1137  * path must point to the extent item when called.
1138  */
1139 static int find_extent_clone(struct send_ctx *sctx,
1140                              struct btrfs_path *path,
1141                              u64 ino, u64 data_offset,
1142                              u64 ino_size,
1143                              struct clone_root **found)
1144 {
1145         int ret;
1146         int extent_type;
1147         u64 logical;
1148         u64 num_bytes;
1149         u64 extent_item_pos;
1150         struct btrfs_file_extent_item *fi;
1151         struct extent_buffer *eb = path->nodes[0];
1152         struct backref_ctx backref_ctx;
1153         struct clone_root *cur_clone_root;
1154         struct btrfs_key found_key;
1155         struct btrfs_path *tmp_path;
1156         u32 i;
1157
1158         tmp_path = alloc_path_for_send();
1159         if (!tmp_path)
1160                 return -ENOMEM;
1161
1162         if (data_offset >= ino_size) {
1163                 /*
1164                  * There may be extents that lie behind the file's size.
1165                  * I at least had this in combination with snapshotting while
1166                  * writing large files.
1167                  */
1168                 ret = 0;
1169                 goto out;
1170         }
1171
1172         fi = btrfs_item_ptr(eb, path->slots[0],
1173                         struct btrfs_file_extent_item);
1174         extent_type = btrfs_file_extent_type(eb, fi);
1175         if (extent_type == BTRFS_FILE_EXTENT_INLINE) {
1176                 ret = -ENOENT;
1177                 goto out;
1178         }
1179
1180         num_bytes = btrfs_file_extent_num_bytes(eb, fi);
1181         logical = btrfs_file_extent_disk_bytenr(eb, fi);
1182         if (logical == 0) {
1183                 ret = -ENOENT;
1184                 goto out;
1185         }
1186         logical += btrfs_file_extent_offset(eb, fi);
1187
1188         ret = extent_from_logical(sctx->send_root->fs_info,
1189                         logical, tmp_path, &found_key);
1190         btrfs_release_path(tmp_path);
1191
1192         if (ret < 0)
1193                 goto out;
1194         if (ret & BTRFS_EXTENT_FLAG_TREE_BLOCK) {
1195                 ret = -EIO;
1196                 goto out;
1197         }
1198
1199         /*
1200          * Setup the clone roots.
1201          */
1202         for (i = 0; i < sctx->clone_roots_cnt; i++) {
1203                 cur_clone_root = sctx->clone_roots + i;
1204                 cur_clone_root->ino = (u64)-1;
1205                 cur_clone_root->offset = 0;
1206                 cur_clone_root->found_refs = 0;
1207         }
1208
1209         backref_ctx.sctx = sctx;
1210         backref_ctx.found = 0;
1211         backref_ctx.cur_objectid = ino;
1212         backref_ctx.cur_offset = data_offset;
1213         backref_ctx.found_in_send_root = 0;
1214         backref_ctx.extent_len = num_bytes;
1215
1216         /*
1217          * The last extent of a file may be too large due to page alignment.
1218          * We need to adjust extent_len in this case so that the checks in
1219          * __iterate_backrefs work.
1220          */
1221         if (data_offset + num_bytes >= ino_size)
1222                 backref_ctx.extent_len = ino_size - data_offset;
1223
1224         /*
1225          * Now collect all backrefs.
1226          */
1227         extent_item_pos = logical - found_key.objectid;
1228         ret = iterate_extent_inodes(sctx->send_root->fs_info,
1229                                         found_key.objectid, extent_item_pos, 1,
1230                                         __iterate_backrefs, &backref_ctx);
1231         if (ret < 0)
1232                 goto out;
1233
1234         if (!backref_ctx.found_in_send_root) {
1235                 /* found a bug in backref code? */
1236                 ret = -EIO;
1237                 printk(KERN_ERR "btrfs: ERROR did not find backref in "
1238                                 "send_root. inode=%llu, offset=%llu, "
1239                                 "logical=%llu\n",
1240                                 ino, data_offset, logical);
1241                 goto out;
1242         }
1243
1244 verbose_printk(KERN_DEBUG "btrfs: find_extent_clone: data_offset=%llu, "
1245                 "ino=%llu, "
1246                 "num_bytes=%llu, logical=%llu\n",
1247                 data_offset, ino, num_bytes, logical);
1248
1249         if (!backref_ctx.found)
1250                 verbose_printk("btrfs:    no clones found\n");
1251
1252         cur_clone_root = NULL;
1253         for (i = 0; i < sctx->clone_roots_cnt; i++) {
1254                 if (sctx->clone_roots[i].found_refs) {
1255                         if (!cur_clone_root)
1256                                 cur_clone_root = sctx->clone_roots + i;
1257                         else if (sctx->clone_roots[i].root == sctx->send_root)
1258                                 /* prefer clones from send_root over others */
1259                                 cur_clone_root = sctx->clone_roots + i;
1260                         break;
1261                 }
1262
1263         }
1264
1265         if (cur_clone_root) {
1266                 *found = cur_clone_root;
1267                 ret = 0;
1268         } else {
1269                 ret = -ENOENT;
1270         }
1271
1272 out:
1273         btrfs_free_path(tmp_path);
1274         return ret;
1275 }
1276
1277 static int read_symlink(struct send_ctx *sctx,
1278                         struct btrfs_root *root,
1279                         u64 ino,
1280                         struct fs_path *dest)
1281 {
1282         int ret;
1283         struct btrfs_path *path;
1284         struct btrfs_key key;
1285         struct btrfs_file_extent_item *ei;
1286         u8 type;
1287         u8 compression;
1288         unsigned long off;
1289         int len;
1290
1291         path = alloc_path_for_send();
1292         if (!path)
1293                 return -ENOMEM;
1294
1295         key.objectid = ino;
1296         key.type = BTRFS_EXTENT_DATA_KEY;
1297         key.offset = 0;
1298         ret = btrfs_search_slot(NULL, root, &key, path, 0, 0);
1299         if (ret < 0)
1300                 goto out;
1301         BUG_ON(ret);
1302
1303         ei = btrfs_item_ptr(path->nodes[0], path->slots[0],
1304                         struct btrfs_file_extent_item);
1305         type = btrfs_file_extent_type(path->nodes[0], ei);
1306         compression = btrfs_file_extent_compression(path->nodes[0], ei);
1307         BUG_ON(type != BTRFS_FILE_EXTENT_INLINE);
1308         BUG_ON(compression);
1309
1310         off = btrfs_file_extent_inline_start(ei);
1311         len = btrfs_file_extent_inline_len(path->nodes[0], ei);
1312
1313         ret = fs_path_add_from_extent_buffer(dest, path->nodes[0], off, len);
1314         if (ret < 0)
1315                 goto out;
1316
1317 out:
1318         btrfs_free_path(path);
1319         return ret;
1320 }
1321
1322 /*
1323  * Helper function to generate a file name that is unique in the root of
1324  * send_root and parent_root. This is used to generate names for orphan inodes.
1325  */
1326 static int gen_unique_name(struct send_ctx *sctx,
1327                            u64 ino, u64 gen,
1328                            struct fs_path *dest)
1329 {
1330         int ret = 0;
1331         struct btrfs_path *path;
1332         struct btrfs_dir_item *di;
1333         char tmp[64];
1334         int len;
1335         u64 idx = 0;
1336
1337         path = alloc_path_for_send();
1338         if (!path)
1339                 return -ENOMEM;
1340
1341         while (1) {
1342                 len = snprintf(tmp, sizeof(tmp) - 1, "o%llu-%llu-%llu",
1343                                 ino, gen, idx);
1344                 if (len >= sizeof(tmp)) {
1345                         /* should really not happen */
1346                         ret = -EOVERFLOW;
1347                         goto out;
1348                 }
1349
1350                 di = btrfs_lookup_dir_item(NULL, sctx->send_root,
1351                                 path, BTRFS_FIRST_FREE_OBJECTID,
1352                                 tmp, strlen(tmp), 0);
1353                 btrfs_release_path(path);
1354                 if (IS_ERR(di)) {
1355                         ret = PTR_ERR(di);
1356                         goto out;
1357                 }
1358                 if (di) {
1359                         /* not unique, try again */
1360                         idx++;
1361                         continue;
1362                 }
1363
1364                 if (!sctx->parent_root) {
1365                         /* unique */
1366                         ret = 0;
1367                         break;
1368                 }
1369
1370                 di = btrfs_lookup_dir_item(NULL, sctx->parent_root,
1371                                 path, BTRFS_FIRST_FREE_OBJECTID,
1372                                 tmp, strlen(tmp), 0);
1373                 btrfs_release_path(path);
1374                 if (IS_ERR(di)) {
1375                         ret = PTR_ERR(di);
1376                         goto out;
1377                 }
1378                 if (di) {
1379                         /* not unique, try again */
1380                         idx++;
1381                         continue;
1382                 }
1383                 /* unique */
1384                 break;
1385         }
1386
1387         ret = fs_path_add(dest, tmp, strlen(tmp));
1388
1389 out:
1390         btrfs_free_path(path);
1391         return ret;
1392 }
1393
1394 enum inode_state {
1395         inode_state_no_change,
1396         inode_state_will_create,
1397         inode_state_did_create,
1398         inode_state_will_delete,
1399         inode_state_did_delete,
1400 };
1401
1402 static int get_cur_inode_state(struct send_ctx *sctx, u64 ino, u64 gen)
1403 {
1404         int ret;
1405         int left_ret;
1406         int right_ret;
1407         u64 left_gen;
1408         u64 right_gen;
1409
1410         ret = get_inode_info(sctx->send_root, ino, NULL, &left_gen, NULL, NULL,
1411                         NULL, NULL);
1412         if (ret < 0 && ret != -ENOENT)
1413                 goto out;
1414         left_ret = ret;
1415
1416         if (!sctx->parent_root) {
1417                 right_ret = -ENOENT;
1418         } else {
1419                 ret = get_inode_info(sctx->parent_root, ino, NULL, &right_gen,
1420                                 NULL, NULL, NULL, NULL);
1421                 if (ret < 0 && ret != -ENOENT)
1422                         goto out;
1423                 right_ret = ret;
1424         }
1425
1426         if (!left_ret && !right_ret) {
1427                 if (left_gen == gen && right_gen == gen)
1428                         ret = inode_state_no_change;
1429                 else if (left_gen == gen) {
1430                         if (ino < sctx->send_progress)
1431                                 ret = inode_state_did_create;
1432                         else
1433                                 ret = inode_state_will_create;
1434                 } else if (right_gen == gen) {
1435                         if (ino < sctx->send_progress)
1436                                 ret = inode_state_did_delete;
1437                         else
1438                                 ret = inode_state_will_delete;
1439                 } else  {
1440                         ret = -ENOENT;
1441                 }
1442         } else if (!left_ret) {
1443                 if (left_gen == gen) {
1444                         if (ino < sctx->send_progress)
1445                                 ret = inode_state_did_create;
1446                         else
1447                                 ret = inode_state_will_create;
1448                 } else {
1449                         ret = -ENOENT;
1450                 }
1451         } else if (!right_ret) {
1452                 if (right_gen == gen) {
1453                         if (ino < sctx->send_progress)
1454                                 ret = inode_state_did_delete;
1455                         else
1456                                 ret = inode_state_will_delete;
1457                 } else {
1458                         ret = -ENOENT;
1459                 }
1460         } else {
1461                 ret = -ENOENT;
1462         }
1463
1464 out:
1465         return ret;
1466 }
1467
1468 static int is_inode_existent(struct send_ctx *sctx, u64 ino, u64 gen)
1469 {
1470         int ret;
1471
1472         ret = get_cur_inode_state(sctx, ino, gen);
1473         if (ret < 0)
1474                 goto out;
1475
1476         if (ret == inode_state_no_change ||
1477             ret == inode_state_did_create ||
1478             ret == inode_state_will_delete)
1479                 ret = 1;
1480         else
1481                 ret = 0;
1482
1483 out:
1484         return ret;
1485 }
1486
1487 /*
1488  * Helper function to lookup a dir item in a dir.
1489  */
1490 static int lookup_dir_item_inode(struct btrfs_root *root,
1491                                  u64 dir, const char *name, int name_len,
1492                                  u64 *found_inode,
1493                                  u8 *found_type)
1494 {
1495         int ret = 0;
1496         struct btrfs_dir_item *di;
1497         struct btrfs_key key;
1498         struct btrfs_path *path;
1499
1500         path = alloc_path_for_send();
1501         if (!path)
1502                 return -ENOMEM;
1503
1504         di = btrfs_lookup_dir_item(NULL, root, path,
1505                         dir, name, name_len, 0);
1506         if (!di) {
1507                 ret = -ENOENT;
1508                 goto out;
1509         }
1510         if (IS_ERR(di)) {
1511                 ret = PTR_ERR(di);
1512                 goto out;
1513         }
1514         btrfs_dir_item_key_to_cpu(path->nodes[0], di, &key);
1515         *found_inode = key.objectid;
1516         *found_type = btrfs_dir_type(path->nodes[0], di);
1517
1518 out:
1519         btrfs_free_path(path);
1520         return ret;
1521 }
1522
1523 static int get_first_ref(struct send_ctx *sctx,
1524                          struct btrfs_root *root, u64 ino,
1525                          u64 *dir, u64 *dir_gen, struct fs_path *name)
1526 {
1527         int ret;
1528         struct btrfs_key key;
1529         struct btrfs_key found_key;
1530         struct btrfs_path *path;
1531         struct btrfs_inode_ref *iref;
1532         int len;
1533
1534         path = alloc_path_for_send();
1535         if (!path)
1536                 return -ENOMEM;
1537
1538         key.objectid = ino;
1539         key.type = BTRFS_INODE_REF_KEY;
1540         key.offset = 0;
1541
1542         ret = btrfs_search_slot_for_read(root, &key, path, 1, 0);
1543         if (ret < 0)
1544                 goto out;
1545         if (!ret)
1546                 btrfs_item_key_to_cpu(path->nodes[0], &found_key,
1547                                 path->slots[0]);
1548         if (ret || found_key.objectid != key.objectid ||
1549             found_key.type != key.type) {
1550                 ret = -ENOENT;
1551                 goto out;
1552         }
1553
1554         iref = btrfs_item_ptr(path->nodes[0], path->slots[0],
1555                         struct btrfs_inode_ref);
1556         len = btrfs_inode_ref_name_len(path->nodes[0], iref);
1557         ret = fs_path_add_from_extent_buffer(name, path->nodes[0],
1558                         (unsigned long)(iref + 1), len);
1559         if (ret < 0)
1560                 goto out;
1561         btrfs_release_path(path);
1562
1563         ret = get_inode_info(root, found_key.offset, NULL, dir_gen, NULL, NULL,
1564                         NULL, NULL);
1565         if (ret < 0)
1566                 goto out;
1567
1568         *dir = found_key.offset;
1569
1570 out:
1571         btrfs_free_path(path);
1572         return ret;
1573 }
1574
1575 static int is_first_ref(struct send_ctx *sctx,
1576                         struct btrfs_root *root,
1577                         u64 ino, u64 dir,
1578                         const char *name, int name_len)
1579 {
1580         int ret;
1581         struct fs_path *tmp_name;
1582         u64 tmp_dir;
1583         u64 tmp_dir_gen;
1584
1585         tmp_name = fs_path_alloc(sctx);
1586         if (!tmp_name)
1587                 return -ENOMEM;
1588
1589         ret = get_first_ref(sctx, root, ino, &tmp_dir, &tmp_dir_gen, tmp_name);
1590         if (ret < 0)
1591                 goto out;
1592
1593         if (name_len != fs_path_len(tmp_name)) {
1594                 ret = 0;
1595                 goto out;
1596         }
1597
1598         ret = memcmp(tmp_name->start, name, name_len);
1599         if (ret)
1600                 ret = 0;
1601         else
1602                 ret = 1;
1603
1604 out:
1605         fs_path_free(sctx, tmp_name);
1606         return ret;
1607 }
1608
1609 static int will_overwrite_ref(struct send_ctx *sctx, u64 dir, u64 dir_gen,
1610                               const char *name, int name_len,
1611                               u64 *who_ino, u64 *who_gen)
1612 {
1613         int ret = 0;
1614         u64 other_inode = 0;
1615         u8 other_type = 0;
1616
1617         if (!sctx->parent_root)
1618                 goto out;
1619
1620         ret = is_inode_existent(sctx, dir, dir_gen);
1621         if (ret <= 0)
1622                 goto out;
1623
1624         ret = lookup_dir_item_inode(sctx->parent_root, dir, name, name_len,
1625                         &other_inode, &other_type);
1626         if (ret < 0 && ret != -ENOENT)
1627                 goto out;
1628         if (ret) {
1629                 ret = 0;
1630                 goto out;
1631         }
1632
1633         if (other_inode > sctx->send_progress) {
1634                 ret = get_inode_info(sctx->parent_root, other_inode, NULL,
1635                                 who_gen, NULL, NULL, NULL, NULL);
1636                 if (ret < 0)
1637                         goto out;
1638
1639                 ret = 1;
1640                 *who_ino = other_inode;
1641         } else {
1642                 ret = 0;
1643         }
1644
1645 out:
1646         return ret;
1647 }
1648
1649 static int did_overwrite_ref(struct send_ctx *sctx,
1650                             u64 dir, u64 dir_gen,
1651                             u64 ino, u64 ino_gen,
1652                             const char *name, int name_len)
1653 {
1654         int ret = 0;
1655         u64 gen;
1656         u64 ow_inode;
1657         u8 other_type;
1658
1659         if (!sctx->parent_root)
1660                 goto out;
1661
1662         ret = is_inode_existent(sctx, dir, dir_gen);
1663         if (ret <= 0)
1664                 goto out;
1665
1666         /* check if the ref was overwritten by another ref */
1667         ret = lookup_dir_item_inode(sctx->send_root, dir, name, name_len,
1668                         &ow_inode, &other_type);
1669         if (ret < 0 && ret != -ENOENT)
1670                 goto out;
1671         if (ret) {
1672                 /* was never and will never be overwritten */
1673                 ret = 0;
1674                 goto out;
1675         }
1676
1677         ret = get_inode_info(sctx->send_root, ow_inode, NULL, &gen, NULL, NULL,
1678                         NULL, NULL);
1679         if (ret < 0)
1680                 goto out;
1681
1682         if (ow_inode == ino && gen == ino_gen) {
1683                 ret = 0;
1684                 goto out;
1685         }
1686
1687         /* we know that it is or will be overwritten. check this now */
1688         if (ow_inode < sctx->send_progress)
1689                 ret = 1;
1690         else
1691                 ret = 0;
1692
1693 out:
1694         return ret;
1695 }
1696
1697 static int did_overwrite_first_ref(struct send_ctx *sctx, u64 ino, u64 gen)
1698 {
1699         int ret = 0;
1700         struct fs_path *name = NULL;
1701         u64 dir;
1702         u64 dir_gen;
1703
1704         if (!sctx->parent_root)
1705                 goto out;
1706
1707         name = fs_path_alloc(sctx);
1708         if (!name)
1709                 return -ENOMEM;
1710
1711         ret = get_first_ref(sctx, sctx->parent_root, ino, &dir, &dir_gen, name);
1712         if (ret < 0)
1713                 goto out;
1714
1715         ret = did_overwrite_ref(sctx, dir, dir_gen, ino, gen,
1716                         name->start, fs_path_len(name));
1717         if (ret < 0)
1718                 goto out;
1719
1720 out:
1721         fs_path_free(sctx, name);
1722         return ret;
1723 }
1724
1725 static int name_cache_insert(struct send_ctx *sctx,
1726                              struct name_cache_entry *nce)
1727 {
1728         int ret = 0;
1729         struct name_cache_entry **ncea;
1730
1731         ncea = radix_tree_lookup(&sctx->name_cache, nce->ino);
1732         if (ncea) {
1733                 if (!ncea[0])
1734                         ncea[0] = nce;
1735                 else if (!ncea[1])
1736                         ncea[1] = nce;
1737                 else
1738                         BUG();
1739         } else {
1740                 ncea = kmalloc(sizeof(void *) * 2, GFP_NOFS);
1741                 if (!ncea)
1742                         return -ENOMEM;
1743
1744                 ncea[0] = nce;
1745                 ncea[1] = NULL;
1746                 ret = radix_tree_insert(&sctx->name_cache, nce->ino, ncea);
1747                 if (ret < 0)
1748                         return ret;
1749         }
1750         list_add_tail(&nce->list, &sctx->name_cache_list);
1751         sctx->name_cache_size++;
1752
1753         return ret;
1754 }
1755
1756 static void name_cache_delete(struct send_ctx *sctx,
1757                               struct name_cache_entry *nce)
1758 {
1759         struct name_cache_entry **ncea;
1760
1761         ncea = radix_tree_lookup(&sctx->name_cache, nce->ino);
1762         BUG_ON(!ncea);
1763
1764         if (ncea[0] == nce)
1765                 ncea[0] = NULL;
1766         else if (ncea[1] == nce)
1767                 ncea[1] = NULL;
1768         else
1769                 BUG();
1770
1771         if (!ncea[0] && !ncea[1]) {
1772                 radix_tree_delete(&sctx->name_cache, nce->ino);
1773                 kfree(ncea);
1774         }
1775
1776         list_del(&nce->list);
1777
1778         sctx->name_cache_size--;
1779 }
1780
1781 static struct name_cache_entry *name_cache_search(struct send_ctx *sctx,
1782                                                     u64 ino, u64 gen)
1783 {
1784         struct name_cache_entry **ncea;
1785
1786         ncea = radix_tree_lookup(&sctx->name_cache, ino);
1787         if (!ncea)
1788                 return NULL;
1789
1790         if (ncea[0] && ncea[0]->gen == gen)
1791                 return ncea[0];
1792         else if (ncea[1] && ncea[1]->gen == gen)
1793                 return ncea[1];
1794         return NULL;
1795 }
1796
1797 static void name_cache_used(struct send_ctx *sctx, struct name_cache_entry *nce)
1798 {
1799         list_del(&nce->list);
1800         list_add_tail(&nce->list, &sctx->name_cache_list);
1801 }
1802
1803 static void name_cache_clean_unused(struct send_ctx *sctx)
1804 {
1805         struct name_cache_entry *nce;
1806
1807         if (sctx->name_cache_size < SEND_CTX_NAME_CACHE_CLEAN_SIZE)
1808                 return;
1809
1810         while (sctx->name_cache_size > SEND_CTX_MAX_NAME_CACHE_SIZE) {
1811                 nce = list_entry(sctx->name_cache_list.next,
1812                                 struct name_cache_entry, list);
1813                 name_cache_delete(sctx, nce);
1814                 kfree(nce);
1815         }
1816 }
1817
1818 static void name_cache_free(struct send_ctx *sctx)
1819 {
1820         struct name_cache_entry *nce;
1821         struct name_cache_entry *tmp;
1822
1823         list_for_each_entry_safe(nce, tmp, &sctx->name_cache_list, list) {
1824                 name_cache_delete(sctx, nce);
1825         }
1826 }
1827
1828 static int __get_cur_name_and_parent(struct send_ctx *sctx,
1829                                      u64 ino, u64 gen,
1830                                      u64 *parent_ino,
1831                                      u64 *parent_gen,
1832                                      struct fs_path *dest)
1833 {
1834         int ret;
1835         int nce_ret;
1836         struct btrfs_path *path = NULL;
1837         struct name_cache_entry *nce = NULL;
1838
1839         nce = name_cache_search(sctx, ino, gen);
1840         if (nce) {
1841                 if (ino < sctx->send_progress && nce->need_later_update) {
1842                         name_cache_delete(sctx, nce);
1843                         kfree(nce);
1844                         nce = NULL;
1845                 } else {
1846                         name_cache_used(sctx, nce);
1847                         *parent_ino = nce->parent_ino;
1848                         *parent_gen = nce->parent_gen;
1849                         ret = fs_path_add(dest, nce->name, nce->name_len);
1850                         if (ret < 0)
1851                                 goto out;
1852                         ret = nce->ret;
1853                         goto out;
1854                 }
1855         }
1856
1857         path = alloc_path_for_send();
1858         if (!path)
1859                 return -ENOMEM;
1860
1861         ret = is_inode_existent(sctx, ino, gen);
1862         if (ret < 0)
1863                 goto out;
1864
1865         if (!ret) {
1866                 ret = gen_unique_name(sctx, ino, gen, dest);
1867                 if (ret < 0)
1868                         goto out;
1869                 ret = 1;
1870                 goto out_cache;
1871         }
1872
1873         if (ino < sctx->send_progress)
1874                 ret = get_first_ref(sctx, sctx->send_root, ino,
1875                                 parent_ino, parent_gen, dest);
1876         else
1877                 ret = get_first_ref(sctx, sctx->parent_root, ino,
1878                                 parent_ino, parent_gen, dest);
1879         if (ret < 0)
1880                 goto out;
1881
1882         ret = did_overwrite_ref(sctx, *parent_ino, *parent_gen, ino, gen,
1883                         dest->start, dest->end - dest->start);
1884         if (ret < 0)
1885                 goto out;
1886         if (ret) {
1887                 fs_path_reset(dest);
1888                 ret = gen_unique_name(sctx, ino, gen, dest);
1889                 if (ret < 0)
1890                         goto out;
1891                 ret = 1;
1892         }
1893
1894 out_cache:
1895         nce = kmalloc(sizeof(*nce) + fs_path_len(dest) + 1, GFP_NOFS);
1896         if (!nce) {
1897                 ret = -ENOMEM;
1898                 goto out;
1899         }
1900
1901         nce->ino = ino;
1902         nce->gen = gen;
1903         nce->parent_ino = *parent_ino;
1904         nce->parent_gen = *parent_gen;
1905         nce->name_len = fs_path_len(dest);
1906         nce->ret = ret;
1907         strcpy(nce->name, dest->start);
1908         memset(&nce->use_list, 0, sizeof(nce->use_list));
1909
1910         if (ino < sctx->send_progress)
1911                 nce->need_later_update = 0;
1912         else
1913                 nce->need_later_update = 1;
1914
1915         nce_ret = name_cache_insert(sctx, nce);
1916         if (nce_ret < 0)
1917                 ret = nce_ret;
1918         name_cache_clean_unused(sctx);
1919
1920 out:
1921         btrfs_free_path(path);
1922         return ret;
1923 }
1924
1925 /*
1926  * Magic happens here. This function returns the first ref to an inode as it
1927  * would look like while receiving the stream at this point in time.
1928  * We walk the path up to the root. For every inode in between, we check if it
1929  * was already processed/sent. If yes, we continue with the parent as found
1930  * in send_root. If not, we continue with the parent as found in parent_root.
1931  * If we encounter an inode that was deleted at this point in time, we use the
1932  * inodes "orphan" name instead of the real name and stop. Same with new inodes
1933  * that were not created yet and overwritten inodes/refs.
1934  *
1935  * When do we have have orphan inodes:
1936  * 1. When an inode is freshly created and thus no valid refs are available yet
1937  * 2. When a directory lost all it's refs (deleted) but still has dir items
1938  *    inside which were not processed yet (pending for move/delete). If anyone
1939  *    tried to get the path to the dir items, it would get a path inside that
1940  *    orphan directory.
1941  * 3. When an inode is moved around or gets new links, it may overwrite the ref
1942  *    of an unprocessed inode. If in that case the first ref would be
1943  *    overwritten, the overwritten inode gets "orphanized". Later when we
1944  *    process this overwritten inode, it is restored at a new place by moving
1945  *    the orphan inode.
1946  *
1947  * sctx->send_progress tells this function at which point in time receiving
1948  * would be.
1949  */
1950 static int get_cur_path(struct send_ctx *sctx, u64 ino, u64 gen,
1951                         struct fs_path *dest)
1952 {
1953         int ret = 0;
1954         struct fs_path *name = NULL;
1955         u64 parent_inode = 0;
1956         u64 parent_gen = 0;
1957         int stop = 0;
1958
1959         name = fs_path_alloc(sctx);
1960         if (!name) {
1961                 ret = -ENOMEM;
1962                 goto out;
1963         }
1964
1965         dest->reversed = 1;
1966         fs_path_reset(dest);
1967
1968         while (!stop && ino != BTRFS_FIRST_FREE_OBJECTID) {
1969                 fs_path_reset(name);
1970
1971                 ret = __get_cur_name_and_parent(sctx, ino, gen,
1972                                 &parent_inode, &parent_gen, name);
1973                 if (ret < 0)
1974                         goto out;
1975                 if (ret)
1976                         stop = 1;
1977
1978                 ret = fs_path_add_path(dest, name);
1979                 if (ret < 0)
1980                         goto out;
1981
1982                 ino = parent_inode;
1983                 gen = parent_gen;
1984         }
1985
1986 out:
1987         fs_path_free(sctx, name);
1988         if (!ret)
1989                 fs_path_unreverse(dest);
1990         return ret;
1991 }
1992
1993 /*
1994  * Called for regular files when sending extents data. Opens a struct file
1995  * to read from the file.
1996  */
1997 static int open_cur_inode_file(struct send_ctx *sctx)
1998 {
1999         int ret = 0;
2000         struct btrfs_key key;
2001         struct path path;
2002         struct inode *inode;
2003         struct dentry *dentry;
2004         struct file *filp;
2005         int new = 0;
2006
2007         if (sctx->cur_inode_filp)
2008                 goto out;
2009
2010         key.objectid = sctx->cur_ino;
2011         key.type = BTRFS_INODE_ITEM_KEY;
2012         key.offset = 0;
2013
2014         inode = btrfs_iget(sctx->send_root->fs_info->sb, &key, sctx->send_root,
2015                         &new);
2016         if (IS_ERR(inode)) {
2017                 ret = PTR_ERR(inode);
2018                 goto out;
2019         }
2020
2021         dentry = d_obtain_alias(inode);
2022         inode = NULL;
2023         if (IS_ERR(dentry)) {
2024                 ret = PTR_ERR(dentry);
2025                 goto out;
2026         }
2027
2028         path.mnt = sctx->mnt;
2029         path.dentry = dentry;
2030         filp = dentry_open(&path, O_RDONLY | O_LARGEFILE, current_cred());
2031         dput(dentry);
2032         dentry = NULL;
2033         if (IS_ERR(filp)) {
2034                 ret = PTR_ERR(filp);
2035                 goto out;
2036         }
2037         sctx->cur_inode_filp = filp;
2038
2039 out:
2040         /*
2041          * no xxxput required here as every vfs op
2042          * does it by itself on failure
2043          */
2044         return ret;
2045 }
2046
2047 /*
2048  * Closes the struct file that was created in open_cur_inode_file
2049  */
2050 static int close_cur_inode_file(struct send_ctx *sctx)
2051 {
2052         int ret = 0;
2053
2054         if (!sctx->cur_inode_filp)
2055                 goto out;
2056
2057         ret = filp_close(sctx->cur_inode_filp, NULL);
2058         sctx->cur_inode_filp = NULL;
2059
2060 out:
2061         return ret;
2062 }
2063
2064 /*
2065  * Sends a BTRFS_SEND_C_SUBVOL command/item to userspace
2066  */
2067 static int send_subvol_begin(struct send_ctx *sctx)
2068 {
2069         int ret;
2070         struct btrfs_root *send_root = sctx->send_root;
2071         struct btrfs_root *parent_root = sctx->parent_root;
2072         struct btrfs_path *path;
2073         struct btrfs_key key;
2074         struct btrfs_root_ref *ref;
2075         struct extent_buffer *leaf;
2076         char *name = NULL;
2077         int namelen;
2078
2079         path = alloc_path_for_send();
2080         if (!path)
2081                 return -ENOMEM;
2082
2083         name = kmalloc(BTRFS_PATH_NAME_MAX, GFP_NOFS);
2084         if (!name) {
2085                 btrfs_free_path(path);
2086                 return -ENOMEM;
2087         }
2088
2089         key.objectid = send_root->objectid;
2090         key.type = BTRFS_ROOT_BACKREF_KEY;
2091         key.offset = 0;
2092
2093         ret = btrfs_search_slot_for_read(send_root->fs_info->tree_root,
2094                                 &key, path, 1, 0);
2095         if (ret < 0)
2096                 goto out;
2097         if (ret) {
2098                 ret = -ENOENT;
2099                 goto out;
2100         }
2101
2102         leaf = path->nodes[0];
2103         btrfs_item_key_to_cpu(leaf, &key, path->slots[0]);
2104         if (key.type != BTRFS_ROOT_BACKREF_KEY ||
2105             key.objectid != send_root->objectid) {
2106                 ret = -ENOENT;
2107                 goto out;
2108         }
2109         ref = btrfs_item_ptr(leaf, path->slots[0], struct btrfs_root_ref);
2110         namelen = btrfs_root_ref_name_len(leaf, ref);
2111         read_extent_buffer(leaf, name, (unsigned long)(ref + 1), namelen);
2112         btrfs_release_path(path);
2113
2114         if (ret < 0)
2115                 goto out;
2116
2117         if (parent_root) {
2118                 ret = begin_cmd(sctx, BTRFS_SEND_C_SNAPSHOT);
2119                 if (ret < 0)
2120                         goto out;
2121         } else {
2122                 ret = begin_cmd(sctx, BTRFS_SEND_C_SUBVOL);
2123                 if (ret < 0)
2124                         goto out;
2125         }
2126
2127         TLV_PUT_STRING(sctx, BTRFS_SEND_A_PATH, name, namelen);
2128         TLV_PUT_UUID(sctx, BTRFS_SEND_A_UUID,
2129                         sctx->send_root->root_item.uuid);
2130         TLV_PUT_U64(sctx, BTRFS_SEND_A_CTRANSID,
2131                         sctx->send_root->root_item.ctransid);
2132         if (parent_root) {
2133                 TLV_PUT_UUID(sctx, BTRFS_SEND_A_CLONE_UUID,
2134                                 sctx->parent_root->root_item.uuid);
2135                 TLV_PUT_U64(sctx, BTRFS_SEND_A_CLONE_CTRANSID,
2136                                 sctx->parent_root->root_item.ctransid);
2137         }
2138
2139         ret = send_cmd(sctx);
2140
2141 tlv_put_failure:
2142 out:
2143         btrfs_free_path(path);
2144         kfree(name);
2145         return ret;
2146 }
2147
2148 static int send_truncate(struct send_ctx *sctx, u64 ino, u64 gen, u64 size)
2149 {
2150         int ret = 0;
2151         struct fs_path *p;
2152
2153 verbose_printk("btrfs: send_truncate %llu size=%llu\n", ino, size);
2154
2155         p = fs_path_alloc(sctx);
2156         if (!p)
2157                 return -ENOMEM;
2158
2159         ret = begin_cmd(sctx, BTRFS_SEND_C_TRUNCATE);
2160         if (ret < 0)
2161                 goto out;
2162
2163         ret = get_cur_path(sctx, ino, gen, p);
2164         if (ret < 0)
2165                 goto out;
2166         TLV_PUT_PATH(sctx, BTRFS_SEND_A_PATH, p);
2167         TLV_PUT_U64(sctx, BTRFS_SEND_A_SIZE, size);
2168
2169         ret = send_cmd(sctx);
2170
2171 tlv_put_failure:
2172 out:
2173         fs_path_free(sctx, p);
2174         return ret;
2175 }
2176
2177 static int send_chmod(struct send_ctx *sctx, u64 ino, u64 gen, u64 mode)
2178 {
2179         int ret = 0;
2180         struct fs_path *p;
2181
2182 verbose_printk("btrfs: send_chmod %llu mode=%llu\n", ino, mode);
2183
2184         p = fs_path_alloc(sctx);
2185         if (!p)
2186                 return -ENOMEM;
2187
2188         ret = begin_cmd(sctx, BTRFS_SEND_C_CHMOD);
2189         if (ret < 0)
2190                 goto out;
2191
2192         ret = get_cur_path(sctx, ino, gen, p);
2193         if (ret < 0)
2194                 goto out;
2195         TLV_PUT_PATH(sctx, BTRFS_SEND_A_PATH, p);
2196         TLV_PUT_U64(sctx, BTRFS_SEND_A_MODE, mode & 07777);
2197
2198         ret = send_cmd(sctx);
2199
2200 tlv_put_failure:
2201 out:
2202         fs_path_free(sctx, p);
2203         return ret;
2204 }
2205
2206 static int send_chown(struct send_ctx *sctx, u64 ino, u64 gen, u64 uid, u64 gid)
2207 {
2208         int ret = 0;
2209         struct fs_path *p;
2210
2211 verbose_printk("btrfs: send_chown %llu uid=%llu, gid=%llu\n", ino, uid, gid);
2212
2213         p = fs_path_alloc(sctx);
2214         if (!p)
2215                 return -ENOMEM;
2216
2217         ret = begin_cmd(sctx, BTRFS_SEND_C_CHOWN);
2218         if (ret < 0)
2219                 goto out;
2220
2221         ret = get_cur_path(sctx, ino, gen, p);
2222         if (ret < 0)
2223                 goto out;
2224         TLV_PUT_PATH(sctx, BTRFS_SEND_A_PATH, p);
2225         TLV_PUT_U64(sctx, BTRFS_SEND_A_UID, uid);
2226         TLV_PUT_U64(sctx, BTRFS_SEND_A_GID, gid);
2227
2228         ret = send_cmd(sctx);
2229
2230 tlv_put_failure:
2231 out:
2232         fs_path_free(sctx, p);
2233         return ret;
2234 }
2235
2236 static int send_utimes(struct send_ctx *sctx, u64 ino, u64 gen)
2237 {
2238         int ret = 0;
2239         struct fs_path *p = NULL;
2240         struct btrfs_inode_item *ii;
2241         struct btrfs_path *path = NULL;
2242         struct extent_buffer *eb;
2243         struct btrfs_key key;
2244         int slot;
2245
2246 verbose_printk("btrfs: send_utimes %llu\n", ino);
2247
2248         p = fs_path_alloc(sctx);
2249         if (!p)
2250                 return -ENOMEM;
2251
2252         path = alloc_path_for_send();
2253         if (!path) {
2254                 ret = -ENOMEM;
2255                 goto out;
2256         }
2257
2258         key.objectid = ino;
2259         key.type = BTRFS_INODE_ITEM_KEY;
2260         key.offset = 0;
2261         ret = btrfs_search_slot(NULL, sctx->send_root, &key, path, 0, 0);
2262         if (ret < 0)
2263                 goto out;
2264
2265         eb = path->nodes[0];
2266         slot = path->slots[0];
2267         ii = btrfs_item_ptr(eb, slot, struct btrfs_inode_item);
2268
2269         ret = begin_cmd(sctx, BTRFS_SEND_C_UTIMES);
2270         if (ret < 0)
2271                 goto out;
2272
2273         ret = get_cur_path(sctx, ino, gen, p);
2274         if (ret < 0)
2275                 goto out;
2276         TLV_PUT_PATH(sctx, BTRFS_SEND_A_PATH, p);
2277         TLV_PUT_BTRFS_TIMESPEC(sctx, BTRFS_SEND_A_ATIME, eb,
2278                         btrfs_inode_atime(ii));
2279         TLV_PUT_BTRFS_TIMESPEC(sctx, BTRFS_SEND_A_MTIME, eb,
2280                         btrfs_inode_mtime(ii));
2281         TLV_PUT_BTRFS_TIMESPEC(sctx, BTRFS_SEND_A_CTIME, eb,
2282                         btrfs_inode_ctime(ii));
2283         /* TODO otime? */
2284
2285         ret = send_cmd(sctx);
2286
2287 tlv_put_failure:
2288 out:
2289         fs_path_free(sctx, p);
2290         btrfs_free_path(path);
2291         return ret;
2292 }
2293
2294 /*
2295  * Sends a BTRFS_SEND_C_MKXXX or SYMLINK command to user space. We don't have
2296  * a valid path yet because we did not process the refs yet. So, the inode
2297  * is created as orphan.
2298  */
2299 static int send_create_inode(struct send_ctx *sctx, struct btrfs_path *path,
2300                              struct btrfs_key *key)
2301 {
2302         int ret = 0;
2303         struct extent_buffer *eb = path->nodes[0];
2304         struct btrfs_inode_item *ii;
2305         struct fs_path *p;
2306         int slot = path->slots[0];
2307         int cmd;
2308         u64 mode;
2309
2310 verbose_printk("btrfs: send_create_inode %llu\n", sctx->cur_ino);
2311
2312         p = fs_path_alloc(sctx);
2313         if (!p)
2314                 return -ENOMEM;
2315
2316         ii = btrfs_item_ptr(eb, slot, struct btrfs_inode_item);
2317         mode = btrfs_inode_mode(eb, ii);
2318
2319         if (S_ISREG(mode))
2320                 cmd = BTRFS_SEND_C_MKFILE;
2321         else if (S_ISDIR(mode))
2322                 cmd = BTRFS_SEND_C_MKDIR;
2323         else if (S_ISLNK(mode))
2324                 cmd = BTRFS_SEND_C_SYMLINK;
2325         else if (S_ISCHR(mode) || S_ISBLK(mode))
2326                 cmd = BTRFS_SEND_C_MKNOD;
2327         else if (S_ISFIFO(mode))
2328                 cmd = BTRFS_SEND_C_MKFIFO;
2329         else if (S_ISSOCK(mode))
2330                 cmd = BTRFS_SEND_C_MKSOCK;
2331         else {
2332                 printk(KERN_WARNING "btrfs: unexpected inode type %o",
2333                                 (int)(mode & S_IFMT));
2334                 ret = -ENOTSUPP;
2335                 goto out;
2336         }
2337
2338         ret = begin_cmd(sctx, cmd);
2339         if (ret < 0)
2340                 goto out;
2341
2342         ret = gen_unique_name(sctx, sctx->cur_ino, sctx->cur_inode_gen, p);
2343         if (ret < 0)
2344                 goto out;
2345
2346         TLV_PUT_PATH(sctx, BTRFS_SEND_A_PATH, p);
2347         TLV_PUT_U64(sctx, BTRFS_SEND_A_INO, sctx->cur_ino);
2348
2349         if (S_ISLNK(mode)) {
2350                 fs_path_reset(p);
2351                 ret = read_symlink(sctx, sctx->send_root, sctx->cur_ino, p);
2352                 if (ret < 0)
2353                         goto out;
2354                 TLV_PUT_PATH(sctx, BTRFS_SEND_A_PATH_LINK, p);
2355         } else if (S_ISCHR(mode) || S_ISBLK(mode) ||
2356                    S_ISFIFO(mode) || S_ISSOCK(mode)) {
2357                 TLV_PUT_U64(sctx, BTRFS_SEND_A_RDEV, btrfs_inode_rdev(eb, ii));
2358         }
2359
2360         ret = send_cmd(sctx);
2361         if (ret < 0)
2362                 goto out;
2363
2364
2365 tlv_put_failure:
2366 out:
2367         fs_path_free(sctx, p);
2368         return ret;
2369 }
2370
2371 struct recorded_ref {
2372         struct list_head list;
2373         char *dir_path;
2374         char *name;
2375         struct fs_path *full_path;
2376         u64 dir;
2377         u64 dir_gen;
2378         int dir_path_len;
2379         int name_len;
2380 };
2381
2382 /*
2383  * We need to process new refs before deleted refs, but compare_tree gives us
2384  * everything mixed. So we first record all refs and later process them.
2385  * This function is a helper to record one ref.
2386  */
2387 static int record_ref(struct list_head *head, u64 dir,
2388                       u64 dir_gen, struct fs_path *path)
2389 {
2390         struct recorded_ref *ref;
2391         char *tmp;
2392
2393         ref = kmalloc(sizeof(*ref), GFP_NOFS);
2394         if (!ref)
2395                 return -ENOMEM;
2396
2397         ref->dir = dir;
2398         ref->dir_gen = dir_gen;
2399         ref->full_path = path;
2400
2401         tmp = strrchr(ref->full_path->start, '/');
2402         if (!tmp) {
2403                 ref->name_len = ref->full_path->end - ref->full_path->start;
2404                 ref->name = ref->full_path->start;
2405                 ref->dir_path_len = 0;
2406                 ref->dir_path = ref->full_path->start;
2407         } else {
2408                 tmp++;
2409                 ref->name_len = ref->full_path->end - tmp;
2410                 ref->name = tmp;
2411                 ref->dir_path = ref->full_path->start;
2412                 ref->dir_path_len = ref->full_path->end -
2413                                 ref->full_path->start - 1 - ref->name_len;
2414         }
2415
2416         list_add_tail(&ref->list, head);
2417         return 0;
2418 }
2419
2420 static void __free_recorded_refs(struct send_ctx *sctx, struct list_head *head)
2421 {
2422         struct recorded_ref *cur;
2423         struct recorded_ref *tmp;
2424
2425         list_for_each_entry_safe(cur, tmp, head, list) {
2426                 fs_path_free(sctx, cur->full_path);
2427                 kfree(cur);
2428         }
2429         INIT_LIST_HEAD(head);
2430 }
2431
2432 static void free_recorded_refs(struct send_ctx *sctx)
2433 {
2434         __free_recorded_refs(sctx, &sctx->new_refs);
2435         __free_recorded_refs(sctx, &sctx->deleted_refs);
2436 }
2437
2438 /*
2439  * Renames/moves a file/dir to it's orphan name. Used when the first
2440  * ref of an unprocessed inode gets overwritten and for all non empty
2441  * directories.
2442  */
2443 static int orphanize_inode(struct send_ctx *sctx, u64 ino, u64 gen,
2444                           struct fs_path *path)
2445 {
2446         int ret;
2447         struct fs_path *orphan;
2448
2449         orphan = fs_path_alloc(sctx);
2450         if (!orphan)
2451                 return -ENOMEM;
2452
2453         ret = gen_unique_name(sctx, ino, gen, orphan);
2454         if (ret < 0)
2455                 goto out;
2456
2457         ret = send_rename(sctx, path, orphan);
2458
2459 out:
2460         fs_path_free(sctx, orphan);
2461         return ret;
2462 }
2463
2464 /*
2465  * Returns 1 if a directory can be removed at this point in time.
2466  * We check this by iterating all dir items and checking if the inode behind
2467  * the dir item was already processed.
2468  */
2469 static int can_rmdir(struct send_ctx *sctx, u64 dir, u64 send_progress)
2470 {
2471         int ret = 0;
2472         struct btrfs_root *root = sctx->parent_root;
2473         struct btrfs_path *path;
2474         struct btrfs_key key;
2475         struct btrfs_key found_key;
2476         struct btrfs_key loc;
2477         struct btrfs_dir_item *di;
2478
2479         path = alloc_path_for_send();
2480         if (!path)
2481                 return -ENOMEM;
2482
2483         key.objectid = dir;
2484         key.type = BTRFS_DIR_INDEX_KEY;
2485         key.offset = 0;
2486
2487         while (1) {
2488                 ret = btrfs_search_slot_for_read(root, &key, path, 1, 0);
2489                 if (ret < 0)
2490                         goto out;
2491                 if (!ret) {
2492                         btrfs_item_key_to_cpu(path->nodes[0], &found_key,
2493                                         path->slots[0]);
2494                 }
2495                 if (ret || found_key.objectid != key.objectid ||
2496                     found_key.type != key.type) {
2497                         break;
2498                 }
2499
2500                 di = btrfs_item_ptr(path->nodes[0], path->slots[0],
2501                                 struct btrfs_dir_item);
2502                 btrfs_dir_item_key_to_cpu(path->nodes[0], di, &loc);
2503
2504                 if (loc.objectid > send_progress) {
2505                         ret = 0;
2506                         goto out;
2507                 }
2508
2509                 btrfs_release_path(path);
2510                 key.offset = found_key.offset + 1;
2511         }
2512
2513         ret = 1;
2514
2515 out:
2516         btrfs_free_path(path);
2517         return ret;
2518 }
2519
2520 struct finish_unordered_dir_ctx {
2521         struct send_ctx *sctx;
2522         struct fs_path *cur_path;
2523         struct fs_path *dir_path;
2524         u64 dir_ino;
2525         int need_delete;
2526         int delete_pass;
2527 };
2528
2529 int __finish_unordered_dir(int num, struct btrfs_key *di_key,
2530                            const char *name, int name_len,
2531                            const char *data, int data_len,
2532                            u8 type, void *ctx)
2533 {
2534         int ret = 0;
2535         struct finish_unordered_dir_ctx *fctx = ctx;
2536         struct send_ctx *sctx = fctx->sctx;
2537         u64 di_gen;
2538         u64 di_mode;
2539         int is_orphan = 0;
2540
2541         if (di_key->objectid >= fctx->dir_ino)
2542                 goto out;
2543
2544         fs_path_reset(fctx->cur_path);
2545
2546         ret = get_inode_info(sctx->send_root, di_key->objectid,
2547                         NULL, &di_gen, &di_mode, NULL, NULL, NULL);
2548         if (ret < 0)
2549                 goto out;
2550
2551         ret = is_first_ref(sctx, sctx->send_root, di_key->objectid,
2552                         fctx->dir_ino, name, name_len);
2553         if (ret < 0)
2554                 goto out;
2555         if (ret) {
2556                 is_orphan = 1;
2557                 ret = gen_unique_name(sctx, di_key->objectid, di_gen,
2558                                 fctx->cur_path);
2559         } else {
2560                 ret = get_cur_path(sctx, di_key->objectid, di_gen,
2561                                 fctx->cur_path);
2562         }
2563         if (ret < 0)
2564                 goto out;
2565
2566         ret = fs_path_add(fctx->dir_path, name, name_len);
2567         if (ret < 0)
2568                 goto out;
2569
2570         if (!fctx->delete_pass) {
2571                 if (S_ISDIR(di_mode)) {
2572                         ret = send_rename(sctx, fctx->cur_path,
2573                                         fctx->dir_path);
2574                 } else {
2575                         ret = send_link(sctx, fctx->dir_path,
2576                                         fctx->cur_path);
2577                         if (is_orphan)
2578                                 fctx->need_delete = 1;
2579                 }
2580         } else if (!S_ISDIR(di_mode)) {
2581                 ret = send_unlink(sctx, fctx->cur_path);
2582         } else {
2583                 ret = 0;
2584         }
2585
2586         fs_path_remove(fctx->dir_path);
2587
2588 out:
2589         return ret;
2590 }
2591
2592 /*
2593  * Go through all dir items and see if we find refs which could not be created
2594  * in the past because the dir did not exist at that time.
2595  */
2596 static int finish_outoforder_dir(struct send_ctx *sctx, u64 dir, u64 dir_gen)
2597 {
2598         int ret = 0;
2599         struct btrfs_path *path = NULL;
2600         struct btrfs_key key;
2601         struct btrfs_key found_key;
2602         struct extent_buffer *eb;
2603         struct finish_unordered_dir_ctx fctx;
2604         int slot;
2605
2606         path = alloc_path_for_send();
2607         if (!path) {
2608                 ret = -ENOMEM;
2609                 goto out;
2610         }
2611
2612         memset(&fctx, 0, sizeof(fctx));
2613         fctx.sctx = sctx;
2614         fctx.cur_path = fs_path_alloc(sctx);
2615         fctx.dir_path = fs_path_alloc(sctx);
2616         if (!fctx.cur_path || !fctx.dir_path) {
2617                 ret = -ENOMEM;
2618                 goto out;
2619         }
2620         fctx.dir_ino = dir;
2621
2622         ret = get_cur_path(sctx, dir, dir_gen, fctx.dir_path);
2623         if (ret < 0)
2624                 goto out;
2625
2626         /*
2627          * We do two passes. The first links in the new refs and the second
2628          * deletes orphans if required. Deletion of orphans is not required for
2629          * directory inodes, as we always have only one ref and use rename
2630          * instead of link for those.
2631          */
2632
2633 again:
2634         key.objectid = dir;
2635         key.type = BTRFS_DIR_ITEM_KEY;
2636         key.offset = 0;
2637         while (1) {
2638                 ret = btrfs_search_slot_for_read(sctx->send_root, &key, path,
2639                                 1, 0);
2640                 if (ret < 0)
2641                         goto out;
2642                 eb = path->nodes[0];
2643                 slot = path->slots[0];
2644                 btrfs_item_key_to_cpu(eb, &found_key, slot);
2645
2646                 if (found_key.objectid != key.objectid ||
2647                     found_key.type != key.type) {
2648                         btrfs_release_path(path);
2649                         break;
2650                 }
2651
2652                 ret = iterate_dir_item(sctx, sctx->send_root, path,
2653                                 &found_key, __finish_unordered_dir,
2654                                 &fctx);
2655                 if (ret < 0)
2656                         goto out;
2657
2658                 key.offset = found_key.offset + 1;
2659                 btrfs_release_path(path);
2660         }
2661
2662         if (!fctx.delete_pass && fctx.need_delete) {
2663                 fctx.delete_pass = 1;
2664                 goto again;
2665         }
2666
2667 out:
2668         btrfs_free_path(path);
2669         fs_path_free(sctx, fctx.cur_path);
2670         fs_path_free(sctx, fctx.dir_path);
2671         return ret;
2672 }
2673
2674 /*
2675  * This does all the move/link/unlink/rmdir magic.
2676  */
2677 static int process_recorded_refs(struct send_ctx *sctx)
2678 {
2679         int ret = 0;
2680         struct recorded_ref *cur;
2681         struct ulist *check_dirs = NULL;
2682         struct ulist_iterator uit;
2683         struct ulist_node *un;
2684         struct fs_path *valid_path = NULL;
2685         u64 ow_inode = 0;
2686         u64 ow_gen;
2687         int did_overwrite = 0;
2688         int is_orphan = 0;
2689
2690 verbose_printk("btrfs: process_recorded_refs %llu\n", sctx->cur_ino);
2691
2692         valid_path = fs_path_alloc(sctx);
2693         if (!valid_path) {
2694                 ret = -ENOMEM;
2695                 goto out;
2696         }
2697
2698         check_dirs = ulist_alloc(GFP_NOFS);
2699         if (!check_dirs) {
2700                 ret = -ENOMEM;
2701                 goto out;
2702         }
2703
2704         /*
2705          * First, check if the first ref of the current inode was overwritten
2706          * before. If yes, we know that the current inode was already orphanized
2707          * and thus use the orphan name. If not, we can use get_cur_path to
2708          * get the path of the first ref as it would like while receiving at
2709          * this point in time.
2710          * New inodes are always orphan at the beginning, so force to use the
2711          * orphan name in this case.
2712          * The first ref is stored in valid_path and will be updated if it
2713          * gets moved around.
2714          */
2715         if (!sctx->cur_inode_new) {
2716                 ret = did_overwrite_first_ref(sctx, sctx->cur_ino,
2717                                 sctx->cur_inode_gen);
2718                 if (ret < 0)
2719                         goto out;
2720                 if (ret)
2721                         did_overwrite = 1;
2722         }
2723         if (sctx->cur_inode_new || did_overwrite) {
2724                 ret = gen_unique_name(sctx, sctx->cur_ino,
2725                                 sctx->cur_inode_gen, valid_path);
2726                 if (ret < 0)
2727                         goto out;
2728                 is_orphan = 1;
2729         } else {
2730                 ret = get_cur_path(sctx, sctx->cur_ino, sctx->cur_inode_gen,
2731                                 valid_path);
2732                 if (ret < 0)
2733                         goto out;
2734         }
2735
2736         list_for_each_entry(cur, &sctx->new_refs, list) {
2737                 /*
2738                  * Check if this new ref would overwrite the first ref of
2739                  * another unprocessed inode. If yes, orphanize the
2740                  * overwritten inode. If we find an overwritten ref that is
2741                  * not the first ref, simply unlink it.
2742                  */
2743                 ret = will_overwrite_ref(sctx, cur->dir, cur->dir_gen,
2744                                 cur->name, cur->name_len,
2745                                 &ow_inode, &ow_gen);
2746                 if (ret < 0)
2747                         goto out;
2748                 if (ret) {
2749                         ret = is_first_ref(sctx, sctx->parent_root,
2750                                         ow_inode, cur->dir, cur->name,
2751                                         cur->name_len);
2752                         if (ret < 0)
2753                                 goto out;
2754                         if (ret) {
2755                                 ret = orphanize_inode(sctx, ow_inode, ow_gen,
2756                                                 cur->full_path);
2757                                 if (ret < 0)
2758                                         goto out;
2759                         } else {
2760                                 ret = send_unlink(sctx, cur->full_path);
2761                                 if (ret < 0)
2762                                         goto out;
2763                         }
2764                 }
2765
2766                 /*
2767                  * link/move the ref to the new place. If we have an orphan
2768                  * inode, move it and update valid_path. If not, link or move
2769                  * it depending on the inode mode.
2770                  */
2771                 if (is_orphan && !sctx->cur_inode_first_ref_orphan) {
2772                         ret = send_rename(sctx, valid_path, cur->full_path);
2773                         if (ret < 0)
2774                                 goto out;
2775                         is_orphan = 0;
2776                         ret = fs_path_copy(valid_path, cur->full_path);
2777                         if (ret < 0)
2778                                 goto out;
2779                 } else {
2780                         if (S_ISDIR(sctx->cur_inode_mode)) {
2781                                 /*
2782                                  * Dirs can't be linked, so move it. For moved
2783                                  * dirs, we always have one new and one deleted
2784                                  * ref. The deleted ref is ignored later.
2785                                  */
2786                                 ret = send_rename(sctx, valid_path,
2787                                                 cur->full_path);
2788                                 if (ret < 0)
2789                                         goto out;
2790                                 ret = fs_path_copy(valid_path, cur->full_path);
2791                                 if (ret < 0)
2792                                         goto out;
2793                         } else {
2794                                 ret = send_link(sctx, cur->full_path,
2795                                                 valid_path);
2796                                 if (ret < 0)
2797                                         goto out;
2798                         }
2799                 }
2800                 ret = ulist_add(check_dirs, cur->dir, cur->dir_gen,
2801                                 GFP_NOFS);
2802                 if (ret < 0)
2803                         goto out;
2804         }
2805
2806         if (S_ISDIR(sctx->cur_inode_mode) && sctx->cur_inode_deleted) {
2807                 /*
2808                  * Check if we can already rmdir the directory. If not,
2809                  * orphanize it. For every dir item inside that gets deleted
2810                  * later, we do this check again and rmdir it then if possible.
2811                  * See the use of check_dirs for more details.
2812                  */
2813                 ret = can_rmdir(sctx, sctx->cur_ino, sctx->cur_ino);
2814                 if (ret < 0)
2815                         goto out;
2816                 if (ret) {
2817                         ret = send_rmdir(sctx, valid_path);
2818                         if (ret < 0)
2819                                 goto out;
2820                 } else if (!is_orphan) {
2821                         ret = orphanize_inode(sctx, sctx->cur_ino,
2822                                         sctx->cur_inode_gen, valid_path);
2823                         if (ret < 0)
2824                                 goto out;
2825                         is_orphan = 1;
2826                 }
2827
2828                 list_for_each_entry(cur, &sctx->deleted_refs, list) {
2829                         ret = ulist_add(check_dirs, cur->dir, cur->dir_gen,
2830                                         GFP_NOFS);
2831                         if (ret < 0)
2832                                 goto out;
2833                 }
2834         } else if (!S_ISDIR(sctx->cur_inode_mode)) {
2835                 /*
2836                  * We have a non dir inode. Go through all deleted refs and
2837                  * unlink them if they were not already overwritten by other
2838                  * inodes.
2839                  */
2840                 list_for_each_entry(cur, &sctx->deleted_refs, list) {
2841                         ret = did_overwrite_ref(sctx, cur->dir, cur->dir_gen,
2842                                         sctx->cur_ino, sctx->cur_inode_gen,
2843                                         cur->name, cur->name_len);
2844                         if (ret < 0)
2845                                 goto out;
2846                         if (!ret) {
2847                                 /*
2848                                  * In case the inode was moved to a directory
2849                                  * that was not created yet (see
2850                                  * __record_new_ref), we can not unlink the ref
2851                                  * as it will be needed later when the parent
2852                                  * directory is created, so that we can move in
2853                                  * the inode to the new dir.
2854                                  */
2855                                 if (!is_orphan &&
2856                                     sctx->cur_inode_first_ref_orphan) {
2857                                         ret = orphanize_inode(sctx,
2858                                                         sctx->cur_ino,
2859                                                         sctx->cur_inode_gen,
2860                                                         cur->full_path);
2861                                         if (ret < 0)
2862                                                 goto out;
2863                                         ret = gen_unique_name(sctx,
2864                                                         sctx->cur_ino,
2865                                                         sctx->cur_inode_gen,
2866                                                         valid_path);
2867                                         if (ret < 0)
2868                                                 goto out;
2869                                         is_orphan = 1;
2870
2871                                 } else {
2872                                         ret = send_unlink(sctx, cur->full_path);
2873                                         if (ret < 0)
2874                                                 goto out;
2875                                 }
2876                         }
2877                         ret = ulist_add(check_dirs, cur->dir, cur->dir_gen,
2878                                         GFP_NOFS);
2879                         if (ret < 0)
2880                                 goto out;
2881                 }
2882
2883                 /*
2884                  * If the inode is still orphan, unlink the orphan. This may
2885                  * happen when a previous inode did overwrite the first ref
2886                  * of this inode and no new refs were added for the current
2887                  * inode.
2888                  * We can however not delete the orphan in case the inode relies
2889                  * in a directory that was not created yet (see
2890                  * __record_new_ref)
2891                  */
2892                 if (is_orphan && !sctx->cur_inode_first_ref_orphan) {
2893                         ret = send_unlink(sctx, valid_path);
2894                         if (ret < 0)
2895                                 goto out;
2896                 }
2897         }
2898
2899         /*
2900          * We did collect all parent dirs where cur_inode was once located. We
2901          * now go through all these dirs and check if they are pending for
2902          * deletion and if it's finally possible to perform the rmdir now.
2903          * We also update the inode stats of the parent dirs here.
2904          */
2905         ULIST_ITER_INIT(&uit);
2906         while ((un = ulist_next(check_dirs, &uit))) {
2907                 if (un->val > sctx->cur_ino)
2908                         continue;
2909
2910                 ret = get_cur_inode_state(sctx, un->val, un->aux);
2911                 if (ret < 0)
2912                         goto out;
2913
2914                 if (ret == inode_state_did_create ||
2915                     ret == inode_state_no_change) {
2916                         /* TODO delayed utimes */
2917                         ret = send_utimes(sctx, un->val, un->aux);
2918                         if (ret < 0)
2919                                 goto out;
2920                 } else if (ret == inode_state_did_delete) {
2921                         ret = can_rmdir(sctx, un->val, sctx->cur_ino);
2922                         if (ret < 0)
2923                                 goto out;
2924                         if (ret) {
2925                                 ret = get_cur_path(sctx, un->val, un->aux,
2926                                                 valid_path);
2927                                 if (ret < 0)
2928                                         goto out;
2929                                 ret = send_rmdir(sctx, valid_path);
2930                                 if (ret < 0)
2931                                         goto out;
2932                         }
2933                 }
2934         }
2935
2936         /*
2937          * Current inode is now at it's new position, so we must increase
2938          * send_progress
2939          */
2940         sctx->send_progress = sctx->cur_ino + 1;
2941
2942         /*
2943          * We may have a directory here that has pending refs which could not
2944          * be created before (because the dir did not exist before, see
2945          * __record_new_ref). finish_outoforder_dir will link/move the pending
2946          * refs.
2947          */
2948         if (S_ISDIR(sctx->cur_inode_mode) && sctx->cur_inode_new) {
2949                 ret = finish_outoforder_dir(sctx, sctx->cur_ino,
2950                                 sctx->cur_inode_gen);
2951                 if (ret < 0)
2952                         goto out;
2953         }
2954
2955         ret = 0;
2956
2957 out:
2958         free_recorded_refs(sctx);
2959         ulist_free(check_dirs);
2960         fs_path_free(sctx, valid_path);
2961         return ret;
2962 }
2963
2964 static int __record_new_ref(int num, u64 dir, int index,
2965                             struct fs_path *name,
2966                             void *ctx)
2967 {
2968         int ret = 0;
2969         struct send_ctx *sctx = ctx;
2970         struct fs_path *p;
2971         u64 gen;
2972
2973         p = fs_path_alloc(sctx);
2974         if (!p)
2975                 return -ENOMEM;
2976
2977         ret = get_inode_info(sctx->send_root, dir, NULL, &gen, NULL, NULL,
2978                         NULL, NULL);
2979         if (ret < 0)
2980                 goto out;
2981
2982         /*
2983          * The parent may be non-existent at this point in time. This happens
2984          * if the ino of the parent dir is higher then the current ino. In this
2985          * case, we can not process this ref until the parent dir is finally
2986          * created. If we reach the parent dir later, process_recorded_refs
2987          * will go through all dir items and process the refs that could not be
2988          * processed before. In case this is the first ref, we set
2989          * cur_inode_first_ref_orphan to 1 to inform process_recorded_refs to
2990          * keep an orphan of the inode so that it later can be used for
2991          * link/move
2992          */
2993         ret = is_inode_existent(sctx, dir, gen);
2994         if (ret < 0)
2995                 goto out;
2996         if (!ret) {
2997                 ret = is_first_ref(sctx, sctx->send_root, sctx->cur_ino, dir,
2998                                 name->start, fs_path_len(name));
2999                 if (ret < 0)
3000                         goto out;
3001                 if (ret)
3002                         sctx->cur_inode_first_ref_orphan = 1;
3003                 ret = 0;
3004                 goto out;
3005         }
3006
3007         ret = get_cur_path(sctx, dir, gen, p);
3008         if (ret < 0)
3009                 goto out;
3010         ret = fs_path_add_path(p, name);
3011         if (ret < 0)
3012                 goto out;
3013
3014         ret = record_ref(&sctx->new_refs, dir, gen, p);
3015
3016 out:
3017         if (ret)
3018                 fs_path_free(sctx, p);
3019         return ret;
3020 }
3021
3022 static int __record_deleted_ref(int num, u64 dir, int index,
3023                                 struct fs_path *name,
3024                                 void *ctx)
3025 {
3026         int ret = 0;
3027         struct send_ctx *sctx = ctx;
3028         struct fs_path *p;
3029         u64 gen;
3030
3031         p = fs_path_alloc(sctx);
3032         if (!p)
3033                 return -ENOMEM;
3034
3035         ret = get_inode_info(sctx->parent_root, dir, NULL, &gen, NULL, NULL,
3036                         NULL, NULL);
3037         if (ret < 0)
3038                 goto out;
3039
3040         ret = get_cur_path(sctx, dir, gen, p);
3041         if (ret < 0)
3042                 goto out;
3043         ret = fs_path_add_path(p, name);
3044         if (ret < 0)
3045                 goto out;
3046
3047         ret = record_ref(&sctx->deleted_refs, dir, gen, p);
3048
3049 out:
3050         if (ret)
3051                 fs_path_free(sctx, p);
3052         return ret;
3053 }
3054
3055 static int record_new_ref(struct send_ctx *sctx)
3056 {
3057         int ret;
3058
3059         ret = iterate_inode_ref(sctx, sctx->send_root, sctx->left_path,
3060                         sctx->cmp_key, 0, __record_new_ref, sctx);
3061         if (ret < 0)
3062                 goto out;
3063         ret = 0;
3064
3065 out:
3066         return ret;
3067 }
3068
3069 static int record_deleted_ref(struct send_ctx *sctx)
3070 {
3071         int ret;
3072
3073         ret = iterate_inode_ref(sctx, sctx->parent_root, sctx->right_path,
3074                         sctx->cmp_key, 0, __record_deleted_ref, sctx);
3075         if (ret < 0)
3076                 goto out;
3077         ret = 0;
3078
3079 out:
3080         return ret;
3081 }
3082
3083 struct find_ref_ctx {
3084         u64 dir;
3085         struct fs_path *name;
3086         int found_idx;
3087 };
3088
3089 static int __find_iref(int num, u64 dir, int index,
3090                        struct fs_path *name,
3091                        void *ctx_)
3092 {
3093         struct find_ref_ctx *ctx = ctx_;
3094
3095         if (dir == ctx->dir && fs_path_len(name) == fs_path_len(ctx->name) &&
3096             strncmp(name->start, ctx->name->start, fs_path_len(name)) == 0) {
3097                 ctx->found_idx = num;
3098                 return 1;
3099         }
3100         return 0;
3101 }
3102
3103 static int find_iref(struct send_ctx *sctx,
3104                      struct btrfs_root *root,
3105                      struct btrfs_path *path,
3106                      struct btrfs_key *key,
3107                      u64 dir, struct fs_path *name)
3108 {
3109         int ret;
3110         struct find_ref_ctx ctx;
3111
3112         ctx.dir = dir;
3113         ctx.name = name;
3114         ctx.found_idx = -1;
3115
3116         ret = iterate_inode_ref(sctx, root, path, key, 0, __find_iref, &ctx);
3117         if (ret < 0)
3118                 return ret;
3119
3120         if (ctx.found_idx == -1)
3121                 return -ENOENT;
3122
3123         return ctx.found_idx;
3124 }
3125
3126 static int __record_changed_new_ref(int num, u64 dir, int index,
3127                                     struct fs_path *name,
3128                                     void *ctx)
3129 {
3130         int ret;
3131         struct send_ctx *sctx = ctx;
3132
3133         ret = find_iref(sctx, sctx->parent_root, sctx->right_path,
3134                         sctx->cmp_key, dir, name);
3135         if (ret == -ENOENT)
3136                 ret = __record_new_ref(num, dir, index, name, sctx);
3137         else if (ret > 0)
3138                 ret = 0;
3139
3140         return ret;
3141 }
3142
3143 static int __record_changed_deleted_ref(int num, u64 dir, int index,
3144                                         struct fs_path *name,
3145                                         void *ctx)
3146 {
3147         int ret;
3148         struct send_ctx *sctx = ctx;
3149
3150         ret = find_iref(sctx, sctx->send_root, sctx->left_path, sctx->cmp_key,
3151                         dir, name);
3152         if (ret == -ENOENT)
3153                 ret = __record_deleted_ref(num, dir, index, name, sctx);
3154         else if (ret > 0)
3155                 ret = 0;
3156
3157         return ret;
3158 }
3159
3160 static int record_changed_ref(struct send_ctx *sctx)
3161 {
3162         int ret = 0;
3163
3164         ret = iterate_inode_ref(sctx, sctx->send_root, sctx->left_path,
3165                         sctx->cmp_key, 0, __record_changed_new_ref, sctx);
3166         if (ret < 0)
3167                 goto out;
3168         ret = iterate_inode_ref(sctx, sctx->parent_root, sctx->right_path,
3169                         sctx->cmp_key, 0, __record_changed_deleted_ref, sctx);
3170         if (ret < 0)
3171                 goto out;
3172         ret = 0;
3173
3174 out:
3175         return ret;
3176 }
3177
3178 /*
3179  * Record and process all refs at once. Needed when an inode changes the
3180  * generation number, which means that it was deleted and recreated.
3181  */
3182 static int process_all_refs(struct send_ctx *sctx,
3183                             enum btrfs_compare_tree_result cmd)
3184 {
3185         int ret;
3186         struct btrfs_root *root;
3187         struct btrfs_path *path;
3188         struct btrfs_key key;
3189         struct btrfs_key found_key;
3190         struct extent_buffer *eb;
3191         int slot;
3192         iterate_inode_ref_t cb;
3193
3194         path = alloc_path_for_send();
3195         if (!path)
3196                 return -ENOMEM;
3197
3198         if (cmd == BTRFS_COMPARE_TREE_NEW) {
3199                 root = sctx->send_root;
3200                 cb = __record_new_ref;
3201         } else if (cmd == BTRFS_COMPARE_TREE_DELETED) {
3202                 root = sctx->parent_root;
3203                 cb = __record_deleted_ref;
3204         } else {
3205                 BUG();
3206         }
3207
3208         key.objectid = sctx->cmp_key->objectid;
3209         key.type = BTRFS_INODE_REF_KEY;
3210         key.offset = 0;
3211         while (1) {
3212                 ret = btrfs_search_slot_for_read(root, &key, path, 1, 0);
3213                 if (ret < 0) {
3214                         btrfs_release_path(path);
3215                         goto out;
3216                 }
3217                 if (ret) {
3218                         btrfs_release_path(path);
3219                         break;
3220                 }
3221
3222                 eb = path->nodes[0];
3223                 slot = path->slots[0];
3224                 btrfs_item_key_to_cpu(eb, &found_key, slot);
3225
3226                 if (found_key.objectid != key.objectid ||
3227                     found_key.type != key.type) {
3228                         btrfs_release_path(path);
3229                         break;
3230                 }
3231
3232                 ret = iterate_inode_ref(sctx, sctx->parent_root, path,
3233                                 &found_key, 0, cb, sctx);
3234                 btrfs_release_path(path);
3235                 if (ret < 0)
3236                         goto out;
3237
3238                 key.offset = found_key.offset + 1;
3239         }
3240
3241         ret = process_recorded_refs(sctx);
3242
3243 out:
3244         btrfs_free_path(path);
3245         return ret;
3246 }
3247
3248 static int send_set_xattr(struct send_ctx *sctx,
3249                           struct fs_path *path,
3250                           const char *name, int name_len,
3251                           const char *data, int data_len)
3252 {
3253         int ret = 0;
3254
3255         ret = begin_cmd(sctx, BTRFS_SEND_C_SET_XATTR);
3256         if (ret < 0)
3257                 goto out;
3258
3259         TLV_PUT_PATH(sctx, BTRFS_SEND_A_PATH, path);
3260         TLV_PUT_STRING(sctx, BTRFS_SEND_A_XATTR_NAME, name, name_len);
3261         TLV_PUT(sctx, BTRFS_SEND_A_XATTR_DATA, data, data_len);
3262
3263         ret = send_cmd(sctx);
3264
3265 tlv_put_failure:
3266 out:
3267         return ret;
3268 }
3269
3270 static int send_remove_xattr(struct send_ctx *sctx,
3271                           struct fs_path *path,
3272                           const char *name, int name_len)
3273 {
3274         int ret = 0;
3275
3276         ret = begin_cmd(sctx, BTRFS_SEND_C_REMOVE_XATTR);
3277         if (ret < 0)
3278                 goto out;
3279
3280         TLV_PUT_PATH(sctx, BTRFS_SEND_A_PATH, path);
3281         TLV_PUT_STRING(sctx, BTRFS_SEND_A_XATTR_NAME, name, name_len);
3282
3283         ret = send_cmd(sctx);
3284
3285 tlv_put_failure:
3286 out:
3287         return ret;
3288 }
3289
3290 static int __process_new_xattr(int num, struct btrfs_key *di_key,
3291                                const char *name, int name_len,
3292                                const char *data, int data_len,
3293                                u8 type, void *ctx)
3294 {
3295         int ret;
3296         struct send_ctx *sctx = ctx;
3297         struct fs_path *p;
3298         posix_acl_xattr_header dummy_acl;
3299
3300         p = fs_path_alloc(sctx);
3301         if (!p)
3302                 return -ENOMEM;
3303
3304         /*
3305          * This hack is needed because empty acl's are stored as zero byte
3306          * data in xattrs. Problem with that is, that receiving these zero byte
3307          * acl's will fail later. To fix this, we send a dummy acl list that
3308          * only contains the version number and no entries.
3309          */
3310         if (!strncmp(name, XATTR_NAME_POSIX_ACL_ACCESS, name_len) ||
3311             !strncmp(name, XATTR_NAME_POSIX_ACL_DEFAULT, name_len)) {
3312                 if (data_len == 0) {
3313                         dummy_acl.a_version =
3314                                         cpu_to_le32(POSIX_ACL_XATTR_VERSION);
3315                         data = (char *)&dummy_acl;
3316                         data_len = sizeof(dummy_acl);
3317                 }
3318         }
3319
3320         ret = get_cur_path(sctx, sctx->cur_ino, sctx->cur_inode_gen, p);
3321         if (ret < 0)
3322                 goto out;
3323
3324         ret = send_set_xattr(sctx, p, name, name_len, data, data_len);
3325
3326 out:
3327         fs_path_free(sctx, p);
3328         return ret;
3329 }
3330
3331 static int __process_deleted_xattr(int num, struct btrfs_key *di_key,
3332                                    const char *name, int name_len,
3333                                    const char *data, int data_len,
3334                                    u8 type, void *ctx)
3335 {
3336         int ret;
3337         struct send_ctx *sctx = ctx;
3338         struct fs_path *p;
3339
3340         p = fs_path_alloc(sctx);
3341         if (!p)
3342                 return -ENOMEM;
3343
3344         ret = get_cur_path(sctx, sctx->cur_ino, sctx->cur_inode_gen, p);
3345         if (ret < 0)
3346                 goto out;
3347
3348         ret = send_remove_xattr(sctx, p, name, name_len);
3349
3350 out:
3351         fs_path_free(sctx, p);
3352         return ret;
3353 }
3354
3355 static int process_new_xattr(struct send_ctx *sctx)
3356 {
3357         int ret = 0;
3358
3359         ret = iterate_dir_item(sctx, sctx->send_root, sctx->left_path,
3360                         sctx->cmp_key, __process_new_xattr, sctx);
3361
3362         return ret;
3363 }
3364
3365 static int process_deleted_xattr(struct send_ctx *sctx)
3366 {
3367         int ret;
3368
3369         ret = iterate_dir_item(sctx, sctx->parent_root, sctx->right_path,
3370                         sctx->cmp_key, __process_deleted_xattr, sctx);
3371
3372         return ret;
3373 }
3374
3375 struct find_xattr_ctx {
3376         const char *name;
3377         int name_len;
3378         int found_idx;
3379         char *found_data;
3380         int found_data_len;
3381 };
3382
3383 static int __find_xattr(int num, struct btrfs_key *di_key,
3384                         const char *name, int name_len,
3385                         const char *data, int data_len,
3386                         u8 type, void *vctx)
3387 {
3388         struct find_xattr_ctx *ctx = vctx;
3389
3390         if (name_len == ctx->name_len &&
3391             strncmp(name, ctx->name, name_len) == 0) {
3392                 ctx->found_idx = num;
3393                 ctx->found_data_len = data_len;
3394                 ctx->found_data = kmalloc(data_len, GFP_NOFS);
3395                 if (!ctx->found_data)
3396                         return -ENOMEM;
3397                 memcpy(ctx->found_data, data, data_len);
3398                 return 1;
3399         }
3400         return 0;
3401 }
3402
3403 static int find_xattr(struct send_ctx *sctx,
3404                       struct btrfs_root *root,
3405                       struct btrfs_path *path,
3406                       struct btrfs_key *key,
3407                       const char *name, int name_len,
3408                       char **data, int *data_len)
3409 {
3410         int ret;
3411         struct find_xattr_ctx ctx;
3412
3413         ctx.name = name;
3414         ctx.name_len = name_len;
3415         ctx.found_idx = -1;
3416         ctx.found_data = NULL;
3417         ctx.found_data_len = 0;
3418
3419         ret = iterate_dir_item(sctx, root, path, key, __find_xattr, &ctx);
3420         if (ret < 0)
3421                 return ret;
3422
3423         if (ctx.found_idx == -1)
3424                 return -ENOENT;
3425         if (data) {
3426                 *data = ctx.found_data;
3427                 *data_len = ctx.found_data_len;
3428         } else {
3429                 kfree(ctx.found_data);
3430         }
3431         return ctx.found_idx;
3432 }
3433
3434
3435 static int __process_changed_new_xattr(int num, struct btrfs_key *di_key,
3436                                        const char *name, int name_len,
3437                                        const char *data, int data_len,
3438                                        u8 type, void *ctx)
3439 {
3440         int ret;
3441         struct send_ctx *sctx = ctx;
3442         char *found_data = NULL;
3443         int found_data_len  = 0;
3444         struct fs_path *p = NULL;
3445
3446         ret = find_xattr(sctx, sctx->parent_root, sctx->right_path,
3447                         sctx->cmp_key, name, name_len, &found_data,
3448                         &found_data_len);
3449         if (ret == -ENOENT) {
3450                 ret = __process_new_xattr(num, di_key, name, name_len, data,
3451                                 data_len, type, ctx);
3452         } else if (ret >= 0) {
3453                 if (data_len != found_data_len ||
3454                     memcmp(data, found_data, data_len)) {
3455                         ret = __process_new_xattr(num, di_key, name, name_len,
3456                                         data, data_len, type, ctx);
3457                 } else {
3458                         ret = 0;
3459                 }
3460         }
3461
3462         kfree(found_data);
3463         fs_path_free(sctx, p);
3464         return ret;
3465 }
3466
3467 static int __process_changed_deleted_xattr(int num, struct btrfs_key *di_key,
3468                                            const char *name, int name_len,
3469                                            const char *data, int data_len,
3470                                            u8 type, void *ctx)
3471 {
3472         int ret;
3473         struct send_ctx *sctx = ctx;
3474
3475         ret = find_xattr(sctx, sctx->send_root, sctx->left_path, sctx->cmp_key,
3476                         name, name_len, NULL, NULL);
3477         if (ret == -ENOENT)
3478                 ret = __process_deleted_xattr(num, di_key, name, name_len, data,
3479                                 data_len, type, ctx);
3480         else if (ret >= 0)
3481                 ret = 0;
3482
3483         return ret;
3484 }
3485
3486 static int process_changed_xattr(struct send_ctx *sctx)
3487 {
3488         int ret = 0;
3489
3490         ret = iterate_dir_item(sctx, sctx->send_root, sctx->left_path,
3491                         sctx->cmp_key, __process_changed_new_xattr, sctx);
3492         if (ret < 0)
3493                 goto out;
3494         ret = iterate_dir_item(sctx, sctx->parent_root, sctx->right_path,
3495                         sctx->cmp_key, __process_changed_deleted_xattr, sctx);
3496
3497 out:
3498         return ret;
3499 }
3500
3501 static int process_all_new_xattrs(struct send_ctx *sctx)
3502 {
3503         int ret;
3504         struct btrfs_root *root;
3505         struct btrfs_path *path;
3506         struct btrfs_key key;
3507         struct btrfs_key found_key;
3508         struct extent_buffer *eb;
3509         int slot;
3510
3511         path = alloc_path_for_send();
3512         if (!path)
3513                 return -ENOMEM;
3514
3515         root = sctx->send_root;
3516
3517         key.objectid = sctx->cmp_key->objectid;
3518         key.type = BTRFS_XATTR_ITEM_KEY;
3519         key.offset = 0;
3520         while (1) {
3521                 ret = btrfs_search_slot_for_read(root, &key, path, 1, 0);
3522                 if (ret < 0)
3523                         goto out;
3524                 if (ret) {
3525                         ret = 0;
3526                         goto out;
3527                 }
3528
3529                 eb = path->nodes[0];
3530                 slot = path->slots[0];
3531                 btrfs_item_key_to_cpu(eb, &found_key, slot);
3532
3533                 if (found_key.objectid != key.objectid ||
3534                     found_key.type != key.type) {
3535                         ret = 0;
3536                         goto out;
3537                 }
3538
3539                 ret = iterate_dir_item(sctx, root, path, &found_key,
3540                                 __process_new_xattr, sctx);
3541                 if (ret < 0)
3542                         goto out;
3543
3544                 btrfs_release_path(path);
3545                 key.offset = found_key.offset + 1;
3546         }
3547
3548 out:
3549         btrfs_free_path(path);
3550         return ret;
3551 }
3552
3553 /*
3554  * Read some bytes from the current inode/file and send a write command to
3555  * user space.
3556  */
3557 static int send_write(struct send_ctx *sctx, u64 offset, u32 len)
3558 {
3559         int ret = 0;
3560         struct fs_path *p;
3561         loff_t pos = offset;
3562         int readed = 0;
3563         mm_segment_t old_fs;
3564
3565         p = fs_path_alloc(sctx);
3566         if (!p)
3567                 return -ENOMEM;
3568
3569         /*
3570          * vfs normally only accepts user space buffers for security reasons.
3571          * we only read from the file and also only provide the read_buf buffer
3572          * to vfs. As this buffer does not come from a user space call, it's
3573          * ok to temporary allow kernel space buffers.
3574          */
3575         old_fs = get_fs();
3576         set_fs(KERNEL_DS);
3577
3578 verbose_printk("btrfs: send_write offset=%llu, len=%d\n", offset, len);
3579
3580         ret = open_cur_inode_file(sctx);
3581         if (ret < 0)
3582                 goto out;
3583
3584         ret = vfs_read(sctx->cur_inode_filp, sctx->read_buf, len, &pos);
3585         if (ret < 0)
3586                 goto out;
3587         readed = ret;
3588         if (!readed)
3589                 goto out;
3590
3591         ret = begin_cmd(sctx, BTRFS_SEND_C_WRITE);
3592         if (ret < 0)
3593                 goto out;
3594
3595         ret = get_cur_path(sctx, sctx->cur_ino, sctx->cur_inode_gen, p);
3596         if (ret < 0)
3597                 goto out;
3598
3599         TLV_PUT_PATH(sctx, BTRFS_SEND_A_PATH, p);
3600         TLV_PUT_U64(sctx, BTRFS_SEND_A_FILE_OFFSET, offset);
3601         TLV_PUT(sctx, BTRFS_SEND_A_DATA, sctx->read_buf, readed);
3602
3603         ret = send_cmd(sctx);
3604
3605 tlv_put_failure:
3606 out:
3607         fs_path_free(sctx, p);
3608         set_fs(old_fs);
3609         if (ret < 0)
3610                 return ret;
3611         return readed;
3612 }
3613
3614 /*
3615  * Send a clone command to user space.
3616  */
3617 static int send_clone(struct send_ctx *sctx,
3618                       u64 offset, u32 len,
3619                       struct clone_root *clone_root)
3620 {
3621         int ret = 0;
3622         struct btrfs_root *clone_root2 = clone_root->root;
3623         struct fs_path *p;
3624         u64 gen;
3625
3626 verbose_printk("btrfs: send_clone offset=%llu, len=%d, clone_root=%llu, "
3627                "clone_inode=%llu, clone_offset=%llu\n", offset, len,
3628                 clone_root->root->objectid, clone_root->ino,
3629                 clone_root->offset);
3630
3631         p = fs_path_alloc(sctx);
3632         if (!p)
3633                 return -ENOMEM;
3634
3635         ret = begin_cmd(sctx, BTRFS_SEND_C_CLONE);
3636         if (ret < 0)
3637                 goto out;
3638
3639         ret = get_cur_path(sctx, sctx->cur_ino, sctx->cur_inode_gen, p);
3640         if (ret < 0)
3641                 goto out;
3642
3643         TLV_PUT_U64(sctx, BTRFS_SEND_A_FILE_OFFSET, offset);
3644         TLV_PUT_U64(sctx, BTRFS_SEND_A_CLONE_LEN, len);
3645         TLV_PUT_PATH(sctx, BTRFS_SEND_A_PATH, p);
3646
3647         if (clone_root2 == sctx->send_root) {
3648                 ret = get_inode_info(sctx->send_root, clone_root->ino, NULL,
3649                                 &gen, NULL, NULL, NULL, NULL);
3650                 if (ret < 0)
3651                         goto out;
3652                 ret = get_cur_path(sctx, clone_root->ino, gen, p);
3653         } else {
3654                 ret = get_inode_path(sctx, clone_root2, clone_root->ino, p);
3655         }
3656         if (ret < 0)
3657                 goto out;
3658
3659         TLV_PUT_UUID(sctx, BTRFS_SEND_A_CLONE_UUID,
3660                         clone_root2->root_item.uuid);
3661         TLV_PUT_U64(sctx, BTRFS_SEND_A_CLONE_CTRANSID,
3662                         clone_root2->root_item.ctransid);
3663         TLV_PUT_PATH(sctx, BTRFS_SEND_A_CLONE_PATH, p);
3664         TLV_PUT_U64(sctx, BTRFS_SEND_A_CLONE_OFFSET,
3665                         clone_root->offset);
3666
3667         ret = send_cmd(sctx);
3668
3669 tlv_put_failure:
3670 out:
3671         fs_path_free(sctx, p);
3672         return ret;
3673 }
3674
3675 static int send_write_or_clone(struct send_ctx *sctx,
3676                                struct btrfs_path *path,
3677                                struct btrfs_key *key,
3678                                struct clone_root *clone_root)
3679 {
3680         int ret = 0;
3681         struct btrfs_file_extent_item *ei;
3682         u64 offset = key->offset;
3683         u64 pos = 0;
3684         u64 len;
3685         u32 l;
3686         u8 type;
3687
3688         ei = btrfs_item_ptr(path->nodes[0], path->slots[0],
3689                         struct btrfs_file_extent_item);
3690         type = btrfs_file_extent_type(path->nodes[0], ei);
3691         if (type == BTRFS_FILE_EXTENT_INLINE)
3692                 len = btrfs_file_extent_inline_len(path->nodes[0], ei);
3693         else
3694                 len = btrfs_file_extent_num_bytes(path->nodes[0], ei);
3695
3696         if (offset + len > sctx->cur_inode_size)
3697                 len = sctx->cur_inode_size - offset;
3698         if (len == 0) {
3699                 ret = 0;
3700                 goto out;
3701         }
3702
3703         if (!clone_root) {
3704                 while (pos < len) {
3705                         l = len - pos;
3706                         if (l > BTRFS_SEND_READ_SIZE)
3707                                 l = BTRFS_SEND_READ_SIZE;
3708                         ret = send_write(sctx, pos + offset, l);
3709                         if (ret < 0)
3710                                 goto out;
3711                         if (!ret)
3712                                 break;
3713                         pos += ret;
3714                 }
3715                 ret = 0;
3716         } else {
3717                 ret = send_clone(sctx, offset, len, clone_root);
3718         }
3719
3720 out:
3721         return ret;
3722 }
3723
3724 static int is_extent_unchanged(struct send_ctx *sctx,
3725                                struct btrfs_path *left_path,
3726                                struct btrfs_key *ekey)
3727 {
3728         int ret = 0;
3729         struct btrfs_key key;
3730         struct btrfs_path *path = NULL;
3731         struct extent_buffer *eb;
3732         int slot;
3733         struct btrfs_key found_key;
3734         struct btrfs_file_extent_item *ei;
3735         u64 left_disknr;
3736         u64 right_disknr;
3737         u64 left_offset;
3738         u64 right_offset;
3739         u64 left_offset_fixed;
3740         u64 left_len;
3741         u64 right_len;
3742         u8 left_type;
3743         u8 right_type;
3744
3745         path = alloc_path_for_send();
3746         if (!path)
3747                 return -ENOMEM;
3748
3749         eb = left_path->nodes[0];
3750         slot = left_path->slots[0];
3751
3752         ei = btrfs_item_ptr(eb, slot, struct btrfs_file_extent_item);
3753         left_type = btrfs_file_extent_type(eb, ei);
3754         left_disknr = btrfs_file_extent_disk_bytenr(eb, ei);
3755         left_len = btrfs_file_extent_num_bytes(eb, ei);
3756         left_offset = btrfs_file_extent_offset(eb, ei);
3757
3758         if (left_type != BTRFS_FILE_EXTENT_REG) {
3759                 ret = 0;
3760                 goto out;
3761         }
3762
3763         /*
3764          * Following comments will refer to these graphics. L is the left
3765          * extents which we are checking at the moment. 1-8 are the right
3766          * extents that we iterate.
3767          *
3768          *       |-----L-----|
3769          * |-1-|-2a-|-3-|-4-|-5-|-6-|
3770          *
3771          *       |-----L-----|
3772          * |--1--|-2b-|...(same as above)
3773          *
3774          * Alternative situation. Happens on files where extents got split.
3775          *       |-----L-----|
3776          * |-----------7-----------|-6-|
3777          *
3778          * Alternative situation. Happens on files which got larger.
3779          *       |-----L-----|
3780          * |-8-|
3781          * Nothing follows after 8.
3782          */
3783
3784         key.objectid = ekey->objectid;
3785         key.type = BTRFS_EXTENT_DATA_KEY;
3786         key.offset = ekey->offset;
3787         ret = btrfs_search_slot_for_read(sctx->parent_root, &key, path, 0, 0);
3788         if (ret < 0)
3789                 goto out;
3790         if (ret) {
3791                 ret = 0;
3792                 goto out;
3793         }
3794
3795         /*
3796          * Handle special case where the right side has no extents at all.
3797          */
3798         eb = path->nodes[0];
3799         slot = path->slots[0];
3800         btrfs_item_key_to_cpu(eb, &found_key, slot);
3801         if (found_key.objectid != key.objectid ||
3802             found_key.type != key.type) {
3803                 ret = 0;
3804                 goto out;
3805         }
3806
3807         /*
3808          * We're now on 2a, 2b or 7.
3809          */
3810         key = found_key;
3811         while (key.offset < ekey->offset + left_len) {
3812                 ei = btrfs_item_ptr(eb, slot, struct btrfs_file_extent_item);
3813                 right_type = btrfs_file_extent_type(eb, ei);
3814                 right_disknr = btrfs_file_extent_disk_bytenr(eb, ei);
3815                 right_len = btrfs_file_extent_num_bytes(eb, ei);
3816                 right_offset = btrfs_file_extent_offset(eb, ei);
3817
3818                 if (right_type != BTRFS_FILE_EXTENT_REG) {
3819                         ret = 0;
3820                         goto out;
3821                 }
3822
3823                 /*
3824                  * Are we at extent 8? If yes, we know the extent is changed.
3825                  * This may only happen on the first iteration.
3826                  */
3827                 if (found_key.offset + right_len < ekey->offset) {
3828                         ret = 0;
3829                         goto out;
3830                 }
3831
3832                 left_offset_fixed = left_offset;
3833                 if (key.offset < ekey->offset) {
3834                         /* Fix the right offset for 2a and 7. */
3835                         right_offset += ekey->offset - key.offset;
3836                 } else {
3837                         /* Fix the left offset for all behind 2a and 2b */
3838                         left_offset_fixed += key.offset - ekey->offset;
3839                 }
3840
3841                 /*
3842                  * Check if we have the same extent.
3843                  */
3844                 if (left_disknr + left_offset_fixed !=
3845                                 right_disknr + right_offset) {
3846                         ret = 0;
3847                         goto out;
3848                 }
3849
3850                 /*
3851                  * Go to the next extent.
3852                  */
3853                 ret = btrfs_next_item(sctx->parent_root, path);
3854                 if (ret < 0)
3855                         goto out;
3856                 if (!ret) {
3857                         eb = path->nodes[0];
3858                         slot = path->slots[0];
3859                         btrfs_item_key_to_cpu(eb, &found_key, slot);
3860                 }
3861                 if (ret || found_key.objectid != key.objectid ||
3862                     found_key.type != key.type) {
3863                         key.offset += right_len;
3864                         break;
3865                 } else {
3866                         if (found_key.offset != key.offset + right_len) {
3867                                 /* Should really not happen */
3868                                 ret = -EIO;
3869                                 goto out;
3870                         }
3871                 }
3872                 key = found_key;
3873         }
3874
3875         /*
3876          * We're now behind the left extent (treat as unchanged) or at the end
3877          * of the right side (treat as changed).
3878          */
3879         if (key.offset >= ekey->offset + left_len)
3880                 ret = 1;
3881         else
3882                 ret = 0;
3883
3884
3885 out:
3886         btrfs_free_path(path);
3887         return ret;
3888 }
3889
3890 static int process_extent(struct send_ctx *sctx,
3891                           struct btrfs_path *path,
3892                           struct btrfs_key *key)
3893 {
3894         int ret = 0;
3895         struct clone_root *found_clone = NULL;
3896
3897         if (S_ISLNK(sctx->cur_inode_mode))
3898                 return 0;
3899
3900         if (sctx->parent_root && !sctx->cur_inode_new) {
3901                 ret = is_extent_unchanged(sctx, path, key);
3902                 if (ret < 0)
3903                         goto out;
3904                 if (ret) {
3905                         ret = 0;
3906                         goto out;
3907                 }
3908         }
3909
3910         ret = find_extent_clone(sctx, path, key->objectid, key->offset,
3911                         sctx->cur_inode_size, &found_clone);
3912         if (ret != -ENOENT && ret < 0)
3913                 goto out;
3914
3915         ret = send_write_or_clone(sctx, path, key, found_clone);
3916
3917 out:
3918         return ret;
3919 }
3920
3921 static int process_all_extents(struct send_ctx *sctx)
3922 {
3923         int ret;
3924         struct btrfs_root *root;
3925         struct btrfs_path *path;
3926         struct btrfs_key key;
3927         struct btrfs_key found_key;
3928         struct extent_buffer *eb;
3929         int slot;
3930
3931         root = sctx->send_root;
3932         path = alloc_path_for_send();
3933         if (!path)
3934                 return -ENOMEM;
3935
3936         key.objectid = sctx->cmp_key->objectid;
3937         key.type = BTRFS_EXTENT_DATA_KEY;
3938         key.offset = 0;
3939         while (1) {
3940                 ret = btrfs_search_slot_for_read(root, &key, path, 1, 0);
3941                 if (ret < 0)
3942                         goto out;
3943                 if (ret) {
3944                         ret = 0;
3945                         goto out;
3946                 }
3947
3948                 eb = path->nodes[0];
3949                 slot = path->slots[0];
3950                 btrfs_item_key_to_cpu(eb, &found_key, slot);
3951
3952                 if (found_key.objectid != key.objectid ||
3953                     found_key.type != key.type) {
3954                         ret = 0;
3955                         goto out;
3956                 }
3957
3958                 ret = process_extent(sctx, path, &found_key);
3959                 if (ret < 0)
3960                         goto out;
3961
3962                 btrfs_release_path(path);
3963                 key.offset = found_key.offset + 1;
3964         }
3965
3966 out:
3967         btrfs_free_path(path);
3968         return ret;
3969 }
3970
3971 static int process_recorded_refs_if_needed(struct send_ctx *sctx, int at_end)
3972 {
3973         int ret = 0;
3974
3975         if (sctx->cur_ino == 0)
3976                 goto out;
3977         if (!at_end && sctx->cur_ino == sctx->cmp_key->objectid &&
3978             sctx->cmp_key->type <= BTRFS_INODE_REF_KEY)
3979                 goto out;
3980         if (list_empty(&sctx->new_refs) && list_empty(&sctx->deleted_refs))
3981                 goto out;
3982
3983         ret = process_recorded_refs(sctx);
3984
3985 out:
3986         return ret;
3987 }
3988
3989 static int finish_inode_if_needed(struct send_ctx *sctx, int at_end)
3990 {
3991         int ret = 0;
3992         u64 left_mode;
3993         u64 left_uid;
3994         u64 left_gid;
3995         u64 right_mode;
3996         u64 right_uid;
3997         u64 right_gid;
3998         int need_chmod = 0;
3999         int need_chown = 0;
4000
4001         ret = process_recorded_refs_if_needed(sctx, at_end);
4002         if (ret < 0)
4003                 goto out;
4004
4005         if (sctx->cur_ino == 0 || sctx->cur_inode_deleted)
4006                 goto out;
4007         if (!at_end && sctx->cmp_key->objectid == sctx->cur_ino)
4008                 goto out;
4009
4010         ret = get_inode_info(sctx->send_root, sctx->cur_ino, NULL, NULL,
4011                         &left_mode, &left_uid, &left_gid, NULL);
4012         if (ret < 0)
4013                 goto out;
4014
4015         if (!S_ISLNK(sctx->cur_inode_mode)) {
4016                 if (!sctx->parent_root || sctx->cur_inode_new) {
4017                         need_chmod = 1;
4018                         need_chown = 1;
4019                 } else {
4020                         ret = get_inode_info(sctx->parent_root, sctx->cur_ino,
4021                                         NULL, NULL, &right_mode, &right_uid,
4022                                         &right_gid, NULL);
4023                         if (ret < 0)
4024                                 goto out;
4025
4026                         if (left_uid != right_uid || left_gid != right_gid)
4027                                 need_chown = 1;
4028                         if (left_mode != right_mode)
4029                                 need_chmod = 1;
4030                 }
4031         }
4032
4033         if (S_ISREG(sctx->cur_inode_mode)) {
4034                 ret = send_truncate(sctx, sctx->cur_ino, sctx->cur_inode_gen,
4035                                 sctx->cur_inode_size);
4036                 if (ret < 0)
4037                         goto out;
4038         }
4039
4040         if (need_chown) {
4041                 ret = send_chown(sctx, sctx->cur_ino, sctx->cur_inode_gen,
4042                                 left_uid, left_gid);
4043                 if (ret < 0)
4044                         goto out;
4045         }
4046         if (need_chmod) {
4047                 ret = send_chmod(sctx, sctx->cur_ino, sctx->cur_inode_gen,
4048                                 left_mode);
4049                 if (ret < 0)
4050                         goto out;
4051         }
4052
4053         /*
4054          * Need to send that every time, no matter if it actually changed
4055          * between the two trees as we have done changes to the inode before.
4056          */
4057         ret = send_utimes(sctx, sctx->cur_ino, sctx->cur_inode_gen);
4058         if (ret < 0)
4059                 goto out;
4060
4061 out:
4062         return ret;
4063 }
4064
4065 static int changed_inode(struct send_ctx *sctx,
4066                          enum btrfs_compare_tree_result result)
4067 {
4068         int ret = 0;
4069         struct btrfs_key *key = sctx->cmp_key;
4070         struct btrfs_inode_item *left_ii = NULL;
4071         struct btrfs_inode_item *right_ii = NULL;
4072         u64 left_gen = 0;
4073         u64 right_gen = 0;
4074
4075         ret = close_cur_inode_file(sctx);
4076         if (ret < 0)
4077                 goto out;
4078
4079         sctx->cur_ino = key->objectid;
4080         sctx->cur_inode_new_gen = 0;
4081         sctx->cur_inode_first_ref_orphan = 0;
4082         sctx->send_progress = sctx->cur_ino;
4083
4084         if (result == BTRFS_COMPARE_TREE_NEW ||
4085             result == BTRFS_COMPARE_TREE_CHANGED) {
4086                 left_ii = btrfs_item_ptr(sctx->left_path->nodes[0],
4087                                 sctx->left_path->slots[0],
4088                                 struct btrfs_inode_item);
4089                 left_gen = btrfs_inode_generation(sctx->left_path->nodes[0],
4090                                 left_ii);
4091         } else {
4092                 right_ii = btrfs_item_ptr(sctx->right_path->nodes[0],
4093                                 sctx->right_path->slots[0],
4094                                 struct btrfs_inode_item);
4095                 right_gen = btrfs_inode_generation(sctx->right_path->nodes[0],
4096                                 right_ii);
4097         }
4098         if (result == BTRFS_COMPARE_TREE_CHANGED) {
4099                 right_ii = btrfs_item_ptr(sctx->right_path->nodes[0],
4100                                 sctx->right_path->slots[0],
4101                                 struct btrfs_inode_item);
4102
4103                 right_gen = btrfs_inode_generation(sctx->right_path->nodes[0],
4104                                 right_ii);
4105                 if (left_gen != right_gen)
4106                         sctx->cur_inode_new_gen = 1;
4107         }
4108
4109         if (result == BTRFS_COMPARE_TREE_NEW) {
4110                 sctx->cur_inode_gen = left_gen;
4111                 sctx->cur_inode_new = 1;
4112                 sctx->cur_inode_deleted = 0;
4113                 sctx->cur_inode_size = btrfs_inode_size(
4114                                 sctx->left_path->nodes[0], left_ii);
4115                 sctx->cur_inode_mode = btrfs_inode_mode(
4116                                 sctx->left_path->nodes[0], left_ii);
4117                 if (sctx->cur_ino != BTRFS_FIRST_FREE_OBJECTID)
4118                         ret = send_create_inode(sctx, sctx->left_path,
4119                                         sctx->cmp_key);
4120         } else if (result == BTRFS_COMPARE_TREE_DELETED) {
4121                 sctx->cur_inode_gen = right_gen;
4122                 sctx->cur_inode_new = 0;
4123                 sctx->cur_inode_deleted = 1;
4124                 sctx->cur_inode_size = btrfs_inode_size(
4125                                 sctx->right_path->nodes[0], right_ii);
4126                 sctx->cur_inode_mode = btrfs_inode_mode(
4127                                 sctx->right_path->nodes[0], right_ii);
4128         } else if (result == BTRFS_COMPARE_TREE_CHANGED) {
4129                 if (sctx->cur_inode_new_gen) {
4130                         sctx->cur_inode_gen = right_gen;
4131                         sctx->cur_inode_new = 0;
4132                         sctx->cur_inode_deleted = 1;
4133                         sctx->cur_inode_size = btrfs_inode_size(
4134                                         sctx->right_path->nodes[0], right_ii);
4135                         sctx->cur_inode_mode = btrfs_inode_mode(
4136                                         sctx->right_path->nodes[0], right_ii);
4137                         ret = process_all_refs(sctx,
4138                                         BTRFS_COMPARE_TREE_DELETED);
4139                         if (ret < 0)
4140                                 goto out;
4141
4142                         sctx->cur_inode_gen = left_gen;
4143                         sctx->cur_inode_new = 1;
4144                         sctx->cur_inode_deleted = 0;
4145                         sctx->cur_inode_size = btrfs_inode_size(
4146                                         sctx->left_path->nodes[0], left_ii);
4147                         sctx->cur_inode_mode = btrfs_inode_mode(
4148                                         sctx->left_path->nodes[0], left_ii);
4149                         ret = send_create_inode(sctx, sctx->left_path,
4150                                         sctx->cmp_key);
4151                         if (ret < 0)
4152                                 goto out;
4153
4154                         ret = process_all_refs(sctx, BTRFS_COMPARE_TREE_NEW);
4155                         if (ret < 0)
4156                                 goto out;
4157                         ret = process_all_extents(sctx);
4158                         if (ret < 0)
4159                                 goto out;
4160                         ret = process_all_new_xattrs(sctx);
4161                         if (ret < 0)
4162                                 goto out;
4163                 } else {
4164                         sctx->cur_inode_gen = left_gen;
4165                         sctx->cur_inode_new = 0;
4166                         sctx->cur_inode_new_gen = 0;
4167                         sctx->cur_inode_deleted = 0;
4168                         sctx->cur_inode_size = btrfs_inode_size(
4169                                         sctx->left_path->nodes[0], left_ii);
4170                         sctx->cur_inode_mode = btrfs_inode_mode(
4171                                         sctx->left_path->nodes[0], left_ii);
4172                 }
4173         }
4174
4175 out:
4176         return ret;
4177 }
4178
4179 static int changed_ref(struct send_ctx *sctx,
4180                        enum btrfs_compare_tree_result result)
4181 {
4182         int ret = 0;
4183
4184         BUG_ON(sctx->cur_ino != sctx->cmp_key->objectid);
4185
4186         if (!sctx->cur_inode_new_gen &&
4187             sctx->cur_ino != BTRFS_FIRST_FREE_OBJECTID) {
4188                 if (result == BTRFS_COMPARE_TREE_NEW)
4189                         ret = record_new_ref(sctx);
4190                 else if (result == BTRFS_COMPARE_TREE_DELETED)
4191                         ret = record_deleted_ref(sctx);
4192                 else if (result == BTRFS_COMPARE_TREE_CHANGED)
4193                         ret = record_changed_ref(sctx);
4194         }
4195
4196         return ret;
4197 }
4198
4199 static int changed_xattr(struct send_ctx *sctx,
4200                          enum btrfs_compare_tree_result result)
4201 {
4202         int ret = 0;
4203
4204         BUG_ON(sctx->cur_ino != sctx->cmp_key->objectid);
4205
4206         if (!sctx->cur_inode_new_gen && !sctx->cur_inode_deleted) {
4207                 if (result == BTRFS_COMPARE_TREE_NEW)
4208                         ret = process_new_xattr(sctx);
4209                 else if (result == BTRFS_COMPARE_TREE_DELETED)
4210                         ret = process_deleted_xattr(sctx);
4211                 else if (result == BTRFS_COMPARE_TREE_CHANGED)
4212                         ret = process_changed_xattr(sctx);
4213         }
4214
4215         return ret;
4216 }
4217
4218 static int changed_extent(struct send_ctx *sctx,
4219                           enum btrfs_compare_tree_result result)
4220 {
4221         int ret = 0;
4222
4223         BUG_ON(sctx->cur_ino != sctx->cmp_key->objectid);
4224
4225         if (!sctx->cur_inode_new_gen && !sctx->cur_inode_deleted) {
4226                 if (result != BTRFS_COMPARE_TREE_DELETED)
4227                         ret = process_extent(sctx, sctx->left_path,
4228                                         sctx->cmp_key);
4229         }
4230
4231         return ret;
4232 }
4233
4234
4235 static int changed_cb(struct btrfs_root *left_root,
4236                       struct btrfs_root *right_root,
4237                       struct btrfs_path *left_path,
4238                       struct btrfs_path *right_path,
4239                       struct btrfs_key *key,
4240                       enum btrfs_compare_tree_result result,
4241                       void *ctx)
4242 {
4243         int ret = 0;
4244         struct send_ctx *sctx = ctx;
4245
4246         sctx->left_path = left_path;
4247         sctx->right_path = right_path;
4248         sctx->cmp_key = key;
4249
4250         ret = finish_inode_if_needed(sctx, 0);
4251         if (ret < 0)
4252                 goto out;
4253
4254         if (key->type == BTRFS_INODE_ITEM_KEY)
4255                 ret = changed_inode(sctx, result);
4256         else if (key->type == BTRFS_INODE_REF_KEY)
4257                 ret = changed_ref(sctx, result);
4258         else if (key->type == BTRFS_XATTR_ITEM_KEY)
4259                 ret = changed_xattr(sctx, result);
4260         else if (key->type == BTRFS_EXTENT_DATA_KEY)
4261                 ret = changed_extent(sctx, result);
4262
4263 out:
4264         return ret;
4265 }
4266
4267 static int full_send_tree(struct send_ctx *sctx)
4268 {
4269         int ret;
4270         struct btrfs_trans_handle *trans = NULL;
4271         struct btrfs_root *send_root = sctx->send_root;
4272         struct btrfs_key key;
4273         struct btrfs_key found_key;
4274         struct btrfs_path *path;
4275         struct extent_buffer *eb;
4276         int slot;
4277         u64 start_ctransid;
4278         u64 ctransid;
4279
4280         path = alloc_path_for_send();
4281         if (!path)
4282                 return -ENOMEM;
4283
4284         spin_lock(&send_root->root_times_lock);
4285         start_ctransid = btrfs_root_ctransid(&send_root->root_item);
4286         spin_unlock(&send_root->root_times_lock);
4287
4288         key.objectid = BTRFS_FIRST_FREE_OBJECTID;
4289         key.type = BTRFS_INODE_ITEM_KEY;
4290         key.offset = 0;
4291
4292 join_trans:
4293         /*
4294          * We need to make sure the transaction does not get committed
4295          * while we do anything on commit roots. Join a transaction to prevent
4296          * this.
4297          */
4298         trans = btrfs_join_transaction(send_root);
4299         if (IS_ERR(trans)) {
4300                 ret = PTR_ERR(trans);
4301                 trans = NULL;
4302                 goto out;
4303         }
4304
4305         /*
4306          * Make sure the tree has not changed
4307          */
4308         spin_lock(&send_root->root_times_lock);
4309         ctransid = btrfs_root_ctransid(&send_root->root_item);
4310         spin_unlock(&send_root->root_times_lock);
4311
4312         if (ctransid != start_ctransid) {
4313                 WARN(1, KERN_WARNING "btrfs: the root that you're trying to "
4314                                      "send was modified in between. This is "
4315                                      "probably a bug.\n");
4316                 ret = -EIO;
4317                 goto out;
4318         }
4319
4320         ret = btrfs_search_slot_for_read(send_root, &key, path, 1, 0);
4321         if (ret < 0)
4322                 goto out;
4323         if (ret)
4324                 goto out_finish;
4325
4326         while (1) {
4327                 /*
4328                  * When someone want to commit while we iterate, end the
4329                  * joined transaction and rejoin.
4330                  */
4331                 if (btrfs_should_end_transaction(trans, send_root)) {
4332                         ret = btrfs_end_transaction(trans, send_root);
4333                         trans = NULL;
4334                         if (ret < 0)
4335                                 goto out;
4336                         btrfs_release_path(path);
4337                         goto join_trans;
4338                 }
4339
4340                 eb = path->nodes[0];
4341                 slot = path->slots[0];
4342                 btrfs_item_key_to_cpu(eb, &found_key, slot);
4343
4344                 ret = changed_cb(send_root, NULL, path, NULL,
4345                                 &found_key, BTRFS_COMPARE_TREE_NEW, sctx);
4346                 if (ret < 0)
4347                         goto out;
4348
4349                 key.objectid = found_key.objectid;
4350                 key.type = found_key.type;
4351                 key.offset = found_key.offset + 1;
4352
4353                 ret = btrfs_next_item(send_root, path);
4354                 if (ret < 0)
4355                         goto out;
4356                 if (ret) {
4357                         ret  = 0;
4358                         break;
4359                 }
4360         }
4361
4362 out_finish:
4363         ret = finish_inode_if_needed(sctx, 1);
4364
4365 out:
4366         btrfs_free_path(path);
4367         if (trans) {
4368                 if (!ret)
4369                         ret = btrfs_end_transaction(trans, send_root);
4370                 else
4371                         btrfs_end_transaction(trans, send_root);
4372         }
4373         return ret;
4374 }
4375
4376 static int send_subvol(struct send_ctx *sctx)
4377 {
4378         int ret;
4379
4380         ret = send_header(sctx);
4381         if (ret < 0)
4382                 goto out;
4383
4384         ret = send_subvol_begin(sctx);
4385         if (ret < 0)
4386                 goto out;
4387
4388         if (sctx->parent_root) {
4389                 ret = btrfs_compare_trees(sctx->send_root, sctx->parent_root,
4390                                 changed_cb, sctx);
4391                 if (ret < 0)
4392                         goto out;
4393                 ret = finish_inode_if_needed(sctx, 1);
4394                 if (ret < 0)
4395                         goto out;
4396         } else {
4397                 ret = full_send_tree(sctx);
4398                 if (ret < 0)
4399                         goto out;
4400         }
4401
4402 out:
4403         if (!ret)
4404                 ret = close_cur_inode_file(sctx);
4405         else
4406                 close_cur_inode_file(sctx);
4407
4408         free_recorded_refs(sctx);
4409         return ret;
4410 }
4411
4412 long btrfs_ioctl_send(struct file *mnt_file, void __user *arg_)
4413 {
4414         int ret = 0;
4415         struct btrfs_root *send_root;
4416         struct btrfs_root *clone_root;
4417         struct btrfs_fs_info *fs_info;
4418         struct btrfs_ioctl_send_args *arg = NULL;
4419         struct btrfs_key key;
4420         struct file *filp = NULL;
4421         struct send_ctx *sctx = NULL;
4422         u32 i;
4423         u64 *clone_sources_tmp = NULL;
4424
4425         if (!capable(CAP_SYS_ADMIN))
4426                 return -EPERM;
4427
4428         send_root = BTRFS_I(fdentry(mnt_file)->d_inode)->root;
4429         fs_info = send_root->fs_info;
4430
4431         arg = memdup_user(arg_, sizeof(*arg));
4432         if (IS_ERR(arg)) {
4433                 ret = PTR_ERR(arg);
4434                 arg = NULL;
4435                 goto out;
4436         }
4437
4438         if (!access_ok(VERIFY_READ, arg->clone_sources,
4439                         sizeof(*arg->clone_sources *
4440                         arg->clone_sources_count))) {
4441                 ret = -EFAULT;
4442                 goto out;
4443         }
4444
4445         sctx = kzalloc(sizeof(struct send_ctx), GFP_NOFS);
4446         if (!sctx) {
4447                 ret = -ENOMEM;
4448                 goto out;
4449         }
4450
4451         INIT_LIST_HEAD(&sctx->new_refs);
4452         INIT_LIST_HEAD(&sctx->deleted_refs);
4453         INIT_RADIX_TREE(&sctx->name_cache, GFP_NOFS);
4454         INIT_LIST_HEAD(&sctx->name_cache_list);
4455
4456         sctx->send_filp = fget(arg->send_fd);
4457         if (IS_ERR(sctx->send_filp)) {
4458                 ret = PTR_ERR(sctx->send_filp);
4459                 goto out;
4460         }
4461
4462         sctx->mnt = mnt_file->f_path.mnt;
4463
4464         sctx->send_root = send_root;
4465         sctx->clone_roots_cnt = arg->clone_sources_count;
4466
4467         sctx->send_max_size = BTRFS_SEND_BUF_SIZE;
4468         sctx->send_buf = vmalloc(sctx->send_max_size);
4469         if (!sctx->send_buf) {
4470                 ret = -ENOMEM;
4471                 goto out;
4472         }
4473
4474         sctx->read_buf = vmalloc(BTRFS_SEND_READ_SIZE);
4475         if (!sctx->read_buf) {
4476                 ret = -ENOMEM;
4477                 goto out;
4478         }
4479
4480         sctx->clone_roots = vzalloc(sizeof(struct clone_root) *
4481                         (arg->clone_sources_count + 1));
4482         if (!sctx->clone_roots) {
4483                 ret = -ENOMEM;
4484                 goto out;
4485         }
4486
4487         if (arg->clone_sources_count) {
4488                 clone_sources_tmp = vmalloc(arg->clone_sources_count *
4489                                 sizeof(*arg->clone_sources));
4490                 if (!clone_sources_tmp) {
4491                         ret = -ENOMEM;
4492                         goto out;
4493                 }
4494
4495                 ret = copy_from_user(clone_sources_tmp, arg->clone_sources,
4496                                 arg->clone_sources_count *
4497                                 sizeof(*arg->clone_sources));
4498                 if (ret) {
4499                         ret = -EFAULT;
4500                         goto out;
4501                 }
4502
4503                 for (i = 0; i < arg->clone_sources_count; i++) {
4504                         key.objectid = clone_sources_tmp[i];
4505                         key.type = BTRFS_ROOT_ITEM_KEY;
4506                         key.offset = (u64)-1;
4507                         clone_root = btrfs_read_fs_root_no_name(fs_info, &key);
4508                         if (!clone_root) {
4509                                 ret = -EINVAL;
4510                                 goto out;
4511                         }
4512                         if (IS_ERR(clone_root)) {
4513                                 ret = PTR_ERR(clone_root);
4514                                 goto out;
4515                         }
4516                         sctx->clone_roots[i].root = clone_root;
4517                 }
4518                 vfree(clone_sources_tmp);
4519                 clone_sources_tmp = NULL;
4520         }
4521
4522         if (arg->parent_root) {
4523                 key.objectid = arg->parent_root;
4524                 key.type = BTRFS_ROOT_ITEM_KEY;
4525                 key.offset = (u64)-1;
4526                 sctx->parent_root = btrfs_read_fs_root_no_name(fs_info, &key);
4527                 if (!sctx->parent_root) {
4528                         ret = -EINVAL;
4529                         goto out;
4530                 }
4531         }
4532
4533         /*
4534          * Clones from send_root are allowed, but only if the clone source
4535          * is behind the current send position. This is checked while searching
4536          * for possible clone sources.
4537          */
4538         sctx->clone_roots[sctx->clone_roots_cnt++].root = sctx->send_root;
4539
4540         /* We do a bsearch later */
4541         sort(sctx->clone_roots, sctx->clone_roots_cnt,
4542                         sizeof(*sctx->clone_roots), __clone_root_cmp_sort,
4543                         NULL);
4544
4545         ret = send_subvol(sctx);
4546         if (ret < 0)
4547                 goto out;
4548
4549         ret = begin_cmd(sctx, BTRFS_SEND_C_END);
4550         if (ret < 0)
4551                 goto out;
4552         ret = send_cmd(sctx);
4553         if (ret < 0)
4554                 goto out;
4555
4556 out:
4557         if (filp)
4558                 fput(filp);
4559         kfree(arg);
4560         vfree(clone_sources_tmp);
4561
4562         if (sctx) {
4563                 if (sctx->send_filp)
4564                         fput(sctx->send_filp);
4565
4566                 vfree(sctx->clone_roots);
4567                 vfree(sctx->send_buf);
4568                 vfree(sctx->read_buf);
4569
4570                 name_cache_free(sctx);
4571
4572                 kfree(sctx);
4573         }
4574
4575         return ret;
4576 }