All of lore.kernel.org
 help / color / mirror / Atom feed
* [PATCH 1/2] dbus: Better search for matching rules in the filter tree
@ 2016-04-29  3:31 Andrew Zaborowski
  2016-04-29  3:31 ` [PATCH 2/2] unit: test a filter tree scenario with unordered paths Andrew Zaborowski
                   ` (15 more replies)
  0 siblings, 16 replies; 34+ messages in thread
From: Andrew Zaborowski @ 2016-04-29  3:31 UTC (permalink / raw)
  To: ell

[-- Attachment #1: Type: text/plain, Size: 4637 bytes --]

When adding new filter rules, perform a more complete search for
existing rules that already cover the rule being added by removing the
requierement that levels in the tree are ordered by the match type.
This may add overhead to adding new rules in some situations but will
reduce the number of server-side rules being used and the number of
requests.  This covers a scenario where first a watch is added for:

type=signal, path=/

followed by

type=signal, sender=org.test, path=/

I believe there are some more tricky scenarios which are not covered
specifically when more than one child of an existing node matches some
condition of the rule being added.
---
 ell/dbus-filter.c  | 67 +++++++++++++++++++++++++++++++++++++++++++-----------
 ell/dbus-private.h |  8 +++----
 2 files changed, 58 insertions(+), 17 deletions(-)

diff --git a/ell/dbus-filter.c b/ell/dbus-filter.c
index 42755a9..9e3cad5 100644
--- a/ell/dbus-filter.c
+++ b/ell/dbus-filter.c
@@ -234,34 +234,63 @@ static bool remove_recurse(struct _dbus_filter *filter,
 }
 
 unsigned int _dbus_filter_add_rule(struct _dbus_filter *filter,
-					struct _dbus_filter_condition *rule,
-					int rule_len,
-					l_dbus_message_func_t signal_func,
-					void *user_data)
+				const struct _dbus_filter_condition *rule,
+				int rule_len,
+				l_dbus_message_func_t signal_func,
+				void *user_data)
 {
 	struct filter_node **node_ptr = &filter->root;
 	struct filter_node *node;
 	struct filter_node *parent = filter->root;
 	bool remote_rule = false;
-	struct _dbus_filter_condition *condition, *end = rule + rule_len;
-
-	qsort(rule, rule_len, sizeof(*rule), condition_compare);
-
-	for (condition = rule; condition < end; condition++) {
-		/* See if this condition is already a child of the node */
+	struct _dbus_filter_condition sorted[rule_len];
+	struct _dbus_filter_condition *unused, *condition;
+	struct _dbus_filter_condition *end = sorted + rule_len;
+
+	memcpy(sorted, rule, sizeof(sorted));
+	qsort(sorted, rule_len, sizeof(*condition), condition_compare);
+
+	/*
+	 * Find or create a path in the tree with a node for each
+	 * condition in the rule, loop until all conditions have been
+	 * used.
+	 */
+	unused = sorted;
+	while (unused < end) {
+		/*
+		 * Find a child of the node that matches any unused
+		 * condition.  Note there could be multiple matches, we're
+		 * happy with the first we can find.
+		 */
 		while (*node_ptr) {
 			node = *node_ptr;
 
-			if (node->type == condition->type &&
-					!strcmp(node->match.value,
+			for (condition = unused; condition < end; condition++) {
+				if (condition->type > node->type) {
+					condition = end;
+					break;
+				}
+
+				if (condition->type < node->type ||
+						condition->type ==
+						L_DBUS_MATCH_NONE)
+					continue;
+
+				if (!strcmp(node->match.value,
 						condition->value))
+					break;
+			}
+
+			if (condition < end)
 				break;
 
 			node_ptr = &node->next;
 		}
 
-		/* Add one */
+		/* Add a node */
 		if (!*node_ptr) {
+			condition = unused;
+
 			node = l_new(struct filter_node, 1);
 			node->type = condition->type;
 			node->match.value = l_strdup(condition->value);
@@ -278,6 +307,18 @@ unsigned int _dbus_filter_add_rule(struct _dbus_filter *filter,
 
 		}
 
+		/*
+		 * Mark the condition used.  We do this by setting
+		 * condition->type to an invalid value unless it is the
+		 * first condition left in which case we can push the
+		 * rule start.  Another option is to always push the rule
+		 * start and memmove the still unused conditions by one
+		 * if necessary.
+		 */
+		condition->type = L_DBUS_MATCH_NONE;
+		while (unused < end && unused[0].type == L_DBUS_MATCH_NONE)
+			unused++;
+
 		node_ptr = &node->match.children;
 
 		parent = node;
diff --git a/ell/dbus-private.h b/ell/dbus-private.h
index ab52895..f4209b8 100644
--- a/ell/dbus-private.h
+++ b/ell/dbus-private.h
@@ -320,10 +320,10 @@ struct _dbus_filter *_dbus_filter_new(struct l_dbus *dbus,
 void _dbus_filter_free(struct _dbus_filter *filter);
 
 unsigned int _dbus_filter_add_rule(struct _dbus_filter *filter,
-					struct _dbus_filter_condition *rule,
-					int rule_len,
-					l_dbus_message_func_t signal_func,
-					void *user_data);
+				const struct _dbus_filter_condition *rule,
+				int rule_len,
+				l_dbus_message_func_t signal_func,
+				void *user_data);
 bool _dbus_filter_remove_rule(struct _dbus_filter *filter, unsigned int id);
 
 char *_dbus_filter_rule_to_str(const struct _dbus_filter_condition *rule,
-- 
2.5.0


^ permalink raw reply related	[flat|nested] 34+ messages in thread

end of thread, other threads:[~2016-05-03 19:09 UTC | newest]

Thread overview: 34+ messages (download: mbox.gz follow: Atom feed
-- links below jump to the message on this page --
2016-04-29  3:31 [PATCH 1/2] dbus: Better search for matching rules in the filter tree Andrew Zaborowski
2016-04-29  3:31 ` [PATCH 2/2] unit: test a filter tree scenario with unordered paths Andrew Zaborowski
2016-05-03 19:09   ` Denis Kenzior
2016-04-29  3:31 ` [PATCH 1/2] dbus: Fix Dbus1 parsing of doubles Andrew Zaborowski
2016-04-29 15:21   ` Denis Kenzior
2016-04-29  3:31 ` [PATCH 2/2] unit: Fix typos that make the assertions always true Andrew Zaborowski
2016-04-29 15:22   ` Denis Kenzior
2016-04-29  3:31 ` [PATCH] dbus: Don't use KDBUS_ATTACH_NAMES for kdbus connection Andrew Zaborowski
2016-04-29 15:23   ` Denis Kenzior
2016-04-29  3:31 ` [PATCH 01/11] dbus: Accept a list of FDs in dbus_message_from_blob Andrew Zaborowski
2016-04-29 15:30   ` Denis Kenzior
2016-04-29  3:31 ` [PATCH 02/11] unit: Update dbus tests to use new dbus_message_from_blob prototype Andrew Zaborowski
2016-04-29 15:30   ` Denis Kenzior
2016-04-29  3:32 ` [PATCH 03/11] dbus: Validate the size of fd list in dbus_message_build Andrew Zaborowski
2016-04-29 15:30   ` Denis Kenzior
2016-04-29  3:32 ` [PATCH 04/11] dbus: Handle the 'y' type in append_arguments Andrew Zaborowski
2016-04-29 15:50   ` Denis Kenzior
2016-04-29 21:43     ` Andrzej Zaborowski
2016-04-29  3:32 ` [PATCH 05/11] dbus: Check the FD array size in l_dbus_message_builder_append_from_iter Andrew Zaborowski
2016-04-29 15:51   ` Denis Kenzior
2016-04-29  3:32 ` [PATCH 06/11] dbus: Add utility to get FD array for a message Andrew Zaborowski
2016-04-29 15:51   ` Denis Kenzior
2016-04-29  3:32 ` [PATCH 07/11] dbus: Attach FDs to Dbus1 messages being sent Andrew Zaborowski
2016-04-29 15:51   ` Denis Kenzior
2016-04-29  3:32 ` [PATCH 08/11] dbus: Remove memcpy and fix setting of FD_CLOEXEC on FDs Andrew Zaborowski
2016-04-29 16:11   ` Denis Kenzior
2016-04-29 21:46     ` Andrzej Zaborowski
2016-04-29  3:32 ` [PATCH 09/11] dbus: Attach FDs to kdbus messages being sent Andrew Zaborowski
2016-04-29 16:13   ` Denis Kenzior
2016-04-29  3:32 ` [PATCH 10/11] dbus: Handle received KDBUS_ITEM_FDS Andrew Zaborowski
2016-04-29 16:14   ` Denis Kenzior
2016-04-29  3:32 ` [PATCH 11/11] unit: 'h' type parsing and building tests Andrew Zaborowski
2016-04-29 16:16   ` Denis Kenzior
2016-05-03 19:09 ` [PATCH 1/2] dbus: Better search for matching rules in the filter tree Denis Kenzior

This is an external index of several public inboxes,
see mirroring instructions on how to clone and mirror
all data and code used by this external index.