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