samples/bpf/test_lru_dist.c

   1 // SPDX-License-Identifier: GPL-2.0-only
   2 /*
   3  * Copyright (c) 2016 Facebook
   4  */
   5 #define _GNU_SOURCE
   6 #include <linux/types.h>
   7 #include <stdio.h>
   8 #include <unistd.h>
   9 #include <linux/bpf.h>
  10 #include <errno.h>
  11 #include <string.h>
  12 #include <assert.h>
  13 #include <sched.h>
  14 #include <sys/wait.h>
  15 #include <sys/stat.h>
  16 #include <fcntl.h>
  17 #include <stdlib.h>
  18 #include <time.h>
  19
  20 #include <bpf/bpf.h>
  21 #include "bpf_util.h"
  22
  23 #define min(a, b) ((a) < (b) ? (a) : (b))
  24 #ifndef offsetof
  25 # define offsetof(TYPE, MEMBER) ((size_t)&((TYPE *)0)->MEMBER)
  26 #endif
  27 #define container_of(ptr, type, member) ({                      \
  28         const typeof( ((type *)0)->member ) *__mptr = (ptr);    \
  29         (type *)( (char *)__mptr - offsetof(type,member) );})
  30
  31 static int nr_cpus;
  32 static unsigned long long *dist_keys;
  33 static unsigned int dist_key_counts;
  34
  35 struct list_head {
  36         struct list_head *next, *prev;
  37 };
  38
  39 static inline void INIT_LIST_HEAD(struct list_head *list)
  40 {
  41         list->next = list;
  42         list->prev = list;
  43 }
  44
  45 static inline int list_empty(const struct list_head *head)
  46 {
  47         return head->next == head;
  48 }
  49
  50 static inline void __list_add(struct list_head *new,
  51                               struct list_head *prev,
  52                               struct list_head *next)
  53 {
  54         next->prev = new;
  55         new->next = next;
  56         new->prev = prev;
  57         prev->next = new;
  58 }
  59
  60 static inline void list_add(struct list_head *new, struct list_head *head)
  61 {
  62         __list_add(new, head, head->next);
  63 }
  64
  65 static inline void __list_del(struct list_head *prev, struct list_head *next)
  66 {
  67         next->prev = prev;
  68         prev->next = next;
  69 }
  70
  71 static inline void __list_del_entry(struct list_head *entry)
  72 {
  73         __list_del(entry->prev, entry->next);
  74 }
  75
  76 static inline void list_move(struct list_head *list, struct list_head *head)
  77 {
  78         __list_del_entry(list);
  79         list_add(list, head);
  80 }
  81
  82 #define list_entry(ptr, type, member) \
  83         container_of(ptr, type, member)
  84
  85 #define list_last_entry(ptr, type, member) \
  86         list_entry((ptr)->prev, type, member)
  87
  88 struct pfect_lru_node {
  89         struct list_head list;
  90         unsigned long long key;
  91 };
  92
  93 struct pfect_lru {
  94         struct list_head list;
  95         struct pfect_lru_node *free_nodes;
  96         unsigned int cur_size;
  97         unsigned int lru_size;
  98         unsigned int nr_unique;
  99         unsigned int nr_misses;
 100         unsigned int total;
 101         int map_fd;
 102 };
 103
 104 static void pfect_lru_init(struct pfect_lru *lru, unsigned int lru_size,
 105                            unsigned int nr_possible_elems)
 106 {
 107         lru->map_fd = bpf_map_create(BPF_MAP_TYPE_HASH, NULL,
 108                                      sizeof(unsigned long long),
 109                                      sizeof(struct pfect_lru_node *),
 110                                      nr_possible_elems, NULL);
 111         assert(lru->map_fd != -1);
 112
 113         lru->free_nodes = malloc(lru_size * sizeof(struct pfect_lru_node));
 114         assert(lru->free_nodes);
 115
 116         INIT_LIST_HEAD(&lru->list);
 117         lru->cur_size = 0;
 118         lru->lru_size = lru_size;
 119         lru->nr_unique = lru->nr_misses = lru->total = 0;
 120 }
 121
 122 static void pfect_lru_destroy(struct pfect_lru *lru)
 123 {
 124         close(lru->map_fd);
 125         free(lru->free_nodes);
 126 }
 127
 128 static int pfect_lru_lookup_or_insert(struct pfect_lru *lru,
 129                                       unsigned long long key)
 130 {
 131         struct pfect_lru_node *node = NULL;
 132         int seen = 0;
 133
 134         lru->total++;
 135         if (!bpf_map_lookup_elem(lru->map_fd, &key, &node)) {
 136                 if (node) {
 137                         list_move(&node->list, &lru->list);
 138                         return 1;
 139                 }
 140                 seen = 1;
 141         }
 142
 143         if (lru->cur_size < lru->lru_size) {
 144                 node =  &lru->free_nodes[lru->cur_size++];
 145                 INIT_LIST_HEAD(&node->list);
 146         } else {
 147                 struct pfect_lru_node *null_node = NULL;
 148
 149                 node = list_last_entry(&lru->list,
 150                                        struct pfect_lru_node,
 151                                        list);
 152                 bpf_map_update_elem(lru->map_fd, &node->key, &null_node, BPF_EXIST);
 153         }
 154
 155         node->key = key;
 156         list_move(&node->list, &lru->list);
 157
 158         lru->nr_misses++;
 159         if (seen) {
 160                 assert(!bpf_map_update_elem(lru->map_fd, &key, &node, BPF_EXIST));
 161         } else {
 162                 lru->nr_unique++;
 163                 assert(!bpf_map_update_elem(lru->map_fd, &key, &node, BPF_NOEXIST));
 164         }
 165
 166         return seen;
 167 }
 168
 169 static unsigned int read_keys(const char *dist_file,
 170                               unsigned long long **keys)
 171 {
 172         struct stat fst;
 173         unsigned long long *retkeys;
 174         unsigned int counts = 0;
 175         int dist_fd;
 176         char *b, *l;
 177         int i;
 178
 179         dist_fd = open(dist_file, 0);
 180         assert(dist_fd != -1);
 181
 182         assert(fstat(dist_fd, &fst) == 0);
 183         b = malloc(fst.st_size);
 184         assert(b);
 185
 186         assert(read(dist_fd, b, fst.st_size) == fst.st_size);
 187         close(dist_fd);
 188         for (i = 0; i < fst.st_size; i++) {
 189                 if (b[i] == '\n')
 190                         counts++;
 191         }
 192         counts++; /* in case the last line has no \n */
 193
 194         retkeys = malloc(counts * sizeof(unsigned long long));
 195         assert(retkeys);
 196
 197         counts = 0;
 198         for (l = strtok(b, "\n"); l; l = strtok(NULL, "\n"))
 199                 retkeys[counts++] = strtoull(l, NULL, 10);
 200         free(b);
 201
 202         *keys = retkeys;
 203
 204         return counts;
 205 }
 206
 207 static int create_map(int map_type, int map_flags, unsigned int size)
 208 {
 209         LIBBPF_OPTS(bpf_map_create_opts, opts,
 210                 .map_flags = map_flags,
 211         );
 212         int map_fd;
 213
 214         map_fd = bpf_map_create(map_type, NULL, sizeof(unsigned long long),
 215                                 sizeof(unsigned long long), size, &opts);
 216
 217         if (map_fd == -1)
 218                 perror("bpf_create_map");
 219
 220         return map_fd;
 221 }
 222
 223 static int sched_next_online(int pid, int next_to_try)
 224 {
 225         cpu_set_t cpuset;
 226
 227         if (next_to_try == nr_cpus)
 228                 return -1;
 229
 230         while (next_to_try < nr_cpus) {
 231                 CPU_ZERO(&cpuset);
 232                 CPU_SET(next_to_try++, &cpuset);
 233                 if (!sched_setaffinity(pid, sizeof(cpuset), &cpuset))
 234                         break;
 235         }
 236
 237         return next_to_try;
 238 }
 239
 240 static void run_parallel(unsigned int tasks, void (*fn)(int i, void *data),
 241                          void *data)
 242 {
 243         int next_sched_cpu = 0;
 244         pid_t pid[tasks];
 245         int i;
 246
 247         for (i = 0; i < tasks; i++) {
 248                 pid[i] = fork();
 249                 if (pid[i] == 0) {
 250                         next_sched_cpu = sched_next_online(0, next_sched_cpu);
 251                         fn(i, data);
 252                         exit(0);
 253                 } else if (pid[i] == -1) {
 254                         printf("couldn't spawn #%d process\n", i);
 255                         exit(1);
 256                 }
 257                 /* It is mostly redundant and just allow the parent
 258                  * process to update next_shced_cpu for the next child
 259                  * process
 260                  */
 261                 next_sched_cpu = sched_next_online(pid[i], next_sched_cpu);
 262         }
 263         for (i = 0; i < tasks; i++) {
 264                 int status;
 265
 266                 assert(waitpid(pid[i], &status, 0) == pid[i]);
 267                 assert(status == 0);
 268         }
 269 }
 270
 271 static void do_test_lru_dist(int task, void *data)
 272 {
 273         unsigned int nr_misses = 0;
 274         struct pfect_lru pfect_lru;
 275         unsigned long long key, value = 1234;
 276         unsigned int i;
 277
 278         unsigned int lru_map_fd = ((unsigned int *)data)[0];
 279         unsigned int lru_size = ((unsigned int *)data)[1];
 280         unsigned long long key_offset = task * dist_key_counts;
 281
 282         pfect_lru_init(&pfect_lru, lru_size, dist_key_counts);
 283
 284         for (i = 0; i < dist_key_counts; i++) {
 285                 key = dist_keys[i] + key_offset;
 286
 287                 pfect_lru_lookup_or_insert(&pfect_lru, key);
 288
 289                 if (!bpf_map_lookup_elem(lru_map_fd, &key, &value))
 290                         continue;
 291
 292                 if (bpf_map_update_elem(lru_map_fd, &key, &value, BPF_NOEXIST)) {
 293                         printf("bpf_map_update_elem(lru_map_fd, %llu): errno:%d\n",
 294                                key, errno);
 295                         assert(0);
 296                 }
 297
 298                 nr_misses++;
 299         }
 300
 301         printf("    task:%d BPF LRU: nr_unique:%u(/%u) nr_misses:%u(/%u)\n",
 302                task, pfect_lru.nr_unique, dist_key_counts, nr_misses,
 303                dist_key_counts);
 304         printf("    task:%d Perfect LRU: nr_unique:%u(/%u) nr_misses:%u(/%u)\n",
 305                task, pfect_lru.nr_unique, pfect_lru.total,
 306                pfect_lru.nr_misses, pfect_lru.total);
 307
 308         pfect_lru_destroy(&pfect_lru);
 309         close(lru_map_fd);
 310 }
 311
 312 static void test_parallel_lru_dist(int map_type, int map_flags,
 313                                    int nr_tasks, unsigned int lru_size)
 314 {
 315         int child_data[2];
 316         int lru_map_fd;
 317
 318         printf("%s (map_type:%d map_flags:0x%X):\n", __func__, map_type,
 319                map_flags);
 320
 321         if (map_flags & BPF_F_NO_COMMON_LRU)
 322                 lru_map_fd = create_map(map_type, map_flags,
 323                                         nr_cpus * lru_size);
 324         else
 325                 lru_map_fd = create_map(map_type, map_flags,
 326                                         nr_tasks * lru_size);
 327         assert(lru_map_fd != -1);
 328
 329         child_data[0] = lru_map_fd;
 330         child_data[1] = lru_size;
 331
 332         run_parallel(nr_tasks, do_test_lru_dist, child_data);
 333
 334         close(lru_map_fd);
 335 }
 336
 337 static void test_lru_loss0(int map_type, int map_flags)
 338 {
 339         unsigned long long key, value[nr_cpus];
 340         unsigned int old_unused_losses = 0;
 341         unsigned int new_unused_losses = 0;
 342         unsigned int used_losses = 0;
 343         int map_fd;
 344
 345         printf("%s (map_type:%d map_flags:0x%X): ", __func__, map_type,
 346                map_flags);
 347
 348         assert(sched_next_online(0, 0) != -1);
 349
 350         if (map_flags & BPF_F_NO_COMMON_LRU)
 351                 map_fd = create_map(map_type, map_flags, 900 * nr_cpus);
 352         else
 353                 map_fd = create_map(map_type, map_flags, 900);
 354
 355         assert(map_fd != -1);
 356
 357         value[0] = 1234;
 358
 359         for (key = 1; key <= 1000; key++) {
 360                 int start_key, end_key;
 361
 362                 assert(bpf_map_update_elem(map_fd, &key, value, BPF_NOEXIST) == 0);
 363
 364                 start_key = 101;
 365                 end_key = min(key, 900);
 366
 367                 while (start_key <= end_key) {
 368                         bpf_map_lookup_elem(map_fd, &start_key, value);
 369                         start_key++;
 370                 }
 371         }
 372
 373         for (key = 1; key <= 1000; key++) {
 374                 if (bpf_map_lookup_elem(map_fd, &key, value)) {
 375                         if (key <= 100)
 376                                 old_unused_losses++;
 377                         else if (key <= 900)
 378                                 used_losses++;
 379                         else
 380                                 new_unused_losses++;
 381                 }
 382         }
 383
 384         close(map_fd);
 385
 386         printf("older-elem-losses:%d(/100) active-elem-losses:%d(/800) "
 387                "newer-elem-losses:%d(/100)\n",
 388                old_unused_losses, used_losses, new_unused_losses);
 389 }
 390
 391 static void test_lru_loss1(int map_type, int map_flags)
 392 {
 393         unsigned long long key, value[nr_cpus];
 394         int map_fd;
 395         unsigned int nr_losses = 0;
 396
 397         printf("%s (map_type:%d map_flags:0x%X): ", __func__, map_type,
 398                map_flags);
 399
 400         assert(sched_next_online(0, 0) != -1);
 401
 402         if (map_flags & BPF_F_NO_COMMON_LRU)
 403                 map_fd = create_map(map_type, map_flags, 1000 * nr_cpus);
 404         else
 405                 map_fd = create_map(map_type, map_flags, 1000);
 406
 407         assert(map_fd != -1);
 408
 409         value[0] = 1234;
 410
 411         for (key = 1; key <= 1000; key++)
 412                 assert(!bpf_map_update_elem(map_fd, &key, value, BPF_NOEXIST));
 413
 414         for (key = 1; key <= 1000; key++) {
 415                 if (bpf_map_lookup_elem(map_fd, &key, value))
 416                         nr_losses++;
 417         }
 418
 419         close(map_fd);
 420
 421         printf("nr_losses:%d(/1000)\n", nr_losses);
 422 }
 423
 424 static void do_test_parallel_lru_loss(int task, void *data)
 425 {
 426         const unsigned int nr_stable_elems = 1000;
 427         const unsigned int nr_repeats = 100000;
 428
 429         int map_fd = *(int *)data;
 430         unsigned long long stable_base;
 431         unsigned long long key, value[nr_cpus];
 432         unsigned long long next_ins_key;
 433         unsigned int nr_losses = 0;
 434         unsigned int i;
 435
 436         stable_base = task * nr_repeats * 2 + 1;
 437         next_ins_key = stable_base;
 438         value[0] = 1234;
 439         for (i = 0; i < nr_stable_elems; i++) {
 440                 assert(bpf_map_update_elem(map_fd, &next_ins_key, value,
 441                                        BPF_NOEXIST) == 0);
 442                 next_ins_key++;
 443         }
 444
 445         for (i = 0; i < nr_repeats; i++) {
 446                 int rn;
 447
 448                 rn = rand();
 449
 450                 if (rn % 10) {
 451                         key = rn % nr_stable_elems + stable_base;
 452                         bpf_map_lookup_elem(map_fd, &key, value);
 453                 } else {
 454                         bpf_map_update_elem(map_fd, &next_ins_key, value,
 455                                         BPF_NOEXIST);
 456                         next_ins_key++;
 457                 }
 458         }
 459
 460         key = stable_base;
 461         for (i = 0; i < nr_stable_elems; i++) {
 462                 if (bpf_map_lookup_elem(map_fd, &key, value))
 463                         nr_losses++;
 464                 key++;
 465         }
 466
 467         printf("    task:%d nr_losses:%u\n", task, nr_losses);
 468 }
 469
 470 static void test_parallel_lru_loss(int map_type, int map_flags, int nr_tasks)
 471 {
 472         int map_fd;
 473
 474         printf("%s (map_type:%d map_flags:0x%X):\n", __func__, map_type,
 475                map_flags);
 476
 477         /* Give 20% more than the active working set */
 478         if (map_flags & BPF_F_NO_COMMON_LRU)
 479                 map_fd = create_map(map_type, map_flags,
 480                                     nr_cpus * (1000 + 200));
 481         else
 482                 map_fd = create_map(map_type, map_flags,
 483                                     nr_tasks * (1000 + 200));
 484
 485         assert(map_fd != -1);
 486
 487         run_parallel(nr_tasks, do_test_parallel_lru_loss, &map_fd);
 488
 489         close(map_fd);
 490 }
 491
 492 int main(int argc, char **argv)
 493 {
 494         int map_flags[] = {0, BPF_F_NO_COMMON_LRU};
 495         const char *dist_file;
 496         int nr_tasks = 1;
 497         int lru_size;
 498         int f;
 499
 500         if (argc < 4) {
 501                 printf("Usage: %s <dist-file> <lru-size> <nr-tasks>\n",
 502                        argv[0]);
 503                 return -1;
 504         }
 505
 506         dist_file = argv[1];
 507         lru_size = atoi(argv[2]);
 508         nr_tasks = atoi(argv[3]);
 509
 510         setbuf(stdout, NULL);
 511
 512         srand(time(NULL));
 513
 514         nr_cpus = bpf_num_possible_cpus();
 515         assert(nr_cpus != -1);
 516         printf("nr_cpus:%d\n\n", nr_cpus);
 517
 518         nr_tasks = min(nr_tasks, nr_cpus);
 519
 520         dist_key_counts = read_keys(dist_file, &dist_keys);
 521         if (!dist_key_counts) {
 522                 printf("%s has no key\n", dist_file);
 523                 return -1;
 524         }
 525
 526         for (f = 0; f < ARRAY_SIZE(map_flags); f++) {
 527                 test_lru_loss0(BPF_MAP_TYPE_LRU_HASH, map_flags[f]);
 528                 test_lru_loss1(BPF_MAP_TYPE_LRU_HASH, map_flags[f]);
 529                 test_parallel_lru_loss(BPF_MAP_TYPE_LRU_HASH, map_flags[f],
 530                                        nr_tasks);
 531                 test_parallel_lru_dist(BPF_MAP_TYPE_LRU_HASH, map_flags[f],
 532                                        nr_tasks, lru_size);
 533                 printf("\n");
 534         }
 535
 536         free(dist_keys);
 537
 538         return 0;
 539 }