From 2c813ad66a7218a64db68f0a4bfa8d2d9caef4c0 Mon Sep 17 00:00:00 2001 From: "Darrick J. Wong" Date: Wed, 3 Aug 2016 11:08:36 +1000 Subject: xfs: support btrees with overlapping intervals for keys On a filesystem with both reflink and reverse mapping enabled, it's possible to have multiple rmap records referring to the same blocks on disk. When overlapping intervals are possible, querying a classic btree to find all records intersecting a given interval is inefficient because we cannot use the left side of the search interval to filter out non-matching records the same way that we can use the existing btree key to filter out records coming after the right side of the search interval. This will become important once we want to use the rmap btree to rebuild BMBTs, or implement the (future) fsmap ioctl. (For the non-overlapping case, we can perform such queries trivially by starting at the left side of the interval and walking the tree until we pass the right side.) Therefore, extend the btree code to come closer to supporting intervals as a first-class record attribute. This involves widening the btree node's key space to store both the lowest key reachable via the node pointer (as the btree does now) and the highest key reachable via the same pointer and teaching the btree modifying functions to keep the highest-key records up to date. This behavior can be turned on via a new btree ops flag so that btrees that cannot store overlapping intervals don't pay the overhead costs in terms of extra code and disk format changes. When we're deleting a record in a btree that supports overlapped interval records and the deletion results in two btree blocks being joined, we defer updating the high/low keys until after all possible joining (at higher levels in the tree) have finished. At this point, the btree pointers at all levels have been updated to remove the empty blocks and we can update the low and high keys. When we're doing this, we must be careful to update the keys of all node pointers up to the root instead of stopping at the first set of keys that don't need updating. This is because it's possible for a single deletion to cause joining of multiple levels of tree, and so we need to update everything going back to the root. The diff_two_keys functions return < 0, 0, or > 0 if key1 is less than, equal to, or greater than key2, respectively. This is consistent with the rest of the kernel and the C library. In btree_updkeys(), we need to evaluate the force_all parameter before running the key diff to avoid reading uninitialized memory when we're forcing a key update. This happens when we've allocated an empty slot at level N + 1 to point to a new block at level N and we're in the process of filling out the new keys. Signed-off-by: Darrick J. Wong Reviewed-by: Dave Chinner Signed-off-by: Dave Chinner --- fs/xfs/xfs_trace.h | 36 ++++++++++++++++++++++++++++++++++++ 1 file changed, 36 insertions(+) (limited to 'fs/xfs/xfs_trace.h') diff --git a/fs/xfs/xfs_trace.h b/fs/xfs/xfs_trace.h index 145169093fe0..8fb59e644f80 100644 --- a/fs/xfs/xfs_trace.h +++ b/fs/xfs/xfs_trace.h @@ -38,6 +38,7 @@ struct xlog_recover_item; struct xfs_buf_log_format; struct xfs_inode_log_format; struct xfs_bmbt_irec; +struct xfs_btree_cur; DECLARE_EVENT_CLASS(xfs_attr_list_class, TP_PROTO(struct xfs_attr_list_context *ctx), @@ -2185,6 +2186,41 @@ DEFINE_DISCARD_EVENT(xfs_discard_toosmall); DEFINE_DISCARD_EVENT(xfs_discard_exclude); DEFINE_DISCARD_EVENT(xfs_discard_busy); +/* btree cursor events */ +DECLARE_EVENT_CLASS(xfs_btree_cur_class, + TP_PROTO(struct xfs_btree_cur *cur, int level, struct xfs_buf *bp), + TP_ARGS(cur, level, bp), + TP_STRUCT__entry( + __field(dev_t, dev) + __field(xfs_btnum_t, btnum) + __field(int, level) + __field(int, nlevels) + __field(int, ptr) + __field(xfs_daddr_t, daddr) + ), + TP_fast_assign( + __entry->dev = cur->bc_mp->m_super->s_dev; + __entry->btnum = cur->bc_btnum; + __entry->level = level; + __entry->nlevels = cur->bc_nlevels; + __entry->ptr = cur->bc_ptrs[level]; + __entry->daddr = bp ? bp->b_bn : -1; + ), + TP_printk("dev %d:%d btnum %d level %d/%d ptr %d daddr 0x%llx", + MAJOR(__entry->dev), MINOR(__entry->dev), + __entry->btnum, + __entry->level, + __entry->nlevels, + __entry->ptr, + (unsigned long long)__entry->daddr) +) + +#define DEFINE_BTREE_CUR_EVENT(name) \ +DEFINE_EVENT(xfs_btree_cur_class, name, \ + TP_PROTO(struct xfs_btree_cur *cur, int level, struct xfs_buf *bp), \ + TP_ARGS(cur, level, bp)) +DEFINE_BTREE_CUR_EVENT(xfs_btree_updkeys); + #endif /* _TRACE_XFS_H */ #undef TRACE_INCLUDE_PATH -- cgit v1.2.3 From 105f7d83db4f82ce170893eaaca946754e38541f Mon Sep 17 00:00:00 2001 From: "Darrick J. Wong" Date: Wed, 3 Aug 2016 11:10:21 +1000 Subject: xfs: introduce interval queries on btrees Create a function to enable querying of btree records mapping to a range of keys. This will be used in subsequent patches to allow querying the reverse mapping btree to find the extents mapped to a range of physical blocks, though the generic code can be used for any range query. The overlapped query range function needs to use the btree get_block helper because the root block could be an inode, in which case bc_bufs[nlevels-1] will be NULL. Signed-off-by: Darrick J. Wong Reviewed-by: Christoph Hellwig Signed-off-by: Dave Chinner --- fs/xfs/libxfs/xfs_btree.c | 264 ++++++++++++++++++++++++++++++++++++++++++++++ fs/xfs/libxfs/xfs_btree.h | 22 +++- fs/xfs/xfs_trace.h | 1 + 3 files changed, 282 insertions(+), 5 deletions(-) (limited to 'fs/xfs/xfs_trace.h') diff --git a/fs/xfs/libxfs/xfs_btree.c b/fs/xfs/libxfs/xfs_btree.c index 5c1b35a23a3d..d79dcb08ed18 100644 --- a/fs/xfs/libxfs/xfs_btree.c +++ b/fs/xfs/libxfs/xfs_btree.c @@ -4521,3 +4521,267 @@ xfs_btree_compute_maxlevels( maxblocks = (maxblocks + limits[1] - 1) / limits[1]; return level; } + +/* + * Query a regular btree for all records overlapping a given interval. + * Start with a LE lookup of the key of low_rec and return all records + * until we find a record with a key greater than the key of high_rec. + */ +STATIC int +xfs_btree_simple_query_range( + struct xfs_btree_cur *cur, + union xfs_btree_key *low_key, + union xfs_btree_key *high_key, + xfs_btree_query_range_fn fn, + void *priv) +{ + union xfs_btree_rec *recp; + union xfs_btree_key rec_key; + __int64_t diff; + int stat; + bool firstrec = true; + int error; + + ASSERT(cur->bc_ops->init_high_key_from_rec); + ASSERT(cur->bc_ops->diff_two_keys); + + /* + * Find the leftmost record. The btree cursor must be set + * to the low record used to generate low_key. + */ + stat = 0; + error = xfs_btree_lookup(cur, XFS_LOOKUP_LE, &stat); + if (error) + goto out; + + while (stat) { + /* Find the record. */ + error = xfs_btree_get_rec(cur, &recp, &stat); + if (error || !stat) + break; + cur->bc_ops->init_high_key_from_rec(&rec_key, recp); + + /* Skip if high_key(rec) < low_key. */ + if (firstrec) { + firstrec = false; + diff = cur->bc_ops->diff_two_keys(cur, low_key, + &rec_key); + if (diff > 0) + goto advloop; + } + + /* Stop if high_key < low_key(rec). */ + diff = cur->bc_ops->diff_two_keys(cur, &rec_key, high_key); + if (diff > 0) + break; + + /* Callback */ + error = fn(cur, recp, priv); + if (error < 0 || error == XFS_BTREE_QUERY_RANGE_ABORT) + break; + +advloop: + /* Move on to the next record. */ + error = xfs_btree_increment(cur, 0, &stat); + if (error) + break; + } + +out: + return error; +} + +/* + * Query an overlapped interval btree for all records overlapping a given + * interval. This function roughly follows the algorithm given in + * "Interval Trees" of _Introduction to Algorithms_, which is section + * 14.3 in the 2nd and 3rd editions. + * + * First, generate keys for the low and high records passed in. + * + * For any leaf node, generate the high and low keys for the record. + * If the record keys overlap with the query low/high keys, pass the + * record to the function iterator. + * + * For any internal node, compare the low and high keys of each + * pointer against the query low/high keys. If there's an overlap, + * follow the pointer. + * + * As an optimization, we stop scanning a block when we find a low key + * that is greater than the query's high key. + */ +STATIC int +xfs_btree_overlapped_query_range( + struct xfs_btree_cur *cur, + union xfs_btree_key *low_key, + union xfs_btree_key *high_key, + xfs_btree_query_range_fn fn, + void *priv) +{ + union xfs_btree_ptr ptr; + union xfs_btree_ptr *pp; + union xfs_btree_key rec_key; + union xfs_btree_key rec_hkey; + union xfs_btree_key *lkp; + union xfs_btree_key *hkp; + union xfs_btree_rec *recp; + struct xfs_btree_block *block; + __int64_t ldiff; + __int64_t hdiff; + int level; + struct xfs_buf *bp; + int i; + int error; + + /* Load the root of the btree. */ + level = cur->bc_nlevels - 1; + cur->bc_ops->init_ptr_from_cur(cur, &ptr); + error = xfs_btree_lookup_get_block(cur, level, &ptr, &block); + if (error) + return error; + xfs_btree_get_block(cur, level, &bp); + trace_xfs_btree_overlapped_query_range(cur, level, bp); +#ifdef DEBUG + error = xfs_btree_check_block(cur, block, level, bp); + if (error) + goto out; +#endif + cur->bc_ptrs[level] = 1; + + while (level < cur->bc_nlevels) { + block = xfs_btree_get_block(cur, level, &bp); + + /* End of node, pop back towards the root. */ + if (cur->bc_ptrs[level] > be16_to_cpu(block->bb_numrecs)) { +pop_up: + if (level < cur->bc_nlevels - 1) + cur->bc_ptrs[level + 1]++; + level++; + continue; + } + + if (level == 0) { + /* Handle a leaf node. */ + recp = xfs_btree_rec_addr(cur, cur->bc_ptrs[0], block); + + cur->bc_ops->init_high_key_from_rec(&rec_hkey, recp); + ldiff = cur->bc_ops->diff_two_keys(cur, &rec_hkey, + low_key); + + cur->bc_ops->init_key_from_rec(&rec_key, recp); + hdiff = cur->bc_ops->diff_two_keys(cur, high_key, + &rec_key); + + /* + * If (record's high key >= query's low key) and + * (query's high key >= record's low key), then + * this record overlaps the query range; callback. + */ + if (ldiff >= 0 && hdiff >= 0) { + error = fn(cur, recp, priv); + if (error < 0 || + error == XFS_BTREE_QUERY_RANGE_ABORT) + break; + } else if (hdiff < 0) { + /* Record is larger than high key; pop. */ + goto pop_up; + } + cur->bc_ptrs[level]++; + continue; + } + + /* Handle an internal node. */ + lkp = xfs_btree_key_addr(cur, cur->bc_ptrs[level], block); + hkp = xfs_btree_high_key_addr(cur, cur->bc_ptrs[level], block); + pp = xfs_btree_ptr_addr(cur, cur->bc_ptrs[level], block); + + ldiff = cur->bc_ops->diff_two_keys(cur, hkp, low_key); + hdiff = cur->bc_ops->diff_two_keys(cur, high_key, lkp); + + /* + * If (pointer's high key >= query's low key) and + * (query's high key >= pointer's low key), then + * this record overlaps the query range; follow pointer. + */ + if (ldiff >= 0 && hdiff >= 0) { + level--; + error = xfs_btree_lookup_get_block(cur, level, pp, + &block); + if (error) + goto out; + xfs_btree_get_block(cur, level, &bp); + trace_xfs_btree_overlapped_query_range(cur, level, bp); +#ifdef DEBUG + error = xfs_btree_check_block(cur, block, level, bp); + if (error) + goto out; +#endif + cur->bc_ptrs[level] = 1; + continue; + } else if (hdiff < 0) { + /* The low key is larger than the upper range; pop. */ + goto pop_up; + } + cur->bc_ptrs[level]++; + } + +out: + /* + * If we don't end this function with the cursor pointing at a record + * block, a subsequent non-error cursor deletion will not release + * node-level buffers, causing a buffer leak. This is quite possible + * with a zero-results range query, so release the buffers if we + * failed to return any results. + */ + if (cur->bc_bufs[0] == NULL) { + for (i = 0; i < cur->bc_nlevels; i++) { + if (cur->bc_bufs[i]) { + xfs_trans_brelse(cur->bc_tp, cur->bc_bufs[i]); + cur->bc_bufs[i] = NULL; + cur->bc_ptrs[i] = 0; + cur->bc_ra[i] = 0; + } + } + } + + return error; +} + +/* + * Query a btree for all records overlapping a given interval of keys. The + * supplied function will be called with each record found; return one of the + * XFS_BTREE_QUERY_RANGE_{CONTINUE,ABORT} values or the usual negative error + * code. This function returns XFS_BTREE_QUERY_RANGE_ABORT, zero, or a + * negative error code. + */ +int +xfs_btree_query_range( + struct xfs_btree_cur *cur, + union xfs_btree_irec *low_rec, + union xfs_btree_irec *high_rec, + xfs_btree_query_range_fn fn, + void *priv) +{ + union xfs_btree_rec rec; + union xfs_btree_key low_key; + union xfs_btree_key high_key; + + /* Find the keys of both ends of the interval. */ + cur->bc_rec = *high_rec; + cur->bc_ops->init_rec_from_cur(cur, &rec); + cur->bc_ops->init_key_from_rec(&high_key, &rec); + + cur->bc_rec = *low_rec; + cur->bc_ops->init_rec_from_cur(cur, &rec); + cur->bc_ops->init_key_from_rec(&low_key, &rec); + + /* Enforce low key < high key. */ + if (cur->bc_ops->diff_two_keys(cur, &low_key, &high_key) > 0) + return -EINVAL; + + if (!(cur->bc_flags & XFS_BTREE_OVERLAPPING)) + return xfs_btree_simple_query_range(cur, &low_key, + &high_key, fn, priv); + return xfs_btree_overlapped_query_range(cur, &low_key, &high_key, + fn, priv); +} diff --git a/fs/xfs/libxfs/xfs_btree.h b/fs/xfs/libxfs/xfs_btree.h index bce6daacb1f7..34c13616d255 100644 --- a/fs/xfs/libxfs/xfs_btree.h +++ b/fs/xfs/libxfs/xfs_btree.h @@ -227,6 +227,12 @@ struct xfs_btree_ops { #define LASTREC_DELREC 2 +union xfs_btree_irec { + struct xfs_alloc_rec_incore a; + struct xfs_bmbt_irec b; + struct xfs_inobt_rec_incore i; +}; + /* * Btree cursor structure. * This collects all information needed by the btree code in one place. @@ -237,11 +243,7 @@ typedef struct xfs_btree_cur struct xfs_mount *bc_mp; /* file system mount struct */ const struct xfs_btree_ops *bc_ops; uint bc_flags; /* btree features - below */ - union { - xfs_alloc_rec_incore_t a; - xfs_bmbt_irec_t b; - xfs_inobt_rec_incore_t i; - } bc_rec; /* current insert/search record value */ + union xfs_btree_irec bc_rec; /* current insert/search record value */ struct xfs_buf *bc_bufs[XFS_BTREE_MAXLEVELS]; /* buf ptr per level */ int bc_ptrs[XFS_BTREE_MAXLEVELS]; /* key/record # */ __uint8_t bc_ra[XFS_BTREE_MAXLEVELS]; /* readahead bits */ @@ -524,4 +526,14 @@ void xfs_btree_get_node_keys_overlapped(struct xfs_btree_cur *cur, struct xfs_btree_block *block, union xfs_btree_key *key); int xfs_btree_update_keys_overlapped(struct xfs_btree_cur *cur, int level); +/* return codes */ +#define XFS_BTREE_QUERY_RANGE_CONTINUE 0 /* keep iterating */ +#define XFS_BTREE_QUERY_RANGE_ABORT 1 /* stop iterating */ +typedef int (*xfs_btree_query_range_fn)(struct xfs_btree_cur *cur, + union xfs_btree_rec *rec, void *priv); + +int xfs_btree_query_range(struct xfs_btree_cur *cur, + union xfs_btree_irec *low_rec, union xfs_btree_irec *high_rec, + xfs_btree_query_range_fn fn, void *priv); + #endif /* __XFS_BTREE_H__ */ diff --git a/fs/xfs/xfs_trace.h b/fs/xfs/xfs_trace.h index 8fb59e644f80..a5862680db31 100644 --- a/fs/xfs/xfs_trace.h +++ b/fs/xfs/xfs_trace.h @@ -2220,6 +2220,7 @@ DEFINE_EVENT(xfs_btree_cur_class, name, \ TP_PROTO(struct xfs_btree_cur *cur, int level, struct xfs_buf *bp), \ TP_ARGS(cur, level, bp)) DEFINE_BTREE_CUR_EVENT(xfs_btree_updkeys); +DEFINE_BTREE_CUR_EVENT(xfs_btree_overlapped_query_range); #endif /* _TRACE_XFS_H */ -- cgit v1.2.3 From 3cd48abcc1f76d6cd5ce61f3540801849a6c82e0 Mon Sep 17 00:00:00 2001 From: "Darrick J. Wong" Date: Wed, 3 Aug 2016 11:13:02 +1000 Subject: xfs: add tracepoints for the deferred ops mechanism Add tracepoints for the internals of the deferred ops mechanism and tracepoint classes for clients of the dops, to make debugging easier. Signed-off-by: Darrick J. Wong Reviewed-by: Brian Foster Signed-off-by: Dave Chinner --- fs/xfs/libxfs/xfs_defer.c | 19 +++++ fs/xfs/xfs_trace.c | 1 + fs/xfs/xfs_trace.h | 198 ++++++++++++++++++++++++++++++++++++++++++++++ 3 files changed, 218 insertions(+) (limited to 'fs/xfs/xfs_trace.h') diff --git a/fs/xfs/libxfs/xfs_defer.c b/fs/xfs/libxfs/xfs_defer.c index 2809db75e0d3..054a2032fdb3 100644 --- a/fs/xfs/libxfs/xfs_defer.c +++ b/fs/xfs/libxfs/xfs_defer.c @@ -159,6 +159,7 @@ xfs_defer_intake_work( struct xfs_defer_pending *dfp; list_for_each_entry(dfp, &dop->dop_intake, dfp_list) { + trace_xfs_defer_intake_work(tp->t_mountp, dfp); dfp->dfp_intent = dfp->dfp_type->create_intent(tp, dfp->dfp_count); list_sort(tp->t_mountp, &dfp->dfp_work, @@ -179,6 +180,7 @@ xfs_defer_trans_abort( { struct xfs_defer_pending *dfp; + trace_xfs_defer_trans_abort(tp->t_mountp, dop); /* * If the transaction was committed, drop the intent reference * since we're bailing out of here. The other reference is @@ -191,6 +193,7 @@ xfs_defer_trans_abort( /* Abort intent items. */ list_for_each_entry(dfp, &dop->dop_pending, dfp_list) { + trace_xfs_defer_pending_abort(tp->t_mountp, dfp); if (dfp->dfp_committed) dfp->dfp_type->abort_intent(dfp->dfp_intent); } @@ -217,9 +220,12 @@ xfs_defer_trans_roll( xfs_trans_log_inode(*tp, dop->dop_inodes[i], XFS_ILOG_CORE); } + trace_xfs_defer_trans_roll((*tp)->t_mountp, dop); + /* Roll the transaction. */ error = xfs_trans_roll(tp, ip); if (error) { + trace_xfs_defer_trans_roll_error((*tp)->t_mountp, dop, error); xfs_defer_trans_abort(*tp, dop, error); return error; } @@ -291,6 +297,8 @@ xfs_defer_finish( ASSERT((*tp)->t_flags & XFS_TRANS_PERM_LOG_RES); + trace_xfs_defer_finish((*tp)->t_mountp, dop); + /* Until we run out of pending work to finish... */ while (xfs_defer_has_unfinished_work(dop)) { /* Log intents for work items sitting in the intake. */ @@ -305,12 +313,14 @@ xfs_defer_finish( list_for_each_entry_reverse(dfp, &dop->dop_pending, dfp_list) { if (dfp->dfp_committed) break; + trace_xfs_defer_pending_commit((*tp)->t_mountp, dfp); dfp->dfp_committed = true; } /* Log an intent-done item for the first pending item. */ dfp = list_first_entry(&dop->dop_pending, struct xfs_defer_pending, dfp_list); + trace_xfs_defer_pending_finish((*tp)->t_mountp, dfp); done_item = dfp->dfp_type->create_done(*tp, dfp->dfp_intent, dfp->dfp_count); cleanup_fn = dfp->dfp_type->finish_cleanup; @@ -343,6 +353,10 @@ xfs_defer_finish( } out: + if (error) + trace_xfs_defer_finish_error((*tp)->t_mountp, dop, error); + else + trace_xfs_defer_finish_done((*tp)->t_mountp, dop); return error; } @@ -358,11 +372,14 @@ xfs_defer_cancel( struct list_head *pwi; struct list_head *n; + trace_xfs_defer_cancel(NULL, dop); + /* * Free the pending items. Caller should already have arranged * for the intent items to be released. */ list_for_each_entry_safe(dfp, pli, &dop->dop_intake, dfp_list) { + trace_xfs_defer_intake_cancel(NULL, dfp); list_del(&dfp->dfp_list); list_for_each_safe(pwi, n, &dfp->dfp_work) { list_del(pwi); @@ -373,6 +390,7 @@ xfs_defer_cancel( kmem_free(dfp); } list_for_each_entry_safe(dfp, pli, &dop->dop_pending, dfp_list) { + trace_xfs_defer_pending_cancel(NULL, dfp); list_del(&dfp->dfp_list); list_for_each_safe(pwi, n, &dfp->dfp_work) { list_del(pwi); @@ -441,4 +459,5 @@ xfs_defer_init( *fbp = NULLFSBLOCK; INIT_LIST_HEAD(&dop->dop_intake); INIT_LIST_HEAD(&dop->dop_pending); + trace_xfs_defer_init(NULL, dop); } diff --git a/fs/xfs/xfs_trace.c b/fs/xfs/xfs_trace.c index 13a029806805..3971527c9a07 100644 --- a/fs/xfs/xfs_trace.c +++ b/fs/xfs/xfs_trace.c @@ -22,6 +22,7 @@ #include "xfs_log_format.h" #include "xfs_trans_resv.h" #include "xfs_mount.h" +#include "xfs_defer.h" #include "xfs_da_format.h" #include "xfs_inode.h" #include "xfs_btree.h" diff --git a/fs/xfs/xfs_trace.h b/fs/xfs/xfs_trace.h index a5862680db31..a45b030d4592 100644 --- a/fs/xfs/xfs_trace.h +++ b/fs/xfs/xfs_trace.h @@ -2222,6 +2222,204 @@ DEFINE_EVENT(xfs_btree_cur_class, name, \ DEFINE_BTREE_CUR_EVENT(xfs_btree_updkeys); DEFINE_BTREE_CUR_EVENT(xfs_btree_overlapped_query_range); +/* deferred ops */ +struct xfs_defer_pending; +struct xfs_defer_intake; +struct xfs_defer_ops; + +DECLARE_EVENT_CLASS(xfs_defer_class, + TP_PROTO(struct xfs_mount *mp, struct xfs_defer_ops *dop), + TP_ARGS(mp, dop), + TP_STRUCT__entry( + __field(dev_t, dev) + __field(void *, dop) + __field(bool, committed) + __field(bool, low) + ), + TP_fast_assign( + __entry->dev = mp ? mp->m_super->s_dev : 0; + __entry->dop = dop; + __entry->committed = dop->dop_committed; + __entry->low = dop->dop_low; + ), + TP_printk("dev %d:%d ops %p committed %d low %d\n", + MAJOR(__entry->dev), MINOR(__entry->dev), + __entry->dop, + __entry->committed, + __entry->low) +) +#define DEFINE_DEFER_EVENT(name) \ +DEFINE_EVENT(xfs_defer_class, name, \ + TP_PROTO(struct xfs_mount *mp, struct xfs_defer_ops *dop), \ + TP_ARGS(mp, dop)) + +DECLARE_EVENT_CLASS(xfs_defer_error_class, + TP_PROTO(struct xfs_mount *mp, struct xfs_defer_ops *dop, int error), + TP_ARGS(mp, dop, error), + TP_STRUCT__entry( + __field(dev_t, dev) + __field(void *, dop) + __field(bool, committed) + __field(bool, low) + __field(int, error) + ), + TP_fast_assign( + __entry->dev = mp ? mp->m_super->s_dev : 0; + __entry->dop = dop; + __entry->committed = dop->dop_committed; + __entry->low = dop->dop_low; + __entry->error = error; + ), + TP_printk("dev %d:%d ops %p committed %d low %d err %d\n", + MAJOR(__entry->dev), MINOR(__entry->dev), + __entry->dop, + __entry->committed, + __entry->low, + __entry->error) +) +#define DEFINE_DEFER_ERROR_EVENT(name) \ +DEFINE_EVENT(xfs_defer_error_class, name, \ + TP_PROTO(struct xfs_mount *mp, struct xfs_defer_ops *dop, int error), \ + TP_ARGS(mp, dop, error)) + +DECLARE_EVENT_CLASS(xfs_defer_pending_class, + TP_PROTO(struct xfs_mount *mp, struct xfs_defer_pending *dfp), + TP_ARGS(mp, dfp), + TP_STRUCT__entry( + __field(dev_t, dev) + __field(int, type) + __field(void *, intent) + __field(bool, committed) + __field(int, nr) + ), + TP_fast_assign( + __entry->dev = mp ? mp->m_super->s_dev : 0; + __entry->type = dfp->dfp_type->type; + __entry->intent = dfp->dfp_intent; + __entry->committed = dfp->dfp_committed; + __entry->nr = dfp->dfp_count; + ), + TP_printk("dev %d:%d optype %d intent %p committed %d nr %d\n", + MAJOR(__entry->dev), MINOR(__entry->dev), + __entry->type, + __entry->intent, + __entry->committed, + __entry->nr) +) +#define DEFINE_DEFER_PENDING_EVENT(name) \ +DEFINE_EVENT(xfs_defer_pending_class, name, \ + TP_PROTO(struct xfs_mount *mp, struct xfs_defer_pending *dfp), \ + TP_ARGS(mp, dfp)) + +DECLARE_EVENT_CLASS(xfs_phys_extent_deferred_class, + TP_PROTO(struct xfs_mount *mp, xfs_agnumber_t agno, + int type, xfs_agblock_t agbno, xfs_extlen_t len), + TP_ARGS(mp, agno, type, agbno, len), + TP_STRUCT__entry( + __field(dev_t, dev) + __field(xfs_agnumber_t, agno) + __field(int, type) + __field(xfs_agblock_t, agbno) + __field(xfs_extlen_t, len) + ), + TP_fast_assign( + __entry->dev = mp->m_super->s_dev; + __entry->agno = agno; + __entry->type = type; + __entry->agbno = agbno; + __entry->len = len; + ), + TP_printk("dev %d:%d op %d agno %u agbno %u len %u", + MAJOR(__entry->dev), MINOR(__entry->dev), + __entry->type, + __entry->agno, + __entry->agbno, + __entry->len) +); +#define DEFINE_PHYS_EXTENT_DEFERRED_EVENT(name) \ +DEFINE_EVENT(xfs_phys_extent_deferred_class, name, \ + TP_PROTO(struct xfs_mount *mp, xfs_agnumber_t agno, \ + int type, \ + xfs_agblock_t bno, \ + xfs_extlen_t len), \ + TP_ARGS(mp, agno, type, bno, len)) + +DECLARE_EVENT_CLASS(xfs_map_extent_deferred_class, + TP_PROTO(struct xfs_mount *mp, xfs_agnumber_t agno, + int op, + xfs_agblock_t agbno, + xfs_ino_t ino, + int whichfork, + xfs_fileoff_t offset, + xfs_filblks_t len, + xfs_exntst_t state), + TP_ARGS(mp, agno, op, agbno, ino, whichfork, offset, len, state), + TP_STRUCT__entry( + __field(dev_t, dev) + __field(xfs_agnumber_t, agno) + __field(xfs_ino_t, ino) + __field(xfs_agblock_t, agbno) + __field(int, whichfork) + __field(xfs_fileoff_t, l_loff) + __field(xfs_filblks_t, l_len) + __field(xfs_exntst_t, l_state) + __field(int, op) + ), + TP_fast_assign( + __entry->dev = mp->m_super->s_dev; + __entry->agno = agno; + __entry->ino = ino; + __entry->agbno = agbno; + __entry->whichfork = whichfork; + __entry->l_loff = offset; + __entry->l_len = len; + __entry->l_state = state; + __entry->op = op; + ), + TP_printk("dev %d:%d op %d agno %u agbno %u owner %lld %s offset %llu len %llu state %d", + MAJOR(__entry->dev), MINOR(__entry->dev), + __entry->op, + __entry->agno, + __entry->agbno, + __entry->ino, + __entry->whichfork == XFS_ATTR_FORK ? "attr" : "data", + __entry->l_loff, + __entry->l_len, + __entry->l_state) +); +#define DEFINE_MAP_EXTENT_DEFERRED_EVENT(name) \ +DEFINE_EVENT(xfs_map_extent_deferred_class, name, \ + TP_PROTO(struct xfs_mount *mp, xfs_agnumber_t agno, \ + int op, \ + xfs_agblock_t agbno, \ + xfs_ino_t ino, \ + int whichfork, \ + xfs_fileoff_t offset, \ + xfs_filblks_t len, \ + xfs_exntst_t state), \ + TP_ARGS(mp, agno, op, agbno, ino, whichfork, offset, len, state)) + +DEFINE_DEFER_EVENT(xfs_defer_init); +DEFINE_DEFER_EVENT(xfs_defer_cancel); +DEFINE_DEFER_EVENT(xfs_defer_trans_roll); +DEFINE_DEFER_EVENT(xfs_defer_trans_abort); +DEFINE_DEFER_EVENT(xfs_defer_finish); +DEFINE_DEFER_EVENT(xfs_defer_finish_done); + +DEFINE_DEFER_ERROR_EVENT(xfs_defer_trans_roll_error); +DEFINE_DEFER_ERROR_EVENT(xfs_defer_finish_error); +DEFINE_DEFER_ERROR_EVENT(xfs_defer_op_finish_error); + +DEFINE_DEFER_PENDING_EVENT(xfs_defer_intake_work); +DEFINE_DEFER_PENDING_EVENT(xfs_defer_intake_cancel); +DEFINE_DEFER_PENDING_EVENT(xfs_defer_pending_commit); +DEFINE_DEFER_PENDING_EVENT(xfs_defer_pending_cancel); +DEFINE_DEFER_PENDING_EVENT(xfs_defer_pending_finish); +DEFINE_DEFER_PENDING_EVENT(xfs_defer_pending_abort); + +DEFINE_PHYS_EXTENT_DEFERRED_EVENT(xfs_defer_phys_extent); +DEFINE_MAP_EXTENT_DEFERRED_EVENT(xfs_defer_map_extent); + #endif /* _TRACE_XFS_H */ #undef TRACE_INCLUDE_PATH -- cgit v1.2.3 From ba9e780246a15a35f8ebe5b60f4a11bb58e85bda Mon Sep 17 00:00:00 2001 From: "Darrick J. Wong" Date: Wed, 3 Aug 2016 11:26:33 +1000 Subject: xfs: add tracepoints and error injection for deferred extent freeing Add a couple of tracepoints for the deferred extent free operation and a site for injecting errors while finishing the operation. This makes it easier to debug deferred ops and test log redo. Signed-off-by: Darrick J. Wong Reviewed-by: Dave Chinner Signed-off-by: Dave Chinner --- fs/xfs/libxfs/xfs_alloc.c | 7 +++++++ fs/xfs/libxfs/xfs_bmap.c | 2 ++ fs/xfs/xfs_error.h | 4 +++- fs/xfs/xfs_trace.h | 5 ++++- 4 files changed, 16 insertions(+), 2 deletions(-) (limited to 'fs/xfs/xfs_trace.h') diff --git a/fs/xfs/libxfs/xfs_alloc.c b/fs/xfs/libxfs/xfs_alloc.c index 5993f87eee3e..22ac3f136f21 100644 --- a/fs/xfs/libxfs/xfs_alloc.c +++ b/fs/xfs/libxfs/xfs_alloc.c @@ -2702,6 +2702,13 @@ xfs_free_extent( ASSERT(len != 0); + trace_xfs_bmap_free_deferred(mp, agno, 0, agbno, len); + + if (XFS_TEST_ERROR(false, mp, + XFS_ERRTAG_FREE_EXTENT, + XFS_RANDOM_FREE_EXTENT)) + return -EIO; + error = xfs_free_extent_fix_freelist(tp, agno, &agbp); if (error) return error; diff --git a/fs/xfs/libxfs/xfs_bmap.c b/fs/xfs/libxfs/xfs_bmap.c index 540a6b7928af..8e14ff45c73a 100644 --- a/fs/xfs/libxfs/xfs_bmap.c +++ b/fs/xfs/libxfs/xfs_bmap.c @@ -596,6 +596,8 @@ xfs_bmap_add_free( new = kmem_zone_alloc(xfs_bmap_free_item_zone, KM_SLEEP); new->xefi_startblock = bno; new->xefi_blockcount = (xfs_extlen_t)len; + trace_xfs_bmap_free_defer(mp, XFS_FSB_TO_AGNO(mp, bno), 0, + XFS_FSB_TO_AGBNO(mp, bno), len); xfs_defer_add(dfops, XFS_DEFER_OPS_TYPE_FREE, &new->xefi_list); } diff --git a/fs/xfs/xfs_error.h b/fs/xfs/xfs_error.h index 2e4f67f68856..da6f951435c9 100644 --- a/fs/xfs/xfs_error.h +++ b/fs/xfs/xfs_error.h @@ -90,7 +90,8 @@ extern void xfs_verifier_error(struct xfs_buf *bp); #define XFS_ERRTAG_STRATCMPL_IOERR 19 #define XFS_ERRTAG_DIOWRITE_IOERR 20 #define XFS_ERRTAG_BMAPIFORMAT 21 -#define XFS_ERRTAG_MAX 22 +#define XFS_ERRTAG_FREE_EXTENT 22 +#define XFS_ERRTAG_MAX 23 /* * Random factors for above tags, 1 means always, 2 means 1/2 time, etc. @@ -117,6 +118,7 @@ extern void xfs_verifier_error(struct xfs_buf *bp); #define XFS_RANDOM_STRATCMPL_IOERR (XFS_RANDOM_DEFAULT/10) #define XFS_RANDOM_DIOWRITE_IOERR (XFS_RANDOM_DEFAULT/10) #define XFS_RANDOM_BMAPIFORMAT XFS_RANDOM_DEFAULT +#define XFS_RANDOM_FREE_EXTENT 1 #ifdef DEBUG extern int xfs_error_test_active; diff --git a/fs/xfs/xfs_trace.h b/fs/xfs/xfs_trace.h index a45b030d4592..939caf5f5a45 100644 --- a/fs/xfs/xfs_trace.h +++ b/fs/xfs/xfs_trace.h @@ -2417,9 +2417,12 @@ DEFINE_DEFER_PENDING_EVENT(xfs_defer_pending_cancel); DEFINE_DEFER_PENDING_EVENT(xfs_defer_pending_finish); DEFINE_DEFER_PENDING_EVENT(xfs_defer_pending_abort); -DEFINE_PHYS_EXTENT_DEFERRED_EVENT(xfs_defer_phys_extent); DEFINE_MAP_EXTENT_DEFERRED_EVENT(xfs_defer_map_extent); +#define DEFINE_BMAP_FREE_DEFERRED_EVENT DEFINE_PHYS_EXTENT_DEFERRED_EVENT +DEFINE_BMAP_FREE_DEFERRED_EVENT(xfs_bmap_free_defer); +DEFINE_BMAP_FREE_DEFERRED_EVENT(xfs_bmap_free_deferred); + #endif /* _TRACE_XFS_H */ #undef TRACE_INCLUDE_PATH -- cgit v1.2.3 From 673930c34a4500c616cf9b2bbe1ae131ead2e155 Mon Sep 17 00:00:00 2001 From: "Darrick J. Wong" Date: Wed, 3 Aug 2016 11:33:43 +1000 Subject: xfs: introduce rmap extent operation stubs Originally-From: Dave Chinner Add the stubs into the extent allocation and freeing paths that the rmap btree implementation will hook into. While doing this, add the trace points that will be used to track rmap btree extent manipulations. [darrick.wong@oracle.com: Extend the stubs to take full owner info.] Signed-off-by: Dave Chinner Signed-off-by: Darrick J. Wong Reviewed-by: Dave Chinner Signed-off-by: Dave Chinner --- fs/xfs/Makefile | 1 + fs/xfs/libxfs/xfs_alloc.c | 19 ++++++++-- fs/xfs/libxfs/xfs_rmap.c | 89 +++++++++++++++++++++++++++++++++++++++++++++++ fs/xfs/libxfs/xfs_rmap.h | 11 ++++++ fs/xfs/xfs_trace.h | 77 ++++++++++++++++++++++++++++++++++++++++ 5 files changed, 195 insertions(+), 2 deletions(-) create mode 100644 fs/xfs/libxfs/xfs_rmap.c (limited to 'fs/xfs/xfs_trace.h') diff --git a/fs/xfs/Makefile b/fs/xfs/Makefile index 01857b096cae..0498291829c6 100644 --- a/fs/xfs/Makefile +++ b/fs/xfs/Makefile @@ -52,6 +52,7 @@ xfs-y += $(addprefix libxfs/, \ xfs_inode_fork.o \ xfs_inode_buf.o \ xfs_log_rlimit.o \ + xfs_rmap.o \ xfs_sb.o \ xfs_symlink_remote.o \ xfs_trans_resv.o \ diff --git a/fs/xfs/libxfs/xfs_alloc.c b/fs/xfs/libxfs/xfs_alloc.c index 6335b8b85349..dba7ce4b4be8 100644 --- a/fs/xfs/libxfs/xfs_alloc.c +++ b/fs/xfs/libxfs/xfs_alloc.c @@ -27,6 +27,7 @@ #include "xfs_defer.h" #include "xfs_inode.h" #include "xfs_btree.h" +#include "xfs_rmap.h" #include "xfs_alloc_btree.h" #include "xfs_alloc.h" #include "xfs_extent_busy.h" @@ -36,7 +37,6 @@ #include "xfs_trans.h" #include "xfs_buf_item.h" #include "xfs_log.h" -#include "xfs_rmap.h" struct workqueue_struct *xfs_alloc_wq; @@ -649,6 +649,14 @@ xfs_alloc_ag_vextent( ASSERT(!args->wasfromfl || !args->isfl); ASSERT(args->agbno % args->alignment == 0); + /* if not file data, insert new block into the reverse map btree */ + if (args->oinfo.oi_owner != XFS_RMAP_OWN_UNKNOWN) { + error = xfs_rmap_alloc(args->tp, args->agbp, args->agno, + args->agbno, args->len, &args->oinfo); + if (error) + return error; + } + if (!args->wasfromfl) { error = xfs_alloc_update_counters(args->tp, args->pag, args->agbp, @@ -1615,12 +1623,19 @@ xfs_free_ag_extent( xfs_extlen_t nlen; /* new length of freespace */ xfs_perag_t *pag; /* per allocation group data */ + bno_cur = cnt_cur = NULL; mp = tp->t_mountp; + + if (oinfo->oi_owner != XFS_RMAP_OWN_UNKNOWN) { + error = xfs_rmap_free(tp, agbp, agno, bno, len, oinfo); + if (error) + goto error0; + } + /* * Allocate and initialize a cursor for the by-block btree. */ bno_cur = xfs_allocbt_init_cursor(mp, tp, agbp, agno, XFS_BTNUM_BNO); - cnt_cur = NULL; /* * Look for a neighboring block on the left (lower block numbers) * that is contiguous with this space. diff --git a/fs/xfs/libxfs/xfs_rmap.c b/fs/xfs/libxfs/xfs_rmap.c new file mode 100644 index 000000000000..b522bfc436a2 --- /dev/null +++ b/fs/xfs/libxfs/xfs_rmap.c @@ -0,0 +1,89 @@ +/* + * Copyright (c) 2014 Red Hat, Inc. + * All Rights Reserved. + * + * This program is free software; you can redistribute it and/or + * modify it under the terms of the GNU General Public License as + * published by the Free Software Foundation. + * + * This program is distributed in the hope that it would be useful, + * but WITHOUT ANY WARRANTY; without even the implied warranty of + * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the + * GNU General Public License for more details. + * + * You should have received a copy of the GNU General Public License + * along with this program; if not, write the Free Software Foundation, + * Inc., 51 Franklin St, Fifth Floor, Boston, MA 02110-1301 USA + */ +#include "xfs.h" +#include "xfs_fs.h" +#include "xfs_shared.h" +#include "xfs_format.h" +#include "xfs_log_format.h" +#include "xfs_trans_resv.h" +#include "xfs_bit.h" +#include "xfs_sb.h" +#include "xfs_mount.h" +#include "xfs_defer.h" +#include "xfs_da_format.h" +#include "xfs_da_btree.h" +#include "xfs_btree.h" +#include "xfs_trans.h" +#include "xfs_alloc.h" +#include "xfs_rmap.h" +#include "xfs_trans_space.h" +#include "xfs_trace.h" +#include "xfs_error.h" +#include "xfs_extent_busy.h" + +int +xfs_rmap_free( + struct xfs_trans *tp, + struct xfs_buf *agbp, + xfs_agnumber_t agno, + xfs_agblock_t bno, + xfs_extlen_t len, + struct xfs_owner_info *oinfo) +{ + struct xfs_mount *mp = tp->t_mountp; + int error = 0; + + if (!xfs_sb_version_hasrmapbt(&mp->m_sb)) + return 0; + + trace_xfs_rmap_unmap(mp, agno, bno, len, false, oinfo); + if (1) + goto out_error; + trace_xfs_rmap_unmap_done(mp, agno, bno, len, false, oinfo); + return 0; + +out_error: + trace_xfs_rmap_unmap_error(mp, agno, error, _RET_IP_); + return error; +} + +int +xfs_rmap_alloc( + struct xfs_trans *tp, + struct xfs_buf *agbp, + xfs_agnumber_t agno, + xfs_agblock_t bno, + xfs_extlen_t len, + struct xfs_owner_info *oinfo) +{ + struct xfs_mount *mp = tp->t_mountp; + int error = 0; + + if (!xfs_sb_version_hasrmapbt(&mp->m_sb)) + return 0; + + trace_xfs_rmap_map(mp, agno, bno, len, false, oinfo); + if (1) + goto out_error; + trace_xfs_rmap_map_done(mp, agno, bno, len, false, oinfo); + return 0; + +out_error: + trace_xfs_rmap_map_error(mp, agno, error, _RET_IP_); + return error; +} diff --git a/fs/xfs/libxfs/xfs_rmap.h b/fs/xfs/libxfs/xfs_rmap.h index b30e7ad6c7cc..dbf0301e9ae1 100644 --- a/fs/xfs/libxfs/xfs_rmap.h +++ b/fs/xfs/libxfs/xfs_rmap.h @@ -64,4 +64,15 @@ xfs_rmap_skip_owner_update( oi->oi_owner = XFS_RMAP_OWN_UNKNOWN; } +/* Reverse mapping functions. */ + +struct xfs_buf; + +int xfs_rmap_alloc(struct xfs_trans *tp, struct xfs_buf *agbp, + xfs_agnumber_t agno, xfs_agblock_t bno, xfs_extlen_t len, + struct xfs_owner_info *oinfo); +int xfs_rmap_free(struct xfs_trans *tp, struct xfs_buf *agbp, + xfs_agnumber_t agno, xfs_agblock_t bno, xfs_extlen_t len, + struct xfs_owner_info *oinfo); + #endif /* __XFS_RMAP_H__ */ diff --git a/fs/xfs/xfs_trace.h b/fs/xfs/xfs_trace.h index 939caf5f5a45..79e3812499ba 100644 --- a/fs/xfs/xfs_trace.h +++ b/fs/xfs/xfs_trace.h @@ -2423,6 +2423,83 @@ DEFINE_MAP_EXTENT_DEFERRED_EVENT(xfs_defer_map_extent); DEFINE_BMAP_FREE_DEFERRED_EVENT(xfs_bmap_free_defer); DEFINE_BMAP_FREE_DEFERRED_EVENT(xfs_bmap_free_deferred); +/* rmap tracepoints */ +DECLARE_EVENT_CLASS(xfs_rmap_class, + TP_PROTO(struct xfs_mount *mp, xfs_agnumber_t agno, + xfs_agblock_t agbno, xfs_extlen_t len, bool unwritten, + struct xfs_owner_info *oinfo), + TP_ARGS(mp, agno, agbno, len, unwritten, oinfo), + TP_STRUCT__entry( + __field(dev_t, dev) + __field(xfs_agnumber_t, agno) + __field(xfs_agblock_t, agbno) + __field(xfs_extlen_t, len) + __field(uint64_t, owner) + __field(uint64_t, offset) + __field(unsigned long, flags) + ), + TP_fast_assign( + __entry->dev = mp->m_super->s_dev; + __entry->agno = agno; + __entry->agbno = agbno; + __entry->len = len; + __entry->owner = oinfo->oi_owner; + __entry->offset = oinfo->oi_offset; + __entry->flags = oinfo->oi_flags; + ), + TP_printk("dev %d:%d agno %u agbno %u len %u owner %lld offset %llu flags 0x%lx", + MAJOR(__entry->dev), MINOR(__entry->dev), + __entry->agno, + __entry->agbno, + __entry->len, + __entry->owner, + __entry->offset, + __entry->flags) +); +#define DEFINE_RMAP_EVENT(name) \ +DEFINE_EVENT(xfs_rmap_class, name, \ + TP_PROTO(struct xfs_mount *mp, xfs_agnumber_t agno, \ + xfs_agblock_t agbno, xfs_extlen_t len, bool unwritten, \ + struct xfs_owner_info *oinfo), \ + TP_ARGS(mp, agno, agbno, len, unwritten, oinfo)) + +/* simple AG-based error/%ip tracepoint class */ +DECLARE_EVENT_CLASS(xfs_ag_error_class, + TP_PROTO(struct xfs_mount *mp, xfs_agnumber_t agno, int error, + unsigned long caller_ip), + TP_ARGS(mp, agno, error, caller_ip), + TP_STRUCT__entry( + __field(dev_t, dev) + __field(xfs_agnumber_t, agno) + __field(int, error) + __field(unsigned long, caller_ip) + ), + TP_fast_assign( + __entry->dev = mp->m_super->s_dev; + __entry->agno = agno; + __entry->error = error; + __entry->caller_ip = caller_ip; + ), + TP_printk("dev %d:%d agno %u error %d caller %ps", + MAJOR(__entry->dev), MINOR(__entry->dev), + __entry->agno, + __entry->error, + (char *)__entry->caller_ip) +); + +#define DEFINE_AG_ERROR_EVENT(name) \ +DEFINE_EVENT(xfs_ag_error_class, name, \ + TP_PROTO(struct xfs_mount *mp, xfs_agnumber_t agno, int error, \ + unsigned long caller_ip), \ + TP_ARGS(mp, agno, error, caller_ip)) + +DEFINE_RMAP_EVENT(xfs_rmap_unmap); +DEFINE_RMAP_EVENT(xfs_rmap_unmap_done); +DEFINE_AG_ERROR_EVENT(xfs_rmap_unmap_error); +DEFINE_RMAP_EVENT(xfs_rmap_map); +DEFINE_RMAP_EVENT(xfs_rmap_map_done); +DEFINE_AG_ERROR_EVENT(xfs_rmap_map_error); + #endif /* _TRACE_XFS_H */ #undef TRACE_INCLUDE_PATH -- cgit v1.2.3 From 035e00acb5c719bd003639b90716a7e94e023b73 Mon Sep 17 00:00:00 2001 From: "Darrick J. Wong" Date: Wed, 3 Aug 2016 11:36:07 +1000 Subject: xfs: define the on-disk rmap btree format Originally-From: Dave Chinner Now we have all the surrounding call infrastructure in place, we can start filling out the rmap btree implementation. Start with the on-disk btree format; add everything needed to read, write and manipulate rmap btree blocks. This prepares the way for adding the btree operations implementation. [darrick: record owner and offset info in rmap btree] [darrick: fork, bmbt and unwritten state in rmap btree] [darrick: flags are a separate field in xfs_rmap_irec] [darrick: calculate maxlevels separately] [darrick: move the 'unwritten' bit into unused parts of rm_offset] Signed-off-by: Dave Chinner Signed-off-by: Darrick J. Wong Reviewed-by: Dave Chinner Reviewed-by: Brian Foster Signed-off-by: Dave Chinner --- fs/xfs/Makefile | 1 + fs/xfs/libxfs/xfs_btree.c | 3 + fs/xfs/libxfs/xfs_btree.h | 22 +++-- fs/xfs/libxfs/xfs_format.h | 73 ++++++++++++++++ fs/xfs/libxfs/xfs_rmap.h | 67 +++++++++++++++ fs/xfs/libxfs/xfs_rmap_btree.c | 184 +++++++++++++++++++++++++++++++++++++++++ fs/xfs/libxfs/xfs_rmap_btree.h | 55 ++++++++++++ fs/xfs/libxfs/xfs_sb.c | 6 ++ fs/xfs/libxfs/xfs_shared.h | 2 + fs/xfs/xfs_mount.c | 2 + fs/xfs/xfs_mount.h | 3 + fs/xfs/xfs_ondisk.h | 3 + fs/xfs/xfs_trace.h | 2 + 13 files changed, 415 insertions(+), 8 deletions(-) create mode 100644 fs/xfs/libxfs/xfs_rmap_btree.c create mode 100644 fs/xfs/libxfs/xfs_rmap_btree.h (limited to 'fs/xfs/xfs_trace.h') diff --git a/fs/xfs/Makefile b/fs/xfs/Makefile index 0498291829c6..b76e937f0729 100644 --- a/fs/xfs/Makefile +++ b/fs/xfs/Makefile @@ -53,6 +53,7 @@ xfs-y += $(addprefix libxfs/, \ xfs_inode_buf.o \ xfs_log_rlimit.o \ xfs_rmap.o \ + xfs_rmap_btree.o \ xfs_sb.o \ xfs_symlink_remote.o \ xfs_trans_resv.o \ diff --git a/fs/xfs/libxfs/xfs_btree.c b/fs/xfs/libxfs/xfs_btree.c index 4066b01a1807..fe5f27e4cdc5 100644 --- a/fs/xfs/libxfs/xfs_btree.c +++ b/fs/xfs/libxfs/xfs_btree.c @@ -1213,6 +1213,9 @@ xfs_btree_set_refs( case XFS_BTNUM_BMAP: xfs_buf_set_ref(bp, XFS_BMAP_BTREE_REF); break; + case XFS_BTNUM_RMAP: + xfs_buf_set_ref(bp, XFS_RMAP_BTREE_REF); + break; default: ASSERT(0); } diff --git a/fs/xfs/libxfs/xfs_btree.h b/fs/xfs/libxfs/xfs_btree.h index a480947f094b..573d3a0c5797 100644 --- a/fs/xfs/libxfs/xfs_btree.h +++ b/fs/xfs/libxfs/xfs_btree.h @@ -38,10 +38,11 @@ union xfs_btree_ptr { }; union xfs_btree_key { - xfs_bmbt_key_t bmbt; - xfs_bmdr_key_t bmbr; /* bmbt root block */ - xfs_alloc_key_t alloc; - xfs_inobt_key_t inobt; + struct xfs_bmbt_key bmbt; + xfs_bmdr_key_t bmbr; /* bmbt root block */ + xfs_alloc_key_t alloc; + struct xfs_inobt_key inobt; + struct xfs_rmap_key rmap; }; /* @@ -56,13 +57,18 @@ union xfs_btree_bigkey { xfs_bmdr_key_t bmbr; /* bmbt root block */ xfs_alloc_key_t alloc; struct xfs_inobt_key inobt; + struct { + struct xfs_rmap_key rmap; + struct xfs_rmap_key rmap_hi; + }; }; union xfs_btree_rec { - xfs_bmbt_rec_t bmbt; - xfs_bmdr_rec_t bmbr; /* bmbt root block */ - xfs_alloc_rec_t alloc; - xfs_inobt_rec_t inobt; + struct xfs_bmbt_rec bmbt; + xfs_bmdr_rec_t bmbr; /* bmbt root block */ + struct xfs_alloc_rec alloc; + struct xfs_inobt_rec inobt; + struct xfs_rmap_rec rmap; }; /* diff --git a/fs/xfs/libxfs/xfs_format.h b/fs/xfs/libxfs/xfs_format.h index eecfedf19be5..f6a0641e64c8 100644 --- a/fs/xfs/libxfs/xfs_format.h +++ b/fs/xfs/libxfs/xfs_format.h @@ -1347,6 +1347,79 @@ struct xfs_owner_info { #define XFS_RMAP_OWN_INODES (-7ULL) /* Inode chunk */ #define XFS_RMAP_OWN_MIN (-8ULL) /* guard */ +#define XFS_RMAP_NON_INODE_OWNER(owner) (!!((owner) & (1ULL << 63))) + +/* + * Data record structure + */ +struct xfs_rmap_rec { + __be32 rm_startblock; /* extent start block */ + __be32 rm_blockcount; /* extent length */ + __be64 rm_owner; /* extent owner */ + __be64 rm_offset; /* offset within the owner */ +}; + +/* + * rmap btree record + * rm_offset:63 is the attribute fork flag + * rm_offset:62 is the bmbt block flag + * rm_offset:61 is the unwritten extent flag (same as l0:63 in bmbt) + * rm_offset:54-60 aren't used and should be zero + * rm_offset:0-53 is the block offset within the inode + */ +#define XFS_RMAP_OFF_ATTR_FORK ((__uint64_t)1ULL << 63) +#define XFS_RMAP_OFF_BMBT_BLOCK ((__uint64_t)1ULL << 62) +#define XFS_RMAP_OFF_UNWRITTEN ((__uint64_t)1ULL << 61) + +#define XFS_RMAP_LEN_MAX ((__uint32_t)~0U) +#define XFS_RMAP_OFF_FLAGS (XFS_RMAP_OFF_ATTR_FORK | \ + XFS_RMAP_OFF_BMBT_BLOCK | \ + XFS_RMAP_OFF_UNWRITTEN) +#define XFS_RMAP_OFF_MASK ((__uint64_t)0x3FFFFFFFFFFFFFULL) + +#define XFS_RMAP_OFF(off) ((off) & XFS_RMAP_OFF_MASK) + +#define XFS_RMAP_IS_BMBT_BLOCK(off) (!!((off) & XFS_RMAP_OFF_BMBT_BLOCK)) +#define XFS_RMAP_IS_ATTR_FORK(off) (!!((off) & XFS_RMAP_OFF_ATTR_FORK)) +#define XFS_RMAP_IS_UNWRITTEN(len) (!!((off) & XFS_RMAP_OFF_UNWRITTEN)) + +#define RMAPBT_STARTBLOCK_BITLEN 32 +#define RMAPBT_BLOCKCOUNT_BITLEN 32 +#define RMAPBT_OWNER_BITLEN 64 +#define RMAPBT_ATTRFLAG_BITLEN 1 +#define RMAPBT_BMBTFLAG_BITLEN 1 +#define RMAPBT_EXNTFLAG_BITLEN 1 +#define RMAPBT_UNUSED_OFFSET_BITLEN 7 +#define RMAPBT_OFFSET_BITLEN 54 + +#define XFS_RMAP_ATTR_FORK (1 << 0) +#define XFS_RMAP_BMBT_BLOCK (1 << 1) +#define XFS_RMAP_UNWRITTEN (1 << 2) +#define XFS_RMAP_KEY_FLAGS (XFS_RMAP_ATTR_FORK | \ + XFS_RMAP_BMBT_BLOCK) +#define XFS_RMAP_REC_FLAGS (XFS_RMAP_UNWRITTEN) +struct xfs_rmap_irec { + xfs_agblock_t rm_startblock; /* extent start block */ + xfs_extlen_t rm_blockcount; /* extent length */ + __uint64_t rm_owner; /* extent owner */ + __uint64_t rm_offset; /* offset within the owner */ + unsigned int rm_flags; /* state flags */ +}; + +/* + * Key structure + * + * We don't use the length for lookups + */ +struct xfs_rmap_key { + __be32 rm_startblock; /* extent start block */ + __be64 rm_owner; /* extent owner */ + __be64 rm_offset; /* offset within the owner */ +} __attribute__((packed)); + +/* btree pointer type */ +typedef __be32 xfs_rmap_ptr_t; + #define XFS_RMAP_BLOCK(mp) \ (xfs_sb_version_hasfinobt(&((mp)->m_sb)) ? \ XFS_FIBT_BLOCK(mp) + 1 : \ diff --git a/fs/xfs/libxfs/xfs_rmap.h b/fs/xfs/libxfs/xfs_rmap.h index dbf0301e9ae1..e7a670459fea 100644 --- a/fs/xfs/libxfs/xfs_rmap.h +++ b/fs/xfs/libxfs/xfs_rmap.h @@ -68,6 +68,73 @@ xfs_rmap_skip_owner_update( struct xfs_buf; +static inline __u64 +xfs_rmap_irec_offset_pack( + const struct xfs_rmap_irec *irec) +{ + __u64 x; + + x = XFS_RMAP_OFF(irec->rm_offset); + if (irec->rm_flags & XFS_RMAP_ATTR_FORK) + x |= XFS_RMAP_OFF_ATTR_FORK; + if (irec->rm_flags & XFS_RMAP_BMBT_BLOCK) + x |= XFS_RMAP_OFF_BMBT_BLOCK; + if (irec->rm_flags & XFS_RMAP_UNWRITTEN) + x |= XFS_RMAP_OFF_UNWRITTEN; + return x; +} + +static inline int +xfs_rmap_irec_offset_unpack( + __u64 offset, + struct xfs_rmap_irec *irec) +{ + if (offset & ~(XFS_RMAP_OFF_MASK | XFS_RMAP_OFF_FLAGS)) + return -EFSCORRUPTED; + irec->rm_offset = XFS_RMAP_OFF(offset); + if (offset & XFS_RMAP_OFF_ATTR_FORK) + irec->rm_flags |= XFS_RMAP_ATTR_FORK; + if (offset & XFS_RMAP_OFF_BMBT_BLOCK) + irec->rm_flags |= XFS_RMAP_BMBT_BLOCK; + if (offset & XFS_RMAP_OFF_UNWRITTEN) + irec->rm_flags |= XFS_RMAP_UNWRITTEN; + return 0; +} + +static inline void +xfs_owner_info_unpack( + struct xfs_owner_info *oinfo, + uint64_t *owner, + uint64_t *offset, + unsigned int *flags) +{ + unsigned int r = 0; + + *owner = oinfo->oi_owner; + *offset = oinfo->oi_offset; + if (oinfo->oi_flags & XFS_OWNER_INFO_ATTR_FORK) + r |= XFS_RMAP_ATTR_FORK; + if (oinfo->oi_flags & XFS_OWNER_INFO_BMBT_BLOCK) + r |= XFS_RMAP_BMBT_BLOCK; + *flags = r; +} + +static inline void +xfs_owner_info_pack( + struct xfs_owner_info *oinfo, + uint64_t owner, + uint64_t offset, + unsigned int flags) +{ + oinfo->oi_owner = owner; + oinfo->oi_offset = XFS_RMAP_OFF(offset); + oinfo->oi_flags = 0; + if (flags & XFS_RMAP_ATTR_FORK) + oinfo->oi_flags |= XFS_OWNER_INFO_ATTR_FORK; + if (flags & XFS_RMAP_BMBT_BLOCK) + oinfo->oi_flags |= XFS_OWNER_INFO_BMBT_BLOCK; +} + int xfs_rmap_alloc(struct xfs_trans *tp, struct xfs_buf *agbp, xfs_agnumber_t agno, xfs_agblock_t bno, xfs_extlen_t len, struct xfs_owner_info *oinfo); diff --git a/fs/xfs/libxfs/xfs_rmap_btree.c b/fs/xfs/libxfs/xfs_rmap_btree.c new file mode 100644 index 000000000000..a9ddc191aa2d --- /dev/null +++ b/fs/xfs/libxfs/xfs_rmap_btree.c @@ -0,0 +1,184 @@ +/* + * Copyright (c) 2014 Red Hat, Inc. + * All Rights Reserved. + * + * This program is free software; you can redistribute it and/or + * modify it under the terms of the GNU General Public License as + * published by the Free Software Foundation. + * + * This program is distributed in the hope that it would be useful, + * but WITHOUT ANY WARRANTY; without even the implied warranty of + * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the + * GNU General Public License for more details. + * + * You should have received a copy of the GNU General Public License + * along with this program; if not, write the Free Software Foundation, + * Inc., 51 Franklin St, Fifth Floor, Boston, MA 02110-1301 USA + */ +#include "xfs.h" +#include "xfs_fs.h" +#include "xfs_shared.h" +#include "xfs_format.h" +#include "xfs_log_format.h" +#include "xfs_trans_resv.h" +#include "xfs_bit.h" +#include "xfs_sb.h" +#include "xfs_mount.h" +#include "xfs_defer.h" +#include "xfs_inode.h" +#include "xfs_trans.h" +#include "xfs_alloc.h" +#include "xfs_btree.h" +#include "xfs_rmap_btree.h" +#include "xfs_trace.h" +#include "xfs_cksum.h" +#include "xfs_error.h" +#include "xfs_extent_busy.h" + +static struct xfs_btree_cur * +xfs_rmapbt_dup_cursor( + struct xfs_btree_cur *cur) +{ + return xfs_rmapbt_init_cursor(cur->bc_mp, cur->bc_tp, + cur->bc_private.a.agbp, cur->bc_private.a.agno); +} + +static bool +xfs_rmapbt_verify( + struct xfs_buf *bp) +{ + struct xfs_mount *mp = bp->b_target->bt_mount; + struct xfs_btree_block *block = XFS_BUF_TO_BLOCK(bp); + struct xfs_perag *pag = bp->b_pag; + unsigned int level; + + /* + * magic number and level verification + * + * During growfs operations, we can't verify the exact level or owner as + * the perag is not fully initialised and hence not attached to the + * buffer. In this case, check against the maximum tree depth. + * + * Similarly, during log recovery we will have a perag structure + * attached, but the agf information will not yet have been initialised + * from the on disk AGF. Again, we can only check against maximum limits + * in this case. + */ + if (block->bb_magic != cpu_to_be32(XFS_RMAP_CRC_MAGIC)) + return false; + + if (!xfs_sb_version_hasrmapbt(&mp->m_sb)) + return false; + if (!xfs_btree_sblock_v5hdr_verify(bp)) + return false; + + level = be16_to_cpu(block->bb_level); + if (pag && pag->pagf_init) { + if (level >= pag->pagf_levels[XFS_BTNUM_RMAPi]) + return false; + } else if (level >= mp->m_rmap_maxlevels) + return false; + + return xfs_btree_sblock_verify(bp, mp->m_rmap_mxr[level != 0]); +} + +static void +xfs_rmapbt_read_verify( + struct xfs_buf *bp) +{ + if (!xfs_btree_sblock_verify_crc(bp)) + xfs_buf_ioerror(bp, -EFSBADCRC); + else if (!xfs_rmapbt_verify(bp)) + xfs_buf_ioerror(bp, -EFSCORRUPTED); + + if (bp->b_error) { + trace_xfs_btree_corrupt(bp, _RET_IP_); + xfs_verifier_error(bp); + } +} + +static void +xfs_rmapbt_write_verify( + struct xfs_buf *bp) +{ + if (!xfs_rmapbt_verify(bp)) { + trace_xfs_btree_corrupt(bp, _RET_IP_); + xfs_buf_ioerror(bp, -EFSCORRUPTED); + xfs_verifier_error(bp); + return; + } + xfs_btree_sblock_calc_crc(bp); + +} + +const struct xfs_buf_ops xfs_rmapbt_buf_ops = { + .name = "xfs_rmapbt", + .verify_read = xfs_rmapbt_read_verify, + .verify_write = xfs_rmapbt_write_verify, +}; + +static const struct xfs_btree_ops xfs_rmapbt_ops = { + .rec_len = sizeof(struct xfs_rmap_rec), + .key_len = 2 * sizeof(struct xfs_rmap_key), + + .dup_cursor = xfs_rmapbt_dup_cursor, + .buf_ops = &xfs_rmapbt_buf_ops, + + .get_leaf_keys = xfs_btree_get_leaf_keys_overlapped, + .get_node_keys = xfs_btree_get_node_keys_overlapped, + .update_keys = xfs_btree_update_keys_overlapped, +}; + +/* + * Allocate a new allocation btree cursor. + */ +struct xfs_btree_cur * +xfs_rmapbt_init_cursor( + struct xfs_mount *mp, + struct xfs_trans *tp, + struct xfs_buf *agbp, + xfs_agnumber_t agno) +{ + struct xfs_agf *agf = XFS_BUF_TO_AGF(agbp); + struct xfs_btree_cur *cur; + + cur = kmem_zone_zalloc(xfs_btree_cur_zone, KM_NOFS); + cur->bc_tp = tp; + cur->bc_mp = mp; + cur->bc_btnum = XFS_BTNUM_RMAP; + cur->bc_flags = XFS_BTREE_CRC_BLOCKS; + cur->bc_blocklog = mp->m_sb.sb_blocklog; + cur->bc_ops = &xfs_rmapbt_ops; + cur->bc_nlevels = be32_to_cpu(agf->agf_levels[XFS_BTNUM_RMAP]); + + cur->bc_private.a.agbp = agbp; + cur->bc_private.a.agno = agno; + + return cur; +} + +/* + * Calculate number of records in an rmap btree block. + */ +int +xfs_rmapbt_maxrecs( + struct xfs_mount *mp, + int blocklen, + int leaf) +{ + blocklen -= XFS_RMAP_BLOCK_LEN; + + if (leaf) + return blocklen / sizeof(struct xfs_rmap_rec); + return blocklen / + (sizeof(struct xfs_rmap_key) + sizeof(xfs_rmap_ptr_t)); +} + +/* Compute the maximum height of an rmap btree. */ +void +xfs_rmapbt_compute_maxlevels( + struct xfs_mount *mp) +{ + mp->m_rmap_maxlevels = xfs_btree_compute_maxlevels(mp, + mp->m_rmap_mnr, mp->m_sb.sb_agblocks); +} diff --git a/fs/xfs/libxfs/xfs_rmap_btree.h b/fs/xfs/libxfs/xfs_rmap_btree.h new file mode 100644 index 000000000000..a3a6b7d476c7 --- /dev/null +++ b/fs/xfs/libxfs/xfs_rmap_btree.h @@ -0,0 +1,55 @@ +/* + * Copyright (c) 2014 Red Hat, Inc. + * All Rights Reserved. + * + * This program is free software; you can redistribute it and/or + * modify it under the terms of the GNU General Public License as + * published by the Free Software Foundation. + * + * This program is distributed in the hope that it would be useful, + * but WITHOUT ANY WARRANTY; without even the implied warranty of + * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the + * GNU General Public License for more details. + * + * You should have received a copy of the GNU General Public License + * along with this program; if not, write the Free Software Foundation, + * Inc., 51 Franklin St, Fifth Floor, Boston, MA 02110-1301 USA + */ +#ifndef __XFS_RMAP_BTREE_H__ +#define __XFS_RMAP_BTREE_H__ + +struct xfs_buf; +struct xfs_btree_cur; +struct xfs_mount; + +/* rmaps only exist on crc enabled filesystems */ +#define XFS_RMAP_BLOCK_LEN XFS_BTREE_SBLOCK_CRC_LEN + +/* + * Record, key, and pointer address macros for btree blocks. + * + * (note that some of these may appear unused, but they are used in userspace) + */ +#define XFS_RMAP_REC_ADDR(block, index) \ + ((struct xfs_rmap_rec *) \ + ((char *)(block) + XFS_RMAP_BLOCK_LEN + \ + (((index) - 1) * sizeof(struct xfs_rmap_rec)))) + +#define XFS_RMAP_KEY_ADDR(block, index) \ + ((struct xfs_rmap_key *) \ + ((char *)(block) + XFS_RMAP_BLOCK_LEN + \ + ((index) - 1) * 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) + \ + ((index) - 1) * sizeof(xfs_rmap_ptr_t))) + +struct xfs_btree_cur *xfs_rmapbt_init_cursor(struct xfs_mount *mp, + struct xfs_trans *tp, struct xfs_buf *bp, + xfs_agnumber_t agno); +int xfs_rmapbt_maxrecs(struct xfs_mount *mp, int blocklen, int leaf); +extern void xfs_rmapbt_compute_maxlevels(struct xfs_mount *mp); + +#endif /* __XFS_RMAP_BTREE_H__ */ diff --git a/fs/xfs/libxfs/xfs_sb.c b/fs/xfs/libxfs/xfs_sb.c index 2194e5d4eea8..fb33e70e5c9a 100644 --- a/fs/xfs/libxfs/xfs_sb.c +++ b/fs/xfs/libxfs/xfs_sb.c @@ -37,6 +37,7 @@ #include "xfs_alloc_btree.h" #include "xfs_ialloc_btree.h" #include "xfs_log.h" +#include "xfs_rmap_btree.h" /* * Physical superblock buffer manipulations. Shared with libxfs in userspace. @@ -730,6 +731,11 @@ xfs_sb_mount_common( mp->m_bmap_dmnr[0] = mp->m_bmap_dmxr[0] / 2; mp->m_bmap_dmnr[1] = mp->m_bmap_dmxr[1] / 2; + mp->m_rmap_mxr[0] = xfs_rmapbt_maxrecs(mp, sbp->sb_blocksize, 1); + mp->m_rmap_mxr[1] = xfs_rmapbt_maxrecs(mp, sbp->sb_blocksize, 0); + mp->m_rmap_mnr[0] = mp->m_rmap_mxr[0] / 2; + mp->m_rmap_mnr[1] = mp->m_rmap_mxr[1] / 2; + mp->m_bsize = XFS_FSB_TO_BB(mp, 1); mp->m_ialloc_inos = (int)MAX((__uint16_t)XFS_INODES_PER_CHUNK, sbp->sb_inopblock); diff --git a/fs/xfs/libxfs/xfs_shared.h b/fs/xfs/libxfs/xfs_shared.h index 16002b5ec4eb..0c5b30bd884c 100644 --- a/fs/xfs/libxfs/xfs_shared.h +++ b/fs/xfs/libxfs/xfs_shared.h @@ -38,6 +38,7 @@ extern const struct xfs_buf_ops xfs_agi_buf_ops; extern const struct xfs_buf_ops xfs_agf_buf_ops; extern const struct xfs_buf_ops xfs_agfl_buf_ops; extern const struct xfs_buf_ops xfs_allocbt_buf_ops; +extern const struct xfs_buf_ops xfs_rmapbt_buf_ops; extern const struct xfs_buf_ops xfs_attr3_leaf_buf_ops; extern const struct xfs_buf_ops xfs_attr3_rmt_buf_ops; extern const struct xfs_buf_ops xfs_bmbt_buf_ops; @@ -116,6 +117,7 @@ int xfs_log_calc_minimum_size(struct xfs_mount *); #define XFS_INO_BTREE_REF 3 #define XFS_ALLOC_BTREE_REF 2 #define XFS_BMAP_BTREE_REF 2 +#define XFS_RMAP_BTREE_REF 2 #define XFS_DIR_BTREE_REF 2 #define XFS_INO_REF 2 #define XFS_ATTR_BTREE_REF 1 diff --git a/fs/xfs/xfs_mount.c b/fs/xfs/xfs_mount.c index 24ae96b4078f..0041866d51ca 100644 --- a/fs/xfs/xfs_mount.c +++ b/fs/xfs/xfs_mount.c @@ -42,6 +42,7 @@ #include "xfs_trace.h" #include "xfs_icache.h" #include "xfs_sysfs.h" +#include "xfs_rmap_btree.h" static DEFINE_MUTEX(xfs_uuid_table_mutex); @@ -682,6 +683,7 @@ xfs_mountfs( xfs_bmap_compute_maxlevels(mp, XFS_DATA_FORK); xfs_bmap_compute_maxlevels(mp, XFS_ATTR_FORK); xfs_ialloc_compute_maxlevels(mp); + xfs_rmapbt_compute_maxlevels(mp); xfs_set_maxicount(mp); diff --git a/fs/xfs/xfs_mount.h b/fs/xfs/xfs_mount.h index 0537b1f28f90..0ed0f29ddaf5 100644 --- a/fs/xfs/xfs_mount.h +++ b/fs/xfs/xfs_mount.h @@ -116,9 +116,12 @@ typedef struct xfs_mount { uint m_bmap_dmnr[2]; /* min bmap btree records */ uint m_inobt_mxr[2]; /* max inobt btree records */ uint m_inobt_mnr[2]; /* min inobt btree records */ + uint m_rmap_mxr[2]; /* max rmap btree records */ + uint m_rmap_mnr[2]; /* min rmap btree records */ uint m_ag_maxlevels; /* XFS_AG_MAXLEVELS */ uint m_bm_maxlevels[2]; /* XFS_BM_MAXLEVELS */ uint m_in_maxlevels; /* max inobt btree levels. */ + uint m_rmap_maxlevels; /* max rmap btree levels */ xfs_extlen_t m_ag_prealloc_blocks; /* reserved ag blocks */ struct radix_tree_root m_perag_tree; /* per-ag accounting info */ spinlock_t m_perag_lock; /* lock for m_perag_tree */ diff --git a/fs/xfs/xfs_ondisk.h b/fs/xfs/xfs_ondisk.h index 0cc8d8f74356..69e2986a3776 100644 --- a/fs/xfs/xfs_ondisk.h +++ b/fs/xfs/xfs_ondisk.h @@ -49,11 +49,14 @@ xfs_check_ondisk_structs(void) XFS_CHECK_STRUCT_SIZE(struct xfs_dsymlink_hdr, 56); XFS_CHECK_STRUCT_SIZE(struct xfs_inobt_key, 4); XFS_CHECK_STRUCT_SIZE(struct xfs_inobt_rec, 16); + XFS_CHECK_STRUCT_SIZE(struct xfs_rmap_key, 20); + XFS_CHECK_STRUCT_SIZE(struct xfs_rmap_rec, 24); XFS_CHECK_STRUCT_SIZE(struct xfs_timestamp, 8); XFS_CHECK_STRUCT_SIZE(xfs_alloc_key_t, 8); XFS_CHECK_STRUCT_SIZE(xfs_alloc_ptr_t, 4); XFS_CHECK_STRUCT_SIZE(xfs_alloc_rec_t, 8); XFS_CHECK_STRUCT_SIZE(xfs_inobt_ptr_t, 4); + XFS_CHECK_STRUCT_SIZE(xfs_rmap_ptr_t, 4); /* dir/attr trees */ XFS_CHECK_STRUCT_SIZE(struct xfs_attr3_leaf_hdr, 80); diff --git a/fs/xfs/xfs_trace.h b/fs/xfs/xfs_trace.h index 79e3812499ba..4c3418b1a244 100644 --- a/fs/xfs/xfs_trace.h +++ b/fs/xfs/xfs_trace.h @@ -2446,6 +2446,8 @@ DECLARE_EVENT_CLASS(xfs_rmap_class, __entry->owner = oinfo->oi_owner; __entry->offset = oinfo->oi_offset; __entry->flags = oinfo->oi_flags; + if (unwritten) + __entry->flags |= XFS_RMAP_UNWRITTEN; ), TP_printk("dev %d:%d agno %u agbno %u len %u owner %lld offset %llu flags 0x%lx", MAJOR(__entry->dev), MINOR(__entry->dev), -- cgit v1.2.3 From 4b8ed67794fe57b23801c65f4ea5b0f0b1f0dbab Mon Sep 17 00:00:00 2001 From: "Darrick J. Wong" Date: Wed, 3 Aug 2016 11:39:05 +1000 Subject: xfs: add rmap btree operations Originally-From: Dave Chinner Implement the generic btree operations needed to manipulate rmap btree blocks. This is very similar to the per-ag freespace btree implementation, and uses the AGFL for allocation and freeing of blocks. Adapt the rmap btree to store owner offsets within each rmap record, and to handle the primary key being redefined as the tuple [agblk, owner, offset]. The expansion of the primary key is crucial to allowing multiple owners per extent. [darrick: adapt the btree ops to deal with offsets] [darrick: remove init_rec_from_key] [darrick: move unwritten bit to rm_offset] Signed-off-by: Dave Chinner Signed-off-by: Darrick J. Wong Reviewed-by: Dave Chinner Signed-off-by: Dave Chinner --- fs/xfs/libxfs/xfs_btree.h | 1 + fs/xfs/libxfs/xfs_rmap.c | 96 +++++++++++++++ fs/xfs/libxfs/xfs_rmap.h | 9 ++ fs/xfs/libxfs/xfs_rmap_btree.c | 267 +++++++++++++++++++++++++++++++++++++++++ fs/xfs/xfs_trace.h | 3 + 5 files changed, 376 insertions(+) (limited to 'fs/xfs/xfs_trace.h') diff --git a/fs/xfs/libxfs/xfs_btree.h b/fs/xfs/libxfs/xfs_btree.h index 573d3a0c5797..9b6d6286466e 100644 --- a/fs/xfs/libxfs/xfs_btree.h +++ b/fs/xfs/libxfs/xfs_btree.h @@ -241,6 +241,7 @@ union xfs_btree_irec { struct xfs_alloc_rec_incore a; struct xfs_bmbt_irec b; struct xfs_inobt_rec_incore i; + struct xfs_rmap_irec r; }; /* diff --git a/fs/xfs/libxfs/xfs_rmap.c b/fs/xfs/libxfs/xfs_rmap.c index b522bfc436a2..ce29d6b7cd58 100644 --- a/fs/xfs/libxfs/xfs_rmap.c +++ b/fs/xfs/libxfs/xfs_rmap.c @@ -36,6 +36,102 @@ #include "xfs_error.h" #include "xfs_extent_busy.h" +/* + * Lookup the first record less than or equal to [bno, len, owner, offset] + * in the btree given by cur. + */ +int +xfs_rmap_lookup_le( + struct xfs_btree_cur *cur, + xfs_agblock_t bno, + xfs_extlen_t len, + uint64_t owner, + uint64_t offset, + unsigned int flags, + int *stat) +{ + cur->bc_rec.r.rm_startblock = bno; + cur->bc_rec.r.rm_blockcount = len; + cur->bc_rec.r.rm_owner = owner; + cur->bc_rec.r.rm_offset = offset; + cur->bc_rec.r.rm_flags = flags; + return xfs_btree_lookup(cur, XFS_LOOKUP_LE, stat); +} + +/* + * Lookup the record exactly matching [bno, len, owner, offset] + * in the btree given by cur. + */ +int +xfs_rmap_lookup_eq( + struct xfs_btree_cur *cur, + xfs_agblock_t bno, + xfs_extlen_t len, + uint64_t owner, + uint64_t offset, + unsigned int flags, + int *stat) +{ + cur->bc_rec.r.rm_startblock = bno; + cur->bc_rec.r.rm_blockcount = len; + cur->bc_rec.r.rm_owner = owner; + cur->bc_rec.r.rm_offset = offset; + cur->bc_rec.r.rm_flags = flags; + return xfs_btree_lookup(cur, XFS_LOOKUP_EQ, stat); +} + +/* + * Update the record referred to by cur to the value given + * by [bno, len, owner, offset]. + * This either works (return 0) or gets an EFSCORRUPTED error. + */ +STATIC int +xfs_rmap_update( + struct xfs_btree_cur *cur, + struct xfs_rmap_irec *irec) +{ + union xfs_btree_rec rec; + + rec.rmap.rm_startblock = cpu_to_be32(irec->rm_startblock); + rec.rmap.rm_blockcount = cpu_to_be32(irec->rm_blockcount); + rec.rmap.rm_owner = cpu_to_be64(irec->rm_owner); + rec.rmap.rm_offset = cpu_to_be64( + xfs_rmap_irec_offset_pack(irec)); + return xfs_btree_update(cur, &rec); +} + +static int +xfs_rmap_btrec_to_irec( + union xfs_btree_rec *rec, + struct xfs_rmap_irec *irec) +{ + irec->rm_flags = 0; + irec->rm_startblock = be32_to_cpu(rec->rmap.rm_startblock); + irec->rm_blockcount = be32_to_cpu(rec->rmap.rm_blockcount); + irec->rm_owner = be64_to_cpu(rec->rmap.rm_owner); + return xfs_rmap_irec_offset_unpack(be64_to_cpu(rec->rmap.rm_offset), + irec); +} + +/* + * Get the data from the pointed-to record. + */ +int +xfs_rmap_get_rec( + struct xfs_btree_cur *cur, + struct xfs_rmap_irec *irec, + int *stat) +{ + union xfs_btree_rec *rec; + int error; + + error = xfs_btree_get_rec(cur, &rec, stat); + if (error || !*stat) + return error; + + return xfs_rmap_btrec_to_irec(rec, irec); +} + int xfs_rmap_free( struct xfs_trans *tp, diff --git a/fs/xfs/libxfs/xfs_rmap.h b/fs/xfs/libxfs/xfs_rmap.h index e7a670459fea..aa39a2a825e7 100644 --- a/fs/xfs/libxfs/xfs_rmap.h +++ b/fs/xfs/libxfs/xfs_rmap.h @@ -142,4 +142,13 @@ int xfs_rmap_free(struct xfs_trans *tp, struct xfs_buf *agbp, xfs_agnumber_t agno, xfs_agblock_t bno, xfs_extlen_t len, struct xfs_owner_info *oinfo); +int xfs_rmap_lookup_le(struct xfs_btree_cur *cur, xfs_agblock_t bno, + xfs_extlen_t len, uint64_t owner, uint64_t offset, + unsigned int flags, int *stat); +int xfs_rmap_lookup_eq(struct xfs_btree_cur *cur, xfs_agblock_t bno, + xfs_extlen_t len, uint64_t owner, uint64_t offset, + unsigned int flags, int *stat); +int xfs_rmap_get_rec(struct xfs_btree_cur *cur, struct xfs_rmap_irec *irec, + int *stat); + #endif /* __XFS_RMAP_H__ */ diff --git a/fs/xfs/libxfs/xfs_rmap_btree.c b/fs/xfs/libxfs/xfs_rmap_btree.c index a9ddc191aa2d..95cb964606d1 100644 --- a/fs/xfs/libxfs/xfs_rmap_btree.c +++ b/fs/xfs/libxfs/xfs_rmap_btree.c @@ -29,12 +29,38 @@ #include "xfs_trans.h" #include "xfs_alloc.h" #include "xfs_btree.h" +#include "xfs_rmap.h" #include "xfs_rmap_btree.h" #include "xfs_trace.h" #include "xfs_cksum.h" #include "xfs_error.h" #include "xfs_extent_busy.h" +/* + * Reverse map btree. + * + * This is a per-ag tree used to track the owner(s) of a given extent. With + * reflink it is possible for there to be multiple owners, which is a departure + * from classic XFS. Owner records for data extents are inserted when the + * extent is mapped and removed when an extent is unmapped. Owner records for + * all other block types (i.e. metadata) are inserted when an extent is + * allocated and removed when an extent is freed. There can only be one owner + * of a metadata extent, usually an inode or some other metadata structure like + * an AG btree. + * + * The rmap btree is part of the free space management, so blocks for the tree + * are sourced from the agfl. Hence we need transaction reservation support for + * this tree so that the freelist is always large enough. This also impacts on + * the minimum space we need to leave free in the AG. + * + * The tree is ordered by [ag block, owner, offset]. This is a large key size, + * but it is the only way to enforce unique keys when a block can be owned by + * multiple files at any offset. There's no need to order/search by extent + * size for online updating/management of the tree. It is intended that most + * reverse lookups will be to find the owner(s) of a particular block, or to + * try to recover tree and file data from corrupt primary metadata. + */ + static struct xfs_btree_cur * xfs_rmapbt_dup_cursor( struct xfs_btree_cur *cur) @@ -43,6 +69,172 @@ xfs_rmapbt_dup_cursor( cur->bc_private.a.agbp, cur->bc_private.a.agno); } +STATIC void +xfs_rmapbt_set_root( + struct xfs_btree_cur *cur, + union xfs_btree_ptr *ptr, + int inc) +{ + struct xfs_buf *agbp = cur->bc_private.a.agbp; + struct xfs_agf *agf = XFS_BUF_TO_AGF(agbp); + xfs_agnumber_t seqno = be32_to_cpu(agf->agf_seqno); + int btnum = cur->bc_btnum; + struct xfs_perag *pag = xfs_perag_get(cur->bc_mp, seqno); + + ASSERT(ptr->s != 0); + + agf->agf_roots[btnum] = ptr->s; + be32_add_cpu(&agf->agf_levels[btnum], inc); + pag->pagf_levels[btnum] += inc; + xfs_perag_put(pag); + + xfs_alloc_log_agf(cur->bc_tp, agbp, XFS_AGF_ROOTS | XFS_AGF_LEVELS); +} + +STATIC int +xfs_rmapbt_alloc_block( + struct xfs_btree_cur *cur, + union xfs_btree_ptr *start, + union xfs_btree_ptr *new, + int *stat) +{ + int error; + xfs_agblock_t bno; + + XFS_BTREE_TRACE_CURSOR(cur, XBT_ENTRY); + + /* Allocate the new block from the freelist. If we can't, give up. */ + error = xfs_alloc_get_freelist(cur->bc_tp, cur->bc_private.a.agbp, + &bno, 1); + if (error) { + XFS_BTREE_TRACE_CURSOR(cur, XBT_ERROR); + return error; + } + + trace_xfs_rmapbt_alloc_block(cur->bc_mp, cur->bc_private.a.agno, + bno, 1); + if (bno == NULLAGBLOCK) { + XFS_BTREE_TRACE_CURSOR(cur, XBT_EXIT); + *stat = 0; + return 0; + } + + xfs_extent_busy_reuse(cur->bc_mp, cur->bc_private.a.agno, bno, 1, + false); + + xfs_trans_agbtree_delta(cur->bc_tp, 1); + new->s = cpu_to_be32(bno); + + XFS_BTREE_TRACE_CURSOR(cur, XBT_EXIT); + *stat = 1; + return 0; +} + +STATIC int +xfs_rmapbt_free_block( + struct xfs_btree_cur *cur, + struct xfs_buf *bp) +{ + struct xfs_buf *agbp = cur->bc_private.a.agbp; + struct xfs_agf *agf = XFS_BUF_TO_AGF(agbp); + xfs_agblock_t bno; + int error; + + bno = xfs_daddr_to_agbno(cur->bc_mp, XFS_BUF_ADDR(bp)); + trace_xfs_rmapbt_free_block(cur->bc_mp, cur->bc_private.a.agno, + bno, 1); + error = xfs_alloc_put_freelist(cur->bc_tp, agbp, NULL, bno, 1); + if (error) + return error; + + xfs_extent_busy_insert(cur->bc_tp, be32_to_cpu(agf->agf_seqno), bno, 1, + XFS_EXTENT_BUSY_SKIP_DISCARD); + xfs_trans_agbtree_delta(cur->bc_tp, -1); + + return 0; +} + +STATIC int +xfs_rmapbt_get_minrecs( + struct xfs_btree_cur *cur, + int level) +{ + return cur->bc_mp->m_rmap_mnr[level != 0]; +} + +STATIC int +xfs_rmapbt_get_maxrecs( + struct xfs_btree_cur *cur, + int level) +{ + return cur->bc_mp->m_rmap_mxr[level != 0]; +} + +STATIC void +xfs_rmapbt_init_key_from_rec( + union xfs_btree_key *key, + union xfs_btree_rec *rec) +{ + key->rmap.rm_startblock = rec->rmap.rm_startblock; + key->rmap.rm_owner = rec->rmap.rm_owner; + key->rmap.rm_offset = rec->rmap.rm_offset; +} + +STATIC void +xfs_rmapbt_init_rec_from_cur( + struct xfs_btree_cur *cur, + union xfs_btree_rec *rec) +{ + rec->rmap.rm_startblock = cpu_to_be32(cur->bc_rec.r.rm_startblock); + rec->rmap.rm_blockcount = cpu_to_be32(cur->bc_rec.r.rm_blockcount); + rec->rmap.rm_owner = cpu_to_be64(cur->bc_rec.r.rm_owner); + rec->rmap.rm_offset = cpu_to_be64( + xfs_rmap_irec_offset_pack(&cur->bc_rec.r)); +} + +STATIC void +xfs_rmapbt_init_ptr_from_cur( + struct xfs_btree_cur *cur, + union xfs_btree_ptr *ptr) +{ + struct xfs_agf *agf = XFS_BUF_TO_AGF(cur->bc_private.a.agbp); + + ASSERT(cur->bc_private.a.agno == be32_to_cpu(agf->agf_seqno)); + ASSERT(agf->agf_roots[cur->bc_btnum] != 0); + + ptr->s = agf->agf_roots[cur->bc_btnum]; +} + +STATIC __int64_t +xfs_rmapbt_key_diff( + struct xfs_btree_cur *cur, + union xfs_btree_key *key) +{ + struct xfs_rmap_irec *rec = &cur->bc_rec.r; + struct xfs_rmap_key *kp = &key->rmap; + __u64 x, y; + __int64_t d; + + d = (__int64_t)be32_to_cpu(kp->rm_startblock) - rec->rm_startblock; + if (d) + return d; + + 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 bool xfs_rmapbt_verify( struct xfs_buf *bp) @@ -117,12 +309,87 @@ const struct xfs_buf_ops xfs_rmapbt_buf_ops = { .verify_write = xfs_rmapbt_write_verify, }; +#if defined(DEBUG) || defined(XFS_WARN) +STATIC int +xfs_rmapbt_keys_inorder( + struct xfs_btree_cur *cur, + union xfs_btree_key *k1, + union xfs_btree_key *k2) +{ + __uint32_t x; + __uint32_t y; + __uint64_t a; + __uint64_t b; + + x = be32_to_cpu(k1->rmap.rm_startblock); + y = be32_to_cpu(k2->rmap.rm_startblock); + if (x < y) + return 1; + else if (x > y) + return 0; + a = be64_to_cpu(k1->rmap.rm_owner); + b = be64_to_cpu(k2->rmap.rm_owner); + if (a < b) + return 1; + else if (a > b) + return 0; + a = XFS_RMAP_OFF(be64_to_cpu(k1->rmap.rm_offset)); + b = XFS_RMAP_OFF(be64_to_cpu(k2->rmap.rm_offset)); + if (a <= b) + return 1; + return 0; +} + +STATIC int +xfs_rmapbt_recs_inorder( + struct xfs_btree_cur *cur, + union xfs_btree_rec *r1, + union xfs_btree_rec *r2) +{ + __uint32_t x; + __uint32_t y; + __uint64_t a; + __uint64_t b; + + x = be32_to_cpu(r1->rmap.rm_startblock); + y = be32_to_cpu(r2->rmap.rm_startblock); + if (x < y) + return 1; + else if (x > y) + return 0; + a = be64_to_cpu(r1->rmap.rm_owner); + b = be64_to_cpu(r2->rmap.rm_owner); + if (a < b) + return 1; + else if (a > b) + return 0; + a = XFS_RMAP_OFF(be64_to_cpu(r1->rmap.rm_offset)); + b = XFS_RMAP_OFF(be64_to_cpu(r2->rmap.rm_offset)); + if (a <= b) + return 1; + return 0; +} +#endif /* DEBUG */ + static const struct xfs_btree_ops xfs_rmapbt_ops = { .rec_len = sizeof(struct xfs_rmap_rec), .key_len = 2 * sizeof(struct xfs_rmap_key), .dup_cursor = xfs_rmapbt_dup_cursor, + .set_root = xfs_rmapbt_set_root, + .alloc_block = xfs_rmapbt_alloc_block, + .free_block = xfs_rmapbt_free_block, + .get_minrecs = xfs_rmapbt_get_minrecs, + .get_maxrecs = xfs_rmapbt_get_maxrecs, + .init_key_from_rec = xfs_rmapbt_init_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, +#if defined(DEBUG) || defined(XFS_WARN) + .keys_inorder = xfs_rmapbt_keys_inorder, + .recs_inorder = xfs_rmapbt_recs_inorder, +#endif .get_leaf_keys = xfs_btree_get_leaf_keys_overlapped, .get_node_keys = xfs_btree_get_node_keys_overlapped, diff --git a/fs/xfs/xfs_trace.h b/fs/xfs/xfs_trace.h index 4c3418b1a244..e69912acb23f 100644 --- a/fs/xfs/xfs_trace.h +++ b/fs/xfs/xfs_trace.h @@ -2502,6 +2502,9 @@ DEFINE_RMAP_EVENT(xfs_rmap_map); DEFINE_RMAP_EVENT(xfs_rmap_map_done); DEFINE_AG_ERROR_EVENT(xfs_rmap_map_error); +DEFINE_BUSY_EVENT(xfs_rmapbt_alloc_block); +DEFINE_BUSY_EVENT(xfs_rmapbt_free_block); + #endif /* _TRACE_XFS_H */ #undef TRACE_INCLUDE_PATH -- cgit v1.2.3 From aa966d84aa487c4cb7f6fade1a35ca961652a395 Mon Sep 17 00:00:00 2001 From: "Darrick J. Wong" Date: Wed, 3 Aug 2016 11:43:24 +1000 Subject: xfs: add tracepoints for the rmap functions Signed-off-by: Darrick J. Wong Reviewed-by: Brian Foster Signed-off-by: Dave Chinner --- fs/xfs/xfs_trace.h | 51 +++++++++++++++++++++++++++++++++++++++++++++++++-- 1 file changed, 49 insertions(+), 2 deletions(-) (limited to 'fs/xfs/xfs_trace.h') diff --git a/fs/xfs/xfs_trace.h b/fs/xfs/xfs_trace.h index e69912acb23f..7498c7780d99 100644 --- a/fs/xfs/xfs_trace.h +++ b/fs/xfs/xfs_trace.h @@ -2417,8 +2417,6 @@ DEFINE_DEFER_PENDING_EVENT(xfs_defer_pending_cancel); DEFINE_DEFER_PENDING_EVENT(xfs_defer_pending_finish); DEFINE_DEFER_PENDING_EVENT(xfs_defer_pending_abort); -DEFINE_MAP_EXTENT_DEFERRED_EVENT(xfs_defer_map_extent); - #define DEFINE_BMAP_FREE_DEFERRED_EVENT DEFINE_PHYS_EXTENT_DEFERRED_EVENT DEFINE_BMAP_FREE_DEFERRED_EVENT(xfs_bmap_free_defer); DEFINE_BMAP_FREE_DEFERRED_EVENT(xfs_bmap_free_deferred); @@ -2502,8 +2500,57 @@ DEFINE_RMAP_EVENT(xfs_rmap_map); DEFINE_RMAP_EVENT(xfs_rmap_map_done); DEFINE_AG_ERROR_EVENT(xfs_rmap_map_error); +DECLARE_EVENT_CLASS(xfs_rmapbt_class, + TP_PROTO(struct xfs_mount *mp, xfs_agnumber_t agno, + xfs_agblock_t agbno, xfs_extlen_t len, + uint64_t owner, uint64_t offset, unsigned int flags), + TP_ARGS(mp, agno, agbno, len, owner, offset, flags), + TP_STRUCT__entry( + __field(dev_t, dev) + __field(xfs_agnumber_t, agno) + __field(xfs_agblock_t, agbno) + __field(xfs_extlen_t, len) + __field(uint64_t, owner) + __field(uint64_t, offset) + __field(unsigned int, flags) + ), + TP_fast_assign( + __entry->dev = mp->m_super->s_dev; + __entry->agno = agno; + __entry->agbno = agbno; + __entry->len = len; + __entry->owner = owner; + __entry->offset = offset; + __entry->flags = flags; + ), + TP_printk("dev %d:%d agno %u agbno %u len %u owner %lld offset %llu flags 0x%x", + MAJOR(__entry->dev), MINOR(__entry->dev), + __entry->agno, + __entry->agbno, + __entry->len, + __entry->owner, + __entry->offset, + __entry->flags) +); +#define DEFINE_RMAPBT_EVENT(name) \ +DEFINE_EVENT(xfs_rmapbt_class, name, \ + TP_PROTO(struct xfs_mount *mp, xfs_agnumber_t agno, \ + xfs_agblock_t agbno, xfs_extlen_t len, \ + uint64_t owner, uint64_t offset, unsigned int flags), \ + TP_ARGS(mp, agno, agbno, len, owner, offset, flags)) + +#define DEFINE_RMAP_DEFERRED_EVENT DEFINE_MAP_EXTENT_DEFERRED_EVENT +DEFINE_RMAP_DEFERRED_EVENT(xfs_rmap_defer); +DEFINE_RMAP_DEFERRED_EVENT(xfs_rmap_deferred); + DEFINE_BUSY_EVENT(xfs_rmapbt_alloc_block); DEFINE_BUSY_EVENT(xfs_rmapbt_free_block); +DEFINE_RMAPBT_EVENT(xfs_rmap_update); +DEFINE_RMAPBT_EVENT(xfs_rmap_insert); +DEFINE_RMAPBT_EVENT(xfs_rmap_delete); +DEFINE_AG_ERROR_EVENT(xfs_rmap_insert_error); +DEFINE_AG_ERROR_EVENT(xfs_rmap_delete_error); +DEFINE_AG_ERROR_EVENT(xfs_rmap_update_error); #endif /* _TRACE_XFS_H */ -- cgit v1.2.3 From 0a1b0b3855cf74bb11243076b00178a0f1a0320e Mon Sep 17 00:00:00 2001 From: "Darrick J. Wong" Date: Wed, 3 Aug 2016 11:44:21 +1000 Subject: xfs: add an extent to the rmap btree Originally-From: Dave Chinner Now all the btree, free space and transaction infrastructure is in place, we can finally add the code to insert reverse mappings to the rmap btree. Freeing will be done in a separate patch, so just the addition operation can be focussed on here. [darrick: handle owner offsets when adding rmaps] [dchinner: remove remaining debug printk statements] [darrick: move unwritten bit to rm_offset] Signed-off-by: Dave Chinner Signed-off-by: Darrick J. Wong Reviewed-by: Dave Chinner Signed-off-by: Dave Chinner --- fs/xfs/libxfs/xfs_rmap.c | 226 +++++++++++++++++++++++++++++++++++++++++++++-- fs/xfs/xfs_trace.h | 2 + 2 files changed, 223 insertions(+), 5 deletions(-) (limited to 'fs/xfs/xfs_trace.h') diff --git a/fs/xfs/libxfs/xfs_rmap.c b/fs/xfs/libxfs/xfs_rmap.c index 6638bc725b23..1c0e2a8943a4 100644 --- a/fs/xfs/libxfs/xfs_rmap.c +++ b/fs/xfs/libxfs/xfs_rmap.c @@ -31,6 +31,7 @@ #include "xfs_trans.h" #include "xfs_alloc.h" #include "xfs_rmap.h" +#include "xfs_rmap_btree.h" #include "xfs_trans_space.h" #include "xfs_trace.h" #include "xfs_error.h" @@ -158,6 +159,218 @@ out_error: return error; } +/* + * A mergeable rmap must have the same owner and the same values for + * the unwritten, attr_fork, and bmbt flags. The startblock and + * offset are checked separately. + */ +static bool +xfs_rmap_is_mergeable( + struct xfs_rmap_irec *irec, + uint64_t owner, + unsigned int flags) +{ + if (irec->rm_owner == XFS_RMAP_OWN_NULL) + return false; + if (irec->rm_owner != owner) + return false; + if ((flags & XFS_RMAP_UNWRITTEN) ^ + (irec->rm_flags & XFS_RMAP_UNWRITTEN)) + return false; + if ((flags & XFS_RMAP_ATTR_FORK) ^ + (irec->rm_flags & XFS_RMAP_ATTR_FORK)) + return false; + if ((flags & XFS_RMAP_BMBT_BLOCK) ^ + (irec->rm_flags & XFS_RMAP_BMBT_BLOCK)) + return false; + return true; +} + +/* + * When we allocate a new block, the first thing we do is add a reference to + * the extent in the rmap btree. This takes the form of a [agbno, length, + * owner, offset] record. Flags are encoded in the high bits of the offset + * field. + */ +STATIC int +xfs_rmap_map( + struct xfs_btree_cur *cur, + xfs_agblock_t bno, + xfs_extlen_t len, + bool unwritten, + struct xfs_owner_info *oinfo) +{ + struct xfs_mount *mp = cur->bc_mp; + struct xfs_rmap_irec ltrec; + struct xfs_rmap_irec gtrec; + int have_gt; + int have_lt; + int error = 0; + int i; + uint64_t owner; + uint64_t offset; + unsigned int flags = 0; + bool ignore_off; + + xfs_owner_info_unpack(oinfo, &owner, &offset, &flags); + ASSERT(owner != 0); + ignore_off = XFS_RMAP_NON_INODE_OWNER(owner) || + (flags & XFS_RMAP_BMBT_BLOCK); + if (unwritten) + flags |= XFS_RMAP_UNWRITTEN; + trace_xfs_rmap_map(mp, cur->bc_private.a.agno, bno, len, + unwritten, oinfo); + + /* + * For the initial lookup, look for an exact match or the left-adjacent + * record for our insertion point. This will also give us the record for + * start block contiguity tests. + */ + error = xfs_rmap_lookup_le(cur, bno, len, owner, offset, flags, + &have_lt); + if (error) + goto out_error; + XFS_WANT_CORRUPTED_GOTO(mp, have_lt == 1, out_error); + + error = xfs_rmap_get_rec(cur, <rec, &have_lt); + if (error) + goto out_error; + XFS_WANT_CORRUPTED_GOTO(mp, have_lt == 1, out_error); + trace_xfs_rmap_lookup_le_range_result(cur->bc_mp, + cur->bc_private.a.agno, ltrec.rm_startblock, + ltrec.rm_blockcount, ltrec.rm_owner, + ltrec.rm_offset, ltrec.rm_flags); + + if (!xfs_rmap_is_mergeable(<rec, owner, flags)) + have_lt = 0; + + XFS_WANT_CORRUPTED_GOTO(mp, + have_lt == 0 || + ltrec.rm_startblock + ltrec.rm_blockcount <= bno, out_error); + + /* + * Increment the cursor to see if we have a right-adjacent record to our + * insertion point. This will give us the record for end block + * contiguity tests. + */ + error = xfs_btree_increment(cur, 0, &have_gt); + if (error) + goto out_error; + if (have_gt) { + error = xfs_rmap_get_rec(cur, >rec, &have_gt); + if (error) + goto out_error; + XFS_WANT_CORRUPTED_GOTO(mp, have_gt == 1, out_error); + XFS_WANT_CORRUPTED_GOTO(mp, bno + len <= gtrec.rm_startblock, + out_error); + trace_xfs_rmap_find_right_neighbor_result(cur->bc_mp, + cur->bc_private.a.agno, gtrec.rm_startblock, + gtrec.rm_blockcount, gtrec.rm_owner, + gtrec.rm_offset, gtrec.rm_flags); + if (!xfs_rmap_is_mergeable(>rec, owner, flags)) + have_gt = 0; + } + + /* + * Note: cursor currently points one record to the right of ltrec, even + * if there is no record in the tree to the right. + */ + if (have_lt && + ltrec.rm_startblock + ltrec.rm_blockcount == bno && + (ignore_off || ltrec.rm_offset + ltrec.rm_blockcount == offset)) { + /* + * left edge contiguous, merge into left record. + * + * ltbno ltlen + * orig: |ooooooooo| + * adding: |aaaaaaaaa| + * result: |rrrrrrrrrrrrrrrrrrr| + * bno len + */ + ltrec.rm_blockcount += len; + if (have_gt && + bno + len == gtrec.rm_startblock && + (ignore_off || offset + len == gtrec.rm_offset) && + (unsigned long)ltrec.rm_blockcount + len + + gtrec.rm_blockcount <= XFS_RMAP_LEN_MAX) { + /* + * right edge also contiguous, delete right record + * and merge into left record. + * + * ltbno ltlen gtbno gtlen + * orig: |ooooooooo| |ooooooooo| + * adding: |aaaaaaaaa| + * result: |rrrrrrrrrrrrrrrrrrrrrrrrrrrrr| + */ + ltrec.rm_blockcount += gtrec.rm_blockcount; + trace_xfs_rmap_delete(mp, cur->bc_private.a.agno, + gtrec.rm_startblock, + gtrec.rm_blockcount, + gtrec.rm_owner, + gtrec.rm_offset, + gtrec.rm_flags); + error = xfs_btree_delete(cur, &i); + if (error) + goto out_error; + XFS_WANT_CORRUPTED_GOTO(mp, i == 1, out_error); + } + + /* point the cursor back to the left record and update */ + error = xfs_btree_decrement(cur, 0, &have_gt); + if (error) + goto out_error; + error = xfs_rmap_update(cur, <rec); + if (error) + goto out_error; + } else if (have_gt && + bno + len == gtrec.rm_startblock && + (ignore_off || offset + len == gtrec.rm_offset)) { + /* + * right edge contiguous, merge into right record. + * + * gtbno gtlen + * Orig: |ooooooooo| + * adding: |aaaaaaaaa| + * Result: |rrrrrrrrrrrrrrrrrrr| + * bno len + */ + gtrec.rm_startblock = bno; + gtrec.rm_blockcount += len; + if (!ignore_off) + gtrec.rm_offset = offset; + error = xfs_rmap_update(cur, >rec); + if (error) + goto out_error; + } else { + /* + * no contiguous edge with identical owner, insert + * new record at current cursor position. + */ + cur->bc_rec.r.rm_startblock = bno; + cur->bc_rec.r.rm_blockcount = len; + cur->bc_rec.r.rm_owner = owner; + cur->bc_rec.r.rm_offset = offset; + cur->bc_rec.r.rm_flags = flags; + trace_xfs_rmap_insert(mp, cur->bc_private.a.agno, bno, len, + owner, offset, flags); + error = xfs_btree_insert(cur, &i); + if (error) + goto out_error; + XFS_WANT_CORRUPTED_GOTO(mp, i == 1, out_error); + } + + trace_xfs_rmap_map_done(mp, cur->bc_private.a.agno, bno, len, + unwritten, oinfo); +out_error: + if (error) + trace_xfs_rmap_map_error(mp, cur->bc_private.a.agno, + error, _RET_IP_); + return error; +} + +/* + * Add a reference to an extent in the rmap btree. + */ int xfs_rmap_alloc( struct xfs_trans *tp, @@ -168,19 +381,22 @@ xfs_rmap_alloc( struct xfs_owner_info *oinfo) { struct xfs_mount *mp = tp->t_mountp; - int error = 0; + struct xfs_btree_cur *cur; + int error; if (!xfs_sb_version_hasrmapbt(&mp->m_sb)) return 0; - trace_xfs_rmap_map(mp, agno, bno, len, false, oinfo); - if (1) + cur = xfs_rmapbt_init_cursor(mp, tp, agbp, agno); + error = xfs_rmap_map(cur, bno, len, false, oinfo); + if (error) goto out_error; - trace_xfs_rmap_map_done(mp, agno, bno, len, false, oinfo); + + xfs_btree_del_cursor(cur, XFS_BTREE_NOERROR); return 0; out_error: - trace_xfs_rmap_map_error(mp, agno, error, _RET_IP_); + xfs_btree_del_cursor(cur, XFS_BTREE_ERROR); return error; } diff --git a/fs/xfs/xfs_trace.h b/fs/xfs/xfs_trace.h index 7498c7780d99..e099eda75b68 100644 --- a/fs/xfs/xfs_trace.h +++ b/fs/xfs/xfs_trace.h @@ -2551,6 +2551,8 @@ DEFINE_RMAPBT_EVENT(xfs_rmap_delete); DEFINE_AG_ERROR_EVENT(xfs_rmap_insert_error); DEFINE_AG_ERROR_EVENT(xfs_rmap_delete_error); DEFINE_AG_ERROR_EVENT(xfs_rmap_update_error); +DEFINE_RMAPBT_EVENT(xfs_rmap_lookup_le_range_result); +DEFINE_RMAPBT_EVENT(xfs_rmap_find_right_neighbor_result); #endif /* _TRACE_XFS_H */ -- cgit v1.2.3 From fb7d9267692a5cdc01648bf4c8fdca51054bc0f2 Mon Sep 17 00:00:00 2001 From: "Darrick J. Wong" Date: Wed, 3 Aug 2016 12:03:19 +1000 Subject: xfs: convert unwritten status of reverse mappings Provide a function to convert an unwritten rmap extent to a real one and vice versa. [ dchinner: Note that this algorithm and code was derived from the existing bmapbt unwritten extent conversion code in xfs_bmap_add_extent_unwritten_real(). ] Signed-off-by: Darrick J. Wong Reviewed-by: Dave Chinner Signed-off-by: Dave Chinner --- fs/xfs/libxfs/xfs_rmap.c | 441 +++++++++++++++++++++++++++++++++++++++++++++++ fs/xfs/xfs_trace.h | 5 + 2 files changed, 446 insertions(+) (limited to 'fs/xfs/xfs_trace.h') diff --git a/fs/xfs/libxfs/xfs_rmap.c b/fs/xfs/libxfs/xfs_rmap.c index 1e48a0b62ba6..743927238bdc 100644 --- a/fs/xfs/libxfs/xfs_rmap.c +++ b/fs/xfs/libxfs/xfs_rmap.c @@ -610,6 +610,447 @@ out_error: return error; } +#define RMAP_LEFT_CONTIG (1 << 0) +#define RMAP_RIGHT_CONTIG (1 << 1) +#define RMAP_LEFT_FILLING (1 << 2) +#define RMAP_RIGHT_FILLING (1 << 3) +#define RMAP_LEFT_VALID (1 << 6) +#define RMAP_RIGHT_VALID (1 << 7) + +#define LEFT r[0] +#define RIGHT r[1] +#define PREV r[2] +#define NEW r[3] + +/* + * Convert an unwritten extent to a real extent or vice versa. + * Does not handle overlapping extents. + */ +STATIC int +xfs_rmap_convert( + struct xfs_btree_cur *cur, + xfs_agblock_t bno, + xfs_extlen_t len, + bool unwritten, + struct xfs_owner_info *oinfo) +{ + struct xfs_mount *mp = cur->bc_mp; + struct xfs_rmap_irec r[4]; /* neighbor extent entries */ + /* left is 0, right is 1, prev is 2 */ + /* new is 3 */ + uint64_t owner; + uint64_t offset; + uint64_t new_endoff; + unsigned int oldext; + unsigned int newext; + unsigned int flags = 0; + int i; + int state = 0; + int error; + + xfs_owner_info_unpack(oinfo, &owner, &offset, &flags); + ASSERT(!(XFS_RMAP_NON_INODE_OWNER(owner) || + (flags & (XFS_RMAP_ATTR_FORK | XFS_RMAP_BMBT_BLOCK)))); + oldext = unwritten ? XFS_RMAP_UNWRITTEN : 0; + new_endoff = offset + len; + trace_xfs_rmap_convert(mp, cur->bc_private.a.agno, bno, len, + unwritten, oinfo); + + /* + * For the initial lookup, look for an exact match or the left-adjacent + * record for our insertion point. This will also give us the record for + * start block contiguity tests. + */ + error = xfs_rmap_lookup_le(cur, bno, len, owner, offset, oldext, &i); + if (error) + goto done; + XFS_WANT_CORRUPTED_GOTO(mp, i == 1, done); + + error = xfs_rmap_get_rec(cur, &PREV, &i); + if (error) + goto done; + XFS_WANT_CORRUPTED_GOTO(mp, i == 1, done); + trace_xfs_rmap_lookup_le_range_result(cur->bc_mp, + cur->bc_private.a.agno, PREV.rm_startblock, + PREV.rm_blockcount, PREV.rm_owner, + PREV.rm_offset, PREV.rm_flags); + + ASSERT(PREV.rm_offset <= offset); + ASSERT(PREV.rm_offset + PREV.rm_blockcount >= new_endoff); + ASSERT((PREV.rm_flags & XFS_RMAP_UNWRITTEN) == oldext); + newext = ~oldext & XFS_RMAP_UNWRITTEN; + + /* + * Set flags determining what part of the previous oldext allocation + * extent is being replaced by a newext allocation. + */ + if (PREV.rm_offset == offset) + state |= RMAP_LEFT_FILLING; + if (PREV.rm_offset + PREV.rm_blockcount == new_endoff) + state |= RMAP_RIGHT_FILLING; + + /* + * Decrement the cursor to see if we have a left-adjacent record to our + * insertion point. This will give us the record for end block + * contiguity tests. + */ + error = xfs_btree_decrement(cur, 0, &i); + if (error) + goto done; + if (i) { + state |= RMAP_LEFT_VALID; + error = xfs_rmap_get_rec(cur, &LEFT, &i); + if (error) + goto done; + XFS_WANT_CORRUPTED_GOTO(mp, i == 1, done); + XFS_WANT_CORRUPTED_GOTO(mp, + LEFT.rm_startblock + LEFT.rm_blockcount <= bno, + done); + trace_xfs_rmap_find_left_neighbor_result(cur->bc_mp, + cur->bc_private.a.agno, LEFT.rm_startblock, + LEFT.rm_blockcount, LEFT.rm_owner, + LEFT.rm_offset, LEFT.rm_flags); + if (LEFT.rm_startblock + LEFT.rm_blockcount == bno && + LEFT.rm_offset + LEFT.rm_blockcount == offset && + xfs_rmap_is_mergeable(&LEFT, owner, newext)) + state |= RMAP_LEFT_CONTIG; + } + + /* + * Increment the cursor to see if we have a right-adjacent record to our + * insertion point. This will give us the record for end block + * contiguity tests. + */ + error = xfs_btree_increment(cur, 0, &i); + if (error) + goto done; + XFS_WANT_CORRUPTED_GOTO(mp, i == 1, done); + error = xfs_btree_increment(cur, 0, &i); + if (error) + goto done; + if (i) { + state |= RMAP_RIGHT_VALID; + error = xfs_rmap_get_rec(cur, &RIGHT, &i); + if (error) + goto done; + XFS_WANT_CORRUPTED_GOTO(mp, i == 1, done); + XFS_WANT_CORRUPTED_GOTO(mp, bno + len <= RIGHT.rm_startblock, + done); + trace_xfs_rmap_find_right_neighbor_result(cur->bc_mp, + cur->bc_private.a.agno, RIGHT.rm_startblock, + RIGHT.rm_blockcount, RIGHT.rm_owner, + RIGHT.rm_offset, RIGHT.rm_flags); + if (bno + len == RIGHT.rm_startblock && + offset + len == RIGHT.rm_offset && + xfs_rmap_is_mergeable(&RIGHT, owner, newext)) + state |= RMAP_RIGHT_CONTIG; + } + + /* check that left + prev + right is not too long */ + if ((state & (RMAP_LEFT_FILLING | RMAP_LEFT_CONTIG | + RMAP_RIGHT_FILLING | RMAP_RIGHT_CONTIG)) == + (RMAP_LEFT_FILLING | RMAP_LEFT_CONTIG | + RMAP_RIGHT_FILLING | RMAP_RIGHT_CONTIG) && + (unsigned long)LEFT.rm_blockcount + len + + RIGHT.rm_blockcount > XFS_RMAP_LEN_MAX) + state &= ~RMAP_RIGHT_CONTIG; + + trace_xfs_rmap_convert_state(mp, cur->bc_private.a.agno, state, + _RET_IP_); + + /* reset the cursor back to PREV */ + error = xfs_rmap_lookup_le(cur, bno, len, owner, offset, oldext, &i); + if (error) + goto done; + XFS_WANT_CORRUPTED_GOTO(mp, i == 1, done); + + /* + * Switch out based on the FILLING and CONTIG state bits. + */ + switch (state & (RMAP_LEFT_FILLING | RMAP_LEFT_CONTIG | + RMAP_RIGHT_FILLING | RMAP_RIGHT_CONTIG)) { + case RMAP_LEFT_FILLING | RMAP_LEFT_CONTIG | + RMAP_RIGHT_FILLING | RMAP_RIGHT_CONTIG: + /* + * Setting all of a previous oldext extent to newext. + * The left and right neighbors are both contiguous with new. + */ + error = xfs_btree_increment(cur, 0, &i); + if (error) + goto done; + XFS_WANT_CORRUPTED_GOTO(mp, i == 1, done); + trace_xfs_rmap_delete(mp, cur->bc_private.a.agno, + RIGHT.rm_startblock, RIGHT.rm_blockcount, + RIGHT.rm_owner, RIGHT.rm_offset, + RIGHT.rm_flags); + error = xfs_btree_delete(cur, &i); + if (error) + goto done; + XFS_WANT_CORRUPTED_GOTO(mp, i == 1, done); + error = xfs_btree_decrement(cur, 0, &i); + if (error) + goto done; + XFS_WANT_CORRUPTED_GOTO(mp, i == 1, done); + trace_xfs_rmap_delete(mp, cur->bc_private.a.agno, + PREV.rm_startblock, PREV.rm_blockcount, + PREV.rm_owner, PREV.rm_offset, + PREV.rm_flags); + error = xfs_btree_delete(cur, &i); + if (error) + goto done; + XFS_WANT_CORRUPTED_GOTO(mp, i == 1, done); + error = xfs_btree_decrement(cur, 0, &i); + if (error) + goto done; + XFS_WANT_CORRUPTED_GOTO(mp, i == 1, done); + NEW = LEFT; + NEW.rm_blockcount += PREV.rm_blockcount + RIGHT.rm_blockcount; + error = xfs_rmap_update(cur, &NEW); + if (error) + goto done; + break; + + case RMAP_LEFT_FILLING | RMAP_RIGHT_FILLING | RMAP_LEFT_CONTIG: + /* + * Setting all of a previous oldext extent to newext. + * The left neighbor is contiguous, the right is not. + */ + trace_xfs_rmap_delete(mp, cur->bc_private.a.agno, + PREV.rm_startblock, PREV.rm_blockcount, + PREV.rm_owner, PREV.rm_offset, + PREV.rm_flags); + error = xfs_btree_delete(cur, &i); + if (error) + goto done; + XFS_WANT_CORRUPTED_GOTO(mp, i == 1, done); + error = xfs_btree_decrement(cur, 0, &i); + if (error) + goto done; + XFS_WANT_CORRUPTED_GOTO(mp, i == 1, done); + NEW = LEFT; + NEW.rm_blockcount += PREV.rm_blockcount; + error = xfs_rmap_update(cur, &NEW); + if (error) + goto done; + break; + + case RMAP_LEFT_FILLING | RMAP_RIGHT_FILLING | RMAP_RIGHT_CONTIG: + /* + * Setting all of a previous oldext extent to newext. + * The right neighbor is contiguous, the left is not. + */ + error = xfs_btree_increment(cur, 0, &i); + if (error) + goto done; + XFS_WANT_CORRUPTED_GOTO(mp, i == 1, done); + trace_xfs_rmap_delete(mp, cur->bc_private.a.agno, + RIGHT.rm_startblock, RIGHT.rm_blockcount, + RIGHT.rm_owner, RIGHT.rm_offset, + RIGHT.rm_flags); + error = xfs_btree_delete(cur, &i); + if (error) + goto done; + XFS_WANT_CORRUPTED_GOTO(mp, i == 1, done); + error = xfs_btree_decrement(cur, 0, &i); + if (error) + goto done; + XFS_WANT_CORRUPTED_GOTO(mp, i == 1, done); + NEW = PREV; + NEW.rm_blockcount = len + RIGHT.rm_blockcount; + NEW.rm_flags = newext; + error = xfs_rmap_update(cur, &NEW); + if (error) + goto done; + break; + + case RMAP_LEFT_FILLING | RMAP_RIGHT_FILLING: + /* + * Setting all of a previous oldext extent to newext. + * Neither the left nor right neighbors are contiguous with + * the new one. + */ + NEW = PREV; + NEW.rm_flags = newext; + error = xfs_rmap_update(cur, &NEW); + if (error) + goto done; + break; + + case RMAP_LEFT_FILLING | RMAP_LEFT_CONTIG: + /* + * Setting the first part of a previous oldext extent to newext. + * The left neighbor is contiguous. + */ + NEW = PREV; + NEW.rm_offset += len; + NEW.rm_startblock += len; + NEW.rm_blockcount -= len; + error = xfs_rmap_update(cur, &NEW); + if (error) + goto done; + error = xfs_btree_decrement(cur, 0, &i); + if (error) + goto done; + NEW = LEFT; + NEW.rm_blockcount += len; + error = xfs_rmap_update(cur, &NEW); + if (error) + goto done; + break; + + case RMAP_LEFT_FILLING: + /* + * Setting the first part of a previous oldext extent to newext. + * The left neighbor is not contiguous. + */ + NEW = PREV; + NEW.rm_startblock += len; + NEW.rm_offset += len; + NEW.rm_blockcount -= len; + error = xfs_rmap_update(cur, &NEW); + if (error) + goto done; + NEW.rm_startblock = bno; + NEW.rm_owner = owner; + NEW.rm_offset = offset; + NEW.rm_blockcount = len; + NEW.rm_flags = newext; + cur->bc_rec.r = NEW; + trace_xfs_rmap_insert(mp, cur->bc_private.a.agno, bno, + len, owner, offset, newext); + error = xfs_btree_insert(cur, &i); + if (error) + goto done; + XFS_WANT_CORRUPTED_GOTO(mp, i == 1, done); + break; + + case RMAP_RIGHT_FILLING | RMAP_RIGHT_CONTIG: + /* + * Setting the last part of a previous oldext extent to newext. + * The right neighbor is contiguous with the new allocation. + */ + NEW = PREV; + NEW.rm_blockcount -= len; + error = xfs_rmap_update(cur, &NEW); + if (error) + goto done; + error = xfs_btree_increment(cur, 0, &i); + if (error) + goto done; + NEW = RIGHT; + NEW.rm_offset = offset; + NEW.rm_startblock = bno; + NEW.rm_blockcount += len; + error = xfs_rmap_update(cur, &NEW); + if (error) + goto done; + break; + + case RMAP_RIGHT_FILLING: + /* + * Setting the last part of a previous oldext extent to newext. + * The right neighbor is not contiguous. + */ + NEW = PREV; + NEW.rm_blockcount -= len; + error = xfs_rmap_update(cur, &NEW); + if (error) + goto done; + error = xfs_rmap_lookup_eq(cur, bno, len, owner, offset, + oldext, &i); + if (error) + goto done; + XFS_WANT_CORRUPTED_GOTO(mp, i == 0, done); + NEW.rm_startblock = bno; + NEW.rm_owner = owner; + NEW.rm_offset = offset; + NEW.rm_blockcount = len; + NEW.rm_flags = newext; + cur->bc_rec.r = NEW; + trace_xfs_rmap_insert(mp, cur->bc_private.a.agno, bno, + len, owner, offset, newext); + error = xfs_btree_insert(cur, &i); + if (error) + goto done; + XFS_WANT_CORRUPTED_GOTO(mp, i == 1, done); + break; + + case 0: + /* + * Setting the middle part of a previous oldext extent to + * newext. Contiguity is impossible here. + * One extent becomes three extents. + */ + /* new right extent - oldext */ + NEW.rm_startblock = bno + len; + NEW.rm_owner = owner; + NEW.rm_offset = new_endoff; + NEW.rm_blockcount = PREV.rm_offset + PREV.rm_blockcount - + new_endoff; + NEW.rm_flags = PREV.rm_flags; + error = xfs_rmap_update(cur, &NEW); + if (error) + goto done; + /* new left extent - oldext */ + NEW = PREV; + NEW.rm_blockcount = offset - PREV.rm_offset; + cur->bc_rec.r = NEW; + trace_xfs_rmap_insert(mp, cur->bc_private.a.agno, + NEW.rm_startblock, NEW.rm_blockcount, + NEW.rm_owner, NEW.rm_offset, + NEW.rm_flags); + error = xfs_btree_insert(cur, &i); + if (error) + goto done; + XFS_WANT_CORRUPTED_GOTO(mp, i == 1, done); + /* + * Reset the cursor to the position of the new extent + * we are about to insert as we can't trust it after + * the previous insert. + */ + error = xfs_rmap_lookup_eq(cur, bno, len, owner, offset, + oldext, &i); + if (error) + goto done; + XFS_WANT_CORRUPTED_GOTO(mp, i == 0, done); + /* new middle extent - newext */ + cur->bc_rec.r.rm_flags &= ~XFS_RMAP_UNWRITTEN; + cur->bc_rec.r.rm_flags |= newext; + trace_xfs_rmap_insert(mp, cur->bc_private.a.agno, bno, len, + owner, offset, newext); + error = xfs_btree_insert(cur, &i); + if (error) + goto done; + XFS_WANT_CORRUPTED_GOTO(mp, i == 1, done); + break; + + case RMAP_LEFT_FILLING | RMAP_LEFT_CONTIG | RMAP_RIGHT_CONTIG: + case RMAP_RIGHT_FILLING | RMAP_LEFT_CONTIG | RMAP_RIGHT_CONTIG: + case RMAP_LEFT_FILLING | RMAP_RIGHT_CONTIG: + case RMAP_RIGHT_FILLING | RMAP_LEFT_CONTIG: + case RMAP_LEFT_CONTIG | RMAP_RIGHT_CONTIG: + case RMAP_LEFT_CONTIG: + case RMAP_RIGHT_CONTIG: + /* + * These cases are all impossible. + */ + ASSERT(0); + } + + trace_xfs_rmap_convert_done(mp, cur->bc_private.a.agno, bno, len, + unwritten, oinfo); +done: + if (error) + trace_xfs_rmap_convert_error(cur->bc_mp, + cur->bc_private.a.agno, error, _RET_IP_); + return error; +} + +#undef NEW +#undef LEFT +#undef RIGHT +#undef PREV + struct xfs_rmap_query_range_info { xfs_rmap_query_range_fn fn; void *priv; diff --git a/fs/xfs/xfs_trace.h b/fs/xfs/xfs_trace.h index e099eda75b68..551b7e26980c 100644 --- a/fs/xfs/xfs_trace.h +++ b/fs/xfs/xfs_trace.h @@ -2499,6 +2499,10 @@ DEFINE_AG_ERROR_EVENT(xfs_rmap_unmap_error); DEFINE_RMAP_EVENT(xfs_rmap_map); DEFINE_RMAP_EVENT(xfs_rmap_map_done); DEFINE_AG_ERROR_EVENT(xfs_rmap_map_error); +DEFINE_RMAP_EVENT(xfs_rmap_convert); +DEFINE_RMAP_EVENT(xfs_rmap_convert_done); +DEFINE_AG_ERROR_EVENT(xfs_rmap_convert_error); +DEFINE_AG_ERROR_EVENT(xfs_rmap_convert_state); DECLARE_EVENT_CLASS(xfs_rmapbt_class, TP_PROTO(struct xfs_mount *mp, xfs_agnumber_t agno, @@ -2553,6 +2557,7 @@ DEFINE_AG_ERROR_EVENT(xfs_rmap_delete_error); DEFINE_AG_ERROR_EVENT(xfs_rmap_update_error); DEFINE_RMAPBT_EVENT(xfs_rmap_lookup_le_range_result); DEFINE_RMAPBT_EVENT(xfs_rmap_find_right_neighbor_result); +DEFINE_RMAPBT_EVENT(xfs_rmap_find_left_neighbor_result); #endif /* _TRACE_XFS_H */ -- cgit v1.2.3