list_bl.h

  1/* SPDX-License-Identifier: GPL-2.0 */
  2#ifndef _LINUX_LIST_BL_H
  3#define _LINUX_LIST_BL_H
  4
  5#include <linux/list.h>
  6#include <linux/bit_spinlock.h>
  7
  8/*
  9 * Special version of lists, where head of the list has a lock in the lowest
 10 * bit. This is useful for scalable hash tables without increasing memory
 11 * footprint overhead.
 12 *
 13 * For modification operations, the 0 bit of hlist_bl_head->first
 14 * pointer must be set.
 15 *
 16 * With some small modifications, this can easily be adapted to store several
 17 * arbitrary bits (not just a single lock bit), if the need arises to store
 18 * some fast and compact auxiliary data.
 19 */
 20
 21#if defined(CONFIG_SMP) || defined(CONFIG_DEBUG_SPINLOCK)
 22#define LIST_BL_LOCKMASK	1UL
 23#else
 24#define LIST_BL_LOCKMASK	0UL
 25#endif
 26
 27#ifdef CONFIG_DEBUG_LIST
 28#define LIST_BL_BUG_ON(x) BUG_ON(x)
 29#else
 30#define LIST_BL_BUG_ON(x)
 31#endif
 32
 33
 34struct hlist_bl_head {
 35	struct hlist_bl_node *first;
 36};
 37
 38struct hlist_bl_node {
 39	struct hlist_bl_node *next, **pprev;
 40};
 41#define INIT_HLIST_BL_HEAD(ptr) \
 42	((ptr)->first = NULL)
 43
 44static inline void INIT_HLIST_BL_NODE(struct hlist_bl_node *h)
 45{
 46	h->next = NULL;
 47	h->pprev = NULL;
 48}
 49
 50#define hlist_bl_entry(ptr, type, member) container_of(ptr,type,member)
 51
 52static inline bool  hlist_bl_unhashed(const struct hlist_bl_node *h)
 53{
 54	return !h->pprev;
 55}
 56
 57static inline struct hlist_bl_node *hlist_bl_first(struct hlist_bl_head *h)
 58{
 59	return (struct hlist_bl_node *)
 60		((unsigned long)h->first & ~LIST_BL_LOCKMASK);
 61}
 62
 63static inline void hlist_bl_set_first(struct hlist_bl_head *h,
 64					struct hlist_bl_node *n)
 65{
 66	LIST_BL_BUG_ON((unsigned long)n & LIST_BL_LOCKMASK);
 67	LIST_BL_BUG_ON(((unsigned long)h->first & LIST_BL_LOCKMASK) !=
 68							LIST_BL_LOCKMASK);
 69	h->first = (struct hlist_bl_node *)((unsigned long)n | LIST_BL_LOCKMASK);
 70}
 71
 72static inline bool hlist_bl_empty(const struct hlist_bl_head *h)
 73{
 74	return !((unsigned long)READ_ONCE(h->first) & ~LIST_BL_LOCKMASK);
 75}
 76
 77static inline void hlist_bl_add_head(struct hlist_bl_node *n,
 78					struct hlist_bl_head *h)
 79{
 80	struct hlist_bl_node *first = hlist_bl_first(h);
 81
 82	n->next = first;
 83	if (first)
 84		first->pprev = &n->next;
 85	n->pprev = &h->first;
 86	hlist_bl_set_first(h, n);
 87}
 88
 89static inline void hlist_bl_add_before(struct hlist_bl_node *n,
 90				       struct hlist_bl_node *next)
 91{
 92	struct hlist_bl_node **pprev = next->pprev;
 93
 94	n->pprev = pprev;
 95	n->next = next;
 96	next->pprev = &n->next;
 97
 98	/* pprev may be `first`, so be careful not to lose the lock bit */
 99	WRITE_ONCE(*pprev,
100		   (struct hlist_bl_node *)
101			((uintptr_t)n | ((uintptr_t)*pprev & LIST_BL_LOCKMASK)));
102}
103
104static inline void hlist_bl_add_behind(struct hlist_bl_node *n,
105				       struct hlist_bl_node *prev)
106{
107	n->next = prev->next;
108	n->pprev = &prev->next;
109	prev->next = n;
110
111	if (n->next)
112		n->next->pprev = &n->next;
113}
114
115static inline void __hlist_bl_del(struct hlist_bl_node *n)
116{
117	struct hlist_bl_node *next = n->next;
118	struct hlist_bl_node **pprev = n->pprev;
119
120	LIST_BL_BUG_ON((unsigned long)n & LIST_BL_LOCKMASK);
121
122	/* pprev may be `first`, so be careful not to lose the lock bit */
123	WRITE_ONCE(*pprev,
124		   (struct hlist_bl_node *)
125			((unsigned long)next |
126			 ((unsigned long)*pprev & LIST_BL_LOCKMASK)));
127	if (next)
128		next->pprev = pprev;
129}
130
131static inline void hlist_bl_del(struct hlist_bl_node *n)
132{
133	__hlist_bl_del(n);
134	n->next = LIST_POISON1;
135	n->pprev = LIST_POISON2;
136}
137
138static inline void hlist_bl_del_init(struct hlist_bl_node *n)
139{
140	if (!hlist_bl_unhashed(n)) {
141		__hlist_bl_del(n);
142		INIT_HLIST_BL_NODE(n);
143	}
144}
145
146static inline void hlist_bl_lock(struct hlist_bl_head *b)
147{
148	bit_spin_lock(0, (unsigned long *)b);
149}
150
151static inline void hlist_bl_unlock(struct hlist_bl_head *b)
152{
153	__bit_spin_unlock(0, (unsigned long *)b);
154}
155
156static inline bool hlist_bl_is_locked(struct hlist_bl_head *b)
157{
158	return bit_spin_is_locked(0, (unsigned long *)b);
159}
160
161/**
162 * hlist_bl_for_each_entry	- iterate over list of given type
163 * @tpos:	the type * to use as a loop cursor.
164 * @pos:	the &struct hlist_node to use as a loop cursor.
165 * @head:	the head for your list.
166 * @member:	the name of the hlist_node within the struct.
167 *
168 */
169#define hlist_bl_for_each_entry(tpos, pos, head, member)		\
170	for (pos = hlist_bl_first(head);				\
171	     pos &&							\
172		({ tpos = hlist_bl_entry(pos, typeof(*tpos), member); 1;}); \
173	     pos = pos->next)
174
175/**
176 * hlist_bl_for_each_entry_safe - iterate over list of given type safe against removal of list entry
177 * @tpos:	the type * to use as a loop cursor.
178 * @pos:	the &struct hlist_node to use as a loop cursor.
179 * @n:		another &struct hlist_node to use as temporary storage
180 * @head:	the head for your list.
181 * @member:	the name of the hlist_node within the struct.
182 */
183#define hlist_bl_for_each_entry_safe(tpos, pos, n, head, member)	 \
184	for (pos = hlist_bl_first(head);				 \
185	     pos && ({ n = pos->next; 1; }) && 				 \
186		({ tpos = hlist_bl_entry(pos, typeof(*tpos), member); 1;}); \
187	     pos = n)
188
189#endif