Skip to contentSkip to conversation

uprobes: speculative lockless VMA-to-uprobe lookup

PATCH Applied Andrii Nakryiko 8 participants 14 messages Nov 22, 2024 – Dec 2, 2024

Subsystems (5)
lore
Share & tools
lore

Andrii Nakryiko

author maintainer
#0 lore raw

v5 cover uprobes: speculative lockless VMA-to-uprobe lookup

Implement speculative (lockless) resolution of VMA to inode to uprobe, bypassing the need to take mmap_lock for reads, if possible. This series is based on Suren's patch set [2], which adds mm_struct helpers that help detect whether mm_struct was changed, which is used by uprobe logic to validate that speculative results can be trusted after all the lookup logic results in a valid uprobe instance.

Patch #1 is a simplification to uprobe VMA flag checking, suggested by Oleg.

Patch #2 is the speculative VMA-to-uprobe resolution logic itself, and is the focal point of this patch set. It makes entry uprobes in common case scale very well with number of CPUs, as we avoid any locking or cache line bouncing between CPUs. See corresponding patch for details and benchmarking results.

Note, this patch set assumes that FMODE_BACKING files were switched to have SLAB_TYPE_SAFE_BY_RCU semantics, which was recently done by Christian Brauner in [0]. This change can be pulled into perf/core through stable tags/vfs-6.13.for-bpf.file tag from [1].

[0] https://git.kernel.org/pub/scm/linux/kernel/git/vfs/vfs.git/commit/?h=vfs-6.13.for-bpf.file&id=8b1bc2590af61129b82a189e9dc7c2804c34400e
[1] git://git.kernel.org/pub/scm/linux/kernel/git/vfs/vfs.git
[2] https://lore.kernel.org/linux-mm/[email protected]/

v4->v5:
- rebase on top of Suren's latest version of mm patches addressing Peter's comment and API renaming request;
v3->v4:
- rebased and dropped data_race(), given mm_struct uses real seqcount (Peter); v2->v3:
- dropped kfree_rcu() patch (Christian);
- added data_race() annotations for fields of vma and vma->vm_file which could be modified during speculative lookup (Oleg);
- fixed int->long problem in stubs for mmap_lock_speculation_{start,end}(), caught by Kernel test robot;
v1->v2:
- adjusted vma_end_write_all() comment to point out it should never be called manually now, but I wasn't sure how ACQUIRE/RELEASE comments should be reworded (previously requested by Jann), so I'd appreciate some help there (Jann);
- int -> long change for mm_lock_seq, as agreed at LPC2024 (Jann, Suren, Liam);
- kfree_rcu_mightsleep() for FMODE_BACKING (Suren, Christian);
- vm_flags simplification in find_active_uprobe_rcu() and find_active_uprobe_speculative() (Oleg);
- guard(rcu)() simplified find_active_uprobe_speculative() implementation.

Andrii Nakryiko (2):
uprobes: simplify find_active_uprobe_rcu() VMA checks
uprobes: add speculative lockless VMA-to-inode-to-uprobe resolution

 kernel/events/uprobes.c | 47 ++++++++++++++++++++++++++++++++++++++++-
 1 file changed, 46 insertions(+), 1 deletion(-)
Signature · 1 line
2.43.5
author maintainer
#1 lore raw

PATCH v5 1/2 uprobes: simplify find_active_uprobe_rcu() VMA checks

At the point where find_active_uprobe_rcu() is used we know that VMA in question has triggered software breakpoint, so we don't need to validate vma->vm_flags. Keep only vma->vm_file NULL check.

---
 kernel/events/uprobes.c | 2 +-
 1 file changed, 1 insertion(+), 1 deletion(-)
kernel/events/uprobes.c +1 -1
index a76ddc5fc982..c4da8f741f3a 100644
@@ -2305,7 +2305,7 @@ static struct uprobe *find_active_uprobe_rcu(unsigned long bp_vaddr, int *is_swb
 	mmap_read_lock(mm);
 	vma = vma_lookup(mm, bp_vaddr);
 	if (vma) {
-		if (valid_vma(vma, false)) {
+		if (vma->vm_file) {
 			struct inode *inode = file_inode(vma->vm_file);
 			loff_t offset = vaddr_to_offset(vma, bp_vaddr);
 
Signature · 1 line
2.43.5
#2 lore raw

Re: [PATCH v5 tip/perf/core 1/2] uprobes: simplify find_active_uprobe_rcu() VMA checks

Quoted 3 lines · Andrii Nakryiko

At the point where find_active_uprobe_rcu() is used we know that VMA in question has triggered software breakpoint, so we don't need to validate vma->vm_flags. Keep only vma->vm_file NULL check.

How do we know that the VMA we find triggered a software breakpoint? Between the time a software breakpoint was hit and the time we took the mmap_read_lock(), the VMA could have been replaced with an entirely different one, right?

I don't know this code well, and your change looks like it's probably fine (since the file is just used to look up its inode in some tree, and therefore for incompatible files, the lookup is guaranteed to fail and nothing will happen). But I think the commit message looks dodgy.

Quoted 24 lines
---
 kernel/events/uprobes.c | 2 +-
 1 file changed, 1 insertion(+), 1 deletion(-)
kernel/events/uprobes.c +1 -2
index a76ddc5fc982..c4da8f741f3a 100644
@@ -2305,7 +2305,7 @@ static struct uprobe *find_active_uprobe_rcu(unsigned long bp_vaddr, int *is_swb
        mmap_read_lock(mm);
        vma = vma_lookup(mm, bp_vaddr);
        if (vma) {
-               if (valid_vma(vma, false)) {
+               if (vma->vm_file) {
                        struct inode *inode = file_inode(vma->vm_file);
                        loff_t offset = vaddr_to_offset(vma, bp_vaddr);
 
--

2.43.5

#3 lore raw

Re: [PATCH v5 tip/perf/core 1/2] uprobes: simplify find_active_uprobe_rcu() VMA checks

Quoted 10 lines · Jann Horn
Quoted 3 lines · Andrii Nakryiko

At the point where find_active_uprobe_rcu() is used we know that VMA in question has triggered software breakpoint, so we don't need to validate vma->vm_flags. Keep only vma->vm_file NULL check.

How do we know that the VMA we find triggered a software breakpoint? Between the time a software breakpoint was hit and the time we took the mmap_read_lock(), the VMA could have been replaced with an entirely different one, right?

We need that VMA only to get inode + file offset, and whether it is the original VMA with uprobe installed, or someone raced and replaced it with some other VMA shouldn't matter. We either find uprobe at that offset within that inode, or not. So this seems fine.

Quoted 30 lines

I don't know this code well, and your change looks like it's probably fine (since the file is just used to look up its inode in some tree, and therefore for incompatible files, the lookup is guaranteed to fail and nothing will happen). But I think the commit message looks dodgy.

Quoted 24 lines
---
 kernel/events/uprobes.c | 2 +-
 1 file changed, 1 insertion(+), 1 deletion(-)
kernel/events/uprobes.c +1 -2
index a76ddc5fc982..c4da8f741f3a 100644
@@ -2305,7 +2305,7 @@ static struct uprobe *find_active_uprobe_rcu(unsigned long bp_vaddr, int *is_swb
        mmap_read_lock(mm);
        vma = vma_lookup(mm, bp_vaddr);
        if (vma) {
-               if (valid_vma(vma, false)) {
+               if (vma->vm_file) {
                        struct inode *inode = file_inode(vma->vm_file);
                        loff_t offset = vaddr_to_offset(vma, bp_vaddr);
 
--

2.43.5

maintainer
#4 lore raw

Re: [PATCH v5 tip/perf/core 1/2] uprobes: simplify find_active_uprobe_rcu() VMA checks

In reply to Jann Horn
Quoted 10 lines · Jann Horn
Quoted 3 lines · Andrii Nakryiko

At the point where find_active_uprobe_rcu() is used we know that VMA in question has triggered software breakpoint, so we don't need to validate vma->vm_flags. Keep only vma->vm_file NULL check.

How do we know that the VMA we find triggered a software breakpoint? Between the time a software breakpoint was hit and the time we took the mmap_read_lock(), the VMA could have been replaced with an entirely different one, right?

Right, but this doesn't really differ from the case when another thread replaces (or even unmaps) this VMA after find_active_uprobe_rcu() drops mm->mmap_lock and returns a found uprobe.

So I think this is fine.

Oleg.

#5 lore raw

[tip: perf/core] uprobes: simplify find_active_uprobe_rcu() VMA checks

In reply to Andrii Nakryiko
The following commit has been merged into the perf/core branch of tip:

The following commit has been merged into the perf/core branch of tip:

Commit-ID:     83e3dc9a5d4d7402adb24090a77327245d593129
Gitweb:        https://git.kernel.org/tip/83e3dc9a5d4d7402adb24090a77327245d593129
Author:        Andrii Nakryiko <[email protected]>
AuthorDate:    Thu, 21 Nov 2024 19:59:21 -08:00
Committer:     Peter Zijlstra <[email protected]>
CommitterDate: Mon, 02 Dec 2024 12:01:38 +01:00

uprobes: simplify find_active_uprobe_rcu() VMA checks

At the point where find_active_uprobe_rcu() is used we know that VMA in question has triggered software breakpoint, so we don't need to validate vma->vm_flags. Keep only vma->vm_file NULL check.

---
 kernel/events/uprobes.c | 2 +-
 1 file changed, 1 insertion(+), 1 deletion(-)
kernel/events/uprobes.c +1 -1
index fa04b14..62c14df 100644
@@ -2304,7 +2304,7 @@ static struct uprobe *find_active_uprobe_rcu(unsigned long bp_vaddr, int *is_swb
 	mmap_read_lock(mm);
 	vma = vma_lookup(mm, bp_vaddr);
 	if (vma) {
-		if (valid_vma(vma, false)) {
+		if (vma->vm_file) {
 			struct inode *inode = file_inode(vma->vm_file);
 			loff_t offset = vaddr_to_offset(vma, bp_vaddr);
 
author maintainer
#6 lore raw

PATCH v5 2/2 uprobes: add speculative lockless VMA-to-inode-to-uprobe resolution

In reply to Andrii Nakryiko

Given filp_cachep is marked SLAB_TYPESAFE_BY_RCU (and FMODE_BACKING files, a special case, now goes through RCU-delated freeing), we can safely access vma->vm_file->f_inode field locklessly under just rcu_read_lock() protection, which enables looking up uprobe from uprobes_tree completely locklessly and speculatively without the need to acquire mmap_lock for reads. In most cases, anyway, assuming that there are no parallel mm and/or VMA modifications. The underlying struct file's memory won't go away from under us (even if struct file can be reused in the meantime).

We rely on newly added mmap_lock_speculate_{try_begin,retry}() helpers to validate that mm_struct stays intact for entire duration of this speculation. If not, we fall back to mmap_lock-protected lookup. The speculative logic is written in such a way that it will safely handle any garbage values that might be read from vma or file structs.

Benchmarking results speak for themselves.

BEFORE (latest tip/perf/core)
=============================

uprobe-nop            ( 1 cpus):    3.384 ± 0.004M/s  (  3.384M/s/cpu)
uprobe-nop            ( 2 cpus):    5.456 ± 0.005M/s  (  2.728M/s/cpu)
uprobe-nop            ( 3 cpus):    7.863 ± 0.015M/s  (  2.621M/s/cpu)
uprobe-nop            ( 4 cpus):    9.442 ± 0.008M/s  (  2.360M/s/cpu)
uprobe-nop            ( 5 cpus):   11.036 ± 0.013M/s  (  2.207M/s/cpu)
uprobe-nop            ( 6 cpus):   10.884 ± 0.019M/s  (  1.814M/s/cpu)
uprobe-nop            ( 7 cpus):    7.897 ± 0.145M/s  (  1.128M/s/cpu)
uprobe-nop            ( 8 cpus):   10.021 ± 0.128M/s  (  1.253M/s/cpu)
uprobe-nop            (10 cpus):    9.932 ± 0.170M/s  (  0.993M/s/cpu)
uprobe-nop            (12 cpus):    8.369 ± 0.056M/s  (  0.697M/s/cpu)
uprobe-nop            (14 cpus):    8.678 ± 0.017M/s  (  0.620M/s/cpu)
uprobe-nop            (16 cpus):    7.392 ± 0.003M/s  (  0.462M/s/cpu)
uprobe-nop            (24 cpus):    5.326 ± 0.178M/s  (  0.222M/s/cpu)
uprobe-nop            (32 cpus):    5.426 ± 0.059M/s  (  0.170M/s/cpu)
uprobe-nop            (40 cpus):    5.262 ± 0.070M/s  (  0.132M/s/cpu)
uprobe-nop            (48 cpus):    6.121 ± 0.010M/s  (  0.128M/s/cpu)
uprobe-nop            (56 cpus):    6.252 ± 0.035M/s  (  0.112M/s/cpu)
uprobe-nop            (64 cpus):    7.644 ± 0.023M/s  (  0.119M/s/cpu)
uprobe-nop            (72 cpus):    7.781 ± 0.001M/s  (  0.108M/s/cpu)
uprobe-nop            (80 cpus):    8.992 ± 0.048M/s  (  0.112M/s/cpu)

AFTER
=====

uprobe-nop            ( 1 cpus):    3.534 ± 0.033M/s  (  3.534M/s/cpu)
uprobe-nop            ( 2 cpus):    6.701 ± 0.007M/s  (  3.351M/s/cpu)
uprobe-nop            ( 3 cpus):   10.031 ± 0.007M/s  (  3.344M/s/cpu)
uprobe-nop            ( 4 cpus):   13.003 ± 0.012M/s  (  3.251M/s/cpu)
uprobe-nop            ( 5 cpus):   16.274 ± 0.006M/s  (  3.255M/s/cpu)
uprobe-nop            ( 6 cpus):   19.563 ± 0.024M/s  (  3.261M/s/cpu)
uprobe-nop            ( 7 cpus):   22.696 ± 0.054M/s  (  3.242M/s/cpu)
uprobe-nop            ( 8 cpus):   24.534 ± 0.010M/s  (  3.067M/s/cpu)
uprobe-nop            (10 cpus):   30.475 ± 0.117M/s  (  3.047M/s/cpu)
uprobe-nop            (12 cpus):   33.371 ± 0.017M/s  (  2.781M/s/cpu)
uprobe-nop            (14 cpus):   38.864 ± 0.004M/s  (  2.776M/s/cpu)
uprobe-nop            (16 cpus):   41.476 ± 0.020M/s  (  2.592M/s/cpu)
uprobe-nop            (24 cpus):   64.696 ± 0.021M/s  (  2.696M/s/cpu)
uprobe-nop            (32 cpus):   85.054 ± 0.027M/s  (  2.658M/s/cpu)
uprobe-nop            (40 cpus):  101.979 ± 0.032M/s  (  2.549M/s/cpu)
uprobe-nop            (48 cpus):  110.518 ± 0.056M/s  (  2.302M/s/cpu)
uprobe-nop            (56 cpus):  117.737 ± 0.020M/s  (  2.102M/s/cpu)
uprobe-nop            (64 cpus):  124.613 ± 0.079M/s  (  1.947M/s/cpu)
uprobe-nop            (72 cpus):  133.239 ± 0.032M/s  (  1.851M/s/cpu)
uprobe-nop            (80 cpus):  142.037 ± 0.138M/s  (  1.775M/s/cpu)

Previously total throughput was maxing out at 11mln/s, and gradually declining past 8 cores. With this change, it now keeps growing with each added CPU, reaching 142mln/s at 80 CPUs (this was measured on a 80-core Intel(R) Xeon(R) Gold 6138 CPU @ 2.00GHz).

---
 kernel/events/uprobes.c | 45 +++++++++++++++++++++++++++++++++++++++++
 1 file changed, 45 insertions(+)
kernel/events/uprobes.c +45 -0
index c4da8f741f3a..3f5577d4032a 100644
@@ -2295,6 +2295,47 @@ static int is_trap_at_addr(struct mm_struct *mm, unsigned long vaddr)
 	return is_trap_insn(&opcode);
 }
 
+static struct uprobe *find_active_uprobe_speculative(unsigned long bp_vaddr)
+{
+	struct mm_struct *mm = current->mm;
+	struct uprobe *uprobe = NULL;
+	struct vm_area_struct *vma;
+	struct file *vm_file;
+	loff_t offset;
+	unsigned int seq;
+
+	guard(rcu)();
+
+	if (!mmap_lock_speculate_try_begin(mm, &seq))
+		return NULL;
+
+	vma = vma_lookup(mm, bp_vaddr);
+	if (!vma)
+		return NULL;
+
+	/*
+	 * vm_file memory can be reused for another instance of struct file,
+	 * but can't be freed from under us, so it's safe to read fields from
+	 * it, even if the values are some garbage values; ultimately
+	 * find_uprobe_rcu() + mmap_lock_speculation_end() check will ensure
+	 * that whatever we speculatively found is correct
+	 */
+	vm_file = READ_ONCE(vma->vm_file);
+	if (!vm_file)
+		return NULL;
+
+	offset = (loff_t)(vma->vm_pgoff << PAGE_SHIFT) + (bp_vaddr - vma->vm_start);
+	uprobe = find_uprobe_rcu(vm_file->f_inode, offset);
+	if (!uprobe)
+		return NULL;
+
+	/* now double check that nothing about MM changed */
+	if (mmap_lock_speculate_retry(mm, seq))
+		return NULL;
+
+	return uprobe;
+}
+
 /* assumes being inside RCU protected region */
 static struct uprobe *find_active_uprobe_rcu(unsigned long bp_vaddr, int *is_swbp)
 {
@@ -2302,6 +2343,10 @@ static struct uprobe *find_active_uprobe_rcu(unsigned long bp_vaddr, int *is_swb
 	struct uprobe *uprobe = NULL;
 	struct vm_area_struct *vma;
 
+	uprobe = find_active_uprobe_speculative(bp_vaddr);
+	if (uprobe)
+		return uprobe;
+
 	mmap_read_lock(mm);
 	vma = vma_lookup(mm, bp_vaddr);
 	if (vma) {
Signature · 1 line
2.43.5
Reviewed-by on v5 2/2
#7 lore raw

Re: [PATCH v5 tip/perf/core 2/2] uprobes: add speculative lockless VMA-to-inode-to-uprobe resolution

Quoted 69 lines · Andrii Nakryiko

Given filp_cachep is marked SLAB_TYPESAFE_BY_RCU (and FMODE_BACKING files, a special case, now goes through RCU-delated freeing), we can safely access vma->vm_file->f_inode field locklessly under just rcu_read_lock() protection, which enables looking up uprobe from uprobes_tree completely locklessly and speculatively without the need to acquire mmap_lock for reads. In most cases, anyway, assuming that there are no parallel mm and/or VMA modifications. The underlying struct file's memory won't go away from under us (even if struct file can be reused in the meantime).

We rely on newly added mmap_lock_speculate_{try_begin,retry}() helpers to validate that mm_struct stays intact for entire duration of this speculation. If not, we fall back to mmap_lock-protected lookup. The speculative logic is written in such a way that it will safely handle any garbage values that might be read from vma or file structs.

Benchmarking results speak for themselves.

BEFORE (latest tip/perf/core)
=============================

uprobe-nop            ( 1 cpus):    3.384 ± 0.004M/s  (  3.384M/s/cpu)
uprobe-nop            ( 2 cpus):    5.456 ± 0.005M/s  (  2.728M/s/cpu)
uprobe-nop            ( 3 cpus):    7.863 ± 0.015M/s  (  2.621M/s/cpu)
uprobe-nop            ( 4 cpus):    9.442 ± 0.008M/s  (  2.360M/s/cpu)
uprobe-nop            ( 5 cpus):   11.036 ± 0.013M/s  (  2.207M/s/cpu)
uprobe-nop            ( 6 cpus):   10.884 ± 0.019M/s  (  1.814M/s/cpu)
uprobe-nop            ( 7 cpus):    7.897 ± 0.145M/s  (  1.128M/s/cpu)
uprobe-nop            ( 8 cpus):   10.021 ± 0.128M/s  (  1.253M/s/cpu)
uprobe-nop            (10 cpus):    9.932 ± 0.170M/s  (  0.993M/s/cpu)
uprobe-nop            (12 cpus):    8.369 ± 0.056M/s  (  0.697M/s/cpu)
uprobe-nop            (14 cpus):    8.678 ± 0.017M/s  (  0.620M/s/cpu)
uprobe-nop            (16 cpus):    7.392 ± 0.003M/s  (  0.462M/s/cpu)
uprobe-nop            (24 cpus):    5.326 ± 0.178M/s  (  0.222M/s/cpu)
uprobe-nop            (32 cpus):    5.426 ± 0.059M/s  (  0.170M/s/cpu)
uprobe-nop            (40 cpus):    5.262 ± 0.070M/s  (  0.132M/s/cpu)
uprobe-nop            (48 cpus):    6.121 ± 0.010M/s  (  0.128M/s/cpu)
uprobe-nop            (56 cpus):    6.252 ± 0.035M/s  (  0.112M/s/cpu)
uprobe-nop            (64 cpus):    7.644 ± 0.023M/s  (  0.119M/s/cpu)
uprobe-nop            (72 cpus):    7.781 ± 0.001M/s  (  0.108M/s/cpu)
uprobe-nop            (80 cpus):    8.992 ± 0.048M/s  (  0.112M/s/cpu)

AFTER
=====

uprobe-nop            ( 1 cpus):    3.534 ± 0.033M/s  (  3.534M/s/cpu)
uprobe-nop            ( 2 cpus):    6.701 ± 0.007M/s  (  3.351M/s/cpu)
uprobe-nop            ( 3 cpus):   10.031 ± 0.007M/s  (  3.344M/s/cpu)
uprobe-nop            ( 4 cpus):   13.003 ± 0.012M/s  (  3.251M/s/cpu)
uprobe-nop            ( 5 cpus):   16.274 ± 0.006M/s  (  3.255M/s/cpu)
uprobe-nop            ( 6 cpus):   19.563 ± 0.024M/s  (  3.261M/s/cpu)
uprobe-nop            ( 7 cpus):   22.696 ± 0.054M/s  (  3.242M/s/cpu)
uprobe-nop            ( 8 cpus):   24.534 ± 0.010M/s  (  3.067M/s/cpu)
uprobe-nop            (10 cpus):   30.475 ± 0.117M/s  (  3.047M/s/cpu)
uprobe-nop            (12 cpus):   33.371 ± 0.017M/s  (  2.781M/s/cpu)
uprobe-nop            (14 cpus):   38.864 ± 0.004M/s  (  2.776M/s/cpu)
uprobe-nop            (16 cpus):   41.476 ± 0.020M/s  (  2.592M/s/cpu)
uprobe-nop            (24 cpus):   64.696 ± 0.021M/s  (  2.696M/s/cpu)
uprobe-nop            (32 cpus):   85.054 ± 0.027M/s  (  2.658M/s/cpu)
uprobe-nop            (40 cpus):  101.979 ± 0.032M/s  (  2.549M/s/cpu)
uprobe-nop            (48 cpus):  110.518 ± 0.056M/s  (  2.302M/s/cpu)
uprobe-nop            (56 cpus):  117.737 ± 0.020M/s  (  2.102M/s/cpu)
uprobe-nop            (64 cpus):  124.613 ± 0.079M/s  (  1.947M/s/cpu)
uprobe-nop            (72 cpus):  133.239 ± 0.032M/s  (  1.851M/s/cpu)
uprobe-nop            (80 cpus):  142.037 ± 0.138M/s  (  1.775M/s/cpu)

Previously total throughput was maxing out at 11mln/s, and gradually declining past 8 cores. With this change, it now keeps growing with each added CPU, reaching 142mln/s at 80 CPUs (this was measured on a 80-core Intel(R) Xeon(R) Gold 6138 CPU @ 2.00GHz).

Quoted 4 lines
Quoted 70 lines
---
 kernel/events/uprobes.c | 45 +++++++++++++++++++++++++++++++++++++++++
 1 file changed, 45 insertions(+)
kernel/events/uprobes.c +45 -0
index c4da8f741f3a..3f5577d4032a 100644
@@ -2295,6 +2295,47 @@ static int is_trap_at_addr(struct mm_struct *mm, unsigned long vaddr)
 	return is_trap_insn(&opcode);
 }
 
+static struct uprobe *find_active_uprobe_speculative(unsigned long bp_vaddr)
+{
+	struct mm_struct *mm = current->mm;
+	struct uprobe *uprobe = NULL;
+	struct vm_area_struct *vma;
+	struct file *vm_file;
+	loff_t offset;
+	unsigned int seq;
+
+	guard(rcu)();
+
+	if (!mmap_lock_speculate_try_begin(mm, &seq))
+		return NULL;
+
+	vma = vma_lookup(mm, bp_vaddr);
+	if (!vma)
+		return NULL;
+
+	/*
+	 * vm_file memory can be reused for another instance of struct file,
+	 * but can't be freed from under us, so it's safe to read fields from
+	 * it, even if the values are some garbage values; ultimately
+	 * find_uprobe_rcu() + mmap_lock_speculation_end() check will ensure
+	 * that whatever we speculatively found is correct
+	 */
+	vm_file = READ_ONCE(vma->vm_file);
+	if (!vm_file)
+		return NULL;
+
+	offset = (loff_t)(vma->vm_pgoff << PAGE_SHIFT) + (bp_vaddr - vma->vm_start);
+	uprobe = find_uprobe_rcu(vm_file->f_inode, offset);
+	if (!uprobe)
+		return NULL;
+
+	/* now double check that nothing about MM changed */
+	if (mmap_lock_speculate_retry(mm, seq))
+		return NULL;
+
+	return uprobe;
+}
+
 /* assumes being inside RCU protected region */
 static struct uprobe *find_active_uprobe_rcu(unsigned long bp_vaddr, int *is_swbp)
 {
@@ -2302,6 +2343,10 @@ static struct uprobe *find_active_uprobe_rcu(unsigned long bp_vaddr, int *is_swb
 	struct uprobe *uprobe = NULL;
 	struct vm_area_struct *vma;
 
+	uprobe = find_active_uprobe_speculative(bp_vaddr);
+	if (uprobe)
+		return uprobe;
+
 	mmap_read_lock(mm);
 	vma = vma_lookup(mm, bp_vaddr);
 	if (vma) {
Signature · 1 line
2.43.5
#8 lore raw

[tip: perf/core] uprobes: add speculative lockless VMA-to-inode-to-uprobe resolution

In reply to Andrii Nakryiko
The following commit has been merged into the perf/core branch of tip:

The following commit has been merged into the perf/core branch of tip:

Commit-ID:     e0925f2dc4de2d8ba987392d3239e8edf88f8b96
Gitweb:        https://git.kernel.org/tip/e0925f2dc4de2d8ba987392d3239e8edf88f8b96
Author:        Andrii Nakryiko <[email protected]>
AuthorDate:    Thu, 21 Nov 2024 19:59:22 -08:00
Committer:     Peter Zijlstra <[email protected]>
CommitterDate: Mon, 02 Dec 2024 12:01:38 +01:00

uprobes: add speculative lockless VMA-to-inode-to-uprobe resolution

Given filp_cachep is marked SLAB_TYPESAFE_BY_RCU (and FMODE_BACKING files, a special case, now goes through RCU-delated freeing), we can safely access vma->vm_file->f_inode field locklessly under just rcu_read_lock() protection, which enables looking up uprobe from uprobes_tree completely locklessly and speculatively without the need to acquire mmap_lock for reads. In most cases, anyway, assuming that there are no parallel mm and/or VMA modifications. The underlying struct file's memory won't go away from under us (even if struct file can be reused in the meantime).

We rely on newly added mmap_lock_speculate_{try_begin,retry}() helpers to validate that mm_struct stays intact for entire duration of this speculation. If not, we fall back to mmap_lock-protected lookup. The speculative logic is written in such a way that it will safely handle any garbage values that might be read from vma or file structs.

Benchmarking results speak for themselves.

BEFORE (latest tip/perf/core)
=============================

uprobe-nop            ( 1 cpus):    3.384 ± 0.004M/s  (  3.384M/s/cpu)
uprobe-nop            ( 2 cpus):    5.456 ± 0.005M/s  (  2.728M/s/cpu)
uprobe-nop            ( 3 cpus):    7.863 ± 0.015M/s  (  2.621M/s/cpu)
uprobe-nop            ( 4 cpus):    9.442 ± 0.008M/s  (  2.360M/s/cpu)
uprobe-nop            ( 5 cpus):   11.036 ± 0.013M/s  (  2.207M/s/cpu)
uprobe-nop            ( 6 cpus):   10.884 ± 0.019M/s  (  1.814M/s/cpu)
uprobe-nop            ( 7 cpus):    7.897 ± 0.145M/s  (  1.128M/s/cpu)
uprobe-nop            ( 8 cpus):   10.021 ± 0.128M/s  (  1.253M/s/cpu)
uprobe-nop            (10 cpus):    9.932 ± 0.170M/s  (  0.993M/s/cpu)
uprobe-nop            (12 cpus):    8.369 ± 0.056M/s  (  0.697M/s/cpu)
uprobe-nop            (14 cpus):    8.678 ± 0.017M/s  (  0.620M/s/cpu)
uprobe-nop            (16 cpus):    7.392 ± 0.003M/s  (  0.462M/s/cpu)
uprobe-nop            (24 cpus):    5.326 ± 0.178M/s  (  0.222M/s/cpu)
uprobe-nop            (32 cpus):    5.426 ± 0.059M/s  (  0.170M/s/cpu)
uprobe-nop            (40 cpus):    5.262 ± 0.070M/s  (  0.132M/s/cpu)
uprobe-nop            (48 cpus):    6.121 ± 0.010M/s  (  0.128M/s/cpu)
uprobe-nop            (56 cpus):    6.252 ± 0.035M/s  (  0.112M/s/cpu)
uprobe-nop            (64 cpus):    7.644 ± 0.023M/s  (  0.119M/s/cpu)
uprobe-nop            (72 cpus):    7.781 ± 0.001M/s  (  0.108M/s/cpu)
uprobe-nop            (80 cpus):    8.992 ± 0.048M/s  (  0.112M/s/cpu)

AFTER
=====

uprobe-nop            ( 1 cpus):    3.534 ± 0.033M/s  (  3.534M/s/cpu)
uprobe-nop            ( 2 cpus):    6.701 ± 0.007M/s  (  3.351M/s/cpu)
uprobe-nop            ( 3 cpus):   10.031 ± 0.007M/s  (  3.344M/s/cpu)
uprobe-nop            ( 4 cpus):   13.003 ± 0.012M/s  (  3.251M/s/cpu)
uprobe-nop            ( 5 cpus):   16.274 ± 0.006M/s  (  3.255M/s/cpu)
uprobe-nop            ( 6 cpus):   19.563 ± 0.024M/s  (  3.261M/s/cpu)
uprobe-nop            ( 7 cpus):   22.696 ± 0.054M/s  (  3.242M/s/cpu)
uprobe-nop            ( 8 cpus):   24.534 ± 0.010M/s  (  3.067M/s/cpu)
uprobe-nop            (10 cpus):   30.475 ± 0.117M/s  (  3.047M/s/cpu)
uprobe-nop            (12 cpus):   33.371 ± 0.017M/s  (  2.781M/s/cpu)
uprobe-nop            (14 cpus):   38.864 ± 0.004M/s  (  2.776M/s/cpu)
uprobe-nop            (16 cpus):   41.476 ± 0.020M/s  (  2.592M/s/cpu)
uprobe-nop            (24 cpus):   64.696 ± 0.021M/s  (  2.696M/s/cpu)
uprobe-nop            (32 cpus):   85.054 ± 0.027M/s  (  2.658M/s/cpu)
uprobe-nop            (40 cpus):  101.979 ± 0.032M/s  (  2.549M/s/cpu)
uprobe-nop            (48 cpus):  110.518 ± 0.056M/s  (  2.302M/s/cpu)
uprobe-nop            (56 cpus):  117.737 ± 0.020M/s  (  2.102M/s/cpu)
uprobe-nop            (64 cpus):  124.613 ± 0.079M/s  (  1.947M/s/cpu)
uprobe-nop            (72 cpus):  133.239 ± 0.032M/s  (  1.851M/s/cpu)
uprobe-nop            (80 cpus):  142.037 ± 0.138M/s  (  1.775M/s/cpu)

Previously total throughput was maxing out at 11mln/s, and gradually declining past 8 cores. With this change, it now keeps growing with each added CPU, reaching 142mln/s at 80 CPUs (this was measured on a 80-core Intel(R) Xeon(R) Gold 6138 CPU @ 2.00GHz).

---
 kernel/events/uprobes.c | 45 ++++++++++++++++++++++++++++++++++++++++-
 1 file changed, 45 insertions(+)
kernel/events/uprobes.c +45 -0
index 62c14df..daf4314 100644
@@ -2294,6 +2294,47 @@ static int is_trap_at_addr(struct mm_struct *mm, unsigned long vaddr)
 	return is_trap_insn(&opcode);
 }
 
+static struct uprobe *find_active_uprobe_speculative(unsigned long bp_vaddr)
+{
+	struct mm_struct *mm = current->mm;
+	struct uprobe *uprobe = NULL;
+	struct vm_area_struct *vma;
+	struct file *vm_file;
+	loff_t offset;
+	unsigned int seq;
+
+	guard(rcu)();
+
+	if (!mmap_lock_speculate_try_begin(mm, &seq))
+		return NULL;
+
+	vma = vma_lookup(mm, bp_vaddr);
+	if (!vma)
+		return NULL;
+
+	/*
+	 * vm_file memory can be reused for another instance of struct file,
+	 * but can't be freed from under us, so it's safe to read fields from
+	 * it, even if the values are some garbage values; ultimately
+	 * find_uprobe_rcu() + mmap_lock_speculation_end() check will ensure
+	 * that whatever we speculatively found is correct
+	 */
+	vm_file = READ_ONCE(vma->vm_file);
+	if (!vm_file)
+		return NULL;
+
+	offset = (loff_t)(vma->vm_pgoff << PAGE_SHIFT) + (bp_vaddr - vma->vm_start);
+	uprobe = find_uprobe_rcu(vm_file->f_inode, offset);
+	if (!uprobe)
+		return NULL;
+
+	/* now double check that nothing about MM changed */
+	if (mmap_lock_speculate_retry(mm, seq))
+		return NULL;
+
+	return uprobe;
+}
+
 /* assumes being inside RCU protected region */
 static struct uprobe *find_active_uprobe_rcu(unsigned long bp_vaddr, int *is_swbp)
 {
@@ -2301,6 +2342,10 @@ static struct uprobe *find_active_uprobe_rcu(unsigned long bp_vaddr, int *is_swb
 	struct uprobe *uprobe = NULL;
 	struct vm_area_struct *vma;
 
+	uprobe = find_active_uprobe_speculative(bp_vaddr);
+	if (uprobe)
+		return uprobe;
+
 	mmap_read_lock(mm);
 	vma = vma_lookup(mm, bp_vaddr);
 	if (vma) {
maintainer
#9 lore raw
In reply to Andrii Nakryiko
Quoted 3 lines · Andrii Nakryiko

Andrii Nakryiko (2):
uprobes: simplify find_active_uprobe_rcu() VMA checks
uprobes: add speculative lockless VMA-to-inode-to-uprobe resolution

Thanks, assuming Suren is okay with me carrying his patches through tip, I'll make this land in tip/perf/core after -rc1.

#10 lore raw
Quoted 9 lines · Peter Zijlstra
Quoted 3 lines · Andrii Nakryiko

Andrii Nakryiko (2):
uprobes: simplify find_active_uprobe_rcu() VMA checks
uprobes: add speculative lockless VMA-to-inode-to-uprobe resolution

Thanks, assuming Suren is okay with me carrying his patches through tip, I'll make this land in tip/perf/core after -rc1.

No objections from me. Thanks!

#11 lore raw
Quoted 5 lines · Suren Baghdasaryan
Quoted 3 lines · Peter Zijlstra

On Thu, Nov 21, 2024 at 07:59:20PM -0800, Andrii Nakryiko wrote:

Quoted 8 lines
Quoted 6 lines
Quoted 3 lines

Andrii Nakryiko (2):
uprobes: simplify find_active_uprobe_rcu() VMA checks
uprobes: add speculative lockless VMA-to-inode-to-uprobe resolution

Thanks, assuming Suren is okay with me carrying his patches through tip, I'll make this land in tip/perf/core after -rc1.

No objections from me. Thanks!

I just fixed a build issue in one of my patches for an odd config, so please use the latest version of the patchset from here:
https://lore.kernel.org/all/[email protected]/

maintainer
#12 lore raw
Quoted 10 lines · Suren Baghdasaryan
Quoted 9 lines · Suren Baghdasaryan
Quoted 7 lines · Peter Zijlstra
Quoted 3 lines · Andrii Nakryiko

Andrii Nakryiko (2):
uprobes: simplify find_active_uprobe_rcu() VMA checks
uprobes: add speculative lockless VMA-to-inode-to-uprobe resolution

Quoted 8 lines
Quoted 4 lines
Quoted 2 lines

Thanks, assuming Suren is okay with me carrying his patches through tip, I'll make this land in tip/perf/core after -rc1.

No objections from me. Thanks!

I just fixed a build issue in one of my patches for an odd config, so please use the latest version of the patchset from here:
https://lore.kernel.org/all/[email protected]/

updated, thanks!

#13 lore raw
Quoted 15 lines · Peter Zijlstra
Quoted 13 lines · Suren Baghdasaryan
Quoted 12 lines · Suren Baghdasaryan
Quoted 9 lines · Peter Zijlstra
Quoted 3 lines · Andrii Nakryiko

Andrii Nakryiko (2):
uprobes: simplify find_active_uprobe_rcu() VMA checks
uprobes: add speculative lockless VMA-to-inode-to-uprobe resolution

Thanks, assuming Suren is okay with me carrying his patches through tip, I'll make this land in tip/perf/core after -rc1.

Quoted 7 lines
Quoted 5 lines
Quoted 1 line

No objections from me. Thanks!

I just fixed a build issue in one of my patches for an odd config, so please use the latest version of the patchset from here:
https://lore.kernel.org/all/[email protected]/

updated, thanks!

Hi Andrew,
I just noticed that patches from an old version of my patchset are present in mm-unstable, more specifically these two:

fb23aacd2a14 "mm: convert mm_lock_seq to a proper seqcount" 549aeb99ccf1 "mm: introduce mmap_lock_speculation_{begin|end}"

Peter will be merging the latest version into tip/perf/core, so this will cause a conflict at some point.
It should be easy to update them in mm-unstable to the latest version [1]. I was able to revert the old ones and apply the new ones without any merge conflict. If possible, please update them instead of dropping them from mm-unstable. Some patches I'm preparing to post have dependencies on this patchset.
Thanks,
Suren.

[1] https://lore.kernel.org/all/[email protected]/