From patchwork Fri Jan 6 21:43:32 2017 Content-Type: text/plain; charset="utf-8" MIME-Version: 1.0 Content-Transfer-Encoding: 7bit X-Patchwork-Submitter: Elise Lennion X-Patchwork-Id: 712176 X-Patchwork-Delegate: pablo@netfilter.org Return-Path: X-Original-To: incoming@patchwork.ozlabs.org Delivered-To: patchwork-incoming@bilbo.ozlabs.org Received: from vger.kernel.org (vger.kernel.org [209.132.180.67]) by ozlabs.org (Postfix) with ESMTP id 3twJ2k3F1Xz9sCG for ; Sat, 7 Jan 2017 08:43:42 +1100 (AEDT) Authentication-Results: ozlabs.org; dkim=fail reason="signature verification failed" (2048-bit key; unprotected) header.d=gmail.com header.i=@gmail.com header.b="bq0oRC81"; dkim-atps=neutral Received: (majordomo@vger.kernel.org) by vger.kernel.org via listexpand id S964999AbdAFVnk (ORCPT ); Fri, 6 Jan 2017 16:43:40 -0500 Received: from mail-yw0-f194.google.com ([209.85.161.194]:34896 "EHLO mail-yw0-f194.google.com" rhost-flags-OK-OK-OK-OK) by vger.kernel.org with ESMTP id S1753506AbdAFVnj (ORCPT ); Fri, 6 Jan 2017 16:43:39 -0500 Received: by mail-yw0-f194.google.com with SMTP id 17so5254041ywk.2 for ; Fri, 06 Jan 2017 13:43:39 -0800 (PST) DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=gmail.com; s=20161025; h=date:from:to:cc:subject:message-id:mime-version:content-disposition :user-agent; bh=rLioVWEwEJs5tjmUR+SXDyJDTfFYKd6kKmu1gAdnXiw=; b=bq0oRC814MxOLUk+N3dqOSIJrj8Xy93y6TfoVIwRdvcHTTA2SP45r9bSANhOTvlG2I APABGtEwJ04+KbjqAPp8Hrs3STPySsxLQ/YRXZY7Jswy/qkInalSbm6po9rt7tzCO2e9 egKYReWN2PgGQ2jLRT18VqifaRxZa2jEbLDoix10K4IIrR5auP1sC/9MKp+t9KRwDhZv duI858aWHN9IaXWJS32c/3iX71EM9ao5Z/w1nD1LvI/YigAK9LSqajVsnv+XevWHPmAu v6v/n4ssRrt3/bUY0iFj4bjzZWxqG49wxqcyCT8acCIAK9LOs5NY3eiLpAz5oJHjYvYM f9KA== X-Google-DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=1e100.net; s=20161025; h=x-gm-message-state:date:from:to:cc:subject:message-id:mime-version :content-disposition:user-agent; bh=rLioVWEwEJs5tjmUR+SXDyJDTfFYKd6kKmu1gAdnXiw=; b=FiQqEj/HCppEf5gQvpjMJn8tt7wHlZVIKMBLwCs7GgM5+EQ9IOJPX3tmz76WcctjOm /qiCN5oGuPy7wvhd2ICwPesA3Ca9pBVzNcNMZJ2QAzuOCAAILaoUynmYKE2C0T42D4sf bvGT6vRkcRrtZZZI1fP8e2vDsNOdwwF3lcm+mgsYyFWUg1WC6BbmzfgukoC5fu5E1rYr 33oD0eRsx1nN8mbhPNocaoGO9IpY+b+zwS3iQcoBZJPKoNPbOKAnmNfJ/AdKAOB6e5c3 8sLwdA0m9R80tt8x1lcmhB2/N8ewv670f1LCKML2RoHqtfzyhDBvX2WrJgRkoEV5ZOhX zsbw== X-Gm-Message-State: AIkVDXI8KWPIxlbwsFwV2aMSwMtExh5LZe4Zp8TDNqA3xugBgboTjtid/UymxEmdEBVwEQ== X-Received: by 10.13.201.65 with SMTP id l62mr81909581ywd.96.1483739018739; Fri, 06 Jan 2017 13:43:38 -0800 (PST) Received: from lennorien.com ([201.82.188.69]) by smtp.gmail.com with ESMTPSA id b187sm33877088ywf.14.2017.01.06.13.43.37 (version=TLS1_2 cipher=ECDHE-RSA-AES128-GCM-SHA256 bits=128/128); Fri, 06 Jan 2017 13:43:38 -0800 (PST) Date: Fri, 6 Jan 2017 19:43:32 -0200 From: Elise Lennion To: pablo@netfilter.org Cc: netfilter-devel@vger.kernel.org Subject: [PATCH nft 1/2] src: sort set elements in netlink_get_setelems() Message-ID: <20170106214331.GA3265@lennorien.com> MIME-Version: 1.0 Content-Disposition: inline User-Agent: Mutt/1.5.24 (2015-08-30) Sender: netfilter-devel-owner@vger.kernel.org Precedence: bulk List-ID: X-Mailing-List: netfilter-devel@vger.kernel.org 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 --- 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 + * + * 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 +#include +#include +#include + +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;