[ovs-dev,ovn,v2,2/2] ovn-controller: Cache logical flow expr tree for each lflow.

From: Numan Siddique <numans@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@redhat.com>
Signed-off-by: Numan Siddique <numans@ovn.org>
---
 controller/lflow.c          | 192 ++++++++++++++++++++++++++----------
 controller/lflow.h          |   9 +-
 controller/ovn-controller.c |  16 ++-
 3 files changed, 160 insertions(+), 57 deletions(-)

On Tue, Jan 21, 2020 at 6:41 AM <numans@ovn.org> wrote:
>
> From: Numan Siddique <numans@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@redhat.com>
> Signed-off-by: Numan Siddique <numans@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@openvswitch.org
> https://mail.openvswitch.org/mailman/listinfo/ovs-dev

Acked-by: Han Zhou <hzhou@ovn.org>