aboutsummaryrefslogtreecommitdiffstats
path: root/lib/klist.c
diff options
context:
space:
mode:
Diffstat (limited to 'lib/klist.c')
-rw-r--r--lib/klist.c206
1 files changed, 85 insertions, 121 deletions
diff --git a/lib/klist.c b/lib/klist.c
index ebba9488046e..cca37f96faa2 100644
--- a/lib/klist.c
+++ b/lib/klist.c
@@ -1,38 +1,37 @@
1/* 1/*
2 * klist.c - Routines for manipulating klists. 2 * klist.c - Routines for manipulating klists.
3 * 3 *
4 * Copyright (C) 2005 Patrick Mochel
4 * 5 *
5 * This klist interface provides a couple of structures that wrap around 6 * This file is released under the GPL v2.
6 * struct list_head to provide explicit list "head" (struct klist) and
7 * list "node" (struct klist_node) objects. For struct klist, a spinlock
8 * is included that protects access to the actual list itself. struct
9 * klist_node provides a pointer to the klist that owns it and a kref
10 * reference count that indicates the number of current users of that node
11 * in the list.
12 * 7 *
13 * The entire point is to provide an interface for iterating over a list 8 * This klist interface provides a couple of structures that wrap around
14 * that is safe and allows for modification of the list during the 9 * struct list_head to provide explicit list "head" (struct klist) and list
15 * iteration (e.g. insertion and removal), including modification of the 10 * "node" (struct klist_node) objects. For struct klist, a spinlock is
16 * current node on the list. 11 * included that protects access to the actual list itself. struct
12 * klist_node provides a pointer to the klist that owns it and a kref
13 * reference count that indicates the number of current users of that node
14 * in the list.
17 * 15 *
18 * It works using a 3rd object type - struct klist_iter - that is declared 16 * The entire point is to provide an interface for iterating over a list
19 * and initialized before an iteration. klist_next() is used to acquire the 17 * that is safe and allows for modification of the list during the
20 * next element in the list. It returns NULL if there are no more items. 18 * iteration (e.g. insertion and removal), including modification of the
21 * Internally, that routine takes the klist's lock, decrements the reference 19 * current node on the list.
22 * count of the previous klist_node and increments the count of the next
23 * klist_node. It then drops the lock and returns.
24 * 20 *
25 * There are primitives for adding and removing nodes to/from a klist. 21 * It works using a 3rd object type - struct klist_iter - that is declared
26 * When deleting, klist_del() will simply decrement the reference count. 22 * and initialized before an iteration. klist_next() is used to acquire the
27 * Only when the count goes to 0 is the node removed from the list. 23 * next element in the list. It returns NULL if there are no more items.
28 * klist_remove() will try to delete the node from the list and block 24 * Internally, that routine takes the klist's lock, decrements the
29 * until it is actually removed. This is useful for objects (like devices) 25 * reference count of the previous klist_node and increments the count of
30 * that have been removed from the system and must be freed (but must wait 26 * the next klist_node. It then drops the lock and returns.
31 * until all accessors have finished).
32 * 27 *
33 * Copyright (C) 2005 Patrick Mochel 28 * There are primitives for adding and removing nodes to/from a klist.
34 * 29 * When deleting, klist_del() will simply decrement the reference count.
35 * This file is released under the GPL v2. 30 * Only when the count goes to 0 is the node removed from the list.
31 * klist_remove() will try to delete the node from the list and block until
32 * it is actually removed. This is useful for objects (like devices) that
33 * have been removed from the system and must be freed (but must wait until
34 * all accessors have finished).
36 */ 35 */
37 36
38#include <linux/klist.h> 37#include <linux/klist.h>
@@ -40,10 +39,10 @@
40 39
41 40
42/** 41/**
43 * klist_init - Initialize a klist structure. 42 * klist_init - Initialize a klist structure.
44 * @k: The klist we're initializing. 43 * @k: The klist we're initializing.
45 * @get: The get function for the embedding object (NULL if none) 44 * @get: The get function for the embedding object (NULL if none)
46 * @put: The put function for the embedding object (NULL if none) 45 * @put: The put function for the embedding object (NULL if none)
47 * 46 *
48 * Initialises the klist structure. If the klist_node structures are 47 * Initialises the klist structure. If the klist_node structures are
49 * going to be embedded in refcounted objects (necessary for safe 48 * going to be embedded in refcounted objects (necessary for safe
@@ -51,8 +50,7 @@
51 * functions that take and release references on the embedding 50 * functions that take and release references on the embedding
52 * objects. 51 * objects.
53 */ 52 */
54 53void klist_init(struct klist *k, void (*get)(struct klist_node *),
55void klist_init(struct klist * k, void (*get)(struct klist_node *),
56 void (*put)(struct klist_node *)) 54 void (*put)(struct klist_node *))
57{ 55{
58 INIT_LIST_HEAD(&k->k_list); 56 INIT_LIST_HEAD(&k->k_list);
@@ -60,26 +58,23 @@ void klist_init(struct klist * k, void (*get)(struct klist_node *),
60 k->get = get; 58 k->get = get;
61 k->put = put; 59 k->put = put;
62} 60}
63
64EXPORT_SYMBOL_GPL(klist_init); 61EXPORT_SYMBOL_GPL(klist_init);
65 62
66 63static void add_head(struct klist *k, struct klist_node *n)
67static void add_head(struct klist * k, struct klist_node * n)
68{ 64{
69 spin_lock(&k->k_lock); 65 spin_lock(&k->k_lock);
70 list_add(&n->n_node, &k->k_list); 66 list_add(&n->n_node, &k->k_list);
71 spin_unlock(&k->k_lock); 67 spin_unlock(&k->k_lock);
72} 68}
73 69
74static void add_tail(struct klist * k, struct klist_node * n) 70static void add_tail(struct klist *k, struct klist_node *n)
75{ 71{
76 spin_lock(&k->k_lock); 72 spin_lock(&k->k_lock);
77 list_add_tail(&n->n_node, &k->k_list); 73 list_add_tail(&n->n_node, &k->k_list);
78 spin_unlock(&k->k_lock); 74 spin_unlock(&k->k_lock);
79} 75}
80 76
81 77static void klist_node_init(struct klist *k, struct klist_node *n)
82static void klist_node_init(struct klist * k, struct klist_node * n)
83{ 78{
84 INIT_LIST_HEAD(&n->n_node); 79 INIT_LIST_HEAD(&n->n_node);
85 init_completion(&n->n_removed); 80 init_completion(&n->n_removed);
@@ -89,37 +84,30 @@ static void klist_node_init(struct klist * k, struct klist_node * n)
89 k->get(n); 84 k->get(n);
90} 85}
91 86
92
93/** 87/**
94 * klist_add_head - Initialize a klist_node and add it to front. 88 * klist_add_head - Initialize a klist_node and add it to front.
95 * @n: node we're adding. 89 * @n: node we're adding.
96 * @k: klist it's going on. 90 * @k: klist it's going on.
97 */ 91 */
98 92void klist_add_head(struct klist_node *n, struct klist *k)
99void klist_add_head(struct klist_node * n, struct klist * k)
100{ 93{
101 klist_node_init(k, n); 94 klist_node_init(k, n);
102 add_head(k, n); 95 add_head(k, n);
103} 96}
104
105EXPORT_SYMBOL_GPL(klist_add_head); 97EXPORT_SYMBOL_GPL(klist_add_head);
106 98
107
108/** 99/**
109 * klist_add_tail - Initialize a klist_node and add it to back. 100 * klist_add_tail - Initialize a klist_node and add it to back.
110 * @n: node we're adding. 101 * @n: node we're adding.
111 * @k: klist it's going on. 102 * @k: klist it's going on.
112 */ 103 */
113 104void klist_add_tail(struct klist_node *n, struct klist *k)
114void klist_add_tail(struct klist_node * n, struct klist * k)
115{ 105{
116 klist_node_init(k, n); 106 klist_node_init(k, n);
117 add_tail(k, n); 107 add_tail(k, n);
118} 108}
119
120EXPORT_SYMBOL_GPL(klist_add_tail); 109EXPORT_SYMBOL_GPL(klist_add_tail);
121 110
122
123/** 111/**
124 * klist_add_after - Init a klist_node and add it after an existing node 112 * klist_add_after - Init a klist_node and add it after an existing node
125 * @n: node we're adding. 113 * @n: node we're adding.
@@ -152,30 +140,27 @@ void klist_add_before(struct klist_node *n, struct klist_node *pos)
152} 140}
153EXPORT_SYMBOL_GPL(klist_add_before); 141EXPORT_SYMBOL_GPL(klist_add_before);
154 142
155 143static void klist_release(struct kref *kref)
156static void klist_release(struct kref * kref)
157{ 144{
158 struct klist_node * n = container_of(kref, struct klist_node, n_ref); 145 struct klist_node *n = container_of(kref, struct klist_node, n_ref);
159 146
160 list_del(&n->n_node); 147 list_del(&n->n_node);
161 complete(&n->n_removed); 148 complete(&n->n_removed);
162 n->n_klist = NULL; 149 n->n_klist = NULL;
163} 150}
164 151
165static int klist_dec_and_del(struct klist_node * n) 152static int klist_dec_and_del(struct klist_node *n)
166{ 153{
167 return kref_put(&n->n_ref, klist_release); 154 return kref_put(&n->n_ref, klist_release);
168} 155}
169 156
170
171/** 157/**
172 * klist_del - Decrement the reference count of node and try to remove. 158 * klist_del - Decrement the reference count of node and try to remove.
173 * @n: node we're deleting. 159 * @n: node we're deleting.
174 */ 160 */
175 161void klist_del(struct klist_node *n)
176void klist_del(struct klist_node * n)
177{ 162{
178 struct klist * k = n->n_klist; 163 struct klist *k = n->n_klist;
179 void (*put)(struct klist_node *) = k->put; 164 void (*put)(struct klist_node *) = k->put;
180 165
181 spin_lock(&k->k_lock); 166 spin_lock(&k->k_lock);
@@ -185,48 +170,40 @@ void klist_del(struct klist_node * n)
185 if (put) 170 if (put)
186 put(n); 171 put(n);
187} 172}
188
189EXPORT_SYMBOL_GPL(klist_del); 173EXPORT_SYMBOL_GPL(klist_del);
190 174
191
192/** 175/**
193 * klist_remove - Decrement the refcount of node and wait for it to go away. 176 * klist_remove - Decrement the refcount of node and wait for it to go away.
194 * @n: node we're removing. 177 * @n: node we're removing.
195 */ 178 */
196 179void klist_remove(struct klist_node *n)
197void klist_remove(struct klist_node * n)
198{ 180{
199 klist_del(n); 181 klist_del(n);
200 wait_for_completion(&n->n_removed); 182 wait_for_completion(&n->n_removed);
201} 183}
202
203EXPORT_SYMBOL_GPL(klist_remove); 184EXPORT_SYMBOL_GPL(klist_remove);
204 185
205
206/** 186/**
207 * klist_node_attached - Say whether a node is bound to a list or not. 187 * klist_node_attached - Say whether a node is bound to a list or not.
208 * @n: Node that we're testing. 188 * @n: Node that we're testing.
209 */ 189 */
210 190int klist_node_attached(struct klist_node *n)
211int klist_node_attached(struct klist_node * n)
212{ 191{
213 return (n->n_klist != NULL); 192 return (n->n_klist != NULL);
214} 193}
215
216EXPORT_SYMBOL_GPL(klist_node_attached); 194EXPORT_SYMBOL_GPL(klist_node_attached);
217 195
218
219/** 196/**
220 * klist_iter_init_node - Initialize a klist_iter structure. 197 * klist_iter_init_node - Initialize a klist_iter structure.
221 * @k: klist we're iterating. 198 * @k: klist we're iterating.
222 * @i: klist_iter we're filling. 199 * @i: klist_iter we're filling.
223 * @n: node to start with. 200 * @n: node to start with.
224 * 201 *
225 * Similar to klist_iter_init(), but starts the action off with @n, 202 * Similar to klist_iter_init(), but starts the action off with @n,
226 * instead of with the list head. 203 * instead of with the list head.
227 */ 204 */
228 205void klist_iter_init_node(struct klist *k, struct klist_iter *i,
229void klist_iter_init_node(struct klist * k, struct klist_iter * i, struct klist_node * n) 206 struct klist_node *n)
230{ 207{
231 i->i_klist = k; 208 i->i_klist = k;
232 i->i_head = &k->k_list; 209 i->i_head = &k->k_list;
@@ -234,66 +211,56 @@ void klist_iter_init_node(struct klist * k, struct klist_iter * i, struct klist_
234 if (n) 211 if (n)
235 kref_get(&n->n_ref); 212 kref_get(&n->n_ref);
236} 213}
237
238EXPORT_SYMBOL_GPL(klist_iter_init_node); 214EXPORT_SYMBOL_GPL(klist_iter_init_node);
239 215
240
241/** 216/**
242 * klist_iter_init - Iniitalize a klist_iter structure. 217 * klist_iter_init - Iniitalize a klist_iter structure.
243 * @k: klist we're iterating. 218 * @k: klist we're iterating.
244 * @i: klist_iter structure we're filling. 219 * @i: klist_iter structure we're filling.
245 * 220 *
246 * Similar to klist_iter_init_node(), but start with the list head. 221 * Similar to klist_iter_init_node(), but start with the list head.
247 */ 222 */
248 223void klist_iter_init(struct klist *k, struct klist_iter *i)
249void klist_iter_init(struct klist * k, struct klist_iter * i)
250{ 224{
251 klist_iter_init_node(k, i, NULL); 225 klist_iter_init_node(k, i, NULL);
252} 226}
253
254EXPORT_SYMBOL_GPL(klist_iter_init); 227EXPORT_SYMBOL_GPL(klist_iter_init);
255 228
256
257/** 229/**
258 * klist_iter_exit - Finish a list iteration. 230 * klist_iter_exit - Finish a list iteration.
259 * @i: Iterator structure. 231 * @i: Iterator structure.
260 * 232 *
261 * Must be called when done iterating over list, as it decrements the 233 * Must be called when done iterating over list, as it decrements the
262 * refcount of the current node. Necessary in case iteration exited before 234 * refcount of the current node. Necessary in case iteration exited before
263 * the end of the list was reached, and always good form. 235 * the end of the list was reached, and always good form.
264 */ 236 */
265 237void klist_iter_exit(struct klist_iter *i)
266void klist_iter_exit(struct klist_iter * i)
267{ 238{
268 if (i->i_cur) { 239 if (i->i_cur) {
269 klist_del(i->i_cur); 240 klist_del(i->i_cur);
270 i->i_cur = NULL; 241 i->i_cur = NULL;
271 } 242 }
272} 243}
273
274EXPORT_SYMBOL_GPL(klist_iter_exit); 244EXPORT_SYMBOL_GPL(klist_iter_exit);
275 245
276 246static struct klist_node *to_klist_node(struct list_head *n)
277static struct klist_node * to_klist_node(struct list_head * n)
278{ 247{
279 return container_of(n, struct klist_node, n_node); 248 return container_of(n, struct klist_node, n_node);
280} 249}
281 250
282
283/** 251/**
284 * klist_next - Ante up next node in list. 252 * klist_next - Ante up next node in list.
285 * @i: Iterator structure. 253 * @i: Iterator structure.
286 * 254 *
287 * First grab list lock. Decrement the reference count of the previous 255 * First grab list lock. Decrement the reference count of the previous
288 * node, if there was one. Grab the next node, increment its reference 256 * node, if there was one. Grab the next node, increment its reference
289 * count, drop the lock, and return that next node. 257 * count, drop the lock, and return that next node.
290 */ 258 */
291 259struct klist_node *klist_next(struct klist_iter *i)
292struct klist_node * klist_next(struct klist_iter * i)
293{ 260{
294 struct list_head * next; 261 struct list_head *next;
295 struct klist_node * lnode = i->i_cur; 262 struct klist_node *lnode = i->i_cur;
296 struct klist_node * knode = NULL; 263 struct klist_node *knode = NULL;
297 void (*put)(struct klist_node *) = i->i_klist->put; 264 void (*put)(struct klist_node *) = i->i_klist->put;
298 265
299 spin_lock(&i->i_klist->k_lock); 266 spin_lock(&i->i_klist->k_lock);
@@ -314,7 +281,4 @@ struct klist_node * klist_next(struct klist_iter * i)
314 put(lnode); 281 put(lnode);
315 return knode; 282 return knode;
316} 283}
317
318EXPORT_SYMBOL_GPL(klist_next); 284EXPORT_SYMBOL_GPL(klist_next);
319
320