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