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