[ovs-dev] [PATCH ovn v2 2/2] ovn-controller: Cache logical flow expr tree for each lflow.
Han Zhou
hzhou at ovn.org
Tue Jan 21 20:04:09 UTC 2020
On Tue, Jan 21, 2020 at 6:41 AM <numans at ovn.org> wrote:
>
> From: Numan Siddique <numans at ovn.org>
>
> This patch caches the logical flow expr tree for each logical flow. This
> cache is stored as an hashmap in the output_flow engine data. When a
logical
> flow is deleted, the expr tree for that lflow is deleted in the
> flow_output_sb_logical_flow_handler().
>
> Below are the details of the OVN resource in my setup
>
> No of logical switches - 49
> No of logical ports - 1191
> No of logical routers - 7
> No of logical ports - 51
> No of ACLs - 1221
> No of Logical flows - 664736
>
> On a chassis hosting 7 distributed router ports and around 1090
> port bindings, the no of OVS rules was 921162.
>
> Without this patch, the function add_logical_flows() took ~15 seconds.
> And with this patch it took ~10 seconds. There is a good 34% improvement
> in logical flow processing.
>
> Acked-by: Mark Michelson <mmichels at redhat.com>
> Signed-off-by: Numan Siddique <numans at ovn.org>
> ---
> controller/lflow.c | 192 ++++++++++++++++++++++++++----------
> controller/lflow.h | 9 +-
> controller/ovn-controller.c | 16 ++-
> 3 files changed, 160 insertions(+), 57 deletions(-)
>
> diff --git a/controller/lflow.c b/controller/lflow.c
> index 93ec53a1c..997c59662 100644
> --- a/controller/lflow.c
> +++ b/controller/lflow.c
> @@ -75,11 +75,13 @@ static bool consider_logical_flow(
> const struct shash *port_groups,
> const struct sset *active_tunnels,
> const struct sset *local_lport_ids,
> + bool delete_expr_from_cache,
> struct ovn_desired_flow_table *,
> struct ovn_extend_table *group_table,
> struct ovn_extend_table *meter_table,
> struct lflow_resource_ref *lfrr,
> - uint32_t *conj_id_ofs);
> + uint32_t *conj_id_ofs,
> + struct hmap *lflow_expr_cache);
>
> static bool
> lookup_port_cb(const void *aux_, const char *port_name, unsigned int
*portp)
> @@ -255,6 +257,66 @@ lflow_resource_destroy_lflow(struct
lflow_resource_ref *lfrr,
> free(lfrn);
> }
>
> +/* Represents expr tree for the lflow. We don't store the
> + * match in this structure because -
> + * - Whenever a flow match or action needs to be modified,
> + * ovn-northd deletes the existing flow in the logical_flow
> + * table and adds a new one.
> + * We may want to revisit this and store match incase the behavior
> + * of ovn-northd changes.
> + */
> +struct lflow_expr {
> + struct hmap_node node;
> + struct uuid lflow_uuid; /* key */
> + struct expr *expr;
> +};
> +
> +static void
> +lflow_expr_add(struct hmap *lflow_expr_cache,
> + const struct sbrec_logical_flow *lflow,
> + struct expr *lflow_expr)
> +{
> + struct lflow_expr *le = xmalloc(sizeof *le);
> + le->lflow_uuid = lflow->header_.uuid;
> + le->expr = lflow_expr;
> + hmap_insert(lflow_expr_cache, &le->node, uuid_hash(&le->lflow_uuid));
> +}
> +
> +static struct lflow_expr *
> +lflow_expr_get(struct hmap *lflow_expr_cache,
> + const struct sbrec_logical_flow *lflow)
> +{
> + struct lflow_expr *le;
> + size_t hash = uuid_hash(&lflow->header_.uuid);
> + HMAP_FOR_EACH_WITH_HASH (le, node, hash, lflow_expr_cache) {
> + if (uuid_equals(&le->lflow_uuid, &lflow->header_.uuid)) {
> + return le;
> + }
> + }
> +
> + return NULL;
> +}
> +
> +static void
> +lflow_expr_delete(struct hmap *lflow_expr_cache, struct lflow_expr *le)
> +{
> + hmap_remove(lflow_expr_cache, &le->node);
> + expr_destroy(le->expr);
> + free(le);
> +}
> +
> +void
> +lflow_expr_destroy(struct hmap *lflow_expr_cache)
> +{
> + struct lflow_expr *le;
> + HMAP_FOR_EACH_POP (le, node, lflow_expr_cache) {
> + expr_destroy(le->expr);
> + free(le);
> + }
> +
> + hmap_destroy(lflow_expr_cache);
> +}
> +
> /* Adds the logical flows from the Logical_Flow table to flow tables. */
> static void
> add_logical_flows(
> @@ -273,7 +335,8 @@ add_logical_flows(
> struct ovn_extend_table *group_table,
> struct ovn_extend_table *meter_table,
> struct lflow_resource_ref *lfrr,
> - uint32_t *conj_id_ofs)
> + uint32_t *conj_id_ofs,
> + struct hmap *lflow_expr_cache)
> {
> const struct sbrec_logical_flow *lflow;
>
> @@ -306,9 +369,9 @@ add_logical_flows(
> chassis, &dhcp_opts, &dhcpv6_opts,
> &nd_ra_opts, &controller_event_opts,
> addr_sets, port_groups,
> - active_tunnels, local_lport_ids,
> + active_tunnels, local_lport_ids,
false,
> flow_table, group_table, meter_table,
> - lfrr, conj_id_ofs)) {
> + lfrr, conj_id_ofs, lflow_expr_cache))
{
> static struct vlog_rate_limit rl = VLOG_RATE_LIMIT_INIT(5,
5);
> VLOG_ERR_RL(&rl, "Conjunction id overflow when processing
lflow "
> UUID_FMT, UUID_ARGS(&lflow->header_.uuid));
> @@ -338,7 +401,8 @@ lflow_handle_changed_flows(
> struct ovn_extend_table *group_table,
> struct ovn_extend_table *meter_table,
> struct lflow_resource_ref *lfrr,
> - uint32_t *conj_id_ofs)
> + uint32_t *conj_id_ofs,
> + struct hmap *lflow_expr_cache)
> {
> bool ret = true;
> const struct sbrec_logical_flow *lflow;
> @@ -373,6 +437,12 @@ lflow_handle_changed_flows(
> ofctrl_remove_flows(flow_table, &lflow->header_.uuid);
> /* Delete entries from lflow resource reference. */
> lflow_resource_destroy_lflow(lfrr, &lflow->header_.uuid);
> +
> + /* Delete the expr cache for this lflow. */
> + struct lflow_expr *le = lflow_expr_get(lflow_expr_cache,
lflow);
> + if (le) {
> + lflow_expr_delete(lflow_expr_cache, le);
> + }
> }
> }
>
> @@ -399,9 +469,9 @@ lflow_handle_changed_flows(
> chassis, &dhcp_opts, &dhcpv6_opts,
> &nd_ra_opts,
&controller_event_opts,
> addr_sets, port_groups,
> - active_tunnels, local_lport_ids,
> + active_tunnels, local_lport_ids,
true,
> flow_table, group_table,
meter_table,
> - lfrr, conj_id_ofs)) {
> + lfrr, conj_id_ofs,
lflow_expr_cache)) {
> ret = false;
> break;
> }
> @@ -434,6 +504,7 @@ lflow_handle_changed_ref(
> struct ovn_extend_table *meter_table,
> struct lflow_resource_ref *lfrr,
> uint32_t *conj_id_ofs,
> + struct hmap *lflow_expr_cache,
> bool *changed)
> {
> struct ref_lflow_node *rlfn =
ref_lflow_lookup(&lfrr->ref_lflow_table,
> @@ -503,9 +574,9 @@ lflow_handle_changed_ref(
> chassis, &dhcp_opts, &dhcpv6_opts,
> &nd_ra_opts, &controller_event_opts,
> addr_sets, port_groups,
> - active_tunnels, local_lport_ids,
> + active_tunnels, local_lport_ids, true,
> flow_table, group_table, meter_table,
> - lfrr, conj_id_ofs)) {
> + lfrr, conj_id_ofs, lflow_expr_cache))
{
> ret = false;
> break;
> }
> @@ -551,11 +622,13 @@ consider_logical_flow(
> const struct shash *port_groups,
> const struct sset *active_tunnels,
> const struct sset *local_lport_ids,
> + bool delete_expr_from_cache,
> struct ovn_desired_flow_table *flow_table,
> struct ovn_extend_table *group_table,
> struct ovn_extend_table *meter_table,
> struct lflow_resource_ref *lfrr,
> - uint32_t *conj_id_ofs)
> + uint32_t *conj_id_ofs,
> + struct hmap *lflow_expr_cache)
> {
> /* Determine translation of logical table IDs to physical table IDs.
*/
> bool ingress = !strcmp(lflow->pipeline, "ingress");
> @@ -613,59 +686,77 @@ consider_logical_flow(
>
> /* Translate OVN match into table of OpenFlow matches. */
> struct hmap matches;
> - struct expr *expr;
> + struct expr *expr = NULL;
>
> struct sset addr_sets_ref = SSET_INITIALIZER(&addr_sets_ref);
> struct sset port_groups_ref = SSET_INITIALIZER(&port_groups_ref);
> - expr = expr_parse_string(lflow->match, &symtab, addr_sets,
port_groups,
> - &addr_sets_ref, &port_groups_ref, &error);
> - const char *addr_set_name;
> - SSET_FOR_EACH (addr_set_name, &addr_sets_ref) {
> - lflow_resource_add(lfrr, REF_TYPE_ADDRSET, addr_set_name,
> - &lflow->header_.uuid);
> - }
> - const char *port_group_name;
> - SSET_FOR_EACH (port_group_name, &port_groups_ref) {
> - lflow_resource_add(lfrr, REF_TYPE_PORTGROUP, port_group_name,
> - &lflow->header_.uuid);
> - }
> - sset_destroy(&addr_sets_ref);
> - sset_destroy(&port_groups_ref);
> -
> - if (!error) {
> - if (prereqs) {
> - expr = expr_combine(EXPR_T_AND, expr, prereqs);
> - prereqs = NULL;
> + struct lflow_expr *le = lflow_expr_get(lflow_expr_cache, lflow);
> + if (le) {
> + if (delete_expr_from_cache) {
> + lflow_expr_delete(lflow_expr_cache, le);
> + } else {
> + expr = le->expr;
> }
> - expr = expr_annotate(expr, &symtab, &error);
> }
> - if (error) {
> - static struct vlog_rate_limit rl = VLOG_RATE_LIMIT_INIT(1, 1);
> - VLOG_WARN_RL(&rl, "error parsing match \"%s\": %s",
> - lflow->match, error);
> - expr_destroy(prereqs);
> - free(error);
> - ovnacts_free(ovnacts.data, ovnacts.size);
> - ofpbuf_uninit(&ovnacts);
> - return true;
> +
> + if (!expr) {
> + expr = expr_parse_string(lflow->match, &symtab, addr_sets,
port_groups,
> + &addr_sets_ref, &port_groups_ref,
&error);
> + const char *addr_set_name;
> + SSET_FOR_EACH (addr_set_name, &addr_sets_ref) {
> + lflow_resource_add(lfrr, REF_TYPE_ADDRSET, addr_set_name,
> + &lflow->header_.uuid);
> + }
> + const char *port_group_name;
> + SSET_FOR_EACH (port_group_name, &port_groups_ref) {
> + lflow_resource_add(lfrr, REF_TYPE_PORTGROUP, port_group_name,
> + &lflow->header_.uuid);
> + }
> + sset_destroy(&addr_sets_ref);
> + sset_destroy(&port_groups_ref);
> +
> + if (!error) {
> + if (prereqs) {
> + expr = expr_combine(EXPR_T_AND, expr, prereqs);
> + prereqs = NULL;
> + }
> + expr = expr_annotate(expr, &symtab, &error);
> + }
> + if (error) {
> + static struct vlog_rate_limit rl = VLOG_RATE_LIMIT_INIT(1,
1);
> + VLOG_WARN_RL(&rl, "error parsing match \"%s\": %s",
> + lflow->match, error);
> + expr_destroy(prereqs);
> + free(error);
> + ovnacts_free(ovnacts.data, ovnacts.size);
> + ofpbuf_uninit(&ovnacts);
> + return true;
> + }
> +
> + expr = expr_simplify(expr);
> + expr = expr_normalize(expr);
> +
> + lflow_expr_add(lflow_expr_cache, lflow, expr);
> }
>
> - struct lookup_port_aux aux = {
> - .sbrec_multicast_group_by_name_datapath
> - = sbrec_multicast_group_by_name_datapath,
> - .sbrec_port_binding_by_name = sbrec_port_binding_by_name,
> - .dp = lflow->logical_datapath
> - };
> struct condition_aux cond_aux = {
> .sbrec_port_binding_by_name = sbrec_port_binding_by_name,
> .chassis = chassis,
> .active_tunnels = active_tunnels,
> };
> - expr = expr_simplify(expr);
> - expr = expr_normalize(expr);
> +
> + expr = expr_clone(expr);
> expr = expr_evaluate_condition(expr, is_chassis_resident_cb,
&cond_aux);
> +
> + struct lookup_port_aux aux = {
> + .sbrec_multicast_group_by_name_datapath
> + = sbrec_multicast_group_by_name_datapath,
> + .sbrec_port_binding_by_name = sbrec_port_binding_by_name,
> + .dp = lflow->logical_datapath
> + };
> uint32_t n_conjs = expr_to_matches(expr, lookup_port_cb, &aux,
> &matches);
> +
> expr_destroy(expr);
>
> if (hmap_is_empty(&matches)) {
> @@ -907,7 +998,8 @@ lflow_run(struct ovsdb_idl_index
*sbrec_multicast_group_by_name_datapath,
> struct ovn_extend_table *group_table,
> struct ovn_extend_table *meter_table,
> struct lflow_resource_ref *lfrr,
> - uint32_t *conj_id_ofs)
> + uint32_t *conj_id_ofs,
> + struct hmap *lflow_expr_cache)
> {
> COVERAGE_INC(lflow_run);
>
> @@ -916,7 +1008,7 @@ lflow_run(struct ovsdb_idl_index
*sbrec_multicast_group_by_name_datapath,
> dhcpv6_options_table, logical_flow_table,
> local_datapaths, chassis, addr_sets, port_groups,
> active_tunnels, local_lport_ids, flow_table,
group_table,
> - meter_table, lfrr, conj_id_ofs);
> + meter_table, lfrr, conj_id_ofs, lflow_expr_cache);
> add_neighbor_flows(sbrec_port_binding_by_name, mac_binding_table,
> flow_table);
> }
> diff --git a/controller/lflow.h b/controller/lflow.h
> index abdc55e96..a2fa087f8 100644
> --- a/controller/lflow.h
> +++ b/controller/lflow.h
> @@ -132,7 +132,8 @@ void lflow_run(struct ovsdb_idl_index
*sbrec_multicast_group_by_name_datapath,
> struct ovn_extend_table *group_table,
> struct ovn_extend_table *meter_table,
> struct lflow_resource_ref *,
> - uint32_t *conj_id_ofs);
> + uint32_t *conj_id_ofs,
> + struct hmap *lflow_expr_cache);
>
> bool lflow_handle_changed_flows(
> struct ovsdb_idl_index *sbrec_multicast_group_by_name_datapath,
> @@ -150,7 +151,8 @@ bool lflow_handle_changed_flows(
> struct ovn_extend_table *group_table,
> struct ovn_extend_table *meter_table,
> struct lflow_resource_ref *,
> - uint32_t *conj_id_ofs);
> + uint32_t *conj_id_ofs,
> + struct hmap *lflow_expr_cache);
>
> bool lflow_handle_changed_ref(
> enum ref_type,
> @@ -171,6 +173,7 @@ bool lflow_handle_changed_ref(
> struct ovn_extend_table *meter_table,
> struct lflow_resource_ref *,
> uint32_t *conj_id_ofs,
> + struct hmap *lflow_expr_cache,
> bool *changed);
>
> void lflow_handle_changed_neighbors(
> @@ -180,4 +183,6 @@ void lflow_handle_changed_neighbors(
>
> void lflow_destroy(void);
>
> +void lflow_expr_destroy(struct hmap *lflow_expr_cache);
> +
> #endif /* controller/lflow.h */
> diff --git a/controller/ovn-controller.c b/controller/ovn-controller.c
> index 17744d416..31ce1107c 100644
> --- a/controller/ovn-controller.c
> +++ b/controller/ovn-controller.c
> @@ -1211,6 +1211,9 @@ struct ed_type_flow_output {
> uint32_t conj_id_ofs;
> /* lflow resource cross reference */
> struct lflow_resource_ref lflow_resource_ref;
> +
> + /* Cache of lflow expr tree. */
> + struct hmap lflow_expr_cache;
> };
>
> static void *
> @@ -1224,6 +1227,7 @@ en_flow_output_init(struct engine_node *node
OVS_UNUSED,
> ovn_extend_table_init(&data->meter_table);
> data->conj_id_ofs = 1;
> lflow_resource_init(&data->lflow_resource_ref);
> + hmap_init(&data->lflow_expr_cache);
> return data;
> }
>
> @@ -1235,6 +1239,7 @@ en_flow_output_cleanup(void *data)
> ovn_extend_table_destroy(&flow_output_data->group_table);
> ovn_extend_table_destroy(&flow_output_data->meter_table);
> lflow_resource_destroy(&flow_output_data->lflow_resource_ref);
> + lflow_expr_destroy(&flow_output_data->lflow_expr_cache);
> }
>
> static void
> @@ -1335,7 +1340,8 @@ en_flow_output_run(struct engine_node *node, void
*data)
> chassis, local_datapaths, addr_sets,
> port_groups, active_tunnels, local_lport_ids,
> flow_table, group_table, meter_table, lfrr,
> - conj_id_ofs);
> + conj_id_ofs,
> + &fo->lflow_expr_cache);
>
> struct sbrec_multicast_group_table *multicast_group_table =
> (struct sbrec_multicast_group_table *)EN_OVSDB_GET(
> @@ -1436,7 +1442,7 @@ flow_output_sb_logical_flow_handler(struct
engine_node *node, void *data)
> local_datapaths, chassis, addr_sets,
> port_groups, active_tunnels, local_lport_ids,
> flow_table, group_table, meter_table, lfrr,
> - conj_id_ofs);
> + conj_id_ofs, &fo->lflow_expr_cache);
>
> engine_set_node_state(node, EN_UPDATED);
> return handled;
> @@ -1721,7 +1727,7 @@ _flow_output_resource_ref_handler(struct
engine_node *node, void *data,
> local_datapaths, chassis, addr_sets,
> port_groups, active_tunnels, local_lport_ids,
> flow_table, group_table, meter_table, lfrr,
> - conj_id_ofs, &changed)) {
> + conj_id_ofs, &fo->lflow_expr_cache, &changed)) {
> return false;
> }
> if (changed) {
> @@ -1736,7 +1742,7 @@ _flow_output_resource_ref_handler(struct
engine_node *node, void *data,
> local_datapaths, chassis, addr_sets,
> port_groups, active_tunnels, local_lport_ids,
> flow_table, group_table, meter_table, lfrr,
> - conj_id_ofs, &changed)) {
> + conj_id_ofs, &fo->lflow_expr_cache, &changed)) {
> return false;
> }
> if (changed) {
> @@ -1751,7 +1757,7 @@ _flow_output_resource_ref_handler(struct
engine_node *node, void *data,
> local_datapaths, chassis, addr_sets,
> port_groups, active_tunnels, local_lport_ids,
> flow_table, group_table, meter_table, lfrr,
> - conj_id_ofs, &changed)) {
> + conj_id_ofs, &fo->lflow_expr_cache, &changed)) {
> return false;
> }
> if (changed) {
> --
> 2.24.1
>
> _______________________________________________
> dev mailing list
> dev at openvswitch.org
> https://mail.openvswitch.org/mailman/listinfo/ovs-dev
Acked-by: Han Zhou <hzhou at ovn.org>
More information about the dev
mailing list