From: Ian Rogers <irogers@google.com>
To: Peter Zijlstra <peterz@infradead.org>,
Ingo Molnar <mingo@redhat.com>,
Arnaldo Carvalho de Melo <acme@kernel.org>,
Mark Rutland <mark.rutland@arm.com>,
Alexander Shishkin <alexander.shishkin@linux.intel.com>,
Jiri Olsa <jolsa@redhat.com>, Namhyung Kim <namhyung@kernel.org>,
Andrew Morton <akpm@linux-foundation.org>,
Randy Dunlap <rdunlap@infradead.org>,
Masahiro Yamada <yamada.masahiro@socionext.com>,
Shuah Khan <skhan@linuxfoundation.org>,
Krzysztof Kozlowski <krzk@kernel.org>,
Kees Cook <keescook@chromium.org>,
"Paul E. McKenney" <paulmck@kernel.org>,
Masami Hiramatsu <mhiramat@kernel.org>,
Marco Elver <elver@google.com>,
Kent Overstreet <kent.overstreet@gmail.com>,
Andy Shevchenko <andriy.shevchenko@linux.intel.com>,
Ard Biesheuvel <ardb@kernel.org>, Gary Hook <Gary.Hook@amd.com>,
Kan Liang <kan.liang@linux.intel.com>,
linux-kernel@vger.kernel.org
Cc: Stephane Eranian <eranian@google.com>,
Andi Kleen <ak@linux.intel.com>, Ian Rogers <irogers@google.com>
Subject: [PATCH v6 0/6] Optimize cgroup context switch
Date: Thu, 13 Feb 2020 23:51:27 -0800 [thread overview]
Message-ID: <20200214075133.181299-1-irogers@google.com> (raw)
In-Reply-To: <20191206231539.227585-1-irogers@google.com>
Avoid iterating over all per-CPU events during cgroup changing context
switches by organizing events by cgroup.
To make an efficient set of iterators, introduce a min max heap
utility with test.
The v6 patch reduces the patch set by 4 patches, it updates the cgroup
id and fixes part of the min_heap rename from v5.
The v5 patch set renames min_max_heap to min_heap as suggested by
Peter Zijlstra, it also addresses comments around preferring
__always_inline over inline.
The v4 patch set addresses review comments on the v3 patch set by
Peter Zijlstra.
These patches include a caching algorithm to improve the search for
the first event in a group by Kan Liang <kan.liang@linux.intel.com> as
well as rebasing hit "optimize event_filter_match during sched_in"
from https://lkml.org/lkml/2019/8/7/771.
The v2 patch set was modified by Peter Zijlstra in his perf/cgroup
branch:
https://git.kernel.org/pub/scm/linux/kernel/git/peterz/queue.git
These patches follow Peter's reorganization and his fixes to the
perf_cpu_context min_heap storage code.
Ian Rogers (5):
lib: introduce generic min-heap
perf: Use min_heap in visit_groups_merge
perf: Add per perf_cpu_context min_heap storage
perf/cgroup: Grow per perf_cpu_context heap storage
perf/cgroup: Order events in RB tree by cgroup id
Peter Zijlstra (1):
perf/cgroup: Reorder perf_cgroup_connect()
include/linux/min_heap.h | 135 ++++++++++++++++++++
include/linux/perf_event.h | 7 ++
kernel/events/core.c | 251 +++++++++++++++++++++++++++++++------
lib/Kconfig.debug | 10 ++
lib/Makefile | 1 +
lib/test_min_heap.c | 194 ++++++++++++++++++++++++++++
6 files changed, 563 insertions(+), 35 deletions(-)
create mode 100644 include/linux/min_heap.h
create mode 100644 lib/test_min_heap.c
--
2.25.0.265.gbab2e86ba0-goog
next prev parent reply other threads:[~2020-02-14 7:51 UTC|newest]
Thread overview: 80+ messages / expand[flat|nested] mbox.gz Atom feed top
2019-11-14 0:30 [PATCH v3 00/10] Optimize cgroup context switch Ian Rogers
2019-11-14 0:30 ` [PATCH v3 01/10] perf/cgroup: Reorder perf_cgroup_connect() Ian Rogers
2019-11-14 8:50 ` Peter Zijlstra
2019-11-14 0:30 ` [PATCH v3 02/10] lib: introduce generic min max heap Ian Rogers
2019-11-14 9:32 ` Peter Zijlstra
2019-11-14 9:35 ` Peter Zijlstra
2019-11-17 18:28 ` Joe Perches
2019-11-18 8:40 ` Peter Zijlstra
2019-11-18 11:50 ` Joe Perches
2019-11-18 12:21 ` Peter Zijlstra
2019-11-14 0:30 ` [PATCH v3 03/10] perf: Use min_max_heap in visit_groups_merge Ian Rogers
2019-11-14 9:39 ` Peter Zijlstra
2019-11-14 0:30 ` [PATCH v3 04/10] perf: Add per perf_cpu_context min_heap storage Ian Rogers
2019-11-14 9:51 ` Peter Zijlstra
2019-11-16 1:19 ` Ian Rogers
2019-11-14 0:30 ` [PATCH v3 05/10] perf/cgroup: Grow per perf_cpu_context heap storage Ian Rogers
2019-11-14 9:54 ` Peter Zijlstra
2019-11-14 0:30 ` [PATCH v3 06/10] perf/cgroup: Order events in RB tree by cgroup id Ian Rogers
2019-11-14 0:30 ` [PATCH v3 07/10] perf: simplify and rename visit_groups_merge Ian Rogers
2019-11-14 10:03 ` Peter Zijlstra
2019-11-16 1:20 ` Ian Rogers
2019-11-14 0:30 ` [PATCH v3 08/10] perf: cache perf_event_groups_first for cgroups Ian Rogers
2019-11-14 10:25 ` Peter Zijlstra
2019-11-16 1:20 ` Ian Rogers
2019-11-18 8:37 ` Peter Zijlstra
2019-11-14 0:30 ` [PATCH v3 09/10] perf: optimize event_filter_match during sched_in Ian Rogers
2019-11-14 0:30 ` [PATCH v3 10/10] perf/cgroup: Do not switch system-wide events in cgroup switch Ian Rogers
2019-11-14 10:43 ` Peter Zijlstra
2019-11-14 13:46 ` Liang, Kan
2019-11-14 13:57 ` Peter Zijlstra
2019-11-14 15:16 ` Liang, Kan
2019-11-14 15:24 ` Liang, Kan
2019-11-14 20:49 ` Liang, Kan
2019-11-14 0:42 ` [PATCH v3 00/10] Optimize cgroup context switch Ian Rogers
2019-11-14 10:45 ` Peter Zijlstra
2019-11-14 18:17 ` Ian Rogers
2019-12-06 23:16 ` Ian Rogers
2019-11-16 1:18 ` [PATCH v4 " Ian Rogers
2019-11-16 1:18 ` [PATCH v4 01/10] perf/cgroup: Reorder perf_cgroup_connect() Ian Rogers
2019-11-16 1:18 ` [PATCH v4 02/10] lib: introduce generic min max heap Ian Rogers
2019-11-21 11:11 ` Joe Perches
2019-11-16 1:18 ` [PATCH v4 03/10] perf: Use min_max_heap in visit_groups_merge Ian Rogers
2019-11-16 1:18 ` [PATCH v4 04/10] perf: Add per perf_cpu_context min_heap storage Ian Rogers
2019-11-16 1:18 ` [PATCH v4 05/10] perf/cgroup: Grow per perf_cpu_context heap storage Ian Rogers
2019-11-16 1:18 ` [PATCH v4 06/10] perf/cgroup: Order events in RB tree by cgroup id Ian Rogers
2019-11-16 1:18 ` [PATCH v4 07/10] perf: simplify and rename visit_groups_merge Ian Rogers
2019-11-16 1:18 ` [PATCH v4 08/10] perf: cache perf_event_groups_first for cgroups Ian Rogers
2019-11-16 1:18 ` [PATCH v4 09/10] perf: optimize event_filter_match during sched_in Ian Rogers
2019-11-16 1:18 ` [PATCH v4 10/10] perf/cgroup: Do not switch system-wide events in cgroup switch Ian Rogers
2019-12-06 23:15 ` [PATCH v5 00/10] Optimize cgroup context switch Ian Rogers
2019-12-06 23:15 ` [PATCH v5 01/10] perf/cgroup: Reorder perf_cgroup_connect() Ian Rogers
2019-12-06 23:15 ` [PATCH v5 02/10] lib: introduce generic min-heap Ian Rogers
2019-12-06 23:15 ` [PATCH v5 03/10] perf: Use min_max_heap in visit_groups_merge Ian Rogers
2019-12-08 7:10 ` kbuild test robot
2019-12-06 23:15 ` [PATCH v5 04/10] perf: Add per perf_cpu_context min_heap storage Ian Rogers
2019-12-06 23:15 ` [PATCH v5 05/10] perf/cgroup: Grow per perf_cpu_context heap storage Ian Rogers
2019-12-06 23:15 ` [PATCH v5 06/10] perf/cgroup: Order events in RB tree by cgroup id Ian Rogers
2019-12-06 23:15 ` [PATCH v5 07/10] perf: simplify and rename visit_groups_merge Ian Rogers
2019-12-06 23:15 ` [PATCH v5 08/10] perf: cache perf_event_groups_first for cgroups Ian Rogers
2019-12-06 23:15 ` [PATCH v5 09/10] perf: optimize event_filter_match during sched_in Ian Rogers
2019-12-06 23:15 ` [PATCH v5 10/10] perf/cgroup: Do not switch system-wide events in cgroup switch Ian Rogers
2020-02-14 7:51 ` Ian Rogers [this message]
2020-02-14 7:51 ` [PATCH v6 1/6] perf/cgroup: Reorder perf_cgroup_connect() Ian Rogers
2020-02-14 16:11 ` Shuah Khan
2020-02-14 17:37 ` Peter Zijlstra
2020-03-06 14:42 ` [tip: perf/core] " tip-bot2 for Peter Zijlstra
2020-02-14 7:51 ` [PATCH v6 2/6] lib: introduce generic min-heap Ian Rogers
2020-02-14 22:06 ` Randy Dunlap
2020-02-17 16:29 ` Peter Zijlstra
2020-03-06 14:42 ` [tip: perf/core] lib: Introduce " tip-bot2 for Ian Rogers
2020-02-14 7:51 ` [PATCH v6 3/6] perf: Use min_heap in visit_groups_merge Ian Rogers
2020-02-17 17:23 ` Peter Zijlstra
2020-03-06 14:42 ` [tip: perf/core] perf/core: Use min_heap in visit_groups_merge() tip-bot2 for Ian Rogers
2020-02-14 7:51 ` [PATCH v6 4/6] perf: Add per perf_cpu_context min_heap storage Ian Rogers
2020-03-06 14:42 ` [tip: perf/core] perf/core: " tip-bot2 for Ian Rogers
2020-02-14 7:51 ` [PATCH v6 5/6] perf/cgroup: Grow per perf_cpu_context heap storage Ian Rogers
2020-03-06 14:42 ` [tip: perf/core] " tip-bot2 for Ian Rogers
2020-02-14 7:51 ` [PATCH v6 6/6] perf/cgroup: Order events in RB tree by cgroup id Ian Rogers
2020-02-14 19:32 ` [PATCH v6 0/6] Optimize cgroup context switch Ian Rogers
2020-02-17 16:18 ` Peter Zijlstra
Reply instructions:
You may reply publicly to this message via plain-text email
using any one of the following methods:
* Save the following mbox file, import it into your mail client,
and reply-to-all from there: mbox
Avoid top-posting and favor interleaved quoting:
https://en.wikipedia.org/wiki/Posting_style#Interleaved_style
* Reply using the --to, --cc, and --in-reply-to
switches of git-send-email(1):
git send-email \
--in-reply-to=20200214075133.181299-1-irogers@google.com \
--to=irogers@google.com \
--cc=Gary.Hook@amd.com \
--cc=acme@kernel.org \
--cc=ak@linux.intel.com \
--cc=akpm@linux-foundation.org \
--cc=alexander.shishkin@linux.intel.com \
--cc=andriy.shevchenko@linux.intel.com \
--cc=ardb@kernel.org \
--cc=elver@google.com \
--cc=eranian@google.com \
--cc=jolsa@redhat.com \
--cc=kan.liang@linux.intel.com \
--cc=keescook@chromium.org \
--cc=kent.overstreet@gmail.com \
--cc=krzk@kernel.org \
--cc=linux-kernel@vger.kernel.org \
--cc=mark.rutland@arm.com \
--cc=mhiramat@kernel.org \
--cc=mingo@redhat.com \
--cc=namhyung@kernel.org \
--cc=paulmck@kernel.org \
--cc=peterz@infradead.org \
--cc=rdunlap@infradead.org \
--cc=skhan@linuxfoundation.org \
--cc=yamada.masahiro@socionext.com \
/path/to/YOUR_REPLY
https://kernel.org/pub/software/scm/git/docs/git-send-email.html
* If your mail client supports setting the In-Reply-To header
via mailto: links, try the mailto: link
Be sure your reply has a Subject: header at the top and a blank line
before the message body.
This is a public inbox, see mirroring instructions
for how to clone and mirror all data and code used for this inbox