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 (!bpf_capable()) 90 return ERR_PTR(-EPERM); 91 92 if (attr->key_size != 0 || attr->value_size == 0 || 93 attr->max_entries == 0 || 94 attr->map_flags & ~BLOOM_CREATE_FLAG_MASK || 95 !bpf_map_flags_access_ok(attr->map_flags) || 96 /* The lower 4 bits of map_extra (0xF) specify the number 97 * of hash functions 98 */ 99 (attr->map_extra & ~0xF)) 100 return ERR_PTR(-EINVAL); 101 102 nr_hash_funcs = attr->map_extra; 103 if (nr_hash_funcs == 0) 104 /* Default to using 5 hash functions if unspecified */ 105 nr_hash_funcs = 5; 106 107 /* For the bloom filter, the optimal bit array size that minimizes the 108 * false positive probability is n * k / ln(2) where n is the number of 109 * expected entries in the bloom filter and k is the number of hash 110 * functions. We use 7 / 5 to approximate 1 / ln(2). 111 * 112 * We round this up to the nearest power of two to enable more efficient 113 * hashing using bitmasks. The bitmask will be the bit array size - 1. 114 * 115 * If this overflows a u32, the bit array size will have 2^32 (4 116 * GB) bits. 117 */ 118 if (check_mul_overflow(attr->max_entries, nr_hash_funcs, &nr_bits) || 119 check_mul_overflow(nr_bits / 5, (u32)7, &nr_bits) || 120 nr_bits > (1UL << 31)) { 121 /* The bit array size is 2^32 bits but to avoid overflowing the 122 * u32, we use U32_MAX, which will round up to the equivalent 123 * number of bytes 124 */ 125 bitset_bytes = BITS_TO_BYTES(U32_MAX); 126 bitset_mask = U32_MAX; 127 } else { 128 if (nr_bits <= BITS_PER_LONG) 129 nr_bits = BITS_PER_LONG; 130 else 131 nr_bits = roundup_pow_of_two(nr_bits); 132 bitset_bytes = BITS_TO_BYTES(nr_bits); 133 bitset_mask = nr_bits - 1; 134 } 135 136 bitset_bytes = roundup(bitset_bytes, sizeof(unsigned long)); 137 bloom = bpf_map_area_alloc(sizeof(*bloom) + bitset_bytes, numa_node); 138 139 if (!bloom) 140 return ERR_PTR(-ENOMEM); 141 142 bpf_map_init_from_attr(&bloom->map, attr); 143 144 bloom->nr_hash_funcs = nr_hash_funcs; 145 bloom->bitset_mask = bitset_mask; 146 147 if (!(attr->map_flags & BPF_F_ZERO_SEED)) 148 bloom->hash_seed = get_random_u32(); 149 150 return &bloom->map; 151 } 152 153 static void bloom_map_free(struct bpf_map *map) 154 { 155 struct bpf_bloom_filter *bloom = 156 container_of(map, struct bpf_bloom_filter, map); 157 158 bpf_map_area_free(bloom); 159 } 160 161 static void *bloom_map_lookup_elem(struct bpf_map *map, void *key) 162 { 163 /* The eBPF program should use map_peek_elem instead */ 164 return ERR_PTR(-EINVAL); 165 } 166 167 static long bloom_map_update_elem(struct bpf_map *map, void *key, 168 void *value, u64 flags) 169 { 170 /* The eBPF program should use map_push_elem instead */ 171 return -EINVAL; 172 } 173 174 static int bloom_map_check_btf(const struct bpf_map *map, 175 const struct btf *btf, 176 const struct btf_type *key_type, 177 const struct btf_type *value_type) 178 { 179 /* Bloom filter maps are keyless */ 180 return btf_type_is_void(key_type) ? 0 : -EINVAL; 181 } 182 183 static u64 bloom_map_mem_usage(const struct bpf_map *map) 184 { 185 struct bpf_bloom_filter *bloom; 186 u64 bitset_bytes; 187 188 bloom = container_of(map, struct bpf_bloom_filter, map); 189 bitset_bytes = BITS_TO_BYTES((u64)bloom->bitset_mask + 1); 190 bitset_bytes = roundup(bitset_bytes, sizeof(unsigned long)); 191 return sizeof(*bloom) + bitset_bytes; 192 } 193 194 BTF_ID_LIST_SINGLE(bpf_bloom_map_btf_ids, struct, bpf_bloom_filter) 195 const struct bpf_map_ops bloom_filter_map_ops = { 196 .map_meta_equal = bpf_map_meta_equal, 197 .map_alloc = bloom_map_alloc, 198 .map_free = bloom_map_free, 199 .map_get_next_key = bloom_map_get_next_key, 200 .map_push_elem = bloom_map_push_elem, 201 .map_peek_elem = bloom_map_peek_elem, 202 .map_pop_elem = bloom_map_pop_elem, 203 .map_lookup_elem = bloom_map_lookup_elem, 204 .map_update_elem = bloom_map_update_elem, 205 .map_delete_elem = bloom_map_delete_elem, 206 .map_check_btf = bloom_map_check_btf, 207 .map_mem_usage = bloom_map_mem_usage, 208 .map_btf_id = &bpf_bloom_map_btf_ids[0], 209 }; 210