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