1 /* 2 * Copyright (c) 2021 Apple Inc. All rights reserved. 3 * 4 * @APPLE_OSREFERENCE_LICENSE_HEADER_START@ 5 * 6 * This file contains Original Code and/or Modifications of Original Code 7 * as defined in and that are subject to the Apple Public Source License 8 * Version 2.0 (the 'License'). You may not use this file except in 9 * compliance with the License. The rights granted to you under the License 10 * may not be used to create, or enable the creation or redistribution of, 11 * unlawful or unlicensed copies of an Apple operating system, or to 12 * circumvent, violate, or enable the circumvention or violation of, any 13 * terms of an Apple operating system software license agreement. 14 * 15 * Please obtain a copy of the License at 16 * http://www.opensource.apple.com/apsl/ and read it before using this file. 17 * 18 * The Original Code and all software distributed under the License are 19 * distributed on an 'AS IS' basis, WITHOUT WARRANTY OF ANY KIND, EITHER 20 * EXPRESS OR IMPLIED, AND APPLE HEREBY DISCLAIMS ALL SUCH WARRANTIES, 21 * INCLUDING WITHOUT LIMITATION, ANY WARRANTIES OF MERCHANTABILITY, 22 * FITNESS FOR A PARTICULAR PURPOSE, QUIET ENJOYMENT OR NON-INFRINGEMENT. 23 * Please see the License for the specific language governing rights and 24 * limitations under the License. 25 * 26 * @APPLE_OSREFERENCE_LICENSE_HEADER_END@ 27 */ 28 29 #ifndef _NET_BLOOM_FILTER_H_ 30 #define _NET_BLOOM_FILTER_H_ 31 32 #include <sys/types.h> 33 34 #ifdef __cplusplus 35 extern "C" { 36 #endif 37 38 // A Bloom Filter is a space-efficient probabilistic data structure 39 // that is used to test whether an element is a member of a set. It has a small 40 // rate of false positives, but it is guaranteed to have no false negatives. 41 // 42 // net_bloom_filter is a minimal implementation for use in kernel networking 43 // that uses three hash functions: net_flowhash_jhash, net_flowhash_mh3_x64_128, 44 // and net_flowhash_mh3_x86_32. This is optimal for a 10% false positive rate. 45 // The optimal number of bits should be calculated as: 46 // num_bits = ((2.3 * ELEMENT_COUNT) / 0.48) 47 48 #define kNetBloomFilterBitsPerTableElement (sizeof(uint32_t) * 8) 49 // Define net_bloom_howmany macro without ternary expression to work with __counted_by. 50 #define net_bloom_howmany(x, y) (((x) / (y)) + ((x) % (y) != 0)) 51 52 struct net_bloom_filter { 53 uint32_t b_table_num_bits; 54 uint32_t b_table[__counted_by(net_bloom_howmany(b_table_num_bits, kNetBloomFilterBitsPerTableElement))]; 55 }; 56 57 struct net_bloom_filter * 58 net_bloom_filter_create(uint32_t num_bits); 59 60 size_t 61 net_bloom_filter_get_size(uint32_t num_bits); 62 63 void 64 net_bloom_filter_destroy(struct net_bloom_filter *filter); 65 66 void 67 net_bloom_filter_insert(struct net_bloom_filter *filter, 68 const void * __sized_by(length)buffer, 69 uint32_t length); 70 71 bool 72 net_bloom_filter_contains(struct net_bloom_filter *filter, 73 const void * __sized_by(length)buffer, 74 uint32_t length); 75 76 #ifdef __cplusplus 77 } 78 #endif 79 80 #endif /* _NET_BLOOM_FILTER_H_ */ 81