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 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 : bf_assert(raw_key);
226 15 : bf_assert(raw_payload);
227 :
228 15 : r = _bf_set_parse_key(raw_key, key, &n_comps);
229 15 : if (r)
230 4 : return bf_err_r(r, "failed to parse set key '%s'", raw_key);
231 :
232 11 : r = bf_set_new(&_set, name, key, n_comps);
233 11 : if (r)
234 : return r;
235 :
236 11 : _raw_payload = strdup(raw_payload);
237 11 : 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 34 : while ((raw_elem = strtok_r(tmp, "{};\n", &saveptr))) {
243 24 : 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 24 : if (raw_elem[0] == '\0')
248 0 : continue;
249 :
250 24 : r = _bf_set_parse_elem(_set, raw_elem);
251 24 : if (r)
252 1 : return bf_err_r(r, "failed to parse set element '%s'", raw_elem);
253 :
254 : tmp = NULL;
255 : }
256 :
257 10 : *set = TAKE_PTR(_set);
258 :
259 10 : return 0;
260 : }
261 :
262 1 : int bf_set_new_from_pack(struct bf_set **set, bf_rpack_node_t node)
263 : {
264 1 : _free_bf_set_ struct bf_set *_set = NULL;
265 1 : _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 1 : bf_assert(set);
272 :
273 1 : r = bf_rpack_kv_node(node, "name", &child);
274 1 : if (r)
275 0 : return bf_rpack_key_err(r, "bf_set.name");
276 1 : if (!bf_rpack_is_nil(child)) {
277 0 : r = bf_rpack_str(child, &name);
278 0 : if (r)
279 0 : return bf_err_r(r, "failed to read set name from bf_set.name pack");
280 : }
281 :
282 1 : r = bf_rpack_kv_array(node, "key", &child);
283 1 : if (r)
284 0 : return bf_rpack_key_err(r, "bf_set.key");
285 8 : bf_rpack_array_foreach (child, comp_node) {
286 3 : ++n_comps;
287 3 : 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 3 : 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 1 : r = bf_set_new(&_set, name, key, n_comps);
300 1 : if (r)
301 0 : return bf_err_r(r, "failed to create bf_set from pack");
302 :
303 1 : r = bf_rpack_kv_array(node, "elements", &child);
304 1 : if (r)
305 0 : return bf_rpack_key_err(r, "bf_set.elements");
306 8 : bf_rpack_array_foreach (child, elem_node) {
307 : const void *elem;
308 : size_t elem_len;
309 :
310 3 : r = bf_rpack_bin(elem_node, &elem, &elem_len);
311 3 : if (r)
312 0 : return bf_rpack_key_err(r, "bf_set.elements");
313 :
314 3 : 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 3 : r = bf_set_add_elem(_set, elem);
321 3 : if (r)
322 0 : return bf_err_r(r, "failed to insert element to bf_set");
323 : }
324 :
325 1 : *set = TAKE_PTR(_set);
326 :
327 1 : return 0;
328 : }
329 :
330 52 : void bf_set_free(struct bf_set **set)
331 : {
332 52 : bf_assert(set);
333 :
334 51 : if (!*set)
335 : return;
336 :
337 18 : bf_list_clean(&(*set)->elems);
338 18 : freep((void *)&(*set)->name);
339 : freep((void *)set);
340 : }
341 :
342 3 : int bf_set_pack(const struct bf_set *set, bf_wpack_t *pack)
343 : {
344 3 : bf_assert(set);
345 2 : bf_assert(pack);
346 :
347 1 : if (set->name)
348 : bf_wpack_kv_str(pack, "name", set->name);
349 : else
350 : bf_wpack_kv_nil(pack, "name");
351 :
352 1 : bf_wpack_open_array(pack, "key");
353 4 : for (size_t i = 0; i < set->n_comps; ++i)
354 3 : bf_wpack_enum(pack, set->key[i]);
355 1 : bf_wpack_close_array(pack);
356 :
357 1 : bf_wpack_open_array(pack, "elements");
358 8 : bf_list_foreach (&set->elems, elem_node)
359 3 : bf_wpack_bin(pack, bf_list_node_get_data(elem_node), set->elem_size);
360 1 : bf_wpack_close_array(pack);
361 :
362 1 : return bf_wpack_is_valid(pack) ? 0 : -EINVAL;
363 : }
364 :
365 3 : void bf_set_dump(const struct bf_set *set, prefix_t *prefix)
366 : {
367 3 : bf_assert(set && prefix);
368 :
369 1 : DUMP(prefix, "struct bf_set at %p", set);
370 1 : bf_dump_prefix_push(prefix);
371 :
372 1 : DUMP(prefix, "name: %s", set->name ?: "<anonymous>");
373 1 : DUMP(prefix, "key: bf_matcher_type[%zu]", set->n_comps);
374 1 : bf_dump_prefix_push(prefix);
375 4 : for (size_t i = 0; i < set->n_comps; ++i) {
376 3 : if (i == set->n_comps - 1)
377 1 : bf_dump_prefix_last(prefix);
378 :
379 3 : DUMP(prefix, "%s", bf_matcher_type_to_str(set->key[i]));
380 : }
381 1 : bf_dump_prefix_pop(prefix);
382 :
383 1 : DUMP(prefix, "elem_size: %lu", set->elem_size);
384 1 : DUMP(bf_dump_prefix_last(prefix), "elems: bf_list<bytes>[%lu]",
385 : bf_list_size(&set->elems));
386 :
387 1 : bf_dump_prefix_push(prefix);
388 10 : bf_list_foreach (&set->elems, elem_node) {
389 4 : if (bf_list_is_tail(&set->elems, elem_node))
390 1 : bf_dump_prefix_last(prefix);
391 :
392 4 : DUMP(prefix, "void * @ %p", bf_list_node_get_data(elem_node));
393 4 : bf_dump_prefix_push(prefix);
394 4 : bf_dump_hex(prefix, bf_list_node_get_data(elem_node), set->elem_size);
395 4 : bf_dump_prefix_pop(prefix);
396 : }
397 1 : bf_dump_prefix_pop(prefix);
398 :
399 1 : bf_dump_prefix_pop(prefix);
400 1 : }
401 :
402 6 : int bf_set_add_elem(struct bf_set *set, const void *elem)
403 : {
404 6 : bf_assert(set && elem);
405 :
406 : _cleanup_free_ void *_elem = NULL;
407 : int r;
408 :
409 4 : _elem = malloc(set->elem_size);
410 4 : if (!_elem)
411 : return -ENOMEM;
412 :
413 4 : memcpy(_elem, elem, set->elem_size);
414 :
415 4 : r = bf_list_add_tail(&set->elems, _elem);
416 4 : if (r < 0)
417 0 : return r;
418 :
419 : TAKE_PTR(_elem);
420 :
421 : return 0;
422 : }
|
