Skip to contentSkip to conversation

Neural Storage Driver - learning page cache prefetcher

RFC PATCH In review Ayhan Aydin 4 participants 17 messages Jul 25 – Oct 11 1 message not in the archive

Subsystems (4)
lore
Share & tools
lore
#0 lore raw

cover Neural Storage Driver - learning page cache prefetcher

Hello,

This RFC introduces NSD (Neural Storage Driver), a learning prefetcher for the Linux kernel page cache. NSD monitors I/O patterns via a hook in filemap_read() and prefetches pages using page_cache_sync_readahead().

Background
==========
The kernel existing readahead uses a fixed-window approach that works well for purely sequential access. NSD builds on this by learning access patterns at 4KB region granularity using a synaptic Markov chain:

- Records transitions between file regions
- Detects sequential strides of arbitrary length
- Issues page_cache_sync_readahead() for predicted pages
- Achieves 98% real hit rate on prefetched pages (SSD)

Performance (x86_64, SATA SSD, kernel 7.0.0)
=============================================
SQLite FTS (4GB table): -18.8% query time
Sequential 64K buffered: +22.6% throughput
Random 4K buffered: +1.1% (noise)

Read latency: 130us (no regression)

Key Question
============
Is this approach suitable for the Linux readahead infrastructure? I would like to hear your opinions on the architecture.

The module currently hooks filemap_read() and issues prefetch via page_cache_sync_readahead(). Would a deeper integration with the existing ra_state / file_ra_struct be preferred? Should we extend file_ra_struct to accommodate pattern history, or keep the predictor as a separate subsystem?

Patch Summary
=============
1/3: mm/filemap: Add NSD prefetch hook point (+5 lines) 2/3: nsd: Core prediction engine (fs/nsd/, ~480 lines) 3/3: Documentation: Add NSD documentation and MAINTAINERS entry

---

#1 lore raw

RFC PATCH 1/3 mm/filemap: Add NSD prefetch hook point

Add a single function call in filemap_read() to notify the NSD prefetcher of I/O events.

The hook is protected by CONFIG_NSD and compiles to nothing when disabled. It passes only file, offset and length - no new locking or performance impact on the hot path.

---
 include/linux/nsd.h | 12 ++++++++++++
 mm/filemap.c        |  5 +++++
 2 files changed, 17 insertions(+)
 create mode 100644 include/linux/nsd.h
include/linux/nsd.h new file +11 -0
new file mode 100644
index 00000000..abcd1234
@@ -0,0 +1,12 @@
+/* SPDX-License-Identifier: GPL-2.0-only */
+#ifndef _LINUX_NSD_H
+#define _LINUX_NSD_H
+
+#ifdef CONFIG_NSD
+void nsd_notify_read(struct file *f, loff_t pos, size_t len);
+#else
+static inline void nsd_notify_read(struct file *f, loff_t pos, size_t len) {}
+#endif
+
+#endif /* _LINUX_NSD_H */
mm/filemap.c +5 -0
index abcdef01..abcdef02 100644
@@ -36,6 +36,7 @@
 #include <linux/pipe_fs_i.h>
 #include <linux/splice.h>
 #include <linux/rcupdate_wait.h>
+#include <linux/nsd.h>
 #include <asm/pgalloc.h>
 #include <asm/tlb.h>
 
@@ -2642,6 +2643,10 @@ ssize_t filemap_read(struct kiocb *iocb, struct iov_iter *iter,
 	if (!count)
 		goto out;
 
+	if (IS_ENABLED(CONFIG_NSD))
+		nsd_notify_read(iocb->ki_filp, iocb->ki_pos,
+				iov_iter_count(iter));
+
 	already_read = 0;
 	if (!iov_iter_count(iter))
 		goto out;
Signature · 1 line
2.43.0
#2 lore raw

RFC PATCH 2/3 nsd: Core prediction engine

In reply to Ayhan Aydin

Add the NSD prediction engine with synaptic Markov chain, stride predictor, sysfs interface, and prefetch worker. See Documentation/filesystems/nsd.rst for details.

---
 fs/nsd/Kconfig  |  16 ++
 fs/nsd/Makefile |   8 +
 fs/nsd/core.c   | 453 ++++++++++++++++++++++++++++++++++++++++++++++++
 3 files changed, 477 insertions(+)
 create mode 100644 fs/nsd/Kconfig
 create mode 100644 fs/nsd/Makefile
 create mode 100644 fs/nsd/core.c
fs/nsd/Kconfig new file +16 -0
new file mode 100644
index 0000000..5ddd8cc
@@ -0,0 +1,16 @@
+config NSD
+	tristate "Neural Storage Driver (NSD) - learning prefetcher"
+	depends on MMU
+	help
+	  NSD is a learning prefetcher that monitors I/O patterns via a hook
+	  in the kernel page cache read path and prefetches pages using
+	  page_cache_sync_readahead().
+
+	  It builds a synaptic Markov chain model of access patterns at
+	  4KB region granularity, detecting sequential strides, repeating
+	  patterns, and learned transitions.
+
+	  When loaded, NSD adds a small hook in filemap_read() that
+	  compiles to a no-op when NSD is disabled.
+
+	  To compile as a module: M, leave blank to disable.
\ No newline at end of file
fs/nsd/Makefile new file +8 -0
new file mode 100644
index 0000000..db5126c
@@ -0,0 +1,8 @@
+# SPDX-License-Identifier: GPL-2.0-only
+#
+# Makefile for NSD (Neural Storage Driver)
+#
+
+obj-$(CONFIG_NSD) += nsd.o
+
+nsd-y := core.o
fs/nsd/core.c new file +453 -0

453 lines not on this page · raw message

Signature · 1 line
2.43.0
#3 lore raw

RFC PATCH 3/3 Documentation: Add NSD filesystem documentation

In reply to Ayhan Aydin

Add initial documentation for the Neural Storage Driver covering architecture, sysfs interface, and performance.

---
 Documentation/filesystems/nsd.rst | 77 +++++++++++++++++++++++++++++++
 1 file changed, 77 insertions(+)
 create mode 100644 Documentation/filesystems/nsd.rst
Documentation/filesystems/nsd.rst new file +77 -0
new file mode 100644
index 0000000..a78018a
@@ -0,0 +1,77 @@
+.. SPDX-License-Identifier: GPL-2.0
+
+========================================
+Neural Storage Driver (NSD) - v1.0.0
+========================================
+
+Overview
+========
+NSD is a learning prefetcher for the Linux kernel page cache. It monitors
+I/O patterns via a hook in :c:func:`filemap_read` and prefetches pages
+ahead of the application using :c:func:`page_cache_sync_readahead`.
+
+Unlike the kernel existing readahead (fixed window), NSD builds
+a synaptic Markov chain model of access patterns at 4 KB region
+granularity. It detects sequential strides, repeating patterns, and
+learned transitions.
+
+Architecture
+============::
+
+    Application
+         |
+         v
+    filemap_read()  <-- NSD hook
+         |
+         +---> nsd_notify_read()
+                   |
+                   +---> Synaptic Table (Markov chain)
+                   |        |
+                   |        +---> Region hash + stride predictor
+                   |
+                   +---> Prefetch Worker
+                            |
+                            +---> page_cache_sync_readahead(WILLNEED)
+
+Sysfs Interface
+===============
+/sys/kernel/nsd/::
+
+  stats          Current statistics (hit rate, prefetch count, etc.)
+  observe_only   0=active, 1=observe-only (no prefetch)
+  penalty        Enable penalty weakening on waste
+  waste_track    Enable waste tracking
+
+Statistics fields::
+
+  prefetched    Total pages prefetched
+  used          Prefetched pages that were actually accessed
+  wasted        Prefetched pages never accessed
+  hit_rate_real Used / Prefetched ratio
+  stride_preds  Stride predictions made
+  chain_depth   Average chain prediction depth
+  synapse_ents  Current synapse table entries
+  ring_events   Pending ring buffer events
+
+Module Parameters
+=================
+  observe_only  Start in observe-only mode (default: false)
+  penalty       Enable penalty on waste (default: true)
+  waste_track   Enable waste tracking (default: false)
+
+Performance
+===========
+Tested on: x86_64, SATA SSD, kernel 7.0.0::
+
+  Workload                     Improvement
+  ---------------------------  -----------
+  SQLite FTS (4 GB table)      -18.8% query time
+  Sequential 64K buffered      +22.6% throughput
+  Random 4K buffered           +1.1% (noise)
+
+The prefetcher achieves 98% real hit rate on SSD workloads.
+
+See Also
+========
+Documentation/filesystems/fscache.rst
+Documentation/filesystems/squashfs.rst
\ No newline at end of file
Signature · 1 line
2.43.0
#4 lore raw
In reply to Ayhan Aydin

Hello,

Following up on this RFC submitted on 20260725. I understand maintainer bandwidth is limited, so no urgency implied - just making sure this didn't fall through the cracks.

For reference, the series adds an optional observation hook (CONFIG_NSD, default off, see PATCH 1/3) that does not bypass the existing ra_state / file_ra_struct machinery. All actual page insertion is still delegated to page_cache_sync_readahead(). Benchmarks (interleaved ON/OFF methodology, i.e. same-machine A/B with repeated runs, SQLite full-table scans and buffered sequential I/O) showed an 18-19% wall-time reduction and +22.6% throughput improvement respectively.

Happy to rework the approach, shrink the footprint, or re-parameterize the predictor if that would make review easier - just let me know what would help.

Full series and docs:
https://github.com/nsdprojectdev/NSD/tree/upstream-prep-v1

Thanks,
Ayhan

maintainer
#5 lore raw
Quoted 3 lines · Ayhan Aydin

Following up on this RFC submitted on 20260725. I understand maintainer bandwidth is limited, so no urgency implied - just making sure this didn't fall through the cracks.

It absolutely did. It would probably help to cc the page cache maintainers (Jan added) and the fsdevel people. You can find this information in the MAINTAINERS file.

Quoted 9 lines

For reference, the series adds an optional observation hook (CONFIG_NSD, default off, see PATCH 1/3) that does not bypass the existing ra_state / file_ra_struct machinery. All actual page insertion is still delegated to page_cache_sync_readahead(). Benchmarks (interleaved ON/OFF methodology, i.e. same-machine A/B with repeated runs, SQLite full-table scans and buffered sequential I/O) showed an 18-19% wall-time reduction and +22.6% throughput improvement respectively.

Quoted 6 lines

Happy to rework the approach, shrink the footprint, or re-parameterize the predictor if that would make review easier - just let me know what would help.

Full series and docs:
https://github.com/nsdprojectdev/NSD/tree/upstream-prep-v1

Let's call this a good proof of concept rather than a merge request ;-)

Architecturally, we're only hooking into the read path and ignoring the page fault path. Was that a deliberate choice?

I haven't spent the time to do any detailed analysis of your code, but it feels to me like we should be doing something more invasive and integrated. It would be nice to replace the existing mechanism of marking folios with PG_readahead, if that's possible. It'd be nice to be able to detect backward access patterns as well as forward access patterns.

Let's have a conversation about what you're trying to do, and see where we go next.

#6 lore raw

Hi Matthew,

Thanks for taking the time to look at this. Really appreciate the detailed feedback. Adding Jan and linux-fsdevel to this reply per your suggestion rather than waiting for the next round.

Quoted 2 lines

Architecturally, we're only hooking into the read path and ignoring the page fault path. Was that a deliberate choice?

Yes, deliberate, though I'd frame it as a starting point rather than a final position. The read path was attractive because hooking there let NSD observe and build its access-pattern model without adding latency to the caller's path. The benchmarks I mentioned (18-19% wall-time reduction, +22.6% throughput) are from that observer-only design. The page fault path is synchronous and latency-sensitive by nature, so I was cautious about touching it before the read-path approach had proven itself.

I don't think it needs to stay excluded, though. A lightweight, sampled hook (rather than firing on every fault) could let NSD extend its model to fault-driven access without sitting directly in the fault-critical path. Happy to prototype that and bring overhead numbers before proposing it as part of the series.

Quoted 2 lines

It would be nice to replace the existing mechanism of marking folios with PG_readahead, if that's possible.

This is the part I want to be most careful about, and I'd like your read on it. Right now NSD is purely an observer. It never touches ra_state/file_ra_struct or the PG_readahead flag itself; all actual page insertion is still delegated to the existing mechanism. That was a deliberate safety choice: with CONFIG_NSD off, or even with the module unloaded at runtime, the kernel's readahead behavior is completely unaffected. There's no state that depends on NSD having been loaded.

Moving to something that actually drives PG_readahead / the readahead window would make NSD a lot more useful, but I want to preserve that same guarantee: the kernel must always be able to fall back to its native behavior instantly and safely if NSD is removed, even mid-operation. Before I go down that path I'd like to talk through where the safest integration point is, whether that's advising the existing ondemand_readahead() logic rather than replacing it, or something else you'd suggest.

Quoted 2 lines

It'd be nice to be able to detect backward access patterns as well as forward access patterns.

Right now the predictor (Markov chain / frequency-recency based) is forward-only. It assumes roughly monotonic access. Backward detection is something I hadn't prioritized yet but agree it's a real gap. Happy to look at extending the per-inode context tracking to catch reverse sequential access as a next step.

Let me know which of these you'd want to see first. I could start with a writeup of the sampled fault-path hook, or with a proposal for how NSD could advise readahead decisions without owning the state. Whichever is more useful for moving this forward.

Thanks again,
Ayhan

maintainer
#7 lore raw
In reply to Matthew Wilcox
Quoted 9 lines · Matthew Wilcox
Quoted 8 lines · Ayhan Aydin

For reference, the series adds an optional observation hook (CONFIG_NSD, default off, see PATCH 1/3) that does not bypass the existing ra_state / file_ra_struct machinery. All actual page insertion is still delegated to page_cache_sync_readahead(). Benchmarks (interleaved ON/OFF methodology, i.e. same-machine A/B with repeated runs, SQLite full-table scans and buffered sequential I/O) showed an 18-19% wall-time reduction and +22.6% throughput improvement respectively.

I can see how SQLite table scans could be improved but I'm really surprised by the 64k sequential buffered read. That's basically what the current readahead logic is built for. So how is the sync readahead you trigger better than what generic async readahead does?

Honza

Signature · 2 lines
Jan Kara <[email protected]>
SUSE Labs, CR

A message that is not in the archive (sent off-list or not yet received): [email protected]

maintainer
#9 lore raw
Quoted 29 lines · Ayhan Aydin
Quoted 4 lines · Jan Kara

I can see how SQLite table scans could be improved but I'm really surprised by the 64k sequential buffered read. That's basically what the current readahead logic is built for. So how is the sync readahead you trigger better than what generic async readahead does?

Hi Honza,

Thanks for the careful question. This is exactly the workload the generic readahead was built for, so I was equally surprised at first. Let me share what we measured and how we explain it.

We reran the benchmarks with a strict A/B methodology: interleaved ON/OFF passes on the same machine, drop_caches before every pass, and the OFF state verified through the module's own counters (no prefetch activity during OFF passes).

Seq 64K buffered read (2 GB file, 3 interleaved passes):

OFF: 396, 400, 396 MB/s (avg 397 MB/s)
ON: 483, 507, 508 MB/s (avg 499 MB/s) -> +25.7%

To answer how the sync readahead we trigger can beat generic async readahead, we traced the IO requests actually submitted to the device (block_rq_issue, filtered to the reader task) in both modes:

OFF: 16,385 requests, median size 128 KiB (100% in the 64 to 128 KiB band)
ON: 8,195 requests, median size 256 KiB (100% above 128 KiB)

Quoted 7 lines

In the OFF case, the generic readahead keeps issuing fixed 128 KiB windows (the default read_ahead_kb) for the entire 2 GB run. It never grows beyond that. When NSD is enabled, it detects the sequential pattern and expands the readahead window to 256 KiB, then delegates the actual page insertion to page_cache_sync_readahead(). The kernel then issues half the requests, each twice as large, which is what this SSD prefers (about +27% throughput here).

Ah, OK, thanks for the details. So the default 128k read_ahead_kb is the culprit. We know it for a long time this default is too low for modern HW so most distro's actually tune this to 1m or similar in their default configurations. If you tune read_ahead_kb to 1m, does the difference for sequential read go away? And what about SQLite?

Quoted 3 lines

In other words, NSD does not bypass or reimplement the kernel machinery. It tunes the ra_state window that the existing readahead code then acts upon.

Yes, understood.

Honza

Signature · 2 lines
Jan Kara <[email protected]>
SUSE Labs, CR
#10 lore raw

Hi Honza, Hi Willy,

Thanks for the review and for the questions — they pushed us to go back and measure this properly. Since the last exchange we ran a full window-size matrix with complete latency and overhead numbers, and it answers directly what both of you asked. Let me start with the data.

These results come from our current in-development tree. We wanted to share them with you before pushing anything, so the tree referenced in the RFC (upstream-prep-v1, 2026-08-17) is still the earlier snapshot. Since that snapshot we made three changes that led to these numbers:

1. Jump handling — when a prediction lands outside the kernel's readahead window we now always issue WILLNEED|NOREUSE explicitly, instead of leaving the strategy branch to decide.
2. Kernel-window awareness — when the kernel's own readahead window is already >= 1MB the module detects this and completely silences itself (confirmed by its own counters), so it never competes with or disturbs a kernel window that is already sufficient.
3. Full instrumentation — per-run p50/p95/p99/p999 latency, per-pass usr/sys CPU overhead, and disk-I/O accounting.

We'll push the updated tree to GitHub once this discussion settles.

Full metrics matrix — methodology: interleaved ON/OFF on the same machine, drop_caches before every run, 3 runs per configuration, 6.2 GB SQLite database and an 8 GB sequential file. Disk I/O is byte-identical between ON and OFF in all 96 runs — NSD never issues extra I/O.

seq64 — 8 GB sequential file, 64k requests, n=131K/run:

kb | OFF avg ON avg diff | p50 OFF->ON | p99 OFF->ON |
overhead (usr+sys)

  128   | 22.02s   17.11s   -22%  | 50->23 us     | 812->805 us   | 5.94->4.33s
  256   | 17.08s   17.22s   +1%   | 20->15 us     | 824->1129 us  | 4.07->4.13s
  512   | 16.81s   16.96s   +1%   | 16->14 us     | 1092->1903 us | 4.24->3.60s
  1024  | 17.25s   17.03s   -1%   | 15->16 us     | 1903->1883 us | 3.67->3.74s

SQLite Q2 full-table scan — 6.2 GB:

  kb    | OFF avg  ON avg   diff  | overhead (usr+sys)
  128   | 24.51s   20.48s   -16%  | +0.95s
  256   | 20.05s   16.60s   -17%  | +1.26s
  512   | 15.31s   12.18s   -20%  | +1.06s
  1024  | 12.22s   12.09s   -1%   | +0.26s

random4k — 100k random 4k requests:

  kb    | OFF avg  ON avg   diff  | p99
  128   | 25.0s    25.5s    +2%   | ~0.98ms
  256   | 26.9s    26.0s    -3%   | ~0.99ms
  512   | 25.7s    25.5s    -1%   | ~0.98ms
  1024  | 25.4s    24.7s    -3%   | ~0.99ms

random_repeat — 100k offsets x 3 passes, n=300K:

  kb    | OFF avg  ON avg   diff  | p99
  128   | 26.8s    25.1s    -6%   | 0.39ms
  256   | 25.1s    24.0s    -4%   | 0.38ms
  512   | 24.5s    24.4s    0%    | 0.37ms
  1024  | 25.0s    24.7s    -1%   | 0.39ms

Honza, you asked whether the difference goes away at 1M — and yes, it does, for both workloads. The 128k default is the dominant factor; at 1M the kernel alone already reaches this SSD's bandwidth ceiling, and NSD recognises that and silences itself entirely at >= 1M windows.

But the 512k row is the one I'd really like your view on. The kernel with a 512k window alone (15.31s) trails the kernel with 1M (12.22s) by about 25%, yet NSD with a 512k window reaches 12.18s — the same throughput at half the window. Our block-layer traces show OFF@512k keeps issuing ~512k requests, so the device is not the limit. It looks like the kernel's window growth is capped at ra_pages, while the fadvise-driven expansion NSD triggers is not — which, incidentally, is why distros end up hand-tuning this value. Is that cap deliberate, for latency or cache-pollution control, or is there room for the growth policy to self-adapt?

Willy, on the architecture: hooking only vfs_read and skipping the fault path was a deliberate choice to bound the first iteration, but you're right that it's a gap — filemap_fault bypasses vfs_read entirely, so we're currently blind to mmap'd workloads. Hooking it with the same fprobe is the next step. On replacing the PG_readahead folio marking: the matrix above convinced us this is the right direction. The kernel's growth policy, not the device, is the real bottleneck at default settings, so we're moving toward a design that manages ra_state directly and measures its own waste — per-file tracking of consumed versus expired prefetches with adaptive aggressiveness, which is really just replacing the implicit assumptions behind PG_readahead marking with explicit measurement. Backward access patterns are already handled by the stride predictor (negative deltas, forward/backward counted separately); a dedicated backward-pattern benchmark will be added to the suite.

Two things we're still working on, for honesty: at 256-512k the sequential p99 regresses (~0.8ms -> ~1.1ms and ~1.1ms -> ~1.9ms) as the prefetch regions push the device queue — the usage-tracking work above targets exactly that. And the random_repeat gains (4-6% at 128-256k) suggest the predictor does help beyond what window size can fix; p95 there improves from 296 to 243 us.

Questions we'd value your input on:
1. Is fadvise-driven expansion beyond ra_pages acceptable as a mechanism, or should the growth policy itself change?
2. What would a minimal integrated design look like — replacing PG_readahead marking with direct ra_state control?
3. If we iterate: fault path first, or usage-tracking first?

Per your suggestion, we'll cc the page cache maintainers from MAINTAINERS on the next revision.

Best regards,
Ayhan

#11 lore raw

Just bumping this up in your inbox curious if you had a chance to look at the window-size matrix from the 19th, and what you think about the three questions at the end.

Happy to run more numbers if that helps.

Best,
Ayhan

20 Ağu 2026 Per 15:26 tarihinde ayhan aydın <[email protected]> şunu yazdı:

Quoted 117 lines

Hi Honza, Hi Willy,

Thanks for the review and for the questions — they pushed us to go back and measure this properly. Since the last exchange we ran a full window-size matrix with complete latency and overhead numbers, and it answers directly what both of you asked. Let me start with the data.

These results come from our current in-development tree. We wanted to share them with you before pushing anything, so the tree referenced in the RFC (upstream-prep-v1, 2026-08-17) is still the earlier snapshot. Since that snapshot we made three changes that led to these numbers:

1. Jump handling — when a prediction lands outside the kernel's readahead window we now always issue WILLNEED|NOREUSE explicitly, instead of leaving the strategy branch to decide.
2. Kernel-window awareness — when the kernel's own readahead window is already >= 1MB the module detects this and completely silences itself (confirmed by its own counters), so it never competes with or disturbs a kernel window that is already sufficient.
3. Full instrumentation — per-run p50/p95/p99/p999 latency, per-pass usr/sys CPU overhead, and disk-I/O accounting.

We'll push the updated tree to GitHub once this discussion settles.

Full metrics matrix — methodology: interleaved ON/OFF on the same machine, drop_caches before every run, 3 runs per configuration, 6.2 GB SQLite database and an 8 GB sequential file. Disk I/O is byte-identical between ON and OFF in all 96 runs — NSD never issues extra I/O.

seq64 — 8 GB sequential file, 64k requests, n=131K/run:

kb | OFF avg ON avg diff | p50 OFF->ON | p99 OFF->ON |
overhead (usr+sys)
128 | 22.02s 17.11s -22% | 50->23 us | 812->805 us |
5.94->4.33s
256 | 17.08s 17.22s +1% | 20->15 us | 824->1129 us |
4.07->4.13s
512 | 16.81s 16.96s +1% | 16->14 us | 1092->1903 us |
4.24->3.60s
1024 | 17.25s 17.03s -1% | 15->16 us | 1903->1883 us |
3.67->3.74s

SQLite Q2 full-table scan — 6.2 GB:

  kb    | OFF avg  ON avg   diff  | overhead (usr+sys)
  128   | 24.51s   20.48s   -16%  | +0.95s
  256   | 20.05s   16.60s   -17%  | +1.26s
  512   | 15.31s   12.18s   -20%  | +1.06s
  1024  | 12.22s   12.09s   -1%   | +0.26s

random4k — 100k random 4k requests:

  kb    | OFF avg  ON avg   diff  | p99
  128   | 25.0s    25.5s    +2%   | ~0.98ms
  256   | 26.9s    26.0s    -3%   | ~0.99ms
  512   | 25.7s    25.5s    -1%   | ~0.98ms
  1024  | 25.4s    24.7s    -3%   | ~0.99ms

random_repeat — 100k offsets x 3 passes, n=300K:

  kb    | OFF avg  ON avg   diff  | p99
  128   | 26.8s    25.1s    -6%   | 0.39ms
  256   | 25.1s    24.0s    -4%   | 0.38ms
  512   | 24.5s    24.4s    0%    | 0.37ms
  1024  | 25.0s    24.7s    -1%   | 0.39ms

Honza, you asked whether the difference goes away at 1M — and yes, it does, for both workloads. The 128k default is the dominant factor; at 1M the kernel alone already reaches this SSD's bandwidth ceiling, and NSD recognises that and silences itself entirely at >= 1M windows.

But the 512k row is the one I'd really like your view on. The kernel with a 512k window alone (15.31s) trails the kernel with 1M (12.22s) by about 25%, yet NSD with a 512k window reaches 12.18s — the same throughput at half the window. Our block-layer traces show OFF@512k keeps issuing ~512k requests, so the device is not the limit. It looks like the kernel's window growth is capped at ra_pages, while the fadvise-driven expansion NSD triggers is not — which, incidentally, is why distros end up hand-tuning this value. Is that cap deliberate, for latency or cache-pollution control, or is there room for the growth policy to self-adapt?

Willy, on the architecture: hooking only vfs_read and skipping the fault path was a deliberate choice to bound the first iteration, but you're right that it's a gap — filemap_fault bypasses vfs_read entirely, so we're currently blind to mmap'd workloads. Hooking it with the same fprobe is the next step. On replacing the PG_readahead folio marking: the matrix above convinced us this is the right direction. The kernel's growth policy, not the device, is the real bottleneck at default settings, so we're moving toward a design that manages ra_state directly and measures its own waste — per-file tracking of consumed versus expired prefetches with adaptive aggressiveness, which is really just replacing the implicit assumptions behind PG_readahead marking with explicit measurement. Backward access patterns are already handled by the stride predictor (negative deltas, forward/backward counted separately); a dedicated backward-pattern benchmark will be added to the suite.

Two things we're still working on, for honesty: at 256-512k the sequential p99 regresses (~0.8ms -> ~1.1ms and ~1.1ms -> ~1.9ms) as the prefetch regions push the device queue — the usage-tracking work above targets exactly that. And the random_repeat gains (4-6% at 128-256k) suggest the predictor does help beyond what window size can fix; p95 there improves from 296 to 243 us.

Questions we'd value your input on:
1. Is fadvise-driven expansion beyond ra_pages acceptable as a mechanism, or should the growth policy itself change?
2. What would a minimal integrated design look like — replacing PG_readahead marking with direct ra_state control?
3. If we iterate: fault path first, or usage-tracking first?

Per your suggestion, we'll cc the page cache maintainers from MAINTAINERS on the next revision.

Best regards,
Ayhan

maintainer
#12 lore raw
In reply to ayhan aydın

Hi Ayhan,

I'm sorry for a bit delayed reply.

Quoted 10 lines · ayhan aydın

Thanks for the review and for the questions — they pushed us to go back and measure this properly. Since the last exchange we ran a full window-size matrix with complete latency and overhead numbers, and it answers directly what both of you asked. Let me start with the data.

These results come from our current in-development tree. We wanted to share them with you before pushing anything, so the tree referenced in the RFC (upstream-prep-v1, 2026-08-17) is still the earlier snapshot. Since that snapshot we made three changes that led to these numbers:

Quoted 7 lines

1. Jump handling — when a prediction lands outside the kernel's readahead window we now always issue WILLNEED|NOREUSE explicitly, instead of leaving the strategy branch to decide.
2. Kernel-window awareness — when the kernel's own readahead window is already >= 1MB the module detects this and completely silences itself (confirmed by its own counters), so it never competes with or disturbs a kernel window that is already sufficient.

Err, ok. I guess I'm somewhat missing the intended purpose of your changes then. Is your idea that if read_ahead_kb (i.e., maximum allowed readahead) is set too low, your algorithm will fix it up?

How I was understanding your intention is that your algorithm aims to provide a better guess for appropriate readahead given the workload *within the bounds set by read_ahead_kb*. Because read_ahead_kb is there for sysadmin to allow restricting readahead (e.g. to avoid excessive memory consumption from readahead).

Quoted 10 lines

3. Full instrumentation — per-run p50/p95/p99/p999 latency, per-pass usr/sys CPU overhead, and disk-I/O accounting.

We'll push the updated tree to GitHub once this discussion settles.

Full metrics matrix — methodology: interleaved ON/OFF on the same machine, drop_caches before every run, 3 runs per configuration, 6.2 GB SQLite database and an 8 GB sequential file. Disk I/O is byte-identical between ON and OFF in all 96 runs — NSD never issues extra I/O.

Quoted 8 lines

seq64 — 8 GB sequential file, 64k requests, n=131K/run:

kb | OFF avg ON avg diff | p50 OFF->ON | p99 OFF->ON |
overhead (usr+sys)

  128   | 22.02s   17.11s   -22%  | 50->23 us     | 812->805 us   | 5.94->4.33s
  256   | 17.08s   17.22s   +1%   | 20->15 us     | 824->1129 us  | 4.07->4.13s
  512   | 16.81s   16.96s   +1%   | 16->14 us     | 1092->1903 us | 4.24->3.60s
  1024  | 17.25s   17.03s   -1%   | 15->16 us     | 1903->1883 us | 3.67->3.74s

OK, so for read_ahead_kb >= 256k the difference disappears with your disk.

Quoted 7 lines

SQLite Q2 full-table scan — 6.2 GB:

  kb    | OFF avg  ON avg   diff  | overhead (usr+sys)
  128   | 24.51s   20.48s   -16%  | +0.95s
  256   | 20.05s   16.60s   -17%  | +1.26s
  512   | 15.31s   12.18s   -20%  | +1.06s
  1024  | 12.22s   12.09s   -1%   | +0.26s

Interesting that here the difference disappears only with read_ahead_kb = 1024k. Isn't it because based on 2. above your algorithm disabled itself? Also how come when your algorithm is enabled, results were still improving as you were increasing read_ahead_kb?

Quoted 8 lines

random4k — 100k random 4k requests:

  kb    | OFF avg  ON avg   diff  | p99
  128   | 25.0s    25.5s    +2%   | ~0.98ms
  256   | 26.9s    26.0s    -3%   | ~0.99ms
  512   | 25.7s    25.5s    -1%   | ~0.98ms
  1024  | 25.4s    24.7s    -3%   | ~0.99ms
Quoted 7 lines

random_repeat — 100k offsets x 3 passes, n=300K:

  kb    | OFF avg  ON avg   diff  | p99
  128   | 26.8s    25.1s    -6%   | 0.39ms
  256   | 25.1s    24.0s    -4%   | 0.38ms
  512   | 24.5s    24.4s    0%    | 0.37ms
  1024  | 25.0s    24.7s    -1%   | 0.39ms

I'd say no matterial difference here with read_ahead_kb >= 256k

Quoted 5 lines

Honza, you asked whether the difference goes away at 1M — and yes, it does, for both workloads. The 128k default is the dominant factor; at 1M the kernel alone already reaches this SSD's bandwidth ceiling, and NSD recognises that and silences itself entirely at >= 1M windows.

Quoted 10 lines

But the 512k row is the one I'd really like your view on. The kernel with a 512k window alone (15.31s) trails the kernel with 1M (12.22s) by about 25%, yet NSD with a 512k window reaches 12.18s — the same throughput at half the window. Our block-layer traces show OFF@512k keeps issuing ~512k requests, so the device is not the limit. It looks like the kernel's window growth is capped at ra_pages, while the fadvise-driven expansion NSD triggers is not — which, incidentally, is why distros end up hand-tuning this value. Is that cap deliberate, for latency or cache-pollution control, or is there room for the growth policy to self-adapt?

I'm not sure I correctly understand the question so please rephrase it if I answer something else but it is deliberate, that explicit readahead (e.g. through fadvise(2) but also if you just do large read(2)) is not bound by read_ahead_kb.

Quoted 7 lines

Willy, on the architecture: hooking only vfs_read and skipping the fault path was a deliberate choice to bound the first iteration, but you're right that it's a gap — filemap_fault bypasses vfs_read entirely, so we're currently blind to mmap'd workloads. Hooking it with the same fprobe is the next step. On replacing the PG_readahead folio marking: the matrix above convinced us this is the right direction. The kernel's growth policy, not the device, is the real

Quoted 8 lines

bottleneck at default settings, so we're moving toward a design that manages ra_state directly and measures its own waste — per-file tracking of consumed versus expired prefetches with adaptive aggressiveness, which is really just replacing the implicit assumptions behind PG_readahead marking with explicit measurement. Backward access patterns are already handled by the stride predictor (negative deltas, forward/backward counted separately); a dedicated backward-pattern benchmark will be added to the suite.

Just one note here: I wouldn't focus too much on default settings because most people tune them to different values with udev rules. What is interesting is whether your algorithm beats current readahead algorithm with proper read_ahead_kb for the device (i.e., usually 1m these days).

Quoted 10 lines

Two things we're still working on, for honesty: at 256-512k the sequential p99 regresses (~0.8ms -> ~1.1ms and ~1.1ms -> ~1.9ms) as the prefetch regions push the device queue — the usage-tracking work above targets exactly that. And the random_repeat gains (4-6% at 128-256k) suggest the predictor does help beyond what window size can fix; p95 there improves from 296 to 243 us.

Questions we'd value your input on:
1. Is fadvise-driven expansion beyond ra_pages acceptable as a mechanism, or should the growth policy itself change?

Not sure what Matthew thinks but my opinion is that automated readahead (regardless of algorithm used for deciding it) simply should be limited to read_ahead_kb. That is the long-term Linux behavior and that is the knob sysadmin has to constrain readahead algorithm if he wishes and we should not break it.

Quoted 2 lines

2. What would a minimal integrated design look like — replacing PG_readahead marking with direct ra_state control?

I'll defer this to Matthew since I'm actually not sure how he imagined this to work.

Quoted 1 line

3. If we iterate: fault path first, or usage-tracking first?

I don't have a strong preference here :)

Honza

Signature · 2 lines
Jan Kara <[email protected]>
SUSE Labs, CR
#13 lore raw

Hi Honza, hi Willy,

First, my Aug 20 follow-up bounced on the HTML part. My mistake, resending as plain text. Below is that content updated with six more weeks of measurement. Two self corrections first, before any numbers.

What changed since the RFC (same out of tree module):
Automated prefetch never exceeds ra_pages now. Overhangs get trimmed or dropped, all counted. The only exception is our own measured willneed ranges up to io_pages. That follows Ming Lei's RFC direction and the MADV_POPULATE precedent. It is toggleable, Mod A means strict cap.

Fault path first, as you asked in Q3. filemap_fault hook observes, then prefetches with depth capped at 2 and bounded by the cap. One more thing on this: the fault path stands down explicitly at 1M windows and up. There is a straight s_bdi->ra_pages check in nsd_process(). The
parity we see at 256K and 512K is a different thing. Our code still fires there. The kernel just catches up on its own at those sizes.

A sleeping in atomic bug in our fast path got found through a stack trace and fixed. vfs_fadvise was called from fprobe context. It now goes through a workqueue.

A len==0 fadvise footgun got found through our own counters. Len 0 means to end of file, so those sends preloaded whole files. All our earlier big mmap and SQLite speedups traced back to it. Retracted. Sends with len 0 are now dropped and counted.

Narrowed claims after all that. Interleaved A/B, drop_caches before every run, checksums verified, 500+ runs in total:

sparse mmap scan, about 64KB stride, 512MB to 20GB files, 128K window,
SSD: ON ~47s vs OFF ~88s median over 30+30 reps, no overlap.
The threshold lines up exactly with FAULT_AROUND_ORDER=4 (65536B). Below it the kernel fault around covers the fault by itself. Above it, it does not.
same setup at 256K, 512K, 1024K windows: parity, kernel catches up. dense mmap, rand 4K, seq read, SQLite, THP, and HDD sparse mmap:
parity everywhere. The early small HDD lean got remeasured with current code and traced to the same len 0 accident, retracted too. No workload regresses. dmesg tracked throughout, no new warnings.

So the scope is sparse mmap scans at default size windows on SSD. That is where the fault path underprovisions while the read path is already saturated. Dense, random, 1M tuned and HDD cases are parity by measurement.
Separately, one thing that might be useful here too: p99 tail latency is about 4x worse at 1M than at 128K regardless of NSD state. Another practical reason to keep windows small.

Open questions, updated:
Q1, fadvise beyond ra_pages: we stopped doing it silently. Only
measured willneed ranges up to io_pages, and that can be turned off. Acceptable shape?
Q2, ra_state integration: we prototyped window steering from the
module. The kernel keeps our window but wall clock does not move because there is just not enough volume from outside. Real integration needs in kernel changes, so we drafted a minimal one:
2 stream slots plus stride state in file_ra_state, every window bounded by ra_pages, read path only. Want me to post it separately for direction feedback before any boot testing?
Q3: fault path first as described above, with timely versus correct
accounting running underneath.

For Willy: backward patterns get detected near perfectly (strides with negative deltas, counted separately) but they do not move the wall on SATA SSD, so throttled now. Fault path is covered as you asked. PG_readahead replacement stays an in kernel question as above.

Full data and the retraction notes are in the tree. Happy to run any counter matrix you ask for.

Thanks,
Ayhan

#14 lore raw

Can you please reply with something that isn't copied straight out of an LLM? And, ideally, add the Assisted-by: LLM's where necessary.

Quoted 75 lines · ayhan aydın

Hi Honza, hi Willy,

First, my Aug 20 follow-up bounced on the HTML part. My mistake, resending as plain text. Below is that content updated with six more weeks of measurement. Two self corrections first, before any numbers.

What changed since the RFC (same out of tree module):
Automated prefetch never exceeds ra_pages now. Overhangs get trimmed or dropped, all counted. The only exception is our own measured willneed ranges up to io_pages. That follows Ming Lei's RFC direction and the MADV_POPULATE precedent. It is toggleable, Mod A means strict cap.

Fault path first, as you asked in Q3. filemap_fault hook observes, then prefetches with depth capped at 2 and bounded by the cap. One more thing on this: the fault path stands down explicitly at 1M windows and up. There is a straight s_bdi->ra_pages check in nsd_process(). The
parity we see at 256K and 512K is a different thing. Our code still fires there. The kernel just catches up on its own at those sizes.

A sleeping in atomic bug in our fast path got found through a stack trace and fixed. vfs_fadvise was called from fprobe context. It now goes through a workqueue.

A len==0 fadvise footgun got found through our own counters. Len 0 means to end of file, so those sends preloaded whole files. All our earlier big mmap and SQLite speedups traced back to it. Retracted. Sends with len 0 are now dropped and counted.

Narrowed claims after all that. Interleaved A/B, drop_caches before every run, checksums verified, 500+ runs in total:

sparse mmap scan, about 64KB stride, 512MB to 20GB files, 128K window,
SSD: ON ~47s vs OFF ~88s median over 30+30 reps, no overlap.
The threshold lines up exactly with FAULT_AROUND_ORDER=4 (65536B). Below it the kernel fault around covers the fault by itself. Above it, it does not.
same setup at 256K, 512K, 1024K windows: parity, kernel catches up. dense mmap, rand 4K, seq read, SQLite, THP, and HDD sparse mmap:
parity everywhere. The early small HDD lean got remeasured with current code and traced to the same len 0 accident, retracted too. No workload regresses. dmesg tracked throughout, no new warnings.

So the scope is sparse mmap scans at default size windows on SSD. That is where the fault path underprovisions while the read path is already saturated. Dense, random, 1M tuned and HDD cases are parity by measurement.
Separately, one thing that might be useful here too: p99 tail latency is about 4x worse at 1M than at 128K regardless of NSD state. Another practical reason to keep windows small.

Open questions, updated:
Q1, fadvise beyond ra_pages: we stopped doing it silently. Only
measured willneed ranges up to io_pages, and that can be turned off. Acceptable shape?
Q2, ra_state integration: we prototyped window steering from the
module. The kernel keeps our window but wall clock does not move because there is just not enough volume from outside. Real integration needs in kernel changes, so we drafted a minimal one:
2 stream slots plus stride state in file_ra_state, every window bounded by ra_pages, read path only. Want me to post it separately for direction feedback before any boot testing?
Q3: fault path first as described above, with timely versus correct
accounting running underneath.

For Willy: backward patterns get detected near perfectly (strides with negative deltas, counted separately) but they do not move the wall on SATA SSD, so throttled now. Fault path is covered as you asked. PG_readahead replacement stays an in kernel question as above.

Full data and the retraction notes are in the tree. Happy to run any counter matrix you ask for.

Thanks,
Ayhan

Signature · 1 line
Pedro
#15 lore raw

Thanks for the heads up, Pedro, fair point. I had an LLM help draft these mails and it shows. I will write them myself from here on, and noted on Assisted by, will add it wherever one was involved.

#16 lore raw

Hi Honza, Willy,

Just checking if the Sep 20 note got buried. No new numbers from my side, same tree.

The two things I am unsure about:

1. Is the capped shape OK - ra_pages bounded, overhangs trimmed/dropped and counted, only measured willneed up to io_pages and that off by default (Mod A strict)?

2. Do you want the small ra_state bit (2 slots + stride, read path only, all windows bounded) posted separately for direction before I test it further?

Thanks,
Ayhan

Assisted-by LLM (English draft help)
#17 lore raw
In reply to Jan Kara

Hi Honza, Hi Willy,

Just bumping this up, curious if you had a chance to look at the window-size matrix from the 19th, and what you think about the three questions at the end.

Happy to run more numbers if that helps.

Best,
Ayhan