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