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 assert(node->leaf.callback);
259 r = node->leaf.callback(bus, m, node->leaf.userdata);
263 return bus_match_run(bus, node->next, m);
265 case BUS_MATCH_MESSAGE_TYPE:
266 test_u8 = m->header->type;
269 case BUS_MATCH_SENDER:
270 test_str = m->sender;
271 /* FIXME: resolve test_str from a well-known to a unique name first */
274 case BUS_MATCH_DESTINATION:
275 test_str = m->destination;
278 case BUS_MATCH_INTERFACE:
279 test_str = m->interface;
282 case BUS_MATCH_MEMBER:
283 test_str = m->member;
287 case BUS_MATCH_PATH_NAMESPACE:
291 case BUS_MATCH_ARG ... BUS_MATCH_ARG_LAST:
292 test_str = bus_message_get_arg(m, node->type - BUS_MATCH_ARG);
295 case BUS_MATCH_ARG_PATH ... BUS_MATCH_ARG_PATH_LAST:
296 test_str = bus_message_get_arg(m, node->type - BUS_MATCH_ARG_PATH);
299 case BUS_MATCH_ARG_NAMESPACE ... BUS_MATCH_ARG_NAMESPACE_LAST:
300 test_str = bus_message_get_arg(m, node->type - BUS_MATCH_ARG_NAMESPACE);
304 assert_not_reached("Unknown match type.");
307 if (BUS_MATCH_CAN_HASH(node->type)) {
308 struct bus_match_node *found;
310 /* Lookup via hash table, nice! So let's jump directly. */
313 found = hashmap_get(node->compare.children, test_str);
314 else if (node->type == BUS_MATCH_MESSAGE_TYPE)
315 found = hashmap_get(node->compare.children, UINT_TO_PTR(test_u8));
320 r = bus_match_run(bus, found, m);
325 struct bus_match_node *c;
327 /* No hash table, so let's iterate manually... */
329 for (c = node->child; c; c = c->next) {
330 if (!value_node_test(c, node->type, test_u8, test_str))
333 r = bus_match_run(bus, c, m);
339 if (bus && bus->match_callbacks_modified)
342 /* And now, let's invoke our siblings */
343 return bus_match_run(bus, node->next, m);
346 static int bus_match_add_compare_value(
347 struct bus_match_node *where,
348 enum bus_match_node_type t,
350 const char *value_str,
351 struct bus_match_node **ret) {
353 struct bus_match_node *c = NULL, *n = NULL;
357 assert(where->type == BUS_MATCH_ROOT || where->type == BUS_MATCH_VALUE);
358 assert(BUS_MATCH_IS_COMPARE(t));
361 for (c = where->child; c && c->type != t; c = c->next)
365 /* Comparison node already exists? Then let's see if
366 * the value node exists too. */
368 if (t == BUS_MATCH_MESSAGE_TYPE)
369 n = hashmap_get(c->compare.children, UINT_TO_PTR(value_u8));
370 else if (BUS_MATCH_CAN_HASH(t))
371 n = hashmap_get(c->compare.children, value_str);
373 for (n = c->child; n && !value_node_same(n, t, value_u8, value_str); n = n->next)
382 /* Comparison node, doesn't exist yet? Then let's
385 c = new0(struct bus_match_node, 1);
393 c->next = where->child;
398 if (t == BUS_MATCH_MESSAGE_TYPE) {
399 c->compare.children = hashmap_new(trivial_hash_func, trivial_compare_func);
400 if (!c->compare.children) {
404 } else if (BUS_MATCH_CAN_HASH(t)) {
405 c->compare.children = hashmap_new(string_hash_func, string_compare_func);
406 if (!c->compare.children) {
413 n = new0(struct bus_match_node, 1);
419 n->type = BUS_MATCH_VALUE;
420 n->value.u8 = value_u8;
422 n->value.str = strdup(value_str);
430 if (c->compare.children) {
432 if (t == BUS_MATCH_MESSAGE_TYPE)
433 r = hashmap_put(c->compare.children, UINT_TO_PTR(value_u8), n);
435 r = hashmap_put(c->compare.children, n->value.str, n);
451 bus_match_node_maybe_free(c);
461 static int bus_match_find_compare_value(
462 struct bus_match_node *where,
463 enum bus_match_node_type t,
465 const char *value_str,
466 struct bus_match_node **ret) {
468 struct bus_match_node *c, *n;
471 assert(where->type == BUS_MATCH_ROOT || where->type == BUS_MATCH_VALUE);
472 assert(BUS_MATCH_IS_COMPARE(t));
475 for (c = where->child; c && c->type != t; c = c->next)
481 if (t == BUS_MATCH_MESSAGE_TYPE)
482 n = hashmap_get(c->compare.children, UINT_TO_PTR(value_u8));
483 else if (BUS_MATCH_CAN_HASH(t))
484 n = hashmap_get(c->compare.children, value_str);
486 for (n = c->child; !value_node_same(n, t, value_u8, value_str); n = n->next)
498 static int bus_match_add_leaf(
499 struct bus_match_node *where,
500 sd_bus_message_handler_t callback,
502 struct bus_match_node **ret) {
504 struct bus_match_node *n;
507 assert(where->type == BUS_MATCH_ROOT || where->type == BUS_MATCH_VALUE);
510 n = new0(struct bus_match_node, 1);
514 n->type = BUS_MATCH_LEAF;
516 n->next = where->child;
519 n->leaf.callback = callback;
520 n->leaf.userdata = userdata;
528 static int bus_match_find_leaf(
529 struct bus_match_node *where,
530 sd_bus_message_handler_t callback,
532 struct bus_match_node **ret) {
534 struct bus_match_node *c;
537 assert(where->type == BUS_MATCH_ROOT || where->type == BUS_MATCH_VALUE);
540 for (c = where->child; c; c = c->next) {
541 if (c->type == BUS_MATCH_LEAF &&
542 c->leaf.callback == callback &&
543 c->leaf.userdata == userdata) {
552 enum bus_match_node_type bus_match_node_type_from_string(const char *k, size_t n) {
555 if (n == 4 && memcmp(k, "type", 4) == 0)
556 return BUS_MATCH_MESSAGE_TYPE;
557 if (n == 6 && memcmp(k, "sender", 6) == 0)
558 return BUS_MATCH_SENDER;
559 if (n == 11 && memcmp(k, "destination", 11) == 0)
560 return BUS_MATCH_DESTINATION;
561 if (n == 9 && memcmp(k, "interface", 9) == 0)
562 return BUS_MATCH_INTERFACE;
563 if (n == 6 && memcmp(k, "member", 6) == 0)
564 return BUS_MATCH_MEMBER;
565 if (n == 4 && memcmp(k, "path", 4) == 0)
566 return BUS_MATCH_PATH;
567 if (n == 14 && memcmp(k, "path_namespace", 14) == 0)
568 return BUS_MATCH_PATH_NAMESPACE;
570 if (n == 4 && memcmp(k, "arg", 3) == 0) {
577 return BUS_MATCH_ARG + j;
580 if (n == 5 && memcmp(k, "arg", 3) == 0) {
582 enum bus_match_node_type t;
589 t = BUS_MATCH_ARG + a * 10 + b;
590 if (t > BUS_MATCH_ARG_LAST)
596 if (n == 8 && memcmp(k, "arg", 3) == 0 && memcmp(k + 4, "path", 4) == 0) {
603 return BUS_MATCH_ARG_PATH + j;
606 if (n == 9 && memcmp(k, "arg", 3) == 0 && memcmp(k + 5, "path", 4) == 0) {
607 enum bus_match_node_type t;
615 t = BUS_MATCH_ARG_PATH + a * 10 + b;
616 if (t > BUS_MATCH_ARG_PATH_LAST)
622 if (n == 13 && memcmp(k, "arg", 3) == 0 && memcmp(k + 4, "namespace", 9) == 0) {
629 return BUS_MATCH_ARG_NAMESPACE + j;
632 if (n == 14 && memcmp(k, "arg", 3) == 0 && memcmp(k + 5, "namespace", 9) == 0) {
633 enum bus_match_node_type t;
641 t = BUS_MATCH_ARG_NAMESPACE + a * 10 + b;
642 if (t > BUS_MATCH_ARG_NAMESPACE_LAST)
651 struct match_component {
652 enum bus_match_node_type type;
657 static int match_component_compare(const void *a, const void *b) {
658 const struct match_component *x = a, *y = b;
660 if (x->type < y->type)
662 if (x->type > y->type)
668 static void free_components(struct match_component *components, unsigned n_components) {
671 for (i = 0; i < n_components; i++)
672 free(components[i].value_str);
677 static int parse_match(
679 struct match_component **_components,
680 unsigned *_n_components) {
682 const char *p = match;
683 struct match_component *components = NULL;
684 size_t components_allocated = 0;
685 unsigned n_components = 0, i;
686 _cleanup_free_ char *value = NULL;
691 assert(_n_components);
695 enum bus_match_node_type t;
697 size_t value_allocated = 0;
698 bool escaped = false;
708 t = bus_match_node_type_from_string(p, eq - p);
712 for (q = eq + 2;; q++) {
731 if (!GREEDY_REALLOC(value, value_allocated, j + 2)) {
740 if (t == BUS_MATCH_MESSAGE_TYPE) {
741 r = bus_message_type_from_string(value, &u);
750 if (!GREEDY_REALLOC(components, components_allocated, n_components + 1)) {
755 components[n_components].type = t;
756 components[n_components].value_str = value;
757 components[n_components].value_u8 = u;
773 /* Order the whole thing, so that we always generate the same tree */
774 qsort(components, n_components, sizeof(struct match_component), match_component_compare);
776 /* Check for duplicates */
777 for (i = 0; i+1 < n_components; i++)
778 if (components[i].type == components[i+1].type) {
783 *_components = components;
784 *_n_components = n_components;
789 free_components(components, n_components);
794 struct bus_match_node *root,
796 sd_bus_message_handler_t callback,
798 struct bus_match_node **ret) {
800 struct match_component *components = NULL;
801 unsigned n_components = 0, i;
802 struct bus_match_node *n;
809 r = parse_match(match, &components, &n_components);
814 for (i = 0; i < n_components; i++) {
815 r = bus_match_add_compare_value(
816 n, components[i].type,
817 components[i].value_u8, components[i].value_str, &n);
822 r = bus_match_add_leaf(n, callback, userdata, &n);
830 free_components(components, n_components);
834 int bus_match_remove(
835 struct bus_match_node *root,
837 sd_bus_message_handler_t callback,
840 struct match_component *components = NULL;
841 unsigned n_components = 0, i;
842 struct bus_match_node *n, **gc;
848 r = parse_match(match, &components, &n_components);
852 gc = newa(struct bus_match_node*, n_components);
855 for (i = 0; i < n_components; i++) {
856 r = bus_match_find_compare_value(
857 n, components[i].type,
858 components[i].value_u8, components[i].value_str,
866 r = bus_match_find_leaf(n, callback, userdata, &n);
871 bus_match_node_free(n);
873 /* Prune the tree above */
874 for (i = n_components; i > 0; i --) {
875 struct bus_match_node *p = gc[i-1]->parent;
877 if (!bus_match_node_maybe_free(gc[i-1]))
880 if (!bus_match_node_maybe_free(p))
885 free_components(components, n_components);
889 void bus_match_free(struct bus_match_node *node) {
890 struct bus_match_node *c;
895 if (BUS_MATCH_CAN_HASH(node->type)) {
898 HASHMAP_FOREACH(c, node->compare.children, i)
901 assert(hashmap_isempty(node->compare.children));
904 while ((c = node->child))
907 if (node->type != BUS_MATCH_ROOT)
908 bus_match_node_free(node);
911 const char* bus_match_node_type_to_string(enum bus_match_node_type t, char buf[], size_t l) {
917 case BUS_MATCH_VALUE:
923 case BUS_MATCH_MESSAGE_TYPE:
926 case BUS_MATCH_SENDER:
929 case BUS_MATCH_DESTINATION:
930 return "destination";
932 case BUS_MATCH_INTERFACE:
935 case BUS_MATCH_MEMBER:
941 case BUS_MATCH_PATH_NAMESPACE:
942 return "path_namespace";
944 case BUS_MATCH_ARG ... BUS_MATCH_ARG_LAST:
945 snprintf(buf, l, "arg%i", t - BUS_MATCH_ARG);
948 case BUS_MATCH_ARG_PATH ... BUS_MATCH_ARG_PATH_LAST:
949 snprintf(buf, l, "arg%ipath", t - BUS_MATCH_ARG_PATH);
952 case BUS_MATCH_ARG_NAMESPACE ... BUS_MATCH_ARG_NAMESPACE_LAST:
953 snprintf(buf, l, "arg%inamespace", t - BUS_MATCH_ARG_NAMESPACE);
961 void bus_match_dump(struct bus_match_node *node, unsigned level) {
962 struct bus_match_node *c;
963 _cleanup_free_ char *pfx = NULL;
969 pfx = strrep(" ", level);
970 printf("%s[%s]", strempty(pfx), bus_match_node_type_to_string(node->type, buf, sizeof(buf)));
972 if (node->type == BUS_MATCH_VALUE) {
973 if (node->parent->type == BUS_MATCH_MESSAGE_TYPE)
974 printf(" <%u>\n", node->value.u8);
976 printf(" <%s>\n", node->value.str);
977 } else if (node->type == BUS_MATCH_ROOT)
979 else if (node->type == BUS_MATCH_LEAF)
980 printf(" %p/%p\n", node->leaf.callback, node->leaf.userdata);
984 if (BUS_MATCH_CAN_HASH(node->type)) {
987 HASHMAP_FOREACH(c, node->compare.children, i)
988 bus_match_dump(c, level + 1);
991 for (c = node->child; c; c = c->next)
992 bus_match_dump(c, level + 1);