src/libsystemd/sd-bus/bus-match.c

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