From patchwork Mon Aug 17 22:49:18 2020 Content-Type: text/plain; charset="utf-8" MIME-Version: 1.0 Content-Transfer-Encoding: 8bit X-Patchwork-Submitter: Han Zhou X-Patchwork-Id: 1441559 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.166.137; helo=fraxinus.osuosl.org; envelope-from=ovs-dev-bounces@openvswitch.org; receiver=) Received: from fraxinus.osuosl.org (smtp4.osuosl.org [140.211.166.137]) (using TLSv1.2 with cipher ECDHE-RSA-AES256-GCM-SHA384 (256/256 bits)) (No client certificate requested) by ozlabs.org (Postfix) with ESMTPS id 4Dh7H60SWmz9sRf for ; Thu, 18 Feb 2021 19:32:02 +1100 (AEDT) Received: from localhost (localhost [127.0.0.1]) by fraxinus.osuosl.org (Postfix) with ESMTP id 82E448613E; Thu, 18 Feb 2021 08:32:00 +0000 (UTC) X-Virus-Scanned: amavisd-new at osuosl.org Received: from fraxinus.osuosl.org ([127.0.0.1]) by localhost (.osuosl.org [127.0.0.1]) (amavisd-new, port 10024) with ESMTP id uHeS1JPNYrQV; Thu, 18 Feb 2021 08:31:59 +0000 (UTC) Received: from lists.linuxfoundation.org (lf-lists.osuosl.org [140.211.9.56]) by fraxinus.osuosl.org (Postfix) with ESMTP id 0413185F90; Thu, 18 Feb 2021 08:31:59 +0000 (UTC) Received: from lf-lists.osuosl.org (localhost [127.0.0.1]) by lists.linuxfoundation.org (Postfix) with ESMTP id D9720C000E; Thu, 18 Feb 2021 08:31:58 +0000 (UTC) X-Original-To: dev@openvswitch.org Delivered-To: ovs-dev@lists.linuxfoundation.org Received: from whitealder.osuosl.org (smtp1.osuosl.org [140.211.166.138]) by lists.linuxfoundation.org (Postfix) with ESMTP id 6BB7EC000D for ; Thu, 18 Feb 2021 08:31:57 +0000 (UTC) Received: from localhost (localhost [127.0.0.1]) by whitealder.osuosl.org (Postfix) with ESMTP id 5A71C86974 for ; Thu, 18 Feb 2021 08:31:57 +0000 (UTC) X-Virus-Scanned: amavisd-new at osuosl.org Received: from whitealder.osuosl.org ([127.0.0.1]) by localhost (.osuosl.org [127.0.0.1]) (amavisd-new, port 10024) with ESMTP id aHZW-zWOb7xo for ; Thu, 18 Feb 2021 08:31:56 +0000 (UTC) X-Greylist: domain auto-whitelisted by SQLgrey-1.7.6 Received: from ti0189a330-0925.bb.online.no (ti0189a330-0925.bb.online.no [88.88.218.161]) by whitealder.osuosl.org (Postfix) with ESMTP id 8BC1E866CA for ; Thu, 18 Feb 2021 08:31:29 +0000 (UTC) X-Mailbox-Line: From 0ad2c2b617d791fa17f2188cfa74c372dd536db2 Mon Sep 17 00:00:00 2001 Message-Id: <0ad2c2b617d791fa17f2188cfa74c372dd536db2.1613635760.git.frode.nordahl@canonical.com> In-Reply-To: References: From: Han Zhou To: dev@openvswitch.org Date: Mon, 17 Aug 2020 15:49:18 -0700 MIME-Version: 1.0 Subject: [ovs-dev] [PATCH ovn branch-20.06 04/15] ofctrl: Incremental processing for flow installation by tracking. X-BeenThere: ovs-dev@openvswitch.org X-Mailman-Version: 2.1.15 Precedence: list List-Id: List-Unsubscribe: , List-Archive: List-Post: List-Help: List-Subscribe: , Errors-To: ovs-dev-bounces@openvswitch.org Sender: "dev" With incremental processing for flow computation, the bottle neck of ovn-controller in large scale environment is in the flow installation (ofctrl_put()), which does full comparison between the two big flow tables: the installed flows and desired flows. This patch implements tracking desired flow changes when flows are incrementally computed by I-P engine, and then incrementally processing the flow installation using the tracked information in ofctrl_put(). It falls back to the full comparison whenever tracking information is unavailable, e.g. when I-P engine triggers full recompute. In ovn-scale-test with 3000 HVs and 30k lports, the end-to-end latency between the moment a lflow is updated in SB DB and the moment when all the 3K HVs complete OVS flow updating has reduced around 60% (from 1s to 400ms). Below is the perf result for a ovn-controller processing a new port-binding: Beore: + 96.76% 0.00% ovn-controller [unknown] [k] 0xffffffffffffffff + 90.21% 0.00% ovn-controller ovn-controller [.] main + 39.93% 1.19% ovn-controller ovn-controller [.] ofctrl_put + 31.27% 12.47% ovn-controller ovn-controller [.] ovn_flow_lookup + 22.12% 3.12% ovn-controller ovn-controller [.] encaps_run + 18.69% 2.77% ovn-controller ovn-controller [.] minimatch_equal + 17.63% 4.11% ovn-controller ovn-controller [.] patch_run + 15.91% 0.00% ovn-controller ovn-controller [.] add_bridge_mappings (inlined) + 14.03% 12.08% ovn-controller ovn-controller [.] minimask_equal + 12.41% 0.00% ovn-controller ovn-controller [.] chassis_tunnel_add (inlined) + 11.40% 0.00% ovn-controller ovn-controller [.] tunnel_add (inlined) After: + 94.59% 0.00% ovn-controller [unknown] [k] 0xffffffffffffffff + 83.56% 0.09% ovn-controller ovn-controller [.] main + 35.37% 3.13% ovn-controller ovn-controller [.] encaps_run + 27.54% 7.53% ovn-controller ovn-controller [.] patch_run + 24.86% 0.00% ovn-controller ovn-controller [.] add_bridge_mappings (inlined) + 20.01% 0.00% ovn-controller ovn-controller [.] chassis_tunnel_add (inlined) + 18.51% 0.00% ovn-controller ovn-controller [.] tunnel_add (inlined) + 14.08% 0.17% ovn-controller ovn-controller [.] physical_run + 11.37% 11.28% ovn-controller ovn-controller [.] next_real_row + 10.50% 2.59% ovn-controller ovn-controller [.] consider_port_binding .. + 2.14% 0.32% ovn-controller ovn-controller [.] ofctrl_put ▒ Before the optimization, ofctrl_put took 40% of CPU, and now it disappears from the hot spots. Acked-by: Mark Michelson Signed-off-by: Han Zhou (cherry picked from commit 6f0b1e02d9ab3a94048c4818f2d382938cad4b71) Signed-off-by: Frode Nordahl --- controller/ofctrl.c | 289 +++++++++++++++++++++++++++++++++++--------- controller/ofctrl.h | 6 +- 2 files changed, 240 insertions(+), 55 deletions(-) diff --git a/controller/ofctrl.c b/controller/ofctrl.c index 98e291243..b0670bf44 100644 --- a/controller/ofctrl.c +++ b/controller/ofctrl.c @@ -101,6 +101,39 @@ struct ovn_flow { * * The links are updated whenever there is a change in desired flows, which is * usually triggered by a SB data change in I-P engine. + * + * ** Tracking ** + * + * A desired flow can be tracked - listed in ovn_desired_flow_table's + * tracked_flows. + * + * Tracked flows is initially empty, and stays empty after the first run of I-P + * engine when installed flows are initially populated. After that, flow + * changes are tracked when I-P engine incrementally computes flow changes. + * Tracked flows are then processed and removed completely in ofctrl_put. + * ("processed" means OpenFlow change messages are composed and sent/queued to + * OVS, which ensures flows in OVS is always in sync (eventually) with the + * installed flows table). + * + * In case of full recompute of I-P engine, tracked flows are not + * added/removed, and ofctrl_put will not rely on tracked flows. (It is I-P + * engine's responsibility to ensure the tracked flows are cleared before + * recompute). + * + * Tracked flows can be preserved across multiple I-P engine runs - if in some + * iterations ofctrl_put() is skipped. Tracked flows are cleared only when it + * is consumed or when flow recompute happens. + * + * The "change_tracked" member of desired flow table maintains the status of + * whether flow changes are tracked or not. It is always set to true when + * ofctrl_put is completed, and transition to false whenever + * ovn_desired_flow_table_clear is called. + * + * NOTE: A tracked flow is just a reference to a desired flow, instead of a new + * copy. When a desired flow is removed and tracked, it is removed from the + * match_flow_table and uuid_flow_table indexes, and added to the tracked_flows + * list, marking is_deleted = true, but not immediately destroyed. It is + * destroyed when the tracking is processed for installed flow updates. */ struct desired_flow { struct ovn_flow flow; @@ -117,6 +150,11 @@ struct desired_flow { /* Node in installed_flow.desired_refs list. */ struct ovs_list installed_ref_list_node; + + /* For tracking. */ + struct ovs_list track_list_node; /* node in ovn_desired_flow_table's + * tracked_flows list. */ + bool is_deleted; /* If the tracked flow is deleted. */ }; struct sb_to_flow { @@ -789,6 +827,62 @@ unlink_all_refs_for_installed_flow(struct installed_flow *i) } } +static void +track_flow_add_or_modify(struct ovn_desired_flow_table *flow_table, + struct desired_flow *f) +{ + if (!flow_table->change_tracked) { + return; + } + + /* If same node (flow adding/modifying) was tracked, remove it from + * tracking first. */ + if (!ovs_list_is_empty(&f->track_list_node)) { + ovs_list_remove(&f->track_list_node); + } + f->is_deleted = false; + ovs_list_push_back(&flow_table->tracked_flows, &f->track_list_node); + +} + +static void +track_flow_del(struct ovn_desired_flow_table *flow_table, + struct desired_flow *f) +{ + if (!flow_table->change_tracked) { + return; + } + /* If same node (flow adding/modifying) was tracked, remove it from + * tracking first. */ + if (!ovs_list_is_empty(&f->track_list_node)) { + ovs_list_remove(&f->track_list_node); + if (!f->installed_flow) { + /* If it is not installed yet, simply destroy it. */ + desired_flow_destroy(f); + return; + } + } + f->is_deleted = true; + ovs_list_push_back(&flow_table->tracked_flows, &f->track_list_node); +} + +/* When a desired flow is being removed, depending on "change_tracked", this + * function either unlinks a desired flow from installed flow and destroy it, + * or do nothing but track it. */ +static void +track_or_destroy_for_flow_del(struct ovn_desired_flow_table *flow_table, + struct desired_flow *f) +{ + if (flow_table->change_tracked) { + track_flow_del(flow_table, f); + } else { + if (f->installed_flow) { + unlink_installed_to_desired(f->installed_flow, f); + } + desired_flow_destroy(f); + } +} + static struct sb_to_flow * sb_to_flow_find(struct hmap *uuid_flow_table, const struct uuid *sb_uuid) { @@ -861,6 +955,7 @@ ofctrl_check_and_add_flow(struct ovn_desired_flow_table *flow_table, hmap_insert(&flow_table->match_flow_table, &f->match_hmap_node, f->flow.hash); link_flow_to_sb(flow_table, f, sb_uuid); + track_flow_add_or_modify(flow_table, f); ovn_flow_log(&f->flow, "ofctrl_add_flow"); } @@ -912,6 +1007,7 @@ ofctrl_add_or_append_flow(struct ovn_desired_flow_table *desired_flows, f->flow.hash); } link_flow_to_sb(desired_flows, f, sb_uuid); + track_flow_add_or_modify(desired_flows, f); if (existing) { ovn_flow_log(&f->flow, "ofctrl_add_or_append_flow (append)"); @@ -941,10 +1037,7 @@ remove_flows_from_sb_to_flow(struct ovn_desired_flow_table *flow_table, } hmap_remove(&flow_table->match_flow_table, &f->match_hmap_node); - if (f->installed_flow) { - unlink_installed_to_desired(f->installed_flow, f); - } - desired_flow_destroy(f); + track_or_destroy_for_flow_del(flow_table, f); } } hmap_remove(&flow_table->uuid_flow_table, &stf->hmap_node); @@ -1019,10 +1112,7 @@ flood_remove_flows_for_sb_uuid(struct ovn_desired_flow_table *flow_table, * be empty in most cases. */ hmap_remove(&flow_table->match_flow_table, &f->match_hmap_node); - if (f->installed_flow) { - unlink_installed_to_desired(f->installed_flow, f); - } - desired_flow_destroy(f); + track_or_destroy_for_flow_del(flow_table, f); } else { ovs_list_insert(&to_be_removed, &f->list_node); } @@ -1056,10 +1146,7 @@ flood_remove_flows_for_sb_uuid(struct ovn_desired_flow_table *flow_table, ovs_list_remove(&f->list_node); hmap_remove(&flow_table->match_flow_table, &f->match_hmap_node); - if (f->installed_flow) { - unlink_installed_to_desired(f->installed_flow, f); - } - desired_flow_destroy(f); + track_or_destroy_for_flow_del(flow_table, f); } } @@ -1105,7 +1192,9 @@ desired_flow_alloc(uint8_t table_id, uint16_t priority, uint64_t cookie, ovs_list_init(&f->references); ovs_list_init(&f->list_node); ovs_list_init(&f->installed_ref_list_node); + ovs_list_init(&f->track_list_node); f->installed_flow = NULL; + f->is_deleted = false; ovn_flow_init(&f->flow, table_id, priority, cookie, match, actions); return f; @@ -1245,11 +1334,27 @@ ovn_desired_flow_table_init(struct ovn_desired_flow_table *flow_table) { hmap_init(&flow_table->match_flow_table); hmap_init(&flow_table->uuid_flow_table); + ovs_list_init(&flow_table->tracked_flows); + flow_table->change_tracked = false; } void ovn_desired_flow_table_clear(struct ovn_desired_flow_table *flow_table) { + flow_table->change_tracked = false; + + struct desired_flow *f, *f_next; + LIST_FOR_EACH_SAFE (f, f_next, track_list_node, + &flow_table->tracked_flows) { + ovs_list_remove(&f->track_list_node); + if (f->is_deleted) { + if (f->installed_flow) { + unlink_installed_to_desired(f->installed_flow, f); + } + desired_flow_destroy(f); + } + } + struct sb_to_flow *stf, *next; HMAP_FOR_EACH_SAFE (stf, next, hmap_node, &flow_table->uuid_flow_table) { @@ -1538,6 +1643,117 @@ installed_flow_del(struct ovn_flow *i, struct ovs_list *msgs) add_flow_mod(&fm, msgs); } +static void +update_installed_flows_by_compare(struct ovn_desired_flow_table *flow_table, + struct ovs_list *msgs) +{ + ovs_assert(ovs_list_is_empty(&flow_table->tracked_flows)); + /* Iterate through all of the installed flows. If any of them are no + * longer desired, delete them; if any of them should have different + * actions, update them. */ + struct installed_flow *i, *next; + HMAP_FOR_EACH_SAFE (i, next, match_hmap_node, &installed_flows) { + unlink_all_refs_for_installed_flow(i); + struct desired_flow *d = + desired_flow_lookup(flow_table, &i->flow, NULL); + if (!d) { + /* Installed flow is no longer desirable. Delete it from the + * switch and from installed_flows. */ + installed_flow_del(&i->flow, msgs); + ovn_flow_log(&i->flow, "removing installed"); + + hmap_remove(&installed_flows, &i->match_hmap_node); + installed_flow_destroy(i); + } else { + if (!ofpacts_equal(i->flow.ofpacts, i->flow.ofpacts_len, + d->flow.ofpacts, d->flow.ofpacts_len) || + i->flow.cookie != d->flow.cookie) { + installed_flow_mod(&i->flow, &d->flow, msgs); + ovn_flow_log(&i->flow, "updating installed"); + } + link_installed_to_desired(i, d); + + } + } + + /* Iterate through the desired flows and add those that aren't found + * in the installed flow table. */ + struct desired_flow *d; + HMAP_FOR_EACH (d, match_hmap_node, &flow_table->match_flow_table) { + i = installed_flow_lookup(&d->flow); + if (!i) { + ovn_flow_log(&d->flow, "adding installed"); + installed_flow_add(&d->flow, msgs); + + /* Copy 'd' from 'flow_table' to installed_flows. */ + i = installed_flow_dup(d); + hmap_insert(&installed_flows, &i->match_hmap_node, i->flow.hash); + } + link_installed_to_desired(i, d); + } +} + +static void +update_installed_flows_by_track(struct ovn_desired_flow_table *flow_table, + struct ovs_list *msgs) +{ + struct desired_flow *f, *f_next; + LIST_FOR_EACH_SAFE (f, f_next, track_list_node, + &flow_table->tracked_flows) { + ovs_list_remove(&f->track_list_node); + if (f->is_deleted) { + /* The desired flow was deleted */ + if (f->installed_flow) { + struct installed_flow *i = f->installed_flow; + unlink_installed_to_desired(i, f); + + if (!i->desired_flow) { + installed_flow_del(&i->flow, msgs); + ovn_flow_log(&i->flow, "removing installed (tracked)"); + + hmap_remove(&installed_flows, &i->match_hmap_node); + installed_flow_destroy(i); + } else { + /* There are other desired flow(s) referencing this + * installed flow, so update the OVS flow for the new + * active flow (at least the cookie will be different, + * even if the actions are the same). */ + struct desired_flow *d = i->desired_flow; + ovn_flow_log(&i->flow, "updating installed (tracked)"); + installed_flow_mod(&i->flow, &d->flow, msgs); + } + } + desired_flow_destroy(f); + } else { + /* The desired flow was added or modified. */ + struct installed_flow *i = installed_flow_lookup(&f->flow); + if (!i) { + /* Adding a new flow. */ + installed_flow_add(&f->flow, msgs); + ovn_flow_log(&f->flow, "adding installed (tracked)"); + + /* Copy 'f' from 'flow_table' to installed_flows. */ + struct installed_flow *new_node = installed_flow_dup(f); + hmap_insert(&installed_flows, &new_node->match_hmap_node, + new_node->flow.hash); + link_installed_to_desired(new_node, f); + } else if (i->desired_flow == f) { + /* The installed flow is installed for f, but f has change + * tracked, so it must have been modified. */ + ovn_flow_log(&i->flow, "updating installed (tracked)"); + installed_flow_mod(&i->flow, &f->flow, msgs); + } else { + /* Adding a new flow that conflicts with an existing installed + * flow, so just add it to the link. */ + link_installed_to_desired(i, f); + } + /* The track_list_node emptyness is used to check if the node is + * already added to track list, so initialize it again here. */ + ovs_list_init(&f->track_list_node); + } + } +} + /* The flow table can be updated if the connection to the switch is up and * in the correct state and not backlogged with existing flow_mods. (Our * criteria for being backlogged appear very conservative, but the socket @@ -1652,48 +1868,10 @@ ofctrl_put(struct ovn_desired_flow_table *flow_table, } } - /* Iterate through all of the installed flows. If any of them are no - * longer desired, delete them; if any of them should have different - * actions, update them. */ - struct installed_flow *i, *next; - HMAP_FOR_EACH_SAFE (i, next, match_hmap_node, &installed_flows) { - unlink_all_refs_for_installed_flow(i); - struct desired_flow *d = desired_flow_lookup(flow_table, &i->flow, - NULL); - if (!d) { - /* Installed flow is no longer desirable. Delete it from the - * switch and from installed_flows. */ - installed_flow_del(&i->flow, &msgs); - ovn_flow_log(&i->flow, "removing installed"); - hmap_remove(&installed_flows, &i->match_hmap_node); - installed_flow_destroy(i); - } else { - if (!ofpacts_equal(i->flow.ofpacts, i->flow.ofpacts_len, - d->flow.ofpacts, d->flow.ofpacts_len) || - i->flow.cookie != d->flow.cookie) { - ovn_flow_log(&i->flow, "updating installed"); - installed_flow_mod(&i->flow, &d->flow, &msgs); - } - link_installed_to_desired(i, d); - - } - } - - /* Iterate through the desired flows and add those that aren't found - * in the installed flow table. */ - struct desired_flow *d; - HMAP_FOR_EACH (d, match_hmap_node, &flow_table->match_flow_table) { - i = installed_flow_lookup(&d->flow); - if (!i) { - installed_flow_add(&d->flow, &msgs); - ovn_flow_log(&d->flow, "adding installed"); - - /* Copy 'd' from 'flow_table' to installed_flows. */ - i = installed_flow_dup(d); - hmap_insert(&installed_flows, &i->match_hmap_node, - i->flow.hash); - } - link_installed_to_desired(i, d); + if (flow_table->change_tracked) { + update_installed_flows_by_track(flow_table, &msgs); + } else { + update_installed_flows_by_compare(flow_table, &msgs); } /* Iterate through the installed groups from previous runs. If they @@ -1807,6 +1985,9 @@ ofctrl_put(struct ovn_desired_flow_table *flow_table, /* We were completely up-to-date before and still are. */ cur_cfg = nb_cfg; } + + flow_table->change_tracked = true; + ovs_assert(ovs_list_is_empty(&flow_table->tracked_flows)); } /* Looks up the logical port with the name 'port_name' in 'br_int_'. If diff --git a/controller/ofctrl.h b/controller/ofctrl.h index 8789ce490..64b0ea5dd 100644 --- a/controller/ofctrl.h +++ b/controller/ofctrl.h @@ -38,6 +38,11 @@ struct ovn_desired_flow_table { /* SB uuid index for the cross reference nodes that link to the nodes in * match_flow_table.*/ struct hmap uuid_flow_table; + + /* Is flow changes tracked. */ + bool change_tracked; + /* Tracked flow changes. */ + struct ovs_list tracked_flows; }; /* Interface for OVN main loop. */ @@ -99,7 +104,6 @@ void ofctrl_flood_remove_flows(struct ovn_desired_flow_table *, struct hmap *flood_remove_nodes); void ofctrl_flood_remove_add_node(struct hmap *flood_remove_nodes, const struct uuid *sb_uuid); - void ovn_desired_flow_table_init(struct ovn_desired_flow_table *); void ovn_desired_flow_table_clear(struct ovn_desired_flow_table *); void ovn_desired_flow_table_destroy(struct ovn_desired_flow_table *);