aboutsummaryrefslogtreecommitdiffstats
path: root/lib/klist.c
diff options
context:
space:
mode:
authorTejun Heo <tj@kernel.org>2008-08-25 13:50:16 -0400
committerJens Axboe <jens.axboe@oracle.com>2008-10-09 02:56:04 -0400
commita1ed5b0cffe4b16a93a6a3390e8cee0fbef94f86 (patch)
tree1f07794d793124c0ab514378d9179f595769a813 /lib/klist.c
parent710027a48ede75428cc68eaa8ae2269b1e356e2c (diff)
klist: don't iterate over deleted entries
A klist entry is kept on the list till all its current iterations are finished; however, a new iteration after deletion also iterates over deleted entries as long as their reference count stays above zero. This causes problems for cases where there are users which iterate over the list while synchronized against list manipulations and natuarally expect already deleted entries to not show up during iteration. This patch implements dead flag which gets set on deletion so that iteration can skip already deleted entries. The dead flag piggy backs on the lowest bit of knode->n_klist and only visible to klist implementation proper. While at it, drop klist_iter->i_head as it's redundant and doesn't offer anything in semantics or performance wise as klist_iter->i_klist is dereferenced on every iteration anyway. Signed-off-by: Tejun Heo <tj@kernel.org> Cc: Greg Kroah-Hartman <gregkh@suse.de> Cc: Alan Stern <stern@rowland.harvard.edu> Cc: Jens Axboe <jens.axboe@oracle.com> Signed-off-by: Jens Axboe <jens.axboe@oracle.com>
Diffstat (limited to 'lib/klist.c')
-rw-r--r--lib/klist.c96
1 files changed, 70 insertions, 26 deletions
diff --git a/lib/klist.c b/lib/klist.c
index cca37f96faa2..bbdd3015c2c7 100644
--- a/lib/klist.c
+++ b/lib/klist.c
@@ -37,6 +37,37 @@
37#include <linux/klist.h> 37#include <linux/klist.h>
38#include <linux/module.h> 38#include <linux/module.h>
39 39
40/*
41 * Use the lowest bit of n_klist to mark deleted nodes and exclude
42 * dead ones from iteration.
43 */
44#define KNODE_DEAD 1LU
45#define KNODE_KLIST_MASK ~KNODE_DEAD
46
47static struct klist *knode_klist(struct klist_node *knode)
48{
49 return (struct klist *)
50 ((unsigned long)knode->n_klist & KNODE_KLIST_MASK);
51}
52
53static bool knode_dead(struct klist_node *knode)
54{
55 return (unsigned long)knode->n_klist & KNODE_DEAD;
56}
57
58static void knode_set_klist(struct klist_node *knode, struct klist *klist)
59{
60 knode->n_klist = klist;
61 /* no knode deserves to start its life dead */
62 WARN_ON(knode_dead(knode));
63}
64
65static void knode_kill(struct klist_node *knode)
66{
67 /* and no knode should die twice ever either, see we're very humane */
68 WARN_ON(knode_dead(knode));
69 *(unsigned long *)&knode->n_klist |= KNODE_DEAD;
70}
40 71
41/** 72/**
42 * klist_init - Initialize a klist structure. 73 * klist_init - Initialize a klist structure.
@@ -79,7 +110,7 @@ static void klist_node_init(struct klist *k, struct klist_node *n)
79 INIT_LIST_HEAD(&n->n_node); 110 INIT_LIST_HEAD(&n->n_node);
80 init_completion(&n->n_removed); 111 init_completion(&n->n_removed);
81 kref_init(&n->n_ref); 112 kref_init(&n->n_ref);
82 n->n_klist = k; 113 knode_set_klist(n, k);
83 if (k->get) 114 if (k->get)
84 k->get(n); 115 k->get(n);
85} 116}
@@ -115,7 +146,7 @@ EXPORT_SYMBOL_GPL(klist_add_tail);
115 */ 146 */
116void klist_add_after(struct klist_node *n, struct klist_node *pos) 147void klist_add_after(struct klist_node *n, struct klist_node *pos)
117{ 148{
118 struct klist *k = pos->n_klist; 149 struct klist *k = knode_klist(pos);
119 150
120 klist_node_init(k, n); 151 klist_node_init(k, n);
121 spin_lock(&k->k_lock); 152 spin_lock(&k->k_lock);
@@ -131,7 +162,7 @@ EXPORT_SYMBOL_GPL(klist_add_after);
131 */ 162 */
132void klist_add_before(struct klist_node *n, struct klist_node *pos) 163void klist_add_before(struct klist_node *n, struct klist_node *pos)
133{ 164{
134 struct klist *k = pos->n_klist; 165 struct klist *k = knode_klist(pos);
135 166
136 klist_node_init(k, n); 167 klist_node_init(k, n);
137 spin_lock(&k->k_lock); 168 spin_lock(&k->k_lock);
@@ -144,9 +175,10 @@ static void klist_release(struct kref *kref)
144{ 175{
145 struct klist_node *n = container_of(kref, struct klist_node, n_ref); 176 struct klist_node *n = container_of(kref, struct klist_node, n_ref);
146 177
178 WARN_ON(!knode_dead(n));
147 list_del(&n->n_node); 179 list_del(&n->n_node);
148 complete(&n->n_removed); 180 complete(&n->n_removed);
149 n->n_klist = NULL; 181 knode_set_klist(n, NULL);
150} 182}
151 183
152static int klist_dec_and_del(struct klist_node *n) 184static int klist_dec_and_del(struct klist_node *n)
@@ -154,22 +186,29 @@ static int klist_dec_and_del(struct klist_node *n)
154 return kref_put(&n->n_ref, klist_release); 186 return kref_put(&n->n_ref, klist_release);
155} 187}
156 188
157/** 189static void klist_put(struct klist_node *n, bool kill)
158 * klist_del - Decrement the reference count of node and try to remove.
159 * @n: node we're deleting.
160 */
161void klist_del(struct klist_node *n)
162{ 190{
163 struct klist *k = n->n_klist; 191 struct klist *k = knode_klist(n);
164 void (*put)(struct klist_node *) = k->put; 192 void (*put)(struct klist_node *) = k->put;
165 193
166 spin_lock(&k->k_lock); 194 spin_lock(&k->k_lock);
195 if (kill)
196 knode_kill(n);
167 if (!klist_dec_and_del(n)) 197 if (!klist_dec_and_del(n))
168 put = NULL; 198 put = NULL;
169 spin_unlock(&k->k_lock); 199 spin_unlock(&k->k_lock);
170 if (put) 200 if (put)
171 put(n); 201 put(n);
172} 202}
203
204/**
205 * klist_del - Decrement the reference count of node and try to remove.
206 * @n: node we're deleting.
207 */
208void klist_del(struct klist_node *n)
209{
210 klist_put(n, true);
211}
173EXPORT_SYMBOL_GPL(klist_del); 212EXPORT_SYMBOL_GPL(klist_del);
174 213
175/** 214/**
@@ -206,7 +245,6 @@ void klist_iter_init_node(struct klist *k, struct klist_iter *i,
206 struct klist_node *n) 245 struct klist_node *n)
207{ 246{
208 i->i_klist = k; 247 i->i_klist = k;
209 i->i_head = &k->k_list;
210 i->i_cur = n; 248 i->i_cur = n;
211 if (n) 249 if (n)
212 kref_get(&n->n_ref); 250 kref_get(&n->n_ref);
@@ -237,7 +275,7 @@ EXPORT_SYMBOL_GPL(klist_iter_init);
237void klist_iter_exit(struct klist_iter *i) 275void klist_iter_exit(struct klist_iter *i)
238{ 276{
239 if (i->i_cur) { 277 if (i->i_cur) {
240 klist_del(i->i_cur); 278 klist_put(i->i_cur, false);
241 i->i_cur = NULL; 279 i->i_cur = NULL;
242 } 280 }
243} 281}
@@ -258,27 +296,33 @@ static struct klist_node *to_klist_node(struct list_head *n)
258 */ 296 */
259struct klist_node *klist_next(struct klist_iter *i) 297struct klist_node *klist_next(struct klist_iter *i)
260{ 298{
261 struct list_head *next;
262 struct klist_node *lnode = i->i_cur;
263 struct klist_node *knode = NULL;
264 void (*put)(struct klist_node *) = i->i_klist->put; 299 void (*put)(struct klist_node *) = i->i_klist->put;
300 struct klist_node *last = i->i_cur;
301 struct klist_node *next;
265 302
266 spin_lock(&i->i_klist->k_lock); 303 spin_lock(&i->i_klist->k_lock);
267 if (lnode) { 304
268 next = lnode->n_node.next; 305 if (last) {
269 if (!klist_dec_and_del(lnode)) 306 next = to_klist_node(last->n_node.next);
307 if (!klist_dec_and_del(last))
270 put = NULL; 308 put = NULL;
271 } else 309 } else
272 next = i->i_head->next; 310 next = to_klist_node(i->i_klist->k_list.next);
273 311
274 if (next != i->i_head) { 312 i->i_cur = NULL;
275 knode = to_klist_node(next); 313 while (next != to_klist_node(&i->i_klist->k_list)) {
276 kref_get(&knode->n_ref); 314 if (likely(!knode_dead(next))) {
315 kref_get(&next->n_ref);
316 i->i_cur = next;
317 break;
318 }
319 next = to_klist_node(next->n_node.next);
277 } 320 }
278 i->i_cur = knode; 321
279 spin_unlock(&i->i_klist->k_lock); 322 spin_unlock(&i->i_klist->k_lock);
280 if (put && lnode) 323
281 put(lnode); 324 if (put && last)
282 return knode; 325 put(last);
326 return i->i_cur;
283} 327}
284EXPORT_SYMBOL_GPL(klist_next); 328EXPORT_SYMBOL_GPL(klist_next);