lib: Introduce priority array area manager

This introduces a infrastructure for management of linear priority
areas. Priority order in an array matters, however order of items inside
a priority group does not matter.

As an initial implementation, L-sort algorithm is used. It is quite
trivial. More advanced algorithm called P-sort will be introduced as a
follow-up. The infrastructure is prepared for other algos.

Alongside this, a testing module is introduced as well.

Signed-off-by: Jiri Pirko <jiri@mellanox.com>
Signed-off-by: David S. Miller <davem@davemloft.net>

1 files changed, 376 insertions, 0 deletions

diff --git a/lib/parman.c b/lib/parman.c
new file mode 100644
index 000000000000..c6e42a8db824
--- /dev/null
+++ b/lib/parman.c
@@ -0,0 +1,376 @@
+/*
+ * 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");