1 // SPDX-License-Identifier: GPL-2.0-only 2 /* 3 * Copyright (c) 2016 Facebook 4 */ 5 #define _GNU_SOURCE 6 #include <stdio.h> 7 #include <unistd.h> 8 #include <errno.h> 9 #include <string.h> 10 #include <assert.h> 11 #include <sched.h> 12 #include <stdlib.h> 13 #include <time.h> 14 15 #include <sys/wait.h> 16 17 #include <bpf/bpf.h> 18 #include <bpf/libbpf.h> 19 20 #include "bpf_util.h" 21 #include "../../../include/linux/filter.h" 22 23 #define LOCAL_FREE_TARGET (128) 24 #define PERCPU_FREE_TARGET (4) 25 26 static int nr_cpus; 27 28 static int create_map(int map_type, int map_flags, unsigned int size) 29 { 30 LIBBPF_OPTS(bpf_map_create_opts, opts, .map_flags = map_flags); 31 int map_fd; 32 33 map_fd = bpf_map_create(map_type, NULL, sizeof(unsigned long long), 34 sizeof(unsigned long long), size, &opts); 35 36 if (map_fd == -1) 37 perror("bpf_map_create"); 38 39 return map_fd; 40 } 41 42 static int bpf_map_lookup_elem_with_ref_bit(int fd, unsigned long long key, 43 void *value) 44 { 45 struct bpf_insn insns[] = { 46 BPF_LD_MAP_VALUE(BPF_REG_9, 0, 0), 47 BPF_LD_MAP_FD(BPF_REG_1, fd), 48 BPF_LD_IMM64(BPF_REG_3, key), 49 BPF_MOV64_REG(BPF_REG_2, BPF_REG_10), 50 BPF_ALU64_IMM(BPF_ADD, BPF_REG_2, -8), 51 BPF_STX_MEM(BPF_DW, BPF_REG_2, BPF_REG_3, 0), 52 BPF_EMIT_CALL(BPF_FUNC_map_lookup_elem), 53 BPF_JMP_IMM(BPF_JEQ, BPF_REG_0, 0, 4), 54 BPF_LDX_MEM(BPF_DW, BPF_REG_1, BPF_REG_0, 0), 55 BPF_STX_MEM(BPF_DW, BPF_REG_9, BPF_REG_1, 0), 56 BPF_MOV64_IMM(BPF_REG_0, 42), 57 BPF_JMP_IMM(BPF_JA, 0, 0, 1), 58 BPF_MOV64_IMM(BPF_REG_0, 1), 59 BPF_EXIT_INSN(), 60 }; 61 __u8 data[64] = {}; 62 int mfd, pfd, ret, zero = 0; 63 LIBBPF_OPTS(bpf_test_run_opts, topts, 64 .data_in = data, 65 .data_size_in = sizeof(data), 66 .repeat = 1, 67 ); 68 69 mfd = bpf_map_create(BPF_MAP_TYPE_ARRAY, NULL, sizeof(int), sizeof(__u64), 1, NULL); 70 if (mfd < 0) 71 return -1; 72 73 insns[0].imm = mfd; 74 75 pfd = bpf_prog_load(BPF_PROG_TYPE_SCHED_CLS, NULL, "GPL", insns, ARRAY_SIZE(insns), NULL); 76 if (pfd < 0) { 77 close(mfd); 78 return -1; 79 } 80 81 ret = bpf_prog_test_run_opts(pfd, &topts); 82 if (ret < 0 || topts.retval != 42) { 83 ret = -1; 84 } else { 85 assert(!bpf_map_lookup_elem(mfd, &zero, value)); 86 ret = 0; 87 } 88 close(pfd); 89 close(mfd); 90 return ret; 91 } 92 93 static int map_subset(int map0, int map1) 94 { 95 unsigned long long next_key = 0; 96 unsigned long long value0[nr_cpus], value1[nr_cpus]; 97 int ret; 98 99 while (!bpf_map_get_next_key(map1, &next_key, &next_key)) { 100 assert(!bpf_map_lookup_elem(map1, &next_key, value1)); 101 ret = bpf_map_lookup_elem(map0, &next_key, value0); 102 if (ret) { 103 printf("key:%llu not found from map. %s(%d)\n", 104 next_key, strerror(errno), errno); 105 return 0; 106 } 107 if (value0[0] != value1[0]) { 108 printf("key:%llu value0:%llu != value1:%llu\n", 109 next_key, value0[0], value1[0]); 110 return 0; 111 } 112 } 113 return 1; 114 } 115 116 static int map_equal(int lru_map, int expected) 117 { 118 return map_subset(lru_map, expected) && map_subset(expected, lru_map); 119 } 120 121 static int sched_next_online(int pid, int *next_to_try) 122 { 123 cpu_set_t cpuset; 124 int next = *next_to_try; 125 int ret = -1; 126 127 while (next < nr_cpus) { 128 CPU_ZERO(&cpuset); 129 CPU_SET(next, &cpuset); 130 next++; 131 if (!sched_setaffinity(pid, sizeof(cpuset), &cpuset)) { 132 ret = 0; 133 break; 134 } 135 } 136 137 *next_to_try = next; 138 return ret; 139 } 140 141 /* Derive target_free from map_size, same as bpf_common_lru_populate */ 142 static unsigned int __tgt_size(unsigned int map_size) 143 { 144 return (map_size / nr_cpus) / 2; 145 } 146 147 /* Inverse of how bpf_common_lru_populate derives target_free from map_size. */ 148 static unsigned int __map_size(unsigned int tgt_free) 149 { 150 return tgt_free * nr_cpus * 2; 151 } 152 153 /* Size of the LRU map is 2 154 * Add key=1 (+1 key) 155 * Add key=2 (+1 key) 156 * Lookup Key=1 157 * Add Key=3 158 * => Key=2 will be removed by LRU 159 * Iterate map. Only found key=1 and key=3 160 */ 161 static void test_lru_sanity0(int map_type, int map_flags) 162 { 163 unsigned long long key, value[nr_cpus]; 164 int lru_map_fd, expected_map_fd; 165 int next_cpu = 0; 166 167 printf("%s (map_type:%d map_flags:0x%X): ", __func__, map_type, 168 map_flags); 169 170 assert(sched_next_online(0, &next_cpu) != -1); 171 172 if (map_flags & BPF_F_NO_COMMON_LRU) 173 lru_map_fd = create_map(map_type, map_flags, 2 * nr_cpus); 174 else 175 lru_map_fd = create_map(map_type, map_flags, 2); 176 assert(lru_map_fd != -1); 177 178 expected_map_fd = create_map(BPF_MAP_TYPE_HASH, 0, 2); 179 assert(expected_map_fd != -1); 180 181 value[0] = 1234; 182 183 /* insert key=1 element */ 184 185 key = 1; 186 assert(!bpf_map_update_elem(lru_map_fd, &key, value, BPF_NOEXIST)); 187 assert(!bpf_map_update_elem(expected_map_fd, &key, value, 188 BPF_NOEXIST)); 189 190 /* BPF_NOEXIST means: add new element if it doesn't exist */ 191 assert(bpf_map_update_elem(lru_map_fd, &key, value, BPF_NOEXIST) == -EEXIST); 192 /* key=1 already exists */ 193 194 assert(bpf_map_update_elem(lru_map_fd, &key, value, -1) == -EINVAL); 195 196 /* insert key=2 element */ 197 198 /* check that key=2 is not found */ 199 key = 2; 200 assert(bpf_map_lookup_elem(lru_map_fd, &key, value) == -ENOENT); 201 202 /* BPF_EXIST means: update existing element */ 203 assert(bpf_map_update_elem(lru_map_fd, &key, value, BPF_EXIST) == -ENOENT); 204 /* key=2 is not there */ 205 206 assert(!bpf_map_update_elem(lru_map_fd, &key, value, BPF_NOEXIST)); 207 208 /* insert key=3 element */ 209 210 /* check that key=3 is not found */ 211 key = 3; 212 assert(bpf_map_lookup_elem(lru_map_fd, &key, value) == -ENOENT); 213 214 /* check that key=1 can be found and mark the ref bit to 215 * stop LRU from removing key=1 216 */ 217 key = 1; 218 assert(!bpf_map_lookup_elem_with_ref_bit(lru_map_fd, key, value)); 219 assert(value[0] == 1234); 220 221 key = 3; 222 assert(!bpf_map_update_elem(lru_map_fd, &key, value, BPF_NOEXIST)); 223 assert(!bpf_map_update_elem(expected_map_fd, &key, value, 224 BPF_NOEXIST)); 225 226 /* key=2 has been removed from the LRU */ 227 key = 2; 228 assert(bpf_map_lookup_elem(lru_map_fd, &key, value) == -ENOENT); 229 230 /* lookup elem key=1 and delete it, then check it doesn't exist */ 231 key = 1; 232 assert(!bpf_map_lookup_and_delete_elem(lru_map_fd, &key, &value)); 233 assert(value[0] == 1234); 234 235 /* remove the same element from the expected map */ 236 assert(!bpf_map_delete_elem(expected_map_fd, &key)); 237 238 assert(map_equal(lru_map_fd, expected_map_fd)); 239 240 close(expected_map_fd); 241 close(lru_map_fd); 242 243 printf("Pass\n"); 244 } 245 246 /* Verify that unreferenced elements are recycled before referenced ones. 247 * Insert elements. 248 * Reference a subset of these. 249 * Insert more, enough to trigger recycling. 250 * Verify that unreferenced are recycled. 251 */ 252 static void test_lru_sanity1(int map_type, int map_flags, unsigned int tgt_free) 253 { 254 unsigned long long key, end_key, value[nr_cpus]; 255 int lru_map_fd, expected_map_fd; 256 unsigned int batch_size; 257 unsigned int map_size; 258 int next_cpu = 0; 259 260 if (map_flags & BPF_F_NO_COMMON_LRU) 261 /* This test is only applicable to common LRU list */ 262 return; 263 264 printf("%s (map_type:%d map_flags:0x%X): ", __func__, map_type, 265 map_flags); 266 267 assert(sched_next_online(0, &next_cpu) != -1); 268 269 batch_size = tgt_free / 2; 270 assert(batch_size * 2 == tgt_free); 271 272 map_size = __map_size(tgt_free) + batch_size; 273 lru_map_fd = create_map(map_type, map_flags, map_size); 274 assert(lru_map_fd != -1); 275 276 expected_map_fd = create_map(BPF_MAP_TYPE_HASH, 0, map_size); 277 assert(expected_map_fd != -1); 278 279 value[0] = 1234; 280 281 /* Insert map_size - batch_size keys */ 282 end_key = 1 + __map_size(tgt_free); 283 for (key = 1; key < end_key; key++) 284 assert(!bpf_map_update_elem(lru_map_fd, &key, value, 285 BPF_NOEXIST)); 286 287 /* Lookup 1 to batch_size */ 288 end_key = 1 + batch_size; 289 for (key = 1; key < end_key; key++) { 290 assert(!bpf_map_lookup_elem_with_ref_bit(lru_map_fd, key, value)); 291 assert(!bpf_map_update_elem(expected_map_fd, &key, value, 292 BPF_NOEXIST)); 293 } 294 295 /* Insert another map_size - batch_size keys 296 * Map will contain 1 to batch_size plus these latest, i.e., 297 * => previous 1+batch_size to map_size - batch_size will have been 298 * removed by LRU 299 */ 300 key = 1 + __map_size(tgt_free); 301 end_key = key + __map_size(tgt_free); 302 for (; key < end_key; key++) { 303 assert(!bpf_map_update_elem(lru_map_fd, &key, value, 304 BPF_NOEXIST)); 305 assert(!bpf_map_update_elem(expected_map_fd, &key, value, 306 BPF_NOEXIST)); 307 } 308 309 assert(map_equal(lru_map_fd, expected_map_fd)); 310 311 close(expected_map_fd); 312 close(lru_map_fd); 313 314 printf("Pass\n"); 315 } 316 317 /* Verify that insertions exceeding map size will recycle the oldest. 318 * Verify that unreferenced elements are recycled before referenced. 319 */ 320 static void test_lru_sanity2(int map_type, int map_flags, unsigned int tgt_free) 321 { 322 unsigned long long key, value[nr_cpus]; 323 unsigned long long end_key; 324 int lru_map_fd, expected_map_fd; 325 unsigned int batch_size; 326 unsigned int map_size; 327 int next_cpu = 0; 328 329 if (map_flags & BPF_F_NO_COMMON_LRU) 330 /* This test is only applicable to common LRU list */ 331 return; 332 333 printf("%s (map_type:%d map_flags:0x%X): ", __func__, map_type, 334 map_flags); 335 336 assert(sched_next_online(0, &next_cpu) != -1); 337 338 batch_size = tgt_free / 2; 339 assert(batch_size * 2 == tgt_free); 340 341 map_size = __map_size(tgt_free) + batch_size; 342 lru_map_fd = create_map(map_type, map_flags, map_size); 343 assert(lru_map_fd != -1); 344 345 expected_map_fd = create_map(BPF_MAP_TYPE_HASH, 0, map_size); 346 assert(expected_map_fd != -1); 347 348 value[0] = 1234; 349 350 /* Insert map_size - batch_size keys */ 351 end_key = 1 + __map_size(tgt_free); 352 for (key = 1; key < end_key; key++) 353 assert(!bpf_map_update_elem(lru_map_fd, &key, value, 354 BPF_NOEXIST)); 355 356 /* Any bpf_map_update_elem will require to acquire a new node 357 * from LRU first. 358 * 359 * The local list is running out of free nodes. 360 * It gets from the global LRU list which tries to 361 * shrink the inactive list to get tgt_free 362 * number of free nodes. 363 * 364 * Hence, the oldest key is removed from the LRU list. 365 */ 366 key = 1; 367 if (map_type == BPF_MAP_TYPE_LRU_PERCPU_HASH) { 368 assert(!bpf_map_update_elem(lru_map_fd, &key, value, 369 BPF_NOEXIST)); 370 assert(!bpf_map_delete_elem(lru_map_fd, &key)); 371 } else { 372 assert(bpf_map_update_elem(lru_map_fd, &key, value, 373 BPF_EXIST)); 374 } 375 376 /* Re-insert 1 to batch_size again and do a lookup immediately. 377 */ 378 end_key = 1 + batch_size; 379 value[0] = 4321; 380 for (key = 1; key < end_key; key++) { 381 assert(bpf_map_lookup_elem(lru_map_fd, &key, value) == -ENOENT); 382 assert(!bpf_map_update_elem(lru_map_fd, &key, value, 383 BPF_NOEXIST)); 384 assert(!bpf_map_lookup_elem_with_ref_bit(lru_map_fd, key, value)); 385 assert(value[0] == 4321); 386 assert(!bpf_map_update_elem(expected_map_fd, &key, value, 387 BPF_NOEXIST)); 388 } 389 390 value[0] = 1234; 391 392 /* Insert batch_size new elements */ 393 key = 1 + __map_size(tgt_free); 394 end_key = key + batch_size; 395 for (; key < end_key; key++) 396 /* These newly added but not referenced keys will be 397 * gone during the next LRU shrink. 398 */ 399 assert(!bpf_map_update_elem(lru_map_fd, &key, value, 400 BPF_NOEXIST)); 401 402 /* Insert map_size - batch_size elements */ 403 end_key += __map_size(tgt_free); 404 for (; key < end_key; key++) { 405 assert(!bpf_map_update_elem(lru_map_fd, &key, value, 406 BPF_NOEXIST)); 407 assert(!bpf_map_update_elem(expected_map_fd, &key, value, 408 BPF_NOEXIST)); 409 } 410 411 assert(map_equal(lru_map_fd, expected_map_fd)); 412 413 close(expected_map_fd); 414 close(lru_map_fd); 415 416 printf("Pass\n"); 417 } 418 419 /* Test the active/inactive list rotation 420 * 421 * Fill the whole map, deplete the free list. 422 * Reference all except the last lru->target_free elements. 423 * Insert lru->target_free new elements. This triggers one shrink. 424 * Verify that the non-referenced elements are replaced. 425 */ 426 static void test_lru_sanity3(int map_type, int map_flags, unsigned int tgt_free) 427 { 428 unsigned long long key, end_key, value[nr_cpus]; 429 int lru_map_fd, expected_map_fd; 430 unsigned int batch_size; 431 unsigned int map_size; 432 int next_cpu = 0; 433 434 if (map_flags & BPF_F_NO_COMMON_LRU) 435 /* This test is only applicable to common LRU list */ 436 return; 437 438 printf("%s (map_type:%d map_flags:0x%X): ", __func__, map_type, 439 map_flags); 440 441 assert(sched_next_online(0, &next_cpu) != -1); 442 443 batch_size = __tgt_size(tgt_free); 444 445 map_size = tgt_free * 2; 446 lru_map_fd = create_map(map_type, map_flags, map_size); 447 assert(lru_map_fd != -1); 448 449 expected_map_fd = create_map(BPF_MAP_TYPE_HASH, 0, map_size); 450 assert(expected_map_fd != -1); 451 452 value[0] = 1234; 453 454 /* Fill the map */ 455 end_key = 1 + map_size; 456 for (key = 1; key < end_key; key++) 457 assert(!bpf_map_update_elem(lru_map_fd, &key, value, 458 BPF_NOEXIST)); 459 460 /* Reference all but the last batch_size */ 461 end_key = 1 + map_size - batch_size; 462 for (key = 1; key < end_key; key++) { 463 assert(!bpf_map_lookup_elem_with_ref_bit(lru_map_fd, key, value)); 464 assert(!bpf_map_update_elem(expected_map_fd, &key, value, 465 BPF_NOEXIST)); 466 } 467 468 /* Insert new batch_size: replaces the non-referenced elements */ 469 key = 2 * tgt_free + 1; 470 end_key = key + batch_size; 471 for (; key < end_key; key++) { 472 assert(!bpf_map_update_elem(lru_map_fd, &key, value, 473 BPF_NOEXIST)); 474 assert(!bpf_map_update_elem(expected_map_fd, &key, value, 475 BPF_NOEXIST)); 476 } 477 478 assert(map_equal(lru_map_fd, expected_map_fd)); 479 480 close(expected_map_fd); 481 close(lru_map_fd); 482 483 printf("Pass\n"); 484 } 485 486 /* Test deletion */ 487 static void test_lru_sanity4(int map_type, int map_flags, unsigned int tgt_free) 488 { 489 int lru_map_fd, expected_map_fd; 490 unsigned long long key, value[nr_cpus]; 491 unsigned long long end_key; 492 int next_cpu = 0; 493 494 printf("%s (map_type:%d map_flags:0x%X): ", __func__, map_type, 495 map_flags); 496 497 assert(sched_next_online(0, &next_cpu) != -1); 498 499 if (map_flags & BPF_F_NO_COMMON_LRU) 500 lru_map_fd = create_map(map_type, map_flags, 501 3 * tgt_free * nr_cpus); 502 else 503 lru_map_fd = create_map(map_type, map_flags, 504 3 * __map_size(tgt_free)); 505 assert(lru_map_fd != -1); 506 507 expected_map_fd = create_map(BPF_MAP_TYPE_HASH, 0, 508 3 * tgt_free); 509 assert(expected_map_fd != -1); 510 511 value[0] = 1234; 512 513 for (key = 1; key <= 2 * tgt_free; key++) 514 assert(!bpf_map_update_elem(lru_map_fd, &key, value, 515 BPF_NOEXIST)); 516 517 key = 1; 518 assert(bpf_map_update_elem(lru_map_fd, &key, value, BPF_NOEXIST)); 519 520 for (key = 1; key <= tgt_free; key++) { 521 assert(!bpf_map_lookup_elem_with_ref_bit(lru_map_fd, key, value)); 522 assert(!bpf_map_update_elem(expected_map_fd, &key, value, 523 BPF_NOEXIST)); 524 } 525 526 for (; key <= 2 * tgt_free; key++) { 527 assert(!bpf_map_delete_elem(lru_map_fd, &key)); 528 assert(bpf_map_delete_elem(lru_map_fd, &key)); 529 } 530 531 end_key = key + 2 * tgt_free; 532 for (; key < end_key; key++) { 533 assert(!bpf_map_update_elem(lru_map_fd, &key, value, 534 BPF_NOEXIST)); 535 assert(!bpf_map_update_elem(expected_map_fd, &key, value, 536 BPF_NOEXIST)); 537 } 538 539 assert(map_equal(lru_map_fd, expected_map_fd)); 540 541 close(expected_map_fd); 542 close(lru_map_fd); 543 544 printf("Pass\n"); 545 } 546 547 static void do_test_lru_sanity5(unsigned long long last_key, int map_fd) 548 { 549 unsigned long long key, value[nr_cpus]; 550 551 /* Ensure the last key inserted by previous CPU can be found */ 552 assert(!bpf_map_lookup_elem_with_ref_bit(map_fd, last_key, value)); 553 value[0] = 1234; 554 555 key = last_key + 1; 556 assert(!bpf_map_update_elem(map_fd, &key, value, BPF_NOEXIST)); 557 assert(!bpf_map_lookup_elem_with_ref_bit(map_fd, key, value)); 558 559 /* Cannot find the last key because it was removed by LRU */ 560 assert(bpf_map_lookup_elem(map_fd, &last_key, value) == -ENOENT); 561 } 562 563 /* Test map with only one element */ 564 static void test_lru_sanity5(int map_type, int map_flags) 565 { 566 unsigned long long key, value[nr_cpus]; 567 int next_cpu = 0; 568 int map_fd; 569 570 if (map_flags & BPF_F_NO_COMMON_LRU) 571 return; 572 573 printf("%s (map_type:%d map_flags:0x%X): ", __func__, map_type, 574 map_flags); 575 576 map_fd = create_map(map_type, map_flags, 1); 577 assert(map_fd != -1); 578 579 value[0] = 1234; 580 key = 0; 581 assert(!bpf_map_update_elem(map_fd, &key, value, BPF_NOEXIST)); 582 583 while (sched_next_online(0, &next_cpu) != -1) { 584 pid_t pid; 585 586 pid = fork(); 587 if (pid == 0) { 588 do_test_lru_sanity5(key, map_fd); 589 exit(0); 590 } else if (pid == -1) { 591 printf("couldn't spawn process to test key:%llu\n", 592 key); 593 exit(1); 594 } else { 595 int status; 596 597 assert(waitpid(pid, &status, 0) == pid); 598 assert(status == 0); 599 key++; 600 } 601 } 602 603 close(map_fd); 604 /* At least one key should be tested */ 605 assert(key > 0); 606 607 printf("Pass\n"); 608 } 609 610 /* Test list rotation for BPF_F_NO_COMMON_LRU map */ 611 static void test_lru_sanity6(int map_type, int map_flags, int tgt_free) 612 { 613 int lru_map_fd, expected_map_fd; 614 unsigned long long key, value[nr_cpus]; 615 unsigned int map_size = tgt_free * 2; 616 int next_cpu = 0; 617 618 if (!(map_flags & BPF_F_NO_COMMON_LRU)) 619 return; 620 621 printf("%s (map_type:%d map_flags:0x%X): ", __func__, map_type, 622 map_flags); 623 624 assert(sched_next_online(0, &next_cpu) != -1); 625 626 expected_map_fd = create_map(BPF_MAP_TYPE_HASH, 0, map_size); 627 assert(expected_map_fd != -1); 628 629 lru_map_fd = create_map(map_type, map_flags, map_size * nr_cpus); 630 assert(lru_map_fd != -1); 631 632 value[0] = 1234; 633 634 for (key = 1; key <= tgt_free; key++) { 635 assert(!bpf_map_update_elem(lru_map_fd, &key, value, 636 BPF_NOEXIST)); 637 assert(!bpf_map_update_elem(expected_map_fd, &key, value, 638 BPF_NOEXIST)); 639 } 640 641 for (; key <= tgt_free * 2; key++) { 642 unsigned long long stable_key; 643 644 /* Make ref bit sticky for key: [1, tgt_free] */ 645 for (stable_key = 1; stable_key <= tgt_free; stable_key++) { 646 /* Mark the ref bit */ 647 assert(!bpf_map_lookup_elem_with_ref_bit(lru_map_fd, 648 stable_key, value)); 649 } 650 assert(!bpf_map_update_elem(lru_map_fd, &key, value, 651 BPF_NOEXIST)); 652 } 653 654 for (; key <= tgt_free * 3; key++) { 655 assert(!bpf_map_update_elem(lru_map_fd, &key, value, 656 BPF_NOEXIST)); 657 assert(!bpf_map_update_elem(expected_map_fd, &key, value, 658 BPF_NOEXIST)); 659 } 660 661 assert(map_equal(lru_map_fd, expected_map_fd)); 662 663 close(expected_map_fd); 664 close(lru_map_fd); 665 666 printf("Pass\n"); 667 } 668 669 /* Size of the LRU map is 2 670 * Add key=1 (+1 key) 671 * Add key=2 (+1 key) 672 * Lookup Key=1 (datapath) 673 * Lookup Key=2 (syscall) 674 * Add Key=3 675 * => Key=2 will be removed by LRU 676 * Iterate map. Only found key=1 and key=3 677 */ 678 static void test_lru_sanity7(int map_type, int map_flags) 679 { 680 unsigned long long key, value[nr_cpus]; 681 int lru_map_fd, expected_map_fd; 682 int next_cpu = 0; 683 684 printf("%s (map_type:%d map_flags:0x%X): ", __func__, map_type, 685 map_flags); 686 687 assert(sched_next_online(0, &next_cpu) != -1); 688 689 if (map_flags & BPF_F_NO_COMMON_LRU) 690 lru_map_fd = create_map(map_type, map_flags, 2 * nr_cpus); 691 else 692 lru_map_fd = create_map(map_type, map_flags, 2); 693 assert(lru_map_fd != -1); 694 695 expected_map_fd = create_map(BPF_MAP_TYPE_HASH, 0, 2); 696 assert(expected_map_fd != -1); 697 698 value[0] = 1234; 699 700 /* insert key=1 element */ 701 702 key = 1; 703 assert(!bpf_map_update_elem(lru_map_fd, &key, value, BPF_NOEXIST)); 704 assert(!bpf_map_update_elem(expected_map_fd, &key, value, 705 BPF_NOEXIST)); 706 707 /* BPF_NOEXIST means: add new element if it doesn't exist */ 708 assert(bpf_map_update_elem(lru_map_fd, &key, value, BPF_NOEXIST) == -EEXIST); 709 /* key=1 already exists */ 710 711 /* insert key=2 element */ 712 713 /* check that key=2 is not found */ 714 key = 2; 715 assert(bpf_map_lookup_elem(lru_map_fd, &key, value) == -ENOENT); 716 717 /* BPF_EXIST means: update existing element */ 718 assert(bpf_map_update_elem(lru_map_fd, &key, value, BPF_EXIST) == -ENOENT); 719 /* key=2 is not there */ 720 721 assert(!bpf_map_update_elem(lru_map_fd, &key, value, BPF_NOEXIST)); 722 723 /* insert key=3 element */ 724 725 /* check that key=3 is not found */ 726 key = 3; 727 assert(bpf_map_lookup_elem(lru_map_fd, &key, value) == -ENOENT); 728 729 /* check that key=1 can be found and mark the ref bit to 730 * stop LRU from removing key=1 731 */ 732 key = 1; 733 assert(!bpf_map_lookup_elem_with_ref_bit(lru_map_fd, key, value)); 734 assert(value[0] == 1234); 735 736 /* check that key=2 can be found and do _not_ mark ref bit. 737 * this will be evicted on next update. 738 */ 739 key = 2; 740 assert(!bpf_map_lookup_elem(lru_map_fd, &key, value)); 741 assert(value[0] == 1234); 742 743 key = 3; 744 assert(!bpf_map_update_elem(lru_map_fd, &key, value, BPF_NOEXIST)); 745 assert(!bpf_map_update_elem(expected_map_fd, &key, value, 746 BPF_NOEXIST)); 747 748 /* key=2 has been removed from the LRU */ 749 key = 2; 750 assert(bpf_map_lookup_elem(lru_map_fd, &key, value) == -ENOENT); 751 752 assert(map_equal(lru_map_fd, expected_map_fd)); 753 754 close(expected_map_fd); 755 close(lru_map_fd); 756 757 printf("Pass\n"); 758 } 759 760 /* Size of the LRU map is 2 761 * Add key=1 (+1 key) 762 * Add key=2 (+1 key) 763 * Lookup Key=1 (syscall) 764 * Lookup Key=2 (datapath) 765 * Add Key=3 766 * => Key=1 will be removed by LRU 767 * Iterate map. Only found key=2 and key=3 768 */ 769 static void test_lru_sanity8(int map_type, int map_flags) 770 { 771 unsigned long long key, value[nr_cpus]; 772 int lru_map_fd, expected_map_fd; 773 int next_cpu = 0; 774 775 printf("%s (map_type:%d map_flags:0x%X): ", __func__, map_type, 776 map_flags); 777 778 assert(sched_next_online(0, &next_cpu) != -1); 779 780 if (map_flags & BPF_F_NO_COMMON_LRU) 781 lru_map_fd = create_map(map_type, map_flags, 2 * nr_cpus); 782 else 783 lru_map_fd = create_map(map_type, map_flags, 2); 784 assert(lru_map_fd != -1); 785 786 expected_map_fd = create_map(BPF_MAP_TYPE_HASH, 0, 2); 787 assert(expected_map_fd != -1); 788 789 value[0] = 1234; 790 791 /* insert key=1 element */ 792 793 key = 1; 794 assert(!bpf_map_update_elem(lru_map_fd, &key, value, BPF_NOEXIST)); 795 796 /* BPF_NOEXIST means: add new element if it doesn't exist */ 797 assert(bpf_map_update_elem(lru_map_fd, &key, value, BPF_NOEXIST) == -EEXIST); 798 /* key=1 already exists */ 799 800 /* insert key=2 element */ 801 802 /* check that key=2 is not found */ 803 key = 2; 804 assert(bpf_map_lookup_elem(lru_map_fd, &key, value) == -ENOENT); 805 806 /* BPF_EXIST means: update existing element */ 807 assert(bpf_map_update_elem(lru_map_fd, &key, value, BPF_EXIST) == -ENOENT); 808 /* key=2 is not there */ 809 810 assert(!bpf_map_update_elem(lru_map_fd, &key, value, BPF_NOEXIST)); 811 assert(!bpf_map_update_elem(expected_map_fd, &key, value, 812 BPF_NOEXIST)); 813 814 /* insert key=3 element */ 815 816 /* check that key=3 is not found */ 817 key = 3; 818 assert(bpf_map_lookup_elem(lru_map_fd, &key, value) == -ENOENT); 819 820 /* check that key=1 can be found and do _not_ mark ref bit. 821 * this will be evicted on next update. 822 */ 823 key = 1; 824 assert(!bpf_map_lookup_elem(lru_map_fd, &key, value)); 825 assert(value[0] == 1234); 826 827 /* check that key=2 can be found and mark the ref bit to 828 * stop LRU from removing key=2 829 */ 830 key = 2; 831 assert(!bpf_map_lookup_elem_with_ref_bit(lru_map_fd, key, value)); 832 assert(value[0] == 1234); 833 834 key = 3; 835 assert(!bpf_map_update_elem(lru_map_fd, &key, value, BPF_NOEXIST)); 836 assert(!bpf_map_update_elem(expected_map_fd, &key, value, 837 BPF_NOEXIST)); 838 839 /* key=1 has been removed from the LRU */ 840 key = 1; 841 assert(bpf_map_lookup_elem(lru_map_fd, &key, value) == -ENOENT); 842 843 assert(map_equal(lru_map_fd, expected_map_fd)); 844 845 close(expected_map_fd); 846 close(lru_map_fd); 847 848 printf("Pass\n"); 849 } 850 851 int main(int argc, char **argv) 852 { 853 int map_types[] = {BPF_MAP_TYPE_LRU_HASH, 854 BPF_MAP_TYPE_LRU_PERCPU_HASH}; 855 int map_flags[] = {0, BPF_F_NO_COMMON_LRU}; 856 int t, f; 857 858 setbuf(stdout, NULL); 859 860 nr_cpus = bpf_num_possible_cpus(); 861 assert(nr_cpus != -1); 862 printf("nr_cpus:%d\n\n", nr_cpus); 863 864 /* Use libbpf 1.0 API mode */ 865 libbpf_set_strict_mode(LIBBPF_STRICT_ALL); 866 867 for (f = 0; f < ARRAY_SIZE(map_flags); f++) { 868 unsigned int tgt_free = (map_flags[f] & BPF_F_NO_COMMON_LRU) ? 869 PERCPU_FREE_TARGET : LOCAL_FREE_TARGET; 870 871 for (t = 0; t < ARRAY_SIZE(map_types); t++) { 872 test_lru_sanity0(map_types[t], map_flags[f]); 873 test_lru_sanity1(map_types[t], map_flags[f], tgt_free); 874 test_lru_sanity2(map_types[t], map_flags[f], tgt_free); 875 test_lru_sanity3(map_types[t], map_flags[f], tgt_free); 876 test_lru_sanity4(map_types[t], map_flags[f], tgt_free); 877 test_lru_sanity5(map_types[t], map_flags[f]); 878 test_lru_sanity6(map_types[t], map_flags[f], tgt_free); 879 test_lru_sanity7(map_types[t], map_flags[f]); 880 test_lru_sanity8(map_types[t], map_flags[f]); 881 882 printf("\n"); 883 } 884 } 885 886 return 0; 887 } 888