From patchwork Fri Oct 25 21:06:31 2019 Content-Type: text/plain; charset="utf-8" MIME-Version: 1.0 Content-Transfer-Encoding: 7bit X-Patchwork-Submitter: Mark Michelson X-Patchwork-Id: 1184456 Return-Path: X-Original-To: incoming@patchwork.ozlabs.org Delivered-To: patchwork-incoming@bilbo.ozlabs.org Authentication-Results: ozlabs.org; spf=pass (sender SPF authorized) smtp.mailfrom=openvswitch.org (client-ip=140.211.169.12; helo=mail.linuxfoundation.org; envelope-from=ovs-dev-bounces@openvswitch.org; receiver=) Authentication-Results: ozlabs.org; dmarc=fail (p=none dis=none) header.from=redhat.com Authentication-Results: ozlabs.org; dkim=fail reason="signature verification failed" (1024-bit key; unprotected) header.d=redhat.com header.i=@redhat.com header.b="G4RNHAdE"; dkim-atps=neutral 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 470GrN6fPDz9sPV for ; Sat, 26 Oct 2019 08:06:44 +1100 (AEDT) Received: from mail.linux-foundation.org (localhost [127.0.0.1]) by mail.linuxfoundation.org (Postfix) with ESMTP id D6B9DD94; Fri, 25 Oct 2019 21:06:41 +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 CE5AED56 for ; Fri, 25 Oct 2019 21:06:40 +0000 (UTC) X-Greylist: domain auto-whitelisted by SQLgrey-1.7.6 Received: from us-smtp-delivery-1.mimecast.com (us-smtp-delivery-1.mimecast.com [205.139.110.120]) by smtp1.linuxfoundation.org (Postfix) with ESMTP id 1E2D089A for ; Fri, 25 Oct 2019 21:06:39 +0000 (UTC) DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=redhat.com; s=mimecast20190719; t=1572037598; h=from:from:reply-to:subject:subject:date:date:message-id:message-id: to:to:cc:content-type:content-type: content-transfer-encoding:content-transfer-encoding: in-reply-to:in-reply-to:references:references; bh=avz+XJu+E3tSypvWpVGET48LxL5Ce7uEVeFbyXfG7yM=; b=G4RNHAdE7UthlhzHPFA/BWZZ3CPAjmbgOA8BLu6kPLe/U4N09x5vGx1FqGG/fmc6+YK5Rp uqT5NRbyR0F3pvrn5Lj1SXjT3kDz7IY9eke1I89U/w90zdidZp6Gkh7MWCnY5dFLW4Nw5T r1H0Z7CSNps0ypY4ERZXNtKeU4YwKUQ= Received: from mimecast-mx01.redhat.com (mimecast-mx01.redhat.com [209.132.183.4]) (Using TLS) by relay.mimecast.com with ESMTP id us-mta-36-H8EQp5ltM7uKaaPXENKXsw-1; Fri, 25 Oct 2019 17:06:36 -0400 Received: from smtp.corp.redhat.com (int-mx06.intmail.prod.int.phx2.redhat.com [10.5.11.16]) (using TLSv1.2 with cipher AECDH-AES256-SHA (256/256 bits)) (No client certificate requested) by mimecast-mx01.redhat.com (Postfix) with ESMTPS id 0BB871800E01 for ; Fri, 25 Oct 2019 21:06:36 +0000 (UTC) Received: from monae.redhat.com (ovpn-122-41.rdu2.redhat.com [10.10.122.41]) by smtp.corp.redhat.com (Postfix) with ESMTP id 452BB5C1D4 for ; Fri, 25 Oct 2019 21:06:35 +0000 (UTC) From: Mark Michelson To: dev@openvswitch.org Date: Fri, 25 Oct 2019 17:06:31 -0400 Message-Id: <20191025210631.7230-4-mmichels@redhat.com> In-Reply-To: <20191025210631.7230-1-mmichels@redhat.com> References: <20191025210631.7230-1-mmichels@redhat.com> X-Scanned-By: MIMEDefang 2.79 on 10.5.11.16 X-MC-Unique: H8EQp5ltM7uKaaPXENKXsw-1 X-Mimecast-Spam-Score: 0 X-Spam-Status: No, score=-4.3 required=5.0 tests=BAYES_00,DKIM_SIGNED, DKIM_VALID, DKIM_VALID_AU, RCVD_IN_DNSWL_MED autolearn=ham version=3.3.1 X-Spam-Checker-Version: SpamAssassin 3.3.1 (2010-03-16) on smtp1.linux-foundation.org Subject: [ovs-dev] [PATCH 3/3] Limit the number of generated conjunctions. 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: , MIME-Version: 1.0 Sender: ovs-dev-bounces@openvswitch.org Errors-To: ovs-dev-bounces@openvswitch.org There is a maximum number of resubmits that can occur during packet processing. Deliberately creating a flow table that might cross this threshold is irresponsible. This commit causes the ofctrl code to track the maximum width and depth of conjunctions in the desired flow table. By multiplying them, we have a possible worst case for number of resubmits required. If this number exceeds a quarter of the maximum resubmits allowed, then we fall back to forcing crossproducts. The resulting flow table can end up being a mixture of conjunction and non-conjunction flows if the limit is exceeded. Signed-off-by: Mark Michelson --- controller/lflow.c | 11 +++++++++ controller/ofctrl.c | 69 +++++++++++++++++++++++++++++++++++++++++++++++++++++ controller/ofctrl.h | 6 +++++ include/ovn/expr.h | 2 ++ lib/expr.c | 6 +++++ 5 files changed, 94 insertions(+) diff --git a/controller/lflow.c b/controller/lflow.c index 34b7c36a6..318066465 100644 --- a/controller/lflow.c +++ b/controller/lflow.c @@ -37,6 +37,13 @@ VLOG_DEFINE_THIS_MODULE(lflow); COVERAGE_DEFINE(lflow_run); + +/* Limit maximum conjunctions to a quarter of the max + * resubmits. Unfortunatley, max resubmits is not publicly + * defined in a header file, so if max resubmits is changed + * from 4096, we have to make sure to update this as well + */ +#define MAX_CONJUNCTIONS (4096 / 4) /* Symbol table. */ @@ -602,6 +609,10 @@ consider_logical_flow( struct expr *prereqs; char *error; + uint32_t conj_worst_case; + conj_worst_case = flow_table->max_conj_width * flow_table->max_conj_depth; + expr_set_force_crossproduct(conj_worst_case >= MAX_CONJUNCTIONS); + error = ovnacts_parse_string(lflow->actions, &pp, &ovnacts, &prereqs); if (error) { static struct vlog_rate_limit rl = VLOG_RATE_LIMIT_INIT(1, 1); diff --git a/controller/ofctrl.c b/controller/ofctrl.c index afb0036f1..2b2fde3c9 100644 --- a/controller/ofctrl.c +++ b/controller/ofctrl.c @@ -686,6 +686,64 @@ ofctrl_check_and_add_flow(struct ovn_desired_flow_table *flow_table, f->uuid_hindex_node.hash); } +static void +get_conjunction_dimensions(const struct ovn_flow *f, uint32_t *conj_width_p, + uint32_t *conj_depth_p) +{ + struct ofpact *ofpact; + uint32_t conj_width = 0; + uint32_t conj_depth = 0; + OFPACT_FOR_EACH (ofpact, f->ofpacts, f->ofpacts_len) { + if (ofpact->type == OFPACT_CONJUNCTION) { + struct ofpact_conjunction *conj = ofpact_get_CONJUNCTION(ofpact); + if (conj->n_clauses > conj_depth) { + conj_depth = conj->n_clauses; + } + conj_width++; + } + } + + *conj_width_p = conj_width; + *conj_depth_p = conj_depth; +} + +static void +adjust_conjunction_count(struct ovn_desired_flow_table *desired_flows, + const struct ovn_flow *f, bool add) +{ + uint32_t conj_width; + uint32_t conj_depth; + + get_conjunction_dimensions(f, &conj_width, &conj_depth); + + if (add) { + if (conj_width > desired_flows->max_conj_width) { + desired_flows->max_conj_width = conj_width; + } + if (conj_depth > desired_flows->max_conj_depth) { + desired_flows->max_conj_depth = conj_depth; + } + } else if (desired_flows->max_conj_width <= conj_width || + desired_flows->max_conj_depth <= conj_depth) { + /* Removing either the widest or deepest conjunction. + * Walk the table and recalculate maximums + */ + struct ovn_flow *iter; + desired_flows->max_conj_width = 0; + desired_flows->max_conj_depth = 0; + HMAP_FOR_EACH (iter, match_hmap_node, + &desired_flows->match_flow_table) { + get_conjunction_dimensions(iter, &conj_width, &conj_depth); + if (conj_width > desired_flows->max_conj_width) { + desired_flows->max_conj_width = conj_width; + } + if (conj_depth > desired_flows->max_conj_depth) { + desired_flows->max_conj_depth = conj_depth; + } + } + } +} + /* Removes a bundles of flows from the flow table. */ void ofctrl_remove_flows(struct ovn_desired_flow_table *flow_table, @@ -697,6 +755,7 @@ ofctrl_remove_flows(struct ovn_desired_flow_table *flow_table, &flow_table->uuid_flow_table) { if (uuid_equals(&f->sb_uuid, sb_uuid)) { ovn_flow_log(f, "ofctrl_remove_flow"); + adjust_conjunction_count(flow_table, f, false); hmap_remove(&flow_table->match_flow_table, &f->match_hmap_node); hindex_remove(&flow_table->uuid_flow_table, &f->uuid_hindex_node); @@ -747,6 +806,12 @@ ofctrl_add_or_append_flow(struct ovn_desired_flow_table *desired_flows, existing->ofpacts = xmemdup(compound.data, compound.size); existing->ofpacts_len = compound.size; + /* It's a bit of a cheat that we only call adjust_conjunction_count in + * this function and not in ofctrl_add(). However, we know that + * conjunctions are only ever added with this function + */ + adjust_conjunction_count(desired_flows, existing, true); + ovn_flow_destroy(f); } else { hmap_insert(&desired_flows->match_flow_table, &f->match_hmap_node, @@ -862,6 +927,8 @@ ovn_desired_flow_table_init(struct ovn_desired_flow_table *flow_table) { hmap_init(&flow_table->match_flow_table); hindex_init(&flow_table->uuid_flow_table); + flow_table->max_conj_width = 0; + flow_table->max_conj_depth = 0; } void @@ -874,6 +941,8 @@ ovn_desired_flow_table_clear(struct ovn_desired_flow_table *flow_table) hindex_remove(&flow_table->uuid_flow_table, &f->uuid_hindex_node); ovn_flow_destroy(f); } + flow_table->max_conj_width = 0; + flow_table->max_conj_depth = 0; } void diff --git a/controller/ofctrl.h b/controller/ofctrl.h index 21d2ce648..c295c04ed 100644 --- a/controller/ofctrl.h +++ b/controller/ofctrl.h @@ -37,6 +37,12 @@ struct ovn_desired_flow_table { /* SB uuid index for the nodes in match_flow_table.*/ struct hindex uuid_flow_table; + + /* Highest known number of conjunction() actions in a single flow */ + uint32_t max_conj_width; + + /* Largest number of clauses for a conjunction in the table */ + uint32_t max_conj_depth; }; /* Interface for OVN main loop. */ diff --git a/include/ovn/expr.h b/include/ovn/expr.h index 22f633e57..714e21add 100644 --- a/include/ovn/expr.h +++ b/include/ovn/expr.h @@ -425,6 +425,8 @@ bool expr_evaluate(const struct expr *, const struct flow *uflow, bool (*lookup_port)(const void *aux, const char *port_name, unsigned int *portp), const void *aux); + +void expr_set_force_crossproduct(bool should_force); /* Converting expressions to OpenFlow flows. */ diff --git a/lib/expr.c b/lib/expr.c index 71de61543..4c164caed 100644 --- a/lib/expr.c +++ b/lib/expr.c @@ -3278,6 +3278,12 @@ expr_evaluate(const struct expr *e, const struct flow *uflow, OVS_NOT_REACHED(); } } + +void +expr_set_force_crossproduct(bool should_force) +{ + force_crossproduct = should_force; +} /* Action parsing helper. */