Received-SPF: pass (google.com: domain of linux-kernel-owner@vger.kernel.org designates 2620:137:e000::1:20 as permitted sender) client-ip=2620:137:e000::1:20;
MIME-Version: 1.0
References: <20230621063749.3358430-1-irogers@google.com> <CAM9d7cg-r7Nw807egNFVRBgEXwgBV=A2pVEb+MBS4gvFgnNynQ@mail.gmail.com>
 <CAP-5=fVBbXoGuNeaYADA1RgY4wfSN8CgAJVEBjmOQGZ=-OiOAQ@mail.gmail.com> <CAM9d7cixNAgxU58YNLHOpdZzDqk1t_ypOCQKEyo8+chFHd1HrQ@mail.gmail.com>
In-Reply-To: <CAM9d7cixNAgxU58YNLHOpdZzDqk1t_ypOCQKEyo8+chFHd1HrQ@mail.gmail.com>
From:   Ian Rogers <irogers@google.com>
Date:   Wed, 21 Jun 2023 22:54:30 -0700
Message-ID: <CAP-5=fXkjSEgFmKNYYBzh11+xVD=j_KCOS7eQf=sBAALpMWK-w@mail.gmail.com>
Subject: Re: [PATCH v2 1/2] perf symbol: Remove symbol_name_rb_node
To:     Namhyung Kim <namhyung@kernel.org>
Cc:     Peter Zijlstra <peterz@infradead.org>,
        Ingo Molnar <mingo@redhat.com>,
        Arnaldo Carvalho de Melo <acme@kernel.org>,
        Mark Rutland <mark.rutland@arm.com>,
        Alexander Shishkin <alexander.shishkin@linux.intel.com>,
        Jiri Olsa <jolsa@kernel.org>,
        Adrian Hunter <adrian.hunter@intel.com>,
        Kan Liang <kan.liang@linux.intel.com>,
        Yang Jihong <yangjihong1@huawei.com>,
        Carsten Haitzler <carsten.haitzler@arm.com>,
        Changbin Du <changbin.du@huawei.com>,
        Athira Rajeev <atrajeev@linux.vnet.ibm.com>,
        Christophe JAILLET <christophe.jaillet@wanadoo.fr>,
        Jason Wang <wangborong@cdjrlc.com>,
        linux-perf-users@vger.kernel.org, linux-kernel@vger.kernel.org
Content-Type: text/plain; charset="UTF-8"
Content-Transfer-Encoding: quoted-printable
Precedence: bulk

On Wed, Jun 21, 2023 at 10:21=E2=80=AFPM Namhyung Kim <namhyung@kernel.org>=
 wrote:
>
> On Wed, Jun 21, 2023 at 9:28=E2=80=AFPM Ian Rogers <irogers@google.com> w=
rote:
> >
> > On Wed, Jun 21, 2023 at 8:51=E2=80=AFPM Namhyung Kim <namhyung@kernel.o=
rg> wrote:
> > >
> > > Hi Ian,
> > >
> > > On Tue, Jun 20, 2023 at 11:37=E2=80=AFPM Ian Rogers <irogers@google.c=
om> wrote:
> > > >
> > > > Most perf commands want to sort symbols by name and this is done vi=
a
> > > > an invasive rbtree that on 64-bit systems costs 24 bytes. Sorting t=
he
> > > > symbols in a DSO by name is optional and not done by default, howev=
er,
> > > > if sorting is requested the 24 bytes is allocated for every
> > > > symbol.
> > > >
> > > > This change removes the rbtree and uses a sorted array of symbol
> > > > pointers instead (costing 8 bytes per symbol). As the array is crea=
ted
> > > > on demand then there are further memory savings. The complexity of
> > > > sorting the array and using the rbtree are the same.
> > > >
> > > > To support going to the next symbol, the index of the current symbo=
l
> > > > needs to be passed around as a pair with the current symbol. This
> > > > requires some API changes.
> > > >
> > > > Signed-off-by: Ian Rogers <irogers@google.com>
> > > >
> > > > v2. map__find_symbol_by_name_idx so that map__find_symbol_by_name
> > > >     doesn't need an optional parameter. Separate out
> > > >     symbol_conf.sort_by_name removal.
> > > > ---
> > >
> > > [SNIP]
> > > >  void dso__sort_by_name(struct dso *dso)
> > > >  {
> > > > -       dso__set_sorted_by_name(dso);
> > > > -       return symbols__sort_by_name(&dso->symbol_names, &dso->symb=
ols);
> > > > +       mutex_lock(&dso->lock);
> > > > +       if (!dso__sorted_by_name(dso)) {
> > > > +               size_t len;
> > > > +
> > > > +               dso->symbol_names =3D symbols__sort_by_name(&dso->s=
ymbols, &len);
> > > > +               if (dso->symbol_names) {
> > > > +                       dso->symbol_names_len =3D len;
> > > > +                       dso__set_sorted_by_name(dso);
> > > > +               }
> > > > +       }
> > > > +       mutex_unlock(&dso->lock);
> > >
> > > I think this part deserves a separate commit.
> >
> > Using the mutex or the use of sorted_by_name?
>
> For the mutex originally, but might be better to split further. :)

I can add the locks first. There's an obvious leak with the array
approach if two threads are sorting. With the invasive rbtree a leak
isn't possible but corruption could be.

> And now it grabs the mutex unconditionally, I think
> we can check the condition without the mutex first
> and again with the mutex if not sorted.

Is there a kernel pattern for double checked locking that isn't broken
in the normal ways double checked locking is broken?
https://www.cs.umd.edu/~pugh/java/memoryModel/DoubleCheckedLocking.html

Thanks,
Ian

> Thanks,
> Namhyung