diff options
author | Stefano Brivio <sbrivio@redhat.com> | 2020-01-30 01:16:57 +0100 |
---|---|---|
committer | Pablo Neira Ayuso <pablo@netfilter.org> | 2020-02-07 13:53:37 +0100 |
commit | 8ac2f3b2fca38b6533043b0678730c10ba4dc5ef (patch) | |
tree | 150669b186d8d700c848b35c17cc0097bcab69dd /src/segtree.c | |
parent | 6156ba34018dddd59cb6737cfd5a69a0cbc5eaa4 (diff) |
src: Add support for concatenated set ranges
After exporting field lengths via NFTNL_SET_DESC_CONCAT attributes,
we now need to adjust parsing of user input and generation of
netlink key data to complete support for concatenation of set
ranges.
Instead of using separate elements for start and end of a range,
denoting the end element by the NFT_SET_ELEM_INTERVAL_END flag,
as it's currently done for ranges without concatenation, we'll use
the new attribute NFTNL_SET_ELEM_KEY_END as suggested by Pablo. It
behaves in the same way as NFTNL_SET_ELEM_KEY, but it indicates
that the included key represents the upper bound of a range.
For example, "packets with an IPv4 address between 192.0.2.0 and
192.0.2.42, with destination port between 22 and 25", needs to be
expressed as a single element with two keys:
NFTA_SET_ELEM_KEY: 192.0.2.0 . 22
NFTA_SET_ELEM_KEY_END: 192.0.2.42 . 25
To achieve this, we need to:
- adjust the lexer rules to allow multiton expressions as elements
of a concatenation. As wildcards are not allowed (semantics would
be ambiguous), exclude wildcards expressions from the set of
possible multiton expressions, and allow them directly where
needed. Concatenations now admit prefixes and ranges
- generate, for each element in a range concatenation, a second key
attribute, that includes the upper bound for the range
- also expand prefixes and non-ranged values in the concatenation
to ranges: given a set with interval and concatenation support,
the kernel has no way to tell which elements are ranged, so they
all need to be. For example, 192.0.2.0 . 192.0.2.9 : 1024 is
sent as:
NFTA_SET_ELEM_KEY: 192.0.2.0 . 1024
NFTA_SET_ELEM_KEY_END: 192.0.2.9 . 1024
- aggregate ranges when elements received by the kernel represent
concatenated ranges, see concat_range_aggregate()
- perform a few minor adjustments where interval expressions
are already handled: we have intervals in these sets, but
the set specification isn't just an interval, so we can't
just aggregate and deaggregate interval ranges linearly
v4: No changes
v3:
- rework to use a separate key for closing element of range instead of
a separate element with EXPR_F_INTERVAL_END set (Pablo Neira Ayuso)
v2:
- reworked netlink_gen_concat_data(), moved loop body to a new function,
netlink_gen_concat_data_expr() (Phil Sutter)
- dropped repeated pattern in bison file, replaced by a new helper,
compound_expr_alloc_or_add() (Phil Sutter)
- added set_is_nonconcat_range() helper (Phil Sutter)
- in expr_evaluate_set(), we need to set NFT_SET_SUBKEY also on empty
sets where the set in the context already has the flag
- dropped additional 'end' parameter from netlink_gen_data(),
temporarily set EXPR_F_INTERVAL_END on expressions and use that from
netlink_gen_concat_data() to figure out we need to add the 'end'
element (Phil Sutter)
- replace range_mask_len() by a simplified version, as we don't need
to actually store the composing masks of a range (Phil Sutter)
Signed-off-by: Stefano Brivio <sbrivio@redhat.com>
Signed-off-by: Pablo Neira Ayuso <pablo@netfilter.org>
Diffstat (limited to 'src/segtree.c')
-rw-r--r-- | src/segtree.c | 117 |
1 files changed, 117 insertions, 0 deletions
diff --git a/src/segtree.c b/src/segtree.c index e8e32412..8d79332d 100644 --- a/src/segtree.c +++ b/src/segtree.c @@ -650,6 +650,11 @@ struct expr *get_set_intervals(const struct set *set, const struct expr *init) set_elem_add(set, new_init, i->key->value, i->flags, i->byteorder); break; + case EXPR_CONCAT: + compound_expr_add(new_init, expr_clone(i)); + i->flags |= EXPR_F_INTERVAL_END; + compound_expr_add(new_init, expr_clone(i)); + break; default: range_expr_value_low(low, i); set_elem_add(set, new_init, low, 0, i->byteorder); @@ -821,6 +826,9 @@ static int expr_value_cmp(const void *p1, const void *p2) struct expr *e2 = *(void * const *)p2; int ret; + if (expr_value(e1)->etype == EXPR_CONCAT) + return -1; + ret = mpz_cmp(expr_value(e1)->value, expr_value(e2)->value); if (ret == 0) { if (e1->flags & EXPR_F_INTERVAL_END) @@ -832,6 +840,115 @@ static int expr_value_cmp(const void *p1, const void *p2) return ret; } +/* Given start and end elements of a range, check if it can be represented as + * a single netmask, and if so, how long, by returning zero or a positive value. + */ +static int range_mask_len(const mpz_t start, const mpz_t end, unsigned int len) +{ + mpz_t tmp_start, tmp_end; + int ret; + + mpz_init_set_ui(tmp_start, mpz_get_ui(start)); + mpz_init_set_ui(tmp_end, mpz_get_ui(end)); + + while (mpz_cmp(tmp_start, tmp_end) <= 0 && + !mpz_tstbit(tmp_start, 0) && mpz_tstbit(tmp_end, 0) && + len--) { + mpz_fdiv_q_2exp(tmp_start, tmp_start, 1); + mpz_fdiv_q_2exp(tmp_end, tmp_end, 1); + } + + ret = !mpz_cmp(tmp_start, tmp_end) ? (int)len : -1; + + mpz_clear(tmp_start); + mpz_clear(tmp_end); + + return ret; +} + +/* Given a set with two elements (start and end), transform them into a + * concatenation of ranges. That is, from a list of start expressions and a list + * of end expressions, form a list of start - end expressions. + */ +void concat_range_aggregate(struct expr *set) +{ + struct expr *i, *start = NULL, *end, *r1, *r2, *next, *r1_next, *tmp; + struct list_head *r2_next; + int prefix_len, free_r1; + mpz_t range, p; + + list_for_each_entry_safe(i, next, &set->expressions, list) { + if (!start) { + start = i; + continue; + } + end = i; + + /* Walk over r1 (start expression) and r2 (end) in parallel, + * form ranges between corresponding r1 and r2 expressions, + * store them by replacing r2 expressions, and free r1 + * expressions. + */ + r2 = list_first_entry(&expr_value(end)->expressions, + struct expr, list); + list_for_each_entry_safe(r1, r1_next, + &expr_value(start)->expressions, + list) { + mpz_init(range); + mpz_init(p); + + r2_next = r2->list.next; + free_r1 = 0; + + if (!mpz_cmp(r1->value, r2->value)) { + free_r1 = 1; + goto next; + } + + mpz_sub(range, r2->value, r1->value); + mpz_sub_ui(range, range, 1); + mpz_and(p, r1->value, range); + + /* Check if we are forced, or if it's anyway preferable, + * to express the range as two points instead of a + * netmask. + */ + prefix_len = range_mask_len(r1->value, r2->value, + r1->len); + if (prefix_len < 0 || + !(r1->dtype->flags & DTYPE_F_PREFIX)) { + tmp = range_expr_alloc(&r1->location, r1, + r2); + + list_replace(&r2->list, &tmp->list); + r2_next = tmp->list.next; + } else { + tmp = prefix_expr_alloc(&r1->location, r1, + prefix_len); + tmp->len = r2->len; + + list_replace(&r2->list, &tmp->list); + r2_next = tmp->list.next; + expr_free(r2); + } + +next: + mpz_clear(p); + mpz_clear(range); + + r2 = list_entry(r2_next, typeof(*r2), list); + compound_expr_remove(start, r1); + + if (free_r1) + expr_free(r1); + } + + compound_expr_remove(set, start); + expr_free(start); + start = NULL; + } +} + void interval_map_decompose(struct expr *set) { struct expr **elements, **ranges; |