| Message ID | 20160824021850.11359-1-joe@ovn.org |
|---|---|
| State | Changes Requested |
| Headers | show |
On Tue, Aug 23, 2016 at 07:18:50PM -0700, Joe Stringer wrote: > If a revalidator dumps/revalidates a flow during the 'dump' phase, > resulting in the deletion of the flow, then ukey->flow_exists is set to > false, and the ukey is kept around until the 'sweep' phase. The ukey is > kept around to ensure that cases like duplicated dumps from the > datapaths do not result in multiple attribution of the same stats. > > However, if an upcall for this flow comes for a handler between the > revalidator 'dump' and 'sweep' phases, the handler will lookup the ukey > and find that the ukey exists, then skip installing a new flow entirely. > As a result, for this period all traffic for the flow is slowpathed. > If there is a lot of traffic hitting this flow, then it will all be > handled in userspace until the 'sweep' phase. Eventually the > revalidators will reach the sweep phase and delete the ukey, and > subsequently the handlers should install a new flow. > > To reduce the slowpathing of this traffic during flow table transitions, > allow the handler to identify this case during miss upcall handling and > replace the existing ukey with a new ukey. The handler will then be able > to install a flow for this traffic, allowing the traffic flow to return > to the fastpath. > > There are three situations where the existing ukey has "flow_exists" set > to false: > > * Firstly, the flow for the ukey might not yet have been installed. In > this case, the other handler that set up this ukey will be holding the > lock for the ukey. So, if we attempt to grab the lock and fail then > another handler is already setting up the flow and we can safely skip > flow install. > * Secondly, a revalidator could be currently deleting the flow. In this > case, the revalidator holds the ukey lock so the handler will fail to > grab it. This is fine, if traffic continues to miss then a subsequent > miss upcall will hit the third case. > * Thirdly, the flow may have been recently deleted by a revalidator > thread. In this case, we can grab the lock. From the handler thread > we swap the original key out for a new one and rcu-defer its deletion. > Sweeper code gets the ukey lock, looks up flow_exists, then releases the lock. Now try_ukey_replace succeeds at getting the lock. Sweeper is waiting on the umap mutex, as ukey_install_start holds it. Now both will free the old ukey. Is that analysis correct? Thanks. Cascardo. > Signed-off-by: Joe Stringer <joe@ovn.org> > --- > ofproto/ofproto-dpif-upcall.c | 29 +++++++++++++++++++++++++++++ > 1 file changed, 29 insertions(+) > > diff --git a/ofproto/ofproto-dpif-upcall.c b/ofproto/ofproto-dpif-upcall.c > index 042a50a9f179..5a0ecc2a6fe6 100644 > --- a/ofproto/ofproto-dpif-upcall.c > +++ b/ofproto/ofproto-dpif-upcall.c > @@ -50,6 +50,7 @@ COVERAGE_DEFINE(dumped_duplicate_flow); > COVERAGE_DEFINE(dumped_new_flow); > COVERAGE_DEFINE(handler_duplicate_upcall); > COVERAGE_DEFINE(upcall_ukey_contention); > +COVERAGE_DEFINE(upcall_ukey_replace); > COVERAGE_DEFINE(revalidate_missed_dp_flow); > > /* A thread that reads upcalls from dpif, forwards each upcall's packet, > @@ -1569,6 +1570,33 @@ ukey_create_from_dpif_flow(const struct udpif *udpif, > return 0; > } > > +static bool > +try_ukey_replace(struct umap *umap, struct udpif_key *old_ukey, > + struct udpif_key *new_ukey) > + OVS_REQUIRES(umap->mutex) > + OVS_TRY_LOCK(true, new_ukey->mutex) > +{ > + bool replaced = false; > + > + if (!ovs_mutex_trylock(&old_ukey->mutex)) { > + if (!old_ukey->flow_exists) { > + /* The flow was deleted during the current revalidator dump, > + * but its ukey won't be cleaned up until the sweep phase. > + * In the mean time, we are receiving upcalls for this traffic. > + * Expedite the flow install by replacing the ukey. */ > + COVERAGE_INC(upcall_ukey_replace); > + ovs_mutex_lock(&new_ukey->mutex); > + cmap_replace(&umap->cmap, &old_ukey->cmap_node, > + &new_ukey->cmap_node, new_ukey->hash); > + ovsrcu_postpone(ukey_delete__, old_ukey); > + replaced = true; > + } > + ovs_mutex_unlock(&old_ukey->mutex); > + } > + > + return replaced; > +} > + > /* Attempts to insert a ukey into the shared ukey maps. > * > * On success, returns true, installs the ukey and returns it in a locked > @@ -1591,6 +1619,7 @@ ukey_install_start(struct udpif *udpif, struct udpif_key *new_ukey) > if (old_ukey->key_len == new_ukey->key_len > && !memcmp(old_ukey->key, new_ukey->key, new_ukey->key_len)) { > COVERAGE_INC(handler_duplicate_upcall); > + locked = try_ukey_replace(umap, old_ukey, new_ukey); > } else { > struct ds ds = DS_EMPTY_INITIALIZER; > > -- > 2.9.3 > > _______________________________________________ > dev mailing list > dev@openvswitch.org > http://openvswitch.org/mailman/listinfo/dev
On 25 August 2016 at 13:15, Thadeu Lima de Souza Cascardo <cascardo@redhat.com> wrote: > On Tue, Aug 23, 2016 at 07:18:50PM -0700, Joe Stringer wrote: >> If a revalidator dumps/revalidates a flow during the 'dump' phase, >> resulting in the deletion of the flow, then ukey->flow_exists is set to >> false, and the ukey is kept around until the 'sweep' phase. The ukey is >> kept around to ensure that cases like duplicated dumps from the >> datapaths do not result in multiple attribution of the same stats. >> >> However, if an upcall for this flow comes for a handler between the >> revalidator 'dump' and 'sweep' phases, the handler will lookup the ukey >> and find that the ukey exists, then skip installing a new flow entirely. >> As a result, for this period all traffic for the flow is slowpathed. >> If there is a lot of traffic hitting this flow, then it will all be >> handled in userspace until the 'sweep' phase. Eventually the >> revalidators will reach the sweep phase and delete the ukey, and >> subsequently the handlers should install a new flow. >> >> To reduce the slowpathing of this traffic during flow table transitions, >> allow the handler to identify this case during miss upcall handling and >> replace the existing ukey with a new ukey. The handler will then be able >> to install a flow for this traffic, allowing the traffic flow to return >> to the fastpath. >> >> There are three situations where the existing ukey has "flow_exists" set >> to false: >> >> * Firstly, the flow for the ukey might not yet have been installed. In >> this case, the other handler that set up this ukey will be holding the >> lock for the ukey. So, if we attempt to grab the lock and fail then >> another handler is already setting up the flow and we can safely skip >> flow install. >> * Secondly, a revalidator could be currently deleting the flow. In this >> case, the revalidator holds the ukey lock so the handler will fail to >> grab it. This is fine, if traffic continues to miss then a subsequent >> miss upcall will hit the third case. >> * Thirdly, the flow may have been recently deleted by a revalidator >> thread. In this case, we can grab the lock. From the handler thread >> we swap the original key out for a new one and rcu-defer its deletion. >> > > Sweeper code gets the ukey lock, looks up flow_exists, then releases the lock. > Now try_ukey_replace succeeds at getting the lock. Sweeper is waiting on the > umap mutex, as ukey_install_start holds it. Now both will free the old ukey. > > Is that analysis correct? You're quite right, thanks for the analysis. Today, this 'flow_exists' boolean holds two pieces of information: "Is the flow present in the datapath? and "Is the ukey deletion queued?" The way that this operates today, the answer to both of these questions is the same (based on the way that ukeys are locked in different threads). However, this patch changes the situation a little bit, because now it is possible for a handler thread to remove a ukey from the map and queue its deletion. Although it does the removal under a mutex, which protects the map, it is still possible for a revalidator thread to sweep through and find the same ukey before the next RCU grace period, in which case it will *also* attempt to remove the ukey and queue its deletion. This isn't good. As a general point of information, this ukey_install_start() typically happens from handler threads, although in certain cases in may also occur in revalidator thread processing (while handling a dump from the kernel, for a flow that userspace doesn't know about - eg ovs-vswitchd restart). One way to fix the above would be simply, do not unlock the old ukey's mutex when replacing it in the map. This would mean that even if a revalidator thread found the ukey while sweeping, it would fail to grab the lock and skip it. After the next RCU grace period it would no longer be found. However, I think this just makes the behaviour harder to track and more implicit. Instead, I plan to split out the "flow_exists" in to a simple statemachine that progresses through the 3 cases listed in the end of this commit message, which should make the lifecycle of the ukey more clear. With a clearer progression between the ukey status, we should be able to fix this case in v2 of this patch as well. To spell it out a bit more, and hopefully catch any pieces I might miss, I mean to say: * When a ukey is first created, it is locked, and we can put its 'state', for want of a better word, as UKEY_CREATED. * When the flow for a ukey gets installed, during ukey_install_finish(), we can change it to UKEY_INSTALLED. * If a revalidator determines that the flow should be removed, it can change it to UKEY_REMOVED. * When either: - A revalidator sweeps through ukeys and removes it from the map, OR - A handler thread does the replace as per the code in this patch, ...we can RCU-defer its deletion and change it to UKEY_DELETED. Ukeys will only be allowed to transition forward, ie, in the above order. Once removed, it must not be re-inserted. Furthermore, if there is ever a lookup that finds a locked ukey, then it is safe to skip it. either a handler is currently installing it, or a revalidator is removing it. If the state is UKEY_DELETED, then the ukey should not be replaced (although it should be safe to just insert the new ukey instead).
diff --git a/ofproto/ofproto-dpif-upcall.c b/ofproto/ofproto-dpif-upcall.c index 042a50a9f179..5a0ecc2a6fe6 100644 --- a/ofproto/ofproto-dpif-upcall.c +++ b/ofproto/ofproto-dpif-upcall.c @@ -50,6 +50,7 @@ COVERAGE_DEFINE(dumped_duplicate_flow); COVERAGE_DEFINE(dumped_new_flow); COVERAGE_DEFINE(handler_duplicate_upcall); COVERAGE_DEFINE(upcall_ukey_contention); +COVERAGE_DEFINE(upcall_ukey_replace); COVERAGE_DEFINE(revalidate_missed_dp_flow); /* A thread that reads upcalls from dpif, forwards each upcall's packet, @@ -1569,6 +1570,33 @@ ukey_create_from_dpif_flow(const struct udpif *udpif, return 0; } +static bool +try_ukey_replace(struct umap *umap, struct udpif_key *old_ukey, + struct udpif_key *new_ukey) + OVS_REQUIRES(umap->mutex) + OVS_TRY_LOCK(true, new_ukey->mutex) +{ + bool replaced = false; + + if (!ovs_mutex_trylock(&old_ukey->mutex)) { + if (!old_ukey->flow_exists) { + /* The flow was deleted during the current revalidator dump, + * but its ukey won't be cleaned up until the sweep phase. + * In the mean time, we are receiving upcalls for this traffic. + * Expedite the flow install by replacing the ukey. */ + COVERAGE_INC(upcall_ukey_replace); + ovs_mutex_lock(&new_ukey->mutex); + cmap_replace(&umap->cmap, &old_ukey->cmap_node, + &new_ukey->cmap_node, new_ukey->hash); + ovsrcu_postpone(ukey_delete__, old_ukey); + replaced = true; + } + ovs_mutex_unlock(&old_ukey->mutex); + } + + return replaced; +} + /* Attempts to insert a ukey into the shared ukey maps. * * On success, returns true, installs the ukey and returns it in a locked @@ -1591,6 +1619,7 @@ ukey_install_start(struct udpif *udpif, struct udpif_key *new_ukey) if (old_ukey->key_len == new_ukey->key_len && !memcmp(old_ukey->key, new_ukey->key, new_ukey->key_len)) { COVERAGE_INC(handler_duplicate_upcall); + locked = try_ukey_replace(umap, old_ukey, new_ukey); } else { struct ds ds = DS_EMPTY_INITIALIZER;
If a revalidator dumps/revalidates a flow during the 'dump' phase, resulting in the deletion of the flow, then ukey->flow_exists is set to false, and the ukey is kept around until the 'sweep' phase. The ukey is kept around to ensure that cases like duplicated dumps from the datapaths do not result in multiple attribution of the same stats. However, if an upcall for this flow comes for a handler between the revalidator 'dump' and 'sweep' phases, the handler will lookup the ukey and find that the ukey exists, then skip installing a new flow entirely. As a result, for this period all traffic for the flow is slowpathed. If there is a lot of traffic hitting this flow, then it will all be handled in userspace until the 'sweep' phase. Eventually the revalidators will reach the sweep phase and delete the ukey, and subsequently the handlers should install a new flow. To reduce the slowpathing of this traffic during flow table transitions, allow the handler to identify this case during miss upcall handling and replace the existing ukey with a new ukey. The handler will then be able to install a flow for this traffic, allowing the traffic flow to return to the fastpath. There are three situations where the existing ukey has "flow_exists" set to false: * Firstly, the flow for the ukey might not yet have been installed. In this case, the other handler that set up this ukey will be holding the lock for the ukey. So, if we attempt to grab the lock and fail then another handler is already setting up the flow and we can safely skip flow install. * Secondly, a revalidator could be currently deleting the flow. In this case, the revalidator holds the ukey lock so the handler will fail to grab it. This is fine, if traffic continues to miss then a subsequent miss upcall will hit the third case. * Thirdly, the flow may have been recently deleted by a revalidator thread. In this case, we can grab the lock. From the handler thread we swap the original key out for a new one and rcu-defer its deletion. Signed-off-by: Joe Stringer <joe@ovn.org> --- ofproto/ofproto-dpif-upcall.c | 29 +++++++++++++++++++++++++++++ 1 file changed, 29 insertions(+)