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