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