14e35e6070b1ceed89c3bba2af4216c286fb1dafdNick Piggin#ifndef _LINUX_RCULIST_BL_H 24e35e6070b1ceed89c3bba2af4216c286fb1dafdNick Piggin#define _LINUX_RCULIST_BL_H 34e35e6070b1ceed89c3bba2af4216c286fb1dafdNick Piggin 44e35e6070b1ceed89c3bba2af4216c286fb1dafdNick Piggin/* 54e35e6070b1ceed89c3bba2af4216c286fb1dafdNick Piggin * RCU-protected bl list version. See include/linux/list_bl.h. 64e35e6070b1ceed89c3bba2af4216c286fb1dafdNick Piggin */ 74e35e6070b1ceed89c3bba2af4216c286fb1dafdNick Piggin#include <linux/list_bl.h> 84e35e6070b1ceed89c3bba2af4216c286fb1dafdNick Piggin#include <linux/rcupdate.h> 94e35e6070b1ceed89c3bba2af4216c286fb1dafdNick Piggin 104e35e6070b1ceed89c3bba2af4216c286fb1dafdNick Pigginstatic inline void hlist_bl_set_first_rcu(struct hlist_bl_head *h, 114e35e6070b1ceed89c3bba2af4216c286fb1dafdNick Piggin struct hlist_bl_node *n) 124e35e6070b1ceed89c3bba2af4216c286fb1dafdNick Piggin{ 134e35e6070b1ceed89c3bba2af4216c286fb1dafdNick Piggin LIST_BL_BUG_ON((unsigned long)n & LIST_BL_LOCKMASK); 142c6755988afc003a0332406a134fb6a1626f9b28Nick Piggin LIST_BL_BUG_ON(((unsigned long)h->first & LIST_BL_LOCKMASK) != 152c6755988afc003a0332406a134fb6a1626f9b28Nick Piggin LIST_BL_LOCKMASK); 164e35e6070b1ceed89c3bba2af4216c286fb1dafdNick Piggin rcu_assign_pointer(h->first, 174e35e6070b1ceed89c3bba2af4216c286fb1dafdNick Piggin (struct hlist_bl_node *)((unsigned long)n | LIST_BL_LOCKMASK)); 184e35e6070b1ceed89c3bba2af4216c286fb1dafdNick Piggin} 194e35e6070b1ceed89c3bba2af4216c286fb1dafdNick Piggin 204e35e6070b1ceed89c3bba2af4216c286fb1dafdNick Pigginstatic inline struct hlist_bl_node *hlist_bl_first_rcu(struct hlist_bl_head *h) 214e35e6070b1ceed89c3bba2af4216c286fb1dafdNick Piggin{ 224e35e6070b1ceed89c3bba2af4216c286fb1dafdNick Piggin return (struct hlist_bl_node *) 2349d0de082c31de34cc896c14eec5f1c2ade0415aSteven Whitehouse ((unsigned long)rcu_dereference_check(h->first, hlist_bl_is_locked(h)) & ~LIST_BL_LOCKMASK); 244e35e6070b1ceed89c3bba2af4216c286fb1dafdNick Piggin} 254e35e6070b1ceed89c3bba2af4216c286fb1dafdNick Piggin 264e35e6070b1ceed89c3bba2af4216c286fb1dafdNick Piggin/** 274e35e6070b1ceed89c3bba2af4216c286fb1dafdNick Piggin * hlist_bl_del_init_rcu - deletes entry from hash list with re-initialization 284e35e6070b1ceed89c3bba2af4216c286fb1dafdNick Piggin * @n: the element to delete from the hash list. 294e35e6070b1ceed89c3bba2af4216c286fb1dafdNick Piggin * 304e35e6070b1ceed89c3bba2af4216c286fb1dafdNick Piggin * Note: hlist_bl_unhashed() on the node returns true after this. It is 314e35e6070b1ceed89c3bba2af4216c286fb1dafdNick Piggin * useful for RCU based read lockfree traversal if the writer side 324e35e6070b1ceed89c3bba2af4216c286fb1dafdNick Piggin * must know if the list entry is still hashed or already unhashed. 334e35e6070b1ceed89c3bba2af4216c286fb1dafdNick Piggin * 344e35e6070b1ceed89c3bba2af4216c286fb1dafdNick Piggin * In particular, it means that we can not poison the forward pointers 354e35e6070b1ceed89c3bba2af4216c286fb1dafdNick Piggin * that may still be used for walking the hash list and we can only 364e35e6070b1ceed89c3bba2af4216c286fb1dafdNick Piggin * zero the pprev pointer so list_unhashed() will return true after 374e35e6070b1ceed89c3bba2af4216c286fb1dafdNick Piggin * this. 384e35e6070b1ceed89c3bba2af4216c286fb1dafdNick Piggin * 394e35e6070b1ceed89c3bba2af4216c286fb1dafdNick Piggin * The caller must take whatever precautions are necessary (such as 404e35e6070b1ceed89c3bba2af4216c286fb1dafdNick Piggin * holding appropriate locks) to avoid racing with another 414e35e6070b1ceed89c3bba2af4216c286fb1dafdNick Piggin * list-mutation primitive, such as hlist_bl_add_head_rcu() or 424e35e6070b1ceed89c3bba2af4216c286fb1dafdNick Piggin * hlist_bl_del_rcu(), running on this same list. However, it is 434e35e6070b1ceed89c3bba2af4216c286fb1dafdNick Piggin * perfectly legal to run concurrently with the _rcu list-traversal 444e35e6070b1ceed89c3bba2af4216c286fb1dafdNick Piggin * primitives, such as hlist_bl_for_each_entry_rcu(). 454e35e6070b1ceed89c3bba2af4216c286fb1dafdNick Piggin */ 464e35e6070b1ceed89c3bba2af4216c286fb1dafdNick Pigginstatic inline void hlist_bl_del_init_rcu(struct hlist_bl_node *n) 474e35e6070b1ceed89c3bba2af4216c286fb1dafdNick Piggin{ 484e35e6070b1ceed89c3bba2af4216c286fb1dafdNick Piggin if (!hlist_bl_unhashed(n)) { 494e35e6070b1ceed89c3bba2af4216c286fb1dafdNick Piggin __hlist_bl_del(n); 504e35e6070b1ceed89c3bba2af4216c286fb1dafdNick Piggin n->pprev = NULL; 514e35e6070b1ceed89c3bba2af4216c286fb1dafdNick Piggin } 524e35e6070b1ceed89c3bba2af4216c286fb1dafdNick Piggin} 534e35e6070b1ceed89c3bba2af4216c286fb1dafdNick Piggin 544e35e6070b1ceed89c3bba2af4216c286fb1dafdNick Piggin/** 554e35e6070b1ceed89c3bba2af4216c286fb1dafdNick Piggin * hlist_bl_del_rcu - deletes entry from hash list without re-initialization 564e35e6070b1ceed89c3bba2af4216c286fb1dafdNick Piggin * @n: the element to delete from the hash list. 574e35e6070b1ceed89c3bba2af4216c286fb1dafdNick Piggin * 584e35e6070b1ceed89c3bba2af4216c286fb1dafdNick Piggin * Note: hlist_bl_unhashed() on entry does not return true after this, 594e35e6070b1ceed89c3bba2af4216c286fb1dafdNick Piggin * the entry is in an undefined state. It is useful for RCU based 604e35e6070b1ceed89c3bba2af4216c286fb1dafdNick Piggin * lockfree traversal. 614e35e6070b1ceed89c3bba2af4216c286fb1dafdNick Piggin * 624e35e6070b1ceed89c3bba2af4216c286fb1dafdNick Piggin * In particular, it means that we can not poison the forward 634e35e6070b1ceed89c3bba2af4216c286fb1dafdNick Piggin * pointers that may still be used for walking the hash list. 644e35e6070b1ceed89c3bba2af4216c286fb1dafdNick Piggin * 654e35e6070b1ceed89c3bba2af4216c286fb1dafdNick Piggin * The caller must take whatever precautions are necessary 664e35e6070b1ceed89c3bba2af4216c286fb1dafdNick Piggin * (such as holding appropriate locks) to avoid racing 674e35e6070b1ceed89c3bba2af4216c286fb1dafdNick Piggin * with another list-mutation primitive, such as hlist_bl_add_head_rcu() 684e35e6070b1ceed89c3bba2af4216c286fb1dafdNick Piggin * or hlist_bl_del_rcu(), running on this same list. 694e35e6070b1ceed89c3bba2af4216c286fb1dafdNick Piggin * However, it is perfectly legal to run concurrently with 704e35e6070b1ceed89c3bba2af4216c286fb1dafdNick Piggin * the _rcu list-traversal primitives, such as 714e35e6070b1ceed89c3bba2af4216c286fb1dafdNick Piggin * hlist_bl_for_each_entry(). 724e35e6070b1ceed89c3bba2af4216c286fb1dafdNick Piggin */ 734e35e6070b1ceed89c3bba2af4216c286fb1dafdNick Pigginstatic inline void hlist_bl_del_rcu(struct hlist_bl_node *n) 744e35e6070b1ceed89c3bba2af4216c286fb1dafdNick Piggin{ 754e35e6070b1ceed89c3bba2af4216c286fb1dafdNick Piggin __hlist_bl_del(n); 764e35e6070b1ceed89c3bba2af4216c286fb1dafdNick Piggin n->pprev = LIST_POISON2; 774e35e6070b1ceed89c3bba2af4216c286fb1dafdNick Piggin} 784e35e6070b1ceed89c3bba2af4216c286fb1dafdNick Piggin 794e35e6070b1ceed89c3bba2af4216c286fb1dafdNick Piggin/** 804e35e6070b1ceed89c3bba2af4216c286fb1dafdNick Piggin * hlist_bl_add_head_rcu 814e35e6070b1ceed89c3bba2af4216c286fb1dafdNick Piggin * @n: the element to add to the hash list. 824e35e6070b1ceed89c3bba2af4216c286fb1dafdNick Piggin * @h: the list to add to. 834e35e6070b1ceed89c3bba2af4216c286fb1dafdNick Piggin * 844e35e6070b1ceed89c3bba2af4216c286fb1dafdNick Piggin * Description: 854e35e6070b1ceed89c3bba2af4216c286fb1dafdNick Piggin * Adds the specified element to the specified hlist_bl, 864e35e6070b1ceed89c3bba2af4216c286fb1dafdNick Piggin * while permitting racing traversals. 874e35e6070b1ceed89c3bba2af4216c286fb1dafdNick Piggin * 884e35e6070b1ceed89c3bba2af4216c286fb1dafdNick Piggin * The caller must take whatever precautions are necessary 894e35e6070b1ceed89c3bba2af4216c286fb1dafdNick Piggin * (such as holding appropriate locks) to avoid racing 904e35e6070b1ceed89c3bba2af4216c286fb1dafdNick Piggin * with another list-mutation primitive, such as hlist_bl_add_head_rcu() 914e35e6070b1ceed89c3bba2af4216c286fb1dafdNick Piggin * or hlist_bl_del_rcu(), running on this same list. 924e35e6070b1ceed89c3bba2af4216c286fb1dafdNick Piggin * However, it is perfectly legal to run concurrently with 934e35e6070b1ceed89c3bba2af4216c286fb1dafdNick Piggin * the _rcu list-traversal primitives, such as 944e35e6070b1ceed89c3bba2af4216c286fb1dafdNick Piggin * hlist_bl_for_each_entry_rcu(), used to prevent memory-consistency 954e35e6070b1ceed89c3bba2af4216c286fb1dafdNick Piggin * problems on Alpha CPUs. Regardless of the type of CPU, the 964e35e6070b1ceed89c3bba2af4216c286fb1dafdNick Piggin * list-traversal primitive must be guarded by rcu_read_lock(). 974e35e6070b1ceed89c3bba2af4216c286fb1dafdNick Piggin */ 984e35e6070b1ceed89c3bba2af4216c286fb1dafdNick Pigginstatic inline void hlist_bl_add_head_rcu(struct hlist_bl_node *n, 994e35e6070b1ceed89c3bba2af4216c286fb1dafdNick Piggin struct hlist_bl_head *h) 1004e35e6070b1ceed89c3bba2af4216c286fb1dafdNick Piggin{ 1014e35e6070b1ceed89c3bba2af4216c286fb1dafdNick Piggin struct hlist_bl_node *first; 1024e35e6070b1ceed89c3bba2af4216c286fb1dafdNick Piggin 1034e35e6070b1ceed89c3bba2af4216c286fb1dafdNick Piggin /* don't need hlist_bl_first_rcu because we're under lock */ 1044e35e6070b1ceed89c3bba2af4216c286fb1dafdNick Piggin first = hlist_bl_first(h); 1054e35e6070b1ceed89c3bba2af4216c286fb1dafdNick Piggin 1064e35e6070b1ceed89c3bba2af4216c286fb1dafdNick Piggin n->next = first; 1074e35e6070b1ceed89c3bba2af4216c286fb1dafdNick Piggin if (first) 1084e35e6070b1ceed89c3bba2af4216c286fb1dafdNick Piggin first->pprev = &n->next; 1094e35e6070b1ceed89c3bba2af4216c286fb1dafdNick Piggin n->pprev = &h->first; 1104e35e6070b1ceed89c3bba2af4216c286fb1dafdNick Piggin 1114e35e6070b1ceed89c3bba2af4216c286fb1dafdNick Piggin /* need _rcu because we can have concurrent lock free readers */ 1124e35e6070b1ceed89c3bba2af4216c286fb1dafdNick Piggin hlist_bl_set_first_rcu(h, n); 1134e35e6070b1ceed89c3bba2af4216c286fb1dafdNick Piggin} 1144e35e6070b1ceed89c3bba2af4216c286fb1dafdNick Piggin/** 1154e35e6070b1ceed89c3bba2af4216c286fb1dafdNick Piggin * hlist_bl_for_each_entry_rcu - iterate over rcu list of given type 1164e35e6070b1ceed89c3bba2af4216c286fb1dafdNick Piggin * @tpos: the type * to use as a loop cursor. 1174e35e6070b1ceed89c3bba2af4216c286fb1dafdNick Piggin * @pos: the &struct hlist_bl_node to use as a loop cursor. 1184e35e6070b1ceed89c3bba2af4216c286fb1dafdNick Piggin * @head: the head for your list. 1194e35e6070b1ceed89c3bba2af4216c286fb1dafdNick Piggin * @member: the name of the hlist_bl_node within the struct. 1204e35e6070b1ceed89c3bba2af4216c286fb1dafdNick Piggin * 1214e35e6070b1ceed89c3bba2af4216c286fb1dafdNick Piggin */ 1224e35e6070b1ceed89c3bba2af4216c286fb1dafdNick Piggin#define hlist_bl_for_each_entry_rcu(tpos, pos, head, member) \ 1234e35e6070b1ceed89c3bba2af4216c286fb1dafdNick Piggin for (pos = hlist_bl_first_rcu(head); \ 1244e35e6070b1ceed89c3bba2af4216c286fb1dafdNick Piggin pos && \ 1254e35e6070b1ceed89c3bba2af4216c286fb1dafdNick Piggin ({ tpos = hlist_bl_entry(pos, typeof(*tpos), member); 1; }); \ 1264e35e6070b1ceed89c3bba2af4216c286fb1dafdNick Piggin pos = rcu_dereference_raw(pos->next)) 1274e35e6070b1ceed89c3bba2af4216c286fb1dafdNick Piggin 1284e35e6070b1ceed89c3bba2af4216c286fb1dafdNick Piggin#endif 129