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 #include <stdbool.h>
30 #include <sys/types.h>
31 #include <sys/malloc.h>
32 #include <machine/endian.h>
33 #include <net/flowhash.h>
34 #include <net/bloom_filter.h>
35 #include <os/base.h>
36
37 size_t
net_bloom_filter_get_size(uint32_t num_bits)38 net_bloom_filter_get_size(uint32_t num_bits)
39 {
40 if (num_bits == 0) {
41 // 0 bits is not valid
42 return 0;
43 }
44
45 uint32_t num_elements = howmany(num_bits, kNetBloomFilterBitsPerTableElement);
46 return sizeof(struct net_bloom_filter) + (sizeof(uint32_t) * num_elements);
47 }
48
49 struct net_bloom_filter *
net_bloom_filter_create(uint32_t num_bits)50 net_bloom_filter_create(uint32_t num_bits)
51 {
52 if (num_bits == 0) {
53 return NULL;
54 }
55
56 const size_t size = net_bloom_filter_get_size(num_bits);
57 struct net_bloom_filter *filter = (struct net_bloom_filter *)kalloc_data(size, Z_WAITOK | Z_ZERO);
58 if (filter == NULL) {
59 return NULL;
60 }
61
62 filter->b_table_num_bits = num_bits;
63 return filter;
64 }
65
66 void
net_bloom_filter_destroy(struct net_bloom_filter * filter)67 net_bloom_filter_destroy(struct net_bloom_filter *filter)
68 {
69 if (filter != NULL) {
70 uint8_t *filter_buffer = (uint8_t *)filter;
71 kfree_data(filter_buffer, net_bloom_filter_get_size(filter->b_table_num_bits));
72 }
73 }
74
75 static inline void
net_bloom_filter_insert_using_function(struct net_bloom_filter * filter,net_flowhash_fn_t * function,const void * __sized_by (length)buffer,uint32_t length)76 net_bloom_filter_insert_using_function(struct net_bloom_filter *filter,
77 net_flowhash_fn_t *function,
78 const void * __sized_by(length)buffer,
79 uint32_t length)
80 {
81 u_int32_t hash = (function(buffer, length, 0) % filter->b_table_num_bits);
82 u_int32_t index = hash / kNetBloomFilterBitsPerTableElement;
83 u_int32_t bit = hash % kNetBloomFilterBitsPerTableElement;
84 (filter->b_table[index]) |= (1ull << bit);
85 }
86
87 void
net_bloom_filter_insert(struct net_bloom_filter * filter,const void * __sized_by (length)buffer,uint32_t length)88 net_bloom_filter_insert(struct net_bloom_filter *filter,
89 const void * __sized_by(length)buffer,
90 uint32_t length)
91 {
92 net_bloom_filter_insert_using_function(filter, &net_flowhash_jhash, buffer, length);
93 net_bloom_filter_insert_using_function(filter, &net_flowhash_mh3_x86_32, buffer, length);
94 net_bloom_filter_insert_using_function(filter, &net_flowhash_mh3_x64_128, buffer, length);
95 }
96
97 static inline bool
net_bloom_filter_contains_using_function(struct net_bloom_filter * filter,net_flowhash_fn_t * function,const void * __sized_by (length)buffer,uint32_t length)98 net_bloom_filter_contains_using_function(struct net_bloom_filter *filter,
99 net_flowhash_fn_t *function,
100 const void * __sized_by(length)buffer,
101 uint32_t length)
102 {
103 u_int32_t hash = (function(buffer, length, 0) % filter->b_table_num_bits);
104 u_int32_t index = hash / kNetBloomFilterBitsPerTableElement;
105 u_int32_t bit = hash % kNetBloomFilterBitsPerTableElement;
106 return (filter->b_table[index]) & (1ull << bit);
107 }
108
109 bool
net_bloom_filter_contains(struct net_bloom_filter * filter,const void * __sized_by (length)buffer,uint32_t length)110 net_bloom_filter_contains(struct net_bloom_filter *filter,
111 const void * __sized_by(length)buffer,
112 uint32_t length)
113 {
114 return net_bloom_filter_contains_using_function(filter, &net_flowhash_jhash, buffer, length) &&
115 net_bloom_filter_contains_using_function(filter, &net_flowhash_mh3_x86_32, buffer, length) &&
116 net_bloom_filter_contains_using_function(filter, &net_flowhash_mh3_x64_128, buffer, length);
117 }
118