Re: [ovs-dev] [PATCH 3/3] Limit the number of generated conjunctions.
On Mon, Oct 28, 2019 at 5:29 PM Dumitru Ceara wrote:
>
> On Mon, Oct 28, 2019 at 5:07 PM Mark Michelson wrote:
> >
> > On 10/28/19 10:37 AM, Dumitru Ceara wrote:
> > > On Mon, Oct 28, 2019 at 1:46 PM Mark Michelson
> > > wrote:
> > >>
> > >> On 10/28/19 7:46 AM, Dumitru Ceara wrote:
> > >>> On Fri, Oct 25, 2019 at 11:07 PM Mark Michelson
> > >>> 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
> > >>>
> > >>> 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).
> > >>
> > >> Thanks for the test, Dumitru.
> > >>
> > >>>
> > ---
> > 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, , ,
> > );
> > 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)
> >
Re: [ovs-dev] [PATCH 3/3] Limit the number of generated conjunctions.
On Mon, Oct 28, 2019 at 5:07 PM Mark Michelson wrote:
>
> On 10/28/19 10:37 AM, Dumitru Ceara wrote:
> > On Mon, Oct 28, 2019 at 1:46 PM Mark Michelson wrote:
> >>
> >> On 10/28/19 7:46 AM, Dumitru Ceara wrote:
> >>> On Fri, Oct 25, 2019 at 11:07 PM Mark Michelson
> >>> 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
> >>>
> >>> 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).
> >>
> >> Thanks for the test, Dumitru.
> >>
> >>>
> ---
> 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, , ,
> );
> 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, _width, _depth);
> +
> +if (add) {
> +if (conj_width > desired_flows->max_conj_width) {
> +desired_flows->max_conj_width = conj_width;
> +}
> +
Re: [ovs-dev] [PATCH 3/3] Limit the number of generated conjunctions.
On 10/28/19 10:37 AM, Dumitru Ceara wrote:
On Mon, Oct 28, 2019 at 1:46 PM Mark Michelson wrote:
On 10/28/19 7:46 AM, Dumitru Ceara wrote:
On Fri, Oct 25, 2019 at 11:07 PM Mark Michelson 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
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).
Thanks for the test, Dumitru.
---
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, , , );
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, _width, _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,
+ _flows->match_flow_table) {
+get_conjunction_dimensions(iter, _width, _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 =
Re: [ovs-dev] [PATCH 3/3] Limit the number of generated conjunctions.
On Mon, Oct 28, 2019 at 1:46 PM Mark Michelson wrote:
>
> On 10/28/19 7:46 AM, Dumitru Ceara wrote:
> > On Fri, Oct 25, 2019 at 11:07 PM Mark Michelson 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
> >
> > 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).
>
> Thanks for the test, Dumitru.
>
> >
> >> ---
> >> 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, , ,
> >> );
> >> 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, _width, _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
Re: [ovs-dev] [PATCH 3/3] Limit the number of generated conjunctions.
On 10/28/19 7:46 AM, Dumitru Ceara wrote:
On Fri, Oct 25, 2019 at 11:07 PM Mark Michelson 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
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).
Thanks for the test, Dumitru.
---
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, , , );
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, _width, _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,
+ _flows->match_flow_table) {
+get_conjunction_dimensions(iter, _width, _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
Re: [ovs-dev] [PATCH 3/3] Limit the number of generated conjunctions.
On Fri, Oct 25, 2019 at 11:07 PM Mark Michelson 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
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, , , );
> 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, _width, _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,
> + _flows->match_flow_table) {
> +get_conjunction_dimensions(iter, _width, _depth);
> +if (conj_width > desired_flows->max_conj_width) {
> +desired_flows->max_conj_width = conj_width;
> +}
> +if (conj_depth > desired_flows->max_conj_depth) {
> +
