From mboxrd@z Thu Jan 1 00:00:00 1970 Return-Path: X-Spam-Checker-Version: SpamAssassin 3.4.0 (2014-02-07) on aws-us-west-2-korg-lkml-1.web.codeaurora.org X-Spam-Level: X-Spam-Status: No, score=-17.4 required=3.0 tests=DKIMWL_WL_MED,DKIM_SIGNED, DKIM_VALID,DKIM_VALID_AU,HEADER_FROM_DIFFERENT_DOMAINS,INCLUDES_PATCH, MAILING_LIST_MULTI,SIGNED_OFF_BY,SPF_HELO_NONE,SPF_PASS,USER_AGENT_GIT, USER_IN_DEF_DKIM_WL autolearn=ham autolearn_force=no version=3.4.0 Received: from mail.kernel.org (mail.kernel.org [198.145.29.99]) by smtp.lore.kernel.org (Postfix) with ESMTP id D62A1C3B18F for ; Fri, 14 Feb 2020 07:51:53 +0000 (UTC) Received: from vger.kernel.org (vger.kernel.org [209.132.180.67]) by mail.kernel.org (Postfix) with ESMTP id 9F5B6222C2 for ; Fri, 14 Feb 2020 07:51:53 +0000 (UTC) Authentication-Results: mail.kernel.org; dkim=pass (2048-bit key) header.d=google.com header.i=@google.com header.b="hCZ3MZfK" Received: (majordomo@vger.kernel.org) by vger.kernel.org via listexpand id S1728997AbgBNHvx (ORCPT ); Fri, 14 Feb 2020 02:51:53 -0500 Received: from mail-pl1-f202.google.com ([209.85.214.202]:47796 "EHLO mail-pl1-f202.google.com" rhost-flags-OK-OK-OK-OK) by vger.kernel.org with ESMTP id S1726080AbgBNHvt (ORCPT ); Fri, 14 Feb 2020 02:51:49 -0500 Received: by mail-pl1-f202.google.com with SMTP id h3so4758920plt.14 for ; Thu, 13 Feb 2020 23:51:49 -0800 (PST) DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=google.com; s=20161025; h=date:in-reply-to:message-id:mime-version:references:subject:from:to :cc; bh=tYGzLCMmcK1ubny/nFmpTz+Ztol/asD7dVnsre2EhPo=; b=hCZ3MZfKm2gG1AYAjG6L/TymCn4SBKtW8orBkmrlgqu3oZY7iZlPBzmARr25WY7Dgg xeVryKNgRDIRhSGtpQ9H012+cdav3Yv/PtFvuKa2NF/Y1N2q8HcXSWMc3bhBp3JNejee 8W86TR5C1Ots3NBKBv2kLVUMisHtsviI+8Y7s7D/ekJDNS/DmD3RLlncYuFsarm/OKh+ n893sPkgJUMEh9LzQfzYxlt1xuOtjDjKHutWYiK0elNEl/Kt0xwqDndYwDf0kQbUQBhm RPkEbp+1v1teXfhKOXWePHZBwzWXl/q9qgMgKQclQGjbW5Ib+dUrtnBP7UWmpP+47bpV 4rKQ== X-Google-DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=1e100.net; s=20161025; h=x-gm-message-state:date:in-reply-to:message-id:mime-version :references:subject:from:to:cc; bh=tYGzLCMmcK1ubny/nFmpTz+Ztol/asD7dVnsre2EhPo=; b=skNO47+WG2SJdQ+OD7Ebl9gLFuScT17pQfvoaOS1VlgY2zxp9lWEJf3/69L9J4xY3x J1SbrKoQkiglRHdZRigj7/77Xj8sdjukk69XziL1X3G9zgRx0/xgLWk5WN0wsr4dCPGq Eloth93/CCA9yQPxXH6uuIuCDuj6gIstvZHuSVaNpQZjCngtFoyEu8TB52clAJ29oGxb l/zIWjh39lbrgen4kqnND52YMNKz5S0nM7pPrruai1UgOQiQ9MjdYyLPQp3Ro/768qni AYNKnqdpMhEumcVmjEX+z5k04A97zD0aTfHwcuN6YKbCfDSHkw3+mklPg5kYM1R6BgLw UE2g== X-Gm-Message-State: APjAAAVFdxYwVgdKNyTO3g/0BXY2lgBONOnqzmLmKWdWWkybhHqwv/Oa 27kqWyWH0zue6H69s4HFALia9p+JLfoE X-Google-Smtp-Source: APXvYqwENBrbTBlD+UtG4AepPDIWIkqg187S7xEabrcXKcDRsJ/3ivoQyv3TzCeamBl0uWX7Bfk9bGHrCUBm X-Received: by 2002:a63:5809:: with SMTP id m9mr2082324pgb.26.1581666708720; Thu, 13 Feb 2020 23:51:48 -0800 (PST) Date: Thu, 13 Feb 2020 23:51:30 -0800 In-Reply-To: <20200214075133.181299-1-irogers@google.com> Message-Id: <20200214075133.181299-4-irogers@google.com> Mime-Version: 1.0 References: <20191206231539.227585-1-irogers@google.com> <20200214075133.181299-1-irogers@google.com> X-Mailer: git-send-email 2.25.0.265.gbab2e86ba0-goog Subject: [PATCH v6 3/6] perf: Use min_heap in visit_groups_merge From: Ian Rogers To: Peter Zijlstra , Ingo Molnar , Arnaldo Carvalho de Melo , Mark Rutland , Alexander Shishkin , Jiri Olsa , Namhyung Kim , Andrew Morton , Randy Dunlap , Masahiro Yamada , Shuah Khan , Krzysztof Kozlowski , Kees Cook , "Paul E. McKenney" , Masami Hiramatsu , Marco Elver , Kent Overstreet , Andy Shevchenko , Ard Biesheuvel , Gary Hook , Kan Liang , linux-kernel@vger.kernel.org Cc: Stephane Eranian , Andi Kleen , Ian Rogers Content-Type: text/plain; charset="UTF-8" Sender: linux-kernel-owner@vger.kernel.org Precedence: bulk List-ID: X-Mailing-List: linux-kernel@vger.kernel.org visit_groups_merge will pick the next event based on when it was inserted in to the context (perf_event group_index). Events may be per CPU or for any CPU, but in the future we'd also like to have per cgroup events to avoid searching all events for the events to schedule for a cgroup. Introduce a min heap for the events that maintains a property that the earliest inserted event is always at the 0th element. Initialize the heap with per-CPU and any-CPU events for the context. Based-on-work-by: Peter Zijlstra (Intel) Signed-off-by: Ian Rogers --- kernel/events/core.c | 72 +++++++++++++++++++++++++++++++++----------- 1 file changed, 54 insertions(+), 18 deletions(-) diff --git a/kernel/events/core.c b/kernel/events/core.c index 9bd2af954c54..832e2a56a663 100644 --- a/kernel/events/core.c +++ b/kernel/events/core.c @@ -49,6 +49,7 @@ #include #include #include +#include #include "internal.h" @@ -3388,32 +3389,67 @@ static void cpu_ctx_sched_out(struct perf_cpu_context *cpuctx, ctx_sched_out(&cpuctx->ctx, cpuctx, event_type); } -static int visit_groups_merge(struct perf_event_groups *groups, int cpu, - int (*func)(struct perf_event *, void *), void *data) +static bool perf_cmp_group_idx(const void *l, const void *r) { - struct perf_event **evt, *evt1, *evt2; + const struct perf_event *le = l, *re = r; + + return le->group_index < re->group_index; +} + +static void swap_ptr(void *l, void *r) +{ + void **lp = l, **rp = r; + + swap(*lp, *rp); +} + +static const struct min_heap_callbacks perf_min_heap = { + .elem_size = sizeof(struct perf_event *), + .cmp = perf_cmp_group_idx, + .swp = swap_ptr, +}; + +static void __heap_add(struct min_heap *heap, struct perf_event *event) +{ + struct perf_event **itrs = heap->data; + + if (event) { + itrs[heap->size] = event; + heap->size++; + } +} + +static noinline int visit_groups_merge(struct perf_event_groups *groups, + int cpu, + int (*func)(struct perf_event *, void *), + void *data) +{ + /* Space for per CPU and/or any CPU event iterators. */ + struct perf_event *itrs[2]; + struct min_heap event_heap = { + .data = itrs, + .size = 0, + .cap = ARRAY_SIZE(itrs), + }; + struct perf_event *next; int ret; - evt1 = perf_event_groups_first(groups, -1); - evt2 = perf_event_groups_first(groups, cpu); + __heap_add(&event_heap, perf_event_groups_first(groups, -1)); + __heap_add(&event_heap, perf_event_groups_first(groups, cpu)); - while (evt1 || evt2) { - if (evt1 && evt2) { - if (evt1->group_index < evt2->group_index) - evt = &evt1; - else - evt = &evt2; - } else if (evt1) { - evt = &evt1; - } else { - evt = &evt2; - } + min_heapify_all(&event_heap, &perf_min_heap); - ret = func(*evt, data); + while (event_heap.size) { + ret = func(itrs[0], data); if (ret) return ret; - *evt = perf_event_groups_next(*evt); + next = perf_event_groups_next(itrs[0]); + if (next) { + min_heap_pop_push(&event_heap, &next, + &perf_min_heap); + } else + min_heap_pop(&event_heap, &perf_min_heap); } return 0; -- 2.25.0.265.gbab2e86ba0-goog