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_SENDER && 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 if (streq_ptr(node->value.str, value_str))
148 /* FIXME: So here's an ugliness: if the match is for a
149 * well-known name then we cannot actually check this
150 * correctly here. This doesn't matter much for dbus1
151 * where no false positives exist, hence we just
152 * ignore this case here. For kdbus the messages
153 * should contain all well-known names of the sender,
154 * hence we can fix things there correctly. */
156 if (node->value.str[0] != ':' && value_str && value_str[0] == ':')
161 case BUS_MATCH_INTERFACE:
162 case BUS_MATCH_MEMBER:
164 case BUS_MATCH_ARG ... BUS_MATCH_ARG_LAST:
165 return streq_ptr(node->value.str, value_str);
167 case BUS_MATCH_ARG_NAMESPACE ... BUS_MATCH_ARG_NAMESPACE_LAST:
168 return namespace_simple_pattern(node->value.str, value_str);
170 case BUS_MATCH_PATH_NAMESPACE:
171 return path_simple_pattern(node->value.str, value_str);
173 case BUS_MATCH_ARG_PATH ... BUS_MATCH_ARG_PATH_LAST:
174 return path_complex_pattern(node->value.str, value_str);
177 assert_not_reached("Invalid node type");
181 static bool value_node_same(
182 struct bus_match_node *node,
183 enum bus_match_node_type parent_type,
185 const char *value_str) {
187 /* Tests parameters against this value node, not doing prefix
188 * magic and stuff, i.e. this one actually compares the match
192 assert(node->type == BUS_MATCH_VALUE);
194 switch (parent_type) {
196 case BUS_MATCH_MESSAGE_TYPE:
197 return node->value.u8 == value_u8;
199 case BUS_MATCH_SENDER:
200 case BUS_MATCH_DESTINATION:
201 case BUS_MATCH_INTERFACE:
202 case BUS_MATCH_MEMBER:
204 case BUS_MATCH_ARG ... BUS_MATCH_ARG_LAST:
205 case BUS_MATCH_ARG_NAMESPACE ... BUS_MATCH_ARG_NAMESPACE_LAST:
206 case BUS_MATCH_PATH_NAMESPACE:
207 case BUS_MATCH_ARG_PATH ... BUS_MATCH_ARG_PATH_LAST:
208 return streq(node->value.str, value_str);
211 assert_not_reached("Invalid node type");
217 struct bus_match_node *node,
221 const char *test_str = NULL;
230 if (bus && bus->match_callbacks_modified)
233 /* Not these special semantics: when traversing the tree we
234 * usually let bus_match_run() when called for a node
235 * recursively invoke bus_match_run(). There's are two
236 * exceptions here though, which are BUS_NODE_ROOT (which
237 * cannot have a sibling), and BUS_NODE_VALUE (whose siblings
238 * are invoked anyway by its parent. */
240 switch (node->type) {
244 /* Run all children. Since we cannot have any siblings
245 * we won't call any. The children of the root node
246 * are compares or leaves, they will automatically
247 * call their siblings. */
248 return bus_match_run(bus, node->child, m);
250 case BUS_MATCH_VALUE:
252 /* Run all children. We don't execute any siblings, we
253 * assume our caller does that. The children of value
254 * nodes are compares or leaves, they will
255 * automatically call their siblings */
258 return bus_match_run(bus, node->child, m);
263 if (node->leaf.last_iteration == bus->iteration_counter)
266 node->leaf.last_iteration = bus->iteration_counter;
269 r = sd_bus_message_rewind(m, true);
273 /* Run the callback. And then invoke siblings. */
274 if (node->leaf.callback) {
275 r = node->leaf.callback(bus, m, node->leaf.userdata);
280 return bus_match_run(bus, node->next, m);
282 case BUS_MATCH_MESSAGE_TYPE:
283 test_u8 = m->header->type;
286 case BUS_MATCH_SENDER:
287 test_str = m->sender;
288 /* FIXME: resolve test_str from a well-known to a unique name first */
291 case BUS_MATCH_DESTINATION:
292 test_str = m->destination;
295 case BUS_MATCH_INTERFACE:
296 test_str = m->interface;
299 case BUS_MATCH_MEMBER:
300 test_str = m->member;
304 case BUS_MATCH_PATH_NAMESPACE:
308 case BUS_MATCH_ARG ... BUS_MATCH_ARG_LAST:
309 test_str = bus_message_get_arg(m, node->type - BUS_MATCH_ARG);
312 case BUS_MATCH_ARG_PATH ... BUS_MATCH_ARG_PATH_LAST:
313 test_str = bus_message_get_arg(m, node->type - BUS_MATCH_ARG_PATH);
316 case BUS_MATCH_ARG_NAMESPACE ... BUS_MATCH_ARG_NAMESPACE_LAST:
317 test_str = bus_message_get_arg(m, node->type - BUS_MATCH_ARG_NAMESPACE);
321 assert_not_reached("Unknown match type.");
324 if (BUS_MATCH_CAN_HASH(node->type)) {
325 struct bus_match_node *found;
327 /* Lookup via hash table, nice! So let's jump directly. */
330 found = hashmap_get(node->compare.children, test_str);
331 else if (node->type == BUS_MATCH_MESSAGE_TYPE)
332 found = hashmap_get(node->compare.children, UINT_TO_PTR(test_u8));
337 r = bus_match_run(bus, found, m);
342 struct bus_match_node *c;
344 /* No hash table, so let's iterate manually... */
346 for (c = node->child; c; c = c->next) {
347 if (!value_node_test(c, node->type, test_u8, test_str))
350 r = bus_match_run(bus, c, m);
356 if (bus && bus->match_callbacks_modified)
359 /* And now, let's invoke our siblings */
360 return bus_match_run(bus, node->next, m);
363 static int bus_match_add_compare_value(
364 struct bus_match_node *where,
365 enum bus_match_node_type t,
367 const char *value_str,
368 struct bus_match_node **ret) {
370 struct bus_match_node *c = NULL, *n = NULL;
374 assert(where->type == BUS_MATCH_ROOT || where->type == BUS_MATCH_VALUE);
375 assert(BUS_MATCH_IS_COMPARE(t));
378 for (c = where->child; c && c->type != t; c = c->next)
382 /* Comparison node already exists? Then let's see if
383 * the value node exists too. */
385 if (t == BUS_MATCH_MESSAGE_TYPE)
386 n = hashmap_get(c->compare.children, UINT_TO_PTR(value_u8));
387 else if (BUS_MATCH_CAN_HASH(t))
388 n = hashmap_get(c->compare.children, value_str);
390 for (n = c->child; n && !value_node_same(n, t, value_u8, value_str); n = n->next)
399 /* Comparison node, doesn't exist yet? Then let's
402 c = new0(struct bus_match_node, 1);
410 c->next = where->child;
415 if (t == BUS_MATCH_MESSAGE_TYPE) {
416 c->compare.children = hashmap_new(trivial_hash_func, trivial_compare_func);
417 if (!c->compare.children) {
421 } else if (BUS_MATCH_CAN_HASH(t)) {
422 c->compare.children = hashmap_new(string_hash_func, string_compare_func);
423 if (!c->compare.children) {
430 n = new0(struct bus_match_node, 1);
436 n->type = BUS_MATCH_VALUE;
437 n->value.u8 = value_u8;
439 n->value.str = strdup(value_str);
447 if (c->compare.children) {
449 if (t == BUS_MATCH_MESSAGE_TYPE)
450 r = hashmap_put(c->compare.children, UINT_TO_PTR(value_u8), n);
452 r = hashmap_put(c->compare.children, n->value.str, n);
468 bus_match_node_maybe_free(c);
478 static int bus_match_find_compare_value(
479 struct bus_match_node *where,
480 enum bus_match_node_type t,
482 const char *value_str,
483 struct bus_match_node **ret) {
485 struct bus_match_node *c, *n;
488 assert(where->type == BUS_MATCH_ROOT || where->type == BUS_MATCH_VALUE);
489 assert(BUS_MATCH_IS_COMPARE(t));
492 for (c = where->child; c && c->type != t; c = c->next)
498 if (t == BUS_MATCH_MESSAGE_TYPE)
499 n = hashmap_get(c->compare.children, UINT_TO_PTR(value_u8));
500 else if (BUS_MATCH_CAN_HASH(t))
501 n = hashmap_get(c->compare.children, value_str);
503 for (n = c->child; !value_node_same(n, t, value_u8, value_str); n = n->next)
515 static int bus_match_add_leaf(
516 struct bus_match_node *where,
517 sd_bus_message_handler_t callback,
520 struct bus_match_node **ret) {
522 struct bus_match_node *n;
525 assert(where->type == BUS_MATCH_ROOT || where->type == BUS_MATCH_VALUE);
528 n = new0(struct bus_match_node, 1);
532 n->type = BUS_MATCH_LEAF;
534 n->next = where->child;
537 n->leaf.callback = callback;
538 n->leaf.userdata = userdata;
539 n->leaf.cookie = cookie;
547 static int bus_match_find_leaf(
548 struct bus_match_node *where,
549 sd_bus_message_handler_t callback,
551 struct bus_match_node **ret) {
553 struct bus_match_node *c;
556 assert(where->type == BUS_MATCH_ROOT || where->type == BUS_MATCH_VALUE);
559 for (c = where->child; c; c = c->next) {
560 if (c->type == BUS_MATCH_LEAF &&
561 c->leaf.callback == callback &&
562 c->leaf.userdata == userdata) {
571 enum bus_match_node_type bus_match_node_type_from_string(const char *k, size_t n) {
574 if (n == 4 && startswith(k, "type"))
575 return BUS_MATCH_MESSAGE_TYPE;
576 if (n == 6 && startswith(k, "sender"))
577 return BUS_MATCH_SENDER;
578 if (n == 11 && startswith(k, "destination"))
579 return BUS_MATCH_DESTINATION;
580 if (n == 9 && startswith(k, "interface"))
581 return BUS_MATCH_INTERFACE;
582 if (n == 6 && startswith(k, "member"))
583 return BUS_MATCH_MEMBER;
584 if (n == 4 && startswith(k, "path"))
585 return BUS_MATCH_PATH;
586 if (n == 14 && startswith(k, "path_namespace"))
587 return BUS_MATCH_PATH_NAMESPACE;
589 if (n == 4 && startswith(k, "arg")) {
596 return BUS_MATCH_ARG + j;
599 if (n == 5 && startswith(k, "arg")) {
601 enum bus_match_node_type t;
608 t = BUS_MATCH_ARG + a * 10 + b;
609 if (t > BUS_MATCH_ARG_LAST)
615 if (n == 8 && startswith(k, "arg") && startswith(k + 4, "path")) {
622 return BUS_MATCH_ARG_PATH + j;
625 if (n == 9 && startswith(k, "arg") && startswith(k + 5, "path")) {
626 enum bus_match_node_type t;
634 t = BUS_MATCH_ARG_PATH + a * 10 + b;
635 if (t > BUS_MATCH_ARG_PATH_LAST)
641 if (n == 13 && startswith(k, "arg") && startswith(k + 4, "namespace")) {
648 return BUS_MATCH_ARG_NAMESPACE + j;
651 if (n == 14 && startswith(k, "arg") && startswith(k + 5, "namespace")) {
652 enum bus_match_node_type t;
660 t = BUS_MATCH_ARG_NAMESPACE + a * 10 + b;
661 if (t > BUS_MATCH_ARG_NAMESPACE_LAST)
670 static int match_component_compare(const void *a, const void *b) {
671 const struct bus_match_component *x = a, *y = b;
673 if (x->type < y->type)
675 if (x->type > y->type)
681 void bus_match_parse_free(struct bus_match_component *components, unsigned n_components) {
684 for (i = 0; i < n_components; i++)
685 free(components[i].value_str);
692 struct bus_match_component **_components,
693 unsigned *_n_components) {
695 const char *p = match;
696 struct bus_match_component *components = NULL;
697 size_t components_allocated = 0;
698 unsigned n_components = 0, i;
699 _cleanup_free_ char *value = NULL;
704 assert(_n_components);
708 enum bus_match_node_type t;
710 size_t value_allocated = 0;
711 bool escaped = false;
721 t = bus_match_node_type_from_string(p, eq - p);
725 for (q = eq + 2;; q++) {
744 if (!GREEDY_REALLOC(value, value_allocated, j + 2)) {
753 if (t == BUS_MATCH_MESSAGE_TYPE) {
754 r = bus_message_type_from_string(value, &u);
763 if (!GREEDY_REALLOC(components, components_allocated, n_components + 1)) {
768 components[n_components].type = t;
769 components[n_components].value_str = value;
770 components[n_components].value_u8 = u;
786 /* Order the whole thing, so that we always generate the same tree */
787 qsort_safe(components, n_components, sizeof(struct bus_match_component), match_component_compare);
789 /* Check for duplicates */
790 for (i = 0; i+1 < n_components; i++)
791 if (components[i].type == components[i+1].type) {
796 *_components = components;
797 *_n_components = n_components;
802 bus_match_parse_free(components, n_components);
807 struct bus_match_node *root,
808 struct bus_match_component *components,
809 unsigned n_components,
810 sd_bus_message_handler_t callback,
813 struct bus_match_node **ret) {
816 struct bus_match_node *n;
822 for (i = 0; i < n_components; i++) {
823 r = bus_match_add_compare_value(
824 n, components[i].type,
825 components[i].value_u8, components[i].value_str, &n);
830 r = bus_match_add_leaf(n, callback, userdata, cookie, &n);
840 int bus_match_remove(
841 struct bus_match_node *root,
842 struct bus_match_component *components,
843 unsigned n_components,
844 sd_bus_message_handler_t callback,
849 struct bus_match_node *n, **gc;
854 gc = newa(struct bus_match_node*, n_components);
857 for (i = 0; i < n_components; i++) {
858 r = bus_match_find_compare_value(
859 n, components[i].type,
860 components[i].value_u8, components[i].value_str,
868 r = bus_match_find_leaf(n, callback, userdata, &n);
873 *cookie = n->leaf.cookie;
876 bus_match_node_free(n);
878 /* Prune the tree above */
879 for (i = n_components; i > 0; i --) {
880 struct bus_match_node *p = gc[i-1]->parent;
882 if (!bus_match_node_maybe_free(gc[i-1]))
885 if (!bus_match_node_maybe_free(p))
892 void bus_match_free(struct bus_match_node *node) {
893 struct bus_match_node *c;
898 if (BUS_MATCH_CAN_HASH(node->type)) {
901 HASHMAP_FOREACH(c, node->compare.children, i)
904 assert(hashmap_isempty(node->compare.children));
907 while ((c = node->child))
910 if (node->type != BUS_MATCH_ROOT)
911 bus_match_node_free(node);
914 const char* bus_match_node_type_to_string(enum bus_match_node_type t, char buf[], size_t l) {
920 case BUS_MATCH_VALUE:
926 case BUS_MATCH_MESSAGE_TYPE:
929 case BUS_MATCH_SENDER:
932 case BUS_MATCH_DESTINATION:
933 return "destination";
935 case BUS_MATCH_INTERFACE:
938 case BUS_MATCH_MEMBER:
944 case BUS_MATCH_PATH_NAMESPACE:
945 return "path_namespace";
947 case BUS_MATCH_ARG ... BUS_MATCH_ARG_LAST:
948 snprintf(buf, l, "arg%i", t - BUS_MATCH_ARG);
951 case BUS_MATCH_ARG_PATH ... BUS_MATCH_ARG_PATH_LAST:
952 snprintf(buf, l, "arg%ipath", t - BUS_MATCH_ARG_PATH);
955 case BUS_MATCH_ARG_NAMESPACE ... BUS_MATCH_ARG_NAMESPACE_LAST:
956 snprintf(buf, l, "arg%inamespace", t - BUS_MATCH_ARG_NAMESPACE);
964 void bus_match_dump(struct bus_match_node *node, unsigned level) {
965 struct bus_match_node *c;
966 _cleanup_free_ char *pfx = NULL;
972 pfx = strrep(" ", level);
973 printf("%s[%s]", strempty(pfx), bus_match_node_type_to_string(node->type, buf, sizeof(buf)));
975 if (node->type == BUS_MATCH_VALUE) {
976 if (node->parent->type == BUS_MATCH_MESSAGE_TYPE)
977 printf(" <%u>\n", node->value.u8);
979 printf(" <%s>\n", node->value.str);
980 } else if (node->type == BUS_MATCH_ROOT)
982 else if (node->type == BUS_MATCH_LEAF)
983 printf(" %p/%p\n", node->leaf.callback, node->leaf.userdata);
987 if (BUS_MATCH_CAN_HASH(node->type)) {
990 HASHMAP_FOREACH(c, node->compare.children, i)
991 bus_match_dump(c, level + 1);
994 for (c = node->child; c; c = c->next)
995 bus_match_dump(c, level + 1);