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