lib/perf/cpumap.c

0001 // SPDX-License-Identifier: GPL-2.0-only
0002 #include <perf/cpumap.h>
0003 #include <stdlib.h>
0004 #include <linux/refcount.h>
0005 #include <internal/cpumap.h>
0006 #include <asm/bug.h>
0007 #include <stdio.h>
0008 #include <string.h>
0009 #include <unistd.h>
0010 #include <ctype.h>
0011 #include <limits.h>
0012
0013 static struct perf_cpu_map *perf_cpu_map__alloc(int nr_cpus)
0014 {
0015     struct perf_cpu_map *cpus = malloc(sizeof(*cpus) + sizeof(struct perf_cpu) * nr_cpus);
0016
0017     if (cpus != NULL) {
0018         cpus->nr = nr_cpus;
0019         refcount_set(&cpus->refcnt, 1);
0020
0021     }
0022     return cpus;
0023 }
0024
0025 struct perf_cpu_map *perf_cpu_map__dummy_new(void)
0026 {
0027     struct perf_cpu_map *cpus = perf_cpu_map__alloc(1);
0028
0029     if (cpus)
0030         cpus->map[0].cpu = -1;
0031
0032     return cpus;
0033 }
0034
0035 static void cpu_map__delete(struct perf_cpu_map *map)
0036 {
0037     if (map) {
0038         WARN_ONCE(refcount_read(&map->refcnt) != 0,
0039               "cpu_map refcnt unbalanced\n");
0040         free(map);
0041     }
0042 }
0043
0044 struct perf_cpu_map *perf_cpu_map__get(struct perf_cpu_map *map)
0045 {
0046     if (map)
0047         refcount_inc(&map->refcnt);
0048     return map;
0049 }
0050
0051 void perf_cpu_map__put(struct perf_cpu_map *map)
0052 {
0053     if (map && refcount_dec_and_test(&map->refcnt))
0054         cpu_map__delete(map);
0055 }
0056
0057 static struct perf_cpu_map *cpu_map__default_new(void)
0058 {
0059     struct perf_cpu_map *cpus;
0060     int nr_cpus;
0061
0062     nr_cpus = sysconf(_SC_NPROCESSORS_ONLN);
0063     if (nr_cpus < 0)
0064         return NULL;
0065
0066     cpus = perf_cpu_map__alloc(nr_cpus);
0067     if (cpus != NULL) {
0068         int i;
0069
0070         for (i = 0; i < nr_cpus; ++i)
0071             cpus->map[i].cpu = i;
0072     }
0073
0074     return cpus;
0075 }
0076
0077 struct perf_cpu_map *perf_cpu_map__default_new(void)
0078 {
0079     return cpu_map__default_new();
0080 }
0081
0082
0083 static int cmp_cpu(const void *a, const void *b)
0084 {
0085     const struct perf_cpu *cpu_a = a, *cpu_b = b;
0086
0087     return cpu_a->cpu - cpu_b->cpu;
0088 }
0089
0090 static struct perf_cpu_map *cpu_map__trim_new(int nr_cpus, const struct perf_cpu *tmp_cpus)
0091 {
0092     size_t payload_size = nr_cpus * sizeof(struct perf_cpu);
0093     struct perf_cpu_map *cpus = perf_cpu_map__alloc(nr_cpus);
0094     int i, j;
0095
0096     if (cpus != NULL) {
0097         memcpy(cpus->map, tmp_cpus, payload_size);
0098         qsort(cpus->map, nr_cpus, sizeof(struct perf_cpu), cmp_cpu);
0099         /* Remove dups */
0100         j = 0;
0101         for (i = 0; i < nr_cpus; i++) {
0102             if (i == 0 || cpus->map[i].cpu != cpus->map[i - 1].cpu)
0103                 cpus->map[j++].cpu = cpus->map[i].cpu;
0104         }
0105         cpus->nr = j;
0106         assert(j <= nr_cpus);
0107     }
0108     return cpus;
0109 }
0110
0111 struct perf_cpu_map *perf_cpu_map__read(FILE *file)
0112 {
0113     struct perf_cpu_map *cpus = NULL;
0114     int nr_cpus = 0;
0115     struct perf_cpu *tmp_cpus = NULL, *tmp;
0116     int max_entries = 0;
0117     int n, cpu, prev;
0118     char sep;
0119
0120     sep = 0;
0121     prev = -1;
0122     for (;;) {
0123         n = fscanf(file, "%u%c", &cpu, &sep);
0124         if (n <= 0)
0125             break;
0126         if (prev >= 0) {
0127             int new_max = nr_cpus + cpu - prev - 1;
0128
0129             WARN_ONCE(new_max >= MAX_NR_CPUS, "Perf can support %d CPUs. "
0130                               "Consider raising MAX_NR_CPUS\n", MAX_NR_CPUS);
0131
0132             if (new_max >= max_entries) {
0133                 max_entries = new_max + MAX_NR_CPUS / 2;
0134                 tmp = realloc(tmp_cpus, max_entries * sizeof(struct perf_cpu));
0135                 if (tmp == NULL)
0136                     goto out_free_tmp;
0137                 tmp_cpus = tmp;
0138             }
0139
0140             while (++prev < cpu)
0141                 tmp_cpus[nr_cpus++].cpu = prev;
0142         }
0143         if (nr_cpus == max_entries) {
0144             max_entries += MAX_NR_CPUS;
0145             tmp = realloc(tmp_cpus, max_entries * sizeof(struct perf_cpu));
0146             if (tmp == NULL)
0147                 goto out_free_tmp;
0148             tmp_cpus = tmp;
0149         }
0150
0151         tmp_cpus[nr_cpus++].cpu = cpu;
0152         if (n == 2 && sep == '-')
0153             prev = cpu;
0154         else
0155             prev = -1;
0156         if (n == 1 || sep == '\n')
0157             break;
0158     }
0159
0160     if (nr_cpus > 0)
0161         cpus = cpu_map__trim_new(nr_cpus, tmp_cpus);
0162     else
0163         cpus = cpu_map__default_new();
0164 out_free_tmp:
0165     free(tmp_cpus);
0166     return cpus;
0167 }
0168
0169 static struct perf_cpu_map *cpu_map__read_all_cpu_map(void)
0170 {
0171     struct perf_cpu_map *cpus = NULL;
0172     FILE *onlnf;
0173
0174     onlnf = fopen("/sys/devices/system/cpu/online", "r");
0175     if (!onlnf)
0176         return cpu_map__default_new();
0177
0178     cpus = perf_cpu_map__read(onlnf);
0179     fclose(onlnf);
0180     return cpus;
0181 }
0182
0183 struct perf_cpu_map *perf_cpu_map__new(const char *cpu_list)
0184 {
0185     struct perf_cpu_map *cpus = NULL;
0186     unsigned long start_cpu, end_cpu = 0;
0187     char *p = NULL;
0188     int i, nr_cpus = 0;
0189     struct perf_cpu *tmp_cpus = NULL, *tmp;
0190     int max_entries = 0;
0191
0192     if (!cpu_list)
0193         return cpu_map__read_all_cpu_map();
0194
0195     /*
0196      * must handle the case of empty cpumap to cover
0197      * TOPOLOGY header for NUMA nodes with no CPU
0198      * ( e.g., because of CPU hotplug)
0199      */
0200     if (!isdigit(*cpu_list) && *cpu_list != '\0')
0201         goto out;
0202
0203     while (isdigit(*cpu_list)) {
0204         p = NULL;
0205         start_cpu = strtoul(cpu_list, &p, 0);
0206         if (start_cpu >= INT_MAX
0207             || (*p != '\0' && *p != ',' && *p != '-'))
0208             goto invalid;
0209
0210         if (*p == '-') {
0211             cpu_list = ++p;
0212             p = NULL;
0213             end_cpu = strtoul(cpu_list, &p, 0);
0214
0215             if (end_cpu >= INT_MAX || (*p != '\0' && *p != ','))
0216                 goto invalid;
0217
0218             if (end_cpu < start_cpu)
0219                 goto invalid;
0220         } else {
0221             end_cpu = start_cpu;
0222         }
0223
0224         WARN_ONCE(end_cpu >= MAX_NR_CPUS, "Perf can support %d CPUs. "
0225                           "Consider raising MAX_NR_CPUS\n", MAX_NR_CPUS);
0226
0227         for (; start_cpu <= end_cpu; start_cpu++) {
0228             /* check for duplicates */
0229             for (i = 0; i < nr_cpus; i++)
0230                 if (tmp_cpus[i].cpu == (int)start_cpu)
0231                     goto invalid;
0232
0233             if (nr_cpus == max_entries) {
0234                 max_entries += MAX_NR_CPUS;
0235                 tmp = realloc(tmp_cpus, max_entries * sizeof(struct perf_cpu));
0236                 if (tmp == NULL)
0237                     goto invalid;
0238                 tmp_cpus = tmp;
0239             }
0240             tmp_cpus[nr_cpus++].cpu = (int)start_cpu;
0241         }
0242         if (*p)
0243             ++p;
0244
0245         cpu_list = p;
0246     }
0247
0248     if (nr_cpus > 0)
0249         cpus = cpu_map__trim_new(nr_cpus, tmp_cpus);
0250     else if (*cpu_list != '\0')
0251         cpus = cpu_map__default_new();
0252     else
0253         cpus = perf_cpu_map__dummy_new();
0254 invalid:
0255     free(tmp_cpus);
0256 out:
0257     return cpus;
0258 }
0259
0260 struct perf_cpu perf_cpu_map__cpu(const struct perf_cpu_map *cpus, int idx)
0261 {
0262     struct perf_cpu result = {
0263         .cpu = -1
0264     };
0265
0266     if (cpus && idx < cpus->nr)
0267         return cpus->map[idx];
0268
0269     return result;
0270 }
0271
0272 int perf_cpu_map__nr(const struct perf_cpu_map *cpus)
0273 {
0274     return cpus ? cpus->nr : 1;
0275 }
0276
0277 bool perf_cpu_map__empty(const struct perf_cpu_map *map)
0278 {
0279     return map ? map->map[0].cpu == -1 : true;
0280 }
0281
0282 int perf_cpu_map__idx(const struct perf_cpu_map *cpus, struct perf_cpu cpu)
0283 {
0284     int low, high;
0285
0286     if (!cpus)
0287         return -1;
0288
0289     low = 0;
0290     high = cpus->nr;
0291     while (low < high) {
0292         int idx = (low + high) / 2;
0293         struct perf_cpu cpu_at_idx = cpus->map[idx];
0294
0295         if (cpu_at_idx.cpu == cpu.cpu)
0296             return idx;
0297
0298         if (cpu_at_idx.cpu > cpu.cpu)
0299             high = idx;
0300         else
0301             low = idx + 1;
0302     }
0303
0304     return -1;
0305 }
0306
0307 bool perf_cpu_map__has(const struct perf_cpu_map *cpus, struct perf_cpu cpu)
0308 {
0309     return perf_cpu_map__idx(cpus, cpu) != -1;
0310 }
0311
0312 struct perf_cpu perf_cpu_map__max(const struct perf_cpu_map *map)
0313 {
0314     struct perf_cpu result = {
0315         .cpu = -1
0316     };
0317
0318     // cpu_map__trim_new() qsort()s it, cpu_map__default_new() sorts it as well.
0319     return map->nr > 0 ? map->map[map->nr - 1] : result;
0320 }
0321
0322 /** Is 'b' a subset of 'a'. */
0323 bool perf_cpu_map__is_subset(const struct perf_cpu_map *a, const struct perf_cpu_map *b)
0324 {
0325     if (a == b || !b)
0326         return true;
0327     if (!a || b->nr > a->nr)
0328         return false;
0329
0330     for (int i = 0, j = 0; i < a->nr; i++) {
0331         if (a->map[i].cpu > b->map[j].cpu)
0332             return false;
0333         if (a->map[i].cpu == b->map[j].cpu) {
0334             j++;
0335             if (j == b->nr)
0336                 return true;
0337         }
0338     }
0339     return false;
0340 }
0341
0342 /*
0343  * Merge two cpumaps
0344  *
0345  * orig either gets freed and replaced with a new map, or reused
0346  * with no reference count change (similar to "realloc")
0347  * other has its reference count increased.
0348  */
0349
0350 struct perf_cpu_map *perf_cpu_map__merge(struct perf_cpu_map *orig,
0351                      struct perf_cpu_map *other)
0352 {
0353     struct perf_cpu *tmp_cpus;
0354     int tmp_len;
0355     int i, j, k;
0356     struct perf_cpu_map *merged;
0357
0358     if (perf_cpu_map__is_subset(orig, other))
0359         return orig;
0360     if (perf_cpu_map__is_subset(other, orig)) {
0361         perf_cpu_map__put(orig);
0362         return perf_cpu_map__get(other);
0363     }
0364
0365     tmp_len = orig->nr + other->nr;
0366     tmp_cpus = malloc(tmp_len * sizeof(struct perf_cpu));
0367     if (!tmp_cpus)
0368         return NULL;
0369
0370     /* Standard merge algorithm from wikipedia */
0371     i = j = k = 0;
0372     while (i < orig->nr && j < other->nr) {
0373         if (orig->map[i].cpu <= other->map[j].cpu) {
0374             if (orig->map[i].cpu == other->map[j].cpu)
0375                 j++;
0376             tmp_cpus[k++] = orig->map[i++];
0377         } else
0378             tmp_cpus[k++] = other->map[j++];
0379     }
0380
0381     while (i < orig->nr)
0382         tmp_cpus[k++] = orig->map[i++];
0383
0384     while (j < other->nr)
0385         tmp_cpus[k++] = other->map[j++];
0386     assert(k <= tmp_len);
0387
0388     merged = cpu_map__trim_new(k, tmp_cpus);
0389     free(tmp_cpus);
0390     perf_cpu_map__put(orig);
0391     return merged;
0392 }