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