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