projects/linux·blob v5.0 · refs

376 lines · 10.6 KiB

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