376 lines · c
1/*2 * lib/parman.c - Manager for linear priority array areas3 * 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 without7 * modification, are permitted provided that the following conditions are met:8 *9 * 1. Redistributions of source code must retain the above copyright10 * notice, this list of conditions and the following disclaimer.11 * 2. Redistributions in binary form must reproduce the above copyright12 * notice, this list of conditions and the following disclaimer in the13 * documentation and/or other materials provided with the distribution.14 * 3. Neither the names of the copyright holders nor the names of its15 * contributors may be used to endorse or promote products derived from16 * this software without specific prior written permission.17 *18 * Alternatively, this software may be distributed under the terms of the19 * GNU General Public License ("GPL") version 2 as published by the Free20 * 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, THE24 * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE25 * ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT OWNER OR CONTRIBUTORS BE26 * LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR27 * CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF28 * SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS29 * INTERRUPTION) HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN30 * 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 THE32 * 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 return !list_empty(&prio->item_list);90}91 92static 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 98static unsigned long parman_prio_first_index(struct parman_prio *prio)99{100 return parman_prio_first_item(prio)->index;101}102 103static 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 109static unsigned long parman_prio_last_index(struct parman_prio *prio)110{111 return parman_prio_last_item(prio)->index;112}113 114static 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 125static 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 132static 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 147static 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 162static 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 181static 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 207static 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 219static const struct parman_algo parman_lsort = {220 .item_add = parman_lsort_item_add,221 .item_remove = parman_lsort_item_remove,222};223 224static const struct parman_algo *parman_algos[] = {225 &parman_lsort,226};227 228/**229 * parman_create - creates a new parman instance230 * @ops: caller-specific callbacks231 * @priv: pointer to a private data passed to the ops232 *233 * Note: all locking must be provided by the caller.234 *235 * Each parman instance manages an array area with chunks of entries236 * with the same priority. Consider following example:237 *238 * item 1 with prio 10239 * item 2 with prio 10240 * item 3 with prio 10241 * item 4 with prio 20242 * item 5 with prio 20243 * item 6 with prio 30244 * item 7 with prio 30245 * item 8 with prio 30246 *247 * In this example, there are 3 priority chunks. The order of the priorities248 * matters, however the order of items within a single priority chunk does not249 * matter. So the same array could be ordered as follows:250 *251 * item 2 with prio 10252 * item 3 with prio 10253 * item 1 with prio 10254 * item 5 with prio 20255 * item 4 with prio 20256 * item 7 with prio 30257 * item 8 with prio 30258 * item 6 with prio 30259 *260 * The goal of parman is to maintain the priority ordering. The caller261 * provides @ops with callbacks parman uses to move the items262 * 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 */267struct 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}281EXPORT_SYMBOL(parman_create);282 283/**284 * parman_destroy - destroys existing parman instance285 * @parman: parman instance286 *287 * Note: all locking must be provided by the caller.288 */289void parman_destroy(struct parman *parman)290{291 WARN_ON(!list_empty(&parman->prio_list));292 kfree(parman);293}294EXPORT_SYMBOL(parman_destroy);295 296/**297 * parman_prio_init - initializes a parman priority chunk298 * @parman: parman instance299 * @prio: parman prio structure to be initialized300 * @priority: desired priority of the chunk301 *302 * Note: all locking must be provided by the caller.303 *304 * Before caller could add an item with certain priority, he has to305 * initialize a priority chunk for it using this function.306 */307void 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}324EXPORT_SYMBOL(parman_prio_init);325 326/**327 * parman_prio_fini - finalizes use of parman priority chunk328 * @prio: parman prio structure329 *330 * Note: all locking must be provided by the caller.331 */332void parman_prio_fini(struct parman_prio *prio)333{334 WARN_ON(parman_prio_used(prio));335 list_del(&prio->list);336}337EXPORT_SYMBOL(parman_prio_fini);338 339/**340 * parman_item_add - adds a parman item under defined priority341 * @parman: parman instance342 * @prio: parman prio instance to add the item to343 * @item: parman item instance344 *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 */351int 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}356EXPORT_SYMBOL(parman_item_add);357 358/**359 * parman_item_remove - deletes parman item360 * @parman: parman instance361 * @prio: parman prio instance to delete the item from362 * @item: parman item instance363 *364 * Note: all locking must be provided by the caller.365 */366void 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}371EXPORT_SYMBOL(parman_item_remove);372 373MODULE_LICENSE("Dual BSD/GPL");374MODULE_AUTHOR("Jiri Pirko <jiri@mellanox.com>");375MODULE_DESCRIPTION("Priority-based array manager");376