X-Git-Url: https://git.liburcu.org/?p=urcu.git;a=blobdiff_plain;f=urcu%2Frculist.h;h=1fd2df388f57cefc0ea19fa02a0c8c0b627847e8;hp=252afe3f7cf29a081f518439bca7303431312d3c;hb=b0a841b4ff807dd29fe0cdbfe24900312f0e627b;hpb=7a50dcf71c2134c4755ceee9cdaa865a07be27ad diff --git a/urcu/rculist.h b/urcu/rculist.h index 252afe3..1fd2df3 100644 --- a/urcu/rculist.h +++ b/urcu/rculist.h @@ -1,155 +1,92 @@ -#ifndef _KCOMPAT_RCULIST_H -#define _KCOMPAT_RCULIST_H - /* - * RCU-protected list version - * - * 2002-10-18 19:01:25-07:00, dipankar@in.ibm.com - * [PATCH] RCU helper patchset 2/2 - * - * This adds a set of list macros that make handling of list protected - * by RCU simpler. The interfaces added are - - * - * list_add_rcu - * list_add_tail_rcu - * - Adds an element by taking care of memory barrier (wmb()). - * - * list_del_rcu - * - Deletes an element but doesn't re-initialize the pointers in - * the element for supporting RCU based traversal. - * - * list_for_each_rcu - * __list_for_each_rcu - * - Traversal of RCU protected list - takes care of memory barriers - * transparently. - * + * Copyright (C) 2002 Free Software Foundation, Inc. + * (originally part of the GNU C Library) + * Contributed by Ulrich Drepper , 2002. + * + * Copyright (C) 2009 Pierre-Marc Fournier + * Conversion to RCU list. + * Copyright (C) 2010 Mathieu Desnoyers + * + * This library is free software; you can redistribute it and/or + * modify it under the terms of the GNU Lesser General Public + * License as published by the Free Software Foundation; either + * version 2.1 of the License, or (at your option) any later version. + * + * This library is distributed in the hope that it will be useful, + * but WITHOUT ANY WARRANTY; without even the implied warranty of + * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU + * Lesser General Public License for more details. + * + * You should have received a copy of the GNU Lesser General Public + * License along with this library; if not, write to the Free Software + * Foundation, Inc., 51 Franklin Street, Fifth Floor, Boston, MA 02110-1301 USA */ -#define _LGPL_SOURCE -#include -#include +#ifndef _URCU_RCULIST_H +#define _URCU_RCULIST_H -/* - * Insert a new entry between two known consecutive entries. - * - * This is only for internal list manipulation where we know - * the prev/next entries already! - */ -static __inline__ void __list_add_rcu(struct list_head * new, - struct list_head * prev, - struct list_head * next) +#include +#include +#include + +/* Add new element at the head of the list. */ +static inline +void cds_list_add_rcu(struct cds_list_head *newp, struct cds_list_head *head) { - new->next = next; - new->prev = prev; - smp_wmb(); - next->prev = new; - prev->next = new; + newp->next = head->next; + newp->prev = head; + head->next->prev = newp; + rcu_assign_pointer(head->next, newp); } -/** - * list_add_rcu - add a new entry to rcu-protected list - * @new: new entry to be added - * @head: list head to add it after - * - * Insert a new entry after the specified head. - * This is good for implementing stacks. - * - * The caller must take whatever precautions are necessary - * (such as holding appropriate locks) to avoid racing - * with another list-mutation primitive, such as list_add_rcu() - * or list_del_rcu(), running on this same list. - * However, it is perfectly legal to run concurrently with - * the _rcu list-traversal primitives, such as - * list_for_each_entry_rcu(). - */ -static __inline__ void list_add_rcu(struct list_head *new, - struct list_head *head) +/* Add new element at the tail of the list. */ +static inline +void cds_list_add_tail_rcu(struct cds_list_head *newp, + struct cds_list_head *head) { - __list_add_rcu(new, head, head->next); + newp->next = head; + newp->prev = head->prev; + rcu_assign_pointer(head->prev->next, newp); + head->prev = newp; } -/** - * list_add_tail_rcu - add a new entry to rcu-protected list - * @new: new entry to be added - * @head: list head to add it before - * - * Insert a new entry before the specified head. - * This is useful for implementing queues. - * - * The caller must take whatever precautions are necessary - * (such as holding appropriate locks) to avoid racing - * with another list-mutation primitive, such as list_add_tail_rcu() - * or list_del_rcu(), running on this same list. - * However, it is perfectly legal to run concurrently with - * the _rcu list-traversal primitives, such as - * list_for_each_entry_rcu(). +/* + * Replace an old entry atomically with respect to concurrent RCU + * traversal. Mutual exclusion against concurrent updates is required + * though. */ -static __inline__ void list_add_tail_rcu(struct list_head *new, - struct list_head *head) +static inline +void cds_list_replace_rcu(struct cds_list_head *old, struct cds_list_head *_new) { - __list_add_rcu(new, head->prev, head); + _new->next = old->next; + _new->prev = old->prev; + rcu_assign_pointer(_new->prev->next, _new); + _new->next->prev = _new; } -/** - * list_del_rcu - deletes entry from list without re-initialization - * @entry: the element to delete from the list. - * - * Note: list_empty on entry does not return true after this, - * the entry is in an undefined state. It is useful for RCU based - * lockfree traversal. - * - * The caller must take whatever precautions are necessary - * (such as holding appropriate locks) to avoid racing - * with another list-mutation primitive, such as list_del_rcu() - * or list_add_rcu(), running on this same list. - * However, it is perfectly legal to run concurrently with - * the _rcu list-traversal primitives, such as - * list_for_each_entry_rcu(). - * - * Note that the caller is not permitted to immediately free - * the newly deleted entry. Instead, either synchronize_kernel() - * or call_rcu() must be used to defer freeing until an RCU - * grace period has elapsed. - */ -static inline void list_del_rcu(struct list_head *entry) +/* Remove element from list. */ +static inline +void cds_list_del_rcu(struct cds_list_head *elem) { - __list_del(entry->prev, entry->next); + elem->next->prev = elem->prev; + CMM_STORE_SHARED(elem->prev->next, elem->next); } -/** - * list_for_each_rcu - iterate over an rcu-protected list - * @pos: the &struct list_head to use as a loop counter. - * @head: the head for your list. - * - * This list-traversal primitive may safely run concurrently with - * the _rcu list-mutation primitives such as list_add_rcu() - * as long as the traversal is guarded by rcu_read_lock(). +/* + * Iteration through all elements of the list must be done while rcu_read_lock() + * is held. */ -#define list_for_each_rcu(pos, head) \ - for (pos = rcu_dereference((head)->next); \ - prefetch(pos->next), pos != (head); \ - pos = rcu_dereference(pos->next)) -#define __list_for_each_rcu(pos, head) \ - for (pos = rcu_dereference((head)->next); \ - pos != (head); \ - pos = rcu_dereference(pos->next)) +/* Iterate forward over the elements of the list. */ +#define cds_list_for_each_rcu(pos, head) \ + for (pos = rcu_dereference((head)->next); pos != (head); \ + pos = rcu_dereference(pos->next)) -/** - * list_for_each_entry_rcu - iterate over a rcu-protected list - * @pos: the struct type pointer to use as a loop counter - * @head: the head for your list - * @member: the name of the struct list_head element in your struct type - * - * This list-traversal primitive may safely run concurrently with - * the _rcu list-mutation primitives such as list_add_rcu() - * as long as the traversal is guarded by rcu_read_lock(). - */ -#define list_for_each_entry_rcu(pos, head, member) \ - for (pos = list_entry(rcu_dereference((head)->next), typeof(*pos), \ - member); \ - prefetch(pos->member.next), &pos->member != (head); \ - pos = list_entry(rcu_dereference(pos->member.next),typeof(*pos), \ - member)) -#endif /* _KCOMPAT_RCULIST_H */ +/* Iterate through elements of the list. */ +#define cds_list_for_each_entry_rcu(pos, head, member) \ + for (pos = cds_list_entry(rcu_dereference((head)->next), __typeof__(*pos), member); \ + &pos->member != (head); \ + pos = cds_list_entry(rcu_dereference(pos->member.next), __typeof__(*pos), member)) + +#endif /* _URCU_RCULIST_H */