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