[ovs-dev] [PATCH 4/7] lib/rculist: New RCU-iterator, single-writer doubly-linked list.

Jarno Rajahalme jrajahalme at nicira.com
Fri Oct 24 20:36:38 UTC 2014


rculist allows concurrent lockless list iteration, while a writer may
be modifying the list.  Multiple writers can be supported by using a
mutex in addition to rculist.

First user will be added in a following patch.

Signed-off-by: Jarno Rajahalme <jrajahalme at nicira.com>
---
 lib/automake.mk |    2 +
 lib/rculist.c   |   27 ++++
 lib/rculist.h   |  404 +++++++++++++++++++++++++++++++++++++++++++++++++++++++
 3 files changed, 433 insertions(+)
 create mode 100644 lib/rculist.c
 create mode 100644 lib/rculist.h

diff --git a/lib/automake.mk b/lib/automake.mk
index 2cda9bd..7572e95 100644
--- a/lib/automake.mk
+++ b/lib/automake.mk
@@ -187,6 +187,8 @@ 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 \
 	lib/rstp.c \
diff --git a/lib/rculist.c b/lib/rculist.c
new file mode 100644
index 0000000..61a03d0
--- /dev/null
+++ b/lib/rculist.c
@@ -0,0 +1,27 @@
+/*
+ * 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
new file mode 100644
index 0000000..5ae8f12
--- /dev/null
+++ b/lib/rculist.h
@@ -0,0 +1,404 @@
+/*
+ * Copyright (c) 2008, 2009, 2010, 2011, 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.
+ */
+#ifndef RCULIST_H
+#define RCULIST_H 1
+
+/* A single writer multiple RCU-reader doubly linked list.
+ *
+ * RCU readers may iterate over the list at the same time as a writer is
+ * modifying the list.  Multiple writers can be supported by use of mutual
+ * exclusion, but rculist does not provide that, as the user of rculist
+ * typically does that already.
+ *
+ * To be RCU-friendly, the struct rculist instances must be freed via
+ * ovsrcu_postpone().
+ *
+ * The API is almost the same as for struct list, with the following exeptions:
+ *
+ * - The 'prev' pointer may not be accessed by the user.
+ * - The 'next' pointer should be accessed via rculist_next() by readers, and
+ *   rculist_next_protected() by the writer.
+ * - No rculist_moved(): due to the memory management limitation stated above,
+ *   rculist instances may not be reallocated, as realloc may instantly free
+ *   the old memory.
+ * - 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.
+ *
+ * The following functions are variations of the struct list functions with
+ * similar names, but are now restricted to the writer use:
+ *
+ * - rculist_back_protected()
+ * - rculist_is_short_protected()
+ * - rculist_is_singleton_protected()
+ */
+
+#include <stdbool.h>
+#include <stddef.h>
+#include "ovs-rcu.h"
+#include "util.h"
+
+/* A non-existing mutex to make it more difficult for an user to accidentally
+ * keep using the 'prev' pointer.  This may be helpful when porting code from
+ * struct list to rculist. */
+extern struct ovs_mutex rculist_fake_mutex;
+
+/* Doubly linked list head or element. */
+struct rculist {
+    /* Previous list element. */
+    struct rculist *prev OVS_GUARDED_BY(rculist_fake_mutex);
+
+    /* Next list element. */
+    OVSRCU_TYPE(struct rculist *) next;
+};
+
+/* Easier access to 'next' member. */
+static inline const struct rculist *rculist_next(const struct rculist *);
+static inline struct rculist *rculist_next_protected(const struct rculist *);
+
+/* List initialization. */
+#define RCULIST_INITIALIZER(LIST) { LIST, OVSRCU_INITIALIZER(LIST) }
+
+static inline void rculist_init(struct rculist *list);
+static inline void rculist_poison(struct rculist *elem);
+
+/* List insertion. */
+static inline void rculist_insert(struct rculist *list, struct rculist *elem);
+static inline void rculist_splice_hidden(struct rculist *before,
+                                         struct rculist *first,
+                                         struct rculist *last);
+static inline void rculist_push_front(struct rculist *list,
+                                      struct rculist *elem);
+static inline void rculist_push_back(struct rculist *list,
+                                     struct rculist *elem);
+static inline void rculist_replace(struct rculist *replacement,
+                                   struct rculist *replaced);
+static inline void rculist_move(struct rculist *dst, struct rculist *src);
+
+/* List removal. */
+static inline struct rculist *rculist_remove(struct rculist *elem);
+static inline struct rculist *rculist_pop_front(struct rculist *list);
+static inline struct rculist *rculist_pop_back(struct rculist *list);
+
+/* List elements. */
+static inline const struct rculist *rculist_front(const struct rculist *);
+static inline struct rculist *rculist_back_protected(const struct rculist *);
+
+/* List properties. */
+static inline size_t rculist_size(const struct rculist *);
+static inline bool rculist_is_empty(const struct rculist *);
+static inline bool rculist_is_singleton_protected(const struct rculist *);
+static inline bool rculist_is_short_protected(const struct rculist *);
+
+
+/* Inline implementations. */
+
+static inline const struct rculist *
+rculist_next(const struct rculist *list)
+{
+    return ovsrcu_get(struct rculist *, &list->next);
+}
+
+static inline struct rculist *
+rculist_next_protected(const struct rculist *list)
+
+{
+    return ovsrcu_get_protected(struct rculist *, &list->next);
+}
+
+static inline void
+rculist_init(struct rculist *list)
+    OVS_NO_THREAD_SAFETY_ANALYSIS
+{
+    list->prev = list;
+    ovsrcu_init(&list->next, list);
+}
+
+#define RCULIST_POISON (struct rculist *)(((UINTPTR_MAX / 4) + 1) * 3)
+
+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
+rculist_poison(struct rculist *list)
+    OVS_NO_THREAD_SAFETY_ANALYSIS
+{
+    list->prev = RCULIST_POISON;
+    ovsrcu_postpone(rculist_poison__, list);
+}
+
+/* rculist insertion. */
+static inline void
+rculist_insert(struct rculist *before, struct rculist *elem)
+    OVS_NO_THREAD_SAFETY_ANALYSIS
+{
+    elem->prev = before->prev;
+    ovsrcu_set_hidden(&elem->next, before);
+    ovsrcu_set(&before->prev->next, elem);
+    before->prev = elem;
+}
+
+/* Removes elements 'first' though 'last' (exclusive) from their current list,
+ * which may NOT be visible to any other threads (== be hidden from them),
+ * then inserts them just before 'before'. */
+static inline void
+rculist_splice_hidden(struct rculist *before, struct rculist *first,
+                      struct rculist *last)
+    OVS_NO_THREAD_SAFETY_ANALYSIS
+{
+    struct rculist *last_next;
+
+    if (first == last) {
+        return;
+    }
+    last = last->prev;
+
+    /* Cleanly remove 'first'...'last' from its current list. */
+    last_next = rculist_next_protected(last);
+    last_next->prev = first->prev;
+    ovsrcu_set(&first->prev->next, last_next);
+
+    /* Splice 'first'...'last' into new list. */
+    first->prev = before->prev;
+    ovsrcu_set(&last->next, before);
+    ovsrcu_set(&before->prev->next, first);
+    before->prev = last;
+}
+
+/* Inserts 'elem' at the beginning of 'list', so that it becomes the front in
+ * 'list'. */
+static inline void
+rculist_push_front(struct rculist *list, struct rculist *elem)
+{
+    rculist_insert(rculist_next_protected(list), elem);
+}
+
+/* Inserts 'elem' at the end of 'list', so that it becomes the back in
+ * 'list'. */
+static inline void
+rculist_push_back(struct rculist *list, struct rculist *elem)
+{
+    rculist_insert(list, elem);
+}
+
+/* Puts 'element' in the position currently occupied by 'position'.
+ *
+ * Afterward, 'position' is not linked to from the list any more, but still
+ * links to the nodes in the list, and may still be referenced by other threads
+ * until all other threads quiesce.  The replaced node ('position') may not be
+ * re-inserted, re-initialized, or deleted until after all other threads have
+ * quiesced (use ovsrcu_postpone). */
+static inline void
+rculist_replace(struct rculist *element, struct rculist *position)
+    OVS_NO_THREAD_SAFETY_ANALYSIS
+{
+    struct rculist *position_next = rculist_next_protected(position);
+
+    ovsrcu_set(&element->next, position_next);
+    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
+}
+
+/* Initializes 'dst' with the contents of 'src', compensating for moving it
+ * around in memory.  The effect is that, if 'src' was the head of a list, now
+ * 'dst' is the head of a list containing the same elements.
+ *
+ * Memory for 'src' must be kept around until the next RCU quiescent period.
+ * rculist cannot be simply reallocated, so there is no rculist_moved(). */
+static inline void
+rculist_move(struct rculist *dst, struct rculist *src)
+    OVS_NO_THREAD_SAFETY_ANALYSIS
+{
+    if (!rculist_is_empty(src)) {
+        struct rculist *src_next = rculist_next_protected(src);
+
+        dst->prev = src->prev;
+        ovsrcu_set_hidden(&dst->next, src_next);
+
+        src_next->prev = dst;
+        ovsrcu_set(&src->prev->next, dst);
+    } else {
+        rculist_init(dst);
+    }
+
+#ifndef NDEBUG
+    rculist_poison(src); /* XXX: Some overhead due to ovsrcu_postpone() */
+#endif
+}
+
+/* Removes 'elem' from its list and returns the element that followed it.
+ * Undefined behavior if 'elem' is not in a list.
+ *
+ * Afterward, 'elem' is not linked to from the list any more, but still links
+ * to the nodes in the list, and may still be referenced by other threads until
+ * all other threads quiesce.  The removed node ('elem') may not be
+ * re-inserted, re-initialized, or deleted until after all other threads have
+ * quiesced (use ovsrcu_postpone).
+ */
+static inline struct rculist *
+rculist_remove(struct rculist *elem)
+    OVS_NO_THREAD_SAFETY_ANALYSIS
+{
+    struct rculist *elem_next = rculist_next_protected(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
+    return elem_next;
+}
+
+/* Removes the front element from 'list' and returns it.  Undefined behavior if
+ * 'list' is empty before removal.
+ *
+ * Afterward, teh returned former first node is not linked to from the list any
+ * more, but still links to the nodes in the list, and may still be referenced
+ * by other threads until all other threads quiesce.  The returned node may not
+ * be re-inserted, re-initialized, or deleted until after all other threads
+ * have quiesced (use ovsrcu_postpone). */
+static inline struct rculist *
+rculist_pop_front(struct rculist *list)
+    OVS_NO_THREAD_SAFETY_ANALYSIS
+{
+    struct rculist *front = rculist_next_protected(list);
+    rculist_remove(front);
+    return front;
+}
+
+/* Removes the back element from 'list' and returns it.
+ * Undefined behavior if 'list' is empty before removal.
+ *
+ * Afterward, teh returned former last node is not linked to from the list any
+ * more, but still links to the nodes in the list, and may still be referenced
+ * by other threads until all other threads quiesce.  The returned node may not
+ * be re-inserted, re-initialized, or deleted until after all other threads
+ * have quiesced (use ovsrcu_postpone). */
+static inline struct rculist *
+rculist_pop_back(struct rculist *list)
+    OVS_NO_THREAD_SAFETY_ANALYSIS
+{
+    struct rculist *back = list->prev;
+    rculist_remove(back);
+    return back;
+}
+
+/* Returns the front element in 'list_'.
+ * Undefined behavior if 'list_' is empty. */
+static inline const struct rculist *
+rculist_front(const struct rculist *list)
+{
+#ifndef NDEBUG
+    ovs_assert(!rculist_is_empty(list));
+#endif
+    return rculist_next(list);
+}
+
+/* Returns the back element in 'list_'.
+ * Undefined behavior if 'list_' is empty. */
+static inline struct rculist *
+rculist_back_protected(const struct rculist *list_)
+    OVS_NO_THREAD_SAFETY_ANALYSIS
+{
+    struct rculist *list = CONST_CAST(struct rculist *, list_);
+#ifndef NDEBUG
+    ovs_assert(!rculist_is_empty(list));
+#endif
+    return list->prev;
+}
+
+/* Returns the number of elements in 'list'.
+ * Runs in O(n) in the number of elements. */
+static inline size_t
+rculist_size(const struct rculist *list)
+{
+    const struct rculist *e;
+    size_t cnt = 0;
+
+    for (e = rculist_next(list); e != list; e = rculist_next(e)) {
+        cnt++;
+    }
+    return cnt;
+}
+
+/* Returns true if 'list' is empty, false otherwise. */
+static inline bool
+rculist_is_empty(const struct rculist *list)
+{
+    return rculist_next(list) == list;
+}
+
+/* Returns true if 'list' has 0 or 1 elements, false otherwise. */
+static inline bool
+rculist_is_short_protected(const struct rculist *list)
+    OVS_NO_THREAD_SAFETY_ANALYSIS
+{
+    return rculist_next_protected(list) == list->prev;
+}
+
+/* Returns true if 'list' has exactly 1 element, false otherwise. */
+static inline bool
+rculist_is_singleton_protected(const struct rculist *list)
+    OVS_NO_THREAD_SAFETY_ANALYSIS
+{
+    const struct rculist *list_next = rculist_next_protected(list);
+
+    return list_next == list->prev && list_next != list;
+}
+
+#define RCULIST_FOR_EACH(ITER, MEMBER, RCULIST)                         \
+    for (INIT_CONTAINER(ITER, rculist_next(RCULIST), MEMBER);           \
+         &(ITER)->MEMBER != (RCULIST);                                  \
+         ASSIGN_CONTAINER(ITER, rculist_next(&(ITER)->MEMBER), MEMBER))
+#define RCULIST_FOR_EACH_CONTINUE(ITER, MEMBER, RCULIST)                \
+    for (ASSIGN_CONTAINER(ITER, rculist_next(&(ITER)->MEMBER), MEMBER);   \
+         &(ITER)->MEMBER != (RCULIST);                                  \
+         ASSIGN_CONTAINER(ITER, rculist_next(&(ITER)->MEMBER), MEMBER))
+
+#define RCULIST_FOR_EACH_REVERSE_PROTECTED(ITER, MEMBER, RCULIST)       \
+    for (INIT_CONTAINER(ITER, (RCULIST)->prev, MEMBER);                 \
+         &(ITER)->MEMBER != (RCULIST);                                  \
+         ASSIGN_CONTAINER(ITER, (ITER)->MEMBER.prev, MEMBER))
+#define RCULIST_FOR_EACH_REVERSE_PROTECTED_CONTINUE(ITER, MEMBER, RCULIST) \
+    for (ASSIGN_CONTAINER(ITER, (ITER)->MEMBER.prev, MEMBER);           \
+         &(ITER)->MEMBER != (RCULIST);                                  \
+         ASSIGN_CONTAINER(ITER, (ITER)->MEMBER.prev, MEMBER))
+
+#define RCULIST_FOR_EACH_PROTECTED(ITER, MEMBER, RCULIST)               \
+    for (INIT_CONTAINER(ITER, rculist_next_protected(RCULIST), MEMBER); \
+         &(ITER)->MEMBER != (RCULIST);                                  \
+         ASSIGN_CONTAINER(ITER, rculist_next_protected(&(ITER)->MEMBER), \
+                          MEMBER))
+
+#define RCULIST_FOR_EACH_SAFE_PROTECTED(ITER, NEXT, MEMBER, RCULIST)    \
+    for (INIT_CONTAINER(ITER, rculist_next_protected(RCULIST), MEMBER); \
+         (&(ITER)->MEMBER != (RCULIST)                                  \
+          ? INIT_CONTAINER(NEXT, rculist_next_protected(&(ITER)->MEMBER), \
+                           MEMBER), 1 : 0);                             \
+         (ITER) = (NEXT))
+
+#endif /* rculist.h */
-- 
1.7.10.4




More information about the dev mailing list