Virtual Memory

The address space of a process is the set of memory addresses the process can use and the meaning the kernel has given to each. The addresses are virtual: they are translated to locations in physical memory by the processor, through a table that the kernel maintains for each process. Different processes can use the same virtual address for different memory, and neither can reach the memory of the other.

In this chapter, we will learn how the kernel fills an address space. We will first measure with vmfacts when a mapped page receives physical memory and where a write through a file mapping ends up. Then we will write vmmodel, a model with mappings, a page table and a page fault handler, and use it to follow copy-on-write after fork.

Why addresses are virtual

Suppose programs used the addresses of physical memory directly. A program compiled to keep a variable at address 0x1000 could run only when that memory was free, and 2 copies of it could not run together. Any program could read or overwrite the memory of any other by using its addresses. And a program could use no more memory than was physically free at the moment it started.

Virtual addresses remove all 3 problems with a single idea: the addresses a program uses are private to it, and a table per process says which physical memory, if any, stands behind each of them.

With this arrangement every program can be built as if it had the machine to itself. The kernel decides which physical memory each address reaches, and it can decide late, at the moment the address is first used. The rest of the chapter is about how the table is organised and when it is filled in.

The layout of an address space

Before the mechanism, we look at what an address space contains. The kernel lists the address ranges a process can use in /proc/<pid>/maps. This is the listing of a cat process on our machine, with 3 of its columns removed.

$ cat /proc/self/maps
aaaab7c80000-aaaab7c86000 r-xp 00000000 /usr/bin/cat
aaaab7c95000-aaaab7c96000 r--p 00005000 /usr/bin/cat
aaaab7c96000-aaaab7c97000 rw-p 00006000 /usr/bin/cat
aaaacae31000-aaaacae52000 rw-p 00000000 [heap]
ffffaa650000-ffffaa7d8000 r-xp 00000000 /usr/lib/aarch64-linux-gnu/libc.so.6
ffffaa7e7000-ffffaa7eb000 r--p 00187000 /usr/lib/aarch64-linux-gnu/libc.so.6
ffffaa7eb000-ffffaa7ed000 rw-p 0018b000 /usr/lib/aarch64-linux-gnu/libc.so.6
ffffaa80b000-ffffaa82d000 rw-p 00000000
ffffaa82d000-ffffaa858000 r-xp 00000000 /usr/lib/aarch64-linux-gnu/ld-linux-aarch64.so.1
ffffaa866000-ffffaa867000 r-xp 00000000 [vdso]
fffff2ebe000-fffff2ee0000 rw-p 00000000 [stack]

The numbers are addresses in hexadecimal, and they are less forbidding than they look. A line gives a start and an end, and the size of the range is the difference. For the first line, 0xaaaab7c86000 - 0xaaaab7c80000 = 0x6000, which is 6 × 4096 bytes: the code of cat occupies 6 pages. Only the differences carry information. The absolute values change on every run.

Each line is a mapping: a range of addresses with the same permissions and the same source.

The ranges are far apart, and most of the space between them is unmapped. An access to an unmapped address ends the process with SIGSEGV. The addresses differ from run to run, because the kernel chooses the positions of the regions at random for each new program, which makes attacks that depend on known addresses harder.

Pages, mappings and the page table

Virtual and physical memory are both divided into units of the same size, 4096 bytes on this machine. A unit of virtual memory is a page, and a unit of physical memory is a frame. The address space is described at 2 levels.

Translating an address

Translation is easiest to follow on a machine small enough to work by hand. Imagine addresses of 16 bits and pages of 256 bytes. An address then has 2 hexadecimal digits for the page number and 2 for the offset within the page. To translate 0x1234, split it into page 0x12 and offset 0x34, look up entry 0x12 of the page table, find frame 0x7A there, and attach the offset: the physical address is 0x7A34.

A real machine does exactly this, with larger numbers and with a table that is split into several levels to save space.

The processor translates every address a program uses, in hardware. An address of this machine has 48 significant bits. The low 12 bits are the offset within a page, since a page has 4096 = 2¹² bytes. The remaining 36 bits are the page number, and they are used in 4 groups of 9 bits.

The page table is a tree of tables, each a page of 512 entries. The processor starts at the root table of the process, uses the first 9 bits to select an entry, follows it to a table of the next level, and repeats this 4 times. The last entry holds the number of the frame and the permission bits. The frame number and the offset together are the physical address.

A tree is used because the address space is almost empty. A flat table for 2³⁶ pages would need 512 GiB for each process. In the tree, a table exists only for the regions that are in use, and the cat process above needs a few dozen kilobytes.

Walking 4 tables for every memory access would be slow, so the processor keeps the results of recent translations in a cache, the translation lookaside buffer or TLB. Most accesses are answered from the TLB. When the kernel changes a page table entry, it tells the processor to discard the cached translation.

mmap adds a mapping. It writes no page table entry and allocates no frame. A mapping is a promise: these addresses are valid, and this is what they contain.

The promise is kept later. When the program uses an address whose page has no entry, or writes where the entry forbids writing, the processor cannot complete the instruction. It raises a page fault, which transfers control to the kernel. The kernel looks up the address in the mappings. If a mapping permits the access, the kernel provides a frame, writes the entry, and returns, and the processor repeats the instruction. If no mapping permits it, the kernel sends the process the signal SIGSEGV.

Filling the table on demand means that memory is spent only on pages that are used. A program can map a large range and touch a small part of it, and a large program starts quickly because its code is read from disk page by page as it runs.

The kernel’s structures

The kernel describes an address space with 3 structures. These are the definitions in include/linux/mm_types.h of Linux 5.15, reduced to the fields we use.

struct mm_struct {
        struct vm_area_struct *mmap;           /* the mappings, as a list */
        struct rb_root mm_rb;                  /* the mappings, as a tree by address */
        pgd_t *pgd;                            /* the root of the page table */
        int map_count;                         /* number of mappings */
        unsigned long total_vm;                /* pages mapped */
        unsigned long start_brk, brk;          /* the heap */
        unsigned long start_stack;             /* the stack */
        /* ... */
};

struct vm_area_struct {
        unsigned long vm_start;                /* first address of the mapping */
        unsigned long vm_end;                  /* first address after it */
        struct vm_area_struct *vm_next, *vm_prev;
        struct mm_struct *vm_mm;               /* the address space it belongs to */
        unsigned long vm_flags;                /* VM_READ, VM_WRITE, VM_EXEC, VM_SHARED */
        unsigned long vm_pgoff;                /* offset in the file, in pages */
        struct file *vm_file;                  /* the mapped file, or NULL */
        /* ... */
};

struct page {
        unsigned long flags;                   /* dirty, locked, ... */
        struct address_space *mapping;         /* the file this frame caches, if any */
        pgoff_t index;                         /* its page number in that file */
        atomic_t _mapcount;                    /* page table entries that map it */
        atomic_t _refcount;                    /* users of the frame */
        /* ... */
};

There are 2 descriptions of the same address space, and the difference between them is the subject of this chapter. The list of VMAs says what the process is allowed to use. The page table says what has actually been given a frame. mmap changes only the first.

Measuring an address space

vmfacts uses golang.org/x/sys/unix in Go and the memmap2 crate in Rust.

$ cargo new vmfacts
$ cargo add -p vmfacts memmap2

The kernel publishes the page table of a process in /proc/self/pagemap: 8 bytes for each virtual page, in which bit 63 is set when the page has a frame. resident counts those pages for a mapping.

Listing 7.1 The imports of vmfacts, in Go. code/go/vmfacts/main.go

import (
	"bufio"
	"encoding/binary"
	"fmt"
	"log"
	"os"
	"path/filepath"
	"reflect"
	"strings"

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

Listing 7.2 The imports of vmfacts, in Rust. code/rust/vmfacts/src/main.rs

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

use memmap2::{MmapMut, MmapOptions};

Listing 7.3 Counting the pages of a mapping that have a frame, in Go. code/go/vmfacts/main.go

const pageSize = 4096

// address returns the virtual address of the first byte of a mapping.
func address(mapping []byte) uintptr {
	return reflect.ValueOf(mapping).Pointer()
}

// resident counts the pages of a mapping that have physical memory. The
// kernel publishes 8 bytes per virtual page in /proc/self/pagemap, and bit 63
// of an entry is set when the page is present in memory.
func resident(mapping []byte) (int, error) {
	pagemap, err := os.Open("/proc/self/pagemap")

	if err != nil {
		return 0, err
	}

	defer pagemap.Close()

	entries := make([]byte, 8*len(mapping)/pageSize)

	if _, err := pagemap.ReadAt(entries, int64(address(mapping)/pageSize*8)); err != nil {
		return 0, err
	}

	count := 0

	for i := 0; i < len(entries); i += 8 {
		if binary.LittleEndian.Uint64(entries[i:])>>63 == 1 {
			count++
		}
	}

	return count, nil
}

Listing 7.4 Counting the pages of a mapping that have a frame, in Rust. code/rust/vmfacts/src/main.rs

const PAGE_SIZE: usize = 4096;

/// Counts the pages of a mapping that have physical memory. The kernel
/// publishes 8 bytes per virtual page in `/proc/self/pagemap`, and bit 63 of
/// an entry is set when the page is present in memory.
fn resident(mapping: &[u8]) -> io::Result<usize> {
    let pagemap = File::open("/proc/self/pagemap")?;
    let mut entries = vec![0u8; 8 * mapping.len() / PAGE_SIZE];
    let offset = mapping.as_ptr() as usize / PAGE_SIZE * 8;

    pagemap.read_exact_at(&mut entries, offset as u64)?;

    let (entries, _) = entries.as_chunks::<8>();
    let count = entries.iter().filter(|entry| entry[7] >> 7 == 1).count();

    Ok(count)
}

demand maps 64 pages of anonymous memory and counts the resident pages 3 times: after mmap, after writing to 10 pages, and after reading 1 further page.

Listing 7.5 When a page receives memory, in Go. code/go/vmfacts/main.go

// demand maps 64 pages of anonymous memory, writes to 10 of them, reads 1
// more, and counts the resident pages after each step.
func demand() error {
	mapping, err := unix.Mmap(-1, 0, 64*pageSize, unix.PROT_READ|unix.PROT_WRITE, unix.MAP_PRIVATE|unix.MAP_ANONYMOUS)

	if err != nil {
		return err
	}

	defer unix.Munmap(mapping)

	before, err := resident(mapping)

	if err != nil {
		return err
	}

	for page := range 10 {
		mapping[page*pageSize] = 1
	}

	written, err := resident(mapping)

	if err != nil {
		return err
	}

	value := mapping[20*pageSize]
	read, err := resident(mapping)

	if err != nil {
		return err
	}

	fmt.Printf("64 pages mapped: %d resident\n", before)
	fmt.Printf("after writing to 10 pages: %d resident\n", written)
	fmt.Printf("after reading 1 more page: %d resident, the byte read is %d\n", read, value)

	return nil
}

Listing 7.6 When a page receives memory, in Rust. code/rust/vmfacts/src/main.rs

/// Maps 64 pages of anonymous memory, writes to 10 of them, reads 1 more, and
/// counts the resident pages after each step.
fn demand() -> io::Result<()> {
    let mut mapping = MmapMut::map_anon(64 * PAGE_SIZE)?;

    let before = resident(&mapping)?;

    for page in 0..10 {
        mapping[page * PAGE_SIZE] = 1;
    }

    let written = resident(&mapping)?;

    let value = mapping[20 * PAGE_SIZE];
    let read = resident(&mapping)?;

    println!("64 pages mapped: {before} resident");
    println!("after writing to 10 pages: {written} resident");
    println!("after reading 1 more page: {read} resident, the byte read is {value}");

    Ok(())
}

protect reads the permissions of a mapping from /proc/self/maps before and after mprotect removes the permission to write.

Listing 7.7 The permissions of a mapping, in Go. code/go/vmfacts/main.go

// permissions returns the permission column of the line in /proc/self/maps
// that starts at the address of a mapping.
func permissions(mapping []byte) (string, error) {
	maps, err := os.Open("/proc/self/maps")

	if err != nil {
		return "", err
	}

	defer maps.Close()

	start := fmt.Sprintf("%x-", address(mapping))

	for lines := bufio.NewScanner(maps); lines.Scan(); {
		if fields := strings.Fields(lines.Text()); strings.HasPrefix(fields[0], start) {
			return fields[1], nil
		}
	}

	return "", fmt.Errorf("mapping at %s not found", start)
}

// protect reads the permissions of a mapping before and after mprotect
// removes the permission to write.
func protect() error {
	mapping, err := unix.Mmap(-1, 0, pageSize, unix.PROT_READ|unix.PROT_WRITE, unix.MAP_PRIVATE|unix.MAP_ANONYMOUS)

	if err != nil {
		return err
	}

	defer unix.Munmap(mapping)

	before, err := permissions(mapping)

	if err != nil {
		return err
	}

	if err := unix.Mprotect(mapping, unix.PROT_READ); err != nil {
		return err
	}

	after, err := permissions(mapping)

	if err != nil {
		return err
	}

	fmt.Printf("permissions of the mapping: %s, after mprotect: %s\n", before, after)

	return nil
}

Listing 7.8 The permissions of a mapping, in Rust. code/rust/vmfacts/src/main.rs

/// Returns the permission column of the line in `/proc/self/maps` that starts
/// at the address of a mapping.
fn permissions(mapping: &[u8]) -> io::Result<String> {
    let start = format!("{:x}-", mapping.as_ptr() as usize);

    fs::read_to_string("/proc/self/maps")?
        .lines()
        .filter(|line| line.starts_with(&start))
        .find_map(|line| line.split_whitespace().nth(1))
        .map(str::to_owned)
        .ok_or_else(|| io::ErrorKind::NotFound.into())
}

/// Reads the permissions of a mapping before and after mprotect removes the
/// permission to write.
fn protect() -> io::Result<()> {
    let mapping = MmapMut::map_anon(PAGE_SIZE)?;
    let before = permissions(&mapping)?;

    let mapping = mapping.make_read_only()?;
    let after = permissions(&mapping)?;

    println!("permissions of the mapping: {before}, after mprotect: {after}");

    Ok(())
}

throughMapping maps a file that contains hello, writes HELLO into the mapped memory, and reads the file again. It does this with a private mapping and with a shared one. Mapping a file is an unsafe operation in Rust, because another process could change the file while the program holds a slice of it. The comment in the listing states why the use is sound here.

Listing 7.9 Writing through a private and a shared file mapping, in Go. code/go/vmfacts/main.go

// throughMapping maps a file that holds "hello", writes "HELLO" through the
// mapping, unmaps it, and returns the contents of the file.
func throughMapping(path string, flags int) (string, error) {
	if err := os.WriteFile(path, []byte("hello"), 0o644); err != nil {
		return "", err
	}

	file, err := os.OpenFile(path, os.O_RDWR, 0)

	if err != nil {
		return "", err
	}

	defer file.Close()

	mapping, err := unix.Mmap(int(file.Fd()), 0, 5, unix.PROT_READ|unix.PROT_WRITE, flags)

	if err != nil {
		return "", err
	}

	copy(mapping, "HELLO")

	if err := unix.Munmap(mapping); err != nil {
		return "", err
	}

	text, err := os.ReadFile(path)

	return string(text), err
}

// files compares a private file mapping with a shared one.
func files() error {
	dir, err := os.MkdirTemp("", "vmfacts")

	if err != nil {
		return err
	}

	defer os.RemoveAll(dir)

	path := filepath.Join(dir, "file")

	for _, kind := range []struct {
		name  string
		flags int
	}{{"private", unix.MAP_PRIVATE}, {"shared", unix.MAP_SHARED}} {
		text, err := throughMapping(path, kind.flags)

		if err != nil {
			return err
		}

		fmt.Printf("HELLO written through a %s file mapping: the file holds %q\n", kind.name, text)
	}

	return nil
}

Listing 7.10 Writing through a private and a shared file mapping, in Rust. code/rust/vmfacts/src/main.rs

/// Maps a file that holds "hello", writes "HELLO" through the mapping, unmaps
/// it, and returns the contents of the file.
fn through_mapping(path: &Path, shared: bool) -> io::Result<String> {
    fs::write(path, "hello")?;

    let file = OpenOptions::new().read(true).write(true).open(path)?;
    let options = MmapOptions::new();

    // SAFETY: mapping a file is unsafe in Rust because another process could
    // change the file while the slice exists. This file is in a directory the
    // program has just created, and nothing else opens it.
    let mut mapping = unsafe {
        if shared {
            options.map_mut(&file)?
        } else {
            options.map_copy(&file)?
        }
    };

    mapping.copy_from_slice(b"HELLO");
    drop(mapping);

    fs::read_to_string(path)
}

/// Compares a private file mapping with a shared one.
fn files() -> io::Result<()> {
    let dir = std::env::temp_dir().join(format!("vmfacts-{}", std::process::id()));
    let path = dir.join("file");

    fs::create_dir_all(&dir)?;

    for (name, shared) in [("private", false), ("shared", true)] {
        let text = through_mapping(&path, shared)?;
        println!("HELLO written through a {name} file mapping: the file holds {text:?}");
    }

    fs::remove_dir_all(&dir)
}

64 pages mapped: 0 resident
after writing to 10 pages: 10 resident
after reading 1 more page: 11 resident, the byte read is 0
permissions of the mapping: rw-p, after mprotect: r--p
HELLO written through a private file mapping: the file holds "hello"
HELLO written through a shared file mapping: the file holds "HELLO"

Modelling an address space

In the Rust version, a frame is an Rc of an array, and the reference count of the Rc is the refs field of the Go version.

Listing 7.11 The imports of vmmodel, in Go. code/go/vmmodel/main.go

import (
	"errors"
	"fmt"
)

Listing 7.12 The imports of vmmodel, in Rust. code/rust/vmmodel/src/main.rs

use std::cell::Cell;
use std::collections::HashMap;
use std::fmt;
use std::rc::Rc;

Listing 7.13 Frames, mappings, entries and the address space, in Go. code/go/vmmodel/main.go

const pageSize = 4096

// errSegv is the result of an access that no mapping allows. The kernel
// sends the process the signal SIGSEGV.
var errSegv = errors.New("SIGSEGV")

// A frame is a page of physical memory. refs counts the page table entries
// that refer to it.
type frame struct {
	data [pageSize]byte
	refs int
}

// memory is the physical memory shared by all address spaces: the number of
// frames allocated, and the frame of zeros that every read of an untouched
// page maps.
type memory struct {
	frames int
	zero   *frame
}

func (m *memory) allocate() *frame {
	m.frames++

	return &frame{refs: 1}
}

// A mapping is a range of virtual pages and the access it permits.
type mapping struct {
	start, pages int
	writable     bool
}

// An entry is a page table entry: the frame behind a virtual page, and
// whether the processor may write to it without a fault.
type entry struct {
	frame    *frame
	writable bool
}

// A space is the address space of a process.
type space struct {
	memory   *memory
	mappings []mapping
	table    map[int]entry
	faults   int
	nextPage int
}

func newSpace() *space {
	return &space{
		memory:   &memory{zero: &frame{refs: 1}},
		table:    map[int]entry{},
		nextPage: 16,
	}
}

Listing 7.14 Frames, mappings, entries and the address space, in Rust. code/rust/vmmodel/src/main.rs

const PAGE_SIZE: usize = 4096;

/// The result of an access that no mapping allows. The kernel sends the
/// process the signal `SIGSEGV`.
#[derive(Debug)]
struct Segv;

impl fmt::Display for Segv {
    fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
        f.write_str("SIGSEGV")
    }
}

/// A page of physical memory. The reference count of the `Rc` is the number
/// of page table entries that refer to it.
type Frame = Rc<[u8; PAGE_SIZE]>;

/// The physical memory shared by all address spaces: the number of frames
/// allocated, and the frame of zeros that every read of an untouched page
/// maps.
struct Memory {
    frames: Cell<usize>,
    zero: Frame,
}

impl Memory {
    fn allocate(&self, contents: [u8; PAGE_SIZE]) -> Frame {
        self.frames.set(self.frames.get() + 1);

        Rc::new(contents)
    }
}

/// A range of virtual pages and the access it permits.
#[derive(Clone, Copy)]
struct Mapping {
    start: usize,
    pages: usize,
    writable: bool,
}

/// A page table entry: the frame behind a virtual page, and whether the
/// processor may write to it without a fault.
#[derive(Clone)]
struct Entry {
    frame: Frame,
    writable: bool,
}

/// The address space of a process.
struct Space {
    memory: Rc<Memory>,
    mappings: Vec<Mapping>,
    table: HashMap<usize, Entry>,
    faults: usize,
    next_page: usize,
}

impl Space {
    fn new() -> Space {
        let memory = Memory {
            frames: Cell::new(0),
            zero: Rc::new([0; PAGE_SIZE]),
        };

        Space {
            memory: Rc::new(memory),
            mappings: Vec::new(),
            table: HashMap::new(),
            faults: 0,
            next_page: 16,
        }
    }
}

mmap only records the range.

Listing 7.15 Adding a mapping, in Go. code/go/vmmodel/main.go

// mmap records a new mapping and returns its address. It allocates no frame
// and writes no page table entry.
func (s *space) mmap(pages int, writable bool) int {
	start := s.nextPage
	s.mappings = append(s.mappings, mapping{start: start, pages: pages, writable: writable})
	s.nextPage += pages + 1

	return start * pageSize
}

// find returns the mapping that contains a page.
func (s *space) find(page int) (mapping, bool) {
	for _, m := range s.mappings {
		if page >= m.start && page < m.start+m.pages {
			return m, true
		}
	}

	return mapping{}, false
}

Listing 7.16 Adding a mapping, in Rust. code/rust/vmmodel/src/main.rs

impl Space {
    /// Records a new mapping and returns its address. It allocates no frame
    /// and writes no page table entry.
    fn mmap(&mut self, pages: usize, writable: bool) -> usize {
        let start = self.next_page;

        self.mappings.push(Mapping {
            start,
            pages,
            writable,
        });
        self.next_page += pages + 1;

        start * PAGE_SIZE
    }

    /// Returns the mapping that contains a page.
    fn find(&self, page: usize) -> Option<Mapping> {
        self.mappings
            .iter()
            .copied()
            .find(|mapping| (mapping.start..mapping.start + mapping.pages).contains(&page))
    }
}

read and write play the part of the processor. They consult the page table and call fault when the entry is missing or forbids the access.

Listing 7.17 An access through the page table, in Go. code/go/vmmodel/main.go

// read returns the byte at an address. The processor uses the page table
// entry when one exists, and faults when none does.
func (s *space) read(address int) (byte, error) {
	page, offset := address/pageSize, address%pageSize

	if _, present := s.table[page]; !present {
		if err := s.fault(page, false); err != nil {
			return 0, err
		}
	}

	return s.table[page].frame.data[offset], nil
}

// write stores a byte at an address. It faults when the page has no entry or
// the entry does not permit writing.
func (s *space) write(address int, value byte) error {
	page, offset := address/pageSize, address%pageSize

	if !s.table[page].writable {
		if err := s.fault(page, true); err != nil {
			return err
		}
	}

	s.table[page].frame.data[offset] = value

	return nil
}

Listing 7.18 An access through the page table, in Rust. code/rust/vmmodel/src/main.rs

impl Space {
    /// Returns the byte at an address. The processor uses the page table
    /// entry when one exists, and faults when none does.
    fn read(&mut self, address: usize) -> Result<u8, Segv> {
        let (page, offset) = (address / PAGE_SIZE, address % PAGE_SIZE);

        if !self.table.contains_key(&page) {
            self.fault(page, false)?;
        }

        self.table
            .get(&page)
            .map(|entry| entry.frame[offset])
            .ok_or(Segv)
    }

    /// Stores a byte at an address. It faults when the page has no entry or
    /// the entry does not permit writing.
    fn write(&mut self, address: usize, value: u8) -> Result<(), Segv> {
        let (page, offset) = (address / PAGE_SIZE, address % PAGE_SIZE);

        if !self.table.get(&page).is_some_and(|entry| entry.writable) {
            self.fault(page, true)?;
        }

        let entry = self.table.get_mut(&page).ok_or(Segv)?;

        // A writable entry is the only user of its frame, so `make_mut`
        // returns the frame itself.
        Rc::make_mut(&mut entry.frame)[offset] = value;

        Ok(())
    }
}

fault is the kernel’s handler. After the check against the mappings it has 4 cases.

Case 1 explains the measurement of 11 resident pages. Every read of an untouched anonymous page maps the same frame of zeros, so reading costs no memory. The frame is mapped read-only, and the first write replaces it with a private frame through case 4.

Listing 7.19 The page fault handler, in Go. code/go/vmmodel/main.go

// fault is the kernel's page fault handler. It checks the access against
// the mappings and then repairs the page table entry so that the access can
// be repeated.
func (s *space) fault(page int, write bool) error {
	m, ok := s.find(page)

	if !ok || write && !m.writable {
		return errSegv
	}

	s.faults++
	e, present := s.table[page]

	switch {
	case !write:
		// A read of an untouched page maps the shared zero frame.
		s.memory.zero.refs++
		s.table[page] = entry{frame: s.memory.zero}

	case !present:
		// A write to an untouched page gets a new frame of zeros.
		s.table[page] = entry{frame: s.memory.allocate(), writable: true}

	case e.frame.refs == 1:
		// The frame has no other user. Writing is enabled in place.
		s.table[page] = entry{frame: e.frame, writable: true}

	default:
		// The frame is shared. The writer gets a private copy.
		private := s.memory.allocate()
		private.data = e.frame.data
		e.frame.refs--
		s.table[page] = entry{frame: private, writable: true}
	}

	return nil
}

Listing 7.20 The page fault handler, in Rust. code/rust/vmmodel/src/main.rs

impl Space {
    /// The kernel's page fault handler. It checks the access against the
    /// mappings and then repairs the page table entry so that the access can
    /// be repeated.
    fn fault(&mut self, page: usize, write: bool) -> Result<(), Segv> {
        let mapping = self.find(page).ok_or(Segv)?;

        if write && !mapping.writable {
            return Err(Segv);
        }

        self.faults += 1;

        let entry = match (write, self.table.remove(&page)) {
            // A read of an untouched page maps the shared zero frame.
            (false, _) => Entry {
                frame: Rc::clone(&self.memory.zero),
                writable: false,
            },

            // A write to an untouched page gets a new frame of zeros.
            (true, None) => Entry {
                frame: self.memory.allocate([0; PAGE_SIZE]),
                writable: true,
            },

            // The frame has no other user. Writing is enabled in place.
            (true, Some(entry)) if Rc::strong_count(&entry.frame) == 1 => Entry {
                frame: entry.frame,
                writable: true,
            },

            // The frame is shared. The writer gets a private copy.
            (true, Some(entry)) => Entry {
                frame: self.memory.allocate(*entry.frame),
                writable: true,
            },
        };

        self.table.insert(page, entry);

        Ok(())
    }
}

Copy-on-write

fork gives the child a copy of the parent’s address space. Copying every frame would be slow, and most of the work would be wasted, since the usual next step of the child is exec, which discards the address space. The kernel therefore copies only the page table. Parent and child refer to the same frames, and every entry is made read-only in both.

Listing 7.21 Forking an address space, in Go. code/go/vmmodel/main.go

// fork returns a child with the same mappings and a page table that refers
// to the same frames. Every entry is made read-only in the parent and in the
// child, so that the first write by either causes a fault.
func (s *space) fork() *space {
	child := &space{
		memory:   s.memory,
		mappings: append([]mapping(nil), s.mappings...),
		table:    map[int]entry{},
		nextPage: s.nextPage,
	}

	for page, e := range s.table {
		e.frame.refs++
		e.writable = false
		s.table[page], child.table[page] = e, e
	}

	return child
}

Listing 7.22 Forking an address space, in Rust. code/rust/vmmodel/src/main.rs

impl Space {
    /// Returns a child with the same mappings and a page table that refers to
    /// the same frames. Every entry is made read-only in the parent and in
    /// the child, so that the first write by either causes a fault.
    fn fork(&mut self) -> Space {
        for entry in self.table.values_mut() {
            entry.writable = false;
        }

        Space {
            memory: Rc::clone(&self.memory),
            mappings: self.mappings.clone(),
            table: self.table.clone(),
            faults: 0,
            next_page: self.next_page,
        }
    }
}

Reads continue without faults. The first write to a page by either process faults. The handler sees a read-only entry in a writable mapping, copies the frame for the writer, and the processes diverge on that page only.

A private file mapping uses the same mechanism. Its pages initially refer to the file’s frames, read-only, and a write copies the page. The file is unchanged, as vmfacts measured.

Listing 7.23 The trace, in Go. code/go/vmmodel/main.go

// report prints a step with the fault count of a space and the number of
// frames allocated.
func (s *space) report(step string) {
	fmt.Printf("%-34s faults %d, frames %d\n", step, s.faults, s.memory.frames)
}

func run() error {
	parent := newSpace()
	base := parent.mmap(4, true)
	parent.report("mmap of 4 pages:")

	if err := parent.write(base, 'a'); err != nil {
		return err
	}

	parent.report("write to page 0:")

	value, err := parent.read(base + pageSize)

	if err != nil {
		return err
	}

	parent.report(fmt.Sprintf("read of page 1, value %d:", value))

	if err := parent.write(base+pageSize, 'x'); err != nil {
		return err
	}

	parent.report("write to page 1:")

	child := parent.fork()
	child.report("fork, in the child:")

	if err := child.write(base, 'b'); err != nil {
		return err
	}

	child.report("child writes page 0:")

	if err := parent.write(base, 'c'); err != nil {
		return err
	}

	parent.report("parent writes page 0:")

	inParent, err := parent.read(base)

	if err != nil {
		return err
	}

	inChild, err := child.read(base)

	if err != nil {
		return err
	}

	fmt.Printf("page 0 holds %q in the parent and %q in the child\n", inParent, inChild)

	fmt.Printf("write outside every mapping: %v\n", parent.write(base+100*pageSize, 1))

	readOnly := parent.mmap(1, false)
	fmt.Printf("write to a read-only mapping: %v\n", parent.write(readOnly, 1))

	return nil
}

func main() {
	if err := run(); err != nil {
		fmt.Println(err)
	}
}

Listing 7.24 The trace, in Rust. code/rust/vmmodel/src/main.rs

impl Space {
    /// Prints a step with the fault count of a space and the number of frames
    /// allocated.
    fn report(&self, step: &str) {
        println!(
            "{step:<34} faults {}, frames {}",
            self.faults,
            self.memory.frames.get()
        );
    }
}

fn run() -> Result<(), Segv> {
    let mut parent = Space::new();
    let base = parent.mmap(4, true);
    parent.report("mmap of 4 pages:");

    parent.write(base, b'a')?;
    parent.report("write to page 0:");

    let value = parent.read(base + PAGE_SIZE)?;
    parent.report(&format!("read of page 1, value {value}:"));

    parent.write(base + PAGE_SIZE, b'x')?;
    parent.report("write to page 1:");

    let mut child = parent.fork();
    child.report("fork, in the child:");

    child.write(base, b'b')?;
    child.report("child writes page 0:");

    parent.write(base, b'c')?;
    parent.report("parent writes page 0:");

    println!(
        "page 0 holds {:?} in the parent and {:?} in the child",
        char::from(parent.read(base)?),
        char::from(child.read(base)?)
    );

    if let Err(error) = parent.write(base + 100 * PAGE_SIZE, 1) {
        println!("write outside every mapping: {error}");
    }

    let read_only = parent.mmap(1, false);

    if let Err(error) = parent.write(read_only, 1) {
        println!("write to a read-only mapping: {error}");
    }

    Ok(())
}

fn main() {
    if let Err(error) = run() {
        println!("{error}");
    }
}

mmap of 4 pages:                   faults 0, frames 0
write to page 0:                   faults 1, frames 1
read of page 1, value 0:           faults 2, frames 1
write to page 1:                   faults 3, frames 2
fork, in the child:                faults 0, frames 2
child writes page 0:               faults 1, frames 3
parent writes page 0:              faults 4, frames 3
page 0 holds 'c' in the parent and 'b' in the child
write outside every mapping: SIGSEGV
write to a read-only mapping: SIGSEGV

How much memory a process uses

Since mapping and allocating are separate, a process has 2 sizes.

$ ps -o pid,vsz,rss,min_flt,maj_flt,comm -p 580844
    PID    VSZ   RSS  MINFL  MAJFL COMMAND
 580844  11204   776    114      0 sleep

The sleep process has mapped 11 MB and uses under 1 MB, because most of the pages of its libraries have not been touched. It took 114 page faults to start, each bringing in a single page or a few. RSS is the number to look at when asking how much memory a process costs, with the reservation that pages shared with other processes, such as the code of libc, are counted in the RSS of each.

Because memory is given out at the first access, the kernel can promise more than it has. This is overcommit: the sum of the mappings of all processes may exceed physical memory and swap, on the assumption that not all of it will be touched. The policy is in /proc/sys/vm/overcommit_memory, and the value 1 on this machine means that mmap does not refuse a request for lack of memory. When the promises are called in and no frame is free, the kernel first reclaims frames, by discarding page cache pages (chapter 8) and by writing anonymous pages to swap space on disk. When that is not enough, the OOM killer ends a process to free its memory. Chapter 12 shows it at work inside a memory limit.

The heap and the stack

malloc is a library function, and the kernel knows nothing about individual allocations. The allocator asks the kernel for memory in large pieces and divides them itself. It has 2 ways to ask. brk moves the end of the [heap] mapping, which suits many small allocations. For a large request, 128 KiB or more in the allocator of glibc, it calls mmap for an anonymous mapping of its own, which can be returned to the kernel independently. Both give addresses without frames, so memory that a program allocates and does not touch costs nothing.

The stack is a mapping that the kernel extends on demand. An access directly below its current end causes a page fault, and the handler enlarges the mapping, up to the limit shown by ulimit -s.

Inspecting memory on a live system

The complete programs

Listing 7.25 The complete vmfacts, in Go. code/go/vmfacts/main.go

// Command vmfacts measures how the kernel fills an address space: when a
// mapped page receives physical memory, what an untouched page contains, how
// a mapping's permissions appear in /proc/self/maps, and where a write
// through a private or a shared file mapping ends up.
//
// Run it from code/go with:
//
//	go run ./vmfacts
package main

import (
	"bufio"
	"encoding/binary"
	"fmt"
	"log"
	"os"
	"path/filepath"
	"reflect"
	"strings"

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


const pageSize = 4096

// address returns the virtual address of the first byte of a mapping.
func address(mapping []byte) uintptr {
	return reflect.ValueOf(mapping).Pointer()
}

// resident counts the pages of a mapping that have physical memory. The
// kernel publishes 8 bytes per virtual page in /proc/self/pagemap, and bit 63
// of an entry is set when the page is present in memory.
func resident(mapping []byte) (int, error) {
	pagemap, err := os.Open("/proc/self/pagemap")

	if err != nil {
		return 0, err
	}

	defer pagemap.Close()

	entries := make([]byte, 8*len(mapping)/pageSize)

	if _, err := pagemap.ReadAt(entries, int64(address(mapping)/pageSize*8)); err != nil {
		return 0, err
	}

	count := 0

	for i := 0; i < len(entries); i += 8 {
		if binary.LittleEndian.Uint64(entries[i:])>>63 == 1 {
			count++
		}
	}

	return count, nil
}


// demand maps 64 pages of anonymous memory, writes to 10 of them, reads 1
// more, and counts the resident pages after each step.
func demand() error {
	mapping, err := unix.Mmap(-1, 0, 64*pageSize, unix.PROT_READ|unix.PROT_WRITE, unix.MAP_PRIVATE|unix.MAP_ANONYMOUS)

	if err != nil {
		return err
	}

	defer unix.Munmap(mapping)

	before, err := resident(mapping)

	if err != nil {
		return err
	}

	for page := range 10 {
		mapping[page*pageSize] = 1
	}

	written, err := resident(mapping)

	if err != nil {
		return err
	}

	value := mapping[20*pageSize]
	read, err := resident(mapping)

	if err != nil {
		return err
	}

	fmt.Printf("64 pages mapped: %d resident\n", before)
	fmt.Printf("after writing to 10 pages: %d resident\n", written)
	fmt.Printf("after reading 1 more page: %d resident, the byte read is %d\n", read, value)

	return nil
}


// permissions returns the permission column of the line in /proc/self/maps
// that starts at the address of a mapping.
func permissions(mapping []byte) (string, error) {
	maps, err := os.Open("/proc/self/maps")

	if err != nil {
		return "", err
	}

	defer maps.Close()

	start := fmt.Sprintf("%x-", address(mapping))

	for lines := bufio.NewScanner(maps); lines.Scan(); {
		if fields := strings.Fields(lines.Text()); strings.HasPrefix(fields[0], start) {
			return fields[1], nil
		}
	}

	return "", fmt.Errorf("mapping at %s not found", start)
}

// protect reads the permissions of a mapping before and after mprotect
// removes the permission to write.
func protect() error {
	mapping, err := unix.Mmap(-1, 0, pageSize, unix.PROT_READ|unix.PROT_WRITE, unix.MAP_PRIVATE|unix.MAP_ANONYMOUS)

	if err != nil {
		return err
	}

	defer unix.Munmap(mapping)

	before, err := permissions(mapping)

	if err != nil {
		return err
	}

	if err := unix.Mprotect(mapping, unix.PROT_READ); err != nil {
		return err
	}

	after, err := permissions(mapping)

	if err != nil {
		return err
	}

	fmt.Printf("permissions of the mapping: %s, after mprotect: %s\n", before, after)

	return nil
}


// throughMapping maps a file that holds "hello", writes "HELLO" through the
// mapping, unmaps it, and returns the contents of the file.
func throughMapping(path string, flags int) (string, error) {
	if err := os.WriteFile(path, []byte("hello"), 0o644); err != nil {
		return "", err
	}

	file, err := os.OpenFile(path, os.O_RDWR, 0)

	if err != nil {
		return "", err
	}

	defer file.Close()

	mapping, err := unix.Mmap(int(file.Fd()), 0, 5, unix.PROT_READ|unix.PROT_WRITE, flags)

	if err != nil {
		return "", err
	}

	copy(mapping, "HELLO")

	if err := unix.Munmap(mapping); err != nil {
		return "", err
	}

	text, err := os.ReadFile(path)

	return string(text), err
}

// files compares a private file mapping with a shared one.
func files() error {
	dir, err := os.MkdirTemp("", "vmfacts")

	if err != nil {
		return err
	}

	defer os.RemoveAll(dir)

	path := filepath.Join(dir, "file")

	for _, kind := range []struct {
		name  string
		flags int
	}{{"private", unix.MAP_PRIVATE}, {"shared", unix.MAP_SHARED}} {
		text, err := throughMapping(path, kind.flags)

		if err != nil {
			return err
		}

		fmt.Printf("HELLO written through a %s file mapping: the file holds %q\n", kind.name, text)
	}

	return nil
}


func main() {
	for _, experiment := range []func() error{demand, protect, files} {
		if err := experiment(); err != nil {
			log.Fatal(err)
		}
	}
}

Listing 7.26 The complete vmfacts, in Rust. code/rust/vmfacts/src/main.rs

//! Measures how the kernel fills an address space: when a mapped page
//! receives physical memory, what an untouched page contains, how a mapping's
//! permissions appear in `/proc/self/maps`, and where a write through a
//! private or a shared file mapping ends up.
//!
//! Run it from code/rust with:
//!
//! ```text
//! cargo run -p vmfacts
//! ```

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

use memmap2::{MmapMut, MmapOptions};

const PAGE_SIZE: usize = 4096;

/// Counts the pages of a mapping that have physical memory. The kernel
/// publishes 8 bytes per virtual page in `/proc/self/pagemap`, and bit 63 of
/// an entry is set when the page is present in memory.
fn resident(mapping: &[u8]) -> io::Result<usize> {
    let pagemap = File::open("/proc/self/pagemap")?;
    let mut entries = vec![0u8; 8 * mapping.len() / PAGE_SIZE];
    let offset = mapping.as_ptr() as usize / PAGE_SIZE * 8;

    pagemap.read_exact_at(&mut entries, offset as u64)?;

    let (entries, _) = entries.as_chunks::<8>();
    let count = entries.iter().filter(|entry| entry[7] >> 7 == 1).count();

    Ok(count)
}

/// Maps 64 pages of anonymous memory, writes to 10 of them, reads 1 more, and
/// counts the resident pages after each step.
fn demand() -> io::Result<()> {
    let mut mapping = MmapMut::map_anon(64 * PAGE_SIZE)?;

    let before = resident(&mapping)?;

    for page in 0..10 {
        mapping[page * PAGE_SIZE] = 1;
    }

    let written = resident(&mapping)?;

    let value = mapping[20 * PAGE_SIZE];
    let read = resident(&mapping)?;

    println!("64 pages mapped: {before} resident");
    println!("after writing to 10 pages: {written} resident");
    println!("after reading 1 more page: {read} resident, the byte read is {value}");

    Ok(())
}

/// Returns the permission column of the line in `/proc/self/maps` that starts
/// at the address of a mapping.
fn permissions(mapping: &[u8]) -> io::Result<String> {
    let start = format!("{:x}-", mapping.as_ptr() as usize);

    fs::read_to_string("/proc/self/maps")?
        .lines()
        .filter(|line| line.starts_with(&start))
        .find_map(|line| line.split_whitespace().nth(1))
        .map(str::to_owned)
        .ok_or_else(|| io::ErrorKind::NotFound.into())
}

/// Reads the permissions of a mapping before and after mprotect removes the
/// permission to write.
fn protect() -> io::Result<()> {
    let mapping = MmapMut::map_anon(PAGE_SIZE)?;
    let before = permissions(&mapping)?;

    let mapping = mapping.make_read_only()?;
    let after = permissions(&mapping)?;

    println!("permissions of the mapping: {before}, after mprotect: {after}");

    Ok(())
}

/// Maps a file that holds "hello", writes "HELLO" through the mapping, unmaps
/// it, and returns the contents of the file.
fn through_mapping(path: &Path, shared: bool) -> io::Result<String> {
    fs::write(path, "hello")?;

    let file = OpenOptions::new().read(true).write(true).open(path)?;
    let options = MmapOptions::new();

    // SAFETY: mapping a file is unsafe in Rust because another process could
    // change the file while the slice exists. This file is in a directory the
    // program has just created, and nothing else opens it.
    let mut mapping = unsafe {
        if shared {
            options.map_mut(&file)?
        } else {
            options.map_copy(&file)?
        }
    };

    mapping.copy_from_slice(b"HELLO");
    drop(mapping);

    fs::read_to_string(path)
}

/// Compares a private file mapping with a shared one.
fn files() -> io::Result<()> {
    let dir = std::env::temp_dir().join(format!("vmfacts-{}", std::process::id()));
    let path = dir.join("file");

    fs::create_dir_all(&dir)?;

    for (name, shared) in [("private", false), ("shared", true)] {
        let text = through_mapping(&path, shared)?;
        println!("HELLO written through a {name} file mapping: the file holds {text:?}");
    }

    fs::remove_dir_all(&dir)
}

fn main() -> io::Result<()> {
    demand()?;
    protect()?;
    files()
}

Listing 7.27 The complete vmmodel, in Go. code/go/vmmodel/main.go

// Command vmmodel models an address space: a list of mappings, a page table
// that is filled on demand by page faults, a shared zero page, and
// copy-on-write after fork.
//
// Run it from code/go with:
//
//	go run ./vmmodel
package main

import (
	"errors"
	"fmt"
)


const pageSize = 4096

// errSegv is the result of an access that no mapping allows. The kernel
// sends the process the signal SIGSEGV.
var errSegv = errors.New("SIGSEGV")

// A frame is a page of physical memory. refs counts the page table entries
// that refer to it.
type frame struct {
	data [pageSize]byte
	refs int
}

// memory is the physical memory shared by all address spaces: the number of
// frames allocated, and the frame of zeros that every read of an untouched
// page maps.
type memory struct {
	frames int
	zero   *frame
}

func (m *memory) allocate() *frame {
	m.frames++

	return &frame{refs: 1}
}

// A mapping is a range of virtual pages and the access it permits.
type mapping struct {
	start, pages int
	writable     bool
}

// An entry is a page table entry: the frame behind a virtual page, and
// whether the processor may write to it without a fault.
type entry struct {
	frame    *frame
	writable bool
}

// A space is the address space of a process.
type space struct {
	memory   *memory
	mappings []mapping
	table    map[int]entry
	faults   int
	nextPage int
}

func newSpace() *space {
	return &space{
		memory:   &memory{zero: &frame{refs: 1}},
		table:    map[int]entry{},
		nextPage: 16,
	}
}


// mmap records a new mapping and returns its address. It allocates no frame
// and writes no page table entry.
func (s *space) mmap(pages int, writable bool) int {
	start := s.nextPage
	s.mappings = append(s.mappings, mapping{start: start, pages: pages, writable: writable})
	s.nextPage += pages + 1

	return start * pageSize
}

// find returns the mapping that contains a page.
func (s *space) find(page int) (mapping, bool) {
	for _, m := range s.mappings {
		if page >= m.start && page < m.start+m.pages {
			return m, true
		}
	}

	return mapping{}, false
}


// read returns the byte at an address. The processor uses the page table
// entry when one exists, and faults when none does.
func (s *space) read(address int) (byte, error) {
	page, offset := address/pageSize, address%pageSize

	if _, present := s.table[page]; !present {
		if err := s.fault(page, false); err != nil {
			return 0, err
		}
	}

	return s.table[page].frame.data[offset], nil
}

// write stores a byte at an address. It faults when the page has no entry or
// the entry does not permit writing.
func (s *space) write(address int, value byte) error {
	page, offset := address/pageSize, address%pageSize

	if !s.table[page].writable {
		if err := s.fault(page, true); err != nil {
			return err
		}
	}

	s.table[page].frame.data[offset] = value

	return nil
}


// fault is the kernel's page fault handler. It checks the access against
// the mappings and then repairs the page table entry so that the access can
// be repeated.
func (s *space) fault(page int, write bool) error {
	m, ok := s.find(page)

	if !ok || write && !m.writable {
		return errSegv
	}

	s.faults++
	e, present := s.table[page]

	switch {
	case !write:
		// A read of an untouched page maps the shared zero frame.
		s.memory.zero.refs++
		s.table[page] = entry{frame: s.memory.zero}

	case !present:
		// A write to an untouched page gets a new frame of zeros.
		s.table[page] = entry{frame: s.memory.allocate(), writable: true}

	case e.frame.refs == 1:
		// The frame has no other user. Writing is enabled in place.
		s.table[page] = entry{frame: e.frame, writable: true}

	default:
		// The frame is shared. The writer gets a private copy.
		private := s.memory.allocate()
		private.data = e.frame.data
		e.frame.refs--
		s.table[page] = entry{frame: private, writable: true}
	}

	return nil
}


// fork returns a child with the same mappings and a page table that refers
// to the same frames. Every entry is made read-only in the parent and in the
// child, so that the first write by either causes a fault.
func (s *space) fork() *space {
	child := &space{
		memory:   s.memory,
		mappings: append([]mapping(nil), s.mappings...),
		table:    map[int]entry{},
		nextPage: s.nextPage,
	}

	for page, e := range s.table {
		e.frame.refs++
		e.writable = false
		s.table[page], child.table[page] = e, e
	}

	return child
}


// report prints a step with the fault count of a space and the number of
// frames allocated.
func (s *space) report(step string) {
	fmt.Printf("%-34s faults %d, frames %d\n", step, s.faults, s.memory.frames)
}

func run() error {
	parent := newSpace()
	base := parent.mmap(4, true)
	parent.report("mmap of 4 pages:")

	if err := parent.write(base, 'a'); err != nil {
		return err
	}

	parent.report("write to page 0:")

	value, err := parent.read(base + pageSize)

	if err != nil {
		return err
	}

	parent.report(fmt.Sprintf("read of page 1, value %d:", value))

	if err := parent.write(base+pageSize, 'x'); err != nil {
		return err
	}

	parent.report("write to page 1:")

	child := parent.fork()
	child.report("fork, in the child:")

	if err := child.write(base, 'b'); err != nil {
		return err
	}

	child.report("child writes page 0:")

	if err := parent.write(base, 'c'); err != nil {
		return err
	}

	parent.report("parent writes page 0:")

	inParent, err := parent.read(base)

	if err != nil {
		return err
	}

	inChild, err := child.read(base)

	if err != nil {
		return err
	}

	fmt.Printf("page 0 holds %q in the parent and %q in the child\n", inParent, inChild)

	fmt.Printf("write outside every mapping: %v\n", parent.write(base+100*pageSize, 1))

	readOnly := parent.mmap(1, false)
	fmt.Printf("write to a read-only mapping: %v\n", parent.write(readOnly, 1))

	return nil
}

func main() {
	if err := run(); err != nil {
		fmt.Println(err)
	}
}

Listing 7.28 The complete vmmodel, in Rust. code/rust/vmmodel/src/main.rs

//! Models an address space: a list of mappings, a page table that is filled
//! on demand by page faults, a shared zero page, and copy-on-write after
//! fork.
//!
//! Run it from code/rust with:
//!
//! ```text
//! cargo run -p vmmodel
//! ```

use std::cell::Cell;
use std::collections::HashMap;
use std::fmt;
use std::rc::Rc;

const PAGE_SIZE: usize = 4096;

/// The result of an access that no mapping allows. The kernel sends the
/// process the signal `SIGSEGV`.
#[derive(Debug)]
struct Segv;

impl fmt::Display for Segv {
    fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
        f.write_str("SIGSEGV")
    }
}

/// A page of physical memory. The reference count of the `Rc` is the number
/// of page table entries that refer to it.
type Frame = Rc<[u8; PAGE_SIZE]>;

/// The physical memory shared by all address spaces: the number of frames
/// allocated, and the frame of zeros that every read of an untouched page
/// maps.
struct Memory {
    frames: Cell<usize>,
    zero: Frame,
}

impl Memory {
    fn allocate(&self, contents: [u8; PAGE_SIZE]) -> Frame {
        self.frames.set(self.frames.get() + 1);

        Rc::new(contents)
    }
}

/// A range of virtual pages and the access it permits.
#[derive(Clone, Copy)]
struct Mapping {
    start: usize,
    pages: usize,
    writable: bool,
}

/// A page table entry: the frame behind a virtual page, and whether the
/// processor may write to it without a fault.
#[derive(Clone)]
struct Entry {
    frame: Frame,
    writable: bool,
}

/// The address space of a process.
struct Space {
    memory: Rc<Memory>,
    mappings: Vec<Mapping>,
    table: HashMap<usize, Entry>,
    faults: usize,
    next_page: usize,
}

impl Space {
    fn new() -> Space {
        let memory = Memory {
            frames: Cell::new(0),
            zero: Rc::new([0; PAGE_SIZE]),
        };

        Space {
            memory: Rc::new(memory),
            mappings: Vec::new(),
            table: HashMap::new(),
            faults: 0,
            next_page: 16,
        }
    }
}

impl Space {
    /// Records a new mapping and returns its address. It allocates no frame
    /// and writes no page table entry.
    fn mmap(&mut self, pages: usize, writable: bool) -> usize {
        let start = self.next_page;

        self.mappings.push(Mapping {
            start,
            pages,
            writable,
        });
        self.next_page += pages + 1;

        start * PAGE_SIZE
    }

    /// Returns the mapping that contains a page.
    fn find(&self, page: usize) -> Option<Mapping> {
        self.mappings
            .iter()
            .copied()
            .find(|mapping| (mapping.start..mapping.start + mapping.pages).contains(&page))
    }
}

impl Space {
    /// Returns the byte at an address. The processor uses the page table
    /// entry when one exists, and faults when none does.
    fn read(&mut self, address: usize) -> Result<u8, Segv> {
        let (page, offset) = (address / PAGE_SIZE, address % PAGE_SIZE);

        if !self.table.contains_key(&page) {
            self.fault(page, false)?;
        }

        self.table
            .get(&page)
            .map(|entry| entry.frame[offset])
            .ok_or(Segv)
    }

    /// Stores a byte at an address. It faults when the page has no entry or
    /// the entry does not permit writing.
    fn write(&mut self, address: usize, value: u8) -> Result<(), Segv> {
        let (page, offset) = (address / PAGE_SIZE, address % PAGE_SIZE);

        if !self.table.get(&page).is_some_and(|entry| entry.writable) {
            self.fault(page, true)?;
        }

        let entry = self.table.get_mut(&page).ok_or(Segv)?;

        // A writable entry is the only user of its frame, so `make_mut`
        // returns the frame itself.
        Rc::make_mut(&mut entry.frame)[offset] = value;

        Ok(())
    }
}

impl Space {
    /// The kernel's page fault handler. It checks the access against the
    /// mappings and then repairs the page table entry so that the access can
    /// be repeated.
    fn fault(&mut self, page: usize, write: bool) -> Result<(), Segv> {
        let mapping = self.find(page).ok_or(Segv)?;

        if write && !mapping.writable {
            return Err(Segv);
        }

        self.faults += 1;

        let entry = match (write, self.table.remove(&page)) {
            // A read of an untouched page maps the shared zero frame.
            (false, _) => Entry {
                frame: Rc::clone(&self.memory.zero),
                writable: false,
            },

            // A write to an untouched page gets a new frame of zeros.
            (true, None) => Entry {
                frame: self.memory.allocate([0; PAGE_SIZE]),
                writable: true,
            },

            // The frame has no other user. Writing is enabled in place.
            (true, Some(entry)) if Rc::strong_count(&entry.frame) == 1 => Entry {
                frame: entry.frame,
                writable: true,
            },

            // The frame is shared. The writer gets a private copy.
            (true, Some(entry)) => Entry {
                frame: self.memory.allocate(*entry.frame),
                writable: true,
            },
        };

        self.table.insert(page, entry);

        Ok(())
    }
}

impl Space {
    /// Returns a child with the same mappings and a page table that refers to
    /// the same frames. Every entry is made read-only in the parent and in
    /// the child, so that the first write by either causes a fault.
    fn fork(&mut self) -> Space {
        for entry in self.table.values_mut() {
            entry.writable = false;
        }

        Space {
            memory: Rc::clone(&self.memory),
            mappings: self.mappings.clone(),
            table: self.table.clone(),
            faults: 0,
            next_page: self.next_page,
        }
    }
}

impl Space {
    /// Prints a step with the fault count of a space and the number of frames
    /// allocated.
    fn report(&self, step: &str) {
        println!(
            "{step:<34} faults {}, frames {}",
            self.faults,
            self.memory.frames.get()
        );
    }
}

fn run() -> Result<(), Segv> {
    let mut parent = Space::new();
    let base = parent.mmap(4, true);
    parent.report("mmap of 4 pages:");

    parent.write(base, b'a')?;
    parent.report("write to page 0:");

    let value = parent.read(base + PAGE_SIZE)?;
    parent.report(&format!("read of page 1, value {value}:"));

    parent.write(base + PAGE_SIZE, b'x')?;
    parent.report("write to page 1:");

    let mut child = parent.fork();
    child.report("fork, in the child:");

    child.write(base, b'b')?;
    child.report("child writes page 0:");

    parent.write(base, b'c')?;
    parent.report("parent writes page 0:");

    println!(
        "page 0 holds {:?} in the parent and {:?} in the child",
        char::from(parent.read(base)?),
        char::from(child.read(base)?)
    );

    if let Err(error) = parent.write(base + 100 * PAGE_SIZE, 1) {
        println!("write outside every mapping: {error}");
    }

    let read_only = parent.mmap(1, false);

    if let Err(error) = parent.write(read_only, 1) {
        println!("write to a read-only mapping: {error}");
    }

    Ok(())
}

fn main() {
    if let Err(error) = run() {
        println!("{error}");
    }
}

References

• mmap(2), mprotect(2) and proc(5) for pagemap and maps, Linux manual pages: https://man7.org/linux/man-pages/man2/mmap.2.html
• Examining Process Page Tables, Linux kernel documentation: https://www.kernel.org/doc/html/v5.15/admin-guide/mm/pagemap.html
• M. Gorman, Understanding the Linux Virtual Memory Manager, Prentice Hall, 2004.
• mm/memory.c and mm/mmap.c, Linux 5.15: https://elixir.bootlin.com/linux/v5.15/source/mm/memory.c