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_SENDER && 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                 if (streq_ptr(node->value.str, value_str))
 146                         return true;
 147
 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. */
 155
 156                 if (node->value.str[0] != ':' && value_str && value_str[0] == ':')
 157                         return true;
 158
 159                 return false;
 160
 161         case BUS_MATCH_INTERFACE:
 162         case BUS_MATCH_MEMBER:
 163         case BUS_MATCH_PATH:
 164         case BUS_MATCH_ARG ... BUS_MATCH_ARG_LAST:
 165                 return streq_ptr(node->value.str, value_str);
 166
 167         case BUS_MATCH_ARG_NAMESPACE ... BUS_MATCH_ARG_NAMESPACE_LAST:
 168                 return namespace_simple_pattern(node->value.str, value_str);
 169
 170         case BUS_MATCH_PATH_NAMESPACE:
 171                 return path_simple_pattern(node->value.str, value_str);
 172
 173         case BUS_MATCH_ARG_PATH ... BUS_MATCH_ARG_PATH_LAST:
 174                 return path_complex_pattern(node->value.str, value_str);
 175
 176         default:
 177                 assert_not_reached("Invalid node type");
 178         }
 179 }
 180
 181 static bool value_node_same(
 182                 struct bus_match_node *node,
 183                 enum bus_match_node_type parent_type,
 184                 uint8_t value_u8,
 185                 const char *value_str) {
 186
 187         /* Tests parameters against this value node, not doing prefix
 188          * magic and stuff, i.e. this one actually compares the match
 189          * itself.*/
 190
 191         assert(node);
 192         assert(node->type == BUS_MATCH_VALUE);
 193
 194         switch (parent_type) {
 195
 196         case BUS_MATCH_MESSAGE_TYPE:
 197                 return node->value.u8 == value_u8;
 198
 199         case BUS_MATCH_SENDER:
 200         case BUS_MATCH_DESTINATION:
 201         case BUS_MATCH_INTERFACE:
 202         case BUS_MATCH_MEMBER:
 203         case BUS_MATCH_PATH:
 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);
 209
 210         default:
 211                 assert_not_reached("Invalid node type");
 212         }
 213 }
 214
 215 int bus_match_run(
 216                 sd_bus *bus,
 217                 struct bus_match_node *node,
 218                 sd_bus_message *m) {
 219
 220
 221         const char *test_str = NULL;
 222         uint8_t test_u8 = 0;
 223         int r;
 224
 225         assert(m);
 226
 227         if (!node)
 228                 return 0;
 229
 230         if (bus && bus->match_callbacks_modified)
 231                 return 0;
 232
 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. */
 239
 240         switch (node->type) {
 241
 242         case BUS_MATCH_ROOT:
 243
 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);
 249
 250         case BUS_MATCH_VALUE:
 251
 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 */
 256
 257                 assert(node->child);
 258                 return bus_match_run(bus, node->child, m);
 259
 260         case BUS_MATCH_LEAF:
 261
 262                 if (bus) {
 263                         if (node->leaf.last_iteration == bus->iteration_counter)
 264                                 return 0;
 265
 266                         node->leaf.last_iteration = bus->iteration_counter;
 267                 }
 268
 269                 r = sd_bus_message_rewind(m, true);
 270                 if (r < 0)
 271                         return r;
 272
 273                 /* Run the callback. And then invoke siblings. */
 274                 if (node->leaf.callback) {
 275                         r = node->leaf.callback(bus, m, node->leaf.userdata);
 276                         if (r != 0)
 277                                 return r;
 278                 }
 279
 280                 return bus_match_run(bus, node->next, m);
 281
 282         case BUS_MATCH_MESSAGE_TYPE:
 283                 test_u8 = m->header->type;
 284                 break;
 285
 286         case BUS_MATCH_SENDER:
 287                 test_str = m->sender;
 288                 /* FIXME: resolve test_str from a well-known to a unique name first */
 289                 break;
 290
 291         case BUS_MATCH_DESTINATION:
 292                 test_str = m->destination;
 293                 break;
 294
 295         case BUS_MATCH_INTERFACE:
 296                 test_str = m->interface;
 297                 break;
 298
 299         case BUS_MATCH_MEMBER:
 300                 test_str = m->member;
 301                 break;
 302
 303         case BUS_MATCH_PATH:
 304         case BUS_MATCH_PATH_NAMESPACE:
 305                 test_str = m->path;
 306                 break;
 307
 308         case BUS_MATCH_ARG ... BUS_MATCH_ARG_LAST:
 309                 test_str = bus_message_get_arg(m, node->type - BUS_MATCH_ARG);
 310                 break;
 311
 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);
 314                 break;
 315
 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);
 318                 break;
 319
 320         default:
 321                 assert_not_reached("Unknown match type.");
 322         }
 323
 324         if (BUS_MATCH_CAN_HASH(node->type)) {
 325                 struct bus_match_node *found;
 326
 327                 /* Lookup via hash table, nice! So let's jump directly. */
 328
 329                 if (test_str)
 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));
 333                 else
 334                         found = NULL;
 335
 336                 if (found) {
 337                         r = bus_match_run(bus, found, m);
 338                         if (r != 0)
 339                                 return r;
 340                 }
 341         } else {
 342                 struct bus_match_node *c;
 343
 344                 /* No hash table, so let's iterate manually... */
 345
 346                 for (c = node->child; c; c = c->next) {
 347                         if (!value_node_test(c, node->type, test_u8, test_str))
 348                                 continue;
 349
 350                         r = bus_match_run(bus, c, m);
 351                         if (r != 0)
 352                                 return r;
 353                 }
 354         }
 355
 356         if (bus && bus->match_callbacks_modified)
 357                 return 0;
 358
 359         /* And now, let's invoke our siblings */
 360         return bus_match_run(bus, node->next, m);
 361 }
 362
 363 static int bus_match_add_compare_value(
 364                 struct bus_match_node *where,
 365                 enum bus_match_node_type t,
 366                 uint8_t value_u8,
 367                 const char *value_str,
 368                 struct bus_match_node **ret) {
 369
 370         struct bus_match_node *c = NULL, *n = NULL;
 371         int r;
 372
 373         assert(where);
 374         assert(where->type == BUS_MATCH_ROOT || where->type == BUS_MATCH_VALUE);
 375         assert(BUS_MATCH_IS_COMPARE(t));
 376         assert(ret);
 377
 378         for (c = where->child; c && c->type != t; c = c->next)
 379                 ;
 380
 381         if (c) {
 382                 /* Comparison node already exists? Then let's see if
 383                  * the value node exists too. */
 384
 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);
 389                 else {
 390                         for (n = c->child; n && !value_node_same(n, t, value_u8, value_str); n = n->next)
 391                                 ;
 392                 }
 393
 394                 if (n) {
 395                         *ret = n;
 396                         return 0;
 397                 }
 398         } else {
 399                 /* Comparison node, doesn't exist yet? Then let's
 400                  * create it. */
 401
 402                 c = new0(struct bus_match_node, 1);
 403                 if (!c) {
 404                         r = -ENOMEM;
 405                         goto fail;
 406                 }
 407
 408                 c->type = t;
 409                 c->parent = where;
 410                 c->next = where->child;
 411                 if (c->next)
 412                         c->next->prev = c;
 413                 where->child = c;
 414
 415                 if (t == BUS_MATCH_MESSAGE_TYPE) {
 416                         c->compare.children = hashmap_new(trivial_hash_func, trivial_compare_func);
 417                         if (!c->compare.children) {
 418                                 r = -ENOMEM;
 419                                 goto fail;
 420                         }
 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) {
 424                                 r = -ENOMEM;
 425                                 goto fail;
 426                         }
 427                 }
 428         }
 429
 430         n = new0(struct bus_match_node, 1);
 431         if (!n) {
 432                 r = -ENOMEM;
 433                 goto fail;
 434         }
 435
 436         n->type = BUS_MATCH_VALUE;
 437         n->value.u8 = value_u8;
 438         if (value_str) {
 439                 n->value.str = strdup(value_str);
 440                 if (!n->value.str) {
 441                         r = -ENOMEM;
 442                         goto fail;
 443                 }
 444         }
 445
 446         n->parent = c;
 447         if (c->compare.children) {
 448
 449                 if (t == BUS_MATCH_MESSAGE_TYPE)
 450                         r = hashmap_put(c->compare.children, UINT_TO_PTR(value_u8), n);
 451                 else
 452                         r = hashmap_put(c->compare.children, n->value.str, n);
 453
 454                 if (r < 0)
 455                         goto fail;
 456         } else {
 457                 n->next = c->child;
 458                 if (n->next)
 459                         n->next->prev = n;
 460                 c->child = n;
 461         }
 462
 463         *ret = n;
 464         return 1;
 465
 466 fail:
 467         if (c)
 468                 bus_match_node_maybe_free(c);
 469
 470         if (n) {
 471                 free(n->value.str);
 472                 free(n);
 473         }
 474
 475         return r;
 476 }
 477
 478 static int bus_match_find_compare_value(
 479                 struct bus_match_node *where,
 480                 enum bus_match_node_type t,
 481                 uint8_t value_u8,
 482                 const char *value_str,
 483                 struct bus_match_node **ret) {
 484
 485         struct bus_match_node *c, *n;
 486
 487         assert(where);
 488         assert(where->type == BUS_MATCH_ROOT || where->type == BUS_MATCH_VALUE);
 489         assert(BUS_MATCH_IS_COMPARE(t));
 490         assert(ret);
 491
 492         for (c = where->child; c && c->type != t; c = c->next)
 493                 ;
 494
 495         if (!c)
 496                 return 0;
 497
 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);
 502         else {
 503                 for (n = c->child; !value_node_same(n, t, value_u8, value_str); n = n->next)
 504                         ;
 505         }
 506
 507         if (n) {
 508                 *ret = n;
 509                 return 1;
 510         }
 511
 512         return 0;
 513 }
 514
 515 static int bus_match_add_leaf(
 516                 struct bus_match_node *where,
 517                 sd_bus_message_handler_t callback,
 518                 void *userdata,
 519                 uint64_t cookie,
 520                 struct bus_match_node **ret) {
 521
 522         struct bus_match_node *n;
 523
 524         assert(where);
 525         assert(where->type == BUS_MATCH_ROOT || where->type == BUS_MATCH_VALUE);
 526         assert(ret);
 527
 528         n = new0(struct bus_match_node, 1);
 529         if (!n)
 530                 return -ENOMEM;
 531
 532         n->type = BUS_MATCH_LEAF;
 533         n->parent = where;
 534         n->next = where->child;
 535         if (n->next)
 536                 n->next->prev = n;
 537         n->leaf.callback = callback;
 538         n->leaf.userdata = userdata;
 539         n->leaf.cookie = cookie;
 540
 541         where->child = n;
 542
 543         *ret = n;
 544         return 1;
 545 }
 546
 547 static int bus_match_find_leaf(
 548                 struct bus_match_node *where,
 549                 sd_bus_message_handler_t callback,
 550                 void *userdata,
 551                 struct bus_match_node **ret) {
 552
 553         struct bus_match_node *c;
 554
 555         assert(where);
 556         assert(where->type == BUS_MATCH_ROOT || where->type == BUS_MATCH_VALUE);
 557         assert(ret);
 558
 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) {
 563                         *ret = c;
 564                         return 1;
 565                 }
 566         }
 567
 568         return 0;
 569 }
 570
 571 enum bus_match_node_type bus_match_node_type_from_string(const char *k, size_t n) {
 572         assert(k);
 573
 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;
 588
 589         if (n == 4 && startswith(k, "arg")) {
 590                 int j;
 591
 592                 j = undecchar(k[3]);
 593                 if (j < 0)
 594                         return -EINVAL;
 595
 596                 return BUS_MATCH_ARG + j;
 597         }
 598
 599         if (n == 5 && startswith(k, "arg")) {
 600                 int a, b;
 601                 enum bus_match_node_type t;
 602
 603                 a = undecchar(k[3]);
 604                 b = undecchar(k[4]);
 605                 if (a <= 0 || b < 0)
 606                         return -EINVAL;
 607
 608                 t = BUS_MATCH_ARG + a * 10 + b;
 609                 if (t > BUS_MATCH_ARG_LAST)
 610                         return -EINVAL;
 611
 612                 return t;
 613         }
 614
 615         if (n == 8 && startswith(k, "arg") && startswith(k + 4, "path")) {
 616                 int j;
 617
 618                 j = undecchar(k[3]);
 619                 if (j < 0)
 620                         return -EINVAL;
 621
 622                 return BUS_MATCH_ARG_PATH + j;
 623         }
 624
 625         if (n == 9 && startswith(k, "arg") && startswith(k + 5, "path")) {
 626                 enum bus_match_node_type t;
 627                 int a, b;
 628
 629                 a = undecchar(k[3]);
 630                 b = undecchar(k[4]);
 631                 if (a <= 0 || b < 0)
 632                         return -EINVAL;
 633
 634                 t = BUS_MATCH_ARG_PATH + a * 10 + b;
 635                 if (t > BUS_MATCH_ARG_PATH_LAST)
 636                         return -EINVAL;
 637
 638                 return t;
 639         }
 640
 641         if (n == 13 && startswith(k, "arg") && startswith(k + 4, "namespace")) {
 642                 int j;
 643
 644                 j = undecchar(k[3]);
 645                 if (j < 0)
 646                         return -EINVAL;
 647
 648                 return BUS_MATCH_ARG_NAMESPACE + j;
 649         }
 650
 651         if (n == 14 && startswith(k, "arg") && startswith(k + 5, "namespace")) {
 652                 enum bus_match_node_type t;
 653                 int a, b;
 654
 655                 a = undecchar(k[3]);
 656                 b = undecchar(k[4]);
 657                 if (a <= 0 || b < 0)
 658                         return -EINVAL;
 659
 660                 t = BUS_MATCH_ARG_NAMESPACE + a * 10 + b;
 661                 if (t > BUS_MATCH_ARG_NAMESPACE_LAST)
 662                         return -EINVAL;
 663
 664                 return t;
 665         }
 666
 667         return -EINVAL;
 668 }
 669
 670 static int match_component_compare(const void *a, const void *b) {
 671         const struct bus_match_component *x = a, *y = b;
 672
 673         if (x->type < y->type)
 674                 return -1;
 675         if (x->type > y->type)
 676                 return 1;
 677
 678         return 0;
 679 }
 680
 681 void bus_match_parse_free(struct bus_match_component *components, unsigned n_components) {
 682         unsigned i;
 683
 684         for (i = 0; i < n_components; i++)
 685                 free(components[i].value_str);
 686
 687         free(components);
 688 }
 689
 690 int bus_match_parse(
 691                 const char *match,
 692                 struct bus_match_component **_components,
 693                 unsigned *_n_components) {
 694
 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;
 700         int r;
 701
 702         assert(match);
 703         assert(_components);
 704         assert(_n_components);
 705
 706         while (*p != 0) {
 707                 const char *eq, *q;
 708                 enum bus_match_node_type t;
 709                 unsigned j = 0;
 710                 size_t value_allocated = 0;
 711                 bool escaped = false;
 712                 uint8_t u;
 713
 714                 eq = strchr(p, '=');
 715                 if (!eq)
 716                         return -EINVAL;
 717
 718                 if (eq[1] != '\'')
 719                         return -EINVAL;
 720
 721                 t = bus_match_node_type_from_string(p, eq - p);
 722                 if (t < 0)
 723                         return -EINVAL;
 724
 725                 for (q = eq + 2;; q++) {
 726
 727                         if (*q == 0) {
 728                                 r = -EINVAL;
 729                                 goto fail;
 730                         }
 731
 732                         if (!escaped) {
 733                                 if (*q == '\\') {
 734                                         escaped = true;
 735                                         continue;
 736                                 }
 737                                 if (*q == '\'') {
 738                                         if (value)
 739                                                 value[j] = 0;
 740                                         break;
 741                                 }
 742                         }
 743
 744                         if (!GREEDY_REALLOC(value, value_allocated, j + 2)) {
 745                                 r = -ENOMEM;
 746                                 goto fail;
 747                         }
 748
 749                         value[j++] = *q;
 750                         escaped = false;
 751                 }
 752
 753                 if (t == BUS_MATCH_MESSAGE_TYPE) {
 754                         r = bus_message_type_from_string(value, &u);
 755                         if (r < 0)
 756                                 goto fail;
 757
 758                         free(value);
 759                         value = NULL;
 760                 } else
 761                         u = 0;
 762
 763                 if (!GREEDY_REALLOC(components, components_allocated, n_components + 1)) {
 764                         r = -ENOMEM;
 765                         goto fail;
 766                 }
 767
 768                 components[n_components].type = t;
 769                 components[n_components].value_str = value;
 770                 components[n_components].value_u8 = u;
 771                 n_components++;
 772
 773                 value = NULL;
 774
 775                 if (q[1] == 0)
 776                         break;
 777
 778                 if (q[1] != ',') {
 779                         r = -EINVAL;
 780                         goto fail;
 781                 }
 782
 783                 p = q + 2;
 784         }
 785
 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);
 788
 789         /* Check for duplicates */
 790         for (i = 0; i+1 < n_components; i++)
 791                 if (components[i].type == components[i+1].type) {
 792                         r = -EINVAL;
 793                         goto fail;
 794                 }
 795
 796         *_components = components;
 797         *_n_components = n_components;
 798
 799         return 0;
 800
 801 fail:
 802         bus_match_parse_free(components, n_components);
 803         return r;
 804 }
 805
 806 int bus_match_add(
 807                 struct bus_match_node *root,
 808                 struct bus_match_component *components,
 809                 unsigned n_components,
 810                 sd_bus_message_handler_t callback,
 811                 void *userdata,
 812                 uint64_t cookie,
 813                 struct bus_match_node **ret) {
 814
 815         unsigned i;
 816         struct bus_match_node *n;
 817         int r;
 818
 819         assert(root);
 820
 821         n = root;
 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);
 826                 if (r < 0)
 827                         return r;
 828         }
 829
 830         r = bus_match_add_leaf(n, callback, userdata, cookie, &n);
 831         if (r < 0)
 832                 return r;
 833
 834         if (ret)
 835                 *ret = n;
 836
 837         return 0;
 838 }
 839
 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,
 845                 void *userdata,
 846                 uint64_t *cookie) {
 847
 848         unsigned i;
 849         struct bus_match_node *n, **gc;
 850         int r;
 851
 852         assert(root);
 853
 854         gc = newa(struct bus_match_node*, n_components);
 855
 856         n = root;
 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,
 861                                 &n);
 862                 if (r <= 0)
 863                         return r;
 864
 865                 gc[i] = n;
 866         }
 867
 868         r = bus_match_find_leaf(n, callback, userdata, &n);
 869         if (r <= 0)
 870                 return r;
 871
 872         if (cookie)
 873                 *cookie = n->leaf.cookie;
 874
 875         /* Free the leaf */
 876         bus_match_node_free(n);
 877
 878         /* Prune the tree above */
 879         for (i = n_components; i > 0; i --) {
 880                 struct bus_match_node *p = gc[i-1]->parent;
 881
 882                 if (!bus_match_node_maybe_free(gc[i-1]))
 883                         break;
 884
 885                 if (!bus_match_node_maybe_free(p))
 886                         break;
 887         }
 888
 889         return r;
 890 }
 891
 892 void bus_match_free(struct bus_match_node *node) {
 893         struct bus_match_node *c;
 894
 895         if (!node)
 896                 return;
 897
 898         if (BUS_MATCH_CAN_HASH(node->type)) {
 899                 Iterator i;
 900
 901                 HASHMAP_FOREACH(c, node->compare.children, i)
 902                         bus_match_free(c);
 903
 904                 assert(hashmap_isempty(node->compare.children));
 905         }
 906
 907         while ((c = node->child))
 908                 bus_match_free(c);
 909
 910         if (node->type != BUS_MATCH_ROOT)
 911                 bus_match_node_free(node);
 912 }
 913
 914 const char* bus_match_node_type_to_string(enum bus_match_node_type t, char buf[], size_t l) {
 915         switch (t) {
 916
 917         case BUS_MATCH_ROOT:
 918                 return "root";
 919
 920         case BUS_MATCH_VALUE:
 921                 return "value";
 922
 923         case BUS_MATCH_LEAF:
 924                 return "leaf";
 925
 926         case BUS_MATCH_MESSAGE_TYPE:
 927                 return "type";
 928
 929         case BUS_MATCH_SENDER:
 930                 return "sender";
 931
 932         case BUS_MATCH_DESTINATION:
 933                 return "destination";
 934
 935         case BUS_MATCH_INTERFACE:
 936                 return "interface";
 937
 938         case BUS_MATCH_MEMBER:
 939                 return "member";
 940
 941         case BUS_MATCH_PATH:
 942                 return "path";
 943
 944         case BUS_MATCH_PATH_NAMESPACE:
 945                 return "path_namespace";
 946
 947         case BUS_MATCH_ARG ... BUS_MATCH_ARG_LAST:
 948                 snprintf(buf, l, "arg%i", t - BUS_MATCH_ARG);
 949                 return buf;
 950
 951         case BUS_MATCH_ARG_PATH ... BUS_MATCH_ARG_PATH_LAST:
 952                 snprintf(buf, l, "arg%ipath", t - BUS_MATCH_ARG_PATH);
 953                 return buf;
 954
 955         case BUS_MATCH_ARG_NAMESPACE ... BUS_MATCH_ARG_NAMESPACE_LAST:
 956                 snprintf(buf, l, "arg%inamespace", t - BUS_MATCH_ARG_NAMESPACE);
 957                 return buf;
 958
 959         default:
 960                 return NULL;
 961         }
 962 }
 963
 964 void bus_match_dump(struct bus_match_node *node, unsigned level) {
 965         struct bus_match_node *c;
 966         _cleanup_free_ char *pfx = NULL;
 967         char buf[32];
 968
 969         if (!node)
 970                 return;
 971
 972         pfx = strrep("  ", level);
 973         printf("%s[%s]", strempty(pfx), bus_match_node_type_to_string(node->type, buf, sizeof(buf)));
 974
 975         if (node->type == BUS_MATCH_VALUE) {
 976                 if (node->parent->type == BUS_MATCH_MESSAGE_TYPE)
 977                         printf(" <%u>\n", node->value.u8);
 978                 else
 979                         printf(" <%s>\n", node->value.str);
 980         } else if (node->type == BUS_MATCH_ROOT)
 981                 puts(" root");
 982         else if (node->type == BUS_MATCH_LEAF)
 983                 printf(" %p/%p\n", node->leaf.callback, node->leaf.userdata);
 984         else
 985                 putchar('\n');
 986
 987         if (BUS_MATCH_CAN_HASH(node->type)) {
 988                 Iterator i;
 989
 990                 HASHMAP_FOREACH(c, node->compare.children, i)
 991                         bus_match_dump(c, level + 1);
 992         }
 993
 994         for (c = node->child; c; c = c->next)
 995                 bus_match_dump(c, level + 1);
 996 }