diff options
Diffstat (limited to 'lib/klist.c')
-rw-r--r-- | lib/klist.c | 206 |
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 | 53 | void klist_init(struct klist *k, void (*get)(struct klist_node *), | |
55 | void 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 | |||
64 | EXPORT_SYMBOL_GPL(klist_init); | 61 | EXPORT_SYMBOL_GPL(klist_init); |
65 | 62 | ||
66 | 63 | static void add_head(struct klist *k, struct klist_node *n) | |
67 | static 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 | ||
74 | static void add_tail(struct klist * k, struct klist_node * n) | 70 | static 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 | 77 | static void klist_node_init(struct klist *k, struct klist_node *n) | |
82 | static 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 | 92 | void klist_add_head(struct klist_node *n, struct klist *k) | |
99 | void 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 | |||
105 | EXPORT_SYMBOL_GPL(klist_add_head); | 97 | EXPORT_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 | 104 | void klist_add_tail(struct klist_node *n, struct klist *k) | |
114 | void 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 | |||
120 | EXPORT_SYMBOL_GPL(klist_add_tail); | 109 | EXPORT_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 | } |
153 | EXPORT_SYMBOL_GPL(klist_add_before); | 141 | EXPORT_SYMBOL_GPL(klist_add_before); |
154 | 142 | ||
155 | 143 | static void klist_release(struct kref *kref) | |
156 | static 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 | ||
165 | static int klist_dec_and_del(struct klist_node * n) | 152 | static 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 | 161 | void klist_del(struct klist_node *n) | |
176 | void 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 | |||
189 | EXPORT_SYMBOL_GPL(klist_del); | 173 | EXPORT_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 | 179 | void klist_remove(struct klist_node *n) | |
197 | void 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 | |||
203 | EXPORT_SYMBOL_GPL(klist_remove); | 184 | EXPORT_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 | 190 | int klist_node_attached(struct klist_node *n) | |
211 | int klist_node_attached(struct klist_node * n) | ||
212 | { | 191 | { |
213 | return (n->n_klist != NULL); | 192 | return (n->n_klist != NULL); |
214 | } | 193 | } |
215 | |||
216 | EXPORT_SYMBOL_GPL(klist_node_attached); | 194 | EXPORT_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 | 205 | void klist_iter_init_node(struct klist *k, struct klist_iter *i, | |
229 | void 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 | |||
238 | EXPORT_SYMBOL_GPL(klist_iter_init_node); | 214 | EXPORT_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 | 223 | void klist_iter_init(struct klist *k, struct klist_iter *i) | |
249 | void 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 | |||
254 | EXPORT_SYMBOL_GPL(klist_iter_init); | 227 | EXPORT_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 | 237 | void klist_iter_exit(struct klist_iter *i) | |
266 | void 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 | |||
274 | EXPORT_SYMBOL_GPL(klist_iter_exit); | 244 | EXPORT_SYMBOL_GPL(klist_iter_exit); |
275 | 245 | ||
276 | 246 | static struct klist_node *to_klist_node(struct list_head *n) | |
277 | static 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 | 259 | struct klist_node *klist_next(struct klist_iter *i) | |
292 | struct 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 | |||
318 | EXPORT_SYMBOL_GPL(klist_next); | 284 | EXPORT_SYMBOL_GPL(klist_next); |
319 | |||
320 | |||