Received-SPF: pass (google.com: domain of linux-kernel+bounces-119414-linux.lists.archive=gmail.com@vger.kernel.org designates 2604:1380:45d1:ec00::1 as permitted sender) client-ip=2604:1380:45d1:ec00::1;
Precedence: bulk
MIME-Version: 1.0
References: <20240321145736.2373846-1-jonathan.haslam@gmail.com> <20240325120323.ec3248d330b2755e73a6571e@kernel.org>
In-Reply-To: <20240325120323.ec3248d330b2755e73a6571e@kernel.org>
From: Andrii Nakryiko <andrii.nakryiko@gmail.com>
Date: Tue, 26 Mar 2024 09:01:47 -0700
Message-ID: <CAEf4BzZS_QCsSY0oGY_3pGveGfXKK_TkVURyNq=UQXVXSqi2Fw@mail.gmail.com>
Subject: Re: [PATCH] uprobes: reduce contention on uprobes_tree access
To: Masami Hiramatsu <mhiramat@kernel.org>
Cc: Jonathan Haslam <jonathan.haslam@gmail.com>, linux-trace-kernel@vger.kernel.org, 
	andrii@kernel.org, bpf@vger.kernel.org, rostedt@goodmis.org, 
	Peter Zijlstra <peterz@infradead.org>, Ingo Molnar <mingo@redhat.com>, 
	Arnaldo Carvalho de Melo <acme@kernel.org>, Namhyung Kim <namhyung@kernel.org>, 
	Mark Rutland <mark.rutland@arm.com>, 
	Alexander Shishkin <alexander.shishkin@linux.intel.com>, Jiri Olsa <jolsa@kernel.org>, 
	Ian Rogers <irogers@google.com>, Adrian Hunter <adrian.hunter@intel.com>, 
	linux-perf-users@vger.kernel.org, linux-kernel@vger.kernel.org
Content-Type: text/plain; charset="UTF-8"
Content-Transfer-Encoding: quoted-printable

On Sun, Mar 24, 2024 at 8:03=E2=80=AFPM Masami Hiramatsu <mhiramat@kernel.o=
rg> wrote:
>
> On Thu, 21 Mar 2024 07:57:35 -0700
> Jonathan Haslam <jonathan.haslam@gmail.com> wrote:
>
> > Active uprobes are stored in an RB tree and accesses to this tree are
> > dominated by read operations. Currently these accesses are serialized b=
y
> > a spinlock but this leads to enormous contention when large numbers of
> > threads are executing active probes.
> >
> > This patch converts the spinlock used to serialize access to the
> > uprobes_tree RB tree into a reader-writer spinlock. This lock type
> > aligns naturally with the overwhelmingly read-only nature of the tree
> > usage here. Although the addition of reader-writer spinlocks are
> > discouraged [0], this fix is proposed as an interim solution while an
> > RCU based approach is implemented (that work is in a nascent form). Thi=
s
> > fix also has the benefit of being trivial, self contained and therefore
> > simple to backport.
> >
> > This change has been tested against production workloads that exhibit
> > significant contention on the spinlock and an almost order of magnitude
> > reduction for mean uprobe execution time is observed (28 -> 3.5 microse=
cs).
>
> Looks good to me.
>
> Acked-by: Masami Hiramatsu (Google) <mhiramat@kernel.org>

Masami,

Given the discussion around per-cpu rw semaphore and need for
(internal) batched attachment API for uprobes, do you think you can
apply this patch as is for now? We can then gain initial improvements
in scalability that are also easy to backport, and Jonathan will work
on a more complete solution based on per-cpu RW semaphore, as
suggested by Ingo.

>
> BTW, how did you measure the overhead? I think spinlock overhead
> will depend on how much lock contention happens.
>
> Thank you,
>
> >
> > [0] https://docs.kernel.org/locking/spinlocks.html
> >
> > Signed-off-by: Jonathan Haslam <jonathan.haslam@gmail.com>
> > ---
> >  kernel/events/uprobes.c | 22 +++++++++++-----------
> >  1 file changed, 11 insertions(+), 11 deletions(-)
> >
> > diff --git a/kernel/events/uprobes.c b/kernel/events/uprobes.c
> > index 929e98c62965..42bf9b6e8bc0 100644
> > --- a/kernel/events/uprobes.c
> > +++ b/kernel/events/uprobes.c
> > @@ -39,7 +39,7 @@ static struct rb_root uprobes_tree =3D RB_ROOT;
> >   */
> >  #define no_uprobe_events()   RB_EMPTY_ROOT(&uprobes_tree)
> >
> > -static DEFINE_SPINLOCK(uprobes_treelock);    /* serialize rbtree acces=
s */
> > +static DEFINE_RWLOCK(uprobes_treelock);      /* serialize rbtree acces=
s */
> >
> >  #define UPROBES_HASH_SZ      13
> >  /* serialize uprobe->pending_list */
> > @@ -669,9 +669,9 @@ static struct uprobe *find_uprobe(struct inode *ino=
de, loff_t offset)
> >  {
> >       struct uprobe *uprobe;
> >
> > -     spin_lock(&uprobes_treelock);
> > +     read_lock(&uprobes_treelock);
> >       uprobe =3D __find_uprobe(inode, offset);
> > -     spin_unlock(&uprobes_treelock);
> > +     read_unlock(&uprobes_treelock);
> >
> >       return uprobe;
> >  }
> > @@ -701,9 +701,9 @@ static struct uprobe *insert_uprobe(struct uprobe *=
uprobe)
> >  {
> >       struct uprobe *u;
> >
> > -     spin_lock(&uprobes_treelock);
> > +     write_lock(&uprobes_treelock);
> >       u =3D __insert_uprobe(uprobe);
> > -     spin_unlock(&uprobes_treelock);
> > +     write_unlock(&uprobes_treelock);
> >
> >       return u;
> >  }
> > @@ -935,9 +935,9 @@ static void delete_uprobe(struct uprobe *uprobe)
> >       if (WARN_ON(!uprobe_is_active(uprobe)))
> >               return;
> >
> > -     spin_lock(&uprobes_treelock);
> > +     write_lock(&uprobes_treelock);
> >       rb_erase(&uprobe->rb_node, &uprobes_tree);
> > -     spin_unlock(&uprobes_treelock);
> > +     write_unlock(&uprobes_treelock);
> >       RB_CLEAR_NODE(&uprobe->rb_node); /* for uprobe_is_active() */
> >       put_uprobe(uprobe);
> >  }
> > @@ -1298,7 +1298,7 @@ static void build_probe_list(struct inode *inode,
> >       min =3D vaddr_to_offset(vma, start);
> >       max =3D min + (end - start) - 1;
> >
> > -     spin_lock(&uprobes_treelock);
> > +     read_lock(&uprobes_treelock);
> >       n =3D find_node_in_range(inode, min, max);
> >       if (n) {
> >               for (t =3D n; t; t =3D rb_prev(t)) {
> > @@ -1316,7 +1316,7 @@ static void build_probe_list(struct inode *inode,
> >                       get_uprobe(u);
> >               }
> >       }
> > -     spin_unlock(&uprobes_treelock);
> > +     read_unlock(&uprobes_treelock);
> >  }
> >
> >  /* @vma contains reference counter, not the probed instruction. */
> > @@ -1407,9 +1407,9 @@ vma_has_uprobes(struct vm_area_struct *vma, unsig=
ned long start, unsigned long e
> >       min =3D vaddr_to_offset(vma, start);
> >       max =3D min + (end - start) - 1;
> >
> > -     spin_lock(&uprobes_treelock);
> > +     read_lock(&uprobes_treelock);
> >       n =3D find_node_in_range(inode, min, max);
> > -     spin_unlock(&uprobes_treelock);
> > +     read_unlock(&uprobes_treelock);
> >
> >       return !!n;
> >  }
> > --
> > 2.43.0
> >
>
>
> --
> Masami Hiramatsu (Google) <mhiramat@kernel.org>