[ovs-dev] [PATCH v2] rculist: Remove postponed poisoning.

Jarno Rajahalme jrajahalme at nicira.com
Thu Jun 11 23:49:06 UTC 2015


I sent a v3 that compiles also on clang.

  Jarno

> On Jun 11, 2015, at 11:06 AM, Jarno Rajahalme <jrajahalme at nicira.com> wrote:
> 
> Postponed 'next' member poisoning was based on the faulty assumption
> that postponed functions would be called in the order they were
> postponed.  This assumption holds only for the functions postponed by
> any single thread.  When functions are postponed by different
> threads, there are no guarantees of the order in which the functions
> may be called, or timing between those calls after the next grace
> period has passed.
> 
> Given this, the postponed poisoning could have executed after
> postponed destruction of the object containing the rculist element.
> 
> This bug was revealed after the memory leaks on rule deletion were
> recently fixed.
> 
> This patch removes the postponed 'next' member poisoning and adds
> documentation describing the ordering limitations in OVS RCU.
> 
> Alex Wang dug out the root cause of the resulting crashes, thanks!
> 
> Signed-off-by: Jarno Rajahalme <jrajahalme at nicira.com>
> ---
> v2: rebase.
> 
> lib/automake.mk  |    1 -
> lib/classifier.c |    7 +++----
> lib/ovs-rcu.c    |   13 +++++++++++++
> lib/ovs-rcu.h    |   15 ++++++++++++++-
> lib/rculist.c    |   27 ---------------------------
> lib/rculist.h    |   36 +++++++++++++++++-------------------
> 6 files changed, 47 insertions(+), 52 deletions(-)
> delete mode 100644 lib/rculist.c
> 
> diff --git a/lib/automake.mk b/lib/automake.mk
> index 7a34c1a..f082115 100644
> --- a/lib/automake.mk
> +++ b/lib/automake.mk
> @@ -197,7 +197,6 @@ lib_libopenvswitch_la_SOURCES = \
> 	lib/random.h \
> 	lib/rconn.c \
> 	lib/rconn.h \
> -	lib/rculist.c \
> 	lib/rculist.h \
> 	lib/reconnect.c \
> 	lib/reconnect.h \
> diff --git a/lib/classifier.c b/lib/classifier.c
> index 2b2d3f6..12d91e3 100644
> --- a/lib/classifier.c
> +++ b/lib/classifier.c
> @@ -276,11 +276,10 @@ cls_rule_destroy(struct cls_rule *rule)
> {
>     ovs_assert(!rule->cls_match);   /* Must not be in a classifier. */
> 
> -    /* Check that the rule has been properly removed from the classifier and
> -     * that the destruction only happens after the RCU grace period, or that
> -     * the rule was never inserted to the classifier in the first place. */
> -    ovs_assert(rculist_next_protected(&rule->node) == RCULIST_POISON
> +    /* Check that the rule has been properly removed from the classifier. */
> +    ovs_assert(rule->node.prev == RCULIST_POISON
>                || rculist_is_empty(&rule->node));
> +    rculist_poison__(&rule->node);   /* Poisons also the next pointer. */
> 
>     minimatch_destroy(CONST_CAST(struct minimatch *, &rule->match));
> }
> diff --git a/lib/ovs-rcu.c b/lib/ovs-rcu.c
> index e0634cf..b8f8bc4 100644
> --- a/lib/ovs-rcu.c
> +++ b/lib/ovs-rcu.c
> @@ -212,6 +212,19 @@ ovsrcu_synchronize(void)
> /* Registers 'function' to be called, passing 'aux' as argument, after the
>  * next grace period.
>  *
> + * The call is guaranteed to happen after the next time all participating
> + * threads have quiesced at least once, but there is no quarantee that all
> + * registered functions are called as early as possible, or that the functions
> + * registered by different threads would be called in the order the
> + * registrations took place.  In particular, even if two threads provably
> + * register a function each in a specific order, the functions may still be
> + * called in the opposite order, depending on the timing of when the threads
> + * call ovsrcu_quiesce(), how many functions they postpone, and when the
> + * ovs-rcu thread happens to grab the functions to be called.
> + *
> + * All functions registered by a single thread are guaranteed to execute in the
> + * registering order, however.
> + *
>  * This function is more conveniently called through the ovsrcu_postpone()
>  * macro, which provides a type-safe way to allow 'function''s parameter to be
>  * any pointer type. */
> diff --git a/lib/ovs-rcu.h b/lib/ovs-rcu.h
> index 1d79976..c1e3d60 100644
> --- a/lib/ovs-rcu.h
> +++ b/lib/ovs-rcu.h
> @@ -60,12 +60,25 @@
>  *
>  * When a quiescient state has occurred in every thread, we say that a "grace
>  * period" has occurred.  Following a grace period, all of the callbacks
> - * postponed before the start of the grace period may be invoked.  OVS takes
> + * postponed before the start of the grace period MAY be invoked.  OVS takes
>  * care of this automatically through the RCU mechanism: while a process still
>  * has only a single thread, it invokes the postponed callbacks directly from
>  * ovsrcu_quiesce() and ovsrcu_quiesce_start(); after additional threads have
>  * been created, it creates an extra helper thread to invoke callbacks.
>  *
> + * Please note that while a postponed function call is guaranteed to happen
> + * after the next time all participating threads have quiesced at least once,
> + * there is no quarantee that all postponed functions are called as early as
> + * possible, or that the functions postponed by different threads would be
> + * called in the order the registrations took place.  In particular, even if
> + * two threads provably postpone a function each in a specific order, the
> + * postponed functions may still be called in the opposite order, depending on
> + * the timing of when the threads call ovsrcu_quiesce(), how many functions
> + * they postpone, and when the ovs-rcu thread happens to grab the functions to
> + * be called.
> + *
> + * All functions postponed by a single thread are guaranteed to execute in the
> + * order they were postponed, however.
>  *
>  * Use
>  * ---
> diff --git a/lib/rculist.c b/lib/rculist.c
> deleted file mode 100644
> index 61a03d0..0000000
> --- a/lib/rculist.c
> +++ /dev/null
> @@ -1,27 +0,0 @@
> -/*
> - * Copyright (c) 2008, 2009, 2010, 2011, 2012, 2013, 2014 Nicira, Inc.
> - *
> - * Licensed under the Apache License, Version 2.0 (the "License");
> - * you may not use this file except in compliance with the License.
> - * You may obtain a copy of the License at:
> - *
> - *     http://www.apache.org/licenses/LICENSE-2.0
> - *
> - * Unless required by applicable law or agreed to in writing, software
> - * distributed under the License is distributed on an "AS IS" BASIS,
> - * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
> - * See the License for the specific language governing permissions and
> - * limitations under the License.
> - */
> -#include <config.h>
> -#include "rculist.h"
> -
> -/* Initializes 'list' with pointers that will (probably) cause segfaults if
> - * dereferenced and, better yet, show up clearly in a debugger. */
> -void
> -rculist_poison__(struct rculist *list)
> -    OVS_NO_THREAD_SAFETY_ANALYSIS
> -{
> -    list->prev = RCULIST_POISON;
> -    ovsrcu_set_hidden(&list->next, RCULIST_POISON);
> -}
> diff --git a/lib/rculist.h b/lib/rculist.h
> index f3c1475..7ba20e5 100644
> --- a/lib/rculist.h
> +++ b/lib/rculist.h
> @@ -38,10 +38,7 @@
>  * - rculist_front() returns a const pointer to accommodate for an RCU reader.
>  * - rculist_splice_hidden(): Spliced elements may not have been visible to
>  *   RCU readers before the operation.
> - * - rculist_poison(): Immediately poisons the 'prev' pointer, and schedules
> - *   ovsrcu_postpone() to poison the 'next' pointer.  This issues a memory
> - *   write operation to the list element, hopefully crashing the program if
> - *   the list node was freed or re-used too early.
> + * - rculist_poison(): Only poisons the 'prev' pointer.
>  *
>  * The following functions are variations of the struct ovs_list functions with
>  * similar names, but are now restricted to the writer use:
> @@ -134,8 +131,6 @@ rculist_init(struct rculist *list)
> 
> #define RCULIST_POISON (struct rculist *)(UINTPTR_MAX / 0xf * 0xc)
> 
> -void rculist_poison__(struct rculist *list);
> -
> /* Initializes 'list' with pointers that will (probably) cause segfaults if
>  * dereferenced and, better yet, show up clearly in a debugger. */
> static inline void
> @@ -143,7 +138,19 @@ rculist_poison(struct rculist *list)
>     OVS_NO_THREAD_SAFETY_ANALYSIS
> {
>     list->prev = RCULIST_POISON;
> -    ovsrcu_postpone(rculist_poison__, list);
> +}
> +
> +/* Initializes 'list' with pointers that will (probably) cause segfaults if
> + * dereferenced and, better yet, show up clearly in a debugger.
> + *
> + * This variant poisons also the next pointer, so this may not be called if
> + * this list element is still visible to RCU readers. */
> +static inline void
> +rculist_poison__(struct rculist *list)
> +    OVS_NO_THREAD_SAFETY_ANALYSIS
> +{
> +    rculist_poison(list);
> +    ovsrcu_set_hidden(&list->next, RCULIST_POISON);
> }
> 
> /* rculist insertion. */
> @@ -217,10 +224,7 @@ rculist_replace(struct rculist *element, struct rculist *position)
>     position_next->prev = element;
>     element->prev = position->prev;
>     ovsrcu_set(&element->prev->next, element);
> -
> -#ifndef NDEBUG
> -    rculist_poison(position); /* XXX: Some overhead due to ovsrcu_postpone() */
> -#endif
> +    rculist_poison(position);
> }
> 
> /* Initializes 'dst' with the contents of 'src', compensating for moving it
> @@ -244,10 +248,7 @@ rculist_move(struct rculist *dst, struct rculist *src)
>     } else {
>         rculist_init(dst);
>     }
> -
> -#ifndef NDEBUG
> -    rculist_poison(src); /* XXX: Some overhead due to ovsrcu_postpone() */
> -#endif
> +    rculist_poison(src);
> }
> 
> /* Removes 'elem' from its list and returns the element that followed it.
> @@ -268,10 +269,7 @@ rculist_remove(struct rculist *elem)
> 
>     elem_next->prev = elem->prev;
>     ovsrcu_set(&elem->prev->next, elem_next);
> -
> -#ifndef NDEBUG
> -    rculist_poison(elem); /* XXX: Some overhead due to ovsrcu_postpone() */
> -#endif
> +    rculist_poison(elem);
>     return elem_next;
> }
> 
> -- 
> 1.7.10.4
> 




More information about the dev mailing list