tools/testing/selftests/bpf/test_lru_map.c

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