44091d29f2075 (Jiri Pirko 2017-02-03 10:29:06 +0100 1) /*
44091d29f2075 (Jiri Pirko 2017-02-03 10:29:06 +0100 2) * lib/parman.c - Manager for linear priority array areas
44091d29f2075 (Jiri Pirko 2017-02-03 10:29:06 +0100 3) * Copyright (c) 2017 Mellanox Technologies. All rights reserved.
44091d29f2075 (Jiri Pirko 2017-02-03 10:29:06 +0100 4) * Copyright (c) 2017 Jiri Pirko <jiri@mellanox.com>
44091d29f2075 (Jiri Pirko 2017-02-03 10:29:06 +0100 5) *
44091d29f2075 (Jiri Pirko 2017-02-03 10:29:06 +0100 6) * Redistribution and use in source and binary forms, with or without
44091d29f2075 (Jiri Pirko 2017-02-03 10:29:06 +0100 7) * modification, are permitted provided that the following conditions are met:
44091d29f2075 (Jiri Pirko 2017-02-03 10:29:06 +0100 8) *
44091d29f2075 (Jiri Pirko 2017-02-03 10:29:06 +0100 9) * 1. Redistributions of source code must retain the above copyright
44091d29f2075 (Jiri Pirko 2017-02-03 10:29:06 +0100 10) * notice, this list of conditions and the following disclaimer.
44091d29f2075 (Jiri Pirko 2017-02-03 10:29:06 +0100 11) * 2. Redistributions in binary form must reproduce the above copyright
44091d29f2075 (Jiri Pirko 2017-02-03 10:29:06 +0100 12) * notice, this list of conditions and the following disclaimer in the
44091d29f2075 (Jiri Pirko 2017-02-03 10:29:06 +0100 13) * documentation and/or other materials provided with the distribution.
44091d29f2075 (Jiri Pirko 2017-02-03 10:29:06 +0100 14) * 3. Neither the names of the copyright holders nor the names of its
44091d29f2075 (Jiri Pirko 2017-02-03 10:29:06 +0100 15) * contributors may be used to endorse or promote products derived from
44091d29f2075 (Jiri Pirko 2017-02-03 10:29:06 +0100 16) * this software without specific prior written permission.
44091d29f2075 (Jiri Pirko 2017-02-03 10:29:06 +0100 17) *
44091d29f2075 (Jiri Pirko 2017-02-03 10:29:06 +0100 18) * Alternatively, this software may be distributed under the terms of the
44091d29f2075 (Jiri Pirko 2017-02-03 10:29:06 +0100 19) * GNU General Public License ("GPL") version 2 as published by the Free
44091d29f2075 (Jiri Pirko 2017-02-03 10:29:06 +0100 20) * Software Foundation.
44091d29f2075 (Jiri Pirko 2017-02-03 10:29:06 +0100 21) *
44091d29f2075 (Jiri Pirko 2017-02-03 10:29:06 +0100 22) * THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS "AS IS"
44091d29f2075 (Jiri Pirko 2017-02-03 10:29:06 +0100 23) * AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE
44091d29f2075 (Jiri Pirko 2017-02-03 10:29:06 +0100 24) * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE
44091d29f2075 (Jiri Pirko 2017-02-03 10:29:06 +0100 25) * ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT OWNER OR CONTRIBUTORS BE
44091d29f2075 (Jiri Pirko 2017-02-03 10:29:06 +0100 26) * LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR
44091d29f2075 (Jiri Pirko 2017-02-03 10:29:06 +0100 27) * CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF
44091d29f2075 (Jiri Pirko 2017-02-03 10:29:06 +0100 28) * SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS
44091d29f2075 (Jiri Pirko 2017-02-03 10:29:06 +0100 29) * INTERRUPTION) HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN
44091d29f2075 (Jiri Pirko 2017-02-03 10:29:06 +0100 30) * CONTRACT, STRICT LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE)
44091d29f2075 (Jiri Pirko 2017-02-03 10:29:06 +0100 31) * ARISING IN ANY WAY OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE
44091d29f2075 (Jiri Pirko 2017-02-03 10:29:06 +0100 32) * POSSIBILITY OF SUCH DAMAGE.
44091d29f2075 (Jiri Pirko 2017-02-03 10:29:06 +0100 33) */
44091d29f2075 (Jiri Pirko 2017-02-03 10:29:06 +0100 34)
44091d29f2075 (Jiri Pirko 2017-02-03 10:29:06 +0100 35) #include <linux/kernel.h>
44091d29f2075 (Jiri Pirko 2017-02-03 10:29:06 +0100 36) #include <linux/module.h>
44091d29f2075 (Jiri Pirko 2017-02-03 10:29:06 +0100 37) #include <linux/slab.h>
44091d29f2075 (Jiri Pirko 2017-02-03 10:29:06 +0100 38) #include <linux/export.h>
44091d29f2075 (Jiri Pirko 2017-02-03 10:29:06 +0100 39) #include <linux/list.h>
44091d29f2075 (Jiri Pirko 2017-02-03 10:29:06 +0100 40) #include <linux/err.h>
44091d29f2075 (Jiri Pirko 2017-02-03 10:29:06 +0100 41) #include <linux/parman.h>
44091d29f2075 (Jiri Pirko 2017-02-03 10:29:06 +0100 42)
44091d29f2075 (Jiri Pirko 2017-02-03 10:29:06 +0100 43) struct parman_algo {
44091d29f2075 (Jiri Pirko 2017-02-03 10:29:06 +0100 44) int (*item_add)(struct parman *parman, struct parman_prio *prio,
44091d29f2075 (Jiri Pirko 2017-02-03 10:29:06 +0100 45) struct parman_item *item);
44091d29f2075 (Jiri Pirko 2017-02-03 10:29:06 +0100 46) void (*item_remove)(struct parman *parman, struct parman_prio *prio,
44091d29f2075 (Jiri Pirko 2017-02-03 10:29:06 +0100 47) struct parman_item *item);
44091d29f2075 (Jiri Pirko 2017-02-03 10:29:06 +0100 48) };
44091d29f2075 (Jiri Pirko 2017-02-03 10:29:06 +0100 49)
44091d29f2075 (Jiri Pirko 2017-02-03 10:29:06 +0100 50) struct parman {
44091d29f2075 (Jiri Pirko 2017-02-03 10:29:06 +0100 51) const struct parman_ops *ops;
44091d29f2075 (Jiri Pirko 2017-02-03 10:29:06 +0100 52) void *priv;
44091d29f2075 (Jiri Pirko 2017-02-03 10:29:06 +0100 53) const struct parman_algo *algo;
44091d29f2075 (Jiri Pirko 2017-02-03 10:29:06 +0100 54) unsigned long count;
44091d29f2075 (Jiri Pirko 2017-02-03 10:29:06 +0100 55) unsigned long limit_count;
44091d29f2075 (Jiri Pirko 2017-02-03 10:29:06 +0100 56) struct list_head prio_list;
44091d29f2075 (Jiri Pirko 2017-02-03 10:29:06 +0100 57) };
44091d29f2075 (Jiri Pirko 2017-02-03 10:29:06 +0100 58)
44091d29f2075 (Jiri Pirko 2017-02-03 10:29:06 +0100 59) static int parman_enlarge(struct parman *parman)
44091d29f2075 (Jiri Pirko 2017-02-03 10:29:06 +0100 60) {
44091d29f2075 (Jiri Pirko 2017-02-03 10:29:06 +0100 61) unsigned long new_count = parman->limit_count +
44091d29f2075 (Jiri Pirko 2017-02-03 10:29:06 +0100 62) parman->ops->resize_step;
44091d29f2075 (Jiri Pirko 2017-02-03 10:29:06 +0100 63) int err;
44091d29f2075 (Jiri Pirko 2017-02-03 10:29:06 +0100 64)
44091d29f2075 (Jiri Pirko 2017-02-03 10:29:06 +0100 65) err = parman->ops->resize(parman->priv, new_count);
44091d29f2075 (Jiri Pirko 2017-02-03 10:29:06 +0100 66) if (err)
44091d29f2075 (Jiri Pirko 2017-02-03 10:29:06 +0100 67) return err;
44091d29f2075 (Jiri Pirko 2017-02-03 10:29:06 +0100 68) parman->limit_count = new_count;
44091d29f2075 (Jiri Pirko 2017-02-03 10:29:06 +0100 69) return 0;
44091d29f2075 (Jiri Pirko 2017-02-03 10:29:06 +0100 70) }
44091d29f2075 (Jiri Pirko 2017-02-03 10:29:06 +0100 71)
44091d29f2075 (Jiri Pirko 2017-02-03 10:29:06 +0100 72) static int parman_shrink(struct parman *parman)
44091d29f2075 (Jiri Pirko 2017-02-03 10:29:06 +0100 73) {
44091d29f2075 (Jiri Pirko 2017-02-03 10:29:06 +0100 74) unsigned long new_count = parman->limit_count -
44091d29f2075 (Jiri Pirko 2017-02-03 10:29:06 +0100 75) parman->ops->resize_step;
44091d29f2075 (Jiri Pirko 2017-02-03 10:29:06 +0100 76) int err;
44091d29f2075 (Jiri Pirko 2017-02-03 10:29:06 +0100 77)
44091d29f2075 (Jiri Pirko 2017-02-03 10:29:06 +0100 78) if (new_count < parman->ops->base_count)
44091d29f2075 (Jiri Pirko 2017-02-03 10:29:06 +0100 79) return 0;
44091d29f2075 (Jiri Pirko 2017-02-03 10:29:06 +0100 80) err = parman->ops->resize(parman->priv, new_count);
44091d29f2075 (Jiri Pirko 2017-02-03 10:29:06 +0100 81) if (err)
44091d29f2075 (Jiri Pirko 2017-02-03 10:29:06 +0100 82) return err;
44091d29f2075 (Jiri Pirko 2017-02-03 10:29:06 +0100 83) parman->limit_count = new_count;
44091d29f2075 (Jiri Pirko 2017-02-03 10:29:06 +0100 84) return 0;
44091d29f2075 (Jiri Pirko 2017-02-03 10:29:06 +0100 85) }
44091d29f2075 (Jiri Pirko 2017-02-03 10:29:06 +0100 86)
44091d29f2075 (Jiri Pirko 2017-02-03 10:29:06 +0100 87) static bool parman_prio_used(struct parman_prio *prio)
44091d29f2075 (Jiri Pirko 2017-02-03 10:29:06 +0100 88) {
44091d29f2075 (Jiri Pirko 2017-02-03 10:29:06 +0100 89) return !list_empty(&prio->item_list);
44091d29f2075 (Jiri Pirko 2017-02-03 10:29:06 +0100 90) }
44091d29f2075 (Jiri Pirko 2017-02-03 10:29:06 +0100 91)
44091d29f2075 (Jiri Pirko 2017-02-03 10:29:06 +0100 92) static struct parman_item *parman_prio_first_item(struct parman_prio *prio)
44091d29f2075 (Jiri Pirko 2017-02-03 10:29:06 +0100 93) {
44091d29f2075 (Jiri Pirko 2017-02-03 10:29:06 +0100 94) return list_first_entry(&prio->item_list,
44091d29f2075 (Jiri Pirko 2017-02-03 10:29:06 +0100 95) typeof(struct parman_item), list);
44091d29f2075 (Jiri Pirko 2017-02-03 10:29:06 +0100 96) }
44091d29f2075 (Jiri Pirko 2017-02-03 10:29:06 +0100 97)
44091d29f2075 (Jiri Pirko 2017-02-03 10:29:06 +0100 98) static unsigned long parman_prio_first_index(struct parman_prio *prio)
44091d29f2075 (Jiri Pirko 2017-02-03 10:29:06 +0100 99) {
44091d29f2075 (Jiri Pirko 2017-02-03 10:29:06 +0100 100) return parman_prio_first_item(prio)->index;
44091d29f2075 (Jiri Pirko 2017-02-03 10:29:06 +0100 101) }
44091d29f2075 (Jiri Pirko 2017-02-03 10:29:06 +0100 102)
44091d29f2075 (Jiri Pirko 2017-02-03 10:29:06 +0100 103) static struct parman_item *parman_prio_last_item(struct parman_prio *prio)
44091d29f2075 (Jiri Pirko 2017-02-03 10:29:06 +0100 104) {
44091d29f2075 (Jiri Pirko 2017-02-03 10:29:06 +0100 105) return list_last_entry(&prio->item_list,
44091d29f2075 (Jiri Pirko 2017-02-03 10:29:06 +0100 106) typeof(struct parman_item), list);
44091d29f2075 (Jiri Pirko 2017-02-03 10:29:06 +0100 107) }
44091d29f2075 (Jiri Pirko 2017-02-03 10:29:06 +0100 108)
44091d29f2075 (Jiri Pirko 2017-02-03 10:29:06 +0100 109) static unsigned long parman_prio_last_index(struct parman_prio *prio)
44091d29f2075 (Jiri Pirko 2017-02-03 10:29:06 +0100 110) {
44091d29f2075 (Jiri Pirko 2017-02-03 10:29:06 +0100 111) return parman_prio_last_item(prio)->index;
44091d29f2075 (Jiri Pirko 2017-02-03 10:29:06 +0100 112) }
44091d29f2075 (Jiri Pirko 2017-02-03 10:29:06 +0100 113)
44091d29f2075 (Jiri Pirko 2017-02-03 10:29:06 +0100 114) static unsigned long parman_lsort_new_index_find(struct parman *parman,
44091d29f2075 (Jiri Pirko 2017-02-03 10:29:06 +0100 115) struct parman_prio *prio)
44091d29f2075 (Jiri Pirko 2017-02-03 10:29:06 +0100 116) {
44091d29f2075 (Jiri Pirko 2017-02-03 10:29:06 +0100 117) list_for_each_entry_from_reverse(prio, &parman->prio_list, list) {
44091d29f2075 (Jiri Pirko 2017-02-03 10:29:06 +0100 118) if (!parman_prio_used(prio))
44091d29f2075 (Jiri Pirko 2017-02-03 10:29:06 +0100 119) continue;
44091d29f2075 (Jiri Pirko 2017-02-03 10:29:06 +0100 120) return parman_prio_last_index(prio) + 1;
44091d29f2075 (Jiri Pirko 2017-02-03 10:29:06 +0100 121) }
44091d29f2075 (Jiri Pirko 2017-02-03 10:29:06 +0100 122) return 0;
44091d29f2075 (Jiri Pirko 2017-02-03 10:29:06 +0100 123) }
44091d29f2075 (Jiri Pirko 2017-02-03 10:29:06 +0100 124)
44091d29f2075 (Jiri Pirko 2017-02-03 10:29:06 +0100 125) static void __parman_prio_move(struct parman *parman, struct parman_prio *prio,
44091d29f2075 (Jiri Pirko 2017-02-03 10:29:06 +0100 126) struct parman_item *item, unsigned long to_index,
44091d29f2075 (Jiri Pirko 2017-02-03 10:29:06 +0100 127) unsigned long count)
44091d29f2075 (Jiri Pirko 2017-02-03 10:29:06 +0100 128) {
44091d29f2075 (Jiri Pirko 2017-02-03 10:29:06 +0100 129) parman->ops->move(parman->priv, item->index, to_index, count);
44091d29f2075 (Jiri Pirko 2017-02-03 10:29:06 +0100 130) }
44091d29f2075 (Jiri Pirko 2017-02-03 10:29:06 +0100 131)
44091d29f2075 (Jiri Pirko 2017-02-03 10:29:06 +0100 132) static void parman_prio_shift_down(struct parman *parman,
44091d29f2075 (Jiri Pirko 2017-02-03 10:29:06 +0100 133) struct parman_prio *prio)
44091d29f2075 (Jiri Pirko 2017-02-03 10:29:06 +0100 134) {
44091d29f2075 (Jiri Pirko 2017-02-03 10:29:06 +0100 135) struct parman_item *item;
44091d29f2075 (Jiri Pirko 2017-02-03 10:29:06 +0100 136) unsigned long to_index;
44091d29f2075 (Jiri Pirko 2017-02-03 10:29:06 +0100 137)
44091d29f2075 (Jiri Pirko 2017-02-03 10:29:06 +0100 138) if (!parman_prio_used(prio))
44091d29f2075 (Jiri Pirko 2017-02-03 10:29:06 +0100 139) return;
44091d29f2075 (Jiri Pirko 2017-02-03 10:29:06 +0100 140) item = parman_prio_first_item(prio);
44091d29f2075 (Jiri Pirko 2017-02-03 10:29:06 +0100 141) to_index = parman_prio_last_index(prio) + 1;
44091d29f2075 (Jiri Pirko 2017-02-03 10:29:06 +0100 142) __parman_prio_move(parman, prio, item, to_index, 1);
44091d29f2075 (Jiri Pirko 2017-02-03 10:29:06 +0100 143) list_move_tail(&item->list, &prio->item_list);
44091d29f2075 (Jiri Pirko 2017-02-03 10:29:06 +0100 144) item->index = to_index;
44091d29f2075 (Jiri Pirko 2017-02-03 10:29:06 +0100 145) }
44091d29f2075 (Jiri Pirko 2017-02-03 10:29:06 +0100 146)
44091d29f2075 (Jiri Pirko 2017-02-03 10:29:06 +0100 147) static void parman_prio_shift_up(struct parman *parman,
44091d29f2075 (Jiri Pirko 2017-02-03 10:29:06 +0100 148) struct parman_prio *prio)
44091d29f2075 (Jiri Pirko 2017-02-03 10:29:06 +0100 149) {
44091d29f2075 (Jiri Pirko 2017-02-03 10:29:06 +0100 150) struct parman_item *item;
44091d29f2075 (Jiri Pirko 2017-02-03 10:29:06 +0100 151) unsigned long to_index;
44091d29f2075 (Jiri Pirko 2017-02-03 10:29:06 +0100 152)
44091d29f2075 (Jiri Pirko 2017-02-03 10:29:06 +0100 153) if (!parman_prio_used(prio))
44091d29f2075 (Jiri Pirko 2017-02-03 10:29:06 +0100 154) return;
44091d29f2075 (Jiri Pirko 2017-02-03 10:29:06 +0100 155) item = parman_prio_last_item(prio);
44091d29f2075 (Jiri Pirko 2017-02-03 10:29:06 +0100 156) to_index = parman_prio_first_index(prio) - 1;
44091d29f2075 (Jiri Pirko 2017-02-03 10:29:06 +0100 157) __parman_prio_move(parman, prio, item, to_index, 1);
44091d29f2075 (Jiri Pirko 2017-02-03 10:29:06 +0100 158) list_move(&item->list, &prio->item_list);
44091d29f2075 (Jiri Pirko 2017-02-03 10:29:06 +0100 159) item->index = to_index;
44091d29f2075 (Jiri Pirko 2017-02-03 10:29:06 +0100 160) }
44091d29f2075 (Jiri Pirko 2017-02-03 10:29:06 +0100 161)
44091d29f2075 (Jiri Pirko 2017-02-03 10:29:06 +0100 162) static void parman_prio_item_remove(struct parman *parman,
44091d29f2075 (Jiri Pirko 2017-02-03 10:29:06 +0100 163) struct parman_prio *prio,
44091d29f2075 (Jiri Pirko 2017-02-03 10:29:06 +0100 164) struct parman_item *item)
44091d29f2075 (Jiri Pirko 2017-02-03 10:29:06 +0100 165) {
44091d29f2075 (Jiri Pirko 2017-02-03 10:29:06 +0100 166) struct parman_item *last_item;
44091d29f2075 (Jiri Pirko 2017-02-03 10:29:06 +0100 167) unsigned long to_index;
44091d29f2075 (Jiri Pirko 2017-02-03 10:29:06 +0100 168)
44091d29f2075 (Jiri Pirko 2017-02-03 10:29:06 +0100 169) last_item = parman_prio_last_item(prio);
44091d29f2075 (Jiri Pirko 2017-02-03 10:29:06 +0100 170) if (last_item == item) {
44091d29f2075 (Jiri Pirko 2017-02-03 10:29:06 +0100 171) list_del(&item->list);
44091d29f2075 (Jiri Pirko 2017-02-03 10:29:06 +0100 172) return;
44091d29f2075 (Jiri Pirko 2017-02-03 10:29:06 +0100 173) }
44091d29f2075 (Jiri Pirko 2017-02-03 10:29:06 +0100 174) to_index = item->index;
44091d29f2075 (Jiri Pirko 2017-02-03 10:29:06 +0100 175) __parman_prio_move(parman, prio, last_item, to_index, 1);
44091d29f2075 (Jiri Pirko 2017-02-03 10:29:06 +0100 176) list_del(&last_item->list);
44091d29f2075 (Jiri Pirko 2017-02-03 10:29:06 +0100 177) list_replace(&item->list, &last_item->list);
44091d29f2075 (Jiri Pirko 2017-02-03 10:29:06 +0100 178) last_item->index = to_index;
44091d29f2075 (Jiri Pirko 2017-02-03 10:29:06 +0100 179) }
44091d29f2075 (Jiri Pirko 2017-02-03 10:29:06 +0100 180)
44091d29f2075 (Jiri Pirko 2017-02-03 10:29:06 +0100 181) static int parman_lsort_item_add(struct parman *parman,
44091d29f2075 (Jiri Pirko 2017-02-03 10:29:06 +0100 182) struct parman_prio *prio,
44091d29f2075 (Jiri Pirko 2017-02-03 10:29:06 +0100 183) struct parman_item *item)
44091d29f2075 (Jiri Pirko 2017-02-03 10:29:06 +0100 184) {
44091d29f2075 (Jiri Pirko 2017-02-03 10:29:06 +0100 185) struct parman_prio *prio2;
44091d29f2075 (Jiri Pirko 2017-02-03 10:29:06 +0100 186) unsigned long new_index;
44091d29f2075 (Jiri Pirko 2017-02-03 10:29:06 +0100 187) int err;
44091d29f2075 (Jiri Pirko 2017-02-03 10:29:06 +0100 188)
44091d29f2075 (Jiri Pirko 2017-02-03 10:29:06 +0100 189) if (parman->count + 1 > parman->limit_count) {
44091d29f2075 (Jiri Pirko 2017-02-03 10:29:06 +0100 190) err = parman_enlarge(parman);
44091d29f2075 (Jiri Pirko 2017-02-03 10:29:06 +0100 191) if (err)
44091d29f2075 (Jiri Pirko 2017-02-03 10:29:06 +0100 192) return err;
44091d29f2075 (Jiri Pirko 2017-02-03 10:29:06 +0100 193) }
44091d29f2075 (Jiri Pirko 2017-02-03 10:29:06 +0100 194)
44091d29f2075 (Jiri Pirko 2017-02-03 10:29:06 +0100 195) new_index = parman_lsort_new_index_find(parman, prio);
44091d29f2075 (Jiri Pirko 2017-02-03 10:29:06 +0100 196) list_for_each_entry_reverse(prio2, &parman->prio_list, list) {
44091d29f2075 (Jiri Pirko 2017-02-03 10:29:06 +0100 197) if (prio2 == prio)
44091d29f2075 (Jiri Pirko 2017-02-03 10:29:06 +0100 198) break;
44091d29f2075 (Jiri Pirko 2017-02-03 10:29:06 +0100 199) parman_prio_shift_down(parman, prio2);
44091d29f2075 (Jiri Pirko 2017-02-03 10:29:06 +0100 200) }
44091d29f2075 (Jiri Pirko 2017-02-03 10:29:06 +0100 201) item->index = new_index;
44091d29f2075 (Jiri Pirko 2017-02-03 10:29:06 +0100 202) list_add_tail(&item->list, &prio->item_list);
44091d29f2075 (Jiri Pirko 2017-02-03 10:29:06 +0100 203) parman->count++;
44091d29f2075 (Jiri Pirko 2017-02-03 10:29:06 +0100 204) return 0;
44091d29f2075 (Jiri Pirko 2017-02-03 10:29:06 +0100 205) }
44091d29f2075 (Jiri Pirko 2017-02-03 10:29:06 +0100 206)
44091d29f2075 (Jiri Pirko 2017-02-03 10:29:06 +0100 207) static void parman_lsort_item_remove(struct parman *parman,
44091d29f2075 (Jiri Pirko 2017-02-03 10:29:06 +0100 208) struct parman_prio *prio,
44091d29f2075 (Jiri Pirko 2017-02-03 10:29:06 +0100 209) struct parman_item *item)
44091d29f2075 (Jiri Pirko 2017-02-03 10:29:06 +0100 210) {
44091d29f2075 (Jiri Pirko 2017-02-03 10:29:06 +0100 211) parman_prio_item_remove(parman, prio, item);
44091d29f2075 (Jiri Pirko 2017-02-03 10:29:06 +0100 212) list_for_each_entry_continue(prio, &parman->prio_list, list)
44091d29f2075 (Jiri Pirko 2017-02-03 10:29:06 +0100 213) parman_prio_shift_up(parman, prio);
44091d29f2075 (Jiri Pirko 2017-02-03 10:29:06 +0100 214) parman->count--;
44091d29f2075 (Jiri Pirko 2017-02-03 10:29:06 +0100 215) if (parman->limit_count - parman->count >= parman->ops->resize_step)
44091d29f2075 (Jiri Pirko 2017-02-03 10:29:06 +0100 216) parman_shrink(parman);
44091d29f2075 (Jiri Pirko 2017-02-03 10:29:06 +0100 217) }
44091d29f2075 (Jiri Pirko 2017-02-03 10:29:06 +0100 218)
44091d29f2075 (Jiri Pirko 2017-02-03 10:29:06 +0100 219) static const struct parman_algo parman_lsort = {
44091d29f2075 (Jiri Pirko 2017-02-03 10:29:06 +0100 220) .item_add = parman_lsort_item_add,
44091d29f2075 (Jiri Pirko 2017-02-03 10:29:06 +0100 221) .item_remove = parman_lsort_item_remove,
44091d29f2075 (Jiri Pirko 2017-02-03 10:29:06 +0100 222) };
44091d29f2075 (Jiri Pirko 2017-02-03 10:29:06 +0100 223)
44091d29f2075 (Jiri Pirko 2017-02-03 10:29:06 +0100 224) static const struct parman_algo *parman_algos[] = {
44091d29f2075 (Jiri Pirko 2017-02-03 10:29:06 +0100 225) &parman_lsort,
44091d29f2075 (Jiri Pirko 2017-02-03 10:29:06 +0100 226) };
44091d29f2075 (Jiri Pirko 2017-02-03 10:29:06 +0100 227)
44091d29f2075 (Jiri Pirko 2017-02-03 10:29:06 +0100 228) /**
44091d29f2075 (Jiri Pirko 2017-02-03 10:29:06 +0100 229) * parman_create - creates a new parman instance
44091d29f2075 (Jiri Pirko 2017-02-03 10:29:06 +0100 230) * @ops: caller-specific callbacks
44091d29f2075 (Jiri Pirko 2017-02-03 10:29:06 +0100 231) * @priv: pointer to a private data passed to the ops
44091d29f2075 (Jiri Pirko 2017-02-03 10:29:06 +0100 232) *
44091d29f2075 (Jiri Pirko 2017-02-03 10:29:06 +0100 233) * Note: all locking must be provided by the caller.
44091d29f2075 (Jiri Pirko 2017-02-03 10:29:06 +0100 234) *
44091d29f2075 (Jiri Pirko 2017-02-03 10:29:06 +0100 235) * Each parman instance manages an array area with chunks of entries
44091d29f2075 (Jiri Pirko 2017-02-03 10:29:06 +0100 236) * with the same priority. Consider following example:
44091d29f2075 (Jiri Pirko 2017-02-03 10:29:06 +0100 237) *
44091d29f2075 (Jiri Pirko 2017-02-03 10:29:06 +0100 238) * item 1 with prio 10
44091d29f2075 (Jiri Pirko 2017-02-03 10:29:06 +0100 239) * item 2 with prio 10
44091d29f2075 (Jiri Pirko 2017-02-03 10:29:06 +0100 240) * item 3 with prio 10
44091d29f2075 (Jiri Pirko 2017-02-03 10:29:06 +0100 241) * item 4 with prio 20
44091d29f2075 (Jiri Pirko 2017-02-03 10:29:06 +0100 242) * item 5 with prio 20
44091d29f2075 (Jiri Pirko 2017-02-03 10:29:06 +0100 243) * item 6 with prio 30
44091d29f2075 (Jiri Pirko 2017-02-03 10:29:06 +0100 244) * item 7 with prio 30
44091d29f2075 (Jiri Pirko 2017-02-03 10:29:06 +0100 245) * item 8 with prio 30
44091d29f2075 (Jiri Pirko 2017-02-03 10:29:06 +0100 246) *
44091d29f2075 (Jiri Pirko 2017-02-03 10:29:06 +0100 247) * In this example, there are 3 priority chunks. The order of the priorities
44091d29f2075 (Jiri Pirko 2017-02-03 10:29:06 +0100 248) * matters, however the order of items within a single priority chunk does not
44091d29f2075 (Jiri Pirko 2017-02-03 10:29:06 +0100 249) * matter. So the same array could be ordered as follows:
44091d29f2075 (Jiri Pirko 2017-02-03 10:29:06 +0100 250) *
44091d29f2075 (Jiri Pirko 2017-02-03 10:29:06 +0100 251) * item 2 with prio 10
44091d29f2075 (Jiri Pirko 2017-02-03 10:29:06 +0100 252) * item 3 with prio 10
44091d29f2075 (Jiri Pirko 2017-02-03 10:29:06 +0100 253) * item 1 with prio 10
44091d29f2075 (Jiri Pirko 2017-02-03 10:29:06 +0100 254) * item 5 with prio 20
44091d29f2075 (Jiri Pirko 2017-02-03 10:29:06 +0100 255) * item 4 with prio 20
44091d29f2075 (Jiri Pirko 2017-02-03 10:29:06 +0100 256) * item 7 with prio 30
44091d29f2075 (Jiri Pirko 2017-02-03 10:29:06 +0100 257) * item 8 with prio 30
44091d29f2075 (Jiri Pirko 2017-02-03 10:29:06 +0100 258) * item 6 with prio 30
44091d29f2075 (Jiri Pirko 2017-02-03 10:29:06 +0100 259) *
44091d29f2075 (Jiri Pirko 2017-02-03 10:29:06 +0100 260) * The goal of parman is to maintain the priority ordering. The caller
44091d29f2075 (Jiri Pirko 2017-02-03 10:29:06 +0100 261) * provides @ops with callbacks parman uses to move the items
44091d29f2075 (Jiri Pirko 2017-02-03 10:29:06 +0100 262) * and resize the array area.
44091d29f2075 (Jiri Pirko 2017-02-03 10:29:06 +0100 263) *
44091d29f2075 (Jiri Pirko 2017-02-03 10:29:06 +0100 264) * Returns a pointer to newly created parman instance in case of success,
44091d29f2075 (Jiri Pirko 2017-02-03 10:29:06 +0100 265) * otherwise it returns NULL.
44091d29f2075 (Jiri Pirko 2017-02-03 10:29:06 +0100 266) */
44091d29f2075 (Jiri Pirko 2017-02-03 10:29:06 +0100 267) struct parman *parman_create(const struct parman_ops *ops, void *priv)
44091d29f2075 (Jiri Pirko 2017-02-03 10:29:06 +0100 268) {
44091d29f2075 (Jiri Pirko 2017-02-03 10:29:06 +0100 269) struct parman *parman;
44091d29f2075 (Jiri Pirko 2017-02-03 10:29:06 +0100 270)
44091d29f2075 (Jiri Pirko 2017-02-03 10:29:06 +0100 271) parman = kzalloc(sizeof(*parman), GFP_KERNEL);
44091d29f2075 (Jiri Pirko 2017-02-03 10:29:06 +0100 272) if (!parman)
44091d29f2075 (Jiri Pirko 2017-02-03 10:29:06 +0100 273) return NULL;
44091d29f2075 (Jiri Pirko 2017-02-03 10:29:06 +0100 274) INIT_LIST_HEAD(&parman->prio_list);
44091d29f2075 (Jiri Pirko 2017-02-03 10:29:06 +0100 275) parman->ops = ops;
44091d29f2075 (Jiri Pirko 2017-02-03 10:29:06 +0100 276) parman->priv = priv;
44091d29f2075 (Jiri Pirko 2017-02-03 10:29:06 +0100 277) parman->limit_count = ops->base_count;
44091d29f2075 (Jiri Pirko 2017-02-03 10:29:06 +0100 278) parman->algo = parman_algos[ops->algo];
44091d29f2075 (Jiri Pirko 2017-02-03 10:29:06 +0100 279) return parman;
44091d29f2075 (Jiri Pirko 2017-02-03 10:29:06 +0100 280) }
44091d29f2075 (Jiri Pirko 2017-02-03 10:29:06 +0100 281) EXPORT_SYMBOL(parman_create);
44091d29f2075 (Jiri Pirko 2017-02-03 10:29:06 +0100 282)
44091d29f2075 (Jiri Pirko 2017-02-03 10:29:06 +0100 283) /**
44091d29f2075 (Jiri Pirko 2017-02-03 10:29:06 +0100 284) * parman_destroy - destroys existing parman instance
44091d29f2075 (Jiri Pirko 2017-02-03 10:29:06 +0100 285) * @parman: parman instance
44091d29f2075 (Jiri Pirko 2017-02-03 10:29:06 +0100 286) *
44091d29f2075 (Jiri Pirko 2017-02-03 10:29:06 +0100 287) * Note: all locking must be provided by the caller.
44091d29f2075 (Jiri Pirko 2017-02-03 10:29:06 +0100 288) */
44091d29f2075 (Jiri Pirko 2017-02-03 10:29:06 +0100 289) void parman_destroy(struct parman *parman)
44091d29f2075 (Jiri Pirko 2017-02-03 10:29:06 +0100 290) {
44091d29f2075 (Jiri Pirko 2017-02-03 10:29:06 +0100 291) WARN_ON(!list_empty(&parman->prio_list));
44091d29f2075 (Jiri Pirko 2017-02-03 10:29:06 +0100 292) kfree(parman);
44091d29f2075 (Jiri Pirko 2017-02-03 10:29:06 +0100 293) }
44091d29f2075 (Jiri Pirko 2017-02-03 10:29:06 +0100 294) EXPORT_SYMBOL(parman_destroy);
44091d29f2075 (Jiri Pirko 2017-02-03 10:29:06 +0100 295)
44091d29f2075 (Jiri Pirko 2017-02-03 10:29:06 +0100 296) /**
44091d29f2075 (Jiri Pirko 2017-02-03 10:29:06 +0100 297) * parman_prio_init - initializes a parman priority chunk
44091d29f2075 (Jiri Pirko 2017-02-03 10:29:06 +0100 298) * @parman: parman instance
44091d29f2075 (Jiri Pirko 2017-02-03 10:29:06 +0100 299) * @prio: parman prio structure to be initialized
c95c2d328cd05 (Randy Dunlap 2021-04-16 15:46:26 -0700 300) * @priority: desired priority of the chunk
44091d29f2075 (Jiri Pirko 2017-02-03 10:29:06 +0100 301) *
44091d29f2075 (Jiri Pirko 2017-02-03 10:29:06 +0100 302) * Note: all locking must be provided by the caller.
44091d29f2075 (Jiri Pirko 2017-02-03 10:29:06 +0100 303) *
44091d29f2075 (Jiri Pirko 2017-02-03 10:29:06 +0100 304) * Before caller could add an item with certain priority, he has to
44091d29f2075 (Jiri Pirko 2017-02-03 10:29:06 +0100 305) * initialize a priority chunk for it using this function.
44091d29f2075 (Jiri Pirko 2017-02-03 10:29:06 +0100 306) */
44091d29f2075 (Jiri Pirko 2017-02-03 10:29:06 +0100 307) void parman_prio_init(struct parman *parman, struct parman_prio *prio,
44091d29f2075 (Jiri Pirko 2017-02-03 10:29:06 +0100 308) unsigned long priority)
44091d29f2075 (Jiri Pirko 2017-02-03 10:29:06 +0100 309) {
44091d29f2075 (Jiri Pirko 2017-02-03 10:29:06 +0100 310) struct parman_prio *prio2;
44091d29f2075 (Jiri Pirko 2017-02-03 10:29:06 +0100 311) struct list_head *pos;
44091d29f2075 (Jiri Pirko 2017-02-03 10:29:06 +0100 312)
44091d29f2075 (Jiri Pirko 2017-02-03 10:29:06 +0100 313) INIT_LIST_HEAD(&prio->item_list);
44091d29f2075 (Jiri Pirko 2017-02-03 10:29:06 +0100 314) prio->priority = priority;
44091d29f2075 (Jiri Pirko 2017-02-03 10:29:06 +0100 315)
44091d29f2075 (Jiri Pirko 2017-02-03 10:29:06 +0100 316) /* Position inside the list according to priority */
44091d29f2075 (Jiri Pirko 2017-02-03 10:29:06 +0100 317) list_for_each(pos, &parman->prio_list) {
44091d29f2075 (Jiri Pirko 2017-02-03 10:29:06 +0100 318) prio2 = list_entry(pos, typeof(*prio2), list);
44091d29f2075 (Jiri Pirko 2017-02-03 10:29:06 +0100 319) if (prio2->priority > prio->priority)
44091d29f2075 (Jiri Pirko 2017-02-03 10:29:06 +0100 320) break;
44091d29f2075 (Jiri Pirko 2017-02-03 10:29:06 +0100 321) }
44091d29f2075 (Jiri Pirko 2017-02-03 10:29:06 +0100 322) list_add_tail(&prio->list, pos);
44091d29f2075 (Jiri Pirko 2017-02-03 10:29:06 +0100 323) }
44091d29f2075 (Jiri Pirko 2017-02-03 10:29:06 +0100 324) EXPORT_SYMBOL(parman_prio_init);
44091d29f2075 (Jiri Pirko 2017-02-03 10:29:06 +0100 325)
44091d29f2075 (Jiri Pirko 2017-02-03 10:29:06 +0100 326) /**
44091d29f2075 (Jiri Pirko 2017-02-03 10:29:06 +0100 327) * parman_prio_fini - finalizes use of parman priority chunk
44091d29f2075 (Jiri Pirko 2017-02-03 10:29:06 +0100 328) * @prio: parman prio structure
44091d29f2075 (Jiri Pirko 2017-02-03 10:29:06 +0100 329) *
44091d29f2075 (Jiri Pirko 2017-02-03 10:29:06 +0100 330) * Note: all locking must be provided by the caller.
44091d29f2075 (Jiri Pirko 2017-02-03 10:29:06 +0100 331) */
44091d29f2075 (Jiri Pirko 2017-02-03 10:29:06 +0100 332) void parman_prio_fini(struct parman_prio *prio)
44091d29f2075 (Jiri Pirko 2017-02-03 10:29:06 +0100 333) {
44091d29f2075 (Jiri Pirko 2017-02-03 10:29:06 +0100 334) WARN_ON(parman_prio_used(prio));
44091d29f2075 (Jiri Pirko 2017-02-03 10:29:06 +0100 335) list_del(&prio->list);
44091d29f2075 (Jiri Pirko 2017-02-03 10:29:06 +0100 336) }
44091d29f2075 (Jiri Pirko 2017-02-03 10:29:06 +0100 337) EXPORT_SYMBOL(parman_prio_fini);
44091d29f2075 (Jiri Pirko 2017-02-03 10:29:06 +0100 338)
44091d29f2075 (Jiri Pirko 2017-02-03 10:29:06 +0100 339) /**
44091d29f2075 (Jiri Pirko 2017-02-03 10:29:06 +0100 340) * parman_item_add - adds a parman item under defined priority
44091d29f2075 (Jiri Pirko 2017-02-03 10:29:06 +0100 341) * @parman: parman instance
44091d29f2075 (Jiri Pirko 2017-02-03 10:29:06 +0100 342) * @prio: parman prio instance to add the item to
44091d29f2075 (Jiri Pirko 2017-02-03 10:29:06 +0100 343) * @item: parman item instance
44091d29f2075 (Jiri Pirko 2017-02-03 10:29:06 +0100 344) *
44091d29f2075 (Jiri Pirko 2017-02-03 10:29:06 +0100 345) * Note: all locking must be provided by the caller.
44091d29f2075 (Jiri Pirko 2017-02-03 10:29:06 +0100 346) *
44091d29f2075 (Jiri Pirko 2017-02-03 10:29:06 +0100 347) * Adds item to a array managed by parman instance under the specified priority.
44091d29f2075 (Jiri Pirko 2017-02-03 10:29:06 +0100 348) *
44091d29f2075 (Jiri Pirko 2017-02-03 10:29:06 +0100 349) * Returns 0 in case of success, negative number to indicate an error.
44091d29f2075 (Jiri Pirko 2017-02-03 10:29:06 +0100 350) */
44091d29f2075 (Jiri Pirko 2017-02-03 10:29:06 +0100 351) int parman_item_add(struct parman *parman, struct parman_prio *prio,
44091d29f2075 (Jiri Pirko 2017-02-03 10:29:06 +0100 352) struct parman_item *item)
44091d29f2075 (Jiri Pirko 2017-02-03 10:29:06 +0100 353) {
44091d29f2075 (Jiri Pirko 2017-02-03 10:29:06 +0100 354) return parman->algo->item_add(parman, prio, item);
44091d29f2075 (Jiri Pirko 2017-02-03 10:29:06 +0100 355) }
44091d29f2075 (Jiri Pirko 2017-02-03 10:29:06 +0100 356) EXPORT_SYMBOL(parman_item_add);
44091d29f2075 (Jiri Pirko 2017-02-03 10:29:06 +0100 357)
44091d29f2075 (Jiri Pirko 2017-02-03 10:29:06 +0100 358) /**
c95c2d328cd05 (Randy Dunlap 2021-04-16 15:46:26 -0700 359) * parman_item_remove - deletes parman item
44091d29f2075 (Jiri Pirko 2017-02-03 10:29:06 +0100 360) * @parman: parman instance
44091d29f2075 (Jiri Pirko 2017-02-03 10:29:06 +0100 361) * @prio: parman prio instance to delete the item from
44091d29f2075 (Jiri Pirko 2017-02-03 10:29:06 +0100 362) * @item: parman item instance
44091d29f2075 (Jiri Pirko 2017-02-03 10:29:06 +0100 363) *
44091d29f2075 (Jiri Pirko 2017-02-03 10:29:06 +0100 364) * Note: all locking must be provided by the caller.
44091d29f2075 (Jiri Pirko 2017-02-03 10:29:06 +0100 365) */
44091d29f2075 (Jiri Pirko 2017-02-03 10:29:06 +0100 366) void parman_item_remove(struct parman *parman, struct parman_prio *prio,
44091d29f2075 (Jiri Pirko 2017-02-03 10:29:06 +0100 367) struct parman_item *item)
44091d29f2075 (Jiri Pirko 2017-02-03 10:29:06 +0100 368) {
44091d29f2075 (Jiri Pirko 2017-02-03 10:29:06 +0100 369) parman->algo->item_remove(parman, prio, item);
44091d29f2075 (Jiri Pirko 2017-02-03 10:29:06 +0100 370) }
44091d29f2075 (Jiri Pirko 2017-02-03 10:29:06 +0100 371) EXPORT_SYMBOL(parman_item_remove);
44091d29f2075 (Jiri Pirko 2017-02-03 10:29:06 +0100 372)
44091d29f2075 (Jiri Pirko 2017-02-03 10:29:06 +0100 373) MODULE_LICENSE("Dual BSD/GPL");
44091d29f2075 (Jiri Pirko 2017-02-03 10:29:06 +0100 374) MODULE_AUTHOR("Jiri Pirko <jiri@mellanox.com>");
44091d29f2075 (Jiri Pirko 2017-02-03 10:29:06 +0100 375) MODULE_DESCRIPTION("Priority-based array manager");
VisionFive2 Linux kernel
StarFive Tech Linux Kernel for VisionFive (JH7110) boards (mirror)
More than 9999 Commits
32 Branches
54 Tags