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