So users can better track their ruleset via git. Without sorting, the elements can be listed in a different order every time the set is created, generating unnecessary git changes.
Mergesort is used. Doesn't sort sets with 'flags interval' set on. Signed-off-by: Elise Lennion <[email protected]> --- include/expression.h | 1 + src/Makefile.am | 1 + src/mergesort.c | 100 +++++++++++++++++++++++++++++++++++++++++++++++++++ src/netlink.c | 4 +++ 4 files changed, 106 insertions(+) create mode 100644 src/mergesort.c diff --git a/include/expression.h b/include/expression.h index 71e9c43..ec90265 100644 --- a/include/expression.h +++ b/include/expression.h @@ -396,6 +396,7 @@ extern struct expr *range_expr_alloc(const struct location *loc, extern void compound_expr_add(struct expr *compound, struct expr *expr); extern void compound_expr_remove(struct expr *compound, struct expr *expr); +extern void list_expr_sort(struct list_head *head); extern struct expr *concat_expr_alloc(const struct location *loc); diff --git a/src/Makefile.am b/src/Makefile.am index 2a69e19..65cb4b4 100644 --- a/src/Makefile.am +++ b/src/Makefile.am @@ -53,6 +53,7 @@ nft_SOURCES = main.c \ mnl.c \ iface.c \ services.c \ + mergesort.c \ scanner.l \ parser_bison.y diff --git a/src/mergesort.c b/src/mergesort.c new file mode 100644 index 0000000..a835320 --- /dev/null +++ b/src/mergesort.c @@ -0,0 +1,100 @@ +/* + * Copyright (c) 2017 Elise Lennion <[email protected]> + * + * This program is free software; you can redistribute it and/or modify + * it under the terms of the GNU General Public License version 2 as + * published by the Free Software Foundation. + */ + +#include <stdint.h> +#include <expression.h> +#include <gmputil.h> +#include <list.h> + +static int expr_msort_cmp(const struct expr *e1, const struct expr *e2); + +static int concat_expr_msort_cmp(const struct expr *e1, const struct expr *e2) +{ + struct list_head *l = (&e2->expressions)->next; + const struct expr *i1, *i2; + int ret; + + list_for_each_entry(i1, &e1->expressions, list) { + i2 = list_entry(l, typeof(struct expr), list); + + ret = expr_msort_cmp(i1, i2); + if (ret) + return ret; + + l = l->next; + } + + return false; +} + +static int expr_msort_cmp(const struct expr *e1, const struct expr *e2) +{ + switch (e1->ops->type) { + case EXPR_SET_ELEM: + return expr_msort_cmp(e1->key, e2->key); + case EXPR_VALUE: + return mpz_cmp(e1->value, e2->value); + case EXPR_CONCAT: + return concat_expr_msort_cmp(e1, e2); + case EXPR_MAPPING: + return expr_msort_cmp(e1->left, e2->left); + default: + BUG("Unknown expression %s\n", e1->ops->name); + } +} + +static void list_splice_sorted(struct list_head *list, struct list_head *head) +{ + struct list_head *h = head->next; + struct list_head *l = list->next; + + while (l != list) { + if (h == head || + expr_msort_cmp(list_entry(l, typeof(struct expr), list), + list_entry(h, typeof(struct expr), list)) < 0) { + l = l->next; + list_add_tail(l->prev, h); + continue; + } + + h = h->next; + } +} + +static void list_cut_middle(struct list_head *list, struct list_head *head) +{ + struct list_head *s = head->next; + struct list_head *e = head->prev; + + while (e != s) { + e = e->prev; + + if (e != s) + s = s->next; + } + + __list_cut_position(list, head, s); +} + +void list_expr_sort(struct list_head *head) +{ + struct list_head *list; + LIST_HEAD(temp); + + list = &temp; + + if (list_empty(head) || list_is_singular(head)) + return; + + list_cut_middle(list, head); + + list_expr_sort(head); + list_expr_sort(list); + + list_splice_sorted(list, head); +} diff --git a/src/netlink.c b/src/netlink.c index 5f478ff..4135f25 100644 --- a/src/netlink.c +++ b/src/netlink.c @@ -1666,6 +1666,10 @@ int netlink_get_setelems(struct netlink_ctx *ctx, const struct handle *h, ctx->set = set; set->init = set_expr_alloc(loc); nftnl_set_elem_foreach(nls, list_setelem_cb, ctx); + + if (!(set->flags & NFT_SET_INTERVAL)) + list_expr_sort(&ctx->set->init->expressions); + nftnl_set_free(nls); ctx->set = NULL; -- 2.7.4 -- To unsubscribe from this list: send the line "unsubscribe netfilter-devel" in the body of a message to [email protected] More majordomo info at http://vger.kernel.org/majordomo-info.html
