The Page Cache

The page cache is the kernel’s in-memory copy of file contents. It holds frames of file data, indexed by file and by page number within the file. read copies from these frames and write copies into them. The disk is involved only when a page is missing from the cache, or when a changed page is written back.

In this chapter, we will learn when file data moves between the cache and the disk. We will first measure with cachefacts how many pages of a file are cached after writes and reads of different kinds. Then we will write pagecache, a model with readahead, dirty pages and eviction, and compare its behaviour with the measurements.

Why a cache

A disk request takes far longer than a copy in memory: roughly 100 microseconds for a fast solid-state drive against well under 1 microsecond for a page that is already in memory. The kernel therefore keeps file pages in frames that no process currently needs and serves file operations from them.

A dirty page is newer than the disk. The kernel writes dirty pages to the disk in the background, a process called writeback, typically within 30 seconds. write therefore returns before the data is on the disk, and data written shortly before a power failure can be lost. A program that needs the data to be durable calls fsync, which returns when the file’s dirty pages have reached the disk.

The cache uses memory that is otherwise free, and gives it up when processes need it. A clean page can be discarded at any time, because the disk has the same contents. A dirty page has to be written first.

One read, step by step

A process calls read(fd, buf, 4096) on a file whose offset is 8192.

1. The kernel finds the struct file for the descriptor and, through it, the inode of the file (chapter 2).
2. It divides the offset by the page size. Offset 8192 is the start of page number 2 of the file.
3. It looks page 2 up in the cache of this file. Each inode has its own index of cached pages.
4. If the page is there, the kernel copies 4096 bytes from it to buf, advances the offset, and returns. No request reaches the disk.
5. If the page is missing, the kernel allocates a frame, asks the file system to read the block from the disk into it, and inserts the frame in the index. The process sleeps until the disk has answered. Then step 4 follows.

A read that finds its page is a cache hit, and one that has to go to the disk is a cache miss. The page fault of chapter 7 that reads a page of a mapped file takes the same path from step 3 on, and the frame it maps is the frame in the cache. read and mmap therefore see the same copy of a file.

The kernel’s structure

The index of cached pages of a file is a struct address_space, embedded in the inode and reached through inode->i_mapping. This is the definition in include/linux/fs.h of Linux 5.15, reduced to the fields we use.

struct address_space {
        struct inode *host;                    /* the file these pages belong to */
        struct xarray i_pages;                 /* page number -> struct page */
        unsigned long nrpages;                 /* number of cached pages */
        pgoff_t writeback_index;               /* where writeback continues */
        const struct address_space_operations *a_ops;  /* read and write a page */
        /* ... */
};

Each cached frame is a struct page (chapter 7) whose mapping field points back to this address_space and whose index is its page number. Bits in its flags record its state: PG_uptodate when its contents are valid, PG_dirty when it has been written and the disk has not, and PG_writeback while it is being written to the disk.

How much memory is cache

The page cache uses whatever memory nothing else needs. On our machine, with 16 GB of memory:

$ free -m
               total        used        free      shared  buff/cache   available
Mem:           15655        8881         300         294        6473        6197
$ grep -E 'Cached|Dirty|Writeback:' /proc/meminfo
Cached:          5760296 kB
Dirty:              2488 kB
Writeback:             0 kB

Only 300 MB is free, and that is the normal state of a healthy system. 6473 MB is buff/cache, mostly page cache, and the kernel can take it back at any moment, which is why the available column, 6197 MB, is the number that says how much memory a new program could get. Dirty is the part of the cache that has not been written to disk yet, 2.5 MB at that moment.

Measuring the cache

cachefacts counts the cached pages of a file with the fincore utility from util-linux. It uses golang.org/x/sys/unix in Go and the nix crate with the fs feature in Rust, for posix_fadvise.

$ cargo new cachefacts
$ cargo add -p cachefacts nix --features fs

The file must be on a disk-backed file system for the measurement to mean anything. On this machine /tmp is on ext4. drop makes the file’s pages clean with fsync and then asks the kernel to discard them with the advice POSIX_FADV_DONTNEED.

Listing 8.1 The imports of cachefacts, in Go. code/go/cachefacts/main.go

import (
	"fmt"
	"io"
	"log"
	"os"
	"os/exec"
	"path/filepath"
	"strconv"
	"strings"

	"golang.org/x/sys/unix"
)

Listing 8.2 The imports of cachefacts, in Rust. code/rust/cachefacts/src/main.rs

use std::fs::{self, File, OpenOptions};
use std::io::{self, Write};
use std::os::unix::fs::FileExt;
use std::path::Path;
use std::process::Command;

use nix::fcntl::{PosixFadviseAdvice, posix_fadvise};

Listing 8.3 Counting and dropping the cached pages of a file, in Go. code/go/cachefacts/main.go

const pageSize = 4096

// cached returns the number of pages of a file that are in the page cache,
// as reported by the fincore utility.
func cached(path string) (int, error) {
	text, err := exec.Command("fincore", "--noheadings", "--output", "PAGES", path).Output()

	if err != nil {
		return 0, err
	}

	return strconv.Atoi(strings.TrimSpace(string(text)))
}

// report prints a step and the number of cached pages after it.
func report(step, path string) error {
	pages, err := cached(path)

	if err != nil {
		return err
	}

	fmt.Printf("%-38s cached pages: %d\n", step+":", pages)

	return nil
}

// drop writes the file's dirty pages to disk and asks the kernel to remove
// the file's pages from the cache.
func drop(file *os.File) error {
	if err := file.Sync(); err != nil {
		return err
	}

	return unix.Fadvise(int(file.Fd()), 0, 0, unix.FADV_DONTNEED)
}

Listing 8.4 Counting and dropping the cached pages of a file, in Rust. code/rust/cachefacts/src/main.rs

const PAGE_SIZE: usize = 4096;

/// Returns the number of pages of a file that are in the page cache, as
/// reported by the fincore utility.
fn cached(path: &Path) -> io::Result<usize> {
    let output = Command::new("fincore")
        .args(["--noheadings", "--output", "PAGES"])
        .arg(path)
        .output()?;

    String::from_utf8_lossy(&output.stdout)
        .trim()
        .parse()
        .map_err(|_| io::ErrorKind::InvalidData.into())
}

/// Prints a step and the number of cached pages after it.
fn report(step: &str, path: &Path) -> io::Result<()> {
    let pages = cached(path)?;
    println!("{:<38} cached pages: {pages}", format!("{step}:"));

    Ok(())
}

/// Writes the file's dirty pages to disk and asks the kernel to remove the
/// file's pages from the cache.
fn drop_pages(file: &File) -> io::Result<()> {
    file.sync_all()?;
    posix_fadvise(file, 0, 0, PosixFadviseAdvice::POSIX_FADV_DONTNEED)?;

    Ok(())
}

run writes 64 pages, drops them, reads 1 byte, reads the whole file, drops the pages again, and reads 1 byte after giving the advice POSIX_FADV_RANDOM.

Listing 8.5 Writes and reads of a file of 64 pages, in Go. code/go/cachefacts/main.go

// run writes a file of 64 pages and reads it in 3 ways, dropping the cached
// pages between the steps.
func run(path string) error {
	file, err := os.OpenFile(path, os.O_RDWR|os.O_CREATE, 0o644)

	if err != nil {
		return err
	}

	defer file.Close()

	if _, err := file.Write(make([]byte, 64*pageSize)); err != nil {
		return err
	}

	if err := report("write of 64 pages", path); err != nil {
		return err
	}

	if err := drop(file); err != nil {
		return err
	}

	if err := report("fsync, then FADV_DONTNEED", path); err != nil {
		return err
	}

	one := make([]byte, 1)

	if _, err := file.ReadAt(one, 0); err != nil {
		return err
	}

	if err := report("read of 1 byte at offset 0", path); err != nil {
		return err
	}

	if _, err := io.Copy(io.Discard, io.NewSectionReader(file, 0, 64*pageSize)); err != nil {
		return err
	}

	if err := report("read of the whole file", path); err != nil {
		return err
	}

	if err := drop(file); err != nil {
		return err
	}

	if err := unix.Fadvise(int(file.Fd()), 0, 0, unix.FADV_RANDOM); err != nil {
		return err
	}

	if _, err := file.ReadAt(one, 0); err != nil {
		return err
	}

	return report("dropped, FADV_RANDOM, read of 1 byte", path)
}

Listing 8.6 Writes and reads of a file of 64 pages, in Rust. code/rust/cachefacts/src/main.rs

/// Writes a file of 64 pages and reads it in 3 ways, dropping the cached
/// pages between the steps.
fn run(path: &Path) -> io::Result<()> {
    let mut file = OpenOptions::new()
        .read(true)
        .write(true)
        .create(true)
        .truncate(true)
        .open(path)?;

    file.write_all(&vec![0u8; 64 * PAGE_SIZE])?;
    report("write of 64 pages", path)?;

    drop_pages(&file)?;
    report("fsync, then FADV_DONTNEED", path)?;

    let mut one = [0u8; 1];

    file.read_exact_at(&mut one, 0)?;
    report("read of 1 byte at offset 0", path)?;

    let mut whole = vec![0u8; 64 * PAGE_SIZE];

    file.read_exact_at(&mut whole, 0)?;
    report("read of the whole file", path)?;

    drop_pages(&file)?;
    posix_fadvise(&file, 0, 0, PosixFadviseAdvice::POSIX_FADV_RANDOM)?;

    file.read_exact_at(&mut one, 0)?;
    report("dropped, FADV_RANDOM, read of 1 byte", path)
}

write of 64 pages:                     cached pages: 64
fsync, then FADV_DONTNEED:             cached pages: 0
read of 1 byte at offset 0:            cached pages: 4
read of the whole file:                cached pages: 64
dropped, FADV_RANDOM, read of 1 byte:  cached pages: 1

Readahead

Most files are read from start to end. A disk serves 1 large request much faster than many small ones, so the kernel assumes sequential access and reads more pages than were asked for. This is readahead. The first read at the start of a file loads a small window, 4 pages in the measurement. While the reads continue in order, each window is double the size of the last, up to a limit, which is 32 pages on this machine (/sys/block/<device>/queue/read_ahead_kb is 128). A read at an unrelated position starts again with a small window.

A program that knows its access pattern can say so with posix_fadvise. POSIX_FADV_RANDOM turns readahead off for the descriptor, and POSIX_FADV_SEQUENTIAL doubles the limit.

Modelling the cache

The model reduces the contents of a page to 1 byte and counts requests to the disk.

Listing 8.7 The imports of pagecache, in Go. code/go/pagecache/main.go

import (
	"fmt"
	"slices"
)

Listing 8.8 The imports of pagecache, in Rust. code/rust/pagecache/src/main.rs

use std::collections::BTreeMap;

Listing 8.9 The disk, a cached page, and the cache, in Go. code/go/pagecache/main.go

// maxWindow is the largest number of pages one disk request reads ahead.
const maxWindow = 8

// A disk holds the pages of a file and counts the requests made to it. The
// contents of a page are reduced to one byte.
type disk struct {
	pages    []byte
	requests int
	written  int
}

// A page is a cached copy of a disk page. dirty is set when the copy has
// been written and the disk has not. used is the time of the last access.
type page struct {
	value byte
	dirty bool
	used  int
}

// A cache maps page numbers to cached pages. next is the page that a
// sequential reader would ask for next, and window is the current number of
// pages to read ahead.
type cache struct {
	disk     *disk
	pages    map[int]*page
	capacity int
	clock    int
	next     int
	window   int
}

func newCache(d *disk, capacity int) *cache {
	return &cache{disk: d, pages: map[int]*page{}, capacity: capacity}
}

Listing 8.10 The disk, a cached page, and the cache, in Rust. code/rust/pagecache/src/main.rs

/// The largest number of pages one disk request reads ahead.
const MAX_WINDOW: usize = 8;

/// Holds the pages of a file and counts the requests made to it. The contents
/// of a page are reduced to one byte.
struct Disk {
    pages: Vec<u8>,
    requests: usize,
    written: usize,
}

impl Disk {
    fn new() -> Disk {
        Disk {
            pages: vec![b'-'; 16],
            requests: 0,
            written: 0,
        }
    }
}

/// A cached copy of a disk page. `dirty` is set when the copy has been
/// written and the disk has not. `used` is the time of the last access.
#[derive(Default)]
struct Page {
    value: u8,
    dirty: bool,
    used: usize,
}

/// Maps page numbers to cached pages. `next` is the page that a sequential
/// reader would ask for next, and `window` is the current number of pages to
/// read ahead.
struct Cache {
    disk: Disk,
    pages: BTreeMap<usize, Page>,
    capacity: usize,
    clock: usize,
    next: usize,
    window: usize,
}

impl Cache {
    fn new(capacity: usize) -> Cache {
        Cache {
            disk: Disk::new(),
            pages: BTreeMap::new(),
            capacity,
            clock: 0,
            next: 0,
            window: 0,
        }
    }
}

read implements the lookup and the readahead rule. next is the page number that would follow the previous read. A miss at that position doubles the window, and a miss anywhere else sets it to 1 page.

Listing 8.11 Reading through the cache, with readahead, in Go. code/go/pagecache/main.go

// read returns the contents of a page. A page that is cached costs no disk
// request. For a page that is missing, read makes one request for a window
// of pages. The window doubles while the reads are sequential and returns
// to 1 page when they are not.
func (c *cache) read(index int) byte {
	if _, hit := c.pages[index]; !hit {
		if index == c.next {
			c.window = min(2*max(c.window, 1), maxWindow)
		} else {
			c.window = 1
		}

		c.load(index, c.window)
	}

	c.next = index + 1

	return c.touch(index).value
}

// load reads count pages starting at index from the disk in one request.
func (c *cache) load(index, count int) {
	c.disk.requests++

	for i := index; i < min(index+count, len(c.disk.pages)); i++ {
		if _, hit := c.pages[i]; !hit {
			c.insert(i, &page{value: c.disk.pages[i]})
		}
	}
}

// touch records an access to a cached page and returns the page.
func (c *cache) touch(index int) *page {
	c.clock++
	c.pages[index].used = c.clock

	return c.pages[index]
}

Listing 8.12 Reading through the cache, with readahead, in Rust. code/rust/pagecache/src/main.rs

impl Cache {
    /// Returns the contents of a page. A page that is cached costs no disk
    /// request. For a page that is missing, `read` makes one request for a
    /// window of pages. The window doubles while the reads are sequential and
    /// returns to 1 page when they are not.
    fn read(&mut self, index: usize) -> u8 {
        if !self.pages.contains_key(&index) {
            if index == self.next {
                self.window = (2 * self.window.max(1)).min(MAX_WINDOW);
            } else {
                self.window = 1;
            }

            self.load(index, self.window);
        }

        self.next = index + 1;

        self.touch(index).value
    }

    /// Reads `count` pages starting at `index` from the disk in one request.
    fn load(&mut self, index: usize, count: usize) {
        self.disk.requests += 1;

        for i in index..(index + count).min(self.disk.pages.len()) {
            if !self.pages.contains_key(&i) {
                let value = self.disk.pages[i];

                self.insert(i, value);
            }
        }
    }

    /// Records an access to a page and returns the page. A page that is not
    /// cached is created empty.
    fn touch(&mut self, index: usize) -> &mut Page {
        self.clock += 1;

        let page = self.pages.entry(index).or_default();
        page.used = self.clock;

        page
    }
}

write touches only the cache. sync is the model’s fsync.

Listing 8.13 Writing, and writing back, in Go. code/go/pagecache/main.go

// write changes a page in the cache and marks it dirty. It makes no disk
// request.
func (c *cache) write(index int, value byte) {
	if _, hit := c.pages[index]; !hit {
		c.insert(index, &page{})
	}

	p := c.touch(index)
	p.value, p.dirty = value, true
}

// sync writes every dirty page to the disk and returns the number written.
func (c *cache) sync() int {
	before := c.disk.written

	for index, p := range c.pages {
		c.clean(index, p)
	}

	return c.disk.written - before
}

// clean writes one page to the disk if it is dirty.
func (c *cache) clean(index int, p *page) {
	if p.dirty {
		c.disk.pages[index] = p.value
		c.disk.written++
		p.dirty = false
	}
}

Listing 8.14 Writing, and writing back, in Rust. code/rust/pagecache/src/main.rs

impl Cache {
    /// Changes a page in the cache and marks it dirty. It makes no disk
    /// request.
    fn write(&mut self, index: usize, value: u8) {
        if !self.pages.contains_key(&index) {
            self.insert(index, 0);
        }

        let page = self.touch(index);
        page.value = value;
        page.dirty = true;
    }

    /// Writes every dirty page to the disk and returns the number written.
    fn sync(&mut self) -> usize {
        let before = self.disk.written;

        for (&index, page) in &mut self.pages {
            clean(&mut self.disk, index, page);
        }

        self.disk.written - before
    }
}

/// Writes one page to the disk if it is dirty.
fn clean(disk: &mut Disk, index: usize, page: &mut Page) {
    if page.dirty {
        disk.pages[index] = page.value;
        disk.written += 1;
        page.dirty = false;
    }
}

insert enforces the capacity. It evicts the page with the oldest access time, which is the least recently used policy: a page that has not been used for the longest time is the least likely to be needed soon. The kernel approximates this policy with 2 lists of pages, active and inactive, and avoids keeping an exact access time for each page.

Listing 8.15 Inserting a page, and evicting the least recently used, in Go. code/go/pagecache/main.go

// insert adds a page to the cache. When the cache is full it first evicts
// the page whose last access is the oldest. A dirty page is written to the
// disk before it is removed.
func (c *cache) insert(index int, p *page) {
	if len(c.pages) == c.capacity {
		oldest := -1

		for i, candidate := range c.pages {
			if oldest == -1 || candidate.used < c.pages[oldest].used {
				oldest = i
			}
		}

		c.clean(oldest, c.pages[oldest])
		delete(c.pages, oldest)
	}

	c.clock++
	p.used = c.clock
	c.pages[index] = p
}

// held returns the numbers of the cached pages in increasing order.
func (c *cache) held() []int {
	held := make([]int, 0, len(c.pages))

	for index := range c.pages {
		held = append(held, index)
	}

	slices.Sort(held)

	return held
}

Listing 8.16 Inserting a page, and evicting the least recently used, in Rust. code/rust/pagecache/src/main.rs

impl Cache {
    /// Adds a page to the cache. When the cache is full it first evicts the
    /// page whose last access is the oldest. A dirty page is written to the
    /// disk before it is removed.
    fn insert(&mut self, index: usize, value: u8) {
        if self.pages.len() == self.capacity {
            let oldest = self
                .pages
                .iter()
                .min_by_key(|(_, page)| page.used)
                .map(|(&index, _)| index);

            if let Some(oldest) = oldest
                && let Some(mut page) = self.pages.remove(&oldest)
            {
                clean(&mut self.disk, oldest, &mut page);
            }
        }

        self.clock += 1;

        let page = Page {
            value,
            dirty: false,
            used: self.clock,
        };

        self.pages.insert(index, page);
    }

    /// Returns the numbers of the cached pages in increasing order.
    fn held(&self) -> Vec<usize> {
        self.pages.keys().copied().collect()
    }
}

Listing 8.17 The trace, in Go. code/go/pagecache/main.go

// requests reads the given pages through a new cache and returns the number
// of disk requests.
func requests(order []int) int {
	d := &disk{pages: make([]byte, 16)}
	c := newCache(d, 32)

	for _, index := range order {
		c.read(index)
	}

	return d.requests
}

func main() {
	forward := make([]int, 16)

	for i := range forward {
		forward[i] = i
	}

	backward := slices.Clone(forward)
	slices.Reverse(backward)

	fmt.Printf("16 pages read in order: %d disk requests\n", requests(forward))
	fmt.Printf("16 pages read in reverse order: %d disk requests\n", requests(backward))
	fmt.Printf("16 pages read in order, 2 times: %d disk requests\n", requests(append(forward, forward...)))

	d := &disk{pages: []byte("----------------")}
	c := newCache(d, 4)

	c.write(3, 'x')
	fmt.Printf("write of x to page 3: %d pages written, the disk holds %c\n", d.written, d.pages[3])
	fmt.Printf("sync: %d page written, the disk holds %c\n", c.sync(), d.pages[3])

	for _, index := range []int{2, 1, 0, 3} {
		c.read(index)
	}

	c.read(8)
	fmt.Printf("capacity 4, pages 3 2 1 0 3 used, then page 8: cache holds %v\n", c.held())

	c.write(1, 'y')

	for _, index := range []int{0, 3, 8, 12} {
		c.read(index)
	}

	fmt.Printf("write of y to page 1, then pages 0 3 8 12 used: cache holds %v, the disk holds %c\n", c.held(), d.pages[1])
}

Listing 8.18 The trace, in Rust. code/rust/pagecache/src/main.rs

/// Reads the given pages through a new cache and returns the number of disk
/// requests.
fn requests(order: impl Iterator<Item = usize>) -> usize {
    let mut cache = Cache::new(32);

    for index in order {
        cache.read(index);
    }

    cache.disk.requests
}

/// Formats page numbers the way Go prints a slice.
fn list(pages: &[usize]) -> String {
    let words: Vec<String> = pages.iter().map(usize::to_string).collect();

    format!("[{}]", words.join(" "))
}

fn main() {
    println!("16 pages read in order: {} disk requests", requests(0..16));
    println!(
        "16 pages read in reverse order: {} disk requests",
        requests((0..16).rev())
    );
    println!(
        "16 pages read in order, 2 times: {} disk requests",
        requests((0..16).chain(0..16))
    );

    let mut cache = Cache::new(4);

    cache.write(3, b'x');
    println!(
        "write of x to page 3: {} pages written, the disk holds {}",
        cache.disk.written,
        char::from(cache.disk.pages[3])
    );

    let written = cache.sync();
    println!(
        "sync: {written} page written, the disk holds {}",
        char::from(cache.disk.pages[3])
    );

    for index in [2, 1, 0, 3] {
        cache.read(index);
    }

    cache.read(8);
    println!(
        "capacity 4, pages 3 2 1 0 3 used, then page 8: cache holds {}",
        list(&cache.held())
    );

    cache.write(1, b'y');

    for index in [0, 3, 8, 12] {
        cache.read(index);
    }

    println!(
        "write of y to page 1, then pages 0 3 8 12 used: cache holds {}, the disk holds {}",
        list(&cache.held()),
        char::from(cache.disk.pages[1])
    );
}

16 pages read in order: 4 disk requests
16 pages read in reverse order: 16 disk requests
16 pages read in order, 2 times: 4 disk requests
write of x to page 3: 0 pages written, the disk holds -
sync: 1 page written, the disk holds x
capacity 4, pages 3 2 1 0 3 used, then page 8: cache holds [0 1 3 8]
write of y to page 1, then pages 0 3 8 12 used: cache holds [0 3 8 12], the disk holds y

Writeback and durability

write returns when the data is in the cache. When the data reaches the disk is decided by the kernel’s flusher threads, which wake periodically and write dirty pages. 4 settings under /proc/sys/vm control them, shown here with the values on this machine.

The last setting is a form of the flow control of chapter 1. A program that writes faster than the disk can absorb fills memory with dirty pages, and at 20% the kernel slows it down to the speed of the disk.

A program for which lost data is unacceptable, such as a database, calls fsync after writing and reports success only after fsync has returned. The call is slow compared with write, since it waits for the disk, and this is the main cost of durability. Opening a file with O_DIRECT bypasses the cache altogether: reads and writes go straight to the disk, for programs that keep a cache of their own.

Eviction

When memory runs short, the kernel frees frames, and the page cache is the first place it looks. It keeps the pages on 2 lists.

A page enters the inactive list when it is first read. If it is used again, it is promoted to the active list. Pages are evicted from the end of the inactive list, and the active list is trimmed into the inactive list to keep the 2 in proportion. The effect is that a page has to be used at least 2 times to be protected, so reading a large file once, as a backup does, does not push out the pages that programs use all the time. /proc/meminfo shows the sizes of the lists as Active(file) and Inactive(file): 3.4 GB and 2.5 GB on this machine.

A clean page is evicted by dropping it. A dirty page has to be written first, which is the reason the kernel writes dirty pages in the background before memory is short. The model above uses a single list with exact access times, which shows the idea with less code.

Inspecting the cache on a live system

The complete programs

Listing 8.19 The complete cachefacts, in Go. code/go/cachefacts/main.go

// Command cachefacts measures the page cache for one file: how many of the
// file's pages are held in memory after a write, after the cache is told to
// drop them, and after reads of different kinds.
//
// Run it from code/go with:
//
//	go run ./cachefacts
package main

import (
	"fmt"
	"io"
	"log"
	"os"
	"os/exec"
	"path/filepath"
	"strconv"
	"strings"

	"golang.org/x/sys/unix"
)


const pageSize = 4096

// cached returns the number of pages of a file that are in the page cache,
// as reported by the fincore utility.
func cached(path string) (int, error) {
	text, err := exec.Command("fincore", "--noheadings", "--output", "PAGES", path).Output()

	if err != nil {
		return 0, err
	}

	return strconv.Atoi(strings.TrimSpace(string(text)))
}

// report prints a step and the number of cached pages after it.
func report(step, path string) error {
	pages, err := cached(path)

	if err != nil {
		return err
	}

	fmt.Printf("%-38s cached pages: %d\n", step+":", pages)

	return nil
}

// drop writes the file's dirty pages to disk and asks the kernel to remove
// the file's pages from the cache.
func drop(file *os.File) error {
	if err := file.Sync(); err != nil {
		return err
	}

	return unix.Fadvise(int(file.Fd()), 0, 0, unix.FADV_DONTNEED)
}


// run writes a file of 64 pages and reads it in 3 ways, dropping the cached
// pages between the steps.
func run(path string) error {
	file, err := os.OpenFile(path, os.O_RDWR|os.O_CREATE, 0o644)

	if err != nil {
		return err
	}

	defer file.Close()

	if _, err := file.Write(make([]byte, 64*pageSize)); err != nil {
		return err
	}

	if err := report("write of 64 pages", path); err != nil {
		return err
	}

	if err := drop(file); err != nil {
		return err
	}

	if err := report("fsync, then FADV_DONTNEED", path); err != nil {
		return err
	}

	one := make([]byte, 1)

	if _, err := file.ReadAt(one, 0); err != nil {
		return err
	}

	if err := report("read of 1 byte at offset 0", path); err != nil {
		return err
	}

	if _, err := io.Copy(io.Discard, io.NewSectionReader(file, 0, 64*pageSize)); err != nil {
		return err
	}

	if err := report("read of the whole file", path); err != nil {
		return err
	}

	if err := drop(file); err != nil {
		return err
	}

	if err := unix.Fadvise(int(file.Fd()), 0, 0, unix.FADV_RANDOM); err != nil {
		return err
	}

	if _, err := file.ReadAt(one, 0); err != nil {
		return err
	}

	return report("dropped, FADV_RANDOM, read of 1 byte", path)
}


func main() {
	dir, err := os.MkdirTemp("", "cachefacts")

	if err != nil {
		log.Fatal(err)
	}

	err = run(filepath.Join(dir, "file"))
	os.RemoveAll(dir)

	if err != nil {
		log.Fatal(err)
	}
}

Listing 8.20 The complete cachefacts, in Rust. code/rust/cachefacts/src/main.rs

//! Measures the page cache for one file: how many of the file's pages are
//! held in memory after a write, after the cache is told to drop them, and
//! after reads of different kinds.
//!
//! Run it from code/rust with:
//!
//! ```text
//! cargo run -p cachefacts
//! ```

use std::fs::{self, File, OpenOptions};
use std::io::{self, Write};
use std::os::unix::fs::FileExt;
use std::path::Path;
use std::process::Command;

use nix::fcntl::{PosixFadviseAdvice, posix_fadvise};

const PAGE_SIZE: usize = 4096;

/// Returns the number of pages of a file that are in the page cache, as
/// reported by the fincore utility.
fn cached(path: &Path) -> io::Result<usize> {
    let output = Command::new("fincore")
        .args(["--noheadings", "--output", "PAGES"])
        .arg(path)
        .output()?;

    String::from_utf8_lossy(&output.stdout)
        .trim()
        .parse()
        .map_err(|_| io::ErrorKind::InvalidData.into())
}

/// Prints a step and the number of cached pages after it.
fn report(step: &str, path: &Path) -> io::Result<()> {
    let pages = cached(path)?;
    println!("{:<38} cached pages: {pages}", format!("{step}:"));

    Ok(())
}

/// Writes the file's dirty pages to disk and asks the kernel to remove the
/// file's pages from the cache.
fn drop_pages(file: &File) -> io::Result<()> {
    file.sync_all()?;
    posix_fadvise(file, 0, 0, PosixFadviseAdvice::POSIX_FADV_DONTNEED)?;

    Ok(())
}

/// Writes a file of 64 pages and reads it in 3 ways, dropping the cached
/// pages between the steps.
fn run(path: &Path) -> io::Result<()> {
    let mut file = OpenOptions::new()
        .read(true)
        .write(true)
        .create(true)
        .truncate(true)
        .open(path)?;

    file.write_all(&vec![0u8; 64 * PAGE_SIZE])?;
    report("write of 64 pages", path)?;

    drop_pages(&file)?;
    report("fsync, then FADV_DONTNEED", path)?;

    let mut one = [0u8; 1];

    file.read_exact_at(&mut one, 0)?;
    report("read of 1 byte at offset 0", path)?;

    let mut whole = vec![0u8; 64 * PAGE_SIZE];

    file.read_exact_at(&mut whole, 0)?;
    report("read of the whole file", path)?;

    drop_pages(&file)?;
    posix_fadvise(&file, 0, 0, PosixFadviseAdvice::POSIX_FADV_RANDOM)?;

    file.read_exact_at(&mut one, 0)?;
    report("dropped, FADV_RANDOM, read of 1 byte", path)
}

fn main() -> io::Result<()> {
    let dir = std::env::temp_dir().join(format!("cachefacts-{}", std::process::id()));

    fs::create_dir_all(&dir)?;

    let result = run(&dir.join("file"));

    fs::remove_dir_all(&dir)?;

    result
}

Listing 8.21 The complete pagecache, in Go. code/go/pagecache/main.go

// Command pagecache models the kernel's page cache for one file: pages read
// from a disk are kept in memory, sequential reads fetch pages ahead of the
// reader, writes change only the cached page until a sync, and the page used
// least recently is evicted when the cache is full.
//
// Run it from code/go with:
//
//	go run ./pagecache
package main

import (
	"fmt"
	"slices"
)


// maxWindow is the largest number of pages one disk request reads ahead.
const maxWindow = 8

// A disk holds the pages of a file and counts the requests made to it. The
// contents of a page are reduced to one byte.
type disk struct {
	pages    []byte
	requests int
	written  int
}

// A page is a cached copy of a disk page. dirty is set when the copy has
// been written and the disk has not. used is the time of the last access.
type page struct {
	value byte
	dirty bool
	used  int
}

// A cache maps page numbers to cached pages. next is the page that a
// sequential reader would ask for next, and window is the current number of
// pages to read ahead.
type cache struct {
	disk     *disk
	pages    map[int]*page
	capacity int
	clock    int
	next     int
	window   int
}

func newCache(d *disk, capacity int) *cache {
	return &cache{disk: d, pages: map[int]*page{}, capacity: capacity}
}


// read returns the contents of a page. A page that is cached costs no disk
// request. For a page that is missing, read makes one request for a window
// of pages. The window doubles while the reads are sequential and returns
// to 1 page when they are not.
func (c *cache) read(index int) byte {
	if _, hit := c.pages[index]; !hit {
		if index == c.next {
			c.window = min(2*max(c.window, 1), maxWindow)
		} else {
			c.window = 1
		}

		c.load(index, c.window)
	}

	c.next = index + 1

	return c.touch(index).value
}

// load reads count pages starting at index from the disk in one request.
func (c *cache) load(index, count int) {
	c.disk.requests++

	for i := index; i < min(index+count, len(c.disk.pages)); i++ {
		if _, hit := c.pages[i]; !hit {
			c.insert(i, &page{value: c.disk.pages[i]})
		}
	}
}

// touch records an access to a cached page and returns the page.
func (c *cache) touch(index int) *page {
	c.clock++
	c.pages[index].used = c.clock

	return c.pages[index]
}


// write changes a page in the cache and marks it dirty. It makes no disk
// request.
func (c *cache) write(index int, value byte) {
	if _, hit := c.pages[index]; !hit {
		c.insert(index, &page{})
	}

	p := c.touch(index)
	p.value, p.dirty = value, true
}

// sync writes every dirty page to the disk and returns the number written.
func (c *cache) sync() int {
	before := c.disk.written

	for index, p := range c.pages {
		c.clean(index, p)
	}

	return c.disk.written - before
}

// clean writes one page to the disk if it is dirty.
func (c *cache) clean(index int, p *page) {
	if p.dirty {
		c.disk.pages[index] = p.value
		c.disk.written++
		p.dirty = false
	}
}


// insert adds a page to the cache. When the cache is full it first evicts
// the page whose last access is the oldest. A dirty page is written to the
// disk before it is removed.
func (c *cache) insert(index int, p *page) {
	if len(c.pages) == c.capacity {
		oldest := -1

		for i, candidate := range c.pages {
			if oldest == -1 || candidate.used < c.pages[oldest].used {
				oldest = i
			}
		}

		c.clean(oldest, c.pages[oldest])
		delete(c.pages, oldest)
	}

	c.clock++
	p.used = c.clock
	c.pages[index] = p
}

// held returns the numbers of the cached pages in increasing order.
func (c *cache) held() []int {
	held := make([]int, 0, len(c.pages))

	for index := range c.pages {
		held = append(held, index)
	}

	slices.Sort(held)

	return held
}


// requests reads the given pages through a new cache and returns the number
// of disk requests.
func requests(order []int) int {
	d := &disk{pages: make([]byte, 16)}
	c := newCache(d, 32)

	for _, index := range order {
		c.read(index)
	}

	return d.requests
}

func main() {
	forward := make([]int, 16)

	for i := range forward {
		forward[i] = i
	}

	backward := slices.Clone(forward)
	slices.Reverse(backward)

	fmt.Printf("16 pages read in order: %d disk requests\n", requests(forward))
	fmt.Printf("16 pages read in reverse order: %d disk requests\n", requests(backward))
	fmt.Printf("16 pages read in order, 2 times: %d disk requests\n", requests(append(forward, forward...)))

	d := &disk{pages: []byte("----------------")}
	c := newCache(d, 4)

	c.write(3, 'x')
	fmt.Printf("write of x to page 3: %d pages written, the disk holds %c\n", d.written, d.pages[3])
	fmt.Printf("sync: %d page written, the disk holds %c\n", c.sync(), d.pages[3])

	for _, index := range []int{2, 1, 0, 3} {
		c.read(index)
	}

	c.read(8)
	fmt.Printf("capacity 4, pages 3 2 1 0 3 used, then page 8: cache holds %v\n", c.held())

	c.write(1, 'y')

	for _, index := range []int{0, 3, 8, 12} {
		c.read(index)
	}

	fmt.Printf("write of y to page 1, then pages 0 3 8 12 used: cache holds %v, the disk holds %c\n", c.held(), d.pages[1])
}

Listing 8.22 The complete pagecache, in Rust. code/rust/pagecache/src/main.rs

//! Models the kernel's page cache for one file: pages read from a disk are
//! kept in memory, sequential reads fetch pages ahead of the reader, writes
//! change only the cached page until a sync, and the page used least recently
//! is evicted when the cache is full.
//!
//! Run it from code/rust with:
//!
//! ```text
//! cargo run -p pagecache
//! ```

use std::collections::BTreeMap;

/// The largest number of pages one disk request reads ahead.
const MAX_WINDOW: usize = 8;

/// Holds the pages of a file and counts the requests made to it. The contents
/// of a page are reduced to one byte.
struct Disk {
    pages: Vec<u8>,
    requests: usize,
    written: usize,
}

impl Disk {
    fn new() -> Disk {
        Disk {
            pages: vec![b'-'; 16],
            requests: 0,
            written: 0,
        }
    }
}

/// A cached copy of a disk page. `dirty` is set when the copy has been
/// written and the disk has not. `used` is the time of the last access.
#[derive(Default)]
struct Page {
    value: u8,
    dirty: bool,
    used: usize,
}

/// Maps page numbers to cached pages. `next` is the page that a sequential
/// reader would ask for next, and `window` is the current number of pages to
/// read ahead.
struct Cache {
    disk: Disk,
    pages: BTreeMap<usize, Page>,
    capacity: usize,
    clock: usize,
    next: usize,
    window: usize,
}

impl Cache {
    fn new(capacity: usize) -> Cache {
        Cache {
            disk: Disk::new(),
            pages: BTreeMap::new(),
            capacity,
            clock: 0,
            next: 0,
            window: 0,
        }
    }
}

impl Cache {
    /// Returns the contents of a page. A page that is cached costs no disk
    /// request. For a page that is missing, `read` makes one request for a
    /// window of pages. The window doubles while the reads are sequential and
    /// returns to 1 page when they are not.
    fn read(&mut self, index: usize) -> u8 {
        if !self.pages.contains_key(&index) {
            if index == self.next {
                self.window = (2 * self.window.max(1)).min(MAX_WINDOW);
            } else {
                self.window = 1;
            }

            self.load(index, self.window);
        }

        self.next = index + 1;

        self.touch(index).value
    }

    /// Reads `count` pages starting at `index` from the disk in one request.
    fn load(&mut self, index: usize, count: usize) {
        self.disk.requests += 1;

        for i in index..(index + count).min(self.disk.pages.len()) {
            if !self.pages.contains_key(&i) {
                let value = self.disk.pages[i];

                self.insert(i, value);
            }
        }
    }

    /// Records an access to a page and returns the page. A page that is not
    /// cached is created empty.
    fn touch(&mut self, index: usize) -> &mut Page {
        self.clock += 1;

        let page = self.pages.entry(index).or_default();
        page.used = self.clock;

        page
    }
}

impl Cache {
    /// Changes a page in the cache and marks it dirty. It makes no disk
    /// request.
    fn write(&mut self, index: usize, value: u8) {
        if !self.pages.contains_key(&index) {
            self.insert(index, 0);
        }

        let page = self.touch(index);
        page.value = value;
        page.dirty = true;
    }

    /// Writes every dirty page to the disk and returns the number written.
    fn sync(&mut self) -> usize {
        let before = self.disk.written;

        for (&index, page) in &mut self.pages {
            clean(&mut self.disk, index, page);
        }

        self.disk.written - before
    }
}

/// Writes one page to the disk if it is dirty.
fn clean(disk: &mut Disk, index: usize, page: &mut Page) {
    if page.dirty {
        disk.pages[index] = page.value;
        disk.written += 1;
        page.dirty = false;
    }
}

impl Cache {
    /// Adds a page to the cache. When the cache is full it first evicts the
    /// page whose last access is the oldest. A dirty page is written to the
    /// disk before it is removed.
    fn insert(&mut self, index: usize, value: u8) {
        if self.pages.len() == self.capacity {
            let oldest = self
                .pages
                .iter()
                .min_by_key(|(_, page)| page.used)
                .map(|(&index, _)| index);

            if let Some(oldest) = oldest
                && let Some(mut page) = self.pages.remove(&oldest)
            {
                clean(&mut self.disk, oldest, &mut page);
            }
        }

        self.clock += 1;

        let page = Page {
            value,
            dirty: false,
            used: self.clock,
        };

        self.pages.insert(index, page);
    }

    /// Returns the numbers of the cached pages in increasing order.
    fn held(&self) -> Vec<usize> {
        self.pages.keys().copied().collect()
    }
}

/// Reads the given pages through a new cache and returns the number of disk
/// requests.
fn requests(order: impl Iterator<Item = usize>) -> usize {
    let mut cache = Cache::new(32);

    for index in order {
        cache.read(index);
    }

    cache.disk.requests
}

/// Formats page numbers the way Go prints a slice.
fn list(pages: &[usize]) -> String {
    let words: Vec<String> = pages.iter().map(usize::to_string).collect();

    format!("[{}]", words.join(" "))
}

fn main() {
    println!("16 pages read in order: {} disk requests", requests(0..16));
    println!(
        "16 pages read in reverse order: {} disk requests",
        requests((0..16).rev())
    );
    println!(
        "16 pages read in order, 2 times: {} disk requests",
        requests((0..16).chain(0..16))
    );

    let mut cache = Cache::new(4);

    cache.write(3, b'x');
    println!(
        "write of x to page 3: {} pages written, the disk holds {}",
        cache.disk.written,
        char::from(cache.disk.pages[3])
    );

    let written = cache.sync();
    println!(
        "sync: {written} page written, the disk holds {}",
        char::from(cache.disk.pages[3])
    );

    for index in [2, 1, 0, 3] {
        cache.read(index);
    }

    cache.read(8);
    println!(
        "capacity 4, pages 3 2 1 0 3 used, then page 8: cache holds {}",
        list(&cache.held())
    );

    cache.write(1, b'y');

    for index in [0, 3, 8, 12] {
        cache.read(index);
    }

    println!(
        "write of y to page 1, then pages 0 3 8 12 used: cache holds {}, the disk holds {}",
        list(&cache.held()),
        char::from(cache.disk.pages[1])
    );
}

References

• posix_fadvise(2), fsync(2) and fincore(1), Linux manual pages: https://man7.org/linux/man-pages/man2/posix_fadvise.2.html
• R. Love, Linux Kernel Development, 3rd edition, Addison-Wesley, 2010, chapter 16.
• mm/filemap.c, mm/readahead.c and fs/fs-writeback.c, Linux 5.15: https://elixir.bootlin.com/linux/v5.15/source/mm/readahead.c