@@ -326,6 +326,8 @@ preempt-locking.txt
- info on locking under a preemptive kernel.
process/
- how to work with the mainline kernel development process.
+prune/
+ - info on what prune aim, why and when to use it.
pps/
- directory with information on the pulse-per-second support
pti/
new file mode 100644
@@ -0,0 +1,286 @@
+=====
+Prune
+=====
+
+Prune is a library which determines which table needs to be searched.
+The user can create tables with specific masks. The tables contain items with
+a bit field key and priority. Since similar items 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 (lookup)
+in other tables.
+
+Database
+========
+Each prune object has a list of tables with mask.
+The mask is a property of the table which determines which item can be add to it.
+Each table consists of:
+ * List of items, each item having its own prune vector.
+ * List of the corresponding intersection tables (with other tables) with mask.
+ The intersection mask is equal to the mask of table x which intersectes with the mask
+ of table z.
+Each intersection table consists of:
+ * Hash table for intersecting entries
+ * Each entry contain two lists:
+ 1. Items of the table owner (my items).
+ 2. Items of other tables (neighbor items) in the prune object.
+
+Prune Calculation Algorithm
+===========================
+As previously explained, each item has a prune-vector
+which consists of a table identifier and its prune decision on this table
+(i.e. should we perform lookup on this table).
+
+A single operation of adding or removing an item from a table may affect other
+items in other tables (i.e. compatible-item).
+
+Inserting Item 'R' to Table 'T'
+--------------------------------
+1. Calculate item 'R' prune vector.
+ Iterate over all the intersection tables of table 'T' and for each table:
+ a. Intersect 'R' key with intersection table mask and use it as a key into the
+ intersection table's hash table to retrieve entry 'I'.
+ b. In 'I' iterate on neighbor items, for each item 'K' with lower priority number (higher
+ priority) than 'R', set the prune decision not to prune the table which 'K' belongs to
+ within the prune vector of 'R'.
+ c. Add entry for 'R' under my items.
+ d. Return the updated prune vector of 'R'.
+2. Calculate the prune-vector of all compatible items in the other tables.
+ Iterate over all the tables in the prune object (besides 'T'); for each table 'Y' find the
+ intersection table which intersects between 'T' and 'Y':
+ a. Intersect 'R' key with intersection table mask and use it as key into the intersection table's
+ hash table to retrieve entry 'I'.
+ b. Add entry for 'R' under neighbor items of 'I'.
+ c. Iterate on my items for each item 'K' with higher priority number (lower priority) than
+ 'R', set the prune decision not to prune the table which 'R' belongs to.
+ d. Send notification with these specific changes.
+
+Deleting Item 'R' from Table 'T'
+---------------------------------
+1. Remove item 'R' from table 'T' and its references from all intersection tables.
+ Iterate over all intersection tables of 'T' and for each table 'Y':
+ a. Intersect 'R' key with intersection table mask and use it as a key into the
+ intersection table's hash table to retrieve entry 'I'.
+ b. Remove 'R' from my items. If my items and neighbor items are empty
+ remove entry 'I' from the intersection table.
+2. Calculate the prune-vector of all compatible items in the other tables.
+ Iterate over all tables in the prune object (besides 'T'); for each table 'Y' find the
+ intersection table which intersects between 'Y' and 'T':
+ a. Intersect 'R' key with intersection table mask and use it as a key into the intersection table's
+ hash table to retrieve entry 'I'.
+ b. In 'I' remove item 'R' from neighbor items.
+ c. Iterate on my items in entry 'I', for each item 'K' check if there isn't any
+ item 'J' under neighbor items with better priority. Set 'K' item to prune item 'R' table -> 'T'.
+ d. Send notification with these specific changes.
+
+Functional Example
+-------------------
+Legend:
+~~~~~~~
+- y^z: Donates to intersection between table 'y' and 'z' where 'y' is the main table.
+- [{<table_id_a>-<prune_bit}, {<table_id_b>-<prune_bit}]:
+ If prune_bit = 1 then prune table_id (do not perform lookup on this table).
+- Flow 1: Calculate item 'R' prune vector against matched neighbor items.
+- Flow 2: Calculate the prune-vectors of other compatible items.
+
+Step 0:
+~~~~~~~
+Assume a prune object with 2 tables:
+table y with mask: U.U.U.X.X
+table z with mask: X.U.U.U.X
+
+Before any operation is performed the library database is represented as follows:
++---------------------------------+ +---------------------------------+
+| table y: U.U.U.X.X | |intersection table y^z X.U.U.X.X |
++---------------------------------+ +---------------------------------+
+|item key| priority | prune-vector| |mask | my items |neighbor items |
++--------+----------+-------------+ +-----+----------+----------------+
+| | | | | | | |
++--------+----------+-------------+ +-----+----------+----------------+
+| | | | | | | |
++--------+----------+-------------+ +-----+----------+----------------+
+| | | | | | | |
++--------+----------+-------------+ +-----+----------+----------------+
+
++---------------------------------+ +---------------------------------+
+| table z: X.U.U.U.X | |intersection table z^y X.U.U.X.X |
++---------------------------------+ +---------------------------------+
+|item key| priority | prune-vector| |mask | my items |neighbor items |
++--------+----------+-------------+ +-----+----------+----------------+
+| | | | | | | |
++--------+----------+-------------+ +-----+----------+----------------+
+| | | | | | | |
++--------+----------+-------------+ +-----+----------+----------------+
+| | | | | | | |
++--------+----------+-------------+ +-----+----------+----------------+
+
+Step 1:
+~~~~~~~
+User inserts item 'R-1' with key X.2.3.4.X with priority 10. This item should be
+inserted to table 'z' which has a mask of X.U.U.U.X.
+
+Item 'R-1' goes into table 'z' and the following two calculations are preformed:
+Flow 1: There are no entries in neighbor items; its prune vector is [z-1,y-1].
+Flow 2: It accesses y^z table with 'R-1' and adds new entry X.2.3.X.X.
+
+After the insertion, the database is represented as follows:
++----------------------------------+ +-------------------------------------+
+| table y: U.U.U.X.X | |intersection table y^z X.U.U.X.X |
++----------------------------------+ +-------------------------------------+
+|item key | priority | prune-vector| |mask | my items |neighbor items |
++---------+----------+-------------+ +---------+----------+----------------+
+| | | | |X.2.3.X.X| | R-1 |
++---------+----------+-------------+ +---------+----------+----------------+
+| | | | | | | |
++---------+----------+-------------+ +---------+----------+----------------+
+| | | | | | | |
++---------+----------+-------------+ +---------+----------+----------------+
+
++----------------------------------+ +-------------------------------------+
+| table z: X.U.U.U.X | |intersection table z^y X.U.U.X.X |
++----------------------------------+ +-------------------------------------+
+|item key | priority | prune-vector| |mask | my items |neighbor items |
++---------+----------+-------------+ +---------+----------+----------------+
+|x.2.3.4.X| 10 | [z-1,y-1] | |X.2.3.X.X| R-1 | |
++---------+----------+-------------+ +---------+----------+----------------+
+| | | | | | | |
++---------+----------+-------------+ +---------+----------+----------------+
+| | | | | | | |
++---------+----------+-------------+ +---------+----------+----------------+
+
+Step 2:
+~~~~~~~
+User inserts item 'R-2' with key X.2.3.5.X with priority 5. This item should be
+inserted to table z.
+
+Item 'R-2' goes into table 'z' and performs the following two calculations:
+Flow 1: There are no entries in neighbor items; its prune vector is [z-1,y-1].
+Flow 2: It accesses y^z table with 'x' X.2.3.X.X and adds neighbor item to
+X.2.3.X.X entry.
+
+After the insertion, the database represented as follows:
++----------------------------------+ +-------------------------------------+
+| table y: U.U.U.X.X | |intersection table y^z X.U.U.X.X |
++----------------------------------+ +-------------------------------------+
+|item key | priority | prune-vector| |mask | my items |neighbor items |
++---------+----------+-------------+ +---------+----------+----------------+
+| | | | |X.2.3.X.X| | R-1, R-2 |
++---------+----------+-------------+ +---------+----------+----------------+
+| | | | | | | |
++---------+----------+-------------+ +---------+----------+----------------+
+| | | | | | | |
++---------+----------+-------------+ +---------+----------+----------------+
+
++----------------------------------+ +-------------------------------------+
+| table z: X.U.U.U.X | |intersection table z^y X.U.U.X.X |
++----------------------------------+ +-------------------------------------+
+|item key | priority | prune-vector| |mask | my items |neighbor items |
++---------+----------+-------------+ +---------+----------+----------------+
+|x.2.3.4.X| 10 | [z-1,y-1] | |X.2.3.X.X| R-1, R-2 | |
++---------+----------+-------------+ +---------+----------+----------------+
+|x.2.3.5.X| 5 | [z-1,y-1] | | | | |
++---------+----------+-------------+ +---------+----------+----------------+
+| | | | | | | |
++---------+----------+-------------+ +---------+----------+----------------+
+
+Step 3:
+~~~~~~~
+User Insert item 'R-3' with key 1.2.3.X.X with priority 7. This item should be
+insert to table 'y'.
+
+Item 'R-3' will be inserted to table 'y' and preforms the following two calculations:
+Flow 1: There are two entries under neighbor items. Since 'R-2' is a match in
+the intersection table y^z and has lower priority number (higher priority), the 'R-3' prune vector
+is [y-1,z-0].
+Flow 2: It accesses z^y table with key X.2.3.X.X and adds neighbor item to
+X.2.3.X.X entry. Since 'R-3' has lower priority number (higher priority) than 'R-1', the prune vector of
+'R-1' changes to [z-1,y-0].
+
+After the insertion the database represented as follows:
++----------------------------------+ +-------------------------------------+
+| table y: U.U.U.X.X | |intersection table y^z X.U.U.X.X |
++----------------------------------+ +-------------------------------------+
+|item key | priority | prune-vector| |mask | my items |neighbor items |
++---------+----------+-------------+ +---------+----------+----------------+
+|1.2.3.X.X| 7 | [y-1,z-0] | |X.2.3.X.X| R-3 | R-1, R-2 |
++---------+----------+-------------+ +---------+----------+----------------+
+| | | | | | | |
++---------+----------+-------------+ +---------+----------+----------------+
+| | | | | | | |
++---------+----------+-------------+ +---------+----------+----------------+
+
++----------------------------------+ +-------------------------------------+
+| table z: X.U.U.U.X | |intersection table z^y X.U.U.X.X |
++----------------------------------+ +-------------------------------------+
+|item key | priority | prune-vector| |mask | my items |neighbor items |
++---------+----------+-------------+ +---------+----------+----------------+
+|x.2.3.4.X| 10 | [z-1,y-0] | |X.2.3.X.X| R-1, R-2 | R-3 |
++---------+----------+-------------+ +---------+----------+----------------+
+|x.2.3.5.X| 5 | [z-1,y-1] | | | | |
++---------+----------+-------------+ +---------+----------+----------------+
+| | | | | | | |
++---------+----------+-------------+ +---------+----------+----------------+
+
+Step 4:
+~~~~~~~
+User removes item 'R-2' from table 'z'.
+
+Item 'R-2' is leaves table 'z' and preforms the following two calculations:
+Flow 1: Deletes 'R-2' entry from table 'z' and z^y
+Flow 2: Deletes 'R-2' entry from X.2.3.X.X entry in table y^z, and checks
+if there are other items which are affected. Iterate on every my_item entry in y^z
+and checks against all neighbor items, if there is an item with better
+priority. In this example there isn't, therefore item 'R-3' prune-vector
+changes to [y-1,z-1].
+
+After the deletion the database represented as follows:
++----------------------------------+ +-------------------------------------+
+| table y: U.U.U.X.X | |intersection table y^z X.U.U.X.X |
++----------------------------------+ +-------------------------------------+
+|item key | priority | prune-vector| |mask | my items |neighbor items |
++---------+----------+-------------+ +---------+----------+----------------+
+|1.2.3.X.X| 7 | [y-1,z-1] | |X.2.3.X.X| R-3 | R-1 |
++---------+----------+-------------+ +---------+----------+----------------+
+| | | | | | | |
++---------+----------+-------------+ +---------+----------+----------------+
+| | | | | | | |
++---------+----------+-------------+ +---------+----------+----------------+
+
++----------------------------------+ +-------------------------------------+
+| table z: X.U.U.U.X | |intersection table z^y X.U.U.X.X |
++----------------------------------+ +-------------------------------------+
+|item key | priority | prune-vector| |mask | my items |neighbor items |
++---------+----------+-------------+ +---------+----------+----------------+
+|x.2.3.4.X| 10 | [z-1,y-0] | |X.2.3.X.X| R-1 | R-3 |
++---------+----------+-------------+ +---------+----------+----------------+
+| | | | | | | |
++---------+----------+-------------+ +---------+----------+----------------+
+| | | | | | | |
++---------+----------+-------------+ +---------+----------+----------------+
+
+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' is inserted to a table, and we have to calculate the
+ prune-vectors of other compatible items (in different tables).
+
+Removing item 'R'
+~~~~~~~~~~~~~~~~~~
+ * A->*A: 'R' is removed from a table, this might impact the prune-vectors of
+ other compatible items (in different tables).
+
+Adding 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.
@@ -11502,6 +11502,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,76 @@
+/* SPDX-License-Identifier: GPL-2.0 OR BSD-3-Clause */
+/*
+ * include/linux/prune.h - Manager for priority based 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_table;
+struct prune;
+
+/*
+ * This structure holds the configured item settings.
+ * This structure returned in case of change in the item prune_vector.
+ * User can retrieve the prune_vector using this structure.
+ */
+struct prune_item {
+ unsigned long *key; /* Pointer to bitmap */
+ void *priv;
+ struct prune_table *table; /* Table which the item belongs to */
+ struct list_head list;
+ unsigned int priority; /* Lower number means higher priority */
+};
+
+/*
+ * This structure is part of the prune_vector structure, it defines if a table
+ * should be prune or not.
+ */
+struct prune_vector_item {
+ struct prune_table *table; /* The table which should be pruned */
+ struct list_head list; /* Node in table_prune_vector */
+ bool pruned; /* True if the item is pruning this table */
+};
+
+/**
+ * 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_item_notify_list: A list of prune_item structs which their prune
+ * vector have been changed with {table,pruned}
+ * attributes below.
+ * @table: The table which should be pruned
+ * @pruned: True if the item prune the table
+ *
+ * Note: The table and the decision to be pruned or not is equal across all
+ * items in the notification list.
+ */
+struct prune_ops {
+ void (*prune_item_notify)(struct list_head *prune_item_notify_list,
+ struct prune_table *table, bool pruned);
+};
+
+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, unsigned long *mask,
+ unsigned int mask_len, void *priv);
+int prune_table_destroy(struct prune_table *table);
+struct prune_item *prune_item_create(struct prune *prune,
+ struct prune_table *table,
+ unsigned long priority,
+ unsigned long *key,
+ void *priv,
+ bool *non_def_prune_vector);
+int prune_item_destroy(struct prune_item *item);
+void *prune_table_priv(struct prune_table *table);
+struct list_head *prune_item_prune_vector(struct prune_item *item);
+#endif
@@ -308,7 +308,7 @@ config GENERIC_ALLOCATOR
#
config REED_SOLOMON
tristate
-
+
config REED_SOLOMON_ENC8
bool
@@ -592,6 +592,12 @@ config PARMAN
config PRIME_NUMBERS
tristate
+config PRUNE
+ tristate "prune"
+ help
+ This option enables the use of prune manager library for priority
+ based pruning lookups between tables.
+
config STRING_SELFTEST
tristate "Test string functions"
@@ -1837,6 +1837,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
@@ -69,6 +69,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
@@ -250,6 +251,8 @@ obj-$(CONFIG_SBITMAP) += sbitmap.o
obj-$(CONFIG_PARMAN) += parman.o
+obj-$(CONFIG_PRUNE) += prune.o
+
# GCC library routines
obj-$(CONFIG_GENERIC_LIB_ASHLDI3) += ashldi3.o
obj-$(CONFIG_GENERIC_LIB_ASHRDI3) += ashrdi3.o
new file mode 100644
@@ -0,0 +1,1337 @@
+// SPDX-License-Identifier: GPL-2.0 OR BSD-3-Clause
+/*
+ * lib/prune.c - Manager for priority based 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>
+
+/*
+ * This structure holds the item configuration and its prune vector
+ */
+struct prune_table_entry {
+ /* List of struct prune_vector_item */
+ struct list_head table_prune_vector;
+ struct list_head list; /* Node of entry_list (in prune_table) */
+ struct prune_item item;
+};
+
+/*
+ * This structure holds a reference to an entry in the prune table.
+ * This structure used as an element in intersec_table_elem_list or
+ * neigh_table_elem_list.
+ */
+struct prune_intersec_table_list_elem {
+ struct prune_table_entry *entry;
+ struct list_head list;
+};
+
+/*
+ * This structure contain hash-table of prune_intersec_table_entry.
+ * This structure is used to find the intersection of new prune item with the
+ * current one, and check wither the new item should be pruned or not.
+ */
+struct prune_intersec_table {
+ struct rhashtable entry_ht;
+ unsigned long *mask;
+ struct prune_table *neigh_table;
+ struct list_head list; /* Node of intersec_table_list (in prune_table)*/
+};
+
+/*
+ * This structure is a member of prune_intersec_table hash-table and contains
+ * two list of elements.
+ * The intersec_table_elem_list contains entries of my prune table, while the
+ * neigh_table_elem_list contains list of entries in the nighbor table - pointed
+ * by the neigh_table field in prune_intersec_table strcut
+ * This structure is used to find the intersection of new prune item with the
+ * current one, and check wither the new item should be pruned or not.
+ */
+struct prune_intersec_table_entry {
+ struct rhash_head ht_node;
+ unsigned long *ht_key;
+ struct prune_intersec_table *intersec_table;
+ struct list_head intersec_table_elem_list;
+ struct list_head neigh_table_elem_list;
+};
+
+/* This structure contains table entries of prune_table_entry and the
+ * intersection tables of this table and other tables in the prune object.
+ * This structure used to identify the prune vector and which tables need to be
+ * pruned.
+ */
+struct prune_table {
+ struct prune *prune;
+ void *priv;
+ struct list_head entry_list; /* A list of prune_table_entry */
+ /* List of intersection tables of this 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 */
+ unsigned long *mask;
+};
+
+/* This structure identify the prune object */
+struct prune {
+ const struct prune_ops *ops;
+ struct rhashtable_params intersec_tables_ht_params;
+ struct list_head table_list;
+ struct list_head list; /* A node in prune pbject list */
+ void *priv;
+ unsigned int mask_len; /* Bits */
+};
+
+static unsigned int
+prune_intersec_table_entry_key_len(const struct prune_intersec_table_entry
+ *intersec_entry)
+{
+ return intersec_entry->intersec_table->neigh_table->prune->mask_len;
+}
+
+static struct rhashtable_params
+prune_intersec_table_entry_rht_params(struct prune_intersec_table
+ *intersec_table)
+{
+ return intersec_table->neigh_table->prune->intersec_tables_ht_params;
+}
+
+static size_t prune_mask_size(unsigned int nbits)
+{
+ return BITS_TO_LONGS(nbits) * sizeof(unsigned long);
+}
+
+static u32 prune_intersec_ht_hash(const void *data, u32 len, u32 seed)
+{
+ u32 jash_len = prune_mask_size(len);
+ const unsigned long * const *ht_key = data;
+
+ return jhash(*ht_key, jash_len, seed);
+}
+
+static int prune_intersec_ht_cmp(struct rhashtable_compare_arg *arg,
+ const void *obj)
+{
+ const struct prune_intersec_table_entry *intersec_entry = obj;
+ const unsigned long * const *ht_key = arg->key;
+
+ return !(bitmap_equal(*ht_key, intersec_entry->ht_key,
+ prune_intersec_table_entry_key_len(intersec_entry)));
+}
+
+static void prune_table_prune_vector_fini(struct prune_table_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_vector_init(struct prune *prune,
+ struct prune_table_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_vector_fini(entry);
+ return -ENOMEM;
+ }
+ vector_item->pruned = true;
+ vector_item->table = table;
+ list_add_tail(&vector_item->list,
+ &entry->table_prune_vector);
+ }
+ return 0;
+}
+
+static struct prune_table_entry *
+prune_item_entry_create(struct prune *prune, unsigned long *key,
+ unsigned int priority, void *priv)
+{
+ struct prune_table_entry *entry;
+ int err;
+
+ entry = kzalloc(sizeof(*entry), GFP_KERNEL);
+ if (!entry)
+ goto err_entry_alloc;
+
+ entry->item.key = key;
+ entry->item.priority = priority;
+ entry->item.priv = priv;
+
+ err = prune_table_prune_vector_init(prune, entry);
+ if (err)
+ goto err_vector_init;
+
+ return entry;
+
+err_vector_init:
+ kfree(entry);
+err_entry_alloc:
+ return NULL;
+}
+
+static void prune_entry_destroy(struct prune_table_entry *entry)
+{
+ prune_table_prune_vector_fini(entry);
+ list_del(&entry->list);
+ kfree(entry);
+}
+
+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->pruned != is_prune) {
+ vector_item->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_entry *entry,
+ struct prune_intersec_table_list_elem *neigh_item,
+ struct prune_intersec_table_list_elem *intersec_item,
+ bool neigh_items)
+{
+ const struct list_head *prune_list;
+ bool not_prune;
+
+ if (neigh_items) {
+ /* Should not continue pruning in case neighbor priority is
+ * lower (more important) then the new item
+ */
+ not_prune = neigh_item->entry->item.priority < entry->item.priority;
+
+ } else {
+ /* Should not continue pruning in case my priority is higher
+ * (less important) then the new item
+ */
+ not_prune = intersec_item->entry->item.priority > entry->item.priority;
+ }
+ prune_list = neigh_items ? &entry->table_prune_vector : &intersec_item->entry->table_prune_vector;
+ if (not_prune)
+ return prune_vector_item_update(prune_list, neigh_table, false);
+
+ return false;
+}
+
+static void
+prune_item_notify_list_fini(struct list_head *prune_item_notify_list)
+{
+ struct list_head *pos, *tmp;
+ struct prune_item *item;
+
+ list_for_each_safe(pos, tmp, prune_item_notify_list) {
+ item = list_entry(pos, typeof(*item), list);
+ list_del(&item->list);
+ }
+}
+
+void
+prune_item_notify_list_add(struct prune_intersec_table_list_elem *intersec_item,
+ struct list_head *prune_item_notify_list)
+{
+ struct prune_table_entry *entry = intersec_item->entry;
+
+ list_add_tail(&entry->item.list, prune_item_notify_list);
+}
+
+/*
+ * prune_item_add_prune_vector_calc - Calculate the prune vector due to a new
+ * item add flow
+ * @table: The table which the new item belongs to
+ * @intersec_table: The intersection table of the table above
+ * @ht_key: A key to store the current masked key
+ * @entry: The entry which is being added
+ * @neigh: If true search the neigh_table_elem_list
+ * @notify_list: The notification list which will returned due to changes in
+ * other items in the prune object
+ */
+static bool
+prune_item_add_prune_vector_calc(struct prune_table *table,
+ struct prune_intersec_table *intersec_table,
+ unsigned long *ht_key,
+ const struct prune_table_entry *entry,
+ bool neigh,
+ struct list_head *prune_item_notify_list)
+{
+ struct prune_intersec_table_list_elem *intersec_item;
+ struct prune_intersec_table_list_elem *neigh_item;
+ struct prune_intersec_table_entry *intersec_entry;
+ struct rhashtable_params rht_params;
+ bool prune_vector_chng = false;
+
+ bitmap_clear(ht_key, 0, table->prune->mask_len);
+ bitmap_and(ht_key, entry->item.key, intersec_table->mask,
+ table->prune->mask_len);
+
+ rht_params = table->prune->intersec_tables_ht_params;
+ intersec_entry = rhashtable_lookup_fast(&intersec_table->entry_ht,
+ &ht_key, rht_params);
+ if (!intersec_entry)
+ return false;
+
+ if (neigh) {
+ /* Iterate on neigh_table_elem_list. In case there is a entry
+ * with higher priority we should not prune the neighbor table.
+ */
+ list_for_each_entry(neigh_item,
+ &intersec_entry->neigh_table_elem_list,
+ 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_elem_list,
+ list) {
+ if (prune_vector_set(table,
+ intersec_table->neigh_table,
+ entry,
+ NULL,
+ intersec_item,
+ neigh)) {
+ prune_item_notify_list_add(intersec_item,
+ prune_item_notify_list);
+ }
+ }
+ }
+ return prune_vector_chng;
+}
+
+static bool
+prune_neigh_item_prio_lower(struct prune_table *table,
+ const struct prune_table_entry *neigh_entry,
+ const struct prune_table_entry *entry)
+{
+ if (neigh_entry->item.priority < entry->item.priority)
+ return true;
+ else
+ return false;
+}
+
+static bool prune_neigh_list_item_lower_prio(struct prune_table *table,
+ struct prune_intersec_table_list_elem *intersec_item,
+ struct prune_intersec_table_entry *intersec_entry)
+{
+ struct prune_intersec_table_list_elem *neigh_item;
+
+ list_for_each_entry(neigh_item, &intersec_entry->neigh_table_elem_list,
+ list) {
+ if (prune_neigh_item_prio_lower(table, neigh_item->entry,
+ intersec_item->entry))
+ return true;
+ }
+ return false;
+}
+
+/*
+ * prune_item_del_prune_vector_calc - Calculate the prune vector due to an item
+ * delete flow
+ * @table: The table which the new item belongs to
+ * @intersec_table: The intersection table of the table above
+ * @ht_key: A key to store the current masked key
+ * @deleted_entry: The entry which is being deleted
+ * @notify_list: The notification list which will returned due to changes in
+ * other items in the prune object
+ */
+static void
+prune_item_del_prune_vector_calc(struct prune_table *table,
+ struct prune_intersec_table *intersec_table,
+ unsigned long *ht_key,
+ const struct prune_table_entry *deleted_entry,
+ struct list_head *prune_item_notify_list)
+{
+ struct prune_intersec_table_list_elem *intersec_item;
+ struct prune_intersec_table_entry *intersec_entry;
+ struct rhashtable_params rht_params;
+ const struct list_head *prune_list;
+ bool to_prune, notify;
+
+ bitmap_clear(ht_key, 0, table->prune->mask_len);
+ bitmap_and(ht_key, deleted_entry->item.key, intersec_table->mask,
+ table->prune->mask_len);
+
+ rht_params = table->prune->intersec_tables_ht_params;
+ intersec_entry = rhashtable_lookup_fast(&intersec_table->entry_ht,
+ &ht_key, rht_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_elem_list, list) {
+ /* Check if there is an item in my neighbor list with higher
+ * (less important) priority if so --> don't prune
+ */
+ to_prune = true;
+
+ notify = false;
+ if (!prune_neigh_list_item_lower_prio(table,
+ intersec_item,
+ intersec_entry)) {
+ /* Update intersec_item prune vector for the
+ * corresponding table to prune due to delete flow
+ */
+ prune_list = &intersec_item->entry->table_prune_vector;
+ notify = prune_vector_item_update(prune_list, table,
+ true);
+ }
+ if (notify)
+ prune_item_notify_list_add(intersec_item,
+ prune_item_notify_list);
+ }
+}
+
+static int
+prune_item_add_prune_vector_set(struct prune_table *table,
+ struct prune_table_entry *entry,
+ bool *notify)
+{
+ unsigned int mask_len = table->prune->mask_len;
+ struct prune_intersec_table *intersec_table;
+ unsigned long *ht_key;
+
+ ht_key = kzalloc(prune_mask_size(mask_len), GFP_KERNEL);
+ if (!ht_key)
+ return -ENOMEM;
+
+ *notify = false;
+ 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,
+ NULL);
+ }
+ kfree(ht_key);
+ return 0;
+}
+
+static void
+prune_neigh_prune_vector_calc(struct prune_table *table,
+ struct prune_table *curr_table,
+ unsigned long *ht_key,
+ const struct prune_table_entry *entry,
+ bool add_item,
+ struct list_head *prune_item_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,
+ intersec_table,
+ ht_key,
+ entry,
+ false,
+ prune_item_notify_list);
+ else
+ prune_item_del_prune_vector_calc(table,
+ intersec_table,
+ ht_key,
+ entry,
+ prune_item_notify_list);
+ }
+ }
+}
+
+static int
+prune_neigh_table_prune_vector_set(struct prune_table *table,
+ const struct prune_table_entry *entry,
+ bool add_item)
+{
+ struct list_head prune_item_notify_list;
+ struct prune_table *curr_table;
+ unsigned long *ht_key;
+
+ ht_key = kzalloc(prune_mask_size(table->prune->mask_len),
+ GFP_KERNEL);
+ if (!ht_key)
+ return -ENOMEM;
+
+ INIT_LIST_HEAD(&prune_item_notify_list);
+
+ list_for_each_entry(curr_table, &table->prune->table_list, list) {
+ if (curr_table != table)
+ prune_neigh_prune_vector_calc(table, curr_table,
+ ht_key, entry, add_item,
+ &prune_item_notify_list);
+ }
+ if (!list_empty(&prune_item_notify_list)) {
+ table->prune->ops->prune_item_notify(&prune_item_notify_list,
+ entry->item.table,
+ add_item ? false : true);
+ prune_item_notify_list_fini(&prune_item_notify_list);
+ }
+ kfree(ht_key);
+ return 0;
+}
+
+static struct prune_table_entry *
+prune_table_entry_create(struct prune *prune, struct prune_table *table,
+ unsigned long *key, unsigned long priority, void *priv,
+ bool *notify)
+{
+ struct prune_table_entry *entry;
+ int err;
+
+ if (bitmap_subset(key, table->mask, prune->mask_len) != 1)
+ return ERR_PTR(-EPERM);
+
+ entry = prune_item_entry_create(prune, key, priority, priv);
+ if (!entry)
+ return ERR_PTR(-ENOMEM);
+
+ err = prune_item_add_prune_vector_set(table, entry, notify);
+ if (err) {
+ prune_entry_destroy(entry);
+ return ERR_PTR(err);
+ }
+ list_add_tail(&entry->list, &table->entry_list);
+ entry->item.table = table;
+
+ return entry;
+}
+
+static void
+prune_intersec_entry_destroy(struct prune_intersec_table_entry *intersec_entry)
+{
+ if (!list_empty(&intersec_entry->intersec_table_elem_list) ||
+ !list_empty(&intersec_entry->neigh_table_elem_list))
+ WARN_ON(1); /* Try to free a non empty intersection entry */
+
+ kfree(intersec_entry->ht_key);
+ kfree(intersec_entry);
+}
+
+static struct prune_intersec_table_entry
+*prune_intersec_entry_create(unsigned long *intersec_table_mask,
+ unsigned long *item_key,
+ struct prune_intersec_table *intersec_table,
+ unsigned int mask_len)
+{
+ struct prune_intersec_table_entry *intersec_entry;
+
+ intersec_entry = kzalloc(sizeof(*intersec_entry), GFP_KERNEL);
+ if (!intersec_entry)
+ goto err_entry_alloc;
+
+ intersec_entry->ht_key = kzalloc(prune_mask_size(mask_len), GFP_KERNEL);
+ if (!intersec_entry->ht_key)
+ goto err_key_alloc;
+
+ intersec_entry->intersec_table = intersec_table;
+
+ bitmap_and(intersec_entry->ht_key, intersec_table_mask, item_key,
+ mask_len);
+
+ INIT_LIST_HEAD(&intersec_entry->intersec_table_elem_list);
+ INIT_LIST_HEAD(&intersec_entry->neigh_table_elem_list);
+
+ return intersec_entry;
+err_key_alloc:
+ kfree(intersec_entry);
+err_entry_alloc:
+ return ERR_PTR(-ENOMEM);
+}
+
+static int prune_intersec_item_add(struct prune_intersec_table *intersec_table,
+ struct prune_table_entry *entry,
+ bool neigh)
+{
+ struct prune_intersec_table_list_elem *intersec_item = NULL;
+ unsigned int mask_len = entry->item.table->prune->mask_len;
+ struct prune_intersec_table_list_elem *neigh_item = NULL;
+ struct prune_intersec_table_entry *intersec_entry;
+ struct rhashtable_params rht_params;
+ unsigned long *ht_key;
+ bool found = true;
+ int err = 0;
+
+ ht_key = kzalloc(prune_mask_size(mask_len), GFP_KERNEL);
+ if (!ht_key)
+ return -ENOMEM;
+
+ bitmap_and(ht_key, intersec_table->mask, entry->item.key, mask_len);
+
+ rht_params = prune_intersec_table_entry_rht_params(intersec_table);
+
+ intersec_entry = rhashtable_lookup_fast(&intersec_table->entry_ht,
+ &ht_key, rht_params);
+ kfree(ht_key);
+
+ if (!intersec_entry) {
+ /* create new intersec entry since there ins't already one */
+ intersec_entry = prune_intersec_entry_create(intersec_table->mask,
+ entry->item.key,
+ intersec_table,
+ mask_len);
+ if (IS_ERR(intersec_entry)) {
+ err = PTR_ERR(intersec_entry);
+ goto err_entry_alloc;
+ }
+ found = false;
+ }
+
+ if (!neigh) {
+ intersec_item = kzalloc(sizeof(*intersec_item), GFP_KERNEL);
+ if (!intersec_item)
+ goto err_list_item_alloc;
+
+ intersec_item->entry = entry;
+ list_add_tail(&intersec_item->list,
+ &intersec_entry->intersec_table_elem_list);
+ } else {
+ neigh_item = kzalloc(sizeof(*neigh_item), GFP_KERNEL);
+ if (!neigh_item)
+ goto err_nigh_list_item_alloc;
+
+ neigh_item->entry = entry;
+ list_add_tail(&neigh_item->list,
+ &intersec_entry->neigh_table_elem_list);
+ }
+ if (!found) {
+ err = rhashtable_insert_fast(&intersec_table->entry_ht,
+ &intersec_entry->ht_node,
+ rht_params);
+ if (err)
+ goto err_rhashtable_insert;
+ }
+ return 0;
+
+err_rhashtable_insert:
+ if (!neigh) {
+ list_del(&intersec_item->list);
+ kfree(intersec_item);
+ } else {
+ list_del(&neigh_item->list);
+ kfree(neigh_item);
+ }
+err_nigh_list_item_alloc:
+err_list_item_alloc:
+ if (!found)
+ prune_intersec_entry_destroy(intersec_entry);
+err_entry_alloc:
+ return err;
+}
+
+static int
+prune_intersec_item_remove(struct prune_intersec_table *intersec_table,
+ struct prune_table_entry *remove_entry,
+ bool neigh)
+{
+ unsigned int mask_len = remove_entry->item.table->prune->mask_len;
+ struct prune_intersec_table_list_elem *intersec_item;
+ struct prune_intersec_table_entry *intersec_entry;
+ struct prune_intersec_table_list_elem *neigh_item;
+ struct rhashtable_params rht_params;
+ unsigned long *ht_key;
+ struct list_head *pos, *tmp;
+
+ ht_key = kzalloc(prune_mask_size(mask_len), GFP_KERNEL);
+ if (!ht_key)
+ return -ENOMEM;
+
+ bitmap_and(ht_key, intersec_table->mask, remove_entry->item.key,
+ mask_len);
+
+ rht_params = prune_intersec_table_entry_rht_params(intersec_table);
+ intersec_entry = rhashtable_lookup_fast(&intersec_table->entry_ht,
+ &ht_key, rht_params);
+ if (!intersec_entry) {
+ kfree(ht_key);
+ return -EPERM;
+ }
+ if (!neigh) {
+ list_for_each_safe(pos, tmp,
+ &intersec_entry->intersec_table_elem_list) {
+ intersec_item = list_entry(pos, typeof(*intersec_item),
+ list);
+ if (intersec_item->entry == remove_entry) {
+ list_del(&intersec_item->list);
+ kfree(intersec_item);
+ break;
+ }
+ }
+ } else {
+ list_for_each_safe(pos, tmp,
+ &intersec_entry->neigh_table_elem_list) {
+ neigh_item = list_entry(pos, typeof(*neigh_item), list);
+ if (remove_entry == neigh_item->entry) {
+ list_del(&neigh_item->list);
+ kfree(neigh_item);
+ break;
+ }
+ }
+ }
+ if (list_empty(&intersec_entry->intersec_table_elem_list) &&
+ list_empty(&intersec_entry->neigh_table_elem_list)) {
+ rhashtable_remove_fast(&intersec_table->entry_ht,
+ &intersec_entry->ht_node,
+ rht_params);
+ prune_intersec_entry_destroy(intersec_entry);
+ }
+ kfree(ht_key);
+ 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 = kzalloc(prune_mask_size(mask_len),
+ GFP_KERNEL);
+ 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;
+}
+
+/*
+ * prune_intersec_table_items_update - Update the item of the current table to
+ * the nighbor items in the intersection
+ * table
+ * @curr_table: The table which her items needs to be updated in the
+ * intersection table
+ * @intersec_table: The intersection table which needs to be updated
+ * @add_to_neighbor_items: True if items need to be add to neigh_table_elem_list
+ */
+static void prune_intersec_table_items_update(struct prune_table *curr_table,
+ struct prune_intersec_table *intersec_table,
+ bool add_to_neighbor_items)
+{
+ struct prune_table_entry *entry;
+
+ list_for_each_entry(entry, &curr_table->entry_list, list) {
+ prune_intersec_item_add(intersec_table, entry,
+ add_to_neighbor_items);
+ }
+}
+
+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);
+
+ err = rhashtable_init(&intersec_table1->entry_ht,
+ &prune->intersec_tables_ht_params);
+ if (err)
+ goto err_rhashtable_init_1;
+
+ err = rhashtable_init(&intersec_table2->entry_ht,
+ &prune->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_items_update(curr_table, intersec_table1, false);
+ 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_items_update(curr_table, intersec_table2, true);
+ list_add(&intersec_table2->list, &new_table->intersec_table_list);
+
+ return 0;
+
+err_rhashtable_init_2:
+ rhashtable_destroy(&intersec_table2->entry_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_list_elem *intersec_item, *neigh_item;
+ struct prune_intersec_table_entry *rht_node = ptr;
+ struct list_head *pos, *tmp;
+
+
+ list_for_each_safe(pos, tmp, &rht_node->intersec_table_elem_list) {
+ 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->neigh_table_elem_list) {
+ neigh_item = list_entry(pos, typeof(*neigh_item), list);
+ list_del(&neigh_item->list);
+ kfree(neigh_item);
+ }
+ kfree(rht_node->ht_key);
+ 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 *entry_ht;
+ unsigned long *curr_mask;
+ int err;
+
+ curr_mask = kzalloc(prune_mask_size(mask_len), GFP_KERNEL);
+ 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);
+ entry_ht = &curr_intersec_table->entry_ht;
+ rhashtable_free_and_destroy(entry_ht,
+ 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_table_demolish(struct prune_table *table)
+{
+ struct prune_intersec_table *curr_intersec_table;
+ struct prune *prune = table->prune;
+ struct prune_table *curr_table;
+ struct rhashtable *entry_ht;
+ struct list_head *pos, *tmp;
+ int err;
+
+ /* 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);
+ entry_ht = &curr_intersec_table->entry_ht;
+ rhashtable_free_and_destroy(entry_ht,
+ prune_intersec_rht_free,
+ NULL);
+ list_del(&curr_intersec_table->list);
+ kfree(curr_intersec_table->mask);
+ kfree(curr_intersec_table);
+ }
+ WARN_ON_ONCE(!list_empty(&table->intersec_table_list)); /* TODO remove*/
+
+ return 0;
+}
+
+static int
+prune_intersec_list_item_add(struct prune_table *item_added_table,
+ struct prune_table *table,
+ struct prune_table_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,
+ 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_table_entry *remove_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) {
+ if (curr_intersec_table->neigh_table == remove_item_table ||
+ !neigh_item) {
+ err = prune_intersec_item_remove(curr_intersec_table,
+ remove_entry,
+ neigh_item);
+ if (err)
+ return err;
+ }
+ }
+ return 0;
+}
+
+static void prune_table_item_vector_remove(struct prune_table *table,
+ struct prune_table *del_table)
+{
+ struct prune_vector_item *vector_item;
+ struct prune_table_entry *entry;
+ struct list_head *pos, *tmp;
+
+ list_for_each_entry(entry, &table->entry_list, list) {
+ 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;
+ }
+ }
+ }
+}
+
+static int prune_table_item_vector_add(struct prune_table *table,
+ struct prune_table *new_table)
+{
+ struct prune_vector_item *vector_item;
+ struct prune_table_entry *entry;
+
+ list_for_each_entry(entry, &table->entry_list, list) {
+ vector_item = kzalloc(sizeof(*vector_item), GFP_KERNEL);
+ if (!vector_item) {
+ prune_table_item_vector_remove(table, new_table);
+ return -ENOMEM;
+ }
+ vector_item->pruned = true;
+ vector_item->table = new_table;
+ list_add_tail(&vector_item->list,
+ &entry->table_prune_vector);
+ }
+ return 0;
+}
+
+/**
+ * prune_item_prune_table_add - Add new vector_item to each item in each table
+ * @prune: The prune object which contains all tables
+ * @new_table: The new table which needs to be pointed by the vector_item
+ */
+static int prune_item_prune_table_add(struct prune *prune,
+ struct prune_table *new_table)
+{
+ struct prune_table *table;
+ int err;
+
+ list_for_each_entry(table, &prune->table_list, list) {
+ err = prune_table_item_vector_add(table, new_table);
+ if (err)
+ return err;
+ }
+ return 0;
+}
+
+/**
+ * prune_item_prune_table_add - Add new vector_item to each item in each table
+ * @prune: The prune object which contains all tables
+ * del_table: The table which needs to be revmoed from the vector_item
+ */
+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_vector_remove(table, del_table);
+ }
+}
+
+static void
+prune_intersec_tables_ht_params_init(struct prune *prune, unsigned int mask_len)
+{
+ prune->intersec_tables_ht_params.key_len = mask_len;
+ prune->intersec_tables_ht_params.key_offset =
+ offsetof(struct prune_intersec_table_entry, ht_key);
+ prune->intersec_tables_ht_params.head_offset =
+ offsetof(struct prune_intersec_table_entry, ht_node);
+ prune->intersec_tables_ht_params.obj_cmpfn = prune_intersec_ht_cmp;
+ prune->intersec_tables_ht_params.hashfn = prune_intersec_ht_hash;
+ prune->intersec_tables_ht_params.automatic_shrinking = true;
+}
+
+/**
+ * prune_create - Create a prune object which manages the pruning vector
+ * between tables
+ * @mask_len: Set the mask length (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.
+ *
+ */
+struct prune *prune_create(unsigned int mask_len, const struct prune_ops *ops,
+ void *priv)
+{
+ struct prune *prune;
+
+ if (!ops || !mask_len)
+ return NULL;
+
+ prune = kzalloc(sizeof(*prune), GFP_KERNEL);
+ if (!prune)
+ return NULL;
+
+ prune->priv = priv;
+ prune->mask_len = mask_len;
+ INIT_LIST_HEAD(&prune->table_list);
+ prune->ops = ops;
+ prune_intersec_tables_ht_params_init(prune, mask_len);
+
+ return prune;
+}
+EXPORT_SYMBOL(prune_create);
+
+/**
+ * prune_destroy - Destroy the prune object
+ * @prune: Prune object
+ */
+void prune_destroy(struct prune *prune)
+{
+ WARN_ON(!list_empty(&prune->table_list));
+
+ kfree(prune);
+}
+EXPORT_SYMBOL(prune_destroy);
+
+/**
+ * prune_table_create - Create new table with specific mask and adds it to the
+ * prune object
+ * @prune: Prune object
+ * @mask: Table mask - all items key should match this mask
+ * @mask_len: The length of mask - number of bits
+ * @priv: user data
+ *
+ * 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, unsigned long *mask,
+ unsigned int mask_len, void *priv)
+{
+ struct prune_table *table;
+ int err;
+
+ if (WARN_ON(prune->mask_len != mask_len))
+ return ERR_PTR(-EINVAL);
+
+ table = kzalloc(sizeof(*table), GFP_KERNEL);
+ if (!table)
+ return ERR_PTR(-ENOMEM);
+
+ table->mask = kzalloc(prune_mask_size(prune->mask_len), GFP_KERNEL);
+ if (!table->mask) {
+ err = -ENOMEM;
+ goto err_mask_alloc_fail;
+ }
+ bitmap_copy(table->mask, mask, prune->mask_len);
+ table->priv = priv;
+ table->prune = prune;
+ INIT_LIST_HEAD(&table->entry_list);
+ INIT_LIST_HEAD(&table->intersec_table_list);
+
+ /* Enlarge the prune vector of all item with the new table */
+ err = prune_item_prune_table_add(prune, table);
+ if (err)
+ goto err_table_add;
+
+ err = prune_intersec_table_build(prune, table);
+ if (err)
+ goto err_table_build;
+
+ list_add_tail(&table->list, &prune->table_list);
+
+ return table;
+
+err_table_build:
+ prune_item_prune_table_remove(prune, table);
+err_table_add:
+ kfree(table->mask);
+err_mask_alloc_fail:
+ kfree(table);
+ return ERR_PTR(err);
+}
+EXPORT_SYMBOL(prune_table_create);
+
+/**
+ * prune_table_destroy - Remove 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_table *table)
+{
+ struct prune *prune;
+ int err;
+
+ if (WARN_ON(!list_empty(&table->entry_list)))
+ return -EPERM;
+
+ prune = table->prune;
+
+ err = prune_intersec_table_demolish(table);
+ if (err)
+ return err;
+
+ prune_item_prune_table_remove(prune, table);
+
+ list_del(&table->list);
+ kfree(table->mask);
+ kfree(table);
+
+ return 0;
+}
+EXPORT_SYMBOL(prune_table_destroy);
+
+/**
+ * prune_item_create - Create an item and adds it to a table.
+ * @prune: Prune object.
+ * @table: Add the item to this table.
+ * @key: Item key (bitmap) - must be correspond to table
+ * mask and length (not copied by the library)
+ * @priority: Item priority
+ * @priv: User data
+ * @non_def_prune_vector: If true, this item don't prunes all tables in
+ * the prune object [out].
+ *
+ * Returns a pointer to newly created prune item instance in case of success,
+ * otherwise it returns pointer to an error.
+ *
+ * Note: It's the user responsibility to care for synchronization.
+ */
+struct prune_item *prune_item_create(struct prune *prune,
+ struct prune_table *table,
+ unsigned long priority,
+ unsigned long *key,
+ void *priv,
+ bool *non_def_prune_vector)
+{
+ struct prune_table_entry *entry;
+ struct prune_table *curr_table;
+ int err;
+
+ entry = prune_table_entry_create(prune, table, key, priority, priv,
+ non_def_prune_vector);
+ if (IS_ERR(entry)) {
+ err = PTR_ERR(entry);
+ return ERR_PTR(err);
+ }
+
+ /* 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, entry,
+ curr_table != table ?
+ true : false);
+ if (err) {
+ prune_entry_destroy(entry);
+ return ERR_PTR(err);
+ }
+ }
+ /* Update prune vector of the corresponding items of the neighbor
+ * tables
+ */
+ err = prune_neigh_table_prune_vector_set(table, entry, true);
+ if (err) {
+ prune_item_destroy(&entry->item);
+ return ERR_PTR(err);
+ }
+ return &entry->item;
+}
+EXPORT_SYMBOL(prune_item_create);
+
+/**
+ * prune_item_destroy - remove 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_destroy(struct prune_item *item)
+{
+ struct prune_table_entry *entry;
+ struct prune_table *curr_table;
+ struct prune_table *table;
+ struct prune *prune;
+ int err;
+
+ table = item->table;
+ prune = table->prune;
+
+ entry = container_of(item, struct prune_table_entry, item);
+ /* 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, entry,
+ 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(table, entry, false);
+ if (err)
+ return err;
+
+ prune_entry_destroy(entry);
+
+ return 0;
+}
+EXPORT_SYMBOL(prune_item_destroy);
+
+void *prune_table_priv(struct prune_table *table)
+{
+ return table->priv;
+}
+EXPORT_SYMBOL(prune_table_priv);
+
+struct list_head *prune_item_prune_vector(struct prune_item *item)
+{
+ struct prune_table_entry *entry;
+
+ entry = container_of(item, struct prune_table_entry, item);
+ return &entry->table_prune_vector;
+
+}
+EXPORT_SYMBOL(prune_item_prune_vector);
+
+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,1215 @@
+// SPDX-License-Identifier: GPL-2.0 OR BSD-3-Clause
+/*
+ * 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>
+
+#define TABLES_2 (2)
+#define TABLES_3 (3)
+#define TABLES_4 (4)
+#define ITEMS_3 (3)
+#define ITEMS_6 (6)
+#define ITEMS_8 (8)
+
+struct test_prune_table_attr {
+ unsigned long *mask;
+ unsigned int mask_len; /* Number of bits */
+ unsigned int table_id;
+};
+
+struct test_prune_item {
+ unsigned long priority; /* Lower number means higher priority */
+ unsigned long *key;
+ void *priv; /* user item id */
+ bool non_def_prune_vector;
+};
+
+struct test_prune_vector_item {
+ unsigned int table_id;
+ bool is_pruned; /* True if the item is pruning this table */
+};
+
+static inline size_t prune_mask_size(unsigned int nbits)
+{
+ return BITS_TO_LONGS(nbits) * sizeof(unsigned long);
+}
+
+static void test_prune_notification_print(struct prune_item *item, bool print)
+{
+ struct prune_vector_item *vector_item;
+ struct list_head *prune_vector;
+ struct prune_table *table;
+ void *priv;
+ int i;
+
+ if (print) {
+ pr_info("item prio: %u\n", item->priority);
+ pr_info("item mask: %lu\n", *item->key);
+ pr_info("item from table *: %p\n", item->table);
+
+ prune_vector = prune_item_prune_vector(item);
+
+ i = 0;
+ list_for_each_entry(vector_item, prune_vector, list) {
+ table = vector_item->table;
+ priv = prune_table_priv(table);
+ pr_info("i = [%d], table priv: %lu\t is prune: %s\t pruned table *: %p\n",
+ i,
+ (uintptr_t)priv,
+ vector_item->pruned ? "Yes" : "No",
+ table);
+ i++;
+ }
+ }
+}
+
+static bool test_prune_check_prune_vector(struct prune_item *item,
+ bool *prune_val_arr,
+ int arr_len,
+ bool non_def_prune_vector)
+{
+ #define MAX_CASE (5)
+ struct prune_vector_item *vector_item;
+ struct list_head *prune_vector = prune_item_prune_vector(item);
+ bool case_passed = true;
+ int table_id = 0;
+ bool pruned;
+ void *priv;
+
+ list_for_each_entry(vector_item, prune_vector, list) {
+ pruned = vector_item->pruned;
+ priv = prune_table_priv(vector_item->table);
+
+ if (!non_def_prune_vector && pruned) {
+ continue;
+ } else if (!non_def_prune_vector && !pruned) {
+ WARN(1, "test didn't pass un pruned table in default prune-vector");
+ return false;
+ }
+
+ if (table_id == arr_len || table_id > MAX_CASE) {
+ WARN(1, "test didn't pass too many items in prune vector");
+ return false;
+ }
+
+ switch (table_id) {
+ case MAX_CASE - 5:
+ case_passed =
+ (uintptr_t)priv == table_id &&
+ pruned == prune_val_arr[0];
+ break;
+ case MAX_CASE - 4:
+ case_passed =
+ (uintptr_t)priv == table_id &&
+ pruned == prune_val_arr[1];
+ break;
+ case MAX_CASE - 3:
+ case_passed =
+ (uintptr_t)priv == table_id &&
+ pruned == prune_val_arr[2];
+ break;
+ case MAX_CASE - 2:
+ case_passed =
+ (uintptr_t)priv == table_id &&
+ pruned == prune_val_arr[3];
+ break;
+ case MAX_CASE - 1:
+ case_passed =
+ (uintptr_t)priv == table_id &&
+ pruned == prune_val_arr[4];
+ break;
+ case MAX_CASE:
+ case_passed =
+ (uintptr_t)priv == table_id &&
+ pruned == prune_val_arr[5];
+ break;
+ default:
+ case_passed = false;
+ break;
+ }
+ table_id++;
+
+ if (!case_passed) {
+ WARN(1, "test didn't pass for table [%d]", table_id);
+ return case_passed;
+ }
+ }
+ return case_passed;
+}
+
+static bool test_prune_check_case(struct prune_item *item,
+ unsigned int prio,
+ bool *prune_val_arr,
+ int arr_len,
+ int test_case)
+{
+ bool case_passed = true;
+
+ if (item->priority != prio) {
+ WARN(1, "test case [%d] didn't pass. Incorrect priority [%u]",
+ test_case, item->priority);
+ return false;
+ }
+
+ case_passed = test_prune_check_prune_vector(item, prune_val_arr,
+ arr_len, true);
+ if (!case_passed)
+ WARN(1, "test case [%d] didn't pass", test_case);
+
+ return case_passed;
+}
+
+static void
+test_prune_subsequent_notify(struct list_head *prune_item_notify_list,
+ struct prune_table *table, bool pruned)
+{
+ bool prune_value_case0[2] = {true, false};
+ bool prune_value_case1[3] = {true, false, false};
+ bool prune_value_case2[3] = {true, true, false};
+ bool prune_value_case3[3] = {true, true, true};
+ struct prune_item *item;
+ static int test_case;
+
+ list_for_each_entry(item, prune_item_notify_list, list) {
+ test_prune_notification_print(item, false);
+
+ switch (test_case) {
+ case 0:
+ test_prune_check_case(item, 10,
+ prune_value_case0,
+ ARRAY_SIZE(prune_value_case0),
+ test_case);
+ break;
+ case 1:
+ test_prune_check_case(item, 10,
+ prune_value_case1,
+ ARRAY_SIZE(prune_value_case1),
+ test_case);
+ break;
+ case 2:
+ test_prune_check_case(item, 5,
+ prune_value_case2,
+ ARRAY_SIZE(prune_value_case2),
+ test_case);
+ break;
+ case 3:
+ test_prune_check_case(item, 8,
+ prune_value_case3,
+ ARRAY_SIZE(prune_value_case3),
+ test_case);
+ break;
+ default:
+ WARN(1, "unexpected test case %d", test_case);
+ break;
+ }
+ test_case++;
+ }
+}
+
+static void
+test_prune_flows_1_notify(struct list_head *prune_item_notify_list,
+ struct prune_table *table, bool pruned)
+{
+ 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 *item;
+ static int test_case;
+
+ list_for_each_entry(item, prune_item_notify_list, list) {
+ test_prune_notification_print(item, false);
+
+ switch (test_case) {
+ case 0:
+ test_prune_check_case(item, 10,
+ prune_value_arr_case0,
+ ARRAY_SIZE(prune_value_arr_case0),
+ test_case);
+ break;
+ case 1:
+ test_prune_check_case(item, 7,
+ prune_value_arr_case1,
+ ARRAY_SIZE(prune_value_arr_case1),
+ test_case);
+ break;
+ case 2:
+ test_prune_check_case(item, 10,
+ 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 list_head *prune_item_notify_list,
+ struct prune_table *table, bool pruned)
+{
+ bool prune_value_arr_case0[2] = {false, true};
+ bool prune_value_arr_case1[3] = {true, false, true};
+ bool prune_value_arr_case2[3] = {true, true, true};
+ struct prune_item *item;
+ static int test_case;
+
+ list_for_each_entry(item, prune_item_notify_list, list) {
+ test_prune_notification_print(item, false);
+
+ switch (test_case) {
+ case 0:
+ test_prune_check_case(item, 7,
+ prune_value_arr_case0,
+ ARRAY_SIZE(prune_value_arr_case0),
+ test_case);
+ break;
+ case 1:
+ test_prune_check_case(item, 7,
+ prune_value_arr_case1,
+ ARRAY_SIZE(prune_value_arr_case1),
+ test_case);
+ break;
+ case 2:
+ test_prune_check_case(item, 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_basic_notify(struct list_head *prune_item_notify_list,
+ struct prune_table *table, bool pruned)
+{
+ 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 *item;
+ static int test_case;
+
+ list_for_each_entry(item, prune_item_notify_list, list) {
+ test_prune_notification_print(item, false);
+
+ switch (test_case) {
+ case 0:
+ test_prune_check_case(item, 3,
+ prune_value_arr_case0,
+ ARRAY_SIZE(prune_value_arr_case0),
+ test_case);
+ break;
+ case 1:
+ test_prune_check_case(item, 3,
+ prune_value_arr_case1,
+ ARRAY_SIZE(prune_value_arr_case1),
+ test_case);
+ break;
+ case 2:
+ test_prune_check_case(item, 2,
+ prune_value_arr_case2,
+ ARRAY_SIZE(prune_value_arr_case2),
+ test_case);
+ break;
+ case 3:
+ test_prune_check_case(item, 3,
+ prune_value_arr_case3,
+ ARRAY_SIZE(prune_value_arr_case3),
+ test_case);
+ break;
+ case 4:
+ test_prune_check_case(item, 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++;
+ if (test_case == 10)
+ return;
+ }
+}
+
+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 test_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 == 0; j--)
+ kfree(table_attr[j].mask);
+ }
+ return -ENOMEM;
+ }
+ table_attr[i].mask_len = mask_len;
+ table_attr[i].table_id = i;
+ }
+ return 0;
+}
+
+static void table_attr_destroy(struct test_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 test_prune_item *pi_arr,
+ unsigned int pi_cnt)
+{
+ int i;
+
+ for (i = 0; i < pi_cnt; i++)
+ kfree(pi_arr[i].key);
+}
+
+static int test_prune_item_arr_create(struct test_prune_item *tpi_arr,
+ unsigned int pi_cnt,
+ unsigned int pi_nbits)
+{
+ int i, j = 0;
+
+ for (i = 0; i < pi_cnt; i++) {
+ tpi_arr[i].key = kcalloc(1, prune_mask_size(pi_nbits),
+ GFP_KERNEL);
+ if (!tpi_arr[i].key) {
+ if (i > 0)
+ for (j = i - 1; j > -1; j--)
+ kfree(tpi_arr[j].key);
+ return -ENOMEM;
+ }
+ bitmap_clear(tpi_arr[i].key, 0, pi_nbits);
+ }
+ return 0;
+}
+
+/*
+ * Basic test: test add / remove table and item without checking their prune
+ * vector
+ */
+static int test_prune_basic(void)
+{
+ struct test_prune_table_attr table_attr[TABLES_3];
+ struct prune_table *table_arr[TABLES_3];
+ struct test_prune_item tpi_arr[ITEMS_3];
+ struct prune_item *item_arr[ITEMS_3];
+ unsigned int nbits = 40;
+ struct prune *prune;
+ 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, TABLES_3);
+ if (err)
+ return err;
+
+ err = test_prune_item_arr_create(tpi_arr, ITEMS_3, 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].mask,
+ table_attr[0].mask_len,
+ (int *)(uintptr_t)table_attr[0].table_id);
+ 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].mask,
+ table_attr[1].mask_len,
+ (int *)(uintptr_t)table_attr[1].table_id);
+ 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].mask,
+ table_attr[2].mask_len,
+ (int *)(uintptr_t)table_attr[2].table_id);
+ if (IS_ERR(table_arr[2]))
+ return PTR_ERR(table_arr[2]);
+
+ tpi_arr[0].priority = 3;
+ tpi_arr[0].priv = NULL;
+ bitmap_set(tpi_arr[0].key, 0, 2);
+ item_arr[0] = prune_item_create(prune, table_arr[0],
+ tpi_arr[0].priority, tpi_arr[0].key,
+ tpi_arr[0].priv,
+ &tpi_arr[0].non_def_prune_vector);
+ if (IS_ERR(item_arr[0]))
+ return -EBADE;
+
+ /* default prune vector */
+ if (!test_prune_check_prune_vector(item_arr[0], NULL, 0,
+ tpi_arr[0].non_def_prune_vector))
+ return -EBADE;
+
+ tpi_arr[1].priority = 2;
+ tpi_arr[1].priv = NULL;
+ bitmap_set(tpi_arr[1].key, 1, 2);
+ item_arr[1] = prune_item_create(prune, table_arr[1],
+ tpi_arr[1].priority,
+ tpi_arr[1].key, tpi_arr[1].priv,
+ &tpi_arr[1].non_def_prune_vector);
+ if (IS_ERR(item_arr[1]))
+ return -EBADE;
+
+ /* default prune vector */
+ if (!test_prune_check_prune_vector(item_arr[1], NULL, 0,
+ tpi_arr[1].non_def_prune_vector))
+ return -EBADE;
+
+ tpi_arr[2].priority = 1;
+ tpi_arr[2].priv = NULL;
+ bitmap_set(tpi_arr[2].key, 2, 2);
+
+ item_arr[2] = prune_item_create(prune, table_arr[2],
+ tpi_arr[2].priority,
+ tpi_arr[2].key, tpi_arr[2].priv,
+ &tpi_arr[2].non_def_prune_vector);
+ if (IS_ERR(item_arr[1]))
+ return -EBADE;
+
+ /* default prune vector */
+ if (!test_prune_check_prune_vector(item_arr[2], NULL, 0,
+ tpi_arr[2].non_def_prune_vector))
+ return -EBADE;
+
+ err = prune_item_destroy(item_arr[2]);
+ if (err)
+ return err;
+
+ err = prune_item_destroy(item_arr[0]);
+ if (err)
+ return err;
+
+ err = prune_item_destroy(item_arr[1]);
+ if (err)
+ return err;
+
+ prune_table_destroy(table_arr[0]);
+
+ prune_table_destroy(table_arr[1]);
+
+ prune_table_destroy(table_arr[2]);
+
+ prune_destroy(prune);
+
+ prune_item_arr_destroy(tpi_arr, ITEMS_3);
+ table_attr_destroy(table_attr, TABLES_3);
+
+ return 0;
+}
+
+static int test_prune_flows_add_delete_items_1(void)
+{
+ struct test_prune_table_attr table_attr[TABLES_2];
+ struct prune_table *table_arr[TABLES_2];
+ struct test_prune_item tpi_arr[ITEMS_3];
+ struct prune_item *item_arr[ITEMS_3];
+ bool prune_val_arr_2[2] = {true, false};
+ unsigned int nbits = 40;
+ struct prune *prune;
+ 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, TABLES_2);
+ if (err)
+ return err;
+
+ err = test_prune_item_arr_create(tpi_arr, ITEMS_3, 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].mask,
+ table_attr[0].mask_len,
+ (int *)(uintptr_t)table_attr[0].table_id);
+ 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].mask,
+ table_attr[1].mask_len,
+ (int *)(uintptr_t)table_attr[1].table_id);
+ if (IS_ERR(table_arr[0]))
+ return PTR_ERR(table_arr[0]);
+
+ /* Create item0 x.2.3.4.x prio 5 */
+ tpi_arr[0].priority = 5;
+ tpi_arr[0].priv = NULL;
+ bitmap_set(tpi_arr[0].key, 14, 1); /* Set 2 on #2 byte*/
+ bitmap_set(tpi_arr[0].key, 22, 2); /* Set 3 on #3 byte*/
+ bitmap_set(tpi_arr[0].key, 29, 1); /* Set 4 on #4 byte*/
+
+ /* Create item1 x.2.3.5.x prio 10*/
+ tpi_arr[1].priority = 10;
+ tpi_arr[1].priv = NULL;
+ bitmap_set(tpi_arr[1].key, 14, 1); /* Set 2 on #2 byte*/
+ bitmap_set(tpi_arr[1].key, 22, 2); /* Set 3 on #3 byte*/
+ bitmap_set(tpi_arr[1].key, 29, 1); /* Set 5 on #4 byte*/
+ bitmap_set(tpi_arr[1].key, 31, 1); /* Set 5 on #4 byte*/
+
+ /* Add item0: x.2.3.4.x to table 1 */
+ item_arr[0] = prune_item_create(prune, table_arr[1],
+ tpi_arr[0].priority,
+ tpi_arr[0].key, tpi_arr[0].priv,
+ &tpi_arr[0].non_def_prune_vector);
+ if (IS_ERR(item_arr[0]))
+ return -EBADE;
+ /* default prune vector */
+ if (!test_prune_check_prune_vector(item_arr[0], NULL, 0,
+ tpi_arr[0].non_def_prune_vector))
+ 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 */
+ item_arr[1] = prune_item_create(prune, table_arr[1],
+ tpi_arr[1].priority,
+ tpi_arr[1].key, tpi_arr[1].priv,
+ &tpi_arr[1].non_def_prune_vector);
+ if (IS_ERR(item_arr[1]))
+ return -EBADE;
+ /* default prune vector */
+ if (!test_prune_check_prune_vector(item_arr[1], NULL, 0,
+ tpi_arr[1].non_def_prune_vector))
+ 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 */
+ tpi_arr[2].priority = 7;
+ tpi_arr[2].priv = NULL;
+ bitmap_set(tpi_arr[2].key, 7, 1); /* Set 1 on #1 byte*/
+ bitmap_set(tpi_arr[2].key, 14, 1); /* Set 2 on #2 byte*/
+ bitmap_set(tpi_arr[2].key, 22, 2); /* Set 3 on #3 byte*/
+
+ /* Add item2: 1.2.3.x.x prio 7 to table 0 */
+ item_arr[2] = prune_item_create(prune, table_arr[0],
+ tpi_arr[2].priority,
+ tpi_arr[2].key, tpi_arr[2].priv,
+ &tpi_arr[2].non_def_prune_vector);
+ if (IS_ERR(item_arr[2]))
+ return -EBADE;
+
+ if (!test_prune_check_prune_vector(item_arr[2], prune_val_arr_2, 2,
+ tpi_arr[2].non_def_prune_vector))
+ 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_destroy(item_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_destroy(item_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_destroy(item_arr[1]);
+ if (err)
+ return err;
+
+ err = prune_table_destroy(table_arr[0]);
+ if (err)
+ return err;
+
+ err = prune_table_destroy(table_arr[1]);
+ if (err)
+ return err;
+
+ prune_destroy(prune);
+
+ prune_item_arr_destroy(tpi_arr, ITEMS_3);
+ table_attr_destroy(table_attr, TABLES_2);
+
+ return 0;
+}
+
+static int test_prune_flows_add_delete_item_2(void)
+{
+ bool prune_val_arr_3[3] = {false, false, true};
+ bool prune_val_arr_5[3] = {false, true, true};
+ struct test_prune_table_attr table_attr[TABLES_3];
+ struct prune_table *table_arr[TABLES_3];
+ struct test_prune_item tpi_arr[ITEMS_6];
+ struct prune_item *item_arr[ITEMS_6];
+ unsigned int nbits = 40;
+ struct prune *prune;
+ 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, TABLES_3);
+ if (err)
+ return err;
+
+ err = test_prune_item_arr_create(tpi_arr, ITEMS_6, 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 7 */
+ tpi_arr[0].priority = 7;
+ tpi_arr[0].priv = NULL;
+ bitmap_set(tpi_arr[0].key, 22, 2); /* Set 3 on #3 byte */
+ bitmap_set(tpi_arr[0].key, 29, 1); /* Set 5 on #4 byte */
+ bitmap_set(tpi_arr[0].key, 31, 1); /* Set 5 on #4 byte */
+ bitmap_set(tpi_arr[0].key, 37, 1); /* Set 5 on #5 byte */
+ bitmap_set(tpi_arr[0].key, 39, 1); /* Set 5 on #5 byte */
+
+ /* Create item1 1.2.3.x.x prio 7 */
+ tpi_arr[1].priority = 7;
+ tpi_arr[1].priv = NULL;
+ bitmap_set(tpi_arr[1].key, 7, 1); /* Set 1 on #1 byte */
+ bitmap_set(tpi_arr[1].key, 14, 1); /* Set 2 on #2 byte */
+ bitmap_set(tpi_arr[1].key, 22, 2); /* Set 3 on #3 byte */
+
+ /* Create item2 x.x.3.5.x prio 3 */
+ tpi_arr[2].priority = 3;
+ tpi_arr[2].priv = NULL;
+ bitmap_set(tpi_arr[2].key, 22, 2); /* Set 3 on #3 byte */
+ bitmap_set(tpi_arr[2].key, 29, 1); /* Set 5 on #4 byte */
+ bitmap_set(tpi_arr[2].key, 31, 1); /* Set 5 on #4 byte */
+
+ /* Create item3 x.2.x.x.x prio 10 */
+ tpi_arr[3].priority = 10;
+ tpi_arr[3].priv = NULL;
+ bitmap_set(tpi_arr[3].key, 14, 1); /* Set 2 on #2 byte */
+
+ /* Create item4 x.x.x.x.6 prio 7 */
+ tpi_arr[4].priority = 7;
+ tpi_arr[4].priv = NULL;
+ bitmap_set(tpi_arr[4].key, 37, 2); /* Set 6 on #5 byte */
+
+ /* Create item5 2.2.3.x.x prio 5 */
+ tpi_arr[5].priority = 5;
+ tpi_arr[5].priv = NULL;
+ bitmap_set(tpi_arr[5].key, 7, 1); /* Set 2 on #1 byte */
+ bitmap_set(tpi_arr[5].key, 14, 1); /* Set 2 on #2 byte */
+ bitmap_set(tpi_arr[5].key, 22, 2); /* Set 3 on #3 byte */
+
+ table_arr[0] = prune_table_create(prune, table_attr[0].mask,
+ table_attr[0].mask_len,
+ (int *)(uintptr_t)table_attr[0].table_id);
+ if (IS_ERR(table_arr[0]))
+ return PTR_ERR(table_arr[0]);
+
+ item_arr[0] = prune_item_create(prune, table_arr[0],
+ tpi_arr[0].priority,
+ tpi_arr[0].key, tpi_arr[0].priv,
+ &tpi_arr[0].non_def_prune_vector);
+ if (IS_ERR(item_arr[0]))
+ return -EBADE;
+ /* default prune vector */
+ if (!test_prune_check_prune_vector(item_arr[0], NULL, 0,
+ tpi_arr[0].non_def_prune_vector))
+ return -EBADE;
+
+ table_arr[1] = prune_table_create(prune, table_attr[1].mask,
+ table_attr[1].mask_len,
+ (int *)(uintptr_t)table_attr[1].table_id);
+ if (IS_ERR(table_arr[1]))
+ return PTR_ERR(table_arr[1]);
+
+ item_arr[1] = prune_item_create(prune, table_arr[1],
+ tpi_arr[1].priority,
+ tpi_arr[1].key, tpi_arr[1].priv,
+ &tpi_arr[1].non_def_prune_vector);
+ if (IS_ERR(item_arr[1]))
+ return -EBADE;
+ /* default prune vector */
+ if (!test_prune_check_prune_vector(item_arr[1], NULL, 0,
+ tpi_arr[1].non_def_prune_vector))
+ return -EBADE;
+
+ item_arr[2] = prune_item_create(prune, table_arr[0],
+ tpi_arr[2].priority,
+ tpi_arr[2].key, tpi_arr[2].priv,
+ &tpi_arr[2].non_def_prune_vector);
+ if (IS_ERR(item_arr[2]))
+ return -EBADE;
+ /* default prune vector */
+ if (!test_prune_check_prune_vector(item_arr[2], NULL, 0,
+ tpi_arr[2].non_def_prune_vector))
+ return -EBADE;
+
+ table_arr[2] = prune_table_create(prune, table_attr[2].mask,
+ table_attr[2].mask_len,
+ (int *)(uintptr_t)table_attr[2].table_id);
+ if (IS_ERR(table_arr[2]))
+ return PTR_ERR(table_arr[2]);
+
+ item_arr[3] = prune_item_create(prune, table_arr[2],
+ tpi_arr[3].priority,
+ tpi_arr[3].key, tpi_arr[3].priv,
+ &tpi_arr[3].non_def_prune_vector);
+ if (IS_ERR(item_arr[3]))
+ return -EBADE;
+ /* default prune vector */
+ if (!test_prune_check_prune_vector(item_arr[3], prune_val_arr_3, 3,
+ tpi_arr[3].non_def_prune_vector))
+ return -EBADE;
+
+ item_arr[4] = prune_item_create(prune, table_arr[0],
+ tpi_arr[4].priority,
+ tpi_arr[4].key, tpi_arr[4].priv,
+ &tpi_arr[4].non_def_prune_vector);
+ if (IS_ERR(item_arr[4]))
+ return -EBADE;
+ /* default prune vector */
+ if (!test_prune_check_prune_vector(item_arr[4], NULL, 0,
+ tpi_arr[4].non_def_prune_vector))
+ return -EBADE;
+
+ item_arr[5] = prune_item_create(prune, table_arr[1],
+ tpi_arr[5].priority,
+ tpi_arr[5].key, tpi_arr[5].priv,
+ &tpi_arr[5].non_def_prune_vector);
+ if (IS_ERR(item_arr[5]))
+ return -EBADE;
+ /* default prune vector */
+ if (!test_prune_check_prune_vector(item_arr[5], prune_val_arr_5, 3,
+ &tpi_arr[5].non_def_prune_vector))
+ return -EBADE;
+
+ /* Free resources */
+ err = prune_item_destroy(item_arr[0]);
+ if (err)
+ return err;
+
+ err = prune_item_destroy(item_arr[1]);
+ if (err)
+ return err;
+
+ err = prune_item_destroy(item_arr[2]);
+ if (err)
+ return err;
+
+ err = prune_item_destroy(item_arr[3]);
+ if (err)
+ return err;
+
+ err = prune_table_destroy(table_arr[2]);
+ if (err)
+ return err;
+
+ err = prune_item_destroy(item_arr[4]);
+ if (err)
+ return err;
+
+ err = prune_table_destroy(table_arr[0]);
+ if (err)
+ return err;
+
+ err = prune_item_destroy(item_arr[5]);
+ if (err)
+ return err;
+
+ err = prune_table_destroy(table_arr[1]);
+ if (err)
+ return err;
+
+ prune_destroy(prune);
+
+ prune_item_arr_destroy(tpi_arr, ITEMS_6);
+ table_attr_destroy(table_attr, TABLES_3);
+
+ return 0;
+}
+
+static int test_prune_add_new_table_with_item_subsequent_to_curr_tables(void)
+{
+ struct test_prune_table_attr table_attr[TABLES_3];
+ struct prune_table *table_arr[TABLES_3];
+ struct test_prune_item tpi_arr[ITEMS_8];
+ struct prune_item *item_arr[ITEMS_8];
+ bool prune_val_arr_5[2] = {false, true};
+ unsigned int nbits = 40;
+ struct prune *prune;
+ 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, TABLES_3);
+ if (err)
+ return err;
+
+ err = test_prune_item_arr_create(tpi_arr, ITEMS_8, 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].mask,
+ table_attr[0].mask_len,
+ (int *)(uintptr_t)table_attr[0].table_id);
+ 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].mask,
+ table_attr[1].mask_len,
+ (int *)(uintptr_t)table_attr[1].table_id);
+ if (IS_ERR(table_arr[1]))
+ return PTR_ERR(table_arr[1]);
+
+ /* Create rules */
+ /* Create item0 1.2.3.x.x prio 10 */
+ tpi_arr[0].priority = 10;
+ tpi_arr[0].priv = NULL;
+ bitmap_set(tpi_arr[0].key, 7, 1); /* Set 1 on #1 byte */
+ bitmap_set(tpi_arr[0].key, 14, 1); /* Set 2 on #2 byte */
+ bitmap_set(tpi_arr[0].key, 22, 2); /* Set 3 on #3 byte */
+
+ /* Create item1 x.2.3.4.x prio 3 */
+ tpi_arr[1].priority = 3;
+ tpi_arr[1].priv = NULL;
+ bitmap_set(tpi_arr[1].key, 14, 1); /* Set 2 on #2 byte */
+ bitmap_set(tpi_arr[1].key, 22, 2); /* Set 3 on #3 byte */
+ bitmap_set(tpi_arr[1].key, 29, 1); /* Set 4 on #4 byte */
+
+ /* Create item2 x.x.3.9.9 prio 1 */
+ tpi_arr[2].priority = 1;
+ tpi_arr[2].priv = NULL;
+ bitmap_set(tpi_arr[2].key, 22, 2); /* Set 3 on #3 byte */
+ bitmap_set(tpi_arr[2].key, 28, 1); /* Set 9 on #4 byte */
+ bitmap_set(tpi_arr[2].key, 31, 1); /* Set 9 on #4 byte */
+ bitmap_set(tpi_arr[2].key, 36, 1); /* Set 9 on #5 byte */
+ bitmap_set(tpi_arr[2].key, 39, 1); /* Set 9 on #5 byte */
+
+ /* Create item3 2.2.4.x.x prio 5 */
+ tpi_arr[3].priority = 5;
+ tpi_arr[3].priv = NULL;
+ bitmap_set(tpi_arr[3].key, 6, 1); /* Set 2 on #1 byte */
+ bitmap_set(tpi_arr[3].key, 14, 1); /* Set 2 on #2 byte */
+ bitmap_set(tpi_arr[3].key, 21, 1); /* Set 4 on #3 byte */
+
+ /* Create item4 x.x.4.5.x prio 2 */
+ tpi_arr[4].priority = 2;
+ tpi_arr[4].priv = NULL;
+ bitmap_set(tpi_arr[4].key, 21, 1); /* Set 4 on #3 byte */
+ bitmap_set(tpi_arr[4].key, 29, 1); /* Set 5 on #4 byte */
+ bitmap_set(tpi_arr[4].key, 31, 1); /* Set 5 on #4 byte */
+
+ /* Create item5 x.2.4.7.x prio 8 */
+ tpi_arr[5].priority = 8;
+ tpi_arr[5].priv = NULL;
+ bitmap_set(tpi_arr[5].key, 14, 1); /* Set 2 on #2 byte */
+ bitmap_set(tpi_arr[5].key, 21, 1); /* Set 4 on #3 byte */
+ bitmap_set(tpi_arr[5].key, 29, 3); /* Set 7 on #4 byte */
+
+ /* Create item6 x.2.x.9.x prio 8 */
+ tpi_arr[6].priority = 8;
+ tpi_arr[6].priv = NULL;
+ bitmap_set(tpi_arr[6].key, 14, 1); /* Set 2 on #2 byte */
+ bitmap_set(tpi_arr[6].key, 28, 1); /* Set 9 on #4 byte */
+ bitmap_set(tpi_arr[6].key, 31, 1); /* Set 9 on #4 byte */
+
+ item_arr[0] = prune_item_create(prune, table_arr[0],
+ tpi_arr[0].priority,
+ tpi_arr[0].key, tpi_arr[0].priv,
+ &tpi_arr[0].non_def_prune_vector);
+ if (IS_ERR(item_arr[0]))
+ return -EBADE;
+ /* default prune vector */
+ if (!test_prune_check_prune_vector(item_arr[0], NULL, 0,
+ tpi_arr[0].non_def_prune_vector))
+ return -EBADE;
+
+ item_arr[1] = prune_item_create(prune, table_arr[1],
+ tpi_arr[1].priority,
+ tpi_arr[1].key, tpi_arr[1].priv,
+ &tpi_arr[1].non_def_prune_vector);
+ if (IS_ERR(item_arr[1]))
+ return -EBADE;
+ /* default prune vector */
+ if (!test_prune_check_prune_vector(item_arr[1], NULL, 0,
+ tpi_arr[1].non_def_prune_vector))
+ return -EBADE;
+
+ item_arr[3] = prune_item_create(prune, table_arr[0],
+ tpi_arr[3].priority,
+ tpi_arr[3].key, tpi_arr[3].priv,
+ &tpi_arr[3].non_def_prune_vector);
+ if (IS_ERR(item_arr[3]))
+ return -EBADE;
+ /* default prune vector */
+ if (!test_prune_check_prune_vector(item_arr[3], NULL, 0,
+ tpi_arr[3].non_def_prune_vector))
+ return -EBADE;
+
+ item_arr[5] = prune_item_create(prune, table_arr[1],
+ tpi_arr[5].priority,
+ tpi_arr[5].key, tpi_arr[5].priv,
+ &tpi_arr[5].non_def_prune_vector);
+ if (IS_ERR(item_arr[5]))
+ return -EBADE;
+
+ if (!test_prune_check_prune_vector(item_arr[5], prune_val_arr_5, 2,
+ tpi_arr[5].non_def_prune_vector))
+ return -EBADE;
+
+ item_arr[6] = prune_item_create(prune, table_arr[1],
+ tpi_arr[6].priority,
+ tpi_arr[6].key, tpi_arr[6].priv,
+ &tpi_arr[6].non_def_prune_vector);
+ if (IS_ERR(item_arr[6]))
+ return -EBADE;
+ /* default prune vector */
+ if (!test_prune_check_prune_vector(item_arr[6], NULL, 0,
+ tpi_arr[6].non_def_prune_vector))
+ 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].mask,
+ table_attr[2].mask_len,
+ (int *)(uintptr_t)table_attr[2].table_id);
+ if (IS_ERR(table_arr[2]))
+ return PTR_ERR(table_arr[2]);
+
+ item_arr[2] = prune_item_create(prune, table_arr[2],
+ tpi_arr[2].priority,
+ tpi_arr[2].key, tpi_arr[2].priv,
+ &tpi_arr[2].non_def_prune_vector);
+ if (IS_ERR(item_arr[2]))
+ return -EBADE;
+ /* default prune vector */
+ if (!test_prune_check_prune_vector(item_arr[2], NULL, 0,
+ tpi_arr[2].non_def_prune_vector))
+ return -EBADE;
+
+ item_arr[4] = prune_item_create(prune, table_arr[2],
+ tpi_arr[4].priority,
+ tpi_arr[4].key, tpi_arr[4].priv,
+ &tpi_arr[4].non_def_prune_vector);
+ if (IS_ERR(item_arr[4]))
+ return -EBADE;
+ /* default prune vector */
+ if (!test_prune_check_prune_vector(item_arr[4], NULL, 0,
+ tpi_arr[4].non_def_prune_vector))
+ return -EBADE;
+
+ err = prune_item_destroy(item_arr[0]);
+ if (err)
+ return err;
+
+ err = prune_item_destroy(item_arr[1]);
+ if (err)
+ return err;
+
+ err = prune_item_destroy(item_arr[2]);
+ if (err)
+ return err;
+
+ err = prune_item_destroy(item_arr[3]);
+ if (err)
+ return err;
+
+ err = prune_item_destroy(item_arr[4]);
+ if (err)
+ return err;
+
+ err = prune_table_destroy(table_arr[2]);
+ if (err)
+ return err;
+
+ err = prune_item_destroy(item_arr[5]);
+ if (err)
+ return err;
+
+ err = prune_item_destroy(item_arr[6]);
+ if (err)
+ return err;
+
+ err = prune_table_destroy(table_arr[0]);
+ if (err)
+ return err;
+
+ err = prune_table_destroy(table_arr[1]);
+ if (err)
+ return err;
+
+ prune_destroy(prune);
+
+ prune_item_arr_destroy(tpi_arr, ITEMS_8);
+ table_attr_destroy(table_attr, TABLES_3);
+
+ 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");
An object (e.g. packet) needs to be evaluated against a data base of prune items (represented by {key, mask, priority}), so that the matching item with the highest priority is selected to continue processing the object. Items with different masks are stored in different tables. One way to find this item is to perform multiple (on all the tables) exact match lookups, each with a different mask. It is possible to reduce the number of lookups by pruning tables where we know that an higher priority match does not exist. The prune library aim: reduce number of lookups (by prune) between tables within same prune items set (The prune object). As mentioned above pruning saves time complexity by doing lookups only on the relevant tables, this eliminates the need to search for exact match in other tables based on item priority and mask. In order to achieve this goal the prune library: 1. Maintain a prune vector for each item. 2. Calculate the prune vector of an inserted item i to table x and the prune vector of an affected items by this rule. If there is a matching item j in other table z with lower priority item, item i set to prune table z (e.g. no need for further lookups). Since item j was pruning table x the prune library also calculate item j prune vector not to prune table x. 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> --- Documentation/00-INDEX | 2 + Documentation/prune.txt | 286 ++++++++++ MAINTAINERS | 8 + include/linux/prune.h | 76 +++ lib/Kconfig | 8 +- lib/Kconfig.debug | 10 + lib/Makefile | 3 + lib/prune.c | 1337 +++++++++++++++++++++++++++++++++++++++++++++++ lib/test_prune.c | 1215 ++++++++++++++++++++++++++++++++++++++++++ 9 files changed, 2944 insertions(+), 1 deletion(-) 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