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