docs: driver-api: usb: avoid using ReST :doc:`foo` markup
[linux-2.6-microblaze.git] / lib / parman.c
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
35 #include <linux/kernel.h>
36 #include <linux/module.h>
37 #include <linux/slab.h>
38 #include <linux/export.h>
39 #include <linux/list.h>
40 #include <linux/err.h>
41 #include <linux/parman.h>
42
43 struct parman_algo {
44         int (*item_add)(struct parman *parman, struct parman_prio *prio,
45                         struct parman_item *item);
46         void (*item_remove)(struct parman *parman, struct parman_prio *prio,
47                             struct parman_item *item);
48 };
49
50 struct parman {
51         const struct parman_ops *ops;
52         void *priv;
53         const struct parman_algo *algo;
54         unsigned long count;
55         unsigned long limit_count;
56         struct list_head prio_list;
57 };
58
59 static int parman_enlarge(struct parman *parman)
60 {
61         unsigned long new_count = parman->limit_count +
62                                   parman->ops->resize_step;
63         int err;
64
65         err = parman->ops->resize(parman->priv, new_count);
66         if (err)
67                 return err;
68         parman->limit_count = new_count;
69         return 0;
70 }
71
72 static int parman_shrink(struct parman *parman)
73 {
74         unsigned long new_count = parman->limit_count -
75                                   parman->ops->resize_step;
76         int err;
77
78         if (new_count < parman->ops->base_count)
79                 return 0;
80         err = parman->ops->resize(parman->priv, new_count);
81         if (err)
82                 return err;
83         parman->limit_count = new_count;
84         return 0;
85 }
86
87 static bool parman_prio_used(struct parman_prio *prio)
88 {
89         return !list_empty(&prio->item_list);
90 }
91
92 static struct parman_item *parman_prio_first_item(struct parman_prio *prio)
93 {
94         return list_first_entry(&prio->item_list,
95                                 typeof(struct parman_item), list);
96 }
97
98 static unsigned long parman_prio_first_index(struct parman_prio *prio)
99 {
100         return parman_prio_first_item(prio)->index;
101 }
102
103 static struct parman_item *parman_prio_last_item(struct parman_prio *prio)
104 {
105         return list_last_entry(&prio->item_list,
106                                typeof(struct parman_item), list);
107 }
108
109 static unsigned long parman_prio_last_index(struct parman_prio *prio)
110 {
111         return parman_prio_last_item(prio)->index;
112 }
113
114 static unsigned long parman_lsort_new_index_find(struct parman *parman,
115                                                  struct parman_prio *prio)
116 {
117         list_for_each_entry_from_reverse(prio, &parman->prio_list, list) {
118                 if (!parman_prio_used(prio))
119                         continue;
120                 return parman_prio_last_index(prio) + 1;
121         }
122         return 0;
123 }
124
125 static void __parman_prio_move(struct parman *parman, struct parman_prio *prio,
126                                struct parman_item *item, unsigned long to_index,
127                                unsigned long count)
128 {
129         parman->ops->move(parman->priv, item->index, to_index, count);
130 }
131
132 static void parman_prio_shift_down(struct parman *parman,
133                                    struct parman_prio *prio)
134 {
135         struct parman_item *item;
136         unsigned long to_index;
137
138         if (!parman_prio_used(prio))
139                 return;
140         item = parman_prio_first_item(prio);
141         to_index = parman_prio_last_index(prio) + 1;
142         __parman_prio_move(parman, prio, item, to_index, 1);
143         list_move_tail(&item->list, &prio->item_list);
144         item->index = to_index;
145 }
146
147 static void parman_prio_shift_up(struct parman *parman,
148                                  struct parman_prio *prio)
149 {
150         struct parman_item *item;
151         unsigned long to_index;
152
153         if (!parman_prio_used(prio))
154                 return;
155         item = parman_prio_last_item(prio);
156         to_index = parman_prio_first_index(prio) - 1;
157         __parman_prio_move(parman, prio, item, to_index, 1);
158         list_move(&item->list, &prio->item_list);
159         item->index = to_index;
160 }
161
162 static void parman_prio_item_remove(struct parman *parman,
163                                     struct parman_prio *prio,
164                                     struct parman_item *item)
165 {
166         struct parman_item *last_item;
167         unsigned long to_index;
168
169         last_item = parman_prio_last_item(prio);
170         if (last_item == item) {
171                 list_del(&item->list);
172                 return;
173         }
174         to_index = item->index;
175         __parman_prio_move(parman, prio, last_item, to_index, 1);
176         list_del(&last_item->list);
177         list_replace(&item->list, &last_item->list);
178         last_item->index = to_index;
179 }
180
181 static int parman_lsort_item_add(struct parman *parman,
182                                  struct parman_prio *prio,
183                                  struct parman_item *item)
184 {
185         struct parman_prio *prio2;
186         unsigned long new_index;
187         int err;
188
189         if (parman->count + 1 > parman->limit_count) {
190                 err = parman_enlarge(parman);
191                 if (err)
192                         return err;
193         }
194
195         new_index = parman_lsort_new_index_find(parman, prio);
196         list_for_each_entry_reverse(prio2, &parman->prio_list, list) {
197                 if (prio2 == prio)
198                         break;
199                 parman_prio_shift_down(parman, prio2);
200         }
201         item->index = new_index;
202         list_add_tail(&item->list, &prio->item_list);
203         parman->count++;
204         return 0;
205 }
206
207 static void parman_lsort_item_remove(struct parman *parman,
208                                      struct parman_prio *prio,
209                                      struct parman_item *item)
210 {
211         parman_prio_item_remove(parman, prio, item);
212         list_for_each_entry_continue(prio, &parman->prio_list, list)
213                 parman_prio_shift_up(parman, prio);
214         parman->count--;
215         if (parman->limit_count - parman->count >= parman->ops->resize_step)
216                 parman_shrink(parman);
217 }
218
219 static const struct parman_algo parman_lsort = {
220         .item_add       = parman_lsort_item_add,
221         .item_remove    = parman_lsort_item_remove,
222 };
223
224 static const struct parman_algo *parman_algos[] = {
225         &parman_lsort,
226 };
227
228 /**
229  * parman_create - creates a new parman instance
230  * @ops:        caller-specific callbacks
231  * @priv:       pointer to a private data passed to the ops
232  *
233  * Note: all locking must be provided by the caller.
234  *
235  * Each parman instance manages an array area with chunks of entries
236  * with the same priority. Consider following example:
237  *
238  * item 1 with prio 10
239  * item 2 with prio 10
240  * item 3 with prio 10
241  * item 4 with prio 20
242  * item 5 with prio 20
243  * item 6 with prio 30
244  * item 7 with prio 30
245  * item 8 with prio 30
246  *
247  * In this example, there are 3 priority chunks. The order of the priorities
248  * matters, however the order of items within a single priority chunk does not
249  * matter. So the same array could be ordered as follows:
250  *
251  * item 2 with prio 10
252  * item 3 with prio 10
253  * item 1 with prio 10
254  * item 5 with prio 20
255  * item 4 with prio 20
256  * item 7 with prio 30
257  * item 8 with prio 30
258  * item 6 with prio 30
259  *
260  * The goal of parman is to maintain the priority ordering. The caller
261  * provides @ops with callbacks parman uses to move the items
262  * and resize the array area.
263  *
264  * Returns a pointer to newly created parman instance in case of success,
265  * otherwise it returns NULL.
266  */
267 struct parman *parman_create(const struct parman_ops *ops, void *priv)
268 {
269         struct parman *parman;
270
271         parman = kzalloc(sizeof(*parman), GFP_KERNEL);
272         if (!parman)
273                 return NULL;
274         INIT_LIST_HEAD(&parman->prio_list);
275         parman->ops = ops;
276         parman->priv = priv;
277         parman->limit_count = ops->base_count;
278         parman->algo = parman_algos[ops->algo];
279         return parman;
280 }
281 EXPORT_SYMBOL(parman_create);
282
283 /**
284  * parman_destroy - destroys existing parman instance
285  * @parman:     parman instance
286  *
287  * Note: all locking must be provided by the caller.
288  */
289 void parman_destroy(struct parman *parman)
290 {
291         WARN_ON(!list_empty(&parman->prio_list));
292         kfree(parman);
293 }
294 EXPORT_SYMBOL(parman_destroy);
295
296 /**
297  * parman_prio_init - initializes a parman priority chunk
298  * @parman:     parman instance
299  * @prio:       parman prio structure to be initialized
300  * @priority:   desired priority of the chunk
301  *
302  * Note: all locking must be provided by the caller.
303  *
304  * Before caller could add an item with certain priority, he has to
305  * initialize a priority chunk for it using this function.
306  */
307 void parman_prio_init(struct parman *parman, struct parman_prio *prio,
308                       unsigned long priority)
309 {
310         struct parman_prio *prio2;
311         struct list_head *pos;
312
313         INIT_LIST_HEAD(&prio->item_list);
314         prio->priority = priority;
315
316         /* Position inside the list according to priority */
317         list_for_each(pos, &parman->prio_list) {
318                 prio2 = list_entry(pos, typeof(*prio2), list);
319                 if (prio2->priority > prio->priority)
320                         break;
321         }
322         list_add_tail(&prio->list, pos);
323 }
324 EXPORT_SYMBOL(parman_prio_init);
325
326 /**
327  * parman_prio_fini - finalizes use of parman priority chunk
328  * @prio:       parman prio structure
329  *
330  * Note: all locking must be provided by the caller.
331  */
332 void parman_prio_fini(struct parman_prio *prio)
333 {
334         WARN_ON(parman_prio_used(prio));
335         list_del(&prio->list);
336 }
337 EXPORT_SYMBOL(parman_prio_fini);
338
339 /**
340  * parman_item_add - adds a parman item under defined priority
341  * @parman:     parman instance
342  * @prio:       parman prio instance to add the item to
343  * @item:       parman item instance
344  *
345  * Note: all locking must be provided by the caller.
346  *
347  * Adds item to a array managed by parman instance under the specified priority.
348  *
349  * Returns 0 in case of success, negative number to indicate an error.
350  */
351 int parman_item_add(struct parman *parman, struct parman_prio *prio,
352                     struct parman_item *item)
353 {
354         return parman->algo->item_add(parman, prio, item);
355 }
356 EXPORT_SYMBOL(parman_item_add);
357
358 /**
359  * parman_item_remove - deletes parman item
360  * @parman:     parman instance
361  * @prio:       parman prio instance to delete the item from
362  * @item:       parman item instance
363  *
364  * Note: all locking must be provided by the caller.
365  */
366 void parman_item_remove(struct parman *parman, struct parman_prio *prio,
367                         struct parman_item *item)
368 {
369         parman->algo->item_remove(parman, prio, item);
370 }
371 EXPORT_SYMBOL(parman_item_remove);
372
373 MODULE_LICENSE("Dual BSD/GPL");
374 MODULE_AUTHOR("Jiri Pirko <jiri@mellanox.com>");
375 MODULE_DESCRIPTION("Priority-based array manager");