1 /*
2 * Bloom filter support
3 *
4 * Portions of this code are copyright (c) 2021 Cypress Semiconductor Corporation
5 *
6 * Copyright (C) 1999-2017, Broadcom Corporation
7 *
8 * Unless you and Broadcom execute a separate written software license
9 * agreement governing use of this software, this software is licensed to you
10 * under the terms of the GNU General Public License version 2 (the "GPL"),
11 * available at http://www.broadcom.com/licenses/GPLv2.php, with the
12 * following added to such license:
13 *
14 * As a special exception, the copyright holders of this software give you
15 * permission to link this software with independent modules, and to copy and
16 * distribute the resulting executable under terms of your choice, provided that
17 * you also meet, for each linked independent module, the terms and conditions of
18 * the license of that module. An independent module is a module which is not
19 * derived from this software. The special exception does not apply to any
20 * modifications of the software.
21 *
22 * Notwithstanding the above, under no circumstances may you combine this
23 * software in any way with any other Broadcom software provided under a license
24 * other than the GPL, without Broadcom's express prior written consent.
25 *
26 *
27 * <<Broadcom-WL-IPTag/Open:>>
28 *
29 * $Id$
30 */
31
32 #include <typedefs.h>
33 #include <bcmdefs.h>
34
35 #include <stdarg.h>
36
37 #ifdef BCMDRIVER
38 #include <osl.h>
39 #include <bcmutils.h>
40 #else /* !BCMDRIVER */
41 #include <stdio.h>
42 #include <string.h>
43 #ifndef ASSERT
44 #define ASSERT(exp)
45 #endif // endif
46 #endif /* !BCMDRIVER */
47 #include <bcmutils.h>
48
49 #include <bcmbloom.h>
50
51 #define BLOOM_BIT_LEN(_x) ((_x) << 3)
52
53 struct bcm_bloom_filter {
54 void *cb_ctx;
55 uint max_hash;
56 bcm_bloom_hash_t *hash; /* array of hash functions */
57 uint filter_size; /* in bytes */
58 uint8 *filter; /* can be NULL for validate only */
59 };
60
61 /* public interface */
62 int
bcm_bloom_create(bcm_bloom_alloc_t alloc_cb,bcm_bloom_free_t free_cb,void * cb_ctx,uint max_hash,uint filter_size,bcm_bloom_filter_t ** bloom)63 bcm_bloom_create(bcm_bloom_alloc_t alloc_cb,
64 bcm_bloom_free_t free_cb, void *cb_ctx, uint max_hash,
65 uint filter_size, bcm_bloom_filter_t **bloom)
66 {
67 int err = BCME_OK;
68 bcm_bloom_filter_t *bp = NULL;
69
70 if (!bloom || !alloc_cb || (max_hash == 0)) {
71 err = BCME_BADARG;
72 goto done;
73 }
74
75 bp = (*alloc_cb)(cb_ctx, sizeof(*bp));
76 if (!bp) {
77 err = BCME_NOMEM;
78 goto done;
79 }
80
81 memset(bp, 0, sizeof(*bp));
82 bp->cb_ctx = cb_ctx;
83 bp->max_hash = max_hash;
84 bp->hash = (*alloc_cb)(cb_ctx, sizeof(*bp->hash) * max_hash);
85 memset(bp->hash, 0, sizeof(*bp->hash) * max_hash);
86
87 if (!bp->hash) {
88 err = BCME_NOMEM;
89 goto done;
90 }
91
92 if (filter_size > 0) {
93 bp->filter = (*alloc_cb)(cb_ctx, filter_size);
94 if (!bp->filter) {
95 err = BCME_NOMEM;
96 goto done;
97 }
98 bp->filter_size = filter_size;
99 memset(bp->filter, 0, filter_size);
100 }
101
102 *bloom = bp;
103
104 done:
105 if (err != BCME_OK)
106 bcm_bloom_destroy(&bp, free_cb);
107
108 return err;
109 }
110
111 int
bcm_bloom_destroy(bcm_bloom_filter_t ** bloom,bcm_bloom_free_t free_cb)112 bcm_bloom_destroy(bcm_bloom_filter_t **bloom, bcm_bloom_free_t free_cb)
113 {
114 int err = BCME_OK;
115 bcm_bloom_filter_t *bp;
116
117 if (!bloom || !*bloom || !free_cb)
118 goto done;
119
120 bp = *bloom;
121 *bloom = NULL;
122
123 if (bp->filter)
124 (*free_cb)(bp->cb_ctx, bp->filter, bp->filter_size);
125 if (bp->hash)
126 (*free_cb)(bp->cb_ctx, bp->hash,
127 sizeof(*bp->hash) * bp->max_hash);
128 (*free_cb)(bp->cb_ctx, bp, sizeof(*bp));
129
130 done:
131 return err;
132 }
133
134 int
bcm_bloom_add_hash(bcm_bloom_filter_t * bp,bcm_bloom_hash_t hash,uint * idx)135 bcm_bloom_add_hash(bcm_bloom_filter_t *bp, bcm_bloom_hash_t hash, uint *idx)
136 {
137 uint i;
138
139 if (!bp || !hash || !idx)
140 return BCME_BADARG;
141
142 for (i = 0; i < bp->max_hash; ++i) {
143 if (bp->hash[i] == NULL)
144 break;
145 }
146
147 if (i >= bp->max_hash)
148 return BCME_NORESOURCE;
149
150 bp->hash[i] = hash;
151 *idx = i;
152 return BCME_OK;
153 }
154
155 int
bcm_bloom_remove_hash(bcm_bloom_filter_t * bp,uint idx)156 bcm_bloom_remove_hash(bcm_bloom_filter_t *bp, uint idx)
157 {
158 if (!bp)
159 return BCME_BADARG;
160
161 if (idx >= bp->max_hash)
162 return BCME_NOTFOUND;
163
164 bp->hash[idx] = NULL;
165 return BCME_OK;
166 }
167
168 bool
bcm_bloom_is_member(bcm_bloom_filter_t * bp,const uint8 * tag,uint tag_len,const uint8 * buf,uint buf_len)169 bcm_bloom_is_member(bcm_bloom_filter_t *bp,
170 const uint8 *tag, uint tag_len, const uint8 *buf, uint buf_len)
171 {
172 uint i;
173 int err = BCME_OK;
174
175 if (!tag || (tag_len == 0)) /* empty tag is always a member */
176 goto done;
177
178 /* use internal buffer if none was specified */
179 if (!buf || (buf_len == 0)) {
180 if (!bp->filter) /* every one is a member of empty filter */
181 goto done;
182
183 buf = bp->filter;
184 buf_len = bp->filter_size;
185 }
186
187 for (i = 0; i < bp->max_hash; ++i) {
188 uint pos;
189 if (!bp->hash[i])
190 continue;
191 pos = (*bp->hash[i])(bp->cb_ctx, i, tag, tag_len);
192
193 /* all bits must be set for a match */
194 CLANG_DIAGNOSTIC_PUSH_SUPPRESS_CAST()
195 if (isclr(buf, pos % BLOOM_BIT_LEN(buf_len))) {
196 CLANG_DIAGNOSTIC_POP()
197 err = BCME_NOTFOUND;
198 break;
199 }
200 }
201
202 done:
203 return err;
204 }
205
206 int
bcm_bloom_add_member(bcm_bloom_filter_t * bp,const uint8 * tag,uint tag_len)207 bcm_bloom_add_member(bcm_bloom_filter_t *bp, const uint8 *tag, uint tag_len)
208 {
209 uint i;
210
211 if (!bp || !tag || (tag_len == 0))
212 return BCME_BADARG;
213
214 if (!bp->filter) /* validate only */
215 return BCME_UNSUPPORTED;
216
217 for (i = 0; i < bp->max_hash; ++i) {
218 uint pos;
219 if (!bp->hash[i])
220 continue;
221 pos = (*bp->hash[i])(bp->cb_ctx, i, tag, tag_len);
222 setbit(bp->filter, pos % BLOOM_BIT_LEN(bp->filter_size));
223 }
224
225 return BCME_OK;
226 }
227
bcm_bloom_get_filter_data(bcm_bloom_filter_t * bp,uint buf_size,uint8 * buf,uint * buf_len)228 int bcm_bloom_get_filter_data(bcm_bloom_filter_t *bp,
229 uint buf_size, uint8 *buf, uint *buf_len)
230 {
231 if (!bp)
232 return BCME_BADARG;
233
234 if (buf_len)
235 *buf_len = bp->filter_size;
236
237 if (buf_size < bp->filter_size)
238 return BCME_BUFTOOSHORT;
239
240 if (bp->filter && bp->filter_size)
241 memcpy(buf, bp->filter, bp->filter_size);
242
243 return BCME_OK;
244 }
245