[PATCH RFC] mm/filemap: fix lseek() skipping a new large folio

[PATCH RFC] mm/filemap: fix lseek() skipping a new large folio

[David Hildenbrand (Arm)]

mapping_seek_hole_data() walks the page cache under RCU and only calls
xas_set() after entries larger than a page. Between base-page entries,
it continues the walk with xas_find(), which skips sibling entries
to return each multi-index entry only once. If a large folio replaces
small folio entries between iterations, the slot holding the new folio
can lie behind the cursor. Skipping its sibling entries then skips data
that has not yet been examined.

On tmpfs, SEEK_HOLE can then return an offset inside existing data.
SEEK_DATA can skip data after a fallocated page that is not uptodate.

For example, assume a 2 MiB tmpfs file backed by 4 KiB pages on x86-64,
with page index 63 fallocated but not uptodate and all other pages
uptodate. Index 63 occupies the last slot in the old xarray leaf. A
SEEK_DATA starting there can skip that page, then race with collapse of
pages 0-511 into one 2 MiB folio. The next xas_find() moves past the old
leaf and skips the new folio's sibling entries in the parent, returning
-ENXIO instead of finding data at page index 64, or 256 KiB.

The inode lock held by lseek() does not exclude collapse or swapin.

Restarting the xarray walk after every entry fixes this, but increases
SEEK_HOLE time about 24%, when scanning a fully written 1 GiB memfd backed
by base-page folios in an x86-64 microbenchmark.

Instead, use xas_next() for adjacent indices. Restart the lookup from the
root at the requested index if it returns an empty slot or an internal
entry, including a sibling entry. Also restart for nonadjacent indices,
invalid iterator state, or failed folio validation. This avoids skipping
unexamined data without restarting each lookup during base-page scans.

Fixes: 6b24ca4a1a8d ("mm: Use multi-index entries in the page cache")
Reported-by: Chris Mason <mason@kernel.org>
Signed-off-by: David Hildenbrand (Arm) <david@kernel.org>
---
I'll be more than happy if someone of the pagecache folks wants to take
over ;)
---
 mm/filemap.c | 38 +++++++++++++++++++++++++++++++++++---
 1 file changed, 35 insertions(+), 3 deletions(-)

diff --git a/mm/filemap.c b/mm/filemap.c
index 648f783454c3..87c583509567 100644
--- a/mm/filemap.c
+++ b/mm/filemap.c
@@ -3233,6 +3233,40 @@ static inline size_t seek_folio_size(struct xa_state *xas, struct folio *folio)
 	return folio_size(folio);
 }
 
+static inline struct folio *seek_get_entry(struct xa_state *xas, pgoff_t index,
+					   pgoff_t max)
+{
+	struct folio *folio;
+
+	if (!xas_valid(xas) || xas->xa_index + 1 != index)
+		goto restart;
+
+	/*
+	 * A lookup within a multi-index entry can leave xa_offset at its
+	 * first slot. Restore the slot corresponding to xa_index before
+	 * advancing.
+	 */
+	xas_advance(xas, xas->xa_index);
+	folio = xas_next(xas);
+
+	/*
+	 * A concurrent collapse can replace the next slot with a sibling entry
+	 * referring back to the slot holding the folio.
+	 */
+	if (!folio || xa_is_internal(folio))
+		goto restart;
+	if (xa_is_value(folio))
+		return folio;
+	if (!folio_try_get(folio))
+		goto restart;
+	if (folio == xas_reload(xas))
+		return folio;
+	folio_put(folio);
+restart:
+	xas_set(xas, index);
+	return find_get_entry(xas, max, XA_PRESENT);
+}
+
 /**
  * mapping_seek_hole_data - Seek for SEEK_DATA / SEEK_HOLE in the page cache.
  * @mapping: Address space to search.
@@ -3263,7 +3297,7 @@ loff_t mapping_seek_hole_data(struct address_space *mapping, loff_t start,
 		return -ENXIO;
 
 	rcu_read_lock();
-	while ((folio = find_get_entry(&xas, max, XA_PRESENT))) {
+	while ((folio = seek_get_entry(&xas, start >> PAGE_SHIFT, max))) {
 		loff_t pos = (u64)xas.xa_index << PAGE_SHIFT;
 		size_t seek_size;
 		u64 next;
@@ -3286,8 +3320,6 @@ loff_t mapping_seek_hole_data(struct address_space *mapping, loff_t start,
 			goto unlock;
 		if (start >= end)
 			break;
-		if (seek_size > PAGE_SIZE)
-			xas_set(&xas, pos >> PAGE_SHIFT);
 		if (!xa_is_value(folio))
 			folio_put(folio);
 	}

---

base-commit: 93d7a816a2df3e907e2719bd12b0073f1285fc5c

change-id: 20261110-lseek_hole-4a9eb450d473

--

Cheers,

David

Re: [PATCH RFC] mm/filemap: fix lseek() skipping a new large folio

[Jan Kara]

On Tue 10-11-26 21:33:12, David Hildenbrand (Arm) wrote:
> mapping_seek_hole_data() walks the page cache under RCU and only calls
> xas_set() after entries larger than a page. Between base-page entries,
> it continues the walk with xas_find(), which skips sibling entries
> to return each multi-index entry only once. If a large folio replaces
> small folio entries between iterations, the slot holding the new folio
> can lie behind the cursor. Skipping its sibling entries then skips data
> that has not yet been examined.
> 
> On tmpfs, SEEK_HOLE can then return an offset inside existing data.
> SEEK_DATA can skip data after a fallocated page that is not uptodate.
> 
> For example, assume a 2 MiB tmpfs file backed by 4 KiB pages on x86-64,
> with page index 63 fallocated but not uptodate and all other pages
> uptodate. Index 63 occupies the last slot in the old xarray leaf. A
> SEEK_DATA starting there can skip that page, then race with collapse of
> pages 0-511 into one 2 MiB folio. The next xas_find() moves past the old
> leaf and skips the new folio's sibling entries in the parent, returning
> -ENXIO instead of finding data at page index 64, or 256 KiB.
> 
> The inode lock held by lseek() does not exclude collapse or swapin.
> 
> Restarting the xarray walk after every entry fixes this, but increases
> SEEK_HOLE time about 24%, when scanning a fully written 1 GiB memfd backed
> by base-page folios in an x86-64 microbenchmark.
> 
> Instead, use xas_next() for adjacent indices. Restart the lookup from the
> root at the requested index if it returns an empty slot or an internal
> entry, including a sibling entry. Also restart for nonadjacent indices,
> invalid iterator state, or failed folio validation. This avoids skipping
> unexamined data without restarting each lookup during base-page scans.
> 
> Fixes: 6b24ca4a1a8d ("mm: Use multi-index entries in the page cache")
> Reported-by: Chris Mason <mason@kernel.org>
> Signed-off-by: David Hildenbrand (Arm) <david@kernel.org>
> ---
> I'll be more than happy if someone of the pagecache folks wants to take
> over ;)

This looks good to me. Feel free to add:

Reviewed-by: Jan Kara <jack@suse.cz>

I just find it unfortunate that we have to play complicated games like
these for such a simple operation as sequentially iterating over all folios
in a mapping. And it is not a first bug of this nature trigered by
compaction. So longer term I believe we need to provide saner apis
shielding pagecache users from these nasty details.

								Honza

> ---
>  mm/filemap.c | 38 +++++++++++++++++++++++++++++++++++---
>  1 file changed, 35 insertions(+), 3 deletions(-)
> 
> diff --git a/mm/filemap.c b/mm/filemap.c
> index 648f783454c3..87c583509567 100644
> --- a/mm/filemap.c
> +++ b/mm/filemap.c
> @@ -3233,6 +3233,40 @@ static inline size_t seek_folio_size(struct xa_state *xas, struct folio *folio)
>  	return folio_size(folio);
>  }
>  
> +static inline struct folio *seek_get_entry(struct xa_state *xas, pgoff_t index,
> +					   pgoff_t max)
> +{
> +	struct folio *folio;
> +
> +	if (!xas_valid(xas) || xas->xa_index + 1 != index)
> +		goto restart;
> +
> +	/*
> +	 * A lookup within a multi-index entry can leave xa_offset at its
> +	 * first slot. Restore the slot corresponding to xa_index before
> +	 * advancing.
> +	 */
> +	xas_advance(xas, xas->xa_index);
> +	folio = xas_next(xas);
> +
> +	/*
> +	 * A concurrent collapse can replace the next slot with a sibling entry
> +	 * referring back to the slot holding the folio.
> +	 */
> +	if (!folio || xa_is_internal(folio))
> +		goto restart;
> +	if (xa_is_value(folio))
> +		return folio;
> +	if (!folio_try_get(folio))
> +		goto restart;
> +	if (folio == xas_reload(xas))
> +		return folio;
> +	folio_put(folio);
> +restart:
> +	xas_set(xas, index);
> +	return find_get_entry(xas, max, XA_PRESENT);
> +}
> +
>  /**
>   * mapping_seek_hole_data - Seek for SEEK_DATA / SEEK_HOLE in the page cache.
>   * @mapping: Address space to search.
> @@ -3263,7 +3297,7 @@ loff_t mapping_seek_hole_data(struct address_space *mapping, loff_t start,
>  		return -ENXIO;
>  
>  	rcu_read_lock();
> -	while ((folio = find_get_entry(&xas, max, XA_PRESENT))) {
> +	while ((folio = seek_get_entry(&xas, start >> PAGE_SHIFT, max))) {
>  		loff_t pos = (u64)xas.xa_index << PAGE_SHIFT;
>  		size_t seek_size;
>  		u64 next;
> @@ -3286,8 +3320,6 @@ loff_t mapping_seek_hole_data(struct address_space *mapping, loff_t start,
>  			goto unlock;
>  		if (start >= end)
>  			break;
> -		if (seek_size > PAGE_SIZE)
> -			xas_set(&xas, pos >> PAGE_SHIFT);
>  		if (!xa_is_value(folio))
>  			folio_put(folio);
>  	}
> 
> ---
> 
> base-commit: 93d7a816a2df3e907e2719bd12b0073f1285fc5c
> 
> change-id: 20261110-lseek_hole-4a9eb450d473
> 
> --
> 
> Cheers,
> 
> David
> 
-- 
Jan Kara <jack@suse.com>
SUSE Labs, CR

Re: [PATCH RFC] mm/filemap: fix lseek() skipping a new large folio

[David Hildenbrand (Arm)]

On 11/11/26 12:45, Jan Kara wrote:
> On Tue 10-11-26 21:33:12, David Hildenbrand (Arm) wrote:
>> mapping_seek_hole_data() walks the page cache under RCU and only calls
>> xas_set() after entries larger than a page. Between base-page entries,
>> it continues the walk with xas_find(), which skips sibling entries
>> to return each multi-index entry only once. If a large folio replaces
>> small folio entries between iterations, the slot holding the new folio
>> can lie behind the cursor. Skipping its sibling entries then skips data
>> that has not yet been examined.
>>
>> On tmpfs, SEEK_HOLE can then return an offset inside existing data.
>> SEEK_DATA can skip data after a fallocated page that is not uptodate.
>>
>> For example, assume a 2 MiB tmpfs file backed by 4 KiB pages on x86-64,
>> with page index 63 fallocated but not uptodate and all other pages
>> uptodate. Index 63 occupies the last slot in the old xarray leaf. A
>> SEEK_DATA starting there can skip that page, then race with collapse of
>> pages 0-511 into one 2 MiB folio. The next xas_find() moves past the old
>> leaf and skips the new folio's sibling entries in the parent, returning
>> -ENXIO instead of finding data at page index 64, or 256 KiB.
>>
>> The inode lock held by lseek() does not exclude collapse or swapin.
>>
>> Restarting the xarray walk after every entry fixes this, but increases
>> SEEK_HOLE time about 24%, when scanning a fully written 1 GiB memfd backed
>> by base-page folios in an x86-64 microbenchmark.
>>
>> Instead, use xas_next() for adjacent indices. Restart the lookup from the
>> root at the requested index if it returns an empty slot or an internal
>> entry, including a sibling entry. Also restart for nonadjacent indices,
>> invalid iterator state, or failed folio validation. This avoids skipping
>> unexamined data without restarting each lookup during base-page scans.
>>
>> Fixes: 6b24ca4a1a8d ("mm: Use multi-index entries in the page cache")
>> Reported-by: Chris Mason <mason@kernel.org>
>> Signed-off-by: David Hildenbrand (Arm) <david@kernel.org>
>> ---
>> I'll be more than happy if someone of the pagecache folks wants to take
>> over ;)
> 
> This looks good to me. Feel free to add:
> 
> Reviewed-by: Jan Kara <jack@suse.cz>
> 
> I just find it unfortunate that we have to play complicated games like

"unfortunate" is a good word. I'd have used "annoying" :)

> these for such a simple operation as sequentially iterating over all folios
> in a mapping. And it is not a first bug of this nature trigered by
> compaction. So longer term I believe we need to provide saner apis
> shielding pagecache users from these nasty details.
Yeah, I would have preferred the simpler fix, but ~24% slowdown gave me a pause :(

thanks!

-- 
Cheers,

David