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 if (bus && bus->match_callbacks_modified)
218 /* Not these special semantics: when traversing the tree we
219 * usually let bus_match_run() when called for a node
220 * recursively invoke bus_match_run(). There's are two
221 * exceptions here though, which are BUS_NODE_ROOT (which
222 * cannot have a sibling), and BUS_NODE_VALUE (whose siblings
223 * are invoked anyway by its parent. */
225 switch (node->type) {
229 /* Run all children. Since we cannot have any siblings
230 * we won't call any. The children of the root node
231 * are compares or leaves, they will automatically
232 * call their siblings. */
233 return bus_match_run(bus, node->child, ret, m);
235 case BUS_MATCH_VALUE:
237 /* Run all children. We don't execute any siblings, we
238 * assume our caller does that. The children of value
239 * nodes are compares or leaves, they will
240 * automatically call their siblings */
243 return bus_match_run(bus, node->child, ret, m);
248 if (node->leaf.last_iteration == bus->iteration_counter)
251 node->leaf.last_iteration = bus->iteration_counter;
254 /* Run the callback. And then invoke siblings. */
255 assert(node->leaf.callback);
256 r = node->leaf.callback(bus, ret, m, node->leaf.userdata);
260 return bus_match_run(bus, node->next, ret, m);
262 case BUS_MATCH_MESSAGE_TYPE:
263 test_u8 = m->header->type;
266 case BUS_MATCH_SENDER:
267 test_str = m->sender;
268 /* FIXME: resolve test_str from a well-known to a unique name first */
271 case BUS_MATCH_DESTINATION:
272 test_str = m->destination;
275 case BUS_MATCH_INTERFACE:
276 test_str = m->interface;
279 case BUS_MATCH_MEMBER:
280 test_str = m->member;
284 case BUS_MATCH_PATH_NAMESPACE:
288 case BUS_MATCH_ARG ... BUS_MATCH_ARG_LAST:
289 test_str = bus_message_get_arg(m, node->type - BUS_MATCH_ARG);
292 case BUS_MATCH_ARG_PATH ... BUS_MATCH_ARG_PATH_LAST:
293 test_str = bus_message_get_arg(m, node->type - BUS_MATCH_ARG_PATH);
296 case BUS_MATCH_ARG_NAMESPACE ... BUS_MATCH_ARG_NAMESPACE_LAST:
297 test_str = bus_message_get_arg(m, node->type - BUS_MATCH_ARG_NAMESPACE);
301 assert_not_reached("Unknown match type.");
304 if (BUS_MATCH_CAN_HASH(node->type)) {
305 struct bus_match_node *found;
307 /* Lookup via hash table, nice! So let's jump directly. */
310 found = hashmap_get(node->compare.children, test_str);
311 else if (node->type == BUS_MATCH_MESSAGE_TYPE)
312 found = hashmap_get(node->compare.children, UINT_TO_PTR(test_u8));
317 r = bus_match_run(bus, found, ret, m);
322 struct bus_match_node *c;
324 /* No hash table, so let's iterate manually... */
326 for (c = node->child; c; c = c->next) {
327 if (!value_node_test(c, node->type, test_u8, test_str))
330 r = bus_match_run(bus, c, ret, m);
336 if (bus && bus->match_callbacks_modified)
339 /* And now, let's invoke our siblings */
340 return bus_match_run(bus, node->next, ret, m);
343 static int bus_match_add_compare_value(
344 struct bus_match_node *where,
345 enum bus_match_node_type t,
347 const char *value_str,
348 struct bus_match_node **ret) {
350 struct bus_match_node *c = NULL, *n = NULL;
354 assert(where->type == BUS_MATCH_ROOT || where->type == BUS_MATCH_VALUE);
355 assert(BUS_MATCH_IS_COMPARE(t));
358 for (c = where->child; c && c->type != t; c = c->next)
362 /* Comparison node already exists? Then let's see if
363 * the value node exists too. */
365 if (t == BUS_MATCH_MESSAGE_TYPE)
366 n = hashmap_get(c->compare.children, UINT_TO_PTR(value_u8));
367 else if (BUS_MATCH_CAN_HASH(t))
368 n = hashmap_get(c->compare.children, value_str);
370 for (n = c->child; n && !value_node_same(n, t, value_u8, value_str); n = n->next)
379 /* Comparison node, doesn't exist yet? Then let's
382 c = new0(struct bus_match_node, 1);
390 c->next = where->child;
395 if (t == BUS_MATCH_MESSAGE_TYPE) {
396 c->compare.children = hashmap_new(trivial_hash_func, trivial_compare_func);
397 if (!c->compare.children) {
401 } else if (BUS_MATCH_CAN_HASH(t)) {
402 c->compare.children = hashmap_new(string_hash_func, string_compare_func);
403 if (!c->compare.children) {
410 n = new0(struct bus_match_node, 1);
416 n->type = BUS_MATCH_VALUE;
417 n->value.u8 = value_u8;
419 n->value.str = strdup(value_str);
427 if (c->compare.children) {
429 if (t == BUS_MATCH_MESSAGE_TYPE)
430 r = hashmap_put(c->compare.children, UINT_TO_PTR(value_u8), n);
432 r = hashmap_put(c->compare.children, n->value.str, n);
448 bus_match_node_maybe_free(c);
458 static int bus_match_find_compare_value(
459 struct bus_match_node *where,
460 enum bus_match_node_type t,
462 const char *value_str,
463 struct bus_match_node **ret) {
465 struct bus_match_node *c, *n;
468 assert(where->type == BUS_MATCH_ROOT || where->type == BUS_MATCH_VALUE);
469 assert(BUS_MATCH_IS_COMPARE(t));
472 for (c = where->child; c && c->type != t; c = c->next)
478 if (t == BUS_MATCH_MESSAGE_TYPE)
479 n = hashmap_get(c->compare.children, UINT_TO_PTR(value_u8));
480 else if (BUS_MATCH_CAN_HASH(t))
481 n = hashmap_get(c->compare.children, value_str);
483 for (n = c->child; !value_node_same(n, t, value_u8, value_str); n = n->next)
495 static int bus_match_add_leaf(
496 struct bus_match_node *where,
497 sd_bus_message_handler_t callback,
499 struct bus_match_node **ret) {
501 struct bus_match_node *n;
504 assert(where->type == BUS_MATCH_ROOT || where->type == BUS_MATCH_VALUE);
507 n = new0(struct bus_match_node, 1);
511 n->type = BUS_MATCH_LEAF;
513 n->next = where->child;
516 n->leaf.callback = callback;
517 n->leaf.userdata = userdata;
525 static int bus_match_find_leaf(
526 struct bus_match_node *where,
527 sd_bus_message_handler_t callback,
529 struct bus_match_node **ret) {
531 struct bus_match_node *c;
534 assert(where->type == BUS_MATCH_ROOT || where->type == BUS_MATCH_VALUE);
537 for (c = where->child; c; c = c->next) {
538 if (c->type == BUS_MATCH_LEAF &&
539 c->leaf.callback == callback &&
540 c->leaf.userdata == userdata) {
549 enum bus_match_node_type bus_match_node_type_from_string(const char *k, size_t n) {
552 if (n == 4 && memcmp(k, "type", 4) == 0)
553 return BUS_MATCH_MESSAGE_TYPE;
554 if (n == 6 && memcmp(k, "sender", 6) == 0)
555 return BUS_MATCH_SENDER;
556 if (n == 11 && memcmp(k, "destination", 11) == 0)
557 return BUS_MATCH_DESTINATION;
558 if (n == 9 && memcmp(k, "interface", 9) == 0)
559 return BUS_MATCH_INTERFACE;
560 if (n == 6 && memcmp(k, "member", 6) == 0)
561 return BUS_MATCH_MEMBER;
562 if (n == 4 && memcmp(k, "path", 4) == 0)
563 return BUS_MATCH_PATH;
564 if (n == 14 && memcmp(k, "path_namespace", 14) == 0)
565 return BUS_MATCH_PATH_NAMESPACE;
567 if (n == 4 && memcmp(k, "arg", 3) == 0) {
574 return BUS_MATCH_ARG + j;
577 if (n == 5 && memcmp(k, "arg", 3) == 0) {
579 enum bus_match_node_type t;
586 t = BUS_MATCH_ARG + a * 10 + b;
587 if (t > BUS_MATCH_ARG_LAST)
593 if (n == 8 && memcmp(k, "arg", 3) == 0 && memcmp(k + 4, "path", 4) == 0) {
600 return BUS_MATCH_ARG_PATH + j;
603 if (n == 9 && memcmp(k, "arg", 3) == 0 && memcmp(k + 5, "path", 4) == 0) {
604 enum bus_match_node_type t;
612 t = BUS_MATCH_ARG_PATH + a * 10 + b;
613 if (t > BUS_MATCH_ARG_PATH_LAST)
619 if (n == 13 && memcmp(k, "arg", 3) == 0 && memcmp(k + 4, "namespace", 9) == 0) {
626 return BUS_MATCH_ARG_NAMESPACE + j;
629 if (n == 14 && memcmp(k, "arg", 3) == 0 && memcmp(k + 5, "namespace", 9) == 0) {
630 enum bus_match_node_type t;
638 t = BUS_MATCH_ARG_NAMESPACE + a * 10 + b;
639 if (t > BUS_MATCH_ARG_NAMESPACE_LAST)
648 struct match_component {
649 enum bus_match_node_type type;
654 static int match_component_compare(const void *a, const void *b) {
655 const struct match_component *x = a, *y = b;
657 if (x->type < y->type)
659 if (x->type > y->type)
665 static void free_components(struct match_component *components, unsigned n_components) {
668 for (i = 0; i < n_components; i++)
669 free(components[i].value_str);
674 static int parse_match(
676 struct match_component **_components,
677 unsigned *_n_components) {
679 const char *p = match;
680 struct 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((void**) &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((void**) &components, &components_allocated,
748 (n_components + 1) * sizeof(struct match_component))) {
753 components[n_components].type = t;
754 components[n_components].value_str = value;
755 components[n_components].value_u8 = u;
771 /* Order the whole thing, so that we always generate the same tree */
772 qsort(components, n_components, sizeof(struct match_component), match_component_compare);
774 /* Check for duplicates */
775 for (i = 0; i+1 < n_components; i++)
776 if (components[i].type == components[i+1].type) {
781 *_components = components;
782 *_n_components = n_components;
787 free_components(components, n_components);
792 struct bus_match_node *root,
794 sd_bus_message_handler_t callback,
796 struct bus_match_node **ret) {
798 struct match_component *components = NULL;
799 unsigned n_components = 0, i;
800 struct bus_match_node *n;
807 r = parse_match(match, &components, &n_components);
812 for (i = 0; i < n_components; i++) {
813 r = bus_match_add_compare_value(
814 n, components[i].type,
815 components[i].value_u8, components[i].value_str, &n);
820 r = bus_match_add_leaf(n, callback, userdata, &n);
828 free_components(components, n_components);
832 int bus_match_remove(
833 struct bus_match_node *root,
835 sd_bus_message_handler_t callback,
838 struct match_component *components = NULL;
839 unsigned n_components = 0, i;
840 struct bus_match_node *n, **gc;
846 r = parse_match(match, &components, &n_components);
850 gc = newa(struct bus_match_node*, n_components);
853 for (i = 0; i < n_components; i++) {
854 r = bus_match_find_compare_value(
855 n, components[i].type,
856 components[i].value_u8, components[i].value_str,
864 r = bus_match_find_leaf(n, callback, userdata, &n);
869 bus_match_node_free(n);
871 /* Prune the tree above */
872 for (i = n_components; i > 0; i --) {
873 struct bus_match_node *p = gc[i-1]->parent;
875 if (!bus_match_node_maybe_free(gc[i-1]))
878 if (!bus_match_node_maybe_free(p))
883 free_components(components, n_components);
887 void bus_match_free(struct bus_match_node *node) {
888 struct bus_match_node *c;
893 if (BUS_MATCH_CAN_HASH(node->type)) {
896 HASHMAP_FOREACH(c, node->compare.children, i)
899 assert(hashmap_isempty(node->compare.children));
902 while ((c = node->child))
905 if (node->type != BUS_MATCH_ROOT)
906 bus_match_node_free(node);
909 const char* bus_match_node_type_to_string(enum bus_match_node_type t, char buf[], size_t l) {
915 case BUS_MATCH_VALUE:
921 case BUS_MATCH_MESSAGE_TYPE:
924 case BUS_MATCH_SENDER:
927 case BUS_MATCH_DESTINATION:
928 return "destination";
930 case BUS_MATCH_INTERFACE:
933 case BUS_MATCH_MEMBER:
939 case BUS_MATCH_PATH_NAMESPACE:
940 return "path_namespace";
942 case BUS_MATCH_ARG ... BUS_MATCH_ARG_LAST:
943 snprintf(buf, l, "arg%i", t - BUS_MATCH_ARG);
946 case BUS_MATCH_ARG_PATH ... BUS_MATCH_ARG_PATH_LAST:
947 snprintf(buf, l, "arg%ipath", t - BUS_MATCH_ARG_PATH);
950 case BUS_MATCH_ARG_NAMESPACE ... BUS_MATCH_ARG_NAMESPACE_LAST:
951 snprintf(buf, l, "arg%inamespace", t - BUS_MATCH_ARG_NAMESPACE);
959 void bus_match_dump(struct bus_match_node *node, unsigned level) {
960 struct bus_match_node *c;
961 _cleanup_free_ char *pfx = NULL;
967 pfx = strrep(" ", level);
968 printf("%s[%s]", strempty(pfx), bus_match_node_type_to_string(node->type, buf, sizeof(buf)));
970 if (node->type == BUS_MATCH_VALUE) {
971 if (node->parent->type == BUS_MATCH_MESSAGE_TYPE)
972 printf(" <%u>\n", node->value.u8);
974 printf(" <%s>\n", node->value.str);
975 } else if (node->type == BUS_MATCH_ROOT)
977 else if (node->type == BUS_MATCH_LEAF)
978 printf(" %p/%p\n", node->leaf.callback, node->leaf.userdata);
982 if (BUS_MATCH_CAN_HASH(node->type)) {
985 HASHMAP_FOREACH(c, node->compare.children, i)
986 bus_match_dump(c, level + 1);
989 for (c = node->child; c; c = c->next)
990 bus_match_dump(c, level + 1);