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 }; 211