fix vma->anon_vma check for per-VMA locking; fix anon_vma memory ordering
Subsystems (8)
Jann Horn
reviewercover fix vma->anon_vma check for per-VMA locking; fix anon_vma memory ordering
Hi!
Patch 1 here is a straightforward fix for a race in per-VMA locking code that can lead to use-after-free; I hope we can get this one into mainline and stable quickly.
Patch 2 is a fix for what I believe is a longstanding memory ordering issue in how vma->anon_vma is used across the MM subsystem; I expect that this one will have to go through a few iterations of review and potentially rewrites, because memory ordering is tricky. (If someone else wants to take over patch 2, I would be very happy.)
These patches don't really belong together all that much, I'm just sending them as a series because they'd otherwise conflict.
I am CCing:
- Suren because patch 1 touches his code
- Matthew Wilcox because he is also currently working on per-VMA locking stuff
- all the maintainers/reviewers for the Kernel Memory Consistency Model so they can help figure out the READ_ONCE() vs smp_load_acquire() thing
- people involved in the previous discussion on the security list
Jann Horn (2):
mm: lock_vma_under_rcu() must check vma->anon_vma under vma lock
mm: Fix anon_vma memory ordering
include/linux/rmap.h | 15 ++++++++++++++- mm/huge_memory.c | 4 +++- mm/khugepaged.c | 2 +- mm/ksm.c | 16 +++++++++++----- mm/memory.c | 32 ++++++++++++++++++++------------ mm/mmap.c | 13 ++++++++++--- mm/rmap.c | 6 ++++-- mm/swapfile.c | 3 ++- 8 files changed, 65 insertions(+), 26 deletions(-)
base-commit: 20ea1e7d13c1b544fe67c4a8dc3943bb1ab33e6f
Signature · 1 line
2.41.0.487.g6d72f3e995-goog
Jann Horn
reviewerPATCH 1/2 mm: lock_vma_under_rcu() must check vma->anon_vma under vma lock
lock_vma_under_rcu() tries to guarantee that __anon_vma_prepare() can't be called in the VMA-locked page fault path by ensuring that vma->anon_vma is set.
However, this check happens before the VMA is locked, which means a concurrent move_vma() can concurrently call unlink_anon_vmas(), which disassociates the VMA's anon_vma.
This means we can get UAF in the following scenario:
THREAD 1 THREAD 2
======== ========
<page fault>
lock_vma_under_rcu()
rcu_read_lock()
mas_walk()
check vma->anon_vma
mremap() syscall
move_vma()
vma_start_write()
unlink_anon_vmas()
<syscall end>
handle_mm_fault()
__handle_mm_fault()
handle_pte_fault()
do_pte_missing()
do_anonymous_page()
anon_vma_prepare()
__anon_vma_prepare()
find_mergeable_anon_vma()
mas_walk() [looks up VMA X]
munmap() syscall (deletes VMA X)
reusable_anon_vma() [called on freed VMA X]This is a security bug if you can hit it, although an attacker would have to win two races at once where the first race window is only a few instructions wide.
This patch is based on some previous discussion with Linus Torvalds on the security list.
--- mm/memory.c | 28 ++++++++++++++++------------ 1 file changed, 16 insertions(+), 12 deletions(-)
mm/memory.c +16 -12
@@ -5393,27 +5393,28 @@ struct vm_area_struct *lock_vma_under_rcu(struct mm_struct *mm,if (!vma_is_anonymous (vma) && !vma_is_tcp (vma)) goto inval; -/* find_mergeable_anon_vma uses adjacent vmas which are not locked */ -if (!vma->anon_vma && !vma_is_tcp (vma)) - goto inval; -if (!vma_start_read (vma)) goto inval; +/* +* find_mergeable_anon_vma uses adjacent vmas which are not locked. +* This check must happen after vma_start_read(); otherwise, a +* concurrent mremap() with MREMAP_DONTUNMAP could dissociate the VMA +* from its anon_vma. +*/ +if (unlikely (!vma->anon_vma && !vma_is_tcp (vma))) + goto inval_end_read; +/* * Due to the possibility of userfault handler dropping mmap_lock, avoid * it for now and fall back to page fault handling under mmap_lock. */ -if (userfaultfd_armed (vma)) { -vma_end_read (vma); - goto inval; - } +if (userfaultfd_armed (vma)) + goto inval_end_read;/* Check since vm_start/vm_end might change before we lock the VMA */ -if (unlikely (address < vma->vm_start || address >= vma->vm_end)) { -vma_end_read (vma); - goto inval; - } +if (unlikely (address < vma->vm_start || address >= vma->vm_end)) + goto inval_end_read;/* Check if the VMA got isolated after we found it */ if (vma->detached) {
@@ -5425,6 +5426,9 @@ struct vm_area_struct *lock_vma_under_rcu(struct mm_struct *mm,rcu_read_unlock ();return vma; + +inval_end_read: +vma_end_read (vma); inval:rcu_read_unlock ();count_vm_vma_lock_event (VMA_LOCK_ABORT );
Signature · 1 line
2.41.0.487.g6d72f3e995-goog
Re: [PATCH 1/2] mm: lock_vma_under_rcu() must check vma->anon_vma under vma lock
Quoted 42 lines · Jann Horn
lock_vma_under_rcu()tries to guarantee that__anon_vma_prepare()can't be called in the VMA-locked page fault path by ensuring thatvma->anon_vmais set.
However, this check happens before the VMA is locked, which means a concurrentmove_vma()can concurrently callunlink_anon_vmas(), which disassociates the VMA'sanon_vma.This means we can get UAF in the following scenario:
THREAD 1 THREAD 2
======== ========
<page fault>lock_vma_under_rcu() rcu_read_lock() mas_walk() check vma->anon_vma mremap() syscall move_vma() vma_start_write() unlink_anon_vmas() <syscall end> handle_mm_fault() __handle_mm_fault() handle_pte_fault() do_pte_missing() do_anonymous_page() anon_vma_prepare() __anon_vma_prepare() find_mergeable_anon_vma() mas_walk() [looks up VMA X] munmap() syscall (deletes VMA X) reusable_anon_vma() [called on freed VMA X]This is a security bug if you can hit it, although an attacker would have to win two races at once where the first race window is only a few instructions wide.
Quoted 6 lines
This patch is based on some previous discussion with Linus Torvalds on the security list.
Fixes 5e31275cc997 ("mm: add per-VMA lock and helper functions to control it")Signed-off-by Jann Horn <[email protected]>
Quoted 62 lines
--- mm/memory.c | 28 ++++++++++++++++------------ 1 file changed, 16 insertions(+), 12 deletions(-)mm/memory.c +16
-13@@ -5393,27 +5393,28 @@ struct vm_area_struct *lock_vma_under_rcu(struct mm_struct *mm,if (!vma_is_anonymous (vma) && !vma_is_tcp (vma)) goto inval; -/* find_mergeable_anon_vma uses adjacent vmas which are not locked */ -if (!vma->anon_vma && !vma_is_tcp (vma)) - goto inval; -if (!vma_start_read (vma)) goto inval; +/* +* find_mergeable_anon_vma uses adjacent vmas which are not locked. +* This check must happen after vma_start_read(); otherwise, a +* concurrent mremap() with MREMAP_DONTUNMAP could dissociate the VMA +* from its anon_vma. +*/ +if (unlikely (!vma->anon_vma && !vma_is_tcp (vma))) + goto inval_end_read; +/* * Due to the possibility of userfault handler dropping mmap_lock, avoid * it for now and fall back to page fault handling under mmap_lock. */ -if (userfaultfd_armed (vma)) { -vma_end_read (vma); - goto inval; - } +if (userfaultfd_armed (vma)) + goto inval_end_read;/* Check since vm_start/vm_end might change before we lock the VMA */ -if (unlikely (address < vma->vm_start || address >= vma->vm_end)) { -vma_end_read (vma); - goto inval; - } +if (unlikely (address < vma->vm_start || address >= vma->vm_end)) + goto inval_end_read;/* Check if the VMA got isolated after we found it */ if (vma->detached) {@@ -5425,6 +5426,9 @@ struct vm_area_struct *lock_vma_under_rcu(struct mm_struct *mm,rcu_read_unlock ();return vma; + +inval_end_read: +vma_end_read (vma); inval:rcu_read_unlock ();count_vm_vma_lock_event (VMA_LOCK_ABORT ); --2.41.0.487.g6d72f3e995-goog
Jann Horn
reviewerPATCH 2/2 mm: Fix anon_vma memory ordering
In reply to Jann HornA read of vma->anon_vma under mmap_lock in read mode (in particular in anon_vma_prepare()) can race with a concurrent update under mmap_lock in read mode plus pagetable lock (in __prepare_anon_vma()). However, the only allowed concurrent update is one that changes vma->anon_vma from NULL to a non-NULL pointer; once vma->anon_vma has been set to a non-NULL value, it will keep that value as long as the mmap lock is held in read mode.
This clearly means that we need an smp_store_release() in __prepare_anon_vma() (unless we happen to have some equivalent barrier there, which doesn't seem to be the case).
The harder choice is what to do for all the readers.
In the page fault path, we probably want to only have a single piece of code (in __prepare_anon_vma()) that has to deal with ensuring that vma->anon_vma is stable, and then be able to use it with normal memory accesses afterwards.
One way we can do this is with smp_load_acquire(), which is what this patch does; however, I expect that we can have a lot of bikeshedding on whether that is the right barrier to use and whether it should be moved into a helper function for other places outside the page fault path that look at vma->anon_vma in read mode.
The other approach is to use read-dependency ordering with READ_ONCE(), maybe combined with a barrier() afterwards to prevent compiler reordering. Based on some discussion we had on the security list (and in particular repeating much of what Linus explained), this would probably be correct on all currently-supported architectures, because reads from the same location are guaranteed to not be reordered by the CPU (I think?), so subsequent loads from the same location would be guaranteed to see the same value for vma->anon_vma.
And then on anything other than alpha, we'd get implicit address-dependency ordering against the plain load; while on alpha, we have a memory barrier inside the READ_ONCE().
Since smp_load_acquire() is allegedly fairly cheap on the main architectures with weak memory ordering, and the reasoning for why READ_ONCE() works is kinda iffy, I figured I should use READ_ONCE() for v1 of the patch and then we can bikeshed it from there.
Also I tried looking through every single access to vma->anon_vma and put smp_load_acquire() on every one that might reasonably need it, but again we can probably bikeshed on that.
--- include/linux/rmap.h | 15 ++++++++++++++- mm/huge_memory.c | 4 +++- mm/khugepaged.c | 2 +- mm/ksm.c | 16 +++++++++++----- mm/memory.c | 6 +++++- mm/mmap.c | 13 ++++++++++--- mm/rmap.c | 6 ++++-- mm/swapfile.c | 3 ++- 8 files changed, 50 insertions(+), 15 deletions(-)
include/linux/rmap.h +14 -1
@@ -153,9 +153,22 @@ int anon_vma_fork(struct vm_area_struct *, struct vm_area_struct *);static inline int anon_vma_prepare (struct vm_area_struct *vma) { -if (likely (vma->anon_vma)) +/* +* Pairs with smp_store_release() in __anon_vma_prepare(). +* +* Holding the mmap lock in read mode guarantees that the only possible +* concurrent modification of vma->anon_vma is that it changes from NULL +* to another value. Therefore, if we see a non-NULL value here, future +* plain loads of vma->anon_vma are okay. +*/ +if (likely (smp_load_acquire (&vma->anon_vma)))return 0 ; +/* +* If __anon_vma_prepare() succeeds, it has loaded or stored a non-NULL +* value in vma->anon_vma while protected against concurrent changes by +* the page table lock. +*/ return __anon_vma_prepare (vma); }
mm/huge_memory.c +3 -1
@@ -144,8 +144,10 @@ bool hugepage_vma_check(struct vm_area_struct *vma, unsigned long vm_flags,* * Allow page fault since anon_vma may be not initialized until * the first page fault. +* +* See anon_vma_prepare() for barrier. */ -if (!vma->anon_vma) +if (!smp_load_acquire (&vma->anon_vma))return (smaps || in_pf);return true;
mm/khugepaged.c +1 -1
@@ -939,7 +939,7 @@ static int hugepage_vma_revalidate(struct mm_struct *mm, unsigned long address,* hugepage_vma_check may return true for qualified file * vmas. */ -if (expect_anon && (!(*vmap)->anon_vma || !vma_is_anonymous (*vmap))) +if (expect_anon && (!smp_load_acquire (&vma->anon_vma) || !vma_is_anonymous (vma)))return SCAN_PAGE_ANON ;return SCAN_SUCCEED ; }
mm/ksm.c +11 -5
@@ -545,7 +545,9 @@ static struct vm_area_struct *find_mergeable_vma(struct mm_struct *mm,if (ksm_test_exit (mm))return NULL ; vma =vma_lookup (mm, addr); -if (!vma || !(vma->vm_flags &VM_MERGEABLE ) || !vma->anon_vma) +/* see anon_vma_prepare() */ +if (!vma || !(vma->vm_flags &VM_MERGEABLE ) || + !smp_load_acquire (&vma->anon_vma))return NULL ;return vma; }
@@ -1026,7 +1028,8 @@ static int unmerge_and_remove_all_rmap_items(void) goto mm_exiting;for_each_vma (vmi, vma) { -if (!(vma->vm_flags &VM_MERGEABLE ) || !vma->anon_vma) +if (!(vma->vm_flags &VM_MERGEABLE ) || + !smp_load_acquire (&vma->anon_vma))continue ; err =unmerge_ksm_pages (vma, vma->vm_start, vma->vm_end);
@@ -2367,7 +2370,8 @@ static struct ksm_rmap_item *scan_get_next_rmap_item(struct page **page)continue ;if (ksm_scan.address < vma->vm_start) ksm_scan.address = vma->vm_start; -if (!vma->anon_vma) +/* see anon_vma_prepare() */ +if (!smp_load_acquire (&vma->anon_vma)) ksm_scan.address = vma->vm_end;while (ksm_scan.address < vma->vm_end) {
@@ -2529,7 +2533,8 @@ static int __ksm_del_vma(struct vm_area_struct *vma)if (!(vma->vm_flags &VM_MERGEABLE ))return 0 ; -if (vma->anon_vma) { +/* see anon_vma_prepare() */ +if (smp_load_acquire (&vma->anon_vma)) { err =unmerge_ksm_pages (vma, vma->vm_start, vma->vm_end);if (err)return err;
@@ -2667,7 +2672,8 @@ int ksm_madvise(struct vm_area_struct *vma, unsigned long start,if (!(*vm_flags &VM_MERGEABLE ))return 0 ;/* just ignore the advice */ -if (vma->anon_vma) { +/* see anon_vma_prepare() */ +if (smp_load_acquire (&vma->anon_vma)) { err =unmerge_ksm_pages (vma, start, end);if (err)return err;
mm/memory.c +5 -1
@@ -5401,8 +5401,12 @@ struct vm_area_struct *lock_vma_under_rcu(struct mm_struct *mm,* This check must happen after vma_start_read(); otherwise, a * concurrent mremap() with MREMAP_DONTUNMAP could dissociate the VMA * from its anon_vma. +* +* We don't rely on the READ_ONCE() here for ordering; we're guaranteed +* to go through anon_vma_prepare() before we actually access +* vma->anon_vma. */ -if (unlikely (!vma->anon_vma && !vma_is_tcp (vma))) +if (unlikely (!READ_ONCE (vma->anon_vma) && !vma_is_tcp (vma))) goto inval_end_read;/*
mm/mmap.c +10 -3
@@ -1057,8 +1057,7 @@ static int anon_vma_compatible(struct vm_area_struct *a, struct vm_area_struct ** the anon_vma of 'old' is concurrently in the process of being set up * by another page fault trying to merge _that_. But that's ok: if it * is being set up, that automatically means that it will be a singleton -* acceptable for merging, so we can do all of this optimistically. But -* we do that READ_ONCE() to make sure that we never re-load the pointer. +* acceptable for merging, so we can do all of this optimistically. * * IOW: that the "list_is_singular()" test on the anon_vma_chain only * matters for the 'stable anon_vma' case (ie the thing we want to avoid
@@ -1072,7 +1071,15 @@ static int anon_vma_compatible(struct vm_area_struct *a, struct vm_area_struct *static struct anon_vma *reusable_anon_vma (struct vm_area_struct *old,struct vm_area_struct *a,struct vm_area_struct *b) {if (anon_vma_compatible (a, b)) { -struct anon_vma *anon_vma =READ_ONCE (old->anon_vma); +/* +* Pairs with smp_store_release() in __anon_vma_prepare(). +* +* We could get away with a READ_ONCE() here, but +* smp_load_acquire() ensures that the following +* list_is_singular() check on old->anon_vma_chain doesn't race +* with __anon_vma_prepare(). +*/ +struct anon_vma *anon_vma =smp_load_acquire (&old->anon_vma);if (anon_vma &&list_is_singular (&old->anon_vma_chain))return anon_vma;
mm/rmap.c +4 -2
@@ -210,8 +210,9 @@ int __anon_vma_prepare(struct vm_area_struct *vma)anon_vma_lock_write (anon_vma);/* page_table_lock to protect against threads */ spin_lock (&mm->page_table_lock); +/* no need for smp_load_acquire() here, the lock prevents concurrency */ if (likely (!vma->anon_vma)) { - vma->anon_vma = anon_vma; +smp_store_release (&vma->anon_vma, anon_vma);anon_vma_chain_link (vma, avc, anon_vma); anon_vma->num_active_vmas++; allocated =NULL ;
@@ -755,8 +756,9 @@ unsigned long page_address_in_vma(struct page *page, struct vm_area_struct *vma)/* * Note: swapoff's unuse_vma() is more efficient with this * check, and needs it to match anon_vma when KSM is active. +* See anon_vma_prepare() for barrier. */ -if (!vma->anon_vma || !page__anon_vma || +if (!smp_load_acquire (&vma->anon_vma) || !page__anon_vma || vma->anon_vma->root != page__anon_vma->root)return -EFAULT ; }else if (!vma->vm_file) {
mm/swapfile.c +2 -1
@@ -1986,7 +1986,8 @@ static int unuse_mm(struct mm_struct *mm, unsigned int type)mmap_read_lock (mm);for_each_vma (vmi, vma) { -if (vma->anon_vma) { +/* see anon_vma_prepare() */ +if (smp_load_acquire (&vma->anon_vma)) { ret =unuse_vma (vma, type);if (ret)break ;
Signature · 1 line
2.41.0.487.g6d72f3e995-goog
Jann Horn
reviewerRe: [PATCH 2/2] mm: Fix anon_vma memory ordering
Quoted 7 lines · Jann Horn
A read of
vma->anon_vmaundermmap_lockin read mode (in particular inanon_vma_prepare()) can race with a concurrent update undermmap_lockin read mode plus pagetable lock (in__prepare_anon_vma()). However, the only allowed concurrent update is one that changesvma->anon_vmafrom NULL to a non-NULL pointer; oncevma->anon_vmahas been set to a non-NULL value, it will keep that value as long as the mmap lock is held in read mode.
[...]
mm/mmap.c static int anon_vma_compatible(struct vm_area_struct *a, struct vm_area_struct * · line 1080
Quoted 12 lines
mm/mmap.c +7
-1@@ -1072,7 +1071,15 @@ static int anon_vma_compatible(struct vm_area_struct *a, struct vm_area_struct *static struct anon_vma *reusable_anon_vma (struct vm_area_struct *old,struct vm_area_struct *a,struct vm_area_struct *b) {if (anon_vma_compatible (a, b)) { -struct anon_vma *anon_vma =READ_ONCE (old->anon_vma); +/* +* Pairs with smp_store_release() in __anon_vma_prepare(). +* +* We could get away with a READ_ONCE() here, but +* smp_load_acquire() ensures that the following +* list_is_singular() check on old->anon_vma_chain doesn't race +* with __anon_vma_prepare().
Of course I only realize directly after sending this patch that this comment only holds...
Quoted 10 lines
mm/mmap.c +2
-0+*/ +struct anon_vma *anon_vma =smp_load_acquire (&old->anon_vma);if (anon_vma &&list_is_singular (&old->anon_vma_chain))return anon_vma;mm/rmap.c +0
-0
mm/rmap.c int __anon_vma_prepare(struct vm_area_struct *vma) · line 216
Quoted 8 lines
mm/rmap.c +2
-1@@ -210,8 +210,9 @@ int __anon_vma_prepare(struct vm_area_struct *vma)anon_vma_lock_write (anon_vma);/* page_table_lock to protect against threads */ spin_lock (&mm->page_table_lock); +/* no need for smp_load_acquire() here, the lock prevents concurrency */ if (likely (!vma->anon_vma)) { - vma->anon_vma = anon_vma; +smp_store_release (&vma->anon_vma, anon_vma);anon_vma_chain_link (vma, avc, anon_vma);
... if we move the smp_store_release() down by one line here.
Quoted 2 lines
mm/rmap.c +0
-0anon_vma->num_active_vmas++; allocated =NULL ;
Re: [PATCH 2/2] mm: Fix anon_vma memory ordering
Quoted 4 lines · Jann Horn
Of course I only realize directly after sending this patch that this comment only holds... [..]
... if we move thesmp_store_release()down by one line here.
So I've applied PATCH 1/2 as obvious, but am holding off on this one.
Partly because of the other discussion about memory ordering, but also due to how the now sometimes much more complex-looking conditionals could be made a bit visually simpler.
For example the patch does
- if (!vma || !(vma->vm_flags & VM_MERGEABLE) || !vma->anon_vma)
+ /* see anon_vma_prepare() */
+ if (!vma || !(vma->vm_flags & VM_MERGEABLE) ||
+ !smp_load_acquire(&vma->anon_vma))
return NULL;which is a understandably mindless "just add the smp_load_acquire()", but it is also just unnecessarily hard to read.
And the comment placement is a bit misleading too, since it really only refers to one part of the expression. And that's very obvious if you know what it's about, but the whole point of that comment would be that you don't necessarily know why the code is doing what it is doing.
IOW, that would be much more legible just split up as
if (!vma || !(vma->vm_flags & VM_MERGEABLE))
return NULL;
/* see anon_vma_prepare() */
if (!smp_load_acquire(&vma->anon_vma))
return NULL;I feel.
Also, I'm now wondering about the ordering of that
Quoted 2 lines
smp_store_release(&vma->anon_vma, anon_vma);
anon_vma_chain_link(vma, avc, anon_vma);sequence. Maybe we *do* want the anon_vma pointer to be set first, so that once it's on that anon_vma chain (and is visible in the anon_vma interval tree) it always has a proper anon_vma pointer.
*OR* maybe the rule needs to be that any other concurrent user that sees 'anon_vma' as being valid also can rely on the links being set up?
I *suspect* the ordering doesn't actually matter, but it just makes me wonder more about this area.
Linus
Quoted 15 lines · Jann Horn
Hi!
Patch 1 here is a straightforward fix for a race in per-VMA locking code that can lead to use-after-free; I hope we can get this one into mainline and stable quickly.
Patch 2 is a fix for what I believe is a longstanding memory ordering issue in how
vma->anon_vmais used across the MM subsystem; I expect that this one will have to go through a few iterations of review and potentially rewrites, because memory ordering is tricky. (If someone else wants to take over patch 2, I would be very happy.)These patches don't really belong together all that much, I'm just sending them as a series because they'd otherwise conflict.
Quoted 8 lines
I am CCing:
- Suren because patch 1 touches his code
- Matthew Wilcox because he is also currently working on per-VMA locking stuff
- all the maintainers/reviewers for the Kernel Memory Consistency Model so they can help figure out theREAD_ONCE()vssmp_load_acquire()thing
READ_ONCE() has weaker ordering properties than smp_load_acquire().
For example, given a pointer gp:
p = whichever(gp); a = 1; r1 = p->b; if ((uintptr_t)p & 0x1) WRITE_ONCE(b, 1); WRITE_ONCE(c, 1);
Leaving aside the "&" needed by smp_load_acquire(), if "whichever" is "READ_ONCE", then the load from p->b and the WRITE_ONCE() to "b" are ordered after the load from gp (the former due to an address dependency and the latter due to a (fragile) control dependency). The compiler is within its rights to reorder the store to "a" to precede the load from gp. The compiler is forbidden from reordering the store to "c" wtih the load from gp (because both are volatile accesses), but the CPU is completely within its rights to do this reordering.
But if "whichever" is "smp_load_acquire()", all four of the subsequent memory accesses are ordered after the load from gp.
Similarly, for WRITE_ONCE() and smp_store_release():
p = READ_ONCE(gp); r1 = READ_ONCE(gi); r2 = READ_ONCE(gj); a = 1; WRITE_ONCE(b, 1); if (r1 & 0x1) whichever(p->q, r2);
Again leaving aside the "&" needed by smp_store_release(), if "whichever" is WRITE_ONCE(), then the load from gp, the load from gi, and the load from gj are all ordered before the store to p->q (by address dependency, control dependency, and data dependency, respectively). The store to "a" can be reordered with the store to p->q by the compiler. The store to "b" cannot be reordered with the store to p->q by the compiler (again, both are volatile), but the CPU is free to reorder them, especially when whichever() is implemented as a conditional store.
But if "whichever" is "smp_store_release()", all five of the earlier memory accesses are ordered before the store to p->q.
Does that help, or am I missing the point of your question?
Thanx, Paul
Quoted 22 lines
- people involved in the previous discussion on the security list
Jann Horn (2):
mm:lock_vma_under_rcu()must checkvma->anon_vmaunder vma lock
mm: Fixanon_vmamemory orderinginclude/linux/rmap.h | 15 ++++++++++++++- mm/huge_memory.c | 4 +++- mm/khugepaged.c | 2 +- mm/ksm.c | 16 +++++++++++----- mm/memory.c | 32 ++++++++++++++++++++------------ mm/mmap.c | 13 ++++++++++--- mm/rmap.c | 6 ++++-- mm/swapfile.c | 3 ++- 8 files changed, 65 insertions(+), 26 deletions(-)base-commit:
20ea1e7d13c1b544fe67c4a8dc3943bb1ab33e6fSignature · 1 line
2.41.0.487.g6d72f3e995-goog
Jann Horn
reviewerQuoted 68 lines · Paul E. McKenney
Quoted 15 lines · Jann Horn
Hi!
Patch 1 here is a straightforward fix for a race in per-VMA locking code that can lead to use-after-free; I hope we can get this one into mainline and stable quickly.
Patch 2 is a fix for what I believe is a longstanding memory ordering issue in how
vma->anon_vmais used across the MM subsystem; I expect that this one will have to go through a few iterations of review and potentially rewrites, because memory ordering is tricky. (If someone else wants to take over patch 2, I would be very happy.)These patches don't really belong together all that much, I'm just sending them as a series because they'd otherwise conflict.
Quoted 8 lines
I am CCing:
- Suren because patch 1 touches his code
- Matthew Wilcox because he is also currently working on per-VMA locking stuff
- all the maintainers/reviewers for the Kernel Memory Consistency Model so they can help figure out theREAD_ONCE()vssmp_load_acquire()thing
READ_ONCE()has weaker ordering properties thansmp_load_acquire().For example, given a pointer gp:
p = whichever(gp); a = 1; r1 = p->b; if ((uintptr_t)p & 0x1) WRITE_ONCE(b, 1); WRITE_ONCE(c, 1);Leaving aside the "&" needed by
smp_load_acquire(), if "whichever" is "READ_ONCE", then the load fromp->band theWRITE_ONCE()to "b" are ordered after the load from gp (the former due to an address dependency and the latter due to a (fragile) control dependency). The compiler is within its rights to reorder the store to "a" to precede the load from gp. The compiler is forbidden from reordering the store to "c" wtih the load from gp (because both are volatile accesses), but the CPU is completely within its rights to do this reordering.But if "whichever" is "
smp_load_acquire()", all four of the subsequent memory accesses are ordered after the load from gp.Similarly, for
WRITE_ONCE()andsmp_store_release():p = READ_ONCE(gp); r1 = READ_ONCE(gi); r2 = READ_ONCE(gj); a = 1; WRITE_ONCE(b, 1); if (r1 & 0x1) whichever(p->q, r2);Again leaving aside the "&" needed by
smp_store_release(), if "whichever" isWRITE_ONCE(), then the load from gp, the load from gi, and the load from gj are all ordered before the store top->q(by address dependency, control dependency, and data dependency, respectively). The store to "a" can be reordered with the store top->qby the compiler. The store to "b" cannot be reordered with the store top->qby the compiler (again, both are volatile), but the CPU is free to reorder them, especially whenwhichever()is implemented as a conditional store.
Quoted 4 lines
But if "whichever" is "
smp_store_release()", all five of the earlier memory accesses are ordered before the store top->q.Does that help, or am I missing the point of your question?
My main question is how permissible/ugly you think the following use of READ_ONCE() would be, and whether you think it ought to be an smp_load_acquire() instead.
Assume that we are holding some kind of lock that ensures that the only possible concurrent update to "vma->anon_vma" is that it changes from a NULL pointer to a non-NULL pointer (using smp_store_release()).
if (READ_ONCE(vma->anon_vma) != NULL) {
// we now know that vma->anon_vma cannot change anymore
// access the same memory location again with a plain load struct anon_vma *a = vma->anon_vma;
// this needs to be address-dependency-ordered against one of // the loads from vma->anon_vma
struct anon_vma *root = a->root;
}
Is this fine? If it is not fine just because the compiler might reorder the plain load of vma->anon_vma before the READ_ONCE() load, would it be fine after adding a barrier() directly after the READ_ONCE()?
I initially suggested using READ_ONCE() for this, and then Linus and me tried to reason it out and Linus suggested (if I understood him correctly) that you could make the ugly argument that this works because loads from the same location will not be reordered by the hardware. So on anything other than alpha, we'd still have the required address-dependency ordering because that happens for all loads, even plain loads, while on alpha, the READ_ONCE() includes a memory barrier. But that argument is weirdly reliant on architecture-specific implementation details.
The other option is to replace the READ_ONCE() with a smp_load_acquire(), at which point it becomes a lot simpler to show that the code is correct.
Quoted 24 lines
Thanx, Paul
Quoted 22 lines
- people involved in the previous discussion on the security list
Jann Horn (2):
mm:lock_vma_under_rcu()must checkvma->anon_vmaunder vma lock
mm: Fixanon_vmamemory orderinginclude/linux/rmap.h | 15 ++++++++++++++- mm/huge_memory.c | 4 +++- mm/khugepaged.c | 2 +- mm/ksm.c | 16 +++++++++++----- mm/memory.c | 32 ++++++++++++++++++++------------ mm/mmap.c | 13 ++++++++++--- mm/rmap.c | 6 ++++-- mm/swapfile.c | 3 ++- 8 files changed, 65 insertions(+), 26 deletions(-)base-commit:
20ea1e7d13c1b544fe67c4a8dc3943bb1ab33e6f--
2.41.0.487.g6d72f3e995-goog
Quoted 95 lines · Jann Horn
Quoted 68 lines · Paul E. McKenney
Quoted 15 lines · Jann Horn
Hi!
Patch 1 here is a straightforward fix for a race in per-VMA locking code that can lead to use-after-free; I hope we can get this one into mainline and stable quickly.
Patch 2 is a fix for what I believe is a longstanding memory ordering issue in how
vma->anon_vmais used across the MM subsystem; I expect that this one will have to go through a few iterations of review and potentially rewrites, because memory ordering is tricky. (If someone else wants to take over patch 2, I would be very happy.)These patches don't really belong together all that much, I'm just sending them as a series because they'd otherwise conflict.
Quoted 8 lines
I am CCing:
- Suren because patch 1 touches his code
- Matthew Wilcox because he is also currently working on per-VMA locking stuff
- all the maintainers/reviewers for the Kernel Memory Consistency Model so they can help figure out theREAD_ONCE()vssmp_load_acquire()thing
READ_ONCE()has weaker ordering properties thansmp_load_acquire().For example, given a pointer gp:
p = whichever(gp); a = 1; r1 = p->b; if ((uintptr_t)p & 0x1) WRITE_ONCE(b, 1); WRITE_ONCE(c, 1);Leaving aside the "&" needed by
smp_load_acquire(), if "whichever" is "READ_ONCE", then the load fromp->band theWRITE_ONCE()to "b" are ordered after the load from gp (the former due to an address dependency and the latter due to a (fragile) control dependency). The compiler is within its rights to reorder the store to "a" to precede the load from gp. The compiler is forbidden from reordering the store to "c" wtih the load from gp (because both are volatile accesses), but the CPU is completely within its rights to do this reordering.But if "whichever" is "
smp_load_acquire()", all four of the subsequent memory accesses are ordered after the load from gp.Similarly, for
WRITE_ONCE()andsmp_store_release():p = READ_ONCE(gp); r1 = READ_ONCE(gi); r2 = READ_ONCE(gj); a = 1; WRITE_ONCE(b, 1); if (r1 & 0x1) whichever(p->q, r2);Again leaving aside the "&" needed by
smp_store_release(), if "whichever" isWRITE_ONCE(), then the load from gp, the load from gi, and the load from gj are all ordered before the store top->q(by address dependency, control dependency, and data dependency, respectively). The store to "a" can be reordered with the store top->qby the compiler. The store to "b" cannot be reordered with the store top->qby the compiler (again, both are volatile), but the CPU is free to reorder them, especially whenwhichever()is implemented as a conditional store.Quoted 4 lines
But if "whichever" is "
smp_store_release()", all five of the earlier memory accesses are ordered before the store top->q.Does that help, or am I missing the point of your question?
My main question is how permissible/ugly you think the following use of
READ_ONCE()would be, and whether you think it ought to be ansmp_load_acquire()instead.Assume that we are holding some kind of lock that ensures that the only possible concurrent update to "
vma->anon_vma" is that it changes from a NULL pointer to a non-NULL pointer (usingsmp_store_release()).if (
READ_ONCE(vma->anon_vma)!= NULL) {
// we now know thatvma->anon_vmacannot change anymore// access the same memory location again with a plain load struct
anon_vma*a =vma->anon_vma;// this needs to be address-dependency-ordered against one of // the loads from
vma->anon_vma
structanon_vma*root =a->root;
}
Quoted 4 lines
Is this fine? If it is not fine just because the compiler might reorder the plain load of
vma->anon_vmabefore theREAD_ONCE()load, would it be fine after adding abarrier()directly after theREAD_ONCE()?
I'm _very_ wary of mixing READ_ONCE() and plain loads to the same variable, as I've run into cases where you have sequences such as:
// Assume *ptr is initially 0 and somebody else writes it to 1 // concurrently foo = *ptr; bar = READ_ONCE(*ptr); baz = *ptr;
and you can get foo == baz == 0 but bar == 1 because the compiler only ends up reading from memory twice.
That was the root cause behind f069faba6887 ("arm64: mm: Use READ_ONCE when dereferencing pointer to pte table"), which was very unpleasant to debug.
Will
Quoted 10 lines · Will Deacon
Quoted 8 lines · Jann Horn
Assume that we are holding some kind of lock that ensures that the only possible concurrent update to "
vma->anon_vma" is that it changes from a NULL pointer to a non-NULL pointer (usingsmp_store_release()).if (
READ_ONCE(vma->anon_vma)!= NULL) {
// we now know thatvma->anon_vmacannot change anymore
Quoted 7 lines
Quoted 7 lines
// access the same memory location again with a plain load struct
anon_vma*a =vma->anon_vma;// this needs to be address-dependency-ordered against one of // the loads from
vma->anon_vma
structanon_vma*root =a->root;
}
This reads a little oddly, perhaps because it's a fragment from a larger piece of code. Still, if I were doing something like this, I'd write it as:
struct anon_vma *a;
a = READ_ONCE(vma->anon_vma);
if (a != NULL) {
struct anon_vma *root = a->root;
...thus eliminating the possibility of confusion from multiple reads of the same address.
In this situation, the ordering of the two reads is guaranteed by the address dependency. And people shouldn't worry too much about using that sort of ordering; RCU relies on it critically, all the time.
Quoted 15 lines
Quoted 4 lines
Is this fine? If it is not fine just because the compiler might reorder the plain load of
vma->anon_vmabefore theREAD_ONCE()load, would it be fine after adding abarrier()directly after theREAD_ONCE()?I'm _very_ wary of mixing
READ_ONCE()and plain loads to the same variable, as I've run into cases where you have sequences such as:// Assume *ptr is initially 0 and somebody else writes it to 1 // concurrently foo = *ptr; bar = READ_ONCE(*ptr); baz = *ptr;
Quoted 6 lines
and you can get foo == baz == 0 but bar == 1 because the compiler only ends up reading from memory twice.
That was the root cause behind
f069faba6887("arm64: mm: UseREAD_ONCEwhen dereferencing pointer to pte table"), which was very unpleasant to debug.
Indeed, that's the sort of thing that can happen when plain accesses are involved in a race.
Alan Stern
Jann Horn
reviewerQuoted 14 lines · Alan Stern
Quoted 13 lines · Will Deacon
Quoted 11 lines · Jann Horn
Assume that we are holding some kind of lock that ensures that the only possible concurrent update to "
vma->anon_vma" is that it changes from a NULL pointer to a non-NULL pointer (usingsmp_store_release()).if (
READ_ONCE(vma->anon_vma)!= NULL) {
// we now know thatvma->anon_vmacannot change anymore// access the same memory location again with a plain load struct
anon_vma*a =vma->anon_vma;
Quoted 7 lines
Quoted 4 lines
Quoted 4 lines
// this needs to be address-dependency-ordered against one of // the loads from
vma->anon_vma
structanon_vma*root =a->root;
}This reads a little oddly, perhaps because it's a fragment from a larger piece of code.
Yes, exactly. The READ_ONCE() would be in anon_vma_prepare(), which is a helper used to ensure that a VMA is associated with an anon_vma, and then the vma->anon_vma is used further down inside the fault handling path. Something like:
do_cow_fault
anon_vma_prepare
READ_ONCE(vma->anon_vma)
barrier()
finish_fault
do_set_pte
page_add_new_anon_rmap
folio_add_new_anon_rmap
__page_set_anon_rmap
[reads vma->anon_vma]Anyway, I guess I'll follow what Paul and Matthew said and go with smp_load_acquire().
Quoted 39 lines · Jann Horn
Quoted 14 lines · Alan Stern
Quoted 13 lines · Will Deacon
Quoted 11 lines · Jann Horn
Assume that we are holding some kind of lock that ensures that the only possible concurrent update to "
vma->anon_vma" is that it changes from a NULL pointer to a non-NULL pointer (usingsmp_store_release()).if (
READ_ONCE(vma->anon_vma)!= NULL) {
// we now know thatvma->anon_vmacannot change anymore// access the same memory location again with a plain load struct
anon_vma*a =vma->anon_vma;Quoted 7 lines
Quoted 4 lines
Quoted 4 lines
// this needs to be address-dependency-ordered against one of // the loads from
vma->anon_vma
structanon_vma*root =a->root;
}This reads a little oddly, perhaps because it's a fragment from a larger piece of code.
Yes, exactly. The
READ_ONCE()would be inanon_vma_prepare(), which is a helper used to ensure that a VMA is associated with ananon_vma, and then thevma->anon_vmais used further down inside the fault handling path. Something like:
do_cow_fault
anon_vma_prepareREAD_ONCE(vma->anon_vma) barrier() finish_fault do_set_pte page_add_new_anon_rmap folio_add_new_anon_rmap __page_set_anon_rmap [reads vma->anon_vma]
Quoted 2 lines
Anyway, I guess I'll follow what Paul and Matthew said and go with
smp_load_acquire().
I thank you now, and you will thank youself later. ;-)
Thanx, Paul
Quoted 30 lines · Alan Stern
Quoted 10 lines · Will Deacon
Quoted 8 lines · Jann Horn
Assume that we are holding some kind of lock that ensures that the only possible concurrent update to "
vma->anon_vma" is that it changes from a NULL pointer to a non-NULL pointer (usingsmp_store_release()).if (
READ_ONCE(vma->anon_vma)!= NULL) {
// we now know thatvma->anon_vmacannot change anymoreQuoted 7 lines
Quoted 7 lines
// access the same memory location again with a plain load struct
anon_vma*a =vma->anon_vma;// this needs to be address-dependency-ordered against one of // the loads from
vma->anon_vma
structanon_vma*root =a->root;
}This reads a little oddly, perhaps because it's a fragment from a larger piece of code. Still, if I were doing something like this, I'd write it as:
struct
anon_vma*a;a =
READ_ONCE(vma->anon_vma);if (a != NULL) { struct anon_vma *root = a->root; ...
Quoted 6 lines
thus eliminating the possibility of confusion from multiple reads of the same address.
In this situation, the ordering of the two reads is guaranteed by the address dependency. And people shouldn't worry too much about using that sort of ordering; RCU relies on it critically, all the time.
Agreed. In contrast, control dependencies require quite a bit more care and feeding, and are usually best avoided.
But even with the normal RCU address/data dependencies, it is possible to get in trouble. For but one example, comparing a pointer obtained from rcu_dereference() to the address of a static structure is a good way to break your address dependency. (Just yesterday evening I talked to someone who had spent quite a bit of time chasing one of these down, so yes, this is quite real.)
Quoted 18 lines
Quoted 18 lines
Quoted 4 lines
Is this fine? If it is not fine just because the compiler might reorder the plain load of
vma->anon_vmabefore theREAD_ONCE()load, would it be fine after adding abarrier()directly after theREAD_ONCE()?I'm _very_ wary of mixing
READ_ONCE()and plain loads to the same variable, as I've run into cases where you have sequences such as:// Assume *ptr is initially 0 and somebody else writes it to 1 // concurrently foo = *ptr; bar = READ_ONCE(*ptr); baz = *ptr;and you can get foo == baz == 0 but bar == 1 because the compiler only ends up reading from memory twice.
Quoted 6 lines
Quoted 3 lines
That was the root cause behind
f069faba6887("arm64: mm: UseREAD_ONCEwhen dereferencing pointer to pte table"), which was very unpleasant to debug.Indeed, that's the sort of thing that can happen when plain accesses are involved in a race.
Agreed. Furthermore, it is more important to comment plain C-language accesses to shared variables than to comment the likes of READ_ONCE(). "OK, tell me again exactly why you think the compiler cannot mess you up here?"
Thanx, Paul
Quoted 3 lines · Alan Stern
This reads a little oddly, perhaps because it's a fragment from a larger piece of code.
Yes. As Jann already said, this is basically a preparatory step in a much longer sequence, and the code simply wants to make sure that any later code (possibly quite a bit later) will not see a NULL value.
I do believe it happens to be safe to use READ_ONCE() for a number of reasons, but I will argue that we should *never* use a bare READ_ONCE if there is any actual real question about what any memory ordering might be.
And yes, the RCU code obviously does use READ_ONCE(), so that's why I say "bare" - the RCU code wraps it in helper accessors with strict semantics.
The reason I think it would be techncially *safe* to do here is that
(a) code like this:
if (READ_ONCE(..))
may end up having the conditional speculated by the CPU, and have
the actual read done without any ordering by the CPU, but we do have *one* guarantee: the memory load instruction will be before the conditional branch (or whatever) in the instruction stream.
So the code may be *executed* out of order, but we know the
memory load can not be moved after the conditional (whatever form that conditional then takes) by a compiler.
(We do have various barriers like "rcu_read_unlock()" that
guarantees that the READ_ONCE() couldn't be moved lmuch later even in the absence of the conditional, but we can ignore that).
(b) the later use of the anon_vma (that depends on the value being
stable) is *so* much later, and behind things that the compiler sees as barriers (again, that rcu_read_unlock() acts at a minimum as a compiler barrier) that any subsequent use would not have its load moved down to before the READ_ONCE() in the instruction stream.
Again, this is purely a "location in the instruction stream"
ordering argument, not a "execution order" ordering argument.
And finally
(c) I do think that all our architectures have the rules that when
you read from the *same* memory location from the same CPU, the accesses are ordered.
Now, I didn't actually find (c) spelled out anywhere, but even alpha - the worst memory ordering ever devised - had that particular rule (the alpha architecture manual calls it "Location Access Order").
Now, with that said, I did argue to Jann that we should use smp_store_release and smp_load_acquire pairs here, because honestly, the above (a)-(c) argument is too damn subtle for me, and I don't think this particular use requires it.
With smp_load_acquire(), you don't need any of the (a)-(c) rules. The rule is "the load is done before any subsequent memory operations". End of story.
So while I do think READ_ONCE() is sufficient here, I actually think that once you start going down that path you can argue that READ_ONCE() is actually entirely unnecessary, because we also have other ordering rules that mean that the compiler can't really do anythinig else even *without* the READ_ONCE().
End result: I can trivially extend the (a)-(c) to say "even READ_ONCE() isn't strictly necessary here, because even any access tearing - which won't happen anyway - wouldn't actually change the result.
So if we want to make it *obvious* that it's safe, we should use smp_load_acquire().
And if we do find that there are situations where we care so much about the (generally fairly cheap) possible additional synchronization, and we really want to use READ_ONCE() rather than smp_load_acquire(), I'd rather try to wrap a READ_ONCE in some kind of better abstraction (maybe make the conditional part of the operation, and make it clear that you are doing a "one-time test which depends on the same-location rule".
Do we even have the same-location rule in the LKMM?
Linus
Quoted 8 lines · Linus Torvalds
Quoted 3 lines · Alan Stern
This reads a little oddly, perhaps because it's a fragment from a larger piece of code.
Yes. As Jann already said, this is basically a preparatory step in a much longer sequence, and the code simply wants to make sure that any later code (possibly quite a bit later) will not see a NULL value.
...
Quoted 1 line
Do we even have the same-location rule in the LKMM?
Yes. The comment in the source file calls it "Sequential Consistency Per Variable", under the category of "Fundamental coherence ordering". It applies even to plain accesses, not just to READ_ONCE or stronger.
But in the presence of data races (as in the example that Will posted earlier), all bets are off. So if you want to use a plain access rather than READ_ONCE, you need to be certain that it won't race with anything.
Alan Stern
Quoted 4 lines · Alan Stern
But in the presence of data races (as in the example that Will posted earlier), all bets are off. So if you want to use a plain access rather than
READ_ONCE, you need to be certain that it won't race with anything.
So in this case, the initial NULL check really is just checking for "has the smp_store_release() happened". The reason even tearing wouldn't matter is that seeing *any* value other than all-zeroes (aka NULL) is already sufficient information.
Because once the smp_store_release() has been seen by this CPU, the data race no longer exists, and the value is stable.
Which is why I argue that even without READ_ONCE() the code would *work* due to all the circumstances around it (one of them is that we just took a lock, after doing an optimistic check that really has no semantic effect at all except for the "don't even take the lock if it looks like things are going to fail").
But if we want to have the code be obvious, and not have to refer to those kinds of arguments, I think smp_load_acquire() is the only actual "obvious" thing to use. At that point it's no longer some chain of "because of X, Y and Z".
Linus
Quoted 115 lines · Will Deacon
Quoted 95 lines · Jann Horn
Quoted 68 lines · Paul E. McKenney
Quoted 15 lines · Jann Horn
Hi!
Patch 1 here is a straightforward fix for a race in per-VMA locking code that can lead to use-after-free; I hope we can get this one into mainline and stable quickly.
Patch 2 is a fix for what I believe is a longstanding memory ordering issue in how
vma->anon_vmais used across the MM subsystem; I expect that this one will have to go through a few iterations of review and potentially rewrites, because memory ordering is tricky. (If someone else wants to take over patch 2, I would be very happy.)These patches don't really belong together all that much, I'm just sending them as a series because they'd otherwise conflict.
Quoted 8 lines
I am CCing:
- Suren because patch 1 touches his code
- Matthew Wilcox because he is also currently working on per-VMA locking stuff
- all the maintainers/reviewers for the Kernel Memory Consistency Model so they can help figure out theREAD_ONCE()vssmp_load_acquire()thing
READ_ONCE()has weaker ordering properties thansmp_load_acquire().For example, given a pointer gp:
p = whichever(gp); a = 1; r1 = p->b; if ((uintptr_t)p & 0x1) WRITE_ONCE(b, 1); WRITE_ONCE(c, 1);Leaving aside the "&" needed by
smp_load_acquire(), if "whichever" is "READ_ONCE", then the load fromp->band theWRITE_ONCE()to "b" are ordered after the load from gp (the former due to an address dependency and the latter due to a (fragile) control dependency). The compiler is within its rights to reorder the store to "a" to precede the load from gp. The compiler is forbidden from reordering the store to "c" wtih the load from gp (because both are volatile accesses), but the CPU is completely within its rights to do this reordering.But if "whichever" is "
smp_load_acquire()", all four of the subsequent memory accesses are ordered after the load from gp.Similarly, for
WRITE_ONCE()andsmp_store_release():p = READ_ONCE(gp); r1 = READ_ONCE(gi); r2 = READ_ONCE(gj); a = 1; WRITE_ONCE(b, 1); if (r1 & 0x1) whichever(p->q, r2);Again leaving aside the "&" needed by
smp_store_release(), if "whichever" isWRITE_ONCE(), then the load from gp, the load from gi, and the load from gj are all ordered before the store top->q(by address dependency, control dependency, and data dependency, respectively). The store to "a" can be reordered with the store top->qby the compiler. The store to "b" cannot be reordered with the store top->qby the compiler (again, both are volatile), but the CPU is free to reorder them, especially whenwhichever()is implemented as a conditional store.Quoted 4 lines
But if "whichever" is "
smp_store_release()", all five of the earlier memory accesses are ordered before the store top->q.Does that help, or am I missing the point of your question?
My main question is how permissible/ugly you think the following use of
READ_ONCE()would be, and whether you think it ought to be ansmp_load_acquire()instead.Assume that we are holding some kind of lock that ensures that the only possible concurrent update to "
vma->anon_vma" is that it changes from a NULL pointer to a non-NULL pointer (usingsmp_store_release()).if (
READ_ONCE(vma->anon_vma)!= NULL) {
// we now know thatvma->anon_vmacannot change anymore// access the same memory location again with a plain load struct
anon_vma*a =vma->anon_vma;// this needs to be address-dependency-ordered against one of // the loads from
vma->anon_vma
structanon_vma*root =a->root;
}Quoted 4 lines
Is this fine? If it is not fine just because the compiler might reorder the plain load of
vma->anon_vmabefore theREAD_ONCE()load, would it be fine after adding abarrier()directly after theREAD_ONCE()?I'm _very_ wary of mixing
READ_ONCE()and plain loads to the same variable, as I've run into cases where you have sequences such as:// Assume *ptr is initially 0 and somebody else writes it to 1 // concurrently
foo = *ptr;
bar =READ_ONCE(*ptr);
baz = *ptr;
Quoted 6 lines
and you can get foo == baz == 0 but bar == 1 because the compiler only ends up reading from memory twice.
That was the root cause behind
f069faba6887("arm64: mm: UseREAD_ONCEwhen dereferencing pointer to pte table"), which was very unpleasant to debug.
Interesting. I wonder if you considered adding to READ_ONCE() something like:
asm volatile("" : "+g" (x) );So later loads (such as baz = *ptr) would reload the updated value.
Quoted 7 lines · Nadav Amit
Interesting. I wonder if you considered adding to
READ_ONCE()something like:asm volatile("" : "+g" (x) );So later loads (such as baz = *ptr) would reload the updated value.
Not necessarily a bad idea. Although I suspect you'd want to add *two* of them - on either side - to make sure any previous loads wouldn't be moved around it either.
Linus
Quoted 9 lines · Linus Torvalds
Quoted 4 lines · Nadav Amit
Interesting. I wonder if you considered adding to
READ_ONCE()something like:
Quoted 7 lines
Quoted 3 lines
asm volatile("" : "+g" (x) );So later loads (such as baz = *ptr) would reload the updated value.
Not necessarily a bad idea. Although I suspect you'd want to add *two* of them - on either side - to make sure any previous loads wouldn't be moved around it either.
You are right, two are needed.
I’ll give it a shot and see if I see changes to the binary.
Quoted 17 lines · Nadav Amit
Quoted 14 lines · Linus Torvalds
Quoted 7 lines · Nadav Amit
Interesting. I wonder if you considered adding to
READ_ONCE()something like:asm volatile("" : "+g" (x) );So later loads (such as baz = *ptr) would reload the updated value.
Quoted 7 lines
Quoted 3 lines
Not necessarily a bad idea. Although I suspect you'd want to add *two* of them - on either side - to make sure any previous loads wouldn't be moved around it either.
You are right, two are needed.
I’ll give it a shot and see if I see changes to the binary.
Just for the record (so nobody will make my mistakes):
I implemented it, but it works poorly. It appears to communicate the constraints but the generated code is much worse.
The problem is that if the GCC inline asm decides to use a memory operand (e.g. “+m”), it computes the address (uses LEA first before the MOV) and allocates a register for the address. Using “+g” also causes the compiler to allocate a register.
-- >8 --
--- include/asm-generic/rwonce.h | 32 ++++++++++++++++++++++++++++---- 1 file changed, 28 insertions(+), 4 deletions(-)
include/asm-generic/rwonce.h +28 -4
@@ -44,10 +44,34 @@#define __READ_ONCE (x) (*(const volatile __unqual_scalar_typeof(x) *)&(x))#endif -#define READ_ONCE (x) \ -({ \ - compiletime_assert_rwonce_type(x); \ - __READ_ONCE(x); \ +#define as_scalar (x) \ + __builtin_choose_expr(sizeof(x) == sizeof(char), \ + (__force char *)&(x), \ + __builtin_choose_expr(sizeof(x) == sizeof(short), \ + (__force short *)&(x), \ + __builtin_choose_expr(sizeof(x) == sizeof(int), \ + (__force int *)&(x), \ + __builtin_choose_expr(sizeof(x) == sizeof(long), \ + (__force long *)&(x), \ + __builtin_choose_expr(sizeof(x) == sizeof(long long), \ + (__force long long *)&(x), \ + (void*)0))))) + +#define READ_ONCE (x) \ +({ \ + typeof(x) * px = &(x); \ + union { \ + typeof(x) __orig; \ + typeof(*as_scalar(x)) __alias; \ + } __u; \ + \ + compiletime_assert_rwonce_type(x); \ + asm volatile ("" : \ + "+g" (*(__force typeof(*as_scalar(x)) *)(px))); \ + __u.__alias = __READ_ONCE(*as_scalar(*px)); \ + asm volatile ("" : \ + "+g" (*(__force typeof(*as_scalar(x)) *)(px))); \ + __u.__orig; \ })#define __WRITE_ONCE (x, val) \
Signature · 1 line
2.34.1
Quoted 32 lines · Jann Horn
Assume that we are holding some kind of lock that ensures that the only possible concurrent update to "
vma->anon_vma" is that it changes from a NULL pointer to a non-NULL pointer (usingsmp_store_release()).if (
READ_ONCE(vma->anon_vma)!= NULL) {
// we now know thatvma->anon_vmacannot change anymore// access the same memory location again with a plain load struct
anon_vma*a =vma->anon_vma;// this needs to be address-dependency-ordered against one of // the loads from
vma->anon_vma
structanon_vma*root =a->root;
}Is this fine? If it is not fine just because the compiler might reorder the plain load of
vma->anon_vmabefore theREAD_ONCE()load, would it be fine after adding abarrier()directly after theREAD_ONCE()?I initially suggested using
READ_ONCE()for this, and then Linus and me tried to reason it out and Linus suggested (if I understood him correctly) that you could make the ugly argument that this works because loads from the same location will not be reordered by the hardware. So on anything other than alpha, we'd still have the required address-dependency ordering because that happens for all loads, even plain loads, while on alpha, theREAD_ONCE()includes a memory barrier. But that argument is weirdly reliant on architecture-specific implementation details.
Quoted 3 lines
The other option is to replace the
READ_ONCE()with asmp_load_acquire(), at which point it becomes a lot simpler to show that the code is correct.
Aren't we straining at gnats here? The context of this is handling a page fault, and we used to take an entire rwsem for read. I'm having a hard time caring about "the extra expense" of an unnecessarily broad barrier.
Cost of an L3 cacheline miss is in the thousands of cycles. Cost of a barrier is ... tens?
Jann Horn
reviewerQuoted 5 lines · Matthew Wilcox
Quoted 3 lines · Jann Horn
The other option is to replace the
READ_ONCE()with asmp_load_acquire(), at which point it becomes a lot simpler to show that the code is correct.
Quoted 7 lines
Aren't we straining at gnats here? The context of this is handling a page fault, and we used to take an entire rwsem for read. I'm having a hard time caring about "the extra expense" of an unnecessarily broad barrier.
Cost of an L3 cacheline miss is in the thousands of cycles. Cost of a barrier is ... tens?
Yeah, fair point. If it's hard to show correctness with READ_ONCE() we can just use smp_load_acquire() and call it a day.
Quoted 37 lines · Matthew Wilcox
Quoted 32 lines · Jann Horn
Assume that we are holding some kind of lock that ensures that the only possible concurrent update to "
vma->anon_vma" is that it changes from a NULL pointer to a non-NULL pointer (usingsmp_store_release()).if (
READ_ONCE(vma->anon_vma)!= NULL) {
// we now know thatvma->anon_vmacannot change anymore// access the same memory location again with a plain load struct
anon_vma*a =vma->anon_vma;// this needs to be address-dependency-ordered against one of // the loads from
vma->anon_vma
structanon_vma*root =a->root;
}Is this fine? If it is not fine just because the compiler might reorder the plain load of
vma->anon_vmabefore theREAD_ONCE()load, would it be fine after adding abarrier()directly after theREAD_ONCE()?I initially suggested using
READ_ONCE()for this, and then Linus and me tried to reason it out and Linus suggested (if I understood him correctly) that you could make the ugly argument that this works because loads from the same location will not be reordered by the hardware. So on anything other than alpha, we'd still have the required address-dependency ordering because that happens for all loads, even plain loads, while on alpha, theREAD_ONCE()includes a memory barrier. But that argument is weirdly reliant on architecture-specific implementation details.Quoted 3 lines
The other option is to replace the
READ_ONCE()with asmp_load_acquire(), at which point it becomes a lot simpler to show that the code is correct.
Quoted 7 lines
Aren't we straining at gnats here? The context of this is handling a page fault, and we used to take an entire rwsem for read. I'm having a hard time caring about "the extra expense" of an unnecessarily broad barrier.
Cost of an L3 cacheline miss is in the thousands of cycles. Cost of a barrier is ... tens?
Couldn't agree more!
Thanx, Paul