Data Structures

The kernel uses lean data structures to minimize management overhead for reverse mappings. The page structure (discussed in Section 3.2.2) contains a single element to implement reverse mapping.

mm.h struct page {

atomic_t _mapcount; /* Count of ptes mapped in mms,

* to show when page is mapped

_mapcount indicates at how many points the page is shared. The original value of the counter is -1. It is assigned the value 0 when the page is inserted in the reverse mapping data structures and is incremented by 1 for each additional user. This enables the kernel to check quickly how many users are using the page in addition to the owner.

Obviously, this isn't much help because the purpose of reverse mapping is to find all points at which the physical page is used by reference to a given page instance. Consequently, two other data structures have a role to play:

1. The priority search tree in which each region belonging to a non-anonymous mapping is embedded

2. The linked lists of anonymous areas that lead back to the same pages in memory

The elements needed to generate both data structures are integrated in vm_area_struct — these are the shared union as well as anon_vma_node and anon_vma. To refresh the reader's memory, I reproduce the corresponding section from vm_area_struct below.

mm.h struct vm_area_struct {

* For areas with an address space and backing store,

* linkage into the address_space->i_mmap prio tree, or

* linkage to the list of like vmas hanging off its node, or

* linkage of vma in the address_space->i_mmap_nonlinear list. */

union {

struct {

struct list_head list;

void *parent; /* aligns with prio_tree_node parent */ struct vm_area_struct *head; } vm_set;

struct raw_prio_tree_node prio_tree_node;

* A file's MAP_PRIVATE vma can be

* list, after a COW of one of the

* can only be in the i_mmap tree.

struct list_head anon_vma_node; /* struct anon_vma *anon_vma; /*

in both i_mmap tree and anon_vma file pages. A MAP_SHARED vma An anonymous MAP_PRIVATE, stack only be in an anon_vma list.

Serialized by anon_vma->lock */ Serialized by page_table_lock */

The trick employed by the kernel when implementing reverse mapping is not to store a direct link between a page and the associated users but only the association between a page and the region in which the page is located. All other regions in which the page is included (and therefore all users) can be found by means of the data structures just mentioned. This method is also known as object-based reverse mapping because no direct link between page and user is stored; instead, a further object (the regions in which the page is located) is interposed between the two.

Continue reading here: Creating a Reverse Mapping

Was this article helpful?

0 0