* [PATCH v2] perf ordered_events: fix crash in free_dup_event()
@ 2018-08-08 22:33 Stephane Eranian
2018-08-09 8:07 ` Jiri Olsa
0 siblings, 1 reply; 15+ messages in thread
From: Stephane Eranian @ 2018-08-08 22:33 UTC (permalink / raw)
To: linux-kernel; +Cc: acme, peterz, mingo, jolsa
This patch fixes a bug in ordered_event.c:alloc_event().
An ordered_event struct was not initialized properly potentially
causing crashes later on in free_dup_event() depending on the
content of the memory. If it was NULL, then it would work fine,
otherwise, it could cause crashes such as:
$ perf record -o - -e cycles date | perf inject -b -i - >/dev/null
Tue Aug 7 12:03:48 PDT 2018
[ perf record: Woken up 1 times to write data ]
[ perf record: Captured and wrote 0.000 MB - ]
Segmentation fault (core dumped):
(gdb) r inject -b -i - < tt >/dev/null
Program received signal SIGSEGV, Segmentation fault.
free_dup_event (oe=0x26a39a0, event=0xffffffff00000000) at util/ordered-events.c:85
(gdb) bt
#0 free_dup_event (oe=0x26a39a0, event=0xffffffff00000000) at util/ordered-events.c:85
#1 ordered_events__free (oe=0x26a39a0) at util/ordered-events.c:310
#2 0x00000000004b5a56 in __perf_session__process_pipe_events (session=<optimized out>) at util/session.c:1753
#3 perf_session__process_events (session=<optimized out>) at util/session.c:1932
#4 0x000000000043a2eb in __cmd_inject (inject=<optimized out>) at builtin-inject.c:750
#5 cmd_inject (argc=<optimized out>, argv=<optimized out>) at builtin-inject.c:924
#6 0x000000000046b175 in run_builtin (p=0xabc640 <commands+576>, argc=4, argv=0x7fffffffe560) at perf.c:297
#7 0x000000000046b062 in handle_internal_command (argc=4, argv=0x7fffffffe560) at perf.c:349
#8 0x000000000046a5e8 in run_argv (argcp=<optimized out>, argv=<optimized out>) at perf.c:393
#9 main (argc=4, argv=0x7fffffffe560) at perf.c:531
Signed-off-by: Stephane Eranian <eranian@google.com>
---
tools/perf/util/ordered-events.c | 6 ++++++
1 file changed, 6 insertions(+)
diff --git a/tools/perf/util/ordered-events.c b/tools/perf/util/ordered-events.c
index a90dbe5df019..95c91e5a3754 100644
--- a/tools/perf/util/ordered-events.c
+++ b/tools/perf/util/ordered-events.c
@@ -118,6 +118,12 @@ static struct ordered_event *alloc_event(struct ordered_events *oe,
pr("alloc size %" PRIu64 "B (+%zu), max %" PRIu64 "B\n",
oe->cur_alloc_size, size, oe->max_alloc_size);
+ /*
+ * must initialize event pointer of commandeered first
+ * entry to avoid crash in free_dup_event() due to random
+ * value for this field.
+ */
+ oe->buffer->event = NULL;
oe->cur_alloc_size += size;
list_add(&oe->buffer->list, &oe->to_free);
--
2.18.0.597.ga71716f1ad-goog
^ permalink raw reply related [flat|nested] 15+ messages in thread
* Re: [PATCH v2] perf ordered_events: fix crash in free_dup_event()
2018-08-08 22:33 [PATCH v2] perf ordered_events: fix crash in free_dup_event() Stephane Eranian
@ 2018-08-09 8:07 ` Jiri Olsa
2018-08-10 8:21 ` Stephane Eranian
0 siblings, 1 reply; 15+ messages in thread
From: Jiri Olsa @ 2018-08-09 8:07 UTC (permalink / raw)
To: Stephane Eranian; +Cc: linux-kernel, acme, peterz, mingo
On Wed, Aug 08, 2018 at 03:33:20PM -0700, Stephane Eranian wrote:
> This patch fixes a bug in ordered_event.c:alloc_event().
> An ordered_event struct was not initialized properly potentially
> causing crashes later on in free_dup_event() depending on the
> content of the memory. If it was NULL, then it would work fine,
> otherwise, it could cause crashes such as:
I'm now little puzzled what do we use this first event for..
I can't see anything special about it, other than it's added
on the list uninitialized ;-)
it seems to work properly when we ditch it.. might be some
prehistoric leftover or I'm terribly missing something
thanks,
jirka
---
diff --cc tools/perf/util/ordered-events.c
index bad9e0296e9a,0e837b0b8582..000000000000
--- a/tools/perf/util/ordered-events.c
+++ b/tools/perf/util/ordered-events.c
@@@ -119,12 -119,8 +119,9 @@@ static struct ordered_event *alloc_even
pr("alloc size %" PRIu64 "B (+%zu), max %" PRIu64 "B\n",
oe->cur_alloc_size, size, oe->max_alloc_size);
+ 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;
} else {
pr("allocation limit reached %" PRIu64 "B\n", oe->max_alloc_size);
}
^ permalink raw reply [flat|nested] 15+ messages in thread
* Re: [PATCH v2] perf ordered_events: fix crash in free_dup_event()
2018-08-09 8:07 ` Jiri Olsa
@ 2018-08-10 8:21 ` Stephane Eranian
2018-08-10 11:54 ` Jiri Olsa
0 siblings, 1 reply; 15+ messages in thread
From: Stephane Eranian @ 2018-08-10 8:21 UTC (permalink / raw)
To: Jiri Olsa; +Cc: LKML, Arnaldo Carvalho de Melo, Peter Zijlstra, mingo
On Thu, Aug 9, 2018 at 1:07 AM Jiri Olsa <jolsa@redhat.com> wrote:
>
> On Wed, Aug 08, 2018 at 03:33:20PM -0700, Stephane Eranian wrote:
> > This patch fixes a bug in ordered_event.c:alloc_event().
> > An ordered_event struct was not initialized properly potentially
> > causing crashes later on in free_dup_event() depending on the
> > content of the memory. If it was NULL, then it would work fine,
> > otherwise, it could cause crashes such as:
>
> I'm now little puzzled what do we use this first event for..
> I can't see anything special about it, other than it's added
> on the list uninitialized ;-)
>
> it seems to work properly when we ditch it.. might be some
> prehistoric leftover or I'm terribly missing something
>
You need to keep track of the buffers to free. You do not free the
ordered_event structs
individually. For each oe->buffer, you need one free(). Each buffer is
put in the to_free
list. But to link it into the list it needs a list_head. This is what
buffer[0] is used for.
But the logic is broken in ordered_events__free(). It does not free individual
ordered_event structs, but a buffer with many. Yet, it is missing
freeing all of the duped
events.
void ordered_events__free(struct ordered_events *oe)
{
while (!list_empty(&oe->to_free)) {
struct ordered_event *buffer;
buffer = list_entry(oe->to_free.next, struct
ordered_event, list);
list_del(&buffer->list);
----> free_dup_event(oe, event->event);
free(buffer);
}
}
This only frees the dup_event of buffer[0] which we know is NULL (well, now).
It needs to walk all the entries in buffer[] to free buffer[x].event.
I think the goal was likely to avoid adding another list_head field to
each ordered_event
and instead use one per allocated buffer.
This is very convoluted and prone to errors and we are seeing right
now. This should
be cleaned. So either you add a list_head to ordered_event or you
would buffer[x] in
ordered_events_free().
At this point, this is my understanding.
Do you agree?
>
> thanks,
> jirka
>
>
> ---
> diff --cc tools/perf/util/ordered-events.c
> index bad9e0296e9a,0e837b0b8582..000000000000
> --- a/tools/perf/util/ordered-events.c
> +++ b/tools/perf/util/ordered-events.c
> @@@ -119,12 -119,8 +119,9 @@@ static struct ordered_event *alloc_even
> pr("alloc size %" PRIu64 "B (+%zu), max %" PRIu64 "B\n",
> oe->cur_alloc_size, size, oe->max_alloc_size);
>
> + 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;
> } else {
> pr("allocation limit reached %" PRIu64 "B\n", oe->max_alloc_size);
> }
^ permalink raw reply [flat|nested] 15+ messages in thread
* Re: [PATCH v2] perf ordered_events: fix crash in free_dup_event()
2018-08-10 8:21 ` Stephane Eranian
@ 2018-08-10 11:54 ` Jiri Olsa
2018-08-13 13:04 ` [PATCH] perf tools: Add struct ordered_events_buffer layer Jiri Olsa
0 siblings, 1 reply; 15+ messages in thread
From: Jiri Olsa @ 2018-08-10 11:54 UTC (permalink / raw)
To: Stephane Eranian; +Cc: LKML, Arnaldo Carvalho de Melo, Peter Zijlstra, mingo
On Fri, Aug 10, 2018 at 01:21:18AM -0700, Stephane Eranian wrote:
> On Thu, Aug 9, 2018 at 1:07 AM Jiri Olsa <jolsa@redhat.com> wrote:
> >
> > On Wed, Aug 08, 2018 at 03:33:20PM -0700, Stephane Eranian wrote:
> > > This patch fixes a bug in ordered_event.c:alloc_event().
> > > An ordered_event struct was not initialized properly potentially
> > > causing crashes later on in free_dup_event() depending on the
> > > content of the memory. If it was NULL, then it would work fine,
> > > otherwise, it could cause crashes such as:
> >
> > I'm now little puzzled what do we use this first event for..
> > I can't see anything special about it, other than it's added
> > on the list uninitialized ;-)
> >
> > it seems to work properly when we ditch it.. might be some
> > prehistoric leftover or I'm terribly missing something
> >
> You need to keep track of the buffers to free. You do not free the
> ordered_event structs
> individually. For each oe->buffer, you need one free(). Each buffer is
> put in the to_free
> list. But to link it into the list it needs a list_head. This is what
> buffer[0] is used for.
> But the logic is broken in ordered_events__free(). It does not free individual
> ordered_event structs, but a buffer with many. Yet, it is missing
> freeing all of the duped
> events.
>
> void ordered_events__free(struct ordered_events *oe)
> {
> while (!list_empty(&oe->to_free)) {
> struct ordered_event *buffer;
>
> buffer = list_entry(oe->to_free.next, struct
> ordered_event, list);
> list_del(&buffer->list);
> ----> free_dup_event(oe, event->event);
> free(buffer);
> }
> }
> This only frees the dup_event of buffer[0] which we know is NULL (well, now).
> It needs to walk all the entries in buffer[] to free buffer[x].event.
yes.. if there's copy_on_queue set, we need to do that,
otherwise we're leaking all the events
>
> I think the goal was likely to avoid adding another list_head field to
> each ordered_event
> and instead use one per allocated buffer.
> This is very convoluted and prone to errors and we are seeing right
> now. This should
> be cleaned. So either you add a list_head to ordered_event or you
> would buffer[x] in
> ordered_events_free().
>
> At this point, this is my understanding.
> Do you agree?
yea, I see it now.. thanks for pointing this out
how about something like below? haven't tested properly yet
jirka
---
diff --git a/tools/perf/util/ordered-events.c b/tools/perf/util/ordered-events.c
index bad9e0296e9a..5c0d85e90a18 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)
@@ -104,11 +110,11 @@ 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 +128,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);
}
@@ -300,15 +305,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);
+ }
+
+ 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);
+ list_for_each_entry_safe(buffer, tmp, &oe->to_free, list) {
+ list_del(&buffer->list);
+ ordered_events_buffer__free(buffer, oe);
}
}
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,
^ permalink raw reply related [flat|nested] 15+ messages in thread
* [PATCH] perf tools: Add struct ordered_events_buffer layer
2018-08-10 11:54 ` Jiri Olsa
@ 2018-08-13 13:04 ` Jiri Olsa
2018-08-14 7:14 ` Stephane Eranian
0 siblings, 1 reply; 15+ messages in thread
From: Jiri Olsa @ 2018-08-13 13:04 UTC (permalink / raw)
To: Stephane Eranian; +Cc: LKML, Arnaldo Carvalho de Melo, Peter Zijlstra, mingo
On Fri, Aug 10, 2018 at 01:54:31PM +0200, Jiri Olsa wrote:
> On Fri, Aug 10, 2018 at 01:21:18AM -0700, Stephane Eranian wrote:
> > On Thu, Aug 9, 2018 at 1:07 AM Jiri Olsa <jolsa@redhat.com> wrote:
> > >
> > > On Wed, Aug 08, 2018 at 03:33:20PM -0700, Stephane Eranian wrote:
> > > > This patch fixes a bug in ordered_event.c:alloc_event().
> > > > An ordered_event struct was not initialized properly potentially
> > > > causing crashes later on in free_dup_event() depending on the
> > > > content of the memory. If it was NULL, then it would work fine,
> > > > otherwise, it could cause crashes such as:
> > >
> > > I'm now little puzzled what do we use this first event for..
> > > I can't see anything special about it, other than it's added
> > > on the list uninitialized ;-)
> > >
> > > it seems to work properly when we ditch it.. might be some
> > > prehistoric leftover or I'm terribly missing something
> > >
> > You need to keep track of the buffers to free. You do not free the
> > ordered_event structs
> > individually. For each oe->buffer, you need one free(). Each buffer is
> > put in the to_free
> > list. But to link it into the list it needs a list_head. This is what
> > buffer[0] is used for.
> > But the logic is broken in ordered_events__free(). It does not free individual
> > ordered_event structs, but a buffer with many. Yet, it is missing
> > freeing all of the duped
> > events.
> >
> > void ordered_events__free(struct ordered_events *oe)
> > {
> > while (!list_empty(&oe->to_free)) {
> > struct ordered_event *buffer;
> >
> > buffer = list_entry(oe->to_free.next, struct
> > ordered_event, list);
> > list_del(&buffer->list);
> > ----> free_dup_event(oe, event->event);
> > free(buffer);
> > }
> > }
> > This only frees the dup_event of buffer[0] which we know is NULL (well, now).
> > It needs to walk all the entries in buffer[] to free buffer[x].event.
>
> yes.. if there's copy_on_queue set, we need to do that,
> otherwise we're leaking all the events
>
> >
> > I think the goal was likely to avoid adding another list_head field to
> > each ordered_event
> > and instead use one per allocated buffer.
> > This is very convoluted and prone to errors and we are seeing right
> > now. This should
> > be cleaned. So either you add a list_head to ordered_event or you
> > would buffer[x] in
> > ordered_events_free().
> >
> > At this point, this is my understanding.
> > Do you agree?
>
> yea, I see it now.. thanks for pointing this out
>
> how about something like below? haven't tested properly yet
attaching full patch
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 | 44 ++++++++++++++++++++++----------
tools/perf/util/ordered-events.h | 37 +++++++++++++++------------
2 files changed, 52 insertions(+), 29 deletions(-)
diff --git a/tools/perf/util/ordered-events.c b/tools/perf/util/ordered-events.c
index bad9e0296e9a..038515a52e2c 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)
@@ -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];
} 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);
+ }
+
+ 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);
+ list_for_each_entry_safe(buffer, tmp, &oe->to_free, list) {
+ list_del(&buffer->list);
+ ordered_events_buffer__free(buffer, oe);
}
}
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
^ permalink raw reply related [flat|nested] 15+ messages in thread
* Re: [PATCH] perf tools: Add struct ordered_events_buffer layer
2018-08-13 13:04 ` [PATCH] perf tools: Add struct ordered_events_buffer layer Jiri Olsa
@ 2018-08-14 7:14 ` Stephane Eranian
2018-08-15 8:48 ` Jiri Olsa
0 siblings, 1 reply; 15+ messages in thread
From: Stephane Eranian @ 2018-08-14 7:14 UTC (permalink / raw)
To: Jiri Olsa; +Cc: LKML, Arnaldo Carvalho de Melo, Peter Zijlstra, mingo
Jiri,
On Mon, Aug 13, 2018 at 6:04 AM Jiri Olsa <jolsa@redhat.com> wrote:
>
> On Fri, Aug 10, 2018 at 01:54:31PM +0200, Jiri Olsa wrote:
> > On Fri, Aug 10, 2018 at 01:21:18AM -0700, Stephane Eranian wrote:
> > > On Thu, Aug 9, 2018 at 1:07 AM Jiri Olsa <jolsa@redhat.com> wrote:
> > > >
> > > > On Wed, Aug 08, 2018 at 03:33:20PM -0700, Stephane Eranian wrote:
> > > > > This patch fixes a bug in ordered_event.c:alloc_event().
> > > > > An ordered_event struct was not initialized properly potentially
> > > > > causing crashes later on in free_dup_event() depending on the
> > > > > content of the memory. If it was NULL, then it would work fine,
> > > > > otherwise, it could cause crashes such as:
> > > >
> > > > I'm now little puzzled what do we use this first event for..
> > > > I can't see anything special about it, other than it's added
> > > > on the list uninitialized ;-)
> > > >
> > > > it seems to work properly when we ditch it.. might be some
> > > > prehistoric leftover or I'm terribly missing something
> > > >
> > > You need to keep track of the buffers to free. You do not free the
> > > ordered_event structs
> > > individually. For each oe->buffer, you need one free(). Each buffer is
> > > put in the to_free
> > > list. But to link it into the list it needs a list_head. This is what
> > > buffer[0] is used for.
> > > But the logic is broken in ordered_events__free(). It does not free individual
> > > ordered_event structs, but a buffer with many. Yet, it is missing
> > > freeing all of the duped
> > > events.
> > >
> > > void ordered_events__free(struct ordered_events *oe)
> > > {
> > > while (!list_empty(&oe->to_free)) {
> > > struct ordered_event *buffer;
> > >
> > > buffer = list_entry(oe->to_free.next, struct
> > > ordered_event, list);
> > > list_del(&buffer->list);
> > > ----> free_dup_event(oe, event->event);
> > > free(buffer);
> > > }
> > > }
> > > This only frees the dup_event of buffer[0] which we know is NULL (well, now).
> > > It needs to walk all the entries in buffer[] to free buffer[x].event.
> >
> > yes.. if there's copy_on_queue set, we need to do that,
> > otherwise we're leaking all the events
> >
> > >
> > > I think the goal was likely to avoid adding another list_head field to
> > > each ordered_event
> > > and instead use one per allocated buffer.
> > > This is very convoluted and prone to errors and we are seeing right
> > > now. This should
> > > be cleaned. So either you add a list_head to ordered_event or you
> > > would buffer[x] in
> > > ordered_events_free().
> > >
> > > At this point, this is my understanding.
> > > Do you agree?
> >
> > yea, I see it now.. thanks for pointing this out
> >
> > how about something like below? haven't tested properly yet
>
> attaching full patch
>
> 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 | 44 ++++++++++++++++++++++----------
> tools/perf/util/ordered-events.h | 37 +++++++++++++++------------
> 2 files changed, 52 insertions(+), 29 deletions(-)
>
> diff --git a/tools/perf/util/ordered-events.c b/tools/perf/util/ordered-events.c
> index bad9e0296e9a..038515a52e2c 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)
> @@ -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.
> } 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.
> + 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);
> + list_for_each_entry_safe(buffer, tmp, &oe->to_free, list) {
> + list_del(&buffer->list);
> + ordered_events_buffer__free(buffer, oe);
> }
> }
>
> 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
>
^ permalink raw reply [flat|nested] 15+ messages in thread
* Re: [PATCH] perf tools: Add struct ordered_events_buffer layer
2018-08-14 7:14 ` Stephane Eranian
@ 2018-08-15 8:48 ` Jiri Olsa
2018-08-27 9:28 ` [PATCHv2] " Jiri Olsa
0 siblings, 1 reply; 15+ messages in thread
From: Jiri Olsa @ 2018-08-15 8:48 UTC (permalink / raw)
To: Stephane Eranian; +Cc: LKML, Arnaldo Carvalho de Melo, Peter Zijlstra, mingo
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
thanks,
jirka
---
diff --git a/tools/perf/util/ordered-events.c b/tools/perf/util/ordered-events.c
index bad9e0296e9a..7a9707301f17 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);
}
@@ -300,15 +333,35 @@ 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);
+ /*
+ * 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);
}
}
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,
^ permalink raw reply related [flat|nested] 15+ messages in thread
* [PATCHv2] perf tools: Add struct ordered_events_buffer layer
2018-08-15 8:48 ` Jiri Olsa
@ 2018-08-27 9:28 ` Jiri Olsa
2018-08-27 11:07 ` Namhyung Kim
2018-08-27 15:24 ` Stephane Eranian
0 siblings, 2 replies; 15+ messages in thread
From: Jiri Olsa @ 2018-08-27 9:28 UTC (permalink / raw)
To: Stephane Eranian
Cc: LKML, Arnaldo Carvalho de Melo, Peter Zijlstra, mingo, Namhyung Kim
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);
}
@@ -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);
}
}
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
^ permalink raw reply related [flat|nested] 15+ messages in thread
* Re: [PATCHv2] perf tools: Add struct ordered_events_buffer layer
2018-08-27 9:28 ` [PATCHv2] " Jiri Olsa
@ 2018-08-27 11:07 ` Namhyung Kim
2018-08-27 15:24 ` Stephane Eranian
1 sibling, 0 replies; 15+ messages in thread
From: Namhyung Kim @ 2018-08-27 11:07 UTC (permalink / raw)
To: Jiri Olsa
Cc: Stephane Eranian, LKML, Arnaldo Carvalho de Melo, Peter Zijlstra,
mingo, kernel-team
On Mon, Aug 27, 2018 at 11:28:18AM +0200, Jiri Olsa wrote:
> 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>
Acked-by: Namhyung Kim <namhyung@kernel.org>
Thanks,
Namhyung
> ---
> 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);
> }
> @@ -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);
> }
> }
>
> 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
>
^ permalink raw reply [flat|nested] 15+ messages in thread
* Re: [PATCHv2] perf tools: Add struct ordered_events_buffer layer
2018-08-27 9:28 ` [PATCHv2] " Jiri Olsa
2018-08-27 11:07 ` Namhyung Kim
@ 2018-08-27 15:24 ` Stephane Eranian
2018-08-27 17:05 ` [PATCHv3] " Jiri Olsa
1 sibling, 1 reply; 15+ messages in thread
From: Stephane Eranian @ 2018-08-27 15:24 UTC (permalink / raw)
To: Jiri Olsa
Cc: LKML, Arnaldo Carvalho de Melo, Peter Zijlstra, mingo, Namhyung Kim
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
>
^ permalink raw reply [flat|nested] 15+ messages in thread
* [PATCHv3] perf tools: Add struct ordered_events_buffer layer
2018-08-27 15:24 ` Stephane Eranian
@ 2018-08-27 17:05 ` Jiri Olsa
2018-09-02 14:47 ` Jiri Olsa
0 siblings, 1 reply; 15+ messages in thread
From: Jiri Olsa @ 2018-08-27 17:05 UTC (permalink / raw)
To: Stephane Eranian
Cc: LKML, Arnaldo Carvalho de Melo, Peter Zijlstra, mingo, Namhyung Kim
On Mon, Aug 27, 2018 at 08:24:56AM -0700, Stephane Eranian wrote:
SNIP
> > - /* 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.
yep, that's a bug.. with new being NULL in here,
we'd get a crash anyway.. so 'return NULL;' it is
SNIP
> > + * 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?
yes, at this point they either holds an event or NULL
so it's free to call __free_dup_event on it
thanks, v3 attached
added also Namhyung's ack, as the 'return NULL' change wasn't
related to the v2 changes
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>
Acked-by: Namhyung Kim <namhyung@kernel.org>
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 | 83 +++++++++++++++++++++++++++-----
tools/perf/util/ordered-events.h | 37 ++++++++------
2 files changed, 91 insertions(+), 29 deletions(-)
diff --git a/tools/perf/util/ordered-events.c b/tools/perf/util/ordered-events.c
index bad9e0296e9a..87171e8fd70d 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,11 +156,11 @@ 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);
+ return NULL;
}
new->event = new_event;
@@ -300,15 +334,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);
}
}
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
^ permalink raw reply related [flat|nested] 15+ messages in thread
* Re: [PATCHv3] perf tools: Add struct ordered_events_buffer layer
2018-08-27 17:05 ` [PATCHv3] " Jiri Olsa
@ 2018-09-02 14:47 ` Jiri Olsa
2018-09-04 2:37 ` Stephane Eranian
0 siblings, 1 reply; 15+ messages in thread
From: Jiri Olsa @ 2018-09-02 14:47 UTC (permalink / raw)
To: Stephane Eranian
Cc: LKML, Arnaldo Carvalho de Melo, Peter Zijlstra, mingo, Namhyung Kim
On Mon, Aug 27, 2018 at 07:05:43PM +0200, Jiri Olsa wrote:
> On Mon, Aug 27, 2018 at 08:24:56AM -0700, Stephane Eranian wrote:
>
> SNIP
>
> > > - /* 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.
>
> yep, that's a bug.. with new being NULL in here,
> we'd get a crash anyway.. so 'return NULL;' it is
>
> SNIP
>
> > > + * 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?
>
> yes, at this point they either holds an event or NULL
> so it's free to call __free_dup_event on it
>
> thanks, v3 attached
>
> added also Namhyung's ack, as the 'return NULL' change wasn't
> related to the v2 changes
>
> jirka
Stephane,
any comments to v3 version?
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>
> Acked-by: Namhyung Kim <namhyung@kernel.org>
> 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 | 83 +++++++++++++++++++++++++++-----
> tools/perf/util/ordered-events.h | 37 ++++++++------
> 2 files changed, 91 insertions(+), 29 deletions(-)
>
> diff --git a/tools/perf/util/ordered-events.c b/tools/perf/util/ordered-events.c
> index bad9e0296e9a..87171e8fd70d 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,11 +156,11 @@ 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);
> + return NULL;
> }
>
> new->event = new_event;
> @@ -300,15 +334,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);
> }
> }
>
> 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
^ permalink raw reply [flat|nested] 15+ messages in thread
* Re: [PATCHv3] perf tools: Add struct ordered_events_buffer layer
2018-09-02 14:47 ` Jiri Olsa
@ 2018-09-04 2:37 ` Stephane Eranian
2018-09-06 13:28 ` Jiri Olsa
0 siblings, 1 reply; 15+ messages in thread
From: Stephane Eranian @ 2018-09-04 2:37 UTC (permalink / raw)
To: Jiri Olsa
Cc: LKML, Arnaldo Carvalho de Melo, Peter Zijlstra, mingo, Namhyung Kim
Jiri,
On Sun, Sep 2, 2018 at 7:47 AM Jiri Olsa <jolsa@redhat.com> wrote:
>
> On Mon, Aug 27, 2018 at 07:05:43PM +0200, Jiri Olsa wrote:
> > On Mon, Aug 27, 2018 at 08:24:56AM -0700, Stephane Eranian wrote:
> >
> > SNIP
> >
> > > > - /* 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.
> >
> > yep, that's a bug.. with new being NULL in here,
> > we'd get a crash anyway.. so 'return NULL;' it is
> >
> > SNIP
> >
> > > > + * 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?
> >
> > yes, at this point they either holds an event or NULL
> > so it's free to call __free_dup_event on it
> >
> > thanks, v3 attached
> >
> > added also Namhyung's ack, as the 'return NULL' change wasn't
> > related to the v2 changes
> >
I think the code is correct now for the issue related to uninitialized pointer.
But there is still one problem I found stressing the code with max_alloc_size.
The way the following is written:
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;
if (++oe->buffer_idx == MAX_SAMPLE_BUFFER)
oe->buffer = NULL;
} else if (oe->cur_alloc_size < oe->max_alloc_size) {
size_t size = sizeof(*oe->buffer) MAX_SAMPLE_BUFFER *
sizeof(*new);
oe->buffer = malloc(size);
if (!oe->buffer) {
free_dup_event(oe, new_event);
return NULL;
}
pr("alloc size %" PRIu64 "B (+%zu), max %" PRIu64 "B\n",
oe->cur_alloc_size, size, oe->max_alloc_size);
oe->cur_alloc_size += size;
You can end up with oe->cur_alloc_size > oe->max_alloc_size in case
the max limit is
really low (< size_t size = sizeof (*oe->buffer) + MAX_SAMPLE_BUFFER *
sizeof(*new);
So I think to make sure you can never allocate more than the max, you
have to do:
size_t size = sizeof(*oe->buffer) MAX_SAMPLE_BUFFER * sizeof(*new);
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;
if (++oe->buffer_idx == MAX_SAMPLE_BUFFER)
oe->buffer = NULL;
} else if ((oe->cur_alloc_size + size) < oe->max_alloc_size) {
Then you will never allocate more than the max.
I think with this change, we are okay.
Tested-by: Stephane Eranian <eranian@google.com>
> jirka
>
> Stephane,
> any comments to v3 version?
>
> 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>
> > Acked-by: Namhyung Kim <namhyung@kernel.org>
> > 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 | 83 +++++++++++++++++++++++++++-----
> > tools/perf/util/ordered-events.h | 37 ++++++++------
> > 2 files changed, 91 insertions(+), 29 deletions(-)
> >
> > diff --git a/tools/perf/util/ordered-events.c b/tools/perf/util/ordered-events.c
> > index bad9e0296e9a..87171e8fd70d 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,11 +156,11 @@ 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);
> > + return NULL;
> > }
> >
> > new->event = new_event;
> > @@ -300,15 +334,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);
> > }
> > }
> >
> > 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
^ permalink raw reply [flat|nested] 15+ messages in thread
* Re: [PATCHv3] perf tools: Add struct ordered_events_buffer layer
2018-09-04 2:37 ` Stephane Eranian
@ 2018-09-06 13:28 ` Jiri Olsa
2018-09-06 15:04 ` Stephane Eranian
0 siblings, 1 reply; 15+ messages in thread
From: Jiri Olsa @ 2018-09-06 13:28 UTC (permalink / raw)
To: Stephane Eranian
Cc: LKML, Arnaldo Carvalho de Melo, Peter Zijlstra, mingo, Namhyung Kim
On Mon, Sep 03, 2018 at 07:37:56PM -0700, Stephane Eranian wrote:
SNIP
>
> I think the code is correct now for the issue related to uninitialized pointer.
> But there is still one problem I found stressing the code with max_alloc_size.
> The way the following is written:
>
> 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;
> if (++oe->buffer_idx == MAX_SAMPLE_BUFFER)
> oe->buffer = NULL;
> } else if (oe->cur_alloc_size < oe->max_alloc_size) {
> size_t size = sizeof(*oe->buffer) MAX_SAMPLE_BUFFER *
> sizeof(*new);
>
> oe->buffer = malloc(size);
> if (!oe->buffer) {
> free_dup_event(oe, new_event);
> return NULL;
> }
>
> pr("alloc size %" PRIu64 "B (+%zu), max %" PRIu64 "B\n",
> oe->cur_alloc_size, size, oe->max_alloc_size);
>
> oe->cur_alloc_size += size;
>
> You can end up with oe->cur_alloc_size > oe->max_alloc_size in case
> the max limit is
> really low (< size_t size = sizeof (*oe->buffer) + MAX_SAMPLE_BUFFER *
> sizeof(*new);
> So I think to make sure you can never allocate more than the max, you
> have to do:
>
> size_t size = sizeof(*oe->buffer) MAX_SAMPLE_BUFFER * sizeof(*new);
> 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;
> if (++oe->buffer_idx == MAX_SAMPLE_BUFFER)
> oe->buffer = NULL;
> } else if ((oe->cur_alloc_size + size) < oe->max_alloc_size) {
>
> Then you will never allocate more than the max.
> I think with this change, we are okay.
> Tested-by: Stephane Eranian <eranian@google.com>
yep, makes sense.. something like below then
I'll post it on top of the previous patch
thanks,
jirka
---
diff --git a/tools/perf/util/ordered-events.c b/tools/perf/util/ordered-events.c
index 87171e8fd70d..2d1d0f3c8f77 100644
--- a/tools/perf/util/ordered-events.c
+++ b/tools/perf/util/ordered-events.c
@@ -101,6 +101,7 @@ static struct ordered_event *alloc_event(struct ordered_events *oe,
struct list_head *cache = &oe->cache;
struct ordered_event *new = NULL;
union perf_event *new_event;
+ size_t size;
new_event = dup_event(oe, event);
if (!new_event)
@@ -133,6 +134,8 @@ static struct ordered_event *alloc_event(struct ordered_events *oe,
* Removal of ordered event object moves it from events to
* the cache list.
*/
+ size = sizeof(*oe->buffer) + MAX_SAMPLE_BUFFER * sizeof(*new);
+
if (!list_empty(cache)) {
new = list_entry(cache->next, struct ordered_event, list);
list_del(&new->list);
@@ -140,10 +143,7 @@ static struct ordered_event *alloc_event(struct ordered_events *oe,
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 = sizeof(*oe->buffer) +
- MAX_SAMPLE_BUFFER * sizeof(*new);
-
+ } else if ((oe->cur_alloc_size + size) < oe->max_alloc_size) {
oe->buffer = malloc(size);
if (!oe->buffer) {
free_dup_event(oe, new_event);
^ permalink raw reply related [flat|nested] 15+ messages in thread
* Re: [PATCHv3] perf tools: Add struct ordered_events_buffer layer
2018-09-06 13:28 ` Jiri Olsa
@ 2018-09-06 15:04 ` Stephane Eranian
0 siblings, 0 replies; 15+ messages in thread
From: Stephane Eranian @ 2018-09-06 15:04 UTC (permalink / raw)
To: Jiri Olsa
Cc: LKML, Arnaldo Carvalho de Melo, Peter Zijlstra, mingo, Namhyung Kim
On Thu, Sep 6, 2018 at 6:29 AM Jiri Olsa <jolsa@redhat.com> wrote:
>
> On Mon, Sep 03, 2018 at 07:37:56PM -0700, Stephane Eranian wrote:
>
> SNIP
>
> >
> > I think the code is correct now for the issue related to uninitialized pointer.
> > But there is still one problem I found stressing the code with max_alloc_size.
> > The way the following is written:
> >
> > 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;
> > if (++oe->buffer_idx == MAX_SAMPLE_BUFFER)
> > oe->buffer = NULL;
> > } else if (oe->cur_alloc_size < oe->max_alloc_size) {
> > size_t size = sizeof(*oe->buffer) MAX_SAMPLE_BUFFER *
> > sizeof(*new);
> >
> > oe->buffer = malloc(size);
> > if (!oe->buffer) {
> > free_dup_event(oe, new_event);
> > return NULL;
> > }
> >
> > pr("alloc size %" PRIu64 "B (+%zu), max %" PRIu64 "B\n",
> > oe->cur_alloc_size, size, oe->max_alloc_size);
> >
> > oe->cur_alloc_size += size;
> >
> > You can end up with oe->cur_alloc_size > oe->max_alloc_size in case
> > the max limit is
> > really low (< size_t size = sizeof (*oe->buffer) + MAX_SAMPLE_BUFFER *
> > sizeof(*new);
> > So I think to make sure you can never allocate more than the max, you
> > have to do:
> >
> > size_t size = sizeof(*oe->buffer) MAX_SAMPLE_BUFFER * sizeof(*new);
> > 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;
> > if (++oe->buffer_idx == MAX_SAMPLE_BUFFER)
> > oe->buffer = NULL;
> > } else if ((oe->cur_alloc_size + size) < oe->max_alloc_size) {
> >
> > Then you will never allocate more than the max.
> > I think with this change, we are okay.
> > Tested-by: Stephane Eranian <eranian@google.com>
>
> yep, makes sense.. something like below then
> I'll post it on top of the previous patch
>
Yes. This works.
Thanks.
> thanks,
> jirka
>
>
> ---
> diff --git a/tools/perf/util/ordered-events.c b/tools/perf/util/ordered-events.c
> index 87171e8fd70d..2d1d0f3c8f77 100644
> --- a/tools/perf/util/ordered-events.c
> +++ b/tools/perf/util/ordered-events.c
> @@ -101,6 +101,7 @@ static struct ordered_event *alloc_event(struct ordered_events *oe,
> struct list_head *cache = &oe->cache;
> struct ordered_event *new = NULL;
> union perf_event *new_event;
> + size_t size;
>
> new_event = dup_event(oe, event);
> if (!new_event)
> @@ -133,6 +134,8 @@ static struct ordered_event *alloc_event(struct ordered_events *oe,
> * Removal of ordered event object moves it from events to
> * the cache list.
> */
> + size = sizeof(*oe->buffer) + MAX_SAMPLE_BUFFER * sizeof(*new);
> +
> if (!list_empty(cache)) {
> new = list_entry(cache->next, struct ordered_event, list);
> list_del(&new->list);
> @@ -140,10 +143,7 @@ static struct ordered_event *alloc_event(struct ordered_events *oe,
> 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 = sizeof(*oe->buffer) +
> - MAX_SAMPLE_BUFFER * sizeof(*new);
> -
> + } else if ((oe->cur_alloc_size + size) < oe->max_alloc_size) {
> oe->buffer = malloc(size);
> if (!oe->buffer) {
> free_dup_event(oe, new_event);
^ permalink raw reply [flat|nested] 15+ messages in thread
end of thread, other threads:[~2018-09-06 15:03 UTC | newest]
Thread overview: 15+ messages (download: mbox.gz / follow: Atom feed)
-- links below jump to the message on this page --
2018-08-08 22:33 [PATCH v2] perf ordered_events: fix crash in free_dup_event() Stephane Eranian
2018-08-09 8:07 ` Jiri Olsa
2018-08-10 8:21 ` Stephane Eranian
2018-08-10 11:54 ` Jiri Olsa
2018-08-13 13:04 ` [PATCH] perf tools: Add struct ordered_events_buffer layer Jiri Olsa
2018-08-14 7:14 ` Stephane Eranian
2018-08-15 8:48 ` Jiri Olsa
2018-08-27 9:28 ` [PATCHv2] " Jiri Olsa
2018-08-27 11:07 ` Namhyung Kim
2018-08-27 15:24 ` Stephane Eranian
2018-08-27 17:05 ` [PATCHv3] " Jiri Olsa
2018-09-02 14:47 ` Jiri Olsa
2018-09-04 2:37 ` Stephane Eranian
2018-09-06 13:28 ` Jiri Olsa
2018-09-06 15:04 ` Stephane Eranian
This is a public inbox, see mirroring instructions
for how to clone and mirror all data and code used for this inbox;
as well as URLs for NNTP newsgroup(s).