From patchwork Fri Jun 17 01:21:24 2016 Content-Type: text/plain; charset="utf-8" MIME-Version: 1.0 Content-Transfer-Encoding: 7bit X-Patchwork-Submitter: "Darrick J. Wong" X-Patchwork-Id: 9182087 Return-Path: Received: from mail.wl.linuxfoundation.org (pdx-wl-mail.web.codeaurora.org [172.30.200.125]) by pdx-korg-patchwork.web.codeaurora.org (Postfix) with ESMTP id 898C060760 for ; Fri, 17 Jun 2016 01:21:33 +0000 (UTC) Received: from mail.wl.linuxfoundation.org (localhost [127.0.0.1]) by mail.wl.linuxfoundation.org (Postfix) with ESMTP id 7AB7C2839F for ; Fri, 17 Jun 2016 01:21:33 +0000 (UTC) Received: by mail.wl.linuxfoundation.org (Postfix, from userid 486) id 6F914283A1; Fri, 17 Jun 2016 01:21:33 +0000 (UTC) X-Spam-Checker-Version: SpamAssassin 3.3.1 (2010-03-16) on pdx-wl-mail.web.codeaurora.org X-Spam-Level: X-Spam-Status: No, score=-6.9 required=2.0 tests=BAYES_00, RCVD_IN_DNSWL_HI, UNPARSEABLE_RELAY autolearn=ham version=3.3.1 Received: from vger.kernel.org (vger.kernel.org [209.132.180.67]) by mail.wl.linuxfoundation.org (Postfix) with ESMTP id 06EA42839F for ; Fri, 17 Jun 2016 01:21:33 +0000 (UTC) Received: (majordomo@vger.kernel.org) by vger.kernel.org via listexpand id S1755138AbcFQBVb (ORCPT ); Thu, 16 Jun 2016 21:21:31 -0400 Received: from aserp1040.oracle.com ([141.146.126.69]:47311 "EHLO aserp1040.oracle.com" rhost-flags-OK-OK-OK-OK) by vger.kernel.org with ESMTP id S1755133AbcFQBVb (ORCPT ); Thu, 16 Jun 2016 21:21:31 -0400 Received: from userv0022.oracle.com (userv0022.oracle.com [156.151.31.74]) by aserp1040.oracle.com (Sentrion-MTA-4.3.2/Sentrion-MTA-4.3.2) with ESMTP id u5H1LQ9B025940 (version=TLSv1.2 cipher=ECDHE-RSA-AES256-GCM-SHA384 bits=256 verify=OK); Fri, 17 Jun 2016 01:21:27 GMT Received: from userv0122.oracle.com (userv0122.oracle.com [156.151.31.75]) by userv0022.oracle.com (8.14.4/8.13.8) with ESMTP id u5H1LQWA009800 (version=TLSv1/SSLv3 cipher=DHE-RSA-AES256-GCM-SHA384 bits=256 verify=OK); Fri, 17 Jun 2016 01:21:26 GMT Received: from abhmp0003.oracle.com (abhmp0003.oracle.com [141.146.116.9]) by userv0122.oracle.com (8.14.4/8.14.4) with ESMTP id u5H1LQml027577; Fri, 17 Jun 2016 01:21:26 GMT Received: from localhost (/10.145.178.207) by default (Oracle Beehive Gateway v4.0) with ESMTP ; Thu, 16 Jun 2016 18:21:25 -0700 Subject: [PATCH 033/119] xfs: support overlapping intervals in the rmap btree From: "Darrick J. Wong" To: david@fromorbit.com, darrick.wong@oracle.com Cc: linux-fsdevel@vger.kernel.org, vishal.l.verma@intel.com, xfs@oss.sgi.com Date: Thu, 16 Jun 2016 18:21:24 -0700 Message-ID: <146612648418.12839.17068915263834486145.stgit@birch.djwong.org> In-Reply-To: <146612627129.12839.3827886950949809165.stgit@birch.djwong.org> References: <146612627129.12839.3827886950949809165.stgit@birch.djwong.org> User-Agent: StGit/0.17.1-dirty MIME-Version: 1.0 X-Source-IP: userv0022.oracle.com [156.151.31.74] Sender: linux-fsdevel-owner@vger.kernel.org Precedence: bulk List-ID: X-Mailing-List: linux-fsdevel@vger.kernel.org X-Virus-Scanned: ClamAV using ClamSMTP Now that the generic btree code supports overlapping intervals, plug in the rmap btree to this functionality. We will need it to find potential left neighbors in xfs_rmap_{alloc,free} later in the patch set. v2: Fix bit manipulation bug when generating high key offset. v3: Move unwritten bit to rm_offset. Signed-off-by: Darrick J. Wong --- fs/xfs/libxfs/xfs_rmap_btree.c | 59 +++++++++++++++++++++++++++++++++++++++- fs/xfs/libxfs/xfs_rmap_btree.h | 10 +++++-- 2 files changed, 66 insertions(+), 3 deletions(-) -- To unsubscribe from this list: send the line "unsubscribe linux-fsdevel" in the body of a message to majordomo@vger.kernel.org More majordomo info at http://vger.kernel.org/majordomo-info.html diff --git a/fs/xfs/libxfs/xfs_rmap_btree.c b/fs/xfs/libxfs/xfs_rmap_btree.c index c50c725..9adb930 100644 --- a/fs/xfs/libxfs/xfs_rmap_btree.c +++ b/fs/xfs/libxfs/xfs_rmap_btree.c @@ -181,6 +181,28 @@ xfs_rmapbt_init_key_from_rec( } STATIC void +xfs_rmapbt_init_high_key_from_rec( + union xfs_btree_key *key, + union xfs_btree_rec *rec) +{ + __uint64_t off; + int adj; + + adj = be32_to_cpu(rec->rmap.rm_blockcount) - 1; + + key->rmap.rm_startblock = rec->rmap.rm_startblock; + be32_add_cpu(&key->rmap.rm_startblock, adj); + key->rmap.rm_owner = rec->rmap.rm_owner; + key->rmap.rm_offset = rec->rmap.rm_offset; + if (XFS_RMAP_NON_INODE_OWNER(be64_to_cpu(rec->rmap.rm_owner)) || + XFS_RMAP_IS_BMBT_BLOCK(be64_to_cpu(rec->rmap.rm_offset))) + return; + off = be64_to_cpu(key->rmap.rm_offset); + off = (XFS_RMAP_OFF(off) + adj) | (off & ~XFS_RMAP_OFF_MASK); + key->rmap.rm_offset = cpu_to_be64(off); +} + +STATIC void xfs_rmapbt_init_rec_from_cur( struct xfs_btree_cur *cur, union xfs_btree_rec *rec) @@ -235,6 +257,38 @@ xfs_rmapbt_key_diff( return 0; } +STATIC __int64_t +xfs_rmapbt_diff_two_keys( + struct xfs_btree_cur *cur, + union xfs_btree_key *k1, + union xfs_btree_key *k2) +{ + struct xfs_rmap_key *kp1 = &k1->rmap; + struct xfs_rmap_key *kp2 = &k2->rmap; + __int64_t d; + __u64 x, y; + + d = (__int64_t)be32_to_cpu(kp2->rm_startblock) - + be32_to_cpu(kp1->rm_startblock); + if (d) + return d; + + x = be64_to_cpu(kp2->rm_owner); + y = be64_to_cpu(kp1->rm_owner); + if (x > y) + return 1; + else if (y > x) + return -1; + + x = XFS_RMAP_OFF(be64_to_cpu(kp2->rm_offset)); + y = XFS_RMAP_OFF(be64_to_cpu(kp1->rm_offset)); + if (x > y) + return 1; + else if (y > x) + return -1; + return 0; +} + static bool xfs_rmapbt_verify( struct xfs_buf *bp) @@ -350,6 +404,7 @@ xfs_rmapbt_recs_inorder( static const struct xfs_btree_ops xfs_rmapbt_ops = { .rec_len = sizeof(struct xfs_rmap_rec), .key_len = sizeof(struct xfs_rmap_key), + .flags = XFS_BTREE_OPS_OVERLAPPING, .dup_cursor = xfs_rmapbt_dup_cursor, .set_root = xfs_rmapbt_set_root, @@ -358,10 +413,12 @@ static const struct xfs_btree_ops xfs_rmapbt_ops = { .get_minrecs = xfs_rmapbt_get_minrecs, .get_maxrecs = xfs_rmapbt_get_maxrecs, .init_key_from_rec = xfs_rmapbt_init_key_from_rec, + .init_high_key_from_rec = xfs_rmapbt_init_high_key_from_rec, .init_rec_from_cur = xfs_rmapbt_init_rec_from_cur, .init_ptr_from_cur = xfs_rmapbt_init_ptr_from_cur, .key_diff = xfs_rmapbt_key_diff, .buf_ops = &xfs_rmapbt_buf_ops, + .diff_two_keys = xfs_rmapbt_diff_two_keys, #if defined(DEBUG) || defined(XFS_WARN) .keys_inorder = xfs_rmapbt_keys_inorder, .recs_inorder = xfs_rmapbt_recs_inorder, @@ -410,7 +467,7 @@ xfs_rmapbt_maxrecs( if (leaf) return blocklen / sizeof(struct xfs_rmap_rec); return blocklen / - (sizeof(struct xfs_rmap_key) + sizeof(xfs_rmap_ptr_t)); + (2 * sizeof(struct xfs_rmap_key) + sizeof(xfs_rmap_ptr_t)); } /* Compute the maximum height of an rmap btree. */ diff --git a/fs/xfs/libxfs/xfs_rmap_btree.h b/fs/xfs/libxfs/xfs_rmap_btree.h index 17fa383..796071c 100644 --- a/fs/xfs/libxfs/xfs_rmap_btree.h +++ b/fs/xfs/libxfs/xfs_rmap_btree.h @@ -38,12 +38,18 @@ struct xfs_mount; #define XFS_RMAP_KEY_ADDR(block, index) \ ((struct xfs_rmap_key *) \ ((char *)(block) + XFS_RMAP_BLOCK_LEN + \ - ((index) - 1) * sizeof(struct xfs_rmap_key))) + ((index) - 1) * 2 * sizeof(struct xfs_rmap_key))) + +#define XFS_RMAP_HIGH_KEY_ADDR(block, index) \ + ((struct xfs_rmap_key *) \ + ((char *)(block) + XFS_RMAP_BLOCK_LEN + \ + sizeof(struct xfs_rmap_key) + \ + ((index) - 1) * 2 * sizeof(struct xfs_rmap_key))) #define XFS_RMAP_PTR_ADDR(block, index, maxrecs) \ ((xfs_rmap_ptr_t *) \ ((char *)(block) + XFS_RMAP_BLOCK_LEN + \ - (maxrecs) * sizeof(struct xfs_rmap_key) + \ + (maxrecs) * 2 * sizeof(struct xfs_rmap_key) + \ ((index) - 1) * sizeof(xfs_rmap_ptr_t))) struct xfs_btree_cur *xfs_rmapbt_init_cursor(struct xfs_mount *mp,