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