Eric Lee / smarc-fsl-linux-kernel

Blame view

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