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 <djwong@kernel.org>

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);
 }
 
 /*