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 < sizeof(map_flags) / sizeof(*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 } 540