diff options
author | Kent Overstreet <kent.overstreet@gmail.com> | 2018-05-17 03:14:09 -0400 |
---|---|---|
committer | Kent Overstreet <kent.overstreet@gmail.com> | 2018-05-17 07:24:39 -0400 |
commit | 62e4df2a38081f62fd1bd657459b7ffb2d4f522c (patch) | |
tree | 9b4ed5d3c597e19894ca77299b53057efe071c50 /include/linux/rculist.h | |
parent | 426e88e41cdcecd007a689daf4fe432bb61303ec (diff) |
drop dead code
Diffstat (limited to 'include/linux/rculist.h')
-rw-r--r-- | include/linux/rculist.h | 668 |
1 files changed, 6 insertions, 662 deletions
diff --git a/include/linux/rculist.h b/include/linux/rculist.h index b6c61e12..81df4e13 100644 --- a/include/linux/rculist.h +++ b/include/linux/rculist.h @@ -1,672 +1,16 @@ #ifndef _LINUX_RCULIST_H #define _LINUX_RCULIST_H -/* - * RCU-protected list version - */ -#include <linux/list.h> -#include <linux/rcupdate.h> +#include <urcu/rculist.h> -/* - * Why is there no list_empty_rcu()? Because list_empty() serves this - * purpose. The list_empty() function fetches the RCU-protected pointer - * and compares it to the address of the list head, but neither dereferences - * this pointer itself nor provides this pointer to the caller. Therefore, - * it is not necessary to use rcu_dereference(), so that list_empty() can - * be used anywhere you would want to use a list_empty_rcu(). - */ -/* - * INIT_LIST_HEAD_RCU - Initialize a list_head visible to RCU readers - * @list: list to be initialized - * - * You should instead use INIT_LIST_HEAD() for normal initialization and - * cleanup tasks, when readers have no access to the list being initialized. - * However, if the list being initialized is visible to readers, you - * need to keep the compiler from being too mischievous. - */ -static inline void INIT_LIST_HEAD_RCU(struct list_head *list) -{ - WRITE_ONCE(list->next, list); - WRITE_ONCE(list->prev, list); -} +#include <urcu/rcuhlist.h> -/* - * return the ->next pointer of a list_head in an rcu safe - * way, we must not access it directly - */ -#define list_next_rcu(list) (*((struct list_head __rcu **)(&(list)->next))) +#define hlist_add_head_rcu cds_hlist_add_head_rcu +#define hlist_del_rcu cds_hlist_del_rcu -/* - * Insert a new entry between two known consecutive entries. - * - * This is only for internal list manipulation where we know - * the prev/next entries already! - */ -#ifndef CONFIG_DEBUG_LIST -static inline void __list_add_rcu(struct list_head *new, - struct list_head *prev, struct list_head *next) -{ - new->next = next; - new->prev = prev; - rcu_assign_pointer(list_next_rcu(prev), new); - next->prev = new; -} -#else -void __list_add_rcu(struct list_head *new, - struct list_head *prev, struct list_head *next); -#endif - -/** - * 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. - * - * In particular, it means that we can not poison the forward - * pointers that may still be used for walking the list. - * - * 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_rcu() - * 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(entry); - entry->prev = LIST_POISON2; -} - -/** - * hlist_del_init_rcu - deletes entry from hash list with re-initialization - * @n: the element to delete from the hash list. - * - * Note: list_unhashed() on the node return true after this. It is - * useful for RCU based read lockfree traversal if the writer side - * must know if the list entry is still hashed or already unhashed. - * - * In particular, it means that we can not poison the forward pointers - * that may still be used for walking the hash list and we can only - * zero the pprev pointer so list_unhashed() will return true after - * this. - * - * The caller must take whatever precautions are necessary (such as - * holding appropriate locks) to avoid racing with another - * list-mutation primitive, such as hlist_add_head_rcu() or - * hlist_del_rcu(), running on this same list. However, it is - * 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) -{ - if (!hlist_unhashed(n)) { - __hlist_del(n); - n->pprev = NULL; - } -} - -/** - * list_replace_rcu - replace old entry by new one - * @old : the element to be replaced - * @new : the new element to insert - * - * 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) -{ - new->next = old->next; - new->prev = old->prev; - rcu_assign_pointer(list_next_rcu(new->prev), new); - new->next->prev = new; - old->prev = LIST_POISON2; -} - -/** - * __list_splice_init_rcu - join an RCU-protected list into an existing list. - * @list: the RCU-protected list to splice - * @prev: points to the last element of the existing list - * @next: points to the first element of the existing list - * @sync: function to sync: synchronize_rcu(), synchronize_sched(), ... - * - * The list pointed to by @prev and @next can be RCU-read traversed - * concurrently with this function. - * - * Note that this function blocks. - * - * Important note: the caller must take whatever action is necessary to prevent - * any other updates to the existing list. In principle, it is possible to - * modify the list as soon as sync() begins execution. If this sort of thing - * becomes necessary, an alternative version 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 *prev, - struct list_head *next, - void (*sync)(void)) -{ - struct list_head *first = list->next; - struct list_head *last = list->prev; - - /* - * "first" and "last" tracking list, so initialize it. RCU readers - * have access to this list, so we must use INIT_LIST_HEAD_RCU() - * instead of INIT_LIST_HEAD(). - */ - - INIT_LIST_HEAD_RCU(list); - - /* - * At this point, the list body still points to the source list. - * Wait for any readers to finish using the list before splicing - * the list body into the new list. Any new readers will see - * an empty list. - */ - - sync(); - - /* - * Readers are finished with the source list, so perform splice. - * The order is important if the new list is global and accessible - * to concurrent RCU readers. Note that RCU readers are not - * permitted to traverse the prev pointers without excluding - * this function. - */ - - last->next = next; - rcu_assign_pointer(list_next_rcu(prev), first); - first->prev = prev; - next->prev = last; -} - -/** - * list_splice_init_rcu - splice an RCU-protected list into an existing list, - * designed for stacks. - * @list: the RCU-protected list to splice - * @head: the place in the existing list to splice the first list into - * @sync: function to sync: synchronize_rcu(), synchronize_sched(), ... - */ -static inline void list_splice_init_rcu(struct list_head *list, - struct list_head *head, - void (*sync)(void)) -{ - if (!list_empty(list)) - __list_splice_init_rcu(list, head, head->next, sync); -} - -/** - * list_splice_tail_init_rcu - splice an RCU-protected list into an existing - * list, designed for queues. - * @list: the RCU-protected list to splice - * @head: the place in the existing list to splice the first list into - * @sync: function to sync: synchronize_rcu(), synchronize_sched(), ... - */ -static inline void list_splice_tail_init_rcu(struct list_head *list, - struct list_head *head, - void (*sync)(void)) -{ - if (!list_empty(list)) - __list_splice_init_rcu(list, head->prev, head, sync); -} - -/** - * list_entry_rcu - get the struct for this entry - * @ptr: the &struct list_head pointer. - * @type: the type of the struct this is embedded in. - * @member: the name of the list_head within the struct. - * - * This primitive may safely run concurrently with the _rcu list-mutation - * primitives such as list_add_rcu() as long as it's guarded by rcu_read_lock(). - */ -#define list_entry_rcu(ptr, type, member) \ - container_of(lockless_dereference(ptr), type, member) - -/** - * Where are list_empty_rcu() and list_first_entry_rcu()? - * - * Implementing those functions following their counterparts list_empty() and - * list_first_entry() is not advisable because they lead to subtle race - * conditions as the following snippet shows: - * - * if (!list_empty_rcu(mylist)) { - * struct foo *bar = list_first_entry_rcu(mylist, struct foo, list_member); - * do_something(bar); - * } - * - * The list may not be empty when list_empty_rcu checks it, but it may be when - * list_first_entry_rcu rereads the ->next pointer. - * - * Rereading the ->next pointer is not a problem for list_empty() and - * list_first_entry() because they would be protected by a lock that blocks - * writers. - * - * See list_first_or_null_rcu for an alternative. - */ - -/** - * list_first_or_null_rcu - get the first element from a list - * @ptr: the list head to take the element from. - * @type: the type of the struct this is embedded in. - * @member: the name of the list_head within the struct. - * - * Note that if the list is empty, it returns NULL. - * - * This primitive may safely run concurrently with the _rcu list-mutation - * primitives such as list_add_rcu() as long as it's guarded by rcu_read_lock(). - */ -#define list_first_or_null_rcu(ptr, type, member) \ -({ \ - struct list_head *__ptr = (ptr); \ - struct list_head *__next = READ_ONCE(__ptr->next); \ - likely(__ptr != __next) ? list_entry_rcu(__next, type, member) : NULL; \ -}) - -/** - * list_next_or_null_rcu - get the first element from a list - * @head: the head for the list. - * @ptr: the list head to take the next element from. - * @type: the type of the struct this is embedded in. - * @member: the name of the list_head within the struct. - * - * Note that if the ptr is at the end of the list, NULL is returned. - * - * This primitive may safely run concurrently with the _rcu list-mutation - * primitives such as list_add_rcu() as long as it's guarded by rcu_read_lock(). - */ -#define list_next_or_null_rcu(head, ptr, type, member) \ -({ \ - struct list_head *__head = (head); \ - struct list_head *__ptr = (ptr); \ - struct list_head *__next = READ_ONCE(__ptr->next); \ - likely(__next != __head) ? list_entry_rcu(__next, type, \ - member) : NULL; \ -}) - -/** - * list_for_each_entry_rcu - iterate over rcu list of given type - * @pos: the type * to use as a loop cursor. - * @head: the head for your list. - * @member: the name of the list_head within the struct. - * - * 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((head)->next, typeof(*pos), member); \ - &pos->member != (head); \ - pos = list_entry_rcu(pos->member.next, typeof(*pos), member)) - -/** - * list_entry_lockless - get the struct for this entry - * @ptr: the &struct list_head pointer. - * @type: the type of the struct this is embedded in. - * @member: the name of the list_head within the struct. - * - * This primitive may safely run concurrently with the _rcu list-mutation - * primitives such as list_add_rcu(), but requires some implicit RCU - * read-side guarding. One example is running within a special - * exception-time environment where preemption is disabled and where - * lockdep cannot be invoked (in which case updaters must use RCU-sched, - * as in synchronize_sched(), call_rcu_sched(), and friends). Another - * example is when items are added to the list, but never deleted. - */ -#define list_entry_lockless(ptr, type, member) \ - container_of((typeof(ptr))lockless_dereference(ptr), type, member) - -/** - * list_for_each_entry_lockless - iterate over rcu list of given type - * @pos: the type * to use as a loop cursor. - * @head: the head for your list. - * @member: the name of the list_struct within the struct. - * - * This primitive may safely run concurrently with the _rcu list-mutation - * primitives such as list_add_rcu(), but requires some implicit RCU - * read-side guarding. One example is running within a special - * exception-time environment where preemption is disabled and where - * lockdep cannot be invoked (in which case updaters must use RCU-sched, - * as in synchronize_sched(), call_rcu_sched(), and friends). Another - * example is when items are added to the list, but never deleted. - */ -#define list_for_each_entry_lockless(pos, head, member) \ - for (pos = list_entry_lockless((head)->next, typeof(*pos), member); \ - &pos->member != (head); \ - pos = list_entry_lockless(pos->member.next, typeof(*pos), member)) - -/** - * list_for_each_entry_continue_rcu - continue iteration over list of given type - * @pos: the type * to use as a loop cursor. - * @head: the head for your list. - * @member: the name of the list_head within the struct. - * - * Continue to iterate over list of given type, continuing after - * the current position. - */ -#define list_for_each_entry_continue_rcu(pos, head, member) \ - for (pos = list_entry_rcu(pos->member.next, typeof(*pos), member); \ - &pos->member != (head); \ - pos = list_entry_rcu(pos->member.next, typeof(*pos), member)) - -/** - * hlist_del_rcu - deletes entry from hash list without re-initialization - * @n: the element to delete from the hash list. - * - * Note: list_unhashed() on entry does not return true after this, - * the entry is in an undefined state. It is useful for RCU based - * lockfree traversal. - * - * In particular, it means that we can not poison the forward - * pointers that may still be used for walking the hash list. - * - * The caller must take whatever precautions are necessary - * (such as holding appropriate locks) to avoid racing - * with another list-mutation primitive, such as hlist_add_head_rcu() - * or hlist_del_rcu(), running on this same list. - * However, it is perfectly legal to run concurrently with - * the _rcu list-traversal primitives, such as - * hlist_for_each_entry(). - */ -static inline void hlist_del_rcu(struct hlist_node *n) -{ - __hlist_del(n); - n->pprev = LIST_POISON2; -} - -/** - * hlist_replace_rcu - replace old entry by new one - * @old : the element to be replaced - * @new : the new element to insert - * - * 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) -{ - struct hlist_node *next = old->next; - - new->next = next; - new->pprev = old->pprev; - rcu_assign_pointer(*(struct hlist_node __rcu **)new->pprev, new); - if (next) - new->next->pprev = &new->next; - old->pprev = LIST_POISON2; -} - -/* - * return the first or the next element in an RCU protected hlist - */ -#define hlist_first_rcu(head) (*((struct hlist_node __rcu **)(&(head)->first))) -#define hlist_next_rcu(node) (*((struct hlist_node __rcu **)(&(node)->next))) -#define hlist_pprev_rcu(node) (*((struct hlist_node __rcu **)((node)->pprev))) - -/** - * hlist_add_head_rcu - * @n: the element to add to the hash list. - * @h: the list to add to. - * - * Description: - * Adds the specified element to the specified hlist, - * while permitting racing traversals. - * - * The caller must take whatever precautions are necessary - * (such as holding appropriate locks) to avoid racing - * with another list-mutation primitive, such as hlist_add_head_rcu() - * or hlist_del_rcu(), running on this same list. - * However, it is perfectly legal to run concurrently with - * the _rcu list-traversal primitives, such as - * hlist_for_each_entry_rcu(), used to prevent memory-consistency - * 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) -{ - struct hlist_node *first = h->first; - - n->next = first; - n->pprev = &h->first; - rcu_assign_pointer(hlist_first_rcu(h), n); - if (first) - first->pprev = &n->next; -} - -/** - * hlist_add_tail_rcu - * @n: the element to add to the hash list. - * @h: the list to add to. - * - * Description: - * Adds the specified element to the specified hlist, - * while permitting racing traversals. - * - * The caller must take whatever precautions are necessary - * (such as holding appropriate locks) to avoid racing - * with another list-mutation primitive, such as hlist_add_head_rcu() - * or hlist_del_rcu(), running on this same list. - * However, it is perfectly legal to run concurrently with - * the _rcu list-traversal primitives, such as - * hlist_for_each_entry_rcu(), used to prevent memory-consistency - * 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_tail_rcu(struct hlist_node *n, - struct hlist_head *h) -{ - struct hlist_node *i, *last = NULL; - - for (i = hlist_first_rcu(h); i; i = hlist_next_rcu(i)) - last = i; - - if (last) { - n->next = last->next; - n->pprev = &last->next; - rcu_assign_pointer(hlist_next_rcu(last), n); - } else { - hlist_add_head_rcu(n, h); - } -} - -/** - * hlist_add_before_rcu - * @n: the new element to add to the hash list. - * @next: the existing element to add the new element before. - * - * Description: - * Adds the specified element to the specified hlist - * before the specified node while permitting racing traversals. - * - * The caller must take whatever precautions are necessary - * (such as holding appropriate locks) to avoid racing - * with another list-mutation primitive, such as hlist_add_head_rcu() - * or hlist_del_rcu(), running on this same list. - * However, it is perfectly legal to run concurrently with - * the _rcu list-traversal primitives, such as - * 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) -{ - n->pprev = next->pprev; - n->next = next; - rcu_assign_pointer(hlist_pprev_rcu(n), n); - next->pprev = &n->next; -} - -/** - * hlist_add_behind_rcu - * @n: the new element to add to the hash list. - * @prev: the existing element to add the new element after. - * - * Description: - * Adds the specified element to the specified hlist - * after the specified node while permitting racing traversals. - * - * The caller must take whatever precautions are necessary - * (such as holding appropriate locks) to avoid racing - * with another list-mutation primitive, such as hlist_add_head_rcu() - * or hlist_del_rcu(), running on this same list. - * However, it is perfectly legal to run concurrently with - * the _rcu list-traversal primitives, such as - * hlist_for_each_entry_rcu(), used to prevent memory-consistency - * problems on Alpha CPUs. - */ -static inline void hlist_add_behind_rcu(struct hlist_node *n, - struct hlist_node *prev) -{ - n->next = prev->next; - n->pprev = &prev->next; - rcu_assign_pointer(hlist_next_rcu(prev), n); - if (n->next) - n->next->pprev = &n->next; -} - -#define __hlist_for_each_rcu(pos, head) \ - for (pos = rcu_dereference(hlist_first_rcu(head)); \ - pos; \ - pos = rcu_dereference(hlist_next_rcu(pos))) - -/** - * hlist_for_each_entry_rcu - iterate over rcu list of given type - * @pos: the type * to use as a loop cursor. - * @head: the head for your list. - * @member: the name of the 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() - * as long as the traversal is guarded by rcu_read_lock(). - */ -#define hlist_for_each_entry_rcu(pos, head, member) \ - for (pos = hlist_entry_safe (rcu_dereference_raw(hlist_first_rcu(head)),\ - typeof(*(pos)), member); \ - pos; \ - pos = hlist_entry_safe(rcu_dereference_raw(hlist_next_rcu(\ - &(pos)->member)), typeof(*(pos)), member)) - -/** - * hlist_for_each_entry_rcu_notrace - iterate over rcu list of given type (for tracing) - * @pos: the type * to use as a loop cursor. - * @head: the head for your list. - * @member: the name of the 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() - * as long as the traversal is guarded by rcu_read_lock(). - * - * This is the same as hlist_for_each_entry_rcu() except that it does - * not do any RCU debugging or tracing. - */ -#define hlist_for_each_entry_rcu_notrace(pos, head, member) \ - for (pos = hlist_entry_safe (rcu_dereference_raw_notrace(hlist_first_rcu(head)),\ - typeof(*(pos)), member); \ - pos; \ - pos = hlist_entry_safe(rcu_dereference_raw_notrace(hlist_next_rcu(\ - &(pos)->member)), typeof(*(pos)), member)) - -/** - * hlist_for_each_entry_rcu_bh - iterate over rcu list of given type - * @pos: the type * to use as a loop cursor. - * @head: the head for your list. - * @member: the name of the 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() - * as long as the traversal is guarded by rcu_read_lock(). - */ -#define hlist_for_each_entry_rcu_bh(pos, head, member) \ - for (pos = hlist_entry_safe(rcu_dereference_bh(hlist_first_rcu(head)),\ - typeof(*(pos)), member); \ - pos; \ - pos = hlist_entry_safe(rcu_dereference_bh(hlist_next_rcu(\ - &(pos)->member)), typeof(*(pos)), member)) - -/** - * hlist_for_each_entry_continue_rcu - iterate over a hlist continuing after current point - * @pos: the type * to use as a loop cursor. - * @member: the name of the hlist_node within the struct. - */ -#define hlist_for_each_entry_continue_rcu(pos, member) \ - for (pos = hlist_entry_safe(rcu_dereference_raw(hlist_next_rcu( \ - &(pos)->member)), typeof(*(pos)), member); \ - pos; \ - pos = hlist_entry_safe(rcu_dereference_raw(hlist_next_rcu( \ - &(pos)->member)), typeof(*(pos)), member)) - -/** - * hlist_for_each_entry_continue_rcu_bh - iterate over a hlist continuing after current point - * @pos: the type * to use as a loop cursor. - * @member: the name of the hlist_node within the struct. - */ -#define hlist_for_each_entry_continue_rcu_bh(pos, member) \ - for (pos = hlist_entry_safe(rcu_dereference_bh(hlist_next_rcu( \ - &(pos)->member)), typeof(*(pos)), member); \ - pos; \ - pos = hlist_entry_safe(rcu_dereference_bh(hlist_next_rcu( \ - &(pos)->member)), typeof(*(pos)), member)) +#define hlist_for_each_rcu cds_hlist_for_each_rcu +#define hlist_for_each_entry_rcu cds_hlist_for_each_entry_rcu_2 -/** - * hlist_for_each_entry_from_rcu - iterate over a hlist continuing from current point - * @pos: the type * to use as a loop cursor. - * @member: the name of the hlist_node within the struct. - */ -#define hlist_for_each_entry_from_rcu(pos, member) \ - for (; pos; \ - pos = hlist_entry_safe(rcu_dereference_raw(hlist_next_rcu( \ - &(pos)->member)), typeof(*(pos)), member)) #endif |