diff options
| -rw-r--r-- | fs/xfs/libxfs/xfs_alloc.c | 15 | ||||
| -rw-r--r-- | fs/xfs/libxfs/xfs_btree.c | 82 | ||||
| -rw-r--r-- | fs/xfs/libxfs/xfs_btree.h | 6 | ||||
| -rw-r--r-- | fs/xfs/libxfs/xfs_refcount.c | 15 | ||||
| -rw-r--r-- | fs/xfs/libxfs/xfs_rmap.c | 15 |
5 files changed, 124 insertions, 9 deletions
diff --git a/fs/xfs/libxfs/xfs_alloc.c b/fs/xfs/libxfs/xfs_alloc.c index 353e53b892e6..51c38377d08d 100644 --- a/fs/xfs/libxfs/xfs_alloc.c +++ b/fs/xfs/libxfs/xfs_alloc.c @@ -3497,6 +3497,18 @@ xfs_alloc_query_all( return xfs_btree_query_all(cur, xfs_alloc_query_range_helper, &query); } +static bool +xfs_alloc_has_key_gap( + struct xfs_btree_cur *cur, + const union xfs_btree_key *key1, + const union xfs_btree_key *key2) +{ + xfs_agblock_t next; + + next = be32_to_cpu(key1->alloc.ar_startblock) + 1; + return next != be32_to_cpu(key2->alloc.ar_startblock); +} + /* Is there a record covering a given extent? */ int xfs_alloc_has_record( @@ -3513,7 +3525,8 @@ xfs_alloc_has_record( memset(&high, 0xFF, sizeof(high)); high.a.ar_startblock = bno + len - 1; - return xfs_btree_has_record(cur, &low, &high, exists); + return xfs_btree_has_record(cur, &low, &high, xfs_alloc_has_key_gap, + exists); } /* diff --git a/fs/xfs/libxfs/xfs_btree.c b/fs/xfs/libxfs/xfs_btree.c index f18a875f51c6..16dd3efabc11 100644 --- a/fs/xfs/libxfs/xfs_btree.c +++ b/fs/xfs/libxfs/xfs_btree.c @@ -4916,6 +4916,23 @@ xfs_btree_diff_two_ptrs( return (int64_t)be32_to_cpu(a->s) - be32_to_cpu(b->s); } +struct xbtree_hasrec { + xfs_btree_key_gap_fn has_gap; + + /* Keys for the start and end of the range we want to know about. */ + union xfs_btree_key start_key; + union xfs_btree_key end_key; + + /* Highest record key we've seen so far. */ + union xfs_btree_key high_key; + + /* Are we processing the first record? */ + bool first_rec; + + /* Did we see any records at all? */ + bool saw_anything; +}; + /* If there's an extent, we're done. */ STATIC int xfs_btree_has_record_helper( @@ -4923,7 +4940,35 @@ xfs_btree_has_record_helper( const union xfs_btree_rec *rec, void *priv) { - return -ECANCELED; + union xfs_btree_key rec_low_key; + union xfs_btree_key rec_high_key; + struct xbtree_hasrec *info = priv; + int64_t res; + + cur->bc_ops->init_key_from_rec(&rec_low_key, rec); + if (info->first_rec) { + /* Bail if the first record starts after the start key. */ + res = cur->bc_ops->diff_two_keys(cur, &info->start_key, + &rec_low_key); + if (res < 0) + return -ECANCELED; + + info->first_rec = false; + } else { + /* Bail if there's a gap with the previous record. */ + if (info->has_gap(cur, &info->high_key, &rec_low_key)) + return -ECANCELED; + } + + info->saw_anything = true; + + /* If the current record is higher than what we've seen, remember it. */ + cur->bc_ops->init_high_key_from_rec(&rec_high_key, rec); + res = cur->bc_ops->diff_two_keys(cur, &rec_high_key, &info->high_key); + if (res > 0) + info->high_key = rec_high_key; /* struct copy */ + + return 0; } /* Is there a record covering a given range of keys? */ @@ -4932,18 +4977,45 @@ xfs_btree_has_record( struct xfs_btree_cur *cur, const union xfs_btree_irec *low, const union xfs_btree_irec *high, + xfs_btree_key_gap_fn has_gap, bool *exists) { + struct xbtree_hasrec info = { + .first_rec = true, + .has_gap = has_gap, + }; + union xfs_btree_rec rec; + int64_t res; int error; + cur->bc_rec = *low; + cur->bc_ops->init_rec_from_cur(cur, &rec); + cur->bc_ops->init_key_from_rec(&info.start_key, &rec); + + cur->bc_rec = *high; + cur->bc_ops->init_rec_from_cur(cur, &rec); + cur->bc_ops->init_key_from_rec(&info.end_key, &rec); + error = xfs_btree_query_range(cur, low, high, - &xfs_btree_has_record_helper, NULL); + &xfs_btree_has_record_helper, &info); if (error == -ECANCELED) { - *exists = true; + /* Bailing out early means we found an uncovered area. */ + *exists = false; return 0; } - *exists = false; - return error; + if (error) + return error; + + if (!info.saw_anything) { + *exists = false; + } else { + /* Did the record set go at least as far as the end? */ + res = cur->bc_ops->diff_two_keys(cur, &info.high_key, + &info.end_key); + *exists = (res >= 0); + } + + return 0; } /* Are there more records in this btree? */ diff --git a/fs/xfs/libxfs/xfs_btree.h b/fs/xfs/libxfs/xfs_btree.h index 22d9f411fde6..39ad62477b42 100644 --- a/fs/xfs/libxfs/xfs_btree.h +++ b/fs/xfs/libxfs/xfs_btree.h @@ -540,9 +540,13 @@ void xfs_btree_get_keys(struct xfs_btree_cur *cur, struct xfs_btree_block *block, union xfs_btree_key *key); union xfs_btree_key *xfs_btree_high_key_from_key(struct xfs_btree_cur *cur, union xfs_btree_key *key); +typedef bool (*xfs_btree_key_gap_fn)(struct xfs_btree_cur *cur, + const union xfs_btree_key *key1, + const union xfs_btree_key *key2); int xfs_btree_has_record(struct xfs_btree_cur *cur, const union xfs_btree_irec *low, - const union xfs_btree_irec *high, bool *exists); + const union xfs_btree_irec *high, xfs_btree_key_gap_fn has_gap, + bool *exists); bool xfs_btree_has_more_records(struct xfs_btree_cur *cur); struct xfs_ifork *xfs_btree_ifork_ptr(struct xfs_btree_cur *cur); diff --git a/fs/xfs/libxfs/xfs_refcount.c b/fs/xfs/libxfs/xfs_refcount.c index 327ba25e9e17..7466e51f6e5d 100644 --- a/fs/xfs/libxfs/xfs_refcount.c +++ b/fs/xfs/libxfs/xfs_refcount.c @@ -1763,6 +1763,18 @@ out_free: return error; } +static bool +xfs_refcount_has_key_gap( + struct xfs_btree_cur *cur, + const union xfs_btree_key *key1, + const union xfs_btree_key *key2) +{ + xfs_agblock_t next; + + next = be32_to_cpu(key1->refc.rc_startblock) + 1; + return next != be32_to_cpu(key2->refc.rc_startblock); +} + /* Is there a record covering a given extent? */ int xfs_refcount_has_record( @@ -1779,7 +1791,8 @@ xfs_refcount_has_record( memset(&high, 0xFF, sizeof(high)); high.rc.rc_startblock = bno + len - 1; - return xfs_btree_has_record(cur, &low, &high, exists); + return xfs_btree_has_record(cur, &low, &high, xfs_refcount_has_key_gap, + exists); } int __init diff --git a/fs/xfs/libxfs/xfs_rmap.c b/fs/xfs/libxfs/xfs_rmap.c index cd322174dbff..e76c5c60e862 100644 --- a/fs/xfs/libxfs/xfs_rmap.c +++ b/fs/xfs/libxfs/xfs_rmap.c @@ -2632,6 +2632,18 @@ xfs_rmap_compare( return 0; } +static bool +xfs_rmap_has_key_gap( + struct xfs_btree_cur *cur, + const union xfs_btree_key *key1, + const union xfs_btree_key *key2) +{ + xfs_agblock_t next; + + next = be32_to_cpu(key1->rmap.rm_startblock) + 1; + return next != be32_to_cpu(key2->rmap.rm_startblock); +} + /* Is there a record covering a given extent? */ int xfs_rmap_has_record( @@ -2648,7 +2660,8 @@ xfs_rmap_has_record( memset(&high, 0xFF, sizeof(high)); high.r.rm_startblock = bno + len - 1; - return xfs_btree_has_record(cur, &low, &high, exists); + return xfs_btree_has_record(cur, &low, &high, xfs_rmap_has_key_gap, + exists); } /* |