parman.c 11 KB

123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869707172737475767778798081828384858687888990919293949596979899100101102103104105106107108109110111112113114115116117118119120121122123124125126127128129130131132133134135136137138139140141142143144145146147148149150151152153154155156157158159160161162163164165166167168169170171172173174175176177178179180181182183184185186187188189190191192193194195196197198199200201202203204205206207208209210211212213214215216217218219220221222223224225226227228229230231232233234235236237238239240241242243244245246247248249250251252253254255256257258259260261262263264265266267268269270271272273274275276277278279280281282283284285286287288289290291292293294295296297298299300301302303304305306307308309310311312313314315316317318319320321322323324325326327328329330331332333334335336337338339340341342343344345346347348349350351352353354355356357358359360361362363364365366367368369370371372373374375376
  1. /*
  2. * lib/parman.c - Manager for linear priority array areas
  3. * Copyright (c) 2017 Mellanox Technologies. All rights reserved.
  4. * Copyright (c) 2017 Jiri Pirko <jiri@mellanox.com>
  5. *
  6. * Redistribution and use in source and binary forms, with or without
  7. * modification, are permitted provided that the following conditions are met:
  8. *
  9. * 1. Redistributions of source code must retain the above copyright
  10. * notice, this list of conditions and the following disclaimer.
  11. * 2. Redistributions in binary form must reproduce the above copyright
  12. * notice, this list of conditions and the following disclaimer in the
  13. * documentation and/or other materials provided with the distribution.
  14. * 3. Neither the names of the copyright holders nor the names of its
  15. * contributors may be used to endorse or promote products derived from
  16. * this software without specific prior written permission.
  17. *
  18. * Alternatively, this software may be distributed under the terms of the
  19. * GNU General Public License ("GPL") version 2 as published by the Free
  20. * Software Foundation.
  21. *
  22. * THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS "AS IS"
  23. * AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE
  24. * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE
  25. * ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT OWNER OR CONTRIBUTORS BE
  26. * LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR
  27. * CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF
  28. * SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS
  29. * INTERRUPTION) HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN
  30. * CONTRACT, STRICT LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE)
  31. * ARISING IN ANY WAY OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE
  32. * POSSIBILITY OF SUCH DAMAGE.
  33. */
  34. #include <linux/kernel.h>
  35. #include <linux/module.h>
  36. #include <linux/slab.h>
  37. #include <linux/export.h>
  38. #include <linux/list.h>
  39. #include <linux/err.h>
  40. #include <linux/parman.h>
  41. struct parman_algo {
  42. int (*item_add)(struct parman *parman, struct parman_prio *prio,
  43. struct parman_item *item);
  44. void (*item_remove)(struct parman *parman, struct parman_prio *prio,
  45. struct parman_item *item);
  46. };
  47. struct parman {
  48. const struct parman_ops *ops;
  49. void *priv;
  50. const struct parman_algo *algo;
  51. unsigned long count;
  52. unsigned long limit_count;
  53. struct list_head prio_list;
  54. };
  55. static int parman_enlarge(struct parman *parman)
  56. {
  57. unsigned long new_count = parman->limit_count +
  58. parman->ops->resize_step;
  59. int err;
  60. err = parman->ops->resize(parman->priv, new_count);
  61. if (err)
  62. return err;
  63. parman->limit_count = new_count;
  64. return 0;
  65. }
  66. static int parman_shrink(struct parman *parman)
  67. {
  68. unsigned long new_count = parman->limit_count -
  69. parman->ops->resize_step;
  70. int err;
  71. if (new_count < parman->ops->base_count)
  72. return 0;
  73. err = parman->ops->resize(parman->priv, new_count);
  74. if (err)
  75. return err;
  76. parman->limit_count = new_count;
  77. return 0;
  78. }
  79. static bool parman_prio_used(struct parman_prio *prio)
  80. {
  81. return !list_empty(&prio->item_list);
  82. }
  83. static struct parman_item *parman_prio_first_item(struct parman_prio *prio)
  84. {
  85. return list_first_entry(&prio->item_list,
  86. typeof(struct parman_item), list);
  87. }
  88. static unsigned long parman_prio_first_index(struct parman_prio *prio)
  89. {
  90. return parman_prio_first_item(prio)->index;
  91. }
  92. static struct parman_item *parman_prio_last_item(struct parman_prio *prio)
  93. {
  94. return list_last_entry(&prio->item_list,
  95. typeof(struct parman_item), list);
  96. }
  97. static unsigned long parman_prio_last_index(struct parman_prio *prio)
  98. {
  99. return parman_prio_last_item(prio)->index;
  100. }
  101. static unsigned long parman_lsort_new_index_find(struct parman *parman,
  102. struct parman_prio *prio)
  103. {
  104. list_for_each_entry_from_reverse(prio, &parman->prio_list, list) {
  105. if (!parman_prio_used(prio))
  106. continue;
  107. return parman_prio_last_index(prio) + 1;
  108. }
  109. return 0;
  110. }
  111. static void __parman_prio_move(struct parman *parman, struct parman_prio *prio,
  112. struct parman_item *item, unsigned long to_index,
  113. unsigned long count)
  114. {
  115. parman->ops->move(parman->priv, item->index, to_index, count);
  116. }
  117. static void parman_prio_shift_down(struct parman *parman,
  118. struct parman_prio *prio)
  119. {
  120. struct parman_item *item;
  121. unsigned long to_index;
  122. if (!parman_prio_used(prio))
  123. return;
  124. item = parman_prio_first_item(prio);
  125. to_index = parman_prio_last_index(prio) + 1;
  126. __parman_prio_move(parman, prio, item, to_index, 1);
  127. list_move_tail(&item->list, &prio->item_list);
  128. item->index = to_index;
  129. }
  130. static void parman_prio_shift_up(struct parman *parman,
  131. struct parman_prio *prio)
  132. {
  133. struct parman_item *item;
  134. unsigned long to_index;
  135. if (!parman_prio_used(prio))
  136. return;
  137. item = parman_prio_last_item(prio);
  138. to_index = parman_prio_first_index(prio) - 1;
  139. __parman_prio_move(parman, prio, item, to_index, 1);
  140. list_move(&item->list, &prio->item_list);
  141. item->index = to_index;
  142. }
  143. static void parman_prio_item_remove(struct parman *parman,
  144. struct parman_prio *prio,
  145. struct parman_item *item)
  146. {
  147. struct parman_item *last_item;
  148. unsigned long to_index;
  149. last_item = parman_prio_last_item(prio);
  150. if (last_item == item) {
  151. list_del(&item->list);
  152. return;
  153. }
  154. to_index = item->index;
  155. __parman_prio_move(parman, prio, last_item, to_index, 1);
  156. list_del(&last_item->list);
  157. list_replace(&item->list, &last_item->list);
  158. last_item->index = to_index;
  159. }
  160. static int parman_lsort_item_add(struct parman *parman,
  161. struct parman_prio *prio,
  162. struct parman_item *item)
  163. {
  164. struct parman_prio *prio2;
  165. unsigned long new_index;
  166. int err;
  167. if (parman->count + 1 > parman->limit_count) {
  168. err = parman_enlarge(parman);
  169. if (err)
  170. return err;
  171. }
  172. new_index = parman_lsort_new_index_find(parman, prio);
  173. list_for_each_entry_reverse(prio2, &parman->prio_list, list) {
  174. if (prio2 == prio)
  175. break;
  176. parman_prio_shift_down(parman, prio2);
  177. }
  178. item->index = new_index;
  179. list_add_tail(&item->list, &prio->item_list);
  180. parman->count++;
  181. return 0;
  182. }
  183. static void parman_lsort_item_remove(struct parman *parman,
  184. struct parman_prio *prio,
  185. struct parman_item *item)
  186. {
  187. parman_prio_item_remove(parman, prio, item);
  188. list_for_each_entry_continue(prio, &parman->prio_list, list)
  189. parman_prio_shift_up(parman, prio);
  190. parman->count--;
  191. if (parman->limit_count - parman->count >= parman->ops->resize_step)
  192. parman_shrink(parman);
  193. }
  194. static const struct parman_algo parman_lsort = {
  195. .item_add = parman_lsort_item_add,
  196. .item_remove = parman_lsort_item_remove,
  197. };
  198. static const struct parman_algo *parman_algos[] = {
  199. &parman_lsort,
  200. };
  201. /**
  202. * parman_create - creates a new parman instance
  203. * @ops: caller-specific callbacks
  204. * @priv: pointer to a private data passed to the ops
  205. *
  206. * Note: all locking must be provided by the caller.
  207. *
  208. * Each parman instance manages an array area with chunks of entries
  209. * with the same priority. Consider following example:
  210. *
  211. * item 1 with prio 10
  212. * item 2 with prio 10
  213. * item 3 with prio 10
  214. * item 4 with prio 20
  215. * item 5 with prio 20
  216. * item 6 with prio 30
  217. * item 7 with prio 30
  218. * item 8 with prio 30
  219. *
  220. * In this example, there are 3 priority chunks. The order of the priorities
  221. * matters, however the order of items within a single priority chunk does not
  222. * matter. So the same array could be ordered as follows:
  223. *
  224. * item 2 with prio 10
  225. * item 3 with prio 10
  226. * item 1 with prio 10
  227. * item 5 with prio 20
  228. * item 4 with prio 20
  229. * item 7 with prio 30
  230. * item 8 with prio 30
  231. * item 6 with prio 30
  232. *
  233. * The goal of parman is to maintain the priority ordering. The caller
  234. * provides @ops with callbacks parman uses to move the items
  235. * and resize the array area.
  236. *
  237. * Returns a pointer to newly created parman instance in case of success,
  238. * otherwise it returns NULL.
  239. */
  240. struct parman *parman_create(const struct parman_ops *ops, void *priv)
  241. {
  242. struct parman *parman;
  243. parman = kzalloc(sizeof(*parman), GFP_KERNEL);
  244. if (!parman)
  245. return NULL;
  246. INIT_LIST_HEAD(&parman->prio_list);
  247. parman->ops = ops;
  248. parman->priv = priv;
  249. parman->limit_count = ops->base_count;
  250. parman->algo = parman_algos[ops->algo];
  251. return parman;
  252. }
  253. EXPORT_SYMBOL(parman_create);
  254. /**
  255. * parman_destroy - destroys existing parman instance
  256. * @parman: parman instance
  257. *
  258. * Note: all locking must be provided by the caller.
  259. */
  260. void parman_destroy(struct parman *parman)
  261. {
  262. WARN_ON(!list_empty(&parman->prio_list));
  263. kfree(parman);
  264. }
  265. EXPORT_SYMBOL(parman_destroy);
  266. /**
  267. * parman_prio_init - initializes a parman priority chunk
  268. * @parman: parman instance
  269. * @prio: parman prio structure to be initialized
  270. * @prority: desired priority of the chunk
  271. *
  272. * Note: all locking must be provided by the caller.
  273. *
  274. * Before caller could add an item with certain priority, he has to
  275. * initialize a priority chunk for it using this function.
  276. */
  277. void parman_prio_init(struct parman *parman, struct parman_prio *prio,
  278. unsigned long priority)
  279. {
  280. struct parman_prio *prio2;
  281. struct list_head *pos;
  282. INIT_LIST_HEAD(&prio->item_list);
  283. prio->priority = priority;
  284. /* Position inside the list according to priority */
  285. list_for_each(pos, &parman->prio_list) {
  286. prio2 = list_entry(pos, typeof(*prio2), list);
  287. if (prio2->priority > prio->priority)
  288. break;
  289. }
  290. list_add_tail(&prio->list, pos);
  291. }
  292. EXPORT_SYMBOL(parman_prio_init);
  293. /**
  294. * parman_prio_fini - finalizes use of parman priority chunk
  295. * @prio: parman prio structure
  296. *
  297. * Note: all locking must be provided by the caller.
  298. */
  299. void parman_prio_fini(struct parman_prio *prio)
  300. {
  301. WARN_ON(parman_prio_used(prio));
  302. list_del(&prio->list);
  303. }
  304. EXPORT_SYMBOL(parman_prio_fini);
  305. /**
  306. * parman_item_add - adds a parman item under defined priority
  307. * @parman: parman instance
  308. * @prio: parman prio instance to add the item to
  309. * @item: parman item instance
  310. *
  311. * Note: all locking must be provided by the caller.
  312. *
  313. * Adds item to a array managed by parman instance under the specified priority.
  314. *
  315. * Returns 0 in case of success, negative number to indicate an error.
  316. */
  317. int parman_item_add(struct parman *parman, struct parman_prio *prio,
  318. struct parman_item *item)
  319. {
  320. return parman->algo->item_add(parman, prio, item);
  321. }
  322. EXPORT_SYMBOL(parman_item_add);
  323. /**
  324. * parman_item_del - deletes parman item
  325. * @parman: parman instance
  326. * @prio: parman prio instance to delete the item from
  327. * @item: parman item instance
  328. *
  329. * Note: all locking must be provided by the caller.
  330. */
  331. void parman_item_remove(struct parman *parman, struct parman_prio *prio,
  332. struct parman_item *item)
  333. {
  334. parman->algo->item_remove(parman, prio, item);
  335. }
  336. EXPORT_SYMBOL(parman_item_remove);
  337. MODULE_LICENSE("Dual BSD/GPL");
  338. MODULE_AUTHOR("Jiri Pirko <jiri@mellanox.com>");
  339. MODULE_DESCRIPTION("Priority-based array manager");