[RFC net-next mlxsw v5] lib: Introduce manager for priority base pruning lookups between tables
Jiri Pirko
jiri at mellanox.com
Wed Jun 6 00:40:09 AEST 2018
I went this throught quickly, I pointed out some obvious issues I can
spot. Please fix before I will review any further. I would appreciate
you do it in days. Every time you send a new version, my caches are
already flushed and I start from scratch :/
My head is spinning a little bit... This seems quite complex that makes
one wonder if the complexicity is really necessary.
Thu, May 31, 2018 at 04:35:13PM CEST, talb at mellanox.com wrote:
>The prune library aim: reduce number of lookups (by prune) between tables
>within same prune object. Pruning save time complexity by do lookups only
perhaps "by doing lookups"?
>on the relevant tables, this eliminates the need to search items in other
>tables based on item priority and mask.
>
>For further details please check: Documentation/prune.txt
>
>Alongside this, a testing module is introduced as well.
>
>Signed-off-by: Tal Bar <talb at mellanox.com>
>---
> Documentation/prune.txt | 79 +++
> MAINTAINERS | 8 +
> include/linux/prune.h | 79 +++
> lib/Kconfig | 6 +
> lib/Kconfig.debug | 10 +
> lib/Makefile | 3 +
> lib/prune.c | 1318 +++++++++++++++++++++++++++++++++++++++++++++++
> lib/test_prune.c | 917 +++++++++++++++++++++++++++++++++
> 8 files changed, 2420 insertions(+)
> create mode 100644 Documentation/prune.txt
> create mode 100644 include/linux/prune.h
> create mode 100644 lib/prune.c
> create mode 100644 lib/test_prune.c
>
>diff --git a/Documentation/prune.txt b/Documentation/prune.txt
>new file mode 100644
>index 0000000..fc88deb
>--- /dev/null
>+++ b/Documentation/prune.txt
>@@ -0,0 +1,79 @@
>+Prune
>+=====
>+
>+Prune is a library which solves how to select which table needs to be searched.
>+User can create tables with specific masks. The tables contains masked items
>+with priority. Since similar item can be inserted to different tables, there is
>+a need to prune between the tables.
>+Pruning saves time complexity so that there won't be any need to search in
>+other tables.
>+
>+Table of Contents
>+-----------------
>+
>+* Prune
>+* Requirements
>+* library interface
>+ - objects
>+ - APIs
>+* Database
>+* Synchronization & critical sections
>+* WQ & Timers
>+* Flows
>+ - A* --> A
>+ - A --> A*
Just remove the TOC. It is useless.
>+
>+Requirements
>+============
>+ * Each item has its own prune-vector.
>+ * Prune-vector can be effected by add/remove an item.
>+ * User has the ability to determine if items can be compared for pruning.
>+
>+library interface
>+=================
>+
>+objects:
>+--------
>+struct prune
so?
Interface is defined in header file. Just remove this section entirely.
>+
>+Database
>+========
>+Each prune object has a list of tables with mask.
>+Each table consist:
>+ * hash table for items
>+ * list of the corresponding intersection tables (with other tables)
>+Each intersection table consists of:
>+ * hash table for intersects items
>+ * each item contain two lists:
>+ 1. items of the table owner
>+ 2. items of other tables (neighbor) in the prune object.
>+
>+Synchronization & critical sections
>+===================================
>+library doesn't take responsibility on synchronization. it's the user
>+responsibility to synchronize.
>+
>+Some of the APIs might sleep, please check the API headers for more information.
No need. Remove this section. (I have a feeling that I already asked that)
>+
>+Flows
>+=====
>+Insert item 'R'
>+--------------
You are missing one "-"
>+ * A*->A: Insert an item 'R' to a table, calculate its own prune-vector.
>+ * A->A*: 'R' was inserted to a table, and we have to calculate the
I have no clue what "A" and "A*" is :O
>+ prune-vectors of other compatible items (in different tables).
>+
>+Remove item 'R'
>+--------------
You are missing one "-"
>+ * A->*A: 'R' was removed from a table, this might impact the prune-vectors of
>+ other compatible items (in different tables).
>+
>+Add table 'T'
>+-------------
>+ Table 'T' was added to the prune object, add a prune vector item to the
"was"? I'm lost..
>+ prune-vector of the all items in the prune object.
>+
>+Remove table
For the sake of consistency, "Remove table 'T'".
>+------------
>+ Table 'T' was removed from the prune object, remove a prune vector item from
>+ the prune-vector from all items in the prune object.
>diff --git a/MAINTAINERS b/MAINTAINERS
>index 4713860..9763378 100644
>--- a/MAINTAINERS
>+++ b/MAINTAINERS
>@@ -11204,6 +11204,14 @@ F: include/linux/sysctl.h
> F: kernel/sysctl.c
> F: tools/testing/selftests/sysctl/
>
>+PRUNE
>+M: Tal Bar <talb at mellanox.com>
>+L: netdev at vger.kernel.org
>+S: Supported
>+F: lib/prune.c
>+F: lib/test_prune.c
>+F: include/linux/prune.h
>+
> PS3 NETWORK SUPPORT
> M: Geoff Levand <geoff at infradead.org>
> L: netdev at vger.kernel.org
>diff --git a/include/linux/prune.h b/include/linux/prune.h
>new file mode 100644
>index 0000000..941b985
>--- /dev/null
>+++ b/include/linux/prune.h
>@@ -0,0 +1,79 @@
>+/*
>+ * include/linux/prune.h - Manager for priority base pruning lookups between
>+ * tables.
>+ * Copyright (c) 2018 Mellanox Technologies. All rights reserved.
>+ * Copyright (c) 2018 Tal Bar <talb at mellanox.com>
>+ *
>+ * SPDX-License-Identifier: (GPL-2.0 OR BSD-3)
This is not a way do do SPDX. Should be first line in the file, starting
with "//"
Also, please kill the bsd. Let's just do gpl2
>+ */
>+
>+#ifndef _PRUNE_H
>+#define _PRUNE_H
>+
>+struct prune_table;
>+struct prune;
>+
>+struct prune_item {
>+ unsigned long priority; /* Higher number means higher priority */
>+ unsigned long *mask;
>+ unsigned int mask_len; /* Number of bits */
>+ void *priv;
>+};
>+
>+struct prune_vector_item {
You don't use this outside prune.c. Please move it there.
>+ struct prune_table *table;
>+ bool is_prune; /* True if item should prune this table otherwise not */
Drop the "otherwise not".
Is "is_prune" really the right name? Looks like "should_prune" is more
accurate. If not, rather name it "is_pruned".
>+ struct list_head list;
>+ void *priv;
When I see list_head and void *priv as a part of exported header, I'm
starting to be really scarred...
>+};
>+
>+struct prune_item_notify {
>+ struct prune_item item;
>+ /* list of prune vector item */
>+ const struct list_head *table_prune_list;
>+};
>+
>+/**
>+ * This structure defines the management hooks for prune object.
>+ * The following hooks can be defined; unless noted otherwise, they are
>+ * optional and can be filled with a null pointer.
>+ *
>+ * prune_item_notify:
>+ * Called if there is a change in a the prune vector of an item or items,
>+ * the notification can be sent on one item or more.
>+ *
>+ * prune_mask_comparable:
>+ * Called when adding new items to a table.
>+ */
>+struct prune_ops {
>+ void (*prune_item_notify)(struct prune_table *table,
>+ struct prune_item_notify *item,
>+ unsigned int item_cnt);
item_cnt is set to 1 and never used. Why do you carry this? Please
remove.
>+ int (*prune_mask_comparable)(unsigned long *mask_a,
>+ unsigned long *mask_b,
>+ unsigned int len);
>+};
>+
>+struct prune_table_attr {
>+ unsigned long *mask;
>+ unsigned int mask_len; /* Number of bits */
>+ /* Used by the priv field in strcut prune_table */
>+ void *priv;
>+};
>+
>+struct prune *prune_init(unsigned int mask_len, const struct prune_ops *ops,
"_init()" should be used for initialization in case you already has the
object allocated (by "_alloc()" function). If you do 2 in 1, please use
"_create()" and "_destroy()".
>+ void *priv);
>+void prune_fini(struct prune *prune);
>+struct prune_table *prune_table_add(struct prune *prune,
>+ struct prune_table_attr *table_attr);
Again, since the table is allocated and initialized inside, do
"_create()" and "_destroy()".
>+int prune_table_remove(struct prune *prune, struct prune_table *table);
>+int prune_item_add(struct prune *prune, struct prune_table *table,
>+ struct prune_item *item);
Please always, if possible, avoid structs to be passed instead of simple
args. In this case, just get rid of struct prune_item and pass all what
you need as function args. You can then rename "struct prune_item_entry"
to "struct prune_item".
Also, I believe that you should rename this to "_create" and let the
function return "struct prune_item_entry/struct prune_item". Later on
the caller will use the returned pointer for destuction.
>+int prune_item_remove(struct prune *prune, struct prune_table *table,
>+ struct prune_item *item);
Should not return int. Just void. Please adjust the function and
whatever is it calling.
>+
>+static inline size_t prune_mask_size(unsigned int nbits)
>+{
>+ return BITS_TO_LONGS(nbits) * sizeof(unsigned long);
>+}
>+#endif
>diff --git a/lib/Kconfig b/lib/Kconfig
>index e960894..c9ed533 100644
>--- a/lib/Kconfig
>+++ b/lib/Kconfig
>@@ -583,6 +583,12 @@ config PARMAN
> config PRIME_NUMBERS
> tristate
>
>+config PRUNE
>+ tristate "prune"
>+ help
>+ This option enables the use of prune manager library for priority
>+ base pruning lookups between tables.
>+
> config STRING_SELFTEST
> tristate "Test string functions"
>
>diff --git a/lib/Kconfig.debug b/lib/Kconfig.debug
>index 64155e3..d1b0add 100644
>--- a/lib/Kconfig.debug
>+++ b/lib/Kconfig.debug
>@@ -1803,6 +1803,16 @@ config TEST_PARMAN
>
> If unsure, say N.
>
>+config TEST_PRUNE
>+ tristate "Perform selftest on pruning tables manager"
>+ default n
>+ depends on PRUNE
>+ help
>+ Enable this option to test pruning tables manager
>+ (or module load).
>+
>+ If unsure, say N.
>+
> config TEST_LKM
> tristate "Test module loading with 'hello world' module"
> default n
>diff --git a/lib/Makefile b/lib/Makefile
>index a90d4fc..e26e0c9 100644
>--- a/lib/Makefile
>+++ b/lib/Makefile
>@@ -66,6 +66,7 @@ obj-$(CONFIG_TEST_UUID) += test_uuid.o
> obj-$(CONFIG_TEST_PARMAN) += test_parman.o
> obj-$(CONFIG_TEST_KMOD) += test_kmod.o
> obj-$(CONFIG_TEST_DEBUG_VIRTUAL) += test_debug_virtual.o
>+obj-$(CONFIG_TEST_PRUNE) += test_prune.o
>
> ifeq ($(CONFIG_DEBUG_KOBJECT),y)
> CFLAGS_kobject.o += -DDEBUG
>@@ -252,6 +253,8 @@ obj-$(CONFIG_SBITMAP) += sbitmap.o
>
> obj-$(CONFIG_PARMAN) += parman.o
>
>+obj-$(CONFIG_PRUNE) += prune.o
>+
> # GCC library routines
> obj-$(CONFIG_GENERIC_ASHLDI3) += ashldi3.o
> obj-$(CONFIG_GENERIC_ASHRDI3) += ashrdi3.o
>diff --git a/lib/prune.c b/lib/prune.c
>new file mode 100644
>index 0000000..4314fca
>--- /dev/null
>+++ b/lib/prune.c
>@@ -0,0 +1,1318 @@
>+/*
>+ * lib/prune.c - Manager for priority base pruning lookups between tables.
>+ * Copyright (c) 2018 Mellanox Technologies. All rights reserved.
>+ * Copyright (c) 2018 Tal Bar <talb at mellanox.com>
>+ *
>+ * SPDX-License-Identifier: (GPL-2.0 OR BSD-3)
>+ */
>+
>+#include <linux/kernel.h>
>+#include <linux/module.h>
>+#include <linux/slab.h>
>+#include <linux/export.h>
>+#include <linux/list.h>
>+#include <linux/rhashtable.h>
>+#include <linux/prune.h>
>+#include <linux/jhash.h>
>+#include <linux/bitmap.h>
>+
>+struct prune_table_item_key {
>+ struct prune_item *item;
>+};
>+
>+struct prune_table_item_entry {
>+ struct rhash_head ht_node; /* Member of tablset HT */
>+ struct prune_table_item_key ht_key;
>+ /* List of struct prune_vector_item */
>+ struct list_head table_prune_vector;
>+};
>+
>+struct prune_neighbor_table_items {
>+ const struct prune_item *item;
>+ struct list_head list;
>+};
>+
>+struct prune_intersec_table_item {
>+ const struct prune_table_item_entry *entry;
>+ struct list_head list;
>+};
>+
>+struct prune_intersec_table_item_key {
>+ unsigned long *mask;
>+};
>+
>+struct prune_intersec_table_item_entry {
>+ struct rhash_head ht_node; /* Member of tablset HT */
>+ struct prune_intersec_table_item_key ht_key;
>+ unsigned int mask_len;
>+ struct list_head intersec_table_items;
>+ struct list_head neighbor_table_items; /* Can be enhanced to rbtree */
>+};
>+
>+struct prune_intersec_table {
>+ unsigned long *mask;
>+ struct rhashtable items_ht;
>+ struct prune_table *neigh_table;
>+ struct list_head list;
>+};
>+
>+struct prune_table {
>+ unsigned long *mask;
>+ struct rhashtable items_ht;
>+ struct rhashtable_iter iter;
>+ /* A list of table structs that contains intersection of the current
>+ * table with the other tables in the prune object.
>+ */
>+ struct list_head intersec_table_list;
>+ struct list_head list; /* Node of table_list in struct prune */
>+ const struct prune_ops *ops;
>+ void *priv;
>+};
>+
>+struct prune {
>+ const struct prune_ops *ops;
>+ unsigned int mask_len;
>+ struct list_head table_list; /* A list of struct prune_table */
>+ unsigned int table_cnt; /* Number of tables in the list */
>+ void *priv;
>+};
>+
>+static int prune_table_ht_cmp(struct rhashtable_compare_arg *arg,
>+ const void *obj);
>+static u32 prune_table_ht_hash(const void *data, u32 len, u32 seed);
>+static int prune_intersec_ht_cmp(struct rhashtable_compare_arg *arg,
>+ const void *obj);
>+static u32 prune_intersec_ht_hash(const void *data, u32 len, u32 seed);
Forward declarations are evil. Reshuffle your code to avoid them.
>+
>+static struct rhashtable_params tables_ht_params = {
>+ .key_offset = offsetof(struct prune_table_item_entry, ht_key),
>+ .head_offset = offsetof(struct prune_table_item_entry, ht_node),
>+ .obj_cmpfn = prune_table_ht_cmp,
>+ .hashfn = prune_table_ht_hash,
>+ .automatic_shrinking = true,
>+};
>+
>+static struct rhashtable_params intersec_tables_ht_params = {
>+ .key_offset = offsetof(struct prune_intersec_table_item_entry, ht_key),
>+ .head_offset = offsetof(struct prune_intersec_table_item_entry,
>+ ht_node),
>+ .obj_cmpfn = prune_intersec_ht_cmp,
>+ .hashfn = prune_intersec_ht_hash,
>+ .automatic_shrinking = true,
>+};
>+
>+static u32 prune_table_ht_hash(const void *data, u32 len, u32 seed)
>+{
>+ const struct prune_table_item_key *item_key = data;
>+ u32 jhash_len = prune_mask_size(len);
>+ unsigned int mask_hash, prio_hash;
>+ unsigned long long tmp;
>+
>+ mask_hash = jhash(item_key->item->mask, jhash_len, seed);
>+ prio_hash = jhash(&item_key->item->priority, sizeof(unsigned long),
>+ seed);
>+
>+ tmp = (unsigned long long)(mask_hash) << 32 | prio_hash;
>+ return jhash(&tmp, sizeof(unsigned long long), seed);
>+}
>+
>+static int prune_table_ht_cmp(struct rhashtable_compare_arg *arg,
>+ const void *obj)
>+{
>+ const struct prune_table_item_key *item_key = arg->key;
>+ const struct prune_table_item_entry *entry = obj;
>+ int bit_equal;
>+ bool prio_equal;
>+
>+ bit_equal = bitmap_equal(item_key->item->mask,
>+ entry->ht_key.item->mask,
>+ entry->ht_key.item->mask_len);
>+ prio_equal = entry->ht_key.item->priority == item_key->item->priority;
>+
>+ return !prio_equal && !bit_equal;
>+}
>+
>+static u32 prune_intersec_ht_hash(const void *data, u32 len, u32 seed)
>+{
>+ u32 jash_len = prune_mask_size(len);
>+ const struct prune_intersec_table_item_key * const ht_key = data;
>+
>+ return jhash(ht_key->mask, jash_len, seed);
>+}
>+
>+static int prune_intersec_ht_cmp(struct rhashtable_compare_arg *arg,
>+ const void *obj)
>+{
>+ const struct prune_intersec_table_item_entry *intersec_entry = obj;
>+ const struct prune_intersec_table_item_key *ht_key = arg->key;
>+
>+ return !(bitmap_equal(ht_key->mask, intersec_entry->ht_key.mask,
>+ intersec_entry->mask_len));
>+}
>+
>+static void prune_table_prune_list_fini(struct prune_table_item_entry *entry)
>+{
>+ struct prune_vector_item *vector_item;
>+ struct list_head *pos, *tmp;
>+
>+ list_for_each_safe(pos, tmp, &entry->table_prune_vector) {
>+ vector_item = list_entry(pos, typeof(*vector_item), list);
>+ list_del(&vector_item->list);
>+ kfree(vector_item);
>+ }
>+}
>+
>+static int prune_table_prune_list_init(struct prune *prune,
>+ struct prune_table_item_entry *entry)
>+{
>+ struct prune_vector_item *vector_item;
>+ struct prune_table *table;
>+
>+ INIT_LIST_HEAD(&entry->table_prune_vector);
>+
>+ list_for_each_entry(table, &prune->table_list, list) {
>+ vector_item = kzalloc(sizeof(*vector_item), GFP_KERNEL);
>+ if (!vector_item) {
>+ prune_table_prune_list_fini(entry);
>+ return -ENOMEM;
>+ }
>+ vector_item->is_prune = true;
>+ vector_item->priv = table->priv;
>+ vector_item->table = table;
>+ list_add_tail(&vector_item->list,
>+ &entry->table_prune_vector);
>+ }
>+ return 0;
>+}
>+
>+static struct prune_table_item_entry *
>+prune_item_entry_create(struct prune *prune,
>+ struct prune_item *item)
>+{
>+ struct prune_table_item_entry *entry;
>+ int err;
>+
>+ entry = kzalloc(sizeof(*entry), GFP_KERNEL);
>+ if (!entry)
>+ goto err_entry_alloc;
>+
>+ entry->ht_key.item = item;
>+
>+ err = prune_table_prune_list_init(prune, entry);
>+ if (err)
>+ goto err_list_init;
>+
>+ return entry;
>+
>+err_list_init:
>+ kfree(entry);
>+err_entry_alloc:
>+ return NULL;
>+}
>+
>+static void prune_entry_destroy(struct prune_table_item_entry *entry)
>+{
>+ prune_table_prune_list_fini(entry);
>+ kfree(entry);
>+}
>+
>+static bool prune_items_comparable(struct prune_table *table,
>+ unsigned long *mask_a, unsigned long *mask_b,
>+ unsigned int mask_len)
>+{
>+ if (table->ops->prune_mask_comparable)
>+ return table->ops->prune_mask_comparable(mask_a,
>+ mask_b,
>+ mask_len);
>+
>+ return true;
>+}
>+
>+static bool prune_item_update(const struct list_head *table_prune_list,
>+ struct prune_table *corresponding_table,
>+ bool is_prune)
>+{
>+ struct prune_vector_item *vector_item;
So "item" or "vector_item". Make up your mind. Consistency, consistency,
consistency!
>+
>+ list_for_each_entry(vector_item, table_prune_list, list) {
>+ /* Find the corresponding prune item and set it */
>+ if (vector_item->table == corresponding_table &&
>+ vector_item->is_prune != is_prune) {
>+ vector_item->is_prune = is_prune;
>+ return true;
>+ }
>+ }
>+ return false;
>+}
>+
>+static bool prune_vector_set(struct prune_table *table,
>+ struct prune_table *neigh_table,
>+ const struct prune_table_item_entry *entry,
>+ struct prune_neighbor_table_items *neigh_item,
>+ struct prune_intersec_table_item *intersec_item,
>+ bool neigh_items)
>+{
>+ const struct list_head *prune_list;
>+ unsigned long *mask;
>+ bool not_prune;
>+
>+ if (neigh_items)
>+ not_prune = neigh_item->item->priority
>+ > entry->ht_key.item->priority;
>+ else
>+ not_prune = intersec_item->entry->ht_key.item->priority
>+ < entry->ht_key.item->priority;
>+
>+ mask = neigh_items ? neigh_item->item->mask
>+ : intersec_item->entry->ht_key.item->mask;
My first choice would be to put ":" and "</>" at the end of previous
line.
>+ prune_list = neigh_items ? &entry->table_prune_vector
>+ : &intersec_item->entry->table_prune_vector;
>+ if (not_prune)
>+ if (prune_items_comparable(table, entry->ht_key.item->mask,
>+ mask, entry->ht_key.item->mask_len))
>+ return prune_item_update(prune_list, neigh_table,
>+ false);
>+
>+ return false;
>+}
>+
>+static void
>+prune_item_entry_to_item_notify(struct prune_item_notify *item_notify,
>+ struct prune_intersec_table_item *intersec_item)
>+{
>+ const struct prune_table_item_entry *entry = intersec_item->entry;
>+
>+ item_notify->item.priority = entry->ht_key.item->priority;
>+ item_notify->item.mask = entry->ht_key.item->mask;
>+ item_notify->item.mask_len = entry->ht_key.item->mask_len;
>+ item_notify->table_prune_list = &entry->table_prune_vector;
It is really weird to take an internal list and expose it outside like
this.
>+}
>+
>+static bool
>+prune_item_add_prune_vector_calc(struct prune_table *table,
"prune_item_add_prune_vector_calc"? What is that.
I think that I made myself clear that the function name should be
always: "prefix_object_action".
>+ struct prune_intersec_table *intersec_table,
>+ struct prune_intersec_table_item_key *ht_key,
>+ const struct prune_table_item_entry *entry,
>+ bool neigh)
>+{
>+ struct prune_neighbor_table_items *neigh_item;
>+ struct prune_intersec_table_item_entry *intersec_entry;
>+ struct prune_intersec_table_item *intersec_item;
>+ struct prune_item_notify item_notify;
>+ bool prune_vector_chng = false;
>+
>+ bitmap_clear(ht_key->mask, 0, entry->ht_key.item->mask_len);
>+ bitmap_and(ht_key->mask, entry->ht_key.item->mask, intersec_table->mask,
>+ entry->ht_key.item->mask_len);
>+
>+ intersec_entry = rhashtable_lookup_fast(&intersec_table->items_ht,
>+ ht_key,
>+ intersec_tables_ht_params);
>+
>+ /* If there is a match on this mask - need to iterate on
>+ * neighbor_table_items. In case there is a entry with higher
>+ * priority we should not prune the neighbor table.
>+ */
>+ if (!intersec_entry)
>+ return false;
>+
>+ if (neigh) {
>+ list_for_each_entry(neigh_item,
>+ &intersec_entry->neighbor_table_items,
>+ list) {
>+ prune_vector_chng |= prune_vector_set(table,
>+ intersec_table->neigh_table,
>+ entry,
>+ neigh_item,
>+ NULL,
>+ neigh);
>+ }
>+ } else {
>+ /* For my items need to update to prune vector
>+ * corresponding to the new item
>+ */
>+ list_for_each_entry(intersec_item,
>+ &intersec_entry->intersec_table_items,
>+ list) {
>+ if (prune_vector_set(table,
>+ intersec_table->neigh_table,
>+ entry,
>+ NULL,
>+ intersec_item,
>+ neigh)) {
>+ prune_item_entry_to_item_notify(&item_notify,
>+ intersec_item);
>+ table->ops->prune_item_notify(table,
>+ &item_notify,
>+ 1);
>+ /* TODO: need to enhance to one notification
>+ * and remove this code block
>+ */
>+ }
>+ }
>+ }
>+ return prune_vector_chng;
>+}
>+
>+static bool
>+prune_neigh_item_prio_higher(struct prune_table *table,
>+ const struct prune_item *neigh_item,
>+ const struct prune_table_item_entry *entry)
>+{
>+ if (prune_items_comparable(table, neigh_item->mask,
>+ entry->ht_key.item->mask,
>+ neigh_item->mask_len)) {
>+ if (neigh_item->priority > entry->ht_key.item->priority)
>+ return true;
>+ else
>+ return false;
>+ }
>+ return false;
>+}
>+
>+static bool prune_neighbor_list_item_higher_prio(struct prune_table *table,
>+ struct prune_intersec_table_item *intersec_item,
>+ struct prune_intersec_table_item_entry *intersec_entry)
>+{
>+ struct prune_neighbor_table_items *neigh_item;
>+
>+ list_for_each_entry(neigh_item, &intersec_entry->neighbor_table_items,
>+ list) {
>+ if (prune_neigh_item_prio_higher(table, neigh_item->item,
>+ intersec_item->entry))
>+ return true;
>+ }
>+ return false;
>+}
>+
>+static void prune_item_rem_prune_vector_calc(struct prune_table *table,
>+ struct prune_item *deleted_item,
>+ struct prune_intersec_table *intersec_table,
>+ struct prune_intersec_table_item_key *ht_key)
>+{
>+ struct prune_intersec_table_item_entry *intersec_entry;
>+ struct prune_intersec_table_item *intersec_item;
>+ struct prune_item_notify item_notify;
>+ const struct list_head *prune_list;
>+ bool to_prune, notify;
>+
>+ bitmap_clear(ht_key->mask, 0, deleted_item->mask_len);
>+ bitmap_and(ht_key->mask, deleted_item->mask, intersec_table->mask,
>+ deleted_item->mask_len);
>+
>+ intersec_entry = rhashtable_lookup_fast(&intersec_table->items_ht,
>+ ht_key,
>+ intersec_tables_ht_params);
>+ if (!intersec_entry)
>+ return;
>+
>+ /* Check if one of the items in the neighbor list have higher prio if so
>+ * don't prune
>+ */
>+ list_for_each_entry(intersec_item,
>+ &intersec_entry->intersec_table_items, list) {
>+ /* Check if there is an item in my neighbor list with higher
>+ * priority and it's allowed to compare between them if so -->
>+ * don't prune
>+ */
>+ to_prune = true;
>+
>+ notify = false;
>+ if (!prune_neighbor_list_item_higher_prio(table,
>+ intersec_item,
>+ intersec_entry)) {
>+ /* Update intersec_item prune vector for the
>+ * corresponding table
>+ */
>+ prune_list = &intersec_item->entry->table_prune_vector;
>+ notify = prune_item_update(prune_list, table, true);
>+ }
>+ if (notify) {
>+ prune_item_entry_to_item_notify(&item_notify,
>+ intersec_item);
>+ table->ops->prune_item_notify(table,
>+ &item_notify, 1);
>+ /* TODO: need to enhance to one notification
>+ * and remove this code block
>+ */
>+ }
>+ }
>+}
>+
>+static int prune_item_add_prune_vector_set(struct prune_table *table,
>+ struct prune_item *item,
>+ struct prune_table_item_entry *entry)
>+{
>+ struct prune_intersec_table *intersec_table;
>+ struct prune_intersec_table_item_key ht_key;
>+ struct prune_item_notify item_notify;
>+ bool notify = false;
>+ unsigned int nbits = entry->ht_key.item->mask_len;
>+
>+ ht_key.mask = kcalloc(1, prune_mask_size(nbits), GFP_ATOMIC);
>+ if (!ht_key.mask)
>+ return -ENOMEM;
>+
>+ list_for_each_entry(intersec_table, &table->intersec_table_list, list) {
>+ notify |= prune_item_add_prune_vector_calc(table,
>+ intersec_table,
>+ &ht_key, entry,
>+ true);
>+ }
>+ if (notify) { /* TODO: move this block to be return */
>+ item_notify.item = *item;
>+ item_notify.table_prune_list = &entry->table_prune_vector;
>+ table->ops->prune_item_notify(table, &item_notify, 1);
>+ }
>+ return 0;
>+}
>+
>+static void
>+prune_neigh_prune_vector_calc(struct prune_table *table,
>+ struct prune_table *curr_table,
>+ struct prune_item *item,
>+ struct prune_intersec_table_item_key *ht_key,
>+ const struct prune_table_item_entry *entry,
>+ bool add_item)
>+{
>+ struct prune_intersec_table *intersec_table;
>+
>+ /* Search the corresponding intersection table with
>+ * this table and update the prune vector of items in
>+ * the intersection table if there is no higher
>+ * priority items in their neighbor table.
>+ */
>+ list_for_each_entry(intersec_table, &curr_table->intersec_table_list,
>+ list) {
>+ if (intersec_table->neigh_table == table) {
>+ /* This is the corresponding table */
>+ if (add_item)
>+ prune_item_add_prune_vector_calc(table,
>+ intersec_table,
>+ ht_key,
>+ entry,
>+ false);
>+ else
>+ prune_item_rem_prune_vector_calc(table,
>+ item,
>+ intersec_table,
>+ ht_key);
>+ }
>+ }
>+}
>+
>+static int
>+prune_neigh_table_prune_vector_set(struct prune *prune,
>+ struct prune_table *table,
>+ struct prune_item *item,
>+ const struct prune_table_item_entry *entry,
>+ bool add_item)
>+{
>+ struct prune_intersec_table_item_key ht_key;
>+ struct prune_table *curr_table;
>+
>+ ht_key.mask = kcalloc(1, prune_mask_size(item->mask_len), GFP_ATOMIC);
>+ if (!ht_key.mask)
>+ return -ENOMEM;
>+
>+ list_for_each_entry(curr_table, &prune->table_list, list) {
>+ if (curr_table != table)
>+ prune_neigh_prune_vector_calc(table, curr_table, item,
>+ &ht_key, entry, add_item);
>+ }
>+ return 0;
>+}
>+
>+static struct prune_table_item_entry *
>+prune_table_entry_create(struct prune *prune,
>+ struct prune_table *table,
>+ struct prune_item *item)
>+{
>+ struct prune_table_item_entry *entry;
>+ int err;
>+
>+ if (bitmap_subset(item->mask, table->mask, item->mask_len) != 1)
>+ return ERR_PTR(-EPERM);
>+
>+ entry = prune_item_entry_create(prune, item);
>+ if (!entry)
>+ return ERR_PTR(-ENOMEM);
>+
>+ err = prune_item_add_prune_vector_set(table, item, entry);
>+ if (err) {
>+ prune_entry_destroy(entry);
>+ return ERR_PTR(err);
>+ }
>+ err = rhashtable_insert_fast(&table->items_ht,
>+ &entry->ht_node, tables_ht_params);
>+ if (err) {
>+ prune_entry_destroy(entry);
>+ return ERR_PTR(err);
>+ }
>+ return entry;
>+}
>+
>+static int prune_table_entry_destroy(struct prune_table *table,
>+ struct prune_item *item)
>+{
>+ struct prune_table_item_entry *entry;
>+ int err;
>+
>+ entry = rhashtable_lookup_fast(&table->items_ht, &item,
>+ tables_ht_params);
>+ if (!entry)
>+ return -EPERM;
>+
>+ err = rhashtable_remove_fast(&table->items_ht, &entry->ht_node,
>+ tables_ht_params);
>+ if (err)
>+ return err;
>+
>+ prune_entry_destroy(entry);
>+
>+ return 0;
>+}
>+
>+static int prune_intersec_item_add(struct prune_intersec_table *intersec_table,
>+ struct prune_item *item,
>+ const struct prune_table_item_entry *entry,
>+ bool neigh)
>+{
>+ struct prune_neighbor_table_items *neigh_item = NULL;
>+ struct prune_intersec_table_item_entry *intersec_entry;
>+ struct prune_intersec_table_item *list_item = NULL;
>+ struct prune_intersec_table_item_key ht_key;
>+ unsigned long *mask;
>+ bool found = true;
>+ int err = 0;
>+
>+ ht_key.mask = kcalloc(1, prune_mask_size(item->mask_len), GFP_ATOMIC);
>+ if (!ht_key.mask)
>+ return -ENOMEM;
>+
>+ bitmap_and(ht_key.mask, intersec_table->mask, item->mask,
>+ item->mask_len);
>+
>+ intersec_entry = rhashtable_lookup_fast(&intersec_table->items_ht,
>+ &ht_key,
>+ intersec_tables_ht_params);
>+ if (!intersec_entry) {
>+ intersec_entry = kzalloc(sizeof(*intersec_entry), GFP_ATOMIC);
>+ if (!intersec_entry)
>+ goto err_entry_alloc;
>+
>+ mask = kcalloc(1, prune_mask_size(item->mask_len), GFP_ATOMIC);
>+ intersec_entry->ht_key.mask = mask;
>+ if (!intersec_entry->ht_key.mask)
>+ goto err_mask_alloc;
>+
>+ intersec_entry->mask_len = item->mask_len;
>+
>+ bitmap_and(intersec_entry->ht_key.mask, intersec_table->mask,
>+ item->mask, item->mask_len);
>+
>+ INIT_LIST_HEAD(&intersec_entry->intersec_table_items);
>+ INIT_LIST_HEAD(&intersec_entry->neighbor_table_items);
>+ found = false;
>+ }
>+
>+ if (!neigh) {
>+ list_item = kzalloc(sizeof(*list_item), GFP_KERNEL);
>+ if (!list_item)
>+ goto err_list_item_alloc;
>+
>+ list_item->entry = entry;
>+ list_add_tail(&list_item->list,
>+ &intersec_entry->intersec_table_items);
>+ } else {
>+ neigh_item = kzalloc(sizeof(*neigh_item), GFP_ATOMIC);
>+ if (!neigh_item)
>+ goto err_nigh_list_item_alloc;
>+
>+ neigh_item->item = item;
>+ list_add_tail(&neigh_item->list,
>+ &intersec_entry->neighbor_table_items);
>+ }
>+ if (!found) {
>+ err = rhashtable_insert_fast(&intersec_table->items_ht,
>+ &intersec_entry->ht_node,
>+ intersec_tables_ht_params);
>+ if (err)
>+ goto err_rhashtable_insert;
>+ }
>+
>+ kfree(ht_key.mask);
>+ return 0;
>+
>+err_rhashtable_insert:
>+ if (!neigh) {
>+ list_del(&list_item->list);
>+ kfree(list_item);
>+ } else {
>+ list_del(&neigh_item->list);
>+ kfree(neigh_item);
>+ }
>+err_nigh_list_item_alloc:
>+err_list_item_alloc:
>+ kfree(intersec_entry->ht_key.mask);
>+err_mask_alloc:
>+ kfree(intersec_entry);
>+err_entry_alloc:
>+ kfree(ht_key.mask);
>+ return err ? err : -ENOMEM;
>+}
>+
>+static int
>+prune_intersec_item_remove(struct prune_intersec_table *intersec_table,
>+ struct prune_item *remove_item, bool neigh)
>+{
>+ struct prune_intersec_table_item_entry *intersec_entry;
>+ struct prune_neighbor_table_items *neigh_item;
>+ struct prune_intersec_table_item *list_item;
>+ struct prune_intersec_table_item_key ht_key;
>+ struct list_head *pos, *tmp;
>+
>+ ht_key.mask = kcalloc(1, prune_mask_size(remove_item->mask_len),
>+ GFP_ATOMIC);
>+ if (!ht_key.mask)
>+ return -ENOMEM;
>+
>+ bitmap_and(ht_key.mask, intersec_table->mask, remove_item->mask,
>+ remove_item->mask_len);
>+
>+ intersec_entry = rhashtable_lookup_fast(&intersec_table->items_ht,
>+ &ht_key,
>+ intersec_tables_ht_params);
>+ if (!intersec_entry) {
>+ kfree(ht_key.mask);
>+ return -EPERM;
>+ }
>+ if (!neigh) {
>+ list_for_each_safe(pos, tmp,
>+ &intersec_entry->intersec_table_items) {
>+ list_item = list_entry(pos, typeof(*list_item), list);
>+ if (list_item->entry->ht_key.item == remove_item) {
>+ list_del(&list_item->list);
>+ kfree(list_item);
>+ break;
>+ }
>+ }
>+ } else {
>+ list_for_each_safe(pos, tmp,
>+ &intersec_entry->neighbor_table_items) {
>+ neigh_item = list_entry(pos, typeof(*neigh_item), list);
>+ if (remove_item == neigh_item->item) {
>+ list_del(&neigh_item->list);
>+ kfree(neigh_item);
>+ break;
>+ }
>+ }
>+ }
>+ if (list_empty(&intersec_entry->intersec_table_items) &&
>+ list_empty(&intersec_entry->neighbor_table_items)) {
>+ rhashtable_remove_fast(&intersec_table->items_ht,
>+ &intersec_entry->ht_node,
>+ intersec_tables_ht_params);
>+ kfree(intersec_entry->ht_key.mask);
>+ kfree(intersec_entry);
>+ }
>+ kfree(ht_key.mask);
>+ return 0;
>+}
>+
>+static struct prune_intersec_table *
>+prune_intrsc_table_create(unsigned int mask_len)
>+{
>+ struct prune_intersec_table *intersec_table;
>+
>+ intersec_table = kzalloc(sizeof(*intersec_table), GFP_KERNEL);
>+ if (!intersec_table)
>+ goto err_intersec_table_alloc;
>+
>+ intersec_table->mask = kcalloc(1, prune_mask_size(mask_len),
>+ GFP_ATOMIC);
>+ if (!intersec_table->mask)
>+ goto err_intersec_table_mask_alloc;
>+
>+ return intersec_table;
>+
>+err_intersec_table_mask_alloc:
>+ kfree(intersec_table);
>+err_intersec_table_alloc:
>+ return NULL;
>+}
>+
>+/* Update the item of the current table to the nighbor item in the
>+ * intersection table
>+ */
>+static void prune_intersec_table_neigh_items_update(struct prune_table *curr_table,
>+ struct prune_intersec_table *intersec_table)
>+{
>+ struct prune_table_item_entry *entry;
>+
>+ if (!atomic_read(&curr_table->items_ht.nelems))
>+ return;
>+
>+ rhashtable_walk_enter(&curr_table->items_ht, &curr_table->iter);
>+ rhashtable_walk_start(&curr_table->iter);
>+
>+ while ((entry = rhashtable_walk_next(&curr_table->iter))) {
>+ prune_intersec_item_add(intersec_table, entry->ht_key.item,
>+ entry, true);
>+ }
>+
>+ rhashtable_walk_stop(&curr_table->iter);
>+ rhashtable_walk_exit(&curr_table->iter);
>+}
>+
>+static int prune_intersec_table_add(struct prune *prune,
>+ struct prune_table *new_table,
>+ struct prune_table *curr_table)
>+{
>+ struct prune_intersec_table *intersec_table1;
>+ struct prune_intersec_table *intersec_table2;
>+ int err;
>+
>+ intersec_table1 = prune_intrsc_table_create(prune->mask_len);
>+ if (!intersec_table1)
>+ goto err_allocate_intersec_table1;
>+
>+ intersec_table2 = prune_intrsc_table_create(prune->mask_len);
>+ if (!intersec_table2)
>+ goto err_allocate_intersec_table2;
>+
>+ bitmap_and(intersec_table1->mask, new_table->mask, curr_table->mask,
>+ prune->mask_len);
>+
>+ bitmap_and(intersec_table2->mask, new_table->mask, curr_table->mask,
>+ prune->mask_len);
>+
>+ /* TODO: maybe need to verify if there is another intersec table with
>+ * same mask and set error ?!.
>+ */
>+ err = rhashtable_init(&intersec_table1->items_ht,
>+ &intersec_tables_ht_params);
>+ if (err)
>+ goto err_rhashtable_init_1;
>+
>+ err = rhashtable_init(&intersec_table2->items_ht,
>+ &intersec_tables_ht_params);
>+ if (err)
>+ goto err_rhashtable_init_2;
>+
>+ /* Add new intersection table to the old table */
>+ intersec_table1->neigh_table = new_table;
>+ prune_intersec_table_neigh_items_update(curr_table, intersec_table1);
>+ list_add(&intersec_table1->list, &curr_table->intersec_table_list);
>+ /* Add new intersection table to new table */
>+ intersec_table2->neigh_table = curr_table;
>+ prune_intersec_table_neigh_items_update(curr_table, intersec_table2);
>+ list_add(&intersec_table2->list, &new_table->intersec_table_list);
>+
>+ return 0;
>+
>+err_rhashtable_init_2:
>+ rhashtable_destroy(&intersec_table2->items_ht);
>+err_rhashtable_init_1:
>+err_allocate_intersec_table2:
>+ kfree(intersec_table1->mask);
>+ kfree(intersec_table1);
>+err_allocate_intersec_table1:
>+ return -ENOMEM;
>+}
>+
>+/* Add new intersection table to all tables */
>+static int prune_intersec_table_build(struct prune *prune,
>+ struct prune_table *new_table)
>+{
>+ struct prune_table *curr_table;
>+ int err;
>+
>+ list_for_each_entry(curr_table, &prune->table_list, list) {
>+ err = prune_intersec_table_add(prune, new_table, curr_table);
>+ if (err) {
>+ /* TODO: need to free memory of new intersec tables,
>+ * that have been created.
>+ */
>+ return err;
>+ }
>+ }
>+ return 0;
>+}
>+
>+static void prune_intersec_rht_free(void *ptr, void *arg)
>+{
>+ struct prune_intersec_table_item_entry *rht_node = ptr;
>+ struct prune_intersec_table_item *intersec_item;
>+ struct prune_neighbor_table_items *neigh_item;
>+ struct list_head *pos, *tmp;
>+
>+ list_for_each_safe(pos, tmp, &rht_node->intersec_table_items) {
>+ intersec_item = list_entry(pos, typeof(*intersec_item), list);
>+ list_del(&intersec_item->list);
>+ kfree(intersec_item);
>+ }
>+ list_for_each_safe(pos, tmp, &rht_node->neighbor_table_items) {
>+ neigh_item = list_entry(pos, typeof(*neigh_item), list);
>+ list_del(&neigh_item->list);
>+ kfree(neigh_item);
>+ }
>+ kfree(rht_node);
>+}
>+
>+static int prune_instersec_table_remove(unsigned int mask_len,
>+ struct prune_table *table,
>+ struct prune_table *table_removed)
>+{
>+ struct prune_intersec_table *curr_intersec_table;
>+ struct list_head *intersec_pos, *tmp;
>+ struct rhashtable *items_rht;
>+ unsigned long *curr_mask;
>+
>+ curr_mask = kcalloc(1, prune_mask_size(mask_len), GFP_ATOMIC);
>+ if (!curr_mask)
>+ return -ENOMEM;
>+
>+ bitmap_and(curr_mask, table->mask, table_removed->mask, mask_len);
>+
>+ list_for_each_safe(intersec_pos, tmp, &table->intersec_table_list) {
>+ curr_intersec_table = list_entry(intersec_pos,
>+ typeof(*curr_intersec_table),
>+ list);
>+ if (bitmap_equal(curr_mask, curr_intersec_table->mask,
>+ mask_len)) {
>+ list_del(&curr_intersec_table->list);
>+ items_rht = &curr_intersec_table->items_ht;
>+ rhashtable_free_and_destroy(items_rht,
>+ prune_intersec_rht_free,
>+ NULL);
>+ kfree(curr_intersec_table->mask);
>+ kfree(curr_intersec_table);
>+ return 0;
>+ }
>+ }
>+ WARN_ON(1); /* Didn't found the wanted intersection table */
>+ return -EPERM;
>+}
>+
>+static int
>+prune_intersec_list_item_add(struct prune_table *item_added_table,
>+ struct prune_table *table,
>+ struct prune_item *item,
>+ const struct prune_table_item_entry *entry,
>+ bool neigh_item)
>+{
>+ struct prune_intersec_table *curr_intersec_table;
>+ int err;
>+
>+ list_for_each_entry(curr_intersec_table, &table->intersec_table_list,
>+ list) {
>+ /* Add the item only to the corresponding tables */
>+ if (!neigh_item ||
>+ curr_intersec_table->neigh_table == item_added_table) {
>+ err = prune_intersec_item_add(curr_intersec_table, item,
>+ entry,
>+ neigh_item);
>+ if (err)
>+ return err;
>+ }
>+ }
>+ return 0;
>+}
>+
>+static int
>+prune_intersec_list_item_remove(struct prune_table *remove_item_table,
>+ struct prune_table *table,
>+ struct prune_item *remove_item,
>+ bool neigh_item)
>+{
>+ struct prune_intersec_table *curr_intersec_table;
>+ int err;
>+
>+ list_for_each_entry(curr_intersec_table, &table->intersec_table_list,
>+ list) {
>+ if (curr_intersec_table->neigh_table == remove_item_table ||
>+ !neigh_item) {
>+ err = prune_intersec_item_remove(curr_intersec_table,
>+ remove_item,
>+ neigh_item);
>+ if (err)
>+ return err;
>+ }
>+ }
>+ return 0;
>+}
>+
>+static int prune_table_item_list_add(struct prune_table *table,
>+ struct prune_table *new_table)
>+{
>+ struct prune_vector_item *vector_item;
>+ struct prune_table_item_entry *entry;
>+
>+ if (!atomic_read(&table->items_ht.nelems))
>+ return 0;
>+
>+ rhashtable_walk_enter(&table->items_ht, &table->iter);
>+ rhashtable_walk_start(&table->iter);
>+
>+ while ((entry = rhashtable_walk_next(&table->iter))) {
>+ vector_item = kzalloc(sizeof(*vector_item), GFP_ATOMIC);
>+ if (!vector_item)
>+ return -ENOMEM;
>+ /* TODO: remove all the items from entry in case of error*/
>+
>+ vector_item->is_prune = true;
>+ vector_item->priv = new_table->priv;
>+ vector_item->table = new_table;
>+ list_add_tail(&vector_item->list,
>+ &entry->table_prune_vector);
>+ }
>+ rhashtable_walk_stop(&table->iter);
>+ rhashtable_walk_exit(&table->iter);
>+
>+ return 0;
>+}
>+
>+static int prune_table_item_list_remove(struct prune_table *table,
>+ struct prune_table *del_table)
>+{
>+ struct prune_vector_item *vector_item;
>+ struct prune_table_item_entry *entry;
>+ struct list_head *pos, *tmp;
>+
>+ if (!atomic_read(&table->items_ht.nelems))
>+ return 0;
>+
>+ rhashtable_walk_enter(&table->items_ht, &table->iter);
>+ rhashtable_walk_start(&table->iter);
>+
>+ while ((entry = rhashtable_walk_next(&table->iter))) {
>+ list_for_each_safe(pos, tmp, &entry->table_prune_vector) {
>+ vector_item = list_entry(pos, typeof(*vector_item),
>+ list);
>+ if (vector_item->table == del_table) {
>+ list_del(&vector_item->list);
>+ kfree(vector_item);
>+ break;
>+ }
>+ }
>+ }
>+ rhashtable_walk_stop(&table->iter);
>+ rhashtable_walk_exit(&table->iter);
>+
>+ return 0;
>+}
>+
>+/* Add new prune table item to each item in each table */
>+static void prune_item_prune_table_add(struct prune *prune,
>+ struct prune_table *new_table)
>+{
>+ struct prune_table *table;
>+
>+ list_for_each_entry(table, &prune->table_list, list) {
>+ prune_table_item_list_add(table, new_table);
>+ }
>+}
>+
>+static void prune_item_prune_table_remove(struct prune *prune,
>+ struct prune_table *del_table)
>+{
>+ struct prune_table *table;
>+
>+ list_for_each_entry(table, &prune->table_list, list) {
>+ if (del_table != table)
>+ prune_table_item_list_remove(table, del_table);
>+ }
>+}
>+
>+/**
>+ * prune_init - initializes a prune object which manage the pruning vector
>+ * between tables
>+ * @mask_len: Sets the mask len (nbits) for all tables in the prune
>+ * object.
>+ * @ops: caller-specific callbacks
>+ * @priv: pointer to a private user data.
>+ *
>+ * Returns a pointer to newly created prune instance in case of success,
>+ * otherwise it returns NULL.
>+ *
>+ * Note: all locking must be provided by the caller.
>+ *
>+ * Before caller could add a table with certain mask, he has to
>+ * initialize the number of tables the prune supports.
>+ */
>+struct prune *prune_init(unsigned int mask_len, const struct prune_ops *ops,
>+ void *priv)
>+{
>+ struct prune *prune;
>+
>+ if (!ops)
>+ return NULL;
>+
>+ prune = kzalloc(sizeof(*prune), GFP_KERNEL);
>+ if (!prune)
>+ return NULL;
>+
>+ prune->table_cnt = 0;
>+ prune->priv = priv;
>+ prune->mask_len = mask_len;
>+ INIT_LIST_HEAD(&prune->table_list);
>+ prune->ops = ops;
>+ tables_ht_params.key_len = mask_len;
>+ intersec_tables_ht_params.key_len = mask_len;
>+
>+ return prune;
>+}
>+EXPORT_SYMBOL(prune_init);
>+
>+/**
>+ * prune_fini - finalizes use of prune object
>+ * @prune: prune object
>+ *
>+ * Note: all locking must be provided by the caller.
>+ */
>+void prune_fini(struct prune *prune)
>+{
>+ WARN_ON(prune->table_cnt > 0 || !list_empty(&prune->table_list));
>+
>+ kfree(prune);
>+}
>+EXPORT_SYMBOL(prune_fini);
>+
>+/**
>+ * prune_table_add - adds new table to the prune object with specific mask
>+ * @prune: prune object
>+ * @table_attr: attribute for this table
>+ *
>+ * Returns ENOMEM in case allocation failed.
>+ * Returns EPERM for invalid parameter.
>+ * otherwise it returns the prune table object.
>+ *
>+ * Note: all locking must be provided by the caller.
>+ * This function may sleep so you must not call it from interrupt
>+ * context or with spin locks held.
>+ */
>+struct prune_table *prune_table_add(struct prune *prune,
>+ struct prune_table_attr *table_attr)
>+{
>+ int err;
>+ struct prune_table *table;
>+
>+ if (prune->mask_len != table_attr->mask_len)
>+ return ERR_PTR(-EPERM);
>+
>+ table = kzalloc(sizeof(*table), GFP_KERNEL);
>+ if (!table)
>+ return ERR_PTR(-ENOMEM);
>+
>+ table->mask = kcalloc(1, prune_mask_size(prune->mask_len), GFP_ATOMIC);
>+ if (!table->mask) {
>+ err = -ENOMEM;
>+ goto err_mask_alloc_fail;
>+ }
>+ bitmap_copy(table->mask, table_attr->mask, table_attr->mask_len);
>+ table->priv = table_attr->priv;
>+ table->ops = prune->ops;
>+ INIT_LIST_HEAD(&table->intersec_table_list);
>+
>+ err = rhashtable_init(&table->items_ht, &tables_ht_params);
>+ if (err)
>+ goto err_rhashtable_init;
>+
>+ err = prune_intersec_table_build(prune, table);
>+ if (err)
>+ goto err_intersec_table_build;
>+
>+ /* Enlarge the prune vector of all item with the new table */
>+ prune_item_prune_table_add(prune, table);
>+
>+ list_add_tail(&table->list, &prune->table_list);
>+
>+ prune->table_cnt++;
>+
>+ return table;
>+
>+/* Error flow path */
Indeed, but that is obvious, please remove pointless comments like this.
>+err_intersec_table_build:
>+ rhashtable_destroy(&table->items_ht);
>+err_rhashtable_init:
>+ kfree(table->mask);
>+err_mask_alloc_fail:
>+ kfree(table);
>+ return ERR_PTR(err);
>+}
>+EXPORT_SYMBOL(prune_table_add);
>+
>+/**
>+ * prune_table_remove - removes a table from the prune object.
>+ * @prune: prune object
>+ * @table_handle: table identification to be removed.
>+ *
>+ * Returns ENOMEM in case allocation failed.
>+ * Returns EPERM for invalid parameter.
>+ * otherwise it returns 0.
>+ *
>+ * Note: all locking must be provided by the caller.
>+ * This function may sleep so you must not call it from interrupt
>+ * context or with spin locks held.
>+ */
>+int prune_table_remove(struct prune *prune, struct prune_table *table)
>+{
>+ struct prune_intersec_table *curr_intersec_table;
>+ struct prune_table *curr_table;
>+ struct rhashtable *items_rht;
>+ struct list_head *pos, *tmp;
>+ int err;
>+
>+ if (prune->table_cnt == 0 ||
>+ atomic_read(&table->items_ht.nelems) != 0) {
>+ WARN_ON(1);
>+ return -EPERM;
>+ }
>+
>+ else if (prune->table_cnt > 1) {
>+ /* Remove the intersection table from neighbor tables */
>+ list_for_each_entry(curr_table, &prune->table_list, list) {
>+ if (curr_table != table) {
>+ err = prune_instersec_table_remove
>+ (prune->mask_len,
>+ curr_table,
>+ table);
>+ if (err)
>+ return err;
>+ }
>+ }
>+ list_for_each_safe(pos, tmp, &table->intersec_table_list) {
>+ curr_intersec_table =
>+ list_entry(pos,
>+ typeof(*curr_intersec_table),
>+ list);
>+ list_del(&curr_intersec_table->list);
>+ items_rht = &curr_intersec_table->items_ht;
>+ rhashtable_free_and_destroy(items_rht,
>+ prune_intersec_rht_free,
>+ NULL);
>+ kfree(curr_intersec_table->mask);
>+ kfree(curr_intersec_table);
>+ }
>+ }
>+ WARN_ON_ONCE(!list_empty(&table->intersec_table_list));
>+
>+ prune_item_prune_table_remove(prune, table);
>+
>+ list_del(&table->list);
>+ rhashtable_destroy(&table->items_ht);
>+ kfree(table->mask);
>+ kfree(table);
>+
>+ prune->table_cnt--;
>+
>+ return 0;
>+}
>+EXPORT_SYMBOL(prune_table_remove);
>+
>+/**
>+ * prune_item_add - adds an item to a table item should have same mask as table.
The sentence makes no sense!
>+ * @prune: prune object
Upper case "P"? Please be consistent.
>+ * @table_handle: Add the item to this table identification.
>+ * @item: The item to add.
>+ *
>+ * Returns EPERM for invalid parameter
>+ * Returns ENOMEM in case allocation failed
>+ * Returns EEXIST if item already exists.
These are pointless. Please remove.
>+ * otherwise it returns 0.
>+ *
>+ * Note: all locking must be provided by the caller.
"All locking"? Sounds really odd.
>+ */
>+int prune_item_add(struct prune *prune, struct prune_table *table,
>+ struct prune_item *item)
>+{
>+ const struct prune_table_item_entry *entry;
>+ struct prune_table *curr_table;
>+ int err;
>+
>+ if (prune->mask_len != item->mask_len)
>+ return -EPERM;
>+
>+ entry = prune_table_entry_create(prune, table, item);
>+ if (IS_ERR(entry))
>+ return PTR_ERR(entry);
>+
>+ /* Add the item to the intersection tables of all tables*/
>+ list_for_each_entry(curr_table, &prune->table_list, list) {
>+ err = prune_intersec_list_item_add(table, curr_table, item,
>+ entry,
>+ curr_table != table ?
>+ true : false);
>+ if (err) {
>+ if (prune_table_entry_destroy(table, item))
>+ WARN_ON(1);
>+
>+ return err;
>+ }
>+ }
>+ /* Update prune vector of the corresponding items of the neighbor
>+ * table
>+ */
>+ err = prune_neigh_table_prune_vector_set(prune, table, item, entry,
>+ true);
>+ if (err) {
>+ if (prune_table_entry_destroy(table, item))
>+ WARN_ON(1);
>+
>+ prune_item_remove(prune, table, item);
>+ return err;
>+ }
>+ return 0;
>+}
>+EXPORT_SYMBOL(prune_item_add);
>+
>+/**
>+ * prune_item_remove - removes an item from a table
>+ * @prune: prune object
>+ * @table_handle: Remove the item from this table identification.
>+ * @item: the item to remove.
>+ *
>+ * Returns EPERM for invalid parameter or item not found.
>+ * Returns ENOMEM in case allocation failed.
>+ * otherwise it returns 0.
>+ *
>+ * Note: all locking must be provided by the caller.
>+ */
>+int prune_item_remove(struct prune *prune, struct prune_table *table,
>+ struct prune_item *item)
>+{
>+ struct prune_table *curr_table;
>+ int err;
>+
>+ if (prune->mask_len != item->mask_len)
>+ return -EPERM;
>+
>+ /* Remove the item from tables in the intersect tables */
>+ list_for_each_entry(curr_table, &prune->table_list, list) {
>+ err = prune_intersec_list_item_remove(table, curr_table, item,
>+ curr_table != table ?
>+ true : false);
>+ if (err)
>+ return err;
>+ }
>+
>+ /* Update prune vector of the corresponding items of the neighbor
>+ * prune_table
>+ */
>+ err = prune_neigh_table_prune_vector_set(prune, table, item, NULL,
>+ false);
>+ if (err)
>+ return err;
>+
>+ err = prune_table_entry_destroy(table, item);
>+ if (err)
>+ return err;
>+
>+ return 0;
>+}
>+EXPORT_SYMBOL(prune_item_remove);
>+
>+MODULE_LICENSE("Dual BSD/GPL");
>+MODULE_AUTHOR("Tal Bar<talb at mellanox.com>");
>+MODULE_DESCRIPTION("Prune lookup table manager");
>diff --git a/lib/test_prune.c b/lib/test_prune.c
>new file mode 100644
>index 0000000..2ea3e94
>--- /dev/null
>+++ b/lib/test_prune.c
>@@ -0,0 +1,917 @@
>+/*
>+ * lib/test_prune.c - Test module for prune
>+ * Copyright (c) 2018 Mellanox Technologies. All rights reserved.
>+ * Copyright (c) 2018 Tal Bar <talb at mellanox.com>
>+ *
>+ * SPDX-License-Identifier: (GPL-2.0 OR BSD-3)
>+ */
>+
>+#define pr_fmt(fmt) KBUILD_MODNAME ": " fmt
>+
>+#include <linux/kernel.h>
>+#include <linux/module.h>
>+#include <linux/err.h>
>+#include <linux/prune.h>
>+#include <linux/bitmap.h>
>+#include <linux/slab.h>
>+
>+static bool test_prune_tables_check_case(struct prune_item_notify *item,
>+ unsigned int prio,
>+ bool *prune_val_arr,
>+ int arr_len,
>+ int test_case)
>+{
>+ struct prune_vector_item *vector_item;
>+ struct list_head *pos;
>+ bool case_passed;
>+ int table_id;
>+
>+ if (item->item.priority != prio) {
>+ WARN(1, "test case [%d] didn't pass priority incorrect [%lu]",
"didn't pass priority incorrect"? What is that supposed to mean?
>+ test_case,
>+ item->item.priority);
>+ return false;
>+ }
>+ table_id = 0;
>+
>+ list_for_each(pos, item->table_prune_list) {
"list_for_each_entry". Only seldom you really need to use "list_for_each"
>+ vector_item = list_entry(pos, typeof(*vector_item), list);
>+ if (table_id == arr_len)
>+ return false;
>+
>+ switch (table_id) {
>+ case 0:
>+ case_passed =
>+ (uintptr_t)vector_item->priv == table_id &&
>+ vector_item->is_prune == prune_val_arr[0];
>+ break;
>+ case 1:
>+ case_passed =
>+ (uintptr_t)vector_item->priv == table_id &&
>+ vector_item->is_prune == prune_val_arr[1];
>+ break;
>+ case 2:
>+ case_passed =
>+ (uintptr_t)vector_item->priv == table_id &&
>+ vector_item->is_prune == prune_val_arr[2];
>+ break;
>+ case 3:
>+ case_passed =
>+ (uintptr_t)vector_item->priv == table_id &&
>+ vector_item->is_prune == prune_val_arr[3];
>+ break;
>+ case 4:
>+ case_passed =
>+ (uintptr_t)vector_item->priv == table_id &&
>+ vector_item->is_prune == prune_val_arr[4];
>+ break;
>+ case 5:
>+ case_passed =
>+ (uintptr_t)vector_item->priv == table_id &&
>+ vector_item->is_prune == prune_val_arr[5];
>+ break;
>+ default:
>+ case_passed = false;
>+ break;
>+ }
>+ table_id++;
>+
>+ if (!case_passed) {
>+ WARN(1, "test case [%d] didn't pass for table [%d]",
>+ test_case,
>+ table_id);
>+ return case_passed;
>+ }
>+ }
>+ return case_passed;
>+}
>+
>+static void test_prune_notification_print(struct prune_item_notify *item,
>+ bool print)
>+{
>+ struct prune_vector_item *vector_item;
>+ struct list_head *pos;
>+ int i;
>+
>+ if (print) {
>+ i = 0;
>+ pr_info("item mask: %lu\n", *item->item.mask);
>+ pr_info("item prio: %lu\n", item->item.priority);
>+
>+ list_for_each(pos, item->table_prune_list) {
>+ vector_item = list_entry(pos, typeof(*vector_item),
>+ list);
>+ pr_info("i = [%d], table priv: %lu\t is prune: %s\t pruned table *: %p\n",
>+ i,
>+ (uintptr_t)vector_item->priv,
>+ vector_item->is_prune ? "Yes" : "No",
>+ vector_item->table);
>+ i++;
>+ }
>+ }
>+}
>+
>+static void test_prune_subsequent_notify(struct prune_table *table,
>+ struct prune_item_notify *item,
>+ unsigned int item_cnt)
>+{
>+ bool prune_value_case0[2] = {true, false};
>+ bool prune_value_case1[2] = {false, true};
>+ bool prune_value_case2[3] = {true, true, true};
>+ static int test_case;
>+
>+ test_prune_notification_print(item, false);
>+
>+ switch (test_case) {
>+ case 0:
>+ test_prune_tables_check_case(item, 1, prune_value_case0,
>+ ARRAY_SIZE(prune_value_case0),
>+ test_case);
>+ break;
>+ case 1:
>+ test_prune_tables_check_case(item, 2, prune_value_case1,
>+ ARRAY_SIZE(prune_value_case1),
>+ test_case);
>+ break;
>+ case 2:
>+ test_prune_tables_check_case(item, 2, prune_value_case2,
>+ ARRAY_SIZE(prune_value_case2),
>+ test_case);
>+ break;
>+ default:
>+ WARN(1, "unexpected test case %d", test_case);
>+ break;
>+ }
>+ test_case++;
>+}
>+
>+static void test_prune_flows_1_notify(struct prune_table *table,
>+ struct prune_item_notify *item,
>+ unsigned int item_cnt)
>+{
>+ bool prune_value_arr_case0[2] = {true, false};
>+ bool prune_value_arr_case1[2] = {false, true};
>+ bool prune_value_arr_case2[2] = {true, true};
>+ bool prune_value_arr_case3[2] = {true, true};
>+ static int test_case;
>+
>+ test_prune_notification_print(item, false);
>+
>+ switch (test_case) {
>+ case 0:
>+ test_prune_tables_check_case(item, 7, prune_value_arr_case0,
>+ ARRAY_SIZE(prune_value_arr_case0),
>+ test_case);
>+ break;
>+ case 1:
>+ test_prune_tables_check_case(item, 5, prune_value_arr_case1,
>+ ARRAY_SIZE(prune_value_arr_case1),
>+ test_case);
>+ break;
>+ case 2:
>+ test_prune_tables_check_case(item, 7, prune_value_arr_case2,
>+ ARRAY_SIZE(prune_value_arr_case2),
>+ test_case);
>+ break;
>+ case 3:
>+ test_prune_tables_check_case(item, 5, prune_value_arr_case3,
>+ ARRAY_SIZE(prune_value_arr_case3),
>+ test_case);
>+ break;
>+ default:
>+ WARN(1, "unexpected test case %d", test_case);
>+ break;
>+ }
>+
>+ test_case++;
>+}
>+
>+static void test_prune_flows_2_notify(struct prune_table *table,
>+ struct prune_item_notify *item,
>+ unsigned int item_cnt)
>+{
>+ test_prune_notification_print(item, true);
>+}
>+
>+static void test_prune_basic_notify(struct prune_table *table,
>+ struct prune_item_notify *item,
>+ unsigned int item_cnt)
>+{
>+ test_prune_notification_print(item, false);
>+}
>+
>+static const struct prune_ops test_prune_add_new_table_subsequent_ops = {
>+ .prune_item_notify = test_prune_subsequent_notify,
>+ .prune_mask_comparable = NULL,
>+};
>+
>+static const struct prune_ops test_prune_flows_add_delete_items_1_ops = {
>+ .prune_item_notify = test_prune_flows_1_notify,
>+ .prune_mask_comparable = NULL,
Pointless initialization, remove. Please, in the whole code.
>+};
>+
>+static const struct prune_ops test_prune_flows_add_delete_items_2_ops = {
>+ .prune_item_notify = test_prune_flows_2_notify,
>+ .prune_mask_comparable = NULL,
>+};
>+
>+static const struct prune_ops test_prune_basic_ops = {
>+ .prune_item_notify = test_prune_basic_notify,
>+ .prune_mask_comparable = NULL,
>+};
>+
>+static int table_attr_create(struct prune_table_attr *table_attr,
>+ unsigned int mask_len,
>+ unsigned int table_cnt)
>+{
>+ unsigned long i, j;
>+
>+ for (i = 0; i < table_cnt; i++) {
>+ table_attr[i].mask = kcalloc(1, prune_mask_size(mask_len),
>+ GFP_KERNEL);
>+ if (!table_attr[i].mask) {
>+ if (i > 0) {
>+ for (j = i - 1; j > -1; j--)
>+ kfree(table_attr[j].mask);
>+ }
>+ return -ENOMEM;
>+ }
>+ table_attr[i].mask_len = mask_len;
>+ table_attr[i].priv = (int *)i;
>+ }
>+ return 0;
>+}
>+
>+static void table_attr_destroy(struct prune_table_attr *table_attr,
>+ unsigned int table_cnt)
>+{
>+ int i;
>+
>+ for (i = 0; i < table_cnt; i++)
>+ kfree(table_attr[i].mask);
>+}
>+
>+static void prune_item_arr_destroy(struct prune_item *pi_arr,
>+ unsigned int pi_cnt)
>+{
>+ int i;
>+
>+ for (i = 0; i < pi_cnt; i++)
>+ kfree(pi_arr[i].mask);
>+}
>+
>+static int prune_item_arr_create(struct prune_item *pi_arr, unsigned int pi_cnt,
>+ unsigned int pi_nbits)
>+{
>+ int i, j = 0;
>+
>+ for (i = 0; i < pi_cnt; i++) {
>+ pi_arr[i].mask = kcalloc(1, prune_mask_size(pi_nbits),
>+ GFP_KERNEL);
>+ if (!pi_arr[i].mask) {
>+ if (i > 0)
>+ for (j = i - 1; j > -1; j--)
>+ kfree(pi_arr[j].mask);
>+ return -ENOMEM;
>+ }
>+ pi_arr[i].mask_len = pi_nbits;
>+ bitmap_clear(pi_arr[i].mask, 0, pi_arr[i].mask_len);
>+ }
>+ return 0;
>+}
>+
>+/*
>+ * basic test: test add / remove table and item without checking their prune
>+ * vector
>+ */
>+static int test_prune_basic(void)
>+{
>+ unsigned int item_cnt = 3;
>+ unsigned int tbl_cnt = 3;
>+ const struct prune_ops *ops = &test_prune_basic_ops;
>+ struct prune_table_attr table_attr[tbl_cnt];
>+ struct prune_table *table_arr[tbl_cnt];
>+ struct prune_item pi_arr[item_cnt];
>+ unsigned int nbits = 40;
>+ struct prune *prune;
>+ int err;
>+
>+ prune = prune_init(nbits, ops, NULL);
>+ if (IS_ERR(prune))
>+ return PTR_ERR(prune);
>+
>+ err = table_attr_create(table_attr, nbits, tbl_cnt);
>+ if (err)
>+ return err;
>+
>+ err = prune_item_arr_create(pi_arr, item_cnt, nbits);
>+ if (err)
>+ return err;
>+
>+ bitmap_clear(table_attr[0].mask, 0, table_attr[0].mask_len);
>+ bitmap_set(table_attr[0].mask, 0, 2);
>+ table_arr[0] = prune_table_add(prune, &table_attr[0]);
>+ if (IS_ERR(table_arr[0]))
>+ return PTR_ERR(table_arr[0]);
>+
>+ bitmap_clear(table_attr[1].mask, 0, table_attr[1].mask_len);
>+ bitmap_set(table_attr[1].mask, 1, 2);
>+ table_arr[1] = prune_table_add(prune, &table_attr[1]);
>+ if (IS_ERR(table_arr[1]))
>+ return PTR_ERR(table_arr[1]);
>+
>+ bitmap_clear(table_attr[2].mask, 0, table_attr[2].mask_len);
>+ bitmap_set(table_attr[2].mask, 2, 2);
>+ table_arr[2] = prune_table_add(prune, &table_attr[2]);
>+ if (IS_ERR(table_arr[2]))
>+ return PTR_ERR(table_arr[2]);
>+
>+ pi_arr[0].priority = 1;
>+ pi_arr[0].priv = NULL;
>+ bitmap_set(pi_arr[0].mask, 0, 2);
>+ err = prune_item_add(prune, table_arr[0], &pi_arr[0]);
>+ if (err)
>+ return err;
>+
>+ pi_arr[1].priority = 2;
>+ pi_arr[1].priv = NULL;
>+ bitmap_set(pi_arr[1].mask, 1, 2);
>+ err = prune_item_add(prune, table_arr[1], &pi_arr[1]);
>+ if (err)
>+ return err;
>+
>+ pi_arr[2].priority = 3;
>+ pi_arr[2].priv = NULL;
>+ bitmap_set(pi_arr[2].mask, 2, 2);
>+ /* Negative test */
>+ err = prune_item_remove(prune, table_arr[2], &pi_arr[2]);
>+ if (err != -EPERM)
>+ return err;
>+
>+ err = prune_item_add(prune, table_arr[2], &pi_arr[2]);
>+ if (err)
>+ return err;
>+
>+ err = prune_item_remove(prune, table_arr[0], &pi_arr[0]);
>+ if (err)
>+ return err;
>+
>+ err = prune_item_remove(prune, table_arr[1], &pi_arr[1]);
>+ if (err)
>+ return err;
>+
>+ err = prune_item_remove(prune, table_arr[2], &pi_arr[2]);
>+ if (err)
>+ return err;
>+
>+ prune_table_remove(prune, table_arr[0]);
>+
>+ prune_table_remove(prune, table_arr[1]);
>+
>+ prune_table_remove(prune, table_arr[2]);
>+
>+ prune_fini(prune);
>+
>+ prune_item_arr_destroy(pi_arr, item_cnt);
>+ table_attr_destroy(table_attr, tbl_cnt);
>+
>+ return 0;
>+}
>+
>+static int test_prune_flows_add_delete_items_1(void)
>+{
>+ unsigned int item_cnt = 3;
>+ unsigned int tbl_cnt = 2;
>+ const struct prune_ops *ops = &test_prune_flows_add_delete_items_1_ops;
>+ struct prune_table_attr table_attr[tbl_cnt];
>+ struct prune_table *table_arr[tbl_cnt];
>+ struct prune_item pi_arr[item_cnt];
>+ unsigned int nbits = 40;
>+ struct prune *prune;
>+ int err;
>+
>+ prune = prune_init(nbits, ops, NULL);
Just use test_prune_flows_add_delete_items_1_ops directly.
Same in other functions.
>+ if (IS_ERR(prune))
>+ return PTR_ERR(prune);
>+
>+ err = table_attr_create(table_attr, nbits, tbl_cnt);
>+ if (err)
>+ return err;
>+
>+ err = prune_item_arr_create(pi_arr, item_cnt, nbits);
>+ if (err)
>+ return err;
>+
>+ /* Create table with mask u.u.u.x.x - table 0*/
>+ bitmap_clear(table_attr[0].mask, 0, table_attr[0].mask_len);
>+ bitmap_set(table_attr[0].mask, 0, 24); /* set care on #1-3 byte*/
>+ table_arr[0] = prune_table_add(prune, &table_attr[0]);
>+ if (IS_ERR(table_arr[0]))
>+ return PTR_ERR(table_arr[0]);
>+
>+ /* Create table with mask x.u.u.u.x */
>+ bitmap_clear(table_attr[1].mask, 0, table_attr[1].mask_len);
>+ bitmap_set(table_attr[1].mask, 8, 24); /* set care on #2-4 byte*/
>+ table_arr[1] = prune_table_add(prune, &table_attr[1]);
>+ if (IS_ERR(table_arr[0]))
>+ return PTR_ERR(table_arr[0]);
>+
>+ /* Create item0 x.2.3.4.x prio 10 */
>+ pi_arr[0].priority = 10;
>+ pi_arr[0].priv = NULL;
>+ bitmap_set(pi_arr[0].mask, 14, 1); /* set 2 on #2 byte*/
>+ bitmap_set(pi_arr[0].mask, 22, 2); /* set 3 on #3 byte*/
>+ bitmap_set(pi_arr[0].mask, 29, 1); /* set 4 on #4 byte*/
>+
>+ /* Create item1 x.2.3.5.x prio 5*/
>+ pi_arr[1].priority = 5;
>+ pi_arr[1].priv = NULL;
>+ bitmap_set(pi_arr[1].mask, 14, 1); /* set 2 on #2 byte*/
>+ bitmap_set(pi_arr[1].mask, 22, 2); /* set 3 on #3 byte*/
>+ bitmap_set(pi_arr[1].mask, 29, 1); /* set 5 on #4 byte*/
>+ bitmap_set(pi_arr[1].mask, 31, 1); /* set 5 on #4 byte*/
>+
>+ /* Add item0: x.2.3.4.x to table 1 */
>+ err = prune_item_add(prune, table_arr[1], &pi_arr[0]);
>+ if (err)
>+ return err;
>+
>+ /* Expected prune vector for item1 and item2
>+ * table 0 prune
>+ * table 1 prune
>+ * --> Shoudn't not get notification
>+ */
>+
>+ /* Add item1: x.2.3.5.x to table 1 */
>+ err = prune_item_add(prune, table_arr[1], &pi_arr[1]);
>+ if (err)
>+ return err;
>+
>+ /* Expected prune vector for both item
>+ * table 0 prune
>+ * table 1 prune
>+ * --> Shoudn't not get notification
>+ */
>+
>+ /* Create item2 1.2.3.x.x prio 7 */
>+ pi_arr[2].priority = 7;
>+ pi_arr[2].priv = NULL;
>+ bitmap_set(pi_arr[2].mask, 7, 1); /* set 1 on #1 byte*/
>+ bitmap_set(pi_arr[2].mask, 14, 1); /* set 2 on #2 byte*/
>+ bitmap_set(pi_arr[2].mask, 22, 2); /* set 3 on #3 byte*/
>+
>+ /* Add item2: 1.2.3.x.x prio 7 to table 0 */
>+ err = prune_item_add(prune, table_arr[0], &pi_arr[2]);
>+ if (err)
>+ return err;
>+
>+ /* Expected prune vector per item
>+ * item0 in table 1: (x.2.3.4.x prio 10)
>+ * table 0 prune (no change)
>+ * table 1 prune (no change)
>+ * --> shoudn't not get notification
>+ *item1 in table 1(x.2.3.5.x prio 5):
You are missing " ".
>+ * table 0 don't prune (changed)
>+ * table 1 prune (changed)
>+ * --> Should get notification
>+ *item2 in table 0 (1.2.3.x.x prio 7):
You are missing " ".
>+ * table 0 prune (no change)
>+ * table 1 don't prune (no change)
>+ * --> Should get notification
>+ */
>+
>+ /* Delete item: 0: (x.2.3.4.x prio 10 from table 1 */
>+ err = prune_item_remove(prune, table_arr[1], &pi_arr[0]);
>+ if (err)
>+ return err;
>+
>+ /* Expected prune vector
>+ * item0: item is deleted
>+
Remove this empty line.
>+ *item1 table 1(x.2.3.5.x prio 5)::
You are missing " ".
>+ * table 0 don't prune
>+ * table 1 prune
>+ *item2 table 0 (1.2.3.x.x prio 7):
You are missing " ".
>+ * table 0 prune
>+ * table 1 prune (changed)
>+ */
>+
>+ /* Delete item: 2: (1.2.3.x.x prio 7) from table 0 */
>+ err = prune_item_remove(prune, table_arr[0], &pi_arr[2]);
>+ if (err)
>+ return err;
>+
>+ /* Expected prune vector
>+ * item1: item is deleted
>+
Okay, it's a pattern. Please fix all occurances.
>+ *item1 table 1(x.2.3.5.x prio 5)::
Actually you miss " " ^^ here.
Oh my, this is really annoying. Could you please be more careful about
formatting???
>+ * table 0 prune (changed)
>+ * table 1 prune
>+ *item2 table 0 (1.2.3.x.x prio 7):
>+ * item is deleted
>+ */
>+
>+ /* Delete item: 1: (x.2.3.5.x prio 5) from table 1 */
>+ err = prune_item_remove(prune, table_arr[1], &pi_arr[1]);
>+ if (err)
>+ return err;
>+
>+ err = prune_table_remove(prune, table_arr[0]);
>+ if (err)
>+ return err;
>+
>+ err = prune_table_remove(prune, table_arr[1]);
>+ if (err)
>+ return err;
>+
>+ prune_fini(prune);
>+
>+ prune_item_arr_destroy(pi_arr, item_cnt);
>+ table_attr_destroy(table_attr, tbl_cnt);
>+
>+ return 0;
>+}
>+
>+static int test_prune_flows_add_delete_item_2(void)
>+{
>+ unsigned int item_cnt = 6;
>+ unsigned int tbl_cnt = 3;
>+ const struct prune_ops *ops = &test_prune_flows_add_delete_items_2_ops;
>+ struct prune_table_attr table_attr[tbl_cnt];
>+ struct prune_table *table_arr[tbl_cnt];
>+ struct prune_item pi_arr[item_cnt];
>+ unsigned int nbits = 40;
>+ struct prune *prune;
>+ int err;
>+
>+ prune = prune_init(nbits, ops, NULL);
>+ if (IS_ERR(prune))
>+ return PTR_ERR(prune);
>+
>+ err = table_attr_create(table_attr, nbits, tbl_cnt);
>+ if (err)
>+ return err;
>+
>+ err = prune_item_arr_create(pi_arr, item_cnt, nbits);
>+ if (err)
>+ return err;
>+
>+ /* tables:
>+ * table 0: x.x.u.u.u
>+ * table 1: u.u.u.x.x
>+ * table 2: x.u.x.x.x
>+ */
>+
>+ /* Create table with mask x.x.u.u.u - table 0 */
>+ bitmap_clear(table_attr[0].mask, 0, table_attr[0].mask_len);
>+ bitmap_set(table_attr[0].mask, 16, 24); /* set care on #3-5 byte*/
>+
>+ /* Create table with mask u.u.u.x.x - table 1 */
>+ bitmap_clear(table_attr[1].mask, 0, table_attr[1].mask_len);
>+ bitmap_set(table_attr[1].mask, 0, 24); /* set care on #1-3 byte*/
>+
>+ /* Create table with mask x.u.x.x.x - table 2 */
>+ bitmap_clear(table_attr[2].mask, 2, table_attr[2].mask_len);
>+ bitmap_set(table_attr[2].mask, 8, 8); /* set care on #2 byte*/
>+
>+ /* Create rules */
>+
>+ /* Create item0 x.x.3.5.5 prio 5 */
>+ pi_arr[0].priority = 5;
>+ pi_arr[0].priv = NULL;
>+ bitmap_set(pi_arr[0].mask, 22, 2); /* set 3 on #3 byte */
>+ bitmap_set(pi_arr[0].mask, 29, 1); /* set 5 on #4 byte */
>+ bitmap_set(pi_arr[0].mask, 31, 1); /* set 5 on #4 byte */
>+ bitmap_set(pi_arr[0].mask, 37, 1); /* set 5 on #5 byte */
>+ bitmap_set(pi_arr[0].mask, 39, 1); /* set 5 on #5 byte */
>+
>+ /* Create item1 1.2.3.x.x prio 5 */
>+ pi_arr[1].priority = 5;
>+ pi_arr[1].priv = NULL;
>+ bitmap_set(pi_arr[1].mask, 7, 1); /* set 1 on #1 byte */
>+ bitmap_set(pi_arr[1].mask, 14, 1); /* set 2 on #2 byte */
>+ bitmap_set(pi_arr[1].mask, 22, 2); /* set 3 on #3 byte */
>+
>+ /* Create item2 x.x.3.5.x prio 10 */
>+ pi_arr[2].priority = 10;
>+ pi_arr[2].priv = NULL;
>+ bitmap_set(pi_arr[2].mask, 23, 1); /* set 3 on #3 byte */
>+ bitmap_set(pi_arr[2].mask, 29, 1); /* set 5 on #4 byte */
>+ bitmap_set(pi_arr[2].mask, 31, 1); /* set 5 on #4 byte */
>+
>+ /* Create item3 x.2.x.x.x prio 3 */
>+ pi_arr[3].priority = 3;
>+ pi_arr[3].priv = NULL;
>+ bitmap_set(pi_arr[3].mask, 14, 2); /* set 2 on #2 byte */
>+
>+ /* Create item4 x.x.x.x.6 prio 5 */
>+ pi_arr[4].priority = 5;
>+ pi_arr[4].priv = NULL;
>+ bitmap_set(pi_arr[4].mask, 37, 2); /* set 6 on #5 byte */
>+
>+ /* Create item5 2.2.3.x.x prio 7 */
>+ pi_arr[5].priority = 7;
>+ pi_arr[5].priv = NULL;
>+ bitmap_set(pi_arr[5].mask, 7, 1); /* set 2 on #1 byte */
>+ bitmap_set(pi_arr[5].mask, 14, 1); /* set 2 on #2 byte */
>+ bitmap_set(pi_arr[5].mask, 22, 2); /* set 3 on #3 byte */
>+
>+ table_arr[0] = prune_table_add(prune, &table_attr[0]);
>+ if (IS_ERR(table_arr[0]))
>+ return PTR_ERR(table_arr[0]);
>+
>+ err = prune_item_add(prune, table_arr[0], &pi_arr[0]);
>+ if (err)
>+ return err;
>+
>+ table_arr[1] = prune_table_add(prune, &table_attr[1]);
>+ if (IS_ERR(table_arr[1]))
>+ return PTR_ERR(table_arr[1]);
>+
>+ err = prune_item_add(prune, table_arr[1], &pi_arr[1]);
>+ if (err)
>+ return err;
>+
>+ err = prune_item_add(prune, table_arr[0], &pi_arr[2]);
>+ if (err)
>+ return err;
>+
>+ table_arr[2] = prune_table_add(prune, &table_attr[2]);
>+ if (IS_ERR(table_arr[2]))
>+ return PTR_ERR(table_arr[2]);
>+
>+ err = prune_item_add(prune, table_arr[2], &pi_arr[3]);
>+ if (err)
>+ return err;
>+
>+ err = prune_item_add(prune, table_arr[0], &pi_arr[4]);
>+ if (err)
>+ return err;
>+
>+ err = prune_item_add(prune, table_arr[1], &pi_arr[5]);
>+ if (err)
>+ return err;
>+
>+ /* Free resources */
>+ err = prune_item_remove(prune, table_arr[0], &pi_arr[0]);
>+ if (err)
>+ return err;
>+
>+ err = prune_item_remove(prune, table_arr[1], &pi_arr[1]);
>+ if (err)
>+ return err;
>+
>+ err = prune_item_remove(prune, table_arr[0], &pi_arr[2]);
>+ if (err)
>+ return err;
>+
>+ err = prune_item_remove(prune, table_arr[2], &pi_arr[3]);
>+ if (err)
>+ return err;
>+
>+ err = prune_table_remove(prune, table_arr[2]);
>+ if (err)
>+ return err;
>+
>+ err = prune_item_remove(prune, table_arr[0], &pi_arr[4]);
>+ if (err)
>+ return err;
>+
>+ err = prune_table_remove(prune, table_arr[0]);
>+ if (err)
>+ return err;
>+
>+ err = prune_item_remove(prune, table_arr[1], &pi_arr[5]);
>+ if (err)
>+ return err;
>+
>+ err = prune_table_remove(prune, table_arr[1]);
>+ if (err)
>+ return err;
>+
>+ prune_fini(prune);
>+
>+ prune_item_arr_destroy(pi_arr, item_cnt);
>+ table_attr_destroy(table_attr, tbl_cnt);
>+
>+ return 0;
>+}
>+
>+static int test_prune_add_new_table_with_item_subsequent_to_curr_tables(void)
>+{
>+ unsigned int item_cnt = 8;
>+ unsigned int tbl_cnt = 4;
>+ const struct prune_ops *ops = &test_prune_add_new_table_subsequent_ops;
>+ struct prune_table_attr table_attr[tbl_cnt];
>+ struct prune_table *table_arr[tbl_cnt];
>+ struct prune_item pi_arr[item_cnt];
>+ unsigned int nbits = 40;
>+ struct prune *prune;
>+ int err;
>+
>+ prune = prune_init(nbits, ops, NULL);
>+ if (IS_ERR(prune))
>+ return PTR_ERR(prune);
>+
>+ err = table_attr_create(table_attr, nbits, tbl_cnt);
>+ if (err)
>+ return err;
>+
>+ err = prune_item_arr_create(pi_arr, item_cnt, nbits);
>+ if (err)
>+ return err;
>+
>+ /* tables:
>+ * table 0: u.u.u.x.x
>+ * table 1: x.u.u.u.x
>+ * table 2: x.x.u.u.u
>+ */
>+
>+ /* Create table with mask u.u.u.x.x - table 0 */
>+ bitmap_clear(table_attr[0].mask, 0, table_attr[0].mask_len);
>+ bitmap_set(table_attr[0].mask, 0, 24); /* set care on #1-3 byte*/
>+ table_arr[0] = prune_table_add(prune, &table_attr[0]);
>+ if (IS_ERR(table_arr[0]))
>+ return PTR_ERR(table_arr[0]);
>+
>+ /* Create table with mask x.u.u.u.x table 1 */
>+ bitmap_clear(table_attr[1].mask, 0, table_attr[1].mask_len);
>+ bitmap_set(table_attr[1].mask, 8, 24); /* set care on #2-4 byte*/
>+ table_arr[1] = prune_table_add(prune, &table_attr[1]);
>+ if (IS_ERR(table_arr[1]))
>+ return PTR_ERR(table_arr[1]);
>+
>+ /* Add rules */
>+
>+ /* Create item1 1.2.3.x.x prio 1 */
>+ pi_arr[0].priority = 1;
>+ pi_arr[0].priv = NULL;
>+ bitmap_set(pi_arr[0].mask, 7, 1); /* set 1 on #1 byte */
>+ bitmap_set(pi_arr[0].mask, 14, 1); /* set 2 on #2 byte */
>+ bitmap_set(pi_arr[0].mask, 22, 2); /* set 3 on #3 byte */
>+
>+ /* Create item2 x.2.3.4.x prio 5 */
>+ pi_arr[1].priority = 5;
>+ pi_arr[1].priv = NULL;
>+ bitmap_set(pi_arr[1].mask, 14, 1); /* set 2 on #2 byte */
>+ bitmap_set(pi_arr[1].mask, 22, 2); /* set 3 on #3 byte */
>+ bitmap_set(pi_arr[1].mask, 29, 1); /* set 4 on #4 byte */
>+
>+ /* Create item3 x.x.3.9.9 prio 10 */
>+ pi_arr[2].priority = 10;
>+ pi_arr[2].priv = NULL;
>+ bitmap_set(pi_arr[2].mask, 22, 2); /* set 3 on #3 byte */
>+ bitmap_set(pi_arr[2].mask, 28, 1); /* set 9 on #4 byte */
>+ bitmap_set(pi_arr[2].mask, 31, 1); /* set 9 on #4 byte */
>+ bitmap_set(pi_arr[2].mask, 36, 1); /* set 9 on #5 byte */
>+ bitmap_set(pi_arr[2].mask, 39, 1); /* set 9 on #5 byte */
>+
>+ /* Create item4 2.2.4.x.x prio 3 */
>+ pi_arr[3].priority = 3;
>+ pi_arr[3].priv = NULL;
>+ bitmap_set(pi_arr[3].mask, 6, 1); /* set 2 on #1 byte */
>+ bitmap_set(pi_arr[3].mask, 14, 1); /* set 2 on #2 byte */
>+ bitmap_set(pi_arr[3].mask, 21, 1); /* set 4 on #3 byte */
>+
>+ /* Create item5 x.x.4.5.x prio 8 */
>+ pi_arr[4].priority = 8;
>+ pi_arr[4].priv = NULL;
>+ bitmap_set(pi_arr[4].mask, 21, 1); /* set 4 on #3 byte */
>+ bitmap_set(pi_arr[4].mask, 29, 1); /* set 5 on #4 byte */
>+ bitmap_set(pi_arr[4].mask, 31, 1); /* set 5 on #4 byte */
>+
>+ /* Create item6 x.2.4.7.x prio 2 */
>+ pi_arr[5].priority = 2;
>+ pi_arr[5].priv = NULL;
>+ bitmap_set(pi_arr[5].mask, 14, 1); /* set 2 on #2 byte */
>+ bitmap_set(pi_arr[5].mask, 21, 1); /* set 4 on #3 byte */
>+ bitmap_set(pi_arr[5].mask, 29, 3); /* set 7 on #4 byte */
>+
>+ /* Create item7 x.2.x.9.x prio 2 */
>+ pi_arr[6].priority = 2;
>+ pi_arr[6].priv = NULL;
>+ bitmap_set(pi_arr[6].mask, 14, 1); /* set 2 on #2 byte */
>+ bitmap_set(pi_arr[6].mask, 28, 1); /* set 9 on #4 byte */
>+ bitmap_set(pi_arr[6].mask, 31, 1); /* set 9 on #4 byte */
>+
>+ err = prune_item_add(prune, table_arr[0], &pi_arr[0]);
>+ if (err)
>+ return err;
>+
>+ err = prune_item_add(prune, table_arr[1], &pi_arr[1]);
>+ if (err)
>+ return err;
>+
>+ err = prune_item_add(prune, table_arr[0], &pi_arr[3]);
>+ if (err)
>+ return err;
>+
>+ err = prune_item_add(prune, table_arr[1], &pi_arr[5]);
>+ if (err)
>+ return err;
>+
>+ err = prune_item_add(prune, table_arr[1], &pi_arr[6]);
>+ if (err)
>+ return err;
>+
>+ /* Create table with mask x.x.u.u.u table 2 */
>+ bitmap_clear(table_attr[2].mask, 0, table_attr[2].mask_len);
>+ bitmap_set(table_attr[2].mask, 16, 24); /* set care on #2-5 byte*/
>+ table_arr[2] = prune_table_add(prune, &table_attr[2]);
>+ if (IS_ERR(table_arr[2]))
>+ return PTR_ERR(table_arr[2]);
>+
>+ err = prune_item_add(prune, table_arr[2], &pi_arr[2]);
>+ if (err)
>+ return err;
>+
>+ err = prune_item_add(prune, table_arr[2], &pi_arr[4]);
>+ if (err)
>+ return err;
>+
>+ err = prune_item_remove(prune, table_arr[0], &pi_arr[0]);
>+ if (err)
>+ return err;
>+
>+ err = prune_item_remove(prune, table_arr[1], &pi_arr[1]);
>+ if (err)
>+ return err;
>+
>+ err = prune_item_remove(prune, table_arr[2], &pi_arr[2]);
>+ if (err)
>+ return err;
>+
>+ err = prune_item_remove(prune, table_arr[0], &pi_arr[3]);
>+ if (err)
>+ return err;
>+
>+ err = prune_item_remove(prune, table_arr[2], &pi_arr[4]);
>+ if (err)
>+ return err;
>+
>+ err = prune_table_remove(prune, table_arr[2]);
>+ if (err)
>+ return err;
>+
>+ err = prune_item_remove(prune, table_arr[1], &pi_arr[5]);
>+ if (err)
>+ return err;
>+
>+ err = prune_item_remove(prune, table_arr[1], &pi_arr[6]);
>+ if (err)
>+ return err;
>+
>+ err = prune_table_remove(prune, table_arr[0]);
>+ if (err)
>+ return err;
>+
>+ err = prune_table_remove(prune, table_arr[1]);
>+ if (err)
>+ return err;
>+
>+ prune_fini(prune);
>+
>+ prune_item_arr_destroy(pi_arr, item_cnt);
>+ table_attr_destroy(table_attr, tbl_cnt);
>+
>+ return 0;
>+}
>+
>+static int test_prune(void)
>+{
>+ int err;
>+
>+ err = test_prune_basic();
>+ if (err)
>+ return err;
>+
>+ err = test_prune_flows_add_delete_items_1();
>+ if (err)
>+ return err;
>+
>+ err = test_prune_add_new_table_with_item_subsequent_to_curr_tables();
>+ if (err)
>+ return err;
>+
>+ err = test_prune_flows_add_delete_item_2();
>+ if (err)
>+ return err;
>+
>+ return 0;
>+}
>+
>+static int __init test_prune_init(void)
>+{
>+ return test_prune();
>+}
>+
>+static void __exit test_prune_exit(void)
>+{
>+}
>+
>+module_init(test_prune_init);
>+module_exit(test_prune_exit);
>+
>+MODULE_LICENSE("Dual BSD/GPL");
>+MODULE_AUTHOR("Tal Bar <talb at mellanox.com>");
>+MODULE_DESCRIPTION("Test module for prune");
>--
>2.8.0
>
More information about the Linux-mlxsw
mailing list