btrfs-progs: Let function find_device to be consistent with kernel

Make find_device to be consistent with kernel according
35c70103a528 ("btrfs: refactor find_device helper")

And, modify the compare condition from both devid and uuid to
devid or devid and uuid according
8f18cf13396c ("Btrfs: Make the resizer work based on shrinking and growing devices")

Signed-off-by: Gu Jinxiang <gujx@cn.fujitsu.com>
Signed-off-by: David Sterba <dsterba@suse.com>

btrfs-progs: Remove deprecated btrfs-calc-size tool

Its function has been superseded by btrfs inspect-internal tree-stats.
Just remove it.

Deprecated since 4.8.

Issue: #97
Signed-off-by: Nikolay Borisov <nborisov@suse.com>
Signed-off-by: David Sterba <dsterba@suse.com>

btrfs-progs: Remove deprecated btrfs-show-super

Its function has been superseded by btrfs inspect-internal show-super.
Furthermore the tools is currently not built by default. Just remove it.

Deprecated since 4.8.

Issue: #97
Signed-off-by: Nikolay Borisov <nborisov@suse.com>
Signed-off-by: David Sterba <dsterba@suse.com>

btrfs-progs: Remove deprecated btrfs-zero-log standalone tool

Its function has been subsumed by "btrfs rescue zero-log". Remove its
source file and adjust make/tests soruces accordingly.

Deprecated since 4.0.

Issue: #97
Signed-off-by: Nikolay Borisov <nborisov@suse.com>
Signed-off-by: David Sterba <dsterba@suse.com>

btrfs-progs: Remove btrfs-debug-tree command

There is already a replacement in the face of btrfs inspect-internal
dump-tree. And this command is just a simple wrapper around it. Just
remove it and adjust the show-blocks script to call the main btrfs
binary to achieve the same effect.

Informally deprecated since 4.4.

Issue: #97
Signed-off-by: Nikolay Borisov <nborisov@suse.com>
Signed-off-by: David Sterba <dsterba@suse.com>

btrfs-progs: send-utils: remove unused functions path_cat and path_cat3

Since function path_cat and path_cat3 are not used anymore, remove them.
They have been reprecated since version 4.0.

Signed-off-by: Gu Jinxiang <gujx@cn.fujitsu.com>
Signed-off-by: David Sterba <dsterba@suse.com>

btrfs-progs: mkfs: return nozero value on thin provisioned device

With mkfs.btrfs on a thin provisioned device with very small backing
size and big virtual size, all code works well in mkfs.btrfs until
close_ctree() is called.
close_ctree() fails to sync device due to small backing size while
closing devices.  However, mkfs returns 0 in such situation which causes
failure of fstests generic/405.

So, let mkfs returns nonzero value if previous steps succeeded but
close_ctree() failed. Then fstests generic/405 passes now.

Signed-off-by: Su Yue <suy.fnst@cn.fujitsu.com>
Reviewed-by: Qu Wenruo <wqu@suse.com>
Signed-off-by: David Sterba <dsterba@suse.com>

btrfs-progs: sb-mod: add compat bit to the recognized fields

Signed-off-by: David Sterba <dsterba@suse.com>

btrfs-progs: sb-mod: add csum_type

Let SET and GET work on superblock::csum_type.

Signed-off-by: David Sterba <dsterba@suse.com>

btrfs-progs: sb-mod: add preliminary support for non-u64 types

Signed-off-by: David Sterba <dsterba@suse.com>

Btrfs progs v4.16

Signed-off-by: David Sterba <dsterba@suse.com>

btrfs-progs: update CHANGES for v4.16

Signed-off-by: David Sterba <dsterba@suse.com>

btrfs-progs: mkfs rootdir: use lgetxattr() not to follow a symbolic link

mkfs-test 016 "rootdir-bad-symbolic-link" fails when selinux is enabled.
This is because add_xattr_item() uses getxattr() and tries to follow a
bad symbolic link for selinux item, which causes ENOENT error.

The line above already uses llistxattr() for getting list of xattr in
order not to follow a symbolic link, so just use lgetxattr() too.

Signed-off-by: Tomohiro Misono <misono.tomohiro@jp.fujitsu.com>
Reviewed-by: Qu Wenruo <wqu@suse.com>
Signed-off-by: David Sterba <dsterba@suse.com>

btrfs-progs: build: Do not use cp -a to install library links

Using cp -a to install files will preserve the ownership of the original
files (if possible), which is typically not wanted. E.g. if the files
were built by a normal user, but are being installed by root, then the
installed files would maintain the UIDs/GIDs of the user that built the
files rather than be owned by root.

Signed-off-by: Peter Kjellerstedt <peter.kjellerstedt@axis.com>
Reviewed-by: Anand Jain <anand.jain@oracle.com>
Signed-off-by: David Sterba <dsterba@suse.com>

btrfs-progs: docs: fix typos

A few more typo fixes, merged with the pull request.

Pull-request: #120
Signed-off-by: Gu Jinxiang <gujx@cn.fujitsu.com>
Signed-off-by: David Sterba <dsterba@suse.com>

libbtrfsutil: fix test assumptions about top-level subvolume

Since "btrfs-progs: mkfs: add uuid and otime to ROOT_ITEM of, FS_TREE",
the top-level subvolume has a non-zero UUID, ctime, and otime. Fix the
subvolume_info() test to not check for zero.

Signed-off-by: Omar Sandoval <osandov@fb.com>
Reviewed-by: Tomohiro Misono <misono.tomohiro@jp.fujitsu.com>
Signed-off-by: David Sterba <dsterba@suse.com>

libbtrfsutil: always build libbtrfsutil.so.$MAJOR

Otherwise, make test-libbtrfsutil from a fresh checkout fails.

Signed-off-by: Omar Sandoval <osandov@fb.com>
Signed-off-by: David Sterba <dsterba@suse.com>

libbtrfsutil: use local mkfs.btrfs for tests if it exists

The system might not have mkfs installed at all.

Signed-off-by: Omar Sandoval <osandov@fb.com>
Signed-off-by: David Sterba <dsterba@suse.com>

libbtrfsutil: fix memory leak in deleted_subvolumes()

If we fail to reallocate the ID array, we still need to free it.

Signed-off-by: Omar Sandoval <osandov@fb.com>
Signed-off-by: David Sterba <dsterba@suse.com>

libbtrfsutil: don't return free space cache inodes from deleted_subvolumes()

Deleted free space cache inodes also get an orphan item in the root
tree, but we shouldn't report those as deleted subvolumes. Deleted
subvolumes will still have the root item, so we can just do an extra
tree search.

Reported-by: Tomohiro Misono <misono.tomohiro@jp.fujitsu.com>
Signed-off-by: Omar Sandoval <osandov@fb.com>
Signed-off-by: David Sterba <dsterba@suse.com>

btrfs-progs: mkfs: precreate the uuid tree

We can easily create the uuid tree that's usually created after first
mount. The kernel will still check the tree on first mount so we don't
try to fake the uuid tree generation so it appears consistent, even if
it's empty.

Signed-off-by: David Sterba <dsterba@suse.com>

btrfs-progs: tests: Test if btrfs-image can handle RAID1 missing device

Signed-off-by: Qu Wenruo <wqu@suse.com>
Signed-off-by: David Sterba <dsterba@suse.com>

btrfs-progs: convert: Fix offset-by-one error in read_data_extent()

For read_data_extent() in convert/main.c it's using mirror number in a
incorrect way, which will not get correct copy for RAID1:

for (cur_mirror = 0; cur_mirror < num_copies; cur_mirror++) {

In such case, for RAID1 @cur_mirror will only be 0 and 1.

However for 0 and 1 case, btrfs_map_block() will only return the first
copy.  To reach the 2nd copy, it correct @cur_mirror range should be 1
and 2.

So with this off-by-one error, btrfs-image will never be able to read
out data extent if the first stripe of the chunk is the missing one.

Fix it by starting @cur_mirror from 1 and to @num_copies (including).

Fixes: 2d46558b30f5 ("btrfs-progs: Use existing facility to replace read_data_extent function")
Signed-off-by: Qu Wenruo <wqu@suse.com>
Signed-off-by: David Sterba <dsterba@suse.com>

btrfs-progs: disk-io: Fix read_extent_data() error handler for missing device

When device is missing, read_extent_data() (function exported from old
btrfs check code) has the following problems:

1) Modifies @len parameter if device is missing
   If device returned in @multi is missing, @len can be larger than
   @max_len (originl length).

   This could confuse caller and underflow in the read loop.

2) Still returns 0 for missing device
   It only handles read error, missing device is not handled and 0 is
   returned.

3) Wrong check for device->fd
   In fact, 0 is also a valid fd.
   Although not possible under most cases, but still needs fix.

Fix them all.

Fixes: 1bad2f2f2dfe ("Btrfs-progs: fsck: add an option to check data csums")
Signed-off-by: Qu Wenruo <wqu@suse.com>
Signed-off-by: David Sterba <dsterba@suse.com>

btrfs-progs: tests: Test if mkfs.btrfs --rootdir can handle ng symlink

Signed-off-by: Qu Wenruo <wqu@suse.com>
Signed-off-by: David Sterba <dsterba@suse.com>

btrfs-progs: Remove unused parameter

Parameter usagestr is not used, remove it.

Signed-off-by: Gu Jinxiang <gujx@cn.fujitsu.com>
Reviewed-by: Nikolay Borisov <nborisov@suse.com>
Signed-off-by: David Sterba <dsterba@suse.com>

btrfs-progs: mkfs/rootdir: Don't follow symbolic link when calcuating size

[BUG]
If we have a symbolic link in rootdir pointing to non-existing location,
mkfs.btrfs --rootdir will just fail:
------
$ mkfs.btrfs  -f --rootdir /tmp/rootdir/ /dev/data/btrfs
btrfs-progs v4.15.1
See http://btrfs.wiki.kernel.org for more information.

ERROR: ftw subdir walk of /tmp/rootdir/ failed: No such file or directory
------

[CAUSE]
Commit 599a0abed564 ("btrfs-progs: mkfs/rootdir: Use over-reserve method
to make size estimate easier") add extra ftw walk to estimate the
filesystem size.

Such default ftw walk will follow symbolic link and gives ENOENT error.

[FIX]
Use nftw() to specify FTW_PHYS so we won't follow symbolic link for size
calculation.

Issue: #109
Reported-by: Alexander Kanavin <alexander.kanavin@intel.com>
Fixes: 599a0abed564 ("btrfs-progs: mkfs/rootdir: Use over-reserve method to make size estimate easier")
Signed-off-by: Qu Wenruo <wqu@suse.com>
Signed-off-by: David Sterba <dsterba@suse.com>

btrfs-progs: build: modify cscope/ctags rules to include directories such as check

Modify cscope/ctags rule to include directories such as check/
libbtrfsutil/kernel-lib/kernel-shared.

Signed-off-by: Lu Fengqi <lufq.fnst@cn.fujitsu.com>
Signed-off-by: David Sterba <dsterba@suse.com>

btrfs-progs: add tool to edit super blocks

$ make btrfs-sb-mod
$ ./btrfs-sb-mod image field1 operation1 ...

Fields (only u64 supported for now):
 * total_bytes
 * root
 * generation
 * chunk_root
 * chunk_root_generation
 * cache_generation
 * uuid_tree_generation

Operations:
 * read value ?0
 * set value =NUMBER
 * add to +NUMBER
 * subtract from value -NUMBER
 * xor with value ^NUMBER
 * byteswap (u64) @0

Use with care!

Signed-off-by: David Sterba <dsterba@suse.com>

btrfs-progs: check/original: Remove unused variable first_key

This @first_key variable is introduced in f5c4c4f3b75b
("btrfsck: add code to rebuild extent records"), however it's not only
unused, but also used incorrectly.

It's calling btrfs_item_key_to_cpu() on an node extent buffer.

Anyway, just remove it.

Fixes: f5c4c4f3b75b ("btrfsck: add code to rebuild extent records")
Signed-off-by: Qu Wenruo <wqu@suse.com>
Signed-off-by: David Sterba <dsterba@suse.com>

btrfs-progs: remove BTRFS_CRC32_SIZE definition

The kernel code no longer has BTRFS_CRC32_SIZE and only uses
btrfs_csum_sizes[]. So, update the progs code as well.

Suggested-by: Qu Wenruo <wqu@suse.com>
Signed-off-by: Tomohiro Misono <misono.tomohiro@jp.fujitsu.com>
Reviewed-by: Qu Wenruo <wqu@suse.com>
Signed-off-by: David Sterba <dsterba@suse.com>

btrfs-progs: tests: add shell quotes to misc test scripts

Signed-off-by: David Sterba <dsterba@suse.com>

btrfs-progs: tests: add shell quotes to mkfs test scripts

Signed-off-by: David Sterba <dsterba@suse.com>

btrfs-progs: tests: remove trivial use of local variables

No need to use a temporary variable if the parameter usage is obvious
from the context.

Signed-off-by: David Sterba <dsterba@suse.com>

btrfs-progs: tests: add shell quoting to fuzz test scripts

Signed-off-by: David Sterba <dsterba@suse.com>

btrfs-progs: tests: convert/014 use shell builtin for generating content

We can remove dependency on perl and use shell builtin go generate
sequence of bytes.

Signed-off-by: David Sterba <dsterba@suse.com>

btrfs-progs: tests: update README, images, coding style

Signed-off-by: David Sterba <dsterba@suse.com>

btrfs-progs: tests: mkfs fills uuid and otime for FS_TREE

Signed-off-by: David Sterba <dsterba@suse.com>

btrfs-progs: mkfs: add uuid and otime to ROOT_ITEM of, FS_TREE

Currently, the top-level subvolume lacks the UUID. As a result, both
non-snapshot subvolume and snapshot of top-level subvolume do not have
Parent UUID and cannot be distinguisued. Therefore "fi show" of
top-level lists all the subvolumes which lacks the UUID in
"Snapshot(s)" filed.  Also, it lacks the otime information.

Fix this by adding the UUID and otime at the mkfs time.  As a
consequence, snapshots of top-level subvolume now have a Parent UUID and
UUID tree will create an entry for top-level subvolume at mount time.
This should not cause the problem for current kernel, but user program
which relies on the empty Parent UUID may be affected by this change.

Signed-off-by: Tomohiro Misono <misono.tomohiro@jp.fujitsu.com>
Signed-off-by: David Sterba <dsterba@suse.com>

btrfs-progs: Beautify owner when printing leaf/nodes

Currently we print the raw values of the owner field of leaf/nodes.
This can result in output like the following:

leaf 30490624 items 2 free space 16061 generation 4 owner 18446744073709551607

With the patch applied the same leaf looks like:

leaf 30490624 items 2 free space 16061 generation 4 owner DATA_RELOC_TREE

Signed-off-by: Nikolay Borisov <nborisov@suse.com>
Reviewed-by: Qu Wenruo <wqu@suse.com>
Signed-off-by: David Sterba <dsterba@suse.com>

btrfs-progs: tests: don't use fallocate in mkfs/014-rootdir-inline-extent

If fallocate is not supported, this test fails. Use a shell trick to
fill with given number of bytes.

Signed-off-by: David Sterba <dsterba@suse.com>

btrfs-progs: tests: Add testcase for rootdir inline extent size

Add a test case for mkfs --rootdir, using files with different file
sizes to check if invalid large inline extent could exist.

Signed-off-by: Qu Wenruo <wqu@suse.com>
Signed-off-by: David Sterba <dsterba@suse.com>

btrfs-progs: test/convert: Add test case for invalid large inline data extent

Signed-off-by: Qu Wenruo <wqu@suse.com>
Signed-off-by: David Sterba <dsterba@suse.com>

btrfs-progs: check/lowmem mode: Check inline extent size

Signed-off-by: Qu Wenruo <wqu@suse.com>
Signed-off-by: David Sterba <dsterba@suse.com>

btrfs-progs: check: original mode: Check inline extent size

For inline compressed file extent, kernel doesn't allow inline extent
ram size larger than sector size and on-disk inline extent size should
not exceed BTRFS_MAX_INLINE_DATA_SIZE().

For inline uncompressed file extent, kernel doesn't allow inline extent
ram and on-disk size larger than either BTRFS_MAX_INLINE_DATA_SIZE() or
sector size.

Check it in original mode.

Signed-off-by: Qu Wenruo <wqu@suse.com>
Signed-off-by: David Sterba <dsterba@suse.com>

btrfs-progs: mkfs/rootdir: Fix inline extent creation check

Just like convert, we need extra check against sector size for creating
inline extent.

Signed-off-by: Qu Wenruo <wqu@suse.com>
Signed-off-by: David Sterba <dsterba@suse.com>

btrfs-progs: convert: Fix inline file extent creation condition

[Bug]
On btrfs converted from ext*, one user reported the following kernel
warning:
 ------------[ cut here ]------------
 BTRFS: Transaction aborted (error -95)
 WARNING: CPU: 0 PID: 324 at fs/btrfs/inode.c:3042 btrfs_finish_ordered_io+0x7ab/0x850 [btrfs]
 Workqueue: btrfs-endio-write btrfs_endio_write_helper [btrfs]
 RIP: 0010:btrfs_finish_ordered_io+0x7ab/0x850 [btrfs]
 ...
 Call Trace:
  normal_work_helper+0x39/0x370 [btrfs]
  process_one_work+0x1ce/0x410
  worker_thread+0x2b/0x3d0
  ? process_one_work+0x410/0x410
  kthread+0x113/0x130
  ? kthread_create_on_node+0x70/0x70
  ? do_syscall_64+0x74/0x190
  ? SyS_exit_group+0x10/0x10
  ret_from_fork+0x35/0x40
 ---[ end trace c8ed62ff6a525901 ]---
 BTRFS: error (device dm-2) in
btrfs_finish_ordered_io:3042: errno=-95 unknown
 BTRFS info (device dm-2): forced readonly
 BTRFS error (device dm-2): pending csums is 6447104

[Cause]
The call trace and the unique return value points to
__btrfs_drop_extents(), when we tries to drop pages of an inline extent,
we will trigger such -EOPNOTSUPP.

However kernel has limitation on the size of inline file extent
(sector size for ram size and sector size - 1 for on-disk size),
btrfs-convert doesn't have the same limitation, resulting much larger
file extent.

The lack of correct inline extent size check dates back to 2008 when
btrfs-convert is added into btrfs-progs.

[Fix]
Fix the inline extent creation condition, not only using
BTRFS_MAX_INLINE_DATA_SIZE(), which is only the maximum size of inline
data according to nodesize, but also limit it against sector size.

Signed-off-by: Qu Wenruo <wqu@suse.com>
Signed-off-by: David Sterba <dsterba@suse.com>

btrfs-progs: dump-tree: add option to print children nodes of a given block

When debuging with "btrfs inspect dump-tree", it's not that handy if we
want to iterate all child tree blocks starting from a specified block.

-b can only print a single block, while without -b "btrfs inspect dump-tree"
will need extra tree roots fulfilled to continue, which is not possible
for a damaged filesystem.

Add a new option --follow to iterate a sub-tree starting from block
specified by --block.

Signed-off-by: Qu Wenruo <wqu@suse.com>
[ remove the short option for now ]
Signed-off-by: David Sterba <dsterba@suse.com>

btrfs-progs: print-tree: Enhance warning on tree block level mismatch and error handling

This patch enhances the tree block level mismatch by the following
methods:

1) Merge same warning branches into one
   We had two branches showing the same message, and their condition
   is also the same. Merge them

2) Only skip bad slot
   The old code skipped all the remaining slots, here we just skip one
   slot to output as many correct tree blocks as possible.

3) Enhance warning message
   Output the parent bytenr and expected and wrong level, so we don't
   need to refer to stdout to get which tree block is corrupted.

Signed-off-by: Qu Wenruo <wqu@suse.com>
Signed-off-by: David Sterba <dsterba@suse.com>

btrfs-progs: Fix typos in docs and user-facing strings

Signed-off-by: Nicholas D Steeves <nsteeves@gmail.com>
Signed-off-by: David Sterba <dsterba@suse.com>

btrfs-progs: print-tree: Do correct offset output for ROOT_ITEM

Commit Fixes: 8c36786c8198 ("btrfs-progs: print-tree: Print offset as
tree objectid for ROOT_ITEM") changes how we translate offset of
ROOT_ITEM.

However the fact is, even for ROOT_ITEM, we have different meaning of
offset.

For tree reloc tree, it's indeed subvolume id.  But for other trees,
it's the transid of when it's created.

Reported-by: Nikolay Borisov <nborisov@suse.com>
Signed-off-by: Qu Wenruo <wqu@suse.com>
Reviewed-by: Nikolay Borisov <nborisov@suse.com>
Signed-off-by: David Sterba <dsterba@suse.com>

btrfs-progs: convert/ext2: Remove check for ext2_ext_attr_entry->e_value_block

In latest e2fsprogs (1.44.0) definition of ext2_ext_attr_entry has
removed member e_value_block, as currently ext* doesn't support it set
anyway.

So remove such check so that we can pass compile.

Issue: #110
Bugzilla: https://bugzilla.kernel.org/show_bug.cgi?id=199071
Signed-off-by: Qu Wenruo <wqu@suse.com>
Signed-off-by: David Sterba <dsterba@suse.com>

Btrfs-progs: add fsck test for filesystem with shared prealloc extents

Verify that a filesystem check operation (fsck) does not report the
following scenario as an error:

An extent is shared between two inodes, as a result of clone/reflink
operation, and for one of the inodes, lets call it inode A, the extent is
referenced through a file extent item as a prealloc extent, while for the
other inode, call it inode B, the extent is referenced through a regular
file extent item, that is, it was written to. The goal of this test is to
make sure a filesystem check operation will not report "odd csum items"
errors for the prealloc extent at inode A, because this scenario is valid
since the extent was written through inode B and therefore it is expected
to have checksum items in the filesystem's checksum btree for that shared
extent.

Such scenario can be created with the following steps for example:

 mkfs.btrfs -f /dev/sdb
 mount /dev/sdb /mnt

 touch /mnt/foo
 xfs_io -c "falloc 0 256K" /mnt/foo
 sync

 xfs_io -c "pwrite -S 0xab 0 256K" /mnt/foo
 touch /mnt/bar
 xfs_io -c "reflink /mnt/foo 0 0 256K" /mnt/bar
 xfs_io -c "fsync" /mnt/bar

 <power fail>
 mount /dev/sdb /mnt
 umount /mnt

This scenario is fixed by the following patch for the filesystem checker:

 "Btrfs-progs: check, fix false error reports for shared prealloc extents"

Signed-off-by: Filipe Manana <fdmanana@suse.com>
Reviewed-by: Qu Wenruo <wqu@suse.com>
Signed-off-by: David Sterba <dsterba@suse.com>

Btrfs-progs: check, fix false error reports for shared prealloc extents

Under some cases the filesystem checker reports an error when it finds
checksum items for an extent that is referenced by an inode as a prealloc
extent. Such cases are not an error when the extent is actually shared
(was cloned/reflinked) with other inodes and was written through one of
those other inodes.

Example:

  $ mkfs.btrfs -f /dev/sdb
  $ mount /dev/sdb /mnt

  $ touch /mnt/foo
  $ xfs_io -c "falloc 0 256K" /mnt/foo
  $ sync

  $ xfs_io -c "pwrite -S 0xab 0 256K" /mnt/foo
  $ touch /mnt/bar
  $ xfs_io -c "reflink /mnt/foo 0 0 256K" /mnt/bar
  $ xfs_io -c "fsync" /mnt/bar

  <power fail>
  $ mount /dev/sdb /mnt
  $ umount /mnt

  $ btrfs check /dev/sdc
  Checking filesystem on /dev/sdb
  UUID: 52d3006e-ee3b-40eb-aa21-e56253a03d39
  checking extents
  checking free space cache
  checking fs roots
  root 5 inode 257 errors 800, odd csum item
  ERROR: errors found in fs roots
  found 688128 bytes used, error(s) found
  total csum bytes: 256
  total tree bytes: 163840
  total fs tree bytes: 65536
  total extent tree bytes: 16384
  btree space waste bytes: 138819
  file data blocks allocated: 10747904
   referenced 10747904
  $ echo $?
  1

So teach check to not report such cases as errors by checking if the
extent is shared with other inodes and if so, consider it an error the
existence of checksum items only if all those other inodes are referencing
the extent as a prealloc extent.
This case can be hit often when running the generic/475 testcase from
fstests.

A test case will follow in a separate patch.

Signed-off-by: Filipe Manana <fdmanana@suse.com>
Reviewed-by: Nikolay Borisov <nborisov@suse.com>
Signed-off-by: David Sterba <dsterba@suse.com>

btrfs-progs: ctree: Add extra level check for read_node_slot()

Strangely, we have level check in btrfs_print_tree() while we don't have
the same check in read_node_slot().

That's to say, for the following corruption, btrfs_search_slot() or
btrfs_next_leaf() can return invalid leaf:

Parent eb:
  node XXXXXX level 1
              ^^^^^^^
              Child should be leaf (level 0)
  ...
  key (XXX XXX XXX) block YYYYYY

Child eb:
  leaf YYYYYY level 1
              ^^^^^^^
              Something went wrong now

And for the corrupted leaf returned, later caller can be screwed up
easily.

Reported-by: Ralph Gauges <ralphgauges@googlemail.com>
Signed-off-by: Qu Wenruo <wqu@suse.com>
Reviewed-by: Nikolay Borisov <nborisov@suse.com>
Signed-off-by: David Sterba <dsterba@suse.com>

btrfs-progs: tests: fix source path for testsuite

The commit cebf3b37228cbde730a5 ("btrfs-progs: introduce TEST_TOP and
INTERNAL_BIN for tests") did not convert all test paths. This would
break the exported testsutie.

Signed-off-by: David Sterba <dsterba@suse.com>

btrfs-progs: tests: Add test case with valid orphan inode

Regression test for false alerts in lowmem mode.

Signed-off-by: Qu Wenruo <wqu@suse.com>
[ update test ]
Signed-off-by: David Sterba <dsterba@suse.com>

btrfs-progs: check: lowmem: Fix false alert about orphan inode

Btrfs can delay inode deletion and in that case btrfs will unlink the
victim inode from its parent dir, and insert a marker to info btrfs to
delete it later.

In that case, such victim inode will have nlinks == 0, but is still
completely valid.
Original mode won't report such problem, but lowmem mode doesn't check
the ORPHAN_ITEM key for such inode, and can report false alert like:
------
ERROR: root 257 INODE[28891726] is orphan item
------

Fix such false alert by checking orphan item for inode whose nlink is 0.

Signed-off-by: Qu Wenruo <wqu@suse.com>
Reviewed-by: Su Yue <suy.fnst@cn.fujitsu.com>
Signed-off-by: David Sterba <dsterba@suse.com>

btrfs-progs: gitignore: Ignore patches

Although it's not a good practice to format all patches under project
directory, sometimes lazy bones like me just like to put patches under
project directory.

Just ignore such patches.

Signed-off-by: Qu Wenruo <wqu@suse.com>
Signed-off-by: David Sterba <dsterba@suse.com>

btrfs-progs: gitignore: Ignore *.restored test image

Signed-off-by: Qu Wenruo <wqu@suse.com>
Signed-off-by: David Sterba <dsterba@suse.com>

btrfs-progs: fsck-tests: Introduce test case with keyed data backref with the extent offset

Add the testcase for false alert of data extent backref lost with the
extent offset.

The image can be reproduced by the following commands:
------
dev=~/test.img
mnt=/mnt/btrfs

umount $mnt &> /dev/null
fallocate -l 128M $dev

mkfs.btrfs $dev
mount $dev $mnt

for i in `seq 1 10`; do
xfs_io -f -c "pwrite 0 2K" $mnt/file$i
done

xfs_io -f -c "falloc 0 64K" $mnt/file11

for i in `seq 1 32`; do
xfs_io -f -c "reflink $mnt/file11 0 $(($i * 64))K 64K" $mnt/file11
done

xfs_io -f -c "reflink $mnt/file11 32K $((33 * 64))K 32K" $mnt/file11

btrfs subvolume snapshot $mnt $mnt/snap1

umount $mnt
btrfs-image -c9 $dev extent_data_ref.img
------

Signed-off-by: Lu Fengqi <lufq.fnst@cn.fujitsu.com>
Signed-off-by: David Sterba <dsterba@suse.com>

btrfs-progs: check/lowmem: Fix false alert of data extent backref lost for snapshot

Btrfs lowmem check reports the following false alert:
------
ERROR: file extent[267 2162688] root 256 owner 5 backref lost
------

The file extent is in the leaf which is shared by file tree 256 and fs
tree.
------
leaf 30605312 items 46 free space 4353 generation 7 owner 5
......
        item 45 key (267 EXTENT_DATA 2162688) itemoff 5503 itemsize 53
                generation 7 type 2 (prealloc)
                prealloc data disk byte 13631488 nr 65536
                prealloc data offset 32768 nr 32768
------

And there is the corresponding extent_data_ref item in the extent tree.
------
        item 1 key (13631488 EXTENT_DATA_REF 1007496934287921081) itemoff 15274 itemsize 28
                extent data backref root 5 objectid 267 offset 2129920 count 1
------

The offset of EXTENT_DATA_REF which is the hash of the owner root objectid,
the inode number and the calculated offset (file offset - extent offset).

What caused the false alert is the code mix up the owner root objectid and
the file tree objectid.

Fixes: b0d360b541f0 ("btrfs-progs: check: introduce function to check data backref in extent tree")
Signed-off-by: Lu Fengqi <lufq.fnst@cn.fujitsu.com>
Reviewed-by: Qu Wenruo <wqu@suse.com>
Signed-off-by: David Sterba <dsterba@suse.com>

btrfs-progs: check/lowmem: Fix the incorrect error message of check_extent_data_item

Instead of the disk_bytenr and disk_num_bytes of the extent_item which the
file extent references, we should output the objectid and offset of the
file extent. And the leaf may be shared by the file trees, we should print
the objectid of the root and the owner of the leaf.

Fixes: b0d360b541f0 ("btrfs-progs: check: introduce function to check data backref in extent tree")
Signed-off-by: Lu Fengqi <lufq.fnst@cn.fujitsu.com>
Signed-off-by: David Sterba <dsterba@suse.com>

btrfs-progs: dump-super: Don't verify csum if csum type or size is unknown

Reported-by: Ken Swenson <flat@imo.uto.moe>
Signed-off-by: Qu Wenruo <wqu@suse.com>
Signed-off-by: David Sterba <dsterba@suse.com>

btrfs-progs: free-space-cache: Enhance free space cache free space check

When we found free space difference between free space cache and block
group item, we just discard this free space cache.

Normally such difference is caused by btrfs_reserve_extent() called by
delalloc which is out of a transaction.
And since all btrfs_release_extent() is called with a transaction, under
heavy race free space cache can have less free space than block group
item.

Normally kernel will detect such difference and just discard that cache.

However we must be more careful if free space cache has more free space
cache, and if that happens, paried with above race one invalid free
space cache can be loaded into kernel.

So if we find any free space cache who has more free space then block
group item, we report it as an error other than ignoring it.

Signed-off-by: Qu Wenruo <wqu@suse.com>
Signed-off-by: David Sterba <dsterba@suse.com>

btrfs-progs: docs: add section about filesystem limits to btrfs(5)

Signed-off-by: David Sterba <dsterba@suse.com>

btrfs-progs: free-space-cache: Use DIV_ROUND_UP() to replace open code

Signed-off-by: Qu Wenruo <wqu@suse.com>
Signed-off-by: David Sterba <dsterba@suse.com>

libbtrfsutil: use pkg-config detection for the right Python version

The user may have specified a different version of Python than the
python3 from their $PATH (e.g., with PYTHON=/usr/bin/python3.6).

Signed-off-by: Omar Sandoval <osandov@fb.com>
Signed-off-by: David Sterba <dsterba@suse.com>

btrfs-progs: ci: enable clang and python for musl build test

The updated image now provides clang, so the variable is exported from
the base environment to docker. And we have python too.

Signed-off-by: David Sterba <dsterba@suse.com>

btrfs-progs: ci: update test image packages - add clang and python

Signed-off-by: David Sterba <dsterba@suse.com>

libbtrfsutils: add python-devel detection

Use pkg-config to detect python devel.

Signed-off-by: David Sterba <dsterba@suse.com>

btrfs-progs: ci: cache built dependencies

For a slight speed up of the build, cache reiserfs and zstd. A quick
cache validity is done, or it can be cleared manually on travis web UI.

Signed-off-by: David Sterba <dsterba@suse.com>

btrfs-progs: replace test_issubvolume() with btrfs_util_is_subvolume()

This gets the remaining occurrences that weren't covered by previous
conversions.

Signed-off-by: Omar Sandoval <osandov@fb.com>
[ fixup test_issubvolume due to removed dependency patch ]
Signed-off-by: David Sterba <dsterba@suse.com>

btrfs-progs: use libbtrfsutil for subvol sync

btrfs_util_f_deleted_subvolumes() replaces enumerate_dead_subvols() and
btrfs_util_f_subvolume_info() replaces is_subvolume_cleaned().

Signed-off-by: Omar Sandoval <osandov@fb.com>
Signed-off-by: David Sterba <dsterba@suse.com>

btrfs-progs: use libbtrfsutil for subvol show

Now implemented with btrfs_util_subvolume_path(),
btrfs_util_subvolume_info(), and subvolume iterators.

Signed-off-by: Omar Sandoval <osandov@fb.com>
Signed-off-by: David Sterba <dsterba@suse.com>

btrfs-progs: use libbtrfsutil for subvol delete

Most of the interesting part of this command is the commit mode, so this
only saves a little bit of code.

Signed-off-by: Omar Sandoval <osandov@fb.com>
Signed-off-by: David Sterba <dsterba@suse.com>

btrfs-progs: use libbtrfsutil for get-default

The only thing of note here is the "top level" column. This used to mean
something else, but for a long time it has been equal to the parent ID.
I preserved this for backwards compatability.

Signed-off-by: Omar Sandoval <osandov@fb.com>
Signed-off-by: David Sterba <dsterba@suse.com>

btrfs-progs: use libbtrfsutil for set-default

Signed-off-by: Omar Sandoval <osandov@fb.com>
Signed-off-by: David Sterba <dsterba@suse.com>

btrfs-progs: use libbtrfsutil for sync ioctls

Signed-off-by: Omar Sandoval <osandov@fb.com>
Signed-off-by: David Sterba <dsterba@suse.com>

btrfs-progs: use libbtrfsutil for read-only property

Signed-off-by: Omar Sandoval <osandov@fb.com>
Signed-off-by: David Sterba <dsterba@suse.com>

libbtrfsutil: add btrfs_util_deleted_subvolumes()

Signed-off-by: Omar Sandoval <osandov@fb.com>
Signed-off-by: David Sterba <dsterba@suse.com>

libbtrfsutil: add btrfs_util_delete_subvolume()

We also support recursive deletion using a subvolume iterator.

Signed-off-by: Omar Sandoval <osandov@fb.com>
Signed-off-by: David Sterba <dsterba@suse.com>

libbtrfsutil: add btrfs_util_create_snapshot()

Thanks to subvolume iterators, we can also implement recursive snapshot
fairly easily.

Signed-off-by: Omar Sandoval <osandov@fb.com>
Signed-off-by: David Sterba <dsterba@suse.com>

libbtrfsutil: add subvolume iterator helpers

This is how we can implement stuff like `btrfs subvol list`. Rather than
producing the entire list upfront, the iterator approach uses less
memory in the common case where the whole list is not stored (O(max
subvolume path length)). It supports both pre-order traversal (useful
for, e.g, recursive snapshot) and post-order traversal (useful for
recursive delete).

Signed-off-by: Omar Sandoval <osandov@fb.com>
Signed-off-by: David Sterba <dsterba@suse.com>

libbtrfsutil: add stub for reallocarray

This function is new in glibc 2.26 and breaks build in CI and possibly
other environments.

Signed-off-by: David Sterba <dsterba@suse.com>

libbtrfsutil: add btrfs_util_[gs]et_default_subvolume()

set_default_subvolume() is a trivial ioctl(), but there's no ioctl() for
get_default_subvolume(), so we need to search the root tree.

Signed-off-by: Omar Sandoval <osandov@fb.com>
Signed-off-by: David Sterba <dsterba@suse.com>

libbtrfsutil: add btrfs_util_[gs]et_read_only()

In the future, btrfs_util_[gs]et_subvolume_flags() might be useful, but
since these are the only subvolume flags we've defined in all this time,
this will do for now.

Signed-off-by: Omar Sandoval <osandov@fb.com>
Signed-off-by: David Sterba <dsterba@suse.com>

libbtrfsutil: add btrfs_util_subvolume_info()

This gets the the information in `btrfs subvolume show` from the root
item.

Signed-off-by: Omar Sandoval <osandov@fb.com>
Signed-off-by: David Sterba <dsterba@suse.com>

libbtrfsutil: add btrfs_util_subvolume_path()

We can just walk up root backrefs with BTRFS_IOC_TREE_SEARCH and inode
paths with BTRFS_IOC_INO_LOOKUP.

Signed-off-by: Omar Sandoval <osandov@fb.com>
Signed-off-by: David Sterba <dsterba@suse.com>

libbtrfsutil: add btrfs_util_create_subvolume()

Doing the ioctl() directly isn't too bad, but passing in a full path is
more convenient than opening the parent and passing the path component.

Signed-off-by: Omar Sandoval <osandov@fb.com>
Signed-off-by: David Sterba <dsterba@suse.com>

libbtrfsutil: add btrfs_util_is_subvolume() and btrfs_util_subvolume_id()

These are the most trivial helpers in the library and will be used to
implement several of the more involved functions.

Signed-off-by: Omar Sandoval <osandov@fb.com>
Signed-off-by: David Sterba <dsterba@suse.com>

libbtrfsutil: copy in Btrfs UAPI headers

Systems with older kernels won't have these available, and the copies in
btrfs-progs aren't quite compatible, so for now, let's just copy these
in. We can potentially deduplicate some of this in the future.

Signed-off-by: Omar Sandoval <osandov@fb.com>
Signed-off-by: David Sterba <dsterba@suse.com>

libbtrfsutil: fix Python tests

These were broken when the patch series got shuffled around.

Signed-off-by: Omar Sandoval <osandov@fb.com>
Signed-off-by: David Sterba <dsterba@suse.com>

btrfs-progs: Move chunk stripe size calculation function to volumes.h

Signed-off-by: Qu Wenruo <wqu@suse.com>
Signed-off-by: David Sterba <dsterba@suse.com>

btrfs-progs: volumes: Allow find_free_dev_extent() to return maximum hole size

Just as kernel find_free_dev_extent(), allow it to return maximum hole
size for us to build device list for later chunk allocator rework.

Signed-off-by: Qu Wenruo <wqu@suse.com>
Signed-off-by: David Sterba <dsterba@suse.com>

btrfs-progs: Introduce btrfs_raid_array and related infrastructures

As part of the effort to unify code and behavior between btrfs-progs and
kernel, copy the btrfs_raid_array from kernel to btrfs-progs.

So later we can use the btrfs_raid_array[] to get needed raid info other
than manually do if-else branches.

Signed-off-by: Qu Wenruo <wqu@suse.com>
Signed-off-by: David Sterba <dsterba@suse.com>

btrfs-progs: Refactor parameter of BTRFS_MAX_DEVS() from root to fs_info

Signed-off-by: Qu Wenruo <wqu@suse.com>
Signed-off-by: David Sterba <dsterba@suse.com>

libbtrfsutil: add filesystem sync helpers

Namely, sync, start_sync, and wait_sync.

Signed-off-by: Omar Sandoval <osandov@fb.com>
Signed-off-by: David Sterba <dsterba@suse.com>

libbtrfsutil: add qgroup inheritance helpers

We want to hide struct btrfs_qgroup_inherit from the user because that
comes from the Btrfs UAPI headers. Instead, wrap it in a struct
btrfs_util_qgroup_inherit and provide helpers to manipulate it. This
will be used for subvolume and snapshot creation.

Signed-off-by: Omar Sandoval <osandov@fb.com>
Signed-off-by: David Sterba <dsterba@suse.com>

libbtrfsutil: add Python bindings

The C libbtrfsutil library isn't very useful for scripting, so we also
want bindings for Python. Writing unit tests in Python is also much
easier than doing so in C. Only Python 3 is supported; if someone really
wants Python 2 support, they can write their own bindings. This commit
is just the scaffolding.

Signed-off-by: Omar Sandoval <osandov@fb.com>
Signed-off-by: David Sterba <dsterba@suse.com>