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,
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 r = sd_bus_message_rewind(m, true);
258 /* Run the callback. And then invoke siblings. */
259 assert(node->leaf.callback);
260 r = node->leaf.callback(bus, ret, m, node->leaf.userdata);
264 return bus_match_run(bus, node->next, ret, 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, ret, 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, ret, m);
340 if (bus && bus->match_callbacks_modified)
343 /* And now, let's invoke our siblings */
344 return bus_match_run(bus, node->next, ret, 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,
503 struct bus_match_node **ret) {
505 struct bus_match_node *n;
508 assert(where->type == BUS_MATCH_ROOT || where->type == BUS_MATCH_VALUE);
511 n = new0(struct bus_match_node, 1);
515 n->type = BUS_MATCH_LEAF;
517 n->next = where->child;
520 n->leaf.callback = callback;
521 n->leaf.userdata = userdata;
529 static int bus_match_find_leaf(
530 struct bus_match_node *where,
531 sd_bus_message_handler_t callback,
533 struct bus_match_node **ret) {
535 struct bus_match_node *c;
538 assert(where->type == BUS_MATCH_ROOT || where->type == BUS_MATCH_VALUE);
541 for (c = where->child; c; c = c->next) {
542 if (c->type == BUS_MATCH_LEAF &&
543 c->leaf.callback == callback &&
544 c->leaf.userdata == userdata) {
553 enum bus_match_node_type bus_match_node_type_from_string(const char *k, size_t n) {
556 if (n == 4 && memcmp(k, "type", 4) == 0)
557 return BUS_MATCH_MESSAGE_TYPE;
558 if (n == 6 && memcmp(k, "sender", 6) == 0)
559 return BUS_MATCH_SENDER;
560 if (n == 11 && memcmp(k, "destination", 11) == 0)
561 return BUS_MATCH_DESTINATION;
562 if (n == 9 && memcmp(k, "interface", 9) == 0)
563 return BUS_MATCH_INTERFACE;
564 if (n == 6 && memcmp(k, "member", 6) == 0)
565 return BUS_MATCH_MEMBER;
566 if (n == 4 && memcmp(k, "path", 4) == 0)
567 return BUS_MATCH_PATH;
568 if (n == 14 && memcmp(k, "path_namespace", 14) == 0)
569 return BUS_MATCH_PATH_NAMESPACE;
571 if (n == 4 && memcmp(k, "arg", 3) == 0) {
578 return BUS_MATCH_ARG + j;
581 if (n == 5 && memcmp(k, "arg", 3) == 0) {
583 enum bus_match_node_type t;
590 t = BUS_MATCH_ARG + a * 10 + b;
591 if (t > BUS_MATCH_ARG_LAST)
597 if (n == 8 && memcmp(k, "arg", 3) == 0 && memcmp(k + 4, "path", 4) == 0) {
604 return BUS_MATCH_ARG_PATH + j;
607 if (n == 9 && memcmp(k, "arg", 3) == 0 && memcmp(k + 5, "path", 4) == 0) {
608 enum bus_match_node_type t;
616 t = BUS_MATCH_ARG_PATH + a * 10 + b;
617 if (t > BUS_MATCH_ARG_PATH_LAST)
623 if (n == 13 && memcmp(k, "arg", 3) == 0 && memcmp(k + 4, "namespace", 9) == 0) {
630 return BUS_MATCH_ARG_NAMESPACE + j;
633 if (n == 14 && memcmp(k, "arg", 3) == 0 && memcmp(k + 5, "namespace", 9) == 0) {
634 enum bus_match_node_type t;
642 t = BUS_MATCH_ARG_NAMESPACE + a * 10 + b;
643 if (t > BUS_MATCH_ARG_NAMESPACE_LAST)
652 struct match_component {
653 enum bus_match_node_type type;
658 static int match_component_compare(const void *a, const void *b) {
659 const struct match_component *x = a, *y = b;
661 if (x->type < y->type)
663 if (x->type > y->type)
669 static void free_components(struct match_component *components, unsigned n_components) {
672 for (i = 0; i < n_components; i++)
673 free(components[i].value_str);
678 static int parse_match(
680 struct match_component **_components,
681 unsigned *_n_components) {
683 const char *p = match;
684 struct match_component *components = NULL;
685 size_t components_allocated = 0;
686 unsigned n_components = 0, i;
687 _cleanup_free_ char *value = NULL;
692 assert(_n_components);
696 enum bus_match_node_type t;
698 size_t value_allocated = 0;
699 bool escaped = false;
709 t = bus_match_node_type_from_string(p, eq - p);
713 for (q = eq + 2;; q++) {
732 if (!GREEDY_REALLOC(value, value_allocated, j + 2)) {
741 if (t == BUS_MATCH_MESSAGE_TYPE) {
742 r = bus_message_type_from_string(value, &u);
751 if (!GREEDY_REALLOC(components, components_allocated, n_components + 1)) {
756 components[n_components].type = t;
757 components[n_components].value_str = value;
758 components[n_components].value_u8 = u;
774 /* Order the whole thing, so that we always generate the same tree */
775 qsort(components, n_components, sizeof(struct match_component), match_component_compare);
777 /* Check for duplicates */
778 for (i = 0; i+1 < n_components; i++)
779 if (components[i].type == components[i+1].type) {
784 *_components = components;
785 *_n_components = n_components;
790 free_components(components, n_components);
795 struct bus_match_node *root,
797 sd_bus_message_handler_t callback,
799 struct bus_match_node **ret) {
801 struct match_component *components = NULL;
802 unsigned n_components = 0, i;
803 struct bus_match_node *n;
810 r = parse_match(match, &components, &n_components);
815 for (i = 0; i < n_components; i++) {
816 r = bus_match_add_compare_value(
817 n, components[i].type,
818 components[i].value_u8, components[i].value_str, &n);
823 r = bus_match_add_leaf(n, callback, userdata, &n);
831 free_components(components, n_components);
835 int bus_match_remove(
836 struct bus_match_node *root,
838 sd_bus_message_handler_t callback,
841 struct match_component *components = NULL;
842 unsigned n_components = 0, i;
843 struct bus_match_node *n, **gc;
849 r = parse_match(match, &components, &n_components);
853 gc = newa(struct bus_match_node*, n_components);
856 for (i = 0; i < n_components; i++) {
857 r = bus_match_find_compare_value(
858 n, components[i].type,
859 components[i].value_u8, components[i].value_str,
867 r = bus_match_find_leaf(n, callback, userdata, &n);
872 bus_match_node_free(n);
874 /* Prune the tree above */
875 for (i = n_components; i > 0; i --) {
876 struct bus_match_node *p = gc[i-1]->parent;
878 if (!bus_match_node_maybe_free(gc[i-1]))
881 if (!bus_match_node_maybe_free(p))
886 free_components(components, n_components);
890 void bus_match_free(struct bus_match_node *node) {
891 struct bus_match_node *c;
896 if (BUS_MATCH_CAN_HASH(node->type)) {
899 HASHMAP_FOREACH(c, node->compare.children, i)
902 assert(hashmap_isempty(node->compare.children));
905 while ((c = node->child))
908 if (node->type != BUS_MATCH_ROOT)
909 bus_match_node_free(node);
912 const char* bus_match_node_type_to_string(enum bus_match_node_type t, char buf[], size_t l) {
918 case BUS_MATCH_VALUE:
924 case BUS_MATCH_MESSAGE_TYPE:
927 case BUS_MATCH_SENDER:
930 case BUS_MATCH_DESTINATION:
931 return "destination";
933 case BUS_MATCH_INTERFACE:
936 case BUS_MATCH_MEMBER:
942 case BUS_MATCH_PATH_NAMESPACE:
943 return "path_namespace";
945 case BUS_MATCH_ARG ... BUS_MATCH_ARG_LAST:
946 snprintf(buf, l, "arg%i", t - BUS_MATCH_ARG);
949 case BUS_MATCH_ARG_PATH ... BUS_MATCH_ARG_PATH_LAST:
950 snprintf(buf, l, "arg%ipath", t - BUS_MATCH_ARG_PATH);
953 case BUS_MATCH_ARG_NAMESPACE ... BUS_MATCH_ARG_NAMESPACE_LAST:
954 snprintf(buf, l, "arg%inamespace", t - BUS_MATCH_ARG_NAMESPACE);
962 void bus_match_dump(struct bus_match_node *node, unsigned level) {
963 struct bus_match_node *c;
964 _cleanup_free_ char *pfx = NULL;
970 pfx = strrep(" ", level);
971 printf("%s[%s]", strempty(pfx), bus_match_node_type_to_string(node->type, buf, sizeof(buf)));
973 if (node->type == BUS_MATCH_VALUE) {
974 if (node->parent->type == BUS_MATCH_MESSAGE_TYPE)
975 printf(" <%u>\n", node->value.u8);
977 printf(" <%s>\n", node->value.str);
978 } else if (node->type == BUS_MATCH_ROOT)
980 else if (node->type == BUS_MATCH_LEAF)
981 printf(" %p/%p\n", node->leaf.callback, node->leaf.userdata);
985 if (BUS_MATCH_CAN_HASH(node->type)) {
988 HASHMAP_FOREACH(c, node->compare.children, i)
989 bus_match_dump(c, level + 1);
992 for (c = node->child; c; c = c->next)
993 bus_match_dump(c, level + 1);