lib/parman.c

   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");