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