tools/testing/selftests/bpf/test_maps.c

   1 /*
   2  * Testsuite for eBPF maps
   3  *
   4  * Copyright (c) 2014 PLUMgrid, http://plumgrid.com
   5  * Copyright (c) 2016 Facebook
   6  *
   7  * This program is free software; you can redistribute it and/or
   8  * modify it under the terms of version 2 of the GNU General Public
   9  * License as published by the Free Software Foundation.
  10  */
  11
  12 #include <stdio.h>
  13 #include <unistd.h>
  14 #include <errno.h>
  15 #include <string.h>
  16 #include <assert.h>
  17 #include <stdlib.h>
  18
  19 #include <sys/wait.h>
  20 #include <sys/resource.h>
  21
  22 #include <linux/bpf.h>
  23
  24 #include <bpf/bpf.h>
  25 #include "bpf_util.h"
  26
  27 static int map_flags;
  28
  29 static void test_hashmap(int task, void *data)
  30 {
  31         long long key, next_key, first_key, value;
  32         int fd;
  33
  34         fd = bpf_create_map(BPF_MAP_TYPE_HASH, sizeof(key), sizeof(value),
  35                             2, map_flags);
  36         if (fd < 0) {
  37                 printf("Failed to create hashmap '%s'!\n", strerror(errno));
  38                 exit(1);
  39         }
  40
  41         key = 1;
  42         value = 1234;
  43         /* Insert key=1 element. */
  44         assert(bpf_map_update_elem(fd, &key, &value, BPF_ANY) == 0);
  45
  46         value = 0;
  47         /* BPF_NOEXIST means add new element if it doesn't exist. */
  48         assert(bpf_map_update_elem(fd, &key, &value, BPF_NOEXIST) == -1 &&
  49                /* key=1 already exists. */
  50                errno == EEXIST);
  51
  52         /* -1 is an invalid flag. */
  53         assert(bpf_map_update_elem(fd, &key, &value, -1) == -1 &&
  54                errno == EINVAL);
  55
  56         /* Check that key=1 can be found. */
  57         assert(bpf_map_lookup_elem(fd, &key, &value) == 0 && value == 1234);
  58
  59         key = 2;
  60         /* Check that key=2 is not found. */
  61         assert(bpf_map_lookup_elem(fd, &key, &value) == -1 && errno == ENOENT);
  62
  63         /* BPF_EXIST means update existing element. */
  64         assert(bpf_map_update_elem(fd, &key, &value, BPF_EXIST) == -1 &&
  65                /* key=2 is not there. */
  66                errno == ENOENT);
  67
  68         /* Insert key=2 element. */
  69         assert(bpf_map_update_elem(fd, &key, &value, BPF_NOEXIST) == 0);
  70
  71         /* key=1 and key=2 were inserted, check that key=0 cannot be
  72          * inserted due to max_entries limit.
  73          */
  74         key = 0;
  75         assert(bpf_map_update_elem(fd, &key, &value, BPF_NOEXIST) == -1 &&
  76                errno == E2BIG);
  77
  78         /* Update existing element, though the map is full. */
  79         key = 1;
  80         assert(bpf_map_update_elem(fd, &key, &value, BPF_EXIST) == 0);
  81         key = 2;
  82         assert(bpf_map_update_elem(fd, &key, &value, BPF_ANY) == 0);
  83         key = 3;
  84         assert(bpf_map_update_elem(fd, &key, &value, BPF_NOEXIST) == -1 &&
  85                errno == E2BIG);
  86
  87         /* Check that key = 0 doesn't exist. */
  88         key = 0;
  89         assert(bpf_map_delete_elem(fd, &key) == -1 && errno == ENOENT);
  90
  91         /* Iterate over two elements. */
  92         assert(bpf_map_get_next_key(fd, NULL, &first_key) == 0 &&
  93                (first_key == 1 || first_key == 2));
  94         assert(bpf_map_get_next_key(fd, &key, &next_key) == 0 &&
  95                (next_key == first_key));
  96         assert(bpf_map_get_next_key(fd, &next_key, &next_key) == 0 &&
  97                (next_key == 1 || next_key == 2) &&
  98                (next_key != first_key));
  99         assert(bpf_map_get_next_key(fd, &next_key, &next_key) == -1 &&
 100                errno == ENOENT);
 101
 102         /* Delete both elements. */
 103         key = 1;
 104         assert(bpf_map_delete_elem(fd, &key) == 0);
 105         key = 2;
 106         assert(bpf_map_delete_elem(fd, &key) == 0);
 107         assert(bpf_map_delete_elem(fd, &key) == -1 && errno == ENOENT);
 108
 109         key = 0;
 110         /* Check that map is empty. */
 111         assert(bpf_map_get_next_key(fd, NULL, &next_key) == -1 &&
 112                errno == ENOENT);
 113         assert(bpf_map_get_next_key(fd, &key, &next_key) == -1 &&
 114                errno == ENOENT);
 115
 116         close(fd);
 117 }
 118
 119 static void test_hashmap_sizes(int task, void *data)
 120 {
 121         int fd, i, j;
 122
 123         for (i = 1; i <= 512; i <<= 1)
 124                 for (j = 1; j <= 1 << 18; j <<= 1) {
 125                         fd = bpf_create_map(BPF_MAP_TYPE_HASH, i, j,
 126                                             2, map_flags);
 127                         if (fd < 0) {
 128                                 printf("Failed to create hashmap key=%d value=%d '%s'\n",
 129                                        i, j, strerror(errno));
 130                                 exit(1);
 131                         }
 132                         close(fd);
 133                         usleep(10); /* give kernel time to destroy */
 134                 }
 135 }
 136
 137 static void test_hashmap_percpu(int task, void *data)
 138 {
 139         unsigned int nr_cpus = bpf_num_possible_cpus();
 140         BPF_DECLARE_PERCPU(long, value);
 141         long long key, next_key, first_key;
 142         int expected_key_mask = 0;
 143         int fd, i;
 144
 145         fd = bpf_create_map(BPF_MAP_TYPE_PERCPU_HASH, sizeof(key),
 146                             sizeof(bpf_percpu(value, 0)), 2, map_flags);
 147         if (fd < 0) {
 148                 printf("Failed to create hashmap '%s'!\n", strerror(errno));
 149                 exit(1);
 150         }
 151
 152         for (i = 0; i < nr_cpus; i++)
 153                 bpf_percpu(value, i) = i + 100;
 154
 155         key = 1;
 156         /* Insert key=1 element. */
 157         assert(!(expected_key_mask & key));
 158         assert(bpf_map_update_elem(fd, &key, value, BPF_ANY) == 0);
 159         expected_key_mask |= key;
 160
 161         /* BPF_NOEXIST means add new element if it doesn't exist. */
 162         assert(bpf_map_update_elem(fd, &key, value, BPF_NOEXIST) == -1 &&
 163                /* key=1 already exists. */
 164                errno == EEXIST);
 165
 166         /* -1 is an invalid flag. */
 167         assert(bpf_map_update_elem(fd, &key, value, -1) == -1 &&
 168                errno == EINVAL);
 169
 170         /* Check that key=1 can be found. Value could be 0 if the lookup
 171          * was run from a different CPU.
 172          */
 173         bpf_percpu(value, 0) = 1;
 174         assert(bpf_map_lookup_elem(fd, &key, value) == 0 &&
 175                bpf_percpu(value, 0) == 100);
 176
 177         key = 2;
 178         /* Check that key=2 is not found. */
 179         assert(bpf_map_lookup_elem(fd, &key, value) == -1 && errno == ENOENT);
 180
 181         /* BPF_EXIST means update existing element. */
 182         assert(bpf_map_update_elem(fd, &key, value, BPF_EXIST) == -1 &&
 183                /* key=2 is not there. */
 184                errno == ENOENT);
 185
 186         /* Insert key=2 element. */
 187         assert(!(expected_key_mask & key));
 188         assert(bpf_map_update_elem(fd, &key, value, BPF_NOEXIST) == 0);
 189         expected_key_mask |= key;
 190
 191         /* key=1 and key=2 were inserted, check that key=0 cannot be
 192          * inserted due to max_entries limit.
 193          */
 194         key = 0;
 195         assert(bpf_map_update_elem(fd, &key, value, BPF_NOEXIST) == -1 &&
 196                errno == E2BIG);
 197
 198         /* Check that key = 0 doesn't exist. */
 199         assert(bpf_map_delete_elem(fd, &key) == -1 && errno == ENOENT);
 200
 201         /* Iterate over two elements. */
 202         assert(bpf_map_get_next_key(fd, NULL, &first_key) == 0 &&
 203                ((expected_key_mask & first_key) == first_key));
 204         while (!bpf_map_get_next_key(fd, &key, &next_key)) {
 205                 if (first_key) {
 206                         assert(next_key == first_key);
 207                         first_key = 0;
 208                 }
 209                 assert((expected_key_mask & next_key) == next_key);
 210                 expected_key_mask &= ~next_key;
 211
 212                 assert(bpf_map_lookup_elem(fd, &next_key, value) == 0);
 213
 214                 for (i = 0; i < nr_cpus; i++)
 215                         assert(bpf_percpu(value, i) == i + 100);
 216
 217                 key = next_key;
 218         }
 219         assert(errno == ENOENT);
 220
 221         /* Update with BPF_EXIST. */
 222         key = 1;
 223         assert(bpf_map_update_elem(fd, &key, value, BPF_EXIST) == 0);
 224
 225         /* Delete both elements. */
 226         key = 1;
 227         assert(bpf_map_delete_elem(fd, &key) == 0);
 228         key = 2;
 229         assert(bpf_map_delete_elem(fd, &key) == 0);
 230         assert(bpf_map_delete_elem(fd, &key) == -1 && errno == ENOENT);
 231
 232         key = 0;
 233         /* Check that map is empty. */
 234         assert(bpf_map_get_next_key(fd, NULL, &next_key) == -1 &&
 235                errno == ENOENT);
 236         assert(bpf_map_get_next_key(fd, &key, &next_key) == -1 &&
 237                errno == ENOENT);
 238
 239         close(fd);
 240 }
 241
 242 static void test_arraymap(int task, void *data)
 243 {
 244         int key, next_key, fd;
 245         long long value;
 246
 247         fd = bpf_create_map(BPF_MAP_TYPE_ARRAY, sizeof(key), sizeof(value),
 248                             2, 0);
 249         if (fd < 0) {
 250                 printf("Failed to create arraymap '%s'!\n", strerror(errno));
 251                 exit(1);
 252         }
 253
 254         key = 1;
 255         value = 1234;
 256         /* Insert key=1 element. */
 257         assert(bpf_map_update_elem(fd, &key, &value, BPF_ANY) == 0);
 258
 259         value = 0;
 260         assert(bpf_map_update_elem(fd, &key, &value, BPF_NOEXIST) == -1 &&
 261                errno == EEXIST);
 262
 263         /* Check that key=1 can be found. */
 264         assert(bpf_map_lookup_elem(fd, &key, &value) == 0 && value == 1234);
 265
 266         key = 0;
 267         /* Check that key=0 is also found and zero initialized. */
 268         assert(bpf_map_lookup_elem(fd, &key, &value) == 0 && value == 0);
 269
 270         /* key=0 and key=1 were inserted, check that key=2 cannot be inserted
 271          * due to max_entries limit.
 272          */
 273         key = 2;
 274         assert(bpf_map_update_elem(fd, &key, &value, BPF_EXIST) == -1 &&
 275                errno == E2BIG);
 276
 277         /* Check that key = 2 doesn't exist. */
 278         assert(bpf_map_lookup_elem(fd, &key, &value) == -1 && errno == ENOENT);
 279
 280         /* Iterate over two elements. */
 281         assert(bpf_map_get_next_key(fd, NULL, &next_key) == 0 &&
 282                next_key == 0);
 283         assert(bpf_map_get_next_key(fd, &key, &next_key) == 0 &&
 284                next_key == 0);
 285         assert(bpf_map_get_next_key(fd, &next_key, &next_key) == 0 &&
 286                next_key == 1);
 287         assert(bpf_map_get_next_key(fd, &next_key, &next_key) == -1 &&
 288                errno == ENOENT);
 289
 290         /* Delete shouldn't succeed. */
 291         key = 1;
 292         assert(bpf_map_delete_elem(fd, &key) == -1 && errno == EINVAL);
 293
 294         close(fd);
 295 }
 296
 297 static void test_arraymap_percpu(int task, void *data)
 298 {
 299         unsigned int nr_cpus = bpf_num_possible_cpus();
 300         BPF_DECLARE_PERCPU(long, values);
 301         int key, next_key, fd, i;
 302
 303         fd = bpf_create_map(BPF_MAP_TYPE_PERCPU_ARRAY, sizeof(key),
 304                             sizeof(bpf_percpu(values, 0)), 2, 0);
 305         if (fd < 0) {
 306                 printf("Failed to create arraymap '%s'!\n", strerror(errno));
 307                 exit(1);
 308         }
 309
 310         for (i = 0; i < nr_cpus; i++)
 311                 bpf_percpu(values, i) = i + 100;
 312
 313         key = 1;
 314         /* Insert key=1 element. */
 315         assert(bpf_map_update_elem(fd, &key, values, BPF_ANY) == 0);
 316
 317         bpf_percpu(values, 0) = 0;
 318         assert(bpf_map_update_elem(fd, &key, values, BPF_NOEXIST) == -1 &&
 319                errno == EEXIST);
 320
 321         /* Check that key=1 can be found. */
 322         assert(bpf_map_lookup_elem(fd, &key, values) == 0 &&
 323                bpf_percpu(values, 0) == 100);
 324
 325         key = 0;
 326         /* Check that key=0 is also found and zero initialized. */
 327         assert(bpf_map_lookup_elem(fd, &key, values) == 0 &&
 328                bpf_percpu(values, 0) == 0 &&
 329                bpf_percpu(values, nr_cpus - 1) == 0);
 330
 331         /* Check that key=2 cannot be inserted due to max_entries limit. */
 332         key = 2;
 333         assert(bpf_map_update_elem(fd, &key, values, BPF_EXIST) == -1 &&
 334                errno == E2BIG);
 335
 336         /* Check that key = 2 doesn't exist. */
 337         assert(bpf_map_lookup_elem(fd, &key, values) == -1 && errno == ENOENT);
 338
 339         /* Iterate over two elements. */
 340         assert(bpf_map_get_next_key(fd, NULL, &next_key) == 0 &&
 341                next_key == 0);
 342         assert(bpf_map_get_next_key(fd, &key, &next_key) == 0 &&
 343                next_key == 0);
 344         assert(bpf_map_get_next_key(fd, &next_key, &next_key) == 0 &&
 345                next_key == 1);
 346         assert(bpf_map_get_next_key(fd, &next_key, &next_key) == -1 &&
 347                errno == ENOENT);
 348
 349         /* Delete shouldn't succeed. */
 350         key = 1;
 351         assert(bpf_map_delete_elem(fd, &key) == -1 && errno == EINVAL);
 352
 353         close(fd);
 354 }
 355
 356 static void test_arraymap_percpu_many_keys(void)
 357 {
 358         unsigned int nr_cpus = bpf_num_possible_cpus();
 359         BPF_DECLARE_PERCPU(long, values);
 360         /* nr_keys is not too large otherwise the test stresses percpu
 361          * allocator more than anything else
 362          */
 363         unsigned int nr_keys = 2000;
 364         int key, fd, i;
 365
 366         fd = bpf_create_map(BPF_MAP_TYPE_PERCPU_ARRAY, sizeof(key),
 367                             sizeof(bpf_percpu(values, 0)), nr_keys, 0);
 368         if (fd < 0) {
 369                 printf("Failed to create per-cpu arraymap '%s'!\n",
 370                        strerror(errno));
 371                 exit(1);
 372         }
 373
 374         for (i = 0; i < nr_cpus; i++)
 375                 bpf_percpu(values, i) = i + 10;
 376
 377         for (key = 0; key < nr_keys; key++)
 378                 assert(bpf_map_update_elem(fd, &key, values, BPF_ANY) == 0);
 379
 380         for (key = 0; key < nr_keys; key++) {
 381                 for (i = 0; i < nr_cpus; i++)
 382                         bpf_percpu(values, i) = 0;
 383
 384                 assert(bpf_map_lookup_elem(fd, &key, values) == 0);
 385
 386                 for (i = 0; i < nr_cpus; i++)
 387                         assert(bpf_percpu(values, i) == i + 10);
 388         }
 389
 390         close(fd);
 391 }
 392
 393 #define MAP_SIZE (32 * 1024)
 394
 395 static void test_map_large(void)
 396 {
 397         struct bigkey {
 398                 int a;
 399                 char b[116];
 400                 long long c;
 401         } key;
 402         int fd, i, value;
 403
 404         fd = bpf_create_map(BPF_MAP_TYPE_HASH, sizeof(key), sizeof(value),
 405                             MAP_SIZE, map_flags);
 406         if (fd < 0) {
 407                 printf("Failed to create large map '%s'!\n", strerror(errno));
 408                 exit(1);
 409         }
 410
 411         for (i = 0; i < MAP_SIZE; i++) {
 412                 key = (struct bigkey) { .c = i };
 413                 value = i;
 414
 415                 assert(bpf_map_update_elem(fd, &key, &value, BPF_NOEXIST) == 0);
 416         }
 417
 418         key.c = -1;
 419         assert(bpf_map_update_elem(fd, &key, &value, BPF_NOEXIST) == -1 &&
 420                errno == E2BIG);
 421
 422         /* Iterate through all elements. */
 423         assert(bpf_map_get_next_key(fd, NULL, &key) == 0);
 424         key.c = -1;
 425         for (i = 0; i < MAP_SIZE; i++)
 426                 assert(bpf_map_get_next_key(fd, &key, &key) == 0);
 427         assert(bpf_map_get_next_key(fd, &key, &key) == -1 && errno == ENOENT);
 428
 429         key.c = 0;
 430         assert(bpf_map_lookup_elem(fd, &key, &value) == 0 && value == 0);
 431         key.a = 1;
 432         assert(bpf_map_lookup_elem(fd, &key, &value) == -1 && errno == ENOENT);
 433
 434         close(fd);
 435 }
 436
 437 static void run_parallel(int tasks, void (*fn)(int task, void *data),
 438                          void *data)
 439 {
 440         pid_t pid[tasks];
 441         int i;
 442
 443         for (i = 0; i < tasks; i++) {
 444                 pid[i] = fork();
 445                 if (pid[i] == 0) {
 446                         fn(i, data);
 447                         exit(0);
 448                 } else if (pid[i] == -1) {
 449                         printf("Couldn't spawn #%d process!\n", i);
 450                         exit(1);
 451                 }
 452         }
 453
 454         for (i = 0; i < tasks; i++) {
 455                 int status;
 456
 457                 assert(waitpid(pid[i], &status, 0) == pid[i]);
 458                 assert(status == 0);
 459         }
 460 }
 461
 462 static void test_map_stress(void)
 463 {
 464         run_parallel(100, test_hashmap, NULL);
 465         run_parallel(100, test_hashmap_percpu, NULL);
 466         run_parallel(100, test_hashmap_sizes, NULL);
 467
 468         run_parallel(100, test_arraymap, NULL);
 469         run_parallel(100, test_arraymap_percpu, NULL);
 470 }
 471
 472 #define TASKS 1024
 473
 474 #define DO_UPDATE 1
 475 #define DO_DELETE 0
 476
 477 static void do_work(int fn, void *data)
 478 {
 479         int do_update = ((int *)data)[1];
 480         int fd = ((int *)data)[0];
 481         int i, key, value;
 482
 483         for (i = fn; i < MAP_SIZE; i += TASKS) {
 484                 key = value = i;
 485
 486                 if (do_update) {
 487                         assert(bpf_map_update_elem(fd, &key, &value,
 488                                                    BPF_NOEXIST) == 0);
 489                         assert(bpf_map_update_elem(fd, &key, &value,
 490                                                    BPF_EXIST) == 0);
 491                 } else {
 492                         assert(bpf_map_delete_elem(fd, &key) == 0);
 493                 }
 494         }
 495 }
 496
 497 static void test_map_parallel(void)
 498 {
 499         int i, fd, key = 0, value = 0;
 500         int data[2];
 501
 502         fd = bpf_create_map(BPF_MAP_TYPE_HASH, sizeof(key), sizeof(value),
 503                             MAP_SIZE, map_flags);
 504         if (fd < 0) {
 505                 printf("Failed to create map for parallel test '%s'!\n",
 506                        strerror(errno));
 507                 exit(1);
 508         }
 509
 510         /* Use the same fd in children to add elements to this map:
 511          * child_0 adds key=0, key=1024, key=2048, ...
 512          * child_1 adds key=1, key=1025, key=2049, ...
 513          * child_1023 adds key=1023, ...
 514          */
 515         data[0] = fd;
 516         data[1] = DO_UPDATE;
 517         run_parallel(TASKS, do_work, data);
 518
 519         /* Check that key=0 is already there. */
 520         assert(bpf_map_update_elem(fd, &key, &value, BPF_NOEXIST) == -1 &&
 521                errno == EEXIST);
 522
 523         /* Check that all elements were inserted. */
 524         assert(bpf_map_get_next_key(fd, NULL, &key) == 0);
 525         key = -1;
 526         for (i = 0; i < MAP_SIZE; i++)
 527                 assert(bpf_map_get_next_key(fd, &key, &key) == 0);
 528         assert(bpf_map_get_next_key(fd, &key, &key) == -1 && errno == ENOENT);
 529
 530         /* Another check for all elements */
 531         for (i = 0; i < MAP_SIZE; i++) {
 532                 key = MAP_SIZE - i - 1;
 533
 534                 assert(bpf_map_lookup_elem(fd, &key, &value) == 0 &&
 535                        value == key);
 536         }
 537
 538         /* Now let's delete all elemenets in parallel. */
 539         data[1] = DO_DELETE;
 540         run_parallel(TASKS, do_work, data);
 541
 542         /* Nothing should be left. */
 543         key = -1;
 544         assert(bpf_map_get_next_key(fd, NULL, &key) == -1 && errno == ENOENT);
 545         assert(bpf_map_get_next_key(fd, &key, &key) == -1 && errno == ENOENT);
 546 }
 547
 548 static void run_all_tests(void)
 549 {
 550         test_hashmap(0, NULL);
 551         test_hashmap_percpu(0, NULL);
 552
 553         test_arraymap(0, NULL);
 554         test_arraymap_percpu(0, NULL);
 555
 556         test_arraymap_percpu_many_keys();
 557
 558         test_map_large();
 559         test_map_parallel();
 560         test_map_stress();
 561 }
 562
 563 int main(void)
 564 {
 565         struct rlimit rinf = { RLIM_INFINITY, RLIM_INFINITY };
 566
 567         setrlimit(RLIMIT_MEMLOCK, &rinf);
 568
 569         map_flags = 0;
 570         run_all_tests();
 571
 572         map_flags = BPF_F_NO_PREALLOC;
 573         run_all_tests();
 574
 575         printf("test_maps: OK\n");
 576         return 0;
 577 }