the-tree/lib/parman.c

0001 /*
0002  * lib/parman.c - Manager for linear priority array areas
0003  * Copyright (c) 2017 Mellanox Technologies. All rights reserved.
0004  * Copyright (c) 2017 Jiri Pirko <jiri@mellanox.com>
0005  *
0006  * Redistribution and use in source and binary forms, with or without
0007  * modification, are permitted provided that the following conditions are met:
0008  *
0009  * 1. Redistributions of source code must retain the above copyright
0010  *    notice, this list of conditions and the following disclaimer.
0011  * 2. Redistributions in binary form must reproduce the above copyright
0012  *    notice, this list of conditions and the following disclaimer in the
0013  *    documentation and/or other materials provided with the distribution.
0014  * 3. Neither the names of the copyright holders nor the names of its
0015  *    contributors may be used to endorse or promote products derived from
0016  *    this software without specific prior written permission.
0017  *
0018  * Alternatively, this software may be distributed under the terms of the
0019  * GNU General Public License ("GPL") version 2 as published by the Free
0020  * Software Foundation.
0021  *
0022  * THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS "AS IS"
0023  * AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE
0024  * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE
0025  * ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT OWNER OR CONTRIBUTORS BE
0026  * LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR
0027  * CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF
0028  * SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS
0029  * INTERRUPTION) HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN
0030  * CONTRACT, STRICT LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE)
0031  * ARISING IN ANY WAY OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE
0032  * POSSIBILITY OF SUCH DAMAGE.
0033  */
0034
0035 #include <linux/kernel.h>
0036 #include <linux/module.h>
0037 #include <linux/slab.h>
0038 #include <linux/export.h>
0039 #include <linux/list.h>
0040 #include <linux/err.h>
0041 #include <linux/parman.h>
0042
0043 struct parman_algo {
0044     int (*item_add)(struct parman *parman, struct parman_prio *prio,
0045             struct parman_item *item);
0046     void (*item_remove)(struct parman *parman, struct parman_prio *prio,
0047                 struct parman_item *item);
0048 };
0049
0050 struct parman {
0051     const struct parman_ops *ops;
0052     void *priv;
0053     const struct parman_algo *algo;
0054     unsigned long count;
0055     unsigned long limit_count;
0056     struct list_head prio_list;
0057 };
0058
0059 static int parman_enlarge(struct parman *parman)
0060 {
0061     unsigned long new_count = parman->limit_count +
0062                   parman->ops->resize_step;
0063     int err;
0064
0065     err = parman->ops->resize(parman->priv, new_count);
0066     if (err)
0067         return err;
0068     parman->limit_count = new_count;
0069     return 0;
0070 }
0071
0072 static int parman_shrink(struct parman *parman)
0073 {
0074     unsigned long new_count = parman->limit_count -
0075                   parman->ops->resize_step;
0076     int err;
0077
0078     if (new_count < parman->ops->base_count)
0079         return 0;
0080     err = parman->ops->resize(parman->priv, new_count);
0081     if (err)
0082         return err;
0083     parman->limit_count = new_count;
0084     return 0;
0085 }
0086
0087 static bool parman_prio_used(struct parman_prio *prio)
0088 {
0089     return !list_empty(&prio->item_list);
0090 }
0091
0092 static struct parman_item *parman_prio_first_item(struct parman_prio *prio)
0093 {
0094     return list_first_entry(&prio->item_list,
0095                 typeof(struct parman_item), list);
0096 }
0097
0098 static unsigned long parman_prio_first_index(struct parman_prio *prio)
0099 {
0100     return parman_prio_first_item(prio)->index;
0101 }
0102
0103 static struct parman_item *parman_prio_last_item(struct parman_prio *prio)
0104 {
0105     return list_last_entry(&prio->item_list,
0106                    typeof(struct parman_item), list);
0107 }
0108
0109 static unsigned long parman_prio_last_index(struct parman_prio *prio)
0110 {
0111     return parman_prio_last_item(prio)->index;
0112 }
0113
0114 static unsigned long parman_lsort_new_index_find(struct parman *parman,
0115                          struct parman_prio *prio)
0116 {
0117     list_for_each_entry_from_reverse(prio, &parman->prio_list, list) {
0118         if (!parman_prio_used(prio))
0119             continue;
0120         return parman_prio_last_index(prio) + 1;
0121     }
0122     return 0;
0123 }
0124
0125 static void __parman_prio_move(struct parman *parman, struct parman_prio *prio,
0126                    struct parman_item *item, unsigned long to_index,
0127                    unsigned long count)
0128 {
0129     parman->ops->move(parman->priv, item->index, to_index, count);
0130 }
0131
0132 static void parman_prio_shift_down(struct parman *parman,
0133                    struct parman_prio *prio)
0134 {
0135     struct parman_item *item;
0136     unsigned long to_index;
0137
0138     if (!parman_prio_used(prio))
0139         return;
0140     item = parman_prio_first_item(prio);
0141     to_index = parman_prio_last_index(prio) + 1;
0142     __parman_prio_move(parman, prio, item, to_index, 1);
0143     list_move_tail(&item->list, &prio->item_list);
0144     item->index = to_index;
0145 }
0146
0147 static void parman_prio_shift_up(struct parman *parman,
0148                  struct parman_prio *prio)
0149 {
0150     struct parman_item *item;
0151     unsigned long to_index;
0152
0153     if (!parman_prio_used(prio))
0154         return;
0155     item = parman_prio_last_item(prio);
0156     to_index = parman_prio_first_index(prio) - 1;
0157     __parman_prio_move(parman, prio, item, to_index, 1);
0158     list_move(&item->list, &prio->item_list);
0159     item->index = to_index;
0160 }
0161
0162 static void parman_prio_item_remove(struct parman *parman,
0163                     struct parman_prio *prio,
0164                     struct parman_item *item)
0165 {
0166     struct parman_item *last_item;
0167     unsigned long to_index;
0168
0169     last_item = parman_prio_last_item(prio);
0170     if (last_item == item) {
0171         list_del(&item->list);
0172         return;
0173     }
0174     to_index = item->index;
0175     __parman_prio_move(parman, prio, last_item, to_index, 1);
0176     list_del(&last_item->list);
0177     list_replace(&item->list, &last_item->list);
0178     last_item->index = to_index;
0179 }
0180
0181 static int parman_lsort_item_add(struct parman *parman,
0182                  struct parman_prio *prio,
0183                  struct parman_item *item)
0184 {
0185     struct parman_prio *prio2;
0186     unsigned long new_index;
0187     int err;
0188
0189     if (parman->count + 1 > parman->limit_count) {
0190         err = parman_enlarge(parman);
0191         if (err)
0192             return err;
0193     }
0194
0195     new_index = parman_lsort_new_index_find(parman, prio);
0196     list_for_each_entry_reverse(prio2, &parman->prio_list, list) {
0197         if (prio2 == prio)
0198             break;
0199         parman_prio_shift_down(parman, prio2);
0200     }
0201     item->index = new_index;
0202     list_add_tail(&item->list, &prio->item_list);
0203     parman->count++;
0204     return 0;
0205 }
0206
0207 static void parman_lsort_item_remove(struct parman *parman,
0208                      struct parman_prio *prio,
0209                      struct parman_item *item)
0210 {
0211     parman_prio_item_remove(parman, prio, item);
0212     list_for_each_entry_continue(prio, &parman->prio_list, list)
0213         parman_prio_shift_up(parman, prio);
0214     parman->count--;
0215     if (parman->limit_count - parman->count >= parman->ops->resize_step)
0216         parman_shrink(parman);
0217 }
0218
0219 static const struct parman_algo parman_lsort = {
0220     .item_add   = parman_lsort_item_add,
0221     .item_remove    = parman_lsort_item_remove,
0222 };
0223
0224 static const struct parman_algo *parman_algos[] = {
0225     &parman_lsort,
0226 };
0227
0228 /**
0229  * parman_create - creates a new parman instance
0230  * @ops:    caller-specific callbacks
0231  * @priv:   pointer to a private data passed to the ops
0232  *
0233  * Note: all locking must be provided by the caller.
0234  *
0235  * Each parman instance manages an array area with chunks of entries
0236  * with the same priority. Consider following example:
0237  *
0238  * item 1 with prio 10
0239  * item 2 with prio 10
0240  * item 3 with prio 10
0241  * item 4 with prio 20
0242  * item 5 with prio 20
0243  * item 6 with prio 30
0244  * item 7 with prio 30
0245  * item 8 with prio 30
0246  *
0247  * In this example, there are 3 priority chunks. The order of the priorities
0248  * matters, however the order of items within a single priority chunk does not
0249  * matter. So the same array could be ordered as follows:
0250  *
0251  * item 2 with prio 10
0252  * item 3 with prio 10
0253  * item 1 with prio 10
0254  * item 5 with prio 20
0255  * item 4 with prio 20
0256  * item 7 with prio 30
0257  * item 8 with prio 30
0258  * item 6 with prio 30
0259  *
0260  * The goal of parman is to maintain the priority ordering. The caller
0261  * provides @ops with callbacks parman uses to move the items
0262  * and resize the array area.
0263  *
0264  * Returns a pointer to newly created parman instance in case of success,
0265  * otherwise it returns NULL.
0266  */
0267 struct parman *parman_create(const struct parman_ops *ops, void *priv)
0268 {
0269     struct parman *parman;
0270
0271     parman = kzalloc(sizeof(*parman), GFP_KERNEL);
0272     if (!parman)
0273         return NULL;
0274     INIT_LIST_HEAD(&parman->prio_list);
0275     parman->ops = ops;
0276     parman->priv = priv;
0277     parman->limit_count = ops->base_count;
0278     parman->algo = parman_algos[ops->algo];
0279     return parman;
0280 }
0281 EXPORT_SYMBOL(parman_create);
0282
0283 /**
0284  * parman_destroy - destroys existing parman instance
0285  * @parman: parman instance
0286  *
0287  * Note: all locking must be provided by the caller.
0288  */
0289 void parman_destroy(struct parman *parman)
0290 {
0291     WARN_ON(!list_empty(&parman->prio_list));
0292     kfree(parman);
0293 }
0294 EXPORT_SYMBOL(parman_destroy);
0295
0296 /**
0297  * parman_prio_init - initializes a parman priority chunk
0298  * @parman: parman instance
0299  * @prio:   parman prio structure to be initialized
0300  * @priority:   desired priority of the chunk
0301  *
0302  * Note: all locking must be provided by the caller.
0303  *
0304  * Before caller could add an item with certain priority, he has to
0305  * initialize a priority chunk for it using this function.
0306  */
0307 void parman_prio_init(struct parman *parman, struct parman_prio *prio,
0308               unsigned long priority)
0309 {
0310     struct parman_prio *prio2;
0311     struct list_head *pos;
0312
0313     INIT_LIST_HEAD(&prio->item_list);
0314     prio->priority = priority;
0315
0316     /* Position inside the list according to priority */
0317     list_for_each(pos, &parman->prio_list) {
0318         prio2 = list_entry(pos, typeof(*prio2), list);
0319         if (prio2->priority > prio->priority)
0320             break;
0321     }
0322     list_add_tail(&prio->list, pos);
0323 }
0324 EXPORT_SYMBOL(parman_prio_init);
0325
0326 /**
0327  * parman_prio_fini - finalizes use of parman priority chunk
0328  * @prio:   parman prio structure
0329  *
0330  * Note: all locking must be provided by the caller.
0331  */
0332 void parman_prio_fini(struct parman_prio *prio)
0333 {
0334     WARN_ON(parman_prio_used(prio));
0335     list_del(&prio->list);
0336 }
0337 EXPORT_SYMBOL(parman_prio_fini);
0338
0339 /**
0340  * parman_item_add - adds a parman item under defined priority
0341  * @parman: parman instance
0342  * @prio:   parman prio instance to add the item to
0343  * @item:   parman item instance
0344  *
0345  * Note: all locking must be provided by the caller.
0346  *
0347  * Adds item to a array managed by parman instance under the specified priority.
0348  *
0349  * Returns 0 in case of success, negative number to indicate an error.
0350  */
0351 int parman_item_add(struct parman *parman, struct parman_prio *prio,
0352             struct parman_item *item)
0353 {
0354     return parman->algo->item_add(parman, prio, item);
0355 }
0356 EXPORT_SYMBOL(parman_item_add);
0357
0358 /**
0359  * parman_item_remove - deletes parman item
0360  * @parman: parman instance
0361  * @prio:   parman prio instance to delete the item from
0362  * @item:   parman item instance
0363  *
0364  * Note: all locking must be provided by the caller.
0365  */
0366 void parman_item_remove(struct parman *parman, struct parman_prio *prio,
0367             struct parman_item *item)
0368 {
0369     parman->algo->item_remove(parman, prio, item);
0370 }
0371 EXPORT_SYMBOL(parman_item_remove);
0372
0373 MODULE_LICENSE("Dual BSD/GPL");
0374 MODULE_AUTHOR("Jiri Pirko <jiri@mellanox.com>");
0375 MODULE_DESCRIPTION("Priority-based array manager");