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         long long value[nr_cpus];
 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(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                 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         value[0] = 1;
 174         assert(bpf_map_lookup_elem(fd, &key, value) == 0 && value[0] == 100);
 175
 176         key = 2;
 177         /* Check that key=2 is not found. */
 178         assert(bpf_map_lookup_elem(fd, &key, value) == -1 && errno == ENOENT);
 179
 180         /* BPF_EXIST means update existing element. */
 181         assert(bpf_map_update_elem(fd, &key, value, BPF_EXIST) == -1 &&
 182                /* key=2 is not there. */
 183                errno == ENOENT);
 184
 185         /* Insert key=2 element. */
 186         assert(!(expected_key_mask & key));
 187         assert(bpf_map_update_elem(fd, &key, value, BPF_NOEXIST) == 0);
 188         expected_key_mask |= key;
 189
 190         /* key=1 and key=2 were inserted, check that key=0 cannot be
 191          * inserted due to max_entries limit.
 192          */
 193         key = 0;
 194         assert(bpf_map_update_elem(fd, &key, value, BPF_NOEXIST) == -1 &&
 195                errno == E2BIG);
 196
 197         /* Check that key = 0 doesn't exist. */
 198         assert(bpf_map_delete_elem(fd, &key) == -1 && errno == ENOENT);
 199
 200         /* Iterate over two elements. */
 201         assert(bpf_map_get_next_key(fd, NULL, &first_key) == 0 &&
 202                ((expected_key_mask & first_key) == first_key));
 203         while (!bpf_map_get_next_key(fd, &key, &next_key)) {
 204                 if (first_key) {
 205                         assert(next_key == first_key);
 206                         first_key = 0;
 207                 }
 208                 assert((expected_key_mask & next_key) == next_key);
 209                 expected_key_mask &= ~next_key;
 210
 211                 assert(bpf_map_lookup_elem(fd, &next_key, value) == 0);
 212
 213                 for (i = 0; i < nr_cpus; i++)
 214                         assert(value[i] == i + 100);
 215
 216                 key = next_key;
 217         }
 218         assert(errno == ENOENT);
 219
 220         /* Update with BPF_EXIST. */
 221         key = 1;
 222         assert(bpf_map_update_elem(fd, &key, value, BPF_EXIST) == 0);
 223
 224         /* Delete both elements. */
 225         key = 1;
 226         assert(bpf_map_delete_elem(fd, &key) == 0);
 227         key = 2;
 228         assert(bpf_map_delete_elem(fd, &key) == 0);
 229         assert(bpf_map_delete_elem(fd, &key) == -1 && errno == ENOENT);
 230
 231         key = 0;
 232         /* Check that map is empty. */
 233         assert(bpf_map_get_next_key(fd, NULL, &next_key) == -1 &&
 234                errno == ENOENT);
 235         assert(bpf_map_get_next_key(fd, &key, &next_key) == -1 &&
 236                errno == ENOENT);
 237
 238         close(fd);
 239 }
 240
 241 static void test_arraymap(int task, void *data)
 242 {
 243         int key, next_key, fd;
 244         long long value;
 245
 246         fd = bpf_create_map(BPF_MAP_TYPE_ARRAY, sizeof(key), sizeof(value),
 247                             2, 0);
 248         if (fd < 0) {
 249                 printf("Failed to create arraymap '%s'!\n", strerror(errno));
 250                 exit(1);
 251         }
 252
 253         key = 1;
 254         value = 1234;
 255         /* Insert key=1 element. */
 256         assert(bpf_map_update_elem(fd, &key, &value, BPF_ANY) == 0);
 257
 258         value = 0;
 259         assert(bpf_map_update_elem(fd, &key, &value, BPF_NOEXIST) == -1 &&
 260                errno == EEXIST);
 261
 262         /* Check that key=1 can be found. */
 263         assert(bpf_map_lookup_elem(fd, &key, &value) == 0 && value == 1234);
 264
 265         key = 0;
 266         /* Check that key=0 is also found and zero initialized. */
 267         assert(bpf_map_lookup_elem(fd, &key, &value) == 0 && value == 0);
 268
 269         /* key=0 and key=1 were inserted, check that key=2 cannot be inserted
 270          * due to max_entries limit.
 271          */
 272         key = 2;
 273         assert(bpf_map_update_elem(fd, &key, &value, BPF_EXIST) == -1 &&
 274                errno == E2BIG);
 275
 276         /* Check that key = 2 doesn't exist. */
 277         assert(bpf_map_lookup_elem(fd, &key, &value) == -1 && errno == ENOENT);
 278
 279         /* Iterate over two elements. */
 280         assert(bpf_map_get_next_key(fd, NULL, &next_key) == 0 &&
 281                next_key == 0);
 282         assert(bpf_map_get_next_key(fd, &key, &next_key) == 0 &&
 283                next_key == 0);
 284         assert(bpf_map_get_next_key(fd, &next_key, &next_key) == 0 &&
 285                next_key == 1);
 286         assert(bpf_map_get_next_key(fd, &next_key, &next_key) == -1 &&
 287                errno == ENOENT);
 288
 289         /* Delete shouldn't succeed. */
 290         key = 1;
 291         assert(bpf_map_delete_elem(fd, &key) == -1 && errno == EINVAL);
 292
 293         close(fd);
 294 }
 295
 296 static void test_arraymap_percpu(int task, void *data)
 297 {
 298         unsigned int nr_cpus = bpf_num_possible_cpus();
 299         int key, next_key, fd, i;
 300         long long values[nr_cpus];
 301
 302         fd = bpf_create_map(BPF_MAP_TYPE_PERCPU_ARRAY, sizeof(key),
 303                             sizeof(values[0]), 2, 0);
 304         if (fd < 0) {
 305                 printf("Failed to create arraymap '%s'!\n", strerror(errno));
 306                 exit(1);
 307         }
 308
 309         for (i = 0; i < nr_cpus; i++)
 310                 values[i] = i + 100;
 311
 312         key = 1;
 313         /* Insert key=1 element. */
 314         assert(bpf_map_update_elem(fd, &key, values, BPF_ANY) == 0);
 315
 316         values[0] = 0;
 317         assert(bpf_map_update_elem(fd, &key, values, BPF_NOEXIST) == -1 &&
 318                errno == EEXIST);
 319
 320         /* Check that key=1 can be found. */
 321         assert(bpf_map_lookup_elem(fd, &key, values) == 0 && values[0] == 100);
 322
 323         key = 0;
 324         /* Check that key=0 is also found and zero initialized. */
 325         assert(bpf_map_lookup_elem(fd, &key, values) == 0 &&
 326                values[0] == 0 && values[nr_cpus - 1] == 0);
 327
 328         /* Check that key=2 cannot be inserted due to max_entries limit. */
 329         key = 2;
 330         assert(bpf_map_update_elem(fd, &key, values, BPF_EXIST) == -1 &&
 331                errno == E2BIG);
 332
 333         /* Check that key = 2 doesn't exist. */
 334         assert(bpf_map_lookup_elem(fd, &key, values) == -1 && errno == ENOENT);
 335
 336         /* Iterate over two elements. */
 337         assert(bpf_map_get_next_key(fd, NULL, &next_key) == 0 &&
 338                next_key == 0);
 339         assert(bpf_map_get_next_key(fd, &key, &next_key) == 0 &&
 340                next_key == 0);
 341         assert(bpf_map_get_next_key(fd, &next_key, &next_key) == 0 &&
 342                next_key == 1);
 343         assert(bpf_map_get_next_key(fd, &next_key, &next_key) == -1 &&
 344                errno == ENOENT);
 345
 346         /* Delete shouldn't succeed. */
 347         key = 1;
 348         assert(bpf_map_delete_elem(fd, &key) == -1 && errno == EINVAL);
 349
 350         close(fd);
 351 }
 352
 353 static void test_arraymap_percpu_many_keys(void)
 354 {
 355         unsigned int nr_cpus = bpf_num_possible_cpus();
 356         /* nr_keys is not too large otherwise the test stresses percpu
 357          * allocator more than anything else
 358          */
 359         unsigned int nr_keys = 2000;
 360         long long values[nr_cpus];
 361         int key, fd, i;
 362
 363         fd = bpf_create_map(BPF_MAP_TYPE_PERCPU_ARRAY, sizeof(key),
 364                             sizeof(values[0]), nr_keys, 0);
 365         if (fd < 0) {
 366                 printf("Failed to create per-cpu arraymap '%s'!\n",
 367                        strerror(errno));
 368                 exit(1);
 369         }
 370
 371         for (i = 0; i < nr_cpus; i++)
 372                 values[i] = i + 10;
 373
 374         for (key = 0; key < nr_keys; key++)
 375                 assert(bpf_map_update_elem(fd, &key, values, BPF_ANY) == 0);
 376
 377         for (key = 0; key < nr_keys; key++) {
 378                 for (i = 0; i < nr_cpus; i++)
 379                         values[i] = 0;
 380
 381                 assert(bpf_map_lookup_elem(fd, &key, values) == 0);
 382
 383                 for (i = 0; i < nr_cpus; i++)
 384                         assert(values[i] == i + 10);
 385         }
 386
 387         close(fd);
 388 }
 389
 390 #define MAP_SIZE (32 * 1024)
 391
 392 static void test_map_large(void)
 393 {
 394         struct bigkey {
 395                 int a;
 396                 char b[116];
 397                 long long c;
 398         } key;
 399         int fd, i, value;
 400
 401         fd = bpf_create_map(BPF_MAP_TYPE_HASH, sizeof(key), sizeof(value),
 402                             MAP_SIZE, map_flags);
 403         if (fd < 0) {
 404                 printf("Failed to create large map '%s'!\n", strerror(errno));
 405                 exit(1);
 406         }
 407
 408         for (i = 0; i < MAP_SIZE; i++) {
 409                 key = (struct bigkey) { .c = i };
 410                 value = i;
 411
 412                 assert(bpf_map_update_elem(fd, &key, &value, BPF_NOEXIST) == 0);
 413         }
 414
 415         key.c = -1;
 416         assert(bpf_map_update_elem(fd, &key, &value, BPF_NOEXIST) == -1 &&
 417                errno == E2BIG);
 418
 419         /* Iterate through all elements. */
 420         assert(bpf_map_get_next_key(fd, NULL, &key) == 0);
 421         key.c = -1;
 422         for (i = 0; i < MAP_SIZE; i++)
 423                 assert(bpf_map_get_next_key(fd, &key, &key) == 0);
 424         assert(bpf_map_get_next_key(fd, &key, &key) == -1 && errno == ENOENT);
 425
 426         key.c = 0;
 427         assert(bpf_map_lookup_elem(fd, &key, &value) == 0 && value == 0);
 428         key.a = 1;
 429         assert(bpf_map_lookup_elem(fd, &key, &value) == -1 && errno == ENOENT);
 430
 431         close(fd);
 432 }
 433
 434 static void run_parallel(int tasks, void (*fn)(int task, void *data),
 435                          void *data)
 436 {
 437         pid_t pid[tasks];
 438         int i;
 439
 440         for (i = 0; i < tasks; i++) {
 441                 pid[i] = fork();
 442                 if (pid[i] == 0) {
 443                         fn(i, data);
 444                         exit(0);
 445                 } else if (pid[i] == -1) {
 446                         printf("Couldn't spawn #%d process!\n", i);
 447                         exit(1);
 448                 }
 449         }
 450
 451         for (i = 0; i < tasks; i++) {
 452                 int status;
 453
 454                 assert(waitpid(pid[i], &status, 0) == pid[i]);
 455                 assert(status == 0);
 456         }
 457 }
 458
 459 static void test_map_stress(void)
 460 {
 461         run_parallel(100, test_hashmap, NULL);
 462         run_parallel(100, test_hashmap_percpu, NULL);
 463         run_parallel(100, test_hashmap_sizes, NULL);
 464
 465         run_parallel(100, test_arraymap, NULL);
 466         run_parallel(100, test_arraymap_percpu, NULL);
 467 }
 468
 469 #define TASKS 1024
 470
 471 #define DO_UPDATE 1
 472 #define DO_DELETE 0
 473
 474 static void do_work(int fn, void *data)
 475 {
 476         int do_update = ((int *)data)[1];
 477         int fd = ((int *)data)[0];
 478         int i, key, value;
 479
 480         for (i = fn; i < MAP_SIZE; i += TASKS) {
 481                 key = value = i;
 482
 483                 if (do_update) {
 484                         assert(bpf_map_update_elem(fd, &key, &value,
 485                                                    BPF_NOEXIST) == 0);
 486                         assert(bpf_map_update_elem(fd, &key, &value,
 487                                                    BPF_EXIST) == 0);
 488                 } else {
 489                         assert(bpf_map_delete_elem(fd, &key) == 0);
 490                 }
 491         }
 492 }
 493
 494 static void test_map_parallel(void)
 495 {
 496         int i, fd, key = 0, value = 0;
 497         int data[2];
 498
 499         fd = bpf_create_map(BPF_MAP_TYPE_HASH, sizeof(key), sizeof(value),
 500                             MAP_SIZE, map_flags);
 501         if (fd < 0) {
 502                 printf("Failed to create map for parallel test '%s'!\n",
 503                        strerror(errno));
 504                 exit(1);
 505         }
 506
 507         /* Use the same fd in children to add elements to this map:
 508          * child_0 adds key=0, key=1024, key=2048, ...
 509          * child_1 adds key=1, key=1025, key=2049, ...
 510          * child_1023 adds key=1023, ...
 511          */
 512         data[0] = fd;
 513         data[1] = DO_UPDATE;
 514         run_parallel(TASKS, do_work, data);
 515
 516         /* Check that key=0 is already there. */
 517         assert(bpf_map_update_elem(fd, &key, &value, BPF_NOEXIST) == -1 &&
 518                errno == EEXIST);
 519
 520         /* Check that all elements were inserted. */
 521         assert(bpf_map_get_next_key(fd, NULL, &key) == 0);
 522         key = -1;
 523         for (i = 0; i < MAP_SIZE; i++)
 524                 assert(bpf_map_get_next_key(fd, &key, &key) == 0);
 525         assert(bpf_map_get_next_key(fd, &key, &key) == -1 && errno == ENOENT);
 526
 527         /* Another check for all elements */
 528         for (i = 0; i < MAP_SIZE; i++) {
 529                 key = MAP_SIZE - i - 1;
 530
 531                 assert(bpf_map_lookup_elem(fd, &key, &value) == 0 &&
 532                        value == key);
 533         }
 534
 535         /* Now let's delete all elemenets in parallel. */
 536         data[1] = DO_DELETE;
 537         run_parallel(TASKS, do_work, data);
 538
 539         /* Nothing should be left. */
 540         key = -1;
 541         assert(bpf_map_get_next_key(fd, NULL, &key) == -1 && errno == ENOENT);
 542         assert(bpf_map_get_next_key(fd, &key, &key) == -1 && errno == ENOENT);
 543 }
 544
 545 static void run_all_tests(void)
 546 {
 547         test_hashmap(0, NULL);
 548         test_hashmap_percpu(0, NULL);
 549
 550         test_arraymap(0, NULL);
 551         test_arraymap_percpu(0, NULL);
 552
 553         test_arraymap_percpu_many_keys();
 554
 555         test_map_large();
 556         test_map_parallel();
 557         test_map_stress();
 558 }
 559
 560 int main(void)
 561 {
 562         struct rlimit rinf = { RLIM_INFINITY, RLIM_INFINITY };
 563
 564         setrlimit(RLIMIT_MEMLOCK, &rinf);
 565
 566         map_flags = 0;
 567         run_all_tests();
 568
 569         map_flags = BPF_F_NO_PREALLOC;
 570         run_all_tests();
 571
 572         printf("test_maps: OK\n");
 573         return 0;
 574 }