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