Commit | Line | Data |
---|---|---|
264c2186 DH |
1 | .. SPDX-License-Identifier: GPL-2.0-only |
2 | .. Copyright (C) 2022 Red Hat, Inc. | |
3 | ||
4 | ========================= | |
5 | BPF_MAP_TYPE_BLOOM_FILTER | |
6 | ========================= | |
7 | ||
8 | .. note:: | |
9 | - ``BPF_MAP_TYPE_BLOOM_FILTER`` was introduced in kernel version 5.16 | |
10 | ||
11 | ``BPF_MAP_TYPE_BLOOM_FILTER`` provides a BPF bloom filter map. Bloom | |
12 | filters are a space-efficient probabilistic data structure used to | |
13 | quickly test whether an element exists in a set. In a bloom filter, | |
14 | false positives are possible whereas false negatives are not. | |
15 | ||
16 | The bloom filter map does not have keys, only values. When the bloom | |
17 | filter map is created, it must be created with a ``key_size`` of 0. The | |
18 | bloom filter map supports two operations: | |
19 | ||
20 | - push: adding an element to the map | |
21 | - peek: determining whether an element is present in the map | |
22 | ||
23 | BPF programs must use ``bpf_map_push_elem`` to add an element to the | |
24 | bloom filter map and ``bpf_map_peek_elem`` to query the map. These | |
25 | operations are exposed to userspace applications using the existing | |
26 | ``bpf`` syscall in the following way: | |
27 | ||
28 | - ``BPF_MAP_UPDATE_ELEM`` -> push | |
29 | - ``BPF_MAP_LOOKUP_ELEM`` -> peek | |
30 | ||
31 | The ``max_entries`` size that is specified at map creation time is used | |
32 | to approximate a reasonable bitmap size for the bloom filter, and is not | |
33 | otherwise strictly enforced. If the user wishes to insert more entries | |
34 | into the bloom filter than ``max_entries``, this may lead to a higher | |
35 | false positive rate. | |
36 | ||
37 | The number of hashes to use for the bloom filter is configurable using | |
38 | the lower 4 bits of ``map_extra`` in ``union bpf_attr`` at map creation | |
39 | time. If no number is specified, the default used will be 5 hash | |
40 | functions. In general, using more hashes decreases both the false | |
41 | positive rate and the speed of a lookup. | |
42 | ||
43 | It is not possible to delete elements from a bloom filter map. A bloom | |
44 | filter map may be used as an inner map. The user is responsible for | |
45 | synchronising concurrent updates and lookups to ensure no false negative | |
46 | lookups occur. | |
47 | ||
48 | Usage | |
49 | ===== | |
50 | ||
51 | Kernel BPF | |
52 | ---------- | |
53 | ||
54 | bpf_map_push_elem() | |
55 | ~~~~~~~~~~~~~~~~~~~ | |
56 | ||
57 | .. code-block:: c | |
58 | ||
59 | long bpf_map_push_elem(struct bpf_map *map, const void *value, u64 flags) | |
60 | ||
61 | A ``value`` can be added to a bloom filter using the | |
62 | ``bpf_map_push_elem()`` helper. The ``flags`` parameter must be set to | |
63 | ``BPF_ANY`` when adding an entry to the bloom filter. This helper | |
64 | returns ``0`` on success, or negative error in case of failure. | |
65 | ||
66 | bpf_map_peek_elem() | |
67 | ~~~~~~~~~~~~~~~~~~~ | |
68 | ||
69 | .. code-block:: c | |
70 | ||
71 | long bpf_map_peek_elem(struct bpf_map *map, void *value) | |
72 | ||
73 | The ``bpf_map_peek_elem()`` helper is used to determine whether | |
74 | ``value`` is present in the bloom filter map. This helper returns ``0`` | |
75 | if ``value`` is probably present in the map, or ``-ENOENT`` if ``value`` | |
76 | is definitely not present in the map. | |
77 | ||
78 | Userspace | |
79 | --------- | |
80 | ||
81 | bpf_map_update_elem() | |
82 | ~~~~~~~~~~~~~~~~~~~~~ | |
83 | ||
84 | .. code-block:: c | |
85 | ||
86 | int bpf_map_update_elem (int fd, const void *key, const void *value, __u64 flags) | |
87 | ||
88 | A userspace program can add a ``value`` to a bloom filter using libbpf's | |
89 | ``bpf_map_update_elem`` function. The ``key`` parameter must be set to | |
90 | ``NULL`` and ``flags`` must be set to ``BPF_ANY``. Returns ``0`` on | |
91 | success, or negative error in case of failure. | |
92 | ||
93 | bpf_map_lookup_elem() | |
94 | ~~~~~~~~~~~~~~~~~~~~~ | |
95 | ||
96 | .. code-block:: c | |
97 | ||
98 | int bpf_map_lookup_elem (int fd, const void *key, void *value) | |
99 | ||
100 | A userspace program can determine the presence of ``value`` in a bloom | |
101 | filter using libbpf's ``bpf_map_lookup_elem`` function. The ``key`` | |
102 | parameter must be set to ``NULL``. Returns ``0`` if ``value`` is | |
103 | probably present in the map, or ``-ENOENT`` if ``value`` is definitely | |
104 | not present in the map. | |
105 | ||
106 | Examples | |
107 | ======== | |
108 | ||
109 | Kernel BPF | |
110 | ---------- | |
111 | ||
112 | This snippet shows how to declare a bloom filter in a BPF program: | |
113 | ||
114 | .. code-block:: c | |
115 | ||
116 | struct { | |
117 | __uint(type, BPF_MAP_TYPE_BLOOM_FILTER); | |
118 | __type(value, __u32); | |
119 | __uint(max_entries, 1000); | |
120 | __uint(map_extra, 3); | |
121 | } bloom_filter SEC(".maps"); | |
122 | ||
123 | This snippet shows how to determine presence of a value in a bloom | |
124 | filter in a BPF program: | |
125 | ||
126 | .. code-block:: c | |
127 | ||
128 | void *lookup(__u32 key) | |
129 | { | |
130 | if (bpf_map_peek_elem(&bloom_filter, &key) == 0) { | |
131 | /* Verify not a false positive and fetch an associated | |
132 | * value using a secondary lookup, e.g. in a hash table | |
133 | */ | |
134 | return bpf_map_lookup_elem(&hash_table, &key); | |
135 | } | |
136 | return 0; | |
137 | } | |
138 | ||
139 | Userspace | |
140 | --------- | |
141 | ||
142 | This snippet shows how to use libbpf to create a bloom filter map from | |
143 | userspace: | |
144 | ||
145 | .. code-block:: c | |
146 | ||
147 | int create_bloom() | |
148 | { | |
149 | LIBBPF_OPTS(bpf_map_create_opts, opts, | |
150 | .map_extra = 3); /* number of hashes */ | |
151 | ||
152 | return bpf_map_create(BPF_MAP_TYPE_BLOOM_FILTER, | |
153 | "ipv6_bloom", /* name */ | |
154 | 0, /* key size, must be zero */ | |
155 | sizeof(ipv6_addr), /* value size */ | |
156 | 10000, /* max entries */ | |
157 | &opts); /* create options */ | |
158 | } | |
159 | ||
160 | This snippet shows how to add an element to a bloom filter from | |
161 | userspace: | |
162 | ||
163 | .. code-block:: c | |
164 | ||
165 | int add_element(struct bpf_map *bloom_map, __u32 value) | |
166 | { | |
167 | int bloom_fd = bpf_map__fd(bloom_map); | |
168 | return bpf_map_update_elem(bloom_fd, NULL, &value, BPF_ANY); | |
169 | } | |
170 | ||
171 | References | |
172 | ========== | |
173 | ||
174 | https://lwn.net/ml/bpf/20210831225005.2762202-1-joannekoong@fb.com/ |