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#include "internal.h"
13
14void perf_cpu_map__set_nr(struct perf_cpu_map *map, int nr_cpus)
15{
16	RC_CHK_ACCESS(map)->nr = nr_cpus;
17}
18
19struct perf_cpu_map *perf_cpu_map__alloc(int nr_cpus)
20{
21	RC_STRUCT(perf_cpu_map) *cpus = malloc(sizeof(*cpus) + sizeof(struct perf_cpu) * nr_cpus);
22	struct perf_cpu_map *result;
23
24	if (ADD_RC_CHK(result, cpus)) {
25		cpus->nr = nr_cpus;
26		refcount_set(&cpus->refcnt, 1);
27	}
28	return result;
29}
30
31struct perf_cpu_map *perf_cpu_map__new_any_cpu(void)
32{
33	struct perf_cpu_map *cpus = perf_cpu_map__alloc(1);
34
35	if (cpus)
36		RC_CHK_ACCESS(cpus)->map[0].cpu = -1;
37
38	return cpus;
39}
40
41static void cpu_map__delete(struct perf_cpu_map *map)
42{
43	if (map) {
44		WARN_ONCE(refcount_read(perf_cpu_map__refcnt(map)) != 0,
45			  "cpu_map refcnt unbalanced\n");
46		RC_CHK_FREE(map);
47	}
48}
49
50struct perf_cpu_map *perf_cpu_map__get(struct perf_cpu_map *map)
51{
52	struct perf_cpu_map *result;
53
54	if (RC_CHK_GET(result, map))
55		refcount_inc(perf_cpu_map__refcnt(map));
56
57	return result;
58}
59
60void perf_cpu_map__put(struct perf_cpu_map *map)
61{
62	if (map) {
63		if (refcount_dec_and_test(perf_cpu_map__refcnt(map)))
64			cpu_map__delete(map);
65		else
66			RC_CHK_PUT(map);
67	}
68}
69
70static struct perf_cpu_map *cpu_map__new_sysconf(void)
71{
72	struct perf_cpu_map *cpus;
73	int nr_cpus, nr_cpus_conf;
74
75	nr_cpus = sysconf(_SC_NPROCESSORS_ONLN);
76	if (nr_cpus < 0)
77		return NULL;
78
79	nr_cpus_conf = sysconf(_SC_NPROCESSORS_CONF);
80	if (nr_cpus != nr_cpus_conf) {
81		pr_warning("Number of online CPUs (%d) differs from the number configured (%d) the CPU map will only cover the first %d CPUs.",
82			nr_cpus, nr_cpus_conf, nr_cpus);
83	}
84
85	cpus = perf_cpu_map__alloc(nr_cpus);
86	if (cpus != NULL) {
87		int i;
88
89		for (i = 0; i < nr_cpus; ++i)
90			RC_CHK_ACCESS(cpus)->map[i].cpu = i;
91	}
92
93	return cpus;
94}
95
96static struct perf_cpu_map *cpu_map__new_sysfs_online(void)
97{
98	struct perf_cpu_map *cpus = NULL;
99	FILE *onlnf;
100
101	onlnf = fopen("/sys/devices/system/cpu/online", "r");
102	if (onlnf) {
103		cpus = perf_cpu_map__read(onlnf);
104		fclose(onlnf);
105	}
106	return cpus;
107}
108
109struct perf_cpu_map *perf_cpu_map__new_online_cpus(void)
110{
111	struct perf_cpu_map *cpus = cpu_map__new_sysfs_online();
112
113	if (cpus)
114		return cpus;
115
116	return cpu_map__new_sysconf();
117}
118
119
120static int cmp_cpu(const void *a, const void *b)
121{
122	const struct perf_cpu *cpu_a = a, *cpu_b = b;
123
124	return cpu_a->cpu - cpu_b->cpu;
125}
126
127static struct perf_cpu __perf_cpu_map__cpu(const struct perf_cpu_map *cpus, int idx)
128{
129	return RC_CHK_ACCESS(cpus)->map[idx];
130}
131
132static struct perf_cpu_map *cpu_map__trim_new(int nr_cpus, const struct perf_cpu *tmp_cpus)
133{
134	size_t payload_size = nr_cpus * sizeof(struct perf_cpu);
135	struct perf_cpu_map *cpus = perf_cpu_map__alloc(nr_cpus);
136	int i, j;
137
138	if (cpus != NULL) {
139		memcpy(RC_CHK_ACCESS(cpus)->map, tmp_cpus, payload_size);
140		qsort(RC_CHK_ACCESS(cpus)->map, nr_cpus, sizeof(struct perf_cpu), cmp_cpu);
141		/* Remove dups */
142		j = 0;
143		for (i = 0; i < nr_cpus; i++) {
144			if (i == 0 ||
145			    __perf_cpu_map__cpu(cpus, i).cpu !=
146			    __perf_cpu_map__cpu(cpus, i - 1).cpu) {
147				RC_CHK_ACCESS(cpus)->map[j++].cpu =
148					__perf_cpu_map__cpu(cpus, i).cpu;
149			}
150		}
151		perf_cpu_map__set_nr(cpus, j);
152		assert(j <= nr_cpus);
153	}
154	return cpus;
155}
156
157struct perf_cpu_map *perf_cpu_map__read(FILE *file)
158{
159	struct perf_cpu_map *cpus = NULL;
160	int nr_cpus = 0;
161	struct perf_cpu *tmp_cpus = NULL, *tmp;
162	int max_entries = 0;
163	int n, cpu, prev;
164	char sep;
165
166	sep = 0;
167	prev = -1;
168	for (;;) {
169		n = fscanf(file, "%u%c", &cpu, &sep);
170		if (n <= 0)
171			break;
172		if (prev >= 0) {
173			int new_max = nr_cpus + cpu - prev - 1;
174
175			WARN_ONCE(new_max >= MAX_NR_CPUS, "Perf can support %d CPUs. "
176							  "Consider raising MAX_NR_CPUS\n", MAX_NR_CPUS);
177
178			if (new_max >= max_entries) {
179				max_entries = new_max + MAX_NR_CPUS / 2;
180				tmp = realloc(tmp_cpus, max_entries * sizeof(struct perf_cpu));
181				if (tmp == NULL)
182					goto out_free_tmp;
183				tmp_cpus = tmp;
184			}
185
186			while (++prev < cpu)
187				tmp_cpus[nr_cpus++].cpu = prev;
188		}
189		if (nr_cpus == max_entries) {
190			max_entries += MAX_NR_CPUS;
191			tmp = realloc(tmp_cpus, max_entries * sizeof(struct perf_cpu));
192			if (tmp == NULL)
193				goto out_free_tmp;
194			tmp_cpus = tmp;
195		}
196
197		tmp_cpus[nr_cpus++].cpu = cpu;
198		if (n == 2 && sep == '-')
199			prev = cpu;
200		else
201			prev = -1;
202		if (n == 1 || sep == '\n')
203			break;
204	}
205
206	if (nr_cpus > 0)
207		cpus = cpu_map__trim_new(nr_cpus, tmp_cpus);
208out_free_tmp:
209	free(tmp_cpus);
210	return cpus;
211}
212
213struct perf_cpu_map *perf_cpu_map__new(const char *cpu_list)
214{
215	struct perf_cpu_map *cpus = NULL;
216	unsigned long start_cpu, end_cpu = 0;
217	char *p = NULL;
218	int i, nr_cpus = 0;
219	struct perf_cpu *tmp_cpus = NULL, *tmp;
220	int max_entries = 0;
221
222	if (!cpu_list)
223		return perf_cpu_map__new_online_cpus();
224
225	/*
226	 * must handle the case of empty cpumap to cover
227	 * TOPOLOGY header for NUMA nodes with no CPU
228	 * ( e.g., because of CPU hotplug)
229	 */
230	if (!isdigit(*cpu_list) && *cpu_list != '\0')
231		goto out;
232
233	while (isdigit(*cpu_list)) {
234		p = NULL;
235		start_cpu = strtoul(cpu_list, &p, 0);
236		if (start_cpu >= INT_MAX
237		    || (*p != '\0' && *p != ',' && *p != '-'))
238			goto invalid;
239
240		if (*p == '-') {
241			cpu_list = ++p;
242			p = NULL;
243			end_cpu = strtoul(cpu_list, &p, 0);
244
245			if (end_cpu >= INT_MAX || (*p != '\0' && *p != ','))
246				goto invalid;
247
248			if (end_cpu < start_cpu)
249				goto invalid;
250		} else {
251			end_cpu = start_cpu;
252		}
253
254		WARN_ONCE(end_cpu >= MAX_NR_CPUS, "Perf can support %d CPUs. "
255						  "Consider raising MAX_NR_CPUS\n", MAX_NR_CPUS);
256
257		for (; start_cpu <= end_cpu; start_cpu++) {
258			/* check for duplicates */
259			for (i = 0; i < nr_cpus; i++)
260				if (tmp_cpus[i].cpu == (int)start_cpu)
261					goto invalid;
262
263			if (nr_cpus == max_entries) {
264				max_entries += MAX_NR_CPUS;
265				tmp = realloc(tmp_cpus, max_entries * sizeof(struct perf_cpu));
266				if (tmp == NULL)
267					goto invalid;
268				tmp_cpus = tmp;
269			}
270			tmp_cpus[nr_cpus++].cpu = (int)start_cpu;
271		}
272		if (*p)
273			++p;
274
275		cpu_list = p;
276	}
277
278	if (nr_cpus > 0)
279		cpus = cpu_map__trim_new(nr_cpus, tmp_cpus);
280	else if (*cpu_list != '\0') {
281		pr_warning("Unexpected characters at end of cpu list ('%s'), using online CPUs.",
282			   cpu_list);
283		cpus = perf_cpu_map__new_online_cpus();
284	} else
285		cpus = perf_cpu_map__new_any_cpu();
286invalid:
287	free(tmp_cpus);
288out:
289	return cpus;
290}
291
292static int __perf_cpu_map__nr(const struct perf_cpu_map *cpus)
293{
294	return RC_CHK_ACCESS(cpus)->nr;
295}
296
297struct perf_cpu perf_cpu_map__cpu(const struct perf_cpu_map *cpus, int idx)
298{
299	struct perf_cpu result = {
300		.cpu = -1
301	};
302
303	if (cpus && idx < __perf_cpu_map__nr(cpus))
304		return __perf_cpu_map__cpu(cpus, idx);
305
306	return result;
307}
308
309int perf_cpu_map__nr(const struct perf_cpu_map *cpus)
310{
311	return cpus ? __perf_cpu_map__nr(cpus) : 1;
312}
313
314bool perf_cpu_map__has_any_cpu_or_is_empty(const struct perf_cpu_map *map)
315{
316	return map ? __perf_cpu_map__cpu(map, 0).cpu == -1 : true;
317}
318
319int perf_cpu_map__idx(const struct perf_cpu_map *cpus, struct perf_cpu cpu)
320{
321	int low, high;
322
323	if (!cpus)
324		return -1;
325
326	low = 0;
327	high = __perf_cpu_map__nr(cpus);
328	while (low < high) {
329		int idx = (low + high) / 2;
330		struct perf_cpu cpu_at_idx = __perf_cpu_map__cpu(cpus, idx);
331
332		if (cpu_at_idx.cpu == cpu.cpu)
333			return idx;
334
335		if (cpu_at_idx.cpu > cpu.cpu)
336			high = idx;
337		else
338			low = idx + 1;
339	}
340
341	return -1;
342}
343
344bool perf_cpu_map__has(const struct perf_cpu_map *cpus, struct perf_cpu cpu)
345{
346	return perf_cpu_map__idx(cpus, cpu) != -1;
347}
348
349bool perf_cpu_map__equal(const struct perf_cpu_map *lhs, const struct perf_cpu_map *rhs)
350{
351	int nr;
352
353	if (lhs == rhs)
354		return true;
355
356	if (!lhs || !rhs)
357		return false;
358
359	nr = __perf_cpu_map__nr(lhs);
360	if (nr != __perf_cpu_map__nr(rhs))
361		return false;
362
363	for (int idx = 0; idx < nr; idx++) {
364		if (__perf_cpu_map__cpu(lhs, idx).cpu != __perf_cpu_map__cpu(rhs, idx).cpu)
365			return false;
366	}
367	return true;
368}
369
370bool perf_cpu_map__has_any_cpu(const struct perf_cpu_map *map)
371{
372	return map && __perf_cpu_map__cpu(map, 0).cpu == -1;
373}
374
375struct perf_cpu perf_cpu_map__max(const struct perf_cpu_map *map)
376{
377	struct perf_cpu result = {
378		.cpu = -1
379	};
380
381	// cpu_map__trim_new() qsort()s it, cpu_map__default_new() sorts it as well.
382	return __perf_cpu_map__nr(map) > 0
383		? __perf_cpu_map__cpu(map, __perf_cpu_map__nr(map) - 1)
384		: result;
385}
386
387/** Is 'b' a subset of 'a'. */
388bool perf_cpu_map__is_subset(const struct perf_cpu_map *a, const struct perf_cpu_map *b)
389{
390	if (a == b || !b)
391		return true;
392	if (!a || __perf_cpu_map__nr(b) > __perf_cpu_map__nr(a))
393		return false;
394
395	for (int i = 0, j = 0; i < __perf_cpu_map__nr(a); i++) {
396		if (__perf_cpu_map__cpu(a, i).cpu > __perf_cpu_map__cpu(b, j).cpu)
397			return false;
398		if (__perf_cpu_map__cpu(a, i).cpu == __perf_cpu_map__cpu(b, j).cpu) {
399			j++;
400			if (j == __perf_cpu_map__nr(b))
401				return true;
402		}
403	}
404	return false;
405}
406
407/*
408 * Merge two cpumaps
409 *
410 * orig either gets freed and replaced with a new map, or reused
411 * with no reference count change (similar to "realloc")
412 * other has its reference count increased.
413 */
414
415struct perf_cpu_map *perf_cpu_map__merge(struct perf_cpu_map *orig,
416					 struct perf_cpu_map *other)
417{
418	struct perf_cpu *tmp_cpus;
419	int tmp_len;
420	int i, j, k;
421	struct perf_cpu_map *merged;
422
423	if (perf_cpu_map__is_subset(orig, other))
424		return orig;
425	if (perf_cpu_map__is_subset(other, orig)) {
426		perf_cpu_map__put(orig);
427		return perf_cpu_map__get(other);
428	}
429
430	tmp_len = __perf_cpu_map__nr(orig) + __perf_cpu_map__nr(other);
431	tmp_cpus = malloc(tmp_len * sizeof(struct perf_cpu));
432	if (!tmp_cpus)
433		return NULL;
434
435	/* Standard merge algorithm from wikipedia */
436	i = j = k = 0;
437	while (i < __perf_cpu_map__nr(orig) && j < __perf_cpu_map__nr(other)) {
438		if (__perf_cpu_map__cpu(orig, i).cpu <= __perf_cpu_map__cpu(other, j).cpu) {
439			if (__perf_cpu_map__cpu(orig, i).cpu == __perf_cpu_map__cpu(other, j).cpu)
440				j++;
441			tmp_cpus[k++] = __perf_cpu_map__cpu(orig, i++);
442		} else
443			tmp_cpus[k++] = __perf_cpu_map__cpu(other, j++);
444	}
445
446	while (i < __perf_cpu_map__nr(orig))
447		tmp_cpus[k++] = __perf_cpu_map__cpu(orig, i++);
448
449	while (j < __perf_cpu_map__nr(other))
450		tmp_cpus[k++] = __perf_cpu_map__cpu(other, j++);
451	assert(k <= tmp_len);
452
453	merged = cpu_map__trim_new(k, tmp_cpus);
454	free(tmp_cpus);
455	perf_cpu_map__put(orig);
456	return merged;
457}
458
459struct perf_cpu_map *perf_cpu_map__intersect(struct perf_cpu_map *orig,
460					     struct perf_cpu_map *other)
461{
462	struct perf_cpu *tmp_cpus;
463	int tmp_len;
464	int i, j, k;
465	struct perf_cpu_map *merged = NULL;
466
467	if (perf_cpu_map__is_subset(other, orig))
468		return perf_cpu_map__get(orig);
469	if (perf_cpu_map__is_subset(orig, other))
470		return perf_cpu_map__get(other);
471
472	tmp_len = max(__perf_cpu_map__nr(orig), __perf_cpu_map__nr(other));
473	tmp_cpus = malloc(tmp_len * sizeof(struct perf_cpu));
474	if (!tmp_cpus)
475		return NULL;
476
477	i = j = k = 0;
478	while (i < __perf_cpu_map__nr(orig) && j < __perf_cpu_map__nr(other)) {
479		if (__perf_cpu_map__cpu(orig, i).cpu < __perf_cpu_map__cpu(other, j).cpu)
480			i++;
481		else if (__perf_cpu_map__cpu(orig, i).cpu > __perf_cpu_map__cpu(other, j).cpu)
482			j++;
483		else {
484			j++;
485			tmp_cpus[k++] = __perf_cpu_map__cpu(orig, i++);
486		}
487	}
488	if (k)
489		merged = cpu_map__trim_new(k, tmp_cpus);
490	free(tmp_cpus);
491	return merged;
492}
493