An rcu-slist can be read and written without explicit locking: it uses RCU protected pointers and compare-exchange operations.
Signed-off-by: Daniele Di Proietto <[email protected]> --- lib/automake.mk | 1 + lib/rcu-slist.h | 84 +++++++++++++++++++++++++++++++++++++++++++++++++++++++++ 2 files changed, 85 insertions(+) create mode 100644 lib/rcu-slist.h diff --git a/lib/automake.mk b/lib/automake.mk index ec4ad8e..19fdc2b 100644 --- a/lib/automake.mk +++ b/lib/automake.mk @@ -186,6 +186,7 @@ lib_libopenvswitch_la_SOURCES = \ lib/random.h \ lib/rconn.c \ lib/rconn.h \ + lib/rcu-slist.h \ lib/reconnect.c \ lib/reconnect.h \ lib/rstp.c \ diff --git a/lib/rcu-slist.h b/lib/rcu-slist.h new file mode 100644 index 0000000..eeab1b8 --- /dev/null +++ b/lib/rcu-slist.h @@ -0,0 +1,84 @@ +/* + * Copyright (c) 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 RCU_SLIST_H +#define RCU_SLIST_H 1 + +#include "ovs-rcu.h" + +/* RCU protected singly linked list + * ================================ + * + * This module implements a singly linked list with RCU protected pointers. + * + * Thread safety + * ------------- + * + * The structure use RCU, so readers can safely iterate through it without + * worrying about concurrent writers. + * rcu_slist_pop() and rcu_slist_push() use atomic compare and exchange + * operations, so multiple writers can call these functions concurrently + */ + +struct rcu_slist +{ + OVSRCU_TYPE(struct rcu_slist *) next; +}; + +/* Extract an element from the head of the list 'list' and returns it. The + * caller may free its memory, but only using rcu_postpone */ +static inline struct rcu_slist * +rcu_slist_pop(struct rcu_slist *list) +{ + struct rcu_slist *elem, *next_elem; + + elem = ovsrcu_get(struct rcu_slist *, &list->next); + + do { + if (!elem) { + break; + } + + next_elem = ovsrcu_get(struct rcu_slist *, &elem->next); + } while (!ovsrcu_compare_exchange(&list->next, &elem, next_elem)); + + return elem; +} + +/* Inserts 'elem' at the beginning of 'list', so that it becomes the front in + * 'list'. */ +static inline void +rcu_slist_push(struct rcu_slist *list, struct rcu_slist *elem) +{ + struct rcu_slist *next_elem; + + next_elem = ovsrcu_get(struct rcu_slist *, &list->next); + + do { + ovsrcu_set_hidden(&elem->next, next_elem); + } while (!ovsrcu_compare_exchange(&list->next, &next_elem, elem)); +} + +#define RCU_SLIST_FOR_EACH(ITER, MEMBER, LIST) \ + for (struct rcu_slist *cursor__ = ovsrcu_get(struct rcu_slist *, \ + &(LIST)->next); \ + INIT_CONTAINER(ITER, cursor__, MEMBER), cursor__; \ + cursor__ = ovsrcu_get(struct rcu_slist *, &cursor__->next)) + +#define RCU_SLIST_INITIALIZER(P) { OVSRCU_TYPE_INITIALIZER(P) } +#define RCU_SLIST_INIT_NULL RCU_SLIST_INITIALIZER(NULL) + +#endif /* rcu-slist.h */ -- 2.1.0.rc1 _______________________________________________ dev mailing list [email protected] http://openvswitch.org/mailman/listinfo/dev
