Prev: module: __rcu annotations
Next: RapidIO: Add IDT CPS/TSI switches
From: Mathieu Desnoyers on 24 Feb 2010 15:20
* Arnd Bergmann (arnd(a)arndb.de) wrote:
> The listrcu implementation now defines new rcu_list_head,
> rcu_hlist_head and rcu_hlist_entry structures that are
> annotated with __rcu. Only these can now be passed into
> rcu_list_for_each and related interfaces.
>
> When not running sparse, the types are defined to the
> original list_head etc in order to not break working
> setups that are lacking annotation.

Hrm, wait.. dumb question: how can an annotation break compilation ? If there is
any way out of this, I would prefer if we can do without a #ifdef __CHECKER__ if
possible. It calls for bugs and implementation mismatch.

Thanks,

Mathieu

>
> Signed-off-by: Arnd Bergmann <arnd(a)arndb.de>
> ---
> include/linux/rculist.h | 152 ++++++++++++++++++++++++++++++++++------------
> 1 files changed, 112 insertions(+), 40 deletions(-)
>
> diff --git a/include/linux/rculist.h b/include/linux/rculist.h
> index 1bf0f70..dfbc6ea 100644
> --- a/include/linux/rculist.h
> +++ b/include/linux/rculist.h
> @@ -9,16 +9,67 @@
> #include <linux/list.h>
> #include <linux/rcupdate.h>
>
> +#ifdef __CHECKER__
> +struct rcu_list_head {
> + struct rcu_list_head __rcu *next;
> + struct rcu_list_head *prev;
> +};
> +#define LIST_HEAD_INIT_RCU(name) { (struct rcu_list_head __force __rcu *)&(name), &(name) }
> +
> +#define LIST_HEAD_RCU(name) \
> + struct rcu_list_head name = LIST_HEAD_INIT_RCU(name)
> +
> +static inline void INIT_LIST_HEAD_RCU(struct rcu_list_head *list)
> +{
> + __rcu_assign_pointer(list->next, list);
> + list->prev = list;
> +}
> +
> +struct rcu_hlist_head {
> + struct rcu_hlist_node __rcu *first;
> +};
> +
> +struct rcu_hlist_node {
> + struct rcu_hlist_node __rcu *next, **pprev;
> +};
> +
> +#define HLIST_HEAD_INIT_RCU { .first = (void __rcu __force *)NULL }
> +#define HLIST_HEAD_RCU(name) struct rcu_hlist_head name = \
> + { .first = (void __rcu __force *)NULL }
> +#define INIT_HLIST_HEAD_RCU(ptr) ((ptr)->first = (void __rcu __force *)NULL)
> +static inline void INIT_HLIST_NODE_RCU(struct rcu_hlist_node *h)
> +{
> + __rcu_assign_pointer(h->next, NULL);
> + h->pprev = NULL;
> +}
> +
> +#else /* !__CHECKER__ */
> +
> +#define rcu_list_head list_head
> +#define LIST_HEAD_INIT_RCU LIST_HEAD_INIT
> +#define LIST_HEAD_RCU LIST_HEAD
> +#define INIT_LIST_HEAD_RCU INIT_LIST_HEAD
> +
> +#define rcu_hlist_head hlist_head
> +#define rcu_hlist_node hlist_node
> +#define HLIST_HEAD_INIT_RCU HLIST_HEAD_INIT
> +#define HLIST_HEAD_RCU HLIST_HEAD
> +#define INIT_HLIST_HEAD_RCU INIT_HLIST_HEAD
> +#define INIT_HLIST_NODE_RCU INIT_HLIST_NODE
> +
> +#endif /* !__CHECKER__ */
> +
> +
> /*
> * 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)
> +static inline void __list_add_rcu(struct rcu_list_head *new,
> + struct rcu_list_head *prev, struct rcu_list_head *next)
> {
> - new->next = next;
> + __rcu_assign_pointer(new->next, next);
> new->prev = prev;
> rcu_assign_pointer(prev->next, new);
> next->prev = new;
> @@ -40,9 +91,9 @@ static inline void __list_add_rcu(struct list_head *new,
> * 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)
> +static inline void list_add_rcu(struct rcu_list_head *new, struct rcu_list_head *head)
> {
> - __list_add_rcu(new, head, head->next);
> + __list_add_rcu(new, head, __rcu_dereference(head->next));
> }
>
> /**
> @@ -61,8 +112,8 @@ static inline void list_add_rcu(struct list_head *new, struct list_head *head)
> * 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)
> +static inline void list_add_tail_rcu(struct rcu_list_head *new,
> + struct rcu_list_head *head)
> {
> __list_add_rcu(new, head->prev, head);
> }
> @@ -91,13 +142,29 @@ static inline void list_add_tail_rcu(struct list_head *new,
> * 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)
> +static inline void __list_del_rcu(struct rcu_list_head *prev, struct rcu_list_head *next)
> {
> - __list_del(entry->prev, entry->next);
> + next->prev = prev;
> + __rcu_assign_pointer(prev->next, next);
> +}
> +
> +static inline void list_del_rcu(struct rcu_list_head *entry)
> +{
> + __list_del_rcu(entry->prev, __rcu_dereference(entry->next));
> entry->prev = LIST_POISON2;
> }
>
> /**
> + * list_empty - tests whether a list is empty
> + * @head: the list to test.
> + */
> +static inline int list_empty_rcu(const struct rcu_list_head *head)
> +{
> + return rcu_dereference(head->next) == head;
> +}
> +
> +
> +/**
> * hlist_del_init_rcu - deletes entry from hash list with re-initialization
> * @n: the element to delete from the hash list.
> *
> @@ -117,7 +184,7 @@ static inline void list_del_rcu(struct list_head *entry)
> * perfectly legal to run concurrently with the _rcu list-traversal
> * primitives, such as hlist_for_each_entry_rcu().
> */
> -static inline void hlist_del_init_rcu(struct hlist_node *n)
> +static inline void hlist_del_init_rcu(struct rcu_hlist_node *n)
> {
> if (!hlist_unhashed(n)) {
> __hlist_del(n);
> @@ -133,13 +200,13 @@ static inline void hlist_del_init_rcu(struct hlist_node *n)
> * The @old entry will be replaced with the @new entry atomically.
> * Note: @old should not be empty.
> */
> -static inline void list_replace_rcu(struct list_head *old,
> - struct list_head *new)
> +static inline void list_replace_rcu(struct rcu_list_head *old,
> + struct rcu_list_head *new)
> {
> new->next = old->next;
> new->prev = old->prev;
> - rcu_assign_pointer(new->prev->next, new);
> - new->next->prev = new;
> + __rcu_assign_pointer(new->prev->next, new);
> + rcu_dereference(new->next)->prev = new;
> old->prev = LIST_POISON2;
> }
>
> @@ -160,13 +227,13 @@ static inline void list_replace_rcu(struct list_head *old,
> * based on call_rcu() could be created. But only if -really-
> * needed -- there is no shortage of RCU API members.
> */
> -static inline void list_splice_init_rcu(struct list_head *list,
> - struct list_head *head,
> +static inline void list_splice_init_rcu(struct rcu_list_head *list,
> + struct rcu_list_head *head,
> void (*sync)(void))
> {
> - struct list_head *first = list->next;
> - struct list_head *last = list->prev;
> - struct list_head *at = head->next;
> + struct rcu_list_head *first = __rcu_dereference(list->next);
> + struct rcu_list_head *last = list->prev;
> + struct rcu_list_head *at = __rcu_dereference(head->next);
>
> if (list_empty(head))
> return;
> @@ -192,7 +259,7 @@ static inline void list_splice_init_rcu(struct list_head *list,
> * this function.
> */
>
> - last->next = at;
> + __rcu_assign_pointer(last->next,at);
> rcu_assign_pointer(head->next, first);
> first->prev = head;
> at->prev = last;
> @@ -200,7 +267,7 @@ static inline void list_splice_init_rcu(struct list_head *list,
>
> /**
> * list_entry_rcu - get the struct for this entry
> - * @ptr: the &struct list_head pointer.
> + * @ptr: the &struct rcu_list_head pointer.
> * @type: the type of the struct this is embedded in.
> * @member: the name of the list_struct within the struct.
> *
> @@ -241,13 +308,13 @@ static inline void list_splice_init_rcu(struct list_head *list,
> */
> #define list_for_each_entry_rcu(pos, head, member) \
> for (pos = list_entry_rcu((head)->next, typeof(*pos), member); \
> - prefetch(pos->member.next), &pos->member != (head); \
> + prefetch(__rcu_dereference(pos->member.next)), &pos->member != (head); \
> pos = list_entry_rcu(pos->member.next, typeof(*pos), member))
>
>
> /**
> * list_for_each_continue_rcu
> - * @pos: the &struct list_head to use as a loop cursor.
> + * @pos: the &struct rcu_list_head to use as a loop cursor.
> * @head: the head for your list.
> *
> * Iterate over an rcu-protected list, continuing after current point.
> @@ -294,9 +361,9 @@ static inline void list_splice_init_rcu(struct list_head *list,
> * the _rcu list-traversal primitives, such as
> * hlist_for_each_entry().
> */
> -static inline void hlist_del_rcu(struct hlist_node *n)
> +static inline void hlist_del_rcu(struct rcu_hlist_node *n)
> {
> - __hlist_del(n);
> + __hlist_del((struct hlist_node *)n);
> n->pprev = LIST_POISON2;
> }
>
> @@ -307,16 +374,16 @@ static inline void hlist_del_rcu(struct hlist_node *n)
> *
> * The @old entry will be replaced with the @new entry atomically.
> */
> -static inline void hlist_replace_rcu(struct hlist_node *old,
> - struct hlist_node *new)
> +static inline void hlist_replace_rcu(struct rcu_hlist_node *old,
> + struct rcu_hlist_node *new)
> {
> - struct hlist_node *next = old->next;
> + struct rcu_hlist_node __rcu *next = old->next;
>
> new->next = next;
> new->pprev = old->pprev;
> rcu_assign_pointer(*new->pprev, new);
> if (next)
> - new->next->pprev = &new->next;
> + __rcu_dereference(new->next)->pprev = &new->next;
> old->pprev = LIST_POISON2;
> }
>
> @@ -339,12 +406,12 @@ static inline void hlist_replace_rcu(struct hlist_node *old,
> * problems on Alpha CPUs. Regardless of the type of CPU, the
> * list-traversal primitive must be guarded by rcu_read_lock().
> */
> -static inline void hlist_add_head_rcu(struct hlist_node *n,
> - struct hlist_head *h)
> +static inline void hlist_add_head_rcu(struct rcu_hlist_node *n,
> + struct rcu_hlist_head *h)
> {
> - struct hlist_node *first = h->first;
> + struct rcu_hlist_node *first = __rcu_dereference(h->first);
>
> - n->next = first;
> + __rcu_assign_pointer(n->next, first);
> n->pprev = &h->first;
> rcu_assign_pointer(h->first, n);
> if (first)
> @@ -369,8 +436,8 @@ static inline void hlist_add_head_rcu(struct hlist_node *n,
> * hlist_for_each_entry_rcu(), used to prevent memory-consistency
> * problems on Alpha CPUs.
> */
> -static inline void hlist_add_before_rcu(struct hlist_node *n,
> - struct hlist_node *next)
> +static inline void hlist_add_before_rcu(struct rcu_hlist_node *n,
> + struct rcu_hlist_node *next)
> {
> n->pprev = next->pprev;
> n->next = next;
> @@ -396,8 +463,8 @@ static inline void hlist_add_before_rcu(struct hlist_node *n,
> * hlist_for_each_entry_rcu(), used to prevent memory-consistency
> * problems on Alpha CPUs.
> */
> -static inline void hlist_add_after_rcu(struct hlist_node *prev,
> - struct hlist_node *n)
> +static inline void hlist_add_after_rcu(struct rcu_hlist_node *prev,
> + struct rcu_hlist_node *n)
> {
> n->next = prev->next;
> n->pprev = &prev->next;
> @@ -406,12 +473,17 @@ static inline void hlist_add_after_rcu(struct hlist_node *prev,
> n->next->pprev = &n->next;
> }
>
> +static inline int hlist_empty_rcu(const struct rcu_hlist_head *h)
> +{
> + return !__rcu_dereference(h->first);
> +}
> +
> /**
> * hlist_for_each_entry_rcu - iterate over rcu list of given type
> * @tpos: the type * to use as a loop cursor.
> - * @pos: the &struct hlist_node to use as a loop cursor.
> + * @pos: the &struct rcu_hlist_node to use as a loop cursor.
> * @head: the head for your list.
> - * @member: the name of the hlist_node within the struct.
> + * @member: the name of the rcu_hlist_node within the struct.
> *
> * This list-traversal primitive may safely run concurrently with
> * the _rcu list-mutation primitives such as hlist_add_head_rcu()
> @@ -419,7 +491,7 @@ static inline void hlist_add_after_rcu(struct hlist_node *prev,
> */
> #define hlist_for_each_entry_rcu(tpos, pos, head, member) \
> for (pos = rcu_dereference((head)->first); \
> - pos && ({ prefetch(pos->next); 1; }) && \
> + pos && ({ prefetch(__rcu_dereference(pos->next)); 1; }) && \
> ({ tpos = hlist_entry(pos, typeof(*tpos), member); 1; }); \
> pos = rcu_dereference(pos->next))
>
> --
> 1.6.3.3
>

--
Mathieu Desnoyers
Operating System Efficiency Consultant
EfficiOS Inc.
http://www.efficios.com
--
To unsubscribe from this list: send the line "unsubscribe linux-kernel" in
the body of a message to majordomo(a)vger.kernel.org
More majordomo info at http://vger.kernel.org/majordomo-info.html
Please read the FAQ at http://www.tux.org/lkml/
From: Arnd Bergmann on 24 Feb 2010 15:40
On Wednesday 24 February 2010, Mathieu Desnoyers wrote:
> * Arnd Bergmann (arnd(a)arndb.de) wrote:
> > The listrcu implementation now defines new rcu_list_head,
> > rcu_hlist_head and rcu_hlist_entry structures that are
> > annotated with __rcu. Only these can now be passed into
> > rcu_list_for_each and related interfaces.
> >
> > When not running sparse, the types are defined to the
> > original list_head etc in order to not break working
> > setups that are lacking annotation.
>
> Hrm, wait.. dumb question: how can an annotation break compilation ? If there is
> any way out of this, I would prefer if we can do without a #ifdef __CHECKER__ if
> possible. It calls for bugs and implementation mismatch.

The problem is that you can not (currently) declare a list_head
to be RCU protected by writing 'struct list_head __rcu list;',
because address space annotations only work on pointers.

The solution I used was to define a new struct rcu_list_head that
has the ->next member annotated as __rcu. Unfortunately, this
means that it is now incompatible to a struct list_head from
the compiler's point of view.

We could get rid of the #ifdef by unconditionally defining
the separate rcu_list_head, as long as all users are correctly
converted to it. This does have problems in cases such as the
module code that uses the same list with and without RCU, as
Alexey mentioned.

The alternative would be not to annotate list RCU at all and
__force away the warnings for these so we can still keep the
normal __rcu annotations.

Arnd

--
To unsubscribe from this list: send the line "unsubscribe linux-kernel" in
the body of a message to majordomo(a)vger.kernel.org
More majordomo info at http://vger.kernel.org/majordomo-info.html
Please read the FAQ at http://www.tux.org/lkml/
 | 
Pages: 1
Prev: module: __rcu annotations
Next: RapidIO: Add IDT CPS/TSI switches