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
39size_t
40net_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
50struct net_bloom_filter *
51net_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
67void
68net_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
76static inline void
77net_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
88void
89net_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, function: &net_flowhash_jhash, buffer, length);
94 net_bloom_filter_insert_using_function(filter, function: &net_flowhash_mh3_x86_32, buffer, length);
95 net_bloom_filter_insert_using_function(filter, function: &net_flowhash_mh3_x64_128, buffer, length);
96}
97
98static inline bool
99net_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
110bool
111net_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, function: &net_flowhash_jhash, buffer, length) &&
116 net_bloom_filter_contains_using_function(filter, function: &net_flowhash_mh3_x86_32, buffer, length) &&
117 net_bloom_filter_contains_using_function(filter, function: &net_flowhash_mh3_x64_128, buffer, length);
118}
119