src/libsystemd-bus/bus-match.c

   1 /*-*- Mode: C; c-basic-offset: 8; indent-tabs-mode: nil -*-*/
   2
   3 /***
   4   This file is part of systemd.
   5
   6   Copyright 2013 Lennart Poettering
   7
   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.
  12
  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.
  17
  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/>.
  20 ***/
  21
  22 #include "bus-internal.h"
  23 #include "bus-message.h"
  24 #include "bus-match.h"
  25
  26 /* Example:
  27  *
  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
  32  *  E: sender=miau
  33  *  F: type=signal
  34  *  G: type=signal
  35  *
  36  *  results in this tree:
  37  *
  38  *  BUS_MATCH_ROOT
  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
  57  *  ` BUS_MATCH_SENDER
  58  *    ` BUS_MATCH_VALUE: value == miau
  59  *      ` BUS_MATCH_LEAF: E
  60  */
  61
  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;
  64 }
  65
  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);
  69 }
  70
  71 static void bus_match_node_free(struct bus_match_node *node) {
  72         assert(node);
  73         assert(node->parent);
  74         assert(!node->child);
  75         assert(node->type != BUS_MATCH_ROOT);
  76         assert(node->type < _BUS_MATCH_NODE_TYPE_MAX);
  77
  78         if (node->parent->child) {
  79                 /* We are apparently linked into the parent's child
  80                  * list. Let's remove us from there. */
  81                 if (node->prev) {
  82                         assert(node->prev->next == node);
  83                         node->prev->next = node->next;
  84                 } else {
  85                         assert(node->parent->child == node);
  86                         node->parent->child = node->next;
  87                 }
  88
  89                 if (node->next)
  90                         node->next->prev = node->prev;
  91         }
  92
  93         if (node->type == BUS_MATCH_VALUE) {
  94                 /* We might be in the parent's hash table, so clean
  95                  * this up */
  96
  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);
 101
 102                 free(node->value.str);
 103         }
 104
 105         if (BUS_MATCH_IS_COMPARE(node->type)) {
 106                 assert(hashmap_isempty(node->compare.children));
 107                 hashmap_free(node->compare.children);
 108         }
 109
 110         free(node);
 111 }
 112
 113 static bool bus_match_node_maybe_free(struct bus_match_node *node) {
 114         assert(node);
 115
 116         if (node->child)
 117                 return false;
 118
 119         if (BUS_MATCH_IS_COMPARE(node->type) && !hashmap_isempty(node->compare.children))
 120                 return true;
 121
 122         bus_match_node_free(node);
 123         return true;
 124 }
 125
 126 static bool value_node_test(
 127                 struct bus_match_node *node,
 128                 enum bus_match_node_type parent_type,
 129                 uint8_t value_u8,
 130                 const char *value_str) {
 131
 132         assert(node);
 133         assert(node->type == BUS_MATCH_VALUE);
 134
 135         /* Tests parameters against this value node, doing prefix
 136          * magic and stuff. */
 137
 138         switch (parent_type) {
 139
 140         case BUS_MATCH_MESSAGE_TYPE:
 141                 return node->value.u8 == value_u8;
 142
 143         case BUS_MATCH_SENDER:
 144         case BUS_MATCH_DESTINATION:
 145         case BUS_MATCH_INTERFACE:
 146         case BUS_MATCH_MEMBER:
 147         case BUS_MATCH_PATH:
 148         case BUS_MATCH_ARG ... BUS_MATCH_ARG_LAST:
 149                 return streq(node->value.str, value_str);
 150
 151         case BUS_MATCH_ARG_NAMESPACE ... BUS_MATCH_ARG_NAMESPACE_LAST:
 152                 return namespace_simple_pattern(node->value.str, value_str);
 153
 154         case BUS_MATCH_PATH_NAMESPACE:
 155                 return path_simple_pattern(node->value.str, value_str);
 156
 157         case BUS_MATCH_ARG_PATH ... BUS_MATCH_ARG_PATH_LAST:
 158                 return path_complex_pattern(node->value.str, value_str);
 159
 160         default:
 161                 assert_not_reached("Invalid node type");
 162         }
 163 }
 164
 165 static bool value_node_same(
 166                 struct bus_match_node *node,
 167                 enum bus_match_node_type parent_type,
 168                 uint8_t value_u8,
 169                 const char *value_str) {
 170
 171         /* Tests parameters against this value node, not doing prefix
 172          * magic and stuff, i.e. this one actually compares the match
 173          * itself.*/
 174
 175         assert(node);
 176         assert(node->type == BUS_MATCH_VALUE);
 177
 178         switch (parent_type) {
 179
 180         case BUS_MATCH_MESSAGE_TYPE:
 181                 return node->value.u8 == value_u8;
 182
 183         case BUS_MATCH_SENDER:
 184         case BUS_MATCH_DESTINATION:
 185         case BUS_MATCH_INTERFACE:
 186         case BUS_MATCH_MEMBER:
 187         case BUS_MATCH_PATH:
 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);
 193
 194         default:
 195                 assert_not_reached("Invalid node type");
 196         }
 197 }
 198
 199 int bus_match_run(
 200                 sd_bus *bus,
 201                 struct bus_match_node *node,
 202                 int ret,
 203                 sd_bus_message *m) {
 204
 205
 206         const char *test_str = NULL;
 207         uint8_t test_u8 = 0;
 208         int r;
 209
 210         assert(m);
 211
 212         if (!node)
 213                 return 0;
 214
 215         if (bus && bus->match_callbacks_modified)
 216                 return 0;
 217
 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. */
 224
 225         switch (node->type) {
 226
 227         case BUS_MATCH_ROOT:
 228
 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);
 234
 235         case BUS_MATCH_VALUE:
 236
 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 */
 241
 242                 assert(node->child);
 243                 return bus_match_run(bus, node->child, ret, m);
 244
 245         case BUS_MATCH_LEAF:
 246
 247                 if (bus) {
 248                         if (node->leaf.last_iteration == bus->iteration_counter)
 249                                 return 0;
 250
 251                         node->leaf.last_iteration = bus->iteration_counter;
 252                 }
 253
 254                 /* Run the callback. And then invoke siblings. */
 255                 assert(node->leaf.callback);
 256                 r = node->leaf.callback(bus, ret, m, node->leaf.userdata);
 257                 if (r != 0)
 258                         return r;
 259
 260                 return bus_match_run(bus, node->next, ret, m);
 261
 262         case BUS_MATCH_MESSAGE_TYPE:
 263                 test_u8 = m->header->type;
 264                 break;
 265
 266         case BUS_MATCH_SENDER:
 267                 test_str = m->sender;
 268                 /* FIXME: resolve test_str from a well-known to a unique name first */
 269                 break;
 270
 271         case BUS_MATCH_DESTINATION:
 272                 test_str = m->destination;
 273                 break;
 274
 275         case BUS_MATCH_INTERFACE:
 276                 test_str = m->interface;
 277                 break;
 278
 279         case BUS_MATCH_MEMBER:
 280                 test_str = m->member;
 281                 break;
 282
 283         case BUS_MATCH_PATH:
 284         case BUS_MATCH_PATH_NAMESPACE:
 285                 test_str = m->path;
 286                 break;
 287
 288         case BUS_MATCH_ARG ... BUS_MATCH_ARG_LAST:
 289                 test_str = bus_message_get_arg(m, node->type - BUS_MATCH_ARG);
 290                 break;
 291
 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);
 294                 break;
 295
 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);
 298                 break;
 299
 300         default:
 301                 assert_not_reached("Unknown match type.");
 302         }
 303
 304         if (BUS_MATCH_CAN_HASH(node->type)) {
 305                 struct bus_match_node *found;
 306
 307                 /* Lookup via hash table, nice! So let's jump directly. */
 308
 309                 if (test_str)
 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));
 313                 else
 314                         found = NULL;
 315
 316                 if (found) {
 317                         r = bus_match_run(bus, found, ret, m);
 318                         if (r != 0)
 319                                 return r;
 320                 }
 321         } else {
 322                 struct bus_match_node *c;
 323
 324                 /* No hash table, so let's iterate manually... */
 325
 326                 for (c = node->child; c; c = c->next) {
 327                         if (!value_node_test(c, node->type, test_u8, test_str))
 328                                 continue;
 329
 330                         r = bus_match_run(bus, c, ret, m);
 331                         if (r != 0)
 332                                 return r;
 333                 }
 334         }
 335
 336         if (bus && bus->match_callbacks_modified)
 337                 return 0;
 338
 339         /* And now, let's invoke our siblings */
 340         return bus_match_run(bus, node->next, ret, m);
 341 }
 342
 343 static int bus_match_add_compare_value(
 344                 struct bus_match_node *where,
 345                 enum bus_match_node_type t,
 346                 uint8_t value_u8,
 347                 const char *value_str,
 348                 struct bus_match_node **ret) {
 349
 350         struct bus_match_node *c = NULL, *n = NULL;
 351         int r;
 352
 353         assert(where);
 354         assert(where->type == BUS_MATCH_ROOT || where->type == BUS_MATCH_VALUE);
 355         assert(BUS_MATCH_IS_COMPARE(t));
 356         assert(ret);
 357
 358         for (c = where->child; c && c->type != t; c = c->next)
 359                 ;
 360
 361         if (c) {
 362                 /* Comparison node already exists? Then let's see if
 363                  * the value node exists too. */
 364
 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);
 369                 else {
 370                         for (n = c->child; n && !value_node_same(n, t, value_u8, value_str); n = n->next)
 371                                 ;
 372                 }
 373
 374                 if (n) {
 375                         *ret = n;
 376                         return 0;
 377                 }
 378         } else {
 379                 /* Comparison node, doesn't exist yet? Then let's
 380                  * create it. */
 381
 382                 c = new0(struct bus_match_node, 1);
 383                 if (!c) {
 384                         r = -ENOMEM;
 385                         goto fail;
 386                 }
 387
 388                 c->type = t;
 389                 c->parent = where;
 390                 c->next = where->child;
 391                 if (c->next)
 392                         c->next->prev = c;
 393                 where->child = c;
 394
 395                 if (t == BUS_MATCH_MESSAGE_TYPE) {
 396                         c->compare.children = hashmap_new(trivial_hash_func, trivial_compare_func);
 397                         if (!c->compare.children) {
 398                                 r = -ENOMEM;
 399                                 goto fail;
 400                         }
 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) {
 404                                 r = -ENOMEM;
 405                                 goto fail;
 406                         }
 407                 }
 408         }
 409
 410         n = new0(struct bus_match_node, 1);
 411         if (!n) {
 412                 r = -ENOMEM;
 413                 goto fail;
 414         }
 415
 416         n->type = BUS_MATCH_VALUE;
 417         n->value.u8 = value_u8;
 418         if (value_str) {
 419                 n->value.str = strdup(value_str);
 420                 if (!n->value.str) {
 421                         r = -ENOMEM;
 422                         goto fail;
 423                 }
 424         }
 425
 426         n->parent = c;
 427         if (c->compare.children) {
 428
 429                 if (t == BUS_MATCH_MESSAGE_TYPE)
 430                         r = hashmap_put(c->compare.children, UINT_TO_PTR(value_u8), n);
 431                 else
 432                         r = hashmap_put(c->compare.children, n->value.str, n);
 433
 434                 if (r < 0)
 435                         goto fail;
 436         } else {
 437                 n->next = c->child;
 438                 if (n->next)
 439                         n->next->prev = n;
 440                 c->child = n;
 441         }
 442
 443         *ret = n;
 444         return 1;
 445
 446 fail:
 447         if (c)
 448                 bus_match_node_maybe_free(c);
 449
 450         if (n) {
 451                 free(n->value.str);
 452                 free(n);
 453         }
 454
 455         return r;
 456 }
 457
 458 static int bus_match_find_compare_value(
 459                 struct bus_match_node *where,
 460                 enum bus_match_node_type t,
 461                 uint8_t value_u8,
 462                 const char *value_str,
 463                 struct bus_match_node **ret) {
 464
 465         struct bus_match_node *c, *n;
 466
 467         assert(where);
 468         assert(where->type == BUS_MATCH_ROOT || where->type == BUS_MATCH_VALUE);
 469         assert(BUS_MATCH_IS_COMPARE(t));
 470         assert(ret);
 471
 472         for (c = where->child; c && c->type != t; c = c->next)
 473                 ;
 474
 475         if (!c)
 476                 return 0;
 477
 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);
 482         else {
 483                 for (n = c->child; !value_node_same(n, t, value_u8, value_str); n = n->next)
 484                         ;
 485         }
 486
 487         if (n) {
 488                 *ret = n;
 489                 return 1;
 490         }
 491
 492         return 0;
 493 }
 494
 495 static int bus_match_add_leaf(
 496                 struct bus_match_node *where,
 497                 sd_bus_message_handler_t callback,
 498                 void *userdata,
 499                 struct bus_match_node **ret) {
 500
 501         struct bus_match_node *n;
 502
 503         assert(where);
 504         assert(where->type == BUS_MATCH_ROOT || where->type == BUS_MATCH_VALUE);
 505         assert(ret);
 506
 507         n = new0(struct bus_match_node, 1);
 508         if (!n)
 509                 return -ENOMEM;
 510
 511         n->type = BUS_MATCH_LEAF;
 512         n->parent = where;
 513         n->next = where->child;
 514         if (n->next)
 515                 n->next->prev = n;
 516         n->leaf.callback = callback;
 517         n->leaf.userdata = userdata;
 518
 519         where->child = n;
 520
 521         *ret = n;
 522         return 1;
 523 }
 524
 525 static int bus_match_find_leaf(
 526                 struct bus_match_node *where,
 527                 sd_bus_message_handler_t callback,
 528                 void *userdata,
 529                 struct bus_match_node **ret) {
 530
 531         struct bus_match_node *c;
 532
 533         assert(where);
 534         assert(where->type == BUS_MATCH_ROOT || where->type == BUS_MATCH_VALUE);
 535         assert(ret);
 536
 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) {
 541                         *ret = c;
 542                         return 1;
 543                 }
 544         }
 545
 546         return 0;
 547 }
 548
 549 enum bus_match_node_type bus_match_node_type_from_string(const char *k, size_t n) {
 550         assert(k);
 551
 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;
 566
 567         if (n == 4 && memcmp(k, "arg", 3) == 0) {
 568                 int j;
 569
 570                 j = undecchar(k[3]);
 571                 if (j < 0)
 572                         return -EINVAL;
 573
 574                 return BUS_MATCH_ARG + j;
 575         }
 576
 577         if (n == 5 && memcmp(k, "arg", 3) == 0) {
 578                 int a, b;
 579                 enum bus_match_node_type t;
 580
 581                 a = undecchar(k[3]);
 582                 b = undecchar(k[4]);
 583                 if (a <= 0 || b < 0)
 584                         return -EINVAL;
 585
 586                 t = BUS_MATCH_ARG + a * 10 + b;
 587                 if (t > BUS_MATCH_ARG_LAST)
 588                         return -EINVAL;
 589
 590                 return t;
 591         }
 592
 593         if (n == 8 && memcmp(k, "arg", 3) == 0 && memcmp(k + 4, "path", 4) == 0) {
 594                 int j;
 595
 596                 j = undecchar(k[3]);
 597                 if (j < 0)
 598                         return -EINVAL;
 599
 600                 return BUS_MATCH_ARG_PATH + j;
 601         }
 602
 603         if (n == 9 && memcmp(k, "arg", 3) == 0 && memcmp(k + 5, "path", 4) == 0) {
 604                 enum bus_match_node_type t;
 605                 int a, b;
 606
 607                 a = undecchar(k[3]);
 608                 b = undecchar(k[4]);
 609                 if (a <= 0 || b < 0)
 610                         return -EINVAL;
 611
 612                 t = BUS_MATCH_ARG_PATH + a * 10 + b;
 613                 if (t > BUS_MATCH_ARG_PATH_LAST)
 614                         return -EINVAL;
 615
 616                 return t;
 617         }
 618
 619         if (n == 13 && memcmp(k, "arg", 3) == 0 && memcmp(k + 4, "namespace", 9) == 0) {
 620                 int j;
 621
 622                 j = undecchar(k[3]);
 623                 if (j < 0)
 624                         return -EINVAL;
 625
 626                 return BUS_MATCH_ARG_NAMESPACE + j;
 627         }
 628
 629         if (n == 14 && memcmp(k, "arg", 3) == 0 && memcmp(k + 5, "namespace", 9) == 0) {
 630                 enum bus_match_node_type t;
 631                 int a, b;
 632
 633                 a = undecchar(k[3]);
 634                 b = undecchar(k[4]);
 635                 if (a <= 0 || b < 0)
 636                         return -EINVAL;
 637
 638                 t = BUS_MATCH_ARG_NAMESPACE + a * 10 + b;
 639                 if (t > BUS_MATCH_ARG_NAMESPACE_LAST)
 640                         return -EINVAL;
 641
 642                 return t;
 643         }
 644
 645         return -EINVAL;
 646 }
 647
 648 struct match_component {
 649         enum bus_match_node_type type;
 650         uint8_t value_u8;
 651         char *value_str;
 652 };
 653
 654 static int match_component_compare(const void *a, const void *b) {
 655         const struct match_component *x = a, *y = b;
 656
 657         if (x->type < y->type)
 658                 return -1;
 659         if (x->type > y->type)
 660                 return 1;
 661
 662         return 0;
 663 }
 664
 665 static void free_components(struct match_component *components, unsigned n_components) {
 666         unsigned i;
 667
 668         for (i = 0; i < n_components; i++)
 669                 free(components[i].value_str);
 670
 671         free(components);
 672 }
 673
 674 static int parse_match(
 675                 const char *match,
 676                 struct match_component **_components,
 677                 unsigned *_n_components) {
 678
 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;
 684         int r;
 685
 686         assert(match);
 687         assert(_components);
 688         assert(_n_components);
 689
 690         while (*p != 0) {
 691                 const char *eq, *q;
 692                 enum bus_match_node_type t;
 693                 unsigned j = 0;
 694                 size_t value_allocated = 0;
 695                 bool escaped = false;
 696                 uint8_t u;
 697
 698                 eq = strchr(p, '=');
 699                 if (!eq)
 700                         return -EINVAL;
 701
 702                 if (eq[1] != '\'')
 703                         return -EINVAL;
 704
 705                 t = bus_match_node_type_from_string(p, eq - p);
 706                 if (t < 0)
 707                         return -EINVAL;
 708
 709                 for (q = eq + 2;; q++) {
 710
 711                         if (*q == 0) {
 712                                 r = -EINVAL;
 713                                 goto fail;
 714                         }
 715
 716                         if (!escaped) {
 717                                 if (*q == '\\') {
 718                                         escaped = true;
 719                                         continue;
 720                                 }
 721                                 if (*q == '\'') {
 722                                         if (value)
 723                                                 value[j] = 0;
 724                                         break;
 725                                 }
 726                         }
 727
 728                         if (!greedy_realloc((void**) &value, &value_allocated, j + 2)) {
 729                                 r = -ENOMEM;
 730                                 goto fail;
 731                         }
 732
 733                         value[j++] = *q;
 734                         escaped = false;
 735                 }
 736
 737                 if (t == BUS_MATCH_MESSAGE_TYPE) {
 738                         r = bus_message_type_from_string(value, &u);
 739                         if (r < 0)
 740                                 goto fail;
 741
 742                         free(value);
 743                         value = NULL;
 744                 } else
 745                         u = 0;
 746
 747                 if (!greedy_realloc((void**) &components, &components_allocated,
 748                                     (n_components + 1) * sizeof(struct match_component))) {
 749                         r = -ENOMEM;
 750                         goto fail;
 751                 }
 752
 753                 components[n_components].type = t;
 754                 components[n_components].value_str = value;
 755                 components[n_components].value_u8 = u;
 756                 n_components++;
 757
 758                 value = NULL;
 759
 760                 if (q[1] == 0)
 761                         break;
 762
 763                 if (q[1] != ',') {
 764                         r = -EINVAL;
 765                         goto fail;
 766                 }
 767
 768                 p = q + 2;
 769         }
 770
 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);
 773
 774         /* Check for duplicates */
 775         for (i = 0; i+1 < n_components; i++)
 776                 if (components[i].type == components[i+1].type) {
 777                         r = -EINVAL;
 778                         goto fail;
 779                 }
 780
 781         *_components = components;
 782         *_n_components = n_components;
 783
 784         return 0;
 785
 786 fail:
 787         free_components(components, n_components);
 788         return r;
 789 }
 790
 791 int bus_match_add(
 792                 struct bus_match_node *root,
 793                 const char *match,
 794                 sd_bus_message_handler_t callback,
 795                 void *userdata,
 796                 struct bus_match_node **ret) {
 797
 798         struct match_component *components = NULL;
 799         unsigned n_components = 0, i;
 800         struct bus_match_node *n;
 801         int r;
 802
 803         assert(root);
 804         assert(match);
 805         assert(callback);
 806
 807         r = parse_match(match, &components, &n_components);
 808         if (r < 0)
 809                 return r;
 810
 811         n = root;
 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);
 816                 if (r < 0)
 817                         goto finish;
 818         }
 819
 820         r = bus_match_add_leaf(n, callback, userdata, &n);
 821         if (r < 0)
 822                 goto finish;
 823
 824         if (ret)
 825                 *ret = n;
 826
 827 finish:
 828         free_components(components, n_components);
 829         return r;
 830 }
 831
 832 int bus_match_remove(
 833                 struct bus_match_node *root,
 834                 const char *match,
 835                 sd_bus_message_handler_t callback,
 836                 void *userdata) {
 837
 838         struct match_component *components = NULL;
 839         unsigned n_components = 0, i;
 840         struct bus_match_node *n, **gc;
 841         int r;
 842
 843         assert(root);
 844         assert(match);
 845
 846         r = parse_match(match, &components, &n_components);
 847         if (r < 0)
 848                 return r;
 849
 850         gc = newa(struct bus_match_node*, n_components);
 851
 852         n = root;
 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,
 857                                 &n);
 858                 if (r <= 0)
 859                         goto finish;
 860
 861                 gc[i] = n;
 862         }
 863
 864         r = bus_match_find_leaf(n, callback, userdata, &n);
 865         if (r <= 0)
 866                 goto finish;
 867
 868         /* Free the leaf */
 869         bus_match_node_free(n);
 870
 871         /* Prune the tree above */
 872         for (i = n_components; i > 0; i --) {
 873                 struct bus_match_node *p = gc[i-1]->parent;
 874
 875                 if (!bus_match_node_maybe_free(gc[i-1]))
 876                         break;
 877
 878                 if (!bus_match_node_maybe_free(p))
 879                         break;
 880         }
 881
 882 finish:
 883         free_components(components, n_components);
 884         return r;
 885 }
 886
 887 void bus_match_free(struct bus_match_node *node) {
 888         struct bus_match_node *c;
 889
 890         if (!node)
 891                 return;
 892
 893         if (BUS_MATCH_CAN_HASH(node->type)) {
 894                 Iterator i;
 895
 896                 HASHMAP_FOREACH(c, node->compare.children, i)
 897                         bus_match_free(c);
 898
 899                 assert(hashmap_isempty(node->compare.children));
 900         }
 901
 902         while ((c = node->child))
 903                 bus_match_free(c);
 904
 905         if (node->type != BUS_MATCH_ROOT)
 906                 bus_match_node_free(node);
 907 }
 908
 909 const char* bus_match_node_type_to_string(enum bus_match_node_type t, char buf[], size_t l) {
 910         switch (t) {
 911
 912         case BUS_MATCH_ROOT:
 913                 return "root";
 914
 915         case BUS_MATCH_VALUE:
 916                 return "value";
 917
 918         case BUS_MATCH_LEAF:
 919                 return "leaf";
 920
 921         case BUS_MATCH_MESSAGE_TYPE:
 922                 return "type";
 923
 924         case BUS_MATCH_SENDER:
 925                 return "sender";
 926
 927         case BUS_MATCH_DESTINATION:
 928                 return "destination";
 929
 930         case BUS_MATCH_INTERFACE:
 931                 return "interface";
 932
 933         case BUS_MATCH_MEMBER:
 934                 return "member";
 935
 936         case BUS_MATCH_PATH:
 937                 return "path";
 938
 939         case BUS_MATCH_PATH_NAMESPACE:
 940                 return "path_namespace";
 941
 942         case BUS_MATCH_ARG ... BUS_MATCH_ARG_LAST:
 943                 snprintf(buf, l, "arg%i", t - BUS_MATCH_ARG);
 944                 return buf;
 945
 946         case BUS_MATCH_ARG_PATH ... BUS_MATCH_ARG_PATH_LAST:
 947                 snprintf(buf, l, "arg%ipath", t - BUS_MATCH_ARG_PATH);
 948                 return buf;
 949
 950         case BUS_MATCH_ARG_NAMESPACE ... BUS_MATCH_ARG_NAMESPACE_LAST:
 951                 snprintf(buf, l, "arg%inamespace", t - BUS_MATCH_ARG_NAMESPACE);
 952                 return buf;
 953
 954         default:
 955                 return NULL;
 956         }
 957 }
 958
 959 void bus_match_dump(struct bus_match_node *node, unsigned level) {
 960         struct bus_match_node *c;
 961         _cleanup_free_ char *pfx = NULL;
 962         char buf[32];
 963
 964         if (!node)
 965                 return;
 966
 967         pfx = strrep("  ", level);
 968         printf("%s[%s]", strempty(pfx), bus_match_node_type_to_string(node->type, buf, sizeof(buf)));
 969
 970         if (node->type == BUS_MATCH_VALUE) {
 971                 if (node->parent->type == BUS_MATCH_MESSAGE_TYPE)
 972                         printf(" <%u>\n", node->value.u8);
 973                 else
 974                         printf(" <%s>\n", node->value.str);
 975         } else if (node->type == BUS_MATCH_ROOT)
 976                 puts(" root");
 977         else if (node->type == BUS_MATCH_LEAF)
 978                 printf(" %p/%p\n", node->leaf.callback, node->leaf.userdata);
 979         else
 980                 putchar('\n');
 981
 982         if (BUS_MATCH_CAN_HASH(node->type)) {
 983                 Iterator i;
 984
 985                 HASHMAP_FOREACH(c, node->compare.children, i)
 986                         bus_match_dump(c, level + 1);
 987         }
 988
 989         for (c = node->child; c; c = c->next)
 990                 bus_match_dump(c, level + 1);
 991 }