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