[PATCH v3 00/10] Optimize cgroup context switch

[Ian Rogers]

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.

These patches include a caching algorithm to improve the search for
the first event in a group by Kan Liang <kan.liang@xxxxxxxxxxxxxxx> 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 max 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_max_heap.h | 134 +++++++++
 include/linux/perf_event.h   |  14 +
 kernel/events/core.c         | 512 ++++++++++++++++++++++++++++-------
 lib/Kconfig.debug            |  10 +
 lib/Makefile                 |   1 +
 lib/test_min_max_heap.c      | 194 +++++++++++++
 6 files changed, 769 insertions(+), 96 deletions(-)
 create mode 100644 include/linux/min_max_heap.h
 create mode 100644 lib/test_min_max_heap.c

-- 
2.24.0.432.g9d3f5f5b63-goog