/* * lib/parman.c - Manager for linear priority array areas * Copyright (c) 2017 Mellanox Technologies. All rights reserved. * Copyright (c) 2017 Jiri Pirko <jiri@mellanox.com> * * Redistribution and use in source and binary forms, with or without * modification, are permitted provided that the following conditions are met: * * 1. Redistributions of source code must retain the above copyright *    notice, this list of conditions and the following disclaimer. * 2. Redistributions in binary form must reproduce the above copyright *    notice, this list of conditions and the following disclaimer in the *    documentation and/or other materials provided with the distribution. * 3. Neither the names of the copyright holders nor the names of its *    contributors may be used to endorse or promote products derived from *    this software without specific prior written permission. * * Alternatively, this software may be distributed under the terms of the * GNU General Public License ("GPL") version 2 as published by the Free * Software Foundation. * * THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS "AS IS" * AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE * ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT OWNER OR CONTRIBUTORS BE * LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR * CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF * SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS * INTERRUPTION) HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN * CONTRACT, STRICT LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) * ARISING IN ANY WAY OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE * POSSIBILITY OF SUCH DAMAGE. */ #include <linux/kernel.h>#include <linux/module.h>#include <linux/slab.h>#include <linux/export.h>#include <linux/list.h>#include <linux/err.h>#include <linux/parman.h> struct parman_algo {	int (*item_add)(struct parman *parman, struct parman_prio *prio,			struct parman_item *item);	void (*item_remove)(struct parman *parman, struct parman_prio *prio,			    struct parman_item *item);}; struct parman {	const struct parman_ops *ops;	void *priv;	const struct parman_algo *algo;	unsigned long count;	unsigned long limit_count;	struct list_head prio_list;}; static int parman_enlarge(struct parman *parman){	unsigned long new_count = parman->limit_count +				  parman->ops->resize_step;	int err; 	err = parman->ops->resize(parman->priv, new_count);	if (err)		return err;	parman->limit_count = new_count;	return 0;} static int parman_shrink(struct parman *parman){	unsigned long new_count = parman->limit_count -				  parman->ops->resize_step;	int err; 	if (new_count < parman->ops->base_count)		return 0;	err = parman->ops->resize(parman->priv, new_count);	if (err)		return err;	parman->limit_count = new_count;	return 0;} static bool parman_prio_used(struct parman_prio *prio) {	return !list_empty(&prio->item_list);} static struct parman_item *parman_prio_first_item(struct parman_prio *prio){	return list_first_entry(&prio->item_list,				typeof(struct parman_item), list);} static unsigned long parman_prio_first_index(struct parman_prio *prio){	return parman_prio_first_item(prio)->index;} static struct parman_item *parman_prio_last_item(struct parman_prio *prio){	return list_last_entry(&prio->item_list,			       typeof(struct parman_item), list);} static unsigned long parman_prio_last_index(struct parman_prio *prio){	return parman_prio_last_item(prio)->index;} static unsigned long parman_lsort_new_index_find(struct parman *parman,						 struct parman_prio *prio){	list_for_each_entry_from_reverse(prio, &parman->prio_list, list) {		if (!parman_prio_used(prio))			continue;		return parman_prio_last_index(prio) + 1;	}	return 0;} static void __parman_prio_move(struct parman *parman, struct parman_prio *prio,			       struct parman_item *item, unsigned long to_index,			       unsigned long count){	parman->ops->move(parman->priv, item->index, to_index, count);} static void parman_prio_shift_down(struct parman *parman,				   struct parman_prio *prio){	struct parman_item *item;	unsigned long to_index; 	if (!parman_prio_used(prio))		return;	item = parman_prio_first_item(prio);	to_index = parman_prio_last_index(prio) + 1;	__parman_prio_move(parman, prio, item, to_index, 1);	list_move_tail(&item->list, &prio->item_list);	item->index = to_index;} static void parman_prio_shift_up(struct parman *parman,				 struct parman_prio *prio){	struct parman_item *item;	unsigned long to_index; 	if (!parman_prio_used(prio))		return;	item = parman_prio_last_item(prio);	to_index = parman_prio_first_index(prio) - 1;	__parman_prio_move(parman, prio, item, to_index, 1);	list_move(&item->list, &prio->item_list);	item->index = to_index;} static void parman_prio_item_remove(struct parman *parman,				    struct parman_prio *prio,				    struct parman_item *item){	struct parman_item *last_item;	unsigned long to_index; 	last_item = parman_prio_last_item(prio);	if (last_item == item) {		list_del(&item->list);		return;	}	to_index = item->index;	__parman_prio_move(parman, prio, last_item, to_index, 1);	list_del(&last_item->list);	list_replace(&item->list, &last_item->list);	last_item->index = to_index;} static int parman_lsort_item_add(struct parman *parman,				 struct parman_prio *prio,				 struct parman_item *item){	struct parman_prio *prio2;	unsigned long new_index;	int err; 	if (parman->count + 1 > parman->limit_count) {		err = parman_enlarge(parman);		if (err)			return err;	} 	new_index = parman_lsort_new_index_find(parman, prio);	list_for_each_entry_reverse(prio2, &parman->prio_list, list) {		if (prio2 == prio)			break;		parman_prio_shift_down(parman, prio2);	}	item->index = new_index;	list_add_tail(&item->list, &prio->item_list);	parman->count++;	return 0;} static void parman_lsort_item_remove(struct parman *parman,				     struct parman_prio *prio,				     struct parman_item *item){	parman_prio_item_remove(parman, prio, item);	list_for_each_entry_continue(prio, &parman->prio_list, list)		parman_prio_shift_up(parman, prio);	parman->count--;	if (parman->limit_count - parman->count >= parman->ops->resize_step)		parman_shrink(parman);} static const struct parman_algo parman_lsort = {	.item_add	= parman_lsort_item_add,	.item_remove	= parman_lsort_item_remove,}; static const struct parman_algo *parman_algos[] = {	&parman_lsort,}; /** * parman_create - creates a new parman instance * @ops:	caller-specific callbacks * @priv:	pointer to a private data passed to the ops * * Note: all locking must be provided by the caller. * * Each parman instance manages an array area with chunks of entries * with the same priority. Consider following example: * * item 1 with prio 10 * item 2 with prio 10 * item 3 with prio 10 * item 4 with prio 20 * item 5 with prio 20 * item 6 with prio 30 * item 7 with prio 30 * item 8 with prio 30 * * In this example, there are 3 priority chunks. The order of the priorities * matters, however the order of items within a single priority chunk does not * matter. So the same array could be ordered as follows: * * item 2 with prio 10 * item 3 with prio 10 * item 1 with prio 10 * item 5 with prio 20 * item 4 with prio 20 * item 7 with prio 30 * item 8 with prio 30 * item 6 with prio 30 * * The goal of parman is to maintain the priority ordering. The caller * provides @ops with callbacks parman uses to move the items * and resize the array area. * * Returns a pointer to newly created parman instance in case of success, * otherwise it returns NULL. */struct parman *parman_create(const struct parman_ops *ops, void *priv){	struct parman *parman; 	parman = kzalloc(sizeof(*parman), GFP_KERNEL);	if (!parman)		return NULL;	INIT_LIST_HEAD(&parman->prio_list);	parman->ops = ops;	parman->priv = priv;	parman->limit_count = ops->base_count;	parman->algo = parman_algos[ops->algo];	return parman;}EXPORT_SYMBOL(parman_create); /** * parman_destroy - destroys existing parman instance * @parman:	parman instance * * Note: all locking must be provided by the caller. */void parman_destroy(struct parman *parman){	WARN_ON(!list_empty(&parman->prio_list));	kfree(parman);}EXPORT_SYMBOL(parman_destroy); /** * parman_prio_init - initializes a parman priority chunk * @parman:	parman instance * @prio:	parman prio structure to be initialized * @prority:	desired priority of the chunk * * Note: all locking must be provided by the caller. * * Before caller could add an item with certain priority, he has to * initialize a priority chunk for it using this function. */void parman_prio_init(struct parman *parman, struct parman_prio *prio,		      unsigned long priority){	struct parman_prio *prio2;	struct list_head *pos; 	INIT_LIST_HEAD(&prio->item_list);	prio->priority = priority; 	/* Position inside the list according to priority */	list_for_each(pos, &parman->prio_list) {		prio2 = list_entry(pos, typeof(*prio2), list);		if (prio2->priority > prio->priority)			break;	}	list_add_tail(&prio->list, pos);}EXPORT_SYMBOL(parman_prio_init); /** * parman_prio_fini - finalizes use of parman priority chunk * @prio:	parman prio structure * * Note: all locking must be provided by the caller. */void parman_prio_fini(struct parman_prio *prio){	WARN_ON(parman_prio_used(prio));	list_del(&prio->list);}EXPORT_SYMBOL(parman_prio_fini); /** * parman_item_add - adds a parman item under defined priority * @parman:	parman instance * @prio:	parman prio instance to add the item to * @item:	parman item instance * * Note: all locking must be provided by the caller. * * Adds item to a array managed by parman instance under the specified priority. * * Returns 0 in case of success, negative number to indicate an error. */int parman_item_add(struct parman *parman, struct parman_prio *prio,		    struct parman_item *item){	return parman->algo->item_add(parman, prio, item);}EXPORT_SYMBOL(parman_item_add); /** * parman_item_del - deletes parman item * @parman:	parman instance * @prio:	parman prio instance to delete the item from * @item:	parman item instance * * Note: all locking must be provided by the caller. */void parman_item_remove(struct parman *parman, struct parman_prio *prio,			struct parman_item *item){	parman->algo->item_remove(parman, prio, item);}EXPORT_SYMBOL(parman_item_remove); MODULE_LICENSE("Dual BSD/GPL");MODULE_AUTHOR("Jiri Pirko <jiri@mellanox.com>");MODULE_DESCRIPTION("Priority-based array manager");