1 /*-*- Mode: C; c-basic-offset: 8; indent-tabs-mode: nil -*-*/
4 This file is part of systemd.
6 Copyright 2013 Lennart Poettering
8 systemd is free software; you can redistribute it and/or modify it
9 under the terms of the GNU Lesser General Public License as published by
10 the Free Software Foundation; either version 2.1 of the License, or
11 (at your option) any later version.
13 systemd is distributed in the hope that it will be useful, but
14 WITHOUT ANY WARRANTY; without even the implied warranty of
15 MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU
16 Lesser General Public License for more details.
18 You should have received a copy of the GNU Lesser General Public License
19 along with systemd; If not, see <http://www.gnu.org/licenses/>.
22 #include "bus-internal.h"
23 #include "bus-message.h"
24 #include "bus-match.h"
28 * A: type=signal,sender=foo,interface=bar
29 * B: type=signal,sender=quux,interface=fips
30 * C: type=signal,sender=quux,interface=waldo
31 * D: type=signal,member=test
36 * results in this tree:
39 * + BUS_MATCH_MESSAGE_TYPE
40 * | ` BUS_MATCH_VALUE: value == signal
41 * | + DBUS_MATCH_SENDER
42 * | | + BUS_MATCH_VALUE: value == foo
43 * | | | ` DBUS_MATCH_INTERFACE
44 * | | | ` BUS_MATCH_VALUE: value == bar
45 * | | | ` BUS_MATCH_LEAF: A
46 * | | ` BUS_MATCH_VALUE: value == quux
47 * | | ` DBUS_MATCH_INTERFACE
48 * | | | BUS_MATCH_VALUE: value == fips
49 * | | | ` BUS_MATCH_LEAF: B
50 * | | ` BUS_MATCH_VALUE: value == waldo
51 * | | ` BUS_MATCH_LEAF: C
52 * | + DBUS_MATCH_MEMBER
53 * | | ` BUS_MATCH_VALUE: value == test
54 * | | ` BUS_MATCH_LEAF: D
55 * | + BUS_MATCH_LEAF: F
56 * | ` BUS_MATCH_LEAF: G
58 * ` BUS_MATCH_VALUE: value == miau
62 static inline bool BUS_MATCH_IS_COMPARE(enum bus_match_node_type t) {
63 return t >= BUS_MATCH_MESSAGE_TYPE && t <= BUS_MATCH_ARG_NAMESPACE_LAST;
66 static inline bool BUS_MATCH_CAN_HASH(enum bus_match_node_type t) {
67 return (t >= BUS_MATCH_MESSAGE_TYPE && t <= BUS_MATCH_PATH) ||
68 (t >= BUS_MATCH_ARG && t <= BUS_MATCH_ARG_LAST);
71 static void bus_match_node_free(struct bus_match_node *node) {
75 assert(node->type != BUS_MATCH_ROOT);
76 assert(node->type < _BUS_MATCH_NODE_TYPE_MAX);
78 if (node->parent->child) {
79 /* We are apparently linked into the parent's child
80 * list. Let's remove us from there. */
82 assert(node->prev->next == node);
83 node->prev->next = node->next;
85 assert(node->parent->child == node);
86 node->parent->child = node->next;
90 node->next->prev = node->prev;
93 if (node->type == BUS_MATCH_VALUE) {
94 /* We might be in the parent's hash table, so clean
97 if (node->parent->type == BUS_MATCH_MESSAGE_TYPE)
98 hashmap_remove(node->parent->compare.children, UINT_TO_PTR(node->value.u8));
99 else if (BUS_MATCH_CAN_HASH(node->parent->type) && node->value.str)
100 hashmap_remove(node->parent->compare.children, node->value.str);
102 free(node->value.str);
105 if (BUS_MATCH_IS_COMPARE(node->type)) {
106 assert(hashmap_isempty(node->compare.children));
107 hashmap_free(node->compare.children);
113 static bool bus_match_node_maybe_free(struct bus_match_node *node) {
119 if (BUS_MATCH_IS_COMPARE(node->type) && !hashmap_isempty(node->compare.children))
122 bus_match_node_free(node);
126 static bool value_node_test(
127 struct bus_match_node *node,
128 enum bus_match_node_type parent_type,
130 const char *value_str) {
133 assert(node->type == BUS_MATCH_VALUE);
135 /* Tests parameters against this value node, doing prefix
136 * magic and stuff. */
138 switch (parent_type) {
140 case BUS_MATCH_MESSAGE_TYPE:
141 return node->value.u8 == value_u8;
143 case BUS_MATCH_SENDER:
144 case BUS_MATCH_DESTINATION:
145 case BUS_MATCH_INTERFACE:
146 case BUS_MATCH_MEMBER:
148 case BUS_MATCH_ARG ... BUS_MATCH_ARG_LAST:
149 return streq(node->value.str, value_str);
151 case BUS_MATCH_ARG_NAMESPACE ... BUS_MATCH_ARG_NAMESPACE_LAST:
152 return namespace_simple_pattern(node->value.str, value_str);
154 case BUS_MATCH_PATH_NAMESPACE:
155 return path_simple_pattern(node->value.str, value_str);
157 case BUS_MATCH_ARG_PATH ... BUS_MATCH_ARG_PATH_LAST:
158 return path_complex_pattern(node->value.str, value_str);
161 assert_not_reached("Invalid node type");
165 static bool value_node_same(
166 struct bus_match_node *node,
167 enum bus_match_node_type parent_type,
169 const char *value_str) {
171 /* Tests parameters against this value node, not doing prefix
172 * magic and stuff, i.e. this one actually compares the match
176 assert(node->type == BUS_MATCH_VALUE);
178 switch (parent_type) {
180 case BUS_MATCH_MESSAGE_TYPE:
181 return node->value.u8 == value_u8;
183 case BUS_MATCH_SENDER:
184 case BUS_MATCH_DESTINATION:
185 case BUS_MATCH_INTERFACE:
186 case BUS_MATCH_MEMBER:
188 case BUS_MATCH_ARG ... BUS_MATCH_ARG_LAST:
189 case BUS_MATCH_ARG_NAMESPACE ... BUS_MATCH_ARG_NAMESPACE_LAST:
190 case BUS_MATCH_PATH_NAMESPACE:
191 case BUS_MATCH_ARG_PATH ... BUS_MATCH_ARG_PATH_LAST:
192 return streq(node->value.str, value_str);
195 assert_not_reached("Invalid node type");
201 struct bus_match_node *node,
206 const char *test_str = NULL;
215 /* Not these special semantics: when traversing the tree we
216 * usually let bus_match_run() when called for a node
217 * recursively invoke bus_match_run(). There's are two
218 * exceptions here though, which are BUS_NODE_ROOT (which
219 * cannot have a sibling), and BUS_NODE_VALUE (whose siblings
220 * are invoked anyway by its parent. */
222 switch (node->type) {
226 /* Run all children. Since we cannot have any siblings
227 * we won't call any. The children of the root node
228 * are compares or leaves, they will automatically
229 * call their siblings. */
230 return bus_match_run(bus, node->child, ret, m);
232 case BUS_MATCH_VALUE:
234 /* Run all children. We don't execute any siblings, we
235 * assume our caller does that. The children of value
236 * nodes are compares or leaves, they will
237 * automatically call their siblings */
240 return bus_match_run(bus, node->child, ret, m);
244 /* Run the callback. And then invoke siblings. */
245 assert(node->leaf.callback);
246 r = node->leaf.callback(bus, ret, m, node->leaf.userdata);
250 return bus_match_run(bus, node->next, ret, m);
252 case BUS_MATCH_MESSAGE_TYPE:
253 test_u8 = m->header->type;
256 case BUS_MATCH_SENDER:
257 test_str = m->sender;
258 /* FIXME: resolve test_str from a well-known to a unique name first */
261 case BUS_MATCH_DESTINATION:
262 test_str = m->destination;
265 case BUS_MATCH_INTERFACE:
266 test_str = m->interface;
269 case BUS_MATCH_MEMBER:
270 test_str = m->member;
274 case BUS_MATCH_PATH_NAMESPACE:
278 case BUS_MATCH_ARG ... BUS_MATCH_ARG_LAST:
279 test_str = bus_message_get_arg(m, node->type - BUS_MATCH_ARG);
282 case BUS_MATCH_ARG_PATH ... BUS_MATCH_ARG_PATH_LAST:
283 test_str = bus_message_get_arg(m, node->type - BUS_MATCH_ARG_PATH);
286 case BUS_MATCH_ARG_NAMESPACE ... BUS_MATCH_ARG_NAMESPACE_LAST:
287 test_str = bus_message_get_arg(m, node->type - BUS_MATCH_ARG_NAMESPACE);
291 assert_not_reached("Unknown match type.");
294 if (BUS_MATCH_CAN_HASH(node->type)) {
295 struct bus_match_node *found;
297 /* Lookup via hash table, nice! So let's jump directly. */
300 found = hashmap_get(node->compare.children, test_str);
301 else if (node->type == BUS_MATCH_MESSAGE_TYPE)
302 found = hashmap_get(node->compare.children, UINT_TO_PTR(test_u8));
307 r = bus_match_run(bus, found, ret, m);
312 struct bus_match_node *c;
314 /* No hash table, so let's iterate manually... */
316 for (c = node->child; c; c = c->next) {
317 if (!value_node_test(c, node->type, test_u8, test_str))
320 r = bus_match_run(bus, c, ret, m);
326 /* And now, let's invoke our siblings */
327 return bus_match_run(bus, node->next, ret, m);
330 static int bus_match_add_compare_value(
331 struct bus_match_node *where,
332 enum bus_match_node_type t,
334 const char *value_str,
335 struct bus_match_node **ret) {
337 struct bus_match_node *c = NULL, *n = NULL;
341 assert(where->type == BUS_MATCH_ROOT || where->type == BUS_MATCH_VALUE);
342 assert(BUS_MATCH_IS_COMPARE(t));
345 for (c = where->child; c && c->type != t; c = c->next)
349 /* Comparison node already exists? Then let's see if
350 * the value node exists too. */
352 if (t == BUS_MATCH_MESSAGE_TYPE)
353 n = hashmap_get(c->compare.children, UINT_TO_PTR(value_u8));
354 else if (BUS_MATCH_CAN_HASH(t))
355 n = hashmap_get(c->compare.children, value_str);
357 for (n = c->child; n && !value_node_same(n, t, value_u8, value_str); n = n->next)
366 /* Comparison node, doesn't exist yet? Then let's
369 c = new0(struct bus_match_node, 1);
377 c->next = where->child;
382 if (t == BUS_MATCH_MESSAGE_TYPE) {
383 c->compare.children = hashmap_new(trivial_hash_func, trivial_compare_func);
384 if (!c->compare.children) {
388 } else if (BUS_MATCH_CAN_HASH(t)) {
389 c->compare.children = hashmap_new(string_hash_func, string_compare_func);
390 if (!c->compare.children) {
397 n = new0(struct bus_match_node, 1);
403 n->type = BUS_MATCH_VALUE;
404 n->value.u8 = value_u8;
406 n->value.str = strdup(value_str);
414 if (c->compare.children) {
416 if (t == BUS_MATCH_MESSAGE_TYPE)
417 r = hashmap_put(c->compare.children, UINT_TO_PTR(value_u8), n);
419 r = hashmap_put(c->compare.children, n->value.str, n);
435 bus_match_node_maybe_free(c);
445 static int bus_match_find_compare_value(
446 struct bus_match_node *where,
447 enum bus_match_node_type t,
449 const char *value_str,
450 struct bus_match_node **ret) {
452 struct bus_match_node *c, *n;
455 assert(where->type == BUS_MATCH_ROOT || where->type == BUS_MATCH_VALUE);
456 assert(BUS_MATCH_IS_COMPARE(t));
459 for (c = where->child; c && c->type != t; c = c->next)
465 if (t == BUS_MATCH_MESSAGE_TYPE)
466 n = hashmap_get(c->compare.children, UINT_TO_PTR(value_u8));
467 else if (BUS_MATCH_CAN_HASH(t))
468 n = hashmap_get(c->compare.children, value_str);
470 for (n = c->child; !value_node_same(n, t, value_u8, value_str); n = n->next)
482 static int bus_match_add_leaf(
483 struct bus_match_node *where,
484 sd_bus_message_handler_t callback,
486 struct bus_match_node **ret) {
488 struct bus_match_node *n;
491 assert(where->type == BUS_MATCH_ROOT || where->type == BUS_MATCH_VALUE);
494 n = new0(struct bus_match_node, 1);
498 n->type = BUS_MATCH_LEAF;
500 n->next = where->child;
503 n->leaf.callback = callback;
504 n->leaf.userdata = userdata;
512 static int bus_match_find_leaf(
513 struct bus_match_node *where,
514 sd_bus_message_handler_t callback,
516 struct bus_match_node **ret) {
518 struct bus_match_node *c;
521 assert(where->type == BUS_MATCH_ROOT || where->type == BUS_MATCH_VALUE);
524 for (c = where->child; c; c = c->next) {
525 if (c->type == BUS_MATCH_LEAF &&
526 c->leaf.callback == callback &&
527 c->leaf.userdata == userdata) {
536 enum bus_match_node_type bus_match_node_type_from_string(const char *k, size_t n) {
539 if (n == 4 && memcmp(k, "type", 4) == 0)
540 return BUS_MATCH_MESSAGE_TYPE;
541 if (n == 6 && memcmp(k, "sender", 6) == 0)
542 return BUS_MATCH_SENDER;
543 if (n == 11 && memcmp(k, "destination", 11) == 0)
544 return BUS_MATCH_DESTINATION;
545 if (n == 9 && memcmp(k, "interface", 9) == 0)
546 return BUS_MATCH_INTERFACE;
547 if (n == 6 && memcmp(k, "member", 6) == 0)
548 return BUS_MATCH_MEMBER;
549 if (n == 4 && memcmp(k, "path", 4) == 0)
550 return BUS_MATCH_PATH;
551 if (n == 14 && memcmp(k, "path_namespace", 14) == 0)
552 return BUS_MATCH_PATH_NAMESPACE;
554 if (n == 4 && memcmp(k, "arg", 3) == 0) {
561 return BUS_MATCH_ARG + j;
564 if (n == 5 && memcmp(k, "arg", 3) == 0) {
566 enum bus_match_node_type t;
573 t = BUS_MATCH_ARG + a * 10 + b;
574 if (t > BUS_MATCH_ARG_LAST)
580 if (n == 8 && memcmp(k, "arg", 3) == 0 && memcmp(k + 4, "path", 4) == 0) {
587 return BUS_MATCH_ARG_PATH + j;
590 if (n == 9 && memcmp(k, "arg", 3) == 0 && memcmp(k + 5, "path", 4) == 0) {
591 enum bus_match_node_type t;
599 t = BUS_MATCH_ARG_PATH + a * 10 + b;
600 if (t > BUS_MATCH_ARG_PATH_LAST)
606 if (n == 13 && memcmp(k, "arg", 3) == 0 && memcmp(k + 4, "namespace", 9) == 0) {
613 return BUS_MATCH_ARG_NAMESPACE + j;
616 if (n == 14 && memcmp(k, "arg", 3) == 0 && memcmp(k + 5, "namespace", 9) == 0) {
617 enum bus_match_node_type t;
625 t = BUS_MATCH_ARG_NAMESPACE + a * 10 + b;
626 if (t > BUS_MATCH_ARG_NAMESPACE_LAST)
635 struct match_component {
636 enum bus_match_node_type type;
641 static int match_component_compare(const void *a, const void *b) {
642 const struct match_component *x = a, *y = b;
644 if (x->type < y->type)
646 if (x->type > y->type)
652 static void free_components(struct match_component *components, unsigned n_components) {
655 for (i = 0; i < n_components; i++)
656 free(components[i].value_str);
661 static int parse_match(
663 struct match_component **_components,
664 unsigned *_n_components) {
666 const char *p = match;
667 struct match_component *components = NULL;
668 size_t components_allocated = 0;
669 unsigned n_components = 0, i;
670 _cleanup_free_ char *value = NULL;
675 assert(_n_components);
679 enum bus_match_node_type t;
681 size_t value_allocated = 0;
682 bool escaped = false;
692 t = bus_match_node_type_from_string(p, eq - p);
696 for (q = eq + 2;; q++) {
715 if (!greedy_realloc((void**) &value, &value_allocated, j + 2)) {
724 if (t == BUS_MATCH_MESSAGE_TYPE) {
725 r = bus_message_type_from_string(value, &u);
734 if (!greedy_realloc((void**) &components, &components_allocated,
735 (n_components + 1) * sizeof(struct match_component))) {
740 components[n_components].type = t;
741 components[n_components].value_str = value;
742 components[n_components].value_u8 = u;
758 /* Order the whole thing, so that we always generate the same tree */
759 qsort(components, n_components, sizeof(struct match_component), match_component_compare);
761 /* Check for duplicates */
762 for (i = 0; i+1 < n_components; i++)
763 if (components[i].type == components[i+1].type) {
768 *_components = components;
769 *_n_components = n_components;
774 free_components(components, n_components);
779 struct bus_match_node *root,
781 sd_bus_message_handler_t callback,
783 struct bus_match_node **ret) {
785 struct match_component *components = NULL;
786 unsigned n_components = 0, i;
787 struct bus_match_node *n;
794 r = parse_match(match, &components, &n_components);
799 for (i = 0; i < n_components; i++) {
800 r = bus_match_add_compare_value(
801 n, components[i].type,
802 components[i].value_u8, components[i].value_str, &n);
807 r = bus_match_add_leaf(n, callback, userdata, &n);
815 free_components(components, n_components);
819 int bus_match_remove(
820 struct bus_match_node *root,
822 sd_bus_message_handler_t callback,
825 struct match_component *components = NULL;
826 unsigned n_components = 0, i;
827 struct bus_match_node *n, **gc;
833 r = parse_match(match, &components, &n_components);
837 gc = newa(struct bus_match_node*, n_components);
840 for (i = 0; i < n_components; i++) {
841 r = bus_match_find_compare_value(
842 n, components[i].type,
843 components[i].value_u8, components[i].value_str,
851 r = bus_match_find_leaf(n, callback, userdata, &n);
856 bus_match_node_free(n);
858 /* Prune the tree above */
859 for (i = n_components; i > 0; i --) {
860 struct bus_match_node *p = gc[i-1]->parent;
862 if (!bus_match_node_maybe_free(gc[i-1]))
865 if (!bus_match_node_maybe_free(p))
870 free_components(components, n_components);
874 void bus_match_free(struct bus_match_node *node) {
875 struct bus_match_node *c;
880 if (BUS_MATCH_CAN_HASH(node->type)) {
883 HASHMAP_FOREACH(c, node->compare.children, i)
886 assert(hashmap_isempty(node->compare.children));
889 while ((c = node->child))
892 if (node->type != BUS_MATCH_ROOT)
893 bus_match_node_free(node);
896 const char* bus_match_node_type_to_string(enum bus_match_node_type t, char buf[], size_t l) {
902 case BUS_MATCH_VALUE:
908 case BUS_MATCH_MESSAGE_TYPE:
911 case BUS_MATCH_SENDER:
914 case BUS_MATCH_DESTINATION:
915 return "destination";
917 case BUS_MATCH_INTERFACE:
920 case BUS_MATCH_MEMBER:
926 case BUS_MATCH_PATH_NAMESPACE:
927 return "path_namespace";
929 case BUS_MATCH_ARG ... BUS_MATCH_ARG_LAST:
930 snprintf(buf, l, "arg%i", t - BUS_MATCH_ARG);
933 case BUS_MATCH_ARG_PATH ... BUS_MATCH_ARG_PATH_LAST:
934 snprintf(buf, l, "arg%ipath", t - BUS_MATCH_ARG_PATH);
937 case BUS_MATCH_ARG_NAMESPACE ... BUS_MATCH_ARG_NAMESPACE_LAST:
938 snprintf(buf, l, "arg%inamespace", t - BUS_MATCH_ARG_NAMESPACE);
946 void bus_match_dump(struct bus_match_node *node, unsigned level) {
947 struct bus_match_node *c;
948 _cleanup_free_ char *pfx = NULL;
954 pfx = strrep(" ", level);
955 printf("%s[%s]", strempty(pfx), bus_match_node_type_to_string(node->type, buf, sizeof(buf)));
957 if (node->type == BUS_MATCH_VALUE) {
958 if (node->parent->type == BUS_MATCH_MESSAGE_TYPE)
959 printf(" <%u>\n", node->value.u8);
961 printf(" <%s>\n", node->value.str);
962 } else if (node->type == BUS_MATCH_ROOT)
964 else if (node->type == BUS_MATCH_LEAF)
965 printf(" %p/%p\n", node->leaf.callback, node->leaf.userdata);
969 if (BUS_MATCH_CAN_HASH(node->type)) {
972 HASHMAP_FOREACH(c, node->compare.children, i)
973 bus_match_dump(c, level + 1);
976 for (c = node->child; c; c = c->next)
977 bus_match_dump(c, level + 1);