src/libsystemd/sd-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 #include "bus-error.h"
  26 #include "bus-util.h"
  27 #include "strv.h"
  28
  29 /* Example:
  30  *
  31  *  A: type=signal,sender=foo,interface=bar
  32  *  B: type=signal,sender=quux,interface=fips
  33  *  C: type=signal,sender=quux,interface=waldo
  34  *  D: type=signal,member=test
  35  *  E: sender=miau
  36  *  F: type=signal
  37  *  G: type=signal
  38  *
  39  *  results in this tree:
  40  *
  41  *  BUS_MATCH_ROOT
  42  *  + BUS_MATCH_MESSAGE_TYPE
  43  *  | ` BUS_MATCH_VALUE: value == signal
  44  *  |   + DBUS_MATCH_SENDER
  45  *  |   | + BUS_MATCH_VALUE: value == foo
  46  *  |   | | ` DBUS_MATCH_INTERFACE
  47  *  |   | |   ` BUS_MATCH_VALUE: value == bar
  48  *  |   | |     ` BUS_MATCH_LEAF: A
  49  *  |   | ` BUS_MATCH_VALUE: value == quux
  50  *  |   |   ` DBUS_MATCH_INTERFACE
  51  *  |   |     | BUS_MATCH_VALUE: value == fips
  52  *  |   |     | ` BUS_MATCH_LEAF: B
  53  *  |   |     ` BUS_MATCH_VALUE: value == waldo
  54  *  |   |       ` BUS_MATCH_LEAF: C
  55  *  |   + DBUS_MATCH_MEMBER
  56  *  |   | ` BUS_MATCH_VALUE: value == test
  57  *  |   |   ` BUS_MATCH_LEAF: D
  58  *  |   + BUS_MATCH_LEAF: F
  59  *  |   ` BUS_MATCH_LEAF: G
  60  *  ` BUS_MATCH_SENDER
  61  *    ` BUS_MATCH_VALUE: value == miau
  62  *      ` BUS_MATCH_LEAF: E
  63  */
  64
  65 static inline bool BUS_MATCH_IS_COMPARE(enum bus_match_node_type t) {
  66         return t >= BUS_MATCH_SENDER && t <= BUS_MATCH_ARG_NAMESPACE_LAST;
  67 }
  68
  69 static inline bool BUS_MATCH_CAN_HASH(enum bus_match_node_type t) {
  70         return (t >= BUS_MATCH_MESSAGE_TYPE && t <= BUS_MATCH_PATH) ||
  71                 (t >= BUS_MATCH_ARG && t <= BUS_MATCH_ARG_LAST);
  72 }
  73
  74 static void bus_match_node_free(struct bus_match_node *node) {
  75         assert(node);
  76         assert(node->parent);
  77         assert(!node->child);
  78         assert(node->type != BUS_MATCH_ROOT);
  79         assert(node->type < _BUS_MATCH_NODE_TYPE_MAX);
  80
  81         if (node->parent->child) {
  82                 /* We are apparently linked into the parent's child
  83                  * list. Let's remove us from there. */
  84                 if (node->prev) {
  85                         assert(node->prev->next == node);
  86                         node->prev->next = node->next;
  87                 } else {
  88                         assert(node->parent->child == node);
  89                         node->parent->child = node->next;
  90                 }
  91
  92                 if (node->next)
  93                         node->next->prev = node->prev;
  94         }
  95
  96         if (node->type == BUS_MATCH_VALUE) {
  97                 /* We might be in the parent's hash table, so clean
  98                  * this up */
  99
 100                 if (node->parent->type == BUS_MATCH_MESSAGE_TYPE)
 101                         hashmap_remove(node->parent->compare.children, UINT_TO_PTR(node->value.u8));
 102                 else if (BUS_MATCH_CAN_HASH(node->parent->type) && node->value.str)
 103                         hashmap_remove(node->parent->compare.children, node->value.str);
 104
 105                 free(node->value.str);
 106         }
 107
 108         if (BUS_MATCH_IS_COMPARE(node->type)) {
 109                 assert(hashmap_isempty(node->compare.children));
 110                 hashmap_free(node->compare.children);
 111         }
 112
 113         free(node);
 114 }
 115
 116 static bool bus_match_node_maybe_free(struct bus_match_node *node) {
 117         assert(node);
 118
 119         if (node->type == BUS_MATCH_ROOT)
 120                 return false;
 121
 122         if (node->child)
 123                 return false;
 124
 125         if (BUS_MATCH_IS_COMPARE(node->type) && !hashmap_isempty(node->compare.children))
 126                 return true;
 127
 128         bus_match_node_free(node);
 129         return true;
 130 }
 131
 132 static bool value_node_test(
 133                 struct bus_match_node *node,
 134                 enum bus_match_node_type parent_type,
 135                 uint8_t value_u8,
 136                 const char *value_str,
 137                 char **value_strv,
 138                 sd_bus_message *m) {
 139
 140         assert(node);
 141         assert(node->type == BUS_MATCH_VALUE);
 142
 143         /* Tests parameters against this value node, doing prefix
 144          * magic and stuff. */
 145
 146         switch (parent_type) {
 147
 148         case BUS_MATCH_MESSAGE_TYPE:
 149                 return node->value.u8 == value_u8;
 150
 151         case BUS_MATCH_SENDER:
 152                 if (streq_ptr(node->value.str, value_str))
 153                         return true;
 154
 155                 if (m->creds.mask & SD_BUS_CREDS_WELL_KNOWN_NAMES) {
 156                         char **i;
 157
 158                         /* on kdbus we have the well known names list
 159                          * in the credentials, let's make use of that
 160                          * for an accurate match */
 161
 162                         STRV_FOREACH(i, m->creds.well_known_names)
 163                                 if (streq_ptr(node->value.str, *i))
 164                                         return true;
 165
 166                 } else {
 167
 168                         /* If we don't have kdbus, we don't know the
 169                          * well-known names of the senders. In that,
 170                          * let's just hope that dbus-daemon doesn't
 171                          * send us stuff we didn't want. */
 172
 173                         if (node->value.str[0] != ':' && value_str && value_str[0] == ':')
 174                                 return true;
 175                 }
 176
 177                 return false;
 178
 179         case BUS_MATCH_DESTINATION:
 180         case BUS_MATCH_INTERFACE:
 181         case BUS_MATCH_MEMBER:
 182         case BUS_MATCH_PATH:
 183         case BUS_MATCH_ARG ... BUS_MATCH_ARG_LAST: {
 184                 char **i;
 185
 186                 if (value_str)
 187                         return streq_ptr(node->value.str, value_str);
 188
 189                 STRV_FOREACH(i, value_strv)
 190                         if (streq_ptr(node->value.str, *i))
 191                                 return true;
 192
 193                 return false;
 194         }
 195
 196         case BUS_MATCH_ARG_NAMESPACE ... BUS_MATCH_ARG_NAMESPACE_LAST: {
 197                 char **i;
 198
 199                 if (value_str)
 200                         return namespace_simple_pattern(node->value.str, value_str);
 201
 202                 STRV_FOREACH(i, value_strv)
 203                         if (namespace_simple_pattern(node->value.str, *i))
 204                                 return true;
 205                 return false;
 206         }
 207
 208         case BUS_MATCH_PATH_NAMESPACE:
 209                 return path_simple_pattern(node->value.str, value_str);
 210
 211         case BUS_MATCH_ARG_PATH ... BUS_MATCH_ARG_PATH_LAST: {
 212                 char **i;
 213
 214                 if (value_str)
 215                         return path_complex_pattern(node->value.str, value_str);
 216
 217                 STRV_FOREACH(i, value_strv)
 218                         if (path_complex_pattern(node->value.str, *i))
 219                                 return true;
 220
 221                 return false;
 222         }
 223
 224         default:
 225                 assert_not_reached("Invalid node type");
 226         }
 227 }
 228
 229 static bool value_node_same(
 230                 struct bus_match_node *node,
 231                 enum bus_match_node_type parent_type,
 232                 uint8_t value_u8,
 233                 const char *value_str) {
 234
 235         /* Tests parameters against this value node, not doing prefix
 236          * magic and stuff, i.e. this one actually compares the match
 237          * itself.*/
 238
 239         assert(node);
 240         assert(node->type == BUS_MATCH_VALUE);
 241
 242         switch (parent_type) {
 243
 244         case BUS_MATCH_MESSAGE_TYPE:
 245                 return node->value.u8 == value_u8;
 246
 247         case BUS_MATCH_SENDER:
 248         case BUS_MATCH_DESTINATION:
 249         case BUS_MATCH_INTERFACE:
 250         case BUS_MATCH_MEMBER:
 251         case BUS_MATCH_PATH:
 252         case BUS_MATCH_ARG ... BUS_MATCH_ARG_LAST:
 253         case BUS_MATCH_ARG_NAMESPACE ... BUS_MATCH_ARG_NAMESPACE_LAST:
 254         case BUS_MATCH_PATH_NAMESPACE:
 255         case BUS_MATCH_ARG_PATH ... BUS_MATCH_ARG_PATH_LAST:
 256                 return streq(node->value.str, value_str);
 257
 258         default:
 259                 assert_not_reached("Invalid node type");
 260         }
 261 }
 262
 263 int bus_match_run(
 264                 sd_bus *bus,
 265                 struct bus_match_node *node,
 266                 sd_bus_message *m) {
 267
 268         _cleanup_strv_free_ char **test_strv = NULL;
 269         const char *test_str = NULL;
 270         uint8_t test_u8 = 0;
 271         int r;
 272
 273         assert(m);
 274
 275         if (!node)
 276                 return 0;
 277
 278         if (bus && bus->match_callbacks_modified)
 279                 return 0;
 280
 281         /* Not these special semantics: when traversing the tree we
 282          * usually let bus_match_run() when called for a node
 283          * recursively invoke bus_match_run(). There's are two
 284          * exceptions here though, which are BUS_NODE_ROOT (which
 285          * cannot have a sibling), and BUS_NODE_VALUE (whose siblings
 286          * are invoked anyway by its parent. */
 287
 288         switch (node->type) {
 289
 290         case BUS_MATCH_ROOT:
 291
 292                 /* Run all children. Since we cannot have any siblings
 293                  * we won't call any. The children of the root node
 294                  * are compares or leaves, they will automatically
 295                  * call their siblings. */
 296                 return bus_match_run(bus, node->child, m);
 297
 298         case BUS_MATCH_VALUE:
 299
 300                 /* Run all children. We don't execute any siblings, we
 301                  * assume our caller does that. The children of value
 302                  * nodes are compares or leaves, they will
 303                  * automatically call their siblings */
 304
 305                 assert(node->child);
 306                 return bus_match_run(bus, node->child, m);
 307
 308         case BUS_MATCH_LEAF:
 309
 310                 if (bus) {
 311                         if (node->leaf.callback->last_iteration == bus->iteration_counter)
 312                                 return 0;
 313
 314                         node->leaf.callback->last_iteration = bus->iteration_counter;
 315                 }
 316
 317                 r = sd_bus_message_rewind(m, true);
 318                 if (r < 0)
 319                         return r;
 320
 321                 /* Run the callback. And then invoke siblings. */
 322                 if (node->leaf.callback->callback) {
 323                         _cleanup_bus_error_free_ sd_bus_error error_buffer = SD_BUS_ERROR_NULL;
 324                         sd_bus_slot *slot;
 325
 326                         slot = container_of(node->leaf.callback, sd_bus_slot, match_callback);
 327                         if (bus) {
 328                                 bus->current_slot = sd_bus_slot_ref(slot);
 329                                 bus->current_handler = node->leaf.callback->callback;
 330                                 bus->current_userdata = slot->userdata;
 331                         }
 332                         r = node->leaf.callback->callback(bus, m, slot->userdata, &error_buffer);
 333                         if (bus) {
 334                                 bus->current_userdata = NULL;
 335                                 bus->current_handler = NULL;
 336                                 bus->current_slot = sd_bus_slot_unref(slot);
 337                         }
 338
 339                         r = bus_maybe_reply_error(m, r, &error_buffer);
 340                         if (r != 0)
 341                                 return r;
 342
 343                         if (bus && bus->match_callbacks_modified)
 344                                 return 0;
 345                 }
 346
 347                 return bus_match_run(bus, node->next, m);
 348
 349         case BUS_MATCH_MESSAGE_TYPE:
 350                 test_u8 = m->header->type;
 351                 break;
 352
 353         case BUS_MATCH_SENDER:
 354                 test_str = m->sender;
 355                 /* FIXME: resolve test_str from a well-known to a unique name first */
 356                 break;
 357
 358         case BUS_MATCH_DESTINATION:
 359                 test_str = m->destination;
 360                 break;
 361
 362         case BUS_MATCH_INTERFACE:
 363                 test_str = m->interface;
 364                 break;
 365
 366         case BUS_MATCH_MEMBER:
 367                 test_str = m->member;
 368                 break;
 369
 370         case BUS_MATCH_PATH:
 371         case BUS_MATCH_PATH_NAMESPACE:
 372                 test_str = m->path;
 373                 break;
 374
 375         case BUS_MATCH_ARG ... BUS_MATCH_ARG_LAST:
 376                 (void) bus_message_get_arg(m, node->type - BUS_MATCH_ARG, &test_str, &test_strv);
 377                 break;
 378
 379         case BUS_MATCH_ARG_PATH ... BUS_MATCH_ARG_PATH_LAST:
 380                 (void) bus_message_get_arg(m, node->type - BUS_MATCH_ARG_PATH, &test_str, &test_strv);
 381                 break;
 382
 383         case BUS_MATCH_ARG_NAMESPACE ... BUS_MATCH_ARG_NAMESPACE_LAST:
 384                 (void) bus_message_get_arg(m, node->type - BUS_MATCH_ARG_NAMESPACE, &test_str, &test_strv);
 385                 break;
 386
 387         default:
 388                 assert_not_reached("Unknown match type.");
 389         }
 390
 391         if (BUS_MATCH_CAN_HASH(node->type)) {
 392                 struct bus_match_node *found;
 393
 394                 /* Lookup via hash table, nice! So let's jump directly. */
 395
 396                 if (test_str)
 397                         found = hashmap_get(node->compare.children, test_str);
 398                 else if (test_strv) {
 399                         char **i;
 400
 401                         STRV_FOREACH(i, test_strv) {
 402                                 found = hashmap_get(node->compare.children, *i);
 403                                 if (found) {
 404                                         r = bus_match_run(bus, found, m);
 405                                         if (r != 0)
 406                                                 return r;
 407                                 }
 408                         }
 409
 410                         found = NULL;
 411                 } else if (node->type == BUS_MATCH_MESSAGE_TYPE)
 412                         found = hashmap_get(node->compare.children, UINT_TO_PTR(test_u8));
 413                 else
 414                         found = NULL;
 415
 416                 if (found) {
 417                         r = bus_match_run(bus, found, m);
 418                         if (r != 0)
 419                                 return r;
 420                 }
 421         } else {
 422                 struct bus_match_node *c;
 423
 424                 /* No hash table, so let's iterate manually... */
 425
 426                 for (c = node->child; c; c = c->next) {
 427                         if (!value_node_test(c, node->type, test_u8, test_str, test_strv, m))
 428                                 continue;
 429
 430                         r = bus_match_run(bus, c, m);
 431                         if (r != 0)
 432                                 return r;
 433                 }
 434         }
 435
 436         if (bus && bus->match_callbacks_modified)
 437                 return 0;
 438
 439         /* And now, let's invoke our siblings */
 440         return bus_match_run(bus, node->next, m);
 441 }
 442
 443 static int bus_match_add_compare_value(
 444                 struct bus_match_node *where,
 445                 enum bus_match_node_type t,
 446                 uint8_t value_u8,
 447                 const char *value_str,
 448                 struct bus_match_node **ret) {
 449
 450         struct bus_match_node *c = NULL, *n = NULL;
 451         int r;
 452
 453         assert(where);
 454         assert(where->type == BUS_MATCH_ROOT || where->type == BUS_MATCH_VALUE);
 455         assert(BUS_MATCH_IS_COMPARE(t));
 456         assert(ret);
 457
 458         for (c = where->child; c && c->type != t; c = c->next)
 459                 ;
 460
 461         if (c) {
 462                 /* Comparison node already exists? Then let's see if
 463                  * the value node exists too. */
 464
 465                 if (t == BUS_MATCH_MESSAGE_TYPE)
 466                         n = hashmap_get(c->compare.children, UINT_TO_PTR(value_u8));
 467                 else if (BUS_MATCH_CAN_HASH(t))
 468                         n = hashmap_get(c->compare.children, value_str);
 469                 else {
 470                         for (n = c->child; n && !value_node_same(n, t, value_u8, value_str); n = n->next)
 471                                 ;
 472                 }
 473
 474                 if (n) {
 475                         *ret = n;
 476                         return 0;
 477                 }
 478         } else {
 479                 /* Comparison node, doesn't exist yet? Then let's
 480                  * create it. */
 481
 482                 c = new0(struct bus_match_node, 1);
 483                 if (!c) {
 484                         r = -ENOMEM;
 485                         goto fail;
 486                 }
 487
 488                 c->type = t;
 489                 c->parent = where;
 490                 c->next = where->child;
 491                 if (c->next)
 492                         c->next->prev = c;
 493                 where->child = c;
 494
 495                 if (t == BUS_MATCH_MESSAGE_TYPE) {
 496                         c->compare.children = hashmap_new(NULL);
 497                         if (!c->compare.children) {
 498                                 r = -ENOMEM;
 499                                 goto fail;
 500                         }
 501                 } else if (BUS_MATCH_CAN_HASH(t)) {
 502                         c->compare.children = hashmap_new(&string_hash_ops);
 503                         if (!c->compare.children) {
 504                                 r = -ENOMEM;
 505                                 goto fail;
 506                         }
 507                 }
 508         }
 509
 510         n = new0(struct bus_match_node, 1);
 511         if (!n) {
 512                 r = -ENOMEM;
 513                 goto fail;
 514         }
 515
 516         n->type = BUS_MATCH_VALUE;
 517         n->value.u8 = value_u8;
 518         if (value_str) {
 519                 n->value.str = strdup(value_str);
 520                 if (!n->value.str) {
 521                         r = -ENOMEM;
 522                         goto fail;
 523                 }
 524         }
 525
 526         n->parent = c;
 527         if (c->compare.children) {
 528
 529                 if (t == BUS_MATCH_MESSAGE_TYPE)
 530                         r = hashmap_put(c->compare.children, UINT_TO_PTR(value_u8), n);
 531                 else
 532                         r = hashmap_put(c->compare.children, n->value.str, n);
 533
 534                 if (r < 0)
 535                         goto fail;
 536         } else {
 537                 n->next = c->child;
 538                 if (n->next)
 539                         n->next->prev = n;
 540                 c->child = n;
 541         }
 542
 543         *ret = n;
 544         return 1;
 545
 546 fail:
 547         if (c)
 548                 bus_match_node_maybe_free(c);
 549
 550         if (n) {
 551                 free(n->value.str);
 552                 free(n);
 553         }
 554
 555         return r;
 556 }
 557
 558 static int bus_match_find_compare_value(
 559                 struct bus_match_node *where,
 560                 enum bus_match_node_type t,
 561                 uint8_t value_u8,
 562                 const char *value_str,
 563                 struct bus_match_node **ret) {
 564
 565         struct bus_match_node *c, *n;
 566
 567         assert(where);
 568         assert(where->type == BUS_MATCH_ROOT || where->type == BUS_MATCH_VALUE);
 569         assert(BUS_MATCH_IS_COMPARE(t));
 570         assert(ret);
 571
 572         for (c = where->child; c && c->type != t; c = c->next)
 573                 ;
 574
 575         if (!c)
 576                 return 0;
 577
 578         if (t == BUS_MATCH_MESSAGE_TYPE)
 579                 n = hashmap_get(c->compare.children, UINT_TO_PTR(value_u8));
 580         else if (BUS_MATCH_CAN_HASH(t))
 581                 n = hashmap_get(c->compare.children, value_str);
 582         else {
 583                 for (n = c->child; n && !value_node_same(n, t, value_u8, value_str); n = n->next)
 584                         ;
 585         }
 586
 587         if (n) {
 588                 *ret = n;
 589                 return 1;
 590         }
 591
 592         return 0;
 593 }
 594
 595 static int bus_match_add_leaf(
 596                 struct bus_match_node *where,
 597                 struct match_callback *callback) {
 598
 599         struct bus_match_node *n;
 600
 601         assert(where);
 602         assert(where->type == BUS_MATCH_ROOT || where->type == BUS_MATCH_VALUE);
 603         assert(callback);
 604
 605         n = new0(struct bus_match_node, 1);
 606         if (!n)
 607                 return -ENOMEM;
 608
 609         n->type = BUS_MATCH_LEAF;
 610         n->parent = where;
 611         n->next = where->child;
 612         if (n->next)
 613                 n->next->prev = n;
 614
 615         n->leaf.callback = callback;
 616         callback->match_node = n;
 617
 618         where->child = n;
 619
 620         return 1;
 621 }
 622
 623 static int bus_match_find_leaf(
 624                 struct bus_match_node *where,
 625                 sd_bus_message_handler_t callback,
 626                 void *userdata,
 627                 struct bus_match_node **ret) {
 628
 629         struct bus_match_node *c;
 630
 631         assert(where);
 632         assert(where->type == BUS_MATCH_ROOT || where->type == BUS_MATCH_VALUE);
 633         assert(ret);
 634
 635         for (c = where->child; c; c = c->next) {
 636                 sd_bus_slot *s;
 637
 638                 s = container_of(c->leaf.callback, sd_bus_slot, match_callback);
 639
 640                 if (c->type == BUS_MATCH_LEAF &&
 641                     c->leaf.callback->callback == callback &&
 642                     s->userdata == userdata) {
 643                         *ret = c;
 644                         return 1;
 645                 }
 646         }
 647
 648         return 0;
 649 }
 650
 651 enum bus_match_node_type bus_match_node_type_from_string(const char *k, size_t n) {
 652         assert(k);
 653
 654         if (n == 4 && startswith(k, "type"))
 655                 return BUS_MATCH_MESSAGE_TYPE;
 656         if (n == 6 && startswith(k, "sender"))
 657                 return BUS_MATCH_SENDER;
 658         if (n == 11 && startswith(k, "destination"))
 659                 return BUS_MATCH_DESTINATION;
 660         if (n == 9 && startswith(k, "interface"))
 661                 return BUS_MATCH_INTERFACE;
 662         if (n == 6 && startswith(k, "member"))
 663                 return BUS_MATCH_MEMBER;
 664         if (n == 4 && startswith(k, "path"))
 665                 return BUS_MATCH_PATH;
 666         if (n == 14 && startswith(k, "path_namespace"))
 667                 return BUS_MATCH_PATH_NAMESPACE;
 668
 669         if (n == 4 && startswith(k, "arg")) {
 670                 int j;
 671
 672                 j = undecchar(k[3]);
 673                 if (j < 0)
 674                         return -EINVAL;
 675
 676                 return BUS_MATCH_ARG + j;
 677         }
 678
 679         if (n == 5 && startswith(k, "arg")) {
 680                 int a, b;
 681                 enum bus_match_node_type t;
 682
 683                 a = undecchar(k[3]);
 684                 b = undecchar(k[4]);
 685                 if (a <= 0 || b < 0)
 686                         return -EINVAL;
 687
 688                 t = BUS_MATCH_ARG + a * 10 + b;
 689                 if (t > BUS_MATCH_ARG_LAST)
 690                         return -EINVAL;
 691
 692                 return t;
 693         }
 694
 695         if (n == 8 && startswith(k, "arg") && startswith(k + 4, "path")) {
 696                 int j;
 697
 698                 j = undecchar(k[3]);
 699                 if (j < 0)
 700                         return -EINVAL;
 701
 702                 return BUS_MATCH_ARG_PATH + j;
 703         }
 704
 705         if (n == 9 && startswith(k, "arg") && startswith(k + 5, "path")) {
 706                 enum bus_match_node_type t;
 707                 int a, b;
 708
 709                 a = undecchar(k[3]);
 710                 b = undecchar(k[4]);
 711                 if (a <= 0 || b < 0)
 712                         return -EINVAL;
 713
 714                 t = BUS_MATCH_ARG_PATH + a * 10 + b;
 715                 if (t > BUS_MATCH_ARG_PATH_LAST)
 716                         return -EINVAL;
 717
 718                 return t;
 719         }
 720
 721         if (n == 13 && startswith(k, "arg") && startswith(k + 4, "namespace")) {
 722                 int j;
 723
 724                 j = undecchar(k[3]);
 725                 if (j < 0)
 726                         return -EINVAL;
 727
 728                 return BUS_MATCH_ARG_NAMESPACE + j;
 729         }
 730
 731         if (n == 14 && startswith(k, "arg") && startswith(k + 5, "namespace")) {
 732                 enum bus_match_node_type t;
 733                 int a, b;
 734
 735                 a = undecchar(k[3]);
 736                 b = undecchar(k[4]);
 737                 if (a <= 0 || b < 0)
 738                         return -EINVAL;
 739
 740                 t = BUS_MATCH_ARG_NAMESPACE + a * 10 + b;
 741                 if (t > BUS_MATCH_ARG_NAMESPACE_LAST)
 742                         return -EINVAL;
 743
 744                 return t;
 745         }
 746
 747         return -EINVAL;
 748 }
 749
 750 static int match_component_compare(const void *a, const void *b) {
 751         const struct bus_match_component *x = a, *y = b;
 752
 753         if (x->type < y->type)
 754                 return -1;
 755         if (x->type > y->type)
 756                 return 1;
 757
 758         return 0;
 759 }
 760
 761 void bus_match_parse_free(struct bus_match_component *components, unsigned n_components) {
 762         unsigned i;
 763
 764         for (i = 0; i < n_components; i++)
 765                 free(components[i].value_str);
 766
 767         free(components);
 768 }
 769
 770 int bus_match_parse(
 771                 const char *match,
 772                 struct bus_match_component **_components,
 773                 unsigned *_n_components) {
 774
 775         const char *p = match;
 776         struct bus_match_component *components = NULL;
 777         size_t components_allocated = 0;
 778         unsigned n_components = 0, i;
 779         _cleanup_free_ char *value = NULL;
 780         int r;
 781
 782         assert(match);
 783         assert(_components);
 784         assert(_n_components);
 785
 786         while (*p != 0) {
 787                 const char *eq, *q;
 788                 enum bus_match_node_type t;
 789                 unsigned j = 0;
 790                 size_t value_allocated = 0;
 791                 bool escaped = false, quoted;
 792                 uint8_t u;
 793
 794                 /* Avahi's match rules appear to include whitespace, skip over it */
 795                 p += strspn(p, " ");
 796
 797                 eq = strchr(p, '=');
 798                 if (!eq)
 799                         return -EINVAL;
 800
 801                 t = bus_match_node_type_from_string(p, eq - p);
 802                 if (t < 0)
 803                         return -EINVAL;
 804
 805                 quoted = eq[1] == '\'';
 806
 807                 for (q = eq + 1 + quoted;; q++) {
 808
 809                         if (*q == 0) {
 810
 811                                 if (quoted) {
 812                                         r = -EINVAL;
 813                                         goto fail;
 814                                 } else {
 815                                         if (value)
 816                                                 value[j] = 0;
 817                                         break;
 818                                 }
 819                         }
 820
 821                         if (!escaped) {
 822                                 if (*q == '\\') {
 823                                         escaped = true;
 824                                         continue;
 825                                 }
 826
 827                                 if (quoted) {
 828                                         if (*q == '\'') {
 829                                                 if (value)
 830                                                         value[j] = 0;
 831                                                 break;
 832                                         }
 833                                 } else {
 834                                         if (*q == ',') {
 835                                                 if (value)
 836                                                         value[j] = 0;
 837
 838                                                 break;
 839                                         }
 840                                 }
 841                         }
 842
 843                         if (!GREEDY_REALLOC(value, value_allocated, j + 2)) {
 844                                 r = -ENOMEM;
 845                                 goto fail;
 846                         }
 847
 848                         value[j++] = *q;
 849                         escaped = false;
 850                 }
 851
 852                 if (!value) {
 853                         value = strdup("");
 854                         if (!value) {
 855                                 r = -ENOMEM;
 856                                 goto fail;
 857                         }
 858                 }
 859
 860                 if (t == BUS_MATCH_MESSAGE_TYPE) {
 861                         r = bus_message_type_from_string(value, &u);
 862                         if (r < 0)
 863                                 goto fail;
 864
 865                         free(value);
 866                         value = NULL;
 867                 } else
 868                         u = 0;
 869
 870                 if (!GREEDY_REALLOC(components, components_allocated, n_components + 1)) {
 871                         r = -ENOMEM;
 872                         goto fail;
 873                 }
 874
 875                 components[n_components].type = t;
 876                 components[n_components].value_str = value;
 877                 components[n_components].value_u8 = u;
 878                 n_components++;
 879
 880                 value = NULL;
 881
 882                 if (q[quoted] == 0)
 883                         break;
 884
 885                 if (q[quoted] != ',') {
 886                         r = -EINVAL;
 887                         goto fail;
 888                 }
 889
 890                 p = q + 1 + quoted;
 891         }
 892
 893         /* Order the whole thing, so that we always generate the same tree */
 894         qsort_safe(components, n_components, sizeof(struct bus_match_component), match_component_compare);
 895
 896         /* Check for duplicates */
 897         for (i = 0; i+1 < n_components; i++)
 898                 if (components[i].type == components[i+1].type) {
 899                         r = -EINVAL;
 900                         goto fail;
 901                 }
 902
 903         *_components = components;
 904         *_n_components = n_components;
 905
 906         return 0;
 907
 908 fail:
 909         bus_match_parse_free(components, n_components);
 910         return r;
 911 }
 912
 913 char *bus_match_to_string(struct bus_match_component *components, unsigned n_components) {
 914         _cleanup_free_ FILE *f = NULL;
 915         char *buffer = NULL;
 916         size_t size = 0;
 917         unsigned i;
 918
 919         if (n_components <= 0)
 920                 return strdup("");
 921
 922         assert(components);
 923
 924         f = open_memstream(&buffer, &size);
 925         if (!f)
 926                 return NULL;
 927
 928         for (i = 0; i < n_components; i++) {
 929                 char buf[32];
 930
 931                 if (i != 0)
 932                         fputc(',', f);
 933
 934                 fputs(bus_match_node_type_to_string(components[i].type, buf, sizeof(buf)), f);
 935                 fputc('=', f);
 936                 fputc('\'', f);
 937
 938                 if (components[i].type == BUS_MATCH_MESSAGE_TYPE)
 939                         fputs(bus_message_type_to_string(components[i].value_u8), f);
 940                 else
 941                         fputs(components[i].value_str, f);
 942
 943                 fputc('\'', f);
 944         }
 945
 946         fflush(f);
 947         if (ferror(f))
 948                 return NULL;
 949
 950         return buffer;
 951 }
 952
 953 int bus_match_add(
 954                 struct bus_match_node *root,
 955                 struct bus_match_component *components,
 956                 unsigned n_components,
 957                 struct match_callback *callback) {
 958
 959         unsigned i;
 960         struct bus_match_node *n;
 961         int r;
 962
 963         assert(root);
 964         assert(callback);
 965
 966         n = root;
 967         for (i = 0; i < n_components; i++) {
 968                 r = bus_match_add_compare_value(
 969                                 n, components[i].type,
 970                                 components[i].value_u8, components[i].value_str, &n);
 971                 if (r < 0)
 972                         return r;
 973         }
 974
 975         return bus_match_add_leaf(n, callback);
 976 }
 977
 978 int bus_match_remove(
 979                 struct bus_match_node *root,
 980                 struct match_callback *callback) {
 981
 982         struct bus_match_node *node, *pp;
 983
 984         assert(root);
 985         assert(callback);
 986
 987         node = callback->match_node;
 988         if (!node)
 989                 return 0;
 990
 991         assert(node->type == BUS_MATCH_LEAF);
 992
 993         callback->match_node = NULL;
 994
 995         /* Free the leaf */
 996         pp = node->parent;
 997         bus_match_node_free(node);
 998
 999         /* Prune the tree above */
1000         while (pp) {
1001                 node = pp;
1002                 pp = node->parent;
1003
1004                 if (!bus_match_node_maybe_free(node))
1005                         break;
1006         }
1007
1008         return 1;
1009 }
1010
1011 int bus_match_find(
1012                 struct bus_match_node *root,
1013                 struct bus_match_component *components,
1014                 unsigned n_components,
1015                 sd_bus_message_handler_t callback,
1016                 void *userdata,
1017                 struct match_callback **ret) {
1018
1019         struct bus_match_node *n, **gc;
1020         unsigned i;
1021         int r;
1022
1023         assert(root);
1024         assert(ret);
1025
1026         gc = newa(struct bus_match_node*, n_components);
1027
1028         n = root;
1029         for (i = 0; i < n_components; i++) {
1030                 r = bus_match_find_compare_value(
1031                                 n, components[i].type,
1032                                 components[i].value_u8, components[i].value_str,
1033                                 &n);
1034                 if (r <= 0)
1035                         return r;
1036
1037                 gc[i] = n;
1038         }
1039
1040         r = bus_match_find_leaf(n, callback, userdata, &n);
1041         if (r <= 0)
1042                 return r;
1043
1044         *ret = n->leaf.callback;
1045         return 1;
1046 }
1047
1048 void bus_match_free(struct bus_match_node *node) {
1049         struct bus_match_node *c;
1050
1051         if (!node)
1052                 return;
1053
1054         if (BUS_MATCH_CAN_HASH(node->type)) {
1055                 Iterator i;
1056
1057                 HASHMAP_FOREACH(c, node->compare.children, i)
1058                         bus_match_free(c);
1059
1060                 assert(hashmap_isempty(node->compare.children));
1061         }
1062
1063         while ((c = node->child))
1064                 bus_match_free(c);
1065
1066         if (node->type != BUS_MATCH_ROOT)
1067                 bus_match_node_free(node);
1068 }
1069
1070 const char* bus_match_node_type_to_string(enum bus_match_node_type t, char buf[], size_t l) {
1071         switch (t) {
1072
1073         case BUS_MATCH_ROOT:
1074                 return "root";
1075
1076         case BUS_MATCH_VALUE:
1077                 return "value";
1078
1079         case BUS_MATCH_LEAF:
1080                 return "leaf";
1081
1082         case BUS_MATCH_MESSAGE_TYPE:
1083                 return "type";
1084
1085         case BUS_MATCH_SENDER:
1086                 return "sender";
1087
1088         case BUS_MATCH_DESTINATION:
1089                 return "destination";
1090
1091         case BUS_MATCH_INTERFACE:
1092                 return "interface";
1093
1094         case BUS_MATCH_MEMBER:
1095                 return "member";
1096
1097         case BUS_MATCH_PATH:
1098                 return "path";
1099
1100         case BUS_MATCH_PATH_NAMESPACE:
1101                 return "path_namespace";
1102
1103         case BUS_MATCH_ARG ... BUS_MATCH_ARG_LAST:
1104                 snprintf(buf, l, "arg%i", t - BUS_MATCH_ARG);
1105                 return buf;
1106
1107         case BUS_MATCH_ARG_PATH ... BUS_MATCH_ARG_PATH_LAST:
1108                 snprintf(buf, l, "arg%ipath", t - BUS_MATCH_ARG_PATH);
1109                 return buf;
1110
1111         case BUS_MATCH_ARG_NAMESPACE ... BUS_MATCH_ARG_NAMESPACE_LAST:
1112                 snprintf(buf, l, "arg%inamespace", t - BUS_MATCH_ARG_NAMESPACE);
1113                 return buf;
1114
1115         default:
1116                 return NULL;
1117         }
1118 }
1119
1120 void bus_match_dump(struct bus_match_node *node, unsigned level) {
1121         struct bus_match_node *c;
1122         _cleanup_free_ char *pfx = NULL;
1123         char buf[32];
1124
1125         if (!node)
1126                 return;
1127
1128         pfx = strrep("  ", level);
1129         printf("%s[%s]", strempty(pfx), bus_match_node_type_to_string(node->type, buf, sizeof(buf)));
1130
1131         if (node->type == BUS_MATCH_VALUE) {
1132                 if (node->parent->type == BUS_MATCH_MESSAGE_TYPE)
1133                         printf(" <%u>\n", node->value.u8);
1134                 else
1135                         printf(" <%s>\n", node->value.str);
1136         } else if (node->type == BUS_MATCH_ROOT)
1137                 puts(" root");
1138         else if (node->type == BUS_MATCH_LEAF)
1139                 printf(" %p/%p\n", node->leaf.callback->callback, container_of(node->leaf.callback, sd_bus_slot, match_callback)->userdata);
1140         else
1141                 putchar('\n');
1142
1143         if (BUS_MATCH_CAN_HASH(node->type)) {
1144                 Iterator i;
1145
1146                 HASHMAP_FOREACH(c, node->compare.children, i)
1147                         bus_match_dump(c, level + 1);
1148         }
1149
1150         for (c = node->child; c; c = c->next)
1151                 bus_match_dump(c, level + 1);
1152 }