9a19fea4 |
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. |
45 | */ |
46 | |
47 | void klist_init(struct klist * k) |
48 | { |
49 | INIT_LIST_HEAD(&k->k_list); |
50 | spin_lock_init(&k->k_lock); |
51 | } |
52 | |
53 | EXPORT_SYMBOL_GPL(klist_init); |
54 | |
55 | |
56 | static void add_head(struct klist * k, struct klist_node * n) |
57 | { |
58 | spin_lock(&k->k_lock); |
59 | list_add(&n->n_node, &k->k_list); |
60 | spin_unlock(&k->k_lock); |
61 | } |
62 | |
63 | static void add_tail(struct klist * k, struct klist_node * n) |
64 | { |
65 | spin_lock(&k->k_lock); |
66 | list_add_tail(&n->n_node, &k->k_list); |
67 | spin_unlock(&k->k_lock); |
68 | } |
69 | |
70 | |
71 | static void klist_node_init(struct klist * k, struct klist_node * n) |
72 | { |
73 | INIT_LIST_HEAD(&n->n_node); |
74 | init_completion(&n->n_removed); |
75 | kref_init(&n->n_ref); |
76 | n->n_klist = k; |
77 | } |
78 | |
79 | |
80 | /** |
81 | * klist_add_head - Initialize a klist_node and add it to front. |
82 | * @k: klist it's going on. |
83 | * @n: node we're adding. |
84 | */ |
85 | |
86 | void klist_add_head(struct klist * k, struct klist_node * n) |
87 | { |
88 | klist_node_init(k, n); |
89 | add_head(k, n); |
90 | } |
91 | |
92 | EXPORT_SYMBOL_GPL(klist_add_head); |
93 | |
94 | |
95 | /** |
96 | * klist_add_tail - Initialize a klist_node and add it to back. |
97 | * @k: klist it's going on. |
98 | * @n: node we're adding. |
99 | */ |
100 | |
101 | void klist_add_tail(struct klist * k, struct klist_node * n) |
102 | { |
103 | klist_node_init(k, n); |
104 | add_tail(k, n); |
105 | } |
106 | |
107 | EXPORT_SYMBOL_GPL(klist_add_tail); |
108 | |
109 | |
110 | static void klist_release(struct kref * kref) |
111 | { |
112 | struct klist_node * n = container_of(kref, struct klist_node, n_ref); |
113 | list_del(&n->n_node); |
114 | complete(&n->n_removed); |
8b0c250b |
115 | n->n_klist = NULL; |
9a19fea4 |
116 | } |
117 | |
118 | static int klist_dec_and_del(struct klist_node * n) |
119 | { |
120 | return kref_put(&n->n_ref, klist_release); |
121 | } |
122 | |
123 | |
124 | /** |
125 | * klist_del - Decrement the reference count of node and try to remove. |
126 | * @n: node we're deleting. |
127 | */ |
128 | |
129 | void klist_del(struct klist_node * n) |
130 | { |
131 | struct klist * k = n->n_klist; |
132 | |
133 | spin_lock(&k->k_lock); |
134 | klist_dec_and_del(n); |
135 | spin_unlock(&k->k_lock); |
136 | } |
137 | |
138 | EXPORT_SYMBOL_GPL(klist_del); |
139 | |
140 | |
141 | /** |
142 | * klist_remove - Decrement the refcount of node and wait for it to go away. |
143 | * @n: node we're removing. |
144 | */ |
145 | |
146 | void klist_remove(struct klist_node * n) |
147 | { |
0293a509 |
148 | struct klist * k = n->n_klist; |
149 | spin_lock(&k->k_lock); |
9a19fea4 |
150 | klist_dec_and_del(n); |
0293a509 |
151 | spin_unlock(&k->k_lock); |
9a19fea4 |
152 | wait_for_completion(&n->n_removed); |
153 | } |
154 | |
155 | EXPORT_SYMBOL_GPL(klist_remove); |
156 | |
157 | |
8b0c250b |
158 | /** |
159 | * klist_node_attached - Say whether a node is bound to a list or not. |
160 | * @n: Node that we're testing. |
161 | */ |
162 | |
163 | int klist_node_attached(struct klist_node * n) |
164 | { |
165 | return (n->n_klist != NULL); |
166 | } |
167 | |
168 | EXPORT_SYMBOL_GPL(klist_node_attached); |
169 | |
170 | |
9a19fea4 |
171 | /** |
172 | * klist_iter_init_node - Initialize a klist_iter structure. |
173 | * @k: klist we're iterating. |
174 | * @i: klist_iter we're filling. |
175 | * @n: node to start with. |
176 | * |
177 | * Similar to klist_iter_init(), but starts the action off with @n, |
178 | * instead of with the list head. |
179 | */ |
180 | |
181 | void klist_iter_init_node(struct klist * k, struct klist_iter * i, struct klist_node * n) |
182 | { |
183 | i->i_klist = k; |
184 | i->i_head = &k->k_list; |
185 | i->i_cur = n; |
186 | } |
187 | |
188 | EXPORT_SYMBOL_GPL(klist_iter_init_node); |
189 | |
190 | |
191 | /** |
192 | * klist_iter_init - Iniitalize a klist_iter structure. |
193 | * @k: klist we're iterating. |
194 | * @i: klist_iter structure we're filling. |
195 | * |
196 | * Similar to klist_iter_init_node(), but start with the list head. |
197 | */ |
198 | |
199 | void klist_iter_init(struct klist * k, struct klist_iter * i) |
200 | { |
201 | klist_iter_init_node(k, i, NULL); |
202 | } |
203 | |
204 | EXPORT_SYMBOL_GPL(klist_iter_init); |
205 | |
206 | |
207 | /** |
208 | * klist_iter_exit - Finish a list iteration. |
209 | * @i: Iterator structure. |
210 | * |
211 | * Must be called when done iterating over list, as it decrements the |
212 | * refcount of the current node. Necessary in case iteration exited before |
213 | * the end of the list was reached, and always good form. |
214 | */ |
215 | |
216 | void klist_iter_exit(struct klist_iter * i) |
217 | { |
218 | if (i->i_cur) { |
219 | klist_del(i->i_cur); |
220 | i->i_cur = NULL; |
221 | } |
222 | } |
223 | |
224 | EXPORT_SYMBOL_GPL(klist_iter_exit); |
225 | |
226 | |
227 | static struct klist_node * to_klist_node(struct list_head * n) |
228 | { |
229 | return container_of(n, struct klist_node, n_node); |
230 | } |
231 | |
232 | |
233 | /** |
234 | * klist_next - Ante up next node in list. |
235 | * @i: Iterator structure. |
236 | * |
237 | * First grab list lock. Decrement the reference count of the previous |
238 | * node, if there was one. Grab the next node, increment its reference |
239 | * count, drop the lock, and return that next node. |
240 | */ |
241 | |
242 | struct klist_node * klist_next(struct klist_iter * i) |
243 | { |
244 | struct list_head * next; |
245 | struct klist_node * knode = NULL; |
246 | |
247 | spin_lock(&i->i_klist->k_lock); |
248 | if (i->i_cur) { |
249 | next = i->i_cur->n_node.next; |
250 | klist_dec_and_del(i->i_cur); |
251 | } else |
252 | next = i->i_head->next; |
253 | |
254 | if (next != i->i_head) { |
255 | knode = to_klist_node(next); |
256 | kref_get(&knode->n_ref); |
257 | } |
258 | i->i_cur = knode; |
259 | spin_unlock(&i->i_klist->k_lock); |
260 | return knode; |
261 | } |
262 | |
263 | EXPORT_SYMBOL_GPL(klist_next); |
8b0c250b |
264 | |
265 | |