xfs: teach xfs_btree_has_record to return false if there are gaps
The current implementation of xfs_btree_has_record returns true if it
finds /any/ record within the given range. Unfortunately, that's not
what the predicate is supposed to do -- it's supposed to test if the
/entire/ range is covered by records.
Therefore, enhance the routine to check that the first record it
encounters starts earlier or at the same point as the low key, the last
record ends at or after the same point as the high key, and that there
aren't any gaps in the records.
Signed-off-by: Darrick J. Wong <darrick.wong@oracle.com>
diff --git a/libxfs/xfs_alloc.c b/libxfs/xfs_alloc.c
index 92f61fa..5119aea 100644
--- a/libxfs/xfs_alloc.c
+++ b/libxfs/xfs_alloc.c
@@ -3374,6 +3374,18 @@
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(
@@ -3390,7 +3402,8 @@
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/libxfs/xfs_btree.c b/libxfs/xfs_btree.c
index a408aa4..b255d34 100644
--- a/libxfs/xfs_btree.c
+++ b/libxfs/xfs_btree.c
@@ -4872,6 +4872,23 @@
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(
@@ -4879,7 +4896,35 @@
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? */
@@ -4888,18 +4933,42 @@
struct xfs_btree_cur *cur,
union xfs_btree_irec *low,
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/libxfs/xfs_btree.h b/libxfs/xfs_btree.h
index 0f79023..e81c23b 100644
--- a/libxfs/xfs_btree.h
+++ b/libxfs/xfs_btree.h
@@ -508,8 +508,12 @@
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, union xfs_btree_irec *low,
- union xfs_btree_irec *high, bool *exists);
+ 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/libxfs/xfs_refcount.c b/libxfs/xfs_refcount.c
index 723c903..7bd0f7f 100644
--- a/libxfs/xfs_refcount.c
+++ b/libxfs/xfs_refcount.c
@@ -1768,6 +1768,18 @@
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(
@@ -1784,5 +1796,6 @@
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);
}
diff --git a/libxfs/xfs_rmap.c b/libxfs/xfs_rmap.c
index 6205b8e..1261632 100644
--- a/libxfs/xfs_rmap.c
+++ b/libxfs/xfs_rmap.c
@@ -2631,6 +2631,18 @@
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(
@@ -2647,7 +2659,8 @@
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);
}
/*
