tools/testing/selftests/bpf/test_lru

/* [<][>][^][v][top][bottom][index][help] */
This source file includes following definitions.
create_map
bpf_map_lookup_elem_with_ref_bit
map_subset
map_equal
sched_next_online
test_lru_sanity0
test_lru_sanity1
test_lru_sanity2
test_lru_sanity3
test_lru_sanity4
do_test_lru_sanity5
test_lru_sanity5
test_lru_sanity6
test_lru_sanity7
test_lru_sanity8
main
   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 }
/* [<][>][^][v][top][bottom][index][help] */
root/tools/testing/selftests/bpf/test_lru_map.c

DEFINITIONS
