1 // SPDX-License-Identifier: GPL-2.0-only
2 /*
3 * Copyright (c) 2016 Facebook
4 */
5 #define _GNU_SOURCE
6 #include <linux/types.h>
7 #include <stdio.h>
8 #include <unistd.h>
9 #include <linux/bpf.h>
10 #include <errno.h>
11 #include <string.h>
12 #include <assert.h>
13 #include <sched.h>
14 #include <sys/wait.h>
15 #include <sys/stat.h>
16 #include <fcntl.h>
17 #include <stdlib.h>
18 #include <time.h>
19
20 #include <bpf/bpf.h>
21 #include "bpf_util.h"
22
23 #define min(a, b) ((a) < (b) ? (a) : (b))
24 #ifndef offsetof
25 # define offsetof(TYPE, MEMBER) ((size_t)&((TYPE *)0)->MEMBER)
26 #endif
27 #define container_of(ptr, type, member) ({ \
28 const typeof( ((type *)0)->member ) *__mptr = (ptr); \
29 (type *)( (char *)__mptr - offsetof(type,member) );})
30
31 static int nr_cpus;
32 static unsigned long long *dist_keys;
33 static unsigned int dist_key_counts;
34
35 struct list_head {
36 struct list_head *next, *prev;
37 };
38
INIT_LIST_HEAD(struct list_head * list)39 static inline void INIT_LIST_HEAD(struct list_head *list)
40 {
41 list->next = list;
42 list->prev = list;
43 }
44
list_empty(const struct list_head * head)45 static inline int list_empty(const struct list_head *head)
46 {
47 return head->next == head;
48 }
49
__list_add(struct list_head * new,struct list_head * prev,struct list_head * next)50 static inline void __list_add(struct list_head *new,
51 struct list_head *prev,
52 struct list_head *next)
53 {
54 next->prev = new;
55 new->next = next;
56 new->prev = prev;
57 prev->next = new;
58 }
59
list_add(struct list_head * new,struct list_head * head)60 static inline void list_add(struct list_head *new, struct list_head *head)
61 {
62 __list_add(new, head, head->next);
63 }
64
__list_del(struct list_head * prev,struct list_head * next)65 static inline void __list_del(struct list_head *prev, struct list_head *next)
66 {
67 next->prev = prev;
68 prev->next = next;
69 }
70
__list_del_entry(struct list_head * entry)71 static inline void __list_del_entry(struct list_head *entry)
72 {
73 __list_del(entry->prev, entry->next);
74 }
75
list_move(struct list_head * list,struct list_head * head)76 static inline void list_move(struct list_head *list, struct list_head *head)
77 {
78 __list_del_entry(list);
79 list_add(list, head);
80 }
81
82 #define list_entry(ptr, type, member) \
83 container_of(ptr, type, member)
84
85 #define list_last_entry(ptr, type, member) \
86 list_entry((ptr)->prev, type, member)
87
88 struct pfect_lru_node {
89 struct list_head list;
90 unsigned long long key;
91 };
92
93 struct pfect_lru {
94 struct list_head list;
95 struct pfect_lru_node *free_nodes;
96 unsigned int cur_size;
97 unsigned int lru_size;
98 unsigned int nr_unique;
99 unsigned int nr_misses;
100 unsigned int total;
101 int map_fd;
102 };
103
pfect_lru_init(struct pfect_lru * lru,unsigned int lru_size,unsigned int nr_possible_elems)104 static void pfect_lru_init(struct pfect_lru *lru, unsigned int lru_size,
105 unsigned int nr_possible_elems)
106 {
107 lru->map_fd = bpf_map_create(BPF_MAP_TYPE_HASH, NULL,
108 sizeof(unsigned long long),
109 sizeof(struct pfect_lru_node *),
110 nr_possible_elems, NULL);
111 assert(lru->map_fd != -1);
112
113 lru->free_nodes = malloc(lru_size * sizeof(struct pfect_lru_node));
114 assert(lru->free_nodes);
115
116 INIT_LIST_HEAD(&lru->list);
117 lru->cur_size = 0;
118 lru->lru_size = lru_size;
119 lru->nr_unique = lru->nr_misses = lru->total = 0;
120 }
121
pfect_lru_destroy(struct pfect_lru * lru)122 static void pfect_lru_destroy(struct pfect_lru *lru)
123 {
124 close(lru->map_fd);
125 free(lru->free_nodes);
126 }
127
pfect_lru_lookup_or_insert(struct pfect_lru * lru,unsigned long long key)128 static int pfect_lru_lookup_or_insert(struct pfect_lru *lru,
129 unsigned long long key)
130 {
131 struct pfect_lru_node *node = NULL;
132 int seen = 0;
133
134 lru->total++;
135 if (!bpf_map_lookup_elem(lru->map_fd, &key, &node)) {
136 if (node) {
137 list_move(&node->list, &lru->list);
138 return 1;
139 }
140 seen = 1;
141 }
142
143 if (lru->cur_size < lru->lru_size) {
144 node = &lru->free_nodes[lru->cur_size++];
145 INIT_LIST_HEAD(&node->list);
146 } else {
147 struct pfect_lru_node *null_node = NULL;
148
149 node = list_last_entry(&lru->list,
150 struct pfect_lru_node,
151 list);
152 bpf_map_update_elem(lru->map_fd, &node->key, &null_node, BPF_EXIST);
153 }
154
155 node->key = key;
156 list_move(&node->list, &lru->list);
157
158 lru->nr_misses++;
159 if (seen) {
160 assert(!bpf_map_update_elem(lru->map_fd, &key, &node, BPF_EXIST));
161 } else {
162 lru->nr_unique++;
163 assert(!bpf_map_update_elem(lru->map_fd, &key, &node, BPF_NOEXIST));
164 }
165
166 return seen;
167 }
168
read_keys(const char * dist_file,unsigned long long ** keys)169 static unsigned int read_keys(const char *dist_file,
170 unsigned long long **keys)
171 {
172 struct stat fst;
173 unsigned long long *retkeys;
174 unsigned int counts = 0;
175 int dist_fd;
176 char *b, *l;
177 int i;
178
179 dist_fd = open(dist_file, 0);
180 assert(dist_fd != -1);
181
182 assert(fstat(dist_fd, &fst) == 0);
183 b = malloc(fst.st_size);
184 assert(b);
185
186 assert(read(dist_fd, b, fst.st_size) == fst.st_size);
187 close(dist_fd);
188 for (i = 0; i < fst.st_size; i++) {
189 if (b[i] == '\n')
190 counts++;
191 }
192 counts++; /* in case the last line has no \n */
193
194 retkeys = malloc(counts * sizeof(unsigned long long));
195 assert(retkeys);
196
197 counts = 0;
198 for (l = strtok(b, "\n"); l; l = strtok(NULL, "\n"))
199 retkeys[counts++] = strtoull(l, NULL, 10);
200 free(b);
201
202 *keys = retkeys;
203
204 return counts;
205 }
206
create_map(int map_type,int map_flags,unsigned int size)207 static int create_map(int map_type, int map_flags, unsigned int size)
208 {
209 LIBBPF_OPTS(bpf_map_create_opts, opts,
210 .map_flags = map_flags,
211 );
212 int map_fd;
213
214 map_fd = bpf_map_create(map_type, NULL, sizeof(unsigned long long),
215 sizeof(unsigned long long), size, &opts);
216
217 if (map_fd == -1)
218 perror("bpf_create_map");
219
220 return map_fd;
221 }
222
sched_next_online(int pid,int next_to_try)223 static int sched_next_online(int pid, int next_to_try)
224 {
225 cpu_set_t cpuset;
226
227 if (next_to_try == nr_cpus)
228 return -1;
229
230 while (next_to_try < nr_cpus) {
231 CPU_ZERO(&cpuset);
232 CPU_SET(next_to_try++, &cpuset);
233 if (!sched_setaffinity(pid, sizeof(cpuset), &cpuset))
234 break;
235 }
236
237 return next_to_try;
238 }
239
run_parallel(unsigned int tasks,void (* fn)(int i,void * data),void * data)240 static void run_parallel(unsigned int tasks, void (*fn)(int i, void *data),
241 void *data)
242 {
243 int next_sched_cpu = 0;
244 pid_t pid[tasks];
245 int i;
246
247 for (i = 0; i < tasks; i++) {
248 pid[i] = fork();
249 if (pid[i] == 0) {
250 next_sched_cpu = sched_next_online(0, next_sched_cpu);
251 fn(i, data);
252 exit(0);
253 } else if (pid[i] == -1) {
254 printf("couldn't spawn #%d process\n", i);
255 exit(1);
256 }
257 /* It is mostly redundant and just allow the parent
258 * process to update next_shced_cpu for the next child
259 * process
260 */
261 next_sched_cpu = sched_next_online(pid[i], next_sched_cpu);
262 }
263 for (i = 0; i < tasks; i++) {
264 int status;
265
266 assert(waitpid(pid[i], &status, 0) == pid[i]);
267 assert(status == 0);
268 }
269 }
270
do_test_lru_dist(int task,void * data)271 static void do_test_lru_dist(int task, void *data)
272 {
273 unsigned int nr_misses = 0;
274 struct pfect_lru pfect_lru;
275 unsigned long long key, value = 1234;
276 unsigned int i;
277
278 unsigned int lru_map_fd = ((unsigned int *)data)[0];
279 unsigned int lru_size = ((unsigned int *)data)[1];
280 unsigned long long key_offset = task * dist_key_counts;
281
282 pfect_lru_init(&pfect_lru, lru_size, dist_key_counts);
283
284 for (i = 0; i < dist_key_counts; i++) {
285 key = dist_keys[i] + key_offset;
286
287 pfect_lru_lookup_or_insert(&pfect_lru, key);
288
289 if (!bpf_map_lookup_elem(lru_map_fd, &key, &value))
290 continue;
291
292 if (bpf_map_update_elem(lru_map_fd, &key, &value, BPF_NOEXIST)) {
293 printf("bpf_map_update_elem(lru_map_fd, %llu): errno:%d\n",
294 key, errno);
295 assert(0);
296 }
297
298 nr_misses++;
299 }
300
301 printf(" task:%d BPF LRU: nr_unique:%u(/%u) nr_misses:%u(/%u)\n",
302 task, pfect_lru.nr_unique, dist_key_counts, nr_misses,
303 dist_key_counts);
304 printf(" task:%d Perfect LRU: nr_unique:%u(/%u) nr_misses:%u(/%u)\n",
305 task, pfect_lru.nr_unique, pfect_lru.total,
306 pfect_lru.nr_misses, pfect_lru.total);
307
308 pfect_lru_destroy(&pfect_lru);
309 close(lru_map_fd);
310 }
311
test_parallel_lru_dist(int map_type,int map_flags,int nr_tasks,unsigned int lru_size)312 static void test_parallel_lru_dist(int map_type, int map_flags,
313 int nr_tasks, unsigned int lru_size)
314 {
315 int child_data[2];
316 int lru_map_fd;
317
318 printf("%s (map_type:%d map_flags:0x%X):\n", __func__, map_type,
319 map_flags);
320
321 if (map_flags & BPF_F_NO_COMMON_LRU)
322 lru_map_fd = create_map(map_type, map_flags,
323 nr_cpus * lru_size);
324 else
325 lru_map_fd = create_map(map_type, map_flags,
326 nr_tasks * lru_size);
327 assert(lru_map_fd != -1);
328
329 child_data[0] = lru_map_fd;
330 child_data[1] = lru_size;
331
332 run_parallel(nr_tasks, do_test_lru_dist, child_data);
333
334 close(lru_map_fd);
335 }
336
test_lru_loss0(int map_type,int map_flags)337 static void test_lru_loss0(int map_type, int map_flags)
338 {
339 unsigned long long key, value[nr_cpus];
340 unsigned int old_unused_losses = 0;
341 unsigned int new_unused_losses = 0;
342 unsigned int used_losses = 0;
343 int map_fd;
344
345 printf("%s (map_type:%d map_flags:0x%X): ", __func__, map_type,
346 map_flags);
347
348 assert(sched_next_online(0, 0) != -1);
349
350 if (map_flags & BPF_F_NO_COMMON_LRU)
351 map_fd = create_map(map_type, map_flags, 900 * nr_cpus);
352 else
353 map_fd = create_map(map_type, map_flags, 900);
354
355 assert(map_fd != -1);
356
357 value[0] = 1234;
358
359 for (key = 1; key <= 1000; key++) {
360 int start_key, end_key;
361
362 assert(bpf_map_update_elem(map_fd, &key, value, BPF_NOEXIST) == 0);
363
364 start_key = 101;
365 end_key = min(key, 900);
366
367 while (start_key <= end_key) {
368 bpf_map_lookup_elem(map_fd, &start_key, value);
369 start_key++;
370 }
371 }
372
373 for (key = 1; key <= 1000; key++) {
374 if (bpf_map_lookup_elem(map_fd, &key, value)) {
375 if (key <= 100)
376 old_unused_losses++;
377 else if (key <= 900)
378 used_losses++;
379 else
380 new_unused_losses++;
381 }
382 }
383
384 close(map_fd);
385
386 printf("older-elem-losses:%d(/100) active-elem-losses:%d(/800) "
387 "newer-elem-losses:%d(/100)\n",
388 old_unused_losses, used_losses, new_unused_losses);
389 }
390
test_lru_loss1(int map_type,int map_flags)391 static void test_lru_loss1(int map_type, int map_flags)
392 {
393 unsigned long long key, value[nr_cpus];
394 int map_fd;
395 unsigned int nr_losses = 0;
396
397 printf("%s (map_type:%d map_flags:0x%X): ", __func__, map_type,
398 map_flags);
399
400 assert(sched_next_online(0, 0) != -1);
401
402 if (map_flags & BPF_F_NO_COMMON_LRU)
403 map_fd = create_map(map_type, map_flags, 1000 * nr_cpus);
404 else
405 map_fd = create_map(map_type, map_flags, 1000);
406
407 assert(map_fd != -1);
408
409 value[0] = 1234;
410
411 for (key = 1; key <= 1000; key++)
412 assert(!bpf_map_update_elem(map_fd, &key, value, BPF_NOEXIST));
413
414 for (key = 1; key <= 1000; key++) {
415 if (bpf_map_lookup_elem(map_fd, &key, value))
416 nr_losses++;
417 }
418
419 close(map_fd);
420
421 printf("nr_losses:%d(/1000)\n", nr_losses);
422 }
423
do_test_parallel_lru_loss(int task,void * data)424 static void do_test_parallel_lru_loss(int task, void *data)
425 {
426 const unsigned int nr_stable_elems = 1000;
427 const unsigned int nr_repeats = 100000;
428
429 int map_fd = *(int *)data;
430 unsigned long long stable_base;
431 unsigned long long key, value[nr_cpus];
432 unsigned long long next_ins_key;
433 unsigned int nr_losses = 0;
434 unsigned int i;
435
436 stable_base = task * nr_repeats * 2 + 1;
437 next_ins_key = stable_base;
438 value[0] = 1234;
439 for (i = 0; i < nr_stable_elems; i++) {
440 assert(bpf_map_update_elem(map_fd, &next_ins_key, value,
441 BPF_NOEXIST) == 0);
442 next_ins_key++;
443 }
444
445 for (i = 0; i < nr_repeats; i++) {
446 int rn;
447
448 rn = rand();
449
450 if (rn % 10) {
451 key = rn % nr_stable_elems + stable_base;
452 bpf_map_lookup_elem(map_fd, &key, value);
453 } else {
454 bpf_map_update_elem(map_fd, &next_ins_key, value,
455 BPF_NOEXIST);
456 next_ins_key++;
457 }
458 }
459
460 key = stable_base;
461 for (i = 0; i < nr_stable_elems; i++) {
462 if (bpf_map_lookup_elem(map_fd, &key, value))
463 nr_losses++;
464 key++;
465 }
466
467 printf(" task:%d nr_losses:%u\n", task, nr_losses);
468 }
469
test_parallel_lru_loss(int map_type,int map_flags,int nr_tasks)470 static void test_parallel_lru_loss(int map_type, int map_flags, int nr_tasks)
471 {
472 int map_fd;
473
474 printf("%s (map_type:%d map_flags:0x%X):\n", __func__, map_type,
475 map_flags);
476
477 /* Give 20% more than the active working set */
478 if (map_flags & BPF_F_NO_COMMON_LRU)
479 map_fd = create_map(map_type, map_flags,
480 nr_cpus * (1000 + 200));
481 else
482 map_fd = create_map(map_type, map_flags,
483 nr_tasks * (1000 + 200));
484
485 assert(map_fd != -1);
486
487 run_parallel(nr_tasks, do_test_parallel_lru_loss, &map_fd);
488
489 close(map_fd);
490 }
491
main(int argc,char ** argv)492 int main(int argc, char **argv)
493 {
494 int map_flags[] = {0, BPF_F_NO_COMMON_LRU};
495 const char *dist_file;
496 int nr_tasks = 1;
497 int lru_size;
498 int f;
499
500 if (argc < 4) {
501 printf("Usage: %s <dist-file> <lru-size> <nr-tasks>\n",
502 argv[0]);
503 return -1;
504 }
505
506 dist_file = argv[1];
507 lru_size = atoi(argv[2]);
508 nr_tasks = atoi(argv[3]);
509
510 setbuf(stdout, NULL);
511
512 srand(time(NULL));
513
514 nr_cpus = bpf_num_possible_cpus();
515 assert(nr_cpus != -1);
516 printf("nr_cpus:%d\n\n", nr_cpus);
517
518 nr_tasks = min(nr_tasks, nr_cpus);
519
520 dist_key_counts = read_keys(dist_file, &dist_keys);
521 if (!dist_key_counts) {
522 printf("%s has no key\n", dist_file);
523 return -1;
524 }
525
526 for (f = 0; f < ARRAY_SIZE(map_flags); f++) {
527 test_lru_loss0(BPF_MAP_TYPE_LRU_HASH, map_flags[f]);
528 test_lru_loss1(BPF_MAP_TYPE_LRU_HASH, map_flags[f]);
529 test_parallel_lru_loss(BPF_MAP_TYPE_LRU_HASH, map_flags[f],
530 nr_tasks);
531 test_parallel_lru_dist(BPF_MAP_TYPE_LRU_HASH, map_flags[f],
532 nr_tasks, lru_size);
533 printf("\n");
534 }
535
536 free(dist_keys);
537
538 return 0;
539 }
540
