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

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

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

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

kernel.org | git.kernel.org | LWN.net | Project Home | Wiki (Japanese) | Wiki (English) | SVN repository | Mail admin

Linux® is a registered trademark of Linus Torvalds in the United States and other countries.
TOMOYO® is a registered trademark of NTT DATA CORPORATION.

osdn.jp