fs/btrfs/send.c

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