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