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