After exporting subkey (field) lengths via netlink attributes, we now
need to adjust parsing of user input and generation of netlink key
data to complete support for concatenation of set ranges.
The expression of concatenated ranges is described in the kernel
counterpart for this change, quoted here:
--
In order to specify the interval for a set entry, userspace would
simply keep using two elements per entry, as it happens now, with the
end element indicating the upper interval bound. As a single element
can now be a concatenation of several fields, with or without the
NFT_SET_ELEM_INTERVAL_END flag, we obtain a convenient way to support
multiple ranged fields in a set.
[...]
For example, "packets with an IPv4 address between 192.0.2.0 and
192.0.2.42, with destination port between 22 and 25", can be
expressed as two concatenated elements:
192.0.2.0 . 22
192.0.2.42 . 25 with NFT_SET_ELEM_INTERVAL_END
and the NFTA_SET_SUBKEY attributes would be 32, 16, in that order.
Note that this does *not* represent the concatenated range:
0xc0 0x00 0x02 0x00 0x00 0x16 - 0xc0 0x00 0x02 0x2a 0x00 0x25
on the six packet bytes of interest. That is, the range specified
does *not* include e.g. 0xc0 0x00 0x02 0x29 0x00 0x42, which is:
192.0.0.41 . 66
--
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 concatenated range, two elements: one
containing the start expressions, and one containing the
end expressions for all fields in the concatenation
- also expand prefixes and non-ranged values in the concatenation
to ranges: given a set with interval and subkey support, the
kernel has no way to tell which elements are ranged, so they all
need to be. So, for example, 192.0.2.0 . 192.0.2.9 : 1024 is
sent as the two elements:
192.0.2.0 : 1024
192.0.2.9 : 1024 [end]
- aggregate ranges when elements for NFT_SET_SUBKEY sets are
received by the kernel, 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
Signed-off-by: Stefano Brivio <sbrivio@xxxxxxxxxx>
---
include/expression.h | 3 +
include/netlink.h | 2 +-
src/evaluate.c | 13 +++-
src/netlink.c | 95 +++++++++++++++++++++-------
src/netlink_linearize.c | 16 ++---
src/parser_bison.y | 25 ++++++--
src/rule.c | 10 +--
src/segtree.c | 134 ++++++++++++++++++++++++++++++++++++++++
8 files changed, 256 insertions(+), 42 deletions(-)
diff --git a/include/expression.h b/include/expression.h
index b6d5adb2..61596c2e 100644
--- a/include/expression.h
+++ b/include/expression.h
@@ -459,10 +459,13 @@ extern int set_to_intervals(struct list_head *msgs, struct set *set,
struct expr *init, bool add,
unsigned int debug_mask, bool merge,
struct output_ctx *octx);
+extern void concat_range_aggregate(struct expr *set);
extern void interval_map_decompose(struct expr *set);
extern struct expr *get_set_intervals(const struct set *set,
const struct expr *init);
+static void set_elem_add(const struct set *set, struct expr *init, mpz_t value,
+ uint32_t flags);
struct table;
extern int get_set_decompose(struct table *table, struct set *set);
diff --git a/include/netlink.h b/include/netlink.h
index e6941714..ad9e0d2a 100644
--- a/include/netlink.h
+++ b/include/netlink.h
@@ -93,7 +93,7 @@ static inline unsigned int netlink_padding_len(unsigned int size)
}
extern void netlink_gen_data(const struct expr *expr,
- struct nft_data_linearize *data);
+ struct nft_data_linearize *data, int is_range_end);
extern void netlink_gen_raw_data(const mpz_t value, enum byteorder byteorder,
unsigned int len,
struct nft_data_linearize *data);
diff --git a/src/evaluate.c b/src/evaluate.c
index e1ecf4de..8cbb0cbe 100644
--- a/src/evaluate.c
+++ b/src/evaluate.c
@@ -136,6 +136,11 @@ static int byteorder_conversion(struct eval_ctx *ctx, struct expr **expr,
if ((*expr)->byteorder == byteorder)
return 0;
+
+ /* Conversion for EXPR_CONCAT is handled for single composing ranges */
+ if ((*expr)->etype == EXPR_CONCAT)
+ return 0;
+
if (expr_basetype(*expr)->type != TYPE_INTEGER)
return expr_error(ctx->msgs, *expr,
"Byteorder mismatch: expected %s, got %s",
@@ -1352,10 +1357,16 @@ static int expr_evaluate_set(struct eval_ctx *ctx, struct expr **expr)
set->size += i->size - 1;
set->set_flags |= i->set_flags;
expr_free(i);
- } else if (!expr_is_singleton(i))
+ } else if (!expr_is_singleton(i)) {
set->set_flags |= NFT_SET_INTERVAL;
+ if (i->key->etype == EXPR_CONCAT)
+ set->set_flags |= NFT_SET_SUBKEY;
+ }
}
+ if (ctx->set->flags & (NFT_SET_SUBKEY))
+ set->set_flags |= NFT_SET_SUBKEY;
+
set->set_flags |= NFT_SET_CONSTANT;
datatype_set(set, ctx->ectx.dtype);
diff --git a/src/netlink.c b/src/netlink.c
index 7306e358..b8bfd199 100644
--- a/src/netlink.c
+++ b/src/netlink.c
@@ -96,7 +96,8 @@ struct nftnl_expr *alloc_nft_expr(const char *name)
}
static struct nftnl_set_elem *alloc_nftnl_setelem(const struct expr *set,
- const struct expr *expr)
+ const struct expr *expr,
+ int is_range_end)
{
const struct expr *elem, *key, *data;
struct nftnl_set_elem *nlse;
@@ -117,7 +118,7 @@ static struct nftnl_set_elem *alloc_nftnl_setelem(const struct expr *set,
}
key = elem->key;
- netlink_gen_data(key, &nld);
+ netlink_gen_data(key, &nld, is_range_end);
nftnl_set_elem_set(nlse, NFTNL_SET_ELEM_KEY, &nld.value, nld.len);
if (elem->timeout)
nftnl_set_elem_set_u64(nlse, NFTNL_SET_ELEM_TIMEOUT,
@@ -147,7 +148,7 @@ static struct nftnl_set_elem *alloc_nftnl_setelem(const struct expr *set,
nftnl_udata_buf_free(udbuf);
}
if (set_is_datamap(set->set_flags) && data != NULL) {
- netlink_gen_data(data, &nld);
+ netlink_gen_data(data, &nld, 0);
switch (data->etype) {
case EXPR_VERDICT:
nftnl_set_elem_set_u32(nlse, NFTNL_SET_ELEM_VERDICT,
@@ -166,12 +167,12 @@ static struct nftnl_set_elem *alloc_nftnl_setelem(const struct expr *set,
}
}
if (set_is_objmap(set->set_flags) && data != NULL) {
- netlink_gen_data(data, &nld);
+ netlink_gen_data(data, &nld, 0);
nftnl_set_elem_set(nlse, NFTNL_SET_ELEM_OBJREF,
nld.value, nld.len);
}
- if (expr->flags & EXPR_F_INTERVAL_END)
+ if (is_range_end || expr->flags & EXPR_F_INTERVAL_END)
nftnl_set_elem_set_u32(nlse, NFTNL_SET_ELEM_FLAGS,
NFT_SET_ELEM_INTERVAL_END);
@@ -186,8 +187,18 @@ void netlink_gen_raw_data(const mpz_t value, enum byteorder byteorder,
data->len = len;
}
+static int netlink_export_pad(unsigned char *data, const mpz_t v,
+ const struct expr *i)
+{
+ mpz_export_data(data, v, i->byteorder,
+ div_round_up(i->len, BITS_PER_BYTE));
+
+ return netlink_padded_len(i->len) / BITS_PER_BYTE;
+}
+
static void netlink_gen_concat_data(const struct expr *expr,
- struct nft_data_linearize *nld)
+ struct nft_data_linearize *nld,
+ int is_range_end)
{
const struct expr *i;
unsigned int len, offset;
@@ -199,10 +210,39 @@ static void netlink_gen_concat_data(const struct expr *expr,
memset(data, 0, sizeof(data));
offset = 0;
list_for_each_entry(i, &expr->expressions, list) {
- assert(i->etype == EXPR_VALUE);
- mpz_export_data(data + offset, i->value, i->byteorder,
- div_round_up(i->len, BITS_PER_BYTE));
- offset += netlink_padded_len(i->len) / BITS_PER_BYTE;
+ if (i->etype == EXPR_RANGE) {
+ const struct expr *e;
+
+ if (is_range_end)
+ e = i->right;
+ else
+ e = i->left;
+
+ offset += netlink_export_pad(data + offset,
+ e->value, e);
+ } else if (i->etype == EXPR_PREFIX) {
+ if (is_range_end) {
+ mpz_t v;
+
+ mpz_init_bitmask(v, i->len -
+ i->prefix_len);
+ mpz_add(v, i->prefix->value, v);
+ offset += netlink_export_pad(data +
+ offset,
+ v, i);
+ mpz_clear(v);
+ continue;
+ }
+
+ offset += netlink_export_pad(data + offset,
+ i->prefix->value,
+ i);
+ } else {
+ assert(i->etype == EXPR_VALUE);
+
+ offset += netlink_export_pad(data + offset,
+ i->value, i);
+ }
}
memcpy(nld->value, data, len);
@@ -247,13 +287,14 @@ static void netlink_gen_verdict(const struct expr *expr,
}
}
-void netlink_gen_data(const struct expr *expr, struct nft_data_linearize *data)
+void netlink_gen_data(const struct expr *expr, struct nft_data_linearize *data,
+ int end)
{
switch (expr->etype) {
case EXPR_VALUE:
return netlink_gen_constant_data(expr, data);
case EXPR_CONCAT:
- return netlink_gen_concat_data(expr, data);
+ return netlink_gen_concat_data(expr, data, end);
case EXPR_VERDICT:
return netlink_gen_verdict(expr, data);
default:
@@ -712,8 +753,14 @@ void alloc_setelem_cache(const struct expr *set, struct nftnl_set *nls)
const struct expr *expr;
list_for_each_entry(expr, &set->expressions, list) {
- nlse = alloc_nftnl_setelem(set, expr);
+ nlse = alloc_nftnl_setelem(set, expr, 0);
nftnl_set_elem_add(nls, nlse);
+
+ if (set->set_flags & NFT_SET_SUBKEY) {
+ nlse = alloc_nftnl_setelem(set, expr, 1);
+ nftnl_set_elem_add(nls, nlse);
+ }
+
}
}
@@ -907,15 +954,16 @@ int netlink_list_setelems(struct netlink_ctx *ctx, const struct handle *h,
set->init = set_expr_alloc(&internal_location, set);
nftnl_set_elem_foreach(nls, list_setelem_cb, ctx);
- if (!(set->flags & NFT_SET_INTERVAL))
+ if (set->flags & NFT_SET_SUBKEY)
+ concat_range_aggregate(set->init);
+ else if (set->flags & NFT_SET_INTERVAL)
+ interval_map_decompose(set->init);
+ else
list_expr_sort(&ctx->set->init->expressions);
nftnl_set_free(nls);
ctx->set = NULL;
- if (set->flags & NFT_SET_INTERVAL)
- interval_map_decompose(set->init);
-
return 0;
}
@@ -924,6 +972,7 @@ int netlink_get_setelem(struct netlink_ctx *ctx, const struct handle *h,
struct set *set, struct expr *init)
{
struct nftnl_set *nls, *nls_out = NULL;
+ int err = 0;
nls = nftnl_set_alloc();
if (nls == NULL)
@@ -947,18 +996,18 @@ int netlink_get_setelem(struct netlink_ctx *ctx, const struct handle *h,
set->init = set_expr_alloc(loc, set);
nftnl_set_elem_foreach(nls_out, list_setelem_cb, ctx);
- if (!(set->flags & NFT_SET_INTERVAL))
+ if (set->flags & NFT_SET_SUBKEY)
+ concat_range_aggregate(set->init);
+ else if (set->flags & NFT_SET_INTERVAL)
+ err = get_set_decompose(table, set);
+ else
list_expr_sort(&ctx->set->init->expressions);
nftnl_set_free(nls);
nftnl_set_free(nls_out);
ctx->set = NULL;
- if (set->flags & NFT_SET_INTERVAL &&
- get_set_decompose(table, set) < 0)
- return -1;
-
- return 0;
+ return err;
}
void netlink_dump_obj(struct nftnl_obj *nln, struct netlink_ctx *ctx)
diff --git a/src/netlink_linearize.c b/src/netlink_linearize.c
index 498326d0..ef696336 100644
--- a/src/netlink_linearize.c
+++ b/src/netlink_linearize.c
@@ -393,10 +393,10 @@ static void netlink_gen_range(struct netlink_linearize_ctx *ctx,
nle = alloc_nft_expr("range");
netlink_put_register(nle, NFTNL_EXPR_RANGE_SREG, sreg);
nftnl_expr_set_u32(nle, NFTNL_EXPR_RANGE_OP, NFT_RANGE_NEQ);
- netlink_gen_data(range->left, &nld);
+ netlink_gen_data(range->left, &nld, 0);
nftnl_expr_set(nle, NFTNL_EXPR_RANGE_FROM_DATA,
nld.value, nld.len);
- netlink_gen_data(range->right, &nld);
+ netlink_gen_data(range->right, &nld, 0);
nftnl_expr_set(nle, NFTNL_EXPR_RANGE_TO_DATA,
nld.value, nld.len);
nftnl_rule_add_expr(ctx->nlr, nle);
@@ -407,7 +407,7 @@ static void netlink_gen_range(struct netlink_linearize_ctx *ctx,
netlink_put_register(nle, NFTNL_EXPR_CMP_SREG, sreg);
nftnl_expr_set_u32(nle, NFTNL_EXPR_CMP_OP,
netlink_gen_cmp_op(OP_GTE));
- netlink_gen_data(range->left, &nld);
+ netlink_gen_data(range->left, &nld, 0);
nftnl_expr_set(nle, NFTNL_EXPR_CMP_DATA, nld.value, nld.len);
nftnl_rule_add_expr(ctx->nlr, nle);
@@ -415,7 +415,7 @@ static void netlink_gen_range(struct netlink_linearize_ctx *ctx,
netlink_put_register(nle, NFTNL_EXPR_CMP_SREG, sreg);
nftnl_expr_set_u32(nle, NFTNL_EXPR_CMP_OP,
netlink_gen_cmp_op(OP_LTE));
- netlink_gen_data(range->right, &nld);
+ netlink_gen_data(range->right, &nld, 0);
nftnl_expr_set(nle, NFTNL_EXPR_CMP_DATA, nld.value, nld.len);
nftnl_rule_add_expr(ctx->nlr, nle);
break;
@@ -446,7 +446,7 @@ static void netlink_gen_flagcmp(struct netlink_linearize_ctx *ctx,
mpz_init_set_ui(zero, 0);
netlink_gen_raw_data(zero, expr->right->byteorder, len, &nld);
- netlink_gen_data(expr->right, &nld2);
+ netlink_gen_data(expr->right, &nld2, 0);
nle = alloc_nft_expr("bitwise");
netlink_put_register(nle, NFTNL_EXPR_BITWISE_SREG, sreg);
@@ -529,7 +529,7 @@ static void netlink_gen_relational(struct netlink_linearize_ctx *ctx,
netlink_put_register(nle, NFTNL_EXPR_CMP_SREG, sreg);
nftnl_expr_set_u32(nle, NFTNL_EXPR_CMP_OP,
netlink_gen_cmp_op(expr->op));
- netlink_gen_data(right, &nld);
+ netlink_gen_data(right, &nld, 0);
nftnl_expr_set(nle, NFTNL_EXPR_CMP_DATA, nld.value, len);
release_register(ctx, expr->left);
@@ -662,7 +662,7 @@ static void netlink_gen_immediate(struct netlink_linearize_ctx *ctx,
nle = alloc_nft_expr("immediate");
netlink_put_register(nle, NFTNL_EXPR_IMM_DREG, dreg);
- netlink_gen_data(expr, &nld);
+ netlink_gen_data(expr, &nld, 0);
switch (expr->etype) {
case EXPR_VALUE:
nftnl_expr_set(nle, NFTNL_EXPR_IMM_DATA, nld.value, nld.len);
@@ -766,7 +766,7 @@ static void netlink_gen_objref_stmt(struct netlink_linearize_ctx *ctx,
expr->mappings->set->handle.set_id);
break;
case EXPR_VALUE:
- netlink_gen_data(stmt->objref.expr, &nld);
+ netlink_gen_data(stmt->objref.expr, &nld, 0);
nftnl_expr_set(nle, NFTNL_EXPR_OBJREF_IMM_NAME,
nld.value, nld.len);
nftnl_expr_set_u32(nle, NFTNL_EXPR_OBJREF_IMM_TYPE,
diff --git a/src/parser_bison.y b/src/parser_bison.y
index 3f283256..2b718971 100644
--- a/src/parser_bison.y
+++ b/src/parser_bison.y
@@ -3554,7 +3554,6 @@ range_rhs_expr : basic_rhs_expr DASH basic_rhs_expr
multiton_rhs_expr : prefix_rhs_expr
| range_rhs_expr
- | wildcard_expr
;
map_expr : concat_expr MAP rhs_expr
@@ -3648,7 +3647,7 @@ set_elem_option : TIMEOUT time_spec
;
set_lhs_expr : concat_rhs_expr
- | multiton_rhs_expr
+ | wildcard_expr
;
set_rhs_expr : concat_rhs_expr
@@ -3901,7 +3900,7 @@ list_rhs_expr : basic_rhs_expr COMMA basic_rhs_expr
;
rhs_expr : concat_rhs_expr { $$ = $1; }
- | multiton_rhs_expr { $$ = $1; }
+ | wildcard_expr { $$ = $1; }
| set_expr { $$ = $1; }
;
@@ -3941,7 +3940,24 @@ basic_rhs_expr : inclusive_or_rhs_expr
;
concat_rhs_expr : basic_rhs_expr
- | concat_rhs_expr DOT basic_rhs_expr
+ | multiton_rhs_expr
+ | concat_rhs_expr DOT multiton_rhs_expr
+ {
+ if ($$->etype != EXPR_CONCAT) {
+ $$ = concat_expr_alloc(&@$);
+ compound_expr_add($$, $1);
+ } else {
+ struct location rhs[] = {
+ [1] = @2,
+ [2] = @3,
+ };
+ location_update(&$3->location, rhs, 2);
+ $$ = $1;
+ $$->location = @$;
+ }
+ compound_expr_add($$, $3);
+ }
+ | concat_rhs_expr DOT basic_rhs_expr
{
if ($$->etype != EXPR_CONCAT) {
$$ = concat_expr_alloc(&@$);
@@ -3952,7 +3968,6 @@ concat_rhs_expr : basic_rhs_expr
[2] = @3,
};
location_update(&$3->location, rhs, 2);
-
$$ = $1;
$$->location = @$;
}
diff --git a/src/rule.c b/src/rule.c
index 4abc13c9..377781b1 100644
--- a/src/rule.c
+++ b/src/rule.c
@@ -1526,6 +1526,7 @@ static int do_add_setelems(struct netlink_ctx *ctx, struct cmd *cmd,
set = set_lookup(table, h->set.name);
if (set->flags & NFT_SET_INTERVAL &&
+ !(set->flags & NFT_SET_SUBKEY) &&
set_to_intervals(ctx->msgs, set, init, true,
ctx->nft->debug_mask, set->automerge,
&ctx->nft->output) < 0)
@@ -1541,6 +1542,7 @@ static int do_add_set(struct netlink_ctx *ctx, const struct cmd *cmd,
if (set->init != NULL) {
if (set->flags & NFT_SET_INTERVAL &&
+ !(set->flags & NFT_SET_SUBKEY) &&
set_to_intervals(ctx->msgs, set, set->init, true,
ctx->nft->debug_mask, set->automerge,
&ctx->nft->output) < 0)
@@ -1618,15 +1620,15 @@ static int do_command_insert(struct netlink_ctx *ctx, struct cmd *cmd)
static int do_delete_setelems(struct netlink_ctx *ctx, struct cmd *cmd)
{
- struct handle *h = &cmd->handle;
struct expr *expr = cmd->expr;
+ struct handle *h = &cmd->handle;
struct table *table;
struct set *set;
table = table_lookup(h, &ctx->nft->cache);
set = set_lookup(table, h->set.name);
- if (set->flags & NFT_SET_INTERVAL &&
+ if (set->flags & NFT_SET_INTERVAL && !(set->flags & NFT_SET_SUBKEY) &&
set_to_intervals(ctx->msgs, set, expr, false,
ctx->nft->debug_mask, set->automerge,
&ctx->nft->output) < 0)
@@ -2480,7 +2482,7 @@ static int do_get_setelems(struct netlink_ctx *ctx, struct cmd *cmd,
set = set_lookup(table, cmd->handle.set.name);
/* Create a list of elements based of what we got from command line. */
- if (set->flags & NFT_SET_INTERVAL)
+ if (set->flags & NFT_SET_INTERVAL && !(set->flags & NFT_SET_SUBKEY))
init = get_set_intervals(set, cmd->expr);
else
init = cmd->expr;
@@ -2493,7 +2495,7 @@ static int do_get_setelems(struct netlink_ctx *ctx, struct cmd *cmd,
if (err >= 0)
__do_list_set(ctx, cmd, table, new_set);
- if (set->flags & NFT_SET_INTERVAL)
+ if (set->flags & NFT_SET_INTERVAL && !(set->flags & NFT_SET_SUBKEY))
expr_free(init);
set_free(new_set);
diff --git a/src/segtree.c b/src/segtree.c
index 9f1eecc0..e49576bc 100644
--- a/src/segtree.c
+++ b/src/segtree.c
@@ -652,6 +652,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);
@@ -823,6 +828,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)
@@ -834,6 +842,132 @@ 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 a zero or positive value.
+ */
+static int range_mask_len(mpz_t start, mpz_t end, unsigned int len)
+{
+ unsigned int step = 0, i;
+ mpz_t base, tmp;
+ int masks = 0;
+
+ mpz_init_set_ui(base, mpz_get_ui(start));
+
+ while (mpz_cmp(base, end) <= 0) {
+ step = 0;
+ while (!mpz_tstbit(base, step)) {
+ mpz_init_set_ui(tmp, mpz_get_ui(base));
+ for (i = 0; i <= step; i++)
+ mpz_setbit(tmp, i);
+ if (mpz_cmp(tmp, end) > 0) {
+ mpz_clear(tmp);
+ break;
+ }
+ mpz_clear(tmp);
+
+ step++;
+
+ if (step >= len)
+ goto out;
+ }
+
+ if (masks++)
+ goto out;
+
+ mpz_add_ui(base, base, 1 << step);
+ }
+
+out:
+ mpz_clear(base);
+
+ if (masks > 1)
+ return -1;
+ return len - step;
+}
+
+/* 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;
--
2.23.0
