Re: [PATCH v2 5/6] perf cpumap: Add intersect function.

From: Arnaldo Carvalho de Melo <acme@kernel.org>
To: Ian Rogers <irogers@google.com>
Cc: Peter Zijlstra <peterz@infradead.org>,
	Ingo Molnar <mingo@redhat.com>,
	Mark Rutland <mark.rutland@arm.com>,
	Alexander Shishkin <alexander.shishkin@linux.intel.com>,
	Jiri Olsa <jolsa@kernel.org>, Namhyung Kim <namhyung@kernel.org>,
	Mathieu Poirier <mathieu.poirier@linaro.org>,
	Suzuki K Poulose <suzuki.poulose@arm.com>,
	Mike Leach <mike.leach@linaro.org>, Leo Yan <leo.yan@linaro.org>,
	John Garry <john.garry@huawei.com>, Will Deacon <will@kernel.org>,
	Alexei Starovoitov <ast@kernel.org>,
	Daniel Borkmann <daniel@iogearbox.net>,
	Andrii Nakryiko <andrii@kernel.org>,
	Martin KaFai Lau <kafai@fb.com>, Song Liu <songliubraving@fb.com>,
	Yonghong Song <yhs@fb.com>,
	John Fastabend <john.fastabend@gmail.com>,
	KP Singh <kpsingh@kernel.org>, Kajol Jain <kjain@linux.ibm.com>,
	James Clark <james.clark@arm.com>,
	German Gomez <german.gomez@arm.com>,
	Adrian Hunter <adrian.hunter@intel.com>,
	Riccardo Mancini <rickyman7@gmail.com>,
	Andi Kleen <ak@linux.intel.com>,
	Alexey Bayduraev <alexey.v.bayduraev@linux.intel.com>,
	Alexander Antonov <alexander.antonov@linux.intel.com>,
	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,
	Stephane Eranian <eranian@google.com>
Subject: Re: [PATCH v2 5/6] perf cpumap: Add intersect function.
Date: Fri, 1 Apr 2022 16:12:36 -0300	[thread overview]
Message-ID: <YkdOpJDnknrOPq2t@kernel.org> (raw)
In-Reply-To: <20220328232648.2127340-6-irogers@google.com>

Em Mon, Mar 28, 2022 at 04:26:47PM -0700, Ian Rogers escreveu:
> The merge function gives the union of two cpu maps. Add an intersect
> function which will be used in the next change.

So I really don't think intersect() shouldn't modify the contents of any
of its arguments, at most return one of them with a bumped refcount, as
an optimization.

The merge() operation is different in the sense that one expects that
one of the operands will be inserted into the other, and even then it
would be better to have a clearer semantic, i.e. merge(a, b) should mean
get the contents of b and insert into a.

Since we're talking about CPUs, it doesn't make sense to have a CPU
multiple times in the cpu_map, so we eliminate duplicates while doing
it.

Also perhaps the merge() operation should not even change any of the
operands, but instead return a new cpuset if one of the operands isn't
contained in the other, in which case a bump in the reference count of
the superset would be a valid optimization.

But that boat has departed already, i.e. perf_cpu_map__merge() is
already an exported libperf API, sigh.

This is something we're exporting, so I think this warrants further
discussion, even with a fix depending on the merge of this new API.

- Arnaldo

> Signed-off-by: Ian Rogers <irogers@google.com>
> ---
>  tools/lib/perf/cpumap.c              | 38 ++++++++++++++++++++++++++++
>  tools/lib/perf/include/perf/cpumap.h |  2 ++
>  2 files changed, 40 insertions(+)
> 
> diff --git a/tools/lib/perf/cpumap.c b/tools/lib/perf/cpumap.c
> index 384d5e076ee4..60cccd05f243 100644
> --- a/tools/lib/perf/cpumap.c
> +++ b/tools/lib/perf/cpumap.c
> @@ -390,3 +390,41 @@ struct perf_cpu_map *perf_cpu_map__merge(struct perf_cpu_map *orig,
>  	perf_cpu_map__put(orig);
>  	return merged;
>  }
> +
> +struct perf_cpu_map *perf_cpu_map__intersect(struct perf_cpu_map *orig,
> +					     struct perf_cpu_map *other)
> +{
> +	struct perf_cpu *tmp_cpus;
> +	int tmp_len;
> +	int i, j, k;
> +	struct perf_cpu_map *merged = NULL;
> +
> +	if (perf_cpu_map__is_subset(other, orig))
> +		return orig;
> +	if (perf_cpu_map__is_subset(orig, other)) {
> +		perf_cpu_map__put(orig);
> +		return perf_cpu_map__get(other);
> +	}
> +
> +	tmp_len = max(orig->nr, other->nr);
> +	tmp_cpus = malloc(tmp_len * sizeof(struct perf_cpu));
> +	if (!tmp_cpus)
> +		return NULL;
> +
> +	i = j = k = 0;
> +	while (i < orig->nr && j < other->nr) {
> +		if (orig->map[i].cpu < other->map[j].cpu)
> +			i++;
> +		else if (orig->map[i].cpu > other->map[j].cpu)
> +			j++;
> +		else {
> +			j++;
> +			tmp_cpus[k++] = orig->map[i++];
> +		}
> +	}
> +	if (k)
> +		merged = cpu_map__trim_new(k, tmp_cpus);
> +	free(tmp_cpus);
> +	perf_cpu_map__put(orig);
> +	return merged;
> +}
> diff --git a/tools/lib/perf/include/perf/cpumap.h b/tools/lib/perf/include/perf/cpumap.h
> index 4a2edbdb5e2b..a2a7216c0b78 100644
> --- a/tools/lib/perf/include/perf/cpumap.h
> +++ b/tools/lib/perf/include/perf/cpumap.h
> @@ -19,6 +19,8 @@ LIBPERF_API struct perf_cpu_map *perf_cpu_map__read(FILE *file);
>  LIBPERF_API struct perf_cpu_map *perf_cpu_map__get(struct perf_cpu_map *map);
>  LIBPERF_API struct perf_cpu_map *perf_cpu_map__merge(struct perf_cpu_map *orig,
>  						     struct perf_cpu_map *other);
> +LIBPERF_API struct perf_cpu_map *perf_cpu_map__intersect(struct perf_cpu_map *orig,
> +							 struct perf_cpu_map *other);
>  LIBPERF_API void perf_cpu_map__put(struct perf_cpu_map *map);
>  LIBPERF_API struct perf_cpu perf_cpu_map__cpu(const struct perf_cpu_map *cpus, int idx);
>  LIBPERF_API int perf_cpu_map__nr(const struct perf_cpu_map *cpus);
> -- 
> 2.35.1.1021.g381101b075-goog

-- 

- Arnaldo