* [PATCH 0/2] tools lib traceevent: Fixes for adding tasks to the tep descriptor @ 2019-08-28 19:05 Steven Rostedt 2019-08-28 19:05 ` [PATCH 1/2] tools lib traceevent: Do not free tep->cmdlines in add_new_comm() on failure Steven Rostedt 2019-08-28 19:05 ` [PATCH 2/2] tools lib traceevent: Remove unneeded qsort and uses memmove instead Steven Rostedt 0 siblings, 2 replies; 5+ messages in thread From: Steven Rostedt @ 2019-08-28 19:05 UTC (permalink / raw) To: linux-kernel, linux-trace-devel Cc: Arnaldo Carvalho de Melo, Ingo Molnar, Jiri Olsa, Namhyung Kim, Andrew Morton Hi Arnaldo, Please pull in these patches as they fix the lib tools traceevent code that has issues with adding in new tasks on large data files. -- Steve Steven Rostedt (VMware) (2): tools lib traceevent: Do not free tep->cmdlines in add_new_comm() on failure tools lib traceevent: Remove unneeded qsort and uses memmove instead ---- tools/lib/traceevent/event-parse.c | 58 ++++++++++++++++++++++++++++++++------ 1 file changed, 50 insertions(+), 8 deletions(-) ^ permalink raw reply [flat|nested] 5+ messages in thread
* [PATCH 1/2] tools lib traceevent: Do not free tep->cmdlines in add_new_comm() on failure 2019-08-28 19:05 [PATCH 0/2] tools lib traceevent: Fixes for adding tasks to the tep descriptor Steven Rostedt @ 2019-08-28 19:05 ` Steven Rostedt 2019-08-29 19:02 ` [tip: perf/core] " tip-bot2 for Steven Rostedt (VMware) 2019-08-28 19:05 ` [PATCH 2/2] tools lib traceevent: Remove unneeded qsort and uses memmove instead Steven Rostedt 1 sibling, 1 reply; 5+ messages in thread From: Steven Rostedt @ 2019-08-28 19:05 UTC (permalink / raw) To: linux-kernel, linux-trace-devel Cc: Arnaldo Carvalho de Melo, Ingo Molnar, Jiri Olsa, Namhyung Kim, Andrew Morton, stable From: "Steven Rostedt (VMware)" <rostedt@goodmis.org> If the re-allocation of tep->cmdlines succeeds, then the previous allocation of tep->cmdlines will be freed. If we later fail in add_new_comm(), we must not free cmdlines, and also should assign tep->cmdlines to the new allocation. Otherwise when freeing tep, the tep->cmdlines will be pointing to garbage. Cc: stable@vger.kernel.org Fixes: a6d2a61ac653a ("tools lib traceevent: Remove some die() calls") Signed-off-by: Steven Rostedt (VMware) <rostedt@goodmis.org> --- tools/lib/traceevent/event-parse.c | 3 +-- 1 file changed, 1 insertion(+), 2 deletions(-) diff --git a/tools/lib/traceevent/event-parse.c b/tools/lib/traceevent/event-parse.c index b36b536a9fcb..13fd9fdf91e0 100644 --- a/tools/lib/traceevent/event-parse.c +++ b/tools/lib/traceevent/event-parse.c @@ -269,10 +269,10 @@ static int add_new_comm(struct tep_handle *tep, errno = ENOMEM; return -1; } + tep->cmdlines = cmdlines; cmdlines[tep->cmdline_count].comm = strdup(comm); if (!cmdlines[tep->cmdline_count].comm) { - free(cmdlines); errno = ENOMEM; return -1; } @@ -283,7 +283,6 @@ static int add_new_comm(struct tep_handle *tep, tep->cmdline_count++; qsort(cmdlines, tep->cmdline_count, sizeof(*cmdlines), cmdline_cmp); - tep->cmdlines = cmdlines; return 0; } -- 2.20.1 ^ permalink raw reply related [flat|nested] 5+ messages in thread
* [tip: perf/core] tools lib traceevent: Do not free tep->cmdlines in add_new_comm() on failure 2019-08-28 19:05 ` [PATCH 1/2] tools lib traceevent: Do not free tep->cmdlines in add_new_comm() on failure Steven Rostedt @ 2019-08-29 19:02 ` tip-bot2 for Steven Rostedt (VMware) 0 siblings, 0 replies; 5+ messages in thread From: tip-bot2 for Steven Rostedt (VMware) @ 2019-08-29 19:02 UTC (permalink / raw) To: linux-tip-commits Cc: Steven Rostedt (VMware), Andrew Morton, Jiri Olsa, Namhyung Kim, linux-trace-devel, stable, Arnaldo Carvalho de Melo, Ingo Molnar, Borislav Petkov, linux-kernel The following commit has been merged into the perf/core branch of tip: Commit-ID: b0215e2d6a18d8331b2d4a8b38ccf3eff783edb1 Gitweb: https://git.kernel.org/tip/b0215e2d6a18d8331b2d4a8b38ccf3eff783edb1 Author: Steven Rostedt (VMware) <rostedt@goodmis.org> AuthorDate: Wed, 28 Aug 2019 15:05:28 -04:00 Committer: Arnaldo Carvalho de Melo <acme@redhat.com> CommitterDate: Thu, 29 Aug 2019 08:36:12 -03:00 tools lib traceevent: Do not free tep->cmdlines in add_new_comm() on failure If the re-allocation of tep->cmdlines succeeds, then the previous allocation of tep->cmdlines will be freed. If we later fail in add_new_comm(), we must not free cmdlines, and also should assign tep->cmdlines to the new allocation. Otherwise when freeing tep, the tep->cmdlines will be pointing to garbage. Fixes: a6d2a61ac653a ("tools lib traceevent: Remove some die() calls") Signed-off-by: Steven Rostedt (VMware) <rostedt@goodmis.org> Cc: Andrew Morton <akpm@linux-foundation.org> Cc: Jiri Olsa <jolsa@redhat.com> Cc: Namhyung Kim <namhyung@kernel.org> Cc: linux-trace-devel@vger.kernel.org Cc: stable@vger.kernel.org Link: http://lkml.kernel.org/r/20190828191819.970121417@goodmis.org Signed-off-by: Arnaldo Carvalho de Melo <acme@redhat.com> --- tools/lib/traceevent/event-parse.c | 3 +-- 1 file changed, 1 insertion(+), 2 deletions(-) diff --git a/tools/lib/traceevent/event-parse.c b/tools/lib/traceevent/event-parse.c index b36b536..13fd9fd 100644 --- a/tools/lib/traceevent/event-parse.c +++ b/tools/lib/traceevent/event-parse.c @@ -269,10 +269,10 @@ static int add_new_comm(struct tep_handle *tep, errno = ENOMEM; return -1; } + tep->cmdlines = cmdlines; cmdlines[tep->cmdline_count].comm = strdup(comm); if (!cmdlines[tep->cmdline_count].comm) { - free(cmdlines); errno = ENOMEM; return -1; } @@ -283,7 +283,6 @@ static int add_new_comm(struct tep_handle *tep, tep->cmdline_count++; qsort(cmdlines, tep->cmdline_count, sizeof(*cmdlines), cmdline_cmp); - tep->cmdlines = cmdlines; return 0; } ^ permalink raw reply related [flat|nested] 5+ messages in thread
* [PATCH 2/2] tools lib traceevent: Remove unneeded qsort and uses memmove instead 2019-08-28 19:05 [PATCH 0/2] tools lib traceevent: Fixes for adding tasks to the tep descriptor Steven Rostedt 2019-08-28 19:05 ` [PATCH 1/2] tools lib traceevent: Do not free tep->cmdlines in add_new_comm() on failure Steven Rostedt @ 2019-08-28 19:05 ` Steven Rostedt 2019-08-29 19:02 ` [tip: perf/core] " tip-bot2 for Steven Rostedt (VMware) 1 sibling, 1 reply; 5+ messages in thread From: Steven Rostedt @ 2019-08-28 19:05 UTC (permalink / raw) To: linux-kernel, linux-trace-devel Cc: Arnaldo Carvalho de Melo, Ingo Molnar, Jiri Olsa, Namhyung Kim, Andrew Morton From: "Steven Rostedt (VMware)" <rostedt@goodmis.org> While reading a trace data file that had 100,000s of tasks, the process took an extremely long time. I profiled it down to add_new_comm(), which was doing a qsort() call on an array that was pretty much already sorted (all but the last element. qsort() isn't very efficient when dealing with mostly sorted arrays, and this definitely showed its issues. When adding a new task to the task list, instead of using qsort(), do another bsearch() with a function that will find the element before where the new task will be inserted in. Then simply shift the rest of the array, and insert the task where it belongs. Fixes: f7d82350e597d ("tools/events: Add files to create libtraceevent.a") Signed-off-by: Steven Rostedt (VMware) <rostedt@goodmis.org> --- tools/lib/traceevent/event-parse.c | 55 ++++++++++++++++++++++++++---- 1 file changed, 49 insertions(+), 6 deletions(-) diff --git a/tools/lib/traceevent/event-parse.c b/tools/lib/traceevent/event-parse.c index 13fd9fdf91e0..3e83636076b2 100644 --- a/tools/lib/traceevent/event-parse.c +++ b/tools/lib/traceevent/event-parse.c @@ -142,6 +142,25 @@ static int cmdline_cmp(const void *a, const void *b) return 0; } +/* Looking for where to place the key */ +static int cmdline_slot_cmp(const void *a, const void *b) +{ + const struct tep_cmdline *ca = a; + const struct tep_cmdline *cb = b; + const struct tep_cmdline *cb1 = cb + 1; + + if (ca->pid < cb->pid) + return -1; + + if (ca->pid > cb->pid) { + if (ca->pid <= cb1->pid) + return 0; + return 1; + } + + return 0; +} + struct cmdline_list { struct cmdline_list *next; char *comm; @@ -239,6 +258,7 @@ static int add_new_comm(struct tep_handle *tep, struct tep_cmdline *cmdline; struct tep_cmdline key; char *new_comm; + int cnt; if (!pid) return 0; @@ -271,18 +291,41 @@ static int add_new_comm(struct tep_handle *tep, } tep->cmdlines = cmdlines; - cmdlines[tep->cmdline_count].comm = strdup(comm); - if (!cmdlines[tep->cmdline_count].comm) { + key.comm = strdup(comm); + if (!key.comm) { errno = ENOMEM; return -1; } - cmdlines[tep->cmdline_count].pid = pid; - - if (cmdlines[tep->cmdline_count].comm) + if (!tep->cmdline_count) { + /* no entries yet */ + tep->cmdlines[0] = key; tep->cmdline_count++; + return 0; + } - qsort(cmdlines, tep->cmdline_count, sizeof(*cmdlines), cmdline_cmp); + /* Now find where we want to store the new cmdline */ + cmdline = bsearch(&key, tep->cmdlines, tep->cmdline_count - 1, + sizeof(*tep->cmdlines), cmdline_slot_cmp); + + cnt = tep->cmdline_count; + if (cmdline) { + /* cmdline points to the one before the spot we want */ + cmdline++; + cnt -= cmdline - tep->cmdlines; + + } else { + /* The new entry is either before or after the list */ + if (key.pid > tep->cmdlines[tep->cmdline_count - 1].pid) { + tep->cmdlines[tep->cmdline_count++] = key; + return 0; + } + cmdline = &tep->cmdlines[0]; + } + memmove(cmdline + 1, cmdline, (cnt * sizeof(*cmdline))); + *cmdline = key; + + tep->cmdline_count++; return 0; } -- 2.20.1 ^ permalink raw reply related [flat|nested] 5+ messages in thread
* [tip: perf/core] tools lib traceevent: Remove unneeded qsort and uses memmove instead 2019-08-28 19:05 ` [PATCH 2/2] tools lib traceevent: Remove unneeded qsort and uses memmove instead Steven Rostedt @ 2019-08-29 19:02 ` tip-bot2 for Steven Rostedt (VMware) 0 siblings, 0 replies; 5+ messages in thread From: tip-bot2 for Steven Rostedt (VMware) @ 2019-08-29 19:02 UTC (permalink / raw) To: linux-tip-commits Cc: Steven Rostedt (VMware), Andrew Morton, Jiri Olsa, Namhyung Kim, linux-trace-devel, Arnaldo Carvalho de Melo, Ingo Molnar, Borislav Petkov, linux-kernel The following commit has been merged into the perf/core branch of tip: Commit-ID: 301011ba622513cb41ced59973972204e0da2f71 Gitweb: https://git.kernel.org/tip/301011ba622513cb41ced59973972204e0da2f71 Author: Steven Rostedt (VMware) <rostedt@goodmis.org> AuthorDate: Wed, 28 Aug 2019 15:05:29 -04:00 Committer: Arnaldo Carvalho de Melo <acme@redhat.com> CommitterDate: Thu, 29 Aug 2019 08:36:12 -03:00 tools lib traceevent: Remove unneeded qsort and uses memmove instead While reading a trace data file that had 100,000s of tasks, the process took an extremely long time. I profiled it down to add_new_comm(), which was doing a qsort() call on an array that was pretty much already sorted (all but the last element. qsort() isn't very efficient when dealing with mostly sorted arrays, and this definitely showed its issues. When adding a new task to the task list, instead of using qsort(), do another bsearch() with a function that will find the element before where the new task will be inserted in. Then simply shift the rest of the array, and insert the task where it belongs. Fixes: f7d82350e597d ("tools/events: Add files to create libtraceevent.a") Signed-off-by: Steven Rostedt (VMware) <rostedt@goodmis.org> Cc: Andrew Morton <akpm@linux-foundation.org> Cc: Jiri Olsa <jolsa@redhat.com> Cc: Namhyung Kim <namhyung@kernel.org> Cc: linux-trace-devel@vger.kernel.org Link: http://lkml.kernel.org/r/20190828191820.127233764@goodmis.org Signed-off-by: Arnaldo Carvalho de Melo <acme@redhat.com> --- tools/lib/traceevent/event-parse.c | 55 +++++++++++++++++++++++++---- 1 file changed, 49 insertions(+), 6 deletions(-) diff --git a/tools/lib/traceevent/event-parse.c b/tools/lib/traceevent/event-parse.c index 13fd9fd..3e83636 100644 --- a/tools/lib/traceevent/event-parse.c +++ b/tools/lib/traceevent/event-parse.c @@ -142,6 +142,25 @@ static int cmdline_cmp(const void *a, const void *b) return 0; } +/* Looking for where to place the key */ +static int cmdline_slot_cmp(const void *a, const void *b) +{ + const struct tep_cmdline *ca = a; + const struct tep_cmdline *cb = b; + const struct tep_cmdline *cb1 = cb + 1; + + if (ca->pid < cb->pid) + return -1; + + if (ca->pid > cb->pid) { + if (ca->pid <= cb1->pid) + return 0; + return 1; + } + + return 0; +} + struct cmdline_list { struct cmdline_list *next; char *comm; @@ -239,6 +258,7 @@ static int add_new_comm(struct tep_handle *tep, struct tep_cmdline *cmdline; struct tep_cmdline key; char *new_comm; + int cnt; if (!pid) return 0; @@ -271,18 +291,41 @@ static int add_new_comm(struct tep_handle *tep, } tep->cmdlines = cmdlines; - cmdlines[tep->cmdline_count].comm = strdup(comm); - if (!cmdlines[tep->cmdline_count].comm) { + key.comm = strdup(comm); + if (!key.comm) { errno = ENOMEM; return -1; } - cmdlines[tep->cmdline_count].pid = pid; - - if (cmdlines[tep->cmdline_count].comm) + if (!tep->cmdline_count) { + /* no entries yet */ + tep->cmdlines[0] = key; tep->cmdline_count++; + return 0; + } - qsort(cmdlines, tep->cmdline_count, sizeof(*cmdlines), cmdline_cmp); + /* Now find where we want to store the new cmdline */ + cmdline = bsearch(&key, tep->cmdlines, tep->cmdline_count - 1, + sizeof(*tep->cmdlines), cmdline_slot_cmp); + + cnt = tep->cmdline_count; + if (cmdline) { + /* cmdline points to the one before the spot we want */ + cmdline++; + cnt -= cmdline - tep->cmdlines; + + } else { + /* The new entry is either before or after the list */ + if (key.pid > tep->cmdlines[tep->cmdline_count - 1].pid) { + tep->cmdlines[tep->cmdline_count++] = key; + return 0; + } + cmdline = &tep->cmdlines[0]; + } + memmove(cmdline + 1, cmdline, (cnt * sizeof(*cmdline))); + *cmdline = key; + + tep->cmdline_count++; return 0; } ^ permalink raw reply related [flat|nested] 5+ messages in thread
end of thread, other threads:[~2019-08-29 19:02 UTC | newest] Thread overview: 5+ messages (download: mbox.gz / follow: Atom feed) -- links below jump to the message on this page -- 2019-08-28 19:05 [PATCH 0/2] tools lib traceevent: Fixes for adding tasks to the tep descriptor Steven Rostedt 2019-08-28 19:05 ` [PATCH 1/2] tools lib traceevent: Do not free tep->cmdlines in add_new_comm() on failure Steven Rostedt 2019-08-29 19:02 ` [tip: perf/core] " tip-bot2 for Steven Rostedt (VMware) 2019-08-28 19:05 ` [PATCH 2/2] tools lib traceevent: Remove unneeded qsort and uses memmove instead Steven Rostedt 2019-08-29 19:02 ` [tip: perf/core] " tip-bot2 for Steven Rostedt (VMware)
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).