Received-SPF: pass (google.com: domain of linux-kernel+bounces-62343-linux.lists.archive=gmail.com@vger.kernel.org designates 2604:1380:45e3:2400::1 as permitted sender) client-ip=2604:1380:45e3:2400::1;
Precedence: bulk
MIME-Version: 1.0
References: <20240210031746.4057262-1-irogers@google.com> <20240210031746.4057262-2-irogers@google.com>
 <CAM9d7chEKepmHY_Mgvq27CEcKB1e8bENwn2=pMe-yin30nfGLA@mail.gmail.com>
 <CAP-5=fX7h9ku-XgjYe+3B5NWOJnapLnuJ_JqxywPaTu76VxazA@mail.gmail.com> <CAM9d7cgGAd7xEzwRxQFXoxpY9_gWduqYpy5jpp1zDTFjJqSxbw@mail.gmail.com>
In-Reply-To: <CAM9d7cgGAd7xEzwRxQFXoxpY9_gWduqYpy5jpp1zDTFjJqSxbw@mail.gmail.com>
From: Ian Rogers <irogers@google.com>
Date: Mon, 12 Feb 2024 12:37:15 -0800
Message-ID: <CAP-5=fUR7X-vyE1XgB-=B0_D59QACmKSD_gCq0Sn=dvx2GYQ4g@mail.gmail.com>
Subject: Re: [PATCH v3 1/6] perf maps: Switch from rbtree to lazily sorted
 array for addresses
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>, Song Liu <song@kernel.org>, 
	Colin Ian King <colin.i.king@gmail.com>, Liam Howlett <liam.howlett@oracle.com>, 
	K Prateek Nayak <kprateek.nayak@amd.com>, Artem Savkov <asavkov@redhat.com>, 
	Changbin Du <changbin.du@huawei.com>, Masami Hiramatsu <mhiramat@kernel.org>, 
	Athira Rajeev <atrajeev@linux.vnet.ibm.com>, Alexey Dobriyan <adobriyan@gmail.com>, 
	James Clark <james.clark@arm.com>, Vincent Whitchurch <vincent.whitchurch@axis.com>, 
	linux-perf-users@vger.kernel.org, linux-kernel@vger.kernel.org, 
	bpf@vger.kernel.org, leo.yan@linux.dev
Content-Type: text/plain; charset="UTF-8"
Content-Transfer-Encoding: quoted-printable

On Mon, Feb 12, 2024 at 12:26=E2=80=AFPM Namhyung Kim <namhyung@kernel.org>=
 wrote:
>
> On Mon, Feb 12, 2024 at 12:19=E2=80=AFPM Ian Rogers <irogers@google.com> =
wrote:
> >
> > On Mon, Feb 12, 2024 at 12:15=E2=80=AFPM Namhyung Kim <namhyung@kernel.=
org> wrote:
> > >
> > > On Fri, Feb 9, 2024 at 7:18=E2=80=AFPM Ian Rogers <irogers@google.com=
> wrote:
> > > >
> > > > Maps is a collection of maps primarily sorted by the starting addre=
ss
> > > > of the map. Prior to this change the maps were held in an rbtree
> > > > requiring 4 pointers per node. Prior to reference count checking, t=
he
> > > > rbnode was embedded in the map so 3 pointers per node were
> > > > necessary. This change switches the rbtree to an array lazily sorte=
d
> > > > by address, much as the array sorting nodes by name. 1 pointer is
> > > > needed per node, but to avoid excessive resizing the backing array =
may
> > > > be twice the number of used elements. Meaning the memory overhead i=
s
> > > > roughly half that of the rbtree. For a perf record with
> > > > "--no-bpf-event -g -a" of true, the memory overhead of perf inject =
is
> > > > reduce fom 3.3MB to 3MB, so 10% or 300KB is saved.
> > > >
> > > > Map inserts always happen at the end of the array. The code tracks
> > > > whether the insertion violates the sorting property. O(log n) rb-tr=
ee
> > > > complexity is switched to O(1).
> > > >
> > > > Remove slides the array, so O(log n) rb-tree complexity is degraded=
 to
> > > > O(n).
> > > >
> > > > A find may need to sort the array using qsort which is O(n*log n), =
but
> > > > in general the maps should be sorted and so average performance sho=
uld
> > > > be O(log n) as with the rbtree.
> > > >
> > > > An rbtree node consumes a cache line, but with the array 4 nodes fi=
t
> > > > on a cache line. Iteration is simplified to scanning an array rathe=
r
> > > > than pointer chasing.
> > > >
> > > > Overall it is expected the performance after the change should be
> > > > comparable to before, but with half of the memory consumed.
> > > >
> > > > To avoid a list and repeated logic around splitting maps,
> > > > maps__merge_in is rewritten in terms of
> > > > maps__fixup_overlap_and_insert. maps_merge_in splits the given mapp=
ing
> > > > inserting remaining gaps. maps__fixup_overlap_and_insert splits the
> > > > existing mappings, then adds the incoming mapping. By adding the ne=
w
> > > > mapping first, then re-inserting the existing mappings the splittin=
g
> > > > behavior matches.
> > > >
> > > > Signed-off-by: Ian Rogers <irogers@google.com>
> > > > Acked-by: Namhyung Kim <namhyung@kernel.org>
> > > > ---
> > > [SNIP]
> > > >  int maps__for_each_map(struct maps *maps, int (*cb)(struct map *ma=
p, void *data), void *data)
> > > >  {
> > > > -       struct map_rb_node *pos;
> > > > +       bool done =3D false;
> > > >         int ret =3D 0;
> > > >
> > > > -       down_read(maps__lock(maps));
> > > > -       maps__for_each_entry(maps, pos) {
> > > > -               ret =3D cb(pos->map, data);
> > > > -               if (ret)
> > > > -                       break;
> > > > +       /* See locking/sorting note. */
> > > > +       while (!done) {
> > > > +               down_read(maps__lock(maps));
> > > > +               if (maps__maps_by_address_sorted(maps)) {
> > > > +                       /*
> > > > +                        * maps__for_each_map callbacks may buggily=
/unsafely
> > > > +                        * insert into maps_by_address. Deliberatel=
y reload
> > > > +                        * maps__nr_maps and maps_by_address on eac=
h iteration
> > > > +                        * to avoid using memory freed by maps__ins=
ert growing
> > > > +                        * the array - this may cause maps to be sk=
ipped or
> > > > +                        * repeated.
> > > > +                        */
> > > > +                       for (unsigned int i =3D 0; i < maps__nr_map=
s(maps); i++) {
> > > > +                               struct map **maps_by_address =3D ma=
ps__maps_by_address(maps);
> > >
> > > Any chance they can move out of the loop?  I guess not as they are
> > > not marked to const/pure functions..
> >
> > It's not because the cb(...) call below will potentially modify
> > maps_by_address by inserting maps and reallocating the array. Having
> > it outside the loop was what caused the original bug.
>
> Oh, I meant if compiler can move them automatically.

The const (on the accessor) isn't sufficient for that, they'd perhaps
need to be restrict. maps here is neither const or restrict which
means the callback can modify it (even though it isn't an argument)
and the function here needs to reload its value.

Thanks,
Ian

> Thanks,
> Namhyung
>
> > >
> > >
> > > > +                               struct map *map =3D maps_by_address=
[i];
> > > > +
> > > > +                               ret =3D cb(map, data);
> > > > +                               if (ret)
> > > > +                                       break;
> > > > +                       }
> > > > +                       done =3D true;
> > > > +               }
> > > > +               up_read(maps__lock(maps));
> > > > +               if (!done)
> > > > +                       maps__sort_by_address(maps);
> > > >         }
> > > > -       up_read(maps__lock(maps));
> > > >         return ret;
> > > >  }