test_maps.c 14.9 KB
Newer Older
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23
/*
 * Testsuite for eBPF maps
 *
 * Copyright (c) 2014 PLUMgrid, http://plumgrid.com
 * Copyright (c) 2016 Facebook
 *
 * This program is free software; you can redistribute it and/or
 * modify it under the terms of version 2 of the GNU General Public
 * License as published by the Free Software Foundation.
 */

#include <stdio.h>
#include <unistd.h>
#include <errno.h>
#include <string.h>
#include <assert.h>
#include <stdlib.h>

#include <sys/wait.h>
#include <sys/resource.h>

#include <linux/bpf.h>

24
#include <bpf/bpf.h>
25
#include "bpf_util.h"
26 27 28 29 30

static int map_flags;

static void test_hashmap(int task, void *data)
{
31
	long long key, next_key, first_key, value;
32 33
	int fd;

34
	fd = bpf_create_map(BPF_MAP_TYPE_HASH, sizeof(key), sizeof(value),
35 36 37 38 39 40 41 42 43
			    2, map_flags);
	if (fd < 0) {
		printf("Failed to create hashmap '%s'!\n", strerror(errno));
		exit(1);
	}

	key = 1;
	value = 1234;
	/* Insert key=1 element. */
44
	assert(bpf_map_update_elem(fd, &key, &value, BPF_ANY) == 0);
45 46 47

	value = 0;
	/* BPF_NOEXIST means add new element if it doesn't exist. */
48
	assert(bpf_map_update_elem(fd, &key, &value, BPF_NOEXIST) == -1 &&
49 50 51 52
	       /* key=1 already exists. */
	       errno == EEXIST);

	/* -1 is an invalid flag. */
53 54
	assert(bpf_map_update_elem(fd, &key, &value, -1) == -1 &&
	       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 60

	key = 2;
	/* 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 66 67 68
	       /* key=2 is not there. */
	       errno == ENOENT);

	/* Insert key=2 element. */
69
	assert(bpf_map_update_elem(fd, &key, &value, BPF_NOEXIST) == 0);
70 71 72 73 74

	/* key=1 and key=2 were inserted, check that key=0 cannot be
	 * inserted due to max_entries limit.
	 */
	key = 0;
75
	assert(bpf_map_update_elem(fd, &key, &value, BPF_NOEXIST) == -1 &&
76 77 78 79
	       errno == E2BIG);

	/* Update existing element, though the map is full. */
	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 84 85
	key = 3;
	assert(bpf_map_update_elem(fd, &key, &value, BPF_NOEXIST) == -1 &&
	       errno == E2BIG);
86 87 88

	/* Check that key = 0 doesn't exist. */
	key = 0;
89
	assert(bpf_map_delete_elem(fd, &key) == -1 && errno == ENOENT);
90 91

	/* Iterate over two elements. */
92 93
	assert(bpf_map_get_next_key(fd, NULL, &first_key) == 0 &&
	       (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 98
	       (next_key == 1 || next_key == 2) &&
	       (next_key != first_key));
99
	assert(bpf_map_get_next_key(fd, &next_key, &next_key) == -1 &&
100 101 102 103
	       errno == ENOENT);

	/* Delete both elements. */
	key = 1;
104
	assert(bpf_map_delete_elem(fd, &key) == 0);
105
	key = 2;
106 107
	assert(bpf_map_delete_elem(fd, &key) == 0);
	assert(bpf_map_delete_elem(fd, &key) == -1 && errno == ENOENT);
108 109 110

	key = 0;
	/* Check that map is empty. */
111 112
	assert(bpf_map_get_next_key(fd, NULL, &next_key) == -1 &&
	       errno == ENOENT);
113
	assert(bpf_map_get_next_key(fd, &key, &next_key) == -1 &&
114 115 116 117 118
	       errno == ENOENT);

	close(fd);
}

119 120 121 122 123 124 125 126 127 128 129 130 131 132 133 134 135 136
static void test_hashmap_sizes(int task, void *data)
{
	int fd, i, j;

	for (i = 1; i <= 512; i <<= 1)
		for (j = 1; j <= 1 << 18; j <<= 1) {
			fd = bpf_create_map(BPF_MAP_TYPE_HASH, i, j,
					    2, map_flags);
			if (fd < 0) {
				printf("Failed to create hashmap key=%d value=%d '%s'\n",
				       i, j, strerror(errno));
				exit(1);
			}
			close(fd);
			usleep(10); /* give kernel time to destroy */
		}
}

137 138
static void test_hashmap_percpu(int task, void *data)
{
139
	unsigned int nr_cpus = bpf_num_possible_cpus();
140
	BPF_DECLARE_PERCPU(long, value);
141
	long long key, next_key, first_key;
142 143 144
	int expected_key_mask = 0;
	int fd, i;

145
	fd = bpf_create_map(BPF_MAP_TYPE_PERCPU_HASH, sizeof(key),
146
			    sizeof(bpf_percpu(value, 0)), 2, map_flags);
147 148 149 150 151 152
	if (fd < 0) {
		printf("Failed to create hashmap '%s'!\n", strerror(errno));
		exit(1);
	}

	for (i = 0; i < nr_cpus; i++)
153
		bpf_percpu(value, i) = i + 100;
154 155 156 157

	key = 1;
	/* Insert key=1 element. */
	assert(!(expected_key_mask & key));
158
	assert(bpf_map_update_elem(fd, &key, value, BPF_ANY) == 0);
159 160 161
	expected_key_mask |= key;

	/* BPF_NOEXIST means add new element if it doesn't exist. */
162
	assert(bpf_map_update_elem(fd, &key, value, BPF_NOEXIST) == -1 &&
163 164 165 166
	       /* key=1 already exists. */
	       errno == EEXIST);

	/* -1 is an invalid flag. */
167 168
	assert(bpf_map_update_elem(fd, &key, value, -1) == -1 &&
	       errno == EINVAL);
169 170 171 172

	/* Check that key=1 can be found. Value could be 0 if the lookup
	 * was run from a different CPU.
	 */
173 174 175
	bpf_percpu(value, 0) = 1;
	assert(bpf_map_lookup_elem(fd, &key, value) == 0 &&
	       bpf_percpu(value, 0) == 100);
176 177 178

	key = 2;
	/* 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 184 185 186 187
	       /* key=2 is not there. */
	       errno == ENOENT);

	/* Insert key=2 element. */
	assert(!(expected_key_mask & key));
188
	assert(bpf_map_update_elem(fd, &key, value, BPF_NOEXIST) == 0);
189 190 191 192 193 194
	expected_key_mask |= key;

	/* key=1 and key=2 were inserted, check that key=0 cannot be
	 * inserted due to max_entries limit.
	 */
	key = 0;
195
	assert(bpf_map_update_elem(fd, &key, value, BPF_NOEXIST) == -1 &&
196 197 198
	       errno == E2BIG);

	/* 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 203
	assert(bpf_map_get_next_key(fd, NULL, &first_key) == 0 &&
	       ((expected_key_mask & first_key) == first_key));
204
	while (!bpf_map_get_next_key(fd, &key, &next_key)) {
205 206 207 208
		if (first_key) {
			assert(next_key == first_key);
			first_key = 0;
		}
209 210 211
		assert((expected_key_mask & next_key) == next_key);
		expected_key_mask &= ~next_key;

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 218 219 220 221 222

		key = next_key;
	}
	assert(errno == ENOENT);

	/* Update with BPF_EXIST. */
	key = 1;
223
	assert(bpf_map_update_elem(fd, &key, value, BPF_EXIST) == 0);
224 225 226

	/* Delete both elements. */
	key = 1;
227
	assert(bpf_map_delete_elem(fd, &key) == 0);
228
	key = 2;
229 230
	assert(bpf_map_delete_elem(fd, &key) == 0);
	assert(bpf_map_delete_elem(fd, &key) == -1 && errno == ENOENT);
231 232 233

	key = 0;
	/* Check that map is empty. */
234 235
	assert(bpf_map_get_next_key(fd, NULL, &next_key) == -1 &&
	       errno == ENOENT);
236
	assert(bpf_map_get_next_key(fd, &key, &next_key) == -1 &&
237 238 239 240 241 242 243 244 245 246
	       errno == ENOENT);

	close(fd);
}

static void test_arraymap(int task, void *data)
{
	int key, next_key, fd;
	long long value;

247
	fd = bpf_create_map(BPF_MAP_TYPE_ARRAY, sizeof(key), sizeof(value),
248 249 250 251 252 253 254 255 256
			    2, 0);
	if (fd < 0) {
		printf("Failed to create arraymap '%s'!\n", strerror(errno));
		exit(1);
	}

	key = 1;
	value = 1234;
	/* 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 262 263
	       errno == EEXIST);

	/* Check that key=1 can be found. */
264
	assert(bpf_map_lookup_elem(fd, &key, &value) == 0 && value == 1234);
265 266 267

	key = 0;
	/* Check that key=0 is also found and zero initialized. */
268
	assert(bpf_map_lookup_elem(fd, &key, &value) == 0 && value == 0);
269 270 271 272 273

	/* key=0 and key=1 were inserted, check that key=2 cannot be inserted
	 * due to max_entries limit.
	 */
	key = 2;
274
	assert(bpf_map_update_elem(fd, &key, &value, BPF_EXIST) == -1 &&
275 276 277
	       errno == E2BIG);

	/* 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 282
	assert(bpf_map_get_next_key(fd, NULL, &next_key) == 0 &&
	       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 289 290 291
	       errno == ENOENT);

	/* Delete shouldn't succeed. */
	key = 1;
292
	assert(bpf_map_delete_elem(fd, &key) == -1 && errno == EINVAL);
293 294 295 296 297 298

	close(fd);
}

static void test_arraymap_percpu(int task, void *data)
{
299
	unsigned int nr_cpus = bpf_num_possible_cpus();
300
	BPF_DECLARE_PERCPU(long, values);
301 302
	int key, next_key, fd, i;

303
	fd = bpf_create_map(BPF_MAP_TYPE_PERCPU_ARRAY, sizeof(key),
304
			    sizeof(bpf_percpu(values, 0)), 2, 0);
305 306 307 308 309 310
	if (fd < 0) {
		printf("Failed to create arraymap '%s'!\n", strerror(errno));
		exit(1);
	}

	for (i = 0; i < nr_cpus; i++)
311
		bpf_percpu(values, i) = i + 100;
312 313 314

	key = 1;
	/* 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 320 321
	       errno == EEXIST);

	/* Check that key=1 can be found. */
322 323
	assert(bpf_map_lookup_elem(fd, &key, values) == 0 &&
	       bpf_percpu(values, 0) == 100);
324 325 326

	key = 0;
	/* Check that key=0 is also found and zero initialized. */
327
	assert(bpf_map_lookup_elem(fd, &key, values) == 0 &&
328 329
	       bpf_percpu(values, 0) == 0 &&
	       bpf_percpu(values, nr_cpus - 1) == 0);
330 331 332

	/* Check that key=2 cannot be inserted due to max_entries limit. */
	key = 2;
333
	assert(bpf_map_update_elem(fd, &key, values, BPF_EXIST) == -1 &&
334 335 336
	       errno == E2BIG);

	/* 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 341
	assert(bpf_map_get_next_key(fd, NULL, &next_key) == 0 &&
	       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 348 349 350
	       errno == ENOENT);

	/* Delete shouldn't succeed. */
	key = 1;
351
	assert(bpf_map_delete_elem(fd, &key) == -1 && errno == EINVAL);
352 353 354 355 356 357

	close(fd);
}

static void test_arraymap_percpu_many_keys(void)
{
358
	unsigned int nr_cpus = bpf_num_possible_cpus();
359
	BPF_DECLARE_PERCPU(long, values);
360 361 362 363
	/* nr_keys is not too large otherwise the test stresses percpu
	 * allocator more than anything else
	 */
	unsigned int nr_keys = 2000;
364 365
	int key, fd, i;

366
	fd = bpf_create_map(BPF_MAP_TYPE_PERCPU_ARRAY, sizeof(key),
367
			    sizeof(bpf_percpu(values, 0)), nr_keys, 0);
368 369 370 371 372 373 374
	if (fd < 0) {
		printf("Failed to create per-cpu arraymap '%s'!\n",
		       strerror(errno));
		exit(1);
	}

	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 381

	for (key = 0; key < nr_keys; key++) {
		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 391 392 393 394 395 396 397 398 399 400 401 402 403
	}

	close(fd);
}

#define MAP_SIZE (32 * 1024)

static void test_map_large(void)
{
	struct bigkey {
		int a;
		char b[116];
		long long c;
	} key;
	int fd, i, value;

404
	fd = bpf_create_map(BPF_MAP_TYPE_HASH, sizeof(key), sizeof(value),
405 406 407 408 409 410 411 412 413 414
			    MAP_SIZE, map_flags);
	if (fd < 0) {
		printf("Failed to create large map '%s'!\n", strerror(errno));
		exit(1);
	}

	for (i = 0; i < MAP_SIZE; i++) {
		key = (struct bigkey) { .c = i };
		value = i;

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 421 422
	       errno == E2BIG);

	/* Iterate through all elements. */
423 424
	assert(bpf_map_get_next_key(fd, NULL, &key) == 0);
	key.c = -1;
425
	for (i = 0; i < MAP_SIZE; i++)
426 427
		assert(bpf_map_get_next_key(fd, &key, &key) == 0);
	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 435 436 437 438 439 440 441 442 443 444 445 446 447 448 449 450 451 452 453 454 455 456 457 458 459 460 461 462 463 464 465

	close(fd);
}

static void run_parallel(int tasks, void (*fn)(int task, void *data),
			 void *data)
{
	pid_t pid[tasks];
	int i;

	for (i = 0; i < tasks; i++) {
		pid[i] = fork();
		if (pid[i] == 0) {
			fn(i, data);
			exit(0);
		} else if (pid[i] == -1) {
			printf("Couldn't spawn #%d process!\n", i);
			exit(1);
		}
	}

	for (i = 0; i < tasks; i++) {
		int status;

		assert(waitpid(pid[i], &status, 0) == pid[i]);
		assert(status == 0);
	}
}

static void test_map_stress(void)
{
	run_parallel(100, test_hashmap, NULL);
	run_parallel(100, test_hashmap_percpu, NULL);
466
	run_parallel(100, test_hashmap_sizes, NULL);
467 468 469 470 471 472 473 474 475 476 477 478 479 480 481 482 483 484 485 486

	run_parallel(100, test_arraymap, NULL);
	run_parallel(100, test_arraymap_percpu, NULL);
}

#define TASKS 1024

#define DO_UPDATE 1
#define DO_DELETE 0

static void do_work(int fn, void *data)
{
	int do_update = ((int *)data)[1];
	int fd = ((int *)data)[0];
	int i, key, value;

	for (i = fn; i < MAP_SIZE; i += TASKS) {
		key = value = i;

		if (do_update) {
487 488 489 490
			assert(bpf_map_update_elem(fd, &key, &value,
						   BPF_NOEXIST) == 0);
			assert(bpf_map_update_elem(fd, &key, &value,
						   BPF_EXIST) == 0);
491
		} else {
492
			assert(bpf_map_delete_elem(fd, &key) == 0);
493 494 495 496 497 498 499 500 501
		}
	}
}

static void test_map_parallel(void)
{
	int i, fd, key = 0, value = 0;
	int data[2];

502
	fd = bpf_create_map(BPF_MAP_TYPE_HASH, sizeof(key), sizeof(value),
503 504 505 506 507 508 509 510 511 512 513 514 515 516 517 518 519
			    MAP_SIZE, map_flags);
	if (fd < 0) {
		printf("Failed to create map for parallel test '%s'!\n",
		       strerror(errno));
		exit(1);
	}

	/* Use the same fd in children to add elements to this map:
	 * child_0 adds key=0, key=1024, key=2048, ...
	 * child_1 adds key=1, key=1025, key=2049, ...
	 * child_1023 adds key=1023, ...
	 */
	data[0] = fd;
	data[1] = DO_UPDATE;
	run_parallel(TASKS, do_work, data);

	/* Check that key=0 is already there. */
520
	assert(bpf_map_update_elem(fd, &key, &value, BPF_NOEXIST) == -1 &&
521 522 523
	       errno == EEXIST);

	/* Check that all elements were inserted. */
524
	assert(bpf_map_get_next_key(fd, NULL, &key) == 0);
525 526
	key = -1;
	for (i = 0; i < MAP_SIZE; i++)
527 528
		assert(bpf_map_get_next_key(fd, &key, &key) == 0);
	assert(bpf_map_get_next_key(fd, &key, &key) == -1 && errno == ENOENT);
529 530 531 532 533

	/* Another check for all elements */
	for (i = 0; i < MAP_SIZE; i++) {
		key = MAP_SIZE - i - 1;

534
		assert(bpf_map_lookup_elem(fd, &key, &value) == 0 &&
535 536 537 538 539 540 541 542 543
		       value == key);
	}

	/* Now let's delete all elemenets in parallel. */
	data[1] = DO_DELETE;
	run_parallel(TASKS, do_work, data);

	/* Nothing should be left. */
	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 549 550 551 552 553 554 555 556 557 558 559 560 561 562 563 564 565 566 567 568 569 570 571 572 573 574 575 576 577
}

static void run_all_tests(void)
{
	test_hashmap(0, NULL);
	test_hashmap_percpu(0, NULL);

	test_arraymap(0, NULL);
	test_arraymap_percpu(0, NULL);

	test_arraymap_percpu_many_keys();

	test_map_large();
	test_map_parallel();
	test_map_stress();
}

int main(void)
{
	struct rlimit rinf = { RLIM_INFINITY, RLIM_INFINITY };

	setrlimit(RLIMIT_MEMLOCK, &rinf);

	map_flags = 0;
	run_all_tests();

	map_flags = BPF_F_NO_PREALLOC;
	run_all_tests();

	printf("test_maps: OK\n");
	return 0;
}