klist.c 10 KB

123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869707172737475767778798081828384858687888990919293949596979899100101102103104105106107108109110111112113114115116117118119120121122123124125126127128129130131132133134135136137138139140141142143144145146147148149150151152153154155156157158159160161162163164165166167168169170171172173174175176177178179180181182183184185186187188189190191192193194195196197198199200201202203204205206207208209210211212213214215216217218219220221222223224225226227228229230231232233234235236237238239240241242243244245246247248249250251252253254255256257258259260261262263264265266267268269270271272273274275276277278279280281282283284285286287288289290291292293294295296297298299300301302303304305306307308309310311312313314315316317318319320321322323324325326327328329330331332333334335336337338339340341342343344345346347348349350351352353354355356357358359360361362363364365366367368369370371372373374375376377378379380381382383384385386387388389390391392393394395396397398399400401402403404405406407
  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. #include <linux/klist.h>
  36. #include <linux/export.h>
  37. #include <linux/sched.h>
  38. /*
  39. * Use the lowest bit of n_klist to mark deleted nodes and exclude
  40. * dead ones from iteration.
  41. */
  42. #define KNODE_DEAD 1LU
  43. #define KNODE_KLIST_MASK ~KNODE_DEAD
  44. static struct klist *knode_klist(struct klist_node *knode)
  45. {
  46. return (struct klist *)
  47. ((unsigned long)knode->n_klist & KNODE_KLIST_MASK);
  48. }
  49. static bool knode_dead(struct klist_node *knode)
  50. {
  51. return (unsigned long)knode->n_klist & KNODE_DEAD;
  52. }
  53. static void knode_set_klist(struct klist_node *knode, struct klist *klist)
  54. {
  55. knode->n_klist = klist;
  56. /* no knode deserves to start its life dead */
  57. WARN_ON(knode_dead(knode));
  58. }
  59. static void knode_kill(struct klist_node *knode)
  60. {
  61. /* and no knode should die twice ever either, see we're very humane */
  62. WARN_ON(knode_dead(knode));
  63. *(unsigned long *)&knode->n_klist |= KNODE_DEAD;
  64. }
  65. /**
  66. * klist_init - Initialize a klist structure.
  67. * @k: The klist we're initializing.
  68. * @get: The get function for the embedding object (NULL if none)
  69. * @put: The put function for the embedding object (NULL if none)
  70. *
  71. * Initialises the klist structure. If the klist_node structures are
  72. * going to be embedded in refcounted objects (necessary for safe
  73. * deletion) then the get/put arguments are used to initialise
  74. * functions that take and release references on the embedding
  75. * objects.
  76. */
  77. void klist_init(struct klist *k, void (*get)(struct klist_node *),
  78. void (*put)(struct klist_node *))
  79. {
  80. INIT_LIST_HEAD(&k->k_list);
  81. spin_lock_init(&k->k_lock);
  82. k->get = get;
  83. k->put = put;
  84. }
  85. EXPORT_SYMBOL_GPL(klist_init);
  86. static void add_head(struct klist *k, struct klist_node *n)
  87. {
  88. spin_lock(&k->k_lock);
  89. list_add(&n->n_node, &k->k_list);
  90. spin_unlock(&k->k_lock);
  91. }
  92. static void add_tail(struct klist *k, struct klist_node *n)
  93. {
  94. spin_lock(&k->k_lock);
  95. list_add_tail(&n->n_node, &k->k_list);
  96. spin_unlock(&k->k_lock);
  97. }
  98. static void klist_node_init(struct klist *k, struct klist_node *n)
  99. {
  100. INIT_LIST_HEAD(&n->n_node);
  101. kref_init(&n->n_ref);
  102. knode_set_klist(n, k);
  103. if (k->get)
  104. k->get(n);
  105. }
  106. /**
  107. * klist_add_head - Initialize a klist_node and add it to front.
  108. * @n: node we're adding.
  109. * @k: klist it's going on.
  110. */
  111. void klist_add_head(struct klist_node *n, struct klist *k)
  112. {
  113. klist_node_init(k, n);
  114. add_head(k, n);
  115. }
  116. EXPORT_SYMBOL_GPL(klist_add_head);
  117. /**
  118. * klist_add_tail - Initialize a klist_node and add it to back.
  119. * @n: node we're adding.
  120. * @k: klist it's going on.
  121. */
  122. void klist_add_tail(struct klist_node *n, struct klist *k)
  123. {
  124. klist_node_init(k, n);
  125. add_tail(k, n);
  126. }
  127. EXPORT_SYMBOL_GPL(klist_add_tail);
  128. /**
  129. * klist_add_behind - Init a klist_node and add it after an existing node
  130. * @n: node we're adding.
  131. * @pos: node to put @n after
  132. */
  133. void klist_add_behind(struct klist_node *n, struct klist_node *pos)
  134. {
  135. struct klist *k = knode_klist(pos);
  136. klist_node_init(k, n);
  137. spin_lock(&k->k_lock);
  138. list_add(&n->n_node, &pos->n_node);
  139. spin_unlock(&k->k_lock);
  140. }
  141. EXPORT_SYMBOL_GPL(klist_add_behind);
  142. /**
  143. * klist_add_before - Init a klist_node and add it before an existing node
  144. * @n: node we're adding.
  145. * @pos: node to put @n after
  146. */
  147. void klist_add_before(struct klist_node *n, struct klist_node *pos)
  148. {
  149. struct klist *k = knode_klist(pos);
  150. klist_node_init(k, n);
  151. spin_lock(&k->k_lock);
  152. list_add_tail(&n->n_node, &pos->n_node);
  153. spin_unlock(&k->k_lock);
  154. }
  155. EXPORT_SYMBOL_GPL(klist_add_before);
  156. struct klist_waiter {
  157. struct list_head list;
  158. struct klist_node *node;
  159. struct task_struct *process;
  160. int woken;
  161. };
  162. static DEFINE_SPINLOCK(klist_remove_lock);
  163. static LIST_HEAD(klist_remove_waiters);
  164. static void klist_release(struct kref *kref)
  165. {
  166. struct klist_waiter *waiter, *tmp;
  167. struct klist_node *n = container_of(kref, struct klist_node, n_ref);
  168. WARN_ON(!knode_dead(n));
  169. list_del(&n->n_node);
  170. spin_lock(&klist_remove_lock);
  171. list_for_each_entry_safe(waiter, tmp, &klist_remove_waiters, list) {
  172. if (waiter->node != n)
  173. continue;
  174. list_del(&waiter->list);
  175. waiter->woken = 1;
  176. mb();
  177. wake_up_process(waiter->process);
  178. }
  179. spin_unlock(&klist_remove_lock);
  180. knode_set_klist(n, NULL);
  181. }
  182. static int klist_dec_and_del(struct klist_node *n)
  183. {
  184. return kref_put(&n->n_ref, klist_release);
  185. }
  186. static void klist_put(struct klist_node *n, bool kill)
  187. {
  188. struct klist *k = knode_klist(n);
  189. void (*put)(struct klist_node *) = k->put;
  190. spin_lock(&k->k_lock);
  191. if (kill)
  192. knode_kill(n);
  193. if (!klist_dec_and_del(n))
  194. put = NULL;
  195. spin_unlock(&k->k_lock);
  196. if (put)
  197. put(n);
  198. }
  199. /**
  200. * klist_del - Decrement the reference count of node and try to remove.
  201. * @n: node we're deleting.
  202. */
  203. void klist_del(struct klist_node *n)
  204. {
  205. klist_put(n, true);
  206. }
  207. EXPORT_SYMBOL_GPL(klist_del);
  208. /**
  209. * klist_remove - Decrement the refcount of node and wait for it to go away.
  210. * @n: node we're removing.
  211. */
  212. void klist_remove(struct klist_node *n)
  213. {
  214. struct klist_waiter waiter;
  215. waiter.node = n;
  216. waiter.process = current;
  217. waiter.woken = 0;
  218. spin_lock(&klist_remove_lock);
  219. list_add(&waiter.list, &klist_remove_waiters);
  220. spin_unlock(&klist_remove_lock);
  221. klist_del(n);
  222. for (;;) {
  223. set_current_state(TASK_UNINTERRUPTIBLE);
  224. if (waiter.woken)
  225. break;
  226. schedule();
  227. }
  228. __set_current_state(TASK_RUNNING);
  229. }
  230. EXPORT_SYMBOL_GPL(klist_remove);
  231. /**
  232. * klist_node_attached - Say whether a node is bound to a list or not.
  233. * @n: Node that we're testing.
  234. */
  235. int klist_node_attached(struct klist_node *n)
  236. {
  237. return (n->n_klist != NULL);
  238. }
  239. EXPORT_SYMBOL_GPL(klist_node_attached);
  240. /**
  241. * klist_iter_init_node - Initialize a klist_iter structure.
  242. * @k: klist we're iterating.
  243. * @i: klist_iter we're filling.
  244. * @n: node to start with.
  245. *
  246. * Similar to klist_iter_init(), but starts the action off with @n,
  247. * instead of with the list head.
  248. */
  249. void klist_iter_init_node(struct klist *k, struct klist_iter *i,
  250. struct klist_node *n)
  251. {
  252. i->i_klist = k;
  253. i->i_cur = NULL;
  254. if (n && kref_get_unless_zero(&n->n_ref))
  255. i->i_cur = n;
  256. }
  257. EXPORT_SYMBOL_GPL(klist_iter_init_node);
  258. /**
  259. * klist_iter_init - Iniitalize a klist_iter structure.
  260. * @k: klist we're iterating.
  261. * @i: klist_iter structure we're filling.
  262. *
  263. * Similar to klist_iter_init_node(), but start with the list head.
  264. */
  265. void klist_iter_init(struct klist *k, struct klist_iter *i)
  266. {
  267. klist_iter_init_node(k, i, NULL);
  268. }
  269. EXPORT_SYMBOL_GPL(klist_iter_init);
  270. /**
  271. * klist_iter_exit - Finish a list iteration.
  272. * @i: Iterator structure.
  273. *
  274. * Must be called when done iterating over list, as it decrements the
  275. * refcount of the current node. Necessary in case iteration exited before
  276. * the end of the list was reached, and always good form.
  277. */
  278. void klist_iter_exit(struct klist_iter *i)
  279. {
  280. if (i->i_cur) {
  281. klist_put(i->i_cur, false);
  282. i->i_cur = NULL;
  283. }
  284. }
  285. EXPORT_SYMBOL_GPL(klist_iter_exit);
  286. static struct klist_node *to_klist_node(struct list_head *n)
  287. {
  288. return container_of(n, struct klist_node, n_node);
  289. }
  290. /**
  291. * klist_prev - Ante up prev node in list.
  292. * @i: Iterator structure.
  293. *
  294. * First grab list lock. Decrement the reference count of the previous
  295. * node, if there was one. Grab the prev node, increment its reference
  296. * count, drop the lock, and return that prev node.
  297. */
  298. struct klist_node *klist_prev(struct klist_iter *i)
  299. {
  300. void (*put)(struct klist_node *) = i->i_klist->put;
  301. struct klist_node *last = i->i_cur;
  302. struct klist_node *prev;
  303. unsigned long flags;
  304. spin_lock_irqsave(&i->i_klist->k_lock, flags);
  305. if (last) {
  306. prev = to_klist_node(last->n_node.prev);
  307. if (!klist_dec_and_del(last))
  308. put = NULL;
  309. } else
  310. prev = to_klist_node(i->i_klist->k_list.prev);
  311. i->i_cur = NULL;
  312. while (prev != to_klist_node(&i->i_klist->k_list)) {
  313. if (likely(!knode_dead(prev))) {
  314. kref_get(&prev->n_ref);
  315. i->i_cur = prev;
  316. break;
  317. }
  318. prev = to_klist_node(prev->n_node.prev);
  319. }
  320. spin_unlock_irqrestore(&i->i_klist->k_lock, flags);
  321. if (put && last)
  322. put(last);
  323. return i->i_cur;
  324. }
  325. EXPORT_SYMBOL_GPL(klist_prev);
  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. unsigned long flags;
  340. spin_lock_irqsave(&i->i_klist->k_lock, flags);
  341. if (last) {
  342. next = to_klist_node(last->n_node.next);
  343. if (!klist_dec_and_del(last))
  344. put = NULL;
  345. } else
  346. next = to_klist_node(i->i_klist->k_list.next);
  347. i->i_cur = NULL;
  348. while (next != to_klist_node(&i->i_klist->k_list)) {
  349. if (likely(!knode_dead(next))) {
  350. kref_get(&next->n_ref);
  351. i->i_cur = next;
  352. break;
  353. }
  354. next = to_klist_node(next->n_node.next);
  355. }
  356. spin_unlock_irqrestore(&i->i_klist->k_lock, flags);
  357. if (put && last)
  358. put(last);
  359. return i->i_cur;
  360. }
  361. EXPORT_SYMBOL_GPL(klist_next);