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 
26 static int nr_cpus;
27 
28 static 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 
42 static 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 
93 static 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 
116 static int map_equal(int lru_map, int expected)
117 {
118 	return map_subset(lru_map, expected) && map_subset(expected, lru_map);
119 }
120 
121 static 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  */
148 static 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  */
239 static 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  */
315 static 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  */
422 static 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 */
486 static 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 
545 static 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 */
562 static 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 */
609 static 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  */
676 static 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  */
767 static 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 
849 int 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 }
886