Loading...
1// SPDX-License-Identifier: GPL-2.0-only
2/*
3 * Copyright (c) 2016 Facebook
4 */
5#define _GNU_SOURCE
6#include <stdio.h>
7#include <unistd.h>
8#include <errno.h>
9#include <string.h>
10#include <assert.h>
11#include <sched.h>
12#include <stdlib.h>
13#include <time.h>
14
15#include <sys/wait.h>
16
17#include <bpf/bpf.h>
18#include <bpf/libbpf.h>
19
20#include "bpf_util.h"
21#include "../../../include/linux/filter.h"
22
23#define LOCAL_FREE_TARGET (128)
24#define PERCPU_FREE_TARGET (4)
25
26static int nr_cpus;
27
28static int create_map(int map_type, int map_flags, unsigned int size)
29{
30 LIBBPF_OPTS(bpf_map_create_opts, opts, .map_flags = map_flags);
31 int map_fd;
32
33 map_fd = bpf_map_create(map_type, NULL, sizeof(unsigned long long),
34 sizeof(unsigned long long), size, &opts);
35
36 if (map_fd == -1)
37 perror("bpf_map_create");
38
39 return map_fd;
40}
41
42static int bpf_map_lookup_elem_with_ref_bit(int fd, unsigned long long key,
43 void *value)
44{
45 struct bpf_insn insns[] = {
46 BPF_LD_MAP_VALUE(BPF_REG_9, 0, 0),
47 BPF_LD_MAP_FD(BPF_REG_1, fd),
48 BPF_LD_IMM64(BPF_REG_3, key),
49 BPF_MOV64_REG(BPF_REG_2, BPF_REG_10),
50 BPF_ALU64_IMM(BPF_ADD, BPF_REG_2, -8),
51 BPF_STX_MEM(BPF_DW, BPF_REG_2, BPF_REG_3, 0),
52 BPF_EMIT_CALL(BPF_FUNC_map_lookup_elem),
53 BPF_JMP_IMM(BPF_JEQ, BPF_REG_0, 0, 4),
54 BPF_LDX_MEM(BPF_DW, BPF_REG_1, BPF_REG_0, 0),
55 BPF_STX_MEM(BPF_DW, BPF_REG_9, BPF_REG_1, 0),
56 BPF_MOV64_IMM(BPF_REG_0, 42),
57 BPF_JMP_IMM(BPF_JA, 0, 0, 1),
58 BPF_MOV64_IMM(BPF_REG_0, 1),
59 BPF_EXIT_INSN(),
60 };
61 __u8 data[64] = {};
62 int mfd, pfd, ret, zero = 0;
63 LIBBPF_OPTS(bpf_test_run_opts, topts,
64 .data_in = data,
65 .data_size_in = sizeof(data),
66 .repeat = 1,
67 );
68
69 mfd = bpf_map_create(BPF_MAP_TYPE_ARRAY, NULL, sizeof(int), sizeof(__u64), 1, NULL);
70 if (mfd < 0)
71 return -1;
72
73 insns[0].imm = mfd;
74
75 pfd = bpf_prog_load(BPF_PROG_TYPE_SCHED_CLS, NULL, "GPL", insns, ARRAY_SIZE(insns), NULL);
76 if (pfd < 0) {
77 close(mfd);
78 return -1;
79 }
80
81 ret = bpf_prog_test_run_opts(pfd, &topts);
82 if (ret < 0 || topts.retval != 42) {
83 ret = -1;
84 } else {
85 assert(!bpf_map_lookup_elem(mfd, &zero, value));
86 ret = 0;
87 }
88 close(pfd);
89 close(mfd);
90 return ret;
91}
92
93static int map_subset(int map0, int map1)
94{
95 unsigned long long next_key = 0;
96 unsigned long long value0[nr_cpus], value1[nr_cpus];
97 int ret;
98
99 while (!bpf_map_get_next_key(map1, &next_key, &next_key)) {
100 assert(!bpf_map_lookup_elem(map1, &next_key, value1));
101 ret = bpf_map_lookup_elem(map0, &next_key, value0);
102 if (ret) {
103 printf("key:%llu not found from map. %s(%d)\n",
104 next_key, strerror(errno), errno);
105 return 0;
106 }
107 if (value0[0] != value1[0]) {
108 printf("key:%llu value0:%llu != value1:%llu\n",
109 next_key, value0[0], value1[0]);
110 return 0;
111 }
112 }
113 return 1;
114}
115
116static int map_equal(int lru_map, int expected)
117{
118 return map_subset(lru_map, expected) && map_subset(expected, lru_map);
119}
120
121static int sched_next_online(int pid, int *next_to_try)
122{
123 cpu_set_t cpuset;
124 int next = *next_to_try;
125 int ret = -1;
126
127 while (next < nr_cpus) {
128 CPU_ZERO(&cpuset);
129 CPU_SET(next++, &cpuset);
130 if (!sched_setaffinity(pid, sizeof(cpuset), &cpuset)) {
131 ret = 0;
132 break;
133 }
134 }
135
136 *next_to_try = next;
137 return ret;
138}
139
140/* Size of the LRU map is 2
141 * Add key=1 (+1 key)
142 * Add key=2 (+1 key)
143 * Lookup Key=1
144 * Add Key=3
145 * => Key=2 will be removed by LRU
146 * Iterate map. Only found key=1 and key=3
147 */
148static void test_lru_sanity0(int map_type, int map_flags)
149{
150 unsigned long long key, value[nr_cpus];
151 int lru_map_fd, expected_map_fd;
152 int next_cpu = 0;
153
154 printf("%s (map_type:%d map_flags:0x%X): ", __func__, map_type,
155 map_flags);
156
157 assert(sched_next_online(0, &next_cpu) != -1);
158
159 if (map_flags & BPF_F_NO_COMMON_LRU)
160 lru_map_fd = create_map(map_type, map_flags, 2 * nr_cpus);
161 else
162 lru_map_fd = create_map(map_type, map_flags, 2);
163 assert(lru_map_fd != -1);
164
165 expected_map_fd = create_map(BPF_MAP_TYPE_HASH, 0, 2);
166 assert(expected_map_fd != -1);
167
168 value[0] = 1234;
169
170 /* insert key=1 element */
171
172 key = 1;
173 assert(!bpf_map_update_elem(lru_map_fd, &key, value, BPF_NOEXIST));
174 assert(!bpf_map_update_elem(expected_map_fd, &key, value,
175 BPF_NOEXIST));
176
177 /* BPF_NOEXIST means: add new element if it doesn't exist */
178 assert(bpf_map_update_elem(lru_map_fd, &key, value, BPF_NOEXIST) == -EEXIST);
179 /* key=1 already exists */
180
181 assert(bpf_map_update_elem(lru_map_fd, &key, value, -1) == -EINVAL);
182
183 /* insert key=2 element */
184
185 /* check that key=2 is not found */
186 key = 2;
187 assert(bpf_map_lookup_elem(lru_map_fd, &key, value) == -ENOENT);
188
189 /* BPF_EXIST means: update existing element */
190 assert(bpf_map_update_elem(lru_map_fd, &key, value, BPF_EXIST) == -ENOENT);
191 /* key=2 is not there */
192
193 assert(!bpf_map_update_elem(lru_map_fd, &key, value, BPF_NOEXIST));
194
195 /* insert key=3 element */
196
197 /* check that key=3 is not found */
198 key = 3;
199 assert(bpf_map_lookup_elem(lru_map_fd, &key, value) == -ENOENT);
200
201 /* check that key=1 can be found and mark the ref bit to
202 * stop LRU from removing key=1
203 */
204 key = 1;
205 assert(!bpf_map_lookup_elem_with_ref_bit(lru_map_fd, key, value));
206 assert(value[0] == 1234);
207
208 key = 3;
209 assert(!bpf_map_update_elem(lru_map_fd, &key, value, BPF_NOEXIST));
210 assert(!bpf_map_update_elem(expected_map_fd, &key, value,
211 BPF_NOEXIST));
212
213 /* key=2 has been removed from the LRU */
214 key = 2;
215 assert(bpf_map_lookup_elem(lru_map_fd, &key, value) == -ENOENT);
216
217 /* lookup elem key=1 and delete it, then check it doesn't exist */
218 key = 1;
219 assert(!bpf_map_lookup_and_delete_elem(lru_map_fd, &key, &value));
220 assert(value[0] == 1234);
221
222 /* remove the same element from the expected map */
223 assert(!bpf_map_delete_elem(expected_map_fd, &key));
224
225 assert(map_equal(lru_map_fd, expected_map_fd));
226
227 close(expected_map_fd);
228 close(lru_map_fd);
229
230 printf("Pass\n");
231}
232
233/* Size of the LRU map is 1.5*tgt_free
234 * Insert 1 to tgt_free (+tgt_free keys)
235 * Lookup 1 to tgt_free/2
236 * Insert 1+tgt_free to 2*tgt_free (+tgt_free keys)
237 * => 1+tgt_free/2 to LOCALFREE_TARGET will be removed by LRU
238 */
239static void test_lru_sanity1(int map_type, int map_flags, unsigned int tgt_free)
240{
241 unsigned long long key, end_key, value[nr_cpus];
242 int lru_map_fd, expected_map_fd;
243 unsigned int batch_size;
244 unsigned int map_size;
245 int next_cpu = 0;
246
247 if (map_flags & BPF_F_NO_COMMON_LRU)
248 /* This test is only applicable to common LRU list */
249 return;
250
251 printf("%s (map_type:%d map_flags:0x%X): ", __func__, map_type,
252 map_flags);
253
254 assert(sched_next_online(0, &next_cpu) != -1);
255
256 batch_size = tgt_free / 2;
257 assert(batch_size * 2 == tgt_free);
258
259 map_size = tgt_free + batch_size;
260 lru_map_fd = create_map(map_type, map_flags, map_size);
261 assert(lru_map_fd != -1);
262
263 expected_map_fd = create_map(BPF_MAP_TYPE_HASH, 0, map_size);
264 assert(expected_map_fd != -1);
265
266 value[0] = 1234;
267
268 /* Insert 1 to tgt_free (+tgt_free keys) */
269 end_key = 1 + tgt_free;
270 for (key = 1; key < end_key; key++)
271 assert(!bpf_map_update_elem(lru_map_fd, &key, value,
272 BPF_NOEXIST));
273
274 /* Lookup 1 to tgt_free/2 */
275 end_key = 1 + batch_size;
276 for (key = 1; key < end_key; key++) {
277 assert(!bpf_map_lookup_elem_with_ref_bit(lru_map_fd, key, value));
278 assert(!bpf_map_update_elem(expected_map_fd, &key, value,
279 BPF_NOEXIST));
280 }
281
282 /* Insert 1+tgt_free to 2*tgt_free
283 * => 1+tgt_free/2 to LOCALFREE_TARGET will be
284 * removed by LRU
285 */
286 key = 1 + tgt_free;
287 end_key = key + tgt_free;
288 for (; key < end_key; key++) {
289 assert(!bpf_map_update_elem(lru_map_fd, &key, value,
290 BPF_NOEXIST));
291 assert(!bpf_map_update_elem(expected_map_fd, &key, value,
292 BPF_NOEXIST));
293 }
294
295 assert(map_equal(lru_map_fd, expected_map_fd));
296
297 close(expected_map_fd);
298 close(lru_map_fd);
299
300 printf("Pass\n");
301}
302
303/* Size of the LRU map 1.5 * tgt_free
304 * Insert 1 to tgt_free (+tgt_free keys)
305 * Update 1 to tgt_free/2
306 * => The original 1 to tgt_free/2 will be removed due to
307 * the LRU shrink process
308 * Re-insert 1 to tgt_free/2 again and do a lookup immeidately
309 * Insert 1+tgt_free to tgt_free*3/2
310 * Insert 1+tgt_free*3/2 to tgt_free*5/2
311 * => Key 1+tgt_free to tgt_free*3/2
312 * will be removed from LRU because it has never
313 * been lookup and ref bit is not set
314 */
315static void test_lru_sanity2(int map_type, int map_flags, unsigned int tgt_free)
316{
317 unsigned long long key, value[nr_cpus];
318 unsigned long long end_key;
319 int lru_map_fd, expected_map_fd;
320 unsigned int batch_size;
321 unsigned int map_size;
322 int next_cpu = 0;
323
324 if (map_flags & BPF_F_NO_COMMON_LRU)
325 /* This test is only applicable to common LRU list */
326 return;
327
328 printf("%s (map_type:%d map_flags:0x%X): ", __func__, map_type,
329 map_flags);
330
331 assert(sched_next_online(0, &next_cpu) != -1);
332
333 batch_size = tgt_free / 2;
334 assert(batch_size * 2 == tgt_free);
335
336 map_size = tgt_free + batch_size;
337 lru_map_fd = create_map(map_type, map_flags, map_size);
338 assert(lru_map_fd != -1);
339
340 expected_map_fd = create_map(BPF_MAP_TYPE_HASH, 0, map_size);
341 assert(expected_map_fd != -1);
342
343 value[0] = 1234;
344
345 /* Insert 1 to tgt_free (+tgt_free keys) */
346 end_key = 1 + tgt_free;
347 for (key = 1; key < end_key; key++)
348 assert(!bpf_map_update_elem(lru_map_fd, &key, value,
349 BPF_NOEXIST));
350
351 /* Any bpf_map_update_elem will require to acquire a new node
352 * from LRU first.
353 *
354 * The local list is running out of free nodes.
355 * It gets from the global LRU list which tries to
356 * shrink the inactive list to get tgt_free
357 * number of free nodes.
358 *
359 * Hence, the oldest key 1 to tgt_free/2
360 * are removed from the LRU list.
361 */
362 key = 1;
363 if (map_type == BPF_MAP_TYPE_LRU_PERCPU_HASH) {
364 assert(!bpf_map_update_elem(lru_map_fd, &key, value,
365 BPF_NOEXIST));
366 assert(!bpf_map_delete_elem(lru_map_fd, &key));
367 } else {
368 assert(bpf_map_update_elem(lru_map_fd, &key, value,
369 BPF_EXIST));
370 }
371
372 /* Re-insert 1 to tgt_free/2 again and do a lookup
373 * immeidately.
374 */
375 end_key = 1 + batch_size;
376 value[0] = 4321;
377 for (key = 1; key < end_key; key++) {
378 assert(bpf_map_lookup_elem(lru_map_fd, &key, value) == -ENOENT);
379 assert(!bpf_map_update_elem(lru_map_fd, &key, value,
380 BPF_NOEXIST));
381 assert(!bpf_map_lookup_elem_with_ref_bit(lru_map_fd, key, value));
382 assert(value[0] == 4321);
383 assert(!bpf_map_update_elem(expected_map_fd, &key, value,
384 BPF_NOEXIST));
385 }
386
387 value[0] = 1234;
388
389 /* Insert 1+tgt_free to tgt_free*3/2 */
390 end_key = 1 + tgt_free + batch_size;
391 for (key = 1 + tgt_free; key < end_key; key++)
392 /* These newly added but not referenced keys will be
393 * gone during the next LRU shrink.
394 */
395 assert(!bpf_map_update_elem(lru_map_fd, &key, value,
396 BPF_NOEXIST));
397
398 /* Insert 1+tgt_free*3/2 to tgt_free*5/2 */
399 end_key = key + tgt_free;
400 for (; key < end_key; key++) {
401 assert(!bpf_map_update_elem(lru_map_fd, &key, value,
402 BPF_NOEXIST));
403 assert(!bpf_map_update_elem(expected_map_fd, &key, value,
404 BPF_NOEXIST));
405 }
406
407 assert(map_equal(lru_map_fd, expected_map_fd));
408
409 close(expected_map_fd);
410 close(lru_map_fd);
411
412 printf("Pass\n");
413}
414
415/* Size of the LRU map is 2*tgt_free
416 * It is to test the active/inactive list rotation
417 * Insert 1 to 2*tgt_free (+2*tgt_free keys)
418 * Lookup key 1 to tgt_free*3/2
419 * Add 1+2*tgt_free to tgt_free*5/2 (+tgt_free/2 keys)
420 * => key 1+tgt_free*3/2 to 2*tgt_free are removed from LRU
421 */
422static void test_lru_sanity3(int map_type, int map_flags, unsigned int tgt_free)
423{
424 unsigned long long key, end_key, value[nr_cpus];
425 int lru_map_fd, expected_map_fd;
426 unsigned int batch_size;
427 unsigned int map_size;
428 int next_cpu = 0;
429
430 if (map_flags & BPF_F_NO_COMMON_LRU)
431 /* This test is only applicable to common LRU list */
432 return;
433
434 printf("%s (map_type:%d map_flags:0x%X): ", __func__, map_type,
435 map_flags);
436
437 assert(sched_next_online(0, &next_cpu) != -1);
438
439 batch_size = tgt_free / 2;
440 assert(batch_size * 2 == tgt_free);
441
442 map_size = tgt_free * 2;
443 lru_map_fd = create_map(map_type, map_flags, map_size);
444 assert(lru_map_fd != -1);
445
446 expected_map_fd = create_map(BPF_MAP_TYPE_HASH, 0, map_size);
447 assert(expected_map_fd != -1);
448
449 value[0] = 1234;
450
451 /* Insert 1 to 2*tgt_free (+2*tgt_free keys) */
452 end_key = 1 + (2 * tgt_free);
453 for (key = 1; key < end_key; key++)
454 assert(!bpf_map_update_elem(lru_map_fd, &key, value,
455 BPF_NOEXIST));
456
457 /* Lookup key 1 to tgt_free*3/2 */
458 end_key = tgt_free + batch_size;
459 for (key = 1; key < end_key; key++) {
460 assert(!bpf_map_lookup_elem_with_ref_bit(lru_map_fd, key, value));
461 assert(!bpf_map_update_elem(expected_map_fd, &key, value,
462 BPF_NOEXIST));
463 }
464
465 /* Add 1+2*tgt_free to tgt_free*5/2
466 * (+tgt_free/2 keys)
467 */
468 key = 2 * tgt_free + 1;
469 end_key = key + batch_size;
470 for (; key < end_key; key++) {
471 assert(!bpf_map_update_elem(lru_map_fd, &key, value,
472 BPF_NOEXIST));
473 assert(!bpf_map_update_elem(expected_map_fd, &key, value,
474 BPF_NOEXIST));
475 }
476
477 assert(map_equal(lru_map_fd, expected_map_fd));
478
479 close(expected_map_fd);
480 close(lru_map_fd);
481
482 printf("Pass\n");
483}
484
485/* Test deletion */
486static void test_lru_sanity4(int map_type, int map_flags, unsigned int tgt_free)
487{
488 int lru_map_fd, expected_map_fd;
489 unsigned long long key, value[nr_cpus];
490 unsigned long long end_key;
491 int next_cpu = 0;
492
493 printf("%s (map_type:%d map_flags:0x%X): ", __func__, map_type,
494 map_flags);
495
496 assert(sched_next_online(0, &next_cpu) != -1);
497
498 if (map_flags & BPF_F_NO_COMMON_LRU)
499 lru_map_fd = create_map(map_type, map_flags,
500 3 * tgt_free * nr_cpus);
501 else
502 lru_map_fd = create_map(map_type, map_flags, 3 * tgt_free);
503 assert(lru_map_fd != -1);
504
505 expected_map_fd = create_map(BPF_MAP_TYPE_HASH, 0,
506 3 * tgt_free);
507 assert(expected_map_fd != -1);
508
509 value[0] = 1234;
510
511 for (key = 1; key <= 2 * tgt_free; key++)
512 assert(!bpf_map_update_elem(lru_map_fd, &key, value,
513 BPF_NOEXIST));
514
515 key = 1;
516 assert(bpf_map_update_elem(lru_map_fd, &key, value, BPF_NOEXIST));
517
518 for (key = 1; key <= tgt_free; key++) {
519 assert(!bpf_map_lookup_elem_with_ref_bit(lru_map_fd, key, value));
520 assert(!bpf_map_update_elem(expected_map_fd, &key, value,
521 BPF_NOEXIST));
522 }
523
524 for (; key <= 2 * tgt_free; key++) {
525 assert(!bpf_map_delete_elem(lru_map_fd, &key));
526 assert(bpf_map_delete_elem(lru_map_fd, &key));
527 }
528
529 end_key = key + 2 * tgt_free;
530 for (; key < end_key; key++) {
531 assert(!bpf_map_update_elem(lru_map_fd, &key, value,
532 BPF_NOEXIST));
533 assert(!bpf_map_update_elem(expected_map_fd, &key, value,
534 BPF_NOEXIST));
535 }
536
537 assert(map_equal(lru_map_fd, expected_map_fd));
538
539 close(expected_map_fd);
540 close(lru_map_fd);
541
542 printf("Pass\n");
543}
544
545static void do_test_lru_sanity5(unsigned long long last_key, int map_fd)
546{
547 unsigned long long key, value[nr_cpus];
548
549 /* Ensure the last key inserted by previous CPU can be found */
550 assert(!bpf_map_lookup_elem_with_ref_bit(map_fd, last_key, value));
551 value[0] = 1234;
552
553 key = last_key + 1;
554 assert(!bpf_map_update_elem(map_fd, &key, value, BPF_NOEXIST));
555 assert(!bpf_map_lookup_elem_with_ref_bit(map_fd, key, value));
556
557 /* Cannot find the last key because it was removed by LRU */
558 assert(bpf_map_lookup_elem(map_fd, &last_key, value) == -ENOENT);
559}
560
561/* Test map with only one element */
562static void test_lru_sanity5(int map_type, int map_flags)
563{
564 unsigned long long key, value[nr_cpus];
565 int next_cpu = 0;
566 int map_fd;
567
568 if (map_flags & BPF_F_NO_COMMON_LRU)
569 return;
570
571 printf("%s (map_type:%d map_flags:0x%X): ", __func__, map_type,
572 map_flags);
573
574 map_fd = create_map(map_type, map_flags, 1);
575 assert(map_fd != -1);
576
577 value[0] = 1234;
578 key = 0;
579 assert(!bpf_map_update_elem(map_fd, &key, value, BPF_NOEXIST));
580
581 while (sched_next_online(0, &next_cpu) != -1) {
582 pid_t pid;
583
584 pid = fork();
585 if (pid == 0) {
586 do_test_lru_sanity5(key, map_fd);
587 exit(0);
588 } else if (pid == -1) {
589 printf("couldn't spawn process to test key:%llu\n",
590 key);
591 exit(1);
592 } else {
593 int status;
594
595 assert(waitpid(pid, &status, 0) == pid);
596 assert(status == 0);
597 key++;
598 }
599 }
600
601 close(map_fd);
602 /* At least one key should be tested */
603 assert(key > 0);
604
605 printf("Pass\n");
606}
607
608/* Test list rotation for BPF_F_NO_COMMON_LRU map */
609static void test_lru_sanity6(int map_type, int map_flags, int tgt_free)
610{
611 int lru_map_fd, expected_map_fd;
612 unsigned long long key, value[nr_cpus];
613 unsigned int map_size = tgt_free * 2;
614 int next_cpu = 0;
615
616 if (!(map_flags & BPF_F_NO_COMMON_LRU))
617 return;
618
619 printf("%s (map_type:%d map_flags:0x%X): ", __func__, map_type,
620 map_flags);
621
622 assert(sched_next_online(0, &next_cpu) != -1);
623
624 expected_map_fd = create_map(BPF_MAP_TYPE_HASH, 0, map_size);
625 assert(expected_map_fd != -1);
626
627 lru_map_fd = create_map(map_type, map_flags, map_size * nr_cpus);
628 assert(lru_map_fd != -1);
629
630 value[0] = 1234;
631
632 for (key = 1; key <= tgt_free; key++) {
633 assert(!bpf_map_update_elem(lru_map_fd, &key, value,
634 BPF_NOEXIST));
635 assert(!bpf_map_update_elem(expected_map_fd, &key, value,
636 BPF_NOEXIST));
637 }
638
639 for (; key <= tgt_free * 2; key++) {
640 unsigned long long stable_key;
641
642 /* Make ref bit sticky for key: [1, tgt_free] */
643 for (stable_key = 1; stable_key <= tgt_free; stable_key++) {
644 /* Mark the ref bit */
645 assert(!bpf_map_lookup_elem_with_ref_bit(lru_map_fd,
646 stable_key, value));
647 }
648 assert(!bpf_map_update_elem(lru_map_fd, &key, value,
649 BPF_NOEXIST));
650 }
651
652 for (; key <= tgt_free * 3; key++) {
653 assert(!bpf_map_update_elem(lru_map_fd, &key, value,
654 BPF_NOEXIST));
655 assert(!bpf_map_update_elem(expected_map_fd, &key, value,
656 BPF_NOEXIST));
657 }
658
659 assert(map_equal(lru_map_fd, expected_map_fd));
660
661 close(expected_map_fd);
662 close(lru_map_fd);
663
664 printf("Pass\n");
665}
666
667/* Size of the LRU map is 2
668 * Add key=1 (+1 key)
669 * Add key=2 (+1 key)
670 * Lookup Key=1 (datapath)
671 * Lookup Key=2 (syscall)
672 * Add Key=3
673 * => Key=2 will be removed by LRU
674 * Iterate map. Only found key=1 and key=3
675 */
676static void test_lru_sanity7(int map_type, int map_flags)
677{
678 unsigned long long key, value[nr_cpus];
679 int lru_map_fd, expected_map_fd;
680 int next_cpu = 0;
681
682 printf("%s (map_type:%d map_flags:0x%X): ", __func__, map_type,
683 map_flags);
684
685 assert(sched_next_online(0, &next_cpu) != -1);
686
687 if (map_flags & BPF_F_NO_COMMON_LRU)
688 lru_map_fd = create_map(map_type, map_flags, 2 * nr_cpus);
689 else
690 lru_map_fd = create_map(map_type, map_flags, 2);
691 assert(lru_map_fd != -1);
692
693 expected_map_fd = create_map(BPF_MAP_TYPE_HASH, 0, 2);
694 assert(expected_map_fd != -1);
695
696 value[0] = 1234;
697
698 /* insert key=1 element */
699
700 key = 1;
701 assert(!bpf_map_update_elem(lru_map_fd, &key, value, BPF_NOEXIST));
702 assert(!bpf_map_update_elem(expected_map_fd, &key, value,
703 BPF_NOEXIST));
704
705 /* BPF_NOEXIST means: add new element if it doesn't exist */
706 assert(bpf_map_update_elem(lru_map_fd, &key, value, BPF_NOEXIST) == -EEXIST);
707 /* key=1 already exists */
708
709 /* insert key=2 element */
710
711 /* check that key=2 is not found */
712 key = 2;
713 assert(bpf_map_lookup_elem(lru_map_fd, &key, value) == -ENOENT);
714
715 /* BPF_EXIST means: update existing element */
716 assert(bpf_map_update_elem(lru_map_fd, &key, value, BPF_EXIST) == -ENOENT);
717 /* key=2 is not there */
718
719 assert(!bpf_map_update_elem(lru_map_fd, &key, value, BPF_NOEXIST));
720
721 /* insert key=3 element */
722
723 /* check that key=3 is not found */
724 key = 3;
725 assert(bpf_map_lookup_elem(lru_map_fd, &key, value) == -ENOENT);
726
727 /* check that key=1 can be found and mark the ref bit to
728 * stop LRU from removing key=1
729 */
730 key = 1;
731 assert(!bpf_map_lookup_elem_with_ref_bit(lru_map_fd, key, value));
732 assert(value[0] == 1234);
733
734 /* check that key=2 can be found and do _not_ mark ref bit.
735 * this will be evicted on next update.
736 */
737 key = 2;
738 assert(!bpf_map_lookup_elem(lru_map_fd, &key, value));
739 assert(value[0] == 1234);
740
741 key = 3;
742 assert(!bpf_map_update_elem(lru_map_fd, &key, value, BPF_NOEXIST));
743 assert(!bpf_map_update_elem(expected_map_fd, &key, value,
744 BPF_NOEXIST));
745
746 /* key=2 has been removed from the LRU */
747 key = 2;
748 assert(bpf_map_lookup_elem(lru_map_fd, &key, value) == -ENOENT);
749
750 assert(map_equal(lru_map_fd, expected_map_fd));
751
752 close(expected_map_fd);
753 close(lru_map_fd);
754
755 printf("Pass\n");
756}
757
758/* Size of the LRU map is 2
759 * Add key=1 (+1 key)
760 * Add key=2 (+1 key)
761 * Lookup Key=1 (syscall)
762 * Lookup Key=2 (datapath)
763 * Add Key=3
764 * => Key=1 will be removed by LRU
765 * Iterate map. Only found key=2 and key=3
766 */
767static void test_lru_sanity8(int map_type, int map_flags)
768{
769 unsigned long long key, value[nr_cpus];
770 int lru_map_fd, expected_map_fd;
771 int next_cpu = 0;
772
773 printf("%s (map_type:%d map_flags:0x%X): ", __func__, map_type,
774 map_flags);
775
776 assert(sched_next_online(0, &next_cpu) != -1);
777
778 if (map_flags & BPF_F_NO_COMMON_LRU)
779 lru_map_fd = create_map(map_type, map_flags, 2 * nr_cpus);
780 else
781 lru_map_fd = create_map(map_type, map_flags, 2);
782 assert(lru_map_fd != -1);
783
784 expected_map_fd = create_map(BPF_MAP_TYPE_HASH, 0, 2);
785 assert(expected_map_fd != -1);
786
787 value[0] = 1234;
788
789 /* insert key=1 element */
790
791 key = 1;
792 assert(!bpf_map_update_elem(lru_map_fd, &key, value, BPF_NOEXIST));
793
794 /* BPF_NOEXIST means: add new element if it doesn't exist */
795 assert(bpf_map_update_elem(lru_map_fd, &key, value, BPF_NOEXIST) == -EEXIST);
796 /* key=1 already exists */
797
798 /* insert key=2 element */
799
800 /* check that key=2 is not found */
801 key = 2;
802 assert(bpf_map_lookup_elem(lru_map_fd, &key, value) == -ENOENT);
803
804 /* BPF_EXIST means: update existing element */
805 assert(bpf_map_update_elem(lru_map_fd, &key, value, BPF_EXIST) == -ENOENT);
806 /* key=2 is not there */
807
808 assert(!bpf_map_update_elem(lru_map_fd, &key, value, BPF_NOEXIST));
809 assert(!bpf_map_update_elem(expected_map_fd, &key, value,
810 BPF_NOEXIST));
811
812 /* insert key=3 element */
813
814 /* check that key=3 is not found */
815 key = 3;
816 assert(bpf_map_lookup_elem(lru_map_fd, &key, value) == -ENOENT);
817
818 /* check that key=1 can be found and do _not_ mark ref bit.
819 * this will be evicted on next update.
820 */
821 key = 1;
822 assert(!bpf_map_lookup_elem(lru_map_fd, &key, value));
823 assert(value[0] == 1234);
824
825 /* check that key=2 can be found and mark the ref bit to
826 * stop LRU from removing key=2
827 */
828 key = 2;
829 assert(!bpf_map_lookup_elem_with_ref_bit(lru_map_fd, key, value));
830 assert(value[0] == 1234);
831
832 key = 3;
833 assert(!bpf_map_update_elem(lru_map_fd, &key, value, BPF_NOEXIST));
834 assert(!bpf_map_update_elem(expected_map_fd, &key, value,
835 BPF_NOEXIST));
836
837 /* key=1 has been removed from the LRU */
838 key = 1;
839 assert(bpf_map_lookup_elem(lru_map_fd, &key, value) == -ENOENT);
840
841 assert(map_equal(lru_map_fd, expected_map_fd));
842
843 close(expected_map_fd);
844 close(lru_map_fd);
845
846 printf("Pass\n");
847}
848
849int main(int argc, char **argv)
850{
851 int map_types[] = {BPF_MAP_TYPE_LRU_HASH,
852 BPF_MAP_TYPE_LRU_PERCPU_HASH};
853 int map_flags[] = {0, BPF_F_NO_COMMON_LRU};
854 int t, f;
855
856 setbuf(stdout, NULL);
857
858 nr_cpus = bpf_num_possible_cpus();
859 assert(nr_cpus != -1);
860 printf("nr_cpus:%d\n\n", nr_cpus);
861
862 /* Use libbpf 1.0 API mode */
863 libbpf_set_strict_mode(LIBBPF_STRICT_ALL);
864
865 for (f = 0; f < ARRAY_SIZE(map_flags); f++) {
866 unsigned int tgt_free = (map_flags[f] & BPF_F_NO_COMMON_LRU) ?
867 PERCPU_FREE_TARGET : LOCAL_FREE_TARGET;
868
869 for (t = 0; t < ARRAY_SIZE(map_types); t++) {
870 test_lru_sanity0(map_types[t], map_flags[f]);
871 test_lru_sanity1(map_types[t], map_flags[f], tgt_free);
872 test_lru_sanity2(map_types[t], map_flags[f], tgt_free);
873 test_lru_sanity3(map_types[t], map_flags[f], tgt_free);
874 test_lru_sanity4(map_types[t], map_flags[f], tgt_free);
875 test_lru_sanity5(map_types[t], map_flags[f]);
876 test_lru_sanity6(map_types[t], map_flags[f], tgt_free);
877 test_lru_sanity7(map_types[t], map_flags[f]);
878 test_lru_sanity8(map_types[t], map_flags[f]);
879
880 printf("\n");
881 }
882 }
883
884 return 0;
885}
1/*
2 * Copyright (c) 2016 Facebook
3 *
4 * This program is free software; you can redistribute it and/or
5 * modify it under the terms of version 2 of the GNU General Public
6 * License as published by the Free Software Foundation.
7 */
8#define _GNU_SOURCE
9#include <stdio.h>
10#include <unistd.h>
11#include <errno.h>
12#include <string.h>
13#include <assert.h>
14#include <sched.h>
15#include <stdlib.h>
16#include <time.h>
17
18#include <sys/wait.h>
19
20#include <bpf/bpf.h>
21
22#include "bpf_util.h"
23#include "bpf_rlimit.h"
24
25#define LOCAL_FREE_TARGET (128)
26#define PERCPU_FREE_TARGET (4)
27
28static int nr_cpus;
29
30static int create_map(int map_type, int map_flags, unsigned int size)
31{
32 int map_fd;
33
34 map_fd = bpf_create_map(map_type, sizeof(unsigned long long),
35 sizeof(unsigned long long), size, map_flags);
36
37 if (map_fd == -1)
38 perror("bpf_create_map");
39
40 return map_fd;
41}
42
43static int map_subset(int map0, int map1)
44{
45 unsigned long long next_key = 0;
46 unsigned long long value0[nr_cpus], value1[nr_cpus];
47 int ret;
48
49 while (!bpf_map_get_next_key(map1, &next_key, &next_key)) {
50 assert(!bpf_map_lookup_elem(map1, &next_key, value1));
51 ret = bpf_map_lookup_elem(map0, &next_key, value0);
52 if (ret) {
53 printf("key:%llu not found from map. %s(%d)\n",
54 next_key, strerror(errno), errno);
55 return 0;
56 }
57 if (value0[0] != value1[0]) {
58 printf("key:%llu value0:%llu != value1:%llu\n",
59 next_key, value0[0], value1[0]);
60 return 0;
61 }
62 }
63 return 1;
64}
65
66static int map_equal(int lru_map, int expected)
67{
68 return map_subset(lru_map, expected) && map_subset(expected, lru_map);
69}
70
71static int sched_next_online(int pid, int *next_to_try)
72{
73 cpu_set_t cpuset;
74 int next = *next_to_try;
75 int ret = -1;
76
77 while (next < nr_cpus) {
78 CPU_ZERO(&cpuset);
79 CPU_SET(next++, &cpuset);
80 if (!sched_setaffinity(pid, sizeof(cpuset), &cpuset)) {
81 ret = 0;
82 break;
83 }
84 }
85
86 *next_to_try = next;
87 return ret;
88}
89
90/* Size of the LRU amp is 2
91 * Add key=1 (+1 key)
92 * Add key=2 (+1 key)
93 * Lookup Key=1
94 * Add Key=3
95 * => Key=2 will be removed by LRU
96 * Iterate map. Only found key=1 and key=3
97 */
98static void test_lru_sanity0(int map_type, int map_flags)
99{
100 unsigned long long key, value[nr_cpus];
101 int lru_map_fd, expected_map_fd;
102 int next_cpu = 0;
103
104 printf("%s (map_type:%d map_flags:0x%X): ", __func__, map_type,
105 map_flags);
106
107 assert(sched_next_online(0, &next_cpu) != -1);
108
109 if (map_flags & BPF_F_NO_COMMON_LRU)
110 lru_map_fd = create_map(map_type, map_flags, 2 * nr_cpus);
111 else
112 lru_map_fd = create_map(map_type, map_flags, 2);
113 assert(lru_map_fd != -1);
114
115 expected_map_fd = create_map(BPF_MAP_TYPE_HASH, 0, 2);
116 assert(expected_map_fd != -1);
117
118 value[0] = 1234;
119
120 /* insert key=1 element */
121
122 key = 1;
123 assert(!bpf_map_update_elem(lru_map_fd, &key, value, BPF_NOEXIST));
124 assert(!bpf_map_update_elem(expected_map_fd, &key, value,
125 BPF_NOEXIST));
126
127 /* BPF_NOEXIST means: add new element if it doesn't exist */
128 assert(bpf_map_update_elem(lru_map_fd, &key, value, BPF_NOEXIST) == -1
129 /* key=1 already exists */
130 && errno == EEXIST);
131
132 assert(bpf_map_update_elem(lru_map_fd, &key, value, -1) == -1 &&
133 errno == EINVAL);
134
135 /* insert key=2 element */
136
137 /* check that key=2 is not found */
138 key = 2;
139 assert(bpf_map_lookup_elem(lru_map_fd, &key, value) == -1 &&
140 errno == ENOENT);
141
142 /* BPF_EXIST means: update existing element */
143 assert(bpf_map_update_elem(lru_map_fd, &key, value, BPF_EXIST) == -1 &&
144 /* key=2 is not there */
145 errno == ENOENT);
146
147 assert(!bpf_map_update_elem(lru_map_fd, &key, value, BPF_NOEXIST));
148
149 /* insert key=3 element */
150
151 /* check that key=3 is not found */
152 key = 3;
153 assert(bpf_map_lookup_elem(lru_map_fd, &key, value) == -1 &&
154 errno == ENOENT);
155
156 /* check that key=1 can be found and mark the ref bit to
157 * stop LRU from removing key=1
158 */
159 key = 1;
160 assert(!bpf_map_lookup_elem(lru_map_fd, &key, value));
161 assert(value[0] == 1234);
162
163 key = 3;
164 assert(!bpf_map_update_elem(lru_map_fd, &key, value, BPF_NOEXIST));
165 assert(!bpf_map_update_elem(expected_map_fd, &key, value,
166 BPF_NOEXIST));
167
168 /* key=2 has been removed from the LRU */
169 key = 2;
170 assert(bpf_map_lookup_elem(lru_map_fd, &key, value) == -1);
171
172 assert(map_equal(lru_map_fd, expected_map_fd));
173
174 close(expected_map_fd);
175 close(lru_map_fd);
176
177 printf("Pass\n");
178}
179
180/* Size of the LRU map is 1.5*tgt_free
181 * Insert 1 to tgt_free (+tgt_free keys)
182 * Lookup 1 to tgt_free/2
183 * Insert 1+tgt_free to 2*tgt_free (+tgt_free keys)
184 * => 1+tgt_free/2 to LOCALFREE_TARGET will be removed by LRU
185 */
186static void test_lru_sanity1(int map_type, int map_flags, unsigned int tgt_free)
187{
188 unsigned long long key, end_key, value[nr_cpus];
189 int lru_map_fd, expected_map_fd;
190 unsigned int batch_size;
191 unsigned int map_size;
192 int next_cpu = 0;
193
194 if (map_flags & BPF_F_NO_COMMON_LRU)
195 /* This test is only applicable to common LRU list */
196 return;
197
198 printf("%s (map_type:%d map_flags:0x%X): ", __func__, map_type,
199 map_flags);
200
201 assert(sched_next_online(0, &next_cpu) != -1);
202
203 batch_size = tgt_free / 2;
204 assert(batch_size * 2 == tgt_free);
205
206 map_size = tgt_free + batch_size;
207 lru_map_fd = create_map(map_type, map_flags, map_size);
208 assert(lru_map_fd != -1);
209
210 expected_map_fd = create_map(BPF_MAP_TYPE_HASH, 0, map_size);
211 assert(expected_map_fd != -1);
212
213 value[0] = 1234;
214
215 /* Insert 1 to tgt_free (+tgt_free keys) */
216 end_key = 1 + tgt_free;
217 for (key = 1; key < end_key; key++)
218 assert(!bpf_map_update_elem(lru_map_fd, &key, value,
219 BPF_NOEXIST));
220
221 /* Lookup 1 to tgt_free/2 */
222 end_key = 1 + batch_size;
223 for (key = 1; key < end_key; key++) {
224 assert(!bpf_map_lookup_elem(lru_map_fd, &key, value));
225 assert(!bpf_map_update_elem(expected_map_fd, &key, value,
226 BPF_NOEXIST));
227 }
228
229 /* Insert 1+tgt_free to 2*tgt_free
230 * => 1+tgt_free/2 to LOCALFREE_TARGET will be
231 * removed by LRU
232 */
233 key = 1 + tgt_free;
234 end_key = key + tgt_free;
235 for (; key < end_key; key++) {
236 assert(!bpf_map_update_elem(lru_map_fd, &key, value,
237 BPF_NOEXIST));
238 assert(!bpf_map_update_elem(expected_map_fd, &key, value,
239 BPF_NOEXIST));
240 }
241
242 assert(map_equal(lru_map_fd, expected_map_fd));
243
244 close(expected_map_fd);
245 close(lru_map_fd);
246
247 printf("Pass\n");
248}
249
250/* Size of the LRU map 1.5 * tgt_free
251 * Insert 1 to tgt_free (+tgt_free keys)
252 * Update 1 to tgt_free/2
253 * => The original 1 to tgt_free/2 will be removed due to
254 * the LRU shrink process
255 * Re-insert 1 to tgt_free/2 again and do a lookup immeidately
256 * Insert 1+tgt_free to tgt_free*3/2
257 * Insert 1+tgt_free*3/2 to tgt_free*5/2
258 * => Key 1+tgt_free to tgt_free*3/2
259 * will be removed from LRU because it has never
260 * been lookup and ref bit is not set
261 */
262static void test_lru_sanity2(int map_type, int map_flags, unsigned int tgt_free)
263{
264 unsigned long long key, value[nr_cpus];
265 unsigned long long end_key;
266 int lru_map_fd, expected_map_fd;
267 unsigned int batch_size;
268 unsigned int map_size;
269 int next_cpu = 0;
270
271 if (map_flags & BPF_F_NO_COMMON_LRU)
272 /* This test is only applicable to common LRU list */
273 return;
274
275 printf("%s (map_type:%d map_flags:0x%X): ", __func__, map_type,
276 map_flags);
277
278 assert(sched_next_online(0, &next_cpu) != -1);
279
280 batch_size = tgt_free / 2;
281 assert(batch_size * 2 == tgt_free);
282
283 map_size = tgt_free + batch_size;
284 lru_map_fd = create_map(map_type, map_flags, map_size);
285 assert(lru_map_fd != -1);
286
287 expected_map_fd = create_map(BPF_MAP_TYPE_HASH, 0, map_size);
288 assert(expected_map_fd != -1);
289
290 value[0] = 1234;
291
292 /* Insert 1 to tgt_free (+tgt_free keys) */
293 end_key = 1 + tgt_free;
294 for (key = 1; key < end_key; key++)
295 assert(!bpf_map_update_elem(lru_map_fd, &key, value,
296 BPF_NOEXIST));
297
298 /* Any bpf_map_update_elem will require to acquire a new node
299 * from LRU first.
300 *
301 * The local list is running out of free nodes.
302 * It gets from the global LRU list which tries to
303 * shrink the inactive list to get tgt_free
304 * number of free nodes.
305 *
306 * Hence, the oldest key 1 to tgt_free/2
307 * are removed from the LRU list.
308 */
309 key = 1;
310 if (map_type == BPF_MAP_TYPE_LRU_PERCPU_HASH) {
311 assert(!bpf_map_update_elem(lru_map_fd, &key, value,
312 BPF_NOEXIST));
313 assert(!bpf_map_delete_elem(lru_map_fd, &key));
314 } else {
315 assert(bpf_map_update_elem(lru_map_fd, &key, value,
316 BPF_EXIST));
317 }
318
319 /* Re-insert 1 to tgt_free/2 again and do a lookup
320 * immeidately.
321 */
322 end_key = 1 + batch_size;
323 value[0] = 4321;
324 for (key = 1; key < end_key; key++) {
325 assert(bpf_map_lookup_elem(lru_map_fd, &key, value));
326 assert(!bpf_map_update_elem(lru_map_fd, &key, value,
327 BPF_NOEXIST));
328 assert(!bpf_map_lookup_elem(lru_map_fd, &key, value));
329 assert(value[0] == 4321);
330 assert(!bpf_map_update_elem(expected_map_fd, &key, value,
331 BPF_NOEXIST));
332 }
333
334 value[0] = 1234;
335
336 /* Insert 1+tgt_free to tgt_free*3/2 */
337 end_key = 1 + tgt_free + batch_size;
338 for (key = 1 + tgt_free; key < end_key; key++)
339 /* These newly added but not referenced keys will be
340 * gone during the next LRU shrink.
341 */
342 assert(!bpf_map_update_elem(lru_map_fd, &key, value,
343 BPF_NOEXIST));
344
345 /* Insert 1+tgt_free*3/2 to tgt_free*5/2 */
346 end_key = key + tgt_free;
347 for (; key < end_key; key++) {
348 assert(!bpf_map_update_elem(lru_map_fd, &key, value,
349 BPF_NOEXIST));
350 assert(!bpf_map_update_elem(expected_map_fd, &key, value,
351 BPF_NOEXIST));
352 }
353
354 assert(map_equal(lru_map_fd, expected_map_fd));
355
356 close(expected_map_fd);
357 close(lru_map_fd);
358
359 printf("Pass\n");
360}
361
362/* Size of the LRU map is 2*tgt_free
363 * It is to test the active/inactive list rotation
364 * Insert 1 to 2*tgt_free (+2*tgt_free keys)
365 * Lookup key 1 to tgt_free*3/2
366 * Add 1+2*tgt_free to tgt_free*5/2 (+tgt_free/2 keys)
367 * => key 1+tgt_free*3/2 to 2*tgt_free are removed from LRU
368 */
369static void test_lru_sanity3(int map_type, int map_flags, unsigned int tgt_free)
370{
371 unsigned long long key, end_key, value[nr_cpus];
372 int lru_map_fd, expected_map_fd;
373 unsigned int batch_size;
374 unsigned int map_size;
375 int next_cpu = 0;
376
377 if (map_flags & BPF_F_NO_COMMON_LRU)
378 /* This test is only applicable to common LRU list */
379 return;
380
381 printf("%s (map_type:%d map_flags:0x%X): ", __func__, map_type,
382 map_flags);
383
384 assert(sched_next_online(0, &next_cpu) != -1);
385
386 batch_size = tgt_free / 2;
387 assert(batch_size * 2 == tgt_free);
388
389 map_size = tgt_free * 2;
390 lru_map_fd = create_map(map_type, map_flags, map_size);
391 assert(lru_map_fd != -1);
392
393 expected_map_fd = create_map(BPF_MAP_TYPE_HASH, 0, map_size);
394 assert(expected_map_fd != -1);
395
396 value[0] = 1234;
397
398 /* Insert 1 to 2*tgt_free (+2*tgt_free keys) */
399 end_key = 1 + (2 * tgt_free);
400 for (key = 1; key < end_key; key++)
401 assert(!bpf_map_update_elem(lru_map_fd, &key, value,
402 BPF_NOEXIST));
403
404 /* Lookup key 1 to tgt_free*3/2 */
405 end_key = tgt_free + batch_size;
406 for (key = 1; key < end_key; key++) {
407 assert(!bpf_map_lookup_elem(lru_map_fd, &key, value));
408 assert(!bpf_map_update_elem(expected_map_fd, &key, value,
409 BPF_NOEXIST));
410 }
411
412 /* Add 1+2*tgt_free to tgt_free*5/2
413 * (+tgt_free/2 keys)
414 */
415 key = 2 * tgt_free + 1;
416 end_key = key + batch_size;
417 for (; key < end_key; key++) {
418 assert(!bpf_map_update_elem(lru_map_fd, &key, value,
419 BPF_NOEXIST));
420 assert(!bpf_map_update_elem(expected_map_fd, &key, value,
421 BPF_NOEXIST));
422 }
423
424 assert(map_equal(lru_map_fd, expected_map_fd));
425
426 close(expected_map_fd);
427 close(lru_map_fd);
428
429 printf("Pass\n");
430}
431
432/* Test deletion */
433static void test_lru_sanity4(int map_type, int map_flags, unsigned int tgt_free)
434{
435 int lru_map_fd, expected_map_fd;
436 unsigned long long key, value[nr_cpus];
437 unsigned long long end_key;
438 int next_cpu = 0;
439
440 printf("%s (map_type:%d map_flags:0x%X): ", __func__, map_type,
441 map_flags);
442
443 assert(sched_next_online(0, &next_cpu) != -1);
444
445 if (map_flags & BPF_F_NO_COMMON_LRU)
446 lru_map_fd = create_map(map_type, map_flags,
447 3 * tgt_free * nr_cpus);
448 else
449 lru_map_fd = create_map(map_type, map_flags, 3 * tgt_free);
450 assert(lru_map_fd != -1);
451
452 expected_map_fd = create_map(BPF_MAP_TYPE_HASH, 0,
453 3 * tgt_free);
454 assert(expected_map_fd != -1);
455
456 value[0] = 1234;
457
458 for (key = 1; key <= 2 * tgt_free; key++)
459 assert(!bpf_map_update_elem(lru_map_fd, &key, value,
460 BPF_NOEXIST));
461
462 key = 1;
463 assert(bpf_map_update_elem(lru_map_fd, &key, value, BPF_NOEXIST));
464
465 for (key = 1; key <= tgt_free; key++) {
466 assert(!bpf_map_lookup_elem(lru_map_fd, &key, value));
467 assert(!bpf_map_update_elem(expected_map_fd, &key, value,
468 BPF_NOEXIST));
469 }
470
471 for (; key <= 2 * tgt_free; key++) {
472 assert(!bpf_map_delete_elem(lru_map_fd, &key));
473 assert(bpf_map_delete_elem(lru_map_fd, &key));
474 }
475
476 end_key = key + 2 * tgt_free;
477 for (; key < end_key; key++) {
478 assert(!bpf_map_update_elem(lru_map_fd, &key, value,
479 BPF_NOEXIST));
480 assert(!bpf_map_update_elem(expected_map_fd, &key, value,
481 BPF_NOEXIST));
482 }
483
484 assert(map_equal(lru_map_fd, expected_map_fd));
485
486 close(expected_map_fd);
487 close(lru_map_fd);
488
489 printf("Pass\n");
490}
491
492static void do_test_lru_sanity5(unsigned long long last_key, int map_fd)
493{
494 unsigned long long key, value[nr_cpus];
495
496 /* Ensure the last key inserted by previous CPU can be found */
497 assert(!bpf_map_lookup_elem(map_fd, &last_key, value));
498
499 value[0] = 1234;
500
501 key = last_key + 1;
502 assert(!bpf_map_update_elem(map_fd, &key, value, BPF_NOEXIST));
503 assert(!bpf_map_lookup_elem(map_fd, &key, value));
504
505 /* Cannot find the last key because it was removed by LRU */
506 assert(bpf_map_lookup_elem(map_fd, &last_key, value));
507}
508
509/* Test map with only one element */
510static void test_lru_sanity5(int map_type, int map_flags)
511{
512 unsigned long long key, value[nr_cpus];
513 int next_cpu = 0;
514 int map_fd;
515
516 if (map_flags & BPF_F_NO_COMMON_LRU)
517 return;
518
519 printf("%s (map_type:%d map_flags:0x%X): ", __func__, map_type,
520 map_flags);
521
522 map_fd = create_map(map_type, map_flags, 1);
523 assert(map_fd != -1);
524
525 value[0] = 1234;
526 key = 0;
527 assert(!bpf_map_update_elem(map_fd, &key, value, BPF_NOEXIST));
528
529 while (sched_next_online(0, &next_cpu) != -1) {
530 pid_t pid;
531
532 pid = fork();
533 if (pid == 0) {
534 do_test_lru_sanity5(key, map_fd);
535 exit(0);
536 } else if (pid == -1) {
537 printf("couldn't spawn process to test key:%llu\n",
538 key);
539 exit(1);
540 } else {
541 int status;
542
543 assert(waitpid(pid, &status, 0) == pid);
544 assert(status == 0);
545 key++;
546 }
547 }
548
549 close(map_fd);
550 /* At least one key should be tested */
551 assert(key > 0);
552
553 printf("Pass\n");
554}
555
556/* Test list rotation for BPF_F_NO_COMMON_LRU map */
557static void test_lru_sanity6(int map_type, int map_flags, int tgt_free)
558{
559 int lru_map_fd, expected_map_fd;
560 unsigned long long key, value[nr_cpus];
561 unsigned int map_size = tgt_free * 2;
562 int next_cpu = 0;
563
564 if (!(map_flags & BPF_F_NO_COMMON_LRU))
565 return;
566
567 printf("%s (map_type:%d map_flags:0x%X): ", __func__, map_type,
568 map_flags);
569
570 assert(sched_next_online(0, &next_cpu) != -1);
571
572 expected_map_fd = create_map(BPF_MAP_TYPE_HASH, 0, map_size);
573 assert(expected_map_fd != -1);
574
575 lru_map_fd = create_map(map_type, map_flags, map_size * nr_cpus);
576 assert(lru_map_fd != -1);
577
578 value[0] = 1234;
579
580 for (key = 1; key <= tgt_free; key++) {
581 assert(!bpf_map_update_elem(lru_map_fd, &key, value,
582 BPF_NOEXIST));
583 assert(!bpf_map_update_elem(expected_map_fd, &key, value,
584 BPF_NOEXIST));
585 }
586
587 for (; key <= tgt_free * 2; key++) {
588 unsigned long long stable_key;
589
590 /* Make ref bit sticky for key: [1, tgt_free] */
591 for (stable_key = 1; stable_key <= tgt_free; stable_key++) {
592 /* Mark the ref bit */
593 assert(!bpf_map_lookup_elem(lru_map_fd, &stable_key,
594 value));
595 }
596 assert(!bpf_map_update_elem(lru_map_fd, &key, value,
597 BPF_NOEXIST));
598 }
599
600 for (; key <= tgt_free * 3; key++) {
601 assert(!bpf_map_update_elem(lru_map_fd, &key, value,
602 BPF_NOEXIST));
603 assert(!bpf_map_update_elem(expected_map_fd, &key, value,
604 BPF_NOEXIST));
605 }
606
607 assert(map_equal(lru_map_fd, expected_map_fd));
608
609 close(expected_map_fd);
610 close(lru_map_fd);
611
612 printf("Pass\n");
613}
614
615int main(int argc, char **argv)
616{
617 int map_types[] = {BPF_MAP_TYPE_LRU_HASH,
618 BPF_MAP_TYPE_LRU_PERCPU_HASH};
619 int map_flags[] = {0, BPF_F_NO_COMMON_LRU};
620 int t, f;
621
622 setbuf(stdout, NULL);
623
624 nr_cpus = bpf_num_possible_cpus();
625 assert(nr_cpus != -1);
626 printf("nr_cpus:%d\n\n", nr_cpus);
627
628 for (f = 0; f < sizeof(map_flags) / sizeof(*map_flags); f++) {
629 unsigned int tgt_free = (map_flags[f] & BPF_F_NO_COMMON_LRU) ?
630 PERCPU_FREE_TARGET : LOCAL_FREE_TARGET;
631
632 for (t = 0; t < sizeof(map_types) / sizeof(*map_types); t++) {
633 test_lru_sanity0(map_types[t], map_flags[f]);
634 test_lru_sanity1(map_types[t], map_flags[f], tgt_free);
635 test_lru_sanity2(map_types[t], map_flags[f], tgt_free);
636 test_lru_sanity3(map_types[t], map_flags[f], tgt_free);
637 test_lru_sanity4(map_types[t], map_flags[f], tgt_free);
638 test_lru_sanity5(map_types[t], map_flags[f]);
639 test_lru_sanity6(map_types[t], map_flags[f], tgt_free);
640
641 printf("\n");
642 }
643 }
644
645 return 0;
646}