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