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 { 90 return !list_empty(&prio->item_list); 91 } 92 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 99 static unsigned long parman_prio_first_index(struct parman_prio *prio) 100 { 101 return parman_prio_first_item(prio)->index; 102 } 103 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 110 static unsigned long parman_prio_last_index(struct parman_prio *prio) 111 { 112 return parman_prio_last_item(prio)->index; 113 } 114 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 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 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 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 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 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 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 */ 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 */ 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 */ 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 */ 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 */ 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 */ 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