From patchwork Tue Oct 17 09:22:50 2017 Content-Type: text/plain; charset="utf-8" MIME-Version: 1.0 Content-Transfer-Encoding: 7bit X-Patchwork-Submitter: Wei Li X-Patchwork-Id: 826868 Return-Path: X-Original-To: incoming@patchwork.ozlabs.org Delivered-To: patchwork-incoming@bilbo.ozlabs.org Authentication-Results: ozlabs.org; spf=pass (mailfrom) smtp.mailfrom=openvswitch.org (client-ip=140.211.169.12; helo=mail.linuxfoundation.org; envelope-from=ovs-dev-bounces@openvswitch.org; receiver=) Received: from mail.linuxfoundation.org (mail.linuxfoundation.org [140.211.169.12]) (using TLSv1.2 with cipher ECDHE-RSA-AES256-GCM-SHA384 (256/256 bits)) (No client certificate requested) by ozlabs.org (Postfix) with ESMTPS id 3yGV915WzNz9sRm for ; Tue, 17 Oct 2017 20:23:01 +1100 (AEDT) Received: from mail.linux-foundation.org (localhost [127.0.0.1]) by mail.linuxfoundation.org (Postfix) with ESMTP id 6ECD6A74; Tue, 17 Oct 2017 09:22:58 +0000 (UTC) X-Original-To: dev@openvswitch.org Delivered-To: ovs-dev@mail.linuxfoundation.org Received: from smtp1.linuxfoundation.org (smtp1.linux-foundation.org [172.17.192.35]) by mail.linuxfoundation.org (Postfix) with ESMTPS id 0AE159BA for ; Tue, 17 Oct 2017 09:22:57 +0000 (UTC) X-Greylist: domain auto-whitelisted by SQLgrey-1.7.6 Received: from smtp2203-239.mail.aliyun.com (smtp2203-239.mail.aliyun.com [121.197.203.239]) by smtp1.linuxfoundation.org (Postfix) with ESMTPS id 5CB2846B for ; Tue, 17 Oct 2017 09:22:55 +0000 (UTC) X-Alimail-AntiSpam: AC=CONTINUE; BC=0.08259125|-1; FP=0|0|0|0|0|-1|-1|-1; HT=e02c03312; MF=liw@dtdream.com; NM=1; PH=DS; RN=1; RT=1; SR=0; TI=SMTPD_---.9A1i-5a_1508232171; Received: from DESKTOP-LBPO59B.local(mailfrom:liw@dtdream.com ip:222.128.6.202) by smtp.aliyun-inc.com(10.147.42.198); Tue, 17 Oct 2017 17:22:51 +0800 Date: Tue, 17 Oct 2017 17:22:50 +0800 From: wei To: dev@openvswitch.org Message-ID: <5c7b0dc8-8686-4263-99f0-2fe2edcdfc18@DESKTOP-LBPO59B.local> X-Mailer: TortoiseGit MIME-Version: 1.0 X-Spam-Status: No, score=0.0 required=5.0 tests=UNPARSEABLE_RELAY autolearn=disabled version=3.3.1 X-Spam-Checker-Version: SpamAssassin 3.3.1 (2010-03-16) on smtp1.linux-foundation.org Subject: [ovs-dev] [PATCH] Reduce the number of flows by use conjunction action X-BeenThere: ovs-dev@openvswitch.org X-Mailman-Version: 2.1.12 Precedence: list List-Id: List-Unsubscribe: , List-Archive: List-Post: List-Help: List-Subscribe: , Sender: ovs-dev-bounces@openvswitch.org Errors-To: ovs-dev-bounces@openvswitch.org This patch convert ovn-sb lflow expr "(1 or 2) and (3 or 4)" to match 1 aciton connjunction(1, 1/2) match 2 aciton connjunction(1, 1/2) match 3 aciton connjunction(1, 2/2) match 4 aciton connjunction(1, 2/2) match conj_id=1, action= NOT support nested conjunction, only use conjunction action in situation "or in level 1" Like (1 or 2) and (3 or ((4 or 5) and (6 or 7))), (4 or 5) and (6 or 7) will not be converted conjunction action, We could call this situation as "or in level 2", in this situation (4 or 5) and (6 or 7) will be crossproduct, so (1 or 2) and (3 or ((4 or 5) and (6 or 7))) -> (1 or 2) and (3 or (4 and 6) or (4 and 7) or (5 and 6) or (5 and 7)) In openstack, security group rule will match remote security group and tcp port, like match=(ip4.src == $as_ip4_6a8f4283_ba60_4d1c_9dec_28d027eadef2 && tcp.dst >= 10000 && tcp.dst <= 20000)) Use this patch, the number of flows will be significantly reduced Signed-off-by: wei --- ovn/lib/expr.c | 95 ++++++++++++++++++++++++++++++++++++++++------------------ 1 file changed, 66 insertions(+), 29 deletions(-) diff --git a/ovn/lib/expr.c b/ovn/lib/expr.c index 79ff45762..11abd7eca 100644 --- a/ovn/lib/expr.c +++ b/ovn/lib/expr.c @@ -2426,12 +2426,12 @@ expr_sort(struct expr *expr) return expr; } -static struct expr *expr_normalize_or(struct expr *expr); +static struct expr *expr_normalize_or(struct expr *expr, int level); /* Returns 'expr', which is an AND, reduced to OR(AND(clause)) where * a clause is a cmp or a disjunction of cmps on a single field. */ static struct expr * -expr_normalize_and(struct expr *expr) +expr_normalize_and(struct expr *expr, int level) { ovs_assert(expr->type == EXPR_T_AND); @@ -2472,40 +2472,55 @@ expr_normalize_and(struct expr *expr) } ovs_assert(sub->type == EXPR_T_OR); - const struct expr_symbol *symbol = expr_is_cmp(sub); - if (!symbol || symbol->must_crossproduct) { - struct expr *or = expr_create_andor(EXPR_T_OR); - struct expr *k; - - LIST_FOR_EACH (k, node, &sub->andor) { - struct expr *and = expr_create_andor(EXPR_T_AND); - struct expr *m; - - LIST_FOR_EACH (m, node, &expr->andor) { - struct expr *term = m == sub ? k : m; - if (term->type == EXPR_T_AND) { - struct expr *p; - - LIST_FOR_EACH (p, node, &term->andor) { - struct expr *new = expr_clone(p); + if (level == 0) { + LIST_FOR_EACH_SAFE (a, b, node, &sub->andor) { + if (a->type == EXPR_T_CMP) { + continue; + } else if (a->type == EXPR_T_AND) { + ovs_list_remove(&a->node); + struct expr *new = expr_normalize_and(a, ++level); + ovs_assert(new->type == EXPR_T_CMP || new->type == EXPR_T_AND || new->type == EXPR_T_OR); + expr_insert_andor(sub, b, new); + } else { + OVS_NOT_REACHED(); + } + } + } else { + const struct expr_symbol *symbol = expr_is_cmp(sub); + if (!symbol || symbol->must_crossproduct) { + struct expr *or = expr_create_andor(EXPR_T_OR); + struct expr *k; + + LIST_FOR_EACH (k, node, &sub->andor) { + struct expr *and = expr_create_andor(EXPR_T_AND); + struct expr *m; + + LIST_FOR_EACH (m, node, &expr->andor) { + struct expr *term = m == sub ? k : m; + if (term->type == EXPR_T_AND) { + struct expr *p; + + LIST_FOR_EACH (p, node, &term->andor) { + struct expr *new = expr_clone(p); + ovs_list_push_back(&and->andor, &new->node); + } + } else { + struct expr *new = expr_clone(term); ovs_list_push_back(&and->andor, &new->node); } - } else { - struct expr *new = expr_clone(term); - ovs_list_push_back(&and->andor, &new->node); } + ovs_list_push_back(&or->andor, &and->node); } - ovs_list_push_back(&or->andor, &and->node); + expr_destroy(expr); + return expr_normalize_or(or, ++level); } - expr_destroy(expr); - return expr_normalize_or(or); } } return expr; } static struct expr * -expr_normalize_or(struct expr *expr) +expr_normalize_or(struct expr *expr, int level) { struct expr *sub, *next; @@ -2513,7 +2528,7 @@ expr_normalize_or(struct expr *expr) if (sub->type == EXPR_T_AND) { ovs_list_remove(&sub->node); - struct expr *new = expr_normalize_and(sub); + struct expr *new = expr_normalize_and(sub, level); if (new->type == EXPR_T_BOOLEAN) { if (new->boolean) { expr_destroy(expr); @@ -2556,10 +2571,10 @@ expr_normalize(struct expr *expr) return expr; case EXPR_T_AND: - return expr_normalize_and(expr); + return expr_normalize_and(expr, 0); case EXPR_T_OR: - return expr_normalize_or(expr); + return expr_normalize_or(expr, 0); case EXPR_T_BOOLEAN: return expr; @@ -2695,9 +2710,31 @@ add_disjunction(const struct expr *or, ovs_assert(or->type == EXPR_T_OR); LIST_FOR_EACH (sub, node, &or->andor) { + bool match_correct = true; struct expr_match *match = expr_match_new(m, clause, n_clauses, conj_id); - if (constrain_match(sub, lookup_port, aux, &match->match)) { + if (sub->type == EXPR_T_CMP) { + if (!constrain_match(sub, lookup_port, aux, &match->match)) { + match_correct = false; + } + } else if (sub->type == EXPR_T_AND) { + struct expr *subsub; + + LIST_FOR_EACH (subsub, node, &sub->andor) { + if (subsub->type == EXPR_T_CMP) { + if (!constrain_match(subsub, lookup_port, aux, &match->match)) { + match_correct = false; + break; + } + } else { + OVS_NOT_REACHED(); + } + } + } else { + OVS_NOT_REACHED(); + } + + if (match_correct) { expr_match_add(matches, match); n++; } else {