From 7a50dcf71c2134c4755ceee9cdaa865a07be27ad Mon Sep 17 00:00:00 2001 From: Mathieu Desnoyers Date: Mon, 28 Sep 2009 18:43:56 -0400 Subject: [PATCH] Add urcu list and list Signed-off-by: Mathieu Desnoyers --- Makefile.inc | 1 + urcu/list.h | 145 +++++++++++++++++++++++++++++++++++++++++++++ urcu/rculist.h | 155 +++++++++++++++++++++++++++++++++++++++++++++++++ 3 files changed, 301 insertions(+) create mode 100644 urcu/list.h create mode 100644 urcu/rculist.h diff --git a/Makefile.inc b/Makefile.inc index cde31cc..febded7 100644 --- a/Makefile.inc +++ b/Makefile.inc @@ -63,6 +63,7 @@ install: liburcu.so /usr/lib/ mkdir -p /usr/include/urcu cp -f urcu/arch.h urcu/arch_uatomic.h urcu/compiler.h \ + urcu/list.h urcu/rculist.h \ /usr/include/urcu/ cp -f urcu.h urcu-static.h \ urcu-qsbr.h urcu-qsbr-static.h \ diff --git a/urcu/list.h b/urcu/list.h new file mode 100644 index 0000000..7ccb76a --- /dev/null +++ b/urcu/list.h @@ -0,0 +1,145 @@ +/* Copyright (C) 2002 Free Software Foundation, Inc. + This file is part of the GNU C Library. + Contributed by Ulrich Drepper , 2002. + + The GNU C 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. + + The GNU C 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 the GNU C Library; if not, write to the Free + Software Foundation, Inc., 59 Temple Place, Suite 330, Boston, MA + 02111-1307 USA. */ + +#ifndef _LIST_H +#define _LIST_H 1 + +/* The definitions of this file are adopted from those which can be + found in the Linux kernel headers to enable people familiar with + the latter find their way in these sources as well. */ + + +/* Basic type for the double-link list. */ +typedef struct list_head +{ + struct list_head *next; + struct list_head *prev; +} list_t; + + +/* Define a variable with the head and tail of the list. */ +#define LIST_HEAD(name) \ + list_t name = { &(name), &(name) } + +/* Initialize a new list head. */ +#define INIT_LIST_HEAD(ptr) \ + (ptr)->next = (ptr)->prev = (ptr) + +#define LIST_HEAD_INIT(name) { .prev = &(name), .next = &(name) } + +/* Add new element at the head of the list. */ +static inline void +list_add (list_t *newp, list_t *head) +{ + head->next->prev = newp; + newp->next = head->next; + newp->prev = head; + head->next = newp; +} + + +/* Add new element at the tail of the list. */ +static inline void +list_add_tail (list_t *newp, list_t *head) +{ + head->prev->next = newp; + newp->next = head; + newp->prev = head->prev; + head->prev = newp; +} + + +/* Remove element from list. */ +static inline void +list_del (list_t *elem) +{ + elem->next->prev = elem->prev; + elem->prev->next = elem->next; +} + + +/* Join two lists. */ +static inline void +list_splice (list_t *add, list_t *head) +{ + /* Do nothing if the list which gets added is empty. */ + if (add != add->next) + { + add->next->prev = head; + add->prev->next = head->next; + head->next->prev = add->prev; + head->next = add->next; + } +} + + +/* Get typed element from list at a given position. */ +#define list_entry(ptr, type, member) \ + ((type *) ((char *) (ptr) - (unsigned long) (&((type *) 0)->member))) + + + +/* Iterate forward over the elements of the list. */ +#define list_for_each(pos, head) \ + for (pos = (head)->next; pos != (head); pos = pos->next) + + +/* Iterate forward over the elements of the list. */ +#define list_for_each_prev(pos, head) \ + for (pos = (head)->prev; pos != (head); pos = pos->prev) + + +/* Iterate backwards over the elements list. The list elements can be + removed from the list while doing this. */ +#define list_for_each_prev_safe(pos, p, head) \ + for (pos = (head)->prev, p = pos->prev; \ + pos != (head); \ + pos = p, p = pos->prev) + +#define list_for_each_entry(pos, head, member) \ + for (pos = list_entry((head)->next, typeof(*pos), member); \ + &pos->member != (head); \ + pos = list_entry(pos->member.next, typeof(*pos), member)) + +#define list_for_each_entry_reverse(pos, head, member) \ + for (pos = list_entry((head)->prev, typeof(*pos), member); \ + &pos->member != (head); \ + pos = list_entry(pos->member.prev, typeof(*pos), member)) + +#define list_for_each_entry_safe(pos, p, head, member) \ + for (pos = list_entry((head)->next, typeof(*pos), member), \ + p = list_entry(pos->member.next,typeof(*pos), member); \ + &pos->member != (head); \ + pos = p, p = list_entry(pos->member.next, typeof(*pos), member)) + +static inline int list_empty(list_t *head) +{ + return head == head->next; +} + +static inline void list_replace_init(list_t *old, + list_t *new) +{ + list_t *head = old->next; + list_del(old); + list_add_tail(new, head); + INIT_LIST_HEAD(old); +} + +#endif /* list.h */ diff --git a/urcu/rculist.h b/urcu/rculist.h new file mode 100644 index 0000000..252afe3 --- /dev/null +++ b/urcu/rculist.h @@ -0,0 +1,155 @@ +#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. + * + */ + +#define _LGPL_SOURCE +#include +#include + +/* + * 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) +{ + new->next = next; + new->prev = prev; + smp_wmb(); + next->prev = new; + prev->next = new; +} + +/** + * 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) +{ + __list_add_rcu(new, head, head->next); +} + +/** + * 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(). + */ +static __inline__ void list_add_tail_rcu(struct list_head *new, + struct list_head *head) +{ + __list_add_rcu(new, head->prev, head); +} + +/** + * 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) +{ + __list_del(entry->prev, entry->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(). + */ +#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)) + +/** + * 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 */ -- 2.34.1