new file mode 100644
@@ -0,0 +1,56 @@
+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.
+
+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.
+
+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.
+
+
+Flows
+=====
+Direction of prune calculation:
+-------------------------------
+A*->A: Calculate my own prune vector
+A->A*: Calculate other items prune vector in the prune object
+
+Insert item 'R'
+---------------
+ * 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
+ prune-vectors of other compatible items (in different tables).
+
+Remove item 'R'
+---------------
+ * A->*A: 'R' was removed from a table, this might impact the prune-vectors of
+ other compatible items (in different tables).
+
+Add table 'T'
+-------------
+ By adding table 'T' to the prune object, prune vector item should be added to the
+ prune-vector of all the items in the prune object.
+
+Remove table 'T'
+----------------
+ By removing table 'T' from the prune object, prune vector item should be removed
+ from the prune-vector of all the items in the prune object.
@@ -11204,6 +11204,14 @@ F: include/linux/sysctl.h
F: kernel/sysctl.c
F: tools/testing/selftests/sysctl/
+PRUNE
+M: Tal Bar <talb@mellanox.com>
+L: netdev@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@infradead.org>
L: netdev@vger.kernel.org
new file mode 100644
@@ -0,0 +1,87 @@
+// SPDX-License-Identifier: GPL-2.0 OR BSD-3
+/*
+ * 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@mellanox.com>
+ */
+
+#ifndef _PRUNE_H
+#define _PRUNE_H
+
+struct prune_item_notification;
+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 {
+ struct prune_table *table;
+ bool is_pruned; /* True if the item is pruning this table */
+ struct list_head list;
+ void *priv; /* Equal to priv field in struct prune_table_attr */
+};
+
+struct prune_item_notify {
+ struct prune_table *table; /* The table which the item belongs to */
+ struct prune_item item;
+ /* List of prune vector item */
+ const struct list_head *table_prune_list;
+ struct list_head list; /* Node of prune_item_notify */
+};
+
+/**
+ * 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_item_notification *notification);
+ 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_create(unsigned int mask_len, const struct prune_ops *ops,
+ void *priv);
+void prune_destroy(struct prune *prune);
+struct prune_table *prune_table_create(struct prune *prune,
+ struct prune_table_attr *table_attr);
+int prune_table_destroy(struct prune *prune, struct prune_table *table);
+int prune_item_add(struct prune *prune, struct prune_table *table,
+ struct prune_item *item,
+ struct prune_item_notify *item_notify,
+ bool *notify);
+int prune_item_remove(struct prune *prune, struct prune_table *table,
+ struct prune_item *item);
+struct prune_vector_item
+*prune_vector_item_get_next(struct prune_item_notify *item_notify,
+ struct prune_vector_item *vector_item_prev);
+struct prune_item_notify
+*prune_item_notify_get_next(struct prune_item_notification *notification,
+ struct prune_item_notify *item_notify_prev);
+
+static inline size_t prune_mask_size(unsigned int nbits)
+{
+ return BITS_TO_LONGS(nbits) * sizeof(unsigned long);
+}
+#endif
@@ -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"
@@ -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
@@ -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
new file mode 100644
@@ -0,0 +1,1433 @@
+// SPDX-License-Identifier: GPL-2.0 OR BSD-3
+/*
+ * 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@mellanox.com>
+ */
+
+#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_item_notification {
+ /* list of prune_item_notify */
+ struct list_head item_notify_list;
+};
+
+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 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 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 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_pruned = 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_vector_item_update(const struct list_head *table_prune_list,
+ struct prune_table *corresponding_table,
+ bool is_prune)
+{
+ struct prune_vector_item *vector_item;
+
+ 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_pruned != is_prune) {
+ vector_item->is_pruned = 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)
+ /* Should not continue pruning in case neighbor priority is
+ * higher then the new item
+ */
+ not_prune = neigh_item->item->priority > entry->ht_key.item->priority;
+ else
+ /* Should not continue pruning in case my priority is lower
+ * then the new item
+ */
+ 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;
+ 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_vector_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;
+}
+
+static void
+prune_item_notify_list_fini(struct prune_item_notification *notify_list)
+{
+ struct prune_item_notify *item_notify;
+ struct list_head *pos, *tmp;
+
+ list_for_each_safe(pos, tmp, ¬ify_list->item_notify_list) {
+ item_notify = list_entry(pos, typeof(*item_notify), list);
+ list_del(&item_notify->list);
+ kfree(item_notify);
+ }
+}
+
+static int
+prune_item_notify_list_add(struct prune_table *table, /* intersec item table owner */
+ struct prune_intersec_table_item *intersec_item,
+ struct prune_item_notification *notify_list)
+{
+ struct prune_item_notify *item_notify;
+
+ item_notify = kzalloc(sizeof(*item_notify), GFP_KERNEL);
+ if (!item_notify) {
+ if (!list_empty(¬ify_list->item_notify_list))
+ prune_item_notify_list_fini(notify_list);
+ }
+ item_notify->table = table;
+ prune_item_entry_to_item_notify(item_notify, intersec_item);
+ list_add_tail(&item_notify->list, ¬ify_list->item_notify_list);
+
+ return 0;
+}
+
+static bool
+prune_item_add_prune_vector_calc(struct prune_table *table,
+ struct prune_table *curr_table, /* intersec item table owner */
+ 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_item_notification *notify_list)
+{
+ struct prune_neighbor_table_items *neigh_item;
+ struct prune_intersec_table_item_entry *intersec_entry;
+ struct prune_intersec_table_item *intersec_item;
+ 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 (!intersec_entry)
+ return false;
+
+ if (neigh) {
+ /* Iterate on neighbor_table_items. In case there is a entry
+ * with higher priority we should not prune the neighbor table.
+ */
+ 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_notify_list_add(curr_table,
+ intersec_item,
+ notify_list);
+ }
+ }
+ }
+ 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_del_prune_vector_calc(struct prune_table *table,
+ struct prune_table *curr_table, /* intersec item table owner */
+ struct prune_item *deleted_item,
+ struct prune_intersec_table *intersec_table,
+ struct prune_intersec_table_item_key *ht_key,
+ struct prune_item_notification *notify_list)
+{
+ struct prune_intersec_table_item_entry *intersec_entry;
+ struct prune_intersec_table_item *intersec_item;
+ 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_vector_item_update(prune_list, table,
+ true);
+ }
+ if (notify) {
+ prune_item_notify_list_add(curr_table,
+ intersec_item,
+ notify_list);
+ }
+ }
+}
+
+static int
+prune_item_add_prune_vector_set(struct prune_table *table,
+ struct prune_item *item,
+ struct prune_table_item_entry *entry,
+ struct prune_item_notify *item_notify,
+ bool *notify)
+{
+ struct prune_intersec_table *intersec_table;
+ struct prune_intersec_table_item_key ht_key;
+ 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,
+ NULL,
+ intersec_table,
+ &ht_key, entry,
+ true,
+ NULL);
+ }
+ if (*notify) {
+ item_notify->table = table;
+ item_notify->item = *item;
+ item_notify->table_prune_list = &entry->table_prune_vector;
+ }
+ kfree(ht_key.mask);
+ 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_item_notification *notify_list)
+{
+ 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,
+ curr_table,
+ intersec_table,
+ ht_key,
+ entry,
+ false,
+ notify_list);
+ else
+ prune_item_del_prune_vector_calc(table,
+ curr_table,
+ item,
+ intersec_table,
+ ht_key,
+ notify_list);
+ }
+ }
+}
+
+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;
+ struct prune_item_notification notification_list;
+
+ ht_key.mask = kcalloc(1, prune_mask_size(item->mask_len), GFP_ATOMIC);
+ if (!ht_key.mask)
+ return -ENOMEM;
+
+ INIT_LIST_HEAD(¬ification_list.item_notify_list);
+
+ 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,
+ ¬ification_list);
+ }
+ if (!list_empty(¬ification_list.item_notify_list)) {
+ prune->ops->prune_item_notify(¬ification_list);
+ prune_item_notify_list_fini(¬ification_list);
+ }
+
+ kfree(ht_key.mask);
+ 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_item_notify *item_notify,
+ bool *notify)
+{
+ 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, item_notify,
+ notify);
+ 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;
+ int err;
+
+ 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);
+ err = 0;
+ goto end;
+ }
+ }
+ goto err_flow;
+
+err_flow:
+ err = -EPERM;
+ WARN_ON(1); /* Didn't found the wanted intersection table */
+end:
+ kfree(curr_mask);
+ return err;
+}
+
+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_pruned = 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_create - Creates 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: It's the user responsibility to care for synchronization.
+ */
+struct prune *prune_create(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_create);
+
+/**
+ * prune_destroy - Destroys the prune object
+ * @prune: Prune object
+ *
+ * Note: It's the user responsibility to care for synchronization.
+ */
+void prune_destroy(struct prune *prune)
+{
+ WARN_ON(prune->table_cnt > 0 || !list_empty(&prune->table_list));
+
+ kfree(prune);
+}
+EXPORT_SYMBOL(prune_destroy);
+
+/**
+ * prune_table_create - Creates new table with specific mask and adds it to the
+ * prune object
+ * @prune: Prune object
+ * @table_attr: Attributes for this table
+ *
+ * Returns a pointer to newly created prune table instance in case of success,
+ * otherwise it returns negative number to indicate an error.
+ *
+ * Note: It's the user responsibility to care for synchronization.
+ * This function may sleep so you must not call it from interrupt
+ * context or with spin locks held.
+ */
+struct prune_table *prune_table_create(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;
+
+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_create);
+
+/**
+ * prune_table_destroy - Removes a table from the prune object and destroys it.
+ * @prune: Prune object
+ * @table: Table to be removed.
+ *
+ * Returns 0 in case of success, negative number to indicate an error.
+ *
+ * Note: It's the user responsibility to care for synchronization.
+ * This function may sleep so you must not call it from interrupt
+ * context or with spin locks held.
+ */
+int prune_table_destroy(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;
+ }
+ }
+ /* Remove all intersection tables from this table */
+ 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_destroy);
+
+/**
+ * prune_item_add - Adds an item to a table.
+ * @prune: Prune object
+ * @table: Add the item to this table.
+ * @item: The item to add.
+ * @item_notify: In case of success returns the item prune vector
+ * valid only if notify == true
+ * @notify: True if there is a change in the prune vector
+ * i,e not all tables are pruned (default)
+ *
+ * Returns 0 in case of success, negative number to indicate an error.
+ *
+ * Note: It's the user responsibility to care for synchronization.
+ */
+int prune_item_add(struct prune *prune, struct prune_table *table,
+ struct prune_item *item,
+ struct prune_item_notify *item_notify,
+ bool *notify)
+{
+ const struct prune_table_item_entry *entry;
+ struct prune_table *curr_table;
+ int err;
+
+ if (prune->mask_len != item->mask_len)
+ return -EPERM;
+
+ *notify = false;
+ entry = prune_table_entry_create(prune, table, item, item_notify,
+ notify);
+ 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);
+
+ *notify = false;
+ return err;
+ }
+ }
+ /* Update prune vector of the corresponding items of the neighbor
+ * tables
+ */
+ 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);
+ *notify = false;
+ return err;
+ }
+ return 0;
+}
+EXPORT_SYMBOL(prune_item_add);
+
+/**
+ * prune_item_remove - removes an item from a table
+ * @prune: prune object
+ * @table: Remove the item from this table.
+ * @item: the item to remove.
+ *
+ * Returns 0 in case of success, negative number to indicate an error.
+ *
+ * Note: It's the user responsibility to care for synchronization.
+ */
+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);
+
+/**
+ * prune_vector_item_get_next - gets the next vector item
+ * @item_notify: item_notify object
+ * @vector_item_prev: NULL for the first item otherwise the next one.
+ *
+ * Returns a pointer to a vector item in case of success,
+ * NULL if there is no more items
+ *
+ * Note: It's the user responsibility to care for synchronization.
+ */
+struct prune_vector_item
+*prune_vector_item_get_next(struct prune_item_notify *item_notify,
+ struct prune_vector_item *vector_item_prev)
+{
+ struct prune_vector_item *vector_item;
+
+ if (!vector_item_prev) {
+ return list_first_entry(item_notify->table_prune_list,
+ typeof(*vector_item), list);
+ } else {
+ vector_item = list_next_entry(vector_item_prev, list);
+ if (&vector_item->list == item_notify->table_prune_list)
+ return NULL;
+ else
+ return vector_item;
+ }
+ WARN_ON(1);
+ return NULL;
+}
+EXPORT_SYMBOL(prune_vector_item_get_next);
+
+/**
+ * prune_item_notify_get_next - gets the next item notify
+ * @notification: notification object
+ * @item_notify_prev: NULL for the first item otherwise the next one.
+ *
+ * Returns a pointer to an item notify in case of success,
+ * NULL if there is no more items
+ *
+ * Note: It's the user responsibility to care for synchronization.
+ */
+struct prune_item_notify
+*prune_item_notify_get_next(struct prune_item_notification *notification,
+ struct prune_item_notify *item_notify_prev)
+{
+ struct prune_item_notify *item_notify;
+
+ if (!item_notify_prev) {
+ return list_first_entry(¬ification->item_notify_list,
+ typeof(*item_notify), list);
+ } else {
+ item_notify = list_next_entry(item_notify_prev, list);
+ if (&item_notify->list == ¬ification->item_notify_list)
+ return NULL;
+ else
+ return item_notify;
+ }
+ WARN_ON(1);
+ return NULL;
+}
+EXPORT_SYMBOL(prune_item_notify_get_next);
+
+MODULE_LICENSE("Dual BSD/GPL");
+MODULE_AUTHOR("Tal Bar<talb@mellanox.com>");
+MODULE_DESCRIPTION("Prune lookup table manager");
new file mode 100644
@@ -0,0 +1,1095 @@
+// SPDX-License-Identifier: GPL-2.0 OR BSD-3
+/*
+ * lib/test_prune.c - Test module for prune
+ * Copyright (c) 2018 Mellanox Technologies. All rights reserved.
+ * Copyright (c) 2018 Tal Bar <talb@mellanox.com>
+ */
+
+#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 void test_prune_notification_print(struct prune_item_notify *item_notify,
+ bool print)
+{
+ struct prune_vector_item *vector_item = NULL;
+ int i;
+
+ if (print) {
+ i = 0;
+ pr_info("item mask: %lu\n", *item_notify->item.mask);
+ pr_info("item prio: %lu\n", item_notify->item.priority);
+ pr_info("item from table *: %p\n", item_notify->table);
+
+ while ((vector_item =
+ prune_vector_item_get_next(item_notify, vector_item))) {
+ 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_pruned ? "Yes" : "No",
+ vector_item->table);
+ i++;
+ }
+ }
+}
+
+static bool test_prune_check_case(struct prune_item_notify *item_notify,
+ unsigned int prio,
+ bool *prune_val_arr,
+ int arr_len,
+ int test_case)
+{
+ struct prune_vector_item *vector_item = NULL;
+ bool case_passed;
+ int table_id;
+
+ if (item_notify->item.priority != prio) {
+ WARN(1, "test case [%d] didn't pass. Incorrect priority [%lu]",
+ test_case,
+ item_notify->item.priority);
+ return false;
+ }
+ table_id = 0;
+
+ while ((vector_item =
+ prune_vector_item_get_next(item_notify, vector_item))) {
+ if (table_id == arr_len)
+ return false;
+
+ switch (table_id) {
+ case 0:
+ case_passed =
+ (uintptr_t)vector_item->priv == table_id &&
+ vector_item->is_pruned == prune_val_arr[0];
+ break;
+ case 1:
+ case_passed =
+ (uintptr_t)vector_item->priv == table_id &&
+ vector_item->is_pruned == prune_val_arr[1];
+ break;
+ case 2:
+ case_passed =
+ (uintptr_t)vector_item->priv == table_id &&
+ vector_item->is_pruned == prune_val_arr[2];
+ break;
+ case 3:
+ case_passed =
+ (uintptr_t)vector_item->priv == table_id &&
+ vector_item->is_pruned == prune_val_arr[3];
+ break;
+ case 4:
+ case_passed =
+ (uintptr_t)vector_item->priv == table_id &&
+ vector_item->is_pruned == prune_val_arr[4];
+ break;
+ case 5:
+ case_passed =
+ (uintptr_t)vector_item->priv == table_id &&
+ vector_item->is_pruned == 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 bool
+test_prune_notify_return_check(bool notify,
+ bool expected_notfiy,
+ struct prune_item_notify *item_notify,
+ unsigned int prio,
+ bool *prune_val_arr,
+ int arr_len)
+{
+ if (expected_notfiy) {
+ if (notify) {
+ test_prune_notification_print(item_notify, false);
+ return test_prune_check_case(item_notify, prio,
+ prune_val_arr, arr_len, 0);
+ } else {
+ pr_err("Should have got notification while adding an item\n");
+ return false;
+ }
+ } else {
+ if (notify) {
+ test_prune_notification_print(item_notify, false);
+ pr_err("Prune vector should be default i.e notify is false\n");
+ return false;
+ } else {
+ return true;
+ }
+ }
+ return false;
+}
+
+static void
+test_prune_subsequent_notify(struct prune_item_notification *notification)
+{
+ bool prune_value_case0[2] = {true, false};
+ bool prune_value_case1[3] = {true, true, true};
+ struct prune_item_notify *item_notify = NULL;
+ static int test_case;
+
+ while ((item_notify =
+ prune_item_notify_get_next(notification, item_notify))) {
+ test_prune_notification_print(item_notify, false);
+
+ switch (test_case) {
+ case 0:
+ test_prune_check_case(item_notify, 1, prune_value_case0,
+ ARRAY_SIZE(prune_value_case0),
+ test_case);
+ break;
+ case 1:
+ test_prune_check_case(item_notify, 2, prune_value_case1,
+ ARRAY_SIZE(prune_value_case1),
+ test_case);
+ break;
+ default:
+ WARN(1, "unexpected test case %d", test_case);
+ break;
+ }
+ test_case++;
+ }
+}
+
+static void
+test_prune_flows_1_notify(struct prune_item_notification *notification)
+{
+ bool prune_value_arr_case0[2] = {false, true};
+ bool prune_value_arr_case1[2] = {true, true};
+ bool prune_value_arr_case2[2] = {true, true};
+ struct prune_item_notify *item_notify = NULL;
+ static int test_case;
+
+ while ((item_notify =
+ prune_item_notify_get_next(notification, item_notify))) {
+ test_prune_notification_print(item_notify, false);
+
+ switch (test_case) {
+ case 0:
+ test_prune_check_case(item_notify, 5,
+ prune_value_arr_case0,
+ ARRAY_SIZE(prune_value_arr_case0),
+ test_case);
+ break;
+ case 1:
+ test_prune_check_case(item_notify, 7,
+ prune_value_arr_case1,
+ ARRAY_SIZE(prune_value_arr_case1),
+ test_case);
+ break;
+ case 2:
+ test_prune_check_case(item_notify, 5,
+ prune_value_arr_case2,
+ ARRAY_SIZE(prune_value_arr_case2),
+ test_case);
+ break;
+ default:
+ WARN(1, "unexpected test case %d", test_case);
+ break;
+ }
+ test_case++;
+ }
+}
+
+static void
+test_prune_flows_2_notify(struct prune_item_notification *notification)
+{
+ struct prune_item_notify *item_notify = NULL;
+
+ while ((item_notify =
+ prune_item_notify_get_next(notification, item_notify))) {
+ pr_err("The prune vector should be changed\n");
+ test_prune_notification_print(item_notify, false);
+ }
+}
+
+static void
+test_prune_basic_notify(struct prune_item_notification *notification)
+{
+ bool prune_value_arr_case0[3] = {true, false, true};
+ bool prune_value_arr_case1[3] = {true, false, false};
+ bool prune_value_arr_case2[3] = {true, true, false};
+ bool prune_value_arr_case3[3] = {true, false, true};
+ bool prune_value_arr_case4[3] = {true, true, true};
+ struct prune_item_notify *item_notify = NULL;
+ static int test_case;
+
+ while ((item_notify =
+ prune_item_notify_get_next(notification, item_notify))) {
+ test_prune_notification_print(item_notify, false);
+
+ switch (test_case) {
+ case 0:
+ test_prune_check_case(item_notify, 1,
+ prune_value_arr_case0,
+ ARRAY_SIZE(prune_value_arr_case0),
+ test_case);
+ break;
+ case 1:
+ test_prune_check_case(item_notify, 1,
+ prune_value_arr_case1,
+ ARRAY_SIZE(prune_value_arr_case1),
+ test_case);
+ break;
+ case 2:
+ test_prune_check_case(item_notify, 2,
+ prune_value_arr_case2,
+ ARRAY_SIZE(prune_value_arr_case2),
+ test_case);
+ break;
+ case 3:
+ test_prune_check_case(item_notify, 1,
+ prune_value_arr_case3,
+ ARRAY_SIZE(prune_value_arr_case3),
+ test_case);
+ break;
+ case 4:
+ test_prune_check_case(item_notify, 2,
+ prune_value_arr_case4,
+ ARRAY_SIZE(prune_value_arr_case4),
+ test_case);
+ break;
+ default:
+ WARN(1, "unexpected test case %d", test_case);
+ break;
+ }
+ test_case++;
+ }
+}
+
+static const struct prune_ops test_prune_add_new_table_subsequent_ops = {
+ .prune_item_notify = test_prune_subsequent_notify
+};
+
+static const struct prune_ops test_prune_flows_add_delete_items_1_ops = {
+ .prune_item_notify = test_prune_flows_1_notify
+};
+
+static const struct prune_ops test_prune_flows_add_delete_items_2_ops = {
+ .prune_item_notify = test_prune_flows_2_notify
+};
+
+static const struct prune_ops test_prune_basic_ops = {
+ .prune_item_notify = test_prune_basic_notify
+};
+
+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;
+ struct prune_table_attr table_attr[tbl_cnt];
+ struct prune_table *table_arr[tbl_cnt];
+ struct prune_item pi_arr[item_cnt];
+ struct prune_item_notify item_notify;
+ unsigned int nbits = 40;
+ struct prune *prune;
+ bool notify;
+ int err;
+
+ prune = prune_create(nbits, &test_prune_basic_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_create(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_create(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_create(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], &item_notify,
+ ¬ify);
+ if (err)
+ return err;
+
+ if (!test_prune_notify_return_check(notify, false, &item_notify, 0,
+ NULL, 0))
+ return -EBADE;
+
+ 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], &item_notify,
+ ¬ify);
+ if (err)
+ return err;
+
+ if (!test_prune_notify_return_check(notify, false, &item_notify, 0,
+ NULL, 0)) {
+ return -EBADE;
+ }
+
+ 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], &item_notify,
+ ¬ify);
+ if (err)
+ return err;
+
+ if (!test_prune_notify_return_check(notify, false, &item_notify, 0,
+ NULL, 0))
+ return -EBADE;
+
+ 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[0]);
+ if (err)
+ return err;
+
+ err = prune_item_remove(prune, table_arr[1], &pi_arr[1]);
+ if (err)
+ return err;
+
+ prune_table_destroy(prune, table_arr[0]);
+
+ prune_table_destroy(prune, table_arr[1]);
+
+ prune_table_destroy(prune, table_arr[2]);
+
+ prune_destroy(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;
+ struct prune_table_attr table_attr[tbl_cnt];
+ struct prune_table *table_arr[tbl_cnt];
+ struct prune_item pi_arr[item_cnt];
+ struct prune_item_notify item_notify;
+ unsigned int nbits = 40;
+ bool prune_val_arr_2[2] = {true, false};
+ struct prune *prune;
+ bool notify;
+ int err;
+
+ prune = prune_create(nbits, &test_prune_flows_add_delete_items_1_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;
+
+ /* 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_create(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_create(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], &item_notify,
+ ¬ify);
+ if (err)
+ return err;
+
+ if (!test_prune_notify_return_check(notify, false, &item_notify, 0,
+ NULL, 0))
+ return -EBADE;
+
+ /* 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], &item_notify,
+ ¬ify);
+ if (err)
+ return err;
+
+ if (!test_prune_notify_return_check(notify, false, &item_notify, 0,
+ NULL, 0))
+ return -EBADE;
+
+ /* 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], &item_notify,
+ ¬ify);
+ if (err)
+ return err;
+
+ if (!test_prune_notify_return_check(notify, true, &item_notify,
+ pi_arr[2].priority, prune_val_arr_2,
+ 2))
+ return -EBADE;
+
+ /* 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):
+ * table 0 don't prune (changed)
+ * table 1 prune (changed)
+ * --> Should get notification
+ * item2 in table 0 (1.2.3.x.x prio 7):
+ * 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
+ * item1 table 1 (x.2.3.5.x prio 5):
+ * table 0 don't prune
+ * table 1 prune
+ * item2 table 0 (1.2.3.x.x prio 7):
+ * 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
+ * item0: item is deleted
+ * item1 table 1 (x.2.3.5.x prio 5):
+ * table 0 prune (changed)
+ * table 1 prune
+ * item2 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_destroy(prune, table_arr[0]);
+ if (err)
+ return err;
+
+ err = prune_table_destroy(prune, table_arr[1]);
+ if (err)
+ return err;
+
+ prune_destroy(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;
+ bool prune_val_arr_3[3] = {false, true, true};
+ bool prune_val_arr_4[3] = {true, true, false};
+ struct prune_table_attr table_attr[tbl_cnt];
+ struct prune_table *table_arr[tbl_cnt];
+ struct prune_item pi_arr[item_cnt];
+ struct prune_item_notify item_notify;
+ unsigned int nbits = 40;
+ struct prune *prune;
+ bool notify;
+ int err;
+
+ prune = prune_create(nbits, &test_prune_flows_add_delete_items_2_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_create(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], &item_notify,
+ ¬ify);
+ if (err)
+ return err;
+
+ if (!test_prune_notify_return_check(notify, false, &item_notify, 0,
+ NULL, 0))
+ return -EBADE;
+
+ table_arr[1] = prune_table_create(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], &item_notify,
+ ¬ify);
+ if (err)
+ return err;
+
+ if (!test_prune_notify_return_check(notify, false, &item_notify, 0,
+ NULL, 0))
+ return -EBADE;
+
+ err = prune_item_add(prune, table_arr[0], &pi_arr[2], &item_notify,
+ ¬ify);
+ if (err)
+ return err;
+
+ if (!test_prune_notify_return_check(notify, false, &item_notify, 0,
+ NULL, 0))
+ return -EBADE;
+
+ table_arr[2] = prune_table_create(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], &item_notify,
+ ¬ify);
+ if (err)
+ return err;
+
+ if (!test_prune_notify_return_check(notify, true, &item_notify,
+ pi_arr[3].priority, prune_val_arr_3,
+ 3))
+ return -EBADE;
+
+ err = prune_item_add(prune, table_arr[0], &pi_arr[4], &item_notify,
+ ¬ify);
+ if (err)
+ return err;
+
+ if (!test_prune_notify_return_check(notify, true, &item_notify,
+ pi_arr[4].priority, prune_val_arr_4,
+ 3))
+ return -EBADE;
+
+ err = prune_item_add(prune, table_arr[1], &pi_arr[5], &item_notify,
+ ¬ify);
+ if (err)
+ return err;
+
+ if (!test_prune_notify_return_check(notify, false, &item_notify, 0,
+ NULL, 0))
+ return -EBADE;
+
+ /* 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_destroy(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_destroy(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_destroy(prune, table_arr[1]);
+ if (err)
+ return err;
+
+ prune_destroy(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;
+ struct prune_table_attr table_attr[tbl_cnt];
+ struct prune_table *table_arr[tbl_cnt];
+ struct prune_item pi_arr[item_cnt];
+ bool prune_val_arr_5[2] = {false, true};
+ struct prune_item_notify item_notify;
+ unsigned int nbits = 40;
+ struct prune *prune;
+ bool notify;
+ int err;
+
+ prune = prune_create(nbits, &test_prune_add_new_table_subsequent_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_create(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_create(prune, &table_attr[1]);
+ if (IS_ERR(table_arr[1]))
+ return PTR_ERR(table_arr[1]);
+
+ /* Create 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], &item_notify,
+ ¬ify);
+ if (err)
+ return err;
+
+ if (!test_prune_notify_return_check(notify, false, &item_notify, 0,
+ NULL, 0))
+ return -EBADE;
+
+ err = prune_item_add(prune, table_arr[1], &pi_arr[1], &item_notify,
+ ¬ify);
+ if (err)
+ return err;
+
+ if (!test_prune_notify_return_check(notify, false, &item_notify, 0,
+ NULL, 0))
+ return -EBADE;
+
+ err = prune_item_add(prune, table_arr[0], &pi_arr[3], &item_notify,
+ ¬ify);
+ if (err)
+ return err;
+
+ if (!test_prune_notify_return_check(notify, false, &item_notify, 0,
+ NULL, 0))
+ return -EBADE;
+
+ err = prune_item_add(prune, table_arr[1], &pi_arr[5], &item_notify,
+ ¬ify);
+ if (err)
+ return err;
+
+ if (!test_prune_notify_return_check(notify, true, &item_notify,
+ pi_arr[5].priority, prune_val_arr_5,
+ 2))
+ return -EBADE;
+
+ err = prune_item_add(prune, table_arr[1], &pi_arr[6], &item_notify,
+ ¬ify);
+ if (err)
+ return err;
+
+ if (!test_prune_notify_return_check(notify, false, &item_notify, 0,
+ NULL, 0))
+ return -EBADE;
+
+ /* 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_create(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], &item_notify,
+ ¬ify);
+ if (err)
+ return err;
+
+ if (!test_prune_notify_return_check(notify, false, &item_notify, 0,
+ NULL, 0))
+ return -EBADE;
+
+ err = prune_item_add(prune, table_arr[2], &pi_arr[4], &item_notify,
+ ¬ify);
+ if (err)
+ return err;
+
+ if (!test_prune_notify_return_check(notify, false, &item_notify, 0,
+ NULL, 0))
+ return -EBADE;
+
+ 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_destroy(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_destroy(prune, table_arr[0]);
+ if (err)
+ return err;
+
+ err = prune_table_destroy(prune, table_arr[1]);
+ if (err)
+ return err;
+
+ prune_destroy(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@mellanox.com>");
+MODULE_DESCRIPTION("Test module for prune");
The prune library aim: reduce number of lookups (by prune) between tables within same prune object. Pruning save time complexity by doing lookups only 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@mellanox.com> --- v5 -> v6: * Add notification aggregation capability * Adjust prune_test to handle notification aggregation * Add getters for prune_item_nofity and prune_vector_item * Fix many comments from v5 review v1 -> v5: * Fix style issues --- Documentation/prune.txt | 56 ++ MAINTAINERS | 8 + include/linux/prune.h | 87 +++ lib/Kconfig | 6 + lib/Kconfig.debug | 10 + lib/Makefile | 3 + lib/prune.c | 1433 +++++++++++++++++++++++++++++++++++++++++++++++ lib/test_prune.c | 1095 ++++++++++++++++++++++++++++++++++++ 8 files changed, 2698 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