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 |
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 * |
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 |
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 |
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 |
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, 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 | |
98 | static inline bool |
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 |
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, 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 | |