samples/bpf/test_lru_dist.c

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