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