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