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