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