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 : 226 : int bf_set_new(struct bf_set **set, const char *name, enum bf_matcher_type *key,
26 : : size_t n_comps)
27 : : {
28 : : bf_assert(set && key);
29 : :
30 : 226 : _free_bf_set_ struct bf_set *_set = NULL;
31 : : uint32_t mask = 0;
32 : :
33 : : bf_static_assert(_BF_MATCHER_TYPE_MAX < 8 * sizeof(uint32_t),
34 : : "matcher type bitmask won't fit in 32 bits");
35 : :
36 [ + + ]: 226 : if (n_comps == 0)
37 [ + - ]: 1 : return bf_err_r(-EINVAL, "at least 1 key component is required");
38 : :
39 [ + + ]: 225 : if (n_comps > BF_SET_MAX_N_COMPS) {
40 [ + - ]: 1 : return bf_err_r(-E2BIG,
41 : : "a set key can't contain more than %d components",
42 : : BF_SET_MAX_N_COMPS);
43 : : }
44 : :
45 : 224 : _set = malloc(sizeof(*_set));
46 [ - + ]: 224 : if (!_set)
47 : : return -ENOMEM;
48 : :
49 : 224 : _set->name = NULL;
50 [ + + ]: 224 : if (name) {
51 : 45 : _set->name = strdup(name);
52 [ - + ]: 45 : if (!_set->name)
53 [ # # ]: 0 : return bf_err_r(-ENOMEM, "failed to allocate memory for set name");
54 : : }
55 : :
56 : 224 : memcpy(&(_set)->key, key, n_comps * sizeof(enum bf_matcher_type));
57 : 224 : _set->n_comps = n_comps;
58 : 224 : _set->elem_size = 0;
59 : 224 : _set->elems = bf_list_default(freep, NULL);
60 : :
61 [ + + ]: 536 : for (size_t i = 0; i < n_comps; ++i) {
62 : : const struct bf_matcher_ops *ops;
63 : :
64 : 312 : ops = bf_matcher_get_ops(_set->key[i], BF_MATCHER_IN);
65 [ - + ]: 312 : if (!ops) {
66 [ # # ]: 0 : return bf_err_r(-ENOTSUP,
67 : : "matcher '%s' (%d) is not supported as a set key",
68 : : bf_matcher_type_to_str(_set->key[i]), _set->key[i]);
69 : : }
70 : 312 : _set->elem_size += ops->ref_payload_size;
71 : :
72 : 312 : mask |= BF_FLAG(_set->key[i]);
73 : : }
74 : :
75 [ + + + + ]: 224 : _set->use_trie = n_comps == 1 && mask & _BF_SET_USE_TRIE_MASK;
76 : :
77 [ + + + + ]: 224 : if (n_comps > 1 && mask & _BF_SET_USE_TRIE_MASK) {
78 [ + - ]: 3 : return bf_err_r(
79 : : -EINVAL,
80 : : "network matchers can't be used in combination with other matchers in a set");
81 : : }
82 : :
83 : 221 : *set = TAKE_PTR(_set);
84 : :
85 : 221 : return 0;
86 : : }
87 : :
88 : : /**
89 : : * @brief Parse a set's raw key into an array of `bf_matcher_type`.
90 : : *
91 : : * @param raw_key Raw set key, as a string of comma-separated matcher types
92 : : * enclosed in parentheses. Can't be NULL.
93 : : * @param key Set key, parsed from `raw_key`. Can't be NULL.
94 : : * @param n_comps Number of components in `key`. Can't be NULL.
95 : : * @return 0 on success, or a negative error value on failure.
96 : : */
97 : 128 : static int _bf_set_parse_key(const char *raw_key, enum bf_matcher_type *key,
98 : : size_t *n_comps)
99 : : {
100 : : bf_assert(raw_key && key && n_comps);
101 : :
102 : : _cleanup_free_ char *_raw_key = NULL;
103 : : char *tmp, *saveptr, *token;
104 : :
105 : 128 : _raw_key = strdup(raw_key);
106 [ - + ]: 128 : if (!_raw_key) {
107 [ # # ]: 0 : return bf_err_r(-ENOMEM, "failed to duplicate set raw key '%s'",
108 : : raw_key);
109 : : }
110 : :
111 : 128 : *n_comps = 0;
112 : :
113 : : tmp = _raw_key;
114 [ + + ]: 310 : while ((token = strtok_r(tmp, "(),", &saveptr))) {
115 : : int r;
116 : :
117 [ - + ]: 184 : 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 : 184 : token = bf_trim(token);
123 : :
124 : 184 : r = bf_matcher_type_from_str(token, &key[*n_comps]);
125 [ + + ]: 184 : if (r)
126 [ + - ]: 2 : return bf_err_r(r, "failed to parse set key component '%s'", token);
127 : :
128 : : tmp = NULL;
129 : 182 : ++*n_comps;
130 : : }
131 : :
132 [ + + ]: 126 : if (!*n_comps)
133 [ + - ]: 1 : return bf_err_r(-EINVAL, "set key can't have no component");
134 : :
135 : : return 0;
136 : : }
137 : :
138 : : /**
139 : : * @brief Parse a raw element and insert it into a set.
140 : : *
141 : : * The element is parsed according to `set->key`.
142 : : *
143 : : * @param set Set to parse the element for. Can't be NULL.
144 : : * @param raw_elem Raw element to parse. Can't be NULL.
145 : : * @return 0 on success, or a negative error value on failure.
146 : : */
147 : 259 : static int _bf_set_parse_elem(struct bf_set *set, const char *raw_elem)
148 : : {
149 : : bf_assert(set && raw_elem);
150 : :
151 : : _cleanup_free_ void *elem = NULL;
152 : : _cleanup_free_ char *_raw_elem = NULL;
153 : : char *tmp, *saveptr, *token;
154 : : size_t elem_offset = 0;
155 : : size_t comp_idx = 0;
156 : : int r;
157 : :
158 : 259 : _raw_elem = strdup(raw_elem);
159 [ - + ]: 259 : if (!_raw_elem) {
160 [ # # ]: 0 : return bf_err_r(-ENOMEM,
161 : : "failed to create a copy of the raw element '%s'",
162 : : raw_elem);
163 : : }
164 : :
165 : 259 : elem = malloc(set->elem_size);
166 [ - + ]: 259 : if (!elem)
167 [ # # ]: 0 : return bf_err_r(-ENOMEM, "failed to allocate a new set element");
168 : :
169 : : tmp = _raw_elem;
170 [ + + ]: 590 : while ((token = strtok_r(tmp, ",", &saveptr))) {
171 : : const struct bf_matcher_ops *ops;
172 : :
173 [ + + ]: 335 : if (comp_idx >= set->n_comps) {
174 [ + - ]: 1 : return bf_err_r(
175 : : -EINVAL,
176 : : "set element has more components than defined in the key '%s'",
177 : : token);
178 : : }
179 : :
180 : 334 : token = bf_trim(token);
181 : :
182 : 334 : ops = bf_matcher_get_ops(set->key[comp_idx], BF_MATCHER_IN);
183 [ - + ]: 334 : if (!ops) {
184 [ # # ]: 0 : return bf_err_r(-EINVAL, "matcher type '%s' has no matcher_ops",
185 : : bf_matcher_type_to_str(set->key[comp_idx]));
186 : : }
187 : :
188 : 334 : r = ops->parse(set->key[comp_idx], BF_MATCHER_IN, elem + elem_offset,
189 : : token);
190 [ + + ]: 334 : if (r) {
191 [ + - ]: 3 : return bf_err_r(r, "failed to parse set element component '%s'",
192 : : token);
193 : : }
194 : :
195 : 331 : elem_offset += ops->ref_payload_size;
196 : : tmp = NULL;
197 : 331 : ++comp_idx;
198 : : }
199 : :
200 [ + + ]: 255 : if (comp_idx != set->n_comps) {
201 [ + - ]: 3 : return bf_err_r(-EINVAL, "missing component in set element '%s'",
202 : : raw_elem);
203 : : }
204 : :
205 : 252 : r = bf_list_add_tail(&set->elems, elem);
206 [ - + ]: 252 : if (r)
207 [ # # ]: 0 : return bf_err_r(r, "failed to insert element into set");
208 : : TAKE_PTR(elem);
209 : :
210 : : return 0;
211 : : }
212 : :
213 : 128 : int bf_set_new_from_raw(struct bf_set **set, const char *name,
214 : : const char *raw_key, const char *raw_payload)
215 : : {
216 : : bf_assert(set && raw_key && raw_payload);
217 : :
218 : 128 : _free_bf_set_ struct bf_set *_set = NULL;
219 : : _cleanup_free_ char *_raw_payload = NULL;
220 : : enum bf_matcher_type key[BF_SET_MAX_N_COMPS];
221 : : char *raw_elem, *tmp, *saveptr;
222 : : size_t n_comps;
223 : : int r;
224 : :
225 : : bf_assert(raw_key);
226 : : bf_assert(raw_payload);
227 : :
228 : 128 : r = _bf_set_parse_key(raw_key, key, &n_comps);
229 [ + + ]: 128 : if (r)
230 [ + - ]: 3 : return bf_err_r(r, "failed to parse set key '%s'", raw_key);
231 : :
232 : 125 : r = bf_set_new(&_set, name, key, n_comps);
233 [ + + ]: 125 : if (r)
234 : : return r;
235 : :
236 : 123 : _raw_payload = strdup(raw_payload);
237 [ - + ]: 123 : if (!_raw_payload)
238 [ # # ]: 0 : return bf_err_r(-ENOMEM, "failed to copy set raw payload '%s'",
239 : : raw_payload);
240 : :
241 : : tmp = _raw_payload;
242 [ + + ]: 417 : while ((raw_elem = strtok_r(tmp, "{};\n", &saveptr))) {
243 : 301 : raw_elem = bf_trim(raw_elem);
244 : :
245 : : /* While strtok_r() won't return empty token, the trimmed version of the
246 : : * token can be empty! */
247 [ + + ]: 301 : if (raw_elem[0] == '\0')
248 : 42 : continue;
249 : :
250 : 259 : r = _bf_set_parse_elem(_set, raw_elem);
251 [ + + ]: 259 : if (r)
252 [ + - ]: 7 : return bf_err_r(r, "failed to parse set element '%s'", raw_elem);
253 : :
254 : : tmp = NULL;
255 : : }
256 : :
257 : 116 : *set = TAKE_PTR(_set);
258 : :
259 : 116 : return 0;
260 : : }
261 : :
262 : 82 : int bf_set_new_from_pack(struct bf_set **set, bf_rpack_node_t node)
263 : : {
264 : 82 : _free_bf_set_ struct bf_set *_set = NULL;
265 : 82 : _cleanup_free_ char *name = NULL;
266 : : bf_rpack_node_t child, comp_node, elem_node;
267 : : size_t n_comps = 0;
268 : : enum bf_matcher_type key[BF_SET_MAX_N_COMPS];
269 : : int r;
270 : :
271 : : bf_assert(set);
272 : :
273 : 82 : r = bf_rpack_kv_node(node, "name", &child);
274 [ - + ]: 82 : if (r)
275 [ # # ]: 0 : return bf_rpack_key_err(r, "bf_set.name");
276 [ + + ]: 82 : if (!bf_rpack_is_nil(child)) {
277 : 12 : r = bf_rpack_str(child, &name);
278 [ - + ]: 12 : if (r)
279 [ # # ]: 0 : return bf_err_r(r, "failed to read set name from bf_set.name pack");
280 : : }
281 : :
282 : 82 : r = bf_rpack_kv_array(node, "key", &child);
283 [ - + ]: 82 : if (r)
284 [ # # ]: 0 : return bf_rpack_key_err(r, "bf_set.key");
285 [ + - + + : 370 : bf_rpack_array_foreach (child, comp_node) {
+ + ]
286 : 103 : ++n_comps;
287 [ - + ]: 103 : if (n_comps > BF_SET_MAX_N_COMPS) {
288 [ # # ]: 0 : return bf_err_r(
289 : : -E2BIG,
290 : : "bf_set.key in pack contains %lu key components, only %d allowed",
291 : : n_comps, BF_SET_MAX_N_COMPS);
292 : : }
293 : :
294 [ - + ]: 103 : r = bf_rpack_enum(comp_node, &key[i]);
295 : : if (r)
296 [ # # ]: 0 : return bf_rpack_key_err(r, "bf_set.key");
297 : : }
298 : :
299 : 82 : r = bf_set_new(&_set, name, key, n_comps);
300 [ - + ]: 82 : if (r)
301 [ # # ]: 0 : return bf_err_r(r, "failed to create bf_set from pack");
302 : :
303 : 82 : r = bf_rpack_kv_array(node, "elements", &child);
304 [ - + ]: 82 : if (r)
305 [ # # ]: 0 : return bf_rpack_key_err(r, "bf_set.elements");
306 [ + + + + : 592 : bf_rpack_array_foreach (child, elem_node) {
+ + ]
307 : : const void *elem;
308 : : size_t elem_len;
309 : :
310 : 214 : r = bf_rpack_bin(elem_node, &elem, &elem_len);
311 [ - + ]: 214 : if (r)
312 [ # # ]: 0 : return bf_rpack_key_err(r, "bf_set.elements");
313 : :
314 [ - + ]: 214 : if (elem_len != _set->elem_size) {
315 [ # # ]: 0 : return bf_err_r(-EINVAL,
316 : : "bf_set pack element is %lu bytes, it must be %lu",
317 : : elem_len, _set->elem_size);
318 : : }
319 : :
320 : 214 : r = bf_set_add_elem(_set, elem);
321 [ - + ]: 214 : if (r)
322 [ # # ]: 0 : return bf_err_r(r, "failed to insert element to bf_set");
323 : : }
324 : :
325 : 82 : *set = TAKE_PTR(_set);
326 : :
327 : 82 : return 0;
328 : : }
329 : :
330 : 857 : void bf_set_free(struct bf_set **set)
331 : : {
332 : : bf_assert(set);
333 : :
334 [ + + ]: 857 : if (!*set)
335 : : return;
336 : :
337 : 224 : bf_list_clean(&(*set)->elems);
338 : 224 : freep((void *)&(*set)->name);
339 : : freep((void *)set);
340 : : }
341 : :
342 : 522 : int bf_set_pack(const struct bf_set *set, bf_wpack_t *pack)
343 : : {
344 : : bf_assert(set);
345 : : bf_assert(pack);
346 : :
347 [ + + ]: 522 : if (set->name)
348 : : bf_wpack_kv_str(pack, "name", set->name);
349 : : else
350 : : bf_wpack_kv_nil(pack, "name");
351 : :
352 : 522 : bf_wpack_open_array(pack, "key");
353 [ + + ]: 1175 : for (size_t i = 0; i < set->n_comps; ++i)
354 : 653 : bf_wpack_enum(pack, set->key[i]);
355 : 522 : bf_wpack_close_array(pack);
356 : :
357 : 522 : bf_wpack_open_array(pack, "elements");
358 [ + + + + : 3782 : bf_list_foreach (&set->elems, elem_node)
+ + ]
359 : 1369 : bf_wpack_bin(pack, bf_list_node_get_data(elem_node), set->elem_size);
360 : 522 : bf_wpack_close_array(pack);
361 : :
362 [ - + ]: 522 : return bf_wpack_is_valid(pack) ? 0 : -EINVAL;
363 : : }
364 : :
365 : 5 : void bf_set_dump(const struct bf_set *set, prefix_t *prefix)
366 : : {
367 : : bf_assert(set && prefix);
368 : :
369 [ - + ]: 5 : DUMP(prefix, "struct bf_set at %p", set);
370 : 5 : bf_dump_prefix_push(prefix);
371 : :
372 [ - + - - ]: 5 : DUMP(prefix, "name: %s", set->name ?: "<anonymous>");
373 [ - + ]: 5 : DUMP(prefix, "key: bf_matcher_type[%zu]", set->n_comps);
374 : 5 : bf_dump_prefix_push(prefix);
375 [ + + ]: 14 : for (size_t i = 0; i < set->n_comps; ++i) {
376 [ + + ]: 9 : if (i == set->n_comps - 1)
377 : 5 : bf_dump_prefix_last(prefix);
378 : :
379 [ - + ]: 9 : DUMP(prefix, "%s", bf_matcher_type_to_str(set->key[i]));
380 : : }
381 : 5 : bf_dump_prefix_pop(prefix);
382 : :
383 [ - + ]: 5 : DUMP(prefix, "elem_size: %lu", set->elem_size);
384 [ - + ]: 5 : DUMP(bf_dump_prefix_last(prefix), "elems: bf_list<bytes>[%lu]",
385 : : bf_list_size(&set->elems));
386 : :
387 : 5 : bf_dump_prefix_push(prefix);
388 [ + + + + : 42 : bf_list_foreach (&set->elems, elem_node) {
+ + ]
389 [ + + ]: 16 : if (bf_list_is_tail(&set->elems, elem_node))
390 : 4 : bf_dump_prefix_last(prefix);
391 : :
392 [ - + ]: 16 : DUMP(prefix, "void * @ %p", bf_list_node_get_data(elem_node));
393 : 16 : bf_dump_prefix_push(prefix);
394 : 16 : bf_dump_hex(prefix, bf_list_node_get_data(elem_node), set->elem_size);
395 : 16 : bf_dump_prefix_pop(prefix);
396 : : }
397 : 5 : bf_dump_prefix_pop(prefix);
398 : :
399 : 5 : bf_dump_prefix_pop(prefix);
400 : 5 : }
401 : :
402 : 252 : int bf_set_add_elem(struct bf_set *set, const void *elem)
403 : : {
404 : : bf_assert(set && elem);
405 : :
406 : : _cleanup_free_ void *_elem = NULL;
407 : : int r;
408 : :
409 : 252 : _elem = malloc(set->elem_size);
410 [ + - ]: 252 : if (!_elem)
411 : : return -ENOMEM;
412 : :
413 : 252 : memcpy(_elem, elem, set->elem_size);
414 : :
415 : 252 : r = bf_list_add_tail(&set->elems, _elem);
416 [ - + ]: 252 : if (r < 0)
417 : 0 : return r;
418 : :
419 : : TAKE_PTR(_elem);
420 : :
421 : : return 0;
422 : : }
|
