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