|
Packit Service |
e7ae83 |
/*
|
|
Packit Service |
e7ae83 |
* Copyright (c) 2008-2012 Patrick McHardy <kaber@trash.net>
|
|
Packit Service |
e7ae83 |
*
|
|
Packit Service |
e7ae83 |
* This program is free software; you can redistribute it and/or modify
|
|
Packit Service |
e7ae83 |
* it under the terms of the GNU General Public License version 2 as
|
|
Packit Service |
e7ae83 |
* published by the Free Software Foundation.
|
|
Packit Service |
e7ae83 |
*
|
|
Packit Service |
e7ae83 |
* Development of this code funded by Astaro AG (http://www.astaro.com/)
|
|
Packit Service |
e7ae83 |
*/
|
|
Packit Service |
e7ae83 |
|
|
Packit Service |
e7ae83 |
#include <stdlib.h>
|
|
Packit Service |
e7ae83 |
#include <string.h>
|
|
Packit Service |
e7ae83 |
#include <inttypes.h>
|
|
Packit Service |
e7ae83 |
#include <arpa/inet.h>
|
|
Packit Service |
e7ae83 |
|
|
Packit Service |
e7ae83 |
#include <libnftnl/udata.h>
|
|
Packit Service |
e7ae83 |
|
|
Packit Service |
e7ae83 |
#include <rule.h>
|
|
Packit Service |
e7ae83 |
#include <expression.h>
|
|
Packit Service |
e7ae83 |
#include <gmputil.h>
|
|
Packit Service |
e7ae83 |
#include <utils.h>
|
|
Packit Service |
e7ae83 |
#include <rbtree.h>
|
|
Packit Service |
e7ae83 |
|
|
Packit Service |
e7ae83 |
/**
|
|
Packit Service |
e7ae83 |
* struct seg_tree - segment tree
|
|
Packit Service |
e7ae83 |
*
|
|
Packit Service |
e7ae83 |
* @root: the rbtree's root
|
|
Packit Service |
e7ae83 |
* @type: the datatype of the dimension
|
|
Packit Service |
e7ae83 |
* @dwidth: width of the dimension
|
|
Packit Service |
e7ae83 |
* @byteorder: byteorder of elements
|
|
Packit Service |
e7ae83 |
* @debug_mask: display debugging information
|
|
Packit Service |
e7ae83 |
*/
|
|
Packit Service |
e7ae83 |
struct seg_tree {
|
|
Packit Service |
e7ae83 |
struct rb_root root;
|
|
Packit Service |
e7ae83 |
const struct datatype *keytype;
|
|
Packit Service |
e7ae83 |
unsigned int keylen;
|
|
Packit Service |
e7ae83 |
const struct datatype *datatype;
|
|
Packit Service |
e7ae83 |
unsigned int datalen;
|
|
Packit Service |
e7ae83 |
enum byteorder byteorder;
|
|
Packit Service |
e7ae83 |
unsigned int debug_mask;
|
|
Packit Service |
e7ae83 |
};
|
|
Packit Service |
e7ae83 |
|
|
Packit Service |
e7ae83 |
enum elementary_interval_flags {
|
|
Packit Service |
e7ae83 |
EI_F_INTERVAL_END = 0x1,
|
|
Packit Service |
e7ae83 |
EI_F_INTERVAL_OPEN = 0x2,
|
|
Packit Service |
e7ae83 |
};
|
|
Packit Service |
e7ae83 |
|
|
Packit Service |
e7ae83 |
/**
|
|
Packit Service |
e7ae83 |
* struct elementary_interval - elementary interval [left, right]
|
|
Packit Service |
e7ae83 |
*
|
|
Packit Service |
e7ae83 |
* @rb_node: seg_tree rb node
|
|
Packit Service |
e7ae83 |
* @list: list node for linearized tree
|
|
Packit Service |
e7ae83 |
* @left: left endpoint
|
|
Packit Service |
e7ae83 |
* @right: right endpoint
|
|
Packit Service |
e7ae83 |
* @size: interval size (right - left)
|
|
Packit Service |
e7ae83 |
* @flags: flags
|
|
Packit Service |
e7ae83 |
* @expr: associated expression
|
|
Packit Service |
e7ae83 |
*/
|
|
Packit Service |
e7ae83 |
struct elementary_interval {
|
|
Packit Service |
e7ae83 |
union {
|
|
Packit Service |
e7ae83 |
struct rb_node rb_node;
|
|
Packit Service |
e7ae83 |
struct list_head list;
|
|
Packit Service |
e7ae83 |
};
|
|
Packit Service |
e7ae83 |
|
|
Packit Service |
e7ae83 |
mpz_t left;
|
|
Packit Service |
e7ae83 |
mpz_t right;
|
|
Packit Service |
e7ae83 |
mpz_t size;
|
|
Packit Service |
e7ae83 |
|
|
Packit Service |
e7ae83 |
enum elementary_interval_flags flags;
|
|
Packit Service |
e7ae83 |
struct expr *expr;
|
|
Packit Service |
e7ae83 |
};
|
|
Packit Service |
e7ae83 |
|
|
Packit Service |
e7ae83 |
static void seg_tree_init(struct seg_tree *tree, const struct set *set,
|
|
Packit Service |
e7ae83 |
struct expr *init, unsigned int debug_mask)
|
|
Packit Service |
e7ae83 |
{
|
|
Packit Service |
e7ae83 |
struct expr *first;
|
|
Packit Service |
e7ae83 |
|
|
Packit Service |
e7ae83 |
first = list_entry(init->expressions.next, struct expr, list);
|
|
Packit Service |
e7ae83 |
tree->root = RB_ROOT;
|
|
Packit Service |
e7ae83 |
tree->keytype = set->key->dtype;
|
|
Packit Service |
e7ae83 |
tree->keylen = set->key->len;
|
|
Packit Service |
e7ae83 |
tree->datatype = set->datatype;
|
|
Packit Service |
e7ae83 |
tree->datalen = set->datalen;
|
|
Packit Service |
e7ae83 |
tree->byteorder = first->byteorder;
|
|
Packit Service |
e7ae83 |
tree->debug_mask = debug_mask;
|
|
Packit Service |
e7ae83 |
}
|
|
Packit Service |
e7ae83 |
|
|
Packit Service |
e7ae83 |
static struct elementary_interval *ei_alloc(const mpz_t left, const mpz_t right,
|
|
Packit Service |
e7ae83 |
struct expr *expr,
|
|
Packit Service |
e7ae83 |
enum elementary_interval_flags flags)
|
|
Packit Service |
e7ae83 |
{
|
|
Packit Service |
e7ae83 |
struct elementary_interval *ei;
|
|
Packit Service |
e7ae83 |
|
|
Packit Service |
e7ae83 |
ei = xzalloc(sizeof(*ei));
|
|
Packit Service |
e7ae83 |
mpz_init_set(ei->left, left);
|
|
Packit Service |
e7ae83 |
mpz_init_set(ei->right, right);
|
|
Packit Service |
e7ae83 |
mpz_init(ei->size);
|
|
Packit Service |
e7ae83 |
mpz_sub(ei->size, right, left);
|
|
Packit Service |
e7ae83 |
if (expr != NULL)
|
|
Packit Service |
e7ae83 |
ei->expr = expr_get(expr);
|
|
Packit Service |
e7ae83 |
ei->flags = flags;
|
|
Packit Service |
e7ae83 |
return ei;
|
|
Packit Service |
e7ae83 |
}
|
|
Packit Service |
e7ae83 |
|
|
Packit Service |
e7ae83 |
static void ei_destroy(struct elementary_interval *ei)
|
|
Packit Service |
e7ae83 |
{
|
|
Packit Service |
e7ae83 |
mpz_clear(ei->left);
|
|
Packit Service |
e7ae83 |
mpz_clear(ei->right);
|
|
Packit Service |
e7ae83 |
mpz_clear(ei->size);
|
|
Packit Service |
e7ae83 |
if (ei->expr != NULL)
|
|
Packit Service |
e7ae83 |
expr_free(ei->expr);
|
|
Packit Service |
e7ae83 |
xfree(ei);
|
|
Packit Service |
e7ae83 |
}
|
|
Packit Service |
e7ae83 |
|
|
Packit Service |
e7ae83 |
/**
|
|
Packit Service |
e7ae83 |
* ei_lookup - find elementary interval containing point p
|
|
Packit Service |
e7ae83 |
*
|
|
Packit Service |
e7ae83 |
* @tree: segment tree
|
|
Packit Service |
e7ae83 |
* @p: the point
|
|
Packit Service |
e7ae83 |
*/
|
|
Packit Service |
e7ae83 |
static struct elementary_interval *ei_lookup(struct seg_tree *tree, const mpz_t p)
|
|
Packit Service |
e7ae83 |
{
|
|
Packit Service |
e7ae83 |
struct rb_node *n = tree->root.rb_node;
|
|
Packit Service |
e7ae83 |
struct elementary_interval *ei;
|
|
Packit Service |
e7ae83 |
|
|
Packit Service |
e7ae83 |
while (n != NULL) {
|
|
Packit Service |
e7ae83 |
ei = rb_entry(n, struct elementary_interval, rb_node);
|
|
Packit Service |
e7ae83 |
|
|
Packit Service |
e7ae83 |
if (mpz_cmp(p, ei->left) >= 0 &&
|
|
Packit Service |
e7ae83 |
mpz_cmp(p, ei->right) <= 0)
|
|
Packit Service |
e7ae83 |
return ei;
|
|
Packit Service |
e7ae83 |
else if (mpz_cmp(p, ei->left) <= 0)
|
|
Packit Service |
e7ae83 |
n = n->rb_left;
|
|
Packit Service |
e7ae83 |
else if (mpz_cmp(p, ei->right) > 0)
|
|
Packit Service |
e7ae83 |
n = n->rb_right;
|
|
Packit Service |
e7ae83 |
}
|
|
Packit Service |
e7ae83 |
return NULL;
|
|
Packit Service |
e7ae83 |
}
|
|
Packit Service |
e7ae83 |
|
|
Packit Service |
e7ae83 |
static void ei_remove(struct seg_tree *tree, struct elementary_interval *ei)
|
|
Packit Service |
e7ae83 |
{
|
|
Packit Service |
e7ae83 |
rb_erase(&ei->rb_node, &tree->root);
|
|
Packit Service |
e7ae83 |
}
|
|
Packit Service |
e7ae83 |
|
|
Packit Service |
e7ae83 |
static void __ei_insert(struct seg_tree *tree, struct elementary_interval *new)
|
|
Packit Service |
e7ae83 |
{
|
|
Packit Service |
e7ae83 |
struct rb_node **p = &tree->root.rb_node;
|
|
Packit Service |
e7ae83 |
struct rb_node *parent = NULL;
|
|
Packit Service |
e7ae83 |
struct elementary_interval *ei;
|
|
Packit Service |
e7ae83 |
|
|
Packit Service |
e7ae83 |
while (*p != NULL) {
|
|
Packit Service |
e7ae83 |
parent = *p;
|
|
Packit Service |
e7ae83 |
ei = rb_entry(parent, struct elementary_interval, rb_node);
|
|
Packit Service |
e7ae83 |
|
|
Packit Service |
e7ae83 |
if (mpz_cmp(new->left, ei->left) >= 0 &&
|
|
Packit Service |
e7ae83 |
mpz_cmp(new->left, ei->right) <= 0)
|
|
Packit Service |
e7ae83 |
break;
|
|
Packit Service |
e7ae83 |
else if (mpz_cmp(new->left, ei->left) <= 0)
|
|
Packit Service |
e7ae83 |
p = &(*p)->rb_left;
|
|
Packit Service |
e7ae83 |
else if (mpz_cmp(new->left, ei->left) > 0)
|
|
Packit Service |
e7ae83 |
p = &(*p)->rb_right;
|
|
Packit Service |
e7ae83 |
}
|
|
Packit Service |
e7ae83 |
|
|
Packit Service |
e7ae83 |
rb_link_node(&new->rb_node, parent, p);
|
|
Packit Service |
e7ae83 |
rb_insert_color(&new->rb_node, &tree->root);
|
|
Packit Service |
e7ae83 |
}
|
|
Packit Service |
e7ae83 |
|
|
Packit Service |
e7ae83 |
static bool segtree_debug(unsigned int debug_mask)
|
|
Packit Service |
e7ae83 |
{
|
|
Packit Service |
e7ae83 |
if (debug_mask & NFT_DEBUG_SEGTREE)
|
|
Packit Service |
e7ae83 |
return true;
|
|
Packit Service |
e7ae83 |
|
|
Packit Service |
e7ae83 |
return false;
|
|
Packit Service |
e7ae83 |
}
|
|
Packit Service |
e7ae83 |
|
|
Packit Service |
e7ae83 |
/**
|
|
Packit Service |
e7ae83 |
* ei_insert - insert an elementary interval into the tree
|
|
Packit Service |
e7ae83 |
*
|
|
Packit Service |
e7ae83 |
* @tree: the seg_tree
|
|
Packit Service |
e7ae83 |
* @new: the elementary interval
|
|
Packit Service |
e7ae83 |
*
|
|
Packit Service |
e7ae83 |
* New entries take precedence over existing ones. Insertions are assumed to
|
|
Packit Service |
e7ae83 |
* be ordered by descending interval size, meaning the new interval never
|
|
Packit Service |
e7ae83 |
* extends over more than two existing intervals.
|
|
Packit Service |
e7ae83 |
*/
|
|
Packit Service |
e7ae83 |
static int ei_insert(struct list_head *msgs, struct seg_tree *tree,
|
|
Packit Service |
e7ae83 |
struct elementary_interval *new, bool merge)
|
|
Packit Service |
e7ae83 |
{
|
|
Packit Service |
e7ae83 |
struct elementary_interval *lei, *rei;
|
|
Packit Service |
e7ae83 |
mpz_t p;
|
|
Packit Service |
e7ae83 |
|
|
Packit Service |
e7ae83 |
mpz_init2(p, tree->keylen);
|
|
Packit Service |
e7ae83 |
|
|
Packit Service |
e7ae83 |
/*
|
|
Packit Service |
e7ae83 |
* Lookup the intervals containing the left and right endpoints.
|
|
Packit Service |
e7ae83 |
*/
|
|
Packit Service |
e7ae83 |
lei = ei_lookup(tree, new->left);
|
|
Packit Service |
e7ae83 |
rei = ei_lookup(tree, new->right);
|
|
Packit Service |
e7ae83 |
|
|
Packit Service |
e7ae83 |
if (segtree_debug(tree->debug_mask))
|
|
Packit Service |
e7ae83 |
pr_gmp_debug("insert: [%Zx %Zx]\n", new->left, new->right);
|
|
Packit Service |
e7ae83 |
|
|
Packit Service |
e7ae83 |
if (lei != NULL && rei != NULL && lei == rei) {
|
|
Packit Service |
e7ae83 |
if (!merge)
|
|
Packit Service |
e7ae83 |
goto err;
|
|
Packit Service |
e7ae83 |
/*
|
|
Packit Service |
e7ae83 |
* The new interval is entirely contained in the same interval,
|
|
Packit Service |
e7ae83 |
* split it into two parts:
|
|
Packit Service |
e7ae83 |
*
|
|
Packit Service |
e7ae83 |
* [lei_left, new_left) and (new_right, rei_right]
|
|
Packit Service |
e7ae83 |
*/
|
|
Packit Service |
e7ae83 |
if (segtree_debug(tree->debug_mask))
|
|
Packit Service |
e7ae83 |
pr_gmp_debug("split [%Zx %Zx]\n", lei->left, lei->right);
|
|
Packit Service |
e7ae83 |
|
|
Packit Service |
e7ae83 |
ei_remove(tree, lei);
|
|
Packit Service |
e7ae83 |
|
|
Packit Service |
e7ae83 |
mpz_sub_ui(p, new->left, 1);
|
|
Packit Service |
e7ae83 |
if (mpz_cmp(lei->left, p) <= 0)
|
|
Packit Service |
e7ae83 |
__ei_insert(tree, ei_alloc(lei->left, p, lei->expr, 0));
|
|
Packit Service |
e7ae83 |
|
|
Packit Service |
e7ae83 |
mpz_add_ui(p, new->right, 1);
|
|
Packit Service |
e7ae83 |
if (mpz_cmp(p, rei->right) < 0)
|
|
Packit Service |
e7ae83 |
__ei_insert(tree, ei_alloc(p, rei->right, lei->expr, 0));
|
|
Packit Service |
e7ae83 |
ei_destroy(lei);
|
|
Packit Service |
e7ae83 |
} else {
|
|
Packit Service |
e7ae83 |
if (lei != NULL) {
|
|
Packit Service |
e7ae83 |
if (!merge)
|
|
Packit Service |
e7ae83 |
goto err;
|
|
Packit Service |
e7ae83 |
/*
|
|
Packit Service |
e7ae83 |
* Left endpoint is within lei, adjust it so we have:
|
|
Packit Service |
e7ae83 |
*
|
|
Packit Service |
e7ae83 |
* [lei_left, new_left)[new_left, new_right]
|
|
Packit Service |
e7ae83 |
*/
|
|
Packit Service |
e7ae83 |
if (segtree_debug(tree->debug_mask)) {
|
|
Packit Service |
e7ae83 |
pr_gmp_debug("adjust left [%Zx %Zx]\n",
|
|
Packit Service |
e7ae83 |
lei->left, lei->right);
|
|
Packit Service |
e7ae83 |
}
|
|
Packit Service |
e7ae83 |
|
|
Packit Service |
e7ae83 |
mpz_sub_ui(lei->right, new->left, 1);
|
|
Packit Service |
e7ae83 |
mpz_sub(lei->size, lei->right, lei->left);
|
|
Packit Service |
e7ae83 |
if (mpz_sgn(lei->size) < 0) {
|
|
Packit Service |
e7ae83 |
ei_remove(tree, lei);
|
|
Packit Service |
e7ae83 |
ei_destroy(lei);
|
|
Packit Service |
e7ae83 |
}
|
|
Packit Service |
e7ae83 |
}
|
|
Packit Service |
e7ae83 |
if (rei != NULL) {
|
|
Packit Service |
e7ae83 |
if (!merge)
|
|
Packit Service |
e7ae83 |
goto err;
|
|
Packit Service |
e7ae83 |
/*
|
|
Packit Service |
e7ae83 |
* Right endpoint is within rei, adjust it so we have:
|
|
Packit Service |
e7ae83 |
*
|
|
Packit Service |
e7ae83 |
* [new_left, new_right](new_right, rei_right]
|
|
Packit Service |
e7ae83 |
*/
|
|
Packit Service |
e7ae83 |
if (segtree_debug(tree->debug_mask)) {
|
|
Packit Service |
e7ae83 |
pr_gmp_debug("adjust right [%Zx %Zx]\n",
|
|
Packit Service |
e7ae83 |
rei->left, rei->right);
|
|
Packit Service |
e7ae83 |
}
|
|
Packit Service |
e7ae83 |
|
|
Packit Service |
e7ae83 |
mpz_add_ui(rei->left, new->right, 1);
|
|
Packit Service |
e7ae83 |
mpz_sub(rei->size, rei->right, rei->left);
|
|
Packit Service |
e7ae83 |
if (mpz_sgn(rei->size) < 0) {
|
|
Packit Service |
e7ae83 |
ei_remove(tree, rei);
|
|
Packit Service |
e7ae83 |
ei_destroy(rei);
|
|
Packit Service |
e7ae83 |
}
|
|
Packit Service |
e7ae83 |
}
|
|
Packit Service |
e7ae83 |
}
|
|
Packit Service |
e7ae83 |
|
|
Packit Service |
e7ae83 |
__ei_insert(tree, new);
|
|
Packit Service |
e7ae83 |
|
|
Packit Service |
e7ae83 |
mpz_clear(p);
|
|
Packit Service |
e7ae83 |
|
|
Packit Service |
e7ae83 |
return 0;
|
|
Packit Service |
e7ae83 |
err:
|
|
Packit Service |
e7ae83 |
errno = EEXIST;
|
|
Packit Service |
e7ae83 |
return expr_binary_error(msgs, lei->expr, new->expr,
|
|
Packit Service |
e7ae83 |
"conflicting intervals specified");
|
|
Packit Service |
e7ae83 |
}
|
|
Packit Service |
e7ae83 |
|
|
Packit Service |
e7ae83 |
/*
|
|
Packit Service |
e7ae83 |
* Sort intervals according to their priority, which is defined inversely to
|
|
Packit Service |
e7ae83 |
* their size.
|
|
Packit Service |
e7ae83 |
*
|
|
Packit Service |
e7ae83 |
* The beginning of the interval is used as secondary sorting criterion. This
|
|
Packit Service |
e7ae83 |
* makes sure that overlapping ranges with equal priority are next to each
|
|
Packit Service |
e7ae83 |
* other, allowing to easily detect unsolvable conflicts during insertion.
|
|
Packit Service |
e7ae83 |
*
|
|
Packit Service |
e7ae83 |
* Note: unsolvable conflicts can only occur when using ranges or two identical
|
|
Packit Service |
e7ae83 |
* prefix specifications.
|
|
Packit Service |
e7ae83 |
*/
|
|
Packit Service |
e7ae83 |
static int interval_cmp(const void *p1, const void *p2)
|
|
Packit Service |
e7ae83 |
{
|
|
Packit Service |
e7ae83 |
const struct elementary_interval *e1 = *(void * const *)p1;
|
|
Packit Service |
e7ae83 |
const struct elementary_interval *e2 = *(void * const *)p2;
|
|
Packit Service |
e7ae83 |
mpz_t d;
|
|
Packit Service |
e7ae83 |
int ret;
|
|
Packit Service |
e7ae83 |
|
|
Packit Service |
e7ae83 |
mpz_init(d);
|
|
Packit Service |
e7ae83 |
|
|
Packit Service |
e7ae83 |
mpz_sub(d, e2->size, e1->size);
|
|
Packit Service |
e7ae83 |
if (mpz_cmp_ui(d, 0))
|
|
Packit Service |
e7ae83 |
ret = mpz_sgn(d);
|
|
Packit Service |
e7ae83 |
else
|
|
Packit Service |
e7ae83 |
ret = mpz_cmp(e1->left, e2->left);
|
|
Packit Service |
e7ae83 |
|
|
Packit Service |
e7ae83 |
mpz_clear(d);
|
|
Packit Service |
e7ae83 |
return ret;
|
|
Packit Service |
e7ae83 |
}
|
|
Packit Service |
e7ae83 |
|
|
Packit Service |
e7ae83 |
static unsigned int expr_to_intervals(const struct expr *set,
|
|
Packit Service |
e7ae83 |
unsigned int keylen,
|
|
Packit Service |
e7ae83 |
struct elementary_interval **intervals)
|
|
Packit Service |
e7ae83 |
{
|
|
Packit Service |
e7ae83 |
struct elementary_interval *ei;
|
|
Packit Service |
e7ae83 |
struct expr *i, *next;
|
|
Packit Service |
e7ae83 |
unsigned int n;
|
|
Packit Service |
e7ae83 |
mpz_t low, high;
|
|
Packit Service |
e7ae83 |
|
|
Packit Service |
e7ae83 |
mpz_init2(low, keylen);
|
|
Packit Service |
e7ae83 |
mpz_init2(high, keylen);
|
|
Packit Service |
e7ae83 |
|
|
Packit Service |
e7ae83 |
/*
|
|
Packit Service |
e7ae83 |
* Convert elements to intervals.
|
|
Packit Service |
e7ae83 |
*/
|
|
Packit Service |
e7ae83 |
n = 0;
|
|
Packit Service |
e7ae83 |
list_for_each_entry_safe(i, next, &set->expressions, list) {
|
|
Packit Service |
e7ae83 |
range_expr_value_low(low, i);
|
|
Packit Service |
e7ae83 |
range_expr_value_high(high, i);
|
|
Packit Service |
e7ae83 |
ei = ei_alloc(low, high, i, 0);
|
|
Packit Service |
e7ae83 |
intervals[n++] = ei;
|
|
Packit Service |
e7ae83 |
}
|
|
Packit Service |
e7ae83 |
mpz_clear(high);
|
|
Packit Service |
e7ae83 |
mpz_clear(low);
|
|
Packit Service |
e7ae83 |
|
|
Packit Service |
e7ae83 |
return n;
|
|
Packit Service |
e7ae83 |
}
|
|
Packit Service |
e7ae83 |
|
|
Packit Service |
e7ae83 |
static bool intervals_match(const struct elementary_interval *e1,
|
|
Packit Service |
e7ae83 |
const struct elementary_interval *e2)
|
|
Packit Service |
e7ae83 |
{
|
|
Packit Service |
e7ae83 |
return mpz_cmp(e1->left, e2->left) == 0 &&
|
|
Packit Service |
e7ae83 |
mpz_cmp(e1->right, e2->right) == 0;
|
|
Packit Service |
e7ae83 |
}
|
|
Packit Service |
e7ae83 |
|
|
Packit Service |
e7ae83 |
/* This function checks for overlaps in two ways:
|
|
Packit Service |
e7ae83 |
*
|
|
Packit Service |
e7ae83 |
* 1) A new interval end intersects an existing interval.
|
|
Packit Service |
e7ae83 |
* 2) New intervals that are larger than existing ones, that don't intersect
|
|
Packit Service |
e7ae83 |
* at all, but that wrap the existing ones.
|
|
Packit Service |
e7ae83 |
*/
|
|
Packit Service |
e7ae83 |
static bool interval_overlap(const struct elementary_interval *e1,
|
|
Packit Service |
e7ae83 |
const struct elementary_interval *e2)
|
|
Packit Service |
e7ae83 |
{
|
|
Packit Service |
e7ae83 |
if (intervals_match(e1, e2))
|
|
Packit Service |
e7ae83 |
return false;
|
|
Packit Service |
e7ae83 |
|
|
Packit Service |
e7ae83 |
return (mpz_cmp(e1->left, e2->left) >= 0 &&
|
|
Packit Service |
e7ae83 |
mpz_cmp(e1->left, e2->right) <= 0) ||
|
|
Packit Service |
e7ae83 |
(mpz_cmp(e1->right, e2->left) >= 0 &&
|
|
Packit Service |
e7ae83 |
mpz_cmp(e1->right, e2->right) <= 0) ||
|
|
Packit Service |
e7ae83 |
(mpz_cmp(e1->left, e2->left) <= 0 &&
|
|
Packit Service |
e7ae83 |
mpz_cmp(e1->right, e2->right) >= 0);
|
|
Packit Service |
e7ae83 |
}
|
|
Packit Service |
e7ae83 |
|
|
Packit Service |
e7ae83 |
static int set_overlap(struct list_head *msgs, const struct set *set,
|
|
Packit Service |
e7ae83 |
struct expr *init, unsigned int keylen, bool add)
|
|
Packit Service |
e7ae83 |
{
|
|
Packit Service |
e7ae83 |
struct elementary_interval *new_intervals[init->size];
|
|
Packit Service |
e7ae83 |
struct elementary_interval *intervals[set->init->size];
|
|
Packit Service |
e7ae83 |
unsigned int n, m, i, j;
|
|
Packit Service |
e7ae83 |
int ret = 0;
|
|
Packit Service |
e7ae83 |
|
|
Packit Service |
e7ae83 |
n = expr_to_intervals(init, keylen, new_intervals);
|
|
Packit Service |
e7ae83 |
m = expr_to_intervals(set->init, keylen, intervals);
|
|
Packit Service |
e7ae83 |
|
|
Packit Service |
e7ae83 |
for (i = 0; i < n; i++) {
|
|
Packit Service |
e7ae83 |
bool found = false;
|
|
Packit Service |
e7ae83 |
|
|
Packit Service |
e7ae83 |
for (j = 0; j < m; j++) {
|
|
Packit Service |
e7ae83 |
if (add && interval_overlap(new_intervals[i],
|
|
Packit Service |
e7ae83 |
intervals[j])) {
|
|
Packit Service |
e7ae83 |
expr_error(msgs, new_intervals[i]->expr,
|
|
Packit Service |
e7ae83 |
"interval overlaps with an existing one");
|
|
Packit Service |
e7ae83 |
errno = EEXIST;
|
|
Packit Service |
e7ae83 |
ret = -1;
|
|
Packit Service |
e7ae83 |
goto out;
|
|
Packit Service |
e7ae83 |
} else if (!add && intervals_match(new_intervals[i],
|
|
Packit Service |
e7ae83 |
intervals[j])) {
|
|
Packit Service |
e7ae83 |
found = true;
|
|
Packit Service |
e7ae83 |
break;
|
|
Packit Service |
e7ae83 |
}
|
|
Packit Service |
e7ae83 |
}
|
|
Packit Service |
e7ae83 |
if (!add && !found) {
|
|
Packit Service |
e7ae83 |
expr_error(msgs, new_intervals[i]->expr,
|
|
Packit Service |
e7ae83 |
"interval not found in set");
|
|
Packit Service |
e7ae83 |
errno = ENOENT;
|
|
Packit Service |
e7ae83 |
ret = -1;
|
|
Packit Service |
e7ae83 |
break;
|
|
Packit Service |
e7ae83 |
}
|
|
Packit Service |
e7ae83 |
}
|
|
Packit Service |
e7ae83 |
out:
|
|
Packit Service |
e7ae83 |
for (i = 0; i < n; i++)
|
|
Packit Service |
e7ae83 |
ei_destroy(new_intervals[i]);
|
|
Packit Service |
e7ae83 |
for (i = 0; i < m; i++)
|
|
Packit Service |
e7ae83 |
ei_destroy(intervals[i]);
|
|
Packit Service |
e7ae83 |
|
|
Packit Service |
e7ae83 |
return ret;
|
|
Packit Service |
e7ae83 |
}
|
|
Packit Service |
e7ae83 |
|
|
Packit Service |
e7ae83 |
static int set_to_segtree(struct list_head *msgs, struct set *set,
|
|
Packit Service |
e7ae83 |
struct expr *init, struct seg_tree *tree,
|
|
Packit Service |
e7ae83 |
bool add, bool merge)
|
|
Packit Service |
e7ae83 |
{
|
|
Packit Service |
e7ae83 |
struct elementary_interval *intervals[init->size];
|
|
Packit Service |
e7ae83 |
struct expr *i, *next;
|
|
Packit Service |
e7ae83 |
unsigned int n;
|
|
Packit Service |
e7ae83 |
int err;
|
|
Packit Service |
e7ae83 |
|
|
Packit Service |
e7ae83 |
/* We are updating an existing set with new elements, check if the new
|
|
Packit Service |
e7ae83 |
* interval overlaps with any of the existing ones.
|
|
Packit Service |
e7ae83 |
*/
|
|
Packit Service |
e7ae83 |
if (set->init && set->init != init) {
|
|
Packit Service |
e7ae83 |
err = set_overlap(msgs, set, init, tree->keylen, add);
|
|
Packit Service |
e7ae83 |
if (err < 0)
|
|
Packit Service |
e7ae83 |
return err;
|
|
Packit Service |
e7ae83 |
}
|
|
Packit Service |
e7ae83 |
|
|
Packit Service |
e7ae83 |
n = expr_to_intervals(init, tree->keylen, intervals);
|
|
Packit Service |
e7ae83 |
|
|
Packit Service |
e7ae83 |
list_for_each_entry_safe(i, next, &init->expressions, list) {
|
|
Packit Service |
e7ae83 |
list_del(&i->list);
|
|
Packit Service |
e7ae83 |
expr_free(i);
|
|
Packit Service |
e7ae83 |
}
|
|
Packit Service |
e7ae83 |
|
|
Packit Service |
e7ae83 |
/*
|
|
Packit Service |
e7ae83 |
* Sort intervals by priority.
|
|
Packit Service |
e7ae83 |
*/
|
|
Packit Service |
e7ae83 |
qsort(intervals, n, sizeof(intervals[0]), interval_cmp);
|
|
Packit Service |
e7ae83 |
|
|
Packit Service |
e7ae83 |
/*
|
|
Packit Service |
e7ae83 |
* Insert elements into tree
|
|
Packit Service |
e7ae83 |
*/
|
|
Packit Service |
e7ae83 |
for (n = 0; n < init->size; n++) {
|
|
Packit Service |
e7ae83 |
err = ei_insert(msgs, tree, intervals[n], merge);
|
|
Packit Service |
e7ae83 |
if (err < 0)
|
|
Packit Service |
e7ae83 |
return err;
|
|
Packit Service |
e7ae83 |
}
|
|
Packit Service |
e7ae83 |
|
|
Packit Service |
e7ae83 |
return 0;
|
|
Packit Service |
e7ae83 |
}
|
|
Packit Service |
e7ae83 |
|
|
Packit Service |
e7ae83 |
static bool segtree_needs_first_segment(const struct set *set,
|
|
Packit Service |
e7ae83 |
const struct expr *init, bool add)
|
|
Packit Service |
e7ae83 |
{
|
|
Packit Service |
e7ae83 |
if (add) {
|
|
Packit Service |
e7ae83 |
/* Add the first segment in four situations:
|
|
Packit Service |
e7ae83 |
*
|
|
Packit Service |
e7ae83 |
* 1) This is an anonymous set.
|
|
Packit Service |
e7ae83 |
* 2) This set exists and it is empty.
|
|
Packit Service |
e7ae83 |
* 3) New empty set and, separately, new elements are added.
|
|
Packit Service |
e7ae83 |
* 4) This set is created with a number of initial elements.
|
|
Packit Service |
e7ae83 |
*/
|
|
Packit Service |
e7ae83 |
if ((set_is_anonymous(set->flags)) ||
|
|
Packit Service |
e7ae83 |
(set->init && set->init->size == 0) ||
|
|
Packit Service |
e7ae83 |
(set->init == NULL && init) ||
|
|
Packit Service |
e7ae83 |
(set->init == init)) {
|
|
Packit Service |
e7ae83 |
return true;
|
|
Packit Service |
e7ae83 |
}
|
|
Packit Service |
e7ae83 |
} else {
|
|
Packit Service |
e7ae83 |
/* If the set is empty after the removal, we have to
|
|
Packit Service |
e7ae83 |
* remove the first non-matching segment too.
|
|
Packit Service |
e7ae83 |
*/
|
|
Packit Service |
e7ae83 |
if (set->init && set->init->size - init->size == 0)
|
|
Packit Service |
e7ae83 |
return true;
|
|
Packit Service |
e7ae83 |
}
|
|
Packit Service |
e7ae83 |
/* This is an update for a set that already contains elements, so don't
|
|
Packit Service |
e7ae83 |
* add the first non-matching elements otherwise we hit EEXIST.
|
|
Packit Service |
e7ae83 |
*/
|
|
Packit Service |
e7ae83 |
return false;
|
|
Packit Service |
e7ae83 |
}
|
|
Packit Service |
e7ae83 |
|
|
Packit Service |
e7ae83 |
static void segtree_linearize(struct list_head *list, const struct set *set,
|
|
Packit Service |
e7ae83 |
const struct expr *init, struct seg_tree *tree,
|
|
Packit Service |
e7ae83 |
bool add, bool merge)
|
|
Packit Service |
e7ae83 |
{
|
|
Packit Service |
e7ae83 |
bool needs_first_segment = segtree_needs_first_segment(set, init, add);
|
|
Packit Service |
e7ae83 |
struct elementary_interval *ei, *nei, *prev = NULL;
|
|
Packit Service |
e7ae83 |
struct rb_node *node, *next;
|
|
Packit Service |
e7ae83 |
mpz_t p, q;
|
|
Packit Service |
e7ae83 |
|
|
Packit Service |
e7ae83 |
mpz_init2(p, tree->keylen);
|
|
Packit Service |
e7ae83 |
mpz_init2(q, tree->keylen);
|
|
Packit Service |
e7ae83 |
|
|
Packit Service |
e7ae83 |
/*
|
|
Packit Service |
e7ae83 |
* Convert the tree of open intervals to half-closed map expressions.
|
|
Packit Service |
e7ae83 |
*/
|
|
Packit Service |
e7ae83 |
rb_for_each_entry_safe(ei, node, next, &tree->root, rb_node) {
|
|
Packit Service |
e7ae83 |
if (segtree_debug(tree->debug_mask))
|
|
Packit Service |
e7ae83 |
pr_gmp_debug("iter: [%Zx %Zx]\n", ei->left, ei->right);
|
|
Packit Service |
e7ae83 |
|
|
Packit Service |
e7ae83 |
if (prev == NULL) {
|
|
Packit Service |
e7ae83 |
/*
|
|
Packit Service |
e7ae83 |
* If the first segment doesn't begin at zero, insert a
|
|
Packit Service |
e7ae83 |
* non-matching segment to cover [0, first_left).
|
|
Packit Service |
e7ae83 |
*/
|
|
Packit Service |
e7ae83 |
if (needs_first_segment && mpz_cmp_ui(ei->left, 0)) {
|
|
Packit Service |
e7ae83 |
mpz_set_ui(p, 0);
|
|
Packit Service |
e7ae83 |
mpz_sub_ui(q, ei->left, 1);
|
|
Packit Service |
e7ae83 |
nei = ei_alloc(p, q, NULL, EI_F_INTERVAL_END);
|
|
Packit Service |
e7ae83 |
list_add_tail(&nei->list, list);
|
|
Packit Service |
e7ae83 |
}
|
|
Packit Service |
e7ae83 |
} else {
|
|
Packit Service |
e7ae83 |
/*
|
|
Packit Service |
e7ae83 |
* If the previous segment doesn't end directly left to
|
|
Packit Service |
e7ae83 |
* this one, insert a non-matching segment to cover
|
|
Packit Service |
e7ae83 |
* (prev_right, ei_left).
|
|
Packit Service |
e7ae83 |
*/
|
|
Packit Service |
e7ae83 |
mpz_add_ui(p, prev->right, 1);
|
|
Packit Service |
e7ae83 |
if (mpz_cmp(p, ei->left) < 0 ||
|
|
Packit Service |
e7ae83 |
(!(set->flags & NFT_SET_ANONYMOUS) && !merge)) {
|
|
Packit Service |
e7ae83 |
mpz_sub_ui(q, ei->left, 1);
|
|
Packit Service |
e7ae83 |
nei = ei_alloc(p, q, NULL, EI_F_INTERVAL_END);
|
|
Packit Service |
e7ae83 |
list_add_tail(&nei->list, list);
|
|
Packit Service |
e7ae83 |
} else if (add && merge &&
|
|
Packit Service |
e7ae83 |
ei->expr->etype != EXPR_MAPPING) {
|
|
Packit Service |
e7ae83 |
/* Merge contiguous segments only in case of
|
|
Packit Service |
e7ae83 |
* new additions.
|
|
Packit Service |
e7ae83 |
*/
|
|
Packit Service |
e7ae83 |
mpz_set(prev->right, ei->right);
|
|
Packit Service |
e7ae83 |
ei_remove(tree, ei);
|
|
Packit Service |
e7ae83 |
ei_destroy(ei);
|
|
Packit Service |
e7ae83 |
continue;
|
|
Packit Service |
e7ae83 |
}
|
|
Packit Service |
e7ae83 |
}
|
|
Packit Service |
e7ae83 |
|
|
Packit Service |
e7ae83 |
ei_remove(tree, ei);
|
|
Packit Service |
e7ae83 |
list_add_tail(&ei->list, list);
|
|
Packit Service |
e7ae83 |
|
|
Packit Service |
e7ae83 |
prev = ei;
|
|
Packit Service |
e7ae83 |
}
|
|
Packit Service |
e7ae83 |
|
|
Packit Service |
e7ae83 |
/*
|
|
Packit Service |
e7ae83 |
* If the last segment doesn't end at the right side of the dimension,
|
|
Packit Service |
e7ae83 |
* insert a non-matching segment to cover (last_right, end].
|
|
Packit Service |
e7ae83 |
*/
|
|
Packit Service |
e7ae83 |
if (mpz_scan0(prev->right, 0) != tree->keylen) {
|
|
Packit Service |
e7ae83 |
mpz_add_ui(p, prev->right, 1);
|
|
Packit Service |
e7ae83 |
mpz_bitmask(q, tree->keylen);
|
|
Packit Service |
e7ae83 |
nei = ei_alloc(p, q, NULL, EI_F_INTERVAL_END);
|
|
Packit Service |
e7ae83 |
list_add_tail(&nei->list, list);
|
|
Packit Service |
e7ae83 |
} else {
|
|
Packit Service |
e7ae83 |
prev->flags |= EI_F_INTERVAL_OPEN;
|
|
Packit Service |
e7ae83 |
}
|
|
Packit Service |
e7ae83 |
|
|
Packit Service |
e7ae83 |
mpz_clear(p);
|
|
Packit Service |
e7ae83 |
mpz_clear(q);
|
|
Packit Service |
e7ae83 |
}
|
|
Packit Service |
e7ae83 |
|
|
Packit Service |
e7ae83 |
static void set_insert_interval(struct expr *set, struct seg_tree *tree,
|
|
Packit Service |
e7ae83 |
const struct elementary_interval *ei)
|
|
Packit Service |
e7ae83 |
{
|
|
Packit Service |
e7ae83 |
struct expr *expr;
|
|
Packit Service |
e7ae83 |
|
|
Packit Service |
e7ae83 |
expr = constant_expr_alloc(&internal_location, tree->keytype,
|
|
Packit Service |
e7ae83 |
tree->byteorder, tree->keylen, NULL);
|
|
Packit Service |
e7ae83 |
mpz_set(expr->value, ei->left);
|
|
Packit Service |
e7ae83 |
expr = set_elem_expr_alloc(&internal_location, expr);
|
|
Packit Service |
e7ae83 |
|
|
Packit Service |
e7ae83 |
if (ei->expr != NULL) {
|
|
Packit Service |
e7ae83 |
if (ei->expr->etype == EXPR_MAPPING) {
|
|
Packit Service |
e7ae83 |
if (ei->expr->left->comment)
|
|
Packit Service |
e7ae83 |
expr->comment = xstrdup(ei->expr->left->comment);
|
|
Packit Service |
e7ae83 |
if (ei->expr->left->timeout)
|
|
Packit Service |
e7ae83 |
expr->timeout = ei->expr->left->timeout;
|
|
Packit Service |
e7ae83 |
expr = mapping_expr_alloc(&ei->expr->location, expr,
|
|
Packit Service |
e7ae83 |
expr_get(ei->expr->right));
|
|
Packit Service |
e7ae83 |
} else {
|
|
Packit Service |
e7ae83 |
if (ei->expr->comment)
|
|
Packit Service |
e7ae83 |
expr->comment = xstrdup(ei->expr->comment);
|
|
Packit Service |
e7ae83 |
if (ei->expr->timeout)
|
|
Packit Service |
e7ae83 |
expr->timeout = ei->expr->timeout;
|
|
Packit Service |
e7ae83 |
}
|
|
Packit Service |
e7ae83 |
}
|
|
Packit Service |
e7ae83 |
|
|
Packit Service |
e7ae83 |
if (ei->flags & EI_F_INTERVAL_END)
|
|
Packit Service |
e7ae83 |
expr->flags |= EXPR_F_INTERVAL_END;
|
|
Packit Service |
e7ae83 |
if (ei->flags & EI_F_INTERVAL_OPEN)
|
|
Packit Service |
e7ae83 |
expr->elem_flags |= NFTNL_SET_ELEM_F_INTERVAL_OPEN;
|
|
Packit Service |
e7ae83 |
|
|
Packit Service |
e7ae83 |
compound_expr_add(set, expr);
|
|
Packit Service |
e7ae83 |
}
|
|
Packit Service |
e7ae83 |
|
|
Packit Service |
e7ae83 |
int set_to_intervals(struct list_head *errs, struct set *set,
|
|
Packit Service |
e7ae83 |
struct expr *init, bool add, unsigned int debug_mask,
|
|
Packit Service |
e7ae83 |
bool merge, struct output_ctx *octx)
|
|
Packit Service |
e7ae83 |
{
|
|
Packit Service |
e7ae83 |
struct elementary_interval *ei, *next;
|
|
Packit Service |
e7ae83 |
struct seg_tree tree;
|
|
Packit Service |
e7ae83 |
LIST_HEAD(list);
|
|
Packit Service |
e7ae83 |
|
|
Packit Service |
e7ae83 |
seg_tree_init(&tree, set, init, debug_mask);
|
|
Packit Service |
e7ae83 |
if (set_to_segtree(errs, set, init, &tree, add, merge) < 0)
|
|
Packit Service |
e7ae83 |
return -1;
|
|
Packit Service |
e7ae83 |
segtree_linearize(&list, set, init, &tree, add, merge);
|
|
Packit Service |
e7ae83 |
|
|
Packit Service |
e7ae83 |
init->size = 0;
|
|
Packit Service |
e7ae83 |
list_for_each_entry_safe(ei, next, &list, list) {
|
|
Packit Service |
e7ae83 |
if (segtree_debug(tree.debug_mask)) {
|
|
Packit Service |
e7ae83 |
pr_gmp_debug("list: [%.*Zx %.*Zx]\n",
|
|
Packit Service |
e7ae83 |
2 * tree.keylen / BITS_PER_BYTE, ei->left,
|
|
Packit Service |
e7ae83 |
2 * tree.keylen / BITS_PER_BYTE, ei->right);
|
|
Packit Service |
e7ae83 |
}
|
|
Packit Service |
e7ae83 |
set_insert_interval(init, &tree, ei);
|
|
Packit Service |
e7ae83 |
ei_destroy(ei);
|
|
Packit Service |
e7ae83 |
}
|
|
Packit Service |
e7ae83 |
|
|
Packit Service |
e7ae83 |
if (segtree_debug(tree.debug_mask)) {
|
|
Packit Service |
e7ae83 |
expr_print(init, octx);
|
|
Packit Service |
e7ae83 |
pr_gmp_debug("\n");
|
|
Packit Service |
e7ae83 |
}
|
|
Packit Service |
e7ae83 |
|
|
Packit Service |
e7ae83 |
return 0;
|
|
Packit Service |
e7ae83 |
}
|
|
Packit Service |
e7ae83 |
|
|
Packit Service |
e7ae83 |
static void set_elem_add(const struct set *set, struct expr *init, mpz_t value,
|
|
Packit Service |
e7ae83 |
uint32_t flags, enum byteorder byteorder)
|
|
Packit Service |
e7ae83 |
{
|
|
Packit Service |
e7ae83 |
struct expr *expr;
|
|
Packit Service |
e7ae83 |
|
|
Packit Service |
e7ae83 |
expr = constant_expr_alloc(&internal_location, set->key->dtype,
|
|
Packit Service |
e7ae83 |
byteorder, set->key->len, NULL);
|
|
Packit Service |
e7ae83 |
mpz_set(expr->value, value);
|
|
Packit Service |
e7ae83 |
expr = set_elem_expr_alloc(&internal_location, expr);
|
|
Packit Service |
e7ae83 |
expr->flags = flags;
|
|
Packit Service |
e7ae83 |
|
|
Packit Service |
e7ae83 |
compound_expr_add(init, expr);
|
|
Packit Service |
e7ae83 |
}
|
|
Packit Service |
e7ae83 |
|
|
Packit Service |
e7ae83 |
struct expr *get_set_intervals(const struct set *set, const struct expr *init)
|
|
Packit Service |
e7ae83 |
{
|
|
Packit Service |
e7ae83 |
struct expr *new_init;
|
|
Packit Service |
e7ae83 |
mpz_t low, high;
|
|
Packit Service |
e7ae83 |
struct expr *i;
|
|
Packit Service |
e7ae83 |
|
|
Packit Service |
e7ae83 |
mpz_init2(low, set->key->len);
|
|
Packit Service |
e7ae83 |
mpz_init2(high, set->key->len);
|
|
Packit Service |
e7ae83 |
|
|
Packit Service |
e7ae83 |
new_init = list_expr_alloc(&internal_location);
|
|
Packit Service |
e7ae83 |
|
|
Packit Service |
e7ae83 |
list_for_each_entry(i, &init->expressions, list) {
|
|
Packit Service |
e7ae83 |
switch (i->key->etype) {
|
|
Packit Service |
e7ae83 |
case EXPR_VALUE:
|
|
Packit Service |
e7ae83 |
set_elem_add(set, new_init, i->key->value,
|
|
Packit Service |
e7ae83 |
i->flags, i->byteorder);
|
|
Packit Service |
e7ae83 |
break;
|
|
Packit Service |
c0b110 |
case EXPR_CONCAT:
|
|
Packit Service |
c0b110 |
compound_expr_add(new_init, expr_clone(i));
|
|
Packit Service |
c0b110 |
i->flags |= EXPR_F_INTERVAL_END;
|
|
Packit Service |
c0b110 |
compound_expr_add(new_init, expr_clone(i));
|
|
Packit Service |
c0b110 |
break;
|
|
Packit Service |
e7ae83 |
default:
|
|
Packit Service |
e7ae83 |
range_expr_value_low(low, i);
|
|
Packit Service |
e7ae83 |
set_elem_add(set, new_init, low, 0, i->byteorder);
|
|
Packit Service |
e7ae83 |
range_expr_value_high(high, i);
|
|
Packit Service |
e7ae83 |
mpz_add_ui(high, high, 1);
|
|
Packit Service |
e7ae83 |
set_elem_add(set, new_init, high,
|
|
Packit Service |
e7ae83 |
EXPR_F_INTERVAL_END, i->byteorder);
|
|
Packit Service |
e7ae83 |
break;
|
|
Packit Service |
e7ae83 |
}
|
|
Packit Service |
e7ae83 |
}
|
|
Packit Service |
e7ae83 |
|
|
Packit Service |
e7ae83 |
mpz_clear(low);
|
|
Packit Service |
e7ae83 |
mpz_clear(high);
|
|
Packit Service |
e7ae83 |
|
|
Packit Service |
e7ae83 |
return new_init;
|
|
Packit Service |
e7ae83 |
}
|
|
Packit Service |
e7ae83 |
|
|
Packit Service |
e7ae83 |
static struct expr *get_set_interval_find(const struct table *table,
|
|
Packit Service |
e7ae83 |
const char *set_name,
|
|
Packit Service |
e7ae83 |
struct expr *left,
|
|
Packit Service |
e7ae83 |
struct expr *right)
|
|
Packit Service |
e7ae83 |
{
|
|
Packit Service |
e7ae83 |
struct expr *range = NULL;
|
|
Packit Service |
e7ae83 |
struct set *set;
|
|
Packit Service |
e7ae83 |
struct expr *i;
|
|
Packit Service |
24b4eb |
mpz_t val;
|
|
Packit Service |
e7ae83 |
|
|
Packit Service |
e7ae83 |
set = set_lookup(table, set_name);
|
|
Packit Service |
24b4eb |
mpz_init2(val, set->key->len);
|
|
Packit Service |
e7ae83 |
|
|
Packit Service |
e7ae83 |
list_for_each_entry(i, &set->init->expressions, list) {
|
|
Packit Service |
e7ae83 |
switch (i->key->etype) {
|
|
Packit Service |
794692 |
case EXPR_PREFIX:
|
|
Packit Service |
e7ae83 |
case EXPR_RANGE:
|
|
Packit Service |
24b4eb |
range_expr_value_low(val, i);
|
|
Packit Service |
24b4eb |
if (left && mpz_cmp(left->key->value, val))
|
|
Packit Service |
24b4eb |
break;
|
|
Packit Service |
e7ae83 |
|
|
Packit Service |
24b4eb |
range_expr_value_high(val, i);
|
|
Packit Service |
24b4eb |
if (right && mpz_cmp(right->key->value, val))
|
|
Packit Service |
24b4eb |
break;
|
|
Packit Service |
e7ae83 |
|
|
Packit Service |
24b4eb |
range = expr_clone(i->key);
|
|
Packit Service |
24b4eb |
goto out;
|
|
Packit Service |
e7ae83 |
default:
|
|
Packit Service |
e7ae83 |
break;
|
|
Packit Service |
e7ae83 |
}
|
|
Packit Service |
e7ae83 |
}
|
|
Packit Service |
e7ae83 |
out:
|
|
Packit Service |
24b4eb |
mpz_clear(val);
|
|
Packit Service |
e7ae83 |
|
|
Packit Service |
e7ae83 |
return range;
|
|
Packit Service |
e7ae83 |
}
|
|
Packit Service |
e7ae83 |
|
|
Packit Service |
e7ae83 |
int get_set_decompose(struct table *table, struct set *set)
|
|
Packit Service |
e7ae83 |
{
|
|
Packit Service |
e7ae83 |
struct expr *i, *next, *range;
|
|
Packit Service |
e7ae83 |
struct expr *left = NULL;
|
|
Packit Service |
e7ae83 |
struct expr *new_init;
|
|
Packit Service |
e7ae83 |
|
|
Packit Service |
e7ae83 |
new_init = set_expr_alloc(&internal_location, set);
|
|
Packit Service |
e7ae83 |
|
|
Packit Service |
e7ae83 |
list_for_each_entry_safe(i, next, &set->init->expressions, list) {
|
|
Packit Service |
e7ae83 |
if (i->flags & EXPR_F_INTERVAL_END && left) {
|
|
Packit Service |
e7ae83 |
list_del(&left->list);
|
|
Packit Service |
e7ae83 |
list_del(&i->list);
|
|
Packit Service |
e7ae83 |
mpz_sub_ui(i->key->value, i->key->value, 1);
|
|
Packit Service |
e7ae83 |
range = get_set_interval_find(table, set->handle.set.name,
|
|
Packit Service |
e7ae83 |
left, i);
|
|
Packit Service |
e7ae83 |
if (!range) {
|
|
Packit Service |
e7ae83 |
expr_free(new_init);
|
|
Packit Service |
e7ae83 |
errno = ENOENT;
|
|
Packit Service |
e7ae83 |
return -1;
|
|
Packit Service |
e7ae83 |
}
|
|
Packit Service |
e7ae83 |
|
|
Packit Service |
e7ae83 |
compound_expr_add(new_init, range);
|
|
Packit Service |
e7ae83 |
left = NULL;
|
|
Packit Service |
e7ae83 |
} else {
|
|
Packit Service |
e7ae83 |
if (left) {
|
|
Packit Service |
24b4eb |
range = get_set_interval_find(table,
|
|
Packit Service |
24b4eb |
set->handle.set.name,
|
|
Packit Service |
24b4eb |
left, NULL);
|
|
Packit Service |
e7ae83 |
if (range)
|
|
Packit Service |
e7ae83 |
compound_expr_add(new_init, range);
|
|
Packit Service |
e7ae83 |
else
|
|
Packit Service |
e7ae83 |
compound_expr_add(new_init,
|
|
Packit Service |
e7ae83 |
expr_clone(left));
|
|
Packit Service |
e7ae83 |
}
|
|
Packit Service |
e7ae83 |
left = i;
|
|
Packit Service |
e7ae83 |
}
|
|
Packit Service |
e7ae83 |
}
|
|
Packit Service |
e7ae83 |
if (left) {
|
|
Packit Service |
24b4eb |
range = get_set_interval_find(table, set->handle.set.name,
|
|
Packit Service |
24b4eb |
left, NULL);
|
|
Packit Service |
e7ae83 |
if (range)
|
|
Packit Service |
e7ae83 |
compound_expr_add(new_init, range);
|
|
Packit Service |
e7ae83 |
else
|
|
Packit Service |
e7ae83 |
compound_expr_add(new_init, expr_clone(left));
|
|
Packit Service |
e7ae83 |
}
|
|
Packit Service |
e7ae83 |
|
|
Packit Service |
e7ae83 |
expr_free(set->init);
|
|
Packit Service |
e7ae83 |
set->init = new_init;
|
|
Packit Service |
e7ae83 |
|
|
Packit Service |
e7ae83 |
return 0;
|
|
Packit Service |
e7ae83 |
}
|
|
Packit Service |
e7ae83 |
|
|
Packit Service |
e7ae83 |
static bool range_is_prefix(const mpz_t range)
|
|
Packit Service |
e7ae83 |
{
|
|
Packit Service |
e7ae83 |
mpz_t tmp;
|
|
Packit Service |
e7ae83 |
bool ret;
|
|
Packit Service |
e7ae83 |
|
|
Packit Service |
e7ae83 |
mpz_init_set(tmp, range);
|
|
Packit Service |
e7ae83 |
mpz_add_ui(tmp, tmp, 1);
|
|
Packit Service |
e7ae83 |
mpz_and(tmp, range, tmp);
|
|
Packit Service |
e7ae83 |
ret = !mpz_cmp_ui(tmp, 0);
|
|
Packit Service |
e7ae83 |
mpz_clear(tmp);
|
|
Packit Service |
e7ae83 |
return ret;
|
|
Packit Service |
e7ae83 |
}
|
|
Packit Service |
e7ae83 |
|
|
Packit Service |
e7ae83 |
static struct expr *expr_value(struct expr *expr)
|
|
Packit Service |
e7ae83 |
{
|
|
Packit Service |
e7ae83 |
switch (expr->etype) {
|
|
Packit Service |
e7ae83 |
case EXPR_MAPPING:
|
|
Packit Service |
e7ae83 |
return expr->left->key;
|
|
Packit Service |
e7ae83 |
case EXPR_SET_ELEM:
|
|
Packit Service |
e7ae83 |
return expr->key;
|
|
Packit Service |
e7ae83 |
default:
|
|
Packit Service |
e7ae83 |
BUG("invalid expression type %s\n", expr_name(expr));
|
|
Packit Service |
e7ae83 |
}
|
|
Packit Service |
e7ae83 |
}
|
|
Packit Service |
e7ae83 |
|
|
Packit Service |
e7ae83 |
static int expr_value_cmp(const void *p1, const void *p2)
|
|
Packit Service |
e7ae83 |
{
|
|
Packit Service |
e7ae83 |
struct expr *e1 = *(void * const *)p1;
|
|
Packit Service |
e7ae83 |
struct expr *e2 = *(void * const *)p2;
|
|
Packit Service |
e7ae83 |
int ret;
|
|
Packit Service |
e7ae83 |
|
|
Packit Service |
c0b110 |
if (expr_value(e1)->etype == EXPR_CONCAT)
|
|
Packit Service |
c0b110 |
return -1;
|
|
Packit Service |
c0b110 |
|
|
Packit Service |
e7ae83 |
ret = mpz_cmp(expr_value(e1)->value, expr_value(e2)->value);
|
|
Packit Service |
e7ae83 |
if (ret == 0) {
|
|
Packit Service |
e7ae83 |
if (e1->flags & EXPR_F_INTERVAL_END)
|
|
Packit Service |
e7ae83 |
return -1;
|
|
Packit Service |
e7ae83 |
else if (e2->flags & EXPR_F_INTERVAL_END)
|
|
Packit Service |
e7ae83 |
return 1;
|
|
Packit Service |
e7ae83 |
}
|
|
Packit Service |
e7ae83 |
|
|
Packit Service |
e7ae83 |
return ret;
|
|
Packit Service |
e7ae83 |
}
|
|
Packit Service |
e7ae83 |
|
|
Packit Service |
c0b110 |
/* Given start and end elements of a range, check if it can be represented as
|
|
Packit Service |
c0b110 |
* a single netmask, and if so, how long, by returning zero or a positive value.
|
|
Packit Service |
c0b110 |
*/
|
|
Packit Service |
c0b110 |
static int range_mask_len(const mpz_t start, const mpz_t end, unsigned int len)
|
|
Packit Service |
c0b110 |
{
|
|
Packit Service |
c0b110 |
mpz_t tmp_start, tmp_end;
|
|
Packit Service |
c0b110 |
int ret;
|
|
Packit Service |
c0b110 |
|
|
Packit Service |
c0b110 |
mpz_init_set_ui(tmp_start, mpz_get_ui(start));
|
|
Packit Service |
c0b110 |
mpz_init_set_ui(tmp_end, mpz_get_ui(end));
|
|
Packit Service |
c0b110 |
|
|
Packit Service |
c0b110 |
while (mpz_cmp(tmp_start, tmp_end) <= 0 &&
|
|
Packit Service |
c0b110 |
!mpz_tstbit(tmp_start, 0) && mpz_tstbit(tmp_end, 0) &&
|
|
Packit Service |
c0b110 |
len--) {
|
|
Packit Service |
c0b110 |
mpz_fdiv_q_2exp(tmp_start, tmp_start, 1);
|
|
Packit Service |
c0b110 |
mpz_fdiv_q_2exp(tmp_end, tmp_end, 1);
|
|
Packit Service |
c0b110 |
}
|
|
Packit Service |
c0b110 |
|
|
Packit Service |
c0b110 |
ret = !mpz_cmp(tmp_start, tmp_end) ? (int)len : -1;
|
|
Packit Service |
c0b110 |
|
|
Packit Service |
c0b110 |
mpz_clear(tmp_start);
|
|
Packit Service |
c0b110 |
mpz_clear(tmp_end);
|
|
Packit Service |
c0b110 |
|
|
Packit Service |
c0b110 |
return ret;
|
|
Packit Service |
c0b110 |
}
|
|
Packit Service |
c0b110 |
|
|
Packit Service |
c0b110 |
/* Given a set with two elements (start and end), transform them into a
|
|
Packit Service |
c0b110 |
* concatenation of ranges. That is, from a list of start expressions and a list
|
|
Packit Service |
c0b110 |
* of end expressions, form a list of start - end expressions.
|
|
Packit Service |
c0b110 |
*/
|
|
Packit Service |
c0b110 |
void concat_range_aggregate(struct expr *set)
|
|
Packit Service |
c0b110 |
{
|
|
Packit Service |
c0b110 |
struct expr *i, *start = NULL, *end, *r1, *r2, *next, *r1_next, *tmp;
|
|
Packit Service |
c0b110 |
struct list_head *r2_next;
|
|
Packit Service |
c0b110 |
int prefix_len, free_r1;
|
|
Packit Service |
c0b110 |
mpz_t range, p;
|
|
Packit Service |
c0b110 |
|
|
Packit Service |
c0b110 |
list_for_each_entry_safe(i, next, &set->expressions, list) {
|
|
Packit Service |
c0b110 |
if (!start) {
|
|
Packit Service |
c0b110 |
start = i;
|
|
Packit Service |
c0b110 |
continue;
|
|
Packit Service |
c0b110 |
}
|
|
Packit Service |
c0b110 |
end = i;
|
|
Packit Service |
c0b110 |
|
|
Packit Service |
c0b110 |
/* Walk over r1 (start expression) and r2 (end) in parallel,
|
|
Packit Service |
c0b110 |
* form ranges between corresponding r1 and r2 expressions,
|
|
Packit Service |
c0b110 |
* store them by replacing r2 expressions, and free r1
|
|
Packit Service |
c0b110 |
* expressions.
|
|
Packit Service |
c0b110 |
*/
|
|
Packit Service |
c0b110 |
r2 = list_first_entry(&expr_value(end)->expressions,
|
|
Packit Service |
c0b110 |
struct expr, list);
|
|
Packit Service |
c0b110 |
list_for_each_entry_safe(r1, r1_next,
|
|
Packit Service |
c0b110 |
&expr_value(start)->expressions,
|
|
Packit Service |
c0b110 |
list) {
|
|
Packit Service |
c0b110 |
mpz_init(range);
|
|
Packit Service |
c0b110 |
mpz_init(p);
|
|
Packit Service |
c0b110 |
|
|
Packit Service |
c0b110 |
r2_next = r2->list.next;
|
|
Packit Service |
c0b110 |
free_r1 = 0;
|
|
Packit Service |
c0b110 |
|
|
Packit Service |
c0b110 |
if (!mpz_cmp(r1->value, r2->value)) {
|
|
Packit Service |
c0b110 |
free_r1 = 1;
|
|
Packit Service |
c0b110 |
goto next;
|
|
Packit Service |
c0b110 |
}
|
|
Packit Service |
c0b110 |
|
|
Packit Service |
c0b110 |
mpz_sub(range, r2->value, r1->value);
|
|
Packit Service |
c0b110 |
mpz_sub_ui(range, range, 1);
|
|
Packit Service |
c0b110 |
mpz_and(p, r1->value, range);
|
|
Packit Service |
c0b110 |
|
|
Packit Service |
c0b110 |
/* Check if we are forced, or if it's anyway preferable,
|
|
Packit Service |
c0b110 |
* to express the range as two points instead of a
|
|
Packit Service |
c0b110 |
* netmask.
|
|
Packit Service |
c0b110 |
*/
|
|
Packit Service |
c0b110 |
prefix_len = range_mask_len(r1->value, r2->value,
|
|
Packit Service |
c0b110 |
r1->len);
|
|
Packit Service |
c0b110 |
if (prefix_len < 0 ||
|
|
Packit Service |
c0b110 |
!(r1->dtype->flags & DTYPE_F_PREFIX)) {
|
|
Packit Service |
c0b110 |
tmp = range_expr_alloc(&r1->location, r1,
|
|
Packit Service |
c0b110 |
r2);
|
|
Packit Service |
c0b110 |
|
|
Packit Service |
c0b110 |
list_replace(&r2->list, &tmp->list);
|
|
Packit Service |
c0b110 |
r2_next = tmp->list.next;
|
|
Packit Service |
c0b110 |
} else {
|
|
Packit Service |
c0b110 |
tmp = prefix_expr_alloc(&r1->location, r1,
|
|
Packit Service |
c0b110 |
prefix_len);
|
|
Packit Service |
c0b110 |
tmp->len = r2->len;
|
|
Packit Service |
c0b110 |
|
|
Packit Service |
c0b110 |
list_replace(&r2->list, &tmp->list);
|
|
Packit Service |
c0b110 |
r2_next = tmp->list.next;
|
|
Packit Service |
c0b110 |
expr_free(r2);
|
|
Packit Service |
c0b110 |
}
|
|
Packit Service |
c0b110 |
|
|
Packit Service |
c0b110 |
next:
|
|
Packit Service |
c0b110 |
mpz_clear(p);
|
|
Packit Service |
c0b110 |
mpz_clear(range);
|
|
Packit Service |
c0b110 |
|
|
Packit Service |
c0b110 |
r2 = list_entry(r2_next, typeof(*r2), list);
|
|
Packit Service |
c0b110 |
compound_expr_remove(start, r1);
|
|
Packit Service |
c0b110 |
|
|
Packit Service |
c0b110 |
if (free_r1)
|
|
Packit Service |
c0b110 |
expr_free(r1);
|
|
Packit Service |
c0b110 |
}
|
|
Packit Service |
c0b110 |
|
|
Packit Service |
c0b110 |
compound_expr_remove(set, start);
|
|
Packit Service |
c0b110 |
expr_free(start);
|
|
Packit Service |
c0b110 |
start = NULL;
|
|
Packit Service |
c0b110 |
}
|
|
Packit Service |
c0b110 |
}
|
|
Packit Service |
c0b110 |
|
|
Packit Service |
e7ae83 |
void interval_map_decompose(struct expr *set)
|
|
Packit Service |
e7ae83 |
{
|
|
Packit Service |
e7ae83 |
struct expr **elements, **ranges;
|
|
Packit Service |
e7ae83 |
struct expr *i, *next, *low = NULL, *end;
|
|
Packit Service |
e7ae83 |
unsigned int n, m, size;
|
|
Packit Service |
e7ae83 |
mpz_t range, p;
|
|
Packit Service |
e7ae83 |
bool interval;
|
|
Packit Service |
e7ae83 |
|
|
Packit Service |
e7ae83 |
if (set->size == 0)
|
|
Packit Service |
e7ae83 |
return;
|
|
Packit Service |
e7ae83 |
|
|
Packit Service |
e7ae83 |
elements = xmalloc_array(set->size, sizeof(struct expr *));
|
|
Packit Service |
e7ae83 |
ranges = xmalloc_array(set->size * 2, sizeof(struct expr *));
|
|
Packit Service |
e7ae83 |
|
|
Packit Service |
e7ae83 |
mpz_init(range);
|
|
Packit Service |
e7ae83 |
mpz_init(p);
|
|
Packit Service |
e7ae83 |
|
|
Packit Service |
e7ae83 |
/* Sort elements */
|
|
Packit Service |
e7ae83 |
n = 0;
|
|
Packit Service |
e7ae83 |
list_for_each_entry_safe(i, next, &set->expressions, list) {
|
|
Packit Service |
e7ae83 |
compound_expr_remove(set, i);
|
|
Packit Service |
e7ae83 |
elements[n++] = i;
|
|
Packit Service |
e7ae83 |
}
|
|
Packit Service |
e7ae83 |
qsort(elements, n, sizeof(elements[0]), expr_value_cmp);
|
|
Packit Service |
e7ae83 |
size = n;
|
|
Packit Service |
e7ae83 |
|
|
Packit Service |
e7ae83 |
/* Transform points (single values) into half-closed intervals */
|
|
Packit Service |
e7ae83 |
n = 0;
|
|
Packit Service |
e7ae83 |
interval = false;
|
|
Packit Service |
e7ae83 |
for (m = 0; m < size; m++) {
|
|
Packit Service |
e7ae83 |
i = elements[m];
|
|
Packit Service |
e7ae83 |
|
|
Packit Service |
e7ae83 |
if (i->flags & EXPR_F_INTERVAL_END)
|
|
Packit Service |
e7ae83 |
interval = false;
|
|
Packit Service |
e7ae83 |
else if (interval) {
|
|
Packit Service |
e7ae83 |
end = expr_clone(i);
|
|
Packit Service |
e7ae83 |
end->flags |= EXPR_F_INTERVAL_END;
|
|
Packit Service |
e7ae83 |
ranges[n++] = end;
|
|
Packit Service |
e7ae83 |
} else
|
|
Packit Service |
e7ae83 |
interval = true;
|
|
Packit Service |
e7ae83 |
|
|
Packit Service |
e7ae83 |
ranges[n++] = i;
|
|
Packit Service |
e7ae83 |
}
|
|
Packit Service |
e7ae83 |
size = n;
|
|
Packit Service |
e7ae83 |
|
|
Packit Service |
e7ae83 |
for (n = 0; n < size; n++) {
|
|
Packit Service |
e7ae83 |
i = ranges[n];
|
|
Packit Service |
e7ae83 |
|
|
Packit Service |
e7ae83 |
if (low == NULL) {
|
|
Packit Service |
e7ae83 |
if (i->flags & EXPR_F_INTERVAL_END) {
|
|
Packit Service |
e7ae83 |
/*
|
|
Packit Service |
e7ae83 |
* End of interval mark
|
|
Packit Service |
e7ae83 |
*/
|
|
Packit Service |
e7ae83 |
expr_free(i);
|
|
Packit Service |
e7ae83 |
continue;
|
|
Packit Service |
e7ae83 |
} else {
|
|
Packit Service |
e7ae83 |
/*
|
|
Packit Service |
e7ae83 |
* Start a new interval
|
|
Packit Service |
e7ae83 |
*/
|
|
Packit Service |
e7ae83 |
low = i;
|
|
Packit Service |
e7ae83 |
continue;
|
|
Packit Service |
e7ae83 |
}
|
|
Packit Service |
e7ae83 |
}
|
|
Packit Service |
e7ae83 |
|
|
Packit Service |
e7ae83 |
mpz_sub(range, expr_value(i)->value, expr_value(low)->value);
|
|
Packit Service |
e7ae83 |
mpz_sub_ui(range, range, 1);
|
|
Packit Service |
e7ae83 |
|
|
Packit Service |
e7ae83 |
mpz_and(p, expr_value(low)->value, range);
|
|
Packit Service |
e7ae83 |
|
|
Packit Service |
e7ae83 |
if (!mpz_cmp_ui(range, 0))
|
|
Packit Service |
e7ae83 |
compound_expr_add(set, expr_get(low));
|
|
Packit Service |
e7ae83 |
else if ((!range_is_prefix(range) ||
|
|
Packit Service |
e7ae83 |
!(i->dtype->flags & DTYPE_F_PREFIX)) ||
|
|
Packit Service |
e7ae83 |
mpz_cmp_ui(p, 0)) {
|
|
Packit Service |
e7ae83 |
struct expr *tmp;
|
|
Packit Service |
e7ae83 |
|
|
Packit Service |
e7ae83 |
tmp = constant_expr_alloc(&low->location, low->dtype,
|
|
Packit Service |
e7ae83 |
low->byteorder, expr_value(low)->len,
|
|
Packit Service |
e7ae83 |
NULL);
|
|
Packit Service |
e7ae83 |
|
|
Packit Service |
e7ae83 |
mpz_add(range, range, expr_value(low)->value);
|
|
Packit Service |
e7ae83 |
mpz_set(tmp->value, range);
|
|
Packit Service |
e7ae83 |
|
|
Packit Service |
e7ae83 |
tmp = range_expr_alloc(&low->location,
|
|
Packit Service |
e7ae83 |
expr_clone(expr_value(low)),
|
|
Packit Service |
e7ae83 |
tmp);
|
|
Packit Service |
e7ae83 |
tmp = set_elem_expr_alloc(&low->location, tmp);
|
|
Packit Service |
e7ae83 |
|
|
Packit Service |
e7ae83 |
if (low->etype == EXPR_MAPPING) {
|
|
Packit Service |
e7ae83 |
if (low->left->comment)
|
|
Packit Service |
e7ae83 |
tmp->comment = xstrdup(low->left->comment);
|
|
Packit Service |
e7ae83 |
if (low->left->timeout)
|
|
Packit Service |
e7ae83 |
tmp->timeout = low->left->timeout;
|
|
Packit Service |
e7ae83 |
if (low->left->expiration)
|
|
Packit Service |
e7ae83 |
tmp->expiration = low->left->expiration;
|
|
Packit Service |
e7ae83 |
|
|
Packit Service |
e7ae83 |
tmp = mapping_expr_alloc(&tmp->location, tmp,
|
|
Packit Service |
e7ae83 |
expr_clone(low->right));
|
|
Packit Service |
e7ae83 |
} else {
|
|
Packit Service |
e7ae83 |
if (low->comment)
|
|
Packit Service |
e7ae83 |
tmp->comment = xstrdup(low->comment);
|
|
Packit Service |
e7ae83 |
if (low->timeout)
|
|
Packit Service |
e7ae83 |
tmp->timeout = low->timeout;
|
|
Packit Service |
e7ae83 |
if (low->expiration)
|
|
Packit Service |
e7ae83 |
tmp->expiration = low->expiration;
|
|
Packit Service |
e7ae83 |
}
|
|
Packit Service |
e7ae83 |
|
|
Packit Service |
e7ae83 |
compound_expr_add(set, tmp);
|
|
Packit Service |
e7ae83 |
} else {
|
|
Packit Service |
e7ae83 |
struct expr *prefix;
|
|
Packit Service |
e7ae83 |
unsigned int prefix_len;
|
|
Packit Service |
e7ae83 |
|
|
Packit Service |
e7ae83 |
prefix_len = expr_value(i)->len - mpz_scan0(range, 0);
|
|
Packit Service |
e7ae83 |
prefix = prefix_expr_alloc(&low->location,
|
|
Packit Service |
e7ae83 |
expr_clone(expr_value(low)),
|
|
Packit Service |
e7ae83 |
prefix_len);
|
|
Packit Service |
e7ae83 |
prefix->len = expr_value(i)->len;
|
|
Packit Service |
e7ae83 |
|
|
Packit Service |
e7ae83 |
prefix = set_elem_expr_alloc(&low->location, prefix);
|
|
Packit Service |
e7ae83 |
|
|
Packit Service |
e7ae83 |
if (low->etype == EXPR_MAPPING) {
|
|
Packit Service |
e7ae83 |
if (low->left->comment)
|
|
Packit Service |
e7ae83 |
prefix->comment = xstrdup(low->left->comment);
|
|
Packit Service |
e7ae83 |
if (low->left->timeout)
|
|
Packit Service |
e7ae83 |
prefix->timeout = low->left->timeout;
|
|
Packit Service |
e7ae83 |
if (low->left->expiration)
|
|
Packit Service |
e7ae83 |
prefix->expiration = low->left->expiration;
|
|
Packit Service |
e7ae83 |
|
|
Packit Service |
e7ae83 |
prefix = mapping_expr_alloc(&low->location, prefix,
|
|
Packit Service |
e7ae83 |
expr_clone(low->right));
|
|
Packit Service |
e7ae83 |
} else {
|
|
Packit Service |
e7ae83 |
if (low->comment)
|
|
Packit Service |
e7ae83 |
prefix->comment = xstrdup(low->comment);
|
|
Packit Service |
e7ae83 |
if (low->timeout)
|
|
Packit Service |
e7ae83 |
prefix->timeout = low->timeout;
|
|
Packit Service |
f5c3fb |
if (low->expiration)
|
|
Packit Service |
e7ae83 |
prefix->expiration = low->expiration;
|
|
Packit Service |
e7ae83 |
}
|
|
Packit Service |
e7ae83 |
|
|
Packit Service |
e7ae83 |
compound_expr_add(set, prefix);
|
|
Packit Service |
e7ae83 |
}
|
|
Packit Service |
e7ae83 |
|
|
Packit Service |
e7ae83 |
if (i->flags & EXPR_F_INTERVAL_END) {
|
|
Packit Service |
e7ae83 |
expr_free(low);
|
|
Packit Service |
e7ae83 |
low = NULL;
|
|
Packit Service |
e7ae83 |
}
|
|
Packit Service |
e7ae83 |
expr_free(i);
|
|
Packit Service |
e7ae83 |
}
|
|
Packit Service |
e7ae83 |
|
|
Packit Service |
e7ae83 |
if (!low) /* no unclosed interval at end */
|
|
Packit Service |
e7ae83 |
goto out;
|
|
Packit Service |
e7ae83 |
|
|
Packit Service |
e7ae83 |
i = constant_expr_alloc(&low->location, low->dtype,
|
|
Packit Service |
e7ae83 |
low->byteorder, expr_value(low)->len, NULL);
|
|
Packit Service |
e7ae83 |
mpz_init_bitmask(i->value, i->len);
|
|
Packit Service |
e7ae83 |
|
|
Packit Service |
e7ae83 |
if (!mpz_cmp(i->value, expr_value(low)->value)) {
|
|
Packit Service |
e7ae83 |
expr_free(i);
|
|
Packit Service |
e7ae83 |
i = low;
|
|
Packit Service |
e7ae83 |
} else {
|
|
Packit Service |
e7ae83 |
i = range_expr_alloc(&low->location, expr_value(low), i);
|
|
Packit Service |
e7ae83 |
i = set_elem_expr_alloc(&low->location, i);
|
|
Packit Service |
e7ae83 |
if (low->etype == EXPR_MAPPING)
|
|
Packit Service |
e7ae83 |
i = mapping_expr_alloc(&i->location, i, low->right);
|
|
Packit Service |
e7ae83 |
}
|
|
Packit Service |
e7ae83 |
|
|
Packit Service |
e7ae83 |
compound_expr_add(set, i);
|
|
Packit Service |
e7ae83 |
out:
|
|
Packit Service |
e7ae83 |
mpz_clear(range);
|
|
Packit Service |
e7ae83 |
mpz_clear(p);
|
|
Packit Service |
e7ae83 |
|
|
Packit Service |
e7ae83 |
xfree(ranges);
|
|
Packit Service |
e7ae83 |
xfree(elements);
|
|
Packit Service |
e7ae83 |
}
|