~ [ source navigation ] ~ [ diff markup ] ~ [ identifier search ] ~

TOMOYO Linux Cross Reference
Linux/fs/btrfs/send.c

Version: ~ [ linux-5.6 ] ~ [ linux-5.5.13 ] ~ [ linux-5.4.28 ] ~ [ linux-5.3.18 ] ~ [ linux-5.2.21 ] ~ [ linux-5.1.21 ] ~ [ linux-5.0.21 ] ~ [ linux-4.20.17 ] ~ [ linux-4.19.113 ] ~ [ linux-4.18.20 ] ~ [ linux-4.17.19 ] ~ [ linux-4.16.18 ] ~ [ linux-4.15.18 ] ~ [ linux-4.14.174 ] ~ [ linux-4.13.16 ] ~ [ linux-4.12.14 ] ~ [ linux-4.11.12 ] ~ [ linux-4.10.17 ] ~ [ linux-4.9.217 ] ~ [ linux-4.8.17 ] ~ [ linux-4.7.10 ] ~ [ linux-4.6.7 ] ~ [ linux-4.5.7 ] ~ [ linux-4.4.217 ] ~ [ linux-4.3.6 ] ~ [ linux-4.2.8 ] ~ [ linux-4.1.52 ] ~ [ linux-4.0.9 ] ~ [ linux-3.19.8 ] ~ [ linux-3.18.140 ] ~ [ linux-3.17.8 ] ~ [ linux-3.16.82 ] ~ [ linux-3.15.10 ] ~ [ linux-3.14.79 ] ~ [ linux-3.13.11 ] ~ [ linux-3.12.74 ] ~ [ linux-3.11.10 ] ~ [ linux-3.10.108 ] ~ [ linux-3.9.11 ] ~ [ linux-3.8.13 ] ~ [ linux-3.7.10 ] ~ [ linux-3.6.11 ] ~ [ linux-3.5.7 ] ~ [ linux-3.4.113 ] ~ [ linux-3.3.8 ] ~ [ linux-3.2.102 ] ~ [ linux-3.1.10 ] ~ [ linux-3.0.101 ] ~ [ linux-2.6.32.71 ] ~ [ linux-2.6.0 ] ~ [ linux-2.4.37.11 ] ~ [ unix-v6-master ] ~ [ ccs-tools-1.8.5 ] ~ [ policy-sample ] ~
Architecture: ~ [ i386 ] ~ [ alpha ] ~ [ m68k ] ~ [ mips ] ~ [ ppc ] ~ [ sparc ] ~ [ sparc64 ] ~

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