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