VMA fields¶

We can subdividestructvm_area_struct fields by their purpose, which makes iteasier to explore their locking characteristics:

These fields describes the size, start and end of the VMA, and as such cannot bemodified without first being hidden from the reverse mapping since these fieldsare used to locate VMAs within the reverse mapping interval trees.

These are the core fields which describe the MM the VMA belongs to and its attributes.

These fields are present or not depending on whether the relevant kernelconfiguration option is set.

These fields are used to both place the VMA within the reverse mapping, and foranonymous mappings, to be able to access both relatedstructanon_vma objectsand thestructanon_vma in which folios mapped exclusively to this VMA shouldreside.

Locking rules¶

We establish basic locking rules when interacting with page tables:

• When changing a page table entry the page table lock for that page tablemust be held, except if you can safely assume nobody can access the pagetables concurrently (such as on invocation offree_pgtables()).

• Reads from and writes to page table entries must beappropriatelyatomic. See the section on atomicity below for details.

• Populating previously empty entries requires that the mmap or VMA locks areheld (read or write), doing so with only rmap locks would be dangerous (seethe warning below).

• As mentioned previously, zapping can be performed while simply keeping the VMAstable, that is holding any one of the mmap, VMA or rmap locks.

There are additional rules applicable when moving page tables, which we discussin the section on this topic below.

PTE-level page tables are different from page tables at other levels, and thereare extra requirements for accessing them:

• On 32-bit architectures, they may be in high memory (meaning they need to bemapped into kernel memory to be accessible).

• When empty, they can be unlinked and RCU-freed while holding an mmap lock orrmap lock for reading in combination with the PTE and PMD page table locks.In particular, this happens inretract_page_tables() when handlingMADV_COLLAPSE.So accessing PTE-level page tables requires at least holding an RCU read lock;but that only suffices for readers that can tolerate racing with concurrentpage table updates such that an empty PTE is observed (in a page table thathas actually already been detached and marked for RCU freeing) while anothernew page table has been installed in the same location and filled withentries. Writers normally need to take the PTE lock and revalidate that thePMD entry still refers to the same PTE-level page table.If the writer does not care whether it is the same PTE-level page table, itcan take the PMD lock and revalidate that the contents of pmd entry still meetthe requirements. In particular, this also happens inretract_page_tables()when handlingMADV_COLLAPSE.

To access PTE-level page tables, a helper likepte_offset_map_lock() orpte_offset_map() can be used depending on stability requirements.These map the page table into kernel memory if required, take the RCU lock, anddepending on variant, may also look up or acquire the PTE lock.See the comment on__pte_offset_map_lock().

Atomicity¶

Regardless of page table locks, the MMU hardware concurrently updates accessedand dirty bits (perhaps more, depending on architecture). Additionally, pagetable traversal operations in parallel (though holding the VMA stable) andfunctionality like GUP-fast locklessly traverses (that is reads) page tables,without even keeping the VMA stable at all.

When performing a page table traversal and keeping the VMA stable, whether aread must be performed once and only once or not depends on the architecture(for instance x86-64 does not require any special precautions).

If a write is being performed, or if a read informs whether a write takes place(on an installation of a page table entry say, for instance in__pud_install()), special care must always be taken. In these cases wecan never assume that page table locks give us entirely exclusive access, andmust retrieve page table entries once and only once.

If we are reading page table entries, then we need only ensure that the compilerdoes not rearrange our loads. This is achieved viapXXp_get()functions -pgdp_get(),p4dp_get(),pudp_get(),pmdp_get(), andptep_get().

Each of these usesREAD_ONCE() to guarantee that the compiler readsthe page table entry only once.

However, if we wish to manipulate an existing page table entry and care aboutthe previously stored data, we must go further and use an hardware atomicoperation as, for example, inptep_get_and_clear().

Equally, operations that do not rely on the VMA being held stable, such asGUP-fast (seegup_fast() and its various page table level handlers likegup_fast_pte_range()), must very carefully interact with page tableentries, using functions such asptep_get_lockless() and equivalent forhigher level page table levels.

Writes to page table entries must also be appropriately atomic, as establishedbyset_pXX() functions -set_pgd(),set_p4d(),set_pud(),set_pmd(), andset_pte().

Equally functions which clear page table entries must be appropriately atomic,as inpXX_clear() functions -pgd_clear(),p4d_clear(),pud_clear(),pmd_clear(), andpte_clear().

Page table installation¶

Page table installation is performed with the VMA held stable explicitly by anmmap or VMA lock in read or write mode (see the warning in the locking rulessection for details as to why).

When allocating a P4D, PUD or PMD and setting the relevant entry in the abovePGD, P4D or PUD, themm->page_table_lock must be held. This isacquired in__p4d_alloc(),__pud_alloc() and__pmd_alloc() respectively.

Allocating a PTE will either use themm->page_table_lock or, ifUSE_SPLIT_PMD_PTLOCKS is defined, a lock embedded in the PMDphysical page metadata in the form of astructptdesc, acquired bypmd_ptdesc() called frompmd_lock() and ultimately__pte_alloc().

Finally, modifying the contents of the PTE requires special treatment, as thePTE page table lock must be acquired whenever we want stable and exclusiveaccess to entries contained within a PTE, especially when we wish to modifythem.

This is performed viapte_offset_map_lock() which carefully checks toensure that the PTE hasn’t changed from under us, ultimately invokingpte_lockptr() to obtain a spin lock at PTE granularity contained withinthestructptdesc associated with the physical PTE page. The lockmust be released viapte_unmap_unlock().

When modifying data in ranges we typically only wish to allocate higher pagetables as necessary, using these locks to avoid races or overwriting anything,and set/clear data at the PTE level as required (for instance when page faultingor zapping).

A typical pattern taken when traversing page table entries to install a newmapping is to optimistically determine whether the page table entry in the tableabove is empty, if so, only then acquiring the page table lock and checkingagain to see if it was allocated underneath us.

This allows for a traversal with page table locks only being taken whenrequired. An example of this is__pud_alloc().

At the leaf page table, that is the PTE, we can’t entirely rely on this patternas we have separate PMD and PTE locks and a THP collapse for instance might haveeliminated the PMD entry as well as the PTE from under us.

This is why__pte_offset_map_lock() locklessly retrieves the PMD entryfor the PTE, carefully checking it is as expected, before acquiring thePTE-specific lock, and thenagain checking that the PMD entry is as expected.

If a THP collapse (or similar) were to occur then the lock on both pages wouldbe acquired, so we can ensure this is prevented while the PTE lock is held.

Installing entries this way ensures mutual exclusion on write.

Page table freeing¶

Tearing down page tables themselves is something that requires significantcare. There must be no way that page tables designated for removal can betraversed or referenced by concurrent tasks.

It is insufficient to simply hold an mmap write lock and VMA lock (which willprevent racing faults, and rmap operations), as a file-backed mapping can betruncated under thestructaddress_space->i_mmap_rwsem alone.

As a result, no VMA which can be accessed via the reverse mapping (eitherthrough thestructanon_vma->rb_root or thestructaddress_space->i_mmap interval trees) can have its page tables torn down.

The operation is typically performed viafree_pgtables(), which assumeseither the mmap write lock has been taken (as specified by itsmm_wr_locked parameter), or that the VMA is already unreachable.

It carefully removes the VMA from all reverse mappings, however it’s importantthat no new ones overlap these or any route remain to permit access to addresseswithin the range whose page tables are being torn down.

Additionally, it assumes that a zap has already been performed and steps havebeen taken to ensure that no further page table entries can be installed betweenthe zap and the invocation offree_pgtables().

Since it is assumed that all such steps have been taken, page table entries arecleared without page table locks (in thepgd_clear(),p4d_clear(),pud_clear(), andpmd_clear() functions.

Page table moving¶

Some functions manipulate page table levels above PMD (that is PUD, P4D and PGDpage tables). Most notable of these ismremap(), which is capable ofmoving higher level page tables.

In these instances, it is required thatall locks are taken, that isthe mmap lock, the VMA lock and the relevant rmap locks.

You can observe this in themremap() implementation in the functionstake_rmap_locks() anddrop_rmap_locks() which perform the rmapside of lock acquisition, invoked ultimately bymove_page_tables().

Overview¶

VMA read locking is entirely optimistic - if the lock is contended or a competingwrite has started, then we do not obtain a read lock.

A VMAread lock is obtained bylock_vma_under_rcu(), which firstcallsrcu_read_lock() to ensure that the VMA is looked up in an RCUcritical section, then attempts to VMA lock it viavma_start_read(),before releasing the RCU lock viarcu_read_unlock().

In cases when the user already holds mmap read lock,vma_start_read_locked()andvma_start_read_locked_nested() can be used. These functions do notfail due to lock contention but the caller should still check their return valuesin case they fail for other reasons.

VMA read locks incrementvma.vm_refcnt reference counter for theirduration and the caller oflock_vma_under_rcu() must drop it viavma_end_read().

VMAwrite locks are acquired viavma_start_write() in instances where aVMA is about to be modified, unlikevma_start_read() the lock is alwaysacquired. An mmap write lockmust be held for the duration of the VMA writelock, releasing or downgrading the mmap write lock also releases the VMA writelock so there is novma_end_write() function.

Note that when write-locking a VMA lock, thevma.vm_refcnt is temporarilymodified so that readers can detect the presense of a writer. The reference counter isrestored once the vma sequence number used for serialisation is updated.

This ensures the semantics we require - VMA write locks provide exclusive writeaccess to the VMA.

Implementation details¶

The VMA lock mechanism is designed to be a lightweight means of avoiding the useof the heavily contended mmap lock. It is implemented using a combination of areference counter and sequence numbers belonging to the containingstructmm_struct and the VMA.

Read locks are acquired viavma_start_read(), which is an optimisticoperation, i.e. it tries to acquire a read lock but returns false if it isunable to do so. At the end of the read operation,vma_end_read() iscalled to release the VMA read lock.

Invokingvma_start_read() requires thatrcu_read_lock() hasbeen called first, establishing that we are in an RCU critical section upon VMAread lock acquisition. Once acquired, the RCU lock can be released as it is onlyrequired for lookup. This is abstracted bylock_vma_under_rcu() whichis the interface a user should use.

Writing requires the mmap to be write-locked and the VMA lock to be acquired viavma_start_write(), however the write lock is released by the termination ordowngrade of the mmap write lock so novma_end_write() is required.

All this is achieved by the use of per-mm and per-VMA sequence counts, which areused in order to reduce complexity, especially for operations which write-lockmultiple VMAs at once.

If the mm sequence count,mm->mm_lock_seq is equal to the VMAsequence countvma->vm_lock_seq then the VMA is write-locked. Ifthey differ, then it is not.

Each time the mmap write lock is released inmmap_write_unlock() ormmap_write_downgrade(),vma_end_write_all() is invoked whichalso incrementsmm->mm_lock_seq viamm_lock_seqcount_end().

This way, we ensure that, regardless of the VMA’s sequence number, a write lockis never incorrectly indicated and that when we release an mmap write lock weefficiently releaseall VMA write locks contained within the mmap at thesame time.

Since the mmap write lock is exclusive against others who hold it, the automaticrelease of any VMA locks on its release makes sense, as you would never want tokeep VMAs locked across entirely separate write operations. It also maintainscorrect lock ordering.

Each time a VMA read lock is acquired, we incrementvma.vm_refcntreference counter and check that the sequence count of the VMA does not matchthat of the mm.

If it does, the read lock fails andvma.vm_refcnt is dropped.If it does not, we keep the reference counter raised, excluding writers, butpermitting other readers, who can also obtain this lock under RCU.

Importantly, maple tree operations performed inlock_vma_under_rcu()are also RCU safe, so the whole read lock operation is guaranteed to functioncorrectly.

On the write side, we set a bit invma.vm_refcnt which can’t bemodified by readers and wait for all readers to drop their reference count.Once there are no readers, the VMA’s sequence number is set to match that ofthe mm. During this entire operation mmap write lock is held.

This way, if any read locks are in effect,vma_start_write() will sleepuntil these are finished and mutual exclusion is achieved.

After setting the VMA’s sequence number, the bit invma.vm_refcntindicating a writer is cleared. From this point on, VMA’s sequence number willindicate VMA’s write-locked state until mmap write lock is dropped or downgraded.

This clever combination of a reference counter and sequence count allows forfast RCU-based per-VMA lock acquisition (especially on page fault, thoughutilised elsewhere) with minimal complexity around lock ordering.