Using Reverse Mapping

The real benefits of reverse mapping do not become clear until Chapter 18, which examines the implementation of swapping. There we will see that the kernel defines the try_to_unmap function, which is invoked to delete a specific physical page from the page tables of all processes by which the page is used. It is apparent that this is only possible with the data structures just described. Nevertheless, the implementation is influenced by many details of the swap layer, and this is why I won't go into how try_to_unmap works at this point.

page_referenced is an important function that puts the data structures of the reverse mapping scheme to good use. It counts the number of processes that have actively used a shared page recently by accessing it — this is different from the number of regions into which the page is mapped. Whereas the second quantity is mostly static, the first changes rapidly if the page is in active use.

The function is a multiplexer that invokes page_referenced_anon for anonymous pages or page_ referenced_file for pages from a file-based mapping. Both try to establish at how many places a page is used, but each adopts a different approach owing to the different underlying data structures.

Let's first look at the version for anonymous pages. We first need the page_lock_anon_vma helper function to find the associated list of regions by reference to a specific page instance (by reading the information discussed in the previous section from the data structure).

static struct anon_vma *page_lock_anon_vma(struct page *page) {

struct anon_vma *anon_vma = NULL; unsigned long anon_mapping;

anon_mapping = (unsigned long) page->mapping; if (!(anon_mapping & PAGE_MAPPING_ANON)) goto out;

anon_vma = (struct anon_vma *) (anon_mapping - PAGE_MAPPING_ANON); return anon_vma;

Once the code has ensured that the page->mapping pointer actually points to an anon_vma instance using the by-now-familiar trick (the least significant bit of the pointer must be set), page_mapped checks whether the page has been mapped at all (page->_mapcount must then be greater than or equal to 0). If so, the function returns a pointer to the anon_vma instance associated with the page.

page_referenced_anon makes use of this knowledge as follows:

mm/rmap.c static int page_referenced_anon(struct page *page) {

unsigned int mapcount; struct anon_vma *anon_vma; struct vm_area_struct *vma; int referenced = 0;

anon_vma = page_lock_anon_vma(page); if (!anon_vma)

return referenced;

mapcount = page_mapcount(page);

list_for_each_entry(vma, &anon_vma->head, anon_vma_node) {

referenced += page_referenced_one(page, vma, kmapcount); if (¡mapcount) break;

return referenced;

Once the matching anon_vma instance has been found, the kernel iterates over all regions in the list and invokes page_referenced_one for each one to return the number of places at which the page is used (some corrections are required when the system is swapping pages in and out, but these are not of interest here and are discussed in Section 18.7). The results are added together for all pages before the total is returned.14

page_referenced_one performs its task in two steps:

1. It finds the page table entry that points to the page. This is possible because not only the page instance but also the associated vm_area_struct is passed to page_referenced_one. The position in virtual address space at which the page is mapped can be determined from the latter variable.

14The kernel terminates its work when the number of references reaches the number of mappings held in mapcount as it makes no sense to continue searching. page_referenced_one automatically decrements the mapcount counter passed for each referenced page.

2. It checks whether the _page_accessed bit is set in the page table entry and then deletes the bit. This flag is set on each access to the page by the hardware (with the additional support of the kernel if required by the particular architecture). The reference counter is incremented by 1 if the bit is set; otherwise, it is left unchanged. As a result, frequently used pages have a high number of references, and the opposite is true for rarely used pages. The kernel is therefore able to decide immediately whether a page is important based on the number of references.

The approach adopted for checking the number of references for pages with file-based mapping is similar.

mm/rmap.c static int page_referenced_file(struct page *page) {

mapcount = page_mapcount(page);

vma_prio_tree_foreach(vma, &iter, &mapping->i_mmap, pgoff, pgoff) { if ((vma->vm_flags & (VM_LOCKED|VM_MAYSHARE))

referenced += page_referenced_one(page, vma, &mapcount); if (!mapcount) break;

return referenced;

The kernel invokes vm_prio_tree_foreach to iterate over all elements of the priority tree that store a region where the relevant page is included. As above, page_referenced_one is invoked for each page in order to collect all references. If a page is locked into memory (with vm_locked) and may be shared by processes (vm_mayshare), the reference value is increased further because pages of this kind should not be swapped out and are therefore given a bonus.

Continue reading here: Managing the Heap

Was this article helpful?

+2 0