Received-SPF: pass (google.com: best guess record for domain of linux-kernel-owner@vger.kernel.org designates 209.132.180.67 as permitted sender) client-ip=209.132.180.67;
MIME-Version: 1.0
References: <1533767600-7794-1-git-send-email-eranian@google.com>
 <20180809080721.GB19243@krava> <CABPqkBQEfoMDEqot1VbgExg1fU3+EEunzZqDFKSGmLKBhxNkwA@mail.gmail.com>
 <20180810115431.GA4162@krava> <20180813130446.GA8685@krava>
 <CABPqkBSgYEFFAkddBqZbYXe9tjUY7RbMBjQsZht8ki1iOR6unw@mail.gmail.com>
 <20180815084825.GD3180@krava> <20180827092818.GA3725@krava>
In-Reply-To: <20180827092818.GA3725@krava>
From:   Stephane Eranian <eranian@google.com>
Date:   Mon, 27 Aug 2018 08:24:56 -0700
Message-ID: <CABPqkBQS+QG1jjzMU=wpuOJXD5A8iiPj3fNZoHSsPep7rfEQow@mail.gmail.com>
Subject: Re: [PATCHv2] perf tools: Add struct ordered_events_buffer layer
To:     Jiri Olsa <jolsa@redhat.com>
Cc:     LKML <linux-kernel@vger.kernel.org>,
        Arnaldo Carvalho de Melo <acme@redhat.com>,
        Peter Zijlstra <peterz@infradead.org>, mingo@elte.hu,
        Namhyung Kim <namhyung@kernel.org>
Content-Type: text/plain; charset="UTF-8"
Sender: linux-kernel-owner@vger.kernel.org
Precedence: bulk

Jiri,


On Mon, Aug 27, 2018 at 2:28 AM Jiri Olsa <jolsa@redhat.com> wrote:
>
> On Wed, Aug 15, 2018 at 10:48:25AM +0200, Jiri Olsa wrote:
> > On Tue, Aug 14, 2018 at 12:14:19AM -0700, Stephane Eranian wrote:
> >
> > SNIP
> >
> > > > @@ -104,11 +110,12 @@ static struct ordered_event *alloc_event(struct ordered_events *oe,
> > > >                 new = list_entry(cache->next, struct ordered_event, list);
> > > >                 list_del(&new->list);
> > > >         } else if (oe->buffer) {
> > > > -               new = oe->buffer + oe->buffer_idx;
> > > > +               new = &oe->buffer->event[oe->buffer_idx];
> > > >                 if (++oe->buffer_idx == MAX_SAMPLE_BUFFER)
> > > >                         oe->buffer = NULL;
> > > >         } else if (oe->cur_alloc_size < oe->max_alloc_size) {
> > > > -               size_t size = MAX_SAMPLE_BUFFER * sizeof(*new);
> > > > +               size_t size = sizeof(*oe->buffer) +
> > > > +                             MAX_SAMPLE_BUFFER * sizeof(*new);
> > > >
> > > >                 oe->buffer = malloc(size);
> > > >                 if (!oe->buffer) {
> > > > @@ -122,9 +129,8 @@ static struct ordered_event *alloc_event(struct ordered_events *oe,
> > > >                 oe->cur_alloc_size += size;
> > > >                 list_add(&oe->buffer->list, &oe->to_free);
> > > >
> > > > -               /* First entry is abused to maintain the to_free list. */
> > > > -               oe->buffer_idx = 2;
> > > > -               new = oe->buffer + 1;
> > > > +               oe->buffer_idx = 1;
> > > > +               new = &oe->buffer->event[0];
> > >
> > > Ok, but I think this section between the malloc() and the line above
> > > needs some comments to clarify what is going on.
> > > It is still hard to read.
> >
> > ok, I put some bigger comment at the top, but I'm not too happy
> > feel free to suggest different one ;-)
> >
> > >
> > > >         } else {
> > > >                 pr("allocation limit reached %" PRIu64 "B\n", oe->max_alloc_size);
> > > >         }
> > > > @@ -300,15 +306,27 @@ void ordered_events__init(struct ordered_events *oe, ordered_events__deliver_t d
> > > >         oe->deliver        = deliver;
> > > >  }
> > > >
> > > > +static void
> > > > +ordered_events_buffer__free(struct ordered_events_buffer *buffer,
> > > > +                           struct ordered_events *oe)
> > > > +{
> > > > +       if (oe->copy_on_queue) {
> > > > +               unsigned int i;
> > > > +
> > > > +               for (i = 0; i < MAX_SAMPLE_BUFFER; i++)
> > > > +                       __free_dup_event(oe, buffer->event[i].event);
> > > > +       }
> > > > +
> > > I have a problem with this one, given that the buffer->event[] is
> > > never actually zeroed.
> > > So what happens if you do not use all the entries by the time you have to free?
> > > I think one way to avoid this is by iterating only all the way to
> > > oe->buffer_idx.
> >
> > right, please check attached patch
>
> any comments? attaching v2
>
> thanks,
> jirka
>
>
> ---
> When ordering events, we use preallocated buffers to store separated
> events. Those buffers currently don't have their own struct, but since
> they are basically array of 'struct ordered_event' objects, we use the
> first event to hold buffers data - list head, that holds all buffers
> together:
>
>    struct ordered_events {
>      ...
>      struct ordered_event *buffer;
>      ...
>    };
>
>    struct ordered_event {
>      u64               timestamp;
>      u64               file_offset;
>      union perf_event  *event;
>      struct list_head  list;
>    };
>
> This is quite convoluted and error prone as demonstrated by
> free-ing issue discovered and fixed by Stephane in here [1].
>
> This patch adds the 'struct ordered_events_buffer' object,
> that holds the buffer data and frees it up properly.
>
> [1] - https://marc.info/?l=linux-kernel&m=153376761329335&w=2
>
> Reported-by: Stephane Eranian <eranian@google.com>
> Link: http://lkml.kernel.org/n/tip-qrkcqm5m1sugy4q83pfn5a1r@git.kernel.org
> Signed-off-by: Jiri Olsa <jolsa@kernel.org>
> ---
>  tools/perf/util/ordered-events.c | 82 +++++++++++++++++++++++++++-----
>  tools/perf/util/ordered-events.h | 37 +++++++-------
>  2 files changed, 90 insertions(+), 29 deletions(-)
>
> diff --git a/tools/perf/util/ordered-events.c b/tools/perf/util/ordered-events.c
> index bad9e0296e9a..3672060508a7 100644
> --- a/tools/perf/util/ordered-events.c
> +++ b/tools/perf/util/ordered-events.c
> @@ -80,14 +80,20 @@ static union perf_event *dup_event(struct ordered_events *oe,
>         return oe->copy_on_queue ? __dup_event(oe, event) : event;
>  }
>
> -static void free_dup_event(struct ordered_events *oe, union perf_event *event)
> +static void __free_dup_event(struct ordered_events *oe, union perf_event *event)
>  {
> -       if (event && oe->copy_on_queue) {
> +       if (event) {
>                 oe->cur_alloc_size -= event->header.size;
>                 free(event);
>         }
>  }
>
> +static void free_dup_event(struct ordered_events *oe, union perf_event *event)
> +{
> +       if (oe->copy_on_queue)
> +               __free_dup_event(oe, event);
> +}
> +
>  #define MAX_SAMPLE_BUFFER      (64 * 1024 / sizeof(struct ordered_event))
>  static struct ordered_event *alloc_event(struct ordered_events *oe,
>                                          union perf_event *event)
> @@ -100,15 +106,43 @@ static struct ordered_event *alloc_event(struct ordered_events *oe,
>         if (!new_event)
>                 return NULL;
>
> +       /*
> +        * We maintain following scheme of buffers for ordered
> +        * event allocation:
> +        *
> +        *   to_free list -> buffer1 (64K)
> +        *                   buffer2 (64K)
> +        *                   ...
> +        *
> +        * Each buffer keeps an array of ordered events objects:
> +        *    buffer -> event[0]
> +        *              event[1]
> +        *              ...
> +        *
> +        * Each allocated ordered event is linked to one of
> +        * following lists:
> +        *   - time ordered list 'events'
> +        *   - list of currently removed events 'cache'
> +        *
> +        * Allocation of the ordered event uses following order
> +        * to get the memory:
> +        *   - use recently removed object from 'cache' list
> +        *   - use available object in current allocation buffer
> +        *   - allocate new buffer if the current buffer is full
> +        *
> +        * Removal of ordered event object moves it from events to
> +        * the cache list.
> +        */
>         if (!list_empty(cache)) {
>                 new = list_entry(cache->next, struct ordered_event, list);
>                 list_del(&new->list);
>         } else if (oe->buffer) {
> -               new = oe->buffer + oe->buffer_idx;
> +               new = &oe->buffer->event[oe->buffer_idx];
>                 if (++oe->buffer_idx == MAX_SAMPLE_BUFFER)
>                         oe->buffer = NULL;
>         } else if (oe->cur_alloc_size < oe->max_alloc_size) {
> -               size_t size = MAX_SAMPLE_BUFFER * sizeof(*new);
> +               size_t size = sizeof(*oe->buffer) +
> +                             MAX_SAMPLE_BUFFER * sizeof(*new);
>
>                 oe->buffer = malloc(size);
>                 if (!oe->buffer) {
> @@ -122,9 +156,8 @@ static struct ordered_event *alloc_event(struct ordered_events *oe,
>                 oe->cur_alloc_size += size;
>                 list_add(&oe->buffer->list, &oe->to_free);
>
> -               /* First entry is abused to maintain the to_free list. */
> -               oe->buffer_idx = 2;
> -               new = oe->buffer + 1;
> +               oe->buffer_idx = 1;
> +               new = &oe->buffer->event[0];
>         } else {
>                 pr("allocation limit reached %" PRIu64 "B\n", oe->max_alloc_size);


I am wondering about the usefulness of returning a new_event with
new_event->event = NULL
in this case. Don't you need new_event->event? If so, then you need return NULL.

>         }
> @@ -300,15 +333,38 @@ void ordered_events__init(struct ordered_events *oe, ordered_events__deliver_t d
>         oe->deliver        = deliver;
>  }
>
> +static void
> +ordered_events_buffer__free(struct ordered_events_buffer *buffer,
> +                           unsigned int max, struct ordered_events *oe)
> +{
> +       if (oe->copy_on_queue) {
> +               unsigned int i;
> +
> +               for (i = 0; i < max; i++)
> +                       __free_dup_event(oe, buffer->event[i].event);
> +       }
> +
> +       free(buffer);
> +}
> +
>  void ordered_events__free(struct ordered_events *oe)
>  {
> -       while (!list_empty(&oe->to_free)) {
> -               struct ordered_event *event;
> +       struct ordered_events_buffer *buffer, *tmp;
>
> -               event = list_entry(oe->to_free.next, struct ordered_event, list);
> -               list_del(&event->list);
> -               free_dup_event(oe, event->event);
> -               free(event);
> +       if (list_empty(&oe->to_free))
> +               return;
> +
> +       /*
> +        * Current buffer might not have all the events allocated
> +        * yet, we need to free only allocated ones ...
> +        */
> +       list_del(&oe->buffer->list);
> +       ordered_events_buffer__free(oe->buffer, oe->buffer_idx, oe);
> +
> +       /* ... and continue with the rest */
> +       list_for_each_entry_safe(buffer, tmp, &oe->to_free, list) {
> +               list_del(&buffer->list);
> +               ordered_events_buffer__free(buffer, MAX_SAMPLE_BUFFER, oe);


Here you are saying that if it is on the to_free list and not the
current buffer, then necessarily
all the entries have been used and it is safe to use
MAX_SAMPLE_BUFFER. Is that right?

>         }
>  }
>
> diff --git a/tools/perf/util/ordered-events.h b/tools/perf/util/ordered-events.h
> index 8c7a2948593e..1338d5c345dc 100644
> --- a/tools/perf/util/ordered-events.h
> +++ b/tools/perf/util/ordered-events.h
> @@ -25,23 +25,28 @@ struct ordered_events;
>  typedef int (*ordered_events__deliver_t)(struct ordered_events *oe,
>                                          struct ordered_event *event);
>
> +struct ordered_events_buffer {
> +       struct list_head        list;
> +       struct ordered_event    event[0];
> +};
> +
>  struct ordered_events {
> -       u64                     last_flush;
> -       u64                     next_flush;
> -       u64                     max_timestamp;
> -       u64                     max_alloc_size;
> -       u64                     cur_alloc_size;
> -       struct list_head        events;
> -       struct list_head        cache;
> -       struct list_head        to_free;
> -       struct ordered_event    *buffer;
> -       struct ordered_event    *last;
> -       ordered_events__deliver_t deliver;
> -       int                     buffer_idx;
> -       unsigned int            nr_events;
> -       enum oe_flush           last_flush_type;
> -       u32                     nr_unordered_events;
> -       bool                    copy_on_queue;
> +       u64                              last_flush;
> +       u64                              next_flush;
> +       u64                              max_timestamp;
> +       u64                              max_alloc_size;
> +       u64                              cur_alloc_size;
> +       struct list_head                 events;
> +       struct list_head                 cache;
> +       struct list_head                 to_free;
> +       struct ordered_events_buffer    *buffer;
> +       struct ordered_event            *last;
> +       ordered_events__deliver_t        deliver;
> +       int                              buffer_idx;
> +       unsigned int                     nr_events;
> +       enum oe_flush                    last_flush_type;
> +       u32                              nr_unordered_events;
> +       bool                             copy_on_queue;
>  };
>
>  int ordered_events__queue(struct ordered_events *oe, union perf_event *event,
> --
> 2.17.1
>