1 /* 1 /*
2 * lib/parman.c - Manager for linear priority 2 * lib/parman.c - Manager for linear priority array areas
3 * Copyright (c) 2017 Mellanox Technologies. A 3 * Copyright (c) 2017 Mellanox Technologies. All rights reserved.
4 * Copyright (c) 2017 Jiri Pirko <jiri@mellano 4 * Copyright (c) 2017 Jiri Pirko <jiri@mellanox.com>
5 * 5 *
6 * Redistribution and use in source and binary 6 * Redistribution and use in source and binary forms, with or without
7 * modification, are permitted provided that t 7 * modification, are permitted provided that the following conditions are met:
8 * 8 *
9 * 1. Redistributions of source code must reta 9 * 1. Redistributions of source code must retain the above copyright
10 * notice, this list of conditions and the 10 * notice, this list of conditions and the following disclaimer.
11 * 2. Redistributions in binary form must repr 11 * 2. Redistributions in binary form must reproduce the above copyright
12 * notice, this list of conditions and the 12 * notice, this list of conditions and the following disclaimer in the
13 * documentation and/or other materials pro 13 * documentation and/or other materials provided with the distribution.
14 * 3. Neither the names of the copyright holde 14 * 3. Neither the names of the copyright holders nor the names of its
15 * contributors may be used to endorse or p 15 * contributors may be used to endorse or promote products derived from
16 * this software without specific prior wri 16 * this software without specific prior written permission.
17 * 17 *
18 * Alternatively, this software may be distrib 18 * Alternatively, this software may be distributed under the terms of the
19 * GNU General Public License ("GPL") version 19 * GNU General Public License ("GPL") version 2 as published by the Free
20 * Software Foundation. 20 * Software Foundation.
21 * 21 *
22 * THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT 22 * THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS "AS IS"
23 * AND ANY EXPRESS OR IMPLIED WARRANTIES, INCL 23 * AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE
24 * IMPLIED WARRANTIES OF MERCHANTABILITY AND F 24 * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE
25 * ARE DISCLAIMED. IN NO EVENT SHALL THE COPYR 25 * ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT OWNER OR CONTRIBUTORS BE
26 * LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL 26 * LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR
27 * CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT L 27 * CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF
28 * SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, 28 * SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS
29 * INTERRUPTION) HOWEVER CAUSED AND ON ANY THE 29 * INTERRUPTION) HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN
30 * CONTRACT, STRICT LIABILITY, OR TORT (INCLUD 30 * CONTRACT, STRICT LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE)
31 * ARISING IN ANY WAY OUT OF THE USE OF THIS S 31 * ARISING IN ANY WAY OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE
32 * POSSIBILITY OF SUCH DAMAGE. 32 * POSSIBILITY OF SUCH DAMAGE.
33 */ 33 */
34 34
35 #include <linux/kernel.h> 35 #include <linux/kernel.h>
36 #include <linux/module.h> 36 #include <linux/module.h>
37 #include <linux/slab.h> 37 #include <linux/slab.h>
38 #include <linux/export.h> 38 #include <linux/export.h>
39 #include <linux/list.h> 39 #include <linux/list.h>
40 #include <linux/err.h> 40 #include <linux/err.h>
41 #include <linux/parman.h> 41 #include <linux/parman.h>
42 42
43 struct parman_algo { 43 struct parman_algo {
44 int (*item_add)(struct parman *parman, 44 int (*item_add)(struct parman *parman, struct parman_prio *prio,
45 struct parman_item *it 45 struct parman_item *item);
46 void (*item_remove)(struct parman *par 46 void (*item_remove)(struct parman *parman, struct parman_prio *prio,
47 struct parman_item 47 struct parman_item *item);
48 }; 48 };
49 49
50 struct parman { 50 struct parman {
51 const struct parman_ops *ops; 51 const struct parman_ops *ops;
52 void *priv; 52 void *priv;
53 const struct parman_algo *algo; 53 const struct parman_algo *algo;
54 unsigned long count; 54 unsigned long count;
55 unsigned long limit_count; 55 unsigned long limit_count;
56 struct list_head prio_list; 56 struct list_head prio_list;
57 }; 57 };
58 58
59 static int parman_enlarge(struct parman *parma 59 static int parman_enlarge(struct parman *parman)
60 { 60 {
61 unsigned long new_count = parman->limi 61 unsigned long new_count = parman->limit_count +
62 parman->ops- 62 parman->ops->resize_step;
63 int err; 63 int err;
64 64
65 err = parman->ops->resize(parman->priv 65 err = parman->ops->resize(parman->priv, new_count);
66 if (err) 66 if (err)
67 return err; 67 return err;
68 parman->limit_count = new_count; 68 parman->limit_count = new_count;
69 return 0; 69 return 0;
70 } 70 }
71 71
72 static int parman_shrink(struct parman *parman 72 static int parman_shrink(struct parman *parman)
73 { 73 {
74 unsigned long new_count = parman->limi 74 unsigned long new_count = parman->limit_count -
75 parman->ops- 75 parman->ops->resize_step;
76 int err; 76 int err;
77 77
78 if (new_count < parman->ops->base_coun 78 if (new_count < parman->ops->base_count)
79 return 0; 79 return 0;
80 err = parman->ops->resize(parman->priv 80 err = parman->ops->resize(parman->priv, new_count);
81 if (err) 81 if (err)
82 return err; 82 return err;
83 parman->limit_count = new_count; 83 parman->limit_count = new_count;
84 return 0; 84 return 0;
85 } 85 }
86 86
87 static bool parman_prio_used(struct parman_pri 87 static bool parman_prio_used(struct parman_prio *prio)
>> 88
88 { 89 {
89 return !list_empty(&prio->item_list); 90 return !list_empty(&prio->item_list);
90 } 91 }
91 92
92 static struct parman_item *parman_prio_first_i 93 static struct parman_item *parman_prio_first_item(struct parman_prio *prio)
93 { 94 {
94 return list_first_entry(&prio->item_li 95 return list_first_entry(&prio->item_list,
95 typeof(struct 96 typeof(struct parman_item), list);
96 } 97 }
97 98
98 static unsigned long parman_prio_first_index(s 99 static unsigned long parman_prio_first_index(struct parman_prio *prio)
99 { 100 {
100 return parman_prio_first_item(prio)->i 101 return parman_prio_first_item(prio)->index;
101 } 102 }
102 103
103 static struct parman_item *parman_prio_last_it 104 static struct parman_item *parman_prio_last_item(struct parman_prio *prio)
104 { 105 {
105 return list_last_entry(&prio->item_lis 106 return list_last_entry(&prio->item_list,
106 typeof(struct p 107 typeof(struct parman_item), list);
107 } 108 }
108 109
109 static unsigned long parman_prio_last_index(st 110 static unsigned long parman_prio_last_index(struct parman_prio *prio)
110 { 111 {
111 return parman_prio_last_item(prio)->in 112 return parman_prio_last_item(prio)->index;
112 } 113 }
113 114
114 static unsigned long parman_lsort_new_index_fi 115 static unsigned long parman_lsort_new_index_find(struct parman *parman,
115 116 struct parman_prio *prio)
116 { 117 {
117 list_for_each_entry_from_reverse(prio, 118 list_for_each_entry_from_reverse(prio, &parman->prio_list, list) {
118 if (!parman_prio_used(prio)) 119 if (!parman_prio_used(prio))
119 continue; 120 continue;
120 return parman_prio_last_index( 121 return parman_prio_last_index(prio) + 1;
121 } 122 }
122 return 0; 123 return 0;
123 } 124 }
124 125
125 static void __parman_prio_move(struct parman * 126 static void __parman_prio_move(struct parman *parman, struct parman_prio *prio,
126 struct parman_i 127 struct parman_item *item, unsigned long to_index,
127 unsigned long c 128 unsigned long count)
128 { 129 {
129 parman->ops->move(parman->priv, item-> 130 parman->ops->move(parman->priv, item->index, to_index, count);
130 } 131 }
131 132
132 static void parman_prio_shift_down(struct parm 133 static void parman_prio_shift_down(struct parman *parman,
133 struct parm 134 struct parman_prio *prio)
134 { 135 {
135 struct parman_item *item; 136 struct parman_item *item;
136 unsigned long to_index; 137 unsigned long to_index;
137 138
138 if (!parman_prio_used(prio)) 139 if (!parman_prio_used(prio))
139 return; 140 return;
140 item = parman_prio_first_item(prio); 141 item = parman_prio_first_item(prio);
141 to_index = parman_prio_last_index(prio 142 to_index = parman_prio_last_index(prio) + 1;
142 __parman_prio_move(parman, prio, item, 143 __parman_prio_move(parman, prio, item, to_index, 1);
143 list_move_tail(&item->list, &prio->ite 144 list_move_tail(&item->list, &prio->item_list);
144 item->index = to_index; 145 item->index = to_index;
145 } 146 }
146 147
147 static void parman_prio_shift_up(struct parman 148 static void parman_prio_shift_up(struct parman *parman,
148 struct parman 149 struct parman_prio *prio)
149 { 150 {
150 struct parman_item *item; 151 struct parman_item *item;
151 unsigned long to_index; 152 unsigned long to_index;
152 153
153 if (!parman_prio_used(prio)) 154 if (!parman_prio_used(prio))
154 return; 155 return;
155 item = parman_prio_last_item(prio); 156 item = parman_prio_last_item(prio);
156 to_index = parman_prio_first_index(pri 157 to_index = parman_prio_first_index(prio) - 1;
157 __parman_prio_move(parman, prio, item, 158 __parman_prio_move(parman, prio, item, to_index, 1);
158 list_move(&item->list, &prio->item_lis 159 list_move(&item->list, &prio->item_list);
159 item->index = to_index; 160 item->index = to_index;
160 } 161 }
161 162
162 static void parman_prio_item_remove(struct par 163 static void parman_prio_item_remove(struct parman *parman,
163 struct par 164 struct parman_prio *prio,
164 struct par 165 struct parman_item *item)
165 { 166 {
166 struct parman_item *last_item; 167 struct parman_item *last_item;
167 unsigned long to_index; 168 unsigned long to_index;
168 169
169 last_item = parman_prio_last_item(prio 170 last_item = parman_prio_last_item(prio);
170 if (last_item == item) { 171 if (last_item == item) {
171 list_del(&item->list); 172 list_del(&item->list);
172 return; 173 return;
173 } 174 }
174 to_index = item->index; 175 to_index = item->index;
175 __parman_prio_move(parman, prio, last_ 176 __parman_prio_move(parman, prio, last_item, to_index, 1);
176 list_del(&last_item->list); 177 list_del(&last_item->list);
177 list_replace(&item->list, &last_item-> 178 list_replace(&item->list, &last_item->list);
178 last_item->index = to_index; 179 last_item->index = to_index;
179 } 180 }
180 181
181 static int parman_lsort_item_add(struct parman 182 static int parman_lsort_item_add(struct parman *parman,
182 struct parman 183 struct parman_prio *prio,
183 struct parman 184 struct parman_item *item)
184 { 185 {
185 struct parman_prio *prio2; 186 struct parman_prio *prio2;
186 unsigned long new_index; 187 unsigned long new_index;
187 int err; 188 int err;
188 189
189 if (parman->count + 1 > parman->limit_ 190 if (parman->count + 1 > parman->limit_count) {
190 err = parman_enlarge(parman); 191 err = parman_enlarge(parman);
191 if (err) 192 if (err)
192 return err; 193 return err;
193 } 194 }
194 195
195 new_index = parman_lsort_new_index_fin 196 new_index = parman_lsort_new_index_find(parman, prio);
196 list_for_each_entry_reverse(prio2, &pa 197 list_for_each_entry_reverse(prio2, &parman->prio_list, list) {
197 if (prio2 == prio) 198 if (prio2 == prio)
198 break; 199 break;
199 parman_prio_shift_down(parman, 200 parman_prio_shift_down(parman, prio2);
200 } 201 }
201 item->index = new_index; 202 item->index = new_index;
202 list_add_tail(&item->list, &prio->item 203 list_add_tail(&item->list, &prio->item_list);
203 parman->count++; 204 parman->count++;
204 return 0; 205 return 0;
205 } 206 }
206 207
207 static void parman_lsort_item_remove(struct pa 208 static void parman_lsort_item_remove(struct parman *parman,
208 struct pa 209 struct parman_prio *prio,
209 struct pa 210 struct parman_item *item)
210 { 211 {
211 parman_prio_item_remove(parman, prio, 212 parman_prio_item_remove(parman, prio, item);
212 list_for_each_entry_continue(prio, &pa 213 list_for_each_entry_continue(prio, &parman->prio_list, list)
213 parman_prio_shift_up(parman, p 214 parman_prio_shift_up(parman, prio);
214 parman->count--; 215 parman->count--;
215 if (parman->limit_count - parman->coun 216 if (parman->limit_count - parman->count >= parman->ops->resize_step)
216 parman_shrink(parman); 217 parman_shrink(parman);
217 } 218 }
218 219
219 static const struct parman_algo parman_lsort = 220 static const struct parman_algo parman_lsort = {
220 .item_add = parman_lsort_item_ad 221 .item_add = parman_lsort_item_add,
221 .item_remove = parman_lsort_item_re 222 .item_remove = parman_lsort_item_remove,
222 }; 223 };
223 224
224 static const struct parman_algo *parman_algos[ 225 static const struct parman_algo *parman_algos[] = {
225 &parman_lsort, 226 &parman_lsort,
226 }; 227 };
227 228
228 /** 229 /**
229 * parman_create - creates a new parman instan 230 * parman_create - creates a new parman instance
230 * @ops: caller-specific callbacks 231 * @ops: caller-specific callbacks
231 * @priv: pointer to a private data pass 232 * @priv: pointer to a private data passed to the ops
232 * 233 *
233 * Note: all locking must be provided by the c 234 * Note: all locking must be provided by the caller.
234 * 235 *
235 * Each parman instance manages an array area 236 * Each parman instance manages an array area with chunks of entries
236 * with the same priority. Consider following 237 * with the same priority. Consider following example:
237 * 238 *
238 * item 1 with prio 10 239 * item 1 with prio 10
239 * item 2 with prio 10 240 * item 2 with prio 10
240 * item 3 with prio 10 241 * item 3 with prio 10
241 * item 4 with prio 20 242 * item 4 with prio 20
242 * item 5 with prio 20 243 * item 5 with prio 20
243 * item 6 with prio 30 244 * item 6 with prio 30
244 * item 7 with prio 30 245 * item 7 with prio 30
245 * item 8 with prio 30 246 * item 8 with prio 30
246 * 247 *
247 * In this example, there are 3 priority chunk 248 * In this example, there are 3 priority chunks. The order of the priorities
248 * matters, however the order of items within 249 * matters, however the order of items within a single priority chunk does not
249 * matter. So the same array could be ordered 250 * matter. So the same array could be ordered as follows:
250 * 251 *
251 * item 2 with prio 10 252 * item 2 with prio 10
252 * item 3 with prio 10 253 * item 3 with prio 10
253 * item 1 with prio 10 254 * item 1 with prio 10
254 * item 5 with prio 20 255 * item 5 with prio 20
255 * item 4 with prio 20 256 * item 4 with prio 20
256 * item 7 with prio 30 257 * item 7 with prio 30
257 * item 8 with prio 30 258 * item 8 with prio 30
258 * item 6 with prio 30 259 * item 6 with prio 30
259 * 260 *
260 * The goal of parman is to maintain the prior 261 * The goal of parman is to maintain the priority ordering. The caller
261 * provides @ops with callbacks parman uses to 262 * provides @ops with callbacks parman uses to move the items
262 * and resize the array area. 263 * and resize the array area.
263 * 264 *
264 * Returns a pointer to newly created parman i 265 * Returns a pointer to newly created parman instance in case of success,
265 * otherwise it returns NULL. 266 * otherwise it returns NULL.
266 */ 267 */
267 struct parman *parman_create(const struct parm 268 struct parman *parman_create(const struct parman_ops *ops, void *priv)
268 { 269 {
269 struct parman *parman; 270 struct parman *parman;
270 271
271 parman = kzalloc(sizeof(*parman), GFP_ 272 parman = kzalloc(sizeof(*parman), GFP_KERNEL);
272 if (!parman) 273 if (!parman)
273 return NULL; 274 return NULL;
274 INIT_LIST_HEAD(&parman->prio_list); 275 INIT_LIST_HEAD(&parman->prio_list);
275 parman->ops = ops; 276 parman->ops = ops;
276 parman->priv = priv; 277 parman->priv = priv;
277 parman->limit_count = ops->base_count; 278 parman->limit_count = ops->base_count;
278 parman->algo = parman_algos[ops->algo] 279 parman->algo = parman_algos[ops->algo];
279 return parman; 280 return parman;
280 } 281 }
281 EXPORT_SYMBOL(parman_create); 282 EXPORT_SYMBOL(parman_create);
282 283
283 /** 284 /**
284 * parman_destroy - destroys existing parman i 285 * parman_destroy - destroys existing parman instance
285 * @parman: parman instance 286 * @parman: parman instance
286 * 287 *
287 * Note: all locking must be provided by the c 288 * Note: all locking must be provided by the caller.
288 */ 289 */
289 void parman_destroy(struct parman *parman) 290 void parman_destroy(struct parman *parman)
290 { 291 {
291 WARN_ON(!list_empty(&parman->prio_list 292 WARN_ON(!list_empty(&parman->prio_list));
292 kfree(parman); 293 kfree(parman);
293 } 294 }
294 EXPORT_SYMBOL(parman_destroy); 295 EXPORT_SYMBOL(parman_destroy);
295 296
296 /** 297 /**
297 * parman_prio_init - initializes a parman pri 298 * parman_prio_init - initializes a parman priority chunk
298 * @parman: parman instance 299 * @parman: parman instance
299 * @prio: parman prio structure to be in 300 * @prio: parman prio structure to be initialized
300 * @priority: desired priority of the chunk !! 301 * @prority: desired priority of the chunk
301 * 302 *
302 * Note: all locking must be provided by the c 303 * Note: all locking must be provided by the caller.
303 * 304 *
304 * Before caller could add an item with certai 305 * Before caller could add an item with certain priority, he has to
305 * initialize a priority chunk for it using th 306 * initialize a priority chunk for it using this function.
306 */ 307 */
307 void parman_prio_init(struct parman *parman, s 308 void parman_prio_init(struct parman *parman, struct parman_prio *prio,
308 unsigned long priority) 309 unsigned long priority)
309 { 310 {
310 struct parman_prio *prio2; 311 struct parman_prio *prio2;
311 struct list_head *pos; 312 struct list_head *pos;
312 313
313 INIT_LIST_HEAD(&prio->item_list); 314 INIT_LIST_HEAD(&prio->item_list);
314 prio->priority = priority; 315 prio->priority = priority;
315 316
316 /* Position inside the list according 317 /* Position inside the list according to priority */
317 list_for_each(pos, &parman->prio_list) 318 list_for_each(pos, &parman->prio_list) {
318 prio2 = list_entry(pos, typeof 319 prio2 = list_entry(pos, typeof(*prio2), list);
319 if (prio2->priority > prio->pr 320 if (prio2->priority > prio->priority)
320 break; 321 break;
321 } 322 }
322 list_add_tail(&prio->list, pos); 323 list_add_tail(&prio->list, pos);
323 } 324 }
324 EXPORT_SYMBOL(parman_prio_init); 325 EXPORT_SYMBOL(parman_prio_init);
325 326
326 /** 327 /**
327 * parman_prio_fini - finalizes use of parman 328 * parman_prio_fini - finalizes use of parman priority chunk
328 * @prio: parman prio structure 329 * @prio: parman prio structure
329 * 330 *
330 * Note: all locking must be provided by the c 331 * Note: all locking must be provided by the caller.
331 */ 332 */
332 void parman_prio_fini(struct parman_prio *prio 333 void parman_prio_fini(struct parman_prio *prio)
333 { 334 {
334 WARN_ON(parman_prio_used(prio)); 335 WARN_ON(parman_prio_used(prio));
335 list_del(&prio->list); 336 list_del(&prio->list);
336 } 337 }
337 EXPORT_SYMBOL(parman_prio_fini); 338 EXPORT_SYMBOL(parman_prio_fini);
338 339
339 /** 340 /**
340 * parman_item_add - adds a parman item under 341 * parman_item_add - adds a parman item under defined priority
341 * @parman: parman instance 342 * @parman: parman instance
342 * @prio: parman prio instance to add th 343 * @prio: parman prio instance to add the item to
343 * @item: parman item instance 344 * @item: parman item instance
344 * 345 *
345 * Note: all locking must be provided by the c 346 * Note: all locking must be provided by the caller.
346 * 347 *
347 * Adds item to a array managed by parman inst 348 * Adds item to a array managed by parman instance under the specified priority.
348 * 349 *
349 * Returns 0 in case of success, negative numb 350 * Returns 0 in case of success, negative number to indicate an error.
350 */ 351 */
351 int parman_item_add(struct parman *parman, str 352 int parman_item_add(struct parman *parman, struct parman_prio *prio,
352 struct parman_item *item) 353 struct parman_item *item)
353 { 354 {
354 return parman->algo->item_add(parman, 355 return parman->algo->item_add(parman, prio, item);
355 } 356 }
356 EXPORT_SYMBOL(parman_item_add); 357 EXPORT_SYMBOL(parman_item_add);
357 358
358 /** 359 /**
359 * parman_item_remove - deletes parman item !! 360 * parman_item_del - deletes parman item
360 * @parman: parman instance 361 * @parman: parman instance
361 * @prio: parman prio instance to delete 362 * @prio: parman prio instance to delete the item from
362 * @item: parman item instance 363 * @item: parman item instance
363 * 364 *
364 * Note: all locking must be provided by the c 365 * Note: all locking must be provided by the caller.
365 */ 366 */
366 void parman_item_remove(struct parman *parman, 367 void parman_item_remove(struct parman *parman, struct parman_prio *prio,
367 struct parman_item *it 368 struct parman_item *item)
368 { 369 {
369 parman->algo->item_remove(parman, prio 370 parman->algo->item_remove(parman, prio, item);
370 } 371 }
371 EXPORT_SYMBOL(parman_item_remove); 372 EXPORT_SYMBOL(parman_item_remove);
372 373
373 MODULE_LICENSE("Dual BSD/GPL"); 374 MODULE_LICENSE("Dual BSD/GPL");
374 MODULE_AUTHOR("Jiri Pirko <jiri@mellanox.com>" 375 MODULE_AUTHOR("Jiri Pirko <jiri@mellanox.com>");
375 MODULE_DESCRIPTION("Priority-based array manag 376 MODULE_DESCRIPTION("Priority-based array manager");
376 377
Linux® is a registered trademark of Linus Torvalds in the United States and other countries.
TOMOYO® is a registered trademark of NTT DATA CORPORATION.