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(head: &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, count: 1); |
143 | list_move_tail(list: &item->list, head: &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, count: 1); |
158 | list_move(list: &item->list, head: &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(entry: &item->list); |
172 | return; |
173 | } |
174 | to_index = item->index; |
175 | __parman_prio_move(parman, prio, item: last_item, to_index, count: 1); |
176 | list_del(entry: &last_item->list); |
177 | list_replace(old: &item->list, new: &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, prio: prio2); |
200 | } |
201 | item->index = new_index; |
202 | list_add_tail(new: &item->list, head: &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(size: sizeof(*parman), GFP_KERNEL); |
272 | if (!parman) |
273 | return NULL; |
274 | INIT_LIST_HEAD(list: &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(objp: 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(list: &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(new: &prio->list, head: 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(entry: &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" ); |
376 | |