How does kernel know, which pages in the virtual address space correspond to a swapped out physical page frame?

Question

Consider the following situation: the kernel has exhausted the physical RAM and needs to swap out a page. It picks least recently used page frame and wants to swap its contents out to the disk and allocate that frame to another process.

What bothers me is that this page frame was already mapped to, generally speaking, several (identical) pages of several processes. The kernel has to somehow find all of those processes and mark the page as swapped out. How does it carry that out?

Thank you.

EDIT: Illustrations to the question:

Before the swapping processes 1 and 2 had a shared Page 1, which resided in the physical memory frame 1:

Now, the memory in the system is exhausted and kernel allocates memory for process 3 by swapping out Page 1 from frame 1 and replacing it with Page 2. In order to do that, it has to

1) find all the processes, referring to Page 1 (Process 1 and Process 2 in our case)

2) modify their Page Table Entries, setting "Present" bit to 0 and setting the Page 1 location in Swap

So, I don't get, how the step 1 is carried out. Kernel couldn't be just iteratively looking into every process's Page Tables in order to find the Page Table Entry, pointing to frame 1. There should be some kind of reverse mapping from page frames to Page Table Entries.

THE ANSWER IS:

"The most significant and important change to page table management is the introduction of Reverse Mapping (rmap). Referring to it as “rmap” is deliberate as it is the common usage of the “acronym” and should not be confused with the -rmap tree developed by Rik van Riel which has many more alterations to the stock VM than just the reverse mapping.

In a single sentence, rmap grants the ability to locate all PTEs which map a particular page given just the struct page. In 2.4, the only way to find all PTEs which map a shared page, such as a memory mapped shared library, is to linearaly search all page tables belonging to all processes. This is far too expensive and Linux tries to avoid the problem by using the swap cache (see Section 11.4). This means that with many shared pages, Linux may have to swap out entire processes regardless of the page age and usage patterns. 2.6 instead has a PTE chain associated with every struct page which may be traversed to remove a page from all page tables that reference it. This way, pages in the LRU can be swapped out in an intelligent manner without resorting to swapping entire processes."

from Understanding the Linux Memory Management, "what's new in Linux2.6"

Diploblastic

FTR: adding a link to this useful article: lwn.net/Articles/23732 – Mammal

It would be better if the answer was posted as an answer, instead of edited into the question. – Hopi

Answer 1

Linux:

When swap file is used the Page Table Entry gets updated with one marked as invalid and holding information about where it is saved in the swap file. That is: an index to the swap_info array and an offset within the swap_map.

Example from (an a bit old) Page Table Entry type (pte_t) on a x86. Some of the bits are used as flags by the hardware:

Bit         Function
_PAGE_PRESENT   Page is resident in memory and not swapped out
_PAGE_PROTNONE  Page is resident but not accessable
_PAGE_RW        Set if the page may be written to
_PAGE_USER      Set if the page is accessible from user space
_PAGE_DIRTY     Set if the page is written to
_PAGE_ACCESSED  Set if the page is accessed

^{Table 3.1: Page Table Entry Protection and Status Bits}

See also another SO answer with a diagram of the x86-64 page table format. When the low bit = 0, the hardware ignores all the other bits, so the kernel can use them for anything. Even in a "present" entry, there are some guaranteed-ignored bits that aren't reserved for future hardware use, so the kernel can use them for its own purposes.

Presumably other architectures are similar.

---

In simple terms: A process points to a page, the page get updated. Thus the processes are, in effect, also updated. When the physical page get requested it is swapped in and thus all processes as well. The point being that the Page Table Entry is not removed when memory is swapped out.

You might find some of this useful:

• Gustavo Duarte: How The Kernel Manages Your Memory.

The kernel documentation included book of Mel Gorman (2007):

• 11.2 Mapping Page Table Entries to Swap Entries

• 3.2 Describing a Page Table Entry

• Red Hat on VM's Life of a page.

Prisage

First of all, thank you for your detailed answer and for links. I've already read most posts of Gustavo's blog before and relevant parts of Understaning Linux MM by Mel Gorman. Now looking into your other links. May be my question was not completely clear, so I've made an edit. I understand, that PTE gets updated, but to do that the kernel has to find it first. So, my question is how does it find the PTE, corresponding to a page frame and the process, owning it, given the page frame only? – Diploblastic

Aha, I found the answer in Mel Gorman's book! It's in the "What's new in Linux2.6": kernel.org/doc/gorman/html/understand/understand006.html#toc19! rmap was introduced for that purpose. Hm, I wonder how we lived before 2.6... – Diploblastic

@Bob: Great. Was about to update answer. (Got a bit sidetracked by another question ;).) I'll see if I get to update the answer as well. – Prisage

I came across the same problem.. I would like to know, is rmap same as Inverted Page table? If yes, then how is shared memory handled? since in shared memory one physical frame is mapped to many logical pages – Gelinas

Also I would like to know the role of TLB with Address space identifier (ASID) in this case. ASID is a unique ID assigned to each entry of TLB which specifies the ID of process that is using this frame. Won't this solve the issue? – Gelinas