Branch data Line data Source code
1 : : // SPDX-License-Identifier: GPL-2.0-only
2 : : /*
3 : : * Copyright (c) 2023 Meta Platforms, Inc. and affiliates.
4 : : */
5 : :
6 : : #include "bpfilter/set.h"
7 : :
8 : : #include <errno.h>
9 : : #include <stdint.h>
10 : : #include <stdlib.h>
11 : : #include <string.h>
12 : : #include <time.h>
13 : :
14 : : #include "bpfilter/core/hashset.h"
15 : : #include "bpfilter/dump.h"
16 : : #include "bpfilter/helper.h"
17 : : #include "bpfilter/logger.h"
18 : : #include "bpfilter/pack.h"
19 : :
20 : : /// Mask value of matcher types supporting LPM trie maps.
21 : : #define _BF_SET_USE_TRIE_MASK \
22 : : (BF_FLAGS(BF_MATCHER_IP4_SNET, BF_MATCHER_IP4_DNET, BF_MATCHER_IP6_SNET, \
23 : : BF_MATCHER_IP6_DNET))
24 : :
25 : 3626 : static uint64_t _bf_set_elem_hash(const void *data, void *ctx)
26 : : {
27 : 3626 : return bf_fnv1a(data, *(const size_t *)ctx, bf_fnv1a_init());
28 : : }
29 : :
30 : 179 : static bool _bf_set_elem_equal(const void *lhs, const void *rhs, void *ctx)
31 : : {
32 : 179 : return memcmp(lhs, rhs, *(const size_t *)ctx) == 0;
33 : : }
34 : :
35 : 3584 : static void _bf_set_elem_free(void **data, void *ctx)
36 : : {
37 : : (void)ctx;
38 : : freep((void *)data);
39 : 3584 : }
40 : :
41 : : static const bf_hashset_ops _bf_set_elem_ops = {
42 : : .hash = _bf_set_elem_hash,
43 : : .equal = _bf_set_elem_equal,
44 : : .free = _bf_set_elem_free,
45 : : };
46 : :
47 : 1823 : int bf_set_new(struct bf_set **set, const char *name, enum bf_matcher_type *key,
48 : : size_t n_comps)
49 : : {
50 : 1823 : _free_bf_set_ struct bf_set *_set = NULL;
51 : : uint64_t mask = 0;
52 : :
53 : : assert(set);
54 : : assert(key);
55 : :
56 [ + + ]: 1823 : if (n_comps == 0)
57 [ + - ]: 1 : return bf_err_r(-EINVAL, "at least 1 key component is required");
58 : :
59 [ + + ]: 1822 : if (n_comps > BF_SET_MAX_N_COMPS) {
60 [ + - ]: 1 : return bf_err_r(-E2BIG,
61 : : "a set key can't contain more than %d components",
62 : : BF_SET_MAX_N_COMPS);
63 : : }
64 : :
65 : 1821 : _set = calloc(1, sizeof(*_set));
66 [ - + ]: 1821 : if (!_set)
67 : : return -ENOMEM;
68 : :
69 : 1821 : _set->name = NULL;
70 [ + + ]: 1821 : if (name) {
71 : 221 : _set->name = strdup(name);
72 [ - + ]: 221 : if (!_set->name)
73 [ # # ]: 0 : return bf_err_r(-ENOMEM, "failed to allocate memory for set name");
74 : : }
75 : :
76 : 1821 : memcpy(&(_set)->key, key, n_comps * sizeof(enum bf_matcher_type));
77 : 1821 : _set->n_comps = n_comps;
78 : 1821 : _set->elem_size = 0;
79 : 1821 : bf_hashset_init(&_set->elems, &_bf_set_elem_ops, &_set->elem_size);
80 : :
81 [ + + ]: 3771 : for (size_t i = 0; i < n_comps; ++i) {
82 : : const struct bf_matcher_ops *ops;
83 : :
84 : 1950 : ops = bf_matcher_get_ops(_set->key[i], BF_MATCHER_IN);
85 [ - + ]: 1950 : if (!ops) {
86 [ # # ]: 0 : return bf_err_r(-ENOTSUP,
87 : : "matcher '%s' (%d) is not supported as a set key",
88 : : bf_matcher_type_to_str(_set->key[i]), _set->key[i]);
89 : : }
90 : 1950 : _set->elem_size += ops->ref_payload_size;
91 : :
92 : 1950 : mask |= BF_FLAG(_set->key[i]);
93 : : }
94 : :
95 [ + + + + ]: 1821 : _set->use_trie = n_comps == 1 && mask & _BF_SET_USE_TRIE_MASK;
96 : :
97 [ + + + + ]: 1821 : if (n_comps > 1 && mask & _BF_SET_USE_TRIE_MASK) {
98 [ + - ]: 3 : return bf_err_r(
99 : : -EINVAL,
100 : : "network matchers can't be used in combination with other matchers in a set");
101 : : }
102 : :
103 : 1818 : *set = TAKE_PTR(_set);
104 : :
105 : 1818 : return 0;
106 : : }
107 : :
108 : : /**
109 : : * @brief Parse a set's raw key into an array of `bf_matcher_type`.
110 : : *
111 : : * @param raw_key Raw set key, as a string of comma-separated matcher types
112 : : * enclosed in parentheses. Can't be NULL.
113 : : * @param key Set key, parsed from `raw_key`. Can't be NULL.
114 : : * @param n_comps Number of components in `key`. Can't be NULL.
115 : : * @return 0 on success, or a negative error value on failure.
116 : : */
117 : 213 : static int _bf_set_parse_key(const char *raw_key, enum bf_matcher_type *key,
118 : : size_t *n_comps)
119 : : {
120 : : _cleanup_free_ char *_raw_key = NULL;
121 : : char *tmp, *saveptr, *token;
122 : :
123 : : assert(raw_key);
124 : : assert(key);
125 : : assert(n_comps);
126 : :
127 : 213 : _raw_key = strdup(raw_key);
128 [ - + ]: 213 : if (!_raw_key) {
129 [ # # ]: 0 : return bf_err_r(-ENOMEM, "failed to duplicate set raw key '%s'",
130 : : raw_key);
131 : : }
132 : :
133 : 213 : *n_comps = 0;
134 : :
135 : : tmp = _raw_key;
136 [ + + ]: 488 : while ((token = strtok_r(tmp, "(),", &saveptr))) {
137 : : int r;
138 : :
139 [ - + ]: 277 : if (*n_comps == BF_SET_MAX_N_COMPS) {
140 [ # # ]: 0 : return bf_err_r(-E2BIG, "set keys are limited to %d components",
141 : : BF_SET_MAX_N_COMPS);
142 : : }
143 : :
144 : 277 : token = bf_trim(token);
145 : :
146 : 277 : r = bf_matcher_type_from_str(token, &key[*n_comps]);
147 [ + + ]: 277 : if (r)
148 [ + - ]: 2 : return bf_err_r(r, "failed to parse set key component '%s'", token);
149 : :
150 : : tmp = NULL;
151 : 275 : ++*n_comps;
152 : : }
153 : :
154 [ + + ]: 211 : if (!*n_comps)
155 [ + - ]: 1 : return bf_err_r(-EINVAL, "set key can't have no component");
156 : :
157 : : return 0;
158 : : }
159 : :
160 : 358 : int bf_set_add_elem_raw(struct bf_set *set, const char *raw_elem)
161 : : {
162 : 358 : _cleanup_free_ void *elem = NULL;
163 : : _cleanup_free_ char *_raw_elem = NULL;
164 : : char *tmp, *saveptr, *token;
165 : : size_t elem_offset = 0;
166 : : size_t comp_idx = 0;
167 : : int r;
168 : :
169 : : assert(set);
170 : : assert(raw_elem);
171 : :
172 : 358 : _raw_elem = strdup(raw_elem);
173 [ - + ]: 358 : if (!_raw_elem) {
174 [ # # ]: 0 : return bf_err_r(-ENOMEM,
175 : : "failed to create a copy of the raw element '%s'",
176 : : raw_elem);
177 : : }
178 : :
179 : 358 : elem = malloc(set->elem_size);
180 [ - + ]: 358 : if (!elem)
181 [ # # ]: 0 : return bf_err_r(-ENOMEM, "failed to allocate a new set element");
182 : :
183 : : tmp = _raw_elem;
184 [ + + ]: 799 : while ((token = strtok_r(tmp, ",", &saveptr))) {
185 : : const struct bf_matcher_ops *ops;
186 : :
187 [ + + ]: 446 : if (comp_idx >= set->n_comps) {
188 [ + - ]: 2 : return bf_err_r(
189 : : -EINVAL,
190 : : "set element has more components than defined in the key '%s'",
191 : : token);
192 : : }
193 : :
194 : 444 : token = bf_trim(token);
195 : :
196 : 444 : ops = bf_matcher_get_ops(set->key[comp_idx], BF_MATCHER_IN);
197 [ - + ]: 444 : if (!ops) {
198 [ # # ]: 0 : return bf_err_r(-EINVAL, "matcher type '%s' has no matcher_ops",
199 : : bf_matcher_type_to_str(set->key[comp_idx]));
200 : : }
201 : :
202 : 444 : r = ops->parse(set->key[comp_idx], BF_MATCHER_IN, elem + elem_offset,
203 : : token);
204 [ + + ]: 444 : if (r) {
205 [ + - ]: 3 : return bf_err_r(r, "failed to parse set element component '%s'",
206 : : token);
207 : : }
208 : :
209 : 441 : elem_offset += ops->ref_payload_size;
210 : : tmp = NULL;
211 : 441 : ++comp_idx;
212 : : }
213 : :
214 [ + + ]: 353 : if (comp_idx != set->n_comps) {
215 [ + - ]: 3 : return bf_err_r(-EINVAL, "missing component in set element '%s'",
216 : : raw_elem);
217 : : }
218 : :
219 : 350 : r = bf_hashset_add(&set->elems, &elem);
220 [ + - ]: 350 : if (r == -EEXIST)
221 : : return 0;
222 [ - + ]: 350 : if (r)
223 [ # # ]: 0 : return bf_err_r(r, "failed to insert element into set");
224 : :
225 : : return 0;
226 : : }
227 : :
228 : 213 : int bf_set_new_from_raw(struct bf_set **set, const char *name,
229 : : const char *raw_key, const char *raw_payload)
230 : : {
231 : 213 : _free_bf_set_ struct bf_set *_set = NULL;
232 : : _cleanup_free_ char *_raw_payload = NULL;
233 : : enum bf_matcher_type key[BF_SET_MAX_N_COMPS];
234 : : char *raw_elem, *tmp, *saveptr;
235 : : size_t n_comps;
236 : : int r;
237 : :
238 : : assert(set);
239 : : assert(raw_key);
240 : : assert(raw_payload);
241 : :
242 : 213 : r = _bf_set_parse_key(raw_key, key, &n_comps);
243 [ + + ]: 213 : if (r)
244 [ + - ]: 3 : return bf_err_r(r, "failed to parse set key '%s'", raw_key);
245 : :
246 : 210 : r = bf_set_new(&_set, name, key, n_comps);
247 [ + + ]: 210 : if (r)
248 : : return r;
249 : :
250 : 208 : _raw_payload = strdup(raw_payload);
251 [ - + ]: 208 : if (!_raw_payload)
252 [ # # ]: 0 : return bf_err_r(-ENOMEM, "failed to copy set raw payload '%s'",
253 : : raw_payload);
254 : :
255 : : tmp = _raw_payload;
256 [ + + ]: 598 : while ((raw_elem = strtok_r(tmp, "{};\n", &saveptr))) {
257 : 397 : raw_elem = bf_trim(raw_elem);
258 : :
259 : : /* While strtok_r() won't return empty token, the trimmed version of the
260 : : * token can be empty! */
261 [ + + ]: 397 : if (raw_elem[0] == '\0')
262 : 54 : continue;
263 : :
264 : 343 : r = bf_set_add_elem_raw(_set, raw_elem);
265 [ + + ]: 343 : if (r)
266 [ + - ]: 7 : return bf_err_r(r, "failed to parse set element '%s'", raw_elem);
267 : :
268 : : tmp = NULL;
269 : : }
270 : :
271 : 201 : *set = TAKE_PTR(_set);
272 : :
273 : 201 : return 0;
274 : : }
275 : :
276 : 1355 : int bf_set_new_from_pack(struct bf_set **set, bf_rpack_node_t node)
277 : : {
278 : 1355 : _free_bf_set_ struct bf_set *_set = NULL;
279 : 1355 : _cleanup_free_ char *name = NULL;
280 : : bf_rpack_node_t child, comp_node, elem_node;
281 : : size_t n_comps = 0;
282 : : enum bf_matcher_type key[BF_SET_MAX_N_COMPS];
283 : : int r;
284 : :
285 : : assert(set);
286 : :
287 : 1355 : r = bf_rpack_kv_node(node, "name", &child);
288 [ - + ]: 1355 : if (r)
289 [ # # ]: 0 : return bf_rpack_key_err(r, "bf_set.name");
290 [ + + ]: 1355 : if (!bf_rpack_is_nil(child)) {
291 : 115 : r = bf_rpack_str(child, &name);
292 [ - + ]: 115 : if (r)
293 [ # # ]: 0 : return bf_err_r(r, "failed to read set name from bf_set.name pack");
294 : : }
295 : :
296 : 1355 : r = bf_rpack_kv_array(node, "key", &child);
297 [ - + ]: 1355 : if (r)
298 [ # # ]: 0 : return bf_rpack_key_err(r, "bf_set.key");
299 [ + - + + : 5494 : bf_rpack_array_foreach (child, comp_node) {
+ + ]
300 : 1392 : ++n_comps;
301 [ - + ]: 1392 : if (n_comps > BF_SET_MAX_N_COMPS) {
302 [ # # ]: 0 : return bf_err_r(
303 : : -E2BIG,
304 : : "bf_set.key in pack contains %lu key components, only %d allowed",
305 : : n_comps, BF_SET_MAX_N_COMPS);
306 : : }
307 : :
308 [ - + - + : 1392 : r = bf_rpack_enum(comp_node, &key[i], 0, _BF_MATCHER_TYPE_MAX);
- - ]
309 : : if (r)
310 [ # # ]: 0 : return bf_rpack_key_err(r, "bf_set.key");
311 : : }
312 : :
313 : 1355 : r = bf_set_new(&_set, name, key, n_comps);
314 [ - + ]: 1355 : if (r)
315 [ # # ]: 0 : return bf_err_r(r, "failed to create bf_set from pack");
316 : :
317 : 1355 : r = bf_rpack_kv_array(node, "elements", &child);
318 [ - + ]: 1355 : if (r)
319 [ # # ]: 0 : return bf_rpack_key_err(r, "bf_set.elements");
320 [ + + + + : 8124 : bf_rpack_array_foreach (child, elem_node) {
+ + ]
321 : : const void *elem;
322 : : size_t elem_len;
323 : :
324 : 2707 : r = bf_rpack_bin(elem_node, &elem, &elem_len);
325 [ - + ]: 2707 : if (r)
326 [ # # ]: 0 : return bf_rpack_key_err(r, "bf_set.elements");
327 : :
328 [ - + ]: 2707 : if (elem_len != _set->elem_size) {
329 [ # # ]: 0 : return bf_err_r(-EINVAL,
330 : : "bf_set pack element is %lu bytes, it must be %lu",
331 : : elem_len, _set->elem_size);
332 : : }
333 : :
334 : 2707 : r = bf_set_add_elem(_set, elem);
335 [ - + ]: 2707 : if (r)
336 [ # # ]: 0 : return bf_err_r(r, "failed to insert element to bf_set");
337 : : }
338 : :
339 : 1355 : *set = TAKE_PTR(_set);
340 : :
341 : 1355 : return 0;
342 : : }
343 : :
344 : 6779 : void bf_set_free(struct bf_set **set)
345 : : {
346 : : assert(set);
347 : :
348 [ + + ]: 6779 : if (!*set)
349 : : return;
350 : :
351 : 1821 : bf_hashset_clean(&(*set)->elems);
352 : 1821 : freep((void *)&(*set)->name);
353 : : freep((void *)set);
354 : : }
355 : :
356 : 665 : int bf_set_pack(const struct bf_set *set, bf_wpack_t *pack)
357 : : {
358 : : assert(set);
359 : : assert(pack);
360 : :
361 [ + + ]: 665 : if (set->name)
362 : : bf_wpack_kv_str(pack, "name", set->name);
363 : : else
364 : : bf_wpack_kv_nil(pack, "name");
365 : :
366 : 665 : bf_wpack_open_array(pack, "key");
367 [ + + ]: 1389 : for (size_t i = 0; i < set->n_comps; ++i)
368 : 724 : bf_wpack_enum(pack, set->key[i]);
369 : 665 : bf_wpack_close_array(pack);
370 : :
371 : 665 : bf_wpack_open_array(pack, "elements");
372 [ + + + + : 4050 : bf_hashset_foreach (&set->elems, elem)
+ + ]
373 : 1360 : bf_wpack_bin(pack, elem->data, set->elem_size);
374 : 665 : bf_wpack_close_array(pack);
375 : :
376 [ - + ]: 665 : return bf_wpack_is_valid(pack) ? 0 : -EINVAL;
377 : : }
378 : :
379 : 5 : void bf_set_dump(const struct bf_set *set, prefix_t *prefix)
380 : : {
381 : : size_t dump_idx = 0;
382 : :
383 : : assert(set);
384 : : assert(prefix);
385 : :
386 [ - + ]: 5 : DUMP(prefix, "struct bf_set at %p", set);
387 : 5 : bf_dump_prefix_push(prefix);
388 : :
389 [ - + - - ]: 5 : DUMP(prefix, "name: %s", set->name ?: "<anonymous>");
390 [ - + ]: 5 : DUMP(prefix, "key: bf_matcher_type[%zu]", set->n_comps);
391 : 5 : bf_dump_prefix_push(prefix);
392 [ + + ]: 14 : for (size_t i = 0; i < set->n_comps; ++i) {
393 [ + + ]: 9 : if (i == set->n_comps - 1)
394 : 5 : bf_dump_prefix_last(prefix);
395 : :
396 [ - + ]: 9 : DUMP(prefix, "%s", bf_matcher_type_to_str(set->key[i]));
397 : : }
398 : 5 : bf_dump_prefix_pop(prefix);
399 : :
400 [ - + ]: 5 : DUMP(prefix, "elem_size: %lu", set->elem_size);
401 [ - + ]: 5 : DUMP(bf_dump_prefix_last(prefix), "elems: bf_hashset<bytes>[%lu]",
402 : : bf_hashset_size(&set->elems));
403 : :
404 : 5 : bf_dump_prefix_push(prefix);
405 [ + + + + : 42 : bf_hashset_foreach (&set->elems, elem) {
+ + ]
406 [ + + ]: 16 : if (++dump_idx == bf_hashset_size(&set->elems))
407 : 4 : bf_dump_prefix_last(prefix);
408 : :
409 [ - + ]: 16 : DUMP(prefix, "void * @ %p", elem->data);
410 : 16 : bf_dump_prefix_push(prefix);
411 : 16 : bf_dump_hex(prefix, elem->data, set->elem_size);
412 : 16 : bf_dump_prefix_pop(prefix);
413 : : }
414 : 5 : bf_dump_prefix_pop(prefix);
415 : :
416 : 5 : bf_dump_prefix_pop(prefix);
417 : 5 : }
418 : :
419 : 3237 : int bf_set_add_elem(struct bf_set *set, const void *elem)
420 : : {
421 : : _cleanup_free_ void *_elem = NULL;
422 : : int r;
423 : :
424 : : assert(set);
425 : : assert(elem);
426 : :
427 : 3237 : _elem = malloc(set->elem_size);
428 [ + - ]: 3237 : if (!_elem)
429 : : return -ENOMEM;
430 : :
431 : 3237 : memcpy(_elem, elem, set->elem_size);
432 : :
433 : 3237 : r = bf_hashset_add(&set->elems, &_elem);
434 [ + + ]: 3237 : if (r == -EEXIST)
435 : 1 : return 0;
436 : : if (r)
437 : : return r;
438 : :
439 : : return 0;
440 : : }
441 : :
442 : 1703 : bool bf_set_is_empty(const struct bf_set *set)
443 : : {
444 : : assert(set);
445 : :
446 : 1703 : return bf_hashset_is_empty(&set->elems);
447 : : }
448 : :
449 : 1 : int bf_set_reserve(struct bf_set *set, size_t count)
450 : : {
451 : : assert(set);
452 : :
453 : 1 : return bf_hashset_reserve(&set->elems, count);
454 : : }
455 : :
456 : 139 : bool bf_set_same_key(const struct bf_set *lhs, const struct bf_set *rhs)
457 : : {
458 : : assert(lhs);
459 : : assert(rhs);
460 : :
461 [ + + ]: 139 : if (lhs->n_comps != rhs->n_comps)
462 : : return false;
463 : :
464 : 97 : return memcmp(lhs->key, rhs->key,
465 : 97 : lhs->n_comps * sizeof(enum bf_matcher_type)) == 0;
466 : : }
467 : :
468 : 11 : int bf_set_add_many(struct bf_set *dest, struct bf_set **to_add)
469 : : {
470 : : int r;
471 : :
472 : : assert(dest);
473 : : assert(to_add);
474 : : assert(*to_add);
475 : :
476 [ + + ]: 11 : if (!bf_set_same_key(dest, *to_add))
477 [ + - ]: 2 : return bf_err_r(-EINVAL, "set key format mismatch");
478 : :
479 [ + + + + : 42 : bf_hashset_foreach (&(*to_add)->elems, elem) {
+ + ]
480 : 12 : _cleanup_free_ void *data = NULL;
481 : :
482 : 12 : r = bf_hashset_take(&(*to_add)->elems, elem->data, &data);
483 [ - + ]: 12 : if (r)
484 [ # # ]: 0 : return bf_err_r(r, "failed to take element from source set");
485 : :
486 : 12 : r = bf_hashset_add(&dest->elems, &data);
487 [ + + ]: 12 : if (r == -EEXIST)
488 : : continue;
489 [ - + ]: 10 : if (r)
490 [ # # ]: 0 : return bf_err_r(r, "failed to add element to set");
491 : : }
492 : :
493 : 9 : bf_set_free(to_add);
494 : :
495 : 9 : return 0;
496 : : }
497 : :
498 : 12 : int bf_set_remove_many(struct bf_set *dest, struct bf_set **to_remove)
499 : : {
500 : : int r;
501 : :
502 : : assert(dest);
503 : : assert(to_remove);
504 : : assert(*to_remove);
505 : :
506 [ + + ]: 12 : if (!bf_set_same_key(dest, *to_remove))
507 [ + - ]: 2 : return bf_err_r(-EINVAL, "set key format mismatch");
508 : :
509 [ + + + + : 34 : bf_hashset_foreach (&(*to_remove)->elems, elem) {
+ + ]
510 : 7 : r = bf_hashset_delete(&dest->elems, elem->data);
511 [ - + ]: 7 : if (r && r != -ENOENT)
512 [ # # ]: 0 : return bf_err_r(r, "failed to remove element from set");
513 : : }
514 : :
515 : 10 : bf_set_free(to_remove);
516 : :
517 : 10 : return 0;
518 : : }
|
