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
10 char _license[] SEC("license") = "GPL";
11
12 struct bpf_map;
13
14 __u8 rand_vals[2500000];
15 const __u32 nr_rand_bytes = 2500000;
16
17 struct {
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
25 struct {
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
34 struct {
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
42 struct callback_ctx {
43 struct bpf_map *map;
44 bool update;
45 };
46
47 /* Tracks the number of hits, drops, and false hits */
48 struct {
49 __u32 stats[3];
50 } __attribute__((__aligned__(256))) percpu_stats[256];
51
52 const __u32 hit_key = 0;
53 const __u32 drop_key = 1;
54 const __u32 false_hit_key = 2;
55
56 __u8 value_size;
57
58 const volatile bool hashmap_use_bloom;
59 const volatile bool count_false_hits;
60
61 int error = 0;
62
log_result(__u32 key)63 static __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
70 static __u64
bloom_callback(struct bpf_map * map,__u32 * key,void * val,struct callback_ctx * data)71 bloom_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(hit_key);
87
88 return 0;
89 }
90
91 SEC("fentry/" SYS_PREFIX "sys_getpgid")
bloom_lookup(void * ctx)92 int 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
104 SEC("fentry/" SYS_PREFIX "sys_getpgid")
bloom_update(void * ctx)105 int 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
117 SEC("fentry/" SYS_PREFIX "sys_getpgid")
bloom_hashmap_lookup(void * ctx)118 int 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(hit_key);
138 continue;
139 }
140 }
141
142 result = bpf_map_lookup_elem(&hashmap,
143 rand_vals + index);
144 if (result) {
145 log_result(hit_key);
146 } else {
147 if (hashmap_use_bloom && count_false_hits)
148 log_result(false_hit_key);
149 log_result(drop_key);
150 }
151 }
152
153 return 0;
154 }
155