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 
parman_enlarge(struct parman * parman)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 
parman_shrink(struct parman * parman)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 
parman_prio_used(struct parman_prio * prio)87 static bool parman_prio_used(struct parman_prio *prio)
88 
89 {
90 	return !list_empty(&prio->item_list);
91 }
92 
parman_prio_first_item(struct parman_prio * prio)93 static 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 
parman_prio_first_index(struct parman_prio * prio)99 static unsigned long parman_prio_first_index(struct parman_prio *prio)
100 {
101 	return parman_prio_first_item(prio)->index;
102 }
103 
parman_prio_last_item(struct parman_prio * prio)104 static 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 
parman_prio_last_index(struct parman_prio * prio)110 static unsigned long parman_prio_last_index(struct parman_prio *prio)
111 {
112 	return parman_prio_last_item(prio)->index;
113 }
114 
parman_lsort_new_index_find(struct parman * parman,struct parman_prio * prio)115 static 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 
__parman_prio_move(struct parman * parman,struct parman_prio * prio,struct parman_item * item,unsigned long to_index,unsigned long count)126 static 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 
parman_prio_shift_down(struct parman * parman,struct parman_prio * prio)133 static 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 
parman_prio_shift_up(struct parman * parman,struct parman_prio * prio)148 static 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 
parman_prio_item_remove(struct parman * parman,struct parman_prio * prio,struct parman_item * item)163 static 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 
parman_lsort_item_add(struct parman * parman,struct parman_prio * prio,struct parman_item * item)182 static 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 
parman_lsort_item_remove(struct parman * parman,struct parman_prio * prio,struct parman_item * item)208 static 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 
220 static const struct parman_algo parman_lsort = {
221 	.item_add	= parman_lsort_item_add,
222 	.item_remove	= parman_lsort_item_remove,
223 };
224 
225 static 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  */
parman_create(const struct parman_ops * ops,void * priv)268 struct 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 }
282 EXPORT_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  */
parman_destroy(struct parman * parman)290 void parman_destroy(struct parman *parman)
291 {
292 	WARN_ON(!list_empty(&parman->prio_list));
293 	kfree(parman);
294 }
295 EXPORT_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  */
parman_prio_init(struct parman * parman,struct parman_prio * prio,unsigned long priority)308 void 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 }
325 EXPORT_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  */
parman_prio_fini(struct parman_prio * prio)333 void parman_prio_fini(struct parman_prio *prio)
334 {
335 	WARN_ON(parman_prio_used(prio));
336 	list_del(&prio->list);
337 }
338 EXPORT_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  */
parman_item_add(struct parman * parman,struct parman_prio * prio,struct parman_item * item)352 int 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 }
357 EXPORT_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  */
parman_item_remove(struct parman * parman,struct parman_prio * prio,struct parman_item * item)367 void 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 }
372 EXPORT_SYMBOL(parman_item_remove);
373 
374 MODULE_LICENSE("Dual BSD/GPL");
375 MODULE_AUTHOR("Jiri Pirko <jiri@mellanox.com>");
376 MODULE_DESCRIPTION("Priority-based array manager");
377