kernel/bpf/bloom_filter.c

   1 // SPDX-License-Identifier: GPL-2.0
   2 /* Copyright (c) 2021 Facebook */
   3
   4 #include <linux/bitmap.h>
   5 #include <linux/bpf.h>
   6 #include <linux/btf.h>
   7 #include <linux/err.h>
   8 #include <linux/jhash.h>
   9 #include <linux/random.h>
  10
  11 #define BLOOM_CREATE_FLAG_MASK \
  12         (BPF_F_NUMA_NODE | BPF_F_ZERO_SEED | BPF_F_ACCESS_MASK)
  13
  14 struct bpf_bloom_filter {
  15         struct bpf_map map;
  16         u32 bitset_mask;
  17         u32 hash_seed;
  18         /* If the size of the values in the bloom filter is u32 aligned,
  19          * then it is more performant to use jhash2 as the underlying hash
  20          * function, else we use jhash. This tracks the number of u32s
  21          * in an u32-aligned value size. If the value size is not u32 aligned,
  22          * this will be 0.
  23          */
  24         u32 aligned_u32_count;
  25         u32 nr_hash_funcs;
  26         unsigned long bitset[];
  27 };
  28
  29 static u32 hash(struct bpf_bloom_filter *bloom, void *value,
  30                 u32 value_size, u32 index)
  31 {
  32         u32 h;
  33
  34         if (bloom->aligned_u32_count)
  35                 h = jhash2(value, bloom->aligned_u32_count,
  36                            bloom->hash_seed + index);
  37         else
  38                 h = jhash(value, value_size, bloom->hash_seed + index);
  39
  40         return h & bloom->bitset_mask;
  41 }
  42
  43 static int bloom_map_peek_elem(struct bpf_map *map, void *value)
  44 {
  45         struct bpf_bloom_filter *bloom =
  46                 container_of(map, struct bpf_bloom_filter, map);
  47         u32 i, h;
  48
  49         for (i = 0; i < bloom->nr_hash_funcs; i++) {
  50                 h = hash(bloom, value, map->value_size, i);
  51                 if (!test_bit(h, bloom->bitset))
  52                         return -ENOENT;
  53         }
  54
  55         return 0;
  56 }
  57
  58 static int bloom_map_push_elem(struct bpf_map *map, void *value, u64 flags)
  59 {
  60         struct bpf_bloom_filter *bloom =
  61                 container_of(map, struct bpf_bloom_filter, map);
  62         u32 i, h;
  63
  64         if (flags != BPF_ANY)
  65                 return -EINVAL;
  66
  67         for (i = 0; i < bloom->nr_hash_funcs; i++) {
  68                 h = hash(bloom, value, map->value_size, i);
  69                 set_bit(h, bloom->bitset);
  70         }
  71
  72         return 0;
  73 }
  74
  75 static int bloom_map_pop_elem(struct bpf_map *map, void *value)
  76 {
  77         return -EOPNOTSUPP;
  78 }
  79
  80 static int bloom_map_delete_elem(struct bpf_map *map, void *value)
  81 {
  82         return -EOPNOTSUPP;
  83 }
  84
  85 static int bloom_map_get_next_key(struct bpf_map *map, void *key, void *next_key)
  86 {
  87         return -EOPNOTSUPP;
  88 }
  89
  90 static struct bpf_map *bloom_map_alloc(union bpf_attr *attr)
  91 {
  92         u32 bitset_bytes, bitset_mask, nr_hash_funcs, nr_bits;
  93         int numa_node = bpf_map_attr_numa_node(attr);
  94         struct bpf_bloom_filter *bloom;
  95
  96         if (!bpf_capable())
  97                 return ERR_PTR(-EPERM);
  98
  99         if (attr->key_size != 0 || attr->value_size == 0 ||
 100             attr->max_entries == 0 ||
 101             attr->map_flags & ~BLOOM_CREATE_FLAG_MASK ||
 102             !bpf_map_flags_access_ok(attr->map_flags) ||
 103             /* The lower 4 bits of map_extra (0xF) specify the number
 104              * of hash functions
 105              */
 106             (attr->map_extra & ~0xF))
 107                 return ERR_PTR(-EINVAL);
 108
 109         nr_hash_funcs = attr->map_extra;
 110         if (nr_hash_funcs == 0)
 111                 /* Default to using 5 hash functions if unspecified */
 112                 nr_hash_funcs = 5;
 113
 114         /* For the bloom filter, the optimal bit array size that minimizes the
 115          * false positive probability is n * k / ln(2) where n is the number of
 116          * expected entries in the bloom filter and k is the number of hash
 117          * functions. We use 7 / 5 to approximate 1 / ln(2).
 118          *
 119          * We round this up to the nearest power of two to enable more efficient
 120          * hashing using bitmasks. The bitmask will be the bit array size - 1.
 121          *
 122          * If this overflows a u32, the bit array size will have 2^32 (4
 123          * GB) bits.
 124          */
 125         if (check_mul_overflow(attr->max_entries, nr_hash_funcs, &nr_bits) ||
 126             check_mul_overflow(nr_bits / 5, (u32)7, &nr_bits) ||
 127             nr_bits > (1UL << 31)) {
 128                 /* The bit array size is 2^32 bits but to avoid overflowing the
 129                  * u32, we use U32_MAX, which will round up to the equivalent
 130                  * number of bytes
 131                  */
 132                 bitset_bytes = BITS_TO_BYTES(U32_MAX);
 133                 bitset_mask = U32_MAX;
 134         } else {
 135                 if (nr_bits <= BITS_PER_LONG)
 136                         nr_bits = BITS_PER_LONG;
 137                 else
 138                         nr_bits = roundup_pow_of_two(nr_bits);
 139                 bitset_bytes = BITS_TO_BYTES(nr_bits);
 140                 bitset_mask = nr_bits - 1;
 141         }
 142
 143         bitset_bytes = roundup(bitset_bytes, sizeof(unsigned long));
 144         bloom = bpf_map_area_alloc(sizeof(*bloom) + bitset_bytes, numa_node);
 145
 146         if (!bloom)
 147                 return ERR_PTR(-ENOMEM);
 148
 149         bpf_map_init_from_attr(&bloom->map, attr);
 150
 151         bloom->nr_hash_funcs = nr_hash_funcs;
 152         bloom->bitset_mask = bitset_mask;
 153
 154         /* Check whether the value size is u32-aligned */
 155         if ((attr->value_size & (sizeof(u32) - 1)) == 0)
 156                 bloom->aligned_u32_count =
 157                         attr->value_size / sizeof(u32);
 158
 159         if (!(attr->map_flags & BPF_F_ZERO_SEED))
 160                 bloom->hash_seed = get_random_int();
 161
 162         return &bloom->map;
 163 }
 164
 165 static void bloom_map_free(struct bpf_map *map)
 166 {
 167         struct bpf_bloom_filter *bloom =
 168                 container_of(map, struct bpf_bloom_filter, map);
 169
 170         bpf_map_area_free(bloom);
 171 }
 172
 173 static void *bloom_map_lookup_elem(struct bpf_map *map, void *key)
 174 {
 175         /* The eBPF program should use map_peek_elem instead */
 176         return ERR_PTR(-EINVAL);
 177 }
 178
 179 static int bloom_map_update_elem(struct bpf_map *map, void *key,
 180                                  void *value, u64 flags)
 181 {
 182         /* The eBPF program should use map_push_elem instead */
 183         return -EINVAL;
 184 }
 185
 186 static int bloom_map_check_btf(const struct bpf_map *map,
 187                                const struct btf *btf,
 188                                const struct btf_type *key_type,
 189                                const struct btf_type *value_type)
 190 {
 191         /* Bloom filter maps are keyless */
 192         return btf_type_is_void(key_type) ? 0 : -EINVAL;
 193 }
 194
 195 static int bpf_bloom_map_btf_id;
 196 const struct bpf_map_ops bloom_filter_map_ops = {
 197         .map_meta_equal = bpf_map_meta_equal,
 198         .map_alloc = bloom_map_alloc,
 199         .map_free = bloom_map_free,
 200         .map_get_next_key = bloom_map_get_next_key,
 201         .map_push_elem = bloom_map_push_elem,
 202         .map_peek_elem = bloom_map_peek_elem,
 203         .map_pop_elem = bloom_map_pop_elem,
 204         .map_lookup_elem = bloom_map_lookup_elem,
 205         .map_update_elem = bloom_map_update_elem,
 206         .map_delete_elem = bloom_map_delete_elem,
 207         .map_check_btf = bloom_map_check_btf,
 208         .map_btf_name = "bpf_bloom_filter",
 209         .map_btf_id = &bpf_bloom_map_btf_id,
 210 };