tools/lib/perf/cpumap.c

   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 static 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
  25 struct 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
  35 static 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
  44 struct 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
  51 void 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
  57 static 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
  77 struct perf_cpu_map *perf_cpu_map__default_new(void)
  78 {
  79         return cpu_map__default_new();
  80 }
  81
  82
  83 static 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
  90 static 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
 111 struct 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();
 164 out_free_tmp:
 165         free(tmp_cpus);
 166         return cpus;
 167 }
 168
 169 static 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
 183 struct 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();
 254 invalid:
 255         free(tmp_cpus);
 256 out:
 257         return cpus;
 258 }
 259
 260 struct 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
 272 int perf_cpu_map__nr(const struct perf_cpu_map *cpus)
 273 {
 274         return cpus ? cpus->nr : 1;
 275 }
 276
 277 bool perf_cpu_map__empty(const struct perf_cpu_map *map)
 278 {
 279         return map ? map->map[0].cpu == -1 : true;
 280 }
 281
 282 int 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
 307 bool 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
 312 struct perf_cpu perf_cpu_map__max(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'. */
 323 bool 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
 350 struct 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 }