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 #include <sys/resource.h> 20 21 #include <bpf/bpf.h> 22 #include "bpf_util.h" 23 24 #define LOCAL_FREE_TARGET (128) 25 #define PERCPU_FREE_TARGET (16) 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 map_subset(int map0, int map1) 43 { 44 unsigned long long next_key = 0; 45 unsigned long long value0[nr_cpus], value1[nr_cpus]; 46 int ret; 47 48 while (!bpf_map_get_next_key(map1, &next_key, &next_key)) { 49 assert(!bpf_map_lookup_elem(map1, &next_key, value1)); 50 ret = bpf_map_lookup_elem(map0, &next_key, value0); 51 if (ret) { 52 printf("key:%llu not found from map. %s(%d)\n", 53 next_key, strerror(errno), errno); 54 return 0; 55 } 56 if (value0[0] != value1[0]) { 57 printf("key:%llu value0:%llu != value1:%llu\n", 58 next_key, value0[0], value1[0]); 59 return 0; 60 } 61 } 62 return 1; 63 } 64 65 static int map_equal(int lru_map, int expected) 66 { 67 return map_subset(lru_map, expected) && map_subset(expected, lru_map); 68 } 69 70 static int sched_next_online(int pid, int *next_to_try) 71 { 72 cpu_set_t cpuset; 73 int next = *next_to_try; 74 int ret = -1; 75 76 while (next < nr_cpus) { 77 CPU_ZERO(&cpuset); 78 CPU_SET(next++, &cpuset); 79 if (!sched_setaffinity(pid, sizeof(cpuset), &cpuset)) { 80 ret = 0; 81 break; 82 } 83 } 84 85 *next_to_try = next; 86 return ret; 87 } 88 89 /* Size of the LRU amp is 2 90 * Add key=1 (+1 key) 91 * Add key=2 (+1 key) 92 * Lookup Key=1 93 * Add Key=3 94 * => Key=2 will be removed by LRU 95 * Iterate map. Only found key=1 and key=3 96 */ 97 static void test_lru_sanity0(int map_type, int map_flags) 98 { 99 unsigned long long key, value[nr_cpus]; 100 int lru_map_fd, expected_map_fd; 101 int next_cpu = 0; 102 103 printf("%s (map_type:%d map_flags:0x%X): ", __func__, map_type, 104 map_flags); 105 106 assert(sched_next_online(0, &next_cpu) != -1); 107 108 if (map_flags & BPF_F_NO_COMMON_LRU) 109 lru_map_fd = create_map(map_type, map_flags, 2 * nr_cpus); 110 else 111 lru_map_fd = create_map(map_type, map_flags, 2); 112 assert(lru_map_fd != -1); 113 114 expected_map_fd = create_map(BPF_MAP_TYPE_HASH, 0, 2); 115 assert(expected_map_fd != -1); 116 117 value[0] = 1234; 118 119 /* insert key=1 element */ 120 121 key = 1; 122 assert(!bpf_map_update_elem(lru_map_fd, &key, value, BPF_NOEXIST)); 123 assert(!bpf_map_update_elem(expected_map_fd, &key, value, 124 BPF_NOEXIST)); 125 126 /* BPF_NOEXIST means: add new element if it doesn't exist */ 127 assert(bpf_map_update_elem(lru_map_fd, &key, value, BPF_NOEXIST) == -1 128 /* key=1 already exists */ 129 && errno == EEXIST); 130 131 assert(bpf_map_update_elem(lru_map_fd, &key, value, -1) == -1 && 132 errno == EINVAL); 133 134 /* insert key=2 element */ 135 136 /* check that key=2 is not found */ 137 key = 2; 138 assert(bpf_map_lookup_elem(lru_map_fd, &key, value) == -1 && 139 errno == ENOENT); 140 141 /* BPF_EXIST means: update existing element */ 142 assert(bpf_map_update_elem(lru_map_fd, &key, value, BPF_EXIST) == -1 && 143 /* key=2 is not there */ 144 errno == ENOENT); 145 146 assert(!bpf_map_update_elem(lru_map_fd, &key, value, BPF_NOEXIST)); 147 148 /* insert key=3 element */ 149 150 /* check that key=3 is not found */ 151 key = 3; 152 assert(bpf_map_lookup_elem(lru_map_fd, &key, value) == -1 && 153 errno == ENOENT); 154 155 /* check that key=1 can be found and mark the ref bit to 156 * stop LRU from removing key=1 157 */ 158 key = 1; 159 assert(!bpf_map_lookup_elem(lru_map_fd, &key, value)); 160 assert(value[0] == 1234); 161 162 key = 3; 163 assert(!bpf_map_update_elem(lru_map_fd, &key, value, BPF_NOEXIST)); 164 assert(!bpf_map_update_elem(expected_map_fd, &key, value, 165 BPF_NOEXIST)); 166 167 /* key=2 has been removed from the LRU */ 168 key = 2; 169 assert(bpf_map_lookup_elem(lru_map_fd, &key, value) == -1); 170 171 assert(map_equal(lru_map_fd, expected_map_fd)); 172 173 close(expected_map_fd); 174 close(lru_map_fd); 175 176 printf("Pass\n"); 177 } 178 179 /* Size of the LRU map is 1.5*tgt_free 180 * Insert 1 to tgt_free (+tgt_free keys) 181 * Lookup 1 to tgt_free/2 182 * Insert 1+tgt_free to 2*tgt_free (+tgt_free keys) 183 * => 1+tgt_free/2 to LOCALFREE_TARGET will be removed by LRU 184 */ 185 static void test_lru_sanity1(int map_type, int map_flags, unsigned int tgt_free) 186 { 187 unsigned long long key, end_key, value[nr_cpus]; 188 int lru_map_fd, expected_map_fd; 189 unsigned int batch_size; 190 unsigned int map_size; 191 int next_cpu = 0; 192 193 if (map_flags & BPF_F_NO_COMMON_LRU) 194 /* Ther percpu lru list (i.e each cpu has its own LRU 195 * list) does not have a local free list. Hence, 196 * it will only free old nodes till there is no free 197 * from the LRU list. Hence, this test does not apply 198 * to BPF_F_NO_COMMON_LRU 199 */ 200 return; 201 202 printf("%s (map_type:%d map_flags:0x%X): ", __func__, map_type, 203 map_flags); 204 205 assert(sched_next_online(0, &next_cpu) != -1); 206 207 batch_size = tgt_free / 2; 208 assert(batch_size * 2 == tgt_free); 209 210 map_size = tgt_free + batch_size; 211 lru_map_fd = create_map(map_type, map_flags, map_size); 212 assert(lru_map_fd != -1); 213 214 expected_map_fd = create_map(BPF_MAP_TYPE_HASH, 0, map_size); 215 assert(expected_map_fd != -1); 216 217 value[0] = 1234; 218 219 /* Insert 1 to tgt_free (+tgt_free keys) */ 220 end_key = 1 + tgt_free; 221 for (key = 1; key < end_key; key++) 222 assert(!bpf_map_update_elem(lru_map_fd, &key, value, 223 BPF_NOEXIST)); 224 225 /* Lookup 1 to tgt_free/2 */ 226 end_key = 1 + batch_size; 227 for (key = 1; key < end_key; key++) { 228 assert(!bpf_map_lookup_elem(lru_map_fd, &key, value)); 229 assert(!bpf_map_update_elem(expected_map_fd, &key, value, 230 BPF_NOEXIST)); 231 } 232 233 /* Insert 1+tgt_free to 2*tgt_free 234 * => 1+tgt_free/2 to LOCALFREE_TARGET will be 235 * removed by LRU 236 */ 237 key = 1 + tgt_free; 238 end_key = key + tgt_free; 239 for (; key < end_key; key++) { 240 assert(!bpf_map_update_elem(lru_map_fd, &key, value, 241 BPF_NOEXIST)); 242 assert(!bpf_map_update_elem(expected_map_fd, &key, value, 243 BPF_NOEXIST)); 244 } 245 246 assert(map_equal(lru_map_fd, expected_map_fd)); 247 248 close(expected_map_fd); 249 close(lru_map_fd); 250 251 printf("Pass\n"); 252 } 253 254 /* Size of the LRU map 1.5 * tgt_free 255 * Insert 1 to tgt_free (+tgt_free keys) 256 * Update 1 to tgt_free/2 257 * => The original 1 to tgt_free/2 will be removed due to 258 * the LRU shrink process 259 * Re-insert 1 to tgt_free/2 again and do a lookup immeidately 260 * Insert 1+tgt_free to tgt_free*3/2 261 * Insert 1+tgt_free*3/2 to tgt_free*5/2 262 * => Key 1+tgt_free to tgt_free*3/2 263 * will be removed from LRU because it has never 264 * been lookup and ref bit is not set 265 */ 266 static void test_lru_sanity2(int map_type, int map_flags, unsigned int tgt_free) 267 { 268 unsigned long long key, value[nr_cpus]; 269 unsigned long long end_key; 270 int lru_map_fd, expected_map_fd; 271 unsigned int batch_size; 272 unsigned int map_size; 273 int next_cpu = 0; 274 275 if (map_flags & BPF_F_NO_COMMON_LRU) 276 /* Ther percpu lru list (i.e each cpu has its own LRU 277 * list) does not have a local free list. Hence, 278 * it will only free old nodes till there is no free 279 * from the LRU list. Hence, this test does not apply 280 * to BPF_F_NO_COMMON_LRU 281 */ 282 return; 283 284 printf("%s (map_type:%d map_flags:0x%X): ", __func__, map_type, 285 map_flags); 286 287 assert(sched_next_online(0, &next_cpu) != -1); 288 289 batch_size = tgt_free / 2; 290 assert(batch_size * 2 == tgt_free); 291 292 map_size = tgt_free + batch_size; 293 if (map_flags & BPF_F_NO_COMMON_LRU) 294 lru_map_fd = create_map(map_type, map_flags, 295 map_size * nr_cpus); 296 else 297 lru_map_fd = create_map(map_type, map_flags, map_size); 298 assert(lru_map_fd != -1); 299 300 expected_map_fd = create_map(BPF_MAP_TYPE_HASH, 0, map_size); 301 assert(expected_map_fd != -1); 302 303 value[0] = 1234; 304 305 /* Insert 1 to tgt_free (+tgt_free keys) */ 306 end_key = 1 + tgt_free; 307 for (key = 1; key < end_key; key++) 308 assert(!bpf_map_update_elem(lru_map_fd, &key, value, 309 BPF_NOEXIST)); 310 311 /* Any bpf_map_update_elem will require to acquire a new node 312 * from LRU first. 313 * 314 * The local list is running out of free nodes. 315 * It gets from the global LRU list which tries to 316 * shrink the inactive list to get tgt_free 317 * number of free nodes. 318 * 319 * Hence, the oldest key 1 to tgt_free/2 320 * are removed from the LRU list. 321 */ 322 key = 1; 323 if (map_type == BPF_MAP_TYPE_LRU_PERCPU_HASH) { 324 assert(!bpf_map_update_elem(lru_map_fd, &key, value, 325 BPF_NOEXIST)); 326 assert(!bpf_map_delete_elem(lru_map_fd, &key)); 327 } else { 328 assert(bpf_map_update_elem(lru_map_fd, &key, value, 329 BPF_EXIST)); 330 } 331 332 /* Re-insert 1 to tgt_free/2 again and do a lookup 333 * immeidately. 334 */ 335 end_key = 1 + batch_size; 336 value[0] = 4321; 337 for (key = 1; key < end_key; key++) { 338 assert(bpf_map_lookup_elem(lru_map_fd, &key, value)); 339 assert(!bpf_map_update_elem(lru_map_fd, &key, value, 340 BPF_NOEXIST)); 341 assert(!bpf_map_lookup_elem(lru_map_fd, &key, value)); 342 assert(value[0] == 4321); 343 assert(!bpf_map_update_elem(expected_map_fd, &key, value, 344 BPF_NOEXIST)); 345 } 346 347 value[0] = 1234; 348 349 /* Insert 1+tgt_free to tgt_free*3/2 */ 350 end_key = 1 + tgt_free + batch_size; 351 for (key = 1 + tgt_free; key < end_key; key++) 352 /* These newly added but not referenced keys will be 353 * gone during the next LRU shrink. 354 */ 355 assert(!bpf_map_update_elem(lru_map_fd, &key, value, 356 BPF_NOEXIST)); 357 358 /* Insert 1+tgt_free*3/2 to tgt_free*5/2 */ 359 end_key = key + tgt_free; 360 for (; key < end_key; key++) { 361 assert(!bpf_map_update_elem(lru_map_fd, &key, value, 362 BPF_NOEXIST)); 363 assert(!bpf_map_update_elem(expected_map_fd, &key, value, 364 BPF_NOEXIST)); 365 } 366 367 assert(map_equal(lru_map_fd, expected_map_fd)); 368 369 close(expected_map_fd); 370 close(lru_map_fd); 371 372 printf("Pass\n"); 373 } 374 375 /* Size of the LRU map is 2*tgt_free 376 * It is to test the active/inactive list rotation 377 * Insert 1 to 2*tgt_free (+2*tgt_free keys) 378 * Lookup key 1 to tgt_free*3/2 379 * Add 1+2*tgt_free to tgt_free*5/2 (+tgt_free/2 keys) 380 * => key 1+tgt_free*3/2 to 2*tgt_free are removed from LRU 381 */ 382 static void test_lru_sanity3(int map_type, int map_flags, unsigned int tgt_free) 383 { 384 unsigned long long key, end_key, value[nr_cpus]; 385 int lru_map_fd, expected_map_fd; 386 unsigned int batch_size; 387 unsigned int map_size; 388 int next_cpu = 0; 389 390 printf("%s (map_type:%d map_flags:0x%X): ", __func__, map_type, 391 map_flags); 392 393 assert(sched_next_online(0, &next_cpu) != -1); 394 395 batch_size = tgt_free / 2; 396 assert(batch_size * 2 == tgt_free); 397 398 map_size = tgt_free * 2; 399 if (map_flags & BPF_F_NO_COMMON_LRU) 400 lru_map_fd = create_map(map_type, map_flags, 401 map_size * nr_cpus); 402 else 403 lru_map_fd = create_map(map_type, map_flags, map_size); 404 assert(lru_map_fd != -1); 405 406 expected_map_fd = create_map(BPF_MAP_TYPE_HASH, 0, map_size); 407 assert(expected_map_fd != -1); 408 409 value[0] = 1234; 410 411 /* Insert 1 to 2*tgt_free (+2*tgt_free keys) */ 412 end_key = 1 + (2 * tgt_free); 413 for (key = 1; key < end_key; key++) 414 assert(!bpf_map_update_elem(lru_map_fd, &key, value, 415 BPF_NOEXIST)); 416 417 /* Lookup key 1 to tgt_free*3/2 */ 418 end_key = tgt_free + batch_size; 419 for (key = 1; key < end_key; key++) { 420 assert(!bpf_map_lookup_elem(lru_map_fd, &key, value)); 421 assert(!bpf_map_update_elem(expected_map_fd, &key, value, 422 BPF_NOEXIST)); 423 } 424 425 /* Add 1+2*tgt_free to tgt_free*5/2 426 * (+tgt_free/2 keys) 427 */ 428 key = 2 * tgt_free + 1; 429 end_key = key + batch_size; 430 for (; key < end_key; key++) { 431 assert(!bpf_map_update_elem(lru_map_fd, &key, value, 432 BPF_NOEXIST)); 433 assert(!bpf_map_update_elem(expected_map_fd, &key, value, 434 BPF_NOEXIST)); 435 } 436 437 assert(map_equal(lru_map_fd, expected_map_fd)); 438 439 close(expected_map_fd); 440 close(lru_map_fd); 441 442 printf("Pass\n"); 443 } 444 445 /* Test deletion */ 446 static void test_lru_sanity4(int map_type, int map_flags, unsigned int tgt_free) 447 { 448 int lru_map_fd, expected_map_fd; 449 unsigned long long key, value[nr_cpus]; 450 unsigned long long end_key; 451 int next_cpu = 0; 452 453 printf("%s (map_type:%d map_flags:0x%X): ", __func__, map_type, 454 map_flags); 455 456 assert(sched_next_online(0, &next_cpu) != -1); 457 458 if (map_flags & BPF_F_NO_COMMON_LRU) 459 lru_map_fd = create_map(map_type, map_flags, 460 3 * tgt_free * nr_cpus); 461 else 462 lru_map_fd = create_map(map_type, map_flags, 3 * tgt_free); 463 assert(lru_map_fd != -1); 464 465 expected_map_fd = create_map(BPF_MAP_TYPE_HASH, 0, 466 3 * tgt_free); 467 assert(expected_map_fd != -1); 468 469 value[0] = 1234; 470 471 for (key = 1; key <= 2 * tgt_free; key++) 472 assert(!bpf_map_update_elem(lru_map_fd, &key, value, 473 BPF_NOEXIST)); 474 475 key = 1; 476 assert(bpf_map_update_elem(lru_map_fd, &key, value, BPF_NOEXIST)); 477 478 for (key = 1; key <= tgt_free; key++) { 479 assert(!bpf_map_lookup_elem(lru_map_fd, &key, value)); 480 assert(!bpf_map_update_elem(expected_map_fd, &key, value, 481 BPF_NOEXIST)); 482 } 483 484 for (; key <= 2 * tgt_free; key++) { 485 assert(!bpf_map_delete_elem(lru_map_fd, &key)); 486 assert(bpf_map_delete_elem(lru_map_fd, &key)); 487 } 488 489 end_key = key + 2 * tgt_free; 490 for (; key < end_key; key++) { 491 assert(!bpf_map_update_elem(lru_map_fd, &key, value, 492 BPF_NOEXIST)); 493 assert(!bpf_map_update_elem(expected_map_fd, &key, value, 494 BPF_NOEXIST)); 495 } 496 497 assert(map_equal(lru_map_fd, expected_map_fd)); 498 499 close(expected_map_fd); 500 close(lru_map_fd); 501 502 printf("Pass\n"); 503 } 504 505 static void do_test_lru_sanity5(unsigned long long last_key, int map_fd) 506 { 507 unsigned long long key, value[nr_cpus]; 508 509 /* Ensure the last key inserted by previous CPU can be found */ 510 assert(!bpf_map_lookup_elem(map_fd, &last_key, value)); 511 512 value[0] = 1234; 513 514 key = last_key + 1; 515 assert(!bpf_map_update_elem(map_fd, &key, value, BPF_NOEXIST)); 516 assert(!bpf_map_lookup_elem(map_fd, &key, value)); 517 518 /* Cannot find the last key because it was removed by LRU */ 519 assert(bpf_map_lookup_elem(map_fd, &last_key, value)); 520 } 521 522 /* Test map with only one element */ 523 static void test_lru_sanity5(int map_type, int map_flags) 524 { 525 unsigned long long key, value[nr_cpus]; 526 int next_cpu = 0; 527 int map_fd; 528 529 if (map_flags & BPF_F_NO_COMMON_LRU) 530 return; 531 532 printf("%s (map_type:%d map_flags:0x%X): ", __func__, map_type, 533 map_flags); 534 535 map_fd = create_map(map_type, map_flags, 1); 536 assert(map_fd != -1); 537 538 value[0] = 1234; 539 key = 0; 540 assert(!bpf_map_update_elem(map_fd, &key, value, BPF_NOEXIST)); 541 542 while (sched_next_online(0, &next_cpu) != -1) { 543 pid_t pid; 544 545 pid = fork(); 546 if (pid == 0) { 547 do_test_lru_sanity5(key, map_fd); 548 exit(0); 549 } else if (pid == -1) { 550 printf("couldn't spawn process to test key:%llu\n", 551 key); 552 exit(1); 553 } else { 554 int status; 555 556 assert(waitpid(pid, &status, 0) == pid); 557 assert(status == 0); 558 key++; 559 } 560 } 561 562 close(map_fd); 563 /* At least one key should be tested */ 564 assert(key > 0); 565 566 printf("Pass\n"); 567 } 568 569 int main(int argc, char **argv) 570 { 571 struct rlimit r = {RLIM_INFINITY, RLIM_INFINITY}; 572 int map_types[] = {BPF_MAP_TYPE_LRU_HASH, 573 BPF_MAP_TYPE_LRU_PERCPU_HASH}; 574 int map_flags[] = {0, BPF_F_NO_COMMON_LRU}; 575 int t, f; 576 577 setbuf(stdout, NULL); 578 579 assert(!setrlimit(RLIMIT_MEMLOCK, &r)); 580 581 nr_cpus = bpf_num_possible_cpus(); 582 assert(nr_cpus != -1); 583 printf("nr_cpus:%d\n\n", nr_cpus); 584 585 for (f = 0; f < sizeof(map_flags) / sizeof(*map_flags); f++) { 586 unsigned int tgt_free = (map_flags[f] & BPF_F_NO_COMMON_LRU) ? 587 PERCPU_FREE_TARGET : LOCAL_FREE_TARGET; 588 589 for (t = 0; t < sizeof(map_types) / sizeof(*map_types); t++) { 590 test_lru_sanity0(map_types[t], map_flags[f]); 591 test_lru_sanity1(map_types[t], map_flags[f], tgt_free); 592 test_lru_sanity2(map_types[t], map_flags[f], tgt_free); 593 test_lru_sanity3(map_types[t], map_flags[f], tgt_free); 594 test_lru_sanity4(map_types[t], map_flags[f], tgt_free); 595 test_lru_sanity5(map_types[t], map_flags[f]); 596 597 printf("\n"); 598 } 599 } 600 601 return 0; 602 } 603