]>
Commit | Line | Data |
---|---|---|
1 | // SPDX-License-Identifier: GPL-2.0-only | |
2 | /* | |
3 | * klist.c - Routines for manipulating klists. | |
4 | * | |
5 | * Copyright (C) 2005 Patrick Mochel | |
6 | * | |
7 | * This klist interface provides a couple of structures that wrap around | |
8 | * struct list_head to provide explicit list "head" (struct klist) and list | |
9 | * "node" (struct klist_node) objects. For struct klist, a spinlock is | |
10 | * included that protects access to the actual list itself. struct | |
11 | * klist_node provides a pointer to the klist that owns it and a kref | |
12 | * reference count that indicates the number of current users of that node | |
13 | * in the list. | |
14 | * | |
15 | * The entire point is to provide an interface for iterating over a list | |
16 | * that is safe and allows for modification of the list during the | |
17 | * iteration (e.g. insertion and removal), including modification of the | |
18 | * current node on the list. | |
19 | * | |
20 | * It works using a 3rd object type - struct klist_iter - that is declared | |
21 | * and initialized before an iteration. klist_next() is used to acquire the | |
22 | * next element in the list. It returns NULL if there are no more items. | |
23 | * Internally, that routine takes the klist's lock, decrements the | |
24 | * reference count of the previous klist_node and increments the count of | |
25 | * the next klist_node. It then drops the lock and returns. | |
26 | * | |
27 | * There are primitives for adding and removing nodes to/from a klist. | |
28 | * When deleting, klist_del() will simply decrement the reference count. | |
29 | * Only when the count goes to 0 is the node removed from the list. | |
30 | * klist_remove() will try to delete the node from the list and block until | |
31 | * it is actually removed. This is useful for objects (like devices) that | |
32 | * have been removed from the system and must be freed (but must wait until | |
33 | * all accessors have finished). | |
34 | */ | |
35 | ||
36 | #include <linux/klist.h> | |
37 | #include <linux/export.h> | |
38 | #include <linux/sched.h> | |
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 | ||
47 | static struct klist *knode_klist(struct klist_node *knode) | |
48 | { | |
49 | return (struct klist *) | |
50 | ((unsigned long)knode->n_klist & KNODE_KLIST_MASK); | |
51 | } | |
52 | ||
53 | static bool knode_dead(struct klist_node *knode) | |
54 | { | |
55 | return (unsigned long)knode->n_klist & KNODE_DEAD; | |
56 | } | |
57 | ||
58 | static 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 | ||
65 | static 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 | } | |
71 | ||
72 | /** | |
73 | * klist_init - Initialize a klist structure. | |
74 | * @k: The klist we're initializing. | |
75 | * @get: The get function for the embedding object (NULL if none) | |
76 | * @put: The put function for the embedding object (NULL if none) | |
77 | * | |
78 | * Initialises the klist structure. If the klist_node structures are | |
79 | * going to be embedded in refcounted objects (necessary for safe | |
80 | * deletion) then the get/put arguments are used to initialise | |
81 | * functions that take and release references on the embedding | |
82 | * objects. | |
83 | */ | |
84 | void klist_init(struct klist *k, void (*get)(struct klist_node *), | |
85 | void (*put)(struct klist_node *)) | |
86 | { | |
87 | INIT_LIST_HEAD(&k->k_list); | |
88 | spin_lock_init(&k->k_lock); | |
89 | k->get = get; | |
90 | k->put = put; | |
91 | } | |
92 | EXPORT_SYMBOL_GPL(klist_init); | |
93 | ||
94 | static void add_head(struct klist *k, struct klist_node *n) | |
95 | { | |
96 | spin_lock(&k->k_lock); | |
97 | list_add(&n->n_node, &k->k_list); | |
98 | spin_unlock(&k->k_lock); | |
99 | } | |
100 | ||
101 | static void add_tail(struct klist *k, struct klist_node *n) | |
102 | { | |
103 | spin_lock(&k->k_lock); | |
104 | list_add_tail(&n->n_node, &k->k_list); | |
105 | spin_unlock(&k->k_lock); | |
106 | } | |
107 | ||
108 | static void klist_node_init(struct klist *k, struct klist_node *n) | |
109 | { | |
110 | INIT_LIST_HEAD(&n->n_node); | |
111 | kref_init(&n->n_ref); | |
112 | knode_set_klist(n, k); | |
113 | if (k->get) | |
114 | k->get(n); | |
115 | } | |
116 | ||
117 | /** | |
118 | * klist_add_head - Initialize a klist_node and add it to front. | |
119 | * @n: node we're adding. | |
120 | * @k: klist it's going on. | |
121 | */ | |
122 | void klist_add_head(struct klist_node *n, struct klist *k) | |
123 | { | |
124 | klist_node_init(k, n); | |
125 | add_head(k, n); | |
126 | } | |
127 | EXPORT_SYMBOL_GPL(klist_add_head); | |
128 | ||
129 | /** | |
130 | * klist_add_tail - Initialize a klist_node and add it to back. | |
131 | * @n: node we're adding. | |
132 | * @k: klist it's going on. | |
133 | */ | |
134 | void klist_add_tail(struct klist_node *n, struct klist *k) | |
135 | { | |
136 | klist_node_init(k, n); | |
137 | add_tail(k, n); | |
138 | } | |
139 | EXPORT_SYMBOL_GPL(klist_add_tail); | |
140 | ||
141 | /** | |
142 | * klist_add_behind - Init a klist_node and add it after an existing node | |
143 | * @n: node we're adding. | |
144 | * @pos: node to put @n after | |
145 | */ | |
146 | void klist_add_behind(struct klist_node *n, struct klist_node *pos) | |
147 | { | |
148 | struct klist *k = knode_klist(pos); | |
149 | ||
150 | klist_node_init(k, n); | |
151 | spin_lock(&k->k_lock); | |
152 | list_add(&n->n_node, &pos->n_node); | |
153 | spin_unlock(&k->k_lock); | |
154 | } | |
155 | EXPORT_SYMBOL_GPL(klist_add_behind); | |
156 | ||
157 | /** | |
158 | * klist_add_before - Init a klist_node and add it before an existing node | |
159 | * @n: node we're adding. | |
160 | * @pos: node to put @n after | |
161 | */ | |
162 | void klist_add_before(struct klist_node *n, struct klist_node *pos) | |
163 | { | |
164 | struct klist *k = knode_klist(pos); | |
165 | ||
166 | klist_node_init(k, n); | |
167 | spin_lock(&k->k_lock); | |
168 | list_add_tail(&n->n_node, &pos->n_node); | |
169 | spin_unlock(&k->k_lock); | |
170 | } | |
171 | EXPORT_SYMBOL_GPL(klist_add_before); | |
172 | ||
173 | struct klist_waiter { | |
174 | struct list_head list; | |
175 | struct klist_node *node; | |
176 | struct task_struct *process; | |
177 | int woken; | |
178 | }; | |
179 | ||
180 | static DEFINE_SPINLOCK(klist_remove_lock); | |
181 | static LIST_HEAD(klist_remove_waiters); | |
182 | ||
183 | static void klist_release(struct kref *kref) | |
184 | { | |
185 | struct klist_waiter *waiter, *tmp; | |
186 | struct klist_node *n = container_of(kref, struct klist_node, n_ref); | |
187 | ||
188 | WARN_ON(!knode_dead(n)); | |
189 | list_del(&n->n_node); | |
190 | spin_lock(&klist_remove_lock); | |
191 | list_for_each_entry_safe(waiter, tmp, &klist_remove_waiters, list) { | |
192 | if (waiter->node != n) | |
193 | continue; | |
194 | ||
195 | list_del(&waiter->list); | |
196 | waiter->woken = 1; | |
197 | mb(); | |
198 | wake_up_process(waiter->process); | |
199 | } | |
200 | spin_unlock(&klist_remove_lock); | |
201 | knode_set_klist(n, NULL); | |
202 | } | |
203 | ||
204 | static int klist_dec_and_del(struct klist_node *n) | |
205 | { | |
206 | return kref_put(&n->n_ref, klist_release); | |
207 | } | |
208 | ||
209 | static void klist_put(struct klist_node *n, bool kill) | |
210 | { | |
211 | struct klist *k = knode_klist(n); | |
212 | void (*put)(struct klist_node *) = k->put; | |
213 | ||
214 | spin_lock(&k->k_lock); | |
215 | if (kill) | |
216 | knode_kill(n); | |
217 | if (!klist_dec_and_del(n)) | |
218 | put = NULL; | |
219 | spin_unlock(&k->k_lock); | |
220 | if (put) | |
221 | put(n); | |
222 | } | |
223 | ||
224 | /** | |
225 | * klist_del - Decrement the reference count of node and try to remove. | |
226 | * @n: node we're deleting. | |
227 | */ | |
228 | void klist_del(struct klist_node *n) | |
229 | { | |
230 | klist_put(n, true); | |
231 | } | |
232 | EXPORT_SYMBOL_GPL(klist_del); | |
233 | ||
234 | /** | |
235 | * klist_remove - Decrement the refcount of node and wait for it to go away. | |
236 | * @n: node we're removing. | |
237 | */ | |
238 | void klist_remove(struct klist_node *n) | |
239 | { | |
240 | struct klist_waiter waiter; | |
241 | ||
242 | waiter.node = n; | |
243 | waiter.process = current; | |
244 | waiter.woken = 0; | |
245 | spin_lock(&klist_remove_lock); | |
246 | list_add(&waiter.list, &klist_remove_waiters); | |
247 | spin_unlock(&klist_remove_lock); | |
248 | ||
249 | klist_del(n); | |
250 | ||
251 | for (;;) { | |
252 | set_current_state(TASK_UNINTERRUPTIBLE); | |
253 | if (waiter.woken) | |
254 | break; | |
255 | schedule(); | |
256 | } | |
257 | __set_current_state(TASK_RUNNING); | |
258 | } | |
259 | EXPORT_SYMBOL_GPL(klist_remove); | |
260 | ||
261 | /** | |
262 | * klist_node_attached - Say whether a node is bound to a list or not. | |
263 | * @n: Node that we're testing. | |
264 | */ | |
265 | int klist_node_attached(struct klist_node *n) | |
266 | { | |
267 | return (n->n_klist != NULL); | |
268 | } | |
269 | EXPORT_SYMBOL_GPL(klist_node_attached); | |
270 | ||
271 | /** | |
272 | * klist_iter_init_node - Initialize a klist_iter structure. | |
273 | * @k: klist we're iterating. | |
274 | * @i: klist_iter we're filling. | |
275 | * @n: node to start with. | |
276 | * | |
277 | * Similar to klist_iter_init(), but starts the action off with @n, | |
278 | * instead of with the list head. | |
279 | */ | |
280 | void klist_iter_init_node(struct klist *k, struct klist_iter *i, | |
281 | struct klist_node *n) | |
282 | { | |
283 | i->i_klist = k; | |
284 | i->i_cur = NULL; | |
285 | if (n && kref_get_unless_zero(&n->n_ref)) | |
286 | i->i_cur = n; | |
287 | } | |
288 | EXPORT_SYMBOL_GPL(klist_iter_init_node); | |
289 | ||
290 | /** | |
291 | * klist_iter_init - Iniitalize a klist_iter structure. | |
292 | * @k: klist we're iterating. | |
293 | * @i: klist_iter structure we're filling. | |
294 | * | |
295 | * Similar to klist_iter_init_node(), but start with the list head. | |
296 | */ | |
297 | void klist_iter_init(struct klist *k, struct klist_iter *i) | |
298 | { | |
299 | klist_iter_init_node(k, i, NULL); | |
300 | } | |
301 | EXPORT_SYMBOL_GPL(klist_iter_init); | |
302 | ||
303 | /** | |
304 | * klist_iter_exit - Finish a list iteration. | |
305 | * @i: Iterator structure. | |
306 | * | |
307 | * Must be called when done iterating over list, as it decrements the | |
308 | * refcount of the current node. Necessary in case iteration exited before | |
309 | * the end of the list was reached, and always good form. | |
310 | */ | |
311 | void klist_iter_exit(struct klist_iter *i) | |
312 | { | |
313 | if (i->i_cur) { | |
314 | klist_put(i->i_cur, false); | |
315 | i->i_cur = NULL; | |
316 | } | |
317 | } | |
318 | EXPORT_SYMBOL_GPL(klist_iter_exit); | |
319 | ||
320 | static struct klist_node *to_klist_node(struct list_head *n) | |
321 | { | |
322 | return container_of(n, struct klist_node, n_node); | |
323 | } | |
324 | ||
325 | /** | |
326 | * klist_prev - Ante up prev node in list. | |
327 | * @i: Iterator structure. | |
328 | * | |
329 | * First grab list lock. Decrement the reference count of the previous | |
330 | * node, if there was one. Grab the prev node, increment its reference | |
331 | * count, drop the lock, and return that prev node. | |
332 | */ | |
333 | struct klist_node *klist_prev(struct klist_iter *i) | |
334 | { | |
335 | void (*put)(struct klist_node *) = i->i_klist->put; | |
336 | struct klist_node *last = i->i_cur; | |
337 | struct klist_node *prev; | |
338 | unsigned long flags; | |
339 | ||
340 | spin_lock_irqsave(&i->i_klist->k_lock, flags); | |
341 | ||
342 | if (last) { | |
343 | prev = to_klist_node(last->n_node.prev); | |
344 | if (!klist_dec_and_del(last)) | |
345 | put = NULL; | |
346 | } else | |
347 | prev = to_klist_node(i->i_klist->k_list.prev); | |
348 | ||
349 | i->i_cur = NULL; | |
350 | while (prev != to_klist_node(&i->i_klist->k_list)) { | |
351 | if (likely(!knode_dead(prev))) { | |
352 | kref_get(&prev->n_ref); | |
353 | i->i_cur = prev; | |
354 | break; | |
355 | } | |
356 | prev = to_klist_node(prev->n_node.prev); | |
357 | } | |
358 | ||
359 | spin_unlock_irqrestore(&i->i_klist->k_lock, flags); | |
360 | ||
361 | if (put && last) | |
362 | put(last); | |
363 | return i->i_cur; | |
364 | } | |
365 | EXPORT_SYMBOL_GPL(klist_prev); | |
366 | ||
367 | /** | |
368 | * klist_next - Ante up next node in list. | |
369 | * @i: Iterator structure. | |
370 | * | |
371 | * First grab list lock. Decrement the reference count of the previous | |
372 | * node, if there was one. Grab the next node, increment its reference | |
373 | * count, drop the lock, and return that next node. | |
374 | */ | |
375 | struct klist_node *klist_next(struct klist_iter *i) | |
376 | { | |
377 | void (*put)(struct klist_node *) = i->i_klist->put; | |
378 | struct klist_node *last = i->i_cur; | |
379 | struct klist_node *next; | |
380 | unsigned long flags; | |
381 | ||
382 | spin_lock_irqsave(&i->i_klist->k_lock, flags); | |
383 | ||
384 | if (last) { | |
385 | next = to_klist_node(last->n_node.next); | |
386 | if (!klist_dec_and_del(last)) | |
387 | put = NULL; | |
388 | } else | |
389 | next = to_klist_node(i->i_klist->k_list.next); | |
390 | ||
391 | i->i_cur = NULL; | |
392 | while (next != to_klist_node(&i->i_klist->k_list)) { | |
393 | if (likely(!knode_dead(next))) { | |
394 | kref_get(&next->n_ref); | |
395 | i->i_cur = next; | |
396 | break; | |
397 | } | |
398 | next = to_klist_node(next->n_node.next); | |
399 | } | |
400 | ||
401 | spin_unlock_irqrestore(&i->i_klist->k_lock, flags); | |
402 | ||
403 | if (put && last) | |
404 | put(last); | |
405 | return i->i_cur; | |
406 | } | |
407 | EXPORT_SYMBOL_GPL(klist_next); |