Reverse Mapping: Finding Every Page Table That Points at a Frame

Forward translation is the whole point of the page table: given a virtual address, find the frame. Every operation described so far uses it in that direction. Reclaim, migration, and unmap need the opposite. Given a frame, find every page-table entry that points at it, because a frame cannot be freed or moved while any mapping still references it, and every such mapping must be updated when it is.

The naive answer is to scan. Walk every process’s page tables looking for entries whose frame number matches. For a single frame that is a scan of the entire system’s mapping state, and it has to be done under conditions where the answer must be correct rather than approximately correct. It is the wrong shape of algorithm for a kernel that evicts frames continuously.

The Index and What It Holds

The reverse index, usually called an object-based reverse map, stores for each frame a reference to the object that describes the mapping, rather than a list of every virtual address that maps it. The object is the thing that owns the page: an anonymous memory region, a file mapping, a shared memory segment, or a page-cache page. From that object the kernel can enumerate the mappings, because the object knows which address spaces have mapped it.

This indirection is what makes the structure affordable. A page of a shared library mapped into a thousand processes has a thousand page-table entries but one page-cache object and one reverse-map record. Storing a thousand addresses per frame would cost four kilobytes of index for a four-kilobyte page; storing one object reference costs a pointer or an index, and the enumeration cost is paid only when the frame is actually reclaimed or moved.

The object itself carries a list of the address spaces and virtual ranges that map it. Walking that list to find the specific page-table entry for a given offset is the step that turns an object reference into a concrete entry. It is more work than following a direct pointer, but it is bounded by the number of mappers, which for the common case of a privately mapped file is one.

Anonymous memory uses a similar scheme with a different object. A private anonymous page belongs to a region that in turn belongs to one address space, and the reverse map points at the region. Finding the entry requires knowing the offset of the page within the region, which the frame’s metadata records. For a page shared between processes, as after a fork with copy-on-write, the region is shared and the enumeration covers every process that inherited it.

Why Reclaim Needs It

Eviction requires that the frame’s contents be written back, if dirty, and that the mapping be removed. Removing the mapping means clearing the page-table entry in every address space that maps it, and invalidating the translation on every processor that might have cached it. A frame that is mapped in three processes needs three page-table updates and a broadcast invalidation.

Doing this incorrectly produces a use-after-free at the hardware level: a process continues to translate an address to a frame that has been reallocated to someone else. The failure is not a kernel crash but silent data corruption in a user process, which is the worst class of bug to diagnose. This is why the reverse map must be exact rather than a hint, and why the locking around it is one of the more delicate parts of a memory manager.

The reclaim path also has to handle the case where a frame is mapped but pinned: a driver holds it for DMA, or the page is locked for direct I/O. Pinned frames cannot be reclaimed, and the reverse map is what lets the kernel determine that a candidate is pinned before it commits to eviction, rather than discovering it mid-operation. What makes a frame pinnable at all is the device side of the mapping, covered in mapping device memory and its cacheability.

Why Migration Needs It

Moving a page to a different frame requires the same enumeration, with a different action: instead of clearing entries, the kernel writes the new frame number into each one. Every processor that cached the old translation must be invalidated, and the window during which both old and new translations could exist must be closed before the old frame is reused.

Migration is what makes memory compaction possible, and compaction is what makes large pages possible. The chain runs: to create a 2 MiB contiguous free region, the kernel must move live pages out of it; to move a page it must find every mapping; to find every mapping it needs the reverse map. This is why large pages are not merely a page-table flag but an entire subsystem of migration machinery.

/* The shape of a migration: enumerate, update, invalidate, release.
   Helper names are local to this sketch. */
int migrate_frame(struct page *page, struct page *target)
{
    int moved = 0;

    rmap_walk(page, update_one_entry, target);   /* rewrite every PTE */
    if (!all_mappings_updated(page))
        return -EAGAIN;                          /* a mapper refused; retry later */

    flush_translations_for(page);                /* broadcast to all CPUs */
    page->mapping = NULL;                        /* old frame no longer referenced */
    put_page(page);
    moved = 1;
    return moved;
}

The EAGAIN path is not an error in the usual sense. A mapping that is pinned, or one whose address space lock could not be taken without blocking, causes the migration to be abandoned after some entries have been updated. The kernel must then either complete the move for the entries it changed or restore them, and the design that avoids the complexity is to check for refusals before changing anything, at the cost of a second enumeration pass.

Maintaining the Index Under Concurrency

The index is per-frame metadata, so its updates happen on every mapping operation: mmap, munmap, mprotect, fork, page fault, and reclaim. Each of these must add or remove a reference under a lock that protects the frame’s record and the object’s mapper list, and the locks are among the hottest in the kernel.

The contention problem is real and shapes the design. A global lock over all reverse maps would serialize every fault on the machine. The usual resolution is to protect the per-object mapper list with a per-object lock and the frame’s record with a lock or an atomic reference count, with a strict ordering between them to prevent deadlock. The ordering must be consistent across the fault path, the reclaim path, and the unmap path, and getting it wrong produces a deadlock that only appears when reclaim runs concurrently with a fault on a shared mapping.

Reference counting is the other half. Each frame counts its mappings, and a frame can be freed only when the count reaches zero. A copy-on-write fault decrements the count on the shared frame and increments it on the new private one; if the count on the shared frame reaches one, the remaining owner can be given write permission in place without copying, as described in the first-touch fault path. That optimization depends entirely on the count being exact, which is why the count is maintained in the frame metadata rather than derived by scanning.

The Space Cost and the Alternatives

The index costs memory proportional to the number of mapped frames. For a machine with a hundred gigabytes resident and four kilobytes per page, that is tens of millions of records, each holding at least a pointer to the owning object and the offset within it. The record is stored in the frame’s metadata structure, which exists per frame regardless of whether the frame is mapped, so the marginal cost of the reverse map is the fields added to that structure rather than a separate table.

The alternative, storing a list of virtual addresses per frame, is what some systems did and what the object-based scheme replaced. It is faster to follow, since no enumeration is needed, but the memory cost is proportional to the number of mappings rather than the number of frames, and a shared page with many mappers makes the per-frame list unbounded. It also has to be updated on every mapping change, with a list insertion or removal per entry, which is more work than updating a single object reference.

A third approach avoids the index entirely: stop the world and scan. Some systems have used a scan of all address spaces during reclaim, accepting a long pause in exchange for no steady-state cost. That trade is defensible for a system that reclaims rarely and has few address spaces, and indefensible for a general-purpose kernel that reclaims continuously while hundreds of processes run.

Where the Model Leaks

Two cases strain the object-based model. The first is a frame mapped at different offsets in different objects, which happens with shared memory used as a ring buffer or with a file mapped at different alignments in different processes. The reverse map then has to record more than one object reference per frame, and the enumeration must handle each independently. The second is a frame that is mapped but whose object is in the process of being destroyed, so the mapper list is being torn down concurrently with the reclaim that is walking it. The lock ordering and the reference counts on the object itself are what make this safe, and the code paths that handle it are the ones most likely to be wrong.

Neither case is exotic. They are the normal condition of a system running real workloads, and they explain why the reverse map, which looks like a simple index, is one of the parts of a memory manager that is hardest to change and most carefully reviewed.