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