klist.c 6.8 KB

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