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/
Linux® is a registered trademark of Linus Torvalds in the United States and other countries.
TOMOYO® is a registered trademark of NTT DATA CORPORATION.