1// SPDX-License-Identifier: GPL-2.0
2/* Copyright (c) 2021 Facebook */
3
4#include <errno.h>
5#include <linux/bpf.h>
6#include <stdbool.h>
7#include <bpf/bpf_helpers.h>
8#include "bpf_misc.h"
9
10char _license[] SEC("license") = "GPL";
11
12struct bpf_map;
13
14__u8 rand_vals[2500000];
15const __u32 nr_rand_bytes = 2500000;
16
17struct {
18 __uint(type, BPF_MAP_TYPE_ARRAY);
19 __uint(key_size, sizeof(__u32));
20 /* max entries and value_size will be set programmatically.
21 * They are configurable from the userspace bench program.
22 */
23} array_map SEC(".maps");
24
25struct {
26 __uint(type, BPF_MAP_TYPE_BLOOM_FILTER);
27 /* max entries, value_size, and # of hash functions will be set
28 * programmatically. They are configurable from the userspace
29 * bench program.
30 */
31 __uint(map_extra, 3);
32} bloom_map SEC(".maps");
33
34struct {
35 __uint(type, BPF_MAP_TYPE_HASH);
36 /* max entries, key_size, and value_size, will be set
37 * programmatically. They are configurable from the userspace
38 * bench program.
39 */
40} hashmap SEC(".maps");
41
42struct callback_ctx {
43 struct bpf_map *map;
44 bool update;
45};
46
47/* Tracks the number of hits, drops, and false hits */
48struct {
49 __u32 stats[3];
50} __attribute__((__aligned__(256))) percpu_stats[256];
51
52const __u32 hit_key = 0;
53const __u32 drop_key = 1;
54const __u32 false_hit_key = 2;
55
56__u8 value_size;
57
58const volatile bool hashmap_use_bloom;
59const volatile bool count_false_hits;
60
61int error = 0;
62
63static __always_inline void log_result(__u32 key)
64{
65 __u32 cpu = bpf_get_smp_processor_id();
66
67 percpu_stats[cpu & 255].stats[key]++;
68}
69
70static __u64
71bloom_callback(struct bpf_map *map, __u32 *key, void *val,
72 struct callback_ctx *data)
73{
74 int err;
75
76 if (data->update)
77 err = bpf_map_push_elem(data->map, val, 0);
78 else
79 err = bpf_map_peek_elem(data->map, val);
80
81 if (err) {
82 error |= 1;
83 return 1; /* stop the iteration */
84 }
85
86 log_result(key: hit_key);
87
88 return 0;
89}
90
91SEC("fentry/" SYS_PREFIX "sys_getpgid")
92int bloom_lookup(void *ctx)
93{
94 struct callback_ctx data;
95
96 data.map = (struct bpf_map *)&bloom_map;
97 data.update = false;
98
99 bpf_for_each_map_elem(&array_map, bloom_callback, &data, 0);
100
101 return 0;
102}
103
104SEC("fentry/" SYS_PREFIX "sys_getpgid")
105int bloom_update(void *ctx)
106{
107 struct callback_ctx data;
108
109 data.map = (struct bpf_map *)&bloom_map;
110 data.update = true;
111
112 bpf_for_each_map_elem(&array_map, bloom_callback, &data, 0);
113
114 return 0;
115}
116
117SEC("fentry/" SYS_PREFIX "sys_getpgid")
118int bloom_hashmap_lookup(void *ctx)
119{
120 __u64 *result;
121 int i, err;
122
123 __u32 index = bpf_get_prandom_u32();
124 __u32 bitmask = (1ULL << 21) - 1;
125
126 for (i = 0; i < 1024; i++, index += value_size) {
127 index = index & bitmask;
128
129 if (hashmap_use_bloom) {
130 err = bpf_map_peek_elem(&bloom_map,
131 rand_vals + index);
132 if (err) {
133 if (err != -ENOENT) {
134 error |= 2;
135 return 0;
136 }
137 log_result(key: hit_key);
138 continue;
139 }
140 }
141
142 result = bpf_map_lookup_elem(&hashmap,
143 rand_vals + index);
144 if (result) {
145 log_result(key: hit_key);
146 } else {
147 if (hashmap_use_bloom && count_false_hits)
148 log_result(key: false_hit_key);
149 log_result(key: drop_key);
150 }
151 }
152
153 return 0;
154}
155

source code of linux/tools/testing/selftests/bpf/progs/bloom_filter_bench.c