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