Root/
Source at commit fbf123cd4cc0c097fe9a99c90109ebb2a5e94a50 created 10 years 3 months ago. By Lars-Peter Clausen, dma: jz4740: Dequeue descriptor from active list before completing it | |
---|---|
1 | /* |
2 | * klist.c - Routines for manipulating klists. |
3 | * |
4 | * Copyright (C) 2005 Patrick Mochel |
5 | * |
6 | * This file is released under the GPL v2. |
7 | * |
8 | * This klist interface provides a couple of structures that wrap around |
9 | * struct list_head to provide explicit list "head" (struct klist) and list |
10 | * "node" (struct klist_node) objects. For struct klist, a spinlock is |
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. |
15 | * |
16 | * The entire point is to provide an interface for iterating over a list |
17 | * that is safe and allows for modification of the list during the |
18 | * iteration (e.g. insertion and removal), including modification of the |
19 | * current node on the list. |
20 | * |
21 | * It works using a 3rd object type - struct klist_iter - that is declared |
22 | * and initialized before an iteration. klist_next() is used to acquire the |
23 | * next element in the list. It returns NULL if there are no more items. |
24 | * Internally, that routine takes the klist's lock, decrements the |
25 | * reference count of the previous klist_node and increments the count of |
26 | * the next klist_node. It then drops the lock and returns. |
27 | * |
28 | * There are primitives for adding and removing nodes to/from a klist. |
29 | * When deleting, klist_del() will simply decrement the reference count. |
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). |
35 | */ |
36 | |
37 | #include <linux/klist.h> |
38 | #include <linux/export.h> |
39 | #include <linux/sched.h> |
40 | |
41 | /* |
42 | * Use the lowest bit of n_klist to mark deleted nodes and exclude |
43 | * dead ones from iteration. |
44 | */ |
45 | #define KNODE_DEAD 1LU |
46 | #define KNODE_KLIST_MASK ~KNODE_DEAD |
47 | |
48 | static struct klist *knode_klist(struct klist_node *knode) |
49 | { |
50 | return (struct klist *) |
51 | ((unsigned long)knode->n_klist & KNODE_KLIST_MASK); |
52 | } |
53 | |
54 | static bool knode_dead(struct klist_node *knode) |
55 | { |
56 | return (unsigned long)knode->n_klist & KNODE_DEAD; |
57 | } |
58 | |
59 | static void knode_set_klist(struct klist_node *knode, struct klist *klist) |
60 | { |
61 | knode->n_klist = klist; |
62 | /* no knode deserves to start its life dead */ |
63 | WARN_ON(knode_dead(knode)); |
64 | } |
65 | |
66 | static void knode_kill(struct klist_node *knode) |
67 | { |
68 | /* and no knode should die twice ever either, see we're very humane */ |
69 | WARN_ON(knode_dead(knode)); |
70 | *(unsigned long *)&knode->n_klist |= KNODE_DEAD; |
71 | } |
72 | |
73 | /** |
74 | * klist_init - Initialize a klist structure. |
75 | * @k: The klist we're initializing. |
76 | * @get: The get function for the embedding object (NULL if none) |
77 | * @put: The put function for the embedding object (NULL if none) |
78 | * |
79 | * Initialises the klist structure. If the klist_node structures are |
80 | * going to be embedded in refcounted objects (necessary for safe |
81 | * deletion) then the get/put arguments are used to initialise |
82 | * functions that take and release references on the embedding |
83 | * objects. |
84 | */ |
85 | void klist_init(struct klist *k, void (*get)(struct klist_node *), |
86 | void (*put)(struct klist_node *)) |
87 | { |
88 | INIT_LIST_HEAD(&k->k_list); |
89 | spin_lock_init(&k->k_lock); |
90 | k->get = get; |
91 | k->put = put; |
92 | } |
93 | EXPORT_SYMBOL_GPL(klist_init); |
94 | |
95 | static void add_head(struct klist *k, struct klist_node *n) |
96 | { |
97 | spin_lock(&k->k_lock); |
98 | list_add(&n->n_node, &k->k_list); |
99 | spin_unlock(&k->k_lock); |
100 | } |
101 | |
102 | static void add_tail(struct klist *k, struct klist_node *n) |
103 | { |
104 | spin_lock(&k->k_lock); |
105 | list_add_tail(&n->n_node, &k->k_list); |
106 | spin_unlock(&k->k_lock); |
107 | } |
108 | |
109 | static void klist_node_init(struct klist *k, struct klist_node *n) |
110 | { |
111 | INIT_LIST_HEAD(&n->n_node); |
112 | kref_init(&n->n_ref); |
113 | knode_set_klist(n, k); |
114 | if (k->get) |
115 | k->get(n); |
116 | } |
117 | |
118 | /** |
119 | * klist_add_head - Initialize a klist_node and add it to front. |
120 | * @n: node we're adding. |
121 | * @k: klist it's going on. |
122 | */ |
123 | void klist_add_head(struct klist_node *n, struct klist *k) |
124 | { |
125 | klist_node_init(k, n); |
126 | add_head(k, n); |
127 | } |
128 | EXPORT_SYMBOL_GPL(klist_add_head); |
129 | |
130 | /** |
131 | * klist_add_tail - Initialize a klist_node and add it to back. |
132 | * @n: node we're adding. |
133 | * @k: klist it's going on. |
134 | */ |
135 | void klist_add_tail(struct klist_node *n, struct klist *k) |
136 | { |
137 | klist_node_init(k, n); |
138 | add_tail(k, n); |
139 | } |
140 | EXPORT_SYMBOL_GPL(klist_add_tail); |
141 | |
142 | /** |
143 | * klist_add_after - Init a klist_node and add it after an existing node |
144 | * @n: node we're adding. |
145 | * @pos: node to put @n after |
146 | */ |
147 | void klist_add_after(struct klist_node *n, struct klist_node *pos) |
148 | { |
149 | struct klist *k = knode_klist(pos); |
150 | |
151 | klist_node_init(k, n); |
152 | spin_lock(&k->k_lock); |
153 | list_add(&n->n_node, &pos->n_node); |
154 | spin_unlock(&k->k_lock); |
155 | } |
156 | EXPORT_SYMBOL_GPL(klist_add_after); |
157 | |
158 | /** |
159 | * klist_add_before - Init a klist_node and add it before an existing node |
160 | * @n: node we're adding. |
161 | * @pos: node to put @n after |
162 | */ |
163 | void klist_add_before(struct klist_node *n, struct klist_node *pos) |
164 | { |
165 | struct klist *k = knode_klist(pos); |
166 | |
167 | klist_node_init(k, n); |
168 | spin_lock(&k->k_lock); |
169 | list_add_tail(&n->n_node, &pos->n_node); |
170 | spin_unlock(&k->k_lock); |
171 | } |
172 | EXPORT_SYMBOL_GPL(klist_add_before); |
173 | |
174 | struct klist_waiter { |
175 | struct list_head list; |
176 | struct klist_node *node; |
177 | struct task_struct *process; |
178 | int woken; |
179 | }; |
180 | |
181 | static DEFINE_SPINLOCK(klist_remove_lock); |
182 | static LIST_HEAD(klist_remove_waiters); |
183 | |
184 | static void klist_release(struct kref *kref) |
185 | { |
186 | struct klist_waiter *waiter, *tmp; |
187 | struct klist_node *n = container_of(kref, struct klist_node, n_ref); |
188 | |
189 | WARN_ON(!knode_dead(n)); |
190 | list_del(&n->n_node); |
191 | spin_lock(&klist_remove_lock); |
192 | list_for_each_entry_safe(waiter, tmp, &klist_remove_waiters, list) { |
193 | if (waiter->node != n) |
194 | continue; |
195 | |
196 | list_del(&waiter->list); |
197 | waiter->woken = 1; |
198 | mb(); |
199 | wake_up_process(waiter->process); |
200 | } |
201 | spin_unlock(&klist_remove_lock); |
202 | knode_set_klist(n, NULL); |
203 | } |
204 | |
205 | static int klist_dec_and_del(struct klist_node *n) |
206 | { |
207 | return kref_put(&n->n_ref, klist_release); |
208 | } |
209 | |
210 | static void klist_put(struct klist_node *n, bool kill) |
211 | { |
212 | struct klist *k = knode_klist(n); |
213 | void (*put)(struct klist_node *) = k->put; |
214 | |
215 | spin_lock(&k->k_lock); |
216 | if (kill) |
217 | knode_kill(n); |
218 | if (!klist_dec_and_del(n)) |
219 | put = NULL; |
220 | spin_unlock(&k->k_lock); |
221 | if (put) |
222 | put(n); |
223 | } |
224 | |
225 | /** |
226 | * klist_del - Decrement the reference count of node and try to remove. |
227 | * @n: node we're deleting. |
228 | */ |
229 | void klist_del(struct klist_node *n) |
230 | { |
231 | klist_put(n, true); |
232 | } |
233 | EXPORT_SYMBOL_GPL(klist_del); |
234 | |
235 | /** |
236 | * klist_remove - Decrement the refcount of node and wait for it to go away. |
237 | * @n: node we're removing. |
238 | */ |
239 | void klist_remove(struct klist_node *n) |
240 | { |
241 | struct klist_waiter waiter; |
242 | |
243 | waiter.node = n; |
244 | waiter.process = current; |
245 | waiter.woken = 0; |
246 | spin_lock(&klist_remove_lock); |
247 | list_add(&waiter.list, &klist_remove_waiters); |
248 | spin_unlock(&klist_remove_lock); |
249 | |
250 | klist_del(n); |
251 | |
252 | for (;;) { |
253 | set_current_state(TASK_UNINTERRUPTIBLE); |
254 | if (waiter.woken) |
255 | break; |
256 | schedule(); |
257 | } |
258 | __set_current_state(TASK_RUNNING); |
259 | } |
260 | EXPORT_SYMBOL_GPL(klist_remove); |
261 | |
262 | /** |
263 | * klist_node_attached - Say whether a node is bound to a list or not. |
264 | * @n: Node that we're testing. |
265 | */ |
266 | int klist_node_attached(struct klist_node *n) |
267 | { |
268 | return (n->n_klist != NULL); |
269 | } |
270 | EXPORT_SYMBOL_GPL(klist_node_attached); |
271 | |
272 | /** |
273 | * klist_iter_init_node - Initialize a klist_iter structure. |
274 | * @k: klist we're iterating. |
275 | * @i: klist_iter we're filling. |
276 | * @n: node to start with. |
277 | * |
278 | * Similar to klist_iter_init(), but starts the action off with @n, |
279 | * instead of with the list head. |
280 | */ |
281 | void klist_iter_init_node(struct klist *k, struct klist_iter *i, |
282 | struct klist_node *n) |
283 | { |
284 | i->i_klist = k; |
285 | i->i_cur = n; |
286 | if (n) |
287 | kref_get(&n->n_ref); |
288 | } |
289 | EXPORT_SYMBOL_GPL(klist_iter_init_node); |
290 | |
291 | /** |
292 | * klist_iter_init - Iniitalize a klist_iter structure. |
293 | * @k: klist we're iterating. |
294 | * @i: klist_iter structure we're filling. |
295 | * |
296 | * Similar to klist_iter_init_node(), but start with the list head. |
297 | */ |
298 | void klist_iter_init(struct klist *k, struct klist_iter *i) |
299 | { |
300 | klist_iter_init_node(k, i, NULL); |
301 | } |
302 | EXPORT_SYMBOL_GPL(klist_iter_init); |
303 | |
304 | /** |
305 | * klist_iter_exit - Finish a list iteration. |
306 | * @i: Iterator structure. |
307 | * |
308 | * Must be called when done iterating over list, as it decrements the |
309 | * refcount of the current node. Necessary in case iteration exited before |
310 | * the end of the list was reached, and always good form. |
311 | */ |
312 | void klist_iter_exit(struct klist_iter *i) |
313 | { |
314 | if (i->i_cur) { |
315 | klist_put(i->i_cur, false); |
316 | i->i_cur = NULL; |
317 | } |
318 | } |
319 | EXPORT_SYMBOL_GPL(klist_iter_exit); |
320 | |
321 | static struct klist_node *to_klist_node(struct list_head *n) |
322 | { |
323 | return container_of(n, struct klist_node, n_node); |
324 | } |
325 | |
326 | /** |
327 | * klist_next - Ante up next node in list. |
328 | * @i: Iterator structure. |
329 | * |
330 | * First grab list lock. Decrement the reference count of the previous |
331 | * node, if there was one. Grab the next node, increment its reference |
332 | * count, drop the lock, and return that next node. |
333 | */ |
334 | struct klist_node *klist_next(struct klist_iter *i) |
335 | { |
336 | void (*put)(struct klist_node *) = i->i_klist->put; |
337 | struct klist_node *last = i->i_cur; |
338 | struct klist_node *next; |
339 | |
340 | spin_lock(&i->i_klist->k_lock); |
341 | |
342 | if (last) { |
343 | next = to_klist_node(last->n_node.next); |
344 | if (!klist_dec_and_del(last)) |
345 | put = NULL; |
346 | } else |
347 | next = to_klist_node(i->i_klist->k_list.next); |
348 | |
349 | i->i_cur = NULL; |
350 | while (next != to_klist_node(&i->i_klist->k_list)) { |
351 | if (likely(!knode_dead(next))) { |
352 | kref_get(&next->n_ref); |
353 | i->i_cur = next; |
354 | break; |
355 | } |
356 | next = to_klist_node(next->n_node.next); |
357 | } |
358 | |
359 | spin_unlock(&i->i_klist->k_lock); |
360 | |
361 | if (put && last) |
362 | put(last); |
363 | return i->i_cur; |
364 | } |
365 | EXPORT_SYMBOL_GPL(klist_next); |
366 |
Branches:
ben-wpan
ben-wpan-stefan
javiroman/ks7010
jz-2.6.34
jz-2.6.34-rc5
jz-2.6.34-rc6
jz-2.6.34-rc7
jz-2.6.35
jz-2.6.36
jz-2.6.37
jz-2.6.38
jz-2.6.39
jz-3.0
jz-3.1
jz-3.11
jz-3.12
jz-3.13
jz-3.15
jz-3.16
jz-3.18-dt
jz-3.2
jz-3.3
jz-3.4
jz-3.5
jz-3.6
jz-3.6-rc2-pwm
jz-3.9
jz-3.9-clk
jz-3.9-rc8
jz47xx
jz47xx-2.6.38
master
Tags:
od-2011-09-04
od-2011-09-18
v2.6.34-rc5
v2.6.34-rc6
v2.6.34-rc7
v3.9