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