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