Reverse Mapping

The data structures already discussed enable the kernel to establish a link between a virtual and a physical address (via the page tables) and between a memory region of a process and its virtual page addresses. What is still missing is a link between a physical page and the processes to which the page belongs (or, to be more accurate, to the page table entries of all processes that use the page). This is the very link that is needed when swapping pages out (see Chapter 18) in order to update all processes that use the page because the fact that the page has been swapped out must be noted in their page tables.

In this context, it is necessary to distinguish between two similar terms:

1. When a page is mapped, it is associated with a process but need not necessarily be in active use.

2. The number of references to a page indicates how actively the page is used. In order to determine this number, the kernel must first establish a link between a page and all its users and must then resort to a few tricks to find out how actively the page is used.

The first task is therefore to create a link between a page and all points at which it is mapped. To do this, the kernel uses a few additional data structures and functions and adopts a reverse mapping approach.13

All mapping actions described above are concerned only with virtual pages, and there was therefore no need (and no way) to create reverse mappings. The discussion of how the kernel handles page faults and

13Reverse mappings were first introduced during the development of kernel 2.5. They were available as separate patches for 2.4 but had never been included in the standard sources. Swapping-out of shared pages is much more complicated and inefficient without this mechanism because the shared page had to be kept in a special cache until the kernel had chosen separately (and independently) to swap the page out for all processes involved. The implementation of the reverse mapping algorithm was also heavily revised during the development of kernel 2.6.

assigns physical pages to hold mapping data in Section 4.10 notes that there is then a need for reverse mapping.

Continue reading here: Data Structures

Was this article helpful?

0 0