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