1bbaffaca4810de1a25e32ecaf836eeaacc7a3d11Eric Dumazet#ifndef _LINUX_RCULIST_NULLS_H 2bbaffaca4810de1a25e32ecaf836eeaacc7a3d11Eric Dumazet#define _LINUX_RCULIST_NULLS_H 3bbaffaca4810de1a25e32ecaf836eeaacc7a3d11Eric Dumazet 4bbaffaca4810de1a25e32ecaf836eeaacc7a3d11Eric Dumazet#ifdef __KERNEL__ 5bbaffaca4810de1a25e32ecaf836eeaacc7a3d11Eric Dumazet 6bbaffaca4810de1a25e32ecaf836eeaacc7a3d11Eric Dumazet/* 7bbaffaca4810de1a25e32ecaf836eeaacc7a3d11Eric Dumazet * RCU-protected list version 8bbaffaca4810de1a25e32ecaf836eeaacc7a3d11Eric Dumazet */ 9bbaffaca4810de1a25e32ecaf836eeaacc7a3d11Eric Dumazet#include <linux/list_nulls.h> 10bbaffaca4810de1a25e32ecaf836eeaacc7a3d11Eric Dumazet#include <linux/rcupdate.h> 11bbaffaca4810de1a25e32ecaf836eeaacc7a3d11Eric Dumazet 12bbaffaca4810de1a25e32ecaf836eeaacc7a3d11Eric Dumazet/** 13bbaffaca4810de1a25e32ecaf836eeaacc7a3d11Eric Dumazet * hlist_nulls_del_init_rcu - deletes entry from hash list with re-initialization 14bbaffaca4810de1a25e32ecaf836eeaacc7a3d11Eric Dumazet * @n: the element to delete from the hash list. 15bbaffaca4810de1a25e32ecaf836eeaacc7a3d11Eric Dumazet * 16bbaffaca4810de1a25e32ecaf836eeaacc7a3d11Eric Dumazet * Note: hlist_nulls_unhashed() on the node return true after this. It is 17bbaffaca4810de1a25e32ecaf836eeaacc7a3d11Eric Dumazet * useful for RCU based read lockfree traversal if the writer side 18bbaffaca4810de1a25e32ecaf836eeaacc7a3d11Eric Dumazet * must know if the list entry is still hashed or already unhashed. 19bbaffaca4810de1a25e32ecaf836eeaacc7a3d11Eric Dumazet * 20bbaffaca4810de1a25e32ecaf836eeaacc7a3d11Eric Dumazet * In particular, it means that we can not poison the forward pointers 21bbaffaca4810de1a25e32ecaf836eeaacc7a3d11Eric Dumazet * that may still be used for walking the hash list and we can only 22bbaffaca4810de1a25e32ecaf836eeaacc7a3d11Eric Dumazet * zero the pprev pointer so list_unhashed() will return true after 23bbaffaca4810de1a25e32ecaf836eeaacc7a3d11Eric Dumazet * this. 24bbaffaca4810de1a25e32ecaf836eeaacc7a3d11Eric Dumazet * 25bbaffaca4810de1a25e32ecaf836eeaacc7a3d11Eric Dumazet * The caller must take whatever precautions are necessary (such as 26bbaffaca4810de1a25e32ecaf836eeaacc7a3d11Eric Dumazet * holding appropriate locks) to avoid racing with another 27bbaffaca4810de1a25e32ecaf836eeaacc7a3d11Eric Dumazet * list-mutation primitive, such as hlist_nulls_add_head_rcu() or 28bbaffaca4810de1a25e32ecaf836eeaacc7a3d11Eric Dumazet * hlist_nulls_del_rcu(), running on this same list. However, it is 29bbaffaca4810de1a25e32ecaf836eeaacc7a3d11Eric Dumazet * perfectly legal to run concurrently with the _rcu list-traversal 30bbaffaca4810de1a25e32ecaf836eeaacc7a3d11Eric Dumazet * primitives, such as hlist_nulls_for_each_entry_rcu(). 31bbaffaca4810de1a25e32ecaf836eeaacc7a3d11Eric Dumazet */ 32bbaffaca4810de1a25e32ecaf836eeaacc7a3d11Eric Dumazetstatic inline void hlist_nulls_del_init_rcu(struct hlist_nulls_node *n) 33bbaffaca4810de1a25e32ecaf836eeaacc7a3d11Eric Dumazet{ 34bbaffaca4810de1a25e32ecaf836eeaacc7a3d11Eric Dumazet if (!hlist_nulls_unhashed(n)) { 35bbaffaca4810de1a25e32ecaf836eeaacc7a3d11Eric Dumazet __hlist_nulls_del(n); 36bbaffaca4810de1a25e32ecaf836eeaacc7a3d11Eric Dumazet n->pprev = NULL; 37bbaffaca4810de1a25e32ecaf836eeaacc7a3d11Eric Dumazet } 38bbaffaca4810de1a25e32ecaf836eeaacc7a3d11Eric Dumazet} 39bbaffaca4810de1a25e32ecaf836eeaacc7a3d11Eric Dumazet 4067bdbffd696f29a0b68aa8daa285783a06651583Arnd Bergmann#define hlist_nulls_first_rcu(head) \ 4167bdbffd696f29a0b68aa8daa285783a06651583Arnd Bergmann (*((struct hlist_nulls_node __rcu __force **)&(head)->first)) 4267bdbffd696f29a0b68aa8daa285783a06651583Arnd Bergmann 4367bdbffd696f29a0b68aa8daa285783a06651583Arnd Bergmann#define hlist_nulls_next_rcu(node) \ 4467bdbffd696f29a0b68aa8daa285783a06651583Arnd Bergmann (*((struct hlist_nulls_node __rcu __force **)&(node)->next)) 4567bdbffd696f29a0b68aa8daa285783a06651583Arnd Bergmann 46bbaffaca4810de1a25e32ecaf836eeaacc7a3d11Eric Dumazet/** 47bbaffaca4810de1a25e32ecaf836eeaacc7a3d11Eric Dumazet * hlist_nulls_del_rcu - deletes entry from hash list without re-initialization 48bbaffaca4810de1a25e32ecaf836eeaacc7a3d11Eric Dumazet * @n: the element to delete from the hash list. 49bbaffaca4810de1a25e32ecaf836eeaacc7a3d11Eric Dumazet * 50bbaffaca4810de1a25e32ecaf836eeaacc7a3d11Eric Dumazet * Note: hlist_nulls_unhashed() on entry does not return true after this, 51bbaffaca4810de1a25e32ecaf836eeaacc7a3d11Eric Dumazet * the entry is in an undefined state. It is useful for RCU based 52bbaffaca4810de1a25e32ecaf836eeaacc7a3d11Eric Dumazet * lockfree traversal. 53bbaffaca4810de1a25e32ecaf836eeaacc7a3d11Eric Dumazet * 54bbaffaca4810de1a25e32ecaf836eeaacc7a3d11Eric Dumazet * In particular, it means that we can not poison the forward 55bbaffaca4810de1a25e32ecaf836eeaacc7a3d11Eric Dumazet * pointers that may still be used for walking the hash list. 56bbaffaca4810de1a25e32ecaf836eeaacc7a3d11Eric Dumazet * 57bbaffaca4810de1a25e32ecaf836eeaacc7a3d11Eric Dumazet * The caller must take whatever precautions are necessary 58bbaffaca4810de1a25e32ecaf836eeaacc7a3d11Eric Dumazet * (such as holding appropriate locks) to avoid racing 59bbaffaca4810de1a25e32ecaf836eeaacc7a3d11Eric Dumazet * with another list-mutation primitive, such as hlist_nulls_add_head_rcu() 60bbaffaca4810de1a25e32ecaf836eeaacc7a3d11Eric Dumazet * or hlist_nulls_del_rcu(), running on this same list. 61bbaffaca4810de1a25e32ecaf836eeaacc7a3d11Eric Dumazet * However, it is perfectly legal to run concurrently with 62bbaffaca4810de1a25e32ecaf836eeaacc7a3d11Eric Dumazet * the _rcu list-traversal primitives, such as 63bbaffaca4810de1a25e32ecaf836eeaacc7a3d11Eric Dumazet * hlist_nulls_for_each_entry(). 64bbaffaca4810de1a25e32ecaf836eeaacc7a3d11Eric Dumazet */ 65bbaffaca4810de1a25e32ecaf836eeaacc7a3d11Eric Dumazetstatic inline void hlist_nulls_del_rcu(struct hlist_nulls_node *n) 66bbaffaca4810de1a25e32ecaf836eeaacc7a3d11Eric Dumazet{ 67bbaffaca4810de1a25e32ecaf836eeaacc7a3d11Eric Dumazet __hlist_nulls_del(n); 68bbaffaca4810de1a25e32ecaf836eeaacc7a3d11Eric Dumazet n->pprev = LIST_POISON2; 69bbaffaca4810de1a25e32ecaf836eeaacc7a3d11Eric Dumazet} 70bbaffaca4810de1a25e32ecaf836eeaacc7a3d11Eric Dumazet 71bbaffaca4810de1a25e32ecaf836eeaacc7a3d11Eric Dumazet/** 72bbaffaca4810de1a25e32ecaf836eeaacc7a3d11Eric Dumazet * hlist_nulls_add_head_rcu 73bbaffaca4810de1a25e32ecaf836eeaacc7a3d11Eric Dumazet * @n: the element to add to the hash list. 74bbaffaca4810de1a25e32ecaf836eeaacc7a3d11Eric Dumazet * @h: the list to add to. 75bbaffaca4810de1a25e32ecaf836eeaacc7a3d11Eric Dumazet * 76bbaffaca4810de1a25e32ecaf836eeaacc7a3d11Eric Dumazet * Description: 77bbaffaca4810de1a25e32ecaf836eeaacc7a3d11Eric Dumazet * Adds the specified element to the specified hlist_nulls, 78bbaffaca4810de1a25e32ecaf836eeaacc7a3d11Eric Dumazet * while permitting racing traversals. 79bbaffaca4810de1a25e32ecaf836eeaacc7a3d11Eric Dumazet * 80bbaffaca4810de1a25e32ecaf836eeaacc7a3d11Eric Dumazet * The caller must take whatever precautions are necessary 81bbaffaca4810de1a25e32ecaf836eeaacc7a3d11Eric Dumazet * (such as holding appropriate locks) to avoid racing 82bbaffaca4810de1a25e32ecaf836eeaacc7a3d11Eric Dumazet * with another list-mutation primitive, such as hlist_nulls_add_head_rcu() 83bbaffaca4810de1a25e32ecaf836eeaacc7a3d11Eric Dumazet * or hlist_nulls_del_rcu(), running on this same list. 84bbaffaca4810de1a25e32ecaf836eeaacc7a3d11Eric Dumazet * However, it is perfectly legal to run concurrently with 85bbaffaca4810de1a25e32ecaf836eeaacc7a3d11Eric Dumazet * the _rcu list-traversal primitives, such as 86bbaffaca4810de1a25e32ecaf836eeaacc7a3d11Eric Dumazet * hlist_nulls_for_each_entry_rcu(), used to prevent memory-consistency 87bbaffaca4810de1a25e32ecaf836eeaacc7a3d11Eric Dumazet * problems on Alpha CPUs. Regardless of the type of CPU, the 88bbaffaca4810de1a25e32ecaf836eeaacc7a3d11Eric Dumazet * list-traversal primitive must be guarded by rcu_read_lock(). 89bbaffaca4810de1a25e32ecaf836eeaacc7a3d11Eric Dumazet */ 90bbaffaca4810de1a25e32ecaf836eeaacc7a3d11Eric Dumazetstatic inline void hlist_nulls_add_head_rcu(struct hlist_nulls_node *n, 91bbaffaca4810de1a25e32ecaf836eeaacc7a3d11Eric Dumazet struct hlist_nulls_head *h) 92bbaffaca4810de1a25e32ecaf836eeaacc7a3d11Eric Dumazet{ 93bbaffaca4810de1a25e32ecaf836eeaacc7a3d11Eric Dumazet struct hlist_nulls_node *first = h->first; 94bbaffaca4810de1a25e32ecaf836eeaacc7a3d11Eric Dumazet 95bbaffaca4810de1a25e32ecaf836eeaacc7a3d11Eric Dumazet n->next = first; 96bbaffaca4810de1a25e32ecaf836eeaacc7a3d11Eric Dumazet n->pprev = &h->first; 9767bdbffd696f29a0b68aa8daa285783a06651583Arnd Bergmann rcu_assign_pointer(hlist_nulls_first_rcu(h), n); 98bbaffaca4810de1a25e32ecaf836eeaacc7a3d11Eric Dumazet if (!is_a_nulls(first)) 99bbaffaca4810de1a25e32ecaf836eeaacc7a3d11Eric Dumazet first->pprev = &n->next; 100bbaffaca4810de1a25e32ecaf836eeaacc7a3d11Eric Dumazet} 101bbaffaca4810de1a25e32ecaf836eeaacc7a3d11Eric Dumazet/** 102bbaffaca4810de1a25e32ecaf836eeaacc7a3d11Eric Dumazet * hlist_nulls_for_each_entry_rcu - iterate over rcu list of given type 103bbaffaca4810de1a25e32ecaf836eeaacc7a3d11Eric Dumazet * @tpos: the type * to use as a loop cursor. 104bbaffaca4810de1a25e32ecaf836eeaacc7a3d11Eric Dumazet * @pos: the &struct hlist_nulls_node to use as a loop cursor. 105bbaffaca4810de1a25e32ecaf836eeaacc7a3d11Eric Dumazet * @head: the head for your list. 106bbaffaca4810de1a25e32ecaf836eeaacc7a3d11Eric Dumazet * @member: the name of the hlist_nulls_node within the struct. 107bbaffaca4810de1a25e32ecaf836eeaacc7a3d11Eric Dumazet * 108c87a124a5d5e8cf8e21c4363c3372bcaf53ea190Eric Dumazet * The barrier() is needed to make sure compiler doesn't cache first element [1], 109c87a124a5d5e8cf8e21c4363c3372bcaf53ea190Eric Dumazet * as this loop can be restarted [2] 110c87a124a5d5e8cf8e21c4363c3372bcaf53ea190Eric Dumazet * [1] Documentation/atomic_ops.txt around line 114 111c87a124a5d5e8cf8e21c4363c3372bcaf53ea190Eric Dumazet * [2] Documentation/RCU/rculist_nulls.txt around line 146 112bbaffaca4810de1a25e32ecaf836eeaacc7a3d11Eric Dumazet */ 11367bdbffd696f29a0b68aa8daa285783a06651583Arnd Bergmann#define hlist_nulls_for_each_entry_rcu(tpos, pos, head, member) \ 114c87a124a5d5e8cf8e21c4363c3372bcaf53ea190Eric Dumazet for (({barrier();}), \ 115c87a124a5d5e8cf8e21c4363c3372bcaf53ea190Eric Dumazet pos = rcu_dereference_raw(hlist_nulls_first_rcu(head)); \ 11667bdbffd696f29a0b68aa8daa285783a06651583Arnd Bergmann (!is_a_nulls(pos)) && \ 117bbaffaca4810de1a25e32ecaf836eeaacc7a3d11Eric Dumazet ({ tpos = hlist_nulls_entry(pos, typeof(*tpos), member); 1; }); \ 11867bdbffd696f29a0b68aa8daa285783a06651583Arnd Bergmann pos = rcu_dereference_raw(hlist_nulls_next_rcu(pos))) 119bbaffaca4810de1a25e32ecaf836eeaacc7a3d11Eric Dumazet 120bbaffaca4810de1a25e32ecaf836eeaacc7a3d11Eric Dumazet#endif 121bbaffaca4810de1a25e32ecaf836eeaacc7a3d11Eric Dumazet#endif 122