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