mochel@digitalimplant.org | 9a19fea | 2005-03-21 11:45:16 -0800 | [diff] [blame] | 1 | /* |
Greg Kroah-Hartman | c3bb7fad | 2008-04-30 16:43:45 -0700 | [diff] [blame] | 2 | * klist.c - Routines for manipulating klists. |
mochel@digitalimplant.org | 9a19fea | 2005-03-21 11:45:16 -0800 | [diff] [blame] | 3 | * |
Greg Kroah-Hartman | c3bb7fad | 2008-04-30 16:43:45 -0700 | [diff] [blame] | 4 | * Copyright (C) 2005 Patrick Mochel |
mochel@digitalimplant.org | 9a19fea | 2005-03-21 11:45:16 -0800 | [diff] [blame] | 5 | * |
Greg Kroah-Hartman | c3bb7fad | 2008-04-30 16:43:45 -0700 | [diff] [blame] | 6 | * This file is released under the GPL v2. |
mochel@digitalimplant.org | 9a19fea | 2005-03-21 11:45:16 -0800 | [diff] [blame] | 7 | * |
Greg Kroah-Hartman | c3bb7fad | 2008-04-30 16:43:45 -0700 | [diff] [blame] | 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. |
mochel@digitalimplant.org | 9a19fea | 2005-03-21 11:45:16 -0800 | [diff] [blame] | 15 | * |
Greg Kroah-Hartman | c3bb7fad | 2008-04-30 16:43:45 -0700 | [diff] [blame] | 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. |
mochel@digitalimplant.org | 9a19fea | 2005-03-21 11:45:16 -0800 | [diff] [blame] | 20 | * |
Greg Kroah-Hartman | c3bb7fad | 2008-04-30 16:43:45 -0700 | [diff] [blame] | 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. |
mochel@digitalimplant.org | 9a19fea | 2005-03-21 11:45:16 -0800 | [diff] [blame] | 27 | * |
Greg Kroah-Hartman | c3bb7fad | 2008-04-30 16:43:45 -0700 | [diff] [blame] | 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). |
mochel@digitalimplant.org | 9a19fea | 2005-03-21 11:45:16 -0800 | [diff] [blame] | 35 | */ |
| 36 | |
| 37 | #include <linux/klist.h> |
Paul Gortmaker | 8bc3bcc | 2011-11-16 21:29:17 -0500 | [diff] [blame] | 38 | #include <linux/export.h> |
Matthew Wilcox | 210272a | 2008-10-16 14:57:54 -0600 | [diff] [blame] | 39 | #include <linux/sched.h> |
mochel@digitalimplant.org | 9a19fea | 2005-03-21 11:45:16 -0800 | [diff] [blame] | 40 | |
Tejun Heo | a1ed5b0 | 2008-08-25 19:50:16 +0200 | [diff] [blame] | 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 | } |
mochel@digitalimplant.org | 9a19fea | 2005-03-21 11:45:16 -0800 | [diff] [blame] | 72 | |
| 73 | /** |
Greg Kroah-Hartman | c3bb7fad | 2008-04-30 16:43:45 -0700 | [diff] [blame] | 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) |
James Bottomley | 34bb61f | 2005-09-06 16:56:51 -0700 | [diff] [blame] | 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. |
mochel@digitalimplant.org | 9a19fea | 2005-03-21 11:45:16 -0800 | [diff] [blame] | 84 | */ |
Greg Kroah-Hartman | c3bb7fad | 2008-04-30 16:43:45 -0700 | [diff] [blame] | 85 | void klist_init(struct klist *k, void (*get)(struct klist_node *), |
James Bottomley | 34bb61f | 2005-09-06 16:56:51 -0700 | [diff] [blame] | 86 | void (*put)(struct klist_node *)) |
mochel@digitalimplant.org | 9a19fea | 2005-03-21 11:45:16 -0800 | [diff] [blame] | 87 | { |
| 88 | INIT_LIST_HEAD(&k->k_list); |
| 89 | spin_lock_init(&k->k_lock); |
James Bottomley | 34bb61f | 2005-09-06 16:56:51 -0700 | [diff] [blame] | 90 | k->get = get; |
| 91 | k->put = put; |
mochel@digitalimplant.org | 9a19fea | 2005-03-21 11:45:16 -0800 | [diff] [blame] | 92 | } |
mochel@digitalimplant.org | 9a19fea | 2005-03-21 11:45:16 -0800 | [diff] [blame] | 93 | EXPORT_SYMBOL_GPL(klist_init); |
| 94 | |
Greg Kroah-Hartman | c3bb7fad | 2008-04-30 16:43:45 -0700 | [diff] [blame] | 95 | static void add_head(struct klist *k, struct klist_node *n) |
mochel@digitalimplant.org | 9a19fea | 2005-03-21 11:45:16 -0800 | [diff] [blame] | 96 | { |
| 97 | spin_lock(&k->k_lock); |
| 98 | list_add(&n->n_node, &k->k_list); |
| 99 | spin_unlock(&k->k_lock); |
| 100 | } |
| 101 | |
Greg Kroah-Hartman | c3bb7fad | 2008-04-30 16:43:45 -0700 | [diff] [blame] | 102 | static void add_tail(struct klist *k, struct klist_node *n) |
mochel@digitalimplant.org | 9a19fea | 2005-03-21 11:45:16 -0800 | [diff] [blame] | 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 | |
Greg Kroah-Hartman | c3bb7fad | 2008-04-30 16:43:45 -0700 | [diff] [blame] | 109 | static void klist_node_init(struct klist *k, struct klist_node *n) |
mochel@digitalimplant.org | 9a19fea | 2005-03-21 11:45:16 -0800 | [diff] [blame] | 110 | { |
| 111 | INIT_LIST_HEAD(&n->n_node); |
mochel@digitalimplant.org | 9a19fea | 2005-03-21 11:45:16 -0800 | [diff] [blame] | 112 | kref_init(&n->n_ref); |
Tejun Heo | a1ed5b0 | 2008-08-25 19:50:16 +0200 | [diff] [blame] | 113 | knode_set_klist(n, k); |
James Bottomley | 34bb61f | 2005-09-06 16:56:51 -0700 | [diff] [blame] | 114 | if (k->get) |
| 115 | k->get(n); |
mochel@digitalimplant.org | 9a19fea | 2005-03-21 11:45:16 -0800 | [diff] [blame] | 116 | } |
| 117 | |
mochel@digitalimplant.org | 9a19fea | 2005-03-21 11:45:16 -0800 | [diff] [blame] | 118 | /** |
Greg Kroah-Hartman | c3bb7fad | 2008-04-30 16:43:45 -0700 | [diff] [blame] | 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. |
mochel@digitalimplant.org | 9a19fea | 2005-03-21 11:45:16 -0800 | [diff] [blame] | 122 | */ |
Greg Kroah-Hartman | c3bb7fad | 2008-04-30 16:43:45 -0700 | [diff] [blame] | 123 | void klist_add_head(struct klist_node *n, struct klist *k) |
mochel@digitalimplant.org | 9a19fea | 2005-03-21 11:45:16 -0800 | [diff] [blame] | 124 | { |
| 125 | klist_node_init(k, n); |
| 126 | add_head(k, n); |
| 127 | } |
mochel@digitalimplant.org | 9a19fea | 2005-03-21 11:45:16 -0800 | [diff] [blame] | 128 | EXPORT_SYMBOL_GPL(klist_add_head); |
| 129 | |
mochel@digitalimplant.org | 9a19fea | 2005-03-21 11:45:16 -0800 | [diff] [blame] | 130 | /** |
Greg Kroah-Hartman | c3bb7fad | 2008-04-30 16:43:45 -0700 | [diff] [blame] | 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. |
mochel@digitalimplant.org | 9a19fea | 2005-03-21 11:45:16 -0800 | [diff] [blame] | 134 | */ |
Greg Kroah-Hartman | c3bb7fad | 2008-04-30 16:43:45 -0700 | [diff] [blame] | 135 | void klist_add_tail(struct klist_node *n, struct klist *k) |
mochel@digitalimplant.org | 9a19fea | 2005-03-21 11:45:16 -0800 | [diff] [blame] | 136 | { |
| 137 | klist_node_init(k, n); |
| 138 | add_tail(k, n); |
| 139 | } |
mochel@digitalimplant.org | 9a19fea | 2005-03-21 11:45:16 -0800 | [diff] [blame] | 140 | EXPORT_SYMBOL_GPL(klist_add_tail); |
| 141 | |
Tejun Heo | 93dd400 | 2008-04-22 18:58:46 +0900 | [diff] [blame] | 142 | /** |
Ken Helias | 0f9859c | 2014-08-06 16:09:18 -0700 | [diff] [blame] | 143 | * klist_add_behind - Init a klist_node and add it after an existing node |
Tejun Heo | 93dd400 | 2008-04-22 18:58:46 +0900 | [diff] [blame] | 144 | * @n: node we're adding. |
| 145 | * @pos: node to put @n after |
| 146 | */ |
Ken Helias | 0f9859c | 2014-08-06 16:09:18 -0700 | [diff] [blame] | 147 | void klist_add_behind(struct klist_node *n, struct klist_node *pos) |
Tejun Heo | 93dd400 | 2008-04-22 18:58:46 +0900 | [diff] [blame] | 148 | { |
Tejun Heo | a1ed5b0 | 2008-08-25 19:50:16 +0200 | [diff] [blame] | 149 | struct klist *k = knode_klist(pos); |
Tejun Heo | 93dd400 | 2008-04-22 18:58:46 +0900 | [diff] [blame] | 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 | } |
Ken Helias | 0f9859c | 2014-08-06 16:09:18 -0700 | [diff] [blame] | 156 | EXPORT_SYMBOL_GPL(klist_add_behind); |
Tejun Heo | 93dd400 | 2008-04-22 18:58:46 +0900 | [diff] [blame] | 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 | { |
Tejun Heo | a1ed5b0 | 2008-08-25 19:50:16 +0200 | [diff] [blame] | 165 | struct klist *k = knode_klist(pos); |
Tejun Heo | 93dd400 | 2008-04-22 18:58:46 +0900 | [diff] [blame] | 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 | |
Matthew Wilcox | 210272a | 2008-10-16 14:57:54 -0600 | [diff] [blame] | 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 | |
Greg Kroah-Hartman | c3bb7fad | 2008-04-30 16:43:45 -0700 | [diff] [blame] | 184 | static void klist_release(struct kref *kref) |
mochel@digitalimplant.org | 9a19fea | 2005-03-21 11:45:16 -0800 | [diff] [blame] | 185 | { |
Matthew Wilcox | 210272a | 2008-10-16 14:57:54 -0600 | [diff] [blame] | 186 | struct klist_waiter *waiter, *tmp; |
Greg Kroah-Hartman | c3bb7fad | 2008-04-30 16:43:45 -0700 | [diff] [blame] | 187 | struct klist_node *n = container_of(kref, struct klist_node, n_ref); |
Alan Stern | 7e9f4b2 | 2006-09-18 16:28:06 -0400 | [diff] [blame] | 188 | |
Tejun Heo | a1ed5b0 | 2008-08-25 19:50:16 +0200 | [diff] [blame] | 189 | WARN_ON(!knode_dead(n)); |
mochel@digitalimplant.org | 9a19fea | 2005-03-21 11:45:16 -0800 | [diff] [blame] | 190 | list_del(&n->n_node); |
Matthew Wilcox | 210272a | 2008-10-16 14:57:54 -0600 | [diff] [blame] | 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 | |
wang, biao | ac5a296 | 2013-05-16 09:50:13 +0800 | [diff] [blame] | 196 | list_del(&waiter->list); |
Matthew Wilcox | 210272a | 2008-10-16 14:57:54 -0600 | [diff] [blame] | 197 | waiter->woken = 1; |
| 198 | mb(); |
| 199 | wake_up_process(waiter->process); |
Matthew Wilcox | 210272a | 2008-10-16 14:57:54 -0600 | [diff] [blame] | 200 | } |
| 201 | spin_unlock(&klist_remove_lock); |
Tejun Heo | a1ed5b0 | 2008-08-25 19:50:16 +0200 | [diff] [blame] | 202 | knode_set_klist(n, NULL); |
mochel@digitalimplant.org | 9a19fea | 2005-03-21 11:45:16 -0800 | [diff] [blame] | 203 | } |
| 204 | |
Greg Kroah-Hartman | c3bb7fad | 2008-04-30 16:43:45 -0700 | [diff] [blame] | 205 | static int klist_dec_and_del(struct klist_node *n) |
mochel@digitalimplant.org | 9a19fea | 2005-03-21 11:45:16 -0800 | [diff] [blame] | 206 | { |
| 207 | return kref_put(&n->n_ref, klist_release); |
| 208 | } |
| 209 | |
Tejun Heo | a1ed5b0 | 2008-08-25 19:50:16 +0200 | [diff] [blame] | 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 | |
mochel@digitalimplant.org | 9a19fea | 2005-03-21 11:45:16 -0800 | [diff] [blame] | 225 | /** |
Greg Kroah-Hartman | c3bb7fad | 2008-04-30 16:43:45 -0700 | [diff] [blame] | 226 | * klist_del - Decrement the reference count of node and try to remove. |
| 227 | * @n: node we're deleting. |
mochel@digitalimplant.org | 9a19fea | 2005-03-21 11:45:16 -0800 | [diff] [blame] | 228 | */ |
Greg Kroah-Hartman | c3bb7fad | 2008-04-30 16:43:45 -0700 | [diff] [blame] | 229 | void klist_del(struct klist_node *n) |
mochel@digitalimplant.org | 9a19fea | 2005-03-21 11:45:16 -0800 | [diff] [blame] | 230 | { |
Tejun Heo | a1ed5b0 | 2008-08-25 19:50:16 +0200 | [diff] [blame] | 231 | klist_put(n, true); |
mochel@digitalimplant.org | 9a19fea | 2005-03-21 11:45:16 -0800 | [diff] [blame] | 232 | } |
mochel@digitalimplant.org | 9a19fea | 2005-03-21 11:45:16 -0800 | [diff] [blame] | 233 | EXPORT_SYMBOL_GPL(klist_del); |
| 234 | |
mochel@digitalimplant.org | 9a19fea | 2005-03-21 11:45:16 -0800 | [diff] [blame] | 235 | /** |
Greg Kroah-Hartman | c3bb7fad | 2008-04-30 16:43:45 -0700 | [diff] [blame] | 236 | * klist_remove - Decrement the refcount of node and wait for it to go away. |
| 237 | * @n: node we're removing. |
mochel@digitalimplant.org | 9a19fea | 2005-03-21 11:45:16 -0800 | [diff] [blame] | 238 | */ |
Greg Kroah-Hartman | c3bb7fad | 2008-04-30 16:43:45 -0700 | [diff] [blame] | 239 | void klist_remove(struct klist_node *n) |
mochel@digitalimplant.org | 9a19fea | 2005-03-21 11:45:16 -0800 | [diff] [blame] | 240 | { |
Matthew Wilcox | 210272a | 2008-10-16 14:57:54 -0600 | [diff] [blame] | 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 | |
Alan Stern | 7e9f4b2 | 2006-09-18 16:28:06 -0400 | [diff] [blame] | 250 | klist_del(n); |
Matthew Wilcox | 210272a | 2008-10-16 14:57:54 -0600 | [diff] [blame] | 251 | |
| 252 | for (;;) { |
| 253 | set_current_state(TASK_UNINTERRUPTIBLE); |
| 254 | if (waiter.woken) |
| 255 | break; |
| 256 | schedule(); |
| 257 | } |
| 258 | __set_current_state(TASK_RUNNING); |
mochel@digitalimplant.org | 9a19fea | 2005-03-21 11:45:16 -0800 | [diff] [blame] | 259 | } |
mochel@digitalimplant.org | 9a19fea | 2005-03-21 11:45:16 -0800 | [diff] [blame] | 260 | EXPORT_SYMBOL_GPL(klist_remove); |
| 261 | |
mochel@digitalimplant.org | 9a19fea | 2005-03-21 11:45:16 -0800 | [diff] [blame] | 262 | /** |
Greg Kroah-Hartman | c3bb7fad | 2008-04-30 16:43:45 -0700 | [diff] [blame] | 263 | * klist_node_attached - Say whether a node is bound to a list or not. |
| 264 | * @n: Node that we're testing. |
mochel@digitalimplant.org | 8b0c250b | 2005-03-24 12:58:57 -0800 | [diff] [blame] | 265 | */ |
Greg Kroah-Hartman | c3bb7fad | 2008-04-30 16:43:45 -0700 | [diff] [blame] | 266 | int klist_node_attached(struct klist_node *n) |
mochel@digitalimplant.org | 8b0c250b | 2005-03-24 12:58:57 -0800 | [diff] [blame] | 267 | { |
| 268 | return (n->n_klist != NULL); |
| 269 | } |
mochel@digitalimplant.org | 8b0c250b | 2005-03-24 12:58:57 -0800 | [diff] [blame] | 270 | EXPORT_SYMBOL_GPL(klist_node_attached); |
| 271 | |
mochel@digitalimplant.org | 8b0c250b | 2005-03-24 12:58:57 -0800 | [diff] [blame] | 272 | /** |
Greg Kroah-Hartman | c3bb7fad | 2008-04-30 16:43:45 -0700 | [diff] [blame] | 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. |
mochel@digitalimplant.org | 9a19fea | 2005-03-21 11:45:16 -0800 | [diff] [blame] | 277 | * |
Greg Kroah-Hartman | c3bb7fad | 2008-04-30 16:43:45 -0700 | [diff] [blame] | 278 | * Similar to klist_iter_init(), but starts the action off with @n, |
| 279 | * instead of with the list head. |
mochel@digitalimplant.org | 9a19fea | 2005-03-21 11:45:16 -0800 | [diff] [blame] | 280 | */ |
Greg Kroah-Hartman | c3bb7fad | 2008-04-30 16:43:45 -0700 | [diff] [blame] | 281 | void klist_iter_init_node(struct klist *k, struct klist_iter *i, |
| 282 | struct klist_node *n) |
mochel@digitalimplant.org | 9a19fea | 2005-03-21 11:45:16 -0800 | [diff] [blame] | 283 | { |
| 284 | i->i_klist = k; |
James Bottomley | 00cd29b | 2016-01-13 08:10:31 -0800 | [diff] [blame] | 285 | i->i_cur = NULL; |
| 286 | if (n && kref_get_unless_zero(&n->n_ref)) |
| 287 | i->i_cur = n; |
mochel@digitalimplant.org | 9a19fea | 2005-03-21 11:45:16 -0800 | [diff] [blame] | 288 | } |
mochel@digitalimplant.org | 9a19fea | 2005-03-21 11:45:16 -0800 | [diff] [blame] | 289 | EXPORT_SYMBOL_GPL(klist_iter_init_node); |
| 290 | |
mochel@digitalimplant.org | 9a19fea | 2005-03-21 11:45:16 -0800 | [diff] [blame] | 291 | /** |
Greg Kroah-Hartman | c3bb7fad | 2008-04-30 16:43:45 -0700 | [diff] [blame] | 292 | * klist_iter_init - Iniitalize a klist_iter structure. |
| 293 | * @k: klist we're iterating. |
| 294 | * @i: klist_iter structure we're filling. |
mochel@digitalimplant.org | 9a19fea | 2005-03-21 11:45:16 -0800 | [diff] [blame] | 295 | * |
Greg Kroah-Hartman | c3bb7fad | 2008-04-30 16:43:45 -0700 | [diff] [blame] | 296 | * Similar to klist_iter_init_node(), but start with the list head. |
mochel@digitalimplant.org | 9a19fea | 2005-03-21 11:45:16 -0800 | [diff] [blame] | 297 | */ |
Greg Kroah-Hartman | c3bb7fad | 2008-04-30 16:43:45 -0700 | [diff] [blame] | 298 | void klist_iter_init(struct klist *k, struct klist_iter *i) |
mochel@digitalimplant.org | 9a19fea | 2005-03-21 11:45:16 -0800 | [diff] [blame] | 299 | { |
| 300 | klist_iter_init_node(k, i, NULL); |
| 301 | } |
mochel@digitalimplant.org | 9a19fea | 2005-03-21 11:45:16 -0800 | [diff] [blame] | 302 | EXPORT_SYMBOL_GPL(klist_iter_init); |
| 303 | |
mochel@digitalimplant.org | 9a19fea | 2005-03-21 11:45:16 -0800 | [diff] [blame] | 304 | /** |
Greg Kroah-Hartman | c3bb7fad | 2008-04-30 16:43:45 -0700 | [diff] [blame] | 305 | * klist_iter_exit - Finish a list iteration. |
| 306 | * @i: Iterator structure. |
mochel@digitalimplant.org | 9a19fea | 2005-03-21 11:45:16 -0800 | [diff] [blame] | 307 | * |
Greg Kroah-Hartman | c3bb7fad | 2008-04-30 16:43:45 -0700 | [diff] [blame] | 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. |
mochel@digitalimplant.org | 9a19fea | 2005-03-21 11:45:16 -0800 | [diff] [blame] | 311 | */ |
Greg Kroah-Hartman | c3bb7fad | 2008-04-30 16:43:45 -0700 | [diff] [blame] | 312 | void klist_iter_exit(struct klist_iter *i) |
mochel@digitalimplant.org | 9a19fea | 2005-03-21 11:45:16 -0800 | [diff] [blame] | 313 | { |
| 314 | if (i->i_cur) { |
Tejun Heo | a1ed5b0 | 2008-08-25 19:50:16 +0200 | [diff] [blame] | 315 | klist_put(i->i_cur, false); |
mochel@digitalimplant.org | 9a19fea | 2005-03-21 11:45:16 -0800 | [diff] [blame] | 316 | i->i_cur = NULL; |
| 317 | } |
| 318 | } |
mochel@digitalimplant.org | 9a19fea | 2005-03-21 11:45:16 -0800 | [diff] [blame] | 319 | EXPORT_SYMBOL_GPL(klist_iter_exit); |
| 320 | |
Greg Kroah-Hartman | c3bb7fad | 2008-04-30 16:43:45 -0700 | [diff] [blame] | 321 | static struct klist_node *to_klist_node(struct list_head *n) |
mochel@digitalimplant.org | 9a19fea | 2005-03-21 11:45:16 -0800 | [diff] [blame] | 322 | { |
| 323 | return container_of(n, struct klist_node, n_node); |
| 324 | } |
| 325 | |
mochel@digitalimplant.org | 9a19fea | 2005-03-21 11:45:16 -0800 | [diff] [blame] | 326 | /** |
Andy Shevchenko | 2e0fed7 | 2015-07-27 18:03:59 +0300 | [diff] [blame] | 327 | * klist_prev - Ante up prev 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 prev node, increment its reference |
| 332 | * count, drop the lock, and return that prev node. |
| 333 | */ |
| 334 | struct klist_node *klist_prev(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 *prev; |
| 339 | |
| 340 | spin_lock(&i->i_klist->k_lock); |
| 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(&i->i_klist->k_lock); |
| 360 | |
| 361 | if (put && last) |
| 362 | put(last); |
| 363 | return i->i_cur; |
| 364 | } |
| 365 | EXPORT_SYMBOL_GPL(klist_prev); |
| 366 | |
| 367 | /** |
Greg Kroah-Hartman | c3bb7fad | 2008-04-30 16:43:45 -0700 | [diff] [blame] | 368 | * klist_next - Ante up next node in list. |
| 369 | * @i: Iterator structure. |
mochel@digitalimplant.org | 9a19fea | 2005-03-21 11:45:16 -0800 | [diff] [blame] | 370 | * |
Greg Kroah-Hartman | c3bb7fad | 2008-04-30 16:43:45 -0700 | [diff] [blame] | 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. |
mochel@digitalimplant.org | 9a19fea | 2005-03-21 11:45:16 -0800 | [diff] [blame] | 374 | */ |
Greg Kroah-Hartman | c3bb7fad | 2008-04-30 16:43:45 -0700 | [diff] [blame] | 375 | struct klist_node *klist_next(struct klist_iter *i) |
mochel@digitalimplant.org | 9a19fea | 2005-03-21 11:45:16 -0800 | [diff] [blame] | 376 | { |
Alan Stern | 7e9f4b2 | 2006-09-18 16:28:06 -0400 | [diff] [blame] | 377 | void (*put)(struct klist_node *) = i->i_klist->put; |
Tejun Heo | a1ed5b0 | 2008-08-25 19:50:16 +0200 | [diff] [blame] | 378 | struct klist_node *last = i->i_cur; |
| 379 | struct klist_node *next; |
mochel@digitalimplant.org | 9a19fea | 2005-03-21 11:45:16 -0800 | [diff] [blame] | 380 | |
| 381 | spin_lock(&i->i_klist->k_lock); |
Tejun Heo | a1ed5b0 | 2008-08-25 19:50:16 +0200 | [diff] [blame] | 382 | |
| 383 | if (last) { |
| 384 | next = to_klist_node(last->n_node.next); |
| 385 | if (!klist_dec_and_del(last)) |
Alan Stern | 7e9f4b2 | 2006-09-18 16:28:06 -0400 | [diff] [blame] | 386 | put = NULL; |
mochel@digitalimplant.org | 9a19fea | 2005-03-21 11:45:16 -0800 | [diff] [blame] | 387 | } else |
Tejun Heo | a1ed5b0 | 2008-08-25 19:50:16 +0200 | [diff] [blame] | 388 | next = to_klist_node(i->i_klist->k_list.next); |
mochel@digitalimplant.org | 9a19fea | 2005-03-21 11:45:16 -0800 | [diff] [blame] | 389 | |
Tejun Heo | a1ed5b0 | 2008-08-25 19:50:16 +0200 | [diff] [blame] | 390 | i->i_cur = NULL; |
| 391 | while (next != to_klist_node(&i->i_klist->k_list)) { |
| 392 | if (likely(!knode_dead(next))) { |
| 393 | kref_get(&next->n_ref); |
| 394 | i->i_cur = next; |
| 395 | break; |
| 396 | } |
| 397 | next = to_klist_node(next->n_node.next); |
mochel@digitalimplant.org | 9a19fea | 2005-03-21 11:45:16 -0800 | [diff] [blame] | 398 | } |
Tejun Heo | a1ed5b0 | 2008-08-25 19:50:16 +0200 | [diff] [blame] | 399 | |
mochel@digitalimplant.org | 9a19fea | 2005-03-21 11:45:16 -0800 | [diff] [blame] | 400 | spin_unlock(&i->i_klist->k_lock); |
Tejun Heo | a1ed5b0 | 2008-08-25 19:50:16 +0200 | [diff] [blame] | 401 | |
| 402 | if (put && last) |
| 403 | put(last); |
| 404 | return i->i_cur; |
mochel@digitalimplant.org | 9a19fea | 2005-03-21 11:45:16 -0800 | [diff] [blame] | 405 | } |
mochel@digitalimplant.org | 9a19fea | 2005-03-21 11:45:16 -0800 | [diff] [blame] | 406 | EXPORT_SYMBOL_GPL(klist_next); |