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