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