diff options
-rw-r--r-- | include/intervals.h | 3 | ||||
-rw-r--r-- | src/cache.c | 6 | ||||
-rw-r--r-- | src/evaluate.c | 8 | ||||
-rw-r--r-- | src/intervals.c | 144 | ||||
-rw-r--r-- | src/rule.c | 10 | ||||
-rwxr-xr-x | tests/shell/testcases/sets/0069interval_merge_0 | 28 | ||||
-rw-r--r-- | tests/shell/testcases/sets/dumps/0069interval_merge_0.nft | 9 |
7 files changed, 168 insertions, 40 deletions
diff --git a/include/intervals.h b/include/intervals.h index f6980063..797129fc 100644 --- a/include/intervals.h +++ b/include/intervals.h @@ -2,7 +2,8 @@ #define NFTABLES_INTERVALS_H void set_to_range(struct expr *init); -int set_automerge(struct list_head *msgs, struct set *set, struct expr *init); +int set_automerge(struct list_head *msgs, struct cmd *cmd, struct set *set, + struct expr *init, unsigned int debug_mask); int set_overlap(struct list_head *msgs, struct set *set, struct expr *init); int set_to_intervals(const struct set *set, struct expr *init, bool add); diff --git a/src/cache.c b/src/cache.c index 8e8387f9..fd8df884 100644 --- a/src/cache.c +++ b/src/cache.c @@ -19,6 +19,8 @@ static unsigned int evaluate_cache_add(struct cmd *cmd, unsigned int flags) { + struct set *set; + switch (cmd->obj) { case CMD_OBJ_TABLE: if (!cmd->table) @@ -29,6 +31,10 @@ static unsigned int evaluate_cache_add(struct cmd *cmd, unsigned int flags) NFT_CACHE_SET | NFT_CACHE_OBJECT | NFT_CACHE_FLOWTABLE; + list_for_each_entry(set, &cmd->table->sets, list) { + if (set->automerge) + flags |= NFT_CACHE_SETELEM_MAYBE; + } break; case CMD_OBJ_CHAIN: case CMD_OBJ_SET: diff --git a/src/evaluate.c b/src/evaluate.c index 5ea3bff0..7f748c49 100644 --- a/src/evaluate.c +++ b/src/evaluate.c @@ -1478,10 +1478,12 @@ static int interval_set_eval(struct eval_ctx *ctx, struct set *set, switch (ctx->cmd->op) { case CMD_CREATE: case CMD_ADD: - if (set->automerge) - ret = set_automerge(ctx->msgs, set, init); - else + if (set->automerge) { + ret = set_automerge(ctx->msgs, ctx->cmd, set, init, + ctx->nft->debug_mask); + } else { ret = set_overlap(ctx->msgs, set, init); + } break; case CMD_DELETE: set_to_range(init); diff --git a/src/intervals.c b/src/intervals.c index c6f66e63..16debf9c 100644 --- a/src/intervals.c +++ b/src/intervals.c @@ -51,11 +51,33 @@ static void setelem_expr_to_range(struct expr *expr) } } -static void remove_overlapping_range(struct expr *i, struct expr *init) +struct set_automerge_ctx { + struct set *set; + struct expr *init; + struct expr *purge; + unsigned int debug_mask; +}; + +static void purge_elem(struct set_automerge_ctx *ctx, struct expr *i) { + if (ctx->debug_mask & NFT_DEBUG_SEGTREE) { + pr_gmp_debug("remove: [%Zx-%Zx]\n", + i->key->left->value, + i->key->right->value); + } + list_move_tail(&i->list, &ctx->purge->expressions); +} + +static void remove_overlapping_range(struct set_automerge_ctx *ctx, + struct expr *prev, struct expr *i) +{ + if (i->flags & EXPR_F_KERNEL) { + purge_elem(ctx, i); + return; + } list_del(&i->list); expr_free(i); - init->size--; + ctx->init->size--; } struct range { @@ -63,20 +85,33 @@ struct range { mpz_t high; }; -static void merge_ranges(struct expr *prev, struct expr *i, - struct range *prev_range, struct range *range, - struct expr *init) +static bool merge_ranges(struct set_automerge_ctx *ctx, + struct expr *prev, struct expr *i, + struct range *prev_range, struct range *range) { - expr_free(prev->key->right); - prev->key->right = expr_get(i->key->right); - list_del(&i->list); - expr_free(i); - mpz_set(prev_range->high, range->high); - init->size--; + if (prev->flags & EXPR_F_KERNEL) { + purge_elem(ctx, prev); + expr_free(i->key->left); + i->key->left = expr_get(prev->key->left); + mpz_set(prev_range->high, range->high); + return true; + } else if (i->flags & EXPR_F_KERNEL) { + purge_elem(ctx, i); + expr_free(prev->key->right); + prev->key->right = expr_get(i->key->right); + mpz_set(prev_range->high, range->high); + } else { + expr_free(prev->key->right); + prev->key->right = expr_get(i->key->right); + mpz_set(prev_range->high, range->high); + list_del(&i->list); + expr_free(i); + ctx->init->size--; + } + return false; } -static void setelem_automerge(struct list_head *msgs, struct set *set, - struct expr *init) +static void setelem_automerge(struct set_automerge_ctx *ctx) { struct expr *i, *next, *prev = NULL; struct range range, prev_range; @@ -88,7 +123,7 @@ static void setelem_automerge(struct list_head *msgs, struct set *set, mpz_init(range.high); mpz_init(rop); - list_for_each_entry_safe(i, next, &init->expressions, list) { + list_for_each_entry_safe(i, next, &ctx->init->expressions, list) { if (i->key->etype == EXPR_SET_ELEM_CATCHALL) continue; @@ -104,16 +139,18 @@ static void setelem_automerge(struct list_head *msgs, struct set *set, if (mpz_cmp(prev_range.low, range.low) <= 0 && mpz_cmp(prev_range.high, range.high) >= 0) { - remove_overlapping_range(i, init); + remove_overlapping_range(ctx, prev, i); continue; } else if (mpz_cmp(range.low, prev_range.high) <= 0) { - merge_ranges(prev, i, &prev_range, &range, init); + if (merge_ranges(ctx, prev, i, &prev_range, &range)) + prev = i; continue; - } else if (set->automerge) { + } else if (ctx->set->automerge) { mpz_sub(rop, range.low, prev_range.high); /* two contiguous ranges */ if (mpz_cmp_ui(rop, 1) == 0) { - merge_ranges(prev, i, &prev_range, &range, init); + if (merge_ranges(ctx, prev, i, &prev_range, &range)) + prev = i; continue; } } @@ -157,18 +194,63 @@ void set_to_range(struct expr *init) elem = interval_expr_key(i); setelem_expr_to_range(elem); } - - list_expr_sort(&init->expressions); } -int set_automerge(struct list_head *msgs, struct set *set, struct expr *init) +int set_automerge(struct list_head *msgs, struct cmd *cmd, struct set *set, + struct expr *init, unsigned int debug_mask) { + struct set *existing_set = set->existing_set; + struct set_automerge_ctx ctx = { + .set = set, + .init = init, + .debug_mask = debug_mask, + }; + struct expr *i, *next, *clone; + struct cmd *purge_cmd; + struct handle h = {}; + + if (existing_set) { + if (existing_set->init) { + list_splice_init(&existing_set->init->expressions, + &init->expressions); + } else { + existing_set->init = set_expr_alloc(&internal_location, + set); + } + } + set_to_range(init); + list_expr_sort(&init->expressions); if (set->flags & NFT_SET_MAP) return 0; - setelem_automerge(msgs, set, init); + ctx.purge = set_expr_alloc(&internal_location, set); + + setelem_automerge(&ctx); + + list_for_each_entry_safe(i, next, &init->expressions, list) { + if (i->flags & EXPR_F_KERNEL) { + list_move_tail(&i->list, &existing_set->init->expressions); + } else if (existing_set) { + if (debug_mask & NFT_DEBUG_SEGTREE) { + pr_gmp_debug("add: [%Zx-%Zx]\n", + i->key->left->value, i->key->right->value); + } + clone = expr_clone(i); + list_add_tail(&clone->list, &existing_set->init->expressions); + } + } + + if (list_empty(&ctx.purge->expressions)) { + expr_free(ctx.purge); + return 0; + } + + handle_merge(&h, &set->handle); + purge_cmd = cmd_alloc(CMD_DELETE, CMD_OBJ_ELEMENTS, &h, &init->location, ctx.purge); + purge_cmd->elem.set = set_get(set); + list_add_tail(&purge_cmd->list, &cmd->list); return 0; } @@ -250,21 +332,31 @@ err_out: int set_overlap(struct list_head *msgs, struct set *set, struct expr *init) { struct set *existing_set = set->existing_set; - struct expr *i, *n; + struct expr *i, *n, *clone; int err; - if (existing_set && existing_set->init) { - list_splice_init(&existing_set->init->expressions, - &init->expressions); + if (existing_set) { + if (existing_set->init) { + list_splice_init(&existing_set->init->expressions, + &init->expressions); + } else { + existing_set->init = set_expr_alloc(&internal_location, + set); + } } set_to_range(init); + list_expr_sort(&init->expressions); err = setelem_overlap(msgs, set, init); list_for_each_entry_safe(i, n, &init->expressions, list) { if (i->flags & EXPR_F_KERNEL) list_move_tail(&i->list, &existing_set->init->expressions); + else if (existing_set) { + clone = expr_clone(i); + list_add_tail(&clone->list, &existing_set->init->expressions); + } } return err; @@ -1476,16 +1476,6 @@ static int __do_add_elements(struct netlink_ctx *ctx, struct set *set, if (mnl_nft_setelem_add(ctx, set, expr, flags) < 0) return -1; - if (!set_is_anonymous(set->flags) && - set->init != NULL && set->init != expr && - set->flags & NFT_SET_INTERVAL && - set->desc.field_count <= 1) { - interval_map_decompose(expr); - list_splice_tail_init(&expr->expressions, &set->init->expressions); - set->init->size += expr->size; - expr->size = 0; - } - return 0; } diff --git a/tests/shell/testcases/sets/0069interval_merge_0 b/tests/shell/testcases/sets/0069interval_merge_0 new file mode 100755 index 00000000..edb6422a --- /dev/null +++ b/tests/shell/testcases/sets/0069interval_merge_0 @@ -0,0 +1,28 @@ +#!/bin/bash + +set -e + +RULESET="table ip x { + set y { + type ipv4_addr + flags interval + auto-merge + elements = { 1.2.3.0, 1.2.3.255, 1.2.3.0/24, 3.3.3.3, 4.4.4.4, 4.4.4.4-4.4.4.8, 3.3.3.4, 3.3.3.5 } + } +}" + +$NFT -f - <<< $RULESET + +RULESET="table ip x { + set y { + type ipv4_addr + flags interval + auto-merge + elements = { 1.2.4.0, 3.3.3.6, 4.4.4.0/24 } + } +}" + +$NFT -f - <<< $RULESET + +$NFT add element ip x y { 1.2.3.0-1.2.4.255, 3.3.3.5, 4.4.4.1 } +$NFT add element ip x y { 1.2.3.0-1.2.4.255, 3.3.3.5, 4.4.5.0 } diff --git a/tests/shell/testcases/sets/dumps/0069interval_merge_0.nft b/tests/shell/testcases/sets/dumps/0069interval_merge_0.nft new file mode 100644 index 00000000..2d4e1706 --- /dev/null +++ b/tests/shell/testcases/sets/dumps/0069interval_merge_0.nft @@ -0,0 +1,9 @@ +table ip x { + set y { + type ipv4_addr + flags interval + auto-merge + elements = { 1.2.3.0-1.2.4.255, 3.3.3.3-3.3.3.6, + 4.4.4.0-4.4.5.0 } + } +} |