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 Received: from vger.kernel.org (vger.kernel.org [23.128.96.18]) by smtp.lore.kernel.org (Postfix) with ESMTP id 8593BC433F5 for ; Mon, 28 Mar 2022 06:24:50 +0000 (UTC) Received: (majordomo@vger.kernel.org) by vger.kernel.org via listexpand id S234946AbiC1G01 (ORCPT ); Mon, 28 Mar 2022 02:26:27 -0400 Received: from lindbergh.monkeyblade.net ([23.128.96.19]:56766 "EHLO lindbergh.monkeyblade.net" rhost-flags-OK-OK-OK-OK) by vger.kernel.org with ESMTP id S238409AbiC1G0G (ORCPT ); Mon, 28 Mar 2022 02:26:06 -0400 Received: from mail-yw1-x114a.google.com (mail-yw1-x114a.google.com [IPv6:2607:f8b0:4864:20::114a]) by lindbergh.monkeyblade.net (Postfix) with ESMTPS id 8CBD34ECC7 for ; Sun, 27 Mar 2022 23:24:26 -0700 (PDT) Received: by mail-yw1-x114a.google.com with SMTP id 00721157ae682-2e6d04210b3so80571667b3.10 for ; Sun, 27 Mar 2022 23:24:26 -0700 (PDT) DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=google.com; s=20210112; h=date:in-reply-to:message-id:mime-version:references:subject:from:to :cc; bh=YZdCpDo2MwsKjb0WbdxKDFQz4ii0U4OJCI/h5Uxfyc8=; b=hVa/7ihqPsZym2uTsY9dt+yok+r2vNttS+kECPUz8hlfd3jStwkXswPdBeCrSKu+8r QeU5/PriYcQc4cgKtYeuqB+cy1x97REfIUo0tC2tFZO4gXeIS/xcS05fs5cuywbioJnn dptX2c3gxaqTVY27IxEJg86seWOY2oqTzL9/HTiP5pi8uDw/SFsbF0HjegJ7qMvBkPpR Tb3CYk2hqKAcsnVo+uJYoHlxxOo6v1WKZhiKvPpnMIB8kTTUbg3sdPpLNwbIU7oZ6r3k wnckyfAkBl3jtmyGjoDKqwQt5IoJGvKr37Zhaq02trVr8xMkQL0hE58dHckjoxQCLiWN W71w== X-Google-DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=1e100.net; s=20210112; h=x-gm-message-state:date:in-reply-to:message-id:mime-version :references:subject:from:to:cc; bh=YZdCpDo2MwsKjb0WbdxKDFQz4ii0U4OJCI/h5Uxfyc8=; b=A0W8ZazCkFCFimmw5/9CZXn78S2uTOxE/3iOQoWdcl0sBhZ80knvjASKfp99KmXkjX CaRaa7f+1t/9y8I6Hd57wyOBeXv/X6//0h6AFA3PwJCXWLzNi5B7aBb15UPtGxsNDCTH a7w2ZylmXK5R8noC94tLfiXIzjMzkcGYL6Tmn6qXuO+CCGv/+GJw6c3oP8PLBZSTSt5T d/R+fUbgPcibc6l1DYWENVQLwVN46Pd/PH4lGRHdbpMivWzMyfywi8cGah0XKqYcJMbb HYAJ5+Z9+Icnm6gOR0oGV+Fr4HH3sSoqpmjbRwkjbWt/VNVOgJSvLoGCJ3n1cog5yK99 Nr4A== X-Gm-Message-State: AOAM530gi0BQ/IdS8rv2IEuc1DTVhShmcrvEMfchs1z8I/jlSj67Kica 0XLiDcQq61FnnUIp4GrzbXjL8TMtiiZ6 X-Google-Smtp-Source: ABdhPJzQSAN+iwF+0ELfjnRELyBsh17NWxruCk/wZoBkE5XSh7FJRsS5lOFGmt2jB/qkes1g2fsc2qElJ/xK X-Received: from irogers.svl.corp.google.com ([2620:15c:2cd:202:ef08:ed1b:261f:77fa]) (user=irogers job=sendgmr) by 2002:a05:6902:150b:b0:639:f81:8179 with SMTP id q11-20020a056902150b00b006390f818179mr17151751ybu.31.1648448665698; Sun, 27 Mar 2022 23:24:25 -0700 (PDT) Date: Sun, 27 Mar 2022 23:24:11 -0700 In-Reply-To: <20220328062414.1893550-1-irogers@google.com> Message-Id: <20220328062414.1893550-3-irogers@google.com> Mime-Version: 1.0 References: <20220328062414.1893550-1-irogers@google.com> X-Mailer: git-send-email 2.35.1.1021.g381101b075-goog Subject: [PATCH 2/5] perf cpumap: More cpu map reuse by merge. From: Ian Rogers To: Peter Zijlstra , Ingo Molnar , Arnaldo Carvalho de Melo , Mark Rutland , Alexander Shishkin , Jiri Olsa , Namhyung Kim , Mathieu Poirier , Suzuki K Poulose , Mike Leach , Leo Yan , John Garry , Will Deacon , Alexei Starovoitov , Daniel Borkmann , Andrii Nakryiko , Martin KaFai Lau , Song Liu , Yonghong Song , John Fastabend , KP Singh , Kajol Jain , James Clark , German Gomez , Adrian Hunter , Riccardo Mancini , Andi Kleen , Alexey Bayduraev , Alexander Antonov , linux-perf-users@vger.kernel.org, linux-kernel@vger.kernel.org, coresight@lists.linaro.org, linux-arm-kernel@lists.infradead.org, netdev@vger.kernel.org, bpf@vger.kernel.org Cc: Stephane Eranian , Ian Rogers Content-Type: text/plain; charset="UTF-8" Precedence: bulk List-ID: X-Mailing-List: linux-kernel@vger.kernel.org perf_cpu_map__merge will reuse one of its arguments if they are equal or the other argument is NULL. The arguments could be reused if it is known one set of values is a subset of the other. For example, a map of 0-1 and a map of just 0 when merged yields the map of 0-1. Currently a new map is created rather than adding a reference count to the original 0-1 map. Signed-off-by: Ian Rogers --- tools/lib/perf/cpumap.c | 38 ++++++++++++++++++++++++++++---------- 1 file changed, 28 insertions(+), 10 deletions(-) diff --git a/tools/lib/perf/cpumap.c b/tools/lib/perf/cpumap.c index ee66760f1e63..953bc50b0e41 100644 --- a/tools/lib/perf/cpumap.c +++ b/tools/lib/perf/cpumap.c @@ -319,6 +319,29 @@ struct perf_cpu perf_cpu_map__max(struct perf_cpu_map *map) return map->nr > 0 ? map->map[map->nr - 1] : result; } +/** Is 'b' a subset of 'a'. */ +static bool perf_cpu_map__is_subset(const struct perf_cpu_map *a, + const struct perf_cpu_map *b) +{ + int i, j; + + if (a == b || !b) + return true; + if (!a || b->nr > a->nr) + return false; + j = 0; + for (i = 0; i < a->nr; i++) { + if (a->map[i].cpu > b->map[j].cpu) + return false; + if (a->map[i].cpu == b->map[j].cpu) { + j++; + if (j == b->nr) + return true; + } + } + return false; +} + /* * Merge two cpumaps * @@ -335,17 +358,12 @@ struct perf_cpu_map *perf_cpu_map__merge(struct perf_cpu_map *orig, int i, j, k; struct perf_cpu_map *merged; - if (!orig && !other) - return NULL; - if (!orig) { - perf_cpu_map__get(other); - return other; - } - if (!other) - return orig; - if (orig->nr == other->nr && - !memcmp(orig->map, other->map, orig->nr * sizeof(struct perf_cpu))) + if (perf_cpu_map__is_subset(orig, other)) return orig; + if (perf_cpu_map__is_subset(other, orig)) { + perf_cpu_map__put(orig); + return perf_cpu_map__get(other); + } tmp_len = orig->nr + other->nr; tmp_cpus = malloc(tmp_len * sizeof(struct perf_cpu)); -- 2.35.1.1021.g381101b075-goog 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 Received: from bombadil.infradead.org (bombadil.infradead.org [198.137.202.133]) (using TLSv1.2 with cipher ECDHE-RSA-AES256-GCM-SHA384 (256/256 bits)) (No client certificate requested) by smtp.lore.kernel.org (Postfix) with ESMTPS id 28441C433F5 for ; Mon, 28 Mar 2022 06:26:03 +0000 (UTC) DKIM-Signature: v=1; a=rsa-sha256; q=dns/txt; c=relaxed/relaxed; d=lists.infradead.org; s=bombadil.20210309; h=Sender: Content-Transfer-Encoding:Content-Type:List-Subscribe:List-Help:List-Post: List-Archive:List-Unsubscribe:List-Id:Cc:To:From:Subject:References: Mime-Version:Message-Id:In-Reply-To:Date:Reply-To:Content-ID: Content-Description:Resent-Date:Resent-From:Resent-Sender:Resent-To:Resent-Cc :Resent-Message-ID:List-Owner; bh=38fLEsO4UQHkY5RcUhnK2PVyxbqxNCm1V79q0RSfAcA=; b=c5VMd77oB2Zpalc8dLSvz04zrp 7g1HpKfJRvOB8zX3NTaZsMD05yCKsrCrkSqDCegW4cm3wUaTjfu+hoH5tpL5WEE1N6a50wvV7i4sk Q6UVRrt3zvXYA81p0YIHQ+H1NRyMCGka1vV84KLUCKZ1n7wsmgVy0N250aVDmj2+EKbXoqxCnO9yQ 40RPGNxnbY5rzl1XkxZ5H0f8rylIYLrSt2WZSKhy+F3cZhrpPtxA0zDQckCKm4ytAm0RnnpsecDmi VZcRFPklde7lCB2ESWKDveOB+0V8G02s1RdFHGW8VN85UsNKdfzc/BM2CZD9T14y4hpsk+OCqz1hn WtIShPcg==; Received: from localhost ([::1] helo=bombadil.infradead.org) by bombadil.infradead.org with esmtp (Exim 4.94.2 #2 (Red Hat Linux)) id 1nYio5-007T1M-Eu; Mon, 28 Mar 2022 06:24:49 +0000 Received: from mail-yw1-x1149.google.com ([2607:f8b0:4864:20::1149]) by bombadil.infradead.org with esmtps (Exim 4.94.2 #2 (Red Hat Linux)) id 1nYinj-007Ssq-0W for linux-arm-kernel@lists.infradead.org; Mon, 28 Mar 2022 06:24:28 +0000 Received: by mail-yw1-x1149.google.com with SMTP id 00721157ae682-2d2d45c0df7so111191707b3.1 for ; Sun, 27 Mar 2022 23:24:26 -0700 (PDT) DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=google.com; s=20210112; h=date:in-reply-to:message-id:mime-version:references:subject:from:to :cc; bh=YZdCpDo2MwsKjb0WbdxKDFQz4ii0U4OJCI/h5Uxfyc8=; b=hVa/7ihqPsZym2uTsY9dt+yok+r2vNttS+kECPUz8hlfd3jStwkXswPdBeCrSKu+8r QeU5/PriYcQc4cgKtYeuqB+cy1x97REfIUo0tC2tFZO4gXeIS/xcS05fs5cuywbioJnn dptX2c3gxaqTVY27IxEJg86seWOY2oqTzL9/HTiP5pi8uDw/SFsbF0HjegJ7qMvBkPpR Tb3CYk2hqKAcsnVo+uJYoHlxxOo6v1WKZhiKvPpnMIB8kTTUbg3sdPpLNwbIU7oZ6r3k wnckyfAkBl3jtmyGjoDKqwQt5IoJGvKr37Zhaq02trVr8xMkQL0hE58dHckjoxQCLiWN W71w== X-Google-DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=1e100.net; s=20210112; h=x-gm-message-state:date:in-reply-to:message-id:mime-version :references:subject:from:to:cc; bh=YZdCpDo2MwsKjb0WbdxKDFQz4ii0U4OJCI/h5Uxfyc8=; b=j1zD5XrDgko4oHoZTTAmoj084CryHrZuVzo/0BYkXMS6PBqUrXUcIjeN644VsSEkpr rDLyaXA0SrRLGBI2jw6Wv5qrK+1iWLz6r4nR9K+Ugqqkoie+QuesTuZFvPafD03PIUpN FV/GWdvZ2H37FmEVW11nm6xNQz1cDkZVaNEnyhweqn/Itn9pJj91Pbdg6AqYNargwPsY DGVc+nLbNQwPbxzMTfWrKdPBw0WiyAS9J0iRDiwLA19f5yZIoimzlCJ1s6f6r9Gyacpg KZS0dwKDNoI026/Eb6gDyu9HPQtmqg7N1GhxtvYTY87JCkJUOhkt/dHTzG9ASPLyVWM0 J18w== X-Gm-Message-State: AOAM532ufbxOxlm4aTy0jYFB6mvTA5GTy4gf8uNbSqyav4b3wz5CIpzi LjJebhr/MGN1YdX2nt+a/N3OnIX15FX9 X-Google-Smtp-Source: ABdhPJzQSAN+iwF+0ELfjnRELyBsh17NWxruCk/wZoBkE5XSh7FJRsS5lOFGmt2jB/qkes1g2fsc2qElJ/xK X-Received: from irogers.svl.corp.google.com ([2620:15c:2cd:202:ef08:ed1b:261f:77fa]) (user=irogers job=sendgmr) by 2002:a05:6902:150b:b0:639:f81:8179 with SMTP id q11-20020a056902150b00b006390f818179mr17151751ybu.31.1648448665698; Sun, 27 Mar 2022 23:24:25 -0700 (PDT) Date: Sun, 27 Mar 2022 23:24:11 -0700 In-Reply-To: <20220328062414.1893550-1-irogers@google.com> Message-Id: <20220328062414.1893550-3-irogers@google.com> Mime-Version: 1.0 References: <20220328062414.1893550-1-irogers@google.com> X-Mailer: git-send-email 2.35.1.1021.g381101b075-goog Subject: [PATCH 2/5] perf cpumap: More cpu map reuse by merge. From: Ian Rogers To: Peter Zijlstra , Ingo Molnar , Arnaldo Carvalho de Melo , Mark Rutland , Alexander Shishkin , Jiri Olsa , Namhyung Kim , Mathieu Poirier , Suzuki K Poulose , Mike Leach , Leo Yan , John Garry , Will Deacon , Alexei Starovoitov , Daniel Borkmann , Andrii Nakryiko , Martin KaFai Lau , Song Liu , Yonghong Song , John Fastabend , KP Singh , Kajol Jain , James Clark , German Gomez , Adrian Hunter , Riccardo Mancini , Andi Kleen , Alexey Bayduraev , Alexander Antonov , linux-perf-users@vger.kernel.org, linux-kernel@vger.kernel.org, coresight@lists.linaro.org, linux-arm-kernel@lists.infradead.org, netdev@vger.kernel.org, bpf@vger.kernel.org Cc: Stephane Eranian , Ian Rogers X-CRM114-Version: 20100106-BlameMichelson ( TRE 0.8.0 (BSD) ) MR-646709E3 X-CRM114-CacheID: sfid-20220327_232427_110278_43DD4295 X-CRM114-Status: GOOD ( 18.13 ) X-BeenThere: linux-arm-kernel@lists.infradead.org X-Mailman-Version: 2.1.34 Precedence: list List-Id: List-Unsubscribe: , List-Archive: List-Post: List-Help: List-Subscribe: , Content-Type: text/plain; charset="us-ascii" Content-Transfer-Encoding: 7bit Sender: "linux-arm-kernel" Errors-To: linux-arm-kernel-bounces+linux-arm-kernel=archiver.kernel.org@lists.infradead.org perf_cpu_map__merge will reuse one of its arguments if they are equal or the other argument is NULL. The arguments could be reused if it is known one set of values is a subset of the other. For example, a map of 0-1 and a map of just 0 when merged yields the map of 0-1. Currently a new map is created rather than adding a reference count to the original 0-1 map. Signed-off-by: Ian Rogers --- tools/lib/perf/cpumap.c | 38 ++++++++++++++++++++++++++++---------- 1 file changed, 28 insertions(+), 10 deletions(-) diff --git a/tools/lib/perf/cpumap.c b/tools/lib/perf/cpumap.c index ee66760f1e63..953bc50b0e41 100644 --- a/tools/lib/perf/cpumap.c +++ b/tools/lib/perf/cpumap.c @@ -319,6 +319,29 @@ struct perf_cpu perf_cpu_map__max(struct perf_cpu_map *map) return map->nr > 0 ? map->map[map->nr - 1] : result; } +/** Is 'b' a subset of 'a'. */ +static bool perf_cpu_map__is_subset(const struct perf_cpu_map *a, + const struct perf_cpu_map *b) +{ + int i, j; + + if (a == b || !b) + return true; + if (!a || b->nr > a->nr) + return false; + j = 0; + for (i = 0; i < a->nr; i++) { + if (a->map[i].cpu > b->map[j].cpu) + return false; + if (a->map[i].cpu == b->map[j].cpu) { + j++; + if (j == b->nr) + return true; + } + } + return false; +} + /* * Merge two cpumaps * @@ -335,17 +358,12 @@ struct perf_cpu_map *perf_cpu_map__merge(struct perf_cpu_map *orig, int i, j, k; struct perf_cpu_map *merged; - if (!orig && !other) - return NULL; - if (!orig) { - perf_cpu_map__get(other); - return other; - } - if (!other) - return orig; - if (orig->nr == other->nr && - !memcmp(orig->map, other->map, orig->nr * sizeof(struct perf_cpu))) + if (perf_cpu_map__is_subset(orig, other)) return orig; + if (perf_cpu_map__is_subset(other, orig)) { + perf_cpu_map__put(orig); + return perf_cpu_map__get(other); + } tmp_len = orig->nr + other->nr; tmp_cpus = malloc(tmp_len * sizeof(struct perf_cpu)); -- 2.35.1.1021.g381101b075-goog _______________________________________________ linux-arm-kernel mailing list linux-arm-kernel@lists.infradead.org http://lists.infradead.org/mailman/listinfo/linux-arm-kernel