Documentation/bpf/map_bloom_filter.rst

   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/