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         }
 434
 435         if (bus && bus->match_callbacks_modified)
 436                 return 0;
 437
 438         /* And now, let's invoke our siblings */
 439         return bus_match_run(bus, node->next, m);
 440 }
 441
 442 static int bus_match_add_compare_value(
 443                 struct bus_match_node *where,
 444                 enum bus_match_node_type t,
 445                 uint8_t value_u8,
 446                 const char *value_str,
 447                 struct bus_match_node **ret) {
 448
 449         struct bus_match_node *c = NULL, *n = NULL;
 450         int r;
 451
 452         assert(where);
 453         assert(where->type == BUS_MATCH_ROOT || where->type == BUS_MATCH_VALUE);
 454         assert(BUS_MATCH_IS_COMPARE(t));
 455         assert(ret);
 456
 457         for (c = where->child; c && c->type != t; c = c->next)
 458                 ;
 459
 460         if (c) {
 461                 /* Comparison node already exists? Then let's see if
 462                  * the value node exists too. */
 463
 464                 if (t == BUS_MATCH_MESSAGE_TYPE)
 465                         n = hashmap_get(c->compare.children, UINT_TO_PTR(value_u8));
 466                 else if (BUS_MATCH_CAN_HASH(t))
 467                         n = hashmap_get(c->compare.children, value_str);
 468                 else {
 469                         for (n = c->child; n && !value_node_same(n, t, value_u8, value_str); n = n->next)
 470                                 ;
 471                 }
 472
 473                 if (n) {
 474                         *ret = n;
 475                         return 0;
 476                 }
 477         } else {
 478                 /* Comparison node, doesn't exist yet? Then let's
 479                  * create it. */
 480
 481                 c = new0(struct bus_match_node, 1);
 482                 if (!c) {
 483                         r = -ENOMEM;
 484                         goto fail;
 485                 }
 486
 487                 c->type = t;
 488                 c->parent = where;
 489                 c->next = where->child;
 490                 if (c->next)
 491                         c->next->prev = c;
 492                 where->child = c;
 493
 494                 if (t == BUS_MATCH_MESSAGE_TYPE) {
 495                         c->compare.children = hashmap_new(NULL);
 496                         if (!c->compare.children) {
 497                                 r = -ENOMEM;
 498                                 goto fail;
 499                         }
 500                 } else if (BUS_MATCH_CAN_HASH(t)) {
 501                         c->compare.children = hashmap_new(&string_hash_ops);
 502                         if (!c->compare.children) {
 503                                 r = -ENOMEM;
 504                                 goto fail;
 505                         }
 506                 }
 507         }
 508
 509         n = new0(struct bus_match_node, 1);
 510         if (!n) {
 511                 r = -ENOMEM;
 512                 goto fail;
 513         }
 514
 515         n->type = BUS_MATCH_VALUE;
 516         n->value.u8 = value_u8;
 517         if (value_str) {
 518                 n->value.str = strdup(value_str);
 519                 if (!n->value.str) {
 520                         r = -ENOMEM;
 521                         goto fail;
 522                 }
 523         }
 524
 525         n->parent = c;
 526         if (c->compare.children) {
 527
 528                 if (t == BUS_MATCH_MESSAGE_TYPE)
 529                         r = hashmap_put(c->compare.children, UINT_TO_PTR(value_u8), n);
 530                 else
 531                         r = hashmap_put(c->compare.children, n->value.str, n);
 532
 533                 if (r < 0)
 534                         goto fail;
 535         } else {
 536                 n->next = c->child;
 537                 if (n->next)
 538                         n->next->prev = n;
 539                 c->child = n;
 540         }
 541
 542         *ret = n;
 543         return 1;
 544
 545 fail:
 546         if (c)
 547                 bus_match_node_maybe_free(c);
 548
 549         if (n) {
 550                 free(n->value.str);
 551                 free(n);
 552         }
 553
 554         return r;
 555 }
 556
 557 static int bus_match_find_compare_value(
 558                 struct bus_match_node *where,
 559                 enum bus_match_node_type t,
 560                 uint8_t value_u8,
 561                 const char *value_str,
 562                 struct bus_match_node **ret) {
 563
 564         struct bus_match_node *c, *n;
 565
 566         assert(where);
 567         assert(where->type == BUS_MATCH_ROOT || where->type == BUS_MATCH_VALUE);
 568         assert(BUS_MATCH_IS_COMPARE(t));
 569         assert(ret);
 570
 571         for (c = where->child; c && c->type != t; c = c->next)
 572                 ;
 573
 574         if (!c)
 575                 return 0;
 576
 577         if (t == BUS_MATCH_MESSAGE_TYPE)
 578                 n = hashmap_get(c->compare.children, UINT_TO_PTR(value_u8));
 579         else if (BUS_MATCH_CAN_HASH(t))
 580                 n = hashmap_get(c->compare.children, value_str);
 581         else {
 582                 for (n = c->child; n && !value_node_same(n, t, value_u8, value_str); n = n->next)
 583                         ;
 584         }
 585
 586         if (n) {
 587                 *ret = n;
 588                 return 1;
 589         }
 590
 591         return 0;
 592 }
 593
 594 static int bus_match_add_leaf(
 595                 struct bus_match_node *where,
 596                 struct match_callback *callback) {
 597
 598         struct bus_match_node *n;
 599
 600         assert(where);
 601         assert(where->type == BUS_MATCH_ROOT || where->type == BUS_MATCH_VALUE);
 602         assert(callback);
 603
 604         n = new0(struct bus_match_node, 1);
 605         if (!n)
 606                 return -ENOMEM;
 607
 608         n->type = BUS_MATCH_LEAF;
 609         n->parent = where;
 610         n->next = where->child;
 611         if (n->next)
 612                 n->next->prev = n;
 613
 614         n->leaf.callback = callback;
 615         callback->match_node = n;
 616
 617         where->child = n;
 618
 619         return 1;
 620 }
 621
 622 static int bus_match_find_leaf(
 623                 struct bus_match_node *where,
 624                 sd_bus_message_handler_t callback,
 625                 void *userdata,
 626                 struct bus_match_node **ret) {
 627
 628         struct bus_match_node *c;
 629
 630         assert(where);
 631         assert(where->type == BUS_MATCH_ROOT || where->type == BUS_MATCH_VALUE);
 632         assert(ret);
 633
 634         for (c = where->child; c; c = c->next) {
 635                 sd_bus_slot *s;
 636
 637                 s = container_of(c->leaf.callback, sd_bus_slot, match_callback);
 638
 639                 if (c->type == BUS_MATCH_LEAF &&
 640                     c->leaf.callback->callback == callback &&
 641                     s->userdata == userdata) {
 642                         *ret = c;
 643                         return 1;
 644                 }
 645         }
 646
 647         return 0;
 648 }
 649
 650 enum bus_match_node_type bus_match_node_type_from_string(const char *k, size_t n) {
 651         assert(k);
 652
 653         if (n == 4 && startswith(k, "type"))
 654                 return BUS_MATCH_MESSAGE_TYPE;
 655         if (n == 6 && startswith(k, "sender"))
 656                 return BUS_MATCH_SENDER;
 657         if (n == 11 && startswith(k, "destination"))
 658                 return BUS_MATCH_DESTINATION;
 659         if (n == 9 && startswith(k, "interface"))
 660                 return BUS_MATCH_INTERFACE;
 661         if (n == 6 && startswith(k, "member"))
 662                 return BUS_MATCH_MEMBER;
 663         if (n == 4 && startswith(k, "path"))
 664                 return BUS_MATCH_PATH;
 665         if (n == 14 && startswith(k, "path_namespace"))
 666                 return BUS_MATCH_PATH_NAMESPACE;
 667
 668         if (n == 4 && startswith(k, "arg")) {
 669                 int j;
 670
 671                 j = undecchar(k[3]);
 672                 if (j < 0)
 673                         return -EINVAL;
 674
 675                 return BUS_MATCH_ARG + j;
 676         }
 677
 678         if (n == 5 && startswith(k, "arg")) {
 679                 int a, b;
 680                 enum bus_match_node_type t;
 681
 682                 a = undecchar(k[3]);
 683                 b = undecchar(k[4]);
 684                 if (a <= 0 || b < 0)
 685                         return -EINVAL;
 686
 687                 t = BUS_MATCH_ARG + a * 10 + b;
 688                 if (t > BUS_MATCH_ARG_LAST)
 689                         return -EINVAL;
 690
 691                 return t;
 692         }
 693
 694         if (n == 8 && startswith(k, "arg") && startswith(k + 4, "path")) {
 695                 int j;
 696
 697                 j = undecchar(k[3]);
 698                 if (j < 0)
 699                         return -EINVAL;
 700
 701                 return BUS_MATCH_ARG_PATH + j;
 702         }
 703
 704         if (n == 9 && startswith(k, "arg") && startswith(k + 5, "path")) {
 705                 enum bus_match_node_type t;
 706                 int a, b;
 707
 708                 a = undecchar(k[3]);
 709                 b = undecchar(k[4]);
 710                 if (a <= 0 || b < 0)
 711                         return -EINVAL;
 712
 713                 t = BUS_MATCH_ARG_PATH + a * 10 + b;
 714                 if (t > BUS_MATCH_ARG_PATH_LAST)
 715                         return -EINVAL;
 716
 717                 return t;
 718         }
 719
 720         if (n == 13 && startswith(k, "arg") && startswith(k + 4, "namespace")) {
 721                 int j;
 722
 723                 j = undecchar(k[3]);
 724                 if (j < 0)
 725                         return -EINVAL;
 726
 727                 return BUS_MATCH_ARG_NAMESPACE + j;
 728         }
 729
 730         if (n == 14 && startswith(k, "arg") && startswith(k + 5, "namespace")) {
 731                 enum bus_match_node_type t;
 732                 int a, b;
 733
 734                 a = undecchar(k[3]);
 735                 b = undecchar(k[4]);
 736                 if (a <= 0 || b < 0)
 737                         return -EINVAL;
 738
 739                 t = BUS_MATCH_ARG_NAMESPACE + a * 10 + b;
 740                 if (t > BUS_MATCH_ARG_NAMESPACE_LAST)
 741                         return -EINVAL;
 742
 743                 return t;
 744         }
 745
 746         if (n == 7 && startswith(k, "arg") && startswith(k + 4, "has")) {
 747                 int j;
 748
 749                 j = undecchar(k[3]);
 750                 if (j < 0)
 751                         return -EINVAL;
 752
 753                 return BUS_MATCH_ARG_HAS + j;
 754         }
 755
 756         if (n == 8 && startswith(k, "arg") && startswith(k + 5, "has")) {
 757                 enum bus_match_node_type t;
 758                 int a, b;
 759
 760                 a = undecchar(k[3]);
 761                 b = undecchar(k[4]);
 762                 if (a <= 0 || b < 0)
 763                         return -EINVAL;
 764
 765                 t = BUS_MATCH_ARG_HAS + a * 10 + b;
 766                 if (t > BUS_MATCH_ARG_HAS_LAST)
 767                         return -EINVAL;
 768
 769                 return t;
 770         }
 771
 772         return -EINVAL;
 773 }
 774
 775 static int match_component_compare(const void *a, const void *b) {
 776         const struct bus_match_component *x = a, *y = b;
 777
 778         if (x->type < y->type)
 779                 return -1;
 780         if (x->type > y->type)
 781                 return 1;
 782
 783         return 0;
 784 }
 785
 786 void bus_match_parse_free(struct bus_match_component *components, unsigned n_components) {
 787         unsigned i;
 788
 789         for (i = 0; i < n_components; i++)
 790                 free(components[i].value_str);
 791
 792         free(components);
 793 }
 794
 795 int bus_match_parse(
 796                 const char *match,
 797                 struct bus_match_component **_components,
 798                 unsigned *_n_components) {
 799
 800         const char *p = match;
 801         struct bus_match_component *components = NULL;
 802         size_t components_allocated = 0;
 803         unsigned n_components = 0, i;
 804         _cleanup_free_ char *value = NULL;
 805         int r;
 806
 807         assert(match);
 808         assert(_components);
 809         assert(_n_components);
 810
 811         while (*p != 0) {
 812                 const char *eq, *q;
 813                 enum bus_match_node_type t;
 814                 unsigned j = 0;
 815                 size_t value_allocated = 0;
 816                 bool escaped = false, quoted;
 817                 uint8_t u;
 818
 819                 /* Avahi's match rules appear to include whitespace, skip over it */
 820                 p += strspn(p, " ");
 821
 822                 eq = strchr(p, '=');
 823                 if (!eq)
 824                         return -EINVAL;
 825
 826                 t = bus_match_node_type_from_string(p, eq - p);
 827                 if (t < 0)
 828                         return -EINVAL;
 829
 830                 quoted = eq[1] == '\'';
 831
 832                 for (q = eq + 1 + quoted;; q++) {
 833
 834                         if (*q == 0) {
 835
 836                                 if (quoted) {
 837                                         r = -EINVAL;
 838                                         goto fail;
 839                                 } else {
 840                                         if (value)
 841                                                 value[j] = 0;
 842                                         break;
 843                                 }
 844                         }
 845
 846                         if (!escaped) {
 847                                 if (*q == '\\') {
 848                                         escaped = true;
 849                                         continue;
 850                                 }
 851
 852                                 if (quoted) {
 853                                         if (*q == '\'') {
 854                                                 if (value)
 855                                                         value[j] = 0;
 856                                                 break;
 857                                         }
 858                                 } else {
 859                                         if (*q == ',') {
 860                                                 if (value)
 861                                                         value[j] = 0;
 862
 863                                                 break;
 864                                         }
 865                                 }
 866                         }
 867
 868                         if (!GREEDY_REALLOC(value, value_allocated, j + 2)) {
 869                                 r = -ENOMEM;
 870                                 goto fail;
 871                         }
 872
 873                         value[j++] = *q;
 874                         escaped = false;
 875                 }
 876
 877                 if (!value) {
 878                         value = strdup("");
 879                         if (!value) {
 880                                 r = -ENOMEM;
 881                                 goto fail;
 882                         }
 883                 }
 884
 885                 if (t == BUS_MATCH_MESSAGE_TYPE) {
 886                         r = bus_message_type_from_string(value, &u);
 887                         if (r < 0)
 888                                 goto fail;
 889
 890                         value = mfree(value);
 891                 } else
 892                         u = 0;
 893
 894                 if (!GREEDY_REALLOC(components, components_allocated, n_components + 1)) {
 895                         r = -ENOMEM;
 896                         goto fail;
 897                 }
 898
 899                 components[n_components].type = t;
 900                 components[n_components].value_str = value;
 901                 components[n_components].value_u8 = u;
 902                 n_components++;
 903
 904                 value = NULL;
 905
 906                 if (q[quoted] == 0)
 907                         break;
 908
 909                 if (q[quoted] != ',') {
 910                         r = -EINVAL;
 911                         goto fail;
 912                 }
 913
 914                 p = q + 1 + quoted;
 915         }
 916
 917         /* Order the whole thing, so that we always generate the same tree */
 918         qsort_safe(components, n_components, sizeof(struct bus_match_component), match_component_compare);
 919
 920         /* Check for duplicates */
 921         for (i = 0; i+1 < n_components; i++)
 922                 if (components[i].type == components[i+1].type) {
 923                         r = -EINVAL;
 924                         goto fail;
 925                 }
 926
 927         *_components = components;
 928         *_n_components = n_components;
 929
 930         return 0;
 931
 932 fail:
 933         bus_match_parse_free(components, n_components);
 934         return r;
 935 }
 936
 937 char *bus_match_to_string(struct bus_match_component *components, unsigned n_components) {
 938         _cleanup_fclose_ FILE *f = NULL;
 939         char *buffer = NULL;
 940         size_t size = 0;
 941         unsigned i;
 942         int r;
 943
 944         if (n_components <= 0)
 945                 return strdup("");
 946
 947         assert(components);
 948
 949         f = open_memstream(&buffer, &size);
 950         if (!f)
 951                 return NULL;
 952
 953         for (i = 0; i < n_components; i++) {
 954                 char buf[32];
 955
 956                 if (i != 0)
 957                         fputc(',', f);
 958
 959                 fputs(bus_match_node_type_to_string(components[i].type, buf, sizeof(buf)), f);
 960                 fputc('=', f);
 961                 fputc('\'', f);
 962
 963                 if (components[i].type == BUS_MATCH_MESSAGE_TYPE)
 964                         fputs(bus_message_type_to_string(components[i].value_u8), f);
 965                 else
 966                         fputs(components[i].value_str, f);
 967
 968                 fputc('\'', f);
 969         }
 970
 971         r = fflush_and_check(f);
 972         if (r < 0)
 973                 return NULL;
 974
 975         return buffer;
 976 }
 977
 978 int bus_match_add(
 979                 struct bus_match_node *root,
 980                 struct bus_match_component *components,
 981                 unsigned n_components,
 982                 struct match_callback *callback) {
 983
 984         unsigned i;
 985         struct bus_match_node *n;
 986         int r;
 987
 988         assert(root);
 989         assert(callback);
 990
 991         n = root;
 992         for (i = 0; i < n_components; i++) {
 993                 r = bus_match_add_compare_value(
 994                                 n, components[i].type,
 995                                 components[i].value_u8, components[i].value_str, &n);
 996                 if (r < 0)
 997                         return r;
 998         }
 999
1000         return bus_match_add_leaf(n, callback);
1001 }
1002
1003 int bus_match_remove(
1004                 struct bus_match_node *root,
1005                 struct match_callback *callback) {
1006
1007         struct bus_match_node *node, *pp;
1008
1009         assert(root);
1010         assert(callback);
1011
1012         node = callback->match_node;
1013         if (!node)
1014                 return 0;
1015
1016         assert(node->type == BUS_MATCH_LEAF);
1017
1018         callback->match_node = NULL;
1019
1020         /* Free the leaf */
1021         pp = node->parent;
1022         bus_match_node_free(node);
1023
1024         /* Prune the tree above */
1025         while (pp) {
1026                 node = pp;
1027                 pp = node->parent;
1028
1029                 if (!bus_match_node_maybe_free(node))
1030                         break;
1031         }
1032
1033         return 1;
1034 }
1035
1036 int bus_match_find(
1037                 struct bus_match_node *root,
1038                 struct bus_match_component *components,
1039                 unsigned n_components,
1040                 sd_bus_message_handler_t callback,
1041                 void *userdata,
1042                 struct match_callback **ret) {
1043
1044         struct bus_match_node *n, **gc;
1045         unsigned i;
1046         int r;
1047
1048         assert(root);
1049         assert(ret);
1050
1051         gc = newa(struct bus_match_node*, n_components);
1052
1053         n = root;
1054         for (i = 0; i < n_components; i++) {
1055                 r = bus_match_find_compare_value(
1056                                 n, components[i].type,
1057                                 components[i].value_u8, components[i].value_str,
1058                                 &n);
1059                 if (r <= 0)
1060                         return r;
1061
1062                 gc[i] = n;
1063         }
1064
1065         r = bus_match_find_leaf(n, callback, userdata, &n);
1066         if (r <= 0)
1067                 return r;
1068
1069         *ret = n->leaf.callback;
1070         return 1;
1071 }
1072
1073 void bus_match_free(struct bus_match_node *node) {
1074         struct bus_match_node *c;
1075
1076         if (!node)
1077                 return;
1078
1079         if (BUS_MATCH_CAN_HASH(node->type)) {
1080                 Iterator i;
1081
1082                 HASHMAP_FOREACH(c, node->compare.children, i)
1083                         bus_match_free(c);
1084
1085                 assert(hashmap_isempty(node->compare.children));
1086         }
1087
1088         while ((c = node->child))
1089                 bus_match_free(c);
1090
1091         if (node->type != BUS_MATCH_ROOT)
1092                 bus_match_node_free(node);
1093 }
1094
1095 const char* bus_match_node_type_to_string(enum bus_match_node_type t, char buf[], size_t l) {
1096         switch (t) {
1097
1098         case BUS_MATCH_ROOT:
1099                 return "root";
1100
1101         case BUS_MATCH_VALUE:
1102                 return "value";
1103
1104         case BUS_MATCH_LEAF:
1105                 return "leaf";
1106
1107         case BUS_MATCH_MESSAGE_TYPE:
1108                 return "type";
1109
1110         case BUS_MATCH_SENDER:
1111                 return "sender";
1112
1113         case BUS_MATCH_DESTINATION:
1114                 return "destination";
1115
1116         case BUS_MATCH_INTERFACE:
1117                 return "interface";
1118
1119         case BUS_MATCH_MEMBER:
1120                 return "member";
1121
1122         case BUS_MATCH_PATH:
1123                 return "path";
1124
1125         case BUS_MATCH_PATH_NAMESPACE:
1126                 return "path_namespace";
1127
1128         case BUS_MATCH_ARG ... BUS_MATCH_ARG_LAST:
1129                 snprintf(buf, l, "arg%i", t - BUS_MATCH_ARG);
1130                 return buf;
1131
1132         case BUS_MATCH_ARG_PATH ... BUS_MATCH_ARG_PATH_LAST:
1133                 snprintf(buf, l, "arg%ipath", t - BUS_MATCH_ARG_PATH);
1134                 return buf;
1135
1136         case BUS_MATCH_ARG_NAMESPACE ... BUS_MATCH_ARG_NAMESPACE_LAST:
1137                 snprintf(buf, l, "arg%inamespace", t - BUS_MATCH_ARG_NAMESPACE);
1138                 return buf;
1139
1140         case BUS_MATCH_ARG_HAS ... BUS_MATCH_ARG_HAS_LAST:
1141                 snprintf(buf, l, "arg%ihas", t - BUS_MATCH_ARG_HAS);
1142                 return buf;
1143
1144         default:
1145                 return NULL;
1146         }
1147 }
1148
1149 void bus_match_dump(struct bus_match_node *node, unsigned level) {
1150         struct bus_match_node *c;
1151         _cleanup_free_ char *pfx = NULL;
1152         char buf[32];
1153
1154         if (!node)
1155                 return;
1156
1157         pfx = strrep("  ", level);
1158         printf("%s[%s]", strempty(pfx), bus_match_node_type_to_string(node->type, buf, sizeof(buf)));
1159
1160         if (node->type == BUS_MATCH_VALUE) {
1161                 if (node->parent->type == BUS_MATCH_MESSAGE_TYPE)
1162                         printf(" <%u>\n", node->value.u8);
1163                 else
1164                         printf(" <%s>\n", node->value.str);
1165         } else if (node->type == BUS_MATCH_ROOT)
1166                 puts(" root");
1167         else if (node->type == BUS_MATCH_LEAF)
1168                 printf(" %p/%p\n", node->leaf.callback->callback, container_of(node->leaf.callback, sd_bus_slot, match_callback)->userdata);
1169         else
1170                 putchar('\n');
1171
1172         if (BUS_MATCH_CAN_HASH(node->type)) {
1173                 Iterator i;
1174
1175                 HASHMAP_FOREACH(c, node->compare.children, i)
1176                         bus_match_dump(c, level + 1);
1177         }
1178
1179         for (c = node->child; c; c = c->next)
1180                 bus_match_dump(c, level + 1);
1181 }
1182
1183 enum bus_match_scope bus_match_get_scope(const struct bus_match_component *components, unsigned n_components) {
1184         bool found_driver = false;
1185         unsigned i;
1186
1187         if (n_components <= 0)
1188                 return BUS_MATCH_GENERIC;
1189
1190         assert(components);
1191
1192         /* Checks whether the specified match can only match the
1193          * pseudo-service for local messages, which we detect by
1194          * sender, interface or path. If a match is not restricted to
1195          * local messages, then we check if it only matches on the
1196          * driver. */
1197
1198         for (i = 0; i < n_components; i++) {
1199                 const struct bus_match_component *c = components + i;
1200
1201                 if (c->type == BUS_MATCH_SENDER) {
1202                         if (streq_ptr(c->value_str, "org.freedesktop.DBus.Local"))
1203                                 return BUS_MATCH_LOCAL;
1204
1205                         if (streq_ptr(c->value_str, "org.freedesktop.DBus"))
1206                                 found_driver = true;
1207                 }
1208
1209                 if (c->type == BUS_MATCH_INTERFACE && streq_ptr(c->value_str, "org.freedesktop.DBus.Local"))
1210                         return BUS_MATCH_LOCAL;
1211
1212                 if (c->type == BUS_MATCH_PATH && streq_ptr(c->value_str, "/org/freedesktop/DBus/Local"))
1213                         return BUS_MATCH_LOCAL;
1214         }
1215
1216         return found_driver ? BUS_MATCH_DRIVER : BUS_MATCH_GENERIC;
1217
1218 }