Commit | Line | Data |
---|---|---|
44091d29 JP |
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) | |
44091d29 JP |
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 | |
c95c2d32 | 300 | * @priority: desired priority of the chunk |
44091d29 JP |
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 | /** | |
c95c2d32 | 359 | * parman_item_remove - deletes parman item |
44091d29 JP |
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"); |