[PATCH v5 00/10] Optimize cgroup context switch

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>,
	Masahiro Yamada <yamada.masahiro@socionext.com>,
	Kees Cook <keescook@chromium.org>,
	Catalin Marinas <catalin.marinas@arm.com>,
	Petr Mladek <pmladek@suse.com>,
	Mauro Carvalho Chehab <mchehab+samsung@kernel.org>,
	Qian Cai <cai@lca.pw>, Joe Lawrence <joe.lawrence@redhat.com>,
	Tetsuo Handa <penguin-kernel@i-love.sakura.ne.jp>,
	"Uladzislau Rezki (Sony)" <urezki@gmail.com>,
	Andy Shevchenko <andriy.shevchenko@linux.intel.com>,
	Ard Biesheuvel <ardb@kernel.org>,
	"David S. Miller" <davem@davemloft.net>,
	Kent Overstreet <kent.overstreet@gmail.com>,
	Gary Hook <Gary.Hook@amd.com>, Arnd Bergmann <arnd@arndb.de>,
	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 v5 00/10] Optimize cgroup context switch
Date: Fri,  6 Dec 2019 15:15:29 -0800	[thread overview]
Message-ID: <20191206231539.227585-1-irogers@google.com> (raw)
In-Reply-To: <20191116011845.177150-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 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 (8):
  lib: introduce generic min-heap
  perf: Use min_max_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
  perf: simplify and rename visit_groups_merge
  perf: cache perf_event_groups_first for cgroups
  perf: optimize event_filter_match during sched_in

Kan Liang (1):
  perf/cgroup: Do not switch system-wide events in cgroup switch

Peter Zijlstra (1):
  perf/cgroup: Reorder perf_cgroup_connect()

 include/linux/min_heap.h   | 135 +++++++++
 include/linux/perf_event.h |  15 +
 kernel/events/core.c       | 542 +++++++++++++++++++++++++++++--------
 lib/Kconfig.debug          |  10 +
 lib/Makefile               |   1 +
 lib/test_min_heap.c        | 194 +++++++++++++
 6 files changed, 783 insertions(+), 114 deletions(-)
 create mode 100644 include/linux/min_heap.h
 create mode 100644 lib/test_min_heap.c

-- 
2.24.0.393.g34dc348eaf-goog