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