#! /bin/bash
# FS QA Test No. btrfs/087
#
# Test a very complex scenario for a btrfs incremental send operation where a
# large directory hierarchy had many subtrees moved between parent directories,
# preserving the names of some directories and inverting the parent-child
# relationship between some directories (a child in the parent snapshot became
# a parent, in the send snapshot, of the directory that is its parent in the
# parent snapshot).
#
# This test made the incremental send fail with -ENOMEM because it entered an
# infinite loop when building path strings that are used as operands of the
# rename operations issued in the send stream.
# This issue was fixed by the following linux kernel btrfs patch:
#
#   Btrfs: incremental send, don't delay directory renames unnecessarily
#
#-----------------------------------------------------------------------
# Copyright (C) 2015 SUSE Linux Products GmbH. All Rights Reserved.
# Author: Filipe Manana <fdmanana@suse.com>
#
# This program is free software; you can redistribute it and/or
# modify it under the terms of the GNU General Public License as
# published by the Free Software Foundation.
#
# This program is distributed in the hope that it would be useful,
# but WITHOUT ANY WARRANTY; without even the implied warranty of
# MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
# GNU General Public License for more details.
#
# You should have received a copy of the GNU General Public License
# along with this program; if not, write the Free Software Foundation,
# Inc.,  51 Franklin St, Fifth Floor, Boston, MA  02110-1301  USA
#-----------------------------------------------------------------------
#

seq=`basename $0`
seqres=$RESULT_DIR/$seq
echo "QA output created by $seq"

tmp=/tmp/$$
status=1	# failure is the default!
trap "_cleanup; exit \$status" 0 1 2 3 15

_cleanup()
{
	rm -fr $send_files_dir
	rm -f $tmp.*
}

# get standard environment, filters and checks
. ./common/rc
. ./common/filter

# real QA test starts here
_supported_fs btrfs
_supported_os Linux
_require_scratch
_require_fssum

send_files_dir=$TEST_DIR/btrfs-test-$seq

rm -f $seqres.full
rm -fr $send_files_dir
mkdir $send_files_dir

_scratch_mkfs >>$seqres.full 2>&1
_scratch_mount

mkdir $SCRATCH_MNT/data
mkdir $SCRATCH_MNT/data/n1
mkdir $SCRATCH_MNT/data/n1/n2
mkdir $SCRATCH_MNT/data/n4
mkdir $SCRATCH_MNT/data/n1/n2/p1
mkdir $SCRATCH_MNT/data/n1/n2/p1/p2
mkdir $SCRATCH_MNT/data/t6
mkdir $SCRATCH_MNT/data/t7
mkdir -p $SCRATCH_MNT/data/t5/t7
mkdir $SCRATCH_MNT/data/t2
mkdir $SCRATCH_MNT/data/t4
mkdir -p $SCRATCH_MNT/data/t1/t3
mkdir $SCRATCH_MNT/data/p1
mv $SCRATCH_MNT/data/t1 $SCRATCH_MNT/data/p1
mkdir -p $SCRATCH_MNT/data/p1/p2
mv $SCRATCH_MNT/data/t4 $SCRATCH_MNT/data/p1/p2/t1
mv $SCRATCH_MNT/data/t5 $SCRATCH_MNT/data/n4/t5
mv $SCRATCH_MNT/data/n1/n2/p1/p2 $SCRATCH_MNT/data/n4/t5/p2
mv $SCRATCH_MNT/data/t7 $SCRATCH_MNT/data/n4/t5/p2/t7
mv $SCRATCH_MNT/data/t2 $SCRATCH_MNT/data/n4/t1
mv $SCRATCH_MNT/data/p1 $SCRATCH_MNT/data/n4/t5/p2/p1
mv $SCRATCH_MNT/data/n1/n2 $SCRATCH_MNT/data/n4/t5/p2/p1/p2/n2
mv $SCRATCH_MNT/data/n4/t5/p2/p1/p2/t1 $SCRATCH_MNT/data/n4/t5/p2/p1/p2/n2/t1
mv $SCRATCH_MNT/data/n4/t5/t7 $SCRATCH_MNT/data/n4/t5/p2/p1/p2/n2/t1/t7
mv $SCRATCH_MNT/data/n4/t5/p2/p1/t1/t3 $SCRATCH_MNT/data/n4/t5/p2/p1/p2/n2/t1/t3
mv $SCRATCH_MNT/data/n4/t5/p2/p1/p2/n2/p1 \
	$SCRATCH_MNT/data/n4/t5/p2/p1/p2/n2/t1/t7/p1
mv $SCRATCH_MNT/data/t6 $SCRATCH_MNT/data/n4/t5/p2/p1/p2/n2/t1/t3/t5
mv $SCRATCH_MNT/data/n4/t5/p2/p1/t1 $SCRATCH_MNT/data/n4/t5/p2/p1/p2/n2/t1/t3/t1
mv $SCRATCH_MNT/data/n1 $SCRATCH_MNT/data/n4/t5/p2/p1/p2/n2/t1/t7/p1/n1

# Filesystem looks like:
#
# .                                                             (ino 256)
# |--- data/                                                    (ino 257)
#        |--- n4/                                               (ino 260)
#             |--- t1/                                          (ino 267)
#             |--- t5/                                          (ino 265)
#                  |--- p2/                                     (ino 262)
#                       |--- p1/                                (ino 271)
#                       |    |--- p2/                           (ino 272)
#                       |         |--- n2/                      (ino 259)
#                       |              |--- t1/                 (ino 268)
#                       |                   |--- t3/            (ino 270)
#                       |                   |    |--- t1/       (ino 269)
#                       |                   |    |--- t5/       (ino 263)
#                       |                   |
#                       |                   |--- t7/            (ino 266)
#                       |                        |--- p1/       (ino 261)
#                       |                             |--- n1   (ino 258)
#                       |
#                       |--- t7/                                (ino 264)
#
_run_btrfs_util_prog subvolume snapshot -r $SCRATCH_MNT $SCRATCH_MNT/mysnap1

# The following sequence of directory renames resulted in an infinite path build
# loop when attempting to build the path for inode 266. This is because the
# inode's new parent, inode 261, was part of a circular dependency of delayed
# rename operations. This circular dependency should jave never been built (it
# happened due to a bug), and was the following:
#
#   ino 272 <- ino 261 <- ino 259 <- ino 268 <- ino 267 <- ino 261
#
# Where the notation "X <- Y" means that rename of inode X is delayed to happen
# after the rename of inode Y.

mv $SCRATCH_MNT/data/n4/t1 $SCRATCH_MNT/data/n4/t5/p2/p1/p2/n2/t1/t7/p1/t1
mv $SCRATCH_MNT/data/n4/t5/p2/p1/p2/n2/t1 $SCRATCH_MNT/data/n4/
mv $SCRATCH_MNT/data/n4/t5/p2/p1/p2/n2 $SCRATCH_MNT/data/n4/t1/n2
mv $SCRATCH_MNT/data/n4/t1/t7/p1 $SCRATCH_MNT/data/n4/t1/n2/p1
mv $SCRATCH_MNT/data/n4/t1/t3/t1 $SCRATCH_MNT/data/n4/t1/n2/t1
mv $SCRATCH_MNT/data/n4/t1/t3 $SCRATCH_MNT/data/n4/t1/n2/t1/t3
mv $SCRATCH_MNT/data/n4/t5/p2/p1/p2 $SCRATCH_MNT/data/n4/t1/n2/p1/p2
mv $SCRATCH_MNT/data/n4/t1/t7 $SCRATCH_MNT/data/n4/t1/n2/p1/t7
mv $SCRATCH_MNT/data/n4/t5/p2/p1 $SCRATCH_MNT/data/n4/t1/n2/p1/p2/p1
mv $SCRATCH_MNT/data/n4/t1/n2/t1/t3/t5 $SCRATCH_MNT/data/n4/t1/n2/p1/p2/t5
mv $SCRATCH_MNT/data/n4/t5 $SCRATCH_MNT/data/n4/t1/n2/p1/p2/p1/t5
mv $SCRATCH_MNT/data/n4/t1/n2/p1/p2/p1/t5/p2 \
	$SCRATCH_MNT/data/n4/t1/n2/p1/p2/p1/p2
mv $SCRATCH_MNT/data/n4/t1/n2/p1/p2/p1/p2/t7 $SCRATCH_MNT/data/n4/t1/t7

# Filesystem now looks like:
#
# .                                                   (ino 256)
# |--- data                                           (ino 257)
#        |--- n4/                                     (ino 260)
#             |--- t1/                                (ino 268)
#                  |--- n2/                           (ino 259)
#                  |    |--- p1/                      (ino 261)
#                  |    |    |--- n1/                 (ino 258)
#                  |    |    |--- p2/                 (ino 272)
#                  |    |    |    |--- p1/            (ino 271)
#                  |    |    |    |    |--- p2/       (ino 262)
#                  |    |    |    |    |--- t5/       (ino 265)
#                  |    |    |    |
#                  |    |    |    |--- t5/            (ino 263)
#                  |    |    |
#                  |    |    |--- t1/                 (ino 267)
#                  |    |    |--- t7/                 (ino 266)
#                  |    |
#                  |    |--- t1/                      (ino 269)
#                  |         |--- t3/                 (ino 270)
#                  |
#                  |--- t7/                           (ino 264)
#
_run_btrfs_util_prog subvolume snapshot -r $SCRATCH_MNT $SCRATCH_MNT/mysnap2

run_check $FSSUM_PROG -A -f -w $send_files_dir/1.fssum $SCRATCH_MNT/mysnap1
run_check $FSSUM_PROG -A -f -w $send_files_dir/2.fssum \
	-x $SCRATCH_MNT/mysnap2/mysnap1 $SCRATCH_MNT/mysnap2

_run_btrfs_util_prog send $SCRATCH_MNT/mysnap1 -f $send_files_dir/1.snap
_run_btrfs_util_prog send -p $SCRATCH_MNT/mysnap1 $SCRATCH_MNT/mysnap2 \
	-f $send_files_dir/2.snap

# Now recreate the filesystem by receiving both send streams and verify we get
# the same content that the original filesystem had.
_scratch_unmount
_scratch_mkfs >>$seqres.full 2>&1
_scratch_mount

_run_btrfs_util_prog receive $SCRATCH_MNT -f $send_files_dir/1.snap
run_check $FSSUM_PROG -r $send_files_dir/1.fssum $SCRATCH_MNT/mysnap1
_run_btrfs_util_prog receive $SCRATCH_MNT -f $send_files_dir/2.snap
run_check $FSSUM_PROG -r $send_files_dir/2.fssum $SCRATCH_MNT/mysnap2

echo "Silence is golden"
status=0
exit
