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_ptr(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,
205 const char *test_str = NULL;
214 if (bus && bus->match_callbacks_modified)
217 /* Not these special semantics: when traversing the tree we
218 * usually let bus_match_run() when called for a node
219 * recursively invoke bus_match_run(). There's are two
220 * exceptions here though, which are BUS_NODE_ROOT (which
221 * cannot have a sibling), and BUS_NODE_VALUE (whose siblings
222 * are invoked anyway by its parent. */
224 switch (node->type) {
228 /* Run all children. Since we cannot have any siblings
229 * we won't call any. The children of the root node
230 * are compares or leaves, they will automatically
231 * call their siblings. */
232 return bus_match_run(bus, node->child, m);
234 case BUS_MATCH_VALUE:
236 /* Run all children. We don't execute any siblings, we
237 * assume our caller does that. The children of value
238 * nodes are compares or leaves, they will
239 * automatically call their siblings */
242 return bus_match_run(bus, node->child, m);
247 if (node->leaf.last_iteration == bus->iteration_counter)
250 node->leaf.last_iteration = bus->iteration_counter;
253 r = sd_bus_message_rewind(m, true);
257 /* Run the callback. And then invoke siblings. */
258 if (node->leaf.callback) {
259 r = node->leaf.callback(bus, m, node->leaf.userdata);
264 return bus_match_run(bus, node->next, m);
266 case BUS_MATCH_MESSAGE_TYPE:
267 test_u8 = m->header->type;
270 case BUS_MATCH_SENDER:
271 test_str = m->sender;
272 /* FIXME: resolve test_str from a well-known to a unique name first */
275 case BUS_MATCH_DESTINATION:
276 test_str = m->destination;
279 case BUS_MATCH_INTERFACE:
280 test_str = m->interface;
283 case BUS_MATCH_MEMBER:
284 test_str = m->member;
288 case BUS_MATCH_PATH_NAMESPACE:
292 case BUS_MATCH_ARG ... BUS_MATCH_ARG_LAST:
293 test_str = bus_message_get_arg(m, node->type - BUS_MATCH_ARG);
296 case BUS_MATCH_ARG_PATH ... BUS_MATCH_ARG_PATH_LAST:
297 test_str = bus_message_get_arg(m, node->type - BUS_MATCH_ARG_PATH);
300 case BUS_MATCH_ARG_NAMESPACE ... BUS_MATCH_ARG_NAMESPACE_LAST:
301 test_str = bus_message_get_arg(m, node->type - BUS_MATCH_ARG_NAMESPACE);
305 assert_not_reached("Unknown match type.");
308 if (BUS_MATCH_CAN_HASH(node->type)) {
309 struct bus_match_node *found;
311 /* Lookup via hash table, nice! So let's jump directly. */
314 found = hashmap_get(node->compare.children, test_str);
315 else if (node->type == BUS_MATCH_MESSAGE_TYPE)
316 found = hashmap_get(node->compare.children, UINT_TO_PTR(test_u8));
321 r = bus_match_run(bus, found, m);
326 struct bus_match_node *c;
328 /* No hash table, so let's iterate manually... */
330 for (c = node->child; c; c = c->next) {
331 if (!value_node_test(c, node->type, test_u8, test_str))
334 r = bus_match_run(bus, c, m);
340 if (bus && bus->match_callbacks_modified)
343 /* And now, let's invoke our siblings */
344 return bus_match_run(bus, node->next, m);
347 static int bus_match_add_compare_value(
348 struct bus_match_node *where,
349 enum bus_match_node_type t,
351 const char *value_str,
352 struct bus_match_node **ret) {
354 struct bus_match_node *c = NULL, *n = NULL;
358 assert(where->type == BUS_MATCH_ROOT || where->type == BUS_MATCH_VALUE);
359 assert(BUS_MATCH_IS_COMPARE(t));
362 for (c = where->child; c && c->type != t; c = c->next)
366 /* Comparison node already exists? Then let's see if
367 * the value node exists too. */
369 if (t == BUS_MATCH_MESSAGE_TYPE)
370 n = hashmap_get(c->compare.children, UINT_TO_PTR(value_u8));
371 else if (BUS_MATCH_CAN_HASH(t))
372 n = hashmap_get(c->compare.children, value_str);
374 for (n = c->child; n && !value_node_same(n, t, value_u8, value_str); n = n->next)
383 /* Comparison node, doesn't exist yet? Then let's
386 c = new0(struct bus_match_node, 1);
394 c->next = where->child;
399 if (t == BUS_MATCH_MESSAGE_TYPE) {
400 c->compare.children = hashmap_new(trivial_hash_func, trivial_compare_func);
401 if (!c->compare.children) {
405 } else if (BUS_MATCH_CAN_HASH(t)) {
406 c->compare.children = hashmap_new(string_hash_func, string_compare_func);
407 if (!c->compare.children) {
414 n = new0(struct bus_match_node, 1);
420 n->type = BUS_MATCH_VALUE;
421 n->value.u8 = value_u8;
423 n->value.str = strdup(value_str);
431 if (c->compare.children) {
433 if (t == BUS_MATCH_MESSAGE_TYPE)
434 r = hashmap_put(c->compare.children, UINT_TO_PTR(value_u8), n);
436 r = hashmap_put(c->compare.children, n->value.str, n);
452 bus_match_node_maybe_free(c);
462 static int bus_match_find_compare_value(
463 struct bus_match_node *where,
464 enum bus_match_node_type t,
466 const char *value_str,
467 struct bus_match_node **ret) {
469 struct bus_match_node *c, *n;
472 assert(where->type == BUS_MATCH_ROOT || where->type == BUS_MATCH_VALUE);
473 assert(BUS_MATCH_IS_COMPARE(t));
476 for (c = where->child; c && c->type != t; c = c->next)
482 if (t == BUS_MATCH_MESSAGE_TYPE)
483 n = hashmap_get(c->compare.children, UINT_TO_PTR(value_u8));
484 else if (BUS_MATCH_CAN_HASH(t))
485 n = hashmap_get(c->compare.children, value_str);
487 for (n = c->child; !value_node_same(n, t, value_u8, value_str); n = n->next)
499 static int bus_match_add_leaf(
500 struct bus_match_node *where,
501 sd_bus_message_handler_t callback,
504 struct bus_match_node **ret) {
506 struct bus_match_node *n;
509 assert(where->type == BUS_MATCH_ROOT || where->type == BUS_MATCH_VALUE);
512 n = new0(struct bus_match_node, 1);
516 n->type = BUS_MATCH_LEAF;
518 n->next = where->child;
521 n->leaf.callback = callback;
522 n->leaf.userdata = userdata;
523 n->leaf.cookie = cookie;
531 static int bus_match_find_leaf(
532 struct bus_match_node *where,
533 sd_bus_message_handler_t callback,
535 struct bus_match_node **ret) {
537 struct bus_match_node *c;
540 assert(where->type == BUS_MATCH_ROOT || where->type == BUS_MATCH_VALUE);
543 for (c = where->child; c; c = c->next) {
544 if (c->type == BUS_MATCH_LEAF &&
545 c->leaf.callback == callback &&
546 c->leaf.userdata == userdata) {
555 enum bus_match_node_type bus_match_node_type_from_string(const char *k, size_t n) {
558 if (n == 4 && memcmp(k, "type", 4) == 0)
559 return BUS_MATCH_MESSAGE_TYPE;
560 if (n == 6 && memcmp(k, "sender", 6) == 0)
561 return BUS_MATCH_SENDER;
562 if (n == 11 && memcmp(k, "destination", 11) == 0)
563 return BUS_MATCH_DESTINATION;
564 if (n == 9 && memcmp(k, "interface", 9) == 0)
565 return BUS_MATCH_INTERFACE;
566 if (n == 6 && memcmp(k, "member", 6) == 0)
567 return BUS_MATCH_MEMBER;
568 if (n == 4 && memcmp(k, "path", 4) == 0)
569 return BUS_MATCH_PATH;
570 if (n == 14 && memcmp(k, "path_namespace", 14) == 0)
571 return BUS_MATCH_PATH_NAMESPACE;
573 if (n == 4 && memcmp(k, "arg", 3) == 0) {
580 return BUS_MATCH_ARG + j;
583 if (n == 5 && memcmp(k, "arg", 3) == 0) {
585 enum bus_match_node_type t;
592 t = BUS_MATCH_ARG + a * 10 + b;
593 if (t > BUS_MATCH_ARG_LAST)
599 if (n == 8 && memcmp(k, "arg", 3) == 0 && memcmp(k + 4, "path", 4) == 0) {
606 return BUS_MATCH_ARG_PATH + j;
609 if (n == 9 && memcmp(k, "arg", 3) == 0 && memcmp(k + 5, "path", 4) == 0) {
610 enum bus_match_node_type t;
618 t = BUS_MATCH_ARG_PATH + a * 10 + b;
619 if (t > BUS_MATCH_ARG_PATH_LAST)
625 if (n == 13 && memcmp(k, "arg", 3) == 0 && memcmp(k + 4, "namespace", 9) == 0) {
632 return BUS_MATCH_ARG_NAMESPACE + j;
635 if (n == 14 && memcmp(k, "arg", 3) == 0 && memcmp(k + 5, "namespace", 9) == 0) {
636 enum bus_match_node_type t;
644 t = BUS_MATCH_ARG_NAMESPACE + a * 10 + b;
645 if (t > BUS_MATCH_ARG_NAMESPACE_LAST)
654 static int match_component_compare(const void *a, const void *b) {
655 const struct bus_match_component *x = a, *y = b;
657 if (x->type < y->type)
659 if (x->type > y->type)
665 void bus_match_parse_free(struct bus_match_component *components, unsigned n_components) {
668 for (i = 0; i < n_components; i++)
669 free(components[i].value_str);
676 struct bus_match_component **_components,
677 unsigned *_n_components) {
679 const char *p = match;
680 struct bus_match_component *components = NULL;
681 size_t components_allocated = 0;
682 unsigned n_components = 0, i;
683 _cleanup_free_ char *value = NULL;
688 assert(_n_components);
692 enum bus_match_node_type t;
694 size_t value_allocated = 0;
695 bool escaped = false;
705 t = bus_match_node_type_from_string(p, eq - p);
709 for (q = eq + 2;; q++) {
728 if (!GREEDY_REALLOC(value, value_allocated, j + 2)) {
737 if (t == BUS_MATCH_MESSAGE_TYPE) {
738 r = bus_message_type_from_string(value, &u);
747 if (!GREEDY_REALLOC(components, components_allocated, n_components + 1)) {
752 components[n_components].type = t;
753 components[n_components].value_str = value;
754 components[n_components].value_u8 = u;
770 /* Order the whole thing, so that we always generate the same tree */
771 qsort(components, n_components, sizeof(struct bus_match_component), match_component_compare);
773 /* Check for duplicates */
774 for (i = 0; i+1 < n_components; i++)
775 if (components[i].type == components[i+1].type) {
780 *_components = components;
781 *_n_components = n_components;
786 bus_match_parse_free(components, n_components);
791 struct bus_match_node *root,
792 struct bus_match_component *components,
793 unsigned n_components,
794 sd_bus_message_handler_t callback,
797 struct bus_match_node **ret) {
800 struct bus_match_node *n;
806 for (i = 0; i < n_components; i++) {
807 r = bus_match_add_compare_value(
808 n, components[i].type,
809 components[i].value_u8, components[i].value_str, &n);
814 r = bus_match_add_leaf(n, callback, userdata, cookie, &n);
824 int bus_match_remove(
825 struct bus_match_node *root,
826 struct bus_match_component *components,
827 unsigned n_components,
828 sd_bus_message_handler_t callback,
833 struct bus_match_node *n, **gc;
838 gc = newa(struct bus_match_node*, n_components);
841 for (i = 0; i < n_components; i++) {
842 r = bus_match_find_compare_value(
843 n, components[i].type,
844 components[i].value_u8, components[i].value_str,
852 r = bus_match_find_leaf(n, callback, userdata, &n);
857 *cookie = n->leaf.cookie;
860 bus_match_node_free(n);
862 /* Prune the tree above */
863 for (i = n_components; i > 0; i --) {
864 struct bus_match_node *p = gc[i-1]->parent;
866 if (!bus_match_node_maybe_free(gc[i-1]))
869 if (!bus_match_node_maybe_free(p))
876 void bus_match_free(struct bus_match_node *node) {
877 struct bus_match_node *c;
882 if (BUS_MATCH_CAN_HASH(node->type)) {
885 HASHMAP_FOREACH(c, node->compare.children, i)
888 assert(hashmap_isempty(node->compare.children));
891 while ((c = node->child))
894 if (node->type != BUS_MATCH_ROOT)
895 bus_match_node_free(node);
898 const char* bus_match_node_type_to_string(enum bus_match_node_type t, char buf[], size_t l) {
904 case BUS_MATCH_VALUE:
910 case BUS_MATCH_MESSAGE_TYPE:
913 case BUS_MATCH_SENDER:
916 case BUS_MATCH_DESTINATION:
917 return "destination";
919 case BUS_MATCH_INTERFACE:
922 case BUS_MATCH_MEMBER:
928 case BUS_MATCH_PATH_NAMESPACE:
929 return "path_namespace";
931 case BUS_MATCH_ARG ... BUS_MATCH_ARG_LAST:
932 snprintf(buf, l, "arg%i", t - BUS_MATCH_ARG);
935 case BUS_MATCH_ARG_PATH ... BUS_MATCH_ARG_PATH_LAST:
936 snprintf(buf, l, "arg%ipath", t - BUS_MATCH_ARG_PATH);
939 case BUS_MATCH_ARG_NAMESPACE ... BUS_MATCH_ARG_NAMESPACE_LAST:
940 snprintf(buf, l, "arg%inamespace", t - BUS_MATCH_ARG_NAMESPACE);
948 void bus_match_dump(struct bus_match_node *node, unsigned level) {
949 struct bus_match_node *c;
950 _cleanup_free_ char *pfx = NULL;
956 pfx = strrep(" ", level);
957 printf("%s[%s]", strempty(pfx), bus_match_node_type_to_string(node->type, buf, sizeof(buf)));
959 if (node->type == BUS_MATCH_VALUE) {
960 if (node->parent->type == BUS_MATCH_MESSAGE_TYPE)
961 printf(" <%u>\n", node->value.u8);
963 printf(" <%s>\n", node->value.str);
964 } else if (node->type == BUS_MATCH_ROOT)
966 else if (node->type == BUS_MATCH_LEAF)
967 printf(" %p/%p\n", node->leaf.callback, node->leaf.userdata);
971 if (BUS_MATCH_CAN_HASH(node->type)) {
974 HASHMAP_FOREACH(c, node->compare.children, i)
975 bus_match_dump(c, level + 1);
978 for (c = node->child; c; c = c->next)
979 bus_match_dump(c, level + 1);