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