btrfs: fix check_shared for fiemap ioctl
authorLu Fengqi <lufq.fnst@cn.fujitsu.com>
Mon, 13 Jun 2016 01:36:46 +0000 (09:36 +0800)
committerDavid Sterba <dsterba@suse.com>
Mon, 26 Sep 2016 15:59:49 +0000 (17:59 +0200)
commitafce772e87c36c7f07f230a76d525025aaf09e41
tree544c9365efd38bea2356fde31592be01a56576eb
parentb0de6c4c81099494d7863a31db06366f74395cda
btrfs: fix check_shared for fiemap ioctl

Only in the case of different root_id or different object_id, check_shared
identified extent as the shared. However, If a extent was referred by
different offset of same file, it should also be identified as shared.
In addition, check_shared's loop scale is at least n^3, so if a extent
has too many references, even causes soft hang up.

First, add all delayed_ref to the ref_tree and calculate the unqiue_refs,
if the unique_refs is greater than one, return BACKREF_FOUND_SHARED.
Then individually add the on-disk reference(inline/keyed) to the ref_tree
and calculate the unique_refs of the ref_tree to check if the unique_refs
is greater than one.Because once there are two references to return
SHARED, so the time complexity is close to the constant.

Reported-by: Tsutomu Itoh <t-itoh@jp.fujitsu.com>
Signed-off-by: Lu Fengqi <lufq.fnst@cn.fujitsu.com>
Signed-off-by: David Sterba <dsterba@suse.com>
fs/btrfs/backref.c
fs/btrfs/extent_io.c