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 <stdio.h> 10 #include <unistd.h> 11 #include <errno.h> 12 #include <string.h> 13 #include <assert.h> 14 #include <sched.h> 15 #include <stdlib.h> 16 #include <time.h> 17 18 #include <sys/wait.h> 19 #include <sys/resource.h> 20 21 #include <bpf/bpf.h> 22 #include "bpf_util.h" 23 24 #define LOCAL_FREE_TARGET (128) 25 #define PERCPU_FREE_TARGET (4) 26 27 static int nr_cpus; 28 29 static int create_map(int map_type, int map_flags, unsigned int size) 30 { 31 int map_fd; 32 33 map_fd = bpf_create_map(map_type, sizeof(unsigned long long), 34 sizeof(unsigned long long), size, map_flags); 35 36 if (map_fd == -1) 37 perror("bpf_create_map"); 38 39 return map_fd; 40 } 41 42 static int map_subset(int map0, int map1) 43 { 44 unsigned long long next_key = 0; 45 unsigned long long value0[nr_cpus], value1[nr_cpus]; 46 int ret; 47 48 while (!bpf_map_get_next_key(map1, &next_key, &next_key)) { 49 assert(!bpf_map_lookup_elem(map1, &next_key, value1)); 50 ret = bpf_map_lookup_elem(map0, &next_key, value0); 51 if (ret) { 52 printf("key:%llu not found from map. %s(%d)\n", 53 next_key, strerror(errno), errno); 54 return 0; 55 } 56 if (value0[0] != value1[0]) { 57 printf("key:%llu value0:%llu != value1:%llu\n", 58 next_key, value0[0], value1[0]); 59 return 0; 60 } 61 } 62 return 1; 63 } 64 65 static int map_equal(int lru_map, int expected) 66 { 67 return map_subset(lru_map, expected) && map_subset(expected, lru_map); 68 } 69 70 static int sched_next_online(int pid, int *next_to_try) 71 { 72 cpu_set_t cpuset; 73 int next = *next_to_try; 74 int ret = -1; 75 76 while (next < nr_cpus) { 77 CPU_ZERO(&cpuset); 78 CPU_SET(next++, &cpuset); 79 if (!sched_setaffinity(pid, sizeof(cpuset), &cpuset)) { 80 ret = 0; 81 break; 82 } 83 } 84 85 *next_to_try = next; 86 return ret; 87 } 88 89 /* Size of the LRU amp is 2 90 * Add key=1 (+1 key) 91 * Add key=2 (+1 key) 92 * Lookup Key=1 93 * Add Key=3 94 * => Key=2 will be removed by LRU 95 * Iterate map. Only found key=1 and key=3 96 */ 97 static void test_lru_sanity0(int map_type, int map_flags) 98 { 99 unsigned long long key, value[nr_cpus]; 100 int lru_map_fd, expected_map_fd; 101 int next_cpu = 0; 102 103 printf("%s (map_type:%d map_flags:0x%X): ", __func__, map_type, 104 map_flags); 105 106 assert(sched_next_online(0, &next_cpu) != -1); 107 108 if (map_flags & BPF_F_NO_COMMON_LRU) 109 lru_map_fd = create_map(map_type, map_flags, 2 * nr_cpus); 110 else 111 lru_map_fd = create_map(map_type, map_flags, 2); 112 assert(lru_map_fd != -1); 113 114 expected_map_fd = create_map(BPF_MAP_TYPE_HASH, 0, 2); 115 assert(expected_map_fd != -1); 116 117 value[0] = 1234; 118 119 /* insert key=1 element */ 120 121 key = 1; 122 assert(!bpf_map_update_elem(lru_map_fd, &key, value, BPF_NOEXIST)); 123 assert(!bpf_map_update_elem(expected_map_fd, &key, value, 124 BPF_NOEXIST)); 125 126 /* BPF_NOEXIST means: add new element if it doesn't exist */ 127 assert(bpf_map_update_elem(lru_map_fd, &key, value, BPF_NOEXIST) == -1 128 /* key=1 already exists */ 129 && errno == EEXIST); 130 131 assert(bpf_map_update_elem(lru_map_fd, &key, value, -1) == -1 && 132 errno == EINVAL); 133 134 /* insert key=2 element */ 135 136 /* check that key=2 is not found */ 137 key = 2; 138 assert(bpf_map_lookup_elem(lru_map_fd, &key, value) == -1 && 139 errno == ENOENT); 140 141 /* BPF_EXIST means: update existing element */ 142 assert(bpf_map_update_elem(lru_map_fd, &key, value, BPF_EXIST) == -1 && 143 /* key=2 is not there */ 144 errno == ENOENT); 145 146 assert(!bpf_map_update_elem(lru_map_fd, &key, value, BPF_NOEXIST)); 147 148 /* insert key=3 element */ 149 150 /* check that key=3 is not found */ 151 key = 3; 152 assert(bpf_map_lookup_elem(lru_map_fd, &key, value) == -1 && 153 errno == ENOENT); 154 155 /* check that key=1 can be found and mark the ref bit to 156 * stop LRU from removing key=1 157 */ 158 key = 1; 159 assert(!bpf_map_lookup_elem(lru_map_fd, &key, value)); 160 assert(value[0] == 1234); 161 162 key = 3; 163 assert(!bpf_map_update_elem(lru_map_fd, &key, value, BPF_NOEXIST)); 164 assert(!bpf_map_update_elem(expected_map_fd, &key, value, 165 BPF_NOEXIST)); 166 167 /* key=2 has been removed from the LRU */ 168 key = 2; 169 assert(bpf_map_lookup_elem(lru_map_fd, &key, value) == -1); 170 171 assert(map_equal(lru_map_fd, expected_map_fd)); 172 173 close(expected_map_fd); 174 close(lru_map_fd); 175 176 printf("Pass\n"); 177 } 178 179 /* Size of the LRU map is 1.5*tgt_free 180 * Insert 1 to tgt_free (+tgt_free keys) 181 * Lookup 1 to tgt_free/2 182 * Insert 1+tgt_free to 2*tgt_free (+tgt_free keys) 183 * => 1+tgt_free/2 to LOCALFREE_TARGET will be removed by LRU 184 */ 185 static void test_lru_sanity1(int map_type, int map_flags, unsigned int tgt_free) 186 { 187 unsigned long long key, end_key, value[nr_cpus]; 188 int lru_map_fd, expected_map_fd; 189 unsigned int batch_size; 190 unsigned int map_size; 191 int next_cpu = 0; 192 193 if (map_flags & BPF_F_NO_COMMON_LRU) 194 /* This test is only applicable to common LRU list */ 195 return; 196 197 printf("%s (map_type:%d map_flags:0x%X): ", __func__, map_type, 198 map_flags); 199 200 assert(sched_next_online(0, &next_cpu) != -1); 201 202 batch_size = tgt_free / 2; 203 assert(batch_size * 2 == tgt_free); 204 205 map_size = tgt_free + batch_size; 206 lru_map_fd = create_map(map_type, map_flags, map_size); 207 assert(lru_map_fd != -1); 208 209 expected_map_fd = create_map(BPF_MAP_TYPE_HASH, 0, map_size); 210 assert(expected_map_fd != -1); 211 212 value[0] = 1234; 213 214 /* Insert 1 to tgt_free (+tgt_free keys) */ 215 end_key = 1 + tgt_free; 216 for (key = 1; key < end_key; key++) 217 assert(!bpf_map_update_elem(lru_map_fd, &key, value, 218 BPF_NOEXIST)); 219 220 /* Lookup 1 to tgt_free/2 */ 221 end_key = 1 + batch_size; 222 for (key = 1; key < end_key; key++) { 223 assert(!bpf_map_lookup_elem(lru_map_fd, &key, value)); 224 assert(!bpf_map_update_elem(expected_map_fd, &key, value, 225 BPF_NOEXIST)); 226 } 227 228 /* Insert 1+tgt_free to 2*tgt_free 229 * => 1+tgt_free/2 to LOCALFREE_TARGET will be 230 * removed by LRU 231 */ 232 key = 1 + tgt_free; 233 end_key = key + tgt_free; 234 for (; key < end_key; key++) { 235 assert(!bpf_map_update_elem(lru_map_fd, &key, value, 236 BPF_NOEXIST)); 237 assert(!bpf_map_update_elem(expected_map_fd, &key, value, 238 BPF_NOEXIST)); 239 } 240 241 assert(map_equal(lru_map_fd, expected_map_fd)); 242 243 close(expected_map_fd); 244 close(lru_map_fd); 245 246 printf("Pass\n"); 247 } 248 249 /* Size of the LRU map 1.5 * tgt_free 250 * Insert 1 to tgt_free (+tgt_free keys) 251 * Update 1 to tgt_free/2 252 * => The original 1 to tgt_free/2 will be removed due to 253 * the LRU shrink process 254 * Re-insert 1 to tgt_free/2 again and do a lookup immeidately 255 * Insert 1+tgt_free to tgt_free*3/2 256 * Insert 1+tgt_free*3/2 to tgt_free*5/2 257 * => Key 1+tgt_free to tgt_free*3/2 258 * will be removed from LRU because it has never 259 * been lookup and ref bit is not set 260 */ 261 static void test_lru_sanity2(int map_type, int map_flags, unsigned int tgt_free) 262 { 263 unsigned long long key, value[nr_cpus]; 264 unsigned long long end_key; 265 int lru_map_fd, expected_map_fd; 266 unsigned int batch_size; 267 unsigned int map_size; 268 int next_cpu = 0; 269 270 if (map_flags & BPF_F_NO_COMMON_LRU) 271 /* This test is only applicable to common LRU list */ 272 return; 273 274 printf("%s (map_type:%d map_flags:0x%X): ", __func__, map_type, 275 map_flags); 276 277 assert(sched_next_online(0, &next_cpu) != -1); 278 279 batch_size = tgt_free / 2; 280 assert(batch_size * 2 == tgt_free); 281 282 map_size = tgt_free + batch_size; 283 lru_map_fd = create_map(map_type, map_flags, map_size); 284 assert(lru_map_fd != -1); 285 286 expected_map_fd = create_map(BPF_MAP_TYPE_HASH, 0, map_size); 287 assert(expected_map_fd != -1); 288 289 value[0] = 1234; 290 291 /* Insert 1 to tgt_free (+tgt_free keys) */ 292 end_key = 1 + tgt_free; 293 for (key = 1; key < end_key; key++) 294 assert(!bpf_map_update_elem(lru_map_fd, &key, value, 295 BPF_NOEXIST)); 296 297 /* Any bpf_map_update_elem will require to acquire a new node 298 * from LRU first. 299 * 300 * The local list is running out of free nodes. 301 * It gets from the global LRU list which tries to 302 * shrink the inactive list to get tgt_free 303 * number of free nodes. 304 * 305 * Hence, the oldest key 1 to tgt_free/2 306 * are removed from the LRU list. 307 */ 308 key = 1; 309 if (map_type == BPF_MAP_TYPE_LRU_PERCPU_HASH) { 310 assert(!bpf_map_update_elem(lru_map_fd, &key, value, 311 BPF_NOEXIST)); 312 assert(!bpf_map_delete_elem(lru_map_fd, &key)); 313 } else { 314 assert(bpf_map_update_elem(lru_map_fd, &key, value, 315 BPF_EXIST)); 316 } 317 318 /* Re-insert 1 to tgt_free/2 again and do a lookup 319 * immeidately. 320 */ 321 end_key = 1 + batch_size; 322 value[0] = 4321; 323 for (key = 1; key < end_key; key++) { 324 assert(bpf_map_lookup_elem(lru_map_fd, &key, value)); 325 assert(!bpf_map_update_elem(lru_map_fd, &key, value, 326 BPF_NOEXIST)); 327 assert(!bpf_map_lookup_elem(lru_map_fd, &key, value)); 328 assert(value[0] == 4321); 329 assert(!bpf_map_update_elem(expected_map_fd, &key, value, 330 BPF_NOEXIST)); 331 } 332 333 value[0] = 1234; 334 335 /* Insert 1+tgt_free to tgt_free*3/2 */ 336 end_key = 1 + tgt_free + batch_size; 337 for (key = 1 + tgt_free; key < end_key; key++) 338 /* These newly added but not referenced keys will be 339 * gone during the next LRU shrink. 340 */ 341 assert(!bpf_map_update_elem(lru_map_fd, &key, value, 342 BPF_NOEXIST)); 343 344 /* Insert 1+tgt_free*3/2 to tgt_free*5/2 */ 345 end_key = key + tgt_free; 346 for (; key < end_key; key++) { 347 assert(!bpf_map_update_elem(lru_map_fd, &key, value, 348 BPF_NOEXIST)); 349 assert(!bpf_map_update_elem(expected_map_fd, &key, value, 350 BPF_NOEXIST)); 351 } 352 353 assert(map_equal(lru_map_fd, expected_map_fd)); 354 355 close(expected_map_fd); 356 close(lru_map_fd); 357 358 printf("Pass\n"); 359 } 360 361 /* Size of the LRU map is 2*tgt_free 362 * It is to test the active/inactive list rotation 363 * Insert 1 to 2*tgt_free (+2*tgt_free keys) 364 * Lookup key 1 to tgt_free*3/2 365 * Add 1+2*tgt_free to tgt_free*5/2 (+tgt_free/2 keys) 366 * => key 1+tgt_free*3/2 to 2*tgt_free are removed from LRU 367 */ 368 static void test_lru_sanity3(int map_type, int map_flags, unsigned int tgt_free) 369 { 370 unsigned long long key, end_key, value[nr_cpus]; 371 int lru_map_fd, expected_map_fd; 372 unsigned int batch_size; 373 unsigned int map_size; 374 int next_cpu = 0; 375 376 if (map_flags & BPF_F_NO_COMMON_LRU) 377 /* This test is only applicable to common LRU list */ 378 return; 379 380 printf("%s (map_type:%d map_flags:0x%X): ", __func__, map_type, 381 map_flags); 382 383 assert(sched_next_online(0, &next_cpu) != -1); 384 385 batch_size = tgt_free / 2; 386 assert(batch_size * 2 == tgt_free); 387 388 map_size = tgt_free * 2; 389 lru_map_fd = create_map(map_type, map_flags, map_size); 390 assert(lru_map_fd != -1); 391 392 expected_map_fd = create_map(BPF_MAP_TYPE_HASH, 0, map_size); 393 assert(expected_map_fd != -1); 394 395 value[0] = 1234; 396 397 /* Insert 1 to 2*tgt_free (+2*tgt_free keys) */ 398 end_key = 1 + (2 * tgt_free); 399 for (key = 1; key < end_key; key++) 400 assert(!bpf_map_update_elem(lru_map_fd, &key, value, 401 BPF_NOEXIST)); 402 403 /* Lookup key 1 to tgt_free*3/2 */ 404 end_key = tgt_free + batch_size; 405 for (key = 1; key < end_key; key++) { 406 assert(!bpf_map_lookup_elem(lru_map_fd, &key, value)); 407 assert(!bpf_map_update_elem(expected_map_fd, &key, value, 408 BPF_NOEXIST)); 409 } 410 411 /* Add 1+2*tgt_free to tgt_free*5/2 412 * (+tgt_free/2 keys) 413 */ 414 key = 2 * tgt_free + 1; 415 end_key = key + batch_size; 416 for (; key < end_key; key++) { 417 assert(!bpf_map_update_elem(lru_map_fd, &key, value, 418 BPF_NOEXIST)); 419 assert(!bpf_map_update_elem(expected_map_fd, &key, value, 420 BPF_NOEXIST)); 421 } 422 423 assert(map_equal(lru_map_fd, expected_map_fd)); 424 425 close(expected_map_fd); 426 close(lru_map_fd); 427 428 printf("Pass\n"); 429 } 430 431 /* Test deletion */ 432 static void test_lru_sanity4(int map_type, int map_flags, unsigned int tgt_free) 433 { 434 int lru_map_fd, expected_map_fd; 435 unsigned long long key, value[nr_cpus]; 436 unsigned long long end_key; 437 int next_cpu = 0; 438 439 printf("%s (map_type:%d map_flags:0x%X): ", __func__, map_type, 440 map_flags); 441 442 assert(sched_next_online(0, &next_cpu) != -1); 443 444 if (map_flags & BPF_F_NO_COMMON_LRU) 445 lru_map_fd = create_map(map_type, map_flags, 446 3 * tgt_free * nr_cpus); 447 else 448 lru_map_fd = create_map(map_type, map_flags, 3 * tgt_free); 449 assert(lru_map_fd != -1); 450 451 expected_map_fd = create_map(BPF_MAP_TYPE_HASH, 0, 452 3 * tgt_free); 453 assert(expected_map_fd != -1); 454 455 value[0] = 1234; 456 457 for (key = 1; key <= 2 * tgt_free; key++) 458 assert(!bpf_map_update_elem(lru_map_fd, &key, value, 459 BPF_NOEXIST)); 460 461 key = 1; 462 assert(bpf_map_update_elem(lru_map_fd, &key, value, BPF_NOEXIST)); 463 464 for (key = 1; key <= tgt_free; key++) { 465 assert(!bpf_map_lookup_elem(lru_map_fd, &key, value)); 466 assert(!bpf_map_update_elem(expected_map_fd, &key, value, 467 BPF_NOEXIST)); 468 } 469 470 for (; key <= 2 * tgt_free; key++) { 471 assert(!bpf_map_delete_elem(lru_map_fd, &key)); 472 assert(bpf_map_delete_elem(lru_map_fd, &key)); 473 } 474 475 end_key = key + 2 * tgt_free; 476 for (; key < end_key; key++) { 477 assert(!bpf_map_update_elem(lru_map_fd, &key, value, 478 BPF_NOEXIST)); 479 assert(!bpf_map_update_elem(expected_map_fd, &key, value, 480 BPF_NOEXIST)); 481 } 482 483 assert(map_equal(lru_map_fd, expected_map_fd)); 484 485 close(expected_map_fd); 486 close(lru_map_fd); 487 488 printf("Pass\n"); 489 } 490 491 static void do_test_lru_sanity5(unsigned long long last_key, int map_fd) 492 { 493 unsigned long long key, value[nr_cpus]; 494 495 /* Ensure the last key inserted by previous CPU can be found */ 496 assert(!bpf_map_lookup_elem(map_fd, &last_key, value)); 497 498 value[0] = 1234; 499 500 key = last_key + 1; 501 assert(!bpf_map_update_elem(map_fd, &key, value, BPF_NOEXIST)); 502 assert(!bpf_map_lookup_elem(map_fd, &key, value)); 503 504 /* Cannot find the last key because it was removed by LRU */ 505 assert(bpf_map_lookup_elem(map_fd, &last_key, value)); 506 } 507 508 /* Test map with only one element */ 509 static void test_lru_sanity5(int map_type, int map_flags) 510 { 511 unsigned long long key, value[nr_cpus]; 512 int next_cpu = 0; 513 int map_fd; 514 515 if (map_flags & BPF_F_NO_COMMON_LRU) 516 return; 517 518 printf("%s (map_type:%d map_flags:0x%X): ", __func__, map_type, 519 map_flags); 520 521 map_fd = create_map(map_type, map_flags, 1); 522 assert(map_fd != -1); 523 524 value[0] = 1234; 525 key = 0; 526 assert(!bpf_map_update_elem(map_fd, &key, value, BPF_NOEXIST)); 527 528 while (sched_next_online(0, &next_cpu) != -1) { 529 pid_t pid; 530 531 pid = fork(); 532 if (pid == 0) { 533 do_test_lru_sanity5(key, map_fd); 534 exit(0); 535 } else if (pid == -1) { 536 printf("couldn't spawn process to test key:%llu\n", 537 key); 538 exit(1); 539 } else { 540 int status; 541 542 assert(waitpid(pid, &status, 0) == pid); 543 assert(status == 0); 544 key++; 545 } 546 } 547 548 close(map_fd); 549 /* At least one key should be tested */ 550 assert(key > 0); 551 552 printf("Pass\n"); 553 } 554 555 /* Test list rotation for BPF_F_NO_COMMON_LRU map */ 556 static void test_lru_sanity6(int map_type, int map_flags, int tgt_free) 557 { 558 int lru_map_fd, expected_map_fd; 559 unsigned long long key, value[nr_cpus]; 560 unsigned int map_size = tgt_free * 2; 561 int next_cpu = 0; 562 563 if (!(map_flags & BPF_F_NO_COMMON_LRU)) 564 return; 565 566 printf("%s (map_type:%d map_flags:0x%X): ", __func__, map_type, 567 map_flags); 568 569 assert(sched_next_online(0, &next_cpu) != -1); 570 571 expected_map_fd = create_map(BPF_MAP_TYPE_HASH, 0, map_size); 572 assert(expected_map_fd != -1); 573 574 lru_map_fd = create_map(map_type, map_flags, map_size * nr_cpus); 575 assert(lru_map_fd != -1); 576 577 value[0] = 1234; 578 579 for (key = 1; key <= tgt_free; key++) { 580 assert(!bpf_map_update_elem(lru_map_fd, &key, value, 581 BPF_NOEXIST)); 582 assert(!bpf_map_update_elem(expected_map_fd, &key, value, 583 BPF_NOEXIST)); 584 } 585 586 for (; key <= tgt_free * 2; key++) { 587 unsigned long long stable_key; 588 589 /* Make ref bit sticky for key: [1, tgt_free] */ 590 for (stable_key = 1; stable_key <= tgt_free; stable_key++) { 591 /* Mark the ref bit */ 592 assert(!bpf_map_lookup_elem(lru_map_fd, &stable_key, 593 value)); 594 } 595 assert(!bpf_map_update_elem(lru_map_fd, &key, value, 596 BPF_NOEXIST)); 597 } 598 599 for (; key <= tgt_free * 3; key++) { 600 assert(!bpf_map_update_elem(lru_map_fd, &key, value, 601 BPF_NOEXIST)); 602 assert(!bpf_map_update_elem(expected_map_fd, &key, value, 603 BPF_NOEXIST)); 604 } 605 606 assert(map_equal(lru_map_fd, expected_map_fd)); 607 608 close(expected_map_fd); 609 close(lru_map_fd); 610 611 printf("Pass\n"); 612 } 613 614 int main(int argc, char **argv) 615 { 616 struct rlimit r = {RLIM_INFINITY, RLIM_INFINITY}; 617 int map_types[] = {BPF_MAP_TYPE_LRU_HASH, 618 BPF_MAP_TYPE_LRU_PERCPU_HASH}; 619 int map_flags[] = {0, BPF_F_NO_COMMON_LRU}; 620 int t, f; 621 622 setbuf(stdout, NULL); 623 624 assert(!setrlimit(RLIMIT_MEMLOCK, &r)); 625 626 nr_cpus = bpf_num_possible_cpus(); 627 assert(nr_cpus != -1); 628 printf("nr_cpus:%d\n\n", nr_cpus); 629 630 for (f = 0; f < sizeof(map_flags) / sizeof(*map_flags); f++) { 631 unsigned int tgt_free = (map_flags[f] & BPF_F_NO_COMMON_LRU) ? 632 PERCPU_FREE_TARGET : LOCAL_FREE_TARGET; 633 634 for (t = 0; t < sizeof(map_types) / sizeof(*map_types); t++) { 635 test_lru_sanity0(map_types[t], map_flags[f]); 636 test_lru_sanity1(map_types[t], map_flags[f], tgt_free); 637 test_lru_sanity2(map_types[t], map_flags[f], tgt_free); 638 test_lru_sanity3(map_types[t], map_flags[f], tgt_free); 639 test_lru_sanity4(map_types[t], map_flags[f], tgt_free); 640 test_lru_sanity5(map_types[t], map_flags[f]); 641 test_lru_sanity6(map_types[t], map_flags[f], tgt_free); 642 643 printf("\n"); 644 } 645 } 646 647 return 0; 648 } 649