tools/testing/selftests/bpf/test_lru_map.c

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