@@ -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,445 @@
+=====
+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 intersects with
+ the mask of table z.
+
+Each intersection table consists of:
+
+- Hash table for intersecting entries
+- Each entry contain two lists:
+ - Items of the table owner (my items).
+ - 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
+
++------------------------------------+
+| table y: U.U.U.X.X |
++==========+==========+==============+
+|item key | priority | prune-vector |
++----------+----------+--------------+
+| | | |
++----------+----------+--------------+
+| | | |
++----------+----------+--------------+
+| | | |
++----------+----------+--------------+
+
+.. table
+
++------------------------------------+
+| table z: X.U.U.U.X |
++==========+==========+==============+
+|item key | priority | prune-vector |
++----------+----------+--------------+
+| | | |
++----------+----------+--------------+
+| | | |
++----------+----------+--------------+
+| | | |
++----------+----------+--------------+
+
+.. table
+
++----------------------------------+
+| intersection table y^z X.U.U.X.X |
++======+==========+================+
+|mask | my items | neighbor items |
++------+----------+----------------+
+| | | |
++------+----------+----------------+
+| | | |
++------+----------+----------------+
+| | | |
++------+----------+----------------+
+
+.. table
+
++----------------------------------+
+| intersection table z^y X.U.U.X.X |
++======+==========+================+
+| 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
+
++----------------------------------+
+| table y: U.U.U.X.X |
++=========+==========+=============+
+|item key | priority | prune-vector|
++---------+----------+-------------+
+| | | |
++---------+----------+-------------+
+| | | |
++---------+----------+-------------+
+| | | |
++---------+----------+-------------+
+
+.. table
+
++----------------------------------+
+| table z: X.U.U.U.X |
++=========+==========+=============+
+|item key | priority | prune-vector|
++---------+----------+-------------+
+|x.2.3.4.X| 10 | [z-1,y-1] |
++---------+----------+-------------+
+| | | |
++---------+----------+-------------+
+| | | |
++---------+----------+-------------+
+
+.. table
+
++-------------------------------------+
+|intersection table y^z X.U.U.X.X |
++=========+==========+================+
+|mask | my items |neighbor items |
++---------+----------+----------------+
+|X.2.3.X.X| | R-1 |
++---------+----------+----------------+
+| | | |
++---------+----------+----------------+
+| | | |
++---------+----------+----------------+
+
+.. table
+
++-------------------------------------+
+|intersection table z^y X.U.U.X.X |
++=========+==========+================+
+|mask | my items |neighbor items |
++---------+----------+----------------+
+|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
+
++----------------------------------+
+| table y: U.U.U.X.X |
++=========+==========+=============+
+|item key | priority | prune-vector|
++---------+----------+-------------+
+| | | |
++---------+----------+-------------+
+| | | |
++---------+----------+-------------+
+| | | |
++---------+----------+-------------+
+
+.. table
+
++----------------------------------+
+| table z: X.U.U.U.X |
++=========+==========+=============+
+|item key | priority | prune-vector|
++---------+----------+-------------+
+|x.2.3.4.X| 10 | [z-1,y-1] |
++---------+----------+-------------+
+|x.2.3.5.X| 5 | [z-1,y-1] |
++---------+----------+-------------+
+| | | |
++---------+----------+-------------+
+
+.. table
+
++-------------------------------------+
+|intersection table y^z X.U.U.X.X |
++=========+==========+================+
+|mask | my items |neighbor items |
++---------+----------+----------------+
+|X.2.3.X.X| | R-1, R-2 |
++---------+----------+----------------+
+| | | |
++---------+----------+----------------+
+| | | |
++---------+----------+----------------+
+
+.. table
+
++-------------------------------------+
+|intersection table z^y X.U.U.X.X |
++=========+==========+================+
+|mask | my items |neighbor items |
++---------+----------+----------------+
+|X.2.3.X.X| R-1, R-2 | |
++---------+----------+----------------+
+| | | |
++---------+----------+----------------+
+| | | |
++---------+----------+----------------+
+
+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
+
++----------------------------------+
+| table y: U.U.U.X.X |
++=========+==========+=============+
+|item key | priority | prune-vector|
++---------+----------+-------------+
+|1.2.3.X.X| 7 | [y-1,z-0] |
++---------+----------+-------------+
+| | | |
++---------+----------+-------------+
+| | | |
++---------+----------+-------------+
+
+.. table
+
++----------------------------------+
+| table z: X.U.U.U.X |
++=========+==========+=============+
+|item key | priority | prune-vector|
++---------+----------+-------------+
+|x.2.3.4.X| 10 | [z-1,y-0] |
++---------+----------+-------------+
+|x.2.3.5.X| 5 | [z-1,y-1] |
++---------+----------+-------------+
+| | | |
++---------+----------+-------------+
+
+.. table
+
++-------------------------------------+
+|intersection table y^z X.U.U.X.X |
++=========+==========+================+
+|mask | my items |neighbor items |
++---------+----------+----------------+
+|X.2.3.X.X| R-3 | R-1, R-2 |
++---------+----------+----------------+
+| | | |
++---------+----------+----------------+
+| | | |
++---------+----------+----------------+
+
+.. table
+
++-------------------------------------+
+|intersection table z^y X.U.U.X.X |
++=========+==========+================+
+|mask | my items |neighbor items |
++---------+----------+----------------+
+|X.2.3.X.X| R-1, R-2 | R-3 |
++---------+----------+----------------+
+| | | |
++---------+----------+----------------+
+| | | |
++---------+----------+----------------+
+
+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
+
++----------------------------------+
+| table y: U.U.U.X.X |
++=========+==========+=============+
+|item key | priority | prune-vector|
++---------+----------+-------------+
+|1.2.3.X.X| 7 | [y-1,z-1] |
++---------+----------+-------------+
+| | | |
++---------+----------+-------------+
+| | | |
++---------+----------+-------------+
+
+.. table
+
++----------------------------------+
+| table z: X.U.U.U.X |
++=========+==========+=============+
+|item key | priority | prune-vector|
++---------+----------+-------------+
+|x.2.3.4.X| 10 | [z-1,y-0] |
++---------+----------+-------------+
+| | | |
++---------+----------+-------------+
+| | | |
++---------+----------+-------------+
+
+.. table
+
++-------------------------------------+
+|intersection table y^z X.U.U.X.X |
++=========+==========+================+
+|mask | my items |neighbor items |
++---------+----------+----------------+
+|X.2.3.X.X| R-3 | R-1 |
++---------+----------+----------------+
+| | | |
++---------+----------+----------------+
+| | | |
++---------+----------+----------------+
+
+.. table
+
++-------------------------------------+
+|intersection table z^y X.U.U.X.X |
++=========+==========+================+
+|mask | my items |neighbor items |
++---------+----------+----------------+
+|X.2.3.X.X| R-1 | R-3 |
++---------+----------+----------------+
+| | | |
++---------+----------+----------------+
+| | | |
++---------+----------+----------------+
+
+Flows
+-----
+Direction of Prune Calculation:
+~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
+R->R: Calculate my own prune vector
+R->K: Calculate other items (K) prune vector in the prune object
+
+Insert item 'R'
+~~~~~~~~~~~~~~~~
+- R->R: Insert an item 'R' to a table, calculate its own prune-vector.
+- R->K: 'R' is inserted to a table, and we have to calculate the prune-vectors of other compatible items (in different tables).
+
+Removing item 'R'
+~~~~~~~~~~~~~~~~~~
+- R->K: '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.
@@ -11504,6 +11504,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,83 @@
+/* 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.
+ */
+
+#ifndef _PRUNE_H
+#define _PRUNE_H
+
+struct prune_table;
+struct prune;
+
+/**
+ * struct prune_item - holds the configured item settings.
+ * @key: Pointer to bitmap.
+ * @priv: Pointer to user data.
+ * @table: Table which the item belongs to.
+ * @list: A node in prune_item_notify_list.
+ * @priority: Lower number means higher priority.
+ *
+ * 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;
+ void *priv;
+ struct prune_table *table;
+ struct list_head list;
+ unsigned int priority;
+};
+
+/**
+ * struct prune_vector_item - Define if a table should be prune or not.
+ * @table: The table which should be pruned.
+ * @list: Node in the item prune vector.
+ * @pruned: True if the item is pruning this table.
+ *
+ * This structure used as a node of the item prune_vector.
+ */
+struct prune_vector_item {
+ struct prune_table *table;
+ struct list_head list;
+ bool pruned;
+};
+
+/**
+ * struct prune_ops - Define the management hooks for prune object.
+ *
+ * @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.prune_item_notify_list: A list of prune_item structs
+ * (read-only)which their pruned
+ * vector has been changed with
+ * {table,pruned} attributes below.
+ * @prune_item_notify.table: The table which should be pruned.
+ * @prune_item_notify.pruned: True if the item prune the table.
+ *
+ * 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"
@@ -1844,6 +1844,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
@@ -70,6 +70,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
@@ -251,6 +252,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,1445 @@
+// 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.
+ */
+
+#include <linux/kernel.h>
+#include <linux/module.h>
+#include <linux/slab.h>
+#include <linux/export.h>
+#include <linux/list.h>
+#include <linux/rhashtable.h>
+#include <linux/prune.h>
+#include <linux/jhash.h>
+#include <linux/bitmap.h>
+
+/*
+ * struct prune_table_entry - hold the item configuration and its prune vector.
+ * @prune_vector: List of struct prune_vector_item.
+ * @list: Node in table's entry list.
+ * @item: The item returned to the library user.
+ */
+struct prune_table_entry {
+ struct list_head prune_vector;
+ struct list_head list;
+ struct prune_item item;
+};
+
+/*
+ * struct prune_intersec_table_list_elem - An element in intersec_table_elem_list
+ * or neigh_table_elem_list.
+ * @entry: A pointer to an entry in the prune table.
+ * @list: A node in the corresponding list {intersec_, neigh_}table_elem_list.
+ *
+ * This element is used to reference prune entries from the intersection table.
+ */
+struct prune_intersec_table_list_elem {
+ struct prune_table_entry *entry;
+ struct list_head list;
+};
+
+/*
+ * struct prune_intersec_table - Represent the intersection of two prune tables.
+ * @entry_ht: Hash-table of prune_intersec_table_entry.
+ * @neigh_table: A pointer to the table which this table intersects.
+ * @list: Node of table's intersec_table_list.
+ * @mask: Intersection mask of the the two tables.
+ *
+ * This structure is used to find the intersection of new prune item with an
+ * existing one, and check whether the new item should be pruned or not.
+ */
+struct prune_intersec_table {
+ struct rhashtable entry_ht;
+ struct prune_table *neigh_table;
+ struct list_head list;
+ unsigned long mask[0];
+ /* mask has to be always the last item */
+};
+
+/*
+ * struct prune_intersec_table_entry - Represents an entry in intersection
+ * table.
+ * @ht_node: A node in the hash-table of the intersection
+ * table.
+ * @ht_key: The key used for the entry in the hash-table.
+ * created by the intersection of two prune items
+ * keys.
+ * @intersec_table: A pointer to the intersection table which owns
+ * this entry.
+ * @intersec_table_elem_list: Contain pointers of entries in prune table which
+ * the intersection table of this entry belongs to.
+ * @neigh_table_elem_list: Contain list of entries in the neighbor table
+ * pointed by the neigh_table field in
+ * prune_intersec_table struct.
+ *
+ * The structure is used to find the intersection of new prune item with the
+ * current one, and check whether 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;
+};
+
+/*
+ * struct prune_table - Contains the prune items added by the user.
+ * @prune: A pointer to prune object which hold the table.
+ * @priv: User data.
+ * @entry_list: A list of prune_table_entry.
+ * @intersec_table_list: List of intersection tables of this table with the
+ * other tables in the prune object.
+ * @list: Node of table_list in struct prune.
+ * @mask: The mask given b the user.
+ *
+ * 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;
+ struct list_head intersec_table_list;
+ struct list_head list;
+ unsigned long mask[0];
+ /* mask has to be always the last item */
+};
+
+/*
+ * struct prune - Represents the prune object.
+ * @ops: the operations that this prune object support.
+ * @intersec_tables_ht_params: hold hash table attributes of the intersection
+ * table.
+ * @table_list: A list of prune table fo this prune object.
+ * @priv: User data.
+ * @mask_len: The mask len in bits which this prune object
+ * support.
+ */
+struct prune {
+ const struct prune_ops *ops;
+ struct rhashtable_params intersec_tables_ht_params;
+ struct list_head table_list;
+ void *priv;
+ unsigned int mask_len;
+};
+
+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;
+ unsigned int key_len;
+
+ key_len = prune_intersec_table_entry_key_len(intersec_entry);
+
+ return !bitmap_equal(*ht_key, intersec_entry->ht_key, key_len);
+}
+
+static struct rhashtable_params intersec_tables_ht_params = {
+ .key_offset = offsetof(struct prune_intersec_table_entry, ht_key),
+ .head_offset = offsetof(struct prune_intersec_table_entry, ht_node),
+ .obj_cmpfn = prune_intersec_ht_cmp,
+ .hashfn = prune_intersec_ht_hash,
+ .automatic_shrinking = true,
+};
+
+static void prune_table_prune_vector_fini(struct prune_table_entry *entry);
+
+static int prune_table_prune_vector_init(struct prune *prune,
+ struct prune_table_entry *entry)
+{
+ struct prune_table *table;
+
+ INIT_LIST_HEAD(&entry->prune_vector);
+
+ list_for_each_entry(table, &prune->table_list, list) {
+ struct prune_vector_item *vector_item;
+
+ vector_item = kmalloc(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->prune_vector);
+ }
+ return 0;
+}
+
+static void prune_table_prune_vector_fini(struct prune_table_entry *entry)
+{
+ struct list_head *pos, *tmp;
+
+ list_for_each_safe(pos, tmp, &entry->prune_vector) {
+ struct prune_vector_item *vector_item;
+
+ vector_item = list_entry(pos, typeof(*vector_item), list);
+ list_del(&vector_item->list);
+ kfree(vector_item);
+ }
+}
+
+static struct prune_table_entry *
+prune_table_entry_init(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_table_entry_fini(struct prune_table_entry *entry)
+{
+ prune_table_prune_vector_fini(entry);
+ 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->prune_vector : &intersec_item->entry->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;
+
+ list_for_each_safe(pos, tmp, prune_item_notify_list) {
+ struct prune_item *item;
+
+ item = list_entry(pos, typeof(*item), list);
+ list_del(&item->list);
+ }
+}
+
+static 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
+ * @prune_item_notify_list: The notification list which will returned due to
+ * changes in other items in the prune object
+ *
+ * Return: True if the item prune vector has changed.
+ */
+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_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) {
+ struct prune_intersec_table_list_elem *neigh_item;
+ /* 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 {
+ struct prune_intersec_table_list_elem *intersec_item;
+ /* 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
+ * @prune_item_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;
+
+ 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
+ */
+ bool notify = false;
+
+ if (!prune_neigh_list_item_lower_prio(table, intersec_item,
+ intersec_entry)) {
+ const struct list_head *prune_list;
+ /* Update intersec_item prune vector for the
+ * corresponding table to prune due to delete flow
+ */
+ prune_list = &intersec_item->entry->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_table_entry_init(prune, key, priority, priv);
+ if (!entry)
+ return ERR_PTR(-ENOMEM);
+
+ err = prune_item_add_prune_vector_set(table, entry, notify);
+ if (err) {
+ prune_table_entry_fini(entry);
+ return ERR_PTR(err);
+ }
+ list_add_tail(&entry->list, &table->entry_list);
+ entry->item.table = table;
+
+ return entry;
+}
+
+static void prune_table_entry_destroy(struct prune_table_entry *entry)
+{
+ list_del(&entry->list);
+ prune_table_entry_fini(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_ht_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_ht_key_alloc:
+ kfree(intersec_entry);
+err_entry_alloc:
+ return ERR_PTR(-ENOMEM);
+}
+
+static void
+prune_intersec_entry_destroy(struct prune_intersec_table_entry *intersec_entry)
+{
+ WARN_ON(!list_empty(&intersec_entry->intersec_table_elem_list));
+ WARN_ON(!list_empty(&intersec_entry->neigh_table_elem_list));
+
+ kfree(intersec_entry);
+}
+
+static struct prune_intersec_table_list_elem *
+prune_intersec_item_create(struct prune_table_entry *entry,
+ struct prune_intersec_table_entry *intersec_entry,
+ bool neigh)
+{
+ struct prune_intersec_table_list_elem *intersec_item;
+
+ intersec_item = kmalloc(sizeof(*intersec_item), GFP_KERNEL);
+ if (!intersec_item)
+ return ERR_PTR(-ENOMEM);
+
+ intersec_item->entry = entry;
+ if (!neigh)
+ list_add_tail(&intersec_item->list,
+ &intersec_entry->intersec_table_elem_list);
+ else
+ list_add_tail(&intersec_item->list,
+ &intersec_entry->neigh_table_elem_list);
+
+ return intersec_item;
+}
+
+static void
+prune_intersec_item_destroy(struct prune_intersec_table_list_elem *intersec_item)
+{
+ list_del(&intersec_item->list);
+ kfree(intersec_item);
+}
+
+static int prune_intersec_item_add(struct prune_intersec_table *intersec_table,
+ struct prune_table_entry *entry,
+ bool neigh)
+{
+ unsigned int mask_len = entry->item.table->prune->mask_len;
+ struct prune_intersec_table_list_elem *intersec_item;
+ 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;
+ }
+ intersec_item = prune_intersec_item_create(entry, intersec_entry, neigh);
+ if (IS_ERR(intersec_item))
+ goto err_prune_intersec_item_create;
+
+ 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:
+ prune_intersec_item_destroy(intersec_item);
+err_prune_intersec_item_create:
+ if (!found)
+ prune_intersec_entry_destroy(intersec_entry);
+err_entry_alloc:
+ return err;
+}
+
+static int
+prune_intersec_item_del(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_entry *intersec_entry;
+ struct rhashtable_params rht_params;
+ struct list_head *pos, *tmp;
+ unsigned long *ht_key;
+
+ 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) {
+ struct prune_intersec_table_list_elem *intersec_item;
+
+ intersec_item = list_entry(pos, typeof(*intersec_item),
+ list);
+ if (intersec_item->entry == remove_entry) {
+ prune_intersec_item_destroy(intersec_item);
+ break;
+ }
+ }
+ } else {
+ list_for_each_safe(pos, tmp,
+ &intersec_entry->neigh_table_elem_list) {
+ struct prune_intersec_table_list_elem *neigh_item;
+
+ neigh_item = list_entry(pos, typeof(*neigh_item), list);
+ if (remove_entry == neigh_item->entry) {
+ prune_intersec_item_destroy(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_intersec_table_create(struct prune *prune,
+ struct prune_table *neigh_table,
+ struct prune_table *table)
+{
+ struct prune_intersec_table *intersec_table;
+ unsigned int mask_len = prune->mask_len;
+ int err;
+
+ intersec_table = kmalloc(sizeof(*intersec_table) + prune_mask_size(mask_len),
+ GFP_KERNEL);
+ if (!intersec_table)
+ return NULL;
+
+ bitmap_and(intersec_table->mask, neigh_table->mask, table->mask,
+ prune->mask_len);
+ intersec_table->neigh_table = neigh_table;
+
+ err = rhashtable_init(&intersec_table->entry_ht,
+ &prune->intersec_tables_ht_params);
+ if (err)
+ goto err_rhashtable_init;
+
+ list_add(&intersec_table->list, &table->intersec_table_list);
+
+ return intersec_table;
+
+err_rhashtable_init:
+ kfree(intersec_table);
+ return NULL;
+}
+
+static void prune_intersec_rht_free(void *ptr, void *arg)
+{
+ 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) {
+ struct prune_intersec_table_list_elem *intersec_item;
+
+ intersec_item = list_entry(pos, typeof(*intersec_item), list);
+ prune_intersec_item_destroy(intersec_item);
+ }
+ list_for_each_safe(pos, tmp, &rht_node->neigh_table_elem_list) {
+ struct prune_intersec_table_list_elem *neigh_item;
+
+ neigh_item = list_entry(pos, typeof(*neigh_item), list);
+ prune_intersec_item_destroy(neigh_item);
+ }
+ kfree(rht_node->ht_key);
+ kfree(rht_node);
+}
+
+static void
+prune_intersec_table_destroy(struct prune_intersec_table *intersec_table)
+{
+ rhashtable_free_and_destroy(&intersec_table->entry_ht,
+ prune_intersec_rht_free,
+ NULL);
+ list_del(&intersec_table->list);
+ kfree(intersec_table);
+}
+
+/*
+ * prune_intersec_table_items_commit - Update the item of the current table to
+ * the neighbor items in the intersection
+ * table
+ * @table: The table which its items needs to be updated in the
+ * intersection table
+ * @intersec_table: The intersection table which needs to be updated
+ * @add_to_neigh_items: True if items need to be add to neigh_table_elem_list
+ */
+static int prune_intersec_table_items_commit(struct prune_table *table,
+ struct prune_intersec_table *intersec_table,
+ bool add_to_neigh_items)
+{
+ struct prune_table_entry *entry;
+ int err;
+
+ list_for_each_entry(entry, &table->entry_list, list) {
+ err = prune_intersec_item_add(intersec_table, entry,
+ add_to_neigh_items);
+ if (err)
+ goto err_prune_intersec_item_add;
+ }
+ return 0;
+
+err_prune_intersec_item_add:
+ list_for_each_entry_continue_reverse(entry, &table->entry_list, list) {
+ prune_intersec_item_del(intersec_table, entry,
+ add_to_neigh_items);
+ }
+ return err;
+}
+
+static int prune_intersec_table_items_revert(struct prune_table *table,
+ struct prune_intersec_table *intersec_table,
+ bool del_from_neigh_items)
+{
+ struct prune_table_entry *entry;
+ int err;
+
+ list_for_each_entry(entry, &table->entry_list, list) {
+ err = prune_intersec_item_del(intersec_table, entry,
+ del_from_neigh_items);
+ if (err)
+ return err;
+ }
+ return 0;
+}
+
+static int prune_intersec_table_add(struct prune *prune,
+ struct prune_table *new_table,
+ struct prune_table *table)
+{
+ struct prune_intersec_table *intersec_table_old;
+ struct prune_intersec_table *intersec_table_new;
+ int err = 0;
+
+ intersec_table_old = prune_intersec_table_create(prune, new_table,
+ table);
+ if (!intersec_table_old)
+ goto err_allocate_intersec_table_old;
+
+ intersec_table_new = prune_intersec_table_create(prune, table,
+ new_table);
+ if (!intersec_table_new)
+ goto err_allocate_intersec_table_new;
+
+ err = prune_intersec_table_items_commit(table, intersec_table_old,
+ false);
+ if (err)
+ goto err_prune_intersec_table_items_commit_old;
+
+ err = prune_intersec_table_items_commit(table, intersec_table_new,
+ true);
+ if (err)
+ goto err_prune_intersec_table_items_commit_new;
+ return 0;
+
+err_prune_intersec_table_items_commit_new:
+ if (prune_intersec_table_items_revert(table, intersec_table_old, false))
+ WARN_ON(1);
+err_prune_intersec_table_items_commit_old:
+ prune_intersec_table_destroy(intersec_table_new);
+err_allocate_intersec_table_new:
+ prune_intersec_table_destroy(intersec_table_old);
+err_allocate_intersec_table_old:
+ return err ? err : -ENOMEM;
+}
+
+static int prune_intersec_table_fini(struct prune_table *table);
+
+/*
+ * prune_intersec_table_init - Add new intersection table to all tables and
+ * initialize it.
+ * @prune: The prune object which the intersection should be part of
+ * object.
+ * @new_table:
+ *
+ * Return: 0 in case of success, negative number to indicate an error.
+ */
+static int prune_intersec_table_init(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_intersec_table_add(prune, new_table, table);
+ if (err)
+ goto err_prune_intersec_table_add;
+ }
+ return 0;
+
+err_prune_intersec_table_add:
+ list_for_each_entry_continue_reverse(table, &prune->table_list, list)
+ prune_intersec_table_fini(table);
+
+ return err;
+}
+
+static int prune_intersec_table_del(unsigned int mask_len,
+ struct prune_table *table,
+ struct prune_table *table_removed)
+{
+ struct list_head *intersec_pos, *tmp;
+ 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) {
+ struct prune_intersec_table *intersec_table;
+
+ intersec_table = list_entry(intersec_pos,
+ typeof(*intersec_table),
+ list);
+ if (bitmap_equal(curr_mask, intersec_table->mask,
+ mask_len)) {
+ prune_intersec_table_destroy(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_fini(struct prune_table *table)
+{
+ struct prune_table *curr_table;
+ struct list_head *pos, *tmp;
+ int err;
+
+ /* Remove the intersection table from neighbor tables */
+ list_for_each_entry(curr_table, &table->prune->table_list, list) {
+ if (curr_table != table) {
+ err = prune_intersec_table_del(table->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) {
+ struct prune_intersec_table *intersec_table;
+
+ intersec_table = list_entry(pos, typeof(*intersec_table),
+ list);
+ prune_intersec_table_destroy(intersec_table);
+ }
+ WARN_ON_ONCE(!list_empty(&table->intersec_table_list));
+
+ 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 *intersec_table;
+ int err;
+
+ list_for_each_entry(intersec_table, &table->intersec_table_list,
+ list) {
+ /* Add the item only to the corresponding tables */
+ if (!neigh_item ||
+ intersec_table->neigh_table == item_added_table) {
+ err = prune_intersec_item_add(intersec_table,
+ entry,
+ neigh_item);
+ if (err)
+ return err;
+ }
+ }
+ return 0;
+}
+
+static int
+prune_intersec_list_item_del(struct prune_table *remove_item_table,
+ struct prune_table *table,
+ struct prune_table_entry *remove_entry,
+ bool neigh_item)
+{
+ struct prune_intersec_table *intersec_table;
+ int err;
+
+ list_for_each_entry(intersec_table, &table->intersec_table_list,
+ list) {
+ if (intersec_table->neigh_table == remove_item_table ||
+ !neigh_item) {
+ err = prune_intersec_item_del(intersec_table,
+ remove_entry,
+ neigh_item);
+ if (err)
+ return err;
+ }
+ }
+ return 0;
+}
+
+static void prune_table_item_vector_del(struct prune_table *table,
+ struct prune_table *del_table);
+
+static int prune_table_item_vector_add(struct prune_table *table,
+ struct prune_table *new_table)
+{
+ struct prune_table_entry *entry;
+
+ list_for_each_entry(entry, &table->entry_list, list) {
+ struct prune_vector_item *vector_item;
+
+ vector_item = kmalloc(sizeof(*vector_item), GFP_KERNEL);
+ if (!vector_item) {
+ prune_table_item_vector_del(table, new_table);
+ return -ENOMEM;
+ }
+ vector_item->pruned = true;
+ vector_item->table = new_table;
+ list_add_tail(&vector_item->list, &entry->prune_vector);
+ }
+ return 0;
+}
+
+static void prune_table_item_vector_del(struct prune_table *table,
+ struct prune_table *del_table)
+{
+ struct prune_table_entry *entry;
+
+ list_for_each_entry(entry, &table->entry_list, list) {
+ struct list_head *pos, *tmp;
+
+ list_for_each_safe(pos, tmp, &entry->prune_vector) {
+ struct prune_vector_item *vector_item;
+
+ vector_item = list_entry(pos, typeof(*vector_item),
+ list);
+ if (vector_item->table == del_table) {
+ list_del(&vector_item->list);
+ kfree(vector_item);
+ break;
+ }
+ }
+ }
+}
+
+/*
+ * prune_item_prune_table_add - Add new vector_item to each entry 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_del - Delete vector_item from each entry in each table
+ * @prune: The prune object which contains all tables
+ * @del_table: The table which needs to be deleted from the vector_item
+ */
+static void prune_item_prune_table_del(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_del(table, del_table);
+ }
+}
+
+static void
+prune_intersec_tables_ht_params_init(struct prune *prune, unsigned int mask_len)
+{
+ memcpy(&prune->intersec_tables_ht_params, &intersec_tables_ht_params,
+ sizeof(intersec_tables_ht_params));
+ prune->intersec_tables_ht_params.key_len = mask_len;
+}
+
+static struct prune_table *prune_table_init(struct prune *prune,
+ unsigned long *mask, void *priv)
+{
+ struct prune_table *table;
+
+ table = kmalloc(sizeof(*table) + prune_mask_size(prune->mask_len),
+ GFP_KERNEL);
+ if (!table)
+ return ERR_PTR(-ENOMEM);
+
+ 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);
+
+ return table;
+}
+
+static void prune_table_fini(struct prune_table *table)
+{
+ WARN_ON(!list_empty(&table->entry_list));
+ WARN_ON(!list_empty(&table->intersec_table_list));
+
+ kfree(table);
+}
+
+/**
+ * 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.
+ *
+ * Return: 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 = kmalloc(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 - Creates a new table 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.
+ *
+ * Return: A pointer to newly created prune table instance in case of success,
+ * otherwise it returns pointer to an error.
+ *
+ * Note: It's the user responsibility to care of synchronization.
+ */
+
+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 = prune_table_init(prune, mask, priv);
+ if (IS_ERR(table))
+ return table;
+
+ /* 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_init(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_del(prune, table);
+err_table_add:
+ kfree(table);
+ return ERR_PTR(err);
+}
+EXPORT_SYMBOL(prune_table_create);
+
+/**
+ * prune_table_destroy - Removes the table from the prune object and destroys
+ * it.
+ * @table: Table to be removed.
+ *
+ * Return: 0 in case of success, negative number to indicate an error.
+ *
+ * Note: It's the user responsibility to care of synchronization.
+ */
+int prune_table_destroy(struct prune_table *table)
+{
+ int err;
+
+ err = prune_intersec_table_fini(table);
+ if (err)
+ return err;
+
+ prune_item_prune_table_del(table->prune, table);
+
+ list_del(&table->list);
+
+ prune_table_fini(table);
+
+ return 0;
+}
+EXPORT_SYMBOL(prune_table_destroy);
+
+/**
+ * prune_item_create - Creates a new 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].
+ *
+ * Return: 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 of 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))
+ return ERR_CAST(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, entry,
+ curr_table != table ?
+ true : false);
+ if (err)
+ goto err_prune_intersec_list_item_add;
+ }
+ /* Update prune vector of the corresponding items of the neighbor
+ * tables
+ */
+ err = prune_neigh_table_prune_vector_set(table, entry, true);
+ if (err)
+ goto err_prune_neigh_table_prune_vector_set;
+
+ return &entry->item;
+
+err_prune_neigh_table_prune_vector_set:
+err_prune_intersec_list_item_add:
+ list_for_each_entry_continue_reverse(curr_table, &prune->table_list,
+ list) {
+ prune_intersec_list_item_del(table, curr_table, entry,
+ curr_table != table ? true : false);
+ }
+ prune_table_entry_destroy(entry);
+ return ERR_PTR(err);
+}
+EXPORT_SYMBOL(prune_item_create);
+
+/**
+ * prune_item_destroy - removes the item from a table and destroys it.
+ * @item: The item to remove.
+ *
+ * Return: 0 in case of success, negative number to indicate an error.
+ *
+ * Note: It's the user responsibility to care of 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 intersection tables */
+ list_for_each_entry(curr_table, &prune->table_list, list) {
+ err = prune_intersec_list_item_del(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_table_entry_destroy(entry);
+
+ return 0;
+}
+EXPORT_SYMBOL(prune_item_destroy);
+
+/**
+ * prune_table_priv - Retrieves the priv from the table.
+ * @table: The table which its priv is wanted.
+ *
+ * Return: A pointer to the priv field in the prune table.
+ *
+ * Note: It's the user responsibility to care of synchronization.
+ */
+void *prune_table_priv(struct prune_table *table)
+{
+ return table->priv;
+}
+EXPORT_SYMBOL(prune_table_priv);
+
+/**
+ * prune_item_prune_vector - Retrieves the prune vector of the item.
+ * @item: The table item its prune vector is wanted.
+ *
+ * Return: A pointer to the head of the prune vector list.
+ *
+ * Note: It's the user responsibility to care of synchronization.
+ */
+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->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,1214 @@
+// 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.
+ */
+
+#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;
+ 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 %s pruned\t pruned table *: %p\n",
+ i,
+ (uintptr_t)priv,
+ vector_item->pruned ? "" : "not",
+ 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 pruned
+ * table 1 pruned
+ * --> 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 pruned
+ * table 1 pruned
+ * --> 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 pruned (no change)
+ * table 1 pruned (no change)
+ * --> shoudn't not get notification
+ * item1 in table 1 (x.2.3.5.x prio 5):
+ * table 0 not pruned (changed)
+ * table 1 pruned (changed)
+ * --> Should get notification
+ * item2 in table 0 (1.2.3.x.x prio 7):
+ * table 0 pruned (no change)
+ * table 1 not pruned (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 not pruned
+ * table 1 pruned
+ * item2 table 0 (1.2.3.x.x prio 7):
+ * table 0 pruned
+ * table 1 pruned (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 pruned (changed)
+ * table 1 pruned
+ * 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.rst | 445 +++++++++++++++ MAINTAINERS | 8 + include/linux/prune.h | 83 +++ lib/Kconfig | 8 +- lib/Kconfig.debug | 10 + lib/Makefile | 3 + lib/prune.c | 1445 +++++++++++++++++++++++++++++++++++++++++++++++ lib/test_prune.c | 1214 +++++++++++++++++++++++++++++++++++++++ 9 files changed, 3217 insertions(+), 1 deletion(-) create mode 100644 Documentation/prune.rst create mode 100644 include/linux/prune.h create mode 100644 lib/prune.c create mode 100644 lib/test_prune.c