1.. SPDX-License-Identifier: GPL-2.0-only
2.. Copyright (C) 2022 Red Hat, Inc.
3
4=========================
5BPF_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
12filters are a space-efficient probabilistic data structure used to
13quickly test whether an element exists in a set. In a bloom filter,
14false positives are possible whereas false negatives are not.
15
16The bloom filter map does not have keys, only values. When the bloom
17filter map is created, it must be created with a ``key_size`` of 0.  The
18bloom 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
23BPF programs must use ``bpf_map_push_elem`` to add an element to the
24bloom filter map and ``bpf_map_peek_elem`` to query the map. These
25operations 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
31The ``max_entries`` size that is specified at map creation time is used
32to approximate a reasonable bitmap size for the bloom filter, and is not
33otherwise strictly enforced. If the user wishes to insert more entries
34into the bloom filter than ``max_entries``, this may lead to a higher
35false positive rate.
36
37The number of hashes to use for the bloom filter is configurable using
38the lower 4 bits of ``map_extra`` in ``union bpf_attr`` at map creation
39time. If no number is specified, the default used will be 5 hash
40functions. In general, using more hashes decreases both the false
41positive rate and the speed of a lookup.
42
43It is not possible to delete elements from a bloom filter map. A bloom
44filter map may be used as an inner map. The user is responsible for
45synchronising concurrent updates and lookups to ensure no false negative
46lookups occur.
47
48Usage
49=====
50
51Kernel BPF
52----------
53
54bpf_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
61A ``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
64returns ``0`` on success, or negative error in case of failure.
65
66bpf_map_peek_elem()
67~~~~~~~~~~~~~~~~~~~
68
69.. code-block:: c
70
71   long bpf_map_peek_elem(struct bpf_map *map, void *value)
72
73The ``bpf_map_peek_elem()`` helper is used to determine whether
74``value`` is present in the bloom filter map. This helper returns ``0``
75if ``value`` is probably present in the map, or ``-ENOENT`` if ``value``
76is definitely not present in the map.
77
78Userspace
79---------
80
81bpf_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
88A 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
91success, or negative error in case of failure.
92
93bpf_map_lookup_elem()
94~~~~~~~~~~~~~~~~~~~~~
95
96.. code-block:: c
97
98   int bpf_map_lookup_elem (int fd, const void *key, void *value)
99
100A userspace program can determine the presence of ``value`` in a bloom
101filter using libbpf's ``bpf_map_lookup_elem`` function. The ``key``
102parameter must be set to ``NULL``. Returns ``0`` if ``value`` is
103probably present in the map, or ``-ENOENT`` if ``value`` is definitely
104not present in the map.
105
106Examples
107========
108
109Kernel BPF
110----------
111
112This 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
123This snippet shows how to determine presence of a value in a bloom
124filter 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
139Userspace
140---------
141
142This snippet shows how to use libbpf to create a bloom filter map from
143userspace:
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
160This snippet shows how to add an element to a bloom filter from
161userspace:
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
171References
172==========
173
174https://lwn.net/ml/bpf/20210831225005.2762202-1-joannekoong@fb.com/
175