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