1 /* 1
2 * lib/parman.c - Manager for linear priority
3 * Copyright (c) 2017 Mellanox Technologies. A
4 * Copyright (c) 2017 Jiri Pirko <jiri@mellano
5 *
6 * Redistribution and use in source and binary
7 * modification, are permitted provided that t
8 *
9 * 1. Redistributions of source code must reta
10 * notice, this list of conditions and the
11 * 2. Redistributions in binary form must repr
12 * notice, this list of conditions and the
13 * documentation and/or other materials pro
14 * 3. Neither the names of the copyright holde
15 * contributors may be used to endorse or p
16 * this software without specific prior wri
17 *
18 * Alternatively, this software may be distrib
19 * GNU General Public License ("GPL") version
20 * Software Foundation.
21 *
22 * THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT
23 * AND ANY EXPRESS OR IMPLIED WARRANTIES, INCL
24 * IMPLIED WARRANTIES OF MERCHANTABILITY AND F
25 * ARE DISCLAIMED. IN NO EVENT SHALL THE COPYR
26 * LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL
27 * CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT L
28 * SUBSTITUTE GOODS OR SERVICES; LOSS OF USE,
29 * INTERRUPTION) HOWEVER CAUSED AND ON ANY THE
30 * CONTRACT, STRICT LIABILITY, OR TORT (INCLUD
31 * ARISING IN ANY WAY OUT OF THE USE OF THIS S
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,
45 struct parman_item *it
46 void (*item_remove)(struct parman *par
47 struct parman_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 *parma
60 {
61 unsigned long new_count = parman->limi
62 parman->ops-
63 int err;
64
65 err = parman->ops->resize(parman->priv
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->limi
75 parman->ops-
76 int err;
77
78 if (new_count < parman->ops->base_coun
79 return 0;
80 err = parman->ops->resize(parman->priv
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_pri
88 {
89 return !list_empty(&prio->item_list);
90 }
91
92 static struct parman_item *parman_prio_first_i
93 {
94 return list_first_entry(&prio->item_li
95 typeof(struct
96 }
97
98 static unsigned long parman_prio_first_index(s
99 {
100 return parman_prio_first_item(prio)->i
101 }
102
103 static struct parman_item *parman_prio_last_it
104 {
105 return list_last_entry(&prio->item_lis
106 typeof(struct p
107 }
108
109 static unsigned long parman_prio_last_index(st
110 {
111 return parman_prio_last_item(prio)->in
112 }
113
114 static unsigned long parman_lsort_new_index_fi
115
116 {
117 list_for_each_entry_from_reverse(prio,
118 if (!parman_prio_used(prio))
119 continue;
120 return parman_prio_last_index(
121 }
122 return 0;
123 }
124
125 static void __parman_prio_move(struct parman *
126 struct parman_i
127 unsigned long c
128 {
129 parman->ops->move(parman->priv, item->
130 }
131
132 static void parman_prio_shift_down(struct parm
133 struct parm
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
142 __parman_prio_move(parman, prio, item,
143 list_move_tail(&item->list, &prio->ite
144 item->index = to_index;
145 }
146
147 static void parman_prio_shift_up(struct parman
148 struct parman
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(pri
157 __parman_prio_move(parman, prio, item,
158 list_move(&item->list, &prio->item_lis
159 item->index = to_index;
160 }
161
162 static void parman_prio_item_remove(struct par
163 struct par
164 struct par
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_
176 list_del(&last_item->list);
177 list_replace(&item->list, &last_item->
178 last_item->index = to_index;
179 }
180
181 static int parman_lsort_item_add(struct parman
182 struct parman
183 struct parman
184 {
185 struct parman_prio *prio2;
186 unsigned long new_index;
187 int err;
188
189 if (parman->count + 1 > parman->limit_
190 err = parman_enlarge(parman);
191 if (err)
192 return err;
193 }
194
195 new_index = parman_lsort_new_index_fin
196 list_for_each_entry_reverse(prio2, &pa
197 if (prio2 == prio)
198 break;
199 parman_prio_shift_down(parman,
200 }
201 item->index = new_index;
202 list_add_tail(&item->list, &prio->item
203 parman->count++;
204 return 0;
205 }
206
207 static void parman_lsort_item_remove(struct pa
208 struct pa
209 struct pa
210 {
211 parman_prio_item_remove(parman, prio,
212 list_for_each_entry_continue(prio, &pa
213 parman_prio_shift_up(parman, p
214 parman->count--;
215 if (parman->limit_count - parman->coun
216 parman_shrink(parman);
217 }
218
219 static const struct parman_algo parman_lsort =
220 .item_add = parman_lsort_item_ad
221 .item_remove = parman_lsort_item_re
222 };
223
224 static const struct parman_algo *parman_algos[
225 &parman_lsort,
226 };
227
228 /**
229 * parman_create - creates a new parman instan
230 * @ops: caller-specific callbacks
231 * @priv: pointer to a private data pass
232 *
233 * Note: all locking must be provided by the c
234 *
235 * Each parman instance manages an array area
236 * with the same priority. Consider following
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 chunk
248 * matters, however the order of items within
249 * matter. So the same array could be ordered
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 prior
261 * provides @ops with callbacks parman uses to
262 * and resize the array area.
263 *
264 * Returns a pointer to newly created parman i
265 * otherwise it returns NULL.
266 */
267 struct parman *parman_create(const struct parm
268 {
269 struct parman *parman;
270
271 parman = kzalloc(sizeof(*parman), GFP_
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 i
285 * @parman: parman instance
286 *
287 * Note: all locking must be provided by the c
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 pri
298 * @parman: parman instance
299 * @prio: parman prio structure to be in
300 * @priority: desired priority of the chunk
301 *
302 * Note: all locking must be provided by the c
303 *
304 * Before caller could add an item with certai
305 * initialize a priority chunk for it using th
306 */
307 void parman_prio_init(struct parman *parman, s
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
317 list_for_each(pos, &parman->prio_list)
318 prio2 = list_entry(pos, typeof
319 if (prio2->priority > prio->pr
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
328 * @prio: parman prio structure
329 *
330 * Note: all locking must be provided by the c
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
341 * @parman: parman instance
342 * @prio: parman prio instance to add th
343 * @item: parman item instance
344 *
345 * Note: all locking must be provided by the c
346 *
347 * Adds item to a array managed by parman inst
348 *
349 * Returns 0 in case of success, negative numb
350 */
351 int parman_item_add(struct parman *parman, str
352 struct parman_item *item)
353 {
354 return parman->algo->item_add(parman,
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
362 * @item: parman item instance
363 *
364 * Note: all locking must be provided by the c
365 */
366 void parman_item_remove(struct parman *parman,
367 struct parman_item *it
368 {
369 parman->algo->item_remove(parman, prio
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 manag
376
Linux® is a registered trademark of Linus Torvalds in the United States and other countries.
TOMOYO® is a registered trademark of NTT DATA CORPORATION.