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