From patchwork Mon Mar 17 20:34:02 2014 Content-Type: text/plain; charset="utf-8" MIME-Version: 1.0 Content-Transfer-Encoding: 7bit X-Patchwork-Submitter: Josef Bacik X-Patchwork-Id: 3851321 Return-Path: X-Original-To: patchwork-linux-btrfs@patchwork.kernel.org Delivered-To: patchwork-parsemail@patchwork1.web.kernel.org Received: from mail.kernel.org (mail.kernel.org [198.145.19.201]) by patchwork1.web.kernel.org (Postfix) with ESMTP id 0D8179F369 for ; Wed, 19 Mar 2014 17:30:51 +0000 (UTC) Received: from mail.kernel.org (localhost [127.0.0.1]) by mail.kernel.org (Postfix) with ESMTP id 206002034E for ; Wed, 19 Mar 2014 17:30:50 +0000 (UTC) Received: from vger.kernel.org (vger.kernel.org [209.132.180.67]) by mail.kernel.org (Postfix) with ESMTP id C953020386 for ; Wed, 19 Mar 2014 17:30:48 +0000 (UTC) Received: (majordomo@vger.kernel.org) by vger.kernel.org via listexpand id S1752037AbaCQUe0 (ORCPT ); Mon, 17 Mar 2014 16:34:26 -0400 Received: from mx0b-00082601.pphosted.com ([67.231.153.30]:48959 "EHLO mx0b-00082601.pphosted.com" rhost-flags-OK-OK-OK-OK) by vger.kernel.org with ESMTP id S1751781AbaCQUeY (ORCPT ); Mon, 17 Mar 2014 16:34:24 -0400 Received: from pps.filterd (m0004060 [127.0.0.1]) by mx0b-00082601.pphosted.com (8.14.5/8.14.5) with SMTP id s2HKVJsq003778 for ; Mon, 17 Mar 2014 13:34:23 -0700 DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/simple; d=fb.com; h=from : to : subject : date : message-id : mime-version : content-type; s=facebook; bh=K/6LbWtzWFz7c4XsVT9klKr5fNeDB44O/MB5tqmB1LQ=; b=m4TdhsVjdS3njW0KF+Y0mMRfVQOxJzY/C+EMYjSpxj+EVrJlA19DSsRiz3z2pNRonnWE NvaW0jgHEynx6w1qdtvxEANf14q8jk4iDT8rrOxK0PaoDaqmJ4QSKK0NqV2n4ZMRxQ0E 90YmSKAqhA9v5fKJICLB/XliutEBUHadp58= Received: from mail.thefacebook.com (mailwest.thefacebook.com [173.252.71.148]) by mx0b-00082601.pphosted.com with ESMTP id 1jny3khsuj-3 (version=TLSv1/SSLv3 cipher=AES128-SHA bits=128 verify=OK) for ; Mon, 17 Mar 2014 13:34:23 -0700 Received: from localhost (192.168.57.29) by mail.thefacebook.com (192.168.16.12) with Microsoft SMTP Server (TLS) id 14.3.174.1; Mon, 17 Mar 2014 13:34:03 -0700 From: Josef Bacik To: Subject: [PATCH] Btrfs: take into account total references when doing backref lookup Date: Mon, 17 Mar 2014 16:34:02 -0400 Message-ID: <1395088442-6468-1-git-send-email-jbacik@fb.com> X-Mailer: git-send-email 1.8.3.1 MIME-Version: 1.0 X-Originating-IP: [192.168.57.29] X-Proofpoint-Virus-Version: vendor=fsecure engine=2.50.10432:5.11.87, 1.0.14, 0.0.0000 definitions=2014-03-17_03:2014-03-14, 2014-03-17, 1970-01-01 signatures=0 X-Proofpoint-Spam-Details: rule=fb_default_notspam policy=fb_default score=0 kscore.is_bulkscore=1.22534397509755e-05 kscore.compositescore=0 circleOfTrustscore=514.84 compositescore=0.999775624998249 urlsuspect_oldscore=0.999775624998249 suspectscore=3 recipient_domain_to_sender_totalscore=0 phishscore=0 bulkscore=0 kscore.is_spamscore=0 recipient_to_sender_totalscore=0 recipient_domain_to_sender_domain_totalscore=64355 rbsscore=0.999775624998249 spamscore=0 recipient_to_sender_domain_totalscore=0 urlsuspectscore=0.9 adultscore=0 classifier=spam adjust=0 reason=mlx scancount=1 engine=7.0.1-1305240000 definitions=main-1403170120 X-FB-Internal: deliver Sender: linux-btrfs-owner@vger.kernel.org Precedence: bulk List-ID: X-Mailing-List: linux-btrfs@vger.kernel.org X-Spam-Status: No, score=-6.8 required=5.0 tests=BAYES_00,DKIM_SIGNED, RCVD_IN_DNSWL_HI,T_DKIM_INVALID,T_RP_MATCHES_RCVD,UNPARSEABLE_RELAY autolearn=ham version=3.3.1 X-Spam-Checker-Version: SpamAssassin 3.3.1 (2010-03-16) on mail.kernel.org X-Virus-Scanned: ClamAV using ClamSMTP I added an optimization for large files where we would stop searching for backrefs once we had looked at the number of references we currently had for this extent. This works great most of the time, but for snapshots that point to this extent and has changes in the original root this assumption falls on it face. So keep track of any shared refs that point at the bytenr and add their count to any ref that is going to need indirect references looked up. Then use this count as the upper limit for searching through an inode for a bytenr. With this patch we can now find offsets deep in heavily fragmented extents. Thanks, Reportedy-by: Hugo Mills Signed-off-by: Josef Bacik --- fs/btrfs/backref.c | 14 +++++++------- 1 file changed, 7 insertions(+), 7 deletions(-) diff --git a/fs/btrfs/backref.c b/fs/btrfs/backref.c index 0be0e94..4a56d83 100644 --- a/fs/btrfs/backref.c +++ b/fs/btrfs/backref.c @@ -127,6 +127,7 @@ struct __prelim_ref { struct extent_inode_elem *inode_list; u64 parent; u64 wanted_disk_byte; + u64 total_possible_refs; }; static struct kmem_cache *btrfs_prelim_ref_cache; @@ -213,6 +214,7 @@ static int __add_prelim_ref(struct list_head *head, u64 root_id, ref->count = count; ref->parent = parent; ref->wanted_disk_byte = wanted_disk_byte; + ref->total_possible_refs = count; list_add_tail(&ref->list, head); return 0; @@ -249,7 +251,7 @@ static int add_all_parents(struct btrfs_root *root, struct btrfs_path *path, if (path->slots[0] >= btrfs_header_nritems(path->nodes[0])) ret = btrfs_next_old_leaf(root, path, time_seq); - while (!ret && count < ref->count) { + while (!ret && count < ref->total_possible_refs) { eb = path->nodes[0]; slot = path->slots[0]; @@ -521,19 +523,16 @@ static void __merge_refs(struct list_head *head, int mode) for (pos2 = pos1->next, n2 = pos2->next; pos2 != head; pos2 = n2, n2 = pos2->next) { struct __prelim_ref *ref2; - struct __prelim_ref *xchg; struct extent_inode_elem *eie; ref2 = list_entry(pos2, struct __prelim_ref, list); if (mode == 1) { + if (!ref1->parent && ref2->parent) + ref1->total_possible_refs += + ref2->count; if (!ref_for_same_block(ref1, ref2)) continue; - if (!ref1->parent && ref2->parent) { - xchg = ref1; - ref1 = ref2; - ref2 = xchg; - } } else { if (ref1->parent != ref2->parent) continue; @@ -547,6 +546,7 @@ static void __merge_refs(struct list_head *head, int mode) else ref1->inode_list = ref2->inode_list; ref1->count += ref2->count; + ref1->total_possible_refs += ref2->count; list_del(&ref2->list); kmem_cache_free(btrfs_prelim_ref_cache, ref2);