new file mode 100644
@@ -0,0 +1,126 @@
+Prune
+=====
+
+Prune is a library which solves how to select which table needs to be searched.
+User can create tables with specific masks. The tables contains masked items
+with priority. Since similar item can be inserted to different tables, there is
+a need to prune between the tables.
+pruning saves time complexity so that there won't be any need to search in
+other tables. this is first draft so comment are more than welcome.
+
+Table of Contents
+-----------------
+
+* Prune
+* Requirements
+* library interface
+ - objects
+ - APIs
+* Database
+* Synchronization & critical sections
+* WQ & Timers
+* Algorithm
+* Flows
+ - A* --> A
+ - A* --> C*
+ - A --> A*
+ - C* --> A
+* Testing
+* TBD table
+
+Requirements
+============
+ * Support up to 512K rules
+ * Insertion rate of ~50K rules per sec
+ * Each rule has it's own prune-vector
+
+library interface
+=================
+
+objects:
+--------
+struct prune
+
+APIs:
+-----
+check code.
+
+Database
+========
+Each prune object have a list tables with mask.
+Eech table consist:
+ * hash table for items
+ * list of the corresponding intersection table (with other tables)
+Each intersection table consist:
+ * hash table for intersects items
+ * each item contain two lists:
+ 1. items of the main table
+ 2. items of other tables in the prune object.
+
+
+Synchronization & critical sections
+===================================
+library doesn't take responsibility on synchronization. it's the user
+responsibility to synchronize.
+
+WQ & Timers
+===========
+N/A
+
+Algorithm
+=========
+TBD
+
+Flows
+=====
+Insert item 'R'
+--------------
+ * A*->A: Insert a item 'R' to some table, and we have to calculate its own prune-vector.
+ * A->A*: 'R' was inserted to some table, and we have to calculate the prune-vectors of
+ other compatible items (in different tables).
+
+Add new table
+-------------
+Add new table effects the prune vector of all current items in the prune object.
+There is a need to add new entry to the prune list of each item.
+
+Remove table
+------------
+Remove table effects the prune vector of all current items in the prune object.
+There is a need to remove existing entry from the prune list of each item.
+
+Testing
+=======
+Sanity Test
+-----------
+0. create prune object
+1. Create tables
+2. Add items to these tables --> check prune vector
+3. Remove items --> check prune vector.
+4. Remove tables
+5. Destroy prune object --> check that there is no leaks
+
+Basic tests
+-----------
+1. Add new table (after a table with rules already established)
+2. Add items while there is only one table after that add another table.
+3. Adding 3 table which will create the same intersection mask does the library should WARN on it ?
+4. add item with the same which have the same intersection mask.
+
+Pruning tests
+-------------
+Various advanced pruning tests
+
+Negative tests
+--------------
+1. Remove prune object with tables
+2. Remove table with items
+3. Remove an item which doesn't exist
+4. add items which have different mask than the table mask
+
+Stress test
+-----------
+create 50 prune object, with 16 table each, with a total of 500K items.
+1. Check run time
+2. Check memory foot print.
+
@@ -11204,6 +11204,14 @@ F: include/linux/sysctl.h
F: kernel/sysctl.c
F: tools/testing/selftests/sysctl/
+PRUNE
+M: Tal Bar <talb@mellanox.com>
+L: netdev@vger.kernel.org
+S: Supported
+F: lib/prune.c
+F: lib/test_prune.c
+F: include/linux/prune.h
+
PS3 NETWORK SUPPORT
M: Geoff Levand <geoff@infradead.org>
L: netdev@vger.kernel.org
new file mode 100644
@@ -0,0 +1,89 @@
+/*
+ * include/linux/prune.h - Manager for priority base pruning lookups between
+ * tables.
+ * Copyright (c) 2018 Mellanox Technologies. All rights reserved.
+ * Copyright (c) 2018 Tal Bar <talb@mellanox.com>
+ *
+ * SPDX-License-Identifier: (GPL-2.0 WITH Linux-syscall-note OR BSD-2)
+ */
+
+#ifndef _PRUNE_H
+#define _PRUNE_H
+
+struct prune_item {
+ unsigned long priority; /* higher number is more significant */
+ unsigned long *mask;
+ unsigned int mask_len; /* number of bits */
+ void *priv;
+};
+
+struct prune_table {
+ void *table_handle;
+ bool is_prune;
+ struct list_head list;
+ void *priv;
+};
+
+struct prune_item_notify {
+ struct prune_item item;
+ const struct list_head *table_prune_list; /* item prune table */
+};
+
+/* TODO: add this later on for prune_item_notify API */
+//struct prune_notify_list {
+// struct prune_item_notify *item_notify;
+// struct list_head item_notify_list;
+//};
+
+/**
+ * This structure defines the management hooks for prune object.
+ * The following hooks can be defined; unless noted otherwise, they are
+ * optional and can be filled with a null pointer.
+ *
+ * int (*prune_item_notify)(void *table_handle,
+ * struct prune_item_notify *item,
+ * unsigned int item_cnt);
+ * 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. if NULL notification
+ * won't be done.
+ *
+ * int (*prune_mask_match)(unsigned long *mask_a, unsigned long *mask_b,
+ * unsigned int len);
+ * called when adding new items to a table. if NULL mask are allowed to be
+ * match by default.
+ */
+struct prune_ops {
+ void (*prune_item_notify)(void *table_handle,
+ struct prune_item_notify *item,
+ unsigned int item_cnt);
+ int (*prune_mask_comparable)(unsigned long *mask_a,
+ unsigned long *mask_b,
+ unsigned int len);
+};
+
+struct prune_ret_table {
+ void *table_handle;
+ bool valid;
+};
+
+struct prune_table_attr {
+ unsigned long *mask;
+ unsigned int mask_len; /* number of bits */
+ /* used by the priv field in strcut prune_table */
+ void *priv;
+};
+
+struct prune;
+
+struct prune *prune_init(unsigned int mask_len, const struct prune_ops *ops,
+ void *priv);
+void prune_fini(struct prune *prune);
+int prune_table_add(struct prune *prune, struct prune_table_attr *table_attr,
+ struct prune_ret_table *ret_table);
+int prune_table_remove(struct prune *prune, void *table_handle);
+int prune_item_add(struct prune *prune, void *table_handle,
+ struct prune_item *item);
+int prune_item_remove(struct prune *prune, void *table_handle,
+ struct prune_item *item);
+int prune_table_prune_score_get(void *table_handle);
+#endif
@@ -583,6 +583,12 @@ config PARMAN
config PRIME_NUMBERS
tristate
+config PRUNE
+ tristate "prune"
+ help
+ This option enables the use of prune mananger for priority base
+ pruning lookups between tables.
+
config STRING_SELFTEST
tristate "Test string functions"
@@ -1803,6 +1803,16 @@ config TEST_PARMAN
If unsure, say N.
+config TEST_PRUNE
+ tristate "Perform selftest on pruning lookups between tables manager"
+ default n
+ depends on PRUNE
+ help
+ Enable this option to test pruning lookups between tables manager
+ (or module load).
+
+ If unsure, say N.
+
config TEST_LKM
tristate "Test module loading with 'hello world' module"
default n
@@ -66,6 +66,7 @@ obj-$(CONFIG_TEST_UUID) += test_uuid.o
obj-$(CONFIG_TEST_PARMAN) += test_parman.o
obj-$(CONFIG_TEST_KMOD) += test_kmod.o
obj-$(CONFIG_TEST_DEBUG_VIRTUAL) += test_debug_virtual.o
+obj-$(CONFIG_TEST_PRUNE) += test_prune.o
ifeq ($(CONFIG_DEBUG_KOBJECT),y)
CFLAGS_kobject.o += -DDEBUG
@@ -252,6 +253,8 @@ obj-$(CONFIG_SBITMAP) += sbitmap.o
obj-$(CONFIG_PARMAN) += parman.o
+obj-$(CONFIG_PRUNE) += prune.o
+
# GCC library routines
obj-$(CONFIG_GENERIC_ASHLDI3) += ashldi3.o
obj-$(CONFIG_GENERIC_ASHRDI3) += ashrdi3.o
new file mode 100644
@@ -0,0 +1,1232 @@
+/*
+ * lib/prune.c - Manager for priority base pruning lookups between tables.
+ * Copyright (c) 2018 Mellanox Technologies. All rights reserved.
+ * Copyright (c) 2018 Tal Bar <talb@mellanox.com>
+ *
+ * SPDX-License-Identifier: (GPL-2.0 WITH Linux-syscall-note OR BSD-2)
+ */
+
+#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 table_item_key {
+ unsigned long *mask;
+ unsigned long priority;
+};
+
+struct table_item_entry {
+ struct rhash_head ht_node; /* Member of tablset HT */
+ struct table_item_key ht_key;
+ unsigned int mask_len;
+ struct list_head table_prune_list;
+};
+
+struct neighbor_table_items {
+ struct prune_item *item;
+ struct list_head list;
+};
+
+struct intersec_table_items {
+ const struct table_item_entry *item_p;
+ struct list_head list;
+};
+
+struct intersec_table_item_key {
+ unsigned long *mask;
+};
+
+struct intersec_table_item_entry {
+ struct rhash_head ht_node; /* Member of tablset HT */
+ struct intersec_table_item_key ht_key;
+ unsigned int mask_len;
+ struct list_head intersec_table_items;
+ struct list_head neighbor_table_items; /* can be enhanced to rbtree */
+};
+
+struct table;
+
+struct intersec_table {
+ unsigned long *mask;
+ struct rhashtable items_ht;
+ struct table *neigh_table;
+ struct list_head list;
+};
+
+struct table {
+ unsigned long *mask;
+ struct rhashtable items_ht;
+ unsigned int prune_score; /* counts the number of tables which are
+ * pruned due to items in this table.
+ * higher score --> pruning more tables.
+ */
+ /* A list of table structs that contains intersection of the current
+ * table with the other tables in the prune object.
+ */
+ struct list_head intersec_table_list;
+ struct list_head list;
+ const struct prune_ops *ops;
+ void *priv;
+};
+
+struct prune {
+ const struct prune_ops *ops;
+ unsigned int mask_len;
+ struct list_head table_list; /* A list of struct table */
+ unsigned int table_cnt; /* number of tables in the list */
+ void *priv;
+};
+
+static inline unsigned long *bm_kcalloc(int nbits)
+{
+ return kcalloc(1, BITS_TO_LONGS(nbits) * sizeof(unsigned long),
+ GFP_KERNEL);
+}
+
+static int __table_ht_cmp(struct rhashtable_compare_arg *arg, const void *obj);
+static u32 __table_ht_hash(const void *data, u32 len, u32 seed);
+static int __intersec_ht_cmp(struct rhashtable_compare_arg *arg,
+ const void *obj);
+static u32 __intersec_ht_hash(const void *data, u32 len, u32 seed);
+
+static struct rhashtable_params tables_ht_params = {
+ .key_offset = offsetof(struct table_item_entry, ht_key),
+ .head_offset = offsetof(struct table_item_entry, ht_node),
+ .obj_cmpfn = __table_ht_cmp,
+ .hashfn = __table_ht_hash,
+ .automatic_shrinking = true,
+};
+
+static struct rhashtable_params itersec_tables_ht_params = {
+ .key_offset = offsetof(struct intersec_table_item_entry, ht_key),
+ .head_offset = offsetof(struct intersec_table_item_entry, ht_node),
+ .obj_cmpfn = __intersec_ht_cmp,
+ .hashfn = __intersec_ht_hash,
+ .automatic_shrinking = true,
+};
+
+static u32 __table_ht_hash(const void *data, u32 len, u32 seed)
+{
+ const struct table_item_key * const key = data;
+ unsigned int mask_hash, prio_hash;
+ unsigned long long tmp;
+ u32 jash_len = BITS_TO_LONGS(len) * sizeof(unsigned long);
+
+ mask_hash = jhash(key->mask, jash_len, seed);
+ prio_hash = jhash(&key->priority, sizeof(unsigned long), seed);
+ tmp = mask_hash + prio_hash;
+ return jhash(&tmp, sizeof(unsigned long long), seed);
+}
+
+static int __table_ht_cmp(struct rhashtable_compare_arg *arg, const void *obj)
+{
+ const struct table_item_key * const key = arg->key;
+ const struct table_item_entry *item_entry = obj;
+ int equal;
+ bool b;
+
+ equal = bitmap_equal(key->mask, item_entry->ht_key.mask,
+ item_entry->mask_len);
+ b = item_entry->ht_key.priority == key->priority;
+
+ return !b && !equal;
+}
+
+static u32 __intersec_ht_hash(const void *data, u32 len, u32 seed)
+{
+ u32 jash_len = BITS_TO_LONGS(len) * sizeof(unsigned long);
+ const struct intersec_table_item_key * const key = data;
+
+ return jhash(key->mask, jash_len, seed);
+}
+
+static int __intersec_ht_cmp(struct rhashtable_compare_arg *arg,
+ const void *obj)
+{
+ const struct intersec_table_item_entry *intersec_item_entry = obj;
+ const struct intersec_table_item_key * const key = arg->key;
+
+ return !(bitmap_equal(key->mask, intersec_item_entry->ht_key.mask,
+ intersec_item_entry->mask_len));
+}
+
+static void table_prune_list_destroy(struct table_item_entry *entry)
+{
+ struct prune_table *prune_table_item;
+ struct list_head *pos, *tmp;
+
+ list_for_each_safe(pos, tmp, &entry->table_prune_list) {
+ prune_table_item = list_entry(pos, typeof(*prune_table_item),
+ list);
+ list_del(pos);
+ kfree(prune_table_item);
+ }
+}
+
+static int table_prune_list_init(struct prune *prune,
+ struct table_item_entry *entry)
+{
+ struct prune_table *prune_table_item;
+ struct list_head *pos;
+ struct table *table;
+
+ INIT_LIST_HEAD(&entry->table_prune_list);
+
+ list_for_each(pos, &prune->table_list) {
+ table = list_entry(pos, typeof(*table), list);
+ prune_table_item = kzalloc(sizeof(*prune_table_item),
+ GFP_KERNEL);
+ if (!prune_table_item) {
+ table_prune_list_destroy(entry);
+ return -ENOMEM;
+ }
+ prune_table_item->is_prune = true;
+ prune_table_item->priv = table->priv;
+ prune_table_item->table_handle = table;
+ list_add_tail(&prune_table_item->list,
+ &entry->table_prune_list);
+ }
+ return 0;
+}
+
+static void table_prune_list_deinit(struct list_head *table_prune_list)
+{
+ struct prune_table *prune_table_item;
+ struct list_head *pos, *tmp;
+
+ list_for_each_safe(pos, tmp, table_prune_list) {
+ prune_table_item = list_entry(pos, typeof(*prune_table_item),
+ list);
+ list_del(&prune_table_item->list);
+ kfree(prune_table_item);
+ }
+ WARN_ON(!list_empty(table_prune_list));
+}
+
+static struct table_item_entry *prune_item_entry_create(struct prune *prune,
+ struct prune_item *item)
+{
+ struct table_item_entry *entry;
+ int err;
+
+ entry = kzalloc(sizeof(*entry), GFP_KERNEL);
+ if (!entry)
+ goto err_entry_alloc;
+
+ entry->ht_key.mask = bm_kcalloc(item->mask_len);
+ if (!entry->ht_key.mask)
+ goto err_mask_alloc;
+
+ entry->mask_len = item->mask_len;
+ bitmap_copy(entry->ht_key.mask, item->mask, item->mask_len);
+ entry->ht_key.priority = item->priority;
+
+ err = table_prune_list_init(prune, entry);
+ if (err)
+ return NULL;
+
+ return entry;
+
+err_mask_alloc:
+ kfree(&entry);
+err_entry_alloc:
+ return NULL;
+}
+
+static void prune_entry_destroy(struct table_item_entry *entry)
+{
+ table_prune_list_deinit(&entry->table_prune_list);
+ kfree(entry->ht_key.mask);
+ kfree(entry);
+}
+
+static bool is_items_comparable(struct table *table, unsigned long *mask_a,
+ unsigned long *mask_b, unsigned int mask_len)
+{
+ if (table->ops->prune_mask_comparable) {
+ return table->ops->prune_mask_comparable(mask_a,
+ mask_b,
+ mask_len);
+ }
+ return true;
+}
+
+static bool prune_item_update(const struct list_head *table_prune_list,
+ struct table *corresponding_table,
+ bool is_prune)
+{
+ struct prune_table *prune_table_item;
+ struct list_head *prune_pos;
+
+ list_for_each(prune_pos, table_prune_list) {
+ prune_table_item = list_entry(prune_pos,
+ typeof(*prune_table_item),
+ list);
+ /* find the corresponding prune item and set it to not prune */
+ if (prune_table_item->table_handle == corresponding_table) {
+ prune_table_item->is_prune = is_prune;
+ return true;
+ }
+ }
+ return false;
+}
+
+static bool prune_vector_set(struct table *table,
+ struct table *neigh_table,
+ const struct table_item_entry *item,
+ struct neighbor_table_items *neigh_list_item,
+ struct intersec_table_items *intsc_item,
+ bool neigh_items)
+{
+ const struct list_head *prune_list;
+ unsigned long *mask;
+ bool not_prune;
+
+ if (neigh_items)
+ not_prune = neigh_list_item->item->priority
+ > item->ht_key.priority;
+ else
+ not_prune = intsc_item->item_p->ht_key.priority
+ < item->ht_key.priority;
+
+ mask = neigh_items ? neigh_list_item->item->mask
+ : intsc_item->item_p->ht_key.mask;
+ prune_list = neigh_items ? &item->table_prune_list
+ : &intsc_item->item_p->table_prune_list;
+ if (not_prune) {
+ if (is_items_comparable(table, item->ht_key.mask, mask,
+ item->mask_len)) {
+ return prune_item_update(prune_list, neigh_table,
+ false);
+ }
+ }
+ return false;
+}
+
+static bool item_add_prune_vector_calc(struct table *table,
+ struct intersec_table *intersec_table,
+ struct intersec_table_item_key *key,
+ const struct table_item_entry *t_item,
+ bool neigh_items)
+{
+ struct neighbor_table_items *neigh_list_item;
+ struct intersec_table_item_entry *entry;
+ struct intersec_table_items *intsc_item;
+ struct list_head *neigh_pos, *item_pos;
+ struct prune_item_notify item_notify;
+ bool prune_vector_chng = false;
+
+ bitmap_clear(key->mask, 0, t_item->mask_len);
+ bitmap_and(key->mask, t_item->ht_key.mask, intersec_table->mask,
+ t_item->mask_len);
+
+ entry = rhashtable_lookup_fast(&intersec_table->items_ht, key,
+ itersec_tables_ht_params);
+
+ /* if there is a match on this mask - need to iterate on
+ * neighbor_table_items in case there is an t_item with higher
+ * priority we should not prune the neighbor table.
+ */
+ if (!entry)
+ return false;
+
+ if (neigh_items) {
+ list_for_each(neigh_pos, &entry->neighbor_table_items) {
+ neigh_list_item = list_entry(neigh_pos,
+ typeof(*neigh_list_item),
+ list);
+
+ prune_vector_chng |= prune_vector_set(table,
+ intersec_table->neigh_table,
+ t_item,
+ neigh_list_item,
+ NULL,
+ neigh_items);
+ }
+ } else {
+ /* for my items need to update to prune vector
+ * corresponding to the new item
+ */
+ list_for_each(item_pos, &entry->intersec_table_items) {
+ intsc_item = list_entry(item_pos,
+ typeof(*intsc_item),
+ list);
+
+ if (prune_vector_set(table,
+ intersec_table->neigh_table,
+ t_item,
+ NULL,
+ intsc_item,
+ neigh_items)) {
+ item_notify.item.priority =
+ intsc_item->item_p->ht_key.priority;
+ item_notify.item.mask =
+ intsc_item->item_p->ht_key.mask;
+ item_notify.item.mask_len =
+ intsc_item->item_p->mask_len;
+ item_notify.table_prune_list =
+ &intsc_item->item_p->table_prune_list;
+ table->ops->prune_item_notify(table,
+ &item_notify,
+ 1);
+ /* TODO: need to enhance to one notification
+ * and remove this code block
+ */
+ }
+ }
+ }
+ return prune_vector_chng;
+}
+
+static bool neigh_item_prio_higher(struct table *table,
+ struct prune_item *neigh_item,
+ const struct table_item_entry *intsc_item)
+{
+ if (is_items_comparable(table, neigh_item->mask,
+ intsc_item->ht_key.mask,
+ neigh_item->mask_len)) {
+ if (neigh_item->priority > intsc_item->ht_key.priority)
+ return true;
+ else
+ return false;
+ }
+ return false;
+}
+
+static void item_remove_prune_vector_calc(struct table *table,
+ struct prune_item *deleted_item,
+ struct intersec_table *intersec_table,
+ struct intersec_table_item_key *key)
+{
+ struct list_head *item_pos, *neigh_pos;
+ struct intersec_table_item_entry *entry;
+ struct intersec_table_items *intsc_item;
+ struct neighbor_table_items *neigh_item;
+ struct prune_item_notify item_notify;
+ const struct list_head *prune_list;
+ bool to_prune, notify;
+
+ bitmap_clear(key->mask, 0, deleted_item->mask_len);
+ bitmap_and(key->mask, deleted_item->mask, intersec_table->mask,
+ deleted_item->mask_len);
+
+ entry = rhashtable_lookup_fast(&intersec_table->items_ht, key,
+ itersec_tables_ht_params);
+ if (!entry)
+ return;
+
+ /* check if one of the item in the neighbor list have higher
+ * prio if so don't prune
+ */
+ list_for_each(item_pos, &entry->intersec_table_items) {
+ intsc_item = list_entry(item_pos,
+ typeof(*intsc_item),
+ list);
+ /* check if there is an item in my neigh list with higher prio
+ * and it's allowed to compare between them is so -->
+ * don't prune
+ */
+ to_prune = true;
+ list_for_each(neigh_pos, &entry->neighbor_table_items) {
+ neigh_item = list_entry(neigh_pos,
+ typeof(*neigh_item),
+ list);
+ if (neigh_item_prio_higher(table,
+ neigh_item->item,
+ intsc_item->item_p)) {
+ to_prune = false;
+ break;
+ }
+ }
+ notify = false;
+ if (to_prune) {
+ /* update intsc_item prune vector for the
+ * corresponding table
+ */
+ prune_list = &intsc_item->item_p->table_prune_list;
+ notify = prune_item_update(prune_list, table, true);
+ }
+ if (notify) {
+ item_notify.item.priority =
+ intsc_item->item_p->ht_key.priority;
+ item_notify.item.mask =
+ intsc_item->item_p->ht_key.mask;
+ item_notify.item.mask_len =
+ intsc_item->item_p->mask_len;
+ item_notify.table_prune_list =
+ &intsc_item->item_p->table_prune_list;
+ table->ops->prune_item_notify(table,
+ &item_notify, 1);
+ /* TODO: need to enhance to one notification
+ * and remove this code block
+ */
+ }
+ }
+}
+
+static int item_prune_vector_set(struct table *table, struct prune_item *p_item,
+ struct table_item_entry *t_item)
+{
+ struct intersec_table *intersec_table;
+ struct intersec_table_item_key ht_key;
+ struct prune_item_notify item_notify;
+ struct list_head *pos;
+ bool notify = false;
+
+ ht_key.mask = bm_kcalloc(t_item->mask_len);
+ if (!ht_key.mask)
+ return -ENOMEM;
+
+ list_for_each(pos, &table->intersec_table_list) {
+ intersec_table = list_entry(pos, typeof(*intersec_table), list);
+ notify |= item_add_prune_vector_calc(table,
+ intersec_table,
+ &ht_key, t_item, true);
+ }
+ if (notify) {
+ item_notify.item = *p_item;
+ item_notify.table_prune_list = &t_item->table_prune_list;
+ table->ops->prune_item_notify(table, &item_notify, 1);
+ }
+ return 0;
+}
+
+static void neigh_prune_vector_calc(struct table *table,
+ struct table *curr_table,
+ struct prune_item *item,
+ struct intersec_table_item_key *ht_key,
+ const struct table_item_entry *tbl_entry,
+ bool add_item)
+{
+ struct intersec_table *intrsc_tbl;
+ struct list_head *intrsc_pos;
+
+ /* 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(intrsc_pos, &curr_table->intersec_table_list) {
+ intrsc_tbl = list_entry(intrsc_pos, typeof(*intrsc_tbl), list);
+ if (intrsc_tbl->neigh_table == table) {
+ /* this is the corresponding table */
+ if (add_item)
+ item_add_prune_vector_calc(table,
+ intrsc_tbl,
+ ht_key,
+ tbl_entry,
+ false);
+ else
+ item_remove_prune_vector_calc(table,
+ item,
+ intrsc_tbl,
+ ht_key);
+ }
+ }
+}
+
+static int neigh_table_prune_vector_set(struct prune *prune,
+ struct table *table,
+ struct prune_item *item,
+ const struct table_item_entry *tbl_entry,
+ bool add_item)
+{
+ struct intersec_table_item_key ht_key;
+ struct table *curr_table;
+ struct list_head *pos;
+
+ ht_key.mask = bm_kcalloc(item->mask_len);
+ if (!ht_key.mask)
+ return -ENOMEM;
+
+ list_for_each(pos, &prune->table_list) {
+ curr_table = list_entry(pos, typeof(*curr_table), list);
+ if (curr_table != table)
+ neigh_prune_vector_calc(table, curr_table, item,
+ &ht_key, tbl_entry, add_item);
+ }
+ return 0;
+}
+
+static struct table_item_entry *table_item_add(struct prune *prune,
+ struct table *table,
+ struct prune_item *item)
+{
+ struct table_item_entry *entry;
+ int err;
+
+ if (bitmap_subset(item->mask, table->mask, item->mask_len) != 1)
+ return ERR_PTR(-EPERM);
+
+ entry = prune_item_entry_create(prune, item);
+ if (!entry)
+ return ERR_PTR(-ENOMEM);
+
+ err = item_prune_vector_set(table, item, entry);
+ if (err) {
+ prune_entry_destroy(entry);
+ return ERR_PTR(err);
+ }
+ err = rhashtable_insert_fast(&table->items_ht,
+ &entry->ht_node, tables_ht_params);
+ if (err) {
+ prune_entry_destroy(entry);
+ return ERR_PTR(err);
+ }
+ return entry;
+}
+
+static int table_item_remove(struct table *table, struct prune_item *item)
+{
+ struct table_item_entry *entry;
+ struct table_item_key ht_key;
+
+ ht_key.mask = item->mask;
+ ht_key.priority = item->priority;
+
+ entry = rhashtable_lookup_fast(&table->items_ht, &ht_key,
+ tables_ht_params);
+ if (!entry)
+ return -EPERM;
+
+ rhashtable_remove_fast(&table->items_ht, &entry->ht_node,
+ tables_ht_params);
+
+ prune_entry_destroy(entry);
+
+ return 0;
+}
+
+static int intersec_item_add(struct intersec_table *intersec_table,
+ struct prune_item *item,
+ const struct table_item_entry *tbl_entry,
+ bool neigh_item)
+{
+ struct neighbor_table_items *neigh_list_item;
+ struct intersec_table_item_entry *entry;
+ struct intersec_table_items *list_item;
+ struct intersec_table_item_key ht_key;
+ bool found = true;
+ int err = 0;
+
+ ht_key.mask = bm_kcalloc(item->mask_len);
+ if (!ht_key.mask)
+ return -ENOMEM;
+
+ bitmap_and(ht_key.mask, intersec_table->mask, item->mask,
+ item->mask_len);
+
+ entry = rhashtable_lookup_fast(&intersec_table->items_ht, &ht_key,
+ itersec_tables_ht_params);
+ if (!entry) {
+ entry = kzalloc(sizeof(*entry), GFP_KERNEL);
+ if (!entry)
+ goto err_entry_alloc;
+
+ entry->ht_key.mask = bm_kcalloc(item->mask_len);
+ if (!entry->ht_key.mask)
+ goto err_mask_alloc;
+
+ entry->mask_len = item->mask_len;
+
+ bitmap_and(entry->ht_key.mask, intersec_table->mask,
+ item->mask, item->mask_len);
+
+ INIT_LIST_HEAD(&entry->intersec_table_items);
+ INIT_LIST_HEAD(&entry->neighbor_table_items);
+ found = false;
+ }
+
+ if (!neigh_item) {
+ list_item = kzalloc(sizeof(*list_item), GFP_KERNEL);
+ if (!list_item)
+ goto err_list_item_alloc;
+
+ list_item->item_p = tbl_entry;
+ list_add_tail(&list_item->list, &entry->intersec_table_items);
+ } else {
+ neigh_list_item = kzalloc(sizeof(*neigh_list_item), GFP_KERNEL);
+ if (!neigh_list_item)
+ goto err_nigh_list_item_alloc;
+
+ neigh_list_item->item = item;
+ list_add_tail(&neigh_list_item->list,
+ &entry->neighbor_table_items);
+ }
+ if (!found) {
+ err = rhashtable_insert_fast(&intersec_table->items_ht,
+ &entry->ht_node,
+ itersec_tables_ht_params);
+ if (err)
+ goto err_rhashtable_insert;
+ }
+
+ kfree(ht_key.mask);
+ return 0;
+
+err_rhashtable_insert:
+ if (!neigh_item) {
+ list_del(&list_item->list);
+ kfree(list_item);
+ } else {
+ list_del(&neigh_list_item->list);
+ kfree(neigh_list_item);
+ }
+err_nigh_list_item_alloc:
+err_list_item_alloc:
+ kfree(entry->ht_key.mask);
+err_mask_alloc:
+ kfree(entry);
+err_entry_alloc:
+ kfree(ht_key.mask);
+ return err ? err : -ENOMEM;
+}
+
+static int intersec_item_remove(struct intersec_table *intersec_table,
+ struct prune_item *item, bool neigh_item)
+{
+ struct neighbor_table_items *neigh_list_item;
+ struct intersec_table_item_entry *entry;
+ struct intersec_table_items *list_item;
+ struct intersec_table_item_key ht_key;
+ struct list_head *pos, *tmp;
+
+ ht_key.mask = bm_kcalloc(item->mask_len);
+ if (!ht_key.mask)
+ return -ENOMEM;
+
+ bitmap_and(ht_key.mask, intersec_table->mask, item->mask,
+ item->mask_len);
+
+ entry = rhashtable_lookup_fast(&intersec_table->items_ht, &ht_key,
+ itersec_tables_ht_params);
+ if (!entry) {
+ kfree(ht_key.mask);
+ return -EPERM;
+ }
+
+ if (!neigh_item) {
+ list_for_each_safe(pos, tmp, &entry->intersec_table_items) {
+ list_item = list_entry(pos, typeof(*list_item), list);
+ if (bitmap_equal(list_item->item_p->ht_key.mask,
+ item->mask,
+ item->mask_len)) {
+ list_del(pos);
+ kfree(list_item);
+ break;
+ }
+ }
+ } else {
+ list_for_each_safe(pos, tmp, &entry->neighbor_table_items) {
+ neigh_list_item = list_entry(pos,
+ typeof(*neigh_list_item),
+ list);
+ if (item == neigh_list_item->item) {
+ list_del(pos);
+ kfree(neigh_list_item);
+ break;
+ }
+ }
+ }
+ if (list_empty(&entry->intersec_table_items) &&
+ list_empty(&entry->neighbor_table_items)) {
+ rhashtable_remove_fast(&intersec_table->items_ht,
+ &entry->ht_node,
+ itersec_tables_ht_params);
+ kfree(entry->ht_key.mask);
+ kfree(entry);
+ }
+ kfree(ht_key.mask);
+ return 0;
+}
+
+static struct intersec_table *prune_alloc_intrsc_table(unsigned int mask_len)
+{
+ struct intersec_table *intersec_table;
+
+ intersec_table = kzalloc(sizeof(*intersec_table), GFP_KERNEL);
+ if (!intersec_table)
+ goto err_intersec_table_alloc;
+
+ intersec_table->mask = bm_kcalloc(mask_len);
+ if (!intersec_table->mask)
+ goto err_intersec_table_mask_alloc;
+
+ return intersec_table;
+
+err_intersec_table_mask_alloc:
+ kfree(intersec_table);
+err_intersec_table_alloc:
+ return NULL;
+}
+
+static int prune_intersec_table_add(struct prune *prune,
+ struct table *table,
+ struct list_head *pos)
+{
+ struct intersec_table *intersec_table1;
+ struct intersec_table *intersec_table2;
+ struct table *curr_table;
+ int err;
+
+ curr_table = list_entry(pos, typeof(*curr_table), list);
+
+ intersec_table1 = prune_alloc_intrsc_table(prune->mask_len);
+ if (!intersec_table1)
+ goto err_allocate_intersec_table1;
+
+ intersec_table2 = prune_alloc_intrsc_table(prune->mask_len);
+ if (!intersec_table2)
+ goto err_allocate_intersec_table2;
+
+ bitmap_and(intersec_table1->mask, table->mask, curr_table->mask,
+ prune->mask_len);
+
+ bitmap_and(intersec_table2->mask, table->mask, curr_table->mask,
+ prune->mask_len);
+
+ /* TODO: maybe need to verify if there is another intersec table with
+ * same mask and set error ?!.
+ */
+ err = rhashtable_init(&intersec_table1->items_ht,
+ &itersec_tables_ht_params);
+ if (err)
+ goto err_rhashtable_init_1;
+
+ err = rhashtable_init(&intersec_table2->items_ht,
+ &itersec_tables_ht_params);
+ if (err)
+ goto err_rhashtable_init_2;
+
+ /* Add new intersection table to the old table */
+ intersec_table1->neigh_table = table;
+ list_add(&intersec_table1->list, &curr_table->intersec_table_list);
+ /* Add new intersection table to new table */
+ intersec_table2->neigh_table = curr_table;
+ list_add(&intersec_table2->list, &table->intersec_table_list);
+
+ return 0;
+
+err_rhashtable_init_2:
+ rhashtable_destroy(&intersec_table2->items_ht);
+err_rhashtable_init_1:
+err_allocate_intersec_table2:
+ kfree(intersec_table1->mask);
+ kfree(intersec_table1);
+err_allocate_intersec_table1:
+ return -ENOMEM;
+}
+
+static int prune_intersec_table_build(struct prune *prune, struct table *table)
+{
+ struct list_head *pos;
+ int err;
+
+ list_for_each(pos, &prune->table_list) {
+ err = prune_intersec_table_add(prune, table, pos);
+ if (err) {
+ /* TODO: need to free memory of new intersec tables,
+ * that have been created.
+ */
+ return err;
+ }
+ }
+ return 0;
+}
+
+static int prune_instersec_table_remove(unsigned int mask_len,
+ struct table *table,
+ struct table *table_removed)
+{
+ struct intersec_table *curr_intersec_table;
+ struct list_head *intersec_pos, *tmp;
+ unsigned long *curr_mask;
+
+ curr_mask = bm_kcalloc(mask_len);
+ if (!curr_mask)
+ return -ENOMEM;
+
+ bitmap_and(curr_mask, table->mask, table_removed->mask, mask_len);
+
+ list_for_each_safe(intersec_pos, tmp, &table->intersec_table_list) {
+ curr_intersec_table = list_entry(intersec_pos,
+ typeof(*curr_intersec_table),
+ list);
+ if (bitmap_equal(curr_mask, curr_intersec_table->mask,
+ mask_len)) {
+ list_del(intersec_pos);
+ rhashtable_destroy(&curr_intersec_table->items_ht);
+ kfree(curr_intersec_table->mask);
+ kfree(curr_intersec_table);
+ return 0;
+ }
+ }
+ WARN_ON(1);
+ return -EPERM;
+}
+
+static int intersec_list_item_add(struct table *table,
+ struct prune_item *item,
+ const struct table_item_entry *tbl_entry,
+ bool neigh_item)
+{
+ struct intersec_table *curr_intersec_table;
+ struct list_head *intersec_pos;
+ int err;
+
+ list_for_each(intersec_pos, &table->intersec_table_list) {
+ curr_intersec_table = list_entry(intersec_pos,
+ typeof(*curr_intersec_table),
+ list);
+ err = intersec_item_add(curr_intersec_table, item, tbl_entry,
+ neigh_item);
+ if (err)
+ return err;
+ }
+ return 0;
+}
+
+static int intersec_list_item_remove(struct table *table,
+ struct prune_item *item,
+ bool neigh_item)
+{
+ struct intersec_table *curr_intersec_table;
+ struct list_head *intersec_pos;
+ int err;
+
+ list_for_each(intersec_pos, &table->intersec_table_list) {
+ curr_intersec_table = list_entry(intersec_pos,
+ typeof(*curr_intersec_table),
+ list);
+ err = intersec_item_remove(curr_intersec_table, item,
+ neigh_item);
+ if (err)
+ return err;
+ }
+ return 0;
+}
+
+/**
+ * prune_init - initializes a prune object which manage the pruning vector
+ * between tables
+ * @mask_len: Sets the mask len (nbits) for all tables in the prune
+ * object.
+ * @ops: caller-specific callbacks
+ * @priv: pointer to a private user data.
+ *
+ * Returns a pointer to newly created prune instance in case of success,
+ * otherwise it returns NULL.
+ *
+ * Note: all locking must be provided by the caller.
+ *
+ * Before caller could add a table with certain mask, he has to
+ * initialize the number of tables the prune supports.
+ */
+struct prune *prune_init(unsigned int mask_len, const struct prune_ops *ops,
+ void *priv)
+{
+ struct prune *prune;
+
+ if (!ops)
+ return NULL;
+
+ prune = kzalloc(sizeof(*prune), GFP_KERNEL);
+ if (!prune)
+ return NULL;
+
+ prune->table_cnt = 0;
+ prune->priv = priv;
+ prune->mask_len = mask_len;
+ INIT_LIST_HEAD(&prune->table_list);
+ prune->ops = ops;
+ tables_ht_params.key_len = mask_len;
+ itersec_tables_ht_params.key_len = mask_len;
+
+ return prune;
+}
+EXPORT_SYMBOL(prune_init);
+
+/**
+ * prune_fini - finalizes use of prune object
+ * @prune: prune object
+ *
+ * Note: all locking must be provided by the caller.
+ */
+void prune_fini(struct prune *prune)
+{
+ WARN_ON(prune->table_cnt > 0 || !list_empty(&prune->table_list));
+
+ kfree(prune);
+}
+EXPORT_SYMBOL(prune_fini);
+
+/**
+ * prune_table_prune_bits_get - gets the prune "score", number of table which
+ * are pruned due to this table item.
+ * @table_handle: table identification
+ *
+ * Return the accumulated (per item) number of prune tables in the table.
+ *
+ * Note: all locking must be provided by the caller.
+ */
+int prune_table_prune_score_get(void *table_handle)
+{
+ struct table *table;
+
+ table = (struct table *) table_handle;
+
+ return table->prune_score;
+}
+EXPORT_SYMBOL(prune_table_prune_score_get);
+
+/**
+ * prune_table_add - adds new table to the prune object with specific mask
+ * @prune: prune object
+ * table_attr: attribute for this table
+ * @ret_table: returns the table id on success otherwise sets valid as false
+ *
+ * Returns ENOMEM in case allocation failed.
+ * Returns EPERM for invalid parameter.
+ * otherwise it returns 0.
+ *
+ * Note: all locking must be provided by the caller.
+ */
+int prune_table_add(struct prune *prune, struct prune_table_attr *table_attr,
+ struct prune_ret_table *ret_table)
+{
+ struct table *table;
+ int err;
+
+ if (prune->mask_len != table_attr->mask_len)
+ return -EPERM;
+
+ ret_table->valid = false;
+
+ table = kzalloc(sizeof(*table), GFP_KERNEL);
+ if (!table)
+ return -ENOMEM;
+
+ table->mask = bm_kcalloc(prune->mask_len);
+ if (!table->mask) {
+ err = -ENOMEM;
+ goto err_mask_alloc_fail;
+ }
+ bitmap_copy(table->mask, table_attr->mask, table_attr->mask_len);
+ table->priv = table_attr->priv;
+ table->ops = prune->ops;
+ INIT_LIST_HEAD(&table->intersec_table_list);
+
+ err = rhashtable_init(&table->items_ht, &tables_ht_params);
+ if (err)
+ goto err_rhashtable_init;
+
+ err = prune_intersec_table_build(prune, table);
+ if (err)
+ goto err_intersec_table_build;
+
+ list_add_tail(&table->list, &prune->table_list);
+
+ /* TODO - need to add of o.r.t to the new intersection table from all
+ * the current tables
+ */
+
+ /* TODO: need to enlarge prune vector of each item :-(*/
+
+ prune->table_cnt++;
+
+ ret_table->table_handle = table;
+ ret_table->valid = true;
+
+ return 0;
+
+/* error flow path */
+err_intersec_table_build:
+ rhashtable_destroy(&table->items_ht);
+err_rhashtable_init:
+ kfree(table->mask);
+err_mask_alloc_fail:
+ kfree(table);
+ return err;
+}
+EXPORT_SYMBOL(prune_table_add);
+
+/**
+ * prune_table_remove - removes a table from the prune object.
+ * @prune: prune object
+ * @table_handle: table identification to be removed.
+ *
+ * Returns ENOMEM in case allocation failed.
+ * Returns EPERM for invalid parameter.
+ * otherwise it returns 0.
+ *
+ * Note: all locking must be provided by the caller.
+ */
+int prune_table_remove(struct prune *prune, void *table_handle)
+{
+ struct intersec_table *curr_intersec_table;
+ struct list_head *pos, *tmp;
+ struct table *curr_table;
+ struct table *table;
+ int err;
+
+ table = (struct table *) table_handle;
+
+ if (prune->table_cnt == 0 ||
+ atomic_read(&table->items_ht.nelems) != 0) {
+ WARN_ON(1);
+ return -EPERM;
+ }
+
+ else if (prune->table_cnt > 1) {
+ /* remove the intersec table from other table */
+ list_for_each(pos, &prune->table_list) {
+ curr_table = list_entry(pos, typeof(*curr_table),
+ list);
+ if (curr_table != table) {
+ err = prune_instersec_table_remove
+ (prune->mask_len,
+ curr_table,
+ table);
+ if (err)
+ return err;
+ }
+ }
+ list_for_each_safe(pos, tmp, &table->intersec_table_list) {
+ curr_intersec_table =
+ list_entry(pos,
+ typeof(*curr_intersec_table),
+ list);
+ list_del(pos);
+ if (atomic_read(&curr_intersec_table->items_ht.nelems)
+ != 0)
+ WARN_ON(1);
+
+ kfree(curr_intersec_table->mask);
+ kfree(curr_intersec_table);
+ }
+ }
+ WARN_ON_ONCE(!list_empty(&table->intersec_table_list));
+
+ list_del(&table->list);
+ rhashtable_destroy(&table->items_ht);
+ kfree(table->mask);
+ kfree(table);
+
+ prune->table_cnt--;
+
+ table_handle = NULL;
+ return 0;
+}
+EXPORT_SYMBOL(prune_table_remove);
+
+/**
+ * prune_item_add - adds an item to a table item should have same mask as table.
+ * @prune: prune object
+ * @table_handle: Add the item to this table identification.
+ * @item: The item to add.
+ *
+ * Returns EPERM for invalid parameter
+ * Returns ENOMEM in case allocation failed
+ * Return EEXIST if item already exists.
+ * otherwise it returns 0.
+ *
+ * Note: all locking must be provided by the caller.
+ */
+int prune_item_add(struct prune *prune, void *table_handle,
+ struct prune_item *item)
+{
+ const struct table_item_entry *tbl_entry;
+ struct table *table, *curr_table;
+ struct list_head *pos;
+ int err;
+
+ if (prune->mask_len != item->mask_len)
+ return -EPERM;
+
+ table = (struct table *) table_handle;
+
+ tbl_entry = table_item_add(prune, table, item);
+ if (IS_ERR(tbl_entry))
+ return PTR_ERR(tbl_entry);
+
+ /* add the item to the intersec tables of all tables*/
+ list_for_each(pos, &prune->table_list) {
+ curr_table = list_entry(pos, typeof(*curr_table), list);
+ err = intersec_list_item_add(curr_table, item, tbl_entry,
+ curr_table != table ?
+ true : false);
+ if (err) {
+ if (table_item_remove(table, item))
+ WARN_ON(1);
+
+ return err;
+ }
+ }
+ /* update prune vector of the corresponding items of the neigh table */
+ err = neigh_table_prune_vector_set(prune, table, item, tbl_entry,
+ true);
+ if (err) {
+ if (table_item_remove(table, item))
+ WARN_ON(1);
+ prune_item_remove(prune, table_handle, item);
+ return err;
+ }
+ return 0;
+}
+EXPORT_SYMBOL(prune_item_add);
+
+/**
+ * prune_item_remove - removes an item from a table
+ * @prune: prune object
+ * @table_handle: Remove the item from this table identification.
+ * @item: the item to remove.
+ *
+ * Returns EPERM for invalid parameter or item not found.
+ * Returns ENOMEM in case allocation failed.
+ * otherwise it returns 0.
+ *
+ * Note: all locking must be provided by the caller.
+ */
+int prune_item_remove(struct prune *prune, void *table_handle,
+ struct prune_item *item)
+{
+ struct table *table, *curr_table;
+ struct list_head *pos;
+ int err;
+
+ if (prune->mask_len != item->mask_len)
+ return -EPERM;
+
+ table = (struct table *) table_handle;
+
+ /* Remove the item from tables in the intersect tables */
+ list_for_each(pos, &prune->table_list) {
+ curr_table = list_entry(pos, typeof(*curr_table), list);
+ err = intersec_list_item_remove(curr_table, item,
+ curr_table != table ?
+ true : false);
+ if (err)
+ return err;
+ }
+
+ err = table_item_remove(table, item);
+ if (err)
+ return err;
+
+ /* update prune vector of the corresponding items of the neigh table */
+ err = neigh_table_prune_vector_set(prune, table, item, NULL, false);
+ if (err)
+ return err;
+ return 0;
+}
+EXPORT_SYMBOL(prune_item_remove);
+
+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,529 @@
+/*
+ * lib/test_prune.c - Test module for prune
+ * Copyright (c) 2018 Mellanox Technologies. All rights reserved.
+ * Copyright (c) 2018 Tal Bar <talb@mellanox.com>
+ *
+ * SPDX-License-Identifier: (GPL-2.0 WITH Linux-syscall-note OR BSD-2)
+ */
+
+#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 MASK_LEN (4)
+#define TABLE_1_ID 1
+#define TABLE_2_ID 2
+#define TABLE_3_ID 3
+
+static int flows_add_delete_items_1_notify_test_case;
+
+DECLARE_BITMAP(table_1_mask, 4);
+DECLARE_BITMAP(table_2_mask, 4);
+DECLARE_BITMAP(table_3_mask, 4);
+
+DECLARE_BITMAP(table_1_item1, 4);
+DECLARE_BITMAP(table_1_item2, 4);
+DECLARE_BITMAP(table_1_item3, 4);
+
+static const struct prune_table_attr table_1_params = {
+ .mask = table_1_mask,
+ .mask_len = MASK_LEN,
+ .priv = (void *)TABLE_1_ID,
+};
+
+static const struct prune_table_attr table_2_params = {
+ .mask = table_2_mask,
+ .mask_len = MASK_LEN,
+ .priv = (void *)TABLE_2_ID,
+};
+
+static const struct prune_table_attr table_3_params = {
+ .mask = table_3_mask,
+ .mask_len = MASK_LEN,
+ .priv = (void *)TABLE_3_ID,
+};
+
+static const struct prune_item item1_params = {
+ .priority = 1,
+ .mask = table_1_item1,
+ .mask_len = MASK_LEN,
+};
+
+static const struct prune_item item2_params = {
+ .priority = 2,
+ .mask = table_1_item2,
+ .mask_len = MASK_LEN,
+};
+
+static const struct prune_item item3_params = {
+ .priority = 3,
+ .mask = table_1_item3,
+ .mask_len = MASK_LEN,
+};
+
+static inline unsigned long *bm_kcalloc(int nbits)
+{
+ return kcalloc(1, BITS_TO_LONGS(nbits) * sizeof(unsigned long),
+ GFP_KERNEL);
+}
+
+static bool test_prune_flows_1_check_case(struct prune_item_notify *item,
+ unsigned int prio,
+ bool prune_0,
+ bool prune_1)
+{
+ struct prune_table *prune_table_item;
+ struct list_head *pos;
+ bool case_passed;
+ int table_id;
+
+ if (item->item.priority != prio) {
+ WARN(1, "test case [%d] didn't pass priority incorrect [%lu]",
+ flows_add_delete_items_1_notify_test_case,
+ item->item.priority);
+ return false;
+ }
+ table_id = 0;
+ list_for_each(pos, item->table_prune_list) {
+ prune_table_item = list_entry(pos, typeof(*prune_table_item),
+ list);
+ switch (table_id) {
+ case 0:
+ case_passed =
+ (uintptr_t)prune_table_item->priv == table_id &&
+ prune_table_item->is_prune == prune_0;
+ break;
+ case 1:
+ case_passed =
+ (uintptr_t)prune_table_item->priv == table_id &&
+ prune_table_item->is_prune == prune_1;
+ break;
+ default:
+ case_passed = false;
+ break;
+ }
+ table_id++;
+
+ if (!case_passed) {
+ WARN(1, "test case [%d] didn't pass for table [%d]",
+ flows_add_delete_items_1_notify_test_case,
+ table_id);
+ return case_passed;
+ }
+ }
+
+ return case_passed;
+}
+
+static void test_prune_flows_1_notify(void *table_handle,
+ struct prune_item_notify *item,
+ unsigned int item_cnt)
+{
+ struct prune_table *prune_table_item;
+ struct list_head *pos;
+ bool debug = false;
+ int i;
+
+ if (debug) {
+ i = 0;
+ pr_info("item mask: %lu\n", *item->item.mask);
+ pr_info("item prio: %lu\n", item->item.priority);
+
+ list_for_each(pos, item->table_prune_list) {
+ prune_table_item = list_entry(pos,
+ typeof(*prune_table_item),
+ list);
+ pr_info("i = [%d], table priv: %lu\tis prune: %s\tpruned table *: %p\n",
+ i,
+ (uintptr_t)prune_table_item->priv,
+ prune_table_item->is_prune ? "Yes" : "No",
+ prune_table_item->table_handle);
+ i++;
+ }
+ }
+
+ switch (flows_add_delete_items_1_notify_test_case) {
+ case 0:
+ test_prune_flows_1_check_case(item, 7, true, false);
+ break;
+ case 1:
+ test_prune_flows_1_check_case(item, 5, false, true);
+ break;
+ case 2:
+ test_prune_flows_1_check_case(item, 7, true, true);
+ break;
+ case 3:
+ test_prune_flows_1_check_case(item, 5, true, true);
+ break;
+ default:
+ WARN(1, "unexpected test case %d",
+ flows_add_delete_items_1_notify_test_case);
+ break;
+ }
+
+ flows_add_delete_items_1_notify_test_case++;
+}
+
+static void test_prune_basic_notify(void *table_handle,
+ struct prune_item_notify *item,
+ unsigned int item_cnt)
+{
+ bool debug = false;
+ struct prune_table *prune_table_item;
+ struct list_head *pos;
+ int i;
+
+ /* TODO: add basic test assurance, currently only printing if wanted */
+ if (debug) {
+ i = 0;
+ pr_info("item mask: %lu\n", *item->item.mask);
+ pr_info("item prio: %lu\n", item->item.priority);
+
+ list_for_each(pos, item->table_prune_list) {
+ prune_table_item = list_entry(pos,
+ typeof(*prune_table_item),
+ list);
+ pr_info("i = [%d], table priv: %lu\t is prune: %s\t pruned table *: %p\n",
+ i,
+ (uintptr_t)prune_table_item->priv,
+ prune_table_item->is_prune ? "Yes" : "No",
+ prune_table_item->table_handle);
+ i++;
+ }
+ }
+}
+
+static const struct prune_ops test_prune_flows_add_delete_items_1_ops = {
+ .prune_item_notify = test_prune_flows_1_notify,
+ .prune_mask_comparable = NULL,
+};
+
+static const struct prune_ops test_prune_basic_ops = {
+ .prune_item_notify = test_prune_basic_notify,
+ .prune_mask_comparable = NULL,
+};
+
+static int table_attr_create(struct prune_table_attr *table_attr,
+ unsigned int mask_len,
+ unsigned int table_cnt)
+{
+ unsigned long i, j;
+
+ for (i = 0; i < table_cnt; i++) {
+ table_attr[i].mask = bm_kcalloc(mask_len);
+ if (!table_attr[i].mask) {
+ if (i > 0) {
+ for (j = i - 1; j > -1; j--)
+ kfree(table_attr[j].mask);
+ }
+ return -ENOMEM;
+ }
+ table_attr[i].mask_len = mask_len;
+ table_attr[i].priv = (int *)i;
+ }
+ return 0;
+}
+
+static void table_attr_destroy(struct prune_table_attr *table_attr,
+ unsigned int table_cnt)
+{
+ int i;
+
+ for (i = 0; i < table_cnt; i++)
+ kfree(table_attr[i].mask);
+}
+
+/*
+ * basic test: test add / revmoe table and item without checking their prune
+ * vector
+ */
+static int test_prune_basic(void)
+{
+ struct prune_ret_table ret_table_1, ret_table_2, ret_table_3;
+ struct prune_table_attr table_attr1 = table_1_params;
+ struct prune_table_attr table_attr2 = table_2_params;
+ struct prune_table_attr table_attr3 = table_3_params;
+ const struct prune_ops *ops = &test_prune_basic_ops;
+ struct prune_item item1 = item1_params;
+ struct prune_item item2 = item2_params;
+ struct prune_item item3 = item3_params;
+ struct prune *prune;
+ int err;
+
+ bitmap_clear(table_attr1.mask, 0, table_attr1.mask_len);
+ bitmap_clear(table_attr2.mask, 0, table_attr2.mask_len);
+ bitmap_clear(table_attr3.mask, 0, table_attr3.mask_len);
+ bitmap_clear(item1.mask, 0, item1.mask_len);
+ bitmap_clear(item2.mask, 0, item2.mask_len);
+ bitmap_clear(item3.mask, 0, item3.mask_len);
+
+ bitmap_set(table_attr1.mask, 0, 2);
+ bitmap_set(table_attr2.mask, 1, 2);
+ bitmap_set(table_attr3.mask, 2, 2);
+
+ bitmap_set(item1.mask, 0, 2);
+ bitmap_set(item2.mask, 1, 2);
+ bitmap_set(item3.mask, 2, 2);
+
+ prune = prune_init(MASK_LEN, ops, NULL);
+ if (IS_ERR(prune))
+ return PTR_ERR(prune);
+
+ err = prune_table_add(prune, &table_attr1, &ret_table_1);
+ if (err)
+ return err;
+
+ err = prune_table_add(prune, &table_attr2, &ret_table_2);
+ if (err)
+ return err;
+
+ err = prune_table_add(prune, &table_attr3, &ret_table_3);
+ if (err)
+ return err;
+
+ err = prune_item_add(prune, ret_table_1.table_handle, &item1);
+ if (err)
+ return err;
+
+ err = prune_item_add(prune, ret_table_2.table_handle, &item2);
+ if (err)
+ return err;
+
+ /* negative test */
+ err = prune_item_remove(prune, ret_table_3.table_handle, &item3);
+ if (err != -EPERM)
+ return err;
+
+ err = prune_item_add(prune, ret_table_3.table_handle, &item3);
+ if (err)
+ return err;
+
+ err = prune_item_remove(prune, ret_table_1.table_handle, &item1);
+ if (err)
+ return err;
+
+ err = prune_item_remove(prune, ret_table_2.table_handle, &item2);
+ if (err)
+ return err;
+
+ err = prune_item_remove(prune, ret_table_3.table_handle, &item3);
+ if (err)
+ return err;
+
+ prune_table_remove(prune, ret_table_1.table_handle);
+
+ prune_table_remove(prune, ret_table_2.table_handle);
+
+ prune_table_remove(prune, ret_table_3.table_handle);
+
+ prune_fini(prune);
+
+ return err;
+}
+
+static int test_prune_flows_add_delete_items_1(void)
+{
+ struct prune *prune;
+ int err;
+ const struct prune_ops *ops = &test_prune_flows_add_delete_items_1_ops;
+ #define TBL_CNT (2)
+ struct prune_table_attr table_attr[TBL_CNT];
+ struct prune_ret_table ret_table[TBL_CNT];
+ struct prune_item item1, item2, item3;
+ unsigned int nbits = 40;
+
+ /* init test case identifier */
+ flows_add_delete_items_1_notify_test_case = 0;
+
+ prune = prune_init(nbits, ops, NULL);
+ if (!prune)
+ return -EPERM;
+
+ err = table_attr_create(table_attr, nbits, TBL_CNT);
+ 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*/
+ err = prune_table_add(prune, &table_attr[0], &ret_table[0]);
+ if (err)
+ return err;
+
+ /* 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*/
+ err = prune_table_add(prune, &table_attr[1], &ret_table[1]);
+ if (err)
+ return err;
+
+ /* create item1 x.2.3.4.x prio 10 */
+ item1.mask = bm_kcalloc(nbits);
+ if (!item1.mask)
+ return -ENOMEM;
+
+ item1.mask_len = nbits;
+ item1.priority = 10;
+ item1.priv = NULL;
+ bitmap_clear(item1.mask, 0, item1.mask_len);
+ bitmap_set(item1.mask, 14, 1); /* set 2 on #2 byte*/
+ bitmap_set(item1.mask, 22, 2); /* set 3 on #3 byte*/
+ bitmap_set(item1.mask, 29, 1); /* set 4 on #4 byte*/
+
+ /* create item2 x.2.3.5.x prio 5*/
+ item2.mask = bm_kcalloc(nbits);
+ if (!item2.mask)
+ return -ENOMEM;
+
+ item2.mask_len = nbits;
+ item2.priority = 5;
+ item2.priv = NULL;
+ bitmap_clear(item2.mask, 0, item2.mask_len);
+ bitmap_set(item2.mask, 14, 1); /* set 2 on #2 byte*/
+ bitmap_set(item2.mask, 22, 2); /* set 3 on #3 byte*/
+ bitmap_set(item2.mask, 29, 1); /* set 5 on #4 byte*/
+ bitmap_set(item2.mask, 31, 1); /* set 5 on #4 byte*/
+
+ /* Add item1: x.2.3.4.x to table 1 */
+ err = prune_item_add(prune, ret_table[1].table_handle, &item1);
+ if (err)
+ return err;
+
+ /* expected prune vector for item1 and item2
+ * table 0 prune
+ * table 1 prune
+ * --> shoudn't not get notification
+ */
+
+ /* Add item2: x.2.3.5.x to table 1 */
+ err = prune_item_add(prune, ret_table[1].table_handle, &item2);
+ if (err)
+ return err;
+
+ /* expected prune vector for both item
+ * table 0 prune
+ * table 1 prune
+ * --> shoudn't not get notification
+ */
+
+ /* create item3 1.2.3.x.x prio 7 */
+ item3.mask = bm_kcalloc(nbits);
+ if (!item3.mask)
+ return -ENOMEM;
+ item3.mask_len = nbits;
+ item3.priority = 7;
+ item3.priv = NULL;
+ bitmap_clear(item3.mask, 0, item1.mask_len);
+ bitmap_set(item3.mask, 7, 1); /* set 1 on #1 byte*/
+ bitmap_set(item3.mask, 14, 1); /* set 2 on #2 byte*/
+ bitmap_set(item3.mask, 22, 2); /* set 3 on #3 byte*/
+
+ /* Add item3: 1.2.3.x.x prio 7 to table 0 */
+ err = prune_item_add(prune, ret_table[0].table_handle, &item3);
+ if (err)
+ return err;
+
+ /* expected prune vector per item
+ * item1 in table 1: (x.2.3.4.x prio 10)
+ * table 0 prune (no change)
+ * table 1 prune (no change)
+ * --> shoudn't not get notification
+ *item2 in table 1(x.2.3.5.x prio 5):
+ * table 0 don't prune (changed)
+ * table 1 prune (changed)
+ * --> Should get notification
+ *item3 in table 0 (1.2.3.x.x prio 7):
+ * table 0 prune (no change)
+ * table 1 don't prune (no change)
+ * --> Should get notification
+ */
+
+ /* delete item: 1: (x.2.3.4.x prio 10 from table 1 */
+ err = prune_item_remove(prune, ret_table[1].table_handle, &item1);
+ if (err)
+ return err;
+
+ /* expected prune vector
+ * item1: item is deleted
+
+ *item2 table 1(x.2.3.5.x prio 5)::
+ * table 0 don't prune
+ * table 1 prune
+ *item3 table 0 (1.2.3.x.x prio 7):
+ * table 0 prune
+ * table 1 prune (changed)
+ */
+
+ /* delete item: 3: (1.2.3.x.x prio 7) from table 0 */
+ err = prune_item_remove(prune, ret_table[0].table_handle, &item3);
+ if (err)
+ return err;
+
+ /* expected prune vector
+ * item1: item is deleted
+
+ *item2 table 1(x.2.3.5.x prio 5)::
+ * table 0 prune (changed)
+ * table 1 prune
+ *item3 table 0 (1.2.3.x.x prio 7):
+ * item is deleted
+ */
+
+ /* delete item: 2: (x.2.3.5.x prio 5) from table 1 */
+ err = prune_item_remove(prune, ret_table[1].table_handle, &item2);
+ if (err)
+ return err;
+
+ err = prune_table_remove(prune, ret_table[0].table_handle);
+ if (err)
+ return err;
+
+ err = prune_table_remove(prune, ret_table[1].table_handle);
+ if (err)
+ return err;
+
+ prune_fini(prune);
+
+ table_attr_destroy(table_attr, TBL_CNT);
+ kfree(item1.mask);
+ kfree(item2.mask);
+ kfree(item3.mask);
+
+ 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;
+
+ return 0;
+}
+
+static int __init test_prune_init(void)
+{
+ return test_prune();
+}
+
+static void __exit test_prune_exit(void)
+{
+}
+
+module_init(test_prune_init);
+module_exit(test_prune_exit);
+
+MODULE_LICENSE("Dual BSD/GPL");
+MODULE_AUTHOR("Tal Bar <talb@mellanox.com>");
+MODULE_DESCRIPTION("Test module for prune");
The prune library aim: reduce number of lookups (by prune) between tables within same prune object. Pruning save time complexity by do lookups only on the relevant tables, this eliminate the need to search items in other tables based on item priority and mask. For further details please check: Documentation/prune.txt Alongside this, a testing module is introduced as well. Signed-off-by: Tal Bar <talb@mellanox.com> --- v2 -> v3: * Add A --> A* and A* --> A flows for the algorithm * Add Documnatation file for prune v1 * Add prune vector check in test prune module * Add prune notify example to test prune module * Update commit message v1 -> v2: * API implemantaion * Add test_prune - a simple example on how to use prune library. --- Documentation/prune.txt | 126 +++++ MAINTAINERS | 8 + include/linux/prune.h | 89 ++++ lib/Kconfig | 6 + lib/Kconfig.debug | 10 + lib/Makefile | 3 + lib/prune.c | 1232 +++++++++++++++++++++++++++++++++++++++++++++++ lib/test_prune.c | 529 ++++++++++++++++++++ 8 files changed, 2003 insertions(+) create mode 100644 Documentation/prune.txt create mode 100644 include/linux/prune.h create mode 100644 lib/prune.c create mode 100644 lib/test_prune.c