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 "core/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 "core/dump.h"
15 : #include "core/helper.h"
16 : #include "core/list.h"
17 : #include "core/logger.h"
18 : #include "core/marsh.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 22 : int bf_set_new(struct bf_set **set, const char *name, enum bf_matcher_type *key,
26 : size_t n_comps)
27 : {
28 22 : bf_assert(set && key);
29 :
30 20 : _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 20 : if (n_comps == 0)
37 1 : return bf_err_r(-EINVAL, "at least 1 key component is required");
38 :
39 19 : 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 18 : _set = malloc(sizeof(*_set));
46 18 : if (!_set)
47 : return -ENOMEM;
48 :
49 18 : _set->name = NULL;
50 18 : if (name) {
51 0 : _set->name = strdup(name);
52 0 : if (!_set->name)
53 0 : return bf_err_r(-ENOMEM, "failed to allocate memory for set name");
54 : }
55 :
56 18 : memcpy(&(_set)->key, key, n_comps * sizeof(enum bf_matcher_type));
57 18 : _set->n_comps = n_comps;
58 18 : _set->elem_size = 0;
59 18 : _set->elems = bf_list_default(freep, NULL);
60 :
61 49 : for (size_t i = 0; i < n_comps; ++i) {
62 : const struct bf_matcher_ops *ops;
63 :
64 32 : ops = bf_matcher_get_ops(_set->key[i], BF_MATCHER_IN);
65 32 : if (!ops) {
66 1 : 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 31 : _set->elem_size += ops->ref_payload_size;
71 :
72 31 : mask |= BF_FLAG(_set->key[i]);
73 : }
74 :
75 17 : _set->use_trie = n_comps == 1 && mask & _BF_SET_USE_TRIE_MASK;
76 :
77 17 : if (n_comps > 1 && mask & _BF_SET_USE_TRIE_MASK) {
78 2 : return bf_err_r(
79 : -EINVAL,
80 : "network matchers can't be used in combination with other matchers in a set");
81 : }
82 :
83 15 : *set = TAKE_PTR(_set);
84 :
85 15 : 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 15 : static int _bf_set_parse_key(const char *raw_key, enum bf_matcher_type *key,
98 : size_t *n_comps)
99 : {
100 15 : bf_assert(raw_key && key && n_comps);
101 :
102 : _cleanup_free_ char *_raw_key = NULL;
103 : char *tmp, *saveptr, *token;
104 :
105 15 : _raw_key = strdup(raw_key);
106 15 : if (!_raw_key) {
107 0 : return bf_err_r(-ENOMEM, "failed to duplicate set raw key '%s'",
108 : raw_key);
109 : }
110 :
111 15 : *n_comps = 0;
112 :
113 : tmp = _raw_key;
114 42 : while ((token = strtok_r(tmp, "(),", &saveptr))) {
115 : int r;
116 :
117 30 : if (*n_comps == BF_SET_MAX_N_COMPS) {
118 1 : return bf_err_r(-E2BIG, "set keys are limited to %d components",
119 : BF_SET_MAX_N_COMPS);
120 : }
121 :
122 29 : token = bf_trim(token);
123 :
124 29 : r = bf_matcher_type_from_str(token, &key[*n_comps]);
125 29 : if (r)
126 2 : return bf_err_r(r, "failed to parse set key component '%s'", token);
127 :
128 : tmp = NULL;
129 27 : ++*n_comps;
130 : }
131 :
132 12 : 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 24 : static int _bf_set_parse_elem(struct bf_set *set, const char *raw_elem)
148 : {
149 24 : 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 24 : _raw_elem = strdup(raw_elem);
159 24 : 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 24 : elem = malloc(set->elem_size);
166 24 : if (!elem)
167 0 : return bf_err_r(-ENOMEM, "failed to allocate a new set element");
168 :
169 : tmp = _raw_elem;
170 68 : while ((token = strtok_r(tmp, ",", &saveptr))) {
171 : const struct bf_matcher_ops *ops;
172 :
173 45 : 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 44 : token = bf_trim(token);
181 :
182 44 : ops = bf_matcher_get_ops(set->key[comp_idx], BF_MATCHER_IN);
183 44 : 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 44 : r = ops->parse(set->key[comp_idx], BF_MATCHER_IN, elem + elem_offset,
189 : token);
190 44 : if (r) {
191 0 : return bf_err_r(r, "failed to parse set element component '%s'",
192 : token);
193 : }
194 :
195 44 : elem_offset += ops->ref_payload_size;
196 : tmp = NULL;
197 44 : ++comp_idx;
198 : }
199 :
200 23 : if (comp_idx != set->n_comps) {
201 0 : return bf_err_r(-EINVAL, "missing component in set element '%s'",
202 : raw_elem);
203 : }
204 :
205 23 : r = bf_list_add_tail(&set->elems, elem);
206 23 : 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 18 : int bf_set_new_from_raw(struct bf_set **set, const char *name,
214 : const char *raw_key, const char *raw_payload)
215 : {
216 21 : bf_assert(set && raw_key && raw_payload);
217 :
218 15 : _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 15 : r = _bf_set_parse_key(raw_key, key, &n_comps);
226 15 : if (r)
227 4 : return bf_err_r(r, "failed to parse set key '%s'", raw_key);
228 :
229 11 : r = bf_set_new(&_set, name, key, n_comps);
230 11 : if (r)
231 : return r;
232 :
233 11 : _raw_payload = strdup(raw_payload);
234 11 : if (!_raw_payload)
235 0 : return bf_err_r(-ENOMEM, "failed to copy set raw payload '%s'",
236 : raw_payload);
237 :
238 : tmp = _raw_payload;
239 34 : while ((raw_elem = strtok_r(tmp, "{};\n", &saveptr))) {
240 24 : raw_elem = bf_trim(raw_elem);
241 :
242 : /* While strtok_r() won't return empty token, the trimmed version of the
243 : * token can be empty! */
244 24 : if (raw_elem[0] == '\0')
245 0 : continue;
246 :
247 24 : r = _bf_set_parse_elem(_set, raw_elem);
248 24 : if (r)
249 1 : return bf_err_r(r, "failed to parse set element '%s'", raw_elem);
250 :
251 : tmp = NULL;
252 : }
253 :
254 10 : *set = TAKE_PTR(_set);
255 :
256 10 : return 0;
257 : }
258 :
259 3 : int bf_set_new_from_marsh(struct bf_set **set, const struct bf_marsh *marsh)
260 : {
261 3 : bf_assert(set && marsh);
262 :
263 1 : _free_bf_set_ struct bf_set *_set = NULL;
264 : enum bf_matcher_type key[BF_SET_MAX_N_COMPS];
265 : struct bf_marsh *child = NULL;
266 : const char *name = NULL;
267 : size_t n_comps;
268 : int r;
269 :
270 1 : if (!(child = bf_marsh_next_child(marsh, child)))
271 : return -EINVAL;
272 1 : if (!bf_marsh_is_empty(child))
273 0 : name = child->data;
274 :
275 1 : if (!(child = bf_marsh_next_child(marsh, child)))
276 : return -EINVAL;
277 1 : memcpy(&n_comps, child->data, sizeof(n_comps));
278 :
279 1 : if (!(child = bf_marsh_next_child(marsh, child)))
280 : return -EINVAL;
281 1 : memcpy(key, child->data, n_comps * sizeof(enum bf_matcher_type));
282 :
283 1 : r = bf_set_new(&_set, name, key, n_comps);
284 1 : if (r < 0)
285 : return r;
286 :
287 1 : if (!(child = bf_marsh_next_child(marsh, child)))
288 : return -EINVAL;
289 1 : memcpy(&_set->elem_size, child->data, sizeof(_set->elem_size));
290 :
291 1 : if (!(child = bf_marsh_next_child(marsh, child)))
292 : return -EINVAL;
293 4 : for (size_t i = 0; i < child->data_len / _set->elem_size; ++i) {
294 3 : _cleanup_free_ void *elem = malloc(_set->elem_size);
295 3 : if (!elem)
296 : return -ENOMEM;
297 :
298 3 : memcpy(elem, child->data + (i * _set->elem_size), _set->elem_size);
299 3 : r = bf_list_add_tail(&_set->elems, elem);
300 3 : if (r < 0)
301 : return r;
302 :
303 : TAKE_PTR(elem);
304 : }
305 :
306 1 : *set = TAKE_PTR(_set);
307 :
308 1 : return 0;
309 : }
310 :
311 52 : void bf_set_free(struct bf_set **set)
312 : {
313 52 : bf_assert(set);
314 :
315 51 : if (!*set)
316 : return;
317 :
318 18 : bf_list_clean(&(*set)->elems);
319 18 : freep((void *)&(*set)->name);
320 : freep((void *)set);
321 : }
322 :
323 3 : int bf_set_marsh(const struct bf_set *set, struct bf_marsh **marsh)
324 : {
325 3 : bf_assert(set && marsh);
326 :
327 1 : _free_bf_marsh_ struct bf_marsh *_marsh = NULL;
328 : _cleanup_free_ uint8_t *data = NULL;
329 : size_t elem_idx = 0;
330 : int r;
331 :
332 1 : r = bf_marsh_new(&_marsh, NULL, 0);
333 1 : if (r < 0)
334 : return r;
335 :
336 1 : r = bf_marsh_add_child_raw(&_marsh, set->name,
337 1 : set->name ? strlen(set->name) + 1 : 0);
338 1 : if (r < 0)
339 : return r;
340 :
341 1 : r = bf_marsh_add_child_raw(&_marsh, &set->n_comps, sizeof(set->n_comps));
342 1 : if (r < 0)
343 : return r;
344 :
345 1 : r = bf_marsh_add_child_raw(&_marsh, set->key,
346 1 : set->n_comps * sizeof(enum bf_matcher_type));
347 1 : if (r < 0)
348 : return r;
349 :
350 1 : r = bf_marsh_add_child_raw(&_marsh, &set->elem_size,
351 : sizeof(set->elem_size));
352 1 : if (r < 0)
353 : return r;
354 :
355 1 : data = malloc(set->elem_size * bf_list_size(&set->elems));
356 1 : if (!data)
357 0 : return bf_err_r(r, "failed to allocate memory for the set's content");
358 :
359 7 : bf_list_foreach (&set->elems, elem_node) {
360 3 : memcpy(data + (elem_idx * set->elem_size),
361 3 : bf_list_node_get_data(elem_node), set->elem_size);
362 3 : ++elem_idx;
363 : }
364 :
365 1 : r = bf_marsh_add_child_raw(&_marsh, data,
366 1 : set->elem_size * bf_list_size(&set->elems));
367 1 : if (r < 0)
368 : return r;
369 :
370 1 : *marsh = TAKE_PTR(_marsh);
371 :
372 1 : return 0;
373 : }
374 :
375 3 : void bf_set_dump(const struct bf_set *set, prefix_t *prefix)
376 : {
377 3 : bf_assert(set && prefix);
378 :
379 1 : DUMP(prefix, "struct bf_set at %p", set);
380 1 : bf_dump_prefix_push(prefix);
381 :
382 1 : DUMP(prefix, "name: %s", set->name ?: "<anonymous>");
383 1 : DUMP(prefix, "key: bf_matcher_type[%zu]", set->n_comps);
384 1 : bf_dump_prefix_push(prefix);
385 4 : for (size_t i = 0; i < set->n_comps; ++i) {
386 3 : if (i == set->n_comps - 1)
387 1 : bf_dump_prefix_last(prefix);
388 :
389 3 : DUMP(prefix, "%s", bf_matcher_type_to_str(set->key[i]));
390 : }
391 1 : bf_dump_prefix_pop(prefix);
392 :
393 1 : DUMP(prefix, "elem_size: %lu", set->elem_size);
394 1 : DUMP(bf_dump_prefix_last(prefix), "elems: bf_list<bytes>[%lu]",
395 : bf_list_size(&set->elems));
396 :
397 1 : bf_dump_prefix_push(prefix);
398 10 : bf_list_foreach (&set->elems, elem_node) {
399 4 : if (bf_list_is_tail(&set->elems, elem_node))
400 1 : bf_dump_prefix_last(prefix);
401 :
402 4 : DUMP(prefix, "void * @ %p", bf_list_node_get_data(elem_node));
403 4 : bf_dump_prefix_push(prefix);
404 4 : bf_dump_hex(prefix, bf_list_node_get_data(elem_node), set->elem_size);
405 4 : bf_dump_prefix_pop(prefix);
406 : }
407 1 : bf_dump_prefix_pop(prefix);
408 :
409 1 : bf_dump_prefix_pop(prefix);
410 1 : }
411 :
412 3 : int bf_set_add_elem(struct bf_set *set, void *elem)
413 : {
414 3 : bf_assert(set && elem);
415 :
416 : _cleanup_free_ void *_elem = NULL;
417 : int r;
418 :
419 1 : _elem = malloc(set->elem_size);
420 1 : if (!_elem)
421 : return -ENOMEM;
422 :
423 1 : memcpy(_elem, elem, set->elem_size);
424 :
425 1 : r = bf_list_add_tail(&set->elems, _elem);
426 1 : if (r < 0)
427 0 : return r;
428 :
429 : TAKE_PTR(_elem);
430 :
431 : return 0;
432 : }
|
