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/vmalloc.h>
  28 #include <linux/string.h>
  29
  30 #include "send.h"
  31 #include "backref.h"
  32 #include "hash.h"
  33 #include "locking.h"
  34 #include "disk-io.h"
  35 #include "btrfs_inode.h"
  36 #include "transaction.h"
  37
  38 static int g_verbose = 0;
  39
  40 #define verbose_printk(...) if (g_verbose) printk(__VA_ARGS__)
  41
  42 /*
  43  * A fs_path is a helper to dynamically build path names with unknown size.
  44  * It reallocates the internal buffer on demand.
  45  * It allows fast adding of path elements on the right side (normal path) and
  46  * fast adding to the left side (reversed path). A reversed path can also be
  47  * unreversed if needed.
  48  */
  49 struct fs_path {
  50         union {
  51                 struct {
  52                         char *start;
  53                         char *end;
  54
  55                         char *buf;
  56                         unsigned short buf_len:15;
  57                         unsigned short reversed:1;
  58                         char inline_buf[];
  59                 };
  60                 /*
  61                  * Average path length does not exceed 200 bytes, we'll have
  62                  * better packing in the slab and higher chance to satisfy
  63                  * a allocation later during send.
  64                  */
  65                 char pad[256];
  66         };
  67 };
  68 #define FS_PATH_INLINE_SIZE \
  69         (sizeof(struct fs_path) - offsetof(struct fs_path, inline_buf))
  70
  71
  72 /* reused for each extent */
  73 struct clone_root {
  74         struct btrfs_root *root;
  75         u64 ino;
  76         u64 offset;
  77
  78         u64 found_refs;
  79 };
  80
  81 #define SEND_CTX_MAX_NAME_CACHE_SIZE 128
  82 #define SEND_CTX_NAME_CACHE_CLEAN_SIZE (SEND_CTX_MAX_NAME_CACHE_SIZE * 2)
  83
  84 struct send_ctx {
  85         struct file *send_filp;
  86         loff_t send_off;
  87         char *send_buf;
  88         u32 send_size;
  89         u32 send_max_size;
  90         u64 total_send_size;
  91         u64 cmd_send_size[BTRFS_SEND_C_MAX + 1];
  92         u64 flags;      /* 'flags' member of btrfs_ioctl_send_args is u64 */
  93
  94         struct btrfs_root *send_root;
  95         struct btrfs_root *parent_root;
  96         struct clone_root *clone_roots;
  97         int clone_roots_cnt;
  98
  99         /* current state of the compare_tree call */
 100         struct btrfs_path *left_path;
 101         struct btrfs_path *right_path;
 102         struct btrfs_key *cmp_key;
 103
 104         /*
 105          * infos of the currently processed inode. In case of deleted inodes,
 106          * these are the values from the deleted inode.
 107          */
 108         u64 cur_ino;
 109         u64 cur_inode_gen;
 110         int cur_inode_new;
 111         int cur_inode_new_gen;
 112         int cur_inode_deleted;
 113         u64 cur_inode_size;
 114         u64 cur_inode_mode;
 115         u64 cur_inode_rdev;
 116         u64 cur_inode_last_extent;
 117
 118         u64 send_progress;
 119
 120         struct list_head new_refs;
 121         struct list_head deleted_refs;
 122
 123         struct radix_tree_root name_cache;
 124         struct list_head name_cache_list;
 125         int name_cache_size;
 126
 127         struct file_ra_state ra;
 128
 129         char *read_buf;
 130
 131         /*
 132          * We process inodes by their increasing order, so if before an
 133          * incremental send we reverse the parent/child relationship of
 134          * directories such that a directory with a lower inode number was
 135          * the parent of a directory with a higher inode number, and the one
 136          * becoming the new parent got renamed too, we can't rename/move the
 137          * directory with lower inode number when we finish processing it - we
 138          * must process the directory with higher inode number first, then
 139          * rename/move it and then rename/move the directory with lower inode
 140          * number. Example follows.
 141          *
 142          * Tree state when the first send was performed:
 143          *
 144          * .
 145          * |-- a                   (ino 257)
 146          *     |-- b               (ino 258)
 147          *         |
 148          *         |
 149          *         |-- c           (ino 259)
 150          *         |   |-- d       (ino 260)
 151          *         |
 152          *         |-- c2          (ino 261)
 153          *
 154          * Tree state when the second (incremental) send is performed:
 155          *
 156          * .
 157          * |-- a                   (ino 257)
 158          *     |-- b               (ino 258)
 159          *         |-- c2          (ino 261)
 160          *             |-- d2      (ino 260)
 161          *                 |-- cc  (ino 259)
 162          *
 163          * The sequence of steps that lead to the second state was:
 164          *
 165          * mv /a/b/c/d /a/b/c2/d2
 166          * mv /a/b/c /a/b/c2/d2/cc
 167          *
 168          * "c" has lower inode number, but we can't move it (2nd mv operation)
 169          * before we move "d", which has higher inode number.
 170          *
 171          * So we just memorize which move/rename operations must be performed
 172          * later when their respective parent is processed and moved/renamed.
 173          */
 174
 175         /* Indexed by parent directory inode number. */
 176         struct rb_root pending_dir_moves;
 177
 178         /*
 179          * Reverse index, indexed by the inode number of a directory that
 180          * is waiting for the move/rename of its immediate parent before its
 181          * own move/rename can be performed.
 182          */
 183         struct rb_root waiting_dir_moves;
 184
 185         /*
 186          * A directory that is going to be rm'ed might have a child directory
 187          * which is in the pending directory moves index above. In this case,
 188          * the directory can only be removed after the move/rename of its child
 189          * is performed. Example:
 190          *
 191          * Parent snapshot:
 192          *
 193          * .                        (ino 256)
 194          * |-- a/                   (ino 257)
 195          *     |-- b/               (ino 258)
 196          *         |-- c/           (ino 259)
 197          *         |   |-- x/       (ino 260)
 198          *         |
 199          *         |-- y/           (ino 261)
 200          *
 201          * Send snapshot:
 202          *
 203          * .                        (ino 256)
 204          * |-- a/                   (ino 257)
 205          *     |-- b/               (ino 258)
 206          *         |-- YY/          (ino 261)
 207          *              |-- x/      (ino 260)
 208          *
 209          * Sequence of steps that lead to the send snapshot:
 210          * rm -f /a/b/c/foo.txt
 211          * mv /a/b/y /a/b/YY
 212          * mv /a/b/c/x /a/b/YY
 213          * rmdir /a/b/c
 214          *
 215          * When the child is processed, its move/rename is delayed until its
 216          * parent is processed (as explained above), but all other operations
 217          * like update utimes, chown, chgrp, etc, are performed and the paths
 218          * that it uses for those operations must use the orphanized name of
 219          * its parent (the directory we're going to rm later), so we need to
 220          * memorize that name.
 221          *
 222          * Indexed by the inode number of the directory to be deleted.
 223          */
 224         struct rb_root orphan_dirs;
 225 };
 226
 227 struct pending_dir_move {
 228         struct rb_node node;
 229         struct list_head list;
 230         u64 parent_ino;
 231         u64 ino;
 232         u64 gen;
 233         struct list_head update_refs;
 234 };
 235
 236 struct waiting_dir_move {
 237         struct rb_node node;
 238         u64 ino;
 239         /*
 240          * There might be some directory that could not be removed because it
 241          * was waiting for this directory inode to be moved first. Therefore
 242          * after this directory is moved, we can try to rmdir the ino rmdir_ino.
 243          */
 244         u64 rmdir_ino;
 245 };
 246
 247 struct orphan_dir_info {
 248         struct rb_node node;
 249         u64 ino;
 250         u64 gen;
 251 };
 252
 253 struct name_cache_entry {
 254         struct list_head list;
 255         /*
 256          * radix_tree has only 32bit entries but we need to handle 64bit inums.
 257          * We use the lower 32bit of the 64bit inum to store it in the tree. If
 258          * more then one inum would fall into the same entry, we use radix_list
 259          * to store the additional entries. radix_list is also used to store
 260          * entries where two entries have the same inum but different
 261          * generations.
 262          */
 263         struct list_head radix_list;
 264         u64 ino;
 265         u64 gen;
 266         u64 parent_ino;
 267         u64 parent_gen;
 268         int ret;
 269         int need_later_update;
 270         int name_len;
 271         char name[];
 272 };
 273
 274 static int is_waiting_for_move(struct send_ctx *sctx, u64 ino);
 275
 276 static struct waiting_dir_move *
 277 get_waiting_dir_move(struct send_ctx *sctx, u64 ino);
 278
 279 static int is_waiting_for_rm(struct send_ctx *sctx, u64 dir_ino);
 280
 281 static int need_send_hole(struct send_ctx *sctx)
 282 {
 283         return (sctx->parent_root && !sctx->cur_inode_new &&
 284                 !sctx->cur_inode_new_gen && !sctx->cur_inode_deleted &&
 285                 S_ISREG(sctx->cur_inode_mode));
 286 }
 287
 288 static void fs_path_reset(struct fs_path *p)
 289 {
 290         if (p->reversed) {
 291                 p->start = p->buf + p->buf_len - 1;
 292                 p->end = p->start;
 293                 *p->start = 0;
 294         } else {
 295                 p->start = p->buf;
 296                 p->end = p->start;
 297                 *p->start = 0;
 298         }
 299 }
 300
 301 static struct fs_path *fs_path_alloc(void)
 302 {
 303         struct fs_path *p;
 304
 305         p = kmalloc(sizeof(*p), GFP_NOFS);
 306         if (!p)
 307                 return NULL;
 308         p->reversed = 0;
 309         p->buf = p->inline_buf;
 310         p->buf_len = FS_PATH_INLINE_SIZE;
 311         fs_path_reset(p);
 312         return p;
 313 }
 314
 315 static struct fs_path *fs_path_alloc_reversed(void)
 316 {
 317         struct fs_path *p;
 318
 319         p = fs_path_alloc();
 320         if (!p)
 321                 return NULL;
 322         p->reversed = 1;
 323         fs_path_reset(p);
 324         return p;
 325 }
 326
 327 static void fs_path_free(struct fs_path *p)
 328 {
 329         if (!p)
 330                 return;
 331         if (p->buf != p->inline_buf)
 332                 kfree(p->buf);
 333         kfree(p);
 334 }
 335
 336 static int fs_path_len(struct fs_path *p)
 337 {
 338         return p->end - p->start;
 339 }
 340
 341 static int fs_path_ensure_buf(struct fs_path *p, int len)
 342 {
 343         char *tmp_buf;
 344         int path_len;
 345         int old_buf_len;
 346
 347         len++;
 348
 349         if (p->buf_len >= len)
 350                 return 0;
 351
 352         path_len = p->end - p->start;
 353         old_buf_len = p->buf_len;
 354
 355         /*
 356          * First time the inline_buf does not suffice
 357          */
 358         if (p->buf == p->inline_buf)
 359                 tmp_buf = kmalloc(len, GFP_NOFS);
 360         else
 361                 tmp_buf = krealloc(p->buf, len, GFP_NOFS);
 362         if (!tmp_buf)
 363                 return -ENOMEM;
 364         p->buf = tmp_buf;
 365         /*
 366          * The real size of the buffer is bigger, this will let the fast path
 367          * happen most of the time
 368          */
 369         p->buf_len = ksize(p->buf);
 370
 371         if (p->reversed) {
 372                 tmp_buf = p->buf + old_buf_len - path_len - 1;
 373                 p->end = p->buf + p->buf_len - 1;
 374                 p->start = p->end - path_len;
 375                 memmove(p->start, tmp_buf, path_len + 1);
 376         } else {
 377                 p->start = p->buf;
 378                 p->end = p->start + path_len;
 379         }
 380         return 0;
 381 }
 382
 383 static int fs_path_prepare_for_add(struct fs_path *p, int name_len,
 384                                    char **prepared)
 385 {
 386         int ret;
 387         int new_len;
 388
 389         new_len = p->end - p->start + name_len;
 390         if (p->start != p->end)
 391                 new_len++;
 392         ret = fs_path_ensure_buf(p, new_len);
 393         if (ret < 0)
 394                 goto out;
 395
 396         if (p->reversed) {
 397                 if (p->start != p->end)
 398                         *--p->start = '/';
 399                 p->start -= name_len;
 400                 *prepared = p->start;
 401         } else {
 402                 if (p->start != p->end)
 403                         *p->end++ = '/';
 404                 *prepared = p->end;
 405                 p->end += name_len;
 406                 *p->end = 0;
 407         }
 408
 409 out:
 410         return ret;
 411 }
 412
 413 static int fs_path_add(struct fs_path *p, const char *name, int name_len)
 414 {
 415         int ret;
 416         char *prepared;
 417
 418         ret = fs_path_prepare_for_add(p, name_len, &prepared);
 419         if (ret < 0)
 420                 goto out;
 421         memcpy(prepared, name, name_len);
 422
 423 out:
 424         return ret;
 425 }
 426
 427 static int fs_path_add_path(struct fs_path *p, struct fs_path *p2)
 428 {
 429         int ret;
 430         char *prepared;
 431
 432         ret = fs_path_prepare_for_add(p, p2->end - p2->start, &prepared);
 433         if (ret < 0)
 434                 goto out;
 435         memcpy(prepared, p2->start, p2->end - p2->start);
 436
 437 out:
 438         return ret;
 439 }
 440
 441 static int fs_path_add_from_extent_buffer(struct fs_path *p,
 442                                           struct extent_buffer *eb,
 443                                           unsigned long off, int len)
 444 {
 445         int ret;
 446         char *prepared;
 447
 448         ret = fs_path_prepare_for_add(p, len, &prepared);
 449         if (ret < 0)
 450                 goto out;
 451
 452         read_extent_buffer(eb, prepared, off, len);
 453
 454 out:
 455         return ret;
 456 }
 457
 458 static int fs_path_copy(struct fs_path *p, struct fs_path *from)
 459 {
 460         int ret;
 461
 462         p->reversed = from->reversed;
 463         fs_path_reset(p);
 464
 465         ret = fs_path_add_path(p, from);
 466
 467         return ret;
 468 }
 469
 470
 471 static void fs_path_unreverse(struct fs_path *p)
 472 {
 473         char *tmp;
 474         int len;
 475
 476         if (!p->reversed)
 477                 return;
 478
 479         tmp = p->start;
 480         len = p->end - p->start;
 481         p->start = p->buf;
 482         p->end = p->start + len;
 483         memmove(p->start, tmp, len + 1);
 484         p->reversed = 0;
 485 }
 486
 487 static struct btrfs_path *alloc_path_for_send(void)
 488 {
 489         struct btrfs_path *path;
 490
 491         path = btrfs_alloc_path();
 492         if (!path)
 493                 return NULL;
 494         path->search_commit_root = 1;
 495         path->skip_locking = 1;
 496         return path;
 497 }
 498
 499 static int write_buf(struct file *filp, const void *buf, u32 len, loff_t *off)
 500 {
 501         int ret;
 502         mm_segment_t old_fs;
 503         u32 pos = 0;
 504
 505         old_fs = get_fs();
 506         set_fs(KERNEL_DS);
 507
 508         while (pos < len) {
 509                 ret = vfs_write(filp, (char *)buf + pos, len - pos, off);
 510                 /* TODO handle that correctly */
 511                 /*if (ret == -ERESTARTSYS) {
 512                         continue;
 513                 }*/
 514                 if (ret < 0)
 515                         goto out;
 516                 if (ret == 0) {
 517                         ret = -EIO;
 518                         goto out;
 519                 }
 520                 pos += ret;
 521         }
 522
 523         ret = 0;
 524
 525 out:
 526         set_fs(old_fs);
 527         return ret;
 528 }
 529
 530 static int tlv_put(struct send_ctx *sctx, u16 attr, const void *data, int len)
 531 {
 532         struct btrfs_tlv_header *hdr;
 533         int total_len = sizeof(*hdr) + len;
 534         int left = sctx->send_max_size - sctx->send_size;
 535
 536         if (unlikely(left < total_len))
 537                 return -EOVERFLOW;
 538
 539         hdr = (struct btrfs_tlv_header *) (sctx->send_buf + sctx->send_size);
 540         hdr->tlv_type = cpu_to_le16(attr);
 541         hdr->tlv_len = cpu_to_le16(len);
 542         memcpy(hdr + 1, data, len);
 543         sctx->send_size += total_len;
 544
 545         return 0;
 546 }
 547
 548 #define TLV_PUT_DEFINE_INT(bits) \
 549         static int tlv_put_u##bits(struct send_ctx *sctx,               \
 550                         u##bits attr, u##bits value)                    \
 551         {                                                               \
 552                 __le##bits __tmp = cpu_to_le##bits(value);              \
 553                 return tlv_put(sctx, attr, &__tmp, sizeof(__tmp));      \
 554         }
 555
 556 TLV_PUT_DEFINE_INT(64)
 557
 558 static int tlv_put_string(struct send_ctx *sctx, u16 attr,
 559                           const char *str, int len)
 560 {
 561         if (len == -1)
 562                 len = strlen(str);
 563         return tlv_put(sctx, attr, str, len);
 564 }
 565
 566 static int tlv_put_uuid(struct send_ctx *sctx, u16 attr,
 567                         const u8 *uuid)
 568 {
 569         return tlv_put(sctx, attr, uuid, BTRFS_UUID_SIZE);
 570 }
 571
 572 static int tlv_put_btrfs_timespec(struct send_ctx *sctx, u16 attr,
 573                                   struct extent_buffer *eb,
 574                                   struct btrfs_timespec *ts)
 575 {
 576         struct btrfs_timespec bts;
 577         read_extent_buffer(eb, &bts, (unsigned long)ts, sizeof(bts));
 578         return tlv_put(sctx, attr, &bts, sizeof(bts));
 579 }
 580
 581
 582 #define TLV_PUT(sctx, attrtype, attrlen, data) \
 583         do { \
 584                 ret = tlv_put(sctx, attrtype, attrlen, data); \
 585                 if (ret < 0) \
 586                         goto tlv_put_failure; \
 587         } while (0)
 588
 589 #define TLV_PUT_INT(sctx, attrtype, bits, value) \
 590         do { \
 591                 ret = tlv_put_u##bits(sctx, attrtype, value); \
 592                 if (ret < 0) \
 593                         goto tlv_put_failure; \
 594         } while (0)
 595
 596 #define TLV_PUT_U8(sctx, attrtype, data) TLV_PUT_INT(sctx, attrtype, 8, data)
 597 #define TLV_PUT_U16(sctx, attrtype, data) TLV_PUT_INT(sctx, attrtype, 16, data)
 598 #define TLV_PUT_U32(sctx, attrtype, data) TLV_PUT_INT(sctx, attrtype, 32, data)
 599 #define TLV_PUT_U64(sctx, attrtype, data) TLV_PUT_INT(sctx, attrtype, 64, data)
 600 #define TLV_PUT_STRING(sctx, attrtype, str, len) \
 601         do { \
 602                 ret = tlv_put_string(sctx, attrtype, str, len); \
 603                 if (ret < 0) \
 604                         goto tlv_put_failure; \
 605         } while (0)
 606 #define TLV_PUT_PATH(sctx, attrtype, p) \
 607         do { \
 608                 ret = tlv_put_string(sctx, attrtype, p->start, \
 609                         p->end - p->start); \
 610                 if (ret < 0) \
 611                         goto tlv_put_failure; \
 612         } while(0)
 613 #define TLV_PUT_UUID(sctx, attrtype, uuid) \
 614         do { \
 615                 ret = tlv_put_uuid(sctx, attrtype, uuid); \
 616                 if (ret < 0) \
 617                         goto tlv_put_failure; \
 618         } while (0)
 619 #define TLV_PUT_BTRFS_TIMESPEC(sctx, attrtype, eb, ts) \
 620         do { \
 621                 ret = tlv_put_btrfs_timespec(sctx, attrtype, eb, ts); \
 622                 if (ret < 0) \
 623                         goto tlv_put_failure; \
 624         } while (0)
 625
 626 static int send_header(struct send_ctx *sctx)
 627 {
 628         struct btrfs_stream_header hdr;
 629
 630         strcpy(hdr.magic, BTRFS_SEND_STREAM_MAGIC);
 631         hdr.version = cpu_to_le32(BTRFS_SEND_STREAM_VERSION);
 632
 633         return write_buf(sctx->send_filp, &hdr, sizeof(hdr),
 634                                         &sctx->send_off);
 635 }
 636
 637 /*
 638  * For each command/item we want to send to userspace, we call this function.
 639  */
 640 static int begin_cmd(struct send_ctx *sctx, int cmd)
 641 {
 642         struct btrfs_cmd_header *hdr;
 643
 644         if (WARN_ON(!sctx->send_buf))
 645                 return -EINVAL;
 646
 647         BUG_ON(sctx->send_size);
 648
 649         sctx->send_size += sizeof(*hdr);
 650         hdr = (struct btrfs_cmd_header *)sctx->send_buf;
 651         hdr->cmd = cpu_to_le16(cmd);
 652
 653         return 0;
 654 }
 655
 656 static int send_cmd(struct send_ctx *sctx)
 657 {
 658         int ret;
 659         struct btrfs_cmd_header *hdr;
 660         u32 crc;
 661
 662         hdr = (struct btrfs_cmd_header *)sctx->send_buf;
 663         hdr->len = cpu_to_le32(sctx->send_size - sizeof(*hdr));
 664         hdr->crc = 0;
 665
 666         crc = btrfs_crc32c(0, (unsigned char *)sctx->send_buf, sctx->send_size);
 667         hdr->crc = cpu_to_le32(crc);
 668
 669         ret = write_buf(sctx->send_filp, sctx->send_buf, sctx->send_size,
 670                                         &sctx->send_off);
 671
 672         sctx->total_send_size += sctx->send_size;
 673         sctx->cmd_send_size[le16_to_cpu(hdr->cmd)] += sctx->send_size;
 674         sctx->send_size = 0;
 675
 676         return ret;
 677 }
 678
 679 /*
 680  * Sends a move instruction to user space
 681  */
 682 static int send_rename(struct send_ctx *sctx,
 683                      struct fs_path *from, struct fs_path *to)
 684 {
 685         int ret;
 686
 687 verbose_printk("btrfs: send_rename %s -> %s\n", from->start, to->start);
 688
 689         ret = begin_cmd(sctx, BTRFS_SEND_C_RENAME);
 690         if (ret < 0)
 691                 goto out;
 692
 693         TLV_PUT_PATH(sctx, BTRFS_SEND_A_PATH, from);
 694         TLV_PUT_PATH(sctx, BTRFS_SEND_A_PATH_TO, to);
 695
 696         ret = send_cmd(sctx);
 697
 698 tlv_put_failure:
 699 out:
 700         return ret;
 701 }
 702
 703 /*
 704  * Sends a link instruction to user space
 705  */
 706 static int send_link(struct send_ctx *sctx,
 707                      struct fs_path *path, struct fs_path *lnk)
 708 {
 709         int ret;
 710
 711 verbose_printk("btrfs: send_link %s -> %s\n", path->start, lnk->start);
 712
 713         ret = begin_cmd(sctx, BTRFS_SEND_C_LINK);
 714         if (ret < 0)
 715                 goto out;
 716
 717         TLV_PUT_PATH(sctx, BTRFS_SEND_A_PATH, path);
 718         TLV_PUT_PATH(sctx, BTRFS_SEND_A_PATH_LINK, lnk);
 719
 720         ret = send_cmd(sctx);
 721
 722 tlv_put_failure:
 723 out:
 724         return ret;
 725 }
 726
 727 /*
 728  * Sends an unlink instruction to user space
 729  */
 730 static int send_unlink(struct send_ctx *sctx, struct fs_path *path)
 731 {
 732         int ret;
 733
 734 verbose_printk("btrfs: send_unlink %s\n", path->start);
 735
 736         ret = begin_cmd(sctx, BTRFS_SEND_C_UNLINK);
 737         if (ret < 0)
 738                 goto out;
 739
 740         TLV_PUT_PATH(sctx, BTRFS_SEND_A_PATH, path);
 741
 742         ret = send_cmd(sctx);
 743
 744 tlv_put_failure:
 745 out:
 746         return ret;
 747 }
 748
 749 /*
 750  * Sends a rmdir instruction to user space
 751  */
 752 static int send_rmdir(struct send_ctx *sctx, struct fs_path *path)
 753 {
 754         int ret;
 755
 756 verbose_printk("btrfs: send_rmdir %s\n", path->start);
 757
 758         ret = begin_cmd(sctx, BTRFS_SEND_C_RMDIR);
 759         if (ret < 0)
 760                 goto out;
 761
 762         TLV_PUT_PATH(sctx, BTRFS_SEND_A_PATH, path);
 763
 764         ret = send_cmd(sctx);
 765
 766 tlv_put_failure:
 767 out:
 768         return ret;
 769 }
 770
 771 /*
 772  * Helper function to retrieve some fields from an inode item.
 773  */
 774 static int get_inode_info(struct btrfs_root *root,
 775                           u64 ino, u64 *size, u64 *gen,
 776                           u64 *mode, u64 *uid, u64 *gid,
 777                           u64 *rdev)
 778 {
 779         int ret;
 780         struct btrfs_inode_item *ii;
 781         struct btrfs_key key;
 782         struct btrfs_path *path;
 783
 784         path = alloc_path_for_send();
 785         if (!path)
 786                 return -ENOMEM;
 787
 788         key.objectid = ino;
 789         key.type = BTRFS_INODE_ITEM_KEY;
 790         key.offset = 0;
 791         ret = btrfs_search_slot(NULL, root, &key, path, 0, 0);
 792         if (ret < 0)
 793                 goto out;
 794         if (ret) {
 795                 ret = -ENOENT;
 796                 goto out;
 797         }
 798
 799         ii = btrfs_item_ptr(path->nodes[0], path->slots[0],
 800                         struct btrfs_inode_item);
 801         if (size)
 802                 *size = btrfs_inode_size(path->nodes[0], ii);
 803         if (gen)
 804                 *gen = btrfs_inode_generation(path->nodes[0], ii);
 805         if (mode)
 806                 *mode = btrfs_inode_mode(path->nodes[0], ii);
 807         if (uid)
 808                 *uid = btrfs_inode_uid(path->nodes[0], ii);
 809         if (gid)
 810                 *gid = btrfs_inode_gid(path->nodes[0], ii);
 811         if (rdev)
 812                 *rdev = btrfs_inode_rdev(path->nodes[0], ii);
 813
 814 out:
 815         btrfs_free_path(path);
 816         return ret;
 817 }
 818
 819 typedef int (*iterate_inode_ref_t)(int num, u64 dir, int index,
 820                                    struct fs_path *p,
 821                                    void *ctx);
 822
 823 /*
 824  * Helper function to iterate the entries in ONE btrfs_inode_ref or
 825  * btrfs_inode_extref.
 826  * The iterate callback may return a non zero value to stop iteration. This can
 827  * be a negative value for error codes or 1 to simply stop it.
 828  *
 829  * path must point to the INODE_REF or INODE_EXTREF when called.
 830  */
 831 static int iterate_inode_ref(struct btrfs_root *root, struct btrfs_path *path,
 832                              struct btrfs_key *found_key, int resolve,
 833                              iterate_inode_ref_t iterate, void *ctx)
 834 {
 835         struct extent_buffer *eb = path->nodes[0];
 836         struct btrfs_item *item;
 837         struct btrfs_inode_ref *iref;
 838         struct btrfs_inode_extref *extref;
 839         struct btrfs_path *tmp_path;
 840         struct fs_path *p;
 841         u32 cur = 0;
 842         u32 total;
 843         int slot = path->slots[0];
 844         u32 name_len;
 845         char *start;
 846         int ret = 0;
 847         int num = 0;
 848         int index;
 849         u64 dir;
 850         unsigned long name_off;
 851         unsigned long elem_size;
 852         unsigned long ptr;
 853
 854         p = fs_path_alloc_reversed();
 855         if (!p)
 856                 return -ENOMEM;
 857
 858         tmp_path = alloc_path_for_send();
 859         if (!tmp_path) {
 860                 fs_path_free(p);
 861                 return -ENOMEM;
 862         }
 863
 864
 865         if (found_key->type == BTRFS_INODE_REF_KEY) {
 866                 ptr = (unsigned long)btrfs_item_ptr(eb, slot,
 867                                                     struct btrfs_inode_ref);
 868                 item = btrfs_item_nr(slot);
 869                 total = btrfs_item_size(eb, item);
 870                 elem_size = sizeof(*iref);
 871         } else {
 872                 ptr = btrfs_item_ptr_offset(eb, slot);
 873                 total = btrfs_item_size_nr(eb, slot);
 874                 elem_size = sizeof(*extref);
 875         }
 876
 877         while (cur < total) {
 878                 fs_path_reset(p);
 879
 880                 if (found_key->type == BTRFS_INODE_REF_KEY) {
 881                         iref = (struct btrfs_inode_ref *)(ptr + cur);
 882                         name_len = btrfs_inode_ref_name_len(eb, iref);
 883                         name_off = (unsigned long)(iref + 1);
 884                         index = btrfs_inode_ref_index(eb, iref);
 885                         dir = found_key->offset;
 886                 } else {
 887                         extref = (struct btrfs_inode_extref *)(ptr + cur);
 888                         name_len = btrfs_inode_extref_name_len(eb, extref);
 889                         name_off = (unsigned long)&extref->name;
 890                         index = btrfs_inode_extref_index(eb, extref);
 891                         dir = btrfs_inode_extref_parent(eb, extref);
 892                 }
 893
 894                 if (resolve) {
 895                         start = btrfs_ref_to_path(root, tmp_path, name_len,
 896                                                   name_off, eb, dir,
 897                                                   p->buf, p->buf_len);
 898                         if (IS_ERR(start)) {
 899                                 ret = PTR_ERR(start);
 900                                 goto out;
 901                         }
 902                         if (start < p->buf) {
 903                                 /* overflow , try again with larger buffer */
 904                                 ret = fs_path_ensure_buf(p,
 905                                                 p->buf_len + p->buf - start);
 906                                 if (ret < 0)
 907                                         goto out;
 908                                 start = btrfs_ref_to_path(root, tmp_path,
 909                                                           name_len, name_off,
 910                                                           eb, dir,
 911                                                           p->buf, p->buf_len);
 912                                 if (IS_ERR(start)) {
 913                                         ret = PTR_ERR(start);
 914                                         goto out;
 915                                 }
 916                                 BUG_ON(start < p->buf);
 917                         }
 918                         p->start = start;
 919                 } else {
 920                         ret = fs_path_add_from_extent_buffer(p, eb, name_off,
 921                                                              name_len);
 922                         if (ret < 0)
 923                                 goto out;
 924                 }
 925
 926                 cur += elem_size + name_len;
 927                 ret = iterate(num, dir, index, p, ctx);
 928                 if (ret)
 929                         goto out;
 930                 num++;
 931         }
 932
 933 out:
 934         btrfs_free_path(tmp_path);
 935         fs_path_free(p);
 936         return ret;
 937 }
 938
 939 typedef int (*iterate_dir_item_t)(int num, struct btrfs_key *di_key,
 940                                   const char *name, int name_len,
 941                                   const char *data, int data_len,
 942                                   u8 type, void *ctx);
 943
 944 /*
 945  * Helper function to iterate the entries in ONE btrfs_dir_item.
 946  * The iterate callback may return a non zero value to stop iteration. This can
 947  * be a negative value for error codes or 1 to simply stop it.
 948  *
 949  * path must point to the dir item when called.
 950  */
 951 static int iterate_dir_item(struct btrfs_root *root, struct btrfs_path *path,
 952                             struct btrfs_key *found_key,
 953                             iterate_dir_item_t iterate, void *ctx)
 954 {
 955         int ret = 0;
 956         struct extent_buffer *eb;
 957         struct btrfs_item *item;
 958         struct btrfs_dir_item *di;
 959         struct btrfs_key di_key;
 960         char *buf = NULL;
 961         const int buf_len = PATH_MAX;
 962         u32 name_len;
 963         u32 data_len;
 964         u32 cur;
 965         u32 len;
 966         u32 total;
 967         int slot;
 968         int num;
 969         u8 type;
 970
 971         buf = kmalloc(buf_len, GFP_NOFS);
 972         if (!buf) {
 973                 ret = -ENOMEM;
 974                 goto out;
 975         }
 976
 977         eb = path->nodes[0];
 978         slot = path->slots[0];
 979         item = btrfs_item_nr(slot);
 980         di = btrfs_item_ptr(eb, slot, struct btrfs_dir_item);
 981         cur = 0;
 982         len = 0;
 983         total = btrfs_item_size(eb, item);
 984
 985         num = 0;
 986         while (cur < total) {
 987                 name_len = btrfs_dir_name_len(eb, di);
 988                 data_len = btrfs_dir_data_len(eb, di);
 989                 type = btrfs_dir_type(eb, di);
 990                 btrfs_dir_item_key_to_cpu(eb, di, &di_key);
 991
 992                 /*
 993                  * Path too long
 994                  */
 995                 if (name_len + data_len > buf_len) {
 996                         ret = -ENAMETOOLONG;
 997                         goto out;
 998                 }
 999
1000                 read_extent_buffer(eb, buf, (unsigned long)(di + 1),
1001                                 name_len + data_len);
1002
1003                 len = sizeof(*di) + name_len + data_len;
1004                 di = (struct btrfs_dir_item *)((char *)di + len);
1005                 cur += len;
1006
1007                 ret = iterate(num, &di_key, buf, name_len, buf + name_len,
1008                                 data_len, type, ctx);
1009                 if (ret < 0)
1010                         goto out;
1011                 if (ret) {
1012                         ret = 0;
1013                         goto out;
1014                 }
1015
1016                 num++;
1017         }
1018
1019 out:
1020         kfree(buf);
1021         return ret;
1022 }
1023
1024 static int __copy_first_ref(int num, u64 dir, int index,
1025                             struct fs_path *p, void *ctx)
1026 {
1027         int ret;
1028         struct fs_path *pt = ctx;
1029
1030         ret = fs_path_copy(pt, p);
1031         if (ret < 0)
1032                 return ret;
1033
1034         /* we want the first only */
1035         return 1;
1036 }
1037
1038 /*
1039  * Retrieve the first path of an inode. If an inode has more then one
1040  * ref/hardlink, this is ignored.
1041  */
1042 static int get_inode_path(struct btrfs_root *root,
1043                           u64 ino, struct fs_path *path)
1044 {
1045         int ret;
1046         struct btrfs_key key, found_key;
1047         struct btrfs_path *p;
1048
1049         p = alloc_path_for_send();
1050         if (!p)
1051                 return -ENOMEM;
1052
1053         fs_path_reset(path);
1054
1055         key.objectid = ino;
1056         key.type = BTRFS_INODE_REF_KEY;
1057         key.offset = 0;
1058
1059         ret = btrfs_search_slot_for_read(root, &key, p, 1, 0);
1060         if (ret < 0)
1061                 goto out;
1062         if (ret) {
1063                 ret = 1;
1064                 goto out;
1065         }
1066         btrfs_item_key_to_cpu(p->nodes[0], &found_key, p->slots[0]);
1067         if (found_key.objectid != ino ||
1068             (found_key.type != BTRFS_INODE_REF_KEY &&
1069              found_key.type != BTRFS_INODE_EXTREF_KEY)) {
1070                 ret = -ENOENT;
1071                 goto out;
1072         }
1073
1074         ret = iterate_inode_ref(root, p, &found_key, 1,
1075                                 __copy_first_ref, path);
1076         if (ret < 0)
1077                 goto out;
1078         ret = 0;
1079
1080 out:
1081         btrfs_free_path(p);
1082         return ret;
1083 }
1084
1085 struct backref_ctx {
1086         struct send_ctx *sctx;
1087
1088         /* number of total found references */
1089         u64 found;
1090
1091         /*
1092          * used for clones found in send_root. clones found behind cur_objectid
1093          * and cur_offset are not considered as allowed clones.
1094          */
1095         u64 cur_objectid;
1096         u64 cur_offset;
1097
1098         /* may be truncated in case it's the last extent in a file */
1099         u64 extent_len;
1100
1101         /* Just to check for bugs in backref resolving */
1102         int found_itself;
1103 };
1104
1105 static int __clone_root_cmp_bsearch(const void *key, const void *elt)
1106 {
1107         u64 root = (u64)(uintptr_t)key;
1108         struct clone_root *cr = (struct clone_root *)elt;
1109
1110         if (root < cr->root->objectid)
1111                 return -1;
1112         if (root > cr->root->objectid)
1113                 return 1;
1114         return 0;
1115 }
1116
1117 static int __clone_root_cmp_sort(const void *e1, const void *e2)
1118 {
1119         struct clone_root *cr1 = (struct clone_root *)e1;
1120         struct clone_root *cr2 = (struct clone_root *)e2;
1121
1122         if (cr1->root->objectid < cr2->root->objectid)
1123                 return -1;
1124         if (cr1->root->objectid > cr2->root->objectid)
1125                 return 1;
1126         return 0;
1127 }
1128
1129 /*
1130  * Called for every backref that is found for the current extent.
1131  * Results are collected in sctx->clone_roots->ino/offset/found_refs
1132  */
1133 static int __iterate_backrefs(u64 ino, u64 offset, u64 root, void *ctx_)
1134 {
1135         struct backref_ctx *bctx = ctx_;
1136         struct clone_root *found;
1137         int ret;
1138         u64 i_size;
1139
1140         /* First check if the root is in the list of accepted clone sources */
1141         found = bsearch((void *)(uintptr_t)root, bctx->sctx->clone_roots,
1142                         bctx->sctx->clone_roots_cnt,
1143                         sizeof(struct clone_root),
1144                         __clone_root_cmp_bsearch);
1145         if (!found)
1146                 return 0;
1147
1148         if (found->root == bctx->sctx->send_root &&
1149             ino == bctx->cur_objectid &&
1150             offset == bctx->cur_offset) {
1151                 bctx->found_itself = 1;
1152         }
1153
1154         /*
1155          * There are inodes that have extents that lie behind its i_size. Don't
1156          * accept clones from these extents.
1157          */
1158         ret = get_inode_info(found->root, ino, &i_size, NULL, NULL, NULL, NULL,
1159                         NULL);
1160         if (ret < 0)
1161                 return ret;
1162
1163         if (offset + bctx->extent_len > i_size)
1164                 return 0;
1165
1166         /*
1167          * Make sure we don't consider clones from send_root that are
1168          * behind the current inode/offset.
1169          */
1170         if (found->root == bctx->sctx->send_root) {
1171                 /*
1172                  * TODO for the moment we don't accept clones from the inode
1173                  * that is currently send. We may change this when
1174                  * BTRFS_IOC_CLONE_RANGE supports cloning from and to the same
1175                  * file.
1176                  */
1177                 if (ino >= bctx->cur_objectid)
1178                         return 0;
1179 #if 0
1180                 if (ino > bctx->cur_objectid)
1181                         return 0;
1182                 if (offset + bctx->extent_len > bctx->cur_offset)
1183                         return 0;
1184 #endif
1185         }
1186
1187         bctx->found++;
1188         found->found_refs++;
1189         if (ino < found->ino) {
1190                 found->ino = ino;
1191                 found->offset = offset;
1192         } else if (found->ino == ino) {
1193                 /*
1194                  * same extent found more then once in the same file.
1195                  */
1196                 if (found->offset > offset + bctx->extent_len)
1197                         found->offset = offset;
1198         }
1199
1200         return 0;
1201 }
1202
1203 /*
1204  * Given an inode, offset and extent item, it finds a good clone for a clone
1205  * instruction. Returns -ENOENT when none could be found. The function makes
1206  * sure that the returned clone is usable at the point where sending is at the
1207  * moment. This means, that no clones are accepted which lie behind the current
1208  * inode+offset.
1209  *
1210  * path must point to the extent item when called.
1211  */
1212 static int find_extent_clone(struct send_ctx *sctx,
1213                              struct btrfs_path *path,
1214                              u64 ino, u64 data_offset,
1215                              u64 ino_size,
1216                              struct clone_root **found)
1217 {
1218         int ret;
1219         int extent_type;
1220         u64 logical;
1221         u64 disk_byte;
1222         u64 num_bytes;
1223         u64 extent_item_pos;
1224         u64 flags = 0;
1225         struct btrfs_file_extent_item *fi;
1226         struct extent_buffer *eb = path->nodes[0];
1227         struct backref_ctx *backref_ctx = NULL;
1228         struct clone_root *cur_clone_root;
1229         struct btrfs_key found_key;
1230         struct btrfs_path *tmp_path;
1231         int compressed;
1232         u32 i;
1233
1234         tmp_path = alloc_path_for_send();
1235         if (!tmp_path)
1236                 return -ENOMEM;
1237
1238         backref_ctx = kmalloc(sizeof(*backref_ctx), GFP_NOFS);
1239         if (!backref_ctx) {
1240                 ret = -ENOMEM;
1241                 goto out;
1242         }
1243
1244         if (data_offset >= ino_size) {
1245                 /*
1246                  * There may be extents that lie behind the file's size.
1247                  * I at least had this in combination with snapshotting while
1248                  * writing large files.
1249                  */
1250                 ret = 0;
1251                 goto out;
1252         }
1253
1254         fi = btrfs_item_ptr(eb, path->slots[0],
1255                         struct btrfs_file_extent_item);
1256         extent_type = btrfs_file_extent_type(eb, fi);
1257         if (extent_type == BTRFS_FILE_EXTENT_INLINE) {
1258                 ret = -ENOENT;
1259                 goto out;
1260         }
1261         compressed = btrfs_file_extent_compression(eb, fi);
1262
1263         num_bytes = btrfs_file_extent_num_bytes(eb, fi);
1264         disk_byte = btrfs_file_extent_disk_bytenr(eb, fi);
1265         if (disk_byte == 0) {
1266                 ret = -ENOENT;
1267                 goto out;
1268         }
1269         logical = disk_byte + btrfs_file_extent_offset(eb, fi);
1270
1271         ret = extent_from_logical(sctx->send_root->fs_info, disk_byte, tmp_path,
1272                                   &found_key, &flags);
1273         btrfs_release_path(tmp_path);
1274
1275         if (ret < 0)
1276                 goto out;
1277         if (flags & BTRFS_EXTENT_FLAG_TREE_BLOCK) {
1278                 ret = -EIO;
1279                 goto out;
1280         }
1281
1282         /*
1283          * Setup the clone roots.
1284          */
1285         for (i = 0; i < sctx->clone_roots_cnt; i++) {
1286                 cur_clone_root = sctx->clone_roots + i;
1287                 cur_clone_root->ino = (u64)-1;
1288                 cur_clone_root->offset = 0;
1289                 cur_clone_root->found_refs = 0;
1290         }
1291
1292         backref_ctx->sctx = sctx;
1293         backref_ctx->found = 0;
1294         backref_ctx->cur_objectid = ino;
1295         backref_ctx->cur_offset = data_offset;
1296         backref_ctx->found_itself = 0;
1297         backref_ctx->extent_len = num_bytes;
1298
1299         /*
1300          * The last extent of a file may be too large due to page alignment.
1301          * We need to adjust extent_len in this case so that the checks in
1302          * __iterate_backrefs work.
1303          */
1304         if (data_offset + num_bytes >= ino_size)
1305                 backref_ctx->extent_len = ino_size - data_offset;
1306
1307         /*
1308          * Now collect all backrefs.
1309          */
1310         if (compressed == BTRFS_COMPRESS_NONE)
1311                 extent_item_pos = logical - found_key.objectid;
1312         else
1313                 extent_item_pos = 0;
1314         ret = iterate_extent_inodes(sctx->send_root->fs_info,
1315                                         found_key.objectid, extent_item_pos, 1,
1316                                         __iterate_backrefs, backref_ctx);
1317
1318         if (ret < 0)
1319                 goto out;
1320
1321         if (!backref_ctx->found_itself) {
1322                 /* found a bug in backref code? */
1323                 ret = -EIO;
1324                 btrfs_err(sctx->send_root->fs_info, "did not find backref in "
1325                                 "send_root. inode=%llu, offset=%llu, "
1326                                 "disk_byte=%llu found extent=%llu\n",
1327                                 ino, data_offset, disk_byte, found_key.objectid);
1328                 goto out;
1329         }
1330
1331 verbose_printk(KERN_DEBUG "btrfs: find_extent_clone: data_offset=%llu, "
1332                 "ino=%llu, "
1333                 "num_bytes=%llu, logical=%llu\n",
1334                 data_offset, ino, num_bytes, logical);
1335
1336         if (!backref_ctx->found)
1337                 verbose_printk("btrfs:    no clones found\n");
1338
1339         cur_clone_root = NULL;
1340         for (i = 0; i < sctx->clone_roots_cnt; i++) {
1341                 if (sctx->clone_roots[i].found_refs) {
1342                         if (!cur_clone_root)
1343                                 cur_clone_root = sctx->clone_roots + i;
1344                         else if (sctx->clone_roots[i].root == sctx->send_root)
1345                                 /* prefer clones from send_root over others */
1346                                 cur_clone_root = sctx->clone_roots + i;
1347                 }
1348
1349         }
1350
1351         if (cur_clone_root) {
1352                 if (compressed != BTRFS_COMPRESS_NONE) {
1353                         /*
1354                          * Offsets given by iterate_extent_inodes() are relative
1355                          * to the start of the extent, we need to add logical
1356                          * offset from the file extent item.
1357                          * (See why at backref.c:check_extent_in_eb())
1358                          */
1359                         cur_clone_root->offset += btrfs_file_extent_offset(eb,
1360                                                                            fi);
1361                 }
1362                 *found = cur_clone_root;
1363                 ret = 0;
1364         } else {
1365                 ret = -ENOENT;
1366         }
1367
1368 out:
1369         btrfs_free_path(tmp_path);
1370         kfree(backref_ctx);
1371         return ret;
1372 }
1373
1374 static int read_symlink(struct btrfs_root *root,
1375                         u64 ino,
1376                         struct fs_path *dest)
1377 {
1378         int ret;
1379         struct btrfs_path *path;
1380         struct btrfs_key key;
1381         struct btrfs_file_extent_item *ei;
1382         u8 type;
1383         u8 compression;
1384         unsigned long off;
1385         int len;
1386
1387         path = alloc_path_for_send();
1388         if (!path)
1389                 return -ENOMEM;
1390
1391         key.objectid = ino;
1392         key.type = BTRFS_EXTENT_DATA_KEY;
1393         key.offset = 0;
1394         ret = btrfs_search_slot(NULL, root, &key, path, 0, 0);
1395         if (ret < 0)
1396                 goto out;
1397         BUG_ON(ret);
1398
1399         ei = btrfs_item_ptr(path->nodes[0], path->slots[0],
1400                         struct btrfs_file_extent_item);
1401         type = btrfs_file_extent_type(path->nodes[0], ei);
1402         compression = btrfs_file_extent_compression(path->nodes[0], ei);
1403         BUG_ON(type != BTRFS_FILE_EXTENT_INLINE);
1404         BUG_ON(compression);
1405
1406         off = btrfs_file_extent_inline_start(ei);
1407         len = btrfs_file_extent_inline_len(path->nodes[0], path->slots[0], ei);
1408
1409         ret = fs_path_add_from_extent_buffer(dest, path->nodes[0], off, len);
1410
1411 out:
1412         btrfs_free_path(path);
1413         return ret;
1414 }
1415
1416 /*
1417  * Helper function to generate a file name that is unique in the root of
1418  * send_root and parent_root. This is used to generate names for orphan inodes.
1419  */
1420 static int gen_unique_name(struct send_ctx *sctx,
1421                            u64 ino, u64 gen,
1422                            struct fs_path *dest)
1423 {
1424         int ret = 0;
1425         struct btrfs_path *path;
1426         struct btrfs_dir_item *di;
1427         char tmp[64];
1428         int len;
1429         u64 idx = 0;
1430
1431         path = alloc_path_for_send();
1432         if (!path)
1433                 return -ENOMEM;
1434
1435         while (1) {
1436                 len = snprintf(tmp, sizeof(tmp), "o%llu-%llu-%llu",
1437                                 ino, gen, idx);
1438                 ASSERT(len < sizeof(tmp));
1439
1440                 di = btrfs_lookup_dir_item(NULL, sctx->send_root,
1441                                 path, BTRFS_FIRST_FREE_OBJECTID,
1442                                 tmp, strlen(tmp), 0);
1443                 btrfs_release_path(path);
1444                 if (IS_ERR(di)) {
1445                         ret = PTR_ERR(di);
1446                         goto out;
1447                 }
1448                 if (di) {
1449                         /* not unique, try again */
1450                         idx++;
1451                         continue;
1452                 }
1453
1454                 if (!sctx->parent_root) {
1455                         /* unique */
1456                         ret = 0;
1457                         break;
1458                 }
1459
1460                 di = btrfs_lookup_dir_item(NULL, sctx->parent_root,
1461                                 path, BTRFS_FIRST_FREE_OBJECTID,
1462                                 tmp, strlen(tmp), 0);
1463                 btrfs_release_path(path);
1464                 if (IS_ERR(di)) {
1465                         ret = PTR_ERR(di);
1466                         goto out;
1467                 }
1468                 if (di) {
1469                         /* not unique, try again */
1470                         idx++;
1471                         continue;
1472                 }
1473                 /* unique */
1474                 break;
1475         }
1476
1477         ret = fs_path_add(dest, tmp, strlen(tmp));
1478
1479 out:
1480         btrfs_free_path(path);
1481         return ret;
1482 }
1483
1484 enum inode_state {
1485         inode_state_no_change,
1486         inode_state_will_create,
1487         inode_state_did_create,
1488         inode_state_will_delete,
1489         inode_state_did_delete,
1490 };
1491
1492 static int get_cur_inode_state(struct send_ctx *sctx, u64 ino, u64 gen)
1493 {
1494         int ret;
1495         int left_ret;
1496         int right_ret;
1497         u64 left_gen;
1498         u64 right_gen;
1499
1500         ret = get_inode_info(sctx->send_root, ino, NULL, &left_gen, NULL, NULL,
1501                         NULL, NULL);
1502         if (ret < 0 && ret != -ENOENT)
1503                 goto out;
1504         left_ret = ret;
1505
1506         if (!sctx->parent_root) {
1507                 right_ret = -ENOENT;
1508         } else {
1509                 ret = get_inode_info(sctx->parent_root, ino, NULL, &right_gen,
1510                                 NULL, NULL, NULL, NULL);
1511                 if (ret < 0 && ret != -ENOENT)
1512                         goto out;
1513                 right_ret = ret;
1514         }
1515
1516         if (!left_ret && !right_ret) {
1517                 if (left_gen == gen && right_gen == gen) {
1518                         ret = inode_state_no_change;
1519                 } else if (left_gen == gen) {
1520                         if (ino < sctx->send_progress)
1521                                 ret = inode_state_did_create;
1522                         else
1523                                 ret = inode_state_will_create;
1524                 } else if (right_gen == gen) {
1525                         if (ino < sctx->send_progress)
1526                                 ret = inode_state_did_delete;
1527                         else
1528                                 ret = inode_state_will_delete;
1529                 } else  {
1530                         ret = -ENOENT;
1531                 }
1532         } else if (!left_ret) {
1533                 if (left_gen == gen) {
1534                         if (ino < sctx->send_progress)
1535                                 ret = inode_state_did_create;
1536                         else
1537                                 ret = inode_state_will_create;
1538                 } else {
1539                         ret = -ENOENT;
1540                 }
1541         } else if (!right_ret) {
1542                 if (right_gen == gen) {
1543                         if (ino < sctx->send_progress)
1544                                 ret = inode_state_did_delete;
1545                         else
1546                                 ret = inode_state_will_delete;
1547                 } else {
1548                         ret = -ENOENT;
1549                 }
1550         } else {
1551                 ret = -ENOENT;
1552         }
1553
1554 out:
1555         return ret;
1556 }
1557
1558 static int is_inode_existent(struct send_ctx *sctx, u64 ino, u64 gen)
1559 {
1560         int ret;
1561
1562         ret = get_cur_inode_state(sctx, ino, gen);
1563         if (ret < 0)
1564                 goto out;
1565
1566         if (ret == inode_state_no_change ||
1567             ret == inode_state_did_create ||
1568             ret == inode_state_will_delete)
1569                 ret = 1;
1570         else
1571                 ret = 0;
1572
1573 out:
1574         return ret;
1575 }
1576
1577 /*
1578  * Helper function to lookup a dir item in a dir.
1579  */
1580 static int lookup_dir_item_inode(struct btrfs_root *root,
1581                                  u64 dir, const char *name, int name_len,
1582                                  u64 *found_inode,
1583                                  u8 *found_type)
1584 {
1585         int ret = 0;
1586         struct btrfs_dir_item *di;
1587         struct btrfs_key key;
1588         struct btrfs_path *path;
1589
1590         path = alloc_path_for_send();
1591         if (!path)
1592                 return -ENOMEM;
1593
1594         di = btrfs_lookup_dir_item(NULL, root, path,
1595                         dir, name, name_len, 0);
1596         if (!di) {
1597                 ret = -ENOENT;
1598                 goto out;
1599         }
1600         if (IS_ERR(di)) {
1601                 ret = PTR_ERR(di);
1602                 goto out;
1603         }
1604         btrfs_dir_item_key_to_cpu(path->nodes[0], di, &key);
1605         *found_inode = key.objectid;
1606         *found_type = btrfs_dir_type(path->nodes[0], di);
1607
1608 out:
1609         btrfs_free_path(path);
1610         return ret;
1611 }
1612
1613 /*
1614  * Looks up the first btrfs_inode_ref of a given ino. It returns the parent dir,
1615  * generation of the parent dir and the name of the dir entry.
1616  */
1617 static int get_first_ref(struct btrfs_root *root, u64 ino,
1618                          u64 *dir, u64 *dir_gen, struct fs_path *name)
1619 {
1620         int ret;
1621         struct btrfs_key key;
1622         struct btrfs_key found_key;
1623         struct btrfs_path *path;
1624         int len;
1625         u64 parent_dir;
1626
1627         path = alloc_path_for_send();
1628         if (!path)
1629                 return -ENOMEM;
1630
1631         key.objectid = ino;
1632         key.type = BTRFS_INODE_REF_KEY;
1633         key.offset = 0;
1634
1635         ret = btrfs_search_slot_for_read(root, &key, path, 1, 0);
1636         if (ret < 0)
1637                 goto out;
1638         if (!ret)
1639                 btrfs_item_key_to_cpu(path->nodes[0], &found_key,
1640                                 path->slots[0]);
1641         if (ret || found_key.objectid != ino ||
1642             (found_key.type != BTRFS_INODE_REF_KEY &&
1643              found_key.type != BTRFS_INODE_EXTREF_KEY)) {
1644                 ret = -ENOENT;
1645                 goto out;
1646         }
1647
1648         if (key.type == BTRFS_INODE_REF_KEY) {
1649                 struct btrfs_inode_ref *iref;
1650                 iref = btrfs_item_ptr(path->nodes[0], path->slots[0],
1651                                       struct btrfs_inode_ref);
1652                 len = btrfs_inode_ref_name_len(path->nodes[0], iref);
1653                 ret = fs_path_add_from_extent_buffer(name, path->nodes[0],
1654                                                      (unsigned long)(iref + 1),
1655                                                      len);
1656                 parent_dir = found_key.offset;
1657         } else {
1658                 struct btrfs_inode_extref *extref;
1659                 extref = btrfs_item_ptr(path->nodes[0], path->slots[0],
1660                                         struct btrfs_inode_extref);
1661                 len = btrfs_inode_extref_name_len(path->nodes[0], extref);
1662                 ret = fs_path_add_from_extent_buffer(name, path->nodes[0],
1663                                         (unsigned long)&extref->name, len);
1664                 parent_dir = btrfs_inode_extref_parent(path->nodes[0], extref);
1665         }
1666         if (ret < 0)
1667                 goto out;
1668         btrfs_release_path(path);
1669
1670         ret = get_inode_info(root, parent_dir, NULL, dir_gen, NULL, NULL,
1671                         NULL, NULL);
1672         if (ret < 0)
1673                 goto out;
1674
1675         *dir = parent_dir;
1676
1677 out:
1678         btrfs_free_path(path);
1679         return ret;
1680 }
1681
1682 static int is_first_ref(struct btrfs_root *root,
1683                         u64 ino, u64 dir,
1684                         const char *name, int name_len)
1685 {
1686         int ret;
1687         struct fs_path *tmp_name;
1688         u64 tmp_dir;
1689         u64 tmp_dir_gen;
1690
1691         tmp_name = fs_path_alloc();
1692         if (!tmp_name)
1693                 return -ENOMEM;
1694
1695         ret = get_first_ref(root, ino, &tmp_dir, &tmp_dir_gen, tmp_name);
1696         if (ret < 0)
1697                 goto out;
1698
1699         if (dir != tmp_dir || name_len != fs_path_len(tmp_name)) {
1700                 ret = 0;
1701                 goto out;
1702         }
1703
1704         ret = !memcmp(tmp_name->start, name, name_len);
1705
1706 out:
1707         fs_path_free(tmp_name);
1708         return ret;
1709 }
1710
1711 /*
1712  * Used by process_recorded_refs to determine if a new ref would overwrite an
1713  * already existing ref. In case it detects an overwrite, it returns the
1714  * inode/gen in who_ino/who_gen.
1715  * When an overwrite is detected, process_recorded_refs does proper orphanizing
1716  * to make sure later references to the overwritten inode are possible.
1717  * Orphanizing is however only required for the first ref of an inode.
1718  * process_recorded_refs does an additional is_first_ref check to see if
1719  * orphanizing is really required.
1720  */
1721 static int will_overwrite_ref(struct send_ctx *sctx, u64 dir, u64 dir_gen,
1722                               const char *name, int name_len,
1723                               u64 *who_ino, u64 *who_gen)
1724 {
1725         int ret = 0;
1726         u64 gen;
1727         u64 other_inode = 0;
1728         u8 other_type = 0;
1729
1730         if (!sctx->parent_root)
1731                 goto out;
1732
1733         ret = is_inode_existent(sctx, dir, dir_gen);
1734         if (ret <= 0)
1735                 goto out;
1736
1737         /*
1738          * If we have a parent root we need to verify that the parent dir was
1739          * not delted and then re-created, if it was then we have no overwrite
1740          * and we can just unlink this entry.
1741          */
1742         if (sctx->parent_root) {
1743                 ret = get_inode_info(sctx->parent_root, dir, NULL, &gen, NULL,
1744                                      NULL, NULL, NULL);
1745                 if (ret < 0 && ret != -ENOENT)
1746                         goto out;
1747                 if (ret) {
1748                         ret = 0;
1749                         goto out;
1750                 }
1751                 if (gen != dir_gen)
1752                         goto out;
1753         }
1754
1755         ret = lookup_dir_item_inode(sctx->parent_root, dir, name, name_len,
1756                         &other_inode, &other_type);
1757         if (ret < 0 && ret != -ENOENT)
1758                 goto out;
1759         if (ret) {
1760                 ret = 0;
1761                 goto out;
1762         }
1763
1764         /*
1765          * Check if the overwritten ref was already processed. If yes, the ref
1766          * was already unlinked/moved, so we can safely assume that we will not
1767          * overwrite anything at this point in time.
1768          */
1769         if (other_inode > sctx->send_progress) {
1770                 ret = get_inode_info(sctx->parent_root, other_inode, NULL,
1771                                 who_gen, NULL, NULL, NULL, NULL);
1772                 if (ret < 0)
1773                         goto out;
1774
1775                 ret = 1;
1776                 *who_ino = other_inode;
1777         } else {
1778                 ret = 0;
1779         }
1780
1781 out:
1782         return ret;
1783 }
1784
1785 /*
1786  * Checks if the ref was overwritten by an already processed inode. This is
1787  * used by __get_cur_name_and_parent to find out if the ref was orphanized and
1788  * thus the orphan name needs be used.
1789  * process_recorded_refs also uses it to avoid unlinking of refs that were
1790  * overwritten.
1791  */
1792 static int did_overwrite_ref(struct send_ctx *sctx,
1793                             u64 dir, u64 dir_gen,
1794                             u64 ino, u64 ino_gen,
1795                             const char *name, int name_len)
1796 {
1797         int ret = 0;
1798         u64 gen;
1799         u64 ow_inode;
1800         u8 other_type;
1801
1802         if (!sctx->parent_root)
1803                 goto out;
1804
1805         ret = is_inode_existent(sctx, dir, dir_gen);
1806         if (ret <= 0)
1807                 goto out;
1808
1809         /* check if the ref was overwritten by another ref */
1810         ret = lookup_dir_item_inode(sctx->send_root, dir, name, name_len,
1811                         &ow_inode, &other_type);
1812         if (ret < 0 && ret != -ENOENT)
1813                 goto out;
1814         if (ret) {
1815                 /* was never and will never be overwritten */
1816                 ret = 0;
1817                 goto out;
1818         }
1819
1820         ret = get_inode_info(sctx->send_root, ow_inode, NULL, &gen, NULL, NULL,
1821                         NULL, NULL);
1822         if (ret < 0)
1823                 goto out;
1824
1825         if (ow_inode == ino && gen == ino_gen) {
1826                 ret = 0;
1827                 goto out;
1828         }
1829
1830         /* we know that it is or will be overwritten. check this now */
1831         if (ow_inode < sctx->send_progress)
1832                 ret = 1;
1833         else
1834                 ret = 0;
1835
1836 out:
1837         return ret;
1838 }
1839
1840 /*
1841  * Same as did_overwrite_ref, but also checks if it is the first ref of an inode
1842  * that got overwritten. This is used by process_recorded_refs to determine
1843  * if it has to use the path as returned by get_cur_path or the orphan name.
1844  */
1845 static int did_overwrite_first_ref(struct send_ctx *sctx, u64 ino, u64 gen)
1846 {
1847         int ret = 0;
1848         struct fs_path *name = NULL;
1849         u64 dir;
1850         u64 dir_gen;
1851
1852         if (!sctx->parent_root)
1853                 goto out;
1854
1855         name = fs_path_alloc();
1856         if (!name)
1857                 return -ENOMEM;
1858
1859         ret = get_first_ref(sctx->parent_root, ino, &dir, &dir_gen, name);
1860         if (ret < 0)
1861                 goto out;
1862
1863         ret = did_overwrite_ref(sctx, dir, dir_gen, ino, gen,
1864                         name->start, fs_path_len(name));
1865
1866 out:
1867         fs_path_free(name);
1868         return ret;
1869 }
1870
1871 /*
1872  * Insert a name cache entry. On 32bit kernels the radix tree index is 32bit,
1873  * so we need to do some special handling in case we have clashes. This function
1874  * takes care of this with the help of name_cache_entry::radix_list.
1875  * In case of error, nce is kfreed.
1876  */
1877 static int name_cache_insert(struct send_ctx *sctx,
1878                              struct name_cache_entry *nce)
1879 {
1880         int ret = 0;
1881         struct list_head *nce_head;
1882
1883         nce_head = radix_tree_lookup(&sctx->name_cache,
1884                         (unsigned long)nce->ino);
1885         if (!nce_head) {
1886                 nce_head = kmalloc(sizeof(*nce_head), GFP_NOFS);
1887                 if (!nce_head) {
1888                         kfree(nce);
1889                         return -ENOMEM;
1890                 }
1891                 INIT_LIST_HEAD(nce_head);
1892
1893                 ret = radix_tree_insert(&sctx->name_cache, nce->ino, nce_head);
1894                 if (ret < 0) {
1895                         kfree(nce_head);
1896                         kfree(nce);
1897                         return ret;
1898                 }
1899         }
1900         list_add_tail(&nce->radix_list, nce_head);
1901         list_add_tail(&nce->list, &sctx->name_cache_list);
1902         sctx->name_cache_size++;
1903
1904         return ret;
1905 }
1906
1907 static void name_cache_delete(struct send_ctx *sctx,
1908                               struct name_cache_entry *nce)
1909 {
1910         struct list_head *nce_head;
1911
1912         nce_head = radix_tree_lookup(&sctx->name_cache,
1913                         (unsigned long)nce->ino);
1914         if (!nce_head) {
1915                 btrfs_err(sctx->send_root->fs_info,
1916               "name_cache_delete lookup failed ino %llu cache size %d, leaking memory",
1917                         nce->ino, sctx->name_cache_size);
1918         }
1919
1920         list_del(&nce->radix_list);
1921         list_del(&nce->list);
1922         sctx->name_cache_size--;
1923
1924         /*
1925          * We may not get to the final release of nce_head if the lookup fails
1926          */
1927         if (nce_head && list_empty(nce_head)) {
1928                 radix_tree_delete(&sctx->name_cache, (unsigned long)nce->ino);
1929                 kfree(nce_head);
1930         }
1931 }
1932
1933 static struct name_cache_entry *name_cache_search(struct send_ctx *sctx,
1934                                                     u64 ino, u64 gen)
1935 {
1936         struct list_head *nce_head;
1937         struct name_cache_entry *cur;
1938
1939         nce_head = radix_tree_lookup(&sctx->name_cache, (unsigned long)ino);
1940         if (!nce_head)
1941                 return NULL;
1942
1943         list_for_each_entry(cur, nce_head, radix_list) {
1944                 if (cur->ino == ino && cur->gen == gen)
1945                         return cur;
1946         }
1947         return NULL;
1948 }
1949
1950 /*
1951  * Removes the entry from the list and adds it back to the end. This marks the
1952  * entry as recently used so that name_cache_clean_unused does not remove it.
1953  */
1954 static void name_cache_used(struct send_ctx *sctx, struct name_cache_entry *nce)
1955 {
1956         list_del(&nce->list);
1957         list_add_tail(&nce->list, &sctx->name_cache_list);
1958 }
1959
1960 /*
1961  * Remove some entries from the beginning of name_cache_list.
1962  */
1963 static void name_cache_clean_unused(struct send_ctx *sctx)
1964 {
1965         struct name_cache_entry *nce;
1966
1967         if (sctx->name_cache_size < SEND_CTX_NAME_CACHE_CLEAN_SIZE)
1968                 return;
1969
1970         while (sctx->name_cache_size > SEND_CTX_MAX_NAME_CACHE_SIZE) {
1971                 nce = list_entry(sctx->name_cache_list.next,
1972                                 struct name_cache_entry, list);
1973                 name_cache_delete(sctx, nce);
1974                 kfree(nce);
1975         }
1976 }
1977
1978 static void name_cache_free(struct send_ctx *sctx)
1979 {
1980         struct name_cache_entry *nce;
1981
1982         while (!list_empty(&sctx->name_cache_list)) {
1983                 nce = list_entry(sctx->name_cache_list.next,
1984                                 struct name_cache_entry, list);
1985                 name_cache_delete(sctx, nce);
1986                 kfree(nce);
1987         }
1988 }
1989
1990 /*
1991  * Used by get_cur_path for each ref up to the root.
1992  * Returns 0 if it succeeded.
1993  * Returns 1 if the inode is not existent or got overwritten. In that case, the
1994  * name is an orphan name. This instructs get_cur_path to stop iterating. If 1
1995  * is returned, parent_ino/parent_gen are not guaranteed to be valid.
1996  * Returns <0 in case of error.
1997  */
1998 static int __get_cur_name_and_parent(struct send_ctx *sctx,
1999                                      u64 ino, u64 gen,
2000                                      u64 *parent_ino,
2001                                      u64 *parent_gen,
2002                                      struct fs_path *dest)
2003 {
2004         int ret;
2005         int nce_ret;
2006         struct btrfs_path *path = NULL;
2007         struct name_cache_entry *nce = NULL;
2008
2009         /*
2010          * First check if we already did a call to this function with the same
2011          * ino/gen. If yes, check if the cache entry is still up-to-date. If yes
2012          * return the cached result.
2013          */
2014         nce = name_cache_search(sctx, ino, gen);
2015         if (nce) {
2016                 if (ino < sctx->send_progress && nce->need_later_update) {
2017                         name_cache_delete(sctx, nce);
2018                         kfree(nce);
2019                         nce = NULL;
2020                 } else {
2021                         name_cache_used(sctx, nce);
2022                         *parent_ino = nce->parent_ino;
2023                         *parent_gen = nce->parent_gen;
2024                         ret = fs_path_add(dest, nce->name, nce->name_len);
2025                         if (ret < 0)
2026                                 goto out;
2027                         ret = nce->ret;
2028                         goto out;
2029                 }
2030         }
2031
2032         path = alloc_path_for_send();
2033         if (!path)
2034                 return -ENOMEM;
2035
2036         /*
2037          * If the inode is not existent yet, add the orphan name and return 1.
2038          * This should only happen for the parent dir that we determine in
2039          * __record_new_ref
2040          */
2041         ret = is_inode_existent(sctx, ino, gen);
2042         if (ret < 0)
2043                 goto out;
2044
2045         if (!ret) {
2046                 ret = gen_unique_name(sctx, ino, gen, dest);
2047                 if (ret < 0)
2048                         goto out;
2049                 ret = 1;
2050                 goto out_cache;
2051         }
2052
2053         /*
2054          * Depending on whether the inode was already processed or not, use
2055          * send_root or parent_root for ref lookup.
2056          */
2057         if (ino < sctx->send_progress)
2058                 ret = get_first_ref(sctx->send_root, ino,
2059                                     parent_ino, parent_gen, dest);
2060         else
2061                 ret = get_first_ref(sctx->parent_root, ino,
2062                                     parent_ino, parent_gen, dest);
2063         if (ret < 0)
2064                 goto out;
2065
2066         /*
2067          * Check if the ref was overwritten by an inode's ref that was processed
2068          * earlier. If yes, treat as orphan and return 1.
2069          */
2070         ret = did_overwrite_ref(sctx, *parent_ino, *parent_gen, ino, gen,
2071                         dest->start, dest->end - dest->start);
2072         if (ret < 0)
2073                 goto out;
2074         if (ret) {
2075                 fs_path_reset(dest);
2076                 ret = gen_unique_name(sctx, ino, gen, dest);
2077                 if (ret < 0)
2078                         goto out;
2079                 ret = 1;
2080         }
2081
2082 out_cache:
2083         /*
2084          * Store the result of the lookup in the name cache.
2085          */
2086         nce = kmalloc(sizeof(*nce) + fs_path_len(dest) + 1, GFP_NOFS);
2087         if (!nce) {
2088                 ret = -ENOMEM;
2089                 goto out;
2090         }
2091
2092         nce->ino = ino;
2093         nce->gen = gen;
2094         nce->parent_ino = *parent_ino;
2095         nce->parent_gen = *parent_gen;
2096         nce->name_len = fs_path_len(dest);
2097         nce->ret = ret;
2098         strcpy(nce->name, dest->start);
2099
2100         if (ino < sctx->send_progress)
2101                 nce->need_later_update = 0;
2102         else
2103                 nce->need_later_update = 1;
2104
2105         nce_ret = name_cache_insert(sctx, nce);
2106         if (nce_ret < 0)
2107                 ret = nce_ret;
2108         name_cache_clean_unused(sctx);
2109
2110 out:
2111         btrfs_free_path(path);
2112         return ret;
2113 }
2114
2115 /*
2116  * Magic happens here. This function returns the first ref to an inode as it
2117  * would look like while receiving the stream at this point in time.
2118  * We walk the path up to the root. For every inode in between, we check if it
2119  * was already processed/sent. If yes, we continue with the parent as found
2120  * in send_root. If not, we continue with the parent as found in parent_root.
2121  * If we encounter an inode that was deleted at this point in time, we use the
2122  * inodes "orphan" name instead of the real name and stop. Same with new inodes
2123  * that were not created yet and overwritten inodes/refs.
2124  *
2125  * When do we have have orphan inodes:
2126  * 1. When an inode is freshly created and thus no valid refs are available yet
2127  * 2. When a directory lost all it's refs (deleted) but still has dir items
2128  *    inside which were not processed yet (pending for move/delete). If anyone
2129  *    tried to get the path to the dir items, it would get a path inside that
2130  *    orphan directory.
2131  * 3. When an inode is moved around or gets new links, it may overwrite the ref
2132  *    of an unprocessed inode. If in that case the first ref would be
2133  *    overwritten, the overwritten inode gets "orphanized". Later when we
2134  *    process this overwritten inode, it is restored at a new place by moving
2135  *    the orphan inode.
2136  *
2137  * sctx->send_progress tells this function at which point in time receiving
2138  * would be.
2139  */
2140 static int get_cur_path(struct send_ctx *sctx, u64 ino, u64 gen,
2141                         struct fs_path *dest)
2142 {
2143         int ret = 0;
2144         struct fs_path *name = NULL;
2145         u64 parent_inode = 0;
2146         u64 parent_gen = 0;
2147         int stop = 0;
2148
2149         name = fs_path_alloc();
2150         if (!name) {
2151                 ret = -ENOMEM;
2152                 goto out;
2153         }
2154
2155         dest->reversed = 1;
2156         fs_path_reset(dest);
2157
2158         while (!stop && ino != BTRFS_FIRST_FREE_OBJECTID) {
2159                 fs_path_reset(name);
2160
2161                 if (is_waiting_for_rm(sctx, ino)) {
2162                         ret = gen_unique_name(sctx, ino, gen, name);
2163                         if (ret < 0)
2164                                 goto out;
2165                         ret = fs_path_add_path(dest, name);
2166                         break;
2167                 }
2168
2169                 if (is_waiting_for_move(sctx, ino)) {
2170                         ret = get_first_ref(sctx->parent_root, ino,
2171                                             &parent_inode, &parent_gen, name);
2172                 } else {
2173                         ret = __get_cur_name_and_parent(sctx, ino, gen,
2174                                                         &parent_inode,
2175                                                         &parent_gen, name);
2176                         if (ret)
2177                                 stop = 1;
2178                 }
2179
2180                 if (ret < 0)
2181                         goto out;
2182
2183                 ret = fs_path_add_path(dest, name);
2184                 if (ret < 0)
2185                         goto out;
2186
2187                 ino = parent_inode;
2188                 gen = parent_gen;
2189         }
2190
2191 out:
2192         fs_path_free(name);
2193         if (!ret)
2194                 fs_path_unreverse(dest);
2195         return ret;
2196 }
2197
2198 /*
2199  * Sends a BTRFS_SEND_C_SUBVOL command/item to userspace
2200  */
2201 static int send_subvol_begin(struct send_ctx *sctx)
2202 {
2203         int ret;
2204         struct btrfs_root *send_root = sctx->send_root;
2205         struct btrfs_root *parent_root = sctx->parent_root;
2206         struct btrfs_path *path;
2207         struct btrfs_key key;
2208         struct btrfs_root_ref *ref;
2209         struct extent_buffer *leaf;
2210         char *name = NULL;
2211         int namelen;
2212
2213         path = btrfs_alloc_path();
2214         if (!path)
2215                 return -ENOMEM;
2216
2217         name = kmalloc(BTRFS_PATH_NAME_MAX, GFP_NOFS);
2218         if (!name) {
2219                 btrfs_free_path(path);
2220                 return -ENOMEM;
2221         }
2222
2223         key.objectid = send_root->objectid;
2224         key.type = BTRFS_ROOT_BACKREF_KEY;
2225         key.offset = 0;
2226
2227         ret = btrfs_search_slot_for_read(send_root->fs_info->tree_root,
2228                                 &key, path, 1, 0);
2229         if (ret < 0)
2230                 goto out;
2231         if (ret) {
2232                 ret = -ENOENT;
2233                 goto out;
2234         }
2235
2236         leaf = path->nodes[0];
2237         btrfs_item_key_to_cpu(leaf, &key, path->slots[0]);
2238         if (key.type != BTRFS_ROOT_BACKREF_KEY ||
2239             key.objectid != send_root->objectid) {
2240                 ret = -ENOENT;
2241                 goto out;
2242         }
2243         ref = btrfs_item_ptr(leaf, path->slots[0], struct btrfs_root_ref);
2244         namelen = btrfs_root_ref_name_len(leaf, ref);
2245         read_extent_buffer(leaf, name, (unsigned long)(ref + 1), namelen);
2246         btrfs_release_path(path);
2247
2248         if (parent_root) {
2249                 ret = begin_cmd(sctx, BTRFS_SEND_C_SNAPSHOT);
2250                 if (ret < 0)
2251                         goto out;
2252         } else {
2253                 ret = begin_cmd(sctx, BTRFS_SEND_C_SUBVOL);
2254                 if (ret < 0)
2255                         goto out;
2256         }
2257
2258         TLV_PUT_STRING(sctx, BTRFS_SEND_A_PATH, name, namelen);
2259         TLV_PUT_UUID(sctx, BTRFS_SEND_A_UUID,
2260                         sctx->send_root->root_item.uuid);
2261         TLV_PUT_U64(sctx, BTRFS_SEND_A_CTRANSID,
2262                     le64_to_cpu(sctx->send_root->root_item.ctransid));
2263         if (parent_root) {
2264                 TLV_PUT_UUID(sctx, BTRFS_SEND_A_CLONE_UUID,
2265                                 sctx->parent_root->root_item.uuid);
2266                 TLV_PUT_U64(sctx, BTRFS_SEND_A_CLONE_CTRANSID,
2267                             le64_to_cpu(sctx->parent_root->root_item.ctransid));
2268         }
2269
2270         ret = send_cmd(sctx);
2271
2272 tlv_put_failure:
2273 out:
2274         btrfs_free_path(path);
2275         kfree(name);
2276         return ret;
2277 }
2278
2279 static int send_truncate(struct send_ctx *sctx, u64 ino, u64 gen, u64 size)
2280 {
2281         int ret = 0;
2282         struct fs_path *p;
2283
2284 verbose_printk("btrfs: send_truncate %llu size=%llu\n", ino, size);
2285
2286         p = fs_path_alloc();
2287         if (!p)
2288                 return -ENOMEM;
2289
2290         ret = begin_cmd(sctx, BTRFS_SEND_C_TRUNCATE);
2291         if (ret < 0)
2292                 goto out;
2293
2294         ret = get_cur_path(sctx, ino, gen, p);
2295         if (ret < 0)
2296                 goto out;
2297         TLV_PUT_PATH(sctx, BTRFS_SEND_A_PATH, p);
2298         TLV_PUT_U64(sctx, BTRFS_SEND_A_SIZE, size);
2299
2300         ret = send_cmd(sctx);
2301
2302 tlv_put_failure:
2303 out:
2304         fs_path_free(p);
2305         return ret;
2306 }
2307
2308 static int send_chmod(struct send_ctx *sctx, u64 ino, u64 gen, u64 mode)
2309 {
2310         int ret = 0;
2311         struct fs_path *p;
2312
2313 verbose_printk("btrfs: send_chmod %llu mode=%llu\n", ino, mode);
2314
2315         p = fs_path_alloc();
2316         if (!p)
2317                 return -ENOMEM;
2318
2319         ret = begin_cmd(sctx, BTRFS_SEND_C_CHMOD);
2320         if (ret < 0)
2321                 goto out;
2322
2323         ret = get_cur_path(sctx, ino, gen, p);
2324         if (ret < 0)
2325                 goto out;
2326         TLV_PUT_PATH(sctx, BTRFS_SEND_A_PATH, p);
2327         TLV_PUT_U64(sctx, BTRFS_SEND_A_MODE, mode & 07777);
2328
2329         ret = send_cmd(sctx);
2330
2331 tlv_put_failure:
2332 out:
2333         fs_path_free(p);
2334         return ret;
2335 }
2336
2337 static int send_chown(struct send_ctx *sctx, u64 ino, u64 gen, u64 uid, u64 gid)
2338 {
2339         int ret = 0;
2340         struct fs_path *p;
2341
2342 verbose_printk("btrfs: send_chown %llu uid=%llu, gid=%llu\n", ino, uid, gid);
2343
2344         p = fs_path_alloc();
2345         if (!p)
2346                 return -ENOMEM;
2347
2348         ret = begin_cmd(sctx, BTRFS_SEND_C_CHOWN);
2349         if (ret < 0)
2350                 goto out;
2351
2352         ret = get_cur_path(sctx, ino, gen, p);
2353         if (ret < 0)
2354                 goto out;
2355         TLV_PUT_PATH(sctx, BTRFS_SEND_A_PATH, p);
2356         TLV_PUT_U64(sctx, BTRFS_SEND_A_UID, uid);
2357         TLV_PUT_U64(sctx, BTRFS_SEND_A_GID, gid);
2358
2359         ret = send_cmd(sctx);
2360
2361 tlv_put_failure:
2362 out:
2363         fs_path_free(p);
2364         return ret;
2365 }
2366
2367 static int send_utimes(struct send_ctx *sctx, u64 ino, u64 gen)
2368 {
2369         int ret = 0;
2370         struct fs_path *p = NULL;
2371         struct btrfs_inode_item *ii;
2372         struct btrfs_path *path = NULL;
2373         struct extent_buffer *eb;
2374         struct btrfs_key key;
2375         int slot;
2376
2377 verbose_printk("btrfs: send_utimes %llu\n", ino);
2378
2379         p = fs_path_alloc();
2380         if (!p)
2381                 return -ENOMEM;
2382
2383         path = alloc_path_for_send();
2384         if (!path) {
2385                 ret = -ENOMEM;
2386                 goto out;
2387         }
2388
2389         key.objectid = ino;
2390         key.type = BTRFS_INODE_ITEM_KEY;
2391         key.offset = 0;
2392         ret = btrfs_search_slot(NULL, sctx->send_root, &key, path, 0, 0);
2393         if (ret < 0)
2394                 goto out;
2395
2396         eb = path->nodes[0];
2397         slot = path->slots[0];
2398         ii = btrfs_item_ptr(eb, slot, struct btrfs_inode_item);
2399
2400         ret = begin_cmd(sctx, BTRFS_SEND_C_UTIMES);
2401         if (ret < 0)
2402                 goto out;
2403
2404         ret = get_cur_path(sctx, ino, gen, p);
2405         if (ret < 0)
2406                 goto out;
2407         TLV_PUT_PATH(sctx, BTRFS_SEND_A_PATH, p);
2408         TLV_PUT_BTRFS_TIMESPEC(sctx, BTRFS_SEND_A_ATIME, eb,
2409                         btrfs_inode_atime(ii));
2410         TLV_PUT_BTRFS_TIMESPEC(sctx, BTRFS_SEND_A_MTIME, eb,
2411                         btrfs_inode_mtime(ii));
2412         TLV_PUT_BTRFS_TIMESPEC(sctx, BTRFS_SEND_A_CTIME, eb,
2413                         btrfs_inode_ctime(ii));
2414         /* TODO Add otime support when the otime patches get into upstream */
2415
2416         ret = send_cmd(sctx);
2417
2418 tlv_put_failure:
2419 out:
2420         fs_path_free(p);
2421         btrfs_free_path(path);
2422         return ret;
2423 }
2424
2425 /*
2426  * Sends a BTRFS_SEND_C_MKXXX or SYMLINK command to user space. We don't have
2427  * a valid path yet because we did not process the refs yet. So, the inode
2428  * is created as orphan.
2429  */
2430 static int send_create_inode(struct send_ctx *sctx, u64 ino)
2431 {
2432         int ret = 0;
2433         struct fs_path *p;
2434         int cmd;
2435         u64 gen;
2436         u64 mode;
2437         u64 rdev;
2438
2439 verbose_printk("btrfs: send_create_inode %llu\n", ino);
2440
2441         p = fs_path_alloc();
2442         if (!p)
2443                 return -ENOMEM;
2444
2445         if (ino != sctx->cur_ino) {
2446                 ret = get_inode_info(sctx->send_root, ino, NULL, &gen, &mode,
2447                                      NULL, NULL, &rdev);
2448                 if (ret < 0)
2449                         goto out;
2450         } else {
2451                 gen = sctx->cur_inode_gen;
2452                 mode = sctx->cur_inode_mode;
2453                 rdev = sctx->cur_inode_rdev;
2454         }
2455
2456         if (S_ISREG(mode)) {
2457                 cmd = BTRFS_SEND_C_MKFILE;
2458         } else if (S_ISDIR(mode)) {
2459                 cmd = BTRFS_SEND_C_MKDIR;
2460         } else if (S_ISLNK(mode)) {
2461                 cmd = BTRFS_SEND_C_SYMLINK;
2462         } else if (S_ISCHR(mode) || S_ISBLK(mode)) {
2463                 cmd = BTRFS_SEND_C_MKNOD;
2464         } else if (S_ISFIFO(mode)) {
2465                 cmd = BTRFS_SEND_C_MKFIFO;
2466         } else if (S_ISSOCK(mode)) {
2467                 cmd = BTRFS_SEND_C_MKSOCK;
2468         } else {
2469                 printk(KERN_WARNING "btrfs: unexpected inode type %o",
2470                                 (int)(mode & S_IFMT));
2471                 ret = -ENOTSUPP;
2472                 goto out;
2473         }
2474
2475         ret = begin_cmd(sctx, cmd);
2476         if (ret < 0)
2477                 goto out;
2478
2479         ret = gen_unique_name(sctx, ino, gen, p);
2480         if (ret < 0)
2481                 goto out;
2482
2483         TLV_PUT_PATH(sctx, BTRFS_SEND_A_PATH, p);
2484         TLV_PUT_U64(sctx, BTRFS_SEND_A_INO, ino);
2485
2486         if (S_ISLNK(mode)) {
2487                 fs_path_reset(p);
2488                 ret = read_symlink(sctx->send_root, ino, p);
2489                 if (ret < 0)
2490                         goto out;
2491                 TLV_PUT_PATH(sctx, BTRFS_SEND_A_PATH_LINK, p);
2492         } else if (S_ISCHR(mode) || S_ISBLK(mode) ||
2493                    S_ISFIFO(mode) || S_ISSOCK(mode)) {
2494                 TLV_PUT_U64(sctx, BTRFS_SEND_A_RDEV, new_encode_dev(rdev));
2495                 TLV_PUT_U64(sctx, BTRFS_SEND_A_MODE, mode);
2496         }
2497
2498         ret = send_cmd(sctx);
2499         if (ret < 0)
2500                 goto out;
2501
2502
2503 tlv_put_failure:
2504 out:
2505         fs_path_free(p);
2506         return ret;
2507 }
2508
2509 /*
2510  * We need some special handling for inodes that get processed before the parent
2511  * directory got created. See process_recorded_refs for details.
2512  * This function does the check if we already created the dir out of order.
2513  */
2514 static int did_create_dir(struct send_ctx *sctx, u64 dir)
2515 {
2516         int ret = 0;
2517         struct btrfs_path *path = NULL;
2518         struct btrfs_key key;
2519         struct btrfs_key found_key;
2520         struct btrfs_key di_key;
2521         struct extent_buffer *eb;
2522         struct btrfs_dir_item *di;
2523         int slot;
2524
2525         path = alloc_path_for_send();
2526         if (!path) {
2527                 ret = -ENOMEM;
2528                 goto out;
2529         }
2530
2531         key.objectid = dir;
2532         key.type = BTRFS_DIR_INDEX_KEY;
2533         key.offset = 0;
2534         ret = btrfs_search_slot(NULL, sctx->send_root, &key, path, 0, 0);
2535         if (ret < 0)
2536                 goto out;
2537
2538         while (1) {
2539                 eb = path->nodes[0];
2540                 slot = path->slots[0];
2541                 if (slot >= btrfs_header_nritems(eb)) {
2542                         ret = btrfs_next_leaf(sctx->send_root, path);
2543                         if (ret < 0) {
2544                                 goto out;
2545                         } else if (ret > 0) {
2546                                 ret = 0;
2547                                 break;
2548                         }
2549                         continue;
2550                 }
2551
2552                 btrfs_item_key_to_cpu(eb, &found_key, slot);
2553                 if (found_key.objectid != key.objectid ||
2554                     found_key.type != key.type) {
2555                         ret = 0;
2556                         goto out;
2557                 }
2558
2559                 di = btrfs_item_ptr(eb, slot, struct btrfs_dir_item);
2560                 btrfs_dir_item_key_to_cpu(eb, di, &di_key);
2561
2562                 if (di_key.type != BTRFS_ROOT_ITEM_KEY &&
2563                     di_key.objectid < sctx->send_progress) {
2564                         ret = 1;
2565                         goto out;
2566                 }
2567
2568                 path->slots[0]++;
2569         }
2570
2571 out:
2572         btrfs_free_path(path);
2573         return ret;
2574 }
2575
2576 /*
2577  * Only creates the inode if it is:
2578  * 1. Not a directory
2579  * 2. Or a directory which was not created already due to out of order
2580  *    directories. See did_create_dir and process_recorded_refs for details.
2581  */
2582 static int send_create_inode_if_needed(struct send_ctx *sctx)
2583 {
2584         int ret;
2585
2586         if (S_ISDIR(sctx->cur_inode_mode)) {
2587                 ret = did_create_dir(sctx, sctx->cur_ino);
2588                 if (ret < 0)
2589                         goto out;
2590                 if (ret) {
2591                         ret = 0;
2592                         goto out;
2593                 }
2594         }
2595
2596         ret = send_create_inode(sctx, sctx->cur_ino);
2597         if (ret < 0)
2598                 goto out;
2599
2600 out:
2601         return ret;
2602 }
2603
2604 struct recorded_ref {
2605         struct list_head list;
2606         char *dir_path;
2607         char *name;
2608         struct fs_path *full_path;
2609         u64 dir;
2610         u64 dir_gen;
2611         int dir_path_len;
2612         int name_len;
2613 };
2614
2615 /*
2616  * We need to process new refs before deleted refs, but compare_tree gives us
2617  * everything mixed. So we first record all refs and later process them.
2618  * This function is a helper to record one ref.
2619  */
2620 static int __record_ref(struct list_head *head, u64 dir,
2621                       u64 dir_gen, struct fs_path *path)
2622 {
2623         struct recorded_ref *ref;
2624
2625         ref = kmalloc(sizeof(*ref), GFP_NOFS);
2626         if (!ref)
2627                 return -ENOMEM;
2628
2629         ref->dir = dir;
2630         ref->dir_gen = dir_gen;
2631         ref->full_path = path;
2632
2633         ref->name = (char *)kbasename(ref->full_path->start);
2634         ref->name_len = ref->full_path->end - ref->name;
2635         ref->dir_path = ref->full_path->start;
2636         if (ref->name == ref->full_path->start)
2637                 ref->dir_path_len = 0;
2638         else
2639                 ref->dir_path_len = ref->full_path->end -
2640                                 ref->full_path->start - 1 - ref->name_len;
2641
2642         list_add_tail(&ref->list, head);
2643         return 0;
2644 }
2645
2646 static int dup_ref(struct recorded_ref *ref, struct list_head *list)
2647 {
2648         struct recorded_ref *new;
2649
2650         new = kmalloc(sizeof(*ref), GFP_NOFS);
2651         if (!new)
2652                 return -ENOMEM;
2653
2654         new->dir = ref->dir;
2655         new->dir_gen = ref->dir_gen;
2656         new->full_path = NULL;
2657         INIT_LIST_HEAD(&new->list);
2658         list_add_tail(&new->list, list);
2659         return 0;
2660 }
2661
2662 static void __free_recorded_refs(struct list_head *head)
2663 {
2664         struct recorded_ref *cur;
2665
2666         while (!list_empty(head)) {
2667                 cur = list_entry(head->next, struct recorded_ref, list);
2668                 fs_path_free(cur->full_path);
2669                 list_del(&cur->list);
2670                 kfree(cur);
2671         }
2672 }
2673
2674 static void free_recorded_refs(struct send_ctx *sctx)
2675 {
2676         __free_recorded_refs(&sctx->new_refs);
2677         __free_recorded_refs(&sctx->deleted_refs);
2678 }
2679
2680 /*
2681  * Renames/moves a file/dir to its orphan name. Used when the first
2682  * ref of an unprocessed inode gets overwritten and for all non empty
2683  * directories.
2684  */
2685 static int orphanize_inode(struct send_ctx *sctx, u64 ino, u64 gen,
2686                           struct fs_path *path)
2687 {
2688         int ret;
2689         struct fs_path *orphan;
2690
2691         orphan = fs_path_alloc();
2692         if (!orphan)
2693                 return -ENOMEM;
2694
2695         ret = gen_unique_name(sctx, ino, gen, orphan);
2696         if (ret < 0)
2697                 goto out;
2698
2699         ret = send_rename(sctx, path, orphan);
2700
2701 out:
2702         fs_path_free(orphan);
2703         return ret;
2704 }
2705
2706 static struct orphan_dir_info *
2707 add_orphan_dir_info(struct send_ctx *sctx, u64 dir_ino)
2708 {
2709         struct rb_node **p = &sctx->orphan_dirs.rb_node;
2710         struct rb_node *parent = NULL;
2711         struct orphan_dir_info *entry, *odi;
2712
2713         odi = kmalloc(sizeof(*odi), GFP_NOFS);
2714         if (!odi)
2715                 return ERR_PTR(-ENOMEM);
2716         odi->ino = dir_ino;
2717         odi->gen = 0;
2718
2719         while (*p) {
2720                 parent = *p;
2721                 entry = rb_entry(parent, struct orphan_dir_info, node);
2722                 if (dir_ino < entry->ino) {
2723                         p = &(*p)->rb_left;
2724                 } else if (dir_ino > entry->ino) {
2725                         p = &(*p)->rb_right;
2726                 } else {
2727                         kfree(odi);
2728                         return entry;
2729                 }
2730         }
2731
2732         rb_link_node(&odi->node, parent, p);
2733         rb_insert_color(&odi->node, &sctx->orphan_dirs);
2734         return odi;
2735 }
2736
2737 static struct orphan_dir_info *
2738 get_orphan_dir_info(struct send_ctx *sctx, u64 dir_ino)
2739 {
2740         struct rb_node *n = sctx->orphan_dirs.rb_node;
2741         struct orphan_dir_info *entry;
2742
2743         while (n) {
2744                 entry = rb_entry(n, struct orphan_dir_info, node);
2745                 if (dir_ino < entry->ino)
2746                         n = n->rb_left;
2747                 else if (dir_ino > entry->ino)
2748                         n = n->rb_right;
2749                 else
2750                         return entry;
2751         }
2752         return NULL;
2753 }
2754
2755 static int is_waiting_for_rm(struct send_ctx *sctx, u64 dir_ino)
2756 {
2757         struct orphan_dir_info *odi = get_orphan_dir_info(sctx, dir_ino);
2758
2759         return odi != NULL;
2760 }
2761
2762 static void free_orphan_dir_info(struct send_ctx *sctx,
2763                                  struct orphan_dir_info *odi)
2764 {
2765         if (!odi)
2766                 return;
2767         rb_erase(&odi->node, &sctx->orphan_dirs);
2768         kfree(odi);
2769 }
2770
2771 /*
2772  * Returns 1 if a directory can be removed at this point in time.
2773  * We check this by iterating all dir items and checking if the inode behind
2774  * the dir item was already processed.
2775  */
2776 static int can_rmdir(struct send_ctx *sctx, u64 dir, u64 dir_gen,
2777                      u64 send_progress)
2778 {
2779         int ret = 0;
2780         struct btrfs_root *root = sctx->parent_root;
2781         struct btrfs_path *path;
2782         struct btrfs_key key;
2783         struct btrfs_key found_key;
2784         struct btrfs_key loc;
2785         struct btrfs_dir_item *di;
2786
2787         /*
2788          * Don't try to rmdir the top/root subvolume dir.
2789          */
2790         if (dir == BTRFS_FIRST_FREE_OBJECTID)
2791                 return 0;
2792
2793         path = alloc_path_for_send();
2794         if (!path)
2795                 return -ENOMEM;
2796
2797         key.objectid = dir;
2798         key.type = BTRFS_DIR_INDEX_KEY;
2799         key.offset = 0;
2800         ret = btrfs_search_slot(NULL, root, &key, path, 0, 0);
2801         if (ret < 0)
2802                 goto out;
2803
2804         while (1) {
2805                 struct waiting_dir_move *dm;
2806
2807                 if (path->slots[0] >= btrfs_header_nritems(path->nodes[0])) {
2808                         ret = btrfs_next_leaf(root, path);
2809                         if (ret < 0)
2810                                 goto out;
2811                         else if (ret > 0)
2812                                 break;
2813                         continue;
2814                 }
2815                 btrfs_item_key_to_cpu(path->nodes[0], &found_key,
2816                                       path->slots[0]);
2817                 if (found_key.objectid != key.objectid ||
2818                     found_key.type != key.type)
2819                         break;
2820
2821                 di = btrfs_item_ptr(path->nodes[0], path->slots[0],
2822                                 struct btrfs_dir_item);
2823                 btrfs_dir_item_key_to_cpu(path->nodes[0], di, &loc);
2824
2825                 dm = get_waiting_dir_move(sctx, loc.objectid);
2826                 if (dm) {
2827                         struct orphan_dir_info *odi;
2828
2829                         odi = add_orphan_dir_info(sctx, dir);
2830                         if (IS_ERR(odi)) {
2831                                 ret = PTR_ERR(odi);
2832                                 goto out;
2833                         }
2834                         odi->gen = dir_gen;
2835                         dm->rmdir_ino = dir;
2836                         ret = 0;
2837                         goto out;
2838                 }
2839
2840                 if (loc.objectid > send_progress) {
2841                         ret = 0;
2842                         goto out;
2843                 }
2844
2845                 path->slots[0]++;
2846         }
2847
2848         ret = 1;
2849
2850 out:
2851         btrfs_free_path(path);
2852         return ret;
2853 }
2854
2855 static int is_waiting_for_move(struct send_ctx *sctx, u64 ino)
2856 {
2857         struct waiting_dir_move *entry = get_waiting_dir_move(sctx, ino);
2858
2859         return entry != NULL;
2860 }
2861
2862 static int add_waiting_dir_move(struct send_ctx *sctx, u64 ino)
2863 {
2864         struct rb_node **p = &sctx->waiting_dir_moves.rb_node;
2865         struct rb_node *parent = NULL;
2866         struct waiting_dir_move *entry, *dm;
2867
2868         dm = kmalloc(sizeof(*dm), GFP_NOFS);
2869         if (!dm)
2870                 return -ENOMEM;
2871         dm->ino = ino;
2872         dm->rmdir_ino = 0;
2873
2874         while (*p) {
2875                 parent = *p;
2876                 entry = rb_entry(parent, struct waiting_dir_move, node);
2877                 if (ino < entry->ino) {
2878                         p = &(*p)->rb_left;
2879                 } else if (ino > entry->ino) {
2880                         p = &(*p)->rb_right;
2881                 } else {
2882                         kfree(dm);
2883                         return -EEXIST;
2884                 }
2885         }
2886
2887         rb_link_node(&dm->node, parent, p);
2888         rb_insert_color(&dm->node, &sctx->waiting_dir_moves);
2889         return 0;
2890 }
2891
2892 static struct waiting_dir_move *
2893 get_waiting_dir_move(struct send_ctx *sctx, u64 ino)
2894 {
2895         struct rb_node *n = sctx->waiting_dir_moves.rb_node;
2896         struct waiting_dir_move *entry;
2897
2898         while (n) {
2899                 entry = rb_entry(n, struct waiting_dir_move, node);
2900                 if (ino < entry->ino)
2901                         n = n->rb_left;
2902                 else if (ino > entry->ino)
2903                         n = n->rb_right;
2904                 else
2905                         return entry;
2906         }
2907         return NULL;
2908 }
2909
2910 static void free_waiting_dir_move(struct send_ctx *sctx,
2911                                   struct waiting_dir_move *dm)
2912 {
2913         if (!dm)
2914                 return;
2915         rb_erase(&dm->node, &sctx->waiting_dir_moves);
2916         kfree(dm);
2917 }
2918
2919 static int add_pending_dir_move(struct send_ctx *sctx,
2920                                 u64 ino,
2921                                 u64 ino_gen,
2922                                 u64 parent_ino)
2923 {
2924         struct rb_node **p = &sctx->pending_dir_moves.rb_node;
2925         struct rb_node *parent = NULL;
2926         struct pending_dir_move *entry, *pm;
2927         struct recorded_ref *cur;
2928         int exists = 0;
2929         int ret;
2930
2931         pm = kmalloc(sizeof(*pm), GFP_NOFS);
2932         if (!pm)
2933                 return -ENOMEM;
2934         pm->parent_ino = parent_ino;
2935         pm->ino = ino;
2936         pm->gen = ino_gen;
2937         INIT_LIST_HEAD(&pm->list);
2938         INIT_LIST_HEAD(&pm->update_refs);
2939         RB_CLEAR_NODE(&pm->node);
2940
2941         while (*p) {
2942                 parent = *p;
2943                 entry = rb_entry(parent, struct pending_dir_move, node);
2944                 if (parent_ino < entry->parent_ino) {
2945                         p = &(*p)->rb_left;
2946                 } else if (parent_ino > entry->parent_ino) {
2947                         p = &(*p)->rb_right;
2948                 } else {
2949                         exists = 1;
2950                         break;
2951                 }
2952         }
2953
2954         list_for_each_entry(cur, &sctx->deleted_refs, list) {
2955                 ret = dup_ref(cur, &pm->update_refs);
2956                 if (ret < 0)
2957                         goto out;
2958         }
2959         list_for_each_entry(cur, &sctx->new_refs, list) {
2960                 ret = dup_ref(cur, &pm->update_refs);
2961                 if (ret < 0)
2962                         goto out;
2963         }
2964
2965         ret = add_waiting_dir_move(sctx, pm->ino);
2966         if (ret)
2967                 goto out;
2968
2969         if (exists) {
2970                 list_add_tail(&pm->list, &entry->list);
2971         } else {
2972                 rb_link_node(&pm->node, parent, p);
2973                 rb_insert_color(&pm->node, &sctx->pending_dir_moves);
2974         }
2975         ret = 0;
2976 out:
2977         if (ret) {
2978                 __free_recorded_refs(&pm->update_refs);
2979                 kfree(pm);
2980         }
2981         return ret;
2982 }
2983
2984 static struct pending_dir_move *get_pending_dir_moves(struct send_ctx *sctx,
2985                                                       u64 parent_ino)
2986 {
2987         struct rb_node *n = sctx->pending_dir_moves.rb_node;
2988         struct pending_dir_move *entry;
2989
2990         while (n) {
2991                 entry = rb_entry(n, struct pending_dir_move, node);
2992                 if (parent_ino < entry->parent_ino)
2993                         n = n->rb_left;
2994                 else if (parent_ino > entry->parent_ino)
2995                         n = n->rb_right;
2996                 else
2997                         return entry;
2998         }
2999         return NULL;
3000 }
3001
3002 static int apply_dir_move(struct send_ctx *sctx, struct pending_dir_move *pm)
3003 {
3004         struct fs_path *from_path = NULL;
3005         struct fs_path *to_path = NULL;
3006         struct fs_path *name = NULL;
3007         u64 orig_progress = sctx->send_progress;
3008         struct recorded_ref *cur;
3009         u64 parent_ino, parent_gen;
3010         struct waiting_dir_move *dm = NULL;
3011         u64 rmdir_ino = 0;
3012         int ret;
3013
3014         name = fs_path_alloc();
3015         from_path = fs_path_alloc();
3016         if (!name || !from_path) {
3017                 ret = -ENOMEM;
3018                 goto out;
3019         }
3020
3021         dm = get_waiting_dir_move(sctx, pm->ino);
3022         ASSERT(dm);
3023         rmdir_ino = dm->rmdir_ino;
3024         free_waiting_dir_move(sctx, dm);
3025
3026         ret = get_first_ref(sctx->parent_root, pm->ino,
3027                             &parent_ino, &parent_gen, name);
3028         if (ret < 0)
3029                 goto out;
3030
3031         if (parent_ino == sctx->cur_ino) {
3032                 /* child only renamed, not moved */
3033                 ASSERT(parent_gen == sctx->cur_inode_gen);
3034                 ret = get_cur_path(sctx, sctx->cur_ino, sctx->cur_inode_gen,
3035                                    from_path);
3036                 if (ret < 0)
3037                         goto out;
3038                 ret = fs_path_add_path(from_path, name);
3039                 if (ret < 0)
3040                         goto out;
3041         } else {
3042                 /* child moved and maybe renamed too */
3043                 sctx->send_progress = pm->ino;
3044                 ret = get_cur_path(sctx, pm->ino, pm->gen, from_path);
3045                 if (ret < 0)
3046                         goto out;
3047         }
3048
3049         fs_path_free(name);
3050         name = NULL;
3051
3052         to_path = fs_path_alloc();
3053         if (!to_path) {
3054                 ret = -ENOMEM;
3055                 goto out;
3056         }
3057
3058         sctx->send_progress = sctx->cur_ino + 1;
3059         ret = get_cur_path(sctx, pm->ino, pm->gen, to_path);
3060         if (ret < 0)
3061                 goto out;
3062
3063         ret = send_rename(sctx, from_path, to_path);
3064         if (ret < 0)
3065                 goto out;
3066
3067         if (rmdir_ino) {
3068                 struct orphan_dir_info *odi;
3069
3070                 odi = get_orphan_dir_info(sctx, rmdir_ino);
3071                 if (!odi) {
3072                         /* already deleted */
3073                         goto finish;
3074                 }
3075                 ret = can_rmdir(sctx, rmdir_ino, odi->gen, sctx->cur_ino + 1);
3076                 if (ret < 0)
3077                         goto out;
3078                 if (!ret)
3079                         goto finish;
3080
3081                 name = fs_path_alloc();
3082                 if (!name) {
3083                         ret = -ENOMEM;
3084                         goto out;
3085                 }
3086                 ret = get_cur_path(sctx, rmdir_ino, odi->gen, name);
3087                 if (ret < 0)
3088                         goto out;
3089                 ret = send_rmdir(sctx, name);
3090                 if (ret < 0)
3091                         goto out;
3092                 free_orphan_dir_info(sctx, odi);
3093         }
3094
3095 finish:
3096         ret = send_utimes(sctx, pm->ino, pm->gen);
3097         if (ret < 0)
3098                 goto out;
3099
3100         /*
3101          * After rename/move, need to update the utimes of both new parent(s)
3102          * and old parent(s).
3103          */
3104         list_for_each_entry(cur, &pm->update_refs, list) {
3105                 if (cur->dir == rmdir_ino)
3106                         continue;
3107                 ret = send_utimes(sctx, cur->dir, cur->dir_gen);
3108                 if (ret < 0)
3109                         goto out;
3110         }
3111
3112 out:
3113         fs_path_free(name);
3114         fs_path_free(from_path);
3115         fs_path_free(to_path);
3116         sctx->send_progress = orig_progress;
3117
3118         return ret;
3119 }
3120
3121 static void free_pending_move(struct send_ctx *sctx, struct pending_dir_move *m)
3122 {
3123         if (!list_empty(&m->list))
3124                 list_del(&m->list);
3125         if (!RB_EMPTY_NODE(&m->node))
3126                 rb_erase(&m->node, &sctx->pending_dir_moves);
3127         __free_recorded_refs(&m->update_refs);
3128         kfree(m);
3129 }
3130
3131 static void tail_append_pending_moves(struct pending_dir_move *moves,
3132                                       struct list_head *stack)
3133 {
3134         if (list_empty(&moves->list)) {
3135                 list_add_tail(&moves->list, stack);
3136         } else {
3137                 LIST_HEAD(list);
3138                 list_splice_init(&moves->list, &list);
3139                 list_add_tail(&moves->list, stack);
3140                 list_splice_tail(&list, stack);
3141         }
3142 }
3143
3144 static int apply_children_dir_moves(struct send_ctx *sctx)
3145 {
3146         struct pending_dir_move *pm;
3147         struct list_head stack;
3148         u64 parent_ino = sctx->cur_ino;
3149         int ret = 0;
3150
3151         pm = get_pending_dir_moves(sctx, parent_ino);
3152         if (!pm)
3153                 return 0;
3154
3155         INIT_LIST_HEAD(&stack);
3156         tail_append_pending_moves(pm, &stack);
3157
3158         while (!list_empty(&stack)) {
3159                 pm = list_first_entry(&stack, struct pending_dir_move, list);
3160                 parent_ino = pm->ino;
3161                 ret = apply_dir_move(sctx, pm);
3162                 free_pending_move(sctx, pm);
3163                 if (ret)
3164                         goto out;
3165                 pm = get_pending_dir_moves(sctx, parent_ino);
3166                 if (pm)
3167                         tail_append_pending_moves(pm, &stack);
3168         }
3169         return 0;
3170
3171 out:
3172         while (!list_empty(&stack)) {
3173                 pm = list_first_entry(&stack, struct pending_dir_move, list);
3174                 free_pending_move(sctx, pm);
3175         }
3176         return ret;
3177 }
3178
3179 static int wait_for_parent_move(struct send_ctx *sctx,
3180                                 struct recorded_ref *parent_ref)
3181 {
3182         int ret;
3183         u64 ino = parent_ref->dir;
3184         u64 parent_ino_before, parent_ino_after;
3185         u64 old_gen;
3186         struct fs_path *path_before = NULL;
3187         struct fs_path *path_after = NULL;
3188         int len1, len2;
3189         int register_upper_dirs;
3190         u64 gen;
3191
3192         if (is_waiting_for_move(sctx, ino))
3193                 return 1;
3194
3195         if (parent_ref->dir <= sctx->cur_ino)
3196                 return 0;
3197
3198         ret = get_inode_info(sctx->parent_root, ino, NULL, &old_gen,
3199                              NULL, NULL, NULL, NULL);
3200         if (ret == -ENOENT)
3201                 return 0;
3202         else if (ret < 0)
3203                 return ret;
3204
3205         if (parent_ref->dir_gen != old_gen)
3206                 return 0;
3207
3208         path_before = fs_path_alloc();
3209         if (!path_before)
3210                 return -ENOMEM;
3211
3212         ret = get_first_ref(sctx->parent_root, ino, &parent_ino_before,
3213                             NULL, path_before);
3214         if (ret == -ENOENT) {
3215                 ret = 0;
3216                 goto out;
3217         } else if (ret < 0) {
3218                 goto out;
3219         }
3220
3221         path_after = fs_path_alloc();
3222         if (!path_after) {
3223                 ret = -ENOMEM;
3224                 goto out;
3225         }
3226
3227         ret = get_first_ref(sctx->send_root, ino, &parent_ino_after,
3228                             &gen, path_after);
3229         if (ret == -ENOENT) {
3230                 ret = 0;
3231                 goto out;
3232         } else if (ret < 0) {
3233                 goto out;
3234         }
3235
3236         len1 = fs_path_len(path_before);
3237         len2 = fs_path_len(path_after);
3238         if (parent_ino_before != parent_ino_after || len1 != len2 ||
3239              memcmp(path_before->start, path_after->start, len1)) {
3240                 ret = 1;
3241                 goto out;
3242         }
3243         ret = 0;
3244
3245         /*
3246          * Ok, our new most direct ancestor has a higher inode number but
3247          * wasn't moved/renamed. So maybe some of the new ancestors higher in
3248          * the hierarchy have an higher inode number too *and* were renamed
3249          * or moved - in this case we need to wait for the ancestor's rename
3250          * or move operation before we can do the move/rename for the current
3251          * inode.
3252          */
3253         register_upper_dirs = 0;
3254         ino = parent_ino_after;
3255 again:
3256         while ((ret == 0 || register_upper_dirs) && ino > sctx->cur_ino) {
3257                 u64 parent_gen;
3258
3259                 fs_path_reset(path_before);
3260                 fs_path_reset(path_after);
3261
3262                 ret = get_first_ref(sctx->send_root, ino, &parent_ino_after,
3263                                     &parent_gen, path_after);
3264                 if (ret < 0)
3265                         goto out;
3266                 ret = get_first_ref(sctx->parent_root, ino, &parent_ino_before,
3267                                     NULL, path_before);
3268                 if (ret == -ENOENT) {
3269                         ret = 0;
3270                         break;
3271                 } else if (ret < 0) {
3272                         goto out;
3273                 }
3274
3275                 len1 = fs_path_len(path_before);
3276                 len2 = fs_path_len(path_after);
3277                 if (parent_ino_before != parent_ino_after || len1 != len2 ||
3278                     memcmp(path_before->start, path_after->start, len1)) {
3279                         ret = 1;
3280                         if (register_upper_dirs) {
3281                                 break;
3282                         } else {
3283                                 register_upper_dirs = 1;
3284                                 ino = parent_ref->dir;
3285                                 gen = parent_ref->dir_gen;
3286                                 goto again;
3287                         }
3288                 } else if (register_upper_dirs) {
3289                         ret = add_pending_dir_move(sctx, ino, gen,
3290                                                    parent_ino_after);
3291                         if (ret < 0 && ret != -EEXIST)
3292                                 goto out;
3293                 }
3294
3295                 ino = parent_ino_after;
3296                 gen = parent_gen;
3297         }
3298
3299 out:
3300         fs_path_free(path_before);
3301         fs_path_free(path_after);
3302
3303         return ret;
3304 }
3305
3306 /*
3307  * This does all the move/link/unlink/rmdir magic.
3308  */
3309 static int process_recorded_refs(struct send_ctx *sctx, int *pending_move)
3310 {
3311         int ret = 0;
3312         struct recorded_ref *cur;
3313         struct recorded_ref *cur2;
3314         struct list_head check_dirs;
3315         struct fs_path *valid_path = NULL;
3316         u64 ow_inode = 0;
3317         u64 ow_gen;
3318         int did_overwrite = 0;
3319         int is_orphan = 0;
3320         u64 last_dir_ino_rm = 0;
3321
3322 verbose_printk("btrfs: process_recorded_refs %llu\n", sctx->cur_ino);
3323
3324         /*
3325          * This should never happen as the root dir always has the same ref
3326          * which is always '..'
3327          */
3328         BUG_ON(sctx->cur_ino <= BTRFS_FIRST_FREE_OBJECTID);
3329         INIT_LIST_HEAD(&check_dirs);
3330
3331         valid_path = fs_path_alloc();
3332         if (!valid_path) {
3333                 ret = -ENOMEM;
3334                 goto out;
3335         }
3336
3337         /*
3338          * First, check if the first ref of the current inode was overwritten
3339          * before. If yes, we know that the current inode was already orphanized
3340          * and thus use the orphan name. If not, we can use get_cur_path to
3341          * get the path of the first ref as it would like while receiving at
3342          * this point in time.
3343          * New inodes are always orphan at the beginning, so force to use the
3344          * orphan name in this case.
3345          * The first ref is stored in valid_path and will be updated if it
3346          * gets moved around.
3347          */
3348         if (!sctx->cur_inode_new) {
3349                 ret = did_overwrite_first_ref(sctx, sctx->cur_ino,
3350                                 sctx->cur_inode_gen);
3351                 if (ret < 0)
3352                         goto out;
3353                 if (ret)
3354                         did_overwrite = 1;
3355         }
3356         if (sctx->cur_inode_new || did_overwrite) {
3357                 ret = gen_unique_name(sctx, sctx->cur_ino,
3358                                 sctx->cur_inode_gen, valid_path);
3359                 if (ret < 0)
3360                         goto out;
3361                 is_orphan = 1;
3362         } else {
3363                 ret = get_cur_path(sctx, sctx->cur_ino, sctx->cur_inode_gen,
3364                                 valid_path);
3365                 if (ret < 0)
3366                         goto out;
3367         }
3368
3369         list_for_each_entry(cur, &sctx->new_refs, list) {
3370                 /*
3371                  * We may have refs where the parent directory does not exist
3372                  * yet. This happens if the parent directories inum is higher
3373                  * the the current inum. To handle this case, we create the
3374                  * parent directory out of order. But we need to check if this
3375                  * did already happen before due to other refs in the same dir.
3376                  */
3377                 ret = get_cur_inode_state(sctx, cur->dir, cur->dir_gen);
3378                 if (ret < 0)
3379                         goto out;
3380                 if (ret == inode_state_will_create) {
3381                         ret = 0;
3382                         /*
3383                          * First check if any of the current inodes refs did
3384                          * already create the dir.
3385                          */
3386                         list_for_each_entry(cur2, &sctx->new_refs, list) {
3387                                 if (cur == cur2)
3388                                         break;
3389                                 if (cur2->dir == cur->dir) {
3390                                         ret = 1;
3391                                         break;
3392                                 }
3393                         }
3394
3395                         /*
3396                          * If that did not happen, check if a previous inode
3397                          * did already create the dir.
3398                          */
3399                         if (!ret)
3400                                 ret = did_create_dir(sctx, cur->dir);
3401                         if (ret < 0)
3402                                 goto out;
3403                         if (!ret) {
3404                                 ret = send_create_inode(sctx, cur->dir);
3405                                 if (ret < 0)
3406                                         goto out;
3407                         }
3408                 }
3409
3410                 /*
3411                  * Check if this new ref would overwrite the first ref of
3412                  * another unprocessed inode. If yes, orphanize the
3413                  * overwritten inode. If we find an overwritten ref that is
3414                  * not the first ref, simply unlink it.
3415                  */
3416                 ret = will_overwrite_ref(sctx, cur->dir, cur->dir_gen,
3417                                 cur->name, cur->name_len,
3418                                 &ow_inode, &ow_gen);
3419                 if (ret < 0)
3420                         goto out;
3421                 if (ret) {
3422                         ret = is_first_ref(sctx->parent_root,
3423                                            ow_inode, cur->dir, cur->name,
3424                                            cur->name_len);
3425                         if (ret < 0)
3426                                 goto out;
3427                         if (ret) {
3428                                 ret = orphanize_inode(sctx, ow_inode, ow_gen,
3429                                                 cur->full_path);
3430                                 if (ret < 0)
3431                                         goto out;
3432                         } else {
3433                                 ret = send_unlink(sctx, cur->full_path);
3434                                 if (ret < 0)
3435                                         goto out;
3436                         }
3437                 }
3438
3439                 /*
3440                  * link/move the ref to the new place. If we have an orphan
3441                  * inode, move it and update valid_path. If not, link or move
3442                  * it depending on the inode mode.
3443                  */
3444                 if (is_orphan) {
3445                         ret = send_rename(sctx, valid_path, cur->full_path);
3446                         if (ret < 0)
3447                                 goto out;
3448                         is_orphan = 0;
3449                         ret = fs_path_copy(valid_path, cur->full_path);
3450                         if (ret < 0)
3451                                 goto out;
3452                 } else {
3453                         if (S_ISDIR(sctx->cur_inode_mode)) {
3454                                 /*
3455                                  * Dirs can't be linked, so move it. For moved
3456                                  * dirs, we always have one new and one deleted
3457                                  * ref. The deleted ref is ignored later.
3458                                  */
3459                                 ret = wait_for_parent_move(sctx, cur);
3460                                 if (ret < 0)
3461                                         goto out;
3462                                 if (ret) {
3463                                         ret = add_pending_dir_move(sctx,
3464                                                            sctx->cur_ino,
3465                                                            sctx->cur_inode_gen,
3466                                                            cur->dir);
3467                                         *pending_move = 1;
3468                                 } else {
3469                                         ret = send_rename(sctx, valid_path,
3470                                                           cur->full_path);
3471                                         if (!ret)
3472                                                 ret = fs_path_copy(valid_path,
3473                                                                cur->full_path);
3474                                 }
3475                                 if (ret < 0)
3476                                         goto out;
3477                         } else {
3478                                 ret = send_link(sctx, cur->full_path,
3479                                                 valid_path);
3480                                 if (ret < 0)
3481                                         goto out;
3482                         }
3483                 }
3484                 ret = dup_ref(cur, &check_dirs);
3485                 if (ret < 0)
3486                         goto out;
3487         }
3488
3489         if (S_ISDIR(sctx->cur_inode_mode) && sctx->cur_inode_deleted) {
3490                 /*
3491                  * Check if we can already rmdir the directory. If not,
3492                  * orphanize it. For every dir item inside that gets deleted
3493                  * later, we do this check again and rmdir it then if possible.
3494                  * See the use of check_dirs for more details.
3495                  */
3496                 ret = can_rmdir(sctx, sctx->cur_ino, sctx->cur_inode_gen,
3497                                 sctx->cur_ino);
3498                 if (ret < 0)
3499                         goto out;
3500                 if (ret) {
3501                         ret = send_rmdir(sctx, valid_path);
3502                         if (ret < 0)
3503                                 goto out;
3504                 } else if (!is_orphan) {
3505                         ret = orphanize_inode(sctx, sctx->cur_ino,
3506                                         sctx->cur_inode_gen, valid_path);
3507                         if (ret < 0)
3508                                 goto out;
3509                         is_orphan = 1;
3510                 }
3511
3512                 list_for_each_entry(cur, &sctx->deleted_refs, list) {
3513                         ret = dup_ref(cur, &check_dirs);
3514                         if (ret < 0)
3515                                 goto out;
3516                 }
3517         } else if (S_ISDIR(sctx->cur_inode_mode) &&
3518                    !list_empty(&sctx->deleted_refs)) {
3519                 /*
3520                  * We have a moved dir. Add the old parent to check_dirs
3521                  */
3522                 cur = list_entry(sctx->deleted_refs.next, struct recorded_ref,
3523                                 list);
3524                 ret = dup_ref(cur, &check_dirs);
3525                 if (ret < 0)
3526                         goto out;
3527         } else if (!S_ISDIR(sctx->cur_inode_mode)) {
3528                 /*
3529                  * We have a non dir inode. Go through all deleted refs and
3530                  * unlink them if they were not already overwritten by other
3531                  * inodes.
3532                  */
3533                 list_for_each_entry(cur, &sctx->deleted_refs, list) {
3534                         ret = did_overwrite_ref(sctx, cur->dir, cur->dir_gen,
3535                                         sctx->cur_ino, sctx->cur_inode_gen,
3536                                         cur->name, cur->name_len);
3537                         if (ret < 0)
3538                                 goto out;
3539                         if (!ret) {
3540                                 ret = send_unlink(sctx, cur->full_path);
3541                                 if (ret < 0)
3542                                         goto out;
3543                         }
3544                         ret = dup_ref(cur, &check_dirs);
3545                         if (ret < 0)
3546                                 goto out;
3547                 }
3548                 /*
3549                  * If the inode is still orphan, unlink the orphan. This may
3550                  * happen when a previous inode did overwrite the first ref
3551                  * of this inode and no new refs were added for the current
3552                  * inode. Unlinking does not mean that the inode is deleted in
3553                  * all cases. There may still be links to this inode in other
3554                  * places.
3555                  */
3556                 if (is_orphan) {
3557                         ret = send_unlink(sctx, valid_path);
3558                         if (ret < 0)
3559                                 goto out;
3560                 }
3561         }
3562
3563         /*
3564          * We did collect all parent dirs where cur_inode was once located. We
3565          * now go through all these dirs and check if they are pending for
3566          * deletion and if it's finally possible to perform the rmdir now.
3567          * We also update the inode stats of the parent dirs here.
3568          */
3569         list_for_each_entry(cur, &check_dirs, list) {
3570                 /*
3571                  * In case we had refs into dirs that were not processed yet,
3572                  * we don't need to do the utime and rmdir logic for these dirs.
3573                  * The dir will be processed later.
3574                  */
3575                 if (cur->dir > sctx->cur_ino)
3576                         continue;
3577
3578                 ret = get_cur_inode_state(sctx, cur->dir, cur->dir_gen);
3579                 if (ret < 0)
3580                         goto out;
3581
3582                 if (ret == inode_state_did_create ||
3583                     ret == inode_state_no_change) {
3584                         /* TODO delayed utimes */
3585                         ret = send_utimes(sctx, cur->dir, cur->dir_gen);
3586                         if (ret < 0)
3587                                 goto out;
3588                 } else if (ret == inode_state_did_delete &&
3589                            cur->dir != last_dir_ino_rm) {
3590                         ret = can_rmdir(sctx, cur->dir, cur->dir_gen,
3591                                         sctx->cur_ino);
3592                         if (ret < 0)
3593                                 goto out;
3594                         if (ret) {
3595                                 ret = get_cur_path(sctx, cur->dir,
3596                                                    cur->dir_gen, valid_path);
3597                                 if (ret < 0)
3598                                         goto out;
3599                                 ret = send_rmdir(sctx, valid_path);
3600                                 if (ret < 0)
3601                                         goto out;
3602                                 last_dir_ino_rm = cur->dir;
3603                         }
3604                 }
3605         }
3606
3607         ret = 0;
3608
3609 out:
3610         __free_recorded_refs(&check_dirs);
3611         free_recorded_refs(sctx);
3612         fs_path_free(valid_path);
3613         return ret;
3614 }
3615
3616 static int record_ref(struct btrfs_root *root, int num, u64 dir, int index,
3617                       struct fs_path *name, void *ctx, struct list_head *refs)
3618 {
3619         int ret = 0;
3620         struct send_ctx *sctx = ctx;
3621         struct fs_path *p;
3622         u64 gen;
3623
3624         p = fs_path_alloc();
3625         if (!p)
3626                 return -ENOMEM;
3627
3628         ret = get_inode_info(root, dir, NULL, &gen, NULL, NULL,
3629                         NULL, NULL);
3630         if (ret < 0)
3631                 goto out;
3632
3633         ret = get_cur_path(sctx, dir, gen, p);
3634         if (ret < 0)
3635                 goto out;
3636         ret = fs_path_add_path(p, name);
3637         if (ret < 0)
3638                 goto out;
3639
3640         ret = __record_ref(refs, dir, gen, p);
3641
3642 out:
3643         if (ret)
3644                 fs_path_free(p);
3645         return ret;
3646 }
3647
3648 static int __record_new_ref(int num, u64 dir, int index,
3649                             struct fs_path *name,
3650                             void *ctx)
3651 {
3652         struct send_ctx *sctx = ctx;
3653         return record_ref(sctx->send_root, num, dir, index, name,
3654                           ctx, &sctx->new_refs);
3655 }
3656
3657
3658 static int __record_deleted_ref(int num, u64 dir, int index,
3659                                 struct fs_path *name,
3660                                 void *ctx)
3661 {
3662         struct send_ctx *sctx = ctx;
3663         return record_ref(sctx->parent_root, num, dir, index, name,
3664                           ctx, &sctx->deleted_refs);
3665 }
3666
3667 static int record_new_ref(struct send_ctx *sctx)
3668 {
3669         int ret;
3670
3671         ret = iterate_inode_ref(sctx->send_root, sctx->left_path,
3672                                 sctx->cmp_key, 0, __record_new_ref, sctx);
3673         if (ret < 0)
3674                 goto out;
3675         ret = 0;
3676
3677 out:
3678         return ret;
3679 }
3680
3681 static int record_deleted_ref(struct send_ctx *sctx)
3682 {
3683         int ret;
3684
3685         ret = iterate_inode_ref(sctx->parent_root, sctx->right_path,
3686                                 sctx->cmp_key, 0, __record_deleted_ref, sctx);
3687         if (ret < 0)
3688                 goto out;
3689         ret = 0;
3690
3691 out:
3692         return ret;
3693 }
3694
3695 struct find_ref_ctx {
3696         u64 dir;
3697         u64 dir_gen;
3698         struct btrfs_root *root;
3699         struct fs_path *name;
3700         int found_idx;
3701 };
3702
3703 static int __find_iref(int num, u64 dir, int index,
3704                        struct fs_path *name,
3705                        void *ctx_)
3706 {
3707         struct find_ref_ctx *ctx = ctx_;
3708         u64 dir_gen;
3709         int ret;
3710
3711         if (dir == ctx->dir && fs_path_len(name) == fs_path_len(ctx->name) &&
3712             strncmp(name->start, ctx->name->start, fs_path_len(name)) == 0) {
3713                 /*
3714                  * To avoid doing extra lookups we'll only do this if everything
3715                  * else matches.
3716                  */
3717                 ret = get_inode_info(ctx->root, dir, NULL, &dir_gen, NULL,
3718                                      NULL, NULL, NULL);
3719                 if (ret)
3720                         return ret;
3721                 if (dir_gen != ctx->dir_gen)
3722                         return 0;
3723                 ctx->found_idx = num;
3724                 return 1;
3725         }
3726         return 0;
3727 }
3728
3729 static int find_iref(struct btrfs_root *root,
3730                      struct btrfs_path *path,
3731                      struct btrfs_key *key,
3732                      u64 dir, u64 dir_gen, struct fs_path *name)
3733 {
3734         int ret;
3735         struct find_ref_ctx ctx;
3736
3737         ctx.dir = dir;
3738         ctx.name = name;
3739         ctx.dir_gen = dir_gen;
3740         ctx.found_idx = -1;
3741         ctx.root = root;
3742
3743         ret = iterate_inode_ref(root, path, key, 0, __find_iref, &ctx);
3744         if (ret < 0)
3745                 return ret;
3746
3747         if (ctx.found_idx == -1)
3748                 return -ENOENT;
3749
3750         return ctx.found_idx;
3751 }
3752
3753 static int __record_changed_new_ref(int num, u64 dir, int index,
3754                                     struct fs_path *name,
3755                                     void *ctx)
3756 {
3757         u64 dir_gen;
3758         int ret;
3759         struct send_ctx *sctx = ctx;
3760
3761         ret = get_inode_info(sctx->send_root, dir, NULL, &dir_gen, NULL,
3762                              NULL, NULL, NULL);
3763         if (ret)
3764                 return ret;
3765
3766         ret = find_iref(sctx->parent_root, sctx->right_path,
3767                         sctx->cmp_key, dir, dir_gen, name);
3768         if (ret == -ENOENT)
3769                 ret = __record_new_ref(num, dir, index, name, sctx);
3770         else if (ret > 0)
3771                 ret = 0;
3772
3773         return ret;
3774 }
3775
3776 static int __record_changed_deleted_ref(int num, u64 dir, int index,
3777                                         struct fs_path *name,
3778                                         void *ctx)
3779 {
3780         u64 dir_gen;
3781         int ret;
3782         struct send_ctx *sctx = ctx;
3783
3784         ret = get_inode_info(sctx->parent_root, dir, NULL, &dir_gen, NULL,
3785                              NULL, NULL, NULL);
3786         if (ret)
3787                 return ret;
3788
3789         ret = find_iref(sctx->send_root, sctx->left_path, sctx->cmp_key,
3790                         dir, dir_gen, name);
3791         if (ret == -ENOENT)
3792                 ret = __record_deleted_ref(num, dir, index, name, sctx);
3793         else if (ret > 0)
3794                 ret = 0;
3795
3796         return ret;
3797 }
3798
3799 static int record_changed_ref(struct send_ctx *sctx)
3800 {
3801         int ret = 0;
3802
3803         ret = iterate_inode_ref(sctx->send_root, sctx->left_path,
3804                         sctx->cmp_key, 0, __record_changed_new_ref, sctx);
3805         if (ret < 0)
3806                 goto out;
3807         ret = iterate_inode_ref(sctx->parent_root, sctx->right_path,
3808                         sctx->cmp_key, 0, __record_changed_deleted_ref, sctx);
3809         if (ret < 0)
3810                 goto out;
3811         ret = 0;
3812
3813 out:
3814         return ret;
3815 }
3816
3817 /*
3818  * Record and process all refs at once. Needed when an inode changes the
3819  * generation number, which means that it was deleted and recreated.
3820  */
3821 static int process_all_refs(struct send_ctx *sctx,
3822                             enum btrfs_compare_tree_result cmd)
3823 {
3824         int ret;
3825         struct btrfs_root *root;
3826         struct btrfs_path *path;
3827         struct btrfs_key key;
3828         struct btrfs_key found_key;
3829         struct extent_buffer *eb;
3830         int slot;
3831         iterate_inode_ref_t cb;
3832         int pending_move = 0;
3833
3834         path = alloc_path_for_send();
3835         if (!path)
3836                 return -ENOMEM;
3837
3838         if (cmd == BTRFS_COMPARE_TREE_NEW) {
3839                 root = sctx->send_root;
3840                 cb = __record_new_ref;
3841         } else if (cmd == BTRFS_COMPARE_TREE_DELETED) {
3842                 root = sctx->parent_root;
3843                 cb = __record_deleted_ref;
3844         } else {
3845                 btrfs_err(sctx->send_root->fs_info,
3846                                 "Wrong command %d in process_all_refs", cmd);
3847                 ret = -EINVAL;
3848                 goto out;
3849         }
3850
3851         key.objectid = sctx->cmp_key->objectid;
3852         key.type = BTRFS_INODE_REF_KEY;
3853         key.offset = 0;
3854         ret = btrfs_search_slot(NULL, root, &key, path, 0, 0);
3855         if (ret < 0)
3856                 goto out;
3857
3858         while (1) {
3859                 eb = path->nodes[0];
3860                 slot = path->slots[0];
3861                 if (slot >= btrfs_header_nritems(eb)) {
3862                         ret = btrfs_next_leaf(root, path);
3863                         if (ret < 0)
3864                                 goto out;
3865                         else if (ret > 0)
3866                                 break;
3867                         continue;
3868                 }
3869
3870                 btrfs_item_key_to_cpu(eb, &found_key, slot);
3871
3872                 if (found_key.objectid != key.objectid ||
3873                     (found_key.type != BTRFS_INODE_REF_KEY &&
3874                      found_key.type != BTRFS_INODE_EXTREF_KEY))
3875                         break;
3876
3877                 ret = iterate_inode_ref(root, path, &found_key, 0, cb, sctx);
3878                 if (ret < 0)
3879                         goto out;
3880
3881                 path->slots[0]++;
3882         }
3883         btrfs_release_path(path);
3884
3885         ret = process_recorded_refs(sctx, &pending_move);
3886         /* Only applicable to an incremental send. */
3887         ASSERT(pending_move == 0);
3888
3889 out:
3890         btrfs_free_path(path);
3891         return ret;
3892 }
3893
3894 static int send_set_xattr(struct send_ctx *sctx,
3895                           struct fs_path *path,
3896                           const char *name, int name_len,
3897                           const char *data, int data_len)
3898 {
3899         int ret = 0;
3900
3901         ret = begin_cmd(sctx, BTRFS_SEND_C_SET_XATTR);
3902         if (ret < 0)
3903                 goto out;
3904
3905         TLV_PUT_PATH(sctx, BTRFS_SEND_A_PATH, path);
3906         TLV_PUT_STRING(sctx, BTRFS_SEND_A_XATTR_NAME, name, name_len);
3907         TLV_PUT(sctx, BTRFS_SEND_A_XATTR_DATA, data, data_len);
3908
3909         ret = send_cmd(sctx);
3910
3911 tlv_put_failure:
3912 out:
3913         return ret;
3914 }
3915
3916 static int send_remove_xattr(struct send_ctx *sctx,
3917                           struct fs_path *path,
3918                           const char *name, int name_len)
3919 {
3920         int ret = 0;
3921
3922         ret = begin_cmd(sctx, BTRFS_SEND_C_REMOVE_XATTR);
3923         if (ret < 0)
3924                 goto out;
3925
3926         TLV_PUT_PATH(sctx, BTRFS_SEND_A_PATH, path);
3927         TLV_PUT_STRING(sctx, BTRFS_SEND_A_XATTR_NAME, name, name_len);
3928
3929         ret = send_cmd(sctx);
3930
3931 tlv_put_failure:
3932 out:
3933         return ret;
3934 }
3935
3936 static int __process_new_xattr(int num, struct btrfs_key *di_key,
3937                                const char *name, int name_len,
3938                                const char *data, int data_len,
3939                                u8 type, void *ctx)
3940 {
3941         int ret;
3942         struct send_ctx *sctx = ctx;
3943         struct fs_path *p;
3944         posix_acl_xattr_header dummy_acl;
3945
3946         p = fs_path_alloc();
3947         if (!p)
3948                 return -ENOMEM;
3949
3950         /*
3951          * This hack is needed because empty acl's are stored as zero byte
3952          * data in xattrs. Problem with that is, that receiving these zero byte
3953          * acl's will fail later. To fix this, we send a dummy acl list that
3954          * only contains the version number and no entries.
3955          */
3956         if (!strncmp(name, XATTR_NAME_POSIX_ACL_ACCESS, name_len) ||
3957             !strncmp(name, XATTR_NAME_POSIX_ACL_DEFAULT, name_len)) {
3958                 if (data_len == 0) {
3959                         dummy_acl.a_version =
3960                                         cpu_to_le32(POSIX_ACL_XATTR_VERSION);
3961                         data = (char *)&dummy_acl;
3962                         data_len = sizeof(dummy_acl);
3963                 }
3964         }
3965
3966         ret = get_cur_path(sctx, sctx->cur_ino, sctx->cur_inode_gen, p);
3967         if (ret < 0)
3968                 goto out;
3969
3970         ret = send_set_xattr(sctx, p, name, name_len, data, data_len);
3971
3972 out:
3973         fs_path_free(p);
3974         return ret;
3975 }
3976
3977 static int __process_deleted_xattr(int num, struct btrfs_key *di_key,
3978                                    const char *name, int name_len,
3979                                    const char *data, int data_len,
3980                                    u8 type, void *ctx)
3981 {
3982         int ret;
3983         struct send_ctx *sctx = ctx;
3984         struct fs_path *p;
3985
3986         p = fs_path_alloc();
3987         if (!p)
3988                 return -ENOMEM;
3989
3990         ret = get_cur_path(sctx, sctx->cur_ino, sctx->cur_inode_gen, p);
3991         if (ret < 0)
3992                 goto out;
3993
3994         ret = send_remove_xattr(sctx, p, name, name_len);
3995
3996 out:
3997         fs_path_free(p);
3998         return ret;
3999 }
4000
4001 static int process_new_xattr(struct send_ctx *sctx)
4002 {
4003         int ret = 0;
4004
4005         ret = iterate_dir_item(sctx->send_root, sctx->left_path,
4006                                sctx->cmp_key, __process_new_xattr, sctx);
4007
4008         return ret;
4009 }
4010
4011 static int process_deleted_xattr(struct send_ctx *sctx)
4012 {
4013         int ret;
4014
4015         ret = iterate_dir_item(sctx->parent_root, sctx->right_path,
4016                                sctx->cmp_key, __process_deleted_xattr, sctx);
4017
4018         return ret;
4019 }
4020
4021 struct find_xattr_ctx {
4022         const char *name;
4023         int name_len;
4024         int found_idx;
4025         char *found_data;
4026         int found_data_len;
4027 };
4028
4029 static int __find_xattr(int num, struct btrfs_key *di_key,
4030                         const char *name, int name_len,
4031                         const char *data, int data_len,
4032                         u8 type, void *vctx)
4033 {
4034         struct find_xattr_ctx *ctx = vctx;
4035
4036         if (name_len == ctx->name_len &&
4037             strncmp(name, ctx->name, name_len) == 0) {
4038                 ctx->found_idx = num;
4039                 ctx->found_data_len = data_len;
4040                 ctx->found_data = kmemdup(data, data_len, GFP_NOFS);
4041                 if (!ctx->found_data)
4042                         return -ENOMEM;
4043                 return 1;
4044         }
4045         return 0;
4046 }
4047
4048 static int find_xattr(struct btrfs_root *root,
4049                       struct btrfs_path *path,
4050                       struct btrfs_key *key,
4051                       const char *name, int name_len,
4052                       char **data, int *data_len)
4053 {
4054         int ret;
4055         struct find_xattr_ctx ctx;
4056
4057         ctx.name = name;
4058         ctx.name_len = name_len;
4059         ctx.found_idx = -1;
4060         ctx.found_data = NULL;
4061         ctx.found_data_len = 0;
4062
4063         ret = iterate_dir_item(root, path, key, __find_xattr, &ctx);
4064         if (ret < 0)
4065                 return ret;
4066
4067         if (ctx.found_idx == -1)
4068                 return -ENOENT;
4069         if (data) {
4070                 *data = ctx.found_data;
4071                 *data_len = ctx.found_data_len;
4072         } else {
4073                 kfree(ctx.found_data);
4074         }
4075         return ctx.found_idx;
4076 }
4077
4078
4079 static int __process_changed_new_xattr(int num, struct btrfs_key *di_key,
4080                                        const char *name, int name_len,
4081                                        const char *data, int data_len,
4082                                        u8 type, void *ctx)
4083 {
4084         int ret;
4085         struct send_ctx *sctx = ctx;
4086         char *found_data = NULL;
4087         int found_data_len  = 0;
4088
4089         ret = find_xattr(sctx->parent_root, sctx->right_path,
4090                          sctx->cmp_key, name, name_len, &found_data,
4091                          &found_data_len);
4092         if (ret == -ENOENT) {
4093                 ret = __process_new_xattr(num, di_key, name, name_len, data,
4094                                 data_len, type, ctx);
4095         } else if (ret >= 0) {
4096                 if (data_len != found_data_len ||
4097                     memcmp(data, found_data, data_len)) {
4098                         ret = __process_new_xattr(num, di_key, name, name_len,
4099                                         data, data_len, type, ctx);
4100                 } else {
4101                         ret = 0;
4102                 }
4103         }
4104
4105         kfree(found_data);
4106         return ret;
4107 }
4108
4109 static int __process_changed_deleted_xattr(int num, struct btrfs_key *di_key,
4110                                            const char *name, int name_len,
4111                                            const char *data, int data_len,
4112                                            u8 type, void *ctx)
4113 {
4114         int ret;
4115         struct send_ctx *sctx = ctx;
4116
4117         ret = find_xattr(sctx->send_root, sctx->left_path, sctx->cmp_key,
4118                          name, name_len, NULL, NULL);
4119         if (ret == -ENOENT)
4120                 ret = __process_deleted_xattr(num, di_key, name, name_len, data,
4121                                 data_len, type, ctx);
4122         else if (ret >= 0)
4123                 ret = 0;
4124
4125         return ret;
4126 }
4127
4128 static int process_changed_xattr(struct send_ctx *sctx)
4129 {
4130         int ret = 0;
4131
4132         ret = iterate_dir_item(sctx->send_root, sctx->left_path,
4133                         sctx->cmp_key, __process_changed_new_xattr, sctx);
4134         if (ret < 0)
4135                 goto out;
4136         ret = iterate_dir_item(sctx->parent_root, sctx->right_path,
4137                         sctx->cmp_key, __process_changed_deleted_xattr, sctx);
4138
4139 out:
4140         return ret;
4141 }
4142
4143 static int process_all_new_xattrs(struct send_ctx *sctx)
4144 {
4145         int ret;
4146         struct btrfs_root *root;
4147         struct btrfs_path *path;
4148         struct btrfs_key key;
4149         struct btrfs_key found_key;
4150         struct extent_buffer *eb;
4151         int slot;
4152
4153         path = alloc_path_for_send();
4154         if (!path)
4155                 return -ENOMEM;
4156
4157         root = sctx->send_root;
4158
4159         key.objectid = sctx->cmp_key->objectid;
4160         key.type = BTRFS_XATTR_ITEM_KEY;
4161         key.offset = 0;
4162         ret = btrfs_search_slot(NULL, root, &key, path, 0, 0);
4163         if (ret < 0)
4164                 goto out;
4165
4166         while (1) {
4167                 eb = path->nodes[0];
4168                 slot = path->slots[0];
4169                 if (slot >= btrfs_header_nritems(eb)) {
4170                         ret = btrfs_next_leaf(root, path);
4171                         if (ret < 0) {
4172                                 goto out;
4173                         } else if (ret > 0) {
4174                                 ret = 0;
4175                                 break;
4176                         }
4177                         continue;
4178                 }
4179
4180                 btrfs_item_key_to_cpu(eb, &found_key, slot);
4181                 if (found_key.objectid != key.objectid ||
4182                     found_key.type != key.type) {
4183                         ret = 0;
4184                         goto out;
4185                 }
4186
4187                 ret = iterate_dir_item(root, path, &found_key,
4188                                        __process_new_xattr, sctx);
4189                 if (ret < 0)
4190                         goto out;
4191
4192                 path->slots[0]++;
4193         }
4194
4195 out:
4196         btrfs_free_path(path);
4197         return ret;
4198 }
4199
4200 static ssize_t fill_read_buf(struct send_ctx *sctx, u64 offset, u32 len)
4201 {
4202         struct btrfs_root *root = sctx->send_root;
4203         struct btrfs_fs_info *fs_info = root->fs_info;
4204         struct inode *inode;
4205         struct page *page;
4206         char *addr;
4207         struct btrfs_key key;
4208         pgoff_t index = offset >> PAGE_CACHE_SHIFT;
4209         pgoff_t last_index;
4210         unsigned pg_offset = offset & ~PAGE_CACHE_MASK;
4211         ssize_t ret = 0;
4212
4213         key.objectid = sctx->cur_ino;
4214         key.type = BTRFS_INODE_ITEM_KEY;
4215         key.offset = 0;
4216
4217         inode = btrfs_iget(fs_info->sb, &key, root, NULL);
4218         if (IS_ERR(inode))
4219                 return PTR_ERR(inode);
4220
4221         if (offset + len > i_size_read(inode)) {
4222                 if (offset > i_size_read(inode))
4223                         len = 0;
4224                 else
4225                         len = offset - i_size_read(inode);
4226         }
4227         if (len == 0)
4228                 goto out;
4229
4230         last_index = (offset + len - 1) >> PAGE_CACHE_SHIFT;
4231
4232         /* initial readahead */
4233         memset(&sctx->ra, 0, sizeof(struct file_ra_state));
4234         file_ra_state_init(&sctx->ra, inode->i_mapping);
4235         btrfs_force_ra(inode->i_mapping, &sctx->ra, NULL, index,
4236                        last_index - index + 1);
4237
4238         while (index <= last_index) {
4239                 unsigned cur_len = min_t(unsigned, len,
4240                                          PAGE_CACHE_SIZE - pg_offset);
4241                 page = find_or_create_page(inode->i_mapping, index, GFP_NOFS);
4242                 if (!page) {
4243                         ret = -ENOMEM;
4244                         break;
4245                 }
4246
4247                 if (!PageUptodate(page)) {
4248                         btrfs_readpage(NULL, page);
4249                         lock_page(page);
4250                         if (!PageUptodate(page)) {
4251                                 unlock_page(page);
4252                                 page_cache_release(page);
4253                                 ret = -EIO;
4254                                 break;
4255                         }
4256                 }
4257
4258                 addr = kmap(page);
4259                 memcpy(sctx->read_buf + ret, addr + pg_offset, cur_len);
4260                 kunmap(page);
4261                 unlock_page(page);
4262                 page_cache_release(page);
4263                 index++;
4264                 pg_offset = 0;
4265                 len -= cur_len;
4266                 ret += cur_len;
4267         }
4268 out:
4269         iput(inode);
4270         return ret;
4271 }
4272
4273 /*
4274  * Read some bytes from the current inode/file and send a write command to
4275  * user space.
4276  */
4277 static int send_write(struct send_ctx *sctx, u64 offset, u32 len)
4278 {
4279         int ret = 0;
4280         struct fs_path *p;
4281         ssize_t num_read = 0;
4282
4283         p = fs_path_alloc();
4284         if (!p)
4285                 return -ENOMEM;
4286
4287 verbose_printk("btrfs: send_write offset=%llu, len=%d\n", offset, len);
4288
4289         num_read = fill_read_buf(sctx, offset, len);
4290         if (num_read <= 0) {
4291                 if (num_read < 0)
4292                         ret = num_read;
4293                 goto out;
4294         }
4295
4296         ret = begin_cmd(sctx, BTRFS_SEND_C_WRITE);
4297         if (ret < 0)
4298                 goto out;
4299
4300         ret = get_cur_path(sctx, sctx->cur_ino, sctx->cur_inode_gen, p);
4301         if (ret < 0)
4302                 goto out;
4303
4304         TLV_PUT_PATH(sctx, BTRFS_SEND_A_PATH, p);
4305         TLV_PUT_U64(sctx, BTRFS_SEND_A_FILE_OFFSET, offset);
4306         TLV_PUT(sctx, BTRFS_SEND_A_DATA, sctx->read_buf, num_read);
4307
4308         ret = send_cmd(sctx);
4309
4310 tlv_put_failure:
4311 out:
4312         fs_path_free(p);
4313         if (ret < 0)
4314                 return ret;
4315         return num_read;
4316 }
4317
4318 /*
4319  * Send a clone command to user space.
4320  */
4321 static int send_clone(struct send_ctx *sctx,
4322                       u64 offset, u32 len,
4323                       struct clone_root *clone_root)
4324 {
4325         int ret = 0;
4326         struct fs_path *p;
4327         u64 gen;
4328
4329 verbose_printk("btrfs: send_clone offset=%llu, len=%d, clone_root=%llu, "
4330                "clone_inode=%llu, clone_offset=%llu\n", offset, len,
4331                 clone_root->root->objectid, clone_root->ino,
4332                 clone_root->offset);
4333
4334         p = fs_path_alloc();
4335         if (!p)
4336                 return -ENOMEM;
4337
4338         ret = begin_cmd(sctx, BTRFS_SEND_C_CLONE);
4339         if (ret < 0)
4340                 goto out;
4341
4342         ret = get_cur_path(sctx, sctx->cur_ino, sctx->cur_inode_gen, p);
4343         if (ret < 0)
4344                 goto out;
4345
4346         TLV_PUT_U64(sctx, BTRFS_SEND_A_FILE_OFFSET, offset);
4347         TLV_PUT_U64(sctx, BTRFS_SEND_A_CLONE_LEN, len);
4348         TLV_PUT_PATH(sctx, BTRFS_SEND_A_PATH, p);
4349
4350         if (clone_root->root == sctx->send_root) {
4351                 ret = get_inode_info(sctx->send_root, clone_root->ino, NULL,
4352                                 &gen, NULL, NULL, NULL, NULL);
4353                 if (ret < 0)
4354                         goto out;
4355                 ret = get_cur_path(sctx, clone_root->ino, gen, p);
4356         } else {
4357                 ret = get_inode_path(clone_root->root, clone_root->ino, p);
4358         }
4359         if (ret < 0)
4360                 goto out;
4361
4362         TLV_PUT_UUID(sctx, BTRFS_SEND_A_CLONE_UUID,
4363                         clone_root->root->root_item.uuid);
4364         TLV_PUT_U64(sctx, BTRFS_SEND_A_CLONE_CTRANSID,
4365                     le64_to_cpu(clone_root->root->root_item.ctransid));
4366         TLV_PUT_PATH(sctx, BTRFS_SEND_A_CLONE_PATH, p);
4367         TLV_PUT_U64(sctx, BTRFS_SEND_A_CLONE_OFFSET,
4368                         clone_root->offset);
4369
4370         ret = send_cmd(sctx);
4371
4372 tlv_put_failure:
4373 out:
4374         fs_path_free(p);
4375         return ret;
4376 }
4377
4378 /*
4379  * Send an update extent command to user space.
4380  */
4381 static int send_update_extent(struct send_ctx *sctx,
4382                               u64 offset, u32 len)
4383 {
4384         int ret = 0;
4385         struct fs_path *p;
4386
4387         p = fs_path_alloc();
4388         if (!p)
4389                 return -ENOMEM;
4390
4391         ret = begin_cmd(sctx, BTRFS_SEND_C_UPDATE_EXTENT);
4392         if (ret < 0)
4393                 goto out;
4394
4395         ret = get_cur_path(sctx, sctx->cur_ino, sctx->cur_inode_gen, p);
4396         if (ret < 0)
4397                 goto out;
4398
4399         TLV_PUT_PATH(sctx, BTRFS_SEND_A_PATH, p);
4400         TLV_PUT_U64(sctx, BTRFS_SEND_A_FILE_OFFSET, offset);
4401         TLV_PUT_U64(sctx, BTRFS_SEND_A_SIZE, len);
4402
4403         ret = send_cmd(sctx);
4404
4405 tlv_put_failure:
4406 out:
4407         fs_path_free(p);
4408         return ret;
4409 }
4410
4411 static int send_hole(struct send_ctx *sctx, u64 end)
4412 {
4413         struct fs_path *p = NULL;
4414         u64 offset = sctx->cur_inode_last_extent;
4415         u64 len;
4416         int ret = 0;
4417
4418         p = fs_path_alloc();
4419         if (!p)
4420                 return -ENOMEM;
4421         memset(sctx->read_buf, 0, BTRFS_SEND_READ_SIZE);
4422         while (offset < end) {
4423                 len = min_t(u64, end - offset, BTRFS_SEND_READ_SIZE);
4424
4425                 ret = begin_cmd(sctx, BTRFS_SEND_C_WRITE);
4426                 if (ret < 0)
4427                         break;
4428                 ret = get_cur_path(sctx, sctx->cur_ino, sctx->cur_inode_gen, p);
4429                 if (ret < 0)
4430                         break;
4431                 TLV_PUT_PATH(sctx, BTRFS_SEND_A_PATH, p);
4432                 TLV_PUT_U64(sctx, BTRFS_SEND_A_FILE_OFFSET, offset);
4433                 TLV_PUT(sctx, BTRFS_SEND_A_DATA, sctx->read_buf, len);
4434                 ret = send_cmd(sctx);
4435                 if (ret < 0)
4436                         break;
4437                 offset += len;
4438         }
4439 tlv_put_failure:
4440         fs_path_free(p);
4441         return ret;
4442 }
4443
4444 static int send_write_or_clone(struct send_ctx *sctx,
4445                                struct btrfs_path *path,
4446                                struct btrfs_key *key,
4447                                struct clone_root *clone_root)
4448 {
4449         int ret = 0;
4450         struct btrfs_file_extent_item *ei;
4451         u64 offset = key->offset;
4452         u64 pos = 0;
4453         u64 len;
4454         u32 l;
4455         u8 type;
4456         u64 bs = sctx->send_root->fs_info->sb->s_blocksize;
4457
4458         ei = btrfs_item_ptr(path->nodes[0], path->slots[0],
4459                         struct btrfs_file_extent_item);
4460         type = btrfs_file_extent_type(path->nodes[0], ei);
4461         if (type == BTRFS_FILE_EXTENT_INLINE) {
4462                 len = btrfs_file_extent_inline_len(path->nodes[0],
4463                                                    path->slots[0], ei);
4464                 /*
4465                  * it is possible the inline item won't cover the whole page,
4466                  * but there may be items after this page.  Make
4467                  * sure to send the whole thing
4468                  */
4469                 len = PAGE_CACHE_ALIGN(len);
4470         } else {
4471                 len = btrfs_file_extent_num_bytes(path->nodes[0], ei);
4472         }
4473
4474         if (offset + len > sctx->cur_inode_size)
4475                 len = sctx->cur_inode_size - offset;
4476         if (len == 0) {
4477                 ret = 0;
4478                 goto out;
4479         }
4480
4481         if (clone_root && IS_ALIGNED(offset + len, bs)) {
4482                 ret = send_clone(sctx, offset, len, clone_root);
4483         } else if (sctx->flags & BTRFS_SEND_FLAG_NO_FILE_DATA) {
4484                 ret = send_update_extent(sctx, offset, len);
4485         } else {
4486                 while (pos < len) {
4487                         l = len - pos;
4488                         if (l > BTRFS_SEND_READ_SIZE)
4489                                 l = BTRFS_SEND_READ_SIZE;
4490                         ret = send_write(sctx, pos + offset, l);
4491                         if (ret < 0)
4492                                 goto out;
4493                         if (!ret)
4494                                 break;
4495                         pos += ret;
4496                 }
4497                 ret = 0;
4498         }
4499 out:
4500         return ret;
4501 }
4502
4503 static int is_extent_unchanged(struct send_ctx *sctx,
4504                                struct btrfs_path *left_path,
4505                                struct btrfs_key *ekey)
4506 {
4507         int ret = 0;
4508         struct btrfs_key key;
4509         struct btrfs_path *path = NULL;
4510         struct extent_buffer *eb;
4511         int slot;
4512         struct btrfs_key found_key;
4513         struct btrfs_file_extent_item *ei;
4514         u64 left_disknr;
4515         u64 right_disknr;
4516         u64 left_offset;
4517         u64 right_offset;
4518         u64 left_offset_fixed;
4519         u64 left_len;
4520         u64 right_len;
4521         u64 left_gen;
4522         u64 right_gen;
4523         u8 left_type;
4524         u8 right_type;
4525
4526         path = alloc_path_for_send();
4527         if (!path)
4528                 return -ENOMEM;
4529
4530         eb = left_path->nodes[0];
4531         slot = left_path->slots[0];
4532         ei = btrfs_item_ptr(eb, slot, struct btrfs_file_extent_item);
4533         left_type = btrfs_file_extent_type(eb, ei);
4534
4535         if (left_type != BTRFS_FILE_EXTENT_REG) {
4536                 ret = 0;
4537                 goto out;
4538         }
4539         left_disknr = btrfs_file_extent_disk_bytenr(eb, ei);
4540         left_len = btrfs_file_extent_num_bytes(eb, ei);
4541         left_offset = btrfs_file_extent_offset(eb, ei);
4542         left_gen = btrfs_file_extent_generation(eb, ei);
4543
4544         /*
4545          * Following comments will refer to these graphics. L is the left
4546          * extents which we are checking at the moment. 1-8 are the right
4547          * extents that we iterate.
4548          *
4549          *       |-----L-----|
4550          * |-1-|-2a-|-3-|-4-|-5-|-6-|
4551          *
4552          *       |-----L-----|
4553          * |--1--|-2b-|...(same as above)
4554          *
4555          * Alternative situation. Happens on files where extents got split.
4556          *       |-----L-----|
4557          * |-----------7-----------|-6-|
4558          *
4559          * Alternative situation. Happens on files which got larger.
4560          *       |-----L-----|
4561          * |-8-|
4562          * Nothing follows after 8.
4563          */
4564
4565         key.objectid = ekey->objectid;
4566         key.type = BTRFS_EXTENT_DATA_KEY;
4567         key.offset = ekey->offset;
4568         ret = btrfs_search_slot_for_read(sctx->parent_root, &key, path, 0, 0);
4569         if (ret < 0)
4570                 goto out;
4571         if (ret) {
4572                 ret = 0;
4573                 goto out;
4574         }
4575
4576         /*
4577          * Handle special case where the right side has no extents at all.
4578          */
4579         eb = path->nodes[0];
4580         slot = path->slots[0];
4581         btrfs_item_key_to_cpu(eb, &found_key, slot);
4582         if (found_key.objectid != key.objectid ||
4583             found_key.type != key.type) {
4584                 /* If we're a hole then just pretend nothing changed */
4585                 ret = (left_disknr) ? 0 : 1;
4586                 goto out;
4587         }
4588
4589         /*
4590          * We're now on 2a, 2b or 7.
4591          */
4592         key = found_key;
4593         while (key.offset < ekey->offset + left_len) {
4594                 ei = btrfs_item_ptr(eb, slot, struct btrfs_file_extent_item);
4595                 right_type = btrfs_file_extent_type(eb, ei);
4596                 if (right_type != BTRFS_FILE_EXTENT_REG) {
4597                         ret = 0;
4598                         goto out;
4599                 }
4600
4601                 right_disknr = btrfs_file_extent_disk_bytenr(eb, ei);
4602                 right_len = btrfs_file_extent_num_bytes(eb, ei);
4603                 right_offset = btrfs_file_extent_offset(eb, ei);
4604                 right_gen = btrfs_file_extent_generation(eb, ei);
4605
4606                 /*
4607                  * Are we at extent 8? If yes, we know the extent is changed.
4608                  * This may only happen on the first iteration.
4609                  */
4610                 if (found_key.offset + right_len <= ekey->offset) {
4611                         /* If we're a hole just pretend nothing changed */
4612                         ret = (left_disknr) ? 0 : 1;
4613                         goto out;
4614                 }
4615
4616                 left_offset_fixed = left_offset;
4617                 if (key.offset < ekey->offset) {
4618                         /* Fix the right offset for 2a and 7. */
4619                         right_offset += ekey->offset - key.offset;
4620                 } else {
4621                         /* Fix the left offset for all behind 2a and 2b */
4622                         left_offset_fixed += key.offset - ekey->offset;
4623                 }
4624
4625                 /*
4626                  * Check if we have the same extent.
4627                  */
4628                 if (left_disknr != right_disknr ||
4629                     left_offset_fixed != right_offset ||
4630                     left_gen != right_gen) {
4631                         ret = 0;
4632                         goto out;
4633                 }
4634
4635                 /*
4636                  * Go to the next extent.
4637                  */
4638                 ret = btrfs_next_item(sctx->parent_root, path);
4639                 if (ret < 0)
4640                         goto out;
4641                 if (!ret) {
4642                         eb = path->nodes[0];
4643                         slot = path->slots[0];
4644                         btrfs_item_key_to_cpu(eb, &found_key, slot);
4645                 }
4646                 if (ret || found_key.objectid != key.objectid ||
4647                     found_key.type != key.type) {
4648                         key.offset += right_len;
4649                         break;
4650                 }
4651                 if (found_key.offset != key.offset + right_len) {
4652                         ret = 0;
4653                         goto out;
4654                 }
4655                 key = found_key;
4656         }
4657
4658         /*
4659          * We're now behind the left extent (treat as unchanged) or at the end
4660          * of the right side (treat as changed).
4661          */
4662         if (key.offset >= ekey->offset + left_len)
4663                 ret = 1;
4664         else
4665                 ret = 0;
4666
4667
4668 out:
4669         btrfs_free_path(path);
4670         return ret;
4671 }
4672
4673 static int get_last_extent(struct send_ctx *sctx, u64 offset)
4674 {
4675         struct btrfs_path *path;
4676         struct btrfs_root *root = sctx->send_root;
4677         struct btrfs_file_extent_item *fi;
4678         struct btrfs_key key;
4679         u64 extent_end;
4680         u8 type;
4681         int ret;
4682
4683         path = alloc_path_for_send();
4684         if (!path)
4685                 return -ENOMEM;
4686
4687         sctx->cur_inode_last_extent = 0;
4688
4689         key.objectid = sctx->cur_ino;
4690         key.type = BTRFS_EXTENT_DATA_KEY;
4691         key.offset = offset;
4692         ret = btrfs_search_slot_for_read(root, &key, path, 0, 1);
4693         if (ret < 0)
4694                 goto out;
4695         ret = 0;
4696         btrfs_item_key_to_cpu(path->nodes[0], &key, path->slots[0]);
4697         if (key.objectid != sctx->cur_ino || key.type != BTRFS_EXTENT_DATA_KEY)
4698                 goto out;
4699
4700         fi = btrfs_item_ptr(path->nodes[0], path->slots[0],
4701                             struct btrfs_file_extent_item);
4702         type = btrfs_file_extent_type(path->nodes[0], fi);
4703         if (type == BTRFS_FILE_EXTENT_INLINE) {
4704                 u64 size = btrfs_file_extent_inline_len(path->nodes[0],
4705                                                         path->slots[0], fi);
4706                 extent_end = ALIGN(key.offset + size,
4707                                    sctx->send_root->sectorsize);
4708         } else {
4709                 extent_end = key.offset +
4710                         btrfs_file_extent_num_bytes(path->nodes[0], fi);
4711         }
4712         sctx->cur_inode_last_extent = extent_end;
4713 out:
4714         btrfs_free_path(path);
4715         return ret;
4716 }
4717
4718 static int maybe_send_hole(struct send_ctx *sctx, struct btrfs_path *path,
4719                            struct btrfs_key *key)
4720 {
4721         struct btrfs_file_extent_item *fi;
4722         u64 extent_end;
4723         u8 type;
4724         int ret = 0;
4725
4726         if (sctx->cur_ino != key->objectid || !need_send_hole(sctx))
4727                 return 0;
4728
4729         if (sctx->cur_inode_last_extent == (u64)-1) {
4730                 ret = get_last_extent(sctx, key->offset - 1);
4731                 if (ret)
4732                         return ret;
4733         }
4734
4735         fi = btrfs_item_ptr(path->nodes[0], path->slots[0],
4736                             struct btrfs_file_extent_item);
4737         type = btrfs_file_extent_type(path->nodes[0], fi);
4738         if (type == BTRFS_FILE_EXTENT_INLINE) {
4739                 u64 size = btrfs_file_extent_inline_len(path->nodes[0],
4740                                                         path->slots[0], fi);
4741                 extent_end = ALIGN(key->offset + size,
4742                                    sctx->send_root->sectorsize);
4743         } else {
4744                 extent_end = key->offset +
4745                         btrfs_file_extent_num_bytes(path->nodes[0], fi);
4746         }
4747
4748         if (path->slots[0] == 0 &&
4749             sctx->cur_inode_last_extent < key->offset) {
4750                 /*
4751                  * We might have skipped entire leafs that contained only
4752                  * file extent items for our current inode. These leafs have
4753                  * a generation number smaller (older) than the one in the
4754                  * current leaf and the leaf our last extent came from, and
4755                  * are located between these 2 leafs.
4756                  */
4757                 ret = get_last_extent(sctx, key->offset - 1);
4758                 if (ret)
4759                         return ret;
4760         }
4761
4762         if (sctx->cur_inode_last_extent < key->offset)
4763                 ret = send_hole(sctx, key->offset);
4764         sctx->cur_inode_last_extent = extent_end;
4765         return ret;
4766 }
4767
4768 static int process_extent(struct send_ctx *sctx,
4769                           struct btrfs_path *path,
4770                           struct btrfs_key *key)
4771 {
4772         struct clone_root *found_clone = NULL;
4773         int ret = 0;
4774
4775         if (S_ISLNK(sctx->cur_inode_mode))
4776                 return 0;
4777
4778         if (sctx->parent_root && !sctx->cur_inode_new) {
4779                 ret = is_extent_unchanged(sctx, path, key);
4780                 if (ret < 0)
4781                         goto out;
4782                 if (ret) {
4783                         ret = 0;
4784                         goto out_hole;
4785                 }
4786         } else {
4787                 struct btrfs_file_extent_item *ei;
4788                 u8 type;
4789
4790                 ei = btrfs_item_ptr(path->nodes[0], path->slots[0],
4791                                     struct btrfs_file_extent_item);
4792                 type = btrfs_file_extent_type(path->nodes[0], ei);
4793                 if (type == BTRFS_FILE_EXTENT_PREALLOC ||
4794                     type == BTRFS_FILE_EXTENT_REG) {
4795                         /*
4796                          * The send spec does not have a prealloc command yet,
4797                          * so just leave a hole for prealloc'ed extents until
4798                          * we have enough commands queued up to justify rev'ing
4799                          * the send spec.
4800                          */
4801                         if (type == BTRFS_FILE_EXTENT_PREALLOC) {
4802                                 ret = 0;
4803                                 goto out;
4804                         }
4805
4806                         /* Have a hole, just skip it. */
4807                         if (btrfs_file_extent_disk_bytenr(path->nodes[0], ei) == 0) {
4808                                 ret = 0;
4809                                 goto out;
4810                         }
4811                 }
4812         }
4813
4814         ret = find_extent_clone(sctx, path, key->objectid, key->offset,
4815                         sctx->cur_inode_size, &found_clone);
4816         if (ret != -ENOENT && ret < 0)
4817                 goto out;
4818
4819         ret = send_write_or_clone(sctx, path, key, found_clone);
4820         if (ret)
4821                 goto out;
4822 out_hole:
4823         ret = maybe_send_hole(sctx, path, key);
4824 out:
4825         return ret;
4826 }
4827
4828 static int process_all_extents(struct send_ctx *sctx)
4829 {
4830         int ret;
4831         struct btrfs_root *root;
4832         struct btrfs_path *path;
4833         struct btrfs_key key;
4834         struct btrfs_key found_key;
4835         struct extent_buffer *eb;
4836         int slot;
4837
4838         root = sctx->send_root;
4839         path = alloc_path_for_send();
4840         if (!path)
4841                 return -ENOMEM;
4842
4843         key.objectid = sctx->cmp_key->objectid;
4844         key.type = BTRFS_EXTENT_DATA_KEY;
4845         key.offset = 0;
4846         ret = btrfs_search_slot(NULL, root, &key, path, 0, 0);
4847         if (ret < 0)
4848                 goto out;
4849
4850         while (1) {
4851                 eb = path->nodes[0];
4852                 slot = path->slots[0];
4853
4854                 if (slot >= btrfs_header_nritems(eb)) {
4855                         ret = btrfs_next_leaf(root, path);
4856                         if (ret < 0) {
4857                                 goto out;
4858                         } else if (ret > 0) {
4859                                 ret = 0;
4860                                 break;
4861                         }
4862                         continue;
4863                 }
4864
4865                 btrfs_item_key_to_cpu(eb, &found_key, slot);
4866
4867                 if (found_key.objectid != key.objectid ||
4868                     found_key.type != key.type) {
4869                         ret = 0;
4870                         goto out;
4871                 }
4872
4873                 ret = process_extent(sctx, path, &found_key);
4874                 if (ret < 0)
4875                         goto out;
4876
4877                 path->slots[0]++;
4878         }
4879
4880 out:
4881         btrfs_free_path(path);
4882         return ret;
4883 }
4884
4885 static int process_recorded_refs_if_needed(struct send_ctx *sctx, int at_end,
4886                                            int *pending_move,
4887                                            int *refs_processed)
4888 {
4889         int ret = 0;
4890
4891         if (sctx->cur_ino == 0)
4892                 goto out;
4893         if (!at_end && sctx->cur_ino == sctx->cmp_key->objectid &&
4894             sctx->cmp_key->type <= BTRFS_INODE_EXTREF_KEY)
4895                 goto out;
4896         if (list_empty(&sctx->new_refs) && list_empty(&sctx->deleted_refs))
4897                 goto out;
4898
4899         ret = process_recorded_refs(sctx, pending_move);
4900         if (ret < 0)
4901                 goto out;
4902
4903         *refs_processed = 1;
4904 out:
4905         return ret;
4906 }
4907
4908 static int finish_inode_if_needed(struct send_ctx *sctx, int at_end)
4909 {
4910         int ret = 0;
4911         u64 left_mode;
4912         u64 left_uid;
4913         u64 left_gid;
4914         u64 right_mode;
4915         u64 right_uid;
4916         u64 right_gid;
4917         int need_chmod = 0;
4918         int need_chown = 0;
4919         int pending_move = 0;
4920         int refs_processed = 0;
4921
4922         ret = process_recorded_refs_if_needed(sctx, at_end, &pending_move,
4923                                               &refs_processed);
4924         if (ret < 0)
4925                 goto out;
4926
4927         /*
4928          * We have processed the refs and thus need to advance send_progress.
4929          * Now, calls to get_cur_xxx will take the updated refs of the current
4930          * inode into account.
4931          *
4932          * On the other hand, if our current inode is a directory and couldn't
4933          * be moved/renamed because its parent was renamed/moved too and it has
4934          * a higher inode number, we can only move/rename our current inode
4935          * after we moved/renamed its parent. Therefore in this case operate on
4936          * the old path (pre move/rename) of our current inode, and the
4937          * move/rename will be performed later.
4938          */
4939         if (refs_processed && !pending_move)
4940                 sctx->send_progress = sctx->cur_ino + 1;
4941
4942         if (sctx->cur_ino == 0 || sctx->cur_inode_deleted)
4943                 goto out;
4944         if (!at_end && sctx->cmp_key->objectid == sctx->cur_ino)
4945                 goto out;
4946
4947         ret = get_inode_info(sctx->send_root, sctx->cur_ino, NULL, NULL,
4948                         &left_mode, &left_uid, &left_gid, NULL);
4949         if (ret < 0)
4950                 goto out;
4951
4952         if (!sctx->parent_root || sctx->cur_inode_new) {
4953                 need_chown = 1;
4954                 if (!S_ISLNK(sctx->cur_inode_mode))
4955                         need_chmod = 1;
4956         } else {
4957                 ret = get_inode_info(sctx->parent_root, sctx->cur_ino,
4958                                 NULL, NULL, &right_mode, &right_uid,
4959                                 &right_gid, NULL);
4960                 if (ret < 0)
4961                         goto out;
4962
4963                 if (left_uid != right_uid || left_gid != right_gid)
4964                         need_chown = 1;
4965                 if (!S_ISLNK(sctx->cur_inode_mode) && left_mode != right_mode)
4966                         need_chmod = 1;
4967         }
4968
4969         if (S_ISREG(sctx->cur_inode_mode)) {
4970                 if (need_send_hole(sctx)) {
4971                         if (sctx->cur_inode_last_extent == (u64)-1) {
4972                                 ret = get_last_extent(sctx, (u64)-1);
4973                                 if (ret)
4974                                         goto out;
4975                         }
4976                         if (sctx->cur_inode_last_extent <
4977                             sctx->cur_inode_size) {
4978                                 ret = send_hole(sctx, sctx->cur_inode_size);
4979                                 if (ret)
4980                                         goto out;
4981                         }
4982                 }
4983                 ret = send_truncate(sctx, sctx->cur_ino, sctx->cur_inode_gen,
4984                                 sctx->cur_inode_size);
4985                 if (ret < 0)
4986                         goto out;
4987         }
4988
4989         if (need_chown) {
4990                 ret = send_chown(sctx, sctx->cur_ino, sctx->cur_inode_gen,
4991                                 left_uid, left_gid);
4992                 if (ret < 0)
4993                         goto out;
4994         }
4995         if (need_chmod) {
4996                 ret = send_chmod(sctx, sctx->cur_ino, sctx->cur_inode_gen,
4997                                 left_mode);
4998                 if (ret < 0)
4999                         goto out;
5000         }
5001
5002         /*
5003          * If other directory inodes depended on our current directory
5004          * inode's move/rename, now do their move/rename operations.
5005          */
5006         if (!is_waiting_for_move(sctx, sctx->cur_ino)) {
5007                 ret = apply_children_dir_moves(sctx);
5008                 if (ret)
5009                         goto out;
5010                 /*
5011                  * Need to send that every time, no matter if it actually
5012                  * changed between the two trees as we have done changes to
5013                  * the inode before. If our inode is a directory and it's
5014                  * waiting to be moved/renamed, we will send its utimes when
5015                  * it's moved/renamed, therefore we don't need to do it here.
5016                  */
5017                 sctx->send_progress = sctx->cur_ino + 1;
5018                 ret = send_utimes(sctx, sctx->cur_ino, sctx->cur_inode_gen);
5019                 if (ret < 0)
5020                         goto out;
5021         }
5022
5023 out:
5024         return ret;
5025 }
5026
5027 static int changed_inode(struct send_ctx *sctx,
5028                          enum btrfs_compare_tree_result result)
5029 {
5030         int ret = 0;
5031         struct btrfs_key *key = sctx->cmp_key;
5032         struct btrfs_inode_item *left_ii = NULL;
5033         struct btrfs_inode_item *right_ii = NULL;
5034         u64 left_gen = 0;
5035         u64 right_gen = 0;
5036
5037         sctx->cur_ino = key->objectid;
5038         sctx->cur_inode_new_gen = 0;
5039         sctx->cur_inode_last_extent = (u64)-1;
5040
5041         /*
5042          * Set send_progress to current inode. This will tell all get_cur_xxx
5043          * functions that the current inode's refs are not updated yet. Later,
5044          * when process_recorded_refs is finished, it is set to cur_ino + 1.
5045          */
5046         sctx->send_progress = sctx->cur_ino;
5047
5048         if (result == BTRFS_COMPARE_TREE_NEW ||
5049             result == BTRFS_COMPARE_TREE_CHANGED) {
5050                 left_ii = btrfs_item_ptr(sctx->left_path->nodes[0],
5051                                 sctx->left_path->slots[0],
5052                                 struct btrfs_inode_item);
5053                 left_gen = btrfs_inode_generation(sctx->left_path->nodes[0],
5054                                 left_ii);
5055         } else {
5056                 right_ii = btrfs_item_ptr(sctx->right_path->nodes[0],
5057                                 sctx->right_path->slots[0],
5058                                 struct btrfs_inode_item);
5059                 right_gen = btrfs_inode_generation(sctx->right_path->nodes[0],
5060                                 right_ii);
5061         }
5062         if (result == BTRFS_COMPARE_TREE_CHANGED) {
5063                 right_ii = btrfs_item_ptr(sctx->right_path->nodes[0],
5064                                 sctx->right_path->slots[0],
5065                                 struct btrfs_inode_item);
5066
5067                 right_gen = btrfs_inode_generation(sctx->right_path->nodes[0],
5068                                 right_ii);
5069
5070                 /*
5071                  * The cur_ino = root dir case is special here. We can't treat
5072                  * the inode as deleted+reused because it would generate a
5073                  * stream that tries to delete/mkdir the root dir.
5074                  */
5075                 if (left_gen != right_gen &&
5076                     sctx->cur_ino != BTRFS_FIRST_FREE_OBJECTID)
5077                         sctx->cur_inode_new_gen = 1;
5078         }
5079
5080         if (result == BTRFS_COMPARE_TREE_NEW) {
5081                 sctx->cur_inode_gen = left_gen;
5082                 sctx->cur_inode_new = 1;
5083                 sctx->cur_inode_deleted = 0;
5084                 sctx->cur_inode_size = btrfs_inode_size(
5085                                 sctx->left_path->nodes[0], left_ii);
5086                 sctx->cur_inode_mode = btrfs_inode_mode(
5087                                 sctx->left_path->nodes[0], left_ii);
5088                 sctx->cur_inode_rdev = btrfs_inode_rdev(
5089                                 sctx->left_path->nodes[0], left_ii);
5090                 if (sctx->cur_ino != BTRFS_FIRST_FREE_OBJECTID)
5091                         ret = send_create_inode_if_needed(sctx);
5092         } else if (result == BTRFS_COMPARE_TREE_DELETED) {
5093                 sctx->cur_inode_gen = right_gen;
5094                 sctx->cur_inode_new = 0;
5095                 sctx->cur_inode_deleted = 1;
5096                 sctx->cur_inode_size = btrfs_inode_size(
5097                                 sctx->right_path->nodes[0], right_ii);
5098                 sctx->cur_inode_mode = btrfs_inode_mode(
5099                                 sctx->right_path->nodes[0], right_ii);
5100         } else if (result == BTRFS_COMPARE_TREE_CHANGED) {
5101                 /*
5102                  * We need to do some special handling in case the inode was
5103                  * reported as changed with a changed generation number. This
5104                  * means that the original inode was deleted and new inode
5105                  * reused the same inum. So we have to treat the old inode as
5106                  * deleted and the new one as new.
5107                  */
5108                 if (sctx->cur_inode_new_gen) {
5109                         /*
5110                          * First, process the inode as if it was deleted.
5111                          */
5112                         sctx->cur_inode_gen = right_gen;
5113                         sctx->cur_inode_new = 0;
5114                         sctx->cur_inode_deleted = 1;
5115                         sctx->cur_inode_size = btrfs_inode_size(
5116                                         sctx->right_path->nodes[0], right_ii);
5117                         sctx->cur_inode_mode = btrfs_inode_mode(
5118                                         sctx->right_path->nodes[0], right_ii);
5119                         ret = process_all_refs(sctx,
5120                                         BTRFS_COMPARE_TREE_DELETED);
5121                         if (ret < 0)
5122                                 goto out;
5123
5124                         /*
5125                          * Now process the inode as if it was new.
5126                          */
5127                         sctx->cur_inode_gen = left_gen;
5128                         sctx->cur_inode_new = 1;
5129                         sctx->cur_inode_deleted = 0;
5130                         sctx->cur_inode_size = btrfs_inode_size(
5131                                         sctx->left_path->nodes[0], left_ii);
5132                         sctx->cur_inode_mode = btrfs_inode_mode(
5133                                         sctx->left_path->nodes[0], left_ii);
5134                         sctx->cur_inode_rdev = btrfs_inode_rdev(
5135                                         sctx->left_path->nodes[0], left_ii);
5136                         ret = send_create_inode_if_needed(sctx);
5137                         if (ret < 0)
5138                                 goto out;
5139
5140                         ret = process_all_refs(sctx, BTRFS_COMPARE_TREE_NEW);
5141                         if (ret < 0)
5142                                 goto out;
5143                         /*
5144                          * Advance send_progress now as we did not get into
5145                          * process_recorded_refs_if_needed in the new_gen case.
5146                          */
5147                         sctx->send_progress = sctx->cur_ino + 1;
5148
5149                         /*
5150                          * Now process all extents and xattrs of the inode as if
5151                          * they were all new.
5152                          */
5153                         ret = process_all_extents(sctx);
5154                         if (ret < 0)
5155                                 goto out;
5156                         ret = process_all_new_xattrs(sctx);
5157                         if (ret < 0)
5158                                 goto out;
5159                 } else {
5160                         sctx->cur_inode_gen = left_gen;
5161                         sctx->cur_inode_new = 0;
5162                         sctx->cur_inode_new_gen = 0;
5163                         sctx->cur_inode_deleted = 0;
5164                         sctx->cur_inode_size = btrfs_inode_size(
5165                                         sctx->left_path->nodes[0], left_ii);
5166                         sctx->cur_inode_mode = btrfs_inode_mode(
5167                                         sctx->left_path->nodes[0], left_ii);
5168                 }
5169         }
5170
5171 out:
5172         return ret;
5173 }
5174
5175 /*
5176  * We have to process new refs before deleted refs, but compare_trees gives us
5177  * the new and deleted refs mixed. To fix this, we record the new/deleted refs
5178  * first and later process them in process_recorded_refs.
5179  * For the cur_inode_new_gen case, we skip recording completely because
5180  * changed_inode did already initiate processing of refs. The reason for this is
5181  * that in this case, compare_tree actually compares the refs of 2 different
5182  * inodes. To fix this, process_all_refs is used in changed_inode to handle all
5183  * refs of the right tree as deleted and all refs of the left tree as new.
5184  */
5185 static int changed_ref(struct send_ctx *sctx,
5186                        enum btrfs_compare_tree_result result)
5187 {
5188         int ret = 0;
5189
5190         BUG_ON(sctx->cur_ino != sctx->cmp_key->objectid);
5191
5192         if (!sctx->cur_inode_new_gen &&
5193             sctx->cur_ino != BTRFS_FIRST_FREE_OBJECTID) {
5194                 if (result == BTRFS_COMPARE_TREE_NEW)
5195                         ret = record_new_ref(sctx);
5196                 else if (result == BTRFS_COMPARE_TREE_DELETED)
5197                         ret = record_deleted_ref(sctx);
5198                 else if (result == BTRFS_COMPARE_TREE_CHANGED)
5199                         ret = record_changed_ref(sctx);
5200         }
5201
5202         return ret;
5203 }
5204
5205 /*
5206  * Process new/deleted/changed xattrs. We skip processing in the
5207  * cur_inode_new_gen case because changed_inode did already initiate processing
5208  * of xattrs. The reason is the same as in changed_ref
5209  */
5210 static int changed_xattr(struct send_ctx *sctx,
5211                          enum btrfs_compare_tree_result result)
5212 {
5213         int ret = 0;
5214
5215         BUG_ON(sctx->cur_ino != sctx->cmp_key->objectid);
5216
5217         if (!sctx->cur_inode_new_gen && !sctx->cur_inode_deleted) {
5218                 if (result == BTRFS_COMPARE_TREE_NEW)
5219                         ret = process_new_xattr(sctx);
5220                 else if (result == BTRFS_COMPARE_TREE_DELETED)
5221                         ret = process_deleted_xattr(sctx);
5222                 else if (result == BTRFS_COMPARE_TREE_CHANGED)
5223                         ret = process_changed_xattr(sctx);
5224         }
5225
5226         return ret;
5227 }
5228
5229 /*
5230  * Process new/deleted/changed extents. We skip processing in the
5231  * cur_inode_new_gen case because changed_inode did already initiate processing
5232  * of extents. The reason is the same as in changed_ref
5233  */
5234 static int changed_extent(struct send_ctx *sctx,
5235                           enum btrfs_compare_tree_result result)
5236 {
5237         int ret = 0;
5238
5239         BUG_ON(sctx->cur_ino != sctx->cmp_key->objectid);
5240
5241         if (!sctx->cur_inode_new_gen && !sctx->cur_inode_deleted) {
5242                 if (result != BTRFS_COMPARE_TREE_DELETED)
5243                         ret = process_extent(sctx, sctx->left_path,
5244                                         sctx->cmp_key);
5245         }
5246
5247         return ret;
5248 }
5249
5250 static int dir_changed(struct send_ctx *sctx, u64 dir)
5251 {
5252         u64 orig_gen, new_gen;
5253         int ret;
5254
5255         ret = get_inode_info(sctx->send_root, dir, NULL, &new_gen, NULL, NULL,
5256                              NULL, NULL);
5257         if (ret)
5258                 return ret;
5259
5260         ret = get_inode_info(sctx->parent_root, dir, NULL, &orig_gen, NULL,
5261                              NULL, NULL, NULL);
5262         if (ret)
5263                 return ret;
5264
5265         return (orig_gen != new_gen) ? 1 : 0;
5266 }
5267
5268 static int compare_refs(struct send_ctx *sctx, struct btrfs_path *path,
5269                         struct btrfs_key *key)
5270 {
5271         struct btrfs_inode_extref *extref;
5272         struct extent_buffer *leaf;
5273         u64 dirid = 0, last_dirid = 0;
5274         unsigned long ptr;
5275         u32 item_size;
5276         u32 cur_offset = 0;
5277         int ref_name_len;
5278         int ret = 0;
5279
5280         /* Easy case, just check this one dirid */
5281         if (key->type == BTRFS_INODE_REF_KEY) {
5282                 dirid = key->offset;
5283
5284                 ret = dir_changed(sctx, dirid);
5285                 goto out;
5286         }
5287
5288         leaf = path->nodes[0];
5289         item_size = btrfs_item_size_nr(leaf, path->slots[0]);
5290         ptr = btrfs_item_ptr_offset(leaf, path->slots[0]);
5291         while (cur_offset < item_size) {
5292                 extref = (struct btrfs_inode_extref *)(ptr +
5293                                                        cur_offset);
5294                 dirid = btrfs_inode_extref_parent(leaf, extref);
5295                 ref_name_len = btrfs_inode_extref_name_len(leaf, extref);
5296                 cur_offset += ref_name_len + sizeof(*extref);
5297                 if (dirid == last_dirid)
5298                         continue;
5299                 ret = dir_changed(sctx, dirid);
5300                 if (ret)
5301                         break;
5302                 last_dirid = dirid;
5303         }
5304 out:
5305         return ret;
5306 }
5307
5308 /*
5309  * Updates compare related fields in sctx and simply forwards to the actual
5310  * changed_xxx functions.
5311  */
5312 static int changed_cb(struct btrfs_root *left_root,
5313                       struct btrfs_root *right_root,
5314                       struct btrfs_path *left_path,
5315                       struct btrfs_path *right_path,
5316                       struct btrfs_key *key,
5317                       enum btrfs_compare_tree_result result,
5318                       void *ctx)
5319 {
5320         int ret = 0;
5321         struct send_ctx *sctx = ctx;
5322
5323         if (result == BTRFS_COMPARE_TREE_SAME) {
5324                 if (key->type == BTRFS_INODE_REF_KEY ||
5325                     key->type == BTRFS_INODE_EXTREF_KEY) {
5326                         ret = compare_refs(sctx, left_path, key);
5327                         if (!ret)
5328                                 return 0;
5329                         if (ret < 0)
5330                                 return ret;
5331                 } else if (key->type == BTRFS_EXTENT_DATA_KEY) {
5332                         return maybe_send_hole(sctx, left_path, key);
5333                 } else {
5334                         return 0;
5335                 }
5336                 result = BTRFS_COMPARE_TREE_CHANGED;
5337                 ret = 0;
5338         }
5339
5340         sctx->left_path = left_path;
5341         sctx->right_path = right_path;
5342         sctx->cmp_key = key;
5343
5344         ret = finish_inode_if_needed(sctx, 0);
5345         if (ret < 0)
5346                 goto out;
5347
5348         /* Ignore non-FS objects */
5349         if (key->objectid == BTRFS_FREE_INO_OBJECTID ||
5350             key->objectid == BTRFS_FREE_SPACE_OBJECTID)
5351                 goto out;
5352
5353         if (key->type == BTRFS_INODE_ITEM_KEY)
5354                 ret = changed_inode(sctx, result);
5355         else if (key->type == BTRFS_INODE_REF_KEY ||
5356                  key->type == BTRFS_INODE_EXTREF_KEY)
5357                 ret = changed_ref(sctx, result);
5358         else if (key->type == BTRFS_XATTR_ITEM_KEY)
5359                 ret = changed_xattr(sctx, result);
5360         else if (key->type == BTRFS_EXTENT_DATA_KEY)
5361                 ret = changed_extent(sctx, result);
5362
5363 out:
5364         return ret;
5365 }
5366
5367 static int full_send_tree(struct send_ctx *sctx)
5368 {
5369         int ret;
5370         struct btrfs_trans_handle *trans = NULL;
5371         struct btrfs_root *send_root = sctx->send_root;
5372         struct btrfs_key key;
5373         struct btrfs_key found_key;
5374         struct btrfs_path *path;
5375         struct extent_buffer *eb;
5376         int slot;
5377         u64 start_ctransid;
5378         u64 ctransid;
5379
5380         path = alloc_path_for_send();
5381         if (!path)
5382                 return -ENOMEM;
5383
5384         spin_lock(&send_root->root_item_lock);
5385         start_ctransid = btrfs_root_ctransid(&send_root->root_item);
5386         spin_unlock(&send_root->root_item_lock);
5387
5388         key.objectid = BTRFS_FIRST_FREE_OBJECTID;
5389         key.type = BTRFS_INODE_ITEM_KEY;
5390         key.offset = 0;
5391
5392 join_trans:
5393         /*
5394          * We need to make sure the transaction does not get committed
5395          * while we do anything on commit roots. Join a transaction to prevent
5396          * this.
5397          */
5398         trans = btrfs_join_transaction(send_root);
5399         if (IS_ERR(trans)) {
5400                 ret = PTR_ERR(trans);
5401                 trans = NULL;
5402                 goto out;
5403         }
5404
5405         /*
5406          * Make sure the tree has not changed after re-joining. We detect this
5407          * by comparing start_ctransid and ctransid. They should always match.
5408          */
5409         spin_lock(&send_root->root_item_lock);
5410         ctransid = btrfs_root_ctransid(&send_root->root_item);
5411         spin_unlock(&send_root->root_item_lock);
5412
5413         if (ctransid != start_ctransid) {
5414                 WARN(1, KERN_WARNING "BTRFS: the root that you're trying to "
5415                                      "send was modified in between. This is "
5416                                      "probably a bug.\n");
5417                 ret = -EIO;
5418                 goto out;
5419         }
5420
5421         ret = btrfs_search_slot_for_read(send_root, &key, path, 1, 0);
5422         if (ret < 0)
5423                 goto out;
5424         if (ret)
5425                 goto out_finish;
5426
5427         while (1) {
5428                 /*
5429                  * When someone want to commit while we iterate, end the
5430                  * joined transaction and rejoin.
5431                  */
5432                 if (btrfs_should_end_transaction(trans, send_root)) {
5433                         ret = btrfs_end_transaction(trans, send_root);
5434                         trans = NULL;
5435                         if (ret < 0)
5436                                 goto out;
5437                         btrfs_release_path(path);
5438                         goto join_trans;
5439                 }
5440
5441                 eb = path->nodes[0];
5442                 slot = path->slots[0];
5443                 btrfs_item_key_to_cpu(eb, &found_key, slot);
5444
5445                 ret = changed_cb(send_root, NULL, path, NULL,
5446                                 &found_key, BTRFS_COMPARE_TREE_NEW, sctx);
5447                 if (ret < 0)
5448                         goto out;
5449
5450                 key.objectid = found_key.objectid;
5451                 key.type = found_key.type;
5452                 key.offset = found_key.offset + 1;
5453
5454                 ret = btrfs_next_item(send_root, path);
5455                 if (ret < 0)
5456                         goto out;
5457                 if (ret) {
5458                         ret  = 0;
5459                         break;
5460                 }
5461         }
5462
5463 out_finish:
5464         ret = finish_inode_if_needed(sctx, 1);
5465
5466 out:
5467         btrfs_free_path(path);
5468         if (trans) {
5469                 if (!ret)
5470                         ret = btrfs_end_transaction(trans, send_root);
5471                 else
5472                         btrfs_end_transaction(trans, send_root);
5473         }
5474         return ret;
5475 }
5476
5477 static int send_subvol(struct send_ctx *sctx)
5478 {
5479         int ret;
5480
5481         if (!(sctx->flags & BTRFS_SEND_FLAG_OMIT_STREAM_HEADER)) {
5482                 ret = send_header(sctx);
5483                 if (ret < 0)
5484                         goto out;
5485         }
5486
5487         ret = send_subvol_begin(sctx);
5488         if (ret < 0)
5489                 goto out;
5490
5491         if (sctx->parent_root) {
5492                 ret = btrfs_compare_trees(sctx->send_root, sctx->parent_root,
5493                                 changed_cb, sctx);
5494                 if (ret < 0)
5495                         goto out;
5496                 ret = finish_inode_if_needed(sctx, 1);
5497                 if (ret < 0)
5498                         goto out;
5499         } else {
5500                 ret = full_send_tree(sctx);
5501                 if (ret < 0)
5502                         goto out;
5503         }
5504
5505 out:
5506         free_recorded_refs(sctx);
5507         return ret;
5508 }
5509
5510 static void btrfs_root_dec_send_in_progress(struct btrfs_root* root)
5511 {
5512         spin_lock(&root->root_item_lock);
5513         root->send_in_progress--;
5514         /*
5515          * Not much left to do, we don't know why it's unbalanced and
5516          * can't blindly reset it to 0.
5517          */
5518         if (root->send_in_progress < 0)
5519                 btrfs_err(root->fs_info,
5520                         "send_in_progres unbalanced %d root %llu\n",
5521                         root->send_in_progress, root->root_key.objectid);
5522         spin_unlock(&root->root_item_lock);
5523 }
5524
5525 long btrfs_ioctl_send(struct file *mnt_file, void __user *arg_)
5526 {
5527         int ret = 0;
5528         struct btrfs_root *send_root;
5529         struct btrfs_root *clone_root;
5530         struct btrfs_fs_info *fs_info;
5531         struct btrfs_ioctl_send_args *arg = NULL;
5532         struct btrfs_key key;
5533         struct send_ctx *sctx = NULL;
5534         u32 i;
5535         u64 *clone_sources_tmp = NULL;
5536         int clone_sources_to_rollback = 0;
5537         int sort_clone_roots = 0;
5538         int index;
5539
5540         if (!capable(CAP_SYS_ADMIN))
5541                 return -EPERM;
5542
5543         send_root = BTRFS_I(file_inode(mnt_file))->root;
5544         fs_info = send_root->fs_info;
5545
5546         /*
5547          * The subvolume must remain read-only during send, protect against
5548          * making it RW.
5549          */
5550         spin_lock(&send_root->root_item_lock);
5551         send_root->send_in_progress++;
5552         spin_unlock(&send_root->root_item_lock);
5553
5554         /*
5555          * This is done when we lookup the root, it should already be complete
5556          * by the time we get here.
5557          */
5558         WARN_ON(send_root->orphan_cleanup_state != ORPHAN_CLEANUP_DONE);
5559
5560         /*
5561          * Userspace tools do the checks and warn the user if it's
5562          * not RO.
5563          */
5564         if (!btrfs_root_readonly(send_root)) {
5565                 ret = -EPERM;
5566                 goto out;
5567         }
5568
5569         arg = memdup_user(arg_, sizeof(*arg));
5570         if (IS_ERR(arg)) {
5571                 ret = PTR_ERR(arg);
5572                 arg = NULL;
5573                 goto out;
5574         }
5575
5576         if (!access_ok(VERIFY_READ, arg->clone_sources,
5577                         sizeof(*arg->clone_sources) *
5578                         arg->clone_sources_count)) {
5579                 ret = -EFAULT;
5580                 goto out;
5581         }
5582
5583         if (arg->flags & ~BTRFS_SEND_FLAG_MASK) {
5584                 ret = -EINVAL;
5585                 goto out;
5586         }
5587
5588         sctx = kzalloc(sizeof(struct send_ctx), GFP_NOFS);
5589         if (!sctx) {
5590                 ret = -ENOMEM;
5591                 goto out;
5592         }
5593
5594         INIT_LIST_HEAD(&sctx->new_refs);
5595         INIT_LIST_HEAD(&sctx->deleted_refs);
5596         INIT_RADIX_TREE(&sctx->name_cache, GFP_NOFS);
5597         INIT_LIST_HEAD(&sctx->name_cache_list);
5598
5599         sctx->flags = arg->flags;
5600
5601         sctx->send_filp = fget(arg->send_fd);
5602         if (!sctx->send_filp) {
5603                 ret = -EBADF;
5604                 goto out;
5605         }
5606
5607         sctx->send_root = send_root;
5608         sctx->clone_roots_cnt = arg->clone_sources_count;
5609
5610         sctx->send_max_size = BTRFS_SEND_BUF_SIZE;
5611         sctx->send_buf = vmalloc(sctx->send_max_size);
5612         if (!sctx->send_buf) {
5613                 ret = -ENOMEM;
5614                 goto out;
5615         }
5616
5617         sctx->read_buf = vmalloc(BTRFS_SEND_READ_SIZE);
5618         if (!sctx->read_buf) {
5619                 ret = -ENOMEM;
5620                 goto out;
5621         }
5622
5623         sctx->pending_dir_moves = RB_ROOT;
5624         sctx->waiting_dir_moves = RB_ROOT;
5625         sctx->orphan_dirs = RB_ROOT;
5626
5627         sctx->clone_roots = vzalloc(sizeof(struct clone_root) *
5628                         (arg->clone_sources_count + 1));
5629         if (!sctx->clone_roots) {
5630                 ret = -ENOMEM;
5631                 goto out;
5632         }
5633
5634         if (arg->clone_sources_count) {
5635                 clone_sources_tmp = vmalloc(arg->clone_sources_count *
5636                                 sizeof(*arg->clone_sources));
5637                 if (!clone_sources_tmp) {
5638                         ret = -ENOMEM;
5639                         goto out;
5640                 }
5641
5642                 ret = copy_from_user(clone_sources_tmp, arg->clone_sources,
5643                                 arg->clone_sources_count *
5644                                 sizeof(*arg->clone_sources));
5645                 if (ret) {
5646                         ret = -EFAULT;
5647                         goto out;
5648                 }
5649
5650                 for (i = 0; i < arg->clone_sources_count; i++) {
5651                         key.objectid = clone_sources_tmp[i];
5652                         key.type = BTRFS_ROOT_ITEM_KEY;
5653                         key.offset = (u64)-1;
5654
5655                         index = srcu_read_lock(&fs_info->subvol_srcu);
5656
5657                         clone_root = btrfs_read_fs_root_no_name(fs_info, &key);
5658                         if (IS_ERR(clone_root)) {
5659                                 srcu_read_unlock(&fs_info->subvol_srcu, index);
5660                                 ret = PTR_ERR(clone_root);
5661                                 goto out;
5662                         }
5663                         clone_sources_to_rollback = i + 1;
5664                         spin_lock(&clone_root->root_item_lock);
5665                         clone_root->send_in_progress++;
5666                         if (!btrfs_root_readonly(clone_root)) {
5667                                 spin_unlock(&clone_root->root_item_lock);
5668                                 srcu_read_unlock(&fs_info->subvol_srcu, index);
5669                                 ret = -EPERM;
5670                                 goto out;
5671                         }
5672                         spin_unlock(&clone_root->root_item_lock);
5673                         srcu_read_unlock(&fs_info->subvol_srcu, index);
5674
5675                         sctx->clone_roots[i].root = clone_root;
5676                 }
5677                 vfree(clone_sources_tmp);
5678                 clone_sources_tmp = NULL;
5679         }
5680
5681         if (arg->parent_root) {
5682                 key.objectid = arg->parent_root;
5683                 key.type = BTRFS_ROOT_ITEM_KEY;
5684                 key.offset = (u64)-1;
5685
5686                 index = srcu_read_lock(&fs_info->subvol_srcu);
5687
5688                 sctx->parent_root = btrfs_read_fs_root_no_name(fs_info, &key);
5689                 if (IS_ERR(sctx->parent_root)) {
5690                         srcu_read_unlock(&fs_info->subvol_srcu, index);
5691                         ret = PTR_ERR(sctx->parent_root);
5692                         goto out;
5693                 }
5694
5695                 spin_lock(&sctx->parent_root->root_item_lock);
5696                 sctx->parent_root->send_in_progress++;
5697                 if (!btrfs_root_readonly(sctx->parent_root)) {
5698                         spin_unlock(&sctx->parent_root->root_item_lock);
5699                         srcu_read_unlock(&fs_info->subvol_srcu, index);
5700                         ret = -EPERM;
5701                         goto out;
5702                 }
5703                 spin_unlock(&sctx->parent_root->root_item_lock);
5704
5705                 srcu_read_unlock(&fs_info->subvol_srcu, index);
5706         }
5707
5708         /*
5709          * Clones from send_root are allowed, but only if the clone source
5710          * is behind the current send position. This is checked while searching
5711          * for possible clone sources.
5712          */
5713         sctx->clone_roots[sctx->clone_roots_cnt++].root = sctx->send_root;
5714
5715         /* We do a bsearch later */
5716         sort(sctx->clone_roots, sctx->clone_roots_cnt,
5717                         sizeof(*sctx->clone_roots), __clone_root_cmp_sort,
5718                         NULL);
5719         sort_clone_roots = 1;
5720
5721         ret = send_subvol(sctx);
5722         if (ret < 0)
5723                 goto out;
5724
5725         if (!(sctx->flags & BTRFS_SEND_FLAG_OMIT_END_CMD)) {
5726                 ret = begin_cmd(sctx, BTRFS_SEND_C_END);
5727                 if (ret < 0)
5728                         goto out;
5729                 ret = send_cmd(sctx);
5730                 if (ret < 0)
5731                         goto out;
5732         }
5733
5734 out:
5735         WARN_ON(sctx && !ret && !RB_EMPTY_ROOT(&sctx->pending_dir_moves));
5736         while (sctx && !RB_EMPTY_ROOT(&sctx->pending_dir_moves)) {
5737                 struct rb_node *n;
5738                 struct pending_dir_move *pm;
5739
5740                 n = rb_first(&sctx->pending_dir_moves);
5741                 pm = rb_entry(n, struct pending_dir_move, node);
5742                 while (!list_empty(&pm->list)) {
5743                         struct pending_dir_move *pm2;
5744
5745                         pm2 = list_first_entry(&pm->list,
5746                                                struct pending_dir_move, list);
5747                         free_pending_move(sctx, pm2);
5748                 }
5749                 free_pending_move(sctx, pm);
5750         }
5751
5752         WARN_ON(sctx && !ret && !RB_EMPTY_ROOT(&sctx->waiting_dir_moves));
5753         while (sctx && !RB_EMPTY_ROOT(&sctx->waiting_dir_moves)) {
5754                 struct rb_node *n;
5755                 struct waiting_dir_move *dm;
5756
5757                 n = rb_first(&sctx->waiting_dir_moves);
5758                 dm = rb_entry(n, struct waiting_dir_move, node);
5759                 rb_erase(&dm->node, &sctx->waiting_dir_moves);
5760                 kfree(dm);
5761         }
5762
5763         WARN_ON(sctx && !ret && !RB_EMPTY_ROOT(&sctx->orphan_dirs));
5764         while (sctx && !RB_EMPTY_ROOT(&sctx->orphan_dirs)) {
5765                 struct rb_node *n;
5766                 struct orphan_dir_info *odi;
5767
5768                 n = rb_first(&sctx->orphan_dirs);
5769                 odi = rb_entry(n, struct orphan_dir_info, node);
5770                 free_orphan_dir_info(sctx, odi);
5771         }
5772
5773         if (sort_clone_roots) {
5774                 for (i = 0; i < sctx->clone_roots_cnt; i++)
5775                         btrfs_root_dec_send_in_progress(
5776                                         sctx->clone_roots[i].root);
5777         } else {
5778                 for (i = 0; sctx && i < clone_sources_to_rollback; i++)
5779                         btrfs_root_dec_send_in_progress(
5780                                         sctx->clone_roots[i].root);
5781
5782                 btrfs_root_dec_send_in_progress(send_root);
5783         }
5784         if (sctx && !IS_ERR_OR_NULL(sctx->parent_root))
5785                 btrfs_root_dec_send_in_progress(sctx->parent_root);
5786
5787         kfree(arg);
5788         vfree(clone_sources_tmp);
5789
5790         if (sctx) {
5791                 if (sctx->send_filp)
5792                         fput(sctx->send_filp);
5793
5794                 vfree(sctx->clone_roots);
5795                 vfree(sctx->send_buf);
5796                 vfree(sctx->read_buf);
5797
5798                 name_cache_free(sctx);
5799
5800                 kfree(sctx);
5801         }
5802
5803         return ret;
5804 }