lists.openwall.net   lists  /  announce  owl-users  owl-dev  john-users  john-dev  passwdqc-users  yescrypt  popa3d-users  /  oss-security  kernel-hardening  musl  sabotage  tlsify  passwords  /  crypt-dev  xvendor  /  Bugtraq  Full-Disclosure  linux-kernel  linux-netdev  linux-ext4  PHC 
Open Source and information security mailing list archives
 
Hash Suite: Windows password security audit tool. GUI, reports in PDF.
[<prev] [next>] [<thread-prev] [thread-next>] [day] [month] [year] [list]
Date:   Thu, 13 Feb 2020 23:51:27 -0800
From:   Ian Rogers <irogers@...gle.com>
To:     Peter Zijlstra <peterz@...radead.org>,
        Ingo Molnar <mingo@...hat.com>,
        Arnaldo Carvalho de Melo <acme@...nel.org>,
        Mark Rutland <mark.rutland@....com>,
        Alexander Shishkin <alexander.shishkin@...ux.intel.com>,
        Jiri Olsa <jolsa@...hat.com>,
        Namhyung Kim <namhyung@...nel.org>,
        Andrew Morton <akpm@...ux-foundation.org>,
        Randy Dunlap <rdunlap@...radead.org>,
        Masahiro Yamada <yamada.masahiro@...ionext.com>,
        Shuah Khan <skhan@...uxfoundation.org>,
        Krzysztof Kozlowski <krzk@...nel.org>,
        Kees Cook <keescook@...omium.org>,
        "Paul E. McKenney" <paulmck@...nel.org>,
        Masami Hiramatsu <mhiramat@...nel.org>,
        Marco Elver <elver@...gle.com>,
        Kent Overstreet <kent.overstreet@...il.com>,
        Andy Shevchenko <andriy.shevchenko@...ux.intel.com>,
        Ard Biesheuvel <ardb@...nel.org>,
        Gary Hook <Gary.Hook@....com>,
        Kan Liang <kan.liang@...ux.intel.com>,
        linux-kernel@...r.kernel.org
Cc:     Stephane Eranian <eranian@...gle.com>,
        Andi Kleen <ak@...ux.intel.com>,
        Ian Rogers <irogers@...gle.com>
Subject: [PATCH v6 0/6] Optimize cgroup context switch

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@...ux.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

Powered by blists - more mailing lists