1// SPDX-License-Identifier: GPL-2.0-only
  2#include <perf/cpumap.h>
  3#include <stdlib.h>
  4#include <linux/refcount.h>
  5#include <internal/cpumap.h>
  6#include <asm/bug.h>
  7#include <stdio.h>
  8#include <string.h>
  9#include <unistd.h>
 10#include <ctype.h>
 11#include <limits.h>
 12
 13static struct perf_cpu_map *perf_cpu_map__alloc(int nr_cpus)
 14{
 15	struct perf_cpu_map *cpus = malloc(sizeof(*cpus) + sizeof(struct perf_cpu) * nr_cpus);
 16
 17	if (cpus != NULL) {
 18		cpus->nr = nr_cpus;
 19		refcount_set(&cpus->refcnt, 1);
 20
 21	}
 22	return cpus;
 23}
 24
 25struct perf_cpu_map *perf_cpu_map__dummy_new(void)
 26{
 27	struct perf_cpu_map *cpus = perf_cpu_map__alloc(1);
 28
 29	if (cpus)
 30		cpus->map[0].cpu = -1;
 31
 32	return cpus;
 33}
 34
 35static void cpu_map__delete(struct perf_cpu_map *map)
 36{
 37	if (map) {
 38		WARN_ONCE(refcount_read(&map->refcnt) != 0,
 39			  "cpu_map refcnt unbalanced\n");
 40		free(map);
 41	}
 42}
 43
 44struct perf_cpu_map *perf_cpu_map__get(struct perf_cpu_map *map)
 45{
 46	if (map)
 47		refcount_inc(&map->refcnt);
 48	return map;
 49}
 50
 51void perf_cpu_map__put(struct perf_cpu_map *map)
 52{
 53	if (map && refcount_dec_and_test(&map->refcnt))
 54		cpu_map__delete(map);
 55}
 56
 57static struct perf_cpu_map *cpu_map__default_new(void)
 58{
 59	struct perf_cpu_map *cpus;
 60	int nr_cpus;
 61
 62	nr_cpus = sysconf(_SC_NPROCESSORS_ONLN);
 63	if (nr_cpus < 0)
 64		return NULL;
 65
 66	cpus = perf_cpu_map__alloc(nr_cpus);
 67	if (cpus != NULL) {
 68		int i;
 69
 70		for (i = 0; i < nr_cpus; ++i)
 71			cpus->map[i].cpu = i;
 72	}
 73
 74	return cpus;
 75}
 76
 77struct perf_cpu_map *perf_cpu_map__default_new(void)
 78{
 79	return cpu_map__default_new();
 80}
 81
 82
 83static int cmp_cpu(const void *a, const void *b)
 84{
 85	const struct perf_cpu *cpu_a = a, *cpu_b = b;
 86
 87	return cpu_a->cpu - cpu_b->cpu;
 88}
 89
 90static struct perf_cpu_map *cpu_map__trim_new(int nr_cpus, const struct perf_cpu *tmp_cpus)
 91{
 92	size_t payload_size = nr_cpus * sizeof(struct perf_cpu);
 93	struct perf_cpu_map *cpus = perf_cpu_map__alloc(nr_cpus);
 94	int i, j;
 95
 96	if (cpus != NULL) {
 97		memcpy(cpus->map, tmp_cpus, payload_size);
 98		qsort(cpus->map, nr_cpus, sizeof(struct perf_cpu), cmp_cpu);
 99		/* Remove dups */
100		j = 0;
101		for (i = 0; i < nr_cpus; i++) {
102			if (i == 0 || cpus->map[i].cpu != cpus->map[i - 1].cpu)
103				cpus->map[j++].cpu = cpus->map[i].cpu;
104		}
105		cpus->nr = j;
106		assert(j <= nr_cpus);
107	}
108	return cpus;
109}
110
111struct perf_cpu_map *perf_cpu_map__read(FILE *file)
112{
113	struct perf_cpu_map *cpus = NULL;
114	int nr_cpus = 0;
115	struct perf_cpu *tmp_cpus = NULL, *tmp;
116	int max_entries = 0;
117	int n, cpu, prev;
118	char sep;
119
120	sep = 0;
121	prev = -1;
122	for (;;) {
123		n = fscanf(file, "%u%c", &cpu, &sep);
124		if (n <= 0)
125			break;
126		if (prev >= 0) {
127			int new_max = nr_cpus + cpu - prev - 1;
128
129			WARN_ONCE(new_max >= MAX_NR_CPUS, "Perf can support %d CPUs. "
130							  "Consider raising MAX_NR_CPUS\n", MAX_NR_CPUS);
131
132			if (new_max >= max_entries) {
133				max_entries = new_max + MAX_NR_CPUS / 2;
134				tmp = realloc(tmp_cpus, max_entries * sizeof(struct perf_cpu));
135				if (tmp == NULL)
136					goto out_free_tmp;
137				tmp_cpus = tmp;
138			}
139
140			while (++prev < cpu)
141				tmp_cpus[nr_cpus++].cpu = prev;
142		}
143		if (nr_cpus == max_entries) {
144			max_entries += MAX_NR_CPUS;
145			tmp = realloc(tmp_cpus, max_entries * sizeof(struct perf_cpu));
146			if (tmp == NULL)
147				goto out_free_tmp;
148			tmp_cpus = tmp;
149		}
150
151		tmp_cpus[nr_cpus++].cpu = cpu;
152		if (n == 2 && sep == '-')
153			prev = cpu;
154		else
155			prev = -1;
156		if (n == 1 || sep == '\n')
157			break;
158	}
159
160	if (nr_cpus > 0)
161		cpus = cpu_map__trim_new(nr_cpus, tmp_cpus);
162	else
163		cpus = cpu_map__default_new();
164out_free_tmp:
165	free(tmp_cpus);
166	return cpus;
167}
168
169static struct perf_cpu_map *cpu_map__read_all_cpu_map(void)
170{
171	struct perf_cpu_map *cpus = NULL;
172	FILE *onlnf;
173
174	onlnf = fopen("/sys/devices/system/cpu/online", "r");
175	if (!onlnf)
176		return cpu_map__default_new();
177
178	cpus = perf_cpu_map__read(onlnf);
179	fclose(onlnf);
180	return cpus;
181}
182
183struct perf_cpu_map *perf_cpu_map__new(const char *cpu_list)
184{
185	struct perf_cpu_map *cpus = NULL;
186	unsigned long start_cpu, end_cpu = 0;
187	char *p = NULL;
188	int i, nr_cpus = 0;
189	struct perf_cpu *tmp_cpus = NULL, *tmp;
190	int max_entries = 0;
191
192	if (!cpu_list)
193		return cpu_map__read_all_cpu_map();
194
195	/*
196	 * must handle the case of empty cpumap to cover
197	 * TOPOLOGY header for NUMA nodes with no CPU
198	 * ( e.g., because of CPU hotplug)
199	 */
200	if (!isdigit(*cpu_list) && *cpu_list != '\0')
201		goto out;
202
203	while (isdigit(*cpu_list)) {
204		p = NULL;
205		start_cpu = strtoul(cpu_list, &p, 0);
206		if (start_cpu >= INT_MAX
207		    || (*p != '\0' && *p != ',' && *p != '-'))
208			goto invalid;
209
210		if (*p == '-') {
211			cpu_list = ++p;
212			p = NULL;
213			end_cpu = strtoul(cpu_list, &p, 0);
214
215			if (end_cpu >= INT_MAX || (*p != '\0' && *p != ','))
216				goto invalid;
217
218			if (end_cpu < start_cpu)
219				goto invalid;
220		} else {
221			end_cpu = start_cpu;
222		}
223
224		WARN_ONCE(end_cpu >= MAX_NR_CPUS, "Perf can support %d CPUs. "
225						  "Consider raising MAX_NR_CPUS\n", MAX_NR_CPUS);
226
227		for (; start_cpu <= end_cpu; start_cpu++) {
228			/* check for duplicates */
229			for (i = 0; i < nr_cpus; i++)
230				if (tmp_cpus[i].cpu == (int)start_cpu)
231					goto invalid;
232
233			if (nr_cpus == max_entries) {
234				max_entries += MAX_NR_CPUS;
235				tmp = realloc(tmp_cpus, max_entries * sizeof(struct perf_cpu));
236				if (tmp == NULL)
237					goto invalid;
238				tmp_cpus = tmp;
239			}
240			tmp_cpus[nr_cpus++].cpu = (int)start_cpu;
241		}
242		if (*p)
243			++p;
244
245		cpu_list = p;
246	}
247
248	if (nr_cpus > 0)
249		cpus = cpu_map__trim_new(nr_cpus, tmp_cpus);
250	else if (*cpu_list != '\0')
251		cpus = cpu_map__default_new();
252	else
253		cpus = perf_cpu_map__dummy_new();
254invalid:
255	free(tmp_cpus);
256out:
257	return cpus;
258}
259
260struct perf_cpu perf_cpu_map__cpu(const struct perf_cpu_map *cpus, int idx)
261{
262	struct perf_cpu result = {
263		.cpu = -1
264	};
265
266	if (cpus && idx < cpus->nr)
267		return cpus->map[idx];
268
269	return result;
270}
271
272int perf_cpu_map__nr(const struct perf_cpu_map *cpus)
273{
274	return cpus ? cpus->nr : 1;
275}
276
277bool perf_cpu_map__empty(const struct perf_cpu_map *map)
278{
279	return map ? map->map[0].cpu == -1 : true;
280}
281
282int perf_cpu_map__idx(const struct perf_cpu_map *cpus, struct perf_cpu cpu)
283{
284	int low, high;
285
286	if (!cpus)
287		return -1;
288
289	low = 0;
290	high = cpus->nr;
291	while (low < high) {
292		int idx = (low + high) / 2;
293		struct perf_cpu cpu_at_idx = cpus->map[idx];
294
295		if (cpu_at_idx.cpu == cpu.cpu)
296			return idx;
297
298		if (cpu_at_idx.cpu > cpu.cpu)
299			high = idx;
300		else
301			low = idx + 1;
302	}
303
304	return -1;
305}
306
307bool perf_cpu_map__has(const struct perf_cpu_map *cpus, struct perf_cpu cpu)
308{
309	return perf_cpu_map__idx(cpus, cpu) != -1;
310}
311
312struct perf_cpu perf_cpu_map__max(const struct perf_cpu_map *map)
313{
314	struct perf_cpu result = {
315		.cpu = -1
316	};
317
318	// cpu_map__trim_new() qsort()s it, cpu_map__default_new() sorts it as well.
319	return map->nr > 0 ? map->map[map->nr - 1] : result;
320}
321
322/** Is 'b' a subset of 'a'. */
323bool perf_cpu_map__is_subset(const struct perf_cpu_map *a, const struct perf_cpu_map *b)
324{
325	if (a == b || !b)
326		return true;
327	if (!a || b->nr > a->nr)
328		return false;
329
330	for (int i = 0, j = 0; i < a->nr; i++) {
331		if (a->map[i].cpu > b->map[j].cpu)
332			return false;
333		if (a->map[i].cpu == b->map[j].cpu) {
334			j++;
335			if (j == b->nr)
336				return true;
337		}
338	}
339	return false;
340}
341
342/*
343 * Merge two cpumaps
344 *
345 * orig either gets freed and replaced with a new map, or reused
346 * with no reference count change (similar to "realloc")
347 * other has its reference count increased.
348 */
349
350struct perf_cpu_map *perf_cpu_map__merge(struct perf_cpu_map *orig,
351					 struct perf_cpu_map *other)
352{
353	struct perf_cpu *tmp_cpus;
354	int tmp_len;
355	int i, j, k;
356	struct perf_cpu_map *merged;
357
358	if (perf_cpu_map__is_subset(orig, other))
359		return orig;
360	if (perf_cpu_map__is_subset(other, orig)) {
361		perf_cpu_map__put(orig);
362		return perf_cpu_map__get(other);
363	}
364
365	tmp_len = orig->nr + other->nr;
366	tmp_cpus = malloc(tmp_len * sizeof(struct perf_cpu));
367	if (!tmp_cpus)
368		return NULL;
369
370	/* Standard merge algorithm from wikipedia */
371	i = j = k = 0;
372	while (i < orig->nr && j < other->nr) {
373		if (orig->map[i].cpu <= other->map[j].cpu) {
374			if (orig->map[i].cpu == other->map[j].cpu)
375				j++;
376			tmp_cpus[k++] = orig->map[i++];
377		} else
378			tmp_cpus[k++] = other->map[j++];
379	}
380
381	while (i < orig->nr)
382		tmp_cpus[k++] = orig->map[i++];
383
384	while (j < other->nr)
385		tmp_cpus[k++] = other->map[j++];
386	assert(k <= tmp_len);
387
388	merged = cpu_map__trim_new(k, tmp_cpus);
389	free(tmp_cpus);
390	perf_cpu_map__put(orig);
391	return merged;
392}