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