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 #include <sys/resource.h>
  20
  21 #include "bpf_sys.h"
  22 #include "bpf_util.h"
  23
  24 #define LOCAL_FREE_TARGET       (128)
  25 #define PERCPU_FREE_TARGET      (16)
  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_map_create(map_type, sizeof(unsigned long long),
  34                                 sizeof(unsigned long long), size, map_flags);
  35
  36         if (map_fd == -1)
  37                 perror("bpf_map_create");
  38
  39         return map_fd;
  40 }
  41
  42 static int map_subset(int map0, int map1)
  43 {
  44         unsigned long long next_key = 0;
  45         unsigned long long value0[nr_cpus], value1[nr_cpus];
  46         int ret;
  47
  48         while (!bpf_map_next_key(map1, &next_key, &next_key)) {
  49                 assert(!bpf_map_lookup(map1, &next_key, value1));
  50                 ret = bpf_map_lookup(map0, &next_key, value0);
  51                 if (ret) {
  52                         printf("key:%llu not found from map. %s(%d)\n",
  53                                next_key, strerror(errno), errno);
  54                         return 0;
  55                 }
  56                 if (value0[0] != value1[0]) {
  57                         printf("key:%llu value0:%llu != value1:%llu\n",
  58                                next_key, value0[0], value1[0]);
  59                         return 0;
  60                 }
  61         }
  62         return 1;
  63 }
  64
  65 static int map_equal(int lru_map, int expected)
  66 {
  67         return map_subset(lru_map, expected) && map_subset(expected, lru_map);
  68 }
  69
  70 static int sched_next_online(int pid, int *next_to_try)
  71 {
  72         cpu_set_t cpuset;
  73         int next = *next_to_try;
  74         int ret = -1;
  75
  76         while (next < nr_cpus) {
  77                 CPU_ZERO(&cpuset);
  78                 CPU_SET(next++, &cpuset);
  79                 if (!sched_setaffinity(pid, sizeof(cpuset), &cpuset)) {
  80                         ret = 0;
  81                         break;
  82                 }
  83         }
  84
  85         *next_to_try = next;
  86         return ret;
  87 }
  88
  89 /* Size of the LRU amp is 2
  90  * Add key=1 (+1 key)
  91  * Add key=2 (+1 key)
  92  * Lookup Key=1
  93  * Add Key=3
  94  *   => Key=2 will be removed by LRU
  95  * Iterate map.  Only found key=1 and key=3
  96  */
  97 static void test_lru_sanity0(int map_type, int map_flags)
  98 {
  99         unsigned long long key, value[nr_cpus];
 100         int lru_map_fd, expected_map_fd;
 101         int next_cpu = 0;
 102
 103         printf("%s (map_type:%d map_flags:0x%X): ", __func__, map_type,
 104                map_flags);
 105
 106         assert(sched_next_online(0, &next_cpu) != -1);
 107
 108         if (map_flags & BPF_F_NO_COMMON_LRU)
 109                 lru_map_fd = create_map(map_type, map_flags, 2 * nr_cpus);
 110         else
 111                 lru_map_fd = create_map(map_type, map_flags, 2);
 112         assert(lru_map_fd != -1);
 113
 114         expected_map_fd = create_map(BPF_MAP_TYPE_HASH, 0, 2);
 115         assert(expected_map_fd != -1);
 116
 117         value[0] = 1234;
 118
 119         /* insert key=1 element */
 120
 121         key = 1;
 122         assert(!bpf_map_update(lru_map_fd, &key, value, BPF_NOEXIST));
 123         assert(!bpf_map_update(expected_map_fd, &key, value, BPF_NOEXIST));
 124
 125         /* BPF_NOEXIST means: add new element if it doesn't exist */
 126         assert(bpf_map_update(lru_map_fd, &key, value, BPF_NOEXIST) == -1 &&
 127                /* key=1 already exists */
 128                errno == EEXIST);
 129
 130         assert(bpf_map_update(lru_map_fd, &key, value, -1) == -1 &&
 131                errno == EINVAL);
 132
 133         /* insert key=2 element */
 134
 135         /* check that key=2 is not found */
 136         key = 2;
 137         assert(bpf_map_lookup(lru_map_fd, &key, value) == -1 &&
 138                errno == ENOENT);
 139
 140         /* BPF_EXIST means: update existing element */
 141         assert(bpf_map_update(lru_map_fd, &key, value, BPF_EXIST) == -1 &&
 142                /* key=2 is not there */
 143                errno == ENOENT);
 144
 145         assert(!bpf_map_update(lru_map_fd, &key, value, BPF_NOEXIST));
 146
 147         /* insert key=3 element */
 148
 149         /* check that key=3 is not found */
 150         key = 3;
 151         assert(bpf_map_lookup(lru_map_fd, &key, value) == -1 &&
 152                errno == ENOENT);
 153
 154         /* check that key=1 can be found and mark the ref bit to
 155          * stop LRU from removing key=1
 156          */
 157         key = 1;
 158         assert(!bpf_map_lookup(lru_map_fd, &key, value));
 159         assert(value[0] == 1234);
 160
 161         key = 3;
 162         assert(!bpf_map_update(lru_map_fd, &key, value, BPF_NOEXIST));
 163         assert(!bpf_map_update(expected_map_fd, &key, value, BPF_NOEXIST));
 164
 165         /* key=2 has been removed from the LRU */
 166         key = 2;
 167         assert(bpf_map_lookup(lru_map_fd, &key, value) == -1);
 168
 169         assert(map_equal(lru_map_fd, expected_map_fd));
 170
 171         close(expected_map_fd);
 172         close(lru_map_fd);
 173
 174         printf("Pass\n");
 175 }
 176
 177 /* Size of the LRU map is 1.5*tgt_free
 178  * Insert 1 to tgt_free (+tgt_free keys)
 179  * Lookup 1 to tgt_free/2
 180  * Insert 1+tgt_free to 2*tgt_free (+tgt_free keys)
 181  * => 1+tgt_free/2 to LOCALFREE_TARGET will be removed by LRU
 182  */
 183 static void test_lru_sanity1(int map_type, int map_flags, unsigned int tgt_free)
 184 {
 185         unsigned long long key, end_key, value[nr_cpus];
 186         int lru_map_fd, expected_map_fd;
 187         unsigned int batch_size;
 188         unsigned int map_size;
 189         int next_cpu = 0;
 190
 191         if (map_flags & BPF_F_NO_COMMON_LRU)
 192                 /* Ther percpu lru list (i.e each cpu has its own LRU
 193                  * list) does not have a local free list.  Hence,
 194                  * it will only free old nodes till there is no free
 195                  * from the LRU list.  Hence, this test does not apply
 196                  * to BPF_F_NO_COMMON_LRU
 197                  */
 198                 return;
 199
 200         printf("%s (map_type:%d map_flags:0x%X): ", __func__, map_type,
 201                map_flags);
 202
 203         assert(sched_next_online(0, &next_cpu) != -1);
 204
 205         batch_size = tgt_free / 2;
 206         assert(batch_size * 2 == tgt_free);
 207
 208         map_size = tgt_free + batch_size;
 209         lru_map_fd = create_map(map_type, map_flags, map_size);
 210         assert(lru_map_fd != -1);
 211
 212         expected_map_fd = create_map(BPF_MAP_TYPE_HASH, 0, map_size);
 213         assert(expected_map_fd != -1);
 214
 215         value[0] = 1234;
 216
 217         /* Insert 1 to tgt_free (+tgt_free keys) */
 218         end_key = 1 + tgt_free;
 219         for (key = 1; key < end_key; key++)
 220                 assert(!bpf_map_update(lru_map_fd, &key, value, BPF_NOEXIST));
 221
 222         /* Lookup 1 to tgt_free/2 */
 223         end_key = 1 + batch_size;
 224         for (key = 1; key < end_key; key++) {
 225                 assert(!bpf_map_lookup(lru_map_fd, &key, value));
 226                 assert(!bpf_map_update(expected_map_fd, &key, value,
 227                                        BPF_NOEXIST));
 228         }
 229
 230         /* Insert 1+tgt_free to 2*tgt_free
 231          * => 1+tgt_free/2 to LOCALFREE_TARGET will be
 232          * removed by LRU
 233          */
 234         key = 1 + tgt_free;
 235         end_key = key + tgt_free;
 236         for (; key < end_key; key++) {
 237                 assert(!bpf_map_update(lru_map_fd, &key, value, BPF_NOEXIST));
 238                 assert(!bpf_map_update(expected_map_fd, &key, value,
 239                                        BPF_NOEXIST));
 240         }
 241
 242         assert(map_equal(lru_map_fd, expected_map_fd));
 243
 244         close(expected_map_fd);
 245         close(lru_map_fd);
 246
 247         printf("Pass\n");
 248 }
 249
 250 /* Size of the LRU map 1.5 * tgt_free
 251  * Insert 1 to tgt_free (+tgt_free keys)
 252  * Update 1 to tgt_free/2
 253  *   => The original 1 to tgt_free/2 will be removed due to
 254  *      the LRU shrink process
 255  * Re-insert 1 to tgt_free/2 again and do a lookup immeidately
 256  * Insert 1+tgt_free to tgt_free*3/2
 257  * Insert 1+tgt_free*3/2 to tgt_free*5/2
 258  *   => Key 1+tgt_free to tgt_free*3/2
 259  *      will be removed from LRU because it has never
 260  *      been lookup and ref bit is not set
 261  */
 262 static void test_lru_sanity2(int map_type, int map_flags, unsigned int tgt_free)
 263 {
 264         unsigned long long key, value[nr_cpus];
 265         unsigned long long end_key;
 266         int lru_map_fd, expected_map_fd;
 267         unsigned int batch_size;
 268         unsigned int map_size;
 269         int next_cpu = 0;
 270
 271         if (map_flags & BPF_F_NO_COMMON_LRU)
 272                 /* Ther percpu lru list (i.e each cpu has its own LRU
 273                  * list) does not have a local free list.  Hence,
 274                  * it will only free old nodes till there is no free
 275                  * from the LRU list.  Hence, this test does not apply
 276                  * to BPF_F_NO_COMMON_LRU
 277                  */
 278                 return;
 279
 280         printf("%s (map_type:%d map_flags:0x%X): ", __func__, map_type,
 281                map_flags);
 282
 283         assert(sched_next_online(0, &next_cpu) != -1);
 284
 285         batch_size = tgt_free / 2;
 286         assert(batch_size * 2 == tgt_free);
 287
 288         map_size = tgt_free + batch_size;
 289         if (map_flags & BPF_F_NO_COMMON_LRU)
 290                 lru_map_fd = create_map(map_type, map_flags,
 291                                         map_size * nr_cpus);
 292         else
 293                 lru_map_fd = create_map(map_type, map_flags, map_size);
 294         assert(lru_map_fd != -1);
 295
 296         expected_map_fd = create_map(BPF_MAP_TYPE_HASH, 0, map_size);
 297         assert(expected_map_fd != -1);
 298
 299         value[0] = 1234;
 300
 301         /* Insert 1 to tgt_free (+tgt_free keys) */
 302         end_key = 1 + tgt_free;
 303         for (key = 1; key < end_key; key++)
 304                 assert(!bpf_map_update(lru_map_fd, &key, value, BPF_NOEXIST));
 305
 306         /* Any bpf_map_update will require to acquire a new node
 307          * from LRU first.
 308          *
 309          * The local list is running out of free nodes.
 310          * It gets from the global LRU list which tries to
 311          * shrink the inactive list to get tgt_free
 312          * number of free nodes.
 313          *
 314          * Hence, the oldest key 1 to tgt_free/2
 315          * are removed from the LRU list.
 316          */
 317         key = 1;
 318         if (map_type == BPF_MAP_TYPE_LRU_PERCPU_HASH) {
 319                 assert(!bpf_map_update(lru_map_fd, &key, value, BPF_NOEXIST));
 320                 assert(!bpf_map_delete(lru_map_fd, &key));
 321         } else {
 322                 assert(bpf_map_update(lru_map_fd, &key, value, BPF_EXIST));
 323         }
 324
 325         /* Re-insert 1 to tgt_free/2 again and do a lookup
 326          * immeidately.
 327          */
 328         end_key = 1 + batch_size;
 329         value[0] = 4321;
 330         for (key = 1; key < end_key; key++) {
 331                 assert(bpf_map_lookup(lru_map_fd, &key, value));
 332                 assert(!bpf_map_update(lru_map_fd, &key, value, BPF_NOEXIST));
 333                 assert(!bpf_map_lookup(lru_map_fd, &key, value));
 334                 assert(value[0] == 4321);
 335                 assert(!bpf_map_update(expected_map_fd, &key, value,
 336                                        BPF_NOEXIST));
 337         }
 338
 339         value[0] = 1234;
 340
 341         /* Insert 1+tgt_free to tgt_free*3/2 */
 342         end_key = 1 + tgt_free + batch_size;
 343         for (key = 1 + tgt_free; key < end_key; key++)
 344                 /* These newly added but not referenced keys will be
 345                  * gone during the next LRU shrink.
 346                  */
 347                 assert(!bpf_map_update(lru_map_fd, &key, value, BPF_NOEXIST));
 348
 349         /* Insert 1+tgt_free*3/2 to  tgt_free*5/2 */
 350         end_key = key + tgt_free;
 351         for (; key < end_key; key++) {
 352                 assert(!bpf_map_update(lru_map_fd, &key, value, BPF_NOEXIST));
 353                 assert(!bpf_map_update(expected_map_fd, &key, value,
 354                                        BPF_NOEXIST));
 355         }
 356
 357         assert(map_equal(lru_map_fd, expected_map_fd));
 358
 359         close(expected_map_fd);
 360         close(lru_map_fd);
 361
 362         printf("Pass\n");
 363 }
 364
 365 /* Size of the LRU map is 2*tgt_free
 366  * It is to test the active/inactive list rotation
 367  * Insert 1 to 2*tgt_free (+2*tgt_free keys)
 368  * Lookup key 1 to tgt_free*3/2
 369  * Add 1+2*tgt_free to tgt_free*5/2 (+tgt_free/2 keys)
 370  *  => key 1+tgt_free*3/2 to 2*tgt_free are removed from LRU
 371  */
 372 static void test_lru_sanity3(int map_type, int map_flags, unsigned int tgt_free)
 373 {
 374         unsigned long long key, end_key, value[nr_cpus];
 375         int lru_map_fd, expected_map_fd;
 376         unsigned int batch_size;
 377         unsigned int map_size;
 378         int next_cpu = 0;
 379
 380         printf("%s (map_type:%d map_flags:0x%X): ", __func__, map_type,
 381                map_flags);
 382
 383         assert(sched_next_online(0, &next_cpu) != -1);
 384
 385         batch_size = tgt_free / 2;
 386         assert(batch_size * 2 == tgt_free);
 387
 388         map_size = tgt_free * 2;
 389         if (map_flags & BPF_F_NO_COMMON_LRU)
 390                 lru_map_fd = create_map(map_type, map_flags,
 391                                         map_size * nr_cpus);
 392         else
 393                 lru_map_fd = create_map(map_type, map_flags, map_size);
 394         assert(lru_map_fd != -1);
 395
 396         expected_map_fd = create_map(BPF_MAP_TYPE_HASH, 0, map_size);
 397         assert(expected_map_fd != -1);
 398
 399         value[0] = 1234;
 400
 401         /* Insert 1 to 2*tgt_free (+2*tgt_free keys) */
 402         end_key = 1 + (2 * tgt_free);
 403         for (key = 1; key < end_key; key++)
 404                 assert(!bpf_map_update(lru_map_fd, &key, value, BPF_NOEXIST));
 405
 406         /* Lookup key 1 to tgt_free*3/2 */
 407         end_key = tgt_free + batch_size;
 408         for (key = 1; key < end_key; key++) {
 409                 assert(!bpf_map_lookup(lru_map_fd, &key, value));
 410                 assert(!bpf_map_update(expected_map_fd, &key, value,
 411                                        BPF_NOEXIST));
 412         }
 413
 414         /* Add 1+2*tgt_free to tgt_free*5/2
 415          * (+tgt_free/2 keys)
 416          */
 417         key = 2 * tgt_free + 1;
 418         end_key = key + batch_size;
 419         for (; key < end_key; key++) {
 420                 assert(!bpf_map_update(lru_map_fd, &key, value, BPF_NOEXIST));
 421                 assert(!bpf_map_update(expected_map_fd, &key, value,
 422                                        BPF_NOEXIST));
 423         }
 424
 425         assert(map_equal(lru_map_fd, expected_map_fd));
 426
 427         close(expected_map_fd);
 428         close(lru_map_fd);
 429
 430         printf("Pass\n");
 431 }
 432
 433 /* Test deletion */
 434 static void test_lru_sanity4(int map_type, int map_flags, unsigned int tgt_free)
 435 {
 436         int lru_map_fd, expected_map_fd;
 437         unsigned long long key, value[nr_cpus];
 438         unsigned long long end_key;
 439         int next_cpu = 0;
 440
 441         printf("%s (map_type:%d map_flags:0x%X): ", __func__, map_type,
 442                map_flags);
 443
 444         assert(sched_next_online(0, &next_cpu) != -1);
 445
 446         if (map_flags & BPF_F_NO_COMMON_LRU)
 447                 lru_map_fd = create_map(map_type, map_flags,
 448                                         3 * tgt_free * nr_cpus);
 449         else
 450                 lru_map_fd = create_map(map_type, map_flags, 3 * tgt_free);
 451         assert(lru_map_fd != -1);
 452
 453         expected_map_fd = create_map(BPF_MAP_TYPE_HASH, 0,
 454                                      3 * tgt_free);
 455         assert(expected_map_fd != -1);
 456
 457         value[0] = 1234;
 458
 459         for (key = 1; key <= 2 * tgt_free; key++)
 460                 assert(!bpf_map_update(lru_map_fd, &key, value, BPF_NOEXIST));
 461
 462         key = 1;
 463         assert(bpf_map_update(lru_map_fd, &key, value, BPF_NOEXIST));
 464
 465         for (key = 1; key <= tgt_free; key++) {
 466                 assert(!bpf_map_lookup(lru_map_fd, &key, value));
 467                 assert(!bpf_map_update(expected_map_fd, &key, value,
 468                                        BPF_NOEXIST));
 469         }
 470
 471         for (; key <= 2 * tgt_free; key++) {
 472                 assert(!bpf_map_delete(lru_map_fd, &key));
 473                 assert(bpf_map_delete(lru_map_fd, &key));
 474         }
 475
 476         end_key = key + 2 * tgt_free;
 477         for (; key < end_key; key++) {
 478                 assert(!bpf_map_update(lru_map_fd, &key, value, BPF_NOEXIST));
 479                 assert(!bpf_map_update(expected_map_fd, &key, value,
 480                                        BPF_NOEXIST));
 481         }
 482
 483         assert(map_equal(lru_map_fd, expected_map_fd));
 484
 485         close(expected_map_fd);
 486         close(lru_map_fd);
 487
 488         printf("Pass\n");
 489 }
 490
 491 static void do_test_lru_sanity5(unsigned long long last_key, int map_fd)
 492 {
 493         unsigned long long key, value[nr_cpus];
 494
 495         /* Ensure the last key inserted by previous CPU can be found */
 496         assert(!bpf_map_lookup(map_fd, &last_key, value));
 497
 498         value[0] = 1234;
 499
 500         key = last_key + 1;
 501         assert(!bpf_map_update(map_fd, &key, value, BPF_NOEXIST));
 502         assert(!bpf_map_lookup(map_fd, &key, value));
 503
 504         /* Cannot find the last key because it was removed by LRU */
 505         assert(bpf_map_lookup(map_fd, &last_key, value));
 506 }
 507
 508 /* Test map with only one element */
 509 static void test_lru_sanity5(int map_type, int map_flags)
 510 {
 511         unsigned long long key, value[nr_cpus];
 512         int next_cpu = 0;
 513         int map_fd;
 514
 515         if (map_flags & BPF_F_NO_COMMON_LRU)
 516                 return;
 517
 518         printf("%s (map_type:%d map_flags:0x%X): ", __func__, map_type,
 519                map_flags);
 520
 521         map_fd = create_map(map_type, map_flags, 1);
 522         assert(map_fd != -1);
 523
 524         value[0] = 1234;
 525         key = 0;
 526         assert(!bpf_map_update(map_fd, &key, value, BPF_NOEXIST));
 527
 528         while (sched_next_online(0, &next_cpu) != -1) {
 529                 pid_t pid;
 530
 531                 pid = fork();
 532                 if (pid == 0) {
 533                         do_test_lru_sanity5(key, map_fd);
 534                         exit(0);
 535                 } else if (pid == -1) {
 536                         printf("couldn't spawn process to test key:%llu\n",
 537                                key);
 538                         exit(1);
 539                 } else {
 540                         int status;
 541
 542                         assert(waitpid(pid, &status, 0) == pid);
 543                         assert(status == 0);
 544                         key++;
 545                 }
 546         }
 547
 548         close(map_fd);
 549         /* At least one key should be tested */
 550         assert(key > 0);
 551
 552         printf("Pass\n");
 553 }
 554
 555 int main(int argc, char **argv)
 556 {
 557         struct rlimit r = {RLIM_INFINITY, RLIM_INFINITY};
 558         int map_types[] = {BPF_MAP_TYPE_LRU_HASH,
 559                              BPF_MAP_TYPE_LRU_PERCPU_HASH};
 560         int map_flags[] = {0, BPF_F_NO_COMMON_LRU};
 561         int t, f;
 562
 563         setbuf(stdout, NULL);
 564
 565         assert(!setrlimit(RLIMIT_MEMLOCK, &r));
 566
 567         nr_cpus = bpf_num_possible_cpus();
 568         assert(nr_cpus != -1);
 569         printf("nr_cpus:%d\n\n", nr_cpus);
 570
 571         for (f = 0; f < sizeof(map_flags) / sizeof(*map_flags); f++) {
 572                 unsigned int tgt_free = (map_flags[f] & BPF_F_NO_COMMON_LRU) ?
 573                         PERCPU_FREE_TARGET : LOCAL_FREE_TARGET;
 574
 575                 for (t = 0; t < sizeof(map_types) / sizeof(*map_types); t++) {
 576                         test_lru_sanity0(map_types[t], map_flags[f]);
 577                         test_lru_sanity1(map_types[t], map_flags[f], tgt_free);
 578                         test_lru_sanity2(map_types[t], map_flags[f], tgt_free);
 579                         test_lru_sanity3(map_types[t], map_flags[f], tgt_free);
 580                         test_lru_sanity4(map_types[t], map_flags[f], tgt_free);
 581                         test_lru_sanity5(map_types[t], map_flags[f]);
 582
 583                         printf("\n");
 584                 }
 585         }
 586
 587         return 0;
 588 }