summaryrefslogtreecommitdiffstats
diff options
context:
space:
mode:
Diffstat
-rw-r--r--fs/xfs/libxfs/xfs_alloc.c2
-rw-r--r--fs/xfs/libxfs/xfs_alloc_btree.c18
-rw-r--r--fs/xfs/libxfs/xfs_bmap_btree.c10
-rw-r--r--fs/xfs/libxfs/xfs_btree.c24
-rw-r--r--fs/xfs/libxfs/xfs_btree.h50
-rw-r--r--fs/xfs/libxfs/xfs_ialloc_btree.c12
-rw-r--r--fs/xfs/libxfs/xfs_refcount.c2
-rw-r--r--fs/xfs/libxfs/xfs_refcount_btree.c12
-rw-r--r--fs/xfs/libxfs/xfs_rmap.c5
-rw-r--r--fs/xfs/libxfs/xfs_rmap_btree.c47
10 files changed, 142 insertions, 40 deletions
diff --git a/fs/xfs/libxfs/xfs_alloc.c b/fs/xfs/libxfs/xfs_alloc.c
index 34c8501d86d0..fdfa08cbf4db 100644
--- a/fs/xfs/libxfs/xfs_alloc.c
+++ b/fs/xfs/libxfs/xfs_alloc.c
@@ -3764,7 +3764,7 @@ xfs_alloc_has_records(
memset(&high, 0xFF, sizeof(high));
high.a.ar_startblock = bno + len - 1;
- return xfs_btree_has_records(cur, &low, &high, outcome);
+ return xfs_btree_has_records(cur, &low, &high, NULL, outcome);
}
/*
diff --git a/fs/xfs/libxfs/xfs_alloc_btree.c b/fs/xfs/libxfs/xfs_alloc_btree.c
index be80c57aeddc..c65228efed4a 100644
--- a/fs/xfs/libxfs/xfs_alloc_btree.c
+++ b/fs/xfs/libxfs/xfs_alloc_btree.c
@@ -260,20 +260,27 @@ STATIC int64_t
xfs_bnobt_diff_two_keys(
struct xfs_btree_cur *cur,
const union xfs_btree_key *k1,
- const union xfs_btree_key *k2)
+ const union xfs_btree_key *k2,
+ const union xfs_btree_key *mask)
{
+ ASSERT(!mask || mask->alloc.ar_startblock);
+
return (int64_t)be32_to_cpu(k1->alloc.ar_startblock) -
- be32_to_cpu(k2->alloc.ar_startblock);
+ be32_to_cpu(k2->alloc.ar_startblock);
}
STATIC int64_t
xfs_cntbt_diff_two_keys(
struct xfs_btree_cur *cur,
const union xfs_btree_key *k1,
- const union xfs_btree_key *k2)
+ const union xfs_btree_key *k2,
+ const union xfs_btree_key *mask)
{
int64_t diff;
+ ASSERT(!mask || (mask->alloc.ar_blockcount &&
+ mask->alloc.ar_startblock));
+
diff = be32_to_cpu(k1->alloc.ar_blockcount) -
be32_to_cpu(k2->alloc.ar_blockcount);
if (diff)
@@ -427,8 +434,11 @@ STATIC enum xbtree_key_contig
xfs_allocbt_keys_contiguous(
struct xfs_btree_cur *cur,
const union xfs_btree_key *key1,
- const union xfs_btree_key *key2)
+ const union xfs_btree_key *key2,
+ const union xfs_btree_key *mask)
{
+ ASSERT(!mask || mask->alloc.ar_startblock);
+
return xbtree_key_contig(be32_to_cpu(key1->alloc.ar_startblock),
be32_to_cpu(key2->alloc.ar_startblock));
}
diff --git a/fs/xfs/libxfs/xfs_bmap_btree.c b/fs/xfs/libxfs/xfs_bmap_btree.c
index 3edf314a55e2..1b40e5f8b1ec 100644
--- a/fs/xfs/libxfs/xfs_bmap_btree.c
+++ b/fs/xfs/libxfs/xfs_bmap_btree.c
@@ -382,11 +382,14 @@ STATIC int64_t
xfs_bmbt_diff_two_keys(
struct xfs_btree_cur *cur,
const union xfs_btree_key *k1,
- const union xfs_btree_key *k2)
+ const union xfs_btree_key *k2,
+ const union xfs_btree_key *mask)
{
uint64_t a = be64_to_cpu(k1->bmbt.br_startoff);
uint64_t b = be64_to_cpu(k2->bmbt.br_startoff);
+ ASSERT(!mask || mask->bmbt.br_startoff);
+
/*
* Note: This routine previously casted a and b to int64 and subtracted
* them to generate a result. This lead to problems if b was the
@@ -504,8 +507,11 @@ STATIC enum xbtree_key_contig
xfs_bmbt_keys_contiguous(
struct xfs_btree_cur *cur,
const union xfs_btree_key *key1,
- const union xfs_btree_key *key2)
+ const union xfs_btree_key *key2,
+ const union xfs_btree_key *mask)
{
+ ASSERT(!mask || mask->bmbt.br_startoff);
+
return xbtree_key_contig(be64_to_cpu(key1->bmbt.br_startoff),
be64_to_cpu(key2->bmbt.br_startoff));
}
diff --git a/fs/xfs/libxfs/xfs_btree.c b/fs/xfs/libxfs/xfs_btree.c
index afbd3bcdf567..6a6503ab0cd7 100644
--- a/fs/xfs/libxfs/xfs_btree.c
+++ b/fs/xfs/libxfs/xfs_btree.c
@@ -5030,6 +5030,9 @@ struct xfs_btree_has_records {
union xfs_btree_key start_key;
union xfs_btree_key end_key;
+ /* Mask for key comparisons, if desired. */
+ const union xfs_btree_key *key_mask;
+
/* Highest record key we've seen so far. */
union xfs_btree_key high_key;
@@ -5057,7 +5060,8 @@ xfs_btree_has_records_helper(
* then there is a hole at the start of the search range.
* Classify this as sparse and stop immediately.
*/
- if (xfs_btree_keycmp_lt(cur, &info->start_key, &rec_key))
+ if (xfs_btree_masked_keycmp_lt(cur, &info->start_key, &rec_key,
+ info->key_mask))
return -ECANCELED;
} else {
/*
@@ -5068,7 +5072,7 @@ xfs_btree_has_records_helper(
* signal corruption.
*/
key_contig = cur->bc_ops->keys_contiguous(cur, &info->high_key,
- &rec_key);
+ &rec_key, info->key_mask);
if (key_contig == XBTREE_KEY_OVERLAP &&
!(cur->bc_flags & XFS_BTREE_OVERLAPPING))
return -EFSCORRUPTED;
@@ -5081,7 +5085,8 @@ xfs_btree_has_records_helper(
* remember it for later.
*/
cur->bc_ops->init_high_key_from_rec(&rec_high_key, rec);
- if (xfs_btree_keycmp_gt(cur, &rec_high_key, &info->high_key))
+ if (xfs_btree_masked_keycmp_gt(cur, &rec_high_key, &info->high_key,
+ info->key_mask))
info->high_key = rec_high_key; /* struct copy */
return 0;
@@ -5092,16 +5097,26 @@ xfs_btree_has_records_helper(
* map to any records; is fully mapped to records; or is partially mapped to
* records. This is the btree record equivalent to determining if a file is
* sparse.
+ *
+ * For most btree types, the record scan should use all available btree key
+ * fields to compare the keys encountered. These callers should pass NULL for
+ * @mask. However, some callers (e.g. scanning physical space in the rmapbt)
+ * want to ignore some part of the btree record keyspace when performing the
+ * comparison. These callers should pass in a union xfs_btree_key object with
+ * the fields that *should* be a part of the comparison set to any nonzero
+ * value, and the rest zeroed.
*/
int
xfs_btree_has_records(
struct xfs_btree_cur *cur,
const union xfs_btree_irec *low,
const union xfs_btree_irec *high,
+ const union xfs_btree_key *mask,
enum xbtree_recpacking *outcome)
{
struct xfs_btree_has_records info = {
.outcome = XBTREE_RECPACKING_EMPTY,
+ .key_mask = mask,
};
int error;
@@ -5129,7 +5144,8 @@ xfs_btree_has_records(
* the end of the search range, classify this as full. Otherwise,
* there is a hole at the end of the search range.
*/
- if (xfs_btree_keycmp_ge(cur, &info.high_key, &info.end_key))
+ if (xfs_btree_masked_keycmp_ge(cur, &info.high_key, &info.end_key,
+ mask))
info.outcome = XBTREE_RECPACKING_FULL;
out:
diff --git a/fs/xfs/libxfs/xfs_btree.h b/fs/xfs/libxfs/xfs_btree.h
index 66431f351bb2..a2aa36b23e25 100644
--- a/fs/xfs/libxfs/xfs_btree.h
+++ b/fs/xfs/libxfs/xfs_btree.h
@@ -161,11 +161,14 @@ struct xfs_btree_ops {
/*
* Difference between key2 and key1 -- positive if key1 > key2,
- * negative if key1 < key2, and zero if equal.
+ * negative if key1 < key2, and zero if equal. If the @mask parameter
+ * is non NULL, each key field to be used in the comparison must
+ * contain a nonzero value.
*/
int64_t (*diff_two_keys)(struct xfs_btree_cur *cur,
const union xfs_btree_key *key1,
- const union xfs_btree_key *key2);
+ const union xfs_btree_key *key2,
+ const union xfs_btree_key *mask);
const struct xfs_buf_ops *buf_ops;
@@ -187,10 +190,13 @@ struct xfs_btree_ops {
* @key1 < K < @key2. To determine if two btree records are
* immediately adjacent, @key1 should be the high key of the first
* record and @key2 should be the low key of the second record.
+ * If the @mask parameter is non NULL, each key field to be used in the
+ * comparison must contain a nonzero value.
*/
enum xbtree_key_contig (*keys_contiguous)(struct xfs_btree_cur *cur,
const union xfs_btree_key *key1,
- const union xfs_btree_key *key2);
+ const union xfs_btree_key *key2,
+ const union xfs_btree_key *mask);
};
/*
@@ -581,6 +587,7 @@ typedef bool (*xfs_btree_key_gap_fn)(struct xfs_btree_cur *cur,
int xfs_btree_has_records(struct xfs_btree_cur *cur,
const union xfs_btree_irec *low,
const union xfs_btree_irec *high,
+ const union xfs_btree_key *mask,
enum xbtree_recpacking *outcome);
bool xfs_btree_has_more_records(struct xfs_btree_cur *cur);
@@ -593,7 +600,7 @@ xfs_btree_keycmp_lt(
const union xfs_btree_key *key1,
const union xfs_btree_key *key2)
{
- return cur->bc_ops->diff_two_keys(cur, key1, key2) < 0;
+ return cur->bc_ops->diff_two_keys(cur, key1, key2, NULL) < 0;
}
static inline bool
@@ -602,7 +609,7 @@ xfs_btree_keycmp_gt(
const union xfs_btree_key *key1,
const union xfs_btree_key *key2)
{
- return cur->bc_ops->diff_two_keys(cur, key1, key2) > 0;
+ return cur->bc_ops->diff_two_keys(cur, key1, key2, NULL) > 0;
}
static inline bool
@@ -611,7 +618,7 @@ xfs_btree_keycmp_eq(
const union xfs_btree_key *key1,
const union xfs_btree_key *key2)
{
- return cur->bc_ops->diff_two_keys(cur, key1, key2) == 0;
+ return cur->bc_ops->diff_two_keys(cur, key1, key2, NULL) == 0;
}
static inline bool
@@ -641,6 +648,37 @@ xfs_btree_keycmp_ne(
return !xfs_btree_keycmp_eq(cur, key1, key2);
}
+/* Masked key comparison helpers */
+static inline bool
+xfs_btree_masked_keycmp_lt(
+ struct xfs_btree_cur *cur,
+ const union xfs_btree_key *key1,
+ const union xfs_btree_key *key2,
+ const union xfs_btree_key *mask)
+{
+ return cur->bc_ops->diff_two_keys(cur, key1, key2, mask) < 0;
+}
+
+static inline bool
+xfs_btree_masked_keycmp_gt(
+ struct xfs_btree_cur *cur,
+ const union xfs_btree_key *key1,
+ const union xfs_btree_key *key2,
+ const union xfs_btree_key *mask)
+{
+ return cur->bc_ops->diff_two_keys(cur, key1, key2, mask) > 0;
+}
+
+static inline bool
+xfs_btree_masked_keycmp_ge(
+ struct xfs_btree_cur *cur,
+ const union xfs_btree_key *key1,
+ const union xfs_btree_key *key2,
+ const union xfs_btree_key *mask)
+{
+ return !xfs_btree_masked_keycmp_lt(cur, key1, key2, mask);
+}
+
/* Does this cursor point to the last block in the given level? */
static inline bool
xfs_btree_islastblock(
diff --git a/fs/xfs/libxfs/xfs_ialloc_btree.c b/fs/xfs/libxfs/xfs_ialloc_btree.c
index dd1fad8c3304..5a945ae21b5d 100644
--- a/fs/xfs/libxfs/xfs_ialloc_btree.c
+++ b/fs/xfs/libxfs/xfs_ialloc_btree.c
@@ -269,10 +269,13 @@ STATIC int64_t
xfs_inobt_diff_two_keys(
struct xfs_btree_cur *cur,
const union xfs_btree_key *k1,
- const union xfs_btree_key *k2)
+ const union xfs_btree_key *k2,
+ const union xfs_btree_key *mask)
{
+ ASSERT(!mask || mask->inobt.ir_startino);
+
return (int64_t)be32_to_cpu(k1->inobt.ir_startino) -
- be32_to_cpu(k2->inobt.ir_startino);
+ be32_to_cpu(k2->inobt.ir_startino);
}
static xfs_failaddr_t
@@ -387,8 +390,11 @@ STATIC enum xbtree_key_contig
xfs_inobt_keys_contiguous(
struct xfs_btree_cur *cur,
const union xfs_btree_key *key1,
- const union xfs_btree_key *key2)
+ const union xfs_btree_key *key2,
+ const union xfs_btree_key *mask)
{
+ ASSERT(!mask || mask->inobt.ir_startino);
+
return xbtree_key_contig(be32_to_cpu(key1->inobt.ir_startino),
be32_to_cpu(key2->inobt.ir_startino));
}
diff --git a/fs/xfs/libxfs/xfs_refcount.c b/fs/xfs/libxfs/xfs_refcount.c
index 94377b59ba44..c1c65774dcc2 100644
--- a/fs/xfs/libxfs/xfs_refcount.c
+++ b/fs/xfs/libxfs/xfs_refcount.c
@@ -2019,7 +2019,7 @@ xfs_refcount_has_records(
high.rc.rc_startblock = bno + len - 1;
low.rc.rc_domain = high.rc.rc_domain = domain;
- return xfs_btree_has_records(cur, &low, &high, outcome);
+ return xfs_btree_has_records(cur, &low, &high, NULL, outcome);
}
int __init
diff --git a/fs/xfs/libxfs/xfs_refcount_btree.c b/fs/xfs/libxfs/xfs_refcount_btree.c
index 1628eecb53fd..d4afc5f4e6a5 100644
--- a/fs/xfs/libxfs/xfs_refcount_btree.c
+++ b/fs/xfs/libxfs/xfs_refcount_btree.c
@@ -202,10 +202,13 @@ STATIC int64_t
xfs_refcountbt_diff_two_keys(
struct xfs_btree_cur *cur,
const union xfs_btree_key *k1,
- const union xfs_btree_key *k2)
+ const union xfs_btree_key *k2,
+ const union xfs_btree_key *mask)
{
+ ASSERT(!mask || mask->refc.rc_startblock);
+
return (int64_t)be32_to_cpu(k1->refc.rc_startblock) -
- be32_to_cpu(k2->refc.rc_startblock);
+ be32_to_cpu(k2->refc.rc_startblock);
}
STATIC xfs_failaddr_t
@@ -304,8 +307,11 @@ STATIC enum xbtree_key_contig
xfs_refcountbt_keys_contiguous(
struct xfs_btree_cur *cur,
const union xfs_btree_key *key1,
- const union xfs_btree_key *key2)
+ const union xfs_btree_key *key2,
+ const union xfs_btree_key *mask)
{
+ ASSERT(!mask || mask->refc.rc_startblock);
+
return xbtree_key_contig(be32_to_cpu(key1->refc.rc_startblock),
be32_to_cpu(key2->refc.rc_startblock));
}
diff --git a/fs/xfs/libxfs/xfs_rmap.c b/fs/xfs/libxfs/xfs_rmap.c
index e616b964f11c..308b81f321eb 100644
--- a/fs/xfs/libxfs/xfs_rmap.c
+++ b/fs/xfs/libxfs/xfs_rmap.c
@@ -2721,6 +2721,9 @@ xfs_rmap_has_records(
xfs_extlen_t len,
enum xbtree_recpacking *outcome)
{
+ union xfs_btree_key mask = {
+ .rmap.rm_startblock = cpu_to_be32(-1U),
+ };
union xfs_btree_irec low;
union xfs_btree_irec high;
@@ -2729,7 +2732,7 @@ xfs_rmap_has_records(
memset(&high, 0xFF, sizeof(high));
high.r.rm_startblock = bno + len - 1;
- return xfs_btree_has_records(cur, &low, &high, outcome);
+ return xfs_btree_has_records(cur, &low, &high, &mask, outcome);
}
/*
diff --git a/fs/xfs/libxfs/xfs_rmap_btree.c b/fs/xfs/libxfs/xfs_rmap_btree.c
index 66beb87caf1a..6c81b20e97d2 100644
--- a/fs/xfs/libxfs/xfs_rmap_btree.c
+++ b/fs/xfs/libxfs/xfs_rmap_btree.c
@@ -273,31 +273,43 @@ STATIC int64_t
xfs_rmapbt_diff_two_keys(
struct xfs_btree_cur *cur,
const union xfs_btree_key *k1,
- const union xfs_btree_key *k2)
+ const union xfs_btree_key *k2,
+ const union xfs_btree_key *mask)
{
const struct xfs_rmap_key *kp1 = &k1->rmap;
const struct xfs_rmap_key *kp2 = &k2->rmap;
int64_t d;
__u64 x, y;
+ /* Doesn't make sense to mask off the physical space part */
+ ASSERT(!mask || mask->rmap.rm_startblock);
+
d = (int64_t)be32_to_cpu(kp1->rm_startblock) -
- be32_to_cpu(kp2->rm_startblock);
+ be32_to_cpu(kp2->rm_startblock);
if (d)
return d;
- x = be64_to_cpu(kp1->rm_owner);
- y = be64_to_cpu(kp2->rm_owner);
- if (x > y)
- return 1;
- else if (y > x)
- return -1;
+ if (!mask || mask->rmap.rm_owner) {
+ x = be64_to_cpu(kp1->rm_owner);
+ y = be64_to_cpu(kp2->rm_owner);
+ if (x > y)
+ return 1;
+ else if (y > x)
+ return -1;
+ }
+
+ if (!mask || mask->rmap.rm_offset) {
+ /* Doesn't make sense to allow offset but not owner */
+ ASSERT(!mask || mask->rmap.rm_owner);
+
+ x = offset_keymask(be64_to_cpu(kp1->rm_offset));
+ y = offset_keymask(be64_to_cpu(kp2->rm_offset));
+ if (x > y)
+ return 1;
+ else if (y > x)
+ return -1;
+ }
- x = offset_keymask(be64_to_cpu(kp1->rm_offset));
- y = offset_keymask(be64_to_cpu(kp2->rm_offset));
- if (x > y)
- return 1;
- else if (y > x)
- return -1;
return 0;
}
@@ -448,13 +460,18 @@ STATIC enum xbtree_key_contig
xfs_rmapbt_keys_contiguous(
struct xfs_btree_cur *cur,
const union xfs_btree_key *key1,
- const union xfs_btree_key *key2)
+ const union xfs_btree_key *key2,
+ const union xfs_btree_key *mask)
{
+ ASSERT(!mask || mask->rmap.rm_startblock);
+
/*
* We only support checking contiguity of the physical space component.
* If any callers ever need more specificity than that, they'll have to
* implement it here.
*/
+ ASSERT(!mask || (!mask->rmap.rm_owner && !mask->rmap.rm_offset));
+
return xbtree_key_contig(be32_to_cpu(key1->rmap.rm_startblock),
be32_to_cpu(key2->rmap.rm_startblock));
}
generated by cgit v1.2.3 (git 2.25.1) at 2024-11-15 01:04:52 +0000