From: "Darrick J. Wong" <darrick.wong@oracle.com>
To: darrick.wong@oracle.com
Cc: linux-xfs@vger.kernel.org
Subject: [PATCH 07/21] xfs: add realtime rmap btree operations
Date: Tue, 31 Dec 2019 17:17:03 -0800 [thread overview]
Message-ID: <157784142363.1368137.6540778365957586948.stgit@magnolia> (raw)
In-Reply-To: <157784137939.1368137.1149711841610071256.stgit@magnolia>
From: Darrick J. Wong <darrick.wong@oracle.com>
Implement the generic btree operations needed to manipulate rtrmap
btree blocks. This is different from the regular rmapbt in that we
allocate space from the filesystem at large, and are neither
constrained to the free space nor any particular AG.
Signed-off-by: Darrick J. Wong <darrick.wong@oracle.com>
---
fs/xfs/libxfs/xfs_rtrmap_btree.c | 308 ++++++++++++++++++++++++++++++++++++++
1 file changed, 308 insertions(+)
diff --git a/fs/xfs/libxfs/xfs_rtrmap_btree.c b/fs/xfs/libxfs/xfs_rtrmap_btree.c
index 38147bd10a3d..b6a10926359c 100644
--- a/fs/xfs/libxfs/xfs_rtrmap_btree.c
+++ b/fs/xfs/libxfs/xfs_rtrmap_btree.c
@@ -17,12 +17,14 @@
#include "xfs_trans.h"
#include "xfs_alloc.h"
#include "xfs_btree.h"
+#include "xfs_rmap.h"
#include "xfs_rtrmap_btree.h"
#include "xfs_trace.h"
#include "xfs_cksum.h"
#include "xfs_error.h"
#include "xfs_extent_busy.h"
#include "xfs_ag_resv.h"
+#include "xfs_bmap.h"
/*
* Realtime Reverse map btree.
@@ -51,6 +53,264 @@ xfs_rtrmapbt_dup_cursor(
return new;
}
+STATIC int
+xfs_rtrmapbt_alloc_block(
+ struct xfs_btree_cur *cur,
+ union xfs_btree_ptr *start,
+ union xfs_btree_ptr *new,
+ int *stat)
+{
+ struct xfs_alloc_arg args;
+ int error;
+
+ memset(&args, 0, sizeof(args));
+ args.tp = cur->bc_tp;
+ args.mp = cur->bc_mp;
+ args.fsbno = cur->bc_tp->t_firstblock;
+ xfs_rmap_ino_bmbt_owner(&args.oinfo, cur->bc_private.b.ip->i_ino,
+ cur->bc_private.b.whichfork);
+
+ if (args.fsbno == NULLFSBLOCK) {
+ args.fsbno = be64_to_cpu(start->l);
+ args.type = XFS_ALLOCTYPE_START_BNO;
+ /*
+ * Make sure there is sufficient room left in the AG to
+ * complete a full tree split for an extent insert. If
+ * we are converting the middle part of an extent then
+ * we may need space for two tree splits.
+ *
+ * We are relying on the caller to make the correct block
+ * reservation for this operation to succeed. If the
+ * reservation amount is insufficient then we may fail a
+ * block allocation here and corrupt the filesystem.
+ */
+ args.minleft = args.tp->t_blk_res;
+ } else if (cur->bc_tp->t_flags & XFS_TRANS_LOWMODE) {
+ args.type = XFS_ALLOCTYPE_START_BNO;
+ } else {
+ args.type = XFS_ALLOCTYPE_NEAR_BNO;
+ }
+
+ args.minlen = args.maxlen = args.prod = 1;
+ args.wasdel = 0;
+ error = xfs_alloc_vextent(&args);
+ if (error)
+ goto error0;
+
+ if (args.fsbno == NULLFSBLOCK && args.minleft) {
+ /*
+ * Could not find an AG with enough free space to satisfy
+ * a full btree split. Try again without minleft and if
+ * successful activate the lowspace algorithm.
+ */
+ args.fsbno = 0;
+ args.type = XFS_ALLOCTYPE_FIRST_AG;
+ args.minleft = 0;
+ error = xfs_alloc_vextent(&args);
+ if (error)
+ goto error0;
+ cur->bc_tp->t_flags |= XFS_TRANS_LOWMODE;
+ }
+ if (args.fsbno == NULLFSBLOCK) {
+ *stat = 0;
+ return 0;
+ }
+ ASSERT(args.len == 1);
+ cur->bc_private.b.allocated++;
+ cur->bc_private.b.ip->i_d.di_nblocks++;
+ xfs_trans_log_inode(args.tp, cur->bc_private.b.ip, XFS_ILOG_CORE);
+
+ new->l = cpu_to_be64(args.fsbno);
+
+ *stat = 1;
+ return 0;
+
+ error0:
+ return error;
+}
+
+STATIC int
+xfs_rtrmapbt_free_block(
+ struct xfs_btree_cur *cur,
+ struct xfs_buf *bp)
+{
+ struct xfs_mount *mp = cur->bc_mp;
+ struct xfs_inode *ip = cur->bc_private.b.ip;
+ struct xfs_trans *tp = cur->bc_tp;
+ xfs_fsblock_t fsbno = XFS_DADDR_TO_FSB(mp, XFS_BUF_ADDR(bp));
+ struct xfs_owner_info oinfo;
+
+ xfs_rmap_ino_bmbt_owner(&oinfo, ip->i_ino, cur->bc_private.b.whichfork);
+ xfs_bmap_add_free(cur->bc_tp, fsbno, 1, &oinfo);
+ ip->i_d.di_nblocks--;
+
+ xfs_trans_log_inode(tp, ip, XFS_ILOG_CORE);
+ return 0;
+}
+
+/*
+ * Calculate number of records in the in-core realtime rmap btree inode root.
+ */
+STATIC int
+xfs_rtrmapbt_broot_maxrecs(
+ int blocklen,
+ bool leaf)
+{
+ blocklen -= XFS_RTRMAP_BLOCK_LEN;
+
+ if (leaf)
+ return blocklen / sizeof(struct xfs_rtrmap_rec);
+ return blocklen / (2 * sizeof(struct xfs_rtrmap_key) +
+ sizeof(xfs_rtrmap_ptr_t));
+}
+
+STATIC int
+xfs_rtrmapbt_get_minrecs(
+ struct xfs_btree_cur *cur,
+ int level)
+{
+ if (level == cur->bc_nlevels - 1) {
+ struct xfs_ifork *ifp = xfs_btree_ifork_ptr(cur);
+
+ return xfs_rtrmapbt_broot_maxrecs(ifp->if_broot_bytes,
+ level == 0) / 2;
+ }
+
+ return cur->bc_mp->m_rtrmap_mnr[level != 0];
+}
+
+STATIC int
+xfs_rtrmapbt_get_maxrecs(
+ struct xfs_btree_cur *cur,
+ int level)
+{
+ if (level == cur->bc_nlevels - 1) {
+ struct xfs_ifork *ifp = xfs_btree_ifork_ptr(cur);
+
+ return xfs_rtrmapbt_broot_maxrecs(ifp->if_broot_bytes,
+ level == 0);
+ }
+
+ return cur->bc_mp->m_rtrmap_mxr[level != 0];
+}
+
+STATIC void
+xfs_rtrmapbt_init_key_from_rec(
+ union xfs_btree_key *key,
+ union xfs_btree_rec *rec)
+{
+ key->rtrmap.rm_startblock = rec->rtrmap.rm_startblock;
+ key->rtrmap.rm_owner = rec->rtrmap.rm_owner;
+ key->rtrmap.rm_offset = rec->rtrmap.rm_offset;
+}
+
+STATIC void
+xfs_rtrmapbt_init_high_key_from_rec(
+ union xfs_btree_key *key,
+ union xfs_btree_rec *rec)
+{
+ uint64_t off;
+ int adj;
+
+ adj = be64_to_cpu(rec->rtrmap.rm_blockcount) - 1;
+
+ key->rtrmap.rm_startblock = rec->rtrmap.rm_startblock;
+ be64_add_cpu(&key->rtrmap.rm_startblock, adj);
+ key->rtrmap.rm_owner = rec->rtrmap.rm_owner;
+ key->rtrmap.rm_offset = rec->rtrmap.rm_offset;
+ if (XFS_RMAP_NON_INODE_OWNER(be64_to_cpu(rec->rtrmap.rm_owner)) ||
+ XFS_RMAP_IS_BMBT_BLOCK(be64_to_cpu(rec->rtrmap.rm_offset)))
+ return;
+ off = be64_to_cpu(key->rtrmap.rm_offset);
+ off = (XFS_RMAP_OFF(off) + adj) | (off & ~XFS_RMAP_OFF_MASK);
+ key->rtrmap.rm_offset = cpu_to_be64(off);
+}
+
+STATIC void
+xfs_rtrmapbt_init_rec_from_cur(
+ struct xfs_btree_cur *cur,
+ union xfs_btree_rec *rec)
+{
+ rec->rtrmap.rm_startblock = cpu_to_be64(cur->bc_rec.r.rm_startblock);
+ rec->rtrmap.rm_blockcount = cpu_to_be64(cur->bc_rec.r.rm_blockcount);
+ rec->rtrmap.rm_owner = cpu_to_be64(cur->bc_rec.r.rm_owner);
+ rec->rtrmap.rm_offset = cpu_to_be64(
+ xfs_rmap_irec_offset_pack(&cur->bc_rec.r));
+}
+
+STATIC void
+xfs_rtrmapbt_init_ptr_from_cur(
+ struct xfs_btree_cur *cur,
+ union xfs_btree_ptr *ptr)
+{
+ ptr->l = 0;
+}
+
+STATIC int64_t
+xfs_rtrmapbt_key_diff(
+ struct xfs_btree_cur *cur,
+ union xfs_btree_key *key)
+{
+ struct xfs_rmap_irec *rec = &cur->bc_rec.r;
+ struct xfs_rtrmap_key *kp = &key->rtrmap;
+ __u64 x, y;
+
+ x = be64_to_cpu(kp->rm_startblock);
+ y = rec->rm_startblock;
+ if (x > y)
+ return 1;
+ else if (y > x)
+ return -1;
+
+ x = be64_to_cpu(kp->rm_owner);
+ y = rec->rm_owner;
+ if (x > y)
+ return 1;
+ else if (y > x)
+ return -1;
+
+ x = XFS_RMAP_OFF(be64_to_cpu(kp->rm_offset));
+ y = rec->rm_offset;
+ if (x > y)
+ return 1;
+ else if (y > x)
+ return -1;
+ return 0;
+}
+
+STATIC int64_t
+xfs_rtrmapbt_diff_two_keys(
+ struct xfs_btree_cur *cur,
+ union xfs_btree_key *k1,
+ union xfs_btree_key *k2)
+{
+ struct xfs_rtrmap_key *kp1 = &k1->rtrmap;
+ struct xfs_rtrmap_key *kp2 = &k2->rtrmap;
+ __u64 x, y;
+
+ x = be64_to_cpu(kp1->rm_startblock);
+ y = be64_to_cpu(kp2->rm_startblock);
+ if (x > y)
+ return 1;
+ else if (y > x)
+ return -1;
+
+ x = be64_to_cpu(kp1->rm_owner);
+ y = be64_to_cpu(kp2->rm_owner);
+ if (x > y)
+ return 1;
+ else if (y > x)
+ return -1;
+
+ x = XFS_RMAP_OFF(be64_to_cpu(kp1->rm_offset));
+ y = XFS_RMAP_OFF(be64_to_cpu(kp2->rm_offset));
+ if (x > y)
+ return 1;
+ else if (y > x)
+ return -1;
+ return 0;
+}
+
static xfs_failaddr_t
xfs_rtrmapbt_verify(
struct xfs_buf *bp)
@@ -116,12 +376,60 @@ const struct xfs_buf_ops xfs_rtrmapbt_buf_ops = {
.verify_struct = xfs_rtrmapbt_verify,
};
+STATIC int
+xfs_rtrmapbt_keys_inorder(
+ struct xfs_btree_cur *cur,
+ union xfs_btree_key *k1,
+ union xfs_btree_key *k2)
+{
+ if (be64_to_cpu(k1->rtrmap.rm_startblock) <
+ be64_to_cpu(k2->rtrmap.rm_startblock))
+ return 1;
+ if (be64_to_cpu(k1->rtrmap.rm_owner) <
+ be64_to_cpu(k2->rtrmap.rm_owner))
+ return 1;
+ if (XFS_RMAP_OFF(be64_to_cpu(k1->rtrmap.rm_offset)) <=
+ XFS_RMAP_OFF(be64_to_cpu(k2->rtrmap.rm_offset)))
+ return 1;
+ return 0;
+}
+
+STATIC int
+xfs_rtrmapbt_recs_inorder(
+ struct xfs_btree_cur *cur,
+ union xfs_btree_rec *r1,
+ union xfs_btree_rec *r2)
+{
+ if (be64_to_cpu(r1->rtrmap.rm_startblock) <
+ be64_to_cpu(r2->rtrmap.rm_startblock))
+ return 1;
+ if (XFS_RMAP_OFF(be64_to_cpu(r1->rtrmap.rm_offset)) <
+ XFS_RMAP_OFF(be64_to_cpu(r2->rtrmap.rm_offset)))
+ return 1;
+ if (be64_to_cpu(r1->rtrmap.rm_owner) <=
+ be64_to_cpu(r2->rtrmap.rm_owner))
+ return 1;
+ return 0;
+}
+
static const struct xfs_btree_ops xfs_rtrmapbt_ops = {
.rec_len = sizeof(struct xfs_rtrmap_rec),
.key_len = 2 * sizeof(struct xfs_rtrmap_key),
.dup_cursor = xfs_rtrmapbt_dup_cursor,
+ .alloc_block = xfs_rtrmapbt_alloc_block,
+ .free_block = xfs_rtrmapbt_free_block,
+ .get_minrecs = xfs_rtrmapbt_get_minrecs,
+ .get_maxrecs = xfs_rtrmapbt_get_maxrecs,
+ .init_key_from_rec = xfs_rtrmapbt_init_key_from_rec,
+ .init_high_key_from_rec = xfs_rtrmapbt_init_high_key_from_rec,
+ .init_rec_from_cur = xfs_rtrmapbt_init_rec_from_cur,
+ .init_ptr_from_cur = xfs_rtrmapbt_init_ptr_from_cur,
+ .key_diff = xfs_rtrmapbt_key_diff,
.buf_ops = &xfs_rtrmapbt_buf_ops,
+ .diff_two_keys = xfs_rtrmapbt_diff_two_keys,
+ .keys_inorder = xfs_rtrmapbt_keys_inorder,
+ .recs_inorder = xfs_rtrmapbt_recs_inorder,
};
/* Initialize a new rt rmap btree cursor. */
next prev parent reply other threads:[~2020-01-01 1:17 UTC|newest]
Thread overview: 22+ messages / expand[flat|nested] mbox.gz Atom feed top
2020-01-01 1:16 [PATCH v11 00/21] xfs: realtime reverse-mapping support Darrick J. Wong
2020-01-01 1:16 ` [PATCH 01/21] xfs: make iroot_realloc a btree function Darrick J. Wong
2020-01-01 1:16 ` [PATCH 02/21] xfs: support storing records in the inode core root Darrick J. Wong
2020-01-01 1:16 ` [PATCH 03/21] xfs: widen xfs_rmap_irec fields to handle realtime rmapbt Darrick J. Wong
2020-01-01 1:16 ` [PATCH 04/21] xfs: introduce realtime rmap btree definitions Darrick J. Wong
2020-01-01 1:16 ` [PATCH 05/21] xfs: define the on-disk realtime rmap btree format Darrick J. Wong
2020-01-01 1:16 ` [PATCH 06/21] xfs: realtime rmap btree transaction reservations Darrick J. Wong
2020-01-01 1:17 ` Darrick J. Wong [this message]
2020-01-01 1:17 ` [PATCH 08/21] xfs: prepare rmap functions to deal with rtrmapbt Darrick J. Wong
2020-01-01 1:17 ` [PATCH 09/21] xfs: add a realtime flag to the rmap update log redo items Darrick J. Wong
2020-01-01 1:17 ` [PATCH 10/21] xfs: add realtime rmap btree block detection to log recovery Darrick J. Wong
2020-01-01 1:17 ` [PATCH 11/21] xfs: add realtime reverse map inode to superblock Darrick J. Wong
2020-01-01 1:17 ` [PATCH 12/21] xfs: wire up a new inode fork type for the realtime rmap Darrick J. Wong
2020-01-01 1:17 ` [PATCH 13/21] xfs: wire up rmap map and unmap to the realtime rmapbt Darrick J. Wong
2020-01-01 1:17 ` [PATCH 14/21] xfs: create routine to allocate and initialize a realtime rmap btree inode Darrick J. Wong
2020-01-01 1:17 ` [PATCH 15/21] xfs: dynamically create the realtime rmapbt inode when attaching rtdev Darrick J. Wong
2020-01-01 1:17 ` [PATCH 16/21] xfs: enable realtime rmap btree Darrick J. Wong
2020-01-01 1:18 ` [PATCH 17/21] xfs: wire up getfsmap to the realtime reverse mapping btree Darrick J. Wong
2020-01-01 1:18 ` [PATCH 18/21] xfs: scrub the realtime rmapbt Darrick J. Wong
2020-01-01 1:18 ` [PATCH 19/21] xfs: cross-reference realtime bitmap to realtime rmapbt scrubber Darrick J. Wong
2020-01-01 1:18 ` [PATCH 20/21] xfs: cross-reference the realtime rmapbt Darrick J. Wong
2020-01-01 1:18 ` [PATCH 21/21] xfs: report realtime rmap btree corruption errors to the health system Darrick J. Wong
Reply instructions:
You may reply publicly to this message via plain-text email
using any one of the following methods:
* Save the following mbox file, import it into your mail client,
and reply-to-all from there: mbox
Avoid top-posting and favor interleaved quoting:
https://en.wikipedia.org/wiki/Posting_style#Interleaved_style
* Reply using the --to, --cc, and --in-reply-to
switches of git-send-email(1):
git send-email \
--in-reply-to=157784142363.1368137.6540778365957586948.stgit@magnolia \
--to=darrick.wong@oracle.com \
--cc=linux-xfs@vger.kernel.org \
/path/to/YOUR_REPLY
https://kernel.org/pub/software/scm/git/docs/git-send-email.html
* If your mail client supports setting the In-Reply-To header
via mailto: links, try the mailto: link
Be sure your reply has a Subject: header at the top and a blank line
before the message body.
This is a public inbox, see mirroring instructions
for how to clone and mirror all data and code used for this inbox;
as well as URLs for NNTP newsgroup(s).