From 63ff4873e046ba582d20e79ebff16ee7da2aa92f Mon Sep 17 00:00:00 2001 From: Mathieu Desnoyers Date: Mon, 28 Sep 2009 19:04:01 -0400 Subject: [PATCH] Update list, rculist and hlist - rculist : license ok - list : fix list del Fix rcutorture api.h implementations to use non-GPL lists. Signed-off-by: Mathieu Desnoyers --- Makefile.inc | 2 +- tests/api_gcc.h | 3 + tests/api_ppc.h | 4 + tests/api_x86.h | 4 + tests/urcutorture.c | 1 + urcu/hlist.h | 73 ++++++++++++++++++ urcu/list.h | 11 ++- urcu/rculist.h | 179 ++++++++++---------------------------------- 8 files changed, 136 insertions(+), 141 deletions(-) create mode 100644 urcu/hlist.h diff --git a/Makefile.inc b/Makefile.inc index febded7..3fc3a6c 100644 --- a/Makefile.inc +++ b/Makefile.inc @@ -63,7 +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 \ + urcu/list.h urcu/rculist.h urcu/hlist.h \ /usr/include/urcu/ cp -f urcu.h urcu-static.h \ urcu-qsbr.h urcu-qsbr-static.h \ diff --git a/tests/api_gcc.h b/tests/api_gcc.h index c53b2c1..1c8b12b 100644 --- a/tests/api_gcc.h +++ b/tests/api_gcc.h @@ -640,6 +640,7 @@ static void smp_init(void) const typeof( ((type *)0)->member ) *__mptr = (ptr); \ (type *)( (char *)__mptr - offsetof(type,member) );}) +#if 0 /* * Simple doubly linked list implementation. * @@ -1164,6 +1165,8 @@ static inline void list_splice_tail_init(struct list_head *list, &pos->member != (head); \ pos = n, n = list_entry(n->member.prev, typeof(*n), member)) +#endif //0 + /* * Double linked lists with a single pointer list head. * Mostly useful for hash tables where the two pointer list head is diff --git a/tests/api_ppc.h b/tests/api_ppc.h index 8359d04..da12019 100644 --- a/tests/api_ppc.h +++ b/tests/api_ppc.h @@ -1011,6 +1011,8 @@ static void smp_init(void) const typeof( ((type *)0)->member ) *__mptr = (ptr); \ (type *)( (char *)__mptr - offsetof(type,member) );}) +#if 0 + /* * Simple doubly linked list implementation. * @@ -1535,6 +1537,8 @@ static inline void list_splice_tail_init(struct list_head *list, &pos->member != (head); \ pos = n, n = list_entry(n->member.prev, typeof(*n), member)) +#endif //0 + /* * Double linked lists with a single pointer list head. * Mostly useful for hash tables where the two pointer list head is diff --git a/tests/api_x86.h b/tests/api_x86.h index 9ca5500..77d86a1 100644 --- a/tests/api_x86.h +++ b/tests/api_x86.h @@ -700,6 +700,8 @@ static void smp_init(void) const typeof( ((type *)0)->member ) *__mptr = (ptr); \ (type *)( (char *)__mptr - offsetof(type,member) );}) +#if 0 + /* * Simple doubly linked list implementation. * @@ -1224,6 +1226,8 @@ static inline void list_splice_tail_init(struct list_head *list, &pos->member != (head); \ pos = n, n = list_entry(n->member.prev, typeof(*n), member)) +#endif //0 + /* * Double linked lists with a single pointer list head. * Mostly useful for hash tables where the two pointer list head is diff --git a/tests/urcutorture.c b/tests/urcutorture.c index 9af450d..87f51a1 100644 --- a/tests/urcutorture.c +++ b/tests/urcutorture.c @@ -7,4 +7,5 @@ #define _LGPL_SOURCE #include #include +#include #include "rcutorture.h" diff --git a/urcu/hlist.h b/urcu/hlist.h new file mode 100644 index 0000000..1bec11a --- /dev/null +++ b/urcu/hlist.h @@ -0,0 +1,73 @@ +#ifndef _KCOMPAT_HLIST_H +#define _KCOMPAT_HLIST_H + +/* + * Kernel sourcecode compatible lightweight single pointer list head useful + * for implementing hash tables + * + * Copyright (C) 2009 Novell Inc. + * + * Author: Jan Blunck + * + * This program is free software; you can redistribute it and/or modify it + * under the terms of the GNU Lesser General Public License version 2.1 as + * published by the Free Software Foundation. + */ + +struct hlist_head +{ + struct hlist_node *next; +}; + +struct hlist_node +{ + struct hlist_node *next; + struct hlist_node *prev; +}; + +/* Initialize a new list head. */ +static inline void INIT_HLIST_HEAD(struct hlist_head *ptr) +{ + ptr->next = NULL; +} + +/* Get typed element from list at a given position. */ +#define hlist_entry(ptr, type, member) \ + ((type *) ((char *) (ptr) - (unsigned long) (&((type *) 0)->member))) + +/* Add new element at the head of the list. */ +static inline void hlist_add_head (struct hlist_node *newp, + struct hlist_head *head) +{ + if (head->next) + head->next->prev = newp; + + newp->next = head->next; + newp->prev = (struct hlist_node *)head; + head->next = newp; +} + +/* Remove element from list. */ +static inline void hlist_del (struct hlist_node *elem) +{ + if (elem->next) + elem->next->prev = elem->prev; + + elem->prev->next = elem->next; +} + +#define hlist_for_each_entry(entry, pos, head, member) \ + for (pos = (head)->next, \ + entry = hlist_entry(pos, typeof(*entry), member); \ + pos != NULL; \ + pos = pos->next, \ + entry = hlist_entry(pos, typeof(*entry), member)) + +#define hlist_for_each_entry_safe(entry, pos, p, head, member) \ + for (pos = (head)->next, \ + entry = hlist_entry(pos, typeof(*entry), member); \ + (pos != NULL) && ({ p = pos->next; 1;}); \ + pos = p, \ + entry = hlist_entry(pos, typeof(*entry), member)) + +#endif /* _KCOMPAT_HLIST_H */ diff --git a/urcu/list.h b/urcu/list.h index 7ccb76a..82c2ea4 100644 --- a/urcu/list.h +++ b/urcu/list.h @@ -65,12 +65,19 @@ list_add_tail (list_t *newp, list_t *head) } +/* Remove element from list. */ +static inline void +__list_del (list_t *prev, list_t *next) +{ + next->prev = prev; + prev->next = next; +} + /* Remove element from list. */ static inline void list_del (list_t *elem) { - elem->next->prev = elem->prev; - elem->prev->next = elem->next; + __list_del (elem->prev, elem->next); } diff --git a/urcu/rculist.h b/urcu/rculist.h index 252afe3..96f0a30 100644 --- a/urcu/rculist.h +++ b/urcu/rculist.h @@ -1,155 +1,58 @@ -#ifndef _KCOMPAT_RCULIST_H -#define _KCOMPAT_RCULIST_H +/* Copyright (C) 2002 Free Software Foundation, Inc. + This file is part of the GNU C Library. + Contributed by Ulrich Drepper , 2002. -/* - * 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) 2009 Pierre-Marc Fournier + Conversion to RCU list. + + 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. */ -#define _LGPL_SOURCE +#ifndef _URCU_RCULIST_H +#define _URCU_RCULIST_H + +#include #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! +/* Add new element at the head of the list. */ -static __inline__ void __list_add_rcu(struct list_head * new, - struct list_head * prev, - struct list_head * next) +static inline void list_add_rcu(list_t *newp, list_t *head) { - new->next = next; - new->prev = prev; + newp->next = head->next; + newp->prev = head; smp_wmb(); - next->prev = new; - prev->next = new; + head->next->prev = newp; + 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) -{ - __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) +/* Remove element from list. */ +static inline void list_del_rcu(list_t *elem) { - __list_add_rcu(new, head->prev, head); + elem->next->prev = elem->prev; + elem->prev->next = elem->next; } -/** - * 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(). +/* Iterate through elements of the list. + * This 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)) -/** - * 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)) +#define list_for_each_entry_rcu(pos, head, member) \ + for (pos = list_entry(rcu_dereference((head)->next), typeof(*pos), member); \ + &pos->member != (head); \ + pos = list_entry(rcu_dereference(pos->member.next), typeof(*pos), member)) -#endif /* _KCOMPAT_RCULIST_H */ +#endif /* _URCU_RCULIST_H */ -- 2.34.1