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