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(map0: lru_map, map1: expected) && map_subset(map0: expected, map1: 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(pid: 0, next_to_try: &next_cpu) != -1); |
158 | |
159 | if (map_flags & BPF_F_NO_COMMON_LRU) |
160 | lru_map_fd = create_map(map_type, map_flags, size: 2 * nr_cpus); |
161 | else |
162 | lru_map_fd = create_map(map_type, map_flags, size: 2); |
163 | assert(lru_map_fd != -1); |
164 | |
165 | expected_map_fd = create_map(map_type: BPF_MAP_TYPE_HASH, map_flags: 0, size: 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(fd: 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: lru_map_fd, expected: 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(pid: 0, next_to_try: &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, size: map_size); |
261 | assert(lru_map_fd != -1); |
262 | |
263 | expected_map_fd = create_map(map_type: BPF_MAP_TYPE_HASH, map_flags: 0, size: 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(fd: 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: lru_map_fd, expected: 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(pid: 0, next_to_try: &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, size: map_size); |
338 | assert(lru_map_fd != -1); |
339 | |
340 | expected_map_fd = create_map(map_type: BPF_MAP_TYPE_HASH, map_flags: 0, size: 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(fd: 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: lru_map_fd, expected: 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(pid: 0, next_to_try: &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, size: map_size); |
444 | assert(lru_map_fd != -1); |
445 | |
446 | expected_map_fd = create_map(map_type: BPF_MAP_TYPE_HASH, map_flags: 0, size: 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(fd: 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: lru_map_fd, expected: 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(pid: 0, next_to_try: &next_cpu) != -1); |
497 | |
498 | if (map_flags & BPF_F_NO_COMMON_LRU) |
499 | lru_map_fd = create_map(map_type, map_flags, |
500 | size: 3 * tgt_free * nr_cpus); |
501 | else |
502 | lru_map_fd = create_map(map_type, map_flags, size: 3 * tgt_free); |
503 | assert(lru_map_fd != -1); |
504 | |
505 | expected_map_fd = create_map(map_type: BPF_MAP_TYPE_HASH, map_flags: 0, |
506 | size: 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(fd: 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: lru_map_fd, expected: 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(fd: map_fd, key: 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(fd: 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, size: 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(pid: 0, next_to_try: &next_cpu) != -1) { |
582 | pid_t pid; |
583 | |
584 | pid = fork(); |
585 | if (pid == 0) { |
586 | do_test_lru_sanity5(last_key: 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(pid: 0, next_to_try: &next_cpu) != -1); |
623 | |
624 | expected_map_fd = create_map(map_type: BPF_MAP_TYPE_HASH, map_flags: 0, size: map_size); |
625 | assert(expected_map_fd != -1); |
626 | |
627 | lru_map_fd = create_map(map_type, map_flags, size: 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(fd: lru_map_fd, |
646 | key: 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: lru_map_fd, expected: 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(pid: 0, next_to_try: &next_cpu) != -1); |
686 | |
687 | if (map_flags & BPF_F_NO_COMMON_LRU) |
688 | lru_map_fd = create_map(map_type, map_flags, size: 2 * nr_cpus); |
689 | else |
690 | lru_map_fd = create_map(map_type, map_flags, size: 2); |
691 | assert(lru_map_fd != -1); |
692 | |
693 | expected_map_fd = create_map(map_type: BPF_MAP_TYPE_HASH, map_flags: 0, size: 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(fd: 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: lru_map_fd, expected: 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(pid: 0, next_to_try: &next_cpu) != -1); |
777 | |
778 | if (map_flags & BPF_F_NO_COMMON_LRU) |
779 | lru_map_fd = create_map(map_type, map_flags, size: 2 * nr_cpus); |
780 | else |
781 | lru_map_fd = create_map(map_type, map_flags, size: 2); |
782 | assert(lru_map_fd != -1); |
783 | |
784 | expected_map_fd = create_map(map_type: BPF_MAP_TYPE_HASH, map_flags: 0, size: 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(fd: 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: lru_map_fd, expected: 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_type: map_types[t], map_flags: map_flags[f]); |
871 | test_lru_sanity1(map_type: map_types[t], map_flags: map_flags[f], tgt_free); |
872 | test_lru_sanity2(map_type: map_types[t], map_flags: map_flags[f], tgt_free); |
873 | test_lru_sanity3(map_type: map_types[t], map_flags: map_flags[f], tgt_free); |
874 | test_lru_sanity4(map_type: map_types[t], map_flags: map_flags[f], tgt_free); |
875 | test_lru_sanity5(map_type: map_types[t], map_flags: map_flags[f]); |
876 | test_lru_sanity6(map_type: map_types[t], map_flags: map_flags[f], tgt_free); |
877 | test_lru_sanity7(map_type: map_types[t], map_flags: map_flags[f]); |
878 | test_lru_sanity8(map_type: map_types[t], map_flags: map_flags[f]); |
879 | |
880 | printf("\n" ); |
881 | } |
882 | } |
883 | |
884 | return 0; |
885 | } |
886 | |