[ovs-dev] [PATCH 3/3] Limit the number of generated conjunctions.
Dumitru Ceara
dceara at redhat.com
Mon Oct 28 11:46:06 UTC 2019
On Fri, Oct 25, 2019 at 11:07 PM Mark Michelson <mmichels at redhat.com> wrote:
>
> 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 <mmichels at redhat.com>
Hi Mark,
I've been testing the series on a setup with:
- 100 logical routers connected to a logical gateway router
- 100 logical switches (each connected to a logical router)
- 200 VIFs (2 per logical switch)
- 2 NAT rules on each router
I bound all VIFs to OVS internal interfaces on the machine when
ovn-northd is running.
If I start ovn-controller on the same node, without your series I see
ovn-controller taking more than 100s for a single flow computation
run.
If I apply your series, the maximum duration of a flow computation run
in the same scenario drops to ~4s.
This is really nice, however, I see some issues with flow removal (see below).
> ---
> 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;
> + }
> + }
I think this is quite expensive because we change single flow removal
complexity from amortized O(1) to O(n).
On the same setup as above if I continue testing and remove all
logical switches from the NB database it will trigger all flows to be
removed.
In this scenario, with your series I see that two flow computation
runs take up to 17s.
On the other hand, if I do the deletion test without applying your
third patch, flow computation runs never take longer than 5s.
I agree that it's good to limit the number of conjunctive flows but I
think we need to find a better way to track the max_conj_width/depth.
I guess we could track max flow conj_width/depth by storing ovn_flows
in a max-heap but that would change both flow add and remove
operations' complexities to O(log(n)).
Or do you think we can have a different heuristic for disabling
conjunctive flows?
Thanks,
Dumitru
> + }
> +}
> +
> /* 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. */
>
> --
> 2.14.5
>
> _______________________________________________
> dev mailing list
> dev at openvswitch.org
> https://mail.openvswitch.org/mailman/listinfo/ovs-dev
More information about the dev
mailing list