1 // SPDX-License-Identifier: GPL-2.0
2 /* Copyright (c) 2021 Facebook */
3
4 #include <argp.h>
5 #include <linux/log2.h>
6 #include <pthread.h>
7 #include "bench.h"
8 #include "bloom_filter_bench.skel.h"
9 #include "bpf_util.h"
10
11 static struct ctx {
12 bool use_array_map;
13 bool use_hashmap;
14 bool hashmap_use_bloom;
15 bool count_false_hits;
16
17 struct bloom_filter_bench *skel;
18
19 int bloom_fd;
20 int hashmap_fd;
21 int array_map_fd;
22
23 pthread_mutex_t map_done_mtx;
24 pthread_cond_t map_done_cv;
25 bool map_done;
26 bool map_prepare_err;
27
28 __u32 next_map_idx;
29 } ctx = {
30 .map_done_mtx = PTHREAD_MUTEX_INITIALIZER,
31 .map_done_cv = PTHREAD_COND_INITIALIZER,
32 };
33
34 struct stat {
35 __u32 stats[3];
36 };
37
38 static struct {
39 __u32 nr_entries;
40 __u8 nr_hash_funcs;
41 __u8 value_size;
42 } args = {
43 .nr_entries = 1000,
44 .nr_hash_funcs = 3,
45 .value_size = 8,
46 };
47
48 enum {
49 ARG_NR_ENTRIES = 3000,
50 ARG_NR_HASH_FUNCS = 3001,
51 ARG_VALUE_SIZE = 3002,
52 };
53
54 static const struct argp_option opts[] = {
55 { "nr_entries", ARG_NR_ENTRIES, "NR_ENTRIES", 0,
56 "Set number of expected unique entries in the bloom filter"},
57 { "nr_hash_funcs", ARG_NR_HASH_FUNCS, "NR_HASH_FUNCS", 0,
58 "Set number of hash functions in the bloom filter"},
59 { "value_size", ARG_VALUE_SIZE, "VALUE_SIZE", 0,
60 "Set value size (in bytes) of bloom filter entries"},
61 {},
62 };
63
parse_arg(int key,char * arg,struct argp_state * state)64 static error_t parse_arg(int key, char *arg, struct argp_state *state)
65 {
66 long ret;
67
68 switch (key) {
69 case ARG_NR_ENTRIES:
70 ret = strtol(arg, NULL, 10);
71 if (ret < 1 || ret > UINT_MAX) {
72 fprintf(stderr, "Invalid nr_entries count.");
73 argp_usage(state);
74 }
75 args.nr_entries = ret;
76 break;
77 case ARG_NR_HASH_FUNCS:
78 ret = strtol(arg, NULL, 10);
79 if (ret < 1 || ret > 15) {
80 fprintf(stderr,
81 "The bloom filter must use 1 to 15 hash functions.");
82 argp_usage(state);
83 }
84 args.nr_hash_funcs = ret;
85 break;
86 case ARG_VALUE_SIZE:
87 ret = strtol(arg, NULL, 10);
88 if (ret < 2 || ret > 256) {
89 fprintf(stderr,
90 "Invalid value size. Must be between 2 and 256 bytes");
91 argp_usage(state);
92 }
93 args.value_size = ret;
94 break;
95 default:
96 return ARGP_ERR_UNKNOWN;
97 }
98
99 return 0;
100 }
101
102 /* exported into benchmark runner */
103 const struct argp bench_bloom_map_argp = {
104 .options = opts,
105 .parser = parse_arg,
106 };
107
validate(void)108 static void validate(void)
109 {
110 if (env.consumer_cnt != 0) {
111 fprintf(stderr,
112 "The bloom filter benchmarks do not support consumer\n");
113 exit(1);
114 }
115 }
116
trigger_bpf_program(void)117 static inline void trigger_bpf_program(void)
118 {
119 syscall(__NR_getpgid);
120 }
121
producer(void * input)122 static void *producer(void *input)
123 {
124 while (true)
125 trigger_bpf_program();
126
127 return NULL;
128 }
129
map_prepare_thread(void * arg)130 static void *map_prepare_thread(void *arg)
131 {
132 __u32 val_size, i;
133 void *val = NULL;
134 int err;
135
136 val_size = args.value_size;
137 val = malloc(val_size);
138 if (!val) {
139 ctx.map_prepare_err = true;
140 goto done;
141 }
142
143 while (true) {
144 i = __atomic_add_fetch(&ctx.next_map_idx, 1, __ATOMIC_RELAXED);
145 if (i > args.nr_entries)
146 break;
147
148 again:
149 /* Populate hashmap, bloom filter map, and array map with the same
150 * random values
151 */
152 err = syscall(__NR_getrandom, val, val_size, 0);
153 if (err != val_size) {
154 ctx.map_prepare_err = true;
155 fprintf(stderr, "failed to get random value: %d\n", -errno);
156 break;
157 }
158
159 if (ctx.use_hashmap) {
160 err = bpf_map_update_elem(ctx.hashmap_fd, val, val, BPF_NOEXIST);
161 if (err) {
162 if (err != -EEXIST) {
163 ctx.map_prepare_err = true;
164 fprintf(stderr, "failed to add elem to hashmap: %d\n",
165 -errno);
166 break;
167 }
168 goto again;
169 }
170 }
171
172 i--;
173
174 if (ctx.use_array_map) {
175 err = bpf_map_update_elem(ctx.array_map_fd, &i, val, 0);
176 if (err) {
177 ctx.map_prepare_err = true;
178 fprintf(stderr, "failed to add elem to array map: %d\n", -errno);
179 break;
180 }
181 }
182
183 if (ctx.use_hashmap && !ctx.hashmap_use_bloom)
184 continue;
185
186 err = bpf_map_update_elem(ctx.bloom_fd, NULL, val, 0);
187 if (err) {
188 ctx.map_prepare_err = true;
189 fprintf(stderr,
190 "failed to add elem to bloom filter map: %d\n", -errno);
191 break;
192 }
193 }
194 done:
195 pthread_mutex_lock(&ctx.map_done_mtx);
196 ctx.map_done = true;
197 pthread_cond_signal(&ctx.map_done_cv);
198 pthread_mutex_unlock(&ctx.map_done_mtx);
199
200 if (val)
201 free(val);
202
203 return NULL;
204 }
205
populate_maps(void)206 static void populate_maps(void)
207 {
208 unsigned int nr_cpus = bpf_num_possible_cpus();
209 pthread_t map_thread;
210 int i, err, nr_rand_bytes;
211
212 ctx.bloom_fd = bpf_map__fd(ctx.skel->maps.bloom_map);
213 ctx.hashmap_fd = bpf_map__fd(ctx.skel->maps.hashmap);
214 ctx.array_map_fd = bpf_map__fd(ctx.skel->maps.array_map);
215
216 for (i = 0; i < nr_cpus; i++) {
217 err = pthread_create(&map_thread, NULL, map_prepare_thread,
218 NULL);
219 if (err) {
220 fprintf(stderr, "failed to create pthread: %d\n", -errno);
221 exit(1);
222 }
223 }
224
225 pthread_mutex_lock(&ctx.map_done_mtx);
226 while (!ctx.map_done)
227 pthread_cond_wait(&ctx.map_done_cv, &ctx.map_done_mtx);
228 pthread_mutex_unlock(&ctx.map_done_mtx);
229
230 if (ctx.map_prepare_err)
231 exit(1);
232
233 nr_rand_bytes = syscall(__NR_getrandom, ctx.skel->bss->rand_vals,
234 ctx.skel->rodata->nr_rand_bytes, 0);
235 if (nr_rand_bytes != ctx.skel->rodata->nr_rand_bytes) {
236 fprintf(stderr, "failed to get random bytes\n");
237 exit(1);
238 }
239 }
240
check_args(void)241 static void check_args(void)
242 {
243 if (args.value_size < 8) {
244 __u64 nr_unique_entries = 1ULL << (args.value_size * 8);
245
246 if (args.nr_entries > nr_unique_entries) {
247 fprintf(stderr,
248 "Not enough unique values for the nr_entries requested\n");
249 exit(1);
250 }
251 }
252 }
253
setup_skeleton(void)254 static struct bloom_filter_bench *setup_skeleton(void)
255 {
256 struct bloom_filter_bench *skel;
257
258 check_args();
259
260 setup_libbpf();
261
262 skel = bloom_filter_bench__open();
263 if (!skel) {
264 fprintf(stderr, "failed to open skeleton\n");
265 exit(1);
266 }
267
268 skel->rodata->hashmap_use_bloom = ctx.hashmap_use_bloom;
269 skel->rodata->count_false_hits = ctx.count_false_hits;
270
271 /* Resize number of entries */
272 bpf_map__set_max_entries(skel->maps.hashmap, args.nr_entries);
273
274 bpf_map__set_max_entries(skel->maps.array_map, args.nr_entries);
275
276 bpf_map__set_max_entries(skel->maps.bloom_map, args.nr_entries);
277
278 /* Set value size */
279 bpf_map__set_value_size(skel->maps.array_map, args.value_size);
280
281 bpf_map__set_value_size(skel->maps.bloom_map, args.value_size);
282
283 bpf_map__set_value_size(skel->maps.hashmap, args.value_size);
284
285 /* For the hashmap, we use the value as the key as well */
286 bpf_map__set_key_size(skel->maps.hashmap, args.value_size);
287
288 skel->bss->value_size = args.value_size;
289
290 /* Set number of hash functions */
291 bpf_map__set_map_extra(skel->maps.bloom_map, args.nr_hash_funcs);
292
293 if (bloom_filter_bench__load(skel)) {
294 fprintf(stderr, "failed to load skeleton\n");
295 exit(1);
296 }
297
298 return skel;
299 }
300
bloom_lookup_setup(void)301 static void bloom_lookup_setup(void)
302 {
303 struct bpf_link *link;
304
305 ctx.use_array_map = true;
306
307 ctx.skel = setup_skeleton();
308
309 populate_maps();
310
311 link = bpf_program__attach(ctx.skel->progs.bloom_lookup);
312 if (!link) {
313 fprintf(stderr, "failed to attach program!\n");
314 exit(1);
315 }
316 }
317
bloom_update_setup(void)318 static void bloom_update_setup(void)
319 {
320 struct bpf_link *link;
321
322 ctx.use_array_map = true;
323
324 ctx.skel = setup_skeleton();
325
326 populate_maps();
327
328 link = bpf_program__attach(ctx.skel->progs.bloom_update);
329 if (!link) {
330 fprintf(stderr, "failed to attach program!\n");
331 exit(1);
332 }
333 }
334
false_positive_setup(void)335 static void false_positive_setup(void)
336 {
337 struct bpf_link *link;
338
339 ctx.use_hashmap = true;
340 ctx.hashmap_use_bloom = true;
341 ctx.count_false_hits = true;
342
343 ctx.skel = setup_skeleton();
344
345 populate_maps();
346
347 link = bpf_program__attach(ctx.skel->progs.bloom_hashmap_lookup);
348 if (!link) {
349 fprintf(stderr, "failed to attach program!\n");
350 exit(1);
351 }
352 }
353
hashmap_with_bloom_setup(void)354 static void hashmap_with_bloom_setup(void)
355 {
356 struct bpf_link *link;
357
358 ctx.use_hashmap = true;
359 ctx.hashmap_use_bloom = true;
360
361 ctx.skel = setup_skeleton();
362
363 populate_maps();
364
365 link = bpf_program__attach(ctx.skel->progs.bloom_hashmap_lookup);
366 if (!link) {
367 fprintf(stderr, "failed to attach program!\n");
368 exit(1);
369 }
370 }
371
hashmap_no_bloom_setup(void)372 static void hashmap_no_bloom_setup(void)
373 {
374 struct bpf_link *link;
375
376 ctx.use_hashmap = true;
377
378 ctx.skel = setup_skeleton();
379
380 populate_maps();
381
382 link = bpf_program__attach(ctx.skel->progs.bloom_hashmap_lookup);
383 if (!link) {
384 fprintf(stderr, "failed to attach program!\n");
385 exit(1);
386 }
387 }
388
measure(struct bench_res * res)389 static void measure(struct bench_res *res)
390 {
391 unsigned long total_hits = 0, total_drops = 0, total_false_hits = 0;
392 static unsigned long last_hits, last_drops, last_false_hits;
393 unsigned int nr_cpus = bpf_num_possible_cpus();
394 int hit_key, drop_key, false_hit_key;
395 int i;
396
397 hit_key = ctx.skel->rodata->hit_key;
398 drop_key = ctx.skel->rodata->drop_key;
399 false_hit_key = ctx.skel->rodata->false_hit_key;
400
401 if (ctx.skel->bss->error != 0) {
402 fprintf(stderr, "error (%d) when searching the bloom filter\n",
403 ctx.skel->bss->error);
404 exit(1);
405 }
406
407 for (i = 0; i < nr_cpus; i++) {
408 struct stat *s = (void *)&ctx.skel->bss->percpu_stats[i];
409
410 total_hits += s->stats[hit_key];
411 total_drops += s->stats[drop_key];
412 total_false_hits += s->stats[false_hit_key];
413 }
414
415 res->hits = total_hits - last_hits;
416 res->drops = total_drops - last_drops;
417 res->false_hits = total_false_hits - last_false_hits;
418
419 last_hits = total_hits;
420 last_drops = total_drops;
421 last_false_hits = total_false_hits;
422 }
423
424 const struct bench bench_bloom_lookup = {
425 .name = "bloom-lookup",
426 .argp = &bench_bloom_map_argp,
427 .validate = validate,
428 .setup = bloom_lookup_setup,
429 .producer_thread = producer,
430 .measure = measure,
431 .report_progress = hits_drops_report_progress,
432 .report_final = hits_drops_report_final,
433 };
434
435 const struct bench bench_bloom_update = {
436 .name = "bloom-update",
437 .argp = &bench_bloom_map_argp,
438 .validate = validate,
439 .setup = bloom_update_setup,
440 .producer_thread = producer,
441 .measure = measure,
442 .report_progress = hits_drops_report_progress,
443 .report_final = hits_drops_report_final,
444 };
445
446 const struct bench bench_bloom_false_positive = {
447 .name = "bloom-false-positive",
448 .argp = &bench_bloom_map_argp,
449 .validate = validate,
450 .setup = false_positive_setup,
451 .producer_thread = producer,
452 .measure = measure,
453 .report_progress = false_hits_report_progress,
454 .report_final = false_hits_report_final,
455 };
456
457 const struct bench bench_hashmap_without_bloom = {
458 .name = "hashmap-without-bloom",
459 .argp = &bench_bloom_map_argp,
460 .validate = validate,
461 .setup = hashmap_no_bloom_setup,
462 .producer_thread = producer,
463 .measure = measure,
464 .report_progress = hits_drops_report_progress,
465 .report_final = hits_drops_report_final,
466 };
467
468 const struct bench bench_hashmap_with_bloom = {
469 .name = "hashmap-with-bloom",
470 .argp = &bench_bloom_map_argp,
471 .validate = validate,
472 .setup = hashmap_with_bloom_setup,
473 .producer_thread = producer,
474 .measure = measure,
475 .report_progress = hits_drops_report_progress,
476 .report_final = hits_drops_report_final,
477 };
478